Node:The stack in detail, Previous:The stack, Up:The stack



The stack in detail

Let's examine this process in detail. When one function calls another function in a C program, control passes from the first function to the second function. When the second function ends, control passes back to the statement in the first function that immediately follows the function call. But how does the computer know where in its memory this statement resides?

The answer is simple. The computer keeps a list of the addresses in memory of the places to which it must return, no matter how many function calls are made. This list is the stack.

The stack gets its name from the fact that it is a LIFO, or last in, first out structure, meaning that the last item to be pushed onto the stack is the first item to be popped off. It works, in other words, like the stack of dinner plates you keep in your kitchen cabinet. As you wash plates, you pile them one by one on top of the stack, and when you want a plate, you take one from the top of the stack. The stack of plates in your cabinet is therefore also a last in, first out structure, like the computer's stack.

When one C function calls a second function, the computer leaves itself an address at the top of the stack of where it should return when it has finished executing the second function. If the second function calls a third function, the computer will push another address onto the stack. When the third function has finished executing, the computer pops the top address off the stack, which tells it where in the second function it should return. When the second function has finished, the computer again pops the top address off the stack -- which tells it where in the first function it should return. Perhaps the first function then calls another function, and the whole process starts again.

What happens when black_hole calls itself? The computer makes a note of the address it must return to and pushes that address onto the top of the stack. It begins executing black_hole again, and encounters another call to black_hole. The computer pushes another address onto the top of the stack, and begins executing black_hole again. Since the program has no chance of popping addresses off the stack, as the process continues, the stack gets filled up with addresses. Eventually, the stack fills up and the program crashes.