Recovering from out of memory on the stack

S

sandysimons53

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?

Thanks for any insight.

~ Sandy
 
L

Lew Pitcher

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,

Repeat after me: "There is no stack in the definition of the C
Language"

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?

You are describing an irreversible "out-of-memory" condition. What
would you have a hooked-in function do? The best (and probably only)
thing that such a function could do is arrange for a graceful
termination; it certainly couldn't "clean up" the automatic memory
allocations to obtain more space.
 
D

dj3vande

Repeat after me: "There is no stack in the definition of the C
Language"

Not one described by that name, but it would be Rather Difficult to
implement the semantics of function calls and automatic storage
allocation without something that feels and smells like a stack.

You are describing an irreversible "out-of-memory" condition. What
would you have a hooked-in function do? The best (and probably only)
thing that such a function could do is arrange for a graceful
termination; it certainly couldn't "clean up" the automatic memory
allocations to obtain more space.

It could arrange for more memory to be available for automatic
storage. How it would go about doing such a thing is of course
sufficiently system-specific that there's really no point in making it
part of the language.
At least one implementation that I know of puts function invocation
records (including automatic storage) in a contiguous block of memory
with a few pages at the end that trigger a protection trap when they're
accessed; the runtime system catches this trap, maps useable memory in
place of the guard page, and moves the guard page down.
An implementation that dynamically allocates stack frames could run
some kind of cleanup of the dynamically allocated memory area; possibly
a garbage collection and/or defragmentation, or running any deferred
deallocated-memory reclamation, or invoking low-memory handlers (that
would obviously need to do something other than dynamically allocating
*their* invocation records - possibly using pre-allocated ones
instead).


dave
 
L

Lew Pitcher

Not one described by that name, but it would be Rather Difficult to
implement the semantics of function calls and automatic storage
allocation without something that feels and smells like a stack.

I know of at least one implementation that uses dynamic memory
allocations (i.e. allocations from the "heap", what ever that is) to
build function activation records. Each activation record contains
enough storage for all the function's automatic variables, with each
variable preallocated within the record. No stack here; just a linked-
list of memory blocks malloc()ed by the underlying implementation.
It could arrange for more memory to be available for automatic
storage. How it would go about doing such a thing is of course
sufficiently system-specific that there's really no point in making it
part of the language.

As the language does not have support for that sort of thing (as you
wisely note), there isn't much use in discussing hypotheticals. I
could say that hypothetically, such a function could take a complete
checkpoint of the program and its environment, order a ram upgrade
from Best Buy, and perform an orderly shutdown of the computer such
that the startup after Best Buy installs more ram would permit the
program to resume from where it left off. Just as possible, I guess,
as your suggestion :)

In any case, if we stipulate a "stack", then a "stack overflow" is
pretty much an irrecoverable situation. And if we stipulate something
other than a stack, we recognize that C does not have the ability to
explicitly, programmattically, manipulate that data structure. Again,
the best such an intercept could do is perform an orderly shutdown.

Having said that, the signal() functions come to mind; the draft
standard doesn't indicate whether the inability to allocate an
automatic variable would raise a signal (like SIGILL, or SIGSEGV) or
not, but if it did, then a signal handler function could intercept the
signal and take appropriate (limited) action.


[snip]
 
D

dj3vande

I know of at least one implementation that uses dynamic memory
allocations (i.e. allocations from the "heap", what ever that is) to
build function activation records. Each activation record contains
enough storage for all the function's automatic variables, with each
variable preallocated within the record. No stack here; just a linked-
list of memory blocks malloc()ed by the underlying implementation.

How often do you add or remove a link other than at the
most-recently-accessed end?
Smells like a stack to me.

As the language does not have support for that sort of thing (as you
wisely note), there isn't much use in discussing hypotheticals. I
could say that hypothetically, such a function could take a complete
checkpoint of the program and its environment, order a ram upgrade
from Best Buy, and perform an orderly shutdown of the computer such
that the startup after Best Buy installs more ram would permit the
program to resume from where it left off. Just as possible, I guess,
as your suggestion :)

Just as possible, and perhaps less likely to need a second-level
failure handler to handle inability of the recovery routine to make
more memory accessible (at which point there's not much more that can
be done other than logging the failure and aborting), but it would be
rather harder to implement entirely in software.
Note that the first example I gave is not merely hypothetical; it HAS
BEEN implemented in a real system (at the OS level - it's not exclusive
to the C implementation) that runs on a large number of computers,
including millions of desktops.

In any case, if we stipulate a "stack", then a "stack overflow" is
pretty much an irrecoverable situation.

