The branch, v4-10-test has been updated
via e21e24d8345 ldb: Release ldb 1.5.3
via bb850a07502 ldb: Add even more comments on what strict does to the
list intersections
via 2a915942295 ldb: Rename variable
via 62fea7e9c3f ldb: Elaborate on ldb_kv_search_indexed() comments
via f7774530936 ldb: Remove comment that no longer makes sense
via 7fc34817657 ldb: Avoid inefficient one-level searches
from 0c75bfe674b VERSION: Bump version up to 4.10.0rc2...
https://git.samba.org/?p=samba.git;a=shortlog;h=v4-10-test
- Log -----------------------------------------------------------------
commit e21e24d8345e441d639020affc1f6ee59762725d
Author: Andrew Bartlett <[email protected]>
Date: Fri Feb 1 14:41:18 2019 +1300
ldb: Release ldb 1.5.3
* Avoid inefficient one-level searches (bug 13762)
* The test api.py should not rely on order of entries in dict (bug 13772)
BUG: https://bugzilla.samba.org/show_bug.cgi?id=13762
BUG: https://bugzilla.samba.org/show_bug.cgi?id=13772
Signed-off-by: Andrew Bartlett <[email protected]>
Reviewed-by: Garming Sam <[email protected]>
(cherry picked from commit 5e716c0256a6bec92e7855ccfc077a328320f2ea)
Autobuild-User(v4-10-test): Stefan Metzmacher <[email protected]>
Autobuild-Date(v4-10-test): Wed Feb 13 16:24:32 CET 2019 on sn-devel-144
commit bb850a075024ad8ac26a25681339f6ce88334aba
Author: Andrew Bartlett <[email protected]>
Date: Fri Feb 1 14:22:17 2019 +1300
ldb: Add even more comments on what strict does to the list intersections
BUG: https://bugzilla.samba.org/show_bug.cgi?id=13762
Signed-off-by: Andrew Bartlett <[email protected]>
Reviewed-by: Garming Sam <[email protected]>
(cherry picked from commit e7f524fd2128aacb82e980652af8eb6fd275e1a8)
commit 2a915942295e6cdc87dc9aab6cf2c8c78741f26e
Author: Tim Beale <[email protected]>
Date: Thu Jan 10 14:25:06 2019 +1300
ldb: Rename variable
The old name confused me because it's not really related to the
one-level index at all. It's the result from evaluating the indexed
search specified in the ac->tree.
BUG: https://bugzilla.samba.org/show_bug.cgi?id=13762
Signed-off-by: Tim Beale <[email protected]>
Reviewed-by: Andrew Bartlett <[email protected]>
(cherry picked from commit 57a565b2fd680fc1a34f4ab91c6f6314f68ef67f)
commit 62fea7e9c3f94d254e6c9f72cd690137c2ee556c
Author: Tim Beale <[email protected]>
Date: Thu Jan 10 14:19:19 2019 +1300
ldb: Elaborate on ldb_kv_search_indexed() comments
Disclaimer: this is based on my limited understanding of what the code
is doing.
BUG: https://bugzilla.samba.org/show_bug.cgi?id=13762
Signed-off-by: Tim Beale <[email protected]>
Reviewed-by: Andrew Bartlett <[email protected]>
(cherry picked from commit 132600685b8c5d4964f20634cd7a64b14f41cfa7)
commit f7774530936bc3e9795b2f0089c984641ab5c5c9
Author: Tim Beale <[email protected]>
Date: Thu Jan 10 13:53:47 2019 +1300
ldb: Remove comment that no longer makes sense
This comment was written before the GUID_index_attribute block of code
existed. So we now *do* load the index values and *do* check for a
strict intersect, so the comment is redundant.
BUG: https://bugzilla.samba.org/show_bug.cgi?id=13762
Signed-off-by: Tim Beale <[email protected]>
Reviewed-by: Andrew Bartlett <[email protected]>
(cherry picked from commit 72928444823c5b18ac9ef98e7432c999d70aa571)
commit 7fc3481765720d2fa0324f297e4a658520fb092f
Author: Tim Beale <[email protected]>
Date: Thu Jan 10 13:34:18 2019 +1300
ldb: Avoid inefficient one-level searches
Commit 88ae60ed186c9 introduced a problem that made one-level
searches inefficient if there were a lot of child objects in the same
level, and the requested object didn't exist. Basically, it ignored the
case where ldb_kv_index_dn() returned LDB_ERR_NO_SUCH_OBJECT, i.e. the
indexed lookup was successful, but didn't find a match. At which point,
there was no more processing we needed to do.
The behaviour after 88ae60ed186c9 was to fall-through and run the
ldb_kv_index_filter() function over *all* the children. This still
returned the correct result, but could be costly if there were a lot of
children.
The case 88ae60ed186c9 was trying to fix was where we could not do
an indexed search (e.g. trying to match on a 'attribute=*' filter). In
which case we want to ignore the LDB_ERR_OPERATIONS_ERROR and just run
ldb_kv_index_filter() over all the children. This is still more
efficient than the fallback of doing a full database scan.
This patch adds in a short-circuit for the NO_SUCH_OBJECT case, so we
can skip the unnecessary ldb_kv_index_filter() work.
BUG: https://bugzilla.samba.org/show_bug.cgi?id=13762
Signed-off-by: Tim Beale <[email protected]>
Reviewed-by: Andrew Bartlett <[email protected]>
(cherry picked from commit 9a893f9613bd6440abd8e487d22a39ab5b82a7b9)
-----------------------------------------------------------------------
Summary of changes:
lib/ldb/ABI/{ldb-1.5.1.sigs => ldb-1.5.3.sigs} | 0
...yldb-util-1.1.10.sigs => pyldb-util-1.5.3.sigs} | 0
...-util-1.1.10.sigs => pyldb-util.py3-1.5.3.sigs} | 0
lib/ldb/ldb_key_value/ldb_kv_index.c | 76 +++++++++++++++++-----
lib/ldb/wscript | 2 +-
5 files changed, 59 insertions(+), 19 deletions(-)
copy lib/ldb/ABI/{ldb-1.5.1.sigs => ldb-1.5.3.sigs} (100%)
copy lib/ldb/ABI/{pyldb-util-1.1.10.sigs => pyldb-util-1.5.3.sigs} (100%)
copy lib/ldb/ABI/{pyldb-util-1.1.10.sigs => pyldb-util.py3-1.5.3.sigs} (100%)
Changeset truncated at 500 lines:
diff --git a/lib/ldb/ABI/ldb-1.5.1.sigs b/lib/ldb/ABI/ldb-1.5.3.sigs
similarity index 100%
copy from lib/ldb/ABI/ldb-1.5.1.sigs
copy to lib/ldb/ABI/ldb-1.5.3.sigs
diff --git a/lib/ldb/ABI/pyldb-util-1.1.10.sigs
b/lib/ldb/ABI/pyldb-util-1.5.3.sigs
similarity index 100%
copy from lib/ldb/ABI/pyldb-util-1.1.10.sigs
copy to lib/ldb/ABI/pyldb-util-1.5.3.sigs
diff --git a/lib/ldb/ABI/pyldb-util-1.1.10.sigs
b/lib/ldb/ABI/pyldb-util.py3-1.5.3.sigs
similarity index 100%
copy from lib/ldb/ABI/pyldb-util-1.1.10.sigs
copy to lib/ldb/ABI/pyldb-util.py3-1.5.3.sigs
diff --git a/lib/ldb/ldb_key_value/ldb_kv_index.c
b/lib/ldb/ldb_key_value/ldb_kv_index.c
index 6c21c19d654..6d02c91a597 100644
--- a/lib/ldb/ldb_key_value/ldb_kv_index.c
+++ b/lib/ldb/ldb_key_value/ldb_kv_index.c
@@ -1259,6 +1259,14 @@ static bool list_intersect(struct ldb_context *ldb,
return true;
}
+ /*
+ * In both of the below we check for strict and in that
+ * case do not optimise the intersection of this list,
+ * we must never return an entry not in this
+ * list. This allows the index for
+ * SCOPE_ONELEVEL to be trusted.
+ */
+
/* the indexing code is allowed to return a longer list than
what really matches, as all results are filtered by the
full expression at the end - this shortcut avoids a lot of
@@ -1660,7 +1668,13 @@ static int ldb_kv_index_dn_one(struct ldb_module *module,
struct dn_list *list,
enum key_truncation *truncation)
{
- /* Ensure we do not shortcut on intersection for this list */
+ /*
+ * Ensure we do not shortcut on intersection for this list.
+ * We must never be lazy and return an entry not in this
+ * list. This allows the index for
+ * SCOPE_ONELEVEL to be trusted.
+ */
+
list->strict = true;
return ldb_kv_index_dn_attr(
module, ldb_kv, LDB_KV_IDXONE, parent_dn, list, truncation);
@@ -2008,10 +2022,11 @@ int ldb_kv_search_indexed(struct ldb_kv_context *ac,
uint32_t *match_count)
return ldb_operr(ldb);
case LDB_SCOPE_ONELEVEL:
+
/*
- * If we ever start to also load the index values for
- * the tree, we must ensure we strictly intersect with
- * this list, as we trust the ONELEVEL index
+ * First, load all the one-level child objects (regardless of
+ * whether they match the search filter or not). The database
+ * maintains a one-level index, so retrieving this is quick.
*/
ret = ldb_kv_index_dn_one(ac->module,
ldb_kv,
@@ -2024,9 +2039,12 @@ int ldb_kv_search_indexed(struct ldb_kv_context *ac,
uint32_t *match_count)
}
/*
- * If we have too many matches, running the filter
- * tree over the SCOPE_ONELEVEL can be quite expensive
- * so we now check the filter tree index as well.
+ * If we have too many children, running ldb_kv_index_filter()
+ * over all the child objects can be quite expensive. So next
+ * we do a separate indexed query using the search filter.
+ *
+ * This should be quick, but it may return objects that are not
+ * the direct one-level child objects we're interested in.
*
* We only do this in the GUID index mode, which is
* O(n*log(m)) otherwise the intersection below will
@@ -2037,33 +2055,55 @@ int ldb_kv_search_indexed(struct ldb_kv_context *ac,
uint32_t *match_count)
* fast enough in the small case.
*/
if (ldb_kv->cache->GUID_index_attribute != NULL) {
- struct dn_list *idx_one_tree_list
+ struct dn_list *indexed_search_result
= talloc_zero(ac, struct dn_list);
- if (idx_one_tree_list == NULL) {
+ if (indexed_search_result == NULL) {
talloc_free(dn_list);
return ldb_module_oom(ac->module);
}
if (!ldb_kv->cache->attribute_indexes) {
- talloc_free(idx_one_tree_list);
+ talloc_free(indexed_search_result);
talloc_free(dn_list);
return LDB_ERR_OPERATIONS_ERROR;
}
+
/*
- * Here we load the index for the tree.
- *
- * We only care if this is successful, if the
- * index can't trim the result list down then
- * the ONELEVEL index is still good enough.
+ * Try to do an indexed database search
*/
ret = ldb_kv_index_dn(
- ac->module, ldb_kv, ac->tree, idx_one_tree_list);
+ ac->module, ldb_kv, ac->tree,
+ indexed_search_result);
+
+ /*
+ * We can stop if we're sure the object doesn't exist
+ */
+ if (ret == LDB_ERR_NO_SUCH_OBJECT) {
+ talloc_free(indexed_search_result);
+ talloc_free(dn_list);
+ return LDB_ERR_NO_SUCH_OBJECT;
+ }
+
+ /*
+ * Once we have a successful search result, we
+ * intersect it with the one-level children (dn_list).
+ * This should give us exactly the result we're after
+ * (we still need to run ldb_kv_index_filter() to
+ * handle potential index truncation cases).
+ *
+ * The indexed search may fail because we don't support
+ * indexing on that type of search operation, e.g.
+ * matching against '*'. In which case we fall through
+ * and run ldb_kv_index_filter() over all the one-level
+ * children (which is still better than bailing out here
+ * and falling back to a full DB scan).
+ */
if (ret == LDB_SUCCESS) {
if (!list_intersect(ldb,
ldb_kv,
dn_list,
- idx_one_tree_list)) {
- talloc_free(idx_one_tree_list);
+ indexed_search_result)) {
+ talloc_free(indexed_search_result);
talloc_free(dn_list);
return LDB_ERR_OPERATIONS_ERROR;
}
diff --git a/lib/ldb/wscript b/lib/ldb/wscript
index ca0bf410f10..855ee4d556c 100644
--- a/lib/ldb/wscript
+++ b/lib/ldb/wscript
@@ -1,7 +1,7 @@
#!/usr/bin/env python
APPNAME = 'ldb'
-VERSION = '1.5.2'
+VERSION = '1.5.3'
import sys, os
--
Samba Shared Repository
