469,909 Members | 1,617 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,909 developers. It's quick & easy.

calloc/free: a preplexing observation

Hi!

I'm seeking some answers about what seems to be a memory leak.

I have a loop that looks much like this:
double *largeArray = (double*) calloc();
for (...) {
printf("iteration #...\n");
for (...) {
double *foo = (double*) calloc();
.....
.....
largeArray[someIndex] = something;
free(foo);
}
}

Though the actual code is larger, it only differs in 20+ lines of
trivial math performed on stack variables.

Clearly, foo cannot be leaking since it's being freed (and no, it
cannot be allocated outside of the loop, since its size varies each
time.

Now, when I monitor memory usage with top it grows relatively quickly
(300K per pass over the outer loop), thus there ought to be a memory
leak. At first I thought that the "largeArray" was being optimized not
to calloc all at once, but rather on demand, page by page (which would
be bizzarre) but now I believe that might not be the case since the
"largeArray" is about 4000*4000 of double which should be about 16MB -
and I see usage of > 100MB after a few hundred iterations.

I'm using gcc 3.2.2 on i*86 Linux.
Any guesses would be appreciated.

Thanks!

Boris

Nov 14 '05 #1
40 2314
j

<bo***@borisland.com> wrote in message
news:11**********************@c13g2000cwb.googlegr oups.com...
Hi!

I'm seeking some answers about what seems to be a memory leak.

I have a loop that looks much like this:
double *largeArray = (double*) calloc();
for (...) {
printf("iteration #...\n");
for (...) {
double *foo = (double*) calloc();
....
....
largeArray[someIndex] = something;
free(foo);
}
}

Though the actual code is larger, it only differs in 20+ lines of
trivial math performed on stack variables.

Clearly, foo cannot be leaking since it's being freed (and no, it
cannot be allocated outside of the loop, since its size varies each
time.

Now, when I monitor memory usage with top it grows relatively quickly
(300K per pass over the outer loop), thus there ought to be a memory
leak. At first I thought that the "largeArray" was being optimized not
to calloc all at once, but rather on demand, page by page (which would
be bizzarre) but now I believe that might not be the case since the
"largeArray" is about 4000*4000 of double which should be about 16MB -
and I see usage of > 100MB after a few hundred iterations.

I'm using gcc 3.2.2 on i*86 Linux.
Any guesses would be appreciated.


I really do not see an issue with the code you have provided.
(Other than casting where unnecessary). It is too incomplete.
Can you not provide all of it? If not, I would recommend the
use of valgrind here. But that is off-topic for this newsgroup.

--
j
Nov 14 '05 #2
In article <11**********************@c13g2000cwb.googlegroups .com>,
<bo***@borisland.com> wrote:
"largeArray" is about 4000*4000 of double which should be about 16MB -


4000*4000 doubles is 16M * sizeof(double), which is 128MB if you have
8-byte doubles.

-- Richard
Nov 14 '05 #3
On 2005-01-31 12:18:44 -0500, bo***@borisland.com said:
Hi!

I'm seeking some answers about what seems to be a memory leak.
[snip]
... since the
"largeArray" is about 4000*4000 of double which should be about 16MB -
and I see usage of > 100MB after a few hundred iterations.


Do the math again:

4,000 * 4,000
= 16,000,000

If sizeof(double) is 8 then:

8B * 16,000,000
= 128,000,000B
≈ 122 MB

So your usage of > 100MB seems to be right in line with what should be
expected.

--
Clark S. Cox, III
cl*******@gmail.com

Nov 14 '05 #4
Right-O. I'm an idiot: >100MB is exactly the right space usage.
However, why is it not all allocated with the first calloc of
largeArray - why do I see 'top' report ever-growing usage? This is
where I would probably want to use -fprefetch-loop-arrays, which is not
supported on my architecture according to gcc :)

As for providing more code, I could - but the rest of it is just junk -
this is all of the relevant code.

Boris

bo***@borisland.com wrote:
Hi!

I'm seeking some answers about what seems to be a memory leak.

I have a loop that looks much like this:
double *largeArray = (double*) calloc();
for (...) {
printf("iteration #...\n");
for (...) {
double *foo = (double*) calloc();
....
....
largeArray[someIndex] = something;
free(foo);
}
}

Though the actual code is larger, it only differs in 20+ lines of
trivial math performed on stack variables.

Clearly, foo cannot be leaking since it's being freed (and no, it
cannot be allocated outside of the loop, since its size varies each
time.

Now, when I monitor memory usage with top it grows relatively quickly
(300K per pass over the outer loop), thus there ought to be a memory
leak. At first I thought that the "largeArray" was being optimized not to calloc all at once, but rather on demand, page by page (which would be bizzarre) but now I believe that might not be the case since the
"largeArray" is about 4000*4000 of double which should be about 16MB - and I see usage of > 100MB after a few hundred iterations.

I'm using gcc 3.2.2 on i*86 Linux.
Any guesses would be appreciated.

Thanks!

Boris


Nov 14 '05 #5
bo***@borisland.com wrote:
Right-O. I'm an idiot: >100MB is exactly the right space usage.
However, why is it not all allocated with the first calloc of
largeArray - why do I see 'top' report ever-growing usage? This is
where I would probably want to use -fprefetch-loop-arrays, which is not
supported on my architecture according to gcc :)

As for providing more code, I could - but the rest of it is just junk -
this is all of the relevant code.
But it will not work when pasted into some sort of main() function.
Boris

bo***@borisland.com wrote:
Hi!

I'm seeking some answers about what seems to be a memory leak.

I have a loop that looks much like this: #include <stdlib.h>
#include <stdio.h>

int main (void)
{double *largeArray = (double*) calloc(); how much are you calloc()ing.for (...) { where are you looping
printf("iteration #...\n");
for (...) { dito
double *foo = (double*) calloc(); how much are you calloc()ing....
....
largeArray[someIndex] = something; where are someindex and something declared/initialized
free(foo);
}
} where is largeArray free()d

return 0;
}

Now, give us that stuff requested or create a minimal example --
then we can help you.

Note that calloc() does not necessarily make sense for doubles

Please do not top-post.
Cheers
Michael
Though the actual code is larger, it only differs in 20+ lines of
trivial math performed on stack variables.

Clearly, foo cannot be leaking since it's being freed (and no, it
cannot be allocated outside of the loop, since its size varies each
time.

Now, when I monitor memory usage with top it grows relatively quickly
(300K per pass over the outer loop), thus there ought to be a memory
leak. At first I thought that the "largeArray" was being optimized


not
to calloc all at once, but rather on demand, page by page (which


would
be bizzarre) but now I believe that might not be the case since the
"largeArray" is about 4000*4000 of double which should be about 16MB


-
and I see usage of > 100MB after a few hundred iterations.

I'm using gcc 3.2.2 on i*86 Linux.
Any guesses would be appreciated.

Thanks!

Boris


--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Nov 14 '05 #6
bo***@borisland.com writes:
I'm seeking some answers about what seems to be a memory leak.

I have a loop that looks much like this:
double *largeArray = (double*) calloc();
for (...) {
printf("iteration #...\n");
for (...) {
double *foo = (double*) calloc();
....
....
largeArray[someIndex] = something;
free(foo);
}
}

Though the actual code is larger, it only differs in 20+ lines of
trivial math performed on stack variables.

Clearly, foo cannot be leaking since it's being freed (and no, it
cannot be allocated outside of the loop, since its size varies each
time.

Now, when I monitor memory usage with top it grows relatively quickly
(300K per pass over the outer loop), thus there ought to be a memory
leak. At first I thought that the "largeArray" was being optimized not
to calloc all at once, but rather on demand, page by page (which would
be bizzarre) but now I believe that might not be the case since the
"largeArray" is about 4000*4000 of double which should be about 16MB -
and I see usage of > 100MB after a few hundred iterations.


