[Example] Heap Manager for brokenthorn

[Fadekraft]

Hey everyone, today I finally was tired of seeing people needing help with a heap manager so i decided to share with you all a _SIMPLE_ heap manager i wrote a long time ago. Code is commented and you might need to replace the calls to mappage and allocblock to your own functions, but it will work with brokenthorns. The heap can expand but not contract. The code is commented most of it anyway. You can use the code as you want or for inspiration, but please keep the copyright if you decide to copy paste it.

Tell me if there is code missing! The defines can be changed to your own need if you need to relocate the heap
Also you might have to change the includes from heap.c and so on, but nothing hard.

Here is the heap.h:

Code: Select all

/***************************
	Heap Management
 ***************************/
#define KMALLOC_ADDR_START	0xD0000000
#define KMALLOC_ADDR_END	0xE0000000

#define KERNEL_HEAP_STRUCT	0xD0000000
#define KERNEL_HEAP_START	0xD0200000
#define KERNEL_HEAP_END		0xE0000000
#define KERNEL_HEAP_INC		0x100000
#define KERNEL_HEAP_SINC	0x40000
#define KERNEL_HEAP_SIZE	(KERNEL_HEAP_END - KERNEL_HEAP_START)

#define USER_HEAP_STRUCT	0xB0000000
#define USER_HEAP_START		0xB0200000
#define USER_HEAP_END		0xC0000000
#define USER_HEAP_INC		0x100000
#define USER_HEAP_SINC		0x20000
#define USER_HEAP_SIZE		(USER_HEAP_END - USER_HEAP_START)

//This is really big, 12 bytes.
typedef struct HmmHeader
{
	uint32_t addr;
	HmmHeader *next;
	uint32_t allocated : 1;
	uint32_t length : 31;

}hmmheader_t;

#define NODE_4KB_FLAG	0x1
#define NodeIs4KB(x)	((((x)->start_addr) & 0x1) == 0x1)
#define AddrIsAligned(x) ((x & 0xFFF) == 0)

//16 bytes :x
typedef struct HmmNode
{
	uint32_t	start_addr;
	uint32_t	end_addr;
	
	HmmNode *next;
	HmmHeader *head;
}hmmnode_t;

//4 bytes
typedef struct HmmArea 
{
	HmmNode *head;
}hmmarea_t;

//Init
extern void Initialize_Heap();
extern uint32_t HmmGetCount();

//kMalloc Align and phys return
extern void *kmalloc_ap(uint32_t l, uint32_t *p);

//kMalloc return phys
extern void *kmalloc_p(uint32_t l, uint32_t *p);

//kMalloc align
extern void *kmalloc_a(uint32_t l);

//kMalloc
extern void *kmalloc(uint32_t l);

//Internal kmalloc
extern void *_kmalloc(uint32_t sz, uint32_t aligned);

//kFree
extern void kfree(void *p);

//krealloc / reallocate
extern void *kcalloc(size_t nmemb, size_t size);
extern void *krealloc(void *ptr, size_t size);

extern HmmArea* kHeap;

And here is the heap.c

Code: Select all

