Avoid too much stack use in fnmatch.

2 files changed, 128 insertions, 61 deletions

diff --git a/posix/fnmatch.c b/posix/fnmatch.c
index 4baef9e..0af5ee6 100644
--- a/posix/fnmatch.c
+++ b/posix/fnmatch.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991,1992,1993,1996,1997,1998,1999,2000,2001,2002,2003,2007
+/* Copyright (C) 1991,1992,1993,1996,1997,1998,1999,2000,2001,2002,2003,2007,2010
 	Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
@@ -41,6 +41,12 @@
 # include <stdlib.h>
 #endif
 
+#ifdef _LIBC
+# include <alloca.h>
+#else
+# define alloca_account(size., var) alloca (size)
+#endif
+
 /* For platform which support the ISO C amendement 1 functionality we
    support user defined character classes.  */
 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
@@ -330,8 +336,11 @@ fnmatch (pattern, string, flags)
       mbstate_t ps;
       size_t n;
       const char *p;
+      wchar_t *wpattern_malloc = NULL;
       wchar_t *wpattern;
+      wchar_t *wstring_malloc = NULL;
       wchar_t *wstring;
+      size_t alloca_used = 0;
 
       /* Convert the strings into wide characters.  */
       memset (&ps, '\0', sizeof (ps));
@@ -343,7 +352,8 @@ fnmatch (pattern, string, flags)
 #endif
       if (__builtin_expect (n < 1024, 1))
 	{
-	  wpattern = (wchar_t *) alloca ((n + 1) * sizeof (wchar_t));
+	  wpattern = (wchar_t *) alloca_account ((n + 1) * sizeof (wchar_t),
+						 alloca_used);
 	  n = mbsrtowcs (wpattern, &p, n + 1, &ps);
 	  if (__builtin_expect (n == (size_t) -1, 0))
 	    /* Something wrong.
@@ -365,8 +375,11 @@ fnmatch (pattern, string, flags)
 	       XXX Do we have to set `errno' to something which mbsrtows hasn't
 	       already done?  */
 	    return -1;
-	  wpattern = (wchar_t *) alloca ((n + 1) * sizeof (wchar_t));
+	  wpattern_malloc = wpattern
+	    = (wchar_t *) malloc ((n + 1) * sizeof (wchar_t));
 	  assert (mbsinit (&ps));
+	  if (wpattern == NULL)
+	    return -2;
 	  (void) mbsrtowcs (wpattern, &pattern, n + 1, &ps);
 	}
 
@@ -379,13 +392,18 @@ fnmatch (pattern, string, flags)
       p = string;
       if (__builtin_expect (n < 1024, 1))
 	{
-	  wstring = (wchar_t *) alloca ((n + 1) * sizeof (wchar_t));
+	  wstring = (wchar_t *) alloca_account ((n + 1) * sizeof (wchar_t),
+						alloca_used);
 	  n = mbsrtowcs (wstring, &p, n + 1, &ps);
 	  if (__builtin_expect (n == (size_t) -1, 0))
-	    /* Something wrong.
-	       XXX Do we have to set `errno' to something which mbsrtows hasn't
-	       already done?  */
-	    return -1;
+	    {
+	      /* Something wrong.
+		 XXX Do we have to set `errno' to something which
+		 mbsrtows hasn't already done?  */
+	    free_return:
+	      free (wpattern_malloc);
+	      return -1;
+	    }
 	  if (p)
 	    {
 	      memset (&ps, '\0', sizeof (ps));
@@ -400,19 +418,32 @@ fnmatch (pattern, string, flags)
 	    /* Something wrong.
 	       XXX Do we have to set `errno' to something which mbsrtows hasn't
 	       already done?  */
-	    return -1;
-	  wstring = (wchar_t *) alloca ((n + 1) * sizeof (wchar_t));
+	    goto free_return;
+
+	  wstring_malloc = wstring
+	    = (wchar_t *) malloc ((n + 1) * sizeof (wchar_t));
+	  if (wstring == NULL)
+	    {
+	      free (wpattern_malloc);
+	      return -2;
+	    }
 	  assert (mbsinit (&ps));
 	  (void) mbsrtowcs (wstring, &string, n + 1, &ps);
 	}
 
-      return internal_fnwmatch (wpattern, wstring, wstring + n,
-				flags & FNM_PERIOD, flags, NULL);
+      int res = internal_fnwmatch (wpattern, wstring, wstring + n,
+				   flags & FNM_PERIOD, flags, NULL,
+				   alloca_used);
+
+      free (wstring_malloc);
+      free (wpattern_malloc);
+
+      return res;
     }
 # endif  /* mbstate_t and mbsrtowcs or _LIBC.  */
 
   return internal_fnmatch (pattern, string, string + strlen (string),
-			   flags & FNM_PERIOD, flags, NULL);
+			   flags & FNM_PERIOD, flags, NULL, 0);
 }
 
 # ifdef _LIBC
