User:Pancakes/SimpleHeapImplementation

Simple Heap Implementation

This is a fairly simple heap implementation. It has not been well tested so it could have a bug somewhere, but so far it seems to work well and I have not run into any problems. It basically works by you assigning blocks of memory to the heap. Each block of memory is separate. So the maximum allocation you can make is the size of the largest block minus the header. Also, over time the heap can become kind of fragmented from calls to alloc and free which eventually create spots between allocations and this can reduce your maximum allocation size. A good fallback would be for you to add another block to the heap if an allocation can not be made in the event the heap becomes highly fragmented. I do not add another block here because I wanted to keep this implementation with out any dependencies. The best way would likely be to wrap these calls in another layer than can handle the failed call to the allocation function and try to add another block (and also check adding another block will work).

Also, I forgot to mention there is a maximum block size set at 2,147,483,647 bytes (31-bit). This is because each header/chunk inside the block only has 31 bits to specify it's size (free or used). The highest bit (32nd bit) is used to flag if the header/chunk is used or free. However, the implementation is so short and simple that if you needed to support bigger blocks and allocations you could simply expand the header to handle any. I just settled for 2GB because I think that is good for most hobby projects, while still keeping the overhead low on memory consumption and still being quite fast.

A good idea is to build a wrapper around these calls (not only for your kernel to call k_heapAddBlock) to provide a debugging ability. What you do is catch all alloc calls and add some extra bytes onto the size. Then place a special signature at the beginning and end to catch under-flows and overflows for writing. It is not easy to catch over reading or under reading, but at least you can catch when your heap has become corrupted!

k_heapInit

This initializes the heap structure. Nothing too complex.

k_heapAddBlock

You use this to add a block to the heap. Like, h_heapAddBlock(&heap, 0x1000, 0x2000) would add 2KB starting at 1KB.

k_heapAlloc

This will allocate a chunk which can be used.

k_heapFree

This will free a chunk.

Example Usage

    KHEAP       kheap;
    char        *ptr;

    k_heapInit(&kheap);                          /* initialize the heap */
    k_heapAddBlock(&kheap, 0x100000, 0x100000);  /* add block to heap (starting 1MB mark and length of 1MB) */
    ptr = (char*)k_heapAlloc(&kheap, 256);               /* allocate 256 bytes (malloc) */
    k_heapFree(&kheap, ptr);                             /* free the pointer (free) */

Also, you could wrap the functions so that kheap does not need to be passed thus making the calls much more simple and easy to write. I thought it was better to give the programmer the ability to have multiple heaps than to restrict them. So if you only want to use one heap then create an abstraction layer that hands in the kheap argument.

Not handing the kheap argument to k_heapFree will cause it to perform a fast deallocation. The only problem is this leaves the heap not only fragmented but also leaves contiguous free space fragmented which is bad. I have yet to write another function would would go in and consolidate space.

C/C++ Code

#include "kheap.h"

void k_heapInit(KHEAP *heap) {
		heap->fblock = 0;
}

int k_heapAddBlock(KHEAP *heap, uint32 addr, uint32 size) {
	KHEAPBLOCK			*hb;
	KHEAPHDR			*hdr;
	
	hb = (KHEAPBLOCK*)addr;
	hb->size = size - sizeof(KHEAPBLOCK);
	hb->used = 0;
	hb->next = heap->fblock;
	heap->fblock = hb;
	
	hdr = (KHEAPHDR*)&hb[1];
	hdr->flagsize = hb->size - sizeof(KHEAPHDR);
	
	return 1;
}

/*
	Look behind and forward to see if we can merge back into some chunks.
*/
void k_heapFree(KHEAP *heap, void *ptr) {
	KHEAPHDR			*hdr, *phdr, *nhdr;
	KHEAPBLOCK			*hb;
	uint32				sz;
	uint8				fg;
	
	hdr = (KHEAPHDR*)ptr;
	hdr[-1].flagsize &= ~0x80000000;
		
	phdr = 0;
	/* find the block we are located in */
	for (hb = heap->fblock; hb; hb = hb->next) {
		if (((uintptr)ptr > (uintptr)hb) && ((uintptr)ptr < (uintptr)hb + hb->size)) {
			/* we have found the heap block */
			/* try to identify the header before and after */
			hdr = (KHEAPHDR*)&hb[1];
			while ((uintptr)hdr < (uintptr)hb + sizeof(KHEAPBLOCK) + hb->size) {
				fg = hdr->flagsize >> 31;
				sz = hdr->flagsize & 0x7fffffff;
				nhdr = (KHEAPHDR*)((uintptr)&hdr[1] + sz);
				if ((uintptr)&hdr[1] == (uintptr)ptr) {
					/* we have found the header for our 'ptr' */
					if ((uintptr)nhdr < (uintptr)hb + sizeof(KHEAPBLOCK) + hb->size) {
						/* okay we have a header in font of us, can we combine with it */
						if (!(nhdr->flagsize & 0x80000000)) {
							/* combine with it */
							hdr->flagsize += sizeof(KHEAPHDR) + nhdr->flagsize;
							hb->used -= sizeof(KHEAPHDR);
						}
						/* can we combine with previous header? */
						if (phdr) {
							if (!(phdr->flagsize & 0x80000000)) {
								phdr->flagsize += sizeof(KHEAPHDR) + hdr->flagsize;
								hb->used -= sizeof(KHEAPHDR);
							}
						}
					}
					hd->used -= hdr->flagsize;
					return;
				}
				phdr = hdr;
				hdr = nhdr;
			}			
		}
	}
	
	/* uhoh.. this should not happen.. */
	return;
}

/*
	This will allocate a chunk of memory by the specified size, and if
	no memory chunk can be found it will return zero.
*/
void* k_heapAlloc(KHEAP *heap, uint32 size) {
	KHEAPBLOCK			*hb;
	KHEAPHDR			*hdr, *_hdr;
	uint32				sz;
	uint8				fg;
	
	/* first find heap block with enough space */
	for (hb = heap->fblock; hb; hb = hb->next) {
		if ((hb->size - hb->used) >= (size + sizeof(KHEAPHDR))) {
			/* find actual free block */
			hdr = (KHEAPHDR*)&hb[1];
			while ((uintptr)hdr < (uintptr)hb + sizeof(KHEAPBLOCK) + hb->size) {
				fg = hdr->flagsize >> 31;
				sz = hdr->flagsize & 0x7fffffff;
				if (!fg) {
					if (sz >= size) {
						// else take whole chunk
						if (sz > size + sizeof(KHEAPHDR) + 16) {
							/* has enough left over (break into two) */
							_hdr = (KHEAPHDR*)((uint32)&hdr[1] + size);
							/* take out data size and header size */
							_hdr->flagsize = sz - size - sizeof(KHEAPHDR);
							/* set to used and set new size */
							hdr->flagsize = 0x80000000 | size;
							hb->used += sizeof(KHEAPHDR);
						} else {
							/* simply set to used */
							hdr->flagsize |= 0x80000000;
						}
						hb->used += size;
						return &hdr[1];
					}
				}
				hdr = (KHEAPHDR*)((uintptr)&hdr[1] + sz);
			}
		}
	}
	return 0;
}