malloc's out-of-memory error handling

[Pascal Bolzhauser]

Hi all,

running the following small test program on different unices to test
malloc's out-of-memory error handling with this result:

FreeBSD 3.4-RELEASE - 512 MB malloc: Cannot allocate memory
SunOS 5.7 sparc - 1124 MB malloc: Resource temporarily unavailable
AIX 1 5 - 128 MB malloc: Not enough space
HP-UX B.11.00 9000/785- 1015 MB malloc: Not enough space

Linux 2.2.17 i686 - 588 MB malloc: Cannot allocate memory
Linux 2.4.19 x86_64 - 1958 MB Killed
Linux 2.4.17 i686 - 1802 MB Killed
Linux 2.4.17-mckinley-smp ia64 - 2015 MB Killed

-- snip ----
#include <stdlib.h>
#include <stdio.h>

#define MEG (1024*1024)

int main(int argc, const char* argv[]) {
int chunksize = 128*1024; /* 128 kB chunks */
unsigned long sum = 0; /* allocated memory */

printf("Allocating memory in chunks a %dkB\n", chunksize/1024);
for(;;) {
char* p;
int i;

sum += chunksize;
if (sum % MEG == 0) {
fprintf(stdout, "\r%9lu MB ", sum/MEG);
fflush(stdout);
}
p = malloc(chunksize);
if(!p) {
perror("malloc");
return 1;
}
/* touch the allocated memory space */
for (i=0; i<chunksize; i+= 1024) p[i] = ' ';
};
fprintf(stdout, "\nDone.\n");
return 0;
}
-- snap ----


On newer Linux systems a call to malloc() only returns NULL if there are
no more addresses available. Since older Linux systems and other unices
returns NULL if there is no more physical memory availabel.
Does anyone know why this behavior has changed in Linux?

If my test program tries to access the memory address returned from
malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical memory
availabel, so my program can terminate with an out-of-memory error
instead of being killed?


Thanks,
Pascal

[P.T. Breuer]

Post by Pascal Bolzhauser
On newer Linux systems a call to malloc() only returns NULL if there are
no more addresses available. Since older Linux systems and other unices
returns NULL if there is no more physical memory availabel.
Does anyone know why this behavior has changed in Linux?

It hasn't. It's been configurable for ages. See "memory_overcommit" in
proc.

Up till 2.1 I think it was the default not to allocate memory on
demand, but only on write. Some people got annoyed at malloc always
saying "yes, fine" (calloc will be "better", since it zeros the memory)
and wrote their own gnu_malloc wrappers. So Linus made it configurable
and changed the default way back then to be no-overcommit. I've always
kept it as overcommit.

Post by Pascal Bolzhauser
If my test program tries to access the memory address returned from
malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical memory
availabel,

Don't use memory overcommit, or trample memory as you get it.

Peter

[Martin Blume]

"P.T. Breuer" schrieb

Post by P.T. Breuer

Post by Pascal Bolzhauser
On newer Linux systems a call to malloc() only returns NULL if
there are no more addresses available. Since older Linux
systems and other unices returns NULL if there is no more
physical memory availabel.
Does anyone know why this behavior has changed in Linux?

It hasn't. It's been configurable for ages.
See "memory_overcommit" in proc.

What's the idea behind overcommit?

Regards
Martin

[J***@physik.fu-berlin.de]

Post by Martin Blume
"P.T. Breuer" schrieb

Post by P.T. Breuer

Post by Pascal Bolzhauser
On newer Linux systems a call to malloc() only returns NULL if
there are no more addresses available. Since older Linux
systems and other unices returns NULL if there is no more
physical memory availabel.
Does anyone know why this behavior has changed in Linux?

It hasn't. It's been configurable for ages.
See "memory_overcommit" in proc.

What's the idea behind overcommit?

Many programs are rather bad behaved and malloc() lots and lots of
memory they never use (or only at a much later time), but that won't
work when malloc() fails. That led to the idea of having malloc()
return whatever they ask for but only to try to make good on that
promise when the program actually tries to access to that memory
and to kill the program (or some other program that asked for even
more memory) in case there's not enough memory left.

Regards, Jens

[Casper H.S. Dik]

Post by J***@physik.fu-berlin.de

Post by Martin Blume
What's the idea behind overcommit?

Many programs are rather bad behaved and malloc() lots and lots of
memory they never use (or only at a much later time), but that won't
work when malloc() fails. That led to the idea of having malloc()
return whatever they ask for but only to try to make good on that
promise when the program actually tries to access to that memory
and to kill the program (or some other program that asked for even
more memory) in case there's not enough memory left.

I think it's more because of the way fork() generally behaves and
how we allocate stacks.

With fork() you generally modify only a few pages and then either
exec or exit; w/o overcommit for fork() you may find yourself needed
much more swap space then you actually really use.

But extending overcommit to malloc() is stupid but often unavoidable
in a VM system.

Casper

[Kasper Dupont]

Post by Casper H.S. Dik
I think it's more because of the way fork() generally behaves and
how we allocate stacks.

I agree those are the good arguments for overcommiting.
(Of course it is also woth noticing, that it was probably
easier to implement a system with overcommiting than
accurate accounting).

I'll just go into a litle more detail about the stacks:

Stack space is allocated when needed without any system
call being performed. As the stack pointer grows outside
the stack, you will get a page fault. The fault handler
will know this condition, and if the fault happen on an
address between the stack pointer and a mapping with
the MAP_GROWSDOWN flag, another page is allocated for
that mapping.

There is no way the kernel can know in advance how much
stack space a process is going to use. Except from
looking on the rlimit, but very few processes are actually
going to use all of those 2, 8, or 10 MB that is usually
the limit.

If you cannot or willnot allocate more stack space for a
process, there is no clean way to return an error. It is
not a system call, so there is really no possibility to
return an error. And sending a signal would not be an
option either, as that would require even more stack
space. This leaves only one option, kill the process.

Probably you don't want to kill a process running out of
stack if there is really more memory available. So even
if you cannot commit to this additional page, since you
have already commited to all the virtual memory you have,
you probably want to give the process a page anyway (and
it will usually be available as you rarely use all the
memory you have commited to).

[David Schwartz]

Post by Casper H.S. Dik
I think it's more because of the way fork() generally behaves and
how we allocate stacks.
With fork() you generally modify only a few pages and then either
exec or exit; w/o overcommit for fork() you may find yourself needed
much more swap space then you actually really use.
But extending overcommit to malloc() is stupid but often unavoidable
in a VM system.

On x86, code is usually theoretically writable. So every program that
has a shared library mapped could theoretically dirty every single page of
it.

DS

[Kasper Dupont]

Post by David Schwartz
On x86, code is usually theoretically writable. So every program that
has a shared library mapped could theoretically dirty every single page of
it.

Only part of the library is mapped with write access.
If you try to change protection for the read only parts
mprotect could return ENOMEM.

[Nix]

