source4/scripting/bin/samba_kcc

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