automatic vs allocated attempts

[Stefan Ram]

A definition such as

int i = 0;

within a block will attempt to allocate automatic storage
at runtime, while the evaluation of an expression such as

malloc( sizeof( int ))

will attempt to allocate allocated storage at runtime.

In the second case, it is deemed good practice to handle the
possible case of failure to allocate the storage (i.e., the
case when malloc returns 0.)

But an automatic storage allocation might fail at runtime as
well. C does not provide means for a program to detect and
handle this, however (as far as I know). One could imagine a
programming language, where this is possible, too.

Why does C have this asymmetry between automatic and
allocated storage?

Why is it ok to code in C as if allocations of automatic
storage will never fail, but not ok to code as if
allocations of allocated storage will never fail, when
in fact both might fail?

 

[Thad Smith]

A definition such as

int i = 0;

within a block will attempt to allocate automatic storage
at runtime, while the evaluation of an expression such as

malloc( sizeof( int ))

will attempt to allocate allocated storage at runtime.

In the second case, it is deemed good practice to handle the
possible case of failure to allocate the storage (i.e., the
case when malloc returns 0.)

But an automatic storage allocation might fail at runtime as
well. C does not provide means for a program to detect and
handle this, however (as far as I know). One could imagine a
programming language, where this is possible, too.

Why does C have this asymmetry between automatic and
allocated storage?

That's an interesting question. I suspect that, in general, the maximum
amount of automatic storage is more predictable, but that isn't true in
the general case.

Automatic variables are usually allocated on the invocation to the
containing function. Catching the failure could be done with a new
mechanism for returning a unique error code for
function-invocation-memory-failure. This would take a language change.

It could, with the current language, be detected and reported as a
signal, but signal handling is awkward. Let's see: register a automatic
storage failure signal handler, which sets a global flag, then check the
flag after invocation of potential failing functions.

 

[lacos]

A definition such as

int i = 0;

within a block will attempt to allocate automatic storage
at runtime, while the evaluation of an expression such as

malloc( sizeof( int ))

will attempt to allocate allocated storage at runtime.

In the second case, it is deemed good practice to handle the
possible case of failure to allocate the storage (i.e., the
case when malloc returns 0.)

But an automatic storage allocation might fail at runtime as
well. C does not provide means for a program to detect and
handle this, however (as far as I know). One could imagine a
programming language, where this is possible, too.

Why does C have this asymmetry between automatic and
allocated storage?

Why is it ok to code in C as if allocations of automatic
storage will never fail, but not ok to code as if
allocations of allocated storage will never fail, when
in fact both might fail?

I obviously cannot say anything on behalf of the C standard, but I'll
risk a few practical remarks.

On platforms that conform to some version(s) of the Single UNIX(R)
Specification, officially (by certificate) or "accidentally", you do
notice when you run out of stack. (Not that you should try to handle the
situation.)

http://www.opengroup.org/onlinepubs/9699919799/functions/getrlimit.html

----v----
RLIMIT_STACK

This is the maximum size of the initial thread's stack, in bytes. The
implementation does not automatically grow the stack beyond this limit.
If this limit is exceeded, SIGSEGV shall be generated for the thread. If
the thread is blocking SIGSEGV, or the process is ignoring or catching
SIGSEGV and has not made arrangements to use an alternate stack, the
disposition of SIGSEGV shall be set to SIG_DFL before it is generated.
----^----

If you wish to read about alternate stacks for signal handlers:

http://www.opengroup.org/onlinepubs/9699919799/functions/sigaltstack.html#

Theoretically, one might be able to predefine an alternate stack, and
when a SIGSEGV is delivered to the thread due to the exhaustion of its
"normal" stack, handle it on the alternate stack, by unwinding the
normal stack via siglongjmp() or similar.

In my opinion, you don't have to care about the stack if you follow two
simple guidelines:

- avoid unconstrained (input-dependent) recursion,

- avoid declaring large objects (ie. large arrays) with automatic
storage duration (thus also defining them), even if you know their
maximum size up front.

This will result in a limited number of stack frames (activation
records) at runtime, and those frames will be small -- in the end, if
you avoid big arrays, every individual object you put on the stack or
pass as a function parameter will have to be *named* by you explicitly.

