1/* 2 * Copyright 2014, NICTA 3 * 4 * This software may be distributed and modified according to the terms of 5 * the BSD 2-Clause license. Note that NO WARRANTY is provided. 6 * See "LICENSE_BSD2.txt" for details. 7 * 8 * @TAG(NICTA_BSD) 9 */ 10 11#include "alloc.h" 12 13/* Disable "printk" error messages. */ 14#define printk(x...) 15 16/* 17 * Ensure condition "x" is true. 18 */ 19#define assert(x) \ 20 do { if (!(x)) { for (;;); } } while (0) 21 22/* Is the given value aligned to the given alignment? */ 23#define IS_ALIGNED(x, val) (((x) % (1UL << val)) == 0UL) 24 25/* Align "val" up to the next "2 ** align_bits" boundary. */ 26static word_t 27align_up(word_t val, word_t align_bits) 28{ 29 assert(align_bits < 32UL); 30 return (val + ((1UL << align_bits) - 1UL)) & (~((1UL << align_bits) - 1UL)); 31} 32 33/* Return the maximum of "a" and "b". */ 34static word_t 35max(word_t a, word_t b) 36{ 37 if (a >= b) 38 return a; 39 return b; 40} 41 42/* 43 * This simple allocator uses a linked list of "mem_nodes", each which 44 * contain a size (indicating that the 'size' bytes from the beginning 45 * of the mem_node are free, other than containing the mem_node itself), 46 * and a pointer to the next. The list of "mem_nodes" are in sorted 47 * order by their virtual address. 48 * 49 * We additionally have an initial "dummy" mem_node that begins the list 50 * of size 0. This is to make the code simpler by each node having 51 * a previous node. The typical method of dealing with this (taking 52 * a pointer the previous node's next pointer) unfortunately does not 53 * work due to limitations in the verification framework. (Pointers 54 * can't be taken to a field of a struct.) 55 * 56 * To allocate, we find a mem_node which contains a valid range and 57 * allocate the range out of the mem_node. This may completely use up 58 * the mem_node (in which case, it is taken out of the list), be 59 * allocated from the start or end of the mem_node (in which case it is 60 * adjusted/moved), or be allocated from the middle of the mem_node (in 61 * which case, we end up with one more mem_node than we begun with). 62 * 63 * Free'ing is the reverse process, ensuring that we correctly merge 64 * mem_nodes as required. 65 */ 66 67/* Allocate a chunk of memory. */ 68void * 69alloc(struct heap *heap, word_t size, word_t alignment_bits) 70{ 71 assert(size > 0); 72 assert(alignment_bits < 32); 73 74 struct mem_node *prev = heap->head; 75 struct mem_node *current = prev->next; 76 77 /* Round size and alignment up to ALLOC_CHUNK_SIZE_BITS */ 78 size = align_up(size, ALLOC_CHUNK_SIZE_BITS); 79 alignment_bits = max(alignment_bits, ALLOC_CHUNK_SIZE_BITS); 80 81 while (current != NULL) { 82 /* Calculate the bounds of this region of memory. */ 83 word_t node_start = (word_t)current; 84 word_t node_end = node_start + current->size - 1; 85 assert(node_start < node_end); 86 assert(IS_ALIGNED(node_end + 1, ALLOC_CHUNK_SIZE_BITS)); 87 88 /* Calculate the bounds of our desired memory region, 89 * noting that we may overflow in either calculation. */ 90 word_t desired_start = align_up(node_start, alignment_bits); 91 word_t desired_end = desired_start + size - 1; 92 93 /* If the desired range (after alignment and size changes) 94 * fits within this node, then allocate it. */ 95 if (desired_start >= node_start 96 && desired_end <= node_end 97 && desired_start < desired_end) { 98 /* If we have space after the allocation, create a new node 99 * covering the area. */ 100 if (desired_end != node_end) { 101 assert(node_end - desired_end >= ALLOC_CHUNK_SIZE_BITS); 102 struct mem_node *new_node = (struct mem_node *)(desired_end + 1); 103 new_node->size = node_end - desired_end; 104 new_node->next = current->next; 105 current->next = new_node; 106 } 107 108 /* If we have space before the allocation, update the node. 109 * Otherwise, remove it. */ 110 if (desired_start != node_start) { 111 current->size = desired_start - node_start; 112 } else { 113 prev->next = current->next; 114 } 115 116 /* Return the allocation. */ 117 heap->num_allocs++; 118 return (void *)desired_start; 119 } 120 121 prev = current; 122 current = current->next; 123 } 124 125 return NULL; 126} 127 128/* Free a chunk of memory. */ 129void 130dealloc(struct heap *heap, void *ptr, word_t size) 131{ 132 assert(size > 0); 133 assert(ptr != NULL); 134 135 struct mem_node *prev = heap->head; 136 struct mem_node *current = prev->next; 137 struct mem_node *new = (struct mem_node *)ptr; 138 139 /* Round size and alignment up to ALLOC_CHUNK_SIZE_BITS */ 140 size = align_up(size, ALLOC_CHUNK_SIZE_BITS); 141 142 /* Find our position in the list. */ 143 while ((word_t)current < (word_t)ptr && (current != NULL)) { 144 prev = current; 145 current = current->next; 146 } 147 148 /* Determine if we should merge with previous, or add a new node. */ 149 if ((word_t)prev + prev->size == (word_t)new) { 150 prev->size += size; 151 new = prev; 152 } else { 153 new->size = size; 154 prev->next = new; 155 } 156 157 /* Determine if we should merge the next with the new. */ 158 if ((word_t)new + new->size == (word_t)current) { 159 new->size += current->size; 160 new->next = current->next; 161 } else { 162 new->next = current; 163 } 164 165 /* Track deallocation. */ 166 heap->num_allocs--; 167} 168 169/* Add a pool of memory to the given allocator. */ 170void 171add_mem_pool(struct heap *heap, void *ptr, word_t size) 172{ 173 printk("Adding memory pool %lx--%lx\n", 174 (word_t)ptr, (word_t)ptr + size); 175 dealloc(heap, ptr, size); 176 heap->num_allocs++; 177} 178 179/* Setup the initial allocator. */ 180void 181init_allocator(struct heap *init_heap, struct mem_node *init_mem_node) 182{ 183 init_heap->head = init_mem_node; 184 init_heap->head->size = 0; 185 init_heap->head->next = NULL; 186} 187 188 189