[PATCH] Changes to indexing to handle maximum key lengths.
Gary Lockyer
gary at catalyst.net.nz
Tue Feb 27 00:08:42 UTC 2018
Updated patch set attached.
On 27/02/18 12:01, Andrew Bartlett via samba-technical wrote:
> On Tue, 2018-02-27 at 11:44 +1300, Gary Lockyer via samba-technical
> wrote:
>> Attached is the completed patch set ready for review and possibly push.
>>
>> 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.
>>
>>
>> Review and or comments appreciated.
>
> G'Day Gary,
>
> Looking over the tests, one thing that comes to mind is that there is
> no way you currently prove that the key truncation is actually
> happening. I'm concerned that instead of breaking the index layer,
> what could be broken is the option parsing in LDB (as this is the only
> user) and these tests could be rendered ineffective.
>
> Could you please read the actual index values and check they are set as
> expected?
>
> This will also nicely test the layout of the GUID index mode, which
> would be great as well.
>
> You are also missing a h here (ldb_tdb.h):
> + * than this lengt will be rejected.
>
> Also, rather than use a bool here:
>
> 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)
>
> I think it would be better to pass it in as 'enum key_truncation
> *scope_index_truncation' from ltdb_search_indexed() to
> ltdb_index_filter.
>
> Finally, in ltdb_index_add1()
> + /*
> + * More than one entry in the DN->GUID 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
> + */
>
> That comment needs to say 'At least one existing entry...', not 'more
> than one' as we are trying to add the second entry here and it may or
> may not be a duplicate.
>
> This is a really important step towards LMDB support, and I really appreciate it.
>
> Thanks!
>
> Andrew Bartlett
>
-------------- next part --------------
From c2911cc0f6a6a0758c36977496c896ecf5fee09c 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
Allow the setting of the maximum key length, this allows the testing of
index key truncation code. Index key truncation is required to allow
the samba indexing scheme to be used with backends that enforce a
maximum 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 | 7 +++++++
2 files changed, 19 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..421ae4d 100644
--- a/lib/ldb/ldb_tdb/ldb_tdb.h
+++ b/lib/ldb/ldb_tdb/ldb_tdb.h
@@ -38,6 +38,13 @@ struct ltdb_private {
bool read_only;
const struct ldb_schema_syntax *GUID_index_syntax;
+
+ /*
+ * Maximum index key length. If non zero keys longer than this length
+ * will be truncated for non unique indexes. Keys for unique indexes
+ * greater than this length will be rejected.
+ */
+ unsigned max_key_length;
};
struct ltdb_context {
--
2.7.4
From 8d4d433267708013d97f7d296dca788193d9cb56 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
Modify the indexing code to handle a maximum key length, index keys
greater than the maximum length will be truncated to the maximum length.
And the unuque index code has been altered to handle multiple records
for the same index key.
Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
lib/ldb/ldb_tdb/ldb_index.c | 261 +++++++++++++++++++++++++++++++++++++++-----
1 file changed, 233 insertions(+), 28 deletions(-)
diff --git a/lib/ldb/ldb_tdb/ldb_index.c b/lib/ldb/ldb_tdb/ldb_index.c
index 99fef23..e199a72 100644
--- a/lib/ldb/ldb_tdb/ldb_index.c
+++ b/lib/ldb/ldb_tdb/ldb_index.c
@@ -165,13 +165,19 @@ struct ltdb_idxptr {
int error;
};
+enum key_truncation {
+ KEY_NOT_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 +189,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)
{
@@ -423,7 +436,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 +472,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,7 +491,8 @@ 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__
@@ -488,9 +505,71 @@ int ltdb_key_dn_from_idx(struct ldb_module *module,
return LDB_ERR_CONSTRAINT_VIOLATION;
}
+ if (list->count > 0 && truncation == KEY_TRUNCATED) {
+ /*
+ * DN key has been truncated, 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) {
+ TALLOC_FREE(list);
+ 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);
+ TALLOC_FREE(list);
+ return LDB_ERR_OPERATIONS_ERROR;
+ }
+
+ if (ldb_dn_compare(dn, rec->dn) == 0) {
+ index = i;
+ TALLOC_FREE(rec);
+ 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 +822,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 +832,11 @@ 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);
+ unsigned key_len = 0;
+ unsigned attr_len = 0;
+ unsigned indx_len = 0;
+ unsigned frmt_len = 0;
if (attr[0] == '@') {
attr_for_dn = attr;
@@ -788,6 +873,8 @@ static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
return NULL;
}
}
+ attr_len = strlen(attr_for_dn);
+ indx_len = strlen(LTDB_INDEX);
/*
* We do not base 64 encode a DN in a key, it has already been
@@ -812,18 +899,59 @@ static struct ldb_dn *ltdb_index_key(struct ldb_context *ldb,
}
if (should_b64_encode) {
+ unsigned vstr_len = 0;
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_for_dn, vstr);
+ vstr_len = strlen(vstr);
+ 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;
+ /*
+ * Note: the double hash "##" is not a typo and
+ * indicates that the following value is base64 encoded
+ * Truncated keys are placed in a separate key space
+ * from the non truncated keys
+ */
+ ret = ldb_dn_new_fmt(ldb, ldb, "%s#%s##%.*s",
+ LTDB_INDEX, attr_for_dn,
+ frmt_len, vstr);
+ } else {
+ frmt_len = vstr_len;
+ *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 {
- ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s", LTDB_INDEX,
- attr_for_dn,
- (int)v.length, (char *)v.data);
+ 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;
+ /*
+ * Truncated keys are placed in a separate key space
+ * from the non truncated keys
+ */
+ ret = ldb_dn_new_fmt(ldb, ldb, "%s#%s#%.*s",
+ LTDB_INDEX, attr_for_dn,
+ frmt_len, (char *)v.data);
+ } else {
+ frmt_len = v.length;
+ *truncation = KEY_NOT_TRUNCATED;
+ ret = ldb_dn_new_fmt(ldb, ldb, "%s:%s:%.*s",
+ LTDB_INDEX, attr_for_dn,
+ frmt_len, (char *)v.data);
+ }
}
if (v.data != value->data) {
@@ -908,6 +1036,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 +1053,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 +1088,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 +1107,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 +1511,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 +1524,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 +1549,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 +1565,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 +1603,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 +1655,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,
+ enum key_truncation truncation)
{
struct ldb_context *ldb;
struct ldb_message *msg;
@@ -1569,9 +1705,13 @@ static int ltdb_index_filter(struct ltdb_private *ltdb,
return LDB_ERR_OPERATIONS_ERROR;
}
- /* We trust the index for SCOPE_ONELEVEL and SCOPE_BASE */
+ /*
+ * We trust the index for SCOPE_BASE, and for LDB_SCOPE_ONELEVEL
+ * unless the index key has been truncated.
+ */
if ((ac->scope == LDB_SCOPE_ONELEVEL
- && ltdb->cache->one_level_indexes)
+ && ltdb->cache->one_level_indexes
+ && truncation == KEY_NOT_TRUNCATED)
|| ac->scope == LDB_SCOPE_BASE) {
ret = ldb_match_message(ldb, msg, ac->tree,
ac->scope, &matched);
@@ -1645,6 +1785,7 @@ 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;
/* see if indexing is enabled */
if (!ltdb->cache->attribute_indexes &&
@@ -1679,7 +1820,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,7 +1833,7 @@ 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;
@@ -1761,7 +1902,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, truncation);
talloc_free(dn_list);
return ret;
}
@@ -1797,6 +1938,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 +1949,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;
@@ -1827,9 +1970,69 @@ static int ltdb_index_add1(struct ldb_module *module,
* messages.
*/
if (list->count > 0 &&
- ldb_attr_cmp(el->name, LTDB_IDXDN) == 0) {
+ ldb_attr_cmp(el->name, LTDB_IDXDN) == 0 &&
+ truncation == KEY_NOT_TRUNCATED) {
+
talloc_free(list);
return LDB_ERR_CONSTRAINT_VIOLATION;
+
+ } else if (list->count > 0
+ && ldb_attr_cmp(el->name, LTDB_IDXDN) == 0) {
+
+ /*
+ * At least one existing entry in the DN->GUID 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(list);
+ 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);
+ TALLOC_FREE(list);
+ return LDB_ERR_OPERATIONS_ERROR;
+ }
+ if (ldb_dn_compare(msg->dn, rec->dn) == 0) {
+ TALLOC_FREE(rec);
+ TALLOC_FREE(list);
+ return LDB_ERR_CONSTRAINT_VIOLATION;
+ }
+ }
}
/*
@@ -2203,6 +2406,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);
@@ -2216,7 +2420,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;
}
--
2.7.4
From 47aee09333ba142762de0b753325383d0a18517c Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Tue, 27 Feb 2018 10:01:38 +1300
Subject: [PATCH 3/6] ldb_tdb: Combine identical not GUID index and special DN
cases
Fold together two identical cases to simplify the code.
Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
lib/ldb/ldb_tdb/ldb_search.c | 14 ++------------
1 file changed, 2 insertions(+), 12 deletions(-)
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 7d91bcb29bc0d15b2b57ea94ef00388849915101 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 4/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 e199a72..53acc00 100644
--- a/lib/ldb/ldb_tdb/ldb_index.c
+++ b/lib/ldb/ldb_tdb/ldb_index.c
@@ -1954,6 +1954,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 and 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 7d50bd1a252b8dd89f4eb11f640a33ca5eab1891 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 5/6] ldb_tdb: Add tests for truncated index keys
Tests for the index truncation code.
Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
lib/ldb/tests/python/index.py | 715 ++++++++++++++++++++++++++++++++++++++++++
lib/ldb/wscript | 2 +-
2 files changed, 716 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..8ffceda
--- /dev/null
+++ b/lib/ldb/tests/python/index.py
@@ -0,0 +1,715 @@
+#!/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
+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
+
+ for r in result:
+ if str(r["dn"]) == dn:
+ return True
+ return False
+
+
+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", b"notUnique"],
+ "@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):
+ # 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",
+ "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 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")
+ 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_DN_ONE_LEVELX,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"})
+
+ # 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",
+ "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_DN_ONE_LEVELX,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_DN_ONE_LEVELX,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)
+
+ #
+ # Test non unique index searched with truncated keys
+ #
+ def test_index_truncated_keys(self):
+ # 0 1 2 3 4 5
+ # 12345678901234567890123456789012345678901234567890
+ # @INDEX:NOTUNIQUE:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
+
+ eq_max = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+ gt_max = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+ lt_max = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+
+ # Add two entries with the same value, key length = max so no
+ # truncation.
+ self.l.add({"dn": "OU=01,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
+ "name": b"Admins",
+ "notUnique": eq_max,
+ "objectUUID": b"0123456789abcde0"})
+ self.l.add({"dn": "OU=02,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
+ "name": b"Admins",
+ "notUnique": eq_max,
+ "objectUUID": b"0123456789abcde1"})
+
+ #
+ # An entry outside the tree
+ #
+ self.l.add({"dn": "OU=10,OU=SEARCH_NON_UNIQUE01,DC=SAMBA,DC=ORG",
+ "name": b"Admins",
+ "notUnique": eq_max,
+ "objectUUID": b"0123456789abcd11"})
+
+ # Key longer than max so should get truncated to same key as
+ # the previous two entries
+ self.l.add({"dn": "OU=03,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
+ "name": b"Admins",
+ "notUnique": gt_max,
+ "objectUUID": b"0123456789abcde2"})
+ #
+ # An entry outside the tree
+ #
+ self.l.add({"dn": "OU=11,OU=SEARCH_NON_UNIQUE01,DC=SAMBA,DC=ORG",
+ "name": b"Admins",
+ "notUnique": gt_max,
+ "objectUUID": b"0123456789abcd12"})
+
+ # Key shorter than max
+ #
+ self.l.add({"dn": "OU=04,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
+ "name": b"Admins",
+ "notUnique": lt_max,
+ "objectUUID": b"0123456789abcde3"})
+ #
+ # An entry outside the tree
+ #
+ self.l.add({"dn": "OU=12,OU=SEARCH_NON_UNIQUE01,DC=SAMBA,DC=ORG",
+ "name": b"Admins",
+ "notUnique": lt_max,
+ "objectUUID": b"0123456789abcd13"})
+
+ #
+ # search for target is max value not truncated
+ # should return ou's 01, 02
+ #
+ expression = "(notUnique=" + eq_max.decode('ascii') + ")"
+ res = self.l.search(base="OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_ONELEVEL,
+ expression=expression)
+ self.assertEqual(len(res), 2)
+ self.assertTrue(
+ contains(res, "OU=01,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+ self.assertTrue(
+ contains(res, "OU=02,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+ #
+ # search for target is max value not truncated
+ # search one level up the tree, scope is ONE_LEVEL
+ # So should get no matches
+ #
+ expression = "(notUnique=" + eq_max.decode('ascii') + ")"
+ res = self.l.search(base="DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_ONELEVEL,
+ expression=expression)
+ self.assertEqual(len(res), 0)
+ #
+ # search for target is max value not truncated
+ # search one level up the tree, scope is SUBTREE
+ # So should get 3 matches
+ #
+ res = self.l.search(base="DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_SUBTREE,
+ expression=expression)
+ self.assertEqual(len(res), 3)
+ self.assertTrue(
+ contains(res, "OU=01,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+ self.assertTrue(
+ contains(res, "OU=02,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+ self.assertTrue(
+ contains(res, "OU=10,OU=SEARCH_NON_UNIQUE01,DC=SAMBA,DC=ORG"))
+
+ #
+ # search for target is max value + 1 so truncated
+ # should return ou 03
+ #
+ expression = "(notUnique=" + gt_max.decode('ascii') + ")"
+ res = self.l.search(base="OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_ONELEVEL,
+ expression=expression)
+ self.assertEqual(len(res), 1)
+ self.assertTrue(
+ contains(res, "OU=03,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+ #
+ # scope one level and one level up one level up should get no matches
+ #
+ res = self.l.search(base="DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_ONELEVEL,
+ expression=expression)
+ self.assertEqual(len(res), 0)
+ #
+ # scope sub tree and one level up one level up should get 2 matches
+ #
+ res = self.l.search(base="DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_SUBTREE,
+ expression=expression)
+ self.assertEqual(len(res), 2)
+ self.assertTrue(
+ contains(res, "OU=03,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+ self.assertTrue(
+ contains(res, "OU=11,OU=SEARCH_NON_UNIQUE01,DC=SAMBA,DC=ORG"))
+
+ #
+ # search for target is max value - 1 so not truncated
+ # should return ou 04
+ #
+ expression = "(notUnique=" + lt_max.decode('ascii') + ")"
+ res = self.l.search(base="OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_ONELEVEL,
+ expression=expression)
+ self.assertEqual(len(res), 1)
+ self.assertTrue(
+ contains(res, "OU=04,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+
+ #
+ # scope one level and one level up one level up should get no matches
+ #
+ res = self.l.search(base="DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_ONELEVEL,
+ expression=expression)
+ self.assertEqual(len(res), 0)
+
+ #
+ # scope sub tree and one level up one level up should get 2 matches
+ #
+ res = self.l.search(base="DC=SAMBA,DC=ORG",
+ scope=ldb.SCOPE_SUBTREE,
+ expression=expression)
+ self.assertEqual(len(res), 2)
+ self.assertTrue(
+ contains(res, "OU=04,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG"))
+ self.assertTrue(
+ contains(res, "OU=12,OU=SEARCH_NON_UNIQUE01,DC=SAMBA,DC=ORG"))
+
+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 7f4be893a30d695d1a843e2c79ab7671e14db256 Mon Sep 17 00:00:00 2001
From: Gary Lockyer <gary at catalyst.net.nz>
Date: Tue, 27 Feb 2018 12:41:21 +1300
Subject: [PATCH 6/6] ldb_tdb: Add extra tests for truncated index keys
Add tests to ensure that the correct index records are created and that
the GUID's in the index record are correctly sorted.
Signed-off-by: Gary Lockyer <gary at catalyst.net.nz>
---
lib/ldb/tests/python/index.py | 62 ++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 61 insertions(+), 1 deletion(-)
diff --git a/lib/ldb/tests/python/index.py b/lib/ldb/tests/python/index.py
index 8ffceda..7ecb85b 100755
--- a/lib/ldb/tests/python/index.py
+++ b/lib/ldb/tests/python/index.py
@@ -53,6 +53,26 @@ def contains(result, dn):
class MaxIndexKeyLengthTests(TestCase):
+ def checkGuids(self, key, guids):
+ #
+ # This check relies on the current implementation where the indexes
+ # are in the same database as the data.
+ #
+ # It also asserts that the format is correct, including the required
+ # sorting.
+ #
+ # The GUID's need to be sorted in GUID order, it is the callers
+ # responsibility to do this
+ #
+ res = self.l.search(
+ base=key,
+ scope=ldb.SCOPE_BASE)
+ self.assertEqual(len(res), 1)
+
+ # The GUID index format has only one value
+ index = res[0]["@IDX"][0]
+ self.assertEqual(len(guids), len(index))
+ self.assertEqual(guids, index)
def tearDown(self):
shutil.rmtree(self.testdir)
@@ -104,28 +124,45 @@ class MaxIndexKeyLengthTests(TestCase):
"name": b"Admins",
"x": "z", "y": "a",
"objectUUID": b"0123456789abcdef"})
+ self.checkGuids(
+ "@INDEX#@IDXDN#OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+ 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.checkGuids(
+ "@INDEX#@IDXDN#OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+ b"0123456789abcde0" + 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.checkGuids(
+ "@INDEX#@IDXDN#OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+ b"0123456789abcde0" + b"0123456789abcde1" + b"0123456789abcdef")
+ # Key is equal to max length does not get inserted into the truncated
+ # key namespace
self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
"name": b"Admins",
"x": "z", "y": "a",
"objectUUID": b"0123456789abcde5"})
+ self.checkGuids(
+ "@INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA",
+ b"0123456789abcde5")
# This key should not get truncated, as it's one character less than
- # max
+ # max, and will not be in the truncate name space
self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXX,DC=SAMBA",
"name": b"Admins",
"x": "z", "y": "a",
"objectUUID": b"0123456789abcde7"})
+ self.checkGuids(
+ "@INDEX:@IDXDN:OU=A_LONG_DNXXXXXXXXXXXXXX,DC=SAMBA",
+ b"0123456789abcde7")
try:
self.l.add({"dn": "OU=A_LONG_DNXXXXXXXXXXXXXXX,DC=SAMBA,DC=ORG",
@@ -568,10 +605,17 @@ class MaxIndexKeyLengthTests(TestCase):
"name": b"Admins",
"notUnique": eq_max,
"objectUUID": b"0123456789abcde0"})
+ self.checkGuids(
+ "@INDEX:NOTUNIQUE:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+ b"0123456789abcde0")
+
self.l.add({"dn": "OU=02,OU=SEARCH_NON_UNIQUE,DC=SAMBA,DC=ORG",
"name": b"Admins",
"notUnique": eq_max,
"objectUUID": b"0123456789abcde1"})
+ self.checkGuids(
+ "@INDEX:NOTUNIQUE:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+ b"0123456789abcde0" + b"0123456789abcde1")
#
# An entry outside the tree
@@ -580,6 +624,9 @@ class MaxIndexKeyLengthTests(TestCase):
"name": b"Admins",
"notUnique": eq_max,
"objectUUID": b"0123456789abcd11"})
+ self.checkGuids(
+ "@INDEX:NOTUNIQUE:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+ b"0123456789abcd11" + b"0123456789abcde0" + b"0123456789abcde1")
# Key longer than max so should get truncated to same key as
# the previous two entries
@@ -587,6 +634,10 @@ class MaxIndexKeyLengthTests(TestCase):
"name": b"Admins",
"notUnique": gt_max,
"objectUUID": b"0123456789abcde2"})
+ # But in the truncated key space
+ self.checkGuids(
+ "@INDEX#NOTUNIQUE#aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+ b"0123456789abcde2")
#
# An entry outside the tree
#
@@ -594,6 +645,9 @@ class MaxIndexKeyLengthTests(TestCase):
"name": b"Admins",
"notUnique": gt_max,
"objectUUID": b"0123456789abcd12"})
+ self.checkGuids(
+ "@INDEX#NOTUNIQUE#aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+ b"0123456789abcd12" + b"0123456789abcde2")
# Key shorter than max
#
@@ -601,6 +655,9 @@ class MaxIndexKeyLengthTests(TestCase):
"name": b"Admins",
"notUnique": lt_max,
"objectUUID": b"0123456789abcde3"})
+ self.checkGuids(
+ "@INDEX:NOTUNIQUE:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+ b"0123456789abcde3")
#
# An entry outside the tree
#
@@ -608,6 +665,9 @@ class MaxIndexKeyLengthTests(TestCase):
"name": b"Admins",
"notUnique": lt_max,
"objectUUID": b"0123456789abcd13"})
+ self.checkGuids(
+ "@INDEX:NOTUNIQUE:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
+ b"0123456789abcd13" + b"0123456789abcde3")
#
# search for target is max value not truncated
--
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/20180227/24e99ccd/signature-0001.sig>
More information about the samba-technical
mailing list