source4/scripting/bin/samba_kcc

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