3 # Compute our KCC topology
5 # Copyright (C) Dave Craft 2011
7 # This program is free software; you can redistribute it and/or modify
8 # it under the terms of the GNU General Public License as published by
9 # the Free Software Foundation; either version 3 of the License, or
10 # (at your option) any later version.
12 # This program is distributed in the hope that it will be useful,
13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 # GNU General Public License for more details.
17 # You should have received a copy of the GNU General Public License
18 # along with this program. If not, see <http://www.gnu.org/licenses/>.
24 # ensure we get messages out immediately, so they get in the samba logs,
25 # and don't get swallowed by a timeout
26 os.environ['PYTHONUNBUFFERED'] = '1'
28 # forcing GMT avoids a problem in some timezones with kerberos. Both MIT
29 # heimdal can get mutual authentication errors due to the 24 second difference
30 # between UTC and GMT when using some zone files (eg. the PDT zone from
32 os.environ["TZ"] = "GMT"
34 # Find right directory when running from source tree
35 sys.path.insert(0, "bin/python")
41 from samba import getopt as options
42 from samba.auth import system_session
43 from samba.samdb import SamDB
44 from samba.kcc_utils import *
47 """The Knowledge Consistency Checker class. A container for
48 objects and methods allowing a run of the KCC. Produces
49 a set of connections in the samdb for which the Distributed
50 Replication Service can then utilize to replicate naming
53 def __init__(self, samdb):
54 """Initializes the partitions class which can hold
55 our local DCs partitions or all the partitions in
58 self.dsa_table = {} # dsa objects
59 self.part_table = {} # partition objects
61 self.my_dsa_dnstr = None # My dsa DN
62 self.my_site_dnstr = None
66 def load_my_site(self):
67 """Loads the Site class for the local DSA
68 Raises an Exception on error
70 self.my_site_dnstr = "CN=%s,CN=Sites,%s" % (samdb.server_site_name(),
71 samdb.get_config_basedn())
72 site = Site(self.my_site_dnstr)
75 self.site_table[self.my_site_dnstr] = site
78 def load_my_dsa(self):
79 """Discover my nTDSDSA thru the rootDSE entry and
80 instantiate and load the DSA. The dsa is inserted
81 into the dsa_table by dn string
82 Raises an Exception on error.
84 dn = ldb.Dn(self.samdb, "")
86 res = samdb.search(base=dn, scope=ldb.SCOPE_BASE,
87 attrs=["dsServiceName"])
88 except ldb.LdbError, (enum, estr):
89 raise Exception("Unable to find my nTDSDSA - (%s)" % estr)
92 dnstr = res[0]["dsServiceName"][0]
95 if dnstr in self.dsa_table.keys():
98 self.my_dsa_dnstr = dnstr
99 dsa = DirectoryServiceAgent(dnstr)
103 # Assign this dsa to my dsa table
104 # and index by dsa dn
105 self.dsa_table[dnstr] = dsa
109 def load_all_dsa(self):
110 """Discover all nTDSDSA thru the sites entry and
111 instantiate and load the DSAs. Each dsa is inserted
112 into the dsa_table by dn string.
113 Raises an Exception on error.
116 res = self.samdb.search("CN=Sites,%s" %
117 self.samdb.get_config_basedn(),
118 scope=ldb.SCOPE_SUBTREE,
119 expression="(objectClass=nTDSDSA)")
120 except ldb.LdbError, (enum, estr):
121 raise Exception("Unable to find nTDSDSAs - (%s)" % estr)
128 if dnstr in self.dsa_table.keys():
131 dsa = DirectoryServiceAgent(dnstr)
133 dsa.load_dsa(self.samdb)
135 # Assign this dsa to my dsa table
136 # and index by dsa dn
137 self.dsa_table[dnstr] = dsa
141 def load_all_partitions(self):
142 """Discover all NCs thru the Partitions dn and
143 instantiate and load the NCs. Each NC is inserted
144 into the part_table by partition dn string (not
145 the nCName dn string)
146 Raises an Exception on error
149 res = self.samdb.search("CN=Partitions,%s" %
150 self.samdb.get_config_basedn(),
151 scope=ldb.SCOPE_SUBTREE,
152 expression="(objectClass=crossRef)")
153 except ldb.LdbError, (enum, estr):
154 raise Exception("Unable to find partitions - (%s)" % estr)
157 partstr = str(msg.dn)
160 if partstr in self.part_table.keys():
163 part = Partition(partstr)
165 part.load_partition(self.samdb)
166 self.part_table[partstr] = part
170 def should_be_present_test(self):
171 """Enumerate all loaded partitions and DSAs and test
172 if NC should be present as replica
174 for partdn, part in self.part_table.items():
176 for dsadn, dsa in self.dsa_table.items():
177 needed, ro, partial = part.should_be_present(dsa)
179 logger.info("dsadn:%s\nncdn:%s\nneeded=%s:ro=%s:partial=%s\n" % \
180 (dsa.dsa_dnstr, part.nc_dnstr, needed, ro, partial))
183 def refresh_failed_links_connections(self):
184 # XXX - not implemented yet
187 def is_stale_link_connection(self, target_dsa):
188 """Returns False if no tuple z exists in the kCCFailedLinks or
189 kCCFailedConnections variables such that z.UUIDDsa is the
190 objectGUID of the target dsa, z.FailureCount > 0, and
191 the current time - z.TimeFirstFailure > 2 hours.
193 # XXX - not implemented yet
196 def remove_unneeded_failed_links_connections(self):
197 # XXX - not implemented yet
200 def remove_unneeded_ntds_connections(self):
201 # XXX - not implemented yet
204 def translate_connections(self):
205 # XXX - not implemented yet
209 """The head method for generating the inter-site KCC replica
210 connection graph and attendant nTDSConnection objects
213 # XXX - not implemented yet
216 def update_rodc_connection(self):
217 """Runs when the local DC is an RODC and updates the RODC NTFRS
220 # Given an nTDSConnection object cn1, such that cn1.options contains
221 # NTDSCONN_OPT_RODC_TOPOLOGY, and another nTDSConnection object cn2,
222 # does not contain NTDSCONN_OPT_RODC_TOPOLOGY, modify cn1 to ensure
223 # that the following is true:
225 # cn1.fromServer = cn2.fromServer
226 # cn1.schedule = cn2.schedule
228 # If no such cn2 can be found, cn1 is not modified.
229 # If no such cn1 can be found, nothing is modified by this task.
231 # XXX - not implemented yet
234 def intrasite_max_node_edges(self, node_count):
235 """Returns the maximum number of edges directed to a node in
236 the intrasite replica graph. The KCC does not create more
237 than 50 edges directed to a single DC. To optimize replication,
238 we compute that each node should have n+2 total edges directed
239 to it such that (n) is the smallest non-negative integer
240 satisfying (node_count <= 2*(n*n) + 6*n + 7)
241 :param node_count: total number of nodes in the replica graph
245 if node_count <= (2 * (n * n) + (6 * n) + 7):
253 def construct_intrasite_graph(self, site_local, dc_local,
254 nc_x, gc_only, detect_stale):
256 # We're using the MS notation names here to allow
257 # correlation back to the published algorithm.
259 # nc_x - naming context (x) that we are testing if it
260 # "should be present" on the local DC
261 # f_of_x - replica (f) found on a DC (s) for NC (x)
262 # dc_s - DC where f_of_x replica was found
263 # dc_local - local DC that potentially needs a replica
265 # r_list - replica list R
266 # p_of_x - replica (p) is partial and found on a DC (s)
268 # l_of_x - replica (l) is the local replica for NC (x)
269 # that should appear on the local DC
270 # r_len = is length of replica list |R|
272 # If the DSA doesn't need a replica for this
273 # partition (NC x) then continue
274 needed, ro, partial = nc_x.should_be_present(dc_local)
276 logger.debug("construct_intrasite_graph:\n" + \
277 "nc_x: %s\ndc_local: %s\n" % \
279 "gc_only: %s\nneeded: %s\nro: %s\npartial: %s" % \
280 (gc_only, needed, ro, partial))
285 # Create a NCReplica that matches what the local replica
286 # should say. We'll use this below in our r_list
287 l_of_x = NCReplica(dc_local.dsa_dnstr, dc_local.dsa_guid, \
288 nc_x.nc_dnstr, nc_x.nc_guid, nc_x.nc_sid)
290 l_of_x.identify_by_basedn(self.samdb)
292 l_of_x.rep_partial = partial
295 # Empty replica sequence list
298 # We'll loop thru all the DSAs looking for
299 # writeable NC replicas that match the naming
300 # context dn for (nc_x)
302 for dc_s_dn, dc_s in self.dsa_table.items():
304 # If this partition (nc_x) doesn't appear as a
305 # replica (f_of_x) on (dc_s) then continue
306 if not nc_x.nc_dnstr in dc_s.rep_table.keys():
309 # Pull out the NCReplica (f) of (x) with the dn
310 # that matches NC (x) we are examining.
311 f_of_x = dc_s.rep_table[nc_x.nc_dnstr]
313 # Replica (f) of NC (x) must be writable
314 if f_of_x.is_ro() == True:
317 # Replica (f) of NC (x) must satisfy the
318 # "is present" criteria for DC (s) that
320 if f_of_x.is_present() == False:
323 # DC (s) must be a writable DSA other than
324 # my local DC. In other words we'd only replicate
325 # from other writable DC
326 if dc_s.is_ro() or dc_s is dc_local:
329 # Certain replica graphs are produced only
330 # for global catalogs, so test against
331 # method input parameter
332 if gc_only and dc_s.is_gc() == False:
335 # DC (s) must be in the same site as the local DC
336 # This is the intra-site algorithm. We are not
337 # replicating across multiple sites
338 if site_local.is_same_site(dc_s) == False:
341 # If NC (x) is intended to be read-only full replica
342 # for a domain NC on the target DC then the source
343 # DC should have functional level at minimum WIN2008
345 # Effectively we're saying that in order to replicate
346 # to a targeted RODC (which was introduced in Windows 2008)
347 # then we have to replicate from a DC that is also minimally
350 # You can also see this requirement in the MS special
351 # considerations for RODC which state that to deploy
352 # an RODC, at least one writable domain controller in
353 # the domain must be running Windows Server 2008
354 if ro and partial == False and nc_x.nc_type == NCType.domain:
355 if dc_s.is_minimum_behavior(DS_BEHAVIOR_WIN2008) == False:
358 # If we haven't been told to turn off stale connection
359 # detection and this dsa has a stale connection then
361 if detect_stale and self.is_stale_link_connection(dc_s) == True:
364 # Replica meets criteria. Add it to table indexed
365 # by the GUID of the DC that it appears on
366 r_list.append(f_of_x)
368 # If a partial (not full) replica of NC (x) "should be present"
369 # on the local DC, append to R each partial replica (p of x)
370 # such that p "is present" on a DC satisfying the same
371 # criteria defined above for full replica DCs.
374 # Now we loop thru all the DSAs looking for
375 # partial NC replicas that match the naming
376 # context dn for (NC x)
377 for dc_s_dn, dc_s in self.dsa_table.items():
379 # If this partition NC (x) doesn't appear as a
380 # replica (p) of NC (x) on the dsa DC (s) then
382 if not nc_x.nc_dnstr in dc_s.rep_table.keys():
385 # Pull out the NCReplica with the dn that
386 # matches NC (x) we are examining.
387 p_of_x = dsa.rep_table[nc_x.nc_dnstr]
389 # Replica (p) of NC (x) must be partial
390 if p_of_x.is_partial() == False:
393 # Replica (p) of NC (x) must satisfy the
394 # "is present" criteria for DC (s) that
396 if p_of_x.is_present() == False:
399 # DC (s) must be a writable DSA other than
400 # my DSA. In other words we'd only replicate
401 # from other writable DSA
402 if dc_s.is_ro() or dc_s is dc_local:
405 # Certain replica graphs are produced only
406 # for global catalogs, so test against
407 # method input parameter
408 if gc_only and dc_s.is_gc() == False:
411 # DC (s) must be in the same site as the local DC
412 # This is the intra-site algorithm. We are not
413 # replicating across multiple sites
414 if site_local.is_same_site(dc_s) == False:
417 # This criteria is moot (a no-op) for this case
418 # because we are scanning for (partial = True). The
419 # MS algorithm statement says partial replica scans
420 # should adhere to the "same" criteria as full replica
421 # scans so the criteria doesn't change here...its just
422 # rendered pointless.
424 # The case that is occurring would be a partial domain
425 # replica is needed on a local DC global catalog. There
426 # is no minimum windows behavior for those since GCs
427 # have always been present.
428 if ro and partial == False and nc_x.nc_type == NCType.domain:
429 if dc_s.is_minimum_behavior(DS_BEHAVIOR_WIN2008) == False:
432 # If we haven't been told to turn off stale connection
433 # detection and this dsa has a stale connection then
435 if detect_stale and self.is_stale_link_connection(dc_s) == True:
438 # Replica meets criteria. Add it to table indexed
439 # by the GUID of the DSA that it appears on
440 r_list.append(p_of_x)
442 # Append to R the NC replica that "should be present"
444 r_list.append(l_of_x)
446 r_list.sort(sort_replica_by_dsa_guid)
450 max_node_edges = self.intrasite_max_node_edges(r_len)
452 # Add a node for each r_list element to the replica graph
455 node = GraphNode(rep.rep_dsa_dnstr, max_node_edges)
456 graph_list.append(node)
458 # For each r(i) from (0 <= i < |R|-1)
461 # Add an edge from r(i) to r(i+1) if r(i) is a full
462 # replica or r(i+1) is a partial replica
463 if r_list[i].is_partial() == False or \
464 r_list[i+1].is_partial() == True:
465 graph_list[i+1].add_edge_from(r_list[i].rep_dsa_dnstr)
467 # Add an edge from r(i+1) to r(i) if r(i+1) is a full
468 # replica or ri is a partial replica.
469 if r_list[i+1].is_partial() == False or \
470 r_list[i].is_partial() == True:
471 graph_list[i].add_edge_from(r_list[i+1].rep_dsa_dnstr)
474 # Add an edge from r|R|-1 to r0 if r|R|-1 is a full replica
475 # or r0 is a partial replica.
476 if r_list[r_len-1].is_partial() == False or \
477 r_list[0].is_partial() == True:
478 graph_list[0].add_edge_from(r_list[r_len-1].rep_dsa_dnstr)
480 # Add an edge from r0 to r|R|-1 if r0 is a full replica or
481 # r|R|-1 is a partial replica.
482 if r_list[0].is_partial() == False or \
483 r_list[r_len-1].is_partial() == True:
484 graph_list[r_len-1].add_edge_from(r_list[0].rep_dsa_dnstr)
486 # For each existing nTDSConnection object implying an edge
487 # from rj of R to ri such that j != i, an edge from rj to ri
488 # is not already in the graph, and the total edges directed
489 # to ri is less than n+2, the KCC adds that edge to the graph.
492 dsa = self.dsa_table[graph_list[i].dsa_dnstr]
493 graph_list[i].add_edges_from_connections(dsa)
498 tnode = graph_list[i]
500 # To optimize replication latency in sites with many NC replicas, the
501 # KCC adds new edges directed to ri to bring the total edges to n+2,
502 # where the NC replica rk of R from which the edge is directed
503 # is chosen at random such that k != i and an edge from rk to ri
504 # is not already in the graph.
506 # Note that the KCC tech ref does not give a number for the definition
507 # of "sites with many NC replicas". At a bare minimum to satisfy
508 # n+2 edges directed at a node we have to have at least three replicas
509 # in |R| (i.e. if n is zero then at least replicas from two other graph
510 # nodes may direct edges to us).
512 # pick a random index
513 findex = rindex = random.randint(0, r_len-1)
515 # while this node doesn't have sufficient edges
516 while tnode.has_sufficient_edges() == False:
517 # If this edge can be successfully added (i.e. not
518 # the same node and edge doesn't already exist) then
519 # select a new random index for the next round
520 if tnode.add_edge_from(graph_list[rindex].dsa_dnstr) == True:
521 findex = rindex = random.randint(0, r_len-1)
523 # Otherwise continue looking against each node
524 # after the random selection
530 logger.error("Unable to satisfy max edge criteria!")
533 # Print the graph node in debug mode
534 logger.debug("%s" % tnode)
536 # For each edge directed to the local DC, ensure a nTDSConnection
537 # points to us that satisfies the KCC criteria
538 if graph_list[i].dsa_dnstr == dc_local.dsa_dnstr:
539 graph_list[i].add_connections_from_edges(dc_local)
546 """The head method for generating the intra-site KCC replica
547 connection graph and attendant nTDSConnection objects
551 mydsa = self.dsa_table[self.my_dsa_dnstr]
553 logger.debug("intrasite enter:\nmydsa: %s" % mydsa)
555 # Test whether local site has topology disabled
556 mysite = self.site_table[self.my_site_dnstr]
557 if mysite.is_intrasite_topology_disabled():
560 detect_stale = mysite.should_detect_stale()
562 # Loop thru all the partitions.
563 for partdn, part in self.part_table.items():
564 self.construct_intrasite_graph(mysite, mydsa, part, \
568 # If the DC is a GC server, the KCC constructs an additional NC
569 # replica graph (and creates nTDSConnection objects) for the
570 # config NC as above, except that only NC replicas that "are present"
571 # on GC servers are added to R.
572 for partdn, part in self.part_table.items():
574 self.construct_intrasite_graph(mysite, mydsa, part, \
578 # The DC repeats the NC replica graph computation and nTDSConnection
579 # creation for each of the NC replica graphs, this time assuming
580 # that no DC has failed. It does so by re-executing the steps as
581 # if the bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED were
582 # set in the options attribute of the site settings object for
583 # the local DC's site. (ie. we set "detec_stale" flag to False)
585 # Loop thru all the partitions.
586 for partdn, part in self.part_table.items():
587 self.construct_intrasite_graph(mysite, mydsa, part, \
589 False) # don't detect stale
591 # If the DC is a GC server, the KCC constructs an additional NC
592 # replica graph (and creates nTDSConnection objects) for the
593 # config NC as above, except that only NC replicas that "are present"
594 # on GC servers are added to R.
595 for partdn, part in self.part_table.items():
597 self.construct_intrasite_graph(mysite, mydsa, part, \
599 False) # don't detect stale
601 # Commit any newly created connections to the samdb
602 mydsa.commit_connection_table(self.samdb)
604 logger.debug("intrasite exit:\nmydsa: %s" % mydsa)
608 """Method to perform a complete run of the KCC and
609 produce an updated topology for subsequent NC replica
610 syncronization between domain controllers
616 self.load_all_partitions()
619 except Exception, estr:
620 logger.error("%s" % estr)
623 # self.should_be_present_test()
625 # These are the published steps (in order) for the
626 # MS description of the KCC algorithm
629 self.refresh_failed_links_connections()
638 self.remove_unneeded_ntds_connections()
641 self.translate_connections()
644 self.remove_unneeded_failed_links_connections()
647 self.update_rodc_connection()
651 ##################################################
653 ##################################################
654 def sort_replica_by_dsa_guid(rep1, rep2):
655 return cmp(rep1.rep_dsa_guid, rep2.rep_dsa_guid)
657 ##################################################
658 # kcccompute entry point
659 ##################################################
661 parser = optparse.OptionParser("kcccompute [options]")
662 sambaopts = options.SambaOptions(parser)
663 credopts = options.CredentialsOptions(parser)
665 parser.add_option_group(sambaopts)
666 parser.add_option_group(credopts)
667 parser.add_option_group(options.VersionOptions(parser))
669 parser.add_option("--debug", help="debug output", action="store_true")
670 parser.add_option("--seed", help="random number seed")
672 logger = logging.getLogger("kcccompute")
673 logger.addHandler(logging.StreamHandler(sys.stdout))
675 lp = sambaopts.get_loadparm()
676 creds = credopts.get_credentials(lp, fallback_machine=True)
678 opts, args = parser.parse_args()
681 logger.setLevel(logging.DEBUG)
683 logger.setLevel(logging.WARNING)
685 # initialize seed from optional input parameter
687 random.seed(int(opts.seed))
689 random.seed(0xACE5CA11)
691 private_dir = lp.get("private dir")
692 samdb_path = os.path.join(private_dir, "samdb.ldb")
695 samdb = SamDB(url=lp.samdb_url(), session_info=system_session(),
696 credentials=creds, lp=lp)
697 except ldb.LdbError, (num, msg):
698 logger.info("Unable to open sam database %s : %s" % (lp.samdb_url(), msg))
701 # Instantiate Knowledge Consistency Checker and perform run