allocation of local variables on stack

[bahadir.balban]

Hi,

When you define varibles in the middle of your function call (C99),
such as:

if(i == 5) {
int x = 5;
int z = 2;
}

Are they allocated on the stack as they're encountered at run-time or
are they allocated before, along with the arguments and initial
variable declarations? Is a function activation record supposed to be
fixed before you start executing the function code (i.e. statements)?

If this is done at run-time, how does the (standard) compiler do it?

I have also heard about an alloca() call for allocating on the stack.
Is this a non-standard function? Is there a possibility of stack
overflow by doing this?

Thanks,
Bahadir

 

[Eric Sosman]

Hi,

When you define varibles in the middle of your function call (C99),
such as:

if(i == 5) {
int x = 5;
int z = 2;
}

Are they allocated on the stack as they're encountered at run-time or
are they allocated before, along with the arguments and initial
variable declarations?

They are allocated whenever (and wherever) the compiler
chooses. Different compilers will use different strategies;
a single compiler may use different strategies depending on
the rest of the code.

Is a function activation record supposed to be
fixed before you start executing the function code (i.e. statements)?

C does not have a "function activation record." While
a function is executing there is enough information stored
somewhere to allow it to return to its caller and perhaps to
return a value, but that's about all one can say. Again, it's
the compiler's choice about how to maintain this information,
and different compilers will do it differently.

If this is done at run-time, how does the (standard) compiler do it?

I'm not sure what you're asking -- but in any case, there
is no one standard compiler, no "reference implementation." The
language definition describes the effect of running a valid program,
but not how that effect is achieved. Almost all such matters are
left to the discretion of the implementors, so they can have the
freedom to exploit the special characteristics of the platform.

I have also heard about an alloca() call for allocating on the stack.
Is this a non-standard function? Is there a possibility of stack
overflow by doing this?

See Question 7.32 in the comp.lang.c Frequently Asked
Questions (FAQ) list

http://www.eskimo.com/~scs/C-faq/top.html

 

[Anonymous 7843]

When you define varibles in the middle of your function call (C99),
such as:

if(i == 5) {
int x = 5;
int z = 2;
}

Are they allocated on the stack as they're encountered at run-time or
are they allocated before, along with the arguments and initial
variable declarations?

It's better to program as if you didn't know or care, and in
a lot of cases simple variables like that won't even be
on the stack. They'll be optimized away or placed in registers.

With that out of the way, in my observations of a several
different machines, the stack is usually allocated all-at-once
upon entry to the function. There can be overlap though:

void func()
{
int a;

{
int b;
}
{
int c;
}
}

b and c may share a memory location, and that shared b+c memory
location is probably "allocated" on the "stack" at the same
time as a. I use scare quotes because these are implementation-specific
concepts that aren't part of C proper.

About the only time I think any of these issues would be
externally visible would be if a recursive function
used an excessive amount of stack space in a nested
statement, but the recursion occured outside of that.
Consider this incomplete code:

int func(int a)
{
if (a > 0)
{
/* non-trivial return (usually) prevents tail-recursion elimination */
return other_func(a) * func(a-1);
}
else
{
struct gigantic_struct foo[1000000];
/* perform non-trivial processing of gigantic struct array */
/* return non-trivial value after processing */
}
}

Unless the compiler was particularly clever, it might grow
the stack at an alarming rate. I'll have to try this
one out with my favorite compilers and see what happens.

 

[bahadir.balban]

When you define varibles in the middle of your function call (C99),
such as:

if(i == 5) {
int x = 5;
int z = 2;
}

Are they allocated on the stack as they're encountered at run-time or
are they allocated before, along with the arguments and initial
variable declarations?

It's better to program as if you didn't know or care, and in
a lot of cases simple variables like that won't even be
on the stack. They'll be optimized away or placed in registers.

With that out of the way, in my observations of a several
different machines, the stack is usually allocated all-at-once
upon entry to the function. There can be overlap though:

