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]

Re: Implementing Malloc()

On Nov 26, 9:40 pm, CJ <nos...@nospam. invalidwrote:

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]

Re: Implementing Malloc()

CJ wrote:

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]

Re: Implementing Malloc()

CJ wrote:

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]

Re: Implementing Malloc()

CJ wrote:

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?

[Al Balmer]

Re: Implementing Malloc()

On Mon, 26 Nov 2007 22:40:52 +0100 (CET), CJ <nospam@nospam. invalid>
wrote:

>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?

--
Al Balmer
Sun City, AZ

[James Kuyper]

Re: Implementing Malloc()

CJ wrote:

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.

[Charlton Wilbur]

Re: Implementing Malloc()

>>>>"CJ" == CJ <nospam@nospam. invalidwrites:

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

CJSo why not just return a pointer to the 512Kb that's
CJavailable?

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.

CJDo 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


--
Charlton Wilbur
cwilbur@chromat ico.net

[jacob navia]

Re: Implementing Malloc()

CJ wrote:

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,&n s);
if (p == NULL && ns 256*1024) {
p = mallocTry(ns,NU LL);
if (p == NULL) {
fprintf(stderr, "No more memory\n");
exit(-1);
}
}
// Here ns is the size of the block and p is valid.



--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique

http://www.cs.virginia.edu/~lcc-win32

[Francine.Neary@googlemail.com]

Re: Implementing Malloc()

On Nov 26, 9:40 pm, CJ <nos...@nospam. invalidwrote:

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 :~

>
=============== =============== =======
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."

[jacob navia]

Re: Implementing Malloc()

jacob navia wrote:

The user call sequence is like this:
>
size_t ns = 1024*1024;
char *p = mallocTry(ns,&n s);
if (p == NULL && ns 256*1024) {
p = mallocTry(ns,NU LL);
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,&n s);
if (p == NULL ) {
if (ns 256*1024)
p = mallocTry(ns,NU LL);
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.


--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique

http://www.cs.virginia.edu/~lcc-win32

[Eric Sosman]

Re: Implementing Malloc()

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.

--
Eric.Sosman@sun .com

[CBFalconer]

Re: Implementing Malloc()

CJ wrote:

>
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.

--
Chuck F (cbfalconer at maineline dot net)
<http://cbfalconer.home .att.net>
Try the download section.


--
Posted via a free Usenet account from http://www.teranews.com

[Malcolm McLean]

Re: Implementing Malloc()


"James Kuyper" <jameskuyper@ve rizon.netwrote in message

>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.
>

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_FAILU RE); 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.

--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

[Marco Manfredini]

Re: Implementing Malloc()

CBFalconer wrote:

CJ wrote:

>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.
>

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.