[WIP] [PATCH] Changes to indexing to handle maximum key lengths.

Gary Lockyer gary at catalyst.net.nz
Thu Feb 22 01:06:11 UTC 2018


As you've seen from Gamings post we've been working on adding an lmdb
back end to ldb.  Lmdb enforces a maximum key length, currently 511
bytes, these patches allow the current Samba indexing scheme to be used
with an lmdb back end.

This is a work in progress, I need to tidy up the code and add more tests.

Comments appreciated.

Thanks
Gary
-------------- next part --------------
From 5362ce87491d99d7587ea9e07a19bd058b1d969d Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Wed, 21 Feb 2018 15:20:17 +1300
Subject: [PATCH 1/6] ldb_tdb: Add support for an option to restrict the key
 length

This will allow emulation of a length-limited key DB for testing.

Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
 lib/ldb/ldb_tdb/ldb_tdb.c | 12 ++++++++++++
 lib/ldb/ldb_tdb/ldb_tdb.h |  5 +++++
 2 files changed, 17 insertions(+)

diff --git a/lib/ldb/ldb_tdb/ldb_tdb.c b/lib/ldb/ldb_tdb/ldb_tdb.c
index 16e4b8e..72c112a 100644
--- a/lib/ldb/ldb_tdb/ldb_tdb.c
+++ b/lib/ldb/ldb_tdb/ldb_tdb.c
@@ -1952,6 +1952,18 @@ static int ltdb_connect(struct ldb_context *ldb, const char *url,
 	}
 
 	*_module = module;
+
+	/*
+	 * Set the maximum key length
+	 */
+	{
+		const char *len_str =
+			ldb_options_find(ldb, options, "max_key_len");
+		if (len_str != NULL) {
+			unsigned len = strtoul(len_str, NULL, 0);
+			ltdb->max_key_length = len;
+		}
+	}
 	return LDB_SUCCESS;
 }
 
diff --git a/lib/ldb/ldb_tdb/ldb_tdb.h b/lib/ldb/ldb_tdb/ldb_tdb.h
index 7e18249..fffd46b 100644
--- a/lib/ldb/ldb_tdb/ldb_tdb.h
+++ b/lib/ldb/ldb_tdb/ldb_tdb.h
@@ -38,6 +38,11 @@ struct ltdb_private {
 	bool read_only;
 
 	const struct ldb_schema_syntax *GUID_index_syntax;
+
+	/*
+	 * Maximum key length
+	 */
+	unsigned max_key_length;
 };
 
 struct ltdb_context {
-- 
2.7.4


From eb872cc95dd683fc69988cfe9b7551c59bb0b2d4 Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Wed, 21 Feb 2018 15:18:11 +1300
Subject: [PATCH 2/6] ldb_tdb: Cope with key truncation

Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
 lib/ldb/ldb_tdb/ldb_index.c  | 277 +++++++++++++++++++++++++++++++++++++------
 lib/ldb/ldb_tdb/ldb_search.c |  14 +--
 2 files changed, 244 insertions(+), 47 deletions(-)

diff --git a/lib/ldb/ldb_tdb/ldb_index.c b/lib/ldb/ldb_tdb/ldb_index.c
index f2fce42..c5f5619 100644
--- a/lib/ldb/ldb_tdb/ldb_index.c
+++ b/lib/ldb/ldb_tdb/ldb_index.c
@@ -165,13 +165,20 @@ struct ltdb_idxptr {
 	int error;
 };
 
+enum key_truncation {
+	KEY_NOT_TRUNCATED,
+	KEY_POSSIBLY_TRUNCATED,
+	KEY_TRUNCATED,
+};
+
 static int ltdb_write_index_dn_guid(struct ldb_module *module,
 				    const struct ldb_message *msg,
 				    int add);
 static int ltdb_index_dn_base_dn(struct ldb_module *module,
 				 struct ltdb_private *ltdb,
 				 struct ldb_dn *base_dn,
-				 struct dn_list *dn_list);
+				 struct dn_list *dn_list,
+				 enum key_truncation *truncation);
 
 static void ltdb_dn_list_sort(struct ltdb_private *ltdb,
 			      struct dn_list *list);