void func()
{
int a;

{
int b;
}
{
int c;
}
}

b and c may share a memory location, and that shared b+c memory
location is probably "allocated" on the "stack" at the same
time as a. I use scare quotes because these are implementation-specific
concepts that aren't part of C proper.

About the only time I think any of these issues would be
externally visible would be if a recursive function
used an excessive amount of stack space in a nested
statement, but the recursion occured outside of that.
Consider this incomplete code:

int func(int a)
{
if (a > 0)
{
/* non-trivial return (usually) prevents tail-recursion elimination */
return other_func(a) * func(a-1);
}
else
{
struct gigantic_struct foo[1000000];
/* perform non-trivial processing of gigantic struct array */
/* return non-trivial value after processing */
}
}

Unless the compiler was particularly clever, it might grow
the stack at an alarming rate. I'll have to try this
one out with my favorite compilers and see what happens.

Thanks a lot, your explanation was very helpful. I asked this because I
was also wondering what would happen when a similar situation as you
exemplified would occur. But yours emphasised it better.

I personally care for these things even if you save an array or two at
runtime. It doesn't make a big difference but it doesn't hurt to code
knowing about it. It may even help in limited stack situations.

Thanks,
Bahadir

 

[Jean-Claude Arbaut]

Le 14/06/2005 18:51, dans
(e-mail address removed),

Hi,

When you define varibles in the middle of your function call (C99),
such as:

if(i == 5) {
int x = 5;
int z = 2;
}

Are they allocated on the stack as they're encountered at run-time or
are they allocated before, along with the arguments and initial
variable declarations? Is a function activation record supposed to be
fixed before you start executing the function code (i.e. statements)?

As already stated, it's implementation dependent. On MacOSX/PowerPC, the
stack is fixed at the beginning of the function, and is not easily
changed afterwards: there is a 24 byte block at the end of the stack frame,
used by any called function. I haven't checked but probably alloca needs to
change this block. On Wintel on the other hand, the stack may be expanded
at any time.

Another interesting point (MacOSX): when a function is called, parameters
are passed by register and if needed on the caller's stack frame, so when
a function is entered, enough space must be reserved in its stack frame
for any function it calls, even if it actually don't call any: the compiler
cannot know that. And of course the stack frame must contain space for
all local variables. This makes a rather big stack frame

 

[CBFalconer]

.... snip ...

Thanks a lot, your explanation was very helpful. I asked this
because I was also wondering what would happen when a similar
situation as you exemplified would occur. But yours emphasised it
better.

I personally care for these things even if you save an array or
two at runtime. It doesn't make a big difference but it doesn't
hurt to code knowing about it. It may even help in limited stack
situations.

I'm leaping in here for two reasons. One is that you are a google
user who is using the system correctly, with adequate quotes etc.
So it IS possible. Congratulations, and it shows that we should
not automatically killfile all google users.

The other is the generic problem of off-topicness. This whole
thread is off-topic, yet where is the newbie to go? [1] We who
have been around for <mumble> [2] years have a pretty good idea of
how things are implemented, or have done the implementation. As a
result we have a fair idea of why the standard imposes, or doesn't
impose, things in various areas. This knowledge is not system or
language or machine specific until it is applied to one specific
situation. One example is stacks. The IBM 360 family doesn't have
them. Yet it can implement automatic storage. Almost everything
that grew out of the PDP11, VAX, x86, 68xxx, etc. has stack
capabilities.

There was a time when all programming, to all practical purposes,
was done in assembly. As languages and their implementations
improved assembly grew less and less important, EXCEPT to the
implementors. Nowadays we can even restrict that EXCEPT to the
implementors of the final code generators. But the assembly
features are built to facilitate the high level language
implementation, and the implementations are skewed to use the
existing machine features, etc. There is no really sharp
demarcation point. We're here because there's beer because we're
here.

