Stack depth

[karthikbalaguru]

Hi,

I have 1 GB RAM and i use Fedora Core.
How many calls can be called recursively so that my stack does not get
corrupted ?
Any ideas ?

Thx in advans,
Karthik Balaguru

 

[Tomás Ó hÉilidhe]

I have 1 GB RAM and i use Fedora Core.
How many calls can be called recursively so that my stack does not get
corrupted ?
Any ideas ?

C programs get compiled to machine code. It is at the machine code
level that the "function call stack" comes into play, so it's possible
for a programmer to write C programs without even knowing what the
function-call stack is (I for one was writing C programs for many
years before I learned how machine code works).

If I knew the answer to your question, I'd give it upfront, but sorry
I don't know. If you want to learn about function-call stacks, I'd say
you'd get a pleasant response at "comp.programming".

As for answering your question regarding Fedora Core, you'd have to
ask someone that knows about Fedora Core. There's a good Linux forum
at "linuxquestions.org", that's where I go with my Linux questions.

 

[Richard Tobin]

I have 1 GB RAM and i use Fedora Core.
How many calls can be called recursively so that my stack does not get
corrupted ?

If making too many recursive function calls causes your stack to get
corrupted, you should switch to another operating system.

A reasonable general-purpose operating system will send you a signal
when you overflow the stack. When his happens depends not on the
amount of RAM you have, but on the amount of virtual memory or some
operating-system-imposed limit on stack size.

-- Richard

 

[Dik T. Winter]

> In article <79bdc22a-8060-4a89-b356-3907273bdef2@k36g2000pri.googlegroups.com>,

>
> If making too many recursive function calls causes your stack to get
> corrupted, you should switch to another operating system.
>
> A reasonable general-purpose operating system will send you a signal
> when you overflow the stack. When his happens depends not on the
> amount of RAM you have, but on the amount of virtual memory or some
> operating-system-imposed limit on stack size.

And on the amount of memory each recursive call takes...

 

[Nate Eldredge]

Hi,

I have 1 GB RAM and i use Fedora Core.
How many calls can be called recursively so that my stack does not get
corrupted ?
Any ideas ?

This is system-specific and not about the C language per se, so I'm
crossposting and setting followups to comp.os.linux.development.apps.

It's not really possible to say exactly, but you can get a rough idea.

First, estimate how much stack space is needed by each call; it should
be approximately equal to the total size of all local variables and
parameters in the function, plus another 8 or 16 bytes or so for the
return address and saved frame pointer.

Next, figure out how much total stack space is available to your
process. Running `ulimit -s' in bash will give you the number in KB. 8
MB is a common default. You can adjust it (for that shell and its
descendants) by giving an argument to `ulimit -s'. You can also say
`ulimit -s unlimited' to allow the stack to grow arbitrarily, limited
only by available memory and swap, and by possibly running into other
parts of the program's memory.

Divide these two numbers.

 

[Andrew Smallshaw]

Next, figure out how much total stack space is available to your
process. Running `ulimit -s' in bash will give you the number in KB. 8
MB is a common default. You can adjust it (for that shell and its
descendants) by giving an argument to `ulimit -s'. You can also say
`ulimit -s unlimited' to allow the stack to grow arbitrarily, limited
only by available memory and swap, and by possibly running into other
parts of the program's memory.

One other point - if using threads your stack space might be much
smaller than you would normally envisage. I know that with UnixWare
the default stack size for new threads is a whole 16Kb. With a
stack that small you don't even need deeply recursive functions if
each iteration uses a reasonable chunk of memory.

 

[CBFalconer]

One other point - if using threads your stack space might be much
smaller than you would normally envisage. I know that with
UnixWare the default stack size for new threads is a whole 16Kb.
With a stack that small you don't even need deeply recursive
functions if each iteration uses a reasonable chunk of memory.

I remember being bitten by a Turbo Pascal system many years ago. I
had a recursive procedure that did some string manipulation. For
each string operation, TP created three 256 byte temporary strings
(for a standard system procedure), which didn't get recovered
(until much later) because the function recursed. The result was
stack overflows. I had to do something peculiar to beat it. This
was under MSDOS, so the stack couldn't be grown beyond 64k in any
circumstance.

 

[Gene]

Hi,

I have 1 GB RAM and i use Fedora Core.
How many calls can be called recursively so that my stack does not get
corrupted ?
Any ideas ?

Nate gave a very good answer except that optmizers can do pretty
exotic inlining of calls (even recursiv ones), which can change
everything.

For a particular function, you can sometimes get an idea of what's
happening by writing incorrect and nonportable C:

#include <stdio.h>

int *base;

