Full_Name: Hallvard B Furuseth Version: HEAD OS: URL: ftp://ftp.openldap.org/incoming/ Submission from: (NULL) (193.157.206.208) 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.

################################

Test case:

#### sortvals.conf include servers/slapd/schema/core.schema attributetype ( 1.3.6.1.4.1.4203.666.777.1 NAME 'boolTest' EQUALITY booleanMatch SYNTAX 1.3.6.1.4.1.1466.115.121.1.7 ) # dnQualifier has string syntax and an ORDERING rule. sortvals boolTest dnQualifier database hdb directory sortvals.dir suffix st=top # shut up monitor warning database monitor

#### sortvals.ldif dn: st=top boolTest: TRUE boolTest: FALSE dnQualifier: bbbb dnQualifier: dd dnQualifier: aaaa objectClass: locality objectClass: extensibleObject st: top

dn: st=sub,st=top boolTest: FALSE boolTest: TRUE dnQualifier: aa dnQualifier: dddd objectClass: locality objectClass: extensibleObject st: sub

#### sortvals.sh #!/bin/sh -e mkdir sortvals.dir touch sortvals.dir/DB_CONFIG 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. dn: st=top boolTest: TRUE boolTest: FALSE dnQualifier: dd dnQualifier: aaaa dnQualifier: bbbb

dn: st=sub,st=top boolTest: FALSE boolTest: TRUE dnQualifier: aa dnQualifier: dddd

=== dn: st=sub,st=top boolTest: FALSE boolTest: TRUE dnQualifier: aa dnQualifier: dddd