What is a stack frame?

Recently K. Thompson asked me to specify what did I understand
with "stack frame". I think that it is im****tant for people using the
language, that this im****tant concept is clear, so I have produced
this post.

Obviously, there are some people here that live in some
special world where all those things do not exist. They should stay
there and ignore this thread. The same goes for all people that
program in coffee machines and other primitive processors that
do not have a stack pointer or enough registers to use a stack
efficiently.

----------------------
What is a stack frame?
---------------------

Within a stack, each procedure builds a "stack frame", i.e. a fixed
point within the stack, where storage for local variables is reserved.

The stack frames are a linked list of this storage areas. This builds
the conceptual stack that the language needs. Each stack frame is
linked to the previous one. A new stack frame is built when a
procedure is entered, and it is popped from the stack of stack frames
at the procedure exit.

The "main" function has the first (visible) frame, and each stack
frame built in one of the functions called after "main" started is
linked to that stack frame. This makes it possible for debuggers
and other tools to "walk the stack" of called procedures.

We can (conceptually) describe the stack frame as follows

struct tagStackFrame {
	void *Previous;
	void *ThisFrame;
	char LocalStorage[];
};

The "Next" member is a pointer to the previous function's stack frame,
the "ThisFrame" pointer points to the current stack frame, and the
Local storage is made out of different variables that a function
declares. We can imagine that the local storage of deeper nested
blocks is added to the function's local storage, even if it is not
visible (i.e. can't be accessed) after its scope disappears.

Building the stack frame (Prologue)
------------------------

The first thing to do to build a stack frame is then, to save in the
"Previous" slot, the value of the current stack frame pointer.
Normally, this is a dedicated register. For instance, the power PC
version of lcc-win uses register 31. This register is normally
defined by the operating system ABI (Application Binary Interface)
since ALL programs running in the same operating system MUST agree
as to what the frame pointer register is, if not CHAOS is surely the
consequence.

After saving the current FP (or Frame Pointer) we copy the current
value of the stack pointer into the frame pointer, to establish a new
stack frame from this stack position on. We fill then, the "ThisFrame"
slot of our structure, and lastly, we subtract from the frame pointer
the amount of space needed by the function's local variables, our
"Local storage" member.

There exist MANY variation of this scheme. Some optimizing compilers
save themselves the trouble of having a different register than the
stack pointer to build a stack frame, and just use the stack pointer to
address local variables. Conceptually however, nothing changes.

Popping the stack frame (Epilogue)
-----------------------

A function must restore the previous stack frame before leaving the
scene. This is done in the reverse order of the previous actions. The
space allocated for local variables is released by adjusting the stack
pointer, the previous value of the stack frame is popped from the stack,
and the function can now return.

Other stuff
-----------

A function uses registers to do its calculations. Those register can be
scratch registers, i.e. registers that can be used without having to
save them, or they can be registers that need save before use, to
preserve their value across function calls. The saved registers are part 
of the stack frame, even if I did not mention that above to keep things
simple. They are restored before the current function exits.

Another thing to be known is "alloca". This function allocates storage
from the stack by decreasing the stack pointer. A function that calls
alloca must do the popping of the current stack frame in a different
manner since the current stack frame is "deformed" by alloca.

And yet another thing: in standard C, we can have objects whose size
is allocated in local storage but whose exact size is unknown until
run time. This is similar to alloca, and produces the same consequences.




-- 
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32