The Stack, I believe is perhaps the most important data-structure. Ever! The Atlas amongst all its siblings (and cousins), as it carries the gruelling burden of entire world of computing on its back. Without it, computing could not have advanced this far – let alone a tenth of this distance, not even an inch ahead. Such is its glory. Believe me; No exaggeration. I swear!

It is so very entwined into the DNA of computational theory that its prominence begins to surface, if you look closely at how programming languages and the instruction set of processors have evolved. Ever since the diaper days of structured programming, in 1950s, functions (or procedures or sub-routines) have been an integral part of writing programs.

Calling a function, under the hood, employs a stack. Could you imagine developing a real-world application without the use of functions? Of all the zillion lines of code in today's monstrous applications, there would probably be a few million functions, to say the least. With multiple such programs running simultaneously, hundreds of stack are at play, expanding and shrinking, churning the wheels of your program, dragging it along the path of execution. The stack is always around – working under cover – supporting execution of your program.

Whenever a function is invoked, the stack (associated with the execution thread) expands – a 'frame' is 'pushed' onto the stack; similarly, when the function returns, the frame is 'popped'out of the stack. Frame is that region of the stack used by the run-time to realize a function invocation. It typically includes the return address, arguments passed, the local variables etc. The lifetime of a frame is same as the lifetime of the function itself (i.e. period from the point the function is called, until the point it returns). The layout of a frame is architecture specific (often referred to as the calling convention). The compiler emits the code to handle creation and cleanup of stack frames.

There are two parties involved in a function call scenario: the caller (the code that calls the function in question, which is usually another function; in the above code fragment 'main' is the caller), and the callee (the function being called; in the above code, 'Func' is the callee). Accordingly, there are two variant implementations of this calling convention, based on who creates and / or cleans up the frame.

Let us dissect further, and understand the anatomy of the stack layout for the standard calling convention on the ubiquitous Intel X86 processor. Prepare to get your hands bloody :-).

For reference, lets take the following code snippet:

where, 'Func'is a function that modified 'n' in someway (which is immaterial to the topic). Lets say, it modified the value of 'n' to 12, and returns 1 (return value). So, the expected output is: 1, 12. However, the output was 1, 0!
To make sense of whats going on, we have to examine the assembly code for the function call – both at the point of invocation, and within the function itself.

The assembly equivalent of the call to 'Func' in the main function is (as generated by the compiler):
1: mov ecx, dword ptr [ebp-0Ch]
2: push ecx
3: push $1
4: call Func
5: add esp,8
In line 1, the address of the variable 'n' is computed, and moved to the register ecx. In line 2, the address is pushed onto the stack (the argument). In line 3, TRUE for the boolean argument is pushed. Notice that the last argument is pushed first onto the stack. i.e., the rightmost argument gets pushed first, followed by the previous argument until the first argument to the function. In line 4, function is actually invoked. It internally pushes the return address onto the stack, and branches execution to the function entry point. In line 5, the stack pointer is incremented by 8bytes – this is equivalent to popping off both the arguments, and hence cleaning up the stack frame.

Before we look at the assembly code of the function 'Func' itself, a diagrammatic representation of how the stack frame looks, when 'Func' is executing.

The assembly code for the function 'Func' itself:
1: push ebp
2: mov ebp,esp
3: sub esp,0C0h
<function logic>
…
4: mov esp,ebp
5: pop ebp
6: ret

The lines 1 – 3, sets up the stack for the function, while the lines 4-6 towards the end of the function cleans up the stack to its original state (when it entered this function).

The line 1 above is the first instruction of the function (aka entry point). The first thing a function does is to save the frame pointer (which is ebp on x86) on the stack itself. In line 2, the current value of the stack pointer is moved into ebp – making the ebp point to the beginning of the new stack frame. This is necessary because the frame pointer is used to relatively reference any local variable. In line 3, the stack pointer is subtracted by 12 bytes (0xC). This is to create space for local variables used in this function. This is equivalent of pushing 12 bytes onto the stack.

In the line 4, is setting the stack pointer to the beginning of this frame. This is equivalent to collapsing the stack (reclaiming all the space created for local variables). Note that it is an exact reverse of what line 2 did. In line 5, the top-most value on the stack is popped into ebp, which is equivalent to restoring the previous frame pointer. Again, this is exact reverse of what line 1 did. Line 6 happily returns the control back to the caller, and in the process pops the return address off the stack.