[RFC] Approach for C++1y N3639 (runtime-sized arrays with automatic storage duration)

Hi!

C++1y adds support for arrays of runtime bound (ARBs) to the C++ language. These are basically a restricted form of VLA, which can only be used for stack variables, and to which sizeof/decltype/typedef/etc can’t be applied (though we’ll still support those constructs as a GNU extension). See http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3639.html for details.

Under N3639, we are required to throw an exception if the array bound * sizeof(element) calculation overflows, or if the array bound is too small. We’re also permitted to call the global operator new/operator delete to acquire storage for the array, if we so choose. VLA stack usage can be problematic in some circumstances (especially in heavily-threaded code), so this may be something we want to pursue. Therefore I’m proposing the following implementation approach:

  • Add a -farb-stack-limit=N command-line option to control the maximum stack memory which can be used by an ARB. If the ARB doesn’t fit in this limit, we use heap allocation instead. By default, there is no limit.
  • Add a -farb-heap-limit=N command-line option to control the maximum heap memory which can be used by an ARB. If the ARB doesn’t fit in this limit, we call __cxa_throw_bad_array_length. By default, the limit is 0 (never use heap allocation).
  • If the bound is erroneous (too small, multiplication overflows, beyond our limit), we call __cxa_throw_bad_array_length. To support old C++ ABI libraries, we emit a weak form of this in every TU which invokes it, and the weak form calls __builtin_trap().

Does this seem reasonable? Would we want any part of this checking (for instance, the overflow check + trap) in C, or in C+±before-C++14? Maybe the flags should be -fvla-foo instead of -farb-foo?

Thanks,
Richard

Hi!

C++1y adds support for arrays of runtime bound (ARBs) to the C++ language.
These are basically a restricted form of VLA, which can only be used for
stack variables, and to which sizeof/decltype/typedef/etc can't be applied
(though we'll still support those constructs as a GNU extension). See
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3639.html for
details.

Under N3639, we are required to throw an exception if the array bound *
sizeof(element) calculation overflows, or if the array bound is too small.
We're also permitted to call the global operator new/operator delete to
acquire storage for the array, if we so choose. VLA stack usage can be
problematic in some circumstances (especially in heavily-threaded code), so
this may be something we want to pursue. Therefore I'm proposing the
following implementation approach:

* Add a -farb-stack-limit=N command-line option to control the maximum stack
memory which can be used by an ARB. If the ARB doesn't fit in this limit, we
use heap allocation instead. By default, there is no limit.
* Add a -farb-heap-limit=N command-line option to control the maximum heap
memory which can be used by an ARB. If the ARB doesn't fit in this limit, we
call __cxa_throw_bad_array_length. By default, the limit is 0 (never use
heap allocation).

What's the particular motivation for the heap limit option (when other
explicit heap allocation has no such limit (neither at the language
nor library level (things like std::vector, etc))?

Hi!

C++1y adds support for arrays of runtime bound (ARBs) to the C++ language.
These are basically a restricted form of VLA, which can only be used for
stack variables, and to which sizeof/decltype/typedef/etc can't be applied
(though we'll still support those constructs as a GNU extension). See
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3639.html for
details.

Under N3639, we are required to throw an exception if the array bound *
sizeof(element) calculation overflows, or if the array bound is too small.
We're also permitted to call the global operator new/operator delete to
acquire storage for the array, if we so choose. VLA stack usage can be
problematic in some circumstances (especially in heavily-threaded code), so
this may be something we want to pursue. Therefore I'm proposing the
following implementation approach:

* Add a -farb-stack-limit=N command-line option to control the maximum
stack memory which can be used by an ARB. If the ARB doesn't fit in this
limit, we use heap allocation instead. By default, there is no limit.
* Add a -farb-heap-limit=N command-line option to control the maximum heap
memory which can be used by an ARB. If the ARB doesn't fit in this limit,
we call __cxa_throw_bad_array_length. By default, the limit is 0 (never use
heap allocation).
* If the bound is erroneous (too small, multiplication overflows, beyond
our limit), we call __cxa_throw_bad_array_length. To support old C++ ABI
libraries, we emit a weak form of this in every TU which invokes it, and
the weak form calls __builtin_trap().

I really like the ability to automatically defer large allocations to the
heap. I don't have any specific problems with your proposed interface or
semantics, but I would really like to work with the GCC community to get
agreement on the semantics and flag names here (the library routines and
exception names should I suspect be handled via the ABI group). Too often
we've have divergence between the two and had to paper over it with
compatibility layers (-fcolor-diagnostics vs. -fdiagnostics-color ...).

Does this seem reasonable? Would we want any part of this checking (for
instance, the overflow check + trap) in C, or in C++-before-C++14? Maybe
the flags should be -fvla-foo instead of -farb-foo?

I think it would be very useful to allow (as an extension) applying these
semantics to VLAs in other language modes. It would suggest:

1) It be clearly marked as an extension with flags to control it. I'm OK
with default-on, but I suspect the better strategy is to make this opt-in.

2) I think opting into it should get you the *full* semantic model
proposed: the crazy things you can do with VLAs that didn't make it into
C++1y should become errors.

Hi! C++1y adds support for arrays of runtime bound (ARBs)

    > to the C++ language. These are basically a restricted form
    > of VLA,

