r12733: Merge ldap/ldb controls into main tree

There's still lot of work to do but the patch is stable
enough to be pushed into the main samba4 tree.

Simo.
(This used to be commit 77125feaff252cab44d26593093a9c211c846ce8)

31 files changed, 880 insertions, 38 deletions

diff --git a/source4/lib/ldb/Makefile.in b/source4/lib/ldb/Makefile.in
index 5a6155edd0..bde2388b82 100644
--- a/source4/lib/ldb/Makefile.in
+++ b/source4/lib/ldb/Makefile.in
@@ -57,10 +57,11 @@ COMMON_OBJ=common/ldb.o common/ldb_ldif.o \
 	   common/ldb_parse.o common/ldb_msg.o common/ldb_utf8.o \
 	   common/ldb_debug.o common/ldb_modules.o \
 	   common/ldb_dn.o common/ldb_match.o common/ldb_attributes.o \
-	   common/attrib_handlers.o
+	   common/attrib_handlers.o common/ldb_controls.o common/qsort.o
 
 MODULES_OBJ=modules/operational.o modules/schema.o modules/rdn_name.o \
-	   modules/objectclass.o modules/ldb_map.o	 
+	   modules/objectclass.o modules/ldb_map.o \
+	   modules/paged_results.o modules/sort.o
 
 OBJS =  $(MODULES_OBJ) $(COMMON_OBJ) $(LDB_TDB_OBJ) $(TDB_OBJ) $(TALLOC_OBJ) $(LDB_LDAP_OBJ) $(LDB_SQLITE3_OBJ)
 
diff --git a/source4/lib/ldb/common/ldb.c b/source4/lib/ldb/common/ldb.c
index 6095f4fc04..604f02a1f7 100644
--- a/source4/lib/ldb/common/ldb.c
+++ b/source4/lib/ldb/common/ldb.c
@@ -307,6 +307,7 @@ int ldb_search(struct ldb_context *ldb,
 	request.op.search.scope = scope;
 	request.op.search.tree = tree;
 	request.op.search.attrs = attrs;
+	request.controls = NULL;
 
 	ret = ldb_request(ldb, &request);
 
@@ -332,6 +333,7 @@ int ldb_add(struct ldb_context *ldb,
 
 	request.operation = LDB_REQ_ADD;
 	request.op.add.message = message;
+	request.controls = NULL;
 
 	return ldb_request(ldb, &request);
 }
@@ -350,6 +352,7 @@ int ldb_modify(struct ldb_context *ldb,
 
 	request.operation = LDB_REQ_MODIFY;
 	request.op.mod.message = message;
+	request.controls = NULL;
 
 	return ldb_request(ldb, &request);
 }
@@ -364,6 +367,7 @@ int ldb_delete(struct ldb_context *ldb, const struct ldb_dn *dn)
 
 	request.operation = LDB_REQ_DELETE;
 	request.op.del.dn = dn;
+	request.controls = NULL;
 
 	return ldb_request(ldb, &request);
 }
@@ -378,6 +382,7 @@ int ldb_rename(struct ldb_context *ldb, const struct ldb_dn *olddn, const struct
 	request.operation = LDB_REQ_RENAME;
 	request.op.rename.olddn = olddn;
 	request.op.rename.newdn = newdn;
+	request.controls = NULL;
 
 	return ldb_request(ldb, &request);
 }
diff --git a/source4/lib/ldb/common/ldb_controls.c b/source4/lib/ldb/common/ldb_controls.c
new file mode 100644
index 0000000000..e4c4c64a6f
--- /dev/null
+++ b/source4/lib/ldb/common/ldb_controls.c
@@ -0,0 +1,108 @@
+/* 
+   ldb database library
+
+   Copyright (C) Simo Sorce  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_controls.c
+ *
+ *  Component: ldb controls utility functions
+ *
+ *  Description: helper functions for control modules
+ *
+ *  Author: Simo Sorce
+ */
+
+#include "includes.h"
+#include "ldb/include/ldb.h"
+#include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
+
+/* check if a control with the specified "oid" exist and return it */
+/* returns NULL if not found */
+struct ldb_control *get_control_from_list(struct ldb_control **controls, const char *oid)
+{
+	int i;
+
+	/* check if there's a paged request control */
+	if (controls != NULL) {
+		for (i = 0; controls[i]; i++) {
+			if (strcmp(oid, controls[i]->oid) == 0) {
+				break;
+			}
+		}
+
+		return controls[i];
+	}
+
+	return NULL;
+}
+
+/* saves the current controls list into the "saver" and replace the one in req with a new one excluding
+the "exclude" control */
+/* returns False on error */
+int save_controls(struct ldb_control *exclude, struct ldb_request *req, struct ldb_control ***saver)
+{
+	struct ldb_control **lcs;
+	int i, j;
+
+	*saver = req->controls;
+	for (i = 0; req->controls[i]; i++);
+	if (i == 1) {
+		req->controls = NULL;
+		return 1;
+	}
+
+	lcs = talloc_array(req, struct ldb_control *, i);
+	if (!lcs) {
+		return 0;
+	}
+
+	for (i = 0, j = 0; (*saver)[i]; i++) {
+		if (exclude == (*saver)[i]) continue;
+		lcs[j] = (*saver)[i];
+		j++;
+	}
+	lcs[j] = NULL;
+
+	req->controls = lcs;
+	return 1;
+}
+
+/* check if there's any control marked as critical in the list */
+/* return True if any, False if none */
+int check_critical_controls(struct ldb_control **controls)
+{
+	int i;
+
+	if (controls == NULL) {
+		return 0;
+	}
+
+	for (i = 0; controls[i]; i++) {
+		if (controls[i]->critical) {
+			return 1;
+		}
+	}
+
+	return 0;
+}
diff --git a/source4/lib/ldb/common/ldb_dn.c b/source4/lib/ldb/common/ldb_dn.c
index 4ae00ee6dc..5ed54ae316 100644
--- a/source4/lib/ldb/common/ldb_dn.c
+++ b/source4/lib/ldb/common/ldb_dn.c
@@ -417,6 +417,39 @@ failed:
 	return NULL;
 }
 
