Why is the recursion depth non-deterministic (C++)?

Question

Repeated runs of the following C++ program give a different maximum number of recursion calls (varying by approximately 100 function calls) before a segmentation fault.

#include <iostream>

void recursion(int i)
{
    std::cout << "iteration: " << ++i  << std::endl;
    recursion(i);
}

int main()
{
    recursion(0);
};

I compiled the file main.cpp with

g++ -O0 main.cpp -o main

Here and here the same issue as above is discussed for java. In both cases, the answers are based on java related concepts, JIT, garbage collection, HotSpot optimizer, etc.

Why does the maximum number of recursions vary for C++?

Undefined behaviour is undefined. There is nothing unusual in different runs producing different results. No one has promised you otherwise. — n. m. could be an AI, Dec 12 '20 at 23:13
I was not aware that [infinite recursions](https://stackoverflow.com/questions/5905155/is-this-infinite-recursion-ub) are undefined behavior in C++ which explains the C++ aspect of the question. But there is some variation in the number of operations the OS "allows" before terminating/killing the process - at least when the stack is full? — dgruending, Dec 12 '20 at 23:20
ASLR could be responsible for that, try disabling it and see what happens. — n. m. could be an AI, Dec 13 '20 at 07:57
Disabling ASLR results in a constant number of recursion. That answers the OS aspect of the question. Thx! I documented what I did below. — dgruending, Dec 13 '20 at 12:24

score 4 · Answer 1 · answered Dec 12 '20 at 22:26

4

Your recursion never logically terminates. It only terminates when your program crashes due to lack of stack space.

A certain amount of stack space is used for every recursive call, but in C++, it's not defined exactly how much stack space is available and how much is used per recursive call.

The stack space used per call may vary by optimization settings, linker options, alignment requirements, how your program is launched, and a ton of other things.

Bottom line: you have coded a bug, and you are running afoul of undefined behavior in your compiler and platform. If you want to figure out exactly how much stack space your program has on its current thread, your platform will have APIs you can call to get that value.

answered Dec 12 '20 at 22:26

Tumbleweed53

1,491
7
13

but I compile it once. the available stack space is also the same every time. shouldn't the execution be independent of the optimization and linker settings for a repeated run of the very same binary? maybe this is less of a C++ question and more related to how the operating system terminates the program? – dgruending Dec 12 '20 at 22:32
@dgruending • Does your platform support [ASLR](https://en.wikipedia.org/wiki/Address_space_layout_randomization)? – Eljay Dec 12 '20 at 22:38
@Eljay I am running Ubuntu 20.04 so I assume that the answer to your question is "yes". – dgruending Dec 12 '20 at 22:39
*"It only terminates when your program crashes due to lack of stack space."*. Can also reach the UB with int overflow (and it is not just theorical, tail recursion can be optimized easily here). – Jarod42 Dec 12 '20 at 22:42

Yakk - Adam Nevraumont · Accepted Answer · 2020-12-13T04:23:51.250

3

What happens when you blow the stack is not a guaranteed crash. Depending on the system, you could just be trashing memory in a relatively random bit of your memory space.

What is in that memory might depend on what memory allocations occurred, how much contiguous memory the OS handed to you when you asked for some, ASLR, or whatever.

Undefined behaviour in C++ is not predictable.

edited Dec 13 '20 at 04:23

answered Dec 12 '20 at 22:58

Yakk - Adam Nevraumont

262,606
27
330
524

I was not aware that infinite loops are undefined behavior in C++. Related [N1528](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1528.htm) – dgruending Dec 12 '20 at 23:02
2

@dgru this is not an infinite loop. It is unbounded recursion. C++ implementations can place limits on recursion, after which behaviour is undefined (aka blowing the stack) – Yakk - Adam Nevraumont Dec 12 '20 at 23:04
What would be the process that would lead to "trashing in a random bit of your memory space?" Shouldn't the OS check for that? – dgruending Dec 12 '20 at 23:05
2

@dgruending The processes' memory space. Many OS's (attempt to) protect the system from the process, but rarely does it protect the process from itself. A process crashing is an example of the OS defending the system from the process. A process writing over its own heap and making new/delete operations fail dramatically is an example of a process damaging itself. How that defence works depends on the system; does it place the stack with a huge set of memory guard pages, or does the stack overflow directly into the heap? – Yakk - Adam Nevraumont Dec 13 '20 at 04:22

score 0 · Answer 3 · answered Dec 13 '20 at 11:37

Beyond the C++ aspect: Following the comments of Eljay and n.'pronouns'.m, I turned of ASLR. This post describes how to do that. In short, ASLR can be disabled via

echo 0 | sudo tee /proc/sys/kernel/randomize_va_space

and enabled via

echo 2 | sudo tee /proc/sys/kernel/randomize_va_space

After disabling ASLR, the number of recursions before the system segmentation fault is constant for repeated execution of the described program.

Why is the recursion depth non-deterministic (C++)?

3 Answers3