Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Implementing Malloc()

Reply
Thread Tools

Implementing Malloc()

 
 
jacob navia
Guest
Posts: n/a
 
      11-26-2007
jacob navia wrote:
> 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.


--
jacob navia
jacob at jacob point remcomp point fr
logiciels/informatique
http://www.cs.virginia.edu/~lcc-win32
 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      11-26-2007
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.

--
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
 
 
 
CBFalconer
Guest
Posts: n/a
 
      11-26-2007
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

 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      11-26-2007

"James Kuyper" <(E-Mail Removed)> wrote 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_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.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

 
Reply With Quote
 
Marco Manfredini
Guest
Posts: n/a
 
      11-26-2007
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.
 
Reply With Quote
 
Flash Gordon
Guest
Posts: n/a
 
      11-26-2007
Malcolm McLean wrote, On 26/11/07 23:27:
>
> "James Kuyper" <(E-Mail Removed)> wrote 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_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?
--
Flash Gordon
 
Reply With Quote
 
Dik T. Winter
Guest
Posts: n/a
 
      11-27-2007
In article <fiflgn$5ds$(E-Mail Removed)> Marco Manfredini <(E-Mail Removed)> writes:
....
> > 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/
 
Reply With Quote
 
Dik T. Winter
Guest
Posts: n/a
 
      11-27-2007
In article <(E-Mail Removed)-gordon.me.uk> Flash Gordon <(E-Mail Removed)> writes:
> 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/
 
Reply With Quote
 
Richard Tobin
Guest
Posts: n/a
 
      11-27-2007
In article <(E-Mail Removed)-gordon.me.uk>,
Flash Gordon <(E-Mail Removed)> wrote:

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


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
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
 
Reply With Quote
 
Richard Tobin
Guest
Posts: n/a
 
      11-27-2007
In article <fiflgn$5ds$(E-Mail Removed)>,
Marco Manfredini <(E-Mail Removed)> wrote:

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

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Implementing Interface Gomathi ASP .Net 1 11-17-2005 03:09 PM
Need help implementing a proj on SPARTAN3 Riccardo Fregonese VHDL 2 01-03-2005 01:21 PM
Implementing the CORDIC algorithm without using Real Data Type Johnsy Joseph VHDL 2 10-29-2004 10:49 AM
Implementing E1 - E3 Dev VHDL 1 09-09-2004 09:06 AM
vhdl for implementing pre-fetch and an instruction cache Eqbal Z VHDL 3 11-16-2003 06:07 AM



Advertisments