See also

http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory

Cheers,
lacos

 

[lacos]

Theoretically, one might be able to predefine an alternate stack, and
when a SIGSEGV is delivered to the thread due to the exhaustion of its
"normal" stack, handle it on the alternate stack, by unwinding the
normal stack via siglongjmp() or similar.

Example code on an x86_64 Debian Lenny GNU/Linux installation (linux
kernel 2.6.26, gcc Debian 4.3.2-1.1, glibc 2.7-18):



/*
Example code demonstrating handling of stack exhaustion. It may be laughable
to specify the license for such a trivial snippet, but so be it:

Copyright (C) 2010 Laszlo Ersek. Released under the GNU GPLv2+.
*/

#define _XOPEN_SOURCE 500 /* SUSv2 */

#include <setjmp.h> /* sigjmp_buf */
#include <signal.h> /* stack_t */
#include <stdio.h> /* perror() */
#include <stdlib.h> /* EXIT_FAILURE */
#include <signal.h> /* struct sigaction */

static sigjmp_buf env;


static void
segv_handler(int sig)
{
siglongjmp(env, /* val */ 1);
}


static void
bigframe(void)
{
char unsigned buf[6u * 1024u * 1024u] = { 0u };
}


int
main(void)
{
/* Set up alternate signal stack with static storage duration. */
{
stack_t stk;
static char unsigned alt_stack[SIGSTKSZ];

stk.ss_sp = alt_stack;
stk.ss_size = sizeof alt_stack;
stk.ss_flags = 0;
if (-1 == sigaltstack(&stk, 0)) {
perror("sigaltstack()");
return EXIT_FAILURE;
}
}

/* Set up handler for SIGSEGV; make it run on the alternate stack. */
{
struct sigaction sa;

sa.sa_handler = segv_handler;
if (-1 == sigemptyset(&sa.sa_mask)) {
perror("sigemptyset()");
return EXIT_FAILURE;
}
sa.sa_flags = SA_ONSTACK;

if (-1 == sigaction(SIGSEGV, &sa, 0)) {
perror("sigaction()");
return EXIT_FAILURE;
}
}

if (0 == sigsetjmp(env, /* savemask */ 1)) {
/* Direct invocation, trigger SIGSEGV by stack exhaustion. */
bigframe();
}
else {
/* Return from siglongjmp(). */
(void)fprintf(stdout, "oops\n");
}

return EXIT_SUCCESS;
}


$ gcc -ansi -pedantic -Wall -Wextra -o stack stack.c
stack.c:20: warning: unused parameter 'sig'
stack.c: In function 'bigframe':
stack.c:29: warning: unused variable 'buf'

$ ulimit -a | grep stack
stack size (kbytes, -s) 8192

$ ./stack
$ echo $?
0

$ (ulimit -s 4096 && ./stack)
oops
$ echo $?
0


Cheers,
lacos

 

[Nick]

A definition such as

int i = 0;

within a block will attempt to allocate automatic storage
at runtime, while the evaluation of an expression such as

malloc( sizeof( int ))

will attempt to allocate allocated storage at runtime.

In the second case, it is deemed good practice to handle the
possible case of failure to allocate the storage (i.e., the
case when malloc returns 0.)

But an automatic storage allocation might fail at runtime as
well. C does not provide means for a program to detect and
handle this, however (as far as I know). One could imagine a
programming language, where this is possible, too.

Why does C have this asymmetry between automatic and
allocated storage?

Why is it ok to code in C as if allocations of automatic
storage will never fail, but not ok to code as if
allocations of allocated storage will never fail, when
in fact both might fail?

It's a good question particularly as in at least a subset of cases,
malloc failure "never" happens. Certainly on my Linux desktop machine,
I can malloc away until the machine is to all intents and purposes dead
- it's page thrashing like there's no tomorrow, the mouse can hardly
move, but malloc is still cheerily giving back storage.

The only time I've ever seen malloc return NULL here has been when I've
corrupted the malloc data structures in some way. That's still useful,
but there's a big difference to how you might want a program to respond
to "everything's OK with the program, but you've run out of memory"
compared with "you've still got oodles of memory but your program's
faulty".

