[glibc/release/2.44/master] misc: Fix out-of-bounds array write in tdelete (bug 34506)

https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=d6ff274313d79feb864cc10eb775b91c817a67e9

commit d6ff274313d79feb864cc10eb775b91c817a67e9
Author: Florian Weimer <[email protected]>
Date:   Fri Aug 14 13:41:16 2026 +0200

    misc: Fix out-of-bounds array write in tdelete (bug 34506)
    
    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.
    
    Reviewed-by: Adhemerval Zanella <[email protected]>
    (cherry picked from commit e2789c46e3bfdcd67a82bea9946b315c179e83d3)

Diff:
---
 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);
 		}