The call stack — or how to find your way to where you are going, and back again

The is a follow-up to my previous article on method calls, so if you have not read that, I would suggest doing that first.

Figure 0: A stack of rocks (Thomas Rey on Unsplash)

With that out of the way, we can start learning about an important part of the mechanics of method calls, that is the call stack. The call stack is the part of memory which contains, usually, local variables, parameters and return addresses. It grows and shrinks all the time, depending on the current state of the program and how “deep” you are in method calls (I promise I will explain what that means).

It is called a stack because, like the rocks on figure 0, you stack each frame on top of the other, and you can do one of two things, push and pop. Pushing is to add another item or frame (or rock), popping is removing and item or a frame (or a rock).

Figure 1: An example of a call stack (R. S. Shaw [Public domain or CC0], from Wikimedia Commons)

What is going on on Figure 1?

As we see on figure 1, the call stack contains a number of frames, with each frame containing parameters, local variables and the return address. Whenever a method call is made, those three things are pushed onto the stack (added to the top, remember?). In the figure, blatantly stolen (with permission!) from Wikipedia, we see at the bottom the stack frame for a method called DrawSquare and above that for a method called DrawLine . The local variables declared in Drawline are all declared at the top, since we might add more as the method goes along, below that we have the return address which does not change size, and we have the parameters, which we also know the size of at the time of the call.

Think for a moment, where does the return address of the top stack frame point to?

It points, of course, to DrawSquare, which we can see because that is the method that was below in the stack. More specifically it is going to point to the line after the method call to DrawLine in DrawSquare, such that when DrawLine returns, the program will resume execution at the correct point after where it was called.

The last things to explain are the frame pointer and the stack pointer, but you can skip this, unless you really want to know.

The stack pointer is at the top and is always at the top. It lets the program know where values are going to be pushed and popped. The frame pointer points at the return address, and it always points to the current return address (which is fixed size, so it is a simple calculation to get from there to the parameters). When the current method returns, the stack pointer is set to the frame pointer, thus getting rid of the local variables and pointing at the return address. What happens hereafter is pretty different between different languages, but eventually the previous frame is restored.

What happens to the stack during a method call

From the figure we can also figure out the algorithm that is used when method calls are made. Here I should add a disclaimer that all languages are different, mostly subtly, but sometimes very, but this is a reasonable enough model for most beginner-intermediate programmers.

1. When the call is made the parameters are pushed on to the stack.
2. Then the return address is pushed.
3. The jump/go to is made — in other words this is where the program starts executing the method that was called. In fancy this method is the callee. You may have heard of an instruction pointer, this is where that gets updated.
4. Local variables are allocated on top of the stack.
5. The method may itself execute method calls, in that case go back to 1).
6. Once it reaches its return statement (or end), it jumps to the return address and the stack pointer and frame pointer are moved to the positions for the previous frame.

Returning values

I sense one final, burning question: how are values returned? Why are you hiding this from us?

I am not hiding it, but it usually does not happen using the stack (it can though). So instead, usually, a register is used. A register is a special piece of memory in the CPU, which is very, very fast and very, very small, usually just 4 or 8 bytes big. In this register the return value is left, for the calling method to pick up.

Wrapping up

This more or less wraps up my little lesson on the call stack. I hope it was useful, or at least interesting. I left many, many details out and mostly wrote it from memory, so it may contain omissions or factual errors. If you want a more detailed description Wikipedia as usual has an excellent article on the call stack. I hope you enjoyed reading, please comment what you thought!