OSDev.org

The Place to Start for Operating System Developers
https://f.osdev.org/

Need optimized buddy system memory allocation alogorithm.

https://f.osdev.org/viewtopic.php?t=25632

Page 1 of 1

Need optimized buddy system memory allocation alogorithm.

Posted: Fri Aug 10, 2012 7:53 am
by dnyaneshgate
Hi all,
I am new at this forum and posting a new topic very first time on this forum.
For a last few days I am trying to implement buddy memory allocator.
I have posted my code below. It works fine on ubuntu-12.04 using g++ compiler,
But it fails on windows 7 platform using dev-c++ compiler.
I am facing problem while merging buddies when run it on window platform, On linux it works smooth.

I would also like to know some suggestion from you guys to optimize it.
I am trying to implement it without using any built in library, so that I can use it in my kernel.

Code: Select all

#include <iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#ifdef WIN32
#	include <conio.h>
#endif

#define M 9       //max memory available

#define TITLE(x) \
	putc('\n',stderr);for(int i=0;i<80;i++) putc('=',stderr);\
	printf("\n%s\n",x);\
	for(int i=0;i<80;i++) putc('=',stderr);putc('\n',stderr);

#define STATUS(block) (block->status?"Used":"Free")

int pow(int x , int y);

enum Status { Free , Reserved };

typedef struct Block
{
	Status status;
	int Kval;
	size_t size;
	Block *prev;
	Block *next;
} __attribute__((packed)) *FreeList[M+1];

#define HEADER_SIZE sizeof(Block)

class BuddyPool
{
	private:
		void devide_buddy(void* P);
		void merge_buddy(void* P1, void* P2);
		int  getOrder(size_t size);
		Block* findBuddy(Block* B, int k);
		void insert_into_freelist(Block* B, int k);
		void delete_from_freelist(Block* B, int k);
		
	protected:
		void* MemoryPool;
		FreeList freelist;
		
	public:
		int total_memory;
		int free_memory;
		int used_memory;
		BuddyPool();
		~BuddyPool();
		void* alloc(size_t size);
		void  dealloc(void* P);
		void  dump();
};

BuddyPool::BuddyPool()
{
	int i;
	free_memory = total_memory = pow(2,M);
	used_memory = 0;
	MemoryPool = malloc(total_memory);
	memset(MemoryPool,'x',total_memory);
	for(i=0;i<M;i++)
	{
		freelist[i] = NULL;
	}
	freelist[i] = (Block*)MemoryPool;
	freelist[i]->status = Free;
	freelist[i]->Kval = i;
	freelist[i]->size = total_memory - HEADER_SIZE;
	freelist[i]->next = freelist[i]->prev = NULL;
}

BuddyPool::~BuddyPool()
{
	free(MemoryPool);
}

Block* BuddyPool::findBuddy(Block* B, int k)
{
	//return (Block*)((unsigned int)B ^ (1<<k));
	size_t sz = pow(2,k);
	unsigned int U = (unsigned int)B / sz;
	if(U%2 == 0)
		return (Block*)((char*)B+sz);
	else
		return (Block*)((char*)B-sz);
}

void BuddyPool::insert_into_freelist(Block* B, int k)
{
	B->next = freelist[k];
	B->prev = NULL;
	
	if(freelist[k] != NULL)
		freelist[k]->prev = B;
	freelist[k] = B;
}

void BuddyPool::delete_from_freelist(Block* B, int k)
{
	if(freelist[k] == B)   /*if head node { head = NULL }*/
	{
		freelist[k] = B->next;
		if(freelist[k] != NULL)
		{
			freelist[k]->prev = NULL;
			freelist[k]->next = NULL;
		}
	}
	else
	{
		Block *prev = NULL;
		Block *next = NULL;
		
		prev = B->prev;
		next = B->next;
		
		if(prev!=NULL)
			prev->next = next;
		if(next!=NULL)
			next->prev = prev;
	}
}

void BuddyPool::dump()
{
	int i;
	TITLE("BUDDY MEMORY DUMP");
	for(i=1;i<=M;i++)
	{
		if(freelist[i] != NULL)
		{
			printf("freelist[%d]:\n",i);
			Block *ptr;
			for(ptr = freelist[i] ; ptr!=NULL ; ptr=ptr->next)
			{
				printf("\t0x%-20xsize=%-20dstatus=%s\n",(unsigned int)ptr,ptr->size+HEADER_SIZE,STATUS(ptr));
			}
		}
		else
			continue;
	}
}

