Why Infinite Recursion Leads to Seg Fault

Why does an infinitely recursive function in PHP cause a segfault?

If you use XDebug, there is a maximum function nesting depth which is controlled by an ini setting:

$foo = function() use (&$foo) { 
    $foo();
};
$foo();

Produces the following error:

Fatal error: Maximum function nesting level of '100' reached, aborting!

This IMHO is a far better alternative than a segfault, since it only kills the current script, not the whole process.

There is this thread that was on the internals list a few years ago (2006). His comments are:

So far nobody had proposed a solution for endless loop problem that
would satisfy these conditions:

1. No false positives (i.e. good code always works)
2. No slowdown for execution
3. Works with any stack size

Thus, this problem remains unsloved.

Now, #1 is quite literally impossible to solve due to the halting problem. #2 is trivial if you keep a counter of stack depth (since you're just checking the incremented stack level on stack push).

Finally, #3 Is a much harder problem to solve. Considering that some operating systems will allocate stack space in a non-contiguous manner, it's not going to be possible to implement with 100% accuracy, since it's impossible to portably get the stack size or usage (for a specific platform it may be possible or even easy, but not in general).

Instead, PHP should take the hint from XDebug and other languages (Python, etc) and make a configurable nesting level (Python's is set to 1000 by default)....

Either that, or trap memory allocation errors on the stack to check for the segfault before it happens and convert that into a RecursionLimitException so that you may be able to recover....

Why doesn't a forever loop crash? Why does an infinite recursion crash?

Because an infinite recursion keep storing recursive calls in the stack (which is one of the memories held by your application), so it will eventually fill the stack completely, hence you get the classic stack overflow error.

In an infinite loop, you don't store anything and frequently you just keep updating variables and things like that, which won't occupy more memory than these variables already do, so nothing will break. However, you can have an infinite loop breaking if you add things in the memory inside your loop, like adding an element to a list inside the loop.

Why does my recursive function cause a segmentation fault?

You are accessing memory you can't access. It just isn't obvious in the code (like a dangling pointer). Recursion is tricky; you can easily overflow the stack. The stack stores information when you enter a function (registers or addresses of parameters, saved values of registers used in the calling function and the called function, and a return pointer (where to jump to when you finish the function) basically.

The stack has a certain size. It might be quite large, but it is finite. In recursion, you keep calling the same function from within itself. If this happens too many times, you will "overflow the stack" -- that is, try to "push" more info onto the stack when it is already full, which means at an address past the end of the stack -- memory you may not have access to. (If you do have access to it, you maybe overwriting one of your variables or some such.)

When you have recursed far enough, you must return from your function without calling it again. Probably in your n==1 "if".

segmentation fault on a recursive function

There is no exit from recursion.

You may wanted

          if(m == 0)
             n = 1;
          else if(m == 1)
             n = n;
          else 
             n = pwr(n, m/2) * pwr(n, m/2);
          return n;

Why does this program cause a segmentation fault?

The situation you describe is known as "infinite recursion", and is described in this post.

In the mentioned post, main() is calling main(), calling main(), ...

In your case, a() is calling b(), calling a(), calling b(), ...

The mentioned post shows the effect of this on the stack and gives an idea on how this is handled in the memory of your computer (using assembly).

segfault due to finite recursion

Each level of recursion takes up a certain amount of memory on the stack. On all platforms I'm aware of stacks have a fixed (but configurable) relatively small size.

Ultimately the number of recursions is limited to (stack size) / (stack used per call) so to increase the number of recursions you need to either increase the size of the stack or decrease the size required for each call. In your example you appear to have an 8mb stack so to achieve 1,000,000 levels of recursion each level can only allocate 8 bytes on the stack which is probably not possible in most implementations.

One way to decrease the size of each call is to pass a reference to a structure containing any static parameters rather than individual parameters. In your example case this won't help as you only have one static parameter. What might help on platforms where an int is smaller than a pointer (e.g. most 64-bit platforms) would be to remove the const& as the reference is likely to be passed as a pointer.

If the above doesn't work then recursion should be replaceable with a non-recursive implementation and store your state in a std::stack which is heap allocated and won't therefore cause stack overflows.

iverilog recursive function causes segmentation fault

As @sharvil111 suggested, the value that I passed was 1'bX at that point of time.

So I made sure to set it to 0 before calling.

Thanks for the other suggestions, but e.g. what @dave_59 said didn't do the trick in my case as param wasn't too small, it was just not defined yet.

---

Related Topics