Avoiding recursive stack overflow in C on Unix/Linux?

[Kleuskes & Moos]

A FSM has a hard coded bound on depth.

Since when?

Can you make these parser generators
admit to reaching their limit by asking
them to parse input that goes too deep?

Huh?

 

[Barry Margolin]

Where i work, code like that is likely to get you fired on the spot.

I wasn't actually suggesting it, I think it's actually an unlikely way
to write C programs. Most parsers are either state machines, which are
purely iterative, or they recurse for nested structures while iterating
for the tokens within it.

 

[Keith Thompson]

Spot on. I hadn't thought of that one.

<reads up on OOM-Killer>

However, if i understand http://linux-mm.org/OOM_Killer correctly
(interesting read, BTW), processes may be killed, but not with a
SIGSEGV, so the program does not crash, but is terminated by the
system. This may not be the desired outcome, but it's not a bug.

And as K. Thompson points out, it may actually kill a different
process, based on the result of badness() and the Law of Least
Surprize.

In any case, malloc should still return NULL if allocation fails, and
the manpage says it does. That processes may be terminated by the
system as a consequence of that call is another matter entirely.

The problem, as I see it, is that by returning a non-null value, the
system promises the program that it can use the allocated memory.
Later invoking the OOM killer when the program actually tries to
use it seems to me to be a violation of that promise.

I understand that overly optimistic allocation can make sense
for stack space; a program will likely never use as much stack
as it could. But I'm not convinced that the same thing applies
to malloc(). If a program calls malloc(), it's telling the OS that
it *will* use that memory (and probably soon). If the system can't
fulfill the request, it should refuse it in the first place.

Do many actual programs malloc() much more memory than they're
actually going to use?

 

[Måns Rullgård]

The problem, as I see it, is that by returning a non-null value, the
system promises the program that it can use the allocated memory.
Later invoking the OOM killer when the program actually tries to
use it seems to me to be a violation of that promise.

I understand that overly optimistic allocation can make sense
for stack space; a program will likely never use as much stack
as it could. But I'm not convinced that the same thing applies
to malloc(). If a program calls malloc(), it's telling the OS that
it *will* use that memory (and probably soon). If the system can't
fulfill the request, it should refuse it in the first place.

Do many actual programs malloc() much more memory than they're
actually going to use?

They do indeed, and that practice is the very reason for overcommit
existing in the first place.

 

[Ian Collins]

I would hope such library was non-recursive. This has Denial of Service
written all over it, considering that JSON data usually comes from untrusted
sources, and even many scripting languages use the C stack for calls in the
scripting language.

I suppose one could add kludges like a depth counter. I say kludge because
stack memory in C is such an opaque and unmeasureable quantity.

It would take an extremely large JSON object (at least as big as the
stack) to overflow a server's stack. A prudent sever admin would set a
realistic limit on request sizes.

 

[Shao Miller]

But i'd still be interested in your non-portable way, and the above is
insufficient to give me an idea about what you have in mind.

Could you please confirm: Are you offering that in practice, it is best
to avoid recursion? That's what I'm gathering since "stack" doesn't
appear in n1256.pdf.

We do get some limits from that draft's 5.2.4.1p1, including:
- 127 nesting levels of blocks
- 511 identifiers with block scope in one block
- 127 arguments in one function call

But I'm not sure if that helps us to control whether or not a C program
would cause a problem if an implementation uses a stack for anything.

If we have mission-critical code and do not use automatic objects at
all, would that even help? Or might a particular C implementation still
use a stack behind-the-scenes for something or another, and we might
still run the risk of overflowing it?

If we roll our own stack(s) and have stack_push() and stack_pop(), and
those functions write their success/failure to a static object, then we
could certainly avoid overflowing our custom stack(s), right?

But are you advising that if it is known or suspected that the C
implementation uses a stack for the operation of function calls, that
such an implementation detail alone is enough reason to avoid recursion
in mission-critical code, because C does not have a standard way to
detect proximity to overflow of said stack?

Would you be interested in C code which tries to avoid automatic objects
and instead manage its memory resources very tightly? Do you already
have code like that, that you're willing to share?

As "un-C-like" as it might be to avoid the native calling features of C,
perhaps there might still be some benefit to having such code, since C
is so widely portable, thanks to its years of standardization efforts,
and so audience-accessible, do you think?

Thanks for the interesting read!

 

[Keith Thompson]

They do indeed, and that practice is the very reason for overcommit
existing in the first place.

(I'm keeping this in comp.unix.programmer and comp.lang.c for now, since
it still seems relevant to both. Feel free to set followups if that
changes.)

