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).
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.
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.
*/
#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);
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;
/* if you need ultra fast deallocation and you plan to later
come back and cleanup this heap then this is an option.. */
if (!heap)
return;
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;
}
/* can we combine with previous header? */
if (phdr) {
if (!(phdr->flagsize & 0x80000000)) {
phdr->flagsize += sizeof(KHEAPHDR) + 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;
} else {
/* simply set to used */
hdr->flagsize |= 0x80000000;
}
return &hdr[1];
}
}
hdr = (KHEAPHDR*)((uintptr)&hdr[1] + sz);
}
}
}
k_serdbg_puts("none found\n");
return 0;
}