Remove a number of NT_STATUS_HAVE_NO_MEMORY_AND_FREE macros from the codebase.
[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         if (graph->vertices.data == NULL) {
509                 TALLOC_FREE(graph);
510                 return NT_STATUS_NO_MEMORY;
511         }
512
513         TYPESAFE_QSORT(guids.data, guids.count, GUID_compare);
514
515         for (i = 0; i < guids.count; i++) {
516                 graph->vertices.data[i].id = guids.data[i];
517         }
518
519         *_graph = graph;
520         return NT_STATUS_OK;
521 }
522
523 /**
524  * create a kcctpl_multi_edge instance.
525  */
526 static NTSTATUS kcctpl_create_edge(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
527                                    struct GUID type,
528                                    struct ldb_message *site_link,
529                                    struct kcctpl_multi_edge **_edge)
530 {
531         struct kcctpl_multi_edge *edge;
532         TALLOC_CTX *tmp_ctx;
533         struct ldb_dn *sites_dn;
534         struct ldb_result *res;
535         const char * const attrs[] = { "siteList", NULL };
536         int ret;
537         struct ldb_message_element *el;
538         unsigned int i;
539         struct ldb_val val;
540
541         tmp_ctx = talloc_new(mem_ctx);
542         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
543
544         edge = talloc_zero(tmp_ctx, struct kcctpl_multi_edge);
545         if (edge == NULL) {
546                 TALLOC_FREE(tmp_ctx);
547                 return NT_STATUS_NO_MEMORY;
548         }
549
550         edge->id = samdb_result_guid(site_link, "objectGUID");
551
552         sites_dn = samdb_sites_dn(ldb, tmp_ctx);
553         if (!sites_dn) {
554                 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
555
556                 talloc_free(tmp_ctx);
557                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
558         }
559
560         ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE, attrs,
561                          "objectGUID=%s", GUID_string(tmp_ctx, &edge->id));
562         if (ret != LDB_SUCCESS) {
563                 DEBUG(1, (__location__ ": failed to find siteLink object %s: "
564                           "%s\n", GUID_string(tmp_ctx, &edge->id),
565                           ldb_strerror(ret)));
566
567                 talloc_free(tmp_ctx);
568                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
569         }
570         if (res->count == 0) {
571                 DEBUG(1, (__location__ ": failed to find siteLink object %s\n",
572                           GUID_string(tmp_ctx, &edge->id)));
573
574                 talloc_free(tmp_ctx);
575                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
576         }
577
578         el = ldb_msg_find_element(res->msgs[0], "siteList");
579         if (!el) {
580                 DEBUG(1, (__location__ ": failed to find siteList attribute of "
581                           "object %s\n",
582                           ldb_dn_get_linearized(res->msgs[0]->dn)));
583
584                 talloc_free(tmp_ctx);
585                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
586         }
587
588         edge->vertex_ids.data = talloc_array(edge, struct GUID, el->num_values);
589         if (edge->vertex_ids.data == NULL) {
590                 TALLOC_FREE(tmp_ctx);
591                 return NT_STATUS_NO_MEMORY;
592         }
593         edge->vertex_ids.count = el->num_values;
594
595         for (i = 0; i < el->num_values; i++) {
596                 struct ldb_dn *dn;
597                 struct GUID guid;
598
599                 val = el->values[i];
600                 dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
601                 if (!dn) {
602                         DEBUG(1, (__location__ ": failed to read a DN from "
603                                   "siteList attribute of %s\n",
604                                   ldb_dn_get_linearized(res->msgs[0]->dn)));
605
606                         talloc_free(tmp_ctx);
607                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
608                 }
609                 ret = dsdb_find_guid_by_dn(ldb, dn, &guid);
610                 if (ret != LDB_SUCCESS) {
611                         DEBUG(1, (__location__ ": failed to find objectGUID "
612                                   "for object %s: %s\n",
613                                   ldb_dn_get_linearized(dn),
614                                   ldb_strerror(ret)));
615
616                         talloc_free(tmp_ctx);
617                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
618                 }
619
620                 edge->vertex_ids.data[i] = guid;
621         }
622
623         edge->repl_info.cost = ldb_msg_find_attr_as_int64(site_link, "cost", 0);
624         edge->repl_info.options = ldb_msg_find_attr_as_uint(site_link, "options", 0);
625         edge->repl_info.interval = ldb_msg_find_attr_as_int64(site_link,
626                                                       "replInterval", 0);
627         /* TODO: edge->repl_info.schedule = site_link!schedule */
628         edge->type = type;
629         edge->directed = false;
630
631         *_edge = talloc_steal(mem_ctx, edge);
632         talloc_free(tmp_ctx);
633         return NT_STATUS_OK;
634 }
635
636 /**
637  * create a kcctpl_multi_edge_set instance containing edges for all siteLink
638  * objects.
639  */
640 static NTSTATUS kcctpl_create_auto_edge_set(struct kcctpl_graph *graph,
641                                             struct GUID type,
642                                             struct ldb_result *res_site_link,
643                                             struct kcctpl_multi_edge_set **_set)
644 {
645         struct kcctpl_multi_edge_set *set;
646         TALLOC_CTX *tmp_ctx;
647         uint32_t i;
648
649         tmp_ctx = talloc_new(graph);
650         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
651
652         set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
653         if (set == NULL) {
654                 TALLOC_FREE(tmp_ctx);
655                 return NT_STATUS_NO_MEMORY;
656         }
657
658         for (i = 0; i < res_site_link->count; i++) {
659                 struct GUID site_link_guid;
660                 struct kcctpl_multi_edge *edge;
661
662                 site_link_guid = samdb_result_guid(res_site_link->msgs[i],
663                                                    "objectGUID");
664                 edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
665                 if (!edge) {
666                         DEBUG(1, (__location__ ": failed to find a graph edge "
667                                   "with ID=%s\n",
668                                   GUID_string(tmp_ctx, &site_link_guid)));
669
670                         talloc_free(tmp_ctx);
671                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
672                 }
673
674                 if (GUID_equal(&edge->type, &type)) {
675                         struct GUID *new_data;
676
677                         new_data = talloc_realloc(set, set->edge_ids.data,
678                                                   struct GUID,
679                                                   set->edge_ids.count + 1);
680                         if (new_data == NULL) {
681                                 TALLOC_FREE(tmp_ctx);
682                                 return NT_STATUS_NO_MEMORY;
683                         }
684                         new_data[set->edge_ids.count] = site_link_guid;
685                         set->edge_ids.data = new_data;
686                         set->edge_ids.count++;
687                 }
688         }
689
690         *_set = talloc_steal(graph, set);
691         return NT_STATUS_OK;
692 }
693
694 /**
695  * create a kcctpl_multi_edge_set instance.
696  */
697 static NTSTATUS kcctpl_create_edge_set(struct ldb_context *ldb,
698                                        struct kcctpl_graph *graph,
699                                        struct GUID type,
700                                        struct ldb_message *bridge,
701                                        struct kcctpl_multi_edge_set **_set)
702 {
703         struct kcctpl_multi_edge_set *set;
704         TALLOC_CTX *tmp_ctx;
705         struct ldb_message_element *el;
706         unsigned int i;
707
708         tmp_ctx = talloc_new(ldb);
709         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
710
711         set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
712         if (set == NULL) {
713                 TALLOC_FREE(tmp_ctx);
714                 return NT_STATUS_NO_MEMORY;
715         }
716
717         set->id = samdb_result_guid(bridge, "objectGUID");
718
719         el = ldb_msg_find_element(bridge, "siteLinkList");
720         if (!el) {
721                 DEBUG(1, (__location__ ": failed to find siteLinkList "
722                           "attribute of object %s\n",
723                           ldb_dn_get_linearized(bridge->dn)));
724
725                 talloc_free(tmp_ctx);
726                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
727         }
728         for (i = 0; i < el->num_values; i++) {
729                 struct ldb_val val;
730                 struct ldb_dn *dn;
731                 struct GUID site_link_guid;
732                 int ret;
733                 struct kcctpl_multi_edge *edge;
734
735                 val = el->values[i];
736                 dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
737                 if (!dn) {
738                         DEBUG(1, (__location__ ": failed to read a DN from "
739                                   "siteList attribute of %s\n",
740                                   ldb_dn_get_linearized(bridge->dn)));
741
742                         talloc_free(tmp_ctx);
743                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
744                 }
745
746                 ret = dsdb_find_guid_by_dn(ldb, dn, &site_link_guid);
747                 if (ret != LDB_SUCCESS) {
748                         DEBUG(1, (__location__ ": failed to find objectGUID "
749                                   "for object %s: %s\n",
750                                   ldb_dn_get_linearized(dn),
751                                   ldb_strerror(ret)));
752
753                         talloc_free(tmp_ctx);
754                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
755                 }
756
757                 edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
758                 if (!edge) {
759                         DEBUG(1, (__location__ ": failed to find a graph edge "
760                                   "with ID=%s\n",
761                                   GUID_string(tmp_ctx, &site_link_guid)));
762
763                         talloc_free(tmp_ctx);
764                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
765                 }
766
767                 if (GUID_equal(&edge->type, &type)) {
768                         struct GUID *new_data;
769
770                         new_data = talloc_realloc(set, set->edge_ids.data,
771                                                   struct GUID,
772                                                   set->edge_ids.count + 1);
773                         if (new_data == NULL) {
774                                 TALLOC_FREE(tmp_ctx);
775                                 return NT_STATUS_NO_MEMORY;
776                         }
777                         new_data[set->edge_ids.count] = site_link_guid;
778                         set->edge_ids.data = new_data;
779                         set->edge_ids.count++;
780                 }
781         }
782
783         *_set = talloc_steal(graph, set);
784         talloc_free(tmp_ctx);
785         return NT_STATUS_OK;
786 }
787
788 /**
789  * set up a kcctpl_graph, populated with a kcctpl_vertex for each site object, a
790  * kcctpl_multi_edge for each siteLink object, and a kcctpl_multi_edge_set for
791  * each siteLinkBridge object (or implied siteLinkBridge).
792  */
793 static NTSTATUS kcctpl_setup_graph(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
794                                    struct kcctpl_graph **_graph)
795 {
796         struct kcctpl_graph *graph;
797         struct ldb_dn *sites_dn, *transports_dn;
798         TALLOC_CTX *tmp_ctx;
799         struct ldb_result *res;
800         const char * const transport_attrs[] = { "objectGUID", NULL };
801         const char * const site_attrs[] = { "objectGUID", "options", NULL };
802         const char * const attrs[] = { "objectGUID", "cost", "options",
803                                        "replInterval", "schedule", NULL };
804         const char * const site_link_bridge_attrs[] = { "objectGUID",
805                                                         "siteLinkList",
806                                                         NULL };
807         int ret;
808         struct GUID_list vertex_ids;
809         unsigned int i;
810         NTSTATUS status;
811         struct ldb_message *site;
812         uint32_t site_opts;
813
814         tmp_ctx = talloc_new(mem_ctx);
815         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
816
817         sites_dn = samdb_sites_dn(ldb, tmp_ctx);
818         if (!sites_dn) {
819                 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
820
821                 talloc_free(tmp_ctx);
822                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
823         }
824
825         ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE,
826                          site_attrs, "objectClass=site");
827         if (ret != LDB_SUCCESS) {
828                 DEBUG(1, (__location__ ": failed to find site objects under "
829                           "%s: %s\n", ldb_dn_get_linearized(sites_dn),
830                           ldb_strerror(ret)));
831
832                 talloc_free(tmp_ctx);
833                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
834         }
835
836         ZERO_STRUCT(vertex_ids);
837         for (i = 0; i < res->count; i++) {
838                 struct GUID guid, *new_data;
839
840                 guid = samdb_result_guid(res->msgs[i], "objectGUID");
841
842                 new_data = talloc_realloc(tmp_ctx, vertex_ids.data, struct GUID,
843                                           vertex_ids.count + 1);
844                 if (new_data == NULL) {
845                         TALLOC_FREE(tmp_ctx);
846                         return NT_STATUS_NO_MEMORY;
847                 }
848                 new_data[vertex_ids.count] = guid;
849                 vertex_ids.data = new_data;
850                 vertex_ids.count++;
851         }
852
853         status = kcctpl_create_graph(tmp_ctx, vertex_ids, &graph);
854         if (NT_STATUS_IS_ERR(status)) {
855                 DEBUG(1, (__location__ ": failed to create graph: %s\n",
856                           nt_errstr(status)));
857
858                 talloc_free(tmp_ctx);
859                 return status;
860         }
861
862         site = kcctpl_local_site(ldb, tmp_ctx);
863         if (!site) {
864                 DEBUG(1, (__location__ ": failed to find our own local DC's "
865                           "site\n"));
866
867                 talloc_free(tmp_ctx);
868                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
869         }
870         site_opts = ldb_msg_find_attr_as_uint(site, "options", 0);
871
872         transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
873         if (!transports_dn) {
874                 DEBUG(1, (__location__ ": failed to find our own Inter-Site "
875                           "Transports DN\n"));
876
877                 talloc_free(tmp_ctx);
878                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
879         }
880
881         ret = ldb_search(ldb, tmp_ctx, &res, transports_dn, LDB_SCOPE_ONELEVEL,
882                         transport_attrs, "objectClass=interSiteTransport");
883         if (ret != LDB_SUCCESS) {
884                 DEBUG(1, (__location__ ": failed to find interSiteTransport "
885                           "objects under %s: %s\n",
886                           ldb_dn_get_linearized(transports_dn),
887                           ldb_strerror(ret)));
888
889                 talloc_free(tmp_ctx);
890                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
891         }
892
893         for (i = 0; i < res->count; i++) {
894                 struct ldb_message *transport;
895                 struct ldb_result *res_site_link;
896                 struct GUID transport_guid;
897                 unsigned int j;
898                 uint32_t transport_opts;
899
900                 transport = res->msgs[i];
901
902                 ret = ldb_search(ldb, tmp_ctx, &res_site_link, transport->dn,
903                                  LDB_SCOPE_SUBTREE, attrs,
904                                  "objectClass=siteLink");
905                 if (ret != LDB_SUCCESS) {
906                         DEBUG(1, (__location__ ": failed to find siteLink "
907                                   "objects under %s: %s\n",
908                                   ldb_dn_get_linearized(transport->dn),
909                                   ldb_strerror(ret)));
910
911                         talloc_free(tmp_ctx);
912                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
913                 }
914
915                 transport_guid = samdb_result_guid(transport, "objectGUID");
916                 for (j = 0; j < res_site_link->count; j++) {
917                         struct kcctpl_multi_edge *edge, *new_data;
918
919                         status = kcctpl_create_edge(ldb, graph, transport_guid,
920                                                     res_site_link->msgs[j],
921                                                     &edge);
922                         if (NT_STATUS_IS_ERR(status)) {
923                                 DEBUG(1, (__location__ ": failed to create "
924                                           "edge: %s\n", nt_errstr(status)));
925                                 talloc_free(tmp_ctx);
926                                 return status;
927                         }
928
929                         new_data = talloc_realloc(graph, graph->edges.data,
930                                                   struct kcctpl_multi_edge,
931                                                   graph->edges.count + 1);
932                         if (new_data == NULL) {
933                                 TALLOC_FREE(tmp_ctx);
934                                 return NT_STATUS_NO_MEMORY;
935                         }
936                         new_data[graph->edges.count] = *edge;
937                         graph->edges.data = new_data;
938                         graph->edges.count++;
939                 }
940
941                 transport_opts = ldb_msg_find_attr_as_uint(transport, "options", 0);
942                 if (!(transport_opts & NTDSTRANSPORT_OPT_BRIDGES_REQUIRED) &&
943                     !(site_opts & NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED)) {
944                         struct kcctpl_multi_edge_set *edge_set, *new_data;
945
946                         status = kcctpl_create_auto_edge_set(graph,
947                                                              transport_guid,
948                                                              res_site_link,
949                                                              &edge_set);
950                         if (NT_STATUS_IS_ERR(status)) {
951                                 DEBUG(1, (__location__ ": failed to create "
952                                           "edge set: %s\n", nt_errstr(status)));
953                                 talloc_free(tmp_ctx);
954                                 return status;
955                         }
956
957                         new_data = talloc_realloc(graph, graph->edge_sets.data,
958                                                   struct kcctpl_multi_edge_set,
959                                                   graph->edge_sets.count + 1);
960                         if (new_data == NULL) {
961                                 TALLOC_FREE(tmp_ctx);
962                                 return NT_STATUS_NO_MEMORY;
963                         }
964                         new_data[graph->edge_sets.count] = *edge_set;
965                         graph->edge_sets.data = new_data;
966                         graph->edge_sets.count++;
967                 } else {
968                         ret = ldb_search(ldb, tmp_ctx, &res_site_link,
969                                          transport->dn, LDB_SCOPE_SUBTREE,
970                                          site_link_bridge_attrs,
971                                          "objectClass=siteLinkBridge");
972                         if (ret != LDB_SUCCESS) {
973                                 DEBUG(1, (__location__ ": failed to find "
974                                           "siteLinkBridge objects under %s: "
975                                           "%s\n",
976                                           ldb_dn_get_linearized(transport->dn),
977                                           ldb_strerror(ret)));
978
979                                 talloc_free(tmp_ctx);
980                                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
981                         }
982
983                         for (j = 0; j < res_site_link->count; j++) {
984                                 struct ldb_message *bridge;
985                                 struct kcctpl_multi_edge_set *edge_set,
986                                                              *new_data;
987
988                                 bridge = res_site_link->msgs[j];
989                                 status = kcctpl_create_edge_set(ldb, graph,
990                                                                 transport_guid,
991                                                                 bridge,
992                                                                 &edge_set);
993                                 if (NT_STATUS_IS_ERR(status)) {
994                                         DEBUG(1, (__location__ ": failed to "
995                                                   "create edge set: %s\n",
996                                                   nt_errstr(status)));
997
998                                         talloc_free(tmp_ctx);
999                                         return status;
1000                                 }
1001
1002                                 new_data = talloc_realloc(graph,
1003                                                           graph->edge_sets.data,
1004                                                           struct kcctpl_multi_edge_set,
1005                                                           graph->edge_sets.count + 1);
1006                                 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
1007                                                                   tmp_ctx);
1008                                 new_data[graph->edge_sets.count] = *edge_set;
1009                                 graph->edge_sets.data = new_data;
1010                                 graph->edge_sets.count++;
1011                         }
1012                 }
1013         }
1014
1015         *_graph = talloc_steal(mem_ctx, graph);
1016         talloc_free(tmp_ctx);
1017         return NT_STATUS_OK;
1018 }
1019
1020 /**
1021  * determine whether a given DC is known to be in a failed state.
1022  */
1023 static NTSTATUS kcctpl_bridgehead_dc_failed(struct ldb_context *ldb,
1024                                             struct GUID guid,
1025                                             bool detect_failed_dcs,
1026                                             bool *_failed)
1027 {
1028         TALLOC_CTX *tmp_ctx;
1029         struct ldb_dn *settings_dn;
1030         struct ldb_result *res;
1031         const char * const attrs[] = { "options", NULL };
1032         int ret;
1033         struct ldb_message *settings;
1034         uint32_t settings_opts;
1035         bool failed;
1036
1037         tmp_ctx = talloc_new(ldb);
1038         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1039
1040         settings_dn = samdb_ntds_settings_dn(ldb, tmp_ctx);
1041         if (!settings_dn) {
1042                 DEBUG(1, (__location__ ": failed to find our own NTDS Settings "
1043                           "DN\n"));
1044                 talloc_free(tmp_ctx);
1045                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1046         }
1047
1048         ret = ldb_search(ldb, tmp_ctx, &res, settings_dn, LDB_SCOPE_BASE, attrs,
1049                         "objectClass=nTDSSiteSettings");
1050         if (ret != LDB_SUCCESS) {
1051                 DEBUG(1, (__location__ ": failed to find site settings object "
1052                           "%s: %s\n", ldb_dn_get_linearized(settings_dn),
1053                           ldb_strerror(ret)));
1054                 talloc_free(tmp_ctx);
1055                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1056         }
1057         if (res->count == 0) {
1058                 DEBUG(1, ("failed to find site settings object %s\n",
1059                           ldb_dn_get_linearized(settings_dn)));
1060                 talloc_free(tmp_ctx);
1061                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1062         }
1063
1064         settings = res->msgs[0];
1065
1066         settings_opts = ldb_msg_find_attr_as_uint(settings, "options", 0);
1067         if (settings_opts & NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED) {
1068                 failed = false;
1069         } else if (true) { /* TODO: how to get kCCFailedLinks and
1070                               kCCFailedConnections? */
1071                 failed = true;
1072         } else {
1073                 failed = detect_failed_dcs;
1074         }
1075
1076         *_failed = failed;
1077         talloc_free(tmp_ctx);
1078         return NT_STATUS_OK;
1079 }
1080
1081 /**
1082  * get all bridgehead DCs satisfying the given criteria.
1083  */
1084 static NTSTATUS kcctpl_get_all_bridgehead_dcs(struct kccsrv_service *service,
1085                                               TALLOC_CTX *mem_ctx,
1086                                               struct GUID site_guid,
1087                                               struct ldb_message *cross_ref,
1088                                               struct ldb_message *transport,
1089                                               bool partial_replica_okay,
1090                                               bool detect_failed_dcs,
1091                                               struct message_list *_bridgeheads)
1092 {
1093         struct message_list bridgeheads, all_dcs_in_site;
1094         TALLOC_CTX *tmp_ctx;
1095         struct ldb_result *res;
1096         struct ldb_dn *sites_dn, *schemas_dn;
1097         const char * const attrs[] = { "options", NULL };
1098         int ret;
1099         struct ldb_message *site, *schema;
1100         const char * const dc_attrs[] = { "objectGUID", "options", NULL };
1101         struct ldb_message_element *el;
1102         unsigned int i;
1103         const char *transport_name, *transport_address_attr;
1104         uint32_t site_opts;
1105
1106         ZERO_STRUCT(bridgeheads);
1107
1108         tmp_ctx = talloc_new(mem_ctx);
1109         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1110
1111         sites_dn = samdb_sites_dn(service->samdb, tmp_ctx);
1112         if (!sites_dn) {
1113                 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
1114
1115                 talloc_free(tmp_ctx);
1116                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1117         }
1118
1119         ret = ldb_search(service->samdb, tmp_ctx, &res, sites_dn, LDB_SCOPE_ONELEVEL,
1120                          attrs, "(&(objectClass=site)(objectGUID=%s))",
1121                          GUID_string(tmp_ctx, &site_guid));
1122         if (ret != LDB_SUCCESS) {
1123                 DEBUG(1, (__location__ ": failed to find site object %s: %s\n",
1124                           GUID_string(tmp_ctx, &site_guid),
1125                           ldb_strerror(ret)));
1126
1127                 talloc_free(tmp_ctx);
1128                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1129         }
1130         if (res->count == 0) {
1131                 DEBUG(1, (__location__ ": failed to find site object %s\n",
1132                           GUID_string(tmp_ctx, &site_guid)));
1133
1134                 talloc_free(tmp_ctx);
1135                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1136         }
1137         site = res->msgs[0];
1138
1139         schemas_dn = ldb_get_schema_basedn(service->samdb);
1140         if (!schemas_dn) {
1141                 DEBUG(1, (__location__ ": failed to find our own Schemas DN\n"));
1142
1143                 talloc_free(tmp_ctx);
1144                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1145         }
1146
1147         ret = ldb_search(service->samdb, tmp_ctx, &res, schemas_dn, LDB_SCOPE_SUBTREE,
1148                          NULL,
1149                         "(&(lDAPDisplayName=nTDSDSA)(objectClass=classSchema))");
1150         if (ret != LDB_SUCCESS) {
1151                 DEBUG(1, (__location__ ": failed to find classSchema object :"
1152                           "%s\n", ldb_strerror(ret)));
1153
1154                 talloc_free(tmp_ctx);
1155                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1156         }
1157         if (res->count == 0) {
1158                 DEBUG(1, (__location__ ": failed to find classSchema "
1159                           "object\n"));
1160
1161                 talloc_free(tmp_ctx);
1162                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1163         }
1164         schema = res->msgs[0];
1165
1166         ZERO_STRUCT(all_dcs_in_site);
1167
1168         ret = ldb_search(service->samdb, tmp_ctx, &res, site->dn, LDB_SCOPE_SUBTREE,
1169                         dc_attrs, "objectCategory=%s",
1170                         ldb_dn_get_linearized(schema->dn));
1171         if (ret != LDB_SUCCESS) {
1172                 DEBUG(1, (__location__ ": failed to find DCs objects :%s\n",
1173                           ldb_strerror(ret)));
1174
1175                 talloc_free(tmp_ctx);
1176                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1177         }
1178
1179         el = ldb_msg_find_element(transport, "bridgeheadServerListBL");
1180
1181         transport_name = ldb_msg_find_attr_as_string(transport, "name", NULL);
1182         if (!transport_name) {
1183                 DEBUG(1, (__location__ ": failed to find name attribute of "
1184                           "object %s\n", ldb_dn_get_linearized(transport->dn)));
1185
1186                 talloc_free(tmp_ctx);
1187                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1188         }
1189
1190         transport_address_attr = ldb_msg_find_attr_as_string(transport,
1191                                                      "transportAddressAttribute",
1192                                                      NULL);
1193         if (!transport_address_attr) {
1194                 DEBUG(1, (__location__ ": failed to find "
1195                           "transportAddressAttribute attribute of object %s\n",
1196                           ldb_dn_get_linearized(transport->dn)));
1197
1198                 talloc_free(tmp_ctx);
1199                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1200         }
1201
1202         site_opts = ldb_msg_find_attr_as_uint(site, "options", 0);
1203
1204         for (i = 0; i < res->count; i++) {
1205                 struct ldb_message *dc, *new_data;
1206                 struct ldb_dn *parent_dn;
1207                 uint64_t behavior_version;
1208                 const char *dc_transport_address;
1209                 struct ldb_result *parent_res;
1210                 const char *parent_attrs[] = { transport_address_attr, NULL };
1211                 NTSTATUS status;
1212                 struct GUID dc_guid;
1213                 bool failed;
1214
1215                 dc = res->msgs[i];
1216
1217                 parent_dn = ldb_dn_get_parent(tmp_ctx, dc->dn);
1218                 if (!parent_dn) {
1219                         DEBUG(1, (__location__ ": failed to get parent DN of "
1220                                   "%s\n", ldb_dn_get_linearized(dc->dn)));
1221
1222                         talloc_free(tmp_ctx);
1223                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1224                 }
1225
1226                 if (el && (el->num_values >= 1)) {
1227                         bool contains;
1228                         unsigned int j;
1229
1230                         contains = false;
1231
1232                         for (j = 0; j < el->num_values; j++) {
1233                                 struct ldb_val val;
1234                                 struct ldb_dn *dn;
1235
1236                                 val = el->values[j];
1237
1238                                 dn = ldb_dn_from_ldb_val(tmp_ctx, service->samdb, &val);
1239                                 if (!dn) {
1240                                         DEBUG(1, (__location__ ": failed to read a DN "
1241                                                   "from bridgeheadServerListBL "
1242                                                   "attribute of %s\n",
1243                                                   ldb_dn_get_linearized(transport->dn)));
1244
1245                                         talloc_free(tmp_ctx);
1246                                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1247                                 }
1248
1249                                 if (ldb_dn_compare(dn, parent_dn) == 0) {
1250                                         contains = true;
1251                                         break;
1252                                 }
1253                         }
1254
1255                         if (!contains) {
1256                                 continue;
1257                         }
1258                 }
1259
1260                 /* TODO: if dc is in the same site as the local DC */
1261                 if (true) {
1262                         /* TODO: if a replica of cr!nCName is not in the set of
1263                          * NC replicas that "should be present" on 'dc' */
1264                         /* TODO: a partial replica of the NC "should be
1265                            present" */
1266                         if (true || (true && !partial_replica_okay)) {
1267                                 continue;
1268                         }
1269                 } else {
1270                         /* TODO: if an NC replica of cr!nCName is not in the set
1271                          * of NC replicas that "are present" on 'dc' */
1272                         /* TODO: a partial replica of the NC "is present" */
1273                         if (true || (true && !partial_replica_okay)) {
1274                                 continue;
1275                         }
1276                 }
1277
1278                 behavior_version = ldb_msg_find_attr_as_int64(dc,
1279                                                       "msDS-Behavior-Version", 0);
1280                 /* TODO: cr!nCName corresponds to default NC */
1281                 if (service->am_rodc && true && behavior_version < DS_BEHAVIOR_WIN2008) {
1282                         continue;
1283                 }
1284
1285                 ret = ldb_search(service->samdb, tmp_ctx, &parent_res, parent_dn,
1286                                 LDB_SCOPE_BASE, parent_attrs , NULL);
1287
1288                 dc_transport_address = ldb_msg_find_attr_as_string(parent_res->msgs[0],
1289                                                            transport_address_attr,
1290                                                            NULL);
1291
1292                 if (strncmp(transport_name, "IP", 2) != 0 &&
1293                     dc_transport_address == NULL) {
1294                         continue;
1295                 }
1296
1297                 dc_guid = samdb_result_guid(dc, "objectGUID");
1298
1299                 status = kcctpl_bridgehead_dc_failed(service->samdb, dc_guid,
1300                                                      detect_failed_dcs,
1301                                                      &failed);
1302                 if (NT_STATUS_IS_ERR(status)) {
1303                         DEBUG(1, (__location__ ": failed to check if "
1304                                   "bridgehead DC has failed: %s\n",
1305                                   nt_errstr(status)));
1306
1307                         talloc_free(tmp_ctx);
1308                         return status;
1309                 }
1310
1311                 if (failed) {
1312                         continue;
1313                 }
1314
1315                 new_data = talloc_realloc(tmp_ctx, bridgeheads.data,
1316                                           struct ldb_message,
1317                                           bridgeheads.count + 1);
1318                 if (new_data == NULL) {
1319                         TALLOC_FREE(tmp_ctx);
1320                         return NT_STATUS_NO_MEMORY;
1321                 }
1322                 new_data[bridgeheads.count + 1] = *dc;
1323                 bridgeheads.data = new_data;
1324                 bridgeheads.count++;
1325         }
1326
1327         if (site_opts & NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED) {
1328                 qsort(bridgeheads.data, bridgeheads.count,
1329                       sizeof(struct ldb_message), kcctpl_sort_bridgeheads);
1330         } else {
1331                 kcctpl_shuffle_bridgeheads(bridgeheads);
1332         }
1333
1334         talloc_steal(mem_ctx, bridgeheads.data);
1335         *_bridgeheads = bridgeheads;
1336         talloc_free(tmp_ctx);
1337         return NT_STATUS_OK;
1338 }
1339
1340 /**
1341  * get a bridgehead DC.
1342  */
1343 static NTSTATUS kcctpl_get_bridgehead_dc(struct kccsrv_service *service,
1344                                          TALLOC_CTX *mem_ctx,
1345                                          struct GUID site_guid,
1346                                          struct ldb_message *cross_ref,
1347                                          struct ldb_message *transport,
1348                                          bool partial_replica_okay,
1349                                          bool detect_failed_dcs,
1350                                          struct ldb_message **_dsa)
1351 {
1352         struct message_list dsa_list;
1353         NTSTATUS status;
1354
1355         status = kcctpl_get_all_bridgehead_dcs(service, mem_ctx,
1356                                                site_guid, cross_ref, transport,
1357                                                partial_replica_okay,
1358                                                detect_failed_dcs, &dsa_list);
1359         if (NT_STATUS_IS_ERR(status)) {
1360                 DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
1361                           "%s\n", nt_errstr(status)));
1362                 return status;
1363         }
1364
1365         *_dsa = (dsa_list.count == 0) ? NULL : &dsa_list.data[0];
1366
1367         return NT_STATUS_OK;
1368 }
1369
1370 /*
1371  * color each vertex to indicate which kinds of NC replicas it contains.
1372  */
1373 static NTSTATUS kcctpl_color_vertices(struct kccsrv_service *service,
1374                                       struct kcctpl_graph *graph,
1375                                       struct ldb_message *cross_ref,
1376                                       bool detect_failed_dcs,
1377                                       bool *_found_failed_dcs)
1378 {
1379         TALLOC_CTX *tmp_ctx;
1380         struct ldb_dn *sites_dn;
1381         bool found_failed_dcs, partial_replica_okay;
1382         uint32_t i;
1383         struct ldb_message *site;
1384         struct ldb_result *res;
1385         int ret, cr_flags;
1386         struct GUID site_guid;
1387         struct kcctpl_vertex *site_vertex;
1388
1389         found_failed_dcs = false;
1390
1391         tmp_ctx = talloc_new(service);
1392         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1393
1394         sites_dn = samdb_sites_dn(service->samdb, tmp_ctx);
1395         if (!sites_dn) {
1396                 DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
1397
1398                 talloc_free(tmp_ctx);
1399                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1400         }
1401
1402         for (i = 0; i < graph->vertices.count; i++) {
1403                 struct kcctpl_vertex *vertex;
1404                 struct ldb_dn *nc_name;
1405                 /* TODO: set 'attrs' with its corresponding values */
1406                 const char * const attrs[] = { NULL };
1407
1408                 vertex = &graph->vertices.data[i];
1409
1410                 ret = ldb_search(service->samdb, tmp_ctx, &res, sites_dn,
1411                                  LDB_SCOPE_SUBTREE, attrs, "objectGUID=%s",
1412                                  GUID_string(tmp_ctx, &vertex->id));
1413                 if (ret != LDB_SUCCESS) {
1414                         DEBUG(1, (__location__ ": failed to find site object "
1415                                   "%s: %s\n", GUID_string(tmp_ctx, &vertex->id),
1416                                   ldb_strerror(ret)));
1417
1418                         talloc_free(tmp_ctx);
1419                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1420                 }
1421                 if (res->count == 0) {
1422                         DEBUG(1, (__location__ ": failed to find site object "
1423                                   "%s\n", GUID_string(tmp_ctx, &vertex->id)));
1424
1425                         talloc_free(tmp_ctx);
1426                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1427                 }
1428                 site = res->msgs[0];
1429
1430                 nc_name = samdb_result_dn(service->samdb, tmp_ctx, cross_ref,
1431                                           "nCName", NULL);
1432                 if (!nc_name) {
1433                         DEBUG(1, (__location__ ": failed to find nCName "
1434                                   "attribute of object %s\n",
1435                                   ldb_dn_get_linearized(cross_ref->dn)));
1436
1437                         talloc_free(tmp_ctx);
1438                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1439                 }
1440
1441                 if (true) { /* TODO: site contains 1+ DCs with full replicas of
1442                                'nc_name' */
1443                         vertex->color = RED;
1444                 } else if (true) { /* TODO: site contains 1+ partial replicas of
1445                                       'nc_name' */
1446                         vertex->color = BLACK;
1447                 } else {
1448                         vertex->color = WHITE;
1449                 }
1450         }
1451
1452         site = kcctpl_local_site(service->samdb, tmp_ctx);
1453         if (!site) {
1454                 DEBUG(1, (__location__ ": failed to find our own local DC's "
1455                           "site\n"));
1456
1457                 talloc_free(tmp_ctx);
1458                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1459         }
1460         site_guid = samdb_result_guid(site, "objectGUID");
1461
1462         site_vertex = kcctpl_find_vertex_by_guid(graph, site_guid);
1463         if (!site_vertex) {
1464                 DEBUG(1, (__location__ ": failed to find a vertex edge with "
1465                           "GUID=%s\n", GUID_string(tmp_ctx, &site_guid)));
1466
1467                 talloc_free(tmp_ctx);
1468                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1469         }
1470
1471         partial_replica_okay = (site_vertex->color == BLACK);
1472
1473         cr_flags = ldb_msg_find_attr_as_int64(cross_ref, "systemFlags", 0);
1474
1475         for (i = 0; i < graph->vertices.count; i++) {
1476                 struct kcctpl_vertex *vertex;
1477                 struct ldb_dn *transports_dn;
1478                 const char * const attrs[] = { "objectGUID", "name",
1479                                                "transportAddressAttribute",
1480                                                NULL };
1481                 unsigned int j;
1482
1483                 vertex = &graph->vertices.data[i];
1484
1485                 transports_dn = kcctpl_transports_dn(service->samdb, tmp_ctx);
1486                 if (!transports_dn) {
1487                         DEBUG(1, (__location__ ": failed to find our own "
1488                                   "Inter-Site Transports DN\n"));
1489
1490                         talloc_free(tmp_ctx);
1491                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1492                 }
1493
1494                 ret = ldb_search(service->samdb, tmp_ctx, &res, transports_dn,
1495                                  LDB_SCOPE_ONELEVEL, attrs,
1496                                  "objectClass=interSiteTransport");
1497                 if (ret != LDB_SUCCESS) {
1498                         DEBUG(1, (__location__ ": failed to find "
1499                                   "interSiteTransport objects under %s: %s\n",
1500                                   ldb_dn_get_linearized(transports_dn),
1501                                   ldb_strerror(ret)));
1502
1503                         talloc_free(tmp_ctx);
1504                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1505                 }
1506
1507                 for (j = 0; j < res->count; j++) {
1508                         struct ldb_message *transport, *bridgehead;
1509                         const char *transport_name;
1510                         struct GUID transport_guid, *new_data;
1511                         NTSTATUS status;
1512
1513                         transport = res->msgs[j];
1514
1515                         transport_name = ldb_msg_find_attr_as_string(transport,
1516                                                              "name", NULL);
1517                         if (!transport_name) {
1518                                 DEBUG(1, (__location__ ": failed to find name "
1519                                           "attribute of object %s\n",
1520                                           ldb_dn_get_linearized(transport->dn)));
1521
1522                                 talloc_free(tmp_ctx);
1523                                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1524                         }
1525
1526                         transport_guid = samdb_result_guid(transport,
1527                                                            "objectGUID");
1528
1529                         if (site_vertex->color == RED &&
1530                             strncmp(transport_name, "IP", 2) != 0 &&
1531                             (cr_flags & FLAG_CR_NTDS_DOMAIN)) {
1532                                 continue;
1533                         }
1534
1535                         if (!kcctpl_find_edge_by_vertex_guid(graph,
1536                                                              vertex->id)) {
1537                                 continue;
1538                         }
1539
1540                         status = kcctpl_get_bridgehead_dc(service, tmp_ctx,
1541                                                           site_vertex->id,
1542                                                           cross_ref, transport,
1543                                                           partial_replica_okay,
1544                                                           detect_failed_dcs,
1545                                                           &bridgehead);
1546                         if (NT_STATUS_IS_ERR(status)) {
1547                                 DEBUG(1, (__location__ ": failed to get a "
1548                                           "bridgehead DC: %s\n",
1549                                           nt_errstr(status)));
1550
1551                                 talloc_free(tmp_ctx);
1552                                 return status;
1553                         }
1554                         if (!bridgehead) {
1555                                 found_failed_dcs = true;
1556                                 continue;
1557                         }
1558
1559                         new_data = talloc_realloc(vertex,
1560                                                   vertex->accept_red_red.data,
1561                                                   struct GUID,
1562                                                   vertex->accept_red_red.count + 1);
1563                         if (new_data == NULL) {
1564                                 TALLOC_FREE(tmp_ctx);
1565                                 return NT_STATUS_NO_MEMORY;
1566                         }
1567                         new_data[vertex->accept_red_red.count + 1] = transport_guid;
1568                         vertex->accept_red_red.data = new_data;
1569                         vertex->accept_red_red.count++;
1570
1571                         new_data = talloc_realloc(vertex,
1572                                                   vertex->accept_black.data,
1573                                                   struct GUID,
1574                                                   vertex->accept_black.count + 1);
1575                         if (new_data == NULL) {
1576                                 TALLOC_FREE(tmp_ctx);
1577                                 return NT_STATUS_NO_MEMORY;
1578                         }
1579                         new_data[vertex->accept_black.count + 1] = transport_guid;
1580                         vertex->accept_black.data = new_data;
1581                         vertex->accept_black.count++;
1582                 }
1583         }
1584
1585         *_found_failed_dcs = found_failed_dcs;
1586         talloc_free(tmp_ctx);
1587         return NT_STATUS_OK;
1588 }
1589
1590 /**
1591  * setup the fields of the vertices that are relevant to Phase I (Dijkstra's
1592  * Algorithm). for each vertex, set up its cost, root vertex and component. this
1593  * defines the shortest-path forest structures.
1594  */
1595 static void kcctpl_setup_vertices(struct kcctpl_graph *graph)
1596 {
1597         uint32_t i;
1598
1599         for (i = 0; i < graph->vertices.count; i++) {
1600                 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
1601
1602                 if (vertex->color == WHITE) {
1603                         vertex->repl_info.cost = UINT32_MAX;
1604                         vertex->root_id = vertex->component_id = GUID_zero();
1605                 } else {
1606                         vertex->repl_info.cost = 0;
1607                         vertex->root_id = vertex->component_id = vertex->id;
1608                 }
1609
1610                 vertex->repl_info.interval = 0;
1611                 vertex->repl_info.options = 0xFFFFFFFF;
1612                 ZERO_STRUCT(vertex->repl_info.schedule);
1613                 vertex->demoted = false;
1614         }
1615 }
1616
1617 /**
1618  * demote one vertex if necessary.
1619  */
1620 static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex *vertex,
1621                                            struct GUID type)
1622 {
1623         if (vertex->color == WHITE) {
1624                 return;
1625         }
1626
1627         if (!kcctpl_guid_list_contains(vertex->accept_black, type) &&
1628             !kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
1629                 vertex->repl_info.cost = UINT32_MAX;
1630                 vertex->root_id = GUID_zero();
1631                 vertex->demoted = true;
1632         }
1633 }
1634
1635 /**
1636  * clear the demoted state of a vertex.
1637  */
1638 static void kcctpl_undemote_one_vertex(struct kcctpl_vertex *vertex)
1639 {
1640         if (vertex->color == WHITE) {
1641                 return;
1642         }
1643
1644         vertex->repl_info.cost = 0;
1645         vertex->root_id = vertex->id;
1646         vertex->demoted = false;
1647 }
1648
1649 /**
1650  * returns the id of the component containing 'vertex' by traversing the up-tree
1651  * implied by the component pointers.
1652  */
1653 static struct GUID kcctpl_get_component_id(struct kcctpl_graph *graph,
1654                                            struct kcctpl_vertex *vertex)
1655 {
1656         struct kcctpl_vertex *u;
1657         struct GUID root;
1658
1659         u = vertex;
1660         while (!GUID_equal(&u->component_id, &u->id)) {
1661                 u = kcctpl_find_vertex_by_guid(graph, u->component_id);
1662         }
1663
1664         root = u->id;
1665
1666         u = vertex;
1667         while (!GUID_equal(&u->component_id, &u->id)) {
1668                 struct kcctpl_vertex *w;
1669
1670                 w = kcctpl_find_vertex_by_guid(graph, u->component_id);
1671                 u->component_id = root;
1672                 u = w;
1673         }
1674
1675         return root;
1676 }
1677
1678 /**
1679  * copy all spanning tree edges from 'output_edges' that contain the vertex for
1680  * DCs in the local DC's site.
1681  */
1682 static NTSTATUS kcctpl_copy_output_edges(struct kccsrv_service *service,
1683                                          TALLOC_CTX *mem_ctx,
1684                                          struct kcctpl_graph *graph,
1685                                          struct kcctpl_multi_edge_list output_edges,
1686                                          struct kcctpl_multi_edge_list *_copy)
1687 {
1688         struct kcctpl_multi_edge_list copy;
1689         TALLOC_CTX *tmp_ctx;
1690         struct ldb_message *site;
1691         struct GUID site_guid;
1692         uint32_t i;
1693
1694         ZERO_STRUCT(copy);
1695
1696         tmp_ctx = talloc_new(service);
1697         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1698
1699         site = kcctpl_local_site(service->samdb, tmp_ctx);
1700         if (!site) {
1701                 DEBUG(1, (__location__ ": failed to find our own local DC's "
1702                           "site\n"));
1703
1704                 talloc_free(tmp_ctx);
1705                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
1706         }
1707         site_guid = samdb_result_guid(site, "objectGUID");
1708
1709         for (i = 0; i < output_edges.count; i++) {
1710                 struct kcctpl_multi_edge *edge;
1711                 struct kcctpl_vertex *vertex1, *vertex2;
1712
1713                 edge = &output_edges.data[i];
1714
1715                 vertex1 = kcctpl_find_vertex_by_guid(graph,
1716                                                      edge->vertex_ids.data[0]);
1717                 if (!vertex1) {
1718                         DEBUG(1, (__location__ ": failed to find vertex %s\n",
1719                                   GUID_string(tmp_ctx,
1720                                               &edge->vertex_ids.data[0])));
1721                         talloc_free(tmp_ctx);
1722                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1723                 }
1724
1725                 vertex2 = kcctpl_find_vertex_by_guid(graph,
1726                                                      edge->vertex_ids.data[1]);
1727                 if (!vertex2) {
1728                         DEBUG(1, (__location__ ": failed to find vertex %s\n",
1729                                   GUID_string(tmp_ctx,
1730                                               &edge->vertex_ids.data[1])));
1731                         talloc_free(tmp_ctx);
1732                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
1733                 }
1734
1735                 if (GUID_equal(&vertex1->id, &site_guid) ||
1736                     GUID_equal(&vertex2->id, &site_guid)) {
1737                         struct kcctpl_multi_edge *new_data;
1738
1739                         if ((vertex1->color == BLACK ||
1740                              vertex2->color == BLACK) &&
1741                             vertex1->dist_to_red != UINT32_MAX) {
1742
1743                                 edge->directed = true;
1744
1745                                 if (vertex2->dist_to_red <
1746                                     vertex1->dist_to_red) {
1747                                         struct GUID tmp;
1748
1749                                         tmp = edge->vertex_ids.data[0];
1750                                         edge->vertex_ids.data[0] = edge->vertex_ids.data[1];
1751                                         edge->vertex_ids.data[1] = tmp;
1752                                 }
1753                         }
1754
1755                         new_data = talloc_realloc(tmp_ctx, copy.data,
1756                                                   struct kcctpl_multi_edge,
1757                                                   copy.count + 1);
1758                         if (new_data == NULL) {
1759                                 TALLOC_FREE(tmp_ctx);
1760                                 return NT_STATUS_NO_MEMORY;
1761                         }
1762                         new_data[copy.count + 1] = *edge;
1763                         copy.data = new_data;
1764                         copy.count++;
1765                 }
1766         }
1767
1768         talloc_steal(mem_ctx, copy.data);
1769         talloc_free(tmp_ctx);
1770         *_copy = copy;
1771         return NT_STATUS_OK;
1772 }
1773
1774 /**
1775  * build the initial sequence for use with Dijkstra's algorithm. it will contain
1776  * the red and black vertices as root vertices, unless these vertices accept no
1777  * edges of the current 'type', or unless black vertices are not being
1778  * including.
1779  */
1780 static NTSTATUS kcctpl_setup_dijkstra(TALLOC_CTX *mem_ctx,
1781                                       struct kcctpl_graph *graph,
1782                                       struct GUID type, bool include_black,
1783                                       struct kcctpl_vertex_list *_vertices)
1784 {
1785         struct kcctpl_vertex_list vertices;
1786         uint32_t i;
1787
1788         kcctpl_setup_vertices(graph);
1789
1790         ZERO_STRUCT(vertices);
1791
1792         for (i = 0; i < graph->vertices.count; i++) {
1793                 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
1794
1795                 if (vertex->color == WHITE) {
1796                         continue;
1797                 }
1798
1799                 if ((vertex->color == BLACK && !include_black) ||
1800                     !kcctpl_guid_list_contains(vertex->accept_black, type) ||
1801                     !kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
1802                         vertex->repl_info.cost = UINT32_MAX;
1803                         vertex->root_id = GUID_zero();
1804                         vertex->demoted = true;
1805                 } else {
1806                         struct kcctpl_vertex *new_data;
1807
1808                         new_data = talloc_realloc(mem_ctx, vertices.data,
1809                                                   struct kcctpl_vertex,
1810                                                   vertices.count + 1);
1811                         NT_STATUS_HAVE_NO_MEMORY(new_data);
1812                         new_data[vertices.count] = *vertex;
1813                         vertices.data = new_data;
1814                         vertices.count++;
1815                 }
1816         }
1817
1818         *_vertices = vertices;
1819         return NT_STATUS_OK;
1820 }
1821
1822 /**
1823  * merge schedules, replication intervals, options and costs.
1824  */
1825 static bool kcctpl_combine_repl_info(struct kcctpl_graph *graph,
1826                                      struct kcctpl_repl_info *ria,
1827                                      struct kcctpl_repl_info *rib,
1828                                      struct kcctpl_repl_info *ric)
1829 {
1830         uint8_t schedule[84];
1831         bool is_available;
1832         uint32_t i;
1833         int32_t ric_cost;
1834
1835         is_available = false;
1836         for (i = 0; i < 84; i++) {
1837                 schedule[i] = ria->schedule[i] & rib->schedule[i];
1838
1839                 if (schedule[i] == 1) {
1840                         is_available = true;
1841                 }
1842         }
1843         if (!is_available) {
1844                 return false;
1845         }
1846
1847         ric_cost = ria->cost + rib->cost;
1848         ric->cost = (ric_cost < 0) ? UINT32_MAX : ric_cost;
1849
1850         ric->interval = MAX(ria->interval, rib->interval);
1851         ric->options = ria->options & rib->options;
1852         memcpy(&ric->schedule, &schedule, 84);
1853
1854         return true;
1855 }
1856
1857 /**
1858  * helper function for Dijkstra's algorithm. a new path has been found from a
1859  * root vertex to vertex 'vertex2'. this path is ('vertex1->root, ..., vertex1,
1860  * vertex2'). 'edge' is the edge connecting 'vertex1' and 'vertex2'. if this new
1861  * path is better (in this case cheaper, or has a longer schedule), update
1862  * 'vertex2' to use the new path.
1863  */
1864 static NTSTATUS kcctpl_try_new_path(TALLOC_CTX *mem_ctx,
1865                                     struct kcctpl_graph *graph,
1866                                     struct kcctpl_vertex_list vertices,
1867                                     struct kcctpl_vertex *vertex1,
1868                                     struct kcctpl_multi_edge *edge,
1869                                     struct kcctpl_vertex *vertex2)
1870 {
1871         struct kcctpl_repl_info new_repl_info;
1872         bool intersect;
1873         uint32_t i, new_duration, old_duration;
1874
1875         ZERO_STRUCT(new_repl_info);
1876
1877         intersect = kcctpl_combine_repl_info(graph, &vertex1->repl_info,
1878                                              &edge->repl_info, &new_repl_info);
1879
1880         if (new_repl_info.cost > vertex2->repl_info.cost) {
1881                 return NT_STATUS_OK;
1882         }
1883
1884         if (new_repl_info.cost < vertex2->repl_info.cost && !intersect) {
1885                 return NT_STATUS_OK;
1886         }
1887
1888         new_duration = old_duration = 0;
1889         for (i = 0; i < 84; i++) {
1890                 if (new_repl_info.schedule[i] == 1) {
1891                         new_duration++;
1892                 }
1893
1894                 if (vertex2->repl_info.schedule[i] == 1) {
1895                         old_duration++;
1896                 }
1897         }
1898
1899         if (new_repl_info.cost < vertex2->repl_info.cost ||
1900             new_duration > old_duration) {
1901                 struct kcctpl_vertex *new_data;
1902
1903                 vertex2->root_id = vertex1->root_id;
1904                 vertex2->component_id = vertex1->component_id;
1905                 vertex2->repl_info = new_repl_info;
1906
1907                 new_data = talloc_realloc(mem_ctx, vertices.data,
1908                                           struct kcctpl_vertex,
1909                                           vertices.count + 1);
1910                 NT_STATUS_HAVE_NO_MEMORY(new_data);
1911                 new_data[vertices.count + 1] = *vertex2;
1912                 vertices.data = new_data;
1913                 vertices.count++;
1914         }
1915
1916         return NT_STATUS_OK;
1917 }
1918
1919 /**
1920  * run Dijkstra's algorithm with the red (and possibly black) vertices as the
1921  * root vertices, and build up a shortest-path forest.
1922  */
1923 static NTSTATUS kcctpl_dijkstra(struct kcctpl_graph *graph, struct GUID type,
1924                                 bool include_black)
1925 {
1926         TALLOC_CTX *tmp_ctx;
1927         struct kcctpl_vertex_list vertices;
1928         NTSTATUS status;
1929
1930         tmp_ctx = talloc_new(graph);
1931         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1932
1933         status = kcctpl_setup_dijkstra(tmp_ctx, graph, type, include_black,
1934                                        &vertices);
1935         if (NT_STATUS_IS_ERR(status)) {
1936                 DEBUG(1, (__location__ ": failed to build the initial sequence "
1937                           "for Dijkstra's algorithm: %s\n", nt_errstr(status)));
1938
1939                 talloc_free(tmp_ctx);
1940                 return status;
1941         }
1942
1943         while (vertices.count > 0) {
1944                 uint32_t minimum_cost, minimum_index, i;
1945                 struct kcctpl_vertex *minimum_vertex, *new_data;
1946
1947                 minimum_cost = UINT32_MAX;
1948                 minimum_index = -1;
1949                 minimum_vertex = NULL;
1950                 for (i = 0; i < vertices.count; i++) {
1951                         struct kcctpl_vertex *vertex = &vertices.data[i];
1952
1953                         if (vertex->repl_info.cost < minimum_cost) {
1954                                 minimum_cost = vertex->repl_info.cost;
1955                                 minimum_vertex = vertex;
1956                                 minimum_index = i;
1957                         } else if (vertex->repl_info.cost == minimum_cost &&
1958                                    GUID_compare(&vertex->id,
1959                                                 &minimum_vertex->id) < 0) {
1960                                 minimum_vertex = vertex;
1961                                 minimum_index = i;
1962                         }
1963                 }
1964
1965                 if (minimum_index < vertices.count - 1) {
1966                         memcpy(&vertices.data[minimum_index + 1],
1967                                &vertices.data[minimum_index],
1968                                vertices.count - minimum_index - 1);
1969                 }
1970                 new_data = talloc_realloc(tmp_ctx, vertices.data,
1971                                           struct kcctpl_vertex,
1972                                           vertices.count - 1);
1973                 if (new_data == NULL) {
1974                         TALLOC_FREE(tmp_ctx);
1975                         return NT_STATUS_NO_MEMORY;
1976                 }
1977                 talloc_free(vertices.data);
1978                 vertices.data = new_data;
1979                 vertices.count--;
1980
1981                 for (i = 0; i < graph->edges.count; i++) {
1982                         struct kcctpl_multi_edge *edge = &graph->edges.data[i];
1983
1984                         if (kcctpl_guid_list_contains(minimum_vertex->edge_ids,
1985                                                       edge->id)) {
1986                                 uint32_t j;
1987
1988                                 for (j = 0; j < edge->vertex_ids.count; j++) {
1989                                         struct GUID vertex_id;
1990                                         struct kcctpl_vertex *vertex;
1991
1992                                         vertex_id = edge->vertex_ids.data[j];
1993                                         vertex = kcctpl_find_vertex_by_guid(graph,
1994                                                                             vertex_id);
1995                                         if (!vertex) {
1996                                                 DEBUG(1, (__location__
1997                                                           ": failed to find "
1998                                                           "vertex %s\n",
1999                                                           GUID_string(tmp_ctx,
2000                                                                       &vertex_id)));
2001
2002                                                 talloc_free(tmp_ctx);
2003                                                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2004                                         }
2005
2006                                         kcctpl_try_new_path(tmp_ctx, graph,
2007                                                             vertices,
2008                                                             minimum_vertex,
2009                                                             edge, vertex);
2010                                 }
2011                         }
2012                 }
2013         }
2014
2015         talloc_free(tmp_ctx);
2016         return NT_STATUS_OK;
2017 }
2018
2019 /**
2020  * add an edge to the list of edges that will be processed with Kruskal's. the
2021  * endpoints are in fact the root of the vertices to pass in, so the endpoints
2022  * are always colored vertices.
2023  */
2024 static NTSTATUS kcctpl_add_int_edge(TALLOC_CTX *mem_ctx,
2025                                     struct kcctpl_graph *graph,
2026                                     struct kcctpl_internal_edge_list internal_edges,
2027                                     struct kcctpl_multi_edge *edge,
2028                                     struct kcctpl_vertex *vertex1,
2029                                     struct kcctpl_vertex *vertex2)
2030 {
2031         struct kcctpl_vertex *root1, *root2;
2032         bool red_red, found;
2033         struct kcctpl_repl_info repl_info1, repl_info2;
2034         struct kcctpl_internal_edge new_internal_edge, *new_data;
2035         uint32_t i;
2036
2037         root1 = kcctpl_find_vertex_by_guid(graph, vertex1->root_id);
2038         if (!root1) {
2039                 TALLOC_CTX *tmp_ctx = talloc_new(graph);
2040                 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2041
2042                 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2043                           GUID_string(tmp_ctx, &vertex1->root_id)));
2044
2045                 talloc_free(tmp_ctx);
2046                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2047         }
2048
2049         root2 = kcctpl_find_vertex_by_guid(graph, vertex2->root_id);
2050         if (!root2) {
2051                 TALLOC_CTX *tmp_ctx = talloc_new(graph);
2052                 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2053
2054                 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2055                           GUID_string(tmp_ctx, &vertex2->root_id)));
2056
2057                 talloc_free(tmp_ctx);
2058                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2059         }
2060
2061         red_red = (root1->color == RED && root2->color == RED);
2062
2063         if (red_red) {
2064                 if (!kcctpl_guid_list_contains(root1->accept_red_red,
2065                                                edge->type) ||
2066                     !kcctpl_guid_list_contains(root2->accept_red_red,
2067                                                edge->type)) {
2068                         return NT_STATUS_OK;
2069                 }
2070         } else if (!kcctpl_guid_list_contains(root1->accept_black,
2071                                               edge->type) ||
2072                    !kcctpl_guid_list_contains(root2->accept_black,
2073                                               edge->type)) {
2074                 return NT_STATUS_OK;
2075         }
2076
2077         if (!kcctpl_combine_repl_info(graph, &vertex1->repl_info,
2078                                       &vertex2->repl_info, &repl_info1) ||
2079             !kcctpl_combine_repl_info(graph, &repl_info1, &edge->repl_info,
2080                                       &repl_info2)) {
2081                 return NT_STATUS_OK;
2082         }
2083
2084         new_internal_edge.v1id = root1->id;
2085         new_internal_edge.v2id = root2->id;
2086         new_internal_edge.red_red = red_red;
2087         new_internal_edge.repl_info = repl_info2;
2088         new_internal_edge.type = edge->type;
2089
2090         if (GUID_compare(&new_internal_edge.v1id,
2091                          &new_internal_edge.v2id) > 0) {
2092                 struct GUID tmp_guid = new_internal_edge.v1id;
2093
2094                 new_internal_edge.v1id = new_internal_edge.v2id;
2095                 new_internal_edge.v2id = tmp_guid;
2096         }
2097
2098         found = false;
2099         for (i = 0; i < internal_edges.count; i++) {
2100                 struct kcctpl_internal_edge *ie = &internal_edges.data[i];
2101
2102                 if (kcctpl_internal_edge_equal(ie, &new_internal_edge)) {
2103                         found = true;
2104                 }
2105         }
2106         if (found) {
2107                 return NT_STATUS_OK;
2108         }
2109
2110         new_data = talloc_realloc(mem_ctx, internal_edges.data,
2111                                   struct kcctpl_internal_edge,
2112                                   internal_edges.count + 1);
2113         NT_STATUS_HAVE_NO_MEMORY(new_data);
2114         new_data[internal_edges.count + 1] = new_internal_edge;
2115         internal_edges.data = new_data;
2116         internal_edges.count++;
2117
2118         return NT_STATUS_OK;
2119 }
2120
2121 /**
2122  * after running Dijkstra's algorithm, this function examines a multi-edge and
2123  * adds internal edges between every tree connected by this edge.
2124  */
2125 static NTSTATUS kcctpl_process_edge(TALLOC_CTX *mem_ctx,
2126                                     struct kcctpl_graph *graph,
2127                                     struct kcctpl_multi_edge *edge,
2128                                     struct kcctpl_internal_edge_list internal_edges)
2129 {
2130         TALLOC_CTX *tmp_ctx;
2131         struct kcctpl_vertex_list vertices;
2132         uint32_t i;
2133         struct kcctpl_vertex *best_vertex;
2134
2135         ZERO_STRUCT(vertices);
2136
2137         tmp_ctx = talloc_new(mem_ctx);
2138         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2139
2140         for (i = 0; i < edge->vertex_ids.count; i++) {
2141                 struct GUID id;
2142                 struct kcctpl_vertex *vertex, *new_data;
2143
2144                 id = edge->vertex_ids.data[i];
2145
2146                 vertex = kcctpl_find_vertex_by_guid(graph, id);
2147                 if (!vertex) {
2148                         DEBUG(1, (__location__ ": failed to find vertex %s\n",
2149                                   GUID_string(tmp_ctx, &id)));
2150
2151                         talloc_free(tmp_ctx);
2152                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
2153                 }
2154
2155                 new_data = talloc_realloc(tmp_ctx, vertices.data,
2156                                           struct kcctpl_vertex,
2157                                           vertices.count + 1);
2158                 if (new_data == NULL) {
2159                         TALLOC_FREE(tmp_ctx);
2160                         return NT_STATUS_NO_MEMORY;
2161                 }
2162                 new_data[vertices.count] = *vertex;
2163                 vertices.data = new_data;
2164                 vertices.count++;
2165         }
2166
2167         qsort(vertices.data, vertices.count, sizeof(struct kcctpl_vertex),
2168               kcctpl_sort_vertices);
2169
2170         best_vertex = &vertices.data[0];
2171
2172         for (i = 0; i < edge->vertex_ids.count; i++) {
2173                 struct GUID id, empty_id = GUID_zero();
2174                 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2175
2176                 id = edge->vertex_ids.data[i];
2177
2178                 vertex = kcctpl_find_vertex_by_guid(graph, id);
2179                 if (!vertex) {
2180                         DEBUG(1, (__location__ ": failed to find vertex %s\n",
2181                                   GUID_string(tmp_ctx, &id)));
2182
2183                         talloc_free(tmp_ctx);
2184                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
2185                 }
2186
2187                 if (!GUID_equal(&vertex->component_id, &empty_id) &&
2188                     !GUID_equal(&vertex->root_id, &empty_id)) {
2189                         continue;
2190                 }
2191
2192                 if (!GUID_equal(&best_vertex->component_id,
2193                                 &empty_id) &&
2194                     !GUID_equal(&best_vertex->root_id, &empty_id) &&
2195                     !GUID_equal(&vertex->component_id, &empty_id) &&
2196                     !GUID_equal(&vertex->root_id, &empty_id) &&
2197                     !GUID_equal(&best_vertex->component_id,
2198                                 &vertex->component_id)) {
2199                         NTSTATUS status;
2200
2201                         status = kcctpl_add_int_edge(mem_ctx, graph,
2202                                                      internal_edges,
2203                                                      edge, best_vertex,
2204                                                      vertex);
2205                         if (NT_STATUS_IS_ERR(status)) {
2206                                 DEBUG(1, (__location__ ": failed to add an "
2207                                           "internal edge for %s: %s\n",
2208                                           GUID_string(tmp_ctx, &vertex->id),
2209                                           nt_errstr(status)));
2210                                 talloc_free(tmp_ctx);
2211                                 return status;
2212                         }
2213                 }
2214         }
2215
2216         talloc_free(tmp_ctx);
2217         return NT_STATUS_OK;
2218 }
2219
2220 /**
2221  * after running Dijkstra's algorithm to determine the shortest-path forest,
2222  * examine all edges in this edge set. find all inter-tree edges, from which to
2223  * build the list of 'internal edges', which will later be passed on to
2224  * Kruskal's algorithm.
2225  */
2226 static NTSTATUS kcctpl_process_edge_set(TALLOC_CTX *mem_ctx,
2227                                         struct kcctpl_graph *graph,
2228                                         struct kcctpl_multi_edge_set *set,
2229                                         struct kcctpl_internal_edge_list internal_edges)
2230 {
2231         uint32_t i;
2232
2233         if (!set) {
2234                 for (i = 0; i < graph->edges.count; i++) {
2235                         struct kcctpl_multi_edge *edge;
2236                         uint32_t j;
2237                         NTSTATUS status;
2238
2239                         edge = &graph->edges.data[i];
2240
2241                         for (j = 0; j < edge->vertex_ids.count; j++) {
2242                                 struct GUID id;
2243                                 struct kcctpl_vertex *vertex;
2244
2245                                 id = edge->vertex_ids.data[j];
2246
2247                                 vertex = kcctpl_find_vertex_by_guid(graph, id);
2248                                 if (!vertex) {
2249                                         TALLOC_CTX *tmp_ctx;
2250
2251                                         tmp_ctx = talloc_new(mem_ctx);
2252                                         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2253
2254                                         DEBUG(1, (__location__ ": failed to "
2255                                                   "find vertex %s\n",
2256                                                   GUID_string(tmp_ctx, &id)));
2257
2258                                         talloc_free(tmp_ctx);
2259                                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
2260                                 }
2261
2262                                 kcctpl_check_demote_one_vertex(vertex,
2263                                                                edge->type);
2264                         }
2265
2266                         status = kcctpl_process_edge(mem_ctx, graph, edge,
2267                                                      internal_edges);
2268                         if (NT_STATUS_IS_ERR(status)) {
2269                                 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2270                                 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2271
2272                                 DEBUG(1, (__location__ ": failed to process "
2273                                           "edge %s: %s\n",
2274                                           GUID_string(tmp_ctx, &edge->id),
2275                                           nt_errstr(status)));
2276
2277                                 talloc_free(tmp_ctx);
2278                                 return status;
2279                         }
2280
2281                         for (j = 0; j < edge->vertex_ids.count; j++) {
2282                                 struct GUID id;
2283                                 struct kcctpl_vertex *vertex;
2284
2285                                 id = edge->vertex_ids.data[j];
2286
2287                                 vertex = kcctpl_find_vertex_by_guid(graph, id);
2288                                 if (!vertex) {
2289                                         TALLOC_CTX *tmp_ctx;
2290
2291                                         tmp_ctx = talloc_new(mem_ctx);
2292                                         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2293
2294                                         DEBUG(1, (__location__ ": failed to "
2295                                                   "find vertex %s\n",
2296                                                   GUID_string(tmp_ctx, &id)));
2297
2298                                         talloc_free(tmp_ctx);
2299                                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
2300                                 }
2301
2302                                 kcctpl_undemote_one_vertex(vertex);
2303                         }
2304                 }
2305         } else {
2306                 for (i = 0; i < graph->edges.count; i++) {
2307                         struct kcctpl_multi_edge *edge = &graph->edges.data[i];
2308
2309                         if (kcctpl_guid_list_contains(set->edge_ids,
2310                                                       edge->id)) {
2311                                 NTSTATUS status;
2312
2313                                 status = kcctpl_process_edge(mem_ctx, graph,
2314                                                              edge,
2315                                                              internal_edges);
2316                                 if (NT_STATUS_IS_ERR(status)) {
2317                                         TALLOC_CTX *tmp_ctx;
2318
2319                                         tmp_ctx = talloc_new(mem_ctx);
2320                                         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2321
2322                                         DEBUG(1, (__location__ ": failed to "
2323                                                   "process edge %s: %s\n",
2324                                                   GUID_string(tmp_ctx,
2325                                                               &edge->id),
2326                                                   nt_errstr(status)));
2327
2328                                         talloc_free(tmp_ctx);
2329                                         return status;
2330                                 }
2331                         }
2332                 }
2333         }
2334
2335         return NT_STATUS_OK;
2336 }
2337
2338 /**
2339  * a new edge, 'internal_edge', has been found for the spanning tree edge. add
2340  * this edge to the list of output edges.
2341  */
2342 static NTSTATUS kcctpl_add_out_edge(TALLOC_CTX *mem_ctx,
2343                                     struct kcctpl_graph *graph,
2344                                     struct kcctpl_multi_edge_list output_edges,
2345                                     struct kcctpl_internal_edge *internal_edge)
2346 {
2347         struct kcctpl_vertex *vertex1, *vertex2;
2348         TALLOC_CTX *tmp_ctx;
2349         struct kcctpl_multi_edge *new_edge, *new_data;
2350         struct GUID *new_data_id;
2351
2352         tmp_ctx = talloc_new(mem_ctx);
2353         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2354
2355         vertex1 = kcctpl_find_vertex_by_guid(graph, internal_edge->v1id);
2356         if (!vertex1) {
2357                 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2358                           GUID_string(tmp_ctx, &internal_edge->v1id)));
2359
2360                 talloc_free(tmp_ctx);
2361                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2362         }
2363
2364         vertex2 = kcctpl_find_vertex_by_guid(graph, internal_edge->v2id);
2365         if (!vertex2) {
2366                 DEBUG(1, (__location__ ": failed to find vertex %s\n",
2367                           GUID_string(tmp_ctx, &internal_edge->v2id)));
2368
2369                 talloc_free(tmp_ctx);
2370                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2371         }
2372
2373         new_edge = talloc(tmp_ctx, struct kcctpl_multi_edge);
2374         if (new_edge == NULL) {
2375                 TALLOC_FREE(tmp_ctx);
2376                 return NT_STATUS_NO_MEMORY;
2377         }
2378
2379         new_edge->id = GUID_random(); /* TODO: what should be new_edge->GUID? */
2380         new_edge->directed = false;
2381
2382         new_edge->vertex_ids.data = talloc_array(new_edge, struct GUID, 2);
2383         if (new_edge->vertex_ids.data == NULL) {
2384                 TALLOC_FREE(tmp_ctx);
2385                 return NT_STATUS_NO_MEMORY;
2386         }
2387
2388         new_edge->vertex_ids.data[0] = vertex1->id;
2389         new_edge->vertex_ids.data[1] = vertex2->id;
2390         new_edge->vertex_ids.count = 2;
2391
2392         new_edge->type = internal_edge->type;
2393         new_edge->repl_info = internal_edge->repl_info;
2394
2395         new_data = talloc_realloc(tmp_ctx, output_edges.data,
2396                                   struct kcctpl_multi_edge,
2397                                   output_edges.count + 1);
2398         if (new_data == NULL) {
2399                 TALLOC_FREE(tmp_ctx);
2400                 return NT_STATUS_NO_MEMORY;
2401         }
2402         new_data[output_edges.count + 1] = *new_edge;
2403         output_edges.data = new_data;
2404         output_edges.count++;
2405
2406         new_data_id = talloc_realloc(vertex1, vertex1->edge_ids.data,
2407                                      struct GUID, vertex1->edge_ids.count);
2408         if (new_data_id == NULL) {
2409                 TALLOC_FREE(tmp_ctx);
2410                 return NT_STATUS_NO_MEMORY;
2411         }
2412         new_data_id[vertex1->edge_ids.count] = new_edge->id;
2413         talloc_free(vertex1->edge_ids.data);
2414         vertex1->edge_ids.data = new_data_id;
2415         vertex1->edge_ids.count++;
2416
2417         new_data_id = talloc_realloc(vertex2, vertex2->edge_ids.data,
2418                                      struct GUID, vertex2->edge_ids.count);
2419         if (new_data_id == NULL) {
2420                 TALLOC_FREE(tmp_ctx);
2421                 return NT_STATUS_NO_MEMORY;
2422         }
2423         new_data_id[vertex2->edge_ids.count] = new_edge->id;
2424         talloc_free(vertex2->edge_ids.data);
2425         vertex2->edge_ids.data = new_data_id;
2426         vertex2->edge_ids.count++;
2427
2428         talloc_steal(graph, new_edge);
2429         talloc_steal(mem_ctx, output_edges.data);
2430         talloc_free(tmp_ctx);
2431         return NT_STATUS_OK;
2432 }
2433
2434 /**
2435  * run Kruskal's minimum-cost spanning tree algorithm on the internal edges
2436  * (that represent shortest paths in the original graph between colored
2437  * vertices).
2438  */
2439 static NTSTATUS kcctpl_kruskal(TALLOC_CTX *mem_ctx, struct kcctpl_graph *graph,
2440                                struct kcctpl_internal_edge_list internal_edges,
2441                                struct kcctpl_multi_edge_list *_output_edges)
2442 {
2443         uint32_t i, num_expected_tree_edges, cst_edges;
2444         struct kcctpl_multi_edge_list output_edges;
2445
2446         num_expected_tree_edges = 0;
2447         for (i = 0; i < graph->vertices.count; i++) {
2448                 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2449
2450                 talloc_free(vertex->edge_ids.data);
2451                 ZERO_STRUCT(vertex->edge_ids);
2452
2453                 if (vertex->color == RED || vertex->color == WHITE) {
2454                         num_expected_tree_edges++;
2455                 }
2456         }
2457
2458         qsort(internal_edges.data, internal_edges.count,
2459               sizeof(struct kcctpl_internal_edge), kcctpl_sort_internal_edges);
2460
2461         cst_edges = 0;
2462
2463         ZERO_STRUCT(output_edges);
2464
2465         while (internal_edges.count > 0 &&
2466                cst_edges < num_expected_tree_edges) {
2467                 struct kcctpl_internal_edge *edge, *new_data;
2468                 struct kcctpl_vertex *vertex1, *vertex2;
2469                 struct GUID comp1, comp2;
2470
2471                 edge = &internal_edges.data[0];
2472
2473                 vertex1 = kcctpl_find_vertex_by_guid(graph, edge->v1id);
2474                 if (!vertex1) {
2475                         TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2476                         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2477
2478                         DEBUG(1, (__location__ ": failed to find vertex %s\n",
2479                                   GUID_string(tmp_ctx, &edge->v1id)));
2480
2481                         talloc_free(tmp_ctx);
2482                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
2483                 }
2484
2485                 vertex2 = kcctpl_find_vertex_by_guid(graph, edge->v2id);
2486                 if (!vertex2) {
2487                         TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2488                         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2489
2490                         DEBUG(1, (__location__ ": failed to find vertex %s\n",
2491                                   GUID_string(tmp_ctx, &edge->v2id)));
2492
2493                         talloc_free(tmp_ctx);
2494                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
2495                 }
2496
2497                 comp1 = kcctpl_get_component_id(graph, vertex1);
2498                 comp2 = kcctpl_get_component_id(graph, vertex2);
2499
2500                 if (!GUID_equal(&comp1, &comp2)) {
2501                         NTSTATUS status;
2502                         struct kcctpl_vertex *vertex;
2503
2504                         cst_edges++;
2505
2506                         status = kcctpl_add_out_edge(mem_ctx, graph,
2507                                                      output_edges, edge);
2508                         if (NT_STATUS_IS_ERR(status)) {
2509                                 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2510                                 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2511
2512                                 DEBUG(1, (__location__ ": failed to add an "
2513                                           "output edge between %s and %s: %s\n",
2514                                           GUID_string(tmp_ctx, &edge->v1id),
2515                                           GUID_string(tmp_ctx, &edge->v2id),
2516                                           nt_errstr(status)));
2517
2518                                 talloc_free(tmp_ctx);
2519                                 return status;
2520                         }
2521
2522                         vertex = kcctpl_find_vertex_by_guid(graph, comp1);
2523                         if (!vertex) {
2524                                 TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2525                                 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2526
2527                                 DEBUG(1, (__location__ ": failed to find "
2528                                           "vertex %s\n", GUID_string(tmp_ctx,
2529                                                                      &comp1)));
2530
2531                                 talloc_free(tmp_ctx);
2532                                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2533                         }
2534                         vertex->component_id = comp2;
2535                 }
2536
2537                 internal_edges.data = internal_edges.data + 1;
2538                 new_data = talloc_realloc(mem_ctx, internal_edges.data,
2539                                           struct kcctpl_internal_edge,
2540                                           internal_edges.count - 1);
2541                 NT_STATUS_HAVE_NO_MEMORY(new_data);
2542                 talloc_free(internal_edges.data);
2543                 internal_edges.data = new_data;
2544                 internal_edges.count--;
2545         }
2546
2547         *_output_edges = output_edges;
2548         return NT_STATUS_OK;
2549 }
2550
2551 /**
2552  * count the number of components. a component is considered to be a bunch of
2553  * colored vertices that are connected by the spanning tree. vertices whose
2554  * component ID is the same as their vertex ID are the root of the connected
2555  * component.
2556  */
2557 static uint32_t kcctpl_count_components(struct kcctpl_graph *graph)
2558 {
2559         uint32_t num_components = 0, i;
2560
2561         for (i = 0; i < graph->vertices.count; i++) {
2562                 struct kcctpl_vertex *vertex;
2563                 struct GUID component_id;
2564
2565                 vertex = &graph->vertices.data[i];
2566
2567                 if (vertex->color == WHITE) {
2568                         continue;
2569                 }
2570
2571                 component_id = kcctpl_get_component_id(graph, vertex);
2572                 if (GUID_equal(&component_id, &vertex->id)) {
2573                         vertex->component_index = num_components;
2574                         num_components++;
2575                 }
2576         }
2577
2578         return num_components;
2579 }
2580
2581 /**
2582  * calculate the spanning tree and return the edges that include the vertex for
2583  * the local site.
2584  */
2585 static NTSTATUS kcctpl_get_spanning_tree_edges(struct kccsrv_service *service,
2586                                                TALLOC_CTX *mem_ctx,
2587                                                struct kcctpl_graph *graph,
2588                                                uint32_t *_component_count,
2589                                                struct kcctpl_multi_edge_list *_st_edge_list)
2590 {
2591         TALLOC_CTX *tmp_ctx;
2592         struct kcctpl_internal_edge_list internal_edges;
2593         uint32_t i, component_count;
2594         NTSTATUS status;
2595         struct kcctpl_multi_edge_list output_edges, st_edge_list;
2596
2597         ZERO_STRUCT(internal_edges);
2598
2599         tmp_ctx = talloc_new(mem_ctx);
2600         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2601
2602         for (i = 0; i < graph->edge_sets.count; i++) {
2603                 struct kcctpl_multi_edge_set *set;
2604                 struct GUID edge_type;
2605                 uint32_t j;
2606
2607                 set = &graph->edge_sets.data[i];
2608
2609                 edge_type = GUID_zero();
2610
2611                 for (j = 0; j < graph->vertices.count; j++) {
2612                         struct kcctpl_vertex *vertex = &graph->vertices.data[j];
2613
2614                         talloc_free(vertex->edge_ids.data);
2615                         ZERO_STRUCT(vertex->edge_ids.data);
2616                 }
2617
2618                 for (j = 0; j < set->edge_ids.count; j++) {
2619                         struct GUID edge_id;
2620                         struct kcctpl_multi_edge *edge;
2621                         uint32_t k;
2622
2623                         edge_id = set->edge_ids.data[j];
2624                         edge = kcctpl_find_edge_by_guid(graph, edge_id);
2625                         if (!edge) {
2626                                 DEBUG(1, (__location__ ": failed to find a "
2627                                           "graph edge with ID=%s\n",
2628                                           GUID_string(tmp_ctx, &edge_id)));
2629
2630                                 talloc_free(tmp_ctx);
2631                                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2632                         }
2633
2634                         edge_type = edge->type;
2635
2636                         for (k = 0; k < edge->vertex_ids.count; k++) {
2637                                 struct GUID vertex_id, *new_data;
2638                                 struct kcctpl_vertex *vertex;
2639
2640                                 vertex_id = edge->vertex_ids.data[k];
2641                                 vertex = kcctpl_find_vertex_by_guid(graph,
2642                                                                     vertex_id);
2643                                 if (!vertex) {
2644                                         DEBUG(1, (__location__ ": failed to "
2645                                                   "find a graph vertex with "
2646                                                   "ID=%s\n",
2647                                                   GUID_string(tmp_ctx,
2648                                                               &edge_id)));
2649
2650                                         talloc_free(tmp_ctx);
2651                                         return NT_STATUS_INTERNAL_DB_CORRUPTION;
2652                                 }
2653
2654                                 new_data = talloc_realloc(tmp_ctx,
2655                                                           vertex->edge_ids.data,
2656                                                           struct GUID,
2657                                                           vertex->edge_ids.count + 1);
2658                                 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
2659                                                                   tmp_ctx);
2660                                 new_data[vertex->edge_ids.count] = edge->id;
2661                                 vertex->edge_ids.data = new_data;
2662                                 vertex->edge_ids.count++;
2663                         }
2664                 }
2665
2666                 status = kcctpl_dijkstra(graph, edge_type, false);
2667                 if (NT_STATUS_IS_ERR(status)) {
2668                         DEBUG(1, (__location__ ": failed to run Dijkstra's "
2669                                   "algorithm: %s\n", nt_errstr(status)));
2670
2671                         talloc_free(tmp_ctx);
2672                         return status;
2673                 }
2674
2675                 status = kcctpl_process_edge_set(tmp_ctx, graph, set,
2676                                                  internal_edges);
2677                 if (NT_STATUS_IS_ERR(status)) {
2678                         DEBUG(1, (__location__ ": failed to process edge set "
2679                                   "%s: %s\n", GUID_string(tmp_ctx, &set->id),
2680                                   nt_errstr(status)));
2681
2682                         talloc_free(tmp_ctx);
2683                         return status;
2684                 }
2685
2686                 status = kcctpl_dijkstra(graph, edge_type, true);
2687                 if (NT_STATUS_IS_ERR(status)) {
2688                         DEBUG(1, (__location__ ": failed to run Dijkstra's "
2689                                   "algorithm: %s\n", nt_errstr(status)));
2690
2691                         talloc_free(tmp_ctx);
2692                         return status;
2693                 }
2694
2695                 status = kcctpl_process_edge_set(tmp_ctx, graph, set,
2696                                                  internal_edges);
2697                 if (NT_STATUS_IS_ERR(status)) {
2698                         DEBUG(1, (__location__ ": failed to process edge set "
2699                                   "%s: %s\n", GUID_string(tmp_ctx, &set->id),
2700                                   nt_errstr(status)));
2701
2702                         talloc_free(tmp_ctx);
2703                         return status;
2704                 }
2705         }
2706
2707         kcctpl_setup_vertices(graph);
2708
2709         status = kcctpl_process_edge_set(tmp_ctx, graph, NULL, internal_edges);
2710         if (NT_STATUS_IS_ERR(status)) {
2711                 DEBUG(1, (__location__ ": failed to process empty edge set: "
2712                           "%s\n", nt_errstr(status)));
2713
2714                 talloc_free(tmp_ctx);
2715                 return status;
2716         }
2717
2718         status = kcctpl_kruskal(tmp_ctx, graph, internal_edges, &output_edges);
2719         if (NT_STATUS_IS_ERR(status)) {
2720                 DEBUG(1, (__location__ ": failed to run Kruskal's algorithm: "
2721                           "%s\n", nt_errstr(status)));
2722
2723                 talloc_free(tmp_ctx);
2724                 return status;
2725         }
2726
2727         for (i = 0; i < graph->vertices.count; i++) {
2728                 struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2729
2730                 if (vertex->color == RED) {
2731                         vertex->dist_to_red = 0;
2732                 } else if (true) { /* TODO: if there exists a path from 'vertex'
2733                                     to a RED vertex */
2734                         vertex->dist_to_red = -1; /* TODO: the length of the
2735                                                      shortest such path */
2736                 } else {
2737                         vertex->dist_to_red = UINT32_MAX;
2738                 }
2739         }
2740
2741         component_count = kcctpl_count_components(graph);
2742
2743         status = kcctpl_copy_output_edges(service, tmp_ctx, graph, output_edges,
2744                                           &st_edge_list);
2745         if (NT_STATUS_IS_ERR(status)) {
2746                 DEBUG(1, (__location__ ": failed to copy edge list: %s\n",
2747                           nt_errstr(status)));
2748
2749                 talloc_free(tmp_ctx);
2750                 return status;
2751         }
2752
2753         *_component_count = component_count;
2754         talloc_steal(mem_ctx, st_edge_list.data);
2755         *_st_edge_list = st_edge_list;
2756         talloc_free(tmp_ctx);
2757         return NT_STATUS_OK;
2758 }
2759
2760 /**
2761  * creat an nTDSConnection object with the given parameters if one does not
2762  * already exist.
2763  */
2764 static NTSTATUS kcctpl_create_connection(struct kccsrv_service *service,
2765                                          TALLOC_CTX *mem_ctx,
2766                                          struct ldb_message *cross_ref,
2767                                          struct ldb_message *r_bridgehead,
2768                                          struct ldb_message *transport,
2769                                          struct ldb_message *l_bridgehead,
2770                                          struct kcctpl_repl_info repl_info,
2771                                          uint8_t schedule[84],
2772                                          bool detect_failed_dcs,
2773                                          bool partial_replica_okay,
2774                                          struct GUID_list *_keep_connections)
2775 {
2776         TALLOC_CTX *tmp_ctx;
2777         struct ldb_dn *r_site_dn, *l_site_dn, *servers_dn;
2778         bool ok;
2779         struct GUID r_site_guid, l_site_guid;
2780         int ret;
2781         struct message_list r_bridgeheads_all, l_bridgeheads_all,
2782                             r_bridgeheads_available, l_bridgeheads_available;
2783         NTSTATUS status;
2784         struct ldb_result *res;
2785         const char * const attrs[] = { "objectGUID", "parent", "fromServer",
2786                                        "transportType", "schedule", "options",
2787                                        "enabledConnection", NULL };
2788         unsigned int i, valid_connections;
2789         struct GUID_list keep_connections;
2790
2791         tmp_ctx = talloc_new(service);
2792         NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2793
2794         r_site_dn = ldb_dn_copy(tmp_ctx, r_bridgehead->dn);
2795         if (r_site_dn == NULL) {
2796                 TALLOC_FREE(tmp_ctx);
2797                 return NT_STATUS_NO_MEMORY;
2798         }
2799
2800         ok = ldb_dn_remove_child_components(r_site_dn, 3);
2801         if (!ok) {
2802                 talloc_free(tmp_ctx);
2803                 return NT_STATUS_NO_MEMORY;
2804         }
2805
2806         ret = dsdb_find_guid_by_dn(service->samdb, r_site_dn, &r_site_guid);
2807         if (ret != LDB_SUCCESS) {
2808                 DEBUG(1, (__location__ ": failed to find objectGUID for object "
2809                           "%s: %s\n", ldb_dn_get_linearized(r_site_dn),
2810                           ldb_strerror(ret)));
2811
2812                 talloc_free(tmp_ctx);
2813                 return NT_STATUS_INTERNAL_DB_CORRUPTION;
2814         }
2815
2816         l_site_dn = ldb_dn_copy(tmp_ctx, l_bridgehead->dn);
2817         if (l_site_dn == NULL) {
2818                 TALLOC_FREE(tmp_ctx);