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/** 14 * @file allocman.h 15 * 16 * @brief The allocman is system for resolving dependencies between allocators for different resources 17 * 18 * Allocations need to go via the allocation manager in order to ensure 19 * the correct watermark levels of resources are maintained. While an 20 * individual manager is free to directly give away resources, if it 21 * calls into the allocation manager then that manager may be recursively 22 * invoked. Performing allocations from the allocation manager is also 23 * the only way to allocate the final watermark resources when memory 24 * becomes exhausted. 25 * 26 * It is generally desirable that a free operation does not have any 27 * allocation calls in it. If an allocator does wish to allocate a 28 * resource when performing a free it must accept that its allocation 29 * function could be called as a result. In a similar manner if your 30 * allocation function frees resources your free function may be recursively 31 * called. 32 * 33 * There are (generally) two different types of allocators. Those that are 34 * linked to an allocation manager, and those that are not. Typically the 35 * only sort of manager you would not want linked to an allocation manager 36 * is a cspace manager (if you are managing a clients cspace). Although you 37 * could also create an untyped manager if you do not want to give clients 38 * untypeds directly, but still want to have a fixed untyped pool reserved 39 * for it. 40 * 41 * Possibility exists for much foot shooting with any allocators. A typical 42 * desire might be to create a sub allocator (such as a cspace manager), 43 * use an already existing allocation manager to back all of its allocations, 44 * and then destroy that cspace manager at some point to release all its resources. 45 * There are no guarantees that this will work. If all requests to the sub allocator 46 * use the same allocation manager to perform book keeping requests, and the 47 * sub allocator is told to free using that same allocation manager then all 48 * should work. But this is strictly up to using your allocators correctly, 49 * and knowing how they work. 50 */ 51 52#pragma once 53 54#include <assert.h> 55#include <autoconf.h> 56#include <sel4/types.h> 57#include <allocman/util.h> 58#include <allocman/cspace/cspace.h> 59#include <allocman/mspace/mspace.h> 60#include <allocman/utspace/utspace.h> 61#include <vka/cspacepath_t.h> 62#include <sel4platsupport/timer.h> 63 64/** 65 * Describes a reservation chunk for the memory system. 66 * Used by {@link #allocman_configure_mspace_reserve} 67 */ 68struct allocman_mspace_chunk { 69 size_t size; 70 size_t count; 71}; 72 73/** 74 * Describes a reservation chunk for the untyped system. 75 * Used by {@link #allocman_configure_utspace_reserve} 76 */ 77struct allocman_utspace_chunk { 78 size_t size_bits; 79 seL4_Word type; 80 size_t count; 81}; 82 83/** 84 * Internal data structure for describing an untyped allocation in 85 * the reservation system 86 */ 87struct allocman_utspace_allocation { 88 seL4_Word cookie; 89 cspacepath_t slot; 90}; 91 92struct allocman_freed_mspace_chunk { 93 void *ptr; 94 size_t size; 95}; 96 97struct allocman_freed_utspace_chunk { 98 size_t size_bits; 99 seL4_Word cookie; 100}; 101 102/** 103 * The allocman itself. This is generally the only type you will need to pass around 104 * to deal with allocation. It is declared in full here so that the compiler is able 105 * to calculate its size so it can be allocated on stacks/globals etc as required 106 */ 107typedef struct allocman { 108 /* link to our underlying allocators. some are lazily added. the mspace will always be here, 109 * and have_mspace can be used to check if the allocman is initialized at all */ 110 int have_mspace; 111 struct mspace_interface mspace; 112 int have_cspace; 113 struct cspace_interface cspace; 114 int have_utspace; 115 struct utspace_interface utspace; 116 117 /* Flag that tracks whether any alloc/free/other function has been entered yet */ 118 int in_operation; 119 120 /* Counts that track re-entry into each specific alloc/free function */ 121 size_t cspace_alloc_depth; 122 size_t cspace_free_depth; 123 size_t utspace_alloc_depth; 124 size_t utspace_free_depth; 125 size_t mspace_alloc_depth; 126 size_t mspace_free_depth; 127 128 /* Track whether the watermark is currently refilled so we don't recursively do it */ 129 int refilling_watermark; 130 /* Has a watermark resource been used. This is just an optimization */ 131 int used_watermark; 132 133 /* track resources that we have not yet been able to free due to circular dependencies */ 134 size_t desired_freed_slots; 135 size_t num_freed_slots; 136 cspacepath_t *freed_slots; 137 138 size_t desired_freed_mspace_chunks; 139 size_t num_freed_mspace_chunks; 140 struct allocman_freed_mspace_chunk *freed_mspace_chunks; 141 142 size_t desired_freed_utspace_chunks; 143 size_t num_freed_utspace_chunks; 144 struct allocman_freed_utspace_chunk *freed_utspace_chunks; 145 146 /* cspace watermark resources */ 147 size_t desired_cspace_slots; 148 size_t num_cspace_slots; 149 cspacepath_t *cspace_slots; 150 151 /* mspace watermark resources */ 152 size_t num_mspace_chunks; 153 struct allocman_mspace_chunk *mspace_chunk; 154 size_t *mspace_chunk_count; 155 void ***mspace_chunks; 156 157 /* utspace watermark resources */ 158 size_t num_utspace_chunks; 159 struct allocman_utspace_chunk *utspace_chunk; 160 size_t *utspace_chunk_count; 161 struct allocman_utspace_allocation **utspace_chunks; 162} allocman_t; 163 164/** 165 * Allocates 'real' memory from the allocator 166 * 167 * @param alloc Allocman to allocate from 168 * @param bytes Size in bytes to allocate 169 * @param _error (Optional) set to 0 on success 170 * 171 * @return returns pointer to allocated memory 172 */ 173void *allocman_mspace_alloc(allocman_t *alloc, size_t bytes, int *_error); 174 175/** 176 * Frees 'real' memory, as previously allocated by {@link #allocman_mspace_alloc} 177 * 178 * @param alloc Allocman to allocate from 179 * @param ptr Allocated memory (as returned by {@link #allocman_mspace_alloc} 180 * @param bytes Size in bytes of the allocation to free. Allocations cannot be partially freed 181 */ 182void allocman_mspace_free(allocman_t *alloc, void *ptr, size_t bytes); 183 184/** 185 * Allocates a cslot from the allocator 186 * 187 * @param alloc Allocman to allocate from 188 * @param slot Stores details of the allocated slot 189 * 190 * @return returns 0 on sucess 191 */ 192int allocman_cspace_alloc(allocman_t *alloc, cspacepath_t *slot); 193 194/** 195 * Frees a cslot from the allocator, as previously allocated by {@link #allocman_cspace_alloc}. 196 * To avoid the need to keep cspacepath_t's laying around, it is guaruanteed that 197 * (*slot) == allocman_cspace_make_path(alloc, slot->capPtr). So if needed you can simply store 198 * the capPtr and reconstruct the path before calling free. 199 * 200 * @param alloc Allocman to allocate from 201 * @param slot The slot to free. 202 * 203 * @return returns 0 on sucess 204 */ 205void allocman_cspace_free(allocman_t *alloc, const cspacepath_t *slot); 206 207/** 208 * Converts a seL4_CPtr into a cspacepath_t using the cspace attached to the allocman. 209 * If the slot is not valid in that cspace then the return path is completely undefined. 210 * 211 * @param alloc Allocman to allocate from 212 * @param slot The slot to convert 213 * 214 * @return cspacepath_t of the given slot 215 */ 216static inline cspacepath_t allocman_cspace_make_path(allocman_t *alloc, seL4_CPtr slot) { 217 assert(alloc->have_cspace); 218 return alloc->cspace.make_path(alloc->cspace.cspace, slot); 219} 220 221/** 222 * Allocates a portion of untyped memory, and retypes it into the desired object for you. 223 * 224 * @param alloc Allocman to allocate from 225 * @param size_bits The size in bits of the memory that will be required to store this object. 226 This is different to seL4_Untyped_Retype for allocating seL4_CapTableObjects 227 * @param type The seL4 type of the object being allocated 228 * @param path A path to a location to put the allocated object (this must be a valid empty slot) 229 * @param paddr The desired physical address of the start of this object. A value of '1' indicates do not care 230 * as '1' can never be a valid object base address 231 * @param canBeDev Whether this allocation can be satisified from a device region, provided that 232 * region is known to be actual RAM. Objects from device regions are not initialized (i.e. not zeroed) 233 * @param _error (Optional) set to 0 on success 234 * 235 * @return Returns a cookie that can be used in future to free this allocation 236 */ 237seL4_Word allocman_utspace_alloc_at(allocman_t *alloc, size_t size_bits, seL4_Word type, const cspacepath_t *path, uintptr_t paddr, bool canBeDev, int *_error); 238 239/** 240 * Allocates a portion of untyped memory, and retypes it into the desired object for you. 241 * 242 * @param alloc Allocman to allocate from 243 * @param size_bits The size in bits of the memory that will be required to store this object. 244 This is different to seL4_Untyped_Retype for allocating seL4_CapTableObjects 245 * @param type The seL4 type of the object being allocated 246 * @param path A path to a location to put the allocated object (this must be a valid empty slot) 247 * @param canBeDev Whether this allocation can be satisified from a device region, provided that 248 * region is known to be actual RAM. Objects from device regions are not initialized (i.e. not zeroed) 249 * @param _error (Optional) set to 0 on success 250 * 251 * @return Returns a cookie that can be used in future to free this allocation 252 */ 253static inline 254seL4_Word allocman_utspace_alloc(allocman_t *alloc, size_t size_bits, seL4_Word type, const cspacepath_t *path, bool canBeDev, int *_error) 255{ 256 return allocman_utspace_alloc_at(alloc, size_bits, type, path, ALLOCMAN_NO_PADDR, canBeDev, _error); 257} 258 259/** 260 * Returns a portion of untyped memory back to the allocator. It is assumed that this 261 * memory is now unused, and every capability to this memory has been deleted (including 262 * the one created by {@link allocman_utspace_alloc} 263 * 264 * @param alloc Allocman to allocate from 265 * @param size_bits The size in bits of the memory that was required to store this object. 266 This is different to seL4_Untyped_Retype for seL4_CapTableObjects 267 * @param cookie The cookie representing this allocation (as returned by {@link allocman_utspace_alloc} 268 */ 269void allocman_utspace_free(allocman_t *alloc, seL4_Word cookie, size_t size_bits); 270 271/** 272 * Initialize a new allocman. all it requires is a memory allocator, everything will be boot strapped from it 273 * 274 * @param alloc Allocman structure to initialize 275 * @param mspace Memory allocator. This will be permanently linked to this allocator and must keep existing 276 * 277 * @return returns 0 on success 278 */ 279int allocman_create(allocman_t *alloc, struct mspace_interface mspace); 280 281/** 282 * Attempts to fill the reserves of the allocator. This can be used if the underlying allocators have been modified, 283 * for instance by having resources added, or as a way to query the health of the allocman 284 * 285 * @param alloc The allocman to fill reserves of 286 * 287 * @return returns 0 if reserves are full 288 */ 289int allocman_fill_reserves(allocman_t *alloc); 290 291/** 292 * Attach an untyped allocator to an allocman. 293 * 294 * @param alloc The allocman to attach to 295 * @param utspace untyped allocator to attach. This wil lbe permanently linked to this allocator and must keep existing 296 * 297 * @return returns 0 on success 298 */ 299int allocman_attach_utspace(allocman_t *alloc, struct utspace_interface utspace); 300 301/** 302 * Attach a cspace manager to an allocman. 303 * 304 * @param alloc The allocman to attach to 305 * @param cspace The cspace manager to attach. This wil lbe permanently linked to this allocator and must keep existing 306 * 307 * @return returns 0 on success 308 */ 309int allocman_attach_cspace(allocman_t *alloc, struct cspace_interface cspace); 310 311/** 312 * Configure the memory reserve for the allocator 313 * 314 * @param alloc The allocman to configure 315 * @param chunk Description of the memory reserve 316 * 317 * @return returns 0 on success 318 */ 319int allocman_configure_mspace_reserve(allocman_t *alloc, struct allocman_mspace_chunk chunk); 320 321/** 322 * Configure the untyped reserve for the allocator 323 * 324 * @param alloc The allocman to configure 325 * @param chunk Description of the untyped reserve 326 * 327 * @return returns 0 on success 328 */ 329int allocman_configure_utspace_reserve(allocman_t *alloc, struct allocman_utspace_chunk chunk); 330 331/** 332 * Configure the cspace reserve for the allocator 333 * 334 * @param alloc The allocman to configure 335 * @param num Number of cslots to hold in reserve 336 * 337 * @return returns 0 on success 338 */ 339int allocman_configure_cspace_reserve(allocman_t *alloc, size_t num); 340 341/** 342 * Configure the maximul number of freed cptrs we can store. This is required for 343 * scenarios where an allocator cannot handle a recursive call, but we would like to not 344 * leak memory 345 * 346 * @param alloc The allocman to configure 347 * @param num Maximum number of slots to handle 348 * 349 * @return returns 0 on success 350 */ 351int allocman_configure_max_freed_slots(allocman_t *alloc, size_t num); 352 353/** 354 * Configure the maximul number of freed memory objects we can store. This is required for 355 * scenarios where an allocator cannot handle a recursive call, but we would like to not 356 * leak memory 357 * 358 * @param alloc The allocman to configure 359 * @param num Maxmimum number of chunks to handle 360 * 361 * @return returns 0 on success 362 */ 363int allocman_configure_max_freed_memory_chunks(allocman_t *alloc, size_t num); 364 365/** 366 * Configure the maximul number of freed untyped objects we can store. This is required for 367 * scenarios where an allocator cannot handle a recursive call, but we would like to not 368 * leak memory 369 * 370 * @param alloc The allocman to configure 371 * @param num Maxmimum number of chunks to handle 372 * 373 * @return returns 0 on success 374 */ 375int allocman_configure_max_freed_untyped_chunks(allocman_t *alloc, size_t num); 376 377/** 378 * Add additional untyped objects to the underlying untyped manager. This allows additional 379 * resources to be injected after the allocman has started 380 * 381 * @param alloc The allocman to add to 382 * @param num Number of untypeds to add 383 * @param uts Path to each of the untyped to add. untyped is assumed to be at depth 32 from this threads cspace_root 384 * @param size_bits Size, in bits, of each of the untypeds 385 * @param paddr Optional parameter specifying the physical address of each of the untypeds 386 * @param utType The type of all untypeds being added. One of (ALLOCMAN_UT_KERNEL, ALLOCMAN_UT_DEV, ALLOCMAN_UT_DEV_MEM) 387 * 388 * @return returns 0 on success 389 */ 390static inline int allocman_utspace_add_uts(allocman_t *alloc, size_t num, const cspacepath_t *uts, size_t *size_bits, uintptr_t *paddr, int utType) { 391 int error; 392 assert(alloc->have_utspace); 393 error = alloc->utspace.add_uts(alloc, alloc->utspace.utspace, num, uts, size_bits, paddr, utType); 394 if (error) { 395 return error; 396 } 397 allocman_fill_reserves(alloc); 398 return 0; 399} 400 401/** 402 * Retrieves the physical address for an allocated untyped object 403 * 404 * @param alloc The allocman to query 405 * @param cookie Cookie to the allocated untyped object 406 * @param size_bits Size of the allocated untyped object 407 * 408 * @return Physical address of the object 409 */ 410static inline uintptr_t allocman_utspace_paddr(allocman_t *alloc, seL4_Word cookie, size_t size_bits) { 411 assert(alloc->have_utspace); 412 return alloc->utspace.paddr(alloc->utspace.utspace, cookie, size_bits); 413} 414 415/** 416 * Helper function for adding device untypeds from platform specific timer objects 417 * 418 * @param alloc The allocman to query 419 * @param to struct containing untyped metadata 420 * 421 * @return 0 on success, otherwise error. 422 */ 423int allocman_add_untypeds_from_timer_objects(allocman_t *alloc, timer_objects_t *to); 424 425