[SCM] Samba Shared Repository - branch v4-10-test updated

Stefan Metzmacher metze at samba.org
Wed Feb 13 15:25:01 UTC 2019


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 <abartlet at samba.org>
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 <abartlet at samba.org>
    Reviewed-by: Garming Sam <garming at catalyst.net.nz>
    (cherry picked from commit 5e716c0256a6bec92e7855ccfc077a328320f2ea)
    
    Autobuild-User(v4-10-test): Stefan Metzmacher <metze at samba.org>
    Autobuild-Date(v4-10-test): Wed Feb 13 16:24:32 CET 2019 on sn-devel-144

commit bb850a075024ad8ac26a25681339f6ce88334aba
Author: Andrew Bartlett <abartlet at samba.org>
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 <abartlet at samba.org>
    Reviewed-by: Garming Sam <garming at catalyst.net.nz>
    (cherry picked from commit e7f524fd2128aacb82e980652af8eb6fd275e1a8)

commit 2a915942295e6cdc87dc9aab6cf2c8c78741f26e
Author: Tim Beale <timbeale at catalyst.net.nz>
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 <timbeale at catalyst.net.nz>
    Reviewed-by: Andrew Bartlett <abartlet at samba.org>
    (cherry picked from commit 57a565b2fd680fc1a34f4ab91c6f6314f68ef67f)

commit 62fea7e9c3f94d254e6c9f72cd690137c2ee556c
Author: Tim Beale <timbeale at catalyst.net.nz>
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 <timbeale at catalyst.net.nz>
    Reviewed-by: Andrew Bartlett <abartlet at samba.org>
    (cherry picked from commit 132600685b8c5d4964f20634cd7a64b14f41cfa7)

commit f7774530936bc3e9795b2f0089c984641ab5c5c9
Author: Tim Beale <timbeale at catalyst.net.nz>
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 <timbeale at catalyst.net.nz>
    Reviewed-by: Andrew Bartlett <abartlet at samba.org>
    (cherry picked from commit 72928444823c5b18ac9ef98e7432c999d70aa571)

commit 7fc3481765720d2fa0324f297e4a658520fb092f
Author: Tim Beale <timbeale at catalyst.net.nz>
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 <timbeale at catalyst.net.nz>
    Reviewed-by: Andrew Bartlett <abartlet at samba.org>
    (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



More information about the samba-cvs mailing list