This must be some new meaning of the word "stack" with which I am not
familiar.
A stack is a data structure that allows you to insert data, and to
remove the most-recently-inserted not-yet-removed data element; you can
run out of memory to put the data you try to insert, but the idea of
"overflowing" the stack itself doesn't make sense.
And if we stipulate something
other than a stack, we recognize that C does not have the ability to
explicitly, programmattically, manipulate that data structure. Again,
the best such an intercept could do

....without knowing more about the system than that it's a conforming
hosted C implementation...
is perform an orderly shutdown.

Which can be rather difficult to do without being able to allocate
automatic storage, though probably not harder than "prohibitively
expensive", and certainly worth doing in applications where being able
to fail cleanly is important enough. I'm not sure you'd be able to do
even that without knowing more about the system than that it's a
conforming C implementation, though.

Or it can use knowledge about the implementation (whether in a C
program tied to that implementation or built into the implementation
itself) to recover from the failure and keep going.

Having said that, the signal() functions come to mind; the draft
standard doesn't indicate whether the inability to allocate an
automatic variable would raise a signal (like SIGILL, or SIGSEGV) or
not, but if it did, then a signal handler function could intercept the
signal and take appropriate (limited) action.

Using a guard page at the end of a contiguous block of memory would be
isomorphic to handling SIGSEGV, though that's not the mechanism that
the implementation I referred to uses.
If the program knows how to set up the guard page mechanism and
identify whether the SIGSEGV applies to that or to something else, it
could probably implement the actual recovery using only two or three
system-specific calls. (In fact, I'd expect that's what the OS handler
does if it's handled at the OS level: Call a recovery routine written
to use kernel calls and compiled with a C compiler.)


dave
 
D

David Tiktin

I know of at least one implementation that uses dynamic memory
allocations (i.e. allocations from the "heap", what ever that is)
to build function activation records. Each activation record
contains enough storage for all the function's automatic
variables, with each variable preallocated within the record. No
stack here; just a linked- list of memory blocks malloc()ed by the
underlying implementation.

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 ;-)

Dave
 
J

jacob navia

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?

Thanks for any insight.

~ Sandy

This is an extremely difficult situation.

Within the lcc-win compiler system, you can recover from such a
situation if you use the try/catch feature, but it is VERY
difficult since when you run into the recovery function
there is almost no stack at all.

Detailed instructions for lcc-win can be found in the
tutorial. Look t the chapter about structured
exception handling.

In other compilers, the situation is worst. This is
very system specific, and depends on the facilities that
offers the compiler system in question. Besides, you can change
the size of the stack under windows: this can be changed with
a compiler option.

Under Unix you have to change the limits of the user probably
but better look at the documentation.

You can have an idea of how much stack you are using if you do
the following

char *StartOfStack;
int main(...)
{
char foo;

StartOfStack = &foo;
}


This will tell you approximately WHERE the stack begins.

You can see how much you have used if in the function "fn" you do:

int fn(void)
{
char foo;
char *CurrentStack = &foo;

size_t StackSize = CurrentStack - StartOfStack;
}


You can then TEST before you call a function that uses a lot of stack
if you are beyond some limit.

Of course this is very compiler specific too, but should work
in most systems.

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.
 
S

sandysimons53

Hi,

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.

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... :)

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.

Just my $0.02...

~ Sandy
 
J

jacob navia

David said:
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.

But this is CS, i.e. Computer Science. This is not mentioned in the C
standard of 1989. It is impossible to speak about things like
computer science to some people here.
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 ;-)

But it confuses people, makes them look like ignorant fools, and
the poster of this nonsense feels like a small god:

"Repeat after me"

he says. Like when you speak with little children. Isn't it
wonderful the fun you can get in comp.lang.c?
 
W

Walter Roberson

But this is CS, i.e. Computer Science. This is not mentioned in the C
standard of 1989. It is impossible to speak about things like
computer science to some people here.

The implementation Lew described does not behave like what most people
would think of as a stack. In a "stack", when an old element is popped
off, and a new element of the same size or smaller is pushed on, the
space that was previously used for the old element is reused for the new
element.

In the malloc()'d function- activation- record implementation
that Lew described, you have no idea where the new element will go
in memory -- it *might* go where the old element was, but it might
not. For example, if something else was free()'d in the meanwhile,
then the dynamic storage allocator might decide to put the new
element in that vacated space. Or if something else was free()'d
in the meanwhile, free blocks might get coallesced and possibly
even returned to the operating system, a garbage collection might
get triggered, etc., leading to the new activation record getting
stored in a very different location than the old one was. And of course
if additional memory was malloc()'d inbetween, then the space that
was used for the old activation record might be part of some object
now, so again the new activation record might go somewhere very
different.
 
W

Walter Roberson

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.

C does not provide any such mechanism.