int BuddyPool::getOrder(size_t size)     /*return log2(size)*/
{
	int k = 0;
	while( ( pow(2,k) < (int)size ) && ( k <= M ) ) k++;
	if( k <= M ) return k;
	else return -1;
}

void BuddyPool::devide_buddy(void* P)
{
	printf("splitting buddy 0x%x\n",(unsigned int)P);
	Block* buddy1 = (Block*)P;
	Block* buddy2;
	
	int size = (buddy1->size + HEADER_SIZE) / 2;
	//printf("size=%d\t",size);
	
	int k = buddy1->Kval;
	//printf("k=%d\n",k);
	
	printf("buddy1 = 0x%x",(unsigned int)buddy1);
	buddy1->size = size - HEADER_SIZE;
	buddy1->status = Free;
	buddy1->Kval = k-1;
	buddy1->next = buddy1->prev = NULL;
	
	buddy2 = (Block*)((char*)buddy1 + size);
	printf("\tbuddy2 = 0x%x\n\n",(unsigned int)buddy2);
	buddy2->size = size - HEADER_SIZE;
	buddy2->status = Free;
	buddy2->Kval = k-1;
	
	buddy2->next = freelist[k-1];
	buddy2->prev = NULL;
	
	if(freelist[k-1] != NULL)
		freelist[k-1]->prev = buddy2;
	freelist[k-1] = buddy2;
}

void BuddyPool::merge_buddy(void* P1, void* P2)
{
	
	Block* buddy1 = (Block*)P1;
	Block* buddy2 = (Block*)P2;
	
	int k1 = buddy1->Kval;
	int k2 = buddy2->Kval;
	
	int final_size = 0;
	
	if(k1 != k2)
	{
		printf("buddies are of different order  (k1 != k2)\n");
		return;
	}
	
	int k = k1;
	
	do
	{
		printf("Merging buddy1 = 0x%x\tbuddy2 = 0x%x\n",(unsigned int)buddy1,(unsigned int)buddy2);
		printf("K1 = %d\tK2 = %d\n\n",k,k2);
		final_size = buddy1->size + HEADER_SIZE + buddy2->size + HEADER_SIZE;
		delete_from_freelist(buddy2,k2);
		
		if(buddy1 > buddy2)
			buddy1 = buddy2;
		
		/*update buddy1*/
		buddy1->size = final_size - HEADER_SIZE;
		buddy1->Kval = ++k;
		buddy2 = findBuddy(buddy1,k);
		k2 = buddy2->Kval;
		printf("buddy2 = 0x%x\tK1 = %d\tK2 = %d\n\n",(unsigned int)buddy2,k,k2);
		if(buddy2->status != Free)
			break;
		else
			continue;
	}while(k<=M && k==k2);
	buddy1->status = Free;
	insert_into_freelist(buddy1,k);
}

void* BuddyPool::alloc(size_t size)
{
	if(size <= 0)
	{
		printf("Not a valid size\n");
		return NULL;
	}
	if((int)size > total_memory)
	{
		printf("Not Enough Memory\n");
		return NULL;
	}
	TITLE("BUDDY MEMORY ALLOCATION");
	int final_size = size + HEADER_SIZE;
	printf("Allocating Size = %d\n",final_size);
	int k = getOrder(final_size);
	printf("k = %d\n",k);
	int i;
	for(i=k;i<=M;i++)
		if(freelist[i] != NULL)
			break;
	if(i>M)
	{
		printf("Not Enough Memory\n");
		return NULL;
	}
	
	Block *addr = freelist[i];

	delete_from_freelist(addr,i);

	while(i > k)
	{
		printf("i = %d\t",i);
		devide_buddy(addr);
		--i;
	}
	addr->status = Reserved;
	return (void*)addr;
}

void BuddyPool::dealloc(void* P)
{
	if(P == NULL)
	{
		printf("Invalid Memory Address\n");
		return;
	}
	
	TITLE("BUDDY MEMORY DEALLOCATION");
	
	Block* buddy1 = (Block*)P;
	Block* buddy2;
	
	if(buddy1->status == Free)
	{
		printf("Memory Not Allocated 0x%x\n",(unsigned int)buddy1);
		return;
	}
	
	printf("Deallocating 0x%x       size = %d\n",(unsigned int)buddy1,buddy1->size+HEADER_SIZE);
	
	buddy1->status = Free;
	int k = buddy1->Kval;
	
	buddy2 = findBuddy(buddy1,k);
	
	printf("buddy1 = 0x%x (%s)\tbuddy2 = 0x%x (%s)\n",(unsigned int)buddy1,STATUS(buddy1),(unsigned int)buddy2,STATUS(buddy2));
	
	if(buddy2->status == Free)
		merge_buddy(buddy1,buddy2);
	else
	{
		buddy1->next = freelist[k];
		buddy1->prev = NULL;
		if(freelist[k] != NULL)
			freelist[k]->prev = buddy1;
		freelist[k] = buddy1;
	}
}