Apart from your miscalculation of the size allocated for largeArray,
there's no guarantee that free() gives memory back to the operating
system. Very likely it stays within your program and becomes
available for further allocation. You don't give us a clue about what
arguments you're giving to calloc(), but it's possible that you're
fragmenting the heap and making it difficult for the system to
re-allocate the memory you've freed.

I would probably add some printf() statements to log all the calls to
calloc() and free(). For example:

double *foo = calloc(something, something_else);
/*
* don't cast the result of malloc() or calloc().
*/
printf("foo = calloc("%lu, %lu) --> [%p]\n",
(unsigned long)something,
(unsigned long)something_else,
(void*)foo);
...
printf("free(foo), foo=[%p]\n", (void*)foo);
free(foo);

Analyze the results and make sure you're freeing everything you
allocate. If not, there's your problem; if so, the displayed
addresses may tell you something, or there may be some system-specific
way to trace the internal behavior of calloc() and free().

Incidentally, it's not safe to assume that calloc() will set all the
doubles in your allocated array to 0.0. It sets the allocated memory
to all-bits-zero. This is often the representation of 0.0, but the
language doesn't guarantee it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #7
bo***@borisland.com wrote:
Right-O. I'm an idiot: >100MB is exactly the right space usage.
However, why is it not all allocated with the first calloc of
largeArray - why do I see 'top' report ever-growing usage? This is
where I would probably want to use -fprefetch-loop-arrays, which is not supported on my architecture according to gcc :)


Probably your operating system is doing 'lazy allocation'. It will
allocate you an address space but not actually claim that memory yet.

Then when you try and access memory in the space you have been
given, it will go and actually allocate that memory.

If there is not actually any memory available then it will die
in a screaming heap, or start swapping endlessly.

I think the point of lazy allocation is so that if a programmer
is lazy and just mallocs a huge chunk at the start, then other
applications do not need to suffer the effects of having not
much memory available.

Nov 14 '05 #8
"Old Wolf" <ol*****@inspire.net.nz> writes:
bo***@borisland.com wrote:
Right-O. I'm an idiot: >100MB is exactly the right space usage.
However, why is it not all allocated with the first calloc of
largeArray - why do I see 'top' report ever-growing usage? This is
where I would probably want to use -fprefetch-loop-arrays, which is
not supported on my architecture according to gcc :)


Probably your operating system is doing 'lazy allocation'. It will
allocate you an address space but not actually claim that memory yet.

Then when you try and access memory in the space you have been
given, it will go and actually allocate that memory.

If there is not actually any memory available then it will die
in a screaming heap, or start swapping endlessly.

I think the point of lazy allocation is so that if a programmer
is lazy and just mallocs a huge chunk at the start, then other
applications do not need to suffer the effects of having not
much memory available.


It's pretty clear that lazy allocation is non-conforming. A program
should be able to determine whether enough memory is available when it
attempts to allocate it; that's why malloc() provides a simple and
clear mechanism for reporting failure. There's no way a program can
fail gracefully if the OS randomly kills it when it tries to access
memory it thinks it's already allocated.

The OP was using calloc(), which zeros the allocated memory, but
perhaps the system simulates that (so that the memory which springs
into existence when it's accessed looks like it's already filled with
zeros).

If your system does lazy allocation, one way to make it act as if it
were more nearly conforming would be to fill the allocated memory
with, say, 0xff bytes immediately after allocating it. That still
won't let it fail gracefully, but at least the failure will occur
sooner rather than later.