If you are declaring huge arrays as local variables such that
running out of stack memory is a serious problem that needs to be
potentially recoverable from, then Don't Do That: allocate just
a pointer variable in the local variables, and malloc() the required
memory, thus giving you control to detect not only -that- some
memory could not be allocated, but also control to detect -which-
memory could not be allocated.
 
G

gw7rib

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.

This is considered good practice.
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.

If you need to get hold of some memory to use when malloc fails, then
one way to do this is to malloc some memory as a spare early on in the
program. Perhaps make your program bail out if this malloc fails. If
it doesn't, if the program then runs out of memory in the middle of
something interesting, you have some (so far unused) memory to play
with.

One problem might be if you run out of stack memory (assuming your
computer uses such a thing, which it probably does) as the stack is
used in the running of the program and you need the free memory to be
in a particular place, ie next to the rest of the stack. I can only
recommend that you use malloc rather than the stack for any "huge
arrays" you deal with, even if they are only local to a particular
function.

Hope that helps.
Paul.
 
F

Flash Gordon

jacob navia wrote, On 10/01/08 20:27:
This is an extremely difficult situation.

Within the lcc-win compiler system, you can recover from such a
situation if you use the try/catch feature, but it is VERY
difficult since when you run into the recovery function
there is almost no stack at all.

This, of course, is specific to lcc-win and not part of the C language.

You can have an idea of how much stack you are using if you do
the following

char *StartOfStack;
int main(...)
{
char foo;

StartOfStack = &foo;

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.
}

This will tell you approximately WHERE the stack begins.

You can see how much you have used if in the function "fn" you do:

int fn(void)
{
char foo;
char *CurrentStack = &foo;

size_t StackSize = CurrentStack - StartOfStack;

Of course, if the stack grows in the opposite direction (as it does on
the PowerPC) it could give very unexpected results. 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.
}


You can then TEST before you call a function that uses a lot of stack
if you are beyond some limit.

However you have no way of knowing (in general) what limit you need to
test against, so it does not help you.
Of course this is very compiler specific too, but should work
in most systems.

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...
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 trying to make a point that you still seem not to have
understood. Even with a stack your suggestion can easily fail miserably,
especially if you consider the linked list implementation of the C
semantics as being a stack.
 
T

Tor Rustad

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.
 
T

Tor Rustad

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.

Repeat after me... slowly 1000 times:

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

jameskuyper

David said:
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 ;-)

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. The concept they are thinking of
can be explained by considering the following code. That concept
implies that:
1. There is, or at least could be, a linear address space containing
the entire stack, which renders the pointer comparisons below
meaningful even though the C standard itself does not say so.
2. None of the calls to assert() in the following code will abort the
program.
3. Both calls to printf() will print the same thing.

#include <stdio.h>
#include <assert.h>
void f1(int *pa, int *pb, int *pc)
{
int d;
printf("%p\n", (void*)&d);
assert( (pa > pc) == (pc > &d) );
assert( (pa > pc) == (pb > pc) );
assert( (pa > &d) == (pb > &d) );
}

void f2(int *pa, int *pb)
{
int c;
f1(pa, pb, &c);
f1(pa, pb, &c);
}

int main(void)
{
int a,b;
f2(&a, &b);
return 0;
}

The statement "there is no stack in the definition of the C language"
is intended to remind people that any one of those calls to assert()
might fail, and that the two calls to printf() are not required to
produce the same output.
 
R

robertwessel2

Hi,

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.

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... :)


It's not pointless. Failing to check every malloc, or equivalent, is
simply an indication of a grievously flawed program. Now in some
sample or test code it's perhaps not unreasonable to omit, but
certainly nothing like that should ever make it into any kind of
production system. OTOH, the failure of most mallocs is simply a
fatal error, and it's quite reasonable to have a small wrapper around
malloc along the lines of:

void * mustmalloc(size_t s)
{
void *p;
p = malloc(s);
if (!p)
KaBoom(); /* issue diagnostic and abend */
return p;
}

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.


If I fatally run out of stack space, I hope the implementation will
abend the program at that point. And most do.

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.

The thing you *don't* want to do is wander back into your program with
bad pointers, buffer overflows, and whatnot, which might cause all
sorts of havoc long after the failing memory allocation.
 
J

jacob navia

Tor said:
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.

Repeat after me... slowly 1000 times:

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

Who cares really?

I don't.

Most implementations use a stack, and in a discussion about stack
overflow your pedantic insistence is OFF TOPIC!

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.
 
W

Walter Roberson

Tor Rustad wrote:
Most implementations use a stack, and in a discussion about stack
overflow your pedantic insistence is OFF TOPIC!

It is not off-topic when it is in direct response to your claim
in this very subthread, that,
 
S

sandysimons53

Interesting.

I know that the stack grows down from the high addresses while the
heap grows up the address space - 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.

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.

~ Sandy
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top