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