[PATCH] Use saturated arithmetic for overflow detection.

[OndÅej BÃlka <neleai at seznam dot cz>]

Hi,

This is followup to malloc discussion. Here we add simple header for 
saturated arithmetic and simplify existing code.

A case malloc (x * sizeof (tp)) could be treated separately by adding 
XNMALLOC (x, tp) macro.

What needs to be done are system specific headers which will come latter.

Could these be also added to gnulib?

Comments?

	* bits/saturated.h: New file.
	* posix/fnmatch.c (fnmatch): Use saturated arithmetic for
	overflow detection.
	* posix/regcomp.c (init_dfa): Likewise.
	* posix/regexec.c (build_trtable, prune_impossible_nodes,
	re_search_internal, set_regs): Likewise.
	* posix/regex_internal.c (re_dfa_add_node,
	re_string_realloc_buffers): Likewise.
	* posix/regex_internal.h (static): Likewise.
	* stdio-common/vfprintf.c (vfprintf): Likewise.
	* string/strcoll_l.c (STRCOLL): Likewise.
	* sysdeps/posix/getaddrinfo.c (gaih_inet, getaddrinfo): Likewise.


---
 bits/saturated.h            |   34 ++++++++++++++++++++++++++++++++++
 posix/fnmatch.c             |   17 ++++-------------
 posix/regcomp.c             |    6 +-----
 posix/regex_internal.c      |   12 ------------
 posix/regex_internal.h      |    5 +++--
 posix/regexec.c             |   36 +++++++++++-------------------------
 stdio-common/vfprintf.c     |    9 +++++----
 string/strcoll_l.c          |   14 +++++---------
 sysdeps/posix/getaddrinfo.c |   25 +++++++++++--------------
 9 files changed, 74 insertions(+), 84 deletions(-)
 create mode 100644 bits/saturated.h

diff --git a/bits/saturated.h b/bits/saturated.h
new file mode 100644
index 0000000..428017b
--- /dev/null
+++ b/bits/saturated.h
@@ -0,0 +1,34 @@
+/* Saturated unsigned arithmetic for size calculations - generic version.
+   Copyright (C) 2013 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef _SATURATED_H
+#define _SATURATED_H
+
+#define ADD_S(___x, ___y) ({ \
+  size_t __x = (___x), __y = (___y);			\
+  (__x + __y >= __x) ? __x + __y : SIZE_MAX;		\
+})
+
+#define MUL_S(___x, ___y)({ \
+  size_t __x = (___x), __y = (___y);                    \
+  __builtin_constant_p (__x) 				\
+  ? (__y <= SIZE_MAX / __x ? __x * __y : SIZE_MAX)	\
+  : (__x <= SIZE_MAX / __y ? __x * __y : SIZE_MAX);	\
+})
+
+#endif
diff --git a/posix/fnmatch.c b/posix/fnmatch.c
index 0f26a2e..d8073da 100644
--- a/posix/fnmatch.c
+++ b/posix/fnmatch.c
@@ -28,6 +28,7 @@
 #include <errno.h>
 #include <fnmatch.h>
 #include <ctype.h>
+#include <bits/saturated.h>
 
 #if HAVE_STRING_H || defined _LIBC
 # include <string.h>
@@ -373,13 +374,9 @@ fnmatch (pattern, string, flags)
 	       XXX Do we have to set `errno' to something which mbsrtows hasn't
 	       already done?  */
 	    return -1;
-	  if (__builtin_expect (n >= (size_t) -1 / sizeof (wchar_t), 0))
-	    {
-	      __set_errno (ENOMEM);
-	      return -2;
-	    }
+
 	  wpattern_malloc = wpattern
-	    = (wchar_t *) malloc ((n + 1) * sizeof (wchar_t));
+	    = (wchar_t *) malloc (MUL_S (n + 1, sizeof (wchar_t)));
 	  assert (mbsinit (&ps));
 	  if (wpattern == NULL)
 	    return -2;
@@ -422,15 +419,9 @@ fnmatch (pattern, string, flags)
 	       XXX Do we have to set `errno' to something which mbsrtows hasn't
 	       already done?  */
 	    goto free_return;
-	  if (__builtin_expect (n >= (size_t) -1 / sizeof (wchar_t), 0))
-	    {
-	      free (wpattern_malloc);
-	      __set_errno (ENOMEM);
-	      return -2;
-	    }
 
 	  wstring_malloc = wstring
-	    = (wchar_t *) malloc ((n + 1) * sizeof (wchar_t));
+	    = (wchar_t *) malloc (MUL_S (n + 1, sizeof (wchar_t)));
 	  if (wstring == NULL)
 	    {
 	      free (wpattern_malloc);
diff --git a/posix/regcomp.c b/posix/regcomp.c
index 0ffc2fa..c1b302d 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -839,11 +839,7 @@ init_dfa (re_dfa_t *dfa, size_t pat_len)
   /* Force allocation of str_tree_storage the first time.  */
   dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
 
-  /* Avoid overflows.  */
-  if (pat_len == SIZE_MAX)
-    return REG_ESPACE;
-
-  dfa->nodes_alloc = pat_len + 1;
+  dfa->nodes_alloc = ADD_S (pat_len, 1);
   dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
 
   /*  table_size = 2 ^ ceil(log pat_len) */
diff --git a/posix/regex_internal.c b/posix/regex_internal.c
index 0a3830b..a0c1f77 100644
--- a/posix/regex_internal.c
+++ b/posix/regex_internal.c
@@ -134,11 +134,6 @@ re_string_realloc_buffers (re_string_t *pstr, int new_buf_len)
     {
       wint_t *new_wcs;
 
-      /* Avoid overflow in realloc.  */
-      const size_t max_object_size = MAX (sizeof (wint_t), sizeof (int));
-      if (BE (SIZE_MAX / max_object_size < new_buf_len, 0))
-	return REG_ESPACE;
-
       new_wcs = re_realloc (pstr->wcs, wint_t, new_buf_len);
       if (BE (new_wcs == NULL, 0))
 	return REG_ESPACE;
@@ -1416,13 +1411,6 @@ re_dfa_add_node (re_dfa_t *dfa, re_token_t token)
       re_node_set *new_edests, *new_eclosures;
       re_token_t *new_nodes;
 
-      /* Avoid overflows in realloc.  */
-      const size_t max_object_size = MAX (sizeof (re_token_t),
-					  MAX (sizeof (re_node_set),
-					       sizeof (int)));
-      if (BE (SIZE_MAX / max_object_size < new_nodes_alloc, 0))
-	return -1;
-
       new_nodes = re_realloc (dfa->nodes, re_token_t, new_nodes_alloc);
       if (BE (new_nodes == NULL, 0))
 	return -1;
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index 3c94fbe..555d945 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -25,6 +25,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <bits/saturated.h>
 
 #if defined HAVE_LANGINFO_H || defined HAVE_LANGINFO_CODESET || defined _LIBC
 # include <langinfo.h>
@@ -429,8 +430,8 @@ static unsigned int re_string_context_at (const re_string_t *input, int idx,
 # endif
 #endif
 
-#define re_malloc(t,n) ((t *) malloc ((n) * sizeof (t)))
-#define re_realloc(p,t,n) ((t *) realloc (p, (n) * sizeof (t)))
+#define re_malloc(t,n) ((t *) malloc (MUL_S (n, sizeof (t))))
+#define re_realloc(p,t,n) ((t *) realloc (p, MUL_S (n, sizeof (t))))
 #define re_free(p) free (p)
 
 struct bin_tree_t
diff --git a/posix/regexec.c b/posix/regexec.c
index f85c5e8..482a0e4 100644
--- a/posix/regexec.c
+++ b/posix/regexec.c
@@ -18,6 +18,7 @@
    <http://www.gnu.org/licenses/>.  */
 
 #include <stdint.h>
+#include <bits/saturated.h>
 
 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
 				     int n) internal_function;
@@ -703,13 +704,6 @@ re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
      multi character collating element.  */
   if (nmatch > 1 || dfa->has_mb_node)
     {
-      /* Avoid overflow.  */
-      if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
-	{
-	  err = REG_ESPACE;
-	  goto free_return;
-	}
-
       mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
       if (BE (mctx.state_log == NULL, 0))
 	{
@@ -969,10 +963,6 @@ prune_impossible_nodes (mctx)
   match_last = mctx->match_last;
   halt_node = mctx->last_node;
 
-  /* Avoid overflow.  */
-  if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
-    return REG_ESPACE;
-
   sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
   if (BE (sifted_states == NULL, 0))
     {
@@ -1442,8 +1432,10 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
   cur_node = dfa->init_node;
   re_node_set_init_empty (&eps_via_nodes);
 
-  if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
-    prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
+  size_t match_size = MUL_S (nmatch, sizeof (regmatch_t));
+  
+  if (__libc_use_alloca (match_size))
+    prev_idx_match = (regmatch_t *) alloca (match_size);
   else
     {
       prev_idx_match = re_malloc (regmatch_t, nmatch);
@@ -1454,7 +1446,7 @@ set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
 	}
       prev_idx_match_malloced = 1;
     }
-  memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
+  memcpy (prev_idx_match, pmatch, match_size);
 
   for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
     {
@@ -3387,21 +3379,15 @@ build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
   if (BE (err != REG_NOERROR, 0))
     goto out_free;
 
-  /* Avoid arithmetic overflow in size calculation.  */
-  if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
-	    / (3 * sizeof (re_dfastate_t *)))
-	   < ndests),
-	  0))
-    goto out_free;
+  size_t allocated = (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX;
+  size_t needed_memory = MUL_S (MUL_S (ndests, 3), sizeof (re_dfastate_t *));
 
-  if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
-			 + ndests * 3 * sizeof (re_dfastate_t *)))
-    dest_states = (re_dfastate_t **)
-      alloca (ndests * 3 * sizeof (re_dfastate_t *));
+  if (__libc_use_alloca (ADD_S (allocated, needed_memory)))
+    dest_states = (re_dfastate_t **) alloca (needed_memory);
   else
     {
       dest_states = (re_dfastate_t **)
-	malloc (ndests * 3 * sizeof (re_dfastate_t *));
+	malloc (needed_memory);
       if (BE (dest_states == NULL, 0))
 	{
 out_free:
diff --git a/stdio-common/vfprintf.c b/stdio-common/vfprintf.c
index 8cd7a85..3d4b90a 100644
--- a/stdio-common/vfprintf.c
+++ b/stdio-common/vfprintf.c
@@ -25,6 +25,7 @@
 #include <errno.h>
 #include <wchar.h>
 #include <bits/libc-lock.h>
+#include <bits/saturated.h>
 #include <sys/param.h>
 #include <_itoa.h>
 #include <locale/localeinfo.h>
@@ -1067,10 +1068,10 @@ vfprintf (FILE *s, const CHAR_T *format, va_list ap)
 	    /* Allocate dynamically an array which definitely is long	      \
 	       enough for the wide character version.  Each byte in the	      \
 	       multi-byte string can produce at most one wide character.  */  \
-	    if (__libc_use_alloca (len * sizeof (wchar_t)))		      \
-	      string = (CHAR_T *) alloca (len * sizeof (wchar_t));	      \
-	    else if ((string = (CHAR_T *) malloc (len * sizeof (wchar_t)))    \
-		     == NULL)						      \
+	    size_t needed = MUL_S (len, sizeof (wchar_t));		      \
+	    if (__libc_use_alloca (needed))				      \
+	      string = (CHAR_T *) alloca (needed);			      \
+	    else if ((string = (CHAR_T *) malloc (needed)) == NULL)	      \
 	      {								      \
 		done = -1;						      \
 		goto all_done;						      \
diff --git a/string/strcoll_l.c b/string/strcoll_l.c
index 4ee101a..26e6e6e 100644
--- a/string/strcoll_l.c
+++ b/string/strcoll_l.c
@@ -24,6 +24,7 @@
 #include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
+#include <bits/saturated.h>
 
 #ifndef STRING_TYPE
 # define STRING_TYPE char
@@ -524,17 +525,12 @@ STRCOLL (const STRING_TYPE *s1, const STRING_TYPE *s2, __locale_t l)
   memset (&seq1, 0, sizeof (seq1));
   seq2 = seq1;
 
-  size_t size_max = SIZE_MAX / (sizeof (int32_t) + 1);
+  size_t size_needed = MUL_S (s1len + s2len, sizeof (int32_t) + 1);
 
-  if (MIN (s1len, s2len) > size_max
-      || MAX (s1len, s2len) > size_max - MIN (s1len, s2len))
-    {
-      /* If the strings are long enough to cause overflow in the size request,
-         then skip the allocation and proceed with the non-cached routines.  */
-    }
-  else if (! __libc_use_alloca ((s1len + s2len) * (sizeof (int32_t) + 1)))
+
+  if (!__libc_use_alloca (size_needed))
     {
-      seq1.idxarr = (int32_t *) malloc ((s1len + s2len) * (sizeof (int32_t) + 1));
+      seq1.idxarr = (int32_t *) malloc (size_needed);
 
       /* If we failed to allocate memory, we leave everything as NULL so that
 	 we use the nocache version of traversal and comparison functions.  */
diff --git a/sysdeps/posix/getaddrinfo.c b/sysdeps/posix/getaddrinfo.c
index 0f4b885..8697da0 100644
--- a/sysdeps/posix/getaddrinfo.c
+++ b/sysdeps/posix/getaddrinfo.c
@@ -63,6 +63,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 #include <nscd/nscd-client.h>
 #include <nscd/nscd_proto.h>
 #include <resolv/res_hconf.h>
+#include <bits/saturated.h>
 
 #ifdef HAVE_LIBIDN
 extern int __idna_to_ascii_lz (const char *input, char **output, int flags);
@@ -618,14 +619,12 @@ gaih_inet (const char *name, const struct gaih_service *service,
 		      if (i > 0 && *pat != NULL)
 			--i;
 
-		      if (__libc_use_alloca (alloca_used
-					     + i * sizeof (struct gaih_addrtuple)))
-			addrmem = alloca_account (i * sizeof (struct gaih_addrtuple),
-						  alloca_used);
+		      size_t needed = MUL_S (i,  sizeof (struct gaih_addrtuple));
+		      if (__libc_use_alloca (alloca_used + needed))
+			addrmem = alloca_account (needed, alloca_used);
 		      else
 			{
-			  addrmem = malloc (i
-					    * sizeof (struct gaih_addrtuple));
+			  addrmem = malloc (needed);
 			  if (addrmem == NULL)
 			    {
 			      result = -EAI_MEMORY;
@@ -689,15 +688,13 @@ gaih_inet (const char *name, const struct gaih_service *service,
 		  bool added_canon = (req->ai_flags & AI_CANONNAME) == 0;
 		  char *addrs = air->addrs;
 
-		  if (__libc_use_alloca (alloca_used
-					 + air->naddrs * sizeof (struct gaih_addrtuple)))
-		    addrmem = alloca_account (air->naddrs
-					      * sizeof (struct gaih_addrtuple),
-					      alloca_used);
+		  size_t needed = MUL_S (air->naddrs, sizeof (struct gaih_addrtuple));
+
+		  if (__libc_use_alloca (alloca_used + needed))
+		    addrmem = alloca_account (needed, alloca_used);
 		  else
 		    {
-		      addrmem = malloc (air->naddrs
-					* sizeof (struct gaih_addrtuple));
+		      addrmem = malloc (needed);
 		      if (addrmem == NULL)
 			{
 			  result = -EAI_MEMORY;
@@ -2435,7 +2432,7 @@ getaddrinfo (const char *name, const char *service,
       struct addrinfo *last = NULL;
       char *canonname = NULL;
       bool malloc_results;
-      size_t alloc_size = nresults * (sizeof (*results) + sizeof (size_t));
+      size_t alloc_size = MUL_S (nresults, (sizeof (*results) + sizeof (size_t)));
 
       malloc_results
 	= !__libc_use_alloca (alloc_size);
-- 
1.7.10.4