dbcheck: fallback to the default tombstoneLifetime of 180 days
[metze/samba/wip.git] / python / samba / dbchecker.py
index 8a9ee438cf679996d4e25f3189f7b03a3516fbc9..04304b0b0dc5f72f700492929dad06ea216cd099 100644 (file)
@@ -17,6 +17,7 @@
 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
 #
 
+from __future__ import print_function
 import ldb
 import samba
 import time
@@ -34,13 +35,34 @@ from samba.auth import system_session, admin_session
 from samba.netcmd import CommandError
 from samba.netcmd.fsmo import get_fsmo_roleowner
 
+# vals is a sequence of ldb.bytes objects which are a subclass
+# of 'byte' type in python3 and just a str type in python2, to
+# display as string these need to be converted to string via (str)
+# function in python3 but that may generate a UnicodeDecode error,
+# if so use repr instead.  We need to at least try to get the 'str'
+# value if possible to allow some tests which check the strings
+# outputted to pass, these tests compare attr values logged to stdout
+# against those in various results files.
+
+def dump_attr_values(vals):
+    result = ""
+    for value in vals:
+        if len(result):
+            result = "," + result
+        try:
+            result = result + str(value)
+        except UnicodeDecodeError:
+            result = result + repr(value)
+    return result
 
 class dbcheck(object):
     """check a SAM database for errors"""
 
     def __init__(self, samdb, samdb_schema=None, verbose=False, fix=False,
                  yes=False, quiet=False, in_transaction=False,
-                 reset_well_known_acls=False):
+                 quick_membership_checks=False,
+                 reset_well_known_acls=False,
+                 check_expired_tombstones=False):
         self.samdb = samdb
         self.dict_oid_name = None
         self.samdb_schema = (samdb_schema or samdb)
@@ -59,13 +81,16 @@ class dbcheck(object):
         self.fix_all_string_dn_component_mismatch = False
         self.fix_all_GUID_dn_component_mismatch = False
         self.fix_all_SID_dn_component_mismatch = False
+        self.fix_all_SID_dn_component_missing = False
         self.fix_all_old_dn_string_component_mismatch = False
         self.fix_all_metadata = False
         self.fix_time_metadata = False
         self.fix_undead_linked_attributes = False
         self.fix_all_missing_backlinks = False
         self.fix_all_orphaned_backlinks = False
-        self.fix_all_duplicate_links = False
+        self.fix_all_missing_forward_links = False
+        self.duplicate_link_cache = dict()
+        self.recover_all_forward_links = False
         self.fix_rmd_flags = False
         self.fix_ntsecuritydescriptor = False
         self.fix_ntsecuritydescriptor_owner_group = False
@@ -83,7 +108,10 @@ class dbcheck(object):
         self.fix_utf8_userparameters = False
         self.fix_doubled_userparameters = False
         self.fix_sid_rid_set_conflict = False
+        self.quick_membership_checks = quick_membership_checks
         self.reset_well_known_acls = reset_well_known_acls
+        self.check_expired_tombstones = check_expired_tombstones
+        self.expired_tombstones = 0
         self.reset_all_well_known_acls = False
         self.in_transaction = in_transaction
         self.infrastructure_dn = ldb.Dn(samdb, "CN=Infrastructure," + samdb.domain_dn())
@@ -97,16 +125,18 @@ class dbcheck(object):
         self.fix_missing_deleted_objects = False
         self.fix_replica_locations = False
         self.fix_missing_rid_set_master = False
+        self.fix_changes_after_deletion_bug = False
 
         self.dn_set = set()
         self.link_id_cache = {}
         self.name_map = {}
         try:
             res = samdb.search(base="CN=DnsAdmins,CN=Users,%s" % samdb.domain_dn(), scope=ldb.SCOPE_BASE,
-                           attrs=["objectSid"])
+                               attrs=["objectSid"])
             dnsadmins_sid = ndr_unpack(security.dom_sid, res[0]["objectSid"][0])
             self.name_map['DnsAdmins'] = str(dnsadmins_sid)
-        except ldb.LdbError, (enum, estr):
+        except ldb.LdbError as e5:
+            (enum, estr) = e5.args
             if enum != ldb.ERR_NO_SUCH_OBJECT:
                 raise
             pass
@@ -140,11 +170,11 @@ class dbcheck(object):
 
         for nc in self.ncs:
             try:
-                dn = self.samdb.get_wellknown_dn(ldb.Dn(self.samdb, nc),
+                dn = self.samdb.get_wellknown_dn(ldb.Dn(self.samdb, nc.decode('utf8')),
                                                  dsdb.DS_GUID_DELETED_OBJECTS_CONTAINER)
                 self.deleted_objects_containers.append(dn)
             except KeyError:
-                self.ncs_lacking_deleted_containers.append(ldb.Dn(self.samdb, nc))
+                self.ncs_lacking_deleted_containers.append(ldb.Dn(self.samdb, nc.decode('utf8')))
 
         domaindns_zone = 'DC=DomainDnsZones,%s' % self.samdb.get_default_basedn()
         forestdns_zone = 'DC=ForestDnsZones,%s' % self.samdb.get_root_basedn()
@@ -174,17 +204,47 @@ class dbcheck(object):
         res = self.samdb.search(base=ldb.Dn(self.samdb, self.samdb.get_serverName()),
                                 scope=ldb.SCOPE_BASE, attrs=["serverReference"])
         # 2. Get server reference
-        self.server_ref_dn = ldb.Dn(self.samdb, res[0]['serverReference'][0])
+        self.server_ref_dn = ldb.Dn(self.samdb, res[0]['serverReference'][0].decode('utf8'))
 
         # 3. Get RID Set
         res = self.samdb.search(base=self.server_ref_dn,
                                 scope=ldb.SCOPE_BASE, attrs=['rIDSetReferences'])
         if "rIDSetReferences" in res[0]:
-            self.rid_set_dn = ldb.Dn(self.samdb, res[0]['rIDSetReferences'][0])
+            self.rid_set_dn = ldb.Dn(self.samdb, res[0]['rIDSetReferences'][0].decode('utf8'))
         else:
             self.rid_set_dn = None
 
-    def check_database(self, DN=None, scope=ldb.SCOPE_SUBTREE, controls=[], attrs=['*']):
+        ntds_service_dn = "CN=Directory Service,CN=Windows NT,CN=Services,%s" % \
+                          self.samdb.get_config_basedn().get_linearized()
+        res = samdb.search(base=ntds_service_dn,
+                           scope=ldb.SCOPE_BASE,
+                           expression="(objectClass=nTDSService)",
+                           attrs=["tombstoneLifetime"])
+        if "tombstoneLifetime" in res[0]:
+            self.tombstoneLifetime = int(res[0]["tombstoneLifetime"][0])
+        else:
+            self.tombstoneLifetime = 180
+
+        self.compatibleFeatures = []
+        self.requiredFeatures = []
+
+        try:
+            res = self.samdb.search(scope=ldb.SCOPE_BASE,
+                                    base="@SAMBA_DSDB",
+                                    attrs=["compatibleFeatures",
+                                           "requiredFeatures"])
+            if "compatibleFeatures" in res[0]:
+                self.compatibleFeatures = res[0]["compatibleFeatures"]
+            if "requiredFeatures" in res[0]:
+                self.requiredFeatures = res[0]["requiredFeatures"]
+        except ldb.LdbError as e6:
+            (enum, estr) = e6.args
+            if enum != ldb.ERR_NO_SUCH_OBJECT:
+                raise
+            pass
+
+    def check_database(self, DN=None, scope=ldb.SCOPE_SUBTREE, controls=None,
+                       attrs=None):
         '''perform a database check, returning the number of errors found'''
         res = self.samdb.search(base=DN, scope=scope, attrs=['dn'], controls=controls)
         self.report('Checking %u objects' % len(res))
@@ -201,6 +261,13 @@ class dbcheck(object):
         if DN is None:
             error_count += self.check_rootdse()
 
+        if self.expired_tombstones > 0:
+            self.report("NOTICE: found %d expired tombstones, "
+                        "'samba' will remove them daily, "
+                        "'samba-tool domain tombstones expunge' "
+                        "would do that immediately." % (
+                        self.expired_tombstones))
+
         if error_count != 0 and not self.fix:
             self.report("Please use --fix to fix these errors")
 
@@ -234,7 +301,8 @@ class dbcheck(object):
                                          "CN=Deleted Objects\\0ACNF:%s" % str(misc.GUID(guid)))
                     conflict_dn.add_base(nc)
 
-            except ldb.LdbError, (enum, estr):
+            except ldb.LdbError as e2:
+                (enum, estr) = e2.args
                 if enum == ldb.ERR_NO_SUCH_OBJECT:
                     pass
                 else:
@@ -244,7 +312,8 @@ class dbcheck(object):
             if conflict_dn is not None:
                 try:
                     self.samdb.rename(dn, conflict_dn, ["show_deleted:1", "relax:0", "show_recycled:1"])
-                except ldb.LdbError, (enum, estr):
+                except ldb.LdbError as e1:
+                    (enum, estr) = e1.args
                     self.report("Couldn't move old Deleted Objects placeholder: %s to %s: %s" % (dn, conflict_dn, estr))
                     return 1
 
@@ -262,14 +331,14 @@ class dbcheck(object):
             listwko = []
             proposed_objectguid = None
             for o in wko:
