First Fit Memory Allocation -- review
KIRAN
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;
}
/************************************************/