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 on a site satisfying the given criteria
1225
1226         Part of MS-ADTS 6.2.2.3.4.4
1227
1228         :param site: site object representing the site for which
1229             bridgehead DCs are desired.
1230         :param part: partition for NC to replicate.
1231         :param transport: interSiteTransport object for
1232             replication traffic.
1233         :param partial_ok: True if a DC containing a partial
1234             replica or a full replica will suffice, False if
1235             only a full replica will suffice.
1236         :param detect_failed: True to detect failed DCs and route
1237             replication traffic around them, FALSE to assume
1238             no DC has failed.
1239         :return: list of dsa object for available bridgehead DCs
1240         """
1241
1242         bhs = []
1243
1244         logger.debug("get_all_bridgeheads: %s" % transport.name)
1245         if 'Site-5' in site.site_dnstr:
1246             DEBUG_RED("get_all_bridgeheads with %s, part%s, partial_ok %s"
1247                       " detect_failed %s" % (site.site_dnstr, part.partstr,
1248                                              partial_ok, detect_failed))
1249         logger.debug(site.rw_dsa_table)
1250         for dsa in site.rw_dsa_table.values():
1251
1252             pdnstr = dsa.get_parent_dnstr()
1253
1254             # IF t!bridgeheadServerListBL has one or more values and
1255             # t!bridgeheadServerListBL does not contain a reference
1256             # to the parent object of dc then skip dc
1257             if ((len(transport.bridgehead_list) != 0 and
1258                  pdnstr not in transport.bridgehead_list)):
1259                 continue
1260
1261             # IF dc is in the same site as the local DC
1262             #    IF a replica of cr!nCName is not in the set of NC replicas
1263             #    that "should be present" on dc or a partial replica of the
1264             #    NC "should be present" but partialReplicasOkay = FALSE
1265             #        Skip dc
1266             if self.my_site.same_site(dsa):
1267                 needed, ro, partial = part.should_be_present(dsa)
1268                 if not needed or (partial and not partial_ok):
1269                     continue
1270                 rep = dsa.get_current_replica(part.nc_dnstr)
1271
1272             # ELSE
1273             #     IF an NC replica of cr!nCName is not in the set of NC
1274             #     replicas that "are present" on dc or a partial replica of
1275             #     the NC "is present" but partialReplicasOkay = FALSE
1276             #          Skip dc
1277             else:
1278                 rep = dsa.get_current_replica(part.nc_dnstr)
1279                 if rep is None or (rep.is_partial() and not partial_ok):
1280                     continue
1281
1282             # IF AmIRODC() and cr!nCName corresponds to default NC then
1283             #     Let dsaobj be the nTDSDSA object of the dc
1284             #     IF  dsaobj.msDS-Behavior-Version < DS_DOMAIN_FUNCTION_2008
1285             #         Skip dc
1286             if self.my_dsa.is_ro() and rep is not None and rep.is_default():
1287                 if not dsa.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
1288                     continue
1289
1290             # IF t!name != "IP" and the parent object of dc has no value for
1291             # the attribute specified by t!transportAddressAttribute
1292             #     Skip dc
1293             if transport.name != "IP":
1294                 # MS tech specification says we retrieve the named
1295                 # attribute in "transportAddressAttribute" from the parent
1296                 # of the DSA object
1297                 try:
1298                     attrs = [transport.address_attr]
1299
1300                     res = self.samdb.search(base=pdnstr, scope=ldb.SCOPE_BASE,
1301                                             attrs=attrs)
1302                 except ldb.LdbError, (enum, estr):
1303                     continue
1304
1305                 msg = res[0]
1306                 if transport.address_attr not in msg:
1307                     continue
1308                 #XXX nastr is NEVER USED. It will be removed.
1309                 nastr = str(msg[transport.address_attr][0])
1310
1311             # IF BridgeheadDCFailed(dc!objectGUID, detectFailedDCs) = TRUE
1312             #     Skip dc
1313             if self.is_bridgehead_failed(dsa, detect_failed):
1314                 DEBUG("bridgehead is failed")
1315                 continue
1316
1317             logger.debug("get_all_bridgeheads: dsadn=%s" % dsa.dsa_dnstr)
1318             bhs.append(dsa)
1319
1320         # IF bit NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED is set in
1321         # s!options
1322         #    SORT bhs such that all GC servers precede DCs that are not GC
1323         #    servers, and otherwise by ascending objectGUID
1324         # ELSE
1325         #    SORT bhs in a random order
1326         if site.is_random_bridgehead_disabled():
1327             bhs.sort(sort_dsa_by_gc_and_guid)
1328         else:
1329             random.shuffle(bhs)
1330         DEBUG_YELLOW(bhs)
1331         return bhs
1332
1333     def is_bridgehead_failed(self, dsa, detect_failed):
1334         """Determine whether a given DC is known to be in a failed state
1335         ::returns: True if and only if the DC should be considered failed
1336
1337         Here we DEPART from the pseudo code spec which appears to be
1338         wrong. It says, in full:
1339
1340     /***** BridgeheadDCFailed *****/
1341     /* Determine whether a given DC is known to be in a failed state.
1342      * IN: objectGUID - objectGUID of the DC's nTDSDSA object.
1343      * IN: detectFailedDCs - TRUE if and only failed DC detection is
1344      *     enabled.
1345      * RETURNS: TRUE if and only if the DC should be considered to be in a
1346      *          failed state.
1347      */
1348     BridgeheadDCFailed(IN GUID objectGUID, IN bool detectFailedDCs) : bool
1349     {
1350         IF bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set in
1351         the options attribute of the site settings object for the local
1352         DC's site
1353             RETURN FALSE
1354         ELSEIF a tuple z exists in the kCCFailedLinks or
1355         kCCFailedConnections variables such that z.UUIDDsa =
1356         objectGUID, z.FailureCount > 1, and the current time -
1357         z.TimeFirstFailure > 2 hours
1358             RETURN TRUE
1359         ELSE
1360             RETURN detectFailedDCs
1361         ENDIF
1362     }
1363
1364         where you will see detectFailedDCs is not behaving as
1365         advertised -- it is acting as a default return code in the
1366         event that a failure is not detected, not a switch turning
1367         detection on or off. Elsewhere the documentation seems to
1368         concur with the comment rather than the code.
1369         """
1370         if not detect_failed:
1371             return False
1372
1373         # NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED = 0x00000008
1374         # When DETECT_STALE_DISABLED, we can never know of if
1375         # it's in a failed state
1376         if self.my_site.site_options & 0x00000008:
1377             return False
1378
1379         return self.is_stale_link_connection(dsa)
1380
1381     def create_connection(self, part, rbh, rsite, transport,
1382                           lbh, lsite, link_opt, link_sched,
1383                           partial_ok, detect_failed):
1384         """Create an nTDSConnection object with the given parameters
1385         if one does not already exist.
1386
1387         :param part: crossRef object for the NC to replicate.
1388         :param rbh: nTDSDSA object for DC to act as the
1389             IDL_DRSGetNCChanges server (which is in a site other
1390             than the local DC's site).
1391         :param rsite: site of the rbh
1392         :param transport: interSiteTransport object for the transport
1393             to use for replication traffic.
1394         :param lbh: nTDSDSA object for DC to act as the
1395             IDL_DRSGetNCChanges client (which is in the local DC's site).
1396         :param lsite: site of the lbh
1397         :param link_opt: Replication parameters (aggregated siteLink options,
1398                                                  etc.)
1399         :param link_sched: Schedule specifying the times at which
1400             to begin replicating.
1401         :partial_ok: True if bridgehead DCs containing partial
1402             replicas of the NC are acceptable.
1403         :param detect_failed: True to detect failed DCs and route
1404             replication traffic around them, FALSE to assume no DC
1405             has failed.
1406         """
1407         rbhs_all = self.get_all_bridgeheads(rsite, part, transport,
1408                                             partial_ok, False)
1409         rbh_table = {x.dsa_dnstr: x for x in rbhs_all}
1410
1411         DEBUG_GREY("rbhs_all: %s %s" % (len(rbhs_all),
1412                                         [x.dsa_dnstr for x in rbhs_all]))
1413
1414         # MS-TECH says to compute rbhs_avail but then doesn't use it
1415         # rbhs_avail = self.get_all_bridgeheads(rsite, part, transport,
1416         #                                        partial_ok, detect_failed)
1417
1418         lbhs_all = self.get_all_bridgeheads(lsite, part, transport,
1419                                             partial_ok, False)
1420         if lbh.is_ro():
1421             lbhs_all.append(lbh)
1422
1423         DEBUG_GREY("lbhs_all: %s %s" % (len(lbhs_all),
1424                                         [x.dsa_dnstr for x in lbhs_all]))
1425
1426         # MS-TECH says to compute lbhs_avail but then doesn't use it
1427         # lbhs_avail = self.get_all_bridgeheads(lsite, part, transport,
1428         #                                       partial_ok, detect_failed)
1429
1430         # FOR each nTDSConnection object cn such that the parent of cn is
1431         # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1432         for ldsa in lbhs_all:
1433             for cn in ldsa.connect_table.values():
1434
1435                 rdsa = rbh_table.get(cn.from_dnstr)
1436                 if rdsa is None:
1437                     continue
1438
1439                 DEBUG_DARK_YELLOW("rdsa is %s" % rdsa.dsa_dnstr)
1440                 # IF bit NTDSCONN_OPT_IS_GENERATED is set in cn!options and
1441                 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options and
1442                 # cn!transportType references t
1443                 if ((cn.is_generated() and
1444                      not cn.is_rodc_topology() and
1445                      cn.transport_guid == transport.guid)):
1446
1447                     # IF bit NTDSCONN_OPT_USER_OWNED_SCHEDULE is clear in
1448                     # cn!options and cn!schedule != sch
1449                     #     Perform an originating update to set cn!schedule to
1450                     #     sched
1451                     if ((not cn.is_user_owned_schedule() and
1452                          not cn.is_equivalent_schedule(link_sched))):
1453                         cn.schedule = link_sched
1454                         cn.set_modified(True)
1455
1456                     # IF bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1457                     # NTDSCONN_OPT_USE_NOTIFY are set in cn
1458                     if cn.is_override_notify_default() and \
1459                        cn.is_use_notify():
1460
1461                         # IF bit NTDSSITELINK_OPT_USE_NOTIFY is clear in
1462                         # ri.Options
1463                         #    Perform an originating update to clear bits
1464                         #    NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1465                         #    NTDSCONN_OPT_USE_NOTIFY in cn!options
1466                         if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) == 0:
1467                             cn.options &= \
1468                                 ~(dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1469                                   dsdb.NTDSCONN_OPT_USE_NOTIFY)
1470                             cn.set_modified(True)
1471
1472                     # ELSE
1473                     else:
1474
1475                         # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in
1476                         # ri.Options
1477                         #     Perform an originating update to set bits
1478                         #     NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1479                         #     NTDSCONN_OPT_USE_NOTIFY in cn!options
1480                         if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1481                             cn.options |= \
1482                                 (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1483                                  dsdb.NTDSCONN_OPT_USE_NOTIFY)
1484                             cn.set_modified(True)
1485
1486                     # IF bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options
1487                     if cn.is_twoway_sync():
1488
1489                         # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is clear in
1490                         # ri.Options
1491                         #     Perform an originating update to clear bit
1492                         #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1493                         if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) == 0:
1494                             cn.options &= ~dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1495                             cn.set_modified(True)
1496
1497                     # ELSE
1498                     else:
1499
1500                         # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in
1501                         # ri.Options
1502                         #     Perform an originating update to set bit
1503                         #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1504                         if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1505                             cn.options |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1506                             cn.set_modified(True)
1507
1508                     # IF bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION is set
1509                     # in cn!options
1510                     if cn.is_intersite_compression_disabled():
1511
1512                         # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is clear
1513                         # in ri.Options
1514                         #     Perform an originating update to clear bit
1515                         #     NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1516                         #     cn!options
1517                         if ((link_opt &
1518                              dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) == 0):
1519                             cn.options &= \
1520                                 ~dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1521                             cn.set_modified(True)
1522
1523                     # ELSE
1524                     else:
1525                         # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1526                         # ri.Options
1527                         #     Perform an originating update to set bit
1528                         #     NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1529                         #     cn!options
1530                         if ((link_opt &
1531                              dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1532                             cn.options |= \
1533                                 dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1534                             cn.set_modified(True)
1535
1536                     # Display any modified connection
1537                     if opts.readonly:
1538                         if cn.to_be_modified:
1539                             logger.info("TO BE MODIFIED:\n%s" % cn)
1540
1541                         ldsa.commit_connections(self.samdb, ro=True)
1542                     else:
1543                         ldsa.commit_connections(self.samdb)
1544         # ENDFOR
1545
1546         valid_connections = 0
1547
1548         # FOR each nTDSConnection object cn such that cn!parent is
1549         # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1550         for ldsa in lbhs_all:
1551             for cn in ldsa.connect_table.values():
1552
1553                 rdsa = rbh_table.get(cn.from_dnstr)
1554                 if rdsa is None:
1555                     continue
1556
1557                 DEBUG_DARK_YELLOW("round 2: rdsa is %s" % rdsa.dsa_dnstr)
1558
1559                 # IF (bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options or
1560                 # cn!transportType references t) and
1561                 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options
1562                 if (((not cn.is_generated() or
1563                       cn.transport_guid == transport.guid) and
1564                      not cn.is_rodc_topology())):
1565
1566                     # LET rguid be the objectGUID of the nTDSDSA object
1567                     # referenced by cn!fromServer
1568                     # LET lguid be (cn!parent)!objectGUID
1569
1570                     # IF BridgeheadDCFailed(rguid, detectFailedDCs) = FALSE and
1571                     # BridgeheadDCFailed(lguid, detectFailedDCs) = FALSE
1572                     #     Increment cValidConnections by 1
1573                     if ((not self.is_bridgehead_failed(rdsa, detect_failed) and
1574                          not self.is_bridgehead_failed(ldsa, detect_failed))):
1575                         valid_connections += 1
1576
1577                     # IF keepConnections does not contain cn!objectGUID
1578                     #     APPEND cn!objectGUID to keepConnections
1579                     self.kept_connections.add(cn)
1580
1581         # ENDFOR
1582         DEBUG_RED("valid connections %d" % valid_connections)
1583         DEBUG("kept_connections:\n%s" % (self.kept_connections,))
1584         # IF cValidConnections = 0
1585         if valid_connections == 0:
1586
1587             # LET opt be NTDSCONN_OPT_IS_GENERATED
1588             opt = dsdb.NTDSCONN_OPT_IS_GENERATED
1589
1590             # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in ri.Options
1591             #     SET bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1592             #     NTDSCONN_OPT_USE_NOTIFY in opt
1593             if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1594                 opt |= (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1595                         dsdb.NTDSCONN_OPT_USE_NOTIFY)
1596
1597             # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in ri.Options
1598             #     SET bit NTDSCONN_OPT_TWOWAY_SYNC opt
1599             if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1600                 opt |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1601
1602             # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1603             # ri.Options
1604             #     SET bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in opt
1605             if ((link_opt &
1606                  dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1607                 opt |= dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1608
1609             # Perform an originating update to create a new nTDSConnection
1610             # object cn that is a child of lbh, cn!enabledConnection = TRUE,
1611             # cn!options = opt, cn!transportType is a reference to t,
1612             # cn!fromServer is a reference to rbh, and cn!schedule = sch
1613             DEBUG_FN("new connection, KCC dsa: %s" % self.my_dsa.dsa_dnstr)
1614             cn = lbh.new_connection(opt, 0, transport,
1615                                     rbh.dsa_dnstr, link_sched)
1616
1617             # Display any added connection
1618             if opts.readonly:
1619                 if cn.to_be_added:
1620                     logger.info("TO BE ADDED:\n%s" % cn)
1621
1622                     lbh.commit_connections(self.samdb, ro=True)
1623             else:
1624                 lbh.commit_connections(self.samdb)
1625
1626             # APPEND cn!objectGUID to keepConnections
1627             self.kept_connections.add(cn)
1628
1629     def add_transports(self, vertex, local_vertex, graph, detect_failed):
1630         """Build a Vertex's transport lists
1631
1632         Each vertex has accept_red_red and accept_black lists that
1633         list what transports they accept under various conditions. The
1634         only transport that is ever accepted is IP, and a dummy extra
1635         transport called "EDGE_TYPE_ALL".
1636
1637         Part of MS-ADTS 6.2.2.3.4.3 -- ColorVertices
1638
1639         :param vertex: the remote vertex we are thinking about
1640         :param local_vertex: the vertex relating to the local site.
1641         :param graph: the intersite graph
1642         :param detect_failed: whether to detect failed links
1643         :return: True if some bridgeheads were not found
1644         """
1645         # The docs ([MS-ADTS] 6.2.2.3.4.3) say to use local_vertex
1646         # here, but using vertex seems to make more sense. That is,
1647         # the docs want this:
1648         #
1649         #bh = self.get_bridgehead(vertex.site, vertex.part, transport,
1650         #                         local_vertex.is_black(), detect_failed)
1651         #
1652         # TODO WHY?????
1653
1654         vertex.accept_red_red = []
1655         vertex.accept_black = []
1656         found_failed = False
1657         for t_guid, transport in self.transport_table.items():
1658             if transport.name != 'IP':
1659                 #XXX well this is cheating a bit
1660                 logging.warning("WARNING: we are ignoring a transport named %r"
1661                                 % transport.name)
1662                 continue
1663
1664             # FLAG_CR_NTDS_DOMAIN 0x00000002
1665             if ((vertex.is_red() and transport.name != "IP" and
1666                  vertex.part.system_flags & 0x00000002)):
1667                 continue
1668
1669             if vertex not in graph.connected_vertices:
1670                 continue
1671
1672             partial_replica_okay = vertex.is_black()
1673             bh = self.get_bridgehead(vertex.site, vertex.part, transport,
1674                                      partial_replica_okay, detect_failed)
1675             if bh is None:
1676                 found_failed = True
1677                 continue
1678
1679             vertex.accept_red_red.append(t_guid)
1680             vertex.accept_black.append(t_guid)
1681
1682             # Add additional transport to allow another run of Dijkstra
1683             vertex.accept_red_red.append("EDGE_TYPE_ALL")
1684             vertex.accept_black.append("EDGE_TYPE_ALL")
1685
1686         return found_failed
1687
1688     def create_connections(self, graph, part, detect_failed):
1689         """Construct an NC replica graph for the NC identified by
1690         the given crossRef, then create any additional nTDSConnection
1691         objects required.
1692
1693         :param graph: site graph.
1694         :param part: crossRef object for NC.
1695         :param detect_failed:  True to detect failed DCs and route
1696             replication traffic around them, False to assume no DC
1697             has failed.
1698
1699         Modifies self.kept_connections by adding any connections
1700         deemed to be "in use".
1701
1702         ::returns: (all_connected, found_failed_dc)
1703         (all_connected) True if the resulting NC replica graph
1704             connects all sites that need to be connected.
1705         (found_failed_dc) True if one or more failed DCs were
1706             detected.
1707         """
1708         all_connected = True
1709         found_failed = False
1710
1711         logger.debug("create_connections(): enter\n"
1712                      "\tpartdn=%s\n\tdetect_failed=%s" %
1713                      (part.nc_dnstr, detect_failed))
1714
1715         # XXX - This is a highly abbreviated function from the MS-TECH
1716         #       ref.  It creates connections between bridgeheads to all
1717         #       sites that have appropriate replicas.  Thus we are not
1718         #       creating a minimum cost spanning tree but instead
1719         #       producing a fully connected tree.  This should produce
1720         #       a full (albeit not optimal cost) replication topology.
1721
1722         my_vertex = Vertex(self.my_site, part)
1723         my_vertex.color_vertex()
1724
1725         for v in graph.vertices:
1726             v.color_vertex()
1727             if self.add_transports(v, my_vertex, graph, False):
1728                 found_failed = True
1729
1730         # No NC replicas for this NC in the site of the local DC,
1731         # so no nTDSConnection objects need be created
1732         if my_vertex.is_white():
1733             return all_connected, found_failed
1734
1735         edge_list, n_components = get_spanning_tree_edges(graph,
1736                                                           self.my_site,
1737                                                           label=part.partstr)
1738
1739         logger.debug("%s Number of components: %d" %
1740                      (part.nc_dnstr, n_components))
1741         if n_components > 1:
1742             all_connected = False
1743
1744         # LET partialReplicaOkay be TRUE if and only if
1745         # localSiteVertex.Color = COLOR.BLACK
1746         partial_ok = my_vertex.is_black()
1747
1748         # Utilize the IP transport only for now
1749         transport = self.ip_transport
1750
1751         DEBUG("edge_list %s" % edge_list)
1752         for e in edge_list:
1753             # XXX more accurate comparison?
1754             if e.directed and e.vertices[0].site is self.my_site:
1755                 continue
1756
1757             if e.vertices[0].site is self.my_site:
1758                 rsite = e.vertices[1].site
1759             else:
1760                 rsite = e.vertices[0].site
1761
1762             # We don't make connections to our own site as that
1763             # is intrasite topology generator's job
1764             if rsite is self.my_site:
1765                 DEBUG("rsite is my_site")
1766                 continue
1767
1768             # Determine bridgehead server in remote site
1769             rbh = self.get_bridgehead(rsite, part, transport,
1770                                       partial_ok, detect_failed)
1771             if rbh is None:
1772                 continue
1773
1774             # RODC acts as an BH for itself
1775             # IF AmIRODC() then
1776             #     LET lbh be the nTDSDSA object of the local DC
1777             # ELSE
1778             #     LET lbh be the result of GetBridgeheadDC(localSiteVertex.ID,
1779             #     cr, t, partialReplicaOkay, detectFailedDCs)
1780             if self.my_dsa.is_ro():
1781                 lsite = self.my_site
1782                 lbh = self.my_dsa
1783             else:
1784                 lsite = self.my_site
1785                 lbh = self.get_bridgehead(lsite, part, transport,
1786                                           partial_ok, detect_failed)
1787             # TODO
1788             if lbh is None:
1789                 DEBUG_RED("DISASTER! lbh is None")
1790                 return False, True
1791
1792             DEBUG_CYAN("SITES")
1793             print lsite, rsite
1794             DEBUG_BLUE("vertices")
1795             print e.vertices
1796             DEBUG_BLUE("bridgeheads")
1797             print lbh, rbh
1798             DEBUG_BLUE("-" * 70)
1799
1800             sitelink = e.site_link
1801             if sitelink is None:
1802                 link_opt = 0x0
1803                 link_sched = None
1804             else:
1805                 link_opt = sitelink.options
1806                 link_sched = sitelink.schedule
1807
1808             self.create_connection(part, rbh, rsite, transport,
1809                                    lbh, lsite, link_opt, link_sched,
1810                                    partial_ok, detect_failed)
1811
1812         return all_connected, found_failed
1813
1814     def create_intersite_connections(self):
1815         """Computes an NC replica graph for each NC replica that "should be
1816         present" on the local DC or "is present" on any DC in the same site
1817         as the local DC. For each edge directed to an NC replica on such a
1818         DC from an NC replica on a DC in another site, the KCC creates an
1819         nTDSConnection object to imply that edge if one does not already
1820         exist.
1821
1822         Modifies self.kept_connections - A set of nTDSConnection
1823         objects for edges that are directed
1824         to the local DC's site in one or more NC replica graphs.
1825
1826         returns: True if spanning trees were created for all NC replica
1827             graphs, otherwise False.
1828         """
1829         all_connected = True
1830         self.kept_connections = set()
1831
1832         # LET crossRefList be the set containing each object o of class
1833         # crossRef such that o is a child of the CN=Partitions child of the
1834         # config NC
1835
1836         # FOR each crossRef object cr in crossRefList
1837         #    IF cr!enabled has a value and is false, or if FLAG_CR_NTDS_NC
1838         #        is clear in cr!systemFlags, skip cr.
1839         #    LET g be the GRAPH return of SetupGraph()
1840
1841         for part in self.part_table.values():
1842
1843             if not part.is_enabled():
1844                 continue
1845
1846             if part.is_foreign():
1847                 continue
1848
1849             graph = self.setup_graph(part)
1850
1851             # Create nTDSConnection objects, routing replication traffic
1852             # around "failed" DCs.
1853             found_failed = False
1854
1855             connected, found_failed = self.create_connections(graph,
1856                                                               part, True)
1857
1858             DEBUG("with detect_failed: connected %s Found failed %s" %
1859                   (connected, found_failed))
1860             if not connected:
1861                 all_connected = False
1862
1863                 if found_failed:
1864                     # One or more failed DCs preclude use of the ideal NC
1865                     # replica graph. Add connections for the ideal graph.
1866                     self.create_connections(graph, part, False)
1867
1868         return all_connected
1869
1870     def intersite(self):
1871         """The head method for generating the inter-site KCC replica
1872         connection graph and attendant nTDSConnection objects
1873         in the samdb.
1874
1875         Produces self.kept_connections set of NTDS Connections
1876         that should be kept during subsequent pruning process.
1877
1878         ::return (True or False):  (True) if the produced NC replica
1879             graph connects all sites that need to be connected
1880         """
1881
1882         # Retrieve my DSA
1883         mydsa = self.my_dsa
1884         mysite = self.my_site
1885         all_connected = True
1886
1887         logger.debug("intersite(): enter")
1888
1889         # Determine who is the ISTG
1890         if opts.readonly:
1891             mysite.select_istg(self.samdb, mydsa, ro=True)
1892         else:
1893             mysite.select_istg(self.samdb, mydsa, ro=False)
1894
1895         # Test whether local site has topology disabled
1896         if mysite.is_intersite_topology_disabled():
1897             logger.debug("intersite(): exit disabled all_connected=%d" %
1898                          all_connected)
1899             return all_connected
1900
1901         if not mydsa.is_istg():
1902             logger.debug("intersite(): exit not istg all_connected=%d" %
1903                          all_connected)
1904             return all_connected
1905
1906         self.merge_failed_links()
1907
1908         # For each NC with an NC replica that "should be present" on the
1909         # local DC or "is present" on any DC in the same site as the
1910         # local DC, the KCC constructs a site graph--a precursor to an NC
1911         # replica graph. The site connectivity for a site graph is defined
1912         # by objects of class interSiteTransport, siteLink, and
1913         # siteLinkBridge in the config NC.
1914
1915         all_connected = self.create_intersite_connections()
1916
1917         logger.debug("intersite(): exit all_connected=%d" % all_connected)
1918         return all_connected
1919
1920     def update_rodc_connection(self):
1921         """Runs when the local DC is an RODC and updates the RODC NTFRS
1922         connection object.
1923         """
1924         # Given an nTDSConnection object cn1, such that cn1.options contains
1925         # NTDSCONN_OPT_RODC_TOPOLOGY, and another nTDSConnection object cn2,
1926         # does not contain NTDSCONN_OPT_RODC_TOPOLOGY, modify cn1 to ensure
1927         # that the following is true:
1928         #
1929         #     cn1.fromServer = cn2.fromServer
1930         #     cn1.schedule = cn2.schedule
1931         #
1932         # If no such cn2 can be found, cn1 is not modified.
1933         # If no such cn1 can be found, nothing is modified by this task.
1934
1935         if not self.my_dsa.is_ro():
1936             return
1937
1938         all_connections = self.my_dsa.connect_table.values()
1939         ro_connections = [x for x in all_connections if x.is_rodc_topology()]
1940         rw_connections = [x for x in all_connections
1941                           if x not in ro_connections]
1942
1943         # XXX here we are dealing with multiple RODC_TOPO connections,
1944         # if they exist. It is not clear whether the spec means that
1945         # or if it ever arises.
1946         if rw_connections and ro_connections:
1947             for con in ro_connections:
1948                 cn2 = rw_connections[0]
1949                 con.from_dnstr = cn2.from_dnstr
1950                 con.schedule = cn2.schedule
1951                 con.to_be_modified = True
1952
1953             self.my_dsa.commit_connections(self.samdb, ro=opts.readonly)
1954
1955     def intrasite_max_node_edges(self, node_count):
1956         """Returns the maximum number of edges directed to a node in
1957         the intrasite replica graph.
1958
1959         The KCC does not create more
1960         than 50 edges directed to a single DC. To optimize replication,
1961         we compute that each node should have n+2 total edges directed
1962         to it such that (n) is the smallest non-negative integer
1963         satisfying (node_count <= 2*(n*n) + 6*n + 7)
1964
1965         (If the number of edges is m (i.e. n + 2), that is the same as
1966         2 * m*m - 2 * m + 3).
1967
1968         edges  n   nodecount
1969           2    0    7
1970           3    1   15
1971           4    2   27
1972           5    3   43
1973                   ...
1974          50   48 4903
1975
1976         :param node_count: total number of nodes in the replica graph
1977
1978         The intention is that there should be no more than 3 hops
1979         between any two DSAs at a site. With up to 7 nodes the 2 edges
1980         of the ring are enough; any configuration of extra edges with
1981         8 nodes will be enough. It is less clear that the 3 hop
1982         guarantee holds at e.g. 15 nodes in degenerate cases, but
1983         those are quite unlikely given the extra edges are randomly
1984         arranged.
1985         """
1986         n = 0
1987         while True:
1988             if node_count <= (2 * (n * n) + (6 * n) + 7):
1989                 break
1990             n = n + 1
1991         n = n + 2
1992         if n < 50:
1993             return n
1994         return 50
1995
1996     def construct_intrasite_graph(self, site_local, dc_local,
1997                                   nc_x, gc_only, detect_stale):
1998         # [MS-ADTS] 6.2.2.2
1999         # We're using the MS notation names here to allow
2000         # correlation back to the published algorithm.
2001         #
2002         # nc_x     - naming context (x) that we are testing if it
2003         #            "should be present" on the local DC
2004         # f_of_x   - replica (f) found on a DC (s) for NC (x)
2005         # dc_s     - DC where f_of_x replica was found
2006         # dc_local - local DC that potentially needs a replica
2007         #            (f_of_x)
2008         # r_list   - replica list R
2009         # p_of_x   - replica (p) is partial and found on a DC (s)
2010         #            for NC (x)
2011         # l_of_x   - replica (l) is the local replica for NC (x)
2012         #            that should appear on the local DC
2013         # r_len = is length of replica list |R|
2014         #
2015         # If the DSA doesn't need a replica for this
2016         # partition (NC x) then continue
2017         needed, ro, partial = nc_x.should_be_present(dc_local)
2018
2019         DEBUG_YELLOW("construct_intrasite_graph(): enter" +
2020                      "\n\tgc_only=%d" % gc_only +
2021                      "\n\tdetect_stale=%d" % detect_stale +
2022                      "\n\tneeded=%s" % needed +
2023                      "\n\tro=%s" % ro +
2024                      "\n\tpartial=%s" % partial +
2025                      "\n%s" % nc_x)
2026
2027         if not needed:
2028             DEBUG_RED("%s lacks 'should be present' status, "
2029                       "aborting construct_intersite_graph!" %
2030                       nc_x.nc_dnstr)
2031             return
2032
2033         # Create a NCReplica that matches what the local replica
2034         # should say.  We'll use this below in our r_list
2035         l_of_x = NCReplica(dc_local.dsa_dnstr, dc_local.dsa_guid,
2036                            nc_x.nc_dnstr)
2037
2038         l_of_x.identify_by_basedn(self.samdb)
2039
2040         l_of_x.rep_partial = partial
2041         l_of_x.rep_ro = ro
2042
2043         # Add this replica that "should be present" to the
2044         # needed replica table for this DSA
2045         dc_local.add_needed_replica(l_of_x)
2046
2047         # Replica list
2048         #
2049         # Let R be a sequence containing each writable replica f of x
2050         # such that f "is present" on a DC s satisfying the following
2051         # criteria:
2052         #
2053         #  * s is a writable DC other than the local DC.
2054         #
2055         #  * s is in the same site as the local DC.
2056         #
2057         #  * If x is a read-only full replica and x is a domain NC,
2058         #    then the DC's functional level is at least
2059         #    DS_BEHAVIOR_WIN2008.
2060         #
2061         #  * Bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set
2062         #    in the options attribute of the site settings object for
2063         #    the local DC's site, or no tuple z exists in the
2064         #    kCCFailedLinks or kCCFailedConnections variables such
2065         #    that z.UUIDDsa is the objectGUID of the nTDSDSA object
2066         #    for s, z.FailureCount > 0, and the current time -
2067         #    z.TimeFirstFailure > 2 hours.
2068
2069         r_list = []
2070
2071         # We'll loop thru all the DSAs looking for
2072         # writeable NC replicas that match the naming
2073         # context dn for (nc_x)
2074         #
2075         for dc_s in self.my_site.dsa_table.values():
2076             # If this partition (nc_x) doesn't appear as a
2077             # replica (f_of_x) on (dc_s) then continue
2078             if not nc_x.nc_dnstr in dc_s.current_rep_table:
2079                 continue
2080
2081             # Pull out the NCReplica (f) of (x) with the dn
2082             # that matches NC (x) we are examining.
2083             f_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2084
2085             # Replica (f) of NC (x) must be writable
2086             if f_of_x.is_ro():
2087                 continue
2088
2089             # Replica (f) of NC (x) must satisfy the
2090             # "is present" criteria for DC (s) that
2091             # it was found on
2092             if not f_of_x.is_present():
2093                 continue
2094
2095             # DC (s) must be a writable DSA other than
2096             # my local DC.  In other words we'd only replicate
2097             # from other writable DC
2098             if dc_s.is_ro() or dc_s is dc_local:
2099                 continue
2100
2101             # Certain replica graphs are produced only
2102             # for global catalogs, so test against
2103             # method input parameter
2104             if gc_only and not dc_s.is_gc():
2105                 continue
2106
2107             # DC (s) must be in the same site as the local DC
2108             # as this is the intra-site algorithm. This is
2109             # handled by virtue of placing DSAs in per
2110             # site objects (see enclosing for() loop)
2111
2112             # If NC (x) is intended to be read-only full replica
2113             # for a domain NC on the target DC then the source
2114             # DC should have functional level at minimum WIN2008
2115             #
2116             # Effectively we're saying that in order to replicate
2117             # to a targeted RODC (which was introduced in Windows 2008)
2118             # then we have to replicate from a DC that is also minimally
2119             # at that level.
2120             #
2121             # You can also see this requirement in the MS special
2122             # considerations for RODC which state that to deploy
2123             # an RODC, at least one writable domain controller in
2124             # the domain must be running Windows Server 2008
2125             if ro and not partial and nc_x.nc_type == NCType.domain:
2126                 if not dc_s.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
2127                     continue
2128
2129             # If we haven't been told to turn off stale connection
2130             # detection and this dsa has a stale connection then
2131             # continue
2132             if detect_stale and self.is_stale_link_connection(dc_s):
2133                 continue
2134
2135             # Replica meets criteria.  Add it to table indexed
2136             # by the GUID of the DC that it appears on
2137             r_list.append(f_of_x)
2138
2139         # If a partial (not full) replica of NC (x) "should be present"
2140         # on the local DC, append to R each partial replica (p of x)
2141         # such that p "is present" on a DC satisfying the same
2142         # criteria defined above for full replica DCs.
2143         #
2144         # XXX This loop and the previous one differ only in whether
2145         # the replica is partial or not. here we only accept partial
2146         # (because we're partial); before we only accepted full. Order
2147         # doen't matter (the list is sorted a few lines down) so these
2148         # loops could easily be merged. Or this could be a helper
2149         # function.
2150
2151         if partial:
2152             # Now we loop thru all the DSAs looking for
2153             # partial NC replicas that match the naming
2154             # context dn for (NC x)
2155             for dc_s in self.my_site.dsa_table.values():
2156
2157                 # If this partition NC (x) doesn't appear as a
2158                 # replica (p) of NC (x) on the dsa DC (s) then
2159                 # continue
2160                 if not nc_x.nc_dnstr in dc_s.current_rep_table:
2161                     continue
2162
2163                 # Pull out the NCReplica with the dn that
2164                 # matches NC (x) we are examining.
2165                 p_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2166
2167                 # Replica (p) of NC (x) must be partial
2168                 if not p_of_x.is_partial():
2169                     continue
2170
2171                 # Replica (p) of NC (x) must satisfy the
2172                 # "is present" criteria for DC (s) that
2173                 # it was found on
2174                 if not p_of_x.is_present():
2175                     continue
2176
2177                 # DC (s) must be a writable DSA other than
2178                 # my DSA.  In other words we'd only replicate
2179                 # from other writable DSA
2180                 if dc_s.is_ro() or dc_s is dc_local:
2181                     continue
2182
2183                 # Certain replica graphs are produced only
2184                 # for global catalogs, so test against
2185                 # method input parameter
2186                 if gc_only and not dc_s.is_gc():
2187                     continue
2188
2189                 # If we haven't been told to turn off stale connection
2190                 # detection and this dsa has a stale connection then
2191                 # continue
2192                 if detect_stale and self.is_stale_link_connection(dc_s):
2193                     continue
2194
2195                 # Replica meets criteria.  Add it to table indexed
2196                 # by the GUID of the DSA that it appears on
2197                 r_list.append(p_of_x)
2198
2199         # Append to R the NC replica that "should be present"
2200         # on the local DC
2201         r_list.append(l_of_x)
2202
2203         r_list.sort(sort_replica_by_dsa_guid)
2204         r_len = len(r_list)
2205
2206         max_node_edges = self.intrasite_max_node_edges(r_len)
2207
2208         # Add a node for each r_list element to the replica graph
2209         graph_list = []
2210         for rep in r_list:
2211             node = GraphNode(rep.rep_dsa_dnstr, max_node_edges)
2212             graph_list.append(node)
2213
2214         # For each r(i) from (0 <= i < |R|-1)
2215         i = 0
2216         while i < (r_len-1):
2217             # Add an edge from r(i) to r(i+1) if r(i) is a full
2218             # replica or r(i+1) is a partial replica
2219             if not r_list[i].is_partial() or r_list[i+1].is_partial():
2220                 graph_list[i+1].add_edge_from(r_list[i].rep_dsa_dnstr)
2221
2222             # Add an edge from r(i+1) to r(i) if r(i+1) is a full
2223             # replica or ri is a partial replica.
2224             if not r_list[i+1].is_partial() or r_list[i].is_partial():
2225                 graph_list[i].add_edge_from(r_list[i+1].rep_dsa_dnstr)
2226             i = i + 1
2227
2228         # Add an edge from r|R|-1 to r0 if r|R|-1 is a full replica
2229         # or r0 is a partial replica.
2230         if not r_list[r_len-1].is_partial() or r_list[0].is_partial():
2231             graph_list[0].add_edge_from(r_list[r_len-1].rep_dsa_dnstr)
2232
2233         # Add an edge from r0 to r|R|-1 if r0 is a full replica or
2234         # r|R|-1 is a partial replica.
2235         if not r_list[0].is_partial() or r_list[r_len-1].is_partial():
2236             graph_list[r_len-1].add_edge_from(r_list[0].rep_dsa_dnstr)
2237
2238         DEBUG("r_list is length %s" % len(r_list))
2239         DEBUG('\n'.join(str((x.rep_dsa_guid, x.rep_dsa_dnstr))
2240                         for x in r_list))
2241
2242         do_dot_files = opts.dot_files and opts.debug
2243         if opts.verify or do_dot_files:
2244             dot_edges = []
2245             dot_vertices = set()
2246             for v1 in graph_list:
2247                 dot_vertices.add(v1.dsa_dnstr)
2248                 for v2 in v1.edge_from:
2249                     dot_edges.append((v2, v1.dsa_dnstr))
2250                     dot_vertices.add(v2)
2251
2252             verify_properties = ('connected', 'directed_double_ring_or_small')
2253             verify_and_dot('intrasite_pre_ntdscon', dot_edges, dot_vertices,
2254                            label='%s__%s__%s' % (site_local.site_dnstr,
2255                                                  nctype_lut[nc_x.nc_type],
2256                                                  nc_x.nc_dnstr),
2257                            properties=verify_properties, debug=DEBUG,
2258                            verify=opts.verify,
2259                            dot_files=do_dot_files, directed=True)
2260
2261         # For each existing nTDSConnection object implying an edge
2262         # from rj of R to ri such that j != i, an edge from rj to ri
2263         # is not already in the graph, and the total edges directed
2264         # to ri is less than n+2, the KCC adds that edge to the graph.
2265         for vertex in graph_list:
2266             dsa = self.my_site.dsa_table[vertex.dsa_dnstr]
2267             for connect in dsa.connect_table.values():
2268                 remote = connect.from_dnstr
2269                 if remote in self.my_site.dsa_table:
2270                     vertex.add_edge_from(remote)
2271
2272         DEBUG('reps are:  %s' % '   '.join(x.rep_dsa_dnstr for x in r_list))
2273         DEBUG('dsas are:  %s' % '   '.join(x.dsa_dnstr for x in graph_list))
2274
2275         for tnode in graph_list:
2276             # To optimize replication latency in sites with many NC
2277             # replicas, the KCC adds new edges directed to ri to bring
2278             # the total edges to n+2, where the NC replica rk of R
2279             # from which the edge is directed is chosen at random such
2280             # that k != i and an edge from rk to ri is not already in
2281             # the graph.
2282             #
2283             # Note that the KCC tech ref does not give a number for
2284             # the definition of "sites with many NC replicas". At a
2285             # bare minimum to satisfy n+2 edges directed at a node we
2286             # have to have at least three replicas in |R| (i.e. if n
2287             # is zero then at least replicas from two other graph
2288             # nodes may direct edges to us).
2289             if r_len >= 3 and not tnode.has_sufficient_edges():
2290                 candidates = [x for x in graph_list if
2291                               (x is not tnode and
2292                                x.dsa_dnstr not in tnode.edge_from)]
2293
2294                 DEBUG_BLUE("looking for random link for %s. r_len %d, "
2295                            "graph len %d candidates %d"
2296                            % (tnode.dsa_dnstr, r_len, len(graph_list),
2297                               len(candidates)))
2298
2299                 DEBUG("candidates %s" % [x.dsa_dnstr for x in candidates])
2300
2301                 while candidates and not tnode.has_sufficient_edges():
2302                     other = random.choice(candidates)
2303                     DEBUG("trying to add candidate %s" % other.dsa_dstr)
2304                     if not tnode.add_edge_from(other):
2305                         DEBUG_RED("could not add %s" % other.dsa_dstr)
2306                     candidates.remove(other)
2307             else:
2308                 DEBUG_FN("not adding links to %s: nodes %s, links is %s/%s" %
2309                          (tnode.dsa_dnstr, r_len, len(tnode.edge_from),
2310                           tnode.max_edges))
2311
2312             # Print the graph node in debug mode
2313             logger.debug("%s" % tnode)
2314
2315             # For each edge directed to the local DC, ensure a nTDSConnection
2316             # points to us that satisfies the KCC criteria
2317
2318             if tnode.dsa_dnstr == dc_local.dsa_dnstr:
2319                 tnode.add_connections_from_edges(dc_local)
2320
2321         if opts.verify or do_dot_files:
2322             dot_edges = []
2323             dot_vertices = set()
2324             for v1 in graph_list:
2325                 dot_vertices.add(v1.dsa_dnstr)
2326                 for v2 in v1.edge_from:
2327                     dot_edges.append((v2, v1.dsa_dnstr))
2328                     dot_vertices.add(v2)
2329
2330             verify_properties = ('connected', 'directed_double_ring_or_small')
2331             verify_and_dot('intrasite_post_ntdscon', dot_edges, dot_vertices,
2332                            label='%s__%s__%s' % (site_local.site_dnstr,
2333                                                  nctype_lut[nc_x.nc_type],
2334                                                  nc_x.nc_dnstr),
2335                            properties=verify_properties, debug=DEBUG,
2336                            verify=opts.verify,
2337                            dot_files=do_dot_files, directed=True)
2338
2339     def intrasite(self):
2340         """The head method for generating the intra-site KCC replica
2341         connection graph and attendant nTDSConnection objects
2342         in the samdb
2343         """
2344         # Retrieve my DSA
2345         mydsa = self.my_dsa
2346
2347         logger.debug("intrasite(): enter")
2348
2349         # Test whether local site has topology disabled
2350         mysite = self.my_site
2351         if mysite.is_intrasite_topology_disabled():
2352             return
2353
2354         detect_stale = (not mysite.is_detect_stale_disabled())
2355         for connect in mydsa.connect_table.values():
2356             if connect.to_be_added:
2357                 DEBUG_CYAN("TO BE ADDED:\n%s" % connect)
2358
2359         # Loop thru all the partitions, with gc_only False
2360         for partdn, part in self.part_table.items():
2361             self.construct_intrasite_graph(mysite, mydsa, part, False,
2362                                            detect_stale)
2363             for connect in mydsa.connect_table.values():
2364                 if connect.to_be_added:
2365                     DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2366
2367         # If the DC is a GC server, the KCC constructs an additional NC
2368         # replica graph (and creates nTDSConnection objects) for the
2369         # config NC as above, except that only NC replicas that "are present"
2370         # on GC servers are added to R.
2371         for connect in mydsa.connect_table.values():
2372             if connect.to_be_added:
2373                 DEBUG_YELLOW("TO BE ADDED:\n%s" % connect)
2374
2375         # Do it again, with gc_only True
2376         for partdn, part in self.part_table.items():
2377             if part.is_config():
2378                 self.construct_intrasite_graph(mysite, mydsa, part, True,
2379                                                detect_stale)
2380
2381         # The DC repeats the NC replica graph computation and nTDSConnection
2382         # creation for each of the NC replica graphs, this time assuming
2383         # that no DC has failed. It does so by re-executing the steps as
2384         # if the bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED were
2385         # set in the options attribute of the site settings object for
2386         # the local DC's site.  (ie. we set "detec_stale" flag to False)
2387         for connect in mydsa.connect_table.values():
2388             if connect.to_be_added:
2389                 DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2390
2391         # Loop thru all the partitions.
2392         for partdn, part in self.part_table.items():
2393             self.construct_intrasite_graph(mysite, mydsa, part, False,
2394                                            False)  # don't detect stale
2395
2396         # If the DC is a GC server, the KCC constructs an additional NC
2397         # replica graph (and creates nTDSConnection objects) for the
2398         # config NC as above, except that only NC replicas that "are present"
2399         # on GC servers are added to R.
2400         for connect in mydsa.connect_table.values():
2401             if connect.to_be_added:
2402                 DEBUG_RED("TO BE ADDED:\n%s" % connect)
2403
2404         for partdn, part in self.part_table.items():
2405             if part.is_config():
2406                 self.construct_intrasite_graph(mysite, mydsa, part, True,
2407                                                False)  # don't detect stale
2408
2409         if opts.readonly:
2410             # Display any to be added or modified repsFrom
2411             for connect in mydsa.connect_table.values():
2412                 if connect.to_be_deleted:
2413                     logger.info("TO BE DELETED:\n%s" % connect)
2414                 if connect.to_be_modified:
2415                     logger.info("TO BE MODIFIED:\n%s" % connect)
2416                 if connect.to_be_added:
2417                     DEBUG_GREEN("TO BE ADDED:\n%s" % connect)
2418
2419             mydsa.commit_connections(self.samdb, ro=True)
2420         else:
2421             # Commit any newly created connections to the samdb
2422             mydsa.commit_connections(self.samdb)
2423
2424     def list_dsas(self):
2425         self.load_my_site()
2426         self.load_my_dsa()
2427
2428         self.load_all_sites()
2429         self.load_all_partitions()
2430         self.load_all_transports()
2431         self.load_all_sitelinks()
2432         dsas = []
2433         for site in self.site_table.values():
2434             dsas.extend([dsa.dsa_dnstr.replace('CN=NTDS Settings,', '', 1)
2435                          for dsa in site.dsa_table.values()])
2436         return dsas
2437
2438     def load_samdb(self, dburl, lp, creds):
2439         self.samdb = SamDB(url=dburl,
2440                            session_info=system_session(),
2441                            credentials=creds, lp=lp)
2442
2443     def plot_all_connections(self, basename, verify_properties=()):
2444         verify = verify_properties and opts.verify
2445         plot = opts.dot_files
2446         if not (verify or plot):
2447             return
2448
2449         dot_edges = []
2450         dot_vertices = []
2451         edge_colours = []
2452         vertex_colours = []
2453
2454         for dsa in self.dsa_by_dnstr.values():
2455             dot_vertices.append(dsa.dsa_dnstr)
2456             if dsa.is_ro():
2457                 vertex_colours.append('#cc0000')
2458             else:
2459                 vertex_colours.append('#0000cc')
2460             for con in dsa.connect_table.values():
2461                 if con.is_rodc_topology():
2462                     edge_colours.append('red')
2463                 else:
2464                     edge_colours.append('blue')
2465                 dot_edges.append((con.from_dnstr, dsa.dsa_dnstr))
2466
2467         verify_and_dot(basename, dot_edges, vertices=dot_vertices,
2468                        label=self.my_dsa_dnstr, properties=verify_properties,
2469                        debug=DEBUG, verify=verify, dot_files=plot,
2470                        directed=True, edge_colors=edge_colours,
2471                        vertex_colors=vertex_colours)
2472
2473     def run(self, dburl, lp, creds, forced_local_dsa=None,
2474             forget_local_links=False, forget_intersite_links=False):
2475         """Method to perform a complete run of the KCC and
2476         produce an updated topology for subsequent NC replica
2477         syncronization between domain controllers
2478         """
2479         # We may already have a samdb setup if we are
2480         # currently importing an ldif for a test run
2481         if self.samdb is None:
2482             try:
2483                 self.load_samdb(dburl, lp, creds)
2484             except ldb.LdbError, (num, msg):
2485                 logger.error("Unable to open sam database %s : %s" %
2486                              (dburl, msg))
2487                 return 1
2488
2489         if forced_local_dsa:
2490             self.samdb.set_ntds_settings_dn("CN=NTDS Settings,%s" %
2491                                             forced_local_dsa)
2492
2493         try:
2494             # Setup
2495             self.load_my_site()
2496             self.load_my_dsa()
2497
2498             self.load_all_sites()
2499             self.load_all_partitions()
2500             self.load_all_transports()
2501             self.load_all_sitelinks()
2502
2503             if opts.verify or opts.dot_files:
2504                 guid_to_dnstr = {}
2505                 for site in self.site_table.values():
2506                     guid_to_dnstr.update((str(dsa.dsa_guid), dnstr)
2507                                          for dnstr, dsa
2508                                          in site.dsa_table.items())
2509
2510                 self.plot_all_connections('dsa_initial')
2511
2512                 dot_edges = []
2513                 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2514                 for dnstr, c_rep in current_reps.items():
2515                     DEBUG("c_rep %s" % c_rep)
2516                     dot_edges.append((self.my_dsa.dsa_dnstr, dnstr))
2517
2518                 verify_and_dot('dsa_repsFrom_initial', dot_edges,
2519                                directed=True, label=self.my_dsa_dnstr,
2520                                properties=(), debug=DEBUG, verify=opts.verify,
2521                                dot_files=opts.dot_files)
2522
2523                 dot_edges = []
2524                 for site in self.site_table.values():
2525                     for dsa in site.dsa_table.values():
2526                         current_reps, needed_reps = dsa.get_rep_tables()
2527                         for dn_str, rep in current_reps.items():
2528                             for reps_from in rep.rep_repsFrom:
2529                                 DEBUG("rep %s" % rep)
2530                                 dsa_guid = str(reps_from.source_dsa_obj_guid)
2531                                 dsa_dn = guid_to_dnstr[dsa_guid]
2532                                 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2533
2534                 verify_and_dot('dsa_repsFrom_initial_all', dot_edges,
2535                                directed=True, label=self.my_dsa_dnstr,
2536                                properties=(), debug=DEBUG, verify=opts.verify,
2537                                dot_files=opts.dot_files)
2538
2539                 dot_edges = []
2540                 for link in self.sitelink_table.values():
2541                     for a, b in itertools.combinations(link.site_list, 2):
2542                         dot_edges.append((str(a), str(b)))
2543                 properties = ('connected',)
2544                 verify_and_dot('dsa_sitelink_initial', dot_edges,
2545                                directed=False,
2546                                label=self.my_dsa_dnstr, properties=properties,
2547                                debug=DEBUG, verify=opts.verify,
2548                                dot_files=opts.dot_files)
2549
2550             if forget_local_links:
2551                 for dsa in self.my_site.dsa_table.values():
2552                     dsa.connect_table = {k: v for k, v in
2553                                          dsa.connect_table.items()
2554                                          if v.is_rodc_topology()}
2555                 self.plot_all_connections('dsa_forgotten_local')
2556
2557             if forget_intersite_links:
2558                 for site in self.site_table.values():
2559                     for dsa in site.dsa_table.values():
2560                         dsa.connect_table = {k: v for k, v in
2561                                              dsa.connect_table.items()
2562                                              if site is self.my_site and
2563                                              v.is_rodc_topology()}
2564
2565                 self.plot_all_connections('dsa_forgotten_all')
2566             # These are the published steps (in order) for the
2567             # MS-TECH description of the KCC algorithm ([MS-ADTS] 6.2.2)
2568
2569             # Step 1
2570             self.refresh_failed_links_connections()
2571
2572             # Step 2
2573             self.intrasite()
2574
2575             # Step 3
2576             all_connected = self.intersite()
2577
2578             # Step 4
2579             self.remove_unneeded_ntdsconn(all_connected)
2580
2581             # Step 5
2582             self.translate_ntdsconn()
2583
2584             # Step 6
2585             self.remove_unneeded_failed_links_connections()
2586
2587             # Step 7
2588             self.update_rodc_connection()
2589
2590             if opts.verify or opts.dot_files:
2591                 self.plot_all_connections('dsa_final',
2592                                           ('connected', 'forest_of_rings'))
2593
2594                 DEBUG_MAGENTA("there are %d dsa guids" % len(guid_to_dnstr))
2595
2596                 dot_edges = []
2597                 edge_colors = []
2598                 my_dnstr = self.my_dsa.dsa_dnstr
2599                 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2600                 for dnstr, n_rep in needed_reps.items():
2601                     for reps_from in n_rep.rep_repsFrom:
2602                         guid_str = str(reps_from.source_dsa_obj_guid)
2603                         dot_edges.append((my_dnstr, guid_to_dnstr[guid_str]))
2604                         edge_colors.append('#' + str(n_rep.nc_guid)[:6])
2605
2606                 verify_and_dot('dsa_repsFrom_final', dot_edges, directed=True,
2607                                label=self.my_dsa_dnstr,
2608                                properties=(), debug=DEBUG, verify=opts.verify,
2609                                dot_files=opts.dot_files,
2610                                edge_colors=edge_colors)
2611
2612                 dot_edges = []
2613
2614                 for site in self.site_table.values():
2615                     for dsa in site.dsa_table.values():
2616                         current_reps, needed_reps = dsa.get_rep_tables()
2617                         for n_rep in needed_reps.values():
2618                             for reps_from in n_rep.rep_repsFrom:
2619                                 dsa_guid = str(reps_from.source_dsa_obj_guid)
2620                                 dsa_dn = guid_to_dnstr[dsa_guid]
2621                                 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2622
2623                 verify_and_dot('dsa_repsFrom_final_all', dot_edges,
2624                                directed=True, label=self.my_dsa_dnstr,
2625                                properties=(), debug=DEBUG, verify=opts.verify,
2626                                dot_files=opts.dot_files)
2627
2628         except:
2629             raise
2630
2631         return 0
2632
2633     def import_ldif(self, dburl, lp, creds, ldif_file):
2634         """Import all objects and attributes that are relevent
2635         to the KCC algorithms from a previously exported LDIF file.
2636
2637         The point of this function is to allow a programmer/debugger to
2638         import an LDIF file with non-security relevent information that
2639         was previously extracted from a DC database.  The LDIF file is used
2640         to create a temporary abbreviated database.  The KCC algorithm can
2641         then run against this abbreviated database for debug or test
2642         verification that the topology generated is computationally the
2643         same between different OSes and algorithms.
2644
2645         :param dburl: path to the temporary abbreviated db to create
2646         :param ldif_file: path to the ldif file to import
2647         """
2648         try:
2649             self.samdb = ldif_utils.ldif_to_samdb(dburl, lp, ldif_file,
2650                                                   opts.forced_local_dsa)
2651         except ldif_utils.LdifError, e:
2652             print e
2653             return 1
2654         return 0
2655
2656     def export_ldif(self, dburl, lp, creds, ldif_file):
2657         """Routine to extract all objects and attributes that are relevent
2658         to the KCC algorithms from a DC database.
2659
2660         The point of this function is to allow a programmer/debugger to
2661         extract an LDIF file with non-security relevent information from
2662         a DC database.  The LDIF file can then be used to "import" via
2663         the import_ldif() function this file into a temporary abbreviated
2664         database.  The KCC algorithm can then run against this abbreviated
2665         database for debug or test verification that the topology generated
2666         is computationally the same between different OSes and algorithms.
2667
2668         :param dburl: LDAP database URL to extract info from
2669         :param ldif_file: output LDIF file name to create
2670         """
2671         try:
2672             ldif_utils.samdb_to_ldif_file(self.samdb, dburl, lp, creds,
2673                                           ldif_file)
2674         except ldif_utils.LdifError, e:
2675             print e
2676             return 1
2677         return 0
2678
2679 ##################################################
2680 # Global Functions
2681 ##################################################
2682
2683
2684 def get_spanning_tree_edges(graph, my_site, label=None):
2685     # Phase 1: Run Dijkstra's to get a list of internal edges, which are
2686     # just the shortest-paths connecting colored vertices
2687
2688     internal_edges = set()
2689
2690     for e_set in graph.edge_set:
2691         edgeType = None
2692         for v in graph.vertices:
2693             v.edges = []
2694
2695         # All con_type in an edge set is the same
2696         for e in e_set.edges:
2697             edgeType = e.con_type
2698             for v in e.vertices:
2699                 v.edges.append(e)
2700
2701         if opts.verify or opts.dot_files:
2702             graph_edges = [(a.site.site_dnstr, b.site.site_dnstr)
2703                            for a, b in
2704                            itertools.chain(
2705                                *(itertools.combinations(edge.vertices, 2)
2706                                  for edge in e_set.edges))]
2707             graph_nodes = [v.site.site_dnstr for v in graph.vertices]
2708
2709             if opts.dot_files and opts.debug:
2710                 write_dot_file('edgeset_%s' % (edgeType,), graph_edges,
2711                                vertices=graph_nodes, label=label)
2712
2713             if opts.verify:
2714                 verify_graph('spanning tree edge set %s' % edgeType,
2715                              graph_edges, vertices=graph_nodes,
2716                              properties=('complete', 'connected'),
2717                              debug=DEBUG)
2718
2719         # Run dijkstra's algorithm with just the red vertices as seeds
2720         # Seed from the full replicas
2721         dijkstra(graph, edgeType, False)
2722
2723         # Process edge set
2724         process_edge_set(graph, e_set, internal_edges)
2725
2726         # Run dijkstra's algorithm with red and black vertices as the seeds
2727         # Seed from both full and partial replicas
2728         dijkstra(graph, edgeType, True)
2729
2730         # Process edge set
2731         process_edge_set(graph, e_set, internal_edges)
2732
2733     # All vertices have root/component as itself
2734     setup_vertices(graph)
2735     process_edge_set(graph, None, internal_edges)
2736
2737     if opts.verify or opts.dot_files:
2738         graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
2739                        for e in internal_edges]
2740         graph_nodes = [v.site.site_dnstr for v in graph.vertices]
2741         verify_properties = ('multi_edge_forest',)
2742         verify_and_dot('prekruskal', graph_edges, graph_nodes, label=label,
2743                        properties=verify_properties, debug=DEBUG,
2744                        verify=opts.verify,
2745                        dot_files=opts.dot_files)
2746
2747     # Phase 2: Run Kruskal's on the internal edges
2748     output_edges, components = kruskal(graph, internal_edges)
2749
2750     # This recalculates the cost for the path connecting the
2751     # closest red vertex. Ignoring types is fine because NO
2752     # suboptimal edge should exist in the graph
2753     dijkstra(graph, "EDGE_TYPE_ALL", False)  # TODO rename
2754     # Phase 3: Process the output
2755     for v in graph.vertices:
2756         if v.is_red():
2757             v.dist_to_red = 0
2758         else:
2759             v.dist_to_red = v.repl_info.cost
2760
2761     if opts.verify or opts.dot_files:
2762         graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
2763                        for e in internal_edges]
2764         graph_nodes = [v.site.site_dnstr for v in graph.vertices]
2765         verify_properties = ('multi_edge_forest',)
2766         verify_and_dot('postkruskal', graph_edges, graph_nodes,
2767                        label=label, properties=verify_properties,
2768                        debug=DEBUG, verify=opts.verify,
2769                        dot_files=opts.dot_files)
2770
2771     # Ensure only one-way connections for partial-replicas,
2772     # and make sure they point the right way.
2773     edge_list = []
2774     for edge in output_edges:
2775         # We know these edges only have two endpoints because we made
2776         # them.
2777         v, w = edge.vertices
2778         if v.site is my_site or w.site is my_site:
2779             if (((v.is_black() or w.is_black()) and
2780                  v.dist_to_red != MAX_DWORD)):
2781                 edge.directed = True
2782
2783                 if w.dist_to_red < v.dist_to_red:
2784                     edge.vertices[:] = w, v
2785             edge_list.append(edge)
2786
2787     if opts.verify or opts.dot_files:
2788         graph_edges = [[x.site.site_dnstr for x in e.vertices]
2789                        for e in edge_list]
2790         #add the reverse edge if not directed.
2791         graph_edges.extend([x.site.site_dnstr
2792                             for x in reversed(e.vertices)]
2793                            for e in edge_list if not e.directed)
2794         graph_nodes = [x.site.site_dnstr for x in graph.vertices]
2795         verify_properties = ()
2796         verify_and_dot('post-one-way-partial', graph_edges, graph_nodes,
2797                        label=label, properties=verify_properties,
2798                        debug=DEBUG, verify=opts.verify,
2799                        directed=True,
2800                        dot_files=opts.dot_files)
2801
2802     # count the components
2803     return edge_list, components
2804
2805
2806 def sort_replica_by_dsa_guid(rep1, rep2):
2807     """Helper to sort NCReplicas by their DSA guids
2808
2809     The guids need to be sorted in their NDR form.
2810
2811     :param rep1: An NC replica
2812     :param rep2: Another replica
2813     :return: -1, 0, or 1, indicating sort order.
2814     """
2815     return cmp(ndr_pack(rep1.rep_dsa_guid), ndr_pack(rep2.rep_dsa_guid))
2816
2817
2818 def sort_dsa_by_gc_and_guid(dsa1, dsa2):
2819     """Helper to sort DSAs by guid global catalog status
2820
2821     GC DSAs come before non-GC DSAs, other than that, the guids are
2822     sorted in NDR form.
2823
2824     :param dsa1: A DSA object
2825     :param dsa2: Another DSA
2826     :return: -1, 0, or 1, indicating sort order.
2827     """
2828     if dsa1.is_gc() and not dsa2.is_gc():
2829         return -1
2830     if not dsa1.is_gc() and dsa2.is_gc():
2831         return +1
2832     return cmp(ndr_pack(dsa1.dsa_guid), ndr_pack(dsa2.dsa_guid))
2833
2834
2835 def is_smtp_replication_available():
2836     """Can the KCC use SMTP replication?
2837
2838     Currently always returns false because Samba doesn't implement
2839     SMTP transfer for NC changes between DCs.
2840
2841     :return: Boolean (always False)
2842     """
2843     return False
2844
2845
2846 def create_edge(con_type, site_link, guid_to_vertex):
2847     e = MultiEdge()
2848     e.site_link = site_link
2849     e.vertices = []
2850     for site_guid in site_link.site_list:
2851         if str(site_guid) in guid_to_vertex:
2852             e.vertices.extend(guid_to_vertex.get(str(site_guid)))
2853     e.repl_info.cost = site_link.cost
2854     e.repl_info.options = site_link.options
2855     e.repl_info.interval = site_link.interval
2856     e.repl_info.schedule = convert_schedule_to_repltimes(site_link.schedule)
2857     e.con_type = con_type
2858     e.directed = False
2859     return e
2860
2861
2862 def create_auto_edge_set(graph, transport):
2863     e_set = MultiEdgeSet()
2864     # use a NULL guid, not associated with a SiteLinkBridge object
2865     e_set.guid = misc.GUID()
2866     for site_link in graph.edges:
2867         if site_link.con_type == transport:
2868             e_set.edges.append(site_link)
2869
2870     return e_set
2871
2872
2873 def create_edge_set(graph, transport, site_link_bridge):
2874     # TODO not implemented - need to store all site link bridges
2875     e_set = MultiEdgeSet()
2876     # e_set.guid = site_link_bridge
2877     return e_set
2878
2879
2880 def setup_vertices(graph):
2881     for v in graph.vertices:
2882         if v.is_white():
2883             v.repl_info.cost = MAX_DWORD
2884             v.root = None
2885             v.component_id = None
2886         else:
2887             v.repl_info.cost = 0
2888             v.root = v
2889             v.component_id = v
2890
2891         v.repl_info.interval = 0
2892         v.repl_info.options = 0xFFFFFFFF
2893         v.repl_info.schedule = None  # TODO highly suspicious
2894         v.demoted = False
2895
2896
2897 def dijkstra(graph, edge_type, include_black):
2898     queue = []
2899     setup_dijkstra(graph, edge_type, include_black, queue)
2900     while len(queue) > 0:
2901         cost, guid, vertex = heapq.heappop(queue)
2902         for edge in vertex.edges:
2903             for v in edge.vertices:
2904                 if v is not vertex:
2905                     # add new path from vertex to v
2906                     try_new_path(graph, queue, vertex, edge, v)
2907
2908
2909 def setup_dijkstra(graph, edge_type, include_black, queue):
2910     setup_vertices(graph)
2911     for vertex in graph.vertices:
2912         if vertex.is_white():
2913             continue
2914
2915         if (((vertex.is_black() and not include_black)
2916              or edge_type not in vertex.accept_black
2917              or edge_type not in vertex.accept_red_red)):
2918             vertex.repl_info.cost = MAX_DWORD
2919             vertex.root = None  # NULL GUID
2920             vertex.demoted = True  # Demoted appears not to be used
2921         else:
2922             heapq.heappush(queue, (vertex.repl_info.cost, vertex.guid, vertex))
2923
2924
2925 def try_new_path(graph, queue, vfrom, edge, vto):
2926     newRI = ReplInfo()
2927     # What this function checks is that there is a valid time frame for
2928     # which replication can actually occur, despite being adequately
2929     # connected
2930     intersect = combine_repl_info(vfrom.repl_info, edge.repl_info, newRI)
2931
2932     # If the new path costs more than the current, then ignore the edge
2933     if newRI.cost > vto.repl_info.cost:
2934         return
2935
2936     if newRI.cost < vto.repl_info.cost and not intersect:
2937         return
2938
2939     new_duration = total_schedule(newRI.schedule)
2940     old_duration = total_schedule(vto.repl_info.schedule)
2941
2942     # Cheaper or longer schedule
2943     if newRI.cost < vto.repl_info.cost or new_duration > old_duration:
2944         vto.root = vfrom.root
2945         vto.component_id = vfrom.component_id
2946         vto.repl_info = newRI
2947         heapq.heappush(queue, (vto.repl_info.cost, vto.guid, vto))
2948
2949
2950 def check_demote_vertex(vertex, edge_type):
2951     if vertex.is_white():
2952         return
2953
2954     # Accepts neither red-red nor black edges, demote
2955     if ((edge_type not in vertex.accept_black and
2956          edge_type not in vertex.accept_red_red)):
2957         vertex.repl_info.cost = MAX_DWORD
2958         vertex.root = None
2959         vertex.demoted = True  # Demoted appears not to be used
2960
2961
2962 def undemote_vertex(vertex):
2963     if vertex.is_white():
2964         return
2965
2966     vertex.repl_info.cost = 0
2967     vertex.root = vertex
2968     vertex.demoted = False
2969
2970
2971 def process_edge_set(graph, e_set, internal_edges):
2972     if e_set is None:
2973         for edge in graph.edges:
2974             for vertex in edge.vertices:
2975                 check_demote_vertex(vertex, edge.con_type)
2976             process_edge(graph, edge, internal_edges)
2977             for vertex in edge.vertices:
2978                 undemote_vertex(vertex)
2979     else:
2980         for edge in e_set.edges:
2981             process_edge(graph, edge, internal_edges)
2982
2983
2984 def process_edge(graph, examine, internal_edges):
2985     # Find the set of all vertices touches the edge to examine
2986     vertices = []
2987     for v in examine.vertices:
2988         # Append a 4-tuple of color, repl cost, guid and vertex
2989         vertices.append((v.color, v.repl_info.cost, v.ndrpacked_guid, v))
2990     # Sort by color, lower
2991     DEBUG("vertices is %s" % vertices)
2992     vertices.sort()
2993
2994     color, cost, guid, bestv = vertices[0]
2995     # Add to internal edges an edge from every colored vertex to bestV
2996     for v in examine.vertices:
2997         if v.component_id is None or v.root is None:
2998             continue
2999
3000         # Only add edge if valid inter-tree edge - needs a root and
3001         # different components
3002         if ((bestv.component_id is not None and
3003              bestv.root is not None and
3004              v.component_id is not None and
3005              v.root is not None and
3006              bestv.component_id != v.component_id)):
3007             add_int_edge(graph, internal_edges, examine, bestv, v)
3008
3009
3010 # Add internal edge, endpoints are roots of the vertices to pass in
3011 # and are always colored
3012 def add_int_edge(graph, internal_edges, examine, v1, v2):
3013     root1 = v1.root
3014     root2 = v2.root
3015
3016     red_red = False
3017     if root1.is_red() and root2.is_red():
3018         red_red = True
3019
3020     if red_red:
3021         if ((examine.con_type not in root1.accept_red_red
3022              or examine.con_type not in root2.accept_red_red)):
3023             return
3024     elif (examine.con_type not in root1.accept_black
3025           or examine.con_type not in root2.accept_black):
3026         return
3027
3028     ri = ReplInfo()
3029     ri2 = ReplInfo()
3030
3031     # Create the transitive replInfo for the two trees and this edge
3032     if not combine_repl_info(v1.repl_info, v2.repl_info, ri):
3033         return
3034     # ri is now initialized
3035     if not combine_repl_info(ri, examine.repl_info, ri2):
3036         return
3037
3038     newIntEdge = InternalEdge(root1, root2, red_red, ri2, examine.con_type,
3039                               examine.site_link)
3040     # Order by vertex guid
3041     #XXX guid comparison using ndr_pack
3042     if newIntEdge.v1.ndrpacked_guid > newIntEdge.v2.ndrpacked_guid:
3043         newIntEdge.v1 = root2
3044         newIntEdge.v2 = root1
3045
3046     internal_edges.add(newIntEdge)
3047
3048
3049 def kruskal(graph, edges):
3050     for v in graph.vertices:
3051         v.edges = []
3052
3053     components = set([x for x in graph.vertices if not x.is_white()])
3054     edges = list(edges)
3055
3056     # Sorted based on internal comparison function of internal edge
3057     edges.sort()
3058
3059     #XXX expected_num_tree_edges is never used
3060     expected_num_tree_edges = 0  # TODO this value makes little sense
3061
3062     count_edges = 0
3063     output_edges = []
3064     index = 0
3065     while index < len(edges):  # TODO and num_components > 1
3066         e = edges[index]
3067         parent1 = find_component(e.v1)
3068         parent2 = find_component(e.v2)
3069         if parent1 is not parent2:
3070             count_edges += 1
3071             add_out_edge(graph, output_edges, e)
3072             parent1.component_id = parent2
3073             components.discard(parent1)
3074
3075         index += 1
3076
3077     return output_edges, len(components)
3078
3079
3080 def find_component(vertex):
3081     if vertex.component_id is vertex:
3082         return vertex
3083
3084     current = vertex
3085     while current.component_id is not current:
3086         current = current.component_id
3087
3088     root = current
3089     current = vertex
3090     while current.component_id is not root:
3091         n = current.component_id
3092         current.component_id = root
3093         current = n
3094
3095     return root
3096
3097
3098 def add_out_edge(graph, output_edges, e):
3099     v1 = e.v1
3100     v2 = e.v2
3101
3102     # This multi-edge is a 'real' edge with no GUID
3103     ee = MultiEdge()
3104     ee.directed = False
3105     ee.site_link = e.site_link
3106     ee.vertices.append(v1)
3107     ee.vertices.append(v2)
3108     ee.con_type = e.e_type
3109     ee.repl_info = e.repl_info
3110     output_edges.append(ee)
3111
3112     v1.edges.append(ee)
3113     v2.edges.append(ee)
3114
3115
3116 def test_all_reps_from(lp, creds, rng_seed=None):
3117     kcc = KCC()
3118     kcc.load_samdb(opts.dburl, lp, creds)
3119     dsas = kcc.list_dsas()
3120     needed_parts = {}
3121     current_parts = {}
3122
3123     guid_to_dnstr = {}
3124     for site in kcc.site_table.values():
3125         guid_to_dnstr.update((str(dsa.dsa_guid), dnstr)
3126                              for dnstr, dsa in site.dsa_table.items())
3127
3128     dot_edges = []
3129     dot_vertices = []
3130     colours = []
3131     vertex_colours = []
3132
3133     for dsa_dn in dsas:
3134         if rng_seed:
3135             random.seed(rng_seed)
3136         kcc = KCC()
3137         kcc.run(opts.dburl, lp, creds, forced_local_dsa=dsa_dn,
3138                 forget_local_links=opts.forget_local_links,
3139                 forget_intersite_links=opts.forget_intersite_links)
3140
3141         current, needed = kcc.my_dsa.get_rep_tables()
3142
3143         for dsa in kcc.my_site.dsa_table.values():
3144             if dsa is kcc.my_dsa:
3145                 continue
3146             kcc.translate_ntdsconn(dsa)
3147             c, n = dsa.get_rep_tables()
3148             current.update(c)
3149             needed.update(n)
3150
3151         for name, rep_table, rep_parts in (
3152                 ('needed', needed, needed_parts),
3153                 ('current', current, current_parts)):
3154             for part, nc_rep in rep_table.items():
3155                 edges = rep_parts.setdefault(part, [])
3156                 for reps_from in nc_rep.rep_repsFrom:
3157                     source = guid_to_dnstr[str(reps_from.source_dsa_obj_guid)]
3158                     dest = guid_to_dnstr[str(nc_rep.rep_dsa_guid)]
3159                     edges.append((source, dest))
3160
3161         for site in kcc.site_table.values():
3162             for dsa in site.dsa_table.values():
3163                 if dsa.is_ro():
3164                     vertex_colours.append('#cc0000')
3165                 else:
3166                     vertex_colours.append('#0000cc')
3167                 dot_vertices.append(dsa.dsa_dnstr)
3168                 if dsa.connect_table:
3169                     DEBUG_FN("DSA %s %s connections:\n%s" %
3170                              (dsa.dsa_dnstr, len(dsa.connect_table),
3171                               [x.from_dnstr for x in
3172                                dsa.connect_table.values()]))
3173                 for con in dsa.connect_table.values():
3174                     if con.is_rodc_topology():
3175                         colours.append('red')
3176                     else:
3177                         colours.append('blue')
3178                     dot_edges.append((con.from_dnstr, dsa.dsa_dnstr))
3179
3180     verify_and_dot('all-dsa-connections', dot_edges, vertices=dot_vertices,
3181                    label="all dsa NTDSConnections", properties=(),
3182                    debug=DEBUG, verify=opts.verify, dot_files=opts.dot_files,
3183                    directed=True, edge_colors=colours,
3184                    vertex_colors=vertex_colours)
3185
3186     for name, rep_parts in (('needed', needed_parts),
3187                             ('current', current_parts)):
3188         for part, edges in rep_parts.items():
3189             verify_and_dot('all-repsFrom_%s__%s' % (name, part), edges,
3190                            directed=True, label=part,
3191                            properties=(), debug=DEBUG, verify=opts.verify,
3192                            dot_files=opts.dot_files)
3193
3194
3195 logger = logging.getLogger("samba_kcc")
3196 logger.addHandler(logging.StreamHandler(sys.stdout))
3197 DEBUG = logger.debug
3198
3199
3200 def _color_debug(*args, **kwargs):
3201     DEBUG('%s%s%s' % (kwargs['color'], args[0], C_NORMAL), *args[1:])
3202
3203 _globals = globals()
3204 for _color in ('DARK_RED', 'RED', 'DARK_GREEN', 'GREEN', 'YELLOW',
3205                'DARK_YELLOW', 'DARK_BLUE', 'BLUE', 'PURPLE', 'MAGENTA',
3206                'DARK_CYAN', 'CYAN', 'GREY', 'WHITE', 'REV_RED'):
3207     _globals['DEBUG_' + _color] = partial(_color_debug, color=_globals[_color])
3208
3209
3210 def DEBUG_FN(msg=''):
3211     import traceback
3212     filename, lineno, function, text = traceback.extract_stack(None, 2)[0]
3213     DEBUG("%s%s:%s%s %s%s()%s '%s'" % (CYAN, filename, BLUE, lineno,
3214                                        CYAN, function, C_NORMAL, msg))
3215
3216
3217 ##################################################
3218 # samba_kcc entry point
3219 ##################################################
3220
3221 parser = optparse.OptionParser("samba_kcc [options]")
3222 sambaopts = options.SambaOptions(parser)
3223 credopts = options.CredentialsOptions(parser)
3224
3225 parser.add_option_group(sambaopts)
3226 parser.add_option_group(credopts)
3227 parser.add_option_group(options.VersionOptions(parser))
3228
3229 parser.add_option("--readonly", default=False,
3230                   help="compute topology but do not update database",
3231                   action="store_true")
3232
3233 parser.add_option("--debug",
3234                   help="debug output",
3235                   action="store_true")
3236
3237 parser.add_option("--verify",
3238                   help="verify that assorted invariants are kept",
3239                   action="store_true")
3240
3241 parser.add_option("--list-verify-tests",
3242                   help=("list what verification actions are available "
3243                         "and do nothing else"),
3244                   action="store_true")
3245
3246 parser.add_option("--no-dot-files", dest='dot_files',
3247                   help="Don't write dot graph files in /tmp",
3248                   default=True, action="store_false")
3249
3250 parser.add_option("--seed",
3251                   help="random number seed",
3252                   type=int)
3253
3254 parser.add_option("--importldif",
3255                   help="import topology ldif file",
3256                   type=str, metavar="<file>")
3257
3258 parser.add_option("--exportldif",
3259                   help="export topology ldif file",
3260                   type=str, metavar="<file>")
3261
3262 parser.add_option("-H", "--URL",
3263                   help="LDB URL for database or target server",
3264                   type=str, metavar="<URL>", dest="dburl")
3265
3266 parser.add_option("--tmpdb",
3267                   help="schemaless database file to create for ldif import",
3268                   type=str, metavar="<file>")
3269
3270 parser.add_option("--now",
3271                   help=("assume current time is this ('YYYYmmddHHMMSS[tz]',"
3272                         " default: system time)"),
3273                   type=str, metavar="<date>")
3274
3275 parser.add_option("--forced-local-dsa",
3276                   help="run calculations assuming the DSA is this DN",
3277                   type=str, metavar="<DSA>")
3278
3279 parser.add_option("--attempt-live-connections", default=False,
3280                   help="Attempt to connect to other DSAs to test links",
3281                   action="store_true")
3282
3283 parser.add_option("--list-valid-dsas", default=False,
3284                   help=("Print a list of DSA dnstrs that could be"
3285                         " used in --forced-local-dsa"),
3286                   action="store_true")
3287
3288 parser.add_option("--test-all-reps-from", default=False,
3289                   help="Create and verify a graph of reps-from for every DSA",
3290                   action="store_true")
3291
3292 parser.add_option("--forget-local-links", default=False,
3293                   help="pretend not to know the existing local topology",
3294                   action="store_true")
3295
3296 parser.add_option("--forget-intersite-links", default=False,
3297                   help="pretend not to know the existing intersite topology",
3298                   action="store_true")
3299
3300
3301 opts, args = parser.parse_args()
3302
3303
3304 if opts.list_verify_tests:
3305     list_verify_tests()
3306     sys.exit(0)
3307
3308 if opts.debug:
3309     logger.setLevel(logging.DEBUG)
3310 elif opts.readonly:
3311     logger.setLevel(logging.INFO)
3312 else:
3313     logger.setLevel(logging.WARNING)
3314
3315 # initialize seed from optional input parameter
3316 if opts.seed:
3317     random.seed(opts.seed)
3318 else:
3319     random.seed(0xACE5CA11)
3320
3321 if opts.now:
3322     for timeformat in ("%Y%m%d%H%M%S%Z", "%Y%m%d%H%M%S"):
3323         try:
3324             now_tuple = time.strptime(opts.now, timeformat)
3325             break
3326         except ValueError:
3327             pass
3328     else:
3329         # else happens if break doesn't --> no match
3330         print >> sys.stderr, "could not parse time '%s'" % opts.now
3331         sys.exit(1)
3332
3333     unix_now = int(time.mktime(now_tuple))
3334 else:
3335     unix_now = int(time.time())
3336
3337 nt_now = unix2nttime(unix_now)
3338
3339 lp = sambaopts.get_loadparm()
3340 creds = credopts.get_credentials(lp, fallback_machine=True)
3341
3342 if opts.dburl is None:
3343     opts.dburl = lp.samdb_url()
3344
3345 if opts.test_all_reps_from:
3346     opts.readonly = True
3347     rng_seed = opts.seed or 0xACE5CA11
3348     test_all_reps_from(lp, creds, rng_seed=rng_seed)
3349     sys.exit()
3350
3351 # Instantiate Knowledge Consistency Checker and perform run
3352 kcc = KCC()
3353
3354 if opts.exportldif:
3355     rc = kcc.export_ldif(opts.dburl, lp, creds, opts.exportldif)
3356     sys.exit(rc)
3357
3358 if opts.importldif:
3359     if opts.tmpdb is None or opts.tmpdb.startswith('ldap'):
3360         logger.error("Specify a target temp database file with --tmpdb option")
3361         sys.exit(1)
3362
3363     rc = kcc.import_ldif(opts.tmpdb, lp, creds, opts.importldif)
3364     if rc != 0:
3365         sys.exit(rc)
3366
3367 if opts.list_valid_dsas:
3368     kcc.load_samdb(opts.dburl, lp, creds)
3369     print '\n'.join(kcc.list_dsas())
3370     sys.exit()
3371
3372 try:
3373     rc = kcc.run(opts.dburl, lp, creds, opts.forced_local_dsa,
3374                  opts.forget_local_links, opts.forget_intersite_links)
3375     sys.exit(rc)
3376
3377 except GraphError, e:
3378     print e
3379     sys.exit(1)