-                dsdb_dn = dsdb_Dn(self.samdb, o, dsdb.DSDB_SYNTAX_BINARY_DN)
+                dsdb_dn = dsdb_Dn(self.samdb, o.decode('utf8'), dsdb.DSDB_SYNTAX_BINARY_DN)
                 if self.is_deleted_objects_dn(dsdb_dn):
                     self.report("wellKnownObjects had duplicate Deleted Objects value %s" % o)
                     # We really want to put this back in the same spot
                     # as the original one, so that on replication we
                     # merge, rather than conflict.
                     proposed_objectguid = dsdb_dn.dn.get_extended_component("GUID")
-                listwko.append(o)
+                listwko.append(str(o))
 
             if proposed_objectguid is not None:
                 guid_suffix = "\nobjectGUID: %s" % str(misc.GUID(proposed_objectguid))
@@ -350,7 +419,7 @@ systemFlags: -1946157056%s""" % (dn, guid_suffix),
         try:
             controls = controls + ["local_oid:%s:0" % dsdb.DSDB_CONTROL_DBCHECK]
             self.samdb.delete(dn, controls=controls)
-        except Exception, err:
+        except Exception as err:
             if self.in_transaction:
                 raise CommandError("%s : %s" % (msg, err))
             self.report("%s : %s" % (msg, err))
@@ -359,12 +428,13 @@ systemFlags: -1946157056%s""" % (dn, guid_suffix),
 
     def do_modify(self, m, controls, msg, validate=True):
         '''perform a modify with optional verbose output'''
+        controls = controls + ["local_oid:%s:0" % dsdb.DSDB_CONTROL_DBCHECK]
         if self.verbose:
             self.report(self.samdb.write_ldif(m, ldb.CHANGETYPE_MODIFY))
+            self.report("controls: %r" % controls)
         try:
-            controls = controls + ["local_oid:%s:0" % dsdb.DSDB_CONTROL_DBCHECK]
             self.samdb.modify(m, controls=controls, validate=validate)
-        except Exception, err:
+        except Exception as err:
             if self.in_transaction:
                 raise CommandError("%s : %s" % (msg, err))
             self.report("%s : %s" % (msg, err))
@@ -383,7 +453,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             to_dn = to_rdn + to_base
             controls = controls + ["local_oid:%s:0" % dsdb.DSDB_CONTROL_DBCHECK]
             self.samdb.rename(from_dn, to_dn, controls=controls)
-        except Exception, err:
+        except Exception as err:
             if self.in_transaction:
                 raise CommandError("%s : %s" % (msg, err))
             self.report("%s : %s" % (msg, err))
@@ -439,7 +509,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             m['value_%u' % i] = ldb.MessageElement(val, ldb.FLAG_MOD_DELETE, attrname)
             if nval != '':
                 m['normv_%u' % i] = ldb.MessageElement(nval, ldb.FLAG_MOD_ADD,
-                    attrname)
+                                                       attrname)
 
         if self.do_modify(m, ["relax:0", "show_recycled:1"],
                           "Failed to normalise attribute %s" % attrname,
@@ -469,7 +539,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
     def err_duplicate_values(self, dn, attrname, dup_values, values):
         '''fix attribute normalisation errors'''
         self.report("ERROR: Duplicate values for attribute '%s' in '%s'" % (attrname, dn))
-        self.report("Values contain a duplicate: [%s]/[%s]!" % (','.join(dup_values), ','.join(values)))
+        self.report("Values contain a duplicate: [%s]/[%s]!" % (','.join(dump_attr_values(dup_values)), ','.join(dump_attr_values(values))))
         if not self.confirm_all("Fix duplicates for '%s' from '%s'?" % (attrname, dn), 'fix_all_duplicates'):
             self.report("Not fixing attribute '%s'" % attrname)
             return
@@ -523,6 +593,19 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
     def err_missing_target_dn_or_GUID(self, dn, attrname, val, dsdb_dn):
         """handle a missing target DN (if specified, GUID form can't be found,
         and otherwise DN string form can't be found)"""
+
+        # Don't change anything if the object itself is deleted
+        if str(dn).find('\\0ADEL') != -1:
+            # We don't bump the error count as Samba produces these
+            # in normal operation
+            self.report("WARNING: no target object found for GUID "
+                        "component link %s in deleted object "
+                        "%s - %s" % (attrname, dn, val))
+            self.report("Not removing dangling one-way "
+                        "link on deleted object "
+                        "(tombstone garbage collection in progress?)")
+            return 0
+
         # check if its a backlink
         linkID, _ = self.get_attr_linkID_and_reverse_name(attrname)
         if (linkID & 1 == 0) and str(dsdb_dn).find('\\0ADEL') == -1:
@@ -573,11 +656,12 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
     def err_missing_dn_GUID_component(self, dn, attrname, val, dsdb_dn, errstr):
         """handle a missing GUID extended DN component"""
         self.report("ERROR: %s component for %s in object %s - %s" % (errstr, attrname, dn, val))
-        controls=["extended_dn:1:1", "show_recycled:1"]
+        controls = ["extended_dn:1:1", "show_recycled:1"]
         try:
             res = self.samdb.search(base=str(dsdb_dn.dn), scope=ldb.SCOPE_BASE,
                                     attrs=[], controls=controls)
-        except ldb.LdbError, (enum, estr):
+        except ldb.LdbError as e7:
+            (enum, estr) = e7.args
             self.report("unable to find object for DN %s - (%s)" % (dsdb_dn.dn, estr))
             if enum != ldb.ERR_NO_SUCH_OBJECT:
                 raise
@@ -604,7 +688,6 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
     def err_incorrect_binary_dn(self, dn, attrname, val, dsdb_dn, errstr):
         """handle an incorrect binary DN component"""
         self.report("ERROR: %s binary component for %s in object %s - %s" % (errstr, attrname, dn, val))
-        controls=["extended_dn:1:1", "show_recycled:1"]
 
         if not self.confirm_all('Change DN to %s?' % str(dsdb_dn), 'fix_all_binary_dn'):
             self.report("Not fixing %s" % errstr)
@@ -631,7 +714,8 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         m.dn = dn
         m['old_value'] = ldb.MessageElement(val, ldb.FLAG_MOD_DELETE, attrname)
         m['new_value'] = ldb.MessageElement(str(dsdb_dn), ldb.FLAG_MOD_ADD, attrname)
-        if self.do_modify(m, ["show_recycled:1"],
+        if self.do_modify(m, ["show_recycled:1",
+                              "local_oid:%s:1" % dsdb.DSDB_CONTROL_DBCHECK_FIX_LINK_DN_NAME],
                           "Failed to fix old DN string on attribute %s" % (attrname)):
             self.report("Fixed old DN string on attribute %s" % (attrname))
 
@@ -652,6 +736,38 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                           "Failed to fix incorrect DN %s on attribute %s" % (mismatch_type, attrname)):
             self.report("Fixed incorrect DN %s on attribute %s" % (mismatch_type, attrname))
 
+    def err_dn_component_missing_target_sid(self, dn, attrname, val, dsdb_dn, target_sid_blob):
+        """handle a DN string being incorrect"""
+        self.report("ERROR: missing DN SID component for %s in object %s - %s" % (attrname, dn, val))
+
+        if len(dsdb_dn.prefix) != 0:
+            self.report("Not fixing missing DN SID on DN+BINARY or DN+STRING")
+            return
+
+        correct_dn = ldb.Dn(self.samdb, dsdb_dn.dn.extended_str())
+        correct_dn.set_extended_component("SID", target_sid_blob)
+
+        if not self.confirm_all('Change DN to %s?' % correct_dn.extended_str(),
+                                'fix_all_SID_dn_component_missing'):
+            self.report("Not fixing missing DN SID component")
+            return
+
+        target_guid_blob = correct_dn.get_extended_component("GUID")
+        guid_sid_dn = ldb.Dn(self.samdb, "")
+        guid_sid_dn.set_extended_component("GUID", target_guid_blob)
+        guid_sid_dn.set_extended_component("SID", target_sid_blob)
+
+        m = ldb.Message()
+        m.dn = dn
+        m['new_value'] = ldb.MessageElement(guid_sid_dn.extended_str(), ldb.FLAG_MOD_ADD, attrname)
+        controls = [
+            "show_recycled:1",
+            "local_oid:%s:1" % dsdb.DSDB_CONTROL_DBCHECK_FIX_LINK_DN_SID
+        ]
+        if self.do_modify(m, controls,
+                          "Failed to ADD missing DN SID on attribute %s" % (attrname)):
+            self.report("Fixed missing DN SID on attribute %s" % (attrname))
+
     def err_unknown_attribute(self, obj, attrname):
         '''handle an unknown attribute error'''
         self.report("ERROR: unknown attribute '%s' in %s" % (attrname, obj.dn))
@@ -708,31 +824,44 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                           "Failed to fix incorrect RMD_FLAGS %u" % rmd_flags):
             self.report("Fixed incorrect RMD_FLAGS %u" % (rmd_flags))
 
-    def err_orphaned_backlink(self, obj, backlink_attr, backlink_val, target_dn, forward_attr, forward_syntax):
+    def err_orphaned_backlink(self, obj_dn, backlink_attr, backlink_val,
+                              target_dn, forward_attr, forward_syntax,
+                              check_duplicates=True):
         '''handle a orphaned backlink value'''
