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