10 replies to this topic

[Fatal_Exception]

This started as a quick reply to an Ask A Pro thread, but ended up becoming a wall of text lesson on stack overflows that might prove useful as a reference. The technical details are not completely accurate, but I think it illustrates the concept.

cowman001, on 21 September 2012 - 01:01 AM, said:

how do i reset the stack? for future reference?

The stack is internal to lua, storing the current state of the program. You can't simply 'reset' it, short of restarting the computer. You can avoid overflowing it by making sure you return from any functions you call, in a timely manner.

It works something like this:
Every time you call a function (or start a new shell process), lua puts the current position in the program on the stack, then calls the function. Any parameters or local variables inside a function also go on the stack.
When you return from a function, it pops (removes from the stack) all the local variables, and returns to where the function was called from.
Unless you're very careful when you make recursive calls (functions calling themselves or their 'ancestors'), you continually push more data onto the stack, but never pop it back off by returning. Eventually you run out of stack memory, and your program crashes.

Consider the following badly-behaved example:

Spoiler

local funcOne, funcTwo -- "forward declaration" of functions

local function functionOne(depth)
-- push parameter (depth) onto the stack (automatic)
  depth = depth or 0 -- set it to 0 if it's nil
  print("In functionOne() -- depth " .. depth)  
  funcTwo(depth + 1) -- push current program position onto stack and call funcTwo()
end -- (we never get here because we keep calling another function)
-- pop local variables and parameters off stack
-- pop return address (the place this function was called from) and move back there

local function functionTwo(depth)
-- push parameter (depth) onto the stack (automatic)
  print("In functionTwo()")
  funcOne(depth) -- push current program position onto stack and call funcOne()
end -- (we never get here because we keep calling another function)
-- pop local variables and parameters off stack
-- pop return address (the place this function was called from) and move back there

-- Execution starts here:

funcOne = functionOne
funcTwo = functionTwo

funcOne() -- push current program position onto stack and call funcOne()

When run, it will rapidly call both functions in succession, adding to the stack each time, but never returning.

Output:

Spoiler

In functionOne() -- depth 0
In functionTwo()
In functionOne() -- depth 1
In functionTwo()
In functionOne() -- depth 2
In functionTwo()

...

In functionOne() -- depth 118
In functionTwo()
In functionOne() -- depth 119
In functionTwo()
In functionOne() -- depth 120
java.lang.ArrayIndexOutOfBoundsException

Because the functions never reach the 'end', they don't get a chance to pop off the data they added to the stack, so it keeps growing.

Let's have a look at what the stack looks like as we run the program:

Spoiler

At the start of the program, the stack is essentially a blank slate (well, not quite, but correct enough for our purposes)

When we first call funcOne() on line 25, it adds information to the stack to tell it where to continue from after we're finished with the function.

funcOne() -- <return to line 25>

Since the function wants a parameter, it also gets added:

funcOne() -- <return to line 25>
depth = nil

Then we set it equal to zero:

funcOne() -- <return to line 25>
depth = 0

Now we call funcTwo with (depth + 1) so:
Push the return address

funcOne() -- <return to line 25>
depth = 0
funcTwo() -- <return to line 6>

Now the parameter

funcOne() -- <return to line 25>
depth = 0
funcTwo() -- <return to line 6>
depth = 1

We then call funcOne again and add its parameter:

funcOne() -- <return to line 25>
depth = 0
funcTwo() -- <return to line 6>
depth = 1
funcOne() -- <return to line 15>
depth = 1

And so on until:

Spoiler

funcOne() -- <return to line 25>
depth = 0
funcTwo() -- <return to line 6>
depth = 1
funcOne() -- <return to line 15>
depth = 1
funcTwo() -- <return to line 6>
depth = 2
funcOne() -- <return to line 15>
depth = 2

...

funcOne() -- <return to line 15>
depth = 118
funcTwo() -- <return to line 6>
depth = 119
funcOne() -- <return to line 15>
depth = 119
funcTwo() -- <return to line 6>
depth = 120
funcOne() -- <return to line 15>
depth = 120

At this point it tries to call funcTwo(121), but there's no more room on the stack. Stack overflow! CRASH!

In contrast, here's a well-behaved program:

Spoiler

local function funcOne()
  print("In funcOne")
end
-- pop return address (the place this function was called from) and move back there


-- Execution starts here:

while true do
   funcOne() --  push current program position onto stack and call funcOne()
end

When we first enter the function, it puts the return address on the stack, so the stack looks like:

funcOne() -- <return to line 10>

When we hit the end of the function, the return address gets popped, leaving the stack empty -- exactly as it found it.
Since we leave the stack in the same condition as it was when we started, it can never overflow.

[Sammich Lord]

Very well explained. I remember when I was a noob and got stack overflows constantly and then I would scream out "Fuck you stack overflow error!".
But very nice post, it will help new people out a lot.

[Mr. Fang]

Not going to lie I was about to ask this question in the forums, mainly because I've never experienced one, but it sounds like the ability to crash your computer because you had too many windows open.

[Cranium]

Mr. Fang, on 21 September 2012 - 04:59 PM, said:

Not going to lie I was about to ask this question in the forums, mainly because I've never experienced one, but it sounds like the ability to crash your computer because you had too many windows open.

That is a very apt analogy.

[Geforce Fan]

Doesn't a stack overflow happen what you shell.run('') ; too many times? How do you fix that one? Is there a shell.quit() or somthing?

[Lyqyd]

Some technical corrections:

• The stack is dealt with in the java code, by LuaJ.
  
• Lua is compiled to bytecode, so the jumping around between functions is actually between different locations in memory, not different lines in the file.
  
• Cross-recursion is not the only way to trigger a stack overflow, thought it's not a bad example. Other ways include:
  
  • Plain recursion
    
  • Recursion using shell.run()
    
  • Cross-recursion using shell.run()
    
  • Improper tail-call recursion

[Fatal_Exception]

All true, and details I basically glossed over to simplify things. I wanted to present an idea of what the stack was conceptually without delving too much into technicalities. I probably should have expanded on the different forms of recursion though.

The major take home point being, if you aren't careful to clean up after yourself, your program will crash eventually.

[PixelToast]

a easier way to do it is to create your own stack in a table storing coroutines or whatever data you want to process
thats how my new advanced serialization works :3 only a couple stack levels />
i also plan on making my own os with its own, unlimited stack

[bbqroast]

Out of interest, will this cause a "stack leak":

function foo()
  // Regular code
end

Because it has no return call? A lot of my void functions I just leave tail less, as they return automatically when they hit the end marker, but does that prevent them from getting kicked off the stack?

[Lyqyd]

No, as long as the function eventually finishes executing and returns (with or without an explicit return keyword doing the returning), it will be removed from the stack. The issue arises when a function is waiting on something else to finish before exiting (such as another call to itself), but nothing ever exits. You fill up the stack with functions all waiting for the next function up the stack to exit until the stack gets too tall and overflows.

[bbqroast]

Cool, thanks for the advice />.