Implementing Malloc()

[CJ]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

Do any implementations of malloc() use a strategy like this?


=====================================
McCoy's a seducer galore,
And of virgins he has quite a score.
He tells them, "My dear,
You're the Final Frontier,
Where man never has gone before."

 

[christian.bau]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

Do any implementations of malloc() use a strategy like this?

I hope not.

 

[Default User]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc()
failure for such a small allocation, so the program will crash with a
SIGSEGV as soon as the NULL pointer is dereferenced.

This can be used safely by an intelligent programmer.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer does write to
the end of the mallocated block. In this case, either there's a
SIGSEGV again (no worse off than before), or if the 512Kb is in the
middle of the heap malloc() is drawing from then the writes might
well succeed, and the program can continue albeit with some possible
minor data corruption.

This cannot.



Brian

 

[Shadowman]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

At least in the first case the programmer *can* detect if the call to
malloc() failed. This is not possible with your solution. With your
solution, every call to malloc() presents the possibility of a SIGSEGV
or data corruption without warning.


SM
rot13 for email

 

[Marco Manfredini]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

Do any implementations of malloc() use a strategy like this?

The Chernobyl mainframe?

 

[Charlton Wilbur]

CJ> Suppose the user requests 1Mb of memory. Unfortunately, we
CJ> only have 512Kb available. In this situation, most mallocs()
CJ> would return null. The huge majority of programmers won't
CJ> bother to check malloc() failure for such a small allocation,
CJ> so the program will crash with a SIGSEGV as soon as the NULL
CJ> pointer is dereferenced.

CJ> So why not just return a pointer to the 512Kb that's
CJ> available?

Because the programmer knows what he's asking for, and why he's asking
for it, and it's not the place of the C library to determine whether
he really means it or not. If he only *wanted* 512K, he would,
presumably, only *ask for* 512K; if he *asks for* 1M, then the system
needs to either give him that 1M or tell him it can't. This is, after
all, the behavior the standard calls for.

And if the programmer is careless enough to not check the return value
of malloc(), he deserves the crash. Under your scheme, a responsible
programmer who *does* check the return value of malloc() and finds
that the allocation succeeded (since that is what a non-NULL return
value means, according to the standard) will be sometimes bitten by
strange unreproducible bugs. Trying to make C less fragile in the
hands of incompetents is a fine thing, but not at the cost of making
it work inconsistently in the hands of competent programmers.

CJ> Do any implementations of malloc() use a strategy like this?

I understand that the Linux virtual memory subsystem can allow
overcommitting (and does so by default on some distributions), but
that happens at a different level than malloc().

Charlton

 

[Al Balmer]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

Nonsense. The vast majority of programmers I know always check for
malloc failure.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

Good grief. Why not just do it right?

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

Do any implementations of malloc() use a strategy like this?

This is all a joke, isn't it?

 

[James Kuyper]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, ...

Only incompetent programmers who no sane person would hire would fail to
check for malloc() failure. If that's a "huge majority", then the C
programming world is in deep trouble.

... so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

Because the C standard requires that if an implementation cannot
allocate the entire amount, then it must return a NULL pointer, a
feature which competent programmers rely upon.

 

[jacob navia]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

Do any implementations of malloc() use a strategy like this?


=====================================
McCoy's a seducer galore,
And of virgins he has quite a score.
He tells them, "My dear,
You're the Final Frontier,
Where man never has gone before."

Your function is a new function, not malloc, you should
call it differently, for instance

SYNOPSIS:
void *mallocTry(size_t size, size_t *new_size);

DESCRIPTION:
This function will return a valid pointer to a block of
size bytes if sucessfull, NULL if there is no block of
the requested size.

If this function fails, it will return in new_size
(if new_size is not a NULL pointer) the size of the
largest request that the malloc system is able to
find at the time of the call to mallocTry.

The user call sequence is like this:

size_t ns = 1024*1024;
char *p = mallocTry(ns,&ns);
if (p == NULL && ns > 256*1024) {
p = mallocTry(ns,NULL);
if (p == NULL) {
fprintf(stderr,"No more memory\n");
exit(-1);
}
}
// Here ns is the size of the block and p is valid.

 

[Francine.Neary]

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

Do any implementations of malloc() use a strategy like this?

I seem to remember reading that it's standard practise for C
implementations on Linux to overcommit memory in this way. Always
seemed a bit crazy to me :~

 

[jacob navia]

The user call sequence is like this:

size_t ns = 1024*1024;
char *p = mallocTry(ns,&ns);
if (p == NULL && ns > 256*1024) {
p = mallocTry(ns,NULL);
if (p == NULL) {
fprintf(stderr,"No more memory\n");
exit(-1);
}
}
// Here ns is the size of the block and p is valid.

BUG:

If ns <= 256K the code above will fail. The correct sequence is:
The user call sequence is like this:

size_t ns = 1024*1024;
char *p = mallocTry(ns,&ns);
if (p == NULL ) {
if (ns > 256*1024)
p = mallocTry(ns,NULL);
if (p == NULL) {
fprintf(stderr,"No more memory\n");
exit(-1);
}
}
// Here ns is the size of the block and p is valid.

Excuse me for this oversight.

 

[Eric Sosman]

CJ wrote On 11/26/07 16:40,:

We were discussing implementing malloc(), in particular the following
situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only have
512Kb available. In this situation, most mallocs() would return null.
The huge majority of programmers won't bother to check malloc() failure
for such a small allocation, so the program will crash with a SIGSEGV as
soon as the NULL pointer is dereferenced.

So why not just return a pointer to the 512Kb that's available? It's
quite possible that the user will never actually write into the upper
half of the memory he's allocated, in which case the program will have
continued successfully where before it would have crashed.

