From e8cf65c07d78e3cfbac953b1b97c51998a5900df Mon Sep 17 00:00:00 2001
From: Alex AUVOLAT <alexis211@gmail.com>
Date: Tue, 1 May 2012 14:55:18 +0200
Subject: Now using Doug Lea's malloc in kernel land. Next: same in userland.

---
 src/kernel/mem/heap.basic.c | 136 --------------------------------------------
 1 file changed, 136 deletions(-)
 delete mode 100644 src/kernel/mem/heap.basic.c

(limited to 'src/kernel/mem/heap.basic.c')

diff --git a/src/kernel/mem/heap.basic.c b/src/kernel/mem/heap.basic.c
deleted file mode 100644
index d746deb..0000000
--- a/src/kernel/mem/heap.basic.c
+++ /dev/null
@@ -1,136 +0,0 @@
-#include "heap.basic.h"
-
-#include "paging.h"
-
-#include <lib/mutex.h>
-#include <core/sys.h>
-
-void heap_create(struct heap *heap, size_t start, size_t datasize, size_t maxdatasize) {
-	uint32_t i;
-	if (start & 0x0FFF) start = (start & 0xFFFFF000) + 0x1000;
-	
-	// Allocate frames
-	for (i = start; i < start + datasize; i += 0x1000) {
-		page_map(pagedir_getPage(kernel_pagedir, i, 1), frame_alloc(), 0, 0);
-	}
-
-	heap->start_addr = start;
-	heap->end_addr = start + datasize;
-	heap->max_end = start + maxdatasize;
-
-	struct heap_header *first = (struct heap_header*)start;
-	first->magic = HH_FREE_MAGIC;
-	first->prev = first->next = first;
-
-	heap->first = first;
-	heap->first_free = first;
-	
-	heap->mutex = 0;
-}
-
-// ***** UTILITY FUNCTIONS *****
-
-#define BLK_SIZE(blk) (blk->next == blk ? ((size_t)heap->end_addr - (size_t)blk) : ((size_t)blk->next - (size_t)blk))
-#define BLK_FREE(blk) (blk->magic == HH_FREE_MAGIC)
-
-void blk_split(struct heap *heap, struct heap_header *hdr, size_t size) {
-	ASSERT (size >= MIN_BLK_SIZE);
-	ASSERT (BLK_SIZE(hdr) > size);
-	ASSERT (BLK_SIZE(hdr) - size >= MIN_BLK_SIZE);
-	ASSERT (BLK_FREE(hdr));
-
-	struct heap_header *hdr_nxt = (struct heap_header*)((size_t)hdr + size);
-	hdr_nxt->magic = HH_FREE_MAGIC;
-	hdr_nxt->prev = hdr;
-	if (hdr->next == hdr) {
-		hdr_nxt->next = hdr_nxt;
-	} else {
-		hdr_nxt->next = hdr->next;
-		hdr->next->prev = hdr_nxt;
-	}
-	hdr->next = hdr_nxt;
-}
-
-void blk_combine_next(struct heap *heap, struct heap_header *hdr) {
-	ASSERT (hdr != hdr->next);	// make sure we are not the last block
-	ASSERT (hdr->magic == HH_FREE_MAGIC);
-	ASSERT (hdr->next->magic == HH_FREE_MAGIC);
-
-	struct heap_header *hdr_nxt = hdr->next;
-	if (hdr_nxt->next == hdr_nxt) {
-		hdr->next = hdr;
-	} else {
-		hdr->next = hdr_nxt->next;
-		hdr_nxt->next->prev = hdr;
-	}
-}
-
-// ***** Allocation/Freeing functions *****
-
-void *heap_alloc(struct heap *heap, size_t sz) {
-	/* Algorithm :
-	1 Use heap->first_free to find first effectively free block, update heap->first_free
-	2 Find first free AND BIG ENOUGH block
-		- If no block can be found, return 0 (no heap expand yet)
-	3 If that block is too big, split it in two
-	4 Mark that block as used and return it's address + sizeof(heap_header) */
-	mutex_lock(&heap->mutex);
-
-	sz += sizeof(struct heap_header);
-	if (sz < MIN_BLK_SIZE) sz = MIN_BLK_SIZE;
-	if (sz % 4 != 0) sz = sz + 4 - (sz % 4); 
-
-	// 1
-	struct heap_header *it = heap->first_free;
-	while (!BLK_FREE(it) && it != it->next) it = it->next;
-	if (!BLK_FREE(it) && it == it->next) {
-		mutex_unlock(&heap->mutex);
-		return 0;
-	}
-	heap->first_free = it;
-
-	// 2
-	while (BLK_SIZE(it) < sz && it != it->next) it = it->next;
-	if (BLK_SIZE(it) < sz) {		// no block could be found
-		mutex_unlock(&heap->mutex);
-		return 0;
-	}
-
-	// 3
-	if (BLK_SIZE(it) >= sz + MIN_BLK_SIZE) blk_split(heap, it, sz);
-
-	// 4
-	void *ret = (void*)((size_t)it + sizeof(struct heap_header));
-	it->magic = HH_ALLOC_MAGIC;
-
-	mutex_unlock(&heap->mutex);
-	return ret;
-}
-
-void heap_free(struct heap *heap, void *ptr) {
-	/* Algorithm :
-	1 Get block pointer to the block we are freeing
-	2 Mark that block as free
-	3 If block->next is free, combine_next(block)
-	4 If block->prev is free, block = block->prev; combine_next(block)
-	5 If block < heap->first_free; heap->first_free = block
-	*/
-	mutex_lock(&heap->mutex);
-
-	// 1
-	struct heap_header *hdr = (struct heap_header*)((size_t)ptr - sizeof(struct heap_header));
-	if (hdr->magic != HH_ALLOC_MAGIC) return;
-	// 2
-	hdr->magic = HH_FREE_MAGIC;
-	// 3
-	if (hdr->next != hdr && hdr->next->magic == HH_FREE_MAGIC) blk_combine_next(heap, hdr);
-	// 4
-	if (hdr->prev != hdr && hdr->prev->magic == HH_FREE_MAGIC) {
-		hdr = hdr->prev;
-		blk_combine_next(heap, hdr);
-	}
-	// 5
-	if (hdr < heap->first_free) heap->first_free = hdr;
-
-	mutex_unlock(&heap->mutex);
-}
-- 
cgit v1.2.3