-        self.report("ERROR: orphaned backlink attribute '%s' in %s for link %s in %s" % (backlink_attr, obj.dn, forward_attr, target_dn))
+        if check_duplicates is True and self.has_duplicate_links(target_dn, forward_attr, forward_syntax):
+            self.report("WARNING: Keep orphaned backlink attribute " +
+                        "'%s' in '%s' for link '%s' in '%s'" % (
+                            backlink_attr, obj_dn, forward_attr, target_dn))
+            return
+        self.report("ERROR: orphaned backlink attribute '%s' in %s for link %s in %s" % (backlink_attr, obj_dn, forward_attr, target_dn))
         if not self.confirm_all('Remove orphaned backlink %s' % backlink_attr, 'fix_all_orphaned_backlinks'):
             self.report("Not removing orphaned backlink %s" % backlink_attr)
             return
         m = ldb.Message()
-        m.dn = obj.dn
+        m.dn = obj_dn
         m['value'] = ldb.MessageElement(backlink_val, ldb.FLAG_MOD_DELETE, backlink_attr)
         if self.do_modify(m, ["show_recycled:1", "relax:0"],
                           "Failed to fix orphaned backlink %s" % backlink_attr):
             self.report("Fixed orphaned backlink %s" % (backlink_attr))
 
-    def err_duplicate_links(self, obj, attrname, vals):
+    def err_recover_forward_links(self, obj, forward_attr, forward_vals):
         '''handle a duplicate links value'''
 
-        if not self.confirm_all("Remove duplicate links in attribute '%s'" % attrname, 'fix_all_duplicate_links'):
-            self.report("Not removing duplicate links in attribute '%s'" % attrname)
+        self.report("RECHECK: 'Missing/Duplicate/Correct link' lines above for attribute '%s' in '%s'" % (forward_attr, obj.dn))
+
+        if not self.confirm_all("Commit fixes for (missing/duplicate) forward links in attribute '%s'" % forward_attr, 'recover_all_forward_links'):
+            self.report("Not fixing corrupted (missing/duplicate) forward links in attribute '%s' of '%s'" % (
+                        forward_attr, obj.dn))
             return
         m = ldb.Message()
         m.dn = obj.dn
-        m['value'] = ldb.MessageElement(vals, ldb.FLAG_MOD_REPLACE, attrname)
-        if self.do_modify(m, ["local_oid:1.3.6.1.4.1.7165.4.3.19.2:1"],
-                "Failed to fix duplicate links in attribute '%s'" % attrname):
-            self.report("Fixed duplicate links in attribute '%s'" % (attrname))
+        m['value'] = ldb.MessageElement(forward_vals, ldb.FLAG_MOD_REPLACE, forward_attr)
+        if self.do_modify(m, ["local_oid:%s:1" % dsdb.DSDB_CONTROL_DBCHECK_FIX_DUPLICATE_LINKS],
+                          "Failed to fix duplicate links in attribute '%s'" % forward_attr):
+            self.report("Fixed duplicate links in attribute '%s'" % (forward_attr))
+            duplicate_cache_key = "%s:%s" % (str(obj.dn), forward_attr)
+            assert duplicate_cache_key in self.duplicate_link_cache
+            self.duplicate_link_cache[duplicate_cache_key] = False
 
     def err_no_fsmoRoleOwner(self, obj):
         '''handle a missing fSMORoleOwner'''
@@ -740,7 +869,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         res = self.samdb.search("",
                                 scope=ldb.SCOPE_BASE, attrs=["dsServiceName"])
         assert len(res) == 1
-        serviceName = res[0]["dsServiceName"][0]
+        serviceName = str(res[0]["dsServiceName"][0])
         if not self.confirm_all('Sieze role %s onto current DC by adding fSMORoleOwner=%s' % (obj.dn, serviceName), 'seize_fsmo_role'):
             self.report("Not Siezing role %s onto current DC by adding fSMORoleOwner=%s" % (obj.dn, serviceName))
             return
@@ -761,7 +890,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         keep_transaction = False
         self.samdb.transaction_start()
         try:
-            nc_root = self.samdb.get_nc_root(obj.dn);
+            nc_root = self.samdb.get_nc_root(obj.dn)
             lost_and_found = self.samdb.get_wellknown_dn(nc_root, dsdb.DS_GUID_LOSTANDFOUND_CONTAINER)
             new_dn = ldb.Dn(self.samdb, str(obj.dn))
             new_dn.remove_base_components(len(new_dn) - 1)
@@ -786,7 +915,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         else:
             self.samdb.transaction_cancel()
 
-    def err_wrong_dn(self, obj, new_dn, rdn_attr, rdn_val, name_val):
+    def err_wrong_dn(self, obj, new_dn, rdn_attr, rdn_val, name_val, controls):
         '''handle a wrong dn'''
 
         new_rdn = ldb.Dn(self.samdb, str(new_dn))
@@ -803,7 +932,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             self.report("Not renaming %s to %s" % (obj.dn, new_dn))
             return
 
