Hi,
How does C++ address the issue of the stack overflow?
It seams that the following function counting the depth of a binary
tree:

size_t depth( Node * node ) {
if( node ) {
size_t l = depth( node->left );
size_t r = depth( node->right );
return 1 + max( l, r );
}
else {
return 0;
}
}

may cause an undefined behavior (and most likely crash in this case)
even though, the tree data was correct, and data fit into the system's
memory, but the stack couldn't fit all the local variables, that were
put there recursively during the algorithm execution.

Can the behavior of any program be undefined because we never know if
we caused the stack overflow or not?

Regards,
&rzej

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

> How does C++ address the issue of the stack overflow?

It doesn't.


> Can the behavior of any program be undefined because we never know if
> we caused the stack overflow or not?

Most certainly.


--
Razvan Cojocaru
KeyID: 1024D/04CA34DE

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Aug 6, 11:25 pm, restor <akrze...@interia.pl> wrote:
> Hi,
> How does C++ address the issue of the stack overflow?

C++ does not address the issue of stack allocation and
overflow, since C++ does not know what is stack.

It is quite common that most of the implementations
will use stack as automatic storage, but C++ does/can
not say more about this, because we do not have an
standardized C++ ABI.

> It seams that the following function counting the depth of a binary
> tree:
>
> size_t depth( Node * node ) {
> if( node ) {
> size_t l = depth( node->left );
> size_t r = depth( node->right );
> return 1 + max( l, r );
> }
> else {
> return 0;
> }
>
> }
>
> may cause an undefined behavior (and most likely crash in this case)
> even though, the tree data was correct, and data fit into the system's
> memory, but the stack couldn't fit all the local variables, that were
> put there recursively during the algorithm execution.


The above code is well-formed according to the C++ standard.
But since the resource for underlying platform is limited,
a well-formed program can crash.

The C++ standard committee added Annex B for this kind of QoI
(Quality of Implementation) issues. However, the quantities
listed are only guidelines and do not determine compliance
at all.

> Can the behavior of any program be undefined because we never know if
> we caused the stack overflow or not?

Since every implementation should document the minimal
size for automatic storage, you should be able to calculate
when the stack overflow occurs.

BTW, for the following popular implementations:

* MS visual C++: check /F (Set Stack Size) option.
* GCC: g++ -Wl,--stack,stacksize -o app.exe app.cpp
(replace stacksize with your desired size)

HTH

Jiang


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

> C++ does not address the issue of stack allocation and
> overflow, since C++ does not know what is stack.

You are right. I didn't realize this, but indeed the standard doesn't
define the notion of stack. What is interesting is that it _does_
define stack unwinding.

> The C++ standard committee added Annex B for this kind of QoI
> (Quality of Implementation) issues. However, the quantities
> listed are only guidelines and do not determine compliance
> at all.

> Since every implementation should document the minimal
> size for automatic storage, you should be able to calculate
> when the stack overflow occurs.

But the standard doesn't list anything like "minimal size for
automatic storage" in Appendix B. Does it mean a standard-conformant
compiler may not give me this number?

I never considered this problem when writing code in my work, but I
wonder how the state-of-the-art implementations of STL algorithms
handle the problem of potential shortage of automatic storage.

Regards,
&rzej

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 2008-08-06 12:41:28 -0400, restor <akrzemi1@interia.pl> said:

>> C++ does not address the issue of stack allocation and
>> overflow, since C++ does not know what is stack.
>
> You are right. I didn't realize this, but indeed the standard doesn't
> define the notion of stack. What is interesting is that it _does_
> define stack unwinding.

Yes, but that's unwinding the call stack. That's an abstract notion,
distinct from the stack where auto objects are usually allocated.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 6 août, 16:25, restor <akrze...@interia.pl> wrote:
> Hi,
> How does C++ address the issue of the stack overflow?

It doesn't.
An OS like Linux handles this on a per-process policy, I think, with
per-user max limits. Thanks to the MMU, it can actually grow as
needed.
When the limit is reached, a signal is sent. The default is no limit,
but that's not the default in most linux distributions.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Aug 7, 7:41 am, restor <akrze...@interia.pl> wrote:

> I never considered this problem when writing code in my work, but I
> wonder how the state-of-the-art implementations of STL algorithms
> handle the problem of potential shortage of automatic storage.


Good point, but unfortunately I do not know STL's design policies for
this issue. Maybe P.J. Plauger or Pete Becker can give you the points
if they want.

But generally speaking, the problem can be prevented systematically.
For your above recursive example, you can

1. Estimate your object size and calculate the maximal recursive
count. If it does not meet your needs, try to specify a new stack
size.

2. Also you can set a maximal count for your default stack size.

3. Or, replace auto variables with dynamical/pool allocated objects.

4. Remove the recursion from your program. Recursion is elegant
if used judiciously, however, usually we do not need it at all.


Regards,

Jiang


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Aug 7, 7:41 am, restor <akrze...@interia.pl> wrote:
> > C++ does not address the issue of stack allocation and
> > overflow, since C++ does not know what is stack.
>

[...]

> What is interesting is that it _does_ define stack unwinding.
>

Please note here "stack unwinding" means (15.2/p3):

The process of calling destructors for automatic objects
constructed on the path from a try block to a
throw-expression is called “stack unwinding.”

It shows me that just like std::stack, it has nothing to do with
the implementation's stack storage.
The term "stack unwinding" is not separatable.

Regards,

Jiang


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

> But generally speaking, the problem can be prevented systematically.
> For your above recursive example, you can

I have just realized that it is not the recursion that is the root of
the problem.
The following function may also trigger the overflow of automatic
storage:

char encryptChar( char ch ){
char ans = ch << 2;
return ans;
}

Because automatic storage resource was already full and the tiny char
just made it.

Regards,
&rzej

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 2008-08-07 01:02:28 -0400, Jiang <goo.mail01@yahoo.com> said:

> On Aug 7, 7:41 am, restor <akrze...@interia.pl> wrote:
>
>> I never considered this problem when writing code in my work, but I
>> wonder how the state-of-the-art implementations of STL algorithms
>> handle the problem of potential shortage of automatic storage.
>
>
> Good point, but unfortunately I do not know STL's design policies for
> this issue. Maybe P.J. Plauger or Pete Becker can give you the points
> if they want.

Not much to say. Calling a function uses stack space, and if you run
out of stack, your program crashes. So don't do that. Library code in
general doesn't try to check available stack space.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)



[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]