When you add dynamic arrays:
void f(int n) {
char x[n];
...

which also don't have a failure mechanism, you just add to the
confusion.

It's odd. It's clearly poor practice not to check the return value from
malloc, but I'm not convinced there's anything sensible you can do with
it when you do.

 

[Thad Smith]

It's odd. It's clearly poor practice not to check the return value from
malloc, but I'm not convinced there's anything sensible you can do with
it when you do.

I usually free some allocated space, print an "out of memory" message,
and exit, which at least informs the user what the problem is. It
certainly beats merely assuming that the allocation worked.

I can conceive of programming techniques that grab lots for memory for
an efficient technique, but run a less efficient technique if the
desirable amount of memory is unavailable.

 

[Eric Sosman]

[...]
It's odd. It's clearly poor practice not to check the return value from
malloc, but I'm not convinced there's anything sensible you can do with
it when you do.

You could tell the (interactive) user that the video clip
he's trying to edit is too large, and suggest that he free up
some memory by closing a few others he's opened earlier. Then
return to "neutral state" and await further instructions.

You could say "Not enough memory to sort this entire file
in one gulp; I'll sort in in multiple core-loads, writing each
to a temp file, and then do a merge."

You could say "Omigosh! Let's free() that megabyte I've
hung onto for emergencies, use it for buffers and miscellaneous
purposes while writing work-in-progress checkpoint files, and
do a controlled shutdown that doesn't lose all the user's work."

Or, of course, you could just say SIGSEGV.

 

[Dennis \(Icarus\)]

It's a good question particularly as in at least a subset of cases,
malloc failure "never" happens. Certainly on my Linux desktop machine,
I can malloc away until the machine is to all intents and purposes dead
- it's page thrashing like there's no tomorrow, the mouse can hardly
move, but malloc is still cheerily giving back storage.

Is it a 64-bit machine?

<snip>

Dennis

 

[lacos]

It's a good question particularly as in at least a subset of cases,
malloc failure "never" happens. Certainly on my Linux desktop machine,
I can malloc away until the machine is to all intents and purposes dead
- it's page thrashing like there's no tomorrow, the mouse can hardly
move, but malloc is still cheerily giving back storage.

On Linux, per default, malloc() allocates address space only (if it
enters kernel space via sbrk() or mmap() at all), and tries to provide
backing store on demand. Thus, per default, you won't see a NULL return
value until you exhaust the process' address space.

If the kernel cannot provide physical RAM or swap space as backing store
when a page fault requires it, the infamous OOM killer shows itself and
kills (possibly unrelated) processes.

Many people think this is not a very good approach. Fortunately, you can
ask the linux kernel to allocate backing store synchronously with the
address space.

http://lists.debian.org/debian-mentors/2009/10/msg00191.html

(I think it's worth noting that while linux allows you to seize the full
swap, PLUS a portion of the physical memory (configured by the
"overcommit_ratio" sysctl, see above) at the same time, some operating
systems permit allocations only while there is free swap space, and
physical RAM serves only as a kernel-managed cache for the swap. That's
why you can boot linux with no swap at all.)

You may be able to trigger NULL returns from malloc() in the following
ways:

1) Leave the default "overcommit_memory" setting in place (0), and try
to allocate a bigger address space than your architecture allows for a
single process; for example, 3.5G in a 32-bit process. This should make
address space allocation (mmap()) fail.

2) Set "overcommit_memory" to the most conservative setting (2, don't
overcommit), and try to allocate more memory than your swap space +
(physram * overcommit_ratio %). Such an attempt might be impossible in a
32-bit process on a 64-bit kernel with lots of RAM and/or swap.

3) (easiest) Restrict the address space available to the shell and its
child processes by "ulimit -S -v" in bash.

-o-

For a much better and much more extensive description, see

http://duartes.org/gustavo/blog/post/how-the-kernel-manages-your-memory

and other posts on that blog.

