When a class dynamically allocates itself at constructor, why does stack overflow happen instead of std::bad_alloc?

Question

I made a class that recursively creates itself using new (just for fun!), expecting that this will throw std::bad_alloc due to infinite dynamic allocation (heap overflow). But stack overflow happened instead of std::bad_alloc. Why does this happen?

class Overflow
{
private:
    Overflow* overflow;

public:
    Overflow()
    {
        overflow = new Overflow();
    }
};

int main()
{
    Overflow overflow_happens; // stack overflow happens instead of std::bad_alloc exeption
}

@Caleth asked what happens if I change new Overflow() to new Overflow[100000], and this gave me std::bad_alloc. According to the answers, shouldn't this also give me stack overflow?

It's important to realize that `new Overflow();` causes `Overflow::Overflow()` to be called. — François Andrieux, Jun 11 '19 at 14:01
Because you don't do a bad allocation you just run out of stack memory because of the recursive constructor calls. — Timo, Jun 11 '19 at 14:01
That is implementation dependent race condition. Like if you take poison and also get shot there's a high chance you'll die but whether from poisoning or bleeding is a race condition. — Tanveer Badar, Jun 11 '19 at 14:03
@TanveerBadar While there is a "race" between running out of stack space and heap space, the term race condition has a [strict definition](https://en.cppreference.com/w/cpp/language/memory_model#Threads_and_data_races) in c++. So it's not accurate to say there is a race condition. — François Andrieux, Jun 11 '19 at 14:11
I wonder whether any heap gets allocated at all since none of the constructor calls actually return — Avin Kavish, Jun 11 '19 at 14:13
If he uses `-O3` when building maybe the compiler will optimize the tail recursion? — Not a real meerkat, Jun 11 '19 at 14:14
@AvinKavish I can't imagine the constructor running *before* it's instance had memory allocated to it. Where would the members be stored? In the constructor `this` has to point to an object and that object needs storage. — François Andrieux, Jun 11 '19 at 14:14
Yeah that makes no sense. @CássioRenan how could this be optimised for tail calls when it's just infinitely recursive with no parameters? — Avin Kavish, Jun 11 '19 at 14:17
What happens if you `overflow = new Overflow[1000]`? or 1000000, or 1000000000? — Caleth, Jun 11 '19 at 15:09
@Caleth `overflow = new Overflow[1000000]` gave me `std::bad_alloc`, but new Overflow[1000] still results in stack overflow. — ownfos, Jun 12 '19 at 08:39
@AvinKavish BTW, a [function returning or having parameters is not a prerequisite for tail call optimization](https://godbolt.org/z/0eToNT). — Not a real meerkat, Jun 13 '19 at 14:33
@CássioRenan thanks, I just assumed that to be the case since useful recursion usually involves passing a parameter, I see now that methods with only side-effects can also be optimised too, even more so easily than ones with parameters. — Avin Kavish, Jun 13 '19 at 16:17

score 18 · Answer 1 · answered Jun 11 '19 at 14:02

18

The stack overflow is happening because you have infinite recursion. Calling Overflow() causes you to call Overflow() again and again and again. Those function calls need to go on the stack. Since your stack is smaller than your heap you'll run out of stack space for all of the those constructor calls before you run out of memory for all of the objects you are creating.

answered Jun 11 '19 at 14:02

NathanOliver

171,901
28
288
402

1

your reasoning is not 100% accurate, It actually depends on the size of `Overflow`. If you just add enough members to `Overflow` the `bad_alloc` will appear first, even if stack space is much more limited than heap. Dont get me wrong, your answer is correct for the example in the question and my critizism was just born out of high level nitpicking on the other answer – 463035818_is_not_an_ai Jun 13 '19 at 16:43

score 4 · Answer 2 · answered Jun 11 '19 at 14:02

4

Because you are recursively calling the constructor, a method, repeatedly. The method calls get pushed to the call stack. Since the stack size is much smaller than the available heap, the call stack overflows before the heap runs out.

answered Jun 11 '19 at 14:02

Avin Kavish

8,317
1
21
36

2

I like the answer, though I think this is not quite accurate: "Since the stack size is much smaller than the available heap...." because calling the constructor once does not require the same amount of heap as it requires stack, – 463035818_is_not_an_ai Jun 11 '19 at 14:07
@formerlyknownas_463035818 What is the point that you are trying to make, I don't understand? The accepted answer uses the same exact words, how have you not found issue with it? – Avin Kavish Jun 13 '19 at 14:50
your conclusion would be 100% accurate if the used stack space would be the same as the used heap space, but that is not quite correct. For each recursion there is a `overflow` on the stack which is a pointer (and probably a bit more, but the details are beyond my understanding ;), while on the heap there is a whole `Overflow` object (whose size can be more than just the size of the member). Maybe in this case they are even exactly the same, but in general not (eg if `Overflow` had other big members then more heap would be needed than stack, probably still resulting in a stack overflow) – 463035818_is_not_an_ai Jun 13 '19 at 15:58
Dont get me wrong, this is nitpicking on a high level, and I could have written a similar comment on the accepted answer – 463035818_is_not_an_ai Jun 13 '19 at 15:58
Yeah I was comparing to the accepted answer to understand the point you are trying to make, and I hoped a difference would give me a clue. Are you referring to the fact that per call stack allocation size is smaller than the per object heap allocation size? Even though that's true, it boils down to the fact that stack allocations are much more restrictive than heap allocations does it not? That's the point I'm trying to make, small is a colloquial way of conveying the point I guess. – Avin Kavish Jun 13 '19 at 16:11
i had to convince myself whether what i was trying to say is correct and put my findings in an answer – 463035818_is_not_an_ai Jun 13 '19 at 16:37

463035818_is_not_an_ai · Accepted Answer · 2019-06-13T16:48:18.940

I made a small modification to your code:

#include <array>

template <size_t size>
class Overflow
{
private:
    Overflow* overflow;
    std::array<int,size> x;

public:
    Overflow()
    {
        overflow = new Overflow();
    }
};

On wandbox this

int main()
{
    Overflow<1> overflow_happens;
}

results in a segmentation fault caused by overflow of the stack.

However, this

int main()
{    
    Overflow<10000> bad_alloc;
}

results in

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Aborted

You basically have two competing effects here. As a first approximation (details are a bit more involved) you have for each recursion of the consturctor:

a Overflow* on the stack
a whole Overflow instance on the heap

Hence whether you first get a stack overflow or bad_alloc depends on the size of Overflow. And for small sizes you'll first get a overflow, because stack space is much more limited than heap space.

PS: I missed your edit... if you place new Overflow[100000] in the constructor in your code you amplify the required heap space, just as I did by adding the array member. On the stack you still have a single pointer and hence you run out of heap much earlier.

When a class dynamically allocates itself at constructor, why does stack overflow happen instead of std::bad_alloc?

3 Answers3