@@ -183,6 +190,13 @@ static void ltdb_dn_list_sort(struct ltdb_private *ltdb,
 
 #define LTDB_GUID_INDEXING_VERSION 3
 
+static unsigned ltdb_max_key_length(struct ltdb_private *ltdb) {
+	if (ltdb->max_key_length == 0){
+		return UINT_MAX;
+	}
+	return ltdb->max_key_length;
+}
+
 /* enable the idxptr mode when transactions start */
 int ltdb_index_transaction_start(struct ldb_module *module)
 {
@@ -329,7 +343,8 @@ static struct dn_list *ltdb_index_idxptr(struct ldb_module *module, TDB_DATA rec
  */
 static int ltdb_dn_list_load(struct ldb_module *module,
 			     struct ltdb_private *ltdb,
-			     struct ldb_dn *dn, struct dn_list *list)
+			     struct ldb_dn *dn,
+			     struct dn_list *list)
 {
 	struct ldb_message *msg;
 	int ret, version;
@@ -423,7 +438,7 @@ normal_index:
 			return LDB_ERR_OPERATIONS_ERROR;
 		}
 
-		if (el->num_values != 1) {
+		if (el->num_values == 0) {
 			return LDB_ERR_OPERATIONS_ERROR;
 		}
 
@@ -459,13 +474,16 @@ int ltdb_key_dn_from_idx(struct ldb_module *module,
 {
 	struct ldb_context *ldb = ldb_module_get_ctx(module);
 	int ret;
+	int index = 0;
+	enum key_truncation truncation = KEY_NOT_TRUNCATED;
 	struct dn_list *list = talloc(mem_ctx, struct dn_list);
 	if (list == NULL) {
 		ldb_oom(ldb);
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
 
-	ret = ltdb_index_dn_base_dn(module, ltdb, dn, list);
+
+	ret = ltdb_index_dn_base_dn(module, ltdb, dn, list, &truncation);
 	if (ret != LDB_SUCCESS) {
 		TALLOC_FREE(list);
 		return ret;
@@ -475,22 +493,81 @@ int ltdb_key_dn_from_idx(struct ldb_module *module,
 		TALLOC_FREE(list);
 		return LDB_ERR_NO_SUCH_OBJECT;
 	}
-	if (list->count > 1) {
+
+	if (list->count > 1 && truncation == KEY_NOT_TRUNCATED)  {
 		const char *dn_str = ldb_dn_get_linearized(dn);
-		ldb_asprintf_errstring(ldb_module_get_ctx(module),
-				       __location__
-				       ": Failed to read DN index "
-				       "against %s for %s: too many "
-				       "values (%u > 1)",
-				       ltdb->cache->GUID_index_attribute,
-				       dn_str, list->count);
+		ldb_asprintf_errstring(
+			ldb_module_get_ctx(module),
+			__location__ ": Failed to read DN index against %s "
+			"for %s: too many values (%u > 1)",
+			ltdb->cache->GUID_index_attribute,
+			dn_str, list->count);
 		TALLOC_FREE(list);
 		return LDB_ERR_CONSTRAINT_VIOLATION;
 	}
 
+	if (list->count > 0 && truncation != KEY_NOT_TRUNCATED)  {
+		/*
+		 * DN key has been truncated, or is same length as a truncated
+		 * key, need to inspect the actual records to locate the
+		 * actual DN
+		 */
+		int i;
+		index = -1;
+		for (i=0; i < list->count; i++) {
+			uint8_t guid_key[LTDB_GUID_KEY_SIZE];
+			TDB_DATA key = {
+				.dptr = guid_key,
+				.dsize = sizeof(guid_key)
+			};
+			const int flags = LDB_UNPACK_DATA_FLAG_NO_ATTRS;
+			struct ldb_message *rec = ldb_msg_new(ldb);
+			if (rec == NULL) {
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+
+			ret = ltdb_idx_to_key(module, ltdb,
+					      ldb, &list->dn[i],
+					      &key);
+			if (ret != LDB_SUCCESS) {
+				return ret;
+			}
+
+			ret = ltdb_search_key(module, ltdb, key,
+					      rec, flags);
+			if (key.dptr != guid_key) {
+				TALLOC_FREE(key.dptr);
+			}
+			if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+				/*
+				 * the record has disappeared?
+				 * yes, this can happen
+				 */
+				talloc_free(rec);
+				continue;
+			}
+
+			if (ret != LDB_SUCCESS &&
+				ret != LDB_ERR_NO_SUCH_OBJECT) {
+				/* an internal error */
+				talloc_free(rec);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+
+			if (ldb_dn_compare(dn, rec->dn) == 0) {
+				index = i;
+				break;
+			}
+		}
+		if (index == -1) {
+			TALLOC_FREE(list);
+			return LDB_ERR_NO_SUCH_OBJECT;
+		}
+	}
+
 	/* The tdb_key memory is allocated by the caller */
 	ret = ltdb_guid_to_key(module, ltdb,
-			       &list->dn[0], tdb_key);
+			       &list->dn[index], tdb_key);
 	TALLOC_FREE(list);
 
 	if (ret != LDB_SUCCESS) {
@@ -743,7 +820,8 @@ int ltdb_index_transaction_cancel(struct ldb_module *module)
 static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
 				     struct ltdb_private *ltdb,
 				     const char *attr, const struct ldb_val *value,
-				     const struct ldb_schema_attribute **ap)
+				     const struct ldb_schema_attribute **ap,
+				     enum key_truncation *truncation)
 {
 	struct ldb_dn *ret;
 	struct ldb_val v;
@@ -752,6 +830,7 @@ static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
 	const char *attr_for_dn = NULL;
 	int r;
 	bool should_b64_encode;
+	unsigned max_key_length = ltdb_max_key_length(ltdb);
 
 	if (attr[0] == '@') {
 		attr_for_dn = attr;
@@ -813,17 +892,62 @@ static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
 
 	if (should_b64_encode) {
 		char *vstr = ldb_base64_encode(ldb, (char *)v.data, v.length);
+		unsigned vstr_len = 0;
+		unsigned key_len = 0;
+		unsigned attr_len = 0;
+		unsigned indx_len = 0;
+		unsigned frmt_len = 0;
 		if (!vstr) {
 			talloc_free(attr_folded);
 			return NULL;
 		}
-		ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s::%s", LTDB_INDEX,
-				     attr_for_dn, vstr);
+		vstr_len = strlen(vstr);
+		attr_len = strlen(attr_folded);
+		indx_len = strlen(LTDB_INDEX);
+		key_len = 3 + indx_len + attr_len + vstr_len;
+		if (key_len > max_key_length) {
+			unsigned excess = key_len - max_key_length;
+			frmt_len = vstr_len - excess;
+			*truncation = KEY_TRUNCATED;
+		} else {
+			frmt_len = vstr_len;
+			if (key_len == max_key_length) {
+				*truncation = KEY_POSSIBLY_TRUNCATED;
+			} else {
+				*truncation = KEY_NOT_TRUNCATED;
+			}
+		}
+
+		/*
+		 * Note: the double colon "::" is not a typo and indicates
+		 * that the following value is base64 encoded
+		 */
+		ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s::%.*s", LTDB_INDEX,
+				     attr_for_dn, frmt_len, vstr);
 		talloc_free(vstr);
 	} else {
+		unsigned attr_len = 0;
+		unsigned indx_len = 0;
+		unsigned key_len = 0;
+		unsigned frmt_len = 0;
+		attr_len = strlen(attr_for_dn);
+		indx_len = strlen(LTDB_INDEX);
+		key_len = 2 + indx_len + attr_len + (int)v.length;
+		if (key_len > max_key_length) {
+			unsigned excess = key_len - max_key_length;
+			frmt_len = v.length - excess;
+			*truncation = KEY_TRUNCATED;
+		} else {
+			frmt_len = v.length;
+			if (key_len == max_key_length) {
+				*truncation = KEY_POSSIBLY_TRUNCATED;
+			} else {
+				*truncation = KEY_NOT_TRUNCATED;
+			}
+		}
 		ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s", LTDB_INDEX,
 				     attr_for_dn,
-				     (int)v.length, (char *)v.data);
+				     frmt_len, (char *)v.data);
 	}
 
 	if (v.data != value->data) {
@@ -908,6 +1032,7 @@ static int ltdb_index_dn_simple(struct ldb_module *module,
 	struct ldb_context *ldb;
 	struct ldb_dn *dn;
 	int ret;
+	enum key_truncation truncation = KEY_NOT_TRUNCATED;
 
 	ldb = ldb_module_get_ctx(module);
 
@@ -924,7 +1049,7 @@ static int ltdb_index_dn_simple(struct ldb_module *module,
 	   search criterion */
 	dn = ltdb_index_key(ldb, ltdb,
 			    tree->u.equality.attr,
-			    &tree->u.equality.value, NULL);
+			    &tree->u.equality.value, NULL, &truncation);
 	if (!dn) return LDB_ERR_OPERATIONS_ERROR;
 
 	ret = ltdb_dn_list_load(module, ltdb, dn, list);
@@ -959,6 +1084,7 @@ static int ltdb_index_dn_leaf(struct ldb_module *module,
 		return LDB_SUCCESS;
 	}
 	if (ldb_attr_dn(tree->u.equality.attr) == 0) {
+		enum key_truncation truncation = KEY_NOT_TRUNCATED;
 		struct ldb_dn *dn
 			= ldb_dn_from_ldb_val(list,
 					      ldb_module_get_ctx(module),
@@ -977,7 +1103,8 @@ static int ltdb_index_dn_leaf(struct ldb_module *module,
 		 * We can't call TALLOC_FREE(dn) as this must belong
 		 * to list for the memory to remain valid.
 		 */
-		return ltdb_index_dn_base_dn(module, ltdb, dn, list);
+		return ltdb_index_dn_base_dn(module, ltdb, dn, list,
+					     &truncation);
 
 	} else if ((ltdb->cache->GUID_index_attribute != NULL) &&
 		   (ldb_attr_cmp(tree->u.equality.attr,
@@ -1380,7 +1507,8 @@ static int ltdb_index_dn_attr(struct ldb_module *module,
 			      struct ltdb_private *ltdb,
 			      const char *attr,
 			      struct ldb_dn *dn,
-			      struct dn_list *list)
+			      struct dn_list *list,
+			      enum key_truncation *truncation)
 {
 	struct ldb_context *ldb;
 	struct ldb_dn *key;
@@ -1392,7 +1520,7 @@ static int ltdb_index_dn_attr(struct ldb_module *module,
 	/* work out the index key from the parent DN */
 	val.data = (uint8_t *)((uintptr_t)ldb_dn_get_casefold(dn));
 	val.length = strlen((char *)val.data);
-	key = ltdb_index_key(ldb, ltdb, attr, &val, NULL);
+	key = ltdb_index_key(ldb, ltdb, attr, &val, NULL, truncation);
 	if (!key) {
 		ldb_oom(ldb);
 		return LDB_ERR_OPERATIONS_ERROR;
@@ -1417,12 +1545,14 @@ static int ltdb_index_dn_attr(struct ldb_module *module,
 static int ltdb_index_dn_one(struct ldb_module *module,
 			     struct ltdb_private *ltdb,
 			     struct ldb_dn *parent_dn,
-			     struct dn_list *list)
+			     struct dn_list *list,
+			     enum key_truncation *truncation)
 {
 	/* Ensure we do not shortcut on intersection for this list */
 	list->strict = true;
 	return ltdb_index_dn_attr(module, ltdb,
-				  LTDB_IDXONE, parent_dn, list);
+				  LTDB_IDXONE, parent_dn, list, truncation);
+
 }
 
 /*
@@ -1431,7 +1561,8 @@ static int ltdb_index_dn_one(struct ldb_module *module,
 static int ltdb_index_dn_base_dn(struct ldb_module *module,
 				 struct ltdb_private *ltdb,
 				 struct ldb_dn *base_dn,
-				 struct dn_list *dn_list)
+				 struct dn_list *dn_list,
+				 enum key_truncation *truncation)
 {
 	const struct ldb_val *guid_val = NULL;
 	if (ltdb->cache->GUID_index_attribute == NULL) {
@@ -1468,7 +1599,7 @@ static int ltdb_index_dn_base_dn(struct ldb_module *module,
 	}
 
 	return ltdb_index_dn_attr(module, ltdb,
-				  LTDB_IDXDN, base_dn, dn_list);
+				  LTDB_IDXDN, base_dn, dn_list, truncation);
 }
 
 /*
@@ -1520,7 +1651,8 @@ static int ltdb_index_dn(struct ldb_module *module,
 static int ltdb_index_filter(struct ltdb_private *ltdb,
 			     const struct dn_list *dn_list,
 			     struct ltdb_context *ac,
-			     uint32_t *match_count)
+			     uint32_t *match_count,
+			     bool trustworthy_base)
 {
 	struct ldb_context *ldb;
 	struct ldb_message *msg;
@@ -1571,7 +1703,7 @@ static int ltdb_index_filter(struct ltdb_private *ltdb,
 
 		/* We trust the index for SCOPE_ONELEVEL and SCOPE_BASE */
 		if ((ac->scope == LDB_SCOPE_ONELEVEL
-		     && ltdb->cache->one_level_indexes)
+		     && ltdb->cache->one_level_indexes && trustworthy_base)
 		    || ac->scope == LDB_SCOPE_BASE) {
 			ret = ldb_match_message(ldb, msg, ac->tree,
 						ac->scope, &matched);
@@ -1645,7 +1777,9 @@ int ltdb_search_indexed(struct ltdb_context *ac, uint32_t *match_count)
 	struct dn_list *dn_list;
 	int ret;
 	enum ldb_scope index_scope;
-
+	enum key_truncation truncation = KEY_NOT_TRUNCATED;
+	bool trustworthy_base = true;
+	
 	/* see if indexing is enabled */
 	if (!ltdb->cache->attribute_indexes &&
 	    !ltdb->cache->one_level_indexes &&
@@ -1679,7 +1813,7 @@ int ltdb_search_indexed(struct ltdb_context *ac, uint32_t *match_count)
 		 * this list, as we trust the BASE index
 		 */
 		ret = ltdb_index_dn_base_dn(ac->module, ltdb,
-					    ac->base, dn_list);
+					    ac->base, dn_list, &truncation);
 		if (ret != LDB_SUCCESS) {
 			talloc_free(dn_list);
 			return ret;
@@ -1692,12 +1826,16 @@ int ltdb_search_indexed(struct ltdb_context *ac, uint32_t *match_count)
 		 * the tree, we must ensure we strictly intersect with
 		 * this list, as we trust the ONELEVEL index
 		 */
-		ret = ltdb_index_dn_one(ac->module, ltdb, ac->base, dn_list);
+		ret = ltdb_index_dn_one(ac->module, ltdb, ac->base, dn_list, &truncation);
 		if (ret != LDB_SUCCESS) {
 			talloc_free(dn_list);
 			return ret;
 		}
 
+		if (truncation != KEY_NOT_TRUNCATED) {
+			trustworthy_base = false;
+		}
+
 		/*
 		 * If we have too many matches, running the filter
 		 * tree over the SCOPE_ONELEVEL can be quite expensive
@@ -1761,7 +1899,7 @@ int ltdb_search_indexed(struct ltdb_context *ac, uint32_t *match_count)
 		break;
 	}
 
-	ret = ltdb_index_filter(ltdb, dn_list, ac, match_count);
+	ret = ltdb_index_filter(ltdb, dn_list, ac, match_count, trustworthy_base);
 	talloc_free(dn_list);
 	return ret;
 }
@@ -1797,6 +1935,8 @@ static int ltdb_index_add1(struct ldb_module *module,
 	const struct ldb_schema_attribute *a;
 	struct dn_list *list;
 	unsigned alloc_len;
+	enum key_truncation truncation = KEY_TRUNCATED;
+
 
 	ldb = ldb_module_get_ctx(module);
 
@@ -1806,7 +1946,7 @@ static int ltdb_index_add1(struct ldb_module *module,
 	}
 
 	dn_key = ltdb_index_key(ldb, ltdb,
-				el->name, &el->values[v_idx], &a);
+				el->name, &el->values[v_idx], &a, &truncation);
 	if (!dn_key) {
 		talloc_free(list);
 		return LDB_ERR_OPERATIONS_ERROR;
@@ -1826,8 +1966,7 @@ static int ltdb_index_add1(struct ldb_module *module,
 	if (list->count > 0 &&
 	    ((a != NULL
 	      && (a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX ||
-		 (el->flags & LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX))) ||
-	     ldb_attr_cmp(el->name, LTDB_IDXDN) == 0)) {
+		  (el->flags & LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX))))) {
 		/*
 		 * We do not want to print info about a possibly
 		 * confidential DN that the conflict was with in the
@@ -1848,6 +1987,72 @@ static int ltdb_index_add1(struct ldb_module *module,
 		return LDB_ERR_CONSTRAINT_VIOLATION;
 	}
 
+	if (list->count > 0 && ldb_attr_cmp(el->name, LTDB_IDXDN) == 0 &&
+		truncation == KEY_NOT_TRUNCATED) {
+
+		ldb_asprintf_errstring(ldb,
+				       __location__ ": DN %s already exists",
+				       ldb_dn_get_linearized(msg->dn));
+			return LDB_ERR_CONSTRAINT_VIOLATION;
+
+	} else if (list->count > 0 && ldb_attr_cmp(el->name, LTDB_IDXDN) == 0) {
+		/*
+		 * More than one entry in the index, which arises when the
+		 * DN indexes have been truncated
+		 *
+		 * So need to pull the DN's to check if it's really a duplicate
+		 */
+		int i;
+		for (i=0; i < list->count; i++) {
+			uint8_t guid_key[LTDB_GUID_KEY_SIZE];
+			TDB_DATA key = {
+				.dptr = guid_key,
+				.dsize = sizeof(guid_key)
+			};
+			const int flags = LDB_UNPACK_DATA_FLAG_NO_ATTRS;
+			struct ldb_message *rec = ldb_msg_new(ldb);
+			if (rec == NULL) {
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+
+			ret = ltdb_idx_to_key(module, ltdb,
+					      ldb, &list->dn[i],
+					      &key);
+			if (ret != LDB_SUCCESS) {
+				talloc_free(rec);
+				return ret;
+			}
+
+			ret = ltdb_search_key(module, ltdb, key,
+					      rec, flags);
+			if (key.dptr != guid_key) {
+				TALLOC_FREE(key.dptr);
+			}
+			if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+				/*
+				 * the record has disappeared?
+				 * yes, this can happen
+				 */
+				talloc_free(rec);
+				continue;
+			}
+
+			if (ret != LDB_SUCCESS && ret != LDB_ERR_NO_SUCH_OBJECT) {
+				/* an internal error */
+				talloc_free(rec);
+				return LDB_ERR_OPERATIONS_ERROR;
+			}
+			if (ldb_dn_compare(msg->dn, rec->dn) == 0) {
+				talloc_free(rec);
+				ldb_asprintf_errstring
+					(ldb,
+					__location__ ": DN %s already exists",
+					ldb_dn_get_linearized(msg->dn));
+				return LDB_ERR_CONSTRAINT_VIOLATION;
+			}
+		}
+	}
+
 	/* overallocate the list a bit, to reduce the number of
 	 * realloc trigered copies */
 	alloc_len = ((list->count+1)+7) & ~7;
@@ -2164,6 +2369,7 @@ int ltdb_index_del_value(struct ldb_module *module,
 	unsigned int j;
 	struct dn_list *list;
 	struct ldb_dn *dn = msg->dn;
+	enum key_truncation truncation = KEY_NOT_TRUNCATED;
 
 	ldb = ldb_module_get_ctx(module);
 
@@ -2177,7 +2383,8 @@ int ltdb_index_del_value(struct ldb_module *module,
 	}
 
 	dn_key = ltdb_index_key(ldb, ltdb,
-				el->name, &el->values[v_idx], NULL);
+				el->name, &el->values[v_idx],
+				NULL, &truncation);
 	if (!dn_key) {
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
diff --git a/lib/ldb/ldb_tdb/ldb_search.c b/lib/ldb/ldb_tdb/ldb_search.c
index 0af230f..d8bf865 100644
--- a/lib/ldb/ldb_tdb/ldb_search.c
+++ b/lib/ldb/ldb_tdb/ldb_search.c
@@ -292,19 +292,9 @@ int ltdb_search_dn1(struct ldb_module *module, struct ldb_dn *dn, struct ldb_mes
 	};
 	TALLOC_CTX *tdb_key_ctx = NULL;
 
-	if (ltdb->cache->GUID_index_attribute == NULL) {
-		tdb_key_ctx = talloc_new(msg);
-		if (!tdb_key_ctx) {
-			return ldb_module_oom(module);
-		}
+	if (ltdb->cache->GUID_index_attribute == NULL ||
+		ldb_dn_is_special(dn)) {
 
-		/* form the key */
-		tdb_key = ltdb_key_dn(module, tdb_key_ctx, dn);
-		if (!tdb_key.dptr) {
-			TALLOC_FREE(tdb_key_ctx);
-			return LDB_ERR_OPERATIONS_ERROR;
-		}
-	} else if (ldb_dn_is_special(dn)) {
 		tdb_key_ctx = talloc_new(msg);
 		if (!tdb_key_ctx) {
 			return ldb_module_oom(module);
-- 
2.7.4


From 10000c3e21e706169c9fe5178043be44d2208746 Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Wed, 21 Feb 2018 15:19:37 +1300
Subject: [PATCH 3/6] ldb_tdb: Refuse to store a value in a unique index that
 is too long

Rather than add many special cases, over-long unique values are simply banned.

Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
 lib/ldb/ldb_tdb/ldb_index.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/lib/ldb/ldb_tdb/ldb_index.c b/lib/ldb/ldb_tdb/ldb_index.c
index c5f5619..530c0c5 100644
--- a/lib/ldb/ldb_tdb/ldb_index.c
+++ b/lib/ldb/ldb_tdb/ldb_index.c
@@ -1951,6 +1951,25 @@ static int ltdb_index_add1(struct ldb_module *module,
 		talloc_free(list);
 		return LDB_ERR_OPERATIONS_ERROR;
 	}
+	/*
+	 * Samba only maintains unique indexes on the objectSID on objectGUID
+	 * so if a unique index key exceeds the maximum length there is a
+	 * problem.
+	 */
+	if ((truncation == KEY_TRUNCATED) && (a != NULL &&
+		(a->flags & LDB_ATTR_FLAG_UNIQUE_INDEX ||
+		(el->flags & LDB_FLAG_INTERNAL_FORCE_UNIQUE_INDEX)))) {
+
+		ldb_asprintf_errstring(
+			ldb,
+			__location__ ": unique index key on %s in %s, "
+			"exceeds maximum key length of %u (encoded).",
+			el->name,
+			ldb_dn_get_linearized(msg->dn),
+			ltdb->max_key_length);
+		talloc_free(list);
+		return LDB_ERR_CONSTRAINT_VIOLATION;
+	}
 	talloc_steal(list, dn_key);
 
 	ret = ltdb_dn_list_load(module, ltdb, dn_key, list);
-- 
2.7.4


From cae02bfb117fc171e6f258c82db637f9924f103b Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Wed, 21 Feb 2018 15:12:40 +1300
Subject: [PATCH 4/6] ldb_tdb: Add tests for truncated DN index keys

Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
 lib/ldb/tests/python/index.py | 526 ++++++++++++++++++++++++++++++++++++++++++
 lib/ldb/wscript               |   2 +-
 2 files changed, 527 insertions(+), 1 deletion(-)
 create mode 100755 lib/ldb/tests/python/index.py

diff --git a/lib/ldb/tests/python/index.py b/lib/ldb/tests/python/index.py
new file mode 100755
index 0000000..a83fa85
--- /dev/null
+++ b/lib/ldb/tests/python/index.py
@@ -0,0 +1,526 @@
+#!/usr/bin/env python
+
+import os
+from unittest import TestCase
+import sys
+import ldb
+import shutil
+
+PY3 = sys.version_info > (3, 0)
+
+
+def tempdir():
+    import tempfile
+    try:
+        dir_prefix = os.path.join(os.environ["SELFTEST_PREFIX"], "tmp")
+    except KeyError:
+        dir_prefix = None
+    return tempfile.mkdtemp(dir=dir_prefix)
+
+
+def contains(result, dn):
+    if result is None:
+        return False
+
+    filtered = filter(lambda x: str(x["dn"]) == dn, result)
+    return len(filtered) == 1
+
+
+class MaxIndexKeyLengthTests(TestCase):
+
+    def tearDown(self):
+        shutil.rmtree(self.testdir)
+        super(MaxIndexKeyLengthTests, self).tearDown()
+
+        # Ensure the LDB is closed now, so we close the FD
+        del(self.l)
+
+    def setUp(self):
+        super(MaxIndexKeyLengthTests, self).setUp()
+        self.testdir = tempdir()
+        self.filename = os.path.join(self.testdir, "key_len_test.ldb")
+        # Note that the maximum key length is set to 50
+        self.l = ldb.Ldb(self.filename,
+                         options=["modules:rdn_name", "max_key_len:50"])
+        self.l.add({"dn": "@ATTRIBUTES",
+                    "uniqueThing": "UNIQUE_INDEX"})
+        self.l.add({"dn": "@INDEXLIST",
+                    "@IDXATTR": [b"uniqueThing"],
+                    "@IDXONE": [b"1"],
+                    "@IDXGUID": [b"objectUUID"],
+                    "@IDX_DN_GUID": [b"GUID"]})
+
+    # Add a value to a unique index that exceeds the maximum key length
+    # This should be rejected.
+    def test_add_long_unique_add(self):
+        try:
+            self.l.add({"dn": "OU=UNIQUE_MAX_LEN,DC=SAMBA,DC=ORG",
+                        "name": b"Admins",
+                        "x": "z", "y": "a",
+                        "objectUUID": b"0123456789abcdef",
+                        "uniqueThing": "01234567890123456789012345678901"})
+            # index key will be
+            # "@INDEX:UNIQUETHING:01234567890123456789012345678901"
+            self.fail("Should have failed on long index key")
+
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_CONSTRAINT_VIOLATION)
+
+    # Test that DN's longer the maximum key length can be added
+    # and that duplicate DN's are rejected correctly
+    def test_add_long_dn_add(self):
+        #
+        # For all entries the DN index key gets truncated to
+        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA
+        #
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcdef"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde0"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde1"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde5"})
+
+        # This key should not get truncated, as it's one character less than
+        # max
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXX,DC=SAMBA",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde7"})
+
+        try:
+            self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG",
+                        "name": b"Admins",
+                        "x": "z", "y": "a",
+                        "objectUUID": b"0123456789abcde2"})
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_ENTRY_ALREADY_EXISTS)
+
+        try:
+            self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=COM",
+                        "name": b"Admins",
+                        "x": "z", "y": "a",
+                        "objectUUID": b"0123456789abcde3"})
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_ENTRY_ALREADY_EXISTS)
+
+        try:
+            self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV",
+                        "name": b"Admins",
+                        "x": "z", "y": "a",
+                        "objectUUID": b"0123456789abcde4"})
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_ENTRY_ALREADY_EXISTS)
+
+        try:
+            self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+                        "name": b"Admins",
+                        "x": "z", "y": "a",
+                        "objectUUID": b"0123456789abcde6"})
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_ENTRY_ALREADY_EXISTS)
+
+        try:
+            self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXX,DC=SAMBA",
+                        "name": b"Admins",
+                        "x": "z", "y": "a",
+                        "objectUUID": b"0123456789abcde8"})
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_ENTRY_ALREADY_EXISTS)
+
+    def test_rename_truncated_dn_keys(self):
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcdef"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde0"})
+
+        # Non conflicting rename, should suceed
+        self.l.rename("OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=ORG",
+                      "OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+
+        try:
+            self.l.rename("OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=COM",
+                          "OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_ENTRY_ALREADY_EXISTS)
+
+    def test_delete_truncated_dn_keys(self):
+        #
+        # For all entries the DN index key gets truncated to
+        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA
+        #
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcdef"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde1"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde5"})
+
+        # Try to delete a non existent DN with a truncated key
+        try:
+            self.l.delete("OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=COM")
+        except ldb.LdbError as err:
+            enum = err.args[0]
+            self.assertEqual(enum, ldb.ERR_NO_SUCH_OBJECT)
+            # Ensure that non of the other truncated DN's got deleted
+            res = self.l.search(
+                base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG")
+            self.assertEqual(len(res), 1)
+
+            res = self.l.search(
+                base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+            self.assertEqual(len(res), 1)
+
+            res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA")
+            self.assertEqual(len(res), 1)
+
+        # delete an existing entry
+        self.l.delete("OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG")
+
+        # Ensure it got deleted
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG")
+        self.assertEqual(len(res), 0)
+
+        # Ensure that non of the other truncated DN's got deleted
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+        self.assertEqual(len(res), 1)
+
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA")
+        self.assertEqual(len(res), 1)
+
+        # delete an existing entry
+        self.l.delete("OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+
+        # Ensure it got deleted
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+        self.assertEqual(len(res), 0)
+
+        # Ensure that non of the other truncated DN's got deleted
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA")
+        self.assertEqual(len(res), 1)
+
+        # delete an existing entry
+        self.l.delete("OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA")
+
+        # Ensure it got deleted
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBAxxx")
+        self.assertEqual(len(res), 0)
+
+    def test_search_truncated_dn_keys(self):
+        #
+        # For all entries the DN index key gets truncated to
+        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA
+        #
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcdef"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde1"})
+
+        self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde5"})
+
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG")
+        self.assertEqual(len(res), 1)
+
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+        self.assertEqual(len(res), 1)
+
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA")
+        self.assertEqual(len(res), 1)
+
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=COM")
+        self.assertEqual(len(res), 0)
+
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXX,DC=SAMBA,DC=GOV")
+        self.assertEqual(len(res), 0)
+
+        # Non existent, key one less than truncation limit
+        res = self.l.search(base="OU=A_LONG_DNXXXXXXXXXXXXXX,DC=SAMBA")
+        self.assertEqual(len(res), 0)
+
+    def test_search_one_level_truncated_dn_keys(self):
+        #
+        # For all entries the DN index key gets truncated to
+        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=
+        #
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcdef"})
+
+        self.l.add({"dn": "OU=01,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde1"})
+
+        self.l.add({"dn": "OU=02,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde2"})
+
+        self.l.add({"dn": "OU=03,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde3"})
+
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde4"})
+
+        self.l.add({"dn": "OU=04,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde5"})
+
+        self.l.add({"dn": "OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde6"})
+
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde7"})
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                            scope=ldb.SCOPE_ONELEVEL)
+        self.assertEqual(len(res), 3)
+        self.assertTrue(
+            contains(res, "OU=01,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+        self.assertTrue(
+            contains(res, "OU=02,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+        self.assertTrue(
+            contains(res, "OU=03,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                            scope=ldb.SCOPE_ONELEVEL)
+        self.assertEqual(len(res), 2)
+        self.assertTrue(
+            contains(res, "OU=04,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+        self.assertTrue(
+            contains(res, "OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV",
+                            scope=ldb.SCOPE_ONELEVEL)
+        self.assertEqual(len(res), 0)
+
+    def test_search_sub_tree_truncated_dn_keys(self):
+        #
+        # For all entries the DN index key gets truncated to
+        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=
+        #
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcdef"})
+
+        self.l.add({"dn": "OU=01,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde1"})
+
+        self.l.add({"dn": "OU=02,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde2"})
+
+        self.l.add({"dn": "OU=03,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde3"})
+
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde4"})
+
+        self.l.add({"dn": "OU=04,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde5"})
+
+        self.l.add({"dn": "OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde6"})
+
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde7"})
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                            scope=ldb.SCOPE_SUBTREE)
+        self.assertEqual(len(res), 4)
+        self.assertTrue(
+            contains(res, "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+        self.assertTrue(
+            contains(res, "OU=01,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+        self.assertTrue(
+            contains(res, "OU=02,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+        self.assertTrue(
+            contains(res, "OU=03,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                            scope=ldb.SCOPE_SUBTREE)
+        self.assertEqual(len(res), 3)
+        self.assertTrue(
+            contains(res, "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+        self.assertTrue(
+            contains(res, "OU=04,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+        self.assertTrue(
+            contains(res, "OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV",
+                            scope=ldb.SCOPE_SUBTREE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV"))
+
+    def test_search_base_truncated_dn_keys(self):
+        #
+        # For all entries the DN index key gets truncated to
+        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=
+        #
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcdef"})
+
+        self.l.add({"dn": "OU=01,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde1"})
+
+        self.l.add({"dn": "OU=02,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde2"})
+
+        self.l.add({"dn": "OU=03,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde3"})
+
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde4"})
+
+        self.l.add({"dn": "OU=04,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde5"})
+
+        self.l.add({"dn": "OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde6"})
+
+        self.l.add({"dn": "OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV",
+                    "name": b"Admins",
+                    "x": "z", "y": "a",
+                    "objectUUID": b"0123456789abcde7"})
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+                            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+
+        res = self.l.search(
+            base="OU=01,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=01,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+
+        res = self.l.search(
+            base="OU=02,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=02,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+
+        res = self.l.search(
+            base="OU=03,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
+            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=03,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG"))
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+                            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+
+        res = self.l.search(
+            base="OU=04,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=04,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+
+        res = self.l.search(
+            base="OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM",
+            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+        self.assertTrue(
+            contains(res, "OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=COM"))
+
+        # Test single truncated value
+        # TODO write a meaningful comment
+        res = self.l.search(
+            base="OU=05,OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=GOV",
+            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 0)
+
+        res = self.l.search(base="OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV",
+                            scope=ldb.SCOPE_BASE)
+        self.assertEqual(len(res), 1)
+
+
+if __name__ == '__main__':
+    import unittest
+    unittest.TestProgram()
diff --git a/lib/ldb/wscript b/lib/ldb/wscript
index 8ae5be3..fc5feae 100644
--- a/lib/ldb/wscript
+++ b/lib/ldb/wscript
@@ -374,7 +374,7 @@ def test(ctx):
     if not os.path.exists(tmp_dir):
         os.mkdir(tmp_dir)
     pyret = samba_utils.RUN_PYTHON_TESTS(
-        ['tests/python/api.py'],
+        ['tests/python/api.py', 'tests/python/index.py'],
         extra_env={'SELFTEST_PREFIX': test_prefix})
     print("Python testsuite returned %d" % pyret)
 
-- 
2.7.4


From f9031f7b956e59b0616861b0a0c7d585885ba765 Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Thu, 22 Feb 2018 08:29:14 +1300
Subject: [PATCH 5/6] fix up tests

Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
 lib/ldb/tests/python/index.py | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

diff --git a/lib/ldb/tests/python/index.py b/lib/ldb/tests/python/index.py
index a83fa85..9434dd1 100755
--- a/lib/ldb/tests/python/index.py
+++ b/lib/ldb/tests/python/index.py
@@ -1,4 +1,28 @@
 #!/usr/bin/env python
+#
+# Tests for truncated index keys
+#
+#   Copyright (C) Andrew Bartlett <abartlet at samba.org> 2018
+#
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program 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 General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.
+#
+"""Tests for truncated index keys
+
+Databases such as lmdb have a maximum key length, these tests ensure that
+ldb behaves correctly in those circumstances.
+
+"""
 
 import os
 from unittest import TestCase
@@ -23,6 +47,9 @@ def contains(result, dn):
         return False
 
     filtered = filter(lambda x: str(x["dn"]) == dn, result)
+    if filtered is None:
+        return False
+
     return len(filtered) == 1
 
 
-- 
2.7.4


From 11dffee682e97ba447e1b253a1251a92ba1ec6cc Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Thu, 22 Feb 2018 10:56:40 +1300
Subject: [PATCH 6/6] fix up tests

Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
 lib/ldb/tests/python/index.py | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

diff --git a/lib/ldb/tests/python/index.py b/lib/ldb/tests/python/index.py
index 9434dd1..9a9c7de 100755
--- a/lib/ldb/tests/python/index.py
+++ b/lib/ldb/tests/python/index.py
@@ -46,11 +46,10 @@ def contains(result, dn):
     if result is None:
         return False
 
-    filtered = filter(lambda x: str(x["dn"]) == dn, result)
-    if filtered is None:
-        return False
-
-    return len(filtered) == 1
+    for r in result:
+        if str(r["dn"]) == dn:
+            return True
+    return False
 
 
 class MaxIndexKeyLengthTests(TestCase):
@@ -174,6 +173,8 @@ class MaxIndexKeyLengthTests(TestCase):
             self.assertEqual(enum, ldb.ERR_ENTRY_ALREADY_EXISTS)
 
     def test_rename_truncated_dn_keys(self):
+        # For all entries the DN index key gets truncated to
+        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA
         self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=ORG",
                     "name": b"Admins",
                     "x": "z", "y": "a",
@@ -184,10 +185,11 @@ class MaxIndexKeyLengthTests(TestCase):
                     "x": "z", "y": "a",
                     "objectUUID": b"0123456789abcde0"})
 
-        # Non conflicting rename, should suceed
+        # Non conflicting rename, should succeed
         self.l.rename("OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=ORG",
                       "OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=GOV")
 
+        # Conflicting rename should fail
         try:
             self.l.rename("OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=COM",
                           "OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=GOV")
@@ -307,7 +309,7 @@ class MaxIndexKeyLengthTests(TestCase):
     def test_search_one_level_truncated_dn_keys(self):
         #
         # For all entries the DN index key gets truncated to
-        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=
+        # @INDEX:@IDXDN:OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=
         #
         self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
                     "name": b"Admins",
@@ -344,6 +346,7 @@ class MaxIndexKeyLengthTests(TestCase):
                     "x": "z", "y": "a",
                     "objectUUID": b"0123456789abcde6"})
 
+        # This key is not truncated as it's one less than the max_key_len
         self.l.add({"dn": "OU=A_LONG_DN_ONE_LVL,DC=SAMBA,DC=GOV",
                     "name": b"Admins",
                     "x": "z", "y": "a",
@@ -374,7 +377,7 @@ class MaxIndexKeyLengthTests(TestCase):
     def test_search_sub_tree_truncated_dn_keys(self):
         #
         # For all entries the DN index key gets truncated to
-        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=
+        # @INDEX:@IDXDN:OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=
         #
         self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
                     "name": b"Admins",
@@ -447,7 +450,7 @@ class MaxIndexKeyLengthTests(TestCase):
     def test_search_base_truncated_dn_keys(self):
         #
         # For all entries the DN index key gets truncated to
-        # @INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXX,DC=SAMBA,DC=
+        # @INDEX:@IDXDN:OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=
         #
         self.l.add({"dn": "OU=A_LONG_DN_ONE_LEVELX,DC=SAMBA,DC=ORG",
                     "name": b"Admins",
-- 
2.7.4

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 473 bytes
Desc: OpenPGP digital signature
URL: <http://lists.samba.org/pipermail/samba-technical/attachments/20180222/b93f8ca0/signature.sig>


More information about the samba-technical mailing list