105 posts
Posted 21 September 2012 - 07:10 AM
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.
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:
When run, it will rapidly call both functions in succession, adding to the stack each time, but never returning.
Output:
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:
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.
Since the function wants a parameter, it also gets added:
Then we set it equal to zero:
Now we call funcTwo with (depth + 1) so:
Push the return address
Now the parameter
We then call funcOne again and add its parameter:
And so on until:
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:
When we first enter the function, it puts the return address on the stack, so the stack looks like:
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.
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.
