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