[PATCH] 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.

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