ldb: make ldb a top level library for Samba 4.0

Signed-off-by: Andrew Tridgell <tridge@samba.org>

7 files changed, 4822 insertions, 0 deletions

diff --git a/lib/ldb/ldb_tdb/ldb_cache.c b/lib/ldb/ldb_tdb/ldb_cache.c
new file mode 100644
index 0000000000..e54ceaaa98
--- /dev/null
+++ b/lib/ldb/ldb_tdb/ldb_cache.c
@@ -0,0 +1,490 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+
+     ** 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 3 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, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb tdb cache functions
+ *
+ *  Description: cache special records in a ldb/tdb
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_tdb.h"
+#include "ldb_private.h"
+
+#define LTDB_FLAG_CASE_INSENSITIVE (1<<0)
+#define LTDB_FLAG_INTEGER          (1<<1)
+#define LTDB_FLAG_HIDDEN           (1<<2)
+
+/* valid attribute flags */
+static const struct {
+	const char *name;
+	int value;
+} ltdb_valid_attr_flags[] = {
+	{ "CASE_INSENSITIVE", LTDB_FLAG_CASE_INSENSITIVE },
+	{ "INTEGER", LTDB_FLAG_INTEGER },
+	{ "HIDDEN", LTDB_FLAG_HIDDEN },
+	{ "NONE", 0 },
+	{ NULL, 0 }
+};
+
+
+/*
+  de-register any special handlers for @ATTRIBUTES
+*/
+static void ltdb_attributes_unload(struct ldb_module *module)
+{
+	struct ldb_context *ldb;
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	struct ldb_message *msg;
+	unsigned int i;
+
+	ldb = ldb_module_get_ctx(module);
+
+	if (ltdb->cache->attributes == NULL) {
+		/* no previously loaded attributes */
+		return;
+	}
+
+	msg = ltdb->cache->attributes;
+	for (i=0;i<msg->num_elements;i++) {
+		ldb_schema_attribute_remove(ldb, msg->elements[i].name);
+	}
+
+	talloc_free(ltdb->cache->attributes);
+	ltdb->cache->attributes = NULL;
+}
+
+/*
+  add up the attrib flags for a @ATTRIBUTES element
+*/
+static int ltdb_attributes_flags(struct ldb_message_element *el, unsigned *v)
+{
+	unsigned int i;
+	unsigned value = 0;
+	for (i=0;i<el->num_values;i++) {
+		unsigned int j;
+		for (j=0;ltdb_valid_attr_flags[j].name;j++) {
+			if (strcmp(ltdb_valid_attr_flags[j].name, 
+				   (char *)el->values[i].data) == 0) {
+				value |= ltdb_valid_attr_flags[j].value;
+				break;
+			}
+		}
+		if (ltdb_valid_attr_flags[j].name == NULL) {
+			return -1;
+		}
+	}
+	*v = value;
+	return 0;
+}
+
+/*
+  register any special handlers from @ATTRIBUTES
+*/
+static int ltdb_attributes_load(struct ldb_module *module)
+{
+	struct ldb_context *ldb;
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	struct ldb_message *msg = ltdb->cache->attributes;
+	struct ldb_dn *dn;
+	unsigned int i;
+	int r;
+
+	ldb = ldb_module_get_ctx(module);
+
+	if (ldb->schema.attribute_handler_override) {
+		/* we skip loading the @ATTRIBUTES record when a module is supplying
+		   its own attribute handling */
+		return 0;
+	}
+
+	dn = ldb_dn_new(module, ldb, LTDB_ATTRIBUTES);
+	if (dn == NULL) goto failed;
+
+	r = ltdb_search_dn1(module, dn, msg);
+	talloc_free(dn);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+	if (r == LDB_ERR_NO_SUCH_OBJECT) {
+		return 0;
+	}
+	/* mapping these flags onto ldap 'syntaxes' isn't strictly correct,
+	   but its close enough for now */
+	for (i=0;i<msg->num_elements;i++) {
+		unsigned flags;
+		const char *syntax;
+		const struct ldb_schema_syntax *s;
+
+		if (ltdb_attributes_flags(&msg->elements[i], &flags) != 0) {
+			ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid @ATTRIBUTES element for '%s'", msg->elements[i].name);
+			goto failed;
+		}
+		switch (flags & ~LTDB_FLAG_HIDDEN) {
+		case 0:
+			syntax = LDB_SYNTAX_OCTET_STRING;
+			break;
+		case LTDB_FLAG_CASE_INSENSITIVE:
+			syntax = LDB_SYNTAX_DIRECTORY_STRING;
+			break;
+		case LTDB_FLAG_INTEGER:
+			syntax = LDB_SYNTAX_INTEGER;
+			break;
+		default:
+			ldb_debug(ldb, LDB_DEBUG_ERROR, 
+				  "Invalid flag combination 0x%x for '%s' in @ATTRIBUTES",
+				  flags, msg->elements[i].name);
+			goto failed;
+		}
+
+		s = ldb_standard_syntax_by_name(ldb, syntax);
+		if (s == NULL) {
+			ldb_debug(ldb, LDB_DEBUG_ERROR, 
+				  "Invalid attribute syntax '%s' for '%s' in @ATTRIBUTES",
+				  syntax, msg->elements[i].name);
+			goto failed;
+		}
+
+		flags |= LDB_ATTR_FLAG_ALLOCATED;
+		if (ldb_schema_attribute_add_with_syntax(ldb, msg->elements[i].name, flags, s) != 0) {
+			goto failed;
+		}
+	}
+
+	return 0;
+failed:
+	return -1;
+}
+
+
+/*
+  initialise the baseinfo record
+*/
+static int ltdb_baseinfo_init(struct ldb_module *module)
+{
+	struct ldb_context *ldb;
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	struct ldb_message *msg;
+	struct ldb_message_element el;
+	struct ldb_val val;
+	int ret;
+	/* the initial sequence number must be different from the one
+	   set in ltdb_cache_free(). Thanks to Jon for pointing this
+	   out. */
+	const char *initial_sequence_number = "1";
+
+	ldb = ldb_module_get_ctx(module);
+
+	ltdb->sequence_number = atof(initial_sequence_number);
+
+	msg = ldb_msg_new(ltdb);
+	if (msg == NULL) {
+		goto failed;
+	}
+
+	msg->num_elements = 1;
+	msg->elements = &el;
+	msg->dn = ldb_dn_new(msg, ldb, LTDB_BASEINFO);
+	if (!msg->dn) {
+		goto failed;
+	}
+	el.name = talloc_strdup(msg, LTDB_SEQUENCE_NUMBER);
+	if (!el.name) {
+		goto failed;
+	}
+	el.values = &val;
+	el.num_values = 1;
+	el.flags = 0;
+	val.data = (uint8_t *)talloc_strdup(msg, initial_sequence_number);
+	if (!val.data) {
+		goto failed;
+	}
+	val.length = 1;
+	
+	ret = ltdb_store(module, msg, TDB_INSERT);
+
+	talloc_free(msg);
+
+	return ret;
+
+failed:
+	talloc_free(msg);
+	errno = ENOMEM;
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+/*
+  free any cache records
+ */
+static void ltdb_cache_free(struct ldb_module *module)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+
+	ltdb->sequence_number = 0;
+	talloc_free(ltdb->cache);
+	ltdb->cache = NULL;
+}
+
+/*
+  force a cache reload
+*/
+int ltdb_cache_reload(struct ldb_module *module)
+{
+	ltdb_attributes_unload(module);
+	ltdb_cache_free(module);
+	return ltdb_cache_load(module);
+}
+
+/*
+  load the cache records
+*/
+int ltdb_cache_load(struct ldb_module *module)
+{
+	struct ldb_context *ldb;
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	struct ldb_dn *baseinfo_dn = NULL, *options_dn = NULL;
+	struct ldb_dn *indexlist_dn = NULL;
+	uint64_t seq;
+	struct ldb_message *baseinfo = NULL, *options = NULL;
+	int r;
+
+	ldb = ldb_module_get_ctx(module);
+
+	/* a very fast check to avoid extra database reads */
+	if (ltdb->cache != NULL && 
+	    tdb_get_seqnum(ltdb->tdb) == ltdb->tdb_seqnum) {
+		return 0;
+	}
+
+	if (ltdb->cache == NULL) {
+		ltdb->cache = talloc_zero(ltdb, struct ltdb_cache);
+		if (ltdb->cache == NULL) goto failed;
+		ltdb->cache->indexlist = ldb_msg_new(ltdb->cache);
+		ltdb->cache->attributes = ldb_msg_new(ltdb->cache);
+		if (ltdb->cache->indexlist == NULL ||
+		    ltdb->cache->attributes == NULL) {
+			goto failed;
+		}
+	}
+
+	baseinfo = ldb_msg_new(ltdb->cache);
+	if (baseinfo == NULL) goto failed;
+
+	baseinfo_dn = ldb_dn_new(baseinfo, ldb, LTDB_BASEINFO);
+	if (baseinfo_dn == NULL) goto failed;
+
+	r= ltdb_search_dn1(module, baseinfo_dn, baseinfo);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+	
+	/* possibly initialise the baseinfo */
+	if (r == LDB_ERR_NO_SUCH_OBJECT) {
+		if (ltdb_baseinfo_init(module) != LDB_SUCCESS) {
+			goto failed;
+		}
+		if (ltdb_search_dn1(module, baseinfo_dn, baseinfo) != LDB_SUCCESS) {
+			goto failed;
+		}
+	}
+
+	ltdb->tdb_seqnum = tdb_get_seqnum(ltdb->tdb);
+
+	/* if the current internal sequence number is the same as the one
+	   in the database then assume the rest of the cache is OK */
+	seq = ldb_msg_find_attr_as_uint64(baseinfo, LTDB_SEQUENCE_NUMBER, 0);
+	if (seq == ltdb->sequence_number) {
+		goto done;
+	}
+	ltdb->sequence_number = seq;
+
+	/* Read an interpret database options */
+	options = ldb_msg_new(ltdb->cache);
+	if (options == NULL) goto failed;
+
+	options_dn = ldb_dn_new(options, ldb, LTDB_OPTIONS);
+	if (options_dn == NULL) goto failed;
+
+	r= ltdb_search_dn1(module, options_dn, options);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+	
+	/* set flag for checking base DN on searches */
+	if (r == LDB_SUCCESS) {
+		ltdb->check_base = ldb_msg_find_attr_as_bool(options, LTDB_CHECK_BASE, false);
+	} else {
+		ltdb->check_base = false;
+	}
+
+	talloc_free(ltdb->cache->indexlist);
+	ltdb_attributes_unload(module); /* calls internally "talloc_free" */
+
+	ltdb->cache->indexlist = ldb_msg_new(ltdb->cache);
+	ltdb->cache->attributes = ldb_msg_new(ltdb->cache);
+	if (ltdb->cache->indexlist == NULL ||
+	    ltdb->cache->attributes == NULL) {
+		goto failed;
+	}
+	ltdb->cache->one_level_indexes = false;
+	ltdb->cache->attribute_indexes = false;
+	    
+	indexlist_dn = ldb_dn_new(module, ldb, LTDB_INDEXLIST);
+	if (indexlist_dn == NULL) goto failed;
+
+	r = ltdb_search_dn1(module, indexlist_dn, ltdb->cache->indexlist);
+	if (r != LDB_SUCCESS && r != LDB_ERR_NO_SUCH_OBJECT) {
+		goto failed;
+	}
+
+	if (ldb_msg_find_element(ltdb->cache->indexlist, LTDB_IDXONE) != NULL) {
+		ltdb->cache->one_level_indexes = true;
+	}
+	if (ldb_msg_find_element(ltdb->cache->indexlist, LTDB_IDXATTR) != NULL) {
+		ltdb->cache->attribute_indexes = true;
+	}
+
+	if (ltdb_attributes_load(module) == -1) {
+		goto failed;
+	}
+
+done:
+	talloc_free(options);
+	talloc_free(baseinfo);
+	talloc_free(indexlist_dn);
+	return 0;
+
+failed:
+	talloc_free(options);
+	talloc_free(baseinfo);
+	talloc_free(indexlist_dn);
+	return -1;
+}
+
+
+/*
+  increase the sequence number to indicate a database change
+*/
+int ltdb_increase_sequence_number(struct ldb_module *module)
+{
+	struct ldb_context *ldb;
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	struct ldb_message *msg;
+	struct ldb_message_element el[2];
+	struct ldb_val val;
+	struct ldb_val val_time;
+	time_t t = time(NULL);
+	char *s = NULL;
+	int ret;
+
+	ldb = ldb_module_get_ctx(module);
+
+	msg = ldb_msg_new(ltdb);
+	if (msg == NULL) {
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	s = talloc_asprintf(msg, "%llu", ltdb->sequence_number+1);
+	if (!s) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	msg->num_elements = ARRAY_SIZE(el);
+	msg->elements = el;
+	msg->dn = ldb_dn_new(msg, ldb, LTDB_BASEINFO);
+	if (msg->dn == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	el[0].name = talloc_strdup(msg, LTDB_SEQUENCE_NUMBER);
+	if (el[0].name == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	el[0].values = &val;
+	el[0].num_values = 1;
+	el[0].flags = LDB_FLAG_MOD_REPLACE;
+	val.data = (uint8_t *)s;
+	val.length = strlen(s);
+
+	el[1].name = talloc_strdup(msg, LTDB_MOD_TIMESTAMP);
+	if (el[1].name == NULL) {
+		talloc_free(msg);
+		errno = ENOMEM;
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	el[1].values = &val_time;
+	el[1].num_values = 1;
+	el[1].flags = LDB_FLAG_MOD_REPLACE;
+
+	s = ldb_timestring(msg, t);
+	if (s == NULL) {
+		talloc_free(msg);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	val_time.data = (uint8_t *)s;
+	val_time.length = strlen(s);
+
+	ret = ltdb_modify_internal(module, msg, NULL);
+
+	talloc_free(msg);
+
+	if (ret == LDB_SUCCESS) {
+		ltdb->sequence_number += 1;
+	}
+
+	/* updating the tdb_seqnum here avoids us reloading the cache
+	   records due to our own modification */
+	ltdb->tdb_seqnum = tdb_get_seqnum(ltdb->tdb);
+
+	return ret;
+}
+
+int ltdb_check_at_attributes_values(const struct ldb_val *value)
+{
+	unsigned int i;
+
+	for (i = 0; ltdb_valid_attr_flags[i].name != NULL; i++) {
+		if ((strcmp(ltdb_valid_attr_flags[i].name, (char *)value->data) == 0)) {
+			return 0;
+		}
+	}
+
+	return -1;
+}
+
diff --git a/lib/ldb/ldb_tdb/ldb_index.c b/lib/ldb/ldb_tdb/ldb_index.c
new file mode 100644
index 0000000000..24cc93feb9
--- /dev/null
+++ b/lib/ldb/ldb_tdb/ldb_index.c
@@ -0,0 +1,1599 @@
+/*
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004-2009
+
+     ** 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 3 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, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb tdb backend - indexing
+ *
+ *  Description: indexing routines for ldb tdb backend
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_tdb.h"
+
+struct dn_list {
+	unsigned int count;
+	struct ldb_val *dn;
+};
+
+struct ltdb_idxptr {
+	struct tdb_context *itdb;
+	int error;
+};
+
+/* we put a @IDXVERSION attribute on index entries. This
+   allows us to tell if it was written by an older version
+*/
+#define LTDB_INDEXING_VERSION 2
+
+/* enable the idxptr mode when transactions start */
+int ltdb_index_transaction_start(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	ltdb->idxptr = talloc_zero(ltdb, struct ltdb_idxptr);
+	return LDB_SUCCESS;
+}
+
+/* compare two DN entries in a dn_list. Take account of possible
+ * differences in string termination */
+static int dn_list_cmp(const struct ldb_val *v1, const struct ldb_val *v2)
+{
+	if (v1->length > v2->length && v1->data[v2->length] != 0) {
+		return -1;
+	}
+	if (v1->length < v2->length && v2->data[v1->length] != 0) {
+		return 1;
+	}
+	return strncmp((char *)v1->data, (char *)v2->data, v1->length);
+}
+
+
+/*
+  find a entry in a dn_list, using a ldb_val. Uses a case sensitive
+  comparison with the dn returns -1 if not found
+ */
+static int ltdb_dn_list_find_val(const struct dn_list *list, const struct ldb_val *v)
+{
+	unsigned int i;
+	for (i=0; i<list->count; i++) {
+		if (dn_list_cmp(&list->dn[i], v) == 0) return i;
+	}
+	return -1;
+}
+
+/*
+  find a entry in a dn_list. Uses a case sensitive comparison with the dn
+  returns -1 if not found
+ */
+static int ltdb_dn_list_find_str(struct dn_list *list, const char *dn)
+{
+	struct ldb_val v;
+	v.data = discard_const_p(unsigned char, dn);
+	v.length = strlen(dn);
+	return ltdb_dn_list_find_val(list, &v);
+}
+
+/*
+  this is effectively a cast function, but with lots of paranoia
+  checks and also copes with CPUs that are fussy about pointer
+  alignment
+ */
+static struct dn_list *ltdb_index_idxptr(struct ldb_module *module, TDB_DATA rec, bool check_parent)
+{
+	struct dn_list *list;
+	if (rec.dsize != sizeof(void *)) {
+		ldb_asprintf_errstring(ldb_module_get_ctx(module), 
+				       "Bad data size for idxptr %u", (unsigned)rec.dsize);
+		return NULL;
+	}
+	/* note that we can't just use a cast here, as rec.dptr may
+	   not be aligned sufficiently for a pointer. A cast would cause
+	   platforms like some ARM CPUs to crash */
+	memcpy(&list, rec.dptr, sizeof(void *));
+	list = talloc_get_type(list, struct dn_list);
+	if (list == NULL) {
+		ldb_asprintf_errstring(ldb_module_get_ctx(module), 
+				       "Bad type '%s' for idxptr", 
+				       talloc_get_name(list));
+		return NULL;
+	}
+	if (check_parent && list->dn && talloc_parent(list->dn) != list) {
+		ldb_asprintf_errstring(ldb_module_get_ctx(module), 
+				       "Bad parent '%s' for idxptr", 
+				       talloc_get_name(talloc_parent(list->dn)));
+		return NULL;
+	}
+	return list;
+}
+
+/*
+  return the @IDX list in an index entry for a dn as a 
+  struct dn_list
+ */
+static int ltdb_dn_list_load(struct ldb_module *module,
+			     struct ldb_dn *dn, struct dn_list *list)
+{
+	struct ldb_message *msg;
+	int ret;
+	struct ldb_message_element *el;
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	TDB_DATA rec;
+	struct dn_list *list2;
+	TDB_DATA key;
+
+	list->dn = NULL;
+	list->count = 0;
+
+	/* see if we have any in-memory index entries */
+	if (ltdb->idxptr == NULL ||
+	    ltdb->idxptr->itdb == NULL) {
+		goto normal_index;
+	}
+
+	key.dptr = discard_const_p(unsigned char, ldb_dn_get_linearized(dn));
+	key.dsize = strlen((char *)key.dptr);
+
+	rec = tdb_fetch_compat(ltdb->idxptr->itdb, key);
+	if (rec.dptr == NULL) {
+		goto normal_index;
+	}
+
+	/* we've found an in-memory index entry */
+	list2 = ltdb_index_idxptr(module, rec, true);
+	if (list2 == NULL) {
+		free(rec.dptr);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	free(rec.dptr);
+
+	*list = *list2;
+	return LDB_SUCCESS;
+
+normal_index:
+	msg = ldb_msg_new(list);
+	if (msg == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_search_dn1(module, dn, msg);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(msg);
+		return ret;
+	}
+
+	/* TODO: check indexing version number */
+
+	el = ldb_msg_find_element(msg, LTDB_IDX);
+	if (!el) {
+		talloc_free(msg);
+		return LDB_SUCCESS;
+	}
+
+	/* we avoid copying the strings by stealing the list */
+	list->dn = talloc_steal(list, el->values);
+	list->count = el->num_values;
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  save a dn_list into a full @IDX style record
+ */
+static int ltdb_dn_list_store_full(struct ldb_module *module, struct ldb_dn *dn, 
+				   struct dn_list *list)
+{
+	struct ldb_message *msg;
+	int ret;
+
+	if (list->count == 0) {
+		ret = ltdb_delete_noindex(module, dn);
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			return LDB_SUCCESS;
+		}
+		return ret;
+	}
+
+	msg = ldb_msg_new(module);
+	if (!msg) {
+		return ldb_module_oom(module);
+	}
+
+	ret = ldb_msg_add_fmt(msg, LTDB_IDXVERSION, "%u", LTDB_INDEXING_VERSION);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(msg);
+		return ldb_module_oom(module);
+	}
+
+	msg->dn = dn;
+	if (list->count > 0) {
+		struct ldb_message_element *el;
+
+		ret = ldb_msg_add_empty(msg, LTDB_IDX, LDB_FLAG_MOD_ADD, &el);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(msg);
+			return ldb_module_oom(module);
+		}
+		el->values = list->dn;
+		el->num_values = list->count;
+	}
+
+	ret = ltdb_store(module, msg, TDB_REPLACE);
+	talloc_free(msg);
+	return ret;
+}
+
+/*
+  save a dn_list into the database, in either @IDX or internal format
+ */
+static int ltdb_dn_list_store(struct ldb_module *module, struct ldb_dn *dn, 
+			      struct dn_list *list)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	TDB_DATA rec, key;
+	int ret;
+	struct dn_list *list2;
+
+	if (ltdb->idxptr == NULL) {
+		return ltdb_dn_list_store_full(module, dn, list);
+	}
+
+	if (ltdb->idxptr->itdb == NULL) {
+		ltdb->idxptr->itdb = tdb_open_compat(NULL, 1000, TDB_INTERNAL, O_RDWR, 0, NULL, NULL);
+		if (ltdb->idxptr->itdb == NULL) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+	}
+
+	key.dptr = discard_const_p(unsigned char, ldb_dn_get_linearized(dn));
+	key.dsize = strlen((char *)key.dptr);
+
+	rec = tdb_fetch_compat(ltdb->idxptr->itdb, key);
+	if (rec.dptr != NULL) {
+		list2 = ltdb_index_idxptr(module, rec, false);
+		if (list2 == NULL) {
+			free(rec.dptr);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		free(rec.dptr);
+		list2->dn = talloc_steal(list2, list->dn);
+		list2->count = list->count;
+		return LDB_SUCCESS;
+	}
+
+	list2 = talloc(ltdb->idxptr, struct dn_list);
+	if (list2 == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	list2->dn = talloc_steal(list2, list->dn);
+	list2->count = list->count;
+
+	rec.dptr = (uint8_t *)&list2;
+	rec.dsize = sizeof(void *);
+
+	ret = tdb_store(ltdb->idxptr->itdb, key, rec, TDB_INSERT);
+	if (ret != 0) {
+		return ltdb_err_map(tdb_error(ltdb->idxptr->itdb));
+	}
+	return LDB_SUCCESS;
+}
+
+/*
+  traverse function for storing the in-memory index entries on disk
+ */
+static int ltdb_index_traverse_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	struct ldb_module *module = state;
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	struct ldb_dn *dn;
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	struct ldb_val v;
+	struct dn_list *list;
+
+	list = ltdb_index_idxptr(module, data, true);
+	if (list == NULL) {
+		ltdb->idxptr->error = LDB_ERR_OPERATIONS_ERROR;
+		return -1;
+	}
+
+	v.data = key.dptr;
+	v.length = strnlen((char *)key.dptr, key.dsize);
+
+	dn = ldb_dn_from_ldb_val(module, ldb, &v);
+	if (dn == NULL) {
+		ldb_asprintf_errstring(ldb, "Failed to parse index key %*.*s as an LDB DN", (int)v.length, (int)v.length, (const char *)v.data);
+		ltdb->idxptr->error = LDB_ERR_OPERATIONS_ERROR;
+		return -1;
+	}
+
+	ltdb->idxptr->error = ltdb_dn_list_store_full(module, dn, list);
+	talloc_free(dn);
+	if (ltdb->idxptr->error != 0) {
+		return -1;
+	}
+	return 0;
+}
+
+/* cleanup the idxptr mode when transaction commits */
+int ltdb_index_transaction_commit(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	int ret;
+
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+
+	ldb_reset_err_string(ldb);
+
+	if (ltdb->idxptr->itdb) {
+		tdb_traverse(ltdb->idxptr->itdb, ltdb_index_traverse_store, module);
+		tdb_close(ltdb->idxptr->itdb);
+	}
+
+	ret = ltdb->idxptr->error;
+	if (ret != LDB_SUCCESS) {
+		if (!ldb_errstring(ldb)) {
+			ldb_set_errstring(ldb, ldb_strerror(ret));
+		}
+		ldb_asprintf_errstring(ldb, "Failed to store index records in transaction commit: %s", ldb_errstring(ldb));
+	}
+
+	talloc_free(ltdb->idxptr);
+	ltdb->idxptr = NULL;
+	return ret;
+}
+
+/* cleanup the idxptr mode when transaction cancels */
+int ltdb_index_transaction_cancel(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	if (ltdb->idxptr && ltdb->idxptr->itdb) {
+		tdb_close(ltdb->idxptr->itdb);
+	}
+	talloc_free(ltdb->idxptr);
+	ltdb->idxptr = NULL;
+	return LDB_SUCCESS;
+}
+
+
+/*
+  return the dn key to be used for an index
+  the caller is responsible for freeing
+*/
+static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
+				     const char *attr, const struct ldb_val *value,
+				     const struct ldb_schema_attribute **ap)
+{
+	struct ldb_dn *ret;
+	struct ldb_val v;
+	const struct ldb_schema_attribute *a;
+	char *attr_folded;
+	int r;
+
+	attr_folded = ldb_attr_casefold(ldb, attr);
+	if (!attr_folded) {
+		return NULL;
+	}
+
+	a = ldb_schema_attribute_by_name(ldb, attr);
+	if (ap) {
+		*ap = a;
+	}
+	r = a->syntax->canonicalise_fn(ldb, ldb, value, &v);
+	if (r != LDB_SUCCESS) {
+		const char *errstr = ldb_errstring(ldb);
+		/* canonicalisation can be refused. For example, 
+		   a attribute that takes wildcards will refuse to canonicalise
+		   if the value contains a wildcard */
+		ldb_asprintf_errstring(ldb, "Failed to create index key for attribute '%s':%s%s%s",
+				       attr, ldb_strerror(r), (errstr?":":""), (errstr?errstr:""));
+		talloc_free(attr_folded);
+		return NULL;
+	}
+	if (ldb_should_b64_encode(ldb, &v)) {
+		char *vstr = ldb_base64_encode(ldb, (char *)v.data, v.length);
+		if (!vstr) {
+			talloc_free(attr_folded);
+			return NULL;
+		}
+		ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s::%s", LTDB_INDEX, attr_folded, vstr);
+		talloc_free(vstr);
+	} else {
+		ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s", LTDB_INDEX, attr_folded, (int)v.length, (char *)v.data);
+	}
+
+	if (v.data != value->data) {
+		talloc_free(v.data);
+	}
+	talloc_free(attr_folded);
+
+	return ret;
+}
+
+/*
+  see if a attribute value is in the list of indexed attributes
+*/
+static bool ltdb_is_indexed(const struct ldb_message *index_list, const char *attr)
+{
+	unsigned int i;
+	struct ldb_message_element *el;
+
+	el = ldb_msg_find_element(index_list, LTDB_IDXATTR);
+	if (el == NULL) {
+		return false;
+	}
+
+	/* TODO: this is too expensive! At least use a binary search */
+	for (i=0; i<el->num_values; i++) {
+		if (ldb_attr_cmp((char *)el->values[i].data, attr) == 0) {
+			return true;
+		}
+	}
+	return false;
+}
+
+/*
+  in the following logic functions, the return value is treated as
+  follows:
+
+     LDB_SUCCESS: we found some matching index values
+
+     LDB_ERR_NO_SUCH_OBJECT: we know for sure that no object matches
+
+     LDB_ERR_OPERATIONS_ERROR: indexing could not answer the call,
+                               we'll need a full search
+ */
+
+/*
+  return a list of dn's that might match a simple indexed search (an
+  equality search only)
+ */
+static int ltdb_index_dn_simple(struct ldb_module *module,
+				const struct ldb_parse_tree *tree,
+				const struct ldb_message *index_list,
+				struct dn_list *list)
+{
+	struct ldb_context *ldb;
+	struct ldb_dn *dn;
+	int ret;
+
+	ldb = ldb_module_get_ctx(module);
+
+	list->count = 0;
+	list->dn = NULL;
+
+	/* if the attribute isn't in the list of indexed attributes then
+	   this node needs a full search */
+	if (!ltdb_is_indexed(index_list, tree->u.equality.attr)) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* the attribute is indexed. Pull the list of DNs that match the 
+	   search criterion */
+	dn = ltdb_index_key(ldb, tree->u.equality.attr, &tree->u.equality.value, NULL);
+	if (!dn) return LDB_ERR_OPERATIONS_ERROR;
+
+	ret = ltdb_dn_list_load(module, dn, list);
+	talloc_free(dn);
+	return ret;
+}
+
+
+static bool list_union(struct ldb_context *, struct dn_list *, const struct dn_list *);
+
+/*
+  return a list of dn's that might match a leaf indexed search
+ */
+static int ltdb_index_dn_leaf(struct ldb_module *module,
+			      const struct ldb_parse_tree *tree,
+			      const struct ldb_message *index_list,
+			      struct dn_list *list)
+{
+	if (ldb_attr_dn(tree->u.equality.attr) == 0) {
+		list->dn = talloc_array(list, struct ldb_val, 1);
+		if (list->dn == NULL) {
+			ldb_module_oom(module);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		list->dn[0] = tree->u.equality.value;
+		list->count = 1;
+		return LDB_SUCCESS;
+	}
+	return ltdb_index_dn_simple(module, tree, index_list, list);
+}
+
+
+/*
+  list intersection
+  list = list & list2
+*/
+static bool list_intersect(struct ldb_context *ldb,
+			   struct dn_list *list, const struct dn_list *list2)
+{
+	struct dn_list *list3;
+	unsigned int i;
+
+	if (list->count == 0) {
+		/* 0 & X == 0 */
+		return true;
+	}
+	if (list2->count == 0) {
+		/* X & 0 == 0 */
+		list->count = 0;
+		list->dn = NULL;
+		return true;
+	}
+
+	/* the indexing code is allowed to return a longer list than
+	   what really matches, as all results are filtered by the
+	   full expression at the end - this shortcut avoids a lot of
+	   work in some cases */
+	if (list->count < 2 && list2->count > 10) {
+		return true;
+	}
+	if (list2->count < 2 && list->count > 10) {
+		list->count = list2->count;
+		list->dn = list2->dn;
+		/* note that list2 may not be the parent of list2->dn,
+		   as list2->dn may be owned by ltdb->idxptr. In that
+		   case we expect this reparent call to fail, which is
+		   OK */
+		talloc_reparent(list2, list, list2->dn);
+		return true;
+	}
+
+	list3 = talloc_zero(list, struct dn_list);
+	if (list3 == NULL) {
+		return false;
+	}
+
+	list3->dn = talloc_array(list3, struct ldb_val, list->count);
+	if (!list3->dn) {
+		talloc_free(list3);
+		return false;
+	}
+	list3->count = 0;
+
+	for (i=0;i<list->count;i++) {
+		if (ltdb_dn_list_find_val(list2, &list->dn[i]) != -1) {
+			list3->dn[list3->count] = list->dn[i];
+			list3->count++;
+		}
+	}
+
+	list->dn = talloc_steal(list, list3->dn);
+	list->count = list3->count;
+	talloc_free(list3);
+
+	return true;
+}
+
+
+/*
+  list union
+  list = list | list2
+*/
+static bool list_union(struct ldb_context *ldb,
+		       struct dn_list *list, const struct dn_list *list2)
+{
+	struct ldb_val *dn3;
+
+	if (list2->count == 0) {
+		/* X | 0 == X */
+		return true;
+	}
+
+	if (list->count == 0) {
+		/* 0 | X == X */
+		list->count = list2->count;
+		list->dn = list2->dn;
+		/* note that list2 may not be the parent of list2->dn,
+		   as list2->dn may be owned by ltdb->idxptr. In that
+		   case we expect this reparent call to fail, which is
+		   OK */
+		talloc_reparent(list2, list, list2->dn);
+		return true;
+	}
+
+	dn3 = talloc_array(list, struct ldb_val, list->count + list2->count);
+	if (!dn3) {
+		ldb_oom(ldb);
+		return false;
+	}
+
+	/* we allow for duplicates here, and get rid of them later */
+	memcpy(dn3, list->dn, sizeof(list->dn[0])*list->count);
+	memcpy(dn3+list->count, list2->dn, sizeof(list2->dn[0])*list2->count);
+
+	list->dn = dn3;
+	list->count += list2->count;
+
+	return true;
+}
+
+static int ltdb_index_dn(struct ldb_module *module,
+			 const struct ldb_parse_tree *tree,
+			 const struct ldb_message *index_list,
+			 struct dn_list *list);
+
+
+/*
+  process an OR list (a union)
+ */
+static int ltdb_index_dn_or(struct ldb_module *module,
+			    const struct ldb_parse_tree *tree,
+			    const struct ldb_message *index_list,
+			    struct dn_list *list)
+{
+	struct ldb_context *ldb;
+	unsigned int i;
+
+	ldb = ldb_module_get_ctx(module);
+
+	list->dn = NULL;
+	list->count = 0;
+
+	for (i=0; i<tree->u.list.num_elements; i++) {
+		struct dn_list *list2;
+		int ret;
+
+		list2 = talloc_zero(list, struct dn_list);
+		if (list2 == NULL) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ret = ltdb_index_dn(module, tree->u.list.elements[i], index_list, list2);
+
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			/* X || 0 == X */
+			talloc_free(list2);
+			continue;
+		}
+
+		if (ret != LDB_SUCCESS) {
+			/* X || * == * */
+			talloc_free(list2);
+			return ret;
+		}
+
+		if (!list_union(ldb, list, list2)) {
+			talloc_free(list2);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+	}
+
+	if (list->count == 0) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  NOT an index results
+ */
+static int ltdb_index_dn_not(struct ldb_module *module,
+			     const struct ldb_parse_tree *tree,
+			     const struct ldb_message *index_list,
+			     struct dn_list *list)
+{
+	/* the only way to do an indexed not would be if we could
+	   negate the not via another not or if we knew the total
+	   number of database elements so we could know that the
+	   existing expression covered the whole database.
+
+	   instead, we just give up, and rely on a full index scan
+	   (unless an outer & manages to reduce the list)
+	*/
+	return LDB_ERR_OPERATIONS_ERROR;
+}
+
+
+static bool ltdb_index_unique(struct ldb_context *ldb,
+			      const char *attr)
+{
+	const struct ldb_schema_attribute *a;
+	a = ldb_schema_attribute_by_name(ldb, attr);
+	if (a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX) {
+		return true;
+	}
+	return false;
+}
+
+/*
+  process an AND expression (intersection)
+ */
+static int ltdb_index_dn_and(struct ldb_module *module,
+			     const struct ldb_parse_tree *tree,
+			     const struct ldb_message *index_list,
+			     struct dn_list *list)
+{
+	struct ldb_context *ldb;
+	unsigned int i;
+	bool found;
+
+	ldb = ldb_module_get_ctx(module);
+
+	list->dn = NULL;
+	list->count = 0;
+
+	/* in the first pass we only look for unique simple
+	   equality tests, in the hope of avoiding having to look
+	   at any others */
+	for (i=0; i<tree->u.list.num_elements; i++) {
+		const struct ldb_parse_tree *subtree = tree->u.list.elements[i];
+		int ret;
+
+		if (subtree->operation != LDB_OP_EQUALITY ||
+		    !ltdb_index_unique(ldb, subtree->u.equality.attr)) {
+			continue;
+		}
+		
+		ret = ltdb_index_dn(module, subtree, index_list, list);
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			/* 0 && X == 0 */
+			return LDB_ERR_NO_SUCH_OBJECT;
+		}
+		if (ret == LDB_SUCCESS) {
+			/* a unique index match means we can
+			 * stop. Note that we don't care if we return
+			 * a few too many objects, due to later
+			 * filtering */
+			return LDB_SUCCESS;
+		}
+	}	
+
+	/* now do a full intersection */
+	found = false;
+
+	for (i=0; i<tree->u.list.num_elements; i++) {
+		const struct ldb_parse_tree *subtree = tree->u.list.elements[i];
+		struct dn_list *list2;
+		int ret;
+
+		list2 = talloc_zero(list, struct dn_list);
+		if (list2 == NULL) {
+			return ldb_module_oom(module);
+		}
+			
+		ret = ltdb_index_dn(module, subtree, index_list, list2);
+
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			/* X && 0 == 0 */
+			list->dn = NULL;
+			list->count = 0;
+			talloc_free(list2);
+			return LDB_ERR_NO_SUCH_OBJECT;
+		}
+		
+		if (ret != LDB_SUCCESS) {
+			/* this didn't adding anything */
+			talloc_free(list2);
+			continue;
+		}
+
+		if (!found) {
+			talloc_reparent(list2, list, list->dn);
+			list->dn = list2->dn;
+			list->count = list2->count;
+			found = true;
+		} else if (!list_intersect(ldb, list, list2)) {
+			talloc_free(list2);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+			
+		if (list->count == 0) {
+			list->dn = NULL;
+			return LDB_ERR_NO_SUCH_OBJECT;
+		}
+			
+		if (list->count < 2) {
+			/* it isn't worth loading the next part of the tree */
+			return LDB_SUCCESS;
+		}
+	}	
+
+	if (!found) {
+		/* none of the attributes were indexed */
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	return LDB_SUCCESS;
+}
+	
+/*
+  return a list of matching objects using a one-level index
+ */
+static int ltdb_index_dn_one(struct ldb_module *module,
+			     struct ldb_dn *parent_dn,
+			     struct dn_list *list)
+{
+	struct ldb_context *ldb;
+	struct ldb_dn *key;
+	struct ldb_val val;
+	int ret;
+
+	ldb = ldb_module_get_ctx(module);
+
+	/* work out the index key from the parent DN */
+	val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(parent_dn));
+	val.length = strlen((char *)val.data);
+	key = ltdb_index_key(ldb, LTDB_IDXONE, &val, NULL);
+	if (!key) {
+		ldb_oom(ldb);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_dn_list_load(module, key, list);
+	talloc_free(key);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	if (list->count == 0) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  return a list of dn's that might match a indexed search or
+  an error. return LDB_ERR_NO_SUCH_OBJECT for no matches, or LDB_SUCCESS for matches
+ */
+static int ltdb_index_dn(struct ldb_module *module,
+			 const struct ldb_parse_tree *tree,
+			 const struct ldb_message *index_list,
+			 struct dn_list *list)
+{
+	int ret = LDB_ERR_OPERATIONS_ERROR;
+
+	switch (tree->operation) {
+	case LDB_OP_AND:
+		ret = ltdb_index_dn_and(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_OR:
+		ret = ltdb_index_dn_or(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_NOT:
+		ret = ltdb_index_dn_not(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_EQUALITY:
+		ret = ltdb_index_dn_leaf(module, tree, index_list, list);
+		break;
+
+	case LDB_OP_SUBSTRING:
+	case LDB_OP_GREATER:
+	case LDB_OP_LESS:
+	case LDB_OP_PRESENT:
+	case LDB_OP_APPROX:
+	case LDB_OP_EXTENDED:
+		/* we can't index with fancy bitops yet */
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		break;
+	}
+
+	return ret;
+}
+
+/*
+  filter a candidate dn_list from an indexed search into a set of results
+  extracting just the given attributes
+*/
+static int ltdb_index_filter(const struct dn_list *dn_list,
+			     struct ltdb_context *ac, 
+			     uint32_t *match_count)
+{
+	struct ldb_context *ldb;
+	struct ldb_message *msg;
+	unsigned int i;
+
+	ldb = ldb_module_get_ctx(ac->module);
+
+	for (i = 0; i < dn_list->count; i++) {
+		struct ldb_dn *dn;
+		int ret;
+		bool matched;
+
+		msg = ldb_msg_new(ac);
+		if (!msg) {
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		dn = ldb_dn_from_ldb_val(msg, ldb, &dn_list->dn[i]);
+		if (dn == NULL) {
+			talloc_free(msg);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ret = ltdb_search_dn1(ac->module, dn, msg);
+		talloc_free(dn);
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			/* the record has disappeared? yes, this can happen */
+			talloc_free(msg);
+			continue;
+		}
+
+		if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+			/* an internal error */
+			talloc_free(msg);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ret = ldb_match_msg_error(ldb, msg,
+					  ac->tree, ac->base, ac->scope, &matched);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(msg);
+			return ret;
+		}
+		if (!matched) {
+			talloc_free(msg);
+			continue;
+		}
+
+		/* filter the attributes that the user wants */
+		ret = ltdb_filter_attrs(msg, ac->attrs);
+
+		if (ret == -1) {
+			talloc_free(msg);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+
+		ret = ldb_module_send_entry(ac->req, msg, NULL);
+		if (ret != LDB_SUCCESS) {
+			/* Regardless of success or failure, the msg
+			 * is the callbacks responsiblity, and should
+			 * not be talloc_free()'ed */
+			ac->request_terminated = true;
+			return ret;
+		}
+
+		(*match_count)++;
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  remove any duplicated entries in a indexed result
+ */
+static void ltdb_dn_list_remove_duplicates(struct dn_list *list)
+{
+	unsigned int i, new_count;
+
+	if (list->count < 2) {
+		return;
+	}
+
+	TYPESAFE_QSORT(list->dn, list->count, dn_list_cmp);
+
+	new_count = 1;
+	for (i=1; i<list->count; i++) {
+		if (dn_list_cmp(&list->dn[i], &list->dn[new_count-1]) != 0) {
+			if (new_count != i) {
+				list->dn[new_count] = list->dn[i];
+			}
+			new_count++;
+		}
+	}
+	
+	list->count = new_count;
+}
+
+/*
+  search the database with a LDAP-like expression using indexes
+  returns -1 if an indexed search is not possible, in which
+  case the caller should call ltdb_search_full()
+*/
+int ltdb_search_indexed(struct ltdb_context *ac, uint32_t *match_count)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(ac->module), struct ltdb_private);
+	struct dn_list *dn_list;
+	int ret;
+
+	/* see if indexing is enabled */
+	if (!ltdb->cache->attribute_indexes && 
+	    !ltdb->cache->one_level_indexes &&
+	    ac->scope != LDB_SCOPE_BASE) {
+		/* fallback to a full search */
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	dn_list = talloc_zero(ac, struct dn_list);
+	if (dn_list == NULL) {
+		return ldb_module_oom(ac->module);
+	}
+
+	switch (ac->scope) {
+	case LDB_SCOPE_BASE:
+		dn_list->dn = talloc_array(dn_list, struct ldb_val, 1);
+		if (dn_list->dn == NULL) {
+			talloc_free(dn_list);
+			return ldb_module_oom(ac->module);
+		}
+		dn_list->dn[0].data = discard_const_p(unsigned char, ldb_dn_get_linearized(ac->base));
+		if (dn_list->dn[0].data == NULL) {
+			talloc_free(dn_list);
+			return ldb_module_oom(ac->module);
+		}
+		dn_list->dn[0].length = strlen((char *)dn_list->dn[0].data);
+		dn_list->count = 1;
+		break;		
+
+	case LDB_SCOPE_ONELEVEL:
+		if (!ltdb->cache->one_level_indexes) {
+			talloc_free(dn_list);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		ret = ltdb_index_dn_one(ac->module, ac->base, dn_list);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(dn_list);
+			return ret;
+		}
+		break;
+
+	case LDB_SCOPE_SUBTREE:
+	case LDB_SCOPE_DEFAULT:
+		if (!ltdb->cache->attribute_indexes) {
+			talloc_free(dn_list);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		ret = ltdb_index_dn(ac->module, ac->tree, ltdb->cache->indexlist, dn_list);
+		if (ret != LDB_SUCCESS) {
+			talloc_free(dn_list);
+			return ret;
+		}
+		ltdb_dn_list_remove_duplicates(dn_list);
+		break;
+	}
+
+	ret = ltdb_index_filter(dn_list, ac, match_count);
+	talloc_free(dn_list);
+	return ret;
+}
+
+/*
+  add an index entry for one message element
+*/
+static int ltdb_index_add1(struct ldb_module *module, const char *dn,
+			   struct ldb_message_element *el, int v_idx)
+{
+	struct ldb_context *ldb;
+	struct ldb_dn *dn_key;
+	int ret;
+	const struct ldb_schema_attribute *a;
+	struct dn_list *list;
+	unsigned alloc_len;
+
+	ldb = ldb_module_get_ctx(module);
+
+	list = talloc_zero(module, struct dn_list);
+	if (list == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx], &a);
+	if (!dn_key) {
+		talloc_free(list);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	talloc_steal(list, dn_key);
+
+	ret = ltdb_dn_list_load(module, dn_key, list);
+	if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+		talloc_free(list);
+		return ret;
+	}
+
+	if (ltdb_dn_list_find_str(list, dn) != -1) {
+		talloc_free(list);
+		return LDB_SUCCESS;
+	}
+
+	if (list->count > 0 &&
+	    a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX) {
+		talloc_free(list);
+		ldb_asprintf_errstring(ldb, __location__ ": unique index violation on %s in %s",
+				       el->name, dn);
+		return LDB_ERR_ENTRY_ALREADY_EXISTS;		
+	}
+
+	/* overallocate the list a bit, to reduce the number of
+	 * realloc trigered copies */	 
+	alloc_len = ((list->count+1)+7) & ~7;
+	list->dn = talloc_realloc(list, list->dn, struct ldb_val, alloc_len);
+	if (list->dn == NULL) {
+		talloc_free(list);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	list->dn[list->count].data = (uint8_t *)talloc_strdup(list->dn, dn);
+	list->dn[list->count].length = strlen(dn);
+	list->count++;
+
+	ret = ltdb_dn_list_store(module, dn_key, list);
+
+	talloc_free(list);
+
+	return ret;
+}
+
+/*
+  add index entries for one elements in a message
+ */
+static int ltdb_index_add_el(struct ldb_module *module, const char *dn,
+			     struct ldb_message_element *el)
+{
+	unsigned int i;
+	for (i = 0; i < el->num_values; i++) {
+		int ret = ltdb_index_add1(module, dn, el, i);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  add index entries for all elements in a message
+ */
+static int ltdb_index_add_all(struct ldb_module *module, const char *dn,
+			      struct ldb_message_element *elements, int num_el)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	unsigned int i;
+
+	if (dn[0] == '@') {
+		return LDB_SUCCESS;
+	}
+
+	if (ltdb->cache->indexlist->num_elements == 0) {
+		/* no indexed fields */
+		return LDB_SUCCESS;
+	}
+
+	for (i = 0; i < num_el; i++) {
+		int ret;
+		if (!ltdb_is_indexed(ltdb->cache->indexlist, elements[i].name)) {
+			continue;
+		}
+		ret = ltdb_index_add_el(module, dn, &elements[i]);
+		if (ret != LDB_SUCCESS) {
+			struct ldb_context *ldb = ldb_module_get_ctx(module);
+			ldb_asprintf_errstring(ldb,
+					       __location__ ": Failed to re-index %s in %s - %s",
+					       elements[i].name, dn, ldb_errstring(ldb));
+			return ret;
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  insert a one level index for a message
+*/
+static int ltdb_index_onelevel(struct ldb_module *module, const struct ldb_message *msg, int add)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	struct ldb_message_element el;
+	struct ldb_val val;
+	struct ldb_dn *pdn;
+	const char *dn;
+	int ret;
+
+	/* We index for ONE Level only if requested */
+	if (!ltdb->cache->one_level_indexes) {
+		return LDB_SUCCESS;
+	}
+
+	pdn = ldb_dn_get_parent(module, msg->dn);
+	if (pdn == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	dn = ldb_dn_get_linearized(msg->dn);
+	if (dn == NULL) {
+		talloc_free(pdn);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(pdn));
+	if (val.data == NULL) {
+		talloc_free(pdn);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	val.length = strlen((char *)val.data);
+	el.name = LTDB_IDXONE;
+	el.values = &val;
+	el.num_values = 1;
+
+	if (add) {
+		ret = ltdb_index_add1(module, dn, &el, 0);
+	} else { /* delete */
+		ret = ltdb_index_del_value(module, msg->dn, &el, 0);
+	}
+
+	talloc_free(pdn);
+
+	return ret;
+}
+
+/*
+  add the index entries for a new element in a record
+  The caller guarantees that these element values are not yet indexed
+*/
+int ltdb_index_add_element(struct ldb_module *module, struct ldb_dn *dn, 
+			   struct ldb_message_element *el)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	if (ldb_dn_is_special(dn)) {
+		return LDB_SUCCESS;
+	}
+	if (!ltdb_is_indexed(ltdb->cache->indexlist, el->name)) {
+		return LDB_SUCCESS;
+	}
+	return ltdb_index_add_el(module, ldb_dn_get_linearized(dn), el);
+}
+
+/*
+  add the index entries for a new record
+*/
+int ltdb_index_add_new(struct ldb_module *module, const struct ldb_message *msg)
+{
+	const char *dn;
+	int ret;
+
+	if (ldb_dn_is_special(msg->dn)) {
+		return LDB_SUCCESS;
+	}
+
+	dn = ldb_dn_get_linearized(msg->dn);
+	if (dn == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_index_add_all(module, dn, msg->elements, msg->num_elements);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	return ltdb_index_onelevel(module, msg, 1);
+}
+
+
+/*
+  delete an index entry for one message element
+*/
+int ltdb_index_del_value(struct ldb_module *module, struct ldb_dn *dn,
+			 struct ldb_message_element *el, unsigned int v_idx)
+{
+	struct ldb_context *ldb;
+	struct ldb_dn *dn_key;
+	const char *dn_str;
+	int ret, i;
+	unsigned int j;
+	struct dn_list *list;
+
+	ldb = ldb_module_get_ctx(module);
+
+	dn_str = ldb_dn_get_linearized(dn);
+	if (dn_str == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (dn_str[0] == '@') {
+		return LDB_SUCCESS;
+	}
+
+	dn_key = ltdb_index_key(ldb, el->name, &el->values[v_idx], NULL);
+	if (!dn_key) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	list = talloc_zero(dn_key, struct dn_list);
+	if (list == NULL) {
+		talloc_free(dn_key);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_dn_list_load(module, dn_key, list);
+	if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+		/* it wasn't indexed. Did we have an earlier error? If we did then
+		   its gone now */
+		talloc_free(dn_key);
+		return LDB_SUCCESS;
+	}
+
+	if (ret != LDB_SUCCESS) {
+		talloc_free(dn_key);
+		return ret;
+	}
+
+	i = ltdb_dn_list_find_str(list, dn_str);
+	if (i == -1) {
+		/* nothing to delete */
+		talloc_free(dn_key);
+		return LDB_SUCCESS;		
+	}
+
+	j = (unsigned int) i;
+	if (j != list->count - 1) {
+		memmove(&list->dn[j], &list->dn[j+1], sizeof(list->dn[0])*(list->count - (j+1)));
+	}
+	list->count--;
+	list->dn = talloc_realloc(list, list->dn, struct ldb_val, list->count);
+
+	ret = ltdb_dn_list_store(module, dn_key, list);
+
+	talloc_free(dn_key);
+
+	return ret;
+}
+
+/*
+  delete the index entries for a element
+  return -1 on failure
+*/
+int ltdb_index_del_element(struct ldb_module *module, struct ldb_dn *dn,
+			   struct ldb_message_element *el)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	const char *dn_str;
+	int ret;
+	unsigned int i;
+
+	if (!ltdb->cache->attribute_indexes) {
+		/* no indexed fields */
+		return LDB_SUCCESS;
+	}
+
+	dn_str = ldb_dn_get_linearized(dn);
+	if (dn_str == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (dn_str[0] == '@') {
+		return LDB_SUCCESS;
+	}
+
+	if (!ltdb_is_indexed(ltdb->cache->indexlist, el->name)) {
+		return LDB_SUCCESS;
+	}
+	for (i = 0; i < el->num_values; i++) {
+		ret = ltdb_index_del_value(module, dn, el, i);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  delete the index entries for a record
+  return -1 on failure
+*/
+int ltdb_index_delete(struct ldb_module *module, const struct ldb_message *msg)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	int ret;
+	unsigned int i;
+
+	if (ldb_dn_is_special(msg->dn)) {
+		return LDB_SUCCESS;
+	}
+
+	ret = ltdb_index_onelevel(module, msg, 0);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	if (!ltdb->cache->attribute_indexes) {
+		/* no indexed fields */
+		return LDB_SUCCESS;
+	}
+
+	for (i = 0; i < msg->num_elements; i++) {
+		ret = ltdb_index_del_element(module, msg->dn, &msg->elements[i]);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  traversal function that deletes all @INDEX records
+*/
+static int delete_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	struct ldb_module *module = state;
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	const char *dnstr = "DN=" LTDB_INDEX ":";
+	struct dn_list list;
+	struct ldb_dn *dn;
+	struct ldb_val v;
+	int ret;
+
+	if (strncmp((char *)key.dptr, dnstr, strlen(dnstr)) != 0) {
+		return 0;
+	}
+	/* we need to put a empty list in the internal tdb for this
+	 * index entry */
+	list.dn = NULL;
+	list.count = 0;
+
+	/* the offset of 3 is to remove the DN= prefix. */
+	v.data = key.dptr + 3;
+	v.length = strnlen((char *)key.dptr, key.dsize) - 3;
+
+	dn = ldb_dn_from_ldb_val(ltdb, ldb_module_get_ctx(module), &v);
+	ret = ltdb_dn_list_store(module, dn, &list);
+	if (ret != LDB_SUCCESS) {
+		ldb_asprintf_errstring(ldb_module_get_ctx(module), 
+				       "Unable to store null index for %s\n",
+						ldb_dn_get_linearized(dn));
+		talloc_free(dn);
+		return -1;
+	}
+	talloc_free(dn);
+	return 0;
+}
+
+struct ltdb_reindex_context {
+	struct ldb_module *module;
+	int error;
+};
+
+/*
+  traversal function that adds @INDEX records during a re index
+*/
+static int re_index(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	struct ldb_context *ldb;
+	struct ltdb_reindex_context *ctx = (struct ltdb_reindex_context *)state;
+	struct ldb_module *module = ctx->module;
+	struct ldb_message *msg;
+	const char *dn = NULL;
+	int ret;
+	TDB_DATA key2;
+
+	ldb = ldb_module_get_ctx(module);
+
+	if (strncmp((char *)key.dptr, "DN=@", 4) == 0 ||
+	    strncmp((char *)key.dptr, "DN=", 3) != 0) {
+		return 0;
+	}
+
+	msg = ldb_msg_new(module);
+	if (msg == NULL) {
+		return -1;
+	}
+
+	ret = ltdb_unpack_data(module, &data, msg);
+	if (ret != 0) {
+		ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid data for index %s\n",
+						ldb_dn_get_linearized(msg->dn));
+		talloc_free(msg);
+		return -1;
+	}
+
+	/* check if the DN key has changed, perhaps due to the
+	   case insensitivity of an element changing */
+	key2 = ltdb_key(module, msg->dn);
+	if (key2.dptr == NULL) {
+		/* probably a corrupt record ... darn */
+		ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid DN in re_index: %s",
+						ldb_dn_get_linearized(msg->dn));
+		talloc_free(msg);
+		return 0;
+	}
+	if (strcmp((char *)key2.dptr, (char *)key.dptr) != 0) {
+		tdb_delete(tdb, key);
+		tdb_store(tdb, key2, data, 0);
+	}
+	talloc_free(key2.dptr);
+
+	if (msg->dn == NULL) {
+		dn = (char *)key.dptr + 3;
+	} else {
+		dn = ldb_dn_get_linearized(msg->dn);
+	}
+
+	ret = ltdb_index_onelevel(module, msg, 1);
+	if (ret != LDB_SUCCESS) {
+		ldb_debug(ldb, LDB_DEBUG_ERROR,
+			  "Adding special ONE LEVEL index failed (%s)!",
+						ldb_dn_get_linearized(msg->dn));
+		talloc_free(msg);
+		return -1;
+	}
+
+	ret = ltdb_index_add_all(module, dn, msg->elements, msg->num_elements);
+
+	if (ret != LDB_SUCCESS) {
+		ctx->error = ret;
+		talloc_free(msg);
+		return -1;
+	}
+
+	talloc_free(msg);
+
+	return 0;
+}
+
+/*
+  force a complete reindex of the database
+*/
+int ltdb_reindex(struct ldb_module *module)
+{
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+	int ret;
+	struct ltdb_reindex_context ctx;
+
+	if (ltdb_cache_reload(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* first traverse the database deleting any @INDEX records by
+	 * putting NULL entries in the in-memory tdb
+	 */
+	ret = tdb_traverse(ltdb->tdb, delete_index, module);
+	if (ret < 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* if we don't have indexes we have nothing todo */
+	if (ltdb->cache->indexlist->num_elements == 0) {
+		return LDB_SUCCESS;
+	}
+
+	ctx.module = module;
+	ctx.error = 0;
+
+	/* now traverse adding any indexes for normal LDB records */
+	ret = tdb_traverse(ltdb->tdb, re_index, &ctx);
+	if (ret < 0) {
+		struct ldb_context *ldb = ldb_module_get_ctx(module);
+		ldb_asprintf_errstring(ldb, "reindexing traverse failed: %s", ldb_errstring(ldb));
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (ctx.error != LDB_SUCCESS) {
+		struct ldb_context *ldb = ldb_module_get_ctx(module);
+		ldb_asprintf_errstring(ldb, "reindexing failed: %s", ldb_errstring(ldb));
+		return ctx.error;
+	}
+
+	return LDB_SUCCESS;
+}
diff --git a/lib/ldb/ldb_tdb/ldb_pack.c b/lib/ldb/ldb_tdb/ldb_pack.c
new file mode 100644
index 0000000000..7c13065aee
--- /dev/null
+++ b/lib/ldb/ldb_tdb/ldb_pack.c
@@ -0,0 +1,292 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+
+     ** 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 3 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, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb pack/unpack
+ *
+ *  Description: pack/unpack routines for ldb messages as key/value blobs
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_tdb.h"
+
+/* change this if the data format ever changes */
+#define LTDB_PACKING_FORMAT 0x26011967
+
+/* old packing formats */
+#define LTDB_PACKING_FORMAT_NODN 0x26011966
+
+/* use a portable integer format */
+static void put_uint32(uint8_t *p, int ofs, unsigned int val)
+{
+	p += ofs;
+	p[0] = val&0xFF;
+	p[1] = (val>>8)  & 0xFF;
+	p[2] = (val>>16) & 0xFF;
+	p[3] = (val>>24) & 0xFF;
+}
+
+static unsigned int pull_uint32(uint8_t *p, int ofs)
+{
+	p += ofs;
+	return p[0] | (p[1]<<8) | (p[2]<<16) | (p[3]<<24);
+}
+
+static int attribute_storable_values(const struct ldb_message_element *el)
+{
+	if (el->num_values == 0) return 0;
+
+	if (ldb_attr_cmp(el->name, "distinguishedName") == 0) return 0;
+
+	return el->num_values;
+}
+
+/*
+  pack a ldb message into a linear buffer in a TDB_DATA
+
+  note that this routine avoids saving elements with zero values,
+  as these are equivalent to having no element
+
+  caller frees the data buffer after use
+*/
+int ltdb_pack_data(struct ldb_module *module,
+		   const struct ldb_message *message,
+		   TDB_DATA *data)
+{
+	struct ldb_context *ldb;
+	unsigned int i, j, real_elements=0;
+	size_t size;
+	const char *dn;
+	uint8_t *p;
+	size_t len;
+
+	ldb = ldb_module_get_ctx(module);
+
+	dn = ldb_dn_get_linearized(message->dn);
+	if (dn == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	/* work out how big it needs to be */
+	size = 8;
+
+	size += 1 + strlen(dn);
+
+	for (i=0;i<message->num_elements;i++) {
+		if (attribute_storable_values(&message->elements[i]) == 0) {
+			continue;
+		}
+
+		real_elements++;
+
+		size += 1 + strlen(message->elements[i].name) + 4;
+		for (j=0;j<message->elements[i].num_values;j++) {
+			size += 4 + message->elements[i].values[j].length + 1;
+		}
+	}
+
+	/* allocate it */
+	data->dptr = talloc_array(ldb, uint8_t, size);
+	if (!data->dptr) {
+		errno = ENOMEM;
+		return -1;
+	}
+	data->dsize = size;
+
+	p = data->dptr;
+	put_uint32(p, 0, LTDB_PACKING_FORMAT); 
+	put_uint32(p, 4, real_elements); 
+	p += 8;
+
+	/* the dn needs to be packed so we can be case preserving
+	   while hashing on a case folded dn */
+	len = strlen(dn);
+	memcpy(p, dn, len+1);
+	p += len + 1;
+	
+	for (i=0;i<message->num_elements;i++) {
+		if (attribute_storable_values(&message->elements[i]) == 0) {
+			continue;
+		}
+		len = strlen(message->elements[i].name);
+		memcpy(p, message->elements[i].name, len+1);
+		p += len + 1;
+		put_uint32(p, 0, message->elements[i].num_values);
+		p += 4;
+		for (j=0;j<message->elements[i].num_values;j++) {
+			put_uint32(p, 0, message->elements[i].values[j].length);
+			memcpy(p+4, message->elements[i].values[j].data, 
+			       message->elements[i].values[j].length);
+			p[4+message->elements[i].values[j].length] = 0;
+			p += 4 + message->elements[i].values[j].length + 1;
+		}
+	}
+
+	return 0;
+}
+
+/*
+  unpack a ldb message from a linear buffer in TDB_DATA
+
+  Free with ltdb_unpack_data_free()
+*/
+int ltdb_unpack_data(struct ldb_module *module,
+		     const TDB_DATA *data,
+		     struct ldb_message *message)
+{
+	struct ldb_context *ldb;
+	uint8_t *p;
+	unsigned int remaining;
+	unsigned int i, j;
+	unsigned format;
+	size_t len;
+
+	ldb = ldb_module_get_ctx(module);
+	message->elements = NULL;
+
+	p = data->dptr;
+	if (data->dsize < 8) {
+		errno = EIO;
+		goto failed;
+	}
+
+	format = pull_uint32(p, 0);
+	message->num_elements = pull_uint32(p, 4);
+	p += 8;
+
+	remaining = data->dsize - 8;
+
+	switch (format) {
+	case LTDB_PACKING_FORMAT_NODN:
+		message->dn = NULL;
+		break;
+
+	case LTDB_PACKING_FORMAT:
+		len = strnlen((char *)p, remaining);
+		if (len == remaining) {
+			errno = EIO;
+			goto failed;
+		}
+		message->dn = ldb_dn_new(message, ldb, (char *)p);
+		if (message->dn == NULL) {
+			errno = ENOMEM;
+			goto failed;
+		}
+		remaining -= len + 1;
+		p += len + 1;
+		break;
+
+	default:
+		errno = EIO;
+		goto failed;
+	}
+
+	if (message->num_elements == 0) {
+		return 0;
+	}
+	
+	if (message->num_elements > remaining / 6) {
+		errno = EIO;
+		goto failed;
+	}
+
+	message->elements = talloc_array(message, struct ldb_message_element, message->num_elements);
+	if (!message->elements) {
+		errno = ENOMEM;
+		goto failed;
+	}
+
+	memset(message->elements, 0, 
+	       message->num_elements * sizeof(struct ldb_message_element));
+
+	for (i=0;i<message->num_elements;i++) {
+		if (remaining < 10) {
+			errno = EIO;
+			goto failed;
+		}
+		len = strnlen((char *)p, remaining-6);
+		if (len == remaining-6) {
+			errno = EIO;
+			goto failed;
+		}
+		if (len == 0) {
+			errno = EIO;
+			goto failed;
+		}
+		message->elements[i].flags = 0;
+		message->elements[i].name = talloc_strndup(message->elements, (char *)p, len);
+		if (message->elements[i].name == NULL) {
+			errno = ENOMEM;
+			goto failed;
+		}
+		remaining -= len + 1;
+		p += len + 1;
+		message->elements[i].num_values = pull_uint32(p, 0);
+		message->elements[i].values = NULL;
+		if (message->elements[i].num_values != 0) {
+			message->elements[i].values = talloc_array(message->elements,
+								     struct ldb_val, 
+								     message->elements[i].num_values);
+			if (!message->elements[i].values) {
+				errno = ENOMEM;
+				goto failed;
+			}
+		}
+		p += 4;
+		remaining -= 4;
+		for (j=0;j<message->elements[i].num_values;j++) {
+			len = pull_uint32(p, 0);
+			if (len > remaining-5) {
+				errno = EIO;
+				goto failed;
+			}
+
+			message->elements[i].values[j].length = len;
+			message->elements[i].values[j].data = talloc_size(message->elements[i].values, len+1);
+			if (message->elements[i].values[j].data == NULL) {
+				errno = ENOMEM;
+				goto failed;
+			}
+			memcpy(message->elements[i].values[j].data, p+4, len);
+			message->elements[i].values[j].data[len] = 0;
+	
+			remaining -= len+4+1;
+			p += len+4+1;
+		}
+	}
+
+	if (remaining != 0) {
+		ldb_debug(ldb, LDB_DEBUG_ERROR, 
+			  "Error: %d bytes unread in ltdb_unpack_data", remaining);
+	}
+
+	return 0;
+
+failed:
+	talloc_free(message->elements);
+	return -1;
+}
diff --git a/lib/ldb/ldb_tdb/ldb_search.c b/lib/ldb/ldb_tdb/ldb_search.c
new file mode 100644
index 0000000000..46e2d74998
--- /dev/null
+++ b/lib/ldb/ldb_tdb/ldb_search.c
@@ -0,0 +1,618 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  2004
+
+     ** 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 3 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, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb
+ *
+ *  Component: ldb search functions
+ *
+ *  Description: functions to search ldb+tdb databases
+ *
+ *  Author: Andrew Tridgell
+ */
+
+#include "ldb_tdb.h"
+#include <lib/tdb_compat/tdb_compat.h>
+
+/*
+  add one element to a message
+*/
+static int msg_add_element(struct ldb_message *ret, 
+			   const struct ldb_message_element *el,
+			   int check_duplicates)
+{
+	unsigned int i;
+	struct ldb_message_element *e2, *elnew;
+
+	if (check_duplicates && ldb_msg_find_element(ret, el->name)) {
+		/* its already there */
+		return 0;
+	}
+
+	e2 = talloc_realloc(ret, ret->elements, struct ldb_message_element, ret->num_elements+1);
+	if (!e2) {
+		return -1;
+	}
+	ret->elements = e2;
+	
+	elnew = &e2[ret->num_elements];
+
+	elnew->name = talloc_strdup(ret->elements, el->name);
+	if (!elnew->name) {
+		return -1;
+	}
+
+	if (el->num_values) {
+		elnew->values = talloc_array(ret->elements, struct ldb_val, el->num_values);
+		if (!elnew->values) {
+			return -1;
+		}
+	} else {
+		elnew->values = NULL;
+	}
+
+	for (i=0;i<el->num_values;i++) {
+		elnew->values[i] = ldb_val_dup(elnew->values, &el->values[i]);
+		if (elnew->values[i].length != el->values[i].length) {
+			return -1;
+		}
+	}
+
+	elnew->num_values = el->num_values;
+	elnew->flags = el->flags;
+
+	ret->num_elements++;
+
+	return 0;
+}
+
+/*
+  add the special distinguishedName element
+*/
+static int msg_add_distinguished_name(struct ldb_message *msg)
+{
+	struct ldb_message_element el;
+	struct ldb_val val;
+	int ret;
+
+	el.flags = 0;
+	el.name = "distinguishedName";
+	el.num_values = 1;
+	el.values = &val;
+	el.flags = 0;
+	val.data = (uint8_t *)ldb_dn_alloc_linearized(msg, msg->dn);
+	val.length = strlen((char *)val.data);
+	
+	ret = msg_add_element(msg, &el, 1);
+	return ret;
+}
+
+/*
+  add all elements from one message into another
+ */
+static int msg_add_all_elements(struct ldb_module *module, struct ldb_message *ret,
+				const struct ldb_message *msg)
+{
+	struct ldb_context *ldb;
+	unsigned int i;
+	int check_duplicates = (ret->num_elements != 0);
+
+	ldb = ldb_module_get_ctx(module);
+
+	if (msg_add_distinguished_name(ret) != 0) {
+		return -1;
+	}
+
+	for (i=0;i<msg->num_elements;i++) {
+		const struct ldb_schema_attribute *a;
+		a = ldb_schema_attribute_by_name(ldb, msg->elements[i].name);
+		if (a->flags & LDB_ATTR_FLAG_HIDDEN) {
+			continue;
+		}
+		if (msg_add_element(ret, &msg->elements[i],
+				    check_duplicates) != 0) {
+			return -1;
+		}
+	}
+
+	return 0;
+}
+
+
+/*
+  pull the specified list of attributes from a message
+ */
+static struct ldb_message *ltdb_pull_attrs(struct ldb_module *module, 
+					   TALLOC_CTX *mem_ctx, 
+					   const struct ldb_message *msg, 
+					   const char * const *attrs)
+{
+	struct ldb_message *ret;
+	unsigned int i;
+
+	ret = talloc(mem_ctx, struct ldb_message);
+	if (!ret) {
+		return NULL;
+	}
+
+	ret->dn = ldb_dn_copy(ret, msg->dn);
+	if (!ret->dn) {
+		talloc_free(ret);
+		return NULL;
+	}
+
+	ret->num_elements = 0;
+	ret->elements = NULL;
+
+	if (!attrs) {
+		if (msg_add_all_elements(module, ret, msg) != 0) {
+			talloc_free(ret);
+			return NULL;
+		}
+		return ret;
+	}
+
+	for (i=0;attrs[i];i++) {
+		struct ldb_message_element *el;
+
+		if (strcmp(attrs[i], "*") == 0) {
+			if (msg_add_all_elements(module, ret, msg) != 0) {
+				talloc_free(ret);
+				return NULL;
+			}
+			continue;
+		}
+
+		if (ldb_attr_cmp(attrs[i], "distinguishedName") == 0) {
+			if (msg_add_distinguished_name(ret) != 0) {
+				return NULL;
+			}
+			continue;
+		}
+
+		el = ldb_msg_find_element(msg, attrs[i]);
+		if (!el) {
+			continue;
+		}
+		if (msg_add_element(ret, el, 1) != 0) {
+			talloc_free(ret);
+			return NULL;				
+		}
+	}
+
+	return ret;
+}
+
+/*
+  search the database for a single simple dn.
+  return LDB_ERR_NO_SUCH_OBJECT on record-not-found
+  and LDB_SUCCESS on success
+*/
+static int ltdb_search_base(struct ldb_module *module, struct ldb_dn *dn)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	TDB_DATA tdb_key, tdb_data;
+
+	if (ldb_dn_is_null(dn)) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+
+	/* form the key */
+	tdb_key = ltdb_key(module, dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	tdb_data = tdb_fetch_compat(ltdb->tdb, tdb_key);
+	talloc_free(tdb_key.dptr);
+	if (!tdb_data.dptr) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+	
+	free(tdb_data.dptr);
+	return LDB_SUCCESS;
+}
+
+/*
+  search the database for a single simple dn, returning all attributes
+  in a single message
+
+  return LDB_ERR_NO_SUCH_OBJECT on record-not-found
+  and LDB_SUCCESS on success
+*/
+int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_message *msg)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	int ret;
+	TDB_DATA tdb_key, tdb_data;
+
+	memset(msg, 0, sizeof(*msg));
+
+	/* form the key */
+	tdb_key = ltdb_key(module, dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	tdb_data = tdb_fetch_compat(ltdb->tdb, tdb_key);
+	talloc_free(tdb_key.dptr);
+	if (!tdb_data.dptr) {
+		return LDB_ERR_NO_SUCH_OBJECT;
+	}
+	
+	msg->num_elements = 0;
+	msg->elements = NULL;
+
+	ret = ltdb_unpack_data(module, &tdb_data, msg);
+	free(tdb_data.dptr);
+	if (ret == -1) {
+		struct ldb_context *ldb = ldb_module_get_ctx(module);
+		ldb_debug(ldb, LDB_DEBUG_ERROR, "Invalid data for index %s\n",
+			  ldb_dn_get_linearized(msg->dn));
+		return LDB_ERR_OPERATIONS_ERROR;		
+	}
+
+	if (!msg->dn) {
+		msg->dn = ldb_dn_copy(msg, dn);
+	}
+	if (!msg->dn) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  add a set of attributes from a record to a set of results
+  return 0 on success, -1 on failure
+*/
+int ltdb_add_attr_results(struct ldb_module *module, 
+			  TALLOC_CTX *mem_ctx, 
+			  struct ldb_message *msg,
+			  const char * const attrs[], 
+			  unsigned int *count, 
+			  struct ldb_message ***res)
+{
+	struct ldb_message *msg2;
+	struct ldb_message **res2;
+
+	/* pull the attributes that the user wants */
+	msg2 = ltdb_pull_attrs(module, mem_ctx, msg, attrs);
+	if (!msg2) {
+		return -1;
+	}
+
+	/* add to the results list */
+	res2 = talloc_realloc(mem_ctx, *res, struct ldb_message *, (*count)+2);
+	if (!res2) {
+		talloc_free(msg2);
+		return -1;
+	}
+
+	(*res) = res2;
+
+	(*res)[*count] = talloc_move(*res, &msg2);
+	(*res)[(*count)+1] = NULL;
+	(*count)++;
+
+	return 0;
+}
+
+
+
+/*
+  filter the specified list of attributes from a message
+  removing not requested attrs.
+ */
+int ltdb_filter_attrs(struct ldb_message *msg, const char * const *attrs)
+{
+	unsigned int i;
+	int keep_all = 0;
+	struct ldb_message_element *el2;
+	uint32_t num_elements;
+
+	if (attrs) {
+		/* check for special attrs */
+		for (i = 0; attrs[i]; i++) {
+			if (strcmp(attrs[i], "*") == 0) {
+				keep_all = 1;
+				break;
+			}
+
+			if (ldb_attr_cmp(attrs[i], "distinguishedName") == 0) {
+				if (msg_add_distinguished_name(msg) != 0) {
+					return -1;
+				}
+			}
+		}
+	} else {
+		keep_all = 1;
+	}
+	
+	if (keep_all) {
+		if (msg_add_distinguished_name(msg) != 0) {
+			return -1;
+		}
+		return 0;
+	}
+
+	el2 = talloc_array(msg, struct ldb_message_element, msg->num_elements);
+	if (el2 == NULL) {
+		return -1;
+	}
+	num_elements = 0;
+
+	for (i = 0; i < msg->num_elements; i++) {
+		unsigned int j;
+		int found = 0;
+		
+		for (j = 0; attrs[j]; j++) {
+			if (ldb_attr_cmp(msg->elements[i].name, attrs[j]) == 0) {
+				found = 1;
+				break;
+			}
+		}
+
+		if (found) {
+			el2[num_elements] = msg->elements[i];
+			talloc_steal(el2, el2[num_elements].name);
+			talloc_steal(el2, el2[num_elements].values);
+			num_elements++;
+		}
+	}
+
+	talloc_free(msg->elements);
+	msg->elements = talloc_realloc(msg, el2, struct ldb_message_element, msg->num_elements);
+	if (msg->elements == NULL) {
+		return -1;
+	}
+	msg->num_elements = num_elements;
+
+	return 0;
+}
+
+/*
+  search function for a non-indexed search
+ */
+static int search_func(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, void *state)
+{
+	struct ldb_context *ldb;
+	struct ltdb_context *ac;
+	struct ldb_message *msg;
+	int ret;
+	bool matched;
+
+	ac = talloc_get_type(state, struct ltdb_context);
+	ldb = ldb_module_get_ctx(ac->module);
+
+	if (key.dsize < 4 || 
+	    strncmp((char *)key.dptr, "DN=", 3) != 0) {
+		return 0;
+	}
+
+	msg = ldb_msg_new(ac);
+	if (!msg) {
+		return -1;
+	}
+
+	/* unpack the record */
+	ret = ltdb_unpack_data(ac->module, &data, msg);
+	if (ret == -1) {
+		talloc_free(msg);
+		return -1;
+	}
+
+	if (!msg->dn) {
+		msg->dn = ldb_dn_new(msg, ldb,
+				     (char *)key.dptr + 3);
+		if (msg->dn == NULL) {
+			talloc_free(msg);
+			return -1;
+		}
+	}
+
+	/* see if it matches the given expression */
+	ret = ldb_match_msg_error(ldb, msg,
+				  ac->tree, ac->base, ac->scope, &matched);
+	if (ret != LDB_SUCCESS) {
+		talloc_free(msg);
+		return -1;
+	}
+	if (!matched) {
+		talloc_free(msg);
+		return 0;
+	}
+
+	/* filter the attributes that the user wants */
+	ret = ltdb_filter_attrs(msg, ac->attrs);
+
+	if (ret == -1) {
+		talloc_free(msg);
+		return -1;
+	}
+
+	ret = ldb_module_send_entry(ac->req, msg, NULL);
+	if (ret != LDB_SUCCESS) {
+		ac->request_terminated = true;
+		/* the callback failed, abort the operation */
+		return -1;
+	}
+
+	return 0;
+}
+
+
+/*
+  search the database with a LDAP-like expression.
+  this is the "full search" non-indexed variant
+*/
+static int ltdb_search_full(struct ltdb_context *ctx)
+{
+	void *data = ldb_module_get_private(ctx->module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	int ret;
+
+	if (ltdb->in_transaction != 0) {
+		ret = tdb_traverse(ltdb->tdb, search_func, ctx);
+	} else {
+		ret = tdb_traverse_read(ltdb->tdb, search_func, ctx);
+	}
+
+	if (ret < 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	return LDB_SUCCESS;
+}
+
+/*
+  search the database with a LDAP-like expression.
+  choses a search method
+*/
+int ltdb_search(struct ltdb_context *ctx)
+{
+	struct ldb_context *ldb;
+	struct ldb_module *module = ctx->module;
+	struct ldb_request *req = ctx->req;
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	int ret;
+
+	ldb = ldb_module_get_ctx(module);
+
+	ldb_request_set_state(req, LDB_ASYNC_PENDING);
+
+	if (ltdb_lock_read(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (ltdb_cache_load(module) != 0) {
+		ltdb_unlock_read(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (req->op.search.tree == NULL) {
+		ltdb_unlock_read(module);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if ((req->op.search.base == NULL) || (ldb_dn_is_null(req->op.search.base) == true)) {
+
+		/* Check what we should do with a NULL dn */
+		switch (req->op.search.scope) {
+		case LDB_SCOPE_BASE:
+			ldb_asprintf_errstring(ldb, 
+					       "NULL Base DN invalid for a base search");
+			ret = LDB_ERR_INVALID_DN_SYNTAX;
+			break;
+		case LDB_SCOPE_ONELEVEL:
+			ldb_asprintf_errstring(ldb, 
+					       "NULL Base DN invalid for a one-level search");
+			ret = LDB_ERR_INVALID_DN_SYNTAX;	
+			break;
+		case LDB_SCOPE_SUBTREE:
+		default:
+			/* We accept subtree searches from a NULL base DN, ie over the whole DB */
+			ret = LDB_SUCCESS;
+		}
+	} else if (ldb_dn_is_valid(req->op.search.base) == false) {
+
+		/* We don't want invalid base DNs here */
+		ldb_asprintf_errstring(ldb, 
+				       "Invalid Base DN: %s", 
+				       ldb_dn_get_linearized(req->op.search.base));
+		ret = LDB_ERR_INVALID_DN_SYNTAX;
+
+	} else if (ltdb->check_base) {
+		/* This database has been marked as 'checkBaseOnSearch', so do a spot check of the base dn */
+		ret = ltdb_search_base(module, req->op.search.base);
+		
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			ldb_asprintf_errstring(ldb, 
+					       "No such Base DN: %s", 
+					       ldb_dn_get_linearized(req->op.search.base));
+		}
+			
+	} else {
+		/* If we are not checking the base DN life is easy */
+		ret = LDB_SUCCESS;
+	}
+
+	ctx->tree = req->op.search.tree;
+	ctx->scope = req->op.search.scope;
+	ctx->base = req->op.search.base;
+	ctx->attrs = req->op.search.attrs;
+
+	if (ret == LDB_SUCCESS) {
+		uint32_t match_count = 0;
+
+		ret = ltdb_search_indexed(ctx, &match_count);
+		if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+			/* Not in the index, therefore OK! */
+			ret = LDB_SUCCESS;
+			
+		}
+		/* Check if we got just a normal error.
+		 * In that case proceed to a full search unless we got a
+		 * callback error */
+		if ( ! ctx->request_terminated && ret != LDB_SUCCESS) {
+			/* Not indexed, so we need to do a full scan */
+			if (ltdb->warn_unindexed) {
+				/* useful for debugging when slow performance
+				 * is caused by unindexed searches */
+				char *expression = ldb_filter_from_tree(ctx, ctx->tree);
+				ldb_debug(ldb, LDB_DEBUG_WARNING, "ldb FULL SEARCH: %s SCOPE: %s DN: %s\n",
+							expression,
+							req->op.search.scope==LDB_SCOPE_BASE?"base":
+							req->op.search.scope==LDB_SCOPE_ONELEVEL?"one":
+							req->op.search.scope==LDB_SCOPE_SUBTREE?"sub":"UNKNOWN",
+							ldb_dn_get_linearized(req->op.search.base));
+
+				talloc_free(expression);
+			}
+			if (match_count != 0) {
+				/* the indexing code gave an error
+				 * after having returned at least one
+				 * entry. This means the indexes are
+				 * corrupt or a database record is
+				 * corrupt. We cannot continue with a
+				 * full search or we may return
+				 * duplicate entries
+				 */
+				ltdb_unlock_read(module);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			ret = ltdb_search_full(ctx);
+			if (ret != LDB_SUCCESS) {
+				ldb_set_errstring(ldb, "Indexed and full searches both failed!\n");
+			}
+		}
+	}
+
+	ltdb_unlock_read(module);
+
+	return ret;
+}
+
diff --git a/lib/ldb/ldb_tdb/ldb_tdb.c b/lib/ldb/ldb_tdb/ldb_tdb.c
new file mode 100644
index 0000000000..0d4be49123
--- /dev/null
+++ b/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -0,0 +1,1519 @@
+/*
+   ldb database library
+
+   Copyright (C) Andrew Tridgell 2004
+   Copyright (C) Stefan Metzmacher 2004
+   Copyright (C) Simo Sorce 2006-2008
+   Copyright (C) Matthias Dieter Wallnöfer 2009-2010
+
+     ** 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 3 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, see <http://www.gnu.org/licenses/>.
+*/
+
+/*
+ *  Name: ldb_tdb
+ *
+ *  Component: ldb tdb backend
+ *
+ *  Description: core functions for tdb backend
+ *
+ *  Author: Andrew Tridgell
+ *  Author: Stefan Metzmacher
+ *
+ *  Modifications:
+ *
+ *  - description: make the module use asynchronous calls
+ *    date: Feb 2006
+ *    Author: Simo Sorce
+ *
+ *  - description: make it possible to use event contexts
+ *    date: Jan 2008
+ *    Author: Simo Sorce
+ *
+ *  - description: fix up memory leaks and small bugs
+ *    date: Oct 2009
+ *    Author: Matthias Dieter Wallnöfer
+ */
+
+#include "ldb_tdb.h"
+#include <lib/tdb_compat/tdb_compat.h>
+
+
+/*
+  map a tdb error code to a ldb error code
+*/
+int ltdb_err_map(enum TDB_ERROR tdb_code)
+{
+	switch (tdb_code) {
+	case TDB_SUCCESS:
+		return LDB_SUCCESS;
+	case TDB_ERR_CORRUPT:
+	case TDB_ERR_OOM:
+	case TDB_ERR_EINVAL:
+		return LDB_ERR_OPERATIONS_ERROR;
+	case TDB_ERR_IO:
+		return LDB_ERR_PROTOCOL_ERROR;
+	case TDB_ERR_LOCK:
+#ifndef BUILD_TDB2
+	case TDB_ERR_NOLOCK:
+#endif
+		return LDB_ERR_BUSY;
+#ifndef BUILD_TDB2
+	case TDB_ERR_LOCK_TIMEOUT:
+#endif
+		return LDB_ERR_TIME_LIMIT_EXCEEDED;
+	case TDB_ERR_EXISTS:
+		return LDB_ERR_ENTRY_ALREADY_EXISTS;
+	case TDB_ERR_NOEXIST:
+		return LDB_ERR_NO_SUCH_OBJECT;
+	case TDB_ERR_RDONLY:
+		return LDB_ERR_INSUFFICIENT_ACCESS_RIGHTS;
+	default:
+		break;
+	}
+	return LDB_ERR_OTHER;
+}
+
+/*
+  lock the database for read - use by ltdb_search and ltdb_sequence_number
+*/
+int ltdb_lock_read(struct ldb_module *module)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	int ret = 0;
+
+	if (ltdb->in_transaction == 0 &&
+	    ltdb->read_lock_count == 0) {
+		ret = tdb_lockall_read(ltdb->tdb);
+	}
+	if (ret == 0) {
+		ltdb->read_lock_count++;
+	}
+	return ret;
+}
+
+/*
+  unlock the database after a ltdb_lock_read()
+*/
+int ltdb_unlock_read(struct ldb_module *module)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	if (ltdb->in_transaction == 0 && ltdb->read_lock_count == 1) {
+		tdb_unlockall_read(ltdb->tdb);
+		return 0;
+	}
+	ltdb->read_lock_count--;
+	return 0;
+}
+
+
+/*
+  form a TDB_DATA for a record key
+  caller frees
+
+  note that the key for a record can depend on whether the
+  dn refers to a case sensitive index record or not
+*/
+TDB_DATA ltdb_key(struct ldb_module *module, struct ldb_dn *dn)
+{
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	TDB_DATA key;
+	char *key_str = NULL;
+	const char *dn_folded = NULL;
+
+	/*
+	  most DNs are case insensitive. The exception is index DNs for
+	  case sensitive attributes
+
+	  there are 3 cases dealt with in this code:
+
+	  1) if the dn doesn't start with @ then uppercase the attribute
+             names and the attributes values of case insensitive attributes
+	  2) if the dn starts with @ then leave it alone -
+	     the indexing code handles the rest
+	*/
+
+	dn_folded = ldb_dn_get_casefold(dn);
+	if (!dn_folded) {
+		goto failed;
+	}
+
+	key_str = talloc_strdup(ldb, "DN=");
+	if (!key_str) {
+		goto failed;
+	}
+
+	key_str = talloc_strdup_append_buffer(key_str, dn_folded);
+	if (!key_str) {
+		goto failed;
+	}
+
+	key.dptr = (uint8_t *)key_str;
+	key.dsize = strlen(key_str) + 1;
+
+	return key;
+
+failed:
+	errno = ENOMEM;
+	key.dptr = NULL;
+	key.dsize = 0;
+	return key;
+}
+
+/*
+  check special dn's have valid attributes
+  currently only @ATTRIBUTES is checked
+*/
+static int ltdb_check_special_dn(struct ldb_module *module,
+				 const struct ldb_message *msg)
+{
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	unsigned int i, j;
+
+	if (! ldb_dn_is_special(msg->dn) ||
+	    ! ldb_dn_check_special(msg->dn, LTDB_ATTRIBUTES)) {
+		return LDB_SUCCESS;
+	}
+
+	/* we have @ATTRIBUTES, let's check attributes are fine */
+	/* should we check that we deny multivalued attributes ? */
+	for (i = 0; i < msg->num_elements; i++) {
+		if (ldb_attr_cmp(msg->elements[i].name, "distinguishedName") == 0) continue;
+
+		for (j = 0; j < msg->elements[i].num_values; j++) {
+			if (ltdb_check_at_attributes_values(&msg->elements[i].values[j]) != 0) {
+				ldb_set_errstring(ldb, "Invalid attribute value in an @ATTRIBUTES entry");
+				return LDB_ERR_INVALID_ATTRIBUTE_SYNTAX;
+			}
+		}
+	}
+
+	return LDB_SUCCESS;
+}
+
+
+/*
+  we've made a modification to a dn - possibly reindex and
+  update sequence number
+*/
+static int ltdb_modified(struct ldb_module *module, struct ldb_dn *dn)
+{
+	int ret = LDB_SUCCESS;
+	struct ltdb_private *ltdb = talloc_get_type(ldb_module_get_private(module), struct ltdb_private);
+
+	/* only allow modifies inside a transaction, otherwise the
+	 * ldb is unsafe */
+	if (ltdb->in_transaction == 0) {
+		ldb_set_errstring(ldb_module_get_ctx(module), "ltdb modify without transaction");
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (ldb_dn_is_special(dn) &&
+	    (ldb_dn_check_special(dn, LTDB_INDEXLIST) ||
+	     ldb_dn_check_special(dn, LTDB_ATTRIBUTES)) ) {
+		ret = ltdb_reindex(module);
+	}
+
+	/* If the modify was to a normal record, or any special except @BASEINFO, update the seq number */
+	if (ret == LDB_SUCCESS &&
+	    !(ldb_dn_is_special(dn) &&
+	      ldb_dn_check_special(dn, LTDB_BASEINFO)) ) {
+		ret = ltdb_increase_sequence_number(module);
+	}
+
+	/* If the modify was to @OPTIONS, reload the cache */
+	if (ret == LDB_SUCCESS &&
+	    ldb_dn_is_special(dn) &&
+	    (ldb_dn_check_special(dn, LTDB_OPTIONS)) ) {
+		ret = ltdb_cache_reload(module);
+	}
+
+	return ret;
+}
+
+/*
+  store a record into the db
+*/
+int ltdb_store(struct ldb_module *module, const struct ldb_message *msg, int flgs)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	TDB_DATA tdb_key, tdb_data;
+	int ret = LDB_SUCCESS;
+
+	tdb_key = ltdb_key(module, msg->dn);
+	if (tdb_key.dptr == NULL) {
+		return LDB_ERR_OTHER;
+	}
+
+	ret = ltdb_pack_data(module, msg, &tdb_data);
+	if (ret == -1) {
+		talloc_free(tdb_key.dptr);
+		return LDB_ERR_OTHER;
+	}
+
+	ret = tdb_store(ltdb->tdb, tdb_key, tdb_data, flgs);
+	if (ret != 0) {
+		ret = ltdb_err_map(tdb_error(ltdb->tdb));
+		goto done;
+	}
+
+done:
+	talloc_free(tdb_key.dptr);
+	talloc_free(tdb_data.dptr);
+
+	return ret;
+}
+
+
+/*
+  check if a attribute is a single valued, for a given element
+ */
+static bool ldb_tdb_single_valued(const struct ldb_schema_attribute *a,
+				  struct ldb_message_element *el)
+{
+	if (!a) return false;
+	if (el != NULL) {
+		if (el->flags & LDB_FLAG_INTERNAL_FORCE_SINGLE_VALUE_CHECK) {
+			/* override from a ldb module, for example
+			   used for the description field, which is
+			   marked multi-valued in the schema but which
+			   should not actually accept multiple
+			   values */
+			return true;
+		}
+		if (el->flags & LDB_FLAG_INTERNAL_DISABLE_SINGLE_VALUE_CHECK) {
+			/* override from a ldb module, for example used for
+			   deleted linked attribute entries */
+			return false;
+		}
+	}
+	if (a->flags & LDB_ATTR_FLAG_SINGLE_VALUE) {
+		return true;
+	}
+	return false;
+}
+
+static int ltdb_add_internal(struct ldb_module *module,
+			     const struct ldb_message *msg)
+{
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	int ret = LDB_SUCCESS;
+	unsigned int i;
+
+	for (i=0;i<msg->num_elements;i++) {
+		struct ldb_message_element *el = &msg->elements[i];
+		const struct ldb_schema_attribute *a = ldb_schema_attribute_by_name(ldb, el->name);
+
+		if (el->num_values == 0) {
+			ldb_asprintf_errstring(ldb, "attribute '%s' on '%s' specified, but with 0 values (illegal)",
+					       el->name, ldb_dn_get_linearized(msg->dn));
+			return LDB_ERR_CONSTRAINT_VIOLATION;
+		}
+		if (el->num_values > 1 && ldb_tdb_single_valued(a, el)) {
+			ldb_asprintf_errstring(ldb, "SINGLE-VALUE attribute %s on %s specified more than once",
+					       el->name, ldb_dn_get_linearized(msg->dn));
+			return LDB_ERR_CONSTRAINT_VIOLATION;
+		}
+	}
+
+	ret = ltdb_store(module, msg, TDB_INSERT);
+	if (ret != LDB_SUCCESS) {
+		if (ret == LDB_ERR_ENTRY_ALREADY_EXISTS) {
+			ldb_asprintf_errstring(ldb,
+					       "Entry %s already exists",
+					       ldb_dn_get_linearized(msg->dn));
+		}
+		return ret;
+	}
+
+	ret = ltdb_index_add_new(module, msg);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	ret = ltdb_modified(module, msg->dn);
+
+	return ret;
+}
+
+/*
+  add a record to the database
+*/
+static int ltdb_add(struct ltdb_context *ctx)
+{
+	struct ldb_module *module = ctx->module;
+	struct ldb_request *req = ctx->req;
+	int ret = LDB_SUCCESS;
+
+	ret = ltdb_check_special_dn(module, req->op.add.message);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	ldb_request_set_state(req, LDB_ASYNC_PENDING);
+
+	if (ltdb_cache_load(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_add_internal(module, req->op.add.message);
+
+	return ret;
+}
+
+/*
+  delete a record from the database, not updating indexes (used for deleting
+  index records)
+*/
+int ltdb_delete_noindex(struct ldb_module *module, struct ldb_dn *dn)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	TDB_DATA tdb_key;
+	int ret;
+
+	tdb_key = ltdb_key(module, dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OTHER;
+	}
+
+	ret = tdb_delete(ltdb->tdb, tdb_key);
+	talloc_free(tdb_key.dptr);
+
+	if (ret != 0) {
+		ret = ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	return ret;
+}
+
+static int ltdb_delete_internal(struct ldb_module *module, struct ldb_dn *dn)
+{
+	struct ldb_message *msg;
+	int ret = LDB_SUCCESS;
+
+	msg = ldb_msg_new(module);
+	if (msg == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* in case any attribute of the message was indexed, we need
+	   to fetch the old record */
+	ret = ltdb_search_dn1(module, dn, msg);
+	if (ret != LDB_SUCCESS) {
+		/* not finding the old record is an error */
+		goto done;
+	}
+
+	ret = ltdb_delete_noindex(module, dn);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+	/* remove any indexed attributes */
+	ret = ltdb_index_delete(module, msg);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+	ret = ltdb_modified(module, dn);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+done:
+	talloc_free(msg);
+	return ret;
+}
+
+/*
+  delete a record from the database
+*/
+static int ltdb_delete(struct ltdb_context *ctx)
+{
+	struct ldb_module *module = ctx->module;
+	struct ldb_request *req = ctx->req;
+	int ret = LDB_SUCCESS;
+
+	ldb_request_set_state(req, LDB_ASYNC_PENDING);
+
+	if (ltdb_cache_load(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_delete_internal(module, req->op.del.dn);
+
+	return ret;
+}
+
+/*
+  find an element by attribute name. At the moment this does a linear search,
+  it should be re-coded to use a binary search once all places that modify
+  records guarantee sorted order
+
+  return the index of the first matching element if found, otherwise -1
+*/
+static int find_element(const struct ldb_message *msg, const char *name)
+{
+	unsigned int i;
+	for (i=0;i<msg->num_elements;i++) {
+		if (ldb_attr_cmp(msg->elements[i].name, name) == 0) {
+			return i;
+		}
+	}
+	return -1;
+}
+
+
+/*
+  add an element to an existing record. Assumes a elements array that we
+  can call re-alloc on, and assumed that we can re-use the data pointers from
+  the passed in additional values. Use with care!
+
+  returns 0 on success, -1 on failure (and sets errno)
+*/
+static int ltdb_msg_add_element(struct ldb_context *ldb,
+				struct ldb_message *msg,
+				struct ldb_message_element *el)
+{
+	struct ldb_message_element *e2;
+	unsigned int i;
+
+	if (el->num_values == 0) {
+		/* nothing to do here - we don't add empty elements */
+		return 0;
+	}
+
+	e2 = talloc_realloc(msg, msg->elements, struct ldb_message_element,
+			      msg->num_elements+1);
+	if (!e2) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	msg->elements = e2;
+
+	e2 = &msg->elements[msg->num_elements];
+
+	e2->name = el->name;
+	e2->flags = el->flags;
+	e2->values = talloc_array(msg->elements,
+				  struct ldb_val, el->num_values);
+	if (!e2->values) {
+		errno = ENOMEM;
+		return -1;
+	}
+	for (i=0;i<el->num_values;i++) {
+		e2->values[i] = el->values[i];
+	}
+	e2->num_values = el->num_values;
+
+	++msg->num_elements;
+
+	return 0;
+}
+
+/*
+  delete all elements having a specified attribute name
+*/
+static int msg_delete_attribute(struct ldb_module *module,
+				struct ldb_context *ldb,
+				struct ldb_message *msg, const char *name)
+{
+	unsigned int i;
+	int ret;
+	struct ldb_message_element *el;
+
+	el = ldb_msg_find_element(msg, name);
+	if (el == NULL) {
+		return LDB_ERR_NO_SUCH_ATTRIBUTE;
+	}
+	i = el - msg->elements;
+
+	ret = ltdb_index_del_element(module, msg->dn, el);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	talloc_free(el->values);
+	if (msg->num_elements > (i+1)) {
+		memmove(el, el+1, sizeof(*el) * (msg->num_elements - (i+1)));
+	}
+	msg->num_elements--;
+	msg->elements = talloc_realloc(msg, msg->elements,
+				       struct ldb_message_element,
+				       msg->num_elements);
+	return LDB_SUCCESS;
+}
+
+/*
+  delete all elements matching an attribute name/value
+
+  return LDB Error on failure
+*/
+static int msg_delete_element(struct ldb_module *module,
+			      struct ldb_message *msg,
+			      const char *name,
+			      const struct ldb_val *val)
+{
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	unsigned int i;
+	int found, ret;
+	struct ldb_message_element *el;
+	const struct ldb_schema_attribute *a;
+
+	found = find_element(msg, name);
+	if (found == -1) {
+		return LDB_ERR_NO_SUCH_ATTRIBUTE;
+	}
+
+	i = (unsigned int) found;
+	el = &(msg->elements[i]);
+
+	a = ldb_schema_attribute_by_name(ldb, el->name);
+
+	for (i=0;i<el->num_values;i++) {
+		bool matched;
+		if (a->syntax->operator_fn) {
+			ret = a->syntax->operator_fn(ldb, LDB_OP_EQUALITY, a,
+						     &el->values[i], val, &matched);
+			if (ret != LDB_SUCCESS) return ret;
+		} else {
+			matched = (a->syntax->comparison_fn(ldb, ldb,
+							    &el->values[i], val) == 0);
+		}
+		if (matched) {
+			if (el->num_values == 1) {
+				return msg_delete_attribute(module, ldb, msg, name);
+			}
+
+			ret = ltdb_index_del_value(module, msg->dn, el, i);
+			if (ret != LDB_SUCCESS) {
+				return ret;
+			}
+
+			if (i<el->num_values-1) {
+				memmove(&el->values[i], &el->values[i+1],
+					sizeof(el->values[i])*
+						(el->num_values-(i+1)));
+			}
+			el->num_values--;
+
+			/* per definition we find in a canonicalised message an
+			   attribute value only once. So we are finished here */
+			return LDB_SUCCESS;
+		}
+	}
+
+	/* Not found */
+	return LDB_ERR_NO_SUCH_ATTRIBUTE;
+}
+
+
+/*
+  modify a record - internal interface
+
+  yuck - this is O(n^2). Luckily n is usually small so we probably
+  get away with it, but if we ever have really large attribute lists
+  then we'll need to look at this again
+
+  'req' is optional, and is used to specify controls if supplied
+*/
+int ltdb_modify_internal(struct ldb_module *module,
+			 const struct ldb_message *msg,
+			 struct ldb_request *req)
+{
+	struct ldb_context *ldb = ldb_module_get_ctx(module);
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+	TDB_DATA tdb_key, tdb_data;
+	struct ldb_message *msg2;
+	unsigned int i, j, k;
+	int ret = LDB_SUCCESS, idx;
+	struct ldb_control *control_permissive = NULL;
+
+	if (req) {
+		control_permissive = ldb_request_get_control(req,
+					LDB_CONTROL_PERMISSIVE_MODIFY_OID);
+	}
+
+	tdb_key = ltdb_key(module, msg->dn);
+	if (!tdb_key.dptr) {
+		return LDB_ERR_OTHER;
+	}
+
+	tdb_data = tdb_fetch_compat(ltdb->tdb, tdb_key);
+	if (!tdb_data.dptr) {
+		talloc_free(tdb_key.dptr);
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	msg2 = ldb_msg_new(tdb_key.dptr);
+	if (msg2 == NULL) {
+		free(tdb_data.dptr);
+		ret = LDB_ERR_OTHER;
+		goto done;
+	}
+
+	ret = ltdb_unpack_data(module, &tdb_data, msg2);
+	free(tdb_data.dptr);
+	if (ret == -1) {
+		ret = LDB_ERR_OTHER;
+		goto done;
+	}
+
+	if (!msg2->dn) {
+		msg2->dn = msg->dn;
+	}
+
+	for (i=0; i<msg->num_elements; i++) {
+		struct ldb_message_element *el = &msg->elements[i], *el2;
+		struct ldb_val *vals;
+		const struct ldb_schema_attribute *a = ldb_schema_attribute_by_name(ldb, el->name);
+		const char *dn;
+
+		switch (msg->elements[i].flags & LDB_FLAG_MOD_MASK) {
+		case LDB_FLAG_MOD_ADD:
+
+			if (el->num_values == 0) {
+				ldb_asprintf_errstring(ldb,
+						       "attribute '%s': attribute on '%s' specified, but with 0 values (illegal)",
+						       el->name, ldb_dn_get_linearized(msg2->dn));
+				ret = LDB_ERR_CONSTRAINT_VIOLATION;
+				goto done;
+			}
+
+			/* make a copy of the array so that a permissive
+			 * control can remove duplicates without changing the
+			 * original values, but do not copy data as we do not
+			 * need to keep it around once the operation is
+			 * finished */
+			if (control_permissive) {
+				el = talloc(msg2, struct ldb_message_element);
+				if (!el) {
+					ret = LDB_ERR_OTHER;
+					goto done;
+				}
+				*el = msg->elements[i];
+				el->values = talloc_array(el, struct ldb_val, el->num_values);
+				if (el->values == NULL) {
+					ret = LDB_ERR_OTHER;
+					goto done;
+				}
+				for (j = 0; j < el->num_values; j++) {
+					el->values[j] = msg->elements[i].values[j];
+				}
+			}
+
+			if (el->num_values > 1 && ldb_tdb_single_valued(a, el)) {
+				ldb_asprintf_errstring(ldb, "SINGLE-VALUE attribute %s on %s specified more than once",
+						       el->name, ldb_dn_get_linearized(msg2->dn));
+				ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+				goto done;
+			}
+
+			/* Checks if element already exists */
+			idx = find_element(msg2, el->name);
+			if (idx == -1) {
+				if (ltdb_msg_add_element(ldb, msg2, el) != 0) {
+					ret = LDB_ERR_OTHER;
+					goto done;
+				}
+				ret = ltdb_index_add_element(module, msg2->dn,
+							     el);
+				if (ret != LDB_SUCCESS) {
+					goto done;
+				}
+			} else {
+				j = (unsigned int) idx;
+				el2 = &(msg2->elements[j]);
+
+				/* We cannot add another value on a existing one
+				   if the attribute is single-valued */
+				if (ldb_tdb_single_valued(a, el)) {
+					ldb_asprintf_errstring(ldb, "SINGLE-VALUE attribute %s on %s specified more than once",
+						               el->name, ldb_dn_get_linearized(msg2->dn));
+					ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+					goto done;
+				}
+
+				/* Check that values don't exist yet on multi-
+				   valued attributes or aren't provided twice */
+				for (j = 0; j < el->num_values; j++) {
+					if (ldb_msg_find_val(el2, &el->values[j]) != NULL) {
+						if (control_permissive) {
+							/* remove this one as if it was never added */
+							el->num_values--;
+							for (k = j; k < el->num_values; k++) {
+								el->values[k] = el->values[k + 1];
+							}
+							j--; /* rewind */
+
+							continue;
+						}
+
+						ldb_asprintf_errstring(ldb,
+								       "attribute '%s': value #%u on '%s' already exists",
+								       el->name, j, ldb_dn_get_linearized(msg2->dn));
+						ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+						goto done;
+					}
+					if (ldb_msg_find_val(el, &el->values[j]) != &el->values[j]) {
+						ldb_asprintf_errstring(ldb,
+								       "attribute '%s': value #%u on '%s' provided more than once",
+								       el->name, j, ldb_dn_get_linearized(msg2->dn));
+						ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+						goto done;
+					}
+				}
+
+				/* Now combine existing and new values to a new
+				   attribute record */
+				vals = talloc_realloc(msg2->elements,
+						      el2->values, struct ldb_val,
+						      el2->num_values + el->num_values);
+				if (vals == NULL) {
+					ldb_oom(ldb);
+					ret = LDB_ERR_OTHER;
+					goto done;
+				}
+
+				for (j=0; j<el->num_values; j++) {
+					vals[el2->num_values + j] =
+						ldb_val_dup(vals, &el->values[j]);
+				}
+
+				el2->values = vals;
+				el2->num_values += el->num_values;
+
+				ret = ltdb_index_add_element(module, msg2->dn, el);
+				if (ret != LDB_SUCCESS) {
+					goto done;
+				}
+			}
+
+			break;
+
+		case LDB_FLAG_MOD_REPLACE:
+
+			if (el->num_values > 1 && ldb_tdb_single_valued(a, el)) {
+				ldb_asprintf_errstring(ldb, "SINGLE-VALUE attribute %s on %s specified more than once",
+						       el->name, ldb_dn_get_linearized(msg2->dn));
+				ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+				goto done;
+			}
+
+			/* TODO: This is O(n^2) - replace with more efficient check */
+			for (j=0; j<el->num_values; j++) {
+				if (ldb_msg_find_val(el, &el->values[j]) != &el->values[j]) {
+					ldb_asprintf_errstring(ldb,
+							       "attribute '%s': value #%u on '%s' provided more than once",
+							       el->name, j, ldb_dn_get_linearized(msg2->dn));
+					ret = LDB_ERR_ATTRIBUTE_OR_VALUE_EXISTS;
+					goto done;
+				}
+			}
+
+			/* Checks if element already exists */
+			idx = find_element(msg2, el->name);
+			if (idx != -1) {
+				j = (unsigned int) idx;
+				el2 = &(msg2->elements[j]);
+				if (ldb_msg_element_compare(el, el2) == 0) {
+					/* we are replacing with the same values */
+					continue;
+				}
+			
+				/* Delete the attribute if it exists in the DB */
+				if (msg_delete_attribute(module, ldb, msg2,
+							 el->name) != 0) {
+					ret = LDB_ERR_OTHER;
+					goto done;
+				}
+			}
+
+			/* Recreate it with the new values */
+			if (ltdb_msg_add_element(ldb, msg2, el) != 0) {
+				ret = LDB_ERR_OTHER;
+				goto done;
+			}
+
+			ret = ltdb_index_add_element(module, msg2->dn, el);
+			if (ret != LDB_SUCCESS) {
+				goto done;
+			}
+
+			break;
+
+		case LDB_FLAG_MOD_DELETE:
+			dn = ldb_dn_get_linearized(msg2->dn);
+			if (dn == NULL) {
+				ret = LDB_ERR_OTHER;
+				goto done;
+			}
+
+			if (msg->elements[i].num_values == 0) {
+				/* Delete the whole attribute */
+				ret = msg_delete_attribute(module, ldb, msg2,
+							   msg->elements[i].name);
+				if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE &&
+				    control_permissive) {
+					ret = LDB_SUCCESS;
+				} else {
+					ldb_asprintf_errstring(ldb,
+							       "attribute '%s': no such attribute for delete on '%s'",
+							       msg->elements[i].name, dn);
+				}
+				if (ret != LDB_SUCCESS) {
+					goto done;
+				}
+			} else {
+				/* Delete specified values from an attribute */
+				for (j=0; j < msg->elements[i].num_values; j++) {
+					ret = msg_delete_element(module,
+							         msg2,
+							         msg->elements[i].name,
+							         &msg->elements[i].values[j]);
+					if (ret == LDB_ERR_NO_SUCH_ATTRIBUTE &&
+					    control_permissive) {
+						ret = LDB_SUCCESS;
+					} else {
+						ldb_asprintf_errstring(ldb,
+								       "attribute '%s': no matching attribute value while deleting attribute on '%s'",
+								       msg->elements[i].name, dn);
+					}
+					if (ret != LDB_SUCCESS) {
+						goto done;
+					}
+				}
+			}
+			break;
+		default:
+			ldb_asprintf_errstring(ldb,
+					       "attribute '%s': invalid modify flags on '%s': 0x%x",
+					       msg->elements[i].name, ldb_dn_get_linearized(msg->dn),
+					       msg->elements[i].flags & LDB_FLAG_MOD_MASK);
+			ret = LDB_ERR_PROTOCOL_ERROR;
+			goto done;
+		}
+	}
+
+	ret = ltdb_store(module, msg2, TDB_MODIFY);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+	ret = ltdb_modified(module, msg2->dn);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+done:
+	talloc_free(tdb_key.dptr);
+	return ret;
+}
+
+/*
+  modify a record
+*/
+static int ltdb_modify(struct ltdb_context *ctx)
+{
+	struct ldb_module *module = ctx->module;
+	struct ldb_request *req = ctx->req;
+	int ret = LDB_SUCCESS;
+
+	ret = ltdb_check_special_dn(module, req->op.mod.message);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	ldb_request_set_state(req, LDB_ASYNC_PENDING);
+
+	if (ltdb_cache_load(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_modify_internal(module, req->op.mod.message, req);
+
+	return ret;
+}
+
+/*
+  rename a record
+*/
+static int ltdb_rename(struct ltdb_context *ctx)
+{
+	struct ldb_module *module = ctx->module;
+	struct ldb_request *req = ctx->req;
+	struct ldb_message *msg;
+	int ret = LDB_SUCCESS;
+
+	ldb_request_set_state(req, LDB_ASYNC_PENDING);
+
+	if (ltdb_cache_load(ctx->module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	msg = ldb_msg_new(ctx);
+	if (msg == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* in case any attribute of the message was indexed, we need
+	   to fetch the old record */
+	ret = ltdb_search_dn1(module, req->op.rename.olddn, msg);
+	if (ret != LDB_SUCCESS) {
+		/* not finding the old record is an error */
+		return ret;
+	}
+
+	/* Always delete first then add, to avoid conflicts with
+	 * unique indexes. We rely on the transaction to make this
+	 * atomic
+	 */
+	ret = ltdb_delete_internal(module, msg->dn);
+	if (ret != LDB_SUCCESS) {
+		return ret;
+	}
+
+	msg->dn = ldb_dn_copy(msg, req->op.rename.newdn);
+	if (msg->dn == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ret = ltdb_add_internal(module, msg);
+
+	return ret;
+}
+
+static int ltdb_start_trans(struct ldb_module *module)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+
+	if (tdb_transaction_start(ltdb->tdb) != 0) {
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	ltdb->in_transaction++;
+
+	ltdb_index_transaction_start(module);
+
+	return LDB_SUCCESS;
+}
+
+static int ltdb_prepare_commit(struct ldb_module *module)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+
+	if (ltdb->in_transaction != 1) {
+		return LDB_SUCCESS;
+	}
+
+	if (ltdb_index_transaction_commit(module) != 0) {
+		tdb_transaction_cancel(ltdb->tdb);
+		ltdb->in_transaction--;
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	if (tdb_transaction_prepare_commit(ltdb->tdb) != 0) {
+		ltdb->in_transaction--;
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	ltdb->prepared_commit = true;
+
+	return LDB_SUCCESS;
+}
+
+static int ltdb_end_trans(struct ldb_module *module)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+
+	if (!ltdb->prepared_commit) {
+		int ret = ltdb_prepare_commit(module);
+		if (ret != LDB_SUCCESS) {
+			return ret;
+		}
+	}
+
+	ltdb->in_transaction--;
+	ltdb->prepared_commit = false;
+
+	if (tdb_transaction_commit(ltdb->tdb) != 0) {
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	return LDB_SUCCESS;
+}
+
+static int ltdb_del_trans(struct ldb_module *module)
+{
+	void *data = ldb_module_get_private(module);
+	struct ltdb_private *ltdb = talloc_get_type(data, struct ltdb_private);
+
+	ltdb->in_transaction--;
+
+	if (ltdb_index_transaction_cancel(module) != 0) {
+		tdb_transaction_cancel(ltdb->tdb);
+		return ltdb_err_map(tdb_error(ltdb->tdb));
+	}
+
+	tdb_transaction_cancel(ltdb->tdb);
+	return LDB_SUCCESS;
+}
+
+/*
+  return sequenceNumber from @BASEINFO
+*/
+static int ltdb_sequence_number(struct ltdb_context *ctx,
+				struct ldb_extended **ext)
+{
+	struct ldb_context *ldb;
+	struct ldb_module *module = ctx->module;
+	struct ldb_request *req = ctx->req;
+	TALLOC_CTX *tmp_ctx = NULL;
+	struct ldb_seqnum_request *seq;
+	struct ldb_seqnum_result *res;
+	struct ldb_message *msg = NULL;
+	struct ldb_dn *dn;
+	const char *date;
+	int ret = LDB_SUCCESS;
+
+	ldb = ldb_module_get_ctx(module);
+
+	seq = talloc_get_type(req->op.extended.data,
+				struct ldb_seqnum_request);
+	if (seq == NULL) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ldb_request_set_state(req, LDB_ASYNC_PENDING);
+
+	if (ltdb_lock_read(module) != 0) {
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	res = talloc_zero(req, struct ldb_seqnum_result);
+	if (res == NULL) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+
+	tmp_ctx = talloc_new(req);
+	if (tmp_ctx == NULL) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+
+	dn = ldb_dn_new(tmp_ctx, ldb, LTDB_BASEINFO);
+	if (dn == NULL) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+
+	msg = ldb_msg_new(tmp_ctx);
+	if (msg == NULL) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+
+	ret = ltdb_search_dn1(module, dn, msg);
+	if (ret != LDB_SUCCESS) {
+		goto done;
+	}
+
+	switch (seq->type) {
+	case LDB_SEQ_HIGHEST_SEQ:
+		res->seq_num = ldb_msg_find_attr_as_uint64(msg, LTDB_SEQUENCE_NUMBER, 0);
+		break;
+	case LDB_SEQ_NEXT:
+		res->seq_num = ldb_msg_find_attr_as_uint64(msg, LTDB_SEQUENCE_NUMBER, 0);
+		res->seq_num++;
+		break;
+	case LDB_SEQ_HIGHEST_TIMESTAMP:
+		date = ldb_msg_find_attr_as_string(msg, LTDB_MOD_TIMESTAMP, NULL);
+		if (date) {
+			res->seq_num = ldb_string_to_time(date);
+		} else {
+			res->seq_num = 0;
+			/* zero is as good as anything when we don't know */
+		}
+		break;
+	}
+
+	*ext = talloc_zero(req, struct ldb_extended);
+	if (*ext == NULL) {
+		ret = LDB_ERR_OPERATIONS_ERROR;
+		goto done;
+	}
+	(*ext)->oid = LDB_EXTENDED_SEQUENCE_NUMBER;
+	(*ext)->data = talloc_steal(*ext, res);
+
+done:
+	talloc_free(tmp_ctx);
+	ltdb_unlock_read(module);
+	return ret;
+}
+
+static void ltdb_request_done(struct ltdb_context *ctx, int error)
+{
+	struct ldb_context *ldb;
+	struct ldb_request *req;
+	struct ldb_reply *ares;
+
+	ldb = ldb_module_get_ctx(ctx->module);
+	req = ctx->req;
+
+	/* if we already returned an error just return */
+	if (ldb_request_get_status(req) != LDB_SUCCESS) {
+		return;
+	}
+
+	ares = talloc_zero(req, struct ldb_reply);
+	if (!ares) {
+		ldb_oom(ldb);
+		req->callback(req, NULL);
+		return;
+	}
+	ares->type = LDB_REPLY_DONE;
+	ares->error = error;
+
+	req->callback(req, ares);
+}
+
+static void ltdb_timeout(struct tevent_context *ev,
+			  struct tevent_timer *te,
+			  struct timeval t,
+			  void *private_data)
+{
+	struct ltdb_context *ctx;
+	ctx = talloc_get_type(private_data, struct ltdb_context);
+
+	if (!ctx->request_terminated) {
+		/* request is done now */
+		ltdb_request_done(ctx, LDB_ERR_TIME_LIMIT_EXCEEDED);
+	}
+
+	if (!ctx->request_terminated) {
+		/* neutralize the spy */
+		ctx->spy->ctx = NULL;
+	}
+	talloc_free(ctx);
+}
+
+static void ltdb_request_extended_done(struct ltdb_context *ctx,
+					struct ldb_extended *ext,
+					int error)
+{
+	struct ldb_context *ldb;
+	struct ldb_request *req;
+	struct ldb_reply *ares;
+
+	ldb = ldb_module_get_ctx(ctx->module);
+	req = ctx->req;
+
+	/* if we already returned an error just return */
+	if (ldb_request_get_status(req) != LDB_SUCCESS) {
+		return;
+	}
+
+	ares = talloc_zero(req, struct ldb_reply);
+	if (!ares) {
+		ldb_oom(ldb);
+		req->callback(req, NULL);
+		return;
+	}
+	ares->type = LDB_REPLY_DONE;
+	ares->response = ext;
+	ares->error = error;
+
+	req->callback(req, ares);
+}
+
+static void ltdb_handle_extended(struct ltdb_context *ctx)
+{
+	struct ldb_extended *ext = NULL;
+	int ret;
+
+	if (strcmp(ctx->req->op.extended.oid,
+		   LDB_EXTENDED_SEQUENCE_NUMBER) == 0) {
+		/* get sequence number */
+		ret = ltdb_sequence_number(ctx, &ext);
+	} else {
+		/* not recognized */
+		ret = LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+	}
+
+	ltdb_request_extended_done(ctx, ext, ret);
+}
+
+static void ltdb_callback(struct tevent_context *ev,
+			  struct tevent_timer *te,
+			  struct timeval t,
+			  void *private_data)
+{
+	struct ltdb_context *ctx;
+	int ret;
+
+	ctx = talloc_get_type(private_data, struct ltdb_context);
+
+	if (ctx->request_terminated) {
+		goto done;
+	}
+
+	switch (ctx->req->operation) {
+	case LDB_SEARCH:
+		ret = ltdb_search(ctx);
+		break;
+	case LDB_ADD:
+		ret = ltdb_add(ctx);
+		break;
+	case LDB_MODIFY:
+		ret = ltdb_modify(ctx);
+		break;
+	case LDB_DELETE:
+		ret = ltdb_delete(ctx);
+		break;
+	case LDB_RENAME:
+		ret = ltdb_rename(ctx);
+		break;
+	case LDB_EXTENDED:
+		ltdb_handle_extended(ctx);
+		goto done;
+	default:
+		/* no other op supported */
+		ret = LDB_ERR_PROTOCOL_ERROR;
+	}
+
+	if (!ctx->request_terminated) {
+		/* request is done now */
+		ltdb_request_done(ctx, ret);
+	}
+
+done:
+	if (!ctx->request_terminated) {
+		/* neutralize the spy */
+		ctx->spy->ctx = NULL;
+	}
+	talloc_free(ctx);
+}
+
+static int ltdb_request_destructor(void *ptr)
+{
+	struct ltdb_req_spy *spy = talloc_get_type(ptr, struct ltdb_req_spy);
+
+	if (spy->ctx != NULL) {
+		spy->ctx->request_terminated = true;
+	}
+
+	return 0;
+}
+
+static int ltdb_handle_request(struct ldb_module *module,
+			       struct ldb_request *req)
+{
+	struct ldb_control *control_permissive;
+	struct ldb_context *ldb;
+	struct tevent_context *ev;
+	struct ltdb_context *ac;
+	struct tevent_timer *te;
+	struct timeval tv;
+	unsigned int i;
+
+	ldb = ldb_module_get_ctx(module);
+
+	control_permissive = ldb_request_get_control(req,
+					LDB_CONTROL_PERMISSIVE_MODIFY_OID);
+
+	for (i = 0; req->controls && req->controls[i]; i++) {
+		if (req->controls[i]->critical &&
+		    req->controls[i] != control_permissive) {
+			ldb_asprintf_errstring(ldb, "Unsupported critical extension %s",
+					       req->controls[i]->oid);
+			return LDB_ERR_UNSUPPORTED_CRITICAL_EXTENSION;
+		}
+	}
+
+	if (req->starttime == 0 || req->timeout == 0) {
+		ldb_set_errstring(ldb, "Invalid timeout settings");
+		return LDB_ERR_TIME_LIMIT_EXCEEDED;
+	}
+
+	ev = ldb_get_event_context(ldb);
+
+	ac = talloc_zero(ldb, struct ltdb_context);
+	if (ac == NULL) {
+		ldb_oom(ldb);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	ac->module = module;
+	ac->req = req;
+
+	tv.tv_sec = 0;
+	tv.tv_usec = 0;
+	te = tevent_add_timer(ev, ac, tv, ltdb_callback, ac);
+	if (NULL == te) {
+		talloc_free(ac);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	tv.tv_sec = req->starttime + req->timeout;
+	ac->timeout_event = tevent_add_timer(ev, ac, tv, ltdb_timeout, ac);
+	if (NULL == ac->timeout_event) {
+		talloc_free(ac);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* set a spy so that we do not try to use the request context
+	 * if it is freed before ltdb_callback fires */
+	ac->spy = talloc(req, struct ltdb_req_spy);
+	if (NULL == ac->spy) {
+		talloc_free(ac);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ac->spy->ctx = ac;
+
+	talloc_set_destructor((TALLOC_CTX *)ac->spy, ltdb_request_destructor);
+
+	return LDB_SUCCESS;
+}
+
+static int ltdb_init_rootdse(struct ldb_module *module)
+{
+	struct ldb_context *ldb;
+	int ret;
+
+	ldb = ldb_module_get_ctx(module);
+
+	ret = ldb_mod_register_control(module,
+				       LDB_CONTROL_PERMISSIVE_MODIFY_OID);
+	/* ignore errors on this - we expect it for non-sam databases */
+
+	/* there can be no module beyond the backend, just return */
+	return LDB_SUCCESS;
+}
+
+static const struct ldb_module_ops ltdb_ops = {
+	.name              = "tdb",
+	.init_context      = ltdb_init_rootdse,
+	.search            = ltdb_handle_request,
+	.add               = ltdb_handle_request,
+	.modify            = ltdb_handle_request,
+	.del               = ltdb_handle_request,
+	.rename            = ltdb_handle_request,
+	.extended          = ltdb_handle_request,
+	.start_transaction = ltdb_start_trans,
+	.end_transaction   = ltdb_end_trans,
+	.prepare_commit    = ltdb_prepare_commit,
+	.del_transaction   = ltdb_del_trans,
+};
+
+/*
+  connect to the database
+*/
+static int ltdb_connect(struct ldb_context *ldb, const char *url,
+			unsigned int flags, const char *options[],
+			struct ldb_module **_module)
+{
+	struct ldb_module *module;
+	const char *path;
+	int tdb_flags, open_flags;
+	struct ltdb_private *ltdb;
+
+	/* parse the url */
+	if (strchr(url, ':')) {
+		if (strncmp(url, "tdb://", 6) != 0) {
+			ldb_debug(ldb, LDB_DEBUG_ERROR,
+				  "Invalid tdb URL '%s'", url);
+			return LDB_ERR_OPERATIONS_ERROR;
+		}
+		path = url+6;
+	} else {
+		path = url;
+	}
+
+	tdb_flags = TDB_DEFAULT | TDB_SEQNUM;
+
+	/* check for the 'nosync' option */
+	if (flags & LDB_FLG_NOSYNC) {
+		tdb_flags |= TDB_NOSYNC;
+	}
+
+	/* and nommap option */
+	if (flags & LDB_FLG_NOMMAP) {
+		tdb_flags |= TDB_NOMMAP;
+	}
+
+	if (flags & LDB_FLG_RDONLY) {
+		open_flags = O_RDONLY;
+	} else {
+		open_flags = O_CREAT | O_RDWR;
+	}
+
+	ltdb = talloc_zero(ldb, struct ltdb_private);
+	if (!ltdb) {
+		ldb_oom(ldb);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	/* note that we use quite a large default hash size */
+	ltdb->tdb = ltdb_wrap_open(ltdb, path, 10000,
+				   tdb_flags, open_flags,
+				   ldb_get_create_perms(ldb), ldb);
+	if (!ltdb->tdb) {
+		ldb_debug(ldb, LDB_DEBUG_ERROR,
+			  "Unable to open tdb '%s'", path);
+		talloc_free(ltdb);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	if (getenv("LDB_WARN_UNINDEXED")) {
+		ltdb->warn_unindexed = true;
+	}
+
+	ltdb->sequence_number = 0;
+
+	module = ldb_module_new(ldb, ldb, "ldb_tdb backend", &ltdb_ops);
+	if (!module) {
+		talloc_free(ltdb);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+	ldb_module_set_private(module, ltdb);
+	talloc_steal(module, ltdb);
+
+	if (ltdb_cache_load(module) != 0) {
+		talloc_free(module);
+		talloc_free(ltdb);
+		return LDB_ERR_OPERATIONS_ERROR;
+	}
+
+	*_module = module;
+	return LDB_SUCCESS;
+}
+
+int ldb_tdb_init(const char *version)
+{
+	LDB_MODULE_CHECK_VERSION(version);
+	return ldb_register_backend("tdb", ltdb_connect, false);
+}
diff --git a/lib/ldb/ldb_tdb/ldb_tdb.h b/lib/ldb/ldb_tdb/ldb_tdb.h
new file mode 100644
index 0000000000..96ad43fbd6
--- /dev/null
+++ b/lib/ldb/ldb_tdb/ldb_tdb.h
@@ -0,0 +1,139 @@
+#include "replace.h"
+#include "system/filesys.h"
+#include "system/time.h"
+#include "tdb_compat.h"
+#include "ldb_module.h"
+
+/* this private structure is used by the ltdb backend in the
+   ldb_context */
+struct ltdb_private {
+	TDB_CONTEXT *tdb;
+	unsigned int connect_flags;
+	
+	unsigned long long sequence_number;
+
+	/* the low level tdb seqnum - used to avoid loading BASEINFO when
+	   possible */
+	int tdb_seqnum;
+
+	struct ltdb_cache {
+		struct ldb_message *indexlist;
+		struct ldb_message *attributes;
+		bool one_level_indexes;
+		bool attribute_indexes;
+	} *cache;
+
+	int in_transaction;
+
+	bool check_base;
+	struct ltdb_idxptr *idxptr;
+	bool prepared_commit;
+	int read_lock_count;
+
+	bool warn_unindexed;
+};
+
+/*
+  the async local context
+  holds also internal search state during a full db search
+*/
+struct ltdb_req_spy {
+	struct ltdb_context *ctx;
+};
+
+struct ltdb_context {
+	struct ldb_module *module;
+	struct ldb_request *req;
+
+	bool request_terminated;
+	struct ltdb_req_spy *spy;
+
+	/* search stuff */
+	const struct ldb_parse_tree *tree;
+	struct ldb_dn *base;
+	enum ldb_scope scope;
+	const char * const *attrs;
+	struct tevent_timer *timeout_event;
+};
+
+/* special record types */
+#define LTDB_INDEX      "@INDEX"
+#define LTDB_INDEXLIST  "@INDEXLIST"
+#define LTDB_IDX        "@IDX"
+#define LTDB_IDXVERSION "@IDXVERSION"
+#define LTDB_IDXATTR    "@IDXATTR"
+#define LTDB_IDXONE     "@IDXONE"
+#define LTDB_BASEINFO   "@BASEINFO"
+#define LTDB_OPTIONS    "@OPTIONS"
+#define LTDB_ATTRIBUTES "@ATTRIBUTES"
+
+/* special attribute types */
+#define LTDB_SEQUENCE_NUMBER "sequenceNumber"
+#define LTDB_CHECK_BASE "checkBaseOnSearch"
+#define LTDB_MOD_TIMESTAMP "whenChanged"
+#define LTDB_OBJECTCLASS "objectClass"
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_cache.c  */
+
+int ltdb_cache_reload(struct ldb_module *module);
+int ltdb_cache_load(struct ldb_module *module);
+int ltdb_increase_sequence_number(struct ldb_module *module);
+int ltdb_check_at_attributes_values(const struct ldb_val *value);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_index.c  */
+
+struct ldb_parse_tree;
+
+int ltdb_search_indexed(struct ltdb_context *ctx, uint32_t *);
+int ltdb_index_add_new(struct ldb_module *module, const struct ldb_message *msg);
+int ltdb_index_delete(struct ldb_module *module, const struct ldb_message *msg);
+int ltdb_index_del_element(struct ldb_module *module, struct ldb_dn *dn,
+			   struct ldb_message_element *el);
+int ltdb_index_add_element(struct ldb_module *module, struct ldb_dn *dn, 
+			   struct ldb_message_element *el);
+int ltdb_index_del_value(struct ldb_module *module, struct ldb_dn *dn,
+			 struct ldb_message_element *el, unsigned int v_idx);
+int ltdb_reindex(struct ldb_module *module);
+int ltdb_index_transaction_start(struct ldb_module *module);
+int ltdb_index_transaction_commit(struct ldb_module *module);
+int ltdb_index_transaction_cancel(struct ldb_module *module);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_pack.c  */
+
+int ltdb_pack_data(struct ldb_module *module,
+		   const struct ldb_message *message,
+		   TDB_DATA *data);
+void ltdb_unpack_data_free(struct ldb_module *module,
+			   struct ldb_message *message);
+int ltdb_unpack_data(struct ldb_module *module,
+		     const TDB_DATA *data,
+		     struct ldb_message *message);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_search.c  */
+
+int ltdb_has_wildcard(struct ldb_module *module, const char *attr_name, 
+		      const struct ldb_val *val);
+void ltdb_search_dn1_free(struct ldb_module *module, struct ldb_message *msg);
+int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_message *msg);
+int ltdb_add_attr_results(struct ldb_module *module,
+ 			  TALLOC_CTX *mem_ctx, 
+			  struct ldb_message *msg,
+			  const char * const attrs[], 
+			  unsigned int *count, 
+			  struct ldb_message ***res);
+int ltdb_filter_attrs(struct ldb_message *msg, const char * const *attrs);
+int ltdb_search(struct ltdb_context *ctx);
+
+/* The following definitions come from lib/ldb/ldb_tdb/ldb_tdb.c  */
+int ltdb_lock_read(struct ldb_module *module);
+int ltdb_unlock_read(struct ldb_module *module);
+TDB_DATA ltdb_key(struct ldb_module *module, struct ldb_dn *dn);
+int ltdb_store(struct ldb_module *module, const struct ldb_message *msg, int flgs);
+int ltdb_modify_internal(struct ldb_module *module, const struct ldb_message *msg, struct ldb_request *req);
+int ltdb_delete_noindex(struct ldb_module *module, struct ldb_dn *dn);
+int ltdb_err_map(enum TDB_ERROR tdb_code);
+
+struct tdb_context *ltdb_wrap_open(TALLOC_CTX *mem_ctx,
+				   const char *path, int hash_size, int tdb_flags,
+				   int open_flags, mode_t mode,
+				   struct ldb_context *ldb);
diff --git a/lib/ldb/ldb_tdb/ldb_tdb_wrap.c b/lib/ldb/ldb_tdb/ldb_tdb_wrap.c
new file mode 100644
index 0000000000..16a037a6c3
--- /dev/null
+++ b/lib/ldb/ldb_tdb/ldb_tdb_wrap.c
@@ -0,0 +1,165 @@
+/* 
+   ldb database library
+
+   Copyright (C) Andrew Tridgell  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 3 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, see <http://www.gnu.org/licenses/>.
+*/
+
+#include "ldb_tdb.h"
+#include "dlinklist.h"
+
+/* FIXME: TDB2 does this internally, so no need to wrap multiple opens! */
+#if BUILD_TDB2
+static void ltdb_log_fn(struct tdb_context *tdb,
+			enum tdb_log_level level,
+			const char *message,
+			struct ldb_context *ldb)
+{
+	enum ldb_debug_level ldb_level;
+	const char *name = tdb_name(tdb);
+
+	switch (level) {
+	case TDB_LOG_WARNING:
+		ldb_level = LDB_DEBUG_WARNING;
+	case TDB_LOG_USE_ERROR:
+	case TDB_LOG_ERROR:
+		ldb_level = LDB_DEBUG_FATAL;
+		break;
+	default:
+		ldb_level = LDB_DEBUG_FATAL;
+	}
+
+	ldb_debug(ldb, ldb_level, "ltdb: tdb(%s): %s", name, message);
+}
+#else /* !TDB2 */
+static void ltdb_log_fn(struct tdb_context *tdb, enum tdb_debug_level level, const char *fmt, ...) PRINTF_ATTRIBUTE(3, 4);
+static void ltdb_log_fn(struct tdb_context *tdb, enum tdb_debug_level level, const char *fmt, ...)
+{
+	va_list ap;
+	const char *name = tdb_name(tdb);
+	struct ldb_context *ldb = talloc_get_type(tdb_get_logging_private(tdb), struct ldb_context);
+	enum ldb_debug_level ldb_level;
+	char *message; 
+
+	if (ldb == NULL)
+		return;
+
+	va_start(ap, fmt);
+	message = talloc_vasprintf(ldb, fmt, ap);
+	va_end(ap);
+
+	switch (level) {
+	case TDB_DEBUG_FATAL:
+		ldb_level = LDB_DEBUG_FATAL;
+		break;
+	case TDB_DEBUG_ERROR:
+		ldb_level = LDB_DEBUG_ERROR;
+		break;
+	case TDB_DEBUG_WARNING:
+		ldb_level = LDB_DEBUG_WARNING;
+		break;
+	case TDB_DEBUG_TRACE:
+		ldb_level = LDB_DEBUG_TRACE;
+		break;
+	default:
+		ldb_level = LDB_DEBUG_FATAL;
+	}
+
+	ldb_debug(ldb, ldb_level, "ltdb: tdb(%s): %s", name, message);
+	talloc_free(message);
+}
+#endif
+
+/*
+  the purpose of this code is to work around the braindead posix locking
+  rules, to allow us to have a ldb open more than once while allowing
+  locking to work
+
+  TDB2 handles multiple opens, so we don't have this problem there.
+*/
+
+struct ltdb_wrap {
+	struct ltdb_wrap *next, *prev;
+	struct tdb_context *tdb;
+	dev_t device;
+	ino_t inode;
+};
+
+static struct ltdb_wrap *tdb_list;
+
+/* destroy the last connection to a tdb */
+static int ltdb_wrap_destructor(struct ltdb_wrap *w)
+{
+	tdb_close(w->tdb);
+	DLIST_REMOVE(tdb_list, w);
+	return 0;
+}
+
+/*
+  wrapped connection to a tdb database. The caller should _not_ free
+  this as it is not a talloc structure (as tdb does not use talloc
+  yet). It will auto-close when the caller frees the mem_ctx that is
+  passed to this call
+ */
+struct tdb_context *ltdb_wrap_open(TALLOC_CTX *mem_ctx,
+				   const char *path, int hash_size, 
+				   int tdb_flags,
+				   int open_flags, mode_t mode, 
+				   struct ldb_context *ldb)
+{
+	struct ltdb_wrap *w;
+	struct stat st;
+
+	if (stat(path, &st) == 0) {
+		for (w=tdb_list;w;w=w->next) {
+			if (st.st_dev == w->device && st.st_ino == w->inode) {
+				if (!talloc_reference(mem_ctx, w)) {
+					return NULL;
+				}
+				return w->tdb;
+			}
+		}
+	}
+
+	w = talloc(mem_ctx, struct ltdb_wrap);
+	if (w == NULL) {
+		return NULL;
+	}
+
+	w->tdb = tdb_open_compat(path, hash_size, tdb_flags, open_flags, mode, ltdb_log_fn, ldb);
+	if (w->tdb == NULL) {
+		talloc_free(w);
+		return NULL;
+	}
+
+	if (fstat(tdb_fd(w->tdb), &st) != 0) {
+		tdb_close(w->tdb);
+		talloc_free(w);
+		return NULL;
+	}
+
+	w->device = st.st_dev;
+	w->inode  = st.st_ino;
+
+	talloc_set_destructor(w, ltdb_wrap_destructor);
+
+	DLIST_ADD(tdb_list, w);
+	
+	return w->tdb;
+}