-        if self.do_rename(obj.dn, new_rdn, new_parent, ["show_recycled:1", "relax:0"],
+        if self.do_rename(obj.dn, new_rdn, new_parent, controls,
                           "Failed to rename object %s into %s" % (obj.dn, new_dn)):
             self.report("Renamed %s into %s" % (obj.dn, new_dn))
 
@@ -863,8 +992,19 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
         m = ldb.Message()
         m.dn = obj.dn
-        m['value'] = ldb.MessageElement(obj[attrname][0].decode('utf-16-le').decode('utf-16-le').encode('utf-16-le'),
+        # m['value'] = ldb.MessageElement(obj[attrname][0].decode('utf-16-le').decode('utf-16-le').encode('utf-16-le'),
+        # hmm the above old python2 code doesn't make sense to me and cannot
+        # work in python3 because a string doesn't have a decode method.
+        # However in python2 for some unknown reason this double decode
+        # followed by encode seems to result in what looks like utf8.
+        # In python2 just .decode('utf-16-le').encode('utf-16-le') does nothing
+        # but trigger the 'double UTF16 encoded' condition again :/
+        #
+        # In python2 and python3 value.decode('utf-16-le').encode('utf8') seems
+        # to do the trick and work as expected.
+        m['value'] = ldb.MessageElement(obj[attrname][0].decode('utf-16-le').encode('utf8'),
                                         ldb.FLAG_MOD_REPLACE, 'userParameters')
+
         if self.do_modify(m, [],
                           "Failed to correct doubled-UTF16 encoded userParameters on %s by converting" % (obj.dn)):
             self.report("Corrected doubled-UTF16 encoded userParameters on %s by converting" % (obj.dn))
@@ -879,35 +1019,33 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                                 controls=["show_deleted:0", "extended_dn:0", "reveal_internals:0"])
         syntax_oid = self.samdb_schema.get_syntax_oid_from_lDAPDisplayName(attrname)
         for val in res[0][attrname]:
-            dsdb_dn = dsdb_Dn(self.samdb, val, syntax_oid)
+            dsdb_dn = dsdb_Dn(self.samdb, val.decode('utf8'), syntax_oid)
             guid2 = dsdb_dn.dn.get_extended_component("GUID")
             if guid == guid2:
                 return dsdb_dn
         return None
 
-    def check_dn(self, obj, attrname, syntax_oid):
-        '''check a DN attribute for correctness'''
+    def check_duplicate_links(self, obj, forward_attr, forward_syntax, forward_linkID, backlink_attr):
+        '''check a linked values for duplicate forward links'''
         error_count = 0
-        obj_guid = obj['objectGUID'][0]
-
-        linkID, reverse_link_name = self.get_attr_linkID_and_reverse_name(attrname)
-        if reverse_link_name is not None:
-            reverse_syntax_oid = self.samdb_schema.get_syntax_oid_from_lDAPDisplayName(reverse_link_name)
-        else:
-            reverse_syntax_oid = None
 
         duplicate_dict = dict()
-        duplicate_list = list()
         unique_dict = dict()
-        unique_list = list()
-        for val in obj[attrname]:
-            if linkID & 1:
-                #
-                # Only cleanup forward links here,
-                # back links are handled below.
-                break
 
-            dsdb_dn = dsdb_Dn(self.samdb, val, syntax_oid)
+        # Only forward links can have this problem
+        if forward_linkID & 1:
+            # If we got the reverse, skip it
+            return (error_count, duplicate_dict, unique_dict)
+
+        if backlink_attr is None:
+            return (error_count, duplicate_dict, unique_dict)
+
+        duplicate_cache_key = "%s:%s" % (str(obj.dn), forward_attr)
+        if duplicate_cache_key not in self.duplicate_link_cache:
+            self.duplicate_link_cache[duplicate_cache_key] = False
+
+        for val in obj[forward_attr]:
+            dsdb_dn = dsdb_Dn(self.samdb, val.decode('utf8'), forward_syntax)
 
             # all DNs should have a GUID component
             guid = dsdb_dn.dn.get_extended_component("GUID")
@@ -917,14 +1055,12 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             keystr = guidstr + dsdb_dn.prefix
             if keystr not in unique_dict:
                 unique_dict[keystr] = dsdb_dn
-                unique_list.append(keystr)
                 continue
             error_count += 1
             if keystr not in duplicate_dict:
                 duplicate_dict[keystr] = dict()
                 duplicate_dict[keystr]["keep"] = None
                 duplicate_dict[keystr]["delete"] = list()
-                duplicate_list.append(keystr)
 
             # Now check for the highest RMD_VERSION
             v1 = int(unique_dict[keystr].dn.get_extended_component("RMD_VERSION"))
@@ -949,31 +1085,214 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             duplicate_dict[keystr]["delete"].append(unique_dict[keystr])
             unique_dict[keystr] = dsdb_dn
 
-        if len(duplicate_list) != 0:
-            self.report("ERROR: Duplicate link values for attribute '%s' in '%s'" % (attrname, obj.dn))
-            for keystr in duplicate_list:
+        if error_count != 0:
+            self.duplicate_link_cache[duplicate_cache_key] = True
+
+        return (error_count, duplicate_dict, unique_dict)
+
+    def has_duplicate_links(self, dn, forward_attr, forward_syntax):
+        '''check a linked values for duplicate forward links'''
+        error_count = 0
+
+        duplicate_cache_key = "%s:%s" % (str(dn), forward_attr)
+        if duplicate_cache_key in self.duplicate_link_cache:
+            return self.duplicate_link_cache[duplicate_cache_key]
+
+        forward_linkID, backlink_attr = self.get_attr_linkID_and_reverse_name(forward_attr)
+
+        attrs = [forward_attr]
+        controls = ["extended_dn:1:1", "reveal_internals:0"]
+
+        # check its the right GUID
+        try:
+            res = self.samdb.search(base=str(dn), scope=ldb.SCOPE_BASE,
+                                    attrs=attrs, controls=controls)
+        except ldb.LdbError as e8:
+            (enum, estr) = e8.args
+            if enum != ldb.ERR_NO_SUCH_OBJECT:
+                raise
+
+            return False
+
+        obj = res[0]
+        error_count, duplicate_dict, unique_dict = \
+            self.check_duplicate_links(obj, forward_attr, forward_syntax, forward_linkID, backlink_attr)
+
+        if duplicate_cache_key in self.duplicate_link_cache:
+            return self.duplicate_link_cache[duplicate_cache_key]
+
+        return False
+
+    def find_missing_forward_links_from_backlinks(self, obj,
+                                                  forward_attr,
+                                                  forward_syntax,
+                                                  backlink_attr,
+                                                  forward_unique_dict):
+        '''Find all backlinks linking to obj_guid_str not already in forward_unique_dict'''
+        missing_forward_links = []
+        error_count = 0
+
+        if backlink_attr is None:
+            return (missing_forward_links, error_count)
+
+        if forward_syntax != ldb.SYNTAX_DN:
+            self.report("Not checking for missing forward links for syntax: %s" %
+                        forward_syntax)
+            return (missing_forward_links, error_count)
+
+        if "sortedLinks" in self.compatibleFeatures:
+            self.report("Not checking for missing forward links because the db " +
+                        "has the sortedLinks feature")
+            return (missing_forward_links, error_count)
+
+        try:
+            obj_guid = obj['objectGUID'][0]
+            obj_guid_str = str(ndr_unpack(misc.GUID, obj_guid))
+            filter = "(%s=<GUID=%s>)" % (backlink_attr, obj_guid_str)
+
+            res = self.samdb.search(expression=filter,
+                                    scope=ldb.SCOPE_SUBTREE, attrs=["objectGUID"],
+                                    controls=["extended_dn:1:1",
+                                              "search_options:1:2",
+                                              "paged_results:1:1000"])
+        except ldb.LdbError as e9:
+            (enum, estr) = e9.args
+            raise
+
+        for r in res:
+            target_dn = dsdb_Dn(self.samdb, r.dn.extended_str(), forward_syntax)
+
+            guid = target_dn.dn.get_extended_component("GUID")
+            guidstr = str(misc.GUID(guid))
+            if guidstr in forward_unique_dict:
+                continue
+
+            # A valid forward link looks like this:
+            #
+            #    <GUID=9f92d30a-fc23-11e4-a5f6-30be15454808>;
+            #    <RMD_ADDTIME=131607546230000000>;
+            #    <RMD_CHANGETIME=131607546230000000>;
+            #    <RMD_FLAGS=0>;
+            #    <RMD_INVOCID=4e4496a3-7fb8-4f97-8a33-d238db8b5e2d>;
+            #    <RMD_LOCAL_USN=3765>;
+            #    <RMD_ORIGINATING_USN=3765>;
+            #    <RMD_VERSION=1>;
+            #    <SID=S-1-5-21-4177067393-1453636373-93818738-1124>;
+            #    CN=unsorted-u8,CN=Users,DC=release-4-5-0-pre1,DC=samba,DC=corp
+            #
+            # Note that versions older than Samba 4.8 create
+            # links with RMD_VERSION=0.
+            #
+            # Try to get the local_usn and time from objectClass
+            # if possible and fallback to any other one.
+            repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob,
+                              obj['replPropertyMetadata'][0])
+            for o in repl.ctr.array:
+                local_usn = o.local_usn
+                t = o.originating_change_time
+                if o.attid == drsuapi.DRSUAPI_ATTID_objectClass:
+                    break
+
+            # We use a magic invocationID for restoring missing
+            # forward links to recover from bug #13228.
+            # This should allow some more future magic to fix the
+            # problem.
+            #
+            # It also means it looses the conflict resolution
+            # against almost every real invocation, if the
+            # version is also 0.
+            originating_invocid = misc.GUID("ffffffff-4700-4700-4700-000000b13228")
+            originating_usn = 1
+
+            rmd_addtime = t
+            rmd_changetime = t
+            rmd_flags = 0
+            rmd_invocid = originating_invocid
+            rmd_originating_usn = originating_usn
+            rmd_local_usn = local_usn
+            rmd_version = 0
+
+            target_dn.dn.set_extended_component("RMD_ADDTIME", str(rmd_addtime))
+            target_dn.dn.set_extended_component("RMD_CHANGETIME", str(rmd_changetime))
+            target_dn.dn.set_extended_component("RMD_FLAGS", str(rmd_flags))
+            target_dn.dn.set_extended_component("RMD_INVOCID", ndr_pack(rmd_invocid))
+            target_dn.dn.set_extended_component("RMD_ORIGINATING_USN", str(rmd_originating_usn))
+            target_dn.dn.set_extended_component("RMD_LOCAL_USN", str(rmd_local_usn))
+            target_dn.dn.set_extended_component("RMD_VERSION", str(rmd_version))
+
+            error_count += 1
+            missing_forward_links.append(target_dn)
+
+        return (missing_forward_links, error_count)
+
+    def check_dn(self, obj, attrname, syntax_oid):
+        '''check a DN attribute for correctness'''
+        error_count = 0
+        obj_guid = obj['objectGUID'][0]
+
+        linkID, reverse_link_name = self.get_attr_linkID_and_reverse_name(attrname)
+        if reverse_link_name is not None:
+            reverse_syntax_oid = self.samdb_schema.get_syntax_oid_from_lDAPDisplayName(reverse_link_name)
+        else:
+            reverse_syntax_oid = None
+
+        is_member_link = attrname in ("member", "memberOf")
+        if is_member_link and self.quick_membership_checks:
+            duplicate_dict = {}
+        else:
+            error_count, duplicate_dict, unique_dict = \
+                self.check_duplicate_links(obj, attrname, syntax_oid,
+                                           linkID, reverse_link_name)
+
+        if len(duplicate_dict) != 0:
+
+            missing_forward_links, missing_error_count = \
+                self.find_missing_forward_links_from_backlinks(obj,
+                                                               attrname, syntax_oid,
+                                                               reverse_link_name,
+                                                               unique_dict)
+            error_count += missing_error_count
+
+            forward_links = [dn for dn in unique_dict.values()]
+
+            if missing_error_count != 0:
+                self.report("ERROR: Missing and duplicate forward link values for attribute '%s' in '%s'" % (
+                            attrname, obj.dn))
+            else:
+                self.report("ERROR: Duplicate forward link values for attribute '%s' in '%s'" % (attrname, obj.dn))
+            for m in missing_forward_links:
+                self.report("Missing   link '%s'" % (m))
+                if not self.confirm_all("Schedule readding missing forward link for attribute %s" % attrname,
+                                        'fix_all_missing_forward_links'):
+                    self.err_orphaned_backlink(m.dn, reverse_link_name,
+                                               obj.dn.extended_str(), obj.dn,
+                                               attrname, syntax_oid,
+                                               check_duplicates=False)
+                    continue
+                forward_links += [m]
+            for keystr in duplicate_dict.keys():
                 d = duplicate_dict[keystr]
                 for dd in d["delete"]:
                     self.report("Duplicate link '%s'" % dd)
                 self.report("Correct   link '%s'" % d["keep"])
 
-            vals = []
-            for keystr in unique_list:
-                dsdb_dn = unique_dict[keystr]
-                vals.append(str(dsdb_dn))
-            self.err_duplicate_links(obj, attrname, vals)
+            # We now construct the sorted dn values.
+            # They're sorted by the objectGUID of the target
+            # See dsdb_Dn.__cmp__()
+            vals = [str(dn) for dn in sorted(forward_links)]
+            self.err_recover_forward_links(obj, attrname, vals)
             # We should continue with the fixed values
-            obj[attrname] = ldb.MessageElement(vals, ldb.FLAG_MOD_REPLACE, attrname)
+            obj[attrname] = ldb.MessageElement(vals, 0, attrname)
 
         for val in obj[attrname]:
-            dsdb_dn = dsdb_Dn(self.samdb, val, syntax_oid)
+            dsdb_dn = dsdb_Dn(self.samdb, val.decode('utf8'), syntax_oid)
 
             # all DNs should have a GUID component
             guid = dsdb_dn.dn.get_extended_component("GUID")
             if guid is None:
                 error_count += 1
                 self.err_missing_dn_GUID_component(obj.dn, attrname, val, dsdb_dn,
-                    "missing GUID")
+                                                   "missing GUID")
                 continue
 
             guidstr = str(misc.GUID(guid))
