1/** 2 * \file 3 * \brief Simple heap allocator. 4 * 5 * This file implements a very simple heap allocator, based on K&R malloc. 6 */ 7 8/* 9 * Copyright (c) 2008, ETH Zurich. 10 * All rights reserved. 11 * 12 * This file is distributed under the terms in the attached LICENSE file. 13 * If you do not find this file, copies can be found by writing to: 14 * ETH Zurich D-INFK, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group. 15 */ 16 17#include <barrelfish/barrelfish.h> 18#include <barrelfish/heap.h> 19 20/** 21 * \brief Initialise a new heap 22 * 23 * \param heap Heap structure to be filled in 24 * \param buf Memory buffer out of which to allocate 25 * \param buflen Size of buffer 26 * \param morecore_func Function to call to increase heap, or NULL 27 */ 28void heap_init(struct heap *heap, void *buf, size_t buflen, 29 Morecore_func_t morecore_func) 30{ 31 assert(heap != NULL); 32 assert(buf != NULL); 33 assert(buflen > sizeof(union heap_header)); 34 35 // Initialise base header (nothing allocated) 36 heap->base.s.ptr = heap->freep = &heap->base; 37 heap->base.s.size = 0; 38 heap->morecore_func = morecore_func; 39 40 // Insert freelist header into new memory buffer 41 union heap_header *h = buf; 42 h->s.size = buflen / sizeof(union heap_header); 43 44 // Add header to freelist 45 heap_free(heap, (void *)(h + 1)); 46} 47 48/** 49 * \brief Equivalent of malloc; allocates memory out of given heap. 50 * 51 * \returns NULL on failure 52 */ 53void *heap_alloc(struct heap *heap, size_t nbytes) 54{ 55 union heap_header *p, *prevp; 56 unsigned nunits; 57 nunits = (nbytes + sizeof(union heap_header) - 1) 58 / sizeof(union heap_header) + 1; 59 60 prevp = heap->freep; 61 assert(prevp != NULL); 62 63 for (p = prevp->s.ptr;; prevp = p, p = p->s.ptr) { 64 if (p->s.size >= nunits) { /* big enough */ 65 if (p->s.size == nunits) { /* exactly */ 66 prevp->s.ptr = p->s.ptr; 67 } else { /* allocate tail end */ 68 p->s.size -= nunits; 69 p += p->s.size; 70 p->s.size = nunits; 71 } 72 heap->freep = prevp; 73 74 return (void *) (p + 1); 75 } 76 if (p == heap->freep) { /* wrapped around free list */ 77 /* try morecore, if we have one */ 78 if (heap->morecore_func == NULL 79 || (p = (union heap_header *) 80 heap->morecore_func(heap, nunits)) == NULL) { 81 return NULL; /* none left */ 82 } 83 } 84 } 85} 86 87/** 88 * \brief Equivalent of free: put block back in free list. 89 */ 90void heap_free(struct heap *heap, void *ap) 91{ 92 union heap_header *bp, *p; 93 94 assert(heap != NULL); 95 assert(heap->freep != NULL); 96 if (ap == NULL) { 97 return; 98 } 99 100 bp = (union heap_header *) ap - 1; /* point to block header */ 101 for (p = heap->freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr) { 102 if (p >= p->s.ptr && (bp > p || bp < p->s.ptr)) { 103 break; /* freed block at start or end of arena */ 104 } 105 } 106 107 if (bp + bp->s.size == p->s.ptr) { /* join to upper nbr */ 108 bp->s.size += p->s.ptr->s.size; 109 bp->s.ptr = p->s.ptr->s.ptr; 110 } else { 111 bp->s.ptr = p->s.ptr; 112 } 113 114 if (p + p->s.size == bp) { /* join to lower nbr */ 115 p->s.size += bp->s.size; 116 p->s.ptr = bp->s.ptr; 117 } else { 118 p->s.ptr = bp; 119 } 120 121 heap->freep = p; 122} 123 124 125/** 126 * \brief Allocate and map in one or more pages of memory 127 */ 128static void *pages_alloc(size_t pages) 129{ 130 assert(!"not implemented"); 131 return NULL; 132} 133 134/** 135 * \brief sbrk() equivalent. 136 * 137 * This function allocates at least the amount given by 'nu' in sizeof(::Header) 138 * byte units. It returns a pointer to the freelist header of the memory region. 139 * NULL is returned when out of memory. 140 * 141 * \param nu Number of memory units (1 unit == sizeof(::Header) bytes) 142 * 143 * \return Pointer to freelist header of new memory region or NULL on out of 144 * memory. 145 */ 146union heap_header *heap_default_morecore(struct heap *heap, unsigned nu) 147{ 148 union heap_header *up; 149 size_t nb = ROUND_UP(nu * sizeof(union heap_header), 150 BASE_PAGE_SIZE); 151 152 // Allocate requested number of pages and insert freelist header 153 up = (union heap_header*)pages_alloc(nb / BASE_PAGE_SIZE); 154 up->s.size = nb / sizeof(union heap_header); 155 156 // Add header to freelist 157 heap_free(heap, (void *)(up + 1)); 158 return up; 159} 160