"A VMA is like a contract between your program and the kernel. You ask
for something to be done (memory allocated, a file mapped, etc.), the
kernel says "sure", and it creates or updates the appropriate VMA. But
it does not actually honor the request right away, it waits until a page
fault happens to do real work."


I apologize for any mistakes above, please do point them out. Thanks.

Cheers,
lacos

 

[Nick]

Is it a 64-bit machine?

It is.

 

[Nick]

[...]
It's odd. It's clearly poor practice not to check the return value from
malloc, but I'm not convinced there's anything sensible you can do with
it when you do.

You could tell the (interactive) user that the video clip
he's trying to edit is too large, and suggest that he free up
some memory by closing a few others he's opened earlier. Then
return to "neutral state" and await further instructions.

You could say "Not enough memory to sort this entire file
in one gulp; I'll sort in in multiple core-loads, writing each
to a temp file, and then do a merge."

You could say "Omigosh! Let's free() that megabyte I've
hung onto for emergencies, use it for buffers and miscellaneous
purposes while writing work-in-progress checkpoint files, and
do a controlled shutdown that doesn't lose all the user's work."

Or, of course, you could just say SIGSEGV.

Did you read my post? Having carefully snipped all the context your
reply seems to make sense, but restore it and it's completely against
everything I said. Ditto Thad.

 

[Dennis \(Icarus\)]

It is.

One source I found said Linux 64-bit linux processses have 128 terabyte
address space.
Somewhat envious, as a Windows 64-bit process has 16 gigabytes, 8 of which
is available to the user.

From what I can tell from lacos' post, it may begin returning NULL once
physical ram and swap space have been exhausted.
Given the thrashing you were seeing, it may take awhile for this to occur.

Dennis

 

[Eric Sosman]

Did you read my post? Having carefully snipped all the context your
reply seems to make sense, but restore it and it's completely against
everything I said. Ditto Thad.

Yes, I read your post. Apparently I misunderstood you.

Ditto Thad.

Two responders, two misunderstandings. Hmmm.

 

[Nobody]

I usually free some allocated space, print an "out of memory" message,
and exit, which at least informs the user what the problem is. It
certainly beats merely assuming that the allocation worked.

I can conceive of programming techniques that grab lots for memory for
an efficient technique, but run a less efficient technique if the
desirable amount of memory is unavailable.

Simply handling direct malloc() failures doesn't allow for the situation
where your large allocation barely succeeds, then some library function
tries to allocate a small amount of memory and fails.

If you want to handle memory contention gracefully, you typically have to
customise the malloc() used by library functions to "steal" memory as
necessary, and write your code such that its memory can be stolen as
necessary.

 

[Nick]

Yes, I read your post. Apparently I misunderstood you.

Ditto Thad.

Two responders, two misunderstandings. Hmmm.

Yes I know, that's usually a sign that the author is incoherent!

But as the entire preceding bit of my post was about the fact that
(under some circumstances) malloc returning NULL means anything but out
of memory, replying that the right thing to do is to act as though you
are out of memory surprised me.

Luckily there have been more than two responses now!

 

[Kaz Kylheku]

One source I found said Linux 64-bit linux processses have 128 terabyte
address space.

One very important and reliable source for this information is /the/
source. That source clearly asserts that address spaces are
architecture-dependent.

Look for TASK_SIZE and surrounding definitions in

include/asm-<arch>/processor.h

 

[Richard Bos]

Why does C have this asymmetry between automatic and
allocated storage?

Why is it ok to code in C as if allocations of automatic
storage will never fail, but not ok to code as if
allocations of allocated storage will never fail, when
in fact both might fail?

Hysterical raisins, I presume. That is, it must have been assumed (and
was, AFAIK, common practice in pre-existing languages) that local
storage would only or predominantly be used for small objects (a handful
of single ints, floats or pointers) while static, global or allocated
storage would be used for large arrays and whole blocks of memory.

Richard

 

[Eric Sosman]

Hysterical raisins, I presume. That is, it must have been assumed (and
was, AFAIK, common practice in pre-existing languages) that local
storage would only or predominantly be used for small objects (a handful
of single ints, floats or pointers) while static, global or allocated
storage would be used for large arrays and whole blocks of memory.

