Avoiding recursive stack overflow in C on Unix/Linux?

[Kleuskes & Moos]

There's no way of implementing recursion without some sort of LIFO
structure, which almost always is a stack. C implementations that
don't use stacks usually don't support recursion.

The problem is that if the stack overflows you get undefined
behaviour, usually but not guaranteed to be a crash. There's a
possibility of malicious exploits. For many applications it doesn't
matter, but for many it does, notably safety-critical systems and
popular mass-market applications. In reality I think almost everyone
just sanity tests the depth of recursion.

I could not have said it better than that. Thanx.

 

[boltar2003]

Exactly. And since implementing a stack mechanism with all the
goodities and niceties a demanding programmer wants, is in the range
of Computer Science 101, it's rather superfluous as a language
element.

Best not to mention that to the STL fanboys on comp.lang.c++

B2003

 

[boltar2003]

the stacked subroutine invocations. In an imperative language, it is
essentially a trick which can be used to cause the compiler
generate the necessary state management code (at the expense of a
certain runtime overhead) automatically instead of writing it by
hand.

And its a very useful trick. Unrolling a simple recursive function
that just calls itself is fairly trivial, but if you have recursion such as:

A() -> B() -> C() -> A() ....

then unrolling that into an iterative loop will give you grey hairs to
rival gandalf if the code is sufficiently complex. Not to mention that
fact that most likely all the code from those 3 functions will end up in
one big lump of code in a single function.

And yes - I have seen the above used in language interpreters. eg:

evalUserFunction()
evalExpression()
evalMathsExpression()
evalUserFunction()
etc

B2003

 

[Rainer Weikusat]

Best not to mention that to the STL fanboys on comp.lang.c++

The STL and Std::String were two of three reasons[*] why it stopped
using C++ in 2001. All common data structures are easily implementable
with a couple of hundreds of lines of code and I certainly don't ever
want to go digging for a programming error in this horrendous mess of
'optimizations' intended to provide a generally useful implementation
of something which is rather simple in itself.

[*] The third one was that I had written an 'open source'
802.1x implementation in C++ which was turned into 0xdeadbeef
because it relied on a particular g++ feature (the ability to
define string contants in headers) which was later removed
because the people working on the compiler reportedly couldn't
agree on a way to implement it.

 

[Malcolm McLean]

The STL and Std::String were two of three reasons[*] why it stopped
using C++ in 2001.

Yes, the problem was the syntax for simple arrays got too baroque.

 

[Keith Thompson]

There's no way of implementing recursion without some sort of LIFO
structure, which almost always is a stack. C implementations that
don't use stacks usually don't support recursion.

What exactly do you mean by "stack"? One definition of "stack" is
a LIFO data structure, which makes your first statement trivially
true even without the "almost".

Another common meaning is a contiguous region of memory that grows
and shrinks in a particular direction, typically, but not always,
managed via a hardware "stack pointer" register. It's true that
most C implementations use this kind of stack, but not all do.
There have been C implementations in which the activation record for
each function call is allocated by a mechanism similar to malloc().
Such an implementation has a "stack" in the first sense, but not
in the second.

And an implementation that doesn't support recursion is not a C
implementation (though it might be C-like).

[...]

 

[Malcolm McLean]

What exactly do you mean by "stack"?  One definition of "stack" is
a LIFO data structure, which makes your first statement trivially
true even without the "almost".

Yes, so here I obviously mean "stack" in the sense of contiguous area
of memory with a pointer to the top.

If C implementations don't use stacks, usually they write to fixed
areas of memory, because they are running on tiny platforms with
instruction sets that don't make indirect addressing easy. Recursion
isn't supported, but normally processors like that only ever run one
program in their useful life, which is likely to be controlling a
digital display or something similar.

 

[Kleuskes & Moos]

Yes, so here I obviously mean "stack" in the sense of contiguous area
of memory with a pointer to the top.

If C implementations don't use stacks, usually they write to fixed
areas of memory, because they are running on tiny platforms with
instruction sets that don't make indirect addressing easy. Recursion
isn't supported, but normally processors like that only ever run one
program in their useful life, which is likely to be controlling a
digital display or something similar.

Additionally:

On large CPU's the stack is just a piece of memory. In
microcontrollers (eg. PIC, 68HC11), the call-stack sometimes resides
in a special registerfile and can be quite small, and may not even
have the same width as the rest of the memory.

 

[Ian Collins]

The STL and Std::String were two of three reasons[*] why it stopped
using C++ in 2001.

Yes, the problem was the syntax for simple arrays got too baroque.

Tait's because it's the same as C!

 

[Ian Collins]

[*] The third one was that I had written an 'open source'
802.1x implementation in C++ which was turned into 0xdeadbeef
because it relied on a particular g++ feature (the ability to
define string contants in headers) which was later removed
because the people working on the compiler reportedly couldn't
agree on a way to implement it.

So you're one of those annoying buggers who writes "portable" code that
only compiles with gcc. At least this time you got your comeuppance!

Posted as one who has spent way too much of his working life porting
such "portable" code.

 

[Rainer Weikusat]

[*] The third one was that I had written an 'open source'
802.1x implementation in C++ which was turned into 0xdeadbeef
because it relied on a particular g++ feature (the ability to
define string contants in headers) which was later removed
because the people working on the compiler reportedly couldn't
agree on a way to implement it.

