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