Recovering from out of memory on the stack

[jacob navia]

jacob navia wrote, On 10/01/08 20:27:

Of course, if you do not call main recursively the compiler might decide
to allocate foo where it allocates "global" variables. I can see reasons
why this optimisation might make sense.

You are daydreaming.
I bet you can't name a single compiler that does that kind of nonsense!

Of course, if the stack grows in the opposite direction (as it does on
the PowerPC) it could give very unexpected results.

And the fix is to take the absolute value... We are interested in the
distance.

Not to mention on
embedded compilers which people have posted about as recently as this
week that do things like allocating *all* local variables statically.

Who cares?

We are speaking about STACK OVERFLOW here, so those compilers are
OFF TOPIC for this thread.

However you have no way of knowing (in general) what limit you need to
test against, so it does not help you.

Of course you know, and if you don't you can measure it with a program
like the above one.

#include <stdio.h>
char *StartOfStack;
int main(int argc,char *argv[])
{
char foo,*p;
char m[8192*16];
if (argc > 0)
p = StartOfStack = &foo;
else
p = &foo;
printf("Stack %d\n",StartOfStack-p);
main(0,NULL);
// Not reached
}

Output:
Stack 0
Stack 131100
Stack 262200
Stack 393300
Stack 524400
Stack 655500
Stack 786600

You can adjust the size of the array to make more finer measures.

Apart from PowerPC and related processors (because you have the stack
direction wrong), so it won't work on big iron (or even relatively small
servers like those we run our accounts system on in my company) from IBM
or Apples from before they switched to x86 processors, or the afore
mentioned embedded compilers...

HELLO HELLO

This thread is about stack overflows!

We are speaking about stack overflows here.

http://dictionary.reference.com/browse/pedant

pedant

–noun
1.a person who makes an excessive or inappropriate display of learning.
2.a person who overemphasizes rules or minor details.
3.a person who adheres rigidly to book knowledge without regard to
common sense.

 

[Default User]

Interesting.

Please don't top-post. Your replies belong following or interspersed
with properly trimmed quotes. See the majority of other posts in the
newsgroup, or:
<http://www.caliburn.nl/topposting.html>

 

[Walter Roberson]

Flash Gordon wrote:

You are daydreaming.
I bet you can't name a single compiler that does that kind of nonsense!

Thad Smith indicated their existance yesterday, in the context
of a thread where the original poster had indicated that the system
in use "had no stack".

http://groups.google.ca/group/comp.lang.c/msg/214174f98d5d485a

 

[Walter Roberson]

Interesting.

I know that the stack grows down from the high addresses while the
heap grows up the address space

On some implementations. On other implementations, it is the
opposite. Some implementations have them both grow in the same
direction. And on yet other implementations, there is no stack as such.

 

[William Ahern]

It's relatively rare that a program can successfully recover from a
failing memory allocation. Even when a program does it, it's usually
only for a very limited portion of the allocations (for example,
storage allocated for buffering a large data file). In most cases
avoidance is a much better idea.

Defining "rare" can be difficult. For the application domains I'm involved
with (network application servers/daemons), after my programs enter their
event loops malloc() could fail all day long, sporadically or continually,
without necessitating that the application exit. Exiting would be the last
thing I'd want. It got that far; why would I want to chance not being to get
that far again on re-instantiation of the program?

I do regression tests on memory failure recovery, which works well for me
since most of the error paths for memory allocation failure overlap w/
general application error paths. So I can just interpose malloc() and
interject random allocation failures. Much easier than simulating arbitrary
network exchanges.

I also try to minimize stack use and avoid recursive function calls. My
async I/O library supports recursion but implements a poorman's tail call
device which limits the depth (no shenanigans; pure C).