It's also the case that the mechanisms for detecting and
reporting (and maybe recovering from) exhaustion of automatic
memory are highly system-specific, varying rather widely from
one environment to the next. Even on a single machine, the
mechanisms available to hosted "user-land" code are usually
different from those applicable in free-standing "kernel" code.
That makes it difficult for a programming language to legislate
one particular way of handling the condition.

malloc(), on the other hand, is not really a creature of
the "core language," but of the library. It can report failure
as a function value -- the fact that functions can return values
is in no way a "special mechanism" just for memory management.
The details of detecting dynamic memory exhaustion can be hidden
safely inside the malloc() implementation, without putting a
structural burden on the rest of the language.

Even so, some implementations get malloc() arguably wrong.
"OOM pa-pa, OOM pa-pa, that's 'ow it goes ..."

 

[Kaz Kylheku]

Why is it ok to code in C as if allocations of automatic
storage will never fail, but not ok to code as if
allocations of allocated storage will never fail, when
in fact both might fail?

The answer to this is multi faceted, and not entirely satisfactory. It
can be summarized by these points:

- malloc can potentially give you access to the full memory resources
of the system, whereas stack space is ``artificially'' limited.
Hence, a malloc failure is an environmental condition, whereas
hitting a stack problem is regarded as an internal problem in
the program. (C programmers are supposed to understand that
stack space is limited; often, the maximum automatic storage
a program can have is nowhere near the amount of dynamic memory
it can ahve).

- It's not unreasonable for programs that handle input of size N to
allocate O(N) dynamic storage. The same cannot be argued for
programs that require (or at least typically require) O(N) automatic
storage (or worse) for input sizes of N; such programs are
incompetently designed, or else, at best, have some pathological
behavior which ought be documented so it can be avoided.
Programmers shoudl study computer science and take steps to avoid
blowing stacks: use tail recursion, or else use divide-and-conquer
type recursion that needs O(log N) space.

- The cause for running out of malloc space may be external; not
attributable to the program which is affected by the failure.
For instance other programs may have gobbled up space.
The cause for blowing a stack is attributable solely to the program.

(But note: in virtual memory systems, both malloc space and the stack
may be lazily allocated, and under overcommit, the program can die
when accessing either malloc space or stack with no detection;
not discussing that configuration here).

- on a note related to the previous point, malloc failures are
recoverable, at least conceptually. It may be the case that system
resources can be freed or added to allow a re-try to succeed. On some
systems we can dynamically add a swap file, increasing the amount of
virtual memory. Even RAM might be hot-swappable. Or we can shut down
some programs. Perhaps we can even dynamically migrate the program to
another compute node which has more local memory available. Recovery
strategies don't make sense with respect to a blown stack: a blown
stack is not OOM (a point raised in bullet #1 above) and so liberating
memory won't help.

- one program module A can cause a malloc failure in another B by
allocating a lot of memory. The failure in B will happen even if A is
not a caller. A and B can be totally unrelated. If a program module A
contributes to a blown stack in B, it must be the case that A is a
direct or indirect caller of B. I.e. functions have to ``conspire''
to blow the stack, so to speak, at least to a greater degree.

- checking for stack allocation failures would be terribly inconvenient;
so much so that if such a thing is provided, it practically requires
exception handling, so that the source program doesn't have to express
the checks, and so that the checking is consistently applied.
Automatic storage is allocated whenever function calls are opened and
block scopes entered. Checking for out-of-stack space at all these
places would be cumbersome, and would not provide any value to
well-behaved programs: well-behaved (from a stack viewpoint) programs
would only look badly written, for not doing the checks. Programmers
writing good code that uses a modest amount of stack space would have
to defend their code against stupid, unfounded accusations of
unreliablity due to missing checks. Myopic project managers would
write coding guidelines calling for these checks to be done
everywhere.

These kinds of checks have to be done 100% consistently everywhere or
not at all. If the 99 stack frames all did the check, but the 100th
nested one does not, and is the one that blows the stack, those 99
checks are for nothing.

Be some of it right or wrong, I think that the above reflects some of
the common reasoning why we get away without checking automatic storage
allocations.