Recovering from out of memory on the stack

[Richard Tobin]

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?

Some operating systems provide a way to do this, but it's not standard
C.

In unix you get a segmentation violation signal when the stack
overflows, and you can set up a handler for it. Of course, you have
the problem that the stack has run out, so how can the handler run?
To solve this there is a system call to set an alternate stack for
signal delivery. See the manual pages for sigaction and sigaltstack.

-- Richard

 

[Walter Roberson]

In unix you get a segmentation violation signal when the stack
overflows, and you can set up a handler for it. Of course, you have
the problem that the stack has run out, so how can the handler run?
To solve this there is a system call to set an alternate stack for
signal delivery. See the manual pages for sigaction and sigaltstack.

For suitable values of "unix".

sigaltstack is part of POSIX XSI (X/Open System Interface), a
POSIX extension added in 2001 and denoted by the symbolic
constant _XOPEN_UNIX . Older Unix versions might not have it --
and as it is an option, there is the -possibility- of a Unix that
does not have it.

 

[David Tiktin]

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.


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.

Yes, I understood that. But my point was still that you were talking
about only one implementation, although a very common one.
(Seriously, I've never worked with any other although I think the
SPARC architecture uses some fancy registers as part of the "stack.")
You call it a "hardware" stack as if that differentiates it in some
way from other implementations, such as the linked list. My point
was that a linked list could also be a hardware implementation. I
don't see how the "contiguous array" implementation is more a
hardware implementation than a linked list. If it's a LIFO
structure, it's a stack.

But be that as it may, the main thing I wanted to say was that the
OP's question should not have been dismissed by saying that the C
Standard doesn't require a stack. I think it requires a LIFO
structure of some sort (commonly known as a stack), and hence the
OP's question about detecting and recovering from stack exhaustion is
a good one. Clearly, the LIFO structure in which program state is
stored will require memory of some form (regardless of how it's
organized) which won't be infinite. If this is true, *every* C
implementation can encounter the problem of "hitting bottom" since
every C implementation must have a "stack" in some form or other.

Dave

 

[David Tiktin]

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.

