Re: [PATCH] misc: Fix out-of-bounds array write in tdelete (bug 34506)

On 11/08/26 06:56, Florian Weimer wrote:
> Allocate the maximum array sizes directly, instead of resizing
> the arrays as needed.  This eliminates alloca usage from the
> function, and fixes the out-of-bounds accesses.  The asserts
> guard against the bug coming back if the balancing of the tree
> turns out not to work correctly.
> 
> ---
>  misc/tsearch.c | 36 ++++++++++++++++--------------------
>  1 file changed, 16 insertions(+), 20 deletions(-)
> 
> diff --git a/misc/tsearch.c b/misc/tsearch.c
> index 9b2eb34b25..29b323c856 100644
> --- a/misc/tsearch.c
> +++ b/misc/tsearch.c
> @@ -406,12 +406,19 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
>    int cmp;
>    node *rootp = (node *) vrootp;
>    node root, unchained;
> -  /* Stack of nodes so we remember the parents without recursion.  It's
> -     _very_ unlikely that there are paths longer than 40 nodes.  The tree
> -     would need to have around 250.000 nodes.  */
> -  int stacksize = 40;
> +  /* Stack of nodes so we remember the parents without recursion.  The
> +     stack size is based on the theoretical address space sizes (2**32
> +     and 2**63 bytes), the size of the node struct (12 bytes and 24
> +     bytes), and the resulting maximum height of a red-black tree.  */
> +#if __WORDSIZE == 32
> +  enum { stacksize = 60 };
> +#elif __WORDSIZE == 64
> +  enum { stacksize = 120 };
> +#else
> +# error "unknown __WORDSIZE"
> +#endif

So assuming the red-black tree height bound h >= 2·log2(n+1), and
peak transient rebalancing push as h + 1:

 * __WORDSIZE == 32: 
 n ≤ 2^32/12
 log2(n+1) =~ 32 − log2 12 = 32 − 3.585 = 28.415
 h <= 2 × 28.415 = 56.83 -> h <= 56
 peak stack depth = h + 1 = 57

 * __WORDSIZE == 64
 n ≤ 2^53/24
 log2(n+1) =~ 63 − log2 24 = 63 − 4.585 = 58.415
 h <= 2 × 58.415 = 116.83 -> h <= 116
 peak stack depth = h + 1 = 117

I think we can infer this without the using internal definitions:

  enum { ptr_bits = CHAR_BIT * sizeof (void *),
         stacksize = 2 * ptr_bits + 1 };

This yields 65 on 32-bit and 129 on 64-bit. We can tune it down a bit by
subtracting some factor from ptr_bits, but I think this is clear.

The rest looks ok.

>    int sp = 0;
> -  node **nodestack = alloca (sizeof (node *) * stacksize);
> +  node *nodestack[stacksize];
>  
>    if (rootp == NULL)
>      return NULL;
> @@ -424,14 +431,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
>    root = DEREFNODEPTR(rootp);
>    while ((cmp = (*compar) (key, root->key)) != 0)
>      {
> -      if (sp == stacksize)
> -	{
> -	  node **newstack;
> -	  stacksize += 20;
> -	  newstack = alloca (sizeof (node *) * stacksize);
> -	  nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
> -	}
> -
> +      assert (sp < stacksize);
>        nodestack[sp++] = rootp;
>        p = DEREFNODEPTR(rootp);
>        if (cmp < 0)
> @@ -470,13 +470,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
>        node upn;
>        for (;;)
>  	{
> -	  if (sp == stacksize)
> -	    {
> -	      node **newstack;
> -	      stacksize += 20;
> -	      newstack = alloca (sizeof (node *) * stacksize);
> -	      nodestack = memcpy (newstack, nodestack, sp * sizeof (node *));
> -	    }
> +	  assert (sp < stacksize);
>  	  nodestack[sp++] = parentp;
>  	  parentp = up;
>  	  upn = DEREFNODEPTR(up);
> @@ -541,6 +535,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
>  		  SETNODEPTR(pp,q);
>  		  /* Make sure pp is right if the case below tries to use
>  		     it.  */
> +		  assert (sp < stacksize);
>  		  nodestack[sp++] = pp = LEFTPTR(q);
>  		  q = RIGHT(p);
>  		}
> @@ -625,6 +620,7 @@ __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
>  		  SETLEFT(p,RIGHT(q));
>  		  SETRIGHT(q,p);
>  		  SETNODEPTR(pp,q);
> +		  assert (sp < stacksize);
>  		  nodestack[sp++] = pp = RIGHTPTR(q);
>  		  q = LEFT(p);
>  		}
> 
> base-commit: b589bd672c529cf264dc6dfdfa11f73c7e4e1666
>