[Date Prev][Date Next]
(ITS#6722) Sortvals broken for some matching rules
Full_Name: Hallvard B Furuseth
Submission from: (NULL) (188.8.131.52)
Submitted by: hallvard
slapd.conf:sortvals sorts attribute values by the EQUALITY rule's match
result, which can be faster than ORDERING. Or octetStringMatch when no
EQUALITY rule, I suppose. Haven't looked closely. However,
(1) When an attribute has sortvals set, filtering by the ORDERING rule
only tests first/last value. This breaks when the EQUALITY rule gives
a different sort order. E.g. string equality sorts by length before
contents of the normalized value, for speed.
(2) Sortvals should only be settable for attributes whose EQUALITY rule:
- imposes an absolute ordering,
- always succeeds. At least, this seems cleanest to me.
Currently there are no such restrictions:
- At least booleanMatch() returns 0 or 1, never -1. Thus (TRUE, FALSE)
sort randomly. And we cannot control third-party dynamically loaded
EQUALITY rules, nor is it documented they should impose an ordering.
- attr_valfind() proceeds with the binary search when value_match()
fails so the 'match' to partition by is unknown. This makes little
sense, attr_valfind() should fail when this happens.
Thus setting sortvals could break previously working functionality,
which is why I think it may be better to forbid sortvals for
attributes where this can happen. Alternatively, we could allow
it if the user sets an "I really mean it" mark for the attribute.
(3) Also it makes me nervous to see search.c in back-ldap + back-meta
react to SLAP_AT_SORTED_VAL. Are there other backends/overlays which
need to do the same? Can some/most of that code be moved into slapd?
Fixes for (1)-(2):
- Sortvals needs some new flags: One to allow SLAP_AT_SORTED_VAL.
SLAP_ATTR_SORT_IS_ORDERING to tell filterentry that ORDERING can
use sortvals. And something to help set SLAP_ATTR_SORT_IS_ORDERING.
The first would be set for the relevant equality matching rules.
Not sure of the last: It could almost be set if (equality rule ==
ordering rule), but matching rules are passed as parameters so their
implementation can act differently for EQUALITY and ORDERING:-(
- filterentry.c:test_ava_filter() should ignore SLAP_ATTR_SORTED_VALS if
(use == SLAP_MR_ORDERING) && (SLAP_ATTR_SORT_IS_ORDERING is not set).
- booleanMatch() needs a fix. Don't know which others, except a
marginal case: Rules that can set
*matchp = (int) (value->bv_len - asserted->bv_len)
need to be more careful when sizeof(ber_len_t) > sizeof(int).
I assume we can safely truncate to ber_slen_t, i.e. that OpenLDAP
would fail anyway for values with bv_len > max ber_slen_t.
I'll fix this where I see it, but I leave the rest to someone else.
- attr_valfind() should abort the binary search on failure. Possibly
some of its callers must be updated to handle more result codes.
In theory it shouldn't happen anyway with my other suggestions, but
this looks hairy enough that it seems best to be safe.
- The sortvals doc should say it need not sort by ORDERING. Fixing.
attributetype ( 184.108.40.206.4.1.4203.666.777.1 NAME 'boolTest'
SYNTAX 220.127.116.11.4.1.1418.104.22.168.7 )
# dnQualifier has string syntax and an ORDERING rule.
sortvals boolTest dnQualifier
# shut up monitor warning
servers/slapd/slapadd -f sortvals.conf -l sortvals.ldif
(servers/slapd/slapcat -f sortvals.conf &&
echo === &&
servers/slapd/slapcat -f sortvals.conf -a '(dnQualifier<=c)'
) | egrep '^($|[bd=])'
#### slapcat output
# boolTest sorted differently in the two entries,
# 2nd slapcat skips entry #1 since dd <= c even though it has aaaa <= c.