?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Revert "s4:prefer "samdb_*_dn" basedn calls over the "ldb_get_*_dn" functions"
[Samba/gebeck_regimport.git] / source4 / dsdb / kcc / kcc_topology.c
blob72eb5e1137b4050be06e89ad8db272a1215e42f1
1 /*
2 Unix SMB/CIFS implementation.
3
4 KCC service
5
6 Copyright (C) Crístian Deives 2010
7
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>.
20
21 */
22
23 #include "includes.h"
24 #include "dsdb/samdb/samdb.h"
25 #include "lib/messaging/irpc.h"
26 #include "librpc/gen_ndr/ndr_misc.h"
27
28 #define FLAG_CR_NTDS_NC 0x00000001
29 #define FLAG_CR_NTDS_DOMAIN 0x00000002
30
31 #define NTDSCONN_OPT_IS_GENERATED 0x00000001
32 #define NTDSCONN_OPT_TWOWAY_SYNC 0x00000002
33 #define NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT 0x00000004
34 #define NTDSCONN_OPT_USE_NOTIFY 0x00000008
35 #define NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION 0x00000010
36 #define NTDSCONN_OPT_USER_OWNED_SCHEDULE 0x00000020
37 #define NTDSCONN_OPT_RODC_TOPOLOGY 0x00000040
38
39 #define NTDSDSA_OPT_IS_GC 0x00000001
40
41 #define NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED 0x00000008
42 #define NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED 0x00000100
43 #define NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED 0x00001000
44
45 #define NTDSSITELINK_OPT_USE_NOTIFY 0x00000001
46 #define NTDSSITELINK_OPT_TWOWAY_SYNC 0x00000002
47 #define NTDSSITELINK_OPT_DISABLE_COMPRESSION 0x00000004
48
49 #define NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
50
51 #define DS_BEHAVIOR_WIN2008 3
52
53 /** replication parameters of a graph edge */
54 struct kcctpl_repl_info {
55 uint32_t cost;
56 uint32_t interval;
57 uint32_t options;
58 uint8_t schedule[84];
59 };
60
61 /** color of a vertex */
62 enum kcctpl_color { RED, BLACK, WHITE };
63
64 /** a GUID array list */
65 struct GUID_list {
66 struct GUID *data;
67 uint32_t count;
68 };
69
70 /** a vertex in the site graph */
71 struct kcctpl_vertex {
72 struct GUID id;
73 struct GUID_list edge_ids;
74 enum kcctpl_color color;
75 struct GUID_list accept_red_red;
76 struct GUID_list accept_black;
77 struct kcctpl_repl_info repl_info;
78 uint32_t dist_to_red;
79
80 /* Dijkstra data */
81 struct GUID root_id;
82 bool demoted;
83
84 /* Kruskal data */
85 struct GUID component_id;
86 uint32_t component_index;
87 };
88
89 /** fully connected subgraph of vertices */
90 struct kcctpl_multi_edge {
91 struct GUID id;
92 struct GUID_list vertex_ids;
93 struct GUID type;
94 struct kcctpl_repl_info repl_info;
95 bool directed;
96 };
97
98 /** set of transitively connected kcc_multi_edge's. all edges within the set
99 * have the same type. */
100 struct kcctpl_multi_edge_set {
101 struct GUID id;
102 struct GUID_list edge_ids;
103 };
104
105 /** a vertices array list */
106 struct kcctpl_vertex_list {
107 struct kcctpl_vertex *data;
108 uint32_t count;
109 };
110
111 /** an edges array list */
112 struct kcctpl_multi_edge_list {
113 struct kcctpl_multi_edge *data;
114 uint32_t count;
115 };
116
117 /** an edge sets array list */
118 struct kcctpl_multi_edge_set_list {
119 struct kcctpl_multi_edge_set *data;
120 uint32_t count;
121 };
122
123 /** a site graph */
124 struct kcctpl_graph {
125 struct kcctpl_vertex_list vertices;
126 struct kcctpl_multi_edge_list edges;
127 struct kcctpl_multi_edge_set_list edge_sets;
128 };
129
130 /** path found in the graph between two non-white vertices */
131 struct kcctpl_internal_edge {
132 struct GUID v1id;
133 struct GUID v2id;
134 bool red_red;
135 struct kcctpl_repl_info repl_info;
136 struct GUID type;
137 };
138
139 /** an internal edges array list */
140 struct kcctpl_internal_edge_list {
141 struct kcctpl_internal_edge *data;
142 uint32_t count;
143 };
144
145 /** an LDB messages array list */
146 struct message_list {
147 struct ldb_message *data;
148 uint32_t count;
149 };
150
151 /**
152 * sort internal edges based on:
153 * - descending red_red,
154 * - ascending repl_info.cost,
155 * - descending available time in repl_info.schedule,
156 * - ascending v1id,
157 * - ascending v2id,
158 * - ascending type.
159 *
160 * this function is used in 'kcctpl_kruskal'.
161 */
162 static int kcctpl_sort_internal_edges(const void *internal_edge1,
163 const void *internal_edge2)
164 {
165 const struct kcctpl_internal_edge *ie1, *ie2;
166 int cmp_red_red;
167
168 ie1 = (const struct kcctpl_internal_edge *) internal_edge1;
169 ie2 = (const struct kcctpl_internal_edge *) internal_edge2;
170
171 cmp_red_red = ie2->red_red - ie1->red_red;
172 if (cmp_red_red == 0) {
173 int cmp_cost = ie1->repl_info.cost - ie2->repl_info.cost;
174
175 if (cmp_cost == 0) {
176 uint32_t available1, available2, i;
177 int cmp_schedule;
178
179 available1 = available2 = 0;
180 for (i = 0; i < 84; i++) {
181 if (ie1->repl_info.schedule[i] == 0) {
182 available1++;
183 }
184
185 if (ie2->repl_info.schedule[i] == 0) {
186 available2++;
187 }
188 }
189 cmp_schedule = available2 - available1;
190
191 if (cmp_schedule == 0) {
192 int cmp_v1id = GUID_compare(&ie1->v1id,
193 &ie2->v1id);
194
195 if (cmp_v1id == 0) {
196 int cmp_v2id = GUID_compare(&ie1->v2id,
197 &ie2->v2id);
198
199 if (cmp_v2id == 0) {
200 return GUID_compare(&ie1->type,
201 &ie2->type);
202 } else {
203 return cmp_v2id;
204 }
205 } else {
206 return cmp_v1id;
207 }
208 } else {
209 return cmp_schedule;
210 }
211 } else {
212 return cmp_cost;
213 }
214 } else {
215 return cmp_red_red;
216 }
217 }
218
219 /**
220 * sort vertices based on the following criteria:
221 * - ascending color (RED < BLACK),
222 * - ascending repl_info.cost,
223 * - ascending id.
224 *
225 * this function is used in 'kcctpl_process_edge'.
226 */
227 static int kcctpl_sort_vertices(const void *vertex1, const void *vertex2)
228 {
229 const struct kcctpl_vertex *v1, *v2;
230 int cmp_color;
231
232 v1 = (const struct kcctpl_vertex *) vertex1;
233 v2 = (const struct kcctpl_vertex *) vertex2;
234
235 cmp_color = v1->color - v2->color;
236 if (cmp_color == 0) {
237 int cmp_cost = v1->repl_info.cost - v2->repl_info.cost;
238 if (cmp_cost == 0) {
239 return GUID_compare(&v1->id, &v2->id);
240 } else {
241 return cmp_cost;
242 }
243 } else {
244 return cmp_color;
245 }
246 }
247
248 /**
249 * sort bridgehead elements (nTDSDSA) based on the following criteria:
250 * - GC servers precede non-GC servers
251 * - ascending objectGUID
252 *
253 * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
254 */
255 static int kcctpl_sort_bridgeheads(const void *bridgehead1,
256 const void *bridgehead2)
257 {
258 const struct ldb_message *bh1, *bh2;
259 uint64_t bh1_opts, bh2_opts, cmp_gc;
260
261 bh1 = (const struct ldb_message *) bridgehead1;
262 bh2 = (const struct ldb_message *) bridgehead2;
263
264 bh1_opts = samdb_result_int64(bh1, "options", 0);
265 bh2_opts = samdb_result_int64(bh2, "options", 0);
266
267 cmp_gc = (bh1_opts & NTDSDSA_OPT_IS_GC) -
268 (bh2_opts & NTDSDSA_OPT_IS_GC);
269
270 if (cmp_gc == 0) {
271 struct GUID bh1_id, bh2_id;
272
273 bh1_id = samdb_result_guid(bh1, "objectGUID");
274 bh2_id = samdb_result_guid(bh2, "objectGUID");
275
276 return GUID_compare(&bh1_id, &bh2_id);
277 } else {
278 return cmp_gc;
279 }
280 }
281
282 /**
283 * sort bridgehead elements (nTDSDSA) in a random order.
284 *
285 * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
286 */
287 static void kcctpl_shuffle_bridgeheads(struct message_list bridgeheads)
288 {
289 uint32_t i;
290
291 srandom(time(NULL));
292
293 for (i = bridgeheads.count; i > 1; i--) {
294 uint32_t r;
295 struct ldb_message tmp;
296
297 r = random() % i;
298
299 tmp = bridgeheads.data[i - 1];
300 bridgeheads.data[i - 1] = bridgeheads.data[r];
301 bridgeheads.data[r] = tmp;
302 }
303 }
304
305 /**
306 * find a graph vertex based on its GUID.
307 */
308 static struct kcctpl_vertex *kcctpl_find_vertex_by_guid(struct kcctpl_graph *graph,
309 struct GUID guid)
310 {
311 uint32_t i;
312
313 for (i = 0; i < graph->vertices.count; i++) {
314 if (GUID_equal(&graph->vertices.data[i].id, &guid)) {
315 return &graph->vertices.data[i];
316 }
317 }
318
319 return NULL;
320 }
321
322 /**
323 * find a graph edge based on its GUID.
324 */
325 static struct kcctpl_multi_edge *kcctpl_find_edge_by_guid(struct kcctpl_graph *graph,
326 struct GUID guid)
327 {
328 uint32_t i;
329
330 for (i = 0; i < graph->edges.count; i++) {
331 if (GUID_equal(&graph->edges.data[i].id, &guid)) {
332 return &graph->edges.data[i];
333 }
334 }
335
336 return NULL;
337 }
338
339 /**
340 * find a graph edge that contains a vertex with the specified GUID. the first
341 * occurrence will be returned.
342 */
343 static struct kcctpl_multi_edge *kcctpl_find_edge_by_vertex_guid(struct kcctpl_graph *graph,
344 struct GUID guid)
345 {
346 uint32_t i;
347
348 for (i = 0; i < graph->edges.count; i++) {
349 struct kcctpl_multi_edge *edge;
350 uint32_t j;
351
352 edge = &graph->edges.data[i];
353
354 for (j = 0; j < edge->vertex_ids.count; j++) {
355 struct GUID vertex_guid = edge->vertex_ids.data[j];
356
357 struct GUID *p = &guid;
358
359 if (GUID_equal(&vertex_guid, p)) {
360 return edge;
361 }
362 }
363 }
364
365 return NULL;
366 }
367
368 /**
369 * search for an occurrence of a GUID inside a list of GUIDs.
370 */
371 static bool kcctpl_guid_list_contains(struct GUID_list list, struct GUID guid)
372 {
373 uint32_t i;
374
375 for (i = 0; i < list.count; i++) {
376 if (GUID_equal(&list.data[i], &guid)) {
377 return true;
378 }
379 }
380
381 return false;
382 }
383
384 /**
385 * search for an occurrence of an ldb_message inside a list of ldb_messages,
386 * based on the ldb_message's DN.
387 */
388 static bool kcctpl_message_list_contains_dn(struct message_list list,
389 struct ldb_dn *dn)
390 {
391 uint32_t i;
392
393 for (i = 0; i < list.count; i++) {
394 struct ldb_message *message = &list.data[i];
395
396 if (ldb_dn_compare(message->dn, dn) == 0) {
397 return true;
398 }
399 }
400
401 return false;
402 }
403
404 /**
405 * get the Transports DN
406 * (CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=<domain>).
407 */
408 static struct ldb_dn *kcctpl_transports_dn(struct ldb_context *ldb,
409 TALLOC_CTX *mem_ctx)
410 {
411 struct ldb_dn *sites_dn;
412 bool ok;
413
414 sites_dn = samdb_sites_dn(ldb, mem_ctx);
415 if (!sites_dn) {
416 return NULL;
417 }
418
419 ok = ldb_dn_add_child_fmt(sites_dn, "CN=Inter-Site Transports");
420 if (!ok) {
421 talloc_free(sites_dn);
422 return NULL;
423 }
424
425 return sites_dn;
426 }
427 /**
428 * get the domain local site object.
429 */
430 static struct ldb_message *kcctpl_local_site(struct ldb_context *ldb,
431 TALLOC_CTX *mem_ctx)
432 {
433 int ret;
434 TALLOC_CTX *tmp_ctx;
435 struct ldb_dn *sites_dn;
436 struct ldb_result *res;
437 const char * const attrs[] = { "objectGUID", "options", NULL };
438
439 tmp_ctx = talloc_new(ldb);
440
441 sites_dn = samdb_sites_dn(ldb, tmp_ctx);
442 if (!sites_dn) {
443 talloc_free(tmp_ctx);
444 return NULL;
445 }
446
447 ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE, attrs,
448 "objectClass=site");
449
450 if (ret != LDB_SUCCESS || res->count == 0) {
451 talloc_free(tmp_ctx);
452 return NULL;
453 }
454
455 talloc_steal(mem_ctx, res);
456 talloc_free(tmp_ctx);
457 return res->msgs[0];
458 }
459
460 /*
461 * compare two internal edges for equality. every field of the structure will be
462 * compared.
463 */
464 static bool kcctpl_internal_edge_equal(struct kcctpl_internal_edge *edge1,
465 struct kcctpl_internal_edge *edge2)
466 {
467 if (!edge1 || !edge2) {
468 return false;
469 }
470
471 if (!GUID_equal(&edge1->v1id, &edge2->v1id)) {
472 return false;
473 }
474
475 if (!GUID_equal(&edge1->v2id, &edge2->v2id)) {
476 return false;
477 }
478
479 if (edge1->red_red != edge2->red_red) {
480 return false;
481 }
482
483 if (edge1->repl_info.cost != edge2->repl_info.cost ||
484 edge1->repl_info.interval != edge2->repl_info.interval ||
485 edge1->repl_info.options != edge2->repl_info.options ||
486 memcmp(&edge1->repl_info.schedule,
487 &edge2->repl_info.schedule, 84) != 0) {
488 return false;
489 }
490
491 if (!GUID_equal(&edge1->type, &edge2->type)) {
492 return false;
493 }
494
495 return true;
496 }
497
498 /**
499 * create a kcctpl_graph instance.
500 */
501 static NTSTATUS kcctpl_create_graph(TALLOC_CTX *mem_ctx,
502 struct GUID_list guids,
503 struct kcctpl_graph **_graph)
504 {
505 struct kcctpl_graph *graph;
506 uint32_t i;
507
508 graph = talloc_zero(mem_ctx, struct kcctpl_graph);
509 NT_STATUS_HAVE_NO_MEMORY(graph);
510
511 graph->vertices.count = guids.count;
512 graph->vertices.data = talloc_zero_array(graph, struct kcctpl_vertex,
513 guids.count);
514 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(graph->vertices.data, graph);
515
516 TYPESAFE_QSORT(guids.data, guids.count, GUID_compare);
517
518 for (i = 0; i < guids.count; i++) {
519 graph->vertices.data[i].id = guids.data[i];
520 }
521
522 *_graph = graph;
523 return NT_STATUS_OK;
524 }
525
526 /**
527 * create a kcctpl_multi_edge instance.
528 */
529 static NTSTATUS kcctpl_create_edge(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
530 struct GUID type,
531 struct ldb_message *site_link,
532 struct kcctpl_multi_edge **_edge)
533 {
534 struct kcctpl_multi_edge *edge;
535 TALLOC_CTX *tmp_ctx;
536 struct ldb_dn *sites_dn;
537 struct ldb_result *res;
538 const char * const attrs[] = { "siteList", NULL };
539 int ret;
540 struct ldb_message_element *el;
541 unsigned int i;
542 struct ldb_val val;
543
544 tmp_ctx = talloc_new(mem_ctx);
545 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
546
547 edge = talloc_zero(tmp_ctx, struct kcctpl_multi_edge);
548 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge, tmp_ctx);
549
550 edge->id = samdb_result_guid(site_link, "objectGUID");
551
552 sites_dn = samdb_sites_dn(ldb, tmp_ctx);
553 if (!sites_dn) {
554 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
555
556 talloc_free(tmp_ctx);
557 return NT_STATUS_INTERNAL_DB_CORRUPTION;
558 }
559
560 ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE, attrs,
561 "objectGUID=%s", GUID_string(tmp_ctx, &edge->id));
562 if (ret != LDB_SUCCESS) {
563 DEBUG(1, (__location__ ": failed to find siteLink object %s: "
564 "%s\n", GUID_string(tmp_ctx, &edge->id),
565 ldb_strerror(ret)));
566
567 talloc_free(tmp_ctx);
568 return NT_STATUS_INTERNAL_DB_CORRUPTION;
569 }
570 if (res->count == 0) {
571 DEBUG(1, (__location__ ": failed to find siteLink object %s\n",
572 GUID_string(tmp_ctx, &edge->id)));
573
574 talloc_free(tmp_ctx);
575 return NT_STATUS_INTERNAL_DB_CORRUPTION;
576 }
577
578 el = ldb_msg_find_element(res->msgs[0], "siteList");
579 if (!el) {
580 DEBUG(1, (__location__ ": failed to find siteList attribute of "
581 "object %s\n",
582 ldb_dn_get_linearized(res->msgs[0]->dn)));
583
584 talloc_free(tmp_ctx);
585 return NT_STATUS_INTERNAL_DB_CORRUPTION;
586 }
587
588 edge->vertex_ids.data = talloc_array(edge, struct GUID, el->num_values);
589 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge->vertex_ids.data, tmp_ctx);
590 edge->vertex_ids.count = el->num_values;
591
592 for (i = 0; i < el->num_values; i++) {
593 struct ldb_dn *dn;
594 struct GUID guid;
595
596 val = el->values[i];
597 dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
598 if (!dn) {
599 DEBUG(1, (__location__ ": failed to read a DN from "
600 "siteList attribute of %s\n",
601 ldb_dn_get_linearized(res->msgs[0]->dn)));
602
603 talloc_free(tmp_ctx);
604 return NT_STATUS_INTERNAL_DB_CORRUPTION;
605 }
606 ret = dsdb_find_guid_by_dn(ldb, dn, &guid);
607 if (ret != LDB_SUCCESS) {
608 DEBUG(1, (__location__ ": failed to find objectGUID "
609 "for object %s: %s\n",
610 ldb_dn_get_linearized(dn),
611 ldb_strerror(ret)));
612
613 talloc_free(tmp_ctx);
614 return NT_STATUS_INTERNAL_DB_CORRUPTION;
615 }
616
617 edge->vertex_ids.data[i] = guid;
618 }
619
620 edge->repl_info.cost = samdb_result_int64(site_link, "cost", 0);
621 edge->repl_info.options = samdb_result_int64(site_link, "options", 0);
622 edge->repl_info.interval = samdb_result_int64(site_link,
623 "replInterval", 0);
624 /* TODO: edge->repl_info.schedule = site_link!schedule */
625 edge->type = type;
626 edge->directed = false;
627
628 *_edge = talloc_steal(mem_ctx, edge);
629 talloc_free(tmp_ctx);
630 return NT_STATUS_OK;
631 }
632
633 /**
634 * create a kcctpl_multi_edge_set instance containing edges for all siteLink
635 * objects.
636 */
637 static NTSTATUS kcctpl_create_auto_edge_set(struct kcctpl_graph *graph,
638 struct GUID type,
639 struct ldb_result *res_site_link,
640 struct kcctpl_multi_edge_set **_set)
641 {
642 struct kcctpl_multi_edge_set *set;
643 TALLOC_CTX *tmp_ctx;
644 uint32_t i;
645
646 tmp_ctx = talloc_new(graph);
647 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
648
649 set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
650 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set, tmp_ctx);
651
652 for (i = 0; i < res_site_link->count; i++) {
653 struct GUID site_link_guid;
654 struct kcctpl_multi_edge *edge;
655
656 site_link_guid = samdb_result_guid(res_site_link->msgs[i],
657 "objectGUID");
658 edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
659 if (!edge) {
660 DEBUG(1, (__location__ ": failed to find a graph edge "
661 "with ID=%s\n",
662 GUID_string(tmp_ctx, &site_link_guid)));
663
664 talloc_free(tmp_ctx);
665 return NT_STATUS_INTERNAL_DB_CORRUPTION;
666 }
667
668 if (GUID_equal(&edge->type, &type)) {
669 struct GUID *new_data;
670
671 new_data = talloc_realloc(set, set->edge_ids.data,
672 struct GUID,
673 set->edge_ids.count + 1);
674 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
675 new_data[set->edge_ids.count] = site_link_guid;
676 set->edge_ids.data = new_data;
677 set->edge_ids.count++;
678 }
679 }
680
681 *_set = talloc_steal(graph, set);
682 return NT_STATUS_OK;
683 }
684
685 /**
686 * create a kcctpl_multi_edge_set instance.
687 */
688 static NTSTATUS kcctpl_create_edge_set(struct ldb_context *ldb,
689 struct kcctpl_graph *graph,
690 struct GUID type,
691 struct ldb_message *bridge,
692 struct kcctpl_multi_edge_set **_set)
693 {
694 struct kcctpl_multi_edge_set *set;
695 TALLOC_CTX *tmp_ctx;
696 struct ldb_message_element *el;
697 unsigned int i;
698
699 tmp_ctx = talloc_new(ldb);
700 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
701
702 set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
703 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set, tmp_ctx);
704
705 set->id = samdb_result_guid(bridge, "objectGUID");
706
707 el = ldb_msg_find_element(bridge, "siteLinkList");
708 if (!el) {
709 DEBUG(1, (__location__ ": failed to find siteLinkList "
710 "attribute of object %s\n",
711 ldb_dn_get_linearized(bridge->dn)));
712
713 talloc_free(tmp_ctx);
714 return NT_STATUS_INTERNAL_DB_CORRUPTION;
715 }
716 for (i = 0; i < el->num_values; i++) {
717 struct ldb_val val;
718 struct ldb_dn *dn;
719 struct GUID site_link_guid;
720 int ret;
721 struct kcctpl_multi_edge *edge;
722
723 val = el->values[i];
724 dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
725 if (!dn) {
726 DEBUG(1, (__location__ ": failed to read a DN from "
727 "siteList attribute of %s\n",
728 ldb_dn_get_linearized(bridge->dn)));
729
730 talloc_free(tmp_ctx);
731 return NT_STATUS_INTERNAL_DB_CORRUPTION;
732 }
733
734 ret = dsdb_find_guid_by_dn(ldb, dn, &site_link_guid);
735 if (ret != LDB_SUCCESS) {
736 DEBUG(1, (__location__ ": failed to find objectGUID "
737 "for object %s: %s\n",
738 ldb_dn_get_linearized(dn),
739 ldb_strerror(ret)));
740
741 talloc_free(tmp_ctx);
742 return NT_STATUS_INTERNAL_DB_CORRUPTION;
743 }
744
745 edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
746 if (!edge) {
747 DEBUG(1, (__location__ ": failed to find a graph edge "
748 "with ID=%s\n",
749 GUID_string(tmp_ctx, &site_link_guid)));
750
751 talloc_free(tmp_ctx);
752 return NT_STATUS_INTERNAL_DB_CORRUPTION;
753 }
754
755 if (GUID_equal(&edge->type, &type)) {
756 struct GUID *new_data;
757
758 new_data = talloc_realloc(set, set->edge_ids.data,
759 struct GUID,
760 set->edge_ids.count + 1);
761 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
762 new_data[set->edge_ids.count] = site_link_guid;
763 set->edge_ids.data = new_data;
764 set->edge_ids.count++;
765 }
766 }
767
768 *_set = talloc_steal(graph, set);
769 talloc_free(tmp_ctx);
770 return NT_STATUS_OK;
771 }
772
773 /**
774 * set up a kcctpl_graph, populated with a kcctpl_vertex for each site object, a
775 * kcctpl_multi_edge for each siteLink object, and a kcctpl_multi_edge_set for
776 * each siteLinkBridge object (or implied siteLinkBridge).
777 */
778 static NTSTATUS kcctpl_setup_graph(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
779 struct kcctpl_graph **_graph)
780 {
781 struct kcctpl_graph *graph;
782 struct ldb_dn *sites_dn, *transports_dn;
783 TALLOC_CTX *tmp_ctx;
784 struct ldb_result *res;
785 const char * const transport_attrs[] = { "objectGUID", NULL };
786 const char * const site_attrs[] = { "objectGUID", "options", NULL };
787 const char * const attrs[] = { "objectGUID", "cost", "options",
788 "replInterval", "schedule", NULL };
789 const char * const site_link_bridge_attrs[] = { "objectGUID",
790 "siteLinkList",
791 NULL };
792 int ret;
793 struct GUID_list vertex_ids;
794 unsigned int i;
795 NTSTATUS status;
796 struct ldb_message *site;
797 uint64_t site_opts;
798
799 tmp_ctx = talloc_new(mem_ctx);
800 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
801
802 sites_dn = samdb_sites_dn(ldb, tmp_ctx);
803 if (!sites_dn) {
804 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
805
806 talloc_free(tmp_ctx);
807 return NT_STATUS_INTERNAL_DB_CORRUPTION;
808 }
809
810 ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE,
811 site_attrs, "objectClass=site");
812 if (ret != LDB_SUCCESS) {
813 DEBUG(1, (__location__ ": failed to find site objects under "
814 "%s: %s\n", ldb_dn_get_linearized(sites_dn),
815 ldb_strerror(ret)));
816
817 talloc_free(tmp_ctx);
818 return NT_STATUS_INTERNAL_DB_CORRUPTION;
819 }
820
821 ZERO_STRUCT(vertex_ids);
822 for (i = 0; i < res->count; i++) {
823 struct GUID guid, *new_data;
824
825 guid = samdb_result_guid(res->msgs[i], "objectGUID");
826
827 new_data = talloc_realloc(tmp_ctx, vertex_ids.data, struct GUID,
828 vertex_ids.count + 1);
829 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
830 new_data[vertex_ids.count] = guid;
831 vertex_ids.data = new_data;
832 vertex_ids.count++;
833 }
834
835 status = kcctpl_create_graph(tmp_ctx, vertex_ids, &graph);
836 if (NT_STATUS_IS_ERR(status)) {
837 DEBUG(1, (__location__ ": failed to create graph: %s\n",
838 nt_errstr(status)));
839
840 talloc_free(tmp_ctx);
841 return status;
842 }
843
844 site = kcctpl_local_site(ldb, tmp_ctx);
845 if (!site) {
846 DEBUG(1, (__location__ ": failed to find our own local DC's "
847 "site\n"));
848
849 talloc_free(tmp_ctx);
850 return NT_STATUS_INTERNAL_DB_CORRUPTION;
851 }
852 site_opts = samdb_result_int64(site, "options", 0);
853
854 transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
855 if (!transports_dn) {
856 DEBUG(1, (__location__ ": failed to find our own Inter-Site "
857 "Transports DN\n"));
858
859 talloc_free(tmp_ctx);
860 return NT_STATUS_INTERNAL_DB_CORRUPTION;
861 }
862
863 ret = ldb_search(ldb, tmp_ctx, &res, transports_dn, LDB_SCOPE_ONELEVEL,
864 transport_attrs, "objectClass=interSiteTransport");
865 if (ret != LDB_SUCCESS) {
866 DEBUG(1, (__location__ ": failed to find interSiteTransport "
867 "objects under %s: %s\n",
868 ldb_dn_get_linearized(transports_dn),
869 ldb_strerror(ret)));
870
871 talloc_free(tmp_ctx);
872 return NT_STATUS_INTERNAL_DB_CORRUPTION;
873 }
874
875 for (i = 0; i < res->count; i++) {
876 struct ldb_message *transport;
877 struct ldb_result *res_site_link;
878 struct GUID transport_guid;
879 unsigned int j;
880 uint64_t transport_opts;
881
882 transport = res->msgs[i];
883
884 ret = ldb_search(ldb, tmp_ctx, &res_site_link, transport->dn,
885 LDB_SCOPE_SUBTREE, attrs,
886 "objectClass=siteLink");
887 if (ret != LDB_SUCCESS) {
888 DEBUG(1, (__location__ ": failed to find siteLink "
889 "objects under %s: %s\n",
890 ldb_dn_get_linearized(transport->dn),
891 ldb_strerror(ret)));
892
893 talloc_free(tmp_ctx);
894 return NT_STATUS_INTERNAL_DB_CORRUPTION;
895 }
896
897 transport_guid = samdb_result_guid(transport, "objectGUID");
898 for (j = 0; j < res_site_link->count; j++) {
899 struct kcctpl_multi_edge *edge, *new_data;
900
901 status = kcctpl_create_edge(ldb, graph, transport_guid,
902 res_site_link->msgs[j],
903 &edge);
904 if (NT_STATUS_IS_ERR(status)) {
905 DEBUG(1, (__location__ ": failed to create "
906 "edge: %s\n", nt_errstr(status)));
907 talloc_free(tmp_ctx);
908 return status;
909 }
910
911 new_data = talloc_realloc(graph, graph->edges.data,
912 struct kcctpl_multi_edge,
913 graph->edges.count + 1);
914 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
915 new_data[graph->edges.count] = *edge;
916 graph->edges.data = new_data;
917 graph->edges.count++;
918 }
919
920 transport_opts = samdb_result_int64(transport, "options", 0);
921 if (!(transport_opts & NTDSTRANSPORT_OPT_BRIDGES_REQUIRED) &&
922 !(site_opts & NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED)) {
923 struct kcctpl_multi_edge_set *edge_set, *new_data;
924
925 status = kcctpl_create_auto_edge_set(graph,
926 transport_guid,
927 res_site_link,
928 &edge_set);
929 if (NT_STATUS_IS_ERR(status)) {
930 DEBUG(1, (__location__ ": failed to create "
931 "edge set: %s\n", nt_errstr(status)));
932 talloc_free(tmp_ctx);
933 return status;
934 }
935
936 new_data = talloc_realloc(graph, graph->edge_sets.data,
937 struct kcctpl_multi_edge_set,
938 graph->edge_sets.count + 1);
939 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
940 new_data[graph->edge_sets.count] = *edge_set;
941 graph->edge_sets.data = new_data;
942 graph->edge_sets.count++;
943 } else {
944 ret = ldb_search(ldb, tmp_ctx, &res_site_link,
945 transport->dn, LDB_SCOPE_SUBTREE,
946 site_link_bridge_attrs,
947 "objectClass=siteLinkBridge");
948 if (ret != LDB_SUCCESS) {
949 DEBUG(1, (__location__ ": failed to find "
950 "siteLinkBridge objects under %s: "
951 "%s\n",
952 ldb_dn_get_linearized(transport->dn),
953 ldb_strerror(ret)));
954
955 talloc_free(tmp_ctx);
956 return NT_STATUS_INTERNAL_DB_CORRUPTION;
957 }
958
959 for (j = 0; j < res_site_link->count; j++) {
960 struct ldb_message *bridge;
961 struct kcctpl_multi_edge_set *edge_set,
962 *new_data;
963
964 bridge = res_site_link->msgs[j];
965 status = kcctpl_create_edge_set(ldb, graph,
966 transport_guid,
967 bridge,
968 &edge_set);
969 if (NT_STATUS_IS_ERR(status)) {
970 DEBUG(1, (__location__ ": failed to "
971 "create edge set: %s\n",
972 nt_errstr(status)));
973
974 talloc_free(tmp_ctx);
975 return status;
976 }
977
978 new_data = talloc_realloc(graph,
979 graph->edge_sets.data,
980 struct kcctpl_multi_edge_set,
981 graph->edge_sets.count + 1);
982 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
983 tmp_ctx);
984 new_data[graph->edge_sets.count] = *edge_set;
985 graph->edge_sets.data = new_data;
986 graph->edge_sets.count++;
987 }
988 }
989 }
990
991 *_graph = talloc_steal(mem_ctx, graph);
992 talloc_free(tmp_ctx);
993 return NT_STATUS_OK;
994 }
995
996 /**
997 * determine whether a given DC is known to be in a failed state.
998 */
999 static NTSTATUS kcctpl_bridgehead_dc_failed(struct ldb_context *ldb,
1000 struct GUID guid,
1001 bool detect_failed_dcs,
1002 bool *_failed)
1003 {
1004 TALLOC_CTX *tmp_ctx;
1005 struct ldb_dn *settings_dn;
1006 struct ldb_result *res;
1007 const char * const attrs[] = { "options", NULL };
1008 int ret;
1009 struct ldb_message *settings;
1010 uint64_t settings_opts;
1011 bool failed;
1012
1013 tmp_ctx = talloc_new(ldb);
1014 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1015
1016 settings_dn = samdb_ntds_settings_dn(ldb);
1017 if (!settings_dn) {
1018 DEBUG(1, (__location__ ": failed to find our own NTDS Settings "
1019 "DN\n"));
1020 talloc_free(tmp_ctx);
1021 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1022 }
1023
1024 ret = ldb_search(ldb, tmp_ctx, &res, settings_dn, LDB_SCOPE_BASE, attrs,
1025 "objectClass=nTDSSiteSettings");
1026 if (ret != LDB_SUCCESS) {
1027 DEBUG(1, (__location__ ": failed to find site settings object "
1028 "%s: %s\n", ldb_dn_get_linearized(settings_dn),
1029 ldb_strerror(ret)));
1030 talloc_free(tmp_ctx);
1031 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1032 }
1033 if (res->count == 0) {
1034 DEBUG(1, ("failed to find site settings object %s\n",
1035 ldb_dn_get_linearized(settings_dn)));
1036 talloc_free(tmp_ctx);
1037 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1038 }
1039
1040 settings = res->msgs[0];
1041
1042 settings_opts = samdb_result_int64(settings, "options", 0);
1043 if (settings_opts & NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED) {
1044 failed = false;
1045 } else if (true) { /* TODO: how to get kCCFailedLinks and
1046 kCCFailedConnections? */
1047 failed = true;
1048 } else {
1049 failed = detect_failed_dcs;
1050 }
1051
1052 *_failed = failed;
1053 talloc_free(tmp_ctx);
1054 return NT_STATUS_OK;
1055 }
1056
1057 /**
1058 * get all bridgehead DCs satisfying the given criteria.
1059 */
1060 static NTSTATUS kcctpl_get_all_bridgehead_dcs(struct ldb_context *ldb,
1061 TALLOC_CTX *mem_ctx,
1062 struct GUID site_guid,
1063 struct ldb_message *cross_ref,
1064 struct ldb_message *transport,
1065 bool partial_replica_okay,
1066 bool detect_failed_dcs,
1067 struct message_list *_bridgeheads)
1068 {
1069 struct message_list bridgeheads, all_dcs_in_site;
1070 TALLOC_CTX *tmp_ctx;
1071 struct ldb_result *res;
1072 struct ldb_dn *sites_dn, *schemas_dn;
1073 const char * const attrs[] = { "options", NULL };
1074 int ret;
1075 struct ldb_message *site, *schema;
1076 const char * const dc_attrs[] = { "objectGUID", "options", NULL };
1077 struct ldb_message_element *el;
1078 unsigned int i;
1079 bool rodc;
1080 const char *transport_name, *transport_address_attr;
1081 uint64_t site_opts;
1082
1083 ZERO_STRUCT(bridgeheads);
1084
1085 tmp_ctx = talloc_new(mem_ctx);
1086 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1087
1088 sites_dn = samdb_sites_dn(ldb, tmp_ctx);
1089 if (!sites_dn) {
1090 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
1091
1092 talloc_free(tmp_ctx);
1093 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1094 }
1095
1096 ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_ONELEVEL,
1097 attrs, "(&(objectClass=site)(objectGUID=%s))",
1098 GUID_string(tmp_ctx, &site_guid));
1099 if (ret != LDB_SUCCESS) {
1100 DEBUG(1, (__location__ ": failed to find site object %s: %s\n",
1101 GUID_string(tmp_ctx, &site_guid),
1102 ldb_strerror(ret)));
1103
1104 talloc_free(tmp_ctx);
1105 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1106 }
1107 if (res->count == 0) {
1108 DEBUG(1, (__location__ ": failed to find site object %s\n",
1109 GUID_string(tmp_ctx, &site_guid)));
1110
1111 talloc_free(tmp_ctx);
1112 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1113 }
1114 site = res->msgs[0];
1115
1116 schemas_dn = ldb_get_schema_basedn(ldb);
1117 if (!schemas_dn) {
1118 DEBUG(1, (__location__ ": failed to find our own Schemas DN\n"));
1119
1120 talloc_free(tmp_ctx);
1121 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1122 }
1123
1124 ret = ldb_search(ldb, tmp_ctx, &res, schemas_dn, LDB_SCOPE_SUBTREE,
1125 NULL,
1126 "(&(lDAPDisplayName=nTDSDSA)(objectClass=classSchema))");
1127 if (ret != LDB_SUCCESS) {
1128 DEBUG(1, (__location__ ": failed to find classSchema object :"
1129 "%s\n", ldb_strerror(ret)));
1130
1131 talloc_free(tmp_ctx);
1132 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1133 }
1134 if (res->count == 0) {
1135 DEBUG(1, (__location__ ": failed to find classSchema "
1136 "object\n"));
1137
1138 talloc_free(tmp_ctx);
1139 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1140 }
1141 schema = res->msgs[0];
1142
1143 ZERO_STRUCT(all_dcs_in_site);
1144
1145 ret = ldb_search(ldb, tmp_ctx, &res, site->dn, LDB_SCOPE_SUBTREE,
1146 dc_attrs, "objectCategory=%s",
1147 ldb_dn_get_linearized(schema->dn));
1148 if (ret != LDB_SUCCESS) {
1149 DEBUG(1, (__location__ ": failed to find DCs objects :%s\n",
1150 ldb_strerror(ret)));
1151
1152 talloc_free(tmp_ctx);
1153 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1154 }
1155
1156 el = ldb_msg_find_element(transport, "bridgeheadServerListBL");
1157
1158 rodc = samdb_rodc(ldb);
1159
1160 transport_name = samdb_result_string(transport, "name", NULL);
1161 if (!transport_name) {
1162 DEBUG(1, (__location__ ": failed to find name attribute of "
1163 "object %s\n", ldb_dn_get_linearized(transport->dn)));
1164
1165 talloc_free(tmp_ctx);
1166 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1167 }
1168
1169 transport_address_attr = samdb_result_string(transport,
1170 "transportAddressAttribute",
1171 NULL);
1172 if (!transport_address_attr) {
1173 DEBUG(1, (__location__ ": failed to find "
1174 "transportAddressAttribute attribute of object %s\n",
1175 ldb_dn_get_linearized(transport->dn)));
1176
1177 talloc_free(tmp_ctx);
1178 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1179 }
1180
1181 site_opts = samdb_result_int64(site, "options", 0);
1182
1183 for (i = 0; i < res->count; i++) {
1184 struct ldb_message *dc, *new_data;
1185 struct ldb_dn *parent_dn;
1186 uint64_t behavior_version;
1187 const char *dc_transport_address;
1188 struct ldb_result *parent_res;
1189 const char *parent_attrs[] = { transport_address_attr, NULL };
1190 NTSTATUS status;
1191 struct GUID dc_guid;
1192 bool failed;
1193
1194 dc = res->msgs[i];
1195
1196 parent_dn = ldb_dn_get_parent(tmp_ctx, dc->dn);
1197 if (!parent_dn) {
1198 DEBUG(1, (__location__ ": failed to get parent DN of "
1199 "%s\n", ldb_dn_get_linearized(dc->dn)));
1200
1201 talloc_free(tmp_ctx);
1202 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1203 }
1204
1205 if (el && (el->num_values >= 1)) {
1206 bool contains;
1207 unsigned int j;
1208
1209 contains = false;
1210
1211 for (j = 0; j < el->num_values; j++) {
1212 struct ldb_val val;
1213 struct ldb_dn *dn;
1214
1215 val = el->values[j];
1216
1217 dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
1218 if (!dn) {
1219 DEBUG(1, (__location__ ": failed to read a DN "
1220 "from bridgeheadServerListBL "
1221 "attribute of %s\n",
1222 ldb_dn_get_linearized(transport->dn)));
1223
1224 talloc_free(tmp_ctx);
1225 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1226 }
1227
1228 if (ldb_dn_compare(dn, parent_dn) == 0) {
1229 contains = true;
1230 break;
1231 }
1232 }
1233
1234 if (!contains) {
1235 continue;
1236 }
1237 }
1238
1239 /* TODO: if dc is in the same site as the local DC */
1240 if (true) {
1241 /* TODO: if a replica of cr!nCName is not in the set of
1242 * NC replicas that "should be present" on 'dc' */
1243 /* TODO: a partial replica of the NC "should be
1244 present" */
1245 if (true || (true && !partial_replica_okay)) {
1246 continue;
1247 }
1248 } else {
1249 /* TODO: if an NC replica of cr!nCName is not in the set
1250 * of NC replicas that "are present" on 'dc' */
1251 /* TODO: a partial replica of the NC "is present" */
1252 if (true || (true && !partial_replica_okay)) {
1253 continue;
1254 }
1255 }
1256
1257 behavior_version = samdb_result_int64(dc,
1258 "msDS-Behavior-Version", 0);
1259 /* TODO: cr!nCName corresponds to default NC */
1260 if (rodc && true && behavior_version < DS_BEHAVIOR_WIN2008) {
1261 continue;
1262 }
1263
1264 ret = ldb_search(ldb, tmp_ctx, &parent_res, parent_dn,
1265 LDB_SCOPE_BASE, parent_attrs , NULL);
1266
1267 dc_transport_address = samdb_result_string(parent_res->msgs[0],
1268 transport_address_attr,
1269 NULL);
1270
1271 if (strncmp(transport_name, "IP", 2) != 0 &&
1272 dc_transport_address == NULL) {
1273 continue;
1274 }
1275
1276 dc_guid = samdb_result_guid(dc, "objectGUID");
1277
1278 status = kcctpl_bridgehead_dc_failed(ldb, dc_guid,
1279 detect_failed_dcs,
1280 &failed);
1281 if (NT_STATUS_IS_ERR(status)) {
1282 DEBUG(1, (__location__ ": failed to check if "
1283 "bridgehead DC has failed: %s\n",
1284 nt_errstr(status)));
1285
1286 talloc_free(tmp_ctx);
1287 return status;
1288 }
1289
1290 if (failed) {
1291 continue;
1292 }
1293
1294 new_data = talloc_realloc(tmp_ctx, bridgeheads.data,
1295 struct ldb_message,
1296 bridgeheads.count + 1);
1297 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1298 new_data[bridgeheads.count + 1] = *dc;
1299 bridgeheads.data = new_data;
1300 bridgeheads.count++;
1301 }
1302
1303 if (site_opts & NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED) {
1304 qsort(bridgeheads.data, bridgeheads.count,
1305 sizeof(struct ldb_message), kcctpl_sort_bridgeheads);
1306 } else {
1307 kcctpl_shuffle_bridgeheads(bridgeheads);
1308 }
1309
1310 talloc_steal(mem_ctx, bridgeheads.data);
1311 *_bridgeheads = bridgeheads;
1312 talloc_free(tmp_ctx);
1313 return NT_STATUS_OK;
1314 }
1315
1316 /**
1317 * get a bridgehead DC.
1318 */
1319 static NTSTATUS kcctpl_get_bridgehead_dc(struct ldb_context *ldb,
1320 TALLOC_CTX *mem_ctx,
1321 struct GUID site_guid,
1322 struct ldb_message *cross_ref,
1323 struct ldb_message *transport,
1324 bool partial_replica_okay,
1325 bool detect_failed_dcs,
1326 struct ldb_message **_dsa)
1327 {
1328 struct message_list dsa_list;
1329 NTSTATUS status;
1330
1331 status = kcctpl_get_all_bridgehead_dcs(ldb, mem_ctx,
1332 site_guid, cross_ref, transport,
1333 partial_replica_okay,
1334 detect_failed_dcs, &dsa_list);
1335 if (NT_STATUS_IS_ERR(status)) {
1336 DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
1337 "%s\n", nt_errstr(status)));
1338 return status;
1339 }
1340
1341 *_dsa = (dsa_list.count == 0) ? NULL : &dsa_list.data[0];
1342
1343 return NT_STATUS_OK;
1344 }
1345
1346 /*
1347 * color each vertex to indicate which kinds of NC replicas it contains.
1348 */
1349 static NTSTATUS kcctpl_color_vertices(struct ldb_context *ldb,
1350 struct kcctpl_graph *graph,
1351 struct ldb_message *cross_ref,
1352 bool detect_failed_dcs,
1353 bool *_found_failed_dcs)
1354 {
1355 TALLOC_CTX *tmp_ctx;
1356 struct ldb_dn *sites_dn;
1357 bool found_failed_dcs, partial_replica_okay;
1358 uint32_t i;
1359 struct ldb_message *site;
1360 struct ldb_result *res;
1361 int ret, cr_flags;
1362 struct GUID site_guid;
1363 struct kcctpl_vertex *site_vertex;
1364
1365 found_failed_dcs = false;
1366
1367 tmp_ctx = talloc_new(ldb);
1368 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1369
1370 sites_dn = samdb_sites_dn(ldb, tmp_ctx);
1371 if (!sites_dn) {
1372 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
1373
1374 talloc_free(tmp_ctx);
1375 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1376 }
1377
1378 for (i = 0; i < graph->vertices.count; i++) {
1379 struct kcctpl_vertex *vertex;
1380 struct ldb_dn *nc_name;
1381 /* TODO: set 'attrs' with its corresponding values */
1382 const char * const attrs[] = { NULL };
1383
1384 vertex = &graph->vertices.data[i];
1385
1386 ret = ldb_search(ldb, tmp_ctx, &res, sites_dn,
1387 LDB_SCOPE_SUBTREE, attrs, "objectGUID=%s",
1388 GUID_string(tmp_ctx, &vertex->id));
1389 if (ret != LDB_SUCCESS) {
1390 DEBUG(1, (__location__ ": failed to find site object "
1391 "%s: %s\n", GUID_string(tmp_ctx, &vertex->id),
1392 ldb_strerror(ret)));
1393
1394 talloc_free(tmp_ctx);
1395 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1396 }
1397 if (res->count == 0) {
1398 DEBUG(1, (__location__ ": failed to find site object "
1399 "%s\n", GUID_string(tmp_ctx, &vertex->id)));
1400
1401 talloc_free(tmp_ctx);
1402 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1403 }
1404 site = res->msgs[0];
1405
1406 nc_name = samdb_result_dn(ldb, tmp_ctx, cross_ref,
1407 "nCName", NULL);
1408 if (!nc_name) {
1409 DEBUG(1, (__location__ ": failed to find nCName "
1410 "attribute of object %s\n",
1411 ldb_dn_get_linearized(cross_ref->dn)));
1412
1413 talloc_free(tmp_ctx);
1414 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1415 }
1416
1417 if (true) { /* TODO: site contains 1+ DCs with full replicas of
1418 'nc_name' */
1419 vertex->color = RED;
1420 } else if (true) { /* TODO: site contains 1+ partial replicas of
1421 'nc_name' */
1422 vertex->color = BLACK;
1423 } else {
1424 vertex->color = WHITE;
1425 }
1426 }
1427
1428 site = kcctpl_local_site(ldb, tmp_ctx);
1429 if (!site) {
1430 DEBUG(1, (__location__ ": failed to find our own local DC's "
1431 "site\n"));
1432
1433 talloc_free(tmp_ctx);
1434 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1435 }
1436 site_guid = samdb_result_guid(site, "objectGUID");
1437
1438 site_vertex = kcctpl_find_vertex_by_guid(graph, site_guid);
1439 if (!site_vertex) {
1440 DEBUG(1, (__location__ ": failed to find a vertex edge with "
1441 "GUID=%s\n", GUID_string(tmp_ctx, &site_guid)));
1442
1443 talloc_free(tmp_ctx);
1444 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1445 }
1446
1447 partial_replica_okay = (site_vertex->color == BLACK);
1448
1449 cr_flags = samdb_result_int64(cross_ref, "systemFlags", 0);
1450
1451 for (i = 0; i < graph->vertices.count; i++) {
1452 struct kcctpl_vertex *vertex;
1453 struct ldb_dn *transports_dn;
1454 const char * const attrs[] = { "objectGUID", "name",
1455 "transportAddressAttribute",
1456 NULL };
1457 unsigned int j;
1458
1459 vertex = &graph->vertices.data[i];
1460
1461 transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
1462 if (!transports_dn) {
1463 DEBUG(1, (__location__ ": failed to find our own "
1464 "Inter-Site Transports DN\n"));
1465
1466 talloc_free(tmp_ctx);
1467 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1468 }
1469
1470 ret = ldb_search(ldb, tmp_ctx, &res, transports_dn,
1471 LDB_SCOPE_ONELEVEL, attrs,
1472 "objectClass=interSiteTransport");
1473 if (ret != LDB_SUCCESS) {
1474 DEBUG(1, (__location__ ": failed to find "
1475 "interSiteTransport objects under %s: %s\n",
1476 ldb_dn_get_linearized(transports_dn),
1477 ldb_strerror(ret)));
1478
1479 talloc_free(tmp_ctx);
1480 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1481 }
1482
1483 for (j = 0; j < res->count; j++) {
1484 struct ldb_message *transport, *bridgehead;
1485 const char *transport_name;
1486 struct GUID transport_guid, *new_data;
1487 NTSTATUS status;
1488
1489 transport = res->msgs[j];
1490
1491 transport_name = samdb_result_string(transport,
1492 "name", NULL);
1493 if (!transport_name) {
1494 DEBUG(1, (__location__ ": failed to find name "
1495 "attribute of object %s\n",
1496 ldb_dn_get_linearized(transport->dn)));
1497
1498 talloc_free(tmp_ctx);
1499 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1500 }
1501
1502 transport_guid = samdb_result_guid(transport,
1503 "objectGUID");
1504
1505 if (site_vertex->color == RED &&
1506 strncmp(transport_name, "IP", 2) != 0 &&
1507 (cr_flags & FLAG_CR_NTDS_DOMAIN)) {
1508 continue;
1509 }
1510
1511 if (!kcctpl_find_edge_by_vertex_guid(graph,
1512 vertex->id)) {
1513 continue;
1514 }
1515
1516 status = kcctpl_get_bridgehead_dc(ldb, tmp_ctx,
1517 site_vertex->id,
1518 cross_ref, transport,
1519 partial_replica_okay,
1520 detect_failed_dcs,
1521 &bridgehead);
1522 if (NT_STATUS_IS_ERR(status)) {
1523 DEBUG(1, (__location__ ": failed to get a "
1524 "bridgehead DC: %s\n",
1525 nt_errstr(status)));
1526
1527 talloc_free(tmp_ctx);
1528 return status;
1529 }
1530 if (!bridgehead) {
1531 found_failed_dcs = true;
1532 continue;
1533 }
1534
1535 new_data = talloc_realloc(vertex,
1536 vertex->accept_red_red.data,
1537 struct GUID,
1538 vertex->accept_red_red.count + 1);
1539 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1540 new_data[vertex->accept_red_red.count + 1] = transport_guid;
1541 vertex->accept_red_red.data = new_data;
1542 vertex->accept_red_red.count++;
1543
1544 new_data = talloc_realloc(vertex,
1545 vertex->accept_black.data,
1546 struct GUID,
1547 vertex->accept_black.count + 1);
1548 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1549 new_data[vertex->accept_black.count + 1] = transport_guid;
1550 vertex->accept_black.data = new_data;
1551 vertex->accept_black.count++;
1552 }
1553 }
1554
1555 *_found_failed_dcs = found_failed_dcs;
1556 talloc_free(tmp_ctx);
1557 return NT_STATUS_OK;
1558 }
1559
1560 /**
1561 * setup the fields of the vertices that are relevant to Phase I (Dijkstra's
1562 * Algorithm). for each vertex, set up its cost, root vertex and component. this
1563 * defines the shortest-path forest structures.
1564 */
1565 static void kcctpl_setup_vertices(struct kcctpl_graph *graph)
1566 {
1567 uint32_t i;
1568
1569 for (i = 0; i < graph->vertices.count; i++) {
1570 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
1571
1572 if (vertex->color == WHITE) {
1573 vertex->repl_info.cost = UINT32_MAX;
1574 vertex->root_id = vertex->component_id = GUID_zero();
1575 } else {
1576 vertex->repl_info.cost = 0;
1577 vertex->root_id = vertex->component_id = vertex->id;
1578 }
1579
1580 vertex->repl_info.interval = 0;
1581 vertex->repl_info.options = 0xFFFFFFFF;
1582 ZERO_STRUCT(vertex->repl_info.schedule);
1583 vertex->demoted = false;
1584 }
1585 }
1586
1587 /**
1588 * demote one vertex if necessary.
1589 */
1590 static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex *vertex,
1591 struct GUID type)
1592 {
1593 if (vertex->color == WHITE) {
1594 return;
1595 }
1596
1597 if (!kcctpl_guid_list_contains(vertex->accept_black, type) &&
1598 !kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
1599 vertex->repl_info.cost = UINT32_MAX;
1600 vertex->root_id = GUID_zero();
1601 vertex->demoted = true;
1602 }
1603 }
1604
1605 /**
1606 * clear the demoted state of a vertex.
1607 */
1608 static void kcctpl_undemote_one_vertex(struct kcctpl_vertex *vertex)
1609 {
1610 if (vertex->color == WHITE) {
1611 return;
1612 }
1613
1614 vertex->repl_info.cost = 0;
1615 vertex->root_id = vertex->id;
1616 vertex->demoted = false;
1617 }
1618
1619 /**
1620 * returns the id of the component containing 'vertex' by traversing the up-tree
1621 * implied by the component pointers.
1622 */
1623 static struct GUID kcctpl_get_component_id(struct kcctpl_graph *graph,
1624 struct kcctpl_vertex *vertex)
1625 {
1626 struct kcctpl_vertex *u;
1627 struct GUID root;
1628
1629 u = vertex;
1630 while (!GUID_equal(&u->component_id, &u->id)) {
1631 u = kcctpl_find_vertex_by_guid(graph, u->component_id);
1632 }
1633
1634 root = u->id;
1635
1636 u = vertex;
1637 while (!GUID_equal(&u->component_id, &u->id)) {
1638 struct kcctpl_vertex *w;
1639
1640 w = kcctpl_find_vertex_by_guid(graph, u->component_id);
1641 u->component_id = root;
1642 u = w;
1643 }
1644
1645 return root;
1646 }
1647
1648 /**
1649 * copy all spanning tree edges from 'output_edges' that contain the vertex for
1650 * DCs in the local DC's site.
1651 */
1652 static NTSTATUS kcctpl_copy_output_edges(struct ldb_context *ldb,
1653 TALLOC_CTX *mem_ctx,
1654 struct kcctpl_graph *graph,
1655 struct kcctpl_multi_edge_list output_edges,
1656 struct kcctpl_multi_edge_list *_copy)
1657 {
1658 struct kcctpl_multi_edge_list copy;
1659 TALLOC_CTX *tmp_ctx;
1660 struct ldb_message *site;
1661 struct GUID site_guid;
1662 uint32_t i;
1663
1664 ZERO_STRUCT(copy);
1665
1666 tmp_ctx = talloc_new(ldb);
1667 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1668
1669 site = kcctpl_local_site(ldb, tmp_ctx);
1670 if (!site) {
1671 DEBUG(1, (__location__ ": failed to find our own local DC's "
1672 "site\n"));
1673
1674 talloc_free(tmp_ctx);
1675 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1676 }
1677 site_guid = samdb_result_guid(site, "objectGUID");
1678
1679 for (i = 0; i < output_edges.count; i++) {
1680 struct kcctpl_multi_edge *edge;
1681 struct kcctpl_vertex *vertex1, *vertex2;
1682
1683 edge = &output_edges.data[i];
1684
1685 vertex1 = kcctpl_find_vertex_by_guid(graph,
1686 edge->vertex_ids.data[0]);
1687 if (!vertex1) {
1688 DEBUG(1, (__location__ ": failed to find vertex %s\n",
1689 GUID_string(tmp_ctx,
1690 &edge->vertex_ids.data[0])));
1691 talloc_free(tmp_ctx);
1692 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1693 }
1694
1695 vertex2 = kcctpl_find_vertex_by_guid(graph,
1696 edge->vertex_ids.data[1]);
1697 if (!vertex2) {
1698 DEBUG(1, (__location__ ": failed to find vertex %s\n",
1699 GUID_string(tmp_ctx,
1700 &edge->vertex_ids.data[1])));
1701 talloc_free(tmp_ctx);
1702 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1703 }
1704
1705 if (GUID_equal(&vertex1->id, &site_guid) ||
1706 GUID_equal(&vertex2->id, &site_guid)) {
1707 struct kcctpl_multi_edge *new_data;
1708
1709 if ((vertex1->color == BLACK ||
1710 vertex2->color == BLACK) &&
1711 vertex1->dist_to_red != UINT32_MAX) {
1712
1713 edge->directed = true;
1714
1715 if (vertex2->dist_to_red <
1716 vertex1->dist_to_red) {
1717 struct GUID tmp;
1718
1719 tmp = edge->vertex_ids.data[0];
1720 edge->vertex_ids.data[0] = edge->vertex_ids.data[1];
1721 edge->vertex_ids.data[1] = tmp;
1722 }
1723 }
1724
1725 new_data = talloc_realloc(tmp_ctx, copy.data,
1726 struct kcctpl_multi_edge,
1727 copy.count + 1);
1728 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1729 new_data[copy.count + 1] = *edge;
1730 copy.data = new_data;
1731 copy.count++;
1732 }
1733 }
1734
1735 talloc_steal(mem_ctx, copy.data);
1736 *_copy = copy;
1737 return NT_STATUS_OK;
1738 }
1739
1740 /**
1741 * build the initial sequence for use with Dijkstra's algorithm. it will contain
1742 * the red and black vertices as root vertices, unless these vertices accept no
1743 * edges of the current 'type', or unless black vertices are not being
1744 * including.
1745 */
1746 static NTSTATUS kcctpl_setup_dijkstra(TALLOC_CTX *mem_ctx,
1747 struct kcctpl_graph *graph,
1748 struct GUID type, bool include_black,
1749 struct kcctpl_vertex_list *_vertices)
1750 {
1751 struct kcctpl_vertex_list vertices;
1752 uint32_t i;
1753
1754 kcctpl_setup_vertices(graph);
1755
1756 ZERO_STRUCT(vertices);
1757
1758 for (i = 0; i < graph->vertices.count; i++) {
1759 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
1760
1761 if (vertex->color == WHITE) {
1762 continue;
1763 }
1764
1765 if ((vertex->color == BLACK && !include_black) ||
1766 !kcctpl_guid_list_contains(vertex->accept_black, type) ||
1767 !kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
1768 vertex->repl_info.cost = UINT32_MAX;
1769 vertex->root_id = GUID_zero();
1770 vertex->demoted = true;
1771 } else {
1772 struct kcctpl_vertex *new_data;
1773
1774 new_data = talloc_realloc(mem_ctx, vertices.data,
1775 struct kcctpl_vertex,
1776 vertices.count + 1);
1777 NT_STATUS_HAVE_NO_MEMORY(new_data);
1778 new_data[vertices.count] = *vertex;
1779 vertices.data = new_data;
1780 vertices.count++;
1781 }
1782 }
1783
1784 *_vertices = vertices;
1785 return NT_STATUS_OK;
1786 }
1787
1788 /**
1789 * merge schedules, replication intervals, options and costs.
1790 */
1791 static bool kcctpl_combine_repl_info(struct kcctpl_graph *graph,
1792 struct kcctpl_repl_info *ria,
1793 struct kcctpl_repl_info *rib,
1794 struct kcctpl_repl_info *ric)
1795 {
1796 uint8_t schedule[84];
1797 bool is_available;
1798 uint32_t i;
1799 int32_t ric_cost;
1800
1801 is_available = false;
1802 for (i = 0; i < 84; i++) {
1803 schedule[i] = ria->schedule[i] & rib->schedule[i];
1804
1805 if (schedule[i] == 1) {
1806 is_available = true;
1807 }
1808 }
1809 if (!is_available) {
1810 return false;
1811 }
1812
1813 ric_cost = ria->cost + rib->cost;
1814 ric->cost = (ric_cost < 0) ? UINT32_MAX : ric_cost;
1815
1816 ric->interval = MAX(ria->interval, rib->interval);
1817 ric->options = ria->options & rib->options;
1818 memcpy(&ric->schedule, &schedule, 84);
1819
1820 return true;
1821 }
1822
1823 /**
1824 * helper function for Dijkstra's algorithm. a new path has been found from a
1825 * root vertex to vertex 'vertex2'. this path is ('vertex1->root, ..., vertex1,
1826 * vertex2'). 'edge' is the edge connecting 'vertex1' and 'vertex2'. if this new
1827 * path is better (in this case cheaper, or has a longer schedule), update
1828 * 'vertex2' to use the new path.
1829 */
1830 static NTSTATUS kcctpl_try_new_path(TALLOC_CTX *mem_ctx,
1831 struct kcctpl_graph *graph,
1832 struct kcctpl_vertex_list vertices,
1833 struct kcctpl_vertex *vertex1,
1834 struct kcctpl_multi_edge *edge,
1835 struct kcctpl_vertex *vertex2)
1836 {
1837 struct kcctpl_repl_info new_repl_info;
1838 bool intersect;
1839 uint32_t i, new_duration, old_duration;
1840
1841 ZERO_STRUCT(new_repl_info);
1842
1843 intersect = kcctpl_combine_repl_info(graph, &vertex1->repl_info,
1844 &edge->repl_info, &new_repl_info);
1845
1846 if (new_repl_info.cost > vertex2->repl_info.cost) {
1847 return NT_STATUS_OK;
1848 }
1849
1850 if (new_repl_info.cost < vertex2->repl_info.cost && !intersect) {
1851 return NT_STATUS_OK;
1852 }
1853
1854 new_duration = old_duration = 0;
1855 for (i = 0; i < 84; i++) {
1856 if (new_repl_info.schedule[i] == 1) {
1857 new_duration++;
1858 }
1859
1860 if (vertex2->repl_info.schedule[i] == 1) {
1861 old_duration++;
1862 }
1863 }
1864
1865 if (new_repl_info.cost < vertex2->repl_info.cost ||
1866 new_duration > old_duration) {
1867 struct kcctpl_vertex *new_data;
1868
1869 vertex2->root_id = vertex1->root_id;
1870 vertex2->component_id = vertex1->component_id;
1871 vertex2->repl_info = new_repl_info;
1872
1873 new_data = talloc_realloc(mem_ctx, vertices.data,
1874 struct kcctpl_vertex,
1875 vertices.count + 1);
1876 NT_STATUS_HAVE_NO_MEMORY(new_data);
1877 new_data[vertices.count + 1] = *vertex2;
1878 vertices.data = new_data;
1879 vertices.count++;
1880 }
1881
1882 return NT_STATUS_OK;
1883 }
1884
1885 /**
1886 * run Dijkstra's algorithm with the red (and possibly black) vertices as the
1887 * root vertices, and build up a shortest-path forest.
1888 */
1889 static NTSTATUS kcctpl_dijkstra(struct kcctpl_graph *graph, struct GUID type,
1890 bool include_black)
1891 {
1892 TALLOC_CTX *tmp_ctx;
1893 struct kcctpl_vertex_list vertices;
1894 NTSTATUS status;
1895
1896 tmp_ctx = talloc_new(graph);
1897 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1898
1899 status = kcctpl_setup_dijkstra(tmp_ctx, graph, type, include_black,
1900 &vertices);
1901 if (NT_STATUS_IS_ERR(status)) {
1902 DEBUG(1, (__location__ ": failed to build the initial sequence "
1903 "for Dijkstra's algorithm: %s\n", nt_errstr(status)));
1904
1905 talloc_free(tmp_ctx);
1906 return status;
1907 }
1908
1909 while (vertices.count > 0) {
1910 uint32_t minimum_cost, minimum_index, i;
1911 struct kcctpl_vertex *minimum_vertex, *new_data;
1912
1913 minimum_cost = UINT32_MAX;
1914 minimum_index = -1;
1915 minimum_vertex = NULL;
1916 for (i = 0; i < vertices.count; i++) {
1917 struct kcctpl_vertex *vertex = &vertices.data[i];
1918
1919 if (vertex->repl_info.cost < minimum_cost) {
1920 minimum_cost = vertex->repl_info.cost;
1921 minimum_vertex = vertex;
1922 minimum_index = i;
1923 } else if (vertex->repl_info.cost == minimum_cost &&
1924 GUID_compare(&vertex->id,
1925 &minimum_vertex->id) < 0) {
1926 minimum_vertex = vertex;
1927 minimum_index = i;
1928 }
1929 }
1930
1931 if (minimum_index < vertices.count - 1) {
1932 memcpy(&vertices.data[minimum_index + 1],
1933 &vertices.data[minimum_index],
1934 vertices.count - minimum_index - 1);
1935 }
1936 new_data = talloc_realloc(tmp_ctx, vertices.data,
1937 struct kcctpl_vertex,
1938 vertices.count - 1);
1939 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1940 talloc_free(vertices.data);
1941 vertices.data = new_data;
1942 vertices.count--;
1943
1944 for (i = 0; i < graph->edges.count; i++) {
1945 struct kcctpl_multi_edge *edge = &graph->edges.data[i];
1946
1947 if (kcctpl_guid_list_contains(minimum_vertex->edge_ids,
1948 edge->id)) {
1949 uint32_t j;
1950
1951 for (j = 0; j < edge->vertex_ids.count; j++) {
1952 struct GUID vertex_id;
1953 struct kcctpl_vertex *vertex;
1954
1955 vertex_id = edge->vertex_ids.data[j];
1956 vertex = kcctpl_find_vertex_by_guid(graph,
1957 vertex_id);
1958 if (!vertex) {
1959 DEBUG(1, (__location__
1960 ": failed to find "
1961 "vertex %s\n",
1962 GUID_string(tmp_ctx,
1963 &vertex_id)));
1964
1965 talloc_free(tmp_ctx);
1966 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1967 }
1968
1969 kcctpl_try_new_path(tmp_ctx, graph,
1970 vertices,
1971 minimum_vertex,
1972 edge, vertex);
1973 }
1974 }
1975 }
1976 }
1977
1978 talloc_free(tmp_ctx);
1979 return NT_STATUS_OK;
1980 }
1981
1982 /**
1983 * add an edge to the list of edges that will be processed with Kruskal's. the
1984 * endpoints are in fact the root of the vertices to pass in, so the endpoints
1985 * are always colored vertices.
1986 */
1987 static NTSTATUS kcctpl_add_int_edge(TALLOC_CTX *mem_ctx,
1988 struct kcctpl_graph *graph,
1989 struct kcctpl_internal_edge_list internal_edges,
1990 struct kcctpl_multi_edge *edge,
1991 struct kcctpl_vertex *vertex1,
1992 struct kcctpl_vertex *vertex2)
1993 {
1994 struct kcctpl_vertex *root1, *root2;
1995 bool red_red, found;
1996 struct kcctpl_repl_info repl_info1, repl_info2;
1997 struct kcctpl_internal_edge new_internal_edge, *new_data;
1998 uint32_t i;
1999
2000 root1 = kcctpl_find_vertex_by_guid(graph, vertex1->root_id);
2001 if (!root1) {
2002 TALLOC_CTX *tmp_ctx = talloc_new(graph);
2003 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2004
2005 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2006 GUID_string(tmp_ctx, &vertex1->root_id)));
2007
2008 talloc_free(tmp_ctx);
2009 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2010 }
2011
2012 root2 = kcctpl_find_vertex_by_guid(graph, vertex2->root_id);
2013 if (!root2) {
2014 TALLOC_CTX *tmp_ctx = talloc_new(graph);
2015 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2016
2017 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2018 GUID_string(tmp_ctx, &vertex2->root_id)));
2019
2020 talloc_free(tmp_ctx);
2021 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2022 }
2023
2024 red_red = (root1->color == RED && root2->color == RED);
2025
2026 if (red_red) {
2027 if (!kcctpl_guid_list_contains(root1->accept_red_red,
2028 edge->type) ||
2029 !kcctpl_guid_list_contains(root2->accept_red_red,
2030 edge->type)) {
2031 return NT_STATUS_OK;
2032 }
2033 } else if (!kcctpl_guid_list_contains(root1->accept_black,
2034 edge->type) ||
2035 !kcctpl_guid_list_contains(root2->accept_black,
2036 edge->type)) {
2037 return NT_STATUS_OK;
2038 }
2039
2040 if (!kcctpl_combine_repl_info(graph, &vertex1->repl_info,
2041 &vertex2->repl_info, &repl_info1) ||
2042 !kcctpl_combine_repl_info(graph, &repl_info1, &edge->repl_info,
2043 &repl_info2)) {
2044 return NT_STATUS_OK;
2045 }
2046
2047 new_internal_edge.v1id = root1->id;
2048 new_internal_edge.v2id = root2->id;
2049 new_internal_edge.red_red = red_red;
2050 new_internal_edge.repl_info = repl_info2;
2051 new_internal_edge.type = edge->type;
2052
2053 if (GUID_compare(&new_internal_edge.v1id,
2054 &new_internal_edge.v2id) > 0) {
2055 struct GUID tmp_guid = new_internal_edge.v1id;
2056
2057 new_internal_edge.v1id = new_internal_edge.v2id;
2058 new_internal_edge.v2id = tmp_guid;
2059 }
2060
2061 found = false;
2062 for (i = 0; i < internal_edges.count; i++) {
2063 struct kcctpl_internal_edge *ie = &internal_edges.data[i];
2064
2065 if (kcctpl_internal_edge_equal(ie, &new_internal_edge)) {
2066 found = true;
2067 }
2068 }
2069 if (found) {
2070 return NT_STATUS_OK;
2071 }
2072
2073 new_data = talloc_realloc(mem_ctx, internal_edges.data,
2074 struct kcctpl_internal_edge,
2075 internal_edges.count + 1);
2076 NT_STATUS_HAVE_NO_MEMORY(new_data);
2077 new_data[internal_edges.count + 1] = new_internal_edge;
2078 internal_edges.data = new_data;
2079 internal_edges.count++;
2080
2081 return NT_STATUS_OK;
2082 }
2083
2084 /**
2085 * after running Dijkstra's algorithm, this function examines a multi-edge and
2086 * adds internal edges between every tree connected by this edge.
2087 */
2088 static NTSTATUS kcctpl_process_edge(TALLOC_CTX *mem_ctx,
2089 struct kcctpl_graph *graph,
2090 struct kcctpl_multi_edge *edge,
2091 struct kcctpl_internal_edge_list internal_edges)
2092 {
2093 TALLOC_CTX *tmp_ctx;
2094 struct kcctpl_vertex_list vertices;
2095 uint32_t i;
2096 struct kcctpl_vertex *best_vertex;
2097
2098 ZERO_STRUCT(vertices);
2099
2100 tmp_ctx = talloc_new(mem_ctx);
2101 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2102
2103 for (i = 0; i < edge->vertex_ids.count; i++) {
2104 struct GUID id;
2105 struct kcctpl_vertex *vertex, *new_data;
2106
2107 id = edge->vertex_ids.data[i];
2108
2109 vertex = kcctpl_find_vertex_by_guid(graph, id);
2110 if (!vertex) {
2111 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2112 GUID_string(tmp_ctx, &id)));
2113
2114 talloc_free(tmp_ctx);
2115 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2116 }
2117
2118 new_data = talloc_realloc(tmp_ctx, vertices.data,
2119 struct kcctpl_vertex,
2120 vertices.count + 1);
2121 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
2122 new_data[vertices.count] = *vertex;
2123 vertices.data = new_data;
2124 vertices.count++;
2125 }
2126
2127 qsort(vertices.data, vertices.count, sizeof(struct kcctpl_vertex),
2128 kcctpl_sort_vertices);
2129
2130 best_vertex = &vertices.data[0];
2131
2132 for (i = 0; i < edge->vertex_ids.count; i++) {
2133 struct GUID id, empty_id = GUID_zero();
2134 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2135
2136 id = edge->vertex_ids.data[i];
2137
2138 vertex = kcctpl_find_vertex_by_guid(graph, id);
2139 if (!vertex) {
2140 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2141 GUID_string(tmp_ctx, &id)));
2142
2143 talloc_free(tmp_ctx);
2144 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2145 }
2146
2147 if (!GUID_equal(&vertex->component_id, &empty_id) &&
2148 !GUID_equal(&vertex->root_id, &empty_id)) {
2149 continue;
2150 }
2151
2152 if (!GUID_equal(&best_vertex->component_id,
2153 &empty_id) &&
2154 !GUID_equal(&best_vertex->root_id, &empty_id) &&
2155 !GUID_equal(&vertex->component_id, &empty_id) &&
2156 !GUID_equal(&vertex->root_id, &empty_id) &&
2157 !GUID_equal(&best_vertex->component_id,
2158 &vertex->component_id)) {
2159 NTSTATUS status;
2160
2161 status = kcctpl_add_int_edge(mem_ctx, graph,
2162 internal_edges,
2163 edge, best_vertex,
2164 vertex);
2165 if (NT_STATUS_IS_ERR(status)) {
2166 DEBUG(1, (__location__ ": failed to add an "
2167 "internal edge for %s: %s\n",
2168 GUID_string(tmp_ctx, &vertex->id),
2169 nt_errstr(status)));
2170 talloc_free(tmp_ctx);
2171 return status;
2172 }
2173 }
2174 }
2175
2176 talloc_free(tmp_ctx);
2177 return NT_STATUS_OK;
2178 }
2179
2180 /**
2181 * after running Dijkstra's algorithm to determine the shortest-path forest,
2182 * examine all edges in this edge set. find all inter-tree edges, from which to
2183 * build the list of 'internal edges', which will later be passed on to
2184 * Kruskal's algorithm.
2185 */
2186 static NTSTATUS kcctpl_process_edge_set(TALLOC_CTX *mem_ctx,
2187 struct kcctpl_graph *graph,
2188 struct kcctpl_multi_edge_set *set,
2189 struct kcctpl_internal_edge_list internal_edges)
2190 {
2191 uint32_t i;
2192
2193 if (!set) {
2194 for (i = 0; i < graph->edges.count; i++) {
2195 struct kcctpl_multi_edge *edge;
2196 uint32_t j;
2197 NTSTATUS status;
2198
2199 edge = &graph->edges.data[i];
2200
2201 for (j = 0; j < edge->vertex_ids.count; j++) {
2202 struct GUID id;
2203 struct kcctpl_vertex *vertex;
2204
2205 id = edge->vertex_ids.data[j];
2206
2207 vertex = kcctpl_find_vertex_by_guid(graph, id);
2208 if (!vertex) {
2209 TALLOC_CTX *tmp_ctx;
2210
2211 tmp_ctx = talloc_new(mem_ctx);
2212 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2213
2214 DEBUG(1, (__location__ ": failed to "
2215 "find vertex %s\n",
2216 GUID_string(tmp_ctx, &id)));
2217
2218 talloc_free(tmp_ctx);
2219 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2220 }
2221
2222 kcctpl_check_demote_one_vertex(vertex,
2223 edge->type);
2224 }
2225
2226 status = kcctpl_process_edge(mem_ctx, graph, edge,
2227 internal_edges);
2228 if (NT_STATUS_IS_ERR(status)) {
2229 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2230 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2231
2232 DEBUG(1, (__location__ ": failed to process "
2233 "edge %s: %s\n",
2234 GUID_string(tmp_ctx, &edge->id),
2235 nt_errstr(status)));
2236
2237 talloc_free(tmp_ctx);
2238 return status;
2239 }
2240
2241 for (j = 0; j < edge->vertex_ids.count; j++) {
2242 struct GUID id;
2243 struct kcctpl_vertex *vertex;
2244
2245 id = edge->vertex_ids.data[j];
2246
2247 vertex = kcctpl_find_vertex_by_guid(graph, id);
2248 if (!vertex) {
2249 TALLOC_CTX *tmp_ctx;
2250
2251 tmp_ctx = talloc_new(mem_ctx);
2252 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2253
2254 DEBUG(1, (__location__ ": failed to "
2255 "find vertex %s\n",
2256 GUID_string(tmp_ctx, &id)));
2257
2258 talloc_free(tmp_ctx);
2259 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2260 }
2261
2262 kcctpl_undemote_one_vertex(vertex);
2263 }
2264 }
2265 } else {
2266 for (i = 0; i < graph->edges.count; i++) {
2267 struct kcctpl_multi_edge *edge = &graph->edges.data[i];
2268
2269 if (kcctpl_guid_list_contains(set->edge_ids,
2270 edge->id)) {
2271 NTSTATUS status;
2272
2273 status = kcctpl_process_edge(mem_ctx, graph,
2274 edge,
2275 internal_edges);
2276 if (NT_STATUS_IS_ERR(status)) {
2277 TALLOC_CTX *tmp_ctx;
2278
2279 tmp_ctx = talloc_new(mem_ctx);
2280 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2281
2282 DEBUG(1, (__location__ ": failed to "
2283 "process edge %s: %s\n",
2284 GUID_string(tmp_ctx,
2285 &edge->id),
2286 nt_errstr(status)));
2287
2288 talloc_free(tmp_ctx);
2289 return status;
2290 }
2291 }
2292 }
2293 }
2294
2295 return NT_STATUS_OK;
2296 }
2297
2298 /**
2299 * a new edge, 'internal_edge', has been found for the spanning tree edge. add
2300 * this edge to the list of output edges.
2301 */
2302 static NTSTATUS kcctpl_add_out_edge(TALLOC_CTX *mem_ctx,
2303 struct kcctpl_graph *graph,
2304 struct kcctpl_multi_edge_list output_edges,
2305 struct kcctpl_internal_edge *internal_edge)
2306 {
2307 struct kcctpl_vertex *vertex1, *vertex2;
2308 TALLOC_CTX *tmp_ctx;
2309 struct kcctpl_multi_edge *new_edge, *new_data;
2310 struct GUID *new_data_id;
2311
2312 tmp_ctx = talloc_new(mem_ctx);
2313 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2314
2315 vertex1 = kcctpl_find_vertex_by_guid(graph, internal_edge->v1id);
2316 if (!vertex1) {
2317 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2318 GUID_string(tmp_ctx, &internal_edge->v1id)));
2319
2320 talloc_free(tmp_ctx);
2321 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2322 }
2323
2324 vertex2 = kcctpl_find_vertex_by_guid(graph, internal_edge->v2id);
2325 if (!vertex2) {
2326 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2327 GUID_string(tmp_ctx, &internal_edge->v2id)));
2328
2329 talloc_free(tmp_ctx);
2330 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2331 }
2332
2333 new_edge = talloc(tmp_ctx, struct kcctpl_multi_edge);
2334 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge, tmp_ctx);
2335
2336 new_edge->id = GUID_random(); /* TODO: what should be new_edge->GUID? */
2337 new_edge->directed = false;
2338
2339 new_edge->vertex_ids.data = talloc_array(new_edge, struct GUID, 2);
2340 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge->vertex_ids.data, tmp_ctx);
2341
2342 new_edge->vertex_ids.data[0] = vertex1->id;
2343 new_edge->vertex_ids.data[1] = vertex2->id;
2344 new_edge->vertex_ids.count = 2;
2345
2346 new_edge->type = internal_edge->type;
2347 new_edge->repl_info = internal_edge->repl_info;
2348
2349 new_data = talloc_realloc(tmp_ctx, output_edges.data,
2350 struct kcctpl_multi_edge,
2351 output_edges.count + 1);
2352 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
2353 new_data[output_edges.count + 1] = *new_edge;
2354 output_edges.data = new_data;
2355 output_edges.count++;
2356
2357 new_data_id = talloc_realloc(vertex1, vertex1->edge_ids.data,
2358 struct GUID, vertex1->edge_ids.count);
2359 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
2360 new_data_id[vertex1->edge_ids.count] = new_edge->id;
2361 talloc_free(vertex1->edge_ids.data);
2362 vertex1->edge_ids.data = new_data_id;
2363 vertex1->edge_ids.count++;
2364
2365 new_data_id = talloc_realloc(vertex2, vertex2->edge_ids.data,
2366 struct GUID, vertex2->edge_ids.count);
2367 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
2368 new_data_id[vertex2->edge_ids.count] = new_edge->id;
2369 talloc_free(vertex2->edge_ids.data);
2370 vertex2->edge_ids.data = new_data_id;
2371 vertex2->edge_ids.count++;
2372
2373 talloc_steal(graph, new_edge);
2374 talloc_steal(mem_ctx, output_edges.data);
2375 talloc_free(tmp_ctx);
2376 return NT_STATUS_OK;
2377 }
2378
2379 /**
2380 * run Kruskal's minimum-cost spanning tree algorithm on the internal edges
2381 * (that represent shortest paths in the original graph between colored
2382 * vertices).
2383 */
2384 static NTSTATUS kcctpl_kruskal(TALLOC_CTX *mem_ctx, struct kcctpl_graph *graph,
2385 struct kcctpl_internal_edge_list internal_edges,
2386 struct kcctpl_multi_edge_list *_output_edges)
2387 {
2388 uint32_t i, num_expected_tree_edges, cst_edges;
2389 struct kcctpl_multi_edge_list output_edges;
2390
2391 num_expected_tree_edges = 0;
2392 for (i = 0; i < graph->vertices.count; i++) {
2393 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2394
2395 talloc_free(vertex->edge_ids.data);
2396 ZERO_STRUCT(vertex->edge_ids);
2397
2398 if (vertex->color == RED || vertex->color == WHITE) {
2399 num_expected_tree_edges++;
2400 }
2401 }
2402
2403 qsort(internal_edges.data, internal_edges.count,
2404 sizeof(struct kcctpl_internal_edge), kcctpl_sort_internal_edges);
2405
2406 cst_edges = 0;
2407
2408 ZERO_STRUCT(output_edges);
2409
2410 while (internal_edges.count > 0 &&
2411 cst_edges < num_expected_tree_edges) {
2412 struct kcctpl_internal_edge *edge, *new_data;
2413 struct kcctpl_vertex *vertex1, *vertex2;
2414 struct GUID comp1, comp2;
2415
2416 edge = &internal_edges.data[0];
2417
2418 vertex1 = kcctpl_find_vertex_by_guid(graph, edge->v1id);
2419 if (!vertex1) {
2420 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2421 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2422
2423 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2424 GUID_string(tmp_ctx, &edge->v1id)));
2425
2426 talloc_free(tmp_ctx);
2427 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2428 }
2429
2430 vertex2 = kcctpl_find_vertex_by_guid(graph, edge->v2id);
2431 if (!vertex2) {
2432 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2433 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2434
2435 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2436 GUID_string(tmp_ctx, &edge->v2id)));
2437
2438 talloc_free(tmp_ctx);
2439 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2440 }
2441
2442 comp1 = kcctpl_get_component_id(graph, vertex1);
2443 comp2 = kcctpl_get_component_id(graph, vertex2);
2444
2445 if (!GUID_equal(&comp1, &comp2)) {
2446 NTSTATUS status;
2447 struct kcctpl_vertex *vertex;
2448
2449 cst_edges++;
2450
2451 status = kcctpl_add_out_edge(mem_ctx, graph,
2452 output_edges, edge);
2453 if (NT_STATUS_IS_ERR(status)) {
2454 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2455 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2456
2457 DEBUG(1, (__location__ ": failed to add an "
2458 "output edge between %s and %s: %s\n",
2459 GUID_string(tmp_ctx, &edge->v1id),
2460 GUID_string(tmp_ctx, &edge->v2id),
2461 nt_errstr(status)));
2462
2463 talloc_free(tmp_ctx);
2464 return status;
2465 }
2466
2467 vertex = kcctpl_find_vertex_by_guid(graph, comp1);
2468 if (!vertex) {
2469 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2470 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2471
2472 DEBUG(1, (__location__ ": failed to find "
2473 "vertex %s\n", GUID_string(tmp_ctx,
2474 &comp1)));
2475
2476 talloc_free(tmp_ctx);
2477 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2478 }
2479 vertex->component_id = comp2;
2480 }
2481
2482 internal_edges.data = internal_edges.data + 1;
2483 new_data = talloc_realloc(mem_ctx, internal_edges.data,
2484 struct kcctpl_internal_edge,
2485 internal_edges.count - 1);
2486 NT_STATUS_HAVE_NO_MEMORY(new_data);
2487 talloc_free(internal_edges.data);
2488 internal_edges.data = new_data;
2489 internal_edges.count--;
2490 }
2491
2492 *_output_edges = output_edges;
2493 return NT_STATUS_OK;
2494 }
2495
2496 /**
2497 * count the number of components. a component is considered to be a bunch of
2498 * colored vertices that are connected by the spanning tree. vertices whose
2499 * component ID is the same as their vertex ID are the root of the connected
2500 * component.
2501 */
2502 static uint32_t kcctpl_count_components(struct kcctpl_graph *graph)
2503 {
2504 uint32_t num_components = 0, i;
2505
2506 for (i = 0; i < graph->vertices.count; i++) {
2507 struct kcctpl_vertex *vertex;
2508 struct GUID component_id;
2509
2510 vertex = &graph->vertices.data[i];
2511
2512 if (vertex->color == WHITE) {
2513 continue;
2514 }
2515
2516 component_id = kcctpl_get_component_id(graph, vertex);
2517 if (GUID_equal(&component_id, &vertex->id)) {
2518 vertex->component_index = num_components;
2519 num_components++;
2520 }
2521 }
2522
2523 return num_components;
2524 }
2525
2526 /**
2527 * calculate the spanning tree and return the edges that include the vertex for
2528 * the local site.
2529 */
2530 static NTSTATUS kcctpl_get_spanning_tree_edges(struct ldb_context *ldb,
2531 TALLOC_CTX *mem_ctx,
2532 struct kcctpl_graph *graph,
2533 uint32_t *_component_count,
2534 struct kcctpl_multi_edge_list *_st_edge_list)
2535 {
2536 TALLOC_CTX *tmp_ctx;
2537 struct kcctpl_internal_edge_list internal_edges;
2538 uint32_t i, component_count;
2539 NTSTATUS status;
2540 struct kcctpl_multi_edge_list output_edges, st_edge_list;
2541
2542 ZERO_STRUCT(internal_edges);
2543
2544 tmp_ctx = talloc_new(mem_ctx);
2545 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2546
2547 for (i = 0; i < graph->edge_sets.count; i++) {
2548 struct kcctpl_multi_edge_set *set;
2549 struct GUID edge_type;
2550 uint32_t j;
2551
2552 set = &graph->edge_sets.data[i];
2553
2554 edge_type = GUID_zero();
2555
2556 for (j = 0; j < graph->vertices.count; j++) {
2557 struct kcctpl_vertex *vertex = &graph->vertices.data[j];
2558
2559 talloc_free(vertex->edge_ids.data);
2560 ZERO_STRUCT(vertex->edge_ids.data);
2561 }
2562
2563 for (j = 0; j < set->edge_ids.count; j++) {
2564 struct GUID edge_id;
2565 struct kcctpl_multi_edge *edge;
2566 uint32_t k;
2567
2568 edge_id = set->edge_ids.data[j];
2569 edge = kcctpl_find_edge_by_guid(graph, edge_id);
2570 if (!edge) {
2571 DEBUG(1, (__location__ ": failed to find a "
2572 "graph edge with ID=%s\n",
2573 GUID_string(tmp_ctx, &edge_id)));
2574
2575 talloc_free(tmp_ctx);
2576 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2577 }
2578
2579 edge_type = edge->type;
2580
2581 for (k = 0; k < edge->vertex_ids.count; k++) {
2582 struct GUID vertex_id, *new_data;
2583 struct kcctpl_vertex *vertex;
2584
2585 vertex_id = edge->vertex_ids.data[k];
2586 vertex = kcctpl_find_vertex_by_guid(graph,
2587 vertex_id);
2588 if (!vertex) {
2589 DEBUG(1, (__location__ ": failed to "
2590 "find a graph vertex with "
2591 "ID=%s\n",
2592 GUID_string(tmp_ctx,
2593 &edge_id)));
2594
2595 talloc_free(tmp_ctx);
2596 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2597 }
2598
2599 new_data = talloc_realloc(tmp_ctx,
2600 vertex->edge_ids.data,
2601 struct GUID,
2602 vertex->edge_ids.count + 1);
2603 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
2604 tmp_ctx);
2605 new_data[vertex->edge_ids.count] = edge->id;
2606 vertex->edge_ids.data = new_data;
2607 vertex->edge_ids.count++;
2608 }
2609 }
2610
2611 status = kcctpl_dijkstra(graph, edge_type, false);
2612 if (NT_STATUS_IS_ERR(status)) {
2613 DEBUG(1, (__location__ ": failed to run Dijkstra's "
2614 "algorithm: %s\n", nt_errstr(status)));
2615
2616 talloc_free(tmp_ctx);
2617 return status;
2618 }
2619
2620 status = kcctpl_process_edge_set(tmp_ctx, graph, set,
2621 internal_edges);
2622 if (NT_STATUS_IS_ERR(status)) {
2623 DEBUG(1, (__location__ ": failed to process edge set "
2624 "%s: %s\n", GUID_string(tmp_ctx, &set->id),
2625 nt_errstr(status)));
2626
2627 talloc_free(tmp_ctx);
2628 return status;
2629 }
2630
2631 status = kcctpl_dijkstra(graph, edge_type, true);
2632 if (NT_STATUS_IS_ERR(status)) {
2633 DEBUG(1, (__location__ ": failed to run Dijkstra's "
2634 "algorithm: %s\n", nt_errstr(status)));
2635
2636 talloc_free(tmp_ctx);
2637 return status;
2638 }
2639
2640 status = kcctpl_process_edge_set(tmp_ctx, graph, set,
2641 internal_edges);
2642 if (NT_STATUS_IS_ERR(status)) {
2643 DEBUG(1, (__location__ ": failed to process edge set "
2644 "%s: %s\n", GUID_string(tmp_ctx, &set->id),
2645 nt_errstr(status)));
2646
2647 talloc_free(tmp_ctx);
2648 return status;
2649 }
2650 }
2651
2652 kcctpl_setup_vertices(graph);
2653
2654 status = kcctpl_process_edge_set(tmp_ctx, graph, NULL, internal_edges);
2655 if (NT_STATUS_IS_ERR(status)) {
2656 DEBUG(1, (__location__ ": failed to process empty edge set: "
2657 "%s\n", nt_errstr(status)));
2658
2659 talloc_free(tmp_ctx);
2660 return status;
2661 }
2662
2663 status = kcctpl_kruskal(tmp_ctx, graph, internal_edges, &output_edges);
2664 if (NT_STATUS_IS_ERR(status)) {
2665 DEBUG(1, (__location__ ": failed to run Kruskal's algorithm: "
2666 "%s\n", nt_errstr(status)));
2667
2668 talloc_free(tmp_ctx);
2669 return status;
2670 }
2671
2672 for (i = 0; i < graph->vertices.count; i++) {
2673 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2674
2675 if (vertex->color == RED) {
2676 vertex->dist_to_red = 0;
2677 } else if (true) { /* TODO: if there exists a path from 'vertex'
2678 to a RED vertex */
2679 vertex->dist_to_red = -1; /* TODO: the length of the
2680 shortest such path */
2681 } else {
2682 vertex->dist_to_red = UINT32_MAX;
2683 }
2684 }
2685
2686 component_count = kcctpl_count_components(graph);
2687
2688 status = kcctpl_copy_output_edges(ldb, tmp_ctx, graph, output_edges,
2689 &st_edge_list);
2690 if (NT_STATUS_IS_ERR(status)) {
2691 DEBUG(1, (__location__ ": failed to copy edge list: %s\n",
2692 nt_errstr(status)));
2693
2694 talloc_free(tmp_ctx);
2695 return status;
2696 }
2697
2698 *_component_count = component_count;
2699 talloc_steal(mem_ctx, st_edge_list.data);
2700 *_st_edge_list = st_edge_list;
2701 talloc_free(tmp_ctx);
2702 return NT_STATUS_OK;
2703 }
2704
2705 /**
2706 * creat an nTDSConnection object with the given parameters if one does not
2707 * already exist.
2708 */
2709 static NTSTATUS kcctpl_create_connection(struct ldb_context *ldb,
2710 TALLOC_CTX *mem_ctx,
2711 struct ldb_message *cross_ref,
2712 struct ldb_message *r_bridgehead,
2713 struct ldb_message *transport,
2714 struct ldb_message *l_bridgehead,
2715 struct kcctpl_repl_info repl_info,
2716 uint8_t schedule[84],
2717 bool detect_failed_dcs,
2718 bool partial_replica_okay,
2719 struct GUID_list *_keep_connections)
2720 {
2721 TALLOC_CTX *tmp_ctx;
2722 struct ldb_dn *r_site_dn, *l_site_dn, *servers_dn;
2723 bool ok;
2724 struct GUID r_site_guid, l_site_guid;
2725 int ret;
2726 struct message_list r_bridgeheads_all, l_bridgeheads_all,
2727 r_bridgeheads_available, l_bridgeheads_available;
2728 NTSTATUS status;
2729 struct ldb_result *res;
2730 const char * const attrs[] = { "objectGUID", "parent", "fromServer",
2731 "transportType", "schedule", "options",
2732 "enabledConnection", NULL };
2733 unsigned int i, valid_connections;
2734 struct GUID_list keep_connections;
2735
2736 tmp_ctx = talloc_new(ldb);
2737 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2738
2739 r_site_dn = ldb_dn_copy(tmp_ctx, r_bridgehead->dn);
2740 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(r_site_dn, tmp_ctx);
2741
2742 ok = ldb_dn_remove_child_components(r_site_dn, 3);
2743 if (!ok) {
2744 talloc_free(tmp_ctx);
2745 return NT_STATUS_NO_MEMORY;
2746 }
2747
2748 ret = dsdb_find_guid_by_dn(ldb, r_site_dn, &r_site_guid);
2749 if (ret != LDB_SUCCESS) {
2750 DEBUG(1, (__location__ ": failed to find objectGUID for object "
2751 "%s: %s\n", ldb_dn_get_linearized(r_site_dn),
2752 ldb_strerror(ret)));
2753
2754 talloc_free(tmp_ctx);
2755 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2756 }
2757
2758 l_site_dn = ldb_dn_copy(tmp_ctx, l_bridgehead->dn);
2759 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(l_site_dn, tmp_ctx);
2760
2761 ok = ldb_dn_remove_child_components(l_site_dn, 3);
2762 if (!ok) {
2763 talloc_free(tmp_ctx);
2764 return NT_STATUS_NO_MEMORY;
2765 }
2766
2767 ret = dsdb_find_guid_by_dn(ldb, l_site_dn, &l_site_guid);
2768 if (ret != LDB_SUCCESS) {
2769 DEBUG(1, (__location__ ": failed to find objectGUID for object "
2770 "%s: %s\n", ldb_dn_get_linearized(l_site_dn),
2771 ldb_strerror(ret)));
2772
2773 talloc_free(tmp_ctx);
2774 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2775 }
2776
2777 status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
2778 r_site_guid, cross_ref,
2779 transport, partial_replica_okay,
2780 false, &r_bridgeheads_all);
2781 if (NT_STATUS_IS_ERR(status)) {
2782 DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2783 "%s\n", nt_errstr(status)));
2784 return status;
2785 }
2786
2787 status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
2788 r_site_guid, cross_ref,
2789 transport, partial_replica_okay,
2790 detect_failed_dcs,
2791 &r_bridgeheads_available);
2792 if (NT_STATUS_IS_ERR(status)) {
2793 DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2794 "%s\n", nt_errstr(status)));
2795 return status;
2796 }
2797
2798 status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
2799 l_site_guid, cross_ref,
2800 transport, partial_replica_okay,
2801 false, &l_bridgeheads_all);
2802 if (NT_STATUS_IS_ERR(status)) {
2803 DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2804 "%s\n", nt_errstr(status)));
2805 return status;
2806 }
2807
2808 status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
2809 l_site_guid, cross_ref,
2810 transport, partial_replica_okay,
2811 detect_failed_dcs,
2812 &l_bridgeheads_available);
2813 if (NT_STATUS_IS_ERR(status)) {
2814 DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2815 "%s\n", nt_errstr(status)));
2816 return status;
2817 }
2818
2819 servers_dn = samdb_sites_dn(ldb, tmp_ctx);
2820 if (!servers_dn) {
2821 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
2822
2823 talloc_free(tmp_ctx);
2824 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2825 }
2826 ok = ldb_dn_add_child_fmt(servers_dn, "CN=Servers");
2827 if (!ok) {
2828 talloc_free(tmp_ctx);
2829 return NT_STATUS_NO_MEMORY;
2830 }
2831
2832 ret = ldb_search(ldb, tmp_ctx, &res, servers_dn, LDB_SCOPE_SUBTREE,
2833 attrs, "objectClass=nTDSConnection");
2834 if (ret != LDB_SUCCESS) {
2835 DEBUG(1, (__location__ ": failed to find nTDSConnection "
2836 "objects: %s\n", ldb_strerror(ret)));
2837
2838 talloc_free(tmp_ctx);
2839 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2840 }
2841
2842 for (i = 0; i < res->count; i++) {
2843 struct ldb_message *connection;
2844 struct ldb_dn *parent_dn, *from_server;
2845
2846 connection = res->msgs[i];
2847
2848 parent_dn = ldb_dn_get_parent(tmp_ctx, connection->dn);
2849 if (!parent_dn) {
2850 DEBUG(1, (__location__ ": failed to get parent DN of "
2851 "%s\n",
2852 ldb_dn_get_linearized(connection->dn)));
2853
2854 talloc_free(tmp_ctx);
2855 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2856 }
2857
2858 from_server = samdb_result_dn(ldb, tmp_ctx, connection,
2859 "fromServer", NULL);
2860 if (!from_server) {
2861 DEBUG(1, (__location__ ": failed to find fromServer "
2862 "attribute of object %s\n",
2863 ldb_dn_get_linearized(connection->dn)));
2864
2865 talloc_free(tmp_ctx);
2866 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2867 }
2868
2869 if (kcctpl_message_list_contains_dn(l_bridgeheads_all,
2870 parent_dn) &&
2871 kcctpl_message_list_contains_dn(r_bridgeheads_all,
2872 from_server)) {
2873 uint64_t conn_opts;
2874 /* TODO: initialize conn_schedule from connection */
2875 uint8_t conn_schedule[84];
2876 struct ldb_dn *conn_transport_type;
2877
2878 conn_opts = samdb_result_int64(connection,
2879 "options", 0);
2880
2881 conn_transport_type = samdb_result_dn(ldb, tmp_ctx,
2882 connection,
2883 "transportType",
2884 NULL);
2885 if (!conn_transport_type) {
2886 DEBUG(1, (__location__ ": failed to find "
2887 "transportType attribute of object "
2888 "%s\n",
2889 ldb_dn_get_linearized(connection->dn)));
2890
2891 talloc_free(tmp_ctx);
2892 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2893 }
2894
2895 if ((conn_opts & NTDSCONN_OPT_IS_GENERATED) &&
2896 !(conn_opts & NTDSCONN_OPT_RODC_TOPOLOGY) &&
2897 ldb_dn_compare(conn_transport_type,
2898 transport->dn) == 0) {
2899 if (!(conn_opts & NTDSCONN_OPT_USER_OWNED_SCHEDULE) &&
2900 memcmp(&conn_schedule, &schedule, 84) != 0) {
2901 /* TODO: perform an originating update
2902 to set conn!schedule to schedule */
2903 }
2904
2905 if ((conn_opts & NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT) &&
2906 (conn_opts & NTDSCONN_OPT_USE_NOTIFY)) {
2907 if (!(repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY)) {
2908 /* TODO: perform an originating
2909 update to clear bits
2910 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2911 and NTDSCONN_OPT_USE_NOTIFY
2912 in conn!options */
2913 }
2914 } else if (repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY) {
2915 /* TODO: perform an originating update
2916 to set bits
2917 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2918 and NTDSCONN_OPT_USE_NOTIFY in
2919 conn!options */
2920 }
2921
2922 if (conn_opts & NTDSCONN_OPT_TWOWAY_SYNC) {
2923 if (!(repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC)) {
2924 /* TODO: perform an originating
2925 update to clear bit
2926 NTDSCONN_OPT_TWOWAY_SYNC in
2927 conn!options. */
2928 }
2929 } else if (repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC) {
2930 /* TODO: perform an originating update
2931 to set bit NTDSCONN_OPT_TWOWAY_SYNC
2932 in conn!options. */
2933 }
2934
2935 if (conn_opts & NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION) {
2936 if (!(repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION)) {
2937 /* TODO: perform an originating
2938 update to clear bit
2939 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2940 in conn!options. */
2941 }
2942 } else if (repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION) {
2943 /* TODO: perform an originating update
2944 to set bit
2945 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2946 in conn!options. */
2947 }
2948 }
2949 }
2950 }
2951
2952 ZERO_STRUCT(keep_connections);
2953
2954 valid_connections = 0;
2955 for (i = 0; i < res->count; i++) {
2956 struct ldb_message *connection;
2957 struct ldb_dn *parent_dn, *from_server;
2958
2959 connection = res->msgs[i];
2960
2961 parent_dn = ldb_dn_get_parent(tmp_ctx, connection->dn);
2962 if (!parent_dn) {
2963 DEBUG(1, (__location__ ": failed to get parent DN of "
2964 "%s\n",
2965 ldb_dn_get_linearized(connection->dn)));
2966
2967 talloc_free(tmp_ctx);
2968 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2969 }
2970
2971 from_server = samdb_result_dn(ldb, tmp_ctx, connection,
2972 "fromServer", NULL);
2973 if (!from_server) {
2974 DEBUG(1, (__location__ ": failed to find fromServer "
2975 "attribute of object %s\n",
2976 ldb_dn_get_linearized(connection->dn)));
2977
2978 talloc_free(tmp_ctx);
2979 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2980 }
2981
2982 if (kcctpl_message_list_contains_dn(l_bridgeheads_all,
2983 parent_dn) &&
2984 kcctpl_message_list_contains_dn(r_bridgeheads_all,
2985 from_server)) {
2986 uint64_t conn_opts;
2987 struct ldb_dn *conn_transport_type;
2988
2989 conn_opts = samdb_result_int64(connection,
2990 "options", 0);
2991
2992 conn_transport_type = samdb_result_dn(ldb, tmp_ctx,
2993 connection,
2994 "transportType",
2995 NULL);
2996 if (!conn_transport_type) {
2997 DEBUG(1, (__location__ ": failed to find "
2998 "transportType attribute of object "
2999 "%s\n",
3000 ldb_dn_get_linearized(connection->dn)));
3001
3002 talloc_free(tmp_ctx);
3003 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3004 }
3005
3006 if ((!(conn_opts & NTDSCONN_OPT_IS_GENERATED) ||
3007 ldb_dn_compare(conn_transport_type,
3008 transport->dn) == 0) &&
3009 !(conn_opts & NTDSCONN_OPT_RODC_TOPOLOGY)) {
3010 struct GUID r_guid, l_guid, conn_guid;
3011 bool failed_state_r, failed_state_l;
3012
3013 ret = dsdb_find_guid_by_dn(ldb, from_server,
3014 &r_guid);
3015 if (ret != LDB_SUCCESS) {
3016 DEBUG(1, (__location__ ": failed to "
3017 "find GUID for object %s\n",
3018 ldb_dn_get_linearized(from_server)));
3019
3020 talloc_free(tmp_ctx);
3021 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3022 }
3023
3024 ret = dsdb_find_guid_by_dn(ldb, parent_dn,
3025 &l_guid);
3026 if (ret != LDB_SUCCESS) {
3027 DEBUG(1, (__location__ ": failed to "
3028 "find GUID for object %s\n",
3029 ldb_dn_get_linearized(parent_dn)));
3030
3031 talloc_free(tmp_ctx);
3032 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3033 }
3034
3035 status = kcctpl_bridgehead_dc_failed(ldb,
3036 r_guid,
3037 detect_failed_dcs,
3038 &failed_state_r);
3039 if (NT_STATUS_IS_ERR(status)) {
3040 DEBUG(1, (__location__ ": failed to "
3041 "check if bridgehead DC has "
3042 "failed: %s\n",
3043 nt_errstr(status)));
3044
3045 talloc_free(tmp_ctx);
3046 return status;
3047 }
3048
3049 status = kcctpl_bridgehead_dc_failed(ldb,
3050 l_guid,
3051 detect_failed_dcs,
3052 &failed_state_l);
3053 if (NT_STATUS_IS_ERR(status)) {
3054 DEBUG(1, (__location__ ": failed to "
3055 "check if bridgehead DC has "
3056 "failed: %s\n",
3057 nt_errstr(status)));
3058
3059 talloc_free(tmp_ctx);
3060 return status;
3061 }
3062
3063 if (!failed_state_r && !failed_state_l) {
3064 valid_connections++;
3065 }
3066
3067 conn_guid = samdb_result_guid(connection,
3068 "objectGUID");
3069
3070 if (!kcctpl_guid_list_contains(keep_connections,
3071 conn_guid)) {
3072 struct GUID *new_data;
3073
3074 new_data = talloc_realloc(tmp_ctx,
3075 keep_connections.data,
3076 struct GUID,
3077 keep_connections.count + 1);
3078 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
3079 tmp_ctx);
3080 new_data[keep_connections.count] = conn_guid;
3081 keep_connections.data = new_data;
3082 keep_connections.count++;
3083 }
3084 }
3085 }
3086 }
3087
3088 if (valid_connections == 0) {
3089 uint64_t opts = NTDSCONN_OPT_IS_GENERATED;
3090 struct GUID new_guid, *new_data;
3091
3092 if (repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY) {
3093 opts |= NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT;
3094 opts |= NTDSCONN_OPT_USE_NOTIFY;
3095 }
3096
3097 if (repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC) {
3098 opts |= NTDSCONN_OPT_TWOWAY_SYNC;
3099 }
3100
3101 if (repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION) {
3102 opts |= NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION;
3103 }
3104
3105 /* perform an originating update to create a new nTDSConnection
3106 * object cn that is:
3107 *
3108 * - child of l_bridgehead
3109 * - cn!enabledConnection = true
3110 * - cn!options = opts
3111 * - cn!transportType = t
3112 * - cn!fromServer = r_bridgehead
3113 * - cn!schedule = schedule
3114 */
3115
3116 /* TODO: what should be the new connection's GUID? */
3117 new_guid = GUID_random();
3118
3119 new_data = talloc_realloc(tmp_ctx, keep_connections.data,
3120 struct GUID,
3121 keep_connections.count + 1);
3122 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
3123 new_data[keep_connections.count] = new_guid;
3124 keep_connections.data = new_data;
3125 keep_connections.count++;
3126 }
3127
3128 talloc_steal(mem_ctx, keep_connections.data);
3129 *_keep_connections = keep_connections;
3130 talloc_free(tmp_ctx);
3131 return NT_STATUS_OK;
3132 }
3133
3134 /**
3135 * construct an NC replica graph for the NC identified by the given 'cross_ref',
3136 * then create any additional nTDSConnection objects required.
3137 */
3138 static NTSTATUS kcctpl_create_connections(struct ldb_context *ldb,
3139 TALLOC_CTX *mem_ctx,
3140 struct kcctpl_graph *graph,
3141 struct ldb_message *cross_ref,
3142 bool detect_failed_dcs,
3143 struct GUID_list keep_connections,
3144 bool *_found_failed_dcs,
3145 bool *_connected)
3146 {
3147 bool connected, found_failed_dcs, partial_replica_okay, rodc;
3148 NTSTATUS status;
3149 struct ldb_message *site;
3150 TALLOC_CTX *tmp_ctx;
3151 struct GUID site_guid;
3152 struct kcctpl_vertex *site_vertex;
3153 uint32_t component_count, i;
3154 struct kcctpl_multi_edge_list st_edge_list;
3155 struct ldb_dn *transports_dn;
3156 const char * const attrs[] = { "bridgeheadServerListBL", "name",
3157 "transportAddressAttribute", NULL };
3158
3159 connected = true;
3160
3161 status = kcctpl_color_vertices(ldb, graph, cross_ref, detect_failed_dcs,
3162 &found_failed_dcs);
3163 if (NT_STATUS_IS_ERR(status)) {
3164 DEBUG(1, (__location__ ": failed to color vertices: %s\n",
3165 nt_errstr(status)));
3166
3167 return status;
3168 }
3169
3170 tmp_ctx = talloc_new(mem_ctx);
3171 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
3172
3173 site = kcctpl_local_site(ldb, tmp_ctx);
3174 if (!site) {
3175 DEBUG(1, (__location__ ": failed to find our own local DC's "
3176 "site\n"));
3177
3178 talloc_free(tmp_ctx);
3179 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3180 }
3181
3182 site_guid = samdb_result_guid(site, "objectGUID");
3183
3184 site_vertex = kcctpl_find_vertex_by_guid(graph, site_guid);
3185 if (!site_vertex) {
3186 DEBUG(1, (__location__ ": failed to find vertex %s\n",
3187 GUID_string(tmp_ctx, &site_guid)));
3188
3189 talloc_free(tmp_ctx);
3190 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3191 }
3192
3193 if (site_vertex->color == WHITE) {
3194 *_found_failed_dcs = found_failed_dcs;
3195 *_connected = true;
3196 talloc_free(tmp_ctx);
3197 return NT_STATUS_OK;
3198 }
3199
3200 status = kcctpl_get_spanning_tree_edges(ldb, tmp_ctx, graph,
3201 &component_count,
3202 &st_edge_list);
3203 if (NT_STATUS_IS_ERR(status)) {
3204 DEBUG(1, (__location__ ": failed get spanning tree edges: %s\n",
3205 nt_errstr(status)));
3206
3207 talloc_free(tmp_ctx);
3208 return status;
3209 }
3210
3211 if (component_count > 1) {
3212 connected = false;
3213 }
3214
3215 partial_replica_okay = (site_vertex->color == BLACK);
3216
3217 transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
3218 if (!transports_dn) {
3219 DEBUG(1, (__location__ ": failed to find our own Inter-Site "
3220 "Transports DN\n"));
3221
3222 talloc_free(tmp_ctx);
3223 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3224 }
3225
3226 rodc = samdb_rodc(ldb);
3227
3228 for (i = 0; i < st_edge_list.count; i++) {
3229 struct kcctpl_multi_edge *edge;
3230 struct GUID other_site_id;
3231 struct kcctpl_vertex *other_site_vertex;
3232 struct ldb_result *res;
3233 int ret;
3234 struct ldb_message *transport, *r_bridgehead, *l_bridgehead;
3235 uint8_t schedule[84];
3236 uint32_t first_available, j, interval;
3237
3238 edge = &st_edge_list.data[i];
3239
3240 if (edge->directed && !GUID_equal(&edge->vertex_ids.data[1],
3241 &site_vertex->id)) {
3242 continue;
3243 }
3244
3245 if (GUID_equal(&edge->vertex_ids.data[0], &site_vertex->id)) {
3246 other_site_id = edge->vertex_ids.data[1];
3247 } else {
3248 other_site_id = edge->vertex_ids.data[0];
3249 }
3250
3251 other_site_vertex = kcctpl_find_vertex_by_guid(graph,
3252 other_site_id);
3253 if (!other_site_vertex) {
3254 DEBUG(1, (__location__ ": failed to find vertex %s\n",
3255 GUID_string(tmp_ctx, &other_site_id)));
3256
3257 talloc_free(tmp_ctx);
3258 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3259 }
3260
3261 ret = ldb_search(ldb, tmp_ctx, &res, transports_dn,
3262 LDB_SCOPE_ONELEVEL, attrs,
3263 "(&(objectClass=interSiteTransport)"
3264 "(objectGUID=%s))", GUID_string(tmp_ctx,
3265 &edge->type));
3266 if (ret != LDB_SUCCESS) {
3267 DEBUG(1, (__location__ ": failed to find "
3268 "interSiteTransport object %s: %s\n",
3269 GUID_string(tmp_ctx, &edge->type),
3270 ldb_strerror(ret)));
3271
3272 talloc_free(tmp_ctx);
3273 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3274 }
3275 if (res->count == 0) {
3276 DEBUG(1, (__location__ ": failed to find "
3277 "interSiteTransport object %s\n",
3278 GUID_string(tmp_ctx, &edge->type)));
3279
3280 talloc_free(tmp_ctx);
3281 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3282 }
3283 transport = res->msgs[0];
3284
3285 status = kcctpl_get_bridgehead_dc(ldb, tmp_ctx,
3286 other_site_vertex->id,
3287 cross_ref, transport,
3288 partial_replica_okay,
3289 detect_failed_dcs,
3290 &r_bridgehead);
3291 if (NT_STATUS_IS_ERR(status)) {
3292 DEBUG(1, (__location__ ": failed to get a bridgehead "
3293 "DC: %s\n", nt_errstr(status)));
3294
3295 talloc_free(tmp_ctx);
3296 return status;
3297 }
3298
3299 if (rodc) {
3300 /* TODO: l_bridgehad = nTDSDSA of local DC */
3301 } else {
3302 status = kcctpl_get_bridgehead_dc(ldb, tmp_ctx,
3303 site_vertex->id,
3304 cross_ref, transport,
3305 partial_replica_okay,
3306 detect_failed_dcs,
3307 &l_bridgehead);
3308 if (NT_STATUS_IS_ERR(status)) {
3309 DEBUG(1, (__location__ ": failed to get a "
3310 "bridgehead DC: %s\n",
3311 nt_errstr(status)));
3312
3313 talloc_free(tmp_ctx);
3314 return status;
3315 }
3316 }
3317
3318 ZERO_ARRAY(schedule);
3319 first_available = 84;
3320 interval = edge->repl_info.interval / 15;
3321 for (j = 0; j < 84; j++) {
3322 if (edge->repl_info.schedule[j] == 1) {
3323 first_available = j;
3324 break;
3325 }
3326 }
3327 for (j = first_available; j < 84; j += interval) {
3328 schedule[j] = 1;
3329 }
3330
3331 status = kcctpl_create_connection(ldb, mem_ctx, cross_ref,
3332 r_bridgehead, transport,
3333 l_bridgehead, edge->repl_info,
3334 schedule, detect_failed_dcs,
3335 partial_replica_okay,
3336 &keep_connections);
3337 if (NT_STATUS_IS_ERR(status)) {
3338 DEBUG(1, (__location__ ": failed to create a "
3339 "connection: %s\n", nt_errstr(status)));
3340
3341 talloc_free(tmp_ctx);
3342 return status;
3343 }
3344 }
3345
3346 *_found_failed_dcs = found_failed_dcs;
3347 *_connected = connected;
3348 talloc_free(tmp_ctx);
3349 return NT_STATUS_OK;
3350 }
3351
3352 /**
3353 * computes an NC replica graph for each NC replica that "should be present" on
3354 * the local DC or "is present" on any DC in the same site as the local DC. for
3355 * each edge directed to an NC replica on such a DC from an NC replica on a DC
3356 * in another site, the KCC creates and nTDSConnection object to imply that edge
3357 * if one does not already exist.
3358 */
3359 static NTSTATUS kcctpl_create_intersite_connections(struct ldb_context *ldb,
3360 TALLOC_CTX *mem_ctx,
3361 struct GUID_list *_keep_connections,
3362 bool *_all_connected)
3363 {
3364 struct GUID_list keep_connections;
3365 bool all_connected;
3366 TALLOC_CTX *tmp_ctx;
3367 struct ldb_dn *partitions_dn;
3368 struct ldb_result *res;
3369 const char * const attrs[] = { "enabled", "systemFlags", "nCName",
3370 NULL };
3371 int ret;
3372 unsigned int i;
3373
3374 all_connected = true;
3375
3376 ZERO_STRUCT(keep_connections);
3377
3378 tmp_ctx = talloc_new(mem_ctx);
3379 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
3380
3381 partitions_dn = samdb_partitions_dn(ldb, tmp_ctx);
3382 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(partitions_dn, tmp_ctx);
3383
3384 ret = ldb_search(ldb, tmp_ctx, &res, partitions_dn, LDB_SCOPE_ONELEVEL,
3385 attrs, "objectClass=crossRef");
3386 if (ret != LDB_SUCCESS) {
3387 DEBUG(1, (__location__ ": failed to find crossRef objects: "
3388 "%s\n", ldb_strerror(ret)));
3389
3390 talloc_free(tmp_ctx);
3391 return NT_STATUS_INTERNAL_DB_CORRUPTION;
3392 }
3393
3394 for (i = 0; i < res->count; i++) {
3395 struct ldb_message *cross_ref;
3396 unsigned int cr_enabled;
3397 int64_t cr_flags;
3398 struct kcctpl_graph *graph;
3399 bool found_failed_dc, connected;
3400 NTSTATUS status;
3401
3402 cross_ref = res->msgs[i];
3403 cr_enabled = samdb_result_uint(cross_ref, "enabled", -1);
3404 cr_flags = samdb_result_int64(cross_ref, "systemFlags", 0);
3405 if ((cr_enabled == 0) || !(cr_flags & FLAG_CR_NTDS_NC)) {
3406 continue;
3407 }
3408
3409 status = kcctpl_setup_graph(ldb, tmp_ctx, &graph);
3410 if (NT_STATUS_IS_ERR(status)) {
3411 DEBUG(1, (__location__ ": failed to create a graph: "
3412 "%s\n", nt_errstr(status)));
3413
3414 talloc_free(tmp_ctx);
3415 return status;
3416 }
3417
3418 status = kcctpl_create_connections(ldb, mem_ctx, graph,
3419 cross_ref, true,
3420 keep_connections,
3421 &found_failed_dc,
3422 &connected);
3423 if (NT_STATUS_IS_ERR(status)) {
3424 DEBUG(1, (__location__ ": failed to create "
3425 "connections: %s\n", nt_errstr(status)));
3426
3427 talloc_free(tmp_ctx);
3428 return status;
3429 }
3430
3431 if (!connected) {
3432 all_connected = false;
3433
3434 if (found_failed_dc) {
3435 status = kcctpl_create_connections(ldb, mem_ctx,
3436 graph,
3437 cross_ref,
3438 true,
3439 keep_connections,
3440 &found_failed_dc,
3441 &connected);
3442 if (NT_STATUS_IS_ERR(status)) {
3443 DEBUG(1, (__location__ ": failed to "
3444 "create connections: %s\n",
3445 nt_errstr(status)));
3446
3447 talloc_free(tmp_ctx);
3448 return status;
3449 }
3450 }
3451 }
3452 }
3453
3454 *_keep_connections = keep_connections;
3455 *_all_connected = all_connected;
3456 talloc_free(tmp_ctx);
3457 return NT_STATUS_OK;
3458 }
3459
3460 NTSTATUS kcctpl_test(struct ldb_context *ldb)
3461 {
3462 NTSTATUS status;
3463 TALLOC_CTX *tmp_ctx = talloc_new(ldb);
3464 struct GUID_list keep;
3465 bool all_connected;
3466
3467 DEBUG(0, ("Testing kcctpl_create_intersite_connections\n"));
3468 status = kcctpl_create_intersite_connections(ldb, tmp_ctx, &keep,
3469 &all_connected);
3470 DEBUG(4, ("%s\n", nt_errstr(status)));
3471 if (NT_STATUS_IS_OK(status)) {
3472 uint32_t i;
3473
3474 DEBUG(4, ("all_connected=%d, %d GUIDs returned\n",
3475 all_connected, keep.count));
3476
3477 for (i = 0; i < keep.count; i++) {
3478 DEBUG(4, ("GUID %d: %s\n", i + 1,
3479 GUID_string(tmp_ctx, &keep.data[i])));
3480 }
3481 }
3482
3483 talloc_free(tmp_ctx);
3484 return status;
3485 }
reg import