CODEWITHSUNDEEP
c++recursion
Ant
Ant

Reputation: 123

Stack overflow error or exception?

Why does the following ends up with no error?

void func()
{
   func();
}

int main()
{
   func();
}

Upvotes: 10

Views: 858

Answers (6)

Matteo Italia
Matteo Italia

Reputation: 126937

In theory, it would overflow the stack (because, even if no local variables are used, each call would add the previous return address on the stack); in practice, with optimizations enabled, it doesn't overflow because of tail call optimization, which actually avoids any resource consumption transforming the call in a jump, thus not consuming the stack.

This can be easily seen by examining the optimized assembly generated by the OP code:

func():
.L2:
        jmp     .L2
main:
.L4:
        jmp     .L4

func is optimized to an infinite loop, both the "freestanding version" and the inlined call in main.

Notice that this is coherent with the C++ standard for the "as if" rule: the compiled program must run as if it were what you requested in the code (in terms of effect), and since the stack size is just an implementation limit, the generated code that uses a call and the one that uses a jmp are equivalent.

But: this is an even more particular case, as the standard even says that infinite looping (defined as "not terminating and not having some side-effect") is actually undefined behavior, so in theory the compiler would be allowed to omit that call entirely.

Upvotes: 24

vbence
vbence

Reputation: 20343

Back in the olden days, when you wanted to over-optimize an ASM program there was a practice: may times a function ended with calling an other function (then returning). It would look something like:

somefunc:

    ; do some things

    CALL someotherfunc
    RET

someotherfunc:

    ; do some other things

    RET

This way when CALL someotherfunc happened the address of the next instruction (the RET) is saved into the stack and then someotherfunc returned just to execute the a return. Exactly the same results can be achieved with a JMP to someotherfunc. This way the stack will not contain the address of the last instruction, but it will contain the original caller's address. So when someotherfunc makes it's RET the program will continue at the original caller.

So the optimized code would look like:

somefunc:

    ; do some things

    JMP someotherfunc

someotherfunc:

    ; do some other things

    RET

And if somefunc is calling itself as the last instruction (in fact that is the only instruction), it would indeed look like:

somefunc:

    JMP somefunc

Upvotes: 1

Ira Baxter
Ira Baxter

Reputation: 95420

If you are compiling and running this on Windows in a command window, you may get a crash but without any remarks from the OS. (We build a funny compiler and run into this problem a lot). Microsoft's claim is that when program does very bad things, they can't recover... so they simply kill the process and restart the command prompt. LIkely in your case, after you've recursed to the stack limit, when the trap handler attempts to do something (like push trap status on the stack) there isn't any space and Windows kills your process.

I personally think this is inexcusable behavior. If my process does something bad, the OS should always complain. It might say, "process terminated with prejudice", along with some kind of indication ("you ran out of stack in the last-ditch error handler") but it should say something.

Multics got this right in 1966. Its a shame we haven't applied these lessons in over 40 years.

Upvotes: 3

jbruni
jbruni

Reputation: 1247

On my machine it ends with a segfault (like infinite recursion should).

Maybe your shell isn't reporting the segfault. What OS are you using?

Upvotes: 1

thkala
thkala

Reputation: 86433

It does end with a Segmentation fault on my Linux system - Valgrind indicates a possible stack overflow, which is of course true, since for each function call a new stack frame is required.

However, enabling optimisations in the compiler reduces this whole program to an infinite loop, which, naturally, does not end at all:

        .file   "so.c"
        .text
        .p2align 4,,15
.globl func
        .type   func, @function
func:
.LFB0:
        .cfi_startproc
        .p2align 4,,10
        .p2align 3
.L2:
        jmp     .L2
        .cfi_endproc
.LFE0:
        .size   func, .-func
        .p2align 4,,15
.globl main
        .type   main, @function
main:
.LFB1:
        .cfi_startproc
        .p2align 4,,10
        .p2align 3
.L5:
        jmp     .L5
        .cfi_endproc
.LFE1:
        .size   main, .-main
        .ident  "GCC: (GNU) 4.4.3"
        .section        .note.GNU-stack,"",@progbits

Here's the interesting part:

.L5:
        jmp     .L5

Upvotes: 5

Puppy
Puppy

Reputation: 147036

Likely, your compiler optimized it away and turned it into a while(true){} construct.

Upvotes: 8

Related Questions