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
-from samba.kcc.kcc_utils import MAX_DWORD
-from samba.kcc.kcc_utils import ReplInfo, total_schedule
+MAX_DWORD = 2 ** 32 - 1
+
+
+class ReplInfo(object):
+ """Represents information about replication
+
+ NTDSConnections use one representation a replication schedule, and
+ graph vertices use another. This is the Vertex one.
+
+ """
+ def __init__(self):
+ self.cost = 0
+ 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):
+ """Return the total number of 15 minute windows in which the schedule
+ is set to replicate in a week. If the schedule is None it is
+ assumed that the replication will happen in every 15 minute
+ window.
+
+ This is essentially a bit population count.
+ """
+
+ if schedule is None:
+ return 84 * 8 # 84 bytes = 84 * 8 bits
+
+ total = 0
+ for byte in schedule:
+ while byte != 0:
+ total += byte & 1
+ byte >>= 1
+ return total
def convert_schedule_to_repltimes(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):
+def combine_repl_info(info_a, info_b):
+ """Generate an repl_info combining two others
+
+ 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
+ :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
-
- # Truncate to MAX_DWORD
- info_c.cost = info_a.cost + info_b.cost
- if info_c.cost > MAX_DWORD:
- info_c.cost = MAX_DWORD
+ info_c.schedule = [a & b for a, b in zip(info_a.schedule, info_b.schedule)]
+ info_c.duration = total_schedule(info_c.schedule)
- 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,
dot_file_dir=None):
+ """Find edges for the intersite graph
+
+ From MS-ADTS 6.2.2.3.4.4
+
+ :param graph: a kcc.kcc_utils.Graph object
+ :param my_site: the topology generator's site
+ :param label: a label for use in dot files and verification
+ :param verify: if True, try to verify that graph properties are correct
+ :param dot_file_dir: if not None, write Graphviz dot files here
+ """
# Phase 1: Run Dijkstra's to get a list of internal edges, which are
# just the shortest-paths connecting colored vertices
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)
def create_edge(con_type, site_link, guid_to_vertex):
+ """Set up a MultiEdge for the intersite graph
+
+ A MultiEdge can have multiple vertices.
+
+ From MS-ADTS 6.2.2.3.4.4
+
+ :param con_type: a transport type GUID
+ :param site_link: a kcc.kcc_utils.SiteLink object
+ :param guid_to_vertex: a mapping between GUIDs and vertices
+ :return: a MultiEdge
+ """
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
-def create_auto_edge_set(graph, transport):
+def create_auto_edge_set(graph, transport_guid):
+ """Set up an automatic MultiEdgeSet for the intersite graph
+
+ From within MS-ADTS 6.2.2.3.4.4
+
+ :param graph: the intersite graph object
+ :param transport_guid: a transport type GUID
+ :return: a MultiEdgeSet
+ """
e_set = MultiEdgeSet()
# use a NULL guid, not associated with a SiteLinkBridge object
e_set.guid = misc.GUID()
for site_link in graph.edges:
- if site_link.con_type == transport:
+ if site_link.con_type == transport_guid:
e_set.edges.append(site_link)
return e_set
-def create_edge_set(graph, transport, site_link_bridge):
- # TODO not implemented - need to store all site link bridges
- e_set = MultiEdgeSet()
- # e_set.guid = site_link_bridge
- return e_set
+def setup_vertices(graph):
+ """Initialise vertices in the graph for the Dijkstra's run.
+ Part of MS-ADTS 6.2.2.3.4.4
-def setup_vertices(graph):
+ 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
+ """
for v in graph.vertices:
if v.is_white():
v.repl_info.cost = MAX_DWORD
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
def dijkstra(graph, edge_type, include_black):
- queue = []
- setup_dijkstra(graph, edge_type, include_black, queue)
+ """Perform Dijkstra's algorithm on an intersite graph.
+
+ :param graph: an IntersiteGraph object
+ :param edge_type: a transport type GUID
+ :param include_black: boolean, whether to include black vertices
+ :return: None
+ """
+ queue = setup_dijkstra(graph, edge_type, include_black)
while len(queue) > 0:
cost, guid, vertex = heapq.heappop(queue)
for edge in vertex.edges:
try_new_path(graph, queue, vertex, edge, v)
-def setup_dijkstra(graph, edge_type, include_black, queue):
+def setup_dijkstra(graph, edge_type, include_black):
+ """Create a vertex queue for Dijksta's algorithm.
+
+ :param graph: an IntersiteGraph object
+ :param edge_type: a transport type GUID
+ :param include_black: boolean, whether to include black vertices
+ :return: A heap queue of vertices
+ """
+ queue = []
setup_vertices(graph)
for vertex in graph.vertices:
if vertex.is_white():
else:
heapq.heappush(queue, (vertex.repl_info.cost, vertex.guid, vertex))
+ return queue
-def try_new_path(graph, queue, vfrom, edge, vto):
- 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
- if newRI.cost < vto.repl_info.cost and not intersect:
- return
+def try_new_path(graph, queue, vfrom, edge, vto):
+ """Helper function for Dijksta's algorithm.
+
+ :param graph: an IntersiteGraph object
+ :param queue: the empty queue to initialise.
+ :param vfrom: Vertex we are coming from
+ :param edge: an edge to try
+ :param vto: the other Vertex
+ :return: None
+ """
+ new_repl_info = combine_repl_info(vfrom.repl_info, edge.repl_info)
- new_duration = total_schedule(newRI.schedule)
- old_duration = total_schedule(vto.repl_info.schedule)
+ # Cheaper or longer schedule goes in the heap
- # 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))
def check_demote_vertex(vertex, edge_type):
+ """Demote non-white vertices that accept only white edges
+
+ This makes them seem temporarily like white vertices.
+
+ :param vertex: a Vertex()
+ :param edge_type: a transport type GUID
+ :return: None
+ """
if vertex.is_white():
return
def undemote_vertex(vertex):
+ """Un-demote non-white vertices
+
+ Set a vertex's to an undemoted state.
+
+ :param vertex: a Vertex()
+ :return: None
+ """
if vertex.is_white():
return
def process_edge_set(graph, e_set, internal_edges):
+ """Find internal edges to pass to Kruskal's algorithm
+
+ :param graph: an IntersiteGraph object
+ :param e_set: an edge set
+ :param internal_edges: a set that internal edges get added to
+ :return: None
+ """
if e_set is None:
for edge in graph.edges:
for vertex in edge.vertices:
def process_edge(graph, examine, internal_edges):
- # Find the set of all vertices touches the edge to examine
+ """Find the set of all vertices touching an edge to examine
+
+ :param graph: an IntersiteGraph object
+ :param examine: an edge
+ :param internal_edges: a set that internal edges get added to
+ :return: None
+ """
vertices = []
for v in examine.vertices:
# Append a 4-tuple of color, repl cost, guid and vertex
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
- #XXX guid comparison using ndr_pack
- 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
v2.edges.append(ee)
-def setup_graph(part, site_table, transport_table, sitelink_table,
+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
guid_vertices.append(vertex)
connected_vertices = set()
- for transport_guid, transport in transport_table.items():
- # Currently only ever "IP"
- if transport.name != 'IP':
- DEBUG_FN("setup_graph is ignoring transport %s" %
- transport.name)
- continue
- for site_link_dn, site_link in sitelink_table.items():
- new_edge = create_edge(transport_guid, site_link,
- guid_to_vertex)
- 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
- 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))
+ for site_link_dn, site_link in sitelink_table.items():
+ new_edge = create_edge(transport_guid, site_link,
+ guid_to_vertex)
+ connected_vertices.update(new_edge.vertices)
+ g.edges.add(new_edge)
+
+ # XXX we are ignoring the bridges_required option and indeed the
+ # whole concept of SiteLinkBridge objects.
+ if bridges_required:
+ 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".
+
+ From within MS-ADTS 6.2.2.3.4.4:
+
+ SORT internalEdges by (descending RedRed,
+ ascending ReplInfo.Cost,
+ descending available time in ReplInfo.Schedule,
+ 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
- #XXX guid comparison using ndr_pack
if self.v1.guid != other.v1.guid:
return self.v1.ndrpacked_guid < other.v1.ndrpacked_guid
git.samba.org / nivanova / samba-autobuild / .git / blobdiff