As a practical matter, on many systems, notwithstanding any VM paging issues
or the like, there are guarantees that you can rely on regarding the stack.
On Unix you can (or have the capacity to, w/ proper configuration) guarantee
that you have a stack of, say, roughly 512K, or 1MB. And by limiting
recursion, as a practical matter, you can indeed assure yourself that you
won't overrun the stack. This is without overly intimate knowledge of the
implementation. Just due diligence and testing. (And I have seen Unix
programs which can actually do proper cleanup on stack overruns, in
conjunction w/ Unix' sigaltstack() facility, so on some systems stack
overruns aren't always a total wash, either.)

Memory management might be a pain, but its also a sort of environmental
stimulus which forces application design and implementation to make good
measure of the efficacy and necessity of various internal devices and
methods. If you don't want to deal with it, then don't use C. Use another
language, maybe a GC'd language. When memory management is merely a burden,
then C is manifestly an inappropriate tool. If you find yourself ignoring
the return value of malloc(), that's about the clearest signal possible that
your project is better implemented with a different tool.

I prefer Lua, which is noteworthy itself because, among other reasons, it
actually does check for memory failures in its ANSI C implementation, and
can throw VM exceptions (if you chose). Imagine that!

So, yes, there are people who actually manage memory, and they're not
confined to rarefied (by some measure) embedded platforms.

 

[jacob navia]

Thad Smith indicated their existance yesterday, in the context
of a thread where the original poster had indicated that the system
in use "had no stack".

http://groups.google.ca/group/comp.lang.c/msg/214174f98d5d485a

That's completely different. It is an embedded system where
there is no RAM for the stack. This is clearly NOT the
case of the user that started this thread.

Mentioning that some obscure implementation in some
embedded chip doesn't have a stack and doesn't implement
recursion doesn't mean that C is not recursive or that
most implementation do use a stack.

LET'S STOP BEING PEDANTIC!
We are speaking about stack overflows here.

http://dictionary.reference.com/browse/pedant

pedant

–noun
1.a person who makes an excessive or inappropriate display of learning.
2.a person who overemphasizes rules or minor details.
3.a person who adheres rigidly to book knowledge without regard to
common sense.

 

[Ian Collins]

Hi,

I know that it's good practise to check the returned pointer from
malloc() against NULL when making large allocations on the heap, so as
to be able to attempt recovery in case of an out-of-memory error.

But my question is: what about if you run out of memory while trying
to allocated things on the stack, e.g. a big local array variable? Is
there some way to hook in a function to run in these circumstances, to
be able to try to clean up?

Avoid the problem rather than trying to fix it, use dynamic allocation
for large objects. Then you can check for failure.

Your implementation should document the system stack size limits
(assuming it has a stack!).

 

[Chris Torek]

I know that the stack grows down from the high addresses while the
heap grows up the address space

It does some or all of the time on some systems, but sometimes
not (e.g., when using threads) on some systems, and never so on
other systems (where it grows in the other direction, or uses
the malloc() arena).

- I wonder if it would be possible to have a #pragma or something
similar that would tell the compiler "Hey I've got some very big
local arrays, so I'm gonna need plenty of stack space - try to
allow more room than usual for the stack at the expense of the
heap"?

Some systems do provide an option of this sort (usually not via
#pragma -- more often it is a linker directive or a "magic" global
variable).

The biggest problem of all comes in when you use various extensions
like threads, so that there is no longer "a" stack, but rather many
stacks, at least one per thread. (One can also have two or more
stacks per thread, as in Forth-like systems, for instance.)

 

[Flash Gordon]

jacob navia wrote, On 10/01/08 23:43:

You are daydreaming.
I bet you can't name a single compiler that does that kind of nonsense!

Since I don't rely on the behaviour you are claiming I have no reason to
check what the compilers I use do.

And the fix is to take the absolute value... We are interested in the
distance.

Where you hit the problems described below and the problem of systems
that implement the C calling conventions using something that is very
much like a heap.

Who cares?

We are speaking about STACK OVERFLOW here, so those compilers are
OFF TOPIC for this thread.

Either these implementations do not have a stack, in which case you
should stop complaining about people saying that C does not require a
stack (and admit that you were wrong) or they do have a stack so these
compilers are relevant (and you should admit that you were wrong). You
can't have it both ways.

Of course you know, and if you don't you can measure it with a program
like the above one.

At which point the system administrator changed your limits. Or you
upgrade your implementation and it changes the default allocation. Or
you are using a system where the stack is allowed to grow until it meets
the heap, so how much stack space is available depends on the current
heap usage (I've used such systems).

#include <stdio.h>
char *StartOfStack;
int main(int argc,char *argv[])
{
char foo,*p;
char m[8192*16];
if (argc > 0)
p = StartOfStack = &foo;
else
p = &foo;
printf("Stack %d\n",StartOfStack-p);
main(0,NULL);
// Not reached
}

It doesn't seem to reliable to me since the final output I get depends
on the optimisation options I pass to the compiler.

Stack 8130432
Segmentation fault (core dumped)

Stack 8374336
Segmentation fault (core dumped)

Stack 8381056
Segmentation fault (core dumped)

Stack 8374848
Segmentation fault (core dumped)

How do we know that on a real program the effects might not be even larger?

HELLO HELLO

This thread is about stack overflows!

We are speaking about stack overflows here.

Actually I thought we were talking about running out of memory on the
stack. Since you always claim that C requires a stack even if it is not
implemented as a hardware stack must include all the systems everyone
has mentioned. It also includes the other types of system I have just
mentioned (one of which can occur on systems with a hardware stack).

http://dictionary.reference.com/browse/pedant

Ah, so now you are changing tactics and calling everyone who disagrees
with you and provides evidence of your errors a pedant.

 

[Ben Pfaff]

I know that it's good practise to check the returned pointer from
malloc() against NULL when making large allocations on the heap, so as
to be able to attempt recovery in case of an out-of-memory error.

I would contend that you should do so for every call to malloc(),
not just the calls that request a large amount of memory.

 

[CBFalconer]

I know that it's good practise to check the returned pointer from
malloc() against NULL when making large allocations on the heap, so
as to be able to attempt recovery in case of an out-of-memory error.

But my question is: what about if you run out of memory while trying
to allocated things on the stack, e.g. a big local array variable?
Is there some way to hook in a function to run in these
circumstances, to be able to try to clean up?

Certainly. For example:

void *p;
...
if (!(p = malloc(whatever))) gofixup(&p); /* malloc failed */
/* here either malloc succeeded or gofixup ran */
if (!p) utterfailure();
else alliswell();

 

[David Tiktin]

That's a very abstract concept of a stack. A great many people
have a much more specific concept of a stack; the term
occasionally used is "hardware stack", and many of those people
mistakenly believe that the C standard requires a hardware stack.

Well, sure, it *is* an abstraction. But the C Standard describes the
operation of an abstract machine, doesn't it? And I still think that
it is fair to say that the abstract machine is stack-based since the
(abstract!) structure of the call graph is LIFO.

I don't mean to be argumentative, but in what way is a linked list
implementation not a "hardware" stack? Do you mean the processor
doesn't have push and pop in its native instruction set? We don't
know that. The linked list could well be implemented "in hardware"
with native hardware support. (Lew's description mentions malloc(),
but I don't see how that can be right since malloc() is a function
call!)

[description of one well-known type of stack implementation snipped]

Dave

 

[David Tiktin]

David Tiktin wrote:

[...]

A linked list can be used to implement a stack, as the
implementation you describe undoubtedly did. The point remains
that the semantics of C's function call and return describes a
LIFO structure, known in CS circles as a stack. There are other
ways to implement a stack, and the C Standard doesn't require any
specific implementation. But IMHO, to say that a linked list
which is being used in a FIFO manner is not a "stack" is not the
best way to describe the situation ;-)

From the function call tree, translators may identify which
function
life times are mutually exclusive, hence storage of object with
automatic storage duration, can be overlaid.

For implementations, using overlaid memory, is quite different
from using a stack.

OK, tail-recursion optimization comes to mind as one such
implementation technique that's not prohibited. But isn't it still
true that the implementation must behave "as if" the call graph is
LIFO?

Dave

 

[Keith Thompson]

jacob navia wrote:

[...]

P.S. When some people tell you that C "Doesn't use a stack" or
that "C doesn't know about a stack" just ignore them, they
are trying to confuse you.

No, they are not. They are making an extremely valid technical point,
one that I'm certain you're aware of by now. They are, however, being
insufficiently clear in how they make that point.

For example:

Repeat after me... slowly 1000 times:

An C implementation may or may not, implement function calls using a stack.

A C implementation *must* implement function calls using a "stack", in
the computer science sense of a last-in first-out data structure.
This is required to support recursion. An implementation could use a
fixed activation record for each function (and thus no stack of any
kind) if it can determine that no function in the program is ever
called recursively, but it must at least be able to use a stack.

(The C standard doesn't use the term "activation record". I'm using
it here to refer to the chunk of memory needed to hold data allocated
for a function call, including storage for automatic objects and
probably for the return address and other bookkeeping information.)

A C implementation may or may not implement this "stack" by means of a
"hardware stack", in which activation records are allocated within a
contiguous region of memory that grows in a particular direction,
typically managed via a dedicated CPU register used as a "stack
pointer". Most implementations do use a "hardware stack"; some use
other methods, such as a linked list of heap-allocated activation
records.

As others have pointed out in this thread and others, many relatively
novice C programmers assume that C requires a hardware stack, which is
usually what they mean by the word "stack". Pointing out to them that
this is not the case, and that writing code that depends on this
assumption is a bad idea, is A Good Thing.

However, just saying that C doesn't require a stack does not serve
this purpose; it's strictly incorrect (if you use stack in the
computer science sense), and it fails to make clear the distinction
between the two usages of the word.

