static int replmd_delete_internals(struct ldb_module *module, struct ldb_request *req, bool re_delete)
{
	int ret = LDB_ERR_OTHER;
	bool retb, disallow_move_on_delete;
	struct ldb_dn *old_dn = NULL, *new_dn = NULL;
	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);
	const struct dsdb_schema *schema;
	struct ldb_message *msg, *old_msg;
	struct ldb_message_element *el;
	TALLOC_CTX *tmp_ctx;
	struct ldb_result *res, *parent_res;
	static const char * const preserved_attrs[] = {
		/*
		 * This list MUST be kept in case-insensitive sorted order,
		 * as we  use it in a binary search with ldb_attr_cmp().
		 *
		 * We get this hard-coded list from
		 * MS-ADTS section 3.1.1.5.5.1.1 "Tombstone Requirements".
		 */
		"attributeID",
		"attributeSyntax",
		"distinguishedName",
		"dNReferenceUpdate",
		"dNSHostName",
		"flatName",
		"governsID",
		"groupType",
		"instanceType",
		"isDeleted",
		"isRecycled",
		"lastKnownParent",
		"lDAPDisplayName",
		"legacyExchangeDN",
		"mS-DS-CreatorSID",
		"msDS-LastKnownRDN",
		"msDS-PortLDAP",
		"mSMQOwnerID",
		"name",
		"nCName",
		"nTSecurityDescriptor",
		"objectClass",
		"objectGUID",
		"objectSid",
		"oMSyntax",
		"proxiedObjectName",
		"replPropertyMetaData",
		"sAMAccountName",
		"securityIdentifier",
		"sIDHistory",
		"subClassOf",
		"systemFlags",
		"trustAttributes",
		"trustDirection",
		"trustPartner",
		"trustType",
		"userAccountControl",
		"uSNChanged",
		"uSNCreated",
		"whenChanged",
		"whenCreated",
		/*
		 * DO NOT JUST APPEND TO THIS LIST.
		 *
		 * In case you missed the note at the top, this list is kept
		 * in case-insensitive sorted order. In the unlikely event you
		 * need to add an attrbute, please add it in the RIGHT PLACE.
		 */
	};
	static const char * const all_attrs[] = {
		DSDB_SECRET_ATTRIBUTES,
		"*",
		NULL
	};
	static const struct ldb_val true_val = {
		.data = discard_const_p(uint8_t, "TRUE"),
		.length = 4
	};
	
	unsigned int i;
	uint32_t dsdb_flags = 0;
	struct replmd_private *replmd_private;
	enum deletion_state deletion_state, next_deletion_state;

	if (ldb_dn_is_special(req->op.del.dn)) {
		return ldb_next_request(module, req);
	}

	/*
	 * We have to allow dbcheck to remove an object that
	 * is beyond repair, and to do so totally.  This could
	 * mean we we can get a partial object from the other
	 * DC, causing havoc, so dbcheck suggests
	 * re-replication first.  dbcheck sets both DBCHECK
	 * and RELAX in this situation.
	 */
	if (ldb_request_get_control(req, LDB_CONTROL_RELAX_OID)
	    && ldb_request_get_control(req, DSDB_CONTROL_DBCHECK)) {
		/* really, really remove it */
		return ldb_next_request(module, req);
	}

	tmp_ctx = talloc_new(ldb);
	if (!tmp_ctx) {
		ldb_oom(ldb);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	schema = dsdb_get_schema(ldb, tmp_ctx);
	if (!schema) {
		talloc_free(tmp_ctx);
		return LDB_ERR_OPERATIONS_ERROR;
	}

	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, all_attrs,
	                            DSDB_FLAG_NEXT_MODULE |
	                            DSDB_SEARCH_SHOW_RECYCLED |
				    DSDB_SEARCH_REVEAL_INTERNALS |
				    DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT, req);
	if (ret != LDB_SUCCESS) {
		ldb_asprintf_errstring(ldb_module_get_ctx(module),
				       "repmd_delete: Failed to %s %s, because we failed to find it: %s",
				       re_delete ? "re-delete" : "delete",
				       ldb_dn_get_linearized(old_dn),
				       ldb_errstring(ldb_module_get_ctx(module)));
		talloc_free(tmp_ctx);
		return ret;
	}
	old_msg = res->msgs[0];

	replmd_deletion_state(module, old_msg,
			      &deletion_state,
			      &next_deletion_state);

	/* This supports us noticing an incoming isDeleted and acting on it */
	if (re_delete) {
		SMB_ASSERT(deletion_state > OBJECT_NOT_DELETED);
		next_deletion_state = deletion_state;
	}

	if (next_deletion_state == OBJECT_REMOVED) {
		/*
		 * We have to prevent objects being deleted, even if
		 * the administrator really wants them gone, as
		 * without the tombstone, we can get a partial object
		 * from the other DC, causing havoc.
		 *
		 * The only other valid case is when the 180 day
		 * timeout has expired, when relax is specified.
		 */
		if (ldb_request_get_control(req, LDB_CONTROL_RELAX_OID)) {
			/* it is already deleted - really remove it this time */
			talloc_free(tmp_ctx);
			return ldb_next_request(module, req);
		}

		ldb_asprintf_errstring(ldb, "Refusing to delete tombstone object %s.  "
				       "This check is to prevent corruption of the replicated state.",
				       ldb_dn_get_linearized(old_msg->dn));
		return LDB_ERR_UNWILLING_TO_PERFORM;
	}

	rdn_name = ldb_dn_get_rdn_name(old_dn);
	rdn_value = ldb_dn_get_rdn_val(old_dn);
	if ((rdn_name == NULL) || (rdn_value == NULL)) {
		talloc_free(tmp_ctx);
		return ldb_operr(ldb);
	}

	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;

	/* consider the SYSTEM_FLAG_DISALLOW_MOVE_ON_DELETE flag */
	disallow_move_on_delete =
		(ldb_msg_find_attr_as_int(old_msg, "systemFlags", 0)
		 & SYSTEM_FLAG_DISALLOW_MOVE_ON_DELETE);

	/* work out where we will be renaming this object to */
	if (!disallow_move_on_delete) {
		struct ldb_dn *deleted_objects_dn;
		ret = dsdb_get_deleted_objects_dn(ldb, tmp_ctx, old_dn,
						  &deleted_objects_dn);

		/*
		 * We should not move objects if we can't find the
		 * deleted objects DN.  Not moving (or otherwise
		 * harming) the Deleted Objects DN itself is handled
		 * in the caller.
		 */
		if (re_delete && (ret != LDB_SUCCESS)) {
			new_dn = ldb_dn_get_parent(tmp_ctx, old_dn);
			if (new_dn == NULL) {
				ldb_module_oom(module);
				talloc_free(tmp_ctx);
				return LDB_ERR_OPERATIONS_ERROR;
			}
		} else 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;
		} else {
			new_dn = deleted_objects_dn;
		}
	} else {
		new_dn = ldb_dn_get_parent(tmp_ctx, old_dn);
		if (new_dn == NULL) {
			ldb_module_oom(module);
			talloc_free(tmp_ctx);
			return LDB_ERR_OPERATIONS_ERROR;
		}
	}

	/* get the objects GUID from the search we just did */
	guid = samdb_result_guid(old_msg, "objectGUID");

	if (deletion_state == OBJECT_NOT_DELETED) {
		struct ldb_message_element *is_deleted_el;

		ret = replmd_make_deleted_child_dn(tmp_ctx,
						   ldb,
						   new_dn,
						   rdn_name, rdn_value,
						   guid);

		if (ret != LDB_SUCCESS) {
			talloc_free(tmp_ctx);
			return ret;
		}

		ret = ldb_msg_add_value(msg, "isDeleted", &true_val,
					&is_deleted_el);
		if (ret != LDB_SUCCESS) {
			ldb_asprintf_errstring(ldb, __location__
					       ": Failed to add isDeleted string to the msg");
			talloc_free(tmp_ctx);
			return ret;
		}
		is_deleted_el->flags = LDB_FLAG_MOD_REPLACE;
	} else {
		/*
		 * No matter what has happened with other renames etc, try again to
		 * get this to be under the deleted DN. See MS-DRSR 5.160 RemoveObj
		 */

		struct ldb_dn *rdn = ldb_dn_copy(tmp_ctx, old_dn);
		retb = ldb_dn_remove_base_components(rdn, ldb_dn_get_comp_num(rdn) - 1);
		if (!retb) {
			ldb_asprintf_errstring(ldb, __location__
					       ": Unable to add a prepare rdn of %s",
					       ldb_dn_get_linearized(rdn));
			talloc_free(tmp_ctx);
			return LDB_ERR_OPERATIONS_ERROR;
		}
		SMB_ASSERT(ldb_dn_get_comp_num(rdn) == 1);

		retb = ldb_dn_add_child(new_dn, rdn);
		if (!retb) {
			ldb_asprintf_errstring(ldb, __location__
					       ": Unable to add rdn %s to base dn: %s",
					       ldb_dn_get_linearized(rdn),
					       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
	    (note we use the backlinks to do this, so we won't find one-way
	     links that still point to this object, or deactivated two-way
	     links, i.e. 'member' after the user has been removed from the
	     group)
	  - add lastKnownParent
	  - update replPropertyMetaData?

	  see MS-ADTS "Tombstone Requirements" section 3.1.1.5.5.1.1
	 */

	if (deletion_state == OBJECT_NOT_DELETED) {
		struct ldb_dn *parent_dn = ldb_dn_get_parent(tmp_ctx, old_dn);
		char *parent_dn_str = NULL;
		struct ldb_message_element *p_el;

		/* we need the storage form of the parent GUID */
		ret = dsdb_module_search_dn(module, tmp_ctx, &parent_res,
					    parent_dn, NULL,
					    DSDB_FLAG_NEXT_MODULE |
					    DSDB_SEARCH_SHOW_DN_IN_STORAGE_FORMAT |
					    DSDB_SEARCH_REVEAL_INTERNALS|
					    DSDB_SEARCH_SHOW_RECYCLED, req);
		if (ret != LDB_SUCCESS) {
			ldb_asprintf_errstring(ldb_module_get_ctx(module),
					       "repmd_delete: Failed to %s %s, "
					       "because we failed to find it's parent (%s): %s",
					       re_delete ? "re-delete" : "delete",
					       ldb_dn_get_linearized(old_dn),
					       ldb_dn_get_linearized(parent_dn),
					       ldb_errstring(ldb_module_get_ctx(module)));
			talloc_free(tmp_ctx);
			return ret;
		}

		/*
		 * Now we can use the DB version,
		 * it will have the extended DN info in it
		 */
		parent_dn = parent_res->msgs[0]->dn;
		parent_dn_str = ldb_dn_get_extended_linearized(tmp_ctx,
							       parent_dn,
							       1);
		if (parent_dn_str == NULL) {
			talloc_free(tmp_ctx);
			return ldb_module_oom(module);
		}

		ret = ldb_msg_add_steal_string(msg, "lastKnownParent",
					       parent_dn_str);
		if (ret != LDB_SUCCESS) {
			ldb_asprintf_errstring(ldb, __location__
					       ": Failed to add lastKnownParent "
					       "string when deleting %s",
					       ldb_dn_get_linearized(old_dn));
			talloc_free(tmp_ctx);
			return ret;
		}
		p_el = ldb_msg_find_element(msg,
					    "lastKnownParent");
		if (p_el == NULL) {
			talloc_free(tmp_ctx);
			return ldb_module_operr(module);
		}
		p_el->flags = LDB_FLAG_MOD_REPLACE;

		if (next_deletion_state == OBJECT_DELETED) {
			ret = ldb_msg_add_value(msg, "msDS-LastKnownRDN", rdn_value, NULL);
			if (ret != LDB_SUCCESS) {
				ldb_asprintf_errstring(ldb, __location__
						       ": Failed to add msDS-LastKnownRDN "
						       "string when deleting %s",
						       ldb_dn_get_linearized(old_dn));
				talloc_free(tmp_ctx);
				return ret;
			}
			p_el = ldb_msg_find_element(msg,
						    "msDS-LastKnownRDN");
			if (p_el == NULL) {
				talloc_free(tmp_ctx);
				return ldb_module_operr(module);
			}
			p_el->flags = LDB_FLAG_MOD_ADD;
		}
	}

	switch (next_deletion_state) {

	case OBJECT_RECYCLED:
	case OBJECT_TOMBSTONE:

		/*
		 * MS-ADTS 3.1.1.5.5.1.1 Tombstone Requirements
		 * describes what must be removed from a tombstone
		 * object
		 *
		 * MS-ADTS 3.1.1.5.5.1.3 Recycled-Object Requirements
		 * describes what must be removed from a recycled
		 * object
		 *
		 */

		/*
		 * we also mark it as recycled, meaning this object can't be
		 * recovered (we are stripping its attributes).
		 * This is done only if we have this schema object of course ...
		 * This behavior is identical to the one of Windows 2008R2 which
		 * always set the isRecycled attribute, even if the recycle-bin is
		 * not activated and what ever the forest level is.
		 */
		if (dsdb_attribute_by_lDAPDisplayName(schema, "isRecycled") != NULL) {
			struct ldb_message_element *is_recycled_el;

			ret = ldb_msg_add_value(msg, "isRecycled", &true_val,
						&is_recycled_el);
			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;
			}
			is_recycled_el->flags = LDB_FLAG_MOD_REPLACE;
		}

		replmd_private = talloc_get_type(ldb_module_get_private(module),
						 struct replmd_private);
		/* 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) {
				const char *old_dn_str
					= ldb_dn_get_linearized(old_dn);

				ldb_asprintf_errstring(ldb,
						       __location__
						       ": Attribute %s "
						       "not found in schema "
						       "when deleting %s. "
						       "Existing record is invalid",
						       el->name,
						       old_dn_str);
				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 & 1) {
				bool caller_should_vanish = false;
				/*
				 * we have a backlink in this object
				 * that needs to be removed. We're not
				 * allowed to remove it directly
				 * however, so we instead setup a
				 * modify to delete the corresponding
				 * forward link
				 */
				ret = replmd_delete_remove_link(module, schema,
								replmd_private,
								old_dn, &guid,
								el, sa, req,
								&caller_should_vanish);
				if (ret != LDB_SUCCESS) {
					const char *old_dn_str
						= ldb_dn_get_linearized(old_dn);
					ldb_asprintf_errstring(ldb,
							       __location__
							       ": Failed to remove backlink of "
							       "%s when deleting %s: %s",
							       el->name,
							       old_dn_str,
							       ldb_errstring(ldb));
					talloc_free(tmp_ctx);
					return LDB_ERR_OPERATIONS_ERROR;
				}

				if (caller_should_vanish == false) {
					/*
					 * now we continue, which means we
					 * won't remove this backlink
					 * directly
					 */
					continue;
				}

				/*
				 * Otherwise vanish the link, we are
				 * out of sync and the controlling
				 * object does not have the source
				 * link any more
				 */

				dsdb_flags |= DSDB_REPLMD_VANISH_LINKS;

			} else if (sa->linkID == 0) {
				const char * const *attr = NULL;
				if (sa->searchFlags & SEARCH_FLAG_PRESERVEONDELETE) {
					continue;
				}
				BINARY_ARRAY_SEARCH_V(preserved_attrs,
						      ARRAY_SIZE(preserved_attrs),
						      el->name,
						      ldb_attr_cmp,
						      attr);
				/*
				 * If we are preserving, do not do the
				 * ldb_msg_add_empty() below, continue
				 * to the next element
				 */
				if (attr != NULL) {
					continue;
				}
			} else {
				/*
				 * Ensure that we tell the modification to vanish any linked
				 * attributes (not simply mark them as isDeleted = TRUE)
				 */
				dsdb_flags |= DSDB_REPLMD_VANISH_LINKS;
			}
			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;
			}
		}

		break;

	case OBJECT_DELETED:
		/*
		 * MS-ADTS 3.1.1.5.5.1.2 Deleted-Object Requirements
		 * describes what must be removed from a deleted
		 * object
		 */

		ret = ldb_msg_add_empty(msg, "objectCategory", LDB_FLAG_MOD_REPLACE, NULL);
		if (ret != LDB_SUCCESS) {
			talloc_free(tmp_ctx);
			ldb_module_oom(module);
			return ret;
		}

		ret = ldb_msg_add_empty(msg, "sAMAccountType", LDB_FLAG_MOD_REPLACE, NULL);
		if (ret != LDB_SUCCESS) {
			talloc_free(tmp_ctx);
			ldb_module_oom(module);
			return ret;
		}

		break;

	default:
		break;
	}

	if (deletion_state == OBJECT_NOT_DELETED) {
		const struct dsdb_attribute *sa;

		/* 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);
		if (new_rdn_value == NULL) {
			talloc_free(tmp_ctx);
			return ldb_operr(ldb);
		}

		sa = dsdb_attribute_by_lDAPDisplayName(schema, rdn_name);
		if (!sa) {
			talloc_free(tmp_ctx);
			return LDB_ERR_OPERATIONS_ERROR;
		}

		ret = ldb_msg_add_value(msg, sa->lDAPDisplayName, 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;
		}
	}

	/*
	 * TODO: Per MS-DRSR 5.160 RemoveObj we should remove links directly, not as an originating update!
	 *
	 */

	/*
	 * No matter what has happned with other renames, try again to
	 * get this to be under the deleted DN.
	 */
	if (strcmp(ldb_dn_get_linearized(old_dn), ldb_dn_get_linearized(new_dn)) != 0) {
		/* now rename onto the new DN */
		ret = dsdb_module_rename(module, old_dn, new_dn, DSDB_FLAG_NEXT_MODULE, req);
		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;
		}
		msg->dn = new_dn;
	}

	ret = dsdb_module_modify(module, msg, dsdb_flags|DSDB_FLAG_OWN_MODULE, req);
	if (ret != LDB_SUCCESS) {
		char *s = NULL;
		/*
		 * This should not fail, so be quite verbose in the
		 * error handling if it fails
		 */
		if (strcmp(ldb_dn_get_linearized(old_dn),
			   ldb_dn_get_linearized(new_dn)) != 0) {
			DBG_NOTICE("Failure to handle '%s' of object %s "
				   "after successful rename to %s.  "
				   "Error during tombstone modificaton was: %s\n",
				   re_delete ? "re-delete" : "delete",
				   ldb_dn_get_linearized(new_dn),
				   ldb_dn_get_linearized(old_dn),
				   ldb_errstring(ldb));
		} else {
			DBG_NOTICE("Failure to handle '%s' of object %s. "
				   "Error during tombstone modificaton was: %s\n",
				   re_delete ? "re-delete" : "delete",
				   ldb_dn_get_linearized(new_dn),
				   ldb_errstring(ldb));
		}
		s = ldb_ldif_message_redacted_string(ldb_module_get_ctx(module),
						     tmp_ctx,
						     LDB_CHANGETYPE_MODIFY,
						     msg);

		DBG_INFO("Failed tombstone modify%s was:\n%s\n",
			 (dsdb_flags & DSDB_REPLMD_VANISH_LINKS) ?
			 " with VANISH_LINKS" : "",
			 s);
		ldb_asprintf_errstring(ldb,
				       "replmd_delete: Failed to modify"
				       " object %s in '%s' - %s",
				       ldb_dn_get_linearized(old_dn),
				       re_delete ? "re-delete" : "delete",
				       ldb_errstring(ldb));
		talloc_free(tmp_ctx);
		return ret;
	}

	talloc_free(tmp_ctx);

	return ldb_module_done(req, NULL, NULL, LDB_SUCCESS);
}