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