It's not totally clear to me who you mean by "most people," but I
think the abstract data type "stack" as encountered in CS does not
depend on all the elements having the same size or even the same
"type." Perhaps that's the kind of implementation "we" typically
encounter as C programmers because that's a natural way to implement
a stack ADT in C. Nevertheless, I don't think it's part of what
makes a stack a stack, and the "hardware" stack James Kuyper
describes elsethread is clearly a stack (since it's LIFO) and doesn't
meet your notion of element size.

Dave

 

[jameskuyper]

Yes, I understood that. But my point was still that you were talking
about only one implementation, although a very common one.

More accurately, I was talking about the misconception that there's
only one possible implementation, and the need to point out the fact
that it is a misconception.

You call it a "hardware" stack as if that differentiates it in some
way from other implementations, such as the linked list. My point
was that a linked list could also be a hardware implementation. I
don't see how the "contiguous array" implementation is more a
hardware implementation than a linked list. If it's a LIFO
structure, it's a stack.

I didn't choose the term; I merely borrowed the term some other people
have been using to distinguish it from the abstract stack that you're
talking about. I agree that it's not the best possible term. The
important thing is that the people who are laboring under the
misconception I referred to above DO NOT have a special term for that
kind of stack, because they imagine that it is the only kind of stack.
As we've seen from messages posted in this same thread, many of them
are even under the misconception that there's only one possible
direction for growth of a stack. I didn't insert an assert reflecting
that assumption into my code.

 

[Tor Rustad]

[...]

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.

Methinks, most programmers who have written compiler backends,
understand perfectly what kind of stack I was talking about. Those who
don't, should find something else to do.

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.

I do agree that in case of recursion, this imply a LIFO mechanism to
keep track of function return address.

However, I object to your usage of "stack", it might be fine in a CS
class on algorithms, but IMO *not* in the context of C compiler code
generation.

Furthermore, in free-standing environments, stack resources can be very
limited. Here, recursive functions are rarely used. I have seen more
than one (non-conforming) C implementation lacking support for
recursion. This is no big deal, C programming guidelines will typically
ban recursion in such environments anyway. In particular, this is true
for safety-critical work, no sane guideline will allow recursion here.

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.

Well, Jacob deserved a sarcastic on-liner, nothing more. We have already
been over this topic, not that long ago.

 

[Keith Thompson]

Methinks, most programmers who have written compiler backends,
understand perfectly what kind of stack I was talking about. Those who
don't, should find something else to do.

How many readers of comp.lang.c write compiler backends?

I do agree that in case of recursion, this imply a LIFO mechanism to
keep track of function return address.

However, I object to your usage of "stack", it might be fine in a CS
class on algorithms, but IMO *not* in the context of C compiler code
generation.

But it's perfectly appropriate in the context of the C language, which
is what we talk about here.

Look, there are clearly two different meanings of the word "stack" in
common usage, and it seems that *every* time the word is mentioned
without making the distinction absolutely clear, it starts an
argument. Perhaps we can avoid that.

Furthermore, in free-standing environments, stack resources can be
very limited. Here, recursive functions are rarely used. I have seen
more than one (non-conforming) C implementation lacking support for
recursion. This is no big deal, C programming guidelines will
typically ban recursion in such environments anyway. In particular,
this is true for safety-critical work, no sane guideline will allow
recursion here.

Well, Jacob deserved a sarcastic on-liner, nothing more. We have
already been over this topic, not that long ago.

jacob wasn't the only person who read your reply; others, including
the OP, deserve more than a sarcastic one-liner.

 

[Paul Hsieh]

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,

You mean auto declarations.

[...] 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?

I think the language is allowed to blow up (be undefined) if it runs
out of the ability to allocate the autos for a frame.

The right answer is to declare minimal auto variables and malloc (and
free) the arrays and structures. In such situations you will either
run out of heap before you run out of auto space or else you have a
deep recursion problem which should probably be solved in some other
way.

 

[Mark F. Haigh]

Yes, but not just large allocations.


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.

<snip>

[OT]

Typically the OS facility (if present) allows you to malloc a buffer
and register it as an alternate stack for the signal handler. On Unix-
ish systems, it's sigaltstack(), which is part of some Open Group
standard, I forget which.

This way your signal handlers won't be affected by stack overflows via
allocation or unbounded recursion.

Of course, that being said, the bulk of my professional work occurs in
environments where this feature is not available. Things like
sigaltstack are great as a value-add type of thing, but there's no
excuse for not understanding your code's automatic (ie stack) and
dynamically-allocated memory requirements.


Mark F. Haigh
(e-mail address removed)

 

[Richard Tobin]

Things like
sigaltstack are great as a value-add type of thing, but there's no
excuse for not understanding your code's automatic (ie stack) and
dynamically-allocated memory requirements.

There are circumstances where it's impractical to limit stack use.
For example, when implementing another programming language in such a
way that recursion in the user program corresponds to recursion in
your implementation. In that case trapping stack overflow can produce
a slightly friendlier result.

-- Richard

 

[Mark F. Haigh]

There are circumstances where it's impractical to limit stack use.
For example, when implementing another programming language in such a
way that recursion in the user program corresponds to recursion in
your implementation. In that case trapping stack overflow can produce
a slightly friendlier result.

Perhaps, but anything that can be implemented recursively can be
implemented iteratively. In your example, the user code would not
care if the underlying implementation was recursive or iterative, as
long as it behaved indistinguishably from the recursive.

Mark F. Haigh
(e-mail address removed)

 

[Richard]

Certainly. For example:

void *p;
...
if (!(p = malloc(whatever))) gofixup(&p); /* malloc failed */

Disgusting style and nigh on impossible to check with a debugger (which
real programmers do in this type of "extreme" programming).

/* here either malloc succeeded or gofixup ran */
if (!p) utterfailure();
else alliswell();

I fail to see how anything you posted helps the question posed. All you
did was show, poorly, how to check the malloc return.

Why poorly? Layout for one thing is debugger and reading unfriendly, and
secondly you call the "alliswell" without the memory pointer and finally
you forget to free the memory. I wouldn't normally bother correcting
your poor advice but it seems somewhat merited considering your normal
pedantic tendencies to correct others.

 

[Richard Tobin]

There are circumstances where it's impractical to limit stack use.
For example, when implementing another programming language in such a
way that recursion in the user program corresponds to recursion in
your implementation. In that case trapping stack overflow can produce
a slightly friendlier result.

[/QUOTE]

Perhaps, but anything that can be implemented recursively can be
implemented iteratively.

So what? That's equally true of C compilers. Do you suggest that C
compilers should never generate recursive code, to avoid this problem?

-- Richard

 

[Martien Verbruggen]

Perhaps, but anything that can be implemented recursively can be
implemented iteratively.

So what? That's equally true of C compilers. Do you suggest that C
compilers should never generate recursive code, to avoid this problem?[/QUOTE]

I think he was suggesting that, in a situation where you feel you need
to avoid stack overflow due to recursion, you could implement an
iterative solution instead. If you do, you either don't run into the
problem of a stack overflowm or, if you have your own internal
structures that fill up, overflow, or become unwieldy, you can produce
the slightly friendlier result that was suggested upthread.

At least, that's how I would read it. I certainly see no possible way to
read what was written as a suggestion that C compilers sould never use
recursive code to avoid this problem.

Martien

 

[Tor Rustad]

[...]

Well, Jacob deserved a sarcastic on-liner, nothing more. We have
already been over this topic, not that long ago.

jacob wasn't the only person who read your reply; others, including
the OP, deserve more than a sarcastic one-liner.

In the art of flaming, Keith "the polite", might not the best teacher
around.


Regarding OP, I can confirm that there is no standard signal for "stack
overflow", some platforms provide extra information after a SIGSEGV, but
using this is non-portable. The word "stack" is nowhere to be seen in
the standard, but a LIFO mechanism is needed by C implementations, in
order to translate a recursive functions.

Happy now Keith?

 

[Keith Thompson]

[...]

Well, Jacob deserved a sarcastic on-liner, nothing more. We have
already been over this topic, not that long ago.

jacob wasn't the only person who read your reply; others, including
the OP, deserve more than a sarcastic one-liner.

In the art of flaming, Keith "the polite", might not the best teacher
around.

Thanks -- I think.

Regarding OP, I can confirm that there is no standard signal for
"stack overflow", some platforms provide extra information after a
SIGSEGV, but using this is non-portable. The word "stack" is nowhere
to be seen in the standard, but a LIFO mechanism is needed by C
implementations, in order to translate a recursive functions.

Happy now Keith?

Deliriously.

 

[Kelsey Bjarnason]

[snips]

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.

No, it doesn't mean that. C does allow for recursion and many, possibly
most implementations do use a stack. However, as far as C is concerned,
there is no requirement a stack exist at all; if there were, C could not
be implemented on non-stack-based systems.

By avoiding the requirement of a stack, the standard allows C to be
implemented on machines without a stack, as long as a (strictly?)
conforming application cannot tell the difference.

LET'S STOP BEING PEDANTIC!

Err... you're in a group inhabited largely by software engineers of some
experience. You know, people who make their livings being pedantic.

People who write code and aren't pedantic about it are the sort who give
us the endless buffer overflows, stack smashes and other wonderful gaping
security holes.

Let me put it this way: if you wanted to hire someone to write the code
which handled all your financial transactions, all your investments,
everything that qualified as your "wealth", who would you pick: someone
who only pays attention to details sometimes, or someone who pays
attention to details all the time, even the minute ones which, if ignored,
might bite you in the ass?

I'm guessing you'd hire the latter sort. Yet when such people talk here,
pointing out that those details actually matter, that good programmers
need to focus on details and not make a lot of incorrect assumptions, you
criticise them for it.

Why is that? Are you trying to actually *encourage* sloppy coding,
inattention to detail, the sort of carelessness which has led to endless
exploits?

This is a field where correctness counts, and where correctness is
damnably difficult to attain in the best of circumstances. Promoting
sloppy behaviour, sloppy discussion and poor assumptions benefits nobody;
promoting good practises, correct information and rejection of unwarranted
assumptions benefits all.

Yet you and others complain. Why?

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.

If that's the proper meaning, then "pedant" applies to nobody here, as
what is being said - repeatedly and endlessly - here is that the details
_do_ matter.

 

[Kelsey Bjarnason]

[snips]

Who cares really?

I can think of lots of people. Implementers, for example. They should at
least know _how_ the language works, or they're likely to produce
implementations which are incorrect.

Most implementations use a stack

Some do, some don't, and as far as _C_ is concerned, the issue is
irrelevant. There's no requirement either way.

and in a discussion about stack
overflow your pedantic insistence is OFF TOPIC!

How can you overflow a stack if there's no stack to overflow? Or were we
not discussing C code in a C group, involving the C language, defined by
the C language standard, which doesn't even _mention_ "stack"?

 

[Keith Thompson]

No, it doesn't mean that. C does allow for recursion and many, possibly
most implementations do use a stack. However, as far as C is concerned,
there is no requirement a stack exist at all; if there were, C could not
be implemented on non-stack-based systems.

By avoiding the requirement of a stack, the standard allows C to be
implemented on machines without a stack, as long as a (strictly?)
conforming application cannot tell the difference.

[...]

Kelsey, what exactly do you mean by the word "stack"? As I've
mentioned several times in this thread, there are two distinct
commonly used meanings of the word.

 

[Kelsey Bjarnason]

No, it doesn't mean that. C does allow for recursion and many, possibly
most implementations do use a stack. However, as far as C is concerned,
there is no requirement a stack exist at all; if there were, C could not
be implemented on non-stack-based systems.

By avoiding the requirement of a stack, the standard allows C to be
implemented on machines without a stack, as long as a (strictly?)
conforming application cannot tell the difference.

[...]

Kelsey, what exactly do you mean by the word "stack"? As I've
mentioned several times in this thread, there are two distinct
commonly used meanings of the word.

There's a commonly used data structure, the stack, which works sorta like
a stack of pancakes: last one onto the stack is the first one off (meaning
the ones at the bottom get cold - ick.)

Then there's a common, but far from universal, concept in computer design
in which a region of memory is used as a stack in order to handle the
mechanics of calling (returning from, to be precise) functions, storing
variables local to those functions and the like. One might note that the
CPU itself often manages much of the housekeeping of such a stack.

To quote jacob, "We are speaking about stack overflows".

The term "stack overflow" almost always (IME always) refers to the second
sort. The idea is simple enough: by some jiggery-pokery, one can stuff
too much stuff into the stack and cause such items as the return address to
be overwritten, in such a manner that a "return" ends up pointing at
injected code and voila, your machine is now "pwned". Or, more simply and
less nastily, something such as excessive recursion can exhaust the
(usually very limited) memory used for this stack, meaning the next time
around, the CPU either pukes or does something equally nasty such as wraps
the stack memory register around.

I don't think I've ever heard "stack overflow" used in reference to the
generic data structure, presumably because such structures do not
overflow; instead you get an allocation failure, a somewhat different
class of problem.

It might be pointed out that C doesn't discuss either type, so in theory
neither would be topical; one would belong on, oh, a hardware group of
some sort, the other on an algorithm group or the like. Of course, if
you've implemented the latter sort in C and it's not working, examining
_why_ it's not working is just the sort of thing we do here.