This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: [PATCH v1.1] Use saturated arithmetic for overflow detection.
- From: OndÅej BÃlka <neleai at seznam dot cz>
- To: "Joseph S. Myers" <joseph at codesourcery dot com>
- Cc: Paul Eggert <eggert at cs dot ucla dot edu>, libc-alpha at sourceware dot org
- Date: Wed, 30 Oct 2013 19:33:18 +0100
- Subject: Re: [PATCH v1.1] Use saturated arithmetic for overflow detection.
- Authentication-results: sourceware.org; auth=none
- References: <20131030174502 dot GA18107 at domone dot podge> <Pine dot LNX dot 4 dot 64 dot 1310301749400 dot 22878 at digraph dot polyomino dot org dot uk>
On Wed, Oct 30, 2013 at 05:54:06PM +0000, Joseph S. Myers wrote:
> On Wed, 30 Oct 2013, Ondrej Bilka wrote:
>
> > * bits/saturated.h: New file.
>
> The bits/*.h naming convention should only be used for installed headers,
> not internal headers like this one. See bug 14912.
>
fixed
> > +#define MUL_S(___x, ___y)({ \
>
> Missing space between ')' and '('.
>
> > + 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); \
>
> This would divide by 0 if an argument is 0.
>
fixed
> No need for __ in macro paramater names, as each macro has its own
> namespace for parameter names and they can't interfere with any use of
> those names outside the token sequence in the #define directive. So just
> call the parameters x and y. (The variables __x and __y used within the
> macros *do* need the underscores.)
>
What if we later decide to add this as extension and some user gets idea
to #define x y.z ?
> --
> Joseph S. Myers
> joseph@codesourcery.com
Here is new version.
* include/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.
---
include/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 include/saturated.h
diff --git a/include/saturated.h b/include/saturated.h
new file mode 100644
index 0000000..08c5990
--- /dev/null
+++ b/include/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 == 0 ? 1 : __x) ? __x * __y : SIZE_MAX) \
+ : (__x <= SIZE_MAX / (__y == 0 ? 1 : __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 <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 <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 <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 <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 <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 8ff74b4..00f959a 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 <saturated.h>
#ifdef HAVE_LIBIDN
extern int __idna_to_ascii_lz (const char *input, char **output, int flags);
@@ -634,14 +635,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;
@@ -705,15 +704,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;
@@ -2451,7 +2448,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.8.4.rc3