So by all means continue to point out that C doesn't require a
hardware stack, but please be clearer in your explanations.

 

[Keith Thompson]

I know that it's good practise to check the returned pointer from
malloc() against NULL when making large allocations on the heap, so as
to be able to attempt recovery in case of an out-of-memory error.

Yes, but not just large allocations.

But my question is: what about if you run out of memory while trying
to allocated things on the stack, e.g. a big local array variable? Is
there some way to hook in a function to run in these circumstances, to
be able to try to clean up?

Quick answer: No.

Slightly less quick answer: There's no portable way to do this. There
*might* be some system-specific way to do it; if so, I'm not at all
familiar with it.

Note that the language *could* have been defined so as to make this
possible. For example, suppose you have a function that declares a
megabyte of local variables, but there's only half a megabyte
available when you try to call it. The call could simply fail; the
system could detect allocation failure before it attempts to do the
call, and the call to the offending function could be aborted before
it happens. Perhaps the implementation could provide something
analagous to atexit() that registers a function to be invoked on this
kind of failure; that function would have half a megabyte of "stack"
to play with. Or the language could have defined an exception
mechanism (see Ada and C++, for example).

But given C as it's actually defined, you just need to avoid running
into this situation in the first place. As others have mentioned,
allocating large objects via malloc() rather than as local variables
makes it possible to detect allocation failures without invoking
undefined behavior.

 