/* MollenOS Heap Manager
	Basic Heap Manager
	No contraction for now, for simplicity.

	MollenOS
	Copyright 2012

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation?, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <Kernel\Memory.h>
#include <Kernel\kPrintf.h>
#include <Kernel\kPanic.h>
#include <Kernel\asmdefs.h>
#include <string.h>
#include <assert.h>

//Prototypes
void HmmExpand4Kb(uint32_t sz);
void HmmExpand1Kb(uint32_t sz);

HmmArea *kHeap = NULL;
uint32_t heap_caddr = KERNEL_HEAP_START;
uint32_t heap_calloc = KERNEL_HEAP_STRUCT;
uint32_t heap_cc_max = KERNEL_HEAP_STRUCT;

void *salloc(size_t sz)
{
	//Make sure we allocate pages enough ;b
	if((heap_calloc + sz) >= heap_cc_max)
	{
		VmmMapPage(PmmAllocBlock(), heap_cc_max);
		heap_cc_max += 0x1000;
	}

	uint32_t *ret = (uint32_t*)heap_calloc;
	memset((void*)heap_calloc, 0, sz);
	heap_calloc += sz;
	
	return ret;
}

void Initialize_Heap()
{
	//use our specially designed struct-alloc hihi
	kHeap = (hmmarea_t*)salloc(sizeof(hmmarea_t));

	//We start out by inserting 128 byte blocks
	HmmNode *node = (hmmnode_t*)salloc(sizeof(hmmnode_t));
	node->head = 0;
	node->next = 0;
	node->start_addr = heap_caddr;
	node->end_addr = heap_caddr + KERNEL_HEAP_SINC;
	
	//Insert pages into heap list!
	for(uint32_t i = 0; i < (KERNEL_HEAP_SINC); i += 0x80)
	{
		//Create a new hole, of size 0x80 (128 bytes)
		hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
		hole->addr = (heap_caddr + i);
		hole->allocated = 0;
		hole->length = 0x80;
		hole->next = NULL;
		
		//Insert it
		if(!node->head)
			node->head = hole;
		else
		{
			hmmheader_t *cur_header = node->head, *prev_header = NULL;
			while (cur_header)
			{
				prev_header = cur_header;
				cur_header = cur_header->next;
			}
			prev_header->next = hole;
		}
	}

	//Set start
	kHeap->head = node;

	//Increment
	heap_caddr += KERNEL_HEAP_SINC;
	
	//Make a 4KB node aswell
	HmmNode *node4kb = (hmmnode_t*)salloc(sizeof(hmmnode_t));
	node4kb->head = 0;
	node4kb->next = 0;
	node4kb->start_addr = heap_caddr | NODE_4KB_FLAG;
	node4kb->end_addr = heap_caddr + KERNEL_HEAP_INC;

	//Insert only 4kb pages
	for(uint32_t i = 0; i < (KERNEL_HEAP_INC); i += 0x1000)
	{
		//Create a new hole, of size 0x1000 (4kb)
		hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
		hole->addr = (heap_caddr + i);
		hole->allocated = 0;
		hole->length = 0x1000;		//This can change
		hole->next = 0;
		
		//Insert it
		if(!node4kb->head)
			node4kb->head = hole;
		else
		{
			hmmheader_t *cur_header = node4kb->head, *prev_header = NULL;
			while (cur_header)
			{
				prev_header = cur_header;
				cur_header = cur_header->next;
			}
			prev_header->next = hole;
		}
	}
	//Set start
	kHeap->head->next = node4kb;

	//Increment
	heap_caddr += KERNEL_HEAP_INC;
}

void HmmExpand1Kb(uint32_t sz)
{
	//Expand time!
	//Alloc
	HmmNode *node = (hmmnode_t*)salloc(sizeof(hmmnode_t));
	node->head = 0;
	node->next = 0;
	node->start_addr = heap_caddr;
	node->end_addr = heap_caddr + sz;

	//Insert new headers
	for(uint32_t i = 0; i < (sz); i += 0x80)
	{
		hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
		hole->addr = (heap_caddr + i);
		hole->allocated = 0;
		hole->length = 0x80;
		hole->next = 0;
		
		if(!node->head)
			node->head = hole;
		else
		{
			hmmheader_t *cur_header = node->head, *prev_header = NULL;
			while (cur_header)
			{
				prev_header = cur_header;
				cur_header = cur_header->next;
			}
			prev_header->next = hole;
		}
	}

	//Find a place in the heap list
	hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
	while (cur_node)
	{
		prev_node = cur_node;
		cur_node = cur_node->next;
	}

	//Set it in list
	prev_node->next = node;

	//Increment
	heap_caddr += sz;
}

void HmmExpand4Kb(uint32_t sz)
{
	//Expand time!
	//Alloc
	HmmNode *node = (hmmnode_t*)salloc(sizeof(hmmnode_t));
	node->head = 0;
	node->next = 0;
	node->start_addr = heap_caddr | NODE_4KB_FLAG;	//Tag it 4kb node
	node->end_addr = heap_caddr + sz;

	//Insert new headers
	for(uint32_t i = 0; i < (sz); i += 0x1000)
	{
		hmmheader_t *hole = (hmmheader_t*)salloc(sizeof(hmmheader_t));
		hole->addr = (heap_caddr + i);
		hole->allocated = 0;
		hole->length = 0x1000;
		hole->next = 0;
		
		if(!node->head)
			node->head = hole;
		else
		{
			hmmheader_t *cur_header = node->head, *prev_header = NULL;
			while (cur_header)
			{
				prev_header = cur_header;
				cur_header = cur_header->next;
			}
			prev_header->next = hole;
		}
	}

	//Find a place in the heap list
	hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
	while (cur_node)
	{
		prev_node = cur_node;
		cur_node = cur_node->next;
	}

	//Set it in list
	prev_node->next = node;

	//Increment
	heap_caddr += sz;
}

uint32_t HmmGetCount()
{
	//Primarily debugging purpose
	//Counts entries.
	uint32_t count = 0;
	hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
	while (cur_node)
	{
		hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
		while (cur_header)
		{
			count++;
			prev_header = cur_header;
			cur_header = cur_header->next;
		}
		prev_node = cur_node;
		cur_node = cur_node->next;
	}

	return count;
}

uint32_t _alloc(uint32_t sz, uint32_t aligned)
{
	//For expansion purposes
	uint32_t found = 0;
	//Are we looking for a page aligned space?
	hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
	while (cur_node)
	{
		if(NodeIs4KB(cur_node) && aligned)
		{
			uint32_t blocks_needed = sz / 0x1000;
			if((sz & 0xFFF) != 0x0)
				blocks_needed++;

			hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
			while (cur_header)
			{
				if(!cur_header->allocated)
				{
					//We found an unallocted 4kb header
					//If blocks needed is above one, we need to search for an hole
					if(blocks_needed > 1)
					{
						hmmheader_t *chead = cur_header;
						uint32_t blocks = blocks_needed;	//2, 1
						while(blocks && chead)
						{
							if(chead->allocated)
								break;

							chead = chead->next;
							blocks--;
						}

						if(blocks)	//ran out of headers and still blocks left to alloc
						{
							if(cur_header->next != NULL)
								cur_header = cur_header->next;
							else
								break;
							continue;
						}
					}

					//If we reach this point, one of two things happened.
					//Either we only need to alloc 1 block, or we need to alloc some more.

					if(blocks_needed > 1)
					{
						hmmheader_t *chead = cur_header;
						while(blocks_needed)
						{
							//Map it in if it isn't
							if(!VmmGetMapping(chead->addr, 0))
								VmmMapPage(PmmAllocBlock(), chead->addr);

							chead->allocated = 1;

							chead = chead->next;
							blocks_needed--;
						}
						cur_header->length = sz;
						return cur_header->addr;
					}

					//1 block needed
					if(!VmmGetMapping(cur_header->addr, 0))
						VmmMapPage(PmmAllocBlock(), cur_header->addr);
					
					cur_header->allocated = 1;
					return cur_header->addr;
				}

				prev_header = cur_header;
				
				if(cur_header->next != NULL)
					cur_header = cur_header->next;
				else
					break;
			}
		}
		else if(!NodeIs4KB(cur_node) && !aligned)
		{
			uint32_t blocks_needed = sz / 0x80;
			if((sz % 0x80) > 0x0)
				blocks_needed++;

			hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
			while (cur_header)
			{
				if(!cur_header->allocated)
				{
					//We found an unallocted 1kb header
					//If blocks needed is above one, we need to search for an hole
					if(blocks_needed > 1)
					{
						hmmheader_t *chead = cur_header;
						uint32_t blocks = blocks_needed;
						while(blocks && chead)
						{
							if(chead->allocated)
								break;

							chead = chead->next;
							blocks--;
						}

						if(blocks)	//ran out of headers and still blocks left to alloc
						{
							if(cur_header->next != NULL)
								cur_header = cur_header->next;
							else
								break;
							continue;
						}
					}

					//If we reach this point, one of two things happened.
					//Either we only need to alloc 1 block, or we need to alloc some more.

					if(blocks_needed > 1)
					{
						hmmheader_t *chead = cur_header;
						while(blocks_needed)
						{
							//Map it in if it isn't
							if(!VmmGetMapping(chead->addr, 0))
								VmmMapPage(PmmAllocBlock(), chead->addr);

							chead->allocated = 1;

							chead = chead->next;
							blocks_needed--;
						}
						cur_header->length = sz;
						return cur_header->addr;
					}

					//We found an unallocted 128byte header
					//Map it in if not already.
					if(!VmmGetMapping((cur_header->addr & PAGE_MASK), 0))
						VmmMapPage(PmmAllocBlock(), (cur_header->addr & PAGE_MASK));
					
					cur_header->allocated = 1;
					return cur_header->addr;
				}

				prev_header = cur_header;
				
				if(cur_header->next != NULL)
					cur_header = cur_header->next;
				else
					break;
			}

		}

		prev_node = cur_node;
		cur_node = cur_node->next;
	}

	//If we get here we need to expand.
	if(aligned && !found)
		HmmExpand4Kb(KERNEL_HEAP_INC);
	else
		HmmExpand1Kb(KERNEL_HEAP_SINC);	//128 byte

	return _alloc(sz, aligned);
}

uint32_t _free(uint32_t addr)
{
	uint32_t freed = 0;
	hmmnode_t *cur_node = kHeap->head, *prev_node = NULL;
	while (cur_node)
	{
		//Initial pointers
		hmmheader_t *cur_header = cur_node->head, *prev_header = NULL;
		//Search headers
		while (cur_header)
		{
			//Is this header our header?
			if(cur_header->addr == addr)
			{
				if(NodeIs4KB(cur_node) && (cur_header->length > 0x1000))
				{
					//Find amount of blocks to free
					uint32_t blocks_needed = cur_header->length / 0x1000;
					if((cur_header->length % 0x1000) > 0x0)
						blocks_needed++;

					//search headers
					hmmheader_t *chead = cur_header;
					while(blocks_needed)
					{
						//Unmap
						if(VmmGetMapping(chead->addr, 0))
							VmmUnmapPage(chead->addr);

						chead->allocated = 0;	//set free
						chead->length = 0x1000; //reset length just in case

						chead = chead->next;
						blocks_needed--;

					}
					return 1;
				}
				else if(cur_header->length > 0x80)
				{
					uint32_t blocks_needed = cur_header->length / 0x80;
					if((cur_header->length % 0x80) > 0x0)
						blocks_needed++;

					//search headers
					hmmheader_t *chead = cur_header;
					while(blocks_needed)
					{
						//Unmap, we need a better algorithm here....
						//if(VmmGetMapping(chead->addr, 0))
						//	VmmUnmapPage(chead->addr);

						chead->allocated = 0;	//set free
						chead->length = 0x80; //reset length just in case

						chead = chead->next;
						blocks_needed--;
					}

					return 1;
				}
				//If 4kb note, it was page aligned and we can unallocate
				if(NodeIs4KB(cur_node))
				{
					//found it, lets unmap it and unallocate it
					if(VmmGetMapping(addr, 0))
						VmmUnmapPage(addr);
					
				}
				cur_header->allocated = 0;
				freed = 1;
				return freed; 
			}
			prev_header = cur_header;
			cur_header = cur_header->next;
		}
		prev_node = cur_node;
		cur_node = cur_node->next;
	}

	return freed;
}

/*
 * KMALLOC
 */

