dsdb: Rework subtree_rename module to use recursive LDB_SCOPE_ONELEVEL searches

This should be more efficient, particularly in the leaf node case when renaming and
deleting entries on large databases.

Andrew Bartlett

Signed-off-by: Andrew Bartlett <abartlet@samba.org>
Reviewed-by: Stefan Metzmacher <metze@samba.org>

2 files changed, 99 insertions, 104 deletions

diff --git a/source4/dsdb/samdb/ldb_modules/subtree_rename.c b/source4/dsdb/samdb/ldb_modules/subtree_rename.c
index ee787d19e4..d26dabe199 100644
--- a/source4/dsdb/samdb/ldb_modules/subtree_rename.c
+++ b/source4/dsdb/samdb/ldb_modules/subtree_rename.c
@@ -34,19 +34,11 @@
 #include <ldb_module.h>
 #include "libds/common/flags.h"
 #include "dsdb/samdb/samdb.h"
-
-struct subren_msg_store {
-	struct subren_msg_store *next;
-	struct ldb_dn *olddn;
-	struct ldb_dn *newdn;
-};
+#include "dsdb/samdb/ldb_modules/util.h"
 
 struct subtree_rename_context {
 	struct ldb_module *module;
 	struct ldb_request *req;
-
-	struct subren_msg_store *list;
-	struct subren_msg_store *current;
 };
 
 static struct subtree_rename_context *subren_ctx_init(struct ldb_module *module,
@@ -66,14 +58,11 @@ static struct subtree_rename_context *subren_ctx_init(struct ldb_module *module,
 	return ac;
 }
 
-static int subtree_rename_next_request(struct subtree_rename_context *ac);
-
 static int subtree_rename_callback(struct ldb_request *req,
 				   struct ldb_reply *ares)
 {
 	struct ldb_context *ldb;
 	struct subtree_rename_context *ac;
-	int ret;
 
 	ac = talloc_get_type(req->context, struct subtree_rename_context);
 	ldb = ldb_module_get_ctx(ac->module);
@@ -98,47 +87,8 @@ static int subtree_rename_callback(struct ldb_request *req,
 					LDB_ERR_OPERATIONS_ERROR);
 	}
 
-	if (ac->current == NULL) {
-		/* this was the last one */
-		return ldb_module_done(ac->req, ares->controls,
-					ares->response, LDB_SUCCESS);
-	}
-
-	ret = subtree_rename_next_request(ac);
-	if (ret != LDB_SUCCESS) {
-		return ldb_module_done(ac->req, NULL, NULL, ret);
-	}
-
 	talloc_free(ares);
-	return LDB_SUCCESS;
-}
-
-static int subtree_rename_next_request(struct subtree_rename_context *ac)
-{
-	struct ldb_context *ldb;
-	struct ldb_request *req;
-	int ret;
-
-	ldb = ldb_module_get_ctx(ac->module);
-
-	if (ac->current == NULL) {
-		return ldb_operr(ldb);
-	}
-
-	ret = ldb_build_rename_req(&req, ldb, ac->current,
-				   ac->current->olddn,
-				   ac->current->newdn,
-				   ac->req->controls,
-				   ac, subtree_rename_callback,
-				   ac->req);
-	LDB_REQ_SET_LOCATION(req);
-	if (ret != LDB_SUCCESS) {
-		return ret;
-	}
-
-	ac->current = ac->current->next;
-
-	return ldb_next_request(ac->module, req);
+	return ldb_module_done(ac->req, NULL, NULL, LDB_SUCCESS);
 }
 
 static int check_constraints(struct ldb_message *msg,
@@ -297,16 +247,15 @@ static int check_constraints(struct ldb_message *msg,
 	return LDB_SUCCESS;
 }
 
-static int subtree_rename_search_callback(struct ldb_request *req,
-					  struct ldb_reply *ares)
+static int subtree_rename_search_onelevel_callback(struct ldb_request *req,
+						   struct ldb_reply *ares)
 {
-	struct subren_msg_store *store;
 	struct subtree_rename_context *ac;
 	int ret;
 
 	ac = talloc_get_type(req->context, struct subtree_rename_context);
 
-	if (!ares || !ac->current) {
+	if (!ares) {
 		return ldb_module_done(ac->req, NULL, NULL,
 					LDB_ERR_OPERATIONS_ERROR);
 	}
@@ -317,46 +266,89 @@ static int subtree_rename_search_callback(struct ldb_request *req,
 
 	switch (ares->type) {
 	case LDB_REPLY_ENTRY:
-		if (ldb_dn_compare(ares->message->dn, ac->list->olddn) == 0) {
-			/*
-			 * This is the root entry of the originating move
-			 * respectively rename request. It has been already
-			 * stored in the list using "subtree_rename_search()".
-			 * Only this one is subject to constraint checking.
-			 */
-			ret = check_constraints(ares->message, ac,
-						ac->list->olddn,
-						ac->list->newdn);
-			if (ret != LDB_SUCCESS) {
-				return ldb_module_done(ac->req, NULL, NULL,
-						       ret);
-			}
-
-			talloc_free(ares);
-			return LDB_SUCCESS;
+	{
+		struct ldb_dn *old_dn = ares->message->dn;
+		struct ldb_dn *new_dn = ldb_dn_copy(ares, old_dn);
+		if (!new_dn) {
+			return ldb_module_oom(ac->module);
 		}
 
-		store = talloc_zero(ac, struct subren_msg_store);
-		if (store == NULL) {
+		if ( ! ldb_dn_remove_base_components(new_dn,
+				ldb_dn_get_comp_num(ac->req->op.rename.olddn))) {
 			return ldb_module_done(ac->req, NULL, NULL,
 						LDB_ERR_OPERATIONS_ERROR);
 		}
-		ac->current->next = store;
-		ac->current = store;
-
-		/* the first list element contains the base for the rename */
-		store->olddn = talloc_steal(store, ares->message->dn);
-		store->newdn = ldb_dn_copy(store, store->olddn);
 
-		if ( ! ldb_dn_remove_base_components(store->newdn,
-				ldb_dn_get_comp_num(ac->list->olddn))) {
+		if ( ! ldb_dn_add_base(new_dn, ac->req->op.rename.newdn)) {
 			return ldb_module_done(ac->req, NULL, NULL,
 						LDB_ERR_OPERATIONS_ERROR);
 		}
+		ret = dsdb_module_rename(ac->module, old_dn, new_dn, DSDB_FLAG_OWN_MODULE, req);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+
+		talloc_free(ares);
 
-		if ( ! ldb_dn_add_base(store->newdn, ac->list->newdn)) {
+		return LDB_SUCCESS;
+	}
+	case LDB_REPLY_REFERRAL:
+		/* ignore */
+		break;
+
+	case LDB_REPLY_DONE:
+
+		ret = ldb_build_rename_req(&req, ldb_module_get_ctx(ac->module), ac,
+					   ac->req->op.rename.olddn,
+					   ac->req->op.rename.newdn,
+					   ac->req->controls,
+					   ac, subtree_rename_callback,
+					   ac->req);
+		LDB_REQ_SET_LOCATION(req);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+
+		talloc_free(ares);
+		return ldb_next_request(ac->module, req);
+	}
+
+	return LDB_SUCCESS;
+}
+
+static int subtree_rename_search_base_callback(struct ldb_request *req,
+					       struct ldb_reply *ares)
+{
+	struct ldb_request *search_req;
+	struct subtree_rename_context *ac;
+	static const char * const no_attrs[] = {NULL};
+	int ret;
+
+	ac = talloc_get_type(req->context, struct subtree_rename_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);
+	}
+
+	switch (ares->type) {
+	case LDB_REPLY_ENTRY:
+		/*
+		 * This is the root entry of the originating move
+		 * respectively rename request. It has been already
+		 * stored in the list using "subtree_rename_search()".
+		 * Only this one is subject to constraint checking.
+		 */
+		ret = check_constraints(ares->message, ac,
+					ac->req->op.rename.olddn,
+					ac->req->op.rename.newdn);
+		if (ret != LDB_SUCCESS) {
 			return ldb_module_done(ac->req, NULL, NULL,
-						LDB_ERR_OPERATIONS_ERROR);
+					       ret);
 		}
 		break;
 
@@ -366,16 +358,28 @@ static int subtree_rename_search_callback(struct ldb_request *req,
 
 	case LDB_REPLY_DONE:
 
-		/* rewind ac->current */
-		ac->current = ac->list;
-
-		/* All dns set up, start with the first one */
-		ret = subtree_rename_next_request(ac);
+		ret = ldb_build_search_req(&search_req, ldb_module_get_ctx(ac->module), ac,
+					   ac->req->op.rename.olddn,
+					   LDB_SCOPE_ONELEVEL,
+					   "(objectClass=*)",
+					   no_attrs,
+					   NULL,
+					   ac,
+					   subtree_rename_search_onelevel_callback,
+					   req);
+		LDB_REQ_SET_LOCATION(search_req);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
 
+		ret = ldb_request_add_control(search_req, LDB_CONTROL_SHOW_RECYCLED_OID,
+					      true, NULL);
 		if (ret != LDB_SUCCESS) {
-			return ldb_module_done(ac->req, NULL, NULL, ret);
+			return ret;
 		}
-		break;
+
+		talloc_free(ares);
+		return ldb_next_request(ac->module, search_req);
 	}
 
 	talloc_free(ares);
@@ -412,23 +416,14 @@ static int subtree_rename(struct ldb_module *module, struct ldb_request *req)
 		return ldb_oom(ldb);
 	}
 
-	/* add this entry as the first to do */
-	ac->current = talloc_zero(ac, struct subren_msg_store);
-	if (ac->current == NULL) {
-		return ldb_oom(ldb);
-	}
-	ac->current->olddn = req->op.rename.olddn;
-	ac->current->newdn = req->op.rename.newdn;
-	ac->list = ac->current;
-
 	ret = ldb_build_search_req(&search_req, ldb, ac,
 				   req->op.rename.olddn, 
-				   LDB_SCOPE_SUBTREE,
+				   LDB_SCOPE_BASE,
 				   "(objectClass=*)",
 				   attrs,
 				   NULL,
 				   ac, 
-				   subtree_rename_search_callback,
+				   subtree_rename_search_base_callback,
 				   req);
 	LDB_REQ_SET_LOCATION(search_req);
 	if (ret != LDB_SUCCESS) {
diff --git a/source4/dsdb/samdb/ldb_modules/wscript_build_server b/source4/dsdb/samdb/ldb_modules/wscript_build_server
index c23ad16b89..41eb0f34e1 100755
--- a/source4/dsdb/samdb/ldb_modules/wscript_build_server
+++ b/source4/dsdb/samdb/ldb_modules/wscript_build_server
@@ -235,7 +235,7 @@ bld.SAMBA_MODULE('ldb_subtree_rename',
 	init_function='ldb_subtree_rename_module_init',
 	module_init_name='ldb_init_module',
 	internal_module=False,
-	deps='talloc samba-util ldb samdb-common'
+	deps='talloc samba-util ldb samdb-common DSDB_MODULE_HELPERS'
 	)