+#endif /* !SINGLE_POOL */
+
+
+#ifdef SINGLE_POOL
+#define MIN_BLOCK_SIZE (sizeof(struct mem_desc) * 2)
+
+void *malloc(size_t sz)
+{
+ int pg0, npages;
+ size_t total_sz, rest_sz;
+ struct mem_desc *mem, *rest, *prev, dummy;
+ int found = 0;
+
+ total_sz = (sz + sizeof(struct mem_desc) + 3) & 0xfffffffc;
+
+ dummy.next = pool;
+ prev = &dummy;
+ while(prev->next) {
+ mem = prev->next;
+ /* give the whole block to the allocation if mem->size == total_sz or
+ * if it's larger, but not large enough to fit another mem_desc in there
+ * for the new block that we're going to split off + some reasonable
+ * amount of memory for the new block.
+ */
+ if(mem->size >= total_sz && mem->size < total_sz + MIN_BLOCK_SIZE) {
+ prev->next = mem->next;
+ found = 1;
+ break;
+ }
+ /* if we have enough space, split the block and give the upper part
+ * to the allocation
+ */
+ if(mem->size > total_sz) {
+ void *ptr = (char*)mem + mem->size - total_sz;
+ mem->size -= total_sz;
+ mem = ptr;
+ found = 1;
+ break;
+ }
+ prev = prev->next;
+ }
+ pool = dummy.next;
+
+ if(found) {
+ mem->size = total_sz;
+ mem->magic = MAGIC_USED;
+ mem->next = 0;
+ return DESC_PTR(mem);
+ }
+
+ /* did not find a free block, grab a new one */
+ npages = BYTES_TO_PAGES(total_sz);
+ if((pg0 = alloc_ppages(npages, 0)) == -1) {
+ errno = ENOMEM;
+ return 0;
+ }
+ mem = PAGE_TO_PTR(pg0);
+ mem->size = total_sz;
+ mem->next = 0;
+ mem->magic = MAGIC_USED;
+
+ /* add the rest of the block to pool */
+ rest_sz = npages * 4096 - total_sz;
+ if(rest_sz > 0) {
+ rest = (struct mem_desc*)((char*)mem + total_sz);
+ rest->size = rest_sz;
+ rest->next = 0;
+ rest->magic = MAGIC_USED;
+ free(DESC_PTR(rest));
+ }
+
+ return DESC_PTR(mem);
+}
+
+void free(void *p)
+{
+ struct mem_desc *mem, *prev, *cur, dummy;
+ char *end;
+
+ if(!p) return;
+ mem = PTR_DESC(p);
+
+ if(mem->magic != MAGIC_USED) {
+ if(mem->magic == MAGIC_FREE) {
+ panic("free(%p): double-free\n", p);
+ } else {
+ panic("free(%p): corrupted magic (%x)!\n", p, mem->magic);
+ }
+ }
+ mem->magic = MAGIC_FREE;
+ mem->next = 0;
+
+ /* nothing in the pool, just add this one */
+ if(!pool) {
+ pool = mem;
+ return;
+ }
+
+ end = (char*)mem + mem->size;
+
+ dummy.next = pool;
+ prev = &dummy;
+
+ while(prev->next) {
+ cur = prev->next;
+
+ /* block starts right at the end of mem: coalesce */
+ if((char*)cur == end) {
+ mem->size += cur->size;
+ mem->next = cur->next;
+ cur->magic = 0;
+ prev->next = mem;
+ goto done;
+ }
+
+ /* block starts *after* the end of mem: add in front */
+ if((char*)cur > end) {
+ mem->next = cur;
+ prev->next = mem;
+ goto done;
+ }
+
+ prev = prev->next;
+ }
+
+ /* our block starts at the end of the last block in the pool: coalesce */
+ if((char*)prev + prev->size == (char*)mem) {
+ mem->magic = 0;
+ prev->size += mem->size;
+ goto done;
+ }
+
+ /* so our block starts after the end of the last block: append */
+ prev->next = mem;
+
+done:
+ pool = dummy.next;
+
+#ifdef MALLOC_DEBUG
+ print_pool();
+#endif
+}
+
+#else /* !SINGLE_POOL */