Sign in to follow this  

My custom mem allocator isn't working because....

This topic is 1793 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

...my line of code in the free function isn't accessing the value I expect!

I have the free blocks of memory kept in a doubly linked list and used blocks also carry size information but aren't kept in the linked list.
 
const int MAX_BYTES = 16 * 1024 * 1024;
 
static MallocStruct* freeListHeader;
static unsigned char DataBuffer[MAX_BYTES];

struct MallocStruct{
	MallocStruct*  next;
	MallocStruct*  prev;
	unsigned char* buffer;
	size_t size;
};
 

void  InitMalloc(){
    freeListHeader = (MallocStruct*)DataBuffer;
    freeListHeader->next   = NULL;
    freeListHeader->prev   = NULL;
    freeListHeader->size   = MAX_BYTES - sizeof(MallocStruct);
    freeListHeader->buffer = (unsigned char*)(freeListHeader + sizeof(MallocStruct));
}
 
void* MyMalloc(int size){

	MallocStruct** ptr = &freeListHeader;

	//round up size
	if(size % 4 != 0){
		size = (float)size/4 + 1;
		size *= 4;
	}

	while(size + sizeof(MallocStruct) > (*ptr)->size){
		ptr = &(*ptr)->next;

		if(*ptr == NULL) return NULL;
	}
	
	int newSize = (*ptr)->size - (size + sizeof(MallocStruct));
	MallocStruct* next = (*ptr)->next;
	MallocStruct* prev = (*ptr)->prev;

	//now change the pointer in the list, and get a pointer to this current location

	(*ptr)->next   = NULL;
	(*ptr)->prev   = NULL;
	(*ptr)->size   = size;
	(*ptr)->buffer = (unsigned char*)((*ptr) + sizeof(MallocStruct));

	unsigned char* data = (*ptr)->buffer;

	//update the freelist pointer
	unsigned char* ptr3 = (*ptr)->buffer + (*ptr)->size;
	*ptr = (MallocStruct*)ptr3;
	(*ptr)->buffer = (unsigned char*)((*ptr) + sizeof(MallocStruct));
	(*ptr)->size = newSize;
	(*ptr)->next = next;
	(*ptr)->prev = prev;

	if((*ptr)->next != NULL) (*ptr)->next->prev = *ptr;
	if((*ptr)->prev != NULL) (*ptr)->prev->next = *ptr;

	return data;
}


void  MyFree(void* data){
	//create a free node, uncoalesced
	MallocStruct* newFree = (MallocStruct*)((unsigned char*)data - sizeof(MallocStruct));
	int size = newFree->size + sizeof(MallocStruct);

	//now insert it into the linked list
	MallocStruct** ptr = &freeListHeader;

	//case 1 - no prev for freeListHeader and address below
	if((*ptr)->prev == NULL && newFree < *ptr){
		(*ptr)->prev  = newFree;
		newFree->next = *ptr;
		newFree->size = size;
		*ptr = newFree;
		return;
	}

	//case 2 - no next for the freeListHeader and address higher
	if((*ptr)->next == NULL && newFree > *ptr){
		(*ptr)->next = newFree;
		newFree->prev = *ptr;
		newFree->size = size;
		return;
	}

	//case3 other wise needs to be inserted into a list somewhere...
	while(newFree > (*ptr)->next){

		//if next is NULL we need to go to case 4 - inserting at the end
		if((*ptr)->next == NULL) break;

		ptr = &((*ptr)->next);

	}

	//case 4 - end of the list
	if((*ptr)->next == NULL){
		(*ptr)->next = newFree;
		newFree->prev = (*ptr);
		newFree->size = size;
		return;
	}

	//back to case 3 - list insertion
	newFree->next = (*ptr)->next;
	(*ptr)->next->prev = newFree;
	(*ptr)->next = newFree;
	newFree->prev = *ptr;
	newFree->size = size;
}

More specifically the lines
 
MallocStruct* newFree = (MallocStruct*)((unsigned char*)data - sizeof(MallocStruct));
int size = newFree->size + sizeof(MallocStruct);
 
aren't extracting the size value I expect, newFree->size is being read as '0' so the size is being recorded as 16, the size of a MallocStruct only. I don't understand why at all!
 
Someone please explain my hopefully silly and trivial mistake. Edited by Lil_Lloyd

Share this post


Link to post
Share on other sites

Looks like you're not setting the buffer correctly on this line:

(*ptr)->buffer = (unsigned char*)((*ptr) + sizeof(MallocStruct));

It should probably be this:

(*ptr)->buffer = (unsigned char*)((*ptr) +1);

or alternatively this:

(*ptr)->buffer = (unsigned char*)(*ptr) + sizeof(MallocStruct);

Share this post


Link to post
Share on other sites

Eek! I have another issue now, and it shows my ignorance with pointers to pointers. I search through a linked list like so:

//use two pointers to gague where the new ptr should go
	MallocStruct** ptr1 = NULL;
	MallocStruct** ptr2 = &freeListHeader;

	//case3 other wise needs to be inserted into a list somewhere...
	while(newFree > *ptr2){

		ptr1 = ptr2;

		ptr2 = &((*ptr2)->next);

		//if next is NULL we need to go to case 4 - inserting at the end
		if(*ptr2 == NULL) break;

	} 

 
Then, if I need to insert my new block, I insert it like so:

// end of the list
	if(ptr2 == NULL){
		(*ptr1)->next = newFree;
		newFree->prev = (*ptr1);
	}else if(ptr1 == NULL){
		//beginning of the list
	  (*ptr2)->prev = newFree;
	  newFree->next = (*ptr2);
	  (*ptr2) = newFree;
	}else{
	  //middle of the list
	  (*ptr1)->next = newFree;
	  newFree->next = (*ptr2);
	  (*ptr2)->prev = newFree;
	  newFree->prev = (*ptr1);
	} 

The problem is the middle of the list insertion. I'm under the false assumption that (*ptr1)->next = newFree; merely changes the address that (*ptr1)->next points to, however it changes the value of *ptr2 too! How am I supposed to insert a node into a list like this?

Share this post


Link to post
Share on other sites

This topic is 1793 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this