(ITS#5909) stack overflow in tavl_delete (libraries/liblutil/tavl.c)?

[Ulrich.Windl@rz.uni-regensburg.de]

Full_Name: Ulrich Windl
Version: 2.4.11
OS: Linux
URL: ftp://ftp.openldap.org/incoming/
Submission from: (NULL) (132.199.156.178)


Looking for a threaded AVL tree implementation that is supposed to work, I found
libraries/liblutil/tavl.c in openLDAP. I'm no expert on threaded AVL trees, but
there's thing that worries me:
tavl_delete uses two stacks (pptr, pdir) with a size of 8 elements on the
routine' stack. While locating the element to delete, it pushes the parent node
onto the stack.
So from my knowledge this means that for a perfectly filled balanced tree, the
stack will overflow when the tree consists of 2^8 (2^0 + 2^1 + 2^2 + ... + 2^7)
or more nodes, and you are locating a leaf node. Maybe even with fewer nodes.
As the algorithm also pushes an other element onto the stack, the problem could
appear even before 128 nodes.
If the problem occurs, I'd suspect data corruption at least, because one stack
will overwrite the other stack.
I've spotted these uses (besides /libraries/liblutil/testtavl.c) of
tavl_delete(): servers/slapd/overlays/translucent.c,
servers/slapd/overlays/pcache.c

I don't understand that code that much, but if the TAVL isn't used in a very
controlled way (i.e. limiting the number of possible nodes), a problem may be
triggered.

I also noticed that the limitation in the code exists for some time already.