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