44

Consider the following snippet:

#include <array> int main() { using huge_type = std::array<char, 20*1024*1024>; huge_type t; }

Obviously it would crash on most of platforms, because the default stack size is usually less than 20MB.

Now consider the following code:

#include <array> #include <vector> int main() { using huge_type = std::array<char, 20*1024*1024>; std::vector<huge_type> v(1); }

Surprisingly it also crashes! The traceback (with one of the recent libstdc++ versions) leads to include/bits/stl_uninitialized.h file, where we can see the following lines:

typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType; std::fill(__first, __last, _ValueType());

The resizing vector constructor must default-initialize the elements, and this is how it's implemented. Obviously, _ValueType() temporary crashes the stack.

The question is whether it's a conforming implementation. If yes, it actually means that the use of a vector of huge types is quite limited, isn't it?

Improve this question
14
  • 2
    Just memory. There are C++ implementations running that don't use virtual memory. Commented Jan 6, 2020 at 20:36
  • 3
    Which compiler, btw? I can't reproduce with VS 2019 (16.4.2) Commented Jan 6, 2020 at 20:50
  • 3
    From looking at the libstdc++ code, this implementation is only used if the element type is trivial and copy assignable and if the default std::allocator is used. Commented Jan 6, 2020 at 20:54
  • 2
    @Damon As I mentioned above it seems to only be used for trivial types with the default allocator, so there shouldn't be any observable difference. Commented Jan 6, 2020 at 23:52
  • 1
    @Damon The former is not part of the observable behavior of the program and an implementation of the standard may do whatever it wants as long as the observable behavior is the same, see the as-if rule. The latter should be covered by the standard not setting any memory requirements on library calls and by the implementation limit rules, see answers to the question. Commented Jan 7, 2020 at 18:28

3 Answers 3

Reset to default
19

There is no limit on how much automatic storage any std API uses.

They could all require 12 terabytes of stack space.

However, that API only requires Cpp17DefaultInsertable, and your implementation creates an extra instance over what is required by the constructor. Unless it is gated behind detecting the object is trivially ctorable and copyable, that implementation looks illegal.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

From looking at the libstdc++ code, this implementation is only used if the element type is trivial and copy assignable and if the default std::allocator is used. I am not sure why this special case is made in the first place.
@walnut Which means the compiler is free to as-if not actually create that temporary object; I'm guessing there is a decent chance on an optimized build it doesn't get created?
Yes, I guess it could, but for large elements GCC doesn't seem to. Clang with libstdc++ does optimize out the temporary, but it seems only if the vector size passed to the constructor is a compile-time constant, see godbolt.org/z/-2ZDMm.
@walnut the special case is there so that we dispatch to std::fill for trivial types, which then uses memcpy to blast the bytes into places, which is potentially much faster than constructing lots of individual objects in a loop. I believe the libstdc++ implementation is conforming, but causing a stack overflow for huge objects is a Quality of Implementation (QoI) bug. I've reported it as gcc.gnu.org/PR94540 and will fix it.
@JonathanWakely Yes, that makes sense. I don't remember why I didn't think of that when I wrote my comment. I guess I would have thought that the first default-constructed element would be constructed directly in-place and then one could copy from that, so that no additional objects of the element type will ever be constructed. But of course I have not really thought this through in detail and I don't know the in and outs of implementing the standard library. (I realized too late that this is also your suggestion in the bug report.)
9 
huge_type t;

Obviously it would crash on most of platforms ...

I dispute the assumption of "most". Since the memory of the huge object is never used, the compiler can completely ignore it and never allocate the memory in which case there would be no crash.

The question is whether it's a conforming implementation.

The C++ standard doesn't limit stack use, or even acknowledge the existence of a stack. So, yes it conforms to the standard. But one could consider this to be a quality of implementation issue.

it actually means that the use of a vector of huge types is quite limited, isn't it?

That appears to be the case with libstdc++. The crash was not reproduced with libc++ (using clang), so it seems that this is not limitation in the language, but rather only in that particular implementation.

Improve this answer

5 Comments

"won't necessarily crash despite overflowing of stack because the allocated memory is never accessed by the program" — if the stack is used in any way after this (e.g. to call a function), this will crash even on the over-committing platforms.
Any platform on which this does not crash (assuming the object isn't successfully allocated) is vulnerable to Stack Clash.
@user253751 It would be optimistic to assume that most platforms / programs aren't vulnerable.
I think overcommit only applies to the heap, not the stack. The stack has a fixed upper bound on its size.
@JonathanWakely You're right. It appears that the reason why it doesn't crash is because the compiler never allocates the object that is unused.
5

I'm not a language lawyer nor a C++ standard expert, but cppreference.com says:

explicit vector( size_type count, const Allocator& alloc = Allocator() );

Constructs the container with count default-inserted instances of T. No copies are made.

Perhaps I'm misunderstanding "default-inserted," but I would expect:

std::vector<huge_type> v(1);

to be equivalent to

std::vector<huge_type> v; v.emplace_back();

The latter version shouldn't create a stack copy but construct a huge_type directly in the vector's dynamic memory.

I can't authoritatively say that what you're seeing is non-compliant, but it's certainly not what I would expect from a quality implementation.

Improve this answer

6 Comments

As I mentioned in a comment on the question, libstdc++ only uses this implementation for trivial types with copy assignment and std::allocator, so there should be no observable difference between inserting directly into the vectors memory and creating an intermediate copy.
@walnut: Right, but the huge stack allocation and the performance impact of init and copy are still things I wouldn't expect from a high-quality implementation.
Yes, I agree. I think this was an oversight in the implementation. My point was only that it doesn't matter in terms of standard compliance.
IIRC you also need copyability or movability for emplace_back but not for just creating a vector. Which means you can have vector<mutex> v(1) but not vector<mutex> v; v.emplace_back(); For something like huge_type you might still have an allocation and move operation more with the second version. Neither should create temporary objects.
@IgorR. vector::vector(size_type, Allocator const&) requires (Cpp17)DefaultInsertable
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.