3 replies to this topic

[Lil_Lloyd]

...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.

[King Mir]

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

[Lil_Lloyd]

Thank you!

[Lil_Lloyd]

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?