Re: Suggestions for my mallocator
- From: Barry Schwarz <schwarzb@xxxxxxxxx>
- Date: Wed, 27 Dec 2006 11:09:46 -0800
On 27 Dec 2006 09:36:03 -0800, nfwavzrdvwl@xxxxxxxxxxxxxx wrote:
Thanks to all on the forum for your thoughts :)
I guess it's a question of trade-offs here between flexibility (how
many allocations do you allow?), speed vs. memory usage (how much
fragmentation is tolerable?), etc. I've come up with what seems like a
pretty good way of doing this, which ensures absolutely no
fragmentation occurs - once a block is freed, the deallocator
immediately tidies things up. An array of pointers keeps references to
all the currently allocated blocks.
The only slight disadvantage of this approach is that it necessitates a
slightly different API for malloc and free, with an extra level of
indirection.
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#define SYSTEM_RAM ( 1<<30 )
#define MAX_TO_USE ( ((SYSTEM_RAM) / 3) * 2 )
#define MAX_ALLOCS ( (MAX_TO_USE) >> 10 )
/* set up heap to allocate from */
static char heap[MAX_TO_USE], *top=heap, *oblivion=heap+MAX_TO_USE;
For ease of discussion below, let's assume top contains 0x10000 and
oblivion contains 0x20000.
/* pointers to allocated blocks */
static char *blocks[MAX_ALLOCS];
void **mymalloc(long bytes)
Let's also assume bytes is 0x1000 for each of two calls.
Why not use size_t for consistency
A void** is not guaranteed to be able to hold the address of anything
other than a void*.
Since a void* can hold the address of anything, there is no reason not
to use it.
{
char **q;
if(top+bytes<oblivion) {
/* find first free pointer in array */
for(q=blocks; *q; q++)
On first call, blocks[0] is NULL, *q is false, and loop exits before
first iteration.
On second call, loop exits when q points to block[1].
if(q==blocks+MAX_ALLOCS)
return NULL;
*q=top;
On first call, blocks[0] now contains 0x10000.
On second call, blocks[1] now contains 0x11000.
top+=bytes;
On first call, top now contains 0x11000.
On second call, top now contains 0x12000.
return (void **) q;
Why are you returning the address of an element in blocks when you
could just as easily return an address in heap.
On first call, you return &blocks[0].
On second call, your return &blocks[1].
}
return NULL;
}
void myfree(void **q)
Let's assume we return block[1] first.
Let's return block[0] second but pretend the first call never
occurred.
{
char **next, **r;
long size;
if(q==NULL || *q==NULL)
return;
/* OK... let's find the start of the block after the one to be freed
*/
next=⊤
On first call, top contains 0x12000.
On second call also.
for(r=blocks; r<blocks+MAX_ALLOCS; r++)
if((char *) *q<*r && *r<*next)
The second relation will not be evaluated until the first one is true.
On first call, *q is 0x11000.
On first iteration, *r is 0x10000; if is false.
On second iteration *r is 0x11000; if is false.
On all subsequent iterations, *r is NULL; if is false.
On second call, *q is 0x10000.
On first iteration, *r is ox10000; if is false
On second call, *r is 0x11000 and *next is 0x12000; if is true.
On subsequent calls, *r is NULL; if is false.
next=r;
You seem to be missing an exit from the for loop once you find the
block you are interested in.
On first call, you fall out of for loop never changing next and r
pointing one byte beyond end of blocks.
On second call, next is set to &blocks[1].
size=next-(char **) q; /* size of the block */
This arithmetic does not yield the number of bytes in the block.
On first call, next contains &top and q contains &block[1]. The
difference has no meaning since it is simply a measure (but not in
bytes) of the space between to unrelated objects defined at file
scope.
On second call, next contains &blocks[1] and q contains block[0]. The
difference is guaranteed to always be exactly 1.
/* shift down to fill in block to be freed */
memmove(*q, *next, MAX_TO_USE-(next-blocks));
Your third argument computes the wrong number of bytes. next-blocks
is the number of elements in blocks, not the number of bytes in heap.
Furthermore, by moving data in heap, you have broken the interface
with your users. Once you have returned the address of blocks[N] to a
user and he has dereferenced it to get the address of heap[M] as the
start of his allocated area, you may not move heap[M] to some other
area in heap.
/* move down all pointers above next */
top=*next-size;
for(r=blocks; r<blocks+MAX_ALLOCS; r++)
if(*next<=*r)
*r-=size;
Once you move any of the entries in blocks, you have broken the
interface with your users. Once you have returned the address of
blocks[N] to a user, you may not alter the value contained in
blocks[N] until the user frees it. Your user is entitled to use the
value in blocks[N] as often as he wants to get to the start of his
allocated area.
}
int main()
{
char **s=(char **) mymalloc(8);
char **t=(char **) mymalloc(7);
strcpy(*s,"Hello, ");
strcpy(*t,"world!");
printf("%s%s\n", *s, *t);
myfree((void **) s);
myfree((void **) t);
return 0;
}
PS. Thanks for the heads-up on the K&R2 discussion - I've got a pdf of
it coming down as a torrent as we speak, so I'll read it as soon as I
get it :)
K&R2 is not legally available as a pdf.
Remove del for email
.
- Follow-Ups:
- Re: Suggestions for my mallocator
- From: nfwavzrdvwl
- Re: Suggestions for my mallocator
- References:
- Suggestions for my mallocator
- From: nfwavzrdvwl
- Re: Suggestions for my mallocator
- From: Richard Heathfield
- Re: Suggestions for my mallocator
- From: nfwavzrdvwl
- Re: Suggestions for my mallocator
- From: Malcolm
- Re: Suggestions for my mallocator
- From: nfwavzrdvwl
- Suggestions for my mallocator
- Prev by Date: Re: c / c++ : is it end of era ?
- Next by Date: Re: switch statement - ANSI-C
- Previous by thread: Re: Suggestions for my mallocator
- Next by thread: Re: Suggestions for my mallocator
- Index(es):
Relevant Pages
|
