/*
Unix SMB/CIFS implementation.
KCC service
Copyright (C) CrÃstian Deives 2010
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
*/
#include "includes.h"
#include "dsdb/samdb/samdb.h"
#include "lib/messaging/irpc.h"
#include "librpc/gen_ndr/ndr_misc.h"
#define FLAG_CR_NTDS_NC 0x00000001
#define FLAG_CR_NTDS_DOMAIN 0x00000002
#define NTDSCONN_OPT_IS_GENERATED 0x00000001
#define NTDSCONN_OPT_TWOWAY_SYNC 0x00000002
#define NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT 0x00000004
#define NTDSCONN_OPT_USE_NOTIFY 0x00000008
#define NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION 0x00000010
#define NTDSCONN_OPT_USER_OWNED_SCHEDULE 0x00000020
#define NTDSCONN_OPT_RODC_TOPOLOGY 0x00000040
#define NTDSDSA_OPT_IS_GC 0x00000001
#define NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED 0x00000008
#define NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED 0x00000100
#define NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED 0x00001000
#define NTDSSITELINK_OPT_USE_NOTIFY 0x00000001
#define NTDSSITELINK_OPT_TWOWAY_SYNC 0x00000002
#define NTDSSITELINK_OPT_DISABLE_COMPRESSION 0x00000004
#define NTDSTRANSPORT_OPT_BRIDGES_REQUIRED 0x00000002
#define DS_BEHAVIOR_WIN2008 3
/** replication parameters of a graph edge */
struct kcctpl_repl_info {
uint32_t cost;
uint32_t interval;
uint32_t options;
uint8_t schedule[84];
};
/** color of a vertex */
enum kcctpl_color { RED, BLACK, WHITE };
/** a GUID array list */
struct GUID_list {
struct GUID *data;
uint32_t count;
};
/** a vertex in the site graph */
struct kcctpl_vertex {
struct GUID id;
struct GUID_list edge_ids;
enum kcctpl_color color;
struct GUID_list accept_red_red;
struct GUID_list accept_black;
struct kcctpl_repl_info repl_info;
uint32_t dist_to_red;
/* Dijkstra data */
struct GUID root_id;
bool demoted;
/* Kruskal data */
struct GUID component_id;
uint32_t component_index;
};
/** fully connected subgraph of vertices */
struct kcctpl_multi_edge {
struct GUID id;
struct GUID_list vertex_ids;
struct GUID type;
struct kcctpl_repl_info repl_info;
bool directed;
};
/** set of transitively connected kcc_multi_edge's. all edges within the set
* have the same type. */
struct kcctpl_multi_edge_set {
struct GUID id;
struct GUID_list edge_ids;
};
/** a vertices array list */
struct kcctpl_vertex_list {
struct kcctpl_vertex *data;
uint32_t count;
};
/** an edges array list */
struct kcctpl_multi_edge_list {
struct kcctpl_multi_edge *data;
uint32_t count;
};
/** an edge sets array list */
struct kcctpl_multi_edge_set_list {
struct kcctpl_multi_edge_set *data;
uint32_t count;
};
/** a site graph */
struct kcctpl_graph {
struct kcctpl_vertex_list vertices;
struct kcctpl_multi_edge_list edges;
struct kcctpl_multi_edge_set_list edge_sets;
};
/** path found in the graph between two non-white vertices */
struct kcctpl_internal_edge {
struct GUID v1id;
struct GUID v2id;
bool red_red;
struct kcctpl_repl_info repl_info;
struct GUID type;
};
/** an internal edges array list */
struct kcctpl_internal_edge_list {
struct kcctpl_internal_edge *data;
uint32_t count;
};
/** an LDB messages array list */
struct message_list {
struct ldb_message *data;
uint32_t count;
};
/**
* sort internal edges based on:
* - descending red_red,
* - ascending repl_info.cost,
* - descending available time in repl_info.schedule,
* - ascending v1id,
* - ascending v2id,
* - ascending type.
*
* this function is used in 'kcctpl_kruskal'.
*/
static int kcctpl_sort_internal_edges(const void *internal_edge1,
const void *internal_edge2)
{
const struct kcctpl_internal_edge *ie1, *ie2;
int cmp_red_red;
ie1 = (const struct kcctpl_internal_edge *) internal_edge1;
ie2 = (const struct kcctpl_internal_edge *) internal_edge2;
cmp_red_red = ie2->red_red - ie1->red_red;
if (cmp_red_red == 0) {
int cmp_cost = ie1->repl_info.cost - ie2->repl_info.cost;
if (cmp_cost == 0) {
uint32_t available1, available2, i;
int cmp_schedule;
available1 = available2 = 0;
for (i = 0; i < 84; i++) {
if (ie1->repl_info.schedule[i] == 0) {
available1++;
}
if (ie2->repl_info.schedule[i] == 0) {
available2++;
}
}
cmp_schedule = available2 - available1;
if (cmp_schedule == 0) {
int cmp_v1id = GUID_compare(&ie1->v1id,
&ie2->v1id);
if (cmp_v1id == 0) {
int cmp_v2id = GUID_compare(&ie1->v2id,
&ie2->v2id);
if (cmp_v2id == 0) {
return GUID_compare(&ie1->type,
&ie2->type);
} else {
return cmp_v2id;
}
} else {
return cmp_v1id;
}
} else {
return cmp_schedule;
}
} else {
return cmp_cost;
}
} else {
return cmp_red_red;
}
}
/**
* sort vertices based on the following criteria:
* - ascending color (RED < BLACK),
* - ascending repl_info.cost,
* - ascending id.
*
* this function is used in 'kcctpl_process_edge'.
*/
static int kcctpl_sort_vertices(const void *vertex1, const void *vertex2)
{
const struct kcctpl_vertex *v1, *v2;
int cmp_color;
v1 = (const struct kcctpl_vertex *) vertex1;
v2 = (const struct kcctpl_vertex *) vertex2;
cmp_color = v1->color - v2->color;
if (cmp_color == 0) {
int cmp_cost = v1->repl_info.cost - v2->repl_info.cost;
if (cmp_cost == 0) {
return GUID_compare(&v1->id, &v2->id);
} else {
return cmp_cost;
}
} else {
return cmp_color;
}
}
/**
* sort bridgehead elements (nTDSDSA) based on the following criteria:
* - GC servers precede non-GC servers
* - ascending objectGUID
*
* this function is used in 'kcctpl_get_all_bridgehead_dcs'.
*/
static int kcctpl_sort_bridgeheads(const void *bridgehead1,
const void *bridgehead2)
{
const struct ldb_message *bh1, *bh2;
uint64_t bh1_opts, bh2_opts, cmp_gc;
bh1 = (const struct ldb_message *) bridgehead1;
bh2 = (const struct ldb_message *) bridgehead2;
bh1_opts = samdb_result_int64(bh1, "options", 0);
bh2_opts = samdb_result_int64(bh2, "options", 0);
cmp_gc = (bh1_opts & NTDSDSA_OPT_IS_GC) -
(bh2_opts & NTDSDSA_OPT_IS_GC);
if (cmp_gc == 0) {
struct GUID bh1_id, bh2_id;
bh1_id = samdb_result_guid(bh1, "objectGUID");
bh2_id = samdb_result_guid(bh2, "objectGUID");
return GUID_compare(&bh1_id, &bh2_id);
} else {
return cmp_gc;
}
}
/**
* sort bridgehead elements (nTDSDSA) in a random order.
*
* this function is used in 'kcctpl_get_all_bridgehead_dcs'.
*/
static void kcctpl_shuffle_bridgeheads(struct message_list bridgeheads)
{
uint32_t i;
srandom(time(NULL));
for (i = bridgeheads.count; i > 1; i--) {
uint32_t r;
struct ldb_message tmp;
r = random() % i;
tmp = bridgeheads.data[i - 1];
bridgeheads.data[i - 1] = bridgeheads.data[r];
bridgeheads.data[r] = tmp;
}
}
/**
* find a graph vertex based on its GUID.
*/
static struct kcctpl_vertex *kcctpl_find_vertex_by_guid(struct kcctpl_graph *graph,
struct GUID guid)
{
uint32_t i;
for (i = 0; i < graph->vertices.count; i++) {
if (GUID_equal(&graph->vertices.data[i].id, &guid)) {
return &graph->vertices.data[i];
}
}
return NULL;
}
/**
* find a graph edge based on its GUID.
*/
static struct kcctpl_multi_edge *kcctpl_find_edge_by_guid(struct kcctpl_graph *graph,
struct GUID guid)
{
uint32_t i;
for (i = 0; i < graph->edges.count; i++) {
if (GUID_equal(&graph->edges.data[i].id, &guid)) {
return &graph->edges.data[i];
}
}
return NULL;
}
/**
* find a graph edge that contains a vertex with the specified GUID. the first
* occurrence will be returned.
*/
static struct kcctpl_multi_edge *kcctpl_find_edge_by_vertex_guid(struct kcctpl_graph *graph,
struct GUID guid)
{
uint32_t i;
for (i = 0; i < graph->edges.count; i++) {
struct kcctpl_multi_edge *edge;
uint32_t j;
edge = &graph->edges.data[i];
for (j = 0; j < edge->vertex_ids.count; j++) {
struct GUID vertex_guid = edge->vertex_ids.data[j];
struct GUID *p = &guid;
if (GUID_equal(&vertex_guid, p)) {
return edge;
}
}
}
return NULL;
}
/**
* search for an occurrence of a GUID inside a list of GUIDs.
*/
static bool kcctpl_guid_list_contains(struct GUID_list list, struct GUID guid)
{
uint32_t i;
for (i = 0; i < list.count; i++) {
if (GUID_equal(&list.data[i], &guid)) {
return true;
}
}
return false;
}
/**
* search for an occurrence of an ldb_message inside a list of ldb_messages,
* based on the ldb_message's DN.
*/
static bool kcctpl_message_list_contains_dn(struct message_list list,
struct ldb_dn *dn)
{
uint32_t i;
for (i = 0; i < list.count; i++) {
struct ldb_message *message = &list.data[i];
if (ldb_dn_compare(message->dn, dn) == 0) {
return true;
}
}
return false;
}
/**
* get the Transports DN
* (CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=).
*/
static struct ldb_dn *kcctpl_transports_dn(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx)
{
struct ldb_dn *sites_dn;
bool ok;
sites_dn = samdb_sites_dn(ldb, mem_ctx);
if (!sites_dn) {
return NULL;
}
ok = ldb_dn_add_child_fmt(sites_dn, "CN=Inter-Site Transports");
if (!ok) {
talloc_free(sites_dn);
return NULL;
}
return sites_dn;
}
/**
* get the domain local site object.
*/
static struct ldb_message *kcctpl_local_site(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx)
{
int ret;
TALLOC_CTX *tmp_ctx;
struct ldb_dn *sites_dn;
struct ldb_result *res;
const char * const attrs[] = { "objectGUID", "options", NULL };
tmp_ctx = talloc_new(ldb);
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
if (!sites_dn) {
talloc_free(tmp_ctx);
return NULL;
}
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE, attrs,
"objectClass=site");
if (ret != LDB_SUCCESS || res->count == 0) {
talloc_free(tmp_ctx);
return NULL;
}
talloc_steal(mem_ctx, res);
talloc_free(tmp_ctx);
return res->msgs[0];
}
/*
* compare two internal edges for equality. every field of the structure will be
* compared.
*/
static bool kcctpl_internal_edge_equal(struct kcctpl_internal_edge *edge1,
struct kcctpl_internal_edge *edge2)
{
if (!edge1 || !edge2) {
return false;
}
if (!GUID_equal(&edge1->v1id, &edge2->v1id)) {
return false;
}
if (!GUID_equal(&edge1->v2id, &edge2->v2id)) {
return false;
}
if (edge1->red_red != edge2->red_red) {
return false;
}
if (edge1->repl_info.cost != edge2->repl_info.cost ||
edge1->repl_info.interval != edge2->repl_info.interval ||
edge1->repl_info.options != edge2->repl_info.options ||
memcmp(&edge1->repl_info.schedule,
&edge2->repl_info.schedule, 84) != 0) {
return false;
}
if (!GUID_equal(&edge1->type, &edge2->type)) {
return false;
}
return true;
}
/**
* create a kcctpl_graph instance.
*/
static NTSTATUS kcctpl_create_graph(TALLOC_CTX *mem_ctx,
struct GUID_list guids,
struct kcctpl_graph **_graph)
{
struct kcctpl_graph *graph;
uint32_t i;
graph = talloc_zero(mem_ctx, struct kcctpl_graph);
NT_STATUS_HAVE_NO_MEMORY(graph);
graph->vertices.count = guids.count;
graph->vertices.data = talloc_zero_array(graph, struct kcctpl_vertex,
guids.count);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(graph->vertices.data, graph);
TYPESAFE_QSORT(guids.data, guids.count, GUID_compare);
for (i = 0; i < guids.count; i++) {
graph->vertices.data[i].id = guids.data[i];
}
*_graph = graph;
return NT_STATUS_OK;
}
/**
* create a kcctpl_multi_edge instance.
*/
static NTSTATUS kcctpl_create_edge(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
struct GUID type,
struct ldb_message *site_link,
struct kcctpl_multi_edge **_edge)
{
struct kcctpl_multi_edge *edge;
TALLOC_CTX *tmp_ctx;
struct ldb_dn *sites_dn;
struct ldb_result *res;
const char * const attrs[] = { "siteList", NULL };
int ret;
struct ldb_message_element *el;
uint32_t i;
struct ldb_val val;
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
edge = talloc_zero(tmp_ctx, struct kcctpl_multi_edge);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge, tmp_ctx);
edge->id = samdb_result_guid(site_link, "objectGUID");
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
if (!sites_dn) {
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE, attrs,
"objectGUID=%s", GUID_string(tmp_ctx, &edge->id));
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find siteLink object %s: "
"%s\n", GUID_string(tmp_ctx, &edge->id),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (res->count == 0) {
DEBUG(1, (__location__ ": failed to find siteLink object %s\n",
GUID_string(tmp_ctx, &edge->id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
el = ldb_msg_find_element(res->msgs[0], "siteList");
if (!el) {
DEBUG(1, (__location__ ": failed to find siteList attribute of "
"object %s\n",
ldb_dn_get_linearized(res->msgs[0]->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
edge->vertex_ids.data = talloc_array(edge, struct GUID, el->num_values);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(edge->vertex_ids.data, tmp_ctx);
edge->vertex_ids.count = el->num_values;
for (i = 0; i < el->num_values; i++) {
struct ldb_dn *dn;
struct GUID guid;
val = el->values[i];
dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
if (!dn) {
DEBUG(1, (__location__ ": failed to read a DN from "
"siteList attribute of %s\n",
ldb_dn_get_linearized(res->msgs[0]->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = dsdb_find_guid_by_dn(ldb, dn, &guid);
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find objectGUID "
"for object %s: %s\n",
ldb_dn_get_linearized(dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
edge->vertex_ids.data[i] = guid;
}
edge->repl_info.cost = samdb_result_int64(site_link, "cost", 0);
edge->repl_info.options = samdb_result_int64(site_link, "options", 0);
edge->repl_info.interval = samdb_result_int64(site_link,
"replInterval", 0);
/* TODO: edge->repl_info.schedule = site_link!schedule */
edge->type = type;
edge->directed = false;
*_edge = talloc_steal(mem_ctx, edge);
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* create a kcctpl_multi_edge_set instance containing edges for all siteLink
* objects.
*/
static NTSTATUS kcctpl_create_auto_edge_set(struct kcctpl_graph *graph,
struct GUID type,
struct ldb_result *res_site_link,
struct kcctpl_multi_edge_set **_set)
{
struct kcctpl_multi_edge_set *set;
TALLOC_CTX *tmp_ctx;
uint32_t i;
tmp_ctx = talloc_new(graph);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set, tmp_ctx);
for (i = 0; i < res_site_link->count; i++) {
struct GUID site_link_guid;
struct kcctpl_multi_edge *edge;
site_link_guid = samdb_result_guid(res_site_link->msgs[i],
"objectGUID");
edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
if (!edge) {
DEBUG(1, (__location__ ": failed to find a graph edge "
"with ID=%s\n",
GUID_string(tmp_ctx, &site_link_guid)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (GUID_equal(&edge->type, &type)) {
struct GUID *new_data;
new_data = talloc_realloc(set, set->edge_ids.data,
struct GUID,
set->edge_ids.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[set->edge_ids.count] = site_link_guid;
set->edge_ids.data = new_data;
set->edge_ids.count++;
}
}
*_set = talloc_steal(graph, set);
return NT_STATUS_OK;
}
/**
* create a kcctpl_multi_edge_set instance.
*/
static NTSTATUS kcctpl_create_edge_set(struct ldb_context *ldb,
struct kcctpl_graph *graph,
struct GUID type,
struct ldb_message *bridge,
struct kcctpl_multi_edge_set **_set)
{
struct kcctpl_multi_edge_set *set;
TALLOC_CTX *tmp_ctx;
struct ldb_message_element *el;
uint32_t i;
tmp_ctx = talloc_new(ldb);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
set = talloc_zero(tmp_ctx, struct kcctpl_multi_edge_set);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(set, tmp_ctx);
set->id = samdb_result_guid(bridge, "objectGUID");
el = ldb_msg_find_element(bridge, "siteLinkList");
if (!el) {
DEBUG(1, (__location__ ": failed to find siteLinkList "
"attribute of object %s\n",
ldb_dn_get_linearized(bridge->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
for (i = 0; i < el->num_values; i++) {
struct ldb_val val;
struct ldb_dn *dn;
struct GUID site_link_guid;
int ret;
struct kcctpl_multi_edge *edge;
val = el->values[i];
dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
if (!dn) {
DEBUG(1, (__location__ ": failed to read a DN from "
"siteList attribute of %s\n",
ldb_dn_get_linearized(bridge->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = dsdb_find_guid_by_dn(ldb, dn, &site_link_guid);
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find objectGUID "
"for object %s: %s\n",
ldb_dn_get_linearized(dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
edge = kcctpl_find_edge_by_guid(graph, site_link_guid);
if (!edge) {
DEBUG(1, (__location__ ": failed to find a graph edge "
"with ID=%s\n",
GUID_string(tmp_ctx, &site_link_guid)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (GUID_equal(&edge->type, &type)) {
struct GUID *new_data;
new_data = talloc_realloc(set, set->edge_ids.data,
struct GUID,
set->edge_ids.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[set->edge_ids.count] = site_link_guid;
set->edge_ids.data = new_data;
set->edge_ids.count++;
}
}
*_set = talloc_steal(graph, set);
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* set up a kcctpl_graph, populated with a kcctpl_vertex for each site object, a
* kcctpl_multi_edge for each siteLink object, and a kcctpl_multi_edge_set for
* each siteLinkBridge object (or implied siteLinkBridge).
*/
static NTSTATUS kcctpl_setup_graph(struct ldb_context *ldb, TALLOC_CTX *mem_ctx,
struct kcctpl_graph **_graph)
{
struct kcctpl_graph *graph;
struct ldb_dn *sites_dn, *transports_dn;
TALLOC_CTX *tmp_ctx;
struct ldb_result *res;
const char * const transport_attrs[] = { "objectGUID", NULL };
const char * const site_attrs[] = { "objectGUID", "options", NULL };
const char * const attrs[] = { "objectGUID", "cost", "options",
"replInterval", "schedule", NULL };
const char * const site_link_bridge_attrs[] = { "objectGUID",
"siteLinkList",
NULL };
int ret;
struct GUID_list vertex_ids;
uint32_t i;
NTSTATUS status;
struct ldb_message *site;
uint64_t site_opts;
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
if (!sites_dn) {
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_SUBTREE,
site_attrs, "objectClass=site");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find site objects under "
"%s: %s\n", ldb_dn_get_linearized(sites_dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ZERO_STRUCT(vertex_ids);
for (i = 0; i < res->count; i++) {
struct GUID guid, *new_data;
guid = samdb_result_guid(res->msgs[i], "objectGUID");
new_data = talloc_realloc(tmp_ctx, vertex_ids.data, struct GUID,
vertex_ids.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[vertex_ids.count] = guid;
vertex_ids.data = new_data;
vertex_ids.count++;
}
status = kcctpl_create_graph(tmp_ctx, vertex_ids, &graph);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to create graph: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
site = kcctpl_local_site(ldb, tmp_ctx);
if (!site) {
DEBUG(1, (__location__ ": failed to find our own local DC's "
"site\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
site_opts = samdb_result_int64(site, "options", 0);
transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
if (!transports_dn) {
DEBUG(1, (__location__ ": failed to find our own Inter-Site "
"Transports DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, transports_dn, LDB_SCOPE_ONELEVEL,
transport_attrs, "objectClass=interSiteTransport");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find interSiteTransport "
"objects under %s: %s\n",
ldb_dn_get_linearized(transports_dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
for (i = 0; i < res->count; i++) {
struct ldb_message *transport;
struct ldb_result *res_site_link;
struct GUID transport_guid;
unsigned int j;
uint64_t transport_opts;
transport = res->msgs[i];
ret = ldb_search(ldb, tmp_ctx, &res_site_link, transport->dn,
LDB_SCOPE_SUBTREE, attrs,
"objectClass=siteLink");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find siteLink "
"objects under %s: %s\n",
ldb_dn_get_linearized(transport->dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
transport_guid = samdb_result_guid(transport, "objectGUID");
for (j = 0; j < res_site_link->count; j++) {
struct kcctpl_multi_edge *edge, *new_data;
status = kcctpl_create_edge(ldb, graph, transport_guid,
res_site_link->msgs[j],
&edge);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to create "
"edge: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
new_data = talloc_realloc(graph, graph->edges.data,
struct kcctpl_multi_edge,
graph->edges.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[graph->edges.count] = *edge;
graph->edges.data = new_data;
graph->edges.count++;
}
transport_opts = samdb_result_int64(transport, "options", 0);
if (!(transport_opts & NTDSTRANSPORT_OPT_BRIDGES_REQUIRED) &&
!(site_opts & NTDSSETTINGS_OPT_W2K3_BRIDGES_REQUIRED)) {
struct kcctpl_multi_edge_set *edge_set, *new_data;
status = kcctpl_create_auto_edge_set(graph,
transport_guid,
res_site_link,
&edge_set);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to create "
"edge set: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
new_data = talloc_realloc(graph, graph->edge_sets.data,
struct kcctpl_multi_edge_set,
graph->edge_sets.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[graph->edge_sets.count] = *edge_set;
graph->edge_sets.data = new_data;
graph->edge_sets.count++;
} else {
ret = ldb_search(ldb, tmp_ctx, &res_site_link,
transport->dn, LDB_SCOPE_SUBTREE,
site_link_bridge_attrs,
"objectClass=siteLinkBridge");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find "
"siteLinkBridge objects under %s: "
"%s\n",
ldb_dn_get_linearized(transport->dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
for (j = 0; j < res_site_link->count; j++) {
struct ldb_message *bridge;
struct kcctpl_multi_edge_set *edge_set,
*new_data;
bridge = res_site_link->msgs[j];
status = kcctpl_create_edge_set(ldb, graph,
transport_guid,
bridge,
&edge_set);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to "
"create edge set: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
new_data = talloc_realloc(graph,
graph->edge_sets.data,
struct kcctpl_multi_edge_set,
graph->edge_sets.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
tmp_ctx);
new_data[graph->edge_sets.count] = *edge_set;
graph->edge_sets.data = new_data;
graph->edge_sets.count++;
}
}
}
*_graph = talloc_steal(mem_ctx, graph);
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* determine whether a given DC is known to be in a failed state.
*/
static NTSTATUS kcctpl_bridgehead_dc_failed(struct ldb_context *ldb,
struct GUID guid,
bool detect_failed_dcs,
bool *_failed)
{
TALLOC_CTX *tmp_ctx;
struct ldb_dn *settings_dn;
struct ldb_result *res;
const char * const attrs[] = { "options", NULL };
int ret;
struct ldb_message *settings;
uint64_t settings_opts;
bool failed;
tmp_ctx = talloc_new(ldb);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
settings_dn = samdb_ntds_settings_dn(ldb);
if (!settings_dn) {
DEBUG(1, (__location__ ": failed to find our own NTDS Settings "
"DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, settings_dn, LDB_SCOPE_BASE, attrs,
"objectClass=nTDSSiteSettings");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find site settings object "
"%s: %s\n", ldb_dn_get_linearized(settings_dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (res->count == 0) {
DEBUG(1, ("failed to find site settings object %s\n",
ldb_dn_get_linearized(settings_dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
settings = res->msgs[0];
settings_opts = samdb_result_int64(settings, "options", 0);
if (settings_opts & NTDSSETTINGS_OPT_IS_TOPL_DETECT_STALE_DISABLED) {
failed = false;
} else if (true) { /* TODO: how to get kCCFailedLinks and
kCCFailedConnections? */
failed = true;
} else {
failed = detect_failed_dcs;
}
*_failed = failed;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* get all bridgehead DCs satisfying the given criteria.
*/
static NTSTATUS kcctpl_get_all_bridgehead_dcs(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx,
struct GUID site_guid,
struct ldb_message *cross_ref,
struct ldb_message *transport,
bool partial_replica_okay,
bool detect_failed_dcs,
struct message_list *_bridgeheads)
{
struct message_list bridgeheads, all_dcs_in_site;
TALLOC_CTX *tmp_ctx;
struct ldb_result *res;
struct ldb_dn *sites_dn, *schemas_dn;
const char * const attrs[] = { "options", NULL };
int ret;
struct ldb_message *site, *schema;
const char * const dc_attrs[] = { "objectGUID", "options", NULL };
struct ldb_message_element *el;
uint32_t i;
bool rodc;
const char *transport_name, *transport_address_attr;
uint64_t site_opts;
ZERO_STRUCT(bridgeheads);
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
if (!sites_dn) {
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn, LDB_SCOPE_ONELEVEL,
attrs, "(&(objectClass=site)(objectGUID=%s))",
GUID_string(tmp_ctx, &site_guid));
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find site object %s: %s\n",
GUID_string(tmp_ctx, &site_guid),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (res->count == 0) {
DEBUG(1, (__location__ ": failed to find site object %s\n",
GUID_string(tmp_ctx, &site_guid)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
site = res->msgs[0];
schemas_dn = samdb_schema_dn(ldb);
if (!schemas_dn) {
DEBUG(1, (__location__ ": failed to find our own Schemas DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, schemas_dn, LDB_SCOPE_SUBTREE,
NULL,
"(&(lDAPDisplayName=nTDSDSA)(objectClass=classSchema))");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find classSchema object :"
"%s\n", ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (res->count == 0) {
DEBUG(1, (__location__ ": failed to find classSchema "
"object\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
schema = res->msgs[0];
ZERO_STRUCT(all_dcs_in_site);
ret = ldb_search(ldb, tmp_ctx, &res, site->dn, LDB_SCOPE_SUBTREE,
dc_attrs, "objectCategory=%s",
ldb_dn_get_linearized(schema->dn));
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find DCs objects :%s\n",
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
el = ldb_msg_find_element(transport, "bridgeheadServerListBL");
rodc = samdb_rodc(ldb);
transport_name = samdb_result_string(transport, "name", NULL);
if (!transport_name) {
DEBUG(1, (__location__ ": failed to find name attribute of "
"object %s\n", ldb_dn_get_linearized(transport->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
transport_address_attr = samdb_result_string(transport,
"transportAddressAttribute",
NULL);
if (!transport_address_attr) {
DEBUG(1, (__location__ ": failed to find "
"transportAddressAttribute attribute of object %s\n",
ldb_dn_get_linearized(transport->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
site_opts = samdb_result_int64(site, "options", 0);
for (i = 0; i < res->count; i++) {
struct ldb_message *dc, *new_data;
uint32_t j;
struct ldb_dn *parent_dn;
uint64_t behavior_version;
const char *dc_transport_address;
struct ldb_result *parent_res;
const char *parent_attrs[] = { transport_address_attr, NULL };
NTSTATUS status;
struct GUID dc_guid;
bool failed;
dc = res->msgs[i];
parent_dn = ldb_dn_get_parent(tmp_ctx, dc->dn);
if (!parent_dn) {
DEBUG(1, (__location__ ": failed to get parent DN of "
"%s\n", ldb_dn_get_linearized(dc->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (el && (el->num_values >= 1)) {
bool contains = false;
for (j = 0; j < el->num_values; j++) {
struct ldb_val val;
struct ldb_dn *dn;
val = el->values[j];
dn = ldb_dn_from_ldb_val(tmp_ctx, ldb, &val);
if (!dn) {
DEBUG(1, (__location__ ": failed to read a DN "
"from bridgeheadServerListBL "
"attribute of %s\n",
ldb_dn_get_linearized(transport->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (ldb_dn_compare(dn, parent_dn) == 0) {
contains = true;
break;
}
}
if (!contains) {
continue;
}
}
/* TODO: if dc is in the same site as the local DC */
if (true) {
/* TODO: if a replica of cr!nCName is not in the set of
* NC replicas that "should be present" on 'dc' */
/* TODO: a partial replica of the NC "should be
present" */
if (true || (true && !partial_replica_okay)) {
continue;
}
} else {
/* TODO: if an NC replica of cr!nCName is not in the set
* of NC replicas that "are present" on 'dc' */
/* TODO: a partial replica of the NC "is present" */
if (true || (true && !partial_replica_okay)) {
continue;
}
}
behavior_version = samdb_result_int64(dc,
"msDS-Behavior-Version", 0);
/* TODO: cr!nCName corresponds to default NC */
if (rodc && true && behavior_version < DS_BEHAVIOR_WIN2008) {
continue;
}
ret = ldb_search(ldb, tmp_ctx, &parent_res, parent_dn,
LDB_SCOPE_BASE, parent_attrs , NULL);
dc_transport_address = samdb_result_string(parent_res->msgs[0],
transport_address_attr,
NULL);
if (strncmp(transport_name, "IP", 2) != 0 &&
dc_transport_address == NULL) {
continue;
}
dc_guid = samdb_result_guid(dc, "objectGUID");
status = kcctpl_bridgehead_dc_failed(ldb, dc_guid,
detect_failed_dcs,
&failed);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to check if "
"bridgehead DC has failed: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
if (failed) {
continue;
}
new_data = talloc_realloc(tmp_ctx, bridgeheads.data,
struct ldb_message,
bridgeheads.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[bridgeheads.count + 1] = *dc;
bridgeheads.data = new_data;
bridgeheads.count++;
}
if (site_opts & NTDSSETTINGS_OPT_IS_RAND_BH_SELECTION_DISABLED) {
qsort(bridgeheads.data, bridgeheads.count,
sizeof(struct ldb_message), kcctpl_sort_bridgeheads);
} else {
kcctpl_shuffle_bridgeheads(bridgeheads);
}
talloc_steal(mem_ctx, bridgeheads.data);
*_bridgeheads = bridgeheads;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* get a bridgehead DC.
*/
static NTSTATUS kcctpl_get_bridgehead_dc(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx,
struct GUID site_guid,
struct ldb_message *cross_ref,
struct ldb_message *transport,
bool partial_replica_okay,
bool detect_failed_dcs,
struct ldb_message **_dsa)
{
struct message_list dsa_list;
NTSTATUS status;
status = kcctpl_get_all_bridgehead_dcs(ldb, mem_ctx,
site_guid, cross_ref, transport,
partial_replica_okay,
detect_failed_dcs, &dsa_list);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
"%s\n", nt_errstr(status)));
return status;
}
*_dsa = (dsa_list.count == 0) ? NULL : &dsa_list.data[0];
return NT_STATUS_OK;
}
/*
* color each vertex to indicate which kinds of NC replicas it contains.
*/
static NTSTATUS kcctpl_color_vertices(struct ldb_context *ldb,
struct kcctpl_graph *graph,
struct ldb_message *cross_ref,
bool detect_failed_dcs,
bool *_found_failed_dcs)
{
TALLOC_CTX *tmp_ctx;
struct ldb_dn *sites_dn;
bool found_failed_dcs, partial_replica_okay;
uint32_t i;
struct ldb_message *site;
struct ldb_result *res;
int ret, cr_flags;
struct GUID site_guid;
struct kcctpl_vertex *site_vertex;
found_failed_dcs = false;
tmp_ctx = talloc_new(ldb);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
sites_dn = samdb_sites_dn(ldb, tmp_ctx);
if (!sites_dn) {
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
for (i = 0; i < graph->vertices.count; i++) {
struct kcctpl_vertex *vertex;
struct ldb_dn *nc_name;
/* TODO: set 'attrs' with its corresponding values */
const char * const attrs[] = { NULL };
vertex = &graph->vertices.data[i];
ret = ldb_search(ldb, tmp_ctx, &res, sites_dn,
LDB_SCOPE_SUBTREE, attrs, "objectGUID=%s",
GUID_string(tmp_ctx, &vertex->id));
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find site object "
"%s: %s\n", GUID_string(tmp_ctx, &vertex->id),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (res->count == 0) {
DEBUG(1, (__location__ ": failed to find site object "
"%s\n", GUID_string(tmp_ctx, &vertex->id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
site = res->msgs[0];
nc_name = samdb_result_dn(ldb, tmp_ctx, cross_ref,
"nCName", NULL);
if (!nc_name) {
DEBUG(1, (__location__ ": failed to find nCName "
"attribute of object %s\n",
ldb_dn_get_linearized(cross_ref->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (true) { /* TODO: site contains 1+ DCs with full replicas of
'nc_name' */
vertex->color = RED;
} else if (true) { /* TODO: site contains 1+ partial replicas of
'nc_name' */
vertex->color = BLACK;
} else {
vertex->color = WHITE;
}
}
site = kcctpl_local_site(ldb, tmp_ctx);
if (!site) {
DEBUG(1, (__location__ ": failed to find our own local DC's "
"site\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
site_guid = samdb_result_guid(site, "objectGUID");
site_vertex = kcctpl_find_vertex_by_guid(graph, site_guid);
if (!site_vertex) {
DEBUG(1, (__location__ ": failed to find a vertex edge with "
"GUID=%s\n", GUID_string(tmp_ctx, &site_guid)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
partial_replica_okay = (site_vertex->color == BLACK);
cr_flags = samdb_result_int64(cross_ref, "systemFlags", 0);
for (i = 0; i < graph->vertices.count; i++) {
struct kcctpl_vertex *vertex;
struct ldb_dn *transports_dn;
const char * const attrs[] = { "objectGUID", "name",
"transportAddressAttribute",
NULL };
uint32_t j;
vertex = &graph->vertices.data[i];
transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
if (!transports_dn) {
DEBUG(1, (__location__ ": failed to find our own "
"Inter-Site Transports DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, transports_dn,
LDB_SCOPE_ONELEVEL, attrs,
"objectClass=interSiteTransport");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find "
"interSiteTransport objects under %s: %s\n",
ldb_dn_get_linearized(transports_dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
for (j = 0; j < res->count; j++) {
struct ldb_message *transport, *bridgehead;
const char *transport_name;
struct GUID transport_guid, *new_data;
NTSTATUS status;
transport = res->msgs[j];
transport_name = samdb_result_string(transport,
"name", NULL);
if (!transport_name) {
DEBUG(1, (__location__ ": failed to find name "
"attribute of object %s\n",
ldb_dn_get_linearized(transport->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
transport_guid = samdb_result_guid(transport,
"objectGUID");
if (site_vertex->color == RED &&
strncmp(transport_name, "IP", 2) != 0 &&
(cr_flags & FLAG_CR_NTDS_DOMAIN)) {
continue;
}
if (!kcctpl_find_edge_by_vertex_guid(graph,
vertex->id)) {
continue;
}
status = kcctpl_get_bridgehead_dc(ldb, tmp_ctx,
site_vertex->id,
cross_ref, transport,
partial_replica_okay,
detect_failed_dcs,
&bridgehead);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get a "
"bridgehead DC: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
if (!bridgehead) {
found_failed_dcs = true;
continue;
}
new_data = talloc_realloc(vertex,
vertex->accept_red_red.data,
struct GUID,
vertex->accept_red_red.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[vertex->accept_red_red.count + 1] = transport_guid;
vertex->accept_red_red.data = new_data;
vertex->accept_red_red.count++;
new_data = talloc_realloc(vertex,
vertex->accept_black.data,
struct GUID,
vertex->accept_black.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[vertex->accept_black.count + 1] = transport_guid;
vertex->accept_black.data = new_data;
vertex->accept_black.count++;
}
}
*_found_failed_dcs = found_failed_dcs;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* setup the fields of the vertices that are relevant to Phase I (Dijkstra's
* Algorithm). for each vertex, set up its cost, root vertex and component. this
* defines the shortest-path forest structures.
*/
static void kcctpl_setup_vertices(struct kcctpl_graph *graph)
{
uint32_t i;
for (i = 0; i < graph->vertices.count; i++) {
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
if (vertex->color == WHITE) {
vertex->repl_info.cost = UINT32_MAX;
vertex->root_id = vertex->component_id = GUID_zero();
} else {
vertex->repl_info.cost = 0;
vertex->root_id = vertex->component_id = vertex->id;
}
vertex->repl_info.interval = 0;
vertex->repl_info.options = 0xFFFFFFFF;
ZERO_STRUCT(vertex->repl_info.schedule);
vertex->demoted = false;
}
}
/**
* demote one vertex if necessary.
*/
static void kcctpl_check_demote_one_vertex(struct kcctpl_vertex *vertex,
struct GUID type)
{
if (vertex->color == WHITE) {
return;
}
if (!kcctpl_guid_list_contains(vertex->accept_black, type) &&
!kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
vertex->repl_info.cost = UINT32_MAX;
vertex->root_id = GUID_zero();
vertex->demoted = true;
}
}
/**
* clear the demoted state of a vertex.
*/
static void kcctpl_undemote_one_vertex(struct kcctpl_vertex *vertex)
{
if (vertex->color == WHITE) {
return;
}
vertex->repl_info.cost = 0;
vertex->root_id = vertex->id;
vertex->demoted = false;
}
/**
* returns the id of the component containing 'vertex' by traversing the up-tree
* implied by the component pointers.
*/
static struct GUID kcctpl_get_component_id(struct kcctpl_graph *graph,
struct kcctpl_vertex *vertex)
{
struct kcctpl_vertex *u;
struct GUID root;
u = vertex;
while (!GUID_equal(&u->component_id, &u->id)) {
u = kcctpl_find_vertex_by_guid(graph, u->component_id);
}
root = u->id;
u = vertex;
while (!GUID_equal(&u->component_id, &u->id)) {
struct kcctpl_vertex *w;
w = kcctpl_find_vertex_by_guid(graph, u->component_id);
u->component_id = root;
u = w;
}
return root;
}
/**
* copy all spanning tree edges from 'output_edges' that contain the vertex for
* DCs in the local DC's site.
*/
static NTSTATUS kcctpl_copy_output_edges(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct kcctpl_multi_edge_list output_edges,
struct kcctpl_multi_edge_list *_copy)
{
struct kcctpl_multi_edge_list copy;
TALLOC_CTX *tmp_ctx;
struct ldb_message *site;
struct GUID site_guid;
uint32_t i;
ZERO_STRUCT(copy);
tmp_ctx = talloc_new(ldb);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
site = kcctpl_local_site(ldb, tmp_ctx);
if (!site) {
DEBUG(1, (__location__ ": failed to find our own local DC's "
"site\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
site_guid = samdb_result_guid(site, "objectGUID");
for (i = 0; i < output_edges.count; i++) {
struct kcctpl_multi_edge *edge;
struct kcctpl_vertex *vertex1, *vertex2;
edge = &output_edges.data[i];
vertex1 = kcctpl_find_vertex_by_guid(graph,
edge->vertex_ids.data[0]);
if (!vertex1) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx,
&edge->vertex_ids.data[0])));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
vertex2 = kcctpl_find_vertex_by_guid(graph,
edge->vertex_ids.data[1]);
if (!vertex2) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx,
&edge->vertex_ids.data[1])));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (GUID_equal(&vertex1->id, &site_guid) ||
GUID_equal(&vertex2->id, &site_guid)) {
struct kcctpl_multi_edge *new_data;
if ((vertex1->color == BLACK ||
vertex2->color == BLACK) &&
vertex1->dist_to_red != UINT32_MAX) {
edge->directed = true;
if (vertex2->dist_to_red <
vertex1->dist_to_red) {
struct GUID tmp;
tmp = edge->vertex_ids.data[0];
edge->vertex_ids.data[0] = edge->vertex_ids.data[1];
edge->vertex_ids.data[1] = tmp;
}
}
new_data = talloc_realloc(tmp_ctx, copy.data,
struct kcctpl_multi_edge,
copy.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[copy.count + 1] = *edge;
copy.data = new_data;
copy.count++;
}
}
talloc_steal(mem_ctx, copy.data);
*_copy = copy;
return NT_STATUS_OK;
}
/**
* build the initial sequence for use with Dijkstra's algorithm. it will contain
* the red and black vertices as root vertices, unless these vertices accept no
* edges of the current 'type', or unless black vertices are not being
* including.
*/
static NTSTATUS kcctpl_setup_dijkstra(TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct GUID type, bool include_black,
struct kcctpl_vertex_list *_vertices)
{
struct kcctpl_vertex_list vertices;
uint32_t i;
kcctpl_setup_vertices(graph);
ZERO_STRUCT(vertices);
for (i = 0; i < graph->vertices.count; i++) {
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
if (vertex->color == WHITE) {
continue;
}
if ((vertex->color == BLACK && !include_black) ||
!kcctpl_guid_list_contains(vertex->accept_black, type) ||
!kcctpl_guid_list_contains(vertex->accept_red_red, type)) {
vertex->repl_info.cost = UINT32_MAX;
vertex->root_id = GUID_zero();
vertex->demoted = true;
} else {
struct kcctpl_vertex *new_data;
new_data = talloc_realloc(mem_ctx, vertices.data,
struct kcctpl_vertex,
vertices.count + 1);
NT_STATUS_HAVE_NO_MEMORY(new_data);
new_data[vertices.count] = *vertex;
vertices.data = new_data;
vertices.count++;
}
}
*_vertices = vertices;
return NT_STATUS_OK;
}
/**
* merge schedules, replication intervals, options and costs.
*/
static bool kcctpl_combine_repl_info(struct kcctpl_graph *graph,
struct kcctpl_repl_info *ria,
struct kcctpl_repl_info *rib,
struct kcctpl_repl_info *ric)
{
uint8_t schedule[84];
bool is_available;
uint32_t i;
int32_t ric_cost;
is_available = false;
for (i = 0; i < 84; i++) {
schedule[i] = ria->schedule[i] & rib->schedule[i];
if (schedule[i] == 1) {
is_available = true;
}
}
if (!is_available) {
return false;
}
ric_cost = ria->cost + rib->cost;
ric->cost = (ric_cost < 0) ? UINT32_MAX : ric_cost;
ric->interval = MAX(ria->interval, rib->interval);
ric->options = ria->options & rib->options;
memcpy(&ric->schedule, &schedule, 84);
return true;
}
/**
* helper function for Dijkstra's algorithm. a new path has been found from a
* root vertex to vertex 'vertex2'. this path is ('vertex1->root, ..., vertex1,
* vertex2'). 'edge' is the edge connecting 'vertex1' and 'vertex2'. if this new
* path is better (in this case cheaper, or has a longer schedule), update
* 'vertex2' to use the new path.
*/
static NTSTATUS kcctpl_try_new_path(TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct kcctpl_vertex_list vertices,
struct kcctpl_vertex *vertex1,
struct kcctpl_multi_edge *edge,
struct kcctpl_vertex *vertex2)
{
struct kcctpl_repl_info new_repl_info;
bool intersect;
uint32_t i, new_duration, old_duration;
ZERO_STRUCT(new_repl_info);
intersect = kcctpl_combine_repl_info(graph, &vertex1->repl_info,
&edge->repl_info, &new_repl_info);
if (new_repl_info.cost > vertex2->repl_info.cost) {
return NT_STATUS_OK;
}
if (new_repl_info.cost < vertex2->repl_info.cost && !intersect) {
return NT_STATUS_OK;
}
new_duration = old_duration = 0;
for (i = 0; i < 84; i++) {
if (new_repl_info.schedule[i] == 1) {
new_duration++;
}
if (vertex2->repl_info.schedule[i] == 1) {
old_duration++;
}
}
if (new_repl_info.cost < vertex2->repl_info.cost ||
new_duration > old_duration) {
struct kcctpl_vertex *new_data;
vertex2->root_id = vertex1->root_id;
vertex2->component_id = vertex1->component_id;
vertex2->repl_info = new_repl_info;
new_data = talloc_realloc(mem_ctx, vertices.data,
struct kcctpl_vertex,
vertices.count + 1);
NT_STATUS_HAVE_NO_MEMORY(new_data);
new_data[vertices.count + 1] = *vertex2;
vertices.data = new_data;
vertices.count++;
}
return NT_STATUS_OK;
}
/**
* run Dijkstra's algorithm with the red (and possibly black) vertices as the
* root vertices, and build up a shortest-path forest.
*/
static NTSTATUS kcctpl_dijkstra(struct kcctpl_graph *graph, struct GUID type,
bool include_black)
{
TALLOC_CTX *tmp_ctx;
struct kcctpl_vertex_list vertices;
NTSTATUS status;
tmp_ctx = talloc_new(graph);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
status = kcctpl_setup_dijkstra(tmp_ctx, graph, type, include_black,
&vertices);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to build the initial sequence "
"for Dijkstra's algorithm: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
while (vertices.count > 0) {
uint32_t minimum_cost, minimum_index, i;
struct kcctpl_vertex *minimum_vertex, *new_data;
minimum_cost = UINT32_MAX;
minimum_index = -1;
minimum_vertex = NULL;
for (i = 0; i < vertices.count; i++) {
struct kcctpl_vertex *vertex = &vertices.data[i];
if (vertex->repl_info.cost < minimum_cost) {
minimum_cost = vertex->repl_info.cost;
minimum_vertex = vertex;
minimum_index = i;
} else if (vertex->repl_info.cost == minimum_cost &&
GUID_compare(&vertex->id,
&minimum_vertex->id) < 0) {
minimum_vertex = vertex;
minimum_index = i;
}
}
if (minimum_index < vertices.count - 1) {
memcpy(&vertices.data[minimum_index + 1],
&vertices.data[minimum_index],
vertices.count - minimum_index - 1);
}
new_data = talloc_realloc(tmp_ctx, vertices.data,
struct kcctpl_vertex,
vertices.count - 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
talloc_free(vertices.data);
vertices.data = new_data;
vertices.count--;
for (i = 0; i < graph->edges.count; i++) {
struct kcctpl_multi_edge *edge = &graph->edges.data[i];
if (kcctpl_guid_list_contains(minimum_vertex->edge_ids,
edge->id)) {
uint32_t j;
for (j = 0; j < edge->vertex_ids.count; j++) {
struct GUID vertex_id;
struct kcctpl_vertex *vertex;
vertex_id = edge->vertex_ids.data[j];
vertex = kcctpl_find_vertex_by_guid(graph,
vertex_id);
if (!vertex) {
DEBUG(1, (__location__
": failed to find "
"vertex %s\n",
GUID_string(tmp_ctx,
&vertex_id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
kcctpl_try_new_path(tmp_ctx, graph,
vertices,
minimum_vertex,
edge, vertex);
}
}
}
}
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* add an edge to the list of edges that will be processed with Kruskal's. the
* endpoints are in fact the root of the vertices to pass in, so the endpoints
* are always colored vertices.
*/
static NTSTATUS kcctpl_add_int_edge(TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct kcctpl_internal_edge_list internal_edges,
struct kcctpl_multi_edge *edge,
struct kcctpl_vertex *vertex1,
struct kcctpl_vertex *vertex2)
{
struct kcctpl_vertex *root1, *root2;
bool red_red, found;
struct kcctpl_repl_info repl_info1, repl_info2;
struct kcctpl_internal_edge new_internal_edge, *new_data;
uint32_t i;
root1 = kcctpl_find_vertex_by_guid(graph, vertex1->root_id);
if (!root1) {
TALLOC_CTX *tmp_ctx = talloc_new(graph);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &vertex1->root_id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
root2 = kcctpl_find_vertex_by_guid(graph, vertex2->root_id);
if (!root2) {
TALLOC_CTX *tmp_ctx = talloc_new(graph);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &vertex2->root_id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
red_red = (root1->color == RED && root2->color == RED);
if (red_red) {
if (!kcctpl_guid_list_contains(root1->accept_red_red,
edge->type) ||
!kcctpl_guid_list_contains(root2->accept_red_red,
edge->type)) {
return NT_STATUS_OK;
}
} else if (!kcctpl_guid_list_contains(root1->accept_black,
edge->type) ||
!kcctpl_guid_list_contains(root2->accept_black,
edge->type)) {
return NT_STATUS_OK;
}
if (!kcctpl_combine_repl_info(graph, &vertex1->repl_info,
&vertex2->repl_info, &repl_info1) ||
!kcctpl_combine_repl_info(graph, &repl_info1, &edge->repl_info,
&repl_info2)) {
return NT_STATUS_OK;
}
new_internal_edge.v1id = root1->id;
new_internal_edge.v2id = root2->id;
new_internal_edge.red_red = red_red;
new_internal_edge.repl_info = repl_info2;
new_internal_edge.type = edge->type;
if (GUID_compare(&new_internal_edge.v1id,
&new_internal_edge.v2id) > 0) {
struct GUID tmp_guid = new_internal_edge.v1id;
new_internal_edge.v1id = new_internal_edge.v2id;
new_internal_edge.v2id = tmp_guid;
}
found = false;
for (i = 0; i < internal_edges.count; i++) {
struct kcctpl_internal_edge *ie = &internal_edges.data[i];
if (kcctpl_internal_edge_equal(ie, &new_internal_edge)) {
found = true;
}
}
if (found) {
return NT_STATUS_OK;
}
new_data = talloc_realloc(mem_ctx, internal_edges.data,
struct kcctpl_internal_edge,
internal_edges.count + 1);
NT_STATUS_HAVE_NO_MEMORY(new_data);
new_data[internal_edges.count + 1] = new_internal_edge;
internal_edges.data = new_data;
internal_edges.count++;
return NT_STATUS_OK;
}
/**
* after running Dijkstra's algorithm, this function examines a multi-edge and
* adds internal edges between every tree connected by this edge.
*/
static NTSTATUS kcctpl_process_edge(TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct kcctpl_multi_edge *edge,
struct kcctpl_internal_edge_list internal_edges)
{
TALLOC_CTX *tmp_ctx;
struct kcctpl_vertex_list vertices;
uint32_t i;
struct kcctpl_vertex *best_vertex;
ZERO_STRUCT(vertices);
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
for (i = 0; i < edge->vertex_ids.count; i++) {
struct GUID id;
struct kcctpl_vertex *vertex, *new_data;
id = edge->vertex_ids.data[i];
vertex = kcctpl_find_vertex_by_guid(graph, id);
if (!vertex) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
new_data = talloc_realloc(tmp_ctx, vertices.data,
struct kcctpl_vertex,
vertices.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[vertices.count] = *vertex;
vertices.data = new_data;
vertices.count++;
}
qsort(vertices.data, vertices.count, sizeof(struct kcctpl_vertex),
kcctpl_sort_vertices);
best_vertex = &vertices.data[0];
for (i = 0; i < edge->vertex_ids.count; i++) {
struct GUID id, empty_id = GUID_zero();
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
id = edge->vertex_ids.data[i];
vertex = kcctpl_find_vertex_by_guid(graph, id);
if (!vertex) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (!GUID_equal(&vertex->component_id, &empty_id) &&
!GUID_equal(&vertex->root_id, &empty_id)) {
continue;
}
if (!GUID_equal(&best_vertex->component_id,
&empty_id) &&
!GUID_equal(&best_vertex->root_id, &empty_id) &&
!GUID_equal(&vertex->component_id, &empty_id) &&
!GUID_equal(&vertex->root_id, &empty_id) &&
!GUID_equal(&best_vertex->component_id,
&vertex->component_id)) {
NTSTATUS status;
status = kcctpl_add_int_edge(mem_ctx, graph,
internal_edges,
edge, best_vertex,
vertex);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to add an "
"internal edge for %s: %s\n",
GUID_string(tmp_ctx, &vertex->id),
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
}
}
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* after running Dijkstra's algorithm to determine the shortest-path forest,
* examine all edges in this edge set. find all inter-tree edges, from which to
* build the list of 'internal edges', which will later be passed on to
* Kruskal's algorithm.
*/
static NTSTATUS kcctpl_process_edge_set(TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct kcctpl_multi_edge_set *set,
struct kcctpl_internal_edge_list internal_edges)
{
uint32_t i;
if (!set) {
for (i = 0; i < graph->edges.count; i++) {
struct kcctpl_multi_edge *edge;
uint32_t j;
NTSTATUS status;
edge = &graph->edges.data[i];
for (j = 0; j < edge->vertex_ids.count; j++) {
struct GUID id;
struct kcctpl_vertex *vertex;
id = edge->vertex_ids.data[j];
vertex = kcctpl_find_vertex_by_guid(graph, id);
if (!vertex) {
TALLOC_CTX *tmp_ctx;
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to "
"find vertex %s\n",
GUID_string(tmp_ctx, &id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
kcctpl_check_demote_one_vertex(vertex,
edge->type);
}
status = kcctpl_process_edge(mem_ctx, graph, edge,
internal_edges);
if (NT_STATUS_IS_ERR(status)) {
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to process "
"edge %s: %s\n",
GUID_string(tmp_ctx, &edge->id),
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
for (j = 0; j < edge->vertex_ids.count; j++) {
struct GUID id;
struct kcctpl_vertex *vertex;
id = edge->vertex_ids.data[j];
vertex = kcctpl_find_vertex_by_guid(graph, id);
if (!vertex) {
TALLOC_CTX *tmp_ctx;
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to "
"find vertex %s\n",
GUID_string(tmp_ctx, &id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
kcctpl_undemote_one_vertex(vertex);
}
}
} else {
for (i = 0; i < graph->edges.count; i++) {
struct kcctpl_multi_edge *edge = &graph->edges.data[i];
if (kcctpl_guid_list_contains(set->edge_ids,
edge->id)) {
NTSTATUS status;
status = kcctpl_process_edge(mem_ctx, graph,
edge,
internal_edges);
if (NT_STATUS_IS_ERR(status)) {
TALLOC_CTX *tmp_ctx;
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to "
"process edge %s: %s\n",
GUID_string(tmp_ctx,
&edge->id),
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
}
}
}
return NT_STATUS_OK;
}
/**
* a new edge, 'internal_edge', has been found for the spanning tree edge. add
* this edge to the list of output edges.
*/
static NTSTATUS kcctpl_add_out_edge(TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct kcctpl_multi_edge_list output_edges,
struct kcctpl_internal_edge *internal_edge)
{
struct kcctpl_vertex *vertex1, *vertex2;
TALLOC_CTX *tmp_ctx;
struct kcctpl_multi_edge *new_edge, *new_data;
struct GUID *new_data_id;
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
vertex1 = kcctpl_find_vertex_by_guid(graph, internal_edge->v1id);
if (!vertex1) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &internal_edge->v1id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
vertex2 = kcctpl_find_vertex_by_guid(graph, internal_edge->v2id);
if (!vertex2) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &internal_edge->v2id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
new_edge = talloc(tmp_ctx, struct kcctpl_multi_edge);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge, tmp_ctx);
new_edge->id = GUID_random(); /* TODO: what should be new_edge->GUID? */
new_edge->directed = false;
new_edge->vertex_ids.data = talloc_array(new_edge, struct GUID, 2);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_edge->vertex_ids.data, tmp_ctx);
new_edge->vertex_ids.data[0] = vertex1->id;
new_edge->vertex_ids.data[1] = vertex2->id;
new_edge->vertex_ids.count = 2;
new_edge->type = internal_edge->type;
new_edge->repl_info = internal_edge->repl_info;
new_data = talloc_realloc(tmp_ctx, output_edges.data,
struct kcctpl_multi_edge,
output_edges.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[output_edges.count + 1] = *new_edge;
output_edges.data = new_data;
output_edges.count++;
new_data_id = talloc_realloc(vertex1, vertex1->edge_ids.data,
struct GUID, vertex1->edge_ids.count);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
new_data_id[vertex1->edge_ids.count] = new_edge->id;
talloc_free(vertex1->edge_ids.data);
vertex1->edge_ids.data = new_data_id;
vertex1->edge_ids.count++;
new_data_id = talloc_realloc(vertex2, vertex2->edge_ids.data,
struct GUID, vertex2->edge_ids.count);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data_id, tmp_ctx);
new_data_id[vertex2->edge_ids.count] = new_edge->id;
talloc_free(vertex2->edge_ids.data);
vertex2->edge_ids.data = new_data_id;
vertex2->edge_ids.count++;
talloc_steal(graph, new_edge);
talloc_steal(mem_ctx, output_edges.data);
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* run Kruskal's minimum-cost spanning tree algorithm on the internal edges
* (that represent shortest paths in the original graph between colored
* vertices).
*/
static NTSTATUS kcctpl_kruskal(TALLOC_CTX *mem_ctx, struct kcctpl_graph *graph,
struct kcctpl_internal_edge_list internal_edges,
struct kcctpl_multi_edge_list *_output_edges)
{
uint32_t i, num_expected_tree_edges, cst_edges;
struct kcctpl_multi_edge_list output_edges;
num_expected_tree_edges = 0;
for (i = 0; i < graph->vertices.count; i++) {
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
talloc_free(vertex->edge_ids.data);
ZERO_STRUCT(vertex->edge_ids);
if (vertex->color == RED || vertex->color == WHITE) {
num_expected_tree_edges++;
}
}
qsort(internal_edges.data, internal_edges.count,
sizeof(struct kcctpl_internal_edge), kcctpl_sort_internal_edges);
cst_edges = 0;
ZERO_STRUCT(output_edges);
while (internal_edges.count > 0 &&
cst_edges < num_expected_tree_edges) {
struct kcctpl_internal_edge *edge, *new_data;
struct kcctpl_vertex *vertex1, *vertex2;
struct GUID comp1, comp2;
edge = &internal_edges.data[0];
vertex1 = kcctpl_find_vertex_by_guid(graph, edge->v1id);
if (!vertex1) {
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &edge->v1id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
vertex2 = kcctpl_find_vertex_by_guid(graph, edge->v2id);
if (!vertex2) {
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &edge->v2id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
comp1 = kcctpl_get_component_id(graph, vertex1);
comp2 = kcctpl_get_component_id(graph, vertex2);
if (!GUID_equal(&comp1, &comp2)) {
NTSTATUS status;
struct kcctpl_vertex *vertex;
cst_edges++;
status = kcctpl_add_out_edge(mem_ctx, graph,
output_edges, edge);
if (NT_STATUS_IS_ERR(status)) {
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to add an "
"output edge between %s and %s: %s\n",
GUID_string(tmp_ctx, &edge->v1id),
GUID_string(tmp_ctx, &edge->v2id),
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
vertex = kcctpl_find_vertex_by_guid(graph, comp1);
if (!vertex) {
TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
DEBUG(1, (__location__ ": failed to find "
"vertex %s\n", GUID_string(tmp_ctx,
&comp1)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
vertex->component_id = comp2;
}
internal_edges.data = internal_edges.data + 1;
new_data = talloc_realloc(mem_ctx, internal_edges.data,
struct kcctpl_internal_edge,
internal_edges.count - 1);
NT_STATUS_HAVE_NO_MEMORY(new_data);
talloc_free(internal_edges.data);
internal_edges.data = new_data;
internal_edges.count--;
}
*_output_edges = output_edges;
return NT_STATUS_OK;
}
/**
* count the number of components. a component is considered to be a bunch of
* colored vertices that are connected by the spanning tree. vertices whose
* component ID is the same as their vertex ID are the root of the connected
* component.
*/
static uint32_t kcctpl_count_components(struct kcctpl_graph *graph)
{
uint32_t num_components = 0, i;
for (i = 0; i < graph->vertices.count; i++) {
struct kcctpl_vertex *vertex;
struct GUID component_id;
vertex = &graph->vertices.data[i];
if (vertex->color == WHITE) {
continue;
}
component_id = kcctpl_get_component_id(graph, vertex);
if (GUID_equal(&component_id, &vertex->id)) {
vertex->component_index = num_components;
num_components++;
}
}
return num_components;
}
/**
* calculate the spanning tree and return the edges that include the vertex for
* the local site.
*/
static NTSTATUS kcctpl_get_spanning_tree_edges(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
uint32_t *_component_count,
struct kcctpl_multi_edge_list *_st_edge_list)
{
TALLOC_CTX *tmp_ctx;
struct kcctpl_internal_edge_list internal_edges;
uint32_t i, component_count;
NTSTATUS status;
struct kcctpl_multi_edge_list output_edges, st_edge_list;
ZERO_STRUCT(internal_edges);
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
for (i = 0; i < graph->edge_sets.count; i++) {
struct kcctpl_multi_edge_set *set;
struct GUID edge_type;
uint32_t j;
set = &graph->edge_sets.data[i];
edge_type = GUID_zero();
for (j = 0; j < graph->vertices.count; j++) {
struct kcctpl_vertex *vertex = &graph->vertices.data[j];
talloc_free(vertex->edge_ids.data);
ZERO_STRUCT(vertex->edge_ids.data);
}
for (j = 0; j < set->edge_ids.count; j++) {
struct GUID edge_id;
struct kcctpl_multi_edge *edge;
uint32_t k;
edge_id = set->edge_ids.data[j];
edge = kcctpl_find_edge_by_guid(graph, edge_id);
if (!edge) {
DEBUG(1, (__location__ ": failed to find a "
"graph edge with ID=%s\n",
GUID_string(tmp_ctx, &edge_id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
edge_type = edge->type;
for (k = 0; k < edge->vertex_ids.count; k++) {
struct GUID vertex_id, *new_data;
struct kcctpl_vertex *vertex;
vertex_id = edge->vertex_ids.data[k];
vertex = kcctpl_find_vertex_by_guid(graph,
vertex_id);
if (!vertex) {
DEBUG(1, (__location__ ": failed to "
"find a graph vertex with "
"ID=%s\n",
GUID_string(tmp_ctx,
&edge_id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
new_data = talloc_realloc(tmp_ctx,
vertex->edge_ids.data,
struct GUID,
vertex->edge_ids.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
tmp_ctx);
new_data[vertex->edge_ids.count] = edge->id;
vertex->edge_ids.data = new_data;
vertex->edge_ids.count++;
}
}
status = kcctpl_dijkstra(graph, edge_type, false);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to run Dijkstra's "
"algorithm: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
status = kcctpl_process_edge_set(tmp_ctx, graph, set,
internal_edges);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to process edge set "
"%s: %s\n", GUID_string(tmp_ctx, &set->id),
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
status = kcctpl_dijkstra(graph, edge_type, true);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to run Dijkstra's "
"algorithm: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
status = kcctpl_process_edge_set(tmp_ctx, graph, set,
internal_edges);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to process edge set "
"%s: %s\n", GUID_string(tmp_ctx, &set->id),
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
}
kcctpl_setup_vertices(graph);
status = kcctpl_process_edge_set(tmp_ctx, graph, NULL, internal_edges);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to process empty edge set: "
"%s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
status = kcctpl_kruskal(tmp_ctx, graph, internal_edges, &output_edges);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to run Kruskal's algorithm: "
"%s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
for (i = 0; i < graph->vertices.count; i++) {
struct kcctpl_vertex *vertex = &graph->vertices.data[i];
if (vertex->color == RED) {
vertex->dist_to_red = 0;
} else if (true) { /* TODO: if there exists a path from 'vertex'
to a RED vertex */
vertex->dist_to_red = -1; /* TODO: the length of the
shortest such path */
} else {
vertex->dist_to_red = UINT32_MAX;
}
}
component_count = kcctpl_count_components(graph);
status = kcctpl_copy_output_edges(ldb, tmp_ctx, graph, output_edges,
&st_edge_list);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to copy edge list: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
*_component_count = component_count;
talloc_steal(mem_ctx, st_edge_list.data);
*_st_edge_list = st_edge_list;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* creat an nTDSConnection object with the given parameters if one does not
* already exist.
*/
static NTSTATUS kcctpl_create_connection(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx,
struct ldb_message *cross_ref,
struct ldb_message *r_bridgehead,
struct ldb_message *transport,
struct ldb_message *l_bridgehead,
struct kcctpl_repl_info repl_info,
uint8_t schedule[84],
bool detect_failed_dcs,
bool partial_replica_okay,
struct GUID_list *_keep_connections)
{
TALLOC_CTX *tmp_ctx;
struct ldb_dn *r_site_dn, *l_site_dn, *servers_dn;
bool ok;
struct GUID r_site_guid, l_site_guid;
int ret;
struct message_list r_bridgeheads_all, l_bridgeheads_all,
r_bridgeheads_available, l_bridgeheads_available;
NTSTATUS status;
struct ldb_result *res;
const char * const attrs[] = { "objectGUID", "parent", "fromServer",
"transportType", "schedule", "options",
"enabledConnection", NULL };
uint32_t i, valid_connections;
struct GUID_list keep_connections;
tmp_ctx = talloc_new(ldb);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
r_site_dn = ldb_dn_copy(tmp_ctx, r_bridgehead->dn);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(r_site_dn, tmp_ctx);
ok = ldb_dn_remove_child_components(r_site_dn, 3);
if (!ok) {
talloc_free(tmp_ctx);
return NT_STATUS_NO_MEMORY;
}
ret = dsdb_find_guid_by_dn(ldb, r_site_dn, &r_site_guid);
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find objectGUID for object "
"%s: %s\n", ldb_dn_get_linearized(r_site_dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
l_site_dn = ldb_dn_copy(tmp_ctx, l_bridgehead->dn);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(l_site_dn, tmp_ctx);
ok = ldb_dn_remove_child_components(l_site_dn, 3);
if (!ok) {
talloc_free(tmp_ctx);
return NT_STATUS_NO_MEMORY;
}
ret = dsdb_find_guid_by_dn(ldb, l_site_dn, &l_site_guid);
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find objectGUID for object "
"%s: %s\n", ldb_dn_get_linearized(l_site_dn),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
r_site_guid, cross_ref,
transport, partial_replica_okay,
false, &r_bridgeheads_all);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
"%s\n", nt_errstr(status)));
return status;
}
status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
r_site_guid, cross_ref,
transport, partial_replica_okay,
detect_failed_dcs,
&r_bridgeheads_available);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
"%s\n", nt_errstr(status)));
return status;
}
status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
l_site_guid, cross_ref,
transport, partial_replica_okay,
false, &l_bridgeheads_all);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
"%s\n", nt_errstr(status)));
return status;
}
status = kcctpl_get_all_bridgehead_dcs(ldb, tmp_ctx,
l_site_guid, cross_ref,
transport, partial_replica_okay,
detect_failed_dcs,
&l_bridgeheads_available);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get all bridgehead DCs: "
"%s\n", nt_errstr(status)));
return status;
}
servers_dn = samdb_sites_dn(ldb, tmp_ctx);
if (!servers_dn) {
DEBUG(1, (__location__ ": failed to find our own Sites DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ok = ldb_dn_add_child_fmt(servers_dn, "CN=Servers");
if (!ok) {
talloc_free(tmp_ctx);
return NT_STATUS_NO_MEMORY;
}
ret = ldb_search(ldb, tmp_ctx, &res, servers_dn, LDB_SCOPE_SUBTREE,
attrs, "objectClass=nTDSConnection");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find nTDSConnection "
"objects: %s\n", ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
for (i = 0; i < res->count; i++) {
struct ldb_message *connection;
struct ldb_dn *parent_dn, *from_server;
connection = res->msgs[i];
parent_dn = ldb_dn_get_parent(tmp_ctx, connection->dn);
if (!parent_dn) {
DEBUG(1, (__location__ ": failed to get parent DN of "
"%s\n",
ldb_dn_get_linearized(connection->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
from_server = samdb_result_dn(ldb, tmp_ctx, connection,
"fromServer", NULL);
if (!from_server) {
DEBUG(1, (__location__ ": failed to find fromServer "
"attribute of object %s\n",
ldb_dn_get_linearized(connection->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (kcctpl_message_list_contains_dn(l_bridgeheads_all,
parent_dn) &&
kcctpl_message_list_contains_dn(r_bridgeheads_all,
from_server)) {
uint64_t conn_opts;
/* TODO: initialize conn_schedule from connection */
uint8_t conn_schedule[84];
struct ldb_dn *conn_transport_type;
conn_opts = samdb_result_int64(connection,
"options", 0);
conn_transport_type = samdb_result_dn(ldb, tmp_ctx,
connection,
"transportType",
NULL);
if (!conn_transport_type) {
DEBUG(1, (__location__ ": failed to find "
"transportType attribute of object "
"%s\n",
ldb_dn_get_linearized(connection->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if ((conn_opts & NTDSCONN_OPT_IS_GENERATED) &&
!(conn_opts & NTDSCONN_OPT_RODC_TOPOLOGY) &&
ldb_dn_compare(conn_transport_type,
transport->dn) == 0) {
if (!(conn_opts & NTDSCONN_OPT_USER_OWNED_SCHEDULE) &&
memcmp(&conn_schedule, &schedule, 84) != 0) {
/* TODO: perform an originating update
to set conn!schedule to schedule */
}
if ((conn_opts & NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT) &&
(conn_opts & NTDSCONN_OPT_USE_NOTIFY)) {
if (!(repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY)) {
/* TODO: perform an originating
update to clear bits
NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
and NTDSCONN_OPT_USE_NOTIFY
in conn!options */
}
} else if (repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY) {
/* TODO: perform an originating update
to set bits
NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT
and NTDSCONN_OPT_USE_NOTIFY in
conn!options */
}
if (conn_opts & NTDSCONN_OPT_TWOWAY_SYNC) {
if (!(repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC)) {
/* TODO: perform an originating
update to clear bit
NTDSCONN_OPT_TWOWAY_SYNC in
conn!options. */
}
} else if (repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC) {
/* TODO: perform an originating update
to set bit NTDSCONN_OPT_TWOWAY_SYNC
in conn!options. */
}
if (conn_opts & NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION) {
if (!(repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION)) {
/* TODO: perform an originating
update to clear bit
NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
in conn!options. */
}
} else if (repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION) {
/* TODO: perform an originating update
to set bit
NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION
in conn!options. */
}
}
}
}
ZERO_STRUCT(keep_connections);
valid_connections = 0;
for (i = 0; i < res->count; i++) {
struct ldb_message *connection;
struct ldb_dn *parent_dn, *from_server;
connection = res->msgs[i];
parent_dn = ldb_dn_get_parent(tmp_ctx, connection->dn);
if (!parent_dn) {
DEBUG(1, (__location__ ": failed to get parent DN of "
"%s\n",
ldb_dn_get_linearized(connection->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
from_server = samdb_result_dn(ldb, tmp_ctx, connection,
"fromServer", NULL);
if (!from_server) {
DEBUG(1, (__location__ ": failed to find fromServer "
"attribute of object %s\n",
ldb_dn_get_linearized(connection->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (kcctpl_message_list_contains_dn(l_bridgeheads_all,
parent_dn) &&
kcctpl_message_list_contains_dn(r_bridgeheads_all,
from_server)) {
uint64_t conn_opts;
struct ldb_dn *conn_transport_type;
conn_opts = samdb_result_int64(connection,
"options", 0);
conn_transport_type = samdb_result_dn(ldb, tmp_ctx,
connection,
"transportType",
NULL);
if (!conn_transport_type) {
DEBUG(1, (__location__ ": failed to find "
"transportType attribute of object "
"%s\n",
ldb_dn_get_linearized(connection->dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if ((!(conn_opts & NTDSCONN_OPT_IS_GENERATED) ||
ldb_dn_compare(conn_transport_type,
transport->dn) == 0) &&
!(conn_opts & NTDSCONN_OPT_RODC_TOPOLOGY)) {
struct GUID r_guid, l_guid, conn_guid;
bool failed_state_r, failed_state_l;
ret = dsdb_find_guid_by_dn(ldb, from_server,
&r_guid);
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to "
"find GUID for object %s\n",
ldb_dn_get_linearized(from_server)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = dsdb_find_guid_by_dn(ldb, parent_dn,
&l_guid);
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to "
"find GUID for object %s\n",
ldb_dn_get_linearized(parent_dn)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
status = kcctpl_bridgehead_dc_failed(ldb,
r_guid,
detect_failed_dcs,
&failed_state_r);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to "
"check if bridgehead DC has "
"failed: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
status = kcctpl_bridgehead_dc_failed(ldb,
l_guid,
detect_failed_dcs,
&failed_state_l);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to "
"check if bridgehead DC has "
"failed: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
if (!failed_state_r && !failed_state_l) {
valid_connections++;
}
conn_guid = samdb_result_guid(connection,
"objectGUID");
if (!kcctpl_guid_list_contains(keep_connections,
conn_guid)) {
struct GUID *new_data;
new_data = talloc_realloc(tmp_ctx,
keep_connections.data,
struct GUID,
keep_connections.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data,
tmp_ctx);
new_data[keep_connections.count] = conn_guid;
keep_connections.data = new_data;
keep_connections.count++;
}
}
}
}
if (valid_connections == 0) {
uint64_t opts = NTDSCONN_OPT_IS_GENERATED;
struct GUID new_guid, *new_data;
if (repl_info.options & NTDSSITELINK_OPT_USE_NOTIFY) {
opts |= NTDSCONN_OPT_OVERRIDE_NOTIFY_DEFAULT;
opts |= NTDSCONN_OPT_USE_NOTIFY;
}
if (repl_info.options & NTDSSITELINK_OPT_TWOWAY_SYNC) {
opts |= NTDSCONN_OPT_TWOWAY_SYNC;
}
if (repl_info.options & NTDSSITELINK_OPT_DISABLE_COMPRESSION) {
opts |= NTDSCONN_OPT_DISABLE_INTERSITE_COMPRESSION;
}
/* perform an originating update to create a new nTDSConnection
* object cn that is:
*
* - child of l_bridgehead
* - cn!enabledConnection = true
* - cn!options = opts
* - cn!transportType = t
* - cn!fromServer = r_bridgehead
* - cn!schedule = schedule
*/
/* TODO: what should be the new connection's GUID? */
new_guid = GUID_random();
new_data = talloc_realloc(tmp_ctx, keep_connections.data,
struct GUID,
keep_connections.count + 1);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(new_data, tmp_ctx);
new_data[keep_connections.count] = new_guid;
keep_connections.data = new_data;
keep_connections.count++;
}
talloc_steal(mem_ctx, keep_connections.data);
*_keep_connections = keep_connections;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* construct an NC replica graph for the NC identified by the given 'cross_ref',
* then create any additional nTDSConnection objects required.
*/
static NTSTATUS kcctpl_create_connections(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx,
struct kcctpl_graph *graph,
struct ldb_message *cross_ref,
bool detect_failed_dcs,
struct GUID_list keep_connections,
bool *_found_failed_dcs,
bool *_connected)
{
bool connected, found_failed_dcs, partial_replica_okay, rodc;
NTSTATUS status;
struct ldb_message *site;
TALLOC_CTX *tmp_ctx;
struct GUID site_guid;
struct kcctpl_vertex *site_vertex;
uint32_t component_count, i;
struct kcctpl_multi_edge_list st_edge_list;
struct ldb_dn *transports_dn;
const char * const attrs[] = { "bridgeheadServerListBL", "name",
"transportAddressAttribute", NULL };
connected = true;
status = kcctpl_color_vertices(ldb, graph, cross_ref, detect_failed_dcs,
&found_failed_dcs);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to color vertices: %s\n",
nt_errstr(status)));
return status;
}
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
site = kcctpl_local_site(ldb, tmp_ctx);
if (!site) {
DEBUG(1, (__location__ ": failed to find our own local DC's "
"site\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
site_guid = samdb_result_guid(site, "objectGUID");
site_vertex = kcctpl_find_vertex_by_guid(graph, site_guid);
if (!site_vertex) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &site_guid)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (site_vertex->color == WHITE) {
*_found_failed_dcs = found_failed_dcs;
*_connected = true;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
status = kcctpl_get_spanning_tree_edges(ldb, tmp_ctx, graph,
&component_count,
&st_edge_list);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed get spanning tree edges: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
if (component_count > 1) {
connected = false;
}
partial_replica_okay = (site_vertex->color == BLACK);
transports_dn = kcctpl_transports_dn(ldb, tmp_ctx);
if (!transports_dn) {
DEBUG(1, (__location__ ": failed to find our own Inter-Site "
"Transports DN\n"));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
rodc = samdb_rodc(ldb);
for (i = 0; i < st_edge_list.count; i++) {
struct kcctpl_multi_edge *edge;
struct GUID other_site_id;
struct kcctpl_vertex *other_site_vertex;
struct ldb_result *res;
int ret;
struct ldb_message *transport, *r_bridgehead, *l_bridgehead;
uint8_t schedule[84];
uint32_t first_available, j, interval;
edge = &st_edge_list.data[i];
if (edge->directed && !GUID_equal(&edge->vertex_ids.data[1],
&site_vertex->id)) {
continue;
}
if (GUID_equal(&edge->vertex_ids.data[0], &site_vertex->id)) {
other_site_id = edge->vertex_ids.data[1];
} else {
other_site_id = edge->vertex_ids.data[0];
}
other_site_vertex = kcctpl_find_vertex_by_guid(graph,
other_site_id);
if (!other_site_vertex) {
DEBUG(1, (__location__ ": failed to find vertex %s\n",
GUID_string(tmp_ctx, &other_site_id)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
ret = ldb_search(ldb, tmp_ctx, &res, transports_dn,
LDB_SCOPE_ONELEVEL, attrs,
"(&(objectClass=interSiteTransport)"
"(objectGUID=%s))", GUID_string(tmp_ctx,
&edge->type));
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find "
"interSiteTransport object %s: %s\n",
GUID_string(tmp_ctx, &edge->type),
ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
if (res->count == 0) {
DEBUG(1, (__location__ ": failed to find "
"interSiteTransport object %s\n",
GUID_string(tmp_ctx, &edge->type)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
transport = res->msgs[0];
status = kcctpl_get_bridgehead_dc(ldb, tmp_ctx,
other_site_vertex->id,
cross_ref, transport,
partial_replica_okay,
detect_failed_dcs,
&r_bridgehead);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get a bridgehead "
"DC: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
if (rodc) {
/* TODO: l_bridgehad = nTDSDSA of local DC */
} else {
status = kcctpl_get_bridgehead_dc(ldb, tmp_ctx,
site_vertex->id,
cross_ref, transport,
partial_replica_okay,
detect_failed_dcs,
&l_bridgehead);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to get a "
"bridgehead DC: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
}
ZERO_ARRAY(schedule);
first_available = 84;
interval = edge->repl_info.interval / 15;
for (j = 0; j < 84; j++) {
if (edge->repl_info.schedule[j] == 1) {
first_available = j;
break;
}
}
for (j = first_available; j < 84; j += interval) {
schedule[j] = 1;
}
status = kcctpl_create_connection(ldb, mem_ctx, cross_ref,
r_bridgehead, transport,
l_bridgehead, edge->repl_info,
schedule, detect_failed_dcs,
partial_replica_okay,
&keep_connections);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to create a "
"connection: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
}
*_found_failed_dcs = found_failed_dcs;
*_connected = connected;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
/**
* computes an NC replica graph for each NC replica that "should be present" on
* the local DC or "is present" on any DC in the same site as the local DC. for
* each edge directed to an NC replica on such a DC from an NC replica on a DC
* in another site, the KCC creates and nTDSConnection object to imply that edge
* if one does not already exist.
*/
static NTSTATUS kcctpl_create_intersite_connections(struct ldb_context *ldb,
TALLOC_CTX *mem_ctx,
struct GUID_list *_keep_connections,
bool *_all_connected)
{
struct GUID_list keep_connections;
bool all_connected;
TALLOC_CTX *tmp_ctx;
struct ldb_dn *partitions_dn;
struct ldb_result *res;
const char * const attrs[] = { "enabled", "systemFlags", "nCName",
NULL };
int ret;
uint32_t i;
all_connected = true;
ZERO_STRUCT(keep_connections);
tmp_ctx = talloc_new(mem_ctx);
NT_STATUS_HAVE_NO_MEMORY(tmp_ctx);
partitions_dn = samdb_partitions_dn(ldb, tmp_ctx);
NT_STATUS_HAVE_NO_MEMORY_AND_FREE(partitions_dn, tmp_ctx);
ret = ldb_search(ldb, tmp_ctx, &res, partitions_dn, LDB_SCOPE_ONELEVEL,
attrs, "objectClass=crossRef");
if (ret != LDB_SUCCESS) {
DEBUG(1, (__location__ ": failed to find crossRef objects: "
"%s\n", ldb_strerror(ret)));
talloc_free(tmp_ctx);
return NT_STATUS_INTERNAL_DB_CORRUPTION;
}
for (i = 0; i < res->count; i++) {
struct ldb_message *cross_ref;
unsigned int cr_enabled;
int64_t cr_flags;
struct kcctpl_graph *graph;
bool found_failed_dc, connected;
NTSTATUS status;
cross_ref = res->msgs[i];
cr_enabled = samdb_result_uint(cross_ref, "enabled", -1);
cr_flags = samdb_result_int64(cross_ref, "systemFlags", 0);
if ((cr_enabled == 0) || !(cr_flags & FLAG_CR_NTDS_NC)) {
continue;
}
status = kcctpl_setup_graph(ldb, tmp_ctx, &graph);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to create a graph: "
"%s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
status = kcctpl_create_connections(ldb, mem_ctx, graph,
cross_ref, true,
keep_connections,
&found_failed_dc,
&connected);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to create "
"connections: %s\n", nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
if (!connected) {
all_connected = false;
if (found_failed_dc) {
status = kcctpl_create_connections(ldb, mem_ctx,
graph,
cross_ref,
true,
keep_connections,
&found_failed_dc,
&connected);
if (NT_STATUS_IS_ERR(status)) {
DEBUG(1, (__location__ ": failed to "
"create connections: %s\n",
nt_errstr(status)));
talloc_free(tmp_ctx);
return status;
}
}
}
}
*_keep_connections = keep_connections;
*_all_connected = all_connected;
talloc_free(tmp_ctx);
return NT_STATUS_OK;
}
NTSTATUS kcctpl_test(struct ldb_context *ldb)
{
NTSTATUS status;
TALLOC_CTX *tmp_ctx = talloc_new(ldb);
struct GUID_list keep;
bool all_connected;
DEBUG(0, ("testing kcctpl_create_intersite_connections\n"));
status = kcctpl_create_intersite_connections(ldb, tmp_ctx, &keep,
&all_connected);
DEBUG(4, ("%s\n", nt_errstr(status)));
if (NT_STATUS_IS_OK(status)) {
uint32_t i;
DEBUG(4, ("all_connected=%d, %d GUIDs returned\n",
all_connected, keep.count));
for (i = 0; i < keep.count; i++) {
DEBUG(4, ("GUID %d: %s\n", i + 1,
GUID_string(tmp_ctx, &keep.data[i])));
}
}
talloc_free(tmp_ctx);
return status;
}