I've been around here for a while, so I'll probably get away with
this without excessive bitching. You, on the other hand, would
most likely have been yelled at for a similar post. And that may
be quite proper, in that I think I have demonstrated that I have a
fairly good idea of what I am talking about, and you haven't. As
yet. In time, you may.

[1] Not comp.programming, that deals with algorithms etc. Not
comp.os.*, those deal with particular systems. Not
comp.compilers.*, because the users need the knowledge. We need
comp.misc. Maybe it exists? But even if it does, it probably
doesn't have much traffic.

[2] <grumble>

 

[Russell Shaw]

It's better to program as if you didn't know or care, and in
a lot of cases simple variables like that won't even be
on the stack. They'll be optimized away or placed in registers.

With that out of the way, in my observations of a several
different machines, the stack is usually allocated all-at-once
upon entry to the function. There can be overlap though:

void func()
{
int a;

{
int b;
}
{
int c;
}
}

b and c may share a memory location, and that shared b+c memory
location is probably "allocated" on the "stack" at the same
time as a. I use scare quotes because these are implementation-specific
concepts that aren't part of C proper.

About the only time I think any of these issues would be
externally visible would be if a recursive function
used an excessive amount of stack space in a nested
statement, but the recursion occured outside of that.
Consider this incomplete code:

....

Sometimes you don't know how much data you're going to read, so you
just have to plonk stuff on the stack regardless:

char* getfile(FILE *infile)
{
size_t i = 0;
char myarray[0];

while(!feof(infile)) {
myarray[i++] = fgetc(infile);
}

alloca(i);

char *buf = malloc(i);
memcpy(buf, myarray, i);
return buf;
}

Portability is all well and good, but i just wouldn't want to use a machine
that has no storage as easy to use as a stack. Without the stack, you'd have
to use expensive reallocs.

 

[Russell Shaw]

It's better to program as if you didn't know or care, and in
a lot of cases simple variables like that won't even be
on the stack. They'll be optimized away or placed in registers.

With that out of the way, in my observations of a several
different machines, the stack is usually allocated all-at-once upon
entry to the function. There can be overlap though:

void func()
{
int a;
{
int b;
}
{
int c;
}
}

b and c may share a memory location, and that shared b+c memory
location is probably "allocated" on the "stack" at the same
time as a. I use scare quotes because these are implementation-specific
concepts that aren't part of C proper.

About the only time I think any of these issues would be
externally visible would be if a recursive function
used an excessive amount of stack space in a nested
statement, but the recursion occured outside of that.
Consider this incomplete code:

...

Sometimes you don't know how much data you're going to read, so you
just have to plonk stuff on the stack regardless:

