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 <sel4utils/slab.h> 14#include <vka/capops.h> 15#include <vka/object.h> 16#include <utils/attribute.h> 17 18typedef struct { 19 /* number of objects in the slab */ 20 seL4_CPtr n; 21 /* next free object in the slab */ 22 seL4_CPtr next; 23 /* list of objects in the slab */ 24 vka_object_t *objects; 25} slab_t; 26 27typedef struct { 28 /* allocator to delegate further allocations to */ 29 vka_t *delegate; 30 /* allocation slab of each type */ 31 slab_t slabs[seL4_ObjectTypeCount]; 32 /* untyped to allocate from */ 33 vka_object_t untyped; 34} slab_data_t; 35 36typedef struct { 37 ssize_t size_bits; 38 seL4_Word type; 39} object_desc_t; 40 41static int compare_object_descs(const void *a, const void *b) 42{ 43 const object_desc_t *obj_a = a; 44 const object_desc_t *obj_b = b; 45 /* order by biggest first */ 46 return obj_b->size_bits - obj_a->size_bits; 47} 48 49static int delegate_cspace_alloc(void *data, seL4_CPtr *res) 50{ 51 slab_data_t *sdata = data; 52 assert(data != NULL); 53 assert(sdata->delegate != NULL); 54 return vka_cspace_alloc(sdata->delegate, res); 55} 56 57static void delegate_cspace_make_path(void *data, seL4_CPtr slot, cspacepath_t *res) 58{ 59 slab_data_t *sdata = data; 60 vka_cspace_make_path(sdata->delegate, slot, res); 61} 62 63static void delegate_cspace_free(void *data, seL4_CPtr slot) 64{ 65 slab_data_t *sdata = data; 66 vka_cspace_free(sdata->delegate, slot); 67} 68 69static int slab_utspace_alloc(void *data, const cspacepath_t *dest, seL4_Word type, 70 seL4_Word size_bits, seL4_Word *res) 71{ 72 slab_data_t *sdata = data; 73 74 if (type >= seL4_ObjectTypeCount) { 75 return -1; 76 } 77 78 slab_t *slab = &sdata->slabs[type]; 79 if (slab->next == slab->n) { 80 ZF_LOGW("Slab of type %lu expired, using delegate allocator", type); 81 return vka_utspace_alloc(sdata->delegate, dest, type, size_bits, res); 82 } 83 84 cspacepath_t src; 85 vka_cspace_make_path(sdata->delegate, slab->objects[slab->next].cptr, &src); 86 if (vka_cnode_move(dest, &src) != seL4_NoError) { 87 ZF_LOGW("Dest invalid\n"); 88 return -1; 89 } 90 91 slab->next++; 92 return 0; 93} 94 95static int slab_utspace_alloc_maybe_device(void *data, const cspacepath_t *dest, seL4_Word type, 96 seL4_Word size_bits, bool can_use_dev, seL4_Word *res) 97{ 98 return slab_utspace_alloc(data, dest, type, size_bits, res); 99} 100 101static int delegate_utspace_alloc_at(void *data, const cspacepath_t *dest, seL4_Word type, seL4_Word size_bits, 102 uintptr_t paddr, seL4_Word *res) 103{ 104 slab_data_t *sdata = data; 105 return vka_utspace_alloc_at(sdata->delegate, dest, type, size_bits, paddr, res); 106} 107 108static void 109slab_utspace_free(void *data, seL4_Word type, seL4_Word size_bits, seL4_Word target) 110{ 111 //TODO this should be possible - swap the object in at next, but do we need it? 112 ZF_LOGW("slab_utspace_free not implemented"); 113} 114 115static size_t calculate_total_size(size_t object_freq[seL4_ObjectTypeCount]) { 116 size_t total_size = 0; 117 for (int i = 0; i < seL4_ObjectTypeCount; i++) { 118 if (object_freq[i] > 0) { 119 size_t object_size = vka_get_object_size(i, 0); 120 if (object_size == 0 || object_size == -1) { 121 ZF_LOGE("Object of undetermined size passed to slab allocator"); 122 return 0; 123 } 124 total_size += (BIT(object_size)) * object_freq[i]; 125 } 126 } 127 return total_size; 128} 129 130static void slab_destroy(vka_t *slab) 131{ 132 ZF_LOGW("Slab destroy not implemented"); 133} 134 135static seL4_Error alloc_object(vka_t *delegate, vka_object_t *untyped, size_t size_bits, seL4_Word type, 136 vka_object_t *object) 137{ 138 /* allocate slot for object */ 139 object->type = type; 140 object->size_bits = size_bits; 141 seL4_Error error = vka_cspace_alloc(delegate, &object->cptr); 142 if (error != seL4_NoError) { 143 ZF_LOGE("Failed to allocate cslot"); 144 return error; 145 } 146 147 /* convert to cspacepath */ 148 cspacepath_t path; 149 vka_cspace_make_path(delegate, object->cptr, &path); 150 151 /* retype object */ 152 return seL4_Untyped_Retype(untyped->cptr, type, size_bits, path.root, path.dest, 153 path.destDepth, path.offset, 1); 154} 155 156static int alloc_object_slab(vka_t *delegate, vka_object_t *untyped, slab_t *slab, size_t n, 157 size_t size_bits, seL4_Word type) 158{ 159 ZF_LOGI("Preallocating %zu objects of %zu size bits, %lu type\n", n, size_bits, (long) type); 160 161 slab->n = n; 162 slab->next = 0; 163 164 if (n > 0) { 165 slab->objects = calloc(n, sizeof(vka_object_t)); 166 if (slab->objects == NULL) { 167 ZF_LOGI("Failed to allocate %zu objects of %zu size bits, %lu type", n, size_bits, (long) type); 168 return -1; 169 } 170 } 171 172 for (int i = 0; i < slab->n; i++) { 173 if (alloc_object(delegate, untyped, size_bits, type, &slab->objects[i]) != seL4_NoError) { 174 return -1; 175 } 176 } 177 178 /* success */ 179 return 0; 180} 181 182int slab_init(vka_t *slab_vka, vka_t *delegate, size_t object_freq[seL4_ObjectTypeCount]) { 183 184 slab_data_t *data = calloc(1, sizeof(slab_data_t)); 185 186 if (!data) { 187 slab_destroy(slab_vka); 188 return -1; 189 } 190 191 slab_vka->data = data; 192 data->delegate = delegate; 193 194 slab_vka->cspace_alloc = delegate_cspace_alloc; 195 slab_vka->cspace_make_path = delegate_cspace_make_path; 196 slab_vka->cspace_free = delegate_cspace_free; 197 slab_vka->utspace_alloc_at = delegate_utspace_alloc_at; 198 slab_vka->utspace_alloc = slab_utspace_alloc; 199 slab_vka->utspace_alloc_maybe_device = slab_utspace_alloc_maybe_device; 200 slab_vka->utspace_free = slab_utspace_free; 201 202 /* allocate untyped */ 203 size_t total_size = calculate_total_size(object_freq); 204 size_t total_size_bits = seL4_WordBits - CLZL(total_size); 205 /* sanity */ 206 assert(BIT(total_size_bits) >= total_size); 207 if (total_size == 0) { 208 ZF_LOGW("No objects to allocate\n"); 209 return 0; 210 } 211 212 int error = vka_alloc_untyped(delegate, total_size_bits, &data->untyped); 213 if (error != 0) { 214 ZF_LOGE("Failed to allocate untyped of size bits %zu\n", total_size_bits); 215 slab_destroy(slab_vka); 216 return -1; 217 } 218 219 /* order object sizes by size */ 220 object_desc_t object_descs[seL4_ObjectTypeCount]; 221 for (int i = 0; i < seL4_ObjectTypeCount; i++) { 222 object_descs[i].type = i; 223 object_descs[i].size_bits = vka_get_object_size(i, 0); 224 } 225 226 qsort(object_descs, seL4_ObjectTypeCount, sizeof(object_desc_t), compare_object_descs); 227 228 /* allocate slabs */ 229 for (int i = 0; i < seL4_ObjectTypeCount && object_descs[i].size_bits != 0; i++) { 230 int type = object_descs[i].type; 231 error = alloc_object_slab(delegate, &data->untyped, &data->slabs[type], 232 object_freq[type], object_descs[i].size_bits, type); 233 if (error != 0) { 234 ZF_LOGE("Failed to create slab\n"); 235 slab_destroy(slab_vka); 236 return -1; 237 } 238 } 239 240 return 0; 241} 242