Implementing Malloc()

[Flash Gordon]

Re: Implementing Malloc()

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

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

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_FAILU RE); 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?
--
Flash Gordon

[Dik T. Winter]

Re: Implementing Malloc()

In article <fiflgn$5ds$1@a ioe.orgMarco Manfredini <ok_nospam_ok@p hoyd.netwrites:
....

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),

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, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Richard Tobin]

Re: Implementing Malloc()

In article <nd2s15x47s.ln2 @news.flash-gordon.me.uk>,
Flash Gordon <spam@flash-gordon.me.ukwro te:

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

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
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Richard Tobin]

Re: Implementing Malloc()

In article <fiflgn$5ds$1@a ioe.org>,
Marco Manfredini <ok_nospam_ok@p hoyd.netwrote:

>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
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Dik T. Winter]

Re: Implementing Malloc()

In article <nd2s15x47s.ln2 @news.flash-gordon.me.ukFla sh Gordon <spam@flash-gordon.me.ukwri tes:

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

....

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?

Not only that. It goes into a tight loop which is not user-friendly at
all, probably tying up many resources.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Gordon Burditt]

Re: Implementing Malloc()

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

"possible minor data corruption", especially the kind you don't
notice, is about the worst case possible. You finally realize
what's happening, and then you discover that last year's backups
are corrupted and you've lost lots of work.

Remind me never to fly on any airplanes with your software running
them.

Remember, anything can run in zero time and zero memory if you don't
require the result to be correct.

[James Fang]

Re: Implementing Malloc()

This is very bad in engineering practice, especially when the error is
undeterminstic and it is impossible to find the root cause of such
error.

Especially in some embedded systems without memory protection, this
kind of malloc implementation will make your program dancing as a
drunk.

BRs
James Fang

On 11ÔÂ27ÈÕ, ÉÏÎç5ʱ40·Ö, CJ <nos...@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.
>
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."

[Flash Gordon]

Re: Implementing Malloc()

Richard Tobin wrote, On 27/11/07 00:56:

In article <nd2s15x47s.ln2 @news.flash-gordon.me.uk>,
Flash Gordon <spam@flash-gordon.me.ukwro te:
>

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

>
Not guaranteed by the C standard, but probably guaranteed on whatever
you're writing a window system for.

OK, let's try it with Windows 3.1, IIRC that did not have much in terms
of memory protection (and is probably still in use in some places since
I have very good reason to believe DOS is still used in some places on
PCs), or under Gem.

The C standard isn't the only
relevant source of guarantees for most programmers.

True. However it is better to rely on the C standard where it can
sensibly provide for what is wanted, and then work your way up through
the steadily less portable standards and system specifics only when
necessary.

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.

I accept that a "tidy up and exit" malloc wrapper is sometimes
appropriate, also a "prompt the user and then retry" wrapper is
sometimes appropriate. I know that my customers would be *much* happier
with either of those than a segmentation violation, since a segmentation
violation implies (correctly IMHO) a bug in the program.

So I think you (Richard) and I are in agreement :-)
--
Flash Gordon

[Flash Gordon]

Re: Implementing Malloc()

Dik T. Winter wrote, On 27/11/07 00:51:

In article <nd2s15x47s.ln2 @news.flash-gordon.me.ukFla sh Gordon <spam@flash-gordon.me.ukwri tes:

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

...

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?

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

I've not seen Malcolm's implementation. If it prompts the users to free
up space and then waits (preferably with options to retry or abort) then
it is useful. If, as you are applying, it is simply a loop repeatedly
calling *alloc, then I would also consider it completely unacceptable.
--
Flash Gordon

[santosh]

Re: Implementing Malloc()

In article <1196116487.706 075@news1nwk>, Eric Sosman
<Eric.Sosman@su n.comwrote on Tuesday 27 Nov 2007 4:04 am:

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.

ROTFL

[CJ]

Re: Implementing Malloc()

On 26 Nov 2007 at 22:34, Eric Sosman wrote:

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.

All very amusing, but I think you and some of the other posters have
misunderstood the context of the discussion.

Of course an implementation of malloc should return a pointer to as much
memory as requested whenever that's possible! The discussion was about
the rare failure case. Typically, programs assume malloc returns a
non-null pointer, so if it returns null on failure then the program will
crash and burn.

