python/samba/kcc/__init__.py

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