Naive Custom Malloc Implementation

[Tarique]

I have tried writing a bare bone very naive storage allocator , my
replacement for malloc (Although it still uses malloc to get memory from
the system ,only once ) I have a question here :

1.Ive just realised that FOOTERBLOCK evaluates to zero How do I include
the size of the footer structure everywhere so that it works with
pointer arithmetic ??

The tag table only stores the relevant information which can be later
used to determine memory leak. All malloc calls are tagged in this table
and all relevant free calls will delete the tags Thus at the end if I
don't end up with any tags in the table , no leaks are present.

If I need to post anything from the tag_table file , please let me know
Also, please provide useful suggestions on improving the design/code
structure.

Thanks & Regards

Here is the code :


/* MemRoutines.c*/
#include "MemRoutines.h"
#include "TagTable.h"

#define ALIGNMENT 8 /*sizeof(double)*/
#define INITALLOC 4096 /*Minimum Memory Block Obtained from OS at once*/

#define BYTE1 0x12345678
#define BYTE2 0x00000000
#define BYTE3 0x1234ABCD
#define BYTE4 0xFFFFFFFF

/* -------------------------------------------------
* |next |size |16 | User |16 |
* |Free | of |byte | Memory |byte |
* |Add |block|picket| Space |picket|
* -------------------------------------------------
* |<---header------->|^Address returned
* ^---Size-------------^
* ^-----------------Memory from OS----------------^

union header {
struct {
union header* next;
union header* prev;
size_t size;
int h4byte1;
int h4byte2;
int h4byte3;
int h4byte4;
}s;
double dummy_align_var;
};

static union header* freep = NULL;

struct footer{
int f4byte1;
int f4byte2;
int f4byte3;
int f4byte4;
};

static size_t align(size_t size){
return ((size + ALIGNMENT - 1) & ~(ALIGNMENT - 1));
}

#define FOOTERBLOCK align(sizeof(struct footer)/sizeof(union header))

static void write_header( union header* hptr,
union header* nptr,
union header* pptr,
size_t sizep){
hptr->s.next = nptr ;
hptr->s.prev = pptr;
hptr->s.size = sizep;
hptr->s.h4byte1 = BYTE1;
hptr->s.h4byte2 = BYTE2;
hptr->s.h4byte3 = BYTE3;
hptr->s.h4byte4 = BYTE4;

return ;
}

static void write_footer( struct footer* footp){

footp->f4byte1 = BYTE1; footp->f4byte2 = BYTE2;
footp->f4byte3 = BYTE3; footp->f4byte4 = BYTE4;

return;
}

static union header* getmemory(size_t n){
union header* BigMem = NULL ;

if ( n < INITALLOC ) n = INITALLOC;

if(( BigMem = malloc( n * sizeof(union header))) == NULL )
return NULL;
write_header(BigMem, NULL, NULL, n);

return BigMem;
}

void* my_malloc(char* filename,unsigned int lineno,size_t request){

union header* p = NULL;
union header* q = NULL;
size_t reqblocks = 0;

char* trailer_ptr = NULL;
struct footer* footptr = NULL;

reqblocks = ((request + sizeof(union header) -1)/sizeof(union header))\
+ FOOTERBLOCK + 1 ;

if( !is_table_initialised() ){

initialise_table();
p = getmemory( reqblocks );

if( p == NULL )
return NULL;

else {
if( p->s.size > reqblocks ){
p->s.size = reqblocks;
p->s.next = p + 2 + reqblocks + FOOTERBLOCK ;
}

else
p->s.next = NULL ;

trailer_ptr = (void*)((char*)( p + 1 ) + request);
footptr = (struct footer*) trailer_ptr;
write_footer(footptr);

freep = p + 1 + reqblocks + FOOTERBLOCK ;
write_header(freep, NULL, p + 1,(reqblocks < p->s.size ?\
(p->s.size - reqblocks) : reqblocks));

add_tag(filename,lineno, p, p + 1, request);
return (void*)( p + 1 );

}
}
else {
p = freep;
while( p != NULL && p->s.size < reqblocks ){
q = p;
p = p->s.next;
}
if( p != NULL){
if ( p->s.size > reqblocks ){
p->s.size = reqblocks;
p->s.next = p + 2 + reqblocks + FOOTERBLOCK ;
}

else
p->s.next = NULL ;

trailer_ptr = (void*)((char*)( p + 1 ) + request);
footptr = (struct footer*) trailer_ptr;
write_footer(footptr);

freep = p + 1 + reqblocks + FOOTERBLOCK ;
write_header(freep, NULL, p + 1,(reqblocks < p->s.size ?\
(p->s.size - reqblocks) : reqblocks));

add_tag(filename,lineno, p, p + 1, request);
return (void*)( p + 1 );
}
}
return NULL;
}

 

[Dann Corbit]

I have tried writing a bare bone very naive storage allocator , my
replacement for malloc (Although it still uses malloc to get memory from
the system ,only once ) I have a question here :

1.Ive just realised that FOOTERBLOCK evaluates to zero How do I include
the size of the footer structure everywhere so that it works with
pointer arithmetic ??

The tag table only stores the relevant information which can be later
used to determine memory leak. All malloc calls are tagged in this table
and all relevant free calls will delete the tags Thus at the end if I
don't end up with any tags in the table , no leaks are present.

If I need to post anything from the tag_table file , please let me know
Also, please provide useful suggestions on improving the design/code
structure.

Thanks & Regards

Here is the code :


/* MemRoutines.c*/
#include "MemRoutines.h"
#include "TagTable.h"

