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

[ulrich.windl@rz.uni-regensburg.de]

On 28 Jan 2009 at 13:06, Howard Chu wrote:

> Ulrich.Windl@rz.uni-regensburg.de wrote:
> > 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.
> 
> You're misreading the code. The stack is 8*sizeof(void *) which means 32 
> elements deep on a 32 bit machine, and 64 deep on a 64 bit machine. There is 
> no possibility of overflow now or for several years to come.

OK! I was confused by the terrible programming style at that point: as the array 
elements are of the proper type (and not bytes), there is no need for a sizeof 
here: I see no reason why the depth of the tree to be allowed should depend on the 
length of a pointer, maning: If you want 32, why don't you write 32? So the worst 
case stack depth would be something like "log2(2^32/(sizeof(void *) * 5))" ("5" 
being 2 links + 2 threading marks + 1 data pointer), something near 32-5 == 27 
(for 32-bit machines) and 64-6 == 58. Practically the latter could be safely 
reduced to a value around 42 IMHO.

> 
> > 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.
> 
> -- 
>    -- Howard Chu
>    CTO, Symas Corp.           http://www.symas.com
>    Director, Highland Sun     http://highlandsun.com/hyc/
>    Chief Architect, OpenLDAP  http://www.openldap.org/project/