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