1 # Graph functions used by KCC intersite
3 # Copyright (C) Dave Craft 2011
4 # Copyright (C) Andrew Bartlett 2015
6 # Andrew Bartlett's alleged work performed by his underlings Douglas
7 # Bagnall and Garming Sam.
9 # This program is free software; you can redistribute it and/or modify
10 # it under the terms of the GNU General Public License as published by
11 # the Free Software Foundation; either version 3 of the License, or
12 # (at your option) any later version.
14 # This program is distributed in the hope that it will be useful,
15 # but WITHOUT ANY WARRANTY; without even the implied warranty of
16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 # GNU General Public License for more details.
19 # You should have received a copy of the GNU General Public License
20 # along with this program. If not, see <http://www.gnu.org/licenses/>.
25 from samba.kcc.graph_utils import write_dot_file, verify_and_dot, verify_graph
26 from samba.ndr import ndr_pack
27 from samba.dcerpc import misc
29 from samba.kcc.debug import DEBUG, DEBUG_FN
31 from samba.kcc.kcc_utils import MAX_DWORD
32 from samba.kcc.kcc_utils import ReplInfo, total_schedule
35 def convert_schedule_to_repltimes(schedule):
36 """Convert NTDS Connection schedule to replTime schedule.
38 Schedule defined in MS-ADTS 6.1.4.5.2
39 ReplTimes defined in MS-DRSR 5.164.
41 "Schedule" has 168 bytes but only the lower nibble of each is
42 significant. There is one byte per hour. Bit 3 (0x08) represents
43 the first 15 minutes of the hour and bit 0 (0x01) represents the
44 last 15 minutes. The first byte presumably covers 12am - 1am
45 Sunday, though the spec doesn't define the start of a week.
47 "ReplTimes" has 84 bytes which are the 168 lower nibbles of
48 "Schedule" packed together. Thus each byte covers 2 hours. Bits 7
49 (i.e. 0x80) is the first 15 minutes and bit 0 is the last. The
50 first byte covers Sunday 12am - 2am (per spec).
52 Here we pack two elements of the NTDS Connection schedule slots
53 into one element of the replTimes list.
55 If no schedule appears in NTDS Connection then a default of 0x11
56 is set in each replTimes slot as per behaviour noted in a Windows
57 DC. That default would cause replication within the last 15
60 if schedule is None or schedule.dataArray[0] is None:
64 data = schedule.dataArray[0].slots
67 times.append((data[i * 2] & 0xF) << 4 | (data[i * 2 + 1] & 0xF))
72 # Returns true if schedule intersect
73 def combine_repl_info(info_a, info_b, info_c):
74 """Set a replInfo to be the intersection of two others
76 If there is any overlap in the replication times specified by the
77 first two parameters, the third replInfo parameter is set up with
78 that overlap, and True is returned. If there is no overlap, the
79 third parameter is unchanged and False is returned.
81 :param info_a: An input replInfo object
82 :param info_b: An input replInfo object
83 :param info_c: The result replInfo, set to the intersection of A and B
84 if the intersection is non-empty.
85 :return: True if info_c allows any replication at all, otherwise False
87 info_c.interval = max(info_a.interval, info_b.interval)
88 info_c.options = info_a.options & info_b.options
90 if info_a.schedule is None:
91 info_a.schedule = [0xFF] * 84
92 if info_b.schedule is None:
93 info_b.schedule = [0xFF] * 84
95 new_info = [a & b for a, b in zip(info_a.schedule, info_b.schedule)]
100 info_c.schedule = new_info
102 # Truncate to MAX_DWORD
103 info_c.cost = info_a.cost + info_b.cost
104 if info_c.cost > MAX_DWORD:
105 info_c.cost = MAX_DWORD
110 def get_spanning_tree_edges(graph, my_site, label=None, verify=False,
112 # Phase 1: Run Dijkstra's to get a list of internal edges, which are
113 # just the shortest-paths connecting colored vertices
115 internal_edges = set()
117 for e_set in graph.edge_set:
119 for v in graph.vertices:
122 # All con_type in an edge set is the same
123 for e in e_set.edges:
124 edgeType = e.con_type
128 if verify or dot_file_dir is not None:
129 graph_edges = [(a.site.site_dnstr, b.site.site_dnstr)
132 *(itertools.combinations(edge.vertices, 2)
133 for edge in e_set.edges))]
134 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
136 if dot_file_dir is not None:
137 write_dot_file('edgeset_%s' % (edgeType,), graph_edges,
138 vertices=graph_nodes, label=label)
141 verify_graph('spanning tree edge set %s' % edgeType,
142 graph_edges, vertices=graph_nodes,
143 properties=('complete', 'connected'),
146 # Run dijkstra's algorithm with just the red vertices as seeds
147 # Seed from the full replicas
148 dijkstra(graph, edgeType, False)
151 process_edge_set(graph, e_set, internal_edges)
153 # Run dijkstra's algorithm with red and black vertices as the seeds
154 # Seed from both full and partial replicas
155 dijkstra(graph, edgeType, True)
158 process_edge_set(graph, e_set, internal_edges)
160 # All vertices have root/component as itself
161 setup_vertices(graph)
162 process_edge_set(graph, None, internal_edges)
164 if verify or dot_file_dir is not None:
165 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
166 for e in internal_edges]
167 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
168 verify_properties = ('multi_edge_forest',)
169 verify_and_dot('prekruskal', graph_edges, graph_nodes, label=label,
170 properties=verify_properties, debug=DEBUG,
171 verify=verify, dot_file_dir=dot_file_dir)
173 # Phase 2: Run Kruskal's on the internal edges
174 output_edges, components = kruskal(graph, internal_edges)
176 # This recalculates the cost for the path connecting the
177 # closest red vertex. Ignoring types is fine because NO
178 # suboptimal edge should exist in the graph
179 dijkstra(graph, "EDGE_TYPE_ALL", False) # TODO rename
180 # Phase 3: Process the output
181 for v in graph.vertices:
185 v.dist_to_red = v.repl_info.cost
187 if verify or dot_file_dir is not None:
188 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
189 for e in internal_edges]
190 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
191 verify_properties = ('multi_edge_forest',)
192 verify_and_dot('postkruskal', graph_edges, graph_nodes,
193 label=label, properties=verify_properties,
194 debug=DEBUG, verify=verify,
195 dot_file_dir=dot_file_dir)
197 # Ensure only one-way connections for partial-replicas,
198 # and make sure they point the right way.
200 for edge in output_edges:
201 # We know these edges only have two endpoints because we made
204 if v.site is my_site or w.site is my_site:
205 if (((v.is_black() or w.is_black()) and
206 v.dist_to_red != MAX_DWORD)):
209 if w.dist_to_red < v.dist_to_red:
210 edge.vertices[:] = w, v
211 edge_list.append(edge)
213 if verify or dot_file_dir is not None:
214 graph_edges = [[x.site.site_dnstr for x in e.vertices]
216 #add the reverse edge if not directed.
217 graph_edges.extend([x.site.site_dnstr
218 for x in reversed(e.vertices)]
219 for e in edge_list if not e.directed)
220 graph_nodes = [x.site.site_dnstr for x in graph.vertices]
221 verify_properties = ()
222 verify_and_dot('post-one-way-partial', graph_edges, graph_nodes,
223 label=label, properties=verify_properties,
224 debug=DEBUG, verify=verify,
226 dot_file_dir=dot_file_dir)
228 # count the components
229 return edge_list, components
232 def create_edge(con_type, site_link, guid_to_vertex):
234 e.site_link = site_link
236 for site_guid in site_link.site_list:
237 if str(site_guid) in guid_to_vertex:
238 e.vertices.extend(guid_to_vertex.get(str(site_guid)))
239 e.repl_info.cost = site_link.cost
240 e.repl_info.options = site_link.options
241 e.repl_info.interval = site_link.interval
242 e.repl_info.schedule = convert_schedule_to_repltimes(site_link.schedule)
243 e.con_type = con_type
248 def create_auto_edge_set(graph, transport):
249 e_set = MultiEdgeSet()
250 # use a NULL guid, not associated with a SiteLinkBridge object
251 e_set.guid = misc.GUID()
252 for site_link in graph.edges:
253 if site_link.con_type == transport:
254 e_set.edges.append(site_link)
259 def create_edge_set(graph, transport, site_link_bridge):
260 # TODO not implemented - need to store all site link bridges
261 e_set = MultiEdgeSet()
262 # e_set.guid = site_link_bridge
266 def setup_vertices(graph):
267 for v in graph.vertices:
269 v.repl_info.cost = MAX_DWORD
271 v.component_id = None
277 v.repl_info.interval = 0
278 v.repl_info.options = 0xFFFFFFFF
279 v.repl_info.schedule = None # TODO highly suspicious
283 def dijkstra(graph, edge_type, include_black):
285 setup_dijkstra(graph, edge_type, include_black, queue)
286 while len(queue) > 0:
287 cost, guid, vertex = heapq.heappop(queue)
288 for edge in vertex.edges:
289 for v in edge.vertices:
291 # add new path from vertex to v
292 try_new_path(graph, queue, vertex, edge, v)
295 def setup_dijkstra(graph, edge_type, include_black, queue):
296 setup_vertices(graph)
297 for vertex in graph.vertices:
298 if vertex.is_white():
301 if (((vertex.is_black() and not include_black)
302 or edge_type not in vertex.accept_black
303 or edge_type not in vertex.accept_red_red)):
304 vertex.repl_info.cost = MAX_DWORD
305 vertex.root = None # NULL GUID
306 vertex.demoted = True # Demoted appears not to be used
308 heapq.heappush(queue, (vertex.repl_info.cost, vertex.guid, vertex))
311 def try_new_path(graph, queue, vfrom, edge, vto):
313 #This function combines the repl_info and checks is that there is
314 # a valid time frame for which replication can actually occur,
315 # despite being adequately connected
316 intersect = combine_repl_info(vfrom.repl_info, edge.repl_info, newRI)
318 # If the new path costs more than the current, then ignore the edge
319 if newRI.cost > vto.repl_info.cost:
322 if newRI.cost < vto.repl_info.cost and not intersect:
325 new_duration = total_schedule(newRI.schedule)
326 old_duration = total_schedule(vto.repl_info.schedule)
328 # Cheaper or longer schedule
329 if newRI.cost < vto.repl_info.cost or new_duration > old_duration:
330 vto.root = vfrom.root
331 vto.component_id = vfrom.component_id
332 vto.repl_info = newRI
333 heapq.heappush(queue, (vto.repl_info.cost, vto.guid, vto))
336 def check_demote_vertex(vertex, edge_type):
337 if vertex.is_white():
340 # Accepts neither red-red nor black edges, demote
341 if ((edge_type not in vertex.accept_black and
342 edge_type not in vertex.accept_red_red)):
343 vertex.repl_info.cost = MAX_DWORD
345 vertex.demoted = True # Demoted appears not to be used
348 def undemote_vertex(vertex):
349 if vertex.is_white():
352 vertex.repl_info.cost = 0
354 vertex.demoted = False
357 def process_edge_set(graph, e_set, internal_edges):
359 for edge in graph.edges:
360 for vertex in edge.vertices:
361 check_demote_vertex(vertex, edge.con_type)
362 process_edge(graph, edge, internal_edges)
363 for vertex in edge.vertices:
364 undemote_vertex(vertex)
366 for edge in e_set.edges:
367 process_edge(graph, edge, internal_edges)
370 def process_edge(graph, examine, internal_edges):
371 # Find the set of all vertices touches the edge to examine
373 for v in examine.vertices:
374 # Append a 4-tuple of color, repl cost, guid and vertex
375 vertices.append((v.color, v.repl_info.cost, v.ndrpacked_guid, v))
376 # Sort by color, lower
377 DEBUG("vertices is %s" % vertices)
380 color, cost, guid, bestv = vertices[0]
381 # Add to internal edges an edge from every colored vertex to bestV
382 for v in examine.vertices:
383 if v.component_id is None or v.root is None:
386 # Only add edge if valid inter-tree edge - needs a root and
387 # different components
388 if ((bestv.component_id is not None and
389 bestv.root is not None and
390 v.component_id is not None and
391 v.root is not None and
392 bestv.component_id != v.component_id)):
393 add_int_edge(graph, internal_edges, examine, bestv, v)
396 # Add internal edge, endpoints are roots of the vertices to pass in
397 # and are always red or black
398 def add_int_edge(graph, internal_edges, examine, v1, v2):
403 if root1.is_red() and root2.is_red():
407 if ((examine.con_type not in root1.accept_red_red
408 or examine.con_type not in root2.accept_red_red)):
410 elif (examine.con_type not in root1.accept_black
411 or examine.con_type not in root2.accept_black):
417 # Create the transitive replInfo for the two trees and this edge
418 if not combine_repl_info(v1.repl_info, v2.repl_info, ri):
420 # ri is now initialized
421 if not combine_repl_info(ri, examine.repl_info, ri2):
424 newIntEdge = InternalEdge(root1, root2, red_red, ri2, examine.con_type,
426 # Order by vertex guid
427 #XXX guid comparison using ndr_pack
428 if newIntEdge.v1.ndrpacked_guid > newIntEdge.v2.ndrpacked_guid:
429 newIntEdge.v1 = root2
430 newIntEdge.v2 = root1
432 internal_edges.add(newIntEdge)
435 def kruskal(graph, edges):
436 for v in graph.vertices:
439 components = set([x for x in graph.vertices if not x.is_white()])
442 # Sorted based on internal comparison function of internal edge
445 #XXX expected_num_tree_edges is never used
446 expected_num_tree_edges = 0 # TODO this value makes little sense
451 while index < len(edges): # TODO and num_components > 1
453 parent1 = find_component(e.v1)
454 parent2 = find_component(e.v2)
455 if parent1 is not parent2:
457 add_out_edge(graph, output_edges, e)
458 parent1.component_id = parent2
459 components.discard(parent1)
463 return output_edges, len(components)
466 def find_component(vertex):
467 if vertex.component_id is vertex:
471 while current.component_id is not current:
472 current = current.component_id
476 while current.component_id is not root:
477 n = current.component_id
478 current.component_id = root
484 def add_out_edge(graph, output_edges, e):
488 # This multi-edge is a 'real' edge with no GUID
491 ee.site_link = e.site_link
492 ee.vertices.append(v1)
493 ee.vertices.append(v2)
494 ee.con_type = e.e_type
495 ee.repl_info = e.repl_info
496 output_edges.append(ee)
502 def setup_graph(part, site_table, transport_table, sitelink_table,
504 """Set up a GRAPH, populated with a VERTEX for each site
505 object, a MULTIEDGE for each siteLink object, and a
506 MUTLIEDGESET for each siteLinkBridge object (or implied
509 ::returns: a new graph
515 for site_guid, site in site_table.items():
516 vertex = Vertex(site, part)
517 vertex.guid = site_guid
518 vertex.ndrpacked_guid = ndr_pack(site.site_guid)
519 g.vertices.add(vertex)
520 guid_vertices = guid_to_vertex.setdefault(site_guid, [])
521 guid_vertices.append(vertex)
523 connected_vertices = set()
524 for transport_guid, transport in transport_table.items():
525 # Currently only ever "IP"
526 if transport.name != 'IP':
527 DEBUG_FN("setup_graph is ignoring transport %s" %
530 for site_link_dn, site_link in sitelink_table.items():
531 new_edge = create_edge(transport_guid, site_link,
533 connected_vertices.update(new_edge.vertices)
534 g.edges.add(new_edge)
536 # If 'Bridge all site links' is enabled and Win2k3 bridges required
538 # NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
539 # No documentation for this however, ntdsapi.h appears to have:
540 # NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED = 0x00001000
542 g.edge_set.add(create_auto_edge_set(g, transport_guid))
544 # TODO get all site link bridges
545 for site_link_bridge in []:
546 g.edge_set.add(create_edge_set(g, transport_guid,
549 g.connected_vertices = connected_vertices
554 class VertexColor(object):
555 (red, black, white, unknown) = range(0, 4)
558 class Vertex(object):
559 """Class encapsulation of a Site Vertex in the
560 intersite topology replication algorithm
562 def __init__(self, site, part):
565 self.color = VertexColor.unknown
567 self.accept_red_red = []
568 self.accept_black = []
569 self.repl_info = ReplInfo()
572 self.component_id = self
577 def color_vertex(self):
578 """Color each vertex to indicate which kind of NC
581 # IF s contains one or more DCs with full replicas of the
583 # SET v.Color to COLOR.RED
584 # ELSEIF s contains one or more partial replicas of the NC
585 # SET v.Color to COLOR.BLACK
587 # SET v.Color to COLOR.WHITE
589 # set to minimum (no replica)
590 self.color = VertexColor.white
592 for dnstr, dsa in self.site.dsa_table.items():
593 rep = dsa.get_current_replica(self.part.nc_dnstr)
597 # We have a full replica which is the largest
599 if not rep.is_partial():
600 self.color = VertexColor.red
603 self.color = VertexColor.black
606 assert(self.color != VertexColor.unknown)
607 return (self.color == VertexColor.red)
610 assert(self.color != VertexColor.unknown)
611 return (self.color == VertexColor.black)
614 assert(self.color != VertexColor.unknown)
615 return (self.color == VertexColor.white)
618 class IntersiteGraph(object):
619 """Graph for representing the intersite"""
621 self.vertices = set()
623 self.edge_set = set()
624 # All vertices that are endpoints of edges
625 self.connected_vertices = None
628 class MultiEdgeSet(object):
629 """Defines a multi edge set"""
631 self.guid = 0 # objectGuid siteLinkBridge
635 class MultiEdge(object):
637 self.site_link = None # object siteLink
639 self.con_type = None # interSiteTransport GUID
640 self.repl_info = ReplInfo()
644 class InternalEdge(object):
645 def __init__(self, v1, v2, redred, repl, eType, site_link):
648 self.red_red = redred
649 self.repl_info = repl
651 self.site_link = site_link
653 def __eq__(self, other):
654 return not self < other and not other < self
656 def __ne__(self, other):
657 return self < other or other < self
659 def __gt__(self, other):
662 def __ge__(self, other):
663 return not self < other
665 def __le__(self, other):
666 return not other < self
668 # TODO compare options and interval
669 def __lt__(self, other):
670 if self.red_red != other.red_red:
673 if self.repl_info.cost != other.repl_info.cost:
674 return self.repl_info.cost < other.repl_info.cost
676 self_time = total_schedule(self.repl_info.schedule)
677 other_time = total_schedule(other.repl_info.schedule)
678 if self_time != other_time:
679 return self_time > other_time
681 #XXX guid comparison using ndr_pack
682 if self.v1.guid != other.v1.guid:
683 return self.v1.ndrpacked_guid < other.v1.ndrpacked_guid
685 if self.v2.guid != other.v2.guid:
686 return self.v2.ndrpacked_guid < other.v2.ndrpacked_guid
688 return self.e_type < other.e_type