So you're one of those annoying buggers who writes "portable" code
that only compiles with gcc.

By that time (2001), I simply wasn't aware that 'string constants'
defined in C++ headers were 'something special' compared to numeric
constants. In particlar, I didn't know that this required the compiler
to allocate space for the string literal somewhere in the object code
files it was supposed to generate. I simply took it for granted
because the feature had always been there. Also, I wasn't exactly in
the position to even contemplate to get access to a ANSI/ISO standards
document, rather in the position where I was happy during the time of
the month where I had the money to buy food without wandering all over
the city in order to collect deposit bottles first. And the program
even worked in Linux and NetBSD and compiled and ran (to the degree I
could test it) on Solaris 8 (IIRC). That's not something I would spend
any time on today: I use Linux, if you use something else, feel free
to port it yourself :->.

 

[Kleuskes & Moos]

On 05/10/11 12:36 AM, Rainer Weikusat wrote:

       [*] The third one was that I had written an 'open source'
       802.1x implementation in C++ which was turned into 0xdeadbeef
       because it relied on a particular g++ feature (the ability to
       define string contants in headers) which was later removed
       because the people working on the compiler reportedly couldn't
       agree on a way to implement it.

So you're one of those annoying buggers who writes "portable" code
that only compiles with gcc.

By that time (2001), I simply wasn't aware that 'string constants'
defined in C++ headers were 'something special' compared to numeric
constants. In particlar, I didn't know that this required the compiler
to allocate space for the string literal somewhere in the object code
files it was supposed to generate. I simply took it for granted
because the feature had always been there. Also, I wasn't exactly in
the position to even contemplate to get access to a ANSI/ISO standards
document, rather in the position where I was happy during the time of
the month where I had the money to buy food without wandering all over
the city in order to collect deposit bottles first. And the program
even worked in Linux and NetBSD and compiled and ran (to the degree I
could test it) on Solaris 8 (IIRC). That's not something I would spend
any time on today: I use Linux, if you use something else, feel free
to port it yourself :->.

I'm slightly drnk, and under the influence of some prime, dutch weed
(K2 for connaisseurs), so it's probably not the right time to make
comments on a public forum, but this, i feel, needs to be said...

I think i love you...

<sigh>

 

[Kleuskes & Moos]

Best not to mention that to the STL fanboys on comp.lang.c++

STL is a library, not a language element. A superbly useful library at
that. That's exactly where stuff like lists, queues, stack and what
have SHOULD be implemented. After all, it's no use inventing the wheel
all over again every time you need one.

 

[James Kuyper]

Yes, so here I obviously mean "stack" in the sense of contiguous area
of memory with a pointer to the top.

If C implementations don't use stacks, usually they write to fixed
areas of memory, because they are running on tiny platforms with
instruction sets that don't make indirect addressing easy. Recursion
isn't supported, ...

So, as Keith said, those aren't actually C implementations.

How should your comments be understood in the context of things which
actually are C implementations, which don't use stacks, but instead rely
upon activation records?

 

[Michael Press]

STL is a library, not a language element. A superbly useful library at
that. That's exactly where stuff like lists, queues, stack and what
have SHOULD be implemented. After all, it's no use inventing the wheel
all over again every time you need one.

There are good reasons to write it oneself. When I want
a binary search I simply write it on the fly; and embed
whatever I want to do with the search result right there.

It takes as long or longer to write the interfaces to a
library binary search as it does to write one that does
exactly what I want.

 

[Ian Collins]

There are good reasons to write it oneself. When I want
a binary search I simply write it on the fly; and embed
whatever I want to do with the search result right there.

I wish I had the time to rewrite (including the required test cases)
standard algorithms each time I needed one.

It takes as long or longer to write the interfaces to a
library binary search as it does to write one that does
exactly what I want.

What could be simpler than

std::binary_search( start, end, value );

 

[Joshua Maurice]

There are good reasons to write it oneself. When I want
a binary search I simply write it on the fly; and embed
whatever I want to do with the search result right there.

It takes as long or longer to write the interfaces to a
library binary search as it does to write one that does
exactly what I want.

I politely disagree, and I must express my extreme disbelief at this
statement that you can write a good correct binary search algorithm
faster than you can use C++ std::map, or C++ std::lower_bound, et al.

 

[Måns Rullgård]

I politely disagree, and I must express my extreme disbelief at this
statement that you can write a good correct binary search algorithm
faster than you can use C++ std::map, or C++ std::lower_bound, et al.

A binary search is roughly 10 lines of code. Writing one really doesn't
take long.

 

[Ian Collins]

A binary search is roughly 10 lines of code. Writing one really doesn't
take long.

Just ten times longer than calling one!

Then there's the however many lines of unit test cases.

 

[Måns Rullgård]

Just ten times longer than calling one!

You're conveniently glossing over the number of lines required to adapt
to some particular library interface. Also, using a library function
usually involves callbacks for comparing elements, which adds runtime
overhead.

Then there's the however many lines of unit test cases.

Assuming you believe in unit tests at all, testing the unit containing
the search will cover it, and that has to be done regardless of
implementation. I have yet to see anyone write separate unit tests for
every line of code.