Why? If a program finds it needs more memory, it can always call
malloc() again, or realloc() to increase the size of an existing block.
Can you give an example where it makes sense to allocate a large block
of memory and not use it (or use only a small initial portion of it)?

 

[James Kuyper]

Let me see if i got that straight... You've been arguing that there's
no portable way to cap recursion and a runaway recursive process will

Nor any portable way to cap non-recursive function calls that overflow
the stack, either. My complaint has nothing to do with recursion; which
is really the point of my objection to your objections to recursion -
the problem you're trying to avoid cannot be absolutely avoided in any
context; and it can be avoided (with less than absolute success) for
recursive programs just as it can be with non-recursive ones.

overflow the stack, resulting in a SIGSEGV...

Not necessarily; that's just what happens on systems which have SIGSEGV,
or some equivalent mechanism.

That means the only cap placed on recursion in such a case is the
kernel THROWING a SIGSEGV. This will terminate the process in question
quite effectively, but not to the liking f your client, i imagine.

I'm commenting on two entirely distinct issues.

1. The lack of any portable way for a C code to avoid making a function
call that requires more stack space than is currently available; there's
not even a portable way to recover from the fact that such a call was
made, which would be a markedly inferior solution to this problem.
Handling a SIGSEGV is indeed an example of such an inferior solution,
but it's not mandated by the C standard.

2. You made a comment about me relying on SIGSEGV; I don't, and I
explained why I can't; but this is only a side issue, not directly
relevant to the first point. My first point would still apply even if I
had no such restrictions placed on my code, and even if it ran on a
platform which misbehaved in some entirely different way when it ran out
of automatically allocated memory. It doesn't even matter whether or not
it uses a stack to provide that memory, or some other mechanism, such as
activation records.

It's like telling a man "the problem with this car is that you might
run out of gas driving it, if you don't pay attention to the fuel-
gauge". No contradiction, but that doesn't mean nothing is wrong with
it.

Every car I've looked at since my second car search, about 1994, has had
as standard equipment either a buzzer or a flashing light (usually both)
that would provided advance warning if the fuel level was too low. I
would in fact consider any car lacking such warning mechanisms to be
seriously defective.

Where's the buzzer/warning light for approaching the stack limits in C?
The non-portable best that I can do is handling SIGSEGV, which is a
little late; the problem I wanted to avoid has already happened by the
time that signal is raised.
For that matter, I'd settle for the analog of a gas gauge - where can I
find it?

I don't want to make this sound like more of a problem than it really
is; I've been writing programs in C for 30 years now despite the lack of
this feature - it hasn't stopped me, and has only occasionally slowed me
down. However, but I'm aware of the problems that the lack of such a
feature can cause, and of my helplessness in dealing with those problems.
My point is that recursive code makes only a quantitative difference in
how difficult it is to avoid such problems; it's not a fundamental
qualitative difference. The improvement in the maintainability of the
code because of the use of a recursive algorithm can easily be
sufficient to make up for that difference. Your advice to "avoid
recursion, if at all possible" is an overreaction.

 

[Barry Margolin]

Do many actual programs malloc() much more memory than they're
actually going to use?

Probably not, but that's not relevant. malloc isn't the system call
that adds memory to the process, sbrk is. When malloc find that the
heap is used up, it probably DOES request more memory with sbrk than it
needs just to satisfy the current request.

 

[Jorgen Grahn]

[...]

Where recursion becomes an issue is when you use it for every element of
a sequential data structure. For instance, if a parser's algorithmic
structure were something like:

read_first_token
process_token
recurse(rest of document)

it would probably run into a stack limit on most implementations when
processing any real input.

Most implementations where the compiler doesn't optimise tail recursion
away, anyway.

Eh ... you do understand that 'compiler detects that programmer was a
crackpot and works around that automatically' implies that recursion
is probematic, do you?

It's the other way around -- recursion is less problematic if it can
be compiled into something which runs efficiently. Compilers and
interpreters for functional languages (Haskell, ML, Lisp ...) where
recursion replaces loops, have been doing this for decades.

(Not that I use recursion a lot myself.)

/Jorgen

 

[Dr Nick]

Probably not, but that's not relevant. malloc isn't the system call
that adds memory to the process, sbrk is. When malloc find that the
heap is used up, it probably DOES request more memory with sbrk than it
needs just to satisfy the current request.

Ah! Like Keith I'd often wondered about just why this happens. That
makes a lot of sense: malloc wants big chunks of memory to parcel out
from.

 

[Nobody]

However, if i understand http://linux-mm.org/OOM_Killer correctly
(interesting read, BTW), processes may be killed, but not with a
SIGSEGV, so the program does not crash, but is terminated by the
system. This may not be the desired outcome, but it's not a bug.