void *kmalloc_ap(uint32_t l, uint32_t *p)
{
	void *ret = _kmalloc(l, 1);
	VmmGetMapping((uint32_t)ret, p);
	*p += (uint32_t)ret % 0x1000;
	return ret;
}

void *kmalloc_p(uint32_t l, uint32_t *p)
{
	void *ret = _kmalloc(l, 0);
	VmmGetMapping((uint32_t)ret, p);
	*p += (uint32_t)ret % 0x1000;
	return ret;
}

void *kmalloc_a(uint32_t l)
{
	return _kmalloc(l, 1);
}

void *kmalloc(uint32_t l)
{
	return _kmalloc(l, 0);
}

//Implementation of _kmalloc.
void *_kmalloc(uint32_t sz, uint32_t aligned)
{
	//Sanity checks
	if(heap_caddr >= KERNEL_HEAP_END)
		kPanic("kmalloc: Out of Memory!!!\n");
	if(heap_calloc >= KERNEL_HEAP_START)
		kPanic("kmalloc: Out of salloc-Memory!!!\n");

	if(sz > 0x1000)
		aligned = 1;

	//Allocation time!
	void* addr = (uint32_t*)_alloc(sz, aligned);

	//Null it
	if(aligned && sz <= 0x1000)
		memset(addr, 0, 0x1000);
	else
		memset(addr, 0, sz);

	return addr;
}

/*
 * KFREE
 */

//Basically just a call to _free
void kfree(void *p)
{
	if(_free((uint32_t)p))
		return;
	else
		kprintf("kfree: Invalid addr to free.");
}

/*
 * KCALLOC
 */

void *kcalloc(size_t nmemb, size_t size)
{
    return kmalloc(nmemb * size);
}

/*
 * KREALLOC
 */


void *krealloc(void *ptr, size_t size)
{
	uint32_t *new_ptr;
    if (ptr == NULL) {
        return kmalloc(size);
    }

    if (ptr != NULL && size == 0) {
        kfree(ptr);
        return NULL;
    }

    /* Simple implementation: allocate new space and copy the contents
       over.  Exercise: Improve this by searching through the free
       list and seeing whether an actual enlargement is possible. */
    new_ptr = (uint32_t*)kmalloc(size);
    
	if (new_ptr != NULL) {
        for (uint32_t i = 0; i < size; i++) {
            new_ptr[i] = ((uint32_t*)ptr)[i];
        }
        kfree(ptr);
    }
    return new_ptr;
}

Tell me if you have any problems using it!

[Fadekraft]

Oh, and i know this is not a tutorial, i just didn't know what to put.

[pathos]

Thank you, I'll give it a try sometime. My heap manager is a mess....

