First Fit Memory Allocation -- review

[KIRAN]

Hi Guys,
I have implemented first fit memory manager with the following
assumtions,

1. This is platform specific and is not portable.
2. sizeof (unsigned int) = 4
3. pointer returned by dg_malloc is word aligned (on my system 1 word
= 4 bytes)
4. I have 2 files dg_memory.c and dg_memory.h

I need experts opinion/comments in memory allocation/de-allocation
routines to improve it further. Help is appreciated.

Thanks,
Kiran


/*<------------------------contents of
dg_memory.h--------------------------------> */
#ifndef DG_MEMORY_H__

#define DG_MEMORY_H__



/*

* defines

*/

#define APP_POOL_SIZE (1024 * 1024) /* size of application
memory pool */

#define ROUND_DOWNTO32(p_) (p_ & ~3U)

#define ROUND_UPTO32(x_) (((x_) + 3U) & ~3U) /* round to the next
multiple of 4 */



#define mCHECK_POOL_POINTER(pl_, ptr_) do {\

unsigned char *pU8;\

pU8 = pl_->start;\

pU8 += pl_->size;\

if (ptr_ < pl_->start || ptr_ > pU8) \

{\

printf ("Error> Pool pointer is not valid\n");\

}\

} while (0)



/*

* typedefs

*/

/*!< Structure definition for a free memory block */

struct tBlock {

unsigned int size; /*!< size of this block */

struct tBlock *nextp; /*!< pointer to the next free block */

};





/*!

* @struct

* @brief Defines a structure for a memory pool

*/

struct tMemPool {

void *sem;

/*!< semaphore to protect this pool */

struct tBlock *avail;

/*!< head pointer to the list of free blocks */

unsigned char *start;

/*!< start pointer to pool */

unsigned int size;

/*!< size of this pool */

};



/*!


******************************************************************************

* @brief Memory pool initialization function

* @details This function intializes memory pool for runtime mallocs/
frees

* This fucction should be calles before calling dg_malloc/
dg_free

* @return TRUE on success

* FALSE in error


******************************************************************************

*/

unsigned char dg_mem_init (struct tMemPool *poolp, unsigned char
*startp, unsigned int size);



/*!


******************************************************************************

* @brief Runtime memory allocation function

* @details This function is used to allocate memory from a specific
pool

* @param poolp pointer to pool

* @param size size of requested memory

* @return void


******************************************************************************

*/



void *dg_malloc (struct tMemPool *poolp, unsigned int size);





/*!


*****************************************************************************

* @brief function to retura a memory block into a pool

* @details This function returns a free memory blocl to a pool

* @param pointer returned by dg_malloc

* @return void


*****************************************************************************

*/

void dg_free (struct tMemPool *poolp, void *ptr);



#endif /* DG_MEMORY_H__ */






/*<------------------------contents of
dg_memory.c--------------------------------> */
/************************/
#include <stdio.h>

#include <memory.h>

#include <stdlib.h>



/*

* Includes

*/



#include "dg_memory.h"



/*

* Defines

*/



/*

* Typedefs

*/

/*

* Imported variables

*/

/*

* Exported variables

*/

/*

* internal variables

*/

static unsigned char app_mem[APP_POOL_SIZE];

static struct tMemPool app_mem_pool;



/*

* internal function prototypes

*/

/*

* internal function definitions

*/

/*

* Function definitions

*/



unsigned char dg_mem_init (struct tMemPool *poolp, unsigned char
*startp, unsigned int size)

{

struct tBlock *t;



/* round down to multiple of 4 */

size = ROUND_DOWNTO32(size);



t = (struct tBlock*)startp;

t->nextp = NULL;

t->size = size;



poolp->avail = t;

poolp->size = size;

poolp->start = startp;



/* TBD: Semaphore to protect to pool */

poolp->sem = NULL;



return 0;



}



void *dg_malloc (struct tMemPool *poolp, unsigned int size)