Post by Kasper Dupont

Post by David Schwartz
On x86, code is usually theoretically writable. So every program that
has a shared library mapped could theoretically dirty every single page of
it.

Only part of the library is mapped with write access.

If the library is not PIC, most of it will be read/write and dirtied for you
by ld-linux.so.


(Of course non-PIC shared libraries are normally a bad idea...)

[Andi Kleen]

Post by Martin Blume
"P.T. Breuer" schrieb

Post by P.T. Breuer

Post by Pascal Bolzhauser
On newer Linux systems a call to malloc() only returns NULL if
there are no more addresses available. Since older Linux
systems and other unices returns NULL if there is no more
physical memory availabel.
Does anyone know why this behavior has changed in Linux?

It hasn't. It's been configurable for ages.
See "memory_overcommit" in proc.

What's the idea behind overcommit?

Consider a 1GB process doing system("/bin/ls"); It would do if (fork()
== 0) exec ... Now while the child is active the process temporarily
needs 2GB memory because in theory the child could touch and copy all
memory before calling exec. This used to be a real problem on Sun
based name servers. named would grow quite big, and it would
occasionally fork some small helpers. People had to add quite big swap
partitions that were never needed just to work around the true commit.
Another big issue is with older fortran programs. They don't allow
malloc() easily, so people just declared very big arrays, but only
used small parts of them. With a non overcommit system these fortran
programs don't load at all or only when you waste a lot of disk space
for never used swap space.

In practice having a lot of swap is also not a great advantage
anyways, even with true overcommit. When some process allocates much
more virtual memory than you have real memory it will thrash the whole
system with a swap storm instead of getting killed relatively quickly
when it gets out of control. The bigger the swap the worse the swap
storm.

So even turning off overcommit and adding swap doesn't help very
much. The only thing that helps is to never use significantly more
memory than you have real memory, but a lot of programs don't like
that.

-Andi

[Martin Blume]

"Andi Kleen" schrieb

Post by Andi Kleen

Post by Martin Blume

Post by P.T. Breuer
It hasn't. It's been configurable for ages.
See "memory_overcommit" in proc.

What's the idea behind overcommit?
[From Jens.Toerring]
Many programs are rather bad behaved and malloc() lots and
lots of memory they never use (or only at a much later time),

Consider a 1GB process doing system("/bin/ls");
...
Another big issue is with older fortran programs.
...

Thanks, Andi and Jens for the explanations. Now it makes sense.

Regards
Martin

[Barry Margolin]

Post by Andi Kleen
In practice having a lot of swap is also not a great advantage
anyways, even with true overcommit. When some process allocates much
more virtual memory than you have real memory it will thrash the whole
system with a swap storm instead of getting killed relatively quickly
when it gets out of control. The bigger the swap the worse the swap
storm.

If it never actually *uses* most of that VM that was allocated, why
would it thrash anything? The system should just reserve the blocks in
the swap partition -- this only requires updating some bookkeeping data,
not copying memory pages to/from disk.

I think the rationalization behind overcommitting and then killing some
arbitrary process when swap space is used up is that if you're running
so close to the edge it's a system configuration problem, not something
for the OS designer to accommodate.

[Andi Kleen]

Post by Barry Margolin
would it thrash anything? The system should just reserve the blocks in

The problem are processes that actually use it ("mem hogs")
A process that only "leaks" address space will eventually run out
of it, even on a overcommit system

[btw the default setting of linux is not true overcommit; it does
a very simple check of available mem+swap that can just be very
easily fooled]

Post by Barry Margolin
the swap partition -- this only requires updating some bookkeeping data,
not copying memory pages to/from disk.

Sure, but also big swap partitions that are never used.

Post by Barry Margolin
I think the rationalization behind overcommitting and then killing some
arbitrary process when swap space is used up is that if you're running
so close to the edge it's a system configuration problem, not something
for the OS designer to accommodate.

When you don't have overcommit administrators are forced to add much
more swap than really needed to handle legitimate workloads. And when
you have that much swap the handling of thrashing memhog becomes much
worse because the kernel cannot legitimately kill them early.

-Andi

[P.T. Breuer]

Post by Martin Blume
"P.T. Breuer" schrieb

Post by P.T. Breuer

Post by Pascal Bolzhauser
On newer Linux systems a call to malloc() only returns NULL if

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Post by Martin Blume

Post by P.T. Breuer

Post by Pascal Bolzhauser
there are no more addresses available. Since older Linux

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Post by Martin Blume

Post by P.T. Breuer

Post by Pascal Bolzhauser
systems and other unices returns NULL if there is no more
physical memory availabel.
Does anyone know why this behavior has changed in Linux?

It hasn't. It's been configurable for ages.
See "memory_overcommit" in proc.

What's the idea behind overcommit?

What he said (see underline above). And what I said.

Peter

[Casper H.S. Dik]

Post by Pascal Bolzhauser
FreeBSD 3.4-RELEASE - 512 MB malloc: Cannot allocate memory
SunOS 5.7 sparc - 1124 MB malloc: Resource temporarily unavailable
AIX 1 5 - 128 MB malloc: Not enough space
HP-UX B.11.00 9000/785- 1015 MB malloc: Not enough space
Linux 2.2.17 i686 - 588 MB malloc: Cannot allocate memory

Standards compliant.

Post by Pascal Bolzhauser
Linux 2.4.19 x86_64 - 1958 MB Killed
Linux 2.4.17 i686 - 1802 MB Killed
Linux 2.4.17-mckinley-smp ia64 - 2015 MB Killed

Non compliant.

I think you need to disable "lazy swap allocation" or whatever they
call it (enable memory overcommit?)

Post by Pascal Bolzhauser
If my test program tries to access the memory address returned from
malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical memory
availabel, so my program can terminate with an out-of-memory error
instead of being killed?

The C standard says that such behaviour is not allowed.

Casper

[Stefan Monnier]

Post by Casper H.S. Dik

Post by Pascal Bolzhauser
If my test program tries to access the memory address returned from
malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical memory
availabel, so my program can terminate with an out-of-memory error
instead of being killed?

The C standard says that such behaviour is not allowed.

Interesting. I never noticed that it disallows it. Do you remember which
part of the standard disallows it?


Stefan

[Eric Sosman]

Post by Stefan Monnier

Post by Casper H.S. Dik

Post by Pascal Bolzhauser
If my test program tries to access the memory address returned from
malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical memory
availabel, so my program can terminate with an out-of-memory error
instead of being killed?

The C standard says that such behaviour is not allowed.

Interesting. I never noticed that it disallows it. Do you remember which
part of the standard disallows it?

