source: trunk/server/source4/dsdb/kcc/kcc_topology.c

Last change on this file was 745, checked in by Silvan Scherrer, 13 years ago

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