r12600: Add a new module to sort the objectclass attribute on store. The

module is perhaps not the most efficient, but I think it is
reasonable.

This should restore operation of MMC against Samba4 (broken by the
templating fixes).

Andrew Bartlett
(This used to be commit 41948c4bdbfca1160a01a92994324f9e22422afe)

5 files changed, 327 insertions, 2 deletions

diff --git a/source4/lib/ldb/common/ldb_modules.c b/source4/lib/ldb/common/ldb_modules.c
index 8076dbfdf9..5c2e36d431 100644
--- a/source4/lib/ldb/common/ldb_modules.c
+++ b/source4/lib/ldb/common/ldb_modules.c
@@ -130,6 +130,7 @@ int ldb_load_modules(struct ldb_context *ldb, const char *options[])
 		{ "schema", schema_module_init },
 		{ "operational", operational_module_init },
 		{ "rdn_name", rdn_name_module_init },
+		{ "objectclass", objectclass_module_init },
 #ifdef _SAMBA_BUILD_
 		{ "objectguid", objectguid_module_init },
 		{ "samldb", samldb_module_init },
diff --git a/source4/lib/ldb/config.mk b/source4/lib/ldb/config.mk
index 2ce0d5043d..9cb74f551b 100644
--- a/source4/lib/ldb/config.mk
+++ b/source4/lib/ldb/config.mk
@@ -8,6 +8,15 @@ OBJ_FILES = \
 ################################################
 
 ################################################
+# Start MODULE libldb_objectclass
+[MODULE::libldb_objectclass]
+SUBSYSTEM = LIBLDB
+OBJ_FILES = \
+		modules/objectclass.o
+# End MODULE libldb_objectclass
+################################################
+
+################################################
 # Start MODULE libldb_rdn_name
 [MODULE::libldb_rdn_name]
 SUBSYSTEM = LIBLDB
diff --git a/source4/lib/ldb/include/dlinklist.h b/source4/lib/ldb/include/dlinklist.h
index 40f7f0a0c7..a39007375f 100644
--- a/source4/lib/ldb/include/dlinklist.h
+++ b/source4/lib/ldb/include/dlinklist.h
@@ -88,6 +88,8 @@ do { \
 			type tmp; \
 			for (tmp = (list1); tmp->next; tmp = tmp->next) ; \
 			tmp->next = (list2); \
-			(list2)->prev = tmp; \
+			if (list2) { \
+				(list2)->prev = tmp;	\
+			} \
 		} \
 } while (0)
