(ITS#6722) Sortvals broken for some matching rules

[h.b.furuseth@usit.uio.no]

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