2 Unix SMB/CIFS implementation.
6 Copyright (C) CrÃstian Deives 2010
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>.
24 #include "dsdb/samdb/samdb.h"
25 #include "lib/messaging/irpc.h"
26 #include "librpc/gen_ndr/ndr_misc.h"
27 #include "dsdb/kcc/kcc_service.h"
29 #define FLAG_CR_NTDS_NC 0x00000001
30 #define FLAG_CR_NTDS_DOMAIN 0x00000002
32 #define NTDSCONN_OPT_IS_GENERATED 0x00000001
33 #define NTDSCONN_OPT_TWOWAY_SYNC 0x00000002
34 #define NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT 0x00000004
35 #define NTDSCONN_OPT_USE_NOTIFY 0x00000008
36 #define NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION 0x00000010
37 #define NTDSCONN_OPT_USER_OWNED_SCHEDULE 0x00000020
38 #define NTDSCONN_OPT_RODC_TOPOLOGY 0x00000040
40 #define NTDSDSA_OPT_IS_GC 0x00000001
42 #define NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED 0x00000008
43 #define NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED 0x00000100
44 #define NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED 0x00001000
46 #define NTDSSITELINK_OPT_USE_NOTIFY 0x00000001
47 #define NTDSSITELINK_OPT_TWOWAY_SYNC 0x00000002
48 #define NTDSSITELINK_OPT_DISABLE_COMPRESSION 0x00000004
50 #define NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
52 #define DS_BEHAVIOR_WIN2008 3
54 /** replication parameters of a graph edge */
55 struct kcctpl_repl_info
{
62 /** color of a vertex */
63 enum kcctpl_color
{ RED
, BLACK
, WHITE
};
65 /** a GUID array list */
71 /** a vertex in the site graph */
72 struct kcctpl_vertex
{
74 struct GUID_list edge_ids
;
75 enum kcctpl_color color
;
76 struct GUID_list accept_red_red
;
77 struct GUID_list accept_black
;
78 struct kcctpl_repl_info repl_info
;
86 struct GUID component_id
;
87 uint32_t component_index
;
90 /** fully connected subgraph of vertices */
91 struct kcctpl_multi_edge
{
93 struct GUID_list vertex_ids
;
95 struct kcctpl_repl_info repl_info
;
99 /** set of transitively connected kcc_multi_edge's. all edges within the set
100 * have the same type. */
101 struct kcctpl_multi_edge_set
{
103 struct GUID_list edge_ids
;
106 /** a vertices array list */
107 struct kcctpl_vertex_list
{
108 struct kcctpl_vertex
*data
;
112 /** an edges array list */
113 struct kcctpl_multi_edge_list
{
114 struct kcctpl_multi_edge
*data
;
118 /** an edge sets array list */
119 struct kcctpl_multi_edge_set_list
{
120 struct kcctpl_multi_edge_set
*data
;
125 struct kcctpl_graph
{
126 struct kcctpl_vertex_list vertices
;
127 struct kcctpl_multi_edge_list edges
;
128 struct kcctpl_multi_edge_set_list edge_sets
;
131 /** path found in the graph between two non-white vertices */
132 struct kcctpl_internal_edge
{
136 struct kcctpl_repl_info repl_info
;
140 /** an internal edges array list */
141 struct kcctpl_internal_edge_list
{
142 struct kcctpl_internal_edge
*data
;
146 /** an LDB messages array list */
147 struct message_list
{
148 struct ldb_message
*data
;
153 * sort internal edges based on:
154 * - descending red_red,
155 * - ascending repl_info.cost,
156 * - descending available time in repl_info.schedule,
161 * this function is used in 'kcctpl_kruskal'.
163 static int kcctpl_sort_internal_edges(const void *internal_edge1
,
164 const void *internal_edge2
)
166 const struct kcctpl_internal_edge
*ie1
, *ie2
;
169 ie1
= (const struct kcctpl_internal_edge
*) internal_edge1
;
170 ie2
= (const struct kcctpl_internal_edge
*) internal_edge2
;
172 cmp_red_red
= ie2
->red_red
- ie1
->red_red
;
173 if (cmp_red_red
== 0) {
174 int cmp_cost
= ie1
->repl_info
.cost
- ie2
->repl_info
.cost
;
177 uint32_t available1
, available2
, i
;
180 available1
= available2
= 0;
181 for (i
= 0; i
< 84; i
++) {
182 if (ie1
->repl_info
.schedule
[i
] == 0) {
186 if (ie2
->repl_info
.schedule
[i
] == 0) {
190 cmp_schedule
= available2
- available1
;
192 if (cmp_schedule
== 0) {
193 int cmp_v1id
= GUID_compare(&ie1
->v1id
,
197 int cmp_v2id
= GUID_compare(&ie1
->v2id
,
201 return GUID_compare(&ie1
->type
,
221 * sort vertices based on the following criteria:
222 * - ascending color (RED < BLACK),
223 * - ascending repl_info.cost,
226 * this function is used in 'kcctpl_process_edge'.
228 static int kcctpl_sort_vertices(const void *vertex1
, const void *vertex2
)
230 const struct kcctpl_vertex
*v1
, *v2
;
233 v1
= (const struct kcctpl_vertex
*) vertex1
;
234 v2
= (const struct kcctpl_vertex
*) vertex2
;
236 cmp_color
= v1
->color
- v2
->color
;
237 if (cmp_color
== 0) {
238 int cmp_cost
= v1
->repl_info
.cost
- v2
->repl_info
.cost
;
240 return GUID_compare(&v1
->id
, &v2
->id
);
250 * sort bridgehead elements (nTDSDSA) based on the following criteria:
251 * - GC servers precede non-GC servers
252 * - ascending objectGUID
254 * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
256 static int kcctpl_sort_bridgeheads(const void *bridgehead1
,
257 const void *bridgehead2
)
259 const struct ldb_message
*bh1
, *bh2
;
260 uint64_t bh1_opts
, bh2_opts
, cmp_gc
;
262 bh1
= (const struct ldb_message
*) bridgehead1
;
263 bh2
= (const struct ldb_message
*) bridgehead2
;
265 bh1_opts
= ldb_msg_find_attr_as_int64(bh1
, "options", 0);
266 bh2_opts
= ldb_msg_find_attr_as_int64(bh2
, "options", 0);
268 cmp_gc
= (bh1_opts
& NTDSDSA_OPT_IS_GC
) -
269 (bh2_opts
& NTDSDSA_OPT_IS_GC
);
272 struct GUID bh1_id
, bh2_id
;
274 bh1_id
= samdb_result_guid(bh1
, "objectGUID");
275 bh2_id
= samdb_result_guid(bh2
, "objectGUID");
277 return GUID_compare(&bh1_id
, &bh2_id
);
284 * sort bridgehead elements (nTDSDSA) in a random order.
286 * this function is used in 'kcctpl_get_all_bridgehead_dcs'.
288 static void kcctpl_shuffle_bridgeheads(struct message_list bridgeheads
)
294 for (i
= bridgeheads
.count
; i
> 1; i
--) {
296 struct ldb_message tmp
;
300 tmp
= bridgeheads
.data
[i
- 1];
301 bridgeheads
.data
[i
- 1] = bridgeheads
.data
[r
];
302 bridgeheads
.data
[r
] = tmp
;
307 * find a graph vertex based on its GUID.
309 static struct kcctpl_vertex
*kcctpl_find_vertex_by_guid(struct kcctpl_graph
*graph
,
314 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
315 if (GUID_equal(&graph
->vertices
.data
[i
].id
, &guid
)) {
316 return &graph
->vertices
.data
[i
];
324 * find a graph edge based on its GUID.
326 static struct kcctpl_multi_edge
*kcctpl_find_edge_by_guid(struct kcctpl_graph
*graph
,
331 for (i
= 0; i
< graph
->edges
.count
; i
++) {
332 if (GUID_equal(&graph
->edges
.data
[i
].id
, &guid
)) {
333 return &graph
->edges
.data
[i
];
341 * find a graph edge that contains a vertex with the specified GUID. the first
342 * occurrence will be returned.
344 static struct kcctpl_multi_edge
*kcctpl_find_edge_by_vertex_guid(struct kcctpl_graph
*graph
,
349 for (i
= 0; i
< graph
->edges
.count
; i
++) {
350 struct kcctpl_multi_edge
*edge
;
353 edge
= &graph
->edges
.data
[i
];
355 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
356 struct GUID vertex_guid
= edge
->vertex_ids
.data
[j
];
358 struct GUID
*p
= &guid
;
360 if (GUID_equal(&vertex_guid
, p
)) {
370 * search for an occurrence of a GUID inside a list of GUIDs.
372 static bool kcctpl_guid_list_contains(struct GUID_list list
, struct GUID guid
)
376 for (i
= 0; i
< list
.count
; i
++) {
377 if (GUID_equal(&list
.data
[i
], &guid
)) {
386 * search for an occurrence of an ldb_message inside a list of ldb_messages,
387 * based on the ldb_message's DN.
389 static bool kcctpl_message_list_contains_dn(struct message_list list
,
394 for (i
= 0; i
< list
.count
; i
++) {
395 struct ldb_message
*message
= &list
.data
[i
];
397 if (ldb_dn_compare(message
->dn
, dn
) == 0) {
406 * get the Transports DN
407 * (CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=<domain>).
409 static struct ldb_dn
*kcctpl_transports_dn(struct ldb_context
*ldb
,
412 struct ldb_dn
*sites_dn
;
415 sites_dn
= samdb_sites_dn(ldb
, mem_ctx
);
420 ok
= ldb_dn_add_child_fmt(sites_dn
, "CN=Inter-Site Transports");
422 talloc_free(sites_dn
);
429 * get the domain local site object.
431 static struct ldb_message
*kcctpl_local_site(struct ldb_context
*ldb
,
436 struct ldb_dn
*sites_dn
;
437 struct ldb_result
*res
;
438 const char * const attrs
[] = { "objectGUID", "options", NULL
};
440 tmp_ctx
= talloc_new(ldb
);
442 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
444 talloc_free(tmp_ctx
);
448 ret
= ldb_search(ldb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_SUBTREE
, attrs
,
451 if (ret
!= LDB_SUCCESS
|| res
->count
== 0) {
452 talloc_free(tmp_ctx
);
456 talloc_steal(mem_ctx
, res
);
457 talloc_free(tmp_ctx
);
462 * compare two internal edges for equality. every field of the structure will be
465 static bool kcctpl_internal_edge_equal(struct kcctpl_internal_edge
*edge1
,
466 struct kcctpl_internal_edge
*edge2
)
468 if (!edge1
|| !edge2
) {
472 if (!GUID_equal(&edge1
->v1id
, &edge2
->v1id
)) {
476 if (!GUID_equal(&edge1
->v2id
, &edge2
->v2id
)) {
480 if (edge1
->red_red
!= edge2
->red_red
) {
484 if (edge1
->repl_info
.cost
!= edge2
->repl_info
.cost
||
485 edge1
->repl_info
.interval
!= edge2
->repl_info
.interval
||
486 edge1
->repl_info
.options
!= edge2
->repl_info
.options
||
487 memcmp(&edge1
->repl_info
.schedule
,
488 &edge2
->repl_info
.schedule
, 84) != 0) {
492 if (!GUID_equal(&edge1
->type
, &edge2
->type
)) {
500 * create a kcctpl_graph instance.
502 static NTSTATUS
kcctpl_create_graph(TALLOC_CTX
*mem_ctx
,
503 struct GUID_list guids
,
504 struct kcctpl_graph
**_graph
)
506 struct kcctpl_graph
*graph
;
509 graph
= talloc_zero(mem_ctx
, struct kcctpl_graph
);
510 NT_STATUS_HAVE_NO_MEMORY(graph
);
512 graph
->vertices
.count
= guids
.count
;
513 graph
->vertices
.data
= talloc_zero_array(graph
, struct kcctpl_vertex
,
515 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(graph
->vertices
.data
, graph
);
517 TYPESAFE_QSORT(guids
.data
, guids
.count
, GUID_compare
);
519 for (i
= 0; i
< guids
.count
; i
++) {
520 graph
->vertices
.data
[i
].id
= guids
.data
[i
];
528 * create a kcctpl_multi_edge instance.
530 static NTSTATUS
kcctpl_create_edge(struct ldb_context
*ldb
, TALLOC_CTX
*mem_ctx
,
532 struct ldb_message
*site_link
,
533 struct kcctpl_multi_edge
**_edge
)
535 struct kcctpl_multi_edge
*edge
;
537 struct ldb_dn
*sites_dn
;
538 struct ldb_result
*res
;
539 const char * const attrs
[] = { "siteList", NULL
};
541 struct ldb_message_element
*el
;
545 tmp_ctx
= talloc_new(mem_ctx
);
546 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
548 edge
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge
);
549 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge
, tmp_ctx
);
551 edge
->id
= samdb_result_guid(site_link
, "objectGUID");
553 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
555 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
557 talloc_free(tmp_ctx
);
558 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
561 ret
= ldb_search(ldb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_SUBTREE
, attrs
,
562 "objectGUID=%s", GUID_string(tmp_ctx
, &edge
->id
));
563 if (ret
!= LDB_SUCCESS
) {
564 DEBUG(1, (__location__
": failed to find siteLink object %s: "
565 "%s\n", GUID_string(tmp_ctx
, &edge
->id
),
568 talloc_free(tmp_ctx
);
569 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
571 if (res
->count
== 0) {
572 DEBUG(1, (__location__
": failed to find siteLink object %s\n",
573 GUID_string(tmp_ctx
, &edge
->id
)));
575 talloc_free(tmp_ctx
);
576 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
579 el
= ldb_msg_find_element(res
->msgs
[0], "siteList");
581 DEBUG(1, (__location__
": failed to find siteList attribute of "
583 ldb_dn_get_linearized(res
->msgs
[0]->dn
)));
585 talloc_free(tmp_ctx
);
586 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
589 edge
->vertex_ids
.data
= talloc_array(edge
, struct GUID
, el
->num_values
);
590 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge
->vertex_ids
.data
, tmp_ctx
);
591 edge
->vertex_ids
.count
= el
->num_values
;
593 for (i
= 0; i
< el
->num_values
; i
++) {
598 dn
= ldb_dn_from_ldb_val(tmp_ctx
, ldb
, &val
);
600 DEBUG(1, (__location__
": failed to read a DN from "
601 "siteList attribute of %s\n",
602 ldb_dn_get_linearized(res
->msgs
[0]->dn
)));
604 talloc_free(tmp_ctx
);
605 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
607 ret
= dsdb_find_guid_by_dn(ldb
, dn
, &guid
);
608 if (ret
!= LDB_SUCCESS
) {
609 DEBUG(1, (__location__
": failed to find objectGUID "
610 "for object %s: %s\n",
611 ldb_dn_get_linearized(dn
),
614 talloc_free(tmp_ctx
);
615 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
618 edge
->vertex_ids
.data
[i
] = guid
;
621 edge
->repl_info
.cost
= ldb_msg_find_attr_as_int64(site_link
, "cost", 0);
622 edge
->repl_info
.options
= ldb_msg_find_attr_as_int64(site_link
, "options", 0);
623 edge
->repl_info
.interval
= ldb_msg_find_attr_as_int64(site_link
,
625 /* TODO: edge->repl_info.schedule = site_link!schedule */
627 edge
->directed
= false;
629 *_edge
= talloc_steal(mem_ctx
, edge
);
630 talloc_free(tmp_ctx
);
635 * create a kcctpl_multi_edge_set instance containing edges for all siteLink
638 static NTSTATUS
kcctpl_create_auto_edge_set(struct kcctpl_graph
*graph
,
640 struct ldb_result
*res_site_link
,
641 struct kcctpl_multi_edge_set
**_set
)
643 struct kcctpl_multi_edge_set
*set
;
647 tmp_ctx
= talloc_new(graph
);
648 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
650 set
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge_set
);
651 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set
, tmp_ctx
);
653 for (i
= 0; i
< res_site_link
->count
; i
++) {
654 struct GUID site_link_guid
;
655 struct kcctpl_multi_edge
*edge
;
657 site_link_guid
= samdb_result_guid(res_site_link
->msgs
[i
],
659 edge
= kcctpl_find_edge_by_guid(graph
, site_link_guid
);
661 DEBUG(1, (__location__
": failed to find a graph edge "
663 GUID_string(tmp_ctx
, &site_link_guid
)));
665 talloc_free(tmp_ctx
);
666 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
669 if (GUID_equal(&edge
->type
, &type
)) {
670 struct GUID
*new_data
;
672 new_data
= talloc_realloc(set
, set
->edge_ids
.data
,
674 set
->edge_ids
.count
+ 1);
675 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
676 new_data
[set
->edge_ids
.count
] = site_link_guid
;
677 set
->edge_ids
.data
= new_data
;
678 set
->edge_ids
.count
++;
682 *_set
= talloc_steal(graph
, set
);
687 * create a kcctpl_multi_edge_set instance.
689 static NTSTATUS
kcctpl_create_edge_set(struct ldb_context
*ldb
,
690 struct kcctpl_graph
*graph
,
692 struct ldb_message
*bridge
,
693 struct kcctpl_multi_edge_set
**_set
)
695 struct kcctpl_multi_edge_set
*set
;
697 struct ldb_message_element
*el
;
700 tmp_ctx
= talloc_new(ldb
);
701 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
703 set
= talloc_zero(tmp_ctx
, struct kcctpl_multi_edge_set
);
704 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set
, tmp_ctx
);
706 set
->id
= samdb_result_guid(bridge
, "objectGUID");
708 el
= ldb_msg_find_element(bridge
, "siteLinkList");
710 DEBUG(1, (__location__
": failed to find siteLinkList "
711 "attribute of object %s\n",
712 ldb_dn_get_linearized(bridge
->dn
)));
714 talloc_free(tmp_ctx
);
715 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
717 for (i
= 0; i
< el
->num_values
; i
++) {
720 struct GUID site_link_guid
;
722 struct kcctpl_multi_edge
*edge
;
725 dn
= ldb_dn_from_ldb_val(tmp_ctx
, ldb
, &val
);
727 DEBUG(1, (__location__
": failed to read a DN from "
728 "siteList attribute of %s\n",
729 ldb_dn_get_linearized(bridge
->dn
)));
731 talloc_free(tmp_ctx
);
732 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
735 ret
= dsdb_find_guid_by_dn(ldb
, dn
, &site_link_guid
);
736 if (ret
!= LDB_SUCCESS
) {
737 DEBUG(1, (__location__
": failed to find objectGUID "
738 "for object %s: %s\n",
739 ldb_dn_get_linearized(dn
),
742 talloc_free(tmp_ctx
);
743 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
746 edge
= kcctpl_find_edge_by_guid(graph
, site_link_guid
);
748 DEBUG(1, (__location__
": failed to find a graph edge "
750 GUID_string(tmp_ctx
, &site_link_guid
)));
752 talloc_free(tmp_ctx
);
753 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
756 if (GUID_equal(&edge
->type
, &type
)) {
757 struct GUID
*new_data
;
759 new_data
= talloc_realloc(set
, set
->edge_ids
.data
,
761 set
->edge_ids
.count
+ 1);
762 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
763 new_data
[set
->edge_ids
.count
] = site_link_guid
;
764 set
->edge_ids
.data
= new_data
;
765 set
->edge_ids
.count
++;
769 *_set
= talloc_steal(graph
, set
);
770 talloc_free(tmp_ctx
);
775 * set up a kcctpl_graph, populated with a kcctpl_vertex for each site object, a
776 * kcctpl_multi_edge for each siteLink object, and a kcctpl_multi_edge_set for
777 * each siteLinkBridge object (or implied siteLinkBridge).
779 static NTSTATUS
kcctpl_setup_graph(struct ldb_context
*ldb
, TALLOC_CTX
*mem_ctx
,
780 struct kcctpl_graph
**_graph
)
782 struct kcctpl_graph
*graph
;
783 struct ldb_dn
*sites_dn
, *transports_dn
;
785 struct ldb_result
*res
;
786 const char * const transport_attrs
[] = { "objectGUID", NULL
};
787 const char * const site_attrs
[] = { "objectGUID", "options", NULL
};
788 const char * const attrs
[] = { "objectGUID", "cost", "options",
789 "replInterval", "schedule", NULL
};
790 const char * const site_link_bridge_attrs
[] = { "objectGUID",
794 struct GUID_list vertex_ids
;
797 struct ldb_message
*site
;
800 tmp_ctx
= talloc_new(mem_ctx
);
801 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
803 sites_dn
= samdb_sites_dn(ldb
, tmp_ctx
);
805 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
807 talloc_free(tmp_ctx
);
808 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
811 ret
= ldb_search(ldb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_SUBTREE
,
812 site_attrs
, "objectClass=site");
813 if (ret
!= LDB_SUCCESS
) {
814 DEBUG(1, (__location__
": failed to find site objects under "
815 "%s: %s\n", ldb_dn_get_linearized(sites_dn
),
818 talloc_free(tmp_ctx
);
819 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
822 ZERO_STRUCT(vertex_ids
);
823 for (i
= 0; i
< res
->count
; i
++) {
824 struct GUID guid
, *new_data
;
826 guid
= samdb_result_guid(res
->msgs
[i
], "objectGUID");
828 new_data
= talloc_realloc(tmp_ctx
, vertex_ids
.data
, struct GUID
,
829 vertex_ids
.count
+ 1);
830 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
831 new_data
[vertex_ids
.count
] = guid
;
832 vertex_ids
.data
= new_data
;
836 status
= kcctpl_create_graph(tmp_ctx
, vertex_ids
, &graph
);
837 if (NT_STATUS_IS_ERR(status
)) {
838 DEBUG(1, (__location__
": failed to create graph: %s\n",
841 talloc_free(tmp_ctx
);
845 site
= kcctpl_local_site(ldb
, tmp_ctx
);
847 DEBUG(1, (__location__
": failed to find our own local DC's "
850 talloc_free(tmp_ctx
);
851 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
853 site_opts
= ldb_msg_find_attr_as_int64(site
, "options", 0);
855 transports_dn
= kcctpl_transports_dn(ldb
, tmp_ctx
);
856 if (!transports_dn
) {
857 DEBUG(1, (__location__
": failed to find our own Inter-Site "
860 talloc_free(tmp_ctx
);
861 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
864 ret
= ldb_search(ldb
, tmp_ctx
, &res
, transports_dn
, LDB_SCOPE_ONELEVEL
,
865 transport_attrs
, "objectClass=interSiteTransport");
866 if (ret
!= LDB_SUCCESS
) {
867 DEBUG(1, (__location__
": failed to find interSiteTransport "
868 "objects under %s: %s\n",
869 ldb_dn_get_linearized(transports_dn
),
872 talloc_free(tmp_ctx
);
873 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
876 for (i
= 0; i
< res
->count
; i
++) {
877 struct ldb_message
*transport
;
878 struct ldb_result
*res_site_link
;
879 struct GUID transport_guid
;
881 uint64_t transport_opts
;
883 transport
= res
->msgs
[i
];
885 ret
= ldb_search(ldb
, tmp_ctx
, &res_site_link
, transport
->dn
,
886 LDB_SCOPE_SUBTREE
, attrs
,
887 "objectClass=siteLink");
888 if (ret
!= LDB_SUCCESS
) {
889 DEBUG(1, (__location__
": failed to find siteLink "
890 "objects under %s: %s\n",
891 ldb_dn_get_linearized(transport
->dn
),
894 talloc_free(tmp_ctx
);
895 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
898 transport_guid
= samdb_result_guid(transport
, "objectGUID");
899 for (j
= 0; j
< res_site_link
->count
; j
++) {
900 struct kcctpl_multi_edge
*edge
, *new_data
;
902 status
= kcctpl_create_edge(ldb
, graph
, transport_guid
,
903 res_site_link
->msgs
[j
],
905 if (NT_STATUS_IS_ERR(status
)) {
906 DEBUG(1, (__location__
": failed to create "
907 "edge: %s\n", nt_errstr(status
)));
908 talloc_free(tmp_ctx
);
912 new_data
= talloc_realloc(graph
, graph
->edges
.data
,
913 struct kcctpl_multi_edge
,
914 graph
->edges
.count
+ 1);
915 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
916 new_data
[graph
->edges
.count
] = *edge
;
917 graph
->edges
.data
= new_data
;
918 graph
->edges
.count
++;
921 transport_opts
= ldb_msg_find_attr_as_int64(transport
, "options", 0);
922 if (!(transport_opts
& NTDSTRANSPORT_OPT_BRIDGES_REQUIRED
) &&
923 !(site_opts
& NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED
)) {
924 struct kcctpl_multi_edge_set
*edge_set
, *new_data
;
926 status
= kcctpl_create_auto_edge_set(graph
,
930 if (NT_STATUS_IS_ERR(status
)) {
931 DEBUG(1, (__location__
": failed to create "
932 "edge set: %s\n", nt_errstr(status
)));
933 talloc_free(tmp_ctx
);
937 new_data
= talloc_realloc(graph
, graph
->edge_sets
.data
,
938 struct kcctpl_multi_edge_set
,
939 graph
->edge_sets
.count
+ 1);
940 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
941 new_data
[graph
->edge_sets
.count
] = *edge_set
;
942 graph
->edge_sets
.data
= new_data
;
943 graph
->edge_sets
.count
++;
945 ret
= ldb_search(ldb
, tmp_ctx
, &res_site_link
,
946 transport
->dn
, LDB_SCOPE_SUBTREE
,
947 site_link_bridge_attrs
,
948 "objectClass=siteLinkBridge");
949 if (ret
!= LDB_SUCCESS
) {
950 DEBUG(1, (__location__
": failed to find "
951 "siteLinkBridge objects under %s: "
953 ldb_dn_get_linearized(transport
->dn
),
956 talloc_free(tmp_ctx
);
957 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
960 for (j
= 0; j
< res_site_link
->count
; j
++) {
961 struct ldb_message
*bridge
;
962 struct kcctpl_multi_edge_set
*edge_set
,
965 bridge
= res_site_link
->msgs
[j
];
966 status
= kcctpl_create_edge_set(ldb
, graph
,
970 if (NT_STATUS_IS_ERR(status
)) {
971 DEBUG(1, (__location__
": failed to "
972 "create edge set: %s\n",
975 talloc_free(tmp_ctx
);
979 new_data
= talloc_realloc(graph
,
980 graph
->edge_sets
.data
,
981 struct kcctpl_multi_edge_set
,
982 graph
->edge_sets
.count
+ 1);
983 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
,
985 new_data
[graph
->edge_sets
.count
] = *edge_set
;
986 graph
->edge_sets
.data
= new_data
;
987 graph
->edge_sets
.count
++;
992 *_graph
= talloc_steal(mem_ctx
, graph
);
993 talloc_free(tmp_ctx
);
998 * determine whether a given DC is known to be in a failed state.
1000 static NTSTATUS
kcctpl_bridgehead_dc_failed(struct ldb_context
*ldb
,
1002 bool detect_failed_dcs
,
1005 TALLOC_CTX
*tmp_ctx
;
1006 struct ldb_dn
*settings_dn
;
1007 struct ldb_result
*res
;
1008 const char * const attrs
[] = { "options", NULL
};
1010 struct ldb_message
*settings
;
1011 uint64_t settings_opts
;
1014 tmp_ctx
= talloc_new(ldb
);
1015 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1017 settings_dn
= samdb_ntds_settings_dn(ldb
);
1019 DEBUG(1, (__location__
": failed to find our own NTDS Settings "
1021 talloc_free(tmp_ctx
);
1022 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1025 ret
= ldb_search(ldb
, tmp_ctx
, &res
, settings_dn
, LDB_SCOPE_BASE
, attrs
,
1026 "objectClass=nTDSSiteSettings");
1027 if (ret
!= LDB_SUCCESS
) {
1028 DEBUG(1, (__location__
": failed to find site settings object "
1029 "%s: %s\n", ldb_dn_get_linearized(settings_dn
),
1030 ldb_strerror(ret
)));
1031 talloc_free(tmp_ctx
);
1032 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1034 if (res
->count
== 0) {
1035 DEBUG(1, ("failed to find site settings object %s\n",
1036 ldb_dn_get_linearized(settings_dn
)));
1037 talloc_free(tmp_ctx
);
1038 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1041 settings
= res
->msgs
[0];
1043 settings_opts
= ldb_msg_find_attr_as_int64(settings
, "options", 0);
1044 if (settings_opts
& NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED
) {
1046 } else if (true) { /* TODO: how to get kCCFailedLinks and
1047 kCCFailedConnections? */
1050 failed
= detect_failed_dcs
;
1054 talloc_free(tmp_ctx
);
1055 return NT_STATUS_OK
;
1059 * get all bridgehead DCs satisfying the given criteria.
1061 static NTSTATUS
kcctpl_get_all_bridgehead_dcs(struct kccsrv_service
*service
,
1062 TALLOC_CTX
*mem_ctx
,
1063 struct GUID site_guid
,
1064 struct ldb_message
*cross_ref
,
1065 struct ldb_message
*transport
,
1066 bool partial_replica_okay
,
1067 bool detect_failed_dcs
,
1068 struct message_list
*_bridgeheads
)
1070 struct message_list bridgeheads
, all_dcs_in_site
;
1071 TALLOC_CTX
*tmp_ctx
;
1072 struct ldb_result
*res
;
1073 struct ldb_dn
*sites_dn
, *schemas_dn
;
1074 const char * const attrs
[] = { "options", NULL
};
1076 struct ldb_message
*site
, *schema
;
1077 const char * const dc_attrs
[] = { "objectGUID", "options", NULL
};
1078 struct ldb_message_element
*el
;
1080 const char *transport_name
, *transport_address_attr
;
1083 ZERO_STRUCT(bridgeheads
);
1085 tmp_ctx
= talloc_new(mem_ctx
);
1086 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1088 sites_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
1090 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
1092 talloc_free(tmp_ctx
);
1093 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1096 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, sites_dn
, LDB_SCOPE_ONELEVEL
,
1097 attrs
, "(&(objectClass=site)(objectGUID=%s))",
1098 GUID_string(tmp_ctx
, &site_guid
));
1099 if (ret
!= LDB_SUCCESS
) {
1100 DEBUG(1, (__location__
": failed to find site object %s: %s\n",
1101 GUID_string(tmp_ctx
, &site_guid
),
1102 ldb_strerror(ret
)));
1104 talloc_free(tmp_ctx
);
1105 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1107 if (res
->count
== 0) {
1108 DEBUG(1, (__location__
": failed to find site object %s\n",
1109 GUID_string(tmp_ctx
, &site_guid
)));
1111 talloc_free(tmp_ctx
);
1112 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1114 site
= res
->msgs
[0];
1116 schemas_dn
= ldb_get_schema_basedn(service
->samdb
);
1118 DEBUG(1, (__location__
": failed to find our own Schemas DN\n"));
1120 talloc_free(tmp_ctx
);
1121 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1124 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, schemas_dn
, LDB_SCOPE_SUBTREE
,
1126 "(&(lDAPDisplayName=nTDSDSA)(objectClass=classSchema))");
1127 if (ret
!= LDB_SUCCESS
) {
1128 DEBUG(1, (__location__
": failed to find classSchema object :"
1129 "%s\n", ldb_strerror(ret
)));
1131 talloc_free(tmp_ctx
);
1132 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1134 if (res
->count
== 0) {
1135 DEBUG(1, (__location__
": failed to find classSchema "
1138 talloc_free(tmp_ctx
);
1139 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1141 schema
= res
->msgs
[0];
1143 ZERO_STRUCT(all_dcs_in_site
);
1145 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, site
->dn
, LDB_SCOPE_SUBTREE
,
1146 dc_attrs
, "objectCategory=%s",
1147 ldb_dn_get_linearized(schema
->dn
));
1148 if (ret
!= LDB_SUCCESS
) {
1149 DEBUG(1, (__location__
": failed to find DCs objects :%s\n",
1150 ldb_strerror(ret
)));
1152 talloc_free(tmp_ctx
);
1153 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1156 el
= ldb_msg_find_element(transport
, "bridgeheadServerListBL");
1158 transport_name
= ldb_msg_find_attr_as_string(transport
, "name", NULL
);
1159 if (!transport_name
) {
1160 DEBUG(1, (__location__
": failed to find name attribute of "
1161 "object %s\n", ldb_dn_get_linearized(transport
->dn
)));
1163 talloc_free(tmp_ctx
);
1164 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1167 transport_address_attr
= ldb_msg_find_attr_as_string(transport
,
1168 "transportAddressAttribute",
1170 if (!transport_address_attr
) {
1171 DEBUG(1, (__location__
": failed to find "
1172 "transportAddressAttribute attribute of object %s\n",
1173 ldb_dn_get_linearized(transport
->dn
)));
1175 talloc_free(tmp_ctx
);
1176 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1179 site_opts
= ldb_msg_find_attr_as_int64(site
, "options", 0);
1181 for (i
= 0; i
< res
->count
; i
++) {
1182 struct ldb_message
*dc
, *new_data
;
1183 struct ldb_dn
*parent_dn
;
1184 uint64_t behavior_version
;
1185 const char *dc_transport_address
;
1186 struct ldb_result
*parent_res
;
1187 const char *parent_attrs
[] = { transport_address_attr
, NULL
};
1189 struct GUID dc_guid
;
1194 parent_dn
= ldb_dn_get_parent(tmp_ctx
, dc
->dn
);
1196 DEBUG(1, (__location__
": failed to get parent DN of "
1197 "%s\n", ldb_dn_get_linearized(dc
->dn
)));
1199 talloc_free(tmp_ctx
);
1200 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1203 if (el
&& (el
->num_values
>= 1)) {
1209 for (j
= 0; j
< el
->num_values
; j
++) {
1213 val
= el
->values
[j
];
1215 dn
= ldb_dn_from_ldb_val(tmp_ctx
, service
->samdb
, &val
);
1217 DEBUG(1, (__location__
": failed to read a DN "
1218 "from bridgeheadServerListBL "
1219 "attribute of %s\n",
1220 ldb_dn_get_linearized(transport
->dn
)));
1222 talloc_free(tmp_ctx
);
1223 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1226 if (ldb_dn_compare(dn
, parent_dn
) == 0) {
1237 /* TODO: if dc is in the same site as the local DC */
1239 /* TODO: if a replica of cr!nCName is not in the set of
1240 * NC replicas that "should be present" on 'dc' */
1241 /* TODO: a partial replica of the NC "should be
1243 if (true || (true && !partial_replica_okay
)) {
1247 /* TODO: if an NC replica of cr!nCName is not in the set
1248 * of NC replicas that "are present" on 'dc' */
1249 /* TODO: a partial replica of the NC "is present" */
1250 if (true || (true && !partial_replica_okay
)) {
1255 behavior_version
= ldb_msg_find_attr_as_int64(dc
,
1256 "msDS-Behavior-Version", 0);
1257 /* TODO: cr!nCName corresponds to default NC */
1258 if (service
->am_rodc
&& true && behavior_version
< DS_BEHAVIOR_WIN2008
) {
1262 ret
= ldb_search(service
->samdb
, tmp_ctx
, &parent_res
, parent_dn
,
1263 LDB_SCOPE_BASE
, parent_attrs
, NULL
);
1265 dc_transport_address
= ldb_msg_find_attr_as_string(parent_res
->msgs
[0],
1266 transport_address_attr
,
1269 if (strncmp(transport_name
, "IP", 2) != 0 &&
1270 dc_transport_address
== NULL
) {
1274 dc_guid
= samdb_result_guid(dc
, "objectGUID");
1276 status
= kcctpl_bridgehead_dc_failed(service
->samdb
, dc_guid
,
1279 if (NT_STATUS_IS_ERR(status
)) {
1280 DEBUG(1, (__location__
": failed to check if "
1281 "bridgehead DC has failed: %s\n",
1282 nt_errstr(status
)));
1284 talloc_free(tmp_ctx
);
1292 new_data
= talloc_realloc(tmp_ctx
, bridgeheads
.data
,
1294 bridgeheads
.count
+ 1);
1295 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1296 new_data
[bridgeheads
.count
+ 1] = *dc
;
1297 bridgeheads
.data
= new_data
;
1298 bridgeheads
.count
++;
1301 if (site_opts
& NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED
) {
1302 qsort(bridgeheads
.data
, bridgeheads
.count
,
1303 sizeof(struct ldb_message
), kcctpl_sort_bridgeheads
);
1305 kcctpl_shuffle_bridgeheads(bridgeheads
);
1308 talloc_steal(mem_ctx
, bridgeheads
.data
);
1309 *_bridgeheads
= bridgeheads
;
1310 talloc_free(tmp_ctx
);
1311 return NT_STATUS_OK
;
1315 * get a bridgehead DC.
1317 static NTSTATUS
kcctpl_get_bridgehead_dc(struct kccsrv_service
*service
,
1318 TALLOC_CTX
*mem_ctx
,
1319 struct GUID site_guid
,
1320 struct ldb_message
*cross_ref
,
1321 struct ldb_message
*transport
,
1322 bool partial_replica_okay
,
1323 bool detect_failed_dcs
,
1324 struct ldb_message
**_dsa
)
1326 struct message_list dsa_list
;
1329 status
= kcctpl_get_all_bridgehead_dcs(service
, mem_ctx
,
1330 site_guid
, cross_ref
, transport
,
1331 partial_replica_okay
,
1332 detect_failed_dcs
, &dsa_list
);
1333 if (NT_STATUS_IS_ERR(status
)) {
1334 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
1335 "%s\n", nt_errstr(status
)));
1339 *_dsa
= (dsa_list
.count
== 0) ? NULL
: &dsa_list
.data
[0];
1341 return NT_STATUS_OK
;
1345 * color each vertex to indicate which kinds of NC replicas it contains.
1347 static NTSTATUS
kcctpl_color_vertices(struct kccsrv_service
*service
,
1348 struct kcctpl_graph
*graph
,
1349 struct ldb_message
*cross_ref
,
1350 bool detect_failed_dcs
,
1351 bool *_found_failed_dcs
)
1353 TALLOC_CTX
*tmp_ctx
;
1354 struct ldb_dn
*sites_dn
;
1355 bool found_failed_dcs
, partial_replica_okay
;
1357 struct ldb_message
*site
;
1358 struct ldb_result
*res
;
1360 struct GUID site_guid
;
1361 struct kcctpl_vertex
*site_vertex
;
1363 found_failed_dcs
= false;
1365 tmp_ctx
= talloc_new(service
);
1366 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1368 sites_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
1370 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
1372 talloc_free(tmp_ctx
);
1373 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1376 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1377 struct kcctpl_vertex
*vertex
;
1378 struct ldb_dn
*nc_name
;
1379 /* TODO: set 'attrs' with its corresponding values */
1380 const char * const attrs
[] = { NULL
};
1382 vertex
= &graph
->vertices
.data
[i
];
1384 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, sites_dn
,
1385 LDB_SCOPE_SUBTREE
, attrs
, "objectGUID=%s",
1386 GUID_string(tmp_ctx
, &vertex
->id
));
1387 if (ret
!= LDB_SUCCESS
) {
1388 DEBUG(1, (__location__
": failed to find site object "
1389 "%s: %s\n", GUID_string(tmp_ctx
, &vertex
->id
),
1390 ldb_strerror(ret
)));
1392 talloc_free(tmp_ctx
);
1393 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1395 if (res
->count
== 0) {
1396 DEBUG(1, (__location__
": failed to find site object "
1397 "%s\n", GUID_string(tmp_ctx
, &vertex
->id
)));
1399 talloc_free(tmp_ctx
);
1400 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1402 site
= res
->msgs
[0];
1404 nc_name
= samdb_result_dn(service
->samdb
, tmp_ctx
, cross_ref
,
1407 DEBUG(1, (__location__
": failed to find nCName "
1408 "attribute of object %s\n",
1409 ldb_dn_get_linearized(cross_ref
->dn
)));
1411 talloc_free(tmp_ctx
);
1412 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1415 if (true) { /* TODO: site contains 1+ DCs with full replicas of
1417 vertex
->color
= RED
;
1418 } else if (true) { /* TODO: site contains 1+ partial replicas of
1420 vertex
->color
= BLACK
;
1422 vertex
->color
= WHITE
;
1426 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
1428 DEBUG(1, (__location__
": failed to find our own local DC's "
1431 talloc_free(tmp_ctx
);
1432 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1434 site_guid
= samdb_result_guid(site
, "objectGUID");
1436 site_vertex
= kcctpl_find_vertex_by_guid(graph
, site_guid
);
1438 DEBUG(1, (__location__
": failed to find a vertex edge with "
1439 "GUID=%s\n", GUID_string(tmp_ctx
, &site_guid
)));
1441 talloc_free(tmp_ctx
);
1442 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1445 partial_replica_okay
= (site_vertex
->color
== BLACK
);
1447 cr_flags
= ldb_msg_find_attr_as_int64(cross_ref
, "systemFlags", 0);
1449 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1450 struct kcctpl_vertex
*vertex
;
1451 struct ldb_dn
*transports_dn
;
1452 const char * const attrs
[] = { "objectGUID", "name",
1453 "transportAddressAttribute",
1457 vertex
= &graph
->vertices
.data
[i
];
1459 transports_dn
= kcctpl_transports_dn(service
->samdb
, tmp_ctx
);
1460 if (!transports_dn
) {
1461 DEBUG(1, (__location__
": failed to find our own "
1462 "Inter-Site Transports DN\n"));
1464 talloc_free(tmp_ctx
);
1465 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1468 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, transports_dn
,
1469 LDB_SCOPE_ONELEVEL
, attrs
,
1470 "objectClass=interSiteTransport");
1471 if (ret
!= LDB_SUCCESS
) {
1472 DEBUG(1, (__location__
": failed to find "
1473 "interSiteTransport objects under %s: %s\n",
1474 ldb_dn_get_linearized(transports_dn
),
1475 ldb_strerror(ret
)));
1477 talloc_free(tmp_ctx
);
1478 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1481 for (j
= 0; j
< res
->count
; j
++) {
1482 struct ldb_message
*transport
, *bridgehead
;
1483 const char *transport_name
;
1484 struct GUID transport_guid
, *new_data
;
1487 transport
= res
->msgs
[j
];
1489 transport_name
= ldb_msg_find_attr_as_string(transport
,
1491 if (!transport_name
) {
1492 DEBUG(1, (__location__
": failed to find name "
1493 "attribute of object %s\n",
1494 ldb_dn_get_linearized(transport
->dn
)));
1496 talloc_free(tmp_ctx
);
1497 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1500 transport_guid
= samdb_result_guid(transport
,
1503 if (site_vertex
->color
== RED
&&
1504 strncmp(transport_name
, "IP", 2) != 0 &&
1505 (cr_flags
& FLAG_CR_NTDS_DOMAIN
)) {
1509 if (!kcctpl_find_edge_by_vertex_guid(graph
,
1514 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
1516 cross_ref
, transport
,
1517 partial_replica_okay
,
1520 if (NT_STATUS_IS_ERR(status
)) {
1521 DEBUG(1, (__location__
": failed to get a "
1522 "bridgehead DC: %s\n",
1523 nt_errstr(status
)));
1525 talloc_free(tmp_ctx
);
1529 found_failed_dcs
= true;
1533 new_data
= talloc_realloc(vertex
,
1534 vertex
->accept_red_red
.data
,
1536 vertex
->accept_red_red
.count
+ 1);
1537 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1538 new_data
[vertex
->accept_red_red
.count
+ 1] = transport_guid
;
1539 vertex
->accept_red_red
.data
= new_data
;
1540 vertex
->accept_red_red
.count
++;
1542 new_data
= talloc_realloc(vertex
,
1543 vertex
->accept_black
.data
,
1545 vertex
->accept_black
.count
+ 1);
1546 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1547 new_data
[vertex
->accept_black
.count
+ 1] = transport_guid
;
1548 vertex
->accept_black
.data
= new_data
;
1549 vertex
->accept_black
.count
++;
1553 *_found_failed_dcs
= found_failed_dcs
;
1554 talloc_free(tmp_ctx
);
1555 return NT_STATUS_OK
;
1559 * setup the fields of the vertices that are relevant to Phase I (Dijkstra's
1560 * Algorithm). for each vertex, set up its cost, root vertex and component. this
1561 * defines the shortest-path forest structures.
1563 static void kcctpl_setup_vertices(struct kcctpl_graph
*graph
)
1567 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1568 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
1570 if (vertex
->color
== WHITE
) {
1571 vertex
->repl_info
.cost
= UINT32_MAX
;
1572 vertex
->root_id
= vertex
->component_id
= GUID_zero();
1574 vertex
->repl_info
.cost
= 0;
1575 vertex
->root_id
= vertex
->component_id
= vertex
->id
;
1578 vertex
->repl_info
.interval
= 0;
1579 vertex
->repl_info
.options
= 0xFFFFFFFF;
1580 ZERO_STRUCT(vertex
->repl_info
.schedule
);
1581 vertex
->demoted
= false;
1586 * demote one vertex if necessary.
1588 static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex
*vertex
,
1591 if (vertex
->color
== WHITE
) {
1595 if (!kcctpl_guid_list_contains(vertex
->accept_black
, type
) &&
1596 !kcctpl_guid_list_contains(vertex
->accept_red_red
, type
)) {
1597 vertex
->repl_info
.cost
= UINT32_MAX
;
1598 vertex
->root_id
= GUID_zero();
1599 vertex
->demoted
= true;
1604 * clear the demoted state of a vertex.
1606 static void kcctpl_undemote_one_vertex(struct kcctpl_vertex
*vertex
)
1608 if (vertex
->color
== WHITE
) {
1612 vertex
->repl_info
.cost
= 0;
1613 vertex
->root_id
= vertex
->id
;
1614 vertex
->demoted
= false;
1618 * returns the id of the component containing 'vertex' by traversing the up-tree
1619 * implied by the component pointers.
1621 static struct GUID
kcctpl_get_component_id(struct kcctpl_graph
*graph
,
1622 struct kcctpl_vertex
*vertex
)
1624 struct kcctpl_vertex
*u
;
1628 while (!GUID_equal(&u
->component_id
, &u
->id
)) {
1629 u
= kcctpl_find_vertex_by_guid(graph
, u
->component_id
);
1635 while (!GUID_equal(&u
->component_id
, &u
->id
)) {
1636 struct kcctpl_vertex
*w
;
1638 w
= kcctpl_find_vertex_by_guid(graph
, u
->component_id
);
1639 u
->component_id
= root
;
1647 * copy all spanning tree edges from 'output_edges' that contain the vertex for
1648 * DCs in the local DC's site.
1650 static NTSTATUS
kcctpl_copy_output_edges(struct kccsrv_service
*service
,
1651 TALLOC_CTX
*mem_ctx
,
1652 struct kcctpl_graph
*graph
,
1653 struct kcctpl_multi_edge_list output_edges
,
1654 struct kcctpl_multi_edge_list
*_copy
)
1656 struct kcctpl_multi_edge_list copy
;
1657 TALLOC_CTX
*tmp_ctx
;
1658 struct ldb_message
*site
;
1659 struct GUID site_guid
;
1664 tmp_ctx
= talloc_new(service
);
1665 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1667 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
1669 DEBUG(1, (__location__
": failed to find our own local DC's "
1672 talloc_free(tmp_ctx
);
1673 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1675 site_guid
= samdb_result_guid(site
, "objectGUID");
1677 for (i
= 0; i
< output_edges
.count
; i
++) {
1678 struct kcctpl_multi_edge
*edge
;
1679 struct kcctpl_vertex
*vertex1
, *vertex2
;
1681 edge
= &output_edges
.data
[i
];
1683 vertex1
= kcctpl_find_vertex_by_guid(graph
,
1684 edge
->vertex_ids
.data
[0]);
1686 DEBUG(1, (__location__
": failed to find vertex %s\n",
1687 GUID_string(tmp_ctx
,
1688 &edge
->vertex_ids
.data
[0])));
1689 talloc_free(tmp_ctx
);
1690 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1693 vertex2
= kcctpl_find_vertex_by_guid(graph
,
1694 edge
->vertex_ids
.data
[1]);
1696 DEBUG(1, (__location__
": failed to find vertex %s\n",
1697 GUID_string(tmp_ctx
,
1698 &edge
->vertex_ids
.data
[1])));
1699 talloc_free(tmp_ctx
);
1700 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1703 if (GUID_equal(&vertex1
->id
, &site_guid
) ||
1704 GUID_equal(&vertex2
->id
, &site_guid
)) {
1705 struct kcctpl_multi_edge
*new_data
;
1707 if ((vertex1
->color
== BLACK
||
1708 vertex2
->color
== BLACK
) &&
1709 vertex1
->dist_to_red
!= UINT32_MAX
) {
1711 edge
->directed
= true;
1713 if (vertex2
->dist_to_red
<
1714 vertex1
->dist_to_red
) {
1717 tmp
= edge
->vertex_ids
.data
[0];
1718 edge
->vertex_ids
.data
[0] = edge
->vertex_ids
.data
[1];
1719 edge
->vertex_ids
.data
[1] = tmp
;
1723 new_data
= talloc_realloc(tmp_ctx
, copy
.data
,
1724 struct kcctpl_multi_edge
,
1726 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1727 new_data
[copy
.count
+ 1] = *edge
;
1728 copy
.data
= new_data
;
1733 talloc_steal(mem_ctx
, copy
.data
);
1734 talloc_free(tmp_ctx
);
1736 return NT_STATUS_OK
;
1740 * build the initial sequence for use with Dijkstra's algorithm. it will contain
1741 * the red and black vertices as root vertices, unless these vertices accept no
1742 * edges of the current 'type', or unless black vertices are not being
1745 static NTSTATUS
kcctpl_setup_dijkstra(TALLOC_CTX
*mem_ctx
,
1746 struct kcctpl_graph
*graph
,
1747 struct GUID type
, bool include_black
,
1748 struct kcctpl_vertex_list
*_vertices
)
1750 struct kcctpl_vertex_list vertices
;
1753 kcctpl_setup_vertices(graph
);
1755 ZERO_STRUCT(vertices
);
1757 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
1758 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
1760 if (vertex
->color
== WHITE
) {
1764 if ((vertex
->color
== BLACK
&& !include_black
) ||
1765 !kcctpl_guid_list_contains(vertex
->accept_black
, type
) ||
1766 !kcctpl_guid_list_contains(vertex
->accept_red_red
, type
)) {
1767 vertex
->repl_info
.cost
= UINT32_MAX
;
1768 vertex
->root_id
= GUID_zero();
1769 vertex
->demoted
= true;
1771 struct kcctpl_vertex
*new_data
;
1773 new_data
= talloc_realloc(mem_ctx
, vertices
.data
,
1774 struct kcctpl_vertex
,
1775 vertices
.count
+ 1);
1776 NT_STATUS_HAVE_NO_MEMORY(new_data
);
1777 new_data
[vertices
.count
] = *vertex
;
1778 vertices
.data
= new_data
;
1783 *_vertices
= vertices
;
1784 return NT_STATUS_OK
;
1788 * merge schedules, replication intervals, options and costs.
1790 static bool kcctpl_combine_repl_info(struct kcctpl_graph
*graph
,
1791 struct kcctpl_repl_info
*ria
,
1792 struct kcctpl_repl_info
*rib
,
1793 struct kcctpl_repl_info
*ric
)
1795 uint8_t schedule
[84];
1800 is_available
= false;
1801 for (i
= 0; i
< 84; i
++) {
1802 schedule
[i
] = ria
->schedule
[i
] & rib
->schedule
[i
];
1804 if (schedule
[i
] == 1) {
1805 is_available
= true;
1808 if (!is_available
) {
1812 ric_cost
= ria
->cost
+ rib
->cost
;
1813 ric
->cost
= (ric_cost
< 0) ? UINT32_MAX
: ric_cost
;
1815 ric
->interval
= MAX(ria
->interval
, rib
->interval
);
1816 ric
->options
= ria
->options
& rib
->options
;
1817 memcpy(&ric
->schedule
, &schedule
, 84);
1823 * helper function for Dijkstra's algorithm. a new path has been found from a
1824 * root vertex to vertex 'vertex2'. this path is ('vertex1->root, ..., vertex1,
1825 * vertex2'). 'edge' is the edge connecting 'vertex1' and 'vertex2'. if this new
1826 * path is better (in this case cheaper, or has a longer schedule), update
1827 * 'vertex2' to use the new path.
1829 static NTSTATUS
kcctpl_try_new_path(TALLOC_CTX
*mem_ctx
,
1830 struct kcctpl_graph
*graph
,
1831 struct kcctpl_vertex_list vertices
,
1832 struct kcctpl_vertex
*vertex1
,
1833 struct kcctpl_multi_edge
*edge
,
1834 struct kcctpl_vertex
*vertex2
)
1836 struct kcctpl_repl_info new_repl_info
;
1838 uint32_t i
, new_duration
, old_duration
;
1840 ZERO_STRUCT(new_repl_info
);
1842 intersect
= kcctpl_combine_repl_info(graph
, &vertex1
->repl_info
,
1843 &edge
->repl_info
, &new_repl_info
);
1845 if (new_repl_info
.cost
> vertex2
->repl_info
.cost
) {
1846 return NT_STATUS_OK
;
1849 if (new_repl_info
.cost
< vertex2
->repl_info
.cost
&& !intersect
) {
1850 return NT_STATUS_OK
;
1853 new_duration
= old_duration
= 0;
1854 for (i
= 0; i
< 84; i
++) {
1855 if (new_repl_info
.schedule
[i
] == 1) {
1859 if (vertex2
->repl_info
.schedule
[i
] == 1) {
1864 if (new_repl_info
.cost
< vertex2
->repl_info
.cost
||
1865 new_duration
> old_duration
) {
1866 struct kcctpl_vertex
*new_data
;
1868 vertex2
->root_id
= vertex1
->root_id
;
1869 vertex2
->component_id
= vertex1
->component_id
;
1870 vertex2
->repl_info
= new_repl_info
;
1872 new_data
= talloc_realloc(mem_ctx
, vertices
.data
,
1873 struct kcctpl_vertex
,
1874 vertices
.count
+ 1);
1875 NT_STATUS_HAVE_NO_MEMORY(new_data
);
1876 new_data
[vertices
.count
+ 1] = *vertex2
;
1877 vertices
.data
= new_data
;
1881 return NT_STATUS_OK
;
1885 * run Dijkstra's algorithm with the red (and possibly black) vertices as the
1886 * root vertices, and build up a shortest-path forest.
1888 static NTSTATUS
kcctpl_dijkstra(struct kcctpl_graph
*graph
, struct GUID type
,
1891 TALLOC_CTX
*tmp_ctx
;
1892 struct kcctpl_vertex_list vertices
;
1895 tmp_ctx
= talloc_new(graph
);
1896 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
1898 status
= kcctpl_setup_dijkstra(tmp_ctx
, graph
, type
, include_black
,
1900 if (NT_STATUS_IS_ERR(status
)) {
1901 DEBUG(1, (__location__
": failed to build the initial sequence "
1902 "for Dijkstra's algorithm: %s\n", nt_errstr(status
)));
1904 talloc_free(tmp_ctx
);
1908 while (vertices
.count
> 0) {
1909 uint32_t minimum_cost
, minimum_index
, i
;
1910 struct kcctpl_vertex
*minimum_vertex
, *new_data
;
1912 minimum_cost
= UINT32_MAX
;
1914 minimum_vertex
= NULL
;
1915 for (i
= 0; i
< vertices
.count
; i
++) {
1916 struct kcctpl_vertex
*vertex
= &vertices
.data
[i
];
1918 if (vertex
->repl_info
.cost
< minimum_cost
) {
1919 minimum_cost
= vertex
->repl_info
.cost
;
1920 minimum_vertex
= vertex
;
1922 } else if (vertex
->repl_info
.cost
== minimum_cost
&&
1923 GUID_compare(&vertex
->id
,
1924 &minimum_vertex
->id
) < 0) {
1925 minimum_vertex
= vertex
;
1930 if (minimum_index
< vertices
.count
- 1) {
1931 memcpy(&vertices
.data
[minimum_index
+ 1],
1932 &vertices
.data
[minimum_index
],
1933 vertices
.count
- minimum_index
- 1);
1935 new_data
= talloc_realloc(tmp_ctx
, vertices
.data
,
1936 struct kcctpl_vertex
,
1937 vertices
.count
- 1);
1938 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
1939 talloc_free(vertices
.data
);
1940 vertices
.data
= new_data
;
1943 for (i
= 0; i
< graph
->edges
.count
; i
++) {
1944 struct kcctpl_multi_edge
*edge
= &graph
->edges
.data
[i
];
1946 if (kcctpl_guid_list_contains(minimum_vertex
->edge_ids
,
1950 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
1951 struct GUID vertex_id
;
1952 struct kcctpl_vertex
*vertex
;
1954 vertex_id
= edge
->vertex_ids
.data
[j
];
1955 vertex
= kcctpl_find_vertex_by_guid(graph
,
1958 DEBUG(1, (__location__
1961 GUID_string(tmp_ctx
,
1964 talloc_free(tmp_ctx
);
1965 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
1968 kcctpl_try_new_path(tmp_ctx
, graph
,
1977 talloc_free(tmp_ctx
);
1978 return NT_STATUS_OK
;
1982 * add an edge to the list of edges that will be processed with Kruskal's. the
1983 * endpoints are in fact the root of the vertices to pass in, so the endpoints
1984 * are always colored vertices.
1986 static NTSTATUS
kcctpl_add_int_edge(TALLOC_CTX
*mem_ctx
,
1987 struct kcctpl_graph
*graph
,
1988 struct kcctpl_internal_edge_list internal_edges
,
1989 struct kcctpl_multi_edge
*edge
,
1990 struct kcctpl_vertex
*vertex1
,
1991 struct kcctpl_vertex
*vertex2
)
1993 struct kcctpl_vertex
*root1
, *root2
;
1994 bool red_red
, found
;
1995 struct kcctpl_repl_info repl_info1
, repl_info2
;
1996 struct kcctpl_internal_edge new_internal_edge
, *new_data
;
1999 root1
= kcctpl_find_vertex_by_guid(graph
, vertex1
->root_id
);
2001 TALLOC_CTX
*tmp_ctx
= talloc_new(graph
);
2002 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2004 DEBUG(1, (__location__
": failed to find vertex %s\n",
2005 GUID_string(tmp_ctx
, &vertex1
->root_id
)));
2007 talloc_free(tmp_ctx
);
2008 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2011 root2
= kcctpl_find_vertex_by_guid(graph
, vertex2
->root_id
);
2013 TALLOC_CTX
*tmp_ctx
= talloc_new(graph
);
2014 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2016 DEBUG(1, (__location__
": failed to find vertex %s\n",
2017 GUID_string(tmp_ctx
, &vertex2
->root_id
)));
2019 talloc_free(tmp_ctx
);
2020 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2023 red_red
= (root1
->color
== RED
&& root2
->color
== RED
);
2026 if (!kcctpl_guid_list_contains(root1
->accept_red_red
,
2028 !kcctpl_guid_list_contains(root2
->accept_red_red
,
2030 return NT_STATUS_OK
;
2032 } else if (!kcctpl_guid_list_contains(root1
->accept_black
,
2034 !kcctpl_guid_list_contains(root2
->accept_black
,
2036 return NT_STATUS_OK
;
2039 if (!kcctpl_combine_repl_info(graph
, &vertex1
->repl_info
,
2040 &vertex2
->repl_info
, &repl_info1
) ||
2041 !kcctpl_combine_repl_info(graph
, &repl_info1
, &edge
->repl_info
,
2043 return NT_STATUS_OK
;
2046 new_internal_edge
.v1id
= root1
->id
;
2047 new_internal_edge
.v2id
= root2
->id
;
2048 new_internal_edge
.red_red
= red_red
;
2049 new_internal_edge
.repl_info
= repl_info2
;
2050 new_internal_edge
.type
= edge
->type
;
2052 if (GUID_compare(&new_internal_edge
.v1id
,
2053 &new_internal_edge
.v2id
) > 0) {
2054 struct GUID tmp_guid
= new_internal_edge
.v1id
;
2056 new_internal_edge
.v1id
= new_internal_edge
.v2id
;
2057 new_internal_edge
.v2id
= tmp_guid
;
2061 for (i
= 0; i
< internal_edges
.count
; i
++) {
2062 struct kcctpl_internal_edge
*ie
= &internal_edges
.data
[i
];
2064 if (kcctpl_internal_edge_equal(ie
, &new_internal_edge
)) {
2069 return NT_STATUS_OK
;
2072 new_data
= talloc_realloc(mem_ctx
, internal_edges
.data
,
2073 struct kcctpl_internal_edge
,
2074 internal_edges
.count
+ 1);
2075 NT_STATUS_HAVE_NO_MEMORY(new_data
);
2076 new_data
[internal_edges
.count
+ 1] = new_internal_edge
;
2077 internal_edges
.data
= new_data
;
2078 internal_edges
.count
++;
2080 return NT_STATUS_OK
;
2084 * after running Dijkstra's algorithm, this function examines a multi-edge and
2085 * adds internal edges between every tree connected by this edge.
2087 static NTSTATUS
kcctpl_process_edge(TALLOC_CTX
*mem_ctx
,
2088 struct kcctpl_graph
*graph
,
2089 struct kcctpl_multi_edge
*edge
,
2090 struct kcctpl_internal_edge_list internal_edges
)
2092 TALLOC_CTX
*tmp_ctx
;
2093 struct kcctpl_vertex_list vertices
;
2095 struct kcctpl_vertex
*best_vertex
;
2097 ZERO_STRUCT(vertices
);
2099 tmp_ctx
= talloc_new(mem_ctx
);
2100 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2102 for (i
= 0; i
< edge
->vertex_ids
.count
; i
++) {
2104 struct kcctpl_vertex
*vertex
, *new_data
;
2106 id
= edge
->vertex_ids
.data
[i
];
2108 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2110 DEBUG(1, (__location__
": failed to find vertex %s\n",
2111 GUID_string(tmp_ctx
, &id
)));
2113 talloc_free(tmp_ctx
);
2114 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2117 new_data
= talloc_realloc(tmp_ctx
, vertices
.data
,
2118 struct kcctpl_vertex
,
2119 vertices
.count
+ 1);
2120 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
2121 new_data
[vertices
.count
] = *vertex
;
2122 vertices
.data
= new_data
;
2126 qsort(vertices
.data
, vertices
.count
, sizeof(struct kcctpl_vertex
),
2127 kcctpl_sort_vertices
);
2129 best_vertex
= &vertices
.data
[0];
2131 for (i
= 0; i
< edge
->vertex_ids
.count
; i
++) {
2132 struct GUID id
, empty_id
= GUID_zero();
2133 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2135 id
= edge
->vertex_ids
.data
[i
];
2137 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2139 DEBUG(1, (__location__
": failed to find vertex %s\n",
2140 GUID_string(tmp_ctx
, &id
)));
2142 talloc_free(tmp_ctx
);
2143 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2146 if (!GUID_equal(&vertex
->component_id
, &empty_id
) &&
2147 !GUID_equal(&vertex
->root_id
, &empty_id
)) {
2151 if (!GUID_equal(&best_vertex
->component_id
,
2153 !GUID_equal(&best_vertex
->root_id
, &empty_id
) &&
2154 !GUID_equal(&vertex
->component_id
, &empty_id
) &&
2155 !GUID_equal(&vertex
->root_id
, &empty_id
) &&
2156 !GUID_equal(&best_vertex
->component_id
,
2157 &vertex
->component_id
)) {
2160 status
= kcctpl_add_int_edge(mem_ctx
, graph
,
2164 if (NT_STATUS_IS_ERR(status
)) {
2165 DEBUG(1, (__location__
": failed to add an "
2166 "internal edge for %s: %s\n",
2167 GUID_string(tmp_ctx
, &vertex
->id
),
2168 nt_errstr(status
)));
2169 talloc_free(tmp_ctx
);
2175 talloc_free(tmp_ctx
);
2176 return NT_STATUS_OK
;
2180 * after running Dijkstra's algorithm to determine the shortest-path forest,
2181 * examine all edges in this edge set. find all inter-tree edges, from which to
2182 * build the list of 'internal edges', which will later be passed on to
2183 * Kruskal's algorithm.
2185 static NTSTATUS
kcctpl_process_edge_set(TALLOC_CTX
*mem_ctx
,
2186 struct kcctpl_graph
*graph
,
2187 struct kcctpl_multi_edge_set
*set
,
2188 struct kcctpl_internal_edge_list internal_edges
)
2193 for (i
= 0; i
< graph
->edges
.count
; i
++) {
2194 struct kcctpl_multi_edge
*edge
;
2198 edge
= &graph
->edges
.data
[i
];
2200 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
2202 struct kcctpl_vertex
*vertex
;
2204 id
= edge
->vertex_ids
.data
[j
];
2206 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2208 TALLOC_CTX
*tmp_ctx
;
2210 tmp_ctx
= talloc_new(mem_ctx
);
2211 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2213 DEBUG(1, (__location__
": failed to "
2215 GUID_string(tmp_ctx
, &id
)));
2217 talloc_free(tmp_ctx
);
2218 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2221 kcctpl_check_demote_one_vertex(vertex
,
2225 status
= kcctpl_process_edge(mem_ctx
, graph
, edge
,
2227 if (NT_STATUS_IS_ERR(status
)) {
2228 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2229 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2231 DEBUG(1, (__location__
": failed to process "
2233 GUID_string(tmp_ctx
, &edge
->id
),
2234 nt_errstr(status
)));
2236 talloc_free(tmp_ctx
);
2240 for (j
= 0; j
< edge
->vertex_ids
.count
; j
++) {
2242 struct kcctpl_vertex
*vertex
;
2244 id
= edge
->vertex_ids
.data
[j
];
2246 vertex
= kcctpl_find_vertex_by_guid(graph
, id
);
2248 TALLOC_CTX
*tmp_ctx
;
2250 tmp_ctx
= talloc_new(mem_ctx
);
2251 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2253 DEBUG(1, (__location__
": failed to "
2255 GUID_string(tmp_ctx
, &id
)));
2257 talloc_free(tmp_ctx
);
2258 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2261 kcctpl_undemote_one_vertex(vertex
);
2265 for (i
= 0; i
< graph
->edges
.count
; i
++) {
2266 struct kcctpl_multi_edge
*edge
= &graph
->edges
.data
[i
];
2268 if (kcctpl_guid_list_contains(set
->edge_ids
,
2272 status
= kcctpl_process_edge(mem_ctx
, graph
,
2275 if (NT_STATUS_IS_ERR(status
)) {
2276 TALLOC_CTX
*tmp_ctx
;
2278 tmp_ctx
= talloc_new(mem_ctx
);
2279 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2281 DEBUG(1, (__location__
": failed to "
2282 "process edge %s: %s\n",
2283 GUID_string(tmp_ctx
,
2285 nt_errstr(status
)));
2287 talloc_free(tmp_ctx
);
2294 return NT_STATUS_OK
;
2298 * a new edge, 'internal_edge', has been found for the spanning tree edge. add
2299 * this edge to the list of output edges.
2301 static NTSTATUS
kcctpl_add_out_edge(TALLOC_CTX
*mem_ctx
,
2302 struct kcctpl_graph
*graph
,
2303 struct kcctpl_multi_edge_list output_edges
,
2304 struct kcctpl_internal_edge
*internal_edge
)
2306 struct kcctpl_vertex
*vertex1
, *vertex2
;
2307 TALLOC_CTX
*tmp_ctx
;
2308 struct kcctpl_multi_edge
*new_edge
, *new_data
;
2309 struct GUID
*new_data_id
;
2311 tmp_ctx
= talloc_new(mem_ctx
);
2312 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2314 vertex1
= kcctpl_find_vertex_by_guid(graph
, internal_edge
->v1id
);
2316 DEBUG(1, (__location__
": failed to find vertex %s\n",
2317 GUID_string(tmp_ctx
, &internal_edge
->v1id
)));
2319 talloc_free(tmp_ctx
);
2320 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2323 vertex2
= kcctpl_find_vertex_by_guid(graph
, internal_edge
->v2id
);
2325 DEBUG(1, (__location__
": failed to find vertex %s\n",
2326 GUID_string(tmp_ctx
, &internal_edge
->v2id
)));
2328 talloc_free(tmp_ctx
);
2329 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2332 new_edge
= talloc(tmp_ctx
, struct kcctpl_multi_edge
);
2333 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge
, tmp_ctx
);
2335 new_edge
->id
= GUID_random(); /* TODO: what should be new_edge->GUID? */
2336 new_edge
->directed
= false;
2338 new_edge
->vertex_ids
.data
= talloc_array(new_edge
, struct GUID
, 2);
2339 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge
->vertex_ids
.data
, tmp_ctx
);
2341 new_edge
->vertex_ids
.data
[0] = vertex1
->id
;
2342 new_edge
->vertex_ids
.data
[1] = vertex2
->id
;
2343 new_edge
->vertex_ids
.count
= 2;
2345 new_edge
->type
= internal_edge
->type
;
2346 new_edge
->repl_info
= internal_edge
->repl_info
;
2348 new_data
= talloc_realloc(tmp_ctx
, output_edges
.data
,
2349 struct kcctpl_multi_edge
,
2350 output_edges
.count
+ 1);
2351 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
2352 new_data
[output_edges
.count
+ 1] = *new_edge
;
2353 output_edges
.data
= new_data
;
2354 output_edges
.count
++;
2356 new_data_id
= talloc_realloc(vertex1
, vertex1
->edge_ids
.data
,
2357 struct GUID
, vertex1
->edge_ids
.count
);
2358 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id
, tmp_ctx
);
2359 new_data_id
[vertex1
->edge_ids
.count
] = new_edge
->id
;
2360 talloc_free(vertex1
->edge_ids
.data
);
2361 vertex1
->edge_ids
.data
= new_data_id
;
2362 vertex1
->edge_ids
.count
++;
2364 new_data_id
= talloc_realloc(vertex2
, vertex2
->edge_ids
.data
,
2365 struct GUID
, vertex2
->edge_ids
.count
);
2366 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id
, tmp_ctx
);
2367 new_data_id
[vertex2
->edge_ids
.count
] = new_edge
->id
;
2368 talloc_free(vertex2
->edge_ids
.data
);
2369 vertex2
->edge_ids
.data
= new_data_id
;
2370 vertex2
->edge_ids
.count
++;
2372 talloc_steal(graph
, new_edge
);
2373 talloc_steal(mem_ctx
, output_edges
.data
);
2374 talloc_free(tmp_ctx
);
2375 return NT_STATUS_OK
;
2379 * run Kruskal's minimum-cost spanning tree algorithm on the internal edges
2380 * (that represent shortest paths in the original graph between colored
2383 static NTSTATUS
kcctpl_kruskal(TALLOC_CTX
*mem_ctx
, struct kcctpl_graph
*graph
,
2384 struct kcctpl_internal_edge_list internal_edges
,
2385 struct kcctpl_multi_edge_list
*_output_edges
)
2387 uint32_t i
, num_expected_tree_edges
, cst_edges
;
2388 struct kcctpl_multi_edge_list output_edges
;
2390 num_expected_tree_edges
= 0;
2391 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2392 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2394 talloc_free(vertex
->edge_ids
.data
);
2395 ZERO_STRUCT(vertex
->edge_ids
);
2397 if (vertex
->color
== RED
|| vertex
->color
== WHITE
) {
2398 num_expected_tree_edges
++;
2402 qsort(internal_edges
.data
, internal_edges
.count
,
2403 sizeof(struct kcctpl_internal_edge
), kcctpl_sort_internal_edges
);
2407 ZERO_STRUCT(output_edges
);
2409 while (internal_edges
.count
> 0 &&
2410 cst_edges
< num_expected_tree_edges
) {
2411 struct kcctpl_internal_edge
*edge
, *new_data
;
2412 struct kcctpl_vertex
*vertex1
, *vertex2
;
2413 struct GUID comp1
, comp2
;
2415 edge
= &internal_edges
.data
[0];
2417 vertex1
= kcctpl_find_vertex_by_guid(graph
, edge
->v1id
);
2419 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2420 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2422 DEBUG(1, (__location__
": failed to find vertex %s\n",
2423 GUID_string(tmp_ctx
, &edge
->v1id
)));
2425 talloc_free(tmp_ctx
);
2426 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2429 vertex2
= kcctpl_find_vertex_by_guid(graph
, edge
->v2id
);
2431 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2432 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2434 DEBUG(1, (__location__
": failed to find vertex %s\n",
2435 GUID_string(tmp_ctx
, &edge
->v2id
)));
2437 talloc_free(tmp_ctx
);
2438 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2441 comp1
= kcctpl_get_component_id(graph
, vertex1
);
2442 comp2
= kcctpl_get_component_id(graph
, vertex2
);
2444 if (!GUID_equal(&comp1
, &comp2
)) {
2446 struct kcctpl_vertex
*vertex
;
2450 status
= kcctpl_add_out_edge(mem_ctx
, graph
,
2451 output_edges
, edge
);
2452 if (NT_STATUS_IS_ERR(status
)) {
2453 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2454 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2456 DEBUG(1, (__location__
": failed to add an "
2457 "output edge between %s and %s: %s\n",
2458 GUID_string(tmp_ctx
, &edge
->v1id
),
2459 GUID_string(tmp_ctx
, &edge
->v2id
),
2460 nt_errstr(status
)));
2462 talloc_free(tmp_ctx
);
2466 vertex
= kcctpl_find_vertex_by_guid(graph
, comp1
);
2468 TALLOC_CTX
*tmp_ctx
= talloc_new(mem_ctx
);
2469 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2471 DEBUG(1, (__location__
": failed to find "
2472 "vertex %s\n", GUID_string(tmp_ctx
,
2475 talloc_free(tmp_ctx
);
2476 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2478 vertex
->component_id
= comp2
;
2481 internal_edges
.data
= internal_edges
.data
+ 1;
2482 new_data
= talloc_realloc(mem_ctx
, internal_edges
.data
,
2483 struct kcctpl_internal_edge
,
2484 internal_edges
.count
- 1);
2485 NT_STATUS_HAVE_NO_MEMORY(new_data
);
2486 talloc_free(internal_edges
.data
);
2487 internal_edges
.data
= new_data
;
2488 internal_edges
.count
--;
2491 *_output_edges
= output_edges
;
2492 return NT_STATUS_OK
;
2496 * count the number of components. a component is considered to be a bunch of
2497 * colored vertices that are connected by the spanning tree. vertices whose
2498 * component ID is the same as their vertex ID are the root of the connected
2501 static uint32_t kcctpl_count_components(struct kcctpl_graph
*graph
)
2503 uint32_t num_components
= 0, i
;
2505 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2506 struct kcctpl_vertex
*vertex
;
2507 struct GUID component_id
;
2509 vertex
= &graph
->vertices
.data
[i
];
2511 if (vertex
->color
== WHITE
) {
2515 component_id
= kcctpl_get_component_id(graph
, vertex
);
2516 if (GUID_equal(&component_id
, &vertex
->id
)) {
2517 vertex
->component_index
= num_components
;
2522 return num_components
;
2526 * calculate the spanning tree and return the edges that include the vertex for
2529 static NTSTATUS
kcctpl_get_spanning_tree_edges(struct kccsrv_service
*service
,
2530 TALLOC_CTX
*mem_ctx
,
2531 struct kcctpl_graph
*graph
,
2532 uint32_t *_component_count
,
2533 struct kcctpl_multi_edge_list
*_st_edge_list
)
2535 TALLOC_CTX
*tmp_ctx
;
2536 struct kcctpl_internal_edge_list internal_edges
;
2537 uint32_t i
, component_count
;
2539 struct kcctpl_multi_edge_list output_edges
, st_edge_list
;
2541 ZERO_STRUCT(internal_edges
);
2543 tmp_ctx
= talloc_new(mem_ctx
);
2544 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2546 for (i
= 0; i
< graph
->edge_sets
.count
; i
++) {
2547 struct kcctpl_multi_edge_set
*set
;
2548 struct GUID edge_type
;
2551 set
= &graph
->edge_sets
.data
[i
];
2553 edge_type
= GUID_zero();
2555 for (j
= 0; j
< graph
->vertices
.count
; j
++) {
2556 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[j
];
2558 talloc_free(vertex
->edge_ids
.data
);
2559 ZERO_STRUCT(vertex
->edge_ids
.data
);
2562 for (j
= 0; j
< set
->edge_ids
.count
; j
++) {
2563 struct GUID edge_id
;
2564 struct kcctpl_multi_edge
*edge
;
2567 edge_id
= set
->edge_ids
.data
[j
];
2568 edge
= kcctpl_find_edge_by_guid(graph
, edge_id
);
2570 DEBUG(1, (__location__
": failed to find a "
2571 "graph edge with ID=%s\n",
2572 GUID_string(tmp_ctx
, &edge_id
)));
2574 talloc_free(tmp_ctx
);
2575 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2578 edge_type
= edge
->type
;
2580 for (k
= 0; k
< edge
->vertex_ids
.count
; k
++) {
2581 struct GUID vertex_id
, *new_data
;
2582 struct kcctpl_vertex
*vertex
;
2584 vertex_id
= edge
->vertex_ids
.data
[k
];
2585 vertex
= kcctpl_find_vertex_by_guid(graph
,
2588 DEBUG(1, (__location__
": failed to "
2589 "find a graph vertex with "
2591 GUID_string(tmp_ctx
,
2594 talloc_free(tmp_ctx
);
2595 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2598 new_data
= talloc_realloc(tmp_ctx
,
2599 vertex
->edge_ids
.data
,
2601 vertex
->edge_ids
.count
+ 1);
2602 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
,
2604 new_data
[vertex
->edge_ids
.count
] = edge
->id
;
2605 vertex
->edge_ids
.data
= new_data
;
2606 vertex
->edge_ids
.count
++;
2610 status
= kcctpl_dijkstra(graph
, edge_type
, false);
2611 if (NT_STATUS_IS_ERR(status
)) {
2612 DEBUG(1, (__location__
": failed to run Dijkstra's "
2613 "algorithm: %s\n", nt_errstr(status
)));
2615 talloc_free(tmp_ctx
);
2619 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, set
,
2621 if (NT_STATUS_IS_ERR(status
)) {
2622 DEBUG(1, (__location__
": failed to process edge set "
2623 "%s: %s\n", GUID_string(tmp_ctx
, &set
->id
),
2624 nt_errstr(status
)));
2626 talloc_free(tmp_ctx
);
2630 status
= kcctpl_dijkstra(graph
, edge_type
, true);
2631 if (NT_STATUS_IS_ERR(status
)) {
2632 DEBUG(1, (__location__
": failed to run Dijkstra's "
2633 "algorithm: %s\n", nt_errstr(status
)));
2635 talloc_free(tmp_ctx
);
2639 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, set
,
2641 if (NT_STATUS_IS_ERR(status
)) {
2642 DEBUG(1, (__location__
": failed to process edge set "
2643 "%s: %s\n", GUID_string(tmp_ctx
, &set
->id
),
2644 nt_errstr(status
)));
2646 talloc_free(tmp_ctx
);
2651 kcctpl_setup_vertices(graph
);
2653 status
= kcctpl_process_edge_set(tmp_ctx
, graph
, NULL
, internal_edges
);
2654 if (NT_STATUS_IS_ERR(status
)) {
2655 DEBUG(1, (__location__
": failed to process empty edge set: "
2656 "%s\n", nt_errstr(status
)));
2658 talloc_free(tmp_ctx
);
2662 status
= kcctpl_kruskal(tmp_ctx
, graph
, internal_edges
, &output_edges
);
2663 if (NT_STATUS_IS_ERR(status
)) {
2664 DEBUG(1, (__location__
": failed to run Kruskal's algorithm: "
2665 "%s\n", nt_errstr(status
)));
2667 talloc_free(tmp_ctx
);
2671 for (i
= 0; i
< graph
->vertices
.count
; i
++) {
2672 struct kcctpl_vertex
*vertex
= &graph
->vertices
.data
[i
];
2674 if (vertex
->color
== RED
) {
2675 vertex
->dist_to_red
= 0;
2676 } else if (true) { /* TODO: if there exists a path from 'vertex'
2678 vertex
->dist_to_red
= -1; /* TODO: the length of the
2679 shortest such path */
2681 vertex
->dist_to_red
= UINT32_MAX
;
2685 component_count
= kcctpl_count_components(graph
);
2687 status
= kcctpl_copy_output_edges(service
, tmp_ctx
, graph
, output_edges
,
2689 if (NT_STATUS_IS_ERR(status
)) {
2690 DEBUG(1, (__location__
": failed to copy edge list: %s\n",
2691 nt_errstr(status
)));
2693 talloc_free(tmp_ctx
);
2697 *_component_count
= component_count
;
2698 talloc_steal(mem_ctx
, st_edge_list
.data
);
2699 *_st_edge_list
= st_edge_list
;
2700 talloc_free(tmp_ctx
);
2701 return NT_STATUS_OK
;
2705 * creat an nTDSConnection object with the given parameters if one does not
2708 static NTSTATUS
kcctpl_create_connection(struct kccsrv_service
*service
,
2709 TALLOC_CTX
*mem_ctx
,
2710 struct ldb_message
*cross_ref
,
2711 struct ldb_message
*r_bridgehead
,
2712 struct ldb_message
*transport
,
2713 struct ldb_message
*l_bridgehead
,
2714 struct kcctpl_repl_info repl_info
,
2715 uint8_t schedule
[84],
2716 bool detect_failed_dcs
,
2717 bool partial_replica_okay
,
2718 struct GUID_list
*_keep_connections
)
2720 TALLOC_CTX
*tmp_ctx
;
2721 struct ldb_dn
*r_site_dn
, *l_site_dn
, *servers_dn
;
2723 struct GUID r_site_guid
, l_site_guid
;
2725 struct message_list r_bridgeheads_all
, l_bridgeheads_all
,
2726 r_bridgeheads_available
, l_bridgeheads_available
;
2728 struct ldb_result
*res
;
2729 const char * const attrs
[] = { "objectGUID", "parent", "fromServer",
2730 "transportType", "schedule", "options",
2731 "enabledConnection", NULL
};
2732 unsigned int i
, valid_connections
;
2733 struct GUID_list keep_connections
;
2735 tmp_ctx
= talloc_new(service
);
2736 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
2738 r_site_dn
= ldb_dn_copy(tmp_ctx
, r_bridgehead
->dn
);
2739 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(r_site_dn
, tmp_ctx
);
2741 ok
= ldb_dn_remove_child_components(r_site_dn
, 3);
2743 talloc_free(tmp_ctx
);
2744 return NT_STATUS_NO_MEMORY
;
2747 ret
= dsdb_find_guid_by_dn(service
->samdb
, r_site_dn
, &r_site_guid
);
2748 if (ret
!= LDB_SUCCESS
) {
2749 DEBUG(1, (__location__
": failed to find objectGUID for object "
2750 "%s: %s\n", ldb_dn_get_linearized(r_site_dn
),
2751 ldb_strerror(ret
)));
2753 talloc_free(tmp_ctx
);
2754 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2757 l_site_dn
= ldb_dn_copy(tmp_ctx
, l_bridgehead
->dn
);
2758 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(l_site_dn
, tmp_ctx
);
2760 ok
= ldb_dn_remove_child_components(l_site_dn
, 3);
2762 talloc_free(tmp_ctx
);
2763 return NT_STATUS_NO_MEMORY
;
2766 ret
= dsdb_find_guid_by_dn(service
->samdb
, l_site_dn
, &l_site_guid
);
2767 if (ret
!= LDB_SUCCESS
) {
2768 DEBUG(1, (__location__
": failed to find objectGUID for object "
2769 "%s: %s\n", ldb_dn_get_linearized(l_site_dn
),
2770 ldb_strerror(ret
)));
2772 talloc_free(tmp_ctx
);
2773 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2776 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2777 r_site_guid
, cross_ref
,
2778 transport
, partial_replica_okay
,
2779 false, &r_bridgeheads_all
);
2780 if (NT_STATUS_IS_ERR(status
)) {
2781 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2782 "%s\n", nt_errstr(status
)));
2786 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2787 r_site_guid
, cross_ref
,
2788 transport
, partial_replica_okay
,
2790 &r_bridgeheads_available
);
2791 if (NT_STATUS_IS_ERR(status
)) {
2792 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2793 "%s\n", nt_errstr(status
)));
2797 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2798 l_site_guid
, cross_ref
,
2799 transport
, partial_replica_okay
,
2800 false, &l_bridgeheads_all
);
2801 if (NT_STATUS_IS_ERR(status
)) {
2802 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2803 "%s\n", nt_errstr(status
)));
2807 status
= kcctpl_get_all_bridgehead_dcs(service
, tmp_ctx
,
2808 l_site_guid
, cross_ref
,
2809 transport
, partial_replica_okay
,
2811 &l_bridgeheads_available
);
2812 if (NT_STATUS_IS_ERR(status
)) {
2813 DEBUG(1, (__location__
": failed to get all bridgehead DCs: "
2814 "%s\n", nt_errstr(status
)));
2818 servers_dn
= samdb_sites_dn(service
->samdb
, tmp_ctx
);
2820 DEBUG(1, (__location__
": failed to find our own Sites DN\n"));
2822 talloc_free(tmp_ctx
);
2823 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2825 ok
= ldb_dn_add_child_fmt(servers_dn
, "CN=Servers");
2827 talloc_free(tmp_ctx
);
2828 return NT_STATUS_NO_MEMORY
;
2831 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, servers_dn
, LDB_SCOPE_SUBTREE
,
2832 attrs
, "objectClass=nTDSConnection");
2833 if (ret
!= LDB_SUCCESS
) {
2834 DEBUG(1, (__location__
": failed to find nTDSConnection "
2835 "objects: %s\n", ldb_strerror(ret
)));
2837 talloc_free(tmp_ctx
);
2838 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2841 for (i
= 0; i
< res
->count
; i
++) {
2842 struct ldb_message
*connection
;
2843 struct ldb_dn
*parent_dn
, *from_server
;
2845 connection
= res
->msgs
[i
];
2847 parent_dn
= ldb_dn_get_parent(tmp_ctx
, connection
->dn
);
2849 DEBUG(1, (__location__
": failed to get parent DN of "
2851 ldb_dn_get_linearized(connection
->dn
)));
2853 talloc_free(tmp_ctx
);
2854 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2857 from_server
= samdb_result_dn(service
->samdb
, tmp_ctx
, connection
,
2858 "fromServer", NULL
);
2860 DEBUG(1, (__location__
": failed to find fromServer "
2861 "attribute of object %s\n",
2862 ldb_dn_get_linearized(connection
->dn
)));
2864 talloc_free(tmp_ctx
);
2865 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2868 if (kcctpl_message_list_contains_dn(l_bridgeheads_all
,
2870 kcctpl_message_list_contains_dn(r_bridgeheads_all
,
2873 /* TODO: initialize conn_schedule from connection */
2874 uint8_t conn_schedule
[84];
2875 struct ldb_dn
*conn_transport_type
;
2877 conn_opts
= ldb_msg_find_attr_as_int64(connection
,
2880 conn_transport_type
= samdb_result_dn(service
->samdb
, tmp_ctx
,
2884 if (!conn_transport_type
) {
2885 DEBUG(1, (__location__
": failed to find "
2886 "transportType attribute of object "
2888 ldb_dn_get_linearized(connection
->dn
)));
2890 talloc_free(tmp_ctx
);
2891 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2894 if ((conn_opts
& NTDSCONN_OPT_IS_GENERATED
) &&
2895 !(conn_opts
& NTDSCONN_OPT_RODC_TOPOLOGY
) &&
2896 ldb_dn_compare(conn_transport_type
,
2897 transport
->dn
) == 0) {
2898 if (!(conn_opts
& NTDSCONN_OPT_USER_OWNED_SCHEDULE
) &&
2899 memcmp(&conn_schedule
, &schedule
, 84) != 0) {
2900 /* TODO: perform an originating update
2901 to set conn!schedule to schedule */
2904 if ((conn_opts
& NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
) &&
2905 (conn_opts
& NTDSCONN_OPT_USE_NOTIFY
)) {
2906 if (!(repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
)) {
2907 /* TODO: perform an originating
2908 update to clear bits
2909 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2910 and NTDSCONN_OPT_USE_NOTIFY
2913 } else if (repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
) {
2914 /* TODO: perform an originating update
2916 NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
2917 and NTDSCONN_OPT_USE_NOTIFY in
2921 if (conn_opts
& NTDSCONN_OPT_TWOWAY_SYNC
) {
2922 if (!(repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
)) {
2923 /* TODO: perform an originating
2925 NTDSCONN_OPT_TWOWAY_SYNC in
2928 } else if (repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
) {
2929 /* TODO: perform an originating update
2930 to set bit NTDSCONN_OPT_TWOWAY_SYNC
2934 if (conn_opts
& NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
) {
2935 if (!(repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
)) {
2936 /* TODO: perform an originating
2938 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2941 } else if (repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
) {
2942 /* TODO: perform an originating update
2944 NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
2951 ZERO_STRUCT(keep_connections
);
2953 valid_connections
= 0;
2954 for (i
= 0; i
< res
->count
; i
++) {
2955 struct ldb_message
*connection
;
2956 struct ldb_dn
*parent_dn
, *from_server
;
2958 connection
= res
->msgs
[i
];
2960 parent_dn
= ldb_dn_get_parent(tmp_ctx
, connection
->dn
);
2962 DEBUG(1, (__location__
": failed to get parent DN of "
2964 ldb_dn_get_linearized(connection
->dn
)));
2966 talloc_free(tmp_ctx
);
2967 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2970 from_server
= samdb_result_dn(service
->samdb
, tmp_ctx
, connection
,
2971 "fromServer", NULL
);
2973 DEBUG(1, (__location__
": failed to find fromServer "
2974 "attribute of object %s\n",
2975 ldb_dn_get_linearized(connection
->dn
)));
2977 talloc_free(tmp_ctx
);
2978 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
2981 if (kcctpl_message_list_contains_dn(l_bridgeheads_all
,
2983 kcctpl_message_list_contains_dn(r_bridgeheads_all
,
2986 struct ldb_dn
*conn_transport_type
;
2988 conn_opts
= ldb_msg_find_attr_as_int64(connection
,
2991 conn_transport_type
= samdb_result_dn(service
->samdb
, tmp_ctx
,
2995 if (!conn_transport_type
) {
2996 DEBUG(1, (__location__
": failed to find "
2997 "transportType attribute of object "
2999 ldb_dn_get_linearized(connection
->dn
)));
3001 talloc_free(tmp_ctx
);
3002 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3005 if ((!(conn_opts
& NTDSCONN_OPT_IS_GENERATED
) ||
3006 ldb_dn_compare(conn_transport_type
,
3007 transport
->dn
) == 0) &&
3008 !(conn_opts
& NTDSCONN_OPT_RODC_TOPOLOGY
)) {
3009 struct GUID r_guid
, l_guid
, conn_guid
;
3010 bool failed_state_r
, failed_state_l
;
3012 ret
= dsdb_find_guid_by_dn(service
->samdb
, from_server
,
3014 if (ret
!= LDB_SUCCESS
) {
3015 DEBUG(1, (__location__
": failed to "
3016 "find GUID for object %s\n",
3017 ldb_dn_get_linearized(from_server
)));
3019 talloc_free(tmp_ctx
);
3020 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3023 ret
= dsdb_find_guid_by_dn(service
->samdb
, parent_dn
,
3025 if (ret
!= LDB_SUCCESS
) {
3026 DEBUG(1, (__location__
": failed to "
3027 "find GUID for object %s\n",
3028 ldb_dn_get_linearized(parent_dn
)));
3030 talloc_free(tmp_ctx
);
3031 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3034 status
= kcctpl_bridgehead_dc_failed(service
->samdb
,
3038 if (NT_STATUS_IS_ERR(status
)) {
3039 DEBUG(1, (__location__
": failed to "
3040 "check if bridgehead DC has "
3042 nt_errstr(status
)));
3044 talloc_free(tmp_ctx
);
3048 status
= kcctpl_bridgehead_dc_failed(service
->samdb
,
3052 if (NT_STATUS_IS_ERR(status
)) {
3053 DEBUG(1, (__location__
": failed to "
3054 "check if bridgehead DC has "
3056 nt_errstr(status
)));
3058 talloc_free(tmp_ctx
);
3062 if (!failed_state_r
&& !failed_state_l
) {
3063 valid_connections
++;
3066 conn_guid
= samdb_result_guid(connection
,
3069 if (!kcctpl_guid_list_contains(keep_connections
,
3071 struct GUID
*new_data
;
3073 new_data
= talloc_realloc(tmp_ctx
,
3074 keep_connections
.data
,
3076 keep_connections
.count
+ 1);
3077 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
,
3079 new_data
[keep_connections
.count
] = conn_guid
;
3080 keep_connections
.data
= new_data
;
3081 keep_connections
.count
++;
3087 if (valid_connections
== 0) {
3088 uint64_t opts
= NTDSCONN_OPT_IS_GENERATED
;
3089 struct GUID new_guid
, *new_data
;
3091 if (repl_info
.options
& NTDSSITELINK_OPT_USE_NOTIFY
) {
3092 opts
|= NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
;
3093 opts
|= NTDSCONN_OPT_USE_NOTIFY
;
3096 if (repl_info
.options
& NTDSSITELINK_OPT_TWOWAY_SYNC
) {
3097 opts
|= NTDSCONN_OPT_TWOWAY_SYNC
;
3100 if (repl_info
.options
& NTDSSITELINK_OPT_DISABLE_COMPRESSION
) {
3101 opts
|= NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
;
3104 /* perform an originating update to create a new nTDSConnection
3105 * object cn that is:
3107 * - child of l_bridgehead
3108 * - cn!enabledConnection = true
3109 * - cn!options = opts
3110 * - cn!transportType = t
3111 * - cn!fromServer = r_bridgehead
3112 * - cn!schedule = schedule
3115 /* TODO: what should be the new connection's GUID? */
3116 new_guid
= GUID_random();
3118 new_data
= talloc_realloc(tmp_ctx
, keep_connections
.data
,
3120 keep_connections
.count
+ 1);
3121 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data
, tmp_ctx
);
3122 new_data
[keep_connections
.count
] = new_guid
;
3123 keep_connections
.data
= new_data
;
3124 keep_connections
.count
++;
3127 talloc_steal(mem_ctx
, keep_connections
.data
);
3128 *_keep_connections
= keep_connections
;
3129 talloc_free(tmp_ctx
);
3130 return NT_STATUS_OK
;
3134 * construct an NC replica graph for the NC identified by the given 'cross_ref',
3135 * then create any additional nTDSConnection objects required.
3137 static NTSTATUS
kcctpl_create_connections(struct kccsrv_service
*service
,
3138 TALLOC_CTX
*mem_ctx
,
3139 struct kcctpl_graph
*graph
,
3140 struct ldb_message
*cross_ref
,
3141 bool detect_failed_dcs
,
3142 struct GUID_list keep_connections
,
3143 bool *_found_failed_dcs
,
3146 bool connected
, found_failed_dcs
, partial_replica_okay
;
3148 struct ldb_message
*site
;
3149 TALLOC_CTX
*tmp_ctx
;
3150 struct GUID site_guid
;
3151 struct kcctpl_vertex
*site_vertex
;
3152 uint32_t component_count
, i
;
3153 struct kcctpl_multi_edge_list st_edge_list
;
3154 struct ldb_dn
*transports_dn
;
3155 const char * const attrs
[] = { "bridgeheadServerListBL", "name",
3156 "transportAddressAttribute", NULL
};
3161 status
= kcctpl_color_vertices(service
, graph
, cross_ref
, detect_failed_dcs
,
3163 if (NT_STATUS_IS_ERR(status
)) {
3164 DEBUG(1, (__location__
": failed to color vertices: %s\n",
3165 nt_errstr(status
)));
3170 tmp_ctx
= talloc_new(mem_ctx
);
3171 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
3173 site
= kcctpl_local_site(service
->samdb
, tmp_ctx
);
3175 DEBUG(1, (__location__
": failed to find our own local DC's "
3178 talloc_free(tmp_ctx
);
3179 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3182 site_guid
= samdb_result_guid(site
, "objectGUID");
3184 site_vertex
= kcctpl_find_vertex_by_guid(graph
, site_guid
);
3186 DEBUG(1, (__location__
": failed to find vertex %s\n",
3187 GUID_string(tmp_ctx
, &site_guid
)));
3189 talloc_free(tmp_ctx
);
3190 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3193 if (site_vertex
->color
== WHITE
) {
3194 *_found_failed_dcs
= found_failed_dcs
;
3196 talloc_free(tmp_ctx
);
3197 return NT_STATUS_OK
;
3200 status
= kcctpl_get_spanning_tree_edges(service
, tmp_ctx
, graph
,
3203 if (NT_STATUS_IS_ERR(status
)) {
3204 DEBUG(1, (__location__
": failed get spanning tree edges: %s\n",
3205 nt_errstr(status
)));
3207 talloc_free(tmp_ctx
);
3211 if (component_count
> 1) {
3215 partial_replica_okay
= (site_vertex
->color
== BLACK
);
3217 transports_dn
= kcctpl_transports_dn(service
->samdb
, tmp_ctx
);
3218 if (!transports_dn
) {
3219 DEBUG(1, (__location__
": failed to find our own Inter-Site "
3220 "Transports DN\n"));
3222 talloc_free(tmp_ctx
);
3223 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3226 for (i
= 0; i
< st_edge_list
.count
; i
++) {
3227 struct kcctpl_multi_edge
*edge
;
3228 struct GUID other_site_id
;
3229 struct kcctpl_vertex
*other_site_vertex
;
3230 struct ldb_result
*res
;
3231 struct ldb_message
*transport
, *r_bridgehead
, *l_bridgehead
;
3232 uint8_t schedule
[84];
3233 uint32_t first_available
, j
, interval
;
3235 edge
= &st_edge_list
.data
[i
];
3237 if (edge
->directed
&& !GUID_equal(&edge
->vertex_ids
.data
[1],
3238 &site_vertex
->id
)) {
3242 if (GUID_equal(&edge
->vertex_ids
.data
[0], &site_vertex
->id
)) {
3243 other_site_id
= edge
->vertex_ids
.data
[1];
3245 other_site_id
= edge
->vertex_ids
.data
[0];
3248 other_site_vertex
= kcctpl_find_vertex_by_guid(graph
,
3250 if (!other_site_vertex
) {
3251 DEBUG(1, (__location__
": failed to find vertex %s\n",
3252 GUID_string(tmp_ctx
, &other_site_id
)));
3254 talloc_free(tmp_ctx
);
3255 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3258 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, transports_dn
,
3259 LDB_SCOPE_ONELEVEL
, attrs
,
3260 "(&(objectClass=interSiteTransport)"
3261 "(objectGUID=%s))", GUID_string(tmp_ctx
,
3263 if (ret
!= LDB_SUCCESS
) {
3264 DEBUG(1, (__location__
": failed to find "
3265 "interSiteTransport object %s: %s\n",
3266 GUID_string(tmp_ctx
, &edge
->type
),
3267 ldb_strerror(ret
)));
3269 talloc_free(tmp_ctx
);
3270 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3272 if (res
->count
== 0) {
3273 DEBUG(1, (__location__
": failed to find "
3274 "interSiteTransport object %s\n",
3275 GUID_string(tmp_ctx
, &edge
->type
)));
3277 talloc_free(tmp_ctx
);
3278 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3280 transport
= res
->msgs
[0];
3282 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
3283 other_site_vertex
->id
,
3284 cross_ref
, transport
,
3285 partial_replica_okay
,
3288 if (NT_STATUS_IS_ERR(status
)) {
3289 DEBUG(1, (__location__
": failed to get a bridgehead "
3290 "DC: %s\n", nt_errstr(status
)));
3292 talloc_free(tmp_ctx
);
3296 if (service
->am_rodc
) {
3297 /* TODO: l_bridgehad = nTDSDSA of local DC */
3299 status
= kcctpl_get_bridgehead_dc(service
, tmp_ctx
,
3301 cross_ref
, transport
,
3302 partial_replica_okay
,
3305 if (NT_STATUS_IS_ERR(status
)) {
3306 DEBUG(1, (__location__
": failed to get a "
3307 "bridgehead DC: %s\n",
3308 nt_errstr(status
)));
3310 talloc_free(tmp_ctx
);
3315 ZERO_ARRAY(schedule
);
3316 first_available
= 84;
3317 interval
= edge
->repl_info
.interval
/ 15;
3318 for (j
= 0; j
< 84; j
++) {
3319 if (edge
->repl_info
.schedule
[j
] == 1) {
3320 first_available
= j
;
3324 for (j
= first_available
; j
< 84; j
+= interval
) {
3328 status
= kcctpl_create_connection(service
, mem_ctx
, cross_ref
,
3329 r_bridgehead
, transport
,
3330 l_bridgehead
, edge
->repl_info
,
3331 schedule
, detect_failed_dcs
,
3332 partial_replica_okay
,
3334 if (NT_STATUS_IS_ERR(status
)) {
3335 DEBUG(1, (__location__
": failed to create a "
3336 "connection: %s\n", nt_errstr(status
)));
3338 talloc_free(tmp_ctx
);
3343 *_found_failed_dcs
= found_failed_dcs
;
3344 *_connected
= connected
;
3345 talloc_free(tmp_ctx
);
3346 return NT_STATUS_OK
;
3350 * computes an NC replica graph for each NC replica that "should be present" on
3351 * the local DC or "is present" on any DC in the same site as the local DC. for
3352 * each edge directed to an NC replica on such a DC from an NC replica on a DC
3353 * in another site, the KCC creates and nTDSConnection object to imply that edge
3354 * if one does not already exist.
3356 static NTSTATUS
kcctpl_create_intersite_connections(struct kccsrv_service
*service
,
3357 TALLOC_CTX
*mem_ctx
,
3358 struct GUID_list
*_keep_connections
,
3359 bool *_all_connected
)
3361 struct GUID_list keep_connections
;
3363 TALLOC_CTX
*tmp_ctx
;
3364 struct ldb_dn
*partitions_dn
;
3365 struct ldb_result
*res
;
3366 const char * const attrs
[] = { "enabled", "systemFlags", "nCName",
3371 all_connected
= true;
3373 ZERO_STRUCT(keep_connections
);
3375 tmp_ctx
= talloc_new(mem_ctx
);
3376 NT_STATUS_HAVE_NO_MEMORY(tmp_ctx
);
3378 partitions_dn
= samdb_partitions_dn(service
->samdb
, tmp_ctx
);
3379 NT_STATUS_HAVE_NO_MEMORY_AND_FREE(partitions_dn
, tmp_ctx
);
3381 ret
= ldb_search(service
->samdb
, tmp_ctx
, &res
, partitions_dn
, LDB_SCOPE_ONELEVEL
,
3382 attrs
, "objectClass=crossRef");
3383 if (ret
!= LDB_SUCCESS
) {
3384 DEBUG(1, (__location__
": failed to find crossRef objects: "
3385 "%s\n", ldb_strerror(ret
)));
3387 talloc_free(tmp_ctx
);
3388 return NT_STATUS_INTERNAL_DB_CORRUPTION
;
3391 for (i
= 0; i
< res
->count
; i
++) {
3392 struct ldb_message
*cross_ref
;
3393 unsigned int cr_enabled
;
3395 struct kcctpl_graph
*graph
;
3396 bool found_failed_dc
, connected
;
3399 cross_ref
= res
->msgs
[i
];
3400 cr_enabled
= ldb_msg_find_attr_as_uint(cross_ref
, "enabled", -1);
3401 cr_flags
= ldb_msg_find_attr_as_int64(cross_ref
, "systemFlags", 0);
3402 if ((cr_enabled
== 0) || !(cr_flags
& FLAG_CR_NTDS_NC
)) {
3406 status
= kcctpl_setup_graph(service
->samdb
, tmp_ctx
, &graph
);
3407 if (NT_STATUS_IS_ERR(status
)) {
3408 DEBUG(1, (__location__
": failed to create a graph: "
3409 "%s\n", nt_errstr(status
)));
3411 talloc_free(tmp_ctx
);
3415 status
= kcctpl_create_connections(service
, mem_ctx
, graph
,
3420 if (NT_STATUS_IS_ERR(status
)) {
3421 DEBUG(1, (__location__
": failed to create "
3422 "connections: %s\n", nt_errstr(status
)));
3424 talloc_free(tmp_ctx
);
3429 all_connected
= false;
3431 if (found_failed_dc
) {
3432 status
= kcctpl_create_connections(service
, mem_ctx
,
3439 if (NT_STATUS_IS_ERR(status
)) {
3440 DEBUG(1, (__location__
": failed to "
3441 "create connections: %s\n",
3442 nt_errstr(status
)));
3444 talloc_free(tmp_ctx
);
3451 *_keep_connections
= keep_connections
;
3452 *_all_connected
= all_connected
;
3453 talloc_free(tmp_ctx
);
3454 return NT_STATUS_OK
;
3457 NTSTATUS
kcctpl_test(struct kccsrv_service
*service
)
3460 TALLOC_CTX
*tmp_ctx
= talloc_new(service
);
3461 struct GUID_list keep
;
3464 DEBUG(5, ("Testing kcctpl_create_intersite_connections\n"));
3465 status
= kcctpl_create_intersite_connections(service
, tmp_ctx
, &keep
,
3467 DEBUG(4, ("%s\n", nt_errstr(status
)));
3468 if (NT_STATUS_IS_OK(status
)) {
3471 DEBUG(4, ("all_connected=%d, %d GUIDs returned\n",
3472 all_connected
, keep
.count
));
3474 for (i
= 0; i
< keep
.count
; i
++) {
3475 DEBUG(4, ("GUID %d: %s\n", i
+ 1,
3476 GUID_string(tmp_ctx
, &keep
.data
[i
])));
3480 talloc_free(tmp_ctx
);