[Gordon Burditt]

I know that the stack grows down from the high addresses while the

heap grows up the address space

Don't know that. It isn't true for some processors that do use a
hardware stack. The stack, if there is one, can grow in either
direction. A few CPUs offer a choice in stack growth direction to
the C implementation or OS. Most don't.

- I wonder if it would be possible to
have a #pragma or something similar that would tell the compiler "Hey
I've got some very big local arrays, so I'm gonna need plenty of stack
space - try to allow more room than usual for the stack at the expense
of the heap"? That might help avoid stack overflows.

Some implementations offer this as a linker option. It is probably
better to offer it on a whole-program basis, as there is not really
a good way to combine requirements from individual source files to
make a requirement for the whole program. You cannot, for example,
add them all up. For non-recursive programs, that can come up with
a number way too high, and for recursive programs, it can be way
too low. For recursive programs where the depth is dependent on
some external factor, like the depth of directories in a filesystem,
there may be no maximum you can pre-determine at link time.

Some implementations put the stack at the opposite end of the address
space from the are used by malloc(), and allocate as it grows, so
when the two ends meet, it really can't get bigger, option or not.

Or maybe the compiler could provide a global variable like
__min_stack_address that would let you use the trick you described and
be able to tell how far off you were from hitting the stack limit.

It's unclear how this would work in an implementation where there isn't
a fixed amount of memory allocated for the stack (e.g. heap and stack
grow together).

 

