nuclear@28: #include <stdlib.h>
nuclear@28: #include "intr.h"
nuclear@28: #include "vm.h"
nuclear@28: #include "panic.h"
nuclear@28: 
nuclear@28: #define MAGIC	0xbaadbeef
nuclear@28: 
nuclear@28: struct mem_range {
nuclear@28: 	uint32_t start;
nuclear@28: 	size_t size;
nuclear@28: 	struct mem_range *next;
nuclear@28: };
nuclear@28: 
nuclear@28: struct alloc_desc {
nuclear@28: 	size_t size;
nuclear@28: 	uint32_t magic;
nuclear@28: };
nuclear@28: 
nuclear@28: static void add_range(struct mem_range *rng);
nuclear@28: static void coalesce(struct mem_range *low, struct mem_range *mid, struct mem_range *high);
nuclear@28: static struct mem_range *alloc_node(void);
nuclear@28: static void free_node(struct mem_range *node);
nuclear@28: 
nuclear@28: struct mem_range *free_list;
nuclear@28: struct mem_range *node_pool;
nuclear@28: 
nuclear@28: 
nuclear@28: void *malloc(size_t sz)
nuclear@28: {
nuclear@28: 	void *res = 0;
nuclear@28: 	struct mem_range *node, *prev, dummy;
nuclear@28: 	int intr_state;
nuclear@28: 	struct alloc_desc *desc;
nuclear@28: 	size_t alloc_size = sz + sizeof *desc;
nuclear@28: 
nuclear@28: 	if(!sz) {
nuclear@28: 		return 0;
nuclear@28: 	}
nuclear@28: 
nuclear@28: 	/* entering the critical section, do not disturb */
nuclear@28: 	intr_state = get_intr_state();
nuclear@28: 	disable_intr();
nuclear@28: 
nuclear@28: find_range:
nuclear@28: 	prev = &dummy;
nuclear@28: 	dummy.next = node = free_list;
nuclear@28: 	while(node) {
nuclear@28: 		/* find a node in the free_list with enough space ... */
nuclear@28: 		if(node->size >= alloc_size) {
nuclear@28: 			/* insert the allocation descriptor at the beginning */
nuclear@28: 			desc = (void*)node->start;
nuclear@28: 			desc->size = alloc_size;
nuclear@28: 			desc->magic = MAGIC;
nuclear@28: 			res = desc + 1; /* that's what we'll return to the user */
nuclear@28: 
nuclear@28: 			/* modify the node to reflect the new range after we
nuclear@28: 			 * grabbed a part at the beginning...
nuclear@28: 			 */
nuclear@28: 			node->size -= alloc_size;
nuclear@28: 			node->start += alloc_size;
nuclear@28: 
nuclear@28: 			/* if the range represented by this node now has zero size,
nuclear@28: 			 * remove and free the node (it goes into the node_pool)
nuclear@28: 			 */
nuclear@28: 			if(!node->size) {
nuclear@28: 				prev->next = node->next;
nuclear@28: 				if(free_list == node) {
nuclear@28: 					free_list = node->next;
nuclear@28: 				}
nuclear@28: 				free_node(node);
nuclear@28: 			}
nuclear@28: 			break;
nuclear@28: 		}
nuclear@28: 		prev = node;
nuclear@28: 		node = node->next;
nuclear@28: 	}
nuclear@28: 
nuclear@28: 	/* we didn't find a range big enough in the free_list. In that case
nuclear@28: 	 * we need to allocate some pages, add them to the free_list and try
nuclear@28: 	 * again.
nuclear@28: 	 */
nuclear@28: 	if(!res) {
nuclear@28: 		struct mem_range *range;
nuclear@28: 		int pg, pgcount = (PGSIZE - 1 + alloc_size) / PGSIZE;
nuclear@28: 
nuclear@28: 		if((pg = pgalloc(pgcount, MEM_KERNEL)) == -1) {
nuclear@28: 			set_intr_state(intr_state);
nuclear@28: 			return 0;
nuclear@28: 		}
nuclear@28: 
nuclear@28: 		range = alloc_node();
nuclear@28: 		range->start = PAGE_TO_ADDR(pg);
nuclear@31: 		range->size = pgcount * PGSIZE;
nuclear@28: 		add_range(range);
nuclear@28: 		goto find_range;
nuclear@28: 	}
nuclear@28: 
nuclear@28: 	set_intr_state(intr_state);
nuclear@28: 	return res;
nuclear@28: }
nuclear@28: 
nuclear@28: void free(void *ptr)
nuclear@28: {
nuclear@28: 	int intr_state;
nuclear@28: 	struct alloc_desc *desc;
nuclear@28: 	struct mem_range *rng;
nuclear@28: 
nuclear@28: 	if(!ptr) return;
nuclear@28: 
nuclear@28: 	intr_state = get_intr_state();
nuclear@28: 	disable_intr();
nuclear@28: 
nuclear@28: 	desc = (struct alloc_desc*)ptr - 1;
nuclear@28: 	if(desc->magic != MAGIC) {
nuclear@28: 		panic("free(%x) magic missmatch, invalid address.\n", (unsigned int)ptr);
nuclear@28: 	}
nuclear@28: 
nuclear@28: 	rng = alloc_node();
nuclear@28: 	rng->start = (uint32_t)desc;
nuclear@28: 	rng->size = desc->size;
nuclear@28: 	add_range(rng);
nuclear@28: 
nuclear@28: 	set_intr_state(intr_state);
nuclear@28: }
nuclear@28: 
nuclear@28: static void add_range(struct mem_range *rng)
nuclear@28: {
nuclear@28: 	struct mem_range *node, *prev = 0;
nuclear@28: 
nuclear@28: 	if(!free_list || free_list->start > rng->start) {
nuclear@28: 		rng->next = free_list;
nuclear@28: 		free_list = rng;
nuclear@28: 
nuclear@28: 	} else {
nuclear@28: 		node = free_list;
nuclear@28: 
nuclear@28: 		while(node) {
nuclear@28: 			if(!node->next || node->next->start > rng->start) {
nuclear@28: 				rng->next = node->next;
nuclear@28: 				node->next = rng;
nuclear@28: 				prev = node;	/* needed by coalesce after the loop */
nuclear@28: 				break;
nuclear@28: 			}
nuclear@28: 
nuclear@28: 			prev = node;
nuclear@28: 			node = node->next;
nuclear@28: 		}
nuclear@28: 	}
nuclear@28: 
nuclear@28: 	coalesce(prev, rng, rng->next);
nuclear@28: }
nuclear@28: 
nuclear@28: static void coalesce(struct mem_range *low, struct mem_range *mid, struct mem_range *high)
nuclear@28: {
nuclear@28: 	if(high) {
nuclear@28: 		if(mid->start + mid->size >= high->start) {
nuclear@28: 			mid->size = high->size - mid->start;
nuclear@28: 			mid->next = high->next;
nuclear@28: 			free_node(high);
nuclear@28: 		}
nuclear@28: 	}
nuclear@28: 
nuclear@28: 	if(low) {
nuclear@28: 		if(low->start + low->size >= mid->start) {
nuclear@28: 			low->size = mid->size - low->start;
nuclear@28: 			low->next = mid->next;
nuclear@28: 			free_node(mid);
nuclear@28: 		}
nuclear@28: 	}
nuclear@28: }
nuclear@28: 
nuclear@28: static struct mem_range *alloc_node(void)
nuclear@28: {
nuclear@28: 	struct mem_range *node;
nuclear@28: 
nuclear@28: 	/* no nodes available for reuse...
nuclear@28: 	 * grab a page, slice it into nodes, link them up and hang them in the pool
nuclear@28: 	 */
nuclear@28: 	if(!node_pool) {
nuclear@28: 		int i, num_nodes, pg;
nuclear@28: 		struct mem_range *nodepage;
nuclear@28: 
nuclear@28: 		pg = pgalloc(1, MEM_KERNEL);
nuclear@28: 		if(pg == -1) {
nuclear@28: 			panic("failed to allocate page for the malloc node pool\n");
nuclear@28: 			return 0;	/* unreachable */
nuclear@28: 		}
nuclear@28: 
nuclear@28: 		nodepage = (struct mem_range*)PAGE_TO_ADDR(pg);
nuclear@28: 		num_nodes = PGSIZE / sizeof *nodepage;
nuclear@28: 
nuclear@28: 		for(i=1; i<num_nodes; i++) {
nuclear@28: 			nodepage[i - 1].next = nodepage + i;
nuclear@28: 		}
nuclear@28: 		nodepage[i - 1].next = 0;
nuclear@28: 		node_pool = nodepage;
nuclear@28: 	}
nuclear@28: 
nuclear@28: 	node = node_pool;
nuclear@28: 	node_pool = node->next;
nuclear@28: 	node->next = 0;
nuclear@28: 	return node;
nuclear@28: }
nuclear@28: 
nuclear@28: static void free_node(struct mem_range *node)
nuclear@28: {
nuclear@28: 	node->next = node_pool;
nuclear@28: 	node_pool = node;
nuclear@28: }