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