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 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(graph
->vertices
.data
, graph
);
510 TYPESAFE_QSORT(guids
.data
, guids
.count
, GUID_compare
);
512 for (i
= 0; i
< guids
.count
; i
++) {
513 graph
->vertices
.data
[i
].id
= guids
.data
[i
];
521 * create a kcctpl_multi_edge instance.
523 static NTSTATUS
kcctpl_create_edge(struct ldb_context
*ldb
, TALLOC_CTX
*mem_ctx
,
525 struct ldb_message
*site_link
,
526 struct kcctpl_multi_edge
**_edge
)
528 struct kcctpl_multi_edge
*edge
;
530 struct ldb_dn
*sites_dn
;
531 struct ldb_result
*res
;
532 const char * const attrs
[] = { "siteList", NULL
};
534 struct ldb_message_element
*el
;
538 tmp_ctx
= talloc_new(mem_ctx
);
539 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
541 edge
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge
);
542 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge
, tmp_ctx
);
544 edge
->id
= samdb_result_guid(site_link
, "objectGUID");
546 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
548 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
550 talloc_free(tmp_ctx
);
551 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
554 ret
= ldb_search(ldb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_SUBTREE
, attrs
,
555 "objectGUID=%s", GUID_string(tmp_ctx
, &edge
->id
));
556 if (ret
!= LDB_SUCCESS
) {
557 DEBUG(1, (__location__
": failed to find siteLink object %s: "
558 "%s\n", GUID_string(tmp_ctx
, &edge
->id
),
561 talloc_free(tmp_ctx
);
562 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
564 if (res
->count
== 0) {
565 DEBUG(1, (__location__
": failed to find siteLink object %s\n",
566 GUID_string(tmp_ctx
, &edge
->id
)));
568 talloc_free(tmp_ctx
);
569 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
572 el
= ldb_msg_find_element(res
->msgs
[0], "siteList");
574 DEBUG(1, (__location__
": failed to find siteList attribute of "
576 ldb_dn_get_linearized(res
->msgs
[0]->dn
)));
578 talloc_free(tmp_ctx
);
579 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
582 edge
->vertex_ids
.data
= talloc_array(edge
, struct GUID
, el
->num_values
);
583 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge
->vertex_ids
.data
, tmp_ctx
);
584 edge
->vertex_ids
.count
= el
->num_values
;
586 for (i
= 0; i
< el
->num_values
; i
++) {
591 dn
= ldb_dn_from_ldb_val(tmp_ctx
, ldb
, &val
);
593 DEBUG(1, (__location__
": failed to read a DN from "
594 "siteList attribute of %s\n",
595 ldb_dn_get_linearized(res
->msgs
[0]->dn
)));
597 talloc_free(tmp_ctx
);
598 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
600 ret
= dsdb_find_guid_by_dn(ldb
, dn
, &guid
);
601 if (ret
!= LDB_SUCCESS
) {
602 DEBUG(1, (__location__
": failed to find objectGUID "
603 "for object %s: %s\n",
604 ldb_dn_get_linearized(dn
),
607 talloc_free(tmp_ctx
);
608 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
611 edge
->vertex_ids
.data
[i
] = guid
;
614 edge
->repl_info
.cost
= ldb_msg_find_attr_as_int64(site_link
, "cost", 0);
615 edge
->repl_info
.options
= ldb_msg_find_attr_as_uint(site_link
, "options", 0);
616 edge
->repl_info
.interval
= ldb_msg_find_attr_as_int64(site_link
,
618 /* TODO: edge->repl_info.schedule = site_link!schedule */
620 edge
->directed
= false;
622 *_edge
= talloc_steal(mem_ctx
, edge
);
623 talloc_free(tmp_ctx
);
628 * create a kcctpl_multi_edge_set instance containing edges for all siteLink
631 static NTSTATUS
kcctpl_create_auto_edge_set(struct kcctpl_graph
*graph
,
633 struct ldb_result
*res_site_link
,
634 struct kcctpl_multi_edge_set
**_set
)
636 struct kcctpl_multi_edge_set
*set
;
640 tmp_ctx
= talloc_new(graph
);
641 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
643 set
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge_set
);
644 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set
, tmp_ctx
);
646 for (i
= 0; i
< res_site_link
->count
; i
++) {
647 struct GUID site_link_guid
;
648 struct kcctpl_multi_edge
*edge
;
650 site_link_guid
= samdb_result_guid(res_site_link
->msgs
[i
],
652 edge
= kcctpl_find_edge_by_guid(graph
, site_link_guid
);
654 DEBUG(1, (__location__
": failed to find a graph edge "
656 GUID_string(tmp_ctx
, &site_link_guid
)));
658 talloc_free(tmp_ctx
);
659 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
662 if (GUID_equal(&edge
->type
, &type
)) {
663 struct GUID
*new_data
;
665 new_data
= talloc_realloc(set
, set
->edge_ids
.data
,
667 set
->edge_ids
.count
+ 1);
668 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
669 new_data
[set
->edge_ids
.count
] = site_link_guid
;
670 set
->edge_ids
.data
= new_data
;
671 set
->edge_ids
.count
++;
675 *_set
= talloc_steal(graph
, set
);
680 * create a kcctpl_multi_edge_set instance.
682 static NTSTATUS
kcctpl_create_edge_set(struct ldb_context
*ldb
,
683 struct kcctpl_graph
*graph
,
685 struct ldb_message
*bridge
,
686 struct kcctpl_multi_edge_set
**_set
)
688 struct kcctpl_multi_edge_set
*set
;
690 struct ldb_message_element
*el
;
693 tmp_ctx
= talloc_new(ldb
);
694 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
696 set
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge_set
);
697 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set
, tmp_ctx
);
699 set
->id
= samdb_result_guid(bridge
, "objectGUID");
701 el
= ldb_msg_find_element(bridge
, "siteLinkList");
703 DEBUG(1, (__location__
": failed to find siteLinkList "
704 "attribute of object %s\n",
705 ldb_dn_get_linearized(bridge
->dn
)));
707 talloc_free(tmp_ctx
);
708 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
710 for (i
= 0; i
< el
->num_values
; i
++) {
713 struct GUID site_link_guid
;
715 struct kcctpl_multi_edge
*edge
;
718 dn
= ldb_dn_from_ldb_val(tmp_ctx
, ldb
, &val
);
720 DEBUG(1, (__location__
": failed to read a DN from "
721 "siteList attribute of %s\n",
722 ldb_dn_get_linearized(bridge
->dn
)));
724 talloc_free(tmp_ctx
);
725 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
728 ret
= dsdb_find_guid_by_dn(ldb
, dn
, &site_link_guid
);
729 if (ret
!= LDB_SUCCESS
) {
730 DEBUG(1, (__location__
": failed to find objectGUID "
731 "for object %s: %s\n",
732 ldb_dn_get_linearized(dn
),
735 talloc_free(tmp_ctx
);
736 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
739 edge
= kcctpl_find_edge_by_guid(graph
, site_link_guid
);
741 DEBUG(1, (__location__
": failed to find a graph edge "
743 GUID_string(tmp_ctx
, &site_link_guid
)));
745 talloc_free(tmp_ctx
);
746 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
749 if (GUID_equal(&edge
->type
, &type
)) {
750 struct GUID
*new_data
;
752 new_data
= talloc_realloc(set
, set
->edge_ids
.data
,
754 set
->edge_ids
.count
+ 1);
755 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
756 new_data
[set
->edge_ids
.count
] = site_link_guid
;
757 set
->edge_ids
.data
= new_data
;
758 set
->edge_ids
.count
++;
762 *_set
= talloc_steal(graph
, set
);
763 talloc_free(tmp_ctx
);
768 * set up a kcctpl_graph, populated with a kcctpl_vertex for each site object, a
769 * kcctpl_multi_edge for each siteLink object, and a kcctpl_multi_edge_set for
770 * each siteLinkBridge object (or implied siteLinkBridge).
772 static NTSTATUS
kcctpl_setup_graph(struct ldb_context
*ldb
, TALLOC_CTX
*mem_ctx
,
773 struct kcctpl_graph
**_graph
)
775 struct kcctpl_graph
*graph
;
776 struct ldb_dn
*sites_dn
, *transports_dn
;
778 struct ldb_result
*res
;
779 const char * const transport_attrs
[] = { "objectGUID", NULL
};
780 const char * const site_attrs
[] = { "objectGUID", "options", NULL
};
781 const char * const attrs
[] = { "objectGUID", "cost", "options",
782 "replInterval", "schedule", NULL
};
783 const char * const site_link_bridge_attrs
[] = { "objectGUID",
787 struct GUID_list vertex_ids
;
790 struct ldb_message
*site
;
793 tmp_ctx
= talloc_new(mem_ctx
);
794 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
796 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
798 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
800 talloc_free(tmp_ctx
);
801 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
804 ret
= ldb_search(ldb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_SUBTREE
,
805 site_attrs
, "objectClass=site");
806 if (ret
!= LDB_SUCCESS
) {
807 DEBUG(1, (__location__
": failed to find site objects under "
808 "%s: %s\n", ldb_dn_get_linearized(sites_dn
),
811 talloc_free(tmp_ctx
);
812 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
815 ZERO_STRUCT(vertex_ids
);
816 for (i
= 0; i
< res
->count
; i
++) {
817 struct GUID guid
, *new_data
;
819 guid
= samdb_result_guid(res
->msgs
[i
], "objectGUID");
821 new_data
= talloc_realloc(tmp_ctx
, vertex_ids
.data
, struct GUID
,
822 vertex_ids
.count
+ 1);
823 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
824 new_data
[vertex_ids
.count
] = guid
;
825 vertex_ids
.data
= new_data
;
829 status
= kcctpl_create_graph(tmp_ctx
, vertex_ids
, &graph
);
830 if (NT_STATUS_IS_ERR(status
)) {
831 DEBUG(1, (__location__
": failed to create graph: %s\n",
834 talloc_free(tmp_ctx
);
838 site
= kcctpl_local_site(ldb
, tmp_ctx
);
840 DEBUG(1, (__location__
": failed to find our own local DC's "
843 talloc_free(tmp_ctx
);
844 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
846 site_opts
= ldb_msg_find_attr_as_uint(site
, "options", 0);
848 transports_dn
= kcctpl_transports_dn(ldb
, tmp_ctx
);
849 if (!transports_dn
) {
850 DEBUG(1, (__location__
": failed to find our own Inter-Site "
853 talloc_free(tmp_ctx
);
854 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
857 ret
= ldb_search(ldb
, tmp_ctx
, &res
, transports_dn
, LDB_SCOPE_ONELEVEL
,
858 transport_attrs
, "objectClass=interSiteTransport");
859 if (ret
!= LDB_SUCCESS
) {
860 DEBUG(1, (__location__
": failed to find interSiteTransport "
861 "objects under %s: %s\n",
862 ldb_dn_get_linearized(transports_dn
),
865 talloc_free(tmp_ctx
);
866 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
869 for (i
= 0; i
< res
->count
; i
++) {
870 struct ldb_message
*transport
;
871 struct ldb_result
*res_site_link
;
872 struct GUID transport_guid
;
874 uint32_t transport_opts
;
876 transport
= res
->msgs
[i
];
878 ret
= ldb_search(ldb
, tmp_ctx
, &res_site_link
, transport
->dn
,
879 LDB_SCOPE_SUBTREE
, attrs
,
880 "objectClass=siteLink");
881 if (ret
!= LDB_SUCCESS
) {
882 DEBUG(1, (__location__
": failed to find siteLink "
883 "objects under %s: %s\n",
884 ldb_dn_get_linearized(transport
->dn
),
887 talloc_free(tmp_ctx
);
888 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
891 transport_guid
= samdb_result_guid(transport
, "objectGUID");
892 for (j
= 0; j
< res_site_link
->count
; j
++) {
893 struct kcctpl_multi_edge
*edge
, *new_data
;
895 status
= kcctpl_create_edge(ldb
, graph
, transport_guid
,
896 res_site_link
->msgs
[j
],
898 if (NT_STATUS_IS_ERR(status
)) {
899 DEBUG(1, (__location__
": failed to create "
900 "edge: %s\n", nt_errstr(status
)));
901 talloc_free(tmp_ctx
);
905 new_data
= talloc_realloc(graph
, graph
->edges
.data
,
906 struct kcctpl_multi_edge
,
907 graph
->edges
.count
+ 1);
908 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
909 new_data
[graph
->edges
.count
] = *edge
;
910 graph
->edges
.data
= new_data
;
911 graph
->edges
.count
++;
914 transport_opts
= ldb_msg_find_attr_as_uint(transport
, "options", 0);
915 if (!(transport_opts
& NTDSTRANSPORT_OPT_BRIDGES_REQUIRED
) &&
916 !(site_opts
& NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED
)) {
917 struct kcctpl_multi_edge_set
*edge_set
, *new_data
;
919 status
= kcctpl_create_auto_edge_set(graph
,
923 if (NT_STATUS_IS_ERR(status
)) {
924 DEBUG(1, (__location__
": failed to create "
925 "edge set: %s\n", nt_errstr(status
)));
926 talloc_free(tmp_ctx
);
930 new_data
= talloc_realloc(graph
, graph
->edge_sets
.data
,
931 struct kcctpl_multi_edge_set
,
932 graph
->edge_sets
.count
+ 1);
933 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
934 new_data
[graph
->edge_sets
.count
] = *edge_set
;
935 graph
->edge_sets
.data
= new_data
;
936 graph
->edge_sets
.count
++;
938 ret
= ldb_search(ldb
, tmp_ctx
, &res_site_link
,
939 transport
->dn
, LDB_SCOPE_SUBTREE
,
940 site_link_bridge_attrs
,
941 "objectClass=siteLinkBridge");
942 if (ret
!= LDB_SUCCESS
) {
943 DEBUG(1, (__location__
": failed to find "
944 "siteLinkBridge objects under %s: "
946 ldb_dn_get_linearized(transport
->dn
),
949 talloc_free(tmp_ctx
);
950 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
953 for (j
= 0; j
< res_site_link
->count
; j
++) {
954 struct ldb_message
*bridge
;
955 struct kcctpl_multi_edge_set
*edge_set
,
958 bridge
= res_site_link
->msgs
[j
];
959 status
= kcctpl_create_edge_set(ldb
, graph
,
963 if (NT_STATUS_IS_ERR(status
)) {
964 DEBUG(1, (__location__
": failed to "
965 "create edge set: %s\n",
968 talloc_free(tmp_ctx
);
972 new_data
= talloc_realloc(graph
,
973 graph
->edge_sets
.data
,
974 struct kcctpl_multi_edge_set
,
975 graph
->edge_sets
.count
+ 1);
976 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
,
978 new_data
[graph
->edge_sets
.count
] = *edge_set
;
979 graph
->edge_sets
.data
= new_data
;
980 graph
->edge_sets
.count
++;
985 *_graph
= talloc_steal(mem_ctx
, graph
);
986 talloc_free(tmp_ctx
);
991 * determine whether a given DC is known to be in a failed state.
993 static NTSTATUS
kcctpl_bridgehead_dc_failed(struct ldb_context
*ldb
,
995 bool detect_failed_dcs
,
999 struct ldb_dn
*settings_dn
;
1000 struct ldb_result
*res
;
1001 const char * const attrs
[] = { "options", NULL
};
1003 struct ldb_message
*settings
;
1004 uint32_t settings_opts
;
1007 tmp_ctx
= talloc_new(ldb
);
1008 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1010 settings_dn
= samdb_ntds_settings_dn(ldb
);
1012 DEBUG(1, (__location__
": failed to find our own NTDS Settings "
1014 talloc_free(tmp_ctx
);
1015 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1018 ret
= ldb_search(ldb
, tmp_ctx
, &res
, settings_dn
, LDB_SCOPE_BASE
, attrs
,
1019 "objectClass=nTDSSiteSettings");
1020 if (ret
!= LDB_SUCCESS
) {
1021 DEBUG(1, (__location__
": failed to find site settings object "
1022 "%s: %s\n", ldb_dn_get_linearized(settings_dn
),
1023 ldb_strerror(ret
)));
1024 talloc_free(tmp_ctx
);
1025 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1027 if (res
->count
== 0) {
1028 DEBUG(1, ("failed to find site settings object %s\n",
1029 ldb_dn_get_linearized(settings_dn
)));
1030 talloc_free(tmp_ctx
);
1031 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1034 settings
= res
->msgs
[0];
1036 settings_opts
= ldb_msg_find_attr_as_uint(settings
, "options", 0);
1037 if (settings_opts
& NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED
) {
1039 } else if (true) { /* TODO: how to get kCCFailedLinks and
1040 kCCFailedConnections? */
1043 failed
= detect_failed_dcs
;
1047 talloc_free(tmp_ctx
);
1048 return NT_STATUS_OK
;
1052 * get all bridgehead DCs satisfying the given criteria.
1054 static NTSTATUS
kcctpl_get_all_bridgehead_dcs(struct kccsrv_service
*service
,
1055 TALLOC_CTX
*mem_ctx
,
1056 struct GUID site_guid
,
1057 struct ldb_message
*cross_ref
,
1058 struct ldb_message
*transport
,
1059 bool partial_replica_okay
,
1060 bool detect_failed_dcs
,
1061 struct message_list
*_bridgeheads
)
1063 struct message_list bridgeheads
, all_dcs_in_site
;
1064 TALLOC_CTX
*tmp_ctx
;
1065 struct ldb_result
*res
;
1066 struct ldb_dn
*sites_dn
, *schemas_dn
;
1067 const char * const attrs
[] = { "options", NULL
};
1069 struct ldb_message
*site
, *schema
;
1070 const char * const dc_attrs
[] = { "objectGUID", "options", NULL
};
1071 struct ldb_message_element
*el
;
1073 const char *transport_name
, *transport_address_attr
;
1076 ZERO_STRUCT(bridgeheads
);
1078 tmp_ctx
= talloc_new(mem_ctx
);
1079 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1081 sites_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
1083 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
1085 talloc_free(tmp_ctx
);
1086 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1089 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_ONELEVEL
,
1090 attrs
, "(&(objectClass=site)(objectGUID=%s))",
1091 GUID_string(tmp_ctx
, &site_guid
));
1092 if (ret
!= LDB_SUCCESS
) {
1093 DEBUG(1, (__location__
": failed to find site object %s: %s\n",
1094 GUID_string(tmp_ctx
, &site_guid
),
1095 ldb_strerror(ret
)));
1097 talloc_free(tmp_ctx
);
1098 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1100 if (res
->count
== 0) {
1101 DEBUG(1, (__location__
": failed to find site object %s\n",
1102 GUID_string(tmp_ctx
, &site_guid
)));
1104 talloc_free(tmp_ctx
);
1105 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1107 site
= res
->msgs
[0];
1109 schemas_dn
= ldb_get_schema_basedn(service
->samdb
);
1111 DEBUG(1, (__location__
": failed to find our own Schemas DN\n"));
1113 talloc_free(tmp_ctx
);
1114 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1117 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, schemas_dn
, LDB_SCOPE_SUBTREE
,
1119 "(&(lDAPDisplayName=nTDSDSA)(objectClass=classSchema))");
1120 if (ret
!= LDB_SUCCESS
) {
1121 DEBUG(1, (__location__
": failed to find classSchema object :"
1122 "%s\n", ldb_strerror(ret
)));
1124 talloc_free(tmp_ctx
);
1125 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1127 if (res
->count
== 0) {
1128 DEBUG(1, (__location__
": failed to find classSchema "
1131 talloc_free(tmp_ctx
);
1132 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1134 schema
= res
->msgs
[0];
1136 ZERO_STRUCT(all_dcs_in_site
);
1138 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, site
->dn
, LDB_SCOPE_SUBTREE
,
1139 dc_attrs
, "objectCategory=%s",
1140 ldb_dn_get_linearized(schema
->dn
));
1141 if (ret
!= LDB_SUCCESS
) {
1142 DEBUG(1, (__location__
": failed to find DCs objects :%s\n",
1143 ldb_strerror(ret
)));
1145 talloc_free(tmp_ctx
);
1146 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1149 el
= ldb_msg_find_element(transport
, "bridgeheadServerListBL");
1151 transport_name
= ldb_msg_find_attr_as_string(transport
, "name", NULL
);
1152 if (!transport_name
) {
1153 DEBUG(1, (__location__
": failed to find name attribute of "
1154 "object %s\n", ldb_dn_get_linearized(transport
->dn
)));
1156 talloc_free(tmp_ctx
);
1157 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1160 transport_address_attr
= ldb_msg_find_attr_as_string(transport
,
1161 "transportAddressAttribute",
1163 if (!transport_address_attr
) {
1164 DEBUG(1, (__location__
": failed to find "
1165 "transportAddressAttribute attribute of object %s\n",
1166 ldb_dn_get_linearized(transport
->dn
)));
1168 talloc_free(tmp_ctx
);
1169 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1172 site_opts
= ldb_msg_find_attr_as_uint(site
, "options", 0);
1174 for (i
= 0; i
< res
->count
; i
++) {
1175 struct ldb_message
*dc
, *new_data
;
1176 struct ldb_dn
*parent_dn
;
1177 uint64_t behavior_version
;
1178 const char *dc_transport_address
;
1179 struct ldb_result
*parent_res
;
1180 const char *parent_attrs
[] = { transport_address_attr
, NULL
};
1182 struct GUID dc_guid
;
1187 parent_dn
= ldb_dn_get_parent(tmp_ctx
, dc
->dn
);
1189 DEBUG(1, (__location__
": failed to get parent DN of "
1190 "%s\n", ldb_dn_get_linearized(dc
->dn
)));
1192 talloc_free(tmp_ctx
);
1193 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1196 if (el
&& (el
->num_values
>= 1)) {
1202 for (j
= 0; j
< el
->num_values
; j
++) {
1206 val
= el
->values
[j
];
1208 dn
= ldb_dn_from_ldb_val(tmp_ctx
, service
->samdb
, &val
);
1210 DEBUG(1, (__location__
": failed to read a DN "
1211 "from bridgeheadServerListBL "
1212 "attribute of %s\n",
1213 ldb_dn_get_linearized(transport
->dn
)));
1215 talloc_free(tmp_ctx
);
1216 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1219 if (ldb_dn_compare(dn
, parent_dn
) == 0) {
1230 /* TODO: if dc is in the same site as the local DC */
1232 /* TODO: if a replica of cr!nCName is not in the set of
1233 * NC replicas that "should be present" on 'dc' */
1234 /* TODO: a partial replica of the NC "should be
1236 if (true || (true && !partial_replica_okay
)) {
1240 /* TODO: if an NC replica of cr!nCName is not in the set
1241 * of NC replicas that "are present" on 'dc' */
1242 /* TODO: a partial replica of the NC "is present" */
1243 if (true || (true && !partial_replica_okay
)) {
1248 behavior_version
= ldb_msg_find_attr_as_int64(dc
,
1249 "msDS-Behavior-Version", 0);
1250 /* TODO: cr!nCName corresponds to default NC */
1251 if (service
->am_rodc
&& true && behavior_version
< DS_BEHAVIOR_WIN2008
) {
1255 ret
= ldb_search(service
->samdb
, tmp_ctx
, &parent_res
, parent_dn
,
1256 LDB_SCOPE_BASE
, parent_attrs
, NULL
);
1258 dc_transport_address
= ldb_msg_find_attr_as_string(parent_res
->msgs
[0],
1259 transport_address_attr
,
1262 if (strncmp(transport_name
, "IP", 2) != 0 &&
1263 dc_transport_address
== NULL
) {
1267 dc_guid
= samdb_result_guid(dc
, "objectGUID");
1269 status
= kcctpl_bridgehead_dc_failed(service
->samdb
, dc_guid
,
1272 if (NT_STATUS_IS_ERR(status
)) {
1273 DEBUG(1, (__location__
": failed to check if "
1274 "bridgehead DC has failed: %s\n",
1275 nt_errstr(status
)));
1277 talloc_free(tmp_ctx
);
1285 new_data
= talloc_realloc(tmp_ctx
, bridgeheads
.data
,
1287 bridgeheads
.count
+ 1);
1288 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1289 new_data
[bridgeheads
.count
+ 1] = *dc
;
1290 bridgeheads
.data
= new_data
;
1291 bridgeheads
.count
++;
1294 if (site_opts
& NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED
) {
1295 qsort(bridgeheads
.data
, bridgeheads
.count
,
1296 sizeof(struct ldb_message
), kcctpl_sort_bridgeheads
);
1298 kcctpl_shuffle_bridgeheads(bridgeheads
);
1301 talloc_steal(mem_ctx
, bridgeheads
.data
);
1302 *_bridgeheads
= bridgeheads
;
1303 talloc_free(tmp_ctx
);
1304 return NT_STATUS_OK
;
1308 * get a bridgehead DC.
1310 static NTSTATUS
kcctpl_get_bridgehead_dc(struct kccsrv_service
*service
,
1311 TALLOC_CTX
*mem_ctx
,
1312 struct GUID site_guid
,
1313 struct ldb_message
*cross_ref
,
1314 struct ldb_message
*transport
,
1315 bool partial_replica_okay
,
1316 bool detect_failed_dcs
,
1317 struct ldb_message
**_dsa
)
1319 struct message_list dsa_list
;
1322 status
= kcctpl_get_all_bridgehead_dcs(service
, mem_ctx
,
1323 site_guid
, cross_ref
, transport
,
1324 partial_replica_okay
,
1325 detect_failed_dcs
, &dsa_list
);
1326 if (NT_STATUS_IS_ERR(status
)) {
1327 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
1328 "%s\n", nt_errstr(status
)));
1332 *_dsa
= (dsa_list
.count
== 0) ? NULL
: &dsa_list
.data
[0];
1334 return NT_STATUS_OK
;
1338 * color each vertex to indicate which kinds of NC replicas it contains.
1340 static NTSTATUS
kcctpl_color_vertices(struct kccsrv_service
*service
,
1341 struct kcctpl_graph
*graph
,
1342 struct ldb_message
*cross_ref
,
1343 bool detect_failed_dcs
,
1344 bool *_found_failed_dcs
)
1346 TALLOC_CTX
*tmp_ctx
;
1347 struct ldb_dn
*sites_dn
;
1348 bool found_failed_dcs
, partial_replica_okay
;
1350 struct ldb_message
*site
;
1351 struct ldb_result
*res
;
1353 struct GUID site_guid
;
1354 struct kcctpl_vertex
*site_vertex
;
1356 found_failed_dcs
= false;
1358 tmp_ctx
= talloc_new(service
);
1359 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1361 sites_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
1363 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
1365 talloc_free(tmp_ctx
);
1366 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1369 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1370 struct kcctpl_vertex
*vertex
;
1371 struct ldb_dn
*nc_name
;
1372 /* TODO: set 'attrs' with its corresponding values */
1373 const char * const attrs
[] = { NULL
};
1375 vertex
= &graph
->vertices
.data
[i
];
1377 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, sites_dn
,
1378 LDB_SCOPE_SUBTREE
, attrs
, "objectGUID=%s",
1379 GUID_string(tmp_ctx
, &vertex
->id
));
1380 if (ret
!= LDB_SUCCESS
) {
1381 DEBUG(1, (__location__
": failed to find site object "
1382 "%s: %s\n", GUID_string(tmp_ctx
, &vertex
->id
),
1383 ldb_strerror(ret
)));
1385 talloc_free(tmp_ctx
);
1386 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1388 if (res
->count
== 0) {
1389 DEBUG(1, (__location__
": failed to find site object "
1390 "%s\n", GUID_string(tmp_ctx
, &vertex
->id
)));
1392 talloc_free(tmp_ctx
);
1393 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1395 site
= res
->msgs
[0];
1397 nc_name
= samdb_result_dn(service
->samdb
, tmp_ctx
, cross_ref
,
1400 DEBUG(1, (__location__
": failed to find nCName "
1401 "attribute of object %s\n",
1402 ldb_dn_get_linearized(cross_ref
->dn
)));
1404 talloc_free(tmp_ctx
);
1405 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1408 if (true) { /* TODO: site contains 1+ DCs with full replicas of
1410 vertex
->color
= RED
;
1411 } else if (true) { /* TODO: site contains 1+ partial replicas of
1413 vertex
->color
= BLACK
;
1415 vertex
->color
= WHITE
;
1419 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
1421 DEBUG(1, (__location__
": failed to find our own local DC's "
1424 talloc_free(tmp_ctx
);
1425 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1427 site_guid
= samdb_result_guid(site
, "objectGUID");
1429 site_vertex
= kcctpl_find_vertex_by_guid(graph
, site_guid
);
1431 DEBUG(1, (__location__
": failed to find a vertex edge with "
1432 "GUID=%s\n", GUID_string(tmp_ctx
, &site_guid
)));
1434 talloc_free(tmp_ctx
);
1435 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1438 partial_replica_okay
= (site_vertex
->color
== BLACK
);
1440 cr_flags
= ldb_msg_find_attr_as_int64(cross_ref
, "systemFlags", 0);
1442 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1443 struct kcctpl_vertex
*vertex
;
1444 struct ldb_dn
*transports_dn
;
1445 const char * const attrs
[] = { "objectGUID", "name",
1446 "transportAddressAttribute",
1450 vertex
= &graph
->vertices
.data
[i
];
1452 transports_dn
= kcctpl_transports_dn(service
->samdb
, tmp_ctx
);
1453 if (!transports_dn
) {
1454 DEBUG(1, (__location__
": failed to find our own "
1455 "Inter-Site Transports DN\n"));
1457 talloc_free(tmp_ctx
);
1458 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1461 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, transports_dn
,
1462 LDB_SCOPE_ONELEVEL
, attrs
,
1463 "objectClass=interSiteTransport");
1464 if (ret
!= LDB_SUCCESS
) {
1465 DEBUG(1, (__location__
": failed to find "
1466 "interSiteTransport objects under %s: %s\n",
1467 ldb_dn_get_linearized(transports_dn
),
1468 ldb_strerror(ret
)));
1470 talloc_free(tmp_ctx
);
1471 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1474 for (j
= 0; j
< res
->count
; j
++) {
1475 struct ldb_message
*transport
, *bridgehead
;
1476 const char *transport_name
;
1477 struct GUID transport_guid
, *new_data
;
1480 transport
= res
->msgs
[j
];
1482 transport_name
= ldb_msg_find_attr_as_string(transport
,
1484 if (!transport_name
) {
1485 DEBUG(1, (__location__
": failed to find name "
1486 "attribute of object %s\n",
1487 ldb_dn_get_linearized(transport
->dn
)));
1489 talloc_free(tmp_ctx
);
1490 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1493 transport_guid
= samdb_result_guid(transport
,
1496 if (site_vertex
->color
== RED
&&
1497 strncmp(transport_name
, "IP", 2) != 0 &&
1498 (cr_flags
& FLAG_CR_NTDS_DOMAIN
)) {
1502 if (!kcctpl_find_edge_by_vertex_guid(graph
,
1507 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
1509 cross_ref
, transport
,
1510 partial_replica_okay
,
1513 if (NT_STATUS_IS_ERR(status
)) {
1514 DEBUG(1, (__location__
": failed to get a "
1515 "bridgehead DC: %s\n",
1516 nt_errstr(status
)));
1518 talloc_free(tmp_ctx
);
1522 found_failed_dcs
= true;
1526 new_data
= talloc_realloc(vertex
,
1527 vertex
->accept_red_red
.data
,
1529 vertex
->accept_red_red
.count
+ 1);
1530 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1531 new_data
[vertex
->accept_red_red
.count
+ 1] = transport_guid
;
1532 vertex
->accept_red_red
.data
= new_data
;
1533 vertex
->accept_red_red
.count
++;
1535 new_data
= talloc_realloc(vertex
,
1536 vertex
->accept_black
.data
,
1538 vertex
->accept_black
.count
+ 1);
1539 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1540 new_data
[vertex
->accept_black
.count
+ 1] = transport_guid
;
1541 vertex
->accept_black
.data
= new_data
;
1542 vertex
->accept_black
.count
++;
1546 *_found_failed_dcs
= found_failed_dcs
;
1547 talloc_free(tmp_ctx
);
1548 return NT_STATUS_OK
;
1552 * setup the fields of the vertices that are relevant to Phase I (Dijkstra's
1553 * Algorithm). for each vertex, set up its cost, root vertex and component. this
1554 * defines the shortest-path forest structures.
1556 static void kcctpl_setup_vertices(struct kcctpl_graph
*graph
)
1560 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1561 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
1563 if (vertex
->color
== WHITE
) {
1564 vertex
->repl_info
.cost
= UINT32_MAX
;
1565 vertex
->root_id
= vertex
->component_id
= GUID_zero();
1567 vertex
->repl_info
.cost
= 0;
1568 vertex
->root_id
= vertex
->component_id
= vertex
->id
;
1571 vertex
->repl_info
.interval
= 0;
1572 vertex
->repl_info
.options
= 0xFFFFFFFF;
1573 ZERO_STRUCT(vertex
->repl_info
.schedule
);
1574 vertex
->demoted
= false;
1579 * demote one vertex if necessary.
1581 static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex
*vertex
,
1584 if (vertex
->color
== WHITE
) {
1588 if (!kcctpl_guid_list_contains(vertex
->accept_black
, type
) &&
1589 !kcctpl_guid_list_contains(vertex
->accept_red_red
, type
)) {
1590 vertex
->repl_info
.cost
= UINT32_MAX
;
1591 vertex
->root_id
= GUID_zero();
1592 vertex
->demoted
= true;
1597 * clear the demoted state of a vertex.
1599 static void kcctpl_undemote_one_vertex(struct kcctpl_vertex
*vertex
)
1601 if (vertex
->color
== WHITE
) {
1605 vertex
->repl_info
.cost
= 0;
1606 vertex
->root_id
= vertex
->id
;
1607 vertex
->demoted
= false;
1611 * returns the id of the component containing 'vertex' by traversing the up-tree
1612 * implied by the component pointers.
1614 static struct GUID
kcctpl_get_component_id(struct kcctpl_graph
*graph
,
1615 struct kcctpl_vertex
*vertex
)
1617 struct kcctpl_vertex
*u
;
1621 while (!GUID_equal(&u
->component_id
, &u
->id
)) {
1622 u
= kcctpl_find_vertex_by_guid(graph
, u
->component_id
);
1628 while (!GUID_equal(&u
->component_id
, &u
->id
)) {
1629 struct kcctpl_vertex
*w
;
1631 w
= kcctpl_find_vertex_by_guid(graph
, u
->component_id
);
1632 u
->component_id
= root
;
1640 * copy all spanning tree edges from 'output_edges' that contain the vertex for
1641 * DCs in the local DC's site.
1643 static NTSTATUS
kcctpl_copy_output_edges(struct kccsrv_service
*service
,
1644 TALLOC_CTX
*mem_ctx
,
1645 struct kcctpl_graph
*graph
,
1646 struct kcctpl_multi_edge_list output_edges
,
1647 struct kcctpl_multi_edge_list
*_copy
)
1649 struct kcctpl_multi_edge_list copy
;
1650 TALLOC_CTX
*tmp_ctx
;
1651 struct ldb_message
*site
;
1652 struct GUID site_guid
;
1657 tmp_ctx
= talloc_new(service
);
1658 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1660 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
1662 DEBUG(1, (__location__
": failed to find our own local DC's "
1665 talloc_free(tmp_ctx
);
1666 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1668 site_guid
= samdb_result_guid(site
, "objectGUID");
1670 for (i
= 0; i
< output_edges
.count
; i
++) {
1671 struct kcctpl_multi_edge
*edge
;
1672 struct kcctpl_vertex
*vertex1
, *vertex2
;
1674 edge
= &output_edges
.data
[i
];
1676 vertex1
= kcctpl_find_vertex_by_guid(graph
,
1677 edge
->vertex_ids
.data
[0]);
1679 DEBUG(1, (__location__
": failed to find vertex %s\n",
1680 GUID_string(tmp_ctx
,
1681 &edge
->vertex_ids
.data
[0])));
1682 talloc_free(tmp_ctx
);
1683 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1686 vertex2
= kcctpl_find_vertex_by_guid(graph
,
1687 edge
->vertex_ids
.data
[1]);
1689 DEBUG(1, (__location__
": failed to find vertex %s\n",
1690 GUID_string(tmp_ctx
,
1691 &edge
->vertex_ids
.data
[1])));
1692 talloc_free(tmp_ctx
);
1693 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1696 if (GUID_equal(&vertex1
->id
, &site_guid
) ||
1697 GUID_equal(&vertex2
->id
, &site_guid
)) {
1698 struct kcctpl_multi_edge
*new_data
;
1700 if ((vertex1
->color
== BLACK
||
1701 vertex2
->color
== BLACK
) &&
1702 vertex1
->dist_to_red
!= UINT32_MAX
) {
1704 edge
->directed
= true;
1706 if (vertex2
->dist_to_red
<
1707 vertex1
->dist_to_red
) {
1710 tmp
= edge
->vertex_ids
.data
[0];
1711 edge
->vertex_ids
.data
[0] = edge
->vertex_ids
.data
[1];
1712 edge
->vertex_ids
.data
[1] = tmp
;
1716 new_data
= talloc_realloc(tmp_ctx
, copy
.data
,
1717 struct kcctpl_multi_edge
,
1719 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1720 new_data
[copy
.count
+ 1] = *edge
;
1721 copy
.data
= new_data
;
1726 talloc_steal(mem_ctx
, copy
.data
);
1727 talloc_free(tmp_ctx
);
1729 return NT_STATUS_OK
;
1733 * build the initial sequence for use with Dijkstra's algorithm. it will contain
1734 * the red and black vertices as root vertices, unless these vertices accept no
1735 * edges of the current 'type', or unless black vertices are not being
1738 static NTSTATUS
kcctpl_setup_dijkstra(TALLOC_CTX
*mem_ctx
,
1739 struct kcctpl_graph
*graph
,
1740 struct GUID type
, bool include_black
,
1741 struct kcctpl_vertex_list
*_vertices
)
1743 struct kcctpl_vertex_list vertices
;
1746 kcctpl_setup_vertices(graph
);
1748 ZERO_STRUCT(vertices
);
1750 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1751 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
1753 if (vertex
->color
== WHITE
) {
1757 if ((vertex
->color
== BLACK
&& !include_black
) ||
1758 !kcctpl_guid_list_contains(vertex
->accept_black
, type
) ||
1759 !kcctpl_guid_list_contains(vertex
->accept_red_red
, type
)) {
1760 vertex
->repl_info
.cost
= UINT32_MAX
;
1761 vertex
->root_id
= GUID_zero();
1762 vertex
->demoted
= true;
1764 struct kcctpl_vertex
*new_data
;
1766 new_data
= talloc_realloc(mem_ctx
, vertices
.data
,
1767 struct kcctpl_vertex
,
1768 vertices
.count
+ 1);
1769 NT_STATUS_HAVE_NO_MEMORY(new_data
);
1770 new_data
[vertices
.count
] = *vertex
;
1771 vertices
.data
= new_data
;
1776 *_vertices
= vertices
;
1777 return NT_STATUS_OK
;
1781 * merge schedules, replication intervals, options and costs.
1783 static bool kcctpl_combine_repl_info(struct kcctpl_graph
*graph
,
1784 struct kcctpl_repl_info
*ria
,
1785 struct kcctpl_repl_info
*rib
,
1786 struct kcctpl_repl_info
*ric
)
1788 uint8_t schedule
[84];
1793 is_available
= false;
1794 for (i
= 0; i
< 84; i
++) {
1795 schedule
[i
] = ria
->schedule
[i
] & rib
->schedule
[i
];
1797 if (schedule
[i
] == 1) {
1798 is_available
= true;
1801 if (!is_available
) {
1805 ric_cost
= ria
->cost
+ rib
->cost
;
1806 ric
->cost
= (ric_cost
< 0) ? UINT32_MAX
: ric_cost
;
1808 ric
->interval
= MAX(ria
->interval
, rib
->interval
);
1809 ric
->options
= ria
->options
& rib
->options
;
1810 memcpy(&ric
->schedule
, &schedule
, 84);
1816 * helper function for Dijkstra's algorithm. a new path has been found from a
1817 * root vertex to vertex 'vertex2'. this path is ('vertex1->root, ..., vertex1,
1818 * vertex2'). 'edge' is the edge connecting 'vertex1' and 'vertex2'. if this new
1819 * path is better (in this case cheaper, or has a longer schedule), update
1820 * 'vertex2' to use the new path.
1822 static NTSTATUS
kcctpl_try_new_path(TALLOC_CTX
*mem_ctx
,
1823 struct kcctpl_graph
*graph
,
1824 struct kcctpl_vertex_list vertices
,
1825 struct kcctpl_vertex
*vertex1
,
1826 struct kcctpl_multi_edge
*edge
,
1827 struct kcctpl_vertex
*vertex2
)
1829 struct kcctpl_repl_info new_repl_info
;
1831 uint32_t i
, new_duration
, old_duration
;
1833 ZERO_STRUCT(new_repl_info
);
1835 intersect
= kcctpl_combine_repl_info(graph
, &vertex1
->repl_info
,
1836 &edge
->repl_info
, &new_repl_info
);
1838 if (new_repl_info
.cost
> vertex2
->repl_info
.cost
) {
1839 return NT_STATUS_OK
;
1842 if (new_repl_info
.cost
< vertex2
->repl_info
.cost
&& !intersect
) {
1843 return NT_STATUS_OK
;
1846 new_duration
= old_duration
= 0;
1847 for (i
= 0; i
< 84; i
++) {
1848 if (new_repl_info
.schedule
[i
] == 1) {
1852 if (vertex2
->repl_info
.schedule
[i
] == 1) {
1857 if (new_repl_info
.cost
< vertex2
->repl_info
.cost
||
1858 new_duration
> old_duration
) {
1859 struct kcctpl_vertex
*new_data
;
1861 vertex2
->root_id
= vertex1
->root_id
;
1862 vertex2
->component_id
= vertex1
->component_id
;
1863 vertex2
->repl_info
= new_repl_info
;
1865 new_data
= talloc_realloc(mem_ctx
, vertices
.data
,
1866 struct kcctpl_vertex
,
1867 vertices
.count
+ 1);
1868 NT_STATUS_HAVE_NO_MEMORY(new_data
);
1869 new_data
[vertices
.count
+ 1] = *vertex2
;
1870 vertices
.data
= new_data
;
1874 return NT_STATUS_OK
;
1878 * run Dijkstra's algorithm with the red (and possibly black) vertices as the
1879 * root vertices, and build up a shortest-path forest.
1881 static NTSTATUS
kcctpl_dijkstra(struct kcctpl_graph
*graph
, struct GUID type
,
1884 TALLOC_CTX
*tmp_ctx
;
1885 struct kcctpl_vertex_list vertices
;
1888 tmp_ctx
= talloc_new(graph
);
1889 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1891 status
= kcctpl_setup_dijkstra(tmp_ctx
, graph
, type
, include_black
,
1893 if (NT_STATUS_IS_ERR(status
)) {
1894 DEBUG(1, (__location__
": failed to build the initial sequence "
1895 "for Dijkstra's algorithm: %s\n", nt_errstr(status
)));
1897 talloc_free(tmp_ctx
);
1901 while (vertices
.count
> 0) {
1902 uint32_t minimum_cost
, minimum_index
, i
;
1903 struct kcctpl_vertex
*minimum_vertex
, *new_data
;
1905 minimum_cost
= UINT32_MAX
;
1907 minimum_vertex
= NULL
;
1908 for (i
= 0; i
< vertices
.count
; i
++) {
1909 struct kcctpl_vertex
*vertex
= &vertices
.data
[i
];
1911 if (vertex
->repl_info
.cost
< minimum_cost
) {
1912 minimum_cost
= vertex
->repl_info
.cost
;
1913 minimum_vertex
= vertex
;
1915 } else if (vertex
->repl_info
.cost
== minimum_cost
&&
1916 GUID_compare(&vertex
->id
,
1917 &minimum_vertex
->id
) < 0) {
1918 minimum_vertex
= vertex
;
1923 if (minimum_index
< vertices
.count
- 1) {
1924 memcpy(&vertices
.data
[minimum_index
+ 1],
1925 &vertices
.data
[minimum_index
],
1926 vertices
.count
- minimum_index
- 1);
1928 new_data
= talloc_realloc(tmp_ctx
, vertices
.data
,
1929 struct kcctpl_vertex
,
1930 vertices
.count
- 1);
1931 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1932 talloc_free(vertices
.data
);
1933 vertices
.data
= new_data
;
1936 for (i
= 0; i
< graph
->edges
.count
; i
++) {
1937 struct kcctpl_multi_edge
*edge
= &graph
->edges
.data
[i
];
1939 if (kcctpl_guid_list_contains(minimum_vertex
->edge_ids
,
1943 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
1944 struct GUID vertex_id
;
1945 struct kcctpl_vertex
*vertex
;
1947 vertex_id
= edge
->vertex_ids
.data
[j
];
1948 vertex
= kcctpl_find_vertex_by_guid(graph
,
1951 DEBUG(1, (__location__
1954 GUID_string(tmp_ctx
,
1957 talloc_free(tmp_ctx
);
1958 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1961 kcctpl_try_new_path(tmp_ctx
, graph
,
1970 talloc_free(tmp_ctx
);
1971 return NT_STATUS_OK
;
1975 * add an edge to the list of edges that will be processed with Kruskal's. the
1976 * endpoints are in fact the root of the vertices to pass in, so the endpoints
1977 * are always colored vertices.
1979 static NTSTATUS
kcctpl_add_int_edge(TALLOC_CTX
*mem_ctx
,
1980 struct kcctpl_graph
*graph
,
1981 struct kcctpl_internal_edge_list internal_edges
,
1982 struct kcctpl_multi_edge
*edge
,
1983 struct kcctpl_vertex
*vertex1
,
1984 struct kcctpl_vertex
*vertex2
)
1986 struct kcctpl_vertex
*root1
, *root2
;
1987 bool red_red
, found
;
1988 struct kcctpl_repl_info repl_info1
, repl_info2
;
1989 struct kcctpl_internal_edge new_internal_edge
, *new_data
;
1992 root1
= kcctpl_find_vertex_by_guid(graph
, vertex1
->root_id
);
1994 TALLOC_CTX
*tmp_ctx
= talloc_new(graph
);
1995 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1997 DEBUG(1, (__location__
": failed to find vertex %s\n",
1998 GUID_string(tmp_ctx
, &vertex1
->root_id
)));
2000 talloc_free(tmp_ctx
);
2001 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2004 root2
= kcctpl_find_vertex_by_guid(graph
, vertex2
->root_id
);
2006 TALLOC_CTX
*tmp_ctx
= talloc_new(graph
);
2007 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2009 DEBUG(1, (__location__
": failed to find vertex %s\n",
2010 GUID_string(tmp_ctx
, &vertex2
->root_id
)));
2012 talloc_free(tmp_ctx
);
2013 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2016 red_red
= (root1
->color
== RED
&& root2
->color
== RED
);
2019 if (!kcctpl_guid_list_contains(root1
->accept_red_red
,
2021 !kcctpl_guid_list_contains(root2
->accept_red_red
,
2023 return NT_STATUS_OK
;
2025 } else if (!kcctpl_guid_list_contains(root1
->accept_black
,
2027 !kcctpl_guid_list_contains(root2
->accept_black
,
2029 return NT_STATUS_OK
;
2032 if (!kcctpl_combine_repl_info(graph
, &vertex1
->repl_info
,
2033 &vertex2
->repl_info
, &repl_info1
) ||
2034 !kcctpl_combine_repl_info(graph
, &repl_info1
, &edge
->repl_info
,
2036 return NT_STATUS_OK
;
2039 new_internal_edge
.v1id
= root1
->id
;
2040 new_internal_edge
.v2id
= root2
->id
;
2041 new_internal_edge
.red_red
= red_red
;
2042 new_internal_edge
.repl_info
= repl_info2
;
2043 new_internal_edge
.type
= edge
->type
;
2045 if (GUID_compare(&new_internal_edge
.v1id
,
2046 &new_internal_edge
.v2id
) > 0) {
2047 struct GUID tmp_guid
= new_internal_edge
.v1id
;
2049 new_internal_edge
.v1id
= new_internal_edge
.v2id
;
2050 new_internal_edge
.v2id
= tmp_guid
;
2054 for (i
= 0; i
< internal_edges
.count
; i
++) {
2055 struct kcctpl_internal_edge
*ie
= &internal_edges
.data
[i
];
2057 if (kcctpl_internal_edge_equal(ie
, &new_internal_edge
)) {
2062 return NT_STATUS_OK
;
2065 new_data
= talloc_realloc(mem_ctx
, internal_edges
.data
,
2066 struct kcctpl_internal_edge
,
2067 internal_edges
.count
+ 1);
2068 NT_STATUS_HAVE_NO_MEMORY(new_data
);
2069 new_data
[internal_edges
.count
+ 1] = new_internal_edge
;
2070 internal_edges
.data
= new_data
;
2071 internal_edges
.count
++;
2073 return NT_STATUS_OK
;
2077 * after running Dijkstra's algorithm, this function examines a multi-edge and
2078 * adds internal edges between every tree connected by this edge.
2080 static NTSTATUS
kcctpl_process_edge(TALLOC_CTX
*mem_ctx
,
2081 struct kcctpl_graph
*graph
,
2082 struct kcctpl_multi_edge
*edge
,
2083 struct kcctpl_internal_edge_list internal_edges
)
2085 TALLOC_CTX
*tmp_ctx
;
2086 struct kcctpl_vertex_list vertices
;
2088 struct kcctpl_vertex
*best_vertex
;
2090 ZERO_STRUCT(vertices
);
2092 tmp_ctx
= talloc_new(mem_ctx
);
2093 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2095 for (i
= 0; i
< edge
->vertex_ids
.count
; i
++) {
2097 struct kcctpl_vertex
*vertex
, *new_data
;
2099 id
= edge
->vertex_ids
.data
[i
];
2101 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2103 DEBUG(1, (__location__
": failed to find vertex %s\n",
2104 GUID_string(tmp_ctx
, &id
)));
2106 talloc_free(tmp_ctx
);
2107 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2110 new_data
= talloc_realloc(tmp_ctx
, vertices
.data
,
2111 struct kcctpl_vertex
,
2112 vertices
.count
+ 1);
2113 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
2114 new_data
[vertices
.count
] = *vertex
;
2115 vertices
.data
= new_data
;
2119 qsort(vertices
.data
, vertices
.count
, sizeof(struct kcctpl_vertex
),
2120 kcctpl_sort_vertices
);
2122 best_vertex
= &vertices
.data
[0];
2124 for (i
= 0; i
< edge
->vertex_ids
.count
; i
++) {
2125 struct GUID id
, empty_id
= GUID_zero();
2126 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2128 id
= edge
->vertex_ids
.data
[i
];
2130 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2132 DEBUG(1, (__location__
": failed to find vertex %s\n",
2133 GUID_string(tmp_ctx
, &id
)));
2135 talloc_free(tmp_ctx
);
2136 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2139 if (!GUID_equal(&vertex
->component_id
, &empty_id
) &&
2140 !GUID_equal(&vertex
->root_id
, &empty_id
)) {
2144 if (!GUID_equal(&best_vertex
->component_id
,
2146 !GUID_equal(&best_vertex
->root_id
, &empty_id
) &&
2147 !GUID_equal(&vertex
->component_id
, &empty_id
) &&
2148 !GUID_equal(&vertex
->root_id
, &empty_id
) &&
2149 !GUID_equal(&best_vertex
->component_id
,
2150 &vertex
->component_id
)) {
2153 status
= kcctpl_add_int_edge(mem_ctx
, graph
,
2157 if (NT_STATUS_IS_ERR(status
)) {
2158 DEBUG(1, (__location__
": failed to add an "
2159 "internal edge for %s: %s\n",
2160 GUID_string(tmp_ctx
, &vertex
->id
),
2161 nt_errstr(status
)));
2162 talloc_free(tmp_ctx
);
2168 talloc_free(tmp_ctx
);
2169 return NT_STATUS_OK
;
2173 * after running Dijkstra's algorithm to determine the shortest-path forest,
2174 * examine all edges in this edge set. find all inter-tree edges, from which to
2175 * build the list of 'internal edges', which will later be passed on to
2176 * Kruskal's algorithm.
2178 static NTSTATUS
kcctpl_process_edge_set(TALLOC_CTX
*mem_ctx
,
2179 struct kcctpl_graph
*graph
,
2180 struct kcctpl_multi_edge_set
*set
,
2181 struct kcctpl_internal_edge_list internal_edges
)
2186 for (i
= 0; i
< graph
->edges
.count
; i
++) {
2187 struct kcctpl_multi_edge
*edge
;
2191 edge
= &graph
->edges
.data
[i
];
2193 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
2195 struct kcctpl_vertex
*vertex
;
2197 id
= edge
->vertex_ids
.data
[j
];
2199 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2201 TALLOC_CTX
*tmp_ctx
;
2203 tmp_ctx
= talloc_new(mem_ctx
);
2204 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2206 DEBUG(1, (__location__
": failed to "
2208 GUID_string(tmp_ctx
, &id
)));
2210 talloc_free(tmp_ctx
);
2211 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2214 kcctpl_check_demote_one_vertex(vertex
,
2218 status
= kcctpl_process_edge(mem_ctx
, graph
, edge
,
2220 if (NT_STATUS_IS_ERR(status
)) {
2221 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2222 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2224 DEBUG(1, (__location__
": failed to process "
2226 GUID_string(tmp_ctx
, &edge
->id
),
2227 nt_errstr(status
)));
2229 talloc_free(tmp_ctx
);
2233 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
2235 struct kcctpl_vertex
*vertex
;
2237 id
= edge
->vertex_ids
.data
[j
];
2239 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2241 TALLOC_CTX
*tmp_ctx
;
2243 tmp_ctx
= talloc_new(mem_ctx
);
2244 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2246 DEBUG(1, (__location__
": failed to "
2248 GUID_string(tmp_ctx
, &id
)));
2250 talloc_free(tmp_ctx
);
2251 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2254 kcctpl_undemote_one_vertex(vertex
);
2258 for (i
= 0; i
< graph
->edges
.count
; i
++) {
2259 struct kcctpl_multi_edge
*edge
= &graph
->edges
.data
[i
];
2261 if (kcctpl_guid_list_contains(set
->edge_ids
,
2265 status
= kcctpl_process_edge(mem_ctx
, graph
,
2268 if (NT_STATUS_IS_ERR(status
)) {
2269 TALLOC_CTX
*tmp_ctx
;
2271 tmp_ctx
= talloc_new(mem_ctx
);
2272 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2274 DEBUG(1, (__location__
": failed to "
2275 "process edge %s: %s\n",
2276 GUID_string(tmp_ctx
,
2278 nt_errstr(status
)));
2280 talloc_free(tmp_ctx
);
2287 return NT_STATUS_OK
;
2291 * a new edge, 'internal_edge', has been found for the spanning tree edge. add
2292 * this edge to the list of output edges.
2294 static NTSTATUS
kcctpl_add_out_edge(TALLOC_CTX
*mem_ctx
,
2295 struct kcctpl_graph
*graph
,
2296 struct kcctpl_multi_edge_list output_edges
,
2297 struct kcctpl_internal_edge
*internal_edge
)
2299 struct kcctpl_vertex
*vertex1
, *vertex2
;
2300 TALLOC_CTX
*tmp_ctx
;
2301 struct kcctpl_multi_edge
*new_edge
, *new_data
;
2302 struct GUID
*new_data_id
;
2304 tmp_ctx
= talloc_new(mem_ctx
);
2305 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2307 vertex1
= kcctpl_find_vertex_by_guid(graph
, internal_edge
->v1id
);
2309 DEBUG(1, (__location__
": failed to find vertex %s\n",
2310 GUID_string(tmp_ctx
, &internal_edge
->v1id
)));
2312 talloc_free(tmp_ctx
);
2313 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2316 vertex2
= kcctpl_find_vertex_by_guid(graph
, internal_edge
->v2id
);
2318 DEBUG(1, (__location__
": failed to find vertex %s\n",
2319 GUID_string(tmp_ctx
, &internal_edge
->v2id
)));
2321 talloc_free(tmp_ctx
);
2322 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2325 new_edge
= talloc(tmp_ctx
, struct kcctpl_multi_edge
);
2326 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge
, tmp_ctx
);
2328 new_edge
->id
= GUID_random(); /* TODO: what should be new_edge->GUID? */
2329 new_edge
->directed
= false;
2331 new_edge
->vertex_ids
.data
= talloc_array(new_edge
, struct GUID
, 2);
2332 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge
->vertex_ids
.data
, tmp_ctx
);
2334 new_edge
->vertex_ids
.data
[0] = vertex1
->id
;
2335 new_edge
->vertex_ids
.data
[1] = vertex2
->id
;
2336 new_edge
->vertex_ids
.count
= 2;
2338 new_edge
->type
= internal_edge
->type
;
2339 new_edge
->repl_info
= internal_edge
->repl_info
;
2341 new_data
= talloc_realloc(tmp_ctx
, output_edges
.data
,
2342 struct kcctpl_multi_edge
,
2343 output_edges
.count
+ 1);
2344 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
2345 new_data
[output_edges
.count
+ 1] = *new_edge
;
2346 output_edges
.data
= new_data
;
2347 output_edges
.count
++;
2349 new_data_id
= talloc_realloc(vertex1
, vertex1
->edge_ids
.data
,
2350 struct GUID
, vertex1
->edge_ids
.count
);
2351 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id
, tmp_ctx
);
2352 new_data_id
[vertex1
->edge_ids
.count
] = new_edge
->id
;
2353 talloc_free(vertex1
->edge_ids
.data
);
2354 vertex1
->edge_ids
.data
= new_data_id
;
2355 vertex1
->edge_ids
.count
++;
2357 new_data_id
= talloc_realloc(vertex2
, vertex2
->edge_ids
.data
,
2358 struct GUID
, vertex2
->edge_ids
.count
);
2359 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id
, tmp_ctx
);
2360 new_data_id
[vertex2
->edge_ids
.count
] = new_edge
->id
;
2361 talloc_free(vertex2
->edge_ids
.data
);
2362 vertex2
->edge_ids
.data
= new_data_id
;
2363 vertex2
->edge_ids
.count
++;
2365 talloc_steal(graph
, new_edge
);
2366 talloc_steal(mem_ctx
, output_edges
.data
);
2367 talloc_free(tmp_ctx
);
2368 return NT_STATUS_OK
;
2372 * run Kruskal's minimum-cost spanning tree algorithm on the internal edges
2373 * (that represent shortest paths in the original graph between colored
2376 static NTSTATUS
kcctpl_kruskal(TALLOC_CTX
*mem_ctx
, struct kcctpl_graph
*graph
,
2377 struct kcctpl_internal_edge_list internal_edges
,
2378 struct kcctpl_multi_edge_list
*_output_edges
)
2380 uint32_t i
, num_expected_tree_edges
, cst_edges
;
2381 struct kcctpl_multi_edge_list output_edges
;
2383 num_expected_tree_edges
= 0;
2384 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2385 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2387 talloc_free(vertex
->edge_ids
.data
);
2388 ZERO_STRUCT(vertex
->edge_ids
);
2390 if (vertex
->color
== RED
|| vertex
->color
== WHITE
) {
2391 num_expected_tree_edges
++;
2395 qsort(internal_edges
.data
, internal_edges
.count
,
2396 sizeof(struct kcctpl_internal_edge
), kcctpl_sort_internal_edges
);
2400 ZERO_STRUCT(output_edges
);
2402 while (internal_edges
.count
> 0 &&
2403 cst_edges
< num_expected_tree_edges
) {
2404 struct kcctpl_internal_edge
*edge
, *new_data
;
2405 struct kcctpl_vertex
*vertex1
, *vertex2
;
2406 struct GUID comp1
, comp2
;
2408 edge
= &internal_edges
.data
[0];
2410 vertex1
= kcctpl_find_vertex_by_guid(graph
, edge
->v1id
);
2412 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2413 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2415 DEBUG(1, (__location__
": failed to find vertex %s\n",
2416 GUID_string(tmp_ctx
, &edge
->v1id
)));
2418 talloc_free(tmp_ctx
);
2419 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2422 vertex2
= kcctpl_find_vertex_by_guid(graph
, edge
->v2id
);
2424 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2425 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2427 DEBUG(1, (__location__
": failed to find vertex %s\n",
2428 GUID_string(tmp_ctx
, &edge
->v2id
)));
2430 talloc_free(tmp_ctx
);
2431 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2434 comp1
= kcctpl_get_component_id(graph
, vertex1
);
2435 comp2
= kcctpl_get_component_id(graph
, vertex2
);
2437 if (!GUID_equal(&comp1
, &comp2
)) {
2439 struct kcctpl_vertex
*vertex
;
2443 status
= kcctpl_add_out_edge(mem_ctx
, graph
,
2444 output_edges
, edge
);
2445 if (NT_STATUS_IS_ERR(status
)) {
2446 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2447 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2449 DEBUG(1, (__location__
": failed to add an "
2450 "output edge between %s and %s: %s\n",
2451 GUID_string(tmp_ctx
, &edge
->v1id
),
2452 GUID_string(tmp_ctx
, &edge
->v2id
),
2453 nt_errstr(status
)));
2455 talloc_free(tmp_ctx
);
2459 vertex
= kcctpl_find_vertex_by_guid(graph
, comp1
);
2461 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2462 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2464 DEBUG(1, (__location__
": failed to find "
2465 "vertex %s\n", GUID_string(tmp_ctx
,
2468 talloc_free(tmp_ctx
);
2469 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2471 vertex
->component_id
= comp2
;
2474 internal_edges
.data
= internal_edges
.data
+ 1;
2475 new_data
= talloc_realloc(mem_ctx
, internal_edges
.data
,
2476 struct kcctpl_internal_edge
,
2477 internal_edges
.count
- 1);
2478 NT_STATUS_HAVE_NO_MEMORY(new_data
);
2479 talloc_free(internal_edges
.data
);
2480 internal_edges
.data
= new_data
;
2481 internal_edges
.count
--;
2484 *_output_edges
= output_edges
;
2485 return NT_STATUS_OK
;
2489 * count the number of components. a component is considered to be a bunch of
2490 * colored vertices that are connected by the spanning tree. vertices whose
2491 * component ID is the same as their vertex ID are the root of the connected
2494 static uint32_t kcctpl_count_components(struct kcctpl_graph
*graph
)
2496 uint32_t num_components
= 0, i
;
2498 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2499 struct kcctpl_vertex
*vertex
;
2500 struct GUID component_id
;
2502 vertex
= &graph
->vertices
.data
[i
];
2504 if (vertex
->color
== WHITE
) {
2508 component_id
= kcctpl_get_component_id(graph
, vertex
);
2509 if (GUID_equal(&component_id
, &vertex
->id
)) {
2510 vertex
->component_index
= num_components
;
2515 return num_components
;
2519 * calculate the spanning tree and return the edges that include the vertex for
2522 static NTSTATUS
kcctpl_get_spanning_tree_edges(struct kccsrv_service
*service
,
2523 TALLOC_CTX
*mem_ctx
,
2524 struct kcctpl_graph
*graph
,
2525 uint32_t *_component_count
,
2526 struct kcctpl_multi_edge_list
*_st_edge_list
)
2528 TALLOC_CTX
*tmp_ctx
;
2529 struct kcctpl_internal_edge_list internal_edges
;
2530 uint32_t i
, component_count
;
2532 struct kcctpl_multi_edge_list output_edges
, st_edge_list
;
2534 ZERO_STRUCT(internal_edges
);
2536 tmp_ctx
= talloc_new(mem_ctx
);
2537 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2539 for (i
= 0; i
< graph
->edge_sets
.count
; i
++) {
2540 struct kcctpl_multi_edge_set
*set
;
2541 struct GUID edge_type
;
2544 set
= &graph
->edge_sets
.data
[i
];
2546 edge_type
= GUID_zero();
2548 for (j
= 0; j
< graph
->vertices
.count
; j
++) {
2549 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[j
];
2551 talloc_free(vertex
->edge_ids
.data
);
2552 ZERO_STRUCT(vertex
->edge_ids
.data
);
2555 for (j
= 0; j
< set
->edge_ids
.count
; j
++) {
2556 struct GUID edge_id
;
2557 struct kcctpl_multi_edge
*edge
;
2560 edge_id
= set
->edge_ids
.data
[j
];
2561 edge
= kcctpl_find_edge_by_guid(graph
, edge_id
);
2563 DEBUG(1, (__location__
": failed to find a "
2564 "graph edge with ID=%s\n",
2565 GUID_string(tmp_ctx
, &edge_id
)));
2567 talloc_free(tmp_ctx
);
2568 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2571 edge_type
= edge
->type
;
2573 for (k
= 0; k
< edge
->vertex_ids
.count
; k
++) {
2574 struct GUID vertex_id
, *new_data
;
2575 struct kcctpl_vertex
*vertex
;
2577 vertex_id
= edge
->vertex_ids
.data
[k
];
2578 vertex
= kcctpl_find_vertex_by_guid(graph
,
2581 DEBUG(1, (__location__
": failed to "
2582 "find a graph vertex with "
2584 GUID_string(tmp_ctx
,
2587 talloc_free(tmp_ctx
);
2588 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2591 new_data
= talloc_realloc(tmp_ctx
,
2592 vertex
->edge_ids
.data
,
2594 vertex
->edge_ids
.count
+ 1);
2595 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
,
2597 new_data
[vertex
->edge_ids
.count
] = edge
->id
;
2598 vertex
->edge_ids
.data
= new_data
;
2599 vertex
->edge_ids
.count
++;
2603 status
= kcctpl_dijkstra(graph
, edge_type
, false);
2604 if (NT_STATUS_IS_ERR(status
)) {
2605 DEBUG(1, (__location__
": failed to run Dijkstra's "
2606 "algorithm: %s\n", nt_errstr(status
)));
2608 talloc_free(tmp_ctx
);
2612 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, set
,
2614 if (NT_STATUS_IS_ERR(status
)) {
2615 DEBUG(1, (__location__
": failed to process edge set "
2616 "%s: %s\n", GUID_string(tmp_ctx
, &set
->id
),
2617 nt_errstr(status
)));
2619 talloc_free(tmp_ctx
);
2623 status
= kcctpl_dijkstra(graph
, edge_type
, true);
2624 if (NT_STATUS_IS_ERR(status
)) {
2625 DEBUG(1, (__location__
": failed to run Dijkstra's "
2626 "algorithm: %s\n", nt_errstr(status
)));
2628 talloc_free(tmp_ctx
);
2632 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, set
,
2634 if (NT_STATUS_IS_ERR(status
)) {
2635 DEBUG(1, (__location__
": failed to process edge set "
2636 "%s: %s\n", GUID_string(tmp_ctx
, &set
->id
),
2637 nt_errstr(status
)));
2639 talloc_free(tmp_ctx
);
2644 kcctpl_setup_vertices(graph
);
2646 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, NULL
, internal_edges
);
2647 if (NT_STATUS_IS_ERR(status
)) {
2648 DEBUG(1, (__location__
": failed to process empty edge set: "
2649 "%s\n", nt_errstr(status
)));
2651 talloc_free(tmp_ctx
);
2655 status
= kcctpl_kruskal(tmp_ctx
, graph
, internal_edges
, &output_edges
);
2656 if (NT_STATUS_IS_ERR(status
)) {
2657 DEBUG(1, (__location__
": failed to run Kruskal's algorithm: "
2658 "%s\n", nt_errstr(status
)));
2660 talloc_free(tmp_ctx
);
2664 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2665 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2667 if (vertex
->color
== RED
) {
2668 vertex
->dist_to_red
= 0;
2669 } else if (true) { /* TODO: if there exists a path from 'vertex'
2671 vertex
->dist_to_red
= -1; /* TODO: the length of the
2672 shortest such path */
2674 vertex
->dist_to_red
= UINT32_MAX
;
2678 component_count
= kcctpl_count_components(graph
);
2680 status
= kcctpl_copy_output_edges(service
, tmp_ctx
, graph
, output_edges
,
2682 if (NT_STATUS_IS_ERR(status
)) {
2683 DEBUG(1, (__location__
": failed to copy edge list: %s\n",
2684 nt_errstr(status
)));
2686 talloc_free(tmp_ctx
);
2690 *_component_count
= component_count
;
2691 talloc_steal(mem_ctx
, st_edge_list
.data
);
2692 *_st_edge_list
= st_edge_list
;
2693 talloc_free(tmp_ctx
);
2694 return NT_STATUS_OK
;
2698 * creat an nTDSConnection object with the given parameters if one does not
2701 static NTSTATUS
kcctpl_create_connection(struct kccsrv_service
*service
,
2702 TALLOC_CTX
*mem_ctx
,
2703 struct ldb_message
*cross_ref
,
2704 struct ldb_message
*r_bridgehead
,
2705 struct ldb_message
*transport
,
2706 struct ldb_message
*l_bridgehead
,
2707 struct kcctpl_repl_info repl_info
,
2708 uint8_t schedule
[84],
2709 bool detect_failed_dcs
,
2710 bool partial_replica_okay
,
2711 struct GUID_list
*_keep_connections
)
2713 TALLOC_CTX
*tmp_ctx
;
2714 struct ldb_dn
*r_site_dn
, *l_site_dn
, *servers_dn
;
2716 struct GUID r_site_guid
, l_site_guid
;
2718 struct message_list r_bridgeheads_all
, l_bridgeheads_all
,
2719 r_bridgeheads_available
, l_bridgeheads_available
;
2721 struct ldb_result
*res
;
2722 const char * const attrs
[] = { "objectGUID", "parent", "fromServer",
2723 "transportType", "schedule", "options",
2724 "enabledConnection", NULL
};
2725 unsigned int i
, valid_connections
;
2726 struct GUID_list keep_connections
;
2728 tmp_ctx
= talloc_new(service
);
2729 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2731 r_site_dn
= ldb_dn_copy(tmp_ctx
, r_bridgehead
->dn
);
2732 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(r_site_dn
, tmp_ctx
);
2734 ok
= ldb_dn_remove_child_components(r_site_dn
, 3);
2736 talloc_free(tmp_ctx
);
2737 return NT_STATUS_NO_MEMORY
;
2740 ret
= dsdb_find_guid_by_dn(service
->samdb
, r_site_dn
, &r_site_guid
);
2741 if (ret
!= LDB_SUCCESS
) {
2742 DEBUG(1, (__location__
": failed to find objectGUID for object "
2743 "%s: %s\n", ldb_dn_get_linearized(r_site_dn
),
2744 ldb_strerror(ret
)));
2746 talloc_free(tmp_ctx
);
2747 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2750 l_site_dn
= ldb_dn_copy(tmp_ctx
, l_bridgehead
->dn
);
2751 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(l_site_dn
, tmp_ctx
);
2753 ok
= ldb_dn_remove_child_components(l_site_dn
, 3);
2755 talloc_free(tmp_ctx
);
2756 return NT_STATUS_NO_MEMORY
;
2759 ret
= dsdb_find_guid_by_dn(service
->samdb
, l_site_dn
, &l_site_guid
);
2760 if (ret
!= LDB_SUCCESS
) {
2761 DEBUG(1, (__location__
": failed to find objectGUID for object "
2762 "%s: %s\n", ldb_dn_get_linearized(l_site_dn
),
2763 ldb_strerror(ret
)));
2765 talloc_free(tmp_ctx
);
2766 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2769 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2770 r_site_guid
, cross_ref
,
2771 transport
, partial_replica_okay
,
2772 false, &r_bridgeheads_all
);
2773 if (NT_STATUS_IS_ERR(status
)) {
2774 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2775 "%s\n", nt_errstr(status
)));
2779 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2780 r_site_guid
, cross_ref
,
2781 transport
, partial_replica_okay
,
2783 &r_bridgeheads_available
);
2784 if (NT_STATUS_IS_ERR(status
)) {
2785 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2786 "%s\n", nt_errstr(status
)));
2790 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2791 l_site_guid
, cross_ref
,
2792 transport
, partial_replica_okay
,
2793 false, &l_bridgeheads_all
);
2794 if (NT_STATUS_IS_ERR(status
)) {
2795 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2796 "%s\n", nt_errstr(status
)));
2800 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2801 l_site_guid
, cross_ref
,
2802 transport
, partial_replica_okay
,
2804 &l_bridgeheads_available
);
2805 if (NT_STATUS_IS_ERR(status
)) {
2806 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2807 "%s\n", nt_errstr(status
)));
2811 servers_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
2813 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
2815 talloc_free(tmp_ctx
);
2816 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2818 ok
= ldb_dn_add_child_fmt(servers_dn
, "CN=Servers");
2820 talloc_free(tmp_ctx
);
2821 return NT_STATUS_NO_MEMORY
;
2824 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, servers_dn
, LDB_SCOPE_SUBTREE
,
2825 attrs
, "objectClass=nTDSConnection");
2826 if (ret
!= LDB_SUCCESS
) {
2827 DEBUG(1, (__location__
": failed to find nTDSConnection "
2828 "objects: %s\n", ldb_strerror(ret
)));
2830 talloc_free(tmp_ctx
);
2831 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2834 for (i
= 0; i
< res
->count
; i
++) {
2835 struct ldb_message
*connection
;
2836 struct ldb_dn
*parent_dn
, *from_server
;
2838 connection
= res
->msgs
[i
];
2840 parent_dn
= ldb_dn_get_parent(tmp_ctx
, connection
->dn
);
2842 DEBUG(1, (__location__
": failed to get parent DN of "
2844 ldb_dn_get_linearized(connection
->dn
)));
2846 talloc_free(tmp_ctx
);
2847 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2850 from_server
= samdb_result_dn(service
->samdb
, tmp_ctx
, connection
,
2851 "fromServer", NULL
);
2853 DEBUG(1, (__location__
": failed to find fromServer "
2854 "attribute of object %s\n",
2855 ldb_dn_get_linearized(connection
->dn
)));
2857 talloc_free(tmp_ctx
);
2858 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2861 if (kcctpl_message_list_contains_dn(l_bridgeheads_all
,
2863 kcctpl_message_list_contains_dn(r_bridgeheads_all
,
2866 /* TODO: initialize conn_schedule from connection */
2867 uint8_t conn_schedule
[84];
2868 struct ldb_dn
*conn_transport_type
;
2870 conn_opts
= ldb_msg_find_attr_as_uint(connection
,
2873 conn_transport_type
= samdb_result_dn(service
->samdb
, tmp_ctx
,
2877 if (!conn_transport_type
) {
2878 DEBUG(1, (__location__
": failed to find "
2879 "transportType attribute of object "
2881 ldb_dn_get_linearized(connection
->dn
)));
2883 talloc_free(tmp_ctx
);
2884 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2887 if ((conn_opts
& NTDSCONN_OPT_IS_GENERATED
) &&
2888 !(conn_opts
& NTDSCONN_OPT_RODC_TOPOLOGY
) &&
2889 ldb_dn_compare(conn_transport_type
,
2890 transport
->dn
) == 0) {
2891 if (!(conn_opts
& NTDSCONN_OPT_USER_OWNED_SCHEDULE
) &&
2892 memcmp(&conn_schedule
, &schedule
, 84) != 0) {
2893 /* TODO: perform an originating update
2894 to set conn!schedule to schedule */
2897 if ((conn_opts
& NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
) &&
2898 (conn_opts
& NTDSCONN_OPT_USE_NOTIFY
)) {
2899 if (!(repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
)) {
2900 /* TODO: perform an originating
2901 update to clear bits
2902 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2903 and NTDSCONN_OPT_USE_NOTIFY
2906 } else if (repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
) {
2907 /* TODO: perform an originating update
2909 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2910 and NTDSCONN_OPT_USE_NOTIFY in
2914 if (conn_opts
& NTDSCONN_OPT_TWOWAY_SYNC
) {
2915 if (!(repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
)) {
2916 /* TODO: perform an originating
2918 NTDSCONN_OPT_TWOWAY_SYNC in
2921 } else if (repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
) {
2922 /* TODO: perform an originating update
2923 to set bit NTDSCONN_OPT_TWOWAY_SYNC
2927 if (conn_opts
& NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
) {
2928 if (!(repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
)) {
2929 /* TODO: perform an originating
2931 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2934 } else if (repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
) {
2935 /* TODO: perform an originating update
2937 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2944 ZERO_STRUCT(keep_connections
);
2946 valid_connections
= 0;
2947 for (i
= 0; i
< res
->count
; i
++) {
2948 struct ldb_message
*connection
;
2949 struct ldb_dn
*parent_dn
, *from_server
;
2951 connection
= res
->msgs
[i
];
2953 parent_dn
= ldb_dn_get_parent(tmp_ctx
, connection
->dn
);
2955 DEBUG(1, (__location__
": failed to get parent DN of "
2957 ldb_dn_get_linearized(connection
->dn
)));
2959 talloc_free(tmp_ctx
);
2960 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2963 from_server
= samdb_result_dn(service
->samdb
, tmp_ctx
, connection
,
2964 "fromServer", NULL
);
2966 DEBUG(1, (__location__
": failed to find fromServer "
2967 "attribute of object %s\n",
2968 ldb_dn_get_linearized(connection
->dn
)));
2970 talloc_free(tmp_ctx
);
2971 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2974 if (kcctpl_message_list_contains_dn(l_bridgeheads_all
,
2976 kcctpl_message_list_contains_dn(r_bridgeheads_all
,
2979 struct ldb_dn
*conn_transport_type
;
2981 conn_opts
= ldb_msg_find_attr_as_uint(connection
,
2984 conn_transport_type
= samdb_result_dn(service
->samdb
, tmp_ctx
,
2988 if (!conn_transport_type
) {
2989 DEBUG(1, (__location__
": failed to find "
2990 "transportType attribute of object "
2992 ldb_dn_get_linearized(connection
->dn
)));
2994 talloc_free(tmp_ctx
);
2995 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2998 if ((!(conn_opts
& NTDSCONN_OPT_IS_GENERATED
) ||
2999 ldb_dn_compare(conn_transport_type
,
3000 transport
->dn
) == 0) &&
3001 !(conn_opts
& NTDSCONN_OPT_RODC_TOPOLOGY
)) {
3002 struct GUID r_guid
, l_guid
, conn_guid
;
3003 bool failed_state_r
, failed_state_l
;
3005 ret
= dsdb_find_guid_by_dn(service
->samdb
, from_server
,
3007 if (ret
!= LDB_SUCCESS
) {
3008 DEBUG(1, (__location__
": failed to "
3009 "find GUID for object %s\n",
3010 ldb_dn_get_linearized(from_server
)));
3012 talloc_free(tmp_ctx
);
3013 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3016 ret
= dsdb_find_guid_by_dn(service
->samdb
, parent_dn
,
3018 if (ret
!= LDB_SUCCESS
) {
3019 DEBUG(1, (__location__
": failed to "
3020 "find GUID for object %s\n",
3021 ldb_dn_get_linearized(parent_dn
)));
3023 talloc_free(tmp_ctx
);
3024 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3027 status
= kcctpl_bridgehead_dc_failed(service
->samdb
,
3031 if (NT_STATUS_IS_ERR(status
)) {
3032 DEBUG(1, (__location__
": failed to "
3033 "check if bridgehead DC has "
3035 nt_errstr(status
)));
3037 talloc_free(tmp_ctx
);
3041 status
= kcctpl_bridgehead_dc_failed(service
->samdb
,
3045 if (NT_STATUS_IS_ERR(status
)) {
3046 DEBUG(1, (__location__
": failed to "
3047 "check if bridgehead DC has "
3049 nt_errstr(status
)));
3051 talloc_free(tmp_ctx
);
3055 if (!failed_state_r
&& !failed_state_l
) {
3056 valid_connections
++;
3059 conn_guid
= samdb_result_guid(connection
,
3062 if (!kcctpl_guid_list_contains(keep_connections
,
3064 struct GUID
*new_data
;
3066 new_data
= talloc_realloc(tmp_ctx
,
3067 keep_connections
.data
,
3069 keep_connections
.count
+ 1);
3070 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
,
3072 new_data
[keep_connections
.count
] = conn_guid
;
3073 keep_connections
.data
= new_data
;
3074 keep_connections
.count
++;
3080 if (valid_connections
== 0) {
3081 uint64_t opts
= NTDSCONN_OPT_IS_GENERATED
;
3082 struct GUID new_guid
, *new_data
;
3084 if (repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
) {
3085 opts
|= NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
;
3086 opts
|= NTDSCONN_OPT_USE_NOTIFY
;
3089 if (repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
) {
3090 opts
|= NTDSCONN_OPT_TWOWAY_SYNC
;
3093 if (repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
) {
3094 opts
|= NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
;
3097 /* perform an originating update to create a new nTDSConnection
3098 * object cn that is:
3100 * - child of l_bridgehead
3101 * - cn!enabledConnection = true
3102 * - cn!options = opts
3103 * - cn!transportType = t
3104 * - cn!fromServer = r_bridgehead
3105 * - cn!schedule = schedule
3108 /* TODO: what should be the new connection's GUID? */
3109 new_guid
= GUID_random();
3111 new_data
= talloc_realloc(tmp_ctx
, keep_connections
.data
,
3113 keep_connections
.count
+ 1);
3114 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
3115 new_data
[keep_connections
.count
] = new_guid
;
3116 keep_connections
.data
= new_data
;
3117 keep_connections
.count
++;
3120 talloc_steal(mem_ctx
, keep_connections
.data
);
3121 *_keep_connections
= keep_connections
;
3122 talloc_free(tmp_ctx
);
3123 return NT_STATUS_OK
;
3127 * construct an NC replica graph for the NC identified by the given 'cross_ref',
3128 * then create any additional nTDSConnection objects required.
3130 static NTSTATUS
kcctpl_create_connections(struct kccsrv_service
*service
,
3131 TALLOC_CTX
*mem_ctx
,
3132 struct kcctpl_graph
*graph
,
3133 struct ldb_message
*cross_ref
,
3134 bool detect_failed_dcs
,
3135 struct GUID_list keep_connections
,
3136 bool *_found_failed_dcs
,
3139 bool connected
, found_failed_dcs
, partial_replica_okay
;
3141 struct ldb_message
*site
;
3142 TALLOC_CTX
*tmp_ctx
;
3143 struct GUID site_guid
;
3144 struct kcctpl_vertex
*site_vertex
;
3145 uint32_t component_count
, i
;
3146 struct kcctpl_multi_edge_list st_edge_list
;
3147 struct ldb_dn
*transports_dn
;
3148 const char * const attrs
[] = { "bridgeheadServerListBL", "name",
3149 "transportAddressAttribute", NULL
};
3154 status
= kcctpl_color_vertices(service
, graph
, cross_ref
, detect_failed_dcs
,
3156 if (NT_STATUS_IS_ERR(status
)) {
3157 DEBUG(1, (__location__
": failed to color vertices: %s\n",
3158 nt_errstr(status
)));
3163 tmp_ctx
= talloc_new(mem_ctx
);
3164 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
3166 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
3168 DEBUG(1, (__location__
": failed to find our own local DC's "
3171 talloc_free(tmp_ctx
);
3172 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3175 site_guid
= samdb_result_guid(site
, "objectGUID");
3177 site_vertex
= kcctpl_find_vertex_by_guid(graph
, site_guid
);
3179 DEBUG(1, (__location__
": failed to find vertex %s\n",
3180 GUID_string(tmp_ctx
, &site_guid
)));
3182 talloc_free(tmp_ctx
);
3183 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3186 if (site_vertex
->color
== WHITE
) {
3187 *_found_failed_dcs
= found_failed_dcs
;
3189 talloc_free(tmp_ctx
);
3190 return NT_STATUS_OK
;
3193 status
= kcctpl_get_spanning_tree_edges(service
, tmp_ctx
, graph
,
3196 if (NT_STATUS_IS_ERR(status
)) {
3197 DEBUG(1, (__location__
": failed get spanning tree edges: %s\n",
3198 nt_errstr(status
)));
3200 talloc_free(tmp_ctx
);
3204 if (component_count
> 1) {
3208 partial_replica_okay
= (site_vertex
->color
== BLACK
);
3210 transports_dn
= kcctpl_transports_dn(service
->samdb
, tmp_ctx
);
3211 if (!transports_dn
) {
3212 DEBUG(1, (__location__
": failed to find our own Inter-Site "
3213 "Transports DN\n"));
3215 talloc_free(tmp_ctx
);
3216 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3219 for (i
= 0; i
< st_edge_list
.count
; i
++) {
3220 struct kcctpl_multi_edge
*edge
;
3221 struct GUID other_site_id
;
3222 struct kcctpl_vertex
*other_site_vertex
;
3223 struct ldb_result
*res
;
3224 struct ldb_message
*transport
, *r_bridgehead
, *l_bridgehead
;
3225 uint8_t schedule
[84];
3226 uint32_t first_available
, j
, interval
;
3228 edge
= &st_edge_list
.data
[i
];
3230 if (edge
->directed
&& !GUID_equal(&edge
->vertex_ids
.data
[1],
3231 &site_vertex
->id
)) {
3235 if (GUID_equal(&edge
->vertex_ids
.data
[0], &site_vertex
->id
)) {
3236 other_site_id
= edge
->vertex_ids
.data
[1];
3238 other_site_id
= edge
->vertex_ids
.data
[0];
3241 other_site_vertex
= kcctpl_find_vertex_by_guid(graph
,
3243 if (!other_site_vertex
) {
3244 DEBUG(1, (__location__
": failed to find vertex %s\n",
3245 GUID_string(tmp_ctx
, &other_site_id
)));
3247 talloc_free(tmp_ctx
);
3248 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3251 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, transports_dn
,
3252 LDB_SCOPE_ONELEVEL
, attrs
,
3253 "(&(objectClass=interSiteTransport)"
3254 "(objectGUID=%s))", GUID_string(tmp_ctx
,
3256 if (ret
!= LDB_SUCCESS
) {
3257 DEBUG(1, (__location__
": failed to find "
3258 "interSiteTransport object %s: %s\n",
3259 GUID_string(tmp_ctx
, &edge
->type
),
3260 ldb_strerror(ret
)));
3262 talloc_free(tmp_ctx
);
3263 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3265 if (res
->count
== 0) {
3266 DEBUG(1, (__location__
": failed to find "
3267 "interSiteTransport object %s\n",
3268 GUID_string(tmp_ctx
, &edge
->type
)));
3270 talloc_free(tmp_ctx
);
3271 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3273 transport
= res
->msgs
[0];
3275 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
3276 other_site_vertex
->id
,
3277 cross_ref
, transport
,
3278 partial_replica_okay
,
3281 if (NT_STATUS_IS_ERR(status
)) {
3282 DEBUG(1, (__location__
": failed to get a bridgehead "
3283 "DC: %s\n", nt_errstr(status
)));
3285 talloc_free(tmp_ctx
);
3289 if (service
->am_rodc
) {
3290 /* TODO: l_bridgehad = nTDSDSA of local DC */
3292 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
3294 cross_ref
, transport
,
3295 partial_replica_okay
,
3298 if (NT_STATUS_IS_ERR(status
)) {
3299 DEBUG(1, (__location__
": failed to get a "
3300 "bridgehead DC: %s\n",
3301 nt_errstr(status
)));
3303 talloc_free(tmp_ctx
);
3308 ZERO_ARRAY(schedule
);
3309 first_available
= 84;
3310 interval
= edge
->repl_info
.interval
/ 15;
3311 for (j
= 0; j
< 84; j
++) {
3312 if (edge
->repl_info
.schedule
[j
] == 1) {
3313 first_available
= j
;
3317 for (j
= first_available
; j
< 84; j
+= interval
) {
3321 status
= kcctpl_create_connection(service
, mem_ctx
, cross_ref
,
3322 r_bridgehead
, transport
,
3323 l_bridgehead
, edge
->repl_info
,
3324 schedule
, detect_failed_dcs
,
3325 partial_replica_okay
,
3327 if (NT_STATUS_IS_ERR(status
)) {
3328 DEBUG(1, (__location__
": failed to create a "
3329 "connection: %s\n", nt_errstr(status
)));
3331 talloc_free(tmp_ctx
);
3336 *_found_failed_dcs
= found_failed_dcs
;
3337 *_connected
= connected
;
3338 talloc_free(tmp_ctx
);
3339 return NT_STATUS_OK
;
3343 * computes an NC replica graph for each NC replica that "should be present" on
3344 * the local DC or "is present" on any DC in the same site as the local DC. for
3345 * each edge directed to an NC replica on such a DC from an NC replica on a DC
3346 * in another site, the KCC creates and nTDSConnection object to imply that edge
3347 * if one does not already exist.
3349 static NTSTATUS
kcctpl_create_intersite_connections(struct kccsrv_service
*service
,
3350 TALLOC_CTX
*mem_ctx
,
3351 struct GUID_list
*_keep_connections
,
3352 bool *_all_connected
)
3354 struct GUID_list keep_connections
;
3356 TALLOC_CTX
*tmp_ctx
;
3357 struct ldb_dn
*partitions_dn
;
3358 struct ldb_result
*res
;
3359 const char * const attrs
[] = { "enabled", "systemFlags", "nCName",
3364 all_connected
= true;
3366 ZERO_STRUCT(keep_connections
);
3368 tmp_ctx
= talloc_new(mem_ctx
);
3369 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
3371 partitions_dn
= samdb_partitions_dn(service
->samdb
, tmp_ctx
);
3372 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(partitions_dn
, tmp_ctx
);
3374 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, partitions_dn
, LDB_SCOPE_ONELEVEL
,
3375 attrs
, "objectClass=crossRef");
3376 if (ret
!= LDB_SUCCESS
) {
3377 DEBUG(1, (__location__
": failed to find crossRef objects: "
3378 "%s\n", ldb_strerror(ret
)));
3380 talloc_free(tmp_ctx
);
3381 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3384 for (i
= 0; i
< res
->count
; i
++) {
3385 struct ldb_message
*cross_ref
;
3386 unsigned int cr_enabled
;
3388 struct kcctpl_graph
*graph
;
3389 bool found_failed_dc
, connected
;
3392 cross_ref
= res
->msgs
[i
];
3393 cr_enabled
= ldb_msg_find_attr_as_uint(cross_ref
, "enabled", -1);
3394 cr_flags
= ldb_msg_find_attr_as_int64(cross_ref
, "systemFlags", 0);
3395 if ((cr_enabled
== 0) || !(cr_flags
& FLAG_CR_NTDS_NC
)) {
3399 status
= kcctpl_setup_graph(service
->samdb
, tmp_ctx
, &graph
);
3400 if (NT_STATUS_IS_ERR(status
)) {
3401 DEBUG(1, (__location__
": failed to create a graph: "
3402 "%s\n", nt_errstr(status
)));
3404 talloc_free(tmp_ctx
);
3408 status
= kcctpl_create_connections(service
, mem_ctx
, graph
,
3413 if (NT_STATUS_IS_ERR(status
)) {
3414 DEBUG(1, (__location__
": failed to create "
3415 "connections: %s\n", nt_errstr(status
)));
3417 talloc_free(tmp_ctx
);
3422 all_connected
= false;
3424 if (found_failed_dc
) {
3425 status
= kcctpl_create_connections(service
, mem_ctx
,
3432 if (NT_STATUS_IS_ERR(status
)) {
3433 DEBUG(1, (__location__
": failed to "
3434 "create connections: %s\n",
3435 nt_errstr(status
)));
3437 talloc_free(tmp_ctx
);
3444 *_keep_connections
= keep_connections
;
3445 *_all_connected
= all_connected
;
3446 talloc_free(tmp_ctx
);
3447 return NT_STATUS_OK
;
3450 NTSTATUS
kcctpl_test(struct kccsrv_service
*service
)
3453 TALLOC_CTX
*tmp_ctx
= talloc_new(service
);
3454 struct GUID_list keep
;
3457 DEBUG(5, ("Testing kcctpl_create_intersite_connections\n"));
3458 status
= kcctpl_create_intersite_connections(service
, tmp_ctx
, &keep
,
3460 DEBUG(4, ("%s\n", nt_errstr(status
)));
3461 if (NT_STATUS_IS_OK(status
)) {
3464 DEBUG(4, ("all_connected=%d, %d GUIDs returned\n",
3465 all_connected
, keep
.count
));
3467 for (i
= 0; i
< keep
.count
; i
++) {
3468 DEBUG(4, ("GUID %d: %s\n", i
+ 1,
3469 GUID_string(tmp_ctx
, &keep
.data
[i
])));
3473 talloc_free(tmp_ctx
);