3 # Compute our KCC topology
5 # Copyright (C) Dave Craft 2011
6 # Copyright (C) Andrew Bartlett 2015
8 # Andrew Bartlett's alleged work performed by his underlings Douglas
9 # Bagnall and Garming Sam.
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.
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.
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/>.
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'
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
37 os.environ["TZ"] = "GMT"
39 # Find right directory when running from source tree
40 sys.path.insert(0, "bin/python")
47 from functools import partial
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
64 """The Knowledge Consistency Checker class.
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
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
77 """Initializes the partitions class which can hold
78 our local DCs partitions or all the partitions in
81 self.part_table = {} # partition objects
83 self.transport_table = {}
84 self.ip_transport = None
85 self.sitelink_table = {}
86 self.dsa_by_dnstr = {}
89 self.get_dsa_by_guidstr = self.dsa_by_guid.get
90 self.get_dsa = self.dsa_by_dnstr.get
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()
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()
103 self.my_dsa_dnstr = None # My dsa DN
104 self.my_dsa = None # My dsa object
106 self.my_site_dnstr = None
111 def load_all_transports(self):
112 """Loads the inter-site transport objects for Sites
115 :raise KCCError: if no IP transport is found
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)" %
129 transport = Transport(dnstr)
131 transport.load_transport(self.samdb)
132 self.transport_table.setdefault(str(transport.guid),
134 if transport.name == 'IP':
135 self.ip_transport = transport
137 if self.ip_transport is None:
138 raise KCCError("there doesn't seem to be an IP transport")
140 def load_all_sitelinks(self):
141 """Loads the inter-site siteLink objects
143 ::returns: Raises KCCError on error
146 res = self.samdb.search("CN=Inter-Site Transports,CN=Sites,%s" %
147 self.samdb.get_config_basedn(),
148 scope=ldb.SCOPE_SUBTREE,
149 expression="(objectClass=siteLink)")
150 except ldb.LdbError, (enum, estr):
151 raise KCCError("Unable to find inter-site siteLinks - (%s)" % estr)
157 if dnstr in self.sitelink_table:
160 sitelink = SiteLink(dnstr)
162 sitelink.load_sitelink(self.samdb)
164 # Assign this siteLink to table
166 self.sitelink_table[dnstr] = sitelink
168 def load_site(self, dn_str):
169 """Helper for load_my_site and load_all_sites. It puts all the site's
170 DSAs into the KCC indices.
172 site = Site(dn_str, unix_now)
173 site.load_site(self.samdb)
175 # I am not sure why, but we avoid replacing the site with an
177 guid = str(site.site_guid)
178 if guid not in self.site_table:
179 self.site_table[guid] = site
180 self.dsa_by_dnstr.update(site.dsa_table)
181 self.dsa_by_guid.update((str(x.dsa_guid), x)
182 for x in site.dsa_table.values())
184 return self.site_table[guid]
186 def load_my_site(self):
187 """Loads the Site class for the local DSA
189 ::returns: Raises an Exception on error
191 self.my_site_dnstr = ("CN=%s,CN=Sites,%s" % (
192 self.samdb.server_site_name(),
193 self.samdb.get_config_basedn()))
195 self.my_site = self.load_site(self.my_site_dnstr)
197 def load_all_sites(self):
198 """Discover all sites and instantiate and load each
201 ::returns: Raises KCCError on error
204 res = self.samdb.search("CN=Sites,%s" %
205 self.samdb.get_config_basedn(),
206 scope=ldb.SCOPE_SUBTREE,
207 expression="(objectClass=site)")
208 except ldb.LdbError, (enum, estr):
209 raise KCCError("Unable to find sites - (%s)" % estr)
212 sitestr = str(msg.dn)
213 self.load_site(sitestr)
215 def load_my_dsa(self):
216 """Discover my nTDSDSA dn thru the rootDSE entry
218 ::returns: Raises KCCError on error.
220 dn = ldb.Dn(self.samdb, "<GUID=%s>" % self.samdb.get_ntds_GUID())
222 res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE,
223 attrs=["objectGUID"])
224 except ldb.LdbError, (enum, estr):
225 logger.warning("Search for %s failed: %s. This typically happens"
226 " in --importldif mode due to lack of module"
227 " support.", dn, estr)
229 # We work around the failure above by looking at the
230 # dsServiceName that was put in the fake rootdse by
231 # the --exportldif, rather than the
232 # samdb.get_ntds_GUID(). The disadvantage is that this
233 # mode requires we modify the @ROOTDSE dnq to support
235 service_name_res = self.samdb.search(base="",
236 scope=ldb.SCOPE_BASE,
237 attrs=["dsServiceName"])
238 dn = ldb.Dn(self.samdb,
239 service_name_res[0]["dsServiceName"][0])
241 res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE,
242 attrs=["objectGUID"])
243 except ldb.LdbError, (enum, estr):
244 raise KCCError("Unable to find my nTDSDSA - (%s)" % estr)
247 raise KCCError("Unable to find my nTDSDSA at %s" %
250 ntds_guid = misc.GUID(self.samdb.get_ntds_GUID())
251 if misc.GUID(res[0]["objectGUID"][0]) != ntds_guid:
252 raise KCCError("Did not find the GUID we expected,"
253 " perhaps due to --importldif")
255 self.my_dsa_dnstr = str(res[0].dn)
257 self.my_dsa = self.my_site.get_dsa(self.my_dsa_dnstr)
259 if self.my_dsa_dnstr not in self.dsa_by_dnstr:
260 DEBUG_DARK_YELLOW("my_dsa %s isn't in self.dsas_by_dnstr:"
261 " it must be RODC.\n"
262 "Let's add it, because my_dsa is special!\n"
263 "(likewise for self.dsa_by_guid of course)" %
266 self.dsa_by_dnstr[self.my_dsa_dnstr] = self.my_dsa
267 self.dsa_by_guid[str(self.my_dsa.dsa_guid)] = self.my_dsa
269 def load_all_partitions(self):
270 """Discover all NCs thru the Partitions dn and
271 instantiate and load the NCs.
273 Each NC is inserted into the part_table by partition
274 dn string (not the nCName dn string)
276 ::returns: Raises KCCError on error
279 res = self.samdb.search("CN=Partitions,%s" %
280 self.samdb.get_config_basedn(),
281 scope=ldb.SCOPE_SUBTREE,
282 expression="(objectClass=crossRef)")
283 except ldb.LdbError, (enum, estr):
284 raise KCCError("Unable to find partitions - (%s)" % estr)
287 partstr = str(msg.dn)
290 if partstr in self.part_table:
293 part = Partition(partstr)
295 part.load_partition(self.samdb)
296 self.part_table[partstr] = part
298 def should_be_present_test(self):
299 """Enumerate all loaded partitions and DSAs in local
300 site and test if NC should be present as replica
302 for partdn, part in self.part_table.items():
303 for dsadn, dsa in self.my_site.dsa_table.items():
304 needed, ro, partial = part.should_be_present(dsa)
305 logger.info("dsadn:%s\nncdn:%s\nneeded=%s:ro=%s:partial=%s\n" %
306 (dsadn, part.nc_dnstr, needed, ro, partial))
308 def refresh_failed_links_connections(self):
309 """Based on MS-ADTS 6.2.2.1"""
311 # Instead of NULL link with failure_count = 0, the tuple is
314 # LINKS: Refresh failed links
315 self.kcc_failed_links = {}
316 current, needed = self.my_dsa.get_rep_tables()
317 for replica in current.values():
318 # For every possible connection to replicate
319 for reps_from in replica.rep_repsFrom:
320 failure_count = reps_from.consecutive_sync_failures
321 if failure_count <= 0:
324 dsa_guid = str(reps_from.source_dsa_obj_guid)
325 time_first_failure = reps_from.last_success
326 last_result = reps_from.last_attempt
327 dns_name = reps_from.dns_name1
329 f = self.kcc_failed_links.get(dsa_guid)
331 f = KCCFailedObject(dsa_guid, failure_count,
332 time_first_failure, last_result,
334 self.kcc_failed_links[dsa_guid] = f
335 #elif f.failure_count == 0:
336 # f.failure_count = failure_count
337 # f.time_first_failure = time_first_failure
338 # f.last_result = last_result
340 f.failure_count = max(f.failure_count, failure_count)
341 f.time_first_failure = min(f.time_first_failure,
343 f.last_result = last_result
345 # CONNECTIONS: Refresh failed connections
346 restore_connections = set()
347 if opts.attempt_live_connections:
348 DEBUG("refresh_failed_links: checking if links are still down")
349 for connection in self.kcc_failed_connections:
351 drs_utils.drsuapi_connect(connection.dns_name, lp, creds)
352 # Failed connection is no longer failing
353 restore_connections.add(connection)
354 except drs_utils.drsException:
355 # Failed connection still failing
356 connection.failure_count += 1
358 DEBUG("refresh_failed_links: not checking live links because we\n"
359 "weren't asked to --attempt-live-connections")
361 # Remove the restored connections from the failed connections
362 self.kcc_failed_connections.difference_update(restore_connections)
364 def is_stale_link_connection(self, target_dsa):
365 """Returns False if no tuple z exists in the kCCFailedLinks or
366 kCCFailedConnections variables such that z.UUIDDsa is the
367 objectGUID of the target dsa, z.FailureCount > 0, and
368 the current time - z.TimeFirstFailure > 2 hours.
370 # Returns True if tuple z exists...
371 failed_link = self.kcc_failed_links.get(str(target_dsa.dsa_guid))
373 # failure_count should be > 0, but check anyways
374 if failed_link.failure_count > 0:
375 unix_first_failure = \
376 nttime2unix(failed_link.time_first_failure)
377 # TODO guard against future
378 if unix_first_failure > unix_now:
379 logger.error("The last success time attribute for \
380 repsFrom is in the future!")
382 # Perform calculation in seconds
383 if (unix_now - unix_first_failure) > 60 * 60 * 2:
390 # TODO: This should be backed by some form of local database
391 def remove_unneeded_failed_links_connections(self):
392 # Remove all tuples in kcc_failed_links where failure count = 0
393 # In this implementation, this should never happen.
395 # Remove all connections which were not used this run or connections
396 # that became active during this run.
399 def remove_unneeded_ntdsconn(self, all_connected):
400 """Removes unneeded NTDS Connections after computation
401 of KCC intra and inter-site topology has finished.
405 # Loop thru connections
406 for cn_conn in mydsa.connect_table.values():
407 if cn_conn.guid is None:
409 cn_conn.guid = misc.GUID(str(uuid.uuid4()))
410 cn_conn.whenCreated = nt_now
412 cn_conn.load_connection(self.samdb)
414 for cn_conn in mydsa.connect_table.values():
416 s_dnstr = cn_conn.get_from_dnstr()
418 cn_conn.to_be_deleted = True
421 # Get the source DSA no matter what site
422 # XXX s_dsa is NEVER USED. It will be removed.
423 s_dsa = self.get_dsa(s_dnstr)
425 #XXX should an RODC be regarded as same site
426 same_site = s_dnstr in self.my_site.dsa_table
428 # Given an nTDSConnection object cn, if the DC with the
429 # nTDSDSA object dc that is the parent object of cn and
430 # the DC with the nTDSDA object referenced by cn!fromServer
431 # are in the same site, the KCC on dc deletes cn if all of
432 # the following are true:
434 # Bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options.
436 # No site settings object s exists for the local DC's site, or
437 # bit NTDSSETTINGS_OPT_IS_TOPL_CLEANUP_DISABLED is clear in
440 # Another nTDSConnection object cn2 exists such that cn and
441 # cn2 have the same parent object, cn!fromServer = cn2!fromServer,
444 # cn!whenCreated < cn2!whenCreated
446 # cn!whenCreated = cn2!whenCreated and
447 # cn!objectGUID < cn2!objectGUID
449 # Bit NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options
451 if not cn_conn.is_generated():
454 if self.my_site.is_cleanup_ntdsconn_disabled():
457 # Loop thru connections looking for a duplicate that
458 # fulfills the previous criteria
460 packed_guid = ndr_pack(cn_conn.guid)
461 for cn2_conn in mydsa.connect_table.values():
462 if cn2_conn is cn_conn:
465 s2_dnstr = cn2_conn.get_from_dnstr()
467 # If the NTDS Connections has a different
468 # fromServer field then no match
469 if s2_dnstr != s_dnstr:
473 lesser = (cn_conn.whenCreated < cn2_conn.whenCreated or
474 (cn_conn.whenCreated == cn2_conn.whenCreated and
475 packed_guid < ndr_pack(cn2_conn.guid)))
480 if lesser and not cn_conn.is_rodc_topology():
481 cn_conn.to_be_deleted = True
483 # Given an nTDSConnection object cn, if the DC with the nTDSDSA
484 # object dc that is the parent object of cn and the DC with
485 # the nTDSDSA object referenced by cn!fromServer are in
486 # different sites, a KCC acting as an ISTG in dc's site
487 # deletes cn if all of the following are true:
489 # Bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options.
491 # cn!fromServer references an nTDSDSA object for a DC
492 # in a site other than the local DC's site.
494 # The keepConnections sequence returned by
495 # CreateIntersiteConnections() does not contain
496 # cn!objectGUID, or cn is "superseded by" (see below)
497 # another nTDSConnection cn2 and keepConnections
498 # contains cn2!objectGUID.
500 # The return value of CreateIntersiteConnections()
503 # Bit NTDSCONN_OPT_RODC_TOPOLOGY is clear in
506 else: # different site
508 if not mydsa.is_istg():
511 if not cn_conn.is_generated():
515 # We are directly using this connection in intersite or
516 # we are using a connection which can supersede this one.
518 # MS-ADTS 6.2.2.4 - Removing Unnecessary Connections does not
519 # appear to be correct.
521 # 1. cn!fromServer and cn!parent appear inconsistent with
523 # 2. The repsFrom do not imply each other
525 if cn_conn in self.kept_connections: # and not_superceded:
528 # This is the result of create_intersite_connections
529 if not all_connected:
532 if not cn_conn.is_rodc_topology():
533 cn_conn.to_be_deleted = True
535 if mydsa.is_ro() or opts.readonly:
536 for connect in mydsa.connect_table.values():
537 if connect.to_be_deleted:
538 DEBUG_FN("TO BE DELETED:\n%s" % connect)
539 if connect.to_be_added:
540 DEBUG_FN("TO BE ADDED:\n%s" % connect)
542 # Peform deletion from our tables but perform
543 # no database modification
544 mydsa.commit_connections(self.samdb, ro=True)
546 # Commit any modified connections
547 mydsa.commit_connections(self.samdb)
549 def modify_repsFrom(self, n_rep, t_repsFrom, s_rep, s_dsa, cn_conn):
550 """Part of MS-ADTS 6.2.2.5.
552 Update t_repsFrom if necessary to satisfy requirements. Such
553 updates are typically required when the IDL_DRSGetNCChanges
554 server has moved from one site to another--for example, to
555 enable compression when the server is moved from the
556 client's site to another site.
558 :param n_rep: NC replica we need
559 :param t_repsFrom: repsFrom tuple to modify
560 :param s_rep: NC replica at source DSA
561 :param s_dsa: source DSA
562 :param cn_conn: Local DSA NTDSConnection child
564 ::returns: (update) bit field containing which portion of the
565 repsFrom was modified. This bit field is suitable as input
566 to IDL_DRSReplicaModify ulModifyFields element, as it consists
568 drsuapi.DRSUAPI_DRS_UPDATE_SCHEDULE
569 drsuapi.DRSUAPI_DRS_UPDATE_FLAGS
570 drsuapi.DRSUAPI_DRS_UPDATE_ADDRESS
572 s_dnstr = s_dsa.dsa_dnstr
575 same_site = s_dnstr in self.my_site.dsa_table
577 # if schedule doesn't match then update and modify
578 times = convert_schedule_to_repltimes(cn_conn.schedule)
579 if times != t_repsFrom.schedule:
580 t_repsFrom.schedule = times
581 update |= drsuapi.DRSUAPI_DRS_UPDATE_SCHEDULE
583 # Bit DRS_PER_SYNC is set in replicaFlags if and only
584 # if nTDSConnection schedule has a value v that specifies
585 # scheduled replication is to be performed at least once
587 if cn_conn.is_schedule_minimum_once_per_week():
589 if ((t_repsFrom.replica_flags &
590 drsuapi.DRSUAPI_DRS_PER_SYNC) == 0x0):
591 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_PER_SYNC
593 # Bit DRS_INIT_SYNC is set in t.replicaFlags if and only
594 # if the source DSA and the local DC's nTDSDSA object are
595 # in the same site or source dsa is the FSMO role owner
596 # of one or more FSMO roles in the NC replica.
597 if same_site or n_rep.is_fsmo_role_owner(s_dnstr):
599 if ((t_repsFrom.replica_flags &
600 drsuapi.DRSUAPI_DRS_INIT_SYNC) == 0x0):
601 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_INIT_SYNC
603 # If bit NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT is set in
604 # cn!options, bit DRS_NEVER_NOTIFY is set in t.replicaFlags
605 # if and only if bit NTDSCONN_OPT_USE_NOTIFY is clear in
606 # cn!options. Otherwise, bit DRS_NEVER_NOTIFY is set in
607 # t.replicaFlags if and only if s and the local DC's
608 # nTDSDSA object are in different sites.
609 if ((cn_conn.options &
610 dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT) != 0x0):
612 if (cn_conn.options & dsdb.NTDSCONN_OPT_USE_NOTIFY) == 0x0:
615 # it LOOKS as if this next test is a bit silly: it
616 # checks the flag then sets it if it not set; the same
617 # effect could be achieved by unconditionally setting
618 # it. But in fact the repsFrom object has special
619 # magic attached to it, and altering replica_flags has
620 # side-effects. That is bad in my opinion, but there
622 if ((t_repsFrom.replica_flags &
623 drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0):
624 t_repsFrom.replica_flags |= \
625 drsuapi.DRSUAPI_DRS_NEVER_NOTIFY
629 if ((t_repsFrom.replica_flags &
630 drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0):
631 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_NEVER_NOTIFY
633 # Bit DRS_USE_COMPRESSION is set in t.replicaFlags if
634 # and only if s and the local DC's nTDSDSA object are
635 # not in the same site and the
636 # NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION bit is
637 # clear in cn!options
638 if (not same_site and
640 dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION) == 0x0):
642 if ((t_repsFrom.replica_flags &
643 drsuapi.DRSUAPI_DRS_USE_COMPRESSION) == 0x0):
644 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_USE_COMPRESSION
646 # Bit DRS_TWOWAY_SYNC is set in t.replicaFlags if and only
647 # if bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options.
648 if (cn_conn.options & dsdb.NTDSCONN_OPT_TWOWAY_SYNC) != 0x0:
650 if ((t_repsFrom.replica_flags &
651 drsuapi.DRSUAPI_DRS_TWOWAY_SYNC) == 0x0):
652 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_TWOWAY_SYNC
654 # Bits DRS_DISABLE_AUTO_SYNC and DRS_DISABLE_PERIODIC_SYNC are
655 # set in t.replicaFlags if and only if cn!enabledConnection = false.
656 if not cn_conn.is_enabled():
658 if ((t_repsFrom.replica_flags &
659 drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC) == 0x0):
660 t_repsFrom.replica_flags |= \
661 drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC
663 if ((t_repsFrom.replica_flags &
664 drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC) == 0x0):
665 t_repsFrom.replica_flags |= \
666 drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC
668 # If s and the local DC's nTDSDSA object are in the same site,
669 # cn!transportType has no value, or the RDN of cn!transportType
672 # Bit DRS_MAIL_REP in t.replicaFlags is clear.
674 # t.uuidTransport = NULL GUID.
676 # t.uuidDsa = The GUID-based DNS name of s.
680 # Bit DRS_MAIL_REP in t.replicaFlags is set.
682 # If x is the object with dsname cn!transportType,
683 # t.uuidTransport = x!objectGUID.
685 # Let a be the attribute identified by
686 # x!transportAddressAttribute. If a is
687 # the dNSHostName attribute, t.uuidDsa = the GUID-based
688 # DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
690 # It appears that the first statement i.e.
692 # "If s and the local DC's nTDSDSA object are in the same
693 # site, cn!transportType has no value, or the RDN of
694 # cn!transportType is CN=IP:"
696 # could be a slightly tighter statement if it had an "or"
697 # between each condition. I believe this should
700 # IF (same-site) OR (no-value) OR (type-ip)
702 # because IP should be the primary transport mechanism
703 # (even in inter-site) and the absense of the transportType
704 # attribute should always imply IP no matter if its multi-site
706 # NOTE MS-TECH INCORRECT:
708 # All indications point to these statements above being
709 # incorrectly stated:
711 # t.uuidDsa = The GUID-based DNS name of s.
713 # Let a be the attribute identified by
714 # x!transportAddressAttribute. If a is
715 # the dNSHostName attribute, t.uuidDsa = the GUID-based
716 # DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
718 # because the uuidDSA is a GUID and not a GUID-base DNS
719 # name. Nor can uuidDsa hold (s!parent)!a if not
720 # dNSHostName. What should have been said is:
722 # t.naDsa = The GUID-based DNS name of s
724 # That would also be correct if transportAddressAttribute
725 # were "mailAddress" because (naDsa) can also correctly
726 # hold the SMTP ISM service address.
728 nastr = "%s._msdcs.%s" % (s_dsa.dsa_guid, self.samdb.forest_dns_name())
730 # We're not currently supporting SMTP replication
731 # so is_smtp_replication_available() is currently
732 # always returning False
734 cn_conn.transport_dnstr is None or
735 cn_conn.transport_dnstr.find("CN=IP") == 0 or
736 not is_smtp_replication_available())):
738 if ((t_repsFrom.replica_flags &
739 drsuapi.DRSUAPI_DRS_MAIL_REP) != 0x0):
740 t_repsFrom.replica_flags &= ~drsuapi.DRSUAPI_DRS_MAIL_REP
742 t_repsFrom.transport_guid = misc.GUID()
744 # See (NOTE MS-TECH INCORRECT) above
745 if t_repsFrom.version == 0x1:
746 if t_repsFrom.dns_name1 is None or \
747 t_repsFrom.dns_name1 != nastr:
748 t_repsFrom.dns_name1 = nastr
750 if t_repsFrom.dns_name1 is None or \
751 t_repsFrom.dns_name2 is None or \
752 t_repsFrom.dns_name1 != nastr or \
753 t_repsFrom.dns_name2 != nastr:
754 t_repsFrom.dns_name1 = nastr
755 t_repsFrom.dns_name2 = nastr
758 # XXX This entire branch is NEVER used! Because we don't do SMTP!
759 # (see the if condition above). Just close your eyes here.
760 if ((t_repsFrom.replica_flags &
761 drsuapi.DRSUAPI_DRS_MAIL_REP) == 0x0):
762 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_MAIL_REP
764 # We have a transport type but its not an
765 # object in the database
766 if cn_conn.transport_guid not in self.transport_table:
767 raise KCCError("Missing inter-site transport - (%s)" %
768 cn_conn.transport_dnstr)
770 x_transport = self.transport_table[str(cn_conn.transport_guid)]
772 if t_repsFrom.transport_guid != x_transport.guid:
773 t_repsFrom.transport_guid = x_transport.guid
775 # See (NOTE MS-TECH INCORRECT) above
776 if x_transport.address_attr == "dNSHostName":
778 if t_repsFrom.version == 0x1:
779 if t_repsFrom.dns_name1 is None or \
780 t_repsFrom.dns_name1 != nastr:
781 t_repsFrom.dns_name1 = nastr
783 if t_repsFrom.dns_name1 is None or \
784 t_repsFrom.dns_name2 is None or \
785 t_repsFrom.dns_name1 != nastr or \
786 t_repsFrom.dns_name2 != nastr:
787 t_repsFrom.dns_name1 = nastr
788 t_repsFrom.dns_name2 = nastr
791 # MS tech specification says we retrieve the named
792 # attribute in "transportAddressAttribute" from the parent of
795 pdnstr = s_dsa.get_parent_dnstr()
796 attrs = [x_transport.address_attr]
798 res = self.samdb.search(base=pdnstr, scope=ldb.SCOPE_BASE,
800 except ldb.LdbError, (enum, estr):
802 "Unable to find attr (%s) for (%s) - (%s)" %
803 (x_transport.address_attr, pdnstr, estr))
806 nastr = str(msg[x_transport.address_attr][0])
808 # See (NOTE MS-TECH INCORRECT) above
809 if t_repsFrom.version == 0x1:
810 if t_repsFrom.dns_name1 is None or \
811 t_repsFrom.dns_name1 != nastr:
812 t_repsFrom.dns_name1 = nastr
814 if t_repsFrom.dns_name1 is None or \
815 t_repsFrom.dns_name2 is None or \
816 t_repsFrom.dns_name1 != nastr or \
817 t_repsFrom.dns_name2 != nastr:
819 t_repsFrom.dns_name1 = nastr
820 t_repsFrom.dns_name2 = nastr
822 if t_repsFrom.is_modified():
823 logger.debug("modify_repsFrom(): %s" % t_repsFrom)
825 def is_repsFrom_implied(self, n_rep, cn_conn):
826 """Given a NC replica and NTDS Connection, determine if the connection
827 implies a repsFrom tuple should be present from the source DSA listed
828 in the connection to the naming context
830 :param n_rep: NC replica
831 :param conn: NTDS Connection
832 ::returns (True || False), source DSA:
834 #XXX different conditions for "implies" than MS-ADTS 6.2.2
836 # NTDS Connection must satisfy all the following criteria
837 # to imply a repsFrom tuple is needed:
839 # cn!enabledConnection = true.
840 # cn!options does not contain NTDSCONN_OPT_RODC_TOPOLOGY.
841 # cn!fromServer references an nTDSDSA object.
845 if cn_conn.is_enabled() and not cn_conn.is_rodc_topology():
846 s_dnstr = cn_conn.get_from_dnstr()
847 if s_dnstr is not None:
848 s_dsa = self.get_dsa(s_dnstr)
850 # No DSA matching this source DN string?
854 # To imply a repsFrom tuple is needed, each of these
857 # An NC replica of the NC "is present" on the DC to
858 # which the nTDSDSA object referenced by cn!fromServer
861 # An NC replica of the NC "should be present" on
863 s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
865 if s_rep is None or not s_rep.is_present():
868 # To imply a repsFrom tuple is needed, each of these
871 # The NC replica on the DC referenced by cn!fromServer is
872 # a writable replica or the NC replica that "should be
873 # present" on the local DC is a partial replica.
875 # The NC is not a domain NC, the NC replica that
876 # "should be present" on the local DC is a partial
877 # replica, cn!transportType has no value, or
878 # cn!transportType has an RDN of CN=IP.
880 implied = (not s_rep.is_ro() or n_rep.is_partial()) and \
881 (not n_rep.is_domain() or
882 n_rep.is_partial() or
883 cn_conn.transport_dnstr is None or
884 cn_conn.transport_dnstr.find("CN=IP") == 0)
891 def translate_ntdsconn(self, current_dsa=None):
892 """This function adjusts values of repsFrom abstract attributes of NC
893 replicas on the local DC to match those implied by
894 nTDSConnection objects.
899 if current_dsa is None:
900 current_dsa = self.my_dsa
902 if current_dsa.is_translate_ntdsconn_disabled():
903 logger.debug("skipping translate_ntdsconn() "
904 "because disabling flag is set")
907 logger.debug("translate_ntdsconn(): enter")
909 current_rep_table, needed_rep_table = current_dsa.get_rep_tables()
911 # Filled in with replicas we currently have that need deleting
914 # We're using the MS notation names here to allow
915 # correlation back to the published algorithm.
917 # n_rep - NC replica (n)
918 # t_repsFrom - tuple (t) in n!repsFrom
919 # s_dsa - Source DSA of the replica. Defined as nTDSDSA
920 # object (s) such that (s!objectGUID = t.uuidDsa)
921 # In our IDL representation of repsFrom the (uuidDsa)
922 # attribute is called (source_dsa_obj_guid)
923 # cn_conn - (cn) is nTDSConnection object and child of the local
924 # DC's nTDSDSA object and (cn!fromServer = s)
925 # s_rep - source DSA replica of n
927 # If we have the replica and its not needed
928 # then we add it to the "to be deleted" list.
929 for dnstr in current_rep_table:
930 if dnstr not in needed_rep_table:
931 delete_reps.add(dnstr)
933 DEBUG_FN('current %d needed %d delete %d' % (len(current_rep_table),
934 len(needed_rep_table), len(delete_reps)))
937 DEBUG('deleting these reps: %s' % delete_reps)
938 for dnstr in delete_reps:
939 del current_rep_table[dnstr]
941 # Now perform the scan of replicas we'll need
942 # and compare any current repsFrom against the
944 for n_rep in needed_rep_table.values():
946 # load any repsFrom and fsmo roles as we'll
947 # need them during connection translation
948 n_rep.load_repsFrom(self.samdb)
949 n_rep.load_fsmo_roles(self.samdb)
951 # Loop thru the existing repsFrom tupples (if any)
952 # XXX This is a list and could contain duplicates
953 # (multiple load_repsFrom calls)
954 for t_repsFrom in n_rep.rep_repsFrom:
956 # for each tuple t in n!repsFrom, let s be the nTDSDSA
957 # object such that s!objectGUID = t.uuidDsa
958 guidstr = str(t_repsFrom.source_dsa_obj_guid)
959 s_dsa = self.get_dsa_by_guidstr(guidstr)
961 # Source dsa is gone from config (strange)
962 # so cleanup stale repsFrom for unlisted DSA
964 logger.warning("repsFrom source DSA guid (%s) not found" %
966 t_repsFrom.to_be_deleted = True
969 s_dnstr = s_dsa.dsa_dnstr
971 # Retrieve my DSAs connection object (if it exists)
972 # that specifies the fromServer equivalent to
973 # the DSA that is specified in the repsFrom source
974 connections = current_dsa.get_connection_by_from_dnstr(s_dnstr)
979 for con in connections:
980 if con.is_rodc_topology():
984 # Let (cn) be the nTDSConnection object such that (cn)
985 # is a child of the local DC's nTDSDSA object and
986 # (cn!fromServer = s) and (cn!options) does not contain
987 # NTDSCONN_OPT_RODC_TOPOLOGY or NULL if no such (cn) exists.
989 # KCC removes this repsFrom tuple if any of the following
994 #XXX varying possible interpretations of rodc_topology
996 t_repsFrom.to_be_deleted = True
999 # [...] KCC removes this repsFrom tuple if:
1001 # No NC replica of the NC "is present" on DSA that
1002 # would be source of replica
1004 # A writable replica of the NC "should be present" on
1005 # the local DC, but a partial replica "is present" on
1007 s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
1009 if s_rep is None or not s_rep.is_present() or \
1010 (not n_rep.is_ro() and s_rep.is_partial()):
1012 t_repsFrom.to_be_deleted = True
1015 # If the KCC did not remove t from n!repsFrom, it updates t
1016 self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)
1018 # Loop thru connections and add implied repsFrom tuples
1019 # for each NTDSConnection under our local DSA if the
1020 # repsFrom is not already present
1021 for cn_conn in current_dsa.connect_table.values():
1023 implied, s_dsa = self.is_repsFrom_implied(n_rep, cn_conn)
1027 # Loop thru the existing repsFrom tupples (if any) and
1028 # if we already have a tuple for this connection then
1029 # no need to proceed to add. It will have been changed
1030 # to have the correct attributes above
1031 for t_repsFrom in n_rep.rep_repsFrom:
1032 guidstr = str(t_repsFrom.source_dsa_obj_guid)
1034 if s_dsa is self.get_dsa_by_guidstr(guidstr):
1041 # Create a new RepsFromTo and proceed to modify
1042 # it according to specification
1043 t_repsFrom = RepsFromTo(n_rep.nc_dnstr)
1045 t_repsFrom.source_dsa_obj_guid = s_dsa.dsa_guid
1047 s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
1049 self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)
1051 # Add to our NC repsFrom as this is newly computed
1052 if t_repsFrom.is_modified():
1053 n_rep.rep_repsFrom.append(t_repsFrom)
1056 # Display any to be deleted or modified repsFrom
1057 text = n_rep.dumpstr_to_be_deleted()
1059 logger.info("TO BE DELETED:\n%s" % text)
1060 text = n_rep.dumpstr_to_be_modified()
1062 logger.info("TO BE MODIFIED:\n%s" % text)
1064 # Peform deletion from our tables but perform
1065 # no database modification
1066 n_rep.commit_repsFrom(self.samdb, ro=True)
1068 # Commit any modified repsFrom to the NC replica
1069 n_rep.commit_repsFrom(self.samdb)
1071 def merge_failed_links(self):
1072 """Merge of kCCFailedLinks and kCCFailedLinks from bridgeheads.
1073 The KCC on a writable DC attempts to merge the link and connection
1074 failure information from bridgehead DCs in its own site to help it
1075 identify failed bridgehead DCs.
1077 # MS-TECH Ref 6.2.2.3.2 Merge of kCCFailedLinks and kCCFailedLinks
1080 # 1. Queries every bridgehead server in your site (other than yourself)
1081 # 2. For every ntDSConnection that references a server in a different
1082 # site merge all the failure info
1084 # XXX - not implemented yet
1085 if opts.attempt_live_connections:
1086 DEBUG_RED("merge_failed_links() is NOT IMPLEMENTED")
1088 DEBUG_FN("skipping merge_failed_links() because it requires "
1089 "real network connections\n"
1090 "and we weren't asked to --attempt-live-connections")
1092 def setup_graph(self, part):
1093 """Set up a GRAPH, populated with a VERTEX for each site
1094 object, a MULTIEDGE for each siteLink object, and a
1095 MUTLIEDGESET for each siteLinkBridge object (or implied
1098 ::returns: a new graph
1102 g = IntersiteGraph()
1104 for site_guid, site in self.site_table.items():
1105 vertex = Vertex(site, part)
1106 vertex.guid = site_guid
1107 vertex.ndrpacked_guid = ndr_pack(site.site_guid)
1108 g.vertices.add(vertex)
1110 if not guid_to_vertex.get(site_guid):
1111 guid_to_vertex[site_guid] = []
1113 guid_to_vertex[site_guid].append(vertex)
1115 connected_vertices = set()
1116 for transport_guid, transport in self.transport_table.items():
1117 # Currently only ever "IP"
1118 if transport.name != 'IP':
1119 DEBUG_FN("setup_graph is ignoring transport %s" %
1122 for site_link_dn, site_link in self.sitelink_table.items():
1123 new_edge = create_edge(transport_guid, site_link,
1125 connected_vertices.update(new_edge.vertices)
1126 g.edges.add(new_edge)
1128 # If 'Bridge all site links' is enabled and Win2k3 bridges required
1130 # NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
1131 # No documentation for this however, ntdsapi.h appears to have:
1132 # NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED = 0x00001000
1133 if (((self.my_site.site_options & 0x00000002) == 0
1134 and (self.my_site.site_options & 0x00001000) == 0)):
1135 g.edge_set.add(create_auto_edge_set(g, transport_guid))
1137 # TODO get all site link bridges
1138 for site_link_bridge in []:
1139 g.edge_set.add(create_edge_set(g, transport_guid,
1142 g.connected_vertices = connected_vertices
1144 #be less verbose in dot file output unless --debug
1145 do_dot_files = opts.dot_files and opts.debug
1147 for edge in g.edges:
1148 for a, b in itertools.combinations(edge.vertices, 2):
1149 dot_edges.append((a.site.site_dnstr, b.site.site_dnstr))
1150 verify_properties = ()
1151 verify_and_dot('site_edges', dot_edges, directed=False,
1152 label=self.my_dsa_dnstr,
1153 properties=verify_properties, debug=DEBUG,
1155 dot_files=do_dot_files)
1159 def get_bridgehead(self, site, part, transport, partial_ok, detect_failed):
1160 """Get a bridghead DC.
1162 :param site: site object representing for which a bridgehead
1164 :param part: crossRef for NC to replicate.
1165 :param transport: interSiteTransport object for replication
1167 :param partial_ok: True if a DC containing a partial
1168 replica or a full replica will suffice, False if only
1169 a full replica will suffice.
1170 :param detect_failed: True to detect failed DCs and route
1171 replication traffic around them, False to assume no DC
1173 ::returns: dsa object for the bridgehead DC or None
1176 bhs = self.get_all_bridgeheads(site, part, transport,
1177 partial_ok, detect_failed)
1179 DEBUG_MAGENTA("get_bridgehead:\n\tsitedn=%s\n\tbhdn=None" %
1183 DEBUG_GREEN("get_bridgehead:\n\tsitedn=%s\n\tbhdn=%s" %
1184 (site.site_dnstr, bhs[0].dsa_dnstr))
1187 def get_all_bridgeheads(self, site, part, transport,
1188 partial_ok, detect_failed):
1189 """Get all bridghead DCs satisfying the given criteria
1191 :param site: site object representing the site for which
1192 bridgehead DCs are desired.
1193 :param part: partition for NC to replicate.
1194 :param transport: interSiteTransport object for
1195 replication traffic.
1196 :param partial_ok: True if a DC containing a partial
1197 replica or a full replica will suffice, False if
1198 only a full replica will suffice.
1199 :param detect_failed: True to detect failed DCs and route
1200 replication traffic around them, FALSE to assume
1202 ::returns: list of dsa object for available bridgehead
1208 logger.debug("get_all_bridgeheads: %s" % transport.name)
1209 if 'Site-5' in site.site_dnstr:
1210 DEBUG_RED("get_all_bridgeheads with %s, part%s, partial_ok %s"
1211 " detect_failed %s" % (site.site_dnstr, part.partstr,
1212 partial_ok, detect_failed))
1213 logger.debug(site.rw_dsa_table)
1214 for dsa in site.rw_dsa_table.values():
1216 pdnstr = dsa.get_parent_dnstr()
1218 # IF t!bridgeheadServerListBL has one or more values and
1219 # t!bridgeheadServerListBL does not contain a reference
1220 # to the parent object of dc then skip dc
1221 if ((len(transport.bridgehead_list) != 0 and
1222 pdnstr not in transport.bridgehead_list)):
1225 # IF dc is in the same site as the local DC
1226 # IF a replica of cr!nCName is not in the set of NC replicas
1227 # that "should be present" on dc or a partial replica of the
1228 # NC "should be present" but partialReplicasOkay = FALSE
1230 if self.my_site.same_site(dsa):
1231 needed, ro, partial = part.should_be_present(dsa)
1232 if not needed or (partial and not partial_ok):
1234 rep = dsa.get_current_replica(part.nc_dnstr)
1237 # IF an NC replica of cr!nCName is not in the set of NC
1238 # replicas that "are present" on dc or a partial replica of
1239 # the NC "is present" but partialReplicasOkay = FALSE
1242 rep = dsa.get_current_replica(part.nc_dnstr)
1243 if rep is None or (rep.is_partial() and not partial_ok):
1246 # IF AmIRODC() and cr!nCName corresponds to default NC then
1247 # Let dsaobj be the nTDSDSA object of the dc
1248 # IF dsaobj.msDS-Behavior-Version < DS_DOMAIN_FUNCTION_2008
1250 if self.my_dsa.is_ro() and rep is not None and rep.is_default():
1251 if not dsa.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
1254 # IF t!name != "IP" and the parent object of dc has no value for
1255 # the attribute specified by t!transportAddressAttribute
1257 if transport.name != "IP":
1258 # MS tech specification says we retrieve the named
1259 # attribute in "transportAddressAttribute" from the parent
1262 attrs = [transport.address_attr]
1264 res = self.samdb.search(base=pdnstr, scope=ldb.SCOPE_BASE,
1266 except ldb.LdbError, (enum, estr):
1270 if transport.address_attr not in msg:
1272 #XXX nastr is NEVER USED. It will be removed.
1273 nastr = str(msg[transport.address_attr][0])
1275 # IF BridgeheadDCFailed(dc!objectGUID, detectFailedDCs) = TRUE
1277 if self.is_bridgehead_failed(dsa, detect_failed):
1278 DEBUG("bridgehead is failed")
1281 logger.debug("get_all_bridgeheads: dsadn=%s" % dsa.dsa_dnstr)
1284 # IF bit NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED is set in
1286 # SORT bhs such that all GC servers precede DCs that are not GC
1287 # servers, and otherwise by ascending objectGUID
1289 # SORT bhs in a random order
1290 if site.is_random_bridgehead_disabled():
1291 bhs.sort(sort_dsa_by_gc_and_guid)
1297 def is_bridgehead_failed(self, dsa, detect_failed):
1298 """Determine whether a given DC is known to be in a failed state
1299 ::returns: True if and only if the DC should be considered failed
1301 Here we DEPART from the pseudo code spec which appears to be
1302 wrong. It says, in full:
1304 /***** BridgeheadDCFailed *****/
1305 /* Determine whether a given DC is known to be in a failed state.
1306 * IN: objectGUID - objectGUID of the DC's nTDSDSA object.
1307 * IN: detectFailedDCs - TRUE if and only failed DC detection is
1309 * RETURNS: TRUE if and only if the DC should be considered to be in a
1312 BridgeheadDCFailed(IN GUID objectGUID, IN bool detectFailedDCs) : bool
1314 IF bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set in
1315 the options attribute of the site settings object for the local
1318 ELSEIF a tuple z exists in the kCCFailedLinks or
1319 kCCFailedConnections variables such that z.UUIDDsa =
1320 objectGUID, z.FailureCount > 1, and the current time -
1321 z.TimeFirstFailure > 2 hours
1324 RETURN detectFailedDCs
1328 where you will see detectFailedDCs is not behaving as
1329 advertised -- it is acting as a default return code in the
1330 event that a failure is not detected, not a switch turning
1331 detection on or off. Elsewhere the documentation seems to
1332 concur with the comment rather than the code.
1334 if not detect_failed:
1337 # NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED = 0x00000008
1338 # When DETECT_STALE_DISABLED, we can never know of if
1339 # it's in a failed state
1340 if self.my_site.site_options & 0x00000008:
1343 return self.is_stale_link_connection(dsa)
1345 def create_connection(self, part, rbh, rsite, transport,
1346 lbh, lsite, link_opt, link_sched,
1347 partial_ok, detect_failed):
1348 """Create an nTDSConnection object with the given parameters
1349 if one does not already exist.
1351 :param part: crossRef object for the NC to replicate.
1352 :param rbh: nTDSDSA object for DC to act as the
1353 IDL_DRSGetNCChanges server (which is in a site other
1354 than the local DC's site).
1355 :param rsite: site of the rbh
1356 :param transport: interSiteTransport object for the transport
1357 to use for replication traffic.
1358 :param lbh: nTDSDSA object for DC to act as the
1359 IDL_DRSGetNCChanges client (which is in the local DC's site).
1360 :param lsite: site of the lbh
1361 :param link_opt: Replication parameters (aggregated siteLink options,
1363 :param link_sched: Schedule specifying the times at which
1364 to begin replicating.
1365 :partial_ok: True if bridgehead DCs containing partial
1366 replicas of the NC are acceptable.
1367 :param detect_failed: True to detect failed DCs and route
1368 replication traffic around them, FALSE to assume no DC
1371 rbhs_all = self.get_all_bridgeheads(rsite, part, transport,
1373 rbh_table = {x.dsa_dnstr: x for x in rbhs_all}
1375 DEBUG_GREY("rbhs_all: %s %s" % (len(rbhs_all),
1376 [x.dsa_dnstr for x in rbhs_all]))
1378 # MS-TECH says to compute rbhs_avail but then doesn't use it
1379 # rbhs_avail = self.get_all_bridgeheads(rsite, part, transport,
1380 # partial_ok, detect_failed)
1382 lbhs_all = self.get_all_bridgeheads(lsite, part, transport,
1385 lbhs_all.append(lbh)
1387 DEBUG_GREY("lbhs_all: %s %s" % (len(lbhs_all),
1388 [x.dsa_dnstr for x in lbhs_all]))
1390 # MS-TECH says to compute lbhs_avail but then doesn't use it
1391 # lbhs_avail = self.get_all_bridgeheads(lsite, part, transport,
1392 # partial_ok, detect_failed)
1394 # FOR each nTDSConnection object cn such that the parent of cn is
1395 # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1396 for ldsa in lbhs_all:
1397 for cn in ldsa.connect_table.values():
1399 rdsa = rbh_table.get(cn.from_dnstr)
1403 DEBUG_DARK_YELLOW("rdsa is %s" % rdsa.dsa_dnstr)
1404 # IF bit NTDSCONN_OPT_IS_GENERATED is set in cn!options and
1405 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options and
1406 # cn!transportType references t
1407 if ((cn.is_generated() and
1408 not cn.is_rodc_topology() and
1409 cn.transport_guid == transport.guid)):
1411 # IF bit NTDSCONN_OPT_USER_OWNED_SCHEDULE is clear in
1412 # cn!options and cn!schedule != sch
1413 # Perform an originating update to set cn!schedule to
1415 if ((not cn.is_user_owned_schedule() and
1416 not cn.is_equivalent_schedule(link_sched))):
1417 cn.schedule = link_sched
1418 cn.set_modified(True)
1420 # IF bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1421 # NTDSCONN_OPT_USE_NOTIFY are set in cn
1422 if cn.is_override_notify_default() and \
1425 # IF bit NTDSSITELINK_OPT_USE_NOTIFY is clear in
1427 # Perform an originating update to clear bits
1428 # NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1429 # NTDSCONN_OPT_USE_NOTIFY in cn!options
1430 if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) == 0:
1432 ~(dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1433 dsdb.NTDSCONN_OPT_USE_NOTIFY)
1434 cn.set_modified(True)
1439 # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in
1441 # Perform an originating update to set bits
1442 # NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1443 # NTDSCONN_OPT_USE_NOTIFY in cn!options
1444 if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1446 (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1447 dsdb.NTDSCONN_OPT_USE_NOTIFY)
1448 cn.set_modified(True)
1450 # IF bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options
1451 if cn.is_twoway_sync():
1453 # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is clear in
1455 # Perform an originating update to clear bit
1456 # NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1457 if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) == 0:
1458 cn.options &= ~dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1459 cn.set_modified(True)
1464 # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in
1466 # Perform an originating update to set bit
1467 # NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1468 if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1469 cn.options |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1470 cn.set_modified(True)
1472 # IF bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION is set
1474 if cn.is_intersite_compression_disabled():
1476 # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is clear
1478 # Perform an originating update to clear bit
1479 # NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1482 dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) == 0):
1484 ~dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1485 cn.set_modified(True)
1489 # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1491 # Perform an originating update to set bit
1492 # NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1495 dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1497 dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1498 cn.set_modified(True)
1500 # Display any modified connection
1502 if cn.to_be_modified:
1503 logger.info("TO BE MODIFIED:\n%s" % cn)
1505 ldsa.commit_connections(self.samdb, ro=True)
1507 ldsa.commit_connections(self.samdb)
1510 valid_connections = 0
1512 # FOR each nTDSConnection object cn such that cn!parent is
1513 # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1514 for ldsa in lbhs_all:
1515 for cn in ldsa.connect_table.values():
1517 rdsa = rbh_table.get(cn.from_dnstr)
1521 DEBUG_DARK_YELLOW("round 2: rdsa is %s" % rdsa.dsa_dnstr)
1523 # IF (bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options or
1524 # cn!transportType references t) and
1525 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options
1526 if (((not cn.is_generated() or
1527 cn.transport_guid == transport.guid) and
1528 not cn.is_rodc_topology())):
1530 # LET rguid be the objectGUID of the nTDSDSA object
1531 # referenced by cn!fromServer
1532 # LET lguid be (cn!parent)!objectGUID
1534 # IF BridgeheadDCFailed(rguid, detectFailedDCs) = FALSE and
1535 # BridgeheadDCFailed(lguid, detectFailedDCs) = FALSE
1536 # Increment cValidConnections by 1
1537 if ((not self.is_bridgehead_failed(rdsa, detect_failed) and
1538 not self.is_bridgehead_failed(ldsa, detect_failed))):
1539 valid_connections += 1
1541 # IF keepConnections does not contain cn!objectGUID
1542 # APPEND cn!objectGUID to keepConnections
1543 self.kept_connections.add(cn)
1546 DEBUG_RED("valid connections %d" % valid_connections)
1547 DEBUG("kept_connections:\n%s" % (self.kept_connections,))
1548 # IF cValidConnections = 0
1549 if valid_connections == 0:
1551 # LET opt be NTDSCONN_OPT_IS_GENERATED
1552 opt = dsdb.NTDSCONN_OPT_IS_GENERATED
1554 # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in ri.Options
1555 # SET bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1556 # NTDSCONN_OPT_USE_NOTIFY in opt
1557 if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1558 opt |= (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1559 dsdb.NTDSCONN_OPT_USE_NOTIFY)
1561 # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in ri.Options
1562 # SET bit NTDSCONN_OPT_TWOWAY_SYNC opt
1563 if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1564 opt |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1566 # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1568 # SET bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in opt
1570 dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1571 opt |= dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1573 # Perform an originating update to create a new nTDSConnection
1574 # object cn that is a child of lbh, cn!enabledConnection = TRUE,
1575 # cn!options = opt, cn!transportType is a reference to t,
1576 # cn!fromServer is a reference to rbh, and cn!schedule = sch
1577 DEBUG_FN("new connection, KCC dsa: %s" % self.my_dsa.dsa_dnstr)
1578 cn = lbh.new_connection(opt, 0, transport,
1579 rbh.dsa_dnstr, link_sched)
1581 # Display any added connection
1584 logger.info("TO BE ADDED:\n%s" % cn)
1586 lbh.commit_connections(self.samdb, ro=True)
1588 lbh.commit_connections(self.samdb)
1590 # APPEND cn!objectGUID to keepConnections
1591 self.kept_connections.add(cn)
1593 def add_transports(self, vertex, local_vertex, graph, detect_failed):
1595 # The docs ([MS-ADTS] 6.2.2.3.4.3) say to use local_vertex
1596 # here, but using vertex seems to make more sense. That is,
1597 # the docs want this:
1599 #bh = self.get_bridgehead(vertex.site, vertex.part, transport,
1600 # local_vertex.is_black(), detect_failed)
1604 vertex.accept_red_red = []
1605 vertex.accept_black = []
1606 found_failed = False
1607 for t_guid, transport in self.transport_table.items():
1608 if transport.name != 'IP':
1609 #XXX well this is cheating a bit
1610 logging.warning("WARNING: we are ignoring a transport named %r"
1614 # FLAG_CR_NTDS_DOMAIN 0x00000002
1615 if ((vertex.is_red() and transport.name != "IP" and
1616 vertex.part.system_flags & 0x00000002)):
1619 if vertex not in graph.connected_vertices:
1622 partial_replica_okay = vertex.is_black()
1623 bh = self.get_bridgehead(vertex.site, vertex.part, transport,
1624 partial_replica_okay, detect_failed)
1629 vertex.accept_red_red.append(t_guid)
1630 vertex.accept_black.append(t_guid)
1632 # Add additional transport to allow another run of Dijkstra
1633 vertex.accept_red_red.append("EDGE_TYPE_ALL")
1634 vertex.accept_black.append("EDGE_TYPE_ALL")
1638 def create_connections(self, graph, part, detect_failed):
1639 """Construct an NC replica graph for the NC identified by
1640 the given crossRef, then create any additional nTDSConnection
1643 :param graph: site graph.
1644 :param part: crossRef object for NC.
1645 :param detect_failed: True to detect failed DCs and route
1646 replication traffic around them, False to assume no DC
1649 Modifies self.kept_connections by adding any connections
1650 deemed to be "in use".
1652 ::returns: (all_connected, found_failed_dc)
1653 (all_connected) True if the resulting NC replica graph
1654 connects all sites that need to be connected.
1655 (found_failed_dc) True if one or more failed DCs were
1658 all_connected = True
1659 found_failed = False
1661 logger.debug("create_connections(): enter\n"
1662 "\tpartdn=%s\n\tdetect_failed=%s" %
1663 (part.nc_dnstr, detect_failed))
1665 # XXX - This is a highly abbreviated function from the MS-TECH
1666 # ref. It creates connections between bridgeheads to all
1667 # sites that have appropriate replicas. Thus we are not
1668 # creating a minimum cost spanning tree but instead
1669 # producing a fully connected tree. This should produce
1670 # a full (albeit not optimal cost) replication topology.
1672 my_vertex = Vertex(self.my_site, part)
1673 my_vertex.color_vertex()
1675 for v in graph.vertices:
1677 if self.add_transports(v, my_vertex, graph, False):
1680 # No NC replicas for this NC in the site of the local DC,
1681 # so no nTDSConnection objects need be created
1682 if my_vertex.is_white():
1683 return all_connected, found_failed
1685 edge_list, n_components = get_spanning_tree_edges(graph,
1689 logger.debug("%s Number of components: %d" %
1690 (part.nc_dnstr, n_components))
1691 if n_components > 1:
1692 all_connected = False
1694 # LET partialReplicaOkay be TRUE if and only if
1695 # localSiteVertex.Color = COLOR.BLACK
1696 partial_ok = my_vertex.is_black()
1698 # Utilize the IP transport only for now
1699 transport = self.ip_transport
1701 DEBUG("edge_list %s" % edge_list)
1703 # XXX more accurate comparison?
1704 if e.directed and e.vertices[0].site is self.my_site:
1707 if e.vertices[0].site is self.my_site:
1708 rsite = e.vertices[1].site
1710 rsite = e.vertices[0].site
1712 # We don't make connections to our own site as that
1713 # is intrasite topology generator's job
1714 if rsite is self.my_site:
1715 DEBUG("rsite is my_site")
1718 # Determine bridgehead server in remote site
1719 rbh = self.get_bridgehead(rsite, part, transport,
1720 partial_ok, detect_failed)
1724 # RODC acts as an BH for itself
1726 # LET lbh be the nTDSDSA object of the local DC
1728 # LET lbh be the result of GetBridgeheadDC(localSiteVertex.ID,
1729 # cr, t, partialReplicaOkay, detectFailedDCs)
1730 if self.my_dsa.is_ro():
1731 lsite = self.my_site
1734 lsite = self.my_site
1735 lbh = self.get_bridgehead(lsite, part, transport,
1736 partial_ok, detect_failed)
1739 DEBUG_RED("DISASTER! lbh is None")
1744 DEBUG_BLUE("vertices")
1746 DEBUG_BLUE("bridgeheads")
1748 DEBUG_BLUE("-" * 70)
1750 sitelink = e.site_link
1751 if sitelink is None:
1755 link_opt = sitelink.options
1756 link_sched = sitelink.schedule
1758 self.create_connection(part, rbh, rsite, transport,
1759 lbh, lsite, link_opt, link_sched,
1760 partial_ok, detect_failed)
1762 return all_connected, found_failed
1764 def create_intersite_connections(self):
1765 """Computes an NC replica graph for each NC replica that "should be
1766 present" on the local DC or "is present" on any DC in the same site
1767 as the local DC. For each edge directed to an NC replica on such a
1768 DC from an NC replica on a DC in another site, the KCC creates an
1769 nTDSConnection object to imply that edge if one does not already
1772 Modifies self.kept_connections - A set of nTDSConnection
1773 objects for edges that are directed
1774 to the local DC's site in one or more NC replica graphs.
1776 returns: True if spanning trees were created for all NC replica
1777 graphs, otherwise False.
1779 all_connected = True
1780 self.kept_connections = set()
1782 # LET crossRefList be the set containing each object o of class
1783 # crossRef such that o is a child of the CN=Partitions child of the
1786 # FOR each crossRef object cr in crossRefList
1787 # IF cr!enabled has a value and is false, or if FLAG_CR_NTDS_NC
1788 # is clear in cr!systemFlags, skip cr.
1789 # LET g be the GRAPH return of SetupGraph()
1791 for part in self.part_table.values():
1793 if not part.is_enabled():
1796 if part.is_foreign():
1799 graph = self.setup_graph(part)
1801 # Create nTDSConnection objects, routing replication traffic
1802 # around "failed" DCs.
1803 found_failed = False
1805 connected, found_failed = self.create_connections(graph,
1808 DEBUG("with detect_failed: connected %s Found failed %s" %
1809 (connected, found_failed))
1811 all_connected = False
1814 # One or more failed DCs preclude use of the ideal NC
1815 # replica graph. Add connections for the ideal graph.
1816 self.create_connections(graph, part, False)
1818 return all_connected
1820 def intersite(self):
1821 """The head method for generating the inter-site KCC replica
1822 connection graph and attendant nTDSConnection objects
1825 Produces self.kept_connections set of NTDS Connections
1826 that should be kept during subsequent pruning process.
1828 ::return (True or False): (True) if the produced NC replica
1829 graph connects all sites that need to be connected
1834 mysite = self.my_site
1835 all_connected = True
1837 logger.debug("intersite(): enter")
1839 # Determine who is the ISTG
1841 mysite.select_istg(self.samdb, mydsa, ro=True)
1843 mysite.select_istg(self.samdb, mydsa, ro=False)
1845 # Test whether local site has topology disabled
1846 if mysite.is_intersite_topology_disabled():
1847 logger.debug("intersite(): exit disabled all_connected=%d" %
1849 return all_connected
1851 if not mydsa.is_istg():
1852 logger.debug("intersite(): exit not istg all_connected=%d" %
1854 return all_connected
1856 self.merge_failed_links()
1858 # For each NC with an NC replica that "should be present" on the
1859 # local DC or "is present" on any DC in the same site as the
1860 # local DC, the KCC constructs a site graph--a precursor to an NC
1861 # replica graph. The site connectivity for a site graph is defined
1862 # by objects of class interSiteTransport, siteLink, and
1863 # siteLinkBridge in the config NC.
1865 all_connected = self.create_intersite_connections()
1867 logger.debug("intersite(): exit all_connected=%d" % all_connected)
1868 return all_connected
1870 def update_rodc_connection(self):
1871 """Runs when the local DC is an RODC and updates the RODC NTFRS
1874 # Given an nTDSConnection object cn1, such that cn1.options contains
1875 # NTDSCONN_OPT_RODC_TOPOLOGY, and another nTDSConnection object cn2,
1876 # does not contain NTDSCONN_OPT_RODC_TOPOLOGY, modify cn1 to ensure
1877 # that the following is true:
1879 # cn1.fromServer = cn2.fromServer
1880 # cn1.schedule = cn2.schedule
1882 # If no such cn2 can be found, cn1 is not modified.
1883 # If no such cn1 can be found, nothing is modified by this task.
1885 if not self.my_dsa.is_ro():
1888 all_connections = self.my_dsa.connect_table.values()
1889 ro_connections = [x for x in all_connections if x.is_rodc_topology()]
1890 rw_connections = [x for x in all_connections
1891 if x not in ro_connections]
1893 # XXX here we are dealing with multiple RODC_TOPO connections,
1894 # if they exist. It is not clear whether the spec means that
1895 # or if it ever arises.
1896 if rw_connections and ro_connections:
1897 for con in ro_connections:
1898 cn2 = rw_connections[0]
1899 con.from_dnstr = cn2.from_dnstr
1900 con.schedule = cn2.schedule
1901 con.to_be_modified = True
1903 self.my_dsa.commit_connections(self.samdb, ro=opts.readonly)
1905 def intrasite_max_node_edges(self, node_count):
1906 """Returns the maximum number of edges directed to a node in
1907 the intrasite replica graph.
1909 The KCC does not create more
1910 than 50 edges directed to a single DC. To optimize replication,
1911 we compute that each node should have n+2 total edges directed
1912 to it such that (n) is the smallest non-negative integer
1913 satisfying (node_count <= 2*(n*n) + 6*n + 7)
1915 (If the number of edges is m (i.e. n + 2), that is the same as
1916 2 * m*m - 2 * m + 3).
1926 :param node_count: total number of nodes in the replica graph
1928 The intention is that there should be no more than 3 hops
1929 between any two DSAs at a site. With up to 7 nodes the 2 edges
1930 of the ring are enough; any configuration of extra edges with
1931 8 nodes will be enough. It is less clear that the 3 hop
1932 guarantee holds at e.g. 15 nodes in degenerate cases, but
1933 those are quite unlikely given the extra edges are randomly
1938 if node_count <= (2 * (n * n) + (6 * n) + 7):
1946 def construct_intrasite_graph(self, site_local, dc_local,
1947 nc_x, gc_only, detect_stale):
1949 # We're using the MS notation names here to allow
1950 # correlation back to the published algorithm.
1952 # nc_x - naming context (x) that we are testing if it
1953 # "should be present" on the local DC
1954 # f_of_x - replica (f) found on a DC (s) for NC (x)
1955 # dc_s - DC where f_of_x replica was found
1956 # dc_local - local DC that potentially needs a replica
1958 # r_list - replica list R
1959 # p_of_x - replica (p) is partial and found on a DC (s)
1961 # l_of_x - replica (l) is the local replica for NC (x)
1962 # that should appear on the local DC
1963 # r_len = is length of replica list |R|
1965 # If the DSA doesn't need a replica for this
1966 # partition (NC x) then continue
1967 needed, ro, partial = nc_x.should_be_present(dc_local)
1969 DEBUG_YELLOW("construct_intrasite_graph(): enter" +
1970 "\n\tgc_only=%d" % gc_only +
1971 "\n\tdetect_stale=%d" % detect_stale +
1972 "\n\tneeded=%s" % needed +
1974 "\n\tpartial=%s" % partial +
1978 DEBUG_RED("%s lacks 'should be present' status, "
1979 "aborting construct_intersite_graph!" %
1983 # Create a NCReplica that matches what the local replica
1984 # should say. We'll use this below in our r_list
1985 l_of_x = NCReplica(dc_local.dsa_dnstr, dc_local.dsa_guid,
1988 l_of_x.identify_by_basedn(self.samdb)
1990 l_of_x.rep_partial = partial
1993 # Add this replica that "should be present" to the
1994 # needed replica table for this DSA
1995 dc_local.add_needed_replica(l_of_x)
1999 # Let R be a sequence containing each writable replica f of x
2000 # such that f "is present" on a DC s satisfying the following
2003 # * s is a writable DC other than the local DC.
2005 # * s is in the same site as the local DC.
2007 # * If x is a read-only full replica and x is a domain NC,
2008 # then the DC's functional level is at least
2009 # DS_BEHAVIOR_WIN2008.
2011 # * Bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set
2012 # in the options attribute of the site settings object for
2013 # the local DC's site, or no tuple z exists in the
2014 # kCCFailedLinks or kCCFailedConnections variables such
2015 # that z.UUIDDsa is the objectGUID of the nTDSDSA object
2016 # for s, z.FailureCount > 0, and the current time -
2017 # z.TimeFirstFailure > 2 hours.
2021 # We'll loop thru all the DSAs looking for
2022 # writeable NC replicas that match the naming
2023 # context dn for (nc_x)
2025 for dc_s in self.my_site.dsa_table.values():
2026 # If this partition (nc_x) doesn't appear as a
2027 # replica (f_of_x) on (dc_s) then continue
2028 if not nc_x.nc_dnstr in dc_s.current_rep_table:
2031 # Pull out the NCReplica (f) of (x) with the dn
2032 # that matches NC (x) we are examining.
2033 f_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2035 # Replica (f) of NC (x) must be writable
2039 # Replica (f) of NC (x) must satisfy the
2040 # "is present" criteria for DC (s) that
2042 if not f_of_x.is_present():
2045 # DC (s) must be a writable DSA other than
2046 # my local DC. In other words we'd only replicate
2047 # from other writable DC
2048 if dc_s.is_ro() or dc_s is dc_local:
2051 # Certain replica graphs are produced only
2052 # for global catalogs, so test against
2053 # method input parameter
2054 if gc_only and not dc_s.is_gc():
2057 # DC (s) must be in the same site as the local DC
2058 # as this is the intra-site algorithm. This is
2059 # handled by virtue of placing DSAs in per
2060 # site objects (see enclosing for() loop)
2062 # If NC (x) is intended to be read-only full replica
2063 # for a domain NC on the target DC then the source
2064 # DC should have functional level at minimum WIN2008
2066 # Effectively we're saying that in order to replicate
2067 # to a targeted RODC (which was introduced in Windows 2008)
2068 # then we have to replicate from a DC that is also minimally
2071 # You can also see this requirement in the MS special
2072 # considerations for RODC which state that to deploy
2073 # an RODC, at least one writable domain controller in
2074 # the domain must be running Windows Server 2008
2075 if ro and not partial and nc_x.nc_type == NCType.domain:
2076 if not dc_s.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
2079 # If we haven't been told to turn off stale connection
2080 # detection and this dsa has a stale connection then
2082 if detect_stale and self.is_stale_link_connection(dc_s):
2085 # Replica meets criteria. Add it to table indexed
2086 # by the GUID of the DC that it appears on
2087 r_list.append(f_of_x)
2089 # If a partial (not full) replica of NC (x) "should be present"
2090 # on the local DC, append to R each partial replica (p of x)
2091 # such that p "is present" on a DC satisfying the same
2092 # criteria defined above for full replica DCs.
2094 # XXX This loop and the previous one differ only in whether
2095 # the replica is partial or not. here we only accept partial
2096 # (because we're partial); before we only accepted full. Order
2097 # doen't matter (the list is sorted a few lines down) so these
2098 # loops could easily be merged. Or this could be a helper
2102 # Now we loop thru all the DSAs looking for
2103 # partial NC replicas that match the naming
2104 # context dn for (NC x)
2105 for dc_s in self.my_site.dsa_table.values():
2107 # If this partition NC (x) doesn't appear as a
2108 # replica (p) of NC (x) on the dsa DC (s) then
2110 if not nc_x.nc_dnstr in dc_s.current_rep_table:
2113 # Pull out the NCReplica with the dn that
2114 # matches NC (x) we are examining.
2115 p_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2117 # Replica (p) of NC (x) must be partial
2118 if not p_of_x.is_partial():
2121 # Replica (p) of NC (x) must satisfy the
2122 # "is present" criteria for DC (s) that
2124 if not p_of_x.is_present():
2127 # DC (s) must be a writable DSA other than
2128 # my DSA. In other words we'd only replicate
2129 # from other writable DSA
2130 if dc_s.is_ro() or dc_s is dc_local:
2133 # Certain replica graphs are produced only
2134 # for global catalogs, so test against
2135 # method input parameter
2136 if gc_only and not dc_s.is_gc():
2139 # If we haven't been told to turn off stale connection
2140 # detection and this dsa has a stale connection then
2142 if detect_stale and self.is_stale_link_connection(dc_s):
2145 # Replica meets criteria. Add it to table indexed
2146 # by the GUID of the DSA that it appears on
2147 r_list.append(p_of_x)
2149 # Append to R the NC replica that "should be present"
2151 r_list.append(l_of_x)
2153 r_list.sort(sort_replica_by_dsa_guid)
2156 max_node_edges = self.intrasite_max_node_edges(r_len)
2158 # Add a node for each r_list element to the replica graph
2161 node = GraphNode(rep.rep_dsa_dnstr, max_node_edges)
2162 graph_list.append(node)
2164 # For each r(i) from (0 <= i < |R|-1)
2166 while i < (r_len-1):
2167 # Add an edge from r(i) to r(i+1) if r(i) is a full
2168 # replica or r(i+1) is a partial replica
2169 if not r_list[i].is_partial() or r_list[i+1].is_partial():
2170 graph_list[i+1].add_edge_from(r_list[i].rep_dsa_dnstr)
2172 # Add an edge from r(i+1) to r(i) if r(i+1) is a full
2173 # replica or ri is a partial replica.
2174 if not r_list[i+1].is_partial() or r_list[i].is_partial():
2175 graph_list[i].add_edge_from(r_list[i+1].rep_dsa_dnstr)
2178 # Add an edge from r|R|-1 to r0 if r|R|-1 is a full replica
2179 # or r0 is a partial replica.
2180 if not r_list[r_len-1].is_partial() or r_list[0].is_partial():
2181 graph_list[0].add_edge_from(r_list[r_len-1].rep_dsa_dnstr)
2183 # Add an edge from r0 to r|R|-1 if r0 is a full replica or
2184 # r|R|-1 is a partial replica.
2185 if not r_list[0].is_partial() or r_list[r_len-1].is_partial():
2186 graph_list[r_len-1].add_edge_from(r_list[0].rep_dsa_dnstr)
2188 DEBUG("r_list is length %s" % len(r_list))
2189 DEBUG('\n'.join(str((x.rep_dsa_guid, x.rep_dsa_dnstr))
2192 do_dot_files = opts.dot_files and opts.debug
2193 if opts.verify or do_dot_files:
2195 dot_vertices = set()
2196 for v1 in graph_list:
2197 dot_vertices.add(v1.dsa_dnstr)
2198 for v2 in v1.edge_from:
2199 dot_edges.append((v2, v1.dsa_dnstr))
2200 dot_vertices.add(v2)
2202 verify_properties = ('connected', 'directed_double_ring_or_small')
2203 verify_and_dot('intrasite_pre_ntdscon', dot_edges, dot_vertices,
2204 label='%s__%s__%s' % (site_local.site_dnstr,
2205 nctype_lut[nc_x.nc_type],
2207 properties=verify_properties, debug=DEBUG,
2209 dot_files=do_dot_files, directed=True)
2211 # For each existing nTDSConnection object implying an edge
2212 # from rj of R to ri such that j != i, an edge from rj to ri
2213 # is not already in the graph, and the total edges directed
2214 # to ri is less than n+2, the KCC adds that edge to the graph.
2215 for vertex in graph_list:
2216 dsa = self.my_site.dsa_table[vertex.dsa_dnstr]
2217 for connect in dsa.connect_table.values():
2218 remote = connect.from_dnstr
2219 if remote in self.my_site.dsa_table:
2220 vertex.add_edge_from(remote)
2222 DEBUG('reps are: %s' % ' '.join(x.rep_dsa_dnstr for x in r_list))
2223 DEBUG('dsas are: %s' % ' '.join(x.dsa_dnstr for x in graph_list))
2225 for tnode in graph_list:
2226 # To optimize replication latency in sites with many NC
2227 # replicas, the KCC adds new edges directed to ri to bring
2228 # the total edges to n+2, where the NC replica rk of R
2229 # from which the edge is directed is chosen at random such
2230 # that k != i and an edge from rk to ri is not already in
2233 # Note that the KCC tech ref does not give a number for
2234 # the definition of "sites with many NC replicas". At a
2235 # bare minimum to satisfy n+2 edges directed at a node we
2236 # have to have at least three replicas in |R| (i.e. if n
2237 # is zero then at least replicas from two other graph
2238 # nodes may direct edges to us).
2239 if r_len >= 3 and not tnode.has_sufficient_edges():
2240 candidates = [x for x in graph_list if
2242 x.dsa_dnstr not in tnode.edge_from)]
2244 DEBUG_BLUE("looking for random link for %s. r_len %d, "
2245 "graph len %d candidates %d"
2246 % (tnode.dsa_dnstr, r_len, len(graph_list),
2249 DEBUG("candidates %s" % [x.dsa_dnstr for x in candidates])
2251 while candidates and not tnode.has_sufficient_edges():
2252 other = random.choice(candidates)
2253 DEBUG("trying to add candidate %s" % other.dsa_dstr)
2254 if not tnode.add_edge_from(other):
2255 DEBUG_RED("could not add %s" % other.dsa_dstr)
2256 candidates.remove(other)
2258 DEBUG_FN("not adding links to %s: nodes %s, links is %s/%s" %
2259 (tnode.dsa_dnstr, r_len, len(tnode.edge_from),
2262 # Print the graph node in debug mode
2263 logger.debug("%s" % tnode)
2265 # For each edge directed to the local DC, ensure a nTDSConnection
2266 # points to us that satisfies the KCC criteria
2268 if tnode.dsa_dnstr == dc_local.dsa_dnstr:
2269 tnode.add_connections_from_edges(dc_local)
2271 if opts.verify or do_dot_files:
2273 dot_vertices = set()
2274 for v1 in graph_list:
2275 dot_vertices.add(v1.dsa_dnstr)
2276 for v2 in v1.edge_from:
2277 dot_edges.append((v2, v1.dsa_dnstr))
2278 dot_vertices.add(v2)
2280 verify_properties = ('connected', 'directed_double_ring_or_small')
2281 verify_and_dot('intrasite_post_ntdscon', dot_edges, dot_vertices,
2282 label='%s__%s__%s' % (site_local.site_dnstr,
2283 nctype_lut[nc_x.nc_type],
2285 properties=verify_properties, debug=DEBUG,
2287 dot_files=do_dot_files, directed=True)
2289 def intrasite(self):
2290 """The head method for generating the intra-site KCC replica
2291 connection graph and attendant nTDSConnection objects
2297 logger.debug("intrasite(): enter")
2299 # Test whether local site has topology disabled
2300 mysite = self.my_site
2301 if mysite.is_intrasite_topology_disabled():
2304 detect_stale = (not mysite.is_detect_stale_disabled())
2305 for connect in mydsa.connect_table.values():
2306 if connect.to_be_added:
2307 DEBUG_CYAN("TO BE ADDED:\n%s" % connect)
2309 # Loop thru all the partitions, with gc_only False
2310 for partdn, part in self.part_table.items():
2311 self.construct_intrasite_graph(mysite, mydsa, part, False,
2313 for connect in mydsa.connect_table.values():
2314 if connect.to_be_added:
2315 DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2317 # If the DC is a GC server, the KCC constructs an additional NC
2318 # replica graph (and creates nTDSConnection objects) for the
2319 # config NC as above, except that only NC replicas that "are present"
2320 # on GC servers are added to R.
2321 for connect in mydsa.connect_table.values():
2322 if connect.to_be_added:
2323 DEBUG_YELLOW("TO BE ADDED:\n%s" % connect)
2325 # Do it again, with gc_only True
2326 for partdn, part in self.part_table.items():
2327 if part.is_config():
2328 self.construct_intrasite_graph(mysite, mydsa, part, True,
2331 # The DC repeats the NC replica graph computation and nTDSConnection
2332 # creation for each of the NC replica graphs, this time assuming
2333 # that no DC has failed. It does so by re-executing the steps as
2334 # if the bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED were
2335 # set in the options attribute of the site settings object for
2336 # the local DC's site. (ie. we set "detec_stale" flag to False)
2337 for connect in mydsa.connect_table.values():
2338 if connect.to_be_added:
2339 DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2341 # Loop thru all the partitions.
2342 for partdn, part in self.part_table.items():
2343 self.construct_intrasite_graph(mysite, mydsa, part, False,
2344 False) # don't detect stale
2346 # If the DC is a GC server, the KCC constructs an additional NC
2347 # replica graph (and creates nTDSConnection objects) for the
2348 # config NC as above, except that only NC replicas that "are present"
2349 # on GC servers are added to R.
2350 for connect in mydsa.connect_table.values():
2351 if connect.to_be_added:
2352 DEBUG_RED("TO BE ADDED:\n%s" % connect)
2354 for partdn, part in self.part_table.items():
2355 if part.is_config():
2356 self.construct_intrasite_graph(mysite, mydsa, part, True,
2357 False) # don't detect stale
2360 # Display any to be added or modified repsFrom
2361 for connect in mydsa.connect_table.values():
2362 if connect.to_be_deleted:
2363 logger.info("TO BE DELETED:\n%s" % connect)
2364 if connect.to_be_modified:
2365 logger.info("TO BE MODIFIED:\n%s" % connect)
2366 if connect.to_be_added:
2367 DEBUG_GREEN("TO BE ADDED:\n%s" % connect)
2369 mydsa.commit_connections(self.samdb, ro=True)
2371 # Commit any newly created connections to the samdb
2372 mydsa.commit_connections(self.samdb)
2374 def list_dsas(self):
2378 self.load_all_sites()
2379 self.load_all_partitions()
2380 self.load_all_transports()
2381 self.load_all_sitelinks()
2383 for site in self.site_table.values():
2384 dsas.extend([dsa.dsa_dnstr.replace('CN=NTDS Settings,', '', 1)
2385 for dsa in site.dsa_table.values()])
2388 def load_samdb(self, dburl, lp, creds):
2389 self.samdb = SamDB(url=dburl,
2390 session_info=system_session(),
2391 credentials=creds, lp=lp)
2393 def plot_all_connections(self, basename, verify_properties=()):
2394 verify = verify_properties and opts.verify
2395 plot = opts.dot_files
2396 if not (verify or plot):
2404 for dsa in self.dsa_by_dnstr.values():
2405 dot_vertices.append(dsa.dsa_dnstr)
2407 vertex_colours.append('#cc0000')
2409 vertex_colours.append('#0000cc')
2410 for con in dsa.connect_table.values():
2411 if con.is_rodc_topology():
2412 edge_colours.append('red')
2414 edge_colours.append('blue')
2415 dot_edges.append((con.from_dnstr, dsa.dsa_dnstr))
2417 verify_and_dot(basename, dot_edges, vertices=dot_vertices,
2418 label=self.my_dsa_dnstr, properties=verify_properties,
2419 debug=DEBUG, verify=verify, dot_files=plot,
2420 directed=True, edge_colors=edge_colours,
2421 vertex_colors=vertex_colours)
2423 def run(self, dburl, lp, creds, forced_local_dsa=None,
2424 forget_local_links=False, forget_intersite_links=False):
2425 """Method to perform a complete run of the KCC and
2426 produce an updated topology for subsequent NC replica
2427 syncronization between domain controllers
2429 # We may already have a samdb setup if we are
2430 # currently importing an ldif for a test run
2431 if self.samdb is None:
2433 self.load_samdb(dburl, lp, creds)
2434 except ldb.LdbError, (num, msg):
2435 logger.error("Unable to open sam database %s : %s" %
2439 if forced_local_dsa:
2440 self.samdb.set_ntds_settings_dn("CN=NTDS Settings,%s" %
2448 self.load_all_sites()
2449 self.load_all_partitions()
2450 self.load_all_transports()
2451 self.load_all_sitelinks()
2453 if opts.verify or opts.dot_files:
2455 for site in self.site_table.values():
2456 guid_to_dnstr.update((str(dsa.dsa_guid), dnstr)
2458 in site.dsa_table.items())
2460 self.plot_all_connections('dsa_initial')
2463 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2464 for dnstr, c_rep in current_reps.items():
2465 DEBUG("c_rep %s" % c_rep)
2466 dot_edges.append((self.my_dsa.dsa_dnstr, dnstr))
2468 verify_and_dot('dsa_repsFrom_initial', dot_edges,
2469 directed=True, label=self.my_dsa_dnstr,
2470 properties=(), debug=DEBUG, verify=opts.verify,
2471 dot_files=opts.dot_files)
2474 for site in self.site_table.values():
2475 for dsa in site.dsa_table.values():
2476 current_reps, needed_reps = dsa.get_rep_tables()
2477 for dn_str, rep in current_reps.items():
2478 for reps_from in rep.rep_repsFrom:
2479 DEBUG("rep %s" % rep)
2480 dsa_guid = str(reps_from.source_dsa_obj_guid)
2481 dsa_dn = guid_to_dnstr[dsa_guid]
2482 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2484 verify_and_dot('dsa_repsFrom_initial_all', dot_edges,
2485 directed=True, label=self.my_dsa_dnstr,
2486 properties=(), debug=DEBUG, verify=opts.verify,
2487 dot_files=opts.dot_files)
2490 for link in self.sitelink_table.values():
2491 for a, b in itertools.combinations(link.site_list, 2):
2492 dot_edges.append((str(a), str(b)))
2493 properties = ('connected',)
2494 verify_and_dot('dsa_sitelink_initial', dot_edges,
2496 label=self.my_dsa_dnstr, properties=properties,
2497 debug=DEBUG, verify=opts.verify,
2498 dot_files=opts.dot_files)
2500 if forget_local_links:
2501 for dsa in self.my_site.dsa_table.values():
2502 dsa.connect_table = {k: v for k, v in
2503 dsa.connect_table.items()
2504 if v.is_rodc_topology()}
2505 self.plot_all_connections('dsa_forgotten_local')
2507 if forget_intersite_links:
2508 for site in self.site_table.values():
2509 for dsa in site.dsa_table.values():
2510 dsa.connect_table = {k: v for k, v in
2511 dsa.connect_table.items()
2512 if site is self.my_site and
2513 v.is_rodc_topology()}
2515 self.plot_all_connections('dsa_forgotten_all')
2516 # These are the published steps (in order) for the
2517 # MS-TECH description of the KCC algorithm ([MS-ADTS] 6.2.2)
2520 self.refresh_failed_links_connections()
2526 all_connected = self.intersite()
2529 self.remove_unneeded_ntdsconn(all_connected)
2532 self.translate_ntdsconn()
2535 self.remove_unneeded_failed_links_connections()
2538 self.update_rodc_connection()
2540 if opts.verify or opts.dot_files:
2541 self.plot_all_connections('dsa_final',
2542 ('connected', 'forest_of_rings'))
2544 DEBUG_MAGENTA("there are %d dsa guids" % len(guid_to_dnstr))
2548 my_dnstr = self.my_dsa.dsa_dnstr
2549 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2550 for dnstr, n_rep in needed_reps.items():
2551 for reps_from in n_rep.rep_repsFrom:
2552 guid_str = str(reps_from.source_dsa_obj_guid)
2553 dot_edges.append((my_dnstr, guid_to_dnstr[guid_str]))
2554 edge_colors.append('#' + str(n_rep.nc_guid)[:6])
2556 verify_and_dot('dsa_repsFrom_final', dot_edges, directed=True,
2557 label=self.my_dsa_dnstr,
2558 properties=(), debug=DEBUG, verify=opts.verify,
2559 dot_files=opts.dot_files,
2560 edge_colors=edge_colors)
2564 for site in self.site_table.values():
2565 for dsa in site.dsa_table.values():
2566 current_reps, needed_reps = dsa.get_rep_tables()
2567 for n_rep in needed_reps.values():
2568 for reps_from in n_rep.rep_repsFrom:
2569 dsa_guid = str(reps_from.source_dsa_obj_guid)
2570 dsa_dn = guid_to_dnstr[dsa_guid]
2571 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2573 verify_and_dot('dsa_repsFrom_final_all', dot_edges,
2574 directed=True, label=self.my_dsa_dnstr,
2575 properties=(), debug=DEBUG, verify=opts.verify,
2576 dot_files=opts.dot_files)
2583 def import_ldif(self, dburl, lp, creds, ldif_file):
2584 """Import all objects and attributes that are relevent
2585 to the KCC algorithms from a previously exported LDIF file.
2587 The point of this function is to allow a programmer/debugger to
2588 import an LDIF file with non-security relevent information that
2589 was previously extracted from a DC database. The LDIF file is used
2590 to create a temporary abbreviated database. The KCC algorithm can
2591 then run against this abbreviated database for debug or test
2592 verification that the topology generated is computationally the
2593 same between different OSes and algorithms.
2595 :param dburl: path to the temporary abbreviated db to create
2596 :param ldif_file: path to the ldif file to import
2599 self.samdb = ldif_utils.ldif_to_samdb(dburl, lp, ldif_file,
2600 opts.forced_local_dsa)
2601 except ldif_utils.LdifError, e:
2606 def export_ldif(self, dburl, lp, creds, ldif_file):
2607 """Routine to extract all objects and attributes that are relevent
2608 to the KCC algorithms from a DC database.
2610 The point of this function is to allow a programmer/debugger to
2611 extract an LDIF file with non-security relevent information from
2612 a DC database. The LDIF file can then be used to "import" via
2613 the import_ldif() function this file into a temporary abbreviated
2614 database. The KCC algorithm can then run against this abbreviated
2615 database for debug or test verification that the topology generated
2616 is computationally the same between different OSes and algorithms.
2618 :param dburl: LDAP database URL to extract info from
2619 :param ldif_file: output LDIF file name to create
2622 ldif_utils.samdb_to_ldif_file(self.samdb, dburl, lp, creds,
2624 except ldif_utils.LdifError, e:
2629 ##################################################
2631 ##################################################
2634 def get_spanning_tree_edges(graph, my_site, label=None):
2635 # Phase 1: Run Dijkstra's to get a list of internal edges, which are
2636 # just the shortest-paths connecting colored vertices
2638 internal_edges = set()
2640 for e_set in graph.edge_set:
2642 for v in graph.vertices:
2645 # All con_type in an edge set is the same
2646 for e in e_set.edges:
2647 edgeType = e.con_type
2648 for v in e.vertices:
2651 if opts.verify or opts.dot_files:
2652 graph_edges = [(a.site.site_dnstr, b.site.site_dnstr)
2655 *(itertools.combinations(edge.vertices, 2)
2656 for edge in e_set.edges))]
2657 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
2659 if opts.dot_files and opts.debug:
2660 write_dot_file('edgeset_%s' % (edgeType,), graph_edges,
2661 vertices=graph_nodes, label=label)
2664 verify_graph('spanning tree edge set %s' % edgeType,
2665 graph_edges, vertices=graph_nodes,
2666 properties=('complete', 'connected'),
2669 # Run dijkstra's algorithm with just the red vertices as seeds
2670 # Seed from the full replicas
2671 dijkstra(graph, edgeType, False)
2674 process_edge_set(graph, e_set, internal_edges)
2676 # Run dijkstra's algorithm with red and black vertices as the seeds
2677 # Seed from both full and partial replicas
2678 dijkstra(graph, edgeType, True)
2681 process_edge_set(graph, e_set, internal_edges)
2683 # All vertices have root/component as itself
2684 setup_vertices(graph)
2685 process_edge_set(graph, None, internal_edges)
2687 if opts.verify or opts.dot_files:
2688 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
2689 for e in internal_edges]
2690 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
2691 verify_properties = ('multi_edge_forest',)
2692 verify_and_dot('prekruskal', graph_edges, graph_nodes, label=label,
2693 properties=verify_properties, debug=DEBUG,
2695 dot_files=opts.dot_files)
2697 # Phase 2: Run Kruskal's on the internal edges
2698 output_edges, components = kruskal(graph, internal_edges)
2700 # This recalculates the cost for the path connecting the
2701 # closest red vertex. Ignoring types is fine because NO
2702 # suboptimal edge should exist in the graph
2703 dijkstra(graph, "EDGE_TYPE_ALL", False) # TODO rename
2704 # Phase 3: Process the output
2705 for v in graph.vertices:
2709 v.dist_to_red = v.repl_info.cost
2711 if opts.verify or opts.dot_files:
2712 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
2713 for e in internal_edges]
2714 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
2715 verify_properties = ('multi_edge_forest',)
2716 verify_and_dot('postkruskal', graph_edges, graph_nodes,
2717 label=label, properties=verify_properties,
2718 debug=DEBUG, verify=opts.verify,
2719 dot_files=opts.dot_files)
2721 # Ensure only one-way connections for partial-replicas,
2722 # and make sure they point the right way.
2724 for edge in output_edges:
2725 # We know these edges only have two endpoints because we made
2727 v, w = edge.vertices
2728 if v.site is my_site or w.site is my_site:
2729 if (((v.is_black() or w.is_black()) and
2730 v.dist_to_red != MAX_DWORD)):
2731 edge.directed = True
2733 if w.dist_to_red < v.dist_to_red:
2734 edge.vertices[:] = w, v
2735 edge_list.append(edge)
2737 if opts.verify or opts.dot_files:
2738 graph_edges = [[x.site.site_dnstr for x in e.vertices]
2740 #add the reverse edge if not directed.
2741 graph_edges.extend([x.site.site_dnstr
2742 for x in reversed(e.vertices)]
2743 for e in edge_list if not e.directed)
2744 graph_nodes = [x.site.site_dnstr for x in graph.vertices]
2745 verify_properties = ()
2746 verify_and_dot('post-one-way-partial', graph_edges, graph_nodes,
2747 label=label, properties=verify_properties,
2748 debug=DEBUG, verify=opts.verify,
2750 dot_files=opts.dot_files)
2752 # count the components
2753 return edge_list, components
2756 def sort_replica_by_dsa_guid(rep1, rep2):
2757 """Helper to sort NCReplicas by their DSA guids
2759 The guids need to be sorted in their NDR form.
2761 :param rep1: An NC replica
2762 :param rep2: Another replica
2763 :return: -1, 0, or 1, indicating sort order.
2765 return cmp(ndr_pack(rep1.rep_dsa_guid), ndr_pack(rep2.rep_dsa_guid))
2768 def sort_dsa_by_gc_and_guid(dsa1, dsa2):
2769 """Helper to sort DSAs by guid global catalog status
2771 GC DSAs come before non-GC DSAs, other than that, the guids are
2774 :param dsa1: A DSA object
2775 :param dsa2: Another DSA
2776 :return: -1, 0, or 1, indicating sort order.
2778 if dsa1.is_gc() and not dsa2.is_gc():
2780 if not dsa1.is_gc() and dsa2.is_gc():
2782 return cmp(ndr_pack(dsa1.dsa_guid), ndr_pack(dsa2.dsa_guid))
2785 def is_smtp_replication_available():
2786 """Can the KCC use SMTP replication?
2788 Currently always returns false because Samba doesn't implement
2789 SMTP transfer for NC changes between DCs.
2791 :return: Boolean (always False)
2796 def create_edge(con_type, site_link, guid_to_vertex):
2798 e.site_link = site_link
2800 for site_guid in site_link.site_list:
2801 if str(site_guid) in guid_to_vertex:
2802 e.vertices.extend(guid_to_vertex.get(str(site_guid)))
2803 e.repl_info.cost = site_link.cost
2804 e.repl_info.options = site_link.options
2805 e.repl_info.interval = site_link.interval
2806 e.repl_info.schedule = convert_schedule_to_repltimes(site_link.schedule)
2807 e.con_type = con_type
2812 def create_auto_edge_set(graph, transport):
2813 e_set = MultiEdgeSet()
2814 # use a NULL guid, not associated with a SiteLinkBridge object
2815 e_set.guid = misc.GUID()
2816 for site_link in graph.edges:
2817 if site_link.con_type == transport:
2818 e_set.edges.append(site_link)
2823 def create_edge_set(graph, transport, site_link_bridge):
2824 # TODO not implemented - need to store all site link bridges
2825 e_set = MultiEdgeSet()
2826 # e_set.guid = site_link_bridge
2830 def setup_vertices(graph):
2831 for v in graph.vertices:
2833 v.repl_info.cost = MAX_DWORD
2835 v.component_id = None
2837 v.repl_info.cost = 0
2841 v.repl_info.interval = 0
2842 v.repl_info.options = 0xFFFFFFFF
2843 v.repl_info.schedule = None # TODO highly suspicious
2847 def dijkstra(graph, edge_type, include_black):
2849 setup_dijkstra(graph, edge_type, include_black, queue)
2850 while len(queue) > 0:
2851 cost, guid, vertex = heapq.heappop(queue)
2852 for edge in vertex.edges:
2853 for v in edge.vertices:
2855 # add new path from vertex to v
2856 try_new_path(graph, queue, vertex, edge, v)
2859 def setup_dijkstra(graph, edge_type, include_black, queue):
2860 setup_vertices(graph)
2861 for vertex in graph.vertices:
2862 if vertex.is_white():
2865 if (((vertex.is_black() and not include_black)
2866 or edge_type not in vertex.accept_black
2867 or edge_type not in vertex.accept_red_red)):
2868 vertex.repl_info.cost = MAX_DWORD
2869 vertex.root = None # NULL GUID
2870 vertex.demoted = True # Demoted appears not to be used
2872 heapq.heappush(queue, (vertex.repl_info.cost, vertex.guid, vertex))
2875 def try_new_path(graph, queue, vfrom, edge, vto):
2877 # What this function checks is that there is a valid time frame for
2878 # which replication can actually occur, despite being adequately
2880 intersect = combine_repl_info(vfrom.repl_info, edge.repl_info, newRI)
2882 # If the new path costs more than the current, then ignore the edge
2883 if newRI.cost > vto.repl_info.cost:
2886 if newRI.cost < vto.repl_info.cost and not intersect:
2889 new_duration = total_schedule(newRI.schedule)
2890 old_duration = total_schedule(vto.repl_info.schedule)
2892 # Cheaper or longer schedule
2893 if newRI.cost < vto.repl_info.cost or new_duration > old_duration:
2894 vto.root = vfrom.root
2895 vto.component_id = vfrom.component_id
2896 vto.repl_info = newRI
2897 heapq.heappush(queue, (vto.repl_info.cost, vto.guid, vto))
2900 def check_demote_vertex(vertex, edge_type):
2901 if vertex.is_white():
2904 # Accepts neither red-red nor black edges, demote
2905 if ((edge_type not in vertex.accept_black and
2906 edge_type not in vertex.accept_red_red)):
2907 vertex.repl_info.cost = MAX_DWORD
2909 vertex.demoted = True # Demoted appears not to be used
2912 def undemote_vertex(vertex):
2913 if vertex.is_white():
2916 vertex.repl_info.cost = 0
2917 vertex.root = vertex
2918 vertex.demoted = False
2921 def process_edge_set(graph, e_set, internal_edges):
2923 for edge in graph.edges:
2924 for vertex in edge.vertices:
2925 check_demote_vertex(vertex, edge.con_type)
2926 process_edge(graph, edge, internal_edges)
2927 for vertex in edge.vertices:
2928 undemote_vertex(vertex)
2930 for edge in e_set.edges:
2931 process_edge(graph, edge, internal_edges)
2934 def process_edge(graph, examine, internal_edges):
2935 # Find the set of all vertices touches the edge to examine
2937 for v in examine.vertices:
2938 # Append a 4-tuple of color, repl cost, guid and vertex
2939 vertices.append((v.color, v.repl_info.cost, v.ndrpacked_guid, v))
2940 # Sort by color, lower
2941 DEBUG("vertices is %s" % vertices)
2944 color, cost, guid, bestv = vertices[0]
2945 # Add to internal edges an edge from every colored vertex to bestV
2946 for v in examine.vertices:
2947 if v.component_id is None or v.root is None:
2950 # Only add edge if valid inter-tree edge - needs a root and
2951 # different components
2952 if ((bestv.component_id is not None and
2953 bestv.root is not None and
2954 v.component_id is not None and
2955 v.root is not None and
2956 bestv.component_id != v.component_id)):
2957 add_int_edge(graph, internal_edges, examine, bestv, v)
2960 # Add internal edge, endpoints are roots of the vertices to pass in
2961 # and are always colored
2962 def add_int_edge(graph, internal_edges, examine, v1, v2):
2967 if root1.is_red() and root2.is_red():
2971 if ((examine.con_type not in root1.accept_red_red
2972 or examine.con_type not in root2.accept_red_red)):
2974 elif (examine.con_type not in root1.accept_black
2975 or examine.con_type not in root2.accept_black):
2981 # Create the transitive replInfo for the two trees and this edge
2982 if not combine_repl_info(v1.repl_info, v2.repl_info, ri):
2984 # ri is now initialized
2985 if not combine_repl_info(ri, examine.repl_info, ri2):
2988 newIntEdge = InternalEdge(root1, root2, red_red, ri2, examine.con_type,
2990 # Order by vertex guid
2991 #XXX guid comparison using ndr_pack
2992 if newIntEdge.v1.ndrpacked_guid > newIntEdge.v2.ndrpacked_guid:
2993 newIntEdge.v1 = root2
2994 newIntEdge.v2 = root1
2996 internal_edges.add(newIntEdge)
2999 def kruskal(graph, edges):
3000 for v in graph.vertices:
3003 components = set([x for x in graph.vertices if not x.is_white()])
3006 # Sorted based on internal comparison function of internal edge
3009 #XXX expected_num_tree_edges is never used
3010 expected_num_tree_edges = 0 # TODO this value makes little sense
3015 while index < len(edges): # TODO and num_components > 1
3017 parent1 = find_component(e.v1)
3018 parent2 = find_component(e.v2)
3019 if parent1 is not parent2:
3021 add_out_edge(graph, output_edges, e)
3022 parent1.component_id = parent2
3023 components.discard(parent1)
3027 return output_edges, len(components)
3030 def find_component(vertex):
3031 if vertex.component_id is vertex:
3035 while current.component_id is not current:
3036 current = current.component_id
3040 while current.component_id is not root:
3041 n = current.component_id
3042 current.component_id = root
3048 def add_out_edge(graph, output_edges, e):
3052 # This multi-edge is a 'real' edge with no GUID
3055 ee.site_link = e.site_link
3056 ee.vertices.append(v1)
3057 ee.vertices.append(v2)
3058 ee.con_type = e.e_type
3059 ee.repl_info = e.repl_info
3060 output_edges.append(ee)
3066 def test_all_reps_from(lp, creds, rng_seed=None):
3068 kcc.load_samdb(opts.dburl, lp, creds)
3069 dsas = kcc.list_dsas()
3074 for site in kcc.site_table.values():
3075 guid_to_dnstr.update((str(dsa.dsa_guid), dnstr)
3076 for dnstr, dsa in site.dsa_table.items())
3085 random.seed(rng_seed)
3087 kcc.run(opts.dburl, lp, creds, forced_local_dsa=dsa_dn,
3088 forget_local_links=opts.forget_local_links,
3089 forget_intersite_links=opts.forget_intersite_links)
3091 current, needed = kcc.my_dsa.get_rep_tables()
3093 for dsa in kcc.my_site.dsa_table.values():
3094 if dsa is kcc.my_dsa:
3096 kcc.translate_ntdsconn(dsa)
3097 c, n = dsa.get_rep_tables()
3101 for name, rep_table, rep_parts in (
3102 ('needed', needed, needed_parts),
3103 ('current', current, current_parts)):
3104 for part, nc_rep in rep_table.items():
3105 edges = rep_parts.setdefault(part, [])
3106 for reps_from in nc_rep.rep_repsFrom:
3107 source = guid_to_dnstr[str(reps_from.source_dsa_obj_guid)]
3108 dest = guid_to_dnstr[str(nc_rep.rep_dsa_guid)]
3109 edges.append((source, dest))
3111 for site in kcc.site_table.values():
3112 for dsa in site.dsa_table.values():
3114 vertex_colours.append('#cc0000')
3116 vertex_colours.append('#0000cc')
3117 dot_vertices.append(dsa.dsa_dnstr)
3118 if dsa.connect_table:
3119 DEBUG_FN("DSA %s %s connections:\n%s" %
3120 (dsa.dsa_dnstr, len(dsa.connect_table),
3121 [x.from_dnstr for x in
3122 dsa.connect_table.values()]))
3123 for con in dsa.connect_table.values():
3124 if con.is_rodc_topology():
3125 colours.append('red')
3127 colours.append('blue')
3128 dot_edges.append((con.from_dnstr, dsa.dsa_dnstr))
3130 verify_and_dot('all-dsa-connections', dot_edges, vertices=dot_vertices,
3131 label="all dsa NTDSConnections", properties=(),
3132 debug=DEBUG, verify=opts.verify, dot_files=opts.dot_files,
3133 directed=True, edge_colors=colours,
3134 vertex_colors=vertex_colours)
3136 for name, rep_parts in (('needed', needed_parts),
3137 ('current', current_parts)):
3138 for part, edges in rep_parts.items():
3139 verify_and_dot('all-repsFrom_%s__%s' % (name, part), edges,
3140 directed=True, label=part,
3141 properties=(), debug=DEBUG, verify=opts.verify,
3142 dot_files=opts.dot_files)
3145 logger = logging.getLogger("samba_kcc")
3146 logger.addHandler(logging.StreamHandler(sys.stdout))
3147 DEBUG = logger.debug
3150 def _color_debug(*args, **kwargs):
3151 DEBUG('%s%s%s' % (kwargs['color'], args[0], C_NORMAL), *args[1:])
3153 _globals = globals()
3154 for _color in ('DARK_RED', 'RED', 'DARK_GREEN', 'GREEN', 'YELLOW',
3155 'DARK_YELLOW', 'DARK_BLUE', 'BLUE', 'PURPLE', 'MAGENTA',
3156 'DARK_CYAN', 'CYAN', 'GREY', 'WHITE', 'REV_RED'):
3157 _globals['DEBUG_' + _color] = partial(_color_debug, color=_globals[_color])
3160 def DEBUG_FN(msg=''):
3162 filename, lineno, function, text = traceback.extract_stack(None, 2)[0]
3163 DEBUG("%s%s:%s%s %s%s()%s '%s'" % (CYAN, filename, BLUE, lineno,
3164 CYAN, function, C_NORMAL, msg))
3167 ##################################################
3168 # samba_kcc entry point
3169 ##################################################
3171 parser = optparse.OptionParser("samba_kcc [options]")
3172 sambaopts = options.SambaOptions(parser)
3173 credopts = options.CredentialsOptions(parser)
3175 parser.add_option_group(sambaopts)
3176 parser.add_option_group(credopts)
3177 parser.add_option_group(options.VersionOptions(parser))
3179 parser.add_option("--readonly", default=False,
3180 help="compute topology but do not update database",
3181 action="store_true")
3183 parser.add_option("--debug",
3184 help="debug output",
3185 action="store_true")
3187 parser.add_option("--verify",
3188 help="verify that assorted invariants are kept",
3189 action="store_true")
3191 parser.add_option("--list-verify-tests",
3192 help=("list what verification actions are available "
3193 "and do nothing else"),
3194 action="store_true")
3196 parser.add_option("--no-dot-files", dest='dot_files',
3197 help="Don't write dot graph files in /tmp",
3198 default=True, action="store_false")
3200 parser.add_option("--seed",
3201 help="random number seed",
3204 parser.add_option("--importldif",
3205 help="import topology ldif file",
3206 type=str, metavar="<file>")
3208 parser.add_option("--exportldif",
3209 help="export topology ldif file",
3210 type=str, metavar="<file>")
3212 parser.add_option("-H", "--URL",
3213 help="LDB URL for database or target server",
3214 type=str, metavar="<URL>", dest="dburl")
3216 parser.add_option("--tmpdb",
3217 help="schemaless database file to create for ldif import",
3218 type=str, metavar="<file>")
3220 parser.add_option("--now",
3221 help=("assume current time is this ('YYYYmmddHHMMSS[tz]',"
3222 " default: system time)"),
3223 type=str, metavar="<date>")
3225 parser.add_option("--forced-local-dsa",
3226 help="run calculations assuming the DSA is this DN",
3227 type=str, metavar="<DSA>")
3229 parser.add_option("--attempt-live-connections", default=False,
3230 help="Attempt to connect to other DSAs to test links",
3231 action="store_true")
3233 parser.add_option("--list-valid-dsas", default=False,
3234 help=("Print a list of DSA dnstrs that could be"
3235 " used in --forced-local-dsa"),
3236 action="store_true")
3238 parser.add_option("--test-all-reps-from", default=False,
3239 help="Create and verify a graph of reps-from for every DSA",
3240 action="store_true")
3242 parser.add_option("--forget-local-links", default=False,
3243 help="pretend not to know the existing local topology",
3244 action="store_true")
3246 parser.add_option("--forget-intersite-links", default=False,
3247 help="pretend not to know the existing intersite topology",
3248 action="store_true")
3251 opts, args = parser.parse_args()
3254 if opts.list_verify_tests:
3259 logger.setLevel(logging.DEBUG)
3261 logger.setLevel(logging.INFO)
3263 logger.setLevel(logging.WARNING)
3265 # initialize seed from optional input parameter
3267 random.seed(opts.seed)
3269 random.seed(0xACE5CA11)
3272 for timeformat in ("%Y%m%d%H%M%S%Z", "%Y%m%d%H%M%S"):
3274 now_tuple = time.strptime(opts.now, timeformat)
3279 # else happens if break doesn't --> no match
3280 print >> sys.stderr, "could not parse time '%s'" % opts.now
3283 unix_now = int(time.mktime(now_tuple))
3285 unix_now = int(time.time())
3287 nt_now = unix2nttime(unix_now)
3289 lp = sambaopts.get_loadparm()
3290 creds = credopts.get_credentials(lp, fallback_machine=True)
3292 if opts.dburl is None:
3293 opts.dburl = lp.samdb_url()
3295 if opts.test_all_reps_from:
3296 opts.readonly = True
3297 rng_seed = opts.seed or 0xACE5CA11
3298 test_all_reps_from(lp, creds, rng_seed=rng_seed)
3301 # Instantiate Knowledge Consistency Checker and perform run
3305 rc = kcc.export_ldif(opts.dburl, lp, creds, opts.exportldif)
3309 if opts.tmpdb is None or opts.tmpdb.startswith('ldap'):
3310 logger.error("Specify a target temp database file with --tmpdb option")
3313 rc = kcc.import_ldif(opts.tmpdb, lp, creds, opts.importldif)
3317 if opts.list_valid_dsas:
3318 kcc.load_samdb(opts.dburl, lp, creds)
3319 print '\n'.join(kcc.list_dsas())
3323 rc = kcc.run(opts.dburl, lp, creds, opts.forced_local_dsa,
3324 opts.forget_local_links, opts.forget_intersite_links)
3327 except GraphError, e: