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

login
register
mail settings
Submitter Florian Weimer
Date Jan. 22, 2011, 8:05 p.m.
Message ID <87d3noemb8.fsf@mid.deneb.enyo.de>
Download mbox | patch
Permalink /patch/80013/
State New
Headers show

Comments

Florian Weimer - Jan. 22, 2011, 8:05 p.m.
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.
Florian Weimer - Feb. 1, 2011, 9:40 p.m.
* Florian Weimer:

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

Hi,

could you perhaps review this?

The patch is here:

  <http://gcc.gnu.org/ml/gcc-patches/2011-01/msg01593.html>

Thanks,
Florian
Mark Mitchell - Feb. 5, 2011, 10:20 p.m.
On 2/1/2011 1:40 PM, Florian Weimer wrote:

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

Purely as a point of semantic clarity, instead of talking about
size_t(-1) we should be talking about std::limits<size_t>::max().  It
was confusing to me to think about using a negative value in this context.

This doesn't seem like a good default to me.  It will penalize code that
doesn't need the check and cause GCC to be perceived negatively in
space-constrained environments; we'll generate worse code that competing
compilers.  In general, in C/C++, we don't check for overflow, leaving
that to the application; I don't see a reason that it's inherently more
important to have the compiler generate checking code for new than
elsewhere.

But, it does seem like a useful mode for some applications.  So, it
makes sense to me to add an option for this.

Thank you,
Gabriel Dos Reis - Feb. 6, 2011, 1:20 a.m.
On Sat, Feb 5, 2011 at 4:20 PM, Mark Mitchell <mark@codesourcery.com> wrote:
> On 2/1/2011 1:40 PM, Florian Weimer wrote:
>
>>>> 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)
>
> Purely as a point of semantic clarity, instead of talking about
> size_t(-1) we should be talking about std::limits<size_t>::max().  It
> was confusing to me to think about using a negative value in this context.

It could be argued that '-1' has always been C's way or writing the
max value of an unsigned integer value.

>
> This doesn't seem like a good default to me.  It will penalize code that
> doesn't need the check and cause GCC to be perceived negatively in
> space-constrained environments; we'll generate worse code that competing
> compilers.  In general, in C/C++, we don't check for overflow, leaving

Except that in this specific case, it is a check mandated by the C++ standard
semantics.  I don't believe we are doing the C++ community a service by
pretending that GCC needs to faultly implement the standard because some
competitors fail to do their homework.  On the contrary, I believe this is
an opportunity for GCC to show the way.

If there is a need for GCC to compete with faulty generated code, we can have
a command line switch for that, but it the default should be to implement
the standard semantics.

> that to the application; I don't see a reason that it's inherently more
> important to have the compiler generate checking code for new than
> elsewhere.

because the C++ standard says we should, and not doing it introduces
a security hole.

>
> But, it does seem like a useful mode for some applications.  So, it
> makes sense to me to add an option for this.

We should probably have the command line switch as you suggest,
but the default should generate the check.

>
> Thank you,
>
> --
> Mark Mitchell
> CodeSourcery
> mark@codesourcery.com
> (650) 331-3385 x713
>
Florian Weimer - Feb. 6, 2011, 8:59 a.m.
* Mark Mitchell:

> On 2/1/2011 1:40 PM, Florian Weimer wrote:
>
>>>> 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)
>
> Purely as a point of semantic clarity, instead of talking about
> size_t(-1) we should be talking about std::limits<size_t>::max().
> It was confusing to me to think about using a negative value in this
> context.

Okay, fixed.

> This doesn't seem like a good default to me.  It will penalize code that
> doesn't need the check and cause GCC to be perceived negatively in
> space-constrained environments; we'll generate worse code that competing
> compilers.

Competing compilers have performed the check for several years.

C++0X requires a similar check (see 5.3.4/7 in N3225), but with
different consequences: a new exception should be thrown.  This
requires a new library function to avoid cluttering the call side too
much, so it is not suitable for those of us who need a solution now.

> In general, in C/C++, we don't check for overflow, leaving
> that to the application; I don't see a reason that it's inherently more
> important to have the compiler generate checking code for new than
> elsewhere.

For the application, it is impossible to check for overflow portably
because the cookie size is not accessible to it.

Arguably, it is incorrect to allocate arrays of arbitrary sizes
because memory is limited and performance does not degrade gracefully
when swapping starts.  But such an issue is more benign than code
injection problems as result of memory allocations which are too
small.

> But, it does seem like a useful mode for some applications.  So, it
> makes sense to me to add an option for this.

If this is what it takes, I will implement it.
Richard Guenther - Feb. 6, 2011, 11:17 a.m.
On Sun, Feb 6, 2011 at 9:59 AM, Florian Weimer <fw@deneb.enyo.de> wrote:
> * Mark Mitchell:
>
>> On 2/1/2011 1:40 PM, Florian Weimer wrote:
>>
>>>>> 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)
>>
>> Purely as a point of semantic clarity, instead of talking about
>> size_t(-1) we should be talking about std::limits<size_t>::max().
>> It was confusing to me to think about using a negative value in this
>> context.
>
> Okay, fixed.
>
>> This doesn't seem like a good default to me.  It will penalize code that
>> doesn't need the check and cause GCC to be perceived negatively in
>> space-constrained environments; we'll generate worse code that competing
>> compilers.
>
> Competing compilers have performed the check for several years.
>
> C++0X requires a similar check (see 5.3.4/7 in N3225), but with
> different consequences: a new exception should be thrown.  This
> requires a new library function to avoid cluttering the call side too
> much, so it is not suitable for those of us who need a solution now.
>
>> In general, in C/C++, we don't check for overflow, leaving
>> that to the application; I don't see a reason that it's inherently more
>> important to have the compiler generate checking code for new than
>> elsewhere.
>
> For the application, it is impossible to check for overflow portably
> because the cookie size is not accessible to it.
>
> Arguably, it is incorrect to allocate arrays of arbitrary sizes
> because memory is limited and performance does not degrade gracefully
> when swapping starts.  But such an issue is more benign than code
> injection problems as result of memory allocations which are too
> small.
>
>> But, it does seem like a useful mode for some applications.  So, it
>> makes sense to me to add an option for this.
>
> If this is what it takes, I will implement it.

I think this is also more safe considering that we are in stage4 (and I suppose
you still want to sneak this into 4.6).  Distributors can always choose to
enable the flag by default (as they do with similar flags).

I haven't yet looked at the code this check generates for the middle-end,
but does it consider targets like m32c where addresses are 24bit
but for example sizetype (and size_t?) is 16bit because m32c cannot do
arithmetic in
the larger mode?  I wonder if the code the FE presents us with is 1) correct,
2) results in absymal code on such targets.

Richard.
Joseph S. Myers - Feb. 6, 2011, 7:17 p.m.
On Sun, 6 Feb 2011, Richard Guenther wrote:

> I haven't yet looked at the code this check generates for the middle-end,
> but does it consider targets like m32c where addresses are 24bit
> but for example sizetype (and size_t?) is 16bit because m32c cannot do
> arithmetic in
> the larger mode?  I wonder if the code the FE presents us with is 1) correct,
> 2) results in absymal code on such targets.

The saturation certainly needs to be in type size_t; it's not meaningfully 
possible to have objects larger than that.  (In fact it's not safely 
possible to have objects larger than PTRDIFF_MAX bytes either, which is 
usually the same value as SIZE_MAX >> 1, as subtraction of pointers to 
elements of larger objects may not work reliably.  Thus C malloc should be 
rejecting allocations between PTRDIFF_MAX and SIZE_MAX, even if enough 
memory is available for them.)
Florian Weimer - Feb. 6, 2011, 7:49 p.m.
* Richard Guenther:

> I haven't yet looked at the code this check generates for the
> middle-end, but does it consider targets like m32c where addresses
> are 24bit but for example sizetype (and size_t?) is 16bit because
> m32c cannot do arithmetic in the larger mode?  I wonder if the code
> the FE presents us with is 1) correct, 2) results in absymal code on
> such targets.

I haven't got a full m32c tool-chain, so I could only compile a
minimal example:

struct foo {
  char bar[159];
};

void *
test (unsigned long s)
{
  return new foo[s];
}

This turns into:

__Z4testm:
.LFB0:
        enter   #0
.LCFI0:
        mov.w   5[fb],r0
        cmp.w   #412,r0
        jgtu    .L3
        mov.w   r0,r1
        sha.w   #5,r1
        mov.w   r0,r2
        sha.w   #7,r2
        add.w   r2,r1
        sub.w   r0,r1
        jsr.a   __Znaj
        exitd
.L3:
        mov.w   #-1,r1
        jsr.a   __Znaj
        exitd

412 is the correct magic constant for 16 bits.  (I'm using
size_type_node now, so the generated value should really correspond to
the size_t type.)
Mark Mitchell - Feb. 7, 2011, 6:10 a.m.
On 2/6/2011 3:17 AM, Richard Guenther wrote:

>>> This doesn't seem like a good default to me.  It will penalize code that
>>> doesn't need the check and cause GCC to be perceived negatively in
>>> space-constrained environments; we'll generate worse code that competing
>>> compilers.
>>
>> Competing compilers have performed the check for several years.

Which ones?  And are you looking at compilers used for embedded systems,
or for workstations/servers, or both?

>> For the application, it is impossible to check for overflow portably
>> because the cookie size is not accessible to it.

True.  But, that's splitting hairs; the cookie size is never going to be
more than a small number of bytes.  The application can check for
overflow, leaving 1K for cookie.
Mark Mitchell - Feb. 7, 2011, 6:11 a.m.
On 2/5/2011 5:20 PM, Gabriel Dos Reis wrote:

>> This doesn't seem like a good default to me.  It will penalize code that
>> doesn't need the check and cause GCC to be perceived negatively in
>> space-constrained environments; we'll generate worse code that competing
>> compilers.  In general, in C/C++, we don't check for overflow, leaving
> 
> Except that in this specific case, it is a check mandated by the C++ standard
> semantics. 

Would you please provide a reference to the place where C++98 requires
this check be performed by the compiler and/or run-time?
Florian Weimer - Feb. 7, 2011, 6:27 a.m.
* Mark Mitchell:

> On 2/6/2011 3:17 AM, Richard Guenther wrote:
>
>>>> This doesn't seem like a good default to me.  It will penalize code that
>>>> doesn't need the check and cause GCC to be perceived negatively in
>>>> space-constrained environments; we'll generate worse code that competing
>>>> compilers.
>>>
>>> Competing compilers have performed the check for several years.
>
> Which ones?

Microsoft and HP have announced fixes.  I think Oracle has addressed
it, too, but I would have to check again.

> And are you looking at compilers used for embedded systems,
> or for workstations/servers, or both?

Sorry, no embedded targets here.  (I think comparison with
traditionally broken compilers is not very helpful, BTW.)

Compared to previous GCC versions, the code is not really nice, but
not too bad either (load of a constant, comparison and conditional
branch, plus load of -1 and a jump).  Fortunately, the code generated
for operator new[] is not very compact to start with because the
multiplication happens in the caller.

The case which really, really suffers is allocation of arrays of VLAs,
but this is an accidental GCC extension, rarely used if ever.
Mark Mitchell - Feb. 7, 2011, 6:33 a.m.
On 2/6/2011 10:27 PM, Florian Weimer wrote:

>> And are you looking at compilers used for embedded systems,
>> or for workstations/servers, or both?
> 
> Sorry, no embedded targets here.  (I think comparison with
> traditionally broken compilers is not very helpful, BTW.)

I'm not sure what compilers you consider "traditionally broken".  I'd be
careful about making such statements; certainly, some embedded compilers
have a reputation as good as GCC in many communities.

Perhaps it makes sense to enable this behavior by default on
workstation/server systems.  I'm skeptical that it's a good idea to do
so on embedded systems.  Fortunately, nothing says that we need to have
the same defaults on all systems; it's perfectly reasonable that the
default behavior for a system with gigabytes of RAM is different from
one with kilobytes of flash.

I'm not opposed to having a mode in which we offer the check, but I am
opposed to doing this by default on embedded systems -- except when
conformance with a version of the standard that requires the check is
requested by the user.
Gabriel Dos Reis - Feb. 7, 2011, 10:49 a.m.
On Mon, Feb 7, 2011 at 12:11 AM, Mark Mitchell <mark@codesourcery.com> wrote:
> On 2/5/2011 5:20 PM, Gabriel Dos Reis wrote:
>
>>> This doesn't seem like a good default to me.  It will penalize code that
>>> doesn't need the check and cause GCC to be perceived negatively in
>>> space-constrained environments; we'll generate worse code that competing
>>> compilers.  In general, in C/C++, we don't check for overflow, leaving
>>
>> Except that in this specific case, it is a check mandated by the C++ standard
>> semantics.
>
> Would you please provide a reference to the place where C++98 requires
> this check be performed by the compiler and/or run-time?

It is hard to fathom what your point is.  That fix is OK for anything
other than C++98?

For the reference to C++98: see 5.3.4/10 (and 5.3.4/12 explanatory notes)

-- Gaby
Gabriel Dos Reis - Feb. 7, 2011, 10:54 a.m.
On Mon, Feb 7, 2011 at 12:33 AM, Mark Mitchell <mark@codesourcery.com> wrote:

> I'm not opposed to having a mode in which we offer the check, but I am
> opposed to doing this by default on embedded systems -- except when
> conformance with a version of the standard that requires the check is
> requested by the user.

if embedded systems people believe that they are best served by not
having the check as requested by the standard semantics, well...
Richard Guenther - Feb. 7, 2011, 11 a.m.
On Mon, Feb 7, 2011 at 7:27 AM, Florian Weimer <fw@deneb.enyo.de> wrote:
> * Mark Mitchell:
>
>> On 2/6/2011 3:17 AM, Richard Guenther wrote:
>>
>>>>> This doesn't seem like a good default to me.  It will penalize code that
>>>>> doesn't need the check and cause GCC to be perceived negatively in
>>>>> space-constrained environments; we'll generate worse code that competing
>>>>> compilers.
>>>>
>>>> Competing compilers have performed the check for several years.
>>
>> Which ones?
>
> Microsoft and HP have announced fixes.  I think Oracle has addressed
> it, too, but I would have to check again.
>
>> And are you looking at compilers used for embedded systems,
>> or for workstations/servers, or both?
>
> Sorry, no embedded targets here.  (I think comparison with
> traditionally broken compilers is not very helpful, BTW.)
>
> Compared to previous GCC versions, the code is not really nice, but
> not too bad either (load of a constant, comparison and conditional
> branch, plus load of -1 and a jump).  Fortunately, the code generated
> for operator new[] is not very compact to start with because the
> multiplication happens in the caller.
>
> The case which really, really suffers is allocation of arrays of VLAs,
> but this is an accidental GCC extension, rarely used if ever.

In the m32c assembly it looks like there are two allocation calls,
is this emitted this way from the frontend or just result of optimization?
(that's not ideal for later optimizers nor code-size)

Btw, I'd really like that C++ people would draft a new entry into libsupc++
that defers size calculation to the library.  Eventually using such
entry would even be ABI compatible(?) and can address the C++0x requirement
of raising a different exception.

Richard.
Gabriel Dos Reis - Feb. 7, 2011, 11:20 a.m.
On Mon, Feb 7, 2011 at 5:00 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:

> Btw, I'd really like that C++ people would draft a new entry into libsupc++
> that defers size calculation to the library.

I had long wondered why the C++ standard did  not use an interface a
la calloc().  Oh well.

> Eventually using such
> entry would even be ABI compatible(?) and can address the C++0x requirement
> of raising a different exception.

Note that C++98 also requires a check.  One problem I see is that the standard
requires calling the allocation function (which is a replaceable
function, therefore
user definable) with a very specific semantics constraint on the first argument.
I don't know how you would defer the multiplication and yet remain ABI compliant
when the function is repleacable (and also overloadable at class scope!)

-- Gaby
Richard Guenther - Feb. 7, 2011, 12:54 p.m.
On Mon, Feb 7, 2011 at 12:20 PM, Gabriel Dos Reis
<gdr@integrable-solutions.net> wrote:
> On Mon, Feb 7, 2011 at 5:00 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>
>> Btw, I'd really like that C++ people would draft a new entry into libsupc++
>> that defers size calculation to the library.
>
> I had long wondered why the C++ standard did  not use an interface a
> la calloc().  Oh well.
>
>> Eventually using such
>> entry would even be ABI compatible(?) and can address the C++0x requirement
>> of raising a different exception.
>
> Note that C++98 also requires a check.  One problem I see is that the standard
> requires calling the allocation function (which is a replaceable
> function, therefore
> user definable) with a very specific semantics constraint on the first argument.
> I don't know how you would defer the multiplication and yet remain ABI compliant
> when the function is repleacable (and also overloadable at class scope!)

Can't we simply supply extra arguments to allow both implementations
to co-exist under the same name?  That wouldn't necessarily be a
big overhead (hopefully calling conventions for the old args do not change
when adding new ones on all targets ...).

Richard.

> -- Gaby
>
Mark Mitchell - Feb. 7, 2011, 4:17 p.m.
On 2/7/2011 2:49 AM, Gabriel Dos Reis wrote:

>> Would you please provide a reference to the place where C++98 requires
>> this check be performed by the compiler and/or run-time?
> 
> It is hard to fathom what your point is.  That fix is OK for anything
> other than C++98?

I want to make sure that we don't impose C++0x requirements on C++98
programs.  If, for example, C++0x requires new checks that were not
required by C++98, then it would likely be inappropriate to add them (by
default) for C++98, since that would slow down C++98 applications.

> For the reference to C++98: see 5.3.4/10 (and 5.3.4/12 explanatory notes)

It's hard to be sure that I'm looking at the same thing as you.  Are you
referring to:

"A new-expression passes the amount of space requested to the allocation
function as the first argument of type std::size_t.  The argument shall
be no less than the size of the object being created..."

?

If so, I don't see evidence that this is a requirement on the
implementation per se.  I think this could also be construed as a
requirement on the application.

In any case, I think that what should be done here is to (a) implement
the check, with a command-line option to control it, (b) set the default
to off for all target, and (c) turn it on by default after discussion
with the appropriate target maintainers, taking into account both the
target and the operating system.  For example, it might make sense to
turn this on by default for ARM GNU/Linux, but not for ARM EABI, given
that the latter tends to be a much more space-constrained environment.
Mark Mitchell - Feb. 7, 2011, 4:27 p.m.
On 2/7/2011 3:00 AM, Richard Guenther wrote:

> Btw, I'd really like that C++ people would draft a new entry into libsupc++
> that defers size calculation to the library.  Eventually using such
> entry would even be ABI compatible(?) and can address the C++0x requirement
> of raising a different exception.

This would certainly be desirable, if technically feasible.

Obviously, in the cases where overflow can be detected statically, we
can issue a warning at compile-time and turn the call into a
__builtin_trap.  That seems perfectly acceptable to me in any C++ mode,
and even by default.  So, the case of interest is something where we
don't know how many elements are being allocated or how big the object is.

The __cxa_vec_new functions (required by the C++ ABI, but unused by G++
AFAIK) are designed for this purpose for array allocation; they take an
element size, element count, and cookie size.   So, the check could be
embedded there -- on systems that desire it.  Using these functions
would likely also be a size optimization, since the code generated for
array construction/destruction (including constructor/destructor calls
and exceptions) tends to be quite verbose.  There would, however, be a
performance cost, particularly in the case of constructors that can be
inlined.

The ARM ABI
<http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043c/IHI0043C_rtabi.pdf>
specifies some additional entry points that might be useful as well.

In general, of course, we can extend the ABI without concern, so long as
we include a copy of the new functions we want to add in each shared
object.  So, it's not unreasonable to consider going down that path.
Gabriel Dos Reis - Feb. 7, 2011, 4:36 p.m.
On Mon, Feb 7, 2011 at 6:54 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Mon, Feb 7, 2011 at 12:20 PM, Gabriel Dos Reis
> <gdr@integrable-solutions.net> wrote:
>> On Mon, Feb 7, 2011 at 5:00 AM, Richard Guenther
>> <richard.guenther@gmail.com> wrote:
>>
>>> Btw, I'd really like that C++ people would draft a new entry into libsupc++
>>> that defers size calculation to the library.
>>
>> I had long wondered why the C++ standard did  not use an interface a
>> la calloc().  Oh well.
>>
>>> Eventually using such
>>> entry would even be ABI compatible(?) and can address the C++0x requirement
>>> of raising a different exception.
>>
>> Note that C++98 also requires a check.  One problem I see is that the standard
>> requires calling the allocation function (which is a replaceable
>> function, therefore
>> user definable) with a very specific semantics constraint on the first argument.
>> I don't know how you would defer the multiplication and yet remain ABI compliant
>> when the function is repleacable (and also overloadable at class scope!)
>
> Can't we simply supply extra arguments to allow both implementations
> to co-exist under the same name?  That wouldn't necessarily be a
> big overhead (hopefully calling conventions for the old args do not change
> when adding new ones on all targets ...).

To be sure we are communicating, are we still talking about the allocation
function operator new?
Richard Guenther - Feb. 7, 2011, 4:41 p.m.
On Mon, Feb 7, 2011 at 5:36 PM, Gabriel Dos Reis
<gdr@integrable-solutions.net> wrote:
> On Mon, Feb 7, 2011 at 6:54 AM, Richard Guenther
> <richard.guenther@gmail.com> wrote:
>> On Mon, Feb 7, 2011 at 12:20 PM, Gabriel Dos Reis
>> <gdr@integrable-solutions.net> wrote:
>>> On Mon, Feb 7, 2011 at 5:00 AM, Richard Guenther
>>> <richard.guenther@gmail.com> wrote:
>>>
>>>> Btw, I'd really like that C++ people would draft a new entry into libsupc++
>>>> that defers size calculation to the library.
>>>
>>> I had long wondered why the C++ standard did  not use an interface a
>>> la calloc().  Oh well.
>>>
>>>> Eventually using such
>>>> entry would even be ABI compatible(?) and can address the C++0x requirement
>>>> of raising a different exception.
>>>
>>> Note that C++98 also requires a check.  One problem I see is that the standard
>>> requires calling the allocation function (which is a replaceable
>>> function, therefore
>>> user definable) with a very specific semantics constraint on the first argument.
>>> I don't know how you would defer the multiplication and yet remain ABI compliant
>>> when the function is repleacable (and also overloadable at class scope!)
>>
>> Can't we simply supply extra arguments to allow both implementations
>> to co-exist under the same name?  That wouldn't necessarily be a
>> big overhead (hopefully calling conventions for the old args do not change
>> when adding new ones on all targets ...).
>
> To be sure we are communicating, are we still talking about the allocation
> function operator new?

Yes.  We are talking about ::new.  I propose to call it with excess
arguments

::new (size_t, size_t, size_t)

and provide an implementation (guarded with a proper ABI version) that
uses the excess args to do the required checking.  Any custom
user-provided implementation will continue to work with the first
argument and simply ignore excess args.

What I'm not 100% sure is if we can provide a call / implementation
pair that will allow us to match the excess arg case with the excess
arg implementation with just versioning the symbol and reference properly.

Richard.
Gabriel Dos Reis - Feb. 7, 2011, 4:42 p.m.
On Mon, Feb 7, 2011 at 10:17 AM, Mark Mitchell <mark@codesourcery.com> wrote:
> On 2/7/2011 2:49 AM, Gabriel Dos Reis wrote:
>
>>> Would you please provide a reference to the place where C++98 requires
>>> this check be performed by the compiler and/or run-time?
>>
>> It is hard to fathom what your point is.  That fix is OK for anything
>> other than C++98?
>
> I want to make sure that we don't impose C++0x requirements on C++98
> programs.  If, for example, C++0x requires new checks that were not
> required by C++98, then it would likely be inappropriate to add them (by
> default) for C++98, since that would slow down C++98 applications.

I believe nobody is arguing that C++0x semantics should be imposed
when C++98 is in effect.

However, I do not find your interpretation of C++98 to be accurate.
(As a matter of fact, this bug has already been filled several times
in the C++98 era.)

>
>> For the reference to C++98: see 5.3.4/10 (and 5.3.4/12 explanatory notes)
>
> It's hard to be sure that I'm looking at the same thing as you.  Are you
> referring to:
>
> "A new-expression passes the amount of space requested to the allocation
> function as the first argument of type std::size_t.  The argument shall
> be no less than the size of the object being created..."
>
> ?
>
> If so, I don't see evidence that this is a requirement on the
> implementation per se.

I am a slow man; can you explain in simple steps why that
paragraph is does not constitute a requirement on the implementation?

>  I think this could also be construed as a
> requirement on the application.

I strongly disagree.
The application has no knowledge *how* the compiler
computes the value it passes to the allocation function.
And it is precisely that incertitude that is exploited.  Only
the implementation knows.

>
> In any case, I think that what should be done here is to (a) implement
> the check, with a command-line option to control it, (b) set the default
> to off for all target, and (c) turn it on by default after discussion
> with the appropriate target maintainers, taking into account both the
> target and the operating system.  For example, it might make sense to
> turn this on by default for ARM GNU/Linux, but not for ARM EABI, given
> that the latter tends to be a much more space-constrained environment.
>
> --
> Mark Mitchell
> CodeSourcery
> mark@codesourcery.com
> (650) 331-3385 x713
>
Gabriel Dos Reis - Feb. 7, 2011, 4:45 p.m.
On Mon, Feb 7, 2011 at 10:41 AM, Richard Guenther
<richard.guenther@gmail.com> wrote:
> On Mon, Feb 7, 2011 at 5:36 PM, Gabriel Dos Reis
> <gdr@integrable-solutions.net> wrote:
>> On Mon, Feb 7, 2011 at 6:54 AM, Richard Guenther
>> <richard.guenther@gmail.com> wrote:
>>> On Mon, Feb 7, 2011 at 12:20 PM, Gabriel Dos Reis
>>> <gdr@integrable-solutions.net> wrote:
>>>> On Mon, Feb 7, 2011 at 5:00 AM, Richard Guenther
>>>> <richard.guenther@gmail.com> wrote:
>>>>
>>>>> Btw, I'd really like that C++ people would draft a new entry into libsupc++
>>>>> that defers size calculation to the library.
>>>>
>>>> I had long wondered why the C++ standard did  not use an interface a
>>>> la calloc().  Oh well.
>>>>
>>>>> Eventually using such
>>>>> entry would even be ABI compatible(?) and can address the C++0x requirement
>>>>> of raising a different exception.
>>>>
>>>> Note that C++98 also requires a check.  One problem I see is that the standard
>>>> requires calling the allocation function (which is a replaceable
>>>> function, therefore
>>>> user definable) with a very specific semantics constraint on the first argument.
>>>> I don't know how you would defer the multiplication and yet remain ABI compliant
>>>> when the function is repleacable (and also overloadable at class scope!)
>>>
>>> Can't we simply supply extra arguments to allow both implementations
>>> to co-exist under the same name?  That wouldn't necessarily be a
>>> big overhead (hopefully calling conventions for the old args do not change
>>> when adding new ones on all targets ...).
>>
>> To be sure we are communicating, are we still talking about the allocation
>> function operator new?
>
> Yes.  We are talking about ::new.  I propose to call it with excess
> arguments
>
> ::new (size_t, size_t, size_t)

that will be overload, therefore not call the replaceable function -- which
is what needs to be fixed.  Furthermore, it is not clear that an implementation
can add overloads other than what the standard specifies.

>
> and provide an implementation (guarded with a proper ABI version) that
> uses the excess args to do the required checking.  Any custom
> user-provided implementation will continue to work with the first
> argument and simply ignore excess args.

I don't see how this is both conforming and fixes the root problem.

>
> What I'm not 100% sure is if we can provide a call / implementation
> pair that will allow us to match the excess arg case with the excess
> arg implementation with just versioning the symbol and reference properly.
Mark Mitchell - Feb. 7, 2011, 4:51 p.m.
On 2/7/2011 8:42 AM, Gabriel Dos Reis wrote:

>> "A new-expression passes the amount of space requested to the allocation
>> function as the first argument of type std::size_t.  The argument shall
>> be no less than the size of the object being created..."

> I am a slow man; can you explain in simple steps why that
> paragraph is does not constitute a requirement on the implementation?

It does not say that the implementation must raise an exception, call
abort, or take any other such action.  Normally, when the standard is
imposing a run-time requirement on the implementation, it specifies some
action that the implementation must take.

I'm not sure, though, that the outcome of any language lawyering is
relevant here.  I think that my recommendation:

>> In any case, I think that what should be done here is to (a) implement
>> the check, with a command-line option to control it, (b) set the default
>> to off for all target, and (c) turn it on by default after discussion
>> with the appropriate target maintainers, taking into account both the
>> target and the operating system.  For example, it might make sense to
>> turn this on by default for ARM GNU/Linux, but not for ARM EABI, given
>> that the latter tends to be a much more space-constrained environment.

is sound, independent of how we read the standard.  Even if the standard
does specify a check, there are certainly people who will not want the
check, just as there are people who do want to have exceptions.  And
taking a conservative approach in terms of enabling this behavior by
default is reasonable -- especially given that the approach I've
suggested provides a clear path for enabling this option by default on
(say) x86 GNU/Linux, or other server/workstation platforms where people
are more likely to find this tradeoff desirable.
Chris Lattner - Feb. 7, 2011, 4:51 p.m.
On Feb 6, 2011, at 10:33 PM, Mark Mitchell wrote:

> On 2/6/2011 10:27 PM, Florian Weimer wrote:
> 
>>> And are you looking at compilers used for embedded systems,
>>> or for workstations/servers, or both?
>> 
>> Sorry, no embedded targets here.  (I think comparison with
>> traditionally broken compilers is not very helpful, BTW.)
> 
> I'm not sure what compilers you consider "traditionally broken".  I'd be
> careful about making such statements; certainly, some embedded compilers
> have a reputation as good as GCC in many communities.
> 
> Perhaps it makes sense to enable this behavior by default on
> workstation/server systems.  I'm skeptical that it's a good idea to do
> so on embedded systems.  Fortunately, nothing says that we need to have
> the same defaults on all systems; it's perfectly reasonable that the
> default behavior for a system with gigabytes of RAM is different from
> one with kilobytes of flash.

FWIW, this is enabled in Clang when targeting embedded systems like ARM (with no way to turn it off).  It turns out that these usually have efficient ways to detect overflow, so the cost is very low.  A few bytes for variable-sized array operator new's hasn't been a problem.

I agree with the general sentiment that not catching this is a disservice to users of the compiler, and am skeptical that there is much code doing C++ array operator new that fits into 1K of flash.

Just MHO,

-Chris
Gabriel Dos Reis - Feb. 7, 2011, 5:05 p.m.
On Mon, Feb 7, 2011 at 10:51 AM, Mark Mitchell <mark@codesourcery.com> wrote:
> On 2/7/2011 8:42 AM, Gabriel Dos Reis wrote:
>
>>> "A new-expression passes the amount of space requested to the allocation
>>> function as the first argument of type std::size_t.  The argument shall
>>> be no less than the size of the object being created..."
>
>> I am a slow man; can you explain in simple steps why that
>> paragraph is does not constitute a requirement on the implementation?
>
> It does not say that the implementation must raise an exception, call
> abort, or take any other such action.  Normally, when the standard is
> imposing a run-time requirement on the implementation, it specifies some
> action that the implementation must take.

The standard says that a value will defined property shall be passed,
and the determination of that value is the responsability of the implementation.
Whether an exception is raised depends on whether implementation is
able to allocate as much space.  I'm surprised you believe there is any
doubt about whose job it is to compute that value.

>
> I'm not sure, though, that the outcome of any language lawyering is
> relevant here.  I think that my recommendation:
>
>>> In any case, I think that what should be done here is to (a) implement
>>> the check, with a command-line option to control it, (b) set the default
>>> to off for all target, and (c) turn it on by default after discussion
>>> with the appropriate target maintainers, taking into account both the
>>> target and the operating system.  For example, it might make sense to
>>> turn this on by default for ARM GNU/Linux, but not for ARM EABI, given
>>> that the latter tends to be a much more space-constrained environment.
>
> is sound, independent of how we read the standard.  Even if the standard
> does specify a check, there are certainly people who will not want the
> check, just as there are people who do want to have exceptions.  And
> taking a conservative approach in terms of enabling this behavior by
> default is reasonable -- especially given that the approach I've
> suggested provides a clear path for enabling this option by default on
> (say) x86 GNU/Linux, or other server/workstation platforms where people
> are more likely to find this tradeoff desirable.

As I said earlier, I have no trouble with people wanting to control this aspect.
However,  I think we should enable it by default and let it be overriden by
specialized targets.
Mark Mitchell - Feb. 7, 2011, 5:12 p.m.
On 2/7/2011 9:05 AM, Gabriel Dos Reis wrote:

>> It does not say that the implementation must raise an exception, call
>> abort, or take any other such action.  Normally, when the standard is
>> imposing a run-time requirement on the implementation, it specifies some
>> action that the implementation must take.

> The standard says that a value will defined property shall be passed,
> and the determination of that value is the responsability of the implementation.
> Whether an exception is raised depends on whether implementation is
> able to allocate as much space.  I'm surprised you believe there is any
> doubt about whose job it is to compute that value.

I see little value in continuing this discussion.  It doesn't seem
relevant to determining what behavior we implement.

> As I said earlier, I have no trouble with people wanting to control this aspect.
> However,  I think we should enable it by default and let it be overriden by
> specialized targets.

Sorry, but I am not at all persuaded.  You'll want to get the other two
C++ maintainers to agree with you.

I am extremely sensitive to the fact that a significant fraction of the
GCC userbase feels that we have not been appropriately conservative in
introducing incompatibilities, including increases in code size.  The
conservative approach here is to disable by default, and enable on a
target-by-target basis, not the reverse.  Please take the conservative
approach.
Gabriel Dos Reis - Feb. 7, 2011, 5:19 p.m.
On Mon, Feb 7, 2011 at 11:12 AM, Mark Mitchell <mark@codesourcery.com> wrote:
> On 2/7/2011 9:05 AM, Gabriel Dos Reis wrote:
>
>>> It does not say that the implementation must raise an exception, call
>>> abort, or take any other such action.  Normally, when the standard is
>>> imposing a run-time requirement on the implementation, it specifies some
>>> action that the implementation must take.
>
>> The standard says that a value will defined property shall be passed,
>> and the determination of that value is the responsability of the implementation.
>> Whether an exception is raised depends on whether implementation is
>> able to allocate as much space.  I'm surprised you believe there is any
>> doubt about whose job it is to compute that value.
>
> I see little value in continuing this discussion.  It doesn't seem
> relevant to determining what behavior we implement.

indeed -- I agree that the interpretation that would somehow make it appear
as if the requirement is on the application as opposed to the implementation
is a little value.

>
>> As I said earlier, I have no trouble with people wanting to control this aspect.
>> However,  I think we should enable it by default and let it be overriden by
>> specialized targets.
>
> Sorry, but I am not at all persuaded.  You'll want to get the other two
> C++ maintainers to agree with you.
>
> I am extremely sensitive to the fact that a significant fraction of the
> GCC userbase feels that we have not been appropriately conservative in
> introducing incompatibilities, including increases in code size.  The
> conservative approach here is to disable by default, and enable on a
> target-by-target basis, not the reverse.  Please take the conservative
> approach.

How is it conservative to enable a compiler bug by default and let it be
a known vector for security hole?

It would appear that the conservative approach is for those targets who have
determined that they can leave with the security hole to turn off the mandated
check.  The compiler behaviour is still controlled.
Jakub Jelinek - Feb. 7, 2011, 5:34 p.m.
On Mon, Feb 07, 2011 at 11:19:51AM -0600, Gabriel Dos Reis wrote:
> > I am extremely sensitive to the fact that a significant fraction of the
> > GCC userbase feels that we have not been appropriately conservative in
> > introducing incompatibilities, including increases in code size.  The
> > conservative approach here is to disable by default, and enable on a
> > target-by-target basis, not the reverse.  Please take the conservative
> > approach.
> 
> How is it conservative to enable a compiler bug by default and let it be
> a known vector for security hole?
> 
> It would appear that the conservative approach is for those targets who have
> determined that they can leave with the security hole to turn off the mandated
> check.  The compiler behaviour is still controlled.

I agree with Gaby here.  If we choose to put it into 4.6, the default
could be still off so that we can work on improving the generated code for
the checks, but for 4.7+ IMHO the default should be on.  The checks are
only needed if the number of elements is not constant, but then not checking
it is a security issue and a bug (returning successfully an array that is
not large enough as it should is not a correct implementation).
At least in glibc, calloc is checking for similar overflows for many years,
and I'm not aware of anyone who would complain about the extra few ticks
spent on it.  In calloc the check is
  /* size_t is unsigned so the behavior on overflow is defined.  */
  bytes = n * elem_size;
#define HALF_INTERNAL_SIZE_T \
  (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
  if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0)) {
    if (elem_size != 0 && bytes / elem_size != n) {
      MALLOC_FAILURE_ACTION;
      return 0;
    }
  }
so in most cases it is just a bit or, comparison with a constant and
untaken conditional jump.  For array new when the elem_size is known
this can be, at least on many targets, even cheaper.

	Jakub
Mark Mitchell - Feb. 7, 2011, 5:36 p.m.
On 2/7/2011 9:19 AM, Gabriel Dos Reis wrote:

> How is it conservative to enable a compiler bug by default and let it be
> a known vector for security hole?

On many systems it's not a security hole -- because there is no concept
of security in the sense of a "kernel" vs. "userspace", or, even
"security" at all.

I realize you think it's a compiler bug, but even if it is, it's
certainly not a bug in the sense that calling the wrong virtual function
would be a bug, or in the sense that computing "2 + 2" and getting "5"
would be a bug.

When an application programmer compiles with a new version of GCC and
sees that their application has gotten bigger, there natural tendency is
to believe that reflects something wrong with the compiler.  If their
application is such that there was no risk of overflow before (either
because the inputs were chosen such that this is impossible, or because
they explicitly checked for overflow in their own code), then we have
introduced a cost, with no benefit to them.

I have already told you how to get the outcome you desire: convince
Nathan and Jason.  Please take it up with them; there is no benefit to
you in arguing about it with me at this point.
Benjamin Smedberg - Feb. 7, 2011, 5:42 p.m.
On 2/7/2011 12:12 PM, Mark Mitchell wrote:
>
> Sorry, but I am not at all persuaded.  You'll want to get the other two
> C++ maintainers to agree with you.
>
> I am extremely sensitive to the fact that a significant fraction of the
> GCC userbase feels that we have not been appropriately conservative in
> introducing incompatibilities, including increases in code size.  The
> conservative approach here is to disable by default, and enable on a
> target-by-target basis, not the reverse.  Please take the conservative
> approach.
At Mozilla we have been equally horrified by the GCC attitude that 
latent security bugs, probable critical security issues, are being 
treated as an optional fix. We believe that it is likely that most 
applications which are processing untrusted content could be induced to 
overwrite array bounds pretty easily via overflow.

I'm not sure how the target architecture or typical memory size is 
really relevant: assuming any overflow can happen, the application 
receives an incorrectly-small value which *can* be allocated, even on a 
1k-flash device. The application then proceeds to write on stomped 
memory. If anything, the bug is much more serious on small devices where 
the search space for an exploit is much lower than on a desktop machine.

I can understand that if you never process untrusted content or can 
somehow prove in your application code that array lengths are 
known-bounded before you hit ::operator new, that a 
-fdisable-new-overflow-check flag might make sense. But that is a very 
hard proof to make, and "conservatively" trading incorrectness for 
performance by default would be an unfortunate decision. In any case, 
Mozilla urgently wishes a version of GCC, no matter what the default is, 
which we can use to compile Firefox without potential vulnerabilities. A 
patch which doesn't involve ABI changes and can therefore be potentially 
backported to stable branches is important if it can be achieved as well.

--BDS
Florian Weimer - Feb. 7, 2011, 6:40 p.m.
* Richard Guenther:

> In the m32c assembly it looks like there are two allocation calls,
> is this emitted this way from the frontend or just result of optimization?

The front end emits a library call with a single COND_EXPR as its
argument.   The GIMPLE dump looks like this:

void* test(long unsigned int) (long unsigned int s)
{
  void * D.1699;
  unsigned int iftmp.0;
  unsigned int iftmp.1;
  unsigned int D.1705;
  unsigned int D.1706;

  if (159 == 0) goto <D.1701>; else goto <D.1702>;
  <D.1701>:
  iftmp.0 = 0;
  goto <D.1703>;
  <D.1702>:
  D.1705 = (unsigned int) s;
  D.1706 = 65535 / 159;
  if (D.1705 <= D.1706) goto <D.1707>; else goto <D.1708>;
  <D.1707>:
  iftmp.1 = D.1705 * 159;
  goto <D.1709>;
  <D.1708>:
  iftmp.1 = 65535;
  <D.1709>:
  iftmp.0 = iftmp.1;
  <D.1703>:
  D.1699 = operator new [] (iftmp.0);
  return D.1699;
}

tree-original was:

<<cleanup_point return <retval> = (void *) (struct foo *) operator new [] (159 == 0 ? 0 : SAVE_EXPR <(unsigned int) s> <= 65535 / 159 ? SAVE_EXPR <(unsigned int) s> * 159 : 65535)>>;

> (that's not ideal for later optimizers nor code-size)
>
> Btw, I'd really like that C++ people would draft a new entry into libsupc++
> that defers size calculation to the library.

Could we emit the function in a link-once section, like it is done for
the i386 get-the-program-counter functions?

> Eventually using such entry would even be ABI compatible(?)

It's not, at least by Debian's standards.

> and can address the C++0x requirement of raising a different
> exception.

Except for the VLA case.  Perhaps we can get rid of that in time.
Joseph S. Myers - Feb. 7, 2011, 6:47 p.m.
On Mon, 7 Feb 2011, Benjamin Smedberg wrote:

> On 2/7/2011 12:12 PM, Mark Mitchell wrote:
> > 
> > Sorry, but I am not at all persuaded.  You'll want to get the other two
> > C++ maintainers to agree with you.
> > 
> > I am extremely sensitive to the fact that a significant fraction of the
> > GCC userbase feels that we have not been appropriately conservative in
> > introducing incompatibilities, including increases in code size.  The
> > conservative approach here is to disable by default, and enable on a
> > target-by-target basis, not the reverse.  Please take the conservative
> > approach.
> At Mozilla we have been equally horrified by the GCC attitude that latent
> security bugs, probable critical security issues, are being treated as an
> optional fix. We believe that it is likely that most applications which are
> processing untrusted content could be induced to overwrite array bounds pretty
> easily via overflow.

I also think it's quite clear that we should aim to enable this check by 
default - even if it's disabled by default in 4.6 pending work in 4.7 to 
implement more efficient checks (via defining GENERIC and GIMPLE codes for 
saturating arithmetic on normal integer types rather than just on 
fixed-point types, passing them down to appropriate RTL where the target 
has the right patterns or lowering in GIMPLE where it doesn't, and adding 
appropriate patterns to the .md files (the RTL for which already exists) 
for saturated operations - using checks of overflow flags where that's the 
appropriate implementation).  We know that there are uses of better 
saturating arithmetic support beyond just this case.

(A similar example might be the snprintf function, where in ISO C it's 
formally undefined behavior if it has the return the number of characters 
that would be written to a large-enough array, but that value is more than 
INT_MAX so cannot be represented in the function's return type.  As with 
operator new, this is a case where it is much more reasonably possible for 
the implementation to check for overflow than for the application - and 
the right behavior is clearly what POSIX adds to the ISO C specification, 
that the function shall fail with EOVERFLOW if the return value could not 
be represented.)

I think however your statement about "most applications" will still be 
true even with this fix - simply because it is hard to avoid integer 
overflow issues in C and C++ and requires constant discipline to consider 
and check for overflow throughout the code, whenever arithmetic is done 
(say you do a calculation a*b+c for the number of array elements, before 
passing it to operator new) or values are converted from one integer type 
to another.  If -ftrapv worked it might help for signed arithmetic, but 
many problems relate to conversions or unsigned arithmetic.
Florian Weimer - Feb. 7, 2011, 8:19 p.m.
* Mark Mitchell:

> Perhaps it makes sense to enable this behavior by default on
> workstation/server systems.  I'm skeptical that it's a good idea to do
> so on embedded systems.  Fortunately, nothing says that we need to have
> the same defaults on all systems; it's perfectly reasonable that the
> default behavior for a system with gigabytes of RAM is different from
> one with kilobytes of flash.

Is ARM an embedded target or not? 8-)