Very restricted... (Well I am biased, as a great fan of C99 VLA :-),
mainly for automatic parallelization & vectorization issues)

    > * Add a -farb-stack-limit=N command-line option to control
    > the maximum stack memory which can be used by an ARB. If
    > the ARB doesn't fit in this limit, we use heap allocation
    > instead. By default, there is no limit. * Add a
    > -farb-heap-limit=N command-line option to control the
    > maximum heap memory which can be used by an ARB. If the ARB
    > doesn't fit in this limit, we call
    > __cxa_throw_bad_array_length. By default, the limit is 0
    > (never use heap allocation). * If the bound is erroneous
    > (too small, multiplication overflows, beyond our limit), we
    > call __cxa_throw_bad_array_length. To support old C++ ABI
    > libraries, we emit a weak form of this in every TU which
    > invokes it, and the weak form calls __builtin_trap().

    > Does this seem reasonable?

Yes.

    > Would we want any part of this checking (for instance, the
    > overflow check + trap) in C, or in C++-before-C++14? Maybe
    > the flags should be -fvla-foo instead of -farb-foo?

I am curious about what is expected in the case of C checking.
In this case do we test for overflows also in the case of
multiple-dimension VLA too?

How to deal with C function definitions such as:
void foo(int n, int m, float array[n][m]) {

}

where do you put the test for n and m?
It looks to me that if you want to be ABI-compatible, you have to
synthesize a function wrapper and put the tests in it before calling the
real renamed function or something like that...

But even if it is difficult, I think your proposition of providing such
verification for C compilation in Clang is a good idea as it can improve
the code safety for C99.

Thank you,

Hi!

C++1y adds support for arrays of runtime bound (ARBs) to the C++ language.
These are basically a restricted form of VLA, which can only be used for
stack variables, and to which sizeof/decltype/typedef/etc can’t be applied
(though we’ll still support those constructs as a GNU extension). See
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3639.html for
details.

Under N3639, we are required to throw an exception if the array bound *
sizeof(element) calculation overflows, or if the array bound is too small.
We’re also permitted to call the global operator new/operator delete to
acquire storage for the array, if we so choose. VLA stack usage can be
problematic in some circumstances (especially in heavily-threaded code), so
this may be something we want to pursue. Therefore I’m proposing the
following implementation approach:

  • Add a -farb-stack-limit=N command-line option to control the maximum stack
    memory which can be used by an ARB. If the ARB doesn’t fit in this limit, we
    use heap allocation instead. By default, there is no limit.
  • Add a -farb-heap-limit=N command-line option to control the maximum heap
    memory which can be used by an ARB. If the ARB doesn’t fit in this limit, we
    call __cxa_throw_bad_array_length. By default, the limit is 0 (never use
    heap allocation).

What’s the particular motivation for the heap limit option (when other
explicit heap allocation has no such limit (neither at the language
nor library level (things like std::vector, etc))?

Perhaps it would make more sense here to just have a flag to say whether we will ever use heap allocation as a fallback. I can certainly imagine situations where you want a stack limit but never want to fall back to the heap (and equally, a stack limit and a heap fallback seems very useful).

Hi! C++1y adds support for arrays of runtime bound (ARBs)
to the C++ language. These are basically a restricted form
of VLA,

Very restricted… (Well I am biased, as a great fan of C99 VLA :-),
mainly for automatic parallelization & vectorization issues)

  • Add a -farb-stack-limit=N command-line option to control
    the maximum stack memory which can be used by an ARB. If
    the ARB doesn’t fit in this limit, we use heap allocation
    instead. By default, there is no limit. * Add a
    -farb-heap-limit=N command-line option to control the
    maximum heap memory which can be used by an ARB. If the ARB
    doesn’t fit in this limit, we call
    __cxa_throw_bad_array_length. By default, the limit is 0
    (never use heap allocation). * If the bound is erroneous
    (too small, multiplication overflows, beyond our limit), we
    call __cxa_throw_bad_array_length. To support old C++ ABI
    libraries, we emit a weak form of this in every TU which
    invokes it, and the weak form calls __builtin_trap().

Does this seem reasonable?

Yes.

Would we want any part of this checking (for instance, the
overflow check + trap) in C, or in C+±before-C++14? Maybe
the flags should be -fvla-foo instead of -farb-foo?

I am curious about what is expected in the case of C checking.
In this case do we test for overflows also in the case of
multiple-dimension VLA too?

Yes, that seems best.

How to deal with C function definitions such as:
void foo(int n, int m, float array[n][m]) {

}

where do you put the test for n and m?

I don’t think a test is necessary here, because this declaration doesn’t allocate storage. Instead, any relevant test should have been performed when the argument passed as ‘array’ was created. I definitely see value in verifying that the ‘array’ argument can be used to access at least n * m floats, but I think that belongs in a separate check (maybe ASan could be taught to verify this).

I was thinking to this kind of creative programming using the example
above:
{
  float a[100][10];
  foo(-5000, -365, a);
}

But you are right, it is to be tested by some more or less static
analyzers instead, since it is not related to the allocation itself.

Since C99 doesn’t allow initializers for VLAs, if we enable this by default in C99 mode, then (unless people use the -fvla-* / -farb-* arguments) the only behavioral difference will be that they get a trap if the multiplication overflows or the array bound is zero (both of which are UB). Is that significant enough to require opt-in?

As an aside, we accept arrays with a constant zero length as a GNU extension, but in C++14 we’re required to throw an exception if a dynamic array bound is zero. How should we handle that?