Re: [PR19351, C++] Fix heap overflow in operator new[]

[Florian Weimer <fw at deneb dot enyo dot de>]

I wrote some time ago:

> This proposed change addresses a long-standing issue in the size
> calculations for operator new[].  The size value could be truncated,
> and operator new[] would return too small an array in such cases.
>
> With this change, the size calculations are performed using
> saturating arithmetic.  If the value cannot be represented exactly,
> ::operator new(size_t) is invoked with size_t(-1), usually throwing
> a std::bad_alloc exception.  The advantage of this approach is full
> ABI compatibility (in both directions). The downside is slightly
> worse code (but it's still branch-free on i386 and amd64; support
> for saturating arithmetic would improve things further, of course).

I have since fixed build_size_mult_saturated so that it should work in
more configurations.  The test case has been updated to work around
the do-not-inline-into-main phenomenon.

The patch passes bootstrap and regression testing on
x86_64-unknown-linux-gnu.

Where would I need to put the test case?

2011-01-22  Florian Weimer  <fw@deneb.enyo.de>

	PR c++/19351

	* init.c (build_size_mult_saturated, build_new_size_expr): Add.
	(build_new_1): Use these new functions in size calculations.

	* call.c (build_operator_new_call): Add size_with_cookie argument.
	* cp-tree.h (build_operator_new_call): Likewise.

