Why Does an Infinitely Recursive Function in PHP Cause a Segfault

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

PHPUnit Segmentation fault

Next to what cweiske suggests, if upgrading PHP is not an option for you and you have problems to locate the source of the segfault, you can use a debugger to find out more.

You can launch gdb this way to debug a PHPUnit session:

gdb --args php /usr/bin/phpunit quiz_service_Test.php

Then type in r to run the program and/or set environment variables first.

set env MALLOC_CHECK_=3
r

You might also consider to install the debugging symbols for PHP on the system to get better results for debugging. gdb checks this on startup for you and leaves a notice how you can do so.

Inline recursive functions

As @HolyBlackCat mentioned - inline is only a hint for a compiler. Compiler ignores it in a lot of cases.

As for your test - your recursive code causes a crash because of stack overflow error - every function call reserves a memory block on the stack and your program runs out of memory.

How can I use recursion to retrieve parent nodes?

Hmm.. judging by your structure of your DB, it would seem that something is amiss unless I'm missing something

The statement

$sql = "SELECT * FROM products WHERE child_id = '$pid'";

Tells me that for each product, you are storing the ID of the child. Typically, in a tree based structure, it's the reverse, you store the parent ID not the child - unless you want a child node to have many parents. If that is the case, then the function could easily run into problems. Consider the following:

| ID | Child_ID |
+----+----------+
| 1  | 2        |
| 2  | 1        |

This would cause an infinite loop. If you store the parent_id, then by that nature, you are encoding the graph to be hierarchical. Since every product has A parent, then the logic can be written recursively.

The could then be written as such?

function get_parents ($pid, $found = array()) {
    array_push ($found, $pid);

    $sql = "SELECT * FROM products WHERE id = '$pid'";
    $result = mysql_query($sql) or die ($sql);

    if(mysql_num_rows($result)){
        while($row = mysql_fetch_assoc($result)){
            $found[] = get_parents($row['parent_id'], $found);
        }
    }
    return $found;
}

How would I best construct a recursive tree visual with unknown child nodes in PHP?

Maybe this will give you a prod in the right direction? (Slightly fixed)

function recursive_tree ($startQuestionId, $alreadyDisplayed = array()) {
  // Make sure we only display each question once
  $alreadyDisplayed[] = $startQuestionId;
  // Replace this with a sensible query to get the answers for question id $startQuestionId
  $answers = $db->query("SELECT answers.answerId, answers.opensQuestionId FROM questions, answers WHERE questions.questionId = '$startQuestionId' AND answers.questionId = questions.questionId");
  // Echo a header for the question
  echo "<div id='question$startQuestionId'>Question $startQuestionId\n<ul>\n";
  while ($row = $db->fetch()) {
    // Loop through the answers to this question
    echo "<li>\nAnswer id {$row['answerId']} opens question id {$row['opensQuestionId']}\n";
    if (!in_array($row['opensQuestionId'],$alreadyDisplayed)) {
      // The linked question hasn't been displayed, show it here
      $alreadyDisplayed = array_merge($alreadyDisplayed,recursive_tree($row['opensQuestionId'],$alreadyDisplayed));
    } else {
      // The linked question has already been displayed
      echo "(<a href='#question{$row['opensQuestionId']}'>Already displayed</a>)\n";
    }
    echo "</li>\n";
  }
  // Close everything off
  echo "</ul>\n</div>\n";
  return $alreadyDisplayed;
}

// And call it like this
$questionToStartAt = 1;
recursive_tree($questionToStartAt);

Code to simulate a segfault

It is as @Marc B says in comment

kill -11 $pid

or

kill -SIGSEGV $pid

where $pid is the pid of the interpreter running your script. Any script would do, one convenient possibility would be just sleep(60), which gives you 60 seconds to send it a SIGSEGV before it exits cleanly on its own.

---

Related Topics