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

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