This is an automated email from the git hooks/post-receive script.
mreynolds pushed a change to branch master in repository 389-ds-base.
from d06b5bb Ticket 49887: Fix SASL map creation when --disable-perl new 104968b Revert "Ticket 49432 - filter optimise crash" new 14a10a3 Revert "Ticket 49372 - filter optimisation improvements for common queries"
The 2 revisions listed above as "new" are entirely new to this repository and will be described in separate emails. The revisions listed as "adds" were already present in the repository and have only been added to this reference.
Summary of changes: Makefile.am | 1 - .../suites/filter/rfc3673_all_oper_attrs_test.py | 5 +- ldap/admin/src/scripts/ns-slapd-gdb.py | 70 ------- ldap/servers/slapd/back-ldbm/ldbm_modrdn.c | 7 +- ldap/servers/slapd/back-ldbm/ldbm_search.c | 79 +++++--- ldap/servers/slapd/back-ldbm/proto-back-ldbm.h | 6 +- ldap/servers/slapd/back-ldbm/vlv_srch.c | 23 ++- ldap/servers/slapd/dse.c | 7 - ldap/servers/slapd/filter.c | 209 ++++----------------- ldap/servers/slapd/index_subsystem.c | 4 - ldap/servers/slapd/slapi-private.h | 1 - test/libslapd/filter/optimise.c | 83 -------- test/libslapd/test.c | 1 - test/test_slapd.h | 3 - 14 files changed, 104 insertions(+), 395 deletions(-) delete mode 100644 test/libslapd/filter/optimise.c
This is an automated email from the git hooks/post-receive script.
mreynolds pushed a commit to branch master in repository 389-ds-base.
commit 104968b67bbfbc89cf5311c7ca7be973dd86baed Author: Mark Reynolds mreynolds@redhat.com Date: Fri Aug 24 16:21:32 2018 -0400
Revert "Ticket 49432 - filter optimise crash"
This reverts commit 5c89dd8f9c8eb77c967574412d049d55565bb364. --- Makefile.am | 1 - ldap/servers/slapd/filter.c | 30 ++++++--------- test/libslapd/filter/optimise.c | 83 ----------------------------------------- test/libslapd/test.c | 1 - test/test_slapd.h | 3 -- 5 files changed, 12 insertions(+), 106 deletions(-)
diff --git a/Makefile.am b/Makefile.am index 4cc0fe7..fffae13 100644 --- a/Makefile.am +++ b/Makefile.am @@ -2150,7 +2150,6 @@ TESTS = test_slapd \ test_slapd_SOURCES = test/main.c \ test/libslapd/test.c \ test/libslapd/counters/atomic.c \ - test/libslapd/filter/optimise.c \ test/libslapd/pblock/analytics.c \ test/libslapd/pblock/v3_compat.c \ test/libslapd/operation/v3_compat.c \ diff --git a/ldap/servers/slapd/filter.c b/ldap/servers/slapd/filter.c index 46a2266..87ec0de 100644 --- a/ldap/servers/slapd/filter.c +++ b/ldap/servers/slapd/filter.c @@ -1561,28 +1561,22 @@ filter_prioritise_element(Slapi_Filter **list, Slapi_Filter **head, Slapi_Filter
static void filter_merge_subfilter(Slapi_Filter **list, Slapi_Filter **f_prev, Slapi_Filter **f_cur, Slapi_Filter **f_next) { - - /* First, graft in the new item between f_cur and f_cur -> f_next */ - Slapi_Filter *remainder = (*f_cur)->f_next; - (*f_cur)->f_next = (*f_cur)->f_list; - /* Go to the end of the newly grafted list, and put in our remainder. */ - Slapi_Filter *f_cur_tail = *f_cur; - while (f_cur_tail->f_next != NULL) { - f_cur_tail = f_cur_tail->f_next; - } - f_cur_tail->f_next = remainder; - - /* Now indicate to the caller what the next element is. */ - *f_next = (*f_cur)->f_next; - - /* Now that we have grafted our list in, cut out f_cur */ + /* Cut our current AND/OR out */ if (*f_prev != NULL) { - (*f_prev)->f_next = *f_next; + (*f_prev)->f_next = (*f_cur)->f_next; } else if (*list == *f_cur) { - *list = *f_next; + *list = (*f_cur)->f_next; } + (*f_next) = (*f_cur)->f_next;
- /* Finally free the f_cur (and/or) */ + /* Look ahead to the end of our list, without the f_cur. */ + Slapi_Filter *f_cur_tail = *list; + while (f_cur_tail->f_next != NULL) { + f_cur_tail = f_cur_tail->f_next; + } + /* Now append our descendant into the tail */ + f_cur_tail->f_next = (*f_cur)->f_list; + /* Finally free the remainder */ slapi_filter_free(*f_cur, 0); }
diff --git a/test/libslapd/filter/optimise.c b/test/libslapd/filter/optimise.c deleted file mode 100644 index bcf4ccd..0000000 --- a/test/libslapd/filter/optimise.c +++ /dev/null @@ -1,83 +0,0 @@ -/** BEGIN COPYRIGHT BLOCK - * Copyright (C) 2017 Red Hat, Inc. - * All rights reserved. - * - * License: GPL (version 3 or any later version). - * See LICENSE for details. - * END COPYRIGHT BLOCK **/ - -#include "../../test_slapd.h" - -/* To access filter optimise */ -#include <slapi-private.h> - -void -test_libslapd_filter_optimise(void **state __attribute__((unused))) -{ - char *test_filters[] = { - "(&(uid=uid1)(sn=last1)(givenname=first1))", - "(&(uid=uid1)(&(sn=last1)(givenname=first1)))", - "(&(uid=uid1)(&(&(sn=last1))(&(givenname=first1))))", - "(&(uid=*)(sn=last3)(givenname=*))", - "(&(uid=*)(&(sn=last3)(givenname=*)))", - "(&(uid=uid5)(&(&(sn=*))(&(givenname=*))))", - "(&(objectclass=*)(uid=*)(sn=last*))", - "(&(objectclass=*)(uid=*)(sn=last1))", - - "(|(uid=uid1)(sn=last1)(givenname=first1))", - "(|(uid=uid1)(|(sn=last1)(givenname=first1)))", - "(|(uid=uid1)(|(|(sn=last1))(|(givenname=first1))))", - "(|(objectclass=*)(sn=last1)(|(givenname=first1)))", - "(|(&(objectclass=*)(sn=last1))(|(givenname=first1)))", - "(|(&(objectclass=*)(sn=last))(|(givenname=first1)))", - - "(&(uid=uid1)(!(cn=NULL)))", - "(&(!(cn=NULL))(uid=uid1))", - "(&(uid=*)(&(!(uid=1))(!(givenname=first1))))", - - "(&(|(uid=uid1)(uid=NULL))(sn=last1))", - "(&(|(uid=uid1)(uid=NULL))(!(sn=NULL)))", - "(&(|(uid=uid1)(sn=last2))(givenname=first1))", - "(|(&(uid=uid1)(!(uid=NULL)))(sn=last2))", - "(|(&(uid=uid1)(uid=NULL))(sn=last2))", - "(&(uid=uid5)(sn=*)(cn=*)(givenname=*)(uid=u*)(sn=la*)(cn=full*)(givenname=f*)(uid>=u)(!(givenname=NULL)))", - "(|(&(objectclass=*)(sn=last))(&(givenname=first1)))", - - "(&(uid=uid1)(sn=last1)(givenname=NULL))", - "(&(uid=uid1)(&(sn=last1)(givenname=NULL)))", - "(&(uid=uid1)(&(&(sn=last1))(&(givenname=NULL))))", - "(&(uid=uid1)(&(&(sn=last1))(&(givenname=NULL)(sn=*)))(|(sn=NULL)))", - "(&(uid=uid1)(&(&(sn=last*))(&(givenname=first*)))(&(sn=NULL)))", - - "(|(uid=NULL)(sn=NULL)(givenname=NULL))", - "(|(uid=NULL)(|(sn=NULL)(givenname=NULL)))", - "(|(uid=NULL)(|(|(sn=NULL))(|(givenname=NULL))))", - - "(uid>=uid3)", - "(&(uid=*)(uid>=uid3))", - "(|(uid>=uid3)(uid<=uid5))", - "(&(uid>=uid3)(uid<=uid5))", - "(|(&(uid>=uid3)(uid<=uid5))(uid=*))", - - "(|(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)(uid=*)" - "(uid=*))", - NULL - }; - - for (size_t i = 0; test_filters[i] != NULL; i++) { - char *filter_str = slapi_ch_strdup(test_filters[i]); - - struct slapi_filter *filter = slapi_str2filter(filter_str); - slapi_filter_optimise(filter); - slapi_filter_free(filter, 1); - slapi_ch_free_string(&filter_str); - } -} - diff --git a/test/libslapd/test.c b/test/libslapd/test.c index 02c6c03..ffa650d 100644 --- a/test/libslapd/test.c +++ b/test/libslapd/test.c @@ -28,7 +28,6 @@ run_libslapd_tests(void) cmocka_unit_test(test_libslapd_operation_v3c_target_spec), cmocka_unit_test(test_libslapd_counters_atomic_usage), cmocka_unit_test(test_libslapd_counters_atomic_overflow), - cmocka_unit_test(test_libslapd_filter_optimise), cmocka_unit_test(test_libslapd_pal_meminfo), cmocka_unit_test(test_libslapd_util_cachesane), }; diff --git a/test/test_slapd.h b/test/test_slapd.h index efccaea..ad4f73f 100644 --- a/test/test_slapd.h +++ b/test/test_slapd.h @@ -26,9 +26,6 @@ int run_plugin_tests(void); /* libslapd */ void test_libslapd_hello(void **state);
-/* libslapd-filter-optimise */ -void test_libslapd_filter_optimise(void **state); - /* libslapd-pblock-analytics */ void test_libslapd_pblock_analytics(void **state);
This is an automated email from the git hooks/post-receive script.
mreynolds pushed a commit to branch master in repository 389-ds-base.
commit 14a10a34b3ff10d5146d73e67aa54c8945cfa37d Author: Mark Reynolds mreynolds@redhat.com Date: Fri Aug 24 16:24:21 2018 -0400
Revert "Ticket 49372 - filter optimisation improvements for common queries"
This reverts commit 4cd1a24b3ce88968ff5f9a2b87efdc84dee176da. --- .../suites/filter/rfc3673_all_oper_attrs_test.py | 5 +- ldap/admin/src/scripts/ns-slapd-gdb.py | 70 ------- ldap/servers/slapd/back-ldbm/ldbm_modrdn.c | 7 +- ldap/servers/slapd/back-ldbm/ldbm_search.c | 79 +++++--- ldap/servers/slapd/back-ldbm/proto-back-ldbm.h | 6 +- ldap/servers/slapd/back-ldbm/vlv_srch.c | 23 ++- ldap/servers/slapd/dse.c | 7 - ldap/servers/slapd/filter.c | 203 ++++----------------- ldap/servers/slapd/index_subsystem.c | 4 - ldap/servers/slapd/slapi-private.h | 1 - 10 files changed, 104 insertions(+), 301 deletions(-)
diff --git a/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py b/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py index e61ece1..7cb15fd 100644 --- a/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py +++ b/dirsrvtests/tests/suites/filter/rfc3673_all_oper_attrs_test.py @@ -148,12 +148,9 @@ def test_search_basic(topology_st, test_user, user_aci, add_attr, else: expected_attrs = sorted(oper_attr_list)
- log.info("suffix: %s filter: %s" % (search_suffix, search_filter)) entries = topology_st.standalone.search_s(search_suffix, ldap.SCOPE_BASE, '(objectclass=*)', search_filter) - log.info("results: %s" % entries) - assert len(entries) > 0 found_attrs = sorted(entries[0].data.keys())
if add_attr == '*': @@ -162,7 +159,7 @@ def test_search_basic(topology_st, test_user, user_aci, add_attr, assert all(attr in found_attrs for attr in ['objectClass', expected_attrs[0]]) else: - assert set(expected_attrs).issubset(set(found_attrs)) + assert cmp(found_attrs, expected_attrs) == 0
if __name__ == '__main__': diff --git a/ldap/admin/src/scripts/ns-slapd-gdb.py b/ldap/admin/src/scripts/ns-slapd-gdb.py index eb99a6f..3273d43 100644 --- a/ldap/admin/src/scripts/ns-slapd-gdb.py +++ b/ldap/admin/src/scripts/ns-slapd-gdb.py @@ -16,22 +16,9 @@ import itertools import re
-from enum import IntEnum - import gdb from gdb.FrameDecorator import FrameDecorator
-class LDAPFilter(IntEnum): - PRESENT = 0x87 - APPROX = 0xa8 - LE = 0xa6 - GE = 0xa5 - SUBSTRINGS = 0xa4 - EQUALITY = 0xa3 - NOT = 0xa2 - OR = 0xa1 - AND = 0xa0 - class DSAccessLog (gdb.Command): """Display the Directory Server access log.""" def __init__ (self): @@ -127,64 +114,7 @@ class DSIdleFilter(): frame_iter = map(DSIdleFilterDecorator, frame_iter) return frame_iter
-class DSFilterPrint (gdb.Command): - """Display a filter's contents""" - def __init__ (self): - super (DSFilterPrint, self).__init__ ("ds-filter-print", gdb.COMMAND_DATA) - - def display_filter(self, filter_element, depth=0): - pad = " " * depth - # Extract the choice, that determines what we access next. - f_choice = filter_element['f_choice'] - f_un = filter_element['f_un'] - f_flags = filter_element['f_flags'] - if f_choice == LDAPFilter.PRESENT: - print("%s(%s=*) flags:%s" % (pad, f_un['f_un_type'], f_flags)) - elif f_choice == LDAPFilter.APPROX: - print("%sAPPROX ???" % pad) - elif f_choice == LDAPFilter.LE: - print("%sLE ???" % pad) - elif f_choice == LDAPFilter.GE: - print("%sGE ???" % pad) - elif f_choice == LDAPFilter.SUBSTRINGS: - f_un_sub = f_un['f_un_sub'] - value = f_un_sub['sf_initial'] - print("%s(%s=%s*) flags:%s" % (pad, f_un_sub['sf_type'], value, f_flags)) - elif f_choice == LDAPFilter.EQUALITY: - f_un_ava = f_un['f_un_ava'] - value = f_un_ava['ava_value']['bv_val'] - print("%s(%s=%s) flags:%s" % (pad, f_un_ava['ava_type'], value, f_flags)) - elif f_choice == LDAPFilter.NOT: - print("%sNOT ???" % pad) - elif f_choice == LDAPFilter.OR: - print("%s(| flags:%s" % (pad, f_flags)) - filter_child = f_un['f_un_complex'].dereference() - self.display_filter(filter_child, depth + 4) - print("%s)" % pad) - elif f_choice == LDAPFilter.AND: - # Our child filter is in f_un_complex. - print("%s(& flags:%s" % (pad, f_flags)) - filter_child = f_un['f_un_complex'].dereference() - self.display_filter(filter_child, depth + 4) - print("%s)" % pad) - else: - print("Corrupted filter, no such value %s" % f_choice) - - f_next = filter_element['f_next'] - if f_next != 0: - self.display_filter(f_next.dereference(), depth) - - def invoke (self, arg, from_tty): - # Select our program state - gdb.newest_frame() - cur_frame = gdb.selected_frame() - # We are given the name of a filter, so we need to look up that symbol. - filter_val = cur_frame.read_var(arg) - filter_root = filter_val.dereference() - self.display_filter(filter_root) - DSAccessLog() DSBacktrace() DSIdleFilter() -DSFilterPrint()
diff --git a/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c b/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c index 71e2a8f..b9a092c 100644 --- a/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c +++ b/ldap/servers/slapd/back-ldbm/ldbm_modrdn.c @@ -2072,13 +2072,8 @@ moddn_get_children(back_txn *ptxn, * being moved */ strcpy(filterstr, "objectclass=*"); filter = slapi_str2filter(filterstr); - /* - * We used to set managedSAIT here, but because the subtree create - * referral step is now in build_candidate_list, we can trust the filter - * we provide here is exactly as we provide it IE no referrals involved. - */ candidates = subtree_candidates(pb, be, slapi_sdn_get_ndn(dn_parentdn), - parententry, filter, + parententry, filter, 1 /* ManageDSAIT */, NULL /* allids_before_scopingp */, &err); slapi_filter_free(filter, 1); } diff --git a/ldap/servers/slapd/back-ldbm/ldbm_search.c b/ldap/servers/slapd/back-ldbm/ldbm_search.c index 966131c..7f3600e 100644 --- a/ldap/servers/slapd/back-ldbm/ldbm_search.c +++ b/ldap/servers/slapd/back-ldbm/ldbm_search.c @@ -32,7 +32,7 @@ /* prototypes */ static int build_candidate_list(Slapi_PBlock *pb, backend *be, struct backentry *e, const char *base, int scope, int *lookup_returned_allidsp, IDList **candidates); static IDList *base_candidates(Slapi_PBlock *pb, struct backentry *e); -static IDList *onelevel_candidates(Slapi_PBlock *pb, backend *be, const char *base, Slapi_Filter *filter, int *lookup_returned_allidsp, int *err); +static IDList *onelevel_candidates(Slapi_PBlock *pb, backend *be, const char *base, struct backentry *e, Slapi_Filter *filter, int managedsait, int *lookup_returned_allidsp, int *err); static back_search_result_set *new_search_result_set(IDList *idl, int vlv, int lookthroughlimit); static void delete_search_result_set(Slapi_PBlock *pb, back_search_result_set **sr); static int can_skip_filter_test(Slapi_PBlock *pb, struct slapi_filter *f, int scope, IDList *idl); @@ -959,25 +959,13 @@ build_candidate_list(Slapi_PBlock *pb, backend *be, struct backentry *e, const c break;
case LDAP_SCOPE_ONELEVEL: - /* modify the filter to be: (&(parentid=idofbase)(|(originalfilter)(objectclass=referral))) */ - filter = create_onelevel_filter(filter, e, managedsait); - /* Now optimise the filter for use */ - slapi_filter_optimise(filter); - - *candidates = onelevel_candidates(pb, be, base, filter, lookup_returned_allidsp, &err); - /* Give the optimised filter back to search filter for free */ - slapi_pblock_set(pb, SLAPI_SEARCH_FILTER, filter); + *candidates = onelevel_candidates(pb, be, base, e, filter, managedsait, + lookup_returned_allidsp, &err); break;
case LDAP_SCOPE_SUBTREE: - /* make (|(originalfilter)(objectclass=referral)) */ - filter = create_subtree_filter(filter, managedsait); - /* Now optimise the filter for use */ - slapi_filter_optimise(filter); - - *candidates = subtree_candidates(pb, be, base, e, filter, lookup_returned_allidsp, &err); - /* Give the optimised filter back to search filter for free */ - slapi_pblock_set(pb, SLAPI_SEARCH_FILTER, filter); + *candidates = subtree_candidates(pb, be, base, e, filter, managedsait, + lookup_returned_allidsp, &err); break;
default: @@ -1036,15 +1024,15 @@ base_candidates(Slapi_PBlock *pb __attribute__((unused)), struct backentry *e) * non-recursively when done with the returned filter. */ static Slapi_Filter * -create_referral_filter(Slapi_Filter *filter) +create_referral_filter(Slapi_Filter *filter, Slapi_Filter **focref, Slapi_Filter **forr) { char *buf = slapi_ch_strdup("objectclass=referral");
- Slapi_Filter *focref = slapi_str2filter(buf); - Slapi_Filter *forr = slapi_filter_join(LDAP_FILTER_OR, filter, focref); + *focref = slapi_str2filter(buf); + *forr = slapi_filter_join(LDAP_FILTER_OR, filter, *focref);
slapi_ch_free((void **)&buf); - return forr; + return *forr; }
/* @@ -1058,20 +1046,20 @@ create_referral_filter(Slapi_Filter *filter) * This function is exported for the VLV code to use. */ Slapi_Filter * -create_onelevel_filter(Slapi_Filter *filter, const struct backentry *baseEntry, int managedsait) +create_onelevel_filter(Slapi_Filter *filter, const struct backentry *baseEntry, int managedsait, Slapi_Filter **fid2kids, Slapi_Filter **focref, Slapi_Filter **fand, Slapi_Filter **forr) { Slapi_Filter *ftop = filter; char buf[40];
if (!managedsait) { - ftop = create_referral_filter(filter); + ftop = create_referral_filter(filter, focref, forr); }
sprintf(buf, "parentid=%lu", (u_long)(baseEntry != NULL ? baseEntry->ep_id : 0)); - Slapi_Filter *fid2kids = slapi_str2filter(buf); - Slapi_Filter *fand = slapi_filter_join(LDAP_FILTER_AND, ftop, fid2kids); + *fid2kids = slapi_str2filter(buf); + *fand = slapi_filter_join(LDAP_FILTER_AND, ftop, *fid2kids);
- return fand; + return *fand; }
/* @@ -1082,16 +1070,38 @@ onelevel_candidates( Slapi_PBlock *pb, backend *be, const char *base, + struct backentry *e, Slapi_Filter *filter, + int managedsait, int *lookup_returned_allidsp, int *err) { + Slapi_Filter *fid2kids = NULL; + Slapi_Filter *focref = NULL; + Slapi_Filter *fand = NULL; + Slapi_Filter *forr = NULL; + Slapi_Filter *ftop = NULL; IDList *candidates;
- candidates = filter_candidates(pb, be, base, filter, NULL, 0, err); + /* + * modify the filter to be something like this: + * + * (&(parentid=idofbase)(|(originalfilter)(objectclass=referral))) + */ + + ftop = create_onelevel_filter(filter, e, managedsait, &fid2kids, &focref, &fand, &forr); + + /* from here, it's just like subtree_candidates */ + candidates = filter_candidates(pb, be, base, ftop, NULL, 0, err);
*lookup_returned_allidsp = slapi_be_is_flag_set(be, SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
+ /* free up just the filter stuff we allocated above */ + slapi_filter_free(fid2kids, 0); + slapi_filter_free(fand, 0); + slapi_filter_free(forr, 0); + slapi_filter_free(focref, 0); + return (candidates); }
@@ -1106,12 +1116,12 @@ onelevel_candidates( * This function is exported for the VLV code to use. */ Slapi_Filter * -create_subtree_filter(Slapi_Filter *filter, int managedsait) +create_subtree_filter(Slapi_Filter *filter, int managedsait, Slapi_Filter **focref, Slapi_Filter **forr) { Slapi_Filter *ftop = filter;
if (!managedsait) { - ftop = create_referral_filter(filter); + ftop = create_referral_filter(filter, focref, forr); }
return ftop; @@ -1128,9 +1138,13 @@ subtree_candidates( const char *base, const struct backentry *e, Slapi_Filter *filter, + int managedsait, int *allids_before_scopingp, int *err) { + Slapi_Filter *focref = NULL; + Slapi_Filter *forr = NULL; + Slapi_Filter *ftop = NULL; IDList *candidates; PRBool has_tombstone_filter; int isroot = 0; @@ -1139,8 +1153,13 @@ subtree_candidates( Operation *op = NULL; PRBool is_bulk_import = PR_FALSE;
+ /* make (|(originalfilter)(objectclass=referral)) */ + ftop = create_subtree_filter(filter, managedsait, &focref, &forr); + /* Fetch a candidate list for the original filter */ - candidates = filter_candidates_ext(pb, be, base, filter, NULL, 0, err, allidslimit); + candidates = filter_candidates_ext(pb, be, base, ftop, NULL, 0, err, allidslimit); + slapi_filter_free(forr, 0); + slapi_filter_free(focref, 0);
/* set 'allids before scoping' flag */ if (NULL != allids_before_scopingp) { diff --git a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h index 6d772cd..f8b86d9 100644 --- a/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h +++ b/ldap/servers/slapd/back-ldbm/proto-back-ldbm.h @@ -568,9 +568,9 @@ int bedse_add_index_entry(int argc, char **argv); /* * ldbm_search.c */ -Slapi_Filter *create_onelevel_filter(Slapi_Filter *filter, const struct backentry *e, int managedsait); -Slapi_Filter *create_subtree_filter(Slapi_Filter *filter, int managedsait); -IDList *subtree_candidates(Slapi_PBlock *pb, backend *be, const char *base, const struct backentry *e, Slapi_Filter *filter, int *allids_before_scopingp, int *err); +Slapi_Filter *create_onelevel_filter(Slapi_Filter *filter, const struct backentry *e, int managedsait, Slapi_Filter **fid2kids, Slapi_Filter **focref, Slapi_Filter **fand, Slapi_Filter **forr); +Slapi_Filter *create_subtree_filter(Slapi_Filter *filter, int managedsait, Slapi_Filter **focref, Slapi_Filter **forr); +IDList *subtree_candidates(Slapi_PBlock *pb, backend *be, const char *base, const struct backentry *e, Slapi_Filter *filter, int managedsait, int *allids_before_scopingp, int *err); void search_set_tune(struct ldbminfo *li, int val); int search_get_tune(struct ldbminfo *li); int compute_lookthrough_limit(Slapi_PBlock *pb, struct ldbminfo *li); diff --git a/ldap/servers/slapd/back-ldbm/vlv_srch.c b/ldap/servers/slapd/back-ldbm/vlv_srch.c index 0c09cb8..c4c0875 100644 --- a/ldap/servers/slapd/back-ldbm/vlv_srch.c +++ b/ldap/servers/slapd/back-ldbm/vlv_srch.c @@ -93,8 +93,13 @@ vlvSearch_reinit(struct vlvSearch *p, const struct backentry *base) p->vlv_slapifilter = slapi_str2filter(p->vlv_filter); filter_normalize(p->vlv_slapifilter); /* make (&(parentid=idofbase)(|(originalfilter)(objectclass=referral))) */ - p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, base, 0 /* managedsait */); - slapi_filter_optimise(p->vlv_slapifilter); + { + Slapi_Filter *fid2kids = NULL; + Slapi_Filter *focref = NULL; + Slapi_Filter *fand = NULL; + Slapi_Filter *forr = NULL; + p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, base, 0 /* managedsait */, &fid2kids, &focref, &fand, &forr); + } }
/* @@ -168,16 +173,22 @@ vlvSearch_init(struct vlvSearch *p, Slapi_PBlock *pb, const Slapi_Entry *e, ldbm
/* make (&(parentid=idofbase)(|(originalfilter)(objectclass=referral))) */ { - p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, e, 0 /* managedsait */); - slapi_filter_optimise(p->vlv_slapifilter); + Slapi_Filter *fid2kids = NULL; + Slapi_Filter *focref = NULL; + Slapi_Filter *fand = NULL; + Slapi_Filter *forr = NULL; + p->vlv_slapifilter = create_onelevel_filter(p->vlv_slapifilter, e, 0 /* managedsait */, &fid2kids, &focref, &fand, &forr); + /* jcm: fid2kids, focref, fand, and forr get freed when we free p->vlv_slapifilter */ CACHE_RETURN(&inst->inst_cache, &e); } } break; case LDAP_SCOPE_SUBTREE: { /* make (|(originalfilter)(objectclass=referral))) */ /* No need for scope-filter since we apply a scope test before the filter test */ - p->vlv_slapifilter = create_subtree_filter(p->vlv_slapifilter, 0 /* managedsait */); - slapi_filter_optimise(p->vlv_slapifilter); + Slapi_Filter *focref = NULL; + Slapi_Filter *forr = NULL; + p->vlv_slapifilter = create_subtree_filter(p->vlv_slapifilter, 0 /* managedsait */, &focref, &forr); + /* jcm: focref and forr get freed when we free p->vlv_slapifilter */ } break; } } diff --git a/ldap/servers/slapd/dse.c b/ldap/servers/slapd/dse.c index e61e9d9..151c8ae 100644 --- a/ldap/servers/slapd/dse.c +++ b/ldap/servers/slapd/dse.c @@ -1635,13 +1635,6 @@ dse_search(Slapi_PBlock *pb) /* JCM There should only be one exit point from thi */ isrootdse = slapi_sdn_isempty(basesdn);
- /* - * Now optimise the filter for use: note that unlike ldbm_search, - * because we don't change the outer filter container, we don't need - * to set back into pb. - */ - slapi_filter_optimise(filter); - switch (scope) { case LDAP_SCOPE_BASE: { Slapi_Entry *baseentry = NULL; diff --git a/ldap/servers/slapd/filter.c b/ldap/servers/slapd/filter.c index 87ec0de..393a4dc 100644 --- a/ldap/servers/slapd/filter.c +++ b/ldap/servers/slapd/filter.c @@ -29,6 +29,7 @@ static int get_extensible_filter(BerElement *ber, mr_filter_t *); static int get_filter_internal(Connection *conn, BerElement *ber, struct slapi_filter **filt, char **fstr, int maxdepth, int curdepth, int *subentry_dont_rewrite, int *has_tombstone_filter, int *has_ruv_filter); static int tombstone_check_filter(Slapi_Filter *f); static int ruv_check_filter(Slapi_Filter *f); +static void filter_optimize(Slapi_Filter *f);
/* @@ -74,12 +75,7 @@ get_filter(Connection *conn, BerElement *ber, int scope, struct slapi_filter **f slapi_filter_to_string(*filt, logbuf, logbufsize)); }
- /* - * Filter optimise has been moved to the onelevel/subtree candidate dispatch. - * this is because they inject referrals or other business, that we can optimise - * and improve. - */ - /* filter_optimize(*filt); */ + filter_optimize(*filt);
if (NULL != logbuf) { slapi_log_err(SLAPI_LOG_DEBUG, "get_filter", " after optimize: %s\n", @@ -862,22 +858,19 @@ slapi_filter_join_ex(int ftype, struct slapi_filter *f1, struct slapi_filter *f2 if (add_to->f_list->f_choice == LDAP_FILTER_NOT) { add_this->f_next = add_to->f_list; add_to->f_list = add_this; + filter_compute_hash(add_to); + return_this = add_to; } else { /* find end of list, add the filter */ for (fjoin = add_to->f_list; fjoin != NULL; fjoin = fjoin->f_next) { if (fjoin->f_next == NULL) { fjoin->f_next = add_this; + filter_compute_hash(add_to); + return_this = add_to; break; } } } - /* - * Make sure we sync the filter flags. The origin filters may have flags - * we still need on the outer layer! - */ - add_to->f_flags |= add_this->f_flags; - filter_compute_hash(add_to); - return_this = add_to; } else { fjoin = (struct slapi_filter *)slapi_ch_calloc(1, sizeof(struct slapi_filter)); fjoin->f_choice = ftype; @@ -890,8 +883,6 @@ slapi_filter_join_ex(int ftype, struct slapi_filter *f1, struct slapi_filter *f2 fjoin->f_list = f1; f1->f_next = f2; } - /* Make sure any flags that were set move to the outer parent */ - fjoin->f_flags |= f1->f_flags | f2->f_flags; filter_compute_hash(fjoin); return_this = fjoin; } @@ -1536,175 +1527,47 @@ ruv_check_filter(Slapi_Filter *f) return 0; /* Not a RUV filter */ }
-/* - * To help filter optimise we break out the list manipulation - * code. - */ - -static void -filter_prioritise_element(Slapi_Filter **list, Slapi_Filter **head, Slapi_Filter **tail, Slapi_Filter **f_prev, Slapi_Filter **f_cur) { - if (*f_prev != NULL) { - (*f_prev)->f_next = (*f_cur)->f_next; - } else if (*list == *f_cur) { - *list = (*f_cur)->f_next; - }
- if (*head == NULL) { - *head = *f_cur; - *tail = *f_cur; - (*f_cur)->f_next = NULL; - } else { - (*f_cur)->f_next = *head; - *head = *f_cur; - } -} - -static void -filter_merge_subfilter(Slapi_Filter **list, Slapi_Filter **f_prev, Slapi_Filter **f_cur, Slapi_Filter **f_next) { - /* Cut our current AND/OR out */ - if (*f_prev != NULL) { - (*f_prev)->f_next = (*f_cur)->f_next; - } else if (*list == *f_cur) { - *list = (*f_cur)->f_next; - } - (*f_next) = (*f_cur)->f_next; - - /* Look ahead to the end of our list, without the f_cur. */ - Slapi_Filter *f_cur_tail = *list; - while (f_cur_tail->f_next != NULL) { - f_cur_tail = f_cur_tail->f_next; - } - /* Now append our descendant into the tail */ - f_cur_tail->f_next = (*f_cur)->f_list; - /* Finally free the remainder */ - slapi_filter_free(*f_cur, 0); -} - -/* slapi_filter_optimise +/* filter_optimize * --------------- - * takes a filter and optimises it for fast evaluation - * - * Optimisations are: - * * In OR conditions move substrings early to promote fail-fast of unindexed types - * * In AND conditions move eq types (that are not objectClass) early to promote triggering threshold shortcut - * * In OR conditions, merge all direct child OR conditions into the list. (|(|(a)(b))) == (|(a)(b)) - * * in AND conditions, merge all direct child AND conditions into the list. (&(&(a)(b))) == (&(a)(b)) - * - * In the case of the OR and AND merges, we remove the inner filter because the outer one may have flags set. - * - * In the future this could be backend dependent. + * takes a filter and optimizes it for fast evaluation + * currently this merely ensures that any AND or OR + * does not start with a NOT sub-filter if possible */ -void -slapi_filter_optimise(Slapi_Filter *f) +static void +filter_optimize(Slapi_Filter *f) { - /* - * Today tombstone searches RELY on filter ordering - * and a filter test threshold quirk. We need to avoid - * touching these cases!!! - */ - if (f == NULL || (f->f_flags & SLAPI_FILTER_TOMBSTONE) != 0) { + if (!f) return; - }
switch (f->f_choice) { case LDAP_FILTER_AND: - /* Move all equality searches to the head. */ - /* Merge any direct descendant AND queries into us */ - { - Slapi_Filter *f_prev = NULL; - Slapi_Filter *f_cur = NULL; - Slapi_Filter *f_next = NULL; - - Slapi_Filter *f_op_head = NULL; - Slapi_Filter *f_op_tail = NULL; - - f_cur = f->f_list; - while(f_cur != NULL) { - - switch(f_cur->f_choice) { - case LDAP_FILTER_AND: - filter_merge_subfilter(&(f->f_list), &f_prev, &f_cur, &f_next); - f_cur = f_next; - break; - case LDAP_FILTER_EQUALITY: - if (strcasecmp(f_cur->f_avtype, "objectclass") != 0) { - f_next = f_cur->f_next; - /* Cut it out */ - filter_prioritise_element(&(f->f_list), &f_op_head, &f_op_tail, &f_prev, &f_cur); - /* Don't change previous, because we remove this f_cur */ - f_cur = f_next; - break; - } else { - /* Move along */ - f_prev = f_cur; - f_cur = f_cur->f_next; - } - break; - default: - /* Move along */ - f_prev = f_cur; - f_cur = f_cur->f_next; + case LDAP_FILTER_OR: { + /* first optimize children */ + filter_optimize(f->f_list); + + /* optimize this */ + if (f->f_list->f_choice == LDAP_FILTER_NOT) { + Slapi_Filter *f_prev = 0; + Slapi_Filter *f_child = 0; + + /* grab a non not filter to place at start */ + for (f_child = f->f_list; f_child != 0; f_child = f_child->f_next) { + if (f_child->f_choice != LDAP_FILTER_NOT) { + /* we have a winner, do swap */ + if (f_prev) + f_prev->f_next = f_child->f_next; + f_child->f_next = f->f_list; + f->f_list = f_child; break; } - }
- if (f_op_head != NULL) { - f_op_tail->f_next = f->f_list; - f->f_list = f_op_head; + f_prev = f_child; } } - /* finally optimize children */ - slapi_filter_optimise(f->f_list); - - break; - - case LDAP_FILTER_OR: - /* Move all substring searches to the head. */ - { - Slapi_Filter *f_prev = NULL; - Slapi_Filter *f_cur = NULL; - Slapi_Filter *f_next = NULL; - - Slapi_Filter *f_op_head = NULL; - Slapi_Filter *f_op_tail = NULL; - - f_cur = f->f_list; - while(f_cur != NULL) { - - switch(f_cur->f_choice) { - case LDAP_FILTER_OR: - filter_merge_subfilter(&(f->f_list), &f_prev, &f_cur, &f_next); - f_cur = f_next; - break; - case LDAP_FILTER_APPROX: - case LDAP_FILTER_GE: - case LDAP_FILTER_LE: - case LDAP_FILTER_SUBSTRINGS: - f_next = f_cur->f_next; - /* Cut it out */ - filter_prioritise_element(&(f->f_list), &f_op_head, &f_op_tail, &f_prev, &f_cur); - /* Don't change previous, because we remove this f_cur */ - f_cur = f_next; - break; - default: - /* Move along */ - f_prev = f_cur; - f_cur = f_cur->f_next; - break; - } - } - if (f_op_head != NULL) { - f_op_tail->f_next = f->f_list; - f->f_list = f_op_head; - } - } - /* finally optimize children */ - slapi_filter_optimise(f->f_list); - - break; - + } default: - slapi_filter_optimise(f->f_next); + filter_optimize(f->f_next); break; } } diff --git a/ldap/servers/slapd/index_subsystem.c b/ldap/servers/slapd/index_subsystem.c index 7d7e1b7..97cb7b4 100644 --- a/ldap/servers/slapd/index_subsystem.c +++ b/ldap/servers/slapd/index_subsystem.c @@ -191,10 +191,6 @@ index_subsys_assign_filter_decoders(Slapi_PBlock *pb) char *subsystem = "index_subsys_assign_filter_decoders"; char logbuf[1024];
- if (!theCache) { - return rc; - } - /* extract the filter */ slapi_pblock_get(pb, SLAPI_SEARCH_FILTER, &f); if (f) { diff --git a/ldap/servers/slapd/slapi-private.h b/ldap/servers/slapd/slapi-private.h index 837ca8e..d93693b 100644 --- a/ldap/servers/slapd/slapi-private.h +++ b/ldap/servers/slapd/slapi-private.h @@ -383,7 +383,6 @@ void ndn_cache_get_stats(uint64_t *hits, uint64_t *tries, uint64_t *size, uint64 int filter_flag_is_set(const Slapi_Filter *f, unsigned char flag); char *slapi_filter_to_string(const Slapi_Filter *f, char *buffer, size_t bufsize); char *slapi_filter_to_string_internal(const struct slapi_filter *f, char *buf, size_t *bufsize); -void slapi_filter_optimise(Slapi_Filter *f);
/* operation.c */
389-commits@lists.fedoraproject.org
-
git repository hosting