The worst thing that can happen is that the programmer _does_ write to
the end of the mallocated block. In this case, either there's a SIGSEGV
again (no worse off than before), or if the 512Kb is in the middle of
the heap malloc() is drawing from then the writes might well succeed,
and the program can continue albeit with some possible minor data
corruption.

Do any implementations of malloc() use a strategy like this?

This idea can be extended to produce the following
extremely efficient implementation of malloc() and its
companions:

#include <stdlib.h>

static unsigned long memory;

void *malloc(size_t bytes) {
return &memory;
}

void *calloc(size_t esize, size_t ecount) {
memory = 0;
return &memory;
}

void *realloc(void *old, size_t bytes) {
return old;
}

void free(void *ptr) {
#ifdef DEBUGGING
memory = 0xDEADBEEF;
#endif
}

Not only does this implementation avoid the processing
overhead of maintaining potentially large data structures
describing the state of memory pools, but it also reduces
the "memory footprint" of every program that uses it, thus
lowering page fault rates, swap I/O rates, and out-of-memory
problems.

 

[CBFalconer]

We were discussing implementing malloc(), in particular the
following situation.

Suppose the user requests 1Mb of memory. Unfortunately, we only
have 512Kb available. In this situation, most mallocs() would
return null. The huge majority of programmers won't bother to
check malloc() failure for such a small allocation, so the
program will crash with a SIGSEGV as soon as the NULL pointer
is dereferenced.

If he doesn't check the return from malloc, he should be disallowed
to use the C compiler. He is obviously an idiot.

 

[Malcolm McLean]

Only incompetent programmers who no sane person would hire would fail to
check for malloc() failure. If that's a "huge majority", then the C
programming world is in deep trouble.

The problem is that, often, there is nothing you can do without imposing
unacceptable runtime overheads. This is especially true in windowing systems
where function that need to allocate trivial amounts of memory are called by
indirection, often several layers deep. It is no longer possible to return
an error condition to the caller.
If all you cna do is exit(EXIT_FAILURE); you might as well segfault, and
have more readable code.

That's why I introduced xmalloc(), the malloc() that never fails. It
achieves this by nagging for memory, until killed by the user as a last
resort when the cupboard is bare.

 

[Marco Manfredini]

If he doesn't check the return from malloc, he should be disallowed
to use the C compiler. He is obviously an idiot.

Two posters recalled the overcommit feature of Linux (and probably the
BSD's and AIX), once engaged malloc() *never* returns NULL. Instead, if
the system runs out of VM, the kernel goes on a killing spree and
terminates all processes that razzed him. The malloc manpage even
contains instructions how to fix this. The idiots are everywhere.

 

[Flash Gordon]

Malcolm McLean wrote, On 26/11/07 23:27:

The problem is that, often, there is nothing you can do without imposing
unacceptable runtime overheads.

There is always something you can do without large runtime overheads.
You can always terminate the program. Of course, that is not always
acceptable.

This is especially true in windowing
systems where function that need to allocate trivial amounts of memory
are called by indirection, often several layers deep. It is no longer
possible to return an error condition to the caller.

If you design it without mechanisms for returning error conditions that
is true. However, if you design it properly it is not true.

If all you cna do is exit(EXIT_FAILURE); you might as well segfault, and
have more readable code.

Complete and utter rubbish. One is predictable and occurs at the actual
point of failure the other is not guaranteed.

That's why I introduced xmalloc(), the malloc() that never fails. It
achieves this by nagging for memory, until killed by the user as a last
resort when the cupboard is bare.

Which it must be doing by checking the value returned by malloc. How can
you be claiming it produces an unacceptable overhead and then actually
doing it?

 

[Dik T. Winter]

> Two posters recalled the overcommit feature of Linux (and probably the
> BSD's and AIX),

As far as I remember, BSD Unix did *not* overcommit.

> once engaged malloc() *never* returns NULL. Instead, if
> the system runs out of VM, the kernel goes on a killing spree and
> terminates all processes that razzed him. The malloc manpage even
> contains instructions how to fix this. The idiots are everywhere.

I experience it the first time when we got our first SGI's (system V based).
It was my impression that the first program killed was fairly random. I have
seen X windows sessions killed due to this. Within a short time the default
to overcommit was changed on *all* those machines.

 

[Dik T. Winter]

> Malcolm McLean wrote, On 26/11/07 23:27: ....
>
> Which it must be doing by checking the value returned by malloc. How can
> you be claiming it produces an unacceptable overhead and then actually
> doing it?

Not only that. It goes into a tight loop which is not user-friendly at
all, probably tying up many resources.

 

[Richard Tobin]

This is especially true in windowing
systems where function that need to allocate trivial amounts of memory
are called by indirection, often several layers deep. It is no longer
possible to return an error condition to the caller.

If you design it without mechanisms for returning error conditions that
is true. However, if you design it properly it is not true.

If all you cna do is exit(EXIT_FAILURE); you might as well segfault, and
have more readable code.

Complete and utter rubbish. One is predictable and occurs at the actual
point of failure the other is not guaranteed.[/QUOTE]

Not guaranteed by the C standard, but probably guaranteed on whatever
you're writing a window system for. The C standard isn't the only
relevant source of guarantees for most programmers.

Not that I advocate doing it. If it really isn't useful to handle the
error gracefully (which is often the case), then something like
xmalloc() is the oobvious solution.

-- Richard

 

[Richard Tobin]

Two posters recalled the overcommit feature of Linux (and probably the
BSD's and AIX), once engaged malloc() *never* returns NULL.

I don't think that's quite true. It may never return NULL because of
memory shortage, but it probably does for other reasons such as
impossible sizes and requests exceeding a settable limit.

-- Richard