diff --git a/gcc/cp/call.c b/gcc/cp/call.c
index 7d602b9..299f73c 100644
--- a/gcc/cp/call.c
+++ b/gcc/cp/call.c
@@ -3633,7 +3633,7 @@ build_new_function_call (tree fn, VEC(tree,gc) **args, bool koenig_p,
 
 tree
 build_operator_new_call (tree fnname, VEC(tree,gc) **args,
-			 tree *size, tree *cookie_size,
+			 tree *size, tree size_with_cookie, tree *cookie_size,
 			 tree *fn)
 {
   tree fns;
@@ -3704,7 +3704,7 @@ build_operator_new_call (tree fnname, VEC(tree,gc) **args,
        if (use_cookie)
 	 {
 	   /* Update the total size.  */
-	   *size = size_binop (PLUS_EXPR, *size, *cookie_size);
+	   *size = size_with_cookie;
 	   /* Update the argument list to reflect the adjusted size.  */
 	   VEC_replace (tree, *args, 0, *size);
 	 }
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 7500826..39898f3 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -4613,7 +4613,7 @@ extern tree build_user_type_conversion		(tree, tree, int);
 extern tree build_new_function_call		(tree, VEC(tree,gc) **, bool, 
 						 tsubst_flags_t);
 extern tree build_operator_new_call		(tree, VEC(tree,gc) **, tree *,
-						 tree *, tree *);
+						 tree, tree *, tree *);
 extern tree build_new_method_call		(tree, tree, VEC(tree,gc) **,
 						 tree, int, tree *,
 						 tsubst_flags_t);
diff --git a/gcc/cp/init.c b/gcc/cp/init.c
index 6ffdc2f..28e5401 100644
--- a/gcc/cp/init.c
+++ b/gcc/cp/init.c
@@ -1912,6 +1912,39 @@ diagnose_uninitialized_cst_or_ref_member (tree type, bool using_new, bool compla
   return diagnose_uninitialized_cst_or_ref_member_1 (type, type, using_new, complain);
 }
 
+/* Multiplies MUL1 with MUL2, and adds ADD.  Returns (size_t)-1 if the
+   result cannot be be represented as a size_t value.  If ADD is
+   null_tree, treat it as a zero constant.
+ */
+static tree
+build_size_mult_saturated (tree mul1, tree mul2, tree add)
+{
+  tree max_mul1, result;
+  max_mul1 = TYPE_MAX_VALUE (size_type_node);
+  if (add != NULL_TREE)
+    max_mul1 = build2 (MINUS_EXPR, size_type_node, max_mul1, add);
+  max_mul1 = build2 (TRUNC_DIV_EXPR, size_type_node, max_mul1, mul2);
+  result = size_binop (MULT_EXPR, mul1, mul2);
+  if (add != NULL_TREE)
+    result = size_binop (PLUS_EXPR, result, add);
+  return build3 (COND_EXPR, size_type_node,
+		 build2 (EQ_EXPR, size_type_node, mul2, size_zero_node),
+		 add == NULL_TREE ? size_zero_node : add,
+		 build3 (COND_EXPR, size_type_node,
+			 build2 (LE_EXPR, size_type_node, mul1, max_mul1),
+			 result, TYPE_MAX_VALUE (size_type_node)));
+}
+
+static tree
+build_new_size_expr (tree elt_type, tree nelts, tree cookie_size)
+{
+  tree elt_size = size_in_bytes (elt_type);
+  if (nelts == NULL_TREE)
+    return elt_size;
+  return build_size_mult_saturated
+    (convert (sizetype, nelts), elt_size, cookie_size);
+}
+
 /* Generate code for a new-expression, including calling the "operator
    new" function, initializing the object, and, if an exception occurs
    during construction, cleaning up.  The arguments are as for
@@ -1981,10 +2014,10 @@ build_new_1 (VEC(tree,gc) **placement, tree type, tree nelts,
   for (elt_type = type;
        TREE_CODE (elt_type) == ARRAY_TYPE;
        elt_type = TREE_TYPE (elt_type))
-    nelts = cp_build_binary_op (input_location,
-				MULT_EXPR, nelts,
-				array_type_nelts_top (elt_type),
-				complain);
+    nelts = build_size_mult_saturated
+      (convert (sizetype, nelts),
+       convert (sizetype, array_type_nelts_top (elt_type)),
+       NULL_TREE);
 
   if (TREE_CODE (elt_type) == VOID_TYPE)
     {
@@ -2036,10 +2069,6 @@ build_new_1 (VEC(tree,gc) **placement, tree type, tree nelts,
       return error_mark_node;
     }
 
-  size = size_in_bytes (elt_type);
-  if (array_p)
-    size = size_binop (MULT_EXPR, size, convert (sizetype, nelts));
-
   alloc_fn = NULL_TREE;
 
   /* If PLACEMENT is a single simple pointer type not passed by
@@ -2103,8 +2132,8 @@ build_new_1 (VEC(tree,gc) **placement, tree type, tree nelts,
 	  if (array_p && TYPE_VEC_NEW_USES_COOKIE (elt_type))
 	    {
 	      cookie_size = targetm.cxx.get_cookie_size (elt_type);
-	      size = size_binop (PLUS_EXPR, size, cookie_size);
 	    }
+	  size = build_new_size_expr (elt_type, nelts, cookie_size);
 	  /* Create the argument list.  */
 	  VEC_safe_insert (tree, gc, *placement, 0, size);
 	  /* Do name-lookup to find the appropriate operator.  */
@@ -2135,14 +2164,24 @@ build_new_1 (VEC(tree,gc) **placement, tree type, tree nelts,
 	{
 	  /* Use a global operator new.  */
 	  /* See if a cookie might be required.  */
+	  tree size_with_cookie;
+	  size = build_new_size_expr (elt_type, nelts, NULL_TREE);
 	  if (array_p && TYPE_VEC_NEW_USES_COOKIE (elt_type))
-	    cookie_size = targetm.cxx.get_cookie_size (elt_type);
+	    {
+	      cookie_size = targetm.cxx.get_cookie_size (elt_type);
+	      size_with_cookie = build_new_size_expr
+		(elt_type, nelts, cookie_size);
+	    }
 	  else
-	    cookie_size = NULL_TREE;
+	    {
+	      cookie_size = NULL_TREE;
+	      size_with_cookie = size;
+	    }
 
-	  alloc_call = build_operator_new_call (fnname, placement,
-						&size, &cookie_size,
-						&alloc_fn);
+	  alloc_call = build_operator_new_call
+	    (fnname, placement,
+	     &size, size_with_cookie, &cookie_size,
+	     &alloc_fn);
 	}
     }
 

#include <stdlib.h>
#include <stdexcept>

struct foo {
  char bar[256];
};

inline void
test (size_t s)
{
  try {
    new foo[s];
    abort ();
  } catch (std::bad_alloc &) {
  }
}

static void test_noopt (size_t) __attribute__((noinline));

static void
test_noopt (size_t s)
{
  __asm__ ("");
  test (s);
}

inline void
test2i (size_t s1, size_t s2)
{
  typedef foo array[s2];
  try {
    new array[s1];
    abort ();
  } catch (std::bad_alloc &) {
  }
}

inline void
test2 (size_t s1, size_t s2)
{
  test2i (s1, s2);
  test2i (s2, s1);
}

static void test2_noopt (size_t, size_t) __attribute__((noinline));

static void
test2_noopt (size_t s1, size_t s2)
{
  __asm__ ("");
  test2 (s1, s2);
}

void
all_tests ()
{
  try {
    ::operator new(size_t(-1));
    abort ();
  } catch (std::bad_alloc &) {
  }
  test(-1);
  test(size_t(-1) / sizeof (foo) + 1);
  test(size_t(-1) / sizeof (foo) + 2);
  test_noopt(-1);
  test_noopt(size_t(-1) / sizeof (foo) + 1);
  test_noopt(size_t(-1) / sizeof (foo) + 2);

  test2 (1, -1);
  test2 (1, size_t(-1) / sizeof (foo) + 1);
  test2 (1, size_t(-1) / sizeof (foo) + 2);
  test2_noopt (1, -1);
  test2_noopt (1, size_t(-1) / sizeof (foo) + 1);
  test2_noopt (1, size_t(-1) / sizeof (foo) + 2);

  const unsigned shift = sizeof (size_t) * 8;
  const size_t c1 = 1U;
  test2 (c1 << (shift / 2), c1 << (shift / 2));
  test2_noopt (c1 << (shift / 2), c1 << (shift / 2));
  test2 (c1 << (shift / 2), (c1 << (shift / 2)) + 1);
  test2_noopt (c1 << (shift / 2), (c1 << (shift / 2)) + 1);
  test2 ((c1 << (shift / 2)) / sizeof (foo), (c1 << (shift / 2)) + 1);
  test2_noopt (c1 << (shift / 2) / sizeof (foo), (c1 << (shift / 2)) + 1);
}

int
main ()
{
  all_tests ();
  return 0;
}