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.