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 NTDSDSA_OPT_IS_GC 0x00000001
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
38 #define NTDSSITELINK_OPT_USE_NOTIFY 0x00000001
39 #define NTDSSITELINK_OPT_TWOWAY_SYNC 0x00000002
40 #define NTDSSITELINK_OPT_DISABLE_COMPRESSION 0x00000004
42 #define NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
44 #define DS_BEHAVIOR_WIN2008 3
46 /** replication parameters of a graph edge */
47 struct kcctpl_repl_info
{
54 /** color of a vertex */
55 enum kcctpl_color
{ RED
, BLACK
, WHITE
};
57 /** a GUID array list */
63 /** a vertex in the site graph */
64 struct kcctpl_vertex
{
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
;
78 struct GUID component_id
;
79 uint32_t component_index
;
82 /** fully connected subgraph of vertices */
83 struct kcctpl_multi_edge
{
85 struct GUID_list vertex_ids
;
87 struct kcctpl_repl_info repl_info
;
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
{
95 struct GUID_list edge_ids
;
98 /** a vertices array list */
99 struct kcctpl_vertex_list
{
100 struct kcctpl_vertex
*data
;
104 /** an edges array list */
105 struct kcctpl_multi_edge_list
{
106 struct kcctpl_multi_edge
*data
;
110 /** an edge sets array list */
111 struct kcctpl_multi_edge_set_list
{
112 struct kcctpl_multi_edge_set
*data
;
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
;
123 /** path found in the graph between two non-white vertices */
124 struct kcctpl_internal_edge
{
128 struct kcctpl_repl_info repl_info
;
132 /** an internal edges array list */
133 struct kcctpl_internal_edge_list
{
134 struct kcctpl_internal_edge
*data
;
138 /** an LDB messages array list */
139 struct message_list
{
140 struct ldb_message
*data
;
145 * sort internal edges based on:
146 * - descending red_red,
147 * - ascending repl_info.cost,
148 * - descending available time in repl_info.schedule,
153 * this function is used in 'kcctpl_kruskal'.
155 static int kcctpl_sort_internal_edges(const void *internal_edge1
,
156 const void *internal_edge2
)
158 const struct kcctpl_internal_edge
*ie1
, *ie2
;
161 ie1
= (const struct kcctpl_internal_edge
*) internal_edge1
;
162 ie2
= (const struct kcctpl_internal_edge
*) internal_edge2
;
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
;
169 uint32_t available1
, available2
, i
;
172 available1
= available2
= 0;
173 for (i
= 0; i
< 84; i
++) {
174 if (ie1
->repl_info
.schedule
[i
] == 0) {
178 if (ie2
->repl_info
.schedule
[i
] == 0) {
182 cmp_schedule
= available2
- available1
;
184 if (cmp_schedule
== 0) {
185 int cmp_v1id
= GUID_compare(&ie1
->v1id
,
189 int cmp_v2id
= GUID_compare(&ie1
->v2id
,
193 return GUID_compare(&ie1
->type
,
213 * sort vertices based on the following criteria:
214 * - ascending color (RED < BLACK),
215 * - ascending repl_info.cost,
218 * this function is used in 'kcctpl_process_edge'.
220 static int kcctpl_sort_vertices(const void *vertex1
, const void *vertex2
)
222 const struct kcctpl_vertex
*v1
, *v2
;
225 v1
= (const struct kcctpl_vertex
*) vertex1
;
226 v2
= (const struct kcctpl_vertex
*) vertex2
;
228 cmp_color
= v1
->color
- v2
->color
;
229 if (cmp_color
== 0) {
230 int cmp_cost
= v1
->repl_info
.cost
- v2
->repl_info
.cost
;
232 return GUID_compare(&v1
->id
, &v2
->id
);
242 * sort bridgehead elements (nTDSDSA) based on the following criteria:
243 * - GC servers precede non-GC servers
244 * - ascending objectGUID
246 * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
248 static int kcctpl_sort_bridgeheads(const void *bridgehead1
,
249 const void *bridgehead2
)
251 const struct ldb_message
*bh1
, *bh2
;
252 uint32_t bh1_opts
, bh2_opts
;
255 bh1
= (const struct ldb_message
*) bridgehead1
;
256 bh2
= (const struct ldb_message
*) bridgehead2
;
258 bh1_opts
= ldb_msg_find_attr_as_uint(bh1
, "options", 0);
259 bh2_opts
= ldb_msg_find_attr_as_uint(bh2
, "options", 0);
261 cmp_gc
= (bh1_opts
& NTDSDSA_OPT_IS_GC
) -
262 (bh2_opts
& NTDSDSA_OPT_IS_GC
);
265 struct GUID bh1_id
, bh2_id
;
267 bh1_id
= samdb_result_guid(bh1
, "objectGUID");
268 bh2_id
= samdb_result_guid(bh2
, "objectGUID");
270 return GUID_compare(&bh1_id
, &bh2_id
);
277 * sort bridgehead elements (nTDSDSA) in a random order.
279 * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
281 static void kcctpl_shuffle_bridgeheads(struct message_list bridgeheads
)
287 for (i
= bridgeheads
.count
; i
> 1; i
--) {
289 struct ldb_message tmp
;
293 tmp
= bridgeheads
.data
[i
- 1];
294 bridgeheads
.data
[i
- 1] = bridgeheads
.data
[r
];
295 bridgeheads
.data
[r
] = tmp
;
300 * find a graph vertex based on its GUID.
302 static struct kcctpl_vertex
*kcctpl_find_vertex_by_guid(struct kcctpl_graph
*graph
,
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
];
317 * find a graph edge based on its GUID.
319 static struct kcctpl_multi_edge
*kcctpl_find_edge_by_guid(struct kcctpl_graph
*graph
,
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
];
334 * find a graph edge that contains a vertex with the specified GUID. the first
335 * occurrence will be returned.
337 static struct kcctpl_multi_edge
*kcctpl_find_edge_by_vertex_guid(struct kcctpl_graph
*graph
,
342 for (i
= 0; i
< graph
->edges
.count
; i
++) {
343 struct kcctpl_multi_edge
*edge
;
346 edge
= &graph
->edges
.data
[i
];
348 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
349 struct GUID vertex_guid
= edge
->vertex_ids
.data
[j
];
351 struct GUID
*p
= &guid
;
353 if (GUID_equal(&vertex_guid
, p
)) {
363 * search for an occurrence of a GUID inside a list of GUIDs.
365 static bool kcctpl_guid_list_contains(struct GUID_list list
, struct GUID guid
)
369 for (i
= 0; i
< list
.count
; i
++) {
370 if (GUID_equal(&list
.data
[i
], &guid
)) {
379 * search for an occurrence of an ldb_message inside a list of ldb_messages,
380 * based on the ldb_message's DN.
382 static bool kcctpl_message_list_contains_dn(struct message_list list
,
387 for (i
= 0; i
< list
.count
; i
++) {
388 struct ldb_message
*message
= &list
.data
[i
];
390 if (ldb_dn_compare(message
->dn
, dn
) == 0) {
399 * get the Transports DN
400 * (CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=<domain>).
402 static struct ldb_dn
*kcctpl_transports_dn(struct ldb_context
*ldb
,
405 struct ldb_dn
*sites_dn
;
408 sites_dn
= samdb_sites_dn(ldb
, mem_ctx
);
413 ok
= ldb_dn_add_child_fmt(sites_dn
, "CN=Inter-Site Transports");
415 talloc_free(sites_dn
);
422 * get the domain local site object.
424 static struct ldb_message
*kcctpl_local_site(struct ldb_context
*ldb
,
429 struct ldb_dn
*sites_dn
;
430 struct ldb_result
*res
;
431 const char * const attrs
[] = { "objectGUID", "options", NULL
};
433 tmp_ctx
= talloc_new(ldb
);
435 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
437 talloc_free(tmp_ctx
);
441 ret
= ldb_search(ldb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_SUBTREE
, attrs
,
444 if (ret
!= LDB_SUCCESS
|| res
->count
== 0) {
445 talloc_free(tmp_ctx
);
449 talloc_steal(mem_ctx
, res
);
450 talloc_free(tmp_ctx
);
455 * compare two internal edges for equality. every field of the structure will be
458 static bool kcctpl_internal_edge_equal(struct kcctpl_internal_edge
*edge1
,
459 struct kcctpl_internal_edge
*edge2
)
461 if (!edge1
|| !edge2
) {
465 if (!GUID_equal(&edge1
->v1id
, &edge2
->v1id
)) {
469 if (!GUID_equal(&edge1
->v2id
, &edge2
->v2id
)) {
473 if (edge1
->red_red
!= edge2
->red_red
) {
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) {
485 if (!GUID_equal(&edge1
->type
, &edge2
->type
)) {
493 * create a kcctpl_graph instance.
495 static NTSTATUS
kcctpl_create_graph(TALLOC_CTX
*mem_ctx
,
496 struct GUID_list guids
,
497 struct kcctpl_graph
**_graph
)
499 struct kcctpl_graph
*graph
;
502 graph
= talloc_zero(mem_ctx
, struct kcctpl_graph
);
503 NT_STATUS_HAVE_NO_MEMORY(graph
);
505 graph
->vertices
.count
= guids
.count
;
506 graph
->vertices
.data
= talloc_zero_array(graph
, struct kcctpl_vertex
,
508 if (graph
->vertices
.data
== NULL
) {
510 return NT_STATUS_NO_MEMORY
;
513 TYPESAFE_QSORT(guids
.data
, guids
.count
, GUID_compare
);
515 for (i
= 0; i
< guids
.count
; i
++) {
516 graph
->vertices
.data
[i
].id
= guids
.data
[i
];
524 * create a kcctpl_multi_edge instance.
526 static NTSTATUS
kcctpl_create_edge(struct ldb_context
*ldb
, TALLOC_CTX
*mem_ctx
,
528 struct ldb_message
*site_link
,
529 struct kcctpl_multi_edge
**_edge
)
531 struct kcctpl_multi_edge
*edge
;
533 struct ldb_dn
*sites_dn
;
534 struct ldb_result
*res
;
535 const char * const attrs
[] = { "siteList", NULL
};
537 struct ldb_message_element
*el
;
541 tmp_ctx
= talloc_new(mem_ctx
);
542 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
544 edge
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge
);
546 TALLOC_FREE(tmp_ctx
);
547 return NT_STATUS_NO_MEMORY
;
550 edge
->id
= samdb_result_guid(site_link
, "objectGUID");
552 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
554 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
556 talloc_free(tmp_ctx
);
557 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
),
567 talloc_free(tmp_ctx
);
568 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
570 if (res
->count
== 0) {
571 DEBUG(1, (__location__
": failed to find siteLink object %s\n",
572 GUID_string(tmp_ctx
, &edge
->id
)));
574 talloc_free(tmp_ctx
);
575 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
578 el
= ldb_msg_find_element(res
->msgs
[0], "siteList");
580 DEBUG(1, (__location__
": failed to find siteList attribute of "
582 ldb_dn_get_linearized(res
->msgs
[0]->dn
)));
584 talloc_free(tmp_ctx
);
585 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
;
593 edge
->vertex_ids
.count
= el
->num_values
;
595 for (i
= 0; i
< el
->num_values
; i
++) {
600 dn
= ldb_dn_from_ldb_val(tmp_ctx
, ldb
, &val
);
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
)));
606 talloc_free(tmp_ctx
);
607 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
),
616 talloc_free(tmp_ctx
);
617 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
620 edge
->vertex_ids
.data
[i
] = guid
;
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
,
627 /* TODO: edge->repl_info.schedule = site_link!schedule */
629 edge
->directed
= false;
631 *_edge
= talloc_steal(mem_ctx
, edge
);
632 talloc_free(tmp_ctx
);
637 * create a kcctpl_multi_edge_set instance containing edges for all siteLink
640 static NTSTATUS
kcctpl_create_auto_edge_set(struct kcctpl_graph
*graph
,
642 struct ldb_result
*res_site_link
,
643 struct kcctpl_multi_edge_set
**_set
)
645 struct kcctpl_multi_edge_set
*set
;
649 tmp_ctx
= talloc_new(graph
);
650 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
652 set
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge_set
);
654 TALLOC_FREE(tmp_ctx
);
655 return NT_STATUS_NO_MEMORY
;
658 for (i
= 0; i
< res_site_link
->count
; i
++) {
659 struct GUID site_link_guid
;
660 struct kcctpl_multi_edge
*edge
;
662 site_link_guid
= samdb_result_guid(res_site_link
->msgs
[i
],
664 edge
= kcctpl_find_edge_by_guid(graph
, site_link_guid
);
666 DEBUG(1, (__location__
": failed to find a graph edge "
668 GUID_string(tmp_ctx
, &site_link_guid
)));
670 talloc_free(tmp_ctx
);
671 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
674 if (GUID_equal(&edge
->type
, &type
)) {
675 struct GUID
*new_data
;
677 new_data
= talloc_realloc(set
, set
->edge_ids
.data
,
679 set
->edge_ids
.count
+ 1);
680 if (new_data
== NULL
) {
681 TALLOC_FREE(tmp_ctx
);
682 return NT_STATUS_NO_MEMORY
;
684 new_data
[set
->edge_ids
.count
] = site_link_guid
;
685 set
->edge_ids
.data
= new_data
;
686 set
->edge_ids
.count
++;
690 *_set
= talloc_steal(graph
, set
);
695 * create a kcctpl_multi_edge_set instance.
697 static NTSTATUS
kcctpl_create_edge_set(struct ldb_context
*ldb
,
698 struct kcctpl_graph
*graph
,
700 struct ldb_message
*bridge
,
701 struct kcctpl_multi_edge_set
**_set
)
703 struct kcctpl_multi_edge_set
*set
;
705 struct ldb_message_element
*el
;
708 tmp_ctx
= talloc_new(ldb
);
709 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
711 set
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge_set
);
713 TALLOC_FREE(tmp_ctx
);
714 return NT_STATUS_NO_MEMORY
;
717 set
->id
= samdb_result_guid(bridge
, "objectGUID");
719 el
= ldb_msg_find_element(bridge
, "siteLinkList");
721 DEBUG(1, (__location__
": failed to find siteLinkList "
722 "attribute of object %s\n",
723 ldb_dn_get_linearized(bridge
->dn
)));
725 talloc_free(tmp_ctx
);
726 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
728 for (i
= 0; i
< el
->num_values
; i
++) {
731 struct GUID site_link_guid
;
733 struct kcctpl_multi_edge
*edge
;
736 dn
= ldb_dn_from_ldb_val(tmp_ctx
, ldb
, &val
);
738 DEBUG(1, (__location__
": failed to read a DN from "
739 "siteList attribute of %s\n",
740 ldb_dn_get_linearized(bridge
->dn
)));
742 talloc_free(tmp_ctx
);
743 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
),
753 talloc_free(tmp_ctx
);
754 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
757 edge
= kcctpl_find_edge_by_guid(graph
, site_link_guid
);
759 DEBUG(1, (__location__
": failed to find a graph edge "
761 GUID_string(tmp_ctx
, &site_link_guid
)));
763 talloc_free(tmp_ctx
);
764 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
767 if (GUID_equal(&edge
->type
, &type
)) {
768 struct GUID
*new_data
;
770 new_data
= talloc_realloc(set
, set
->edge_ids
.data
,
772 set
->edge_ids
.count
+ 1);
773 if (new_data
== NULL
) {
774 TALLOC_FREE(tmp_ctx
);
775 return NT_STATUS_NO_MEMORY
;
777 new_data
[set
->edge_ids
.count
] = site_link_guid
;
778 set
->edge_ids
.data
= new_data
;
779 set
->edge_ids
.count
++;
783 *_set
= talloc_steal(graph
, set
);
784 talloc_free(tmp_ctx
);
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).
793 static NTSTATUS
kcctpl_setup_graph(struct ldb_context
*ldb
, TALLOC_CTX
*mem_ctx
,
794 struct kcctpl_graph
**_graph
)
796 struct kcctpl_graph
*graph
;
797 struct ldb_dn
*sites_dn
, *transports_dn
;
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",
808 struct GUID_list vertex_ids
;
811 struct ldb_message
*site
;
814 tmp_ctx
= talloc_new(mem_ctx
);
815 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
817 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
819 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
821 talloc_free(tmp_ctx
);
822 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
),
832 talloc_free(tmp_ctx
);
833 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
836 ZERO_STRUCT(vertex_ids
);
837 for (i
= 0; i
< res
->count
; i
++) {
838 struct GUID guid
, *new_data
;
840 guid
= samdb_result_guid(res
->msgs
[i
], "objectGUID");
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
;
848 new_data
[vertex_ids
.count
] = guid
;
849 vertex_ids
.data
= new_data
;
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",
858 talloc_free(tmp_ctx
);
862 site
= kcctpl_local_site(ldb
, tmp_ctx
);
864 DEBUG(1, (__location__
": failed to find our own local DC's "
867 talloc_free(tmp_ctx
);
868 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
870 site_opts
= ldb_msg_find_attr_as_uint(site
, "options", 0);
872 transports_dn
= kcctpl_transports_dn(ldb
, tmp_ctx
);
873 if (!transports_dn
) {
874 DEBUG(1, (__location__
": failed to find our own Inter-Site "
877 talloc_free(tmp_ctx
);
878 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
),
889 talloc_free(tmp_ctx
);
890 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
;
898 uint32_t transport_opts
;
900 transport
= res
->msgs
[i
];
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
),
911 talloc_free(tmp_ctx
);
912 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
;
919 status
= kcctpl_create_edge(ldb
, graph
, transport_guid
,
920 res_site_link
->msgs
[j
],
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
);
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
;
936 new_data
[graph
->edges
.count
] = *edge
;
937 graph
->edges
.data
= new_data
;
938 graph
->edges
.count
++;
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
;
946 status
= kcctpl_create_auto_edge_set(graph
,
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
);
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
;
964 new_data
[graph
->edge_sets
.count
] = *edge_set
;
965 graph
->edge_sets
.data
= new_data
;
966 graph
->edge_sets
.count
++;
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: "
976 ldb_dn_get_linearized(transport
->dn
),
979 talloc_free(tmp_ctx
);
980 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
983 for (j
= 0; j
< res_site_link
->count
; j
++) {
984 struct ldb_message
*bridge
;
985 struct kcctpl_multi_edge_set
*edge_set
,
988 bridge
= res_site_link
->msgs
[j
];
989 status
= kcctpl_create_edge_set(ldb
, graph
,
993 if (NT_STATUS_IS_ERR(status
)) {
994 DEBUG(1, (__location__
": failed to "
995 "create edge set: %s\n",
998 talloc_free(tmp_ctx
);
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
;
1010 new_data
[graph
->edge_sets
.count
] = *edge_set
;
1011 graph
->edge_sets
.data
= new_data
;
1012 graph
->edge_sets
.count
++;
1017 *_graph
= talloc_steal(mem_ctx
, graph
);
1018 talloc_free(tmp_ctx
);
1019 return NT_STATUS_OK
;
1023 * determine whether a given DC is known to be in a failed state.
1025 static NTSTATUS
kcctpl_bridgehead_dc_failed(struct ldb_context
*ldb
,
1027 bool detect_failed_dcs
,
1030 TALLOC_CTX
*tmp_ctx
;
1031 struct ldb_dn
*settings_dn
;
1032 struct ldb_result
*res
;
1033 const char * const attrs
[] = { "options", NULL
};
1035 struct ldb_message
*settings
;
1036 uint32_t settings_opts
;
1039 tmp_ctx
= talloc_new(ldb
);
1040 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1042 settings_dn
= samdb_ntds_settings_dn(ldb
, tmp_ctx
);
1044 DEBUG(1, (__location__
": failed to find our own NTDS Settings "
1046 talloc_free(tmp_ctx
);
1047 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
;
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
;
1066 settings
= res
->msgs
[0];
1068 settings_opts
= ldb_msg_find_attr_as_uint(settings
, "options", 0);
1069 if (settings_opts
& NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED
) {
1071 } else if (true) { /* TODO: how to get kCCFailedLinks and
1072 kCCFailedConnections? */
1075 failed
= detect_failed_dcs
;
1079 talloc_free(tmp_ctx
);
1080 return NT_STATUS_OK
;
1084 * get all bridgehead DCs satisfying the given criteria.
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
)
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
};
1101 struct ldb_message
*site
, *schema
;
1102 const char * const dc_attrs
[] = { "objectGUID", "options", NULL
};
1103 struct ldb_message_element
*el
;
1105 const char *transport_name
, *transport_address_attr
;
1108 ZERO_STRUCT(bridgeheads
);
1110 tmp_ctx
= talloc_new(mem_ctx
);
1111 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1113 sites_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
1115 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
1117 talloc_free(tmp_ctx
);
1118 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
)));
1129 talloc_free(tmp_ctx
);
1130 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1132 if (res
->count
== 0) {
1133 DEBUG(1, (__location__
": failed to find site object %s\n",
1134 GUID_string(tmp_ctx
, &site_guid
)));
1136 talloc_free(tmp_ctx
);
1137 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1139 site
= res
->msgs
[0];
1141 schemas_dn
= ldb_get_schema_basedn(service
->samdb
);
1143 DEBUG(1, (__location__
": failed to find our own Schemas DN\n"));
1145 talloc_free(tmp_ctx
);
1146 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1149 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, schemas_dn
, LDB_SCOPE_SUBTREE
,
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
)));
1156 talloc_free(tmp_ctx
);
1157 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1159 if (res
->count
== 0) {
1160 DEBUG(1, (__location__
": failed to find classSchema "
1163 talloc_free(tmp_ctx
);
1164 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1166 schema
= res
->msgs
[0];
1168 ZERO_STRUCT(all_dcs_in_site
);
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
)));
1177 talloc_free(tmp_ctx
);
1178 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1181 el
= ldb_msg_find_element(transport
, "bridgeheadServerListBL");
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
)));
1188 talloc_free(tmp_ctx
);
1189 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1192 transport_address_attr
= ldb_msg_find_attr_as_string(transport
,
1193 "transportAddressAttribute",
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
)));
1200 talloc_free(tmp_ctx
);
1201 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1204 site_opts
= ldb_msg_find_attr_as_uint(site
, "options", 0);
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
};
1214 struct GUID dc_guid
;
1219 parent_dn
= ldb_dn_get_parent(tmp_ctx
, dc
->dn
);
1221 DEBUG(1, (__location__
": failed to get parent DN of "
1222 "%s\n", ldb_dn_get_linearized(dc
->dn
)));
1224 talloc_free(tmp_ctx
);
1225 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1228 if (el
&& (el
->num_values
>= 1)) {
1234 for (j
= 0; j
< el
->num_values
; j
++) {
1238 val
= el
->values
[j
];
1240 dn
= ldb_dn_from_ldb_val(tmp_ctx
, service
->samdb
, &val
);
1242 DEBUG(1, (__location__
": failed to read a DN "
1243 "from bridgeheadServerListBL "
1244 "attribute of %s\n",
1245 ldb_dn_get_linearized(transport
->dn
)));
1247 talloc_free(tmp_ctx
);
1248 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1251 if (ldb_dn_compare(dn
, parent_dn
) == 0) {
1262 /* TODO: if dc is in the same site as the local DC */
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
1268 if (true || (true && !partial_replica_okay
)) {
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
)) {
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
) {
1287 ret
= ldb_search(service
->samdb
, tmp_ctx
, &parent_res
, parent_dn
,
1288 LDB_SCOPE_BASE
, parent_attrs
, NULL
);
1290 dc_transport_address
= ldb_msg_find_attr_as_string(parent_res
->msgs
[0],
1291 transport_address_attr
,
1294 if (strncmp(transport_name
, "IP", 2) != 0 &&
1295 dc_transport_address
== NULL
) {
1299 dc_guid
= samdb_result_guid(dc
, "objectGUID");
1301 status
= kcctpl_bridgehead_dc_failed(service
->samdb
, dc_guid
,
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
)));
1309 talloc_free(tmp_ctx
);
1317 new_data
= talloc_realloc(tmp_ctx
, bridgeheads
.data
,
1319 bridgeheads
.count
+ 1);
1320 if (new_data
== NULL
) {
1321 TALLOC_FREE(tmp_ctx
);
1322 return NT_STATUS_NO_MEMORY
;
1324 new_data
[bridgeheads
.count
+ 1] = *dc
;
1325 bridgeheads
.data
= new_data
;
1326 bridgeheads
.count
++;
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
);
1333 kcctpl_shuffle_bridgeheads(bridgeheads
);
1336 talloc_steal(mem_ctx
, bridgeheads
.data
);
1337 *_bridgeheads
= bridgeheads
;
1338 talloc_free(tmp_ctx
);
1339 return NT_STATUS_OK
;
1343 * get a bridgehead DC.
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
)
1354 struct message_list dsa_list
;
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
)));
1367 *_dsa
= (dsa_list
.count
== 0) ? NULL
: &dsa_list
.data
[0];
1369 return NT_STATUS_OK
;
1373 * color each vertex to indicate which kinds of NC replicas it contains.
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
)
1381 TALLOC_CTX
*tmp_ctx
;
1382 struct ldb_dn
*sites_dn
;
1383 bool found_failed_dcs
, partial_replica_okay
;
1385 struct ldb_message
*site
;
1386 struct ldb_result
*res
;
1388 struct GUID site_guid
;
1389 struct kcctpl_vertex
*site_vertex
;
1391 found_failed_dcs
= false;
1393 tmp_ctx
= talloc_new(service
);
1394 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1396 sites_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
1398 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
1400 talloc_free(tmp_ctx
);
1401 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
};
1410 vertex
= &graph
->vertices
.data
[i
];
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
)));
1420 talloc_free(tmp_ctx
);
1421 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1423 if (res
->count
== 0) {
1424 DEBUG(1, (__location__
": failed to find site object "
1425 "%s\n", GUID_string(tmp_ctx
, &vertex
->id
)));
1427 talloc_free(tmp_ctx
);
1428 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1430 site
= res
->msgs
[0];
1432 nc_name
= samdb_result_dn(service
->samdb
, tmp_ctx
, cross_ref
,
1435 DEBUG(1, (__location__
": failed to find nCName "
1436 "attribute of object %s\n",
1437 ldb_dn_get_linearized(cross_ref
->dn
)));
1439 talloc_free(tmp_ctx
);
1440 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1443 if (true) { /* TODO: site contains 1+ DCs with full replicas of
1445 vertex
->color
= RED
;
1446 } else if (true) { /* TODO: site contains 1+ partial replicas of
1448 vertex
->color
= BLACK
;
1450 vertex
->color
= WHITE
;
1454 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
1456 DEBUG(1, (__location__
": failed to find our own local DC's "
1459 talloc_free(tmp_ctx
);
1460 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1462 site_guid
= samdb_result_guid(site
, "objectGUID");
1464 site_vertex
= kcctpl_find_vertex_by_guid(graph
, site_guid
);
1466 DEBUG(1, (__location__
": failed to find a vertex edge with "
1467 "GUID=%s\n", GUID_string(tmp_ctx
, &site_guid
)));
1469 talloc_free(tmp_ctx
);
1470 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1473 partial_replica_okay
= (site_vertex
->color
== BLACK
);
1475 cr_flags
= ldb_msg_find_attr_as_int64(cross_ref
, "systemFlags", 0);
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",
1485 vertex
= &graph
->vertices
.data
[i
];
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"));
1492 talloc_free(tmp_ctx
);
1493 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
)));
1505 talloc_free(tmp_ctx
);
1506 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
;
1515 transport
= res
->msgs
[j
];
1517 transport_name
= ldb_msg_find_attr_as_string(transport
,
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
)));
1524 talloc_free(tmp_ctx
);
1525 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1528 transport_guid
= samdb_result_guid(transport
,
1531 if (site_vertex
->color
== RED
&&
1532 strncmp(transport_name
, "IP", 2) != 0 &&
1533 (cr_flags
& FLAG_CR_NTDS_DOMAIN
)) {
1537 if (!kcctpl_find_edge_by_vertex_guid(graph
,
1542 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
1544 cross_ref
, transport
,
1545 partial_replica_okay
,
1548 if (NT_STATUS_IS_ERR(status
)) {
1549 DEBUG(1, (__location__
": failed to get a "
1550 "bridgehead DC: %s\n",
1551 nt_errstr(status
)));
1553 talloc_free(tmp_ctx
);
1557 found_failed_dcs
= true;
1561 new_data
= talloc_realloc(vertex
,
1562 vertex
->accept_red_red
.data
,
1564 vertex
->accept_red_red
.count
+ 1);
1565 if (new_data
== NULL
) {
1566 TALLOC_FREE(tmp_ctx
);
1567 return NT_STATUS_NO_MEMORY
;
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
++;
1573 new_data
= talloc_realloc(vertex
,
1574 vertex
->accept_black
.data
,
1576 vertex
->accept_black
.count
+ 1);
1577 if (new_data
== NULL
) {
1578 TALLOC_FREE(tmp_ctx
);
1579 return NT_STATUS_NO_MEMORY
;
1581 new_data
[vertex
->accept_black
.count
+ 1] = transport_guid
;
1582 vertex
->accept_black
.data
= new_data
;
1583 vertex
->accept_black
.count
++;
1587 *_found_failed_dcs
= found_failed_dcs
;
1588 talloc_free(tmp_ctx
);
1589 return NT_STATUS_OK
;
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.
1597 static void kcctpl_setup_vertices(struct kcctpl_graph
*graph
)
1601 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1602 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
1604 if (vertex
->color
== WHITE
) {
1605 vertex
->repl_info
.cost
= UINT32_MAX
;
1606 vertex
->root_id
= vertex
->component_id
= GUID_zero();
1608 vertex
->repl_info
.cost
= 0;
1609 vertex
->root_id
= vertex
->component_id
= vertex
->id
;
1612 vertex
->repl_info
.interval
= 0;
1613 vertex
->repl_info
.options
= 0xFFFFFFFF;
1614 ZERO_STRUCT(vertex
->repl_info
.schedule
);
1615 vertex
->demoted
= false;
1620 * demote one vertex if necessary.
1622 static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex
*vertex
,
1625 if (vertex
->color
== WHITE
) {
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;
1638 * clear the demoted state of a vertex.
1640 static void kcctpl_undemote_one_vertex(struct kcctpl_vertex
*vertex
)
1642 if (vertex
->color
== WHITE
) {
1646 vertex
->repl_info
.cost
= 0;
1647 vertex
->root_id
= vertex
->id
;
1648 vertex
->demoted
= false;
1652 * returns the id of the component containing 'vertex' by traversing the up-tree
1653 * implied by the component pointers.
1655 static struct GUID
kcctpl_get_component_id(struct kcctpl_graph
*graph
,
1656 struct kcctpl_vertex
*vertex
)
1658 struct kcctpl_vertex
*u
;
1662 while (!GUID_equal(&u
->component_id
, &u
->id
)) {
1663 u
= kcctpl_find_vertex_by_guid(graph
, u
->component_id
);
1669 while (!GUID_equal(&u
->component_id
, &u
->id
)) {
1670 struct kcctpl_vertex
*w
;
1672 w
= kcctpl_find_vertex_by_guid(graph
, u
->component_id
);
1673 u
->component_id
= root
;
1681 * copy all spanning tree edges from 'output_edges' that contain the vertex for
1682 * DCs in the local DC's site.
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
)
1690 struct kcctpl_multi_edge_list copy
;
1691 TALLOC_CTX
*tmp_ctx
;
1692 struct ldb_message
*site
;
1693 struct GUID site_guid
;
1698 tmp_ctx
= talloc_new(service
);
1699 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1701 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
1703 DEBUG(1, (__location__
": failed to find our own local DC's "
1706 talloc_free(tmp_ctx
);
1707 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1709 site_guid
= samdb_result_guid(site
, "objectGUID");
1711 for (i
= 0; i
< output_edges
.count
; i
++) {
1712 struct kcctpl_multi_edge
*edge
;
1713 struct kcctpl_vertex
*vertex1
, *vertex2
;
1715 edge
= &output_edges
.data
[i
];
1717 vertex1
= kcctpl_find_vertex_by_guid(graph
,
1718 edge
->vertex_ids
.data
[0]);
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
;
1727 vertex2
= kcctpl_find_vertex_by_guid(graph
,
1728 edge
->vertex_ids
.data
[1]);
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
;
1737 if (GUID_equal(&vertex1
->id
, &site_guid
) ||
1738 GUID_equal(&vertex2
->id
, &site_guid
)) {
1739 struct kcctpl_multi_edge
*new_data
;
1741 if ((vertex1
->color
== BLACK
||
1742 vertex2
->color
== BLACK
) &&
1743 vertex1
->dist_to_red
!= UINT32_MAX
) {
1745 edge
->directed
= true;
1747 if (vertex2
->dist_to_red
<
1748 vertex1
->dist_to_red
) {
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
;
1757 new_data
= talloc_realloc(tmp_ctx
, copy
.data
,
1758 struct kcctpl_multi_edge
,
1760 if (new_data
== NULL
) {
1761 TALLOC_FREE(tmp_ctx
);
1762 return NT_STATUS_NO_MEMORY
;
1764 new_data
[copy
.count
+ 1] = *edge
;
1765 copy
.data
= new_data
;
1770 talloc_steal(mem_ctx
, copy
.data
);
1771 talloc_free(tmp_ctx
);
1773 return NT_STATUS_OK
;
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
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
)
1787 struct kcctpl_vertex_list vertices
;
1790 kcctpl_setup_vertices(graph
);
1792 ZERO_STRUCT(vertices
);
1794 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1795 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
1797 if (vertex
->color
== WHITE
) {
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;
1808 struct kcctpl_vertex
*new_data
;
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
;
1820 *_vertices
= vertices
;
1821 return NT_STATUS_OK
;
1825 * merge schedules, replication intervals, options and costs.
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
)
1832 uint8_t schedule
[84];
1837 is_available
= false;
1838 for (i
= 0; i
< 84; i
++) {
1839 schedule
[i
] = ria
->schedule
[i
] & rib
->schedule
[i
];
1841 if (schedule
[i
] == 1) {
1842 is_available
= true;
1845 if (!is_available
) {
1849 ric_cost
= ria
->cost
+ rib
->cost
;
1850 ric
->cost
= (ric_cost
< 0) ? UINT32_MAX
: ric_cost
;
1852 ric
->interval
= MAX(ria
->interval
, rib
->interval
);
1853 ric
->options
= ria
->options
& rib
->options
;
1854 memcpy(&ric
->schedule
, &schedule
, 84);
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.
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
)
1873 struct kcctpl_repl_info new_repl_info
;
1875 uint32_t i
, new_duration
, old_duration
;
1877 ZERO_STRUCT(new_repl_info
);
1879 intersect
= kcctpl_combine_repl_info(graph
, &vertex1
->repl_info
,
1880 &edge
->repl_info
, &new_repl_info
);
1882 if (new_repl_info
.cost
> vertex2
->repl_info
.cost
) {
1883 return NT_STATUS_OK
;
1886 if (new_repl_info
.cost
< vertex2
->repl_info
.cost
&& !intersect
) {
1887 return NT_STATUS_OK
;
1890 new_duration
= old_duration
= 0;
1891 for (i
= 0; i
< 84; i
++) {
1892 if (new_repl_info
.schedule
[i
] == 1) {
1896 if (vertex2
->repl_info
.schedule
[i
] == 1) {
1901 if (new_repl_info
.cost
< vertex2
->repl_info
.cost
||
1902 new_duration
> old_duration
) {
1903 struct kcctpl_vertex
*new_data
;
1905 vertex2
->root_id
= vertex1
->root_id
;
1906 vertex2
->component_id
= vertex1
->component_id
;
1907 vertex2
->repl_info
= new_repl_info
;
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
;
1918 return NT_STATUS_OK
;
1922 * run Dijkstra's algorithm with the red (and possibly black) vertices as the
1923 * root vertices, and build up a shortest-path forest.
1925 static NTSTATUS
kcctpl_dijkstra(struct kcctpl_graph
*graph
, struct GUID type
,
1928 TALLOC_CTX
*tmp_ctx
;
1929 struct kcctpl_vertex_list vertices
;
1932 tmp_ctx
= talloc_new(graph
);
1933 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1935 status
= kcctpl_setup_dijkstra(tmp_ctx
, graph
, type
, include_black
,
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
)));
1941 talloc_free(tmp_ctx
);
1945 while (vertices
.count
> 0) {
1946 uint32_t minimum_cost
, minimum_index
, i
;
1947 struct kcctpl_vertex
*minimum_vertex
, *new_data
;
1949 minimum_cost
= UINT32_MAX
;
1951 minimum_vertex
= NULL
;
1952 for (i
= 0; i
< vertices
.count
; i
++) {
1953 struct kcctpl_vertex
*vertex
= &vertices
.data
[i
];
1955 if (vertex
->repl_info
.cost
< minimum_cost
) {
1956 minimum_cost
= vertex
->repl_info
.cost
;
1957 minimum_vertex
= vertex
;
1959 } else if (vertex
->repl_info
.cost
== minimum_cost
&&
1960 GUID_compare(&vertex
->id
,
1961 &minimum_vertex
->id
) < 0) {
1962 minimum_vertex
= vertex
;
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);
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
;
1979 talloc_free(vertices
.data
);
1980 vertices
.data
= new_data
;
1983 for (i
= 0; i
< graph
->edges
.count
; i
++) {
1984 struct kcctpl_multi_edge
*edge
= &graph
->edges
.data
[i
];
1986 if (kcctpl_guid_list_contains(minimum_vertex
->edge_ids
,
1990 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
1991 struct GUID vertex_id
;
1992 struct kcctpl_vertex
*vertex
;
1994 vertex_id
= edge
->vertex_ids
.data
[j
];
1995 vertex
= kcctpl_find_vertex_by_guid(graph
,
1998 DEBUG(1, (__location__
2001 GUID_string(tmp_ctx
,
2004 talloc_free(tmp_ctx
);
2005 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2008 kcctpl_try_new_path(tmp_ctx
, graph
,
2017 talloc_free(tmp_ctx
);
2018 return NT_STATUS_OK
;
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.
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
)
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
;
2039 root1
= kcctpl_find_vertex_by_guid(graph
, vertex1
->root_id
);
2041 TALLOC_CTX
*tmp_ctx
= talloc_new(graph
);
2042 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2044 DEBUG(1, (__location__
": failed to find vertex %s\n",
2045 GUID_string(tmp_ctx
, &vertex1
->root_id
)));
2047 talloc_free(tmp_ctx
);
2048 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2051 root2
= kcctpl_find_vertex_by_guid(graph
, vertex2
->root_id
);
2053 TALLOC_CTX
*tmp_ctx
= talloc_new(graph
);
2054 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2056 DEBUG(1, (__location__
": failed to find vertex %s\n",
2057 GUID_string(tmp_ctx
, &vertex2
->root_id
)));
2059 talloc_free(tmp_ctx
);
2060 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2063 red_red
= (root1
->color
== RED
&& root2
->color
== RED
);
2066 if (!kcctpl_guid_list_contains(root1
->accept_red_red
,
2068 !kcctpl_guid_list_contains(root2
->accept_red_red
,
2070 return NT_STATUS_OK
;
2072 } else if (!kcctpl_guid_list_contains(root1
->accept_black
,
2074 !kcctpl_guid_list_contains(root2
->accept_black
,
2076 return NT_STATUS_OK
;
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
,
2083 return NT_STATUS_OK
;
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
;
2092 if (GUID_compare(&new_internal_edge
.v1id
,
2093 &new_internal_edge
.v2id
) > 0) {
2094 struct GUID tmp_guid
= new_internal_edge
.v1id
;
2096 new_internal_edge
.v1id
= new_internal_edge
.v2id
;
2097 new_internal_edge
.v2id
= tmp_guid
;
2101 for (i
= 0; i
< internal_edges
.count
; i
++) {
2102 struct kcctpl_internal_edge
*ie
= &internal_edges
.data
[i
];
2104 if (kcctpl_internal_edge_equal(ie
, &new_internal_edge
)) {
2109 return NT_STATUS_OK
;
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
++;
2120 return NT_STATUS_OK
;
2124 * after running Dijkstra's algorithm, this function examines a multi-edge and
2125 * adds internal edges between every tree connected by this edge.
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
)
2132 TALLOC_CTX
*tmp_ctx
;
2133 struct kcctpl_vertex_list vertices
;
2135 struct kcctpl_vertex
*best_vertex
;
2137 ZERO_STRUCT(vertices
);
2139 tmp_ctx
= talloc_new(mem_ctx
);
2140 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2142 for (i
= 0; i
< edge
->vertex_ids
.count
; i
++) {
2144 struct kcctpl_vertex
*vertex
, *new_data
;
2146 id
= edge
->vertex_ids
.data
[i
];
2148 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2150 DEBUG(1, (__location__
": failed to find vertex %s\n",
2151 GUID_string(tmp_ctx
, &id
)));
2153 talloc_free(tmp_ctx
);
2154 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
;
2164 new_data
[vertices
.count
] = *vertex
;
2165 vertices
.data
= new_data
;
2169 qsort(vertices
.data
, vertices
.count
, sizeof(struct kcctpl_vertex
),
2170 kcctpl_sort_vertices
);
2172 best_vertex
= &vertices
.data
[0];
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
];
2178 id
= edge
->vertex_ids
.data
[i
];
2180 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2182 DEBUG(1, (__location__
": failed to find vertex %s\n",
2183 GUID_string(tmp_ctx
, &id
)));
2185 talloc_free(tmp_ctx
);
2186 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2189 if (!GUID_equal(&vertex
->component_id
, &empty_id
) &&
2190 !GUID_equal(&vertex
->root_id
, &empty_id
)) {
2194 if (!GUID_equal(&best_vertex
->component_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
)) {
2203 status
= kcctpl_add_int_edge(mem_ctx
, graph
,
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
);
2218 talloc_free(tmp_ctx
);
2219 return NT_STATUS_OK
;
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.
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
)
2236 for (i
= 0; i
< graph
->edges
.count
; i
++) {
2237 struct kcctpl_multi_edge
*edge
;
2241 edge
= &graph
->edges
.data
[i
];
2243 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
2245 struct kcctpl_vertex
*vertex
;
2247 id
= edge
->vertex_ids
.data
[j
];
2249 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2251 TALLOC_CTX
*tmp_ctx
;
2253 tmp_ctx
= talloc_new(mem_ctx
);
2254 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2256 DEBUG(1, (__location__
": failed to "
2258 GUID_string(tmp_ctx
, &id
)));
2260 talloc_free(tmp_ctx
);
2261 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2264 kcctpl_check_demote_one_vertex(vertex
,
2268 status
= kcctpl_process_edge(mem_ctx
, graph
, edge
,
2270 if (NT_STATUS_IS_ERR(status
)) {
2271 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2272 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2274 DEBUG(1, (__location__
": failed to process "
2276 GUID_string(tmp_ctx
, &edge
->id
),
2277 nt_errstr(status
)));
2279 talloc_free(tmp_ctx
);
2283 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
2285 struct kcctpl_vertex
*vertex
;
2287 id
= edge
->vertex_ids
.data
[j
];
2289 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2291 TALLOC_CTX
*tmp_ctx
;
2293 tmp_ctx
= talloc_new(mem_ctx
);
2294 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2296 DEBUG(1, (__location__
": failed to "
2298 GUID_string(tmp_ctx
, &id
)));
2300 talloc_free(tmp_ctx
);
2301 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2304 kcctpl_undemote_one_vertex(vertex
);
2308 for (i
= 0; i
< graph
->edges
.count
; i
++) {
2309 struct kcctpl_multi_edge
*edge
= &graph
->edges
.data
[i
];
2311 if (kcctpl_guid_list_contains(set
->edge_ids
,
2315 status
= kcctpl_process_edge(mem_ctx
, graph
,
2318 if (NT_STATUS_IS_ERR(status
)) {
2319 TALLOC_CTX
*tmp_ctx
;
2321 tmp_ctx
= talloc_new(mem_ctx
);
2322 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2324 DEBUG(1, (__location__
": failed to "
2325 "process edge %s: %s\n",
2326 GUID_string(tmp_ctx
,
2328 nt_errstr(status
)));
2330 talloc_free(tmp_ctx
);
2337 return NT_STATUS_OK
;
2341 * a new edge, 'internal_edge', has been found for the spanning tree edge. add
2342 * this edge to the list of output edges.
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
)
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
;
2354 tmp_ctx
= talloc_new(mem_ctx
);
2355 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2357 vertex1
= kcctpl_find_vertex_by_guid(graph
, internal_edge
->v1id
);
2359 DEBUG(1, (__location__
": failed to find vertex %s\n",
2360 GUID_string(tmp_ctx
, &internal_edge
->v1id
)));
2362 talloc_free(tmp_ctx
);
2363 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2366 vertex2
= kcctpl_find_vertex_by_guid(graph
, internal_edge
->v2id
);
2368 DEBUG(1, (__location__
": failed to find vertex %s\n",
2369 GUID_string(tmp_ctx
, &internal_edge
->v2id
)));
2371 talloc_free(tmp_ctx
);
2372 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
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
;
2381 new_edge
->id
= GUID_random(); /* TODO: what should be new_edge->GUID? */
2382 new_edge
->directed
= false;
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
;
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;
2394 new_edge
->type
= internal_edge
->type
;
2395 new_edge
->repl_info
= internal_edge
->repl_info
;
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
;
2404 new_data
[output_edges
.count
+ 1] = *new_edge
;
2405 output_edges
.data
= new_data
;
2406 output_edges
.count
++;
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
;
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
++;
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
;
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
++;
2430 talloc_steal(graph
, new_edge
);
2431 talloc_steal(mem_ctx
, output_edges
.data
);
2432 talloc_free(tmp_ctx
);
2433 return NT_STATUS_OK
;
2437 * run Kruskal's minimum-cost spanning tree algorithm on the internal edges
2438 * (that represent shortest paths in the original graph between colored
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
)
2445 uint32_t i
, num_expected_tree_edges
, cst_edges
;
2446 struct kcctpl_multi_edge_list output_edges
;
2448 num_expected_tree_edges
= 0;
2449 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2450 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2452 talloc_free(vertex
->edge_ids
.data
);
2453 ZERO_STRUCT(vertex
->edge_ids
);
2455 if (vertex
->color
== RED
|| vertex
->color
== WHITE
) {
2456 num_expected_tree_edges
++;
2460 qsort(internal_edges
.data
, internal_edges
.count
,
2461 sizeof(struct kcctpl_internal_edge
), kcctpl_sort_internal_edges
);
2465 ZERO_STRUCT(output_edges
);
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
;
2473 edge
= &internal_edges
.data
[0];
2475 vertex1
= kcctpl_find_vertex_by_guid(graph
, edge
->v1id
);
2477 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2478 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2480 DEBUG(1, (__location__
": failed to find vertex %s\n",
2481 GUID_string(tmp_ctx
, &edge
->v1id
)));
2483 talloc_free(tmp_ctx
);
2484 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2487 vertex2
= kcctpl_find_vertex_by_guid(graph
, edge
->v2id
);
2489 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2490 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2492 DEBUG(1, (__location__
": failed to find vertex %s\n",
2493 GUID_string(tmp_ctx
, &edge
->v2id
)));
2495 talloc_free(tmp_ctx
);
2496 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2499 comp1
= kcctpl_get_component_id(graph
, vertex1
);
2500 comp2
= kcctpl_get_component_id(graph
, vertex2
);
2502 if (!GUID_equal(&comp1
, &comp2
)) {
2504 struct kcctpl_vertex
*vertex
;
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
);
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
)));
2520 talloc_free(tmp_ctx
);
2524 vertex
= kcctpl_find_vertex_by_guid(graph
, comp1
);
2526 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2527 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2529 DEBUG(1, (__location__
": failed to find "
2530 "vertex %s\n", GUID_string(tmp_ctx
,
2533 talloc_free(tmp_ctx
);
2534 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2536 vertex
->component_id
= comp2
;
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
--;
2549 *_output_edges
= output_edges
;
2550 return NT_STATUS_OK
;
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
2559 static uint32_t kcctpl_count_components(struct kcctpl_graph
*graph
)
2561 uint32_t num_components
= 0, i
;
2563 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2564 struct kcctpl_vertex
*vertex
;
2565 struct GUID component_id
;
2567 vertex
= &graph
->vertices
.data
[i
];
2569 if (vertex
->color
== WHITE
) {
2573 component_id
= kcctpl_get_component_id(graph
, vertex
);
2574 if (GUID_equal(&component_id
, &vertex
->id
)) {
2575 vertex
->component_index
= num_components
;
2580 return num_components
;
2584 * calculate the spanning tree and return the edges that include the vertex for
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
)
2593 TALLOC_CTX
*tmp_ctx
;
2594 struct kcctpl_internal_edge_list internal_edges
;
2595 uint32_t i
, component_count
;
2597 struct kcctpl_multi_edge_list output_edges
, st_edge_list
;
2599 ZERO_STRUCT(internal_edges
);
2601 tmp_ctx
= talloc_new(mem_ctx
);
2602 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2604 for (i
= 0; i
< graph
->edge_sets
.count
; i
++) {
2605 struct kcctpl_multi_edge_set
*set
;
2606 struct GUID edge_type
;
2609 set
= &graph
->edge_sets
.data
[i
];
2611 edge_type
= GUID_zero();
2613 for (j
= 0; j
< graph
->vertices
.count
; j
++) {
2614 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[j
];
2616 talloc_free(vertex
->edge_ids
.data
);
2617 ZERO_STRUCT(vertex
->edge_ids
.data
);
2620 for (j
= 0; j
< set
->edge_ids
.count
; j
++) {
2621 struct GUID edge_id
;
2622 struct kcctpl_multi_edge
*edge
;
2625 edge_id
= set
->edge_ids
.data
[j
];
2626 edge
= kcctpl_find_edge_by_guid(graph
, edge_id
);
2628 DEBUG(1, (__location__
": failed to find a "
2629 "graph edge with ID=%s\n",
2630 GUID_string(tmp_ctx
, &edge_id
)));
2632 talloc_free(tmp_ctx
);
2633 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2636 edge_type
= edge
->type
;
2638 for (k
= 0; k
< edge
->vertex_ids
.count
; k
++) {
2639 struct GUID vertex_id
, *new_data
;
2640 struct kcctpl_vertex
*vertex
;
2642 vertex_id
= edge
->vertex_ids
.data
[k
];
2643 vertex
= kcctpl_find_vertex_by_guid(graph
,
2646 DEBUG(1, (__location__
": failed to "
2647 "find a graph vertex with "
2649 GUID_string(tmp_ctx
,
2652 talloc_free(tmp_ctx
);
2653 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2656 new_data
= talloc_realloc(tmp_ctx
,
2657 vertex
->edge_ids
.data
,
2659 vertex
->edge_ids
.count
+ 1);
2660 if (new_data
== NULL
) {
2661 TALLOC_FREE(tmp_ctx
);
2662 return NT_STATUS_NO_MEMORY
;
2664 new_data
[vertex
->edge_ids
.count
] = edge
->id
;
2665 vertex
->edge_ids
.data
= new_data
;
2666 vertex
->edge_ids
.count
++;
2670 status
= kcctpl_dijkstra(graph
, edge_type
, false);
2671 if (NT_STATUS_IS_ERR(status
)) {
2672 DEBUG(1, (__location__
": failed to run Dijkstra's "
2673 "algorithm: %s\n", nt_errstr(status
)));
2675 talloc_free(tmp_ctx
);
2679 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, set
,
2681 if (NT_STATUS_IS_ERR(status
)) {
2682 DEBUG(1, (__location__
": failed to process edge set "
2683 "%s: %s\n", GUID_string(tmp_ctx
, &set
->id
),
2684 nt_errstr(status
)));
2686 talloc_free(tmp_ctx
);
2690 status
= kcctpl_dijkstra(graph
, edge_type
, true);
2691 if (NT_STATUS_IS_ERR(status
)) {
2692 DEBUG(1, (__location__
": failed to run Dijkstra's "
2693 "algorithm: %s\n", nt_errstr(status
)));
2695 talloc_free(tmp_ctx
);
2699 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, set
,
2701 if (NT_STATUS_IS_ERR(status
)) {
2702 DEBUG(1, (__location__
": failed to process edge set "
2703 "%s: %s\n", GUID_string(tmp_ctx
, &set
->id
),
2704 nt_errstr(status
)));
2706 talloc_free(tmp_ctx
);
2711 kcctpl_setup_vertices(graph
);
2713 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, NULL
, internal_edges
);
2714 if (NT_STATUS_IS_ERR(status
)) {
2715 DEBUG(1, (__location__
": failed to process empty edge set: "
2716 "%s\n", nt_errstr(status
)));
2718 talloc_free(tmp_ctx
);
2722 status
= kcctpl_kruskal(tmp_ctx
, graph
, internal_edges
, &output_edges
);
2723 if (NT_STATUS_IS_ERR(status
)) {
2724 DEBUG(1, (__location__
": failed to run Kruskal's algorithm: "
2725 "%s\n", nt_errstr(status
)));
2727 talloc_free(tmp_ctx
);
2731 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2732 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2734 if (vertex
->color
== RED
) {
2735 vertex
->dist_to_red
= 0;
2736 } else if (true) { /* TODO: if there exists a path from 'vertex'
2738 vertex
->dist_to_red
= -1; /* TODO: the length of the
2739 shortest such path */
2741 vertex
->dist_to_red
= UINT32_MAX
;
2745 component_count
= kcctpl_count_components(graph
);
2747 status
= kcctpl_copy_output_edges(service
, tmp_ctx
, graph
, output_edges
,
2749 if (NT_STATUS_IS_ERR(status
)) {
2750 DEBUG(1, (__location__
": failed to copy edge list: %s\n",
2751 nt_errstr(status
)));
2753 talloc_free(tmp_ctx
);
2757 *_component_count
= component_count
;
2758 talloc_steal(mem_ctx
, st_edge_list
.data
);
2759 *_st_edge_list
= st_edge_list
;
2760 talloc_free(tmp_ctx
);
2761 return NT_STATUS_OK
;
2765 * creat an nTDSConnection object with the given parameters if one does not
2768 static NTSTATUS
kcctpl_create_connection(struct kccsrv_service
*service
,
2769 TALLOC_CTX
*mem_ctx
,
2770 struct ldb_message
*cross_ref
,
2771 struct ldb_message
*r_bridgehead
,
2772 struct ldb_message
*transport
,
2773 struct ldb_message
*l_bridgehead
,
2774 struct kcctpl_repl_info repl_info
,
2775 uint8_t schedule
[84],
2776 bool detect_failed_dcs
,
2777 bool partial_replica_okay
,
2778 struct GUID_list
*_keep_connections
)
2780 TALLOC_CTX
*tmp_ctx
;
2781 struct ldb_dn
*r_site_dn
, *l_site_dn
, *servers_dn
;
2783 struct GUID r_site_guid
, l_site_guid
;
2785 struct message_list r_bridgeheads_all
, l_bridgeheads_all
,
2786 r_bridgeheads_available
, l_bridgeheads_available
;
2788 struct ldb_result
*res
;
2789 const char * const attrs
[] = { "objectGUID", "parent", "fromServer",
2790 "transportType", "schedule", "options",
2791 "enabledConnection", NULL
};
2792 unsigned int i
, valid_connections
;
2793 struct GUID_list keep_connections
;
2795 tmp_ctx
= talloc_new(service
);
2796 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2798 r_site_dn
= ldb_dn_copy(tmp_ctx
, r_bridgehead
->dn
);
2799 if (r_site_dn
== NULL
) {
2800 TALLOC_FREE(tmp_ctx
);
2801 return NT_STATUS_NO_MEMORY
;
2804 ok
= ldb_dn_remove_child_components(r_site_dn
, 3);
2806 talloc_free(tmp_ctx
);
2807 return NT_STATUS_NO_MEMORY
;
2810 ret
= dsdb_find_guid_by_dn(service
->samdb
, r_site_dn
, &r_site_guid
);
2811 if (ret
!= LDB_SUCCESS
) {
2812 DEBUG(1, (__location__
": failed to find objectGUID for object "
2813 "%s: %s\n", ldb_dn_get_linearized(r_site_dn
),
2814 ldb_strerror(ret
)));
2816 talloc_free(tmp_ctx
);
2817 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2820 l_site_dn
= ldb_dn_copy(tmp_ctx
, l_bridgehead
->dn
);
2821 if (l_site_dn
== NULL
) {
2822 TALLOC_FREE(tmp_ctx
);
2823 return NT_STATUS_NO_MEMORY
;
2826 ok
= ldb_dn_remove_child_components(l_site_dn
, 3);
2828 talloc_free(tmp_ctx
);
2829 return NT_STATUS_NO_MEMORY
;
2832 ret
= dsdb_find_guid_by_dn(service
->samdb
, l_site_dn
, &l_site_guid
);
2833 if (ret
!= LDB_SUCCESS
) {
2834 DEBUG(1, (__location__
": failed to find objectGUID for object "
2835 "%s: %s\n", ldb_dn_get_linearized(l_site_dn
),
2836 ldb_strerror(ret
)));
2838 talloc_free(tmp_ctx
);
2839 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2842 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2843 r_site_guid
, cross_ref
,
2844 transport
, partial_replica_okay
,
2845 false, &r_bridgeheads_all
);
2846 if (NT_STATUS_IS_ERR(status
)) {
2847 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2848 "%s\n", nt_errstr(status
)));
2852 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2853 r_site_guid
, cross_ref
,
2854 transport
, partial_replica_okay
,
2856 &r_bridgeheads_available
);
2857 if (NT_STATUS_IS_ERR(status
)) {
2858 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2859 "%s\n", nt_errstr(status
)));
2863 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2864 l_site_guid
, cross_ref
,
2865 transport
, partial_replica_okay
,
2866 false, &l_bridgeheads_all
);
2867 if (NT_STATUS_IS_ERR(status
)) {
2868 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2869 "%s\n", nt_errstr(status
)));
2873 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2874 l_site_guid
, cross_ref
,
2875 transport
, partial_replica_okay
,
2877 &l_bridgeheads_available
);
2878 if (NT_STATUS_IS_ERR(status
)) {
2879 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2880 "%s\n", nt_errstr(status
)));
2884 servers_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
2886 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
2888 talloc_free(tmp_ctx
);
2889 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2891 ok
= ldb_dn_add_child_fmt(servers_dn
, "CN=Servers");
2893 talloc_free(tmp_ctx
);
2894 return NT_STATUS_NO_MEMORY
;
2897 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, servers_dn
, LDB_SCOPE_SUBTREE
,
2898 attrs
, "objectClass=nTDSConnection");
2899 if (ret
!= LDB_SUCCESS
) {
2900 DEBUG(1, (__location__
": failed to find nTDSConnection "
2901 "objects: %s\n", ldb_strerror(ret
)));
2903 talloc_free(tmp_ctx
);
2904 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2907 for (i
= 0; i
< res
->count
; i
++) {
2908 struct ldb_message
*connection
;
2909 struct ldb_dn
*parent_dn
, *from_server
;
2911 connection
= res
->msgs
[i
];
2913 parent_dn
= ldb_dn_get_parent(tmp_ctx
, connection
->dn
);
2915 DEBUG(1, (__location__
": failed to get parent DN of "
2917 ldb_dn_get_linearized(connection
->dn
)));
2919 talloc_free(tmp_ctx
);
2920 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2923 from_server
= samdb_result_dn(service
->samdb
, tmp_ctx
, connection
,
2924 "fromServer", NULL
);
2926 DEBUG(1, (__location__
": failed to find fromServer "
2927 "attribute of object %s\n",
2928 ldb_dn_get_linearized(connection
->dn
)));
2930 talloc_free(tmp_ctx
);
2931 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2934 if (kcctpl_message_list_contains_dn(l_bridgeheads_all
,
2936 kcctpl_message_list_contains_dn(r_bridgeheads_all
,
2939 /* TODO: initialize conn_schedule from connection */
2940 uint8_t conn_schedule
[84];
2941 struct ldb_dn
*conn_transport_type
;
2943 conn_opts
= ldb_msg_find_attr_as_uint(connection
,
2946 conn_transport_type
= samdb_result_dn(service
->samdb
, tmp_ctx
,
2950 if (!conn_transport_type
) {
2951 DEBUG(1, (__location__
": failed to find "
2952 "transportType attribute of object "
2954 ldb_dn_get_linearized(connection
->dn
)));
2956 talloc_free(tmp_ctx
);
2957 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2960 if ((conn_opts
& NTDSCONN_OPT_IS_GENERATED
) &&
2961 !(conn_opts
& NTDSCONN_OPT_RODC_TOPOLOGY
) &&
2962 ldb_dn_compare(conn_transport_type
,
2963 transport
->dn
) == 0) {
2964 if (!(conn_opts
& NTDSCONN_OPT_USER_OWNED_SCHEDULE
) &&
2965 memcmp(&conn_schedule
, &schedule
, 84) != 0) {
2966 /* TODO: perform an originating update
2967 to set conn!schedule to schedule */
2970 if ((conn_opts
& NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
) &&
2971 (conn_opts
& NTDSCONN_OPT_USE_NOTIFY
)) {
2972 if (!(repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
)) {
2973 /* TODO: perform an originating
2974 update to clear bits
2975 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2976 and NTDSCONN_OPT_USE_NOTIFY
2979 } else if (repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
) {
2980 /* TODO: perform an originating update
2982 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2983 and NTDSCONN_OPT_USE_NOTIFY in
2987 if (conn_opts
& NTDSCONN_OPT_TWOWAY_SYNC
) {
2988 if (!(repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
)) {
2989 /* TODO: perform an originating
2991 NTDSCONN_OPT_TWOWAY_SYNC in
2994 } else if (repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
) {
2995 /* TODO: perform an originating update
2996 to set bit NTDSCONN_OPT_TWOWAY_SYNC
3000 if (conn_opts
& NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
) {
3001 if (!(repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
)) {
3002 /* TODO: perform an originating
3004 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
3007 } else if (repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
) {
3008 /* TODO: perform an originating update
3010 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
3017 ZERO_STRUCT(keep_connections
);
3019 valid_connections
= 0;
3020 for (i
= 0; i
< res
->count
; i
++) {
3021 struct ldb_message
*connection
;
3022 struct ldb_dn
*parent_dn
, *from_server
;
3024 connection
= res
->msgs
[i
];
3026 parent_dn
= ldb_dn_get_parent(tmp_ctx
, connection
->dn
);
3028 DEBUG(1, (__location__
": failed to get parent DN of "
3030 ldb_dn_get_linearized(connection
->dn
)));
3032 talloc_free(tmp_ctx
);
3033 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3036 from_server
= samdb_result_dn(service
->samdb
, tmp_ctx
, connection
,
3037 "fromServer", NULL
);
3039 DEBUG(1, (__location__
": failed to find fromServer "
3040 "attribute of object %s\n",
3041 ldb_dn_get_linearized(connection
->dn
)));
3043 talloc_free(tmp_ctx
);
3044 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3047 if (kcctpl_message_list_contains_dn(l_bridgeheads_all
,
3049 kcctpl_message_list_contains_dn(r_bridgeheads_all
,
3052 struct ldb_dn
*conn_transport_type
;
3054 conn_opts
= ldb_msg_find_attr_as_uint(connection
,
3057 conn_transport_type
= samdb_result_dn(service
->samdb
, tmp_ctx
,
3061 if (!conn_transport_type
) {
3062 DEBUG(1, (__location__
": failed to find "
3063 "transportType attribute of object "
3065 ldb_dn_get_linearized(connection
->dn
)));
3067 talloc_free(tmp_ctx
);
3068 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3071 if ((!(conn_opts
& NTDSCONN_OPT_IS_GENERATED
) ||
3072 ldb_dn_compare(conn_transport_type
,
3073 transport
->dn
) == 0) &&
3074 !(conn_opts
& NTDSCONN_OPT_RODC_TOPOLOGY
)) {
3075 struct GUID r_guid
, l_guid
, conn_guid
;
3076 bool failed_state_r
, failed_state_l
;
3078 ret
= dsdb_find_guid_by_dn(service
->samdb
, from_server
,
3080 if (ret
!= LDB_SUCCESS
) {
3081 DEBUG(1, (__location__
": failed to "
3082 "find GUID for object %s\n",
3083 ldb_dn_get_linearized(from_server
)));
3085 talloc_free(tmp_ctx
);
3086 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3089 ret
= dsdb_find_guid_by_dn(service
->samdb
, parent_dn
,
3091 if (ret
!= LDB_SUCCESS
) {
3092 DEBUG(1, (__location__
": failed to "
3093 "find GUID for object %s\n",
3094 ldb_dn_get_linearized(parent_dn
)));
3096 talloc_free(tmp_ctx
);
3097 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3100 status
= kcctpl_bridgehead_dc_failed(service
->samdb
,
3104 if (NT_STATUS_IS_ERR(status
)) {
3105 DEBUG(1, (__location__
": failed to "
3106 "check if bridgehead DC has "
3108 nt_errstr(status
)));
3110 talloc_free(tmp_ctx
);
3114 status
= kcctpl_bridgehead_dc_failed(service
->samdb
,
3118 if (NT_STATUS_IS_ERR(status
)) {
3119 DEBUG(1, (__location__
": failed to "
3120 "check if bridgehead DC has "
3122 nt_errstr(status
)));
3124 talloc_free(tmp_ctx
);
3128 if (!failed_state_r
&& !failed_state_l
) {
3129 valid_connections
++;
3132 conn_guid
= samdb_result_guid(connection
,
3135 if (!kcctpl_guid_list_contains(keep_connections
,
3137 struct GUID
*new_data
;
3139 new_data
= talloc_realloc(tmp_ctx
,
3140 keep_connections
.data
,
3142 keep_connections
.count
+ 1);
3143 if (new_data
== NULL
) {
3144 TALLOC_FREE(tmp_ctx
);
3145 return NT_STATUS_NO_MEMORY
;
3147 new_data
[keep_connections
.count
] = conn_guid
;
3148 keep_connections
.data
= new_data
;
3149 keep_connections
.count
++;
3155 if (valid_connections
== 0) {
3156 uint64_t opts
= NTDSCONN_OPT_IS_GENERATED
;
3157 struct GUID new_guid
, *new_data
;
3159 if (repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
) {
3160 opts
|= NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
;
3161 opts
|= NTDSCONN_OPT_USE_NOTIFY
;
3164 if (repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
) {
3165 opts
|= NTDSCONN_OPT_TWOWAY_SYNC
;
3168 if (repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
) {
3169 opts
|= NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
;
3172 /* perform an originating update to create a new nTDSConnection
3173 * object cn that is:
3175 * - child of l_bridgehead
3176 * - cn!enabledConnection = true
3177 * - cn!options = opts
3178 * - cn!transportType = t
3179 * - cn!fromServer = r_bridgehead
3180 * - cn!schedule = schedule
3183 /* TODO: what should be the new connection's GUID? */
3184 new_guid
= GUID_random();
3186 new_data
= talloc_realloc(tmp_ctx
, keep_connections
.data
,
3188 keep_connections
.count
+ 1);
3189 if (new_data
== NULL
) {
3190 TALLOC_FREE(tmp_ctx
);
3191 return NT_STATUS_NO_MEMORY
;
3193 new_data
[keep_connections
.count
] = new_guid
;
3194 keep_connections
.data
= new_data
;
3195 keep_connections
.count
++;
3198 talloc_steal(mem_ctx
, keep_connections
.data
);
3199 *_keep_connections
= keep_connections
;
3200 talloc_free(tmp_ctx
);
3201 return NT_STATUS_OK
;
3205 * construct an NC replica graph for the NC identified by the given 'cross_ref',
3206 * then create any additional nTDSConnection objects required.
3208 static NTSTATUS
kcctpl_create_connections(struct kccsrv_service
*service
,
3209 TALLOC_CTX
*mem_ctx
,
3210 struct kcctpl_graph
*graph
,
3211 struct ldb_message
*cross_ref
,
3212 bool detect_failed_dcs
,
3213 struct GUID_list keep_connections
,
3214 bool *_found_failed_dcs
,
3217 bool connected
, found_failed_dcs
, partial_replica_okay
;
3219 struct ldb_message
*site
;
3220 TALLOC_CTX
*tmp_ctx
;
3221 struct GUID site_guid
;
3222 struct kcctpl_vertex
*site_vertex
;
3223 uint32_t component_count
, i
;
3224 struct kcctpl_multi_edge_list st_edge_list
;
3225 struct ldb_dn
*transports_dn
;
3226 const char * const attrs
[] = { "bridgeheadServerListBL", "name",
3227 "transportAddressAttribute", NULL
};
3232 status
= kcctpl_color_vertices(service
, graph
, cross_ref
, detect_failed_dcs
,
3234 if (NT_STATUS_IS_ERR(status
)) {
3235 DEBUG(1, (__location__
": failed to color vertices: %s\n",
3236 nt_errstr(status
)));
3241 tmp_ctx
= talloc_new(mem_ctx
);
3242 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
3244 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
3246 DEBUG(1, (__location__
": failed to find our own local DC's "
3249 talloc_free(tmp_ctx
);
3250 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3253 site_guid
= samdb_result_guid(site
, "objectGUID");
3255 site_vertex
= kcctpl_find_vertex_by_guid(graph
, site_guid
);
3257 DEBUG(1, (__location__
": failed to find vertex %s\n",
3258 GUID_string(tmp_ctx
, &site_guid
)));
3260 talloc_free(tmp_ctx
);
3261 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3264 if (site_vertex
->color
== WHITE
) {
3265 *_found_failed_dcs
= found_failed_dcs
;
3267 talloc_free(tmp_ctx
);
3268 return NT_STATUS_OK
;
3271 status
= kcctpl_get_spanning_tree_edges(service
, tmp_ctx
, graph
,
3274 if (NT_STATUS_IS_ERR(status
)) {
3275 DEBUG(1, (__location__
": failed get spanning tree edges: %s\n",
3276 nt_errstr(status
)));
3278 talloc_free(tmp_ctx
);
3282 if (component_count
> 1) {
3286 partial_replica_okay
= (site_vertex
->color
== BLACK
);
3288 transports_dn
= kcctpl_transports_dn(service
->samdb
, tmp_ctx
);
3289 if (!transports_dn
) {
3290 DEBUG(1, (__location__
": failed to find our own Inter-Site "
3291 "Transports DN\n"));
3293 talloc_free(tmp_ctx
);
3294 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3297 for (i
= 0; i
< st_edge_list
.count
; i
++) {
3298 struct kcctpl_multi_edge
*edge
;
3299 struct GUID other_site_id
;
3300 struct kcctpl_vertex
*other_site_vertex
;
3301 struct ldb_result
*res
;
3302 struct ldb_message
*transport
, *r_bridgehead
, *l_bridgehead
;
3303 uint8_t schedule
[84];
3304 uint32_t first_available
, j
, interval
;
3306 edge
= &st_edge_list
.data
[i
];
3308 if (edge
->directed
&& !GUID_equal(&edge
->vertex_ids
.data
[1],
3309 &site_vertex
->id
)) {
3313 if (GUID_equal(&edge
->vertex_ids
.data
[0], &site_vertex
->id
)) {
3314 other_site_id
= edge
->vertex_ids
.data
[1];
3316 other_site_id
= edge
->vertex_ids
.data
[0];
3319 other_site_vertex
= kcctpl_find_vertex_by_guid(graph
,
3321 if (!other_site_vertex
) {
3322 DEBUG(1, (__location__
": failed to find vertex %s\n",
3323 GUID_string(tmp_ctx
, &other_site_id
)));
3325 talloc_free(tmp_ctx
);
3326 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3329 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, transports_dn
,
3330 LDB_SCOPE_ONELEVEL
, attrs
,
3331 "(&(objectClass=interSiteTransport)"
3332 "(objectGUID=%s))", GUID_string(tmp_ctx
,
3334 if (ret
!= LDB_SUCCESS
) {
3335 DEBUG(1, (__location__
": failed to find "
3336 "interSiteTransport object %s: %s\n",
3337 GUID_string(tmp_ctx
, &edge
->type
),
3338 ldb_strerror(ret
)));
3340 talloc_free(tmp_ctx
);
3341 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3343 if (res
->count
== 0) {
3344 DEBUG(1, (__location__
": failed to find "
3345 "interSiteTransport object %s\n",
3346 GUID_string(tmp_ctx
, &edge
->type
)));
3348 talloc_free(tmp_ctx
);
3349 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3351 transport
= res
->msgs
[0];
3353 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
3354 other_site_vertex
->id
,
3355 cross_ref
, transport
,
3356 partial_replica_okay
,
3359 if (NT_STATUS_IS_ERR(status
)) {
3360 DEBUG(1, (__location__
": failed to get a bridgehead "
3361 "DC: %s\n", nt_errstr(status
)));
3363 talloc_free(tmp_ctx
);
3367 if (service
->am_rodc
) {
3368 /* TODO: l_bridgehad = nTDSDSA of local DC */
3370 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
3372 cross_ref
, transport
,
3373 partial_replica_okay
,
3376 if (NT_STATUS_IS_ERR(status
)) {
3377 DEBUG(1, (__location__
": failed to get a "
3378 "bridgehead DC: %s\n",
3379 nt_errstr(status
)));
3381 talloc_free(tmp_ctx
);
3386 ZERO_ARRAY(schedule
);
3387 first_available
= 84;
3388 interval
= edge
->repl_info
.interval
/ 15;
3389 for (j
= 0; j
< 84; j
++) {
3390 if (edge
->repl_info
.schedule
[j
] == 1) {
3391 first_available
= j
;
3395 for (j
= first_available
; j
< 84; j
+= interval
) {
3399 status
= kcctpl_create_connection(service
, mem_ctx
, cross_ref
,
3400 r_bridgehead
, transport
,
3401 l_bridgehead
, edge
->repl_info
,
3402 schedule
, detect_failed_dcs
,
3403 partial_replica_okay
,
3405 if (NT_STATUS_IS_ERR(status
)) {
3406 DEBUG(1, (__location__
": failed to create a "
3407 "connection: %s\n", nt_errstr(status
)));
3409 talloc_free(tmp_ctx
);
3414 *_found_failed_dcs
= found_failed_dcs
;
3415 *_connected
= connected
;
3416 talloc_free(tmp_ctx
);
3417 return NT_STATUS_OK
;
3421 * computes an NC replica graph for each NC replica that "should be present" on
3422 * the local DC or "is present" on any DC in the same site as the local DC. for
3423 * each edge directed to an NC replica on such a DC from an NC replica on a DC
3424 * in another site, the KCC creates and nTDSConnection object to imply that edge
3425 * if one does not already exist.
3427 static NTSTATUS
kcctpl_create_intersite_connections(struct kccsrv_service
*service
,
3428 TALLOC_CTX
*mem_ctx
,
3429 struct GUID_list
*_keep_connections
,
3430 bool *_all_connected
)
3432 struct GUID_list keep_connections
;
3434 TALLOC_CTX
*tmp_ctx
;
3435 struct ldb_dn
*partitions_dn
;
3436 struct ldb_result
*res
;
3437 const char * const attrs
[] = { "enabled", "systemFlags", "nCName",
3442 all_connected
= true;
3444 ZERO_STRUCT(keep_connections
);
3446 tmp_ctx
= talloc_new(mem_ctx
);
3447 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
3449 partitions_dn
= samdb_partitions_dn(service
->samdb
, tmp_ctx
);
3450 if (partitions_dn
== NULL
) {
3451 TALLOC_FREE(tmp_ctx
);
3452 return NT_STATUS_NO_MEMORY
;
3455 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, partitions_dn
, LDB_SCOPE_ONELEVEL
,
3456 attrs
, "objectClass=crossRef");
3457 if (ret
!= LDB_SUCCESS
) {
3458 DEBUG(1, (__location__
": failed to find crossRef objects: "
3459 "%s\n", ldb_strerror(ret
)));
3461 talloc_free(tmp_ctx
);
3462 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3465 for (i
= 0; i
< res
->count
; i
++) {
3466 struct ldb_message
*cross_ref
;
3467 unsigned int cr_enabled
;
3469 struct kcctpl_graph
*graph
;
3470 bool found_failed_dc
, connected
;
3473 cross_ref
= res
->msgs
[i
];
3474 cr_enabled
= ldb_msg_find_attr_as_uint(cross_ref
, "enabled", -1);
3475 cr_flags
= ldb_msg_find_attr_as_int64(cross_ref
, "systemFlags", 0);
3476 if ((cr_enabled
== 0) || !(cr_flags
& FLAG_CR_NTDS_NC
)) {
3480 status
= kcctpl_setup_graph(service
->samdb
, tmp_ctx
, &graph
);
3481 if (NT_STATUS_IS_ERR(status
)) {
3482 DEBUG(1, (__location__
": failed to create a graph: "
3483 "%s\n", nt_errstr(status
)));
3485 talloc_free(tmp_ctx
);
3489 status
= kcctpl_create_connections(service
, mem_ctx
, graph
,
3494 if (NT_STATUS_IS_ERR(status
)) {
3495 DEBUG(1, (__location__
": failed to create "
3496 "connections: %s\n", nt_errstr(status
)));
3498 talloc_free(tmp_ctx
);
3503 all_connected
= false;
3505 if (found_failed_dc
) {
3506 status
= kcctpl_create_connections(service
, mem_ctx
,
3513 if (NT_STATUS_IS_ERR(status
)) {
3514 DEBUG(1, (__location__
": failed to "
3515 "create connections: %s\n",
3516 nt_errstr(status
)));
3518 talloc_free(tmp_ctx
);
3525 *_keep_connections
= keep_connections
;
3526 *_all_connected
= all_connected
;
3527 talloc_free(tmp_ctx
);
3528 return NT_STATUS_OK
;
3531 NTSTATUS
kcctpl_test(struct kccsrv_service
*service
)
3534 TALLOC_CTX
*tmp_ctx
= talloc_new(service
);
3535 struct GUID_list keep
;
3538 DEBUG(5, ("Testing kcctpl_create_intersite_connections\n"));
3539 status
= kcctpl_create_intersite_connections(service
, tmp_ctx
, &keep
,
3541 DEBUG(4, ("%s\n", nt_errstr(status
)));
3542 if (NT_STATUS_IS_OK(status
)) {
3545 DEBUG(4, ("all_connected=%d, %d GUIDs returned\n",
3546 all_connected
, keep
.count
));
3548 for (i
= 0; i
< keep
.count
; i
++) {
3549 DEBUG(4, ("GUID %d: %s\n", i
+ 1,
3550 GUID_string(tmp_ctx
, &keep
.data
[i
])));
3554 talloc_free(tmp_ctx
);