int pow(int x , int y)
{
	if(!y) return 1;
	if(!x) return 0;
	int ans = x;
	for(int i = 1 ; i < y ; i++)
		ans *= x;
	return ans;
}

int main(int argc , char **argv)
{
	BuddyPool buddy;
	printf("Total Memory = %d Bytes\n",buddy.total_memory);
	printf("HEADER_SIZE = %d Bytes\n",HEADER_SIZE);
	buddy.dump();
	char *p1 = (char*)buddy.alloc(20);
	buddy.dump();
	char *p2 = (char*)buddy.alloc(20);
	buddy.dump();
	char *p3 = (char*)buddy.alloc(20);
	buddy.dump();
	char *p4 = (char*)buddy.alloc(20);
	buddy.dump();
	char *p5 = (char*)buddy.alloc(20);
	buddy.dump();
	
	buddy.dealloc(p1);	buddy.dump();
	buddy.dealloc(p3);	buddy.dump();
	buddy.dealloc(p5);	buddy.dump();
	buddy.dealloc(p4);	buddy.dump();
	buddy.dealloc(p2);	buddy.dump();

#ifdef WIN32
	getch();
#endif
	return 0;
}

/*    OUTPUT ON WINDOWS 7 USING DEV-C++         */
/*
Total Memory = 512 Bytes
HEADER_SIZE = 20 Bytes

======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[9]:
        0x5b0f38              size=512                 status=Free

======================================================================

BUDDY MEMORY ALLOCATION
======================================================================

Allocating Size = 40
k = 6
i = 9   splitting buddy 0x5b0f38
buddy1 = 0x5b0f38       buddy2 = 0x5b1038

i = 8   splitting buddy 0x5b0f38
buddy1 = 0x5b0f38       buddy2 = 0x5b0fb8

i = 7   splitting buddy 0x5b0f38
buddy1 = 0x5b0f38       buddy2 = 0x5b0f78


======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[6]:
        0x5b0f78              size=64                  status=Free
freelist[7]:
        0x5b0fb8              size=128                 status=Free
freelist[8]:
        0x5b1038              size=256                 status=Free

======================================================================

BUDDY MEMORY ALLOCATION
======================================================================

Allocating Size = 40
k = 6

======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[7]:
        0x5b0fb8              size=128                 status=Free
freelist[8]:
        0x5b1038              size=256                 status=Free

======================================================================

BUDDY MEMORY ALLOCATION
======================================================================

Allocating Size = 40
k = 6
i = 7   splitting buddy 0x5b0fb8
buddy1 = 0x5b0fb8       buddy2 = 0x5b0ff8


======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[6]:
        0x5b0ff8              size=64                  status=Free
freelist[8]:
        0x5b1038              size=256                 status=Free

======================================================================

BUDDY MEMORY ALLOCATION
======================================================================

Allocating Size = 40
k = 6

======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[8]:
        0x5b1038              size=256                 status=Free

======================================================================

BUDDY MEMORY ALLOCATION
======================================================================

Allocating Size = 40
k = 6
i = 8   splitting buddy 0x5b1038
buddy1 = 0x5b1038       buddy2 = 0x5b10b8

i = 7   splitting buddy 0x5b1038
buddy1 = 0x5b1038       buddy2 = 0x5b1078


======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[6]:
        0x5b1078              size=64                  status=Free
freelist[7]:
        0x5b10b8              size=128                 status=Free

======================================================================

BUDDY MEMORY DEALLOCATION
======================================================================

Deallocating 0x5b0f38       size = 64
buddy1 = 0x5b0f38 (Free)        buddy2 = 0x5b0f78 (Used)

======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[6]:
        0x5b0f38              size=64                  status=Free
        0x5b1078              size=64                  status=Free
freelist[7]:
        0x5b10b8              size=128                 status=Free

======================================================================

BUDDY MEMORY DEALLOCATION
======================================================================

Deallocating 0x5b0fb8       size = 64
buddy1 = 0x5b0fb8 (Free)        buddy2 = 0x5b0ff8 (Used)

======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[6]:
        0x5b0fb8              size=64                  status=Free
        0x5b0f38              size=64                  status=Free
        0x5b1078              size=64                  status=Free
freelist[7]:
        0x5b10b8              size=128                 status=Free

======================================================================

BUDDY MEMORY DEALLOCATION
======================================================================

Deallocating 0x5b1038       size = 64
buddy1 = 0x5b1038 (Free)        buddy2 = 0x5b1078 (Free)
Merging buddy1 = 0x5b1038       buddy2 = 0x5b1078
K1 = 6  K2 = 6

buddy2 = 0x5b10b8       K1 = 7  K2 = 7

Merging buddy1 = 0x5b1038       buddy2 = 0x5b10b8
K1 = 7  K2 = 7

buddy2 = 0x5b1138       K1 = 8  K2 = 54759


======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[6]:
        0x5b0fb8              size=64                  status=Free
        0x5b0f38              size=64                  status=Free
freelist[8]:
        0x5b1038              size=256                 status=Free

======================================================================

BUDDY MEMORY DEALLOCATION
======================================================================

Deallocating 0x5b0ff8       size = 64
buddy1 = 0x5b0ff8 (Free)        buddy2 = 0x5b0fb8 (Free)
Merging buddy1 = 0x5b0ff8       buddy2 = 0x5b0fb8
K1 = 6  K2 = 6

buddy2 = 0x5b0f38       K1 = 7  K2 = 6


======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[6]:
        0x5b0f38              size=64                  status=Free
freelist[7]:
        0x5b0fb8              size=128                 status=Free
freelist[8]:
        0x5b1038              size=256                 status=Free

======================================================================

BUDDY MEMORY DEALLOCATION
======================================================================

Deallocating 0x5b0f78       size = 64
buddy1 = 0x5b0f78 (Free)        buddy2 = 0x5b0f38 (Free)
Merging buddy1 = 0x5b0f78       buddy2 = 0x5b0f38
K1 = 6  K2 = 6

buddy2 = 0x5b0fb8       K1 = 7  K2 = 7

Merging buddy1 = 0x5b0f38       buddy2 = 0x5b0fb8
K1 = 7  K2 = 7

buddy2 = 0x5b0e38       K1 = 8  K2 = 0


======================================================================

BUDDY MEMORY DUMP
======================================================================

freelist[8]:
        0x5b0f38              size=256                 status=Free
        0x5b1038              size=256                 status=Free

*/

