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

[Adhemerval Zanella Netto]

On 14/08/26 05:19, 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.

LGTM, thanks.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

> 
> ---
> v2: Avoid preprocessor conditionals
>  misc/tsearch.c | 31 +++++++++++--------------------
>  1 file changed, 11 insertions(+), 20 deletions(-)
> 
> diff --git a/misc/tsearch.c b/misc/tsearch.c
> index 9b2eb34b25..e517dfa712 100644
> --- a/misc/tsearch.c
> +++ b/misc/tsearch.c
> @@ -85,6 +85,7 @@
>  #include <assert.h>
>  #include <stdalign.h>
>  #include <stddef.h>
> +#include <stdint.h>
>  #include <stdlib.h>
>  #include <string.h>
>  #include <search.h>
> @@ -406,12 +407,13 @@ __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 a conservative approximation of the maximum height
> +     of a red-black tree, based on size of the address space.
> +     Actual numbers are closer to 57 (32 bit) and 117 (63 bit).  */
> +  enum { stacksize = 2 * UINTPTR_WIDTH };
>    int sp = 0;
> -  node **nodestack = alloca (sizeof (node *) * stacksize);
> +  node *nodestack[stacksize];
>  
>    if (rootp == NULL)
>      return NULL;
> @@ -424,14 +426,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 +465,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 +530,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 +615,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
>