diff --git a/posix/fnmatch_loop.c b/posix/fnmatch_loop.c
index 67c0ee4..c8e52a6 100644
--- a/posix/fnmatch_loop.c
+++ b/posix/fnmatch_loop.c
@@ -1,4 +1,4 @@
-/* Copyright (C) 1991-1993,1996-2001,2003-2005,2007
+/* Copyright (C) 1991-1993,1996-2001,2003-2005,2007,2010
    Free Software Foundation, Inc.
    This file is part of the GNU C Library.
 
@@ -28,22 +28,24 @@ struct STRUCT
    it matches, nonzero if not.  */
 static int FCT (const CHAR *pattern, const CHAR *string,
 		const CHAR *string_end, int no_leading_period, int flags,
-		struct STRUCT *ends)
+		struct STRUCT *ends, size_t alloca_used)
      internal_function;
 static int EXT (INT opt, const CHAR *pattern, const CHAR *string,
-		const CHAR *string_end, int no_leading_period, int flags)
+		const CHAR *string_end, int no_leading_period, int flags,
+		size_t alloca_used)
      internal_function;
 static const CHAR *END (const CHAR *patternp) internal_function;
 
 static int
 internal_function
-FCT (pattern, string, string_end, no_leading_period, flags, ends)
+FCT (pattern, string, string_end, no_leading_period, flags, ends, alloca_used)
      const CHAR *pattern;
      const CHAR *string;
      const CHAR *string_end;
      int no_leading_period;
      int flags;
      struct STRUCT *ends;
+     size_t alloca_used;
 {
   register const CHAR *p = pattern, *n = string;
   register UCHAR c;
@@ -67,10 +69,8 @@ FCT (pattern, string, string_end, no_leading_period, flags, ends)
 	case L('?'):
 	  if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
 	    {
-	      int res;
-
-	      res = EXT (c, p, n, string_end, no_leading_period,
-			 flags);
+	      int res = EXT (c, p, n, string_end, no_leading_period,
+			     flags, alloca_used);
 	      if (res != -1)
 		return res;
 	    }
@@ -99,10 +99,8 @@ FCT (pattern, string, string_end, no_leading_period, flags, ends)
 	case L('*'):
 	  if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
 	    {
-	      int res;
-
-	      res = EXT (c, p, n, string_end, no_leading_period,
-			 flags);
+	      int res = EXT (c, p, n, string_end, no_leading_period,
+			     flags, alloca_used);
 	      if (res != -1)
 		return res;
 	    }
@@ -191,7 +189,7 @@ FCT (pattern, string, string_end, no_leading_period, flags, ends)
 
 		  for (--p; n < endp; ++n, no_leading_period = 0)
 		    if (FCT (p, n, string_end, no_leading_period, flags2,
-			     &end) == 0)
+			     &end, alloca_used) == 0)
 		      goto found;
 		}
 	      else if (c == L('/') && (flags & FNM_FILE_NAME))
@@ -200,7 +198,7 @@ FCT (pattern, string, string_end, no_leading_period, flags, ends)
 		    ++n;
 		  if (n < string_end && *n == L('/')
 		      && (FCT (p, n + 1, string_end, flags & FNM_PERIOD, flags,
-			       NULL) == 0))
+			       NULL, alloca_used) == 0))
 		    return 0;
 		}
 	      else
@@ -214,7 +212,7 @@ FCT (pattern, string, string_end, no_leading_period, flags, ends)
 		  for (--p; n < endp; ++n, no_leading_period = 0)
 		    if (FOLD ((UCHAR) *n) == c
 			&& (FCT (p, n, string_end, no_leading_period, flags2,
-				 &end) == 0))
+				 &end, alloca_used) == 0))
 		      {
 		      found:
 			if (end.pattern == NULL)
@@ -749,7 +747,7 @@ FCT (pattern, string, string_end, no_leading_period, flags, ends)
 					       _NL_COLLATE_SYMB_EXTRAMB);
 
 				/* Locate the character in the hashing
-                                   table.  */
+				   table.  */
 				hash = elem_hash (str, c1);
 
 				idx = 0;
@@ -971,9 +969,8 @@ FCT (pattern, string, string_end, no_leading_period, flags, ends)
 	case L('!'):
 	  if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
 	    {
-	      int res;
-
-	      res = EXT (c, p, n, string_end, no_leading_period, flags);
+	      int res = EXT (c, p, n, string_end, no_leading_period, flags,
+			     alloca_used);
 	      if (res != -1)
 		return res;
 	    }
@@ -1052,26 +1049,32 @@ END (const CHAR *pattern)
 static int
 internal_function
 EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
-     int no_leading_period, int flags)
+     int no_leading_period, int flags, size_t alloca_used)
 {
   const CHAR *startp;
   int level;
   struct patternlist
   {
     struct patternlist *next;
+    CHAR malloced;
     CHAR str[0];
   } *list = NULL;
   struct patternlist **lastp = &list;
   size_t pattern_len = STRLEN (pattern);
+  int any_malloced = 0;
   const CHAR *p;
   const CHAR *rs;
+  int retval = 0;
 
   /* Parse the pattern.  Store the individual parts in the list.  */
   level = 0;
   for (startp = p = pattern + 1; level >= 0; ++p)
     if (*p == L('\0'))
-      /* This is an invalid pattern.  */
-      return -1;
+      {
+	/* This is an invalid pattern.  */
+	retval = -1;
+	goto out;
+      }
     else if (*p == L('['))
       {
 	/* Handle brackets special.  */
@@ -1088,8 +1091,11 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 	/* Skip over all characters of the list.  */
 	while (*p != L(']'))
 	  if (*p++ == L('\0'))
-	    /* This is no valid pattern.  */
-	    return -1;
+	    {
+	      /* This is no valid pattern.  */
+	      retval = -1;
+	      goto out;
+	    }
       }
     else if ((*p == L('?') || *p == L('*') || *p == L('+') || *p == L('@')
 	      || *p == L('!')) && p[1] == L('('))
@@ -1102,15 +1108,27 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 	    /* This means we found the end of the pattern.  */
 #define NEW_PATTERN \
 	    struct patternlist *newp;					      \
-									      \
-	    if (opt == L('?') || opt == L('@'))				      \
-	      newp = alloca (sizeof (struct patternlist)		      \
-			     + (pattern_len * sizeof (CHAR)));		      \
+	    size_t slen = (opt == L('?') || opt == L('@')		      \
+			   ? pattern_len : (p - startp + 1));		      \
+	    slen = sizeof (struct patternlist) + (slen * sizeof (CHAR));      \
+	    int malloced = ! __libc_use_alloca (alloca_used + slen);	      \
+	    if (__builtin_expect (malloced, 0))				      \
+	      {								      \
+		newp = alloca_account (slen, alloca_used);		      \
+		any_malloced = 1;					      \
+	      }								      \
 	    else							      \
-	      newp = alloca (sizeof (struct patternlist)		      \
-			     + ((p - startp + 1) * sizeof (CHAR)));	      \
-	    *((CHAR *) MEMPCPY (newp->str, startp, p - startp)) = L('\0');    \
+	      {								      \
+		newp = malloc (slen);					      \
+		if (newp == NULL)					      \
+		  {							      \
+		    retval = -2;					      \
+		    goto out;						      \
+		  }							      \
+	      }								      \
 	    newp->next = NULL;						      \
+	    newp->malloced = malloced;					      \
+	    *((CHAR *) MEMPCPY (newp->str, startp, p - startp)) = L('\0');    \
 	    *lastp = newp;						      \
 	    lastp = &newp->next
 	    NEW_PATTERN;
@@ -1131,8 +1149,9 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
   switch (opt)
     {
     case L('*'):
-      if (FCT (p, string, string_end, no_leading_period, flags, NULL) == 0)
-	return 0;
+      if (FCT (p, string, string_end, no_leading_period, flags, NULL,
+	       alloca_used) == 0)
+	goto success;
       /* FALLTHROUGH */
 
     case L('+'):
@@ -1143,7 +1162,7 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 	       current pattern.  */
 	    if (FCT (list->str, string, rs, no_leading_period,
 		     flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD,
-		     NULL) == 0
+		     NULL, alloca_used) == 0
 		/* This was successful.  Now match the rest with the rest
 		   of the pattern.  */
 		&& (FCT (p, rs, string_end,
@@ -1151,7 +1170,7 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 			 ? no_leading_period
 			 : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
 			 flags & FNM_FILE_NAME
-			 ? flags : flags & ~FNM_PERIOD, NULL) == 0
+			 ? flags : flags & ~FNM_PERIOD, NULL, alloca_used) == 0
 		    /* This didn't work.  Try the whole pattern.  */
 		    || (rs != string
 			&& FCT (pattern - 1, rs, string_end,
@@ -1160,18 +1179,21 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 				: (rs[-1] == '/' && NO_LEADING_PERIOD (flags)
 				   ? 1 : 0),
 				flags & FNM_FILE_NAME
-				? flags : flags & ~FNM_PERIOD, NULL) == 0)))
+				? flags : flags & ~FNM_PERIOD, NULL,
+				alloca_used) == 0)))
 	      /* It worked.  Signal success.  */
