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

[hyc@symas.com]

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.

> 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/