User:Pancakes/BitmapHeapImplementation
Bitmap Heap Implementation
This implementation of a heap uses a bitmap per block instead of a header for each allocation (and empty allocation) per block.
It provides data aligned on the block size specified for the block size per block. So if you use multiple block sizes then you could end up with data aligned on different boundaries. This might be a feature you wish to improve upon if you use this heap.
Also do not be confused with block and block size. You add blocks to the heap which is were the allocations happen (inside each block), but inside each block you have a parameter that is specified that tells what size to chop the block into. For instance you could specify 16 which is a 16 byte blocks inside the block. The 16 is also the alignment, and the bitmap represents each of these 16 byte blocks inside the block.
It has also been slightly optimized using the lfb field of each KHEAPBLOCKBM structure. This basically points to the space after the most recent allocation in hopes that during it allocation it will be closer to any free blocks. In certain situations this technique may not work well but it will provide some decent performance needed during early development. So as your kernel, user applications, or what not mature you may have to look for a better implementation.
Simulation
I wrote a okay page that lets you simulate the heap with a view of memory and play back of memory accesses. It relates directly to this algorithm except it uses only 16-bit fields. You can find it at [1] (original link dead).
Example Usage
It might be easier also to use a #define directive to change the function names to something less descriptive such as kmalloc or kfree. Like, #define kmalloc k_heapBMAlloc. Or, you could just directly change the procedure names.
The 16 passed to the add block function specifies the default block size (very much like a hard disk). So something that was 9 bytes long would actually take up 16 bytes, or something that was 17 bytes would take up 32 bytes.
KHEAPBM kheap;
char *ptr;
k_heapBMInit(&kheap); /* initialize the heap */
k_heapBMAddBlock(&kheap, 0x100000, 0x100000, 16); /* add block to heap
(starting 1MB mark and length of 1MB)
with default block size of 16 bytes
*/
ptr = (char*)k_heapBMAlloc(&kheap, 256); /* allocate 256 bytes (malloc) */
k_heapBMFree(&kheap, ptr); /* free the pointer (free) */
Now, using this you will have one problem. It will return a null pointer when there is no memory left which can be a problem. To get around this you can write a wrapper function and call it kmalloc or something, and have it check for a null pointer and if found allocate some memory from your higher level memory manager then add a block with k_heapBMAddBlock then attempt to allocate again. You will also want to add a check that your adding a large enough block for the allocation. You know if you adding 4K blocks to the heap and something allocates 16K well your going to need to add a block larger than 16K to have room for the bitmap and header. I will try to add a function later to tell you how much memory you need to handle a certain sized allocation later, but until now I suppose that is an exercise for you!
Code
/*
2014 Leonard Kevin McGuire Jr (www.kmcg3413.net) ([email protected])
2016 Clément Gallet (provided bug fixes)
*/
typedef struct _KHEAPBLOCKBM {
struct _KHEAPBLOCKBM *next;
uint32 size;
uint32 used;
uint32 bsize;
uint32 lfb;
} KHEAPBLOCKBM;
typedef struct _KHEAPBM {
KHEAPBLOCKBM *fblock;
} KHEAPBM;
void k_heapBMInit(KHEAPBM *heap) {
heap->fblock = 0;
}
int k_heapBMAddBlock(KHEAPBM *heap, uintptr addr, uint32 size, uint32 bsize) {
KHEAPBLOCKBM *b;
uint32 bcnt;
uint32 x;
uint8 *bm;
b = (KHEAPBLOCKBM*)addr;
b->size = size - sizeof(KHEAPBLOCKBM);
b->bsize = bsize;
b->next = heap->fblock;
heap->fblock = b;
bcnt = b->size / b->bsize;
bm = (uint8*)&b[1];
/* clear bitmap */
for (x = 0; x < bcnt; ++x) {
bm[x] = 0;
}
/* reserve room for bitmap */
bcnt = (bcnt / bsize) * bsize < bcnt ? bcnt / bsize + 1 : bcnt / bsize;
for (x = 0; x < bcnt; ++x) {
bm[x] = 5;
}
b->lfb = bcnt - 1;
b->used = bcnt;
return 1;
}
static uint8 k_heapBMGetNID(uint8 a, uint8 b) {
uint8 c;
for (c = a + 1; c == b || c == 0; ++c);
return c;
}
void *k_heapBMAlloc(KHEAPBM *heap, uint32 size) {
KHEAPBLOCKBM *b;
uint8 *bm;
uint32 bcnt;
uint32 x, y, z;
uint32 bneed;
uint8 nid;
/* iterate blocks */
for (b = heap->fblock; b; b = b->next) {
/* check if block has enough room */
if (b->size - (b->used * b->bsize) >= size) {
bcnt = b->size / b->bsize;
bneed = (size / b->bsize) * b->bsize < size ? size / b->bsize + 1 : size / b->bsize;
bm = (uint8*)&b[1];
for (x = (b->lfb + 1 >= bcnt ? 0 : b->lfb + 1); x < b->lfb; ++x) {
/* just wrap around */
if (x >= bcnt) {
x = 0;
}
if (bm[x] == 0) {
/* count free blocks */
for (y = 0; bm[x + y] == 0 && y < bneed && (x + y) < bcnt; ++y);
/* we have enough, now allocate them */
if (y == bneed) {
/* find ID that does not match left or right */
nid = k_heapBMGetNID(bm[x - 1], bm[x + y]);
/* allocate by setting id */
for (z = 0; z < y; ++z) {
bm[x + z] = nid;
}
/* optimization */
b->lfb = (x + bneed) - 2;
/* count used blocks NOT bytes */
b->used += y;
return (void*)(x * b->bsize + (uintptr)&b[1]);
}
/* x will be incremented by one ONCE more in our FOR loop */
x += (y - 1);
continue;
}
}
}
}
return 0;
}
void k_heapBMFree(KHEAPBM *heap, void *ptr) {
KHEAPBLOCKBM *b;
uintptr ptroff;
uint32 bi, x;
uint8 *bm;
uint8 id;
uint32 max;
for (b = heap->fblock; b; b = b->next) {
if ((uintptr)ptr > (uintptr)b && (uintptr)ptr < (uintptr)b + sizeof(KHEAPBLOCKBM) + b->size) {
/* found block */
ptroff = (uintptr)ptr - (uintptr)&b[1]; /* get offset to get block */
/* block offset in BM */
bi = ptroff / b->bsize;
/* .. */
bm = (uint8*)&b[1];
/* clear allocation */
id = bm[bi];
/* oddly.. GCC did not optimize this */
max = b->size / b->bsize;
for (x = bi; bm[x] == id && x < max; ++x) {
bm[x] = 0;
}
/* update free block count */
b->used -= x - bi;
return;
}
}
/* this error needs to be raised or reported somehow */
return;
}