[Fadekraft]

No problem at all, tell me if you need any help or if im using something there isn't in the brokenthorn virtual memory manager.
It worked perfectly for me so if implemented correctly it will work perfectly for all of you ^^

[Benjamin]

Then call it "Simple Heap Example."

[Fadekraft]

Hehe, changed it!

Anyway, hope it helps some people

[Andyhhp]

If you are looking for some constructive criticism:

Your #defines at the top should have the 'U' suffix to imply unsigned. It changes the behaviour of the arithmatic in certain places.

Change HmmHeader to be more like this:

Code: Select all

typedef struct HmmHeader
{
   uint32_t addr;
   HmmHeader *next;
   uint32_t allocated : 1;
   uint32_t length : 31;
}hmmheader_t;

Having bitfields in the middle of structs rather than at the end is a minefield.

Code: Select all

#define AddrIsAligned(x) ((addr & 0x00000FFF) == 0)

You mean ((x) & 0xFFF) ? Dont forget to wrap all macro parameters in brackets.

You dont need any of the externs for the function declarations, and the internal kmalloc should appear at the top of heap.c rather than in the header (although this is simply good coding practices). Any functions taking no parameters should be declared "ReturnType FunctionName(void)". Leaving out the void means that the function will accept any number of arguments without error.

Code: Select all

HmmArea *kHeap = 0;

This should be NULL not 0. NULL and 0 are very different things.

Code: Select all

hmmheader_t *cur_header = node4kb->head, *prev_header = 0;

This code doesn't do what you presumably intend. It will unconditionally set cur_header to be 0. Futhermore, 0 should be NULL, and prev_header appears to be undeclared. I presume you mean ; instead of , ? This syntax appears in several locations through heap.c

Other than that, its looks like a good resource.

~Andrew (who is soon to rewrite the Xen 64bit heap allocator to account for NUMA layouts)

[Fadekraft]

Thanks a lot for taking the time to look through the code and giving comments, most you say i totally agree on, and that mistake with the macros is stupid haha.

I have one counter-comment to the argument about this piece of code:

Code: Select all

hmmheader_t *cur_header = node4kb->head, *prev_header = 0;

This does exactly what I want it to, if it didn't work the heap itself would not work (And this heap compiles and work in the posted state - with visual studio 2010).
In visual studio 2010 that code means exactly the same as:

Code: Select all

hmmheader_t *cur_header = node4kb->head;
hmmheader_t *prev_header = 0;

And yes, indeed it should be NULL and not 0

Thanks again for your comments, much appreciated, I'll just update the code in the post!

[Andyhhp]

D'oh - I have been doing C89 for so long that without syntax highlighting, i completely missed the fact that that was a declaration rather than just another line of code.

~Andrew