#define ALIGNMENT 8 /*sizeof(double)*/
#define INITALLOC 4096 /*Minimum Memory Block Obtained from OS at once*/

#define BYTE1 0x12345678
#define BYTE2 0x00000000
#define BYTE3 0x1234ABCD
#define BYTE4 0xFFFFFFFF

/* -------------------------------------------------
* |next |size |16 | User |16 |
* |Free | of |byte | Memory |byte |
* |Add |block|picket| Space |picket|
* -------------------------------------------------
* |<---header------->|^Address returned
* ^---Size-------------^
* ^-----------------Memory from OS----------------^

union header {
struct {
union header* next;
union header* prev;
size_t size;
int h4byte1;

Why create a naive memory allocator when choices like this are
available:
http://www.hoard.org/

 

[Tarique]

....snip...

Why create a naive memory allocator when choices like this are
available:
http://www.hoard.org/

I know that .I am writing this only as an exercise and the only
problem I guess I have is that I cannot get the correct offset for
the footer structure that I can use in pointer arithmetic.

The code seems to work, compiles fine, produces results which look
ok except the footer memory space. On a sample run I found the footer
to be occupying 69 bytes when it should have been 16. The rest was just
as expected.

Thanks anyways

 

[bartc]

1.Ive just realised that FOOTERBLOCK evaluates to zero How do I include
the size of the footer structure everywhere so that it works with pointer
arithmetic ??

#define ALIGNMENT 8 /*sizeof(double)*/

Why not just use sizeof(double)?

union header { ....
};

static union header* freep = NULL;

struct footer{
int f4byte1;
int f4byte2;
int f4byte3;
int f4byte4;
};

static size_t align(size_t size){
return ((size + ALIGNMENT - 1) & ~(ALIGNMENT - 1));
}

#define FOOTERBLOCK align(sizeof(struct footer)/sizeof(union header))

Is the question why FOOTERBLOCK is zero?

You're dividing 16 by 32, which is zero.

The rest of your question is not clear.

 

[Tarique]

Why not just use sizeof(double)?


Is the question why FOOTERBLOCK is zero?

You're dividing 16 by 32, which is zero.

I realised that before posting here.

The rest of your question is not clear.

How do I get the offset equal to the size of the structure ? I have
used the macro FOOTERBLOCK thinking it was working properly with the
pointer arithmetic in my_malloc( ).

I think I will need to use bytewise arithmetic right ? From the header ,
I can reach the footer address and then I will have to use bytewise
arithmetic to get to the next header.

something like (void*)((char*)p + sizeof(struct footer))
Am I right ?

I hope the question is clearer this time around.

 

[Gene]

I realised that before posting here.




How do I get the offset equal to the size of the structure ? I have
used the macro FOOTERBLOCK thinking it was working properly with the
pointer arithmetic in my_malloc( ).

I think I will need to use bytewise arithmetic right ? From the header ,
I can reach the footer address and then I will have to use bytewise
arithmetic to get to the next header.

something like (void*)((char*)p + sizeof(struct footer))
Am I right ?

I hope the question is clearer this time around.- Hide quoted text -

- Show quoted text -

It looks like you are trying to do the size calculation in units of
header block size. The problem is (obviously) that the footer block is
smaller than the header. I'd guess you want FOOTERBLOCK to be (sizeof
(struct footer) + sizeof(struct header) - 1) / sizeof(struct header).
This is the whole number of header blocks needed to hold one footer
block.

However, I think your whole code will be simpler if you do all size
calculations in bytes.

Another note is that free list information (like the next free
address) is not needed in an allocated block. Allocators I've looked
at use a union to overlay free list pointers with allocated header
block information, since they're never needed at the same time.

 

[bartc]

I realised that before posting here.

How do I get the offset equal to the size of the structure ? I have
used the macro FOOTERBLOCK thinking it was working properly with the
pointer arithmetic in my_malloc( ).

I think I will need to use bytewise arithmetic right ? From the header , I
can reach the footer address and then I will have to use bytewise
arithmetic to get to the next header.

