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