F
Faay
Hi all,
I have written this storage allocator using a first fit algorithm.So I
have maintain a "free list" which is a list of all the unused memory
blocks obtained from the system during the course of the program. My
problem begins when I try to destroy the list at the end of the program
, when all memory allocated by my_malloc() has been freed up by calls to
my_free(). ( I use a "tag table" to keep this information.Every call to
my_malloc()is tagged in the table and every call to my_free() is deleted
from the table. )
I can easily traverse the "free list" but when I try to destroy it , my
prgram crashes! I am somehow losing the next address in the while loop
of the freelist_destroy2() routine. Please help.
Thanks & Regards
#include <string.h>
#include "MemRoutines.h"
#include "TagTable.h"
/*
* Alignment is chosen that will be forced on all blocks allocated.
* All allocated blocks will be rounded up to a multiple of this
* size.
*/
#define ALIGNMENT sizeof(double)
/*
* LARGEMEMORY is the minimum chunk of memory block obtained from
* the OS at once.This size is a multiple of ALIGNMENT.my_malloc()
* called with requested byte size greater than LARGEMEMORY will
* fail by design.
*/
#define LARGEMEMORY 4*1024*1024 /*4MB memory obtained from system at once */
/*
* ------------------------------------------------------
* |Next Free |Size of | User is concerned only about |
* | Memory |Allocated| this portion of memory |
* |Address |Block | and has no knowledge of rest |
* ------------------------------------------------------
* |<------Header------>|^Address Returned to user
* ^-----User Requested Size------^
* ^-------Memory Needed for the Allocation-------------^
*
* " FRAMEWORK OF THE MEMORY MANAGEMENT SCHEME "
*/
/*
* Header is defined assuming double has the strictest memory
* alignment requirement
*/
union header {
struct {
union {
int sign; /*Used when the block is returned by malloc( ) */
union header* next; /*Used when the block is in free list */
}u;
size_t size;/*Size of block including this header*/
}s;
double dummy_align_var;
};
#define SIGN 0xD7E529A2 /* Our magical signature */
/*
* Global Pointer within File scope which points to the start
* of 'free' list
*/
static union header* freelist = NULL;
/*
* The function below will round off the size to a multiple
* of ALIGNMENT Works by setting the last few bits to zero.
* Exploits the fact that ALIGNMENT is a power of 2
*/
static size_t align(size_t size){
return ((size + ALIGNMENT - 1) & ~(ALIGNMENT - 1));
}
/*
* The following macros generate the rounded off size for the
* header and the footer.The overhead size is the extra memory
* that needs to be allocated in addition to user's request.
*/
#define HEADER_SIZE align(sizeof(union header))
void freelist_destroy(void)
{
union header** old = &freelist;
if( old != NULL && *old != NULL ){
free (*old);
*old = NULL;
}
return ;
}
/*This is where the problem lies*/
void freelist_print(void){
union header* p = freelist;
union header* prev = NULL;
int count = 0;
while ( p != NULL ){
printf("Node %d : 0x%p Next\
:0x%p\n",count,(void*)p,(void*)(p->s.u.next) );
p = p->s.u.next;
count++;
}
}
void freelist_destroy2(void)
{
union header* p = freelist;
union header* nextofp = NULL;
while( p != NULL ){
nextofp = p->s.u.next;
free(p);
p = nextofp;
}
return ;
}
/*
* Gets memory block from the OS.malloc() is
* used instead of actual system calls.
*/
union header* getmemory(size_t n){
union header* BigMem = NULL;
if(( BigMem = malloc( n * sizeof(union header))) == NULL )
return NULL;
BigMem->s.size = n;
BigMem->s.u.next = NULL;
return BigMem;
}
void* my_malloc(char* filename,
unsigned int lineno,
size_t request){
union header* prev = NULL;
union header* p = NULL;
union header* memblock = NULL;
size_t space_required = align( request + HEADER_SIZE );
size_t space_left = 0;
if((signed)request <= 0){
/*add_tag(filename,lineno,NULL,NULL,0);*/
return NULL; /*Bad Request*/
}
/*
* Traverse freelist sequentially until appropriate memory block
* is found is found in the freelist.
*/
p = freelist;
while( p != NULL && p->s.size < space_required ){
prev = p;
p = p->s.u.next;
}
/*
* No appropriate block present to fulfill request - Either this
* is the first call to memory or memory block already in the
* freelist is insuffient to fulfill request.
*/
if ( p == NULL ){
if(( memblock = getmemory(LARGEMEMORY)) == NULL ){
/*add_tag(filename,lineno,NULL,NULL,0);*/
return NULL;
}
/*
* Search the free list to insert this block at appropriate loc
* The list is kept sorted on addresses
*/
prev = NULL;
p = freelist;
while ( p != NULL && p < memblock ){
prev = p;
p = p->s.u.next;
}
memblock->s.u.next = p;/*Connect the block to list*/
/*
* The freelist is empty and the memory block is added as the
* first node in the list.
*/
if( prev == NULL )
freelist = memblock;
/*
* The memory block is added as the last node in the free list
*/
else if ( p == NULL ){
memblock->s.u.next = NULL;
prev->s.u.next = memblock;
}
/*
* The memory block is added somewhere in the middle of the
* free list
*/
else
prev->s.u.next = memblock;
/*
* Now p points to a memory block which is of appropriat size
* This block is then either chopped or passed as it is to the
* user
*/
p = memblock;
}
/*
* Calculate size requirements now
*/
if ( space_required > p->s.size ){
/*add_tag(filename,lineno,NULL,NULL,0);*/
return NULL;
}
space_left = p->s.size - space_required;
if ( space_left >= sizeof(union header) + sizeof(int) ){
/*
* Split the block, keep p in free list and return upper end
* of block.This way the pointers dont need to be saved again.
* Simpler
*/
memblock = (union header *)( (char*)p + space_left );
memblock->s.size = space_required;
memblock->s.u.sign = SIGN;/*Unlink Block*/
p->s.size = space_left;
add_tag(filename, lineno, memblock, memblock + 1, request );
return (void*)( memblock + 1 );
}
/*
* No split, unlink the block and return it to user for use
*/
if ( prev == NULL )
freelist = p->s.u.next;
else
prev->s.u.next = p->s.u.next;
p->s.u.sign = SIGN;
add_tag(filename, lineno, p, p + 1, request );
return (void*)( p + 1 );
}
void my_free(char* filename_f,
unsigned int lineno_f,
void* ptr2free){
union header* memblock = NULL;
union header* prev = NULL;
union header* p = NULL;
unsigned int tag_no = 0;
/*
* Freeing a NULL pointer is legal , free() should not do
* anything. Simply return
*/
if( ptr2free == NULL ){
/*fprintf(stderr,"Line %u in %s is trying to free a NULL pointer\n\n",\
lineno_f,filename_f);*/
return ;
}
memblock = (union header*)ptr2free - 1 ;
/*
* My Signature not present and hence the pointer was not
* produced by my_malloc()
*/
if ( memblock->s.u.sign != SIGN ){
/*fprintf(stderr,"Line %u in %s is trying to free a wild pointer\n\n",\
lineno_f,filename_f);*/
return ;
}
/* Find the tag number in the tag table*/
for( tag_no = 0 ; tag_no < TAG_MAX; tag_no++ ){
if( tag_table[tag_no].returned_address == ptr2free )
break;
}
/*
* Search the free list to find an appropriate location to
* insert the memory block
*/
prev = NULL ;
p = freelist;
while( p != NULL && p < (union header*)ptr2free ){
prev = p ;
p = p->s.u.next;
} /*At this point of time , prev < memblock < p */
/*
* If prev == NULL , we must have either of the following two
* cases:
* 1. The Freelist is empty and the node has to be inserted as
* the first node in the free list.
* 2.There is a single node in freelist and the address of the
* memblock is less than the address of the first node , hence
* again this block is inserted as the first node in the list
*/
if( prev == NULL ){
memblock->s.u.next = p;
freelist = prev = memblock;
delete_tag(tag_no);
}
/*
* The memory block starts exactly where the previous block
* ends hence the two blocks are "combined". The size of the
* previous block is simply allowed to grow. There is nothing
* to link here
*/
if( (union header*)(prev + prev->s.size) == memblock ){
prev->s.size += memblock->s.size;
delete_tag(tag_no);
}
/*
* The memory block has to be inserted between the two adjacent
* blocks. Keep track of the 'new prev' as well.
*/
else {
memblock->s.u.next = p;
prev->s.u.next = memblock;
prev = memblock;
delete_tag(tag_no);
}
/*
* Check if the next block is adjacent to the newly added block
*/
if ( p != NULL && ((union header*)(memblock + memblock->s.size) == p) ){
memblock->s.size += p->s.size ;
memblock->s.u.next = p->s.u.next ;
delete_tag(tag_no);
}
/*
* All the my_malloc() calls have been successfully freed,now
* release all memory to the OS before quitting
*/
if( !is_table_initialised() )
freelist_print();
//freelist_destroy2();
return;
}
I have written this storage allocator using a first fit algorithm.So I
have maintain a "free list" which is a list of all the unused memory
blocks obtained from the system during the course of the program. My
problem begins when I try to destroy the list at the end of the program
, when all memory allocated by my_malloc() has been freed up by calls to
my_free(). ( I use a "tag table" to keep this information.Every call to
my_malloc()is tagged in the table and every call to my_free() is deleted
from the table. )
I can easily traverse the "free list" but when I try to destroy it , my
prgram crashes! I am somehow losing the next address in the while loop
of the freelist_destroy2() routine. Please help.
Thanks & Regards
#include <string.h>
#include "MemRoutines.h"
#include "TagTable.h"
/*
* Alignment is chosen that will be forced on all blocks allocated.
* All allocated blocks will be rounded up to a multiple of this
* size.
*/
#define ALIGNMENT sizeof(double)
/*
* LARGEMEMORY is the minimum chunk of memory block obtained from
* the OS at once.This size is a multiple of ALIGNMENT.my_malloc()
* called with requested byte size greater than LARGEMEMORY will
* fail by design.
*/
#define LARGEMEMORY 4*1024*1024 /*4MB memory obtained from system at once */
/*
* ------------------------------------------------------
* |Next Free |Size of | User is concerned only about |
* | Memory |Allocated| this portion of memory |
* |Address |Block | and has no knowledge of rest |
* ------------------------------------------------------
* |<------Header------>|^Address Returned to user
* ^-----User Requested Size------^
* ^-------Memory Needed for the Allocation-------------^
*
* " FRAMEWORK OF THE MEMORY MANAGEMENT SCHEME "
*/
/*
* Header is defined assuming double has the strictest memory
* alignment requirement
*/
union header {
struct {
union {
int sign; /*Used when the block is returned by malloc( ) */
union header* next; /*Used when the block is in free list */
}u;
size_t size;/*Size of block including this header*/
}s;
double dummy_align_var;
};
#define SIGN 0xD7E529A2 /* Our magical signature */
/*
* Global Pointer within File scope which points to the start
* of 'free' list
*/
static union header* freelist = NULL;
/*
* The function below will round off the size to a multiple
* of ALIGNMENT Works by setting the last few bits to zero.
* Exploits the fact that ALIGNMENT is a power of 2
*/
static size_t align(size_t size){
return ((size + ALIGNMENT - 1) & ~(ALIGNMENT - 1));
}
/*
* The following macros generate the rounded off size for the
* header and the footer.The overhead size is the extra memory
* that needs to be allocated in addition to user's request.
*/
#define HEADER_SIZE align(sizeof(union header))
void freelist_destroy(void)
{
union header** old = &freelist;
if( old != NULL && *old != NULL ){
free (*old);
*old = NULL;
}
return ;
}
/*This is where the problem lies*/
void freelist_print(void){
union header* p = freelist;
union header* prev = NULL;
int count = 0;
while ( p != NULL ){
printf("Node %d : 0x%p Next\
:0x%p\n",count,(void*)p,(void*)(p->s.u.next) );
p = p->s.u.next;
count++;
}
}
void freelist_destroy2(void)
{
union header* p = freelist;
union header* nextofp = NULL;
while( p != NULL ){
nextofp = p->s.u.next;
free(p);
p = nextofp;
}
return ;
}
/*
* Gets memory block from the OS.malloc() is
* used instead of actual system calls.
*/
union header* getmemory(size_t n){
union header* BigMem = NULL;
if(( BigMem = malloc( n * sizeof(union header))) == NULL )
return NULL;
BigMem->s.size = n;
BigMem->s.u.next = NULL;
return BigMem;
}
void* my_malloc(char* filename,
unsigned int lineno,
size_t request){
union header* prev = NULL;
union header* p = NULL;
union header* memblock = NULL;
size_t space_required = align( request + HEADER_SIZE );
size_t space_left = 0;
if((signed)request <= 0){
/*add_tag(filename,lineno,NULL,NULL,0);*/
return NULL; /*Bad Request*/
}
/*
* Traverse freelist sequentially until appropriate memory block
* is found is found in the freelist.
*/
p = freelist;
while( p != NULL && p->s.size < space_required ){
prev = p;
p = p->s.u.next;
}
/*
* No appropriate block present to fulfill request - Either this
* is the first call to memory or memory block already in the
* freelist is insuffient to fulfill request.
*/
if ( p == NULL ){
if(( memblock = getmemory(LARGEMEMORY)) == NULL ){
/*add_tag(filename,lineno,NULL,NULL,0);*/
return NULL;
}
/*
* Search the free list to insert this block at appropriate loc
* The list is kept sorted on addresses
*/
prev = NULL;
p = freelist;
while ( p != NULL && p < memblock ){
prev = p;
p = p->s.u.next;
}
memblock->s.u.next = p;/*Connect the block to list*/
/*
* The freelist is empty and the memory block is added as the
* first node in the list.
*/
if( prev == NULL )
freelist = memblock;
/*
* The memory block is added as the last node in the free list
*/
else if ( p == NULL ){
memblock->s.u.next = NULL;
prev->s.u.next = memblock;
}
/*
* The memory block is added somewhere in the middle of the
* free list
*/
else
prev->s.u.next = memblock;
/*
* Now p points to a memory block which is of appropriat size
* This block is then either chopped or passed as it is to the
* user
*/
p = memblock;
}
/*
* Calculate size requirements now
*/
if ( space_required > p->s.size ){
/*add_tag(filename,lineno,NULL,NULL,0);*/
return NULL;
}
space_left = p->s.size - space_required;
if ( space_left >= sizeof(union header) + sizeof(int) ){
/*
* Split the block, keep p in free list and return upper end
* of block.This way the pointers dont need to be saved again.
* Simpler
*/
memblock = (union header *)( (char*)p + space_left );
memblock->s.size = space_required;
memblock->s.u.sign = SIGN;/*Unlink Block*/
p->s.size = space_left;
add_tag(filename, lineno, memblock, memblock + 1, request );
return (void*)( memblock + 1 );
}
/*
* No split, unlink the block and return it to user for use
*/
if ( prev == NULL )
freelist = p->s.u.next;
else
prev->s.u.next = p->s.u.next;
p->s.u.sign = SIGN;
add_tag(filename, lineno, p, p + 1, request );
return (void*)( p + 1 );
}
void my_free(char* filename_f,
unsigned int lineno_f,
void* ptr2free){
union header* memblock = NULL;
union header* prev = NULL;
union header* p = NULL;
unsigned int tag_no = 0;
/*
* Freeing a NULL pointer is legal , free() should not do
* anything. Simply return
*/
if( ptr2free == NULL ){
/*fprintf(stderr,"Line %u in %s is trying to free a NULL pointer\n\n",\
lineno_f,filename_f);*/
return ;
}
memblock = (union header*)ptr2free - 1 ;
/*
* My Signature not present and hence the pointer was not
* produced by my_malloc()
*/
if ( memblock->s.u.sign != SIGN ){
/*fprintf(stderr,"Line %u in %s is trying to free a wild pointer\n\n",\
lineno_f,filename_f);*/
return ;
}
/* Find the tag number in the tag table*/
for( tag_no = 0 ; tag_no < TAG_MAX; tag_no++ ){
if( tag_table[tag_no].returned_address == ptr2free )
break;
}
/*
* Search the free list to find an appropriate location to
* insert the memory block
*/
prev = NULL ;
p = freelist;
while( p != NULL && p < (union header*)ptr2free ){
prev = p ;
p = p->s.u.next;
} /*At this point of time , prev < memblock < p */
/*
* If prev == NULL , we must have either of the following two
* cases:
* 1. The Freelist is empty and the node has to be inserted as
* the first node in the free list.
* 2.There is a single node in freelist and the address of the
* memblock is less than the address of the first node , hence
* again this block is inserted as the first node in the list
*/
if( prev == NULL ){
memblock->s.u.next = p;
freelist = prev = memblock;
delete_tag(tag_no);
}
/*
* The memory block starts exactly where the previous block
* ends hence the two blocks are "combined". The size of the
* previous block is simply allowed to grow. There is nothing
* to link here
*/
if( (union header*)(prev + prev->s.size) == memblock ){
prev->s.size += memblock->s.size;
delete_tag(tag_no);
}
/*
* The memory block has to be inserted between the two adjacent
* blocks. Keep track of the 'new prev' as well.
*/
else {
memblock->s.u.next = p;
prev->s.u.next = memblock;
prev = memblock;
delete_tag(tag_no);
}
/*
* Check if the next block is adjacent to the newly added block
*/
if ( p != NULL && ((union header*)(memblock + memblock->s.size) == p) ){
memblock->s.size += p->s.size ;
memblock->s.u.next = p->s.u.next ;
delete_tag(tag_no);
}
/*
* All the my_malloc() calls have been successfully freed,now
* release all memory to the OS before quitting
*/
if( !is_table_initialised() )
freelist_print();
//freelist_destroy2();
return;
}