int fact(int x)
{
if (!base) base = &x;
printf("stack depth = %u\n", (base > &x) ? base - &x : &x - base);

return x <= 0 ? 1 : x * fact(x - 1);
}

int main(void)
{
int x = 15;
printf("fact(%d) = %d\n", x, fact(x));
return 0;
}

C:\>gcc foo.c
C:\>a
stack depth = 0
stack depth = 8
stack depth = 16
stack depth = 24
stack depth = 32
stack depth = 40
stack depth = 48
stack depth = 56
stack depth = 64
stack depth = 72
stack depth = 80
stack depth = 88
stack depth = 96
stack depth = 104
stack depth = 112
stack depth = 120
fact(15) = 2004310016

But beware. See of you can figure out what's going on here:

C:\>gcc -O4 foo.c
C:\>a
stack depth = 0
stack depth = 8
stack depth = 17
stack depth = 11
stack depth = 12
stack depth = 13
stack depth = 14
stack depth = 15
stack depth = 16
stack depth = 24
stack depth = 33
stack depth = 27
stack depth = 28
stack depth = 29
stack depth = 30
stack depth = 31
fact(15) = 2004310016

 

[Keith Thompson]

These days I believe stack is just virtual memory like everything else
and part of the process' memory map. If you keep consuming stack,
you'll keep adding memory pages. At some point you'll exhaust all
available memory, but I believe you'll run into the total memory limit
for a process and not a limit for the stack.

At least some systems impose a specific limit on stack size. For
example, on one of my computers (it happens to be a Linux system) the
default stack size limit is 8192 kbytes; the system has 1 gigabyte of
physical RAM. (I can change the stack size limit if I want to.)

I wouldn't expect corruption of the stack. Instead, I would expect
the process to be terminated by Linux.

Agreed -- but of course the C standard makes no such guarantees.

[...]

 

[Rainer Weikusat]

One other point - if using threads your stack space might be much
smaller than you would normally envisage. I know that with UnixWare
the default stack size for new threads is a whole 16Kb.

The NPTL-default is to reserve 8M of address space for the (usermode)
stack of each thread, the last page of this being used as a guard page,
ie mapped with no access permissions. This means that a stack overrun
of 4K or less (assuming 4K page size) will result in a segmentation
violation, while writing at sp - 4096 - n, n > 0 (sp ::= stack
pointer) may corrupt the stack of another thread.

In practice, I am running one application with 39 threads, each having
a maximum stacksize of 512K. When all of this would be in use, it
would consume 19.5M of RAM. But the RSS of the process (after six
days) is only 18M, which includes the memory needed by 27 libraries
and all other statically and dynamically allocated 'data areas'.

F'up2 colda.

 

[Ben Bacarisse]

For a particular function, you can sometimes get an idea of what's
happening by writing incorrect and nonportable C:

For the record, it need only be non-portable. It can be "correct"
(for some value of correct) and free from undefined behaviour.

#include <stdio.h>

int *base;