[Ben Bacarisse]

Certainly. For example:

void *p;
...
if (!(p = malloc(whatever))) gofixup(&p); /* malloc failed */
/* here either malloc succeeded or gofixup ran */
if (!p) utterfailure();
else alliswell();

.... and what point is this code making? It illustrates the OPs first
paragraph (they seem to know about that) but are you saying it has
some bearing on the OPs question about automatic object allocations
failing?

 

[Gordon Burditt]

I think this is a pretty silly reply - just think of "local variables"

vs. "malloced memory" if you have hang-ups with the stack and the
heap...

I guess to rephrase what I'm asking... we tend to think of the stack
being for small allocations and the heap for big ones. But it isn't
always so.

For example, I've seen some really paranoid code, where *every*
malloc() is checked to see if it returned NULL, even if it's only for
like 10 bytes to copy a string.

That's not "really paranoid code". That's correct code. And there's
no guarantee that a program that sometimes asks for large amounts
of memory won't happen to run out on one of the more trivial requests,
rather than one of the large ones. This is especially a problem
with a program that tries to find how much memory it can allocate,
then allocates it, while unknown to that code, some other portion
of the program needs some memory also. (For example, fopen() may
call malloc()).

This is pretty pointless, if the function checking malloc so carefully
can't pick up the fact that it failed to allocate three local int
variables say, taking up a whopping 12 bytes...

A program getting an indication of a failed malloc() can back off
and ask for less, free up some other memory, or fail gracefully.
A function that overflows the "stack" (if there is one) does not
have the option of asking for less, or freeing up some other auto
variables, and it's likely that it has *ALREADY* clobbered memory
before it has started running the first line of code in the function.
And in any case, it can't use *ANY* auto variables. There isn't
much opportunity for recovery here.

And just like you can malloc small amounts, you can also use up lots
of stack memory by declaring huge arrays as local variables. There
surely ought to be some way to recover if this fails.

There ought to be a way to recover if you drive too far off a cliff,
too, but the opportunities for recovery are very limited.

 

[James Kuyper]

On 10 Jan 2008, (e-mail address removed) wrote: ....

Well, sure, it *is* an abstraction. But the C Standard describes the
operation of an abstract machine, doesn't it? ...

The issue is that there's a commonly held misconception that the
abstract requirements of the C standard imply a concrete requirement
that they be implemented with a hardware stack.

... And I still think that
it is fair to say that the abstract machine is stack-based since the
(abstract!) structure of the call graph is LIFO.

I don't mean to be argumentative, but in what way is a linked list
implementation not a "hardware" stack?

I explained my answer to that question very concretely in the part you
snipped, with an example program. A linked list implementation could
cause the first call to assert() to abort the program, and even if it
did not, it might cause different outputs from each of the two printf()
calls.

 

[James Kuyper]

jacob navia wrote:
....

http://dictionary.reference.com/browse/pedant

pedant

–noun
1.a person who makes an excessive or inappropriate display of learning.
2.a person who overemphasizes rules or minor details.
3.a person who adheres rigidly to book knowledge without regard to
common sense.

4. (clc) a person who makes a reasonable and appropriate display of
learning, giving appropriate emphasis to rules or minor details, in
accordance with common sense, to point out that not all implementations
of C have the characteristics that the speaker assumes to be universally
true.