It's effectively sent SIGKILL, which cannot be caught, rather than
SIGSEGV, which can be caught.

SIGSEGV isn't really the same thing as a crash (largely because "crash"
isn't a clearly-defined concept). I normally consider a crash to be when
the process' data gets corrupted resulting in the process going out of
control (which usually ends when it receives SIGSEGV due to dereferencing
a bogus pointer).

 

[Niklas Holsti]

for me it is the same recursive function that has to return error; as any other
visible and invisible error; something like

int recursivefunction(int* result, int* value)
{int a, b, c; // esp-=1024 esp<
if(GetCurrentStackPointerValue()<StackLimit-1000)
return -1
....
return recursivefunction(result, value)
}

Can be done in Ada:

function recursivefunction (result, value : access integer)
return integer
is
<declarations...>
begin
<statements...>
return recursivefunction (result, value);
exception
when Storage_Error => return -1;
end recursivefunction;

In the function above, if any of the <statements> or the recursive call
causes stack overflow, the Storage_Error handler is entered and the call
returns -1. If the <declarations> cause stack overflow, the handler for
the present call of recursivefunction is bypassed and the Storage_Error
exception is propagated to the outer call level, entering the handler at
that level.

With the gnat Ada compiler it seems that stack overflow at any point in
the function (declarations or statements) abandons the present call and
propagates Storage_Error to the outer call. So if the stack overflow is
detected on recursion level 9999 it is handled on level 9998. But that
should not matter much.

 

[Kleuskes & Moos]

Nor any portable way to cap non-recursive function calls that overflow
the stack, either.

Of course there is. Do not make the call-tree big enough to do that,
and if there's no recursion involved, it's rather easy to derive a max
stack size and put it in your hardware requirements.

My complaint has nothing to do with recursion; which
is really the point of my objection to your objections to recursion -
the problem you're trying to avoid cannot be absolutely avoided in any
context; and it can be avoided (with less than absolute success) for
recursive programs just as it can be with non-recursive ones.

So, basically, you're saying, since your cannot avoid it absolutely
anyway, all advice is useless, and it's OK to use tail-recursion to
skip through a 2 Mb file. Ok.

Not necessarily; that's just what happens on systems which have SIGSEGV,
or some equivalent mechanism.

Aye. And on systems that haven't got it, results are undefined and
(under some circumstances) may kill someone. As i said, a SIGSEGV is a
luxury item, if you overflow he stack and your system does NOT signal
a segfault, you're in even more trouble. Or rather, the poor sod who's
using your software is in deep shit.

You're like a mechanic telling me how brakes are useless since they
cannot guarantee that you won't run into anything, anyway. Even when
applying the brakes, you can still run over a pedestrian or a 20-ton
truck, so basically brakes are useless.

I'm commenting on two entirely distinct issues.

1. The lack of any portable way for a C code to avoid making a function
call that requires more stack space than is currently available; there's
not even a portable way to recover from the fact that such a call was
made, which would be a markedly inferior solution to this problem.
Handling a SIGSEGV is indeed an example of such an inferior solution,
but it's not mandated by the C standard.

Nope, it's mandated by the POSIX standard instead. But i'm getting
curious, pray describe the superior solution you have in mind.

Secondly if you are making function calls that exhaust the stack (this
time in one go, apparently) either the software you write is pretty
shitty or the platform you're running it on is not suited to your
software and your analysis was pretty shitty.

2. You made a comment about me relying on SIGSEGV; I don't, and I
explained why I can't; but this is only a side issue, not directly
relevant to the first point.

Ok. So you have different ways of dealing with a stack-overflow. Again
i'm curious how you do that. Portably, since you've stressed the
importance of that quality in your software.

My first point would still apply even if I
had no such restrictions placed on my code, and even if it ran on a
platform which misbehaved in some entirely different way when it ran out
of automatically allocated memory.

Ok. lets say that if your software crashes, chances are someone gets
killed. It may seem ridiculous to you, but on one of the projects i
worked on, that was a possible consequence. The project employed 16kB
of ROM and 16kB of RAM, has a clock-frequency of 1-kHz and needs to
run for 10 years on a single battery charge.

So your point applies, and i can't guarantee that a single function-
call won't crash the system. Mission impossible? Mission
irresponsable?

What alternatives do you have?

I'm just glad i _can_ guarantee it does not run out of stack space,
since the call-tree wasn't that high.

It doesn't even matter whether or not
it uses a stack to provide that memory, or some other mechanism, such as
activation records.

I'm getting curious again, what sort of killer-functioncall did you
have in mind? Something which allocates a 2Gb array on stack and
passes it around by value? If that's the case, your design stinks.

