Merge branch 'master' of git://git.samba.org/samba

10 files changed, 2107 insertions, 1392 deletions

diff --git a/source4/dsdb/samdb/ldb_modules/config.mk b/source4/dsdb/samdb/ldb_modules/config.mk
index 3bd38606ea..6128dc9d65 100644
--- a/source4/dsdb/samdb/ldb_modules/config.mk
+++ b/source4/dsdb/samdb/ldb_modules/config.mk
@@ -1,7 +1,7 @@
 ################################################
 # Start SUBSYSTEM DSDB_MODULE_HELPERS
 [SUBSYSTEM::DSDB_MODULE_HELPERS]
-PRIVATE_DEPENDENCIES = LIBLDB
+PRIVATE_DEPENDENCIES = LIBLDB LIBNDR SAMDB_SCHEMA
 
 DSDB_MODULE_HELPERS_OBJ_FILES = $(dsdbsrcdir)/samdb/ldb_modules/util.o
 
@@ -12,7 +12,7 @@ $(eval $(call proto_header_template,$(dsdbsrcdir)/samdb/ldb_modules/util_proto.h
 # Start MODULE ldb_samba_dsdb
 [MODULE::ldb_samba_dsdb]
 SUBSYSTEM = LIBLDB
-PRIVATE_DEPENDENCIES = SAMDB LIBTALLOC LIBEVENTS LIBNDR
+PRIVATE_DEPENDENCIES = SAMDB LIBTALLOC LIBEVENTS LIBNDR DSDB_MODULE_HELPERS
 INIT_FUNCTION = LDB_MODULE(samba_dsdb)
 # End MODULE ldb_samba_dsdb
 ################################################
@@ -119,7 +119,7 @@ ldb_pdc_fsmo_OBJ_FILES = \
 # Start MODULE ldb_samldb
 [MODULE::ldb_samldb]
 SUBSYSTEM = LIBLDB
-PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LDAP_ENCODE SAMDB
+PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LDAP_ENCODE SAMDB DSDB_MODULE_HELPERS
 INIT_FUNCTION = LDB_MODULE(samldb)
 #
 # End MODULE ldb_samldb
@@ -242,7 +242,7 @@ ldb_extended_dn_out_OBJ_FILES = $(dsdbsrcdir)/samdb/ldb_modules/extended_dn_out.
 # Start MODULE ldb_extended_dn_store
 [MODULE::ldb_extended_dn_store]
 SUBSYSTEM = LIBLDB
-PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSAMBA-UTIL SAMDB
+PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSAMBA-UTIL SAMDB DSDB_MODULE_HELPERS
 INIT_FUNCTION = LDB_MODULE(extended_dn_store)
 # End MODULE ldb_extended_dn_store
 ################################################
@@ -301,7 +301,7 @@ ldb_update_keytab_OBJ_FILES = $(dsdbsrcdir)/samdb/ldb_modules/update_keytab.o
 [MODULE::ldb_objectclass]
 INIT_FUNCTION = LDB_MODULE(objectclass)
 CFLAGS = -Ilib/ldb/include
-PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSECURITY NDR_SECURITY SAMDB
+PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSECURITY NDR_SECURITY SAMDB DSDB_MODULE_HELPERS LIBSAMBA-UTIL
 SUBSYSTEM = LIBLDB
 # End MODULE ldb_objectclass
 ################################################
@@ -325,7 +325,7 @@ ldb_subtree_rename_OBJ_FILES = $(dsdbsrcdir)/samdb/ldb_modules/subtree_rename.o
 [MODULE::ldb_subtree_delete]
 INIT_FUNCTION = LDB_MODULE(subtree_delete)
 CFLAGS = -Ilib/ldb/include
-PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSAMBA-UTIL
+PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSAMBA-UTIL DSDB_MODULE_HELPERS
 SUBSYSTEM = LIBLDB
 # End MODULE ldb_subtree_rename
 ################################################
@@ -385,7 +385,7 @@ ldb_instancetype_OBJ_FILES = $(dsdbsrcdir)/samdb/ldb_modules/instancetype.o
 [MODULE::ldb_operational]
 SUBSYSTEM = LIBLDB
 CFLAGS = -Ilib/ldb/include
-PRIVATE_DEPENDENCIES = LIBTALLOC LIBTEVENT
+PRIVATE_DEPENDENCIES = LIBTALLOC LIBTEVENT LIBSAMBA-UTIL SAMDB_COMMON DSDB_MODULE_HELPERS
 INIT_FUNCTION = LDB_MODULE(operational)
 # End MODULE ldb_operational
 ################################################
@@ -397,7 +397,8 @@ ldb_operational_OBJ_FILES = $(dsdbsrcdir)/samdb/ldb_modules/operational.o
 [MODULE::ldb_descriptor]
 INIT_FUNCTION = LDB_MODULE(descriptor)
 CFLAGS = -Ilib/ldb/include
-PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSECURITY NDR_SECURITY SAMDB
+PRIVATE_DEPENDENCIES = LIBTALLOC LIBEVENTS LIBSECURITY NDR_SECURITY SAMDB \
+	DSDB_MODULE_HELPERS
 SUBSYSTEM = LIBLDB
 # End MODULE ldb_descriptor
 ################################################
diff --git a/source4/dsdb/samdb/ldb_modules/descriptor.c b/source4/dsdb/samdb/ldb_modules/descriptor.c
index d5a5e36e0e..f07743c4a2 100644
--- a/source4/dsdb/samdb/ldb_modules/descriptor.c
+++ b/source4/dsdb/samdb/ldb_modules/descriptor.c
@@ -285,6 +285,14 @@ static DATA_BLOB *get_new_descriptor(struct ldb_module *module,
 	if (!final_sd) {
 		return NULL;
 	}
+
+	if (final_sd->dacl) {
+		final_sd->dacl->revision = SECURITY_ACL_REVISION_ADS;
+	}
+	if (final_sd->sacl) {
+		final_sd->sacl->revision = SECURITY_ACL_REVISION_ADS;
+	}
+
 	sddl_sd = sddl_encode(mem_ctx, final_sd, domain_sid);
 	DEBUG(10, ("Object %s created with desriptor %s\n\n", ldb_dn_get_linearized(dn), sddl_sd));
 
diff --git a/source4/dsdb/samdb/ldb_modules/extended_dn_in.c b/source4/dsdb/samdb/ldb_modules/extended_dn_in.c
index 89ba7bb04b..33931167c5 100644
--- a/source4/dsdb/samdb/ldb_modules/extended_dn_in.c
+++ b/source4/dsdb/samdb/ldb_modules/extended_dn_in.c
@@ -34,6 +34,11 @@
 #include "ldb/include/ldb_errors.h"
 #include "ldb/include/ldb_module.h"
 
+/*
+  TODO: if relax is not set then we need to reject the fancy RMD_* and
+  DELETED extended DN codes
+ */
+
 /* search */
 struct extended_search_context {
 	struct ldb_module *module;
diff --git a/source4/dsdb/samdb/ldb_modules/linked_attributes.c b/source4/dsdb/samdb/ldb_modules/linked_attributes.c
index f54693d809..4c326bc240 100644
--- a/source4/dsdb/samdb/ldb_modules/linked_attributes.c
+++ b/source4/dsdb/samdb/ldb_modules/linked_attributes.c
@@ -33,1227 +33,155 @@
 #include "dlinklist.h"
 #include "dsdb/samdb/samdb.h"
 #include "librpc/gen_ndr/ndr_misc.h"
+#include "dsdb/samdb/ldb_modules/util.h"
 
-struct la_private {
-	struct la_context *la_list;
-};
-
-struct la_op_store {
-	struct la_op_store *next;
-	struct la_op_store *prev;
-	enum la_op {LA_OP_ADD, LA_OP_DEL} op;
-	struct GUID guid;
-	char *name;
-	char *value;
-};
-
-struct replace_context {
-	struct la_context *ac;
-	unsigned int num_elements;
-	struct ldb_message_element *el;
-};
-
-struct la_context {
-	struct la_context *next, *prev;
-	const struct dsdb_schema *schema;
-	struct ldb_module *module;
-	struct ldb_request *req;
-	struct ldb_dn *partition_dn;
-	struct ldb_dn *add_dn;
-	struct ldb_dn *del_dn;
-	struct replace_context *rc;
-	struct la_op_store *ops;
-	struct ldb_extended *op_response;
-	struct ldb_control **op_controls;
-};
-
-static struct la_context *linked_attributes_init(struct ldb_module *module,
-						 struct ldb_request *req)
-{
-	struct ldb_context *ldb;
-	struct la_context *ac;
-	const struct ldb_control *partition_ctrl;
-
-	ldb = ldb_module_get_ctx(module);
-
-	ac = talloc_zero(req, struct la_context);
-	if (ac == NULL) {
-		ldb_oom(ldb);
-		return NULL;
-	}
-
-	ac->schema = dsdb_get_schema(ldb);
-	ac->module = module;
-	ac->req = req;
-
-	/* remember the partition DN that came in, if given */
-	partition_ctrl = ldb_request_get_control(req, DSDB_CONTROL_CURRENT_PARTITION_OID);
-	if (partition_ctrl) {
-		const struct dsdb_control_current_partition *partition;
-		partition = talloc_get_type(partition_ctrl->data,
-					    struct dsdb_control_current_partition);
-		SMB_ASSERT(partition && partition->version == DSDB_CONTROL_CURRENT_PARTITION_VERSION);
-	
-		ac->partition_dn = ldb_dn_copy(ac, partition->dn);
-	}
-
-	return ac;
-}
 
-/*
-  turn a DN into a GUID
- */
-static int la_guid_from_dn(struct la_context *ac, struct ldb_dn *dn, struct GUID *guid)
+static int linked_attributes_fix_links(struct ldb_module *module,
+				       struct ldb_dn *old_dn, struct ldb_dn *new_dn,
+				       struct ldb_message_element *el, struct dsdb_schema *schema,
+				       const struct dsdb_attribute *schema_attr)
 {
-	int ret;
-	NTSTATUS status;
+	int i;
+	TALLOC_CTX *tmp_ctx = talloc_new(module);
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	const struct dsdb_attribute *target;
+	const char *attrs[2];
 
-	status = dsdb_get_extended_dn_guid(dn, guid);
-	if (NT_STATUS_IS_OK(status)) {
+	target = dsdb_attribute_by_linkID(schema, schema_attr->linkID ^ 1);
+	if (target == NULL) {
+		/* there is no counterpart link to change */
 		return LDB_SUCCESS;
 	}
-	if (!NT_STATUS_EQUAL(status, NT_STATUS_OBJECT_NAME_NOT_FOUND)) {
-		DEBUG(4,(__location__ ": Unable to parse GUID for dn %s\n",
-			 ldb_dn_get_linearized(dn)));
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	ret = dsdb_find_guid_by_dn(ldb_module_get_ctx(ac->module), dn, guid);
-	if (ret != LDB_SUCCESS) {
-		DEBUG(4,(__location__ ": Failed to find GUID for dn %s\n",
-			 ldb_dn_get_linearized(dn)));
-		return ret;
-	}
-	return LDB_SUCCESS;
-}
-
-
-/* Common routine to handle reading the attributes and creating a
- * series of modify requests */
-static int la_store_op(struct la_context *ac,
-		       enum la_op op, struct ldb_val *dn,
-		       const char *name)
-{
-	struct ldb_context *ldb;
-	struct la_op_store *os;
-	struct ldb_dn *op_dn;
-	int ret;
-
-	ldb = ldb_module_get_ctx(ac->module);
-
-	op_dn = ldb_dn_from_ldb_val(ac, ldb, dn);
-	if (!op_dn) {
-		ldb_asprintf_errstring(ldb, 
-				       "could not parse attribute as a DN");
-		return LDB_ERR_INVALID_DN_SYNTAX;
-	}
-
-	os = talloc_zero(ac, struct la_op_store);
-	if (!os) {
-		ldb_oom(ldb);
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	os->op = op;
-
-	ret = la_guid_from_dn(ac, op_dn, &os->guid);
-	if (ret == LDB_ERR_NO_SUCH_OBJECT && ac->req->operation == LDB_DELETE) {
-		/* we are deleting an object, and we've found it has a
-		 * forward link to a target that no longer
-		 * exists. This is not an error in the delete, and we
-		 * should just not do the deferred delete of the
-		 * target attribute
-		 */
-		talloc_free(os);
-		return LDB_SUCCESS;
-	}
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-
-	os->name = talloc_strdup(os, name);
-	if (!os->name) {
-		ldb_oom(ldb);
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
 
-	/* Do deletes before adds */
-	if (op == LA_OP_ADD) {
-		DLIST_ADD_END(ac->ops, os, struct la_op_store *);
-	} else {
-		/* By adding to the head of the list, we do deletes before
-		 * adds when processing a replace */
-		DLIST_ADD(ac->ops, os);
-	}
-
-	return LDB_SUCCESS;
-}
-
-static int la_op_search_callback(struct ldb_request *req,
-				 struct ldb_reply *ares);
-static int la_queue_mod_request(struct la_context *ac);
-static int la_down_req(struct la_context *ac);
-
-
-
-/* add */
-static int linked_attributes_add(struct ldb_module *module, struct ldb_request *req)
-{
-	struct ldb_context *ldb;
-	const struct dsdb_attribute *target_attr;
-	struct la_context *ac;
-	const char *attr_name;
-	int ret;
-	int i, j;
-
-	ldb = ldb_module_get_ctx(module);
-
-	if (ldb_dn_is_special(req->op.add.message->dn)) {
-		/* do not manipulate our control entries */
-		return ldb_next_request(module, req);
-	}
-
-	ac = linked_attributes_init(module, req);
-	if (!ac) {
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
+	attrs[0] = target->lDAPDisplayName;
+	attrs[1] = NULL;
 
-	if (!ac->schema) {
-		/* without schema, this doesn't make any sense */
-		talloc_free(ac);
-		return ldb_next_request(module, req);
-	}
+	for (i=0; i<el->num_values; i++) {
+		struct dsdb_dn *dsdb_dn;
+		int ret, j;
+		struct ldb_result *res;
+		struct ldb_message *msg;
+		struct ldb_message_element *el2;
 
-	/* Need to ensure we only have forward links being specified */
-	for (i=0; i < req->op.add.message->num_elements; i++) {
-		const struct ldb_message_element *el = &req->op.add.message->elements[i];
-		const struct dsdb_attribute *schema_attr
-			= dsdb_attribute_by_lDAPDisplayName(ac->schema, el->name);
-		if (!schema_attr) {
-			ldb_asprintf_errstring(ldb, 
-					       "attribute %s is not a valid attribute in schema", el->name);
-			return LDB_ERR_OBJECT_CLASS_VIOLATION;			
+		dsdb_dn = dsdb_dn_parse(tmp_ctx, ldb, &el->values[i], schema_attr->syntax->ldap_oid);
+		if (dsdb_dn == NULL) {
+			talloc_free(tmp_ctx);
+			return LDB_ERR_INVALID_DN_SYNTAX;
 		}
-		/* We have a valid attribute, now find out if it is linked */
-		if (schema_attr->linkID == 0) {
-			continue;
-		}
-		
-		if ((schema_attr->linkID & 1) == 1) {
-			/* Odd is for the target.  Illegal to modify */
-			ldb_asprintf_errstring(ldb, 
-					       "attribute %s must not be modified directly, it is a linked attribute", el->name);
-			return LDB_ERR_UNWILLING_TO_PERFORM;
-		}
-		
-		/* Even link IDs are for the originating attribute */
-		target_attr = dsdb_attribute_by_linkID(ac->schema, schema_attr->linkID + 1);
-		if (!target_attr) {
-			/*
-			 * windows 2003 has a broken schema where
-			 * the definition of msDS-IsDomainFor
-			 * is missing (which is supposed to be
-			 * the backlink of the msDS-HasDomainNCs
-			 * attribute
-			 */
-			continue;
-		}
-
-		attr_name = target_attr->lDAPDisplayName;
 
-		for (j = 0; j < el->num_values; j++) {
-			ret = la_store_op(ac, LA_OP_ADD,
-					  &el->values[j],
-					  attr_name);
-			if (ret != LDB_SUCCESS) {
-				return ret;
-			}
+		ret = dsdb_module_search_dn(module, tmp_ctx, &res, dsdb_dn->dn,
+					    attrs,
+					    DSDB_SEARCH_SHOW_DELETED |
+					    DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT |
+					    DSDB_SEARCH_REVEAL_INTERNALS);
+		if (ret != LDB_SUCCESS) {
+			ldb_asprintf_errstring(ldb, "Linked attribute %s->%s between %s and %s - remote not found - %s",
+					       el->name, target->lDAPDisplayName,
+					       ldb_dn_get_linearized(old_dn),
+					       ldb_dn_get_linearized(dsdb_dn->dn),
+					       ldb_errstring(ldb));
+			talloc_free(tmp_ctx);
+			return ret;
 		}
-	}
-
-	/* if no linked attributes are present continue */
-	if (ac->ops == NULL) {
-		/* nothing to do for this module, proceed */
-		talloc_free(ac);
-		return ldb_next_request(module, req);
-	}
-
-	/* start with the original request */
-	return la_down_req(ac);
-}
-
-/* For a delete or rename, we need to find out what linked attributes
- * are currently on this DN, and then deal with them.  This is the
- * callback to the base search */
+		msg = res->msgs[0];
 
-static int la_mod_search_callback(struct ldb_request *req, struct ldb_reply *ares)
-{
-	struct ldb_context *ldb;
-	const struct dsdb_attribute *schema_attr;
-	const struct dsdb_attribute *target_attr;
-	struct ldb_message_element *search_el;
-	struct replace_context *rc;
-	struct la_context *ac;
-	const char *attr_name;
-	int i, j;
-	int ret = LDB_SUCCESS;
-
-	ac = talloc_get_type(req->context, struct la_context);
-	ldb = ldb_module_get_ctx(ac->module);
-	rc = ac->rc;
-
-	if (!ares) {
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	if (ares->error != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, ares->controls,
-					ares->response, ares->error);
-	}
-
-	/* Only entries are interesting, and we only want the olddn */
-	switch (ares->type) {
-	case LDB_REPLY_ENTRY:
-
-		if (ldb_dn_compare(ares->message->dn, ac->req->op.mod.message->dn) != 0) {
-			ldb_asprintf_errstring(ldb, 
-					       "linked_attributes: %s is not the DN we were looking for", ldb_dn_get_linearized(ares->message->dn));
-			/* Guh?  We only asked for this DN */
-			talloc_free(ares);
-			return ldb_module_done(ac->req, NULL, NULL,
-						LDB_ERR_OPERATIONS_ERROR);
+		if (msg->num_elements != 1 ||
+		    ldb_attr_cmp(msg->elements[0].name, target->lDAPDisplayName) != 0) {
+			ldb_set_errstring(ldb, "Bad msg elements in linked_attributes_fix_links");
+			talloc_free(tmp_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
 		}
+		el2 = &msg->elements[0];
 
-		ac->add_dn = ac->del_dn = talloc_steal(ac, ares->message->dn);
-
-		/* We don't populate 'rc' for ADD - it can't be deleting elements anyway */
-		for (i = 0; rc && i < rc->num_elements; i++) {
-
-			schema_attr = dsdb_attribute_by_lDAPDisplayName(ac->schema, rc->el[i].name);
-			if (!schema_attr) {
-				ldb_asprintf_errstring(ldb,
-					"attribute %s is not a valid attribute in schema",
-					rc->el[i].name);
-				talloc_free(ares);
-				return ldb_module_done(ac->req, NULL, NULL,
-						LDB_ERR_OBJECT_CLASS_VIOLATION);
-			}
-
-			search_el = ldb_msg_find_element(ares->message,
-							 rc->el[i].name);
+		el2->flags = LDB_FLAG_MOD_REPLACE;
 
-			/* See if this element already exists */
-			/* otherwise just ignore as
-			 * the add has already been scheduled */
-			if ( ! search_el) {
-				continue;
+		/* find our DN in the values */
+		for (j=0; j<el2->num_values; j++) {
+			struct dsdb_dn *dsdb_dn2;
+			dsdb_dn2 = dsdb_dn_parse(msg, ldb, &el2->values[j], target->syntax->ldap_oid);
+			if (dsdb_dn2 == NULL) {
+				talloc_free(tmp_ctx);
+				return LDB_ERR_INVALID_DN_SYNTAX;
 			}
-
-			target_attr = dsdb_attribute_by_linkID(ac->schema, schema_attr->linkID + 1);
-			if (!target_attr) {
-				/*
-				 * windows 2003 has a broken schema where
-				 * the definition of msDS-IsDomainFor
-				 * is missing (which is supposed to be
-				 * the backlink of the msDS-HasDomainNCs
-				 * attribute
-				 */
+			if (ldb_dn_compare(old_dn, dsdb_dn2->dn) != 0) {
 				continue;
 			}
-			attr_name = target_attr->lDAPDisplayName;
-
-			/* Now we know what was there, we can remove it for the re-add */
-			for (j = 0; j < search_el->num_values; j++) {
-				ret = la_store_op(ac, LA_OP_DEL,
-						  &search_el->values[j],
-						  attr_name);
-				if (ret != LDB_SUCCESS) {
-					talloc_free(ares);
-					return ldb_module_done(ac->req,
-							       NULL, NULL, ret);
-				}
-			}
-		}
-
-		break;
-
-	case LDB_REPLY_REFERRAL:
-		/* ignore */
-		break;
-
-	case LDB_REPLY_DONE:
-
-		talloc_free(ares);
-
-		if (ac->req->operation == LDB_ADD) {
-			/* Start the modifies to the backlinks */
-			ret = la_queue_mod_request(ac);
-
-			if (ret != LDB_SUCCESS) {
-				return ldb_module_done(ac->req, NULL, NULL,
-						       ret);
-			}
-		} else {
-			/* Start with the original request */
-			ret = la_down_req(ac);
+			ret = ldb_dn_update_components(dsdb_dn2->dn, new_dn);
 			if (ret != LDB_SUCCESS) {
-				return ldb_module_done(ac->req, NULL, NULL, ret);
-			}
-		}
-		return LDB_SUCCESS;
-	}
-
-	talloc_free(ares);
-	return ret;
-}
-
-
-/* modify */
-static int linked_attributes_modify(struct ldb_module *module, struct ldb_request *req)
-{
-	/* Look over list of modifications */
-	/* Find if any are for linked attributes */
-	/* Determine the effect of the modification */
-	/* Apply the modify to the linked entry */
-
-	struct ldb_context *ldb;
-	int i, j;
-	struct la_context *ac;
-	struct ldb_request *search_req;
-	const char **attrs;
-
-	int ret;
-
-	ldb = ldb_module_get_ctx(module);
-
-	if (ldb_dn_is_special(req->op.mod.message->dn)) {
-		/* do not manipulate our control entries */
-		return ldb_next_request(module, req);
-	}
-
-	ac = linked_attributes_init(module, req);
-	if (!ac) {
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	if (!ac->schema) {
-		/* without schema, this doesn't make any sense */
-		return ldb_next_request(module, req);
-	}
-
-	ac->rc = talloc_zero(ac, struct replace_context);
-	if (!ac->rc) {
-		ldb_oom(ldb);
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	for (i=0; i < req->op.mod.message->num_elements; i++) {
-		bool store_el = false;
-		const char *attr_name;
-		const struct dsdb_attribute *target_attr;
-		const struct ldb_message_element *el = &req->op.mod.message->elements[i];
-		const struct dsdb_attribute *schema_attr
-			= dsdb_attribute_by_lDAPDisplayName(ac->schema, el->name);
-		if (!schema_attr) {
-			ldb_asprintf_errstring(ldb, 
-					       "attribute %s is not a valid attribute in schema", el->name);
-			return LDB_ERR_OBJECT_CLASS_VIOLATION;			
-		}
-		/* We have a valid attribute, now find out if it is linked */
-		if (schema_attr->linkID == 0) {
-			continue;
-		}
-		
-		if ((schema_attr->linkID & 1) == 1) {
-			/* Odd is for the target.  Illegal to modify */
-			ldb_asprintf_errstring(ldb, 
-					       "attribute %s must not be modified directly, it is a linked attribute", el->name);
-			return LDB_ERR_UNWILLING_TO_PERFORM;
-		}
-		
-		/* Even link IDs are for the originating attribute */
-		
-		/* Now find the target attribute */
-		target_attr = dsdb_attribute_by_linkID(ac->schema, schema_attr->linkID + 1);
-		if (!target_attr) {
-			/*
-			 * windows 2003 has a broken schema where
-			 * the definition of msDS-IsDomainFor
-			 * is missing (which is supposed to be
-			 * the backlink of the msDS-HasDomainNCs
-			 * attribute
-			 */
-			continue;
-		}
-
-		attr_name = target_attr->lDAPDisplayName;
-	
-		switch (el->flags & LDB_FLAG_MOD_MASK) {
-		case LDB_FLAG_MOD_REPLACE:
-			/* treat as just a normal add the delete part is handled by the callback */
-			store_el = true;
-
-			/* break intentionally missing */
-
-		case LDB_FLAG_MOD_ADD:
-
-			/* For each value being added, we need to setup the adds */
-			for (j = 0; j < el->num_values; j++) {
-				ret = la_store_op(ac, LA_OP_ADD,
-						  &el->values[j],
-						  attr_name);
-				if (ret != LDB_SUCCESS) {
-					return ret;
-				}
-			}
-			break;
-
-		case LDB_FLAG_MOD_DELETE:
-
-			if (el->num_values) {
-				/* For each value being deleted, we need to setup the delete */
-				for (j = 0; j < el->num_values; j++) {
-					ret = la_store_op(ac, LA_OP_DEL,
-							  &el->values[j],
-							  attr_name);
-					if (ret != LDB_SUCCESS) {
-						return ret;
-					}
-				}
-			} else {
-				/* Flag that there was a DELETE
-				 * without a value specified, so we
-				 * need to look for the old value */
-				store_el = true;
+				talloc_free(tmp_ctx);
+				return ret;
 			}
 
-			break;
+			el2->values[j] = data_blob_string_const(
+				dsdb_dn_get_extended_linearized(el2->values, dsdb_dn2, 1));
 		}
 
-		if (store_el) {
-			struct ldb_message_element *search_el;
-
-			search_el = talloc_realloc(ac->rc, ac->rc->el,
-						   struct ldb_message_element,
-						   ac->rc->num_elements +1);
-			if (!search_el) {
-				ldb_oom(ldb);
-				return LDB_ERR_OPERATIONS_ERROR;
-			}
-			ac->rc->el = search_el;
-
-			ac->rc->el[ac->rc->num_elements] = *el;
-			ac->rc->num_elements++;
-		}
-	}
-	
-	if (ac->ops || ac->rc->el) {
-		/* both replace and delete without values are handled in the callback
-		 * after the search on the entry to be modified is performed */
-		
-		attrs = talloc_array(ac->rc, const char *, ac->rc->num_elements + 1);
-		if (!attrs) {
-			ldb_oom(ldb);
-			return LDB_ERR_OPERATIONS_ERROR;
-		}
-		for (i = 0; ac->rc && i < ac->rc->num_elements; i++) {
-			attrs[i] = ac->rc->el[i].name;
+		ret = dsdb_check_single_valued_link(target, el2);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
 		}
-		attrs[i] = NULL;
-		
-		/* The callback does all the hard work here */
-		ret = ldb_build_search_req(&search_req, ldb, ac,
-					   req->op.mod.message->dn,
-					   LDB_SCOPE_BASE,
-					   "(objectClass=*)", attrs,
-					   NULL,
-					   ac, la_mod_search_callback,
-					   req);
 
-		/* We need to figure out our own extended DN, to fill in as the backlink target */
-		if (ret == LDB_SUCCESS) {
-			ret = ldb_request_add_control(search_req,
-						      LDB_CONTROL_EXTENDED_DN_OID,
-						      false, NULL);
-		}
-		if (ret == LDB_SUCCESS) {
-			talloc_steal(search_req, attrs);
-			
-			ret = ldb_next_request(module, search_req);
+		ret = dsdb_module_modify(module, msg, DSDB_MODIFY_RELAX);
+		if (ret != LDB_SUCCESS) {
+			ldb_asprintf_errstring(ldb, "Linked attribute %s->%s between %s and %s - update failed - %s",
+					       el->name, target->lDAPDisplayName,
+					       ldb_dn_get_linearized(old_dn),
+					       ldb_dn_get_linearized(dsdb_dn->dn),
+					       ldb_errstring(ldb));
+			talloc_free(tmp_ctx);
+			return ret;
 		}
-
-	} else {
-		/* nothing to do for this module, proceed */
-		talloc_free(ac);
-		ret = ldb_next_request(module, req);
 	}
 
-	return ret;
+	talloc_free(tmp_ctx);
+	return LDB_SUCCESS;
 }
 
-/* delete */
-static int linked_attributes_del(struct ldb_module *module, struct ldb_request *req)
-{
-	struct ldb_context *ldb;
-	struct ldb_request *search_req;
-	struct la_context *ac;
-	const char **attrs;
-	WERROR werr;
-	int ret;
-
-	/* This gets complex:  We need to:
-	   - Do a search for the entry
-	   - Wait for these result to appear
-	   - In the callback for the result, issue a modify
-		request based on the linked attributes found
-	   - Wait for each modify result
-	   - Regain our sainity
-	*/
-
-	ldb = ldb_module_get_ctx(module);
-
-	ac = linked_attributes_init(module, req);
-	if (!ac) {
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	if (!ac->schema) {
-		/* without schema, this doesn't make any sense */
-		return ldb_next_request(module, req);
-	}
-
-	werr = dsdb_linked_attribute_lDAPDisplayName_list(ac->schema, ac, &attrs);
-	if (!W_ERROR_IS_OK(werr)) {
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	ret = ldb_build_search_req(&search_req, ldb, req,
-				   req->op.del.dn, LDB_SCOPE_BASE,
-				   "(objectClass=*)", attrs,
-				   NULL,
-				   ac, la_op_search_callback,
-				   req);
-
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-
-	talloc_steal(search_req, attrs);
-
-	return ldb_next_request(module, search_req);
-}
 
 /* rename */
 static int linked_attributes_rename(struct ldb_module *module, struct ldb_request *req)
 {
-	struct la_context *ac;
-
-	/* This gets complex:  We need to:
-	   - Do a search for the entry
-	   - Wait for these result to appear
-	   - In the callback for the result, issue a modify
-		request based on the linked attributes found
-	   - Wait for each modify result
-	   - Regain our sainity
+	struct ldb_result *res;
+	struct ldb_message *msg;
+	int ret, i;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	struct dsdb_schema *schema = dsdb_get_schema(ldb);
+	/*
+	   - load the current msg
+	   - find any linked attributes
+	   - if its a link then find the target object
+	   - modify the target linked attributes with the new DN
 	*/
-
-	ac = linked_attributes_init(module, req);
-	if (!ac) {
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	if (!ac->schema) {
-		/* without schema, this doesn't make any sense */
-		return ldb_next_request(module, req);
-	}
-
-	/* start with the original request */
-	return la_down_req(ac);
-}
-
-
-static int la_op_search_callback(struct ldb_request *req,
-				 struct ldb_reply *ares)
-{
-	struct ldb_context *ldb;
-	struct la_context *ac;
-	const struct dsdb_attribute *schema_attr;
-	const struct dsdb_attribute *target_attr;
-	const struct ldb_message_element *el;
-	const char *attr_name;
-	int i, j;
-	int ret;
-
-	ac = talloc_get_type(req->context, struct la_context);
-	ldb = ldb_module_get_ctx(ac->module);
-
-	if (!ares) {
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	if (ares->error != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, ares->controls,
-					ares->response, ares->error);
-	}
-
-	/* Only entries are interesting, and we only want the olddn */
-	switch (ares->type) {
-	case LDB_REPLY_ENTRY:
-		ret = ldb_dn_compare(ares->message->dn, req->op.search.base);
-		if (ret != 0) {
-			/* Guh?  We only asked for this DN */
-			talloc_free(ares);
-			return ldb_module_done(ac->req, NULL, NULL,
-						LDB_ERR_OPERATIONS_ERROR);
-		}
-		if (ares->message->num_elements == 0) {
-			/* only bother at all if there were some
-			 * linked attributes found */
-			talloc_free(ares);
-			return LDB_SUCCESS;
-		}
-
-		switch (ac->req->operation) {
-		case LDB_DELETE:
-			ac->del_dn = talloc_steal(ac, ares->message->dn);
-			break;
-		case LDB_RENAME:
-			ac->add_dn = talloc_steal(ac, ares->message->dn); 
-			ac->del_dn = talloc_steal(ac, ac->req->op.rename.olddn);
-			break;
-		default:
-			talloc_free(ares);
-			ldb_set_errstring(ldb,
-					  "operations must be delete or rename");
-			return ldb_module_done(ac->req, NULL, NULL,
-						LDB_ERR_OPERATIONS_ERROR);
-		}
-
-		for (i = 0; i < ares->message->num_elements; i++) {
-			el = &ares->message->elements[i];
-
-			schema_attr = dsdb_attribute_by_lDAPDisplayName(ac->schema, el->name);
-			if (!schema_attr) {
-				ldb_asprintf_errstring(ldb,
-					"attribute %s is not a valid attribute"
-					" in schema", el->name);
-				talloc_free(ares);
-				return ldb_module_done(ac->req, NULL, NULL,
-						LDB_ERR_OBJECT_CLASS_VIOLATION);
-			}
-
-			/* Valid attribute, now find out if it is linked */
-			if (schema_attr->linkID == 0) {
-				/* Not a linked attribute, skip */
-				continue;
-			}
-
-			if ((schema_attr->linkID & 1) == 0) {
-				/* Odd is for the target. */
-				target_attr = dsdb_attribute_by_linkID(ac->schema, schema_attr->linkID + 1);
-				if (!target_attr) {
-					continue;
-				}
-				attr_name = target_attr->lDAPDisplayName;
-			} else {
-				target_attr = dsdb_attribute_by_linkID(ac->schema, schema_attr->linkID - 1);
-				if (!target_attr) {
-					continue;
-				}
-				attr_name = target_attr->lDAPDisplayName;
-			}
-			for (j = 0; j < el->num_values; j++) {
-				ret = la_store_op(ac, LA_OP_DEL,
-						  &el->values[j],
-						  attr_name);
-
-				/* for renames, ensure we add it back */
-				if (ret == LDB_SUCCESS
-				    && ac->req->operation == LDB_RENAME) {
-					ret = la_store_op(ac, LA_OP_ADD,
-							  &el->values[j],
-							  attr_name);
-				}
-				if (ret != LDB_SUCCESS) {
-					talloc_free(ares);
-					return ldb_module_done(ac->req,
-							       NULL, NULL, ret);
-				}
-			}
-		}
-
-		break;
-
-	case LDB_REPLY_REFERRAL:
-		/* ignore */
-		break;
-
-	case LDB_REPLY_DONE:
-
-		talloc_free(ares);
-
-
-		switch (ac->req->operation) {
-		case LDB_DELETE:
-			/* start the mod requests chain */
-			ret = la_down_req(ac);
-			if (ret != LDB_SUCCESS) {
-				return ldb_module_done(ac->req, NULL, NULL, ret);
-			}
-			return ret;
-
-		case LDB_RENAME:	
-			/* start the mod requests chain */
-			ret = la_queue_mod_request(ac);
-			if (ret != LDB_SUCCESS) {
-				return ldb_module_done(ac->req, NULL, NULL,
-						       ret);
-			}	
-			return ret;
-			
-		default:
-			talloc_free(ares);
-			ldb_set_errstring(ldb,
-					  "operations must be delete or rename");
-			return ldb_module_done(ac->req, NULL, NULL,
-						LDB_ERR_OPERATIONS_ERROR);
-		}
-	}
-
-	talloc_free(ares);
-	return LDB_SUCCESS;
-}
-
-/* queue a linked attributes modify request in the la_private
-   structure */
-static int la_queue_mod_request(struct la_context *ac)
-{
-	struct la_private *la_private = 
-		talloc_get_type(ldb_module_get_private(ac->module), struct la_private);
-
-	if (la_private == NULL) {
-		ldb_debug(ldb_module_get_ctx(ac->module), LDB_DEBUG_ERROR, __location__ ": No la_private transaction setup\n");
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	talloc_steal(la_private, ac);
-	DLIST_ADD(la_private->la_list, ac);
-
-	return ldb_module_done(ac->req, ac->op_controls,
-			       ac->op_response, LDB_SUCCESS);
-}
-
-/* Having done the original operation, then try to fix up all the linked attributes for modify and delete */
-static int la_mod_del_callback(struct ldb_request *req, struct ldb_reply *ares)
-{
-	int ret;
-	struct la_context *ac;
-	struct ldb_context *ldb;
-
-	ac = talloc_get_type(req->context, struct la_context);
-	ldb = ldb_module_get_ctx(ac->module);
-
-	if (!ares) {
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	if (ares->error != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, ares->controls,
-					ares->response, ares->error);
-	}
-
-	if (ares->type != LDB_REPLY_DONE) {
-		ldb_set_errstring(ldb,
-				  "invalid ldb_reply_type in callback");
-		talloc_free(ares);
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	
-	ac->op_controls = talloc_steal(ac, ares->controls);
-	ac->op_response = talloc_steal(ac, ares->response);
-
-	/* If we have modfies to make, this is the time to do them for modify and delete */
-	ret = la_queue_mod_request(ac);
-	
-	if (ret != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, NULL, NULL, ret);
-	}
-	talloc_free(ares);
-
-	/* la_queue_mod_request has already sent the callbacks */
-	return LDB_SUCCESS;
-
-}
-
-/* Having done the original rename try to fix up all the linked attributes */
-static int la_rename_callback(struct ldb_request *req, struct ldb_reply *ares)
-{
-	int ret;
-	struct la_context *ac;
-	struct ldb_request *search_req;
-	const char **attrs;
-	WERROR werr;
-	struct ldb_context *ldb;
-
-	ac = talloc_get_type(req->context, struct la_context);
-	ldb = ldb_module_get_ctx(ac->module);
-
-	if (!ares) {
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	if (ares->error != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, ares->controls,
-					ares->response, ares->error);
-	}
-
-	if (ares->type != LDB_REPLY_DONE) {
-		ldb_set_errstring(ldb,
-				  "invalid ldb_reply_type in callback");
-		talloc_free(ares);
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	
-	werr = dsdb_linked_attribute_lDAPDisplayName_list(ac->schema, ac, &attrs);
-	if (!W_ERROR_IS_OK(werr)) {
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-	
-	ret = ldb_build_search_req(&search_req, ldb, req,
-				   ac->req->op.rename.newdn, LDB_SCOPE_BASE,
-				   "(objectClass=*)", attrs,
-				   NULL,
-				   ac, la_op_search_callback,
-				   req);
-	
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-		
-	talloc_steal(search_req, attrs);
-
-	if (ret == LDB_SUCCESS) {
-		ret = ldb_request_add_control(search_req,
-					      LDB_CONTROL_EXTENDED_DN_OID,
-					      false, NULL);
-	}
-	if (ret != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, NULL, NULL,
-				       ret);
-	}
-	
-	ac->op_controls = talloc_steal(ac, ares->controls);
-	ac->op_response = talloc_steal(ac, ares->response);
-
-	return ldb_next_request(ac->module, search_req);
-}
-
-/* Having done the original add, then try to fix up all the linked attributes
-
-  This is done after the add so the links can get the extended DNs correctly.
- */
-static int la_add_callback(struct ldb_request *req, struct ldb_reply *ares)
-{
-	int ret;
-	struct la_context *ac;
-	struct ldb_context *ldb;
-
-	ac = talloc_get_type(req->context, struct la_context);
-	ldb = ldb_module_get_ctx(ac->module);
-
-	if (!ares) {
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	if (ares->error != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, ares->controls,
-					ares->response, ares->error);
-	}
-
-	if (ares->type != LDB_REPLY_DONE) {
-		ldb_set_errstring(ldb,
-				  "invalid ldb_reply_type in callback");
-		talloc_free(ares);
-		return ldb_module_done(ac->req, NULL, NULL,
-					LDB_ERR_OPERATIONS_ERROR);
-	}
-	
-	if (ac->ops) {
-		struct ldb_request *search_req;
-		static const char *attrs[] = { NULL };
-		
-		/* The callback does all the hard work here - we need
-		 * the objectGUID and SID of the added record */
-		ret = ldb_build_search_req(&search_req, ldb, ac,
-					   ac->req->op.add.message->dn,
-					   LDB_SCOPE_BASE,
-					   "(objectClass=*)", attrs,
-					   NULL,
-					   ac, la_mod_search_callback,
-					   ac->req);
-		
-		if (ret == LDB_SUCCESS) {
-			ret = ldb_request_add_control(search_req,
-						      LDB_CONTROL_EXTENDED_DN_OID,
-						      false, NULL);
-		}
-		if (ret != LDB_SUCCESS) {
-			return ldb_module_done(ac->req, NULL, NULL,
-					       ret);
-		}
-
-		ac->op_controls = talloc_steal(ac, ares->controls);
-		ac->op_response = talloc_steal(ac, ares->response);
-
-		return ldb_next_request(ac->module, search_req);
-		
-	} else {
-		return ldb_module_done(ac->req, ares->controls,
-				       ares->response, ares->error);
-	}
-}
-
-/* Reconstruct the original request, but pointing at our local callback to finish things off */
-static int la_down_req(struct la_context *ac)
-{
-	struct ldb_request *down_req;
-	int ret;
-	struct ldb_context *ldb;
-
-	ldb = ldb_module_get_ctx(ac->module);
-
-	switch (ac->req->operation) {
-	case LDB_ADD:
-		ret = ldb_build_add_req(&down_req, ldb, ac,
-					ac->req->op.add.message,
-					ac->req->controls,
-					ac, la_add_callback,
-					ac->req);
-		break;
-	case LDB_MODIFY:
-		ret = ldb_build_mod_req(&down_req, ldb, ac,
-					ac->req->op.mod.message,
-					ac->req->controls,
-					ac, la_mod_del_callback,
-					ac->req);
-		break;
-	case LDB_DELETE:
-		ret = ldb_build_del_req(&down_req, ldb, ac,
-					ac->req->op.del.dn,
-					ac->req->controls,
-					ac, la_mod_del_callback,
-					ac->req);
-		break;
-	case LDB_RENAME:
-		ret = ldb_build_rename_req(&down_req, ldb, ac,
-					   ac->req->op.rename.olddn,
-					   ac->req->op.rename.newdn,
-					   ac->req->controls,
-					   ac, la_rename_callback,
-					   ac->req);
-		break;
-	default:
-		ret = LDB_ERR_OPERATIONS_ERROR;
-	}
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-
-	return ldb_next_request(ac->module, down_req);
-}
-
-/*
-  use the GUID part of an extended DN to find the target DN, in case
-  it has moved
- */
-static int la_find_dn_target(struct ldb_module *module, struct la_context *ac, 
-			     struct GUID *guid, struct ldb_dn **dn)
-{
-	return dsdb_find_dn_by_guid(ldb_module_get_ctx(ac->module), ac, GUID_string(ac, guid), dn);
-}
-
-/* apply one la_context op change */
-static int la_do_op_request(struct ldb_module *module, struct la_context *ac, struct la_op_store *op)
-{
-	struct ldb_message_element *ret_el;
-	struct ldb_request *mod_req;
-	struct ldb_message *new_msg;
-	struct ldb_context *ldb;
-	int ret;
-
-	ldb = ldb_module_get_ctx(ac->module);
-
-	/* Create the modify request */
-	new_msg = ldb_msg_new(ac);
-	if (!new_msg) {
-		ldb_oom(ldb);
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	ret = la_find_dn_target(module, ac, &op->guid, &new_msg->dn);
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-
-	if (op->op == LA_OP_ADD) {
-		ret = ldb_msg_add_empty(new_msg, op->name,
-					LDB_FLAG_MOD_ADD, &ret_el);
-	} else {
-		ret = ldb_msg_add_empty(new_msg, op->name,
-					LDB_FLAG_MOD_DELETE, &ret_el);
-	}
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-	ret_el->values = talloc_array(new_msg, struct ldb_val, 1);
-	if (!ret_el->values) {
-		ldb_oom(ldb);
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-	ret_el->num_values = 1;
-	if (op->op == LA_OP_ADD) {
-		ret_el->values[0] = data_blob_string_const(ldb_dn_get_extended_linearized(new_msg, ac->add_dn, 1));
-	} else {
-		ret_el->values[0] = data_blob_string_const(ldb_dn_get_extended_linearized(new_msg, ac->del_dn, 1));
-	}
-
-#if 0
-	ldb_debug(ldb, LDB_DEBUG_WARNING,
-		  "link on %s %s: %s %s\n", 
-		  ldb_dn_get_linearized(new_msg->dn), ret_el->name, 
-		  ret_el->values[0].data, ac->ops->op == LA_OP_ADD ? "added" : "deleted");
-#endif	
-
-	ret = ldb_build_mod_req(&mod_req, ldb, op,
-				new_msg,
-				NULL,
-				NULL, 
-				ldb_op_default_callback,
-				NULL);
+	ret = dsdb_module_search_dn(module, req, &res, req->op.rename.olddn,
+				    NULL, DSDB_SEARCH_SHOW_DELETED);
 	if (ret != LDB_SUCCESS) {
 		return ret;
 	}
-	talloc_steal(mod_req, new_msg);
-
-	if (DEBUGLVL(4)) {
-		DEBUG(4,("Applying linked attribute change:\n%s\n",
-			 ldb_ldif_message_string(ldb, op, LDB_CHANGETYPE_MODIFY, new_msg)));
-	}
-
-	/* Run the new request */
-	ret = ldb_next_request(module, mod_req);
-
-	/* we need to wait for this to finish, as we are being called
-	   from the synchronous end_transaction hook of this module */
-	if (ret == LDB_SUCCESS) {
-		ret = ldb_wait(mod_req->handle, LDB_WAIT_ALL);
-	}
-
-	if (ret != LDB_SUCCESS) {
-		ldb_debug(ldb, LDB_DEBUG_WARNING, "Failed to apply linked attribute change '%s' %s\n",
-			  ldb_errstring(ldb),
-			  ldb_ldif_message_string(ldb, op, LDB_CHANGETYPE_MODIFY, new_msg));
-	}
-
-	return ret;
-}
-
-/* apply one set of la_context changes */
-static int la_do_mod_request(struct ldb_module *module, struct la_context *ac)
-{
-	struct la_op_store *op;
+	msg = res->msgs[0];
 
-	for (op = ac->ops; op; op=op->next) {
-		int ret = la_do_op_request(module, ac, op);
-		if (ret != LDB_SUCCESS) {
-			if (ret != LDB_ERR_NO_SUCH_OBJECT) {
-				return ret;
-			}
+	for (i=0; i<msg->num_elements; i++) {
+		struct ldb_message_element *el = &msg->elements[i];
+		const struct dsdb_attribute *schema_attr
+			= dsdb_attribute_by_lDAPDisplayName(schema, el->name);
+		if (!schema_attr || schema_attr->linkID == 0) {
+			continue;
 		}
-	}
-
-	return LDB_SUCCESS;
-}
-
-
-/*
-  we hook into the transaction operations to allow us to 
-  perform the linked attribute updates at the end of the whole
-  transaction. This allows a forward linked attribute to be created
-  before the target is created, as long as the target is created
-  in the same transaction
- */
-static int linked_attributes_start_transaction(struct ldb_module *module)
-{
-	/* create our private structure for this transaction */
-	struct la_private *la_private = talloc_get_type(ldb_module_get_private(module),
-							struct la_private);
-	talloc_free(la_private);
-	la_private = talloc(module, struct la_private);
-	if (la_private == NULL) {
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-	la_private->la_list = NULL;
-	ldb_module_set_private(module, la_private);
-	return ldb_next_start_trans(module);
-}
-
-/*
-  on prepare commit we loop over our queued la_context structures
-  and apply each of them
- */
-static int linked_attributes_prepare_commit(struct ldb_module *module)
-{
-	struct la_private *la_private = 
-		talloc_get_type(ldb_module_get_private(module), struct la_private);
-	struct la_context *ac;
-
-	if (!la_private) {
-		/* prepare commit without begin_transaction - let someone else return the error, just don't segfault */
-		return ldb_next_prepare_commit(module);
-	}
-	/* walk the list backwards, to do the first entry first, as we
-	 * added the entries with DLIST_ADD() which puts them at the
-	 * start of the list */
-	for (ac = la_private->la_list; ac && ac->next; ac=ac->next) ;
-
-	for (; ac; ac=ac->prev) {
-		int ret;
-		ac->req = NULL;
-		ret = la_do_mod_request(module, ac);
+		ret = linked_attributes_fix_links(module, msg->dn, req->op.rename.newdn, el,
+						  schema, schema_attr);
 		if (ret != LDB_SUCCESS) {
-			DEBUG(0,(__location__ ": Failed mod request ret=%d\n", ret));
-			talloc_free(la_private);
-			ldb_module_set_private(module, NULL);	
+			talloc_free(res);
 			return ret;
 		}
 	}
 
-	talloc_free(la_private);
-	ldb_module_set_private(module, NULL);	
+	talloc_free(res);
 
-	return ldb_next_prepare_commit(module);
-}
-
-static int linked_attributes_del_transaction(struct ldb_module *module)
-{
-	struct la_private *la_private = 
-		talloc_get_type(ldb_module_get_private(module), struct la_private);
-	talloc_free(la_private);
-	ldb_module_set_private(module, NULL);
-	return ldb_next_del_trans(module);
+	return ldb_next_request(module, req);
 }
 
 
 _PUBLIC_ const struct ldb_module_ops ldb_linked_attributes_module_ops = {
 	.name		   = "linked_attributes",
-	.add               = linked_attributes_add,
-	.modify            = linked_attributes_modify,
-	.del               = linked_attributes_del,
-	.rename            = linked_attributes_rename,
-	.start_transaction = linked_attributes_start_transaction,
-	.prepare_commit    = linked_attributes_prepare_commit,
-	.del_transaction   = linked_attributes_del_transaction,
+	.rename	  	   = linked_attributes_rename,
 };
diff --git a/source4/dsdb/samdb/ldb_modules/repl_meta_data.c b/source4/dsdb/samdb/ldb_modules/repl_meta_data.c
index 3ae165c6da..890eb91d6d 100644
--- a/source4/dsdb/samdb/ldb_modules/repl_meta_data.c
+++ b/source4/dsdb/samdb/ldb_modules/repl_meta_data.c
@@ -46,10 +46,16 @@
 #include "libcli/security/dom_sid.h"
 #include "lib/util/dlinklist.h"
 #include "dsdb/samdb/ldb_modules/util.h"
+#include "lib/util/binsearch.h"
+#include "libcli/security/security.h"
+
+#define W2K3_LINKED_ATTRIBUTES 1
 
 struct replmd_private {
 	TALLOC_CTX *la_ctx;
 	struct la_entry *la_list;
+	TALLOC_CTX *bl_ctx;
+	struct la_backlink *la_backlinks;
 	struct nc_entry {
 		struct nc_entry *prev, *next;
 		struct ldb_dn *dn;
@@ -84,6 +90,7 @@ struct replmd_replicated_request {
 
 static int replmd_replicated_apply_next(struct replmd_replicated_request *ar);
 
+
 /*
   initialise the module
   allocate the private structure and build the list
@@ -104,6 +111,176 @@ static int replmd_init(struct ldb_module *module)
 	return ldb_next_init(module);
 }
 
+/*
+  cleanup our per-transaction contexts
+ */
+static void replmd_txn_cleanup(struct replmd_private *replmd_private)
+{
+	talloc_free(replmd_private->la_ctx);
+	replmd_private->la_list = NULL;
+	replmd_private->la_ctx = NULL;
+
+	talloc_free(replmd_private->bl_ctx);
+	replmd_private->la_backlinks = NULL;
+	replmd_private->bl_ctx = NULL;
+}
+
+
+struct la_backlink {
+	struct la_backlink *next, *prev;
+	const char *attr_name;
+	struct GUID forward_guid, target_guid;
+	bool active;
+};
+
+/*
+  process a backlinks we accumulated during a transaction, adding and
+  deleting the backlinks from the target objects
+ */
+static int replmd_process_backlink(struct ldb_module *module, struct la_backlink *bl)
+{
+	struct ldb_dn *target_dn, *source_dn;
+	int ret;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	struct ldb_message *msg;
+	TALLOC_CTX *tmp_ctx = talloc_new(bl);
+	char *dn_string;
+
+	/*
+	  - find DN of target
+	  - find DN of source
+	  - construct ldb_message
+              - either an add or a delete
+	 */
+	ret = dsdb_module_dn_by_guid(module, tmp_ctx, &bl->target_guid, &target_dn);
+	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb, "Failed to find target DN for linked attribute with GUID %s\n",
+				       GUID_string(bl, &bl->target_guid));
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	ret = dsdb_module_dn_by_guid(module, tmp_ctx, &bl->forward_guid, &source_dn);
+	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb, "Failed to find source DN for linked attribute with GUID %s\n",
+				       GUID_string(bl, &bl->forward_guid));
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	msg = ldb_msg_new(tmp_ctx);
+	if (msg == NULL) {
+		ldb_module_oom(module);
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* construct a ldb_message for adding/deleting the backlink */
+	msg->dn = target_dn;
+	dn_string = ldb_dn_get_extended_linearized(tmp_ctx, source_dn, 1);
+	if (!dn_string) {
+		ldb_module_oom(module);
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ret = ldb_msg_add_steal_string(msg, bl->attr_name, dn_string);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+	msg->elements[0].flags = bl->active?LDB_FLAG_MOD_ADD:LDB_FLAG_MOD_DELETE;
+
+	ret = dsdb_module_modify(module, msg, 0);
+	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb, "Failed to %s backlink from %s to %s - %s",
+				       bl->active?"add":"remove",
+				       ldb_dn_get_linearized(source_dn),
+				       ldb_dn_get_linearized(target_dn),
+				       ldb_errstring(ldb));
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+	talloc_free(tmp_ctx);
+	return ret;
+}
+
+/*
+  add a backlink to the list of backlinks to add/delete in the prepare
+  commit
+ */
+static int replmd_add_backlink(struct ldb_module *module, const struct dsdb_schema *schema,
+			       struct GUID *forward_guid, struct GUID *target_guid,
+			       bool active, const struct dsdb_attribute *schema_attr, bool immediate)
+{
+	const struct dsdb_attribute *target_attr;
+	struct la_backlink *bl;
+	struct replmd_private *replmd_private =
+		talloc_get_type_abort(ldb_module_get_private(module), struct replmd_private);
+
+	target_attr = dsdb_attribute_by_linkID(schema, schema_attr->linkID ^ 1);
+	if (!target_attr) {
+		/*
+		 * windows 2003 has a broken schema where the
+		 * definition of msDS-IsDomainFor is missing (which is
+		 * supposed to be the backlink of the
+		 * msDS-HasDomainNCs attribute
+		 */
+		return LDB_SUCCESS;
+	}
+
+	/* see if its already in the list */
+	for (bl=replmd_private->la_backlinks; bl; bl=bl->next) {
+		if (GUID_equal(forward_guid, &bl->forward_guid) &&
+		    GUID_equal(target_guid, &bl->target_guid) &&
+		    (target_attr->lDAPDisplayName == bl->attr_name ||
+		     strcmp(target_attr->lDAPDisplayName, bl->attr_name) == 0)) {
+			break;
+		}
+	}
+
+	if (bl) {
+		/* we found an existing one */
+		if (bl->active == active) {
+			return LDB_SUCCESS;
+		}
+		DLIST_REMOVE(replmd_private->la_backlinks, bl);
+		talloc_free(bl);
+		return LDB_SUCCESS;
+	}
+
+	if (replmd_private->bl_ctx == NULL) {
+		replmd_private->bl_ctx = talloc_new(replmd_private);
+		if (replmd_private->bl_ctx == NULL) {
+			ldb_module_oom(module);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+	}
+
+	/* its a new one */
+	bl = talloc(replmd_private->bl_ctx, struct la_backlink);
+	if (bl == NULL) {
+		ldb_module_oom(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	bl->attr_name = target_attr->lDAPDisplayName;
+	bl->forward_guid = *forward_guid;
+	bl->target_guid = *target_guid;
+	bl->active = active;
+
+	/* the caller may ask for this backlink to be processed
+	   immediately */
+	if (immediate) {
+		int ret = replmd_process_backlink(module, bl);
+		talloc_free(bl);
+		return ret;
+	}
+
+	DLIST_ADD(replmd_private->la_backlinks, bl);
+
+	return LDB_SUCCESS;
+}
+
 
 /*
  * Callback for most write operations in this module:
@@ -142,6 +319,7 @@ static int replmd_op_callback(struct ldb_request *req, struct ldb_reply *ares)
 	}
 
 	if (!partition_ctrl) {
+		ldb_set_errstring(ldb_module_get_ctx(ac->module),"No partition control on reply");
 		return ldb_module_done(ac->req, NULL,
 				       NULL, LDB_ERR_OPERATIONS_ERROR);
 	}
@@ -336,7 +514,7 @@ static int replmd_replPropertyMetaData1_attid_sort(const struct replPropertyMeta
 		return -1;
 	}
 
-	return m1->attid - m2->attid;
+	return m1->attid > m2->attid ? 1 : -1;
 }
 
 static int replmd_replPropertyMetaDataCtr1_sort(struct replPropertyMetaDataCtr1 *ctr1,
@@ -390,8 +568,10 @@ static int replmd_ldb_message_element_attid_sort(const struct ldb_message_elemen
 	if (!a1 || !a2) {
 		return strcasecmp(e1->name, e2->name);
 	}
-
-	return a1->attributeID_id - a2->attributeID_id;
+	if (a1->attributeID_id == a2->attributeID_id) {
+		return 0;
+	}
+	return a1->attributeID_id > a2->attributeID_id ? 1 : -1;
 }
 
 static void replmd_ldb_message_sort(struct ldb_message *msg,
@@ -401,6 +581,73 @@ static void replmd_ldb_message_sort(struct ldb_message *msg,
 		  discard_const_p(void, schema), (ldb_qsort_cmp_fn_t)replmd_ldb_message_element_attid_sort);
 }
 
+static int replmd_build_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
+			       const struct GUID *invocation_id, uint64_t seq_num,
+			       uint64_t local_usn, NTTIME nttime, uint32_t version, bool deleted);
+
+
+/*
+  fix up linked attributes in replmd_add.
+  This involves setting up the right meta-data in extended DN
+  components, and creating backlinks to the object
+ */
+static int replmd_add_fix_la(struct ldb_module *module, struct ldb_message_element *el,
+			     uint64_t seq_num, const struct GUID *invocationId, time_t t,
+			     struct GUID *guid, const struct dsdb_attribute *sa)
+{
+	int i;
+	TALLOC_CTX *tmp_ctx = talloc_new(el->values);
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	struct dsdb_schema *schema = dsdb_get_schema(ldb);
+	NTTIME now;
+
+	unix_to_nt_time(&now, t);
+
+	for (i=0; i<el->num_values; i++) {
+		struct ldb_val *v = &el->values[i];
+		struct dsdb_dn *dsdb_dn = dsdb_dn_parse(tmp_ctx, ldb, v, sa->syntax->ldap_oid);
+		struct GUID target_guid;
+		NTSTATUS status;
+		int ret;
+
+		/* note that the DN already has the extended
+		   components from the extended_dn_store module */
+		status = dsdb_get_extended_dn_guid(dsdb_dn->dn, &target_guid, "GUID");
+		if (!NT_STATUS_IS_OK(status) || GUID_all_zero(&target_guid)) {
+			ret = dsdb_module_guid_by_dn(module, dsdb_dn->dn, &target_guid);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+			ret = dsdb_set_extended_dn_guid(dsdb_dn->dn, &target_guid, "GUID");
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+		}
+
+		ret = replmd_build_la_val(el->values, v, dsdb_dn, invocationId,
+					  seq_num, seq_num, now, 0, false);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+
+		ret = replmd_add_backlink(module, schema, guid, &target_guid, true, sa, false);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+	}
+
+	talloc_free(tmp_ctx);
+	return LDB_SUCCESS;
+}
+
+
+/*
+  intercept add requests
+ */
 static int replmd_add(struct ldb_module *module, struct ldb_request *req)
 {
 	struct ldb_context *ldb;
@@ -557,6 +804,19 @@ static int replmd_add(struct ldb_module *module, struct ldb_request *req)
 			continue;
 		}
 
+#if W2K3_LINKED_ATTRIBUTES
+		if (sa->linkID != 0 && dsdb_functional_level(ldb) > DS_DOMAIN_FUNCTION_2000) {
+			ret = replmd_add_fix_la(module, e, ac->seq_num, our_invocation_id, t, &guid, sa);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(ac);
+				return ret;
+			}
+			/* linked attributes are not stored in
+			   replPropertyMetaData in FL above w2k */
+			continue;
+		}
+#endif
+
 		m->attid			= sa->attributeID_id;
 		m->version			= 1;
 		m->originating_change_time	= now;
@@ -678,6 +938,20 @@ static int replmd_update_rpmd_element(struct ldb_context *ldb,
 	for (i=0; i<omd->ctr.ctr1.count; i++) {
 		if (a->attributeID_id == omd->ctr.ctr1.array[i].attid) break;
 	}
+
+#if W2K3_LINKED_ATTRIBUTES
+	if (a->linkID != 0 && dsdb_functional_level(ldb) > DS_DOMAIN_FUNCTION_2000) {
+		/* linked attributes are not stored in
+		   replPropertyMetaData in FL above w2k, but we do
+		   raise the seqnum for the object  */
+		if (*seq_num == 0 &&
+		    ldb_sequence_number(ldb, LDB_SEQ_NEXT, seq_num) != LDB_SUCCESS) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		return LDB_SUCCESS;
+	}
+#endif
+
 	if (i == omd->ctr.ctr1.count) {
 		/* we need to add a new one */
 		omd->ctr.ctr1.array = talloc_realloc(msg, omd->ctr.ctr1.array, 
@@ -719,13 +993,13 @@ static int replmd_update_rpmd_element(struct ldb_context *ldb,
  */
 static int replmd_update_rpmd(struct ldb_module *module, 
 			      const struct dsdb_schema *schema, 
-			      struct ldb_message *msg, uint64_t *seq_num)
+			      struct ldb_message *msg, uint64_t *seq_num,
+			      time_t t)
 {
 	const struct ldb_val *omd_value;
 	enum ndr_err_code ndr_err;
 	struct replPropertyMetaDataBlob omd;
 	int i;
-	time_t t = time(NULL);
 	NTTIME now;
 	const struct GUID *our_invocation_id;
 	int ret;
@@ -828,13 +1102,822 @@ static int replmd_update_rpmd(struct ldb_module *module,
 }
 
 
+struct parsed_dn {
+	struct dsdb_dn *dsdb_dn;
+	struct GUID *guid;
+	struct ldb_val *v;
+};
+
+static int parsed_dn_compare(struct parsed_dn *pdn1, struct parsed_dn *pdn2)
+{
+	return GUID_compare(pdn1->guid, pdn2->guid);
+}
+
+static struct parsed_dn *parsed_dn_find(struct parsed_dn *pdn, int count, struct GUID *guid, struct ldb_dn *dn)
+{
+	struct parsed_dn *ret;
+	if (dn && GUID_all_zero(guid)) {
+		/* when updating a link using DRS, we sometimes get a
+		   NULL GUID. We then need to try and match by DN */
+		int i;
+		for (i=0; i<count; i++) {
+			if (ldb_dn_compare(pdn[i].dsdb_dn->dn, dn) == 0) {
+				dsdb_get_extended_dn_guid(pdn[i].dsdb_dn->dn, guid, "GUID");
+				return &pdn[i];
+			}
+		}
+		return NULL;
+	}
+	BINARY_ARRAY_SEARCH(pdn, count, guid, guid, GUID_compare, ret);
+	return ret;
+}
+
+/*
+  get a series of message element values as an array of DNs and GUIDs
+  the result is sorted by GUID
+ */
+static int get_parsed_dns(struct ldb_module *module, TALLOC_CTX *mem_ctx,
+			  struct ldb_message_element *el, struct parsed_dn **pdn,
+			  const char *ldap_oid)
+{
+	int i;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+
+	if (el == NULL) {
+		*pdn = NULL;
+		return LDB_SUCCESS;
+	}
+
+	(*pdn) = talloc_array(mem_ctx, struct parsed_dn, el->num_values);
+	if (!*pdn) {
+		ldb_module_oom(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	for (i=0; i<el->num_values; i++) {
+		struct ldb_val *v = &el->values[i];
+		NTSTATUS status;
+		struct ldb_dn *dn;
+		struct parsed_dn *p;
+
+		p = &(*pdn)[i];
+
+		p->dsdb_dn = dsdb_dn_parse(*pdn, ldb, v, ldap_oid);
+		if (p->dsdb_dn == NULL) {
+			return LDB_ERR_INVALID_DN_SYNTAX;
+		}
+
+		dn = p->dsdb_dn->dn;
+
+		p->guid = talloc(*pdn, struct GUID);
+		if (p->guid == NULL) {
+			ldb_module_oom(module);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		status = dsdb_get_extended_dn_guid(dn, p->guid, "GUID");
+		if (NT_STATUS_EQUAL(status, NT_STATUS_OBJECT_NAME_NOT_FOUND)) {
+			/* we got a DN without a GUID - go find the GUID */
+			int ret = dsdb_module_guid_by_dn(module, dn, p->guid);
+			if (ret != LDB_SUCCESS) {
+				ldb_asprintf_errstring(ldb, "Unable to find GUID for DN %s\n",
+						       ldb_dn_get_linearized(dn));
+				return ret;
+			}
+			ret = dsdb_set_extended_dn_guid(dn, p->guid, "GUID");
+			if (ret != LDB_SUCCESS) {
+				return ret;
+			}
+		} else if (!NT_STATUS_IS_OK(status)) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		/* keep a pointer to the original ldb_val */
+		p->v = v;
+	}
+
+	qsort(*pdn, el->num_values, sizeof((*pdn)[0]), (comparison_fn_t)parsed_dn_compare);
+
+	return LDB_SUCCESS;
+}
+
+/*
+  build a new extended DN, including all meta data fields
+
+  RMD_FLAGS           = DSDB_RMD_FLAG_* bits
+  RMD_ADDTIME         = originating_add_time
+  RMD_INVOCID         = originating_invocation_id
+  RMD_CHANGETIME      = originating_change_time
+  RMD_ORIGINATING_USN = originating_usn
+  RMD_LOCAL_USN       = local_usn
+  RMD_VERSION         = version
+ */
+static int replmd_build_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
+			       const struct GUID *invocation_id, uint64_t seq_num,
+			       uint64_t local_usn, NTTIME nttime, uint32_t version, bool deleted)
+{
+	struct ldb_dn *dn = dsdb_dn->dn;
+	const char *tstring, *usn_string, *flags_string;
+	struct ldb_val tval;
+	struct ldb_val iid;
+	struct ldb_val usnv, local_usnv;
+	struct ldb_val vers, flagsv;
+	NTSTATUS status;
+	int ret;
+	const char *dnstring;
+	char *vstring;
+	uint32_t rmd_flags = deleted?DSDB_RMD_FLAG_DELETED:0;
+
+	tstring = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)nttime);
+	if (!tstring) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	tval = data_blob_string_const(tstring);
+
+	usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)seq_num);
+	if (!usn_string) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	usnv = data_blob_string_const(usn_string);
+
+	usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)local_usn);
+	if (!usn_string) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	local_usnv = data_blob_string_const(usn_string);
+
+	vstring = talloc_asprintf(mem_ctx, "%lu", (unsigned long)version);
+	if (!vstring) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	vers = data_blob_string_const(vstring);
+
+	status = GUID_to_ndr_blob(invocation_id, dn, &iid);
+	if (!NT_STATUS_IS_OK(status)) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	flags_string = talloc_asprintf(mem_ctx, "%u", rmd_flags);
+	if (!flags_string) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	flagsv = data_blob_string_const(flags_string);
+
+	ret = ldb_dn_set_extended_component(dn, "RMD_FLAGS", &flagsv);
+	if (ret != LDB_SUCCESS) return ret;
+	ret = ldb_dn_set_extended_component(dn, "RMD_ADDTIME", &tval);
+	if (ret != LDB_SUCCESS) return ret;
+	ret = ldb_dn_set_extended_component(dn, "RMD_INVOCID", &iid);
+	if (ret != LDB_SUCCESS) return ret;
+	ret = ldb_dn_set_extended_component(dn, "RMD_CHANGETIME", &tval);
+	if (ret != LDB_SUCCESS) return ret;
+	ret = ldb_dn_set_extended_component(dn, "RMD_LOCAL_USN", &local_usnv);
+	if (ret != LDB_SUCCESS) return ret;
+	ret = ldb_dn_set_extended_component(dn, "RMD_ORIGINATING_USN", &usnv);
+	if (ret != LDB_SUCCESS) return ret;
+	ret = ldb_dn_set_extended_component(dn, "RMD_VERSION", &vers);
+	if (ret != LDB_SUCCESS) return ret;
+
+	dnstring = dsdb_dn_get_extended_linearized(mem_ctx, dsdb_dn, 1);
+	if (dnstring == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	*v = data_blob_string_const(dnstring);
+
+	return LDB_SUCCESS;
+}
+
+static int replmd_update_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
+				struct dsdb_dn *old_dsdb_dn, const struct GUID *invocation_id,
+				uint64_t seq_num, uint64_t local_usn, NTTIME nttime,
+				uint32_t version, bool deleted);
+
+/*
+  check if any links need upgrading from w2k format
+ */
+static int replmd_check_upgrade_links(struct parsed_dn *dns, uint32_t count, const struct GUID *invocation_id)
+{
+	int i;
+	for (i=0; i<count; i++) {
+		NTSTATUS status;
+		uint32_t version;
+		int ret;
+
+		status = dsdb_get_extended_dn_uint32(dns[i].dsdb_dn->dn, &version, "RMD_VERSION");
+		if (!NT_STATUS_EQUAL(status, NT_STATUS_OBJECT_NAME_NOT_FOUND)) {
+			continue;
+		}
+
+		/* it's an old one that needs upgrading */
+		ret = replmd_update_la_val(dns, dns[i].v, dns[i].dsdb_dn, dns[i].dsdb_dn, invocation_id,
+					   1, 1, 0, 0, false);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+	return LDB_SUCCESS;
+}
+
+/*
+  update an extended DN, including all meta data fields
+
+  see replmd_build_la_val for value names
+ */
+static int replmd_update_la_val(TALLOC_CTX *mem_ctx, struct ldb_val *v, struct dsdb_dn *dsdb_dn,
+				struct dsdb_dn *old_dsdb_dn, const struct GUID *invocation_id,
+				uint64_t seq_num, uint64_t local_usn, NTTIME nttime,
+				uint32_t version, bool deleted)
+{
+	struct ldb_dn *dn = dsdb_dn->dn;
+	const char *tstring, *usn_string, *flags_string;
+	struct ldb_val tval;
+	struct ldb_val iid;
+	struct ldb_val usnv, local_usnv;
+	struct ldb_val vers, flagsv;
+	const struct ldb_val *old_addtime;
+	uint32_t old_version;
+	NTSTATUS status;
+	int ret;
+	const char *dnstring;
+	char *vstring;
+	uint32_t rmd_flags = deleted?DSDB_RMD_FLAG_DELETED:0;
+
+	tstring = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)nttime);
+	if (!tstring) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	tval = data_blob_string_const(tstring);
+
+	usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)seq_num);
+	if (!usn_string) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	usnv = data_blob_string_const(usn_string);
+
+	usn_string = talloc_asprintf(mem_ctx, "%llu", (unsigned long long)local_usn);
+	if (!usn_string) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	local_usnv = data_blob_string_const(usn_string);
+
+	status = GUID_to_ndr_blob(invocation_id, dn, &iid);
+	if (!NT_STATUS_IS_OK(status)) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	flags_string = talloc_asprintf(mem_ctx, "%u", rmd_flags);
+	if (!flags_string) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	flagsv = data_blob_string_const(flags_string);
+
+	ret = ldb_dn_set_extended_component(dn, "RMD_FLAGS", &flagsv);
+	if (ret != LDB_SUCCESS) return ret;
+
+	/* get the ADDTIME from the original */
+	old_addtime = ldb_dn_get_extended_component(old_dsdb_dn->dn, "RMD_ADDTIME");
+	if (old_addtime == NULL) {
+		old_addtime = &tval;
+	}
+	if (dsdb_dn != old_dsdb_dn) {
+		ret = ldb_dn_set_extended_component(dn, "RMD_ADDTIME", old_addtime);
+		if (ret != LDB_SUCCESS) return ret;
+	}
+
+	/* use our invocation id */
+	ret = ldb_dn_set_extended_component(dn, "RMD_INVOCID", &iid);
+	if (ret != LDB_SUCCESS) return ret;
+
+	/* changetime is the current time */
+	ret = ldb_dn_set_extended_component(dn, "RMD_CHANGETIME", &tval);
+	if (ret != LDB_SUCCESS) return ret;
+
+	/* update the USN */
+	ret = ldb_dn_set_extended_component(dn, "RMD_ORIGINATING_USN", &usnv);
+	if (ret != LDB_SUCCESS) return ret;
+
+	ret = ldb_dn_set_extended_component(dn, "RMD_LOCAL_USN", &local_usnv);
+	if (ret != LDB_SUCCESS) return ret;
+
+	/* increase the version by 1 */
+	status = dsdb_get_extended_dn_uint32(old_dsdb_dn->dn, &old_version, "RMD_VERSION");
+	if (NT_STATUS_IS_OK(status) && old_version >= version) {
+		version = old_version+1;
+	}
+	vstring = talloc_asprintf(dn, "%lu", (unsigned long)version);
+	vers = data_blob_string_const(vstring);
+	ret = ldb_dn_set_extended_component(dn, "RMD_VERSION", &vers);
+	if (ret != LDB_SUCCESS) return ret;
+
+	dnstring = dsdb_dn_get_extended_linearized(mem_ctx, dsdb_dn, 1);
+	if (dnstring == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	*v = data_blob_string_const(dnstring);
+
+	return LDB_SUCCESS;
+}
+
+/*
+  handle adding a linked attribute
+ */
+static int replmd_modify_la_add(struct ldb_module *module,
+				struct dsdb_schema *schema,
+				struct ldb_message *msg,
+				struct ldb_message_element *el,
+				struct ldb_message_element *old_el,
+				const struct dsdb_attribute *schema_attr,
+				uint64_t seq_num,
+				time_t t,
+				struct GUID *msg_guid)
+{
+	int i;
+	struct parsed_dn *dns, *old_dns;
+	TALLOC_CTX *tmp_ctx = talloc_new(msg);
+	int ret;
+	struct ldb_val *new_values = NULL;
+	unsigned int num_new_values = 0;
+	unsigned old_num_values = old_el?old_el->num_values:0;
+	const struct GUID *invocation_id;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	NTTIME now;
+
+	unix_to_nt_time(&now, t);
+
+	ret = get_parsed_dns(module, tmp_ctx, el, &dns, schema_attr->syntax->ldap_oid);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	ret = get_parsed_dns(module, tmp_ctx, old_el, &old_dns, schema_attr->syntax->ldap_oid);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	invocation_id = samdb_ntds_invocation_id(ldb);
+	if (!invocation_id) {
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = replmd_check_upgrade_links(old_dns, old_num_values, invocation_id);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	/* for each new value, see if it exists already with the same GUID */
+	for (i=0; i<el->num_values; i++) {
+		struct parsed_dn *p = parsed_dn_find(old_dns, old_num_values, dns[i].guid, NULL);
+		if (p == NULL) {
+			/* this is a new linked attribute value */
+			new_values = talloc_realloc(tmp_ctx, new_values, struct ldb_val, num_new_values+1);
+			if (new_values == NULL) {
+				ldb_module_oom(module);
+				talloc_free(tmp_ctx);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			ret = replmd_build_la_val(new_values, &new_values[num_new_values], dns[i].dsdb_dn,
+						  invocation_id, seq_num, seq_num, now, 0, false);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+			num_new_values++;
+		} else {
+			/* this is only allowed if the GUID was
+			   previously deleted. */
+			uint32_t rmd_flags = dsdb_dn_rmd_flags(p->dsdb_dn->dn);
+
+			if (!(rmd_flags & DSDB_RMD_FLAG_DELETED)) {
+				ldb_asprintf_errstring(ldb, "Attribute %s already exists for target GUID %s",
+						       el->name, GUID_string(tmp_ctx, p->guid));
+				talloc_free(tmp_ctx);
+				return LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+			}
+			ret = replmd_update_la_val(old_el->values, p->v, dns[i].dsdb_dn, p->dsdb_dn,
+						   invocation_id, seq_num, seq_num, now, 0, false);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+		}
+
+		ret = replmd_add_backlink(module, schema, msg_guid, dns[i].guid, true, schema_attr, true);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+	}
+
+	/* add the new ones on to the end of the old values, constructing a new el->values */
+	el->values = talloc_realloc(msg->elements, old_el?old_el->values:NULL,
+				    struct ldb_val,
+				    old_num_values+num_new_values);
+	if (el->values == NULL) {
+		ldb_module_oom(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	memcpy(&el->values[old_num_values], new_values, num_new_values*sizeof(struct ldb_val));
+	el->num_values = old_num_values + num_new_values;
+
+	talloc_steal(msg->elements, el->values);
+	talloc_steal(el->values, new_values);
+
+	talloc_free(tmp_ctx);
+
+	/* we now tell the backend to replace all existing values
+	   with the one we have constructed */
+	el->flags = LDB_FLAG_MOD_REPLACE;
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  handle deleting all active linked attributes
+ */
+static int replmd_modify_la_delete(struct ldb_module *module,
+				   struct dsdb_schema *schema,
+				   struct ldb_message *msg,
+				   struct ldb_message_element *el,
+				   struct ldb_message_element *old_el,
+				   const struct dsdb_attribute *schema_attr,
+				   uint64_t seq_num,
+				   time_t t,
+				   struct GUID *msg_guid)
+{
+	int i;
+	struct parsed_dn *dns, *old_dns;
+	TALLOC_CTX *tmp_ctx = talloc_new(msg);
+	int ret;
+	const struct GUID *invocation_id;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	NTTIME now;
+
+	unix_to_nt_time(&now, t);
+
+	/* check if there is nothing to delete */
+	if ((!old_el || old_el->num_values == 0) &&
+	    el->num_values == 0) {
+		return LDB_SUCCESS;
+	}
+
+	if (!old_el || old_el->num_values == 0) {
+		return LDB_ERR_NO_SUCH_ATTRIBUTE;
+	}
+
+	ret = get_parsed_dns(module, tmp_ctx, el, &dns, schema_attr->syntax->ldap_oid);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	ret = get_parsed_dns(module, tmp_ctx, old_el, &old_dns, schema_attr->syntax->ldap_oid);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	invocation_id = samdb_ntds_invocation_id(ldb);
+	if (!invocation_id) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = replmd_check_upgrade_links(old_dns, old_el->num_values, invocation_id);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	el->values = NULL;
+
+	/* see if we are being asked to delete any links that
+	   don't exist or are already deleted */
+	for (i=0; i<el->num_values; i++) {
+		struct parsed_dn *p = &dns[i];
+		struct parsed_dn *p2;
+		uint32_t rmd_flags;
+
+		p2 = parsed_dn_find(old_dns, old_el->num_values, p->guid, NULL);
+		if (!p2) {
+			ldb_asprintf_errstring(ldb, "Attribute %s doesn't exist for target GUID %s",
+					       el->name, GUID_string(tmp_ctx, p->guid));
+			return LDB_ERR_NO_SUCH_ATTRIBUTE;
+		}
+		rmd_flags = dsdb_dn_rmd_flags(p2->dsdb_dn->dn);
+		if (rmd_flags & DSDB_RMD_FLAG_DELETED) {
+			ldb_asprintf_errstring(ldb, "Attribute %s already deleted for target GUID %s",
+					       el->name, GUID_string(tmp_ctx, p->guid));
+			return LDB_ERR_NO_SUCH_ATTRIBUTE;
+		}
+	}
+
+	/* for each new value, see if it exists already with the same GUID
+	   if it is not already deleted and matches the delete list then delete it
+	*/
+	for (i=0; i<old_el->num_values; i++) {
+		struct parsed_dn *p = &old_dns[i];
+		uint32_t rmd_flags;
+
+		if (el->num_values && parsed_dn_find(dns, el->num_values, p->guid, NULL) == NULL) {
+			continue;
+		}
+
+		rmd_flags = dsdb_dn_rmd_flags(p->dsdb_dn->dn);
+		if (rmd_flags & DSDB_RMD_FLAG_DELETED) continue;
+
+		ret = replmd_update_la_val(old_el->values, p->v, p->dsdb_dn, p->dsdb_dn,
+					   invocation_id, seq_num, seq_num, now, 0, true);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+
+		ret = replmd_add_backlink(module, schema, msg_guid, old_dns[i].guid, false, schema_attr, true);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+	}
+
+	el->values = talloc_steal(msg->elements, old_el->values);
+	el->num_values = old_el->num_values;
+
+	talloc_free(tmp_ctx);
+
+	/* we now tell the backend to replace all existing values
+	   with the one we have constructed */
+	el->flags = LDB_FLAG_MOD_REPLACE;
+
+	return LDB_SUCCESS;
+}
+
+/*
+  handle replacing a linked attribute
+ */
+static int replmd_modify_la_replace(struct ldb_module *module,
+				    struct dsdb_schema *schema,
+				    struct ldb_message *msg,
+				    struct ldb_message_element *el,
+				    struct ldb_message_element *old_el,
+				    const struct dsdb_attribute *schema_attr,
+				    uint64_t seq_num,
+				    time_t t,
+				    struct GUID *msg_guid)
+{
+	int i;
+	struct parsed_dn *dns, *old_dns;
+	TALLOC_CTX *tmp_ctx = talloc_new(msg);
+	int ret;
+	const struct GUID *invocation_id;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	struct ldb_val *new_values = NULL;
+	uint32_t num_new_values = 0;
+	unsigned old_num_values = old_el?old_el->num_values:0;
+	NTTIME now;
+
+	unix_to_nt_time(&now, t);
+
+	/* check if there is nothing to replace */
+	if ((!old_el || old_el->num_values == 0) &&
+	    el->num_values == 0) {
+		return LDB_SUCCESS;
+	}
+
+	ret = get_parsed_dns(module, tmp_ctx, el, &dns, schema_attr->syntax->ldap_oid);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	ret = get_parsed_dns(module, tmp_ctx, old_el, &old_dns, schema_attr->syntax->ldap_oid);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	invocation_id = samdb_ntds_invocation_id(ldb);
+	if (!invocation_id) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = replmd_check_upgrade_links(old_dns, old_num_values, invocation_id);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	/* mark all the old ones as deleted */
+	for (i=0; i<old_num_values; i++) {
+		struct parsed_dn *old_p = &old_dns[i];
+		struct parsed_dn *p;
+		uint32_t rmd_flags = dsdb_dn_rmd_flags(old_p->dsdb_dn->dn);
+
+		if (rmd_flags & DSDB_RMD_FLAG_DELETED) continue;
+
+		ret = replmd_add_backlink(module, schema, msg_guid, old_dns[i].guid, false, schema_attr, false);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+
+		p = parsed_dn_find(dns, el->num_values, old_p->guid, NULL);
+		if (p) {
+			/* we don't delete it if we are re-adding it */
+			continue;
+		}
+
+		ret = replmd_update_la_val(old_el->values, old_p->v, old_p->dsdb_dn, old_p->dsdb_dn,
+					   invocation_id, seq_num, seq_num, now, 0, true);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+	}
+
+	/* for each new value, either update its meta-data, or add it
+	 * to old_el
+	*/
+	for (i=0; i<el->num_values; i++) {
+		struct parsed_dn *p = &dns[i], *old_p;
+
+		if (old_dns &&
+		    (old_p = parsed_dn_find(old_dns,
+					    old_num_values, p->guid, NULL)) != NULL) {
+			/* update in place */
+			ret = replmd_update_la_val(old_el->values, old_p->v, old_p->dsdb_dn,
+						   old_p->dsdb_dn, invocation_id,
+						   seq_num, seq_num, now, 0, false);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+		} else {
+			/* add a new one */
+			new_values = talloc_realloc(tmp_ctx, new_values, struct ldb_val,
+						    num_new_values+1);
+			if (new_values == NULL) {
+				ldb_module_oom(module);
+				talloc_free(tmp_ctx);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			ret = replmd_build_la_val(new_values, &new_values[num_new_values], dns[i].dsdb_dn,
+						  invocation_id, seq_num, seq_num, now, 0, false);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+			num_new_values++;
+		}
+
+		ret = replmd_add_backlink(module, schema, msg_guid, dns[i].guid, true, schema_attr, false);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+	}
+
+	/* add the new values to the end of old_el */
+	if (num_new_values != 0) {
+		el->values = talloc_realloc(msg->elements, old_el?old_el->values:NULL,
+					    struct ldb_val, old_num_values+num_new_values);
+		if (el->values == NULL) {
+			ldb_module_oom(module);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		memcpy(&el->values[old_num_values], &new_values[0],
+		       sizeof(struct ldb_val)*num_new_values);
+		el->num_values = old_num_values + num_new_values;
+		talloc_steal(msg->elements, new_values);
+	} else {
+		el->values = old_el->values;
+		el->num_values = old_el->num_values;
+		talloc_steal(msg->elements, el->values);
+	}
+
+	talloc_free(tmp_ctx);
+
+	/* we now tell the backend to replace all existing values
+	   with the one we have constructed */
+	el->flags = LDB_FLAG_MOD_REPLACE;
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  handle linked attributes in modify requests
+ */
+static int replmd_modify_handle_linked_attribs(struct ldb_module *module,
+					       struct ldb_message *msg,
+					       uint64_t seq_num, time_t t)
+{
+	struct ldb_result *res;
+	int ret, i;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	struct ldb_message *old_msg;
+	struct dsdb_schema *schema = dsdb_get_schema(ldb);
+	struct GUID old_guid;
+
+	if (seq_num == 0) {
+		/* there the replmd_update_rpmd code has already
+		 * checked and saw that there are no linked
+		 * attributes */
+		return LDB_SUCCESS;
+	}
+
+#if !W2K3_LINKED_ATTRIBUTES
+	return LDB_SUCCESS;
+#endif
+
+	if (dsdb_functional_level(ldb) == DS_DOMAIN_FUNCTION_2000) {
+		/* don't do anything special for linked attributes */
+		return LDB_SUCCESS;
+	}
+
+	ret = dsdb_module_search_dn(module, msg, &res, msg->dn, NULL,
+				    DSDB_SEARCH_SHOW_DELETED |
+				    DSDB_SEARCH_REVEAL_INTERNALS |
+				    DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+	old_msg = res->msgs[0];
+
+	old_guid = samdb_result_guid(old_msg, "objectGUID");
+
+	for (i=0; i<msg->num_elements; i++) {
+		struct ldb_message_element *el = &msg->elements[i];
+		struct ldb_message_element *old_el, *new_el;
+		const struct dsdb_attribute *schema_attr
+			= dsdb_attribute_by_lDAPDisplayName(schema, el->name);
+		if (!schema_attr) {
+			ldb_asprintf_errstring(ldb,
+					       "attribute %s is not a valid attribute in schema", el->name);
+			return LDB_ERR_OBJECT_CLASS_VIOLATION;
+		}
+		if (schema_attr->linkID == 0) {
+			continue;
+		}
+		if ((schema_attr->linkID & 1) == 1) {
+			/* Odd is for the target.  Illegal to modify */
+			ldb_asprintf_errstring(ldb,
+					       "attribute %s must not be modified directly, it is a linked attribute", el->name);
+			return LDB_ERR_UNWILLING_TO_PERFORM;
+		}
+		old_el = ldb_msg_find_element(old_msg, el->name);
+		switch (el->flags & LDB_FLAG_MOD_MASK) {
+		case LDB_FLAG_MOD_REPLACE:
+			ret = replmd_modify_la_replace(module, schema, msg, el, old_el, schema_attr, seq_num, t, &old_guid);
+			break;
+		case LDB_FLAG_MOD_DELETE:
+			ret = replmd_modify_la_delete(module, schema, msg, el, old_el, schema_attr, seq_num, t, &old_guid);
+			break;
+		case LDB_FLAG_MOD_ADD:
+			ret = replmd_modify_la_add(module, schema, msg, el, old_el, schema_attr, seq_num, t, &old_guid);
+			break;
+		default:
+			ldb_asprintf_errstring(ldb,
+					       "invalid flags 0x%x for %s linked attribute",
+					       el->flags, el->name);
+			return LDB_ERR_UNWILLING_TO_PERFORM;
+		}
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+		if (old_el) {
+			ldb_msg_remove_attr(old_msg, el->name);
+		}
+		ldb_msg_add_empty(old_msg, el->name, 0, &new_el);
+		new_el->num_values = el->num_values;
+		new_el->values = talloc_steal(msg->elements, el->values);
+
+		/* TODO: this relises a bit too heavily on the exact
+		   behaviour of ldb_msg_find_element and
+		   ldb_msg_remove_element */
+		old_el = ldb_msg_find_element(msg, el->name);
+		if (old_el != el) {
+			ldb_msg_remove_element(msg, old_el);
+			i--;
+		}
+	}
+
+	talloc_free(res);
+	return ret;
+}
+
+
+
 static int replmd_modify(struct ldb_module *module, struct ldb_request *req)
 {
 	struct ldb_context *ldb;
 	struct replmd_replicated_request *ac;
 	struct ldb_request *down_req;
 	struct ldb_message *msg;
-	struct ldb_result *res;
 	time_t t = time(NULL);
 	int ret;
 
@@ -860,24 +1943,16 @@ static int replmd_modify(struct ldb_module *module, struct ldb_request *req)
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	/* TODO:
-	 * - give an error when a readonly attribute should
-	 *   be modified
-	 * - merge the changed into the old object
-	 *   if the caller set values to the same value
-	 *   ignore the attribute, return success when no
-	 *   attribute was changed
-	 */
+	ldb_msg_remove_attr(msg, "whenChanged");
+	ldb_msg_remove_attr(msg, "uSNChanged");
 
-	ret = dsdb_module_search_dn(module, msg, &res, msg->dn, NULL,
-				    DSDB_SEARCH_SHOW_DELETED |
-				    DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT);
+	ret = replmd_update_rpmd(module, ac->schema, msg, &ac->seq_num, t);
 	if (ret != LDB_SUCCESS) {
 		talloc_free(ac);
 		return ret;
 	}
 
-	ret = replmd_update_rpmd(module, ac->schema, msg, &ac->seq_num);
+	ret = replmd_modify_handle_linked_attribs(module, msg, ac->seq_num, t);
 	if (ret != LDB_SUCCESS) {
 		talloc_free(ac);
 		return ret;
@@ -1030,6 +2105,329 @@ static int replmd_rename_callback(struct ldb_request *req, struct ldb_reply *are
 	return ldb_next_request(ac->module, down_req);
 }
 
+/*
+   remove links from objects that point at this object when an object
+   is deleted
+ */
+static int replmd_delete_remove_link(struct ldb_module *module,
+				     struct dsdb_schema *schema,
+				     struct ldb_dn *dn,
+				     struct ldb_message_element *el,
+				     const struct dsdb_attribute *sa)
+{
+	int i;
+	TALLOC_CTX *tmp_ctx = talloc_new(module);
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+
+	for (i=0; i<el->num_values; i++) {
+		struct dsdb_dn *dsdb_dn;
+		NTSTATUS status;
+		int ret;
+		struct GUID guid2;
+		struct ldb_message *msg;
+		const struct dsdb_attribute *target_attr;
+		struct ldb_message_element *el2;
+		struct ldb_val dn_val;
+
+		if (dsdb_dn_is_deleted_val(&el->values[i])) {
+			continue;
+		}
+
+		dsdb_dn = dsdb_dn_parse(tmp_ctx, ldb, &el->values[i], sa->syntax->ldap_oid);
+		if (!dsdb_dn) {
+			talloc_free(tmp_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		status = dsdb_get_extended_dn_guid(dsdb_dn->dn, &guid2, "GUID");
+		if (!NT_STATUS_IS_OK(status)) {
+			talloc_free(tmp_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		/* remove the link */
+		msg = ldb_msg_new(tmp_ctx);
+		if (!msg) {
+			ldb_module_oom(module);
+			talloc_free(tmp_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+
+		msg->dn = dsdb_dn->dn;
+
+		target_attr = dsdb_attribute_by_linkID(schema, sa->linkID ^ 1);
+		if (target_attr == NULL) {
+			continue;
+		}
+
+		ret = ldb_msg_add_empty(msg, target_attr->lDAPDisplayName, LDB_FLAG_MOD_DELETE, &el2);
+		if (ret != LDB_SUCCESS) {
+			ldb_module_oom(module);
+			talloc_free(tmp_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		dn_val = data_blob_string_const(ldb_dn_get_linearized(dn));
+		el2->values = &dn_val;
+		el2->num_values = 1;
+
+		ret = dsdb_module_modify(module, msg, DSDB_FLAG_OWN_MODULE);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+	}
+	talloc_free(tmp_ctx);
+	return LDB_SUCCESS;
+}
+
+
+/*
+  handle update of replication meta data for deletion of objects
+
+  This also handles the mapping of delete to a rename operation
+  to allow deletes to be replicated.
+ */
+static int replmd_delete(struct ldb_module *module, struct ldb_request *req)
+{
+	int ret = LDB_ERR_OTHER;
+	bool retb;
+	struct ldb_dn *old_dn, *new_dn;
+	const char *rdn_name;
+	const struct ldb_val *rdn_value, *new_rdn_value;
+	struct GUID guid;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	struct dsdb_schema *schema = dsdb_get_schema(ldb);
+	struct ldb_message *msg, *old_msg;
+	struct ldb_message_element *el;
+	TALLOC_CTX *tmp_ctx;
+	struct ldb_result *res, *parent_res;
+	const char *preserved_attrs[] = {
+		/* yes, this really is a hard coded list. See MS-ADTS
+		   section 3.1.1.5.5.1.1 */
+		"nTSecurityDescriptor", "attributeID", "attributeSyntax", "dNReferenceUpdate", "dNSHostName",
+		"flatName", "governsID", "groupType", "instanceType", "lDAPDisplayName", "legacyExchangeDN",
+		"isDeleted", "isRecycled", "lastKnownParent", "msDS-LastKnownRDN", "mS-DS-CreatorSID",
+		"mSMQOwnerID", "nCName", "objectClass", "distinguishedName", "objectGUID", "objectSid",
+		"oMSyntax", "proxiedObjectName", "name", "replPropertyMetaData", "sAMAccountName",
+		"securityIdentifier", "sIDHistory", "subClassOf", "systemFlags", "trustPartner", "trustDirection",
+		"trustType", "trustAttributes", "userAccountControl", "uSNChanged", "uSNCreated", "whenCreated",
+		"whenChanged", NULL};
+	uint32_t el_count = 0;
+	int i;
+
+	if (ldb_dn_is_special(req->op.del.dn)) {
+		return ldb_next_request(module, req);
+	}
+
+	tmp_ctx = talloc_new(ldb);
+
+	old_dn = ldb_dn_copy(tmp_ctx, req->op.del.dn);
+
+	/* we need the complete msg off disk, so we can work out which
+	   attributes need to be removed */
+	ret = dsdb_module_search_dn(module, tmp_ctx, &res, old_dn, NULL,
+				    DSDB_SEARCH_SHOW_DELETED |
+				    DSDB_SEARCH_REVEAL_INTERNALS |
+				    DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+	old_msg = res->msgs[0];
+
+	if (ldb_msg_check_string_attribute(old_msg, "isDeleted", "TRUE")) {
+		struct auth_session_info *session_info =
+			(struct auth_session_info *)ldb_get_opaque(ldb, "sessionInfo");
+		if (security_session_user_level(session_info) != SECURITY_SYSTEM) {
+			ldb_asprintf_errstring(ldb, "Refusing to delete deleted object %s",
+					       ldb_dn_get_linearized(old_msg->dn));
+			return LDB_ERR_UNWILLING_TO_PERFORM;
+		}
+
+		/* it is already deleted - really remove it this time */
+		talloc_free(tmp_ctx);
+		return ldb_next_request(module, req);
+	}
+
+	/* work out where we will be renaming this object to */
+	ret = dsdb_get_deleted_objects_dn(ldb, tmp_ctx, old_dn, &new_dn);
+	if (ret != LDB_SUCCESS) {
+		/* this is probably an attempted delete on a partition
+		 * that doesn't allow delete operations, such as the
+		 * schema partition */
+		ldb_asprintf_errstring(ldb, "No Deleted Objects container for DN %s",
+				       ldb_dn_get_linearized(old_dn));
+		talloc_free(tmp_ctx);
+		return LDB_ERR_UNWILLING_TO_PERFORM;
+	}
+
+	rdn_name = ldb_dn_get_rdn_name(old_dn);
+	rdn_value = ldb_dn_get_rdn_val(old_dn);
+
+	/* get the objects GUID from the search we just did */
+	guid = samdb_result_guid(old_msg, "objectGUID");
+
+	/* Add a formatted child */
+	retb = ldb_dn_add_child_fmt(new_dn, "%s=%s\\0ADEL:%s",
+				    rdn_name,
+				    rdn_value->data,
+				    GUID_string(tmp_ctx, &guid));
+	if (!retb) {
+		DEBUG(0,(__location__ ": Unable to add a formatted child to dn: %s",
+				ldb_dn_get_linearized(new_dn)));
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/*
+	  now we need to modify the object in the following ways:
+
+	  - add isDeleted=TRUE
+	  - update rDN and name, with new rDN
+	  - remove linked attributes
+	  - remove objectCategory and sAMAccountType
+	  - remove attribs not on the preserved list
+	     - preserved if in above list, or is rDN
+	  - remove all linked attribs from this object
+	  - remove all links from other objects to this object
+	  - add lastKnownParent
+	  - update replPropertyMetaData?
+
+	  see MS-ADTS "Tombstone Requirements" section 3.1.1.5.5.1.1
+	 */
+
+	msg = ldb_msg_new(tmp_ctx);
+	if (msg == NULL) {
+		ldb_module_oom(module);
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	msg->dn = old_dn;
+
+	ret = ldb_msg_add_string(msg, "isDeleted", "TRUE");
+	if (ret != LDB_SUCCESS) {
+		DEBUG(0,(__location__ ": Failed to add isDeleted string to the msg\n"));
+		ldb_module_oom(module);
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+	msg->elements[el_count++].flags = LDB_FLAG_MOD_ADD;
+
+	/* we also mark it as recycled, meaning this object can't be
+	   recovered (we are stripping its attributes) */
+	if (dsdb_functional_level(ldb) >= DS_DOMAIN_FUNCTION_2008_R2) {
+		ret = ldb_msg_add_string(msg, "isRecycled", "TRUE");
+		if (ret != LDB_SUCCESS) {
+			DEBUG(0,(__location__ ": Failed to add isRecycled string to the msg\n"));
+			ldb_module_oom(module);
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+		msg->elements[el_count++].flags = LDB_FLAG_MOD_ADD;
+	}
+
+	/* we need the storage form of the parent GUID */
+	ret = dsdb_module_search_dn(module, tmp_ctx, &parent_res,
+				    ldb_dn_get_parent(tmp_ctx, old_dn), NULL,
+				    DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT |
+				    DSDB_SEARCH_REVEAL_INTERNALS);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	ret = ldb_msg_add_steal_string(msg, "lastKnownParent",
+				       ldb_dn_get_extended_linearized(tmp_ctx, parent_res->msgs[0]->dn, 1));
+	if (ret != LDB_SUCCESS) {
+		DEBUG(0,(__location__ ": Failed to add lastKnownParent string to the msg\n"));
+		ldb_module_oom(module);
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+	msg->elements[el_count++].flags = LDB_FLAG_MOD_ADD;
+
+	/* work out which of the old attributes we will be removing */
+	for (i=0; i<old_msg->num_elements; i++) {
+		const struct dsdb_attribute *sa;
+		el = &old_msg->elements[i];
+		sa = dsdb_attribute_by_lDAPDisplayName(schema, el->name);
+		if (!sa) {
+			talloc_free(tmp_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		if (ldb_attr_cmp(el->name, rdn_name) == 0) {
+			/* don't remove the rDN */
+			continue;
+		}
+
+		if (sa->linkID && sa->linkID & 1) {
+			ret = replmd_delete_remove_link(module, schema, old_dn, el, sa);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			continue;
+		}
+
+		if (!sa->linkID && ldb_attr_in_list(preserved_attrs, el->name)) {
+			continue;
+		}
+
+		ret = ldb_msg_add_empty(msg, el->name, LDB_FLAG_MOD_DELETE, &el);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			ldb_module_oom(module);
+			return ret;
+		}
+	}
+
+	/* work out what the new rdn value is, for updating the
+	   rDN and name fields */
+	new_rdn_value = ldb_dn_get_rdn_val(new_dn);
+	ret = ldb_msg_add_value(msg, rdn_name, new_rdn_value, &el);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+	el->flags = LDB_FLAG_MOD_REPLACE;
+
+	el = ldb_msg_find_element(old_msg, "name");
+	if (el) {
+		ret = ldb_msg_add_value(msg, "name", new_rdn_value, &el);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+		el->flags = LDB_FLAG_MOD_REPLACE;
+	}
+
+	ret = dsdb_module_modify(module, msg, DSDB_FLAG_OWN_MODULE);
+	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb, "replmd_delete: Failed to modify object %s in delete - %s",
+				       ldb_dn_get_linearized(old_dn), ldb_errstring(ldb));
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	/* now rename onto the new DN */
+	ret = dsdb_module_rename(module, old_dn, new_dn, 0);
+	if (ret != LDB_SUCCESS){
+		DEBUG(0,(__location__ ": Failed to rename object from '%s' to '%s' - %s\n",
+			 ldb_dn_get_linearized(old_dn),
+			 ldb_dn_get_linearized(new_dn),
+			 ldb_errstring(ldb)));
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	talloc_free(tmp_ctx);
+
+	return ldb_module_done(req, NULL, NULL, LDB_SUCCESS);
+}
+
+
 
 static int replmd_replicated_request_error(struct replmd_replicated_request *ar, int ret)
 {
@@ -1094,14 +2492,15 @@ static int replmd_replicated_apply_add(struct replmd_replicated_request *ar)
 
 	/* remove any message elements that have zero values */
 	for (i=0; i<msg->num_elements; i++) {
-		if (msg->elements[i].num_values == 0) {
+		struct ldb_message_element *el = &msg->elements[i];
+
+		if (el->num_values == 0) {
 			DEBUG(4,(__location__ ": Removing attribute %s with num_values==0\n",
-				 msg->elements[i].name));
-			memmove(&msg->elements[i], 
-				&msg->elements[i+1], 
-				sizeof(msg->elements[i])*(msg->num_elements - (i+1)));
+				 el->name));
+			memmove(el, el+1, sizeof(*el)*(msg->num_elements - (i+1)));
 			msg->num_elements--;
 			i--;
+			continue;
 		}
 	}
 	
@@ -1145,25 +2544,38 @@ static int replmd_replicated_apply_add(struct replmd_replicated_request *ar)
 	return ldb_next_request(ar->module, change_req);
 }
 
-static int replmd_replPropertyMetaData1_conflict_compare(struct replPropertyMetaData1 *m1,
-							 struct replPropertyMetaData1 *m2)
+/*
+   return true if an update is newer than an existing entry
+   see section 5.11 of MS-ADTS
+*/
+static bool replmd_update_is_newer(const struct GUID *current_invocation_id,
+				   const struct GUID *update_invocation_id,
+				   uint32_t current_version,
+				   uint32_t update_version,
+				   NTTIME current_change_time,
+				   NTTIME update_change_time)
 {
-	int ret;
-
-	if (m1->version != m2->version) {
-		return m1->version - m2->version;
+	if (update_version != current_version) {
+		return update_version > current_version;
 	}
-
-	if (m1->originating_change_time != m2->originating_change_time) {
-		return m1->originating_change_time - m2->originating_change_time;
+	if (update_change_time > current_change_time) {
+		return true;
 	}
-
-	ret = GUID_compare(&m1->originating_invocation_id, &m2->originating_invocation_id);
-	if (ret != 0) {
-		return ret;
+	if (update_change_time == current_change_time) {
+		return GUID_compare(update_invocation_id, current_invocation_id) > 0;
 	}
+	return false;
+}
 
-	return m1->originating_usn - m2->originating_usn;
+static bool replmd_replPropertyMetaData1_is_newer(struct replPropertyMetaData1 *cur_m,
+						  struct replPropertyMetaData1 *new_m)
+{
+	return replmd_update_is_newer(&cur_m->originating_invocation_id,
+				      &new_m->originating_invocation_id,
+				      cur_m->version,
+				      new_m->version,
+				      cur_m->originating_change_time,
+				      new_m->originating_change_time);
 }
 
 static int replmd_replicated_apply_merge(struct replmd_replicated_request *ar)
@@ -1194,7 +2606,9 @@ static int replmd_replicated_apply_merge(struct replmd_replicated_request *ar)
 		ldb_debug(ldb, LDB_DEBUG_TRACE, "replmd_replicated_request rename %s => %s\n",
 			  ldb_dn_get_linearized(ar->search_msg->dn),
 			  ldb_dn_get_linearized(msg->dn));
-		if (ldb_rename(ldb, ar->search_msg->dn, msg->dn) != LDB_SUCCESS) {
+		if (dsdb_module_rename(ar->module,
+				       ar->search_msg->dn, msg->dn,
+				       DSDB_FLAG_OWN_MODULE) != LDB_SUCCESS) {
 			ldb_debug(ldb, LDB_DEBUG_FATAL, "replmd_replicated_request rename %s => %s failed - %s\n",
 				  ldb_dn_get_linearized(ar->search_msg->dn),
 				  ldb_dn_get_linearized(msg->dn),
@@ -1238,21 +2652,26 @@ static int replmd_replicated_apply_merge(struct replmd_replicated_request *ar)
 		bool found = false;
 
 		for (j=0; j < ni; j++) {
-			int cmp;
+			bool cmp;
 
 			if (rmd->ctr.ctr1.array[i].attid != nmd.ctr.ctr1.array[j].attid) {
 				continue;
 			}
 
-			cmp = replmd_replPropertyMetaData1_conflict_compare(&rmd->ctr.ctr1.array[i],
-									    &nmd.ctr.ctr1.array[j]);
-			if (cmp > 0) {
+			cmp = replmd_replPropertyMetaData1_is_newer(&nmd.ctr.ctr1.array[j],
+								    &rmd->ctr.ctr1.array[i]);
+			if (cmp) {
 				/* replace the entry */
 				nmd.ctr.ctr1.array[j] = rmd->ctr.ctr1.array[i];
 				found = true;
 				break;
 			}
 
+			DEBUG(1,("Discarding older DRS attribute update to %s on %s from %s\n",
+				 msg->elements[i-removed_attrs].name,
+				 ldb_dn_get_linearized(msg->dn),
+				 GUID_string(ar, &rmd->ctr.ctr1.array[i].originating_invocation_id)));
+
 			/* we don't want to apply this change so remove the attribute */
 			ldb_msg_remove_element(msg, &msg->elements[i-removed_attrs]);
 			removed_attrs++;
@@ -1954,24 +3373,22 @@ static int replmd_process_linked_attribute(struct ldb_module *module,
 	struct drsuapi_DsReplicaLinkedAttribute *la = la_entry->la;
 	struct ldb_context *ldb = ldb_module_get_ctx(module);
 	struct dsdb_schema *schema = dsdb_get_schema(ldb);
-	struct drsuapi_DsReplicaObjectIdentifier3 target;
 	struct ldb_message *msg;
 	TALLOC_CTX *tmp_ctx = talloc_new(la_entry);
-	struct ldb_request *mod_req;
 	int ret;
 	const struct dsdb_attribute *attr;
-	struct ldb_dn *target_dn;
 	struct dsdb_dn *dsdb_dn;
 	uint64_t seq_num = 0;
-	struct drsuapi_DsReplicaAttribute drs;
-	struct drsuapi_DsAttributeValue val;
-	struct ldb_message_element el;
-	const struct ldb_val *guid;
+	struct ldb_message_element *old_el;
 	WERROR status;
-
-	drs.value_ctr.num_values = 1;
-	drs.value_ctr.values = &val;
-	val.blob = la->value.blob;
+	time_t t = time(NULL);
+	struct ldb_result *res;
+	const char *attrs[2];
+	struct parsed_dn *pdn_list, *pdn;
+	struct GUID guid = GUID_zero();
+	NTSTATUS ntstatus;
+	bool active = (la->flags & DRSUAPI_DS_LINKED_ATTRIBUTE_FLAG_ACTIVE)?true:false;
+	const struct GUID *our_invocation_id;
 
 /*
 linked_attributes[0]:                                                     
@@ -2016,155 +3433,212 @@ linked_attributes[0]:
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	status = attr->syntax->drsuapi_to_ldb(ldb, schema, attr, &drs, tmp_ctx, &el);
+	attrs[0] = attr->lDAPDisplayName;
+	attrs[1] = NULL;
 
-	/* construct a modify request for this attribute change */
-	msg = ldb_msg_new(tmp_ctx);
-	if (!msg) {
-		ldb_oom(ldb);
-		talloc_free(tmp_ctx);
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
-	ret = dsdb_find_dn_by_guid(ldb, tmp_ctx, 
-				   GUID_string(tmp_ctx, &la->identifier->guid), &msg->dn);
+	/* get the existing message from the db for the object with
+	   this GUID, returning attribute being modified. We will then
+	   use this msg as the basis for a modify call */
+	ret = dsdb_module_search(module, tmp_ctx, &res, NULL, LDB_SCOPE_SUBTREE, attrs,
+				 DSDB_SEARCH_SEARCH_ALL_PARTITIONS |
+				 DSDB_SEARCH_SHOW_DELETED |
+				 DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT |
+				 DSDB_SEARCH_REVEAL_INTERNALS,
+				 "objectGUID=%s", GUID_string(tmp_ctx, &la->identifier->guid));
 	if (ret != LDB_SUCCESS) {
 		talloc_free(tmp_ctx);
 		return ret;
 	}
+	if (res->count != 1) {
+		ldb_asprintf_errstring(ldb, "DRS linked attribute for GUID %s - DN not found",
+				       GUID_string(tmp_ctx, &la->identifier->guid));
+		talloc_free(tmp_ctx);
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+	msg = res->msgs[0];
 
-	el.name = attr->lDAPDisplayName;
-	if (la->flags & DRSUAPI_DS_LINKED_ATTRIBUTE_FLAG_ACTIVE) {
-		ret = ldb_msg_add(msg, &el, LDB_FLAG_MOD_ADD);
+	if (msg->num_elements == 0) {
+		ret = ldb_msg_add_empty(msg, attr->lDAPDisplayName, LDB_FLAG_MOD_REPLACE, &old_el);
+		if (ret != LDB_SUCCESS) {
+			ldb_module_oom(module);
+			talloc_free(tmp_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
 	} else {
-		ret = ldb_msg_add(msg, &el, LDB_FLAG_MOD_DELETE);
+		old_el = &msg->elements[0];
+		old_el->flags = LDB_FLAG_MOD_REPLACE;
 	}
+
+	/* parse the existing links */
+	ret = get_parsed_dns(module, tmp_ctx, old_el, &pdn_list, attr->syntax->ldap_oid);
 	if (ret != LDB_SUCCESS) {
 		talloc_free(tmp_ctx);
 		return ret;
 	}
 
-	dsdb_dn = dsdb_dn_parse(tmp_ctx, ldb, &el.values[0], attr->syntax->ldap_oid);
-	if (!dsdb_dn) {
-		DEBUG(0,(__location__ ": Failed to parse just-generated DN\n"));
+	/* get our invocationId */
+	our_invocation_id = samdb_ntds_invocation_id(ldb);
+	if (!our_invocation_id) {
+		ldb_debug_set(ldb, LDB_DEBUG_ERROR, __location__ ": unable to find invocationId\n");
 		talloc_free(tmp_ctx);
-		return LDB_ERR_INVALID_DN_SYNTAX;
+		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	guid = ldb_dn_get_extended_component(dsdb_dn->dn, "GUID");
-	if (!guid) {
-		DEBUG(0,(__location__ ": Failed to parse GUID from just-generated DN\n"));
+	ret = replmd_check_upgrade_links(pdn_list, old_el->num_values, our_invocation_id);
+	if (ret != LDB_SUCCESS) {
 		talloc_free(tmp_ctx);
-		return LDB_ERR_INVALID_DN_SYNTAX;
+		return ret;
 	}
 
-	ret = dsdb_find_dn_by_guid(ldb, tmp_ctx, ldb_binary_encode(tmp_ctx, *guid), &target_dn);
-	if (ret != LDB_SUCCESS) {
-		/* If this proves to be a problem in the future, then
-		 * just remove the return - perhaps we can just use
-		 * the details the replication peer supplied */
-
-		DEBUG(0,(__location__ ": Failed to map GUID %s to DN\n", GUID_string(tmp_ctx, &target.guid)));
-		talloc_free(tmp_ctx);
+	status = dsdb_dn_la_from_blob(ldb, attr, schema, tmp_ctx, la->value.blob, &dsdb_dn);
+	if (!W_ERROR_IS_OK(status)) {
+		ldb_asprintf_errstring(ldb, "Failed to parsed linked attribute blob for %s on %s - %s\n",
+				       old_el->name, ldb_dn_get_linearized(msg->dn), win_errstr(status));
 		return LDB_ERR_OPERATIONS_ERROR;
-	} else {
+	}
 
-		/* Now update with full DN we just found in the DB (including extended components) */
-		dsdb_dn->dn = target_dn;
-		/* Now make a linearized version, using the original binary components (if any) */
-		el.values[0] = data_blob_string_const(dsdb_dn_get_extended_linearized(tmp_ctx, dsdb_dn, 1));
+	ntstatus = dsdb_get_extended_dn_guid(dsdb_dn->dn, &guid, "GUID");
+	if (!NT_STATUS_IS_OK(ntstatus) && active) {
+		ldb_asprintf_errstring(ldb, "Failed to find GUID in linked attribute blob for %s on %s from %s",
+				       old_el->name,
+				       ldb_dn_get_linearized(dsdb_dn->dn),
+				       ldb_dn_get_linearized(msg->dn));
+		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	ret = replmd_update_rpmd(module, schema, msg, &seq_num);
+	/* re-resolve the DN by GUID, as the DRS server may give us an
+	   old DN value */
+	ret = dsdb_module_dn_by_guid(module, dsdb_dn, &guid, &dsdb_dn->dn);
 	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb, __location__ ": Failed to re-resolve GUID %s",
+				       GUID_string(tmp_ctx, &guid));
 		talloc_free(tmp_ctx);
 		return ret;
 	}
 
-	/* we only change whenChanged and uSNChanged if the seq_num
-	   has changed */
-	if (seq_num != 0) {
-		time_t t = time(NULL);
-
-		if (add_time_element(msg, "whenChanged", t) != LDB_SUCCESS) {
+	/* see if this link already exists */
+	pdn = parsed_dn_find(pdn_list, old_el->num_values, &guid, dsdb_dn->dn);
+	if (pdn != NULL) {
+		/* see if this update is newer than what we have already */
+		struct GUID invocation_id = GUID_zero();
+		uint32_t version = 0;
+		NTTIME change_time = 0;
+		uint32_t rmd_flags = dsdb_dn_rmd_flags(pdn->dsdb_dn->dn);
+
+		dsdb_get_extended_dn_guid(pdn->dsdb_dn->dn, &invocation_id, "RMD_INVOCID");
+		dsdb_get_extended_dn_uint32(pdn->dsdb_dn->dn, &version, "RMD_VERSION");
+		dsdb_get_extended_dn_nttime(pdn->dsdb_dn->dn, &change_time, "RMD_CHANGETIME");
+
+		if (!replmd_update_is_newer(&invocation_id,
+					    &la->meta_data.originating_invocation_id,
+					    version,
+					    la->meta_data.version,
+					    change_time,
+					    la->meta_data.originating_change_time)) {
+			DEBUG(1,("Discarding older DRS linked attribute update to %s on %s from %s\n",
+				 old_el->name, ldb_dn_get_linearized(msg->dn),
+				 GUID_string(tmp_ctx, &la->meta_data.originating_invocation_id)));
 			talloc_free(tmp_ctx);
-			return LDB_ERR_OPERATIONS_ERROR;
+			return LDB_SUCCESS;
 		}
 
-		if (add_uint64_element(msg, "uSNChanged", seq_num) != LDB_SUCCESS) {
+		/* get a seq_num for this change */
+		ret = ldb_sequence_number(ldb, LDB_SEQ_NEXT, &seq_num);
+		if (ret != LDB_SUCCESS) {
 			talloc_free(tmp_ctx);
-			return LDB_ERR_OPERATIONS_ERROR;
+			return ret;
 		}
-	}
-
-	ret = ldb_build_mod_req(&mod_req, ldb, tmp_ctx,
-				msg,
-				NULL,
-				NULL, 
-				ldb_op_default_callback,
-				NULL);
-	if (ret != LDB_SUCCESS) {
-		talloc_free(tmp_ctx);
-		return ret;
-	}
-	talloc_steal(mod_req, msg);
-
-	if (DEBUGLVL(4)) {
-		DEBUG(4,("Applying DRS linked attribute change:\n%s\n",
-			 ldb_ldif_message_string(ldb, tmp_ctx, LDB_CHANGETYPE_MODIFY, msg)));
-	}
 
-	/* Run the new request */
-	ret = ldb_next_request(module, mod_req);
+		if (!(rmd_flags & DSDB_RMD_FLAG_DELETED)) {
+			/* remove the existing backlink */
+			ret = replmd_add_backlink(module, schema, &la->identifier->guid, &guid, false, attr, false);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+		}
 
-	/* we need to wait for this to finish, as we are being called
-	   from the synchronous end_transaction hook of this module */
-	if (ret == LDB_SUCCESS) {
-		ret = ldb_wait(mod_req->handle, LDB_WAIT_ALL);
-	}
+		ret = replmd_update_la_val(tmp_ctx, pdn->v, dsdb_dn, pdn->dsdb_dn,
+					   &la->meta_data.originating_invocation_id,
+					   la->meta_data.originating_usn, seq_num,
+					   la->meta_data.originating_change_time,
+					   la->meta_data.version,
+					   !active);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
 
-	if (ret == LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS) {
-		/* the link destination exists, we need to update it
-		 * by deleting the old one for the same DN then adding
-		 * the new one */
-		msg->elements = talloc_realloc(msg, msg->elements,
-					       struct ldb_message_element,
-					       msg->num_elements+1);
-		if (msg->elements == NULL) {
-			ldb_oom(ldb);
+		if (active) {
+			/* add the new backlink */
+			ret = replmd_add_backlink(module, schema, &la->identifier->guid, &guid, true, attr, false);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+		}
+	} else {
+		/* get a seq_num for this change */
+		ret = ldb_sequence_number(ldb, LDB_SEQ_NEXT, &seq_num);
+		if (ret != LDB_SUCCESS) {
 			talloc_free(tmp_ctx);
+			return ret;
+		}
+
+		old_el->values = talloc_realloc(msg->elements, old_el->values,
+						struct ldb_val, old_el->num_values+1);
+		if (!old_el->values) {
+			ldb_module_oom(module);
 			return LDB_ERR_OPERATIONS_ERROR;
 		}
-		/* this relies on the backend matching the old entry
-		   only by the DN portion of the extended DN */
-		msg->elements[1] = msg->elements[0];
-		msg->elements[0].flags = LDB_FLAG_MOD_DELETE;
-		msg->num_elements++;
-
-		ret = ldb_build_mod_req(&mod_req, ldb, tmp_ctx,
-					msg,
-					NULL,
-					NULL, 
-					ldb_op_default_callback,
-					NULL);
+		old_el->num_values++;
+
+		ret = replmd_build_la_val(tmp_ctx, &old_el->values[old_el->num_values-1], dsdb_dn,
+					  &la->meta_data.originating_invocation_id,
+					  la->meta_data.originating_usn, seq_num,
+					  la->meta_data.originating_change_time,
+					  la->meta_data.version,
+					  (la->flags & DRSUAPI_DS_LINKED_ATTRIBUTE_FLAG_ACTIVE)?false:true);
 		if (ret != LDB_SUCCESS) {
 			talloc_free(tmp_ctx);
 			return ret;
 		}
 
-		/* Run the new request */
-		ret = ldb_next_request(module, mod_req);
-		
-		if (ret == LDB_SUCCESS) {
-			ret = ldb_wait(mod_req->handle, LDB_WAIT_ALL);
+		if (active) {
+			ret = replmd_add_backlink(module, schema, &la->identifier->guid, &guid,
+						  true, attr, false);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
 		}
 	}
 
+	/* we only change whenChanged and uSNChanged if the seq_num
+	   has changed */
+	if (add_time_element(msg, "whenChanged", t) != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (add_uint64_element(msg, "uSNChanged", seq_num) != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = dsdb_check_single_valued_link(attr, old_el);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	ret = dsdb_module_modify(module, msg, DSDB_MODIFY_RELAX);
 	if (ret != LDB_SUCCESS) {
-		ldb_debug(ldb, LDB_DEBUG_WARNING, "Failed to apply linked attribute change '%s' %s\n",
+		ldb_debug(ldb, LDB_DEBUG_WARNING, "Failed to apply linked attribute change '%s'\n%s\n",
 			  ldb_errstring(ldb),
 			  ldb_ldif_message_string(ldb, tmp_ctx, LDB_CHANGETYPE_MODIFY, msg));
-		ret = LDB_SUCCESS;
+		talloc_free(tmp_ctx);
+		return ret;
 	}
 	
 	talloc_free(tmp_ctx);
@@ -2194,9 +3668,7 @@ static int replmd_start_transaction(struct ldb_module *module)
 	/* create our private structure for this transaction */
 	struct replmd_private *replmd_private = talloc_get_type(ldb_module_get_private(module),
 								struct replmd_private);
-	talloc_free(replmd_private->la_ctx);
-	replmd_private->la_list = NULL;
-	replmd_private->la_ctx = NULL;
+	replmd_txn_cleanup(replmd_private);
 
 	/* free any leftover mod_usn records from cancelled
 	   transactions */
@@ -2218,6 +3690,7 @@ static int replmd_prepare_commit(struct ldb_module *module)
 	struct replmd_private *replmd_private = 
 		talloc_get_type(ldb_module_get_private(module), struct replmd_private);
 	struct la_entry *la, *prev;
+	struct la_backlink *bl;
 	int ret;
 
 	/* walk the list backwards, to do the first entry first, as we
@@ -2230,16 +3703,22 @@ static int replmd_prepare_commit(struct ldb_module *module)
 		DLIST_REMOVE(replmd_private->la_list, la);
 		ret = replmd_process_linked_attribute(module, la);
 		if (ret != LDB_SUCCESS) {
-			talloc_free(replmd_private->la_ctx);
-			replmd_private->la_list = NULL;
-			replmd_private->la_ctx = NULL;
+			replmd_txn_cleanup(replmd_private);
 			return ret;
 		}
 	}
 
-	talloc_free(replmd_private->la_ctx);
-	replmd_private->la_list = NULL;
-	replmd_private->la_ctx = NULL;
+	/* process our backlink list, creating and deleting backlinks
+	   as necessary */
+	for (bl=replmd_private->la_backlinks; bl; bl=bl->next) {
+		ret = replmd_process_backlink(module, bl);
+		if (ret != LDB_SUCCESS) {
+			replmd_txn_cleanup(replmd_private);
+			return ret;
+		}
+	}
+
+	replmd_txn_cleanup(replmd_private);
 
 	/* possibly change @REPLCHANGED */
 	ret = replmd_notify_store(module);
@@ -2254,9 +3733,8 @@ static int replmd_del_transaction(struct ldb_module *module)
 {
 	struct replmd_private *replmd_private = 
 		talloc_get_type(ldb_module_get_private(module), struct replmd_private);
-	talloc_free(replmd_private->la_ctx);
-	replmd_private->la_list = NULL;
-	replmd_private->la_ctx = NULL;
+	replmd_txn_cleanup(replmd_private);
+
 	return ldb_next_del_trans(module);
 }
 
@@ -2267,6 +3745,7 @@ _PUBLIC_ const struct ldb_module_ops ldb_repl_meta_data_module_ops = {
 	.add               = replmd_add,
 	.modify            = replmd_modify,
 	.rename            = replmd_rename,
+	.del	           = replmd_delete,
 	.extended          = replmd_extended,
 	.start_transaction = replmd_start_transaction,
 	.prepare_commit    = replmd_prepare_commit,
diff --git a/source4/dsdb/samdb/ldb_modules/samba_dsdb.c b/source4/dsdb/samdb/ldb_modules/samba_dsdb.c
index ee7e42ef9b..a461a94806 100644
--- a/source4/dsdb/samdb/ldb_modules/samba_dsdb.c
+++ b/source4/dsdb/samdb/ldb_modules/samba_dsdb.c
@@ -38,6 +38,7 @@
 
 #include "dsdb/samdb/ldb_modules/util.h"
 #include "dsdb/samdb/samdb.h"
+#include "librpc/ndr/libndr.h"
 
 static int read_at_rootdse_record(struct ldb_context *ldb, struct ldb_module *module, TALLOC_CTX *mem_ctx,
 				  struct ldb_message **msg)
@@ -135,6 +136,55 @@ static int prepare_modules_line(struct ldb_context *ldb,
 	return ret;
 }
 
+
+
+/*
+  initialise the invocationID for a standalone server
+ */
+static int initialise_invocation_id(struct ldb_module *module, struct GUID *guid)
+{
+	struct ldb_message *msg;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	int ret;
+
+	*guid = GUID_random();
+
+	msg = ldb_msg_new(module);
+	if (msg == NULL) {
+		ldb_module_oom(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	msg->dn = ldb_dn_new(msg, ldb, "@SAMBA_DSDB");
+	if (!msg->dn) {
+		ldb_module_oom(module);
+		talloc_free(msg);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ret = dsdb_msg_add_guid(msg, guid, "invocationID");
+	if (ret != LDB_SUCCESS) {
+		ldb_module_oom(module);
+		talloc_free(msg);
+		return ret;
+	}
+	msg->elements[0].flags = LDB_FLAG_MOD_ADD;
+
+	ret = ldb_modify(ldb, msg);
+	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb, "Failed to setup standalone invocationID - %s",
+				       ldb_errstring(ldb));
+		talloc_free(msg);
+		return ret;
+	}
+
+	DEBUG(1,("Initialised standalone invocationID to %s\n",
+		 GUID_string(msg, guid)));
+
+	talloc_free(msg);
+
+	return LDB_SUCCESS;
+}
+
+
 static int samba_dsdb_init(struct ldb_module *module)
 {
 	struct ldb_context *ldb = ldb_module_get_ctx(module);
@@ -184,16 +234,11 @@ static int samba_dsdb_init(struct ldb_module *module)
 					     "instancetype",
 					     NULL };
 
-	const char *objectguid_module;
-	/* if serverrole == "domain controller": */
-	const char *repl_meta_data = "repl_meta_data";
-	/*    else: */
-        const char *objectguid = "objectguid";
-
 	const char **link_modules;
 	static const char *tdb_modules_list[] = {
-		"subtree_rename",
 		"subtree_delete",
+		"repl_meta_data",
+		"subtree_rename",
 		"linked_attributes",
 		NULL};
 
@@ -213,7 +258,7 @@ static int samba_dsdb_init(struct ldb_module *module)
 	static const char *openldap_backend_modules[] = {
 		"entryuuid", "paged_searches", NULL };
 
-	static const char *samba_dsdb_attrs[] = { "backendType", "serverRole", NULL };
+	static const char *samba_dsdb_attrs[] = { "backendType", "serverRole", "invocationID", NULL };
 	const char *backendType, *serverRole;
 
 	if (!tmp_ctx) {
@@ -248,17 +293,39 @@ static int samba_dsdb_init(struct ldb_module *module)
 		return ret;
 	}
 
+	if (strcmp(serverRole, "standalone") == 0 ||
+	    strcmp(serverRole, "member server") == 0) {
+		struct GUID *guid;
+
+		guid = talloc(module, struct GUID);
+		if (!guid) {
+			ldb_module_oom(module);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		*guid = samdb_result_guid(res->msgs[0], "invocationID");
+		if (GUID_all_zero(guid)) {
+			ret = initialise_invocation_id(module, guid);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(tmp_ctx);
+				return ret;
+			}
+		}
+
+		/* cache the domain_sid in the ldb. See the matching
+		 * code in samdb_ntds_invocation_id() */
+		ret = ldb_set_opaque(ldb, "cache.invocation_id", guid);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(tmp_ctx);
+			return ret;
+		}
+	}
+
 	backend_modules = NULL;
 	if (strcasecmp(backendType, "ldb") == 0) {
-		if (strcasecmp(serverRole, "dc") == 0 || strcasecmp(serverRole, "domain controller") == 0) {
-			objectguid_module = repl_meta_data;
-		} else {
-			objectguid_module = objectguid;
-		}
 		extended_dn_module = extended_dn_module_ldb;
 		link_modules = tdb_modules_list;
 	} else {
-		objectguid_module = NULL;
 		link_modules = NULL;
 		if (strcasecmp(backendType, "fedora-ds") == 0) {
 			backend_modules = fedora_ds_backend_modules;
@@ -281,9 +348,6 @@ static int samba_dsdb_init(struct ldb_module *module)
 	final_module_list = str_list_copy_const(tmp_ctx, modules_list);
 	CHECK_MODULE_LIST;
 
-	final_module_list = str_list_add_const(final_module_list, objectguid_module);
-	CHECK_MODULE_LIST;
-
 	final_module_list = str_list_append_const(final_module_list, link_modules);
 	CHECK_MODULE_LIST;
 
diff --git a/source4/dsdb/samdb/ldb_modules/schema_data.c b/source4/dsdb/samdb/ldb_modules/schema_data.c
index ed10ae6d69..2e99113953 100644
--- a/source4/dsdb/samdb/ldb_modules/schema_data.c
+++ b/source4/dsdb/samdb/ldb_modules/schema_data.c
@@ -92,6 +92,37 @@ struct schema_data_search_data {
 	const struct dsdb_schema *schema;
 };
 
+/* context to be used during async operations */
+struct schema_data_context {
+	struct ldb_module *module;
+	struct ldb_request *req;
+
+	const struct dsdb_schema *schema;
+};
+
+/* Create new context using
+ * ldb_request as memory context */
+static int _schema_data_context_new(struct ldb_module *module,
+				    struct ldb_request *req,
+				    struct schema_data_context **pac)
+{
+	struct schema_data_context *ac;
+	struct ldb_context *ldb;
+
+	ldb = ldb_module_get_ctx(module);
+
+	*pac = ac = talloc_zero(req, struct schema_data_context);
+	if (ac == NULL) {
+		ldb_oom(ldb);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac->module = module;
+	ac->req = req;
+	ac->schema = dsdb_get_schema(ldb);
+
+	return LDB_SUCCESS;
+}
+
 static int schema_data_init(struct ldb_module *module)
 {
 	struct ldb_context *ldb;
@@ -132,6 +163,57 @@ static int schema_data_init(struct ldb_module *module)
 	return LDB_SUCCESS;
 }
 
+
+/* Generate new value for msDs-IntId
+ * Value should be in 0x80000000..0xBFFFFFFF range
+ * Generated value is added ldb_msg */
+static int _schema_data_gen_msds_intid(struct schema_data_context *ac,
+				       struct ldb_message *ldb_msg)
+{
+	uint32_t id;
+
+	/* generate random num in 0x80000000..0xBFFFFFFF */
+	id = generate_random() % 0X3FFFFFFF;
+	id += 0x80000000;
+
+	/* make sure id is unique and adjust if not */
+	while (dsdb_attribute_by_attributeID_id(ac->schema, id)) {
+		id++;
+		if (id > 0xBFFFFFFF) {
+			id = 0x80000001;
+		}
+	}
+
+	/* add generated msDS-IntId value to ldb_msg */
+	return ldb_msg_add_fmt(ldb_msg, "msDS-IntId", "%d", id);
+}
+
+static int _schema_data_add_callback(struct ldb_request *req,
+				     struct ldb_reply *ares)
+{
+	struct schema_data_context *ac;
+
+	ac = talloc_get_type(req->context, struct schema_data_context);
+
+	if (!ares) {
+		return ldb_module_done(ac->req, NULL, NULL,
+					LDB_ERR_OPERATIONS_ERROR);
+	}
+	if (ares->error != LDB_SUCCESS) {
+		return ldb_module_done(ac->req, ares->controls,
+					ares->response, ares->error);
+	}
+
+	if (ares->type != LDB_REPLY_DONE) {
+		talloc_free(ares);
+		return ldb_module_done(ac->req, NULL, NULL,
+					LDB_ERR_OPERATIONS_ERROR);
+	}
+
+	return ldb_module_done(ac->req, ares->controls,
+				ares->response, ares->error);
+}
+
 static int schema_data_add(struct ldb_module *module, struct ldb_request *req)
 {
 	struct ldb_context *ldb;
@@ -140,7 +222,6 @@ static int schema_data_add(struct ldb_module *module, struct ldb_request *req)
 	const struct ldb_val *governsID = NULL;
 	const char *oid_attr = NULL;
 	const char *oid = NULL;
-	uint32_t attid;
 	WERROR status;
 
 	ldb = ldb_module_get_ctx(module);
@@ -170,6 +251,11 @@ static int schema_data_add(struct ldb_module *module, struct ldb_request *req)
 	governsID = ldb_msg_find_ldb_val(req->op.add.message, "governsID");
 
 	if (attributeID) {
+		/* Sanity check for not allowed attributes */
+		if (ldb_msg_find_ldb_val(req->op.add.message, "msDS-IntId")) {
+			return LDB_ERR_UNWILLING_TO_PERFORM;
+		}
+
 		oid_attr = "attributeID";
 		oid = talloc_strndup(req, (const char *)attributeID->data, attributeID->length);
 	} else if (governsID) {
@@ -183,25 +269,83 @@ static int schema_data_add(struct ldb_module *module, struct ldb_request *req)
 		ldb_oom(ldb);
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
-		
-	status = dsdb_schema_pfm_make_attid(schema->prefixmap, oid, &attid);
-	if (W_ERROR_IS_OK(status)) {
+
+	status = dsdb_schema_pfm_find_oid(schema->prefixmap, oid, NULL);
+	if (!W_ERROR_IS_OK(status)) {
+		/* check for internal errors */
+		if (!W_ERROR_EQUAL(WERR_DS_NO_MSDS_INTID, status)) {
+			ldb_debug_set(ldb, LDB_DEBUG_ERROR,
+			              "schema_data_add: failed to map %s[%s]: %s\n",
+			              oid_attr, oid, win_errstr(status));
+			return LDB_ERR_UNWILLING_TO_PERFORM;
+		}
+
+		/* Update prefixMap and save it */
+		status = dsdb_create_prefix_mapping(ldb, schema, oid);
+		if (!W_ERROR_IS_OK(status)) {
+			ldb_debug_set(ldb, LDB_DEBUG_ERROR,
+				  "schema_data_add: failed to create prefix mapping for %s[%s]: %s\n",
+				  oid_attr, oid, win_errstr(status));
+			return LDB_ERR_UNWILLING_TO_PERFORM;
+		}
+	}
+
+	/* generate and add msDS-IntId attr value */
+	if (attributeID
+	    && (dsdb_functional_level(ldb) >= DS_DOMAIN_FUNCTION_2003)
+	    && !(ldb_msg_find_attr_as_uint(req->op.add.message, "systemFlags", 0) & SYSTEM_FLAG_SCHEMA_BASE_OBJECT)) {
+		struct ldb_message *msg;
+		struct schema_data_context *ac;
+		struct ldb_request *add_req;
+
+		if (_schema_data_context_new(module, req, &ac) != LDB_SUCCESS) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		/* we have to copy the message as the caller might have it as a const */
+		msg = ldb_msg_copy_shallow(ac, req->op.add.message);
+		if (msg == NULL) {
+			ldb_oom(ldb);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		/* generate unique value for msDS-IntId attr value */
+		if (_schema_data_gen_msds_intid(ac, msg) != LDB_SUCCESS) {
+			ldb_debug_set(ldb, LDB_DEBUG_ERROR,
+			              "_schema_data_gen_msds_intid() failed to generate msDS-IntId value\n");
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ldb_build_add_req(&add_req, ldb, ac,
+				  msg,
+				  req->controls,
+				  ac, _schema_data_add_callback,
+				  req);
+
+		return ldb_next_request(module, add_req);
+	}
+
+	return ldb_next_request(module, req);
+}
+
+static int schema_data_modify(struct ldb_module *module, struct ldb_request *req)
+{
+	/* special objects should always go through */
+	if (ldb_dn_is_special(req->op.mod.message->dn)) {
 		return ldb_next_request(module, req);
-	} else if (!W_ERROR_EQUAL(WERR_DS_NO_MSDS_INTID, status)) {
-		ldb_debug_set(ldb, LDB_DEBUG_ERROR,
-			  "schema_data_add: failed to map %s[%s]: %s\n",
-			  oid_attr, oid, win_errstr(status));
-		return LDB_ERR_UNWILLING_TO_PERFORM;
 	}
 
-	status = dsdb_create_prefix_mapping(ldb, schema, oid);
-	if (!W_ERROR_IS_OK(status)) {
-		ldb_debug_set(ldb, LDB_DEBUG_ERROR,
-			  "schema_data_add: failed to create prefix mapping for %s[%s]: %s\n",
-			  oid_attr, oid, win_errstr(status));
-		return LDB_ERR_UNWILLING_TO_PERFORM;
+	/* replicated update should always go through */
+	if (ldb_request_get_control(req, DSDB_CONTROL_REPLICATED_UPDATE_OID)) {
+		return ldb_next_request(module, req);
+	}
+
+	/* msDS-IntId is not allowed to be modified */
+	if (ldb_msg_find_ldb_val(req->op.mod.message, "msDS-IntId")) {
+		return LDB_ERR_CONSTRAINT_VIOLATION;
 	}
 
+	/* go on with the call chain */
 	return ldb_next_request(module, req);
 }
 
@@ -460,5 +604,6 @@ _PUBLIC_ const struct ldb_module_ops ldb_schema_data_module_ops = {
 	.name		= "schema_data",
 	.init_context	= schema_data_init,
 	.add		= schema_data_add,
+	.modify		= schema_data_modify,
 	.search         = schema_data_search
 };
diff --git a/source4/dsdb/samdb/ldb_modules/simple_ldap_map.c b/source4/dsdb/samdb/ldb_modules/simple_ldap_map.c
index 43402248c0..bf9cd4fdda 100644
--- a/source4/dsdb/samdb/ldb_modules/simple_ldap_map.c
+++ b/source4/dsdb/samdb/ldb_modules/simple_ldap_map.c
@@ -181,7 +181,7 @@ static struct ldb_val usn_to_entryCSN(struct ldb_module *module, TALLOC_CTX *ctx
 
 static unsigned long long entryCSN_to_usn_int(TALLOC_CTX *ctx, const struct ldb_val *val) 
 {
-	char *entryCSN = talloc_strdup(ctx, (const char *)val->data);
+	char *entryCSN = talloc_strndup(ctx, (const char *)val->data, val->length);
 	char *mod_per_sec;
 	time_t t;
 	unsigned long long usn;
@@ -232,10 +232,10 @@ static struct ldb_val usn_to_timestamp(struct ldb_module *module, TALLOC_CTX *ct
 static struct ldb_val timestamp_to_usn(struct ldb_module *module, TALLOC_CTX *ctx, const struct ldb_val *val)
 {
 	struct ldb_val out;
-	time_t t;
+	time_t t=0;
 	unsigned long long usn;
 
-	t = ldb_string_to_time((const char *)val->data);
+	ldb_val_to_time(val, &t);
 	
 	usn = ((unsigned long long)t <<24);
 
diff --git a/source4/dsdb/samdb/ldb_modules/util.c b/source4/dsdb/samdb/ldb_modules/util.c
index 8d9930a81f..32b79a6701 100644
--- a/source4/dsdb/samdb/ldb_modules/util.c
+++ b/source4/dsdb/samdb/ldb_modules/util.c
@@ -87,6 +87,13 @@ int dsdb_request_add_controls(struct ldb_module *module, struct ldb_request *req
 		}
 	}
 
+	if (dsdb_flags & DSDB_MODIFY_RELAX) {
+		ret = ldb_request_add_control(req, LDB_CONTROL_RELAX_OID, false, NULL);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+
 	return LDB_SUCCESS;
 }
 
@@ -164,15 +171,21 @@ int dsdb_module_search(struct ldb_module *module,
 		       struct ldb_dn *basedn, enum ldb_scope scope, 
 		       const char * const *attrs,
 		       int dsdb_flags, 
-		       const char *expression)
+		       const char *format, ...) _PRINTF_ATTRIBUTE(8, 9)
 {
 	int ret;
 	struct ldb_request *req;
 	TALLOC_CTX *tmp_ctx;
 	struct ldb_result *res;
+	va_list ap;
+	char *expression;
 
 	tmp_ctx = talloc_new(mem_ctx);
 
+	va_start(ap, format);
+	expression = talloc_vasprintf(tmp_ctx, format, ap);
+	va_end(ap);
+
 	res = talloc_zero(tmp_ctx, struct ldb_result);
 	if (!res) {
 		return LDB_ERR_OPERATIONS_ERROR;
@@ -198,7 +211,12 @@ int dsdb_module_search(struct ldb_module *module,
 		return ret;
 	}
 
-	ret = ldb_next_request(module, req);
+	if (dsdb_flags & DSDB_FLAG_OWN_MODULE) {
+		const struct ldb_module_ops *ops = ldb_module_get_ops(module);
+		ret = ops->search(module, req);
+	} else {
+		ret = ldb_next_request(module, req);
+	}
 	if (ret == LDB_SUCCESS) {
 		ret = ldb_wait(req->handle, LDB_WAIT_ALL);
 	}
@@ -219,22 +237,15 @@ int dsdb_module_dn_by_guid(struct ldb_module *module, TALLOC_CTX *mem_ctx,
 {
 	struct ldb_result *res;
 	const char *attrs[] = { NULL };
-	char *expression;
 	TALLOC_CTX *tmp_ctx = talloc_new(mem_ctx);
 	int ret;
 
-	expression = talloc_asprintf(tmp_ctx, "objectGUID=%s", GUID_string(tmp_ctx, guid));
-	if (!expression) {
-		ldb_module_oom(module);
-		return LDB_ERR_OPERATIONS_ERROR;
-	}
-
 	ret = dsdb_module_search(module, tmp_ctx, &res, NULL, LDB_SCOPE_SUBTREE,
 				 attrs,
 				 DSDB_SEARCH_SHOW_DELETED |
 				 DSDB_SEARCH_SEARCH_ALL_PARTITIONS |
 				 DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT,
-				 expression);
+				 "objectGUID=%s", GUID_string(tmp_ctx, guid));
 	if (ret != LDB_SUCCESS) {
 		talloc_free(tmp_ctx);
 		return ret;
@@ -244,8 +255,8 @@ int dsdb_module_dn_by_guid(struct ldb_module *module, TALLOC_CTX *mem_ctx,
 		return LDB_ERR_NO_SUCH_OBJECT;
 	}
 	if (res->count != 1) {
-		ldb_asprintf_errstring(ldb_module_get_ctx(module), "More than one object found matching %s\n",
-				       expression);
+		ldb_asprintf_errstring(ldb_module_get_ctx(module), "More than one object found matching objectGUID %s\n",
+				       GUID_string(tmp_ctx, guid));
 		talloc_free(tmp_ctx);
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
@@ -257,6 +268,37 @@ int dsdb_module_dn_by_guid(struct ldb_module *module, TALLOC_CTX *mem_ctx,
 }
 
 /*
+  find a GUID given a DN.
+ */
+int dsdb_module_guid_by_dn(struct ldb_module *module, struct ldb_dn *dn, struct GUID *guid)
+{
+	const char *attrs[] = { NULL };
+	struct ldb_result *res;
+	TALLOC_CTX *tmp_ctx = talloc_new(module);
+	int ret;
+	NTSTATUS status;
+
+	ret = dsdb_module_search_dn(module, tmp_ctx, &res, dn, attrs,
+				    DSDB_SEARCH_SHOW_DELETED|
+				    DSDB_SEARCH_SHOW_EXTENDED_DN);
+	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb_module_get_ctx(module), "Failed to find GUID for %s",
+				       ldb_dn_get_linearized(dn));
+		talloc_free(tmp_ctx);
+		return ret;
+	}
+
+	status = dsdb_get_extended_dn_guid(res->msgs[0]->dn, guid, "GUID");
+	if (!NT_STATUS_IS_OK(status)) {
+		talloc_free(tmp_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	talloc_free(tmp_ctx);
+	return LDB_SUCCESS;
+}
+
+/*
   a ldb_modify request operating on modules below the
   current module
  */
@@ -287,7 +329,12 @@ int dsdb_module_modify(struct ldb_module *module,
 	}
 
 	/* Run the new request */
-	ret = ldb_next_request(module, mod_req);
+	if (dsdb_flags & DSDB_FLAG_OWN_MODULE) {
+		const struct ldb_module_ops *ops = ldb_module_get_ops(module);
+		ret = ops->modify(module, mod_req);
+	} else {
+		ret = ldb_next_request(module, mod_req);
+	}
 	if (ret == LDB_SUCCESS) {
 		ret = ldb_wait(mod_req->handle, LDB_WAIT_ALL);
 	}
@@ -330,7 +377,12 @@ int dsdb_module_rename(struct ldb_module *module,
 	}
 
 	/* Run the new request */
-	ret = ldb_next_request(module, req);
+	if (dsdb_flags & DSDB_FLAG_OWN_MODULE) {
+		const struct ldb_module_ops *ops = ldb_module_get_ops(module);
+		ret = ops->rename(module, req);
+	} else {
+		ret = ldb_next_request(module, req);
+	}
 	if (ret == LDB_SUCCESS) {
 		ret = ldb_wait(req->handle, LDB_WAIT_ALL);
 	}
@@ -365,3 +417,32 @@ const struct dsdb_class * get_last_structural_class(const struct dsdb_schema *sc
 
 	return last_class;
 }
+
+/*
+  check if a single valued link has multiple non-deleted values
+
+  This is needed when we will be using the RELAX control to stop
+  ldb_tdb from checking single valued links
+ */
+int dsdb_check_single_valued_link(const struct dsdb_attribute *attr,
+				  const struct ldb_message_element *el)
+{
+	bool found_active = false;
+	int i;
+
+	if (!(attr->ldb_schema_attribute->flags & LDB_ATTR_FLAG_SINGLE_VALUE) ||
+	    el->num_values < 2) {
+		return LDB_SUCCESS;
+	}
+
+	for (i=0; i<el->num_values; i++) {
+		if (!dsdb_dn_is_deleted_val(&el->values[i])) {
+			if (found_active) {
+				return LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+			}
+			found_active = true;
+		}
+	}
+
+	return LDB_SUCCESS;
+}
diff --git a/source4/dsdb/samdb/ldb_modules/util.h b/source4/dsdb/samdb/ldb_modules/util.h
index 41ed883dc2..add39e110a 100644
--- a/source4/dsdb/samdb/ldb_modules/util.h
+++ b/source4/dsdb/samdb/ldb_modules/util.h
@@ -21,6 +21,8 @@
 
 struct dsdb_schema; /* predeclare schema struct */
 struct GUID;
+struct dsdb_attribute;
+
 #include "dsdb/samdb/ldb_modules/util_proto.h"
 
 #define DSDB_SEARCH_SEARCH_ALL_PARTITIONS     0x0001
@@ -28,3 +30,5 @@ struct GUID;
 #define DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT 0x0004
 #define DSDB_SEARCH_REVEAL_INTERNALS          0x0008
 #define DSDB_SEARCH_SHOW_EXTENDED_DN          0x0010
+#define DSDB_MODIFY_RELAX		      0x0020
+#define DSDB_FLAG_OWN_MODULE		      0x0040