Does the standard say anything about how deeply nested calls can recurse?  I 
would imagine this is one of those things that's really difficult to 
standardize. Or is this one of those "implementation defined" things, which 
would also seem very difficult to control via the compiler on a modern OS.

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Does the standard say anything about how deeply nested calls can recurse?  I 
> would imagine this is one of those things that's really difficult to 
> standardize. Or is this one of those "implementation defined" things, which 
> would also seem very difficult to control via the compiler on a modern OS.

  That's an interesting question. I don't have the standard here (after all,
it's commercial, so you either have to pay for it, get a free pre-standard
draft, or pirate it), but if I had to guess, it's most probably implementation
defined (the standard *might* recommend a lower limit, but I don't know if
it does).

  In practice you can run out of stack space if you allocate too much on
the stack, and especially if you then recurse deeply. I don't remember now
what kind of error you get in that case (but the end result is probably an
abort()). In many systems the size of the stack can actually be defined from
the outside (iow. the you tell the OS how much stack space it should reserve
for the program you are going to run).

-- 
                                                          - Warp

Post a reply to this message

On 6/22/2011 13:07, Warp wrote:
> (but the end result is probably an abort()).

I would be very, very surprised if it wasn't undefined behavior to violate 
the limits of the stack space.  There's just no good efficient portable way 
of checking on hardware that doesn't do per-access checks (i.e., like a Z80 
or something).

 > In many systems the size of the stack can actually be defined from
> the outside (iow. the you tell the OS how much stack space it should reserve
> for the program you are going to run).

And that's why I'm thinking it can't really be implementation-defined, 
unless the implementation is allowed to define it as "ask the OS."

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> On 6/22/2011 13:07, Warp wrote:
> > (but the end result is probably an abort()).

> I would be very, very surprised if it wasn't undefined behavior to violate 
> the limits of the stack space.  There's just no good efficient portable way 
> of checking on hardware that doesn't do per-access checks (i.e., like a Z80 
> or something).

  You can violate any space by poking with pointers and offset at wild,
but the question was what happens if a function recurses too much and the
function calls run out of stack space.

  The official standard probably defines it as either undefined behavior
or implementation defined, but in practice what happens in most systems
is that the C runtime asks the OS to increase the stack space for that
process, the OS says nope, and then the C runtime aborts with some message.

>  > In many systems the size of the stack can actually be defined from
> > the outside (iow. the you tell the OS how much stack space it should reserve
> > for the program you are going to run).

> And that's why I'm thinking it can't really be implementation-defined, 
> unless the implementation is allowed to define it as "ask the OS."

  AFAIK in most systems the C runtime does indeed ask the OS to increase
the stack space as needed (in a similar way as it asks the OS to increase
heap space as needed).

-- 
                                                          - Warp

Post a reply to this message

On 6/22/2011 14:32, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> On 6/22/2011 13:07, Warp wrote:
>>> (but the end result is probably an abort()).
>
>> I would be very, very surprised if it wasn't undefined behavior to violate
>> the limits of the stack space.  There's just no good efficient portable way
>> of checking on hardware that doesn't do per-access checks (i.e., like a Z80
>> or something).
>
>    You can violate any space by poking with pointers and offset at wild,
> but the question was what happens if a function recurses too much and the
> function calls run out of stack space.

I was aware of what question I asked, yes. :)

>    The official standard probably defines it as either undefined behavior
> or implementation defined, but in practice what happens in most systems
> is that the C runtime asks the OS to increase the stack space for that
> process, the OS says nope, and then the C runtime aborts with some message.

In most multitasking systems with virtual memory running user-space 
applications, yes. And my point is that I don't think there's anything in 
the standard that's going to restrict C to that sort of machine.

In practice, under UNIX and Windows and such, yes, that's what happens. On 
the Amiga 1000? On a Z-80 or 68000 or 8086? No, that's not what happens.

>    AFAIK in most systems the C runtime does indeed ask the OS to increase
> the stack space as needed (in a similar way as it asks the OS to increase
> heap space as needed).

