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