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