What is a stack frame?

[jacob navia]

Recently K. Thompson asked me to specify what did I understand
with "stack frame". I think that it is important for people using the
language, that this important 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.

 

[Richard Heathfield]

jacob navia said:

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

Have you considered posting this in a newsgroup where it's relevant, such
as, perhaps, comp.arch?

Obviously, there are some people here that live in some
special world where all those things do not exist.

Well, there are many such worlds, of which comp.lang.c is one, yes. Others
include rec.scuba, alt.folklore.urban, and sci.med.dentistry. I note that
you did not post this article to those groups. Why post it to comp.lang.c?

<snip>

 

[Bartc]

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)

I think it is specified by the architecture where there is special support
for a frame pointer. But even then implementations can make whatever
arrangements they like.

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.

That sounds unlikely.

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.

And clearly 'chaos' does not result.

The point is all this stuff depends on the implementation of the language
and varies from system to system. Probably most implementations will have
some sort of stack and maybe some will use some concept of a frame pointer,
and sometimes it might be helpful to bear all this in mind. But your details
are far too specific.

 

[jacob navia]

I think it is specified by the architecture where there is special support
for a frame pointer. But even then implementations can make whatever
arrangements they like.

Arrangements that MUST be compatible with the ABI. Here we have the
"as if rule": an implementation could use other registers for the
frame pointer as long as it does NOT trash the value in the official
frame pointer.

That sounds unlikely.

Try trashing the frame pointer then, and see what happens.

And clearly 'chaos' does not result.

Because they preserve the frame pointer register.

The point is all this stuff depends on the implementation of the language
and varies from system to system.

The general setup I described does NOT.

Probably most implementations will have
some sort of stack and maybe some will use some concept of a frame pointer,
and sometimes it might be helpful to bear all this in mind. But your details
are far too specific.

No, they are general enough to cover most implementations.

 

[santosh]

jacob navia said:


Have you considered posting this in a newsgroup where it's relevant,
such as, perhaps, comp.arch?


Well, there are many such worlds, of which comp.lang.c is one, yes.
Others include rec.scuba, alt.folklore.urban, and sci.med.dentistry. I
note that you did not post this article to those groups. Why post it
to comp.lang.c?

IMO, it would be most appropriate in comp.compilers as the stack frame
is more a compiler artifact than anything else.

 

[Richard Tobin]

Try trashing the frame pointer then, and see what happens.

I can't be bothered to find out how to do that. Why not just tell us?

I wouldn't have expected the frame pointer to have any significance
outside the current process (except to a debugger), so I don't know
why "all programs running in the same operating system must agree".

-- Richard

 

[jacob navia]

I can't be bothered to find out how to do that. Why not just tell us?

I wouldn't have expected the frame pointer to have any significance
outside the current process (except to a debugger), so I don't know
why "all programs running in the same operating system must agree".

-- Richard

Obvious, because all libraries in the OS must be called with specific
calling conventions and register usage agreements. All programs must
call the OS to do I/O. They must respect the OS ABI to call those basic
OS routines.

The OS libraries are used by ALL code that runs in that system
eventually, no matter what language the end user is using.

 

[jacob navia]

IMO, it would be most appropriate in comp.compilers as the stack frame
is more a compiler artifact than anything else.

Yes, compilers are an "artifact" of compiled languages. Obviously
you think that C is not one of them.

or what ???

Basic knowledge about compiler code generation is needed if you want
to be able to understand what is going on within your program.

Obviously it is not required, as you can drive a car for miles without
needing to know that it needs gas to run.

"According to my car user's manual, if I press this pedal the car
should move. It doesn't say ANYWHERE that gas is needed".

You have the same attitude here, like your big friend.

Why santosh?

You seem reasonable at times.

 

[Richard Bos]

Yes, compilers are an "artifact" of compiled languages. Obviously
you think that C is not one of them.

or what ???

You've never seen a C interpreter?

Basic knowledge about compiler code generation is needed if you want
to be able to understand what is going on within your program.

Bollocks. Knowledge of the _language_ is needed if you want to know what
your program does. If you want to know _how_ it does that, merely basic
knowledge about merely code generation is not nearly sufficient.

Richard

 

[Richard Tobin]

All programs must call the OS to do I/O. They must respect the OS ABI
to call those basic OS routines.

Do any OS ABIs require the caller to take any care of the frame
pointer?

I just looked up the x86 call conventions. As far as I can see, the
calle saves and restores the frame pointer and does not use its old
value. So on these systems you do can use it for anyh purpose you
like.

[If you are called back by these libraries you will presumably have to
preserve the frame pointer, but that just restricts the functions
that you can pass in to it.]

The OS libraries are used by ALL code that runs in that system
eventually

No, this is certainly not true. I have used several languages that
just did system call instructions directly. The normal procedure
calling convention was irrelevant.

-- Richard

 

[Antoninus Twink]

Recently K. Thompson asked me to specify what did I understand
with "stack frame". I think that it is important for people using the
language, that this important 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.

Jacob,

Your attempts to bring this group into touch with the real world are
admirable, but you must realize by now that they're doomed before they
start?

Noone here is prepared to give you a fair hearing, and noone cares about
stacks and registers or anything that might be tainted by association
with a real computer. The clc zealots aren't going to ignore a thread
just because they have nothing positive to contribute to it.

It's started already, but it's obvious that this thread is just going to
degenerate into a flame war, with HeathField and Thomson strutting,
preening and posturing, while their fawning acolytes (Santosh step
forward) try to cement their position in the Clique by sheer
obsequiousness.

This group just isn't the place for serious discussions about C.

 

