kcc: fixed tabs/spaces in kcc python implementation
[mat/samba.git] / source4 / scripting / bin / samba_kcc
1 #!/usr/bin/env python
2 #
3 # Compute our KCC topology
4 #
5 # Copyright (C) Dave Craft 2011
6 #
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.
11 #
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.
16 #
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/>.
19
20 import os
21 import sys
22 import random
23
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'
27
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
31 # the US)
32 os.environ["TZ"] = "GMT"
33
34 # Find right directory when running from source tree
35 sys.path.insert(0, "bin/python")
36
37 import samba, ldb
38 import optparse
39 import logging
40
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 *
45
46 class KCC:
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
51        contexts
52     """
53     def __init__(self, samdb):
54         """Initializes the partitions class which can hold
55            our local DCs partitions or all the partitions in
56            the forest
57         """
58         self.dsa_table     = {}    # dsa objects
59         self.part_table    = {}    # partition objects
60         self.site_table    = {}
61         self.my_dsa_dnstr  = None  # My dsa DN
62         self.my_site_dnstr = None
63         self.samdb         = samdb
64         return
65
66     def load_my_site(self):
67         """Loads the Site class for the local DSA
68            Raises an Exception on error
69         """
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)
73
74         site.load_site(samdb)
75         self.site_table[self.my_site_dnstr] = site
76         return
77
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.
83         """
84         dn = ldb.Dn(self.samdb, "")
85         try:
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)
90             return
91
92         dnstr = res[0]["dsServiceName"][0]
93
94         # already loaded
95         if dnstr in self.dsa_table.keys():
96             return
97
98         self.my_dsa_dnstr = dnstr
99         dsa = DirectoryServiceAgent(dnstr)
100
101         dsa.load_dsa(samdb)
102
103         # Assign this dsa to my dsa table
104         # and index by dsa dn
105         self.dsa_table[dnstr] = dsa
106
107         return
108
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.
114         """
115         try:
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)
122             return
123
124         for msg in res:
125             dnstr = str(msg.dn)
126
127             # already loaded
128             if dnstr in self.dsa_table.keys():
129                 continue
130
131             dsa = DirectoryServiceAgent(dnstr)
132
133             dsa.load_dsa(self.samdb)
134
135             # Assign this dsa to my dsa table
136             # and index by dsa dn
137             self.dsa_table[dnstr] = dsa
138
139         return
140
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
147         """
148         try:
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)
155
156         for msg in res:
157             partstr = str(msg.dn)
158
159             # already loaded
160             if partstr in self.part_table.keys():
161                 continue
162
163             part = Partition(partstr)
164
165             part.load_partition(self.samdb)
166             self.part_table[partstr] = part
167
168         return
169
170     def should_be_present_test(self):
171         """Enumerate all loaded partitions and DSAs and test
172            if NC should be present as replica
173         """
174         for partdn, part in self.part_table.items():
175
176            for dsadn, dsa in self.dsa_table.items():
177                needed, ro, partial = part.should_be_present(dsa)
178
179                logger.info("dsadn:%s\nncdn:%s\nneeded=%s:ro=%s:partial=%s\n" % \
180                            (dsa.dsa_dnstr, part.nc_dnstr, needed, ro, partial))
181         return
182
183     def refresh_failed_links_connections(self):
184         # XXX - not implemented yet
185         return
186
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.
192         """
193         # XXX - not implemented yet
194         return False
195
196     def remove_unneeded_failed_links_connections(self):
197         # XXX - not implemented yet
198         return
199
200     def remove_unneeded_ntds_connections(self):
201         # XXX - not implemented yet
202         return
203
204     def translate_connections(self):
205         # XXX - not implemented yet
206         return
207
208     def intersite(self):
209         """The head method for generating the inter-site KCC replica
210            connection graph and attendant nTDSConnection objects
211            in the samdb
212         """
213         # XXX - not implemented yet
214         return
215
216     def update_rodc_connection(self):
217         """Runs when the local DC is an RODC and updates the RODC NTFRS
218            connection object.
219         """
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:
224         #
225         #     cn1.fromServer = cn2.fromServer
226         #     cn1.schedule   = cn2.schedule
227         #
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.
230
231         # XXX - not implemented yet
232         return
233
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
242         """
243         n = 0
244         while True:
245             if node_count <= (2 * (n * n) + (6 * n) + 7):
246                 break
247             n = n + 1
248         n = n + 2
249         if n < 50:
250             return n
251         return 50
252
253     def construct_intrasite_graph(self, site_local, dc_local,
254                                   nc_x, gc_only, detect_stale):
255
256         # We're using the MS notation names here to allow
257         # correlation back to the published algorithm.
258         #
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
264         #            (f_of_x)
265         # r_list   - replica list R
266         # p_of_x   - replica (p) is partial and found on a DC (s)
267         #            for NC (x)
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|
271         #
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)
275
276         logger.debug("construct_intrasite_graph:\n" + \
277                      "nc_x: %s\ndc_local: %s\n" % \
278                      (nc_x, dc_local) + \
279                      "gc_only: %s\nneeded: %s\nro: %s\npartial: %s" % \
280                      (gc_only, needed, ro, partial))
281
282         if needed == False:
283             return
284
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)
289
290         l_of_x.identify_by_basedn(self.samdb)
291
292         l_of_x.rep_partial  = partial
293         l_of_x.rep_ro       = ro
294
295         # Empty replica sequence list
296         r_list = []
297
298         # We'll loop thru all the DSAs looking for
299         # writeable NC replicas that match the naming
300         # context dn for (nc_x)
301         #
302         for dc_s_dn, dc_s in self.dsa_table.items():
303
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():
307                 continue
308
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]
312
313             # Replica (f) of NC (x) must be writable
314             if f_of_x.is_ro() == True:
315                 continue
316
317             # Replica (f) of NC (x) must satisfy the
318             # "is present" criteria for DC (s) that
319             # it was found on
320             if f_of_x.is_present() == False:
321                 continue
322
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:
327                 continue
328
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:
333                 continue
334
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:
339                 continue
340
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
344             #
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
348             # at that level.
349             #
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:
356                     continue
357
358             # If we haven't been told to turn off stale connection
359             # detection and this dsa has a stale connection then
360             # continue
361             if detect_stale and self.is_stale_link_connection(dc_s) == True:
362                continue
363
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)
367
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.
372         if partial == True:
373
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():
378
379                 # If this partition NC (x) doesn't appear as a
380                 # replica (p) of NC (x) on the dsa DC (s) then
381                 # continue
382                 if not nc_x.nc_dnstr in dc_s.rep_table.keys():
383                     continue
384
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]
388
389                 # Replica (p) of NC (x) must be partial
390                 if p_of_x.is_partial() == False:
391                     continue
392
393                 # Replica (p) of NC (x) must satisfy the
394                 # "is present" criteria for DC (s) that
395                 # it was found on
396                 if p_of_x.is_present() == False:
397                     continue
398
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:
403                     continue
404
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:
409                     continue
410
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:
415                     continue
416
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.
423                 #
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:
430                         continue
431
432                 # If we haven't been told to turn off stale connection
433                 # detection and this dsa has a stale connection then
434                 # continue
435                 if detect_stale and self.is_stale_link_connection(dc_s) == True:
436                     continue
437
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)
441
442         # Append to R the NC replica that "should be present"
443         # on the local DC
444         r_list.append(l_of_x)
445
446         r_list.sort(sort_replica_by_dsa_guid)
447
448         r_len = len(r_list)
449
450         max_node_edges = self.intrasite_max_node_edges(r_len)
451
452         # Add a node for each r_list element to the replica graph
453         graph_list = []
454         for rep in r_list:
455             node = GraphNode(rep.rep_dsa_dnstr, max_node_edges)
456             graph_list.append(node)
457
458         # For each r(i) from (0 <= i < |R|-1)
459         i = 0
460         while i < (r_len-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)
466
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)
472             i = i + 1
473
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)
479
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)
485
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.
490         i = 0
491         while i < r_len:
492             dsa = self.dsa_table[graph_list[i].dsa_dnstr]
493             graph_list[i].add_edges_from_connections(dsa)
494             i = i + 1
495
496         i = 0
497         while i < r_len:
498             tnode  = graph_list[i]
499
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.
505             #
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).
511             if r_len >= 3:
512                 # pick a random index
513                 findex = rindex = random.randint(0, r_len-1)
514
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)
522                     else:
523                         # Otherwise continue looking against each node
524                         # after the random selection
525                         rindex = rindex + 1
526                         if rindex >= r_len:
527                             rindex = 0
528
529                         if rindex == findex:
530                             logger.error("Unable to satisfy max edge criteria!")
531                             break
532
533             # Print the graph node in debug mode
534             logger.debug("%s" % tnode)
535
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)
540
541             i = i + 1
542
543         return
544
545     def intrasite(self):
546         """The head method for generating the intra-site KCC replica
547            connection graph and attendant nTDSConnection objects
548            in the samdb
549         """
550         # Retrieve my DSA
551         mydsa = self.dsa_table[self.my_dsa_dnstr]
552
553         logger.debug("intrasite enter:\nmydsa: %s" % mydsa)
554
555         # Test whether local site has topology disabled
556         mysite = self.site_table[self.my_site_dnstr]
557         if mysite.is_intrasite_topology_disabled():
558             return
559
560         detect_stale = mysite.should_detect_stale()
561
562         # Loop thru all the partitions.
563         for partdn, part in self.part_table.items():
564             self.construct_intrasite_graph(mysite, mydsa, part,  \
565                                            False, \
566                                            detect_stale)
567
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():
573             if part.is_config():
574                 self.construct_intrasite_graph(mysite, mydsa, part,  \
575                                                True, \
576                                                detect_stale)
577
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)
584
585         # Loop thru all the partitions.
586         for partdn, part in self.part_table.items():
587             self.construct_intrasite_graph(mysite, mydsa, part,  \
588                                            False, \
589                                            False) # don't detect stale
590
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():
596             if part.is_config():
597                 self.construct_intrasite_graph(mysite, mydsa, part,  \
598                                                True, \
599                                                False)  # don't detect stale
600
601         # Commit any newly created connections to the samdb
602         mydsa.commit_connection_table(self.samdb)
603
604         logger.debug("intrasite exit:\nmydsa: %s" % mydsa)
605         return
606
607     def run(self):
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
611         """
612         # Setup
613         try:
614             self.load_my_dsa()
615             self.load_all_dsa()
616             self.load_all_partitions()
617             self.load_my_site()
618
619         except Exception, estr:
620             logger.error("%s" % estr)
621             return
622
623         # self.should_be_present_test()
624
625         # These are the published steps (in order) for the
626         # MS description of the KCC algorithm
627
628         # Step 1
629         self.refresh_failed_links_connections()
630
631         # Step 2
632         self.intrasite()
633
634         # Step 3
635         self.intersite()
636
637         # Step 4
638         self.remove_unneeded_ntds_connections()
639
640         # Step 5
641         self.translate_connections()
642
643         # Step 6
644         self.remove_unneeded_failed_links_connections()
645
646         # Step 7
647         self.update_rodc_connection()
648
649         return
650
651 ##################################################
652 # Global Functions
653 ##################################################
654 def sort_replica_by_dsa_guid(rep1, rep2):
655     return cmp(rep1.rep_dsa_guid, rep2.rep_dsa_guid)
656
657 ##################################################
658 # kcccompute entry point
659 ##################################################
660
661 parser    = optparse.OptionParser("kcccompute [options]")
662 sambaopts = options.SambaOptions(parser)
663 credopts  = options.CredentialsOptions(parser)
664
665 parser.add_option_group(sambaopts)
666 parser.add_option_group(credopts)
667 parser.add_option_group(options.VersionOptions(parser))
668
669 parser.add_option("--debug", help="debug output", action="store_true")
670 parser.add_option("--seed",  help="random number seed")
671
672 logger = logging.getLogger("kcccompute")
673 logger.addHandler(logging.StreamHandler(sys.stdout))
674
675 lp     = sambaopts.get_loadparm()
676 creds  = credopts.get_credentials(lp, fallback_machine=True)
677
678 opts, args = parser.parse_args()
679
680 if opts.debug:
681     logger.setLevel(logging.DEBUG)
682 else:
683     logger.setLevel(logging.WARNING)
684
685 # initialize seed from optional input parameter
686 if opts.seed:
687     random.seed(int(opts.seed))
688 else:
689     random.seed(0xACE5CA11)
690
691 private_dir = lp.get("private dir")
692 samdb_path  = os.path.join(private_dir, "samdb.ldb")
693
694 try:
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))
699     sys.exit(1)
700
701 # Instantiate Knowledge Consistency Checker and perform run
702 kcc = KCC(samdb)
703 kcc.run()