int fact(int x)
{
if (!base) base = &x;
printf("stack depth = %u\n", (base > &x) ? base - &x : &x - base);

You can, I think, remove all the UB like this:

#include <inttypes.h>
...

static void *base;
if (!base) base = &x;
printf("Stack depth = %" PRIdPTR "\n", int_ptr_diff(base, &x));

and then define

intptr_t int_ptr_diff(const void *p1, const void *p2)
{
intptr_t ip1 = (intptr_t)p1, ip2 = (intptr_t)p2;
return ip1 > ip2 ? ip1 - ip2 : ip2 - ip1;
}

 

[James Kuyper]

For the record, it need only be non-portable. It can be "correct"
(for some value of correct) and free from undefined behaviour.


You can, I think, remove all the UB like this:

#include <inttypes.h>
...

static void *base;
if (!base) base = &x;
printf("Stack depth = %" PRIdPTR "\n", int_ptr_diff(base, &x));

and then define

intptr_t int_ptr_diff(const void *p1, const void *p2)
{
intptr_t ip1 = (intptr_t)p1, ip2 = (intptr_t)p2;
return ip1 > ip2 ? ip1 - ip2 : ip2 - ip1;
}

Since intptr_t is an optional type, n order to avoid UB, you need to
surround such code with a #ifdef INTPTR_MAX to verify that the
implementation provides intptr_t. Also note that there's no guarantee
that the subtraction won't overflow.

 

[Ben Bacarisse]

Since intptr_t is an optional type, n order to avoid UB, you need to
surround such code with a #ifdef INTPTR_MAX to verify that the
implementation provides intptr_t.

Agreed. As it stands it avoid UB only where those types are
provided. I'd intended that to be covered by the "non-portable"
description but that is a woolly way to have expressed it.

Also note that there's no guarantee
that the subtraction won't overflow.

I don't understand that. Can you explain?

 

[jameskuyper]

Agreed. As it stands it avoid UB only where those types are
provided. I'd intended that to be covered by the "non-portable"
description but that is a woolly way to have expressed it.


I don't understand that. Can you explain?

A merely unportable aspect of you code is that the standard provides
no guarantees on what values ip1 and ip2 will have. However, that lack
of portability translates into undefined behavior when your code
attempts to evaluate the expression:

ip1 > ip2 ? ip1 - ip2 : ip2 - ip1

For instance, ip1 might be near INTPTR_MAX, while p2 might be near
INTPTR_MIN (or vice versa), in which case the mathematical difference
would be nearly 2*INTPTR_MAX. The corresponding C behavior is
undefined.

 

[Richard Bos]

Forty-two. Or more likely, infinitely many (but some of them may not do
what you want them to do in other ways than corrupting "the", or indeed
any, stack).

C programs get compiled to machine code.

Not even that is necessarily true.

If I knew the answer to your question, I'd give it upfront, but sorry
I don't know. If you want to learn about function-call stacks, I'd say
you'd get a pleasant response at "comp.programming".

Even there the answer will be "nobody can possibly tell".

As for answering your question regarding Fedora Core, you'd have to
ask someone that knows about Fedora Core.

You need a damn sight more information than just the OS variant in use.

Richard

 

[Ben Bacarisse]

A merely unportable aspect of you code is that the standard provides
no guarantees on what values ip1 and ip2 will have. However, that lack
of portability translates into undefined behavior when your code
attempts to evaluate the expression:

ip1 > ip2 ? ip1 - ip2 : ip2 - ip1

For instance, ip1 might be near INTPTR_MAX, while p2 might be near
INTPTR_MIN (or vice versa), in which case the mathematical difference
would be nearly 2*INTPTR_MAX. The corresponding C behavior is
undefined.

Doh! For some mysterious reason, I thought that the conversion to
intptr_t would always be positive! Of course, as you say, it could be
anything. I originally used uintptr_t and I should have stuck with
that.

 

[Bartc]

I also remember that some of the early Microsoft compilers had a "stack
probe" compiler option that you could turn on. Apparently if you put a
lot of automatic variables on the stack and did a memory access to
something more than 1024 bytes beyond the last stack memory access,
something would go wrong and it couldn't grow the stack. The "stack
probe" option generated accesses at the start of every function so it
would work smoothly. You only had to worry if you had 1024 or more bytes
of automatic storage in a function (which is not too common, depending on
what you're doing).

gcc for Windows seems to do the same thing. _alloca() or some such function
is called for large stack frames.

And the stack pointer seems quite low down in virtual memory space
suggesting a limited stack size.

In fact growing the stack automatically doesn't seem that straightforward,
unless the stack grows slowly (because of some 'guard page' just beyond the
stack).

So all the problems you're talking seem alive and well on my system. But
then it is running an ancient copy of Vista.

Anyway, compared to yesteryear, today's systems are trouble-free. If the
program is logically correct, it will run.

I wasn't aware of an 8M soft limit ... interesting. I don't think I've
ever written a program in my life that would use 8M of stack.

Look at the Fibonacci thread on comp.programming for ideas on how to use a
lot of stack.

 

[robertwessel2]

I also remember that some of the early Microsoft compilers had a "stack
probe" compiler option that you could turn on.  Apparently if you put a lot
of automatic variables on the stack and did a memory access to something
more than 1024 bytes beyond the last stack memory access, something would go
wrong and it couldn't grow the stack.  The "stack probe" option generated
accesses at the start of every function so it would work smoothly.  You only
had to worry if you had 1024 or more bytes of automatic storage in a
function (which is not too common, depending on what you're doing).

That's actually pretty common in systems where address space is
allocated to the stack, but no virtual pages are actually assigned
until it's used. Typically the OS catches the access to the next
unassigned page in the stack, and goes ahead and maps in a page. The
problem occurs when the access jumps more than one page ahead (while
the OS *could* just assume in needs to allocate more than one page,
most don't, and assume a bad reference instead). That case gets
handled by including stack probes in any routine what allocates more
than one page worth of local storage. That's a reasonably compromise
since routines with more than a page of local storage are rare, and
the overhead of one memory reference per page is likely to be lost in
most routine that actually have a need for that much storage.

For example, the following generates stack probes in x86-32 MSVC when
array x has more than 4092 chars.

int f(int a)
{
char x[4092];
g(x);
return a;
}