[jacob navia]

Do any OS ABIs require the caller to take any care of the frame
pointer?

Yes, the frame pointer should be preserved at all times.

I just looked up the x86 call conventions. As far as I can see, the
calle saves and restores the frame pointer and does not use its old
value. So on these systems you do can use it for anyh purpose you
like.

Yes, as I said in my message. Please read it again.

[If you are called back by these libraries you will presumably have to
preserve the frame pointer, but that just restricts the functions
that you can pass in to it.]

The OS libraries are used by ALL code that runs in that system
eventually

No, this is certainly not true. I have used several languages that
just did system call instructions directly. The normal procedure
calling convention was irrelevant.

Sure, but even using those "direct" calls, the frame
pointer must be preserved.

 

[santosh]

Yes, compilers are an "artifact" of compiled languages. Obviously
you think that C is not one of them.

Yes, but C itself doesn't specify that a stack frame is needed, nor the
details of it's setup and manipulation.

or what ???

Basic knowledge about compiler code generation is needed if you want
to be able to understand what is going on within your program.

At the machine level. A semantic understanding is possible from just
knowing C and it's standard library. Obviously, it's not sufficient for
things like debugging, interfacing with other languages etc.

Obviously it is not required, as you can drive a car for miles without
needing to know that it needs gas to run.

"According to my car user's manual, if I press this pedal the car
should move. It doesn't say ANYWHERE that gas is needed".

You have the same attitude here, like your big friend.

Why santosh?

You seem reasonable at times.

I was not saying that knowledge of stack operations are not useful. I
was saying that it is not very topical for this group. Maybe you should
post to <or <or
<etc.?

 

[santosh]

Do any OS ABIs require the caller to take any care of the frame
pointer?

Yes, the frame pointer should be preserved at all times.

I just looked up the x86 call conventions. As far as I can see, the
calle saves and restores the frame pointer and does not use its old
value. So on these systems you do can use it for anyh purpose you
like.

Yes, as I said in my message. Please read it again.

[If you are called back by these libraries you will presumably have
[to
preserve the frame pointer, but that just restricts the functions
that you can pass in to it.]

The OS libraries are used by ALL code that runs in that system
eventually

No, this is certainly not true. I have used several languages that
just did system call instructions directly. The normal procedure
calling convention was irrelevant.

Sure, but even using those "direct" calls, the frame
pointer must be preserved.

In point of fact, this isn't necessary under Linux x86.

 

[Morris Dovey]

A very quick question (possibly slightly off topic - sorry if so)
apart from the stack pointers for functions, and the heap for dynamic
allocation, is there any other memory storage commonly used and
refered to?

In embedded ("non-hosted") environments, it is not unusual for
I/O space to be mapped onto memory space. Mapped I/O may or may
not exhibit storage characteristics.

 

[Richard Tobin]

Yes, the frame pointer should be preserved at all times.

But why?

Yes, as I said in my message. Please read it again.

You seem to be contradicting yourself. You say it must be preserved
at all times, and then you agree you can use it for any purpose.
Please explain.

Sure, but even using those "direct" calls, the frame
pointer must be preserved.

Why? What happens if you don't?

-- Richard

 

[Randy Howard]

Yes, the frame pointer should be preserved at all times.

[snip]

Sure, but even using those "direct" calls, the frame
pointer must be preserved.

In point of fact, this isn't necessary under Linux x86.

How did this -fomit-frame-pointer option make its way into my compiler?
BTW, it's not running on Linux either.

 

[jacob navia]

But why?



You seem to be contradicting yourself. You say it must be preserved
at all times, and then you agree you can use it for any purpose.
Please explain.

A procedure can use any reserved register but the stack pointer
to any purpose anywhere, it needs only to save its value in
the stack, then restore it later. The value is preserved.

Obviously, if you do not preserve the stack pointer, many programs like
the debugger and others will no longer work, but in principle
your program will run without any problem.

Why? What happens if you don't?

If you do not preserve the stack pointer, you BREAK the
frame pointer chain, what means that you will destroy the possibility of
returning to the calling functions.

 

[santosh]

Yes, the frame pointer should be preserved at all times.

[snip]

No, this is certainly not true. I have used several languages that
just did system call instructions directly. The normal procedure
calling convention was irrelevant.

Sure, but even using those "direct" calls, the frame
pointer must be preserved.

In point of fact, this isn't necessary under Linux x86.

How did this -fomit-frame-pointer option make its way into my
compiler?

That doesn't matter since you cannot make direct system calls in C
anyway.

BTW, it's not running on Linux either.

Jacob was saying that the frame pointer (in his case: EBP) must be
preserved even for direct system calls. I was saying that it is not
necessary, at least under Linux/x86. In fact EBP can be used for a
parameter, if needed.

What gcc does within the program is just another point against what
Jacob is saying. He may have confused the frame pointer with the stack
pointer.

 

[Richard Tobin]

A procedure can use any reserved register but the stack pointer
to any purpose anywhere, it needs only to save its value in
the stack, then restore it later. The value is preserved.

A procedure that's called from a procedure that expects the frame pointer
to be preserved has to preserve it. If your entire program consists
of functions that don't expect it to be preserved, you don't have to.

If your functions don't save the stack pointer but call library
functions that do, there is no problem. It's only if you are *called*
by functions that expect it to be preserved that you have to worry.

In short, you don't have to follow any convention about the frame
pointer in order to call library functions.

If you do not preserve the stack pointer, you BREAK the
frame pointer chain, what means that you will destroy the possibility of
returning to the calling functions.

How does this arise when doing a system call?

-- Richard