--- /dev/null
+#!/usr/bin/env python
+#
+# Compute our KCC topology
+#
+# Copyright (C) Dave Craft 2011
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program. If not, see <http://www.gnu.org/licenses/>.
+
+import os
+import sys
+import random
+
+# ensure we get messages out immediately, so they get in the samba logs,
+# and don't get swallowed by a timeout
+os.environ['PYTHONUNBUFFERED'] = '1'
+
+# forcing GMT avoids a problem in some timezones with kerberos. Both MIT
+# heimdal can get mutual authentication errors due to the 24 second difference
+# between UTC and GMT when using some zone files (eg. the PDT zone from
+# the US)
+os.environ["TZ"] = "GMT"
+
+# Find right directory when running from source tree
+sys.path.insert(0, "bin/python")
+
+import samba, ldb
+import optparse
+import logging
+
+from samba import getopt as options
+from samba.auth import system_session
+from samba.samdb import SamDB
+from samba.kcc_utils import *
+
+class KCC:
+ """The Knowledge Consistency Checker class. A container for
+ objects and methods allowing a run of the KCC. Produces
+ a set of connections in the samdb for which the Distributed
+ Replication Service can then utilize to replicate naming
+ contexts
+ """
+ def __init__(self, samdb):
+ """Initializes the partitions class which can hold
+ our local DCs partitions or all the partitions in
+ the forest
+ """
+ self.dsa_table = {} # dsa objects
+ self.part_table = {} # partition objects
+ self.site_table = {}
+ self.my_dsa_dnstr = None # My dsa DN
+ self.my_site_dnstr = None
+ self.samdb = samdb
+ return
+
+ def load_my_site(self):
+ """Loads the Site class for the local DSA
+ Raises an Exception on error
+ """
+ self.my_site_dnstr = "CN=%s,CN=Sites,%s" % (samdb.server_site_name(),
+ samdb.get_config_basedn())
+ site = Site(self.my_site_dnstr)
+
+ site.load_site(samdb)
+ self.site_table[self.my_site_dnstr] = site
+ return
+
+ def load_my_dsa(self):
+ """Discover my nTDSDSA thru the rootDSE entry and
+ instantiate and load the DSA. The dsa is inserted
+ into the dsa_table by dn string
+ Raises an Exception on error.
+ """
+ dn = ldb.Dn(self.samdb, "")
+ try:
+ res = samdb.search(base=dn, scope=ldb.SCOPE_BASE,
+ attrs=["dsServiceName"])
+ except ldb.LdbError, (enum, estr):
+ raise Exception("Unable to find my nTDSDSA - (%s)" % estr)
+ return
+
+ dnstr = res[0]["dsServiceName"][0]
+
+ # already loaded
+ if dnstr in self.dsa_table.keys():
+ return
+
+ self.my_dsa_dnstr = dnstr
+ dsa = DirectoryServiceAgent(dnstr)
+
+ dsa.load_dsa(samdb)
+
+ # Assign this dsa to my dsa table
+ # and index by dsa dn
+ self.dsa_table[dnstr] = dsa
+
+ return
+
+ def load_all_dsa(self):
+ """Discover all nTDSDSA thru the sites entry and
+ instantiate and load the DSAs. Each dsa is inserted
+ into the dsa_table by dn string.
+ Raises an Exception on error.
+ """
+ try:
+ res = self.samdb.search("CN=Sites,%s" %
+ self.samdb.get_config_basedn(),
+ scope=ldb.SCOPE_SUBTREE,
+ expression="(objectClass=nTDSDSA)")
+ except ldb.LdbError, (enum, estr):
+ raise Exception("Unable to find nTDSDSAs - (%s)" % estr)
+ return
+
+ for msg in res:
+ dnstr = str(msg.dn)
+
+ # already loaded
+ if dnstr in self.dsa_table.keys():
+ continue
+
+ dsa = DirectoryServiceAgent(dnstr)
+
+ dsa.load_dsa(self.samdb)
+
+ # Assign this dsa to my dsa table
+ # and index by dsa dn
+ self.dsa_table[dnstr] = dsa
+
+ return
+
+ def load_all_partitions(self):
+ """Discover all NCs thru the Partitions dn and
+ instantiate and load the NCs. Each NC is inserted
+ into the part_table by partition dn string (not
+ the nCName dn string)
+ Raises an Exception on error
+ """
+ try:
+ res = self.samdb.search("CN=Partitions,%s" %
+ self.samdb.get_config_basedn(),
+ scope=ldb.SCOPE_SUBTREE,
+ expression="(objectClass=crossRef)")
+ except ldb.LdbError, (enum, estr):
+ raise Exception("Unable to find partitions - (%s)" % estr)
+
+ for msg in res:
+ partstr = str(msg.dn)
+
+ # already loaded
+ if partstr in self.part_table.keys():
+ continue
+
+ part = Partition(partstr)
+
+ part.load_partition(self.samdb)
+ self.part_table[partstr] = part
+
+ return
+
+ def should_be_present_test(self):
+ """Enumerate all loaded partitions and DSAs and test
+ if NC should be present as replica
+ """
+ for partdn, part in self.part_table.items():
+
+ for dsadn, dsa in self.dsa_table.items():
+ needed, ro, partial = part.should_be_present(dsa)
+
+ logger.info("dsadn:%s\nncdn:%s\nneeded=%s:ro=%s:partial=%s\n" % \
+ (dsa.dsa_dnstr, part.nc_dnstr, needed, ro, partial))
+ return
+
+ def refresh_failed_links_connections(self):
+ # XXX - not implemented yet
+ return
+
+ def is_stale_link_connection(self, target_dsa):
+ """Returns False if no tuple z exists in the kCCFailedLinks or
+ kCCFailedConnections variables such that z.UUIDDsa is the
+ objectGUID of the target dsa, z.FailureCount > 0, and
+ the current time - z.TimeFirstFailure > 2 hours.
+ """
+ # XXX - not implemented yet
+ return False
+
+ def remove_unneeded_failed_links_connections(self):
+ # XXX - not implemented yet
+ return
+
+ def remove_unneeded_ntds_connections(self):
+ # XXX - not implemented yet
+ return
+
+ def translate_connections(self):
+ # XXX - not implemented yet
+ return
+
+ def intersite(self):
+ """The head method for generating the inter-site KCC replica
+ connection graph and attendant nTDSConnection objects
+ in the samdb
+ """
+ # XXX - not implemented yet
+ return
+
+ def update_rodc_connection(self):
+ """Runs when the local DC is an RODC and updates the RODC NTFRS
+ connection object.
+ """
+ # Given an nTDSConnection object cn1, such that cn1.options contains
+ # NTDSCONN_OPT_RODC_TOPOLOGY, and another nTDSConnection object cn2,
+ # does not contain NTDSCONN_OPT_RODC_TOPOLOGY, modify cn1 to ensure
+ # that the following is true:
+ #
+ # cn1.fromServer = cn2.fromServer
+ # cn1.schedule = cn2.schedule
+ #
+ # If no such cn2 can be found, cn1 is not modified.
+ # If no such cn1 can be found, nothing is modified by this task.
+
+ # XXX - not implemented yet
+ return
+
+ def intrasite_max_node_edges(self, node_count):
+ """Returns the maximum number of edges directed to a node in
+ the intrasite replica graph. The KCC does not create more
+ than 50 edges directed to a single DC. To optimize replication,
+ we compute that each node should have n+2 total edges directed
+ to it such that (n) is the smallest non-negative integer
+ satisfying (node_count <= 2*(n*n) + 6*n + 7)
+ :param node_count: total number of nodes in the replica graph
+ """
+ n = 0
+ while True:
+ if node_count <= (2 * (n * n) + (6 * n) + 7):
+ break
+ n = n + 1
+ n = n + 2
+ if n < 50:
+ return n
+ return 50
+
+ def construct_intrasite_graph(self, site_local, dc_local,
+ nc_x, gc_only, detect_stale):
+
+ # We're using the MS notation names here to allow
+ # correlation back to the published algorithm.
+ #
+ # nc_x - naming context (x) that we are testing if it
+ # "should be present" on the local DC
+ # f_of_x - replica (f) found on a DC (s) for NC (x)
+ # dc_s - DC where f_of_x replica was found
+ # dc_local - local DC that potentially needs a replica
+ # (f_of_x)
+ # r_list - replica list R
+ # p_of_x - replica (p) is partial and found on a DC (s)
+ # for NC (x)
+ # l_of_x - replica (l) is the local replica for NC (x)
+ # that should appear on the local DC
+ # r_len = is length of replica list |R|
+ #
+ # If the DSA doesn't need a replica for this
+ # partition (NC x) then continue
+ needed, ro, partial = nc_x.should_be_present(dc_local)
+
+ logger.debug("construct_intrasite_graph:\n" + \
+ "nc_x: %s\ndc_local: %s\n" % \
+ (nc_x, dc_local) + \
+ "gc_only: %s\nneeded: %s\nro: %s\npartial: %s" % \
+ (gc_only, needed, ro, partial))
+
+ if needed == False:
+ return
+
+ # Create a NCReplica that matches what the local replica
+ # should say. We'll use this below in our r_list
+ l_of_x = NCReplica(dc_local.dsa_dnstr, dc_local.dsa_guid, \
+ nc_x.nc_dnstr, nc_x.nc_guid, nc_x.nc_sid)
+
+ l_of_x.identify_by_basedn(self.samdb)
+
+ l_of_x.rep_partial = partial
+ l_of_x.rep_ro = ro
+
+ # Empty replica sequence list
+ r_list = []
+
+ # We'll loop thru all the DSAs looking for
+ # writeable NC replicas that match the naming
+ # context dn for (nc_x)
+ #
+ for dc_s_dn, dc_s in self.dsa_table.items():
+
+ # If this partition (nc_x) doesn't appear as a
+ # replica (f_of_x) on (dc_s) then continue
+ if not nc_x.nc_dnstr in dc_s.rep_table.keys():
+ continue
+
+ # Pull out the NCReplica (f) of (x) with the dn
+ # that matches NC (x) we are examining.
+ f_of_x = dc_s.rep_table[nc_x.nc_dnstr]
+
+ # Replica (f) of NC (x) must be writable
+ if f_of_x.is_ro() == True:
+ continue
+
+ # Replica (f) of NC (x) must satisfy the
+ # "is present" criteria for DC (s) that
+ # it was found on
+ if f_of_x.is_present() == False:
+ continue
+
+ # DC (s) must be a writable DSA other than
+ # my local DC. In other words we'd only replicate
+ # from other writable DC
+ if dc_s.is_ro() or dc_s is dc_local:
+ continue
+
+ # Certain replica graphs are produced only
+ # for global catalogs, so test against
+ # method input parameter
+ if gc_only and dc_s.is_gc() == False:
+ continue
+
+ # DC (s) must be in the same site as the local DC
+ # This is the intra-site algorithm. We are not
+ # replicating across multiple sites
+ if site_local.is_same_site(dc_s) == False:
+ continue
+
+ # If NC (x) is intended to be read-only full replica
+ # for a domain NC on the target DC then the source
+ # DC should have functional level at minimum WIN2008
+ #
+ # Effectively we're saying that in order to replicate
+ # to a targeted RODC (which was introduced in Windows 2008)
+ # then we have to replicate from a DC that is also minimally
+ # at that level.
+ #
+ # You can also see this requirement in the MS special
+ # considerations for RODC which state that to deploy
+ # an RODC, at least one writable domain controller in
+ # the domain must be running Windows Server 2008
+ if ro and partial == False and nc_x.nc_type == NCType.domain:
+ if dc_s.is_minimum_behavior(DS_BEHAVIOR_WIN2008) == False:
+ continue
+
+ # If we haven't been told to turn off stale connection
+ # detection and this dsa has a stale connection then
+ # continue
+ if detect_stale and self.is_stale_link_connection(dc_s) == True:
+ continue
+
+ # Replica meets criteria. Add it to table indexed
+ # by the GUID of the DC that it appears on
+ r_list.append(f_of_x)
+
+ # If a partial (not full) replica of NC (x) "should be present"
+ # on the local DC, append to R each partial replica (p of x)
+ # such that p "is present" on a DC satisfying the same
+ # criteria defined above for full replica DCs.
+ if partial == True:
+
+ # Now we loop thru all the DSAs looking for
+ # partial NC replicas that match the naming
+ # context dn for (NC x)
+ for dc_s_dn, dc_s in self.dsa_table.items():
+
+ # If this partition NC (x) doesn't appear as a
+ # replica (p) of NC (x) on the dsa DC (s) then
+ # continue
+ if not nc_x.nc_dnstr in dc_s.rep_table.keys():
+ continue
+
+ # Pull out the NCReplica with the dn that
+ # matches NC (x) we are examining.
+ p_of_x = dsa.rep_table[nc_x.nc_dnstr]
+
+ # Replica (p) of NC (x) must be partial
+ if p_of_x.is_partial() == False:
+ continue
+
+ # Replica (p) of NC (x) must satisfy the
+ # "is present" criteria for DC (s) that
+ # it was found on
+ if p_of_x.is_present() == False:
+ continue
+
+ # DC (s) must be a writable DSA other than
+ # my DSA. In other words we'd only replicate
+ # from other writable DSA
+ if dc_s.is_ro() or dc_s is dc_local:
+ continue
+
+ # Certain replica graphs are produced only
+ # for global catalogs, so test against
+ # method input parameter
+ if gc_only and dc_s.is_gc() == False:
+ continue
+
+ # DC (s) must be in the same site as the local DC
+ # This is the intra-site algorithm. We are not
+ # replicating across multiple sites
+ if site_local.is_same_site(dc_s) == False:
+ continue
+
+ # This criteria is moot (a no-op) for this case
+ # because we are scanning for (partial = True). The
+ # MS algorithm statement says partial replica scans
+ # should adhere to the "same" criteria as full replica
+ # scans so the criteria doesn't change here...its just
+ # rendered pointless.
+ #
+ # The case that is occurring would be a partial domain
+ # replica is needed on a local DC global catalog. There
+ # is no minimum windows behavior for those since GCs
+ # have always been present.
+ if ro and partial == False and nc_x.nc_type == NCType.domain:
+ if dc_s.is_minimum_behavior(DS_BEHAVIOR_WIN2008) == False:
+ continue
+
+ # If we haven't been told to turn off stale connection
+ # detection and this dsa has a stale connection then
+ # continue
+ if detect_stale and self.is_stale_link_connection(dc_s) == True:
+ continue
+
+ # Replica meets criteria. Add it to table indexed
+ # by the GUID of the DSA that it appears on
+ r_list.append(p_of_x)
+
+ # Append to R the NC replica that "should be present"
+ # on the local DC
+ r_list.append(l_of_x)
+
+ r_list.sort(sort_replica_by_dsa_guid)
+
+ r_len = len(r_list)
+
+ max_node_edges = self.intrasite_max_node_edges(r_len)
+
+ # Add a node for each r_list element to the replica graph
+ graph_list = []
+ for rep in r_list:
+ node = GraphNode(rep.rep_dsa_dnstr, max_node_edges)
+ graph_list.append(node)
+
+ # For each r(i) from (0 <= i < |R|-1)
+ i = 0
+ while i < (r_len-1):
+ # Add an edge from r(i) to r(i+1) if r(i) is a full
+ # replica or r(i+1) is a partial replica
+ if r_list[i].is_partial() == False or \
+ r_list[i+1].is_partial() == True:
+ graph_list[i+1].add_edge_from(r_list[i].rep_dsa_dnstr)
+
+ # Add an edge from r(i+1) to r(i) if r(i+1) is a full
+ # replica or ri is a partial replica.
+ if r_list[i+1].is_partial() == False or \
+ r_list[i].is_partial() == True:
+ graph_list[i].add_edge_from(r_list[i+1].rep_dsa_dnstr)
+ i = i + 1
+
+ # Add an edge from r|R|-1 to r0 if r|R|-1 is a full replica
+ # or r0 is a partial replica.
+ if r_list[r_len-1].is_partial() == False or \
+ r_list[0].is_partial() == True:
+ graph_list[0].add_edge_from(r_list[r_len-1].rep_dsa_dnstr)
+
+ # Add an edge from r0 to r|R|-1 if r0 is a full replica or
+ # r|R|-1 is a partial replica.
+ if r_list[0].is_partial() == False or \
+ r_list[r_len-1].is_partial() == True:
+ graph_list[r_len-1].add_edge_from(r_list[0].rep_dsa_dnstr)
+
+ # For each existing nTDSConnection object implying an edge
+ # from rj of R to ri such that j != i, an edge from rj to ri
+ # is not already in the graph, and the total edges directed
+ # to ri is less than n+2, the KCC adds that edge to the graph.
+ i = 0
+ while i < r_len:
+ dsa = self.dsa_table[graph_list[i].dsa_dnstr]
+ graph_list[i].add_edges_from_connections(dsa)
+ i = i + 1
+
+ i = 0
+ while i < r_len:
+ tnode = graph_list[i]
+
+ # To optimize replication latency in sites with many NC replicas, the
+ # KCC adds new edges directed to ri to bring the total edges to n+2,
+ # where the NC replica rk of R from which the edge is directed
+ # is chosen at random such that k != i and an edge from rk to ri
+ # is not already in the graph.
+ #
+ # Note that the KCC tech ref does not give a number for the definition
+ # of "sites with many NC replicas". At a bare minimum to satisfy
+ # n+2 edges directed at a node we have to have at least three replicas
+ # in |R| (i.e. if n is zero then at least replicas from two other graph
+ # nodes may direct edges to us).
+ if r_len >= 3:
+ # pick a random index
+ findex = rindex = random.randint(0, r_len-1)
+
+ # while this node doesn't have sufficient edges
+ while tnode.has_sufficient_edges() == False:
+ # If this edge can be successfully added (i.e. not
+ # the same node and edge doesn't already exist) then
+ # select a new random index for the next round
+ if tnode.add_edge_from(graph_list[rindex].dsa_dnstr) == True:
+ findex = rindex = random.randint(0, r_len-1)
+ else:
+ # Otherwise continue looking against each node
+ # after the random selection
+ rindex = rindex + 1
+ if rindex >= r_len:
+ rindex = 0
+
+ if rindex == findex:
+ logger.error("Unable to satisfy max edge criteria!")
+ break
+
+ # Print the graph node in debug mode
+ logger.debug("%s" % tnode)
+
+ # For each edge directed to the local DC, ensure a nTDSConnection
+ # points to us that satisfies the KCC criteria
+ if graph_list[i].dsa_dnstr == dc_local.dsa_dnstr:
+ graph_list[i].add_connections_from_edges(dc_local)
+
+ i = i + 1
+
+ return
+
+ def intrasite(self):
+ """The head method for generating the intra-site KCC replica
+ connection graph and attendant nTDSConnection objects
+ in the samdb
+ """
+ # Retrieve my DSA
+ mydsa = self.dsa_table[self.my_dsa_dnstr]
+
+ logger.debug("intrasite enter:\nmydsa: %s" % mydsa)
+
+ # Test whether local site has topology disabled
+ mysite = self.site_table[self.my_site_dnstr]
+ if mysite.is_intrasite_topology_disabled():
+ return
+
+ detect_stale = mysite.should_detect_stale()
+
+ # Loop thru all the partitions.
+ for partdn, part in self.part_table.items():
+ self.construct_intrasite_graph(mysite, mydsa, part, \
+ False, \
+ detect_stale)
+
+ # If the DC is a GC server, the KCC constructs an additional NC
+ # replica graph (and creates nTDSConnection objects) for the
+ # config NC as above, except that only NC replicas that "are present"
+ # on GC servers are added to R.
+ for partdn, part in self.part_table.items():
+ if part.is_config():
+ self.construct_intrasite_graph(mysite, mydsa, part, \
+ True, \
+ detect_stale)
+
+ # The DC repeats the NC replica graph computation and nTDSConnection
+ # creation for each of the NC replica graphs, this time assuming
+ # that no DC has failed. It does so by re-executing the steps as
+ # if the bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED were
+ # set in the options attribute of the site settings object for
+ # the local DC's site. (ie. we set "detec_stale" flag to False)
+
+ # Loop thru all the partitions.
+ for partdn, part in self.part_table.items():
+ self.construct_intrasite_graph(mysite, mydsa, part, \
+ False, \
+ False) # don't detect stale
+
+ # If the DC is a GC server, the KCC constructs an additional NC
+ # replica graph (and creates nTDSConnection objects) for the
+ # config NC as above, except that only NC replicas that "are present"
+ # on GC servers are added to R.
+ for partdn, part in self.part_table.items():
+ if part.is_config():
+ self.construct_intrasite_graph(mysite, mydsa, part, \
+ True, \
+ False) # don't detect stale
+
+ # Commit any newly created connections to the samdb
+ mydsa.commit_connection_table(self.samdb)
+
+ logger.debug("intrasite exit:\nmydsa: %s" % mydsa)
+ return
+
+ def run(self):
+ """Method to perform a complete run of the KCC and
+ produce an updated topology for subsequent NC replica
+ syncronization between domain controllers
+ """
+ # Setup
+ try:
+ self.load_my_dsa()
+ self.load_all_dsa()
+ self.load_all_partitions()
+ self.load_my_site()
+
+ except Exception, estr:
+ logger.error("%s" % estr)
+ return
+
+ # self.should_be_present_test()
+
+ # These are the published steps (in order) for the
+ # MS description of the KCC algorithm
+
+ # Step 1
+ self.refresh_failed_links_connections()
+
+ # Step 2
+ self.intrasite()
+
+ # Step 3
+ self.intersite()
+
+ # Step 4
+ self.remove_unneeded_ntds_connections()
+
+ # Step 5
+ self.translate_connections()
+
+ # Step 6
+ self.remove_unneeded_failed_links_connections()
+
+ # Step 7
+ self.update_rodc_connection()
+
+ return
+
+##################################################
+# Global Functions
+##################################################
+def sort_replica_by_dsa_guid(rep1, rep2):
+ return cmp(rep1.rep_dsa_guid, rep2.rep_dsa_guid)
+
+##################################################
+# kcccompute entry point
+##################################################
+
+parser = optparse.OptionParser("kcccompute [options]")
+sambaopts = options.SambaOptions(parser)
+credopts = options.CredentialsOptions(parser)
+
+parser.add_option_group(sambaopts)
+parser.add_option_group(credopts)
+parser.add_option_group(options.VersionOptions(parser))
+
+parser.add_option("--debug", help="debug output", action="store_true")
+parser.add_option("--seed", help="random number seed")
+
+logger = logging.getLogger("kcccompute")
+logger.addHandler(logging.StreamHandler(sys.stdout))
+
+lp = sambaopts.get_loadparm()
+creds = credopts.get_credentials(lp, fallback_machine=True)
+
+opts, args = parser.parse_args()
+
+if opts.debug:
+ logger.setLevel(logging.DEBUG)
+else:
+ logger.setLevel(logging.WARNING)
+
+# initialize seed from optional input parameter
+if opts.seed:
+ random.seed(int(opts.seed))
+else:
+ random.seed(0xACE5CA11)
+
+private_dir = lp.get("private dir")
+samdb_path = os.path.join(private_dir, "samdb.ldb")
+
+try:
+ samdb = SamDB(url=lp.samdb_url(), session_info=system_session(),
+ credentials=creds, lp=lp)
+except ldb.LdbError, (num, msg):
+ logger.info("Unable to open sam database %s : %s" % (lp.samdb_url(), msg))
+ sys.exit(1)
+
+# Instantiate Knowledge Consistency Checker and perform run
+kcc = KCC(samdb)
+kcc.run()
git.samba.org / nivanova / samba-autobuild / .git / commitdiff