Re: What is a stack frame?
- From: Chris Torek <nospam@xxxxxxxxx>
- Date: 3 Mar 2008 14:55:53 GMT
In article <fqgksq$eja$1@xxxxxxxx>, jacob navia <jacob@xxxxxxxxxx> wrote:
We can (conceptually) describe the stack frame as follows
struct tagStackFrame {
void *Previous;
void *ThisFrame;
char LocalStorage[];
};
There is no need for a separate "this frame" pointer.
In any case, the more general term, which covers what a C compiler
*must* provide in effect, is "activation record". Any given
"activation record" -- whether it is on a stack or not -- contains
the "local storage" for the function, as you describe here.
If the activation record contains a single pointer to a previous
("I was called from") record, and new entries are only ever added
and removed from the same end, this forms a "stack-like" data
structure: a linked list in which the "most current" end is the
"top" of the stack, and previous entries are exposed by "popping
off" that top. (The top may well be at the lowest physical or
virtual address, or there may be no defined ordering. The
latter occurs when allocating activation records from a general
storage arena, a la malloc().)
The "Next" member is a pointer to the previous function's stack frame,
"Previous" is of course a better name for this (and is the one
you used earlier). :-)
It is also true that many, perhaps even most, C compilers use a
hardware-provided stack to implement the stack-like data structure
containing the necessary activation records. These are "stack
frames". At least one compiler (for IBM machines) did historically
use a general free-store arena: there is no hardware-provided stack,
so the compiler can do whatever it likes. (As far as I know, these
systems still do this. I merely have not used them in more than
twenty years.)
It is better (in my opinion) to stick with the general term, i.e.,
"activation record", in comp.lang.c, since C compilers are not
required to use a hardware stack to implement the implied stack of
activation records. Moreover, systems that provide threads have
multiple sets of activation records, which may or may not form a
branching data structure of the sort sometimes referred to as a
"cactus stack". (You should think of a saguaro cactus here, the
stereotypical ones seen in Road-Runner-and-Coyote cartoons.) Of
course, A C implementation need not even use actual activation
records -- for instance, a magic one might use Divine Inspiration
to produce the correct results -- but it must behave *as if* it
used them. It does not, however, have to behave as though these
were allocated from a single hardware-provided stack, which is
good news for those that support threads.
You also mentioned VLAs (which are new in C99) here, and I have
a few more notes to make about this and your other extra notes:
A function uses registers to do its calculations.
Most (I think; certainly at least "many") do. Not all, though.
The AT&T "Hobbit" architecture, for instance, had no registers of
that sort at all. Instead, it used "top of stack" for everything.
As a simplified example, if you wanted to add "x" and "y", instead
of loading the values into registers and doing an "add r1, r2",
you would push the values of x and y and then do an "add", which
pops the two top values from the value stack, adds them, and pushes
the result on the stack. Some Forth-oriented hardware does this
as well.
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.
One nice thing about stack-oriented architectures is that, since
there are no registers, there is never any need to save and
restore them. (Register-oriented hardware seems to have won the
CPU speed wars rather decisively, though. As we all know, the
most important thing for any computer is *how fast* it is, not
whether it gets the right answers. :-) )
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.
Indeed, an alloca() that adjusts the stack pointer wreaks havoc on
systems that use a hardware-provided stack and have a clever (but
not super-smart) compiler, since the clever compiler assumes that
only *it* ever does this stack-pointer adjustment. This is why
one *cannot* write this kind of alloca() with some compilers on
some machines -- which is, in turn, a reason (perhaps "the" reason)
why alloca() is not in Standard C: the guys writing the C standard
were aware of this problem. Instead, C99 provides "variable length
arrays":
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.
Unlike alloca(), however, VLAs use special syntax. (A call to the
alloca() function looks like, and indeed sometimes is[%], an ordinary
function call.) By using special syntax, VLAs *force* the compiler
to participate in their creation. This participation means that
the compiler "knows" that the (hardware-provided) stack has been
altered at the point the VLA's storage is allocated, and can take
whatever actions are required to make it work. (This can be as
simple as allocating a "variable size stack frame" instead of a
"fixed size stack frame", along with all the consequences that go
with this: on MIPS machines, for instance, one marks the difference
in the debug table that goes with the binary, and uses a hardware
register as a frame pointer instead of using a "virtual" frame
pointer.)
[% I say "sometimes is" because some overly-clever compilers -- gcc
being one example -- will replace what *looks like* a call to
alloca() with appropriate machine code. This even goes as far
as switching from fixed-size to variable-size frames on machines
like the MIPS. In other words, "calling" alloca() does nothing
of the sort, and makes the compiler do the same work as for a
VLA.]
There is a subtle difference between "alloca-allocated storage"
and "VLA-allocated storage", in that the latter obeys block scope
rules:
void f(void) {
size_t size;
char *p;
for (size = 100; size < 10000; size++) {
char space[size];
... more code, possibly setting p = &space[i] ...
}
}
The function f() needs about 10 kbytes of space for its activation
record, since the largest the VLA named "space" will be is 10000.
However:
void g(void) {
size_t size;
char *p;
for (size = 100; size < 10000; size++) {
char *space = alloca(size);
... more code, possibly setting p = &space[i] ...
}
needs about 50 gigabytes (!), because each allocation must persist
for the duration of function g(). After the first iteration of
the loop in f(), the 100-element VLA named "space" is released
before the 101-element VLA named "space" is created (in the second
iteration of the loop); but in g(), the 100-element area allocated
by the first "call" to the alloca() pseduo-function must persist
when the 101-element area is allocated; both of those persist when
the 102-element area is allocated; and so on. (This matters if
you keep pointers to the "previous instance" around, e.g., if p[i]
might refer to a previous loop iteration.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
.
- Follow-Ups:
- Re: What is a stack frame?
- From: Keith Thompson
- Re: What is a stack frame?
- References:
- What is a stack frame?
- From: jacob navia
- What is a stack frame?
- Prev by Date: Re: ANN: Call for Participation - Code Generation 2008
- Next by Date: Re: Freeing memory - will it be available immediately
- Previous by thread: Re: What is a stack frame?
- Next by thread: Re: What is a stack frame?
- Index(es):
Relevant Pages
|
|