char* getfile(FILE *infile)
{
size_t i = 0;
char myarray[0];

while(!feof(infile)) {
myarray[i++] = fgetc(infile);
}

alloca(i);

char *buf = malloc(i);
Correction:

memcpy(buf, myarray, i);

memcpy(buf, myarray + i + 1, myarray);

 

[Russell Shaw]

It's better to program as if you didn't know or care, and in
a lot of cases simple variables like that won't even be
on the stack. They'll be optimized away or placed in registers.

With that out of the way, in my observations of a several
different machines, the stack is usually allocated all-at-once upon
entry to the function. There can be overlap though:

void func()
{
int a;
{
int b;
}
{
int c;
}
}

b and c may share a memory location, and that shared b+c memory
location is probably "allocated" on the "stack" at the same
time as a. I use scare quotes because these are implementation-specific
concepts that aren't part of C proper.

About the only time I think any of these issues would be
externally visible would be if a recursive function
used an excessive amount of stack space in a nested
statement, but the recursion occured outside of that.
Consider this incomplete code:

...

Sometimes you don't know how much data you're going to read, so you
just have to plonk stuff on the stack regardless:

char* getfile(FILE *infile)
{
size_t i = 0;
char myarray[0];

while(!feof(infile)) {
myarray[i++] = fgetc(infile);
}

alloca(i);

char *buf = malloc(i);
Correction(2):

memcpy(buf, myarray, i);

memcpy(buf, myarray + i + 1, i);

 

[Keith Thompson]

Sometimes you don't know how much data you're going to read, so you
just have to plonk stuff on the stack regardless:

char* getfile(FILE *infile)
{
size_t i = 0;
char myarray[0];

while(!feof(infile)) {
myarray[i++] = fgetc(infile);
}

alloca(i);

char *buf = malloc(i);
memcpy(buf, myarray, i);
return buf;
}

Portability is all well and good, but i just wouldn't want to use a machine
that has no storage as easy to use as a stack. Without the stack, you'd have
to use expensive reallocs.

Sorry, but that's just ugly. Apart from the misuse of feof() (you
should be checking whether fgetc() returned EOF), and the constraint
violation of declaring a zero-length array, you're assuming that the
space beyond myarray is "above" the top of the stack. Even assuming a
stack-based implementation, I can imagine the unallocated space you're
using being clobbered by an interrupt. (I don't even want to think
about what might happen in a multi-threading environment.)

There are functions available that will read a line of arbitrary
length from an input file, allocating it on the heap and expanding
with realloc() as necessary. If can be done portably, there's no
need, and no excuse, for code like the above.

 

[Russell Shaw]

Sometimes you don't know how much data you're going to read, so you
just have to plonk stuff on the stack regardless:

char* getfile(FILE *infile)
{
size_t i = 0;
char myarray[0];

while(!feof(infile)) {
myarray[i++] = fgetc(infile);
}

alloca(i);

char *buf = malloc(i);
memcpy(buf, myarray, i);
return buf;
}

Portability is all well and good, but i just wouldn't want to use a machine
that has no storage as easy to use as a stack. Without the stack, you'd have
to use expensive reallocs.

Sorry, but that's just ugly. Apart from the misuse of feof() (you
should be checking whether fgetc() returned EOF), and the constraint
violation of declaring a zero-length array, you're assuming that the
space beyond myarray is "above" the top of the stack. Even assuming a
stack-based implementation, I can imagine the unallocated space you're
using being clobbered by an interrupt. (I don't even want to think
about what might happen in a multi-threading environment.)

There are functions available that will read a line of arbitrary
length from an input file, allocating it on the heap and expanding
with realloc() as necessary. If can be done portably, there's no
need, and no excuse, for code like the above.

How about:

char* getfile(FILE *infile)
{
size_t i = 0;

while(!feof(infile)) {
char *ptr = alloca(sizeof(char));
*ptr = fgetc(infile);
if(*ptr == EOF) {
return NULL;
}
}

char *buf = malloc(i);
memcpy(buf, ptr, i);
return buf;
}

 

[Keith Thompson]

How about:

char* getfile(FILE *infile)
{
size_t i = 0;

while(!feof(infile)) {
char *ptr = alloca(sizeof(char));
*ptr = fgetc(infile);
if(*ptr == EOF) {
return NULL;
}
}

char *buf = malloc(i);
memcpy(buf, ptr, i);
return buf;
}

Even funnier.

 

[Richard Bos]

Another interesting point (MacOSX): when a function is called, parameters
are passed by register and if needed on the caller's stack frame, so when
a function is entered, enough space must be reserved in its stack frame
for any function it calls, even if it actually don't call any: the compiler
cannot know that. And of course the stack frame must contain space for
all local variables. This makes a rather big stack frame

C allows for (indirectly, so not necessarily detectably) recursive
function calls. Have fun trying to allocate an infinite stack frame.

Richard

 

[Russell Shaw]

C allows for (indirectly, so not necessarily detectably) recursive
function calls. Have fun trying to allocate an infinite stack frame.

Richard

Stack usage is only infinite if the recursion never ends, which usually
means broken code. Anyway, you can always make sure tail-call optimization
is used in which case only the space of one frame is used.

 

[Russell Shaw]

Even funnier.

I always run stuff thru gdb unless it's posted here. Of course the stack
is unwound on exit from the local context