It's difficult to judge the impact of the change.  The obvious
embedded C++ code base I could think of---eCos---does not contain any
operator new[] invocations at all.  Even large non-embedded projects
such as Qt use this language feature in a limited fashion only.

(I hope I'll have the patch with the option ready soon, perhaps
tomorrow.)
Florian Weimer - Feb. 7, 2011, 9:27 p.m.
* Florian Weimer:

>>>> Competing compilers have performed the check for several years.
>>
>> Which ones?
>
> Microsoft and HP have announced fixes.  I think Oracle has addressed
> it, too, but I would have to check again.

It turns out that this was overly optimistic.  Oracle Solaris Studio
12.2 does not emit overflow checks.  Neither do Intel's compiler
(version 11), nor Open64.
Mark Mitchell - Feb. 8, 2011, 3:13 a.m.
On 2/7/2011 12:19 PM, Florian Weimer wrote:

>> Perhaps it makes sense to enable this behavior by default on 
>> workstation/server systems.  I'm skeptical that it's a good idea to
>> do so on embedded systems.  Fortunately, nothing says that we need
>> to have the same defaults on all systems; it's perfectly reasonable
>> that the default behavior for a system with gigabytes of RAM is
>> different from one with kilobytes of flash.
> 
> Is ARM an embedded target or not? 8-)

Yes. :-)

A Cortex-M0 device is deeply embedded; it might have just a few
kilobytes of memory.  (And, yes, people do use C++ there.)  A Cortex-A15
is a workstation of yesteryear; it might have gigabytes of flash.

The Cortex-M0 is probably not processing untrusted input; it might be,
for example, a thermostat.  There's no notion of "security" here, but
individual bytes matter a lot.  The Cortex-A15 might be in a tablet
computer, and doing these kinds of checks may well make a lot of sense.
Richard Guenther - Feb. 8, 2011, 11:17 a.m.
On Mon, Feb 7, 2011 at 7:40 PM, Florian Weimer <fw@deneb.enyo.de> wrote:
> * Richard Guenther:
>
>> In the m32c assembly it looks like there are two allocation calls,
>> is this emitted this way from the frontend or just result of optimization?
>
> The front end emits a library call with a single COND_EXPR as its
> argument.   The GIMPLE dump looks like this:
>
> void* test(long unsigned int) (long unsigned int s)
> {
>  void * D.1699;
>  unsigned int iftmp.0;
>  unsigned int iftmp.1;
>  unsigned int D.1705;
>  unsigned int D.1706;
>
>  if (159 == 0) goto <D.1701>; else goto <D.1702>;
>  <D.1701>:
>  iftmp.0 = 0;
>  goto <D.1703>;
>  <D.1702>:
>  D.1705 = (unsigned int) s;
>  D.1706 = 65535 / 159;
>  if (D.1705 <= D.1706) goto <D.1707>; else goto <D.1708>;
>  <D.1707>:
>  iftmp.1 = D.1705 * 159;
>  goto <D.1709>;
>  <D.1708>:
>  iftmp.1 = 65535;
>  <D.1709>:
>  iftmp.0 = iftmp.1;
>  <D.1703>:
>  D.1699 = operator new [] (iftmp.0);
>  return D.1699;
> }
>
> tree-original was:
>
> <<cleanup_point return <retval> = (void *) (struct foo *) operator new [] (159 == 0 ? 0 : SAVE_EXPR <(unsigned int) s> <= 65535 / 159 ? SAVE_EXPR <(unsigned int) s> * 159 : 65535)>>;

That looks fine (though eventually the FE should fold the comparison
and the COND_EXPR it creates - the 159 == 0 check shouldn't prevail,
even at -O0).

Richard.

>> (that's not ideal for later optimizers nor code-size)
>>
>> Btw, I'd really like that C++ people would draft a new entry into libsupc++
>> that defers size calculation to the library.
>
> Could we emit the function in a link-once section, like it is done for
> the i386 get-the-program-counter functions?
>
>> Eventually using such entry would even be ABI compatible(?)
>
> It's not, at least by Debian's standards.
>
>> and can address the C++0x requirement of raising a different
>> exception.
>
> Except for the VLA case.  Perhaps we can get rid of that in time.
>
Florian Weimer - Feb. 8, 2011, 8:29 p.m.
* Richard Guenther:

>> <<cleanup_point return <retval> = (void *) (struct foo *) operator new [] (159 == 0 ? 0 : SAVE_EXPR <(unsigned int) s> <= 65535 / 159 ? SAVE_EXPR <(unsigned int) s> * 159 : 65535)>>;
>
> That looks fine (though eventually the FE should fold the comparison
> and the COND_EXPR it creates - the 159 == 0 check shouldn't prevail,
> even at -O0).

Thanks for the suggestion.

Should I try to remove the 159 == 0 check only, or the constant
division as well?  Is it allowed to call a fold function at this
point, or do I have to do this manually?
Richard Guenther - Feb. 9, 2011, 9:53 a.m.
On Tue, Feb 8, 2011 at 9:29 PM, Florian Weimer <fw@deneb.enyo.de> wrote:
> * Richard Guenther:
>
>>> <<cleanup_point return <retval> = (void *) (struct foo *) operator new [] (159 == 0 ? 0 : SAVE_EXPR <(unsigned int) s> <= 65535 / 159 ? SAVE_EXPR <(unsigned int) s> * 159 : 65535)>>;
>>
>> That looks fine (though eventually the FE should fold the comparison
>> and the COND_EXPR it creates - the 159 == 0 check shouldn't prevail,
>> even at -O0).
>
> Thanks for the suggestion.
>
> Should I try to remove the 159 == 0 check only, or the constant
> division as well?  Is it allowed to call a fold function at this
> point, or do I have to do this manually?

Calling fold should be ok, but it's really a question for the C++
frontend people.

Richard.

Patch

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);
 	}
     }