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.

C/C++ Code

/*
    Copyright 2014 Leonard Kevin McGuire Jr (www.kmcg3413.net) (kmcg3413@gmail.com)

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU Lesser General Public License as published by
    the Free Software Foundation; either version 2 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 Lesser General Public License for more details.

    You should have received a copy of the GNU Lesser General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    This code is so simple that there is NO reason to copyright it, but I know
    some people out there who have yet to truly understand what they are doing
    might be fearful of using it with out some kind of copyright.
*/
typedef unsigned int uint32;
typedef unsigned char uint8;
typedef unsigned int uintptr;

#define KHEAPFLAG_USED			0x80000000

typedef struct _KHEAPHDR {
	uint32				flagsize;
} KHEAPHDR;

typedef struct _KHEAPBLOCK {
	uint32				size;
	uint32				used;
	struct _KHEAPBLOCK	*next;
} KHEAPBLOCK;

typedef struct _KHEAP {
	KHEAPBLOCK			*fblock;
} KHEAP;

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) - sizeof(KHEAPHDR);
	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;
}