@@ -993,8 +1312,9 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 res = self.samdb.search(base="<GUID=%s>" % guidstr, scope=ldb.SCOPE_BASE,
                                         attrs=attrs, controls=["extended_dn:1:1", "show_recycled:1",
                                                                "reveal_internals:0"
-                                        ])
-            except ldb.LdbError, (enum, estr):
+                                                               ])
+            except ldb.LdbError as e3:
+                (enum, estr) = e3.args
                 if enum != ldb.ERR_NO_SUCH_OBJECT:
                     raise
 
@@ -1009,17 +1329,16 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 dsdb_dn.prefix = "B:8:%08X:" % int(res[0]['instanceType'][0])
                 dsdb_dn.binary = "%08X" % int(res[0]['instanceType'][0])
 
-                if str(dsdb_dn) != val:
-                    error_count +=1
+                if str(dsdb_dn) != str(val):
+                    error_count += 1
                     self.err_incorrect_binary_dn(obj.dn, attrname, val, dsdb_dn, "incorrect instanceType part of Binary DN")
                     continue
 
             # now we have two cases - the source object might or might not be deleted
-            is_deleted = 'isDeleted' in obj and obj['isDeleted'][0].upper() == 'TRUE'
-            target_is_deleted = 'isDeleted' in res[0] and res[0]['isDeleted'][0].upper() == 'TRUE'
+            is_deleted = 'isDeleted' in obj and str(obj['isDeleted'][0]).upper() == 'TRUE'
+            target_is_deleted = 'isDeleted' in res[0] and str(res[0]['isDeleted'][0]).upper() == 'TRUE'
 
-
-            if is_deleted and not obj.dn in self.deleted_objects_containers and linkID:
+            if is_deleted and obj.dn not in self.deleted_objects_containers and linkID:
                 # A fully deleted object should not have any linked
                 # attributes. (MS-ADTS 3.1.1.5.5.1.1 Tombstone
                 # Requirements and 3.1.1.5.5.1.3 Recycled-Object
@@ -1035,7 +1354,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 if local_usn:
                     if 'replPropertyMetaData' in res[0]:
                         repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob,
-                                          str(res[0]['replPropertyMetadata']))
+                                          res[0]['replPropertyMetadata'][0])
                         found_data = False
                         for o in repl.ctr.array:
                             if o.attid == drsuapi.DRSUAPI_ATTID_isDeleted:
@@ -1079,27 +1398,45 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                                                       res[0].dn, "GUID")
                 continue
 
-            if res[0].dn.get_extended_component("SID") != dsdb_dn.dn.get_extended_component("SID"):
+            target_sid = res[0].dn.get_extended_component("SID")
+            link_sid = dsdb_dn.dn.get_extended_component("SID")
+            if link_sid is None and target_sid is not None:
+                error_count += 1
+                self.err_dn_component_missing_target_sid(obj.dn, attrname, val,
+                                                         dsdb_dn, target_sid)
+                continue
+            if link_sid != target_sid:
                 error_count += 1
                 self.err_dn_component_target_mismatch(obj.dn, attrname, val, dsdb_dn,
                                                       res[0].dn, "SID")
                 continue
 
+            # Only for non-links, not even forward-only links
+            # (otherwise this breaks repl_meta_data):
+            #
             # Now we have checked the GUID and SID, offer to fix old
-            # DN strings as a non-error (for forward links with no
+            # DN strings as a non-error (DNs, not links so no
             # backlink).  Samba does not maintain this string
             # otherwise, so we don't increment error_count.
             if reverse_link_name is None:
-                if str(res[0].dn) != str(dsdb_dn.dn):
-                    self.err_dn_string_component_old(obj.dn, attrname, val, dsdb_dn,
-                                                     res[0].dn)
+                if linkID == 0 and str(res[0].dn) != str(dsdb_dn.dn):
+                    # Pass in the old/bad DN without the <GUID=...> part,
+                    # otherwise the LDB code will correct it on the way through
+                    # (Note: we still want to preserve the DSDB DN prefix in the
+                    # case of binary DNs)
+                    bad_dn = dsdb_dn.prefix + dsdb_dn.dn.get_linearized()
+                    self.err_dn_string_component_old(obj.dn, attrname, bad_dn,
+                                                     dsdb_dn, res[0].dn)
+                continue
+
+            if is_member_link and self.quick_membership_checks:
                 continue
 
             # check the reverse_link is correct if there should be one
             match_count = 0
             if reverse_link_name in res[0]:
                 for v in res[0][reverse_link_name]:
-                    v_dn = dsdb_Dn(self.samdb, v)
+                    v_dn = dsdb_Dn(self.samdb, v.decode('utf8'))
                     v_guid = v_dn.dn.get_extended_component("GUID")
                     v_blob = v_dn.dn.get_extended_component("RMD_FLAGS")
                     v_rmd_flags = 0
@@ -1116,7 +1453,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                         # Forward binary multi-valued linked attribute
                         forward_count = 0
                         for w in obj[attrname]:
-                            w_guid = dsdb_Dn(self.samdb, w).dn.get_extended_component("GUID")
+                            w_guid = dsdb_Dn(self.samdb, w.decode('utf8')).dn.get_extended_component("GUID")
                             if w_guid == guid:
                                 forward_count += 1
 
@@ -1124,7 +1461,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                             continue
             expected_count = 0
             for v in obj[attrname]:
-                v_dn = dsdb_Dn(self.samdb, v)
+                v_dn = dsdb_Dn(self.samdb, v.decode('utf8'))
                 v_guid = v_dn.dn.get_extended_component("GUID")
                 v_blob = v_dn.dn.get_extended_component("RMD_FLAGS")
                 v_rmd_flags = 0
@@ -1146,7 +1483,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 # UNLESS, there is no forward link detected.
                 if match_count == 0:
                     error_count += 1
-                    self.err_orphaned_backlink(obj, attrname,
+                    self.err_orphaned_backlink(obj.dn, attrname,
                                                val, dsdb_dn.dn,
                                                reverse_link_name,
                                                reverse_syntax_oid)
@@ -1179,14 +1516,19 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                                               dsdb_dn.dn)
                     diff_count -= 1
                 else:
-                    self.err_orphaned_backlink(res[0], reverse_link_name,
+                    self.err_orphaned_backlink(res[0].dn, reverse_link_name,
                                                obj.dn.extended_str(), obj.dn,
                                                attrname, syntax_oid)
                     diff_count += 1
 
-
         return error_count
 
+    def find_repl_attid(self, repl, attid):
+        for o in repl.ctr.array:
+            if o.attid == attid:
+                return o
+
+        return None
 
     def get_originating_time(self, val, attid):
         '''Read metadata properties and return the originating time for
@@ -1195,13 +1537,10 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
            :return: the originating time or 0 if not found
         '''
 
-        repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob, str(val))
-        obj = repl.ctr
-
-        for o in repl.ctr.array:
-            if o.attid == attid:
-                return o.originating_change_time
-
+        repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob, val)
+        o = self.find_repl_attid(repl, attid)
+        if o is not None:
+            return o.originating_change_time
         return 0
 
     def process_metadata(self, dn, val):
@@ -1213,8 +1552,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         list_attid = []
         in_schema_nc = dn.is_child_of(self.schema_dn)
 
-        repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob, str(val))
-        obj = repl.ctr
+        repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob, val)
 
         for o in repl.ctr.array:
             att = self.samdb_schema.get_lDAPDisplayName_by_attid(o.attid)
@@ -1227,15 +1565,14 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
         return (set_att, list_attid, wrong_attids)
 
-
     def fix_metadata(self, obj, attr):
         '''re-write replPropertyMetaData elements for a single attribute for a
         object. This is used to fix missing replPropertyMetaData elements'''
         guid_str = str(ndr_unpack(misc.GUID, obj['objectGUID'][0]))
         dn = ldb.Dn(self.samdb, "<GUID=%s>" % guid_str)
-        res = self.samdb.search(base = dn, scope=ldb.SCOPE_BASE, attrs = [attr],
-                                controls = ["search_options:1:2",
-                                            "show_recycled:1"])
+        res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE, attrs=[attr],
+                                controls=["search_options:1:2",
+                                          "show_recycled:1"])
         msg = res[0]
         nmsg = ldb.Message()
         nmsg.dn = dn
@@ -1283,9 +1620,9 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         sd_attr = "nTSecurityDescriptor"
         sd_val = obj[sd_attr]
 
-        sd = ndr_unpack(security.descriptor, str(sd_val))
+        sd = ndr_unpack(security.descriptor, sd_val[0])
 
-        is_deleted = 'isDeleted' in obj and obj['isDeleted'][0].upper() == 'TRUE'
+        is_deleted = 'isDeleted' in obj and str(obj['isDeleted'][0]).upper() == 'TRUE'
         if is_deleted:
             # we don't fix deleted objects
             return (sd, None)
@@ -1361,7 +1698,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         cls = None
         try:
             cls = obj["objectClass"][-1]
-        except KeyError, e:
+        except KeyError as e:
             pass
 
         if cls is None:
@@ -1369,7 +1706,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                                     attrs=["isDeleted", "objectClass"],
                                     controls=["show_recycled:1"])
             o = res[0]
-            is_deleted = 'isDeleted' in o and o['isDeleted'][0].upper() == 'TRUE'
+            is_deleted = 'isDeleted' in o and str(o['isDeleted'][0]).upper() == 'TRUE'
             if is_deleted:
                 # we don't fix deleted objects
                 return (sd, None)
