1/*
2 * Copyright 2017, Data61
3 * Commonwealth Scientific and Industrial Research Organisation (CSIRO)
4 * ABN 41 687 119 230.
5 *
6 * This software may be distributed and modified according to the terms of
7 * the BSD 2-Clause license. Note that NO WARRANTY is provided.
8 * See "LICENSE_BSD2.txt" for details.
9 *
10 * @TAG(DATA61_BSD)
11 */
12
13#include <autoconf.h>
14#include <allocman/utspace/split.h>
15#include <allocman/allocman.h>
16#include <allocman/util.h>
17#include <sel4/sel4.h>
18#include <vka/object.h>
19#include <vka/capops.h>
20#include <string.h>
21
22static void _remove_node(struct utspace_split_node **head, struct utspace_split_node *node)
23{
24    if (node->prev) {
25        node->prev->next = node->next;
26    } else {
27        assert(*head == node);
28        *head = node->next;
29    }
30    if (node->next) {
31        node->next->prev = node->prev;
32    }
33    node->head = head;
34}
35
36static void _insert_node(struct utspace_split_node **head, struct utspace_split_node *node)
37{
38    node->next = *head;
39    node->prev = NULL;
40    if (*head) {
41        (*head)->prev = node;
42    }
43    *head = node;
44    /* mark node as not allocated */
45    node->head = NULL;
46}
47
48static struct utspace_split_node *_new_node(allocman_t *alloc)
49{
50    int error;
51    struct utspace_split_node *node;
52    node = (struct utspace_split_node *) allocman_mspace_alloc(alloc, sizeof(*node), &error);
53    if (error) {
54        ZF_LOGV("Failed to allocate node of size %zu", sizeof(*node));
55        return NULL;
56    }
57    error = allocman_cspace_alloc(alloc, &node->ut);
58    if (error) {
59        allocman_mspace_free(alloc, node, sizeof(*node));
60        ZF_LOGV("Failed to allocate slot");
61        return NULL;
62    }
63    return node;
64}
65
66static void _delete_node(allocman_t *alloc, struct utspace_split_node *node)
67{
68    vka_cnode_delete(&node->ut);
69    allocman_cspace_free(alloc, &node->ut);
70    allocman_mspace_free(alloc, node, sizeof(*node));
71}
72
73static int _insert_new_node(allocman_t *alloc, struct utspace_split_node **head, cspacepath_t ut, uintptr_t paddr)
74{
75    int error;
76    struct utspace_split_node *node;
77    node = (struct utspace_split_node *) allocman_mspace_alloc(alloc, sizeof(*node), &error);
78    if (error) {
79        ZF_LOGV("Failed to allocate node of size %zu", sizeof(*node));
80        return 1;
81    }
82    node->parent = NULL;
83    node->ut = ut;
84    node->paddr = paddr;
85    node->origin_head = head;
86    _insert_node(head, node);
87    return 0;
88}
89
90void utspace_split_create(utspace_split_t *split)
91{
92    size_t i;
93    for (i = 0; i < ARRAY_SIZE(split->heads); i++) {
94        split->heads[i] = NULL;
95        split->dev_heads[i] = NULL;
96        split->dev_mem_heads[i] = NULL;
97    }
98}
99
100int _utspace_split_add_uts(allocman_t *alloc, void *_split, size_t num, const cspacepath_t *uts, size_t *size_bits,
101                           uintptr_t *paddr, int utType)
102{
103    utspace_split_t *split = (utspace_split_t *) _split;
104    int error;
105    size_t i;
106    struct utspace_split_node **list;
107    switch (utType) {
108    case ALLOCMAN_UT_KERNEL:
109        list = split->heads;
110        break;
111    case ALLOCMAN_UT_DEV:
112        list = split->dev_heads;
113        break;
114    case ALLOCMAN_UT_DEV_MEM:
115        list = split->dev_mem_heads;
116        break;
117    default:
118        return -1;
119    }
120    for (i = 0; i < num; i++) {
121        error = _insert_new_node(alloc, &list[size_bits[i]], uts[i], paddr ? paddr[i] : ALLOCMAN_NO_PADDR);
122        if (error) {
123            return error;
124        }
125    }
126    return 0;
127}
128
129static int _refill_pool(allocman_t *alloc, utspace_split_t *split, struct utspace_split_node **heads, size_t size_bits,
130                        uintptr_t paddr)
131{
132    struct utspace_split_node *node;
133    struct utspace_split_node *left, *right;
134    int sel4_error;
135    if (paddr == ALLOCMAN_NO_PADDR) {
136        /* see if pool is actually empty */
137        if (heads[size_bits]) {
138            return 0;
139        }
140    } else {
141        /* see if the pool has the paddr we want */
142        for (node = heads[size_bits]; node; node = node->next) {
143            if (node->paddr == ALLOCMAN_NO_PADDR) {
144                continue;
145            }
146            if (node->paddr <= paddr && paddr < node->paddr + BIT(size_bits)) {
147                return 0;
148            }
149        }
150    }
151    /* ensure we are not the highest pool */
152    if (size_bits >= sizeof(seL4_Word) * 8 - 2) {
153        /* bugger, no untypeds bigger than us */
154        ZF_LOGV("Failed to refill pool of size %zu, no larger pools", size_bits);
155        return 1;
156    }
157    /* get something from the highest pool */
158    if (_refill_pool(alloc, split, heads, size_bits + 1, paddr)) {
159        /* could not fill higher pool */
160        ZF_LOGV("Failed to refill pool of size %zu", size_bits);
161        return 1;
162    }
163    if (paddr == ALLOCMAN_NO_PADDR) {
164        /* use the first node for lack of a better one */
165        node = heads[size_bits + 1];
166    } else {
167        for (node = heads[size_bits + 1]; node && (node->paddr == ALLOCMAN_NO_PADDR || !(node->paddr <= paddr
168                                                                                         && paddr < node->paddr + BIT(size_bits + 1))); node = node->next);
169        /* _refill_pool should not have returned if this wasn't possible */
170        assert(node);
171    }
172    /* allocate two new nodes */
173    left = _new_node(alloc);
174    if (!left) {
175        ZF_LOGV("Failed to allocate left node");
176        return 1;
177    }
178    right = _new_node(alloc);
179    if (!right) {
180        ZF_LOGV("Failed to allocate right node");
181        _delete_node(alloc, left);
182        return 1;
183    }
184    /* perform the first retype */
185    sel4_error = seL4_Untyped_Retype(node->ut.capPtr, seL4_UntypedObject, size_bits, left->ut.root, left->ut.dest,
186                                     left->ut.destDepth, left->ut.offset, 1);
187    if (sel4_error != seL4_NoError) {
188        _delete_node(alloc, left);
189        _delete_node(alloc, right);
190        /* Well this shouldn't happen */
191        ZF_LOGE("Failed to retype untyped, error %d\n", sel4_error);
192        return 1;
193    }
194    /* perform the second retype */
195    sel4_error = seL4_Untyped_Retype(node->ut.capPtr, seL4_UntypedObject, size_bits, right->ut.root, right->ut.dest,
196                                     right->ut.destDepth, right->ut.offset, 1);
197    if (sel4_error != seL4_NoError) {
198        vka_cnode_delete(&left->ut);
199        _delete_node(alloc, left);
200        _delete_node(alloc, right);
201        /* Well this shouldn't happen */
202        ZF_LOGE("Failed to retype untyped, error %d\n", sel4_error);
203        return 1;
204    }
205    /* all is done. remove the parent and insert the children */
206    _remove_node(&heads[size_bits + 1], node);
207    left->parent = right->parent = node;
208    left->sibling = right;
209    left->origin_head = &heads[size_bits];
210    right->origin_head = &heads[size_bits];
211    right->sibling = left;
212    if (node->paddr != ALLOCMAN_NO_PADDR) {
213        left->paddr = node->paddr;
214        right->paddr = node->paddr + BIT(size_bits);
215    } else {
216        left->paddr = right->paddr = ALLOCMAN_NO_PADDR;
217    }
218    /* insert in this order so that we end up pulling the untypeds off in order of contiugous
219     * physical address. This makes various allocation problems slightly less likely to happen */
220    _insert_node(&heads[size_bits], right);
221    _insert_node(&heads[size_bits], left);
222    return 0;
223}
224
225static struct utspace_split_node **find_head_for_paddr(struct utspace_split_node **head, uintptr_t paddr,
226                                                       size_t size_bits)
227{
228    int i;
229    for (i = 0; i < CONFIG_WORD_SIZE; i++) {
230        struct utspace_split_node *node;
231        for (node = head[i]; node; node = node->next) {
232            if (node->paddr == ALLOCMAN_NO_PADDR) {
233                /* skip nodes with no physical address */
234                continue;
235            }
236            if (node->paddr <= paddr && paddr + BIT(size_bits) <= node->paddr + BIT(i)) {
237                return head;
238            }
239        }
240    }
241    return NULL;
242}
243
244seL4_Word _utspace_split_alloc(allocman_t *alloc, void *_split, size_t size_bits, seL4_Word type,
245                               const cspacepath_t *slot, uintptr_t paddr, bool canBeDev, int *error)
246{
247    utspace_split_t *split = (utspace_split_t *)_split;
248    size_t sel4_size_bits;
249    int sel4_error;
250    struct utspace_split_node *node;
251    /* get size of untyped call */
252    sel4_size_bits = get_sel4_object_size(type, size_bits);
253    if (size_bits != vka_get_object_size(type, sel4_size_bits) || size_bits == 0) {
254        SET_ERROR(error, 1);
255        return 0;
256    }
257    struct utspace_split_node **head = NULL;
258    /* if we're allocating at a particular paddr then we will just trawl through every pool
259     * and see if we can find out which one has what we want */
260    if (paddr != ALLOCMAN_NO_PADDR) {
261        if (canBeDev) {
262            head = find_head_for_paddr(split->dev_heads, paddr, size_bits);
263            if (!head) {
264                head = find_head_for_paddr(split->dev_mem_heads, paddr, size_bits);
265            }
266        }
267        if (!head) {
268            head = find_head_for_paddr(split->heads, paddr, size_bits);
269        }
270        if (!head) {
271            SET_ERROR(error, 1);
272            ZF_LOGE("Failed to find any untyped capable of creating an object at address %p", (void *)paddr);
273            return 0;
274        }
275        if (_refill_pool(alloc, split, head, size_bits, paddr)) {
276            /* out of memory? */
277            SET_ERROR(error, 1);
278            ZF_LOGV("Failed to refill pool to allocate object of size %zu", size_bits);
279            return 0;
280        }
281        /* search for the node we want to use. We have the advantage of knowing that
282         * due to objects being size aligned that the base paddr of the untyped will
283         * be exactly the paddr we want */
284        for (node = head[size_bits]; node && (node->paddr == ALLOCMAN_NO_PADDR || node->paddr != paddr); node = node->next);
285        /* _refill_pool should not have returned if this wasn't possible */
286        assert(node);
287    } else {
288        /* if we can use device memory then preference allocating from there */
289        if (canBeDev) {
290            if (_refill_pool(alloc, split, split->dev_mem_heads, size_bits, ALLOCMAN_NO_PADDR)) {
291                /* out of memory? Try fall through */
292                ZF_LOGV("Failed to refill device memory pool to allocate object of size %zu", size_bits);
293                ZF_LOGV("Trying regular untyped pool");
294            } else {
295                head = split->dev_mem_heads;
296            }
297
298        }
299        if (!head) {
300            head = split->heads;
301            if (_refill_pool(alloc, split, head, size_bits, ALLOCMAN_NO_PADDR)) {
302                /* out of memory? */
303                SET_ERROR(error, 1);
304                ZF_LOGV("Failed to refill pool to allocate object of size %zu", size_bits);
305                return 0;
306            }
307        }
308        /* use the first node for lack of a better one */
309        node = head[size_bits];
310    }
311    /* Perform the untyped retype */
312    sel4_error = seL4_Untyped_Retype(node->ut.capPtr, type, sel4_size_bits, slot->root, slot->dest, slot->destDepth,
313                                     slot->offset, 1);
314    if (sel4_error != seL4_NoError) {
315        /* Well this shouldn't happen */
316        ZF_LOGE("Failed to retype untyped, error %d\n", sel4_error);
317        SET_ERROR(error, 1);
318        return 0;
319    }
320    /* remove the node */
321    _remove_node(&head[size_bits], node);
322    SET_ERROR(error, 0);
323    /* return the node as a cookie */
324    return (seL4_Word)node;
325}
326
327void _utspace_split_free(allocman_t *alloc, void *_split, seL4_Word cookie, size_t size_bits)
328{
329    utspace_split_t *split = (utspace_split_t *)_split;
330    struct utspace_split_node *node = (struct utspace_split_node *)cookie;
331    struct utspace_split_node *parent = node->parent;
332    /* see if our sibling is also free */
333    if (parent && !node->sibling->head) {
334        /* remove sibling from free list */
335        _remove_node(node->sibling->origin_head, node->sibling);
336        /* delete both of us */
337        _delete_node(alloc, node->sibling);
338        _delete_node(alloc, node);
339        /* put the parent back in */
340        _utspace_split_free(alloc, split, (seL4_Word) parent, size_bits + 1);
341    } else {
342        /* just put ourselves back in */
343        _insert_node(node->head, node);
344    }
345}
346
347uintptr_t _utspace_split_paddr(void *_split, seL4_Word cookie, size_t size_bits)
348{
349    struct utspace_split_node *node = (struct utspace_split_node *)cookie;
350    return node->paddr;
351}
352