std::vector (ab)uses automatic storage

Question

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?

Scapegrace

One should not store huge objects in a array type. Doing so potentially requires a very large region of contigious memory that may not be present. Instead, have a vector of pointers (std::unique_ptr typically) so that you don't place such a high demand on your memory. – Russellrusset

@Russellrusset contiguous virtual memory you mean. – Scapegrace

Just memory. There are C++ implementations running that don't use virtual memory. – Russellrusset

@Russellrusset the are C++ implementations that do not use stack as well :). I mean that in my use-case requesting a few tens of MB (and even more) of cont.memory is ok. – Scapegrace

Which compiler, btw? I can't reproduce with VS 2019 (16.4.2) – Charis

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

@CrisMM I mentioned that it's libstdc++, i.e. GCC. – Scapegrace

@Alcohol right, so passing a custom allocator could probably help. But this looks like a hack... – Scapegrace

If that is indeed the implementation that's used, I daresay it's non-conforming, since it value-assigns (which is what std::fill does) when the standard clearly says "default construct" in the constructor for std::vector. Be sure to check you've 100% certain found the correct code though. Can be tricky to find, and possibly it's something else. – Passing

@Passing 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. – Alcohol

@Passing it's the code you can directly see in the context of the segfault. – Raspy

@walnut: One observable difference would be copying data when no copying is necessary (the implicitly-defined default constructor has an empty initializer list, i.e. it's factually a no-op). Another obvious observable difference is the very crash which comes from creating a temporary when no temporary is to be created. – Passing

@Passing 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. – Alcohol

I'm wondering whether the downvotes are on purpose or just misclicks... :-) – Scapegrace

Answer 1

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.

Nix

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

@Alcohol 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? – Nix

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

@Alcohol 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. – Carabiniere

@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.) – Alcohol

Answer 2

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.

Glavin

"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. – Raspy

Any platform on which this does not crash (assuming the object isn't successfully allocated) is vulnerable to Stack Clash. – Xeroderma

@user253751 It would be optimistic to assume that most platforms / programs aren't vulnerable. – Glavin

I think overcommit only applies to the heap, not the stack. The stack has a fixed upper bound on its size. – Carabiniere

@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. – Glavin

Answer 3

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.

Sleuthhound

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

@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. – Sleuthhound

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

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

@Dichroism No, the both require MoveInsertable only. – Scapegrace

@IgorR. vector::vector(size_type, Allocator const&) requires (Cpp17)DefaultInsertable – Dichroism