delete from dn2id database bug in back-ldbm/idl.c (ITS#3046)

[wout@science.uva.nl]

Full_Name: Wout van Albada
Version: 2.2.6
OS: Solaris 9
URL: 
Submission from: (NULL) (146.50.3.34)


There's a bug in idl.c in the back-ldbm backend for slapd.
This involves version 2.2.6 and any other versions using
the same idl.c.

When idl_delete_key() tries to remove an id from an indirect
block, it sometimes fails to locate the id in question (even
though it does exist) and then doesn't remove it. Function
idl_delete_key() gets tricked by the unreliable result coming
from idl_find(). The bug occurs around line 961 in idl.c.

>From the comments around idl_find():
    Binary search for id in block, return index. An
    index is always returned, even with no match. If no
    match, the returned index is the insertion point.

This statement is not entirely true however. Assume a
call to idl_find():

    pos = idl_find(idl, x);

If item x is not in list idl, then the correct insertion point
for id x could be idl[pos], but could also be idl[pos+1].
Apparently, the caller must check for this.

The call to idl_find() at line 961 does not check for the
above behaviour and thus sometimes fails to remove the id.
I have seen this happen by analyzing my dn2id.gdbm file.

All other code that uses idl_find() has these kind of checks.

The following patch for idl.c fixes idl_delete_key():


--- idl.c.orig  Tue Mar 30 12:58:57 2004
+++ idl.c       Tue Mar 30 12:59:07 2004
@@ -958,7 +958,11 @@
        for ( j = 0; j<nids; j++ )
 #else
        nids = ID_BLOCK_NIDS(idl);
-       for ( j = idl_find(idl, id); j >= 0; j = -1)    /* execute once */
+       j = idl_find(idl, id);
+       if (ID_BLOCK_ID(idl, j) > id) {
+               j--;
+       }
+       for (; j >= 0; j = -1)          /* execute once */
 #endif
        {
                ID_BLOCK *tmp;