Re: Need optimized buddy system memory allocation alogorithm

Posted: Fri Aug 10, 2012 8:16 am
by Combuster
"It doesn't work" is not a valid problem description. I don't even see an issue - only lots of code and dumps without attached meaning.

Do your homework, demonstrate what numbers are actually wrong and what they should be.

Re: Need optimized buddy system memory allocation alogorithm

Posted: Fri Aug 10, 2012 9:16 am
by dnyaneshgate
Well the actual problem is as u can see last 5 lines of output.

Code: Select all

freelist[8]:
        0x5b0f38              size=256                 status=Free
        0x5b1038              size=256                 status=Free
It must be like this.

Code: Select all

freelist[9]:
        0x5b0f38              size=512                 status=Free
problem is when I free a memory allocation it should get merged with its buddies, but it is not getting merged.
I am getting this problem when running it on windows.

There is some where bug in function

Code: Select all

findBuddy()
I am unable to find it; because it is running well on linux,
then what is the problem with windows.

Re: Need optimized buddy system memory allocation alogorithm

Posted: Fri Aug 10, 2012 11:12 am
by cb88
Are you using the updated DevC++ or the old release no one is updating?

http://sourceforge.net/projects/orwelldevcpp/ <= this guy has been continuing development.

Note that I have only compiled some trivial FLTK applications with it but It seems quite good from what I could tell. He has also added 64bit support in the compiler as well as fixed many things.

Also... it seems to be that using a debugger on your program would provide invaluable information as to what is acutally happening. GDB is included in DevC++ I think there is also a tool called Insight you can use that is graphical.

Re: Need optimized buddy system memory allocation alogorithm

Posted: Sun Aug 12, 2012 4:25 pm
by Tosi
Since you are doing this in user-mode (which is a good way to test algorithms before moving them into the kernel):

Learn how to use the debugger.
Learn how to use the debugger.
Learn how to use the debugger.

Also don't use Dev-C++ on windows, if you are doing user-mode development use mingw or cygwin if you don't care about sharing the binaries. If you want an IDE you can use Code::Blocks or possibly set Dev-C++ up to use the newer mingw versions.
All times are UTC-06:00
Page 1 of 1

Powered by phpBB® Forum Software © phpBB Limited