something like (void*)((char*)p + sizeof(struct footer))
Am I right ?

I hope the question is clearer this time around.

Afraid not (to me at least).

What exactly is FOOTERBLOCK? You say offset to struct, but what offset to
what struct? The offset of the footer from the header at the start of the
block?

Why do you need to divide the footer size by the header size?

(I assume the ascii diagram is of one of the large blocks of memory you set
up, from which your smaller blocks are allocated, and there's a header at
the start of this large block, and a footer at the end)

Then, the meaning of INITALLOC is not clear; you're multiplying this by the
size of the header struct and allocating that number of bytes from malloc().
That seems odd.

Maybe you need a more detailed picture!

 

[Tarique]

Afraid not (to me at least).

What exactly is FOOTERBLOCK? You say offset to struct, but what offset
to what struct? The offset of the footer from the header at the start of
the block?

Why do you need to divide the footer size by the header size?

(I assume the ascii diagram is of one of the large blocks of memory you
set up, from which your smaller blocks are allocated, and there's a
header at the start of this large block, and a footer at the end)

Then, the meaning of INITALLOC is not clear; you're multiplying this by
the size of the header struct and allocating that number of bytes from
malloc(). That seems odd.

Maybe you need a more detailed picture!

I am sorry I could not make my question any clear! Ok , the whole
situation is like this : I get a big chunk of memory at once initially.
On a call to my_malloc I , chop it up and pass the required address to
the calling function .

When I malloc at start, I have the starting memory address of the whole
chunk of memory. once my_malloc( ) is called, I chop it into a block of
structure shown above

--------------------------------------------------------
|Block shown in | |
| Deiagram above is USED now| FREE SPACE|

--------------------------------------------------------
^--my_malloc()called once---^
^--This part is used up-----^
^--------------Total memory Obtained at once------------^

When i get the pointer to the start of the smaller block,
I move from the header to the footer and then to the next header.
This is where the problem lies. Since I have used pointer arihmetic,
I tried using *FOOTERBLOCK as size of struct in blocks of header,* so
that I get the Correct movement of pointer and then later realised that
it would have no effect since it evaluates to zero!

Bart had rightly said that I am trying to do the size calculation in
units of header block size& the problem is that the footer block is
smaller than the header!

 

[bartc]

....
I am sorry I could not make my question any clear! Ok , the whole
situation is like this : I get a big chunk of memory at once initially.
On a call to my_malloc I , chop it up and pass the required address to the
calling function .

When I malloc at start, I have the starting memory address of the whole
chunk of memory. once my_malloc( ) is called, I chop it into a block of
structure shown above

--------------------------------------------------------
|Block shown in | |
| Deiagram above is USED now| FREE SPACE|
--------------------------------------------------------
^--my_malloc()called once---^
^--This part is used up-----^
^--------------Total memory Obtained at once------------^

When i get the pointer to the start of the smaller block,
I move from the header to the footer and then to the next header.
This is where the problem lies. Since I have used pointer arihmetic,
I tried using *FOOTERBLOCK as size of struct in blocks of header,* so that
I get the Correct movement of pointer and then later realised that
it would have no effect since it evaluates to zero!

Bart had rightly said that I am trying to do the size calculation in units
of header block size& the problem is that the footer block is smaller than
the header!

Well, that might have been Gene who said that.

(For stuff like this, I would use byte (or char) units for sizes and
offsets, (and probably for pointers too).

After all, ALLOCSIZE is in bytes, presumably the size argument to my_malloc
is in bytes (but this is not specified), the return value from my_alloc is
void* so it might as well be calculated in bytes. INITALLOC however must be
in some other units (of header-blocks?).)

It seems you are allocating space in multiples of header-blocks (in which
case 'header' is a bad name for such a block). If FOOTERBLOCK is supposed to
be the number of extra header-blocks taken up by a footer-block, then the
calculation would be more like:

(sizeof(struct footer)-1)/(sizeof(union header)+1

which should yield 1 header block (no alignment code needed). (But if footer
is never bigger than a header, just use 1.)

Here however:

trailer_ptr = (void*)((char*)( p + 1 ) + request);
footptr = (struct footer*) trailer_ptr;
write_footer(footptr);

if request is in fact in bytes, then you might be writing to an unaligned
footer record, and which doesn't correspond to the one you're reserved space
for. Although that may be based on my (probably incorrect) understanding
that your basic allocation block looks like:

* 1 header block to store header stuff
* N header blocks for the caller's data, ie. 'request' bytes (with up to 31
spare bytes in the last block) (and you return a pointer to the first of
these)
* 1 header block to store the footer (with 16 spare bytes following)

So you are writing that footer either in the first 16 of those spare 31
bytes, or straddling the last of the N blocks and the footer, or (when
request is a multiple of 16) entirely in that last block.