The idea is that instead of a guaranteed crash, isn't it better to make
a last-ditch effort to save the program's bacon by returning a pointer
to what memory there _is_ available? If the program's going to crash
anyway, it's got to be worth a shot.


=============== =============== =========
There once was an old man from Esser,
Who's knowledge grew lesser and lesser.
It at last grew so small,
He knew nothing at all,
And now he's a College Professor.

[jacob navia]

Re: Implementing Malloc()

CJ wrote:

On 26 Nov 2007 at 22:34, Eric Sosman wrote:

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

>
All very amusing, but I think you and some of the other posters have
misunderstood the context of the discussion.
>
Of course an implementation of malloc should return a pointer to as much
memory as requested whenever that's possible! The discussion was about
the rare failure case. Typically, programs assume malloc returns a
non-null pointer, so if it returns null on failure then the program will
crash and burn.
>
The idea is that instead of a guaranteed crash, isn't it better to make
a last-ditch effort to save the program's bacon by returning a pointer
to what memory there _is_ available? If the program's going to crash
anyway, it's got to be worth a shot.
>
>
=============== =============== =========
There once was an old man from Esser,
Who's knowledge grew lesser and lesser.
It at last grew so small,
He knew nothing at all,
And now he's a College Professor.

Well, I proposed the function
mallocTry
that could give you the best of both worlds. Why do
you ignore that suggestion?


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

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

[dj3vande@csclub.uwaterloo.ca.invalid]

Re: Implementing Malloc()

In article <slrnfkomlu.fsa .nospam@nospam. invalid>,
CJ <nospam@nospam. invalidwrote:

>On 26 Nov 2007 at 22:34, Eric Sosman wrote:

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

>
>All very amusing, but I think you and some of the other posters have
>misunderstoo d the context of the discussion.

[...]

>The idea is that instead of a guaranteed crash,

the programmer should handle a failure to allocate resources properly,
and the implementation should make it possible to do so.

I think you're the one who's missing the point.


dave

[Stephen Sprunk]

Re: Implementing Malloc()

"CJ" <nospam@nospam. invalidwrote in message
news:slrnfkomlu .fsa.nospam@nos pam.invalid...

Of course an implementation of malloc should return a pointer to as much
memory as requested whenever that's possible! The discussion was about
the rare failure case. Typically, programs assume malloc returns a
non-null pointer, so if it returns null on failure then the program will
crash and burn.

A program only crashes on malloc() returning NULL if the programmer is
incompetent.

The idea is that instead of a guaranteed crash, isn't it better to make
a last-ditch effort to save the program's bacon by returning a pointer
to what memory there _is_ available? If the program's going to crash
anyway, it's got to be worth a shot.

The change you propose would mean that malloc() _might_ save some
incompetent programmers but _definitely_ make it impossible for competent
programmers to write correct programs because there's no longer a way to
detect if they got the amount of memory they requested. That goes against
both the fundamental philosophy of C and common sense.

S

--
Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

[santosh]

Re: Implementing Malloc()

CJ wrote:

On 26 Nov 2007 at 22:34, Eric Sosman wrote:

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

>
All very amusing, but I think you and some of the other posters have
misunderstood the context of the discussion.
>
Of course an implementation of malloc should return a pointer to as
much memory as requested whenever that's possible! The discussion was
about the rare failure case. Typically, programs assume malloc returns
a non-null pointer, so if it returns null on failure then the program
will crash and burn.

A properly written non-trivial program is not going to "crash and burn"
when malloc() returns NULL. It will shutdown gracefully, or even notify
the user to free up some memory and perhaps try again.

The idea is that instead of a guaranteed crash,

No. There is no guaranteed crash. Consider:

#include <stdlib.h>

int main(void) {
char *p = malloc(SIZE_MAX );
if (p) { free(p); return 0; }
else return EXIT_FAILURE;
}

Where is the "crash"?

isn't it better to
make a last-ditch effort to save the program's bacon by returning a
pointer to what memory there _is_ available? If the program's going to
crash anyway, it's got to be worth a shot.

If malloc() returns NULL for failure, the program can at least exit
gracefully or even try and recover some memory and keep going, but if
it is going to indicate success but return insufficient space, then a
memory overwrite is almost certainly going to lead to either hard to
debug data corruption or a core dump from a segmentation violation.
This is (for any serious program) worse than a clean, controlled exit.

Besides your function (for whatever it's worth) can easily be written on
top of malloc() for anyone mad enough to want it. No need to include
another gets() into the Standard.