Jump to content

  • Log In with Google      Sign In   
  • Create Account


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


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 Lil_Lloyd   Members   -  Reputation: 287

Like
0Likes
Like

Posted 18 February 2013 - 08:21 AM

...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, 18 February 2013 - 08:26 AM.


Sponsor:

#2 King Mir   Members   -  Reputation: 1910

Like
1Likes
Like

Posted 18 February 2013 - 09:48 AM

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);


#3 Lil_Lloyd   Members   -  Reputation: 287

Like
0Likes
Like

Posted 18 February 2013 - 10:06 AM

Thank you! smile.png

#4 Lil_Lloyd   Members   -  Reputation: 287

Like
0Likes
Like

Posted 18 February 2013 - 08:30 PM

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?






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS