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 verify_graph('spanning tree edge set %s' % edgeType
,
188 graph_edges
, vertices
=graph_nodes
,
189 properties
=('complete', 'connected'),
192 # Run dijkstra's algorithm with just the red vertices as seeds
193 # Seed from the full replicas
194 dijkstra(graph
, edgeType
, False)
197 process_edge_set(graph
, e_set
, internal_edges
)
199 # Run dijkstra's algorithm with red and black vertices as the seeds
200 # Seed from both full and partial replicas
201 dijkstra(graph
, edgeType
, True)
204 process_edge_set(graph
, e_set
, internal_edges
)
206 # All vertices have root/component as itself
207 setup_vertices(graph
)
208 process_edge_set(graph
, None, internal_edges
)
210 if verify
or dot_file_dir
is not None:
211 graph_edges
= [(e
.v1
.site
.site_dnstr
, e
.v2
.site
.site_dnstr
)
212 for e
in internal_edges
]
213 graph_nodes
= [v
.site
.site_dnstr
for v
in graph
.vertices
]
214 verify_properties
= ('multi_edge_forest',)
215 verify_and_dot('prekruskal', graph_edges
, graph_nodes
, label
=label
,
216 properties
=verify_properties
, debug
=DEBUG
,
217 verify
=verify
, dot_file_dir
=dot_file_dir
)
219 # Phase 2: Run Kruskal's on the internal edges
220 output_edges
, components
= kruskal(graph
, internal_edges
)
222 # This recalculates the cost for the path connecting the
223 # closest red vertex. Ignoring types is fine because NO
224 # suboptimal edge should exist in the graph
225 dijkstra(graph
, "EDGE_TYPE_ALL", False) # TODO rename
226 # Phase 3: Process the output
227 for v
in graph
.vertices
:
231 v
.dist_to_red
= v
.repl_info
.cost
233 if verify
or dot_file_dir
is not None:
234 graph_edges
= [(e
.v1
.site
.site_dnstr
, e
.v2
.site
.site_dnstr
)
235 for e
in internal_edges
]
236 graph_nodes
= [v
.site
.site_dnstr
for v
in graph
.vertices
]
237 verify_properties
= ('multi_edge_forest',)
238 verify_and_dot('postkruskal', graph_edges
, graph_nodes
,
239 label
=label
, properties
=verify_properties
,
240 debug
=DEBUG
, verify
=verify
,
241 dot_file_dir
=dot_file_dir
)
243 # Ensure only one-way connections for partial-replicas,
244 # and make sure they point the right way.
246 for edge
in output_edges
:
247 # We know these edges only have two endpoints because we made
250 if v
.site
is my_site
or w
.site
is my_site
:
251 if (((v
.is_black() or w
.is_black()) and
252 v
.dist_to_red
!= MAX_DWORD
)):
255 if w
.dist_to_red
< v
.dist_to_red
:
256 edge
.vertices
[:] = w
, v
257 edge_list
.append(edge
)
259 if verify
or dot_file_dir
is not None:
260 graph_edges
= [[x
.site
.site_dnstr
for x
in e
.vertices
]
262 #add the reverse edge if not directed.
263 graph_edges
.extend([x
.site
.site_dnstr
264 for x
in reversed(e
.vertices
)]
265 for e
in edge_list
if not e
.directed
)
266 graph_nodes
= [x
.site
.site_dnstr
for x
in graph
.vertices
]
267 verify_properties
= ()
268 verify_and_dot('post-one-way-partial', graph_edges
, graph_nodes
,
269 label
=label
, properties
=verify_properties
,
270 debug
=DEBUG
, verify
=verify
,
272 dot_file_dir
=dot_file_dir
)
274 # count the components
275 return edge_list
, components
278 def create_edge(con_type
, site_link
, guid_to_vertex
):
279 """Set up a MultiEdge for the intersite graph
281 A MultiEdge can have multiple vertices.
283 From MS-ADTS 6.2.2.3.4.4
285 :param con_type: a transport type GUID
286 :param site_link: a kcc.kcc_utils.SiteLink object
287 :param guid_to_vertex: a mapping between GUIDs and vertices
291 e
.site_link
= site_link
293 for site_guid
in site_link
.site_list
:
294 if str(site_guid
) in guid_to_vertex
:
295 e
.vertices
.extend(guid_to_vertex
.get(str(site_guid
)))
296 e
.repl_info
.cost
= site_link
.cost
297 e
.repl_info
.options
= site_link
.options
298 e
.repl_info
.interval
= site_link
.interval
299 e
.repl_info
.set_repltimes_from_schedule(site_link
.schedule
)
300 e
.con_type
= con_type
305 def create_auto_edge_set(graph
, transport_guid
):
306 """Set up an automatic MultiEdgeSet for the intersite graph
308 From within MS-ADTS 6.2.2.3.4.4
310 :param graph: the intersite graph object
311 :param transport_guid: a transport type GUID
312 :return: a MultiEdgeSet
314 e_set
= MultiEdgeSet()
315 # use a NULL guid, not associated with a SiteLinkBridge object
316 e_set
.guid
= misc
.GUID()
317 for site_link
in graph
.edges
:
318 if site_link
.con_type
== transport_guid
:
319 e_set
.edges
.append(site_link
)
324 def setup_vertices(graph
):
325 """Initialise vertices in the graph for the Dijkstra's run.
327 Part of MS-ADTS 6.2.2.3.4.4
329 The schedule and options are set to all-on, so that intersections
330 with real data defer to that data.
332 Refer to the convert_schedule_to_repltimes() docstring for an
333 explanation of the repltimes schedule values.
335 :param graph: an IntersiteGraph object
338 for v
in graph
.vertices
:
340 v
.repl_info
.cost
= MAX_DWORD
342 v
.component_id
= None
348 v
.repl_info
.interval
= 0
349 v
.repl_info
.options
= 0xFFFFFFFF
350 # repl_info.schedule == None means "always".
351 v
.repl_info
.schedule
= None
352 v
.repl_info
.duration
= 84 * 8
356 def dijkstra(graph
, edge_type
, include_black
):
357 """Perform Dijkstra's algorithm on an intersite graph.
359 :param graph: an IntersiteGraph object
360 :param edge_type: a transport type GUID
361 :param include_black: boolean, whether to include black vertices
364 queue
= setup_dijkstra(graph
, edge_type
, include_black
)
365 while len(queue
) > 0:
366 cost
, guid
, vertex
= heapq
.heappop(queue
)
367 for edge
in vertex
.edges
:
368 for v
in edge
.vertices
:
370 # add new path from vertex to v
371 try_new_path(graph
, queue
, vertex
, edge
, v
)
374 def setup_dijkstra(graph
, edge_type
, include_black
):
375 """Create a vertex queue for Dijksta's algorithm.
377 :param graph: an IntersiteGraph object
378 :param edge_type: a transport type GUID
379 :param include_black: boolean, whether to include black vertices
380 :return: A heap queue of vertices
383 setup_vertices(graph
)
384 for vertex
in graph
.vertices
:
385 if vertex
.is_white():
388 if (((vertex
.is_black() and not include_black
)
389 or edge_type
not in vertex
.accept_black
390 or edge_type
not in vertex
.accept_red_red
)):
391 vertex
.repl_info
.cost
= MAX_DWORD
392 vertex
.root
= None # NULL GUID
393 vertex
.demoted
= True # Demoted appears not to be used
395 heapq
.heappush(queue
, (vertex
.repl_info
.cost
, vertex
.guid
, vertex
))
400 def try_new_path(graph
, queue
, vfrom
, edge
, vto
):
401 """Helper function for Dijksta's algorithm.
403 :param graph: an IntersiteGraph object
404 :param queue: the empty queue to initialise.
405 :param vfrom: Vertex we are coming from
406 :param edge: an edge to try
407 :param vto: the other Vertex
410 new_repl_info
= combine_repl_info(vfrom
.repl_info
, edge
.repl_info
)
412 # Cheaper or longer schedule goes in the heap
414 if (new_repl_info
.cost
< vto
.repl_info
.cost
or
415 new_repl_info
.duration
> vto
.repl_info
.duration
):
416 vto
.root
= vfrom
.root
417 vto
.component_id
= vfrom
.component_id
418 vto
.repl_info
= new_repl_info
419 heapq
.heappush(queue
, (vto
.repl_info
.cost
, vto
.guid
, vto
))
422 def check_demote_vertex(vertex
, edge_type
):
423 """Demote non-white vertices that accept only white edges
425 This makes them seem temporarily like white vertices.
427 :param vertex: a Vertex()
428 :param edge_type: a transport type GUID
431 if vertex
.is_white():
434 # Accepts neither red-red nor black edges, demote
435 if ((edge_type
not in vertex
.accept_black
and
436 edge_type
not in vertex
.accept_red_red
)):
437 vertex
.repl_info
.cost
= MAX_DWORD
439 vertex
.demoted
= True # Demoted appears not to be used
442 def undemote_vertex(vertex
):
443 """Un-demote non-white vertices
445 Set a vertex's to an undemoted state.
447 :param vertex: a Vertex()
450 if vertex
.is_white():
453 vertex
.repl_info
.cost
= 0
455 vertex
.demoted
= False
458 def process_edge_set(graph
, e_set
, internal_edges
):
459 """Find internal edges to pass to Kruskal's algorithm
461 :param graph: an IntersiteGraph object
462 :param e_set: an edge set
463 :param internal_edges: a set that internal edges get added to
467 for edge
in graph
.edges
:
468 for vertex
in edge
.vertices
:
469 check_demote_vertex(vertex
, edge
.con_type
)
470 process_edge(graph
, edge
, internal_edges
)
471 for vertex
in edge
.vertices
:
472 undemote_vertex(vertex
)
474 for edge
in e_set
.edges
:
475 process_edge(graph
, edge
, internal_edges
)
478 def process_edge(graph
, examine
, internal_edges
):
479 """Find the set of all vertices touching an edge to examine
481 :param graph: an IntersiteGraph object
482 :param examine: an edge
483 :param internal_edges: a set that internal edges get added to
487 for v
in examine
.vertices
:
488 # Append a 4-tuple of color, repl cost, guid and vertex
489 vertices
.append((v
.color
, v
.repl_info
.cost
, v
.ndrpacked_guid
, v
))
490 # Sort by color, lower
491 DEBUG("vertices is %s" % vertices
)
494 color
, cost
, guid
, bestv
= vertices
[0]
495 # Add to internal edges an edge from every colored vertex to bestV
496 for v
in examine
.vertices
:
497 if v
.component_id
is None or v
.root
is None:
500 # Only add edge if valid inter-tree edge - needs a root and
501 # different components
502 if ((bestv
.component_id
is not None and
503 bestv
.root
is not None and
504 v
.component_id
is not None and
505 v
.root
is not None and
506 bestv
.component_id
!= v
.component_id
)):
507 add_int_edge(graph
, internal_edges
, examine
, bestv
, v
)
510 def add_int_edge(graph
, internal_edges
, examine
, v1
, v2
):
511 """Add edges between compatible red and black vertices
513 Internal edges form the core of the tree -- white and RODC
514 vertices attach to it as leaf nodes. An edge needs to have black
515 or red endpoints with compatible replication schedules to be
516 accepted as an internal edge.
518 Here we examine an edge and add it to the set of internal edges if
521 :param graph: the graph object.
522 :param internal_edges: a set of internal edges
523 :param examine: an edge to examine for suitability.
525 :param v2: the other Vertex
530 red_red
= root1
.is_red() and root2
.is_red()
533 if (examine
.con_type
not in root1
.accept_red_red
534 or examine
.con_type
not in root2
.accept_red_red
):
536 elif (examine
.con_type
not in root1
.accept_black
537 or examine
.con_type
not in root2
.accept_black
):
540 # Create the transitive replInfo for the two trees and this edge
541 ri
= combine_repl_info(v1
.repl_info
, v2
.repl_info
)
545 ri2
= combine_repl_info(ri
, examine
.repl_info
)
546 if ri2
.duration
== 0:
549 # Order by vertex guid
550 if root1
.ndrpacked_guid
> root2
.ndrpacked_guid
:
551 root1
, root2
= root2
, root1
553 newIntEdge
= InternalEdge(root1
, root2
, red_red
, ri2
, examine
.con_type
,
556 internal_edges
.add(newIntEdge
)
559 def kruskal(graph
, edges
):
560 """Perform Kruskal's algorithm using the given set of edges
562 The input edges are "internal edges" -- between red and black
563 nodes. The output edges are a minimal spanning tree.
565 :param graph: the graph object.
566 :param edges: a set of edges
567 :return: a tuple of a list of edges, and the number of components
569 for v
in graph
.vertices
:
572 components
= set([x
for x
in graph
.vertices
if not x
.is_white()])
575 # Sorted based on internal comparison function of internal edge
578 #XXX expected_num_tree_edges is never used
579 expected_num_tree_edges
= 0 # TODO this value makes little sense
584 while index
< len(edges
): # TODO and num_components > 1
586 parent1
= find_component(e
.v1
)
587 parent2
= find_component(e
.v2
)
588 if parent1
is not parent2
:
590 add_out_edge(graph
, output_edges
, e
)
591 parent1
.component_id
= parent2
592 components
.discard(parent1
)
596 return output_edges
, len(components
)
599 def find_component(vertex
):
600 """Kruskal helper to find the component a vertex belongs to.
602 :param vertex: a Vertex
603 :return: the Vertex object representing the component
605 if vertex
.component_id
is vertex
:
609 while current
.component_id
is not current
:
610 current
= current
.component_id
614 while current
.component_id
is not root
:
615 n
= current
.component_id
616 current
.component_id
= root
622 def add_out_edge(graph
, output_edges
, e
):
623 """Kruskal helper to add output edges
625 :param graph: the InterSiteGraph
626 :param output_edges: the list of spanning tree edges
627 :param e: the edge to be added
633 # This multi-edge is a 'real' undirected 2-vertex edge with no
634 # GUID. XXX It is not really the same thing at all as the
635 # multi-vertex edges relating to site-links. We shouldn't really
636 # be using the same class or storing them in the same list as the
637 # other ones. But we do. Historical reasons.
640 ee
.site_link
= e
.site_link
641 ee
.vertices
.append(v1
)
642 ee
.vertices
.append(v2
)
643 ee
.con_type
= e
.e_type
644 ee
.repl_info
= e
.repl_info
645 output_edges
.append(ee
)
651 def setup_graph(part
, site_table
, transport_guid
, sitelink_table
,
653 """Set up an IntersiteGraph based on intersite topology
655 The graph will have a Vertex for each site, a MultiEdge for each
656 siteLink object, and a MultiEdgeSet for each siteLinkBridge object
657 (or implied siteLinkBridge).
659 :param part: the partition we are dealing with
660 :param site_table: a mapping of guids to sites (KCC.site_table)
661 :param transport_guid: the GUID of the IP transport
662 :param sitelink_table: a mapping of dnstrs to sitelinks
663 :param bridges_required: boolean, asking in vain for something to do
664 with site link bridges
665 :return: a new IntersiteGraph
671 for site_guid
, site
in site_table
.items():
672 vertex
= Vertex(site
, part
)
673 vertex
.guid
= site_guid
674 vertex
.ndrpacked_guid
= ndr_pack(site
.site_guid
)
675 g
.vertices
.add(vertex
)
676 guid_vertices
= guid_to_vertex
.setdefault(site_guid
, [])
677 guid_vertices
.append(vertex
)
679 connected_vertices
= set()
681 for site_link_dn
, site_link
in sitelink_table
.items():
682 new_edge
= create_edge(transport_guid
, site_link
,
684 connected_vertices
.update(new_edge
.vertices
)
685 g
.edges
.add(new_edge
)
687 # XXX we are ignoring the bridges_required option and indeed the
688 # whole concept of SiteLinkBridge objects.
690 WARN("Samba KCC ignores the bridges required option")
692 g
.edge_set
.add(create_auto_edge_set(g
, transport_guid
))
693 g
.connected_vertices
= connected_vertices
698 class VertexColor(object):
699 """Enumeration of vertex colours"""
700 (red
, black
, white
, unknown
) = range(0, 4)
703 class Vertex(object):
704 """intersite graph representation of a Site.
706 There is a separate vertex for each partition.
708 :param site: the site to make a vertex of.
709 :param part: the partition.
711 def __init__(self
, site
, part
):
714 self
.color
= VertexColor
.unknown
716 self
.accept_red_red
= []
717 self
.accept_black
= []
718 self
.repl_info
= ReplInfo()
721 self
.component_id
= self
726 def color_vertex(self
):
727 """Color to indicate which kind of NC replica the vertex contains
729 # IF s contains one or more DCs with full replicas of the
731 # SET v.Color to COLOR.RED
732 # ELSEIF s contains one or more partial replicas of the NC
733 # SET v.Color to COLOR.BLACK
735 # SET v.Color to COLOR.WHITE
737 # set to minimum (no replica)
738 self
.color
= VertexColor
.white
740 for dnstr
, dsa
in self
.site
.dsa_table
.items():
741 rep
= dsa
.get_current_replica(self
.part
.nc_dnstr
)
745 # We have a full replica which is the largest
747 if not rep
.is_partial():
748 self
.color
= VertexColor
.red
751 self
.color
= VertexColor
.black
754 assert(self
.color
!= VertexColor
.unknown
)
755 return (self
.color
== VertexColor
.red
)
758 assert(self
.color
!= VertexColor
.unknown
)
759 return (self
.color
== VertexColor
.black
)
762 assert(self
.color
!= VertexColor
.unknown
)
763 return (self
.color
== VertexColor
.white
)
766 class IntersiteGraph(object):
767 """Graph for representing the intersite"""
769 self
.vertices
= set()
771 self
.edge_set
= set()
772 # All vertices that are endpoints of edges
773 self
.connected_vertices
= None
776 class MultiEdgeSet(object):
777 """Defines a multi edge set"""
779 self
.guid
= 0 # objectGuid siteLinkBridge
783 class MultiEdge(object):
784 """An "edge" between multiple vertices"""
786 self
.site_link
= None # object siteLink
788 self
.con_type
= None # interSiteTransport GUID
789 self
.repl_info
= ReplInfo()
793 class InternalEdge(object):
794 """An edge that forms part of the minimal spanning tree
796 These are used in the Kruskal's algorithm. Their interesting
797 feature isa that they are sortable, with the good edges sorting
798 before the bad ones -- lower is better.
800 def __init__(self
, v1
, v2
, redred
, repl
, eType
, site_link
):
803 self
.red_red
= redred
804 self
.repl_info
= repl
806 self
.site_link
= site_link
808 def __eq__(self
, other
):
809 return not self
< other
and not other
< self
811 def __ne__(self
, other
):
812 return self
< other
or other
< self
814 def __gt__(self
, other
):
817 def __ge__(self
, other
):
818 return not self
< other
820 def __le__(self
, other
):
821 return not other
< self
823 def __lt__(self
, other
):
824 """Here "less than" means "better".
826 From within MS-ADTS 6.2.2.3.4.4:
828 SORT internalEdges by (descending RedRed,
829 ascending ReplInfo.Cost,
830 descending available time in ReplInfo.Schedule,
835 if self
.red_red
!= other
.red_red
:
838 if self
.repl_info
.cost
!= other
.repl_info
.cost
:
839 return self
.repl_info
.cost
< other
.repl_info
.cost
841 if self
.repl_info
.duration
!= other
.repl_info
.duration
:
842 return self
.repl_info
.duration
> other
.repl_info
.duration
844 if self
.v1
.guid
!= other
.v1
.guid
:
845 return self
.v1
.ndrpacked_guid
< other
.v1
.ndrpacked_guid
847 if self
.v2
.guid
!= other
.v2
.guid
:
848 return self
.v2
.ndrpacked_guid
< other
.v2
.ndrpacked_guid
850 return self
.e_type
< other
.e_type