Stack Frames in Nested Function Calls

The Problem: Managing Function State

When one function calls another, the computer faces several logistical challenges. For instance, if main() calls calculate_sum(), how does calculate_sum() know where to return to in main() once it's finished? This gets even more complicated with nested calls: if main() calls A(), and A() calls B(), B must return to A, and then A must return to main(). The return addresses must be handled in a "last-in, first-out" manner.

Furthermore, how does the calling function (caller) pass arguments to the called function (callee)? And where does the callee store its own private, local variables without interfering with the caller's data?

All of these problems are elegantly solved by using the stack.

The Stack: A LIFO Data Structure

At its core, the stack is a simple concept: a region of memory that operates on a LIFO (Last-In, First-Out) principle. Think of it like a stack of plates: you can only add a new plate to the top, and you can only remove the topmost plate.

In the context of the x86 architecture:

• The stack "grows" from high memory addresses towards lower memory addresses.
• A special CPU register, ESP (Stack Pointer), always holds the address of the "top" of the stack.
• Two primary instructions manipulate the stack:
  • push <value>: This first decrements ESP (moving it to a lower address) and then writes the value to the memory location now pointed to by ESP.
  • pop <register>: This reads the value from the memory location pointed to by ESP into a register and then increments ESP.

The following video provides an excellent visual introduction to these concepts.

The Stack Frame: A Function's Private Workspace

When a function is called, a dedicated block of memory is reserved on the stack for its exclusive use. This block is called a stack frame. It contains everything the function needs to do its job and return correctly:

• Its arguments (passed by the caller).
• The return address (so it knows where to go back to).
• Space for its own local variables.

To manage this frame, a second register is essential: EBP (Base Pointer). While ESP is dynamic and moves as we push and pop data, EBP is set once at the beginning of a function to a fixed point in the frame. It acts as a stable anchor, allowing us to reliably access parameters and local variables using constant offsets, regardless of what's happening at the top of the stack.

The diagram below shows a typical layout for a stack frame. Notice how EBP acts as the reference point.

The Calling Convention: The Rules of the Road

To ensure that function calls are predictable and that code compiled from different sources (like C and assembly) can interoperate, CPUs and compilers follow a strict protocol known as a calling convention. For our purposes, we'll focus on the standard C calling convention, cdecl.

This convention defines a precise sequence of actions for both the caller and the callee. Let's trace this "dance" step-by-step. The entire process is beautifully animated in the Mxy video.

Let's formalize what you just saw in the video.

Step 1: The Caller Prepares

Before the call instruction is even executed, the caller sets the stage:

1. Push Arguments: The caller pushes the function arguments onto the stack in reverse order (right-to-left). So for my_func(a, b, c), c is pushed first, then b, then a.

Step 2: The call Instruction

2. call my_func: This instruction does two things automatically in hardware:
   a. Pushes the return address (the address of the instruction immediately after the call) onto the stack.
   b. Jumps to the first instruction of my_func.

Step 3: The Callee's Prologue

The first thing the called function does is execute its prologue, a standard sequence of instructions to set up its stack frame:
3. push ebp: It saves the caller's base pointer. This is crucial; we're essentially saving the anchor point of the previous frame. This creates a linked list of stack frames, which debuggers use to generate a "call stack" trace.
4. mov ebp, esp: It establishes its own stable base pointer. EBP now points to the location of the saved old EBP. This is the anchor for the current frame.
5. sub esp, N: It allocates space for all its local variables by simply moving the stack pointer down by N bytes.

At this point, the function's stack frame is fully formed. The function can now access its parameters at positive offsets from EBP (e.g., [ebp+8], [ebp+12]) and its local variables at negative offsets (e.g., [ebp-4], [ebp-8]).

Step 4: The Callee's Epilogue and Return

Once the function has finished its work, it executes the epilogue, which precisely undoes the prologue:
6. mov esp, ebp: This is a fast way to deallocate all local variables at once by simply resetting the stack pointer back to the base of the current frame.
7. pop ebp: This restores the caller's base pointer, effectively destroying the current stack frame and reverting to the previous one.
8. ret: This final instruction does one thing: it pops the return address off the top of the stack and jumps to it.

Step 5: The Caller Cleans Up

9. Execution is now back in the caller. The final step is for the caller to clean the arguments it pushed in Step 1 off the stack, typically by adding to ESP (add esp, M, where M is the total size of the arguments).

This entire process is meticulously documented in the following guide. It provides the literal assembly code for the prologue and epilogue and explains the caller/callee rules in text, reinforcing what the video showed visually.

Tracing Nested Calls

The true power of this system becomes apparent with nested calls. Each call creates a new frame on top of the previous one, and each ret unwinds the last frame created. The chain of saved EBP values allows the stack to be unwound cleanly, no matter how deep the calls go.

The image below illustrates the state of the stack after main() has called func_A(). You can see two distinct frames, linked by the saved ebp(1) in func_A's frame, which points back to the base of main's frame.

If func_A were to then call another function, func_B, another frame would simply be built on top of func_A's, repeating the exact same process. When func_B returns, its frame is destroyed, returning control to func_A. When func_A returns, its frame is destroyed, returning control to main. It's a robust and scalable system.

Conclusion

In this lesson, we have demystified the process of function calls, tracing the flow from a high-level C instruction down to the movement of individual registers and memory pointers.

• Key Takeaways:
  • The stack is a LIFO memory region, managed by the ESP register, that grows towards lower addresses on x86.
  • Each function call creates a stack frame, a private workspace containing parameters, local variables, and control information.
  • The EBP (Base Pointer) register provides a stable reference point to access data within a stack frame, while ESP can change.
  • The calling convention (cdecl) is a strict protocol that governs how callers and callees cooperate to manage the stack.
  • A function's prologue (push ebp; mov ebp, esp; ...) builds the stack frame, and its epilogue (mov esp, ebp; pop ebp; ret) tears it down.
  • Nested calls create a chain of stack frames, linked by saved EBP values, which are cleanly unwound as each function returns.

We have now completed our foundational survey of computer architecture. You have a solid conceptual understanding of the CPU, memory, I/O, interrupts, and the stack. In our next module, we will transition from theory to practice. We will begin by setting up the necessary tools—an assembler and a cross-compiler—to start writing the very first lines of assembly code for our operating system. You will soon be writing the function prologues and epilogues we discussed today by hand