Again, assuming you're talking about a multi-user virtual-memory-based 
operating system with demand paging, implying the hardware has per-access 
memory checking.  On systems without per-access memory checking, you don't 
get that, and it would be odd to include in the standard something that 
would have egregious overhead to enforce on low-end hardware.

Am I missing something?  Was I unclear, or were you just not paying as much 
attention as you usually do?  (Serious question, not intended as a 
criticism. I'm just trying to improve my communication skills.)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Am 22.06.2011 21:50, schrieb Darren New:
> Does the standard say anything about how deeply nested calls can
> recurse? I would imagine this is one of those things that's really
> difficult to standardize. Or is this one of those "implementation
> defined" things, which would also seem very difficult to control via the
> compiler on a modern OS.

Such a limit wouldn't make much sense, as the nesting of calls is 
typically limited by stack size, the use of which highly depends on the 
number of parameters and local variables in a function call. 
Consequently, according to the standard it's not even "implementation 
defined", nor is the behaviour explicitly "undefined" or "unspecified" 
if such limitations are exceeded.

In a typical software production for embedded systems, the maximum 
required stack size will be determined as part as the build process (by 
examining the call tree), and recursive function calls avoided wherever 
possible. An alternative is to run dedicated tests to determine stack 
(and heap) usage, and makes sure it does not reach the device's limits 
minus a safety margin.

In safety critical applications (e.g. car electronics), dedicated memory 
space might be set aside for a separate "high safety" task with limited 
functionality but well-analyzed requirements, which might in turn watch 
the stack usage of any "convenience" parts of the software at run-time 
(e.g. by filling some safety margin just before that software parts' 
stack limit with a predefined pattern and repeatedly checking whether 
that region remains unchanged). If the expected stack size is ever found 
to have been exceeded, the high safety task would then usually try to 
re-start the convenience tasks (to make sure they're not operating on 
corrupt data), and in case of repeated failure disable them entirely, 
possibly reducing the device's functionality to shutting down safely.

Post a reply to this message

On 6/22/2011 16:31, clipka wrote:
> it's not even "implementation defined", nor is the behaviour
> explicitly "undefined" or "unspecified" if such limitations are exceeded.

It seems odd that a standard wouldn't describe what happens, even if only by 
describing it as "undefined what happens if you exceed a limit that the 
standard also doesn't specify." Because if you don't point out "hey, 
function calls may fail in undefined ways", then it would seem you're 
guaranteeing they'll obey the semantics the standard gives them.

> In a typical software production for embedded systems,

Sure, I understand how the things work. Thanks for the description. I just 
wondered what the standard had to say, if anything.  (But I don't wonder 
intensely enough to try to find it in the draft standards. :-)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Am I missing something?  Was I unclear, or were you just not paying as much 
> attention as you usually do?  (Serious question, not intended as a 
> criticism. I'm just trying to improve my communication skills.)

  I'm not understanding what you are not understanding.

  I said that I don't know for certain what the standard says (because I don't
have a copy) but that I would guess it's implementation defined. Then I
commented on how it works in practice in many systems.

-- 
                                                          - Warp

Post a reply to this message

On 6/22/2011 23:38, Warp wrote:
>    I said that I don't know for certain what the standard says (because I don't
> have a copy) but that I would guess it's implementation defined. Then I
> commented on how it works in practice in many systems.

Oh, OK. I understood what you were saying, indeed. Since you basically 
rephrased in your answer the parts I explained I already knew, I thought 
perhaps I hadn't explained it clearly. But you were just rephrasing to 
clarify anything I might have said that sounded right but was actually not 
understood by me. Cool. Thanks!

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

On 06/22/11 21:50, Darren New wrote:
> Does the standard say anything about how deeply nested calls can
> recurse?

Partially: At least 2, because it says that functions can be called
recursively. :-)


> I would imagine this is one of those things that's really
> difficult to standardize. Or is this one of those "implementation
> defined" things, which would also seem very difficult to control via the
> compiler on a modern OS.

there are a lot of limits and other limitations where "no diagnostic is
required". But I cannot find anything about a maximum of function call
nesting levels, neither in C++ 2003 nor in C 99.

Lars R.

Post a reply to this message