2
Unix SMB/CIFS implementation.
6
Copyright (C) Crístian Deives 2010
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.
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.
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/>.
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"
29
#define FLAG_CR_NTDS_NC 0x00000001
30
#define FLAG_CR_NTDS_DOMAIN 0x00000002
32
#define NTDSCONN_OPT_IS_GENERATED 0x00000001
33
#define NTDSCONN_OPT_TWOWAY_SYNC 0x00000002
34
#define NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT 0x00000004
35
#define NTDSCONN_OPT_USE_NOTIFY 0x00000008
36
#define NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION 0x00000010
37
#define NTDSCONN_OPT_USER_OWNED_SCHEDULE 0x00000020
38
#define NTDSCONN_OPT_RODC_TOPOLOGY 0x00000040
40
#define NTDSDSA_OPT_IS_GC 0x00000001
42
#define NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED 0x00000008
43
#define NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED 0x00000100
44
#define NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED 0x00001000
46
#define NTDSSITELINK_OPT_USE_NOTIFY 0x00000001
47
#define NTDSSITELINK_OPT_TWOWAY_SYNC 0x00000002
48
#define NTDSSITELINK_OPT_DISABLE_COMPRESSION 0x00000004
50
#define NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
52
#define DS_BEHAVIOR_WIN2008 3
54
/** replication parameters of a graph edge */
55
struct kcctpl_repl_info {
62
/** color of a vertex */
63
enum kcctpl_color { RED, BLACK, WHITE };
65
/** a GUID array list */
71
/** a vertex in the site graph */
72
struct kcctpl_vertex {
74
struct GUID_list edge_ids;
75
enum kcctpl_color color;
76
struct GUID_list accept_red_red;
77
struct GUID_list accept_black;
78
struct kcctpl_repl_info repl_info;
86
struct GUID component_id;
87
uint32_t component_index;
90
/** fully connected subgraph of vertices */
91
struct kcctpl_multi_edge {
93
struct GUID_list vertex_ids;
95
struct kcctpl_repl_info repl_info;
99
/** set of transitively connected kcc_multi_edge's. all edges within the set
100
* have the same type. */
101
struct kcctpl_multi_edge_set {
103
struct GUID_list edge_ids;
106
/** a vertices array list */
107
struct kcctpl_vertex_list {
108
struct kcctpl_vertex *data;
112
/** an edges array list */
113
struct kcctpl_multi_edge_list {
114
struct kcctpl_multi_edge *data;
118
/** an edge sets array list */
119
struct kcctpl_multi_edge_set_list {
120
struct kcctpl_multi_edge_set *data;
125
struct kcctpl_graph {
126
struct kcctpl_vertex_list vertices;
127
struct kcctpl_multi_edge_list edges;
128
struct kcctpl_multi_edge_set_list edge_sets;
131
/** path found in the graph between two non-white vertices */
132
struct kcctpl_internal_edge {
136
struct kcctpl_repl_info repl_info;
140
/** an internal edges array list */
141
struct kcctpl_internal_edge_list {
142
struct kcctpl_internal_edge *data;
146
/** an LDB messages array list */
147
struct message_list {
148
struct ldb_message *data;
153
* sort internal edges based on:
154
* - descending red_red,
155
* - ascending repl_info.cost,
156
* - descending available time in repl_info.schedule,
161
* this function is used in 'kcctpl_kruskal'.
163
static int kcctpl_sort_internal_edges(const void *internal_edge1,
164
const void *internal_edge2)
166
const struct kcctpl_internal_edge *ie1, *ie2;
169
ie1 = (const struct kcctpl_internal_edge *) internal_edge1;
170
ie2 = (const struct kcctpl_internal_edge *) internal_edge2;
172
cmp_red_red = ie2->red_red - ie1->red_red;
173
if (cmp_red_red == 0) {
174
int cmp_cost = ie1->repl_info.cost - ie2->repl_info.cost;
177
uint32_t available1, available2, i;
180
available1 = available2 = 0;
181
for (i = 0; i < 84; i++) {
182
if (ie1->repl_info.schedule[i] == 0) {
186
if (ie2->repl_info.schedule[i] == 0) {
190
cmp_schedule = available2 - available1;
192
if (cmp_schedule == 0) {
193
int cmp_v1id = GUID_compare(&ie1->v1id,
197
int cmp_v2id = GUID_compare(&ie1->v2id,
201
return GUID_compare(&ie1->type,
221
* sort vertices based on the following criteria:
222
* - ascending color (RED < BLACK),
223
* - ascending repl_info.cost,
226
* this function is used in 'kcctpl_process_edge'.
228
static int kcctpl_sort_vertices(const void *vertex1, const void *vertex2)
230
const struct kcctpl_vertex *v1, *v2;
233
v1 = (const struct kcctpl_vertex *) vertex1;
234
v2 = (const struct kcctpl_vertex *) vertex2;
236
cmp_color = v1->color - v2->color;
237
if (cmp_color == 0) {
238
int cmp_cost = v1->repl_info.cost - v2->repl_info.cost;
240
return GUID_compare(&v1->id, &v2->id);
250
* sort bridgehead elements (nTDSDSA) based on the following criteria:
251
* - GC servers precede non-GC servers
252
* - ascending objectGUID
254
* this function is used in 'kcctpl_get_all_bridgehead_dcs'.
256
static int kcctpl_sort_bridgeheads(const void *bridgehead1,
257
const void *bridgehead2)
259
const struct ldb_message *bh1, *bh2;
260
uint32_t bh1_opts, bh2_opts;
263
bh1 = (const struct ldb_message *) bridgehead1;
264
bh2 = (const struct ldb_message *) bridgehead2;
266
bh1_opts = ldb_msg_find_attr_as_uint(bh1, "options", 0);
267
bh2_opts = ldb_msg_find_attr_as_uint(bh2, "options", 0);
269
cmp_gc = (bh1_opts & NTDSDSA_OPT_IS_GC) -
270
(bh2_opts & NTDSDSA_OPT_IS_GC);
273
struct GUID bh1_id, bh2_id;
275
bh1_id = samdb_result_guid(bh1, "objectGUID");
276
bh2_id = samdb_result_guid(bh2, "objectGUID");
278
return GUID_compare(&bh1_id, &bh2_id);
285
* sort bridgehead elements (nTDSDSA) in a random order.
287
* this function is used in 'kcctpl_get_all_bridgehead_dcs'.
289
static void kcctpl_shuffle_bridgeheads(struct message_list bridgeheads)
295
for (i = bridgeheads.count; i > 1; i--) {
297
struct ldb_message tmp;
301
tmp = bridgeheads.data[i - 1];
302
bridgeheads.data[i - 1] = bridgeheads.data[r];
303
bridgeheads.data[r] = tmp;
308
* find a graph vertex based on its GUID.
310
static struct kcctpl_vertex *kcctpl_find_vertex_by_guid(struct kcctpl_graph *graph,
315
for (i = 0; i < graph->vertices.count; i++) {
316
if (GUID_equal(&graph->vertices.data[i].id, &guid)) {
317
return &graph->vertices.data[i];
325
* find a graph edge based on its GUID.
327
static struct kcctpl_multi_edge *kcctpl_find_edge_by_guid(struct kcctpl_graph *graph,
332
for (i = 0; i < graph->edges.count; i++) {
333
if (GUID_equal(&graph->edges.data[i].id, &guid)) {
334
return &graph->edges.data[i];
342
* find a graph edge that contains a vertex with the specified GUID. the first
343
* occurrence will be returned.
345
static struct kcctpl_multi_edge *kcctpl_find_edge_by_vertex_guid(struct kcctpl_graph *graph,
350
for (i = 0; i < graph->edges.count; i++) {
351
struct kcctpl_multi_edge *edge;
354
edge = &graph->edges.data[i];
356
for (j = 0; j < edge->vertex_ids.count; j++) {
357
struct GUID vertex_guid = edge->vertex_ids.data[j];
359
struct GUID *p = &guid;
361
if (GUID_equal(&vertex_guid, p)) {
371
* search for an occurrence of a GUID inside a list of GUIDs.
373
static bool kcctpl_guid_list_contains(struct GUID_list list, struct GUID guid)
377
for (i = 0; i < list.count; i++) {
378
if (GUID_equal(&list.data[i], &guid)) {
387
* search for an occurrence of an ldb_message inside a list of ldb_messages,
388
* based on the ldb_message's DN.
390
static bool kcctpl_message_list_contains_dn(struct message_list list,
395
for (i = 0; i < list.count; i++) {
396
struct ldb_message *message = &list.data[i];
398
if (ldb_dn_compare(message->dn, dn) == 0) {
407
* get the Transports DN
408
* (CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=<domain>).
410
static struct ldb_dn *kcctpl_transports_dn(struct ldb_context *ldb,
413
struct ldb_dn *sites_dn;
416
sites_dn = samdb_sites_dn(ldb, mem_ctx);
421
ok = ldb_dn_add_child_fmt(sites_dn, "CN=Inter-Site Transports");
423
talloc_free(sites_dn);
430
* get the domain local site object.
432
static struct ldb_message *kcctpl_local_site(struct ldb_context *ldb,
437
struct ldb_dn *sites_dn;
438
struct ldb_result *res;
439
const char * const attrs[] = { "objectGUID", "options", NULL };
441
tmp_ctx = talloc_new(ldb);
443
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
445
talloc_free(tmp_ctx);
449
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE, attrs,
452
if (ret != LDB_SUCCESS || res->count == 0) {
453
talloc_free(tmp_ctx);
457
talloc_steal(mem_ctx, res);
458
talloc_free(tmp_ctx);
463
* compare two internal edges for equality. every field of the structure will be
466
static bool kcctpl_internal_edge_equal(struct kcctpl_internal_edge *edge1,
467
struct kcctpl_internal_edge *edge2)
469
if (!edge1 || !edge2) {
473
if (!GUID_equal(&edge1->v1id, &edge2->v1id)) {
477
if (!GUID_equal(&edge1->v2id, &edge2->v2id)) {
481
if (edge1->red_red != edge2->red_red) {
485
if (edge1->repl_info.cost != edge2->repl_info.cost ||
486
edge1->repl_info.interval != edge2->repl_info.interval ||
487
edge1->repl_info.options != edge2->repl_info.options ||
488
memcmp(&edge1->repl_info.schedule,
489
&edge2->repl_info.schedule, 84) != 0) {
493
if (!GUID_equal(&edge1->type, &edge2->type)) {
501
* create a kcctpl_graph instance.
503
static NTSTATUS kcctpl_create_graph(TALLOC_CTX *mem_ctx,
504
struct GUID_list guids,
505
struct kcctpl_graph **_graph)
507
struct kcctpl_graph *graph;
510
graph = talloc_zero(mem_ctx, struct kcctpl_graph);
511
NT_STATUS_HAVE_NO_MEMORY(graph);
513
graph->vertices.count = guids.count;
514
graph->vertices.data = talloc_zero_array(graph, struct kcctpl_vertex,
516
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(graph->vertices.data, graph);
518
TYPESAFE_QSORT(guids.data, guids.count, GUID_compare);
520
for (i = 0; i < guids.count; i++) {
521
graph->vertices.data[i].id = guids.data[i];
529
* create a kcctpl_multi_edge instance.
531
static NTSTATUS kcctpl_create_edge(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
533
struct ldb_message *site_link,
534
struct kcctpl_multi_edge **_edge)
536
struct kcctpl_multi_edge *edge;
538
struct ldb_dn *sites_dn;
539
struct ldb_result *res;
540
const char * const attrs[] = { "siteList", NULL };
542
struct ldb_message_element *el;
546
tmp_ctx = talloc_new(mem_ctx);
547
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
549
edge = talloc_zero(tmp_ctx, struct kcctpl_multi_edge);
550
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge, tmp_ctx);
552
edge->id = samdb_result_guid(site_link, "objectGUID");
554
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
556
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
558
talloc_free(tmp_ctx);
559
return NT_STATUS_INTERNAL_DB_CORRUPTION;
562
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE, attrs,
563
"objectGUID=%s", GUID_string(tmp_ctx, &edge->id));
564
if (ret != LDB_SUCCESS) {
565
DEBUG(1, (__location__ ": failed to find siteLink object %s: "
566
"%s\n", GUID_string(tmp_ctx, &edge->id),
569
talloc_free(tmp_ctx);
570
return NT_STATUS_INTERNAL_DB_CORRUPTION;
572
if (res->count == 0) {
573
DEBUG(1, (__location__ ": failed to find siteLink object %s\n",
574
GUID_string(tmp_ctx, &edge->id)));
576
talloc_free(tmp_ctx);
577
return NT_STATUS_INTERNAL_DB_CORRUPTION;
580
el = ldb_msg_find_element(res->msgs[0], "siteList");
582
DEBUG(1, (__location__ ": failed to find siteList attribute of "
584
ldb_dn_get_linearized(res->msgs[0]->dn)));
586
talloc_free(tmp_ctx);
587
return NT_STATUS_INTERNAL_DB_CORRUPTION;
590
edge->vertex_ids.data = talloc_array(edge, struct GUID, el->num_values);
591
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge->vertex_ids.data, tmp_ctx);
592
edge->vertex_ids.count = el->num_values;
594
for (i = 0; i < el->num_values; i++) {
599
dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
601
DEBUG(1, (__location__ ": failed to read a DN from "
602
"siteList attribute of %s\n",
603
ldb_dn_get_linearized(res->msgs[0]->dn)));
605
talloc_free(tmp_ctx);
606
return NT_STATUS_INTERNAL_DB_CORRUPTION;
608
ret = dsdb_find_guid_by_dn(ldb, dn, &guid);
609
if (ret != LDB_SUCCESS) {
610
DEBUG(1, (__location__ ": failed to find objectGUID "
611
"for object %s: %s\n",
612
ldb_dn_get_linearized(dn),
615
talloc_free(tmp_ctx);
616
return NT_STATUS_INTERNAL_DB_CORRUPTION;
619
edge->vertex_ids.data[i] = guid;
622
edge->repl_info.cost = ldb_msg_find_attr_as_int64(site_link, "cost", 0);
623
edge->repl_info.options = ldb_msg_find_attr_as_uint(site_link, "options", 0);
624
edge->repl_info.interval = ldb_msg_find_attr_as_int64(site_link,
626
/* TODO: edge->repl_info.schedule = site_link!schedule */
628
edge->directed = false;
630
*_edge = talloc_steal(mem_ctx, edge);
631
talloc_free(tmp_ctx);
636
* create a kcctpl_multi_edge_set instance containing edges for all siteLink
639
static NTSTATUS kcctpl_create_auto_edge_set(struct kcctpl_graph *graph,
641
struct ldb_result *res_site_link,
642
struct kcctpl_multi_edge_set **_set)
644
struct kcctpl_multi_edge_set *set;
648
tmp_ctx = talloc_new(graph);
649
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
651
set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
652
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set, tmp_ctx);
654
for (i = 0; i < res_site_link->count; i++) {
655
struct GUID site_link_guid;
656
struct kcctpl_multi_edge *edge;
658
site_link_guid = samdb_result_guid(res_site_link->msgs[i],
660
edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
662
DEBUG(1, (__location__ ": failed to find a graph edge "
664
GUID_string(tmp_ctx, &site_link_guid)));
666
talloc_free(tmp_ctx);
667
return NT_STATUS_INTERNAL_DB_CORRUPTION;
670
if (GUID_equal(&edge->type, &type)) {
671
struct GUID *new_data;
673
new_data = talloc_realloc(set, set->edge_ids.data,
675
set->edge_ids.count + 1);
676
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
677
new_data[set->edge_ids.count] = site_link_guid;
678
set->edge_ids.data = new_data;
679
set->edge_ids.count++;
683
*_set = talloc_steal(graph, set);
688
* create a kcctpl_multi_edge_set instance.
690
static NTSTATUS kcctpl_create_edge_set(struct ldb_context *ldb,
691
struct kcctpl_graph *graph,
693
struct ldb_message *bridge,
694
struct kcctpl_multi_edge_set **_set)
696
struct kcctpl_multi_edge_set *set;
698
struct ldb_message_element *el;
701
tmp_ctx = talloc_new(ldb);
702
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
704
set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
705
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set, tmp_ctx);
707
set->id = samdb_result_guid(bridge, "objectGUID");
709
el = ldb_msg_find_element(bridge, "siteLinkList");
711
DEBUG(1, (__location__ ": failed to find siteLinkList "
712
"attribute of object %s\n",
713
ldb_dn_get_linearized(bridge->dn)));
715
talloc_free(tmp_ctx);
716
return NT_STATUS_INTERNAL_DB_CORRUPTION;
718
for (i = 0; i < el->num_values; i++) {
721
struct GUID site_link_guid;
723
struct kcctpl_multi_edge *edge;
726
dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
728
DEBUG(1, (__location__ ": failed to read a DN from "
729
"siteList attribute of %s\n",
730
ldb_dn_get_linearized(bridge->dn)));
732
talloc_free(tmp_ctx);
733
return NT_STATUS_INTERNAL_DB_CORRUPTION;
736
ret = dsdb_find_guid_by_dn(ldb, dn, &site_link_guid);
737
if (ret != LDB_SUCCESS) {
738
DEBUG(1, (__location__ ": failed to find objectGUID "
739
"for object %s: %s\n",
740
ldb_dn_get_linearized(dn),
743
talloc_free(tmp_ctx);
744
return NT_STATUS_INTERNAL_DB_CORRUPTION;
747
edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
749
DEBUG(1, (__location__ ": failed to find a graph edge "
751
GUID_string(tmp_ctx, &site_link_guid)));
753
talloc_free(tmp_ctx);
754
return NT_STATUS_INTERNAL_DB_CORRUPTION;
757
if (GUID_equal(&edge->type, &type)) {
758
struct GUID *new_data;
760
new_data = talloc_realloc(set, set->edge_ids.data,
762
set->edge_ids.count + 1);
763
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
764
new_data[set->edge_ids.count] = site_link_guid;
765
set->edge_ids.data = new_data;
766
set->edge_ids.count++;
770
*_set = talloc_steal(graph, set);
771
talloc_free(tmp_ctx);
776
* set up a kcctpl_graph, populated with a kcctpl_vertex for each site object, a
777
* kcctpl_multi_edge for each siteLink object, and a kcctpl_multi_edge_set for
778
* each siteLinkBridge object (or implied siteLinkBridge).
780
static NTSTATUS kcctpl_setup_graph(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
781
struct kcctpl_graph **_graph)
783
struct kcctpl_graph *graph;
784
struct ldb_dn *sites_dn, *transports_dn;
786
struct ldb_result *res;
787
const char * const transport_attrs[] = { "objectGUID", NULL };
788
const char * const site_attrs[] = { "objectGUID", "options", NULL };
789
const char * const attrs[] = { "objectGUID", "cost", "options",
790
"replInterval", "schedule", NULL };
791
const char * const site_link_bridge_attrs[] = { "objectGUID",
795
struct GUID_list vertex_ids;
798
struct ldb_message *site;
801
tmp_ctx = talloc_new(mem_ctx);
802
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
804
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
806
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
808
talloc_free(tmp_ctx);
809
return NT_STATUS_INTERNAL_DB_CORRUPTION;
812
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE,
813
site_attrs, "objectClass=site");
814
if (ret != LDB_SUCCESS) {
815
DEBUG(1, (__location__ ": failed to find site objects under "
816
"%s: %s\n", ldb_dn_get_linearized(sites_dn),
819
talloc_free(tmp_ctx);
820
return NT_STATUS_INTERNAL_DB_CORRUPTION;
823
ZERO_STRUCT(vertex_ids);
824
for (i = 0; i < res->count; i++) {
825
struct GUID guid, *new_data;
827
guid = samdb_result_guid(res->msgs[i], "objectGUID");
829
new_data = talloc_realloc(tmp_ctx, vertex_ids.data, struct GUID,
830
vertex_ids.count + 1);
831
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
832
new_data[vertex_ids.count] = guid;
833
vertex_ids.data = new_data;
837
status = kcctpl_create_graph(tmp_ctx, vertex_ids, &graph);
838
if (NT_STATUS_IS_ERR(status)) {
839
DEBUG(1, (__location__ ": failed to create graph: %s\n",
842
talloc_free(tmp_ctx);
846
site = kcctpl_local_site(ldb, tmp_ctx);
848
DEBUG(1, (__location__ ": failed to find our own local DC's "
851
talloc_free(tmp_ctx);
852
return NT_STATUS_INTERNAL_DB_CORRUPTION;
854
site_opts = ldb_msg_find_attr_as_uint(site, "options", 0);
856
transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
857
if (!transports_dn) {
858
DEBUG(1, (__location__ ": failed to find our own Inter-Site "
861
talloc_free(tmp_ctx);
862
return NT_STATUS_INTERNAL_DB_CORRUPTION;
865
ret = ldb_search(ldb, tmp_ctx, &res, transports_dn, LDB_SCOPE_ONELEVEL,
866
transport_attrs, "objectClass=interSiteTransport");
867
if (ret != LDB_SUCCESS) {
868
DEBUG(1, (__location__ ": failed to find interSiteTransport "
869
"objects under %s: %s\n",
870
ldb_dn_get_linearized(transports_dn),
873
talloc_free(tmp_ctx);
874
return NT_STATUS_INTERNAL_DB_CORRUPTION;
877
for (i = 0; i < res->count; i++) {
878
struct ldb_message *transport;
879
struct ldb_result *res_site_link;
880
struct GUID transport_guid;
882
uint32_t transport_opts;
884
transport = res->msgs[i];
886
ret = ldb_search(ldb, tmp_ctx, &res_site_link, transport->dn,
887
LDB_SCOPE_SUBTREE, attrs,
888
"objectClass=siteLink");
889
if (ret != LDB_SUCCESS) {
890
DEBUG(1, (__location__ ": failed to find siteLink "
891
"objects under %s: %s\n",
892
ldb_dn_get_linearized(transport->dn),
895
talloc_free(tmp_ctx);
896
return NT_STATUS_INTERNAL_DB_CORRUPTION;
899
transport_guid = samdb_result_guid(transport, "objectGUID");
900
for (j = 0; j < res_site_link->count; j++) {
901
struct kcctpl_multi_edge *edge, *new_data;
903
status = kcctpl_create_edge(ldb, graph, transport_guid,
904
res_site_link->msgs[j],
906
if (NT_STATUS_IS_ERR(status)) {
907
DEBUG(1, (__location__ ": failed to create "
908
"edge: %s\n", nt_errstr(status)));
909
talloc_free(tmp_ctx);
913
new_data = talloc_realloc(graph, graph->edges.data,
914
struct kcctpl_multi_edge,
915
graph->edges.count + 1);
916
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
917
new_data[graph->edges.count] = *edge;
918
graph->edges.data = new_data;
919
graph->edges.count++;
922
transport_opts = ldb_msg_find_attr_as_uint(transport, "options", 0);
923
if (!(transport_opts & NTDSTRANSPORT_OPT_BRIDGES_REQUIRED) &&
924
!(site_opts & NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED)) {
925
struct kcctpl_multi_edge_set *edge_set, *new_data;
927
status = kcctpl_create_auto_edge_set(graph,
931
if (NT_STATUS_IS_ERR(status)) {
932
DEBUG(1, (__location__ ": failed to create "
933
"edge set: %s\n", nt_errstr(status)));
934
talloc_free(tmp_ctx);
938
new_data = talloc_realloc(graph, graph->edge_sets.data,
939
struct kcctpl_multi_edge_set,
940
graph->edge_sets.count + 1);
941
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
942
new_data[graph->edge_sets.count] = *edge_set;
943
graph->edge_sets.data = new_data;
944
graph->edge_sets.count++;
946
ret = ldb_search(ldb, tmp_ctx, &res_site_link,
947
transport->dn, LDB_SCOPE_SUBTREE,
948
site_link_bridge_attrs,
949
"objectClass=siteLinkBridge");
950
if (ret != LDB_SUCCESS) {
951
DEBUG(1, (__location__ ": failed to find "
952
"siteLinkBridge objects under %s: "
954
ldb_dn_get_linearized(transport->dn),
957
talloc_free(tmp_ctx);
958
return NT_STATUS_INTERNAL_DB_CORRUPTION;
961
for (j = 0; j < res_site_link->count; j++) {
962
struct ldb_message *bridge;
963
struct kcctpl_multi_edge_set *edge_set,
966
bridge = res_site_link->msgs[j];
967
status = kcctpl_create_edge_set(ldb, graph,
971
if (NT_STATUS_IS_ERR(status)) {
972
DEBUG(1, (__location__ ": failed to "
973
"create edge set: %s\n",
976
talloc_free(tmp_ctx);
980
new_data = talloc_realloc(graph,
981
graph->edge_sets.data,
982
struct kcctpl_multi_edge_set,
983
graph->edge_sets.count + 1);
984
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
986
new_data[graph->edge_sets.count] = *edge_set;
987
graph->edge_sets.data = new_data;
988
graph->edge_sets.count++;
993
*_graph = talloc_steal(mem_ctx, graph);
994
talloc_free(tmp_ctx);
999
* determine whether a given DC is known to be in a failed state.
1001
static NTSTATUS kcctpl_bridgehead_dc_failed(struct ldb_context *ldb,
1003
bool detect_failed_dcs,
1006
TALLOC_CTX *tmp_ctx;
1007
struct ldb_dn *settings_dn;
1008
struct ldb_result *res;
1009
const char * const attrs[] = { "options", NULL };
1011
struct ldb_message *settings;
1012
uint32_t settings_opts;
1015
tmp_ctx = talloc_new(ldb);
1016
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1018
settings_dn = samdb_ntds_settings_dn(ldb);
1020
DEBUG(1, (__location__ ": failed to find our own NTDS Settings "
1022
talloc_free(tmp_ctx);
1023
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1026
ret = ldb_search(ldb, tmp_ctx, &res, settings_dn, LDB_SCOPE_BASE, attrs,
1027
"objectClass=nTDSSiteSettings");
1028
if (ret != LDB_SUCCESS) {
1029
DEBUG(1, (__location__ ": failed to find site settings object "
1030
"%s: %s\n", ldb_dn_get_linearized(settings_dn),
1031
ldb_strerror(ret)));
1032
talloc_free(tmp_ctx);
1033
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1035
if (res->count == 0) {
1036
DEBUG(1, ("failed to find site settings object %s\n",
1037
ldb_dn_get_linearized(settings_dn)));
1038
talloc_free(tmp_ctx);
1039
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1042
settings = res->msgs[0];
1044
settings_opts = ldb_msg_find_attr_as_uint(settings, "options", 0);
1045
if (settings_opts & NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED) {
1047
} else if (true) { /* TODO: how to get kCCFailedLinks and
1048
kCCFailedConnections? */
1051
failed = detect_failed_dcs;
1055
talloc_free(tmp_ctx);
1056
return NT_STATUS_OK;
1060
* get all bridgehead DCs satisfying the given criteria.
1062
static NTSTATUS kcctpl_get_all_bridgehead_dcs(struct kccsrv_service *service,
1063
TALLOC_CTX *mem_ctx,
1064
struct GUID site_guid,
1065
struct ldb_message *cross_ref,
1066
struct ldb_message *transport,
1067
bool partial_replica_okay,
1068
bool detect_failed_dcs,
1069
struct message_list *_bridgeheads)
1071
struct message_list bridgeheads, all_dcs_in_site;
1072
TALLOC_CTX *tmp_ctx;
1073
struct ldb_result *res;
1074
struct ldb_dn *sites_dn, *schemas_dn;
1075
const char * const attrs[] = { "options", NULL };
1077
struct ldb_message *site, *schema;
1078
const char * const dc_attrs[] = { "objectGUID", "options", NULL };
1079
struct ldb_message_element *el;
1081
const char *transport_name, *transport_address_attr;
1084
ZERO_STRUCT(bridgeheads);
1086
tmp_ctx = talloc_new(mem_ctx);
1087
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1089
sites_dn = samdb_sites_dn(service->samdb, tmp_ctx);
1091
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
1093
talloc_free(tmp_ctx);
1094
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1097
ret = ldb_search(service->samdb, tmp_ctx, &res, sites_dn, LDB_SCOPE_ONELEVEL,
1098
attrs, "(&(objectClass=site)(objectGUID=%s))",
1099
GUID_string(tmp_ctx, &site_guid));
1100
if (ret != LDB_SUCCESS) {
1101
DEBUG(1, (__location__ ": failed to find site object %s: %s\n",
1102
GUID_string(tmp_ctx, &site_guid),
1103
ldb_strerror(ret)));
1105
talloc_free(tmp_ctx);
1106
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1108
if (res->count == 0) {
1109
DEBUG(1, (__location__ ": failed to find site object %s\n",
1110
GUID_string(tmp_ctx, &site_guid)));
1112
talloc_free(tmp_ctx);
1113
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1115
site = res->msgs[0];
1117
schemas_dn = ldb_get_schema_basedn(service->samdb);
1119
DEBUG(1, (__location__ ": failed to find our own Schemas DN\n"));
1121
talloc_free(tmp_ctx);
1122
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1125
ret = ldb_search(service->samdb, tmp_ctx, &res, schemas_dn, LDB_SCOPE_SUBTREE,
1127
"(&(lDAPDisplayName=nTDSDSA)(objectClass=classSchema))");
1128
if (ret != LDB_SUCCESS) {
1129
DEBUG(1, (__location__ ": failed to find classSchema object :"
1130
"%s\n", ldb_strerror(ret)));
1132
talloc_free(tmp_ctx);
1133
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1135
if (res->count == 0) {
1136
DEBUG(1, (__location__ ": failed to find classSchema "
1139
talloc_free(tmp_ctx);
1140
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1142
schema = res->msgs[0];
1144
ZERO_STRUCT(all_dcs_in_site);
1146
ret = ldb_search(service->samdb, tmp_ctx, &res, site->dn, LDB_SCOPE_SUBTREE,
1147
dc_attrs, "objectCategory=%s",
1148
ldb_dn_get_linearized(schema->dn));
1149
if (ret != LDB_SUCCESS) {
1150
DEBUG(1, (__location__ ": failed to find DCs objects :%s\n",
1151
ldb_strerror(ret)));
1153
talloc_free(tmp_ctx);
1154
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1157
el = ldb_msg_find_element(transport, "bridgeheadServerListBL");
1159
transport_name = ldb_msg_find_attr_as_string(transport, "name", NULL);
1160
if (!transport_name) {
1161
DEBUG(1, (__location__ ": failed to find name attribute of "
1162
"object %s\n", ldb_dn_get_linearized(transport->dn)));
1164
talloc_free(tmp_ctx);
1165
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1168
transport_address_attr = ldb_msg_find_attr_as_string(transport,
1169
"transportAddressAttribute",
1171
if (!transport_address_attr) {
1172
DEBUG(1, (__location__ ": failed to find "
1173
"transportAddressAttribute attribute of object %s\n",
1174
ldb_dn_get_linearized(transport->dn)));
1176
talloc_free(tmp_ctx);
1177
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1180
site_opts = ldb_msg_find_attr_as_uint(site, "options", 0);
1182
for (i = 0; i < res->count; i++) {
1183
struct ldb_message *dc, *new_data;
1184
struct ldb_dn *parent_dn;
1185
uint64_t behavior_version;
1186
const char *dc_transport_address;
1187
struct ldb_result *parent_res;
1188
const char *parent_attrs[] = { transport_address_attr, NULL };
1190
struct GUID dc_guid;
1195
parent_dn = ldb_dn_get_parent(tmp_ctx, dc->dn);
1197
DEBUG(1, (__location__ ": failed to get parent DN of "
1198
"%s\n", ldb_dn_get_linearized(dc->dn)));
1200
talloc_free(tmp_ctx);
1201
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1204
if (el && (el->num_values >= 1)) {
1210
for (j = 0; j < el->num_values; j++) {
1214
val = el->values[j];
1216
dn = ldb_dn_from_ldb_val(tmp_ctx, service->samdb, &val);
1218
DEBUG(1, (__location__ ": failed to read a DN "
1219
"from bridgeheadServerListBL "
1220
"attribute of %s\n",
1221
ldb_dn_get_linearized(transport->dn)));
1223
talloc_free(tmp_ctx);
1224
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1227
if (ldb_dn_compare(dn, parent_dn) == 0) {
1238
/* TODO: if dc is in the same site as the local DC */
1240
/* TODO: if a replica of cr!nCName is not in the set of
1241
* NC replicas that "should be present" on 'dc' */
1242
/* TODO: a partial replica of the NC "should be
1244
if (true || (true && !partial_replica_okay)) {
1248
/* TODO: if an NC replica of cr!nCName is not in the set
1249
* of NC replicas that "are present" on 'dc' */
1250
/* TODO: a partial replica of the NC "is present" */
1251
if (true || (true && !partial_replica_okay)) {
1256
behavior_version = ldb_msg_find_attr_as_int64(dc,
1257
"msDS-Behavior-Version", 0);
1258
/* TODO: cr!nCName corresponds to default NC */
1259
if (service->am_rodc && true && behavior_version < DS_BEHAVIOR_WIN2008) {
1263
ret = ldb_search(service->samdb, tmp_ctx, &parent_res, parent_dn,
1264
LDB_SCOPE_BASE, parent_attrs , NULL);
1266
dc_transport_address = ldb_msg_find_attr_as_string(parent_res->msgs[0],
1267
transport_address_attr,
1270
if (strncmp(transport_name, "IP", 2) != 0 &&
1271
dc_transport_address == NULL) {
1275
dc_guid = samdb_result_guid(dc, "objectGUID");
1277
status = kcctpl_bridgehead_dc_failed(service->samdb, dc_guid,
1280
if (NT_STATUS_IS_ERR(status)) {
1281
DEBUG(1, (__location__ ": failed to check if "
1282
"bridgehead DC has failed: %s\n",
1283
nt_errstr(status)));
1285
talloc_free(tmp_ctx);
1293
new_data = talloc_realloc(tmp_ctx, bridgeheads.data,
1295
bridgeheads.count + 1);
1296
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1297
new_data[bridgeheads.count + 1] = *dc;
1298
bridgeheads.data = new_data;
1299
bridgeheads.count++;
1302
if (site_opts & NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED) {
1303
qsort(bridgeheads.data, bridgeheads.count,
1304
sizeof(struct ldb_message), kcctpl_sort_bridgeheads);
1306
kcctpl_shuffle_bridgeheads(bridgeheads);
1309
talloc_steal(mem_ctx, bridgeheads.data);
1310
*_bridgeheads = bridgeheads;
1311
talloc_free(tmp_ctx);
1312
return NT_STATUS_OK;
1316
* get a bridgehead DC.
1318
static NTSTATUS kcctpl_get_bridgehead_dc(struct kccsrv_service *service,
1319
TALLOC_CTX *mem_ctx,
1320
struct GUID site_guid,
1321
struct ldb_message *cross_ref,
1322
struct ldb_message *transport,
1323
bool partial_replica_okay,
1324
bool detect_failed_dcs,
1325
struct ldb_message **_dsa)
1327
struct message_list dsa_list;
1330
status = kcctpl_get_all_bridgehead_dcs(service, mem_ctx,
1331
site_guid, cross_ref, transport,
1332
partial_replica_okay,
1333
detect_failed_dcs, &dsa_list);
1334
if (NT_STATUS_IS_ERR(status)) {
1335
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
1336
"%s\n", nt_errstr(status)));
1340
*_dsa = (dsa_list.count == 0) ? NULL : &dsa_list.data[0];
1342
return NT_STATUS_OK;
1346
* color each vertex to indicate which kinds of NC replicas it contains.
1348
static NTSTATUS kcctpl_color_vertices(struct kccsrv_service *service,
1349
struct kcctpl_graph *graph,
1350
struct ldb_message *cross_ref,
1351
bool detect_failed_dcs,
1352
bool *_found_failed_dcs)
1354
TALLOC_CTX *tmp_ctx;
1355
struct ldb_dn *sites_dn;
1356
bool found_failed_dcs, partial_replica_okay;
1358
struct ldb_message *site;
1359
struct ldb_result *res;
1361
struct GUID site_guid;
1362
struct kcctpl_vertex *site_vertex;
1364
found_failed_dcs = false;
1366
tmp_ctx = talloc_new(service);
1367
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1369
sites_dn = samdb_sites_dn(service->samdb, tmp_ctx);
1371
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
1373
talloc_free(tmp_ctx);
1374
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1377
for (i = 0; i < graph->vertices.count; i++) {
1378
struct kcctpl_vertex *vertex;
1379
struct ldb_dn *nc_name;
1380
/* TODO: set 'attrs' with its corresponding values */
1381
const char * const attrs[] = { NULL };
1383
vertex = &graph->vertices.data[i];
1385
ret = ldb_search(service->samdb, tmp_ctx, &res, sites_dn,
1386
LDB_SCOPE_SUBTREE, attrs, "objectGUID=%s",
1387
GUID_string(tmp_ctx, &vertex->id));
1388
if (ret != LDB_SUCCESS) {
1389
DEBUG(1, (__location__ ": failed to find site object "
1390
"%s: %s\n", GUID_string(tmp_ctx, &vertex->id),
1391
ldb_strerror(ret)));
1393
talloc_free(tmp_ctx);
1394
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1396
if (res->count == 0) {
1397
DEBUG(1, (__location__ ": failed to find site object "
1398
"%s\n", GUID_string(tmp_ctx, &vertex->id)));
1400
talloc_free(tmp_ctx);
1401
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1403
site = res->msgs[0];
1405
nc_name = samdb_result_dn(service->samdb, tmp_ctx, cross_ref,
1408
DEBUG(1, (__location__ ": failed to find nCName "
1409
"attribute of object %s\n",
1410
ldb_dn_get_linearized(cross_ref->dn)));
1412
talloc_free(tmp_ctx);
1413
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1416
if (true) { /* TODO: site contains 1+ DCs with full replicas of
1418
vertex->color = RED;
1419
} else if (true) { /* TODO: site contains 1+ partial replicas of
1421
vertex->color = BLACK;
1423
vertex->color = WHITE;
1427
site = kcctpl_local_site(service->samdb, tmp_ctx);
1429
DEBUG(1, (__location__ ": failed to find our own local DC's "
1432
talloc_free(tmp_ctx);
1433
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1435
site_guid = samdb_result_guid(site, "objectGUID");
1437
site_vertex = kcctpl_find_vertex_by_guid(graph, site_guid);
1439
DEBUG(1, (__location__ ": failed to find a vertex edge with "
1440
"GUID=%s\n", GUID_string(tmp_ctx, &site_guid)));
1442
talloc_free(tmp_ctx);
1443
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1446
partial_replica_okay = (site_vertex->color == BLACK);
1448
cr_flags = ldb_msg_find_attr_as_int64(cross_ref, "systemFlags", 0);
1450
for (i = 0; i < graph->vertices.count; i++) {
1451
struct kcctpl_vertex *vertex;
1452
struct ldb_dn *transports_dn;
1453
const char * const attrs[] = { "objectGUID", "name",
1454
"transportAddressAttribute",
1458
vertex = &graph->vertices.data[i];
1460
transports_dn = kcctpl_transports_dn(service->samdb, tmp_ctx);
1461
if (!transports_dn) {
1462
DEBUG(1, (__location__ ": failed to find our own "
1463
"Inter-Site Transports DN\n"));
1465
talloc_free(tmp_ctx);
1466
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1469
ret = ldb_search(service->samdb, tmp_ctx, &res, transports_dn,
1470
LDB_SCOPE_ONELEVEL, attrs,
1471
"objectClass=interSiteTransport");
1472
if (ret != LDB_SUCCESS) {
1473
DEBUG(1, (__location__ ": failed to find "
1474
"interSiteTransport objects under %s: %s\n",
1475
ldb_dn_get_linearized(transports_dn),
1476
ldb_strerror(ret)));
1478
talloc_free(tmp_ctx);
1479
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1482
for (j = 0; j < res->count; j++) {
1483
struct ldb_message *transport, *bridgehead;
1484
const char *transport_name;
1485
struct GUID transport_guid, *new_data;
1488
transport = res->msgs[j];
1490
transport_name = ldb_msg_find_attr_as_string(transport,
1492
if (!transport_name) {
1493
DEBUG(1, (__location__ ": failed to find name "
1494
"attribute of object %s\n",
1495
ldb_dn_get_linearized(transport->dn)));
1497
talloc_free(tmp_ctx);
1498
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1501
transport_guid = samdb_result_guid(transport,
1504
if (site_vertex->color == RED &&
1505
strncmp(transport_name, "IP", 2) != 0 &&
1506
(cr_flags & FLAG_CR_NTDS_DOMAIN)) {
1510
if (!kcctpl_find_edge_by_vertex_guid(graph,
1515
status = kcctpl_get_bridgehead_dc(service, tmp_ctx,
1517
cross_ref, transport,
1518
partial_replica_okay,
1521
if (NT_STATUS_IS_ERR(status)) {
1522
DEBUG(1, (__location__ ": failed to get a "
1523
"bridgehead DC: %s\n",
1524
nt_errstr(status)));
1526
talloc_free(tmp_ctx);
1530
found_failed_dcs = true;
1534
new_data = talloc_realloc(vertex,
1535
vertex->accept_red_red.data,
1537
vertex->accept_red_red.count + 1);
1538
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1539
new_data[vertex->accept_red_red.count + 1] = transport_guid;
1540
vertex->accept_red_red.data = new_data;
1541
vertex->accept_red_red.count++;
1543
new_data = talloc_realloc(vertex,
1544
vertex->accept_black.data,
1546
vertex->accept_black.count + 1);
1547
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1548
new_data[vertex->accept_black.count + 1] = transport_guid;
1549
vertex->accept_black.data = new_data;
1550
vertex->accept_black.count++;
1554
*_found_failed_dcs = found_failed_dcs;
1555
talloc_free(tmp_ctx);
1556
return NT_STATUS_OK;
1560
* setup the fields of the vertices that are relevant to Phase I (Dijkstra's
1561
* Algorithm). for each vertex, set up its cost, root vertex and component. this
1562
* defines the shortest-path forest structures.
1564
static void kcctpl_setup_vertices(struct kcctpl_graph *graph)
1568
for (i = 0; i < graph->vertices.count; i++) {
1569
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
1571
if (vertex->color == WHITE) {
1572
vertex->repl_info.cost = UINT32_MAX;
1573
vertex->root_id = vertex->component_id = GUID_zero();
1575
vertex->repl_info.cost = 0;
1576
vertex->root_id = vertex->component_id = vertex->id;
1579
vertex->repl_info.interval = 0;
1580
vertex->repl_info.options = 0xFFFFFFFF;
1581
ZERO_STRUCT(vertex->repl_info.schedule);
1582
vertex->demoted = false;
1587
* demote one vertex if necessary.
1589
static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex *vertex,
1592
if (vertex->color == WHITE) {
1596
if (!kcctpl_guid_list_contains(vertex->accept_black, type) &&
1597
!kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
1598
vertex->repl_info.cost = UINT32_MAX;
1599
vertex->root_id = GUID_zero();
1600
vertex->demoted = true;
1605
* clear the demoted state of a vertex.
1607
static void kcctpl_undemote_one_vertex(struct kcctpl_vertex *vertex)
1609
if (vertex->color == WHITE) {
1613
vertex->repl_info.cost = 0;
1614
vertex->root_id = vertex->id;
1615
vertex->demoted = false;
1619
* returns the id of the component containing 'vertex' by traversing the up-tree
1620
* implied by the component pointers.
1622
static struct GUID kcctpl_get_component_id(struct kcctpl_graph *graph,
1623
struct kcctpl_vertex *vertex)
1625
struct kcctpl_vertex *u;
1629
while (!GUID_equal(&u->component_id, &u->id)) {
1630
u = kcctpl_find_vertex_by_guid(graph, u->component_id);
1636
while (!GUID_equal(&u->component_id, &u->id)) {
1637
struct kcctpl_vertex *w;
1639
w = kcctpl_find_vertex_by_guid(graph, u->component_id);
1640
u->component_id = root;
1648
* copy all spanning tree edges from 'output_edges' that contain the vertex for
1649
* DCs in the local DC's site.
1651
static NTSTATUS kcctpl_copy_output_edges(struct kccsrv_service *service,
1652
TALLOC_CTX *mem_ctx,
1653
struct kcctpl_graph *graph,
1654
struct kcctpl_multi_edge_list output_edges,
1655
struct kcctpl_multi_edge_list *_copy)
1657
struct kcctpl_multi_edge_list copy;
1658
TALLOC_CTX *tmp_ctx;
1659
struct ldb_message *site;
1660
struct GUID site_guid;
1665
tmp_ctx = talloc_new(service);
1666
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1668
site = kcctpl_local_site(service->samdb, tmp_ctx);
1670
DEBUG(1, (__location__ ": failed to find our own local DC's "
1673
talloc_free(tmp_ctx);
1674
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1676
site_guid = samdb_result_guid(site, "objectGUID");
1678
for (i = 0; i < output_edges.count; i++) {
1679
struct kcctpl_multi_edge *edge;
1680
struct kcctpl_vertex *vertex1, *vertex2;
1682
edge = &output_edges.data[i];
1684
vertex1 = kcctpl_find_vertex_by_guid(graph,
1685
edge->vertex_ids.data[0]);
1687
DEBUG(1, (__location__ ": failed to find vertex %s\n",
1688
GUID_string(tmp_ctx,
1689
&edge->vertex_ids.data[0])));
1690
talloc_free(tmp_ctx);
1691
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1694
vertex2 = kcctpl_find_vertex_by_guid(graph,
1695
edge->vertex_ids.data[1]);
1697
DEBUG(1, (__location__ ": failed to find vertex %s\n",
1698
GUID_string(tmp_ctx,
1699
&edge->vertex_ids.data[1])));
1700
talloc_free(tmp_ctx);
1701
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1704
if (GUID_equal(&vertex1->id, &site_guid) ||
1705
GUID_equal(&vertex2->id, &site_guid)) {
1706
struct kcctpl_multi_edge *new_data;
1708
if ((vertex1->color == BLACK ||
1709
vertex2->color == BLACK) &&
1710
vertex1->dist_to_red != UINT32_MAX) {
1712
edge->directed = true;
1714
if (vertex2->dist_to_red <
1715
vertex1->dist_to_red) {
1718
tmp = edge->vertex_ids.data[0];
1719
edge->vertex_ids.data[0] = edge->vertex_ids.data[1];
1720
edge->vertex_ids.data[1] = tmp;
1724
new_data = talloc_realloc(tmp_ctx, copy.data,
1725
struct kcctpl_multi_edge,
1727
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1728
new_data[copy.count + 1] = *edge;
1729
copy.data = new_data;
1734
talloc_steal(mem_ctx, copy.data);
1735
talloc_free(tmp_ctx);
1737
return NT_STATUS_OK;
1741
* build the initial sequence for use with Dijkstra's algorithm. it will contain
1742
* the red and black vertices as root vertices, unless these vertices accept no
1743
* edges of the current 'type', or unless black vertices are not being
1746
static NTSTATUS kcctpl_setup_dijkstra(TALLOC_CTX *mem_ctx,
1747
struct kcctpl_graph *graph,
1748
struct GUID type, bool include_black,
1749
struct kcctpl_vertex_list *_vertices)
1751
struct kcctpl_vertex_list vertices;
1754
kcctpl_setup_vertices(graph);
1756
ZERO_STRUCT(vertices);
1758
for (i = 0; i < graph->vertices.count; i++) {
1759
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
1761
if (vertex->color == WHITE) {
1765
if ((vertex->color == BLACK && !include_black) ||
1766
!kcctpl_guid_list_contains(vertex->accept_black, type) ||
1767
!kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
1768
vertex->repl_info.cost = UINT32_MAX;
1769
vertex->root_id = GUID_zero();
1770
vertex->demoted = true;
1772
struct kcctpl_vertex *new_data;
1774
new_data = talloc_realloc(mem_ctx, vertices.data,
1775
struct kcctpl_vertex,
1776
vertices.count + 1);
1777
NT_STATUS_HAVE_NO_MEMORY(new_data);
1778
new_data[vertices.count] = *vertex;
1779
vertices.data = new_data;
1784
*_vertices = vertices;
1785
return NT_STATUS_OK;
1789
* merge schedules, replication intervals, options and costs.
1791
static bool kcctpl_combine_repl_info(struct kcctpl_graph *graph,
1792
struct kcctpl_repl_info *ria,
1793
struct kcctpl_repl_info *rib,
1794
struct kcctpl_repl_info *ric)
1796
uint8_t schedule[84];
1801
is_available = false;
1802
for (i = 0; i < 84; i++) {
1803
schedule[i] = ria->schedule[i] & rib->schedule[i];
1805
if (schedule[i] == 1) {
1806
is_available = true;
1809
if (!is_available) {
1813
ric_cost = ria->cost + rib->cost;
1814
ric->cost = (ric_cost < 0) ? UINT32_MAX : ric_cost;
1816
ric->interval = MAX(ria->interval, rib->interval);
1817
ric->options = ria->options & rib->options;
1818
memcpy(&ric->schedule, &schedule, 84);
1824
* helper function for Dijkstra's algorithm. a new path has been found from a
1825
* root vertex to vertex 'vertex2'. this path is ('vertex1->root, ..., vertex1,
1826
* vertex2'). 'edge' is the edge connecting 'vertex1' and 'vertex2'. if this new
1827
* path is better (in this case cheaper, or has a longer schedule), update
1828
* 'vertex2' to use the new path.
1830
static NTSTATUS kcctpl_try_new_path(TALLOC_CTX *mem_ctx,
1831
struct kcctpl_graph *graph,
1832
struct kcctpl_vertex_list vertices,
1833
struct kcctpl_vertex *vertex1,
1834
struct kcctpl_multi_edge *edge,
1835
struct kcctpl_vertex *vertex2)
1837
struct kcctpl_repl_info new_repl_info;
1839
uint32_t i, new_duration, old_duration;
1841
ZERO_STRUCT(new_repl_info);
1843
intersect = kcctpl_combine_repl_info(graph, &vertex1->repl_info,
1844
&edge->repl_info, &new_repl_info);
1846
if (new_repl_info.cost > vertex2->repl_info.cost) {
1847
return NT_STATUS_OK;
1850
if (new_repl_info.cost < vertex2->repl_info.cost && !intersect) {
1851
return NT_STATUS_OK;
1854
new_duration = old_duration = 0;
1855
for (i = 0; i < 84; i++) {
1856
if (new_repl_info.schedule[i] == 1) {
1860
if (vertex2->repl_info.schedule[i] == 1) {
1865
if (new_repl_info.cost < vertex2->repl_info.cost ||
1866
new_duration > old_duration) {
1867
struct kcctpl_vertex *new_data;
1869
vertex2->root_id = vertex1->root_id;
1870
vertex2->component_id = vertex1->component_id;
1871
vertex2->repl_info = new_repl_info;
1873
new_data = talloc_realloc(mem_ctx, vertices.data,
1874
struct kcctpl_vertex,
1875
vertices.count + 1);
1876
NT_STATUS_HAVE_NO_MEMORY(new_data);
1877
new_data[vertices.count + 1] = *vertex2;
1878
vertices.data = new_data;
1882
return NT_STATUS_OK;
1886
* run Dijkstra's algorithm with the red (and possibly black) vertices as the
1887
* root vertices, and build up a shortest-path forest.
1889
static NTSTATUS kcctpl_dijkstra(struct kcctpl_graph *graph, struct GUID type,
1892
TALLOC_CTX *tmp_ctx;
1893
struct kcctpl_vertex_list vertices;
1896
tmp_ctx = talloc_new(graph);
1897
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
1899
status = kcctpl_setup_dijkstra(tmp_ctx, graph, type, include_black,
1901
if (NT_STATUS_IS_ERR(status)) {
1902
DEBUG(1, (__location__ ": failed to build the initial sequence "
1903
"for Dijkstra's algorithm: %s\n", nt_errstr(status)));
1905
talloc_free(tmp_ctx);
1909
while (vertices.count > 0) {
1910
uint32_t minimum_cost, minimum_index, i;
1911
struct kcctpl_vertex *minimum_vertex, *new_data;
1913
minimum_cost = UINT32_MAX;
1915
minimum_vertex = NULL;
1916
for (i = 0; i < vertices.count; i++) {
1917
struct kcctpl_vertex *vertex = &vertices.data[i];
1919
if (vertex->repl_info.cost < minimum_cost) {
1920
minimum_cost = vertex->repl_info.cost;
1921
minimum_vertex = vertex;
1923
} else if (vertex->repl_info.cost == minimum_cost &&
1924
GUID_compare(&vertex->id,
1925
&minimum_vertex->id) < 0) {
1926
minimum_vertex = vertex;
1931
if (minimum_index < vertices.count - 1) {
1932
memcpy(&vertices.data[minimum_index + 1],
1933
&vertices.data[minimum_index],
1934
vertices.count - minimum_index - 1);
1936
new_data = talloc_realloc(tmp_ctx, vertices.data,
1937
struct kcctpl_vertex,
1938
vertices.count - 1);
1939
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
1940
talloc_free(vertices.data);
1941
vertices.data = new_data;
1944
for (i = 0; i < graph->edges.count; i++) {
1945
struct kcctpl_multi_edge *edge = &graph->edges.data[i];
1947
if (kcctpl_guid_list_contains(minimum_vertex->edge_ids,
1951
for (j = 0; j < edge->vertex_ids.count; j++) {
1952
struct GUID vertex_id;
1953
struct kcctpl_vertex *vertex;
1955
vertex_id = edge->vertex_ids.data[j];
1956
vertex = kcctpl_find_vertex_by_guid(graph,
1959
DEBUG(1, (__location__
1962
GUID_string(tmp_ctx,
1965
talloc_free(tmp_ctx);
1966
return NT_STATUS_INTERNAL_DB_CORRUPTION;
1969
kcctpl_try_new_path(tmp_ctx, graph,
1978
talloc_free(tmp_ctx);
1979
return NT_STATUS_OK;
1983
* add an edge to the list of edges that will be processed with Kruskal's. the
1984
* endpoints are in fact the root of the vertices to pass in, so the endpoints
1985
* are always colored vertices.
1987
static NTSTATUS kcctpl_add_int_edge(TALLOC_CTX *mem_ctx,
1988
struct kcctpl_graph *graph,
1989
struct kcctpl_internal_edge_list internal_edges,
1990
struct kcctpl_multi_edge *edge,
1991
struct kcctpl_vertex *vertex1,
1992
struct kcctpl_vertex *vertex2)
1994
struct kcctpl_vertex *root1, *root2;
1995
bool red_red, found;
1996
struct kcctpl_repl_info repl_info1, repl_info2;
1997
struct kcctpl_internal_edge new_internal_edge, *new_data;
2000
root1 = kcctpl_find_vertex_by_guid(graph, vertex1->root_id);
2002
TALLOC_CTX *tmp_ctx = talloc_new(graph);
2003
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2005
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2006
GUID_string(tmp_ctx, &vertex1->root_id)));
2008
talloc_free(tmp_ctx);
2009
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2012
root2 = kcctpl_find_vertex_by_guid(graph, vertex2->root_id);
2014
TALLOC_CTX *tmp_ctx = talloc_new(graph);
2015
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2017
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2018
GUID_string(tmp_ctx, &vertex2->root_id)));
2020
talloc_free(tmp_ctx);
2021
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2024
red_red = (root1->color == RED && root2->color == RED);
2027
if (!kcctpl_guid_list_contains(root1->accept_red_red,
2029
!kcctpl_guid_list_contains(root2->accept_red_red,
2031
return NT_STATUS_OK;
2033
} else if (!kcctpl_guid_list_contains(root1->accept_black,
2035
!kcctpl_guid_list_contains(root2->accept_black,
2037
return NT_STATUS_OK;
2040
if (!kcctpl_combine_repl_info(graph, &vertex1->repl_info,
2041
&vertex2->repl_info, &repl_info1) ||
2042
!kcctpl_combine_repl_info(graph, &repl_info1, &edge->repl_info,
2044
return NT_STATUS_OK;
2047
new_internal_edge.v1id = root1->id;
2048
new_internal_edge.v2id = root2->id;
2049
new_internal_edge.red_red = red_red;
2050
new_internal_edge.repl_info = repl_info2;
2051
new_internal_edge.type = edge->type;
2053
if (GUID_compare(&new_internal_edge.v1id,
2054
&new_internal_edge.v2id) > 0) {
2055
struct GUID tmp_guid = new_internal_edge.v1id;
2057
new_internal_edge.v1id = new_internal_edge.v2id;
2058
new_internal_edge.v2id = tmp_guid;
2062
for (i = 0; i < internal_edges.count; i++) {
2063
struct kcctpl_internal_edge *ie = &internal_edges.data[i];
2065
if (kcctpl_internal_edge_equal(ie, &new_internal_edge)) {
2070
return NT_STATUS_OK;
2073
new_data = talloc_realloc(mem_ctx, internal_edges.data,
2074
struct kcctpl_internal_edge,
2075
internal_edges.count + 1);
2076
NT_STATUS_HAVE_NO_MEMORY(new_data);
2077
new_data[internal_edges.count + 1] = new_internal_edge;
2078
internal_edges.data = new_data;
2079
internal_edges.count++;
2081
return NT_STATUS_OK;
2085
* after running Dijkstra's algorithm, this function examines a multi-edge and
2086
* adds internal edges between every tree connected by this edge.
2088
static NTSTATUS kcctpl_process_edge(TALLOC_CTX *mem_ctx,
2089
struct kcctpl_graph *graph,
2090
struct kcctpl_multi_edge *edge,
2091
struct kcctpl_internal_edge_list internal_edges)
2093
TALLOC_CTX *tmp_ctx;
2094
struct kcctpl_vertex_list vertices;
2096
struct kcctpl_vertex *best_vertex;
2098
ZERO_STRUCT(vertices);
2100
tmp_ctx = talloc_new(mem_ctx);
2101
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2103
for (i = 0; i < edge->vertex_ids.count; i++) {
2105
struct kcctpl_vertex *vertex, *new_data;
2107
id = edge->vertex_ids.data[i];
2109
vertex = kcctpl_find_vertex_by_guid(graph, id);
2111
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2112
GUID_string(tmp_ctx, &id)));
2114
talloc_free(tmp_ctx);
2115
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2118
new_data = talloc_realloc(tmp_ctx, vertices.data,
2119
struct kcctpl_vertex,
2120
vertices.count + 1);
2121
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
2122
new_data[vertices.count] = *vertex;
2123
vertices.data = new_data;
2127
qsort(vertices.data, vertices.count, sizeof(struct kcctpl_vertex),
2128
kcctpl_sort_vertices);
2130
best_vertex = &vertices.data[0];
2132
for (i = 0; i < edge->vertex_ids.count; i++) {
2133
struct GUID id, empty_id = GUID_zero();
2134
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2136
id = edge->vertex_ids.data[i];
2138
vertex = kcctpl_find_vertex_by_guid(graph, id);
2140
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2141
GUID_string(tmp_ctx, &id)));
2143
talloc_free(tmp_ctx);
2144
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2147
if (!GUID_equal(&vertex->component_id, &empty_id) &&
2148
!GUID_equal(&vertex->root_id, &empty_id)) {
2152
if (!GUID_equal(&best_vertex->component_id,
2154
!GUID_equal(&best_vertex->root_id, &empty_id) &&
2155
!GUID_equal(&vertex->component_id, &empty_id) &&
2156
!GUID_equal(&vertex->root_id, &empty_id) &&
2157
!GUID_equal(&best_vertex->component_id,
2158
&vertex->component_id)) {
2161
status = kcctpl_add_int_edge(mem_ctx, graph,
2165
if (NT_STATUS_IS_ERR(status)) {
2166
DEBUG(1, (__location__ ": failed to add an "
2167
"internal edge for %s: %s\n",
2168
GUID_string(tmp_ctx, &vertex->id),
2169
nt_errstr(status)));
2170
talloc_free(tmp_ctx);
2176
talloc_free(tmp_ctx);
2177
return NT_STATUS_OK;
2181
* after running Dijkstra's algorithm to determine the shortest-path forest,
2182
* examine all edges in this edge set. find all inter-tree edges, from which to
2183
* build the list of 'internal edges', which will later be passed on to
2184
* Kruskal's algorithm.
2186
static NTSTATUS kcctpl_process_edge_set(TALLOC_CTX *mem_ctx,
2187
struct kcctpl_graph *graph,
2188
struct kcctpl_multi_edge_set *set,
2189
struct kcctpl_internal_edge_list internal_edges)
2194
for (i = 0; i < graph->edges.count; i++) {
2195
struct kcctpl_multi_edge *edge;
2199
edge = &graph->edges.data[i];
2201
for (j = 0; j < edge->vertex_ids.count; j++) {
2203
struct kcctpl_vertex *vertex;
2205
id = edge->vertex_ids.data[j];
2207
vertex = kcctpl_find_vertex_by_guid(graph, id);
2209
TALLOC_CTX *tmp_ctx;
2211
tmp_ctx = talloc_new(mem_ctx);
2212
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2214
DEBUG(1, (__location__ ": failed to "
2216
GUID_string(tmp_ctx, &id)));
2218
talloc_free(tmp_ctx);
2219
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2222
kcctpl_check_demote_one_vertex(vertex,
2226
status = kcctpl_process_edge(mem_ctx, graph, edge,
2228
if (NT_STATUS_IS_ERR(status)) {
2229
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2230
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2232
DEBUG(1, (__location__ ": failed to process "
2234
GUID_string(tmp_ctx, &edge->id),
2235
nt_errstr(status)));
2237
talloc_free(tmp_ctx);
2241
for (j = 0; j < edge->vertex_ids.count; j++) {
2243
struct kcctpl_vertex *vertex;
2245
id = edge->vertex_ids.data[j];
2247
vertex = kcctpl_find_vertex_by_guid(graph, id);
2249
TALLOC_CTX *tmp_ctx;
2251
tmp_ctx = talloc_new(mem_ctx);
2252
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2254
DEBUG(1, (__location__ ": failed to "
2256
GUID_string(tmp_ctx, &id)));
2258
talloc_free(tmp_ctx);
2259
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2262
kcctpl_undemote_one_vertex(vertex);
2266
for (i = 0; i < graph->edges.count; i++) {
2267
struct kcctpl_multi_edge *edge = &graph->edges.data[i];
2269
if (kcctpl_guid_list_contains(set->edge_ids,
2273
status = kcctpl_process_edge(mem_ctx, graph,
2276
if (NT_STATUS_IS_ERR(status)) {
2277
TALLOC_CTX *tmp_ctx;
2279
tmp_ctx = talloc_new(mem_ctx);
2280
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2282
DEBUG(1, (__location__ ": failed to "
2283
"process edge %s: %s\n",
2284
GUID_string(tmp_ctx,
2286
nt_errstr(status)));
2288
talloc_free(tmp_ctx);
2295
return NT_STATUS_OK;
2299
* a new edge, 'internal_edge', has been found for the spanning tree edge. add
2300
* this edge to the list of output edges.
2302
static NTSTATUS kcctpl_add_out_edge(TALLOC_CTX *mem_ctx,
2303
struct kcctpl_graph *graph,
2304
struct kcctpl_multi_edge_list output_edges,
2305
struct kcctpl_internal_edge *internal_edge)
2307
struct kcctpl_vertex *vertex1, *vertex2;
2308
TALLOC_CTX *tmp_ctx;
2309
struct kcctpl_multi_edge *new_edge, *new_data;
2310
struct GUID *new_data_id;
2312
tmp_ctx = talloc_new(mem_ctx);
2313
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2315
vertex1 = kcctpl_find_vertex_by_guid(graph, internal_edge->v1id);
2317
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2318
GUID_string(tmp_ctx, &internal_edge->v1id)));
2320
talloc_free(tmp_ctx);
2321
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2324
vertex2 = kcctpl_find_vertex_by_guid(graph, internal_edge->v2id);
2326
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2327
GUID_string(tmp_ctx, &internal_edge->v2id)));
2329
talloc_free(tmp_ctx);
2330
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2333
new_edge = talloc(tmp_ctx, struct kcctpl_multi_edge);
2334
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge, tmp_ctx);
2336
new_edge->id = GUID_random(); /* TODO: what should be new_edge->GUID? */
2337
new_edge->directed = false;
2339
new_edge->vertex_ids.data = talloc_array(new_edge, struct GUID, 2);
2340
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge->vertex_ids.data, tmp_ctx);
2342
new_edge->vertex_ids.data[0] = vertex1->id;
2343
new_edge->vertex_ids.data[1] = vertex2->id;
2344
new_edge->vertex_ids.count = 2;
2346
new_edge->type = internal_edge->type;
2347
new_edge->repl_info = internal_edge->repl_info;
2349
new_data = talloc_realloc(tmp_ctx, output_edges.data,
2350
struct kcctpl_multi_edge,
2351
output_edges.count + 1);
2352
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
2353
new_data[output_edges.count + 1] = *new_edge;
2354
output_edges.data = new_data;
2355
output_edges.count++;
2357
new_data_id = talloc_realloc(vertex1, vertex1->edge_ids.data,
2358
struct GUID, vertex1->edge_ids.count);
2359
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
2360
new_data_id[vertex1->edge_ids.count] = new_edge->id;
2361
talloc_free(vertex1->edge_ids.data);
2362
vertex1->edge_ids.data = new_data_id;
2363
vertex1->edge_ids.count++;
2365
new_data_id = talloc_realloc(vertex2, vertex2->edge_ids.data,
2366
struct GUID, vertex2->edge_ids.count);
2367
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
2368
new_data_id[vertex2->edge_ids.count] = new_edge->id;
2369
talloc_free(vertex2->edge_ids.data);
2370
vertex2->edge_ids.data = new_data_id;
2371
vertex2->edge_ids.count++;
2373
talloc_steal(graph, new_edge);
2374
talloc_steal(mem_ctx, output_edges.data);
2375
talloc_free(tmp_ctx);
2376
return NT_STATUS_OK;
2380
* run Kruskal's minimum-cost spanning tree algorithm on the internal edges
2381
* (that represent shortest paths in the original graph between colored
2384
static NTSTATUS kcctpl_kruskal(TALLOC_CTX *mem_ctx, struct kcctpl_graph *graph,
2385
struct kcctpl_internal_edge_list internal_edges,
2386
struct kcctpl_multi_edge_list *_output_edges)
2388
uint32_t i, num_expected_tree_edges, cst_edges;
2389
struct kcctpl_multi_edge_list output_edges;
2391
num_expected_tree_edges = 0;
2392
for (i = 0; i < graph->vertices.count; i++) {
2393
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2395
talloc_free(vertex->edge_ids.data);
2396
ZERO_STRUCT(vertex->edge_ids);
2398
if (vertex->color == RED || vertex->color == WHITE) {
2399
num_expected_tree_edges++;
2403
qsort(internal_edges.data, internal_edges.count,
2404
sizeof(struct kcctpl_internal_edge), kcctpl_sort_internal_edges);
2408
ZERO_STRUCT(output_edges);
2410
while (internal_edges.count > 0 &&
2411
cst_edges < num_expected_tree_edges) {
2412
struct kcctpl_internal_edge *edge, *new_data;
2413
struct kcctpl_vertex *vertex1, *vertex2;
2414
struct GUID comp1, comp2;
2416
edge = &internal_edges.data[0];
2418
vertex1 = kcctpl_find_vertex_by_guid(graph, edge->v1id);
2420
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2421
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2423
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2424
GUID_string(tmp_ctx, &edge->v1id)));
2426
talloc_free(tmp_ctx);
2427
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2430
vertex2 = kcctpl_find_vertex_by_guid(graph, edge->v2id);
2432
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2433
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2435
DEBUG(1, (__location__ ": failed to find vertex %s\n",
2436
GUID_string(tmp_ctx, &edge->v2id)));
2438
talloc_free(tmp_ctx);
2439
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2442
comp1 = kcctpl_get_component_id(graph, vertex1);
2443
comp2 = kcctpl_get_component_id(graph, vertex2);
2445
if (!GUID_equal(&comp1, &comp2)) {
2447
struct kcctpl_vertex *vertex;
2451
status = kcctpl_add_out_edge(mem_ctx, graph,
2452
output_edges, edge);
2453
if (NT_STATUS_IS_ERR(status)) {
2454
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2455
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2457
DEBUG(1, (__location__ ": failed to add an "
2458
"output edge between %s and %s: %s\n",
2459
GUID_string(tmp_ctx, &edge->v1id),
2460
GUID_string(tmp_ctx, &edge->v2id),
2461
nt_errstr(status)));
2463
talloc_free(tmp_ctx);
2467
vertex = kcctpl_find_vertex_by_guid(graph, comp1);
2469
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
2470
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2472
DEBUG(1, (__location__ ": failed to find "
2473
"vertex %s\n", GUID_string(tmp_ctx,
2476
talloc_free(tmp_ctx);
2477
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2479
vertex->component_id = comp2;
2482
internal_edges.data = internal_edges.data + 1;
2483
new_data = talloc_realloc(mem_ctx, internal_edges.data,
2484
struct kcctpl_internal_edge,
2485
internal_edges.count - 1);
2486
NT_STATUS_HAVE_NO_MEMORY(new_data);
2487
talloc_free(internal_edges.data);
2488
internal_edges.data = new_data;
2489
internal_edges.count--;
2492
*_output_edges = output_edges;
2493
return NT_STATUS_OK;
2497
* count the number of components. a component is considered to be a bunch of
2498
* colored vertices that are connected by the spanning tree. vertices whose
2499
* component ID is the same as their vertex ID are the root of the connected
2502
static uint32_t kcctpl_count_components(struct kcctpl_graph *graph)
2504
uint32_t num_components = 0, i;
2506
for (i = 0; i < graph->vertices.count; i++) {
2507
struct kcctpl_vertex *vertex;
2508
struct GUID component_id;
2510
vertex = &graph->vertices.data[i];
2512
if (vertex->color == WHITE) {
2516
component_id = kcctpl_get_component_id(graph, vertex);
2517
if (GUID_equal(&component_id, &vertex->id)) {
2518
vertex->component_index = num_components;
2523
return num_components;
2527
* calculate the spanning tree and return the edges that include the vertex for
2530
static NTSTATUS kcctpl_get_spanning_tree_edges(struct kccsrv_service *service,
2531
TALLOC_CTX *mem_ctx,
2532
struct kcctpl_graph *graph,
2533
uint32_t *_component_count,
2534
struct kcctpl_multi_edge_list *_st_edge_list)
2536
TALLOC_CTX *tmp_ctx;
2537
struct kcctpl_internal_edge_list internal_edges;
2538
uint32_t i, component_count;
2540
struct kcctpl_multi_edge_list output_edges, st_edge_list;
2542
ZERO_STRUCT(internal_edges);
2544
tmp_ctx = talloc_new(mem_ctx);
2545
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2547
for (i = 0; i < graph->edge_sets.count; i++) {
2548
struct kcctpl_multi_edge_set *set;
2549
struct GUID edge_type;
2552
set = &graph->edge_sets.data[i];
2554
edge_type = GUID_zero();
2556
for (j = 0; j < graph->vertices.count; j++) {
2557
struct kcctpl_vertex *vertex = &graph->vertices.data[j];
2559
talloc_free(vertex->edge_ids.data);
2560
ZERO_STRUCT(vertex->edge_ids.data);
2563
for (j = 0; j < set->edge_ids.count; j++) {
2564
struct GUID edge_id;
2565
struct kcctpl_multi_edge *edge;
2568
edge_id = set->edge_ids.data[j];
2569
edge = kcctpl_find_edge_by_guid(graph, edge_id);
2571
DEBUG(1, (__location__ ": failed to find a "
2572
"graph edge with ID=%s\n",
2573
GUID_string(tmp_ctx, &edge_id)));
2575
talloc_free(tmp_ctx);
2576
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2579
edge_type = edge->type;
2581
for (k = 0; k < edge->vertex_ids.count; k++) {
2582
struct GUID vertex_id, *new_data;
2583
struct kcctpl_vertex *vertex;
2585
vertex_id = edge->vertex_ids.data[k];
2586
vertex = kcctpl_find_vertex_by_guid(graph,
2589
DEBUG(1, (__location__ ": failed to "
2590
"find a graph vertex with "
2592
GUID_string(tmp_ctx,
2595
talloc_free(tmp_ctx);
2596
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2599
new_data = talloc_realloc(tmp_ctx,
2600
vertex->edge_ids.data,
2602
vertex->edge_ids.count + 1);
2603
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
2605
new_data[vertex->edge_ids.count] = edge->id;
2606
vertex->edge_ids.data = new_data;
2607
vertex->edge_ids.count++;
2611
status = kcctpl_dijkstra(graph, edge_type, false);
2612
if (NT_STATUS_IS_ERR(status)) {
2613
DEBUG(1, (__location__ ": failed to run Dijkstra's "
2614
"algorithm: %s\n", nt_errstr(status)));
2616
talloc_free(tmp_ctx);
2620
status = kcctpl_process_edge_set(tmp_ctx, graph, set,
2622
if (NT_STATUS_IS_ERR(status)) {
2623
DEBUG(1, (__location__ ": failed to process edge set "
2624
"%s: %s\n", GUID_string(tmp_ctx, &set->id),
2625
nt_errstr(status)));
2627
talloc_free(tmp_ctx);
2631
status = kcctpl_dijkstra(graph, edge_type, true);
2632
if (NT_STATUS_IS_ERR(status)) {
2633
DEBUG(1, (__location__ ": failed to run Dijkstra's "
2634
"algorithm: %s\n", nt_errstr(status)));
2636
talloc_free(tmp_ctx);
2640
status = kcctpl_process_edge_set(tmp_ctx, graph, set,
2642
if (NT_STATUS_IS_ERR(status)) {
2643
DEBUG(1, (__location__ ": failed to process edge set "
2644
"%s: %s\n", GUID_string(tmp_ctx, &set->id),
2645
nt_errstr(status)));
2647
talloc_free(tmp_ctx);
2652
kcctpl_setup_vertices(graph);
2654
status = kcctpl_process_edge_set(tmp_ctx, graph, NULL, internal_edges);
2655
if (NT_STATUS_IS_ERR(status)) {
2656
DEBUG(1, (__location__ ": failed to process empty edge set: "
2657
"%s\n", nt_errstr(status)));
2659
talloc_free(tmp_ctx);
2663
status = kcctpl_kruskal(tmp_ctx, graph, internal_edges, &output_edges);
2664
if (NT_STATUS_IS_ERR(status)) {
2665
DEBUG(1, (__location__ ": failed to run Kruskal's algorithm: "
2666
"%s\n", nt_errstr(status)));
2668
talloc_free(tmp_ctx);
2672
for (i = 0; i < graph->vertices.count; i++) {
2673
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
2675
if (vertex->color == RED) {
2676
vertex->dist_to_red = 0;
2677
} else if (true) { /* TODO: if there exists a path from 'vertex'
2679
vertex->dist_to_red = -1; /* TODO: the length of the
2680
shortest such path */
2682
vertex->dist_to_red = UINT32_MAX;
2686
component_count = kcctpl_count_components(graph);
2688
status = kcctpl_copy_output_edges(service, tmp_ctx, graph, output_edges,
2690
if (NT_STATUS_IS_ERR(status)) {
2691
DEBUG(1, (__location__ ": failed to copy edge list: %s\n",
2692
nt_errstr(status)));
2694
talloc_free(tmp_ctx);
2698
*_component_count = component_count;
2699
talloc_steal(mem_ctx, st_edge_list.data);
2700
*_st_edge_list = st_edge_list;
2701
talloc_free(tmp_ctx);
2702
return NT_STATUS_OK;
2706
* creat an nTDSConnection object with the given parameters if one does not
2709
static NTSTATUS kcctpl_create_connection(struct kccsrv_service *service,
2710
TALLOC_CTX *mem_ctx,
2711
struct ldb_message *cross_ref,
2712
struct ldb_message *r_bridgehead,
2713
struct ldb_message *transport,
2714
struct ldb_message *l_bridgehead,
2715
struct kcctpl_repl_info repl_info,
2716
uint8_t schedule[84],
2717
bool detect_failed_dcs,
2718
bool partial_replica_okay,
2719
struct GUID_list *_keep_connections)
2721
TALLOC_CTX *tmp_ctx;
2722
struct ldb_dn *r_site_dn, *l_site_dn, *servers_dn;
2724
struct GUID r_site_guid, l_site_guid;
2726
struct message_list r_bridgeheads_all, l_bridgeheads_all,
2727
r_bridgeheads_available, l_bridgeheads_available;
2729
struct ldb_result *res;
2730
const char * const attrs[] = { "objectGUID", "parent", "fromServer",
2731
"transportType", "schedule", "options",
2732
"enabledConnection", NULL };
2733
unsigned int i, valid_connections;
2734
struct GUID_list keep_connections;
2736
tmp_ctx = talloc_new(service);
2737
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
2739
r_site_dn = ldb_dn_copy(tmp_ctx, r_bridgehead->dn);
2740
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(r_site_dn, tmp_ctx);
2742
ok = ldb_dn_remove_child_components(r_site_dn, 3);
2744
talloc_free(tmp_ctx);
2745
return NT_STATUS_NO_MEMORY;
2748
ret = dsdb_find_guid_by_dn(service->samdb, r_site_dn, &r_site_guid);
2749
if (ret != LDB_SUCCESS) {
2750
DEBUG(1, (__location__ ": failed to find objectGUID for object "
2751
"%s: %s\n", ldb_dn_get_linearized(r_site_dn),
2752
ldb_strerror(ret)));
2754
talloc_free(tmp_ctx);
2755
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2758
l_site_dn = ldb_dn_copy(tmp_ctx, l_bridgehead->dn);
2759
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(l_site_dn, tmp_ctx);
2761
ok = ldb_dn_remove_child_components(l_site_dn, 3);
2763
talloc_free(tmp_ctx);
2764
return NT_STATUS_NO_MEMORY;
2767
ret = dsdb_find_guid_by_dn(service->samdb, l_site_dn, &l_site_guid);
2768
if (ret != LDB_SUCCESS) {
2769
DEBUG(1, (__location__ ": failed to find objectGUID for object "
2770
"%s: %s\n", ldb_dn_get_linearized(l_site_dn),
2771
ldb_strerror(ret)));
2773
talloc_free(tmp_ctx);
2774
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2777
status = kcctpl_get_all_bridgehead_dcs(service, tmp_ctx,
2778
r_site_guid, cross_ref,
2779
transport, partial_replica_okay,
2780
false, &r_bridgeheads_all);
2781
if (NT_STATUS_IS_ERR(status)) {
2782
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2783
"%s\n", nt_errstr(status)));
2787
status = kcctpl_get_all_bridgehead_dcs(service, tmp_ctx,
2788
r_site_guid, cross_ref,
2789
transport, partial_replica_okay,
2791
&r_bridgeheads_available);
2792
if (NT_STATUS_IS_ERR(status)) {
2793
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2794
"%s\n", nt_errstr(status)));
2798
status = kcctpl_get_all_bridgehead_dcs(service, tmp_ctx,
2799
l_site_guid, cross_ref,
2800
transport, partial_replica_okay,
2801
false, &l_bridgeheads_all);
2802
if (NT_STATUS_IS_ERR(status)) {
2803
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2804
"%s\n", nt_errstr(status)));
2808
status = kcctpl_get_all_bridgehead_dcs(service, tmp_ctx,
2809
l_site_guid, cross_ref,
2810
transport, partial_replica_okay,
2812
&l_bridgeheads_available);
2813
if (NT_STATUS_IS_ERR(status)) {
2814
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
2815
"%s\n", nt_errstr(status)));
2819
servers_dn = samdb_sites_dn(service->samdb, tmp_ctx);
2821
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
2823
talloc_free(tmp_ctx);
2824
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2826
ok = ldb_dn_add_child_fmt(servers_dn, "CN=Servers");
2828
talloc_free(tmp_ctx);
2829
return NT_STATUS_NO_MEMORY;
2832
ret = ldb_search(service->samdb, tmp_ctx, &res, servers_dn, LDB_SCOPE_SUBTREE,
2833
attrs, "objectClass=nTDSConnection");
2834
if (ret != LDB_SUCCESS) {
2835
DEBUG(1, (__location__ ": failed to find nTDSConnection "
2836
"objects: %s\n", ldb_strerror(ret)));
2838
talloc_free(tmp_ctx);
2839
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2842
for (i = 0; i < res->count; i++) {
2843
struct ldb_message *connection;
2844
struct ldb_dn *parent_dn, *from_server;
2846
connection = res->msgs[i];
2848
parent_dn = ldb_dn_get_parent(tmp_ctx, connection->dn);
2850
DEBUG(1, (__location__ ": failed to get parent DN of "
2852
ldb_dn_get_linearized(connection->dn)));
2854
talloc_free(tmp_ctx);
2855
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2858
from_server = samdb_result_dn(service->samdb, tmp_ctx, connection,
2859
"fromServer", NULL);
2861
DEBUG(1, (__location__ ": failed to find fromServer "
2862
"attribute of object %s\n",
2863
ldb_dn_get_linearized(connection->dn)));
2865
talloc_free(tmp_ctx);
2866
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2869
if (kcctpl_message_list_contains_dn(l_bridgeheads_all,
2871
kcctpl_message_list_contains_dn(r_bridgeheads_all,
2874
/* TODO: initialize conn_schedule from connection */
2875
uint8_t conn_schedule[84];
2876
struct ldb_dn *conn_transport_type;
2878
conn_opts = ldb_msg_find_attr_as_uint(connection,
2881
conn_transport_type = samdb_result_dn(service->samdb, tmp_ctx,
2885
if (!conn_transport_type) {
2886
DEBUG(1, (__location__ ": failed to find "
2887
"transportType attribute of object "
2889
ldb_dn_get_linearized(connection->dn)));
2891
talloc_free(tmp_ctx);
2892
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2895
if ((conn_opts & NTDSCONN_OPT_IS_GENERATED) &&
2896
!(conn_opts & NTDSCONN_OPT_RODC_TOPOLOGY) &&
2897
ldb_dn_compare(conn_transport_type,
2898
transport->dn) == 0) {
2899
if (!(conn_opts & NTDSCONN_OPT_USER_OWNED_SCHEDULE) &&
2900
memcmp(&conn_schedule, &schedule, 84) != 0) {
2901
/* TODO: perform an originating update
2902
to set conn!schedule to schedule */
2905
if ((conn_opts & NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT) &&
2906
(conn_opts & NTDSCONN_OPT_USE_NOTIFY)) {
2907
if (!(repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY)) {
2908
/* TODO: perform an originating
2909
update to clear bits
2910
NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2911
and NTDSCONN_OPT_USE_NOTIFY
2914
} else if (repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY) {
2915
/* TODO: perform an originating update
2917
NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2918
and NTDSCONN_OPT_USE_NOTIFY in
2922
if (conn_opts & NTDSCONN_OPT_TWOWAY_SYNC) {
2923
if (!(repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC)) {
2924
/* TODO: perform an originating
2926
NTDSCONN_OPT_TWOWAY_SYNC in
2929
} else if (repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC) {
2930
/* TODO: perform an originating update
2931
to set bit NTDSCONN_OPT_TWOWAY_SYNC
2935
if (conn_opts & NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION) {
2936
if (!(repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION)) {
2937
/* TODO: perform an originating
2939
NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2942
} else if (repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION) {
2943
/* TODO: perform an originating update
2945
NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2952
ZERO_STRUCT(keep_connections);
2954
valid_connections = 0;
2955
for (i = 0; i < res->count; i++) {
2956
struct ldb_message *connection;
2957
struct ldb_dn *parent_dn, *from_server;
2959
connection = res->msgs[i];
2961
parent_dn = ldb_dn_get_parent(tmp_ctx, connection->dn);
2963
DEBUG(1, (__location__ ": failed to get parent DN of "
2965
ldb_dn_get_linearized(connection->dn)));
2967
talloc_free(tmp_ctx);
2968
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2971
from_server = samdb_result_dn(service->samdb, tmp_ctx, connection,
2972
"fromServer", NULL);
2974
DEBUG(1, (__location__ ": failed to find fromServer "
2975
"attribute of object %s\n",
2976
ldb_dn_get_linearized(connection->dn)));
2978
talloc_free(tmp_ctx);
2979
return NT_STATUS_INTERNAL_DB_CORRUPTION;
2982
if (kcctpl_message_list_contains_dn(l_bridgeheads_all,
2984
kcctpl_message_list_contains_dn(r_bridgeheads_all,
2987
struct ldb_dn *conn_transport_type;
2989
conn_opts = ldb_msg_find_attr_as_uint(connection,
2992
conn_transport_type = samdb_result_dn(service->samdb, tmp_ctx,
2996
if (!conn_transport_type) {
2997
DEBUG(1, (__location__ ": failed to find "
2998
"transportType attribute of object "
3000
ldb_dn_get_linearized(connection->dn)));
3002
talloc_free(tmp_ctx);
3003
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3006
if ((!(conn_opts & NTDSCONN_OPT_IS_GENERATED) ||
3007
ldb_dn_compare(conn_transport_type,
3008
transport->dn) == 0) &&
3009
!(conn_opts & NTDSCONN_OPT_RODC_TOPOLOGY)) {
3010
struct GUID r_guid, l_guid, conn_guid;
3011
bool failed_state_r, failed_state_l;
3013
ret = dsdb_find_guid_by_dn(service->samdb, from_server,
3015
if (ret != LDB_SUCCESS) {
3016
DEBUG(1, (__location__ ": failed to "
3017
"find GUID for object %s\n",
3018
ldb_dn_get_linearized(from_server)));
3020
talloc_free(tmp_ctx);
3021
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3024
ret = dsdb_find_guid_by_dn(service->samdb, parent_dn,
3026
if (ret != LDB_SUCCESS) {
3027
DEBUG(1, (__location__ ": failed to "
3028
"find GUID for object %s\n",
3029
ldb_dn_get_linearized(parent_dn)));
3031
talloc_free(tmp_ctx);
3032
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3035
status = kcctpl_bridgehead_dc_failed(service->samdb,
3039
if (NT_STATUS_IS_ERR(status)) {
3040
DEBUG(1, (__location__ ": failed to "
3041
"check if bridgehead DC has "
3043
nt_errstr(status)));
3045
talloc_free(tmp_ctx);
3049
status = kcctpl_bridgehead_dc_failed(service->samdb,
3053
if (NT_STATUS_IS_ERR(status)) {
3054
DEBUG(1, (__location__ ": failed to "
3055
"check if bridgehead DC has "
3057
nt_errstr(status)));
3059
talloc_free(tmp_ctx);
3063
if (!failed_state_r && !failed_state_l) {
3064
valid_connections++;
3067
conn_guid = samdb_result_guid(connection,
3070
if (!kcctpl_guid_list_contains(keep_connections,
3072
struct GUID *new_data;
3074
new_data = talloc_realloc(tmp_ctx,
3075
keep_connections.data,
3077
keep_connections.count + 1);
3078
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
3080
new_data[keep_connections.count] = conn_guid;
3081
keep_connections.data = new_data;
3082
keep_connections.count++;
3088
if (valid_connections == 0) {
3089
uint64_t opts = NTDSCONN_OPT_IS_GENERATED;
3090
struct GUID new_guid, *new_data;
3092
if (repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY) {
3093
opts |= NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT;
3094
opts |= NTDSCONN_OPT_USE_NOTIFY;
3097
if (repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC) {
3098
opts |= NTDSCONN_OPT_TWOWAY_SYNC;
3101
if (repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION) {
3102
opts |= NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION;
3105
/* perform an originating update to create a new nTDSConnection
3106
* object cn that is:
3108
* - child of l_bridgehead
3109
* - cn!enabledConnection = true
3110
* - cn!options = opts
3111
* - cn!transportType = t
3112
* - cn!fromServer = r_bridgehead
3113
* - cn!schedule = schedule
3116
/* TODO: what should be the new connection's GUID? */
3117
new_guid = GUID_random();
3119
new_data = talloc_realloc(tmp_ctx, keep_connections.data,
3121
keep_connections.count + 1);
3122
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
3123
new_data[keep_connections.count] = new_guid;
3124
keep_connections.data = new_data;
3125
keep_connections.count++;
3128
talloc_steal(mem_ctx, keep_connections.data);
3129
*_keep_connections = keep_connections;
3130
talloc_free(tmp_ctx);
3131
return NT_STATUS_OK;
3135
* construct an NC replica graph for the NC identified by the given 'cross_ref',
3136
* then create any additional nTDSConnection objects required.
3138
static NTSTATUS kcctpl_create_connections(struct kccsrv_service *service,
3139
TALLOC_CTX *mem_ctx,
3140
struct kcctpl_graph *graph,
3141
struct ldb_message *cross_ref,
3142
bool detect_failed_dcs,
3143
struct GUID_list keep_connections,
3144
bool *_found_failed_dcs,
3147
bool connected, found_failed_dcs, partial_replica_okay;
3149
struct ldb_message *site;
3150
TALLOC_CTX *tmp_ctx;
3151
struct GUID site_guid;
3152
struct kcctpl_vertex *site_vertex;
3153
uint32_t component_count, i;
3154
struct kcctpl_multi_edge_list st_edge_list;
3155
struct ldb_dn *transports_dn;
3156
const char * const attrs[] = { "bridgeheadServerListBL", "name",
3157
"transportAddressAttribute", NULL };
3162
status = kcctpl_color_vertices(service, graph, cross_ref, detect_failed_dcs,
3164
if (NT_STATUS_IS_ERR(status)) {
3165
DEBUG(1, (__location__ ": failed to color vertices: %s\n",
3166
nt_errstr(status)));
3171
tmp_ctx = talloc_new(mem_ctx);
3172
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
3174
site = kcctpl_local_site(service->samdb, tmp_ctx);
3176
DEBUG(1, (__location__ ": failed to find our own local DC's "
3179
talloc_free(tmp_ctx);
3180
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3183
site_guid = samdb_result_guid(site, "objectGUID");
3185
site_vertex = kcctpl_find_vertex_by_guid(graph, site_guid);
3187
DEBUG(1, (__location__ ": failed to find vertex %s\n",
3188
GUID_string(tmp_ctx, &site_guid)));
3190
talloc_free(tmp_ctx);
3191
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3194
if (site_vertex->color == WHITE) {
3195
*_found_failed_dcs = found_failed_dcs;
3197
talloc_free(tmp_ctx);
3198
return NT_STATUS_OK;
3201
status = kcctpl_get_spanning_tree_edges(service, tmp_ctx, graph,
3204
if (NT_STATUS_IS_ERR(status)) {
3205
DEBUG(1, (__location__ ": failed get spanning tree edges: %s\n",
3206
nt_errstr(status)));
3208
talloc_free(tmp_ctx);
3212
if (component_count > 1) {
3216
partial_replica_okay = (site_vertex->color == BLACK);
3218
transports_dn = kcctpl_transports_dn(service->samdb, tmp_ctx);
3219
if (!transports_dn) {
3220
DEBUG(1, (__location__ ": failed to find our own Inter-Site "
3221
"Transports DN\n"));
3223
talloc_free(tmp_ctx);
3224
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3227
for (i = 0; i < st_edge_list.count; i++) {
3228
struct kcctpl_multi_edge *edge;
3229
struct GUID other_site_id;
3230
struct kcctpl_vertex *other_site_vertex;
3231
struct ldb_result *res;
3232
struct ldb_message *transport, *r_bridgehead, *l_bridgehead;
3233
uint8_t schedule[84];
3234
uint32_t first_available, j, interval;
3236
edge = &st_edge_list.data[i];
3238
if (edge->directed && !GUID_equal(&edge->vertex_ids.data[1],
3239
&site_vertex->id)) {
3243
if (GUID_equal(&edge->vertex_ids.data[0], &site_vertex->id)) {
3244
other_site_id = edge->vertex_ids.data[1];
3246
other_site_id = edge->vertex_ids.data[0];
3249
other_site_vertex = kcctpl_find_vertex_by_guid(graph,
3251
if (!other_site_vertex) {
3252
DEBUG(1, (__location__ ": failed to find vertex %s\n",
3253
GUID_string(tmp_ctx, &other_site_id)));
3255
talloc_free(tmp_ctx);
3256
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3259
ret = ldb_search(service->samdb, tmp_ctx, &res, transports_dn,
3260
LDB_SCOPE_ONELEVEL, attrs,
3261
"(&(objectClass=interSiteTransport)"
3262
"(objectGUID=%s))", GUID_string(tmp_ctx,
3264
if (ret != LDB_SUCCESS) {
3265
DEBUG(1, (__location__ ": failed to find "
3266
"interSiteTransport object %s: %s\n",
3267
GUID_string(tmp_ctx, &edge->type),
3268
ldb_strerror(ret)));
3270
talloc_free(tmp_ctx);
3271
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3273
if (res->count == 0) {
3274
DEBUG(1, (__location__ ": failed to find "
3275
"interSiteTransport object %s\n",
3276
GUID_string(tmp_ctx, &edge->type)));
3278
talloc_free(tmp_ctx);
3279
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3281
transport = res->msgs[0];
3283
status = kcctpl_get_bridgehead_dc(service, tmp_ctx,
3284
other_site_vertex->id,
3285
cross_ref, transport,
3286
partial_replica_okay,
3289
if (NT_STATUS_IS_ERR(status)) {
3290
DEBUG(1, (__location__ ": failed to get a bridgehead "
3291
"DC: %s\n", nt_errstr(status)));
3293
talloc_free(tmp_ctx);
3297
if (service->am_rodc) {
3298
/* TODO: l_bridgehad = nTDSDSA of local DC */
3300
status = kcctpl_get_bridgehead_dc(service, tmp_ctx,
3302
cross_ref, transport,
3303
partial_replica_okay,
3306
if (NT_STATUS_IS_ERR(status)) {
3307
DEBUG(1, (__location__ ": failed to get a "
3308
"bridgehead DC: %s\n",
3309
nt_errstr(status)));
3311
talloc_free(tmp_ctx);
3316
ZERO_ARRAY(schedule);
3317
first_available = 84;
3318
interval = edge->repl_info.interval / 15;
3319
for (j = 0; j < 84; j++) {
3320
if (edge->repl_info.schedule[j] == 1) {
3321
first_available = j;
3325
for (j = first_available; j < 84; j += interval) {
3329
status = kcctpl_create_connection(service, mem_ctx, cross_ref,
3330
r_bridgehead, transport,
3331
l_bridgehead, edge->repl_info,
3332
schedule, detect_failed_dcs,
3333
partial_replica_okay,
3335
if (NT_STATUS_IS_ERR(status)) {
3336
DEBUG(1, (__location__ ": failed to create a "
3337
"connection: %s\n", nt_errstr(status)));
3339
talloc_free(tmp_ctx);
3344
*_found_failed_dcs = found_failed_dcs;
3345
*_connected = connected;
3346
talloc_free(tmp_ctx);
3347
return NT_STATUS_OK;
3351
* computes an NC replica graph for each NC replica that "should be present" on
3352
* the local DC or "is present" on any DC in the same site as the local DC. for
3353
* each edge directed to an NC replica on such a DC from an NC replica on a DC
3354
* in another site, the KCC creates and nTDSConnection object to imply that edge
3355
* if one does not already exist.
3357
static NTSTATUS kcctpl_create_intersite_connections(struct kccsrv_service *service,
3358
TALLOC_CTX *mem_ctx,
3359
struct GUID_list *_keep_connections,
3360
bool *_all_connected)
3362
struct GUID_list keep_connections;
3364
TALLOC_CTX *tmp_ctx;
3365
struct ldb_dn *partitions_dn;
3366
struct ldb_result *res;
3367
const char * const attrs[] = { "enabled", "systemFlags", "nCName",
3372
all_connected = true;
3374
ZERO_STRUCT(keep_connections);
3376
tmp_ctx = talloc_new(mem_ctx);
3377
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
3379
partitions_dn = samdb_partitions_dn(service->samdb, tmp_ctx);
3380
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(partitions_dn, tmp_ctx);
3382
ret = ldb_search(service->samdb, tmp_ctx, &res, partitions_dn, LDB_SCOPE_ONELEVEL,
3383
attrs, "objectClass=crossRef");
3384
if (ret != LDB_SUCCESS) {
3385
DEBUG(1, (__location__ ": failed to find crossRef objects: "
3386
"%s\n", ldb_strerror(ret)));
3388
talloc_free(tmp_ctx);
3389
return NT_STATUS_INTERNAL_DB_CORRUPTION;
3392
for (i = 0; i < res->count; i++) {
3393
struct ldb_message *cross_ref;
3394
unsigned int cr_enabled;
3396
struct kcctpl_graph *graph;
3397
bool found_failed_dc, connected;
3400
cross_ref = res->msgs[i];
3401
cr_enabled = ldb_msg_find_attr_as_uint(cross_ref, "enabled", -1);
3402
cr_flags = ldb_msg_find_attr_as_int64(cross_ref, "systemFlags", 0);
3403
if ((cr_enabled == 0) || !(cr_flags & FLAG_CR_NTDS_NC)) {
3407
status = kcctpl_setup_graph(service->samdb, tmp_ctx, &graph);
3408
if (NT_STATUS_IS_ERR(status)) {
3409
DEBUG(1, (__location__ ": failed to create a graph: "
3410
"%s\n", nt_errstr(status)));
3412
talloc_free(tmp_ctx);
3416
status = kcctpl_create_connections(service, mem_ctx, graph,
3421
if (NT_STATUS_IS_ERR(status)) {
3422
DEBUG(1, (__location__ ": failed to create "
3423
"connections: %s\n", nt_errstr(status)));
3425
talloc_free(tmp_ctx);
3430
all_connected = false;
3432
if (found_failed_dc) {
3433
status = kcctpl_create_connections(service, mem_ctx,
3440
if (NT_STATUS_IS_ERR(status)) {
3441
DEBUG(1, (__location__ ": failed to "
3442
"create connections: %s\n",
3443
nt_errstr(status)));
3445
talloc_free(tmp_ctx);
3452
*_keep_connections = keep_connections;
3453
*_all_connected = all_connected;
3454
talloc_free(tmp_ctx);
3455
return NT_STATUS_OK;
3458
NTSTATUS kcctpl_test(struct kccsrv_service *service)
3461
TALLOC_CTX *tmp_ctx = talloc_new(service);
3462
struct GUID_list keep;
3465
DEBUG(5, ("Testing kcctpl_create_intersite_connections\n"));
3466
status = kcctpl_create_intersite_connections(service, tmp_ctx, &keep,
3468
DEBUG(4, ("%s\n", nt_errstr(status)));
3469
if (NT_STATUS_IS_OK(status)) {
3472
DEBUG(4, ("all_connected=%d, %d GUIDs returned\n",
3473
all_connected, keep.count));
3475
for (i = 0; i < keep.count; i++) {
3476
DEBUG(4, ("GUID %d: %s\n", i + 1,
3477
GUID_string(tmp_ctx, &keep.data[i])));
3481
talloc_free(tmp_ctx);
added
removed
source4/dsdb/kcc/kcc_topology.c