@@ -1405,7 +1742,6 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         '''re-write the SD due to not matching the default (optional mode for fixing an incorrect provision)'''
         sd_attr = "nTSecurityDescriptor"
         sd_val = ndr_pack(sd)
-        sd_old_val = ndr_pack(sd_old)
         sd_flags = security.SECINFO_DACL | security.SECINFO_SACL
         if sd.owner_sid is not None:
             sd_flags |= security.SECINFO_OWNER
@@ -1454,10 +1790,135 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             self.report("Fixed attribute '%s' of '%s'\n" % (sd_attr, dn))
         self.samdb.set_session_info(self.system_session_info)
 
+    def is_expired_tombstone(self, dn, repl_val):
+        if self.check_expired_tombstones:
+            # This is not the default, it's just
+            # used to keep dbcheck tests work with
+            # old static provision dumps
+            return False
+
+        repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob, repl_val)
+
+        isDeleted = self.find_repl_attid(repl, drsuapi.DRSUAPI_ATTID_isDeleted)
+
+        delete_time = samba.nttime2unix(isDeleted.originating_change_time)
+        current_time = time.time()
+
+        tombstone_delta = self.tombstoneLifetime * (24 * 60 * 60)
+
+        delta = current_time - delete_time
+        if delta <= tombstone_delta:
+            return False
+
+        self.report("SKIPING: object %s is an expired tombstone" % dn)
+        self.report("isDeleted: attid=0x%08x version=%d invocation=%s usn=%s (local=%s) at %s" % (
+                    isDeleted.attid,
+                    isDeleted.version,
+                    isDeleted.originating_invocation_id,
+                    isDeleted.originating_usn,
+                    isDeleted.local_usn,
+                    time.ctime(samba.nttime2unix(isDeleted.originating_change_time))))
+        self.expired_tombstones += 1
+        return True
+
+    def find_changes_after_deletion(self, repl_val):
+        repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob, repl_val)
+
+        isDeleted = self.find_repl_attid(repl, drsuapi.DRSUAPI_ATTID_isDeleted)
+
+        delete_time = samba.nttime2unix(isDeleted.originating_change_time)
+
+        tombstone_delta = self.tombstoneLifetime * (24 * 60 * 60)
+
+        found = []
+        for o in repl.ctr.array:
+            if o.attid == drsuapi.DRSUAPI_ATTID_isDeleted:
+                continue
+
+            if o.local_usn <= isDeleted.local_usn:
+                continue
+
+            if o.originating_change_time <= isDeleted.originating_change_time:
+                continue
+
+            change_time = samba.nttime2unix(o.originating_change_time)
+
+            delta = change_time - delete_time
+            if delta <= tombstone_delta:
+                continue
+
+            # If the modification happened after the tombstone lifetime
+            # has passed, we have a bug as the object might be deleted
+            # already on other DCs and won't be able to replicate
+            # back
+            found.append(o)
+
+        return found, isDeleted
+
+    def has_changes_after_deletion(self, dn, repl_val):
+        found, isDeleted = self.find_changes_after_deletion(repl_val)
+        if len(found) == 0:
+            return False
+
+        def report_attid(o):
+            try:
+                attname = self.samdb_schema.get_lDAPDisplayName_by_attid(o.attid)
+            except KeyError:
+                attname = "<unknown:0x%x08x>" % o.attid
+
+            self.report("%s: attid=0x%08x version=%d invocation=%s usn=%s (local=%s) at %s" % (
+                        attname, o.attid, o.version,
+                        o.originating_invocation_id,
+                        o.originating_usn,
+                        o.local_usn,
+                        time.ctime(samba.nttime2unix(o.originating_change_time))))
+
+        self.report("ERROR: object %s, has changes after deletion" % dn)
+        report_attid(isDeleted)
+        for o in found:
+            report_attid(o)
+
+        return True
+
+    def err_changes_after_deletion(self, dn, repl_val):
+        found, isDeleted = self.find_changes_after_deletion(repl_val)
+
+        in_schema_nc = dn.is_child_of(self.schema_dn)
+        rdn_attr = dn.get_rdn_name()
+        rdn_attid = self.samdb_schema.get_attid_from_lDAPDisplayName(rdn_attr,
+                                                     is_schema_nc=in_schema_nc)
+
+        unexpected = []
+        for o in found:
+            if o.attid == rdn_attid:
+                continue
+            if o.attid == drsuapi.DRSUAPI_ATTID_name:
+                continue
+            if o.attid == drsuapi.DRSUAPI_ATTID_lastKnownParent:
+                continue
+            try:
+                attname = self.samdb_schema.get_lDAPDisplayName_by_attid(o.attid)
+            except KeyError:
+                attname = "<unknown:0x%x08x>" % o.attid
+            unexpected.append(attname)
+
+        if len(unexpected) > 0:
+            self.report('Unexpeted attributes: %s' % ",".join(unexpected))
+            self.report('Not fixing changes after deletion bug')
+            return
+
+        if not self.confirm_all('Delete broken tombstone object %s deleted %s days ago?' % (
+                                dn, self.tombstoneLifetime), 'fix_changes_after_deletion_bug'):
+            self.report('Not fixing changes after deletion bug')
+            return
+
+        if self.do_delete(dn, ["relax:0"],
+                          "Failed to remove DN %s" % dn):
+            self.report("Removed DN %s" % dn)
 
     def has_replmetadata_zero_invocationid(self, dn, repl_meta_data):
         repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob,
-                          str(repl_meta_data))
+                          repl_meta_data)
         ctr = repl.ctr
         found = False
         for o in ctr.array:
@@ -1475,10 +1936,9 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
         return found
 
-
     def err_replmetadata_zero_invocationid(self, dn, attr, repl_meta_data):
         repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob,
-                          str(repl_meta_data))
+                          repl_meta_data)
         ctr = repl.ctr
         now = samba.unix2nttime(int(time.time()))
         found = False
@@ -1513,10 +1973,9 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                               "Failed to fix attribute %s" % attr):
                 self.report("Fixed attribute '%s' of '%s'\n" % (attr, dn))
 
-
     def err_replmetadata_unknown_attid(self, dn, attr, repl_meta_data):
         repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob,
-                          str(repl_meta_data))
+                          repl_meta_data)
         ctr = repl.ctr
         for o in ctr.array:
             # Search for an invalid attid
@@ -1526,10 +1985,9 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 self.report('ERROR: attributeID 0X%0X is not known in our schema, not fixing %s on %s\n' % (o.attid, attr, dn))
                 return
 
-
     def err_replmetadata_incorrect_attid(self, dn, attr, repl_meta_data, wrong_attids):
         repl = ndr_unpack(drsblobs.replPropertyMetaDataBlob,
-                          str(repl_meta_data))
+                          repl_meta_data)
         fix = False
 
         set_att = set()
@@ -1547,7 +2005,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         # the correct values are above 0x80000000) values first and
         # remove the 'second' value we see.
         for o in reversed(ctr.array):
-            print "%s: 0x%08x" % (dn, o.attid)
+            print("%s: 0x%08x" % (dn, o.attid))
             att = self.samdb_schema.get_lDAPDisplayName_by_attid(o.attid)
             if att.lower() in set_att:
                 self.report('ERROR: duplicate attributeID values for %s in %s on %s\n' % (att, attr, dn))
@@ -1617,38 +2075,37 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         nmsg.dn = dn
         nmsg[attr] = ldb.MessageElement(replBlob, ldb.FLAG_MOD_REPLACE, attr)
         if self.do_modify(nmsg, ["local_oid:%s:0" % dsdb.DSDB_CONTROL_DBCHECK_MODIFY_RO_REPLICA,
-                             "local_oid:1.3.6.1.4.1.7165.4.3.14:0",
-                             "local_oid:1.3.6.1.4.1.7165.4.3.25:0"],
-                      "Failed to fix attribute %s" % attr):
+                                 "local_oid:1.3.6.1.4.1.7165.4.3.14:0",
+                                 "local_oid:1.3.6.1.4.1.7165.4.3.25:0"],
+                          "Failed to fix attribute %s" % attr):
             self.report("Fixed attribute '%s' of '%s'\n" % (attr, dn))
 
-
     def is_deleted_deleted_objects(self, obj):
         faulty = False
         if "description" not in obj:
             self.report("ERROR: description not present on Deleted Objects container %s" % obj.dn)
             faulty = True
-        if "showInAdvancedViewOnly" not in obj or obj['showInAdvancedViewOnly'][0].upper() == 'FALSE':
+        if "showInAdvancedViewOnly" not in obj or str(obj['showInAdvancedViewOnly'][0]).upper() == 'FALSE':
             self.report("ERROR: showInAdvancedViewOnly not present on Deleted Objects container %s" % obj.dn)
             faulty = True
         if "objectCategory" not in obj:
             self.report("ERROR: objectCategory not present on Deleted Objects container %s" % obj.dn)
             faulty = True
-        if "isCriticalSystemObject" not in obj or obj['isCriticalSystemObject'][0].upper() == 'FALSE':
+        if "isCriticalSystemObject" not in obj or str(obj['isCriticalSystemObject'][0]).upper() == 'FALSE':
             self.report("ERROR: isCriticalSystemObject not present on Deleted Objects container %s" % obj.dn)
             faulty = True
         if "isRecycled" in obj:
             self.report("ERROR: isRecycled present on Deleted Objects container %s" % obj.dn)
             faulty = True