An experiment the OP might try is to fill the allocated memory with
some non-zero value immediately after calloc(), then fill it with
zeros again. Obviously this is going to slow things down (so you
won't want to do this in your production version), but it could be
useful to see whether this affects the memory behavior.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #9
In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:
An experiment the OP might try is to fill the allocated memory with
some non-zero value immediately after calloc(), then fill it with
zeros again. Obviously this is going to slow things down (so you
won't want to do this in your production version), but it could be
useful to see whether this affects the memory behavior.


I have seen exactly this method being used in serious production code -
a function "my_malloc ()" with the same arguments as malloc, that would
call malloc (), install a signal handler, fill the malloc ()'d pointer
with some data, and finally return the pointer. If anything went wrong
while filling the allocated memory, the signal handler would stop the
signal from propagating; in that case the pointer was free()d and the
function returned NULL. Truly horrible code to attempt to get a
conforming implementation.
Nov 14 '05 #10
Christian Bau <ch***********@cbau.freeserve.co.uk> writes:
In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:
An experiment the OP might try is to fill the allocated memory with
some non-zero value immediately after calloc(), then fill it with
zeros again. Obviously this is going to slow things down (so you
won't want to do this in your production version), but it could be
useful to see whether this affects the memory behavior.


I have seen exactly this method being used in serious production code -
a function "my_malloc ()" with the same arguments as malloc, that would
call malloc (), install a signal handler, fill the malloc ()'d pointer
with some data, and finally return the pointer. If anything went wrong
while filling the allocated memory, the signal handler would stop the
signal from propagating; in that case the pointer was free()d and the
function returned NULL. Truly horrible code to attempt to get a
conforming implementation.


And the signal handler can't be implemented portably (since there's no
guarantee which signal will be raised if it fails). But it does seem
like a reasonable approach.

If you're willing to go a little further into the land of
non-portability, you can likely save some time by setting only one
byte per memory page. This requires knowing what a memory page is, of
course, and assumes that accessing any byte in a page will trap if and
only if accessing a single byte in the page will trap.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #11
Keith Thompson wrote:
.... snip ...
It's pretty clear that lazy allocation is non-conforming. A program
should be able to determine whether enough memory is available when it
attempts to allocate it; that's why malloc() provides a simple and
clear mechanism for reporting failure. There's no way a program can
fail gracefully if the OS randomly kills it when it tries to access
memory it thinks it's already allocated.


That depends. (ever hear that phrase before ;-). If the memory is
not actually available when usage is attempted, the OS can simply
put the program to sleep until it is available. Remember, there
are no speed guarantees.

However if the action is to abort, then I agree with you.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #12
Keith Thompson wrote:

It's pretty clear that lazy allocation is non-conforming.


It's a different sort of non-conformance to something like,
say, giving the wrong result for a division.

Would you also say that any operating system that allows
the user to kill an application is non-conforming? (because
it allows the application to abort when the C standard says
it should have kept running).

Also, any system where stack overflow is a possibility is
non-conforming (which is pretty much every device with a
stack-based implementation for function calls), unless there
are some limits imposed by the standard which I'm not aware of.
But people have to program on these systems every day.

Nov 14 '05 #13
"Old Wolf" <ol*****@inspire.net.nz> writes:
Keith Thompson wrote:

It's pretty clear that lazy allocation is non-conforming.
It's a different sort of non-conformance to something like,
say, giving the wrong result for a division.


I disagree. malloc() is supposed to return a null pointer to indicate
that the requested memory can't be allocated. If it returns a
non-null pointer, it's non-conforming.
Would you also say that any operating system that allows
the user to kill an application is non-conforming? (because
it allows the application to abort when the C standard says
it should have kept running).
Programs can always be affected by external interactions (shutting off
the power if nothing else). I suppose it could be argued that
allowing the program not to finish is non-conforming, but I'm not
*quite* that picky.
Also, any system where stack overflow is a possibility is
non-conforming (which is pretty much every device with a
stack-based implementation for function calls), unless there
are some limits imposed by the standard which I'm not aware of.
But people have to program on these systems every day.


The standard allows implementations to impose limits.

No realistic implementation can provide unlimited resources (say, for
infinitely deep recursion or a loop that will take a trillion years to
complete). A realistic implementation can provide a malloc() that
doesn't lie to the client.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #14
On Tue, 01 Feb 2005 00:20:27 GMT, Keith Thompson
<ks***@mib.org> wrote:
It's pretty clear that lazy allocation is non-conforming. A program
should be able to determine whether enough memory is available when it
attempts to allocate it; that's why malloc() provides a simple and
clear mechanism for reporting failure. There's no way a program can
fail gracefully if the OS randomly kills it when it tries to access
memory it thinks it's already allocated.
By that standard there are no fully conforming real world C compilers,
because all sorts of things can cause programs to abort (being swapped
out and never swapped back in again, running out of process space,
faulty disk drives, a stray cosmic ray in a RAM chip, etc.).

The OS could allocate the memory but it would not necessarily be 'real'
(it's called virtual memory for that reason); it /should/ make sure that
it doesn't allocate more in total than is available in the system, but
it need not do so (it could, for instance, display a message to the
operator to allocate more swap space, or even to attach a new drive,
when it needed the memory). (Similarly, airline companies should only
book seats they have, and return an error if they are full, but in
practice they assume a nmber of "no-shows" so over-commit their
resources in the hope that something will become free...)
The OP was using calloc(), which zeros the allocated memory, but
perhaps the system simulates that (so that the memory which springs
into existence when it's accessed looks like it's already filled with
zeros).
It could do that with any value, of course.
If your system does lazy allocation, one way to make it act as if it
were more nearly conforming would be to fill the allocated memory
with, say, 0xff bytes immediately after allocating it. That still
won't let it fail gracefully, but at least the failure will occur
sooner rather than later.
Write zeros, then 0xFFs, and then a random bit pattern in case the
system notices that complete allocation units are the same value and
deallocates them. But that still won't make it portable, because the
system is free to do whatever it likes as long as it returns the same
value when read as was written to it (and it can take as long as it
likes, the C standards say nothing about performance, if it saves
everything to backing store and asks the operator to build a new machine
and reload the program that is still conforming).
An experiment the OP might try is to fill the allocated memory with
some non-zero value immediately after calloc(), then fill it with
zeros again. Obviously this is going to slow things down (so you
won't want to do this in your production version), but it could be
useful to see whether this affects the memory behavior.


As I understood it the OP was simply noticing the output of the top(1)
command, which displays certain aspects of the process but not all of
the attributes. Certainly if the OP is interested they can do all sorts
of tests (I routinely run speed tests on various machines and compilers)
but it will only, at most, give a small indication of what the system
will do.

Chris C
Nov 14 '05 #15
Keith Thompson wrote:
"Old Wolf" <ol*****@inspire.net.nz> writes:
Keith Thompson wrote:

It's pretty clear that lazy allocation is non-conforming.


It's a different sort of non-conformance to something like,
say, giving the wrong result for a division.


I disagree. malloc() is supposed to return a null pointer to
indicate that the requested memory can't be allocated. If it
returns a non-null pointer, it's non-conforming.


I would argue that the as-if rule allows the OS to not actually
allocate the memory until it is needed.

Suppose for sake of clarity that the OS waits until memory is
available (if the application tries to write to an address
that hasn't been allocated by the OS yet). Then the application
cannot discern in any way that the memory has not been
allocated and there is no requirement for memory writes to occur
in any time frame.

Furthermore, the OS has actually allocated an address range
in the application's virtual address space. There is no
requirement for the virtual address space to be mapped to a
physical address space at the same time (in fact there can't
be, otherwise we could not have systems with disk-swapped
virtual memory).

Nov 14 '05 #16
"Old Wolf" <ol*****@inspire.net.nz> writes:
Keith Thompson wrote:
"Old Wolf" <ol*****@inspire.net.nz> writes:
> Keith Thompson wrote:
>>
>> It's pretty clear that lazy allocation is non-conforming.
>
> It's a different sort of non-conformance to something like,
> say, giving the wrong result for a division.


I disagree. malloc() is supposed to return a null pointer to
indicate that the requested memory can't be allocated. If it
returns a non-null pointer, it's non-conforming.


I would argue that the as-if rule allows the OS to not actually
allocate the memory until it is needed.

Suppose for sake of clarity that the OS waits until memory is
available (if the application tries to write to an address
that hasn't been allocated by the OS yet). Then the application
cannot discern in any way that the memory has not been
allocated and there is no requirement for memory writes to occur
in any time frame.

[...]

I agree *if* an attempt to access unavailable memory causes the
program to wait until it becomes available. If the attempt causes the
program to abort, the as-if rule doesn't apply.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #17
In article <11**********************@z14g2000cwz.googlegroups .com>,
Old Wolf <ol*****@inspire.net.nz> wrote:
I would argue that the as-if rule allows the OS to not actually
allocate the memory until it is needed.


Right, but if it can then not do so, it's not conforming.

Lazy allocation that guarantees that there will be enough when it's
required is conforming.

-- Richard
Nov 14 '05 #18
On Tue, 01 Feb 2005 23:05:16 +0000, Keith Thompson wrote:
"Old Wolf" <ol*****@inspire.net.nz> writes:
Keith Thompson wrote:

It's pretty clear that lazy allocation is non-conforming.
It's a different sort of non-conformance to something like,
say, giving the wrong result for a division.


I disagree. malloc() is supposed to return a null pointer to indicate
that the requested memory can't be allocated. If it returns a
non-null pointer, it's non-conforming.


What we know is that in the *abstract machine* when malloc() returns
non-null an object has been properly created. What an actual
implementation is required to do is a very different and rather more
complex question. Clause 4p6 says

"A conforming hosted implementation shall accept any strictly conforming
program."

"Accept" is the key word here and the standard doesn't define further what
it means. I suggest that it means "not reject" in the sense of saying "I
won't compile this code because it isn't valid C". Consider that a
strictly conforming program can be arbitrarily long and no real-world
compiler is capable of translating every possible strictly conforming
program. The compiler can say "sorry, I can't translate this" in some
fashion, but not "your program is invalid".

5.1.2.3 places requirement on how an implementation must honour the
semantics of the abstract machine. This is based on observable behaviour
notably on I/O and side-effects notably of volatile objects. 5.1.2.3p5
says

"The least requirements on a conforming implementation are:

- At sequence points, volatile objects are stable in the sense that
previous accesses are complete and subsequent accesses have not yet
occurred.

- At program termination, all data written into files shall be identical
to the result that execution of the program according to the abstract
semantics would have produced.

- The input and output dynamics of interactive devices shall
take place as specified in 7.19.3. The intent of these requirements is
that unbuffered or line-buffered output appear as soon as possible, to
ensure that prompting messages actually appear prior to a program
waiting for input."

Note that what is lacking, and what MUST be lacking if there is any chance
of creating a real-world conforming implementation, is any sense that the
implementation must execute the program successfully to completion. All we
know is that IF a sequence point is reached volatile objects are stable,
IF we reach program termination (see 5.1.2.2.3) file output must match the
abstract machine, IF file I/O to interactive devices happens then it
should behave as per the abstract machine.

The standard doesn't guarantee that a conforming implementation will
execute any strictly conforming program to completion (except one
specified in 5.2.4.1), nor does it place any restrictions on how or why
the execution of a program might fail. All that can really be said is that
to the extent that a program does execute it must be consistent with the
abstract machine.

So, aborting the execution of a program, except the one specified by the
implementation w.r.t. 5.2.4.1, because the implementation doesn't
have enough memory available to continue the execution, is very much
allowed by the standard; not in the abstract machine but in an
implementation. 5.2.4.1 is interesting in that an overcommitting system
must make sure that it doesn't trip up for this program. Maybe. Any
multitasking system that doesn't reserve memory permanently for the
possible translation and execution of this program may find itself unable
unable to do so in some circumstances.

Consider:

void foo(void)
{
char data[1000];

puts("I got here");

data[500] = 0;
}

Let's say an implementation aborted the execution of the program at the
statement data[500] = 0; due to hitting a stack quota limit. It spotted
this when the write operation caused a trap on an unmapped memory page and
it tried to allocate a new one. As far as the abstract machine is
concerned the definition of data causes that object to be fully created
when the block is entered, in much the same way that malloc() has created
an object when it returns non-null (for a non-zero argument). So this
is a non-conforming implementation if you consider overcommitting for
malloc'd memory non-conforming.
Would you also say that any operating system that allows
the user to kill an application is non-conforming? (because
it allows the application to abort when the C standard says
it should have kept running).


Programs can always be affected by external interactions (shutting off
the power if nothing else). I suppose it could be argued that
allowing the program not to finish is non-conforming, but I'm not
*quite* that picky.


But is the standard? I don't see anything to suggest that at all.
Also, any system where stack overflow is a possibility is
non-conforming (which is pretty much every device with a
stack-based implementation for function calls), unless there
are some limits imposed by the standard which I'm not aware of.
But people have to program on these systems every day.


The standard allows implementations to impose limits.


For specific things, none of which are directly relevant here.
No realistic implementation can provide unlimited resources (say, for
infinitely deep recursion or a loop that will take a trillion years to
complete). A realistic implementation can provide a malloc() that
doesn't lie to the client.


The question here is conformance. Can a conforming implementation
overcommit or not?

Lawrence
Nov 14 '05 #19
Chris Croughton <ch***@keristor.net> wrote:
On Tue, 01 Feb 2005 00:20:27 GMT, Keith Thompson
<ks***@mib.org> wrote:
It's pretty clear that lazy allocation is non-conforming. A program
should be able to determine whether enough memory is available when it
attempts to allocate it; that's why malloc() provides a simple and
clear mechanism for reporting failure. There's no way a program can
fail gracefully if the OS randomly kills it when it tries to access
memory it thinks it's already allocated.


By that standard there are no fully conforming real world C compilers,
because all sorts of things can cause programs to abort (being swapped
out and never swapped back in again, running out of process space,
faulty disk drives, a stray cosmic ray in a RAM chip, etc.).


None of those are even remotely under the implementation's control,
though. malloc() is.

Richard
Nov 14 '05 #20
Richard Bos wrote:
Chris Croughton <ch***@keristor.net> wrote:
On Tue, 01 Feb 2005 00:20:27 GMT, Keith Thompson wrote:

It's pretty clear that lazy allocation is non-conforming.
How?
A program
should be able to determine whether enough memory is available
when it attempts to allocate it; that's why malloc() provides
a simple and clear mechanism for reporting failure. There's no
way a program can fail gracefully if the OS randomly kills it
when it tries to access memory it thinks it's already allocated.

True, but how is this different from a program which crashes
because it can't allocate automatic or static storage?
By that standard there are no fully conforming real world C compilers, because all sorts of things can cause programs to abort (being swapped out and never swapped back in again, running out of process space,
faulty disk drives, a stray cosmic ray in a RAM chip, etc.).


None of those are even remotely under the implementation's control,
though. malloc() is.


It's a question of degrees. An implementation may be constrained by
the operating system and may not be in any better position to guarantee
allocation than a C program which it runs.

The standard only guarantees that a conforming hosted implementation
can allocate one object of 32767 bytes (65535 under C99.)

Implementations using lazy allocation systems will likely be conforming
with regards to this minimum requirement. But they may legitimately
fail
under other circumstances.

But all this really just highlights that an 'implementation' consists
of more than just the development tools used to create an executable.
The operating system itself has influence on conformance. In some
(many!)
cases, the end user is responsible for guaranteeing that a given
program is executed in a conforming environment. But this is certainly
beyond the scope of a library implementation of malloc().

So, in a sense, Keith is correct, but it is not malloc() which is at
fault!

--
Peter

Nov 14 '05 #21
"Peter Nilsson" <ai***@acay.com.au> writes:
[...]
It's a question of degrees. An implementation may be constrained by
the operating system and may not be in any better position to guarantee
allocation than a C program which it runs.

The standard only guarantees that a conforming hosted implementation
can allocate one object of 32767 bytes (65535 under C99.)

Implementations using lazy allocation systems will likely be conforming
with regards to this minimum requirement. But they may legitimately
fail
under other circumstances.

But all this really just highlights that an 'implementation' consists
of more than just the development tools used to create an executable.
The operating system itself has influence on conformance. In some
(many!)
cases, the end user is responsible for guaranteeing that a given
program is executed in a conforming environment. But this is certainly
beyond the scope of a library implementation of malloc().

So, in a sense, Keith is correct, but it is not malloc() which is at
fault!


malloc() is a C library function, part of the C implementation, not
(necessarily) part of the operating system. Whatever requirements the
C standard imposes on malloc(), it's up to the implementer to do
whatever is necessary to make sure that it meets those requirements.

If the OS provides, say, an ALLOCATE() function that allocates space
that isn't necessarily properly aligned, malloc() has to arrange to
return a pointer to properly aligned memory. If ALLOCATE(0) aborts
the calling program, malloc(0) can't invoke ALLOCATE(0). And so on.

If lazy malloc() is non-conforming, an implementation of malloc() can
attempt to access the allocated memory before returning the pointer;
since the code that implements malloc() can be a system-specific as it
needs to be, presumably it can handle any traps, deallocate the
memory, and return a null pointer. I'd much rather have malloc() do
that than expect the caller to take care of it.

The standard says:

The malloc function allocates space for an object whose size is
specified by *size* and whose value is indeterminate.

I argue that if I can't access the space, it wasn't really allocated.

Having said that, I have to admit that my argument against lazy
allocation is largely based on the fact that I don't like the idea, at
least for an explicit allocation request.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #22
On Thu, 03 Feb 2005 00:38:23 +0000, Keith Thompson wrote:

....
malloc() is a C library function, part of the C implementation, not
(necessarily) part of the operating system.
Ultimately everything that affects behaviour, including the operating
system, has to be considered part of the implementation.
Whatever requirements the
C standard imposes on malloc(), it's up to the implementer to do
whatever is necessary to make sure that it meets those requirements.
Absolutely. I say though, as I explained in another article, that the
standard does not prohibit memory overcommitment.
If the OS provides, say, an ALLOCATE() function that allocates space
that isn't necessarily properly aligned, malloc() has to arrange to
return a pointer to properly aligned memory.
Agreed.
If ALLOCATE(0) aborts the
calling program, malloc(0) can't invoke ALLOCATE(0). And so on.
As long as the abort process dosn't generate anything that is considered
to be program output or a normal termination condition, it could. Of
course that may be unacceptable on QOI grounds, it depends on the
situation where the abort can happen. The standard has to be very loose in
this area to allow conforming implementations to exist at all.
If lazy malloc() is non-conforming, an implementation of malloc() can
attempt to access the allocated memory before returning the pointer;
since the code that implements malloc() can be a system-specific as it
needs to be, presumably it can handle any traps, deallocate the memory,
and return a null pointer. I'd much rather have malloc() do that than
expect the caller to take care of it.
Even if you do that the OS can decide subsequently that it dosn't have
enough memory to go around and yours is the program it is going to kill to
recover some. The kill action might be initiated by your program accessing
part of a malloc'd array that had been paged out. The point is that it
isn't always possible for a C compiler/library to work around what the OS
does.

Consider this another way. It has come to light that many OSs in common
use can overcommit, and there are good reasons (as considered by some
people) for them to do so. This is an OS level issue. It is NOT the
responsibility of a language level standard such as C's to legislate on
this sort of thing. The purpose of a standard like C's is to provide a
language definition that is useful and portable across as many platforms
as possible. If it specified something that made it unimplementable on a
significant class of platforms and the "usefulness" isn't terminally
impacted (overcommitment is presumably deemed acceptable on the systems
that do it), that would have to be considered a MAJOR defect in the
standard. It isn't a matter of liking or hating a feature like
overcommitment it is a matter of recognising that something exists as a
common feature of real systems and it is somebody else's problem (i.e. not
the C standard committee's) to decide whether it is a good thing or not.
If I use an overcommitting system I don't want C programs subverting that
to the detriment of non-C programs. If I don't like overcommitment I
configure the system I have appropriately or use a different one. The
appropriate solution to this is not at the language level, unless you want
to add features for a program to request that its memory be reserved fully
for it.
The standard says:

The malloc function allocates space for an object whose size is
specified by *size* and whose value is indeterminate.

I argue that if I can't access the space, it wasn't really allocated.
In the abstract machine, yes, which is what the majority of the
standard including this describes (see 5.1.2.3p1). OTOH show me the part
of the standard that says an actual implementation can't terminate the
execution of a strictly conforming program at any point it pleases for any
reason, IOW that the program will successfully execute to completion.
There is a requirement for (at least) one program as specified by 5.2.4.1.
But the "at least one program" wouldn't make sense there if it was already
the case for all strictly conforming programs.
Having said that, I have to admit that my argument against lazy
allocation is largely based on the fact that I don't like the idea, at
least for an explicit allocation request.


What you are guaranteed is that while the execution of the program
continues the object created by malloc() will behave correctly as an
object. It just doesn't guarantee continued execution of the
program subsequently.

Lawrence
Nov 14 '05 #23
Lawrence Kirby <lk****@netactive.co.uk> writes:
On Thu, 03 Feb 2005 00:38:23 +0000, Keith Thompson wrote:

...
malloc() is a C library function, part of the C implementation, not
(necessarily) part of the operating system.
Ultimately everything that affects behaviour, including the operating
system, has to be considered part of the implementation.


Sure, but the visible interface has to conform to the requirements in
the standard, whether the underlying OS does or not.
Whatever requirements the
C standard imposes on malloc(), it's up to the implementer to do
whatever is necessary to make sure that it meets those requirements.


Absolutely. I say though, as I explained in another article, that the
standard does not prohibit memory overcommitment.


And that's the point of contention. Is there a DR on this topic? If
a committee response, or a future TC or version of the standard, says
that overcommitment is ok, I'll grit my teeth and accept it. But then
I wonder if there's any point of having malloc() ever return a null
pointer.
If the OS provides, say, an ALLOCATE() function that allocates space
that isn't necessarily properly aligned, malloc() has to arrange to
return a pointer to properly aligned memory.


Agreed.
If ALLOCATE(0) aborts the
calling program, malloc(0) can't invoke ALLOCATE(0). And so on.


As long as the abort process dosn't generate anything that is considered
to be program output or a normal termination condition, it could. Of
course that may be unacceptable on QOI grounds, it depends on the
situation where the abort can happen. The standard has to be very loose in
this area to allow conforming implementations to exist at all.


I contend that the following program is strictly conforming (assuming
that any program that writes to stdout can be strictly conforming):

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

int main(void)
{
char *ptr = malloc(0);
printf("Hello, world\n");
return 0;
}

If it doesn't print "Hello, world" when I execute it, that's a bug in
the implementation. You seem to be arguing that if any statements
that follow malloc(0) are *never* executed, that's acceptable. (If it
happens to fail because somebody pulled the power plug before it was
able to finish, that's a different story.)
If lazy malloc() is non-conforming, an implementation of malloc() can
attempt to access the allocated memory before returning the pointer;
since the code that implements malloc() can be a system-specific as it
needs to be, presumably it can handle any traps, deallocate the memory,
and return a null pointer. I'd much rather have malloc() do that than
expect the caller to take care of it.


Even if you do that the OS can decide subsequently that it dosn't have
enough memory to go around and yours is the program it is going to kill to
recover some. The kill action might be initiated by your program accessing
part of a malloc'd array that had been paged out. The point is that it
isn't always possible for a C compiler/library to work around what the OS
does.


But in this case, it's not only possible, it's easy. Regardless of
whether lazy allocation is conforming or not, an implementer who wants
to provide a non-lazy malloc() can do so.

The requirement for malloc() is that it has to behave as the standard
requires, not as some OS routine happens to behave.

[...] If I use an overcommitting system I don't want C programs subverting that
to the detriment of non-C programs.

[...]

Is your concern that C programs using a non-overcommitting malloc()
would consume more resources, to the detriment of non-C programs
running simultaneously on the system? (When I first read that, I
thought you meant that non-C programs would be forced to do
non-overcommitting allocations, but I don't think that's what you
meant.)
The standard says:

The malloc function allocates space for an object whose size is
specified by *size* and whose value is indeterminate.

I argue that if I can't access the space, it wasn't really allocated.


In the abstract machine, yes, which is what the majority of the
standard including this describes (see 5.1.2.3p1). OTOH show me the part
of the standard that says an actual implementation can't terminate the
execution of a strictly conforming program at any point it pleases for any
reason, IOW that the program will successfully execute to completion.
There is a requirement for (at least) one program as specified by 5.2.4.1.
But the "at least one program" wouldn't make sense there if it was already
the case for all strictly conforming programs.


Sure, a program can die at any time due to external influences
(somebody kills the process, the OS runs out of resources, somebody
pulls the power plug). And it's very difficult to define when this
constitutes a violation of the C standard and when it's just a case of
"oh well, stuff happens". If my program dies when my infinitely
recursive function call attempts to allocate a terabyte of memory, I
have no grounds for complaint. If it dies whenever I try to compute
2+2 in a strictly conforming program, that's a bug in the
implementation. If it dies when I try to access memory that was
allocated by an apparently successful malloc() call, I'm going to be
grumpy.
Having said that, I have to admit that my argument against lazy
allocation is largely based on the fact that I don't like the idea, at
least for an explicit allocation request.


What you are guaranteed is that while the execution of the program
continues the object created by malloc() will behave correctly as an
object. It just doesn't guarantee continued execution of the
program subsequently.


What I am guaranteed is that if malloc() returns a non-null result,
the memory I requested was allocated. The question is what
"allocated" means.

There's also the issue of which behavior is more useful (which is
separate from the question of what the standard actually requires).
If C programs commonly use malloc() to allocate huge amounts of
memory, and then only use part of it, overallocation makes sense. If,
on the other hand, a program malloc()s a block of memory only if it's
actually going to use all of it, overallocation merely causes certain
errors to be detected later and without any recourse. If I request a
megabyte of memory that the system can't or won't give me, I'd rather
have the malloc() fail cleanly than have my program abort later on.

I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #24
On Thu, 03 Feb 2005 22:30:01 GMT, Keith Thompson
<ks***@mib.org> wrote:
I contend that the following program is strictly conforming (assuming
that any program that writes to stdout can be strictly conforming):

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

int main(void)
{
char *ptr = malloc(0);
printf("Hello, world\n");
return 0;
}

If it doesn't print "Hello, world" when I execute it, that's a bug in
the implementation. You seem to be arguing that if any statements
that follow malloc(0) are *never* executed, that's acceptable. (If it
happens to fail because somebody pulled the power plug before it was
able to finish, that's a different story.)
Define 'acceptable'. It could be failing for a number of reasons and
still be compliant with the standard (as far as I can see it is only
guaranteed that a C program exists and works which has a data block of
up to 64K-1 bytes, but it might be required that this block is
statically allocated).
But in this case, it's not only possible, it's easy. Regardless of
whether lazy allocation is conforming or not, an implementer who wants
to provide a non-lazy malloc() can do so.

The requirement for malloc() is that it has to behave as the standard
requires, not as some OS routine happens to behave.
But there is nothing to say that events outside its control might not
stop it from working.
Sure, a program can die at any time due to external influences
(somebody kills the process, the OS runs out of resources, somebody
pulls the power plug).
Or ir unexpectedly runs out of memory (perhaps someone did "swapoff" in
the middle of execution, or the OS did it automatically).
And it's very difficult to define when this
constitutes a violation of the C standard and when it's just a case of
"oh well, stuff happens". If my program dies when my infinitely
recursive function call attempts to allocate a terabyte of memory, I
have no grounds for complaint. If it dies whenever I try to compute
2+2 in a strictly conforming program, that's a bug in the
implementation.
Only if you include the hardware in the implementation as well.
If it dies when I try to access memory that was
allocated by an apparently successful malloc() call, I'm going to be
grumpy.
Quite possibly, but that's a QoI issue not a standard compliance one.
What I am guaranteed is that if malloc() returns a non-null result,
the memory I requested was allocated. The question is what
"allocated" means.
Ecaxtly.
There's also the issue of which behavior is more useful (which is
separate from the question of what the standard actually requires).
If C programs commonly use malloc() to allocate huge amounts of
memory, and then only use part of it, overallocation makes sense. If,
on the other hand, a program malloc()s a block of memory only if it's
actually going to use all of it, overallocation merely causes certain
errors to be detected later and without any recourse. If I request a
megabyte of memory that the system can't or won't give me, I'd rather
have the malloc() fail cleanly than have my program abort later on.
How about (as is far more likely) it just waits until memory is
available? The standard says nothing about performance, if the OS is
swapping "unused" memory to mag tape and prompts the operator to load
the other mag tape, and they don't get round to it for a couple of days,
you may well get pissed off but it isn't against the standard. Or if
they decide "your program is using too much memory so I'll kill it" (or
if the OS decides the same) it isn't a violation of the standard, it's
just a QoI issue.
I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.


I would argue that it is common and that they are not misbehaving at
all. Any program allocating large arrays (where 'large' means more than
a few KB) as uninitialised variabled will probably not have that data in
"real" memory (RAM or swap) until the program writes to it on most Unix
systems. The same may even be true of large arrays on the stack on some
systems. It's not something whicvh is unique to malloc and dynamic
memory allocation.

If you don't like the QoI, you are free to use another system, or turn
off the 'lazy' memory allocation if you have that privilege, but it is
still standard conformming.

Chris C
Nov 14 '05 #25
Keith Thompson wrote:
.... snip ...
I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.


Yet it is essential for systems to guard against such misbehavior,
for self-protection if nothing else.

I still see several justifications for lazy allocation and eventual
failure. One is to simply block the process until the request can
be satisfied (although how to detect that point may be a problem).
Another is to treat it as if that memory chip just failed.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

Nov 14 '05 #26
Chris Croughton <ch***@keristor.net> writes:
On Thu, 03 Feb 2005 22:30:01 GMT, Keith Thompson
<ks***@mib.org> wrote:
I contend that the following program is strictly conforming (assuming
that any program that writes to stdout can be strictly conforming):

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

int main(void)
{
char *ptr = malloc(0);
printf("Hello, world\n");
return 0;
}

If it doesn't print "Hello, world" when I execute it, that's a bug in
the implementation. You seem to be arguing that if any statements
that follow malloc(0) are *never* executed, that's acceptable. (If it
happens to fail because somebody pulled the power plug before it was
able to finish, that's a different story.)
Define 'acceptable'. It could be failing for a number of reasons and
still be compliant with the standard (as far as I can see it is only
guaranteed that a C program exists and works which has a data block of
up to 64K-1 bytes, but it might be required that this block is
statically allocated).


Sure the standard only really requires that one hypothetical program
be accepted. Other programs, even strictly conforming ones, can fail
for any of a variety of reasons.

But, well, there's quality-of-implementation, and then there's
quality-of-implementation.

As I mentioned before, an implementation in which any attempt to
evaluate 2+2 causes the program to abort might be conforming if you
read the standard strictly enough. But nobody would consider such an
implementation to be acceptable (and if there's some valid reason that
the hardware can't compute 2+2, it's up to the compiler to generate
alternative code that yields 4 as the result).

It's all a matter of degree. I'm arguing that a malloc() that does
overallocation isn't *quite* as bad as an implementation that aborts
on 2+2, but it's more severe than one that refuses to allocate a
terabyte on the stack.
But in this case, it's not only possible, it's easy. Regardless of
whether lazy allocation is conforming or not, an implementer who wants
to provide a non-lazy malloc() can do so.

The requirement for malloc() is that it has to behave as the standard
requires, not as some OS routine happens to behave.


But there is nothing to say that events outside its control might not
stop it from working.


But overallocation isn't outside malloc()'s control. If necessary, it
can access the memory before returning the pointer, and return NULL if
the access fails.

[...]
How about (as is far more likely) it just waits until memory is
available?


That would be fine (as far as conformance is concerned).

[...]
I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.


I would argue that it is common and that they are not misbehaving at
all. Any program allocating large arrays (where 'large' means more than
a few KB) as uninitialised variabled will probably not have that data in
"real" memory (RAM or swap) until the program writes to it on most Unix
systems. The same may even be true of large arrays on the stack on some
systems. It's not something whicvh is unique to malloc and dynamic
memory allocation.


The misbehavior I'm taking about is a program allocating a large array
and *never* writing to it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #27
CBFalconer <cb********@yahoo.com> writes:
Keith Thompson wrote:

... snip ...

I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.


Yet it is essential for systems to guard against such misbehavior,
for self-protection if nothing else.


Sure, and the system can guard against it by making the malloc() call
fail.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #28
Keith Thompson wrote:
CBFalconer <cb********@yahoo.com> writes:
Keith Thompson wrote:

... snip ...

I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.


Yet it is essential for systems to guard against such misbehavior,
for self-protection if nothing else.


Sure, and the system can guard against it by making the malloc() call
fail.


Please tell me how the system can differentiate between a malloc
whose space will be used, and a malloc whose space will not be
used?

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 14 '05 #29
CBFalconer <cb********@yahoo.com> writes:
Keith Thompson wrote:
CBFalconer <cb********@yahoo.com> writes:
Keith Thompson wrote:

... snip ...

I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.

Yet it is essential for systems to guard against such misbehavior,
for self-protection if nothing else.


Sure, and the system can guard against it by making the malloc() call
fail.


Please tell me how the system can differentiate between a malloc
whose space will be used, and a malloc whose space will not be
used?


Ok, it can't -- but in my opinion it doesn't need to.

A program requests memory; the system either allocates it or reports
that it can't.

I see your point, though. Lazy allocation means that a program that
requests a huge amount of memory and doesn't use it will have less
impact on the rest of the system. I'm just not convinced that it's
worth the drawbacks.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #30
CBFalconer <cb********@yahoo.com> writes:
Please tell me how the system can differentiate between a malloc
whose space will be used, and a malloc whose space will not be
used?


Incidentally, it is quite common to allocate memory that will
never be used. For example, a table I'm preparing for a paper
here says that Mozilla, in one particular experiment we ran,
dynamically allocated 135 MB RAM but only ever wrote to 71% of
those bytes; Apache allocated 57 MB RAM but only ever wrote to 9%
of it.
--
"Welcome to the wonderful world of undefined behavior, where the demons
are nasal and the DeathStation users are nervous." --Daniel Fox
Nov 14 '05 #31
In article <87************@benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:
Incidentally, it is quite common to allocate memory that will
never be used. For example, a table I'm preparing for a paper
here says that Mozilla, in one particular experiment we ran,
dynamically allocated 135 MB RAM but only ever wrote to 71% of
those bytes; Apache allocated 57 MB RAM but only ever wrote to 9%
of it.


When you say it allocated 135MB do you mean that it malloc()ed 135MB,
or that the system allocated 135MB in response to malloc() calls? On
systems that use power-of-two allocation, the operating system may
allocate up to twice as much as is requested by malloc. And even
systems that return blocks of the "right" size may have an
unnecessarily large pool from which they provide them.

In these cases overcommit avoids rejecting requests for memory that
could actually be satisfied.

-- Richard
Nov 14 '05 #32
On Fri, 04 Feb 2005 02:41:41 GMT, Keith Thompson
<ks***@mib.org> wrote:
Chris Croughton <ch***@keristor.net> writes:

Define 'acceptable'. It could be failing for a number of reasons and
still be compliant with the standard (as far as I can see it is only
guaranteed that a C program exists and works which has a data block of
up to 64K-1 bytes, but it might be required that this block is
statically allocated).
Sure the standard only really requires that one hypothetical program
be accepted. Other programs, even strictly conforming ones, can fail
for any of a variety of reasons.

But, well, there's quality-of-implementation, and then there's
quality-of-implementation.

As I mentioned before, an implementation in which any attempt to
evaluate 2+2 causes the program to abort might be conforming if you
read the standard strictly enough. But nobody would consider such an
implementation to be acceptable (and if there's some valid reason that
the hardware can't compute 2+2, it's up to the compiler to generate
alternative code that yields 4 as the result).


Or not, it's not up to the compiler to check every detail of every
system on which it might be run. The compiler can be fine, but if the
program I generate and run on a possibly different platform fails that
is not the fault of the compiler or the library.
It's all a matter of degree. I'm arguing that a malloc() that does
overallocation isn't *quite* as bad as an implementation that aborts
on 2+2, but it's more severe than one that refuses to allocate a
terabyte on the stack.
It's nowhere near as 'bad' in the Real World(tm). If you are running
your program on a system with insufficient resources, that's your
problem not that of the implementation.
But overallocation isn't outside malloc()'s control. If necessary, it
can access the memory before returning the pointer, and return NULL if
the access fails.


Not necessarily, it might just hang, or even bomb out (just as it would
later when it tried to access the memory). There is also no value with
which it could overwrite the memory which is necessarily going to make
sure that it is really owned.
I would think that it's rare for C programs to malloc() memory that
they're not actually going to use, and I would argue that programs
that do so are misbehaving.


I would argue that it is common and that they are not misbehaving at
all. Any program allocating large arrays (where 'large' means more than
a few KB) as uninitialised variabled will probably not have that data in
"real" memory (RAM or swap) until the program writes to it on most Unix
systems. The same may even be true of large arrays on the stack on some
systems. It's not something whicvh is unique to malloc and dynamic
memory allocation.


The misbehavior I'm taking about is a program allocating a large array
and *never* writing to it.


If I allocate a buffer of (say) 64KB, and it happens that all of the
lines I read in are 80 characters or less, most of that is unused. The
same in many other Real Workd(tm) applications. Using "lazy allocation"
means that it doesn't matter, a program can allocate as much as it might
need and it only gets used when it needs it, instead of the inefficiency
of allocating lots of small chunks. A number of replacement memory
handling systems, for instance, allocate memory in increasing powers of
2 as they find that they need more, in a lot of cases the last block
allocated will be mostly unused.

Perhaps allocating a large chunk of memory and never writing to it at
all is wasteful, but it's hardly 'misbehaving'.

Chris C
Nov 14 '05 #33
ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:
In article <87************@benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.edu> wrote:
Incidentally, it is quite common to allocate memory that will
never be used. For example, a table I'm preparing for a paper
here says that Mozilla, in one particular experiment we ran,
dynamically allocated 135 MB RAM but only ever wrote to 71% of
those bytes; Apache allocated 57 MB RAM but only ever wrote to 9%
of it.


When you say it allocated 135MB do you mean that it malloc()ed 135MB,
or that the system allocated 135MB in response to malloc() calls?


The former. The bytes it requested from malloc() over its
execution summed to 135 MB.
--
"I should killfile you where you stand, worthless human." --Kaz
Nov 14 '05 #34

In article <ln************@nuthaus.mib.org>, Keith Thompson <ks***@mib.org> writes:

And that's the point of contention. Is there a DR on this topic? If
a committee response, or a future TC or version of the standard, says
that overcommitment is ok, I'll grit my teeth and accept it. But then
I wonder if there's any point of having malloc() ever return a null
pointer.
Of course there is. An overcommitting implementation can still reject
an allocation request, and indeed all of the ones I've used do so.

On AIX, for example, the data ulimit is typically set, and will cause
malloc to fail if the heap would need to be extended past that limit.
(This is a Good Thing.)

Commitment and permitting allocation are two separate issues.
If it dies when I try to access memory that was
allocated by an apparently successful malloc() call, I'm going to be
grumpy.
This can easily happen even on a strict-allocating system, for any of
a wide range of reasons (read error from a swap partition, for
example). Be grumpy. That doesn't make the implementation
non-conforming.
I would think that it's rare for C programs to malloc() memory that
they're not actually going to use,
Not in my experience. For performance reasons, many programs I've
seen allocate buffers in relatively large chunks and don't bother
shrinking and enlarging them to fit the current size of their
contents, for example. And, of course, there are various sparse data
structures implemented with large lazily-allocated areas.

I've seen a lot of C code, but I doubt I've seen a statistically
meaningful sample of *all* C code, and I wouldn't know who has. That
makes guessing what's "rare" in C programs tricky.
and I would argue that programs that do so are misbehaving.


And the people who write such programs would argue that they aren't.
I think this one's a non-starter.

--
Michael Wojcik mi************@microfocus.com

When [Columbus] landed on America it was more like an evasion than a
discovery. -- Matt Walsh
Nov 14 '05 #35

In article <ln************@nuthaus.mib.org>, Keith Thompson <ks***@mib.org> writes:

But overallocation isn't outside malloc()'s control. If necessary, it
can access the memory before returning the pointer, and return NULL if
the access fails.


That assumption is not true for all overcommitting OSes.

On AIX, for example, the failure to back overcommitted memory does
not result in a "failed access" that malloc could detect as it's
touching pages. (AIX, incidentally, provides a malloc variant that
does just this, for people who mysteriously cannot write their own.)

When the AIX virtual storage manager - which handles all main
memory and disk access, including filesystems and swap - determines
that additional pages are needed, no more are available, and no more
can be made available automatically, it begins a series of actions
designed to let both system administrators and processes correct the
condition. If no correction is forthcoming, the OS will escalate to
forcibly freeing storage by terminating user processes which are
consuming the most memory.

There's no guarantee that this situation will occur while *your*
process is accessing memory - whether that happens in your code or
in malloc. You might preallocate all of your memory, only to have
some other process push the system into an overcommittment failure.
Further, even if your process is the instigator (insofar as that's
a well-defined role in this scheme), there's no guarantee that it
will be the first process notified of the situation.

Further, malloc is not the only consumer of storage, and the
overcommittment failure could occur outside of malloc. Changing
the behavior of malloc has little impact in general on the system's
allocation scheme or behavior in allocation failure.

This may not be to your liking. Fine. But it *is not a C library
implementation issue* in this case. It's an OS one, and there is
nothing malloc can do to change how the OS behaves.

--
Michael Wojcik mi************@microfocus.com

Pocket #9: A complete "artificial glen" with rocks, and artificial moon,
and forester's station. Excellent for achieving the effect of the
sublime without going out-of-doors. -- Joe Green
Nov 14 '05 #36
Chris Croughton <ch***@keristor.net> writes:
On Fri, 04 Feb 2005 02:41:41 GMT, Keith Thompson
<ks***@mib.org> wrote:

[...]
As I mentioned before, an implementation in which any attempt to
evaluate 2+2 causes the program to abort might be conforming if you
read the standard strictly enough. But nobody would consider such an
implementation to be acceptable (and if there's some valid reason that
the hardware can't compute 2+2, it's up to the compiler to generate
alternative code that yields 4 as the result).


Or not, it's not up to the compiler to check every detail of every
system on which it might be run. The compiler can be fine, but if the
program I generate and run on a possibly different platform fails that
is not the fault of the compiler or the library.


I'm not talking about a different platform. I'm assuming an
(obviously hypothetical and very stupid) implementation in which the
CPU aborts the current program on any attempt to compute 2+2. It's a
documented feature of the ADD instruction; *no* instance of that CPU
is capable of computing 2+2. A usefully conforming C implementation
on such a system would have to work around this limitation.

[...]
But overallocation isn't outside malloc()'s control. If necessary, it
can access the memory before returning the pointer, and return NULL if
the access fails.


Not necessarily, it might just hang, or even bomb out (just as it would
later when it tried to access the memory). There is also no value with
which it could overwrite the memory which is necessarily going to make
sure that it is really owned.


There's no portable way to do it, but the implementation of malloc()
doesn't have to be portable; it can do whatever system-specific stuff
it needs to to do its job.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #37
mw*****@newsguy.com (Michael Wojcik) writes:
In article <ln************@nuthaus.mib.org>, Keith Thompson
<ks***@mib.org> writes:

But overallocation isn't outside malloc()'s control. If necessary, it
can access the memory before returning the pointer, and return NULL if
the access fails.


That assumption is not true for all overcommitting OSes.

On AIX, for example, the failure to back overcommitted memory does
not result in a "failed access" that malloc could detect as it's
touching pages. (AIX, incidentally, provides a malloc variant that
does just this, for people who mysteriously cannot write their own.)

[...]

Just to be clear on what "does just this" refers to, does the malloc
variant attempt to access the allocated memory (and possibly terminate
the process, or another one, if it fails)?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #38

In article <ln************@nuthaus.mib.org>, Keith Thompson <ks***@mib.org> writes:
mw*****@newsguy.com (Michael Wojcik) writes:
In article <ln************@nuthaus.mib.org>, Keith Thompson
<ks***@mib.org> writes:

But overallocation isn't outside malloc()'s control. If necessary, it
can access the memory before returning the pointer, and return NULL if
the access fails.


That assumption is not true for all overcommitting OSes.

On AIX, for example, the failure to back overcommitted memory does
not result in a "failed access" that malloc could detect as it's
touching pages. (AIX, incidentally, provides a malloc variant that
does just this, for people who mysteriously cannot write their own.)


Just to be clear on what "does just this" refers to, does the malloc
variant attempt to access the allocated memory (and possibly terminate
the process, or another one, if it fails)?


The malloc variant (the name escapes me, and I don't recall whether
it was provided as an additional library function or simply as source)
touches each page of the newly-allocated area after successful
allocation. It can't "fail" in that process because there is no
failure mode for touching a page. There's a failure mode for the
system running short on virtual storage, but it's not tied directly
to the malloc-variant's operation.

To be frank, I think strict commitment is the wrong approach. If
you're worried about overcommitment, the proper fix is to ensure it
doesn't happen by setting the appropriate OS restrictions (number of
processes and process data limits) and not letting things run wild on
the system.

Production code should run on production systems. I don't have a lot
of sympathy for people worried about overcommitment while they're
running web browsers and the like.

Computer systems are loaded with compromises. It'd be swell to run
everything on A1-secure fault-tolerant systems with transparent
geographically-separated backups, but that's not an option. Over-
commitment is a compromise that trades an additional - rare - failure
mode for performance and simplicity. For systems build on the sands
of Unix, amateur software, commodity hardware, and the like, that
seems pretty reasonable to me.

But I recognize that this is a controversial issue, and people whose
opinions I respect - such as Doug Gwyn, Dan Bernstein, and yourself -
believe that overcommitment is undesirable. From that perspective,
at least one aspect of the Linux implementation is superior to the
AIX one: Linux lets you disable overcommitment system-wide.

--
Michael Wojcik mi************@microfocus.com

When most of what you do is a bit of a fraud, the word "profession"
starts to look like the Berlin Wall. -- Tawada Yoko (t. M. Mitsutani)
Nov 14 '05 #39
On Fri, 04 Feb 2005 18:26:03 GMT, Keith Thompson
<ks***@mib.org> wrote:
Chris Croughton <ch***@keristor.net> writes:
On Fri, 04 Feb 2005 02:41:41 GMT, Keith Thompson
<ks***@mib.org> wrote: [...]
As I mentioned before, an implementation in which any attempt to
evaluate 2+2 causes the program to abort might be conforming if you
read the standard strictly enough. But nobody would consider such an
implementation to be acceptable (and if there's some valid reason that
the hardware can't compute 2+2, it's up to the compiler to generate
alternative code that yields 4 as the result).


Or not, it's not up to the compiler to check every detail of every
system on which it might be run. The compiler can be fine, but if the
program I generate and run on a possibly different platform fails that
is not the fault of the compiler or the library.


I'm not talking about a different platform. I'm assuming an
(obviously hypothetical and very stupid) implementation in which the
CPU aborts the current program on any attempt to compute 2+2. It's a
documented feature of the ADD instruction; *no* instance of that CPU
is capable of computing 2+2. A usefully conforming C implementation
on such a system would have to work around this limitation.


Or not exist, because the system on which it runs is broken. It seems
that in your opinion systems using lazy allocation are broken, but that
is the fault of the system not that of the C implementation which might
not be able to get around the system behaviour.
[...]
But overallocation isn't outside malloc()'s control. If necessary, it
can access the memory before returning the pointer, and return NULL if
the access fails.


Not necessarily, it might just hang, or even bomb out (just as it would
later when it tried to access the memory). There is also no value with
which it could overwrite the memory which is necessarily going to make
sure that it is really owned.


There's no portable way to do it, but the implementation of malloc()
doesn't have to be portable; it can do whatever system-specific stuff
it needs to to do its job.


I didn't say portable. There might be no way to do it at all, at all.
The OS is at liberty to swap the memory out to tape and then allow the
operator to change tapes, causaing any program which tries to access the
memory to crash. Or any other behaviour it wants. There may be a
system flag which says whether 'lazy' allocation is permitted which the
C library can't access, or the system may just 'hang' if it runs out of
memory, or many other behaviours.

Chris C
Nov 14 '05 #40
Chris Croughton <ch***@keristor.net> writes:
On Fri, 04 Feb 2005 18:26:03 GMT, Keith Thompson <ks***@mib.org> wrote:

[...]
I'm not talking about a different platform. I'm assuming an
(obviously hypothetical and very stupid) implementation in which the
CPU aborts the current program on any attempt to compute 2+2. It's a
documented feature of the ADD instruction; *no* instance of that CPU
is capable of computing 2+2. A usefully conforming C implementation
on such a system would have to work around this limitation.


Or not exist, because the system on which it runs is broken. It seems
that in your opinion systems using lazy allocation are broken, but that
is the fault of the system not that of the C implementation which might
not be able to get around the system behaviour.


If the OS doesn't permit the possibility of a conforming C
implementation, that may not be the C implementation's fault -- but
the C implementation is still non-conforming.

Which still leaves the question of whether lazy allocation is
conforming -- a question I'm no longer trying to answer.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Nov 14 '05 #41

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

5 posts views Thread by Koster | last post: by
29 posts views Thread by David Hill | last post: by
37 posts views Thread by Harsimran | last post: by
2 posts views Thread by chingfulan | last post: by
14 posts views Thread by Roka100 | last post: by
13 posts views Thread by ababeel | last post: by
6 posts views Thread by mthread | last post: by
1 post views Thread by Waqarahmed | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.