This has been a topic of recurring debate in the C groups,
because the C Standard has no explicit language prohibiting
lazy allocation. However, the Standard *does* say that if
malloc(non_zero_size) returns a non-NULL pointer, then all
the `non_zero_size' bytes are available for storing data.
An implementation that allows

int *p = malloc(sizeof *p);
if (p != NULL) *p = 42;

to fail is not a conforming implementation.

Of course, the same thing can be said about the ^C key,
CPU time limits, and pulling the electric plug: All these
things and more can cause a C program to stop when the Standard
says it should still be running, so all of them make the
implementation non-conforming. "Usefully non-conforming," one
might say, which leads one to wonder why lazy allocation should
be singled out as Bad when control-C is recognized as Good ...

Personally, I am in the "lazy allocation is Bad" camp.
But I recognize that the infidels on the other side are not
completely devoid of reason.

[Nick Landsberg]

Post by Eric Sosman

Post by Stefan Monnier

Post by Casper H.S. Dik

Post by Pascal Bolzhauser
If my test program tries to access the memory address returned from
malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical
memory availabel, so my program can terminate with an out-of-memory
error instead of being killed?

The C standard says that such behaviour is not allowed.

Interesting. I never noticed that it disallows it. Do you remember which
part of the standard disallows it?

This has been a topic of recurring debate in the C groups,
because the C Standard has no explicit language prohibiting
lazy allocation. However, the Standard *does* say that if
malloc(non_zero_size) returns a non-NULL pointer, then all
the `non_zero_size' bytes are available for storing data.
An implementation that allows
int *p = malloc(sizeof *p);
if (p != NULL) *p = 42;
to fail is not a conforming implementation.
Of course, the same thing can be said about the ^C key,
CPU time limits, and pulling the electric plug: All these
things and more can cause a C program to stop when the Standard
says it should still be running, so all of them make the
implementation non-conforming. "Usefully non-conforming," one
might say, which leads one to wonder why lazy allocation should
be singled out as Bad when control-C is recognized as Good ...
Personally, I am in the "lazy allocation is Bad" camp.
But I recognize that the infidels on the other side are not
completely devoid of reason.

Yes, this seems to be a religious issue. :)

I would agree with you, Eric, but not necessarily
about the "infidels". IMO it is infinitely better to
have a malloc fail with errno set to ENOMEM than for
the program to (randomly) fail later.

You can deal with a malloc failure in the code,
and take steps to recover from it gracefully,
while you can't cleanly deal with it when your program
is "terminated with extreme prejudice" by the OS.

It depends on your application(s). In a production
environment, where restarts of any module are
reportable incidents and are part of the quality
metrics by which the customer evaluates your
product, having processes die seemingly randomly
is not an option.

In a "time sharing" environment, it *may* be acceptable
behavior. (Although it might be hard to explain to
the random user why this program worked yesterday,
and might work tomorrow, but doesn't work today
because some other random user is hogging all
the memory.)

NPL

[Casper H.S. Dik]

Post by Nick Landsberg
You can deal with a malloc failure in the code,
and take steps to recover from it gracefully,
while you can't cleanly deal with it when your program
is "terminated with extreme prejudice" by the OS.

I'm not sure but I remember some OS killing either the
application trying to get more memory or just a random
"biggest" process; chances are, of course, that the
biggest process or the most frequent allocator is
in fact the *most* important process (say your DB
engine) and having that killed because some other
process gobbled up the VM is really bad. A malloc()
return failure can be guarded against; kill -9 can't.

Casper

[Goran Larsson]

Post by Casper H.S. Dik
I'm not sure but I remember some OS killing either the
application trying to get more memory or just a random
"biggest" process; chances are, of course, that the

I have seen IRIX (sgi) killing off system processes, requireing a
reboot after it died, in an attempt to make good on its promise to
provide memory. Absolutely stupid behaviour.

[Igmar Palsenberg]

Post by Casper H.S. Dik
I'm not sure but I remember some OS killing either the
application trying to get more memory or just a random
"biggest" process;

Old linux 2.4 version did this. It even didn't kill the biggest app, but
it used some other criteria. I've had one occasion where it simply
decided to shoot sshd, which is kinda annoying if you log out, can't log
in because sshd is killed, and the console is a 2 hour drive :(

Recent 2.4 kernels simply kill the process requesting the memory.

Post by Casper H.S. Dik
chances are, of course, that the
biggest process or the most frequent allocator is
in fact the *most* important process (say your DB
engine) and having that killed because some other
process gobbled up the VM is really bad. A malloc()
return failure can be guarded against; kill -9 can't.

Ah well... Start an old version of Mozilla, and something will usually
end up being killed :)

Post by Casper H.S. Dik
Casper

Igmar

[Martin Blume]

"Igmar Palsenberg" schrieb

Post by Igmar Palsenberg
Recent 2.4 kernels simply kill the process requesting the memory.

Post by Casper H.S. Dik
chances are, of course, that the
biggest process or the most frequent allocator is
in fact the *most* important process (say your DB
engine) and having that killed because some other
process gobbled up the VM is really bad. A malloc()
return failure can be guarded against; kill -9 can't.

Ah well... Start an old version of Mozilla, and something will
usually end up being killed :)

Mozilla as a replacement for kill, cool :-)
That's why they have the tyrannosaurus as symbol.

LOL
Martin

[Casper H.S. Dik]

