Some stack questions
Bill Case
First time on this list; Second time through K&R2. Missed a lot the
first time through so I am trying to do it right this time.
Can someone explain to me how C uses the stack. I am looking for an
explanation that lets me see in my "mind's eye" what is happening when I
program different simple events.
I hope I have come to the right user group for this type of question,
but I can find no other that seems appropriate.
I am using a desktop P4 with a Linux 2.6 kernel and a gcc compiler.
The questions I have are things like:
1) When does the stack get created? At the start of a program? At
main()?
2) When a C program is being executed is it entirely within a stack,
or are parts of it in other parts of memory?
3) Stack frames are just sub-stacks within the program's stack.
Is that correct? Or do new stacks always get created for new
functions etc?
4) Where do expressions get evaluated? Completely within the cpu
using registers for temporary storage or back and forth to the
stack?
5) If back and forth, do expressions create there own stack frame
during evaluation or are the moved on and off the top of the stack
frame being used by a function?
6) Is the address revealed by gdb or printf("%p", *x) always a stack
address or could it be an address someplace else in memory?
7) In the context of using the stack, what's a 'statement' in C?
And, how does it differ from a to-be-evaluated expression?
8) What does the statement semi-colon ';' actually tell the compiler
to do? I assume that the semi-colon is an instruction of some kind
and not just a syntactical nicety for the benefit of the programmer.
9) Are the parentheses in functions special instructions to the
compiler in the context of using the stack, or are they simply used to
identify a name as a function to the compiler?, the executable
program?
10) If they are simply identifiers, why are they used in for() while()
and if()? For() while() and if() are not functions, are they?
Parentheses are used in expressions to set aside part of the
expression so that that part of the expression can be evaluated
first. Do parentheses tell the compiler to set aside space in
the stack for the function's stack frame?
--
comp.lang.c.moderated - moderation address: cl...@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.
Douglas A. Gwyn
> 1) When does the stack get created? At the start of a program? At
> main()?
I'll give generic answers, rather than specifics for
one compiler etc.
The stack has storage allocated for it before main
is called. On some platforms, virtual memory is
used and the stack grows (gets more physical memory)
as it needs the space, usually on a function call.
On others, there is a fixed region allocated at link
time, and you need to be careful not to use too many
large auto variables so that you don't overflow the
allocation.
When your program starts, it doesn't actually start
at main, but rather at the beginning of some "run-
time start-off module" that is linked into it from
the C library. It is that run-time start=off module
that sets up the environment, including stack, so
that the rest of the program will work. Then it
invokes the equivalent of exit(main(argc,argv));.
> 2) When a C program is being executed is it entirely within a stack,
> or are parts of it in other parts of memory?
Although systems vary slightly, there are different
memory regions used in different ways, including:
heap (malloc/realloc/free dynamic memory pool),
stack (auto variables and dynamic function linkage),
constant data ("const"-qualified objects and maybe
string literals), initialized variable data
(modifiable variables with specified initial values),
uninitialized variable data (usually set to all zero
bytes values by the run-time start-off module), and
constant program text (machine instructions).
> 3) Stack frames are just sub-stacks within the program's stack.
> Is that correct? Or do new stacks always get created for new
> functions etc?
Typically there is just a single stack, and when a
function is called the "stack pointer" register is
changed to point to a different area of the stack.
Information needed to restore the calling function's
context (including *its* stack pointer value) is
part of what is saved on the stack, and the function
arguments are also stored on the stack (except in
cases where the values are passed in fast registers);
further, space is reserved on the stack for all
variables having "auto" storage class for that
specific invocation of the function. (Thus, "int a"
in one invocation of foo() is likely to use a
different word of (stack) storage than the same
variable in a different invocation of foo().) There
is sometimes a register used as a "frame pointer" in
addition to the one used as a stack pointer, but not
every implementation does that and you don't need to
understand it at this level.
> 4) Where do expressions get evaluated? Completely within the cpu
> using registers for temporary storage or back and forth to the
> stack?
Both. On a register-starved architecture like the
Intel x86, not much can be computed without using
temporary storage (which will be in the stack frame).
On better designed architectures, the compiler
allocates registers efficiently so that most
operations are done without using temp storage.
> 5) If back and forth, do expressions create there own stack frame
> during evaluation or are the moved on and off the top of the stack
> frame being used by a function?
Usually, a certain amount of the stack frame is
set aside for temp storage and the compiler uses
it without changing the stack pointer.
> 6) Is the address revealed by gdb or printf("%p", *x) always a stack
> address or could it be an address someplace else in memory?
I think you meant &x.
If the address is of an object allocated with "auto"
storage class or of one of the function parameters,
then it is within the stack frame. Otherwise, it is
elsewhere (as described previously).
> 7) In the context of using the stack, what's a 'statement' in C?
> And, how does it differ from a to-be-evaluated expression?
Statements have little to do with the stack as such.
They declare variables or specify actions. One form
of statement is an expression statement" which just
evaluates an expression. Since expressions can have
side effects (such as for the ++ or = operators, or
an I/O function), evaluating an expression is not
necessarily a waste of time.
> 8) What does the statement semi-colon ';' actually tell the compiler
> to do? I assume that the semi-colon is an instruction of some kind
> and not just a syntactical nicety for the benefit of the programmer.
No, the semicolon is part of the syntax and has no
operational meaning. A "null statement" has nothing
before the semicolon, and simply does nothing; it is
sometimes useful as a placeholder:
while ((*p = *q) != 0) // copy done here
; // nothing left to do here
> 9) Are the parentheses in functions special instructions to the
> compiler in the context of using the stack, or are they simply used to
> identify a name as a function to the compiler?, the executable
> program?
Parentheses are part of the syntax, and allow the
compiler to more easily isolate the specified
arguments. They have no meaning in themselves.
If you see a function declared with empty
parentheses, that means that its arguments are
being left unspecified; this was common in C
before the C standard and has an occasional good
use even today, but is not worth worrying about
at this stage.
> 10) If they are simply identifiers, why are they used in for() while()
> and if()? For() while() and if() are not functions, are they?
No, they are (part of) special kinds of statements;
the parentheses are again just part of the syntax
and help the compiler analyze the source program.
Some other languages have different syntax, e.g.:
IF condition THEN statements ENDIF
> Parentheses are used in expressions to set aside part of the
> expression so that that part of the expression can be evaluated
> first. Do parentheses tell the compiler to set aside space in
> the stack for the function's stack frame?
No. You're talking about "grouping" for purposes
of evaluation.
Generally speaking, the stack frame is adjusted
just once upon entry to a function invocation, and
is not adjusted again until either another function
call or return. Evaluation of statements within
the function uses general registers, storage outside
the stack frame (non-auto variables), and storage in
the stack frame (auto variables). (Pointers as
arguments or in accessible global variables allow
you to access essentially any storage that it makes
sense to access, and alas even storage that doesn't
make sense to access, if you're careless.)
Hans-Bernhard Broeker
> Can someone explain to me how C uses the stack.
It doesn't. There's no mention of "the" stack in the language
definition. The nesting of function calls and the handling of
function arguments behaves like the abstract data type called a
"stack", but that's by not to say that "the" stack of a given hardware
platform has to be used for this purpose.
As to the remaining questions: answers to those won't help you
understand C. They'll only help you understand how to implement a C
compilation toolchain. Which, at the moment, is not something you
should be worrying yourself about.
There's is such a thing as knowing too much (and mostly the wrong
things), and you're on a direct path towards that state.
--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Keith Thompson
[...]
A lot of your questions are implementation-specific, things not
addressed by the standard. A compiler (more generally, an
implementation) is required to implement the visible semantics
described by your program in accordance with the language definition.
How it does this is largely up to the implementer.
In most cases, you don't really need to know the details. They're
going to vary from one implementation to another. Ideally, your
mental model of what's going on in a program should be on a more
abstract level.
That's not to say that it's not useful to know the details for a given
implementation; it can be useful, for example, to be able to look at
an address (in the debugger or printed with 'printf("%p", ...)') and
know that it looks "wrong". But any such knowledge isn't going to be
portable, and neither will any program that depends on it.
> 1) When does the stack get created? At the start of a program? At
> main()?
Local variables for functions are allocated and deallocated in a
stack-like (last-in first-out) manner that supports recursion. This
is often implemented using a linear hardware "stack", e.g, with CPU
register that points to the "top" of the stack and is adjusted as
memory is allocated and deallocated. But as long as the semantics are
satisfied (variables exist when they need to), this isn't required.
An implementation could allocate "stack frames" from the heap and use
explicit calls to allocate and deallocate them on function entry and
exit.
> 2) When a C program is being executed is it entirely within a stack,
> or are parts of it in other parts of memory?
One common scheme is to allocate local variables on the "stack", use
another region of memory called the "heap" for malloc() and free(),
and a chunk of memory allocated at or before program startup for
global and static variables. There could be a separate region for
global and static variables whose values are constant and/or whose
initial values can be determined at compile time. Program code might
be allocated somewhere else, or even burned into ROM on an embedded
system. Some variables, particularly function parameters, can be
stored in CPU registers rather than in memory.
There are just examples of how *some* implementations handle these
things.
> 3) Stack frames are just sub-stacks within the program's stack.
> Is that correct? Or do new stacks always get created for new
> functions etc?
That's not really a meaningful question. An implementation that uses
a linear stack will typically allocate stack frames within that single
stack, but the language definition doesn't talk about stacks or stack
frames.
> 4) Where do expressions get evaluated? Completely within the cpu
> using registers for temporary storage or back and forth to the
> stack?
It depends.
> 5) If back and forth, do expressions create there own stack frame
> during evaluation or are the moved on and off the top of the stack
> frame being used by a function?
It depends.
> 6) Is the address revealed by gdb or printf("%p", *x) always a stack
> address or could it be an address someplace else in memory?
Do you mean printf("%p", &x), or is x a pointer-to-pointer?
It's going to be the address of whatever thing you're printing the
address of. It could be in any of a number of system-specific places.
> 7) In the context of using the stack, what's a 'statement' in C?
> And, how does it differ from a to-be-evaluated expression?
There are several kinds of statements in C; each one does whatever the
language says it does. Any interaction with the stack is
system-specific. A statement is executed; an expression is evaluated
and yields a value. One kind of statement is an "expression
statement", which evaluates the statement (and discards any result);
it consists of an expression followed by a semicolon.
> 8) What does the statement semi-colon ';' actually tell the compiler
> to do? I assume that the semi-colon is an instruction of some kind
> and not just a syntactical nicety for the benefit of the programmer.
The semicolon is just a syntactic marker; it doesn't specify any action.
> 9) Are the parentheses in functions special instructions to the
> compiler in the context of using the stack, or are they simply used to
> identify a name as a function to the compiler?, the executable
> program?
Parentheses in function calls are just syntactic markers; they don't
specify any action.
> 10) If they are simply identifiers, why are they used in for() while()
> and if()? For() while() and if() are not functions, are they?
> Parentheses are used in expressions to set aside part of the
> expression so that that part of the expression can be evaluated
> first. Do parentheses tell the compiler to set aside space in
> the stack for the function's stack frame?
No, for(), while(), and if() are not functions. Parentheses are used
for a number of different things, including expression grouping, as in
(2+3)*4. In all cases, the parentheses are just part of the syntax of
the construct in which they appear. The compiler has to analyze the
entire construct to process it.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Barry Schwarz
wrote:
>Hi;
>
>First time on this list; Second time through K&R2. Missed a lot the
>first time through so I am trying to do it right this time.
>
>Can someone explain to me how C uses the stack. I am looking for an
>explanation that lets me see in my "mind's eye" what is happening when I
>program different simple events.
The C standard does not require a stack. C is implemented on machines
which do not have stacks.
>
>I hope I have come to the right user group for this type of question,
>but I can find no other that seems appropriate.
If your compiler uses a stack, then the correct place to ask would be
a group that discusses that compiler.
>
>I am using a desktop P4 with a Linux 2.6 kernel and a gcc compiler.
>
>The questions I have are things like:
>
>1) When does the stack get created? At the start of a program? At
>main()?
See above.
>
>2) When a C program is being executed is it entirely within a stack,
>or are parts of it in other parts of memory?
Ditto.
>
>3) Stack frames are just sub-stacks within the program's stack.
>Is that correct? Or do new stacks always get created for new
>functions etc?
Ditto.
>
>4) Where do expressions get evaluated? Completely within the cpu
>using registers for temporary storage or back and forth to the
>stack?
Ditto.
>
>5) If back and forth, do expressions create there own stack frame
>during evaluation or are the moved on and off the top of the stack
>frame being used by a function?
Ditto.
>
>6) Is the address revealed by gdb or printf("%p", *x) always a stack
>address or could it be an address someplace else in memory?
This most likely invokes undefined behavior. The argument
corresponding to the %p MUST be a void*. Unless x is of type void**,
this is not the case.
In general, it is possible for a pointer to point almost anywhere
within the memory available to your program.
>
>7) In the context of using the stack, what's a 'statement' in C?
>And, how does it differ from a to-be-evaluated expression?
The concept of a stack has no significance to the question.
>
>8) What does the statement semi-colon ';' actually tell the compiler
>to do? I assume that the semi-colon is an instruction of some kind
>and not just a syntactical nicety for the benefit of the programmer.
It is a null statement, telling the compiler there is no need to
generate any code. The semi-colon is the normal statement terminator.
>
>9) Are the parentheses in functions special instructions to the
>compiler in the context of using the stack, or are they simply used to
>identify a name as a function to the compiler?, the executable
>program?
The concept of a stack has no significance to the question. The
parentheses in a function call serve to group the arguments being
passed to the function. In a function declaration or definition, they
perform a similar function for the parameters.
>
>10) If they are simply identifiers, why are they used in for() while()
>and if()? For() while() and if() are not functions, are they?
No, the are not functions. There is no For, only for.
>Parentheses are used in expressions to set aside part of the
>expression so that that part of the expression can be evaluated
>first. Do parentheses tell the compiler to set aside space in
The order of evaluation is unspecified for most expressions. Since
there is a sequence point before a function is called, you are
guaranteed that the arguments are evaluated prior to the call.
>the stack for the function's stack frame?
The concept of a stack has no significance to the question.
Parentheses have nothing to do with setting aside space.
<<Remove the del for email>>
Dag-Erling Smørgrav
> Can someone explain to me how C uses the stack.
The C language does not assume the existence of a stack.
> The questions I have are things like:
The answers to your homework are to be found in your textbook.
DES
--
Dag-Erling Smørgrav - d...@des.no
Old Wolf
>
> Can someone explain to me how C uses the stack. I am looking for an
> explanation that lets me see in my "mind's eye" what is happening when I
> program different simple events.
>
I would suggest asking in gnu.gcc.help .
Most of your questions are things that are specific to your system
and may be different on other systems. For example, some systems
don't even have a stack. Some systems have one stack, some have
more than one.
However some of your questions can be answered here:
>
> 4) Where do expressions get evaluated? Completely within the cpu
> using registers for temporary storage or back and forth to the
> stack?
If a temporary variable can't fit in a register then the
compiler will use some storage somewhere for it. I can't
think of any situations in C where this would actually happen,
though.
> 6) Is the address revealed by gdb or printf("%p", *x) always a stack
> address or could it be an address someplace else in memory?
Typically, if *x is a pointer to a stack variable, it will
be a stack address, otherwise it won't.
For example, static variables are usually not stored on the stack.
Note: you should cast the parameter of %p to (void *), and I
suspect you meant &x rather than *x .
> 7) In the context of using the stack, what's a 'statement' in C?
> And, how does it differ from a to-be-evaluated expression?
A statement is either a declaration, or an expression followed
by a semicolon. This is unrelated to the stack.
> 8) What does the statement semi-colon ';' actually tell the compiler
> to do? I assume that the semi-colon is an instruction of some kind
> and not just a syntactical nicety for the benefit of the programmer.
It is in fact a syntactical element. It indicates the end of a
statement. (With some special cases, eg. the control expressions
in a for-loop).
> 9) Are the parentheses in functions special instructions to the
> compiler in the context of using the stack, or are they simply used to
> identify a name as a function to the compiler?, the executable
> program?
The parentheses introduce a function's argument list. C's syntax
specifies that a name followed by an argument list, represents a
function call. Again this is nothing to do with the stack.
The stack may or may not be used as a location for storing
function parameters for the duration of the call; but this
issue is independent of syntax.
> 10) If they are simply identifiers, why are they used in for()
> while() and if()?
Well, why not? The C language designers thought that brackets were
an appropriate way to delimit the control expressions in for(),
while() and if().
> For() while() and if() are not functions, are they?
No, they aren't, because "for", "while" and "if" are reserved words,
so they do not fall into the same syntax rules as WHATEVER() would.
> Parentheses are used in expressions to set aside part of the
> expression so that that part of the expression can be evaluated
> first.
Note that parentheses control precedence, not order-of-evaluation.
To illusrate this point: in the expressions
foo() * (bar() + 1)
the function calls could proceed in either order, as long
as the addition occurs before the multiplication. In other
words, the compiler could call foo(), remember this value,
call bar(), add 1 to that value, and then multiply by the
value it remembered earlier.
> Do parentheses tell the compiler to set aside space in
> the stack for the function's stack frame?
Again, this is nothing to do with the stack.
When there is a function call (regardless of syntax), the
compiler may or may not create a stack frame. (GCC actually
has a commandline option to disable stack frames).
It might be instructive for you to write a C program with some
of these scenarios you are unsure about, and then inspect the
assembly code that your compiler generates.
Jack Klein
> Hi;
>
> First time on this list; Second time through K&R2. Missed a lot the
> first time through so I am trying to do it right this time.
>
> Can someone explain to me how C uses the stack. I am looking for an
> explanation that lets me see in my "mind's eye" what is happening when I
> program different simple events.
The very first thing that you need to know is that C does not define,
require, or explain the concept of a stack.
Electronics engineers developing processors came up with the concept
of a stack maintained by processor hardware long before C existed. In
fact, long before 95% of the programming languages in use today
existed.
Now it just so happens that the hardware stack implementation built
into many processors today can be convenient to use in the machine
language generated by higher level language translators.
> I hope I have come to the right user group for this type of question,
> but I can find no other that seems appropriate.
Actually, this is not really the correct group for this. The fact
that C implementations on many platforms happen to make use of stack
maintaining hardware features on the underlying processor is a detail
of how the compiler implements a C program. C does not define this,
it only defines what the results of a correct program will be, not how
those results are achieved.
> I am using a desktop P4 with a Linux 2.6 kernel and a gcc compiler.
If the processor, compiler, and operating system you are using are
important to your question, it is not a language question, but one
that belongs in a more specialized group.
One good source for you to understand how things work with a Pentium
under Linux is news:comp.os.linux.development.apps.
The best source for understanding the hardware features of the 32-bit
x86 architecture is to go to http://developer.intel.com. You can
download the complete manuals for the processors, which explain all
the memory-management hardware features and how they are typically
used by programs, including C programs.
> The questions I have are things like:
>
> 1) When does the stack get created? At the start of a program? At
> main()?
Stacks don't get created, they are areas of memory that must already
exist. In the common case, a register in the processor is loaded with
the highest or lowest address of a block of memory to be used as a
stack. This register is often called a 'stack pointer', but on ARM
processors, for example, it is merely called 'R15'.
On a platform that uses such a stack, this is done either by the
operating system (if there is one), or some implementation specific
start-up code that runs before main() is called, or some combination
of these two.
> 2) When a C program is being executed is it entirely within a stack,
> or are parts of it in other parts of memory?
Generally, a C program is not executed within a stack. For the
typical processor and it use of stack, none of the executable code is
associated with the stack. Indeed on some processors, memory
management features make it impossible to execute code in stack space.
> 3) Stack frames are just sub-stacks within the program's stack.
> Is that correct? Or do new stacks always get created for new
> functions etc?
There is nothing in the C standard that answers this question. But
generally there are not "sub stacks" within a stack. There are just
areas of memory.
> 4) Where do expressions get evaluated? Completely within the cpu
> using registers for temporary storage or back and forth to the
> stack?
Expressions get evaluated where the machine code generated by the
compiler directs them to. They may or may not have anything at all to
do with a stack.
> 5) If back and forth, do expressions create there own stack frame
> during evaluation or are the moved on and off the top of the stack
> frame being used by a function?
Again, beyond the scope of the C language standard. Admittedly, the
Intel x86 processors are very short on registers, compared to many
other processors, so they may have to deal with this more than some
other architectures.
> 6) Is the address revealed by gdb or printf("%p", *x) always a stack
> address or could it be an address someplace else in memory?
The address of an object is the address, within the address space of
the program, where the object is located. Whatever method of memory
management and division the implementation uses, it is the address of
some memory. If the processor has a stack and that object is on the
stack, then it is an address within the stack. If the object is not
on the stack, then it is an address not on the stack.
> 7) In the context of using the stack, what's a 'statement' in C?
> And, how does it differ from a to-be-evaluated expression?
There is no context of "using the stack" in C. The C standard defines
it like this: "A statement specifies an action to be performed."
That's it, that's the whole thing, the entire definition. Note that
it says nothing at all about a stack.
> 8) What does the statement semi-colon ';' actually tell the compiler
> to do? I assume that the semi-colon is an instruction of some kind
> and not just a syntactical nicety for the benefit of the programmer.
The ';' is a statement terminator in this context. It indicates the
end of a statement. It also generates a 'sequence point' in a
program, and this is a very important concept in C. At a 'sequence
point', all side effects of the previous statement are completed, and
no side effects of the next statement that will execute have begun.
> 9) Are the parentheses in functions special instructions to the
> compiler in the context of using the stack, or are they simply used to
> identify a name as a function to the compiler?, the executable
> program?
Again, there is no context of "using a stack" in C. The parentheses
in a function argument provide lexical markers to the compiler in
parsing the function call and its arguments.
> 10) If they are simply identifiers, why are they used in for() while()
> and if()? For() while() and if() are not functions, are they?
> Parentheses are used in expressions to set aside part of the
> expression so that that part of the expression can be evaluated
> first. Do parentheses tell the compiler to set aside space in
> the stack for the function's stack frame?
Parentheses have nothing at all to do with "stacks" or "stack frames".
C reuses various symbols to mean different things in different
contexts. Consider the '.' character in US English. It is used to
end a sentence, like this one. It is also used to signify an
abbreviation, like Dr. or Mr. And it is used as a decimal point
separator in numbers, as in 123.45. There is no confusion about what
the use of a particular '.' is in reading, due to the context.
The fact that C uses symbols like '(' and ')', '{' and '}', '.', ':',
and ';' several different ways in different contexts is often due more
to the limited number of non-alphanumeric characters available in the
limited C character set than to any similarity of use.
But if you really want to know about stacks on a platform that uses
them, first you need to understand the hardware features of the
processor that provides them. In addition to the links above,
news:comp.lang.asm.x86 is a good place to discuss this.
Do not make the mistake of thinking that "everything is a Pentium",
because that is very far from the truth.
There are some processors, especially those more generous with
registers than x86, where a function called with two or three
parameters might not use a stack at all. All parameters are passed
in, and the result returned, in processor registers. During the
function execution, the return address is not anywhere in memory, but
in a special register in the processor.
And about ten years ago I worked with a specialized processor that did
have a hardware stack, but for return addresses only. There were no
instructions to move data to or from the stack, and the stack pointer
was not addressable so you couldn't even find out where it was
pointing.
Finally, you can become an expert C programmer without ever even
thinking about hardware stacks. From the point of portability, you
will be a better C programmer if you don't.
--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
kgold
>
> Can someone explain to me how C uses the stack. I am looking for an
> explanation that lets me see in my "mind's eye" what is happening when I
> program different simple events.
We will no doubt get a flood of screaming, flaming email correctly
noting that there is nothing in C that requires a stack. So my
answers are what typically happens. I.e., prepend "Typically, but
it's up to the architecture and compiler, ..." to each sentence.
> 1) When does the stack get created? At the start of a program? At
> main()?
By the OS before main, because argc and argv are on the stack when
main is entered.
> 2) When a C program is being executed is it entirely within a stack,
> or are parts of it in other parts of memory?
The program is not on intentionally(*) the stack.
* There are attacks that try to push malicious program instructions on
the stack, and then try to overwrite the return location to cause
the return to jump to that code.
> 3) Stack frames are just sub-stacks within the program's stack.
> Is that correct? Or do new stacks always get created for new
> functions etc?
There is one stack for the program, unless you are creating new
threads. Each function call pushes arguments and the return location
on the stack, and returns pop data off the stack.
> 4) Where do expressions get evaluated? Completely within the cpu
> using registers for temporary storage or back and forth to the
> stack?
Parameters and local variables are nominally on the stack, but the
compiler can use CPU registers to optimize. Same with intermediate
expressions.
> 5) If back and forth, do expressions create there own stack frame
> during evaluation or are the moved on and off the top of the stack
> frame being used by a function?
The compiler creates additional local variables for expression
evaluation. They can be stack or register. There's just one stack
frame.
> 6) Is the address revealed by gdb or printf("%p", *x) always a stack
> address or could it be an address someplace else in memory?
It depends what x points to. It could be a local variable on the
stack, a malloced value on the heap, a static variable on a global
area, or a pointer to a function on the program space.
--
Ken Goldman kg...@watson.ibm.com 914-784-7646
CBFalconer
> Bill Case wrote:
>
With the great delays between posting and appearance on c.l.c.m
these days (which probably reflects the time available to the
moderator), there is no great point to a continued discussion.
However a thoroughly drifted thread may be sensible, thus:
>> 1) When does the stack get created? At the start of a program?
>> At main()?
>
> I'll give generic answers, rather than specifics for
> one compiler etc.
>
.... snip ...
>
>> 4) Where do expressions get evaluated? Completely within the cpu
>> using registers for temporary storage or back and forth to the
>> stack?
>
> Both. On a register-starved architecture like the Intel x86, not
> much can be computed without using temporary storage (which will
> be in the stack frame). On better designed architectures, the
> compiler allocates registers efficiently so that most operations
> are done without using temp storage.
I get rather tired of this negative attitude to the x86
architecture. Yes, it is fundamentally different than that of a
PDP11. Things are built around special purpose registers rather
than general registers. The concept of segmentation is built-in,
although hidden by the large offset ranges possible, which in turn
negates the advantage of segmentation (short addresses). I think
the architects have done a marvellous job of maintaining backward
compatibility together with extended abilities and performance.
In many ways the architecture simplifies optimizations, since some
things must go in pre-specified registers. For example it makes
immediate sense to have a policy that bp and sp must be preserved
through a functions execution. In purely general register
architecture you have to have the decision that registers n and m
will be used as stack pointer and frame pointer, and then that they
should be preserved. By the time you get to n and m the underlying
reason has been obscured.
Someone could build a slow and cheap version of an x86 and be 100%
opcode compatible. It would omit all queues, caches, speculative
execution etc, be much cheaper, but totally software compatible.
Won't happen IMO.
>
.... snip ...
>
>> 9) Are the parentheses in functions special instructions to the
>> compiler in the context of using the stack, or are they simply
>> used to identify a name as a function to the compiler?, the
>> executable program?
>
> Parentheses are part of the syntax, and allow the compiler to more
> easily isolate the specified arguments. They have no meaning in
> themselves. If you see a function declared with empty parentheses,
> that means that its arguments are being left unspecified; this was
> common in C before the C standard and has an occasional good use
> even today, but is not worth worrying about at this stage.
>
>> 10) If they are simply identifiers, why are they used in for()
>> while() and if()? For() while() and if() are not functions,
>> are they?
>
> No, they are (part of) special kinds of statements; the
> parentheses are again just part of the syntax and help the
> compiler analyze the source program. Some other languages have
? different syntax, e.g.:
> IF condition THEN statements ENDIF
Although it makes no difference to the compiler, because blanks are
normally ignored and serve only as symbol separators, I like to
differentiate functional and conditional use of parentheses. In
conditions, I always precede '(' with a blank. For functional
operations, I never use a preceding blank. This agrees with the
imposed syntax of functional macros. I consider that it adds
readability.
if (conditional) foo(bar);
--
Chuck F (cbfal...@yahoo.com) (cbfal...@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Keith Thompson
[...]
> Statements have little to do with the stack as such.
> They declare variables or specify actions.
Statements normally do not declare variables (though a compound
statement can contain variable declarations, and a for statement can
can declare its iteration variable). A variable declaration is not a
statement.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Bill Case
I want to thank the 10 people who took the time to answer a long set of
questions. I truly didn't expect such generosity with your time. My
mind is much clearer on these points plus I learned where to ask these
kinds of questions in the future.
For the record I would like to point out two things 1) it has been over 50
years since I did any "home work" or looked up the answer in the back of
the book, and 2) it is a reflection of my age I am sure, but as a look at
some of the email addresses I can never get used to the fact that I have
been helped by people from around the world.
Regards and thanks, Bill
> Hi;
>
> First time on this list; Second time through K&R2. Missed a lot the
> first time through so I am trying to do it right this time.
[snip]
Dave Thompson
> Hi;
>
> First time on this list; Second time through K&R2. Missed a lot the
> first time through so I am trying to do it right this time.
>
> Can someone explain to me how C uses the stack. I am looking for an
> explanation that lets me see in my "mind's eye" what is happening when I
> program different simple events.
>
> I hope I have come to the right user group for this type of question,
> but I can find no other that seems appropriate.
>
> I am using a desktop P4 with a Linux 2.6 kernel and a gcc compiler.
>
Caveat: the formal definition of the C language does not specify or
require anything called a stack. C, like other algol-family languages,
is designed so that it can most easily be implemented using a stack of
routine (function) activations, usually just called 'the stack', and
usually _is_ so implemented, including on your system. I will expand
below as to the common implementation and yours, but remember this is
not absolutely 100% universal for all C implementations.
> The questions I have are things like:
>
> 1) When does the stack get created? At the start of a program? At
> main()?
>
Before the beginning of main(), yes (assuming a hosted implementation;
on a freestanding implementation you may not even _have_ a main()). On
some systems including Linux (and most? other Unix) a per-process
stack region is part of the OS's process model and already exists when
your program starts; on others the startup code which is provided
automatically by the C implementation sets this up before entering
main(), as it may similarly do for other needed things like
environment variables and stdio files.
> 2) When a C program is being executed is it entirely within a stack,
> or are parts of it in other parts of memory?
>
The program itself is usually in a separate area of memory, the 'code
segment'. The data used by the program can be logically divided into
three types defined by the standard: static-duration which is
allocated at program startup (before main()) and lasts for the entire
life of the program execution; dynamic-duration which is allocated by
calling malloc() calloc() or realloc() and lasts until calling free()
or (in some cases) realloc(); and automatic-duration which is
allocated at function or block entry (or for C99 or GNU C VLA on
reaching the declaration) and lasts until function or block exit.
There are several schemes for placing (data of) these different
durations in different memory area.
For at least older Linux (this may have changed) and many if not all
Unix, static-duration data is organized at link time into a single
large area or maybe two or three allocated at process creation;
dynamic-allocation is done within an area called the 'heap' which may
start after the static area and together with it form the 'data
segment' and may be able to grow as needed during execution; and
automatic-duration is allocated, in frames as below, in the stack
which is a different area called the 'stack segment' which also may be
able to grow during execution (up to some limit).
> 3) Stack frames are just sub-stacks within the program's stack.
> Is that correct? Or do new stacks always get created for new
> functions etc?
>
Stack frames are _areas_ within "the stack". Each frame just contains
local variables and parameters (if not in registers) for one function
activation, plus associated internal information like return PC, saved
registers, unwind links and temporaries. Through C90, each stack frame
only needs to contain data of a constant size and thus can use a
layout predetermined at compile-time; in C99 and already in GNU C as
an extension you can have Variable-Length Arrays, and in GNU C and
some other implementations calls to alloca(), which make the layout of
the 'current' frame -- the one for the currently executing function,
which is necessarily the one at the top of 'the stack' -- variable.
A stack frame is created (allocated) for a function when that function
is called -- or as a possibly special case, for main() when it is
automatically called by the runtime/startup -- and deallocated when
that function _invocation_ terminates, either normally by returning
(including reaching the end of the body) or abnormally by longjmp()
(or an exception on systems which support that as an extension). Note
that there may be more than one frame corresponding to a function --
if the function calls itself or calls other(s) which call it, called
recursion (direct and indirect respectively), there is one stack
frame, and in particular a separate set of any automatic variables,
for _each_ invocation. This is the main reason it is usually easiest
and best to implement algol-family languages with a stack.
> 4) Where do expressions get evaluated? Completely within the cpu
> using registers for temporary storage or back and forth to the
> stack?
>
Either. x86 has relatively few registers (compared to some other CPUs)
so it is likely expressions that are not pretty simple will require
memory temporaries; the compiler always may use memory if it chooses.
> 5) If back and forth, do expressions create there own stack frame
> during evaluation or are the moved on and off the top of the stack
> frame being used by a function?
>
Expressions don't create their own frame -- unless the expression is
or contains a function call: that does create a new frame unless the
call is inlined, in which case it is arguably no longer really a call.
Depending on the compiler, the code for an expression may allocate and
deallocate space in the (current = top-of-stack) frame, or it may
simply use space that was allocated earlier, often at function entry.
IME gcc/x86 usually does dynamic allocation, but this may vary with
version and/or options especially optimization (-On), and certainly
may vary for other implementations.
> 6) Is the address revealed by gdb or printf("%p", *x) always a stack
> address or could it be an address someplace else in memory?
>
Do you really mean *x (x must be a pointer to pointer, or instead an
expression yielding same) or x (where x is a pointer, or instead an
expression yielding a pointer)? It could be any data address (to be
portable must be cast if not already qualified void* or possibly
qualified flavored char*) and for gcc could even be a code address
(this is not required by C, but is for the platforms gcc supports).
> 7) In the context of using the stack, what's a 'statement' in C?
> And, how does it differ from a to-be-evaluated expression?
>
You really should read the first chapter or two of a decent textbook;
this is very basic stuff.
A statement is a unit of executable code in the source, and usually
compiles into a series of consecutive instructions in the object code.
It doesn't necessarily have anything to do with the stack.
An expression is a component in many statements -- the entire body of
an expression-statement; the condition of an if, while, or do-while;
or one of three pieces of a for. (In C99, and C++, the condition of
if, while, or do-while, and the _first_ piece of a for, can instead be
a declaration, usually with an initializer, which is an expression.)
The optional initializer in a declaration may also be an expression,
except for arrays -- there are no array rvalues in C (except for a
kludge in C99 for returned struct components -- don't go there).
> 8) What does the statement semi-colon ';' actually tell the compiler
> to do? I assume that the semi-colon is an instruction of some kind
> and not just a syntactical nicety for the benefit of the programmer.
>
The semi-colon is the _terminator_ on all statements except compound
statements aka blocks; a semi-colon alone where a statement is
expected is a "null statement" which (when executed) does nothing.
Semi-colon is also (similarly) the terminator of declarations.
> 9) Are the parentheses in functions special instructions to the
> compiler in the context of using the stack, or are they simply used to
> identify a name as a function to the compiler?, the executable
> program?
>
You mean in a function _call_? They are part of the syntax. Before C99
if the function-designator is a simple name, as is most common by far
but not required, and that name is not already declared as a function,
this is an implicit declaration (i.e. identification) of the name as a
function of unspecified old-style (default-promoted) nonvariadic
arguments and returning int; this was a wart retained for historical
compatibility and you should not use it.
A function call (compiles to code which) evaluates the function
designator (often trivial) and the arguments (in unspecified order)
and then invokes the function passing the arguments. For the standard
calling sequences on x86 all arguments are passed on the stack; you
should be able to use regparm for your own unportable code only.
Parentheses in a function declaration or defintion are part of the
syntax; and in a function body may occur only as permitted for
statements and declarations and expressions within those.
> 10) If they are simply identifiers, why are they used in for() while()
> and if()? For() while() and if() are not functions, are they?
> Parentheses are used in expressions to set aside part of the
> expression so that that part of the expression can be evaluated
> first. Do parentheses tell the compiler to set aside space in
> the stack for the function's stack frame?
'for' 'while' 'if' are keywords used in constructing statements, as
are 'do' 'switch' 'case' 'default' 'break' 'continue' 'return' 'goto'.
Not 'For'; C is case sensitive. Other keywords are the builtin type
and storage-class specifiers and qualifiers used in declarations (and
casts) 'static' 'int' 'long' 'unsigned' 'float' 'const' 'struct' etc.
and the special operator 'sizeof' (and in GNU C 'typeof').
The parentheses in if() while() do-while() for(;;) switch() are just
part of the syntax; these could have been done differently (and are in
other languages) but weren't. Parentheses in a function call are
similarly part of the syntax, but could not as easily have been done
differently and aren't in most other languages. The execution of a
function call does allocate a new stack frame for that function,
unless inlined, but not the parentheses as such. (Other) parentheses
within an expression control 'precedence', that is which operators
apply to which operands, but do not entirely control sequence.
In (a+3)*(b+4)-f(c) a+3 are added before the multiplication is done,
as are b+4, but a+3 may be done before or after or even during b+4 and
both of them before or after f(c) and f(c) may be done before or after
the multiplication but before the subtraction.
- David.Thompson1 at worldnet.att.net