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

[hyc@symas.com]

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.

There is no bug here, this ITS is closed.

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/