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

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

On 29 Jan 2009 at 2:21, Howard Chu wrote:

> Hardcoding arbitrary limits in portable code is stupid. ("No one will ever 
> need more than 640K...") What may seem (im)practical to you today may be 
> commonplace tomorrow. This code will be maintenance-free no matter what class 
> of machine it's built on, forever. That's *excellent* programming.

Howard,

my proposals were related to the virtual address space, and the specific value for 
64 bit was assuming that no more than 800GB of tree nodes are allocated. Your 
settings relate the depth of the tree to the width of a pointer multiplied by a 
hardcoded value without further explanation.

> 
> There is no bug here, this ITS is closed.

To make a long discussion short, you cold add a comment regarding the use of "8".

Regards,
Ulrich

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