-        if "isDeleted" in obj and obj['isDeleted'][0].upper() == 'FALSE':
+        if "isDeleted" in obj and str(obj['isDeleted'][0]).upper() == 'FALSE':
             self.report("ERROR: isDeleted not set on Deleted Objects container %s" % obj.dn)
             faulty = True
         if "objectClass" not in obj or (len(obj['objectClass']) != 2 or
-                                        obj['objectClass'][0] != 'top' or
-                                        obj['objectClass'][1] != 'container'):
+                                        str(obj['objectClass'][0]) != 'top' or
+                                        str(obj['objectClass'][1]) != 'container'):
             self.report("ERROR: objectClass incorrectly set on Deleted Objects container %s" % obj.dn)
             faulty = True
-        if "systemFlags" not in obj or obj['systemFlags'][0] != '-1946157056':
+        if "systemFlags" not in obj or str(obj['systemFlags'][0]) != '-1946157056':
             self.report("ERROR: systemFlags incorrectly set on Deleted Objects container %s" % obj.dn)
             faulty = True
         return faulty
@@ -1687,7 +2144,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         target = self.samdb.get_dsServiceName()
 
         if self.samdb.am_rodc():
-            self.report('Not fixing %s for the RODC' % (attr, obj.dn))
+            self.report('Not fixing %s %s for the RODC' % (attr, obj.dn))
             return
 
         if not self.confirm_all('Add yourself to the replica locations for %s?'
@@ -1720,13 +2177,13 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             instancetype |= dsdb.INSTANCE_TYPE_IS_NC_HEAD
             try:
                 self.samdb.search(base=dn.parent(), scope=ldb.SCOPE_BASE, attrs=[], controls=["show_recycled:1"])
-            except ldb.LdbError, (enum, estr):
+            except ldb.LdbError as e4:
+                (enum, estr) = e4.args
                 if enum != ldb.ERR_NO_SUCH_OBJECT:
                     raise
             else:
                 instancetype |= dsdb.INSTANCE_TYPE_NC_ABOVE
-
-        if self.write_ncs is not None and str(nc_root) in self.write_ncs:
+        if self.write_ncs is not None and str(nc_root) in [str(x) for x in self.write_ncs]:
             instancetype |= dsdb.INSTANCE_TYPE_WRITE
 
         return instancetype
@@ -1741,14 +2198,15 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
         raise KeyError
 
-    def check_object(self, dn, attrs=['*']):
+    def check_object(self, dn, attrs=None):
         '''check one object'''
         if self.verbose:
             self.report("Checking object %s" % dn)
-
-        # If we modify the pass-by-reference attrs variable, then we get a
-        # replPropertyMetadata for every object that we check.
-        attrs = list(attrs)
+        if attrs is None:
+            attrs = ['*']
+        else:
+            # make a local copy to modify
+            attrs = list(attrs)
         if "dn" in map(str.lower, attrs):
             attrs.append("name")
         if "distinguishedname" in map(str.lower, attrs):
@@ -1759,10 +2217,21 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             attrs.append(dn.get_rdn_name())
             attrs.append("isDeleted")
             attrs.append("systemFlags")
+        need_replPropertyMetaData = False
         if '*' in attrs:
-            attrs.append("replPropertyMetaData")
+            need_replPropertyMetaData = True
         else:
-            attrs.append("objectGUID")
+            for a in attrs:
+                linkID, _ = self.get_attr_linkID_and_reverse_name(a)
+                if linkID == 0:
+                    continue
+                if linkID & 1:
+                    continue
+                need_replPropertyMetaData = True
+                break
+        if need_replPropertyMetaData:
+            attrs.append("replPropertyMetaData")
+        attrs.append("objectGUID")
 
         try:
             sd_flags = 0
@@ -1780,7 +2249,8 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                                         "reveal_internals:0",
                                     ],
                                     attrs=attrs)
-        except ldb.LdbError, (enum, estr):
+        except ldb.LdbError as e10:
+            (enum, estr) = e10.args
             if enum == ldb.ERR_NO_SUCH_OBJECT:
                 if self.in_transaction:
                     self.report("ERROR: Object %s disappeared during check" % dn)
@@ -1794,7 +2264,6 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         error_count = 0
         set_attrs_from_md = set()
         set_attrs_seen = set()
-        got_repl_property_meta_data = False
         got_objectclass = False
 
         nc_dn = self.samdb.get_nc_root(obj.dn)
@@ -1806,12 +2275,31 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             # NCs
             deleted_objects_dn = None
 
-
         object_rdn_attr = None
         object_rdn_val = None
         name_val = None
         isDeleted = False
         systemFlags = 0
+        repl_meta_data_val = None
+
+        for attrname in obj:
+            if str(attrname).lower() == 'isdeleted':
+                if str(obj[attrname][0]) != "FALSE":
+                    isDeleted = True
+
+            if str(attrname).lower() == 'systemflags':
+                systemFlags = int(obj[attrname][0])
+
+            if str(attrname).lower() == 'replpropertymetadata':
+                repl_meta_data_val = obj[attrname][0]
+
+        if isDeleted and repl_meta_data_val:
+            if self.has_changes_after_deletion(dn, repl_meta_data_val):
+                error_count += 1
+                self.err_changes_after_deletion(dn, repl_meta_data_val)
+                return error_count
+            if self.is_expired_tombstone(dn, repl_meta_data_val):
+                return error_count
 
         for attrname in obj:
             if attrname == 'dn' or attrname == "distinguishedName":
@@ -1826,7 +2314,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                     self.report("ERROR: Not fixing num_values(%d) for '%s' on '%s'" %
                                 (len(obj[attrname]), attrname, str(obj.dn)))
                 else:
-                    name_val = obj[attrname][0]
+                    name_val = str(obj[attrname][0])
 
             if str(attrname).lower() == str(obj.dn.get_rdn_name()).lower():
                 object_rdn_attr = attrname
@@ -1835,25 +2323,18 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                     self.report("ERROR: Not fixing num_values(%d) for '%s' on '%s'" %
                                 (len(obj[attrname]), attrname, str(obj.dn)))
                 else:
-                    object_rdn_val = obj[attrname][0]
-
-            if str(attrname).lower() == 'isdeleted':
-                if obj[attrname][0] != "FALSE":
-                    isDeleted = True
-
-            if str(attrname).lower() == 'systemflags':
-                systemFlags = int(obj[attrname][0])
+                    object_rdn_val = str(obj[attrname][0])
 
             if str(attrname).lower() == 'replpropertymetadata':
-                if self.has_replmetadata_zero_invocationid(dn, obj[attrname]):
+                if self.has_replmetadata_zero_invocationid(dn, obj[attrname][0]):
                     error_count += 1
-                    self.err_replmetadata_zero_invocationid(dn, attrname, obj[attrname])
+                    self.err_replmetadata_zero_invocationid(dn, attrname, obj[attrname][0])
                     # We don't continue, as we may also have other fixes for this attribute
                     # based on what other attributes we see.
 
                 try:
                     (set_attrs_from_md, list_attid_from_md, wrong_attids) \
-                        = self.process_metadata(dn, obj[attrname])
+                        = self.process_metadata(dn, obj[attrname][0])
                 except KeyError:
                     error_count += 1
                     self.err_replmetadata_unknown_attid(dn, attrname, obj[attrname])
@@ -1862,18 +2343,17 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 if len(set_attrs_from_md) < len(list_attid_from_md) \
                    or len(wrong_attids) > 0 \
                    or sorted(list_attid_from_md) != list_attid_from_md:
-                    error_count +=1
-                    self.err_replmetadata_incorrect_attid(dn, attrname, obj[attrname], wrong_attids)
+                    error_count += 1
+                    self.err_replmetadata_incorrect_attid(dn, attrname, obj[attrname][0], wrong_attids)
 
                 else:
                     # Here we check that the first attid is 0
                     # (objectClass).
                     if list_attid_from_md[0] != 0:
                         error_count += 1
-                        self.report("ERROR: Not fixing incorrect inital attributeID in '%s' on '%s', it should be objectClass" %
+                        self.report("ERROR: Not fixing incorrect initial attributeID in '%s' on '%s', it should be objectClass" %
                                     (attrname, str(dn)))
 
-                got_repl_property_meta_data = True
                 continue
 
             if str(attrname).lower() == 'ntsecuritydescriptor':
@@ -1895,7 +2375,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                         continue
 
                     current_sd = ndr_unpack(security.descriptor,
-                                            str(obj[attrname][0]))
+                                            obj[attrname][0])
 
                     diff = get_diff_sds(well_known_sd, current_sd, security.dom_sid(self.samdb.get_domain_sid()))
                     if diff != "":
@@ -1924,22 +2404,23 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 continue
 
             if str(attrname).lower() == 'userparameters':
-                if len(obj[attrname][0]) == 1 and obj[attrname][0][0] == '\x20':
+                if len(obj[attrname][0]) == 1 and obj[attrname][0][0] == b'\x20'[0]:
                     error_count += 1
                     self.err_short_userParameters(obj, attrname, obj[attrname])
                     continue
 
-                elif obj[attrname][0][:16] == '\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00':
+                elif obj[attrname][0][:16] == b'\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00\x20\x00':
                     # This is the correct, normal prefix
                     continue
 
-                elif obj[attrname][0][:20] == 'IAAgACAAIAAgACAAIAAg':
+                elif obj[attrname][0][:20] == b'IAAgACAAIAAgACAAIAAg':
                     # this is the typical prefix from a windows migration
                     error_count += 1
                     self.err_base64_userParameters(obj, attrname, obj[attrname])
                     continue
 
