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