9:10 p.m.
Hi there,
Would really like a second opinion here (especially looking at you Ludwig since you know
this code well) about the behaviour of the filter test code.
I have been following up on the filter optimisation patch to understand why in some
conditions it causes IPA to fail.
Examining the logs that Mark provided me (thank you!!!), I have checked a number of cases
that looked like they could be suspect. Most of these were conditions where searches
yielded nentries=0, but some conditions were true.
An example of a query like this was also raised on the RH bugzilla. Here it is exploded to
make it easier to see:
ORIGINAL:
(&
(&
(|
(usercertificate;binary=)
(ipaCertMapData=X509:<I>O=EXAMPLE.TEST,CN=Certificate
Authority<S>O=EXAMPLE.TEST,CN=ipauser1)
(altsecurityidentities=X509:<I>O=EXAMPLE.TEST,CN=Certificate
Authority<S>O=EXAMPLE.TEST,CN=ipauser1)
)
(objectClass=posixAccount)
(uid=*)
(&
(uidNumber=*)
(!
(uidNumber=0)
)
)
)
(objectClass=ipaIDObject)
)
OPTIMISED:
(|
(objectclass=referral)
(&
(|
(usercertificate;binary=)
(ipaCertMapData=X509:<I>O=EXAMPLE.TEST,CN=Certificate
Authority<S>O=EXAMPLE.TEST,CN=ipauser1)
(altsecurityidentities=X509:<I>O=EXAMPLE.TEST,CN=Certificate
Authority<S>O=EXAMPLE.TEST,CN=ipauser1)
)
(objectClass=posixAccount)
(uid=*)
(uidNumber=*)
(!
(uidNumber=0)
)
(objectClass=ipaIDObject)
)
)
To me, observing this, these are identical - it appears the re-arrangement has worked to
fold the nested & conditions, and the re-arrangement has not altered or lost
components of the filter.
As a result, I think that it is not the filter optimisation itself that is suspect, but
the fact that the filter optimiser will cause the filter execution code to operate in a
different order of operations. An important aspect of the optimisation is the we assume
the filter test *must* be executed such that the remaining conditions of the filter are
upheld.
Observing the code I am wondering if there may be a logic error in the application of the
filter test bypass flags.
Note that in this case all line numbers are from branch:
https://pagure.io/389-ds-base/pull-request/50252
All searches take place in ldbm_search.c, starting in ldbm_back_search on line 306. The
actual candidate set is built on line 625 via build_candidate_list.
On line ldbm_search.c:876 the filter bypass is evaluated by:
if (li->li_filter_bypass && NULL != candidates && !virtual_list_view
&& !lookup_returned_allids) {
}
li_filter_bypass comes from ldbm_config.c:1614, and appears to default to 1 after
inspection of dse.ldif (nsslapd-search-bypass-filter-test: on). candidates should be !=
NULL, and !vlv would be upheld. This means the condition now is on
not-lookup_returned_allids.
In build_candidate_list, lookup_returned_allids for a subtree search is set in
subtree_candidates ldbm_search.c:1140. This is determined by checking that candidates is
not NULL, and that candidates is equivalent to ALLIDS. Note that if the candidate set is
partially evaluated here this would cause allids_before_scopingp (lookup_returned_allids)
to be false.
So at this point, all conditions on ldbm_search.c:876 should be met. Imagine we have a
partial candidate set, below the filter test threshold. This would cause idl_intersection
or idl_union etc to execute: slapi_be_set_flag(be, SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
to indicate the partial nature of the candidate set.
However I believe the issue may come from can_skip_filter_test in ldbm_search.c:1289. In
this function the flag SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST is *NOT* evaluated. Only
*other* conditions are asserted about the state of the candidate set and scoping.
This means the flag SR_FLAG_CAN_SKIP_FILTER_TEST may be incorrectly applied to
sr->sr_flags.
If my memory serves correctly, this then would cause ldbm_back_next_search_entry_ext
ldbm_search.c:1643 to now consider the candidate set members valid and the filter test is
*not* run.
It’s important to note, that the DONT_BYPASS flag is only referenced in these locations:
ds I0> grep -r -n -e 'BYPASS_FILTER' ldap
ldap/servers/slapd/back-ldbm/ldbm_search.c:164: * In case
SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST is set,
ldap/servers/slapd/back-ldbm/ldbm_search.c:167: slapi_be_unset_flag(be,
SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
ldap/servers/slapd/back-ldbm/ldbm_search.c:1087: *lookup_returned_allidsp =
slapi_be_is_flag_set(be, SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
ldap/servers/slapd/back-ldbm/idl_common.c:248: slapi_be_set_flag(be,
SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
ldap/servers/slapd/back-ldbm/idl_common.c:252: slapi_be_set_flag(be,
SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
ldap/servers/slapd/back-ldbm/idl_common.c:366: slapi_be_set_flag(be,
SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
ldap/servers/slapd/back-ldbm/idl_set.c:354: slapi_be_set_flag(be,
SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
ldap/servers/slapd/back-ldbm/idl_set.c:374: slapi_be_set_flag(be,
SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
ldap/servers/slapd/slapi-plugin.h:6455:#define SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST 0x10
/* force to call filter_test (search only) */
Importantly note, that the only location where we GET this flag is:
ldap/servers/slapd/back-ldbm/ldbm_search.c:1087: *lookup_returned_allidsp =
slapi_be_is_flag_set(be, SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST);
Which is used as part of onelevel_candidates to set the lookup_returned_allidsp flag.
This could cause a non-matching candidate set to be returned as the filter test was *NOT*
run. The candidate set would be legitimately returned due to the filter test threshold
optimisation. I am concerned this may be the case, because the filter above was (likely)
intended for the following entry:
dn: uid=ipauser1,cn=users,cn=accounts,dc=example,dc=test
givenName: f
sn: f
uid: ipauser1
cn: f f
displayName: f f
initials: ff
gecos: f f
krbPrincipalName: ipauser1(a)EXAMPLE.TEST
objectClass: top
objectClass: person
objectClass: organizationalperson
objectClass: inetorgperson
objectClass: inetuser
objectClass: posixaccount
objectClass: krbprincipalaux
objectClass: krbticketpolicyaux
objectClass: ipaobject
objectClass: ipasshuser
objectClass: ipaSshGroupOfPubKeys
objectClass: mepOriginEntry
objectClass: ipacertmapobject
loginShell: /bin/sh
homeDirectory: /home/ipauser1
mail: ipauser1(a)example.test
krbCanonicalName: ipauser1(a)EXAMPLE.TEST
creatorsName: uid=admin,cn=users,cn=accounts,dc=example,dc=test
modifiersName: uid=admin,cn=users,cn=accounts,dc=example,dc=test
createTimestamp: 20190418161833Z
modifyTimestamp: 20190418162000Z
nsUniqueId: 88b5ac01-61f511e9-8106b510-ee60ba02
ipaUniqueID: 9cabc1f4-61f5-11e9-babc-5254000413f9
uidNumber: 64000001
gidNumber: 64000001
mepManagedEntry: cn=ipauser1,cn=groups,cn=accounts,dc=example,dc=test
memberOf: cn=ipausers,cn=groups,cn=accounts,dc=example,dc=test
ipaCertMapData: X509:<I>O=EXAMPLE.TEST,CN=Certificate
Authority<S>O=EXAMPLE.TE
ST,CN=ipauser1
Important to note here, the condition (objectClass=ipaIDObject) is NOT met on this
object, yet I suspect IPA may expect this object to be returned on the filter above. There
may be other possible errors here too.
So I’d like my thoughts here to be checked and evaluated for sanity. I think that the fix
is a (partial) patch as follows:
@@ -1288,12 +1288,18 @@ grok_filter(struct slapi_filter *f)
static int
can_skip_filter_test(
Slapi_PBlock *pb __attribute__((unused)),
+ backend *be,
struct slapi_filter *f,
int scope,
IDList *idl)
{
int rc = 0;
+ /* Did the search operation tell us NOT to skip the filter test? */
+ if (slapi_be_is_flag_set(be, SLAPI_BE_FLAG_DONT_BYPASS_FILTERTEST)) {
+ return rc;
+ }
+
/* Is the ID list ALLIDS ? */
if (ALLIDS(idl)) {
/* If so, then can't optimize */
An alternate patch could be to check the DONT_BYPASS flag inside of subtree_candidates to
set the allids_before_scopingp (lookup_returned_allids) flags, which may or may not be
more consistent with other server behaviours.
Testing this as a patch with filter optimisation disabled but bypass set passes basic +
filter suites. Enabling filter optimisation and the bypass patch also passes both basic
and filter.
Another method to verify this, would be to set nsslapd-search-bypass-filter-test: verify
in dse.ldif and see if there are verification errors in the output.
CONCLUSION:
It may be that filter optimisation is highlighting incorrect ipa queries by executing
their components in a different yet valid order, rather than actually causing corruption
or other issues. It could be that we have allowed such queries to evaluate as true due to
a mistake in the application of the filter test in our search code.
—
Sincerely,
William Brown
Senior Software Engineer, 389 Directory Server
SUSE Labs