Every car I've looked at since my second car search, about 1994, has had
as standard equipment either a buzzer or a flashing light (usually both)
that would provided advance warning if the fuel level was too low. I
would in fact consider any car lacking such warning mechanisms to be
seriously defective.

That wasn't the point.

Where's the buzzer/warning light for approaching the stack limits in C?

If your design is good, you don't need one. If you feel you need one,
C is not the language for you.

The non-portable best that I can do is handling SIGSEGV, which is a
little late; the problem I wanted to avoid has already happened by the
time that signal is raised.

True. And catching a SIGSEGV isn't a good idea, unless you're writing
a debugger. The only portable option (and it's been dubbed a kludge)
is to keep track of recursions manually and implement the damn buzzer
yourself. A better solution is to avoid that kind of situation in the
first place. Laying off recursion goes a long way of achieving that.

For that matter, I'd settle for the analog of a gas gauge - where can I
find it?

Again, if you feel you need thngs like that, C is not the language for
you. Get used to doing you thinking in design-time instead of at run-
time.

I don't want to make this sound like more of a problem than it really
is; I've been writing programs in C for 30 years now despite the lack of
this feature - it hasn't stopped me, and has only occasionally slowed me
down.

Glad to hear that.

However, but I'm aware of the problems that the lack of such a
feature can cause, and of my helplessness in dealing with those problems.

You're NOT helpless. You're merely LATE.

My point is that recursive code makes only a quantitative difference in
how difficult it is to avoid such problems; it's not a fundamental
qualitative difference.

It's perhaps the difference between p=1E10-6 and 0.9, which makes it a
pretty big quantitative difference. And again, with proper analysis
beforehand (and that has been my job for a number of years) you can
reduce it to p=0, which makes it a quantitative difference.

The improvement in the maintainability of the
code because of the use of a recursive algorithm can easily be
sufficient to make up for that difference.

Perhaps on your job. As i mentioned earlier, if you and your customer
can live with the occasional crash, there's no real problem. But
that's your design choice.

Your advice to "avoid recursion, if at all possible" is an overreaction.

In the thread at hand, which started with someone being worried about
stack overflow, it still makes more sense than your "It's the fault of
C for not providing me with a buzzer, flashing lights and a fuel-
gauge. there's nothing you can do about it, so live with it and
recurse the hell out of your processor, since it's much easier that
way."

So i'll stick with my advice, thank-you-very-much.

 

[Dr Nick]

You're like a mechanic telling me how brakes are useless since they
cannot guarantee that you won't run into anything, anyway. Even when
applying the brakes, you can still run over a pedestrian or a 20-ton
truck, so basically brakes are useless.

No, you're the person who is telling me that because I can drive too
fast and kill people I shouldn't be using the accelerator.

 

[Måns Rullgård]

(I'm keeping this in comp.unix.programmer and comp.lang.c for now, since
it still seems relevant to both. Feel free to set followups if that
changes.)

Why? If a program finds it needs more memory, it can always call
malloc() again, or realloc() to increase the size of an existing block.
Can you give an example where it makes sense to allocate a large block
of memory and not use it (or use only a small initial portion of it)?

It sometimes makes sense to allocate a large block and only use small
scattered portions of it to simplify indexing. Using only a small
_initial_ portion obviously never makes sense.

 

[Malcolm McLean]

The only portable option (and it's been dubbed a kludge)
is to keep track of recursions manually and implement the damn buzzer
yourself. A better solution is to avoid that kind of situation in the
first place. Laying off recursion goes a long way of achieving that.

The problem is that if a data structure is inherently recursive then
it can be very difficult to write non-recursive code to traverse it.
The usual solution is to use a stack. However this doesn't really
solve the problem, it just means that the stack overflow occurs, if it
occurs, in a different place.

 

[Willem]

Malcolm McLean wrote:
) The problem is that if a data structure is inherently recursive then
) it can be very difficult to write non-recursive code to traverse it.
) The usual solution is to use a stack. However this doesn't really
) solve the problem, it just means that the stack overflow occurs, if it
) occurs, in a different place.

In a place where you can catch the error and terminate cleanly.

One of the major problems with C is that you cannot reliably handle
stack overflows, unless you roll your own stack.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Casper H.S. Dik]

Ah... That's news. I was under the distinct impression that stack-
overflows are impossible to catch. Please expound on your method to
reliably (and portably) catch stack-overflows in recursive algorithms.

I'm quite curious.

Using an alternate signal stack is able to catch this, but
don't be an a* about asking for "reliably and portability".

Casper
--

 

[Casper H.S. Dik]

Actaully the OOM-killer kills *some* process, not necessarily the one
that just tried to use allocated memory.

Usually the large process such as the most important process
(I'd start with webbrowser as people will expect it to crash anyway)

Casper
--