-	      return 0;
+	      goto success;
 	}
       while ((list = list->next) != NULL);
 
       /* None of the patterns lead to a match.  */
-      return FNM_NOMATCH;
+      retval = FNM_NOMATCH;
+      break;
 
     case L('?'):
-      if (FCT (p, string, string_end, no_leading_period, flags, NULL) == 0)
-	return 0;
+      if (FCT (p, string, string_end, no_leading_period, flags, NULL,
+	       alloca_used) == 0)
+	goto success;
       /* FALLTHROUGH */
 
     case L('@'):
@@ -1183,13 +1205,14 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 	if (FCT (STRCAT (list->str, p), string, string_end,
 		 no_leading_period,
 		 flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD,
-		 NULL) == 0)
+		 NULL, alloca_used) == 0)
 	  /* It worked.  Signal success.  */
-	  return 0;
+	  goto success;
       while ((list = list->next) != NULL);
 
       /* None of the patterns lead to a match.  */
-      return FNM_NOMATCH;
+      retval = FNM_NOMATCH;
+      break;
 
     case L('!'):
       for (rs = string; rs <= string_end; ++rs)
@@ -1199,7 +1222,7 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 	  for (runp = list; runp != NULL; runp = runp->next)
 	    if (FCT (runp->str, string, rs,  no_leading_period,
 		     flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD,
-		     NULL) == 0)
+		     NULL, alloca_used) == 0)
 	      break;
 
 	  /* If none of the patterns matched see whether the rest does.  */
@@ -1209,21 +1232,34 @@ EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
 		       ? no_leading_period
 		       : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
 		       flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD,
-		       NULL) == 0))
+		       NULL, alloca_used) == 0))
 	    /* This is successful.  */
-	    return 0;
+	    goto success;
 	}
 
       /* None of the patterns together with the rest of the pattern
 	 lead to a match.  */
-      return FNM_NOMATCH;
+      retval = FNM_NOMATCH;
+      break;
 
     default:
       assert (! "Invalid extended matching operator");
+      retval = -1;
       break;
     }
 
-  return -1;
+ success:
+ out:
+  if (any_malloced)
+    while (list != NULL)
+      {
+	struct patternlist *old = list;
+	list = list->next;
+	if (old->malloced)
+	  free (old);
+      }
+
+  return retval;
 }