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
65 def load_my_site(self
):
66 """Loads the Site class for the local DSA
67 Raises an Exception on error
69 self
.my_site_dnstr
= "CN=%s,CN=Sites,%s" % (samdb
.server_site_name(),
70 samdb
.get_config_basedn())
71 site
= Site(self
.my_site_dnstr
)
74 self
.site_table
[self
.my_site_dnstr
] = site
76 def load_my_dsa(self
):
77 """Discover my nTDSDSA thru the rootDSE entry and
78 instantiate and load the DSA. The dsa is inserted
79 into the dsa_table by dn string
80 Raises an Exception on error.
82 dn
= ldb
.Dn(self
.samdb
, "")
84 res
= samdb
.search(base
=dn
, scope
=ldb
.SCOPE_BASE
,
85 attrs
=["dsServiceName"])
86 except ldb
.LdbError
, (enum
, estr
):
87 raise Exception("Unable to find my nTDSDSA - (%s)" % estr
)
89 dnstr
= res
[0]["dsServiceName"][0]
92 if dnstr
in self
.dsa_table
.keys():
95 self
.my_dsa_dnstr
= dnstr
96 dsa
= DirectoryServiceAgent(dnstr
)
100 # Assign this dsa to my dsa table
101 # and index by dsa dn
102 self
.dsa_table
[dnstr
] = dsa
104 def load_all_dsa(self
):
105 """Discover all nTDSDSA thru the sites entry and
106 instantiate and load the DSAs. Each dsa is inserted
107 into the dsa_table by dn string.
108 Raises an Exception on error.
111 res
= self
.samdb
.search("CN=Sites,%s" %
112 self
.samdb
.get_config_basedn(),
113 scope
=ldb
.SCOPE_SUBTREE
,
114 expression
="(objectClass=nTDSDSA)")
115 except ldb
.LdbError
, (enum
, estr
):
116 raise Exception("Unable to find nTDSDSAs - (%s)" % estr
)
122 if dnstr
in self
.dsa_table
.keys():
125 dsa
= DirectoryServiceAgent(dnstr
)
127 dsa
.load_dsa(self
.samdb
)
129 # Assign this dsa to my dsa table
130 # and index by dsa dn
131 self
.dsa_table
[dnstr
] = dsa
133 def load_all_partitions(self
):
134 """Discover all NCs thru the Partitions dn and
135 instantiate and load the NCs. Each NC is inserted
136 into the part_table by partition dn string (not
137 the nCName dn string)
138 Raises an Exception on error
141 res
= self
.samdb
.search("CN=Partitions,%s" %
142 self
.samdb
.get_config_basedn(),
143 scope
=ldb
.SCOPE_SUBTREE
,
144 expression
="(objectClass=crossRef)")
145 except ldb
.LdbError
, (enum
, estr
):
146 raise Exception("Unable to find partitions - (%s)" % estr
)
149 partstr
= str(msg
.dn
)
152 if partstr
in self
.part_table
.keys():
155 part
= Partition(partstr
)
157 part
.load_partition(self
.samdb
)
158 self
.part_table
[partstr
] = part
160 def should_be_present_test(self
):
161 """Enumerate all loaded partitions and DSAs and test
162 if NC should be present as replica
164 for partdn
, part
in self
.part_table
.items():
166 for dsadn
, dsa
in self
.dsa_table
.items():
167 needed
, ro
, partial
= part
.should_be_present(dsa
)
169 logger
.info("dsadn:%s\nncdn:%s\nneeded=%s:ro=%s:partial=%s\n" % \
170 (dsa
.dsa_dnstr
, part
.nc_dnstr
, needed
, ro
, partial
))
172 def refresh_failed_links_connections(self
):
173 # XXX - not implemented yet
176 def is_stale_link_connection(self
, target_dsa
):
177 """Returns False if no tuple z exists in the kCCFailedLinks or
178 kCCFailedConnections variables such that z.UUIDDsa is the
179 objectGUID of the target dsa, z.FailureCount > 0, and
180 the current time - z.TimeFirstFailure > 2 hours.
182 # XXX - not implemented yet
185 def remove_unneeded_failed_links_connections(self
):
186 # XXX - not implemented yet
189 def remove_unneeded_ntds_connections(self
):
190 # XXX - not implemented yet
193 def translate_connections(self
):
194 # XXX - not implemented yet
198 """The head method for generating the inter-site KCC replica
199 connection graph and attendant nTDSConnection objects
202 # XXX - not implemented yet
204 def update_rodc_connection(self
):
205 """Runs when the local DC is an RODC and updates the RODC NTFRS
208 # Given an nTDSConnection object cn1, such that cn1.options contains
209 # NTDSCONN_OPT_RODC_TOPOLOGY, and another nTDSConnection object cn2,
210 # does not contain NTDSCONN_OPT_RODC_TOPOLOGY, modify cn1 to ensure
211 # that the following is true:
213 # cn1.fromServer = cn2.fromServer
214 # cn1.schedule = cn2.schedule
216 # If no such cn2 can be found, cn1 is not modified.
217 # If no such cn1 can be found, nothing is modified by this task.
219 # XXX - not implemented yet
221 def intrasite_max_node_edges(self
, node_count
):
222 """Returns the maximum number of edges directed to a node in
223 the intrasite replica graph. The KCC does not create more
224 than 50 edges directed to a single DC. To optimize replication,
225 we compute that each node should have n+2 total edges directed
226 to it such that (n) is the smallest non-negative integer
227 satisfying (node_count <= 2*(n*n) + 6*n + 7)
228 :param node_count: total number of nodes in the replica graph
232 if node_count
<= (2 * (n
* n
) + (6 * n
) + 7):
240 def construct_intrasite_graph(self
, site_local
, dc_local
,
241 nc_x
, gc_only
, detect_stale
):
243 # We're using the MS notation names here to allow
244 # correlation back to the published algorithm.
246 # nc_x - naming context (x) that we are testing if it
247 # "should be present" on the local DC
248 # f_of_x - replica (f) found on a DC (s) for NC (x)
249 # dc_s - DC where f_of_x replica was found
250 # dc_local - local DC that potentially needs a replica
252 # r_list - replica list R
253 # p_of_x - replica (p) is partial and found on a DC (s)
255 # l_of_x - replica (l) is the local replica for NC (x)
256 # that should appear on the local DC
257 # r_len = is length of replica list |R|
259 # If the DSA doesn't need a replica for this
260 # partition (NC x) then continue
261 needed
, ro
, partial
= nc_x
.should_be_present(dc_local
)
263 logger
.debug("construct_intrasite_graph:\n" + \
264 "nc_x: %s\ndc_local: %s\n" % \
266 "gc_only: %s\nneeded: %s\nro: %s\npartial: %s" % \
267 (gc_only
, needed
, ro
, partial
))
272 # Create a NCReplica that matches what the local replica
273 # should say. We'll use this below in our r_list
274 l_of_x
= NCReplica(dc_local
.dsa_dnstr
, dc_local
.dsa_guid
, \
275 nc_x
.nc_dnstr
, nc_x
.nc_guid
, nc_x
.nc_sid
)
277 l_of_x
.identify_by_basedn(self
.samdb
)
279 l_of_x
.rep_partial
= partial
282 # Empty replica sequence list
285 # We'll loop thru all the DSAs looking for
286 # writeable NC replicas that match the naming
287 # context dn for (nc_x)
289 for dc_s_dn
, dc_s
in self
.dsa_table
.items():
291 # If this partition (nc_x) doesn't appear as a
292 # replica (f_of_x) on (dc_s) then continue
293 if not nc_x
.nc_dnstr
in dc_s
.rep_table
.keys():
296 # Pull out the NCReplica (f) of (x) with the dn
297 # that matches NC (x) we are examining.
298 f_of_x
= dc_s
.rep_table
[nc_x
.nc_dnstr
]
300 # Replica (f) of NC (x) must be writable
301 if f_of_x
.is_ro() == True:
304 # Replica (f) of NC (x) must satisfy the
305 # "is present" criteria for DC (s) that
307 if f_of_x
.is_present() == False:
310 # DC (s) must be a writable DSA other than
311 # my local DC. In other words we'd only replicate
312 # from other writable DC
313 if dc_s
.is_ro() or dc_s
is dc_local
:
316 # Certain replica graphs are produced only
317 # for global catalogs, so test against
318 # method input parameter
319 if gc_only
and dc_s
.is_gc() == False:
322 # DC (s) must be in the same site as the local DC
323 # This is the intra-site algorithm. We are not
324 # replicating across multiple sites
325 if site_local
.is_same_site(dc_s
) == False:
328 # If NC (x) is intended to be read-only full replica
329 # for a domain NC on the target DC then the source
330 # DC should have functional level at minimum WIN2008
332 # Effectively we're saying that in order to replicate
333 # to a targeted RODC (which was introduced in Windows 2008)
334 # then we have to replicate from a DC that is also minimally
337 # You can also see this requirement in the MS special
338 # considerations for RODC which state that to deploy
339 # an RODC, at least one writable domain controller in
340 # the domain must be running Windows Server 2008
341 if ro
and partial
== False and nc_x
.nc_type
== NCType
.domain
:
342 if dc_s
.is_minimum_behavior(DS_BEHAVIOR_WIN2008
) == False:
345 # If we haven't been told to turn off stale connection
346 # detection and this dsa has a stale connection then
348 if detect_stale
and self
.is_stale_link_connection(dc_s
) == True:
351 # Replica meets criteria. Add it to table indexed
352 # by the GUID of the DC that it appears on
353 r_list
.append(f_of_x
)
355 # If a partial (not full) replica of NC (x) "should be present"
356 # on the local DC, append to R each partial replica (p of x)
357 # such that p "is present" on a DC satisfying the same
358 # criteria defined above for full replica DCs.
361 # Now we loop thru all the DSAs looking for
362 # partial NC replicas that match the naming
363 # context dn for (NC x)
364 for dc_s_dn
, dc_s
in self
.dsa_table
.items():
366 # If this partition NC (x) doesn't appear as a
367 # replica (p) of NC (x) on the dsa DC (s) then
369 if not nc_x
.nc_dnstr
in dc_s
.rep_table
.keys():
372 # Pull out the NCReplica with the dn that
373 # matches NC (x) we are examining.
374 p_of_x
= dsa
.rep_table
[nc_x
.nc_dnstr
]
376 # Replica (p) of NC (x) must be partial
377 if p_of_x
.is_partial() == False:
380 # Replica (p) of NC (x) must satisfy the
381 # "is present" criteria for DC (s) that
383 if p_of_x
.is_present() == False:
386 # DC (s) must be a writable DSA other than
387 # my DSA. In other words we'd only replicate
388 # from other writable DSA
389 if dc_s
.is_ro() or dc_s
is dc_local
:
392 # Certain replica graphs are produced only
393 # for global catalogs, so test against
394 # method input parameter
395 if gc_only
and dc_s
.is_gc() == False:
398 # DC (s) must be in the same site as the local DC
399 # This is the intra-site algorithm. We are not
400 # replicating across multiple sites
401 if site_local
.is_same_site(dc_s
) == False:
404 # This criteria is moot (a no-op) for this case
405 # because we are scanning for (partial = True). The
406 # MS algorithm statement says partial replica scans
407 # should adhere to the "same" criteria as full replica
408 # scans so the criteria doesn't change here...its just
409 # rendered pointless.
411 # The case that is occurring would be a partial domain
412 # replica is needed on a local DC global catalog. There
413 # is no minimum windows behavior for those since GCs
414 # have always been present.
415 if ro
and partial
== False and nc_x
.nc_type
== NCType
.domain
:
416 if dc_s
.is_minimum_behavior(DS_BEHAVIOR_WIN2008
) == False:
419 # If we haven't been told to turn off stale connection
420 # detection and this dsa has a stale connection then
422 if detect_stale
and self
.is_stale_link_connection(dc_s
) == True:
425 # Replica meets criteria. Add it to table indexed
426 # by the GUID of the DSA that it appears on
427 r_list
.append(p_of_x
)
429 # Append to R the NC replica that "should be present"
431 r_list
.append(l_of_x
)
433 r_list
.sort(sort_replica_by_dsa_guid
)
437 max_node_edges
= self
.intrasite_max_node_edges(r_len
)
439 # Add a node for each r_list element to the replica graph
442 node
= GraphNode(rep
.rep_dsa_dnstr
, max_node_edges
)
443 graph_list
.append(node
)
445 # For each r(i) from (0 <= i < |R|-1)
448 # Add an edge from r(i) to r(i+1) if r(i) is a full
449 # replica or r(i+1) is a partial replica
450 if r_list
[i
].is_partial() == False or \
451 r_list
[i
+1].is_partial() == True:
452 graph_list
[i
+1].add_edge_from(r_list
[i
].rep_dsa_dnstr
)
454 # Add an edge from r(i+1) to r(i) if r(i+1) is a full
455 # replica or ri is a partial replica.
456 if r_list
[i
+1].is_partial() == False or \
457 r_list
[i
].is_partial() == True:
458 graph_list
[i
].add_edge_from(r_list
[i
+1].rep_dsa_dnstr
)
461 # Add an edge from r|R|-1 to r0 if r|R|-1 is a full replica
462 # or r0 is a partial replica.
463 if r_list
[r_len
-1].is_partial() == False or \
464 r_list
[0].is_partial() == True:
465 graph_list
[0].add_edge_from(r_list
[r_len
-1].rep_dsa_dnstr
)
467 # Add an edge from r0 to r|R|-1 if r0 is a full replica or
468 # r|R|-1 is a partial replica.
469 if r_list
[0].is_partial() == False or \
470 r_list
[r_len
-1].is_partial() == True:
471 graph_list
[r_len
-1].add_edge_from(r_list
[0].rep_dsa_dnstr
)
473 # For each existing nTDSConnection object implying an edge
474 # from rj of R to ri such that j != i, an edge from rj to ri
475 # is not already in the graph, and the total edges directed
476 # to ri is less than n+2, the KCC adds that edge to the graph.
479 dsa
= self
.dsa_table
[graph_list
[i
].dsa_dnstr
]
480 graph_list
[i
].add_edges_from_connections(dsa
)
485 tnode
= graph_list
[i
]
487 # To optimize replication latency in sites with many NC replicas, the
488 # KCC adds new edges directed to ri to bring the total edges to n+2,
489 # where the NC replica rk of R from which the edge is directed
490 # is chosen at random such that k != i and an edge from rk to ri
491 # is not already in the graph.
493 # Note that the KCC tech ref does not give a number for the definition
494 # of "sites with many NC replicas". At a bare minimum to satisfy
495 # n+2 edges directed at a node we have to have at least three replicas
496 # in |R| (i.e. if n is zero then at least replicas from two other graph
497 # nodes may direct edges to us).
499 # pick a random index
500 findex
= rindex
= random
.randint(0, r_len
-1)
502 # while this node doesn't have sufficient edges
503 while tnode
.has_sufficient_edges() == False:
504 # If this edge can be successfully added (i.e. not
505 # the same node and edge doesn't already exist) then
506 # select a new random index for the next round
507 if tnode
.add_edge_from(graph_list
[rindex
].dsa_dnstr
) == True:
508 findex
= rindex
= random
.randint(0, r_len
-1)
510 # Otherwise continue looking against each node
511 # after the random selection
517 logger
.error("Unable to satisfy max edge criteria!")
520 # Print the graph node in debug mode
521 logger
.debug("%s" % tnode
)
523 # For each edge directed to the local DC, ensure a nTDSConnection
524 # points to us that satisfies the KCC criteria
525 if graph_list
[i
].dsa_dnstr
== dc_local
.dsa_dnstr
:
526 graph_list
[i
].add_connections_from_edges(dc_local
)
531 """The head method for generating the intra-site KCC replica
532 connection graph and attendant nTDSConnection objects
536 mydsa
= self
.dsa_table
[self
.my_dsa_dnstr
]
538 logger
.debug("intrasite enter:\nmydsa: %s" % mydsa
)
540 # Test whether local site has topology disabled
541 mysite
= self
.site_table
[self
.my_site_dnstr
]
542 if mysite
.is_intrasite_topology_disabled():
545 detect_stale
= mysite
.should_detect_stale()
547 # Loop thru all the partitions.
548 for partdn
, part
in self
.part_table
.items():
549 self
.construct_intrasite_graph(mysite
, mydsa
, part
, \
553 # If the DC is a GC server, the KCC constructs an additional NC
554 # replica graph (and creates nTDSConnection objects) for the
555 # config NC as above, except that only NC replicas that "are present"
556 # on GC servers are added to R.
557 for partdn
, part
in self
.part_table
.items():
559 self
.construct_intrasite_graph(mysite
, mydsa
, part
, \
563 # The DC repeats the NC replica graph computation and nTDSConnection
564 # creation for each of the NC replica graphs, this time assuming
565 # that no DC has failed. It does so by re-executing the steps as
566 # if the bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED were
567 # set in the options attribute of the site settings object for
568 # the local DC's site. (ie. we set "detec_stale" flag to False)
570 # Loop thru all the partitions.
571 for partdn
, part
in self
.part_table
.items():
572 self
.construct_intrasite_graph(mysite
, mydsa
, part
, \
574 False) # don't detect stale
576 # If the DC is a GC server, the KCC constructs an additional NC
577 # replica graph (and creates nTDSConnection objects) for the
578 # config NC as above, except that only NC replicas that "are present"
579 # on GC servers are added to R.
580 for partdn
, part
in self
.part_table
.items():
582 self
.construct_intrasite_graph(mysite
, mydsa
, part
, \
584 False) # don't detect stale
586 # Commit any newly created connections to the samdb
587 mydsa
.commit_connection_table(self
.samdb
)
589 logger
.debug("intrasite exit:\nmydsa: %s" % mydsa
)
592 """Method to perform a complete run of the KCC and
593 produce an updated topology for subsequent NC replica
594 syncronization between domain controllers
600 self
.load_all_partitions()
603 except Exception, estr
:
604 logger
.error("%s" % estr
)
607 # self.should_be_present_test()
609 # These are the published steps (in order) for the
610 # MS description of the KCC algorithm
613 self
.refresh_failed_links_connections()
622 self
.remove_unneeded_ntds_connections()
625 self
.translate_connections()
628 self
.remove_unneeded_failed_links_connections()
631 self
.update_rodc_connection()
634 ##################################################
636 ##################################################
637 def sort_replica_by_dsa_guid(rep1
, rep2
):
638 return cmp(rep1
.rep_dsa_guid
, rep2
.rep_dsa_guid
)
640 ##################################################
641 # samba_kcc entry point
642 ##################################################
644 parser
= optparse
.OptionParser("samba_kcc [options]")
645 sambaopts
= options
.SambaOptions(parser
)
646 credopts
= options
.CredentialsOptions(parser
)
648 parser
.add_option_group(sambaopts
)
649 parser
.add_option_group(credopts
)
650 parser
.add_option_group(options
.VersionOptions(parser
))
652 parser
.add_option("--debug", help="debug output", action
="store_true")
653 parser
.add_option("--seed", help="random number seed")
655 logger
= logging
.getLogger("samba_kcc")
656 logger
.addHandler(logging
.StreamHandler(sys
.stdout
))
658 lp
= sambaopts
.get_loadparm()
659 creds
= credopts
.get_credentials(lp
, fallback_machine
=True)
661 opts
, args
= parser
.parse_args()
664 logger
.setLevel(logging
.DEBUG
)
666 logger
.setLevel(logging
.WARNING
)
668 # initialize seed from optional input parameter
670 random
.seed(int(opts
.seed
))
672 random
.seed(0xACE5CA11)
674 private_dir
= lp
.get("private dir")
675 samdb_path
= os
.path
.join(private_dir
, "samdb.ldb")
678 samdb
= SamDB(url
=lp
.samdb_url(), session_info
=system_session(),
679 credentials
=creds
, lp
=lp
)
680 except ldb
.LdbError
, (num
, msg
):
681 logger
.info("Unable to open sam database %s : %s" % (lp
.samdb_url(), msg
))
684 # Instantiate Knowledge Consistency Checker and perform run