from samba.ndr import ndr_pack
from samba.dcerpc import misc
-from samba.kcc.debug import DEBUG, DEBUG_FN
+from samba.kcc.debug import DEBUG, DEBUG_FN, WARN
MAX_DWORD = 2 ** 32 - 1
self.interval = 0
self.options = 0
self.schedule = None
+ self.duration = 84 * 8
+
+ def set_repltimes_from_schedule(self, schedule):
+ """Convert the schedule and calculate duration
+
+ :param schdule: the schedule to convert
+ """
+ self.schedule = convert_schedule_to_repltimes(schedule)
+ self.duration = total_schedule(self.schedule)
def total_schedule(schedule):
DC. That default would cause replication within the last 15
minutes of each hour.
"""
+ # note, NTDSConnection schedule == None means "once an hour"
+ # repl_info == None means "always"
if schedule is None or schedule.dataArray[0] is None:
return [0x11] * 84
return times
-# Returns true if schedule intersect
-def combine_repl_info(info_a, info_b, info_c):
- """Set a replInfo to be the intersection of two others
+def combine_repl_info(info_a, info_b):
+ """Generate an repl_info combining two others
- If there is any overlap in the replication times specified by the
- first two parameters, the third replInfo parameter is set up with
- that overlap, and True is returned. If there is no overlap, the
- third parameter is unchanged and False is returned.
+ The schedule is set to be the intersection of the two input schedules.
+ The duration is set to be the duration of the new schedule.
+ The cost is the sum of the costs (saturating at a huge value).
+ The options are the intersection of the input options.
+ The interval is the maximum of the two intervals.
:param info_a: An input replInfo object
:param info_b: An input replInfo object
- :param info_c: The result replInfo, set to the intersection of A and B
- if the intersection is non-empty.
- :return: True if info_c allows any replication at all, otherwise False
+ :return: a new ReplInfo combining the other 2
"""
+ info_c = ReplInfo()
info_c.interval = max(info_a.interval, info_b.interval)
info_c.options = info_a.options & info_b.options
+ # schedule of None defaults to "always"
if info_a.schedule is None:
info_a.schedule = [0xFF] * 84
if info_b.schedule is None:
info_b.schedule = [0xFF] * 84
- new_info = [a & b for a, b in zip(info_a.schedule, info_b.schedule)]
-
- if not any(new_info):
- return False
-
- info_c.schedule = new_info
+ info_c.schedule = [a & b for a, b in zip(info_a.schedule, info_b.schedule)]
+ info_c.duration = total_schedule(info_c.schedule)
- # Truncate to MAX_DWORD
- info_c.cost = info_a.cost + info_b.cost
- if info_c.cost > MAX_DWORD:
- info_c.cost = MAX_DWORD
-
- return True
+ info_c.cost = min(info_a.cost + info_b.cost, MAX_DWORD)
+ return info_c
def get_spanning_tree_edges(graph, my_site, label=None, verify=False,
vertices=graph_nodes, label=label)
if verify:
- verify_graph('spanning tree edge set %s' % edgeType,
- graph_edges, vertices=graph_nodes,
- properties=('complete', 'connected'),
- debug=DEBUG)
+ errors = verify_graph(graph_edges, vertices=graph_nodes,
+ properties=('complete', 'connected'))
+ if errors:
+ DEBUG('spanning tree edge set %s FAILED' % edgeType)
+ for p, e, doc in errors:
+ DEBUG("%18s: %s" % (p, e))
+ raise KCCError("spanning tree failed")
# Run dijkstra's algorithm with just the red vertices as seeds
# Seed from the full replicas
if verify or dot_file_dir is not None:
graph_edges = [[x.site.site_dnstr for x in e.vertices]
for e in edge_list]
- #add the reverse edge if not directed.
+ # add the reverse edge if not directed.
graph_edges.extend([x.site.site_dnstr
for x in reversed(e.vertices)]
for e in edge_list if not e.directed)
e = MultiEdge()
e.site_link = site_link
e.vertices = []
- for site_guid in site_link.site_list:
+ for site_guid, site_dn in site_link.site_list:
if str(site_guid) in guid_to_vertex:
e.vertices.extend(guid_to_vertex.get(str(site_guid)))
e.repl_info.cost = site_link.cost
e.repl_info.options = site_link.options
e.repl_info.interval = site_link.interval
- e.repl_info.schedule = convert_schedule_to_repltimes(site_link.schedule)
+ e.repl_info.set_repltimes_from_schedule(site_link.schedule)
e.con_type = con_type
e.directed = False
return e
return e_set
-def create_edge_set(graph, transport, site_link_bridge):
- # TODO not implemented - need to store all site link bridges
- raise NotImplementedError("We don't create fancy edge sets")
-
-
def setup_vertices(graph):
"""Initialise vertices in the graph for the Dijkstra's run.
+ Part of MS-ADTS 6.2.2.3.4.4
+
+ The schedule and options are set to all-on, so that intersections
+ with real data defer to that data.
+
+ Refer to the convert_schedule_to_repltimes() docstring for an
+ explanation of the repltimes schedule values.
+
:param graph: an IntersiteGraph object
:return: None
"""
v.repl_info.interval = 0
v.repl_info.options = 0xFFFFFFFF
- v.repl_info.schedule = None # TODO highly suspicious
+ # repl_info.schedule == None means "always".
+ v.repl_info.schedule = None
+ v.repl_info.duration = 84 * 8
v.demoted = False
:param vto: the other Vertex
:return: None
"""
- newRI = ReplInfo()
- #This function combines the repl_info and checks is that there is
- # a valid time frame for which replication can actually occur,
- # despite being adequately connected
- intersect = combine_repl_info(vfrom.repl_info, edge.repl_info, newRI)
-
- # If the new path costs more than the current, then ignore the edge
- if newRI.cost > vto.repl_info.cost:
- return
+ new_repl_info = combine_repl_info(vfrom.repl_info, edge.repl_info)
- if newRI.cost < vto.repl_info.cost and not intersect:
- return
+ # Cheaper or longer schedule goes in the heap
- new_duration = total_schedule(newRI.schedule)
- old_duration = total_schedule(vto.repl_info.schedule)
-
- # Cheaper or longer schedule
- if newRI.cost < vto.repl_info.cost or new_duration > old_duration:
+ if (new_repl_info.cost < vto.repl_info.cost or
+ new_repl_info.duration > vto.repl_info.duration):
vto.root = vfrom.root
vto.component_id = vfrom.component_id
- vto.repl_info = newRI
+ vto.repl_info = new_repl_info
heapq.heappush(queue, (vto.repl_info.cost, vto.guid, vto))
add_int_edge(graph, internal_edges, examine, bestv, v)
-# Add internal edge, endpoints are roots of the vertices to pass in
-# and are always red or black
def add_int_edge(graph, internal_edges, examine, v1, v2):
+ """Add edges between compatible red and black vertices
+
+ Internal edges form the core of the tree -- white and RODC
+ vertices attach to it as leaf nodes. An edge needs to have black
+ or red endpoints with compatible replication schedules to be
+ accepted as an internal edge.
+
+ Here we examine an edge and add it to the set of internal edges if
+ it looks good.
+
+ :param graph: the graph object.
+ :param internal_edges: a set of internal edges
+ :param examine: an edge to examine for suitability.
+ :param v1: a Vertex
+ :param v2: the other Vertex
+ """
root1 = v1.root
root2 = v2.root
- red_red = False
- if root1.is_red() and root2.is_red():
- red_red = True
+ red_red = root1.is_red() and root2.is_red()
if red_red:
- if ((examine.con_type not in root1.accept_red_red
- or examine.con_type not in root2.accept_red_red)):
+ if (examine.con_type not in root1.accept_red_red
+ or examine.con_type not in root2.accept_red_red):
return
elif (examine.con_type not in root1.accept_black
or examine.con_type not in root2.accept_black):
return
- ri = ReplInfo()
- ri2 = ReplInfo()
-
# Create the transitive replInfo for the two trees and this edge
- if not combine_repl_info(v1.repl_info, v2.repl_info, ri):
+ ri = combine_repl_info(v1.repl_info, v2.repl_info)
+ if ri.duration == 0:
return
- # ri is now initialized
- if not combine_repl_info(ri, examine.repl_info, ri2):
+
+ ri2 = combine_repl_info(ri, examine.repl_info)
+ if ri2.duration == 0:
return
+ # Order by vertex guid
+ if root1.ndrpacked_guid > root2.ndrpacked_guid:
+ root1, root2 = root2, root1
+
newIntEdge = InternalEdge(root1, root2, red_red, ri2, examine.con_type,
examine.site_link)
- # Order by vertex guid
- if newIntEdge.v1.ndrpacked_guid > newIntEdge.v2.ndrpacked_guid:
- newIntEdge.v1 = root2
- newIntEdge.v2 = root1
internal_edges.add(newIntEdge)
def kruskal(graph, edges):
+ """Perform Kruskal's algorithm using the given set of edges
+
+ The input edges are "internal edges" -- between red and black
+ nodes. The output edges are a minimal spanning tree.
+
+ :param graph: the graph object.
+ :param edges: a set of edges
+ :return: a tuple of a list of edges, and the number of components
+ """
for v in graph.vertices:
v.edges = []
# Sorted based on internal comparison function of internal edge
edges.sort()
- #XXX expected_num_tree_edges is never used
+ # XXX expected_num_tree_edges is never used
expected_num_tree_edges = 0 # TODO this value makes little sense
count_edges = 0
def find_component(vertex):
+ """Kruskal helper to find the component a vertex belongs to.
+
+ :param vertex: a Vertex
+ :return: the Vertex object representing the component
+ """
if vertex.component_id is vertex:
return vertex
def add_out_edge(graph, output_edges, e):
+ """Kruskal helper to add output edges
+
+ :param graph: the InterSiteGraph
+ :param output_edges: the list of spanning tree edges
+ :param e: the edge to be added
+ :return: None
+ """
v1 = e.v1
v2 = e.v2
- # This multi-edge is a 'real' edge with no GUID
+ # This multi-edge is a 'real' undirected 2-vertex edge with no
+ # GUID. XXX It is not really the same thing at all as the
+ # multi-vertex edges relating to site-links. We shouldn't really
+ # be using the same class or storing them in the same list as the
+ # other ones. But we do. Historical reasons.
ee = MultiEdge()
ee.directed = False
ee.site_link = e.site_link
def setup_graph(part, site_table, transport_guid, sitelink_table,
bridges_required):
- """Set up a GRAPH, populated with a VERTEX for each site
- object, a MULTIEDGE for each siteLink object, and a
- MUTLIEDGESET for each siteLinkBridge object (or implied
- siteLinkBridge).
-
- ::returns: a new graph
+ """Set up an IntersiteGraph based on intersite topology
+
+ The graph will have a Vertex for each site, a MultiEdge for each
+ siteLink object, and a MultiEdgeSet for each siteLinkBridge object
+ (or implied siteLinkBridge).
+
+ :param part: the partition we are dealing with
+ :param site_table: a mapping of guids to sites (KCC.site_table)
+ :param transport_guid: the GUID of the IP transport
+ :param sitelink_table: a mapping of dnstrs to sitelinks
+ :param bridges_required: boolean, asking in vain for something to do
+ with site link bridges
+ :return: a new IntersiteGraph
"""
guid_to_vertex = {}
# Create graph
connected_vertices.update(new_edge.vertices)
g.edges.add(new_edge)
- # If 'Bridge all site links' is enabled and Win2k3 bridges required
- # is not set
- # NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
- # No documentation for this however, ntdsapi.h appears to have:
- # NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED = 0x00001000
+ # XXX we are ignoring the bridges_required option and indeed the
+ # whole concept of SiteLinkBridge objects.
if bridges_required:
- g.edge_set.add(create_auto_edge_set(g, transport_guid))
- else:
- # TODO get all site link bridges
- for site_link_bridge in []:
- g.edge_set.add(create_edge_set(g, transport_guid,
- site_link_bridge))
+ WARN("Samba KCC ignores the bridges required option")
+ g.edge_set.add(create_auto_edge_set(g, transport_guid))
g.connected_vertices = connected_vertices
return g
class VertexColor(object):
+ """Enumeration of vertex colours"""
(red, black, white, unknown) = range(0, 4)
class Vertex(object):
- """Class encapsulation of a Site Vertex in the
- intersite topology replication algorithm
+ """intersite graph representation of a Site.
+
+ There is a separate vertex for each partition.
+
+ :param site: the site to make a vertex of.
+ :param part: the partition.
"""
def __init__(self, site, part):
self.site = site
self.interval = 0
def color_vertex(self):
- """Color each vertex to indicate which kind of NC
- replica it contains
+ """Color to indicate which kind of NC replica the vertex contains
"""
# IF s contains one or more DCs with full replicas of the
# NC cr!nCName
# SET v.Color to COLOR.RED
# ELSEIF s contains one or more partial replicas of the NC
# SET v.Color to COLOR.BLACK
- #ELSE
+ # ELSE
# SET v.Color to COLOR.WHITE
# set to minimum (no replica)
class MultiEdge(object):
+ """An "edge" between multiple vertices"""
def __init__(self):
self.site_link = None # object siteLink
self.vertices = []
class InternalEdge(object):
+ """An edge that forms part of the minimal spanning tree
+
+ These are used in the Kruskal's algorithm. Their interesting
+ feature isa that they are sortable, with the good edges sorting
+ before the bad ones -- lower is better.
+ """
def __init__(self, v1, v2, redred, repl, eType, site_link):
self.v1 = v1
self.v2 = v2
self.e_type = eType
self.site_link = site_link
+ def __hash__(self):
+ return hash((
+ self.v1, self.v2, self.red_red, self.repl_info, self.e_type,
+ self.site_link))
+
def __eq__(self, other):
return not self < other and not other < self
def __le__(self, other):
return not other < self
- # TODO compare options and interval
def __lt__(self, other):
"""Here "less than" means "better".
ascending V1ID,
ascending V2ID,
ascending Type)
-
"""
if self.red_red != other.red_red:
return self.red_red
if self.repl_info.cost != other.repl_info.cost:
return self.repl_info.cost < other.repl_info.cost
- self_time = total_schedule(self.repl_info.schedule)
- other_time = total_schedule(other.repl_info.schedule)
- if self_time != other_time:
- return self_time > other_time
+ if self.repl_info.duration != other.repl_info.duration:
+ return self.repl_info.duration > other.repl_info.duration
if self.v1.guid != other.v1.guid:
return self.v1.ndrpacked_guid < other.v1.ndrpacked_guid
git.samba.org / nivanova / samba-autobuild / .git / blobdiff