char* getfile(FILE *infile)
{
size_t i = 0;

while(1) {
char *ptr = alloca(sizeof(char));
*ptr = fgetc(infile);
if(*ptr == EOF) {
char *buf = malloc(i);
memcpy(buf, ptr, i);
return buf;
}
i++;
}
}

I more frequently return stuff directly on the stack than with
malloc.

 

[Jean-Claude Arbaut]

Le 15/06/2005 08:27, dans (e-mail address removed), « Russell

How about:

char* getfile(FILE *infile)
{
size_t i = 0;

while(!feof(infile)) {
char *ptr = alloca(sizeof(char));
*ptr = fgetc(infile);
if(*ptr == EOF) {
return NULL;
}
}

char *buf = malloc(i);
memcpy(buf, ptr, i);
return buf;
}

It may work on your machine, as your preceding post, but
on any other, you have no guarantee alloca creates contiguous
blocks, and in correct order. Depending on your application,
it may or may not be a problem.

Another point: in your preceding post you use "myarray[i++]=..."
so the stack would be growing from low to high addresses, and
in the end you use memcpy with "myarray+i+1", why ?
In this post it's the opposite: if it works, ptr must be the
lower address of you "alloca-ted" block, so stack grows
from high addresses to low addresses.

And BTW, I would replace "while(!feof(infile))" with "for(;".

Not so ugly after all, but bear in mind it's highly non-portable.

 

[Jean-Claude Arbaut]

Le 15/06/2005 10:19, dans (e-mail address removed)4all.nl, « Richard Bos »

C allows for (indirectly, so not necessarily detectably) recursive
function calls. Have fun trying to allocate an infinite stack frame.

Richard

Not infinite: one stack frame for each call. The total amount of stack used
is potentially infinite but function calls *are* finite, that's what
matters. And in case you're interested, stack may be up to 64MiB.

 

[Russell Shaw]

Le 15/06/2005 08:27, dans (e-mail address removed), « Russell



It may work on your machine, as your preceding post, but
on any other, you have no guarantee alloca creates contiguous
blocks, and in correct order. Depending on your application,
it may or may not be a problem.

man alloca (on linux) says it just moves the stack pointer.
The above function is garbage, which is usually the case
before i've tested it. ptr is declared inside the loop (should
be outside). And if(*ptr == EOF) is redundant (i was thinking of
if(*ptr == -1), but that doesn't happen for fgetc()).

Another point: in your preceding post you use "myarray[i++]=..."
so the stack would be growing from low to high addresses, and
in the end you use memcpy with "myarray+i+1", why ?
In this post it's the opposite: if it works, ptr must be the
lower address of you "alloca-ted" block, so stack grows
from high addresses to low addresses.

I got totally confused because i was doing things with alloca
in a memory allocator i wrote a week ago, that needed things
reversed because the stack grows downwards and the heap upwards.
The allocator works now, and does hierarchial garbage collection
(without using alloca).

And BTW, I would replace "while(!feof(infile))" with "for(;".

Not so ugly after all, but bear in mind it's highly non-portable.

Wasn't the best example.

 

[Jean-Claude Arbaut]

Le 15/06/2005 13:07, dans (e-mail address removed), « Russell

man alloca (on linux) says it just moves the stack pointer.

On (your) Linux, probably. But there may be many things between the
stack pointer and your local variable, including other local variables,
(and maybe saved registers, or a block of special data needed for
stack mainenance) and it's not clear *where* alloca leaves space.
You can only refer to the address returned by alloca, but of course
if you know how it runs on your machine and don't care of portability,
it's perfect.

 

[pete]

Keith Thompson wrote:

char *ptr = alloca(sizeof(char));
*ptr = fgetc(infile);
if(*ptr == EOF) {

If char is an unsigned type, then there's no way that
*ptr can equal EOF.

And I would just like to say that heaps and stacks
as they have been discussed in this thread,
have nothing to do with C are off topic for the newsgroup.