python/samba/kcc/__init__.py

   1 # define the KCC object
   2 #
   3 # Copyright (C) Dave Craft 2011
   4 # Copyright (C) Andrew Bartlett 2015
   5 #
   6 # Andrew Bartlett's alleged work performed by his underlings Douglas
   7 # Bagnall and Garming Sam.
   8 #
   9 # This program is free software; you can redistribute it and/or modify
  10 # it under the terms of the GNU General Public License as published by
  11 # the Free Software Foundation; either version 3 of the License, or
  12 # (at your option) any later version.
  13 #
  14 # This program is distributed in the hope that it will be useful,
  15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 # GNU General Public License for more details.
  18 #
  19 # You should have received a copy of the GNU General Public License
  20 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 import random
  23 import uuid
  24
  25 import itertools
  26 from samba import unix2nttime, nttime2unix
  27 from samba import ldb, dsdb, drs_utils
  28 from samba.auth import system_session
  29 from samba.samdb import SamDB
  30 from samba.dcerpc import drsuapi, misc
  31
  32 from samba.kcc.kcc_utils import Site, Partition, Transport, SiteLink
  33 from samba.kcc.kcc_utils import NCReplica, NCType, nctype_lut, GraphNode
  34 from samba.kcc.kcc_utils import RepsFromTo, KCCError, KCCFailedObject
  35 from samba.kcc.graph import convert_schedule_to_repltimes
  36
  37 from samba.ndr import ndr_pack
  38
  39 from samba.kcc.graph_utils import verify_and_dot
  40
  41 from samba.kcc import ldif_import_export
  42 from samba.kcc.graph import setup_graph, get_spanning_tree_edges
  43 from samba.kcc.graph import Vertex
  44
  45 from samba.kcc.debug import DEBUG, DEBUG_FN, logger
  46 from samba.kcc import debug
  47
  48
  49 def sort_replica_by_dsa_guid(rep1, rep2):
  50     """Helper to sort NCReplicas by their DSA guids
  51
  52     The guids need to be sorted in their NDR form.
  53
  54     :param rep1: An NC replica
  55     :param rep2: Another replica
  56     :return: -1, 0, or 1, indicating sort order.
  57     """
  58     return cmp(ndr_pack(rep1.rep_dsa_guid), ndr_pack(rep2.rep_dsa_guid))
  59
  60
  61 def sort_dsa_by_gc_and_guid(dsa1, dsa2):
  62     """Helper to sort DSAs by guid global catalog status
  63
  64     GC DSAs come before non-GC DSAs, other than that, the guids are
  65     sorted in NDR form.
  66
  67     :param dsa1: A DSA object
  68     :param dsa2: Another DSA
  69     :return: -1, 0, or 1, indicating sort order.
  70     """
  71     if dsa1.is_gc() and not dsa2.is_gc():
  72         return -1
  73     if not dsa1.is_gc() and dsa2.is_gc():
  74         return +1
  75     return cmp(ndr_pack(dsa1.dsa_guid), ndr_pack(dsa2.dsa_guid))
  76
  77
  78 def is_smtp_replication_available():
  79     """Can the KCC use SMTP replication?
  80
  81     Currently always returns false because Samba doesn't implement
  82     SMTP transfer for NC changes between DCs.
  83
  84     :return: Boolean (always False)
  85     """
  86     return False
  87
  88
  89 class KCC(object):
  90     """The Knowledge Consistency Checker class.
  91
  92     A container for objects and methods allowing a run of the KCC.  Produces a
  93     set of connections in the samdb for which the Distributed Replication
  94     Service can then utilize to replicate naming contexts
  95
  96     :param unix_now: The putative current time in seconds since 1970.
  97     :param readonly: Don't write to the database.
  98     :param verify: Check topological invariants for the generated graphs
  99     :param debug: Write verbosely to stderr.
 100     :param dot_file_dir: write diagnostic Graphviz files in this directory
 101     """
 102     def __init__(self, unix_now, readonly=False, verify=False, debug=False,
 103                  dot_file_dir=None):
 104         """Initializes the partitions class which can hold
 105         our local DCs partitions or all the partitions in
 106         the forest
 107         """
 108         self.part_table = {}    # partition objects
 109         self.site_table = {}
 110         self.ip_transport = None
 111         self.sitelink_table = {}
 112         self.dsa_by_dnstr = {}
 113         self.dsa_by_guid = {}
 114
 115         self.get_dsa_by_guidstr = self.dsa_by_guid.get
 116         self.get_dsa = self.dsa_by_dnstr.get
 117
 118         # TODO: These should be backed by a 'permanent' store so that when
 119         # calling DRSGetReplInfo with DS_REPL_INFO_KCC_DSA_CONNECT_FAILURES,
 120         # the failure information can be returned
 121         self.kcc_failed_links = {}
 122         self.kcc_failed_connections = set()
 123
 124         # Used in inter-site topology computation.  A list
 125         # of connections (by NTDSConnection object) that are
 126         # to be kept when pruning un-needed NTDS Connections
 127         self.kept_connections = set()
 128
 129         self.my_dsa_dnstr = None  # My dsa DN
 130         self.my_dsa = None  # My dsa object
 131
 132         self.my_site_dnstr = None
 133         self.my_site = None
 134
 135         self.samdb = None
 136
 137         self.unix_now = unix_now
 138         self.nt_now = unix2nttime(unix_now)
 139         self.readonly = readonly
 140         self.verify = verify
 141         self.debug = debug
 142         self.dot_file_dir = dot_file_dir
 143
 144     def load_ip_transport(self):
 145         """Loads the inter-site transport objects for Sites
 146
 147         :return: None
 148         :raise KCCError: if no IP transport is found
 149         """
 150         try:
 151             res = self.samdb.search("CN=Inter-Site Transports,CN=Sites,%s" %
 152                                     self.samdb.get_config_basedn(),
 153                                     scope=ldb.SCOPE_SUBTREE,
 154                                     expression="(objectClass=interSiteTransport)")
 155         except ldb.LdbError, (enum, estr):
 156             raise KCCError("Unable to find inter-site transports - (%s)" %
 157                            estr)
 158
 159         for msg in res:
 160             dnstr = str(msg.dn)
 161
 162             transport = Transport(dnstr)
 163
 164             transport.load_transport(self.samdb)
 165             if transport.name == 'IP':
 166                 self.ip_transport = transport
 167             elif transport.name == 'SMTP':
 168                 logger.debug("Samba KCC is ignoring the obsolete "
 169                              "SMTP transport.")
 170
 171             else:
 172                 logger.warning("Samba KCC does not support the transport "
 173                                "called %r." % (transport.name,))
 174
 175         if self.ip_transport is None:
 176             raise KCCError("there doesn't seem to be an IP transport")
 177
 178     def load_all_sitelinks(self):
 179         """Loads the inter-site siteLink objects
 180
 181         :return: None
 182         :raise KCCError: if site-links aren't found
 183         """
 184         try:
 185             res = self.samdb.search("CN=Inter-Site Transports,CN=Sites,%s" %
 186                                     self.samdb.get_config_basedn(),
 187                                     scope=ldb.SCOPE_SUBTREE,
 188                                     expression="(objectClass=siteLink)")
 189         except ldb.LdbError, (enum, estr):
 190             raise KCCError("Unable to find inter-site siteLinks - (%s)" % estr)
 191
 192         for msg in res:
 193             dnstr = str(msg.dn)
 194
 195             # already loaded
 196             if dnstr in self.sitelink_table:
 197                 continue
 198
 199             sitelink = SiteLink(dnstr)
 200
 201             sitelink.load_sitelink(self.samdb)
 202
 203             # Assign this siteLink to table
 204             # and index by dn
 205             self.sitelink_table[dnstr] = sitelink
 206
 207     def load_site(self, dn_str):
 208         """Helper for load_my_site and load_all_sites.
 209
 210         Put all the site's DSAs into the KCC indices.
 211
 212         :param dn_str: a site dn_str
 213         :return: the Site object pertaining to the dn_str
 214         """
 215         site = Site(dn_str, self.unix_now)
 216         site.load_site(self.samdb)
 217
 218         # We avoid replacing the site with an identical copy in case
 219         # somewhere else has a reference to the old one, which would
 220         # lead to all manner of confusion and chaos.
 221         guid = str(site.site_guid)
 222         if guid not in self.site_table:
 223             self.site_table[guid] = site
 224             self.dsa_by_dnstr.update(site.dsa_table)
 225             self.dsa_by_guid.update((str(x.dsa_guid), x)
 226                                     for x in site.dsa_table.values())
 227
 228         return self.site_table[guid]
 229
 230     def load_my_site(self):
 231         """Load the Site object for the local DSA.
 232
 233         :return: None
 234         """
 235         self.my_site_dnstr = ("CN=%s,CN=Sites,%s" % (
 236             self.samdb.server_site_name(),
 237             self.samdb.get_config_basedn()))
 238
 239         self.my_site = self.load_site(self.my_site_dnstr)
 240
 241     def load_all_sites(self):
 242         """Discover all sites and create Site objects.
 243
 244         :return: None
 245         :raise: KCCError if sites can't be found
 246         """
 247         try:
 248             res = self.samdb.search("CN=Sites,%s" %
 249                                     self.samdb.get_config_basedn(),
 250                                     scope=ldb.SCOPE_SUBTREE,
 251                                     expression="(objectClass=site)")
 252         except ldb.LdbError, (enum, estr):
 253             raise KCCError("Unable to find sites - (%s)" % estr)
 254
 255         for msg in res:
 256             sitestr = str(msg.dn)
 257             self.load_site(sitestr)
 258
 259     def load_my_dsa(self):
 260         """Discover my nTDSDSA dn thru the rootDSE entry
 261
 262         :return: None
 263         :raise: KCCError if DSA can't be found
 264         """
 265         dn_query = "<GUID=%s>" % self.samdb.get_ntds_GUID()
 266         dn = ldb.Dn(self.samdb, dn_query)
 267         try:
 268             res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE,
 269                                     attrs=["objectGUID"])
 270         except ldb.LdbError, (enum, estr):
 271             DEBUG_FN("Search for dn '%s' [from %s] failed: %s. "
 272                      "This typically happens in --importldif mode due "
 273                      "to lack of module support." % (dn, dn_query, estr))
 274             try:
 275                 # We work around the failure above by looking at the
 276                 # dsServiceName that was put in the fake rootdse by
 277                 # the --exportldif, rather than the
 278                 # samdb.get_ntds_GUID(). The disadvantage is that this
 279                 # mode requires we modify the @ROOTDSE dnq to support
 280                 # --forced-local-dsa
 281                 service_name_res = self.samdb.search(base="",
 282                                                      scope=ldb.SCOPE_BASE,
 283                                                      attrs=["dsServiceName"])
 284                 dn = ldb.Dn(self.samdb,
 285                             service_name_res[0]["dsServiceName"][0])
 286
 287                 res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE,
 288                                         attrs=["objectGUID"])
 289             except ldb.LdbError, (enum, estr):
 290                 raise KCCError("Unable to find my nTDSDSA - (%s)" % estr)
 291
 292         if len(res) != 1:
 293             raise KCCError("Unable to find my nTDSDSA at %s" %
 294                            dn.extended_str())
 295
 296         ntds_guid = misc.GUID(self.samdb.get_ntds_GUID())
 297         if misc.GUID(res[0]["objectGUID"][0]) != ntds_guid:
 298             raise KCCError("Did not find the GUID we expected,"
 299                            " perhaps due to --importldif")
 300
 301         self.my_dsa_dnstr = str(res[0].dn)
 302
 303         self.my_dsa = self.my_site.get_dsa(self.my_dsa_dnstr)
 304
 305         if self.my_dsa_dnstr not in self.dsa_by_dnstr:
 306             debug.DEBUG_DARK_YELLOW("my_dsa %s isn't in self.dsas_by_dnstr:"
 307                                     " it must be RODC.\n"
 308                                     "Let's add it, because my_dsa is special!"
 309                                     "\n(likewise for self.dsa_by_guid)" %
 310                                     self.my_dsa_dnstr)
 311
 312             self.dsa_by_dnstr[self.my_dsa_dnstr] = self.my_dsa
 313             self.dsa_by_guid[str(self.my_dsa.dsa_guid)] = self.my_dsa
 314
 315     def load_all_partitions(self):
 316         """Discover and load all partitions.
 317
 318         Each NC is inserted into the part_table by partition
 319         dn string (not the nCName dn string)
 320
 321         :return: None
 322         :raise: KCCError if partitions can't be found
 323         """
 324         try:
 325             res = self.samdb.search("CN=Partitions,%s" %
 326                                     self.samdb.get_config_basedn(),
 327                                     scope=ldb.SCOPE_SUBTREE,
 328                                     expression="(objectClass=crossRef)")
 329         except ldb.LdbError, (enum, estr):
 330             raise KCCError("Unable to find partitions - (%s)" % estr)
 331
 332         for msg in res:
 333             partstr = str(msg.dn)
 334
 335             # already loaded
 336             if partstr in self.part_table:
 337                 continue
 338
 339             part = Partition(partstr)
 340
 341             part.load_partition(self.samdb)
 342             self.part_table[partstr] = part
 343
 344     def refresh_failed_links_connections(self, ping=None):
 345         """Ensure the failed links list is up to date
 346
 347         Based on MS-ADTS 6.2.2.1
 348
 349         :param ping: An oracle function of remote site availability
 350         :return: None
 351         """
 352         # LINKS: Refresh failed links
 353         self.kcc_failed_links = {}
 354         current, needed = self.my_dsa.get_rep_tables()
 355         for replica in current.values():
 356             # For every possible connection to replicate
 357             for reps_from in replica.rep_repsFrom:
 358                 failure_count = reps_from.consecutive_sync_failures
 359                 if failure_count <= 0:
 360                     continue
 361
 362                 dsa_guid = str(reps_from.source_dsa_obj_guid)
 363                 time_first_failure = reps_from.last_success
 364                 last_result = reps_from.last_attempt
 365                 dns_name = reps_from.dns_name1
 366
 367                 f = self.kcc_failed_links.get(dsa_guid)
 368                 if f is None:
 369                     f = KCCFailedObject(dsa_guid, failure_count,
 370                                         time_first_failure, last_result,
 371                                         dns_name)
 372                     self.kcc_failed_links[dsa_guid] = f
 373                 else:
 374                     f.failure_count = max(f.failure_count, failure_count)
 375                     f.time_first_failure = min(f.time_first_failure,
 376                                                time_first_failure)
 377                     f.last_result = last_result
 378
 379         # CONNECTIONS: Refresh failed connections
 380         restore_connections = set()
 381         if ping is not None:
 382             DEBUG("refresh_failed_links: checking if links are still down")
 383             for connection in self.kcc_failed_connections:
 384                 if ping(connection.dns_name):
 385                     # Failed connection is no longer failing
 386                     restore_connections.add(connection)
 387                 else:
 388                     connection.failure_count += 1
 389         else:
 390             DEBUG("refresh_failed_links: not checking live links because we\n"
 391                   "weren't asked to --attempt-live-connections")
 392
 393         # Remove the restored connections from the failed connections
 394         self.kcc_failed_connections.difference_update(restore_connections)
 395
 396     def is_stale_link_connection(self, target_dsa):
 397         """Check whether a link to a remote DSA is stale
 398
 399         Used in MS-ADTS 6.2.2.2 Intrasite Connection Creation
 400
 401         Returns True if the remote seems to have been down for at
 402         least two hours, otherwise False.
 403
 404         :param target_dsa: the remote DSA object
 405         :return: True if link is stale, otherwise False
 406         """
 407         failed_link = self.kcc_failed_links.get(str(target_dsa.dsa_guid))
 408         if failed_link:
 409             # failure_count should be > 0, but check anyways
 410             if failed_link.failure_count > 0:
 411                 unix_first_failure = \
 412                     nttime2unix(failed_link.time_first_failure)
 413                 # TODO guard against future
 414                 if unix_first_failure > self.unix_now:
 415                     logger.error("The last success time attribute for \
 416                                  repsFrom is in the future!")
 417
 418                 # Perform calculation in seconds
 419                 if (self.unix_now - unix_first_failure) > 60 * 60 * 2:
 420                     return True
 421
 422         # TODO connections.
 423         # We have checked failed *links*, but we also need to check
 424         # *connections*
 425
 426         return False
 427
 428     # TODO: This should be backed by some form of local database
 429     def remove_unneeded_failed_links_connections(self):
 430         # Remove all tuples in kcc_failed_links where failure count = 0
 431         # In this implementation, this should never happen.
 432
 433         # Remove all connections which were not used this run or connections
 434         # that became active during this run.
 435         pass
 436
 437     def _ensure_connections_are_loaded(self, connections):
 438         """Load or fake-load NTDSConnections lacking GUIDs
 439
 440         New connections don't have GUIDs and created times which are
 441         needed for sorting. If we're in read-only mode, we make fake
 442         GUIDs, otherwise we ask SamDB to do it for us.
 443
 444         :param connections: an iterable of NTDSConnection objects.
 445         :return: None
 446         """
 447         for cn_conn in connections:
 448             if cn_conn.guid is None:
 449                 if self.readonly:
 450                     cn_conn.guid = misc.GUID(str(uuid.uuid4()))
 451                     cn_conn.whenCreated = self.nt_now
 452                 else:
 453                     cn_conn.load_connection(self.samdb)
 454
 455     def _mark_broken_ntdsconn(self):
 456         """Find NTDS Connections that lack a remote
 457
 458         I'm not sure how they appear. Let's be rid of them by marking
 459         them with the to_be_deleted attribute.
 460
 461         :return: None
 462         """
 463         for cn_conn in self.my_dsa.connect_table.values():
 464             s_dnstr = cn_conn.get_from_dnstr()
 465             if s_dnstr is None:
 466                 DEBUG_FN("%s has phantom connection %s" % (self.my_dsa,
 467                                                            cn_conn))
 468                 cn_conn.to_be_deleted = True
 469
 470     def _mark_unneeded_local_ntdsconn(self):
 471         """Find unneeded intrasite NTDS Connections for removal
 472
 473         Based on MS-ADTS 6.2.2.4 Removing Unnecessary Connections.
 474         Every DC removes its own unnecessary intrasite connections.
 475         This function tags them with the to_be_deleted attribute.
 476
 477         :return: None
 478         """
 479         # XXX should an RODC be regarded as same site? It isn't part
 480         # of the intrasite ring.
 481
 482         if self.my_site.is_cleanup_ntdsconn_disabled():
 483             DEBUG_FN("not doing ntdsconn cleanup for site %s, "
 484                      "because it is disabled" % self.my_site)
 485             return
 486
 487         mydsa = self.my_dsa
 488
 489         try:
 490             self._ensure_connections_are_loaded(mydsa.connect_table.values())
 491         except KCCError:
 492             # RODC never actually added any connections to begin with
 493             if mydsa.is_ro():
 494                 return
 495
 496         local_connections = []
 497
 498         for cn_conn in mydsa.connect_table.values():
 499             s_dnstr = cn_conn.get_from_dnstr()
 500             if s_dnstr in self.my_site.dsa_table:
 501                 removable = not (cn_conn.is_generated() or
 502                                  cn_conn.is_rodc_topology())
 503                 packed_guid = ndr_pack(cn_conn.guid)
 504                 local_connections.append((cn_conn, s_dnstr,
 505                                           packed_guid, removable))
 506
 507         for a, b in itertools.permutations(local_connections, 2):
 508             cn_conn, s_dnstr, packed_guid, removable = a
 509             cn_conn2, s_dnstr2, packed_guid2, removable2 = b
 510             if (removable and
 511                 s_dnstr == s_dnstr2 and
 512                 cn_conn.whenCreated < cn_conn2.whenCreated or
 513                 (cn_conn.whenCreated == cn_conn2.whenCreated and
 514                  packed_guid < packed_guid2)):
 515                 cn_conn.to_be_deleted = True
 516
 517     def _mark_unneeded_intersite_ntdsconn(self):
 518         """find unneeded intersite NTDS Connections for removal
 519
 520         Based on MS-ADTS 6.2.2.4 Removing Unnecessary Connections. The
 521         intersite topology generator removes links for all DCs in its
 522         site. Here we just tag them with the to_be_deleted attribute.
 523
 524         :return: None
 525         """
 526         # TODO Figure out how best to handle the RODC case
 527         # The RODC is ISTG, but shouldn't act on anyone's behalf.
 528         if self.my_dsa.is_ro():
 529             return
 530
 531         # Find the intersite connections
 532         local_dsas = self.my_site.dsa_table
 533         connections_and_dsas = []
 534         for dsa in local_dsas.values():
 535             for cn in dsa.connect_table.values():
 536                 if cn.to_be_deleted:
 537                     continue
 538                 s_dnstr = cn.get_from_dnstr()
 539                 if s_dnstr is None:
 540                     continue
 541                 if s_dnstr not in local_dsas:
 542                     from_dsa = self.get_dsa(s_dnstr)
 543                     # Samba ONLY: ISTG removes connections to dead DCs
 544                     if from_dsa is None or '\\0ADEL' in s_dnstr:
 545                         logger.info("DSA appears deleted, removing connection %s"
 546                                     % s_dnstr)
 547                         cn.to_be_deleted = True
 548                         continue
 549                     connections_and_dsas.append((cn, dsa, from_dsa))
 550
 551         self._ensure_connections_are_loaded(x[0] for x in connections_and_dsas)
 552         for cn, to_dsa, from_dsa in connections_and_dsas:
 553             if not cn.is_generated() or cn.is_rodc_topology():
 554                 continue
 555
 556             # If the connection is in the kept_connections list, we
 557             # only remove it if an endpoint seems down.
 558             if (cn in self.kept_connections and
 559                 not (self.is_bridgehead_failed(to_dsa, True) or
 560                      self.is_bridgehead_failed(from_dsa, True))):
 561                 continue
 562
 563             # this one is broken and might be superseded by another.
 564             # But which other? Let's just say another link to the same
 565             # site can supersede.
 566             from_dnstr = from_dsa.dsa_dnstr
 567             for site in self.site_table.values():
 568                 if from_dnstr in site.rw_dsa_table:
 569                     for cn2, to_dsa2, from_dsa2 in connections_and_dsas:
 570                         if (cn is not cn2 and
 571                             from_dsa2 in site.rw_dsa_table):
 572                             cn.to_be_deleted = True
 573
 574     def _commit_changes(self, dsa):
 575         if dsa.is_ro() or self.readonly:
 576             for connect in dsa.connect_table.values():
 577                 if connect.to_be_deleted:
 578                     logger.info("TO BE DELETED:\n%s" % connect)
 579                 if connect.to_be_added:
 580                     logger.info("TO BE ADDED:\n%s" % connect)
 581                 if connect.to_be_modified:
 582                     logger.info("TO BE MODIFIED:\n%s" % connect)
 583
 584             # Peform deletion from our tables but perform
 585             # no database modification
 586             dsa.commit_connections(self.samdb, ro=True)
 587         else:
 588             # Commit any modified connections
 589             dsa.commit_connections(self.samdb)
 590
 591     def remove_unneeded_ntdsconn(self, all_connected):
 592         """Remove unneeded NTDS Connections once topology is calculated
 593
 594         Based on MS-ADTS 6.2.2.4 Removing Unnecessary Connections
 595
 596         :param all_connected: indicates whether all sites are connected
 597         :return: None
 598         """
 599         self._mark_broken_ntdsconn()
 600         self._mark_unneeded_local_ntdsconn()
 601         # if we are not the istg, we're done!
 602         # if we are the istg, but all_connected is False, we also do nothing.
 603         if self.my_dsa.is_istg() and all_connected:
 604             self._mark_unneeded_intersite_ntdsconn()
 605
 606         for dsa in self.my_site.dsa_table.values():
 607             self._commit_changes(dsa)
 608
 609     def modify_repsFrom(self, n_rep, t_repsFrom, s_rep, s_dsa, cn_conn):
 610         """Update an repsFrom object if required.
 611
 612         Part of MS-ADTS 6.2.2.5.
 613
 614         Update t_repsFrom if necessary to satisfy requirements. Such
 615         updates are typically required when the IDL_DRSGetNCChanges
 616         server has moved from one site to another--for example, to
 617         enable compression when the server is moved from the
 618         client's site to another site.
 619
 620         The repsFrom.update_flags bit field may be modified
 621         auto-magically if any changes are made here. See
 622         kcc_utils.RepsFromTo for gory details.
 623
 624
 625         :param n_rep: NC replica we need
 626         :param t_repsFrom: repsFrom tuple to modify
 627         :param s_rep: NC replica at source DSA
 628         :param s_dsa: source DSA
 629         :param cn_conn: Local DSA NTDSConnection child
 630
 631         :return: None
 632         """
 633         s_dnstr = s_dsa.dsa_dnstr
 634         same_site = s_dnstr in self.my_site.dsa_table
 635
 636         # if schedule doesn't match then update and modify
 637         times = convert_schedule_to_repltimes(cn_conn.schedule)
 638         if times != t_repsFrom.schedule:
 639             t_repsFrom.schedule = times
 640
 641         # Bit DRS_ADD_REF is set in replicaFlags unconditionally
 642         # Samba ONLY:
 643         if ((t_repsFrom.replica_flags &
 644              drsuapi.DRSUAPI_DRS_ADD_REF) == 0x0):
 645             t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_ADD_REF
 646
 647         # Bit DRS_PER_SYNC is set in replicaFlags if and only
 648         # if nTDSConnection schedule has a value v that specifies
 649         # scheduled replication is to be performed at least once
 650         # per week.
 651         if cn_conn.is_schedule_minimum_once_per_week():
 652
 653             if ((t_repsFrom.replica_flags &
 654                  drsuapi.DRSUAPI_DRS_PER_SYNC) == 0x0):
 655                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_PER_SYNC
 656
 657         # Bit DRS_INIT_SYNC is set in t.replicaFlags if and only
 658         # if the source DSA and the local DC's nTDSDSA object are
 659         # in the same site or source dsa is the FSMO role owner
 660         # of one or more FSMO roles in the NC replica.
 661         if same_site or n_rep.is_fsmo_role_owner(s_dnstr):
 662
 663             if ((t_repsFrom.replica_flags &
 664                  drsuapi.DRSUAPI_DRS_INIT_SYNC) == 0x0):
 665                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_INIT_SYNC
 666
 667         # If bit NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT is set in
 668         # cn!options, bit DRS_NEVER_NOTIFY is set in t.replicaFlags
 669         # if and only if bit NTDSCONN_OPT_USE_NOTIFY is clear in
 670         # cn!options. Otherwise, bit DRS_NEVER_NOTIFY is set in
 671         # t.replicaFlags if and only if s and the local DC's
 672         # nTDSDSA object are in different sites.
 673         if ((cn_conn.options &
 674              dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT) != 0x0):
 675
 676             if (cn_conn.options & dsdb.NTDSCONN_OPT_USE_NOTIFY) == 0x0:
 677                 # WARNING
 678                 #
 679                 # it LOOKS as if this next test is a bit silly: it
 680                 # checks the flag then sets it if it not set; the same
 681                 # effect could be achieved by unconditionally setting
 682                 # it. But in fact the repsFrom object has special
 683                 # magic attached to it, and altering replica_flags has
 684                 # side-effects. That is bad in my opinion, but there
 685                 # you go.
 686                 if ((t_repsFrom.replica_flags &
 687                      drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0):
 688                     t_repsFrom.replica_flags |= \
 689                         drsuapi.DRSUAPI_DRS_NEVER_NOTIFY
 690
 691         elif not same_site:
 692
 693             if ((t_repsFrom.replica_flags &
 694                  drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0):
 695                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_NEVER_NOTIFY
 696
 697         # Bit DRS_USE_COMPRESSION is set in t.replicaFlags if
 698         # and only if s and the local DC's nTDSDSA object are
 699         # not in the same site and the
 700         # NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION bit is
 701         # clear in cn!options
 702         if (not same_site and
 703             (cn_conn.options &
 704              dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION) == 0x0):
 705
 706             if ((t_repsFrom.replica_flags &
 707                  drsuapi.DRSUAPI_DRS_USE_COMPRESSION) == 0x0):
 708                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_USE_COMPRESSION
 709
 710         # Bit DRS_TWOWAY_SYNC is set in t.replicaFlags if and only
 711         # if bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options.
 712         if (cn_conn.options & dsdb.NTDSCONN_OPT_TWOWAY_SYNC) != 0x0:
 713
 714             if ((t_repsFrom.replica_flags &
 715                  drsuapi.DRSUAPI_DRS_TWOWAY_SYNC) == 0x0):
 716                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_TWOWAY_SYNC
 717
 718         # Bits DRS_DISABLE_AUTO_SYNC and DRS_DISABLE_PERIODIC_SYNC are
 719         # set in t.replicaFlags if and only if cn!enabledConnection = false.
 720         if not cn_conn.is_enabled():
 721
 722             if ((t_repsFrom.replica_flags &
 723                  drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC) == 0x0):
 724                 t_repsFrom.replica_flags |= \
 725                     drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC
 726
 727             if ((t_repsFrom.replica_flags &
 728                  drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC) == 0x0):
 729                 t_repsFrom.replica_flags |= \
 730                     drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC
 731
 732         # If s and the local DC's nTDSDSA object are in the same site,
 733         # cn!transportType has no value, or the RDN of cn!transportType
 734         # is CN=IP:
 735         #
 736         #     Bit DRS_MAIL_REP in t.replicaFlags is clear.
 737         #
 738         #     t.uuidTransport = NULL GUID.
 739         #
 740         #     t.uuidDsa = The GUID-based DNS name of s.
 741         #
 742         # Otherwise:
 743         #
 744         #     Bit DRS_MAIL_REP in t.replicaFlags is set.
 745         #
 746         #     If x is the object with dsname cn!transportType,
 747         #     t.uuidTransport = x!objectGUID.
 748         #
 749         #     Let a be the attribute identified by
 750         #     x!transportAddressAttribute. If a is
 751         #     the dNSHostName attribute, t.uuidDsa = the GUID-based
 752         #      DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
 753         #
 754         # It appears that the first statement i.e.
 755         #
 756         #     "If s and the local DC's nTDSDSA object are in the same
 757         #      site, cn!transportType has no value, or the RDN of
 758         #      cn!transportType is CN=IP:"
 759         #
 760         # could be a slightly tighter statement if it had an "or"
 761         # between each condition.  I believe this should
 762         # be interpreted as:
 763         #
 764         #     IF (same-site) OR (no-value) OR (type-ip)
 765         #
 766         # because IP should be the primary transport mechanism
 767         # (even in inter-site) and the absense of the transportType
 768         # attribute should always imply IP no matter if its multi-site
 769         #
 770         # NOTE MS-TECH INCORRECT:
 771         #
 772         #     All indications point to these statements above being
 773         #     incorrectly stated:
 774         #
 775         #         t.uuidDsa = The GUID-based DNS name of s.
 776         #
 777         #         Let a be the attribute identified by
 778         #         x!transportAddressAttribute. If a is
 779         #         the dNSHostName attribute, t.uuidDsa = the GUID-based
 780         #         DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
 781         #
 782         #     because the uuidDSA is a GUID and not a GUID-base DNS
 783         #     name.  Nor can uuidDsa hold (s!parent)!a if not
 784         #     dNSHostName.  What should have been said is:
 785         #
 786         #         t.naDsa = The GUID-based DNS name of s
 787         #
 788         #     That would also be correct if transportAddressAttribute
 789         #     were "mailAddress" because (naDsa) can also correctly
 790         #     hold the SMTP ISM service address.
 791         #
 792         nastr = "%s._msdcs.%s" % (s_dsa.dsa_guid, self.samdb.forest_dns_name())
 793
 794         if ((t_repsFrom.replica_flags &
 795              drsuapi.DRSUAPI_DRS_MAIL_REP) != 0x0):
 796             t_repsFrom.replica_flags &= ~drsuapi.DRSUAPI_DRS_MAIL_REP
 797
 798         t_repsFrom.transport_guid = misc.GUID()
 799
 800         # See (NOTE MS-TECH INCORRECT) above
 801
 802         # NOTE: it looks like these conditionals are pointless,
 803         # because the state will end up as `t_repsFrom.dns_name1 ==
 804         # nastr` in either case, BUT the repsFrom thing is magic and
 805         # assigning to it alters some flags. So we try not to update
 806         # it unless necessary.
 807         if t_repsFrom.dns_name1 != nastr:
 808             t_repsFrom.dns_name1 = nastr
 809
 810         if t_repsFrom.version > 0x1 and t_repsFrom.dns_name2 != nastr:
 811             t_repsFrom.dns_name2 = nastr
 812
 813         if t_repsFrom.is_modified():
 814             DEBUG_FN("modify_repsFrom(): %s" % t_repsFrom)
 815
 816     def get_dsa_for_implied_replica(self, n_rep, cn_conn):
 817         """If a connection imply a replica, find the relevant DSA
 818
 819         Given a NC replica and NTDS Connection, determine if the
 820         connection implies a repsFrom tuple should be present from the
 821         source DSA listed in the connection to the naming context. If
 822         it should be, return the DSA; otherwise return None.
 823
 824         Based on part of MS-ADTS 6.2.2.5
 825
 826         :param n_rep: NC replica
 827         :param cn_conn: NTDS Connection
 828         :return: source DSA or None
 829         """
 830         # XXX different conditions for "implies" than MS-ADTS 6.2.2
 831         # preamble.
 832
 833         # It boils down to: we want an enabled, non-FRS connections to
 834         # a valid remote DSA with a non-RO replica corresponding to
 835         # n_rep.
 836
 837         if not cn_conn.is_enabled() or cn_conn.is_rodc_topology():
 838             return None
 839
 840         s_dnstr = cn_conn.get_from_dnstr()
 841         s_dsa = self.get_dsa(s_dnstr)
 842
 843         # No DSA matching this source DN string?
 844         if s_dsa is None:
 845             return None
 846
 847         s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
 848
 849         if (s_rep is not None and
 850             s_rep.is_present() and
 851             (not s_rep.is_ro() or n_rep.is_partial())):
 852             return s_dsa
 853         return None
 854
 855     def translate_ntdsconn(self, current_dsa=None):
 856         """Adjust repsFrom to match NTDSConnections
 857
 858         This function adjusts values of repsFrom abstract attributes of NC
 859         replicas on the local DC to match those implied by
 860         nTDSConnection objects.
 861
 862         Based on [MS-ADTS] 6.2.2.5
 863
 864         :param current_dsa: optional DSA on whose behalf we are acting.
 865         :return: None
 866         """
 867         count = 0
 868
 869         ro = False
 870         if current_dsa is None:
 871             current_dsa = self.my_dsa
 872
 873         if current_dsa.is_ro():
 874             ro = True
 875
 876         if current_dsa.is_translate_ntdsconn_disabled():
 877             DEBUG_FN("skipping translate_ntdsconn() "
 878                      "because disabling flag is set")
 879             return
 880
 881         DEBUG_FN("translate_ntdsconn(): enter")
 882
 883         current_rep_table, needed_rep_table = current_dsa.get_rep_tables()
 884
 885         # Filled in with replicas we currently have that need deleting
 886         delete_reps = set()
 887
 888         # We're using the MS notation names here to allow
 889         # correlation back to the published algorithm.
 890         #
 891         # n_rep      - NC replica (n)
 892         # t_repsFrom - tuple (t) in n!repsFrom
 893         # s_dsa      - Source DSA of the replica. Defined as nTDSDSA
 894         #              object (s) such that (s!objectGUID = t.uuidDsa)
 895         #              In our IDL representation of repsFrom the (uuidDsa)
 896         #              attribute is called (source_dsa_obj_guid)
 897         # cn_conn    - (cn) is nTDSConnection object and child of the local
 898         #               DC's nTDSDSA object and (cn!fromServer = s)
 899         # s_rep      - source DSA replica of n
 900         #
 901         # If we have the replica and its not needed
 902         # then we add it to the "to be deleted" list.
 903         for dnstr in current_rep_table:
 904             # If we're on the RODC, hardcode the update flags
 905             if ro:
 906                 c_rep = current_rep_table[dnstr]
 907                 c_rep.load_repsFrom(self.samdb)
 908                 for t_repsFrom in c_rep.rep_repsFrom:
 909                     replica_flags = (drsuapi.DRSUAPI_DRS_INIT_SYNC |
 910                                      drsuapi.DRSUAPI_DRS_PER_SYNC |
 911                                      drsuapi.DRSUAPI_DRS_ADD_REF |
 912                                      drsuapi.DRSUAPI_DRS_SPECIAL_SECRET_PROCESSING |
 913                                      drsuapi.DRSUAPI_DRS_NONGC_RO_REP)
 914                     if t_repsFrom.replica_flags != replica_flags:
 915                         t_repsFrom.replica_flags = replica_flags
 916                 c_rep.commit_repsFrom(self.samdb, ro=self.readonly)
 917             else:
 918                 if dnstr not in needed_rep_table:
 919                     delete_reps.add(dnstr)
 920
 921         DEBUG_FN('current %d needed %d delete %d' % (len(current_rep_table),
 922                  len(needed_rep_table), len(delete_reps)))
 923
 924         if delete_reps:
 925             # TODO Must delete repsFrom/repsTo for these replicas
 926             DEBUG('deleting these reps: %s' % delete_reps)
 927             for dnstr in delete_reps:
 928                 del current_rep_table[dnstr]
 929
 930         # HANDLE REPS-FROM
 931         #
 932         # Now perform the scan of replicas we'll need
 933         # and compare any current repsFrom against the
 934         # connections
 935         for n_rep in needed_rep_table.values():
 936
 937             # load any repsFrom and fsmo roles as we'll
 938             # need them during connection translation
 939             n_rep.load_repsFrom(self.samdb)
 940             n_rep.load_fsmo_roles(self.samdb)
 941
 942             # Loop thru the existing repsFrom tuples (if any)
 943             # XXX This is a list and could contain duplicates
 944             #     (multiple load_repsFrom calls)
 945             for t_repsFrom in n_rep.rep_repsFrom:
 946
 947                 # for each tuple t in n!repsFrom, let s be the nTDSDSA
 948                 # object such that s!objectGUID = t.uuidDsa
 949                 guidstr = str(t_repsFrom.source_dsa_obj_guid)
 950                 s_dsa = self.get_dsa_by_guidstr(guidstr)
 951
 952                 # Source dsa is gone from config (strange)
 953                 # so cleanup stale repsFrom for unlisted DSA
 954                 if s_dsa is None:
 955                     logger.warning("repsFrom source DSA guid (%s) not found" %
 956                                    guidstr)
 957                     t_repsFrom.to_be_deleted = True
 958                     continue
 959
 960                 # Find the connection that this repsFrom would use. If
 961                 # there isn't a good one (i.e. non-RODC_TOPOLOGY,
 962                 # meaning non-FRS), we delete the repsFrom.
 963                 s_dnstr = s_dsa.dsa_dnstr
 964                 connections = current_dsa.get_connection_by_from_dnstr(s_dnstr)
 965                 for cn_conn in connections:
 966                     if not cn_conn.is_rodc_topology():
 967                         break
 968                 else:
 969                     # no break means no non-rodc_topology connection exists
 970                     t_repsFrom.to_be_deleted = True
 971                     continue
 972
 973                 # KCC removes this repsFrom tuple if any of the following
 974                 # is true:
 975                 #     No NC replica of the NC "is present" on DSA that
 976                 #     would be source of replica
 977                 #
 978                 #     A writable replica of the NC "should be present" on
 979                 #     the local DC, but a partial replica "is present" on
 980                 #     the source DSA
 981                 s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
 982
 983                 if s_rep is None or not s_rep.is_present() or \
 984                    (not n_rep.is_ro() and s_rep.is_partial()):
 985
 986                     t_repsFrom.to_be_deleted = True
 987                     continue
 988
 989                 # If the KCC did not remove t from n!repsFrom, it updates t
 990                 self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)
 991
 992             # Loop thru connections and add implied repsFrom tuples
 993             # for each NTDSConnection under our local DSA if the
 994             # repsFrom is not already present
 995             for cn_conn in current_dsa.connect_table.values():
 996
 997                 s_dsa = self.get_dsa_for_implied_replica(n_rep, cn_conn)
 998                 if s_dsa is None:
 999                     continue
1000
1001                 # Loop thru the existing repsFrom tuples (if any) and
1002                 # if we already have a tuple for this connection then
1003                 # no need to proceed to add.  It will have been changed
1004                 # to have the correct attributes above
1005                 for t_repsFrom in n_rep.rep_repsFrom:
1006                     guidstr = str(t_repsFrom.source_dsa_obj_guid)
1007                     if s_dsa is self.get_dsa_by_guidstr(guidstr):
1008                         s_dsa = None
1009                         break
1010
1011                 if s_dsa is None:
1012                     continue
1013
1014                 # Create a new RepsFromTo and proceed to modify
1015                 # it according to specification
1016                 t_repsFrom = RepsFromTo(n_rep.nc_dnstr)
1017
1018                 t_repsFrom.source_dsa_obj_guid = s_dsa.dsa_guid
1019
1020                 s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
1021
1022                 self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)
1023
1024                 # Add to our NC repsFrom as this is newly computed
1025                 if t_repsFrom.is_modified():
1026                     n_rep.rep_repsFrom.append(t_repsFrom)
1027
1028             if self.readonly or ro:
1029                 # Display any to be deleted or modified repsFrom
1030                 text = n_rep.dumpstr_to_be_deleted()
1031                 if text:
1032                     logger.info("TO BE DELETED:\n%s" % text)
1033                 text = n_rep.dumpstr_to_be_modified()
1034                 if text:
1035                     logger.info("TO BE MODIFIED:\n%s" % text)
1036
1037                 # Peform deletion from our tables but perform
1038                 # no database modification
1039                 n_rep.commit_repsFrom(self.samdb, ro=True)
1040             else:
1041                 # Commit any modified repsFrom to the NC replica
1042                 n_rep.commit_repsFrom(self.samdb)
1043
1044         # HANDLE REPS-TO:
1045         #
1046         # Now perform the scan of replicas we'll need
1047         # and compare any current repsTo against the
1048         # connections
1049
1050         # RODC should never push to anybody (should we check this?)
1051         if ro:
1052             return
1053
1054         for n_rep in needed_rep_table.values():
1055
1056             # load any repsTo and fsmo roles as we'll
1057             # need them during connection translation
1058             n_rep.load_repsTo(self.samdb)
1059
1060             # Loop thru the existing repsTo tuples (if any)
1061             # XXX This is a list and could contain duplicates
1062             #     (multiple load_repsTo calls)
1063             for t_repsTo in n_rep.rep_repsTo:
1064
1065                 # for each tuple t in n!repsTo, let s be the nTDSDSA
1066                 # object such that s!objectGUID = t.uuidDsa
1067                 guidstr = str(t_repsTo.source_dsa_obj_guid)
1068                 s_dsa = self.get_dsa_by_guidstr(guidstr)
1069
1070                 # Source dsa is gone from config (strange)
1071                 # so cleanup stale repsTo for unlisted DSA
1072                 if s_dsa is None:
1073                     logger.warning("repsTo source DSA guid (%s) not found" %
1074                                    guidstr)
1075                     t_repsTo.to_be_deleted = True
1076                     continue
1077
1078                 # Find the connection that this repsTo would use. If
1079                 # there isn't a good one (i.e. non-RODC_TOPOLOGY,
1080                 # meaning non-FRS), we delete the repsTo.
1081                 s_dnstr = s_dsa.dsa_dnstr
1082                 if '\\0ADEL' in s_dnstr:
1083                     logger.warning("repsTo source DSA guid (%s) appears deleted" %
1084                                    guidstr)
1085                     t_repsTo.to_be_deleted = True
1086                     continue
1087
1088                 connections = s_dsa.get_connection_by_from_dnstr(self.my_dsa_dnstr)
1089                 if len(connections) > 0:
1090                     # Then this repsTo is tentatively valid
1091                     continue
1092                 else:
1093                     # There is no plausible connection for this repsTo
1094                     t_repsTo.to_be_deleted = True
1095
1096             if self.readonly:
1097                 # Display any to be deleted or modified repsTo
1098                 for rt in n_rep.rep_repsTo:
1099                     if rt.to_be_deleted:
1100                         logger.info("REMOVING REPS-TO: %s" % rt)
1101
1102                 # Peform deletion from our tables but perform
1103                 # no database modification
1104                 n_rep.commit_repsTo(self.samdb, ro=True)
1105             else:
1106                 # Commit any modified repsTo to the NC replica
1107                 n_rep.commit_repsTo(self.samdb)
1108
1109         # TODO Remove any duplicate repsTo values. This should never happen in
1110         # any normal situations.
1111
1112     def merge_failed_links(self, ping=None):
1113         """Merge of kCCFailedLinks and kCCFailedLinks from bridgeheads.
1114
1115         The KCC on a writable DC attempts to merge the link and connection
1116         failure information from bridgehead DCs in its own site to help it
1117         identify failed bridgehead DCs.
1118
1119         Based on MS-ADTS 6.2.2.3.2 "Merge of kCCFailedLinks and kCCFailedLinks
1120         from Bridgeheads"
1121
1122         :param ping: An oracle of current bridgehead availability
1123         :return: None
1124         """
1125         # 1. Queries every bridgehead server in your site (other than yourself)
1126         # 2. For every ntDSConnection that references a server in a different
1127         #    site merge all the failure info
1128         #
1129         # XXX - not implemented yet
1130         if ping is not None:
1131             debug.DEBUG_RED("merge_failed_links() is NOT IMPLEMENTED")
1132         else:
1133             DEBUG_FN("skipping merge_failed_links() because it requires "
1134                      "real network connections\n"
1135                      "and we weren't asked to --attempt-live-connections")
1136
1137     def setup_graph(self, part):
1138         """Set up an intersite graph
1139
1140         An intersite graph has a Vertex for each site object, a
1141         MultiEdge for each SiteLink object, and a MutliEdgeSet for
1142         each siteLinkBridge object (or implied siteLinkBridge). It
1143         reflects the intersite topology in a slightly more abstract
1144         graph form.
1145
1146         Roughly corresponds to MS-ADTS 6.2.2.3.4.3
1147
1148         :param part: a Partition object
1149         :returns: an InterSiteGraph object
1150         """
1151         # If 'Bridge all site links' is enabled and Win2k3 bridges required
1152         # is not set
1153         # NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
1154         # No documentation for this however, ntdsapi.h appears to have:
1155         # NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED = 0x00001000
1156         bridges_required = self.my_site.site_options & 0x00001002 != 0
1157         transport_guid = str(self.ip_transport.guid)
1158
1159         g = setup_graph(part, self.site_table, transport_guid,
1160                         self.sitelink_table, bridges_required)
1161
1162         if self.verify or self.dot_file_dir is not None:
1163             dot_edges = []
1164             for edge in g.edges:
1165                 for a, b in itertools.combinations(edge.vertices, 2):
1166                     dot_edges.append((a.site.site_dnstr, b.site.site_dnstr))
1167             verify_properties = ()
1168             name = 'site_edges_%s' % part.partstr
1169             verify_and_dot(name, dot_edges, directed=False,
1170                            label=self.my_dsa_dnstr,
1171                            properties=verify_properties, debug=DEBUG,
1172                            verify=self.verify,
1173                            dot_file_dir=self.dot_file_dir)
1174
1175         return g
1176
1177     def get_bridgehead(self, site, part, transport, partial_ok, detect_failed):
1178         """Get a bridghead DC for a site.
1179
1180         Part of MS-ADTS 6.2.2.3.4.4
1181
1182         :param site: site object representing for which a bridgehead
1183             DC is desired.
1184         :param part: crossRef for NC to replicate.
1185         :param transport: interSiteTransport object for replication
1186             traffic.
1187         :param partial_ok: True if a DC containing a partial
1188             replica or a full replica will suffice, False if only
1189             a full replica will suffice.
1190         :param detect_failed: True to detect failed DCs and route
1191             replication traffic around them, False to assume no DC
1192             has failed.
1193         :return: dsa object for the bridgehead DC or None
1194         """
1195
1196         bhs = self.get_all_bridgeheads(site, part, transport,
1197                                        partial_ok, detect_failed)
1198         if not bhs:
1199             debug.DEBUG_MAGENTA("get_bridgehead FAILED:\nsitedn = %s" %
1200                                 site.site_dnstr)
1201             return None
1202
1203         debug.DEBUG_GREEN("get_bridgehead:\n\tsitedn = %s\n\tbhdn = %s" %
1204                           (site.site_dnstr, bhs[0].dsa_dnstr))
1205         return bhs[0]
1206
1207     def get_all_bridgeheads(self, site, part, transport,
1208                             partial_ok, detect_failed):
1209         """Get all bridghead DCs on a site satisfying the given criteria
1210
1211         Part of MS-ADTS 6.2.2.3.4.4
1212
1213         :param site: site object representing the site for which
1214             bridgehead DCs are desired.
1215         :param part: partition for NC to replicate.
1216         :param transport: interSiteTransport object for
1217             replication traffic.
1218         :param partial_ok: True if a DC containing a partial
1219             replica or a full replica will suffice, False if
1220             only a full replica will suffice.
1221         :param detect_failed: True to detect failed DCs and route
1222             replication traffic around them, FALSE to assume
1223             no DC has failed.
1224         :return: list of dsa object for available bridgehead DCs
1225         """
1226         bhs = []
1227
1228         if transport.name != "IP":
1229             raise KCCError("get_all_bridgeheads has run into a "
1230                            "non-IP transport! %r"
1231                            % (transport.name,))
1232
1233         DEBUG_FN(site.rw_dsa_table)
1234         for dsa in site.rw_dsa_table.values():
1235
1236             pdnstr = dsa.get_parent_dnstr()
1237
1238             # IF t!bridgeheadServerListBL has one or more values and
1239             # t!bridgeheadServerListBL does not contain a reference
1240             # to the parent object of dc then skip dc
1241             if ((len(transport.bridgehead_list) != 0 and
1242                  pdnstr not in transport.bridgehead_list)):
1243                 continue
1244
1245             # IF dc is in the same site as the local DC
1246             #    IF a replica of cr!nCName is not in the set of NC replicas
1247             #    that "should be present" on dc or a partial replica of the
1248             #    NC "should be present" but partialReplicasOkay = FALSE
1249             #        Skip dc
1250             if self.my_site.same_site(dsa):
1251                 needed, ro, partial = part.should_be_present(dsa)
1252                 if not needed or (partial and not partial_ok):
1253                     continue
1254                 rep = dsa.get_current_replica(part.nc_dnstr)
1255
1256             # ELSE
1257             #     IF an NC replica of cr!nCName is not in the set of NC
1258             #     replicas that "are present" on dc or a partial replica of
1259             #     the NC "is present" but partialReplicasOkay = FALSE
1260             #          Skip dc
1261             else:
1262                 rep = dsa.get_current_replica(part.nc_dnstr)
1263                 if rep is None or (rep.is_partial() and not partial_ok):
1264                     continue
1265
1266             # IF AmIRODC() and cr!nCName corresponds to default NC then
1267             #     Let dsaobj be the nTDSDSA object of the dc
1268             #     IF  dsaobj.msDS-Behavior-Version < DS_DOMAIN_FUNCTION_2008
1269             #         Skip dc
1270             if self.my_dsa.is_ro() and rep is not None and rep.is_default():
1271                 if not dsa.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
1272                     continue
1273
1274             # IF BridgeheadDCFailed(dc!objectGUID, detectFailedDCs) = TRUE
1275             #     Skip dc
1276             if self.is_bridgehead_failed(dsa, detect_failed):
1277                 DEBUG("bridgehead is failed")
1278                 continue
1279
1280             DEBUG_FN("found a bridgehead: %s" % dsa.dsa_dnstr)
1281             bhs.append(dsa)
1282
1283         # IF bit NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED is set in
1284         # s!options
1285         #    SORT bhs such that all GC servers precede DCs that are not GC
1286         #    servers, and otherwise by ascending objectGUID
1287         # ELSE
1288         #    SORT bhs in a random order
1289         if site.is_random_bridgehead_disabled():
1290             bhs.sort(sort_dsa_by_gc_and_guid)
1291         else:
1292             random.shuffle(bhs)
1293         debug.DEBUG_YELLOW(bhs)
1294         return bhs
1295
1296     def is_bridgehead_failed(self, dsa, detect_failed):
1297         """Determine whether a given DC is known to be in a failed state
1298
1299         :param dsa: the bridgehead to test
1300         :param detect_failed: True to really check, False to assume no failure
1301         :return: True if and only if the DC should be considered failed
1302
1303         Here we DEPART from the pseudo code spec which appears to be
1304         wrong. It says, in full:
1305
1306     /***** BridgeheadDCFailed *****/
1307     /* Determine whether a given DC is known to be in a failed state.
1308      * IN: objectGUID - objectGUID of the DC's nTDSDSA object.
1309      * IN: detectFailedDCs - TRUE if and only failed DC detection is
1310      *     enabled.
1311      * RETURNS: TRUE if and only if the DC should be considered to be in a
1312      *          failed state.
1313      */
1314     BridgeheadDCFailed(IN GUID objectGUID, IN bool detectFailedDCs) : bool
1315     {
1316         IF bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set in
1317         the options attribute of the site settings object for the local
1318         DC's site
1319             RETURN FALSE
1320         ELSEIF a tuple z exists in the kCCFailedLinks or
1321         kCCFailedConnections variables such that z.UUIDDsa =
1322         objectGUID, z.FailureCount > 1, and the current time -
1323         z.TimeFirstFailure > 2 hours
1324             RETURN TRUE
1325         ELSE
1326             RETURN detectFailedDCs
1327         ENDIF
1328     }
1329
1330         where you will see detectFailedDCs is not behaving as
1331         advertised -- it is acting as a default return code in the
1332         event that a failure is not detected, not a switch turning
1333         detection on or off. Elsewhere the documentation seems to
1334         concur with the comment rather than the code.
1335         """
1336         if not detect_failed:
1337             return False
1338
1339         # NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED = 0x00000008
1340         # When DETECT_STALE_DISABLED, we can never know of if
1341         # it's in a failed state
1342         if self.my_site.site_options & 0x00000008:
1343             return False
1344
1345         return self.is_stale_link_connection(dsa)
1346
1347     def create_connection(self, part, rbh, rsite, transport,
1348                           lbh, lsite, link_opt, link_sched,
1349                           partial_ok, detect_failed):
1350         """Create an nTDSConnection object as specified if it doesn't exist.
1351
1352         Part of MS-ADTS 6.2.2.3.4.5
1353
1354         :param part: crossRef object for the NC to replicate.
1355         :param rbh: nTDSDSA object for DC to act as the
1356             IDL_DRSGetNCChanges server (which is in a site other
1357             than the local DC's site).
1358         :param rsite: site of the rbh
1359         :param transport: interSiteTransport object for the transport
1360             to use for replication traffic.
1361         :param lbh: nTDSDSA object for DC to act as the
1362             IDL_DRSGetNCChanges client (which is in the local DC's site).
1363         :param lsite: site of the lbh
1364         :param link_opt: Replication parameters (aggregated siteLink options,
1365                                                  etc.)
1366         :param link_sched: Schedule specifying the times at which
1367             to begin replicating.
1368         :partial_ok: True if bridgehead DCs containing partial
1369             replicas of the NC are acceptable.
1370         :param detect_failed: True to detect failed DCs and route
1371             replication traffic around them, FALSE to assume no DC
1372             has failed.
1373         """
1374         rbhs_all = self.get_all_bridgeheads(rsite, part, transport,
1375                                             partial_ok, False)
1376         rbh_table = dict((x.dsa_dnstr, x) for x in rbhs_all)
1377
1378         debug.DEBUG_GREY("rbhs_all: %s %s" % (len(rbhs_all),
1379                                               [x.dsa_dnstr for x in rbhs_all]))
1380
1381         # MS-TECH says to compute rbhs_avail but then doesn't use it
1382         # rbhs_avail = self.get_all_bridgeheads(rsite, part, transport,
1383         #                                        partial_ok, detect_failed)
1384
1385         lbhs_all = self.get_all_bridgeheads(lsite, part, transport,
1386                                             partial_ok, False)
1387         if lbh.is_ro():
1388             lbhs_all.append(lbh)
1389
1390         debug.DEBUG_GREY("lbhs_all: %s %s" % (len(lbhs_all),
1391                                               [x.dsa_dnstr for x in lbhs_all]))
1392
1393         # MS-TECH says to compute lbhs_avail but then doesn't use it
1394         # lbhs_avail = self.get_all_bridgeheads(lsite, part, transport,
1395         #                                       partial_ok, detect_failed)
1396
1397         # FOR each nTDSConnection object cn such that the parent of cn is
1398         # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1399         for ldsa in lbhs_all:
1400             for cn in ldsa.connect_table.values():
1401
1402                 rdsa = rbh_table.get(cn.from_dnstr)
1403                 if rdsa is None:
1404                     continue
1405
1406                 debug.DEBUG_DARK_YELLOW("rdsa is %s" % rdsa.dsa_dnstr)
1407                 # IF bit NTDSCONN_OPT_IS_GENERATED is set in cn!options and
1408                 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options and
1409                 # cn!transportType references t
1410                 if ((cn.is_generated() and
1411                      not cn.is_rodc_topology() and
1412                      cn.transport_guid == transport.guid)):
1413
1414                     # IF bit NTDSCONN_OPT_USER_OWNED_SCHEDULE is clear in
1415                     # cn!options and cn!schedule != sch
1416                     #     Perform an originating update to set cn!schedule to
1417                     #     sched
1418                     if ((not cn.is_user_owned_schedule() and
1419                          not cn.is_equivalent_schedule(link_sched))):
1420                         cn.schedule = link_sched
1421                         cn.set_modified(True)
1422
1423                     # IF bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1424                     # NTDSCONN_OPT_USE_NOTIFY are set in cn
1425                     if cn.is_override_notify_default() and \
1426                        cn.is_use_notify():
1427
1428                         # IF bit NTDSSITELINK_OPT_USE_NOTIFY is clear in
1429                         # ri.Options
1430                         #    Perform an originating update to clear bits
1431                         #    NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1432                         #    NTDSCONN_OPT_USE_NOTIFY in cn!options
1433                         if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) == 0:
1434                             cn.options &= \
1435                                 ~(dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1436                                   dsdb.NTDSCONN_OPT_USE_NOTIFY)
1437                             cn.set_modified(True)
1438
1439                     # ELSE
1440                     else:
1441
1442                         # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in
1443                         # ri.Options
1444                         #     Perform an originating update to set bits
1445                         #     NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1446                         #     NTDSCONN_OPT_USE_NOTIFY in cn!options
1447                         if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1448                             cn.options |= \
1449                                 (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1450                                  dsdb.NTDSCONN_OPT_USE_NOTIFY)
1451                             cn.set_modified(True)
1452
1453                     # IF bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options
1454                     if cn.is_twoway_sync():
1455
1456                         # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is clear in
1457                         # ri.Options
1458                         #     Perform an originating update to clear bit
1459                         #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1460                         if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) == 0:
1461                             cn.options &= ~dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1462                             cn.set_modified(True)
1463
1464                     # ELSE
1465                     else:
1466
1467                         # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in
1468                         # ri.Options
1469                         #     Perform an originating update to set bit
1470                         #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1471                         if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1472                             cn.options |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1473                             cn.set_modified(True)
1474
1475                     # IF bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION is set
1476                     # in cn!options
1477                     if cn.is_intersite_compression_disabled():
1478
1479                         # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is clear
1480                         # in ri.Options
1481                         #     Perform an originating update to clear bit
1482                         #     NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1483                         #     cn!options
1484                         if ((link_opt &
1485                              dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) == 0):
1486                             cn.options &= \
1487                                 ~dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1488                             cn.set_modified(True)
1489
1490                     # ELSE
1491                     else:
1492                         # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1493                         # ri.Options
1494                         #     Perform an originating update to set bit
1495                         #     NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1496                         #     cn!options
1497                         if ((link_opt &
1498                              dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1499                             cn.options |= \
1500                                 dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1501                             cn.set_modified(True)
1502
1503                     # Display any modified connection
1504                     if self.readonly:
1505                         if cn.to_be_modified:
1506                             logger.info("TO BE MODIFIED:\n%s" % cn)
1507
1508                         ldsa.commit_connections(self.samdb, ro=True)
1509                     else:
1510                         ldsa.commit_connections(self.samdb)
1511         # ENDFOR
1512
1513         valid_connections = 0
1514
1515         # FOR each nTDSConnection object cn such that cn!parent is
1516         # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1517         for ldsa in lbhs_all:
1518             for cn in ldsa.connect_table.values():
1519
1520                 rdsa = rbh_table.get(cn.from_dnstr)
1521                 if rdsa is None:
1522                     continue
1523
1524                 debug.DEBUG_DARK_YELLOW("round 2: rdsa is %s" % rdsa.dsa_dnstr)
1525
1526                 # IF (bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options or
1527                 # cn!transportType references t) and
1528                 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options
1529                 if (((not cn.is_generated() or
1530                       cn.transport_guid == transport.guid) and
1531                      not cn.is_rodc_topology())):
1532
1533                     # LET rguid be the objectGUID of the nTDSDSA object
1534                     # referenced by cn!fromServer
1535                     # LET lguid be (cn!parent)!objectGUID
1536
1537                     # IF BridgeheadDCFailed(rguid, detectFailedDCs) = FALSE and
1538                     # BridgeheadDCFailed(lguid, detectFailedDCs) = FALSE
1539                     #     Increment cValidConnections by 1
1540                     if ((not self.is_bridgehead_failed(rdsa, detect_failed) and
1541                          not self.is_bridgehead_failed(ldsa, detect_failed))):
1542                         valid_connections += 1
1543
1544                     # IF keepConnections does not contain cn!objectGUID
1545                     #     APPEND cn!objectGUID to keepConnections
1546                     self.kept_connections.add(cn)
1547
1548         # ENDFOR
1549         debug.DEBUG_RED("valid connections %d" % valid_connections)
1550         DEBUG("kept_connections:\n%s" % (self.kept_connections,))
1551         # IF cValidConnections = 0
1552         if valid_connections == 0:
1553
1554             # LET opt be NTDSCONN_OPT_IS_GENERATED
1555             opt = dsdb.NTDSCONN_OPT_IS_GENERATED
1556
1557             # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in ri.Options
1558             #     SET bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1559             #     NTDSCONN_OPT_USE_NOTIFY in opt
1560             if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1561                 opt |= (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1562                         dsdb.NTDSCONN_OPT_USE_NOTIFY)
1563
1564             # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in ri.Options
1565             #     SET bit NTDSCONN_OPT_TWOWAY_SYNC opt
1566             if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1567                 opt |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1568
1569             # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1570             # ri.Options
1571             #     SET bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in opt
1572             if ((link_opt &
1573                  dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1574                 opt |= dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1575
1576             # Perform an originating update to create a new nTDSConnection
1577             # object cn that is a child of lbh, cn!enabledConnection = TRUE,
1578             # cn!options = opt, cn!transportType is a reference to t,
1579             # cn!fromServer is a reference to rbh, and cn!schedule = sch
1580             DEBUG_FN("new connection, KCC dsa: %s" % self.my_dsa.dsa_dnstr)
1581             system_flags = (dsdb.SYSTEM_FLAG_CONFIG_ALLOW_RENAME |
1582                             dsdb.SYSTEM_FLAG_CONFIG_ALLOW_MOVE)
1583
1584             cn = lbh.new_connection(opt, system_flags, transport,
1585                                     rbh.dsa_dnstr, link_sched)
1586
1587             # Display any added connection
1588             if self.readonly:
1589                 if cn.to_be_added:
1590                     logger.info("TO BE ADDED:\n%s" % cn)
1591
1592                     lbh.commit_connections(self.samdb, ro=True)
1593             else:
1594                 lbh.commit_connections(self.samdb)
1595
1596             # APPEND cn!objectGUID to keepConnections
1597             self.kept_connections.add(cn)
1598
1599     def add_transports(self, vertex, local_vertex, graph, detect_failed):
1600         """Build a Vertex's transport lists
1601
1602         Each vertex has accept_red_red and accept_black lists that
1603         list what transports they accept under various conditions. The
1604         only transport that is ever accepted is IP, and a dummy extra
1605         transport called "EDGE_TYPE_ALL".
1606
1607         Part of MS-ADTS 6.2.2.3.4.3 -- ColorVertices
1608
1609         :param vertex: the remote vertex we are thinking about
1610         :param local_vertex: the vertex relating to the local site.
1611         :param graph: the intersite graph
1612         :param detect_failed: whether to detect failed links
1613         :return: True if some bridgeheads were not found
1614         """
1615         # The docs ([MS-ADTS] 6.2.2.3.4.3) say to use local_vertex
1616         # here, but using vertex seems to make more sense. That is,
1617         # the docs want this:
1618         #
1619         #bh = self.get_bridgehead(local_vertex.site, vertex.part, transport,
1620         #                         local_vertex.is_black(), detect_failed)
1621         #
1622         # TODO WHY?????
1623
1624         vertex.accept_red_red = []
1625         vertex.accept_black = []
1626         found_failed = False
1627
1628         if vertex in graph.connected_vertices:
1629             t_guid = str(self.ip_transport.guid)
1630
1631             bh = self.get_bridgehead(vertex.site, vertex.part,
1632                                      self.ip_transport,
1633                                      vertex.is_black(), detect_failed)
1634             if bh is None:
1635                 if vertex.site.is_rodc_site():
1636                     vertex.accept_red_red.append(t_guid)
1637                 else:
1638                     found_failed = True
1639             else:
1640                 vertex.accept_red_red.append(t_guid)
1641                 vertex.accept_black.append(t_guid)
1642
1643         # Add additional transport to ensure another run of Dijkstra
1644         vertex.accept_red_red.append("EDGE_TYPE_ALL")
1645         vertex.accept_black.append("EDGE_TYPE_ALL")
1646
1647         return found_failed
1648
1649     def create_connections(self, graph, part, detect_failed):
1650         """Create intersite NTDSConnections as needed by a partition
1651
1652         Construct an NC replica graph for the NC identified by
1653         the given crossRef, then create any additional nTDSConnection
1654         objects required.
1655
1656         :param graph: site graph.
1657         :param part: crossRef object for NC.
1658         :param detect_failed:  True to detect failed DCs and route
1659             replication traffic around them, False to assume no DC
1660             has failed.
1661
1662         Modifies self.kept_connections by adding any connections
1663         deemed to be "in use".
1664
1665         :return: (all_connected, found_failed_dc)
1666         (all_connected) True if the resulting NC replica graph
1667             connects all sites that need to be connected.
1668         (found_failed_dc) True if one or more failed DCs were
1669             detected.
1670         """
1671         all_connected = True
1672         found_failed = False
1673
1674         DEBUG_FN("create_connections(): enter\n"
1675                  "\tpartdn=%s\n\tdetect_failed=%s" %
1676                  (part.nc_dnstr, detect_failed))
1677
1678         # XXX - This is a highly abbreviated function from the MS-TECH
1679         #       ref.  It creates connections between bridgeheads to all
1680         #       sites that have appropriate replicas.  Thus we are not
1681         #       creating a minimum cost spanning tree but instead
1682         #       producing a fully connected tree.  This should produce
1683         #       a full (albeit not optimal cost) replication topology.
1684
1685         my_vertex = Vertex(self.my_site, part)
1686         my_vertex.color_vertex()
1687
1688         for v in graph.vertices:
1689             v.color_vertex()
1690             if self.add_transports(v, my_vertex, graph, detect_failed):
1691                 found_failed = True
1692
1693         # No NC replicas for this NC in the site of the local DC,
1694         # so no nTDSConnection objects need be created
1695         if my_vertex.is_white():
1696             return all_connected, found_failed
1697
1698         edge_list, n_components = get_spanning_tree_edges(graph,
1699                                                           self.my_site,
1700                                                           label=part.partstr)
1701
1702         DEBUG_FN("%s Number of components: %d" %
1703                  (part.nc_dnstr, n_components))
1704         if n_components > 1:
1705             all_connected = False
1706
1707         # LET partialReplicaOkay be TRUE if and only if
1708         # localSiteVertex.Color = COLOR.BLACK
1709         partial_ok = my_vertex.is_black()
1710
1711         # Utilize the IP transport only for now
1712         transport = self.ip_transport
1713
1714         DEBUG("edge_list %s" % edge_list)
1715         for e in edge_list:
1716             # XXX more accurate comparison?
1717             if e.directed and e.vertices[0].site is self.my_site:
1718                 continue
1719
1720             if e.vertices[0].site is self.my_site:
1721                 rsite = e.vertices[1].site
1722             else:
1723                 rsite = e.vertices[0].site
1724
1725             # We don't make connections to our own site as that
1726             # is intrasite topology generator's job
1727             if rsite is self.my_site:
1728                 DEBUG("rsite is my_site")
1729                 continue
1730
1731             # Determine bridgehead server in remote site
1732             rbh = self.get_bridgehead(rsite, part, transport,
1733                                       partial_ok, detect_failed)
1734             if rbh is None:
1735                 continue
1736
1737             # RODC acts as an BH for itself
1738             # IF AmIRODC() then
1739             #     LET lbh be the nTDSDSA object of the local DC
1740             # ELSE
1741             #     LET lbh be the result of GetBridgeheadDC(localSiteVertex.ID,
1742             #     cr, t, partialReplicaOkay, detectFailedDCs)
1743             if self.my_dsa.is_ro():
1744                 lsite = self.my_site
1745                 lbh = self.my_dsa
1746             else:
1747                 lsite = self.my_site
1748                 lbh = self.get_bridgehead(lsite, part, transport,
1749                                           partial_ok, detect_failed)
1750             # TODO
1751             if lbh is None:
1752                 debug.DEBUG_RED("DISASTER! lbh is None")
1753                 return False, True
1754
1755             DEBUG_FN("lsite: %s\nrsite: %s" % (lsite, rsite))
1756             DEBUG_FN("vertices %s" % (e.vertices,))
1757             debug.DEBUG_BLUE("bridgeheads\n%s\n%s\n%s" % (lbh, rbh, "-" * 70))
1758
1759             sitelink = e.site_link
1760             if sitelink is None:
1761                 link_opt = 0x0
1762                 link_sched = None
1763             else:
1764                 link_opt = sitelink.options
1765                 link_sched = sitelink.schedule
1766
1767             self.create_connection(part, rbh, rsite, transport,
1768                                    lbh, lsite, link_opt, link_sched,
1769                                    partial_ok, detect_failed)
1770
1771         return all_connected, found_failed
1772
1773     def create_intersite_connections(self):
1774         """Create NTDSConnections as necessary for all partitions.
1775
1776         Computes an NC replica graph for each NC replica that "should be
1777         present" on the local DC or "is present" on any DC in the same site
1778         as the local DC. For each edge directed to an NC replica on such a
1779         DC from an NC replica on a DC in another site, the KCC creates an
1780         nTDSConnection object to imply that edge if one does not already
1781         exist.
1782
1783         Modifies self.kept_connections - A set of nTDSConnection
1784         objects for edges that are directed
1785         to the local DC's site in one or more NC replica graphs.
1786
1787         :return: True if spanning trees were created for all NC replica
1788                  graphs, otherwise False.
1789         """
1790         all_connected = True
1791         self.kept_connections = set()
1792
1793         # LET crossRefList be the set containing each object o of class
1794         # crossRef such that o is a child of the CN=Partitions child of the
1795         # config NC
1796
1797         # FOR each crossRef object cr in crossRefList
1798         #    IF cr!enabled has a value and is false, or if FLAG_CR_NTDS_NC
1799         #        is clear in cr!systemFlags, skip cr.
1800         #    LET g be the GRAPH return of SetupGraph()
1801
1802         for part in self.part_table.values():
1803
1804             if not part.is_enabled():
1805                 continue
1806
1807             if part.is_foreign():
1808                 continue
1809
1810             graph = self.setup_graph(part)
1811
1812             # Create nTDSConnection objects, routing replication traffic
1813             # around "failed" DCs.
1814             found_failed = False
1815
1816             connected, found_failed = self.create_connections(graph,
1817                                                               part, True)
1818
1819             DEBUG("with detect_failed: connected %s Found failed %s" %
1820                   (connected, found_failed))
1821             if not connected:
1822                 all_connected = False
1823
1824                 if found_failed:
1825                     # One or more failed DCs preclude use of the ideal NC
1826                     # replica graph. Add connections for the ideal graph.
1827                     self.create_connections(graph, part, False)
1828
1829         return all_connected
1830
1831     def intersite(self, ping):
1832         """Generate the inter-site KCC replica graph and nTDSConnections
1833
1834         As per MS-ADTS 6.2.2.3.
1835
1836         If self.readonly is False, the connections are added to self.samdb.
1837
1838         Produces self.kept_connections which is a set of NTDS
1839         Connections that should be kept during subsequent pruning
1840         process.
1841
1842         After this has run, all sites should be connected in a minimum
1843         spanning tree.
1844
1845         :param ping: An oracle function of remote site availability
1846         :return (True or False):  (True) if the produced NC replica
1847             graph connects all sites that need to be connected
1848         """
1849
1850         # Retrieve my DSA
1851         mydsa = self.my_dsa
1852         mysite = self.my_site
1853         all_connected = True
1854
1855         DEBUG_FN("intersite(): enter")
1856
1857         # Determine who is the ISTG
1858         if self.readonly:
1859             mysite.select_istg(self.samdb, mydsa, ro=True)
1860         else:
1861             mysite.select_istg(self.samdb, mydsa, ro=False)
1862
1863         # Test whether local site has topology disabled
1864         if mysite.is_intersite_topology_disabled():
1865             DEBUG_FN("intersite(): exit disabled all_connected=%d" %
1866                      all_connected)
1867             return all_connected
1868
1869         if not mydsa.is_istg():
1870             DEBUG_FN("intersite(): exit not istg all_connected=%d" %
1871                      all_connected)
1872             return all_connected
1873
1874         self.merge_failed_links(ping)
1875
1876         # For each NC with an NC replica that "should be present" on the
1877         # local DC or "is present" on any DC in the same site as the
1878         # local DC, the KCC constructs a site graph--a precursor to an NC
1879         # replica graph. The site connectivity for a site graph is defined
1880         # by objects of class interSiteTransport, siteLink, and
1881         # siteLinkBridge in the config NC.
1882
1883         all_connected = self.create_intersite_connections()
1884
1885         DEBUG_FN("intersite(): exit all_connected=%d" % all_connected)
1886         return all_connected
1887
1888     # This function currently does no actions. The reason being that we cannot
1889     # perform modifies in this way on the RODC.
1890     def update_rodc_connection(self, ro=True):
1891         """Updates the RODC NTFRS connection object.
1892
1893         If the local DSA is not an RODC, this does nothing.
1894         """
1895         if not self.my_dsa.is_ro():
1896             return
1897
1898         # Given an nTDSConnection object cn1, such that cn1.options contains
1899         # NTDSCONN_OPT_RODC_TOPOLOGY, and another nTDSConnection object cn2,
1900         # does not contain NTDSCONN_OPT_RODC_TOPOLOGY, modify cn1 to ensure
1901         # that the following is true:
1902         #
1903         #     cn1.fromServer = cn2.fromServer
1904         #     cn1.schedule = cn2.schedule
1905         #
1906         # If no such cn2 can be found, cn1 is not modified.
1907         # If no such cn1 can be found, nothing is modified by this task.
1908
1909         all_connections = self.my_dsa.connect_table.values()
1910         ro_connections = [x for x in all_connections if x.is_rodc_topology()]
1911         rw_connections = [x for x in all_connections
1912                           if x not in ro_connections]
1913
1914         # XXX here we are dealing with multiple RODC_TOPO connections,
1915         # if they exist. It is not clear whether the spec means that
1916         # or if it ever arises.
1917         if rw_connections and ro_connections:
1918             for con in ro_connections:
1919                 cn2 = rw_connections[0]
1920                 con.from_dnstr = cn2.from_dnstr
1921                 con.schedule = cn2.schedule
1922                 con.to_be_modified = True
1923
1924             self.my_dsa.commit_connections(self.samdb, ro=ro)
1925
1926     def intrasite_max_node_edges(self, node_count):
1927         """Find the maximum number of edges directed to an intrasite node
1928
1929         The KCC does not create more than 50 edges directed to a
1930         single DC. To optimize replication, we compute that each node
1931         should have n+2 total edges directed to it such that (n) is
1932         the smallest non-negative integer satisfying
1933         (node_count <= 2*(n*n) + 6*n + 7)
1934
1935         (If the number of edges is m (i.e. n + 2), that is the same as
1936         2 * m*m - 2 * m + 3). We think in terms of n because that is
1937         the number of extra connections over the double directed ring
1938         that exists by default.
1939
1940         edges  n   nodecount
1941           2    0    7
1942           3    1   15
1943           4    2   27
1944           5    3   43
1945                   ...
1946          50   48 4903
1947
1948         :param node_count: total number of nodes in the replica graph
1949
1950         The intention is that there should be no more than 3 hops
1951         between any two DSAs at a site. With up to 7 nodes the 2 edges
1952         of the ring are enough; any configuration of extra edges with
1953         8 nodes will be enough. It is less clear that the 3 hop
1954         guarantee holds at e.g. 15 nodes in degenerate cases, but
1955         those are quite unlikely given the extra edges are randomly
1956         arranged.
1957
1958         :param node_count: the number of nodes in the site
1959         "return: The desired maximum number of connections
1960         """
1961         n = 0
1962         while True:
1963             if node_count <= (2 * (n * n) + (6 * n) + 7):
1964                 break
1965             n = n + 1
1966         n = n + 2
1967         if n < 50:
1968             return n
1969         return 50
1970
1971     def construct_intrasite_graph(self, site_local, dc_local,
1972                                   nc_x, gc_only, detect_stale):
1973         """Create an intrasite graph using given parameters
1974
1975         This might be called a number of times per site with different
1976         parameters.
1977
1978         Based on [MS-ADTS] 6.2.2.2
1979
1980         :param site_local: site for which we are working
1981         :param dc_local: local DC that potentially needs a replica
1982         :param nc_x:  naming context (x) that we are testing if it
1983                     "should be present" on the local DC
1984         :param gc_only: Boolean - only consider global catalog servers
1985         :param detect_stale: Boolean - check whether links seems down
1986         :return: None
1987         """
1988         # We're using the MS notation names here to allow
1989         # correlation back to the published algorithm.
1990         #
1991         # nc_x     - naming context (x) that we are testing if it
1992         #            "should be present" on the local DC
1993         # f_of_x   - replica (f) found on a DC (s) for NC (x)
1994         # dc_s     - DC where f_of_x replica was found
1995         # dc_local - local DC that potentially needs a replica
1996         #            (f_of_x)
1997         # r_list   - replica list R
1998         # p_of_x   - replica (p) is partial and found on a DC (s)
1999         #            for NC (x)
2000         # l_of_x   - replica (l) is the local replica for NC (x)
2001         #            that should appear on the local DC
2002         # r_len = is length of replica list |R|
2003         #
2004         # If the DSA doesn't need a replica for this
2005         # partition (NC x) then continue
2006         needed, ro, partial = nc_x.should_be_present(dc_local)
2007
2008         debug.DEBUG_YELLOW("construct_intrasite_graph(): enter" +
2009                            "\n\tgc_only=%d" % gc_only +
2010                            "\n\tdetect_stale=%d" % detect_stale +
2011                            "\n\tneeded=%s" % needed +
2012                            "\n\tro=%s" % ro +
2013                            "\n\tpartial=%s" % partial +
2014                            "\n%s" % nc_x)
2015
2016         if not needed:
2017             debug.DEBUG_RED("%s lacks 'should be present' status, "
2018                             "aborting construct_intrasite_graph!" %
2019                             nc_x.nc_dnstr)
2020             return
2021
2022         # Create a NCReplica that matches what the local replica
2023         # should say.  We'll use this below in our r_list
2024         l_of_x = NCReplica(dc_local, nc_x.nc_dnstr)
2025
2026         l_of_x.identify_by_basedn(self.samdb)
2027
2028         l_of_x.rep_partial = partial
2029         l_of_x.rep_ro = ro
2030
2031         # Add this replica that "should be present" to the
2032         # needed replica table for this DSA
2033         dc_local.add_needed_replica(l_of_x)
2034
2035         # Replica list
2036         #
2037         # Let R be a sequence containing each writable replica f of x
2038         # such that f "is present" on a DC s satisfying the following
2039         # criteria:
2040         #
2041         #  * s is a writable DC other than the local DC.
2042         #
2043         #  * s is in the same site as the local DC.
2044         #
2045         #  * If x is a read-only full replica and x is a domain NC,
2046         #    then the DC's functional level is at least
2047         #    DS_BEHAVIOR_WIN2008.
2048         #
2049         #  * Bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set
2050         #    in the options attribute of the site settings object for
2051         #    the local DC's site, or no tuple z exists in the
2052         #    kCCFailedLinks or kCCFailedConnections variables such
2053         #    that z.UUIDDsa is the objectGUID of the nTDSDSA object
2054         #    for s, z.FailureCount > 0, and the current time -
2055         #    z.TimeFirstFailure > 2 hours.
2056
2057         r_list = []
2058
2059         # We'll loop thru all the DSAs looking for
2060         # writeable NC replicas that match the naming
2061         # context dn for (nc_x)
2062         #
2063         for dc_s in self.my_site.dsa_table.values():
2064             # If this partition (nc_x) doesn't appear as a
2065             # replica (f_of_x) on (dc_s) then continue
2066             if not nc_x.nc_dnstr in dc_s.current_rep_table:
2067                 continue
2068
2069             # Pull out the NCReplica (f) of (x) with the dn
2070             # that matches NC (x) we are examining.
2071             f_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2072
2073             # Replica (f) of NC (x) must be writable
2074             if f_of_x.is_ro():
2075                 continue
2076
2077             # Replica (f) of NC (x) must satisfy the
2078             # "is present" criteria for DC (s) that
2079             # it was found on
2080             if not f_of_x.is_present():
2081                 continue
2082
2083             # DC (s) must be a writable DSA other than
2084             # my local DC.  In other words we'd only replicate
2085             # from other writable DC
2086             if dc_s.is_ro() or dc_s is dc_local:
2087                 continue
2088
2089             # Certain replica graphs are produced only
2090             # for global catalogs, so test against
2091             # method input parameter
2092             if gc_only and not dc_s.is_gc():
2093                 continue
2094
2095             # DC (s) must be in the same site as the local DC
2096             # as this is the intra-site algorithm. This is
2097             # handled by virtue of placing DSAs in per
2098             # site objects (see enclosing for() loop)
2099
2100             # If NC (x) is intended to be read-only full replica
2101             # for a domain NC on the target DC then the source
2102             # DC should have functional level at minimum WIN2008
2103             #
2104             # Effectively we're saying that in order to replicate
2105             # to a targeted RODC (which was introduced in Windows 2008)
2106             # then we have to replicate from a DC that is also minimally
2107             # at that level.
2108             #
2109             # You can also see this requirement in the MS special
2110             # considerations for RODC which state that to deploy
2111             # an RODC, at least one writable domain controller in
2112             # the domain must be running Windows Server 2008
2113             if ro and not partial and nc_x.nc_type == NCType.domain:
2114                 if not dc_s.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
2115                     continue
2116
2117             # If we haven't been told to turn off stale connection
2118             # detection and this dsa has a stale connection then
2119             # continue
2120             if detect_stale and self.is_stale_link_connection(dc_s):
2121                 continue
2122
2123             # Replica meets criteria.  Add it to table indexed
2124             # by the GUID of the DC that it appears on
2125             r_list.append(f_of_x)
2126
2127         # If a partial (not full) replica of NC (x) "should be present"
2128         # on the local DC, append to R each partial replica (p of x)
2129         # such that p "is present" on a DC satisfying the same
2130         # criteria defined above for full replica DCs.
2131         #
2132         # XXX This loop and the previous one differ only in whether
2133         # the replica is partial or not. here we only accept partial
2134         # (because we're partial); before we only accepted full. Order
2135         # doen't matter (the list is sorted a few lines down) so these
2136         # loops could easily be merged. Or this could be a helper
2137         # function.
2138
2139         if partial:
2140             # Now we loop thru all the DSAs looking for
2141             # partial NC replicas that match the naming
2142             # context dn for (NC x)
2143             for dc_s in self.my_site.dsa_table.values():
2144
2145                 # If this partition NC (x) doesn't appear as a
2146                 # replica (p) of NC (x) on the dsa DC (s) then
2147                 # continue
2148                 if not nc_x.nc_dnstr in dc_s.current_rep_table:
2149                     continue
2150
2151                 # Pull out the NCReplica with the dn that
2152                 # matches NC (x) we are examining.
2153                 p_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2154
2155                 # Replica (p) of NC (x) must be partial
2156                 if not p_of_x.is_partial():
2157                     continue
2158
2159                 # Replica (p) of NC (x) must satisfy the
2160                 # "is present" criteria for DC (s) that
2161                 # it was found on
2162                 if not p_of_x.is_present():
2163                     continue
2164
2165                 # DC (s) must be a writable DSA other than
2166                 # my DSA.  In other words we'd only replicate
2167                 # from other writable DSA
2168                 if dc_s.is_ro() or dc_s is dc_local:
2169                     continue
2170
2171                 # Certain replica graphs are produced only
2172                 # for global catalogs, so test against
2173                 # method input parameter
2174                 if gc_only and not dc_s.is_gc():
2175                     continue
2176
2177                 # If we haven't been told to turn off stale connection
2178                 # detection and this dsa has a stale connection then
2179                 # continue
2180                 if detect_stale and self.is_stale_link_connection(dc_s):
2181                     continue
2182
2183                 # Replica meets criteria.  Add it to table indexed
2184                 # by the GUID of the DSA that it appears on
2185                 r_list.append(p_of_x)
2186
2187         # Append to R the NC replica that "should be present"
2188         # on the local DC
2189         r_list.append(l_of_x)
2190
2191         r_list.sort(sort_replica_by_dsa_guid)
2192         r_len = len(r_list)
2193
2194         max_node_edges = self.intrasite_max_node_edges(r_len)
2195
2196         # Add a node for each r_list element to the replica graph
2197         graph_list = []
2198         for rep in r_list:
2199             node = GraphNode(rep.rep_dsa_dnstr, max_node_edges)
2200             graph_list.append(node)
2201
2202         # For each r(i) from (0 <= i < |R|-1)
2203         i = 0
2204         while i < (r_len-1):
2205             # Add an edge from r(i) to r(i+1) if r(i) is a full
2206             # replica or r(i+1) is a partial replica
2207             if not r_list[i].is_partial() or r_list[i+1].is_partial():
2208                 graph_list[i+1].add_edge_from(r_list[i].rep_dsa_dnstr)
2209
2210             # Add an edge from r(i+1) to r(i) if r(i+1) is a full
2211             # replica or ri is a partial replica.
2212             if not r_list[i+1].is_partial() or r_list[i].is_partial():
2213                 graph_list[i].add_edge_from(r_list[i+1].rep_dsa_dnstr)
2214             i = i + 1
2215
2216         # Add an edge from r|R|-1 to r0 if r|R|-1 is a full replica
2217         # or r0 is a partial replica.
2218         if not r_list[r_len-1].is_partial() or r_list[0].is_partial():
2219             graph_list[0].add_edge_from(r_list[r_len-1].rep_dsa_dnstr)
2220
2221         # Add an edge from r0 to r|R|-1 if r0 is a full replica or
2222         # r|R|-1 is a partial replica.
2223         if not r_list[0].is_partial() or r_list[r_len-1].is_partial():
2224             graph_list[r_len-1].add_edge_from(r_list[0].rep_dsa_dnstr)
2225
2226         DEBUG("r_list is length %s" % len(r_list))
2227         DEBUG('\n'.join(str((x.rep_dsa_guid, x.rep_dsa_dnstr))
2228                         for x in r_list))
2229
2230         do_dot_files = self.dot_file_dir is not None and self.debug
2231         if self.verify or do_dot_files:
2232             dot_edges = []
2233             dot_vertices = set()
2234             for v1 in graph_list:
2235                 dot_vertices.add(v1.dsa_dnstr)
2236                 for v2 in v1.edge_from:
2237                     dot_edges.append((v2, v1.dsa_dnstr))
2238                     dot_vertices.add(v2)
2239
2240             verify_properties = ('connected',)
2241             verify_and_dot('intrasite_pre_ntdscon', dot_edges, dot_vertices,
2242                            label='%s__%s__%s' % (site_local.site_dnstr,
2243                                                  nctype_lut[nc_x.nc_type],
2244                                                  nc_x.nc_dnstr),
2245                            properties=verify_properties, debug=DEBUG,
2246                            verify=self.verify,
2247                            dot_file_dir=self.dot_file_dir,
2248                            directed=True)
2249
2250             rw_dot_vertices = set(x for x in dot_vertices
2251                                   if not self.get_dsa(x).is_ro())
2252             rw_dot_edges = [(a, b) for a, b in dot_edges if
2253                             a in rw_dot_vertices and b in rw_dot_vertices]
2254             rw_verify_properties = ('connected',
2255                                     'directed_double_ring_or_small')
2256             verify_and_dot('intrasite_rw_pre_ntdscon', rw_dot_edges,
2257                            rw_dot_vertices,
2258                            label='%s__%s__%s' % (site_local.site_dnstr,
2259                                                  nctype_lut[nc_x.nc_type],
2260                                                  nc_x.nc_dnstr),
2261                            properties=rw_verify_properties, debug=DEBUG,
2262                            verify=self.verify,
2263                            dot_file_dir=self.dot_file_dir,
2264                            directed=True)
2265
2266         # For each existing nTDSConnection object implying an edge
2267         # from rj of R to ri such that j != i, an edge from rj to ri
2268         # is not already in the graph, and the total edges directed
2269         # to ri is less than n+2, the KCC adds that edge to the graph.
2270         for vertex in graph_list:
2271             dsa = self.my_site.dsa_table[vertex.dsa_dnstr]
2272             for connect in dsa.connect_table.values():
2273                 remote = connect.from_dnstr
2274                 if remote in self.my_site.dsa_table:
2275                     vertex.add_edge_from(remote)
2276
2277         DEBUG('reps are:  %s' % '   '.join(x.rep_dsa_dnstr for x in r_list))
2278         DEBUG('dsas are:  %s' % '   '.join(x.dsa_dnstr for x in graph_list))
2279
2280         for tnode in graph_list:
2281             # To optimize replication latency in sites with many NC
2282             # replicas, the KCC adds new edges directed to ri to bring
2283             # the total edges to n+2, where the NC replica rk of R
2284             # from which the edge is directed is chosen at random such
2285             # that k != i and an edge from rk to ri is not already in
2286             # the graph.
2287             #
2288             # Note that the KCC tech ref does not give a number for
2289             # the definition of "sites with many NC replicas". At a
2290             # bare minimum to satisfy n+2 edges directed at a node we
2291             # have to have at least three replicas in |R| (i.e. if n
2292             # is zero then at least replicas from two other graph
2293             # nodes may direct edges to us).
2294             if r_len >= 3 and not tnode.has_sufficient_edges():
2295                 candidates = [x for x in graph_list if
2296                               (x is not tnode and
2297                                x.dsa_dnstr not in tnode.edge_from)]
2298
2299                 debug.DEBUG_BLUE("looking for random link for %s. r_len %d, "
2300                                  "graph len %d candidates %d"
2301                                  % (tnode.dsa_dnstr, r_len, len(graph_list),
2302                                     len(candidates)))
2303
2304                 DEBUG("candidates %s" % [x.dsa_dnstr for x in candidates])
2305
2306                 while candidates and not tnode.has_sufficient_edges():
2307                     other = random.choice(candidates)
2308                     DEBUG("trying to add candidate %s" % other.dsa_dnstr)
2309                     if not tnode.add_edge_from(other.dsa_dnstr):
2310                         debug.DEBUG_RED("could not add %s" % other.dsa_dnstr)
2311                     candidates.remove(other)
2312             else:
2313                 DEBUG_FN("not adding links to %s: nodes %s, links is %s/%s" %
2314                          (tnode.dsa_dnstr, r_len, len(tnode.edge_from),
2315                           tnode.max_edges))
2316
2317             # Print the graph node in debug mode
2318             DEBUG_FN("%s" % tnode)
2319
2320             # For each edge directed to the local DC, ensure a nTDSConnection
2321             # points to us that satisfies the KCC criteria
2322
2323             if tnode.dsa_dnstr == dc_local.dsa_dnstr:
2324                 tnode.add_connections_from_edges(dc_local, self.ip_transport)
2325
2326         if self.verify or do_dot_files:
2327             dot_edges = []
2328             dot_vertices = set()
2329             for v1 in graph_list:
2330                 dot_vertices.add(v1.dsa_dnstr)
2331                 for v2 in v1.edge_from:
2332                     dot_edges.append((v2, v1.dsa_dnstr))
2333                     dot_vertices.add(v2)
2334
2335             verify_properties = ('connected',)
2336             verify_and_dot('intrasite_post_ntdscon', dot_edges, dot_vertices,
2337                            label='%s__%s__%s' % (site_local.site_dnstr,
2338                                                  nctype_lut[nc_x.nc_type],
2339                                                  nc_x.nc_dnstr),
2340                            properties=verify_properties, debug=DEBUG,
2341                            verify=self.verify,
2342                            dot_file_dir=self.dot_file_dir,
2343                            directed=True)
2344
2345             rw_dot_vertices = set(x for x in dot_vertices
2346                                   if not self.get_dsa(x).is_ro())
2347             rw_dot_edges = [(a, b) for a, b in dot_edges if
2348                             a in rw_dot_vertices and b in rw_dot_vertices]
2349             rw_verify_properties = ('connected',
2350                                     'directed_double_ring_or_small')
2351             verify_and_dot('intrasite_rw_post_ntdscon', rw_dot_edges,
2352                            rw_dot_vertices,
2353                            label='%s__%s__%s' % (site_local.site_dnstr,
2354                                                  nctype_lut[nc_x.nc_type],
2355                                                  nc_x.nc_dnstr),
2356                            properties=rw_verify_properties, debug=DEBUG,
2357                            verify=self.verify,
2358                            dot_file_dir=self.dot_file_dir,
2359                            directed=True)
2360
2361     def intrasite(self):
2362         """Generate the intrasite KCC connections
2363
2364         As per MS-ADTS 6.2.2.2.
2365
2366         If self.readonly is False, the connections are added to self.samdb.
2367
2368         After this call, all DCs in each site with more than 3 DCs
2369         should be connected in a bidirectional ring. If a site has 2
2370         DCs, they will bidirectionally connected. Sites with many DCs
2371         may have arbitrary extra connections.
2372
2373         :return: None
2374         """
2375         mydsa = self.my_dsa
2376
2377         DEBUG_FN("intrasite(): enter")
2378
2379         # Test whether local site has topology disabled
2380         mysite = self.my_site
2381         if mysite.is_intrasite_topology_disabled():
2382             return
2383
2384         detect_stale = (not mysite.is_detect_stale_disabled())
2385         for connect in mydsa.connect_table.values():
2386             if connect.to_be_added:
2387                 debug.DEBUG_CYAN("TO BE ADDED:\n%s" % connect)
2388
2389         # Loop thru all the partitions, with gc_only False
2390         for partdn, part in self.part_table.items():
2391             self.construct_intrasite_graph(mysite, mydsa, part, False,
2392                                            detect_stale)
2393             for connect in mydsa.connect_table.values():
2394                 if connect.to_be_added:
2395                     debug.DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2396
2397         # If the DC is a GC server, the KCC constructs an additional NC
2398         # replica graph (and creates nTDSConnection objects) for the
2399         # config NC as above, except that only NC replicas that "are present"
2400         # on GC servers are added to R.
2401         for connect in mydsa.connect_table.values():
2402             if connect.to_be_added:
2403                 debug.DEBUG_YELLOW("TO BE ADDED:\n%s" % connect)
2404
2405         # Do it again, with gc_only True
2406         for partdn, part in self.part_table.items():
2407             if part.is_config():
2408                 self.construct_intrasite_graph(mysite, mydsa, part, True,
2409                                                detect_stale)
2410
2411         # The DC repeats the NC replica graph computation and nTDSConnection
2412         # creation for each of the NC replica graphs, this time assuming
2413         # that no DC has failed. It does so by re-executing the steps as
2414         # if the bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED were
2415         # set in the options attribute of the site settings object for
2416         # the local DC's site.  (ie. we set "detec_stale" flag to False)
2417         for connect in mydsa.connect_table.values():
2418             if connect.to_be_added:
2419                 debug.DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2420
2421         # Loop thru all the partitions.
2422         for partdn, part in self.part_table.items():
2423             self.construct_intrasite_graph(mysite, mydsa, part, False,
2424                                            False)  # don't detect stale
2425
2426         # If the DC is a GC server, the KCC constructs an additional NC
2427         # replica graph (and creates nTDSConnection objects) for the
2428         # config NC as above, except that only NC replicas that "are present"
2429         # on GC servers are added to R.
2430         for connect in mydsa.connect_table.values():
2431             if connect.to_be_added:
2432                 debug.DEBUG_RED("TO BE ADDED:\n%s" % connect)
2433
2434         for partdn, part in self.part_table.items():
2435             if part.is_config():
2436                 self.construct_intrasite_graph(mysite, mydsa, part, True,
2437                                                False)  # don't detect stale
2438
2439         self._commit_changes(mydsa)
2440
2441     def list_dsas(self):
2442         """Compile a comprehensive list of DSA DNs
2443
2444         These are all the DSAs on all the sites that KCC would be
2445         dealing with.
2446
2447         This method is not idempotent and may not work correctly in
2448         sequence with KCC.run().
2449
2450         :return: a list of DSA DN strings.
2451         """
2452         self.load_my_site()
2453         self.load_my_dsa()
2454
2455         self.load_all_sites()
2456         self.load_all_partitions()
2457         self.load_ip_transport()
2458         self.load_all_sitelinks()
2459         dsas = []
2460         for site in self.site_table.values():
2461             dsas.extend([dsa.dsa_dnstr.replace('CN=NTDS Settings,', '', 1)
2462                          for dsa in site.dsa_table.values()])
2463         return dsas
2464
2465     def load_samdb(self, dburl, lp, creds, force=False):
2466         """Load the database using an url, loadparm, and credentials
2467
2468         If force is False, the samdb won't be reloaded if it already
2469         exists.
2470
2471         :param dburl: a database url.
2472         :param lp: a loadparm object.
2473         :param creds: a Credentials object.
2474         :param force: a boolean indicating whether to overwrite.
2475
2476         """
2477         if force or self.samdb is None:
2478             try:
2479                 self.samdb = SamDB(url=dburl,
2480                                    session_info=system_session(),
2481                                    credentials=creds, lp=lp)
2482             except ldb.LdbError, (num, msg):
2483                 raise KCCError("Unable to open sam database %s : %s" %
2484                                (dburl, msg))
2485
2486     def plot_all_connections(self, basename, verify_properties=()):
2487         """Helper function to plot and verify NTDSConnections
2488
2489         :param basename: an identifying string to use in filenames and logs.
2490         :param verify_properties: properties to verify (default empty)
2491         """
2492         verify = verify_properties and self.verify
2493         if not verify and self.dot_file_dir is None:
2494             return
2495
2496         dot_edges = []
2497         dot_vertices = []
2498         edge_colours = []
2499         vertex_colours = []
2500
2501         for dsa in self.dsa_by_dnstr.values():
2502             dot_vertices.append(dsa.dsa_dnstr)
2503             if dsa.is_ro():
2504                 vertex_colours.append('#cc0000')
2505             else:
2506                 vertex_colours.append('#0000cc')
2507             for con in dsa.connect_table.values():
2508                 if con.is_rodc_topology():
2509                     edge_colours.append('red')
2510                 else:
2511                     edge_colours.append('blue')
2512                 dot_edges.append((con.from_dnstr, dsa.dsa_dnstr))
2513
2514         verify_and_dot(basename, dot_edges, vertices=dot_vertices,
2515                        label=self.my_dsa_dnstr,
2516                        properties=verify_properties, debug=DEBUG,
2517                        verify=verify, dot_file_dir=self.dot_file_dir,
2518                        directed=True, edge_colors=edge_colours,
2519                        vertex_colors=vertex_colours)
2520
2521     def run(self, dburl, lp, creds, forced_local_dsa=None,
2522             forget_local_links=False, forget_intersite_links=False,
2523             attempt_live_connections=False):
2524         """Perform a KCC run, possibly updating repsFrom topology
2525
2526         :param dburl: url of the database to work with.
2527         :param lp: a loadparm object.
2528         :param creds: a Credentials object.
2529         :param forced_local_dsa: pretend to be on the DSA with this dn_str
2530         :param forget_local_links: calculate as if no connections existed
2531                (boolean, default False)
2532         :param forget_intersite_links: calculate with only intrasite connection
2533                (boolean, default False)
2534         :param attempt_live_connections: attempt to connect to remote DSAs to
2535                determine link availability (boolean, default False)
2536         :return: 1 on error, 0 otherwise
2537         """
2538         if self.samdb is None:
2539             DEBUG_FN("samdb is None; let's load it from %s" % (dburl,))
2540             self.load_samdb(dburl, lp, creds, force=False)
2541
2542         if forced_local_dsa:
2543             self.samdb.set_ntds_settings_dn("CN=NTDS Settings,%s" %
2544                                             forced_local_dsa)
2545
2546         try:
2547             # Setup
2548             self.load_my_site()
2549             self.load_my_dsa()
2550
2551             self.load_all_sites()
2552             self.load_all_partitions()
2553             self.load_ip_transport()
2554             self.load_all_sitelinks()
2555
2556             if self.verify or self.dot_file_dir is not None:
2557                 guid_to_dnstr = {}
2558                 for site in self.site_table.values():
2559                     guid_to_dnstr.update((str(dsa.dsa_guid), dnstr)
2560                                          for dnstr, dsa
2561                                          in site.dsa_table.items())
2562
2563                 self.plot_all_connections('dsa_initial')
2564
2565                 dot_edges = []
2566                 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2567                 for dnstr, c_rep in current_reps.items():
2568                     DEBUG("c_rep %s" % c_rep)
2569                     dot_edges.append((self.my_dsa.dsa_dnstr, dnstr))
2570
2571                 verify_and_dot('dsa_repsFrom_initial', dot_edges,
2572                                directed=True, label=self.my_dsa_dnstr,
2573                                properties=(), debug=DEBUG, verify=self.verify,
2574                                dot_file_dir=self.dot_file_dir)
2575
2576                 dot_edges = []
2577                 for site in self.site_table.values():
2578                     for dsa in site.dsa_table.values():
2579                         current_reps, needed_reps = dsa.get_rep_tables()
2580                         for dn_str, rep in current_reps.items():
2581                             for reps_from in rep.rep_repsFrom:
2582                                 DEBUG("rep %s" % rep)
2583                                 dsa_guid = str(reps_from.source_dsa_obj_guid)
2584                                 dsa_dn = guid_to_dnstr[dsa_guid]
2585                                 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2586
2587                 verify_and_dot('dsa_repsFrom_initial_all', dot_edges,
2588                                directed=True, label=self.my_dsa_dnstr,
2589                                properties=(), debug=DEBUG, verify=self.verify,
2590                                dot_file_dir=self.dot_file_dir)
2591
2592                 dot_edges = []
2593                 for link in self.sitelink_table.values():
2594                     for a, b in itertools.combinations(link.site_list, 2):
2595                         dot_edges.append((str(a), str(b)))
2596                 properties = ('connected',)
2597                 verify_and_dot('dsa_sitelink_initial', dot_edges,
2598                                directed=False,
2599                                label=self.my_dsa_dnstr, properties=properties,
2600                                debug=DEBUG, verify=self.verify,
2601                                dot_file_dir=self.dot_file_dir)
2602
2603             if forget_local_links:
2604                 for dsa in self.my_site.dsa_table.values():
2605                     dsa.connect_table = dict((k, v) for k, v in
2606                                              dsa.connect_table.items()
2607                                              if v.is_rodc_topology() or
2608                                              (v.from_dnstr not in
2609                                               self.my_site.dsa_table))
2610                 self.plot_all_connections('dsa_forgotten_local')
2611
2612             if forget_intersite_links:
2613                 for site in self.site_table.values():
2614                     for dsa in site.dsa_table.values():
2615                         dsa.connect_table = dict((k, v) for k, v in
2616                                                  dsa.connect_table.items()
2617                                                  if site is self.my_site and
2618                                                  v.is_rodc_topology())
2619
2620                 self.plot_all_connections('dsa_forgotten_all')
2621
2622             if attempt_live_connections:
2623                 # Encapsulates lp and creds in a function that
2624                 # attempts connections to remote DSAs.
2625                 def ping(self, dnsname):
2626                     try:
2627                         drs_utils.drsuapi_connect(dnsname, self.lp, self.creds)
2628                     except drs_utils.drsException:
2629                         return False
2630                     return True
2631             else:
2632                 ping = None
2633             # These are the published steps (in order) for the
2634             # MS-TECH description of the KCC algorithm ([MS-ADTS] 6.2.2)
2635
2636             # Step 1
2637             self.refresh_failed_links_connections(ping)
2638
2639             # Step 2
2640             self.intrasite()
2641
2642             # Step 3
2643             all_connected = self.intersite(ping)
2644
2645             # Step 4
2646             self.remove_unneeded_ntdsconn(all_connected)
2647
2648             # Step 5
2649             self.translate_ntdsconn()
2650
2651             # Step 6
2652             self.remove_unneeded_failed_links_connections()
2653
2654             # Step 7
2655             self.update_rodc_connection()
2656
2657             if self.verify or self.dot_file_dir is not None:
2658                 self.plot_all_connections('dsa_final',
2659                                           ('connected',))
2660
2661                 debug.DEBUG_MAGENTA("there are %d dsa guids" %
2662                                     len(guid_to_dnstr))
2663
2664                 dot_edges = []
2665                 edge_colors = []
2666                 my_dnstr = self.my_dsa.dsa_dnstr
2667                 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2668                 for dnstr, n_rep in needed_reps.items():
2669                     for reps_from in n_rep.rep_repsFrom:
2670                         guid_str = str(reps_from.source_dsa_obj_guid)
2671                         dot_edges.append((my_dnstr, guid_to_dnstr[guid_str]))
2672                         edge_colors.append('#' + str(n_rep.nc_guid)[:6])
2673
2674                 verify_and_dot('dsa_repsFrom_final', dot_edges, directed=True,
2675                                label=self.my_dsa_dnstr,
2676                                properties=(), debug=DEBUG, verify=self.verify,
2677                                dot_file_dir=self.dot_file_dir,
2678                                edge_colors=edge_colors)
2679
2680                 dot_edges = []
2681
2682                 for site in self.site_table.values():
2683                     for dsa in site.dsa_table.values():
2684                         current_reps, needed_reps = dsa.get_rep_tables()
2685                         for n_rep in needed_reps.values():
2686                             for reps_from in n_rep.rep_repsFrom:
2687                                 dsa_guid = str(reps_from.source_dsa_obj_guid)
2688                                 dsa_dn = guid_to_dnstr[dsa_guid]
2689                                 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2690
2691                 verify_and_dot('dsa_repsFrom_final_all', dot_edges,
2692                                directed=True, label=self.my_dsa_dnstr,
2693                                properties=(), debug=DEBUG, verify=self.verify,
2694                                dot_file_dir=self.dot_file_dir)
2695
2696         except:
2697             raise
2698
2699         return 0
2700
2701     def import_ldif(self, dburl, lp, ldif_file, forced_local_dsa=None):
2702         """Import relevant objects and attributes from an LDIF file.
2703
2704         The point of this function is to allow a programmer/debugger to
2705         import an LDIF file with non-security relevent information that
2706         was previously extracted from a DC database.  The LDIF file is used
2707         to create a temporary abbreviated database.  The KCC algorithm can
2708         then run against this abbreviated database for debug or test
2709         verification that the topology generated is computationally the
2710         same between different OSes and algorithms.
2711
2712         :param dburl: path to the temporary abbreviated db to create
2713         :param lp: a loadparm object.
2714         :param ldif_file: path to the ldif file to import
2715         :param forced_local_dsa: perform KCC from this DSA's point of view
2716         :return: zero on success, 1 on error
2717         """
2718         try:
2719             self.samdb = ldif_import_export.ldif_to_samdb(dburl, lp, ldif_file,
2720                                                           forced_local_dsa)
2721         except ldif_import_export.LdifError, e:
2722             logger.critical(e)
2723             return 1
2724         return 0
2725
2726     def export_ldif(self, dburl, lp, creds, ldif_file):
2727         """Save KCC relevant details to an ldif file
2728
2729         The point of this function is to allow a programmer/debugger to
2730         extract an LDIF file with non-security relevent information from
2731         a DC database.  The LDIF file can then be used to "import" via
2732         the import_ldif() function this file into a temporary abbreviated
2733         database.  The KCC algorithm can then run against this abbreviated
2734         database for debug or test verification that the topology generated
2735         is computationally the same between different OSes and algorithms.
2736
2737         :param dburl: LDAP database URL to extract info from
2738         :param lp: a loadparm object.
2739         :param cred: a Credentials object.
2740         :param ldif_file: output LDIF file name to create
2741         :return: zero on success, 1 on error
2742         """
2743         try:
2744             ldif_import_export.samdb_to_ldif_file(self.samdb, dburl, lp, creds,
2745                                                   ldif_file)
2746         except ldif_import_export.LdifError, e:
2747             logger.critical(e)
2748             return 1
2749         return 0