Crash with deep recursion

[mingodad]

Hello ! Testing this tool https://github.com/samhocevar/zzuf and using a simple fibonacci function the tool managed to change it in a way to break Squirrel/SquiLu, the same function converted to javscript, python, lua do not crash.

zzuf -s 0:10000 -c -C 0 -q -T 3 squilu fibo.nut

Original src:

local fib;
fib = function(n)
{
    if (n < 2) return 1;
    return fib(n-2) + fib(n-1);
}
fib(10);

Generated src by zzuf:

local fib;
fib = function(n)
{
    if (n < 2) return 1;
    return fib(n=2) + fib(n-1);
}
fib(10);

Segmentation fault

Nodejs:

function fib(n)
{
    if (n < 2) return 1;
    return fib(n=2) + fib(n-1);
}

var n=10;
console.log(n, fib(n));

crash.js:2
function fib(n)
            ^

RangeError: Maximum call stack size exceeded
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:2:13)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)
    at fib (/home/mingo/dev/SquiLu/SquiLu/samples/crash/crash.js:5:12)

Lua:

local function fib(n)

    if (n < 2) then return 1 end;
    return fib(n=2) + fib(n-1);
end

local n=10;
print(n, fib(n));

lua crash.lua 
lua: crash.lua:5: ')' expected near '='

Python:

def fib(n):
    if (n < 2):
        return 1
    return fib(n=2) + fib(n-1)

n=10
print(n, fib(n))

RuntimeError: maximum recursion depth exceeded

Cheers !

[zeromus]

When I test that program, I get over 1 million "deep" with no crash, I assume because it is properly tailcalling and functioning normal with an argument of 2 every single time.

[albertodemichelis]

Works fine for me. Please give a spin with vanilla Squirrel before assuming its a bug in Squirrel.

[mingodad]

Just in case I did on a machine with ubuntu 14.04 64bits:

wget https://github.com/albertodemichelis/squirrel/archive/master.zip
unzip master.zip
cd squirrel-master
make
bin/sq crash.nut 
Segmentation fault (core dumped)

Cheers !

[albertodemichelis]

Ok. after running for about an hour it finally run out of memory and crashed :) . I guess we can add a sq_setmaxstacksize() or something like that.

[mingodad]

Thank you ! I would appreciate a solution for this.

[RizzoRat]

I'd like to point out the reason basically is sq_malloc failing, while tail recursion not kicking in is just ONE of many possible causes for it to fail. "Out of memory" is known to be a hen-or-egg issue. I think it's the host application's responsibility to provide an approach for it and Squirrel should not take care of it (it's no operating system, but going that road would lead to one when thought to an end). I personally use custom sq_malloc with preallocation to shut down the sqvm properly after some proper error output. I'd like to also point out: On low-memory systems (like embedded), a user will have to have the memory in mind anyways. On modern systems with the "virtual memory is insanely many so I don't care" in mind any recursion issue will lead to the user investigating why his recursion apparently "never ends" way before the system/OS bails out.

[albertodemichelis]

In this case tail recursion is not possible as the last operation is not a call but an addition. Tail recursion only kicks in in this case "return call(a,b,c)".

[mingodad]

Hello ! I disagree with "Squirrel should not take care of it" because as you could see I did a look at how other scripting languages managed this issue and gave examples of some known ones and they do manage it themselves. Cheers !

[zeromus]

I think you should have to specify stacksize when creating a thread anyway. Just brainstorming, you could throw an error when the allocation to grow the callstack fails, but you then do have to worry about not being able to allocate the memory required for the error, in case that's supposed to go through the stack, even momentarily; not to mention the memory required to build the string. So it's surely simpler to cap the stack size and throw an error--but leave size on the stack for throwing the error (if needed), else, the stack may unexpectedly grow one last time beyond the user's specifications!

[RizzoRat]

Squirrel automatically increases stack size like any other array or table, too, independent of its initial stacksize - just it has a watermark to do that automatic growing somewhat more early. Hence The stack size per definition(!) is unlimited in the same way like any other Squirrel object. To be strict, when changing that and putting an artificial limit on it, you also should put it on all other objects and the overall total used memory to make sure and keep consistency. It doesn't matter if you get a segfault due to stack grow failing or due to any other array or table grow failing, reading data from a file or whatever you do. When no memory is available, things break. Always. Unless you artificially limit memory to a predefined amount. Note Squirrel offers the latter to the host application by using custom sq_malloc, sq_free and sq_realloc. Handling this issue at all within Squirrel is a very, very basic design decision with quite some consequences (and/or inconsistencies).

Oh and: Think of handling the issue using an exception, preallocating memory at startup or creating any other reserve for handling the exception - the user than uses try/catch to catch it just to again massively allocate memory. What to do THEN? ("out of memory" is unsolveable in a dynamic way!)

[RizzoRat]

To be clear, I consider this as a similar problem to the problem some people ask for over and over: detect unintended infinite loops in Squirrel. A while (1) ; will stall, but would you argue about the necessity of setting a timeout and letting Squirrel catch that itself? I think this thing is pretty similar in terms of design decision.