1# Graph functions used by KCC intersite 2# 3# Copyright (C) Dave Craft 2011 4# Copyright (C) Andrew Bartlett 2015 5# 6# Andrew Bartlett's alleged work performed by his underlings Douglas 7# Bagnall and Garming Sam. 8# 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. 13# 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. 18# 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/>. 21 22import itertools 23import heapq 24 25from samba.kcc.graph_utils import write_dot_file, verify_and_dot, verify_graph 26from samba.kcc.kcc_utils import KCCError 27from samba.ndr import ndr_pack 28from samba.dcerpc import misc 29 30from samba.kcc.debug import DEBUG, DEBUG_FN, WARN 31 32MAX_DWORD = 2 ** 32 - 1 33 34 35class ReplInfo(object): 36 """Represents information about replication 37 38 NTDSConnections use one representation a replication schedule, and 39 graph vertices use another. This is the Vertex one. 40 41 """ 42 def __init__(self): 43 self.cost = 0 44 self.interval = 0 45 self.options = 0 46 self.schedule = None 47 self.duration = 84 * 8 48 49 def set_repltimes_from_schedule(self, schedule): 50 """Convert the schedule and calculate duration 51 52 :param schdule: the schedule to convert 53 """ 54 self.schedule = convert_schedule_to_repltimes(schedule) 55 self.duration = total_schedule(self.schedule) 56 57 58def total_schedule(schedule): 59 """Return the total number of 15 minute windows in which the schedule 60 is set to replicate in a week. If the schedule is None it is 61 assumed that the replication will happen in every 15 minute 62 window. 63 64 This is essentially a bit population count. 65 """ 66 67 if schedule is None: 68 return 84 * 8 # 84 bytes = 84 * 8 bits 69 70 total = 0 71 for byte in schedule: 72 while byte != 0: 73 total += byte & 1 74 byte >>= 1 75 return total 76 77 78def convert_schedule_to_repltimes(schedule): 79 """Convert NTDS Connection schedule to replTime schedule. 80 81 Schedule defined in MS-ADTS 6.1.4.5.2 82 ReplTimes defined in MS-DRSR 5.164. 83 84 "Schedule" has 168 bytes but only the lower nibble of each is 85 significant. There is one byte per hour. Bit 3 (0x08) represents 86 the first 15 minutes of the hour and bit 0 (0x01) represents the 87 last 15 minutes. The first byte presumably covers 12am - 1am 88 Sunday, though the spec doesn't define the start of a week. 89 90 "ReplTimes" has 84 bytes which are the 168 lower nibbles of 91 "Schedule" packed together. Thus each byte covers 2 hours. Bits 7 92 (i.e. 0x80) is the first 15 minutes and bit 0 is the last. The 93 first byte covers Sunday 12am - 2am (per spec). 94 95 Here we pack two elements of the NTDS Connection schedule slots 96 into one element of the replTimes list. 97 98 If no schedule appears in NTDS Connection then a default of 0x11 99 is set in each replTimes slot as per behaviour noted in a Windows 100 DC. That default would cause replication within the last 15 101 minutes of each hour. 102 """ 103 # note, NTDSConnection schedule == None means "once an hour" 104 # repl_info == None means "always" 105 if schedule is None or schedule.dataArray[0] is None: 106 return [0x11] * 84 107 108 times = [] 109 data = schedule.dataArray[0].slots 110 111 for i in range(84): 112 times.append((data[i * 2] & 0xF) << 4 | (data[i * 2 + 1] & 0xF)) 113 114 return times 115 116 117def combine_repl_info(info_a, info_b): 118 """Generate an repl_info combining two others 119 120 The schedule is set to be the intersection of the two input schedules. 121 The duration is set to be the duration of the new schedule. 122 The cost is the sum of the costs (saturating at a huge value). 123 The options are the intersection of the input options. 124 The interval is the maximum of the two intervals. 125 126 :param info_a: An input replInfo object 127 :param info_b: An input replInfo object 128 :return: a new ReplInfo combining the other 2 129 """ 130 info_c = ReplInfo() 131 info_c.interval = max(info_a.interval, info_b.interval) 132 info_c.options = info_a.options & info_b.options 133 134 # schedule of None defaults to "always" 135 if info_a.schedule is None: 136 info_a.schedule = [0xFF] * 84 137 if info_b.schedule is None: 138 info_b.schedule = [0xFF] * 84 139 140 info_c.schedule = [a & b for a, b in zip(info_a.schedule, info_b.schedule)] 141 info_c.duration = total_schedule(info_c.schedule) 142 143 info_c.cost = min(info_a.cost + info_b.cost, MAX_DWORD) 144 return info_c 145 146 147def get_spanning_tree_edges(graph, my_site, label=None, verify=False, 148 dot_file_dir=None): 149 """Find edges for the intersite graph 150 151 From MS-ADTS 6.2.2.3.4.4 152 153 :param graph: a kcc.kcc_utils.Graph object 154 :param my_site: the topology generator's site 155 :param label: a label for use in dot files and verification 156 :param verify: if True, try to verify that graph properties are correct 157 :param dot_file_dir: if not None, write Graphviz dot files here 158 """ 159 # Phase 1: Run Dijkstra's to get a list of internal edges, which are 160 # just the shortest-paths connecting colored vertices 161 162 internal_edges = set() 163 164 for e_set in graph.edge_set: 165 edgeType = None 166 for v in graph.vertices: 167 v.edges = [] 168 169 # All con_type in an edge set is the same 170 for e in e_set.edges: 171 edgeType = e.con_type 172 for v in e.vertices: 173 v.edges.append(e) 174 175 if verify or dot_file_dir is not None: 176 graph_edges = [(a.site.site_dnstr, b.site.site_dnstr) 177 for a, b in 178 itertools.chain( 179 *(itertools.combinations(edge.vertices, 2) 180 for edge in e_set.edges))] 181 graph_nodes = [v.site.site_dnstr for v in graph.vertices] 182 183 if dot_file_dir is not None: 184 write_dot_file('edgeset_%s' % (edgeType,), graph_edges, 185 vertices=graph_nodes, label=label) 186 187 if verify: 188 errors = verify_graph(graph_edges, vertices=graph_nodes, 189 properties=('complete', 'connected')) 190 if errors: 191 DEBUG('spanning tree edge set %s FAILED' % edgeType) 192 for p, e, doc in errors: 193 DEBUG("%18s: %s" % (p, e)) 194 raise KCCError("spanning tree failed") 195 196 # Run dijkstra's algorithm with just the red vertices as seeds 197 # Seed from the full replicas 198 dijkstra(graph, edgeType, False) 199 200 # Process edge set 201 process_edge_set(graph, e_set, internal_edges) 202 203 # Run dijkstra's algorithm with red and black vertices as the seeds 204 # Seed from both full and partial replicas 205 dijkstra(graph, edgeType, True) 206 207 # Process edge set 208 process_edge_set(graph, e_set, internal_edges) 209 210 # All vertices have root/component as itself 211 setup_vertices(graph) 212 process_edge_set(graph, None, internal_edges) 213 214 if verify or dot_file_dir is not None: 215 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr) 216 for e in internal_edges] 217 graph_nodes = [v.site.site_dnstr for v in graph.vertices] 218 verify_properties = ('multi_edge_forest',) 219 verify_and_dot('prekruskal', graph_edges, graph_nodes, label=label, 220 properties=verify_properties, debug=DEBUG, 221 verify=verify, dot_file_dir=dot_file_dir) 222 223 # Phase 2: Run Kruskal's on the internal edges 224 output_edges, components = kruskal(graph, internal_edges) 225 226 # This recalculates the cost for the path connecting the 227 # closest red vertex. Ignoring types is fine because NO 228 # suboptimal edge should exist in the graph 229 dijkstra(graph, "EDGE_TYPE_ALL", False) # TODO rename 230 # Phase 3: Process the output 231 for v in graph.vertices: 232 if v.is_red(): 233 v.dist_to_red = 0 234 else: 235 v.dist_to_red = v.repl_info.cost 236 237 if verify or dot_file_dir is not None: 238 graph_edges = [(e.v1.site.site_dnstr, e.v2.site.site_dnstr) 239 for e in internal_edges] 240 graph_nodes = [v.site.site_dnstr for v in graph.vertices] 241 verify_properties = ('multi_edge_forest',) 242 verify_and_dot('postkruskal', graph_edges, graph_nodes, 243 label=label, properties=verify_properties, 244 debug=DEBUG, verify=verify, 245 dot_file_dir=dot_file_dir) 246 247 # Ensure only one-way connections for partial-replicas, 248 # and make sure they point the right way. 249 edge_list = [] 250 for edge in output_edges: 251 # We know these edges only have two endpoints because we made 252 # them. 253 v, w = edge.vertices 254 if v.site is my_site or w.site is my_site: 255 if (((v.is_black() or w.is_black()) and 256 v.dist_to_red != MAX_DWORD)): 257 edge.directed = True 258 259 if w.dist_to_red < v.dist_to_red: 260 edge.vertices[:] = w, v 261 edge_list.append(edge) 262 263 if verify or dot_file_dir is not None: 264 graph_edges = [[x.site.site_dnstr for x in e.vertices] 265 for e in edge_list] 266 # add the reverse edge if not directed. 267 graph_edges.extend([x.site.site_dnstr 268 for x in reversed(e.vertices)] 269 for e in edge_list if not e.directed) 270 graph_nodes = [x.site.site_dnstr for x in graph.vertices] 271 verify_properties = () 272 verify_and_dot('post-one-way-partial', graph_edges, graph_nodes, 273 label=label, properties=verify_properties, 274 debug=DEBUG, verify=verify, 275 directed=True, 276 dot_file_dir=dot_file_dir) 277 278 # count the components 279 return edge_list, components 280 281 282def create_edge(con_type, site_link, guid_to_vertex): 283 """Set up a MultiEdge for the intersite graph 284 285 A MultiEdge can have multiple vertices. 286 287 From MS-ADTS 6.2.2.3.4.4 288 289 :param con_type: a transport type GUID 290 :param site_link: a kcc.kcc_utils.SiteLink object 291 :param guid_to_vertex: a mapping between GUIDs and vertices 292 :return: a MultiEdge 293 """ 294 e = MultiEdge() 295 e.site_link = site_link 296 e.vertices = [] 297 for site_guid, site_dn in site_link.site_list: 298 if str(site_guid) in guid_to_vertex: 299 e.vertices.extend(guid_to_vertex.get(str(site_guid))) 300 e.repl_info.cost = site_link.cost 301 e.repl_info.options = site_link.options 302 e.repl_info.interval = site_link.interval 303 e.repl_info.set_repltimes_from_schedule(site_link.schedule) 304 e.con_type = con_type 305 e.directed = False 306 return e 307 308 309def create_auto_edge_set(graph, transport_guid): 310 """Set up an automatic MultiEdgeSet for the intersite graph 311 312 From within MS-ADTS 6.2.2.3.4.4 313 314 :param graph: the intersite graph object 315 :param transport_guid: a transport type GUID 316 :return: a MultiEdgeSet 317 """ 318 e_set = MultiEdgeSet() 319 # use a NULL guid, not associated with a SiteLinkBridge object 320 e_set.guid = misc.GUID() 321 for site_link in graph.edges: 322 if site_link.con_type == transport_guid: 323 e_set.edges.append(site_link) 324 325 return e_set 326 327 328def setup_vertices(graph): 329 """Initialise vertices in the graph for the Dijkstra's run. 330 331 Part of MS-ADTS 6.2.2.3.4.4 332 333 The schedule and options are set to all-on, so that intersections 334 with real data defer to that data. 335 336 Refer to the convert_schedule_to_repltimes() docstring for an 337 explanation of the repltimes schedule values. 338 339 :param graph: an IntersiteGraph object 340 :return: None 341 """ 342 for v in graph.vertices: 343 if v.is_white(): 344 v.repl_info.cost = MAX_DWORD 345 v.root = None 346 v.component_id = None 347 else: 348 v.repl_info.cost = 0 349 v.root = v 350 v.component_id = v 351 352 v.repl_info.interval = 0 353 v.repl_info.options = 0xFFFFFFFF 354 # repl_info.schedule == None means "always". 355 v.repl_info.schedule = None 356 v.repl_info.duration = 84 * 8 357 v.demoted = False 358 359 360def dijkstra(graph, edge_type, include_black): 361 """Perform Dijkstra's algorithm on an intersite graph. 362 363 :param graph: an IntersiteGraph object 364 :param edge_type: a transport type GUID 365 :param include_black: boolean, whether to include black vertices 366 :return: None 367 """ 368 queue = setup_dijkstra(graph, edge_type, include_black) 369 while len(queue) > 0: 370 cost, guid, vertex = heapq.heappop(queue) 371 for edge in vertex.edges: 372 for v in edge.vertices: 373 if v is not vertex: 374 # add new path from vertex to v 375 try_new_path(graph, queue, vertex, edge, v) 376 377 378def setup_dijkstra(graph, edge_type, include_black): 379 """Create a vertex queue for Dijksta's algorithm. 380 381 :param graph: an IntersiteGraph object 382 :param edge_type: a transport type GUID 383 :param include_black: boolean, whether to include black vertices 384 :return: A heap queue of vertices 385 """ 386 queue = [] 387 setup_vertices(graph) 388 for vertex in graph.vertices: 389 if vertex.is_white(): 390 continue 391 392 if (((vertex.is_black() and not include_black) 393 or edge_type not in vertex.accept_black 394 or edge_type not in vertex.accept_red_red)): 395 vertex.repl_info.cost = MAX_DWORD 396 vertex.root = None # NULL GUID 397 vertex.demoted = True # Demoted appears not to be used 398 else: 399 heapq.heappush(queue, (vertex.repl_info.cost, vertex.guid, vertex)) 400 401 return queue 402 403 404def try_new_path(graph, queue, vfrom, edge, vto): 405 """Helper function for Dijksta's algorithm. 406 407 :param graph: an IntersiteGraph object 408 :param queue: the empty queue to initialise. 409 :param vfrom: Vertex we are coming from 410 :param edge: an edge to try 411 :param vto: the other Vertex 412 :return: None 413 """ 414 new_repl_info = combine_repl_info(vfrom.repl_info, edge.repl_info) 415 416 # Cheaper or longer schedule goes in the heap 417 418 if (new_repl_info.cost < vto.repl_info.cost or 419 new_repl_info.duration > vto.repl_info.duration): 420 vto.root = vfrom.root 421 vto.component_id = vfrom.component_id 422 vto.repl_info = new_repl_info 423 heapq.heappush(queue, (vto.repl_info.cost, vto.guid, vto)) 424 425 426def check_demote_vertex(vertex, edge_type): 427 """Demote non-white vertices that accept only white edges 428 429 This makes them seem temporarily like white vertices. 430 431 :param vertex: a Vertex() 432 :param edge_type: a transport type GUID 433 :return: None 434 """ 435 if vertex.is_white(): 436 return 437 438 # Accepts neither red-red nor black edges, demote 439 if ((edge_type not in vertex.accept_black and 440 edge_type not in vertex.accept_red_red)): 441 vertex.repl_info.cost = MAX_DWORD 442 vertex.root = None 443 vertex.demoted = True # Demoted appears not to be used 444 445 446def undemote_vertex(vertex): 447 """Un-demote non-white vertices 448 449 Set a vertex's to an undemoted state. 450 451 :param vertex: a Vertex() 452 :return: None 453 """ 454 if vertex.is_white(): 455 return 456 457 vertex.repl_info.cost = 0 458 vertex.root = vertex 459 vertex.demoted = False 460 461 462def process_edge_set(graph, e_set, internal_edges): 463 """Find internal edges to pass to Kruskal's algorithm 464 465 :param graph: an IntersiteGraph object 466 :param e_set: an edge set 467 :param internal_edges: a set that internal edges get added to 468 :return: None 469 """ 470 if e_set is None: 471 for edge in graph.edges: 472 for vertex in edge.vertices: 473 check_demote_vertex(vertex, edge.con_type) 474 process_edge(graph, edge, internal_edges) 475 for vertex in edge.vertices: 476 undemote_vertex(vertex) 477 else: 478 for edge in e_set.edges: 479 process_edge(graph, edge, internal_edges) 480 481 482def process_edge(graph, examine, internal_edges): 483 """Find the set of all vertices touching an edge to examine 484 485 :param graph: an IntersiteGraph object 486 :param examine: an edge 487 :param internal_edges: a set that internal edges get added to 488 :return: None 489 """ 490 vertices = [] 491 for v in examine.vertices: 492 # Append a 4-tuple of color, repl cost, guid and vertex 493 vertices.append((v.color, v.repl_info.cost, v.ndrpacked_guid, v)) 494 # Sort by color, lower 495 DEBUG("vertices is %s" % vertices) 496 vertices.sort() 497 498 color, cost, guid, bestv = vertices[0] 499 # Add to internal edges an edge from every colored vertex to bestV 500 for v in examine.vertices: 501 if v.component_id is None or v.root is None: 502 continue 503 504 # Only add edge if valid inter-tree edge - needs a root and 505 # different components 506 if ((bestv.component_id is not None and 507 bestv.root is not None and 508 v.component_id is not None and 509 v.root is not None and 510 bestv.component_id != v.component_id)): 511 add_int_edge(graph, internal_edges, examine, bestv, v) 512 513 514def add_int_edge(graph, internal_edges, examine, v1, v2): 515 """Add edges between compatible red and black vertices 516 517 Internal edges form the core of the tree -- white and RODC 518 vertices attach to it as leaf nodes. An edge needs to have black 519 or red endpoints with compatible replication schedules to be 520 accepted as an internal edge. 521 522 Here we examine an edge and add it to the set of internal edges if 523 it looks good. 524 525 :param graph: the graph object. 526 :param internal_edges: a set of internal edges 527 :param examine: an edge to examine for suitability. 528 :param v1: a Vertex 529 :param v2: the other Vertex 530 """ 531 root1 = v1.root 532 root2 = v2.root 533 534 red_red = root1.is_red() and root2.is_red() 535 536 if red_red: 537 if (examine.con_type not in root1.accept_red_red 538 or examine.con_type not in root2.accept_red_red): 539 return 540 elif (examine.con_type not in root1.accept_black 541 or examine.con_type not in root2.accept_black): 542 return 543 544 # Create the transitive replInfo for the two trees and this edge 545 ri = combine_repl_info(v1.repl_info, v2.repl_info) 546 if ri.duration == 0: 547 return 548 549 ri2 = combine_repl_info(ri, examine.repl_info) 550 if ri2.duration == 0: 551 return 552 553 # Order by vertex guid 554 if root1.ndrpacked_guid > root2.ndrpacked_guid: 555 root1, root2 = root2, root1 556 557 newIntEdge = InternalEdge(root1, root2, red_red, ri2, examine.con_type, 558 examine.site_link) 559 560 internal_edges.add(newIntEdge) 561 562 563def kruskal(graph, edges): 564 """Perform Kruskal's algorithm using the given set of edges 565 566 The input edges are "internal edges" -- between red and black 567 nodes. The output edges are a minimal spanning tree. 568 569 :param graph: the graph object. 570 :param edges: a set of edges 571 :return: a tuple of a list of edges, and the number of components 572 """ 573 for v in graph.vertices: 574 v.edges = [] 575 576 components = set([x for x in graph.vertices if not x.is_white()]) 577 edges = list(edges) 578 579 # Sorted based on internal comparison function of internal edge 580 edges.sort() 581 582 # XXX expected_num_tree_edges is never used 583 expected_num_tree_edges = 0 # TODO this value makes little sense 584 585 count_edges = 0 586 output_edges = [] 587 index = 0 588 while index < len(edges): # TODO and num_components > 1 589 e = edges[index] 590 parent1 = find_component(e.v1) 591 parent2 = find_component(e.v2) 592 if parent1 is not parent2: 593 count_edges += 1 594 add_out_edge(graph, output_edges, e) 595 parent1.component_id = parent2 596 components.discard(parent1) 597 598 index += 1 599 600 return output_edges, len(components) 601 602 603def find_component(vertex): 604 """Kruskal helper to find the component a vertex belongs to. 605 606 :param vertex: a Vertex 607 :return: the Vertex object representing the component 608 """ 609 if vertex.component_id is vertex: 610 return vertex 611 612 current = vertex 613 while current.component_id is not current: 614 current = current.component_id 615 616 root = current 617 current = vertex 618 while current.component_id is not root: 619 n = current.component_id 620 current.component_id = root 621 current = n 622 623 return root 624 625 626def add_out_edge(graph, output_edges, e): 627 """Kruskal helper to add output edges 628 629 :param graph: the InterSiteGraph 630 :param output_edges: the list of spanning tree edges 631 :param e: the edge to be added 632 :return: None 633 """ 634 v1 = e.v1 635 v2 = e.v2 636 637 # This multi-edge is a 'real' undirected 2-vertex edge with no 638 # GUID. XXX It is not really the same thing at all as the 639 # multi-vertex edges relating to site-links. We shouldn't really 640 # be using the same class or storing them in the same list as the 641 # other ones. But we do. Historical reasons. 642 ee = MultiEdge() 643 ee.directed = False 644 ee.site_link = e.site_link 645 ee.vertices.append(v1) 646 ee.vertices.append(v2) 647 ee.con_type = e.e_type 648 ee.repl_info = e.repl_info 649 output_edges.append(ee) 650 651 v1.edges.append(ee) 652 v2.edges.append(ee) 653 654 655def setup_graph(part, site_table, transport_guid, sitelink_table, 656 bridges_required): 657 """Set up an IntersiteGraph based on intersite topology 658 659 The graph will have a Vertex for each site, a MultiEdge for each 660 siteLink object, and a MultiEdgeSet for each siteLinkBridge object 661 (or implied siteLinkBridge). 662 663 :param part: the partition we are dealing with 664 :param site_table: a mapping of guids to sites (KCC.site_table) 665 :param transport_guid: the GUID of the IP transport 666 :param sitelink_table: a mapping of dnstrs to sitelinks 667 :param bridges_required: boolean, asking in vain for something to do 668 with site link bridges 669 :return: a new IntersiteGraph 670 """ 671 guid_to_vertex = {} 672 # Create graph 673 g = IntersiteGraph() 674 # Add vertices 675 for site_guid, site in site_table.items(): 676 vertex = Vertex(site, part) 677 vertex.guid = site_guid 678 vertex.ndrpacked_guid = ndr_pack(site.site_guid) 679 g.vertices.add(vertex) 680 guid_vertices = guid_to_vertex.setdefault(site_guid, []) 681 guid_vertices.append(vertex) 682 683 connected_vertices = set() 684 685 for site_link_dn, site_link in sitelink_table.items(): 686 new_edge = create_edge(transport_guid, site_link, 687 guid_to_vertex) 688 connected_vertices.update(new_edge.vertices) 689 g.edges.add(new_edge) 690 691 # XXX we are ignoring the bridges_required option and indeed the 692 # whole concept of SiteLinkBridge objects. 693 if bridges_required: 694 WARN("Samba KCC ignores the bridges required option") 695 696 g.edge_set.add(create_auto_edge_set(g, transport_guid)) 697 g.connected_vertices = connected_vertices 698 699 return g 700 701 702class VertexColor(object): 703 """Enumeration of vertex colours""" 704 (red, black, white, unknown) = range(0, 4) 705 706 707class Vertex(object): 708 """intersite graph representation of a Site. 709 710 There is a separate vertex for each partition. 711 712 :param site: the site to make a vertex of. 713 :param part: the partition. 714 """ 715 def __init__(self, site, part): 716 self.site = site 717 self.part = part 718 self.color = VertexColor.unknown 719 self.edges = [] 720 self.accept_red_red = [] 721 self.accept_black = [] 722 self.repl_info = ReplInfo() 723 self.root = self 724 self.guid = None 725 self.component_id = self 726 self.demoted = False 727 self.options = 0 728 self.interval = 0 729 730 def color_vertex(self): 731 """Color to indicate which kind of NC replica the vertex contains 732 """ 733 # IF s contains one or more DCs with full replicas of the 734 # NC cr!nCName 735 # SET v.Color to COLOR.RED 736 # ELSEIF s contains one or more partial replicas of the NC 737 # SET v.Color to COLOR.BLACK 738 # ELSE 739 # SET v.Color to COLOR.WHITE 740 741 # set to minimum (no replica) 742 self.color = VertexColor.white 743 744 for dnstr, dsa in self.site.dsa_table.items(): 745 rep = dsa.get_current_replica(self.part.nc_dnstr) 746 if rep is None: 747 continue 748 749 # We have a full replica which is the largest 750 # value so exit 751 if not rep.is_partial(): 752 self.color = VertexColor.red 753 break 754 else: 755 self.color = VertexColor.black 756 757 def is_red(self): 758 assert(self.color != VertexColor.unknown) 759 return (self.color == VertexColor.red) 760 761 def is_black(self): 762 assert(self.color != VertexColor.unknown) 763 return (self.color == VertexColor.black) 764 765 def is_white(self): 766 assert(self.color != VertexColor.unknown) 767 return (self.color == VertexColor.white) 768 769 770class IntersiteGraph(object): 771 """Graph for representing the intersite""" 772 def __init__(self): 773 self.vertices = set() 774 self.edges = set() 775 self.edge_set = set() 776 # All vertices that are endpoints of edges 777 self.connected_vertices = None 778 779 780class MultiEdgeSet(object): 781 """Defines a multi edge set""" 782 def __init__(self): 783 self.guid = 0 # objectGuid siteLinkBridge 784 self.edges = [] 785 786 787class MultiEdge(object): 788 """An "edge" between multiple vertices""" 789 def __init__(self): 790 self.site_link = None # object siteLink 791 self.vertices = [] 792 self.con_type = None # interSiteTransport GUID 793 self.repl_info = ReplInfo() 794 self.directed = True 795 796 797class InternalEdge(object): 798 """An edge that forms part of the minimal spanning tree 799 800 These are used in the Kruskal's algorithm. Their interesting 801 feature isa that they are sortable, with the good edges sorting 802 before the bad ones -- lower is better. 803 """ 804 def __init__(self, v1, v2, redred, repl, eType, site_link): 805 self.v1 = v1 806 self.v2 = v2 807 self.red_red = redred 808 self.repl_info = repl 809 self.e_type = eType 810 self.site_link = site_link 811 812 def __hash__(self): 813 return hash(( 814 self.v1, self.v2, self.red_red, self.repl_info, self.e_type, 815 self.site_link)) 816 817 def __eq__(self, other): 818 return not self < other and not other < self 819 820 def __ne__(self, other): 821 return self < other or other < self 822 823 def __gt__(self, other): 824 return other < self 825 826 def __ge__(self, other): 827 return not self < other 828 829 def __le__(self, other): 830 return not other < self 831 832 def __lt__(self, other): 833 """Here "less than" means "better". 834 835 From within MS-ADTS 6.2.2.3.4.4: 836 837 SORT internalEdges by (descending RedRed, 838 ascending ReplInfo.Cost, 839 descending available time in ReplInfo.Schedule, 840 ascending V1ID, 841 ascending V2ID, 842 ascending Type) 843 """ 844 if self.red_red != other.red_red: 845 return self.red_red 846 847 if self.repl_info.cost != other.repl_info.cost: 848 return self.repl_info.cost < other.repl_info.cost 849 850 if self.repl_info.duration != other.repl_info.duration: 851 return self.repl_info.duration > other.repl_info.duration 852 853 if self.v1.guid != other.v1.guid: 854 return self.v1.ndrpacked_guid < other.v1.ndrpacked_guid 855 856 if self.v2.guid != other.v2.guid: 857 return self.v2.ndrpacked_guid < other.v2.ndrpacked_guid 858 859 return self.e_type < other.e_type 860