diff --git a/source4/lib/ldb/modules/objectclass.c b/source4/lib/ldb/modules/objectclass.c
new file mode 100644
index 0000000000..b89b70ebf2
--- /dev/null
+++ b/source4/lib/ldb/modules/objectclass.c
@@ -0,0 +1,313 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Bartlett <abartlet@samba.org> 2005
+
+     ** NOTE! The following LGPL license applies to the ldb
+     ** library. This does NOT imply that all of Samba is released
+     ** under the LGPL
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with this library; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: objectClass sorting module
+ *
+ *  Description: sort the objectClass attribute into the class hierarchy
+ *
+ *  Author: Andrew Bartlett
+ */
+
+#include "includes.h"
+#include "ldb/include/ldb.h"
+#include "ldb/include/ldb_private.h"
+#include "ldb/include/ldb_errors.h"
+#include "ldb/include/dlinklist.h"
+
+/* It turns out the MMC assumes that the last objectClass in the list
+ * is the most specific subclass.  As such, we must sort the list,
+ * according to the schema.
+ *
+ * For performance, we do this on the add/modify, not on the search
+ *
+ * We perform the original add/modify, then search for that is now in
+ * the objectClass list. We can then then replace that with the new
+ * sorted list.  The backend is expected to preserve ordering for
+ * subsequent searches.
+ *
+ * We are in a transaction, so this is all perfectly safe...
+ */
+
+static int objectclass_handle(struct ldb_module *module, struct ldb_request *req, const struct ldb_message *msg)
+{
+	TALLOC_CTX *mem_ctx;
+	int ret;
+	struct ldb_request search_request;
+	struct ldb_request modify_request;
+	struct ldb_message *modify_msg;
+	struct ldb_result *res;
+	const char *attrs[] = { "objectClass", NULL };
+	struct class_list {
+		struct class_list *prev, *next;
+		const char *objectclass;
+	};
+	struct class_list *sorted = NULL, *parent_class = NULL, 
+		*subclass = NULL, *unsorted = NULL, *current, *poss_subclass;
+	int i;
+	int layer;
+
+	struct ldb_message_element *objectclass_element;
+
+	ldb_debug(module->ldb, LDB_DEBUG_TRACE, "objectclass_handle\n");
+
+	if (ldb_dn_is_special(msg->dn)) { /* do not manipulate our control entries */
+		return ldb_next_request(module, req);
+	}
+
+	ret = ldb_next_request(module, req);
+
+	if (ret) {
+		return ret;
+	}
+
+	if (ldb_msg_find_element(msg, "objectClass") == NULL ) {
+		/* No sign of the objectClass:  no change, nothing to see here */
+		return ret;
+	}
+
+	/* Thanks to transactions: Now do a search, find the full list
+	 * of objectClasses and do the sort */
+
+	search_request.operation       = LDB_REQ_SEARCH;
+	search_request.op.search.base  = msg->dn;
+	search_request.op.search.scope = LDB_SCOPE_BASE;
+	search_request.op.search.tree  = ldb_parse_tree(module->ldb, NULL);
+	search_request.op.search.attrs = attrs;
+
+	ret = ldb_next_request(module, &search_request);
+	if (ret) {
+		return ret;
+	}
+
+	mem_ctx = talloc_new(module);
+	if (!mem_ctx) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	res = search_request.op.search.res;
+	talloc_steal(mem_ctx, res);
+	if (res->count != 1) {
+		ldb_set_errstring(module, 
+				  talloc_asprintf(mem_ctx, "objectClass_handle: "
+						  "search for %s found %d != 1 objects, for entry we just added/modified",
+						  ldb_dn_linearize(mem_ctx, msg->dn),
+						  res->count));
+		/* What happened?  The above add/modify worked... */
+		talloc_free(mem_ctx);
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	/* This is now the objectClass list from the database */
+	objectclass_element = ldb_msg_find_element(res->msgs[0], "objectClass");
+	if (!objectclass_element) {
+		/* Perhaps the above was a remove?  Move along now, nothing to see here */
+		talloc_free(mem_ctx);
+		return LDB_SUCCESS;
+	}
+	
+	/* DESIGN:
+	 *
+	 * We work on 4 different 'bins' (implemented here as linked lists):
+	 *
+	 * * sorted:       the eventual list, in the order we wish to push
+	 *                 into the database.  This is the only ordered list.
+	 *
+	 * * parent_class: The current parent class 'bin' we are
+	 *                 trying to find subclasses for
+	 *
+	 * * subclass:     The subclasses we have found so far
+	 *
+	 * * unsorted:     The remaining objectClasses
+	 *
+	 * The process is a matter of filtering objectClasses up from
+	 * unsorted into sorted.  Order is irrelevent in the later 3 'bins'.
+	 * 
+	 * We start with 'top' (found and promoted to parent_class
+	 * initially).  Then we find (in unsorted) all the direct
+	 * subclasses of 'top'.  parent_classes is concatenated onto
+	 * the end of 'sorted', and subclass becomes the list in
+	 * parent_class.
+	 *
+	 * We then repeat, until we find no more subclasses.  Any left
+	 * over classes are added to the end.
+	 *
+	 */
+
+	/* Firstly, dump all the objectClass elements into the
+	 * unsorted bin, except for 'top', which is special */
+	for (i=0; i < objectclass_element->num_values; i++) {
+		current = talloc(mem_ctx, struct class_list);
+		if (!current) {
+			talloc_free(mem_ctx);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		current->objectclass = (const char *)objectclass_element->values[i].data;
+
+		/* this is the root of the tree.  We will start
+		 * looking for subclasses from here */
+		if (ldb_attr_cmp("top", current->objectclass) == 0) {
+			DLIST_ADD(parent_class, current);
+		} else {
+			DLIST_ADD(unsorted, current);
+		}
+	}
+
+	/* DEBUGGING aid:  how many layers are we down now? */
+	layer = 0;
+	do {
+		layer++;
+		/* Find all the subclasses of classes in the
+		 * parent_classes.  Push them onto the subclass list */
+
+		/* Ensure we don't bother if there are no unsorted entries left */
+		for (current = parent_class; unsorted && current; current = current->next) {
+			const char **subclasses = ldb_subclass_list(module->ldb, current->objectclass);
+
+			/* Walk the list of possible subclasses in unsorted */
+			for (poss_subclass = unsorted; poss_subclass; ) {
+				struct class_list *next;
+				
+				/* Save the next pointer, as the DLIST_ macros will change poss_subclass->next */
+				next = poss_subclass->next;
+
+				for (i = 0; subclasses && subclasses[i]; i++) {
+					if (ldb_attr_cmp(poss_subclass->objectclass, subclasses[i]) == 0) {
+						DLIST_REMOVE(unsorted, poss_subclass);
+						DLIST_ADD(subclass, poss_subclass);
+
+						break;
+					}
+				}
+				poss_subclass = next;
+			}
+		}
+
+		/* Now push the parent_classes as sorted, we are done with
+		these.  Add to the END of the list by concatenation */
+		DLIST_CONCATENATE(sorted, parent_class, struct class_list *);
+
+		/* and now find subclasses of these */
+		parent_class = subclass;
+		subclass = NULL;
+
+		/* If we didn't find any subclasses we will fall out
+		 * the bottom here */
+	} while (parent_class);
+
+	/* This shouldn't happen, and would break MMC, but we can't
+	 * afford to loose objectClasses.  Perhaps there was no 'top',
+	 * or some other schema error? 
+	 *
+	 * Detecting schema errors is the job of the schema module, so
+	 * at this layer we just try not to loose data
+ 	 */
+	DLIST_CONCATENATE(sorted, unsorted, struct class_list *);
+
+	modify_msg = ldb_msg_new(mem_ctx);
+	if (!modify_msg) {
+		talloc_free(mem_ctx);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	modify_msg->dn = talloc_reference(modify_msg, msg->dn);
+
+	/* We must completely replace the existing objectClass entry.
+	 * We could do a constrained add/del, but we are meant to be
+	 * in a transaction... */
+
+	ret = ldb_msg_add_empty(modify_msg, "objectClass", LDB_FLAG_MOD_REPLACE);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(mem_ctx);
+		return ret;
+	}
+	
+	/* Move from the linked list back into an ldb msg */
+	for (current = sorted; current; current = current->next) {
+		ret = ldb_msg_add_string(modify_msg, "objectClass", current->objectclass);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(mem_ctx);
+			return ret;
+		}
+	}
+
+	ret = ldb_msg_sanity_check(modify_msg);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(mem_ctx);
+		return ret;
+	}
+
+	modify_request.operation = LDB_REQ_MODIFY;
+	modify_request.op.mod.message = modify_msg;
+
+	/* And now push the write into the database */
+	ret = ldb_next_request(module, &modify_request);
+	
+	talloc_free(mem_ctx);
+	return ret;
+}
+
+static int objectclass_request(struct ldb_module *module, struct ldb_request *req)
+{
+	switch (req->operation) {
+
+		/* only care about add and modify requests */
+	case LDB_REQ_ADD:
+		return objectclass_handle(module, req, req->op.add.message);
+
+	case LDB_REQ_MODIFY:
+		return objectclass_handle(module, req, req->op.mod.message);
+
+	default:
+		return ldb_next_request(module, req);
+
+	}
+}
+
+static const struct ldb_module_ops objectclass_ops = {
+	.name		   = "objectclass",
+	.request      	   = objectclass_request,
+};
+
+#ifdef HAVE_DLOPEN_DISABLED
+struct ldb_module *init_module(struct ldb_context *ldb, const char *options[])
+#else
+struct ldb_module *objectclass_module_init(struct ldb_context *ldb, const char *options[])
+#endif
+{
+	struct ldb_module *ctx;
+
+	ctx = talloc(ldb, struct ldb_module);
+	if (!ctx)
+		return NULL;
+
+	ctx->private_data = NULL;
+
+	ctx->ldb = ldb;
+	ctx->prev = ctx->next = NULL;
+	ctx->ops = &objectclass_ops;
+
+	return ctx;
+}
diff --git a/source4/setup/provision_init.ldif b/source4/setup/provision_init.ldif
index e4c2476992..ff6b1def19 100644
--- a/source4/setup/provision_init.ldif
+++ b/source4/setup/provision_init.ldif
@@ -70,5 +70,5 @@ isSynchronized: TRUE
 #Add modules to the list to activate them by default
 #beware often order is important
 dn: @MODULES
-@LIST: rootdse,samldb,password_hash,operational,objectguid,rdn_name
+@LIST: rootdse,samldb,password_hash,operational,objectguid,rdn_name,objectclass