repl: Set GET_ALL_GROUP_MEMBERSHIP flag in the drepl server
[nivanova/samba-autobuild/.git] / python / samba / kcc / __init__.py
1 # define the KCC object
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
22 import random
23 import uuid
24
25 import itertools
26 from samba import unix2nttime, nttime2unix
27 from samba import ldb, dsdb, drs_utils
28 from samba.auth import system_session
29 from samba.samdb import SamDB
30 from samba.dcerpc import drsuapi, misc
31
32 from samba.kcc.kcc_utils import Site, Partition, Transport, SiteLink
33 from samba.kcc.kcc_utils import NCReplica, NCType, nctype_lut, GraphNode
34 from samba.kcc.kcc_utils import RepsFromTo, KCCError, KCCFailedObject
35 from samba.kcc.graph import convert_schedule_to_repltimes
36
37 from samba.ndr import ndr_pack
38
39 from samba.kcc.graph_utils import verify_and_dot
40
41 from samba.kcc import ldif_import_export
42 from samba.kcc.graph import setup_graph, get_spanning_tree_edges
43 from samba.kcc.graph import Vertex
44
45 from samba.kcc.debug import DEBUG, DEBUG_FN, logger
46 from samba.kcc import debug
47
48
49 def sort_replica_by_dsa_guid(rep1, rep2):
50     """Helper to sort NCReplicas by their DSA guids
51
52     The guids need to be sorted in their NDR form.
53
54     :param rep1: An NC replica
55     :param rep2: Another replica
56     :return: -1, 0, or 1, indicating sort order.
57     """
58     return cmp(ndr_pack(rep1.rep_dsa_guid), ndr_pack(rep2.rep_dsa_guid))
59
60
61 def sort_dsa_by_gc_and_guid(dsa1, dsa2):
62     """Helper to sort DSAs by guid global catalog status
63
64     GC DSAs come before non-GC DSAs, other than that, the guids are
65     sorted in NDR form.
66
67     :param dsa1: A DSA object
68     :param dsa2: Another DSA
69     :return: -1, 0, or 1, indicating sort order.
70     """
71     if dsa1.is_gc() and not dsa2.is_gc():
72         return -1
73     if not dsa1.is_gc() and dsa2.is_gc():
74         return +1
75     return cmp(ndr_pack(dsa1.dsa_guid), ndr_pack(dsa2.dsa_guid))
76
77
78 def is_smtp_replication_available():
79     """Can the KCC use SMTP replication?
80
81     Currently always returns false because Samba doesn't implement
82     SMTP transfer for NC changes between DCs.
83
84     :return: Boolean (always False)
85     """
86     return False
87
88
89 class KCC(object):
90     """The Knowledge Consistency Checker class.
91
92     A container for objects and methods allowing a run of the KCC.  Produces a
93     set of connections in the samdb for which the Distributed Replication
94     Service can then utilize to replicate naming contexts
95
96     :param unix_now: The putative current time in seconds since 1970.
97     :param read_only: Don't write to the database.
98     :param verify: Check topological invariants for the generated graphs
99     :param debug: Write verbosely to stderr.
100     "param dot_file_dir: write diagnostic Graphviz files in this directory
101     """
102     def __init__(self, unix_now, readonly=False, verify=False, debug=False,
103                  dot_file_dir=None):
104         """Initializes the partitions class which can hold
105         our local DCs partitions or all the partitions in
106         the forest
107         """
108         self.part_table = {}    # partition objects
109         self.site_table = {}
110         self.ip_transport = None
111         self.sitelink_table = {}
112         self.dsa_by_dnstr = {}
113         self.dsa_by_guid = {}
114
115         self.get_dsa_by_guidstr = self.dsa_by_guid.get
116         self.get_dsa = self.dsa_by_dnstr.get
117
118         # TODO: These should be backed by a 'permanent' store so that when
119         # calling DRSGetReplInfo with DS_REPL_INFO_KCC_DSA_CONNECT_FAILURES,
120         # the failure information can be returned
121         self.kcc_failed_links = {}
122         self.kcc_failed_connections = set()
123
124         # Used in inter-site topology computation.  A list
125         # of connections (by NTDSConnection object) that are
126         # to be kept when pruning un-needed NTDS Connections
127         self.kept_connections = set()
128
129         self.my_dsa_dnstr = None  # My dsa DN
130         self.my_dsa = None  # My dsa object
131
132         self.my_site_dnstr = None
133         self.my_site = None
134
135         self.samdb = None
136
137         self.unix_now = unix_now
138         self.nt_now = unix2nttime(unix_now)
139         self.readonly = readonly
140         self.verify = verify
141         self.debug = debug
142         self.dot_file_dir = dot_file_dir
143
144     def load_ip_transport(self):
145         """Loads the inter-site transport objects for Sites
146
147         :return: None
148         :raise KCCError: if no IP transport is found
149         """
150         try:
151             res = self.samdb.search("CN=Inter-Site Transports,CN=Sites,%s" %
152                                     self.samdb.get_config_basedn(),
153                                     scope=ldb.SCOPE_SUBTREE,
154                                     expression="(objectClass=interSiteTransport)")
155         except ldb.LdbError, (enum, estr):
156             raise KCCError("Unable to find inter-site transports - (%s)" %
157                            estr)
158
159         for msg in res:
160             dnstr = str(msg.dn)
161
162             transport = Transport(dnstr)
163
164             transport.load_transport(self.samdb)
165             if transport.name == 'IP':
166                 self.ip_transport = transport
167             elif transport.name == 'SMTP':
168                 logger.debug("Samba KCC is ignoring the obsolete "
169                              "SMTP transport.")
170
171             else:
172                 logger.warning("Samba KCC does not support the transport "
173                                "called %r." % (transport.name,))
174
175         if self.ip_transport is None:
176             raise KCCError("there doesn't seem to be an IP transport")
177
178     def load_all_sitelinks(self):
179         """Loads the inter-site siteLink objects
180
181         :return: None
182         :raise KCCError: if site-links aren't found
183         """
184         try:
185             res = self.samdb.search("CN=Inter-Site Transports,CN=Sites,%s" %
186                                     self.samdb.get_config_basedn(),
187                                     scope=ldb.SCOPE_SUBTREE,
188                                     expression="(objectClass=siteLink)")
189         except ldb.LdbError, (enum, estr):
190             raise KCCError("Unable to find inter-site siteLinks - (%s)" % estr)
191
192         for msg in res:
193             dnstr = str(msg.dn)
194
195             # already loaded
196             if dnstr in self.sitelink_table:
197                 continue
198
199             sitelink = SiteLink(dnstr)
200
201             sitelink.load_sitelink(self.samdb)
202
203             # Assign this siteLink to table
204             # and index by dn
205             self.sitelink_table[dnstr] = sitelink
206
207     def load_site(self, dn_str):
208         """Helper for load_my_site and load_all_sites.
209
210         Put all the site's DSAs into the KCC indices.
211
212         :param dn_str: a site dn_str
213         :return: the Site object pertaining to the dn_str
214         """
215         site = Site(dn_str, self.unix_now)
216         site.load_site(self.samdb)
217
218         # We avoid replacing the site with an identical copy in case
219         # somewhere else has a reference to the old one, which would
220         # lead to all manner of confusion and chaos.
221         guid = str(site.site_guid)
222         if guid not in self.site_table:
223             self.site_table[guid] = site
224             self.dsa_by_dnstr.update(site.dsa_table)
225             self.dsa_by_guid.update((str(x.dsa_guid), x)
226                                     for x in site.dsa_table.values())
227
228         return self.site_table[guid]
229
230     def load_my_site(self):
231         """Load the Site object for the local DSA.
232
233         :return: None
234         """
235         self.my_site_dnstr = ("CN=%s,CN=Sites,%s" % (
236             self.samdb.server_site_name(),
237             self.samdb.get_config_basedn()))
238
239         self.my_site = self.load_site(self.my_site_dnstr)
240
241     def load_all_sites(self):
242         """Discover all sites and create Site objects.
243
244         :return: None
245         :raise: KCCError if sites can't be found
246         """
247         try:
248             res = self.samdb.search("CN=Sites,%s" %
249                                     self.samdb.get_config_basedn(),
250                                     scope=ldb.SCOPE_SUBTREE,
251                                     expression="(objectClass=site)")
252         except ldb.LdbError, (enum, estr):
253             raise KCCError("Unable to find sites - (%s)" % estr)
254
255         for msg in res:
256             sitestr = str(msg.dn)
257             self.load_site(sitestr)
258
259     def load_my_dsa(self):
260         """Discover my nTDSDSA dn thru the rootDSE entry
261
262         :return: None
263         :raise: KCCError if DSA can't be found
264         """
265         dn_query = "<GUID=%s>" % self.samdb.get_ntds_GUID()
266         dn = ldb.Dn(self.samdb, dn_query)
267         try:
268             res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE,
269                                     attrs=["objectGUID"])
270         except ldb.LdbError, (enum, estr):
271             DEBUG_FN("Search for dn '%s' [from %s] failed: %s. "
272                      "This typically happens in --importldif mode due "
273                      "to lack of module support." % (dn, dn_query, estr))
274             try:
275                 # We work around the failure above by looking at the
276                 # dsServiceName that was put in the fake rootdse by
277                 # the --exportldif, rather than the
278                 # samdb.get_ntds_GUID(). The disadvantage is that this
279                 # mode requires we modify the @ROOTDSE dnq to support
280                 # --forced-local-dsa
281                 service_name_res = self.samdb.search(base="",
282                                                      scope=ldb.SCOPE_BASE,
283                                                      attrs=["dsServiceName"])
284                 dn = ldb.Dn(self.samdb,
285                             service_name_res[0]["dsServiceName"][0])
286
287                 res = self.samdb.search(base=dn, scope=ldb.SCOPE_BASE,
288                                         attrs=["objectGUID"])
289             except ldb.LdbError, (enum, estr):
290                 raise KCCError("Unable to find my nTDSDSA - (%s)" % estr)
291
292         if len(res) != 1:
293             raise KCCError("Unable to find my nTDSDSA at %s" %
294                            dn.extended_str())
295
296         ntds_guid = misc.GUID(self.samdb.get_ntds_GUID())
297         if misc.GUID(res[0]["objectGUID"][0]) != ntds_guid:
298             raise KCCError("Did not find the GUID we expected,"
299                            " perhaps due to --importldif")
300
301         self.my_dsa_dnstr = str(res[0].dn)
302
303         self.my_dsa = self.my_site.get_dsa(self.my_dsa_dnstr)
304
305         if self.my_dsa_dnstr not in self.dsa_by_dnstr:
306             debug.DEBUG_DARK_YELLOW("my_dsa %s isn't in self.dsas_by_dnstr:"
307                                     " it must be RODC.\n"
308                                     "Let's add it, because my_dsa is special!"
309                                     "\n(likewise for self.dsa_by_guid)" %
310                                     self.my_dsa_dnstr)
311
312             self.dsa_by_dnstr[self.my_dsa_dnstr] = self.my_dsa
313             self.dsa_by_guid[str(self.my_dsa.dsa_guid)] = self.my_dsa
314
315     def load_all_partitions(self):
316         """Discover and load all partitions.
317
318         Each NC is inserted into the part_table by partition
319         dn string (not the nCName dn string)
320
321         :return: None
322         :raise: KCCError if partitions can't be found
323         """
324         try:
325             res = self.samdb.search("CN=Partitions,%s" %
326                                     self.samdb.get_config_basedn(),
327                                     scope=ldb.SCOPE_SUBTREE,
328                                     expression="(objectClass=crossRef)")
329         except ldb.LdbError, (enum, estr):
330             raise KCCError("Unable to find partitions - (%s)" % estr)
331
332         for msg in res:
333             partstr = str(msg.dn)
334
335             # already loaded
336             if partstr in self.part_table:
337                 continue
338
339             part = Partition(partstr)
340
341             part.load_partition(self.samdb)
342             self.part_table[partstr] = part
343
344     def refresh_failed_links_connections(self, ping=None):
345         """Ensure the failed links list is up to date
346
347         Based on MS-ADTS 6.2.2.1
348
349         :param ping: An oracle function of remote site availability
350         :return: None
351         """
352         # LINKS: Refresh failed links
353         self.kcc_failed_links = {}
354         current, needed = self.my_dsa.get_rep_tables()
355         for replica in current.values():
356             # For every possible connection to replicate
357             for reps_from in replica.rep_repsFrom:
358                 failure_count = reps_from.consecutive_sync_failures
359                 if failure_count <= 0:
360                     continue
361
362                 dsa_guid = str(reps_from.source_dsa_obj_guid)
363                 time_first_failure = reps_from.last_success
364                 last_result = reps_from.last_attempt
365                 dns_name = reps_from.dns_name1
366
367                 f = self.kcc_failed_links.get(dsa_guid)
368                 if f is None:
369                     f = KCCFailedObject(dsa_guid, failure_count,
370                                         time_first_failure, last_result,
371                                         dns_name)
372                     self.kcc_failed_links[dsa_guid] = f
373                 else:
374                     f.failure_count = max(f.failure_count, failure_count)
375                     f.time_first_failure = min(f.time_first_failure,
376                                                time_first_failure)
377                     f.last_result = last_result
378
379         # CONNECTIONS: Refresh failed connections
380         restore_connections = set()
381         if ping is not None:
382             DEBUG("refresh_failed_links: checking if links are still down")
383             for connection in self.kcc_failed_connections:
384                 if ping(connection.dns_name):
385                     # Failed connection is no longer failing
386                     restore_connections.add(connection)
387                 else:
388                     connection.failure_count += 1
389         else:
390             DEBUG("refresh_failed_links: not checking live links because we\n"
391                   "weren't asked to --attempt-live-connections")
392
393         # Remove the restored connections from the failed connections
394         self.kcc_failed_connections.difference_update(restore_connections)
395
396     def is_stale_link_connection(self, target_dsa):
397         """Check whether a link to a remote DSA is stale
398
399         Used in MS-ADTS 6.2.2.2 Intrasite Connection Creation
400
401         Returns True if the remote seems to have been down for at
402         least two hours, otherwise False.
403
404         :param target_dsa: the remote DSA object
405         :return: True if link is stale, otherwise False
406         """
407         failed_link = self.kcc_failed_links.get(str(target_dsa.dsa_guid))
408         if failed_link:
409             # failure_count should be > 0, but check anyways
410             if failed_link.failure_count > 0:
411                 unix_first_failure = \
412                     nttime2unix(failed_link.time_first_failure)
413                 # TODO guard against future
414                 if unix_first_failure > self.unix_now:
415                     logger.error("The last success time attribute for \
416                                  repsFrom is in the future!")
417
418                 # Perform calculation in seconds
419                 if (self.unix_now - unix_first_failure) > 60 * 60 * 2:
420                     return True
421
422         # TODO connections.
423         # We have checked failed *links*, but we also need to check
424         # *connections*
425
426         return False
427
428     # TODO: This should be backed by some form of local database
429     def remove_unneeded_failed_links_connections(self):
430         # Remove all tuples in kcc_failed_links where failure count = 0
431         # In this implementation, this should never happen.
432
433         # Remove all connections which were not used this run or connections
434         # that became active during this run.
435         pass
436
437     def _ensure_connections_are_loaded(self, connections):
438         """Load or fake-load NTDSConnections lacking GUIDs
439
440         New connections don't have GUIDs and created times which are
441         needed for sorting. If we're in read-only mode, we make fake
442         GUIDs, otherwise we ask SamDB to do it for us.
443
444         :param connections: an iterable of NTDSConnection objects.
445         :return: None
446         """
447         for cn_conn in connections:
448             if cn_conn.guid is None:
449                 if self.readonly:
450                     cn_conn.guid = misc.GUID(str(uuid.uuid4()))
451                     cn_conn.whenCreated = self.nt_now
452                 else:
453                     cn_conn.load_connection(self.samdb)
454
455     def _mark_broken_ntdsconn(self):
456         """Find NTDS Connections that lack a remote
457
458         I'm not sure how they appear. Let's be rid of them by marking
459         them with the to_be_deleted attribute.
460
461         :return: None
462         """
463         for cn_conn in self.my_dsa.connect_table.values():
464             s_dnstr = cn_conn.get_from_dnstr()
465             if s_dnstr is None:
466                 DEBUG_FN("%s has phantom connection %s" % (self.my_dsa,
467                                                            cn_conn))
468                 cn_conn.to_be_deleted = True
469
470     def _mark_unneeded_local_ntdsconn(self):
471         """Find unneeded intrasite NTDS Connections for removal
472
473         Based on MS-ADTS 6.2.2.4 Removing Unnecessary Connections.
474         Every DC removes its own unnecessary intrasite connections.
475         This function tags them with the to_be_deleted attribute.
476
477         :return: None
478         """
479         # XXX should an RODC be regarded as same site? It isn't part
480         # of the intrasite ring.
481
482         if self.my_site.is_cleanup_ntdsconn_disabled():
483             DEBUG_FN("not doing ntdsconn cleanup for site %s, "
484                      "because it is disabled" % self.my_site)
485             return
486
487         mydsa = self.my_dsa
488
489         try:
490             self._ensure_connections_are_loaded(mydsa.connect_table.values())
491         except KCCError:
492             # RODC never actually added any connections to begin with
493             if mydsa.is_ro():
494                 return
495
496         local_connections = []
497
498         for cn_conn in mydsa.connect_table.values():
499             s_dnstr = cn_conn.get_from_dnstr()
500             if s_dnstr in self.my_site.dsa_table:
501                 removable = not (cn_conn.is_generated() or
502                                  cn_conn.is_rodc_topology())
503                 packed_guid = ndr_pack(cn_conn.guid)
504                 local_connections.append((cn_conn, s_dnstr,
505                                           packed_guid, removable))
506
507         for a, b in itertools.permutations(local_connections, 2):
508             cn_conn, s_dnstr, packed_guid, removable = a
509             cn_conn2, s_dnstr2, packed_guid2, removable2 = b
510             if (removable and
511                 s_dnstr == s_dnstr2 and
512                 cn_conn.whenCreated < cn_conn2.whenCreated or
513                 (cn_conn.whenCreated == cn_conn2.whenCreated and
514                  packed_guid < packed_guid2)):
515                 cn_conn.to_be_deleted = True
516
517     def _mark_unneeded_intersite_ntdsconn(self):
518         """find unneeded intersite NTDS Connections for removal
519
520         Based on MS-ADTS 6.2.2.4 Removing Unnecessary Connections. The
521         intersite topology generator removes links for all DCs in its
522         site. Here we just tag them with the to_be_deleted attribute.
523
524         :return: None
525         """
526         # TODO Figure out how best to handle the RODC case
527         # The RODC is ITSG, but shouldn't act on anyone's behalf.
528         if self.my_dsa.is_ro():
529             return
530
531         # Find the intersite connections
532         local_dsas = self.my_site.dsa_table
533         connections_and_dsas = []
534         for dsa in local_dsas.values():
535             for cn in dsa.connect_table.values():
536                 if cn.to_be_deleted:
537                     continue
538                 s_dnstr = cn.get_from_dnstr()
539                 if s_dnstr is None:
540                     continue
541                 if s_dnstr not in local_dsas:
542                     from_dsa = self.get_dsa(s_dnstr)
543                     # Samba ONLY: ISTG removes connections to dead DCs
544                     if from_dsa is None and '\\0ADEL' in s_dnstr:
545                         logger.info("DSA appears deleted, removing connection %s" % s_dnstr)
546                         cn.to_be_deleted = True
547                         continue
548                     connections_and_dsas.append((cn, dsa, from_dsa))
549
550         self._ensure_connections_are_loaded(x[0] for x in connections_and_dsas)
551         for cn, to_dsa, from_dsa in connections_and_dsas:
552             if not cn.is_generated() or cn.is_rodc_topology():
553                 continue
554
555             # If the connection is in the kept_connections list, we
556             # only remove it if an endpoint seems down.
557             if (cn in self.kept_connections and
558                 not (self.is_bridgehead_failed(to_dsa, True) or
559                      self.is_bridgehead_failed(from_dsa, True))):
560                 continue
561
562             # this one is broken and might be superseded by another.
563             # But which other? Let's just say another link to the same
564             # site can supersede.
565             from_dnstr = from_dsa.dsa_dnstr
566             for site in self.site_table.values():
567                 if from_dnstr in site.rw_dsa_table:
568                     for cn2, to_dsa2, from_dsa2 in connections_and_dsas:
569                         if (cn is not cn2 and
570                             from_dsa2 in site.rw_dsa_table):
571                             cn.to_be_deleted = True
572
573     def _commit_changes(self, dsa):
574         if dsa.is_ro() or self.readonly:
575             for connect in dsa.connect_table.values():
576                 if connect.to_be_deleted:
577                     logger.info("TO BE DELETED:\n%s" % connect)
578                 if connect.to_be_added:
579                     logger.info("TO BE ADDED:\n%s" % connect)
580                 if connect.to_be_modified:
581                     logger.info("TO BE MODIFIED:\n%s" % connect)
582
583             # Peform deletion from our tables but perform
584             # no database modification
585             dsa.commit_connections(self.samdb, ro=True)
586         else:
587             # Commit any modified connections
588             dsa.commit_connections(self.samdb)
589
590     def remove_unneeded_ntdsconn(self, all_connected):
591         """Remove unneeded NTDS Connections once topology is calculated
592
593         Based on MS-ADTS 6.2.2.4 Removing Unnecessary Connections
594
595         :param all_connected: indicates whether all sites are connected
596         :return: None
597         """
598         self._mark_broken_ntdsconn()
599         self._mark_unneeded_local_ntdsconn()
600         # if we are not the istg, we're done!
601         # if we are the istg, but all_connected is False, we also do nothing.
602         if self.my_dsa.is_istg() and all_connected:
603             self._mark_unneeded_intersite_ntdsconn()
604
605         for dsa in self.my_site.dsa_table.values():
606             self._commit_changes(dsa)
607
608     def modify_repsFrom(self, n_rep, t_repsFrom, s_rep, s_dsa, cn_conn):
609         """Update an repsFrom object if required.
610
611         Part of MS-ADTS 6.2.2.5.
612
613         Update t_repsFrom if necessary to satisfy requirements. Such
614         updates are typically required when the IDL_DRSGetNCChanges
615         server has moved from one site to another--for example, to
616         enable compression when the server is moved from the
617         client's site to another site.
618
619         The repsFrom.update_flags bit field may be modified
620         auto-magically if any changes are made here. See
621         kcc_utils.RepsFromTo for gory details.
622
623
624         :param n_rep: NC replica we need
625         :param t_repsFrom: repsFrom tuple to modify
626         :param s_rep: NC replica at source DSA
627         :param s_dsa: source DSA
628         :param cn_conn: Local DSA NTDSConnection child
629
630         :return: None
631         """
632         s_dnstr = s_dsa.dsa_dnstr
633         same_site = s_dnstr in self.my_site.dsa_table
634
635         # if schedule doesn't match then update and modify
636         times = convert_schedule_to_repltimes(cn_conn.schedule)
637         if times != t_repsFrom.schedule:
638             t_repsFrom.schedule = times
639
640         # Bit DRS_ADD_REF is set in replicaFlags unconditionally
641         # Samba ONLY:
642         if ((t_repsFrom.replica_flags &
643              drsuapi.DRSUAPI_DRS_ADD_REF) == 0x0):
644             t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_ADD_REF
645
646         # Bit DRS_PER_SYNC is set in replicaFlags if and only
647         # if nTDSConnection schedule has a value v that specifies
648         # scheduled replication is to be performed at least once
649         # per week.
650         if cn_conn.is_schedule_minimum_once_per_week():
651
652             if ((t_repsFrom.replica_flags &
653                  drsuapi.DRSUAPI_DRS_PER_SYNC) == 0x0):
654                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_PER_SYNC
655
656         # Bit DRS_INIT_SYNC is set in t.replicaFlags if and only
657         # if the source DSA and the local DC's nTDSDSA object are
658         # in the same site or source dsa is the FSMO role owner
659         # of one or more FSMO roles in the NC replica.
660         if same_site or n_rep.is_fsmo_role_owner(s_dnstr):
661
662             if ((t_repsFrom.replica_flags &
663                  drsuapi.DRSUAPI_DRS_INIT_SYNC) == 0x0):
664                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_INIT_SYNC
665
666         # If bit NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT is set in
667         # cn!options, bit DRS_NEVER_NOTIFY is set in t.replicaFlags
668         # if and only if bit NTDSCONN_OPT_USE_NOTIFY is clear in
669         # cn!options. Otherwise, bit DRS_NEVER_NOTIFY is set in
670         # t.replicaFlags if and only if s and the local DC's
671         # nTDSDSA object are in different sites.
672         if ((cn_conn.options &
673              dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT) != 0x0):
674
675             if (cn_conn.options & dsdb.NTDSCONN_OPT_USE_NOTIFY) == 0x0:
676                 # WARNING
677                 #
678                 # it LOOKS as if this next test is a bit silly: it
679                 # checks the flag then sets it if it not set; the same
680                 # effect could be achieved by unconditionally setting
681                 # it. But in fact the repsFrom object has special
682                 # magic attached to it, and altering replica_flags has
683                 # side-effects. That is bad in my opinion, but there
684                 # you go.
685                 if ((t_repsFrom.replica_flags &
686                      drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0):
687                     t_repsFrom.replica_flags |= \
688                         drsuapi.DRSUAPI_DRS_NEVER_NOTIFY
689
690         elif not same_site:
691
692             if ((t_repsFrom.replica_flags &
693                  drsuapi.DRSUAPI_DRS_NEVER_NOTIFY) == 0x0):
694                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_NEVER_NOTIFY
695
696         # Bit DRS_USE_COMPRESSION is set in t.replicaFlags if
697         # and only if s and the local DC's nTDSDSA object are
698         # not in the same site and the
699         # NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION bit is
700         # clear in cn!options
701         if (not same_site and
702             (cn_conn.options &
703              dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION) == 0x0):
704
705             if ((t_repsFrom.replica_flags &
706                  drsuapi.DRSUAPI_DRS_USE_COMPRESSION) == 0x0):
707                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_USE_COMPRESSION
708
709         # Bit DRS_TWOWAY_SYNC is set in t.replicaFlags if and only
710         # if bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options.
711         if (cn_conn.options & dsdb.NTDSCONN_OPT_TWOWAY_SYNC) != 0x0:
712
713             if ((t_repsFrom.replica_flags &
714                  drsuapi.DRSUAPI_DRS_TWOWAY_SYNC) == 0x0):
715                 t_repsFrom.replica_flags |= drsuapi.DRSUAPI_DRS_TWOWAY_SYNC
716
717         # Bits DRS_DISABLE_AUTO_SYNC and DRS_DISABLE_PERIODIC_SYNC are
718         # set in t.replicaFlags if and only if cn!enabledConnection = false.
719         if not cn_conn.is_enabled():
720
721             if ((t_repsFrom.replica_flags &
722                  drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC) == 0x0):
723                 t_repsFrom.replica_flags |= \
724                     drsuapi.DRSUAPI_DRS_DISABLE_AUTO_SYNC
725
726             if ((t_repsFrom.replica_flags &
727                  drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC) == 0x0):
728                 t_repsFrom.replica_flags |= \
729                     drsuapi.DRSUAPI_DRS_DISABLE_PERIODIC_SYNC
730
731         # If s and the local DC's nTDSDSA object are in the same site,
732         # cn!transportType has no value, or the RDN of cn!transportType
733         # is CN=IP:
734         #
735         #     Bit DRS_MAIL_REP in t.replicaFlags is clear.
736         #
737         #     t.uuidTransport = NULL GUID.
738         #
739         #     t.uuidDsa = The GUID-based DNS name of s.
740         #
741         # Otherwise:
742         #
743         #     Bit DRS_MAIL_REP in t.replicaFlags is set.
744         #
745         #     If x is the object with dsname cn!transportType,
746         #     t.uuidTransport = x!objectGUID.
747         #
748         #     Let a be the attribute identified by
749         #     x!transportAddressAttribute. If a is
750         #     the dNSHostName attribute, t.uuidDsa = the GUID-based
751         #      DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
752         #
753         # It appears that the first statement i.e.
754         #
755         #     "If s and the local DC's nTDSDSA object are in the same
756         #      site, cn!transportType has no value, or the RDN of
757         #      cn!transportType is CN=IP:"
758         #
759         # could be a slightly tighter statement if it had an "or"
760         # between each condition.  I believe this should
761         # be interpreted as:
762         #
763         #     IF (same-site) OR (no-value) OR (type-ip)
764         #
765         # because IP should be the primary transport mechanism
766         # (even in inter-site) and the absense of the transportType
767         # attribute should always imply IP no matter if its multi-site
768         #
769         # NOTE MS-TECH INCORRECT:
770         #
771         #     All indications point to these statements above being
772         #     incorrectly stated:
773         #
774         #         t.uuidDsa = The GUID-based DNS name of s.
775         #
776         #         Let a be the attribute identified by
777         #         x!transportAddressAttribute. If a is
778         #         the dNSHostName attribute, t.uuidDsa = the GUID-based
779         #         DNS name of s. Otherwise, t.uuidDsa = (s!parent)!a.
780         #
781         #     because the uuidDSA is a GUID and not a GUID-base DNS
782         #     name.  Nor can uuidDsa hold (s!parent)!a if not
783         #     dNSHostName.  What should have been said is:
784         #
785         #         t.naDsa = The GUID-based DNS name of s
786         #
787         #     That would also be correct if transportAddressAttribute
788         #     were "mailAddress" because (naDsa) can also correctly
789         #     hold the SMTP ISM service address.
790         #
791         nastr = "%s._msdcs.%s" % (s_dsa.dsa_guid, self.samdb.forest_dns_name())
792
793         if ((t_repsFrom.replica_flags &
794              drsuapi.DRSUAPI_DRS_MAIL_REP) != 0x0):
795             t_repsFrom.replica_flags &= ~drsuapi.DRSUAPI_DRS_MAIL_REP
796
797         t_repsFrom.transport_guid = misc.GUID()
798
799         # See (NOTE MS-TECH INCORRECT) above
800
801         # NOTE: it looks like these conditionals are pointless,
802         # because the state will end up as `t_repsFrom.dns_name1 ==
803         # nastr` in either case, BUT the repsFrom thing is magic and
804         # assigning to it alters some flags. So we try not to update
805         # it unless necessary.
806         if t_repsFrom.dns_name1 != nastr:
807             t_repsFrom.dns_name1 = nastr
808
809         if t_repsFrom.version > 0x1 and t_repsFrom.dns_name2 != nastr:
810             t_repsFrom.dns_name2 = nastr
811
812         if t_repsFrom.is_modified():
813             DEBUG_FN("modify_repsFrom(): %s" % t_repsFrom)
814
815     def get_dsa_for_implied_replica(self, n_rep, cn_conn):
816         """If a connection imply a replica, find the relevant DSA
817
818         Given a NC replica and NTDS Connection, determine if the
819         connection implies a repsFrom tuple should be present from the
820         source DSA listed in the connection to the naming context. If
821         it should be, return the DSA; otherwise return None.
822
823         Based on part of MS-ADTS 6.2.2.5
824
825         :param n_rep: NC replica
826         :param cn_conn: NTDS Connection
827         :return: source DSA or None
828         """
829         # XXX different conditions for "implies" than MS-ADTS 6.2.2
830         # preamble.
831
832         # It boils down to: we want an enabled, non-FRS connections to
833         # a valid remote DSA with a non-RO replica corresponding to
834         # n_rep.
835
836         if not cn_conn.is_enabled() or cn_conn.is_rodc_topology():
837             return None
838
839         s_dnstr = cn_conn.get_from_dnstr()
840         s_dsa = self.get_dsa(s_dnstr)
841
842         # No DSA matching this source DN string?
843         if s_dsa is None:
844             return None
845
846         s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
847
848         if (s_rep is not None and
849             s_rep.is_present() and
850             (not s_rep.is_ro() or n_rep.is_partial())):
851             return s_dsa
852         return None
853
854     def translate_ntdsconn(self, current_dsa=None):
855         """Adjust repsFrom to match NTDSConnections
856
857         This function adjusts values of repsFrom abstract attributes of NC
858         replicas on the local DC to match those implied by
859         nTDSConnection objects.
860
861         Based on [MS-ADTS] 6.2.2.5
862
863         :param current_dsa: optional DSA on whose behalf we are acting.
864         :return: None
865         """
866         count = 0
867
868         ro = False
869         if current_dsa is None:
870             current_dsa = self.my_dsa
871
872         if current_dsa.is_ro():
873             ro = True
874
875         if current_dsa.is_translate_ntdsconn_disabled():
876             DEBUG_FN("skipping translate_ntdsconn() "
877                      "because disabling flag is set")
878             return
879
880         DEBUG_FN("translate_ntdsconn(): enter")
881
882         current_rep_table, needed_rep_table = current_dsa.get_rep_tables()
883
884         # Filled in with replicas we currently have that need deleting
885         delete_reps = set()
886
887         # We're using the MS notation names here to allow
888         # correlation back to the published algorithm.
889         #
890         # n_rep      - NC replica (n)
891         # t_repsFrom - tuple (t) in n!repsFrom
892         # s_dsa      - Source DSA of the replica. Defined as nTDSDSA
893         #              object (s) such that (s!objectGUID = t.uuidDsa)
894         #              In our IDL representation of repsFrom the (uuidDsa)
895         #              attribute is called (source_dsa_obj_guid)
896         # cn_conn    - (cn) is nTDSConnection object and child of the local
897         #               DC's nTDSDSA object and (cn!fromServer = s)
898         # s_rep      - source DSA replica of n
899         #
900         # If we have the replica and its not needed
901         # then we add it to the "to be deleted" list.
902         for dnstr in current_rep_table:
903             # If we're on the RODC, hardcode the update flags
904             if ro:
905                 c_rep = current_rep_table[dnstr]
906                 c_rep.load_repsFrom(self.samdb)
907                 for t_repsFrom in c_rep.rep_repsFrom:
908                     replica_flags = (drsuapi.DRSUAPI_DRS_INIT_SYNC |
909                                      drsuapi.DRSUAPI_DRS_PER_SYNC |
910                                      drsuapi.DRSUAPI_DRS_ADD_REF |
911                                      drsuapi.DRSUAPI_DRS_SPECIAL_SECRET_PROCESSING |
912                                      drsuapi.DRSUAPI_DRS_NONGC_RO_REP)
913                     if t_repsFrom.replica_flags != replica_flags:
914                         t_repsFrom.replica_flags = replica_flags
915                 c_rep.commit_repsFrom(self.samdb)
916             else:
917                 if dnstr not in needed_rep_table:
918                     delete_reps.add(dnstr)
919
920         DEBUG_FN('current %d needed %d delete %d' % (len(current_rep_table),
921                  len(needed_rep_table), len(delete_reps)))
922
923         if delete_reps:
924             # TODO Must delete repsFrom/repsTo for these replicas
925             DEBUG('deleting these reps: %s' % delete_reps)
926             for dnstr in delete_reps:
927                 del current_rep_table[dnstr]
928
929         # HANDLE REPS-FROM
930         #
931         # Now perform the scan of replicas we'll need
932         # and compare any current repsFrom against the
933         # connections
934         for n_rep in needed_rep_table.values():
935
936             # load any repsFrom and fsmo roles as we'll
937             # need them during connection translation
938             n_rep.load_repsFrom(self.samdb)
939             n_rep.load_fsmo_roles(self.samdb)
940
941             # Loop thru the existing repsFrom tuples (if any)
942             # XXX This is a list and could contain duplicates
943             #     (multiple load_repsFrom calls)
944             for t_repsFrom in n_rep.rep_repsFrom:
945
946                 # for each tuple t in n!repsFrom, let s be the nTDSDSA
947                 # object such that s!objectGUID = t.uuidDsa
948                 guidstr = str(t_repsFrom.source_dsa_obj_guid)
949                 s_dsa = self.get_dsa_by_guidstr(guidstr)
950
951                 # Source dsa is gone from config (strange)
952                 # so cleanup stale repsFrom for unlisted DSA
953                 if s_dsa is None:
954                     logger.warning("repsFrom source DSA guid (%s) not found" %
955                                    guidstr)
956                     t_repsFrom.to_be_deleted = True
957                     continue
958
959                 # Find the connection that this repsFrom would use. If
960                 # there isn't a good one (i.e. non-RODC_TOPOLOGY,
961                 # meaning non-FRS), we delete the repsFrom.
962                 s_dnstr = s_dsa.dsa_dnstr
963                 connections = current_dsa.get_connection_by_from_dnstr(s_dnstr)
964                 for cn_conn in connections:
965                     if not cn_conn.is_rodc_topology():
966                         break
967                 else:
968                     # no break means no non-rodc_topology connection exists
969                     t_repsFrom.to_be_deleted = True
970                     continue
971
972                 # KCC removes this repsFrom tuple if any of the following
973                 # is true:
974                 #     No NC replica of the NC "is present" on DSA that
975                 #     would be source of replica
976                 #
977                 #     A writable replica of the NC "should be present" on
978                 #     the local DC, but a partial replica "is present" on
979                 #     the source DSA
980                 s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
981
982                 if s_rep is None or not s_rep.is_present() or \
983                    (not n_rep.is_ro() and s_rep.is_partial()):
984
985                     t_repsFrom.to_be_deleted = True
986                     continue
987
988                 # If the KCC did not remove t from n!repsFrom, it updates t
989                 self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)
990
991             # Loop thru connections and add implied repsFrom tuples
992             # for each NTDSConnection under our local DSA if the
993             # repsFrom is not already present
994             for cn_conn in current_dsa.connect_table.values():
995
996                 s_dsa = self.get_dsa_for_implied_replica(n_rep, cn_conn)
997                 if s_dsa is None:
998                     continue
999
1000                 # Loop thru the existing repsFrom tuples (if any) and
1001                 # if we already have a tuple for this connection then
1002                 # no need to proceed to add.  It will have been changed
1003                 # to have the correct attributes above
1004                 for t_repsFrom in n_rep.rep_repsFrom:
1005                     guidstr = str(t_repsFrom.source_dsa_obj_guid)
1006                     if s_dsa is self.get_dsa_by_guidstr(guidstr):
1007                         s_dsa = None
1008                         break
1009
1010                 if s_dsa is None:
1011                     continue
1012
1013                 # Create a new RepsFromTo and proceed to modify
1014                 # it according to specification
1015                 t_repsFrom = RepsFromTo(n_rep.nc_dnstr)
1016
1017                 t_repsFrom.source_dsa_obj_guid = s_dsa.dsa_guid
1018
1019                 s_rep = s_dsa.get_current_replica(n_rep.nc_dnstr)
1020
1021                 self.modify_repsFrom(n_rep, t_repsFrom, s_rep, s_dsa, cn_conn)
1022
1023                 # Add to our NC repsFrom as this is newly computed
1024                 if t_repsFrom.is_modified():
1025                     n_rep.rep_repsFrom.append(t_repsFrom)
1026
1027             if self.readonly or ro:
1028                 # Display any to be deleted or modified repsFrom
1029                 text = n_rep.dumpstr_to_be_deleted()
1030                 if text:
1031                     logger.info("TO BE DELETED:\n%s" % text)
1032                 text = n_rep.dumpstr_to_be_modified()
1033                 if text:
1034                     logger.info("TO BE MODIFIED:\n%s" % text)
1035
1036                 # Peform deletion from our tables but perform
1037                 # no database modification
1038                 n_rep.commit_repsFrom(self.samdb, ro=True)
1039             else:
1040                 # Commit any modified repsFrom to the NC replica
1041                 n_rep.commit_repsFrom(self.samdb)
1042
1043         # HANDLE REPS-TO:
1044         #
1045         # Now perform the scan of replicas we'll need
1046         # and compare any current repsTo against the
1047         # connections
1048
1049         # RODC should never push to anybody (should we check this?)
1050         if ro:
1051             return
1052
1053         for n_rep in needed_rep_table.values():
1054
1055             # load any repsTo and fsmo roles as we'll
1056             # need them during connection translation
1057             n_rep.load_repsTo(self.samdb)
1058
1059             # Loop thru the existing repsTo tuples (if any)
1060             # XXX This is a list and could contain duplicates
1061             #     (multiple load_repsTo calls)
1062             for t_repsTo in n_rep.rep_repsTo:
1063
1064                 # for each tuple t in n!repsTo, let s be the nTDSDSA
1065                 # object such that s!objectGUID = t.uuidDsa
1066                 guidstr = str(t_repsTo.source_dsa_obj_guid)
1067                 s_dsa = self.get_dsa_by_guidstr(guidstr)
1068
1069                 # Source dsa is gone from config (strange)
1070                 # so cleanup stale repsTo for unlisted DSA
1071                 if s_dsa is None:
1072                     logger.warning("repsTo source DSA guid (%s) not found" %
1073                                    guidstr)
1074                     t_repsTo.to_be_deleted = True
1075                     continue
1076
1077                 # Find the connection that this repsTo would use. If
1078                 # there isn't a good one (i.e. non-RODC_TOPOLOGY,
1079                 # meaning non-FRS), we delete the repsTo.
1080                 s_dnstr = s_dsa.dsa_dnstr
1081                 if '\\0ADEL' in s_dnstr:
1082                     logger.warning("repsTo source DSA guid (%s) appears deleted" %
1083                                    guidstr)
1084                     t_repsTo.to_be_deleted = True
1085                     continue
1086
1087                 connections = s_dsa.get_connection_by_from_dnstr(self.my_dsa_dnstr)
1088                 if len(connections) > 0:
1089                     # Then this repsTo is tentatively valid
1090                     continue
1091                 else:
1092                     # There is no plausible connection for this repsTo
1093                     t_repsTo.to_be_deleted = True
1094
1095             if self.readonly:
1096                 # Display any to be deleted or modified repsTo
1097                 text = n_rep.dumpstr_reps_to()
1098                 if text:
1099                     logger.info("REMOVING REPS-TO:\n%s" % text)
1100
1101                 # Peform deletion from our tables but perform
1102                 # no database modification
1103                 n_rep.commit_repsTo(self.samdb, ro=True)
1104             else:
1105                 # Commit any modified repsTo to the NC replica
1106                 n_rep.commit_repsTo(self.samdb)
1107
1108         # TODO Remove any duplicate repsTo values. This should never happen in
1109         # any normal situations.
1110
1111     def merge_failed_links(self, ping=None):
1112         """Merge of kCCFailedLinks and kCCFailedLinks from bridgeheads.
1113
1114         The KCC on a writable DC attempts to merge the link and connection
1115         failure information from bridgehead DCs in its own site to help it
1116         identify failed bridgehead DCs.
1117
1118         Based on MS-ADTS 6.2.2.3.2 "Merge of kCCFailedLinks and kCCFailedLinks
1119         from Bridgeheads"
1120
1121         :param ping: An oracle of current bridgehead availability
1122         :return: None
1123         """
1124         # 1. Queries every bridgehead server in your site (other than yourself)
1125         # 2. For every ntDSConnection that references a server in a different
1126         #    site merge all the failure info
1127         #
1128         # XXX - not implemented yet
1129         if ping is not None:
1130             debug.DEBUG_RED("merge_failed_links() is NOT IMPLEMENTED")
1131         else:
1132             DEBUG_FN("skipping merge_failed_links() because it requires "
1133                      "real network connections\n"
1134                      "and we weren't asked to --attempt-live-connections")
1135
1136     def setup_graph(self, part):
1137         """Set up an intersite graph
1138
1139         An intersite graph has a Vertex for each site object, a
1140         MultiEdge for each SiteLink object, and a MutliEdgeSet for
1141         each siteLinkBridge object (or implied siteLinkBridge). It
1142         reflects the intersite topology in a slightly more abstract
1143         graph form.
1144
1145         Roughly corresponds to MS-ADTS 6.2.2.3.4.3
1146
1147         :param part: a Partition object
1148         :returns: an InterSiteGraph object
1149         """
1150         # If 'Bridge all site links' is enabled and Win2k3 bridges required
1151         # is not set
1152         # NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
1153         # No documentation for this however, ntdsapi.h appears to have:
1154         # NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED = 0x00001000
1155         bridges_required = self.my_site.site_options & 0x00001002 != 0
1156         transport_guid = str(self.ip_transport.guid)
1157
1158         g = setup_graph(part, self.site_table, transport_guid,
1159                         self.sitelink_table, bridges_required)
1160
1161         if self.verify or self.dot_file_dir is not None:
1162             dot_edges = []
1163             for edge in g.edges:
1164                 for a, b in itertools.combinations(edge.vertices, 2):
1165                     dot_edges.append((a.site.site_dnstr, b.site.site_dnstr))
1166             verify_properties = ()
1167             name = 'site_edges_%s' % part.partstr
1168             verify_and_dot(name, dot_edges, directed=False,
1169                            label=self.my_dsa_dnstr,
1170                            properties=verify_properties, debug=DEBUG,
1171                            verify=self.verify,
1172                            dot_file_dir=self.dot_file_dir)
1173
1174         return g
1175
1176     def get_bridgehead(self, site, part, transport, partial_ok, detect_failed):
1177         """Get a bridghead DC for a site.
1178
1179         Part of MS-ADTS 6.2.2.3.4.4
1180
1181         :param site: site object representing for which a bridgehead
1182             DC is desired.
1183         :param part: crossRef for NC to replicate.
1184         :param transport: interSiteTransport object for replication
1185             traffic.
1186         :param partial_ok: True if a DC containing a partial
1187             replica or a full replica will suffice, False if only
1188             a full replica will suffice.
1189         :param detect_failed: True to detect failed DCs and route
1190             replication traffic around them, False to assume no DC
1191             has failed.
1192         :return: dsa object for the bridgehead DC or None
1193         """
1194
1195         bhs = self.get_all_bridgeheads(site, part, transport,
1196                                        partial_ok, detect_failed)
1197         if not bhs:
1198             debug.DEBUG_MAGENTA("get_bridgehead FAILED:\nsitedn = %s" %
1199                                 site.site_dnstr)
1200             return None
1201
1202         debug.DEBUG_GREEN("get_bridgehead:\n\tsitedn = %s\n\tbhdn = %s" %
1203                           (site.site_dnstr, bhs[0].dsa_dnstr))
1204         return bhs[0]
1205
1206     def get_all_bridgeheads(self, site, part, transport,
1207                             partial_ok, detect_failed):
1208         """Get all bridghead DCs on a site satisfying the given criteria
1209
1210         Part of MS-ADTS 6.2.2.3.4.4
1211
1212         :param site: site object representing the site for which
1213             bridgehead DCs are desired.
1214         :param part: partition for NC to replicate.
1215         :param transport: interSiteTransport object for
1216             replication traffic.
1217         :param partial_ok: True if a DC containing a partial
1218             replica or a full replica will suffice, False if
1219             only a full replica will suffice.
1220         :param detect_failed: True to detect failed DCs and route
1221             replication traffic around them, FALSE to assume
1222             no DC has failed.
1223         :return: list of dsa object for available bridgehead DCs
1224         """
1225         bhs = []
1226
1227         if transport.name != "IP":
1228             raise KCCError("get_all_bridgeheads has run into a "
1229                            "non-IP transport! %r"
1230                            % (transport.name,))
1231
1232         DEBUG_FN(site.rw_dsa_table)
1233         for dsa in site.rw_dsa_table.values():
1234
1235             pdnstr = dsa.get_parent_dnstr()
1236
1237             # IF t!bridgeheadServerListBL has one or more values and
1238             # t!bridgeheadServerListBL does not contain a reference
1239             # to the parent object of dc then skip dc
1240             if ((len(transport.bridgehead_list) != 0 and
1241                  pdnstr not in transport.bridgehead_list)):
1242                 continue
1243
1244             # IF dc is in the same site as the local DC
1245             #    IF a replica of cr!nCName is not in the set of NC replicas
1246             #    that "should be present" on dc or a partial replica of the
1247             #    NC "should be present" but partialReplicasOkay = FALSE
1248             #        Skip dc
1249             if self.my_site.same_site(dsa):
1250                 needed, ro, partial = part.should_be_present(dsa)
1251                 if not needed or (partial and not partial_ok):
1252                     continue
1253                 rep = dsa.get_current_replica(part.nc_dnstr)
1254
1255             # ELSE
1256             #     IF an NC replica of cr!nCName is not in the set of NC
1257             #     replicas that "are present" on dc or a partial replica of
1258             #     the NC "is present" but partialReplicasOkay = FALSE
1259             #          Skip dc
1260             else:
1261                 rep = dsa.get_current_replica(part.nc_dnstr)
1262                 if rep is None or (rep.is_partial() and not partial_ok):
1263                     continue
1264
1265             # IF AmIRODC() and cr!nCName corresponds to default NC then
1266             #     Let dsaobj be the nTDSDSA object of the dc
1267             #     IF  dsaobj.msDS-Behavior-Version < DS_DOMAIN_FUNCTION_2008
1268             #         Skip dc
1269             if self.my_dsa.is_ro() and rep is not None and rep.is_default():
1270                 if not dsa.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
1271                     continue
1272
1273             # IF BridgeheadDCFailed(dc!objectGUID, detectFailedDCs) = TRUE
1274             #     Skip dc
1275             if self.is_bridgehead_failed(dsa, detect_failed):
1276                 DEBUG("bridgehead is failed")
1277                 continue
1278
1279             DEBUG_FN("found a bridgehead: %s" % dsa.dsa_dnstr)
1280             bhs.append(dsa)
1281
1282         # IF bit NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED is set in
1283         # s!options
1284         #    SORT bhs such that all GC servers precede DCs that are not GC
1285         #    servers, and otherwise by ascending objectGUID
1286         # ELSE
1287         #    SORT bhs in a random order
1288         if site.is_random_bridgehead_disabled():
1289             bhs.sort(sort_dsa_by_gc_and_guid)
1290         else:
1291             random.shuffle(bhs)
1292         debug.DEBUG_YELLOW(bhs)
1293         return bhs
1294
1295     def is_bridgehead_failed(self, dsa, detect_failed):
1296         """Determine whether a given DC is known to be in a failed state
1297
1298         :param dsa: the bridgehead to test
1299         :param detect_failed: True to really check, False to assume no failure
1300         :return: True if and only if the DC should be considered failed
1301
1302         Here we DEPART from the pseudo code spec which appears to be
1303         wrong. It says, in full:
1304
1305     /***** BridgeheadDCFailed *****/
1306     /* Determine whether a given DC is known to be in a failed state.
1307      * IN: objectGUID - objectGUID of the DC's nTDSDSA object.
1308      * IN: detectFailedDCs - TRUE if and only failed DC detection is
1309      *     enabled.
1310      * RETURNS: TRUE if and only if the DC should be considered to be in a
1311      *          failed state.
1312      */
1313     BridgeheadDCFailed(IN GUID objectGUID, IN bool detectFailedDCs) : bool
1314     {
1315         IF bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set in
1316         the options attribute of the site settings object for the local
1317         DC's site
1318             RETURN FALSE
1319         ELSEIF a tuple z exists in the kCCFailedLinks or
1320         kCCFailedConnections variables such that z.UUIDDsa =
1321         objectGUID, z.FailureCount > 1, and the current time -
1322         z.TimeFirstFailure > 2 hours
1323             RETURN TRUE
1324         ELSE
1325             RETURN detectFailedDCs
1326         ENDIF
1327     }
1328
1329         where you will see detectFailedDCs is not behaving as
1330         advertised -- it is acting as a default return code in the
1331         event that a failure is not detected, not a switch turning
1332         detection on or off. Elsewhere the documentation seems to
1333         concur with the comment rather than the code.
1334         """
1335         if not detect_failed:
1336             return False
1337
1338         # NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED = 0x00000008
1339         # When DETECT_STALE_DISABLED, we can never know of if
1340         # it's in a failed state
1341         if self.my_site.site_options & 0x00000008:
1342             return False
1343
1344         return self.is_stale_link_connection(dsa)
1345
1346     def create_connection(self, part, rbh, rsite, transport,
1347                           lbh, lsite, link_opt, link_sched,
1348                           partial_ok, detect_failed):
1349         """Create an nTDSConnection object as specified if it doesn't exist.
1350
1351         Part of MS-ADTS 6.2.2.3.4.5
1352
1353         :param part: crossRef object for the NC to replicate.
1354         :param rbh: nTDSDSA object for DC to act as the
1355             IDL_DRSGetNCChanges server (which is in a site other
1356             than the local DC's site).
1357         :param rsite: site of the rbh
1358         :param transport: interSiteTransport object for the transport
1359             to use for replication traffic.
1360         :param lbh: nTDSDSA object for DC to act as the
1361             IDL_DRSGetNCChanges client (which is in the local DC's site).
1362         :param lsite: site of the lbh
1363         :param link_opt: Replication parameters (aggregated siteLink options,
1364                                                  etc.)
1365         :param link_sched: Schedule specifying the times at which
1366             to begin replicating.
1367         :partial_ok: True if bridgehead DCs containing partial
1368             replicas of the NC are acceptable.
1369         :param detect_failed: True to detect failed DCs and route
1370             replication traffic around them, FALSE to assume no DC
1371             has failed.
1372         """
1373         rbhs_all = self.get_all_bridgeheads(rsite, part, transport,
1374                                             partial_ok, False)
1375         rbh_table = dict((x.dsa_dnstr, x) for x in rbhs_all)
1376
1377         debug.DEBUG_GREY("rbhs_all: %s %s" % (len(rbhs_all),
1378                                               [x.dsa_dnstr for x in rbhs_all]))
1379
1380         # MS-TECH says to compute rbhs_avail but then doesn't use it
1381         # rbhs_avail = self.get_all_bridgeheads(rsite, part, transport,
1382         #                                        partial_ok, detect_failed)
1383
1384         lbhs_all = self.get_all_bridgeheads(lsite, part, transport,
1385                                             partial_ok, False)
1386         if lbh.is_ro():
1387             lbhs_all.append(lbh)
1388
1389         debug.DEBUG_GREY("lbhs_all: %s %s" % (len(lbhs_all),
1390                                               [x.dsa_dnstr for x in lbhs_all]))
1391
1392         # MS-TECH says to compute lbhs_avail but then doesn't use it
1393         # lbhs_avail = self.get_all_bridgeheads(lsite, part, transport,
1394         #                                       partial_ok, detect_failed)
1395
1396         # FOR each nTDSConnection object cn such that the parent of cn is
1397         # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1398         for ldsa in lbhs_all:
1399             for cn in ldsa.connect_table.values():
1400
1401                 rdsa = rbh_table.get(cn.from_dnstr)
1402                 if rdsa is None:
1403                     continue
1404
1405                 debug.DEBUG_DARK_YELLOW("rdsa is %s" % rdsa.dsa_dnstr)
1406                 # IF bit NTDSCONN_OPT_IS_GENERATED is set in cn!options and
1407                 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options and
1408                 # cn!transportType references t
1409                 if ((cn.is_generated() and
1410                      not cn.is_rodc_topology() and
1411                      cn.transport_guid == transport.guid)):
1412
1413                     # IF bit NTDSCONN_OPT_USER_OWNED_SCHEDULE is clear in
1414                     # cn!options and cn!schedule != sch
1415                     #     Perform an originating update to set cn!schedule to
1416                     #     sched
1417                     if ((not cn.is_user_owned_schedule() and
1418                          not cn.is_equivalent_schedule(link_sched))):
1419                         cn.schedule = link_sched
1420                         cn.set_modified(True)
1421
1422                     # IF bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1423                     # NTDSCONN_OPT_USE_NOTIFY are set in cn
1424                     if cn.is_override_notify_default() and \
1425                        cn.is_use_notify():
1426
1427                         # IF bit NTDSSITELINK_OPT_USE_NOTIFY is clear in
1428                         # ri.Options
1429                         #    Perform an originating update to clear bits
1430                         #    NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1431                         #    NTDSCONN_OPT_USE_NOTIFY in cn!options
1432                         if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) == 0:
1433                             cn.options &= \
1434                                 ~(dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1435                                   dsdb.NTDSCONN_OPT_USE_NOTIFY)
1436                             cn.set_modified(True)
1437
1438                     # ELSE
1439                     else:
1440
1441                         # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in
1442                         # ri.Options
1443                         #     Perform an originating update to set bits
1444                         #     NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1445                         #     NTDSCONN_OPT_USE_NOTIFY in cn!options
1446                         if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1447                             cn.options |= \
1448                                 (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1449                                  dsdb.NTDSCONN_OPT_USE_NOTIFY)
1450                             cn.set_modified(True)
1451
1452                     # IF bit NTDSCONN_OPT_TWOWAY_SYNC is set in cn!options
1453                     if cn.is_twoway_sync():
1454
1455                         # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is clear in
1456                         # ri.Options
1457                         #     Perform an originating update to clear bit
1458                         #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1459                         if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) == 0:
1460                             cn.options &= ~dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1461                             cn.set_modified(True)
1462
1463                     # ELSE
1464                     else:
1465
1466                         # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in
1467                         # ri.Options
1468                         #     Perform an originating update to set bit
1469                         #     NTDSCONN_OPT_TWOWAY_SYNC in cn!options
1470                         if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1471                             cn.options |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1472                             cn.set_modified(True)
1473
1474                     # IF bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION is set
1475                     # in cn!options
1476                     if cn.is_intersite_compression_disabled():
1477
1478                         # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is clear
1479                         # in ri.Options
1480                         #     Perform an originating update to clear bit
1481                         #     NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1482                         #     cn!options
1483                         if ((link_opt &
1484                              dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) == 0):
1485                             cn.options &= \
1486                                 ~dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1487                             cn.set_modified(True)
1488
1489                     # ELSE
1490                     else:
1491                         # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1492                         # ri.Options
1493                         #     Perform an originating update to set bit
1494                         #     NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in
1495                         #     cn!options
1496                         if ((link_opt &
1497                              dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1498                             cn.options |= \
1499                                 dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1500                             cn.set_modified(True)
1501
1502                     # Display any modified connection
1503                     if self.readonly:
1504                         if cn.to_be_modified:
1505                             logger.info("TO BE MODIFIED:\n%s" % cn)
1506
1507                         ldsa.commit_connections(self.samdb, ro=True)
1508                     else:
1509                         ldsa.commit_connections(self.samdb)
1510         # ENDFOR
1511
1512         valid_connections = 0
1513
1514         # FOR each nTDSConnection object cn such that cn!parent is
1515         # a DC in lbhsAll and cn!fromServer references a DC in rbhsAll
1516         for ldsa in lbhs_all:
1517             for cn in ldsa.connect_table.values():
1518
1519                 rdsa = rbh_table.get(cn.from_dnstr)
1520                 if rdsa is None:
1521                     continue
1522
1523                 debug.DEBUG_DARK_YELLOW("round 2: rdsa is %s" % rdsa.dsa_dnstr)
1524
1525                 # IF (bit NTDSCONN_OPT_IS_GENERATED is clear in cn!options or
1526                 # cn!transportType references t) and
1527                 # NTDSCONN_OPT_RODC_TOPOLOGY is clear in cn!options
1528                 if (((not cn.is_generated() or
1529                       cn.transport_guid == transport.guid) and
1530                      not cn.is_rodc_topology())):
1531
1532                     # LET rguid be the objectGUID of the nTDSDSA object
1533                     # referenced by cn!fromServer
1534                     # LET lguid be (cn!parent)!objectGUID
1535
1536                     # IF BridgeheadDCFailed(rguid, detectFailedDCs) = FALSE and
1537                     # BridgeheadDCFailed(lguid, detectFailedDCs) = FALSE
1538                     #     Increment cValidConnections by 1
1539                     if ((not self.is_bridgehead_failed(rdsa, detect_failed) and
1540                          not self.is_bridgehead_failed(ldsa, detect_failed))):
1541                         valid_connections += 1
1542
1543                     # IF keepConnections does not contain cn!objectGUID
1544                     #     APPEND cn!objectGUID to keepConnections
1545                     self.kept_connections.add(cn)
1546
1547         # ENDFOR
1548         debug.DEBUG_RED("valid connections %d" % valid_connections)
1549         DEBUG("kept_connections:\n%s" % (self.kept_connections,))
1550         # IF cValidConnections = 0
1551         if valid_connections == 0:
1552
1553             # LET opt be NTDSCONN_OPT_IS_GENERATED
1554             opt = dsdb.NTDSCONN_OPT_IS_GENERATED
1555
1556             # IF bit NTDSSITELINK_OPT_USE_NOTIFY is set in ri.Options
1557             #     SET bits NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT and
1558             #     NTDSCONN_OPT_USE_NOTIFY in opt
1559             if (link_opt & dsdb.NTDSSITELINK_OPT_USE_NOTIFY) != 0:
1560                 opt |= (dsdb.NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT |
1561                         dsdb.NTDSCONN_OPT_USE_NOTIFY)
1562
1563             # IF bit NTDSSITELINK_OPT_TWOWAY_SYNC is set in ri.Options
1564             #     SET bit NTDSCONN_OPT_TWOWAY_SYNC opt
1565             if (link_opt & dsdb.NTDSSITELINK_OPT_TWOWAY_SYNC) != 0:
1566                 opt |= dsdb.NTDSCONN_OPT_TWOWAY_SYNC
1567
1568             # IF bit NTDSSITELINK_OPT_DISABLE_COMPRESSION is set in
1569             # ri.Options
1570             #     SET bit NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION in opt
1571             if ((link_opt &
1572                  dsdb.NTDSSITELINK_OPT_DISABLE_COMPRESSION) != 0):
1573                 opt |= dsdb.NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
1574
1575             # Perform an originating update to create a new nTDSConnection
1576             # object cn that is a child of lbh, cn!enabledConnection = TRUE,
1577             # cn!options = opt, cn!transportType is a reference to t,
1578             # cn!fromServer is a reference to rbh, and cn!schedule = sch
1579             DEBUG_FN("new connection, KCC dsa: %s" % self.my_dsa.dsa_dnstr)
1580             system_flags = (dsdb.SYSTEM_FLAG_CONFIG_ALLOW_RENAME |
1581                             dsdb.SYSTEM_FLAG_CONFIG_ALLOW_MOVE)
1582
1583             cn = lbh.new_connection(opt, system_flags, transport,
1584                                     rbh.dsa_dnstr, link_sched)
1585
1586             # Display any added connection
1587             if self.readonly:
1588                 if cn.to_be_added:
1589                     logger.info("TO BE ADDED:\n%s" % cn)
1590
1591                     lbh.commit_connections(self.samdb, ro=True)
1592             else:
1593                 lbh.commit_connections(self.samdb)
1594
1595             # APPEND cn!objectGUID to keepConnections
1596             self.kept_connections.add(cn)
1597
1598     def add_transports(self, vertex, local_vertex, graph, detect_failed):
1599         """Build a Vertex's transport lists
1600
1601         Each vertex has accept_red_red and accept_black lists that
1602         list what transports they accept under various conditions. The
1603         only transport that is ever accepted is IP, and a dummy extra
1604         transport called "EDGE_TYPE_ALL".
1605
1606         Part of MS-ADTS 6.2.2.3.4.3 -- ColorVertices
1607
1608         :param vertex: the remote vertex we are thinking about
1609         :param local_vertex: the vertex relating to the local site.
1610         :param graph: the intersite graph
1611         :param detect_failed: whether to detect failed links
1612         :return: True if some bridgeheads were not found
1613         """
1614         # The docs ([MS-ADTS] 6.2.2.3.4.3) say to use local_vertex
1615         # here, but using vertex seems to make more sense. That is,
1616         # the docs want this:
1617         #
1618         #bh = self.get_bridgehead(local_vertex.site, vertex.part, transport,
1619         #                         local_vertex.is_black(), detect_failed)
1620         #
1621         # TODO WHY?????
1622
1623         vertex.accept_red_red = []
1624         vertex.accept_black = []
1625         found_failed = False
1626
1627         if vertex in graph.connected_vertices:
1628             t_guid = str(self.ip_transport.guid)
1629
1630             bh = self.get_bridgehead(vertex.site, vertex.part,
1631                                      self.ip_transport,
1632                                      vertex.is_black(), detect_failed)
1633             if bh is None:
1634                 if vertex.site.is_rodc_site():
1635                     vertex.accept_red_red.append(t_guid)
1636                 else:
1637                     found_failed = True
1638             else:
1639                 vertex.accept_red_red.append(t_guid)
1640                 vertex.accept_black.append(t_guid)
1641
1642         # Add additional transport to ensure another run of Dijkstra
1643         vertex.accept_red_red.append("EDGE_TYPE_ALL")
1644         vertex.accept_black.append("EDGE_TYPE_ALL")
1645
1646         return found_failed
1647
1648     def create_connections(self, graph, part, detect_failed):
1649         """Create intersite NTDSConnections as needed by a partition
1650
1651         Construct an NC replica graph for the NC identified by
1652         the given crossRef, then create any additional nTDSConnection
1653         objects required.
1654
1655         :param graph: site graph.
1656         :param part: crossRef object for NC.
1657         :param detect_failed:  True to detect failed DCs and route
1658             replication traffic around them, False to assume no DC
1659             has failed.
1660
1661         Modifies self.kept_connections by adding any connections
1662         deemed to be "in use".
1663
1664         :return: (all_connected, found_failed_dc)
1665         (all_connected) True if the resulting NC replica graph
1666             connects all sites that need to be connected.
1667         (found_failed_dc) True if one or more failed DCs were
1668             detected.
1669         """
1670         all_connected = True
1671         found_failed = False
1672
1673         DEBUG_FN("create_connections(): enter\n"
1674                  "\tpartdn=%s\n\tdetect_failed=%s" %
1675                  (part.nc_dnstr, detect_failed))
1676
1677         # XXX - This is a highly abbreviated function from the MS-TECH
1678         #       ref.  It creates connections between bridgeheads to all
1679         #       sites that have appropriate replicas.  Thus we are not
1680         #       creating a minimum cost spanning tree but instead
1681         #       producing a fully connected tree.  This should produce
1682         #       a full (albeit not optimal cost) replication topology.
1683
1684         my_vertex = Vertex(self.my_site, part)
1685         my_vertex.color_vertex()
1686
1687         for v in graph.vertices:
1688             v.color_vertex()
1689             if self.add_transports(v, my_vertex, graph, detect_failed):
1690                 found_failed = True
1691
1692         # No NC replicas for this NC in the site of the local DC,
1693         # so no nTDSConnection objects need be created
1694         if my_vertex.is_white():
1695             return all_connected, found_failed
1696
1697         edge_list, n_components = get_spanning_tree_edges(graph,
1698                                                           self.my_site,
1699                                                           label=part.partstr)
1700
1701         DEBUG_FN("%s Number of components: %d" %
1702                  (part.nc_dnstr, n_components))
1703         if n_components > 1:
1704             all_connected = False
1705
1706         # LET partialReplicaOkay be TRUE if and only if
1707         # localSiteVertex.Color = COLOR.BLACK
1708         partial_ok = my_vertex.is_black()
1709
1710         # Utilize the IP transport only for now
1711         transport = self.ip_transport
1712
1713         DEBUG("edge_list %s" % edge_list)
1714         for e in edge_list:
1715             # XXX more accurate comparison?
1716             if e.directed and e.vertices[0].site is self.my_site:
1717                 continue
1718
1719             if e.vertices[0].site is self.my_site:
1720                 rsite = e.vertices[1].site
1721             else:
1722                 rsite = e.vertices[0].site
1723
1724             # We don't make connections to our own site as that
1725             # is intrasite topology generator's job
1726             if rsite is self.my_site:
1727                 DEBUG("rsite is my_site")
1728                 continue
1729
1730             # Determine bridgehead server in remote site
1731             rbh = self.get_bridgehead(rsite, part, transport,
1732                                       partial_ok, detect_failed)
1733             if rbh is None:
1734                 continue
1735
1736             # RODC acts as an BH for itself
1737             # IF AmIRODC() then
1738             #     LET lbh be the nTDSDSA object of the local DC
1739             # ELSE
1740             #     LET lbh be the result of GetBridgeheadDC(localSiteVertex.ID,
1741             #     cr, t, partialReplicaOkay, detectFailedDCs)
1742             if self.my_dsa.is_ro():
1743                 lsite = self.my_site
1744                 lbh = self.my_dsa
1745             else:
1746                 lsite = self.my_site
1747                 lbh = self.get_bridgehead(lsite, part, transport,
1748                                           partial_ok, detect_failed)
1749             # TODO
1750             if lbh is None:
1751                 debug.DEBUG_RED("DISASTER! lbh is None")
1752                 return False, True
1753
1754             DEBUG_FN("lsite: %s\nrsite: %s" % (lsite, rsite))
1755             DEBUG_FN("vertices %s" % (e.vertices,))
1756             debug.DEBUG_BLUE("bridgeheads\n%s\n%s\n%s" % (lbh, rbh, "-" * 70))
1757
1758             sitelink = e.site_link
1759             if sitelink is None:
1760                 link_opt = 0x0
1761                 link_sched = None
1762             else:
1763                 link_opt = sitelink.options
1764                 link_sched = sitelink.schedule
1765
1766             self.create_connection(part, rbh, rsite, transport,
1767                                    lbh, lsite, link_opt, link_sched,
1768                                    partial_ok, detect_failed)
1769
1770         return all_connected, found_failed
1771
1772     def create_intersite_connections(self):
1773         """Create NTDSConnections as necessary for all partitions.
1774
1775         Computes an NC replica graph for each NC replica that "should be
1776         present" on the local DC or "is present" on any DC in the same site
1777         as the local DC. For each edge directed to an NC replica on such a
1778         DC from an NC replica on a DC in another site, the KCC creates an
1779         nTDSConnection object to imply that edge if one does not already
1780         exist.
1781
1782         Modifies self.kept_connections - A set of nTDSConnection
1783         objects for edges that are directed
1784         to the local DC's site in one or more NC replica graphs.
1785
1786         :return: True if spanning trees were created for all NC replica
1787                  graphs, otherwise False.
1788         """
1789         all_connected = True
1790         self.kept_connections = set()
1791
1792         # LET crossRefList be the set containing each object o of class
1793         # crossRef such that o is a child of the CN=Partitions child of the
1794         # config NC
1795
1796         # FOR each crossRef object cr in crossRefList
1797         #    IF cr!enabled has a value and is false, or if FLAG_CR_NTDS_NC
1798         #        is clear in cr!systemFlags, skip cr.
1799         #    LET g be the GRAPH return of SetupGraph()
1800
1801         for part in self.part_table.values():
1802
1803             if not part.is_enabled():
1804                 continue
1805
1806             if part.is_foreign():
1807                 continue
1808
1809             graph = self.setup_graph(part)
1810
1811             # Create nTDSConnection objects, routing replication traffic
1812             # around "failed" DCs.
1813             found_failed = False
1814
1815             connected, found_failed = self.create_connections(graph,
1816                                                               part, True)
1817
1818             DEBUG("with detect_failed: connected %s Found failed %s" %
1819                   (connected, found_failed))
1820             if not connected:
1821                 all_connected = False
1822
1823                 if found_failed:
1824                     # One or more failed DCs preclude use of the ideal NC
1825                     # replica graph. Add connections for the ideal graph.
1826                     self.create_connections(graph, part, False)
1827
1828         return all_connected
1829
1830     def intersite(self, ping):
1831         """Generate the inter-site KCC replica graph and nTDSConnections
1832
1833         As per MS-ADTS 6.2.2.3.
1834
1835         If self.readonly is False, the connections are added to self.samdb.
1836
1837         Produces self.kept_connections which is a set of NTDS
1838         Connections that should be kept during subsequent pruning
1839         process.
1840
1841         After this has run, all sites should be connected in a minimum
1842         spanning tree.
1843
1844         :param ping: An oracle function of remote site availability
1845         :return (True or False):  (True) if the produced NC replica
1846             graph connects all sites that need to be connected
1847         """
1848
1849         # Retrieve my DSA
1850         mydsa = self.my_dsa
1851         mysite = self.my_site
1852         all_connected = True
1853
1854         DEBUG_FN("intersite(): enter")
1855
1856         # Determine who is the ISTG
1857         if self.readonly:
1858             mysite.select_istg(self.samdb, mydsa, ro=True)
1859         else:
1860             mysite.select_istg(self.samdb, mydsa, ro=False)
1861
1862         # Test whether local site has topology disabled
1863         if mysite.is_intersite_topology_disabled():
1864             DEBUG_FN("intersite(): exit disabled all_connected=%d" %
1865                      all_connected)
1866             return all_connected
1867
1868         if not mydsa.is_istg():
1869             DEBUG_FN("intersite(): exit not istg all_connected=%d" %
1870                      all_connected)
1871             return all_connected
1872
1873         self.merge_failed_links(ping)
1874
1875         # For each NC with an NC replica that "should be present" on the
1876         # local DC or "is present" on any DC in the same site as the
1877         # local DC, the KCC constructs a site graph--a precursor to an NC
1878         # replica graph. The site connectivity for a site graph is defined
1879         # by objects of class interSiteTransport, siteLink, and
1880         # siteLinkBridge in the config NC.
1881
1882         all_connected = self.create_intersite_connections()
1883
1884         DEBUG_FN("intersite(): exit all_connected=%d" % all_connected)
1885         return all_connected
1886
1887     # This function currently does no actions. The reason being that we cannot
1888     # perform modifies in this way on the RODC.
1889     def update_rodc_connection(self, ro=True):
1890         """Updates the RODC NTFRS connection object.
1891
1892         If the local DSA is not an RODC, this does nothing.
1893         """
1894         if not self.my_dsa.is_ro():
1895             return
1896
1897         # Given an nTDSConnection object cn1, such that cn1.options contains
1898         # NTDSCONN_OPT_RODC_TOPOLOGY, and another nTDSConnection object cn2,
1899         # does not contain NTDSCONN_OPT_RODC_TOPOLOGY, modify cn1 to ensure
1900         # that the following is true:
1901         #
1902         #     cn1.fromServer = cn2.fromServer
1903         #     cn1.schedule = cn2.schedule
1904         #
1905         # If no such cn2 can be found, cn1 is not modified.
1906         # If no such cn1 can be found, nothing is modified by this task.
1907
1908         all_connections = self.my_dsa.connect_table.values()
1909         ro_connections = [x for x in all_connections if x.is_rodc_topology()]
1910         rw_connections = [x for x in all_connections
1911                           if x not in ro_connections]
1912
1913         # XXX here we are dealing with multiple RODC_TOPO connections,
1914         # if they exist. It is not clear whether the spec means that
1915         # or if it ever arises.
1916         if rw_connections and ro_connections:
1917             for con in ro_connections:
1918                 cn2 = rw_connections[0]
1919                 con.from_dnstr = cn2.from_dnstr
1920                 con.schedule = cn2.schedule
1921                 con.to_be_modified = True
1922
1923             self.my_dsa.commit_connections(self.samdb, ro=ro)
1924
1925     def intrasite_max_node_edges(self, node_count):
1926         """Find the maximum number of edges directed to an intrasite node
1927
1928         The KCC does not create more than 50 edges directed to a
1929         single DC. To optimize replication, we compute that each node
1930         should have n+2 total edges directed to it such that (n) is
1931         the smallest non-negative integer satisfying
1932         (node_count <= 2*(n*n) + 6*n + 7)
1933
1934         (If the number of edges is m (i.e. n + 2), that is the same as
1935         2 * m*m - 2 * m + 3). We think in terms of n because that is
1936         the number of extra connections over the double directed ring
1937         that exists by default.
1938
1939         edges  n   nodecount
1940           2    0    7
1941           3    1   15
1942           4    2   27
1943           5    3   43
1944                   ...
1945          50   48 4903
1946
1947         :param node_count: total number of nodes in the replica graph
1948
1949         The intention is that there should be no more than 3 hops
1950         between any two DSAs at a site. With up to 7 nodes the 2 edges
1951         of the ring are enough; any configuration of extra edges with
1952         8 nodes will be enough. It is less clear that the 3 hop
1953         guarantee holds at e.g. 15 nodes in degenerate cases, but
1954         those are quite unlikely given the extra edges are randomly
1955         arranged.
1956
1957         :param node_count: the number of nodes in the site
1958         "return: The desired maximum number of connections
1959         """
1960         n = 0
1961         while True:
1962             if node_count <= (2 * (n * n) + (6 * n) + 7):
1963                 break
1964             n = n + 1
1965         n = n + 2
1966         if n < 50:
1967             return n
1968         return 50
1969
1970     def construct_intrasite_graph(self, site_local, dc_local,
1971                                   nc_x, gc_only, detect_stale):
1972         """Create an intrasite graph using given parameters
1973
1974         This might be called a number of times per site with different
1975         parameters.
1976
1977         Based on [MS-ADTS] 6.2.2.2
1978
1979         :param site_local: site for which we are working
1980         :param dc_local: local DC that potentially needs a replica
1981         :param nc_x:  naming context (x) that we are testing if it
1982                     "should be present" on the local DC
1983         :param gc_only: Boolean - only consider global catalog servers
1984         :param detect_stale: Boolean - check whether links seems down
1985         :return: None
1986         """
1987         # We're using the MS notation names here to allow
1988         # correlation back to the published algorithm.
1989         #
1990         # nc_x     - naming context (x) that we are testing if it
1991         #            "should be present" on the local DC
1992         # f_of_x   - replica (f) found on a DC (s) for NC (x)
1993         # dc_s     - DC where f_of_x replica was found
1994         # dc_local - local DC that potentially needs a replica
1995         #            (f_of_x)
1996         # r_list   - replica list R
1997         # p_of_x   - replica (p) is partial and found on a DC (s)
1998         #            for NC (x)
1999         # l_of_x   - replica (l) is the local replica for NC (x)
2000         #            that should appear on the local DC
2001         # r_len = is length of replica list |R|
2002         #
2003         # If the DSA doesn't need a replica for this
2004         # partition (NC x) then continue
2005         needed, ro, partial = nc_x.should_be_present(dc_local)
2006
2007         debug.DEBUG_YELLOW("construct_intrasite_graph(): enter" +
2008                            "\n\tgc_only=%d" % gc_only +
2009                            "\n\tdetect_stale=%d" % detect_stale +
2010                            "\n\tneeded=%s" % needed +
2011                            "\n\tro=%s" % ro +
2012                            "\n\tpartial=%s" % partial +
2013                            "\n%s" % nc_x)
2014
2015         if not needed:
2016             debug.DEBUG_RED("%s lacks 'should be present' status, "
2017                             "aborting construct_intersite_graph!" %
2018                             nc_x.nc_dnstr)
2019             return
2020
2021         # Create a NCReplica that matches what the local replica
2022         # should say.  We'll use this below in our r_list
2023         l_of_x = NCReplica(dc_local.dsa_dnstr, dc_local.dsa_guid,
2024                            nc_x.nc_dnstr)
2025
2026         l_of_x.identify_by_basedn(self.samdb)
2027
2028         l_of_x.rep_partial = partial
2029         l_of_x.rep_ro = ro
2030
2031         # Add this replica that "should be present" to the
2032         # needed replica table for this DSA
2033         dc_local.add_needed_replica(l_of_x)
2034
2035         # Replica list
2036         #
2037         # Let R be a sequence containing each writable replica f of x
2038         # such that f "is present" on a DC s satisfying the following
2039         # criteria:
2040         #
2041         #  * s is a writable DC other than the local DC.
2042         #
2043         #  * s is in the same site as the local DC.
2044         #
2045         #  * If x is a read-only full replica and x is a domain NC,
2046         #    then the DC's functional level is at least
2047         #    DS_BEHAVIOR_WIN2008.
2048         #
2049         #  * Bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED is set
2050         #    in the options attribute of the site settings object for
2051         #    the local DC's site, or no tuple z exists in the
2052         #    kCCFailedLinks or kCCFailedConnections variables such
2053         #    that z.UUIDDsa is the objectGUID of the nTDSDSA object
2054         #    for s, z.FailureCount > 0, and the current time -
2055         #    z.TimeFirstFailure > 2 hours.
2056
2057         r_list = []
2058
2059         # We'll loop thru all the DSAs looking for
2060         # writeable NC replicas that match the naming
2061         # context dn for (nc_x)
2062         #
2063         for dc_s in self.my_site.dsa_table.values():
2064             # If this partition (nc_x) doesn't appear as a
2065             # replica (f_of_x) on (dc_s) then continue
2066             if not nc_x.nc_dnstr in dc_s.current_rep_table:
2067                 continue
2068
2069             # Pull out the NCReplica (f) of (x) with the dn
2070             # that matches NC (x) we are examining.
2071             f_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2072
2073             # Replica (f) of NC (x) must be writable
2074             if f_of_x.is_ro():
2075                 continue
2076
2077             # Replica (f) of NC (x) must satisfy the
2078             # "is present" criteria for DC (s) that
2079             # it was found on
2080             if not f_of_x.is_present():
2081                 continue
2082
2083             # DC (s) must be a writable DSA other than
2084             # my local DC.  In other words we'd only replicate
2085             # from other writable DC
2086             if dc_s.is_ro() or dc_s is dc_local:
2087                 continue
2088
2089             # Certain replica graphs are produced only
2090             # for global catalogs, so test against
2091             # method input parameter
2092             if gc_only and not dc_s.is_gc():
2093                 continue
2094
2095             # DC (s) must be in the same site as the local DC
2096             # as this is the intra-site algorithm. This is
2097             # handled by virtue of placing DSAs in per
2098             # site objects (see enclosing for() loop)
2099
2100             # If NC (x) is intended to be read-only full replica
2101             # for a domain NC on the target DC then the source
2102             # DC should have functional level at minimum WIN2008
2103             #
2104             # Effectively we're saying that in order to replicate
2105             # to a targeted RODC (which was introduced in Windows 2008)
2106             # then we have to replicate from a DC that is also minimally
2107             # at that level.
2108             #
2109             # You can also see this requirement in the MS special
2110             # considerations for RODC which state that to deploy
2111             # an RODC, at least one writable domain controller in
2112             # the domain must be running Windows Server 2008
2113             if ro and not partial and nc_x.nc_type == NCType.domain:
2114                 if not dc_s.is_minimum_behavior(dsdb.DS_DOMAIN_FUNCTION_2008):
2115                     continue
2116
2117             # If we haven't been told to turn off stale connection
2118             # detection and this dsa has a stale connection then
2119             # continue
2120             if detect_stale and self.is_stale_link_connection(dc_s):
2121                 continue
2122
2123             # Replica meets criteria.  Add it to table indexed
2124             # by the GUID of the DC that it appears on
2125             r_list.append(f_of_x)
2126
2127         # If a partial (not full) replica of NC (x) "should be present"
2128         # on the local DC, append to R each partial replica (p of x)
2129         # such that p "is present" on a DC satisfying the same
2130         # criteria defined above for full replica DCs.
2131         #
2132         # XXX This loop and the previous one differ only in whether
2133         # the replica is partial or not. here we only accept partial
2134         # (because we're partial); before we only accepted full. Order
2135         # doen't matter (the list is sorted a few lines down) so these
2136         # loops could easily be merged. Or this could be a helper
2137         # function.
2138
2139         if partial:
2140             # Now we loop thru all the DSAs looking for
2141             # partial NC replicas that match the naming
2142             # context dn for (NC x)
2143             for dc_s in self.my_site.dsa_table.values():
2144
2145                 # If this partition NC (x) doesn't appear as a
2146                 # replica (p) of NC (x) on the dsa DC (s) then
2147                 # continue
2148                 if not nc_x.nc_dnstr in dc_s.current_rep_table:
2149                     continue
2150
2151                 # Pull out the NCReplica with the dn that
2152                 # matches NC (x) we are examining.
2153                 p_of_x = dc_s.current_rep_table[nc_x.nc_dnstr]
2154
2155                 # Replica (p) of NC (x) must be partial
2156                 if not p_of_x.is_partial():
2157                     continue
2158
2159                 # Replica (p) of NC (x) must satisfy the
2160                 # "is present" criteria for DC (s) that
2161                 # it was found on
2162                 if not p_of_x.is_present():
2163                     continue
2164
2165                 # DC (s) must be a writable DSA other than
2166                 # my DSA.  In other words we'd only replicate
2167                 # from other writable DSA
2168                 if dc_s.is_ro() or dc_s is dc_local:
2169                     continue
2170
2171                 # Certain replica graphs are produced only
2172                 # for global catalogs, so test against
2173                 # method input parameter
2174                 if gc_only and not dc_s.is_gc():
2175                     continue
2176
2177                 # If we haven't been told to turn off stale connection
2178                 # detection and this dsa has a stale connection then
2179                 # continue
2180                 if detect_stale and self.is_stale_link_connection(dc_s):
2181                     continue
2182
2183                 # Replica meets criteria.  Add it to table indexed
2184                 # by the GUID of the DSA that it appears on
2185                 r_list.append(p_of_x)
2186
2187         # Append to R the NC replica that "should be present"
2188         # on the local DC
2189         r_list.append(l_of_x)
2190
2191         r_list.sort(sort_replica_by_dsa_guid)
2192         r_len = len(r_list)
2193
2194         max_node_edges = self.intrasite_max_node_edges(r_len)
2195
2196         # Add a node for each r_list element to the replica graph
2197         graph_list = []
2198         for rep in r_list:
2199             node = GraphNode(rep.rep_dsa_dnstr, max_node_edges)
2200             graph_list.append(node)
2201
2202         # For each r(i) from (0 <= i < |R|-1)
2203         i = 0
2204         while i < (r_len-1):
2205             # Add an edge from r(i) to r(i+1) if r(i) is a full
2206             # replica or r(i+1) is a partial replica
2207             if not r_list[i].is_partial() or r_list[i+1].is_partial():
2208                 graph_list[i+1].add_edge_from(r_list[i].rep_dsa_dnstr)
2209
2210             # Add an edge from r(i+1) to r(i) if r(i+1) is a full
2211             # replica or ri is a partial replica.
2212             if not r_list[i+1].is_partial() or r_list[i].is_partial():
2213                 graph_list[i].add_edge_from(r_list[i+1].rep_dsa_dnstr)
2214             i = i + 1
2215
2216         # Add an edge from r|R|-1 to r0 if r|R|-1 is a full replica
2217         # or r0 is a partial replica.
2218         if not r_list[r_len-1].is_partial() or r_list[0].is_partial():
2219             graph_list[0].add_edge_from(r_list[r_len-1].rep_dsa_dnstr)
2220
2221         # Add an edge from r0 to r|R|-1 if r0 is a full replica or
2222         # r|R|-1 is a partial replica.
2223         if not r_list[0].is_partial() or r_list[r_len-1].is_partial():
2224             graph_list[r_len-1].add_edge_from(r_list[0].rep_dsa_dnstr)
2225
2226         DEBUG("r_list is length %s" % len(r_list))
2227         DEBUG('\n'.join(str((x.rep_dsa_guid, x.rep_dsa_dnstr))
2228                         for x in r_list))
2229
2230         do_dot_files = self.dot_file_dir is not None and self.debug
2231         if self.verify or do_dot_files:
2232             dot_edges = []
2233             dot_vertices = set()
2234             for v1 in graph_list:
2235                 dot_vertices.add(v1.dsa_dnstr)
2236                 for v2 in v1.edge_from:
2237                     dot_edges.append((v2, v1.dsa_dnstr))
2238                     dot_vertices.add(v2)
2239
2240             verify_properties = ('connected',)
2241             verify_and_dot('intrasite_pre_ntdscon', dot_edges, dot_vertices,
2242                            label='%s__%s__%s' % (site_local.site_dnstr,
2243                                                  nctype_lut[nc_x.nc_type],
2244                                                  nc_x.nc_dnstr),
2245                            properties=verify_properties, debug=DEBUG,
2246                            verify=self.verify,
2247                            dot_file_dir=self.dot_file_dir,
2248                            directed=True)
2249
2250             rw_dot_vertices = set(x for x in dot_vertices
2251                                   if not self.get_dsa(x).is_ro())
2252             rw_dot_edges = [(a, b) for a, b in dot_edges if
2253                             a in rw_dot_vertices and b in rw_dot_vertices]
2254             rw_verify_properties = ('connected',
2255                                     'directed_double_ring_or_small')
2256             verify_and_dot('intrasite_rw_pre_ntdscon', rw_dot_edges,
2257                            rw_dot_vertices,
2258                            label='%s__%s__%s' % (site_local.site_dnstr,
2259                                                  nctype_lut[nc_x.nc_type],
2260                                                  nc_x.nc_dnstr),
2261                            properties=rw_verify_properties, debug=DEBUG,
2262                            verify=self.verify,
2263                            dot_file_dir=self.dot_file_dir,
2264                            directed=True)
2265
2266         # For each existing nTDSConnection object implying an edge
2267         # from rj of R to ri such that j != i, an edge from rj to ri
2268         # is not already in the graph, and the total edges directed
2269         # to ri is less than n+2, the KCC adds that edge to the graph.
2270         for vertex in graph_list:
2271             dsa = self.my_site.dsa_table[vertex.dsa_dnstr]
2272             for connect in dsa.connect_table.values():
2273                 remote = connect.from_dnstr
2274                 if remote in self.my_site.dsa_table:
2275                     vertex.add_edge_from(remote)
2276
2277         DEBUG('reps are:  %s' % '   '.join(x.rep_dsa_dnstr for x in r_list))
2278         DEBUG('dsas are:  %s' % '   '.join(x.dsa_dnstr for x in graph_list))
2279
2280         for tnode in graph_list:
2281             # To optimize replication latency in sites with many NC
2282             # replicas, the KCC adds new edges directed to ri to bring
2283             # the total edges to n+2, where the NC replica rk of R
2284             # from which the edge is directed is chosen at random such
2285             # that k != i and an edge from rk to ri is not already in
2286             # the graph.
2287             #
2288             # Note that the KCC tech ref does not give a number for
2289             # the definition of "sites with many NC replicas". At a
2290             # bare minimum to satisfy n+2 edges directed at a node we
2291             # have to have at least three replicas in |R| (i.e. if n
2292             # is zero then at least replicas from two other graph
2293             # nodes may direct edges to us).
2294             if r_len >= 3 and not tnode.has_sufficient_edges():
2295                 candidates = [x for x in graph_list if
2296                               (x is not tnode and
2297                                x.dsa_dnstr not in tnode.edge_from)]
2298
2299                 debug.DEBUG_BLUE("looking for random link for %s. r_len %d, "
2300                                  "graph len %d candidates %d"
2301                                  % (tnode.dsa_dnstr, r_len, len(graph_list),
2302                                     len(candidates)))
2303
2304                 DEBUG("candidates %s" % [x.dsa_dnstr for x in candidates])
2305
2306                 while candidates and not tnode.has_sufficient_edges():
2307                     other = random.choice(candidates)
2308                     DEBUG("trying to add candidate %s" % other.dsa_dnstr)
2309                     if not tnode.add_edge_from(other.dsa_dnstr):
2310                         debug.DEBUG_RED("could not add %s" % other.dsa_dnstr)
2311                     candidates.remove(other)
2312             else:
2313                 DEBUG_FN("not adding links to %s: nodes %s, links is %s/%s" %
2314                          (tnode.dsa_dnstr, r_len, len(tnode.edge_from),
2315                           tnode.max_edges))
2316
2317             # Print the graph node in debug mode
2318             DEBUG_FN("%s" % tnode)
2319
2320             # For each edge directed to the local DC, ensure a nTDSConnection
2321             # points to us that satisfies the KCC criteria
2322
2323             if tnode.dsa_dnstr == dc_local.dsa_dnstr:
2324                 tnode.add_connections_from_edges(dc_local, self.ip_transport)
2325
2326         if self.verify or do_dot_files:
2327             dot_edges = []
2328             dot_vertices = set()
2329             for v1 in graph_list:
2330                 dot_vertices.add(v1.dsa_dnstr)
2331                 for v2 in v1.edge_from:
2332                     dot_edges.append((v2, v1.dsa_dnstr))
2333                     dot_vertices.add(v2)
2334
2335             verify_properties = ('connected',)
2336             verify_and_dot('intrasite_post_ntdscon', dot_edges, dot_vertices,
2337                            label='%s__%s__%s' % (site_local.site_dnstr,
2338                                                  nctype_lut[nc_x.nc_type],
2339                                                  nc_x.nc_dnstr),
2340                            properties=verify_properties, debug=DEBUG,
2341                            verify=self.verify,
2342                            dot_file_dir=self.dot_file_dir,
2343                            directed=True)
2344
2345             rw_dot_vertices = set(x for x in dot_vertices
2346                                   if not self.get_dsa(x).is_ro())
2347             rw_dot_edges = [(a, b) for a, b in dot_edges if
2348                             a in rw_dot_vertices and b in rw_dot_vertices]
2349             rw_verify_properties = ('connected',
2350                                     'directed_double_ring_or_small')
2351             verify_and_dot('intrasite_rw_post_ntdscon', rw_dot_edges,
2352                            rw_dot_vertices,
2353                            label='%s__%s__%s' % (site_local.site_dnstr,
2354                                                  nctype_lut[nc_x.nc_type],
2355                                                  nc_x.nc_dnstr),
2356                            properties=rw_verify_properties, debug=DEBUG,
2357                            verify=self.verify,
2358                            dot_file_dir=self.dot_file_dir,
2359                            directed=True)
2360
2361     def intrasite(self):
2362         """Generate the intrasite KCC connections
2363
2364         As per MS-ADTS 6.2.2.2.
2365
2366         If self.readonly is False, the connections are added to self.samdb.
2367
2368         After this call, all DCs in each site with more than 3 DCs
2369         should be connected in a bidirectional ring. If a site has 2
2370         DCs, they will bidirectionally connected. Sites with many DCs
2371         may have arbitrary extra connections.
2372
2373         :return: None
2374         """
2375         mydsa = self.my_dsa
2376
2377         DEBUG_FN("intrasite(): enter")
2378
2379         # Test whether local site has topology disabled
2380         mysite = self.my_site
2381         if mysite.is_intrasite_topology_disabled():
2382             return
2383
2384         detect_stale = (not mysite.is_detect_stale_disabled())
2385         for connect in mydsa.connect_table.values():
2386             if connect.to_be_added:
2387                 debug.DEBUG_CYAN("TO BE ADDED:\n%s" % connect)
2388
2389         # Loop thru all the partitions, with gc_only False
2390         for partdn, part in self.part_table.items():
2391             self.construct_intrasite_graph(mysite, mydsa, part, False,
2392                                            detect_stale)
2393             for connect in mydsa.connect_table.values():
2394                 if connect.to_be_added:
2395                     debug.DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2396
2397         # If the DC is a GC server, the KCC constructs an additional NC
2398         # replica graph (and creates nTDSConnection objects) for the
2399         # config NC as above, except that only NC replicas that "are present"
2400         # on GC servers are added to R.
2401         for connect in mydsa.connect_table.values():
2402             if connect.to_be_added:
2403                 debug.DEBUG_YELLOW("TO BE ADDED:\n%s" % connect)
2404
2405         # Do it again, with gc_only True
2406         for partdn, part in self.part_table.items():
2407             if part.is_config():
2408                 self.construct_intrasite_graph(mysite, mydsa, part, True,
2409                                                detect_stale)
2410
2411         # The DC repeats the NC replica graph computation and nTDSConnection
2412         # creation for each of the NC replica graphs, this time assuming
2413         # that no DC has failed. It does so by re-executing the steps as
2414         # if the bit NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED were
2415         # set in the options attribute of the site settings object for
2416         # the local DC's site.  (ie. we set "detec_stale" flag to False)
2417         for connect in mydsa.connect_table.values():
2418             if connect.to_be_added:
2419                 debug.DEBUG_BLUE("TO BE ADDED:\n%s" % connect)
2420
2421         # Loop thru all the partitions.
2422         for partdn, part in self.part_table.items():
2423             self.construct_intrasite_graph(mysite, mydsa, part, False,
2424                                            False)  # don't detect stale
2425
2426         # If the DC is a GC server, the KCC constructs an additional NC
2427         # replica graph (and creates nTDSConnection objects) for the
2428         # config NC as above, except that only NC replicas that "are present"
2429         # on GC servers are added to R.
2430         for connect in mydsa.connect_table.values():
2431             if connect.to_be_added:
2432                 debug.DEBUG_RED("TO BE ADDED:\n%s" % connect)
2433
2434         for partdn, part in self.part_table.items():
2435             if part.is_config():
2436                 self.construct_intrasite_graph(mysite, mydsa, part, True,
2437                                                False)  # don't detect stale
2438
2439         self._commit_changes(mydsa)
2440
2441     def list_dsas(self):
2442         """Compile a comprehensive list of DSA DNs
2443
2444         These are all the DSAs on all the sites that KCC would be
2445         dealing with.
2446
2447         This method is not idempotent and may not work correctly in
2448         sequence with KCC.run().
2449
2450         :return: a list of DSA DN strings.
2451         """
2452         self.load_my_site()
2453         self.load_my_dsa()
2454
2455         self.load_all_sites()
2456         self.load_all_partitions()
2457         self.load_ip_transport()
2458         self.load_all_sitelinks()
2459         dsas = []
2460         for site in self.site_table.values():
2461             dsas.extend([dsa.dsa_dnstr.replace('CN=NTDS Settings,', '', 1)
2462                          for dsa in site.dsa_table.values()])
2463         return dsas
2464
2465     def load_samdb(self, dburl, lp, creds, force=False):
2466         """Load the database using an url, loadparm, and credentials
2467
2468         If force is False, the samdb won't be reloaded if it already
2469         exists.
2470
2471         :param dburl: a database url.
2472         :param lp: a loadparm object.
2473         :param creds: a Credentials object.
2474         :param force: a boolean indicating whether to overwrite.
2475
2476         """
2477         if force or self.samdb is None:
2478             try:
2479                 self.samdb = SamDB(url=dburl,
2480                                    session_info=system_session(),
2481                                    credentials=creds, lp=lp)
2482             except ldb.LdbError, (num, msg):
2483                 raise KCCError("Unable to open sam database %s : %s" %
2484                                (dburl, msg))
2485
2486     def plot_all_connections(self, basename, verify_properties=()):
2487         """Helper function to plot and verify NTDSConnections
2488
2489         :param basename: an identifying string to use in filenames and logs.
2490         :param verify_properties: properties to verify (default empty)
2491         """
2492         verify = verify_properties and self.verify
2493         if not verify and self.dot_file_dir is None:
2494             return
2495
2496         dot_edges = []
2497         dot_vertices = []
2498         edge_colours = []
2499         vertex_colours = []
2500
2501         for dsa in self.dsa_by_dnstr.values():
2502             dot_vertices.append(dsa.dsa_dnstr)
2503             if dsa.is_ro():
2504                 vertex_colours.append('#cc0000')
2505             else:
2506                 vertex_colours.append('#0000cc')
2507             for con in dsa.connect_table.values():
2508                 if con.is_rodc_topology():
2509                     edge_colours.append('red')
2510                 else:
2511                     edge_colours.append('blue')
2512                 dot_edges.append((con.from_dnstr, dsa.dsa_dnstr))
2513
2514         verify_and_dot(basename, dot_edges, vertices=dot_vertices,
2515                        label=self.my_dsa_dnstr,
2516                        properties=verify_properties, debug=DEBUG,
2517                        verify=verify, dot_file_dir=self.dot_file_dir,
2518                        directed=True, edge_colors=edge_colours,
2519                        vertex_colors=vertex_colours)
2520
2521     def run(self, dburl, lp, creds, forced_local_dsa=None,
2522             forget_local_links=False, forget_intersite_links=False,
2523             attempt_live_connections=False):
2524         """Perform a KCC run, possibly updating repsFrom topology
2525
2526         :param dburl: url of the database to work with.
2527         :param lp: a loadparm object.
2528         :param creds: a Credentials object.
2529         :param forced_local_dsa: pretend to be on the DSA with this dn_str
2530         :param forget_local_links: calculate as if no connections existed
2531                (boolean, default False)
2532         :param forget_intersite_links: calculate with only intrasite connection
2533                (boolean, default False)
2534         :param attempt_live_connections: attempt to connect to remote DSAs to
2535                determine link availability (boolean, default False)
2536         :return: 1 on error, 0 otherwise
2537         """
2538         if self.samdb is None:
2539             DEBUG_FN("samdb is None; let's load it from %s" % (dburl,))
2540             self.load_samdb(dburl, lp, creds, force=False)
2541
2542         if forced_local_dsa:
2543             self.samdb.set_ntds_settings_dn("CN=NTDS Settings,%s" %
2544                                             forced_local_dsa)
2545
2546         try:
2547             # Setup
2548             self.load_my_site()
2549             self.load_my_dsa()
2550
2551             self.load_all_sites()
2552             self.load_all_partitions()
2553             self.load_ip_transport()
2554             self.load_all_sitelinks()
2555
2556             if self.verify or self.dot_file_dir is not None:
2557                 guid_to_dnstr = {}
2558                 for site in self.site_table.values():
2559                     guid_to_dnstr.update((str(dsa.dsa_guid), dnstr)
2560                                          for dnstr, dsa
2561                                          in site.dsa_table.items())
2562
2563                 self.plot_all_connections('dsa_initial')
2564
2565                 dot_edges = []
2566                 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2567                 for dnstr, c_rep in current_reps.items():
2568                     DEBUG("c_rep %s" % c_rep)
2569                     dot_edges.append((self.my_dsa.dsa_dnstr, dnstr))
2570
2571                 verify_and_dot('dsa_repsFrom_initial', dot_edges,
2572                                directed=True, label=self.my_dsa_dnstr,
2573                                properties=(), debug=DEBUG, verify=self.verify,
2574                                dot_file_dir=self.dot_file_dir)
2575
2576                 dot_edges = []
2577                 for site in self.site_table.values():
2578                     for dsa in site.dsa_table.values():
2579                         current_reps, needed_reps = dsa.get_rep_tables()
2580                         for dn_str, rep in current_reps.items():
2581                             for reps_from in rep.rep_repsFrom:
2582                                 DEBUG("rep %s" % rep)
2583                                 dsa_guid = str(reps_from.source_dsa_obj_guid)
2584                                 dsa_dn = guid_to_dnstr[dsa_guid]
2585                                 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2586
2587                 verify_and_dot('dsa_repsFrom_initial_all', dot_edges,
2588                                directed=True, label=self.my_dsa_dnstr,
2589                                properties=(), debug=DEBUG, verify=self.verify,
2590                                dot_file_dir=self.dot_file_dir)
2591
2592                 dot_edges = []
2593                 for link in self.sitelink_table.values():
2594                     for a, b in itertools.combinations(link.site_list, 2):
2595                         dot_edges.append((str(a), str(b)))
2596                 properties = ('connected',)
2597                 verify_and_dot('dsa_sitelink_initial', dot_edges,
2598                                directed=False,
2599                                label=self.my_dsa_dnstr, properties=properties,
2600                                debug=DEBUG, verify=self.verify,
2601                                dot_file_dir=self.dot_file_dir)
2602
2603             if forget_local_links:
2604                 for dsa in self.my_site.dsa_table.values():
2605                     dsa.connect_table = dict((k, v) for k, v in
2606                                              dsa.connect_table.items()
2607                                              if v.is_rodc_topology() or
2608                                              (v.from_dnstr not in
2609                                               self.my_site.dsa_table))
2610                 self.plot_all_connections('dsa_forgotten_local')
2611
2612             if forget_intersite_links:
2613                 for site in self.site_table.values():
2614                     for dsa in site.dsa_table.values():
2615                         dsa.connect_table = dict((k, v) for k, v in
2616                                                  dsa.connect_table.items()
2617                                                  if site is self.my_site and
2618                                                  v.is_rodc_topology())
2619
2620                 self.plot_all_connections('dsa_forgotten_all')
2621
2622             if attempt_live_connections:
2623                 # Encapsulates lp and creds in a function that
2624                 # attempts connections to remote DSAs.
2625                 def ping(self, dnsname):
2626                     try:
2627                         drs_utils.drsuapi_connect(dnsname, self.lp, self.creds)
2628                     except drs_utils.drsException:
2629                         return False
2630                     return True
2631             else:
2632                 ping = None
2633             # These are the published steps (in order) for the
2634             # MS-TECH description of the KCC algorithm ([MS-ADTS] 6.2.2)
2635
2636             # Step 1
2637             self.refresh_failed_links_connections(ping)
2638
2639             # Step 2
2640             self.intrasite()
2641
2642             # Step 3
2643             all_connected = self.intersite(ping)
2644
2645             # Step 4
2646             self.remove_unneeded_ntdsconn(all_connected)
2647
2648             # Step 5
2649             self.translate_ntdsconn()
2650
2651             # Step 6
2652             self.remove_unneeded_failed_links_connections()
2653
2654             # Step 7
2655             self.update_rodc_connection()
2656
2657             if self.verify or self.dot_file_dir is not None:
2658                 self.plot_all_connections('dsa_final',
2659                                           ('connected',))
2660
2661                 debug.DEBUG_MAGENTA("there are %d dsa guids" %
2662                                     len(guid_to_dnstr))
2663
2664                 dot_edges = []
2665                 edge_colors = []
2666                 my_dnstr = self.my_dsa.dsa_dnstr
2667                 current_reps, needed_reps = self.my_dsa.get_rep_tables()
2668                 for dnstr, n_rep in needed_reps.items():
2669                     for reps_from in n_rep.rep_repsFrom:
2670                         guid_str = str(reps_from.source_dsa_obj_guid)
2671                         dot_edges.append((my_dnstr, guid_to_dnstr[guid_str]))
2672                         edge_colors.append('#' + str(n_rep.nc_guid)[:6])
2673
2674                 verify_and_dot('dsa_repsFrom_final', dot_edges, directed=True,
2675                                label=self.my_dsa_dnstr,
2676                                properties=(), debug=DEBUG, verify=self.verify,
2677                                dot_file_dir=self.dot_file_dir,
2678                                edge_colors=edge_colors)
2679
2680                 dot_edges = []
2681
2682                 for site in self.site_table.values():
2683                     for dsa in site.dsa_table.values():
2684                         current_reps, needed_reps = dsa.get_rep_tables()
2685                         for n_rep in needed_reps.values():
2686                             for reps_from in n_rep.rep_repsFrom:
2687                                 dsa_guid = str(reps_from.source_dsa_obj_guid)
2688                                 dsa_dn = guid_to_dnstr[dsa_guid]
2689                                 dot_edges.append((dsa.dsa_dnstr, dsa_dn))
2690
2691                 verify_and_dot('dsa_repsFrom_final_all', dot_edges,
2692                                directed=True, label=self.my_dsa_dnstr,
2693                                properties=(), debug=DEBUG, verify=self.verify,
2694                                dot_file_dir=self.dot_file_dir)
2695
2696         except:
2697             raise
2698
2699         return 0
2700
2701     def import_ldif(self, dburl, lp, ldif_file, forced_local_dsa=None):
2702         """Import relevant objects and attributes from an LDIF file.
2703
2704         The point of this function is to allow a programmer/debugger to
2705         import an LDIF file with non-security relevent information that
2706         was previously extracted from a DC database.  The LDIF file is used
2707         to create a temporary abbreviated database.  The KCC algorithm can
2708         then run against this abbreviated database for debug or test
2709         verification that the topology generated is computationally the
2710         same between different OSes and algorithms.
2711
2712         :param dburl: path to the temporary abbreviated db to create
2713         :param lp: a loadparm object.
2714         :param ldif_file: path to the ldif file to import
2715         :param forced_local_dsa: perform KCC from this DSA's point of view
2716         :return: zero on success, 1 on error
2717         """
2718         try:
2719             self.samdb = ldif_import_export.ldif_to_samdb(dburl, lp, ldif_file,
2720                                                           forced_local_dsa)
2721         except ldif_import_export.LdifError, e:
2722             logger.critical(e)
2723             return 1
2724         return 0
2725
2726     def export_ldif(self, dburl, lp, creds, ldif_file):
2727         """Save KCC relevant details to an ldif file
2728
2729         The point of this function is to allow a programmer/debugger to
2730         extract an LDIF file with non-security relevent information from
2731         a DC database.  The LDIF file can then be used to "import" via
2732         the import_ldif() function this file into a temporary abbreviated
2733         database.  The KCC algorithm can then run against this abbreviated
2734         database for debug or test verification that the topology generated
2735         is computationally the same between different OSes and algorithms.
2736
2737         :param dburl: LDAP database URL to extract info from
2738         :param lp: a loadparm object.
2739         :param cred: a Credentials object.
2740         :param ldif_file: output LDIF file name to create
2741         :return: zero on success, 1 on error
2742         """
2743         try:
2744             ldif_import_export.samdb_to_ldif_file(self.samdb, dburl, lp, creds,
2745                                                   ldif_file)
2746         except ldif_import_export.LdifError, e:
2747             logger.critical(e)
2748             return 1
2749         return 0