User:Pancakes/EntryBasedHeapImplementation

From OSDev Wiki
Jump to navigation Jump to search

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!

Gotcha

I forgot to make it align on at least a specific boundary such as 4-byte boundary. So, I think it would be good practice for whomever if using this to code that in! At least until I get around to fixing it. The fix should be fairly simple, and mainly just involve some code on the allocation function.

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_heapLCABInit(&kheap);                          /* initialize the heap */
    k_heapLCABAddBlock(&kheap, 0x100000, 0x100000);  /* add block to heap (starting 1MB mark and length of 1MB) */
    ptr = (char*)k_heapLCABAlloc(&kheap, 256);               /* allocate 256 bytes (malloc) */
    k_heapLCABFree(&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

/*
    2014 Leonard Kevin McGuire Jr (www.kmcg3413.net) ([email protected])
*/
typedef unsigned int uint32;
typedef unsigned char uint8;
typedef unsigned int uintptr;

#define KHEAPFLAG_USED			0x80000000

typedef struct _KHEAPHDRLCAB {
	uint32				prevsize;
	uint32				flagsize;
} KHEAPHDRLCAB;

typedef struct _KHEAPBLOCKLCAB {
	uint32					size;
	uint32					used;
	struct _KHEAPBLOCKLCAB	                *next;
	uint32					lastdsize;
	KHEAPHDRLCAB			        *lastdhdr;
} KHEAPBLOCKLCAB;

typedef struct _KHEAPLCAB {
	KHEAPBLOCKLCAB		       *fblock;
	uint32				bcnt;
} KHEAPLCAB;

void k_heapLCABInit(KHEAPLCAB *heap) {
		heap->fblock = 0;
		heap->bcnt = 0;
}

int k_heapLCABAddBlock(KHEAPLCAB *heap, uintptr addr, uint32 size) {
	KHEAPBLOCKLCAB			*hb;
	KHEAPHDRLCAB			*hdr;
	
	//printf("add block addr:%p size:%x\n", addr, size);
	
	hb = (KHEAPBLOCKLCAB*)addr;
	hb->size = size;
	hb->used = 0;
	hb->next = heap->fblock;
	heap->fblock = hb;
	
	hdr = (KHEAPHDRLCAB*)&hb[1];
	hdr->flagsize = hb->size - (sizeof(KHEAPBLOCKLCAB) + 32);
	
	++heap->bcnt;
	
	hb->lastdsize = 0;
	hb->lastdhdr = 0;
	
	//printf("added block; block-count:%u\n", heap->bcnt);
	
	//printf("added block hb:%p hb->next:%p\n", hb, hb->next);
	//sleep(10);
	return 1;
}

/*
	Look behind and forward to see if we can merge back into some chunks.
*/
void k_heapLCABFree(KHEAPLCAB *heap, void *ptr) {
	KHEAPHDRLCAB				*hdr, *phdr, *nhdr;
	KHEAPBLOCKLCAB				*hb;
	uint32						sz;
	uint8						fg;
	
	//printf("lab pre-free ptr:%p\n", ptr);
	
	hdr = (KHEAPHDRLCAB*)ptr;
	//printf("GGGG\n");
	hdr[-1].flagsize &= ~0x80000000;
		
	//printf("lcab free\n");
		
	phdr = 0;
	/* find the block we are located in */
	for (hb = heap->fblock; hb; hb = hb->next) {
		//printf("lcab free looking at block:%p next:%p ptr:%p end:%p\n", hb, hb->next, ptr, (uintptr)hb + hb->size);
		if (((uintptr)ptr > (uintptr)hb) && ((uintptr)ptr < (uintptr)hb + hb->size)) {
			/* we have found the heap block */
			
			/* get header */
			hdr = (KHEAPHDRLCAB*)((uintptr)ptr - sizeof(KHEAPHDRLCAB));
			
			/* set to free */
			hdr->flagsize &= ~0x80000000;
			
			hb->used -= hdr->flagsize;
			
			/* get previous header if it exists */
			if (hdr->prevsize) {
				phdr = (KHEAPHDRLCAB*)((uintptr)&hdr - (sizeof(KHEAPHDRLCAB) + hdr->prevsize));
			} else {
				phdr = 0;
			}
			
			//printf("hdr:%p hdr->flagsize:%x hdr->prevsize:%x\n", hdr, hdr->flagsize, hdr->prevsize);
			/* get next header */
			nhdr = (KHEAPHDRLCAB*)((uintptr)&hdr[1] + hdr->flagsize);
			if ((uintptr)nhdr >= ((uintptr)hb + hb->size)) {
				nhdr = 0;
			}
						
			//fg = hdr->flagsize >> 31;
			//sz = hdr->flagsize & 0x7fffffff;			
			
			//printf("hdr:%p phdr:%p nhdr:%p phdr->flagsize:%x hdr->flagsize:%x\n", hdr, phdr, nhdr, phdr->flagsize, hdr->flagsize);
			if (nhdr) {
				if (!(nhdr->flagsize & 0x80000000)) {
					/* combine with it */
					hdr->flagsize += sizeof(KHEAPHDRLCAB) + nhdr->flagsize;
					hb->used -= sizeof(KHEAPHDRLCAB);
					/* set next header prevsize */
					nhdr = (KHEAPHDRLCAB*)((uintptr)&hdr[1] + hdr->flagsize);
					nhdr->prevsize = hdr->flagsize;
				}
			}
			
			//printf("here hdr:%p prevsize:%x\n", hdr, hdr->prevsize);
			
			/* can we combine with previous header? */
			if (phdr) {				
				if (!(phdr->flagsize & 0x80000000)) {
					//printf("combine backward\n");
					phdr->flagsize += sizeof(KHEAPHDRLCAB) + hdr->flagsize;
					hb->used -= sizeof(KHEAPHDRLCAB);
					hdr = phdr;
					/* set next header prevsize */
					nhdr = (KHEAPHDRLCAB*)((uintptr)&hdr[1] + hdr->flagsize);
					if ((uintptr)nhdr < (uintptr)hb + sizeof(KHEAPBLOCKLCAB) + hb->size) {
						nhdr->prevsize = hdr->flagsize;
					}
				}
			}
			
			/* optimization */
			if (hdr->flagsize > hb->lastdsize) {
				hb->lastdsize = hdr->flagsize;
				hb->lastdhdr = hdr;
			}
			
			return;
		}
	}
	
	printf("uhoh ptr:%p\n", ptr);
	for (hb = heap->fblock; hb; hb = hb->next) {
		printf("lcab free looking at block:%p next:%p ptr:%p end:%p\n", hb, hb->next, ptr, (uintptr)hb + hb->size);
		if (((uintptr)ptr > (uintptr)hb)) {
			printf("above\n");
			if (((uintptr)ptr < ((uintptr)hb + hb->size))) {
				printf("found\n");
			}
		}
	}
	for (;;);
	/* 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_heapLCABAlloc(KHEAPLCAB *heap, uint32 size) {
	KHEAPBLOCKLCAB		*hb;
	KHEAPHDRLCAB		*hdr, *_hdr, *phdr;
	uint32				sz;
	uint8				fg;
	uint32				checks;
	uint32				bc;
	
	checks = 0;
	bc =0;
	
	//printf("lcab alloc\n");
	/* first find heap block with enough space */
	for (hb = heap->fblock; hb; hb = hb->next) {
		if ((hb->size - hb->used) >= (size + sizeof(KHEAPHDRLCAB))) {
			++bc;
			/* optimization */
			//if (hb->lastdsize >= size) {
				/* optimization (use block) */
				//hdr = hb->lastdhdr;
				//hb->lastdhdr = 0;
				//hb->lastdsize = 0;
			//} else {
			hdr = (KHEAPHDRLCAB*)&hb[1];
			//}
			
			//printf("enter loop\n");
			phdr = 0;
			while ((uintptr)hdr < ((uintptr)hb + hb->size)) {
				++checks;
				//printf("lcab alloc found\n");
				fg = hdr->flagsize >> 31;
				sz = hdr->flagsize & 0x7fffffff;
				//printf("hdr:%p fg:%x sz:%x\n", hdr, fg, sz);
				if (!fg) {
					//printf("lcab alloc got chunk\n");
					if (sz >= size) {
						//printf("lcab alloc thinking of splitting\n");
						// else take whole chunk
						if (sz > (size + sizeof(KHEAPHDRLCAB) + 16)) {
							//printf("lcab alloc splitting\n");
							/* has enough left over (break into two) */
							_hdr = (KHEAPHDRLCAB*)((uintptr)&hdr[1] + size);
							//printf("AA\n");
							/* take out data size and header size */
							_hdr->flagsize = sz - (size + sizeof(KHEAPHDRLCAB));
							_hdr->prevsize = size;
							//printf("BB\n");
							/* set to used and set new size */
							hdr->flagsize = 0x80000000 | size;
							//printf("CC\n");
							hb->used += sizeof(KHEAPHDRLCAB);
							//printf("DD\n");
						} else {
							/* simply set to used */
							hdr->flagsize |= 0x80000000;
						}
						hb->used += size;
						
						//printf("ptr:%p\n", &hdr[1]);
						//printf("alloced checks:%u blocks-checked:%u\n", checks, bc);
						
						return &hdr[1];
					}
				}
				phdr = hdr;
				hdr = (KHEAPHDRLCAB*)((uintptr)&hdr[1] + sz);
			}
			//printf("exit loop\n");
		}
	}
	
	//printf("return null\n");
	return 0;
}

Problems/Suggestions/Feedback

I rarely get any feedback from a lot of stuff. So even negative feedback is good. If you want to tell me something just drop a message at, [email protected]. I am always curious who actually find usage for things that I put up on the internet.

Retrieved from "https://wiki.osdev.org/index.php?title=User:Pancakes/EntryBasedHeapImplementation&oldid=16348"