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 <allocman/cspace/two_level.h>
14#include <allocman/util.h>
15#include <allocman/allocman.h>
16#include <sel4/sel4.h>
17#include <string.h>
18#include <utils/attribute.h>
19
20cspacepath_t _cspace_two_level_make_path(void *_cspace, seL4_CPtr slot)
21{
22    cspacepath_t l1_path, l2_path;
23    size_t l1slot, l2slot;
24    cspace_two_level_t *cspace = (cspace_two_level_t *)_cspace;
25    l1slot = slot >> cspace->config.level_two_bits;
26    l2slot = slot & MASK(cspace->config.level_two_bits);
27    /* This is an excessive way of constructing the path. But it's cool to do it in a way that
28       makes no assumptions about the underlying cspace structures. In particular the second level
29       could be a two level cspace and this would still work */
30    if (!cspace->second_levels[l1slot]) {
31        assert(!"ERROR: Tried make a path to a non existant slot\n");
32        return (cspacepath_t) {
33            0, 0, 0, 0, 0, 0, 0
34        };
35    }
36    l1_path = _cspace_single_level_make_path(&cspace->first_level, l1slot);
37    l2_path = _cspace_single_level_make_path(&cspace->second_levels[l1slot]->second_level, l2slot);
38    return (cspacepath_t) {
39        .root = l1_path.root,
40        .capPtr = (l1_path.capPtr << l2_path.capDepth) | l2_path.capPtr,
41        .capDepth = l1_path.capDepth + l2_path.capDepth,
42        .dest = (l1_path.capPtr << l2_path.destDepth) | l2_path.dest,
43        .destDepth = l1_path.capDepth + l2_path.destDepth,
44        .offset = l2_path.offset
45    };
46    /* This is the simpler version */
47    /* path->root = cspace->config.cnode;
48    path->slot = slot;
49    path->slot_depth = cspace->config.cnode_size_bits + cspace->config.cnode_guard_bits + cspace->config.level_two_bits;
50    path->cnode = l1slot;
51    path->cnode_depth = cspace->config.cnode_size_bits + cspace->config.cnode_guard_bits;
52    path->cnode_offset = l2slot;*/
53}
54
55static int _create_second_level(allocman_t *alloc, cspace_two_level_t *cspace, size_t index, int alloc_node)
56{
57    int error;
58    struct cspace_single_level_config single_config = {
59        /* There is no cap at depth 32 to reference the cnode of this cspace, fortunately
60           though we don't actually need it */
61        .cnode = 0,
62        .cnode_size_bits = cspace->config.level_two_bits,
63        .cnode_guard_bits = 0,
64        .first_slot = 0,
65        .end_slot = BIT(cspace->config.level_two_bits)
66    };
67    cspace->second_levels[index] = (struct cspace_two_level_node *) allocman_mspace_alloc(alloc,
68                                                                                          sizeof(struct cspace_two_level_node), &error);
69    if (error) {
70        return error;
71    }
72    if (alloc_node) {
73        cspacepath_t path = _cspace_single_level_make_path(&cspace->first_level, index);
74        cspace->second_levels[index]->cookie = allocman_utspace_alloc(alloc, cspace->config.level_two_bits + seL4_SlotBits,
75                                                                      seL4_CapTableObject, &path, false, &error);
76        cspace->second_levels[index]->cookie_valid = 1;
77    } else {
78        cspace->second_levels[index]->cookie_valid = 0;
79    }
80    if (error) {
81        allocman_mspace_free(alloc, cspace->second_levels[index], sizeof(struct cspace_two_level_node));
82        cspace->second_levels[index] = NULL;
83        return error;
84    }
85    error = cspace_single_level_create(alloc, &cspace->second_levels[index]->second_level, single_config);
86    if (error) {
87        allocman_utspace_free(alloc, cspace->second_levels[index]->cookie, cspace->config.level_two_bits + seL4_SlotBits);
88        allocman_mspace_free(alloc, cspace->second_levels[index], sizeof(struct cspace_two_level_node));
89        cspace->second_levels[index] = NULL;
90        return error;
91    }
92    cspace->second_levels[index]->count = 0;
93    return 0;
94}
95
96int cspace_two_level_create(allocman_t *alloc, cspace_two_level_t *cspace, struct cspace_two_level_config config)
97{
98    int error;
99    size_t i;
100    struct cspace_single_level_config single_config = {
101        .cnode = config.cnode,
102        .cnode_size_bits = config.cnode_size_bits,
103        .cnode_guard_bits = config.cnode_guard_bits,
104        .first_slot = config.first_slot,
105        .end_slot = config.end_slot
106    };
107    cspace->config = config;
108    cspace->second_levels = (struct cspace_two_level_node **)allocman_mspace_alloc(alloc,
109                                                                                   sizeof(struct cspace_two_level_node *) * BIT(config.cnode_size_bits), &error);
110    if (error) {
111        return error;
112    }
113    error = cspace_single_level_create(alloc, &cspace->first_level, single_config);
114    if (error) {
115        allocman_mspace_free(alloc, cspace->second_levels,
116                             sizeof(struct cspace_two_level_node *) * BIT(config.cnode_size_bits));
117        return error;
118    }
119    for (i = 0; i < BIT(config.cnode_size_bits); i++) {
120        cspace->second_levels[i] = NULL;
121    }
122    cspace->last_second_level = 0;
123    for (i = config.start_existing_index; i < config.end_existing_index; i++) {
124        error = _cspace_single_level_alloc_at(alloc, &cspace->first_level, (seL4_CPtr) i);
125        if (error) {
126            cspace_two_level_destroy(alloc, cspace);
127            return error;
128        }
129        error = _create_second_level(alloc, cspace, i, 0);
130        if (error) {
131            cspace_two_level_destroy(alloc, cspace);
132            return error;
133        }
134    }
135    /* now fill in any slots that may already be allocated */
136    for (i = config.start_existing_slot; i < config.end_existing_slot; i++) {
137        error = _cspace_two_level_alloc_at(alloc, cspace, (seL4_CPtr) i);
138        if (error) {
139            cspace_two_level_destroy(alloc, cspace);
140            return error;
141        }
142    }
143    return 0;
144}
145
146int _cspace_two_level_alloc_at(allocman_t *alloc, void *_cspace, seL4_CPtr slot)
147{
148    cspace_two_level_t *cspace = (cspace_two_level_t *)_cspace;
149    size_t l1slot;
150    size_t l2slot;
151    int error;
152    l1slot = slot >> cspace->config.level_two_bits;
153    l2slot = slot & MASK(cspace->config.level_two_bits);
154    /* see if the first level exists */
155    if (!cspace->second_levels[l1slot]) {
156        error = _cspace_single_level_alloc_at(alloc, &cspace->first_level, l1slot);
157        if (error) {
158            return error;
159        }
160        error = _create_second_level(alloc, cspace, l1slot, 1);
161        if (error) {
162            return error;
163        }
164    }
165    /* now try and allocate from the second level */
166    error = _cspace_single_level_alloc_at(alloc, &cspace->second_levels[l1slot]->second_level, (seL4_CPtr) l2slot);
167    if (error) {
168        return error;
169    }
170    cspace->second_levels[l1slot]->count++;
171    return 0;
172}
173
174int _cspace_two_level_alloc(allocman_t *alloc, void *_cspace, cspacepath_t *slot)
175{
176    cspace_two_level_t *cspace = (cspace_two_level_t *)_cspace;
177    size_t i;
178    int found;
179    int first;
180    int error;
181    cspacepath_t level2_slot;
182    /* Hunt for a slot */
183    i = cspace->last_second_level;
184    found = 0;
185    first = 1;
186    while (!found && (first || i != cspace->last_second_level)) {
187        first = 0;
188        if (cspace->second_levels[i] && cspace->second_levels[i]->count < MASK(cspace->config.level_two_bits)) {
189            found = 1;
190        } else {
191            i = (i + 1) % BIT(cspace->config.cnode_size_bits);
192        }
193    }
194    if (!found) {
195        /* ask the first level node for an empty slot */
196        cspacepath_t l1slot;
197        error = _cspace_single_level_alloc(alloc, &cspace->first_level, &l1slot);
198        if (error) {
199            /* our cspace is just full */
200            return error;
201        }
202        /* use this index */
203        error = _create_second_level(alloc, cspace, l1slot.offset, 1);
204        if (error) {
205            return error;
206        }
207    }
208    cspace->last_second_level = i;
209    error = _cspace_single_level_alloc(alloc, &cspace->second_levels[i]->second_level, &level2_slot);
210    if (error) {
211        /* This just shouldn't be possible */
212        assert(!"cspace_single_level not behaving as expected");
213        return error;
214    }
215    cspace->second_levels[i]->count++;
216    *slot = _cspace_two_level_make_path(cspace, (i << cspace->config.level_two_bits) | level2_slot.capPtr);
217    return 0;
218}
219
220static void _destroy_second_level(allocman_t *alloc, cspace_two_level_t *cspace, size_t index)
221{
222    cspacepath_t path;
223    cspace_single_level_destroy(alloc, &cspace->second_levels[index]->second_level);
224    if (cspace->second_levels[index]->cookie_valid) {
225        int UNUSED error = seL4_CNode_Delete(cspace->config.cnode, index,
226                                             seL4_WordBits - cspace->config.level_two_bits);
227        assert(error == seL4_NoError);
228        allocman_utspace_free(alloc, cspace->second_levels[index]->cookie, cspace->config.level_two_bits + seL4_SlotBits);
229    }
230    allocman_mspace_free(alloc, cspace->second_levels[index], sizeof(struct cspace_two_level_node));
231    path = _cspace_single_level_make_path(&cspace->first_level, index);
232    _cspace_single_level_free(alloc, &cspace->first_level, &path);
233}
234
235void _cspace_two_level_free(struct allocman *alloc, void *_cspace, const cspacepath_t *slot)
236{
237    size_t l1slot;
238    size_t l2slot;
239    seL4_CPtr cptr = slot->capPtr;
240    cspacepath_t path;
241    cspace_two_level_t *cspace = (cspace_two_level_t *)_cspace;
242    l1slot = cptr >> cspace->config.level_two_bits;
243    l2slot = cptr & MASK(cspace->config.level_two_bits);
244    path = _cspace_single_level_make_path(&cspace->second_levels[l1slot]->second_level, l2slot);
245    _cspace_single_level_free(alloc, &cspace->second_levels[l1slot]->second_level, &path);
246    cspace->second_levels[l1slot]->count--;
247    if (cspace->second_levels[l1slot]->count == 0) {
248        _destroy_second_level(alloc, cspace, l1slot);
249        cspace->second_levels[l1slot] = NULL;
250    }
251}
252
253void cspace_two_level_destroy(struct allocman *alloc, cspace_two_level_t *cspace)
254{
255    size_t i;
256    for (i = 0; i < BIT(cspace->config.cnode_size_bits); i++) {
257        if (cspace->second_levels[i]) {
258            _destroy_second_level(alloc, cspace, i);
259        }
260    }
261    allocman_mspace_free(alloc, cspace->second_levels,
262                         sizeof(struct cspace_two_level_node *) * BIT(cspace->config.cnode_size_bits));
263    cspace_single_level_destroy(alloc, &cspace->first_level);
264}
265