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, WARN
31 MAX_DWORD = 2 ** 32 - 1
34 class ReplInfo(object):
35 """Represents information about replication
37 NTDSConnections use one representation a replication schedule, and
38 graph vertices use another. This is the Vertex one.
46 self.duration = 84 * 8
48 def set_repltimes_from_schedule(self, schedule):
49 """Convert the schedule and calculate duration
51 :param schdule: the schedule to convert
53 self.schedule = convert_schedule_to_repltimes(schedule)
54 self.duration = total_schedule(self.schedule)
57 def total_schedule(schedule):
58 """Return the total number of 15 minute windows in which the schedule
59 is set to replicate in a week. If the schedule is None it is
60 assumed that the replication will happen in every 15 minute
63 This is essentially a bit population count.
67 return 84 * 8 # 84 bytes = 84 * 8 bits
77 def convert_schedule_to_repltimes(schedule):
78 """Convert NTDS Connection schedule to replTime schedule.
80 Schedule defined in MS-ADTS 6.1.4.5.2
81 ReplTimes defined in MS-DRSR 5.164.
83 "Schedule" has 168 bytes but only the lower nibble of each is
84 significant. There is one byte per hour. Bit 3 (0x08) represents
85 the first 15 minutes of the hour and bit 0 (0x01) represents the
86 last 15 minutes. The first byte presumably covers 12am - 1am
87 Sunday, though the spec doesn't define the start of a week.
89 "ReplTimes" has 84 bytes which are the 168 lower nibbles of
90 "Schedule" packed together. Thus each byte covers 2 hours. Bits 7
91 (i.e. 0x80) is the first 15 minutes and bit 0 is the last. The
92 first byte covers Sunday 12am - 2am (per spec).
94 Here we pack two elements of the NTDS Connection schedule slots
95 into one element of the replTimes list.
97 If no schedule appears in NTDS Connection then a default of 0x11
98 is set in each replTimes slot as per behaviour noted in a Windows
99 DC. That default would cause replication within the last 15
100 minutes of each hour.
102 # note, NTDSConnection schedule == None means "once an hour"
103 # repl_info == None means "always"
104 if schedule is None or schedule.dataArray[0] is None:
108 data = schedule.dataArray[0].slots
111 times.append((data[i * 2] & 0xF) << 4 | (data[i * 2 + 1] & 0xF))
116 def combine_repl_info(info_a, info_b):
117 """Generate an repl_info combining two others
119 The schedule is set to be the intersection of the two input schedules.
120 The duration is set to be the duration of the new schedule.
121 The cost is the sum of the costs (saturating at a huge value).
122 The options are the intersection of the input options.
123 The interval is the maximum of the two intervals.
125 :param info_a: An input replInfo object
126 :param info_b: An input replInfo object
127 :return: a new ReplInfo combining the other 2
130 info_c.interval = max(info_a.interval, info_b.interval)
131 info_c.options = info_a.options & info_b.options
133 #schedule of None defaults to "always"
134 if info_a.schedule is None:
135 info_a.schedule = [0xFF] * 84
136 if info_b.schedule is None:
137 info_b.schedule = [0xFF] * 84
139 info_c.schedule = [a & b for a, b in zip(info_a.schedule, info_b.schedule)]
140 info_c.duration = total_schedule(info_c.schedule)
142 info_c.cost = min(info_a.cost + info_b.cost, MAX_DWORD)
146 def get_spanning_tree_edges(graph, my_site, label=None, verify=False,
148 """Find edges for the intersite graph
150 From MS-ADTS 6.2.2.3.4.4
152 :param graph: a kcc.kcc_utils.Graph object
153 :param my_site: the topology generator's site
154 :param label: a label for use in dot files and verification
155 :param verify: if True, try to verify that graph properties are correct
156 :param dot_file_dir: if not None, write Graphviz dot files here
158 # Phase 1: Run Dijkstra's to get a list of internal edges, which are
159 # just the shortest-paths connecting colored vertices
161 internal_edges = set()
163 for e_set in graph.edge_set:
165 for v in graph.vertices:
168 # All con_type in an edge set is the same
169 for e in e_set.edges:
170 edgeType = e.con_type
174 if verify or dot_file_dir is not None:
175 graph_edges = [(a.site.site_dnstr, b.site.site_dnstr)
178 *(itertools.combinations(edge.vertices, 2)
179 for edge in e_set.edges))]
180 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
182 if dot_file_dir is not None:
183 write_dot_file('edgeset_%s' % (edgeType,), graph_edges,
184 vertices=graph_nodes, label=label)
187 errors = verify_graph(graph_edges, vertices=graph_nodes,
188 properties=('complete', 'connected'))
190 DEBUG('spanning tree edge set %s FAILED' % edgeType)
192 DEBUG("%18s: %s" % (p, e))
193 raise KCCError("spanning tree failed")
195 # Run dijkstra's algorithm with just the red vertices as seeds
196 # Seed from the full replicas
197 dijkstra(graph, edgeType, False)
200 process_edge_set(graph, e_set, internal_edges)
202 # Run dijkstra's algorithm with red and black vertices as the seeds
203 # Seed from both full and partial replicas
204 dijkstra(graph, edgeType, True)
207 process_edge_set(graph, e_set, internal_edges)
209 # All vertices have root/component as itself
210 setup_vertices(graph)
211 process_edge_set(graph, None, internal_edges)
213 if verify or dot_file_dir is not None:
214 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
215 for e in internal_edges]
216 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
217 verify_properties = ('multi_edge_forest',)
218 verify_and_dot('prekruskal', graph_edges, graph_nodes, label=label,
219 properties=verify_properties, debug=DEBUG,
220 verify=verify, dot_file_dir=dot_file_dir)
222 # Phase 2: Run Kruskal's on the internal edges
223 output_edges, components = kruskal(graph, internal_edges)
225 # This recalculates the cost for the path connecting the
226 # closest red vertex. Ignoring types is fine because NO
227 # suboptimal edge should exist in the graph
228 dijkstra(graph, "EDGE_TYPE_ALL", False) # TODO rename
229 # Phase 3: Process the output
230 for v in graph.vertices:
234 v.dist_to_red = v.repl_info.cost
236 if verify or dot_file_dir is not None:
237 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr)
238 for e in internal_edges]
239 graph_nodes = [v.site.site_dnstr for v in graph.vertices]
240 verify_properties = ('multi_edge_forest',)
241 verify_and_dot('postkruskal', graph_edges, graph_nodes,
242 label=label, properties=verify_properties,
243 debug=DEBUG, verify=verify,
244 dot_file_dir=dot_file_dir)
246 # Ensure only one-way connections for partial-replicas,
247 # and make sure they point the right way.
249 for edge in output_edges:
250 # We know these edges only have two endpoints because we made
253 if v.site is my_site or w.site is my_site:
254 if (((v.is_black() or w.is_black()) and
255 v.dist_to_red != MAX_DWORD)):
258 if w.dist_to_red < v.dist_to_red:
259 edge.vertices[:] = w, v
260 edge_list.append(edge)
262 if verify or dot_file_dir is not None:
263 graph_edges = [[x.site.site_dnstr for x in e.vertices]
265 #add the reverse edge if not directed.
266 graph_edges.extend([x.site.site_dnstr
267 for x in reversed(e.vertices)]
268 for e in edge_list if not e.directed)
269 graph_nodes = [x.site.site_dnstr for x in graph.vertices]
270 verify_properties = ()
271 verify_and_dot('post-one-way-partial', graph_edges, graph_nodes,
272 label=label, properties=verify_properties,
273 debug=DEBUG, verify=verify,
275 dot_file_dir=dot_file_dir)
277 # count the components
278 return edge_list, components
281 def create_edge(con_type, site_link, guid_to_vertex):
282 """Set up a MultiEdge for the intersite graph
284 A MultiEdge can have multiple vertices.
286 From MS-ADTS 6.2.2.3.4.4
288 :param con_type: a transport type GUID
289 :param site_link: a kcc.kcc_utils.SiteLink object
290 :param guid_to_vertex: a mapping between GUIDs and vertices
294 e.site_link = site_link
296 for site_guid, site_dn in site_link.site_list:
297 if str(site_guid) in guid_to_vertex:
298 e.vertices.extend(guid_to_vertex.get(str(site_guid)))
299 e.repl_info.cost = site_link.cost
300 e.repl_info.options = site_link.options
301 e.repl_info.interval = site_link.interval
302 e.repl_info.set_repltimes_from_schedule(site_link.schedule)
303 e.con_type = con_type
308 def create_auto_edge_set(graph, transport_guid):
309 """Set up an automatic MultiEdgeSet for the intersite graph
311 From within MS-ADTS 6.2.2.3.4.4
313 :param graph: the intersite graph object
314 :param transport_guid: a transport type GUID
315 :return: a MultiEdgeSet
317 e_set = MultiEdgeSet()
318 # use a NULL guid, not associated with a SiteLinkBridge object
319 e_set.guid = misc.GUID()
320 for site_link in graph.edges:
321 if site_link.con_type == transport_guid:
322 e_set.edges.append(site_link)
327 def setup_vertices(graph):
328 """Initialise vertices in the graph for the Dijkstra's run.
330 Part of MS-ADTS 6.2.2.3.4.4
332 The schedule and options are set to all-on, so that intersections
333 with real data defer to that data.
335 Refer to the convert_schedule_to_repltimes() docstring for an
336 explanation of the repltimes schedule values.
338 :param graph: an IntersiteGraph object
341 for v in graph.vertices:
343 v.repl_info.cost = MAX_DWORD
345 v.component_id = None
351 v.repl_info.interval = 0
352 v.repl_info.options = 0xFFFFFFFF
353 # repl_info.schedule == None means "always".
354 v.repl_info.schedule = None
355 v.repl_info.duration = 84 * 8
359 def dijkstra(graph, edge_type, include_black):
360 """Perform Dijkstra's algorithm on an intersite graph.
362 :param graph: an IntersiteGraph object
363 :param edge_type: a transport type GUID
364 :param include_black: boolean, whether to include black vertices
367 queue = setup_dijkstra(graph, edge_type, include_black)
368 while len(queue) > 0:
369 cost, guid, vertex = heapq.heappop(queue)
370 for edge in vertex.edges:
371 for v in edge.vertices:
373 # add new path from vertex to v
374 try_new_path(graph, queue, vertex, edge, v)
377 def setup_dijkstra(graph, edge_type, include_black):
378 """Create a vertex queue for Dijksta's algorithm.
380 :param graph: an IntersiteGraph object
381 :param edge_type: a transport type GUID
382 :param include_black: boolean, whether to include black vertices
383 :return: A heap queue of vertices
386 setup_vertices(graph)
387 for vertex in graph.vertices:
388 if vertex.is_white():
391 if (((vertex.is_black() and not include_black)
392 or edge_type not in vertex.accept_black
393 or edge_type not in vertex.accept_red_red)):
394 vertex.repl_info.cost = MAX_DWORD
395 vertex.root = None # NULL GUID
396 vertex.demoted = True # Demoted appears not to be used
398 heapq.heappush(queue, (vertex.repl_info.cost, vertex.guid, vertex))
403 def try_new_path(graph, queue, vfrom, edge, vto):
404 """Helper function for Dijksta's algorithm.
406 :param graph: an IntersiteGraph object
407 :param queue: the empty queue to initialise.
408 :param vfrom: Vertex we are coming from
409 :param edge: an edge to try
410 :param vto: the other Vertex
413 new_repl_info = combine_repl_info(vfrom.repl_info, edge.repl_info)
415 # Cheaper or longer schedule goes in the heap
417 if (new_repl_info.cost < vto.repl_info.cost or
418 new_repl_info.duration > vto.repl_info.duration):
419 vto.root = vfrom.root
420 vto.component_id = vfrom.component_id
421 vto.repl_info = new_repl_info
422 heapq.heappush(queue, (vto.repl_info.cost, vto.guid, vto))
425 def check_demote_vertex(vertex, edge_type):
426 """Demote non-white vertices that accept only white edges
428 This makes them seem temporarily like white vertices.
430 :param vertex: a Vertex()
431 :param edge_type: a transport type GUID
434 if vertex.is_white():
437 # Accepts neither red-red nor black edges, demote
438 if ((edge_type not in vertex.accept_black and
439 edge_type not in vertex.accept_red_red)):
440 vertex.repl_info.cost = MAX_DWORD
442 vertex.demoted = True # Demoted appears not to be used
445 def undemote_vertex(vertex):
446 """Un-demote non-white vertices
448 Set a vertex's to an undemoted state.
450 :param vertex: a Vertex()
453 if vertex.is_white():
456 vertex.repl_info.cost = 0
458 vertex.demoted = False
461 def process_edge_set(graph, e_set, internal_edges):
462 """Find internal edges to pass to Kruskal's algorithm
464 :param graph: an IntersiteGraph object
465 :param e_set: an edge set
466 :param internal_edges: a set that internal edges get added to
470 for edge in graph.edges:
471 for vertex in edge.vertices:
472 check_demote_vertex(vertex, edge.con_type)
473 process_edge(graph, edge, internal_edges)
474 for vertex in edge.vertices:
475 undemote_vertex(vertex)
477 for edge in e_set.edges:
478 process_edge(graph, edge, internal_edges)
481 def process_edge(graph, examine, internal_edges):
482 """Find the set of all vertices touching an edge to examine
484 :param graph: an IntersiteGraph object
485 :param examine: an edge
486 :param internal_edges: a set that internal edges get added to
490 for v in examine.vertices:
491 # Append a 4-tuple of color, repl cost, guid and vertex
492 vertices.append((v.color, v.repl_info.cost, v.ndrpacked_guid, v))
493 # Sort by color, lower
494 DEBUG("vertices is %s" % vertices)
497 color, cost, guid, bestv = vertices[0]
498 # Add to internal edges an edge from every colored vertex to bestV
499 for v in examine.vertices:
500 if v.component_id is None or v.root is None:
503 # Only add edge if valid inter-tree edge - needs a root and
504 # different components
505 if ((bestv.component_id is not None and
506 bestv.root is not None and
507 v.component_id is not None and
508 v.root is not None and
509 bestv.component_id != v.component_id)):
510 add_int_edge(graph, internal_edges, examine, bestv, v)
513 def add_int_edge(graph, internal_edges, examine, v1, v2):
514 """Add edges between compatible red and black vertices
516 Internal edges form the core of the tree -- white and RODC
517 vertices attach to it as leaf nodes. An edge needs to have black
518 or red endpoints with compatible replication schedules to be
519 accepted as an internal edge.
521 Here we examine an edge and add it to the set of internal edges if
524 :param graph: the graph object.
525 :param internal_edges: a set of internal edges
526 :param examine: an edge to examine for suitability.
528 :param v2: the other Vertex
533 red_red = root1.is_red() and root2.is_red()
536 if (examine.con_type not in root1.accept_red_red
537 or examine.con_type not in root2.accept_red_red):
539 elif (examine.con_type not in root1.accept_black
540 or examine.con_type not in root2.accept_black):
543 # Create the transitive replInfo for the two trees and this edge
544 ri = combine_repl_info(v1.repl_info, v2.repl_info)
548 ri2 = combine_repl_info(ri, examine.repl_info)
549 if ri2.duration == 0:
552 # Order by vertex guid
553 if root1.ndrpacked_guid > root2.ndrpacked_guid:
554 root1, root2 = root2, root1
556 newIntEdge = InternalEdge(root1, root2, red_red, ri2, examine.con_type,
559 internal_edges.add(newIntEdge)
562 def kruskal(graph, edges):
563 """Perform Kruskal's algorithm using the given set of edges
565 The input edges are "internal edges" -- between red and black
566 nodes. The output edges are a minimal spanning tree.
568 :param graph: the graph object.
569 :param edges: a set of edges
570 :return: a tuple of a list of edges, and the number of components
572 for v in graph.vertices:
575 components = set([x for x in graph.vertices if not x.is_white()])
578 # Sorted based on internal comparison function of internal edge
581 #XXX expected_num_tree_edges is never used
582 expected_num_tree_edges = 0 # TODO this value makes little sense
587 while index < len(edges): # TODO and num_components > 1
589 parent1 = find_component(e.v1)
590 parent2 = find_component(e.v2)
591 if parent1 is not parent2:
593 add_out_edge(graph, output_edges, e)
594 parent1.component_id = parent2
595 components.discard(parent1)
599 return output_edges, len(components)
602 def find_component(vertex):
603 """Kruskal helper to find the component a vertex belongs to.
605 :param vertex: a Vertex
606 :return: the Vertex object representing the component
608 if vertex.component_id is vertex:
612 while current.component_id is not current:
613 current = current.component_id
617 while current.component_id is not root:
618 n = current.component_id
619 current.component_id = root
625 def add_out_edge(graph, output_edges, e):
626 """Kruskal helper to add output edges
628 :param graph: the InterSiteGraph
629 :param output_edges: the list of spanning tree edges
630 :param e: the edge to be added
636 # This multi-edge is a 'real' undirected 2-vertex edge with no
637 # GUID. XXX It is not really the same thing at all as the
638 # multi-vertex edges relating to site-links. We shouldn't really
639 # be using the same class or storing them in the same list as the
640 # other ones. But we do. Historical reasons.
643 ee.site_link = e.site_link
644 ee.vertices.append(v1)
645 ee.vertices.append(v2)
646 ee.con_type = e.e_type
647 ee.repl_info = e.repl_info
648 output_edges.append(ee)
654 def setup_graph(part, site_table, transport_guid, sitelink_table,
656 """Set up an IntersiteGraph based on intersite topology
658 The graph will have a Vertex for each site, a MultiEdge for each
659 siteLink object, and a MultiEdgeSet for each siteLinkBridge object
660 (or implied siteLinkBridge).
662 :param part: the partition we are dealing with
663 :param site_table: a mapping of guids to sites (KCC.site_table)
664 :param transport_guid: the GUID of the IP transport
665 :param sitelink_table: a mapping of dnstrs to sitelinks
666 :param bridges_required: boolean, asking in vain for something to do
667 with site link bridges
668 :return: a new IntersiteGraph
674 for site_guid, site in site_table.items():
675 vertex = Vertex(site, part)
676 vertex.guid = site_guid
677 vertex.ndrpacked_guid = ndr_pack(site.site_guid)
678 g.vertices.add(vertex)
679 guid_vertices = guid_to_vertex.setdefault(site_guid, [])
680 guid_vertices.append(vertex)
682 connected_vertices = set()
684 for site_link_dn, site_link in sitelink_table.items():
685 new_edge = create_edge(transport_guid, site_link,
687 connected_vertices.update(new_edge.vertices)
688 g.edges.add(new_edge)
690 # XXX we are ignoring the bridges_required option and indeed the
691 # whole concept of SiteLinkBridge objects.
693 WARN("Samba KCC ignores the bridges required option")
695 g.edge_set.add(create_auto_edge_set(g, transport_guid))
696 g.connected_vertices = connected_vertices
701 class VertexColor(object):
702 """Enumeration of vertex colours"""
703 (red, black, white, unknown) = range(0, 4)
706 class Vertex(object):
707 """intersite graph representation of a Site.
709 There is a separate vertex for each partition.
711 :param site: the site to make a vertex of.
712 :param part: the partition.
714 def __init__(self, site, part):
717 self.color = VertexColor.unknown
719 self.accept_red_red = []
720 self.accept_black = []
721 self.repl_info = ReplInfo()
724 self.component_id = self
729 def color_vertex(self):
730 """Color to indicate which kind of NC replica the vertex contains
732 # IF s contains one or more DCs with full replicas of the
734 # SET v.Color to COLOR.RED
735 # ELSEIF s contains one or more partial replicas of the NC
736 # SET v.Color to COLOR.BLACK
738 # SET v.Color to COLOR.WHITE
740 # set to minimum (no replica)
741 self.color = VertexColor.white
743 for dnstr, dsa in self.site.dsa_table.items():
744 rep = dsa.get_current_replica(self.part.nc_dnstr)
748 # We have a full replica which is the largest
750 if not rep.is_partial():
751 self.color = VertexColor.red
754 self.color = VertexColor.black
757 assert(self.color != VertexColor.unknown)
758 return (self.color == VertexColor.red)
761 assert(self.color != VertexColor.unknown)
762 return (self.color == VertexColor.black)
765 assert(self.color != VertexColor.unknown)
766 return (self.color == VertexColor.white)
769 class IntersiteGraph(object):
770 """Graph for representing the intersite"""
772 self.vertices = set()
774 self.edge_set = set()
775 # All vertices that are endpoints of edges
776 self.connected_vertices = None
779 class MultiEdgeSet(object):
780 """Defines a multi edge set"""
782 self.guid = 0 # objectGuid siteLinkBridge
786 class MultiEdge(object):
787 """An "edge" between multiple vertices"""
789 self.site_link = None # object siteLink
791 self.con_type = None # interSiteTransport GUID
792 self.repl_info = ReplInfo()
796 class InternalEdge(object):
797 """An edge that forms part of the minimal spanning tree
799 These are used in the Kruskal's algorithm. Their interesting
800 feature isa that they are sortable, with the good edges sorting
801 before the bad ones -- lower is better.
803 def __init__(self, v1, v2, redred, repl, eType, site_link):
806 self.red_red = redred
807 self.repl_info = repl
809 self.site_link = site_link
813 self.v1, self.v2, self.red_red, self.repl_info, self.e_type,
816 def __eq__(self, other):
817 return not self < other and not other < self
819 def __ne__(self, other):
820 return self < other or other < self
822 def __gt__(self, other):
825 def __ge__(self, other):
826 return not self < other
828 def __le__(self, other):
829 return not other < self
831 def __lt__(self, other):
832 """Here "less than" means "better".
834 From within MS-ADTS 6.2.2.3.4.4:
836 SORT internalEdges by (descending RedRed,
837 ascending ReplInfo.Cost,
838 descending available time in ReplInfo.Schedule,
843 if self.red_red != other.red_red:
846 if self.repl_info.cost != other.repl_info.cost:
847 return self.repl_info.cost < other.repl_info.cost
849 if self.repl_info.duration != other.repl_info.duration:
850 return self.repl_info.duration > other.repl_info.duration
852 if self.v1.guid != other.v1.guid:
853 return self.v1.ndrpacked_guid < other.v1.ndrpacked_guid
855 if self.v2.guid != other.v2.guid:
856 return self.v2.ndrpacked_guid < other.v2.ndrpacked_guid
858 return self.e_type < other.e_type