-                elif obj[attrname][0][1] != '\x00' and obj[attrname][0][3] != '\x00' and obj[attrname][0][5] != '\x00' and obj[attrname][0][7] != '\x00' and obj[attrname][0][9] != '\x00':
+                #43:00:00:00:74:00:00:00:78
+                elif obj[attrname][0][1] != b'\x00'[0] and obj[attrname][0][3] != b'\x00'[0] and obj[attrname][0][5] != b'\x00'[0] and obj[attrname][0][7] != b'\x00'[0] and obj[attrname][0][9] != b'\x00'[0]:
                     # This is a prefix that is not in UTF-16 format for the space or munged dialback prefix
                     error_count += 1
                     self.err_utf8_userParameters(obj, attrname, obj[attrname])
@@ -1948,10 +2429,10 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 elif len(obj[attrname][0]) % 2 != 0:
                     # This is a value that isn't even in length
                     error_count += 1
-                    self.err_odd_userParameters(obj, attrname, obj[attrname])
+                    self.err_odd_userParameters(obj, attrname)
                     continue
 
-                elif obj[attrname][0][1] == '\x00' and obj[attrname][0][2] == '\x00' and obj[attrname][0][3] == '\x00' and obj[attrname][0][4] != '\x00' and obj[attrname][0][5] == '\x00':
+                elif obj[attrname][0][1] == b'\x00'[0] and obj[attrname][0][2] == b'\x00'[0] and obj[attrname][0][3] == b'\x00'[0] and obj[attrname][0][4] != b'\x00'[0] and obj[attrname][0][5] == b'\x00'[0]:
                     # This is a prefix that would happen if a SAMR-written value was replicated from a Samba 4.1 server to a working server
                     error_count += 1
                     self.err_doubled_userParameters(obj, attrname, obj[attrname])
@@ -1967,7 +2448,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
             # check for empty attributes
             for val in obj[attrname]:
-                if val == '':
+                if val == b'':
                     self.err_empty_attribute(dn, attrname)
                     error_count += 1
                     continue
@@ -1976,7 +2457,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             # special handling for some specific attribute types
             try:
                 syntax_oid = self.samdb_schema.get_syntax_oid_from_lDAPDisplayName(attrname)
-            except Exception, msg:
+            except Exception as msg:
                 self.err_unknown_attribute(obj, attrname)
                 error_count += 1
                 continue
@@ -1989,8 +2470,8 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 and not linkID):
                 set_attrs_seen.add(str(attrname).lower())
 
-            if syntax_oid in [ dsdb.DSDB_SYNTAX_BINARY_DN, dsdb.DSDB_SYNTAX_OR_NAME,
-                               dsdb.DSDB_SYNTAX_STRING_DN, ldb.SYNTAX_DN ]:
+            if syntax_oid in [dsdb.DSDB_SYNTAX_BINARY_DN, dsdb.DSDB_SYNTAX_OR_NAME,
+                              dsdb.DSDB_SYNTAX_STRING_DN, ldb.SYNTAX_DN]:
                 # it's some form of DN, do specialised checking on those
                 error_count += self.check_dn(obj, attrname, syntax_oid)
             else:
@@ -1998,7 +2479,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 values = set()
                 # check for incorrectly normalised attributes
                 for val in obj[attrname]:
-                    values.add(str(val))
+                    values.add(val)
 
                     normalised = self.samdb.dsdb_normalise_attributes(self.samdb_schema, attrname, [val])
                     if len(normalised) != 1 or normalised[0] != val:
@@ -2013,7 +2494,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
             if str(attrname).lower() == "instancetype":
                 calculated_instancetype = self.calculate_instancetype(dn)
-                if len(obj["instanceType"]) != 1 or obj["instanceType"][0] != str(calculated_instancetype):
+                if len(obj["instanceType"]) != 1 or int(obj["instanceType"][0]) != calculated_instancetype:
                     error_count += 1
                     self.err_wrong_instancetype(obj, calculated_instancetype)
 
@@ -2031,9 +2512,11 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
         if name_val is not None:
             parent_dn = None
+            controls = ["show_recycled:1", "relax:0"]
             if isDeleted:
                 if not (systemFlags & samba.dsdb.SYSTEM_FLAG_DISALLOW_MOVE_ON_DELETE):
                     parent_dn = deleted_objects_dn
+                controls += ["local_oid:%s:1" % dsdb.DSDB_CONTROL_DBCHECK_FIX_LINK_DN_NAME]
             if parent_dn is None:
                 parent_dn = obj.dn.parent()
             expected_dn = ldb.Dn(self.samdb, "RDN=RDN,%s" % (parent_dn))
@@ -2044,19 +2527,20 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
             if expected_dn != obj.dn:
                 error_count += 1
-                self.err_wrong_dn(obj, expected_dn, object_rdn_attr, object_rdn_val, name_val)
+                self.err_wrong_dn(obj, expected_dn, object_rdn_attr,
+                        object_rdn_val, name_val, controls)
             elif obj.dn.get_rdn_value() != object_rdn_val:
                 error_count += 1
                 self.report("ERROR: Not fixing %s=%r on '%s'" % (object_rdn_attr, object_rdn_val, str(obj.dn)))
 
         show_dn = True
-        if got_repl_property_meta_data:
+        if repl_meta_data_val:
             if obj.dn == deleted_objects_dn:
                 isDeletedAttId = 131120
                 # It's 29/12/9999 at 23:59:59 UTC as specified in MS-ADTS 7.1.1.4.2 Deleted Objects Container
 
                 expectedTimeDo = 2650466015990000000
-                originating = self.get_originating_time(obj["replPropertyMetaData"], isDeletedAttId)
+                originating = self.get_originating_time(repl_meta_data_val, isDeletedAttId)
                 if originating != expectedTimeDo:
                     if self.confirm_all("Fix isDeleted originating_change_time on '%s'" % str(dn), 'fix_time_metadata'):
                         nmsg = ldb.Message()
@@ -2088,10 +2572,16 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
             if dn != self.samdb.get_root_basedn() and str(dn.parent()) not in self.dn_set:
                 res = self.samdb.search(base=dn.parent(), scope=ldb.SCOPE_BASE,
                                         controls=["show_recycled:1", "show_deleted:1"])
-        except ldb.LdbError, (enum, estr):
+        except ldb.LdbError as e11:
+            (enum, estr) = e11.args
             if enum == ldb.ERR_NO_SUCH_OBJECT:
-                self.err_missing_parent(obj)
-                error_count += 1
+                if isDeleted:
+                    self.report("WARNING: parent object not found for %s" % (obj.dn))
+                    self.report("Not moving to LostAndFound "
+                                "(tombstone garbage collection in progress?)")
+                else:
+                    self.err_missing_parent(obj)
+                    error_count += 1
             else:
                 raise
 
@@ -2114,7 +2604,7 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
                 found = False
                 for loc in msg[location]:
-                    if loc == self.samdb.get_dsServiceName():
+                    if str(loc) == self.samdb.get_dsServiceName():
                         found = True
                 if not found:
                     # This DC is not in the replica locations
@@ -2149,11 +2639,9 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
 
                             self.samdb.transaction_commit()
 
-
                     elif not self.samdb.am_rodc():
                         self.report("No RID Set found for this server: %s, and we are not the RID Master (so can not self-allocate)" % dn)
 
-
         # Check some details of our own RID Set
         if dn == self.rid_set_dn:
             res = self.samdb.search(base=self.rid_set_dn, scope=ldb.SCOPE_BASE,
@@ -2192,7 +2680,8 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                     try:
                         res = self.samdb.search(base="<SID=%s>" % sid, scope=ldb.SCOPE_BASE,
                                                 attrs=[])
-                    except ldb.LdbError, (enum, estr):
+                    except ldb.LdbError as e:
+                        (enum, estr) = e.args
                         if enum != ldb.ERR_NO_SUCH_OBJECT:
                             raise
                         res = None
@@ -2228,7 +2717,6 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                     else:
                         next_free_rid += 1
 
-
         return error_count
 
     ################################################################
@@ -2246,16 +2734,16 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
         error_count = 0
 
         # check that the dsServiceName is in GUID form
-        if not 'dsServiceName' in obj:
+        if 'dsServiceName' not in obj:
             self.report('ERROR: dsServiceName missing in @ROOTDSE')
-            return error_count+1
+            return error_count + 1
 
-        if not obj['dsServiceName'][0].startswith('<GUID='):
+        if not str(obj['dsServiceName'][0]).startswith('<GUID='):
             self.report('ERROR: dsServiceName not in GUID form in @ROOTDSE')
             error_count += 1
             if not self.confirm('Change dsServiceName to GUID form?'):
                 return error_count
-            res = self.samdb.search(base=ldb.Dn(self.samdb, obj['dsServiceName'][0]),
+            res = self.samdb.search(base=ldb.Dn(self.samdb, obj['dsServiceName'][0].decode('utf8')),
                                     scope=ldb.SCOPE_BASE, attrs=['objectGUID'])
             guid_str = str(ndr_unpack(misc.GUID, res[0]['objectGUID'][0]))
             m = ldb.Message()
@@ -2266,9 +2754,9 @@ newSuperior: %s""" % (str(from_dn), str(to_rdn), str(to_base)))
                 self.report("Changed dsServiceName to GUID form")
         return error_count
 
-
     ###############################################
     # re-index the database
+
     def reindex_database(self):
         '''re-index the whole database'''
         m = ldb.Message()