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

[Kurt@OpenLDAP.org]

Your analysis appears to be correct here.  I've committed
changes based upon your suggestions to HEAD.  Please test.

Thanks, Kurt


At 04:42 AM 3/30/2004, wout@science.uva.nl wrote:
>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;