+struct ldb_dn *ldb_dn_explode_or_special(void *mem_ctx, const char *dn)
+{
+	struct ldb_dn *edn; /* the exploded dn */
+
+	if (dn == NULL) return NULL;
+
+	if (strncasecmp(dn, "<GUID=", 6) == 0) {
+		/* this is special DN returned when the
+		 * exploded_dn control is used
+		 */
+
+		/* Allocate a structure to hold the exploded DN */
+		edn = ldb_dn_new(mem_ctx);
+
+		edn->comp_num = 1;
+		edn->components = talloc(edn, struct ldb_dn_component);
+		if (edn->components == NULL) goto failed;
+		edn->components[0].name = talloc_strdup(edn->components, LDB_SPECIAL);
+		if (edn->components[0].name == NULL) goto failed;
+		edn->components[0].value.data = (uint8_t *)talloc_strdup(edn->components, dn);
+		if (edn->components[0].value.data== NULL) goto failed;
+		edn->components[0].value.length = strlen(dn);
+		return edn;
+
+	}
+	
+	return ldb_dn_explode(mem_ctx, dn);
+
+failed:
+	talloc_free(edn);
+	return NULL;
+}
+
 char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn)
 {
 	char *dn, *value;
diff --git a/source4/lib/ldb/common/ldb_modules.c b/source4/lib/ldb/common/ldb_modules.c
index 5c2e36d431..26a397dccc 100644
--- a/source4/lib/ldb/common/ldb_modules.c
+++ b/source4/lib/ldb/common/ldb_modules.c
@@ -131,12 +131,15 @@ int ldb_load_modules(struct ldb_context *ldb, const char *options[])
 		{ "operational", operational_module_init },
 		{ "rdn_name", rdn_name_module_init },
 		{ "objectclass", objectclass_module_init },
+		{ "paged_results", paged_results_module_init },
+		{ "server_sort", server_sort_module_init },
 #ifdef _SAMBA_BUILD_
 		{ "objectguid", objectguid_module_init },
 		{ "samldb", samldb_module_init },
 		{ "samba3sam", ldb_samba3sam_module_init },
 		{ "proxy", proxy_module_init },
 		{ "rootdse", rootdse_module_init },
+		{ "extended_dn", extended_dn_module_init },
 		{ "password_hash", password_hash_module_init },
 #endif
 		{ NULL, NULL }
@@ -198,7 +201,7 @@ int ldb_load_modules(struct ldb_context *ldb, const char *options[])
 		int m;
 		for (m=0;well_known_modules[m].name;m++) {
 			if (strcmp(modules[i], well_known_modules[m].name) == 0) {
-				current = well_known_modules[m].init(ldb, options);
+				current = well_known_modules[m].init(ldb, LDB_MODULES_INIT_STAGE_1, options);
 				if (current == NULL) {
 					ldb_debug(ldb, LDB_DEBUG_FATAL, "function 'init_module' in %s fails\n", modules[i]);
 					return -1;
@@ -213,6 +216,17 @@ int ldb_load_modules(struct ldb_context *ldb, const char *options[])
 		}
 	}
 
+	/* second stage init */
+	for (i = 0; modules[i] != NULL; i++) {
+		int m;
+		for (m = 0; well_known_modules[m].name; m++) {
+			if (strcmp(modules[i], well_known_modules[m].name) == 0) {
+				well_known_modules[m].init(ldb, LDB_MODULES_INIT_STAGE_2, options);
+				break;
+			}
+		}
+	}
+
 	talloc_free(modules);
 	return 0; 
 }
diff --git a/source4/lib/ldb/config.mk b/source4/lib/ldb/config.mk
index 13280bac68..cbd91a6de6 100644
--- a/source4/lib/ldb/config.mk
+++ b/source4/lib/ldb/config.mk
@@ -1,4 +1,24 @@
 ################################################
+# Start MODULE libldb_sort
+[MODULE::libldb_sort]
+SUBSYSTEM = LIBLDB
+OUTPUT_TYPE = MERGEDOBJ
+OBJ_FILES = \
+		modules/sort.o
+# End MODULE libldb_sort
+################################################
+
+################################################
+# Start MODULE libldb_paged_results
+[MODULE::libldb_paged_results]
+SUBSYSTEM = LIBLDB
+OUTPUT_TYPE = MERGEDOBJ
+OBJ_FILES = \
+		modules/paged_results.o
+# End MODULE libldb_paged_results
+################################################
+
+################################################
 # Start MODULE libldb_operational
 [MODULE::libldb_operational]
 SUBSYSTEM = LIBLDB
@@ -118,7 +138,9 @@ OBJ_FILES = \
 		common/ldb_match.o \
 		common/ldb_attributes.o \
 		common/attrib_handlers.o \
-		common/ldb_dn.o
+		common/ldb_dn.o \
+		common/ldb_controls.o \
+		common/qsort.o
 REQUIRED_SUBSYSTEMS = \
 		LIBREPLACE LIBTALLOC LDBSAMBA
 NOPROTO = YES
diff --git a/source4/lib/ldb/include/ldb.h b/source4/lib/ldb/include/ldb.h
index 9c3b033091..299a5d171e 100644
--- a/source4/lib/ldb/include/ldb.h
+++ b/source4/lib/ldb/include/ldb.h
@@ -141,12 +141,6 @@ struct ldb_context;
 typedef int (*ldb_traverse_fn)(struct ldb_context *, const struct ldb_message *);
 
 
-struct ldb_module;
-
-/* module initialisation function */
-typedef struct ldb_module *(*ldb_module_init_t)(struct ldb_context *, const char **);
-
-
 /* debugging uses one of the following levels */
 enum ldb_debug_level {LDB_DEBUG_FATAL, LDB_DEBUG_ERROR, 
 		      LDB_DEBUG_WARNING, LDB_DEBUG_TRACE};
@@ -253,7 +247,41 @@ struct ldb_attrib_handler {
 #define LDB_SYNTAX_UTC_TIME             "1.3.6.1.4.1.1466.115.121.1.53"
 #define LDB_SYNTAX_OBJECTCLASS          "LDB_SYNTAX_OBJECTCLASS"
 
-struct ldb_controls;
+/* sorting helpers */
+typedef int (*ldb_qsort_cmp_fn_t) (const void *, const void *, const void *);
+
+#define LDB_CONTROL_PAGED_RESULTS_OID	"1.2.840.113556.1.4.319"
+#define LDB_CONTROL_EXTENDED_DN_OID	"1.2.840.113556.1.4.529"
+#define LDB_CONTROL_SERVER_SORT_OID	"1.2.840.113556.1.4.473"
+#define LDB_CONTROL_SORT_RESP_OID	"1.2.840.113556.1.4.474"
+
+struct ldb_paged_control {
+	int size;
+	int cookie_len;
+	char *cookie;
+};
+
+struct ldb_extended_dn_control {
+	int type;
+};
+
+struct ldb_server_sort_control {
+	char *attributeName;
+	char *orderingRule;
+	int reverse;
+};
+
+struct ldb_sort_resp_control {
+	int result;
+	char *attr_desc;
+};
+
+struct ldb_control {
+	const char *oid;
+	int critical;
+	void *data;
+};
+
 struct ldb_credentials;
 
 enum ldb_request_type {
@@ -261,12 +289,14 @@ enum ldb_request_type {
 	LDB_REQ_ADD,
 	LDB_REQ_MODIFY,
 	LDB_REQ_DELETE,
-	LDB_REQ_RENAME
+	LDB_REQ_RENAME,
+	LDB_REQ_REGISTER
 };
 
 struct ldb_result {
 	unsigned int count;
 	struct ldb_message **msgs;
+	struct ldb_control **controls;
 };
 
 struct ldb_search {
@@ -294,6 +324,10 @@ struct ldb_rename {
 	const struct ldb_dn *newdn;
 };
 
+struct ldb_register_control {
+	const char *oid;
+};
+
 struct ldb_request {
 
 	int operation;
@@ -304,9 +338,10 @@ struct ldb_request {
 		struct ldb_modify mod;
 		struct ldb_delete del;
 		struct ldb_rename rename;
+		struct ldb_register_control reg;
 	} op;
 
-	struct ldb_controls *controls;
+	struct ldb_control **controls;
 	struct ldb_credentials *creds;
 }; 
 
@@ -427,6 +462,7 @@ int ldb_dn_check_special(const struct ldb_dn *dn, const char *check);
 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value);
 struct ldb_dn *ldb_dn_new(void *mem_ctx);
 struct ldb_dn *ldb_dn_explode(void *mem_ctx, const char *dn);
+struct ldb_dn *ldb_dn_explode_or_special(void *mem_ctx, const char *dn);
 char *ldb_dn_linearize(void *mem_ctx, const struct ldb_dn *edn);
 char *ldb_dn_linearize_casefold(struct ldb_context *ldb, const struct ldb_dn *edn);
 int ldb_dn_compare_base(struct ldb_context *ldb, const struct ldb_dn *base, const struct ldb_dn *dn);
@@ -565,4 +601,7 @@ time_t ldb_string_to_time(const char *s);
 
 char *ldb_dn_canonical_string(void *mem_ctx, const struct ldb_dn *dn);
 char *ldb_dn_canonical_ex_string(void *mem_ctx, const struct ldb_dn *dn);
+
+
+void ldb_qsort (void *const pbase, size_t total_elems, size_t size, void *opaque, ldb_qsort_cmp_fn_t cmp);
 #endif
diff --git a/source4/lib/ldb/include/ldb_errors.h b/source4/lib/ldb/include/ldb_errors.h
index f59b39f92a..a93d3cd388 100644
--- a/source4/lib/ldb/include/ldb_errors.h
+++ b/source4/lib/ldb/include/ldb_errors.h
@@ -52,7 +52,7 @@
 /* 9 RESERVED */
 #define LDB_ERR_REFERRAL			10
 #define LDB_ERR_ADMIN_LIMIT_EXCEEDED		11
-#define LDB_ERR_UNAVAILABLE_CRITICAL_EXTENSION	12
+#define LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION	12
 #define LDB_ERR_CONFIDENTIALITY_REQUIRED	13
 #define LDB_ERR_SASL_BIND_IN_PROGRESS		14
 #define LDB_ERR_NO_SUCH_ATTRIBUTE		16
diff --git a/source4/lib/ldb/include/ldb_private.h b/source4/lib/ldb/include/ldb_private.h
index d0aec6e137..e8a4d1820a 100644
--- a/source4/lib/ldb/include/ldb_private.h
+++ b/source4/lib/ldb/include/ldb_private.h
@@ -104,7 +104,9 @@ struct ldb_context {
 };
 
 /* the modules init function */
-typedef struct ldb_module *(*ldb_module_init_function)(struct ldb_context *ldb, const char *options[]);
+#define LDB_MODULES_INIT_STAGE_1 1
+#define LDB_MODULES_INIT_STAGE_2 2
+typedef struct ldb_module *(*ldb_module_init_t)(struct ldb_context *, int stage, const char **);
 
 #ifndef ARRAY_SIZE
 #define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
@@ -147,10 +149,12 @@ int lsqlite3_connect(struct ldb_context *ldb,
 		     const char *url, 
 		     unsigned int flags, 
 		     const char *options[]);
-struct ldb_module *operational_module_init(struct ldb_context *ldb, const char *options[]);
-struct ldb_module *schema_module_init(struct ldb_context *ldb, const char *options[]);
-struct ldb_module *rdn_name_module_init(struct ldb_context *ldb, const char *options[]);
-struct ldb_module *objectclass_module_init(struct ldb_context *ldb, const char *options[]);
+struct ldb_module *objectclass_module_init(struct ldb_context *ldb, int stage, const char *options[]);
+struct ldb_module *operational_module_init(struct ldb_context *ldb, int stage, const char *options[]);
+struct ldb_module *paged_results_module_init(struct ldb_context *ldb, int stage, const char *options[]);
+struct ldb_module *rdn_name_module_init(struct ldb_context *ldb, int stage, const char *options[]);
+struct ldb_module *schema_module_init(struct ldb_context *ldb, int stage, const char *options[]);
+struct ldb_module *server_sort_module_init(struct ldb_context *ldb, int stage, const char *options[]);
 
 
 int ldb_match_msg(struct ldb_context *ldb,
@@ -179,4 +183,8 @@ int ldb_handler_copy(struct ldb_context *ldb, void *mem_ctx,
 int ldb_comparison_binary(struct ldb_context *ldb, void *mem_ctx,
 			  const struct ldb_val *v1, const struct ldb_val *v2);
 
+/* The following definitions come from lib/ldb/common/ldb_controls.c  */
+struct ldb_control *get_control_from_list(struct ldb_control **controls, const char *oid);
+int save_controls(struct ldb_control *exclude, struct ldb_request *req, struct ldb_control ***saver);
+int check_critical_controls(struct ldb_control **controls);
 #endif
diff --git a/source4/lib/ldb/ldb_ildap/ldb_ildap.c b/source4/lib/ldb/ldb_ildap/ldb_ildap.c
index 0802469079..ff00a61163 100644
--- a/source4/lib/ldb/ldb_ildap/ldb_ildap.c
+++ b/source4/lib/ldb/ldb_ildap/ldb_ildap.c
@@ -148,11 +148,14 @@ static void ildb_rootdse(struct ldb_module *module);
 */
 static int ildb_search_bytree(struct ldb_module *module, const struct ldb_dn *base,
 			      enum ldb_scope scope, struct ldb_parse_tree *tree,
-			      const char * const *attrs, struct ldb_result **res)
+			      const char * const *attrs,
+			      struct ldb_control **control_req,
+			      struct ldb_result **res)
 {
 	struct ildb_private *ildb = module->private_data;
 	int count, i;
 	struct ldap_message **ldapres, *msg;
+	struct ldap_Control **controls = NULL;
 	char *search_base;
 	NTSTATUS status;
 
@@ -189,9 +192,12 @@ static int ildb_search_bytree(struct ldb_module *module, const struct ldb_dn *ba
 	}
 	(*res)->count = 0;
 	(*res)->msgs = NULL;
+	(*res)->controls = NULL;
 
-	status = ildap_search_bytree(ildb->ldap, search_base, scope, tree, attrs, 
-					    0, &ldapres);
+	status = ildap_search_bytree(ildb->ldap, search_base, scope, tree, attrs, 0,
+				     (struct ldap_Control **)control_req,
+				     &controls,
+				     &ldapres);
 	talloc_free(search_base);
 	if (!NT_STATUS_IS_OK(status)) {
 		ildb_map_error(ildb, status);
@@ -230,7 +236,7 @@ static int ildb_search_bytree(struct ldb_module *module, const struct ldb_dn *ba
 		}
 		(*res)->msgs[i+1] = NULL;
 
-		(*res)->msgs[i]->dn = ldb_dn_explode((*res)->msgs[i], search->dn);
+		(*res)->msgs[i]->dn = ldb_dn_explode_or_special((*res)->msgs[i], search->dn);
 		if ((*res)->msgs[i]->dn == NULL) {
 			goto failed;
 		}
@@ -242,6 +248,11 @@ static int ildb_search_bytree(struct ldb_module *module, const struct ldb_dn *ba
 	talloc_free(ldapres);
 
 	(*res)->count = count;
+
+	if (controls) {
+		(*res)->controls = (struct ldb_control **)talloc_steal(*res, controls);
+	}
+
 	return LDB_SUCCESS;
 
 failed:
@@ -407,6 +418,7 @@ static int ildb_request(struct ldb_module *module, struct ldb_request *req)
 					  req->op.search.scope, 
 					  req->op.search.tree, 
 					  req->op.search.attrs, 
+					  req->controls,
 					  &req->op.search.res);
 
 	case LDB_REQ_ADD:
@@ -449,7 +461,7 @@ static void ildb_rootdse(struct ldb_module *module)
 	int ret;
 	ret = ildb_search_bytree(module, empty_dn, LDB_SCOPE_BASE, 
 				 ldb_parse_tree(empty_dn, "dn=dc=rootDSE"), 
-				 NULL, &res);
+				 NULL, NULL, &res);
 	if (ret == LDB_SUCCESS && res->count == 1) {
 		ildb->rootDSE = talloc_steal(ildb, res->msgs[0]);
 	}
diff --git a/source4/lib/ldb/ldb_ldap/ldb_ldap.c b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
index 893ad0dd2a..8207b5f592 100644
--- a/source4/lib/ldb/ldb_ldap/ldb_ldap.c
+++ b/source4/lib/ldb/ldb_ldap/ldb_ldap.c
@@ -219,6 +219,7 @@ static int lldb_search_bytree(struct ldb_module *module, const struct ldb_dn *ba
 	}
 	(*res)->count = 0;
 	(*res)->msgs = NULL;
+	(*res)->controls = NULL;
 
 	lldb->last_rc = ldap_search_s(lldb->ldap, search_base, ldap_scope, 
 				      expression, 
@@ -272,7 +273,7 @@ static int lldb_search_bytree(struct ldb_module *module, const struct ldb_dn *ba
 			goto failed;
 		}
 
-		(*res)->msgs[msg_count]->dn = ldb_dn_explode((*res)->msgs[msg_count], dn);
+		(*res)->msgs[msg_count]->dn = ldb_dn_explode_or_special((*res)->msgs[msg_count], dn);
 		ldap_memfree(dn);
 		if (!(*res)->msgs[msg_count]->dn) {
 			goto failed;
diff --git a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
index 1d23478941..464c8ce69f 100644
--- a/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
+++ b/source4/lib/ldb/ldb_sqlite3/ldb_sqlite3.c
@@ -984,6 +984,7 @@ static int lsqlite3_search_bytree(struct ldb_module * module, const struct ldb_d
 
 	(*res)->msgs = talloc_steal(*res, msgs.msgs);
 	(*res)->count = msgs.count;
+	(*res)->controls = NULL;
 
 	talloc_free(local_ctx);
 	return LDB_SUCCESS;
@@ -1783,6 +1784,11 @@ destructor(void *p)
 
 static int lsqlite3_request(struct ldb_module *module, struct ldb_request *req)
 {
+	/* check for oustanding critical controls and return an error if found */
+	if (check_critical_controls(req->controls)) {
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+	
 	switch (req->operation) {
 
 	case LDB_REQ_SEARCH:
@@ -1791,7 +1797,7 @@ static int lsqlite3_request(struct ldb_module *module, struct ldb_request *req)
 					  req->op.search.scope, 
 					  req->op.search.tree, 
 					  req->op.search.attrs, 
-					  req->op.search.res);
+					  &req->op.search.res);
 
 	case LDB_REQ_ADD:
 		return lsqlite3_add(module, req->op.add.message);
diff --git a/source4/lib/ldb/ldb_tdb/ldb_index.c b/source4/lib/ldb/ldb_tdb/ldb_index.c
index 75514fac83..cf9ad3b7fe 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_index.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_index.c
@@ -709,6 +709,7 @@ int ltdb_search_indexed(struct ldb_module *module,
 	}
 	(*res)->count = 0;
 	(*res)->msgs = NULL;
+	(*res)->controls = NULL;
 
 	if (scope == LDB_SCOPE_BASE) {
 		/* with BASE searches only one DN can match */
diff --git a/source4/lib/ldb/ldb_tdb/ldb_search.c b/source4/lib/ldb/ldb_tdb/ldb_search.c
index 01a87e00b1..aa5cb40712 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_search.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_search.c
@@ -441,6 +441,7 @@ static int ltdb_search_full(struct ldb_module *module,
 		return -1;
 	}
 
+	result->controls = NULL;
 	result->msgs = talloc_steal(result, sinfo->msgs);
 	result->count = sinfo->count;
 	*res = result;
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb.c b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
index ebee029d9c..432c713336 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -737,6 +737,12 @@ static int ltdb_del_trans(struct ldb_module *module)
 
 static int ltdb_request(struct ldb_module *module, struct ldb_request *req)
 {
+	/* check for oustanding critical controls and return an error if found */
+
+	if (check_critical_controls(req->controls)) {
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+	
 	switch (req->operation) {
 
 	case LDB_REQ_SEARCH:
diff --git a/source4/lib/ldb/ldb_tdb/ldb_tdb_wrap.c b/source4/lib/ldb/ldb_tdb/ldb_tdb_wrap.c
index c2e65cf825..3a18f5df88 100644
--- a/source4/lib/ldb/ldb_tdb/ldb_tdb_wrap.c
+++ b/source4/lib/ldb/ldb_tdb/ldb_tdb_wrap.c
@@ -24,6 +24,7 @@
 
 #include "includes.h"
 #include "ldb/include/ldb.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/ldb_tdb/ldb_tdb.h"
 
 /*
diff --git a/source4/lib/ldb/modules/objectclass.c b/source4/lib/ldb/modules/objectclass.c
index 9891ed8eb1..7a037cc98a 100644
--- a/source4/lib/ldb/modules/objectclass.c
+++ b/source4/lib/ldb/modules/objectclass.c
@@ -108,6 +108,7 @@ static int objectclass_handle(struct ldb_module *module, struct ldb_request *req
 	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;
+	search_request->controls = NULL;
 
 	ret = ldb_next_request(module, search_request);
 	if (ret) {
@@ -273,6 +274,7 @@ static int objectclass_handle(struct ldb_module *module, struct ldb_request *req
 
 	modify_request->operation = LDB_REQ_MODIFY;
 	modify_request->op.mod.message = modify_msg;
+	modify_request->controls = NULL;
 
 	/* And now push the write into the database */
 	ret = ldb_next_request(module, modify_request);
@@ -303,10 +305,12 @@ static const struct ldb_module_ops objectclass_ops = {
 	.request      	   = objectclass_request,
 };
 
-struct ldb_module *objectclass_module_init(struct ldb_context *ldb, const char *options[])
+struct ldb_module *objectclass_module_init(struct ldb_context *ldb, int stage, const char *options[])
 {
 	struct ldb_module *ctx;
 
+	if (stage != LDB_MODULES_INIT_STAGE_1) return NULL;
+
 	ctx = talloc(ldb, struct ldb_module);
 	if (!ctx)
 		return NULL;
diff --git a/source4/lib/ldb/modules/operational.c b/source4/lib/ldb/modules/operational.c
index 65d9f12e34..09de0936a1 100644
--- a/source4/lib/ldb/modules/operational.c
+++ b/source4/lib/ldb/modules/operational.c
@@ -368,10 +368,12 @@ static const struct ldb_module_ops operational_ops = {
 
 
 /* the init function */
-struct ldb_module *operational_module_init(struct ldb_context *ldb, const char *options[])
+struct ldb_module *operational_module_init(struct ldb_context *ldb, int stage, const char *options[])
 {
 	struct ldb_module *ctx;
 
+	if (stage != LDB_MODULES_INIT_STAGE_1) return NULL;
+	
 	ctx = talloc(ldb, struct ldb_module);
 	if (!ctx)
 		return NULL;
diff --git a/source4/lib/ldb/modules/paged_results.c b/source4/lib/ldb/modules/paged_results.c
new file mode 100644
index 0000000000..31b73d2ae4
--- /dev/null
+++ b/source4/lib/ldb/modules/paged_results.c
@@ -0,0 +1,296 @@
+/* 
+   ldb database library
+
+   Copyright (C) Simo Sorce  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: ldb paged results control module
+ *
+ *  Description: this module caches a complete search and sends back
+ *  		 results in chunks as asked by the client
+ *
+ *  Author: Simo Sorce
+ */
+
+#include "includes.h"
+#include "ldb/include/ldb.h"
+#include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
+
+#include <time.h>
+
+struct results_store {
+	char *cookie;
+	time_t timestamp;
+	int num_sent;
+	struct ldb_result *result;
+	struct results_store *prev;
+	struct results_store *next;
+};
+
+struct private_data {
+
+	int next_free_id;
+	struct results_store *store;
+	
+};
+
+
+static struct results_store *new_store(struct private_data *priv)
+{
+	struct results_store *new;
+	int new_id = priv->next_free_id++;
+
+	/* TODO: we should have a limit on the number of
+	 * outstanding paged searches
+	 */
+
+	new = talloc(priv, struct results_store);
+	if (!new) return NULL;
+
+	new->cookie = talloc_asprintf(new, "%d", new_id);
+	if (!new->cookie) {
+		talloc_free(new);
+		return NULL;
+	}
+
+	new->timestamp = time(NULL);
+
+	new->num_sent = 0;
+	new->result = NULL;
+
+	/* put this entry as first */
+	new->prev = NULL;
+	new->next = priv->store;
+	if (priv->store != NULL) priv->store->prev = new;
+	priv->store = new;
+
+	return new;
+}
+
+static void remove_store(struct results_store *store)
+{
+	if (store->prev) {
+		store->prev->next = store->next;
+	}
+	if (store->next) {
+		store->next->prev = store->prev;
+	}
+	talloc_free(store);
+}
+
+/* search */
+static int paged_search(struct ldb_module *module, struct ldb_request *req)
+{
+	struct private_data *private_data = talloc_get_type(module->private_data, struct private_data);
+	struct results_store *current = NULL;
+	struct ldb_result *paged_result;
+	struct ldb_control **saved_controls;
+	struct ldb_control *control;
+	struct ldb_paged_control *paged_ctrl;
+	struct ldb_paged_control *paged_ret;
+	int i, ret;
+
+	/* check if there's a paged request control */
+	control = get_control_from_list(req->controls, LDB_CONTROL_PAGED_RESULTS_OID);
+
+	if (control == NULL) {
+		/* not found go on */
+		return ldb_next_request(module, req);
+	}
+
+	paged_ctrl = talloc_get_type(control->data, struct ldb_paged_control);
+
+	/* check if it is a continuation search the store */
+	if (paged_ctrl->cookie_len != 0) {
+		for (current = private_data->store; current; current = current->next) {
+			if (strcmp(current->cookie, paged_ctrl->cookie) == 0) {
+				current->timestamp = time(NULL);
+				break;
+			}
+		}
+		if (current == NULL) {
+			return LDB_ERR_UNWILLING_TO_PERFORM;
+		}
+	}
+
+	/* is this a brand new paged request ? */
+	if (current == NULL) {
+
+		/* save controls list and remove this one from the list */
+		if (!save_controls(control, req, &saved_controls)) {
+			return LDB_ERR_OTHER;
+		}
+
+		/* perform the search */
+		ret = ldb_next_request(module, req);
+
+		/* restore original controls list */
+		if (req->controls) talloc_free(req->controls);
+		req->controls = saved_controls;
+
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+
+		/* create a new entry in the cache */
+		current = new_store(private_data);
+		if (!current) {
+			return LDB_ERR_OTHER;
+		}
+
+		/* steal the search result */
+		current->result = talloc_steal(current, req->op.search.res);
+		req->op.search.res = NULL;
+	}
+
+	/* create a container for the next batch of results */
+	paged_result = talloc(current, struct ldb_result);
+	if (!paged_result) {
+		return LDB_ERR_OTHER;
+	}
+	paged_result->count = 0;
+	paged_result->msgs = NULL;
+	paged_result->controls = NULL;
+
+	/* check if it is an abandon */
+	if (paged_ctrl->size == 0) {
+		req->op.search.res = talloc_steal(private_data, paged_result);
+		remove_store(current);
+		return LDB_SUCCESS;
+	}
+
+	/* return a batch of results */
+		
+	paged_result->controls = talloc_array(paged_result, struct ldb_control *, 2);
+	if (!paged_result->controls) {
+		talloc_free(paged_result);
+		return LDB_ERR_OTHER;
+	}
+
+	paged_result->controls[0] = talloc(paged_result->controls, struct ldb_control);
+	if (!paged_result->controls[0]) {
+		talloc_free(paged_result);
+		return LDB_ERR_OTHER;
+	}
+	paged_result->controls[0]->oid = talloc_strdup(paged_result->controls[0], LDB_CONTROL_PAGED_RESULTS_OID);
+	paged_result->controls[0]->critical = 0;
+	paged_result->controls[1] = NULL;
+
+	paged_ret = talloc(paged_result->controls[0], struct ldb_paged_control);
+	if (!paged_ret) {
+		talloc_free(paged_result);
+		return LDB_ERR_OTHER;
+	}
+	paged_result->controls[0]->data = paged_ret;
+
+	if (paged_ctrl->size >= current->result->count) {
+		paged_ret->size = 0;
+		paged_ret->cookie = NULL;
+		paged_ret->cookie_len = 0;
+		paged_result->count = current->result->count;
+		current->result->count = 0;
+	} else {
+		paged_ret->size = current->result->count;
+		paged_ret->cookie = talloc_strdup(paged_ret, current->cookie);
+		paged_ret->cookie_len = strlen(paged_ret->cookie) + 1;
+		paged_result->count = paged_ctrl->size;
+		current->result->count -= paged_ctrl->size;
+	}
+
+	paged_result->msgs = talloc_array(paged_result, struct ldb_message *, paged_result->count + 1);
+	if (!paged_result->msgs) {
+		talloc_free(paged_result);
+		return LDB_ERR_OTHER;
+	}
+	for (i = 0; i < paged_result->count; i++) {
+		paged_result->msgs[i] = talloc_steal(paged_result->msgs, current->result->msgs[current->num_sent + i]);
+	}
+	current->num_sent += paged_result->count;
+	paged_result->msgs[paged_result->count] = NULL;
+
+	req->op.search.res = paged_result;
+
+	return LDB_SUCCESS;	
+}
+
+static int paged_request(struct ldb_module *module, struct ldb_request *req)
+{
+	switch (req->operation) {
+
+	case LDB_REQ_SEARCH:
+		return paged_search(module, req);
+
+	default:
+		return ldb_next_request(module, req);
+
+	}
+}
+
+static const struct ldb_module_ops paged_ops = {
+	.name		   = "paged_results",
+	.request      	   = paged_request,
+};
+
+struct ldb_module *paged_results_module_init(struct ldb_context *ldb, int stage, const char *options[])
+{
+	struct ldb_module *ctx;
+	struct private_data *data;
+
+	if (stage == LDB_MODULES_INIT_STAGE_2) {
+		struct ldb_request request;
+		int ret;
+
+		request.operation = LDB_REQ_REGISTER;
+		request.op.reg.oid = LDB_CONTROL_PAGED_RESULTS_OID;
+		request.controls = NULL;
+
+		ret = ldb_request(ldb, &request);
+		if (ret != LDB_SUCCESS) {
+			ldb_debug(ldb, LDB_DEBUG_ERROR, "paged_request: Unable to register control with rootdse!\n");
+		}
+
+		return NULL;
+	}
+
+	ctx = talloc(ldb, struct ldb_module);
+	if (!ctx)
+		return NULL;
+
+	data = talloc(ctx, struct private_data);
+	if (data == NULL) {
+		talloc_free(ctx);
+		return NULL;
+	}
+
+	data->next_free_id = 1;
+	data->store = NULL;
+	ctx->private_data = data;
+
+	ctx->ldb = ldb;
+	ctx->prev = ctx->next = NULL;
+	ctx->ops = &paged_ops;
+
+	return ctx;
+}
diff --git a/source4/lib/ldb/modules/rdn_name.c b/source4/lib/ldb/modules/rdn_name.c
index f35cff916c..f6dbc38740 100644
--- a/source4/lib/ldb/modules/rdn_name.c
+++ b/source4/lib/ldb/modules/rdn_name.c
@@ -214,10 +214,12 @@ static const struct ldb_module_ops rdn_name_ops = {
 
 
 /* the init function */
-struct ldb_module *rdn_name_module_init(struct ldb_context *ldb, const char *options[])
+struct ldb_module *rdn_name_module_init(struct ldb_context *ldb, int stage, const char *options[])
 {
 	struct ldb_module *ctx;
 
+	if (stage != LDB_MODULES_INIT_STAGE_1) return NULL;
+
 	ctx = talloc(ldb, struct ldb_module);
 	if (!ctx)
 		return NULL;
diff --git a/source4/lib/ldb/modules/schema.c b/source4/lib/ldb/modules/schema.c
index 9fb2efee30..778f52885c 100644
--- a/source4/lib/ldb/modules/schema.c
+++ b/source4/lib/ldb/modules/schema.c
@@ -484,10 +484,12 @@ static const struct ldb_module_ops schema_ops = {
 	.request           = schema_request
 };
 
-struct ldb_module *schema_module_init(struct ldb_context *ldb, const char *options[])
+struct ldb_module *schema_module_init(struct ldb_context *ldb, int stage, const char *options[])
 {
 	struct ldb_module *ctx;
 
+	if (stage != LDB_MODULES_INIT_STAGE_1) return NULL;
+
 	ctx = talloc(ldb, struct ldb_module);
 	if (!ctx) {
 		return NULL;
diff --git a/source4/lib/ldb/modules/skel.c b/source4/lib/ldb/modules/skel.c
index 1bbb81f288..dacbd6960e 100644
--- a/source4/lib/ldb/modules/skel.c
+++ b/source4/lib/ldb/modules/skel.c
@@ -131,11 +131,17 @@ static const struct ldb_module_ops skel_ops = {
 	.del_transaction   = skel_del_trans,
 };
 
-struct ldb_module *skel_module_init(struct ldb_context *ldb, const char *options[])
+struct ldb_module *skel_module_init(struct ldb_context *ldb, int stage, const char *options[])
 {
 	struct ldb_module *ctx;
 	struct private_data *data;
 
+	if (stage == LDB_MODULES_INIT_STAGE_2) {
+		/* second stage init stuff */
+		/* see control modules as example */
+		return NULL;
+	}
+
 	ctx = talloc(ldb, struct ldb_module);
 	if (!ctx)
 		return NULL;
diff --git a/source4/lib/ldb/modules/sort.c b/source4/lib/ldb/modules/sort.c
new file mode 100644
index 0000000000..2757647710
--- /dev/null
+++ b/source4/lib/ldb/modules/sort.c
@@ -0,0 +1,265 @@
+/* 
+   ldb database library
+
+   Copyright (C) Simo Sorce  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: ldb server side sort control module
+ *
+ *  Description: this module sorts the results of a search
+ *
+ *  Author: Simo Sorce
+ */
+
+#include "includes.h"
+#include "ldb/include/ldb.h"
+#include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
+
+struct opaque {
+	struct ldb_context *ldb;
+	const struct ldb_attrib_handler *h;
+	const char *attribute;
+	int reverse;
+	int result;
+};
+
+static int build_response(struct ldb_result *res, int result, const char *desc)
+{
+	struct ldb_sort_resp_control *resp;
+	int i;
+
+	if (res->controls) {
+		for (i = 0; res->controls[i]; i++);
+		res->controls = talloc_realloc(res, res->controls, struct ldb_control *, i + 2);
+	} else {
+		i = 0;
+		res->controls = talloc_array(res, struct ldb_control *, 2);
+	}
+	if (! res->controls )
+		return LDB_ERR_OPERATIONS_ERROR;
+
+	res->controls[i+1] = NULL;
+	res->controls[i] = talloc(res->controls, struct ldb_control);
+	if (! res->controls[i] )
+		return LDB_ERR_OPERATIONS_ERROR;
+
+	res->controls[i]->oid = LDB_CONTROL_SORT_RESP_OID;
+	res->controls[i]->critical = 0;
+
+	resp = talloc(res->controls[i], struct ldb_sort_resp_control);
+	if (! resp )
+		return LDB_ERR_OPERATIONS_ERROR;
+
+	resp->result = result;
+	resp->attr_desc = talloc_strdup(resp, desc);
+
+	if (! resp->attr_desc )
+		return LDB_ERR_OPERATIONS_ERROR;
+	
+	res->controls[i]->data = resp;
+
+	return LDB_SUCCESS;
+}
+
+static int sort_compare(struct ldb_message **msg1, struct ldb_message **msg2, void *opaque)
+{
+	struct opaque *data = (struct opaque *)opaque;
+	struct ldb_message_element *el1, *el2;
+
+	if (data->result != 0) {
+		/* an error occurred previously,
+		 * let's exit the sorting by returning always 0 */
+		return 0;
+	}
+
+	el1 = ldb_msg_find_element(*msg1, data->attribute);
+	el2 = ldb_msg_find_element(*msg2, data->attribute);
+
+	if (!el1 || !el2) {
+		/* the attribute was not found return and
+		 * set an error */
+		data->result = 53;
+		return 0;
+	}
+
+	if (data->reverse)
+		return data->h->comparison_fn(data->ldb, data, &el2->values[0], &el1->values[0]);
+
+	return data->h->comparison_fn(data->ldb, data, &el1->values[0], &el2->values[0]);
+}
+
+/* search */
+static int server_sort_search(struct ldb_module *module, struct ldb_request *req)
+{
+	struct ldb_result *sort_result = NULL;
+	struct ldb_control *control;
+	struct ldb_control **saved_controls;
+	struct ldb_server_sort_control **sort_ctrls;
+	int ret, result = 0;
+	int do_sort = 1;
+
+	/* check if there's a paged request control */
+	control = get_control_from_list(req->controls, LDB_CONTROL_SERVER_SORT_OID);
+	if (control == NULL) {
+		/* not found go on */
+		return ldb_next_request(module, req);
+	}
+
+	sort_ctrls = talloc_get_type(control->data, struct ldb_server_sort_control *);
+
+	/* FIXME: we do not support more than one attribute for sorting right now */
+	/* FIXME: we need to check if the attribute type exist or return an error */
+	if (sort_ctrls[1] != NULL)
+		do_sort = 0;
+		
+	if (!do_sort && control->critical) {
+		sort_result = talloc_zero(req, struct ldb_result);
+		if (!sort_result)
+			return LDB_ERR_OPERATIONS_ERROR;
+
+		req->op.search.res = sort_result;
+	
+		/* 53 = unwilling to perform */
+		if ((ret = build_response(sort_result, 53, "sort control is not complete yet")) != LDB_SUCCESS) {
+			return ret;
+		}
+
+		return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+
+	/* save it locally and remove it from the list */
+	if (!save_controls(control, req, &saved_controls)) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ldb_next_request(module, req);
+
+	if (req->controls) talloc_free(req->controls);
+	req->controls = saved_controls;
+
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	/* SORT HERE */
+	if (do_sort) {
+		struct opaque *data;
+	       
+		data = talloc(module, struct opaque);
+		if (!data)
+			return LDB_ERR_OPERATIONS_ERROR;
+		
+		data->attribute = sort_ctrls[0]->attributeName;
+		data->reverse = sort_ctrls[0]->reverse;
+		data->ldb = module->ldb;
+		data->h = ldb_attrib_handler(data->ldb, data->attribute);
+		data->result = 0;
+		sort_result = req->op.search.res;
+
+		/* FIXME: I don't like to use a static structure like sort_control
+		 * we need to either:
+		 * a) write a qsort function that takes a third void parameter
+		 * or
+		 * b) prepare a structure with all elements pre digested like:
+		 * 	struct element {
+		 * 		struct ldb_message_element *el;
+		 * 		struct ldb_message *msg;
+		 * 	}
+		 *
+		 * 	this mean we will have to do a linear scan of
+		 * 	the msgs array to build the new sort array, and
+		 * 	then do a linear scan of the resulting array
+		 * 	to rebuild the msgs array in the original shape.
+		 */
+
+		ldb_qsort(sort_result->msgs,
+			  sort_result->count,
+			  sizeof(struct ldb_message *),
+			  data,
+			  (ldb_qsort_cmp_fn_t)sort_compare);
+
+		result = data->result;
+
+		talloc_free(data);
+	} else {
+		result = 53;
+	}
+
+	if ((ret = build_response(sort_result, result, "sort control is not complete yet")) != LDB_SUCCESS) {
+		return ret;
+	}
+
+	return LDB_SUCCESS;
+}
+
+static int server_sort(struct ldb_module *module, struct ldb_request *req)
+{
+	switch (req->operation) {
+
+	case LDB_REQ_SEARCH:
+		return server_sort_search(module, req);
+
+	default:
+		return ldb_next_request(module, req);
+
+	}
+}
+
+static const struct ldb_module_ops server_sort_ops = {
+	.name		   = "server_sort",
+	.request      	   = server_sort,
+};
+
+struct ldb_module *server_sort_module_init(struct ldb_context *ldb, int stage, const char *options[])
+{
+	struct ldb_module *ctx;
+
+	if (stage == LDB_MODULES_INIT_STAGE_2) {
+		struct ldb_request request;
+		int ret;
+
+		request.operation = LDB_REQ_REGISTER;
+		request.op.reg.oid = LDB_CONTROL_SERVER_SORT_OID;
+		request.controls = NULL;
+
+		ret = ldb_request(ldb, &request);
+		if (ret != LDB_SUCCESS) {
+			ldb_debug(ldb, LDB_DEBUG_ERROR, "server_sort: Unable to register control with rootdse!\n");
+		}
+
+		return NULL;
+	}
+
+	ctx = talloc(ldb, struct ldb_module);
+	if (!ctx)
+		return NULL;
+
+	ctx->ldb = ldb;
+	ctx->prev = ctx->next = NULL;
+	ctx->ops = &server_sort_ops;
+	ctx->private_data = NULL;
+
+	return ctx;
+}
diff --git a/source4/lib/ldb/samba/ldif_handlers.c b/source4/lib/ldb/samba/ldif_handlers.c
index 51cb3f8d78..84270195dc 100644
--- a/source4/lib/ldb/samba/ldif_handlers.c
+++ b/source4/lib/ldb/samba/ldif_handlers.c
@@ -25,6 +25,7 @@
 #include "includes.h"
 #include "ldb/include/ldb.h"
 #include "ldb/include/ldb_private.h"
+#include "librpc/gen_ndr/ndr_security.h"
 #include "librpc/gen_ndr/ndr_misc.h"
 #include "dsdb/samdb/samdb.h"
 
diff --git a/source4/lib/ldb/tools/ldbadd.c b/source4/lib/ldb/tools/ldbadd.c
index c22cfde4ec..058f4dc751 100644
--- a/source4/lib/ldb/tools/ldbadd.c
+++ b/source4/lib/ldb/tools/ldbadd.c
@@ -35,6 +35,7 @@
 #include "includes.h"
 #include "ldb/include/ldb.h"
 #include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/tools/cmdline.h"
 
 #ifdef _SAMBA_BUILD_
diff --git a/source4/lib/ldb/tools/ldbdel.c b/source4/lib/ldb/tools/ldbdel.c
index a6574a5088..6da8d0269f 100644
--- a/source4/lib/ldb/tools/ldbdel.c
+++ b/source4/lib/ldb/tools/ldbdel.c
@@ -35,6 +35,7 @@
 #include "includes.h"
 #include "ldb/include/ldb.h"
 #include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/tools/cmdline.h"
 
 #ifdef _SAMBA_BUILD_
diff --git a/source4/lib/ldb/tools/ldbedit.c b/source4/lib/ldb/tools/ldbedit.c
index 8818777ceb..4d47cf27c9 100644
--- a/source4/lib/ldb/tools/ldbedit.c
+++ b/source4/lib/ldb/tools/ldbedit.c
@@ -35,6 +35,7 @@
 #include "includes.h"
 #include "ldb/include/ldb.h"
 #include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/tools/cmdline.h"
 
 #ifdef _SAMBA_BUILD_
diff --git a/source4/lib/ldb/tools/ldbmodify.c b/source4/lib/ldb/tools/ldbmodify.c
index f067aef3f8..4c78e485b5 100644
--- a/source4/lib/ldb/tools/ldbmodify.c
+++ b/source4/lib/ldb/tools/ldbmodify.c
@@ -34,6 +34,7 @@
 
 #include "includes.h"
 #include "ldb/include/ldb.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/tools/cmdline.h"
 
 #ifdef _SAMBA_BUILD_
diff --git a/source4/lib/ldb/tools/ldbrename.c b/source4/lib/ldb/tools/ldbrename.c
index f225246cc7..4b3b27c130 100644
--- a/source4/lib/ldb/tools/ldbrename.c
+++ b/source4/lib/ldb/tools/ldbrename.c
@@ -36,6 +36,7 @@
 
 #include "includes.h"
 #include "ldb/include/ldb.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/tools/cmdline.h"
 
 #ifdef _SAMBA_BUILD_
diff --git a/source4/lib/ldb/tools/ldbsearch.c b/source4/lib/ldb/tools/ldbsearch.c
index c493356405..a340e16d08 100644
--- a/source4/lib/ldb/tools/ldbsearch.c
+++ b/source4/lib/ldb/tools/ldbsearch.c
@@ -35,6 +35,7 @@
 #include "includes.h"
 #include "ldb/include/ldb.h"
 #include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/tools/cmdline.h"
 
 #ifdef _SAMBA_BUILD_
@@ -55,12 +56,12 @@ static void usage(void)
 	exit(1);
 }
 
-struct ldb_context *ldbsearch_ldb;
-
 static int do_compare_msg(struct ldb_message **el1,
-			  struct ldb_message **el2)
+			  struct ldb_message **el2,
+			  void *opaque)
 {
-	return ldb_dn_compare(ldbsearch_ldb, (*el1)->dn, (*el2)->dn);
+	struct ldb_context *ldb = talloc_get_type(opaque, struct ldb_context);
+	return ldb_dn_compare(ldb, (*el1)->dn, (*el2)->dn);
 }
 
 static int do_search(struct ldb_context *ldb,
@@ -81,10 +82,9 @@ static int do_search(struct ldb_context *ldb,
 
 	printf("# returned %d records\n", ret);
 
-	ldbsearch_ldb = ldb;
 	if (sort_attribs) {
-		qsort(result->msgs, ret, sizeof(struct ldb_message *),
-				(comparison_fn_t)do_compare_msg);
+		ldb_qsort(result->msgs, ret, sizeof(struct ldb_message *),
+			  ldb, (ldb_qsort_cmp_fn_t)do_compare_msg);
 	}
 
 	for (i = 0; i < result->count; i++) {
diff --git a/source4/lib/ldb/tools/ldbtest.c b/source4/lib/ldb/tools/ldbtest.c
index f79f5c6b4c..7abc1bfcef 100644
--- a/source4/lib/ldb/tools/ldbtest.c
+++ b/source4/lib/ldb/tools/ldbtest.c
@@ -35,6 +35,7 @@
 #include "includes.h"
 #include "ldb/include/ldb.h"
 #include "ldb/include/ldb_errors.h"
+#include "ldb/include/ldb_private.h"
 #include "ldb/tools/cmdline.h"
 
 #ifdef _SAMBA_BUILD_