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