{

struct tBlock **pp;

struct tBlock *p;

struct tBlock *t;

unsigned char *ret = NULL;

unsigned int r;

unsigned char *pU8;



if (!size) {

int a = size;

}

printf ("Requested size = %u\n", size);



size = ROUND_UPTO32(size);

/* increase the size to store book keeping information */

size += 4;

printf ("Rounded size = %u\n\n",size);



pp = &poolp->avail;





/*

* we keep searching till we get a block. We need to handle 3
different sceanrios,

*

* 1. A block is found whose size == requested size

* ------ The free block is unlinked from list and returned to
user

*

* 2. A block is found whose size > reuested size

* ------ (a) computed remaining size, r = block size - requested
size

* (b) IF (r > sizeof(struct tBlock))

* split the block into 2 blocks, B1 and B2. Put B2
into free list,

* return B1 to user

* (c) (r < sizeof(struct tBlock))

* unlink the block and return the block to user

*/

/*
* list insertion/deletion using pointer-to-pointer is copied/
stolen from Chris Torek's contribution
* to comp.lang.c . Thanks Chris
*/

while ((p = *pp) != NULL)

{

if (p->size > size) {

if (p->size == size || ((r = p->size - size) < sizeof(struct
tBlock))) {

*pp = p->nextp;

} else {

pU8 = (unsigned char *)p;

pU8 += size;



t = (struct tBlock*)pU8;

t->size = p->size - size;

t->nextp = p->nextp;

p->size = size;

*pp = t;

}

//*pp = p->nextp;

ret = (unsigned char*)p;

ret += sizeof (unsigned int);

p->nextp = NULL; /* optional */

break;

}

pp = &p->nextp;

} /* while */



return ret;

}





void dg_free (struct tMemPool *poolp, void *ptr)

{

unsigned char *pU8;

struct tBlock **pp;

struct tBlock *p;

struct tBlock *np;

struct tBlock *prevp;

struct tBlock *t;



pU8 = ptr;

pU8 -= sizeof (unsigned int);



/* check the pointer healthiness */

mCHECK_POOL_POINTER (poolp, pU8);



pp = &poolp->avail;

np = (struct tBlock*)pU8;

np->nextp = NULL;



//printf ("Free: Size = %u\n", np->size);



prevp = NULL;



while ((p = *pp) != NULL)

{

if (np < p)

{

np->nextp = *pp;

*pp = np;

t = np->nextp;



if (prevp) {

pU8 = (unsigned char *)prevp;

pU8 += prevp->size;

if (pU8 == (unsigned char *)np) {

prevp->size += np->size;

prevp->nextp = np->nextp;

np = prevp;

}

}



if (t) {

pU8 = (unsigned char *)np;

pU8 += np->size;

if (pU8 == (unsigned char*)t) {

np->size += t->size;

np->nextp = t->nextp;

}

}

break;



}

prevp = *pp;

pp = &p->nextp;

} /* while */



if (NULL == p) {

*pp = np;

}



}



#define MAX_SIZE (1024 * 100)



static unsigned char *allocated_ptrs[MAX_SIZE];



int main (void)

{

signed int ii;

unsigned char *p;



dg_mem_init (&app_mem_pool, app_mem, sizeof (app_mem));







for (ii = 0; ii < MAX_SIZE; ii += 2)

{

allocated_ptrs[ii] = dg_malloc (&app_mem_pool, rand()%1024);

if (!allocated_ptrs[ii]) {

break;

}

allocated_ptrs[ii + 1] = dg_malloc (&app_mem_pool, rand()%1024);

if (!allocated_ptrs[ii + 1]) {

break;

}

}



for (ii = 0; ii < MAX_SIZE; ii += 2)

{

if (allocated_ptrs[ii])

dg_free (&app_mem_pool, allocated_ptrs[ii]);



if (allocated_ptrs[ii+1])

dg_free (&app_mem_pool, allocated_ptrs[ii+1]);

}



p = dg_malloc (&app_mem_pool, 20);





return 0;

}
/************************************************/