Post by Igmar Palsenberg
Old linux 2.4 version did this. It even didn't kill the biggest app, but
it used some other criteria. I've had one occasion where it simply
decided to shoot sshd, which is kinda annoying if you log out, can't log
in because sshd is killed, and the console is a 2 hour drive :(
Recent 2.4 kernels simply kill the process requesting the memory.

I'm not sure what "requesting the memory" means in this context;
the memory has been requested and granted some time ago; the problem
is that the process dies trying to use it. And that might just be
a random process which requested memory a long time ago.

Casper

[Robert Stankowic]

Post by Eric Sosman

Post by Stefan Monnier

Post by Casper H.S. Dik

Post by Pascal Bolzhauser
If my test program tries to access the memory address returned
from malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical
memory availabel, so my program can terminate with an
out-of-memory error instead of being killed?

The C standard says that such behaviour is not allowed.

Interesting. I never noticed that it disallows it. Do you
remember which part of the standard disallows it?

This has been a topic of recurring debate in the C groups,
because the C Standard has no explicit language prohibiting
lazy allocation. However, the Standard *does* say that if
malloc(non_zero_size) returns a non-NULL pointer, then all
the `non_zero_size' bytes are available for storing data.
An implementation that allows
int *p = malloc(sizeof *p);
if (p != NULL) *p = 42;
to fail is not a conforming implementation.
Of course, the same thing can be said about the ^C key,
CPU time limits, and pulling the electric plug: All these
things and more can cause a C program to stop when the Standard
says it should still be running, so all of them make the
implementation non-conforming. "Usefully non-conforming," one
might say, which leads one to wonder why lazy allocation should
be singled out as Bad when control-C is recognized as Good ...
Personally, I am in the "lazy allocation is Bad" camp.
But I recognize that the infidels on the other side are not
completely devoid of reason.

IMHO it's not the lazy allocation which is bad - if the OS finds a way
to suspend a task until the lazy allocated memory is actually
available if requested - and I think it can be made with a clever
memory management.

[Jan Knutar]

Post by Robert Stankowic
IMHO it's not the lazy allocation which is bad - if the OS finds a way
to suspend a task until the lazy allocated memory is actually
available if requested - and I think it can be made with a clever
memory management.

This is prone to deadlock...

[Wolfram Gloger]

Post by Eric Sosman
An implementation that allows
int *p = malloc(sizeof *p);
if (p != NULL) *p = 42;
to fail is not a conforming implementation.
Of course, the same thing can be said about the ^C key,
CPU time limits, and pulling the electric plug: All these
things and more can cause a C program to stop when the Standard
says it should still be running, so all of them make the
implementation non-conforming.

Indeed, all this is in the same category.. Therefore, there is no
point in arguing standard semantics here.

Post by Eric Sosman
Personally, I am in the "lazy allocation is Bad" camp.
But I recognize that the infidels on the other side are not
completely devoid of reason.

So, as one of the infidels, let me point out that _you_ as the system
administrator can decide to avoid "problems" due to lazy allocation by
carefully setting ulimits. On Linux, "ulimit -v" and "ulimit -u" must
be used. Of course you need lots of swap space for this to be
practical, or some sort of semi-dynamic scheme which hands out memory
resources, e.g. at login time.

Regards,
Wolfram.

[James]

On 05 Jul 2004 16:34:45 +0200, Wolfram Gloger

Post by Wolfram Gloger

Post by Eric Sosman
An implementation that allows
int *p = malloc(sizeof *p);
if (p != NULL) *p = 42;
to fail is not a conforming implementation.
Of course, the same thing can be said about the ^C key,
CPU time limits, and pulling the electric plug: All these
things and more can cause a C program to stop when the Standard
says it should still be running, so all of them make the
implementation non-conforming.

Indeed, all this is in the same category.. Therefore, there is no
point in arguing standard semantics here.

Essentially, once you run out of memory, *something* breaks. Maybe
it's malloc() returning zero, maybe it's a SEGV when you use the
address space it returns, but either way your program is about to get
a nasty shock.

Having malloc() return zero as soon as the amount of address space
allocated equals the amount of [virtual] memory available may seem
intuitive at first - but that causes the failure to occur much sooner,
by effectively wasting a large amount of VM as described in earlier
posts. The alternative approach, of waiting until the problem is
unavoidable before you feed errors to the program wanting memory, will
prevent many failures entirely; IMHO, a worthwhile tradeoff in many
cases.


James.

[Casper H.S. Dik]

Post by Wolfram Gloger

Post by Eric Sosman
An implementation that allows
int *p = malloc(sizeof *p);
if (p != NULL) *p = 42;
to fail is not a conforming implementation.
Of course, the same thing can be said about the ^C key,
CPU time limits, and pulling the electric plug: All these
things and more can cause a C program to stop when the Standard
says it should still be running, so all of them make the
implementation non-conforming.

Indeed, all this is in the same category.. Therefore, there is no
point in arguing standard semantics here.

I don't think it's the same thing at all.

^C just doesn't happen unless you want it too; lazy allocation
failing with "kill -9" does.

Post by Wolfram Gloger

Post by Eric Sosman
Personally, I am in the "lazy allocation is Bad" camp.
But I recognize that the infidels on the other side are not
completely devoid of reason.

So, as one of the infidels, let me point out that _you_ as the system
administrator can decide to avoid "problems" due to lazy allocation by
carefully setting ulimits. On Linux, "ulimit -v" and "ulimit -u" must
be used. Of course you need lots of swap space for this to be
practical, or some sort of semi-dynamic scheme which hands out memory
resources, e.g. at login time.

It should not be the default. I don't think ulimits help prevent you
running out of swap; because in the end it is happening on an under
configured system or a system dealing with temporary stress.

Casper

[Wolfram Gloger]

Post by Casper H.S. Dik

Post by Wolfram Gloger
Indeed, all this is in the same category.. Therefore, there is no
point in arguing standard semantics here.

I don't think it's the same thing at all.
^C just doesn't happen unless you want it too; lazy allocation
failing with "kill -9" does.

So you never had a process running on a system that was shut down by
the admin? Eric surely meant SIGINT and not literally "pressing ^C at
the terminal". Of course I _want_ to have a machine with unlimited
resources, which is never rebooted, too.

Post by Casper H.S. Dik

Post by Wolfram Gloger
So, as one of the infidels, let me point out that _you_ as the system
administrator can decide to avoid "problems" due to lazy allocation by
carefully setting ulimits. On Linux, "ulimit -v" and "ulimit -u" must
be used. Of course you need lots of swap space for this to be
practical, or some sort of semi-dynamic scheme which hands out memory
resources, e.g. at login time.

It should not be the default.

What should not be the default? If you mean overcommitment, then IMHO
yes, it should be the default simply because it is gives better
performance: it allows you to run much larger applications.
Disallowing fork() for those applications is not an option.

Post by Casper H.S. Dik
I don't think ulimits help prevent you
running out of swap; because in the end it is happening on an under
configured system or a system dealing with temporary stress.

How so? If you have an "under-configured" system and you run out of
swap, then surely you have set the ulimits too high.

Regards,
Wolfram.

[Casper H.S. Dik]

Post by Wolfram Gloger
So you never had a process running on a system that was shut down by
the admin? Eric surely meant SIGINT and not literally "pressing ^C at
the terminal". Of course I _want_ to have a machine with unlimited
resources, which is never rebooted, too.

That's not what I am saying; there's a big differences between processes
being killed by the person running them or the administrator versus
the inability of a process to deal with resource shortages.

Post by Wolfram Gloger
What should not be the default? If you mean overcommitment, then IMHO
yes, it should be the default simply because it is gives better
performance: it allows you to run much larger applications.
Disallowing fork() for those applications is not an option.

No, the default should be "the system conforms to standard C behaviour".

Casper

[Kasper Dupont]

Post by Casper H.S. Dik
No, the default should be "the system conforms to standard C behaviour".

What is a conformant behaviour in case there is no
more memory left to grow the stack?

[Dragan Cvetkovic]

Post by Kasper Dupont

Post by Casper H.S. Dik
No, the default should be "the system conforms to standard C behaviour".

What is a conformant behaviour in case there is no
more memory left to grow the stack?

Undefined?

Dragan

[Kasper Dupont]

Post by Dragan Cvetkovic

Post by Kasper Dupont

Post by Casper H.S. Dik
No, the default should be "the system conforms to standard C behaviour".

What is a conformant behaviour in case there is no
more memory left to grow the stack?

Undefined?

But that would basically make the behaviour of any
program undefined. You can't be sure there is actually
enough stack space available to call main().

[William Ahern]

Post by Kasper Dupont

Post by Dragan Cvetkovic

Post by Kasper Dupont

Post by Casper H.S. Dik
No, the default should be "the system conforms to standard C behaviour".

What is a conformant behaviour in case there is no
more memory left to grow the stack?

Undefined?

But that would basically make the behaviour of any
program undefined. You can't be sure there is actually
enough stack space available to call main().

Well, a stack isn't defined by the C standard. Unix at least provides
SIGSEV, sigaltstack(2) and siglongjmp(3).

[Kasper Dupont]

Post by William Ahern
Well, a stack isn't defined by the C standard.

You can't do function calls without a stack. It doesn't
have to be implemented in the usual way, it could be
implemented as a linked list if you wanted to. But no
matter how you do it, you need some kind of stack.

What result would conform with the C standard for this
particular program?

#include <stdio.h>
unsigned long f(unsigned long x)
{
if (x==8) return 50;
return f(x+1)+1;
}
int main()
{
printf("%lu\n",f(16));
return 0;
}

[William Ahern]

Post by Kasper Dupont

Post by William Ahern
Well, a stack isn't defined by the C standard.

You can't do function calls without a stack. It doesn't
have to be implemented in the usual way, it could be
implemented as a linked list if you wanted to. But no
matter how you do it, you need some kind of stack.

Fair enough. I suppose the excessively pedantic comment was meant to hint
that the C standard deftly sidesteps the issue by not talking about stacks.

See no evil... etc.

And if you take a page from the C committee and define some reasonable,
conveniently myopic scope then concern about stacks when discussing malloc()
is indeed out of place.

After the fact, you can then make a footnote saying that you lied, calling
malloc() can overflow the stack and you should checkout SIGSEGV, sigaltstack
and siglongjmp.

[Kasper Dupont]

Post by William Ahern

Post by Kasper Dupont

Post by William Ahern
Well, a stack isn't defined by the C standard.

You can't do function calls without a stack. It doesn't
have to be implemented in the usual way, it could be
implemented as a linked list if you wanted to. But no
matter how you do it, you need some kind of stack.

Fair enough. I suppose the excessively pedantic comment was meant to hint
that the C standard deftly sidesteps the issue by not talking about stacks.
See no evil... etc.
And if you take a page from the C committee and define some reasonable,
conveniently myopic scope then concern about stacks when discussing malloc()
is indeed out of place.

Of course the concern about the stack is not specific to
malloc(). It applies whenever you call a function. The
problems are related in that in both cases we are talking
about runing out of memory. Only difference is that in
the case of malloc() we can handle it. I don't know any
way in ANSI C to deal with a stack overflow.

Post by William Ahern
After the fact, you can then make a footnote saying that you lied, calling
malloc() can overflow the stack and you should checkout SIGSEGV, sigaltstack
and siglongjmp.

But those are not ANSI C right. And it doesn't really
answer the question, when is an implementation allowed
to fail to execute a function.

[Robert Redelmeier]

Post by Kasper Dupont
about runing out of memory. Only difference is that in
the case of malloc() we can handle it. I don't know any
way in ANSI C to deal with a stack overflow.

Catch SIGSEGV? setrlimit(RLIMIT_STACK)?

-- Robert

[Kasper Dupont]

Post by Robert Redelmeier

Post by Kasper Dupont
about runing out of memory. Only difference is that in
the case of malloc() we can handle it. I don't know any
way in ANSI C to deal with a stack overflow.

Catch SIGSEGV?

Is SIGSEGV defined in ANSI C? And what about programs
that do not setup any kind of signal handling. Is the
behaviour of a program undefined if it does not setup
a signal handler? Besides when there is no more stack
you cannot execute a handler. Maybe you could use
sigaltstack, but that is not ANSI C.

Can anybody tell me if the example program I posted
has a well defined behavioure? And if not, why?

Post by Robert Redelmeier
setrlimit(RLIMIT_STACK)?

That is not ANSI C, besides I don't see how it could
possibly solve the problem. The kernel could guarantee
that there would always be enough virtual memory
available to grow the stack to this limit. But in
that case you would have fork failing way too often.
Besides how much space is you guaranteed if you
don't touch the limit?

And finally when is the system allowed to run out of
stack space? What if the process could run out of
stack space when trying to call main()? Then all
programs would have undefined behavioure.

Is there an answer to this question somewhere? I
somehow have the feeling, that you couldn't make a
conformant implementation unless you have an infinite
amount of memory.

[Robert Redelmeier]

Post by Kasper Dupont
Is SIGSEGV defined in ANSI C?

Dunno. My Linux manpage says signal() is ANSI C. But SIGSEGV
may be more POSIX than C. IIRC there is MS-DOS ANSI C and
I don't think a realmode x86 would know SIGSEGV from CLI/HLT :)

Post by Kasper Dupont
And what about programs that do not setup any kind of
signal handling.

Well, then they get the default handlers with whatever
`ulimit`s the parent pgm sets up.

Post by Kasper Dupont
Can anybody tell me if the example program I posted has a
well defined behavioure? And if not, why?

I'm no `c` expert, but it looks like it's recursively counting
upwards [sic] from 16 to 8. If it doesn't run out of memory, it
depends on the overflow behaviour of the machine. I don't know
if ANSI C defines such (I doubt it) or specifies word/long size
(32, 36 bits?) or even arithmetic base (trinary, anyone?).

Of course, a really smart optimizing compiler might realize
that the pgm has no run-time dependancies (I/O, foreign
objects) and optimize away all the recursion with constant :)

Post by Kasper Dupont
That is not ANSI C, besides I don't see how it could possibly
solve the problem. The kernel could guarantee that there
would always be enough virtual memory available to grow
the stack to this limit. But in that case you would have
fork failing way too often. Besides how much space is you
guaranteed if you don't touch the limit?

Typical stack limits are 8kB minimum. Lots of room for fork()s.

Post by Kasper Dupont
And finally when is the system allowed to run out of stack
space? What if the process could run out of stack space
when trying to call main()? Then all programs would have
undefined behavioure.

Classically, the stack grows down and the heap grows up.
Nastiness results when they collide. Some OSes put in guardpages.

Post by Kasper Dupont
Is there an answer to this question somewhere? I somehow
have the feeling, that you couldn't make a conformant
implementation unless you have an infinite amount of memory.

Handling all cases is impossible. You cannot make something
foolproof, fools are too ***@mned ingenious! The challenge
of computer programming has always been to fit problems into
available resources (human intelligence limiting more now).

-- Robert

[Kasper Dupont]

Post by Robert Redelmeier

Post by Kasper Dupont
Can anybody tell me if the example program I posted has a
well defined behavioure? And if not, why?

I'm no `c` expert, but it looks like it's recursively counting
upwards [sic] from 16 to 8. If it doesn't run out of memory, it
depends on the overflow behaviour of the machine. I don't know
if ANSI C defines such (I doubt it) or specifies word/long size
(32, 36 bits?) or even arithmetic base (trinary, anyone?).

K&R page 36:

unsigned numbers are always positive or zero, and
obey the laws of arithmetic modulus 2^n, where n
is the number of bits in the type.

So the overflow behaviour for unsigned types is in fact
well defined. And how would you do trinary when the C
standard also specify a lot of bitwise manipulations of
integers?

Post by Robert Redelmeier
Of course, a really smart optimizing compiler might realize
that the pgm has no run-time dependancies (I/O, foreign
objects) and optimize away all the recursion with constant :)

Of course the compiler may do that. But it does not. At
least I didn't find any flags that would make gcc optimize
away the recursion.

Anyway if it would optimize away parts of the recursion,
I can do something more complicated. It is possible to
simulate a turing machine with an infinite tape without
ever calling malloc. I can always allocate more memory
by using recursion. Such a program is impossible to
optimize.

Post by Robert Redelmeier

Post by Kasper Dupont
That is not ANSI C, besides I don't see how it could possibly
solve the problem. The kernel could guarantee that there
would always be enough virtual memory available to grow
the stack to this limit. But in that case you would have
fork failing way too often. Besides how much space is you
guaranteed if you don't touch the limit?

Typical stack limits are 8kB minimum. Lots of room for fork()s.

The ulimit is typically either 2MB, 8MB, or 10MB. So what
are those 8KB you are talking about?

Post by Robert Redelmeier

Post by Kasper Dupont
And finally when is the system allowed to run out of stack
space? What if the process could run out of stack space
when trying to call main()? Then all programs would have
undefined behavioure.

Classically, the stack grows down and the heap grows up.
Nastiness results when they collide. Some OSes put in guardpages.

Well, that is really not the issue here. It is not the
two colliding we are worried about. Many configurations
will run out of physical memory and swap before the
address space is used.

And what I'm discussing here is only the growing stack,
which will with the implementation in Linux and
similar systems, result in a SIGSEGV way earlier as you
hit the stack limit. But is that conforming with ANSI C?
And what if it have to stop before the stack limit
specified with rlimit is reached, for that simple reason
that not enough resources are available?

Post by Robert Redelmeier

Post by Kasper Dupont
Is there an answer to this question somewhere? I somehow
have the feeling, that you couldn't make a conformant
implementation unless you have an infinite amount of memory.

Handling all cases is impossible. You cannot make something
of computer programming has always been to fit problems into
available resources (human intelligence limiting more now).

I still wonder what the program is supposed to do when
there is no more stack. And how early it is allowed to
run out of stack and still be conforming with the C
standard.

[William Ahern]

Kasper Dupont <***@nospam.lir.dk.invalid> wrote:
<snip>

Post by Kasper Dupont
I still wonder what the program is supposed to do when
there is no more stack. And how early it is allowed to
run out of stack and still be conforming with the C
standard.

Here's a copy of the last draft C99 standard:

http://rm-f.net/standards/

AFAIU, it doesn't address the issue at all. And it doesn't address the issue
because it doesn't define a stack. And it probably doesn't define a stack or
mention any implementation details for automatic storage so that it wouldn't
have to dictate a minimum or maximum recursion depth.

So, you're left w/ two choices: decide conformance is impossible or decide
that some behaviors by necessity reside outside the scope of the standard.
(Like whether the presence or absence of a power plug makes the
implementation conformant or non-conformant ;)

[Robert Redelmeier]

Is ANSI C a superset of K&R?

So the overflow behaviour for unsigned types is in fact well defined.

A string of bits _must_ overflow to zero?That should be
made explicit. Some machines might stay stuck at FFFFFFFFh

And how would you do trinary when the C standard
also specify a lot of bitwise manipulations of integers?

You can still do bitwise manipulations, just not in
the usual way :) Like I said, I don't know that the
standard specifies binary and not BCD machines.

Of course the compiler may do that. But it does not. At least I didn't
find any flags that would make gcc optimize away the recursion.

Do you consider gcc to be a highly optimizing compiler? :)

ever calling malloc. I can always allocate more memory by
using recursion. Such a program is impossible to optimize.

Maybe a good reason to avoid writing it? :)

Post by Robert Redelmeier
Typical stack limits are 8kB minimum. Lots of room for fork()s.

The ulimit is typically either 2MB, 8MB, or 10MB. So what
are those 8KB you are talking about?

2 MB is greater than 8kB. I believe Linux won't run with
a stack ulimit below 8kB. One stackpage and one guardpage.
Or it might be a real neat way of making `rsh` :)

And what I'm discussing here is only the growing stack,
which will with the implementation in Linux and similar
systems, result in a SIGSEGV way earlier as you hit the
stack limit. But is that conforming with ANSI C? And what
if it have to stop before the stack limit specified with
rlimit is reached, for that simple reason that not enough
resources are available?

I would be surprised to see minimum resources listed
in a standards document such as ANSI C.

I still wonder what the program is supposed to do when
there is no more stack. And how early it is allowed to run
out of stack and still be conforming with the C standard.

The program probably does nothing because it has been
killed by the OS :)

-- Robert

[Kasper Dupont]

Post by Robert Redelmeier
Is ANSI C a superset of K&R?

K&R is a description of ANSI C.

Post by Robert Redelmeier

So the overflow behaviour for unsigned types is in fact well defined.

A string of bits _must_ overflow to zero?That should be
made explicit. Some machines might stay stuck at FFFFFFFFh

You don't think "laws of arithmetic modulus 2^n" is
explicit enough?

Post by Robert Redelmeier

And how would you do trinary when the C standard
also specify a lot of bitwise manipulations of integers?

You can still do bitwise manipulations, just not in
the usual way :) Like I said, I don't know that the
standard specifies binary and not BCD machines.

Arithmetic modulus 2^n would be a bit tricky on BCD
machines.

Post by Robert Redelmeier

Of course the compiler may do that. But it does not. At least I didn't
find any flags that would make gcc optimize away the recursion.

Do you consider gcc to be a highly optimizing compiler? :)

It really doesn't matter. I wasn't the one to bring up
optimization, because I consider it irrelevant to this
discussion. A clever optimizer could remove recursion
from my example. I kept the program simple to demonstrate
my point. But even if the program could be optimized, the
standard certainly doesn't require that a compiler optimize
away recursion from this case. And you can always come up
with an example that cannot be optimized.

Post by Robert Redelmeier

ever calling malloc. I can always allocate more memory by
using recursion. Such a program is impossible to optimize.

Maybe a good reason to avoid writing it? :)

Why did you remove the important part and reply only to
the second half of the statement, that doesn't make any
sense on its own.

The part that is impossible to optimize is the simulation
of a TM. And that is impossible no matter how it is
implemented. The only reason I suggested to do it on the
stack without using malloc, was such that you couldn't
say my program was buggy for not considering an error
from malloc.

Post by Robert Redelmeier

Post by Robert Redelmeier
Typical stack limits are 8kB minimum. Lots of room for fork()s.

The ulimit is typically either 2MB, 8MB, or 10MB. So what
are those 8KB you are talking about?

2 MB is greater than 8kB. I believe Linux won't run with
a stack ulimit below 8kB. One stackpage and one guardpage.

The guardpage really shouldn't be included in the limit.
After all it doesn't really consume any memory. I'm not
actually sure Linux does provide a guard page between
the stack and other allocations, but it surely should.

Post by Robert Redelmeier
Or it might be a real neat way of making `rsh` :)

Huh?

Post by Robert Redelmeier

And what I'm discussing here is only the growing stack,
which will with the implementation in Linux and similar
systems, result in a SIGSEGV way earlier as you hit the
stack limit. But is that conforming with ANSI C? And what
if it have to stop before the stack limit specified with
rlimit is reached, for that simple reason that not enough
resources are available?

I would be surprised to see minimum resources listed
in a standards document such as ANSI C.

I just looked a bit on C99, and it does provide some
minimums. But the wording is a bit silly. "be able to
translate and execute at least one program". So you
could create one program using this amount and let
the compiler recognize it and optimize it to do
nothing.

Post by Robert Redelmeier

I still wonder what the program is supposed to do when
there is no more stack. And how early it is allowed to run
out of stack and still be conforming with the C standard.

The program probably does nothing because it has been
killed by the OS :)

The question was if that was allowed according to
ANSI C. (Or whatever standard you consider authoritative).

[Robert Redelmeier]

Post by Kasper Dupont
K&R is a description of ANSI C.

How could it be, when ANSI C came later?

Post by Kasper Dupont

Post by Robert Redelmeier

ever calling malloc. I can always allocate more memory by
using recursion. Such a program is impossible to optimize.

Maybe a good reason to avoid writing it? :)

Why did you remove the important part and reply only to
the second half of the statement, that doesn't make any
sense on its own.

Did you not see the smiley :) ? My remark was humor.

Of course anyone can overflow a machine by recursion or other
request at more memory than is available. I do not know that
there is any `C`, POSIX, or other generally accepted definition
of what system behaviour should be. Probably because the subject
is controversial, there is no universally accepted best action
(kill requestor, kill newest, kill biggest, lockup solid, etc)
and it really ought to be configurable.

Post by Kasper Dupont

Post by Robert Redelmeier
Or it might be a real neat way of making `rsh` :)

Huh?

More humor! If the system doesn't give _any_ stackspace to
processes, most will segfault immediately, doing nothing,
like /bin/false or a very restricted shell!

Post by Kasper Dupont
I just looked a bit on C99, and it does provide some
minimums. But the wording is a bit silly. "be able to
translate and execute at least one program". So you could
create one program using this amount and let the compiler
recognize it and optimize it to do nothing.

So "Hello, World!" is enough? I'm not surprised.

Post by Kasper Dupont
The question was if that was allowed according to ANSI
C. (Or whatever standard you consider authoritative).

As you have discovered, the standards appear very lax in this area.
Quite likely by design. How tight should the standards be? Would
you care to suggest, for example, a minimum depth of recursion?
Please remember than ANSI C is used for embedded processors,
some of which only have 256 bytes of RAM.

-- Robert

[Kasper Dupont]

Post by Robert Redelmeier

Post by Kasper Dupont
K&R is a description of ANSI C.

How could it be, when ANSI C came later?

I should have mentioned that it is the second edition of K&R.

Post by Robert Redelmeier

Post by Kasper Dupont
I just looked a bit on C99, and it does provide some
minimums. But the wording is a bit silly. "be able to
translate and execute at least one program". So you could
create one program using this amount and let the compiler
recognize it and optimize it to do nothing.

So "Hello, World!" is enough? I'm not surprised.

Maybe I should have provided a bit more context. Page 20:

The implementation shall be able to translate and
execute at least one program that contains at least
one instance of every one of the following limits:

And then goes 22 different limits. But since it has to
be able to handle just one such program, it could be a
very complicated implementation of hello world, that
this compiler knows how to deal with. And any other
source file could be rejected as beyond environmental
limits. Of course such a compiler would be stupid and
completely useless, but aparently conformant.

Post by Robert Redelmeier
Please remember than ANSI C is used for embedded processors,
some of which only have 256 bytes of RAM.

Some of the limits are hard to handle with 256 bytes
of RAM, like 127 arguments in one function call.

[Robert Redelmeier]

Post by Kasper Dupont
And then goes 22 different limits. But since it has to
be able to handle just one such program, it could be a
very complicated implementation of hello world, that

I don't _think_ anyone would be so stupid as to try to
cheat the limits with a "gamed" compiler (unlike SPEC)
1but I suspect the std is written that way to to be able
to _prove_ compliance. "Look Ma! It runs". Covering
all cases is impossible.

Post by Kasper Dupont
Some of the limits are hard to handle with 256 bytes
of RAM, like 127 arguments in one function call.

Ah, but `c` is call-by-value. What about char arguments?
Or on a 16 bit machine (MS-DOS)?

-- Robert

[Goran Larsson]

Post by Kasper Dupont

Post by Robert Redelmeier
How could it be, when ANSI C came later?

I should have mentioned that it is the second edition of K&R.

Even the second edition of K&R (1988) came out before ANSI C (1989).

[Brian Raiter]

Post by Goran Larsson

Post by Kasper Dupont

Post by Robert Redelmeier
How could it be, when ANSI C came later?

I should have mentioned that it is the second edition of K&R.

Even the second edition of K&R (1988) came out before ANSI C (1989).

However, the fact that there was no third edition really is indicative
of how close K&R2 describes the language that was in fact ratified.
Probably the biggest divergence in K&R2 is the lack of information
about stddef.h. (Maybe this is why so many C programmers are unaware
of offsetof().)

See http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html for dmr's list of
errata for K&R2.

b

[Nix]

Post by Kasper Dupont

Post by Robert Redelmeier
Typical stack limits are 8kB minimum. Lots of room for fork()s.

The ulimit is typically either 2MB, 8MB, or 10MB. So what
are those 8KB you are talking about?

Kernel stacks.

(Hm, better make that `4Kb', actually.)

[Brian Raiter]

And finally when is the system allowed to run out of stack space?
What if the process could run out of stack space when trying to call
main()? Then all programs would have undefined behavioure.

A comforming implementation is required to allow for a minimum amount
of several miscellaneous environmental limits, of which one is the
number of nested function calls. (I don't have my copy of the standard
at hand and I don't remember the actual minimum number that the
standard requires, but I assure you that it is higher than one.)

If a program exceeds one of the environmental limits of a given
conforming implementation, then the behavior of the program is
undefined. For those of you completely unfamiliar with the C standard,
that means that all bets are off and the implementation can do
whatever the hell it wants, including e.g. raising a SIGSEV.

b

[Kasper Dupont]

Post by Brian Raiter

And finally when is the system allowed to run out of stack space?
What if the process could run out of stack space when trying to call
main()? Then all programs would have undefined behavioure.

A comforming implementation is required to allow for a minimum amount
of several miscellaneous environmental limits, of which one is the
number of nested function calls. (I don't have my copy of the standard
at hand and I don't remember the actual minimum number that the
standard requires, but I assure you that it is higher than one.)

It cannot be as simple as specifying a nesting depth,
because that certainly depends on the size of the
stack frames (i.e. the number of local variables).

But I guess it would be possible to come up with
some decent definition based on the number of local
variables and the nesting depth.

Post by Brian Raiter
If a program exceeds one of the environmental limits of a given
conforming implementation, then the behavior of the program is
undefined. For those of you completely unfamiliar with the C standard,
that means that all bets are off and the implementation can do
whatever the hell it wants, including e.g. raising a SIGSEV.

In that case my example would be undefined. Because
an implementation is surely allowed to make an
unsigned long larger than whatever limits on the
nesting depth and local variables is mentioned in
the standard.

[Stefan Monnier]

Post by Robert Redelmeier
setrlimit(RLIMIT_STACK)?

How many bytes of stack are used by any given activation frame?
I know for `alloca' how much stack space is used (plus or minus a little
something) but every other stack allocation is done implicitly and uses an
amount of space that depends on the architecture, the calling convention in
use, ...


Stefan

[Robert Redelmeier]

Post by Stefan Monnier
How many bytes of stack are used by any given activation frame?

From the top down Linux/x86:
calling parms (0 - many bytes)
return addr (4 bytes)
saved EBP (4 bytes unless gcc -fomit-frame-pointer)
local callee vars (0 - MANY MANY bytes)

So 4 bytes minimum.

-- Robert

[David Schwartz]

Post by Kasper Dupont

Post by William Ahern
Well, a stack isn't defined by the C standard.

You can't do function calls without a stack.

Nonsense. You most certainly can. The stack is an implementation detail.
A conformant implementation must hide it.

Post by Kasper Dupont
It doesn't
have to be implemented in the usual way, it could be
implemented as a linked list if you wanted to. But no
matter how you do it, you need some kind of stack.

So long as you define a "stack" as "wherever you happen to store
function parameters", sure you have to store them somewhere. But if it's a
linked list, it's not a "stack" by the usual definition.

Post by Kasper Dupont
What result would conform with the C standard for this
particular program?
#include <stdio.h>
unsigned long f(unsigned long x)
{
if (x==8) return 50;
return f(x+1)+1;
}
int main()
{
printf("%lu\n",f(16));
return 0;
}

Each time it needed more memory, it could suspend the program until
memory was available.

DS

[Kasper Dupont]

Post by David Schwartz
So long as you define a "stack" as "wherever you happen to store
function parameters", sure you have to store them somewhere. But if it's a
linked list, it's not a "stack" by the usual definition.

AFAIR a stack is defined as a data structure where you
can insert elements and take them out again in the
opposite order. And a stack certainly can be implemented
as a linked list.

[David Schwartz]

Post by Kasper Dupont

Post by William Ahern
Well, a stack isn't defined by the C standard.

You can't do function calls without a stack.

Nonsense. You most certainly can. The stack is an implementation detail.
A conformant implementation must hide it.

Post by Kasper Dupont
It doesn't
have to be implemented in the usual way, it could be
implemented as a linked list if you wanted to. But no
matter how you do it, you need some kind of stack.

So long as you define a "stack" as "wherever you happen to store
function parameters", sure you have to store them somewhere. But if it's a
linked list, it's not a "stack" by the usual definition.

Post by Kasper Dupont
What result would conform with the C standard for this
particular program?
#include <stdio.h>
unsigned long f(unsigned long x)
{
if (x==8) return 50;
return f(x+1)+1;
}
int main()
{
printf("%lu\n",f(16));
return 0;
}

Each time it needed more memory, it could suspend the program until
memory was available.

DS

[Kasper Dupont]

Post by Wolfram Gloger
What should not be the default? If you mean overcommitment, then IMHO
yes, it should be the default simply because it is gives better
performance: it allows you to run much larger applications.

Performance? Accounting is certainly not going to
cost you much in terms of additional CPU and memory
usage. So as long as you don't reach the limit, there
should be no measurable difference in performance.

Yes, you can run larger applications if overcommitment
is enabled, but you could do that as well if you just
increased the amount of swap. If you have enough swap
and the same memory usage in your applications, there
will be no difference between having overcommitment
enabled and disabled.

As for the trashing problems mentioned earlier, there
are three "solutions".

1. Fail allocations early.
2. Kill the process.
3. Add lots of swap and just let it trash.

Number 1 can be done either by strict accounting and
litle swap, or by limits. If neither is desirable
there are two options left. And no matter which one
you chose, trashing will start happening at the same
time. You really only have the choice between letting
it trash and killing it. If it needs to be killed, I
would rather do it by hand.

So I think the most relevant question really is, how
do we prevent a single (or a few) trashing process
from having such a bad influence on the overall system
performance, that it becomes more or less impossible
to log in and kill the culprit.

[Wolfram Gloger]

Post by Kasper Dupont

Post by Wolfram Gloger
What should not be the default? If you mean overcommitment, then IMHO
yes, it should be the default simply because it is gives better
performance: it allows you to run much larger applications.

Performance? Accounting is certainly not going to
cost you much in terms of additional CPU and memory
usage. So as long as you don't reach the limit, there
should be no measurable difference in performance.

I didn't mean speed here. I meant "being able to run a program (with
varying memory usage) to completion or not, given a certain amount of
resources".

Post by Kasper Dupont
Yes, you can run larger applications if overcommitment
is enabled, but you could do that as well if you just
increased the amount of swap. If you have enough swap
and the same memory usage in your applications, there
will be no difference between having overcommitment
enabled and disabled.

True, but _given_ a certain amount of RAM and swap (fixed on 99% of
the systems I have used), with overcommitment you will be able to run
bigger apps, e.g. in the common case when they fork-and-exec small
helper processes. Without overcommitment, such a fork() must fail,
because the kernel cannot guess that exec() of a small app will follow
shortly.

Post by Kasper Dupont
So I think the most relevant question really is, how
do we prevent a single (or a few) trashing process
from having such a bad influence on the overall system
performance, that it becomes more or less impossible
to log in and kill the culprit.

Indeed, that must not be allowed to happen.

Regards,
Wolfram.

[Casper H.S. Dik]

Post by Stefan Monnier

Post by Casper H.S. Dik

Post by Pascal Bolzhauser
If my test program tries to access the memory address returned from
malloc it receives a kill signal (which can't be handled).
Any (simple) ideas how to realize that there is no more physical memory
availabel, so my program can terminate with an out-of-memory error
instead of being killed?

The C standard says that such behaviour is not allowed.

Interesting. I never noticed that it disallows it. Do you remember which
part of the standard disallows it?

Please point to the part of the standard that says malloc() is
allowed to return memory you can't use.

Casper