1 /* 2 * Copyright (c) 2019 Intel Corporation 3 * 4 * SPDX-License-Identifier: Apache-2.0 5 */ 6 #ifndef ZEPHYR_INCLUDE_SYS_SYS_HEAP_H_ 7 #define ZEPHYR_INCLUDE_SYS_SYS_HEAP_H_ 8 9 #include <stddef.h> 10 #include <stdbool.h> 11 #include <zephyr/types.h> 12 13 /* Simple, fast heap implementation. 14 * 15 * A more or less conventional segregated fit allocator with 16 * power-of-two buckets. 17 * 18 * Excellent space efficiency. Chunks can be split arbitrarily in 8 19 * byte units. Overhead is only four bytes per allocated chunk (eight 20 * bytes for heaps >256kb or on 64 bit systems), plus a log2-sized 21 * array of 2-word bucket headers. No coarse alignment restrictions 22 * on blocks, they can be split and merged (in units of 8 bytes) 23 * arbitrarily. 24 * 25 * Simple API. Initialize at runtime with any blob of memory and not 26 * a macro-generated, carefully aligned static array. Allocate and 27 * free by user pointer and not an opaque block handle. 28 * 29 * Good fragmentation resistance. Freed blocks are always immediately 30 * merged with adjacent free blocks. Allocations are attempted from a 31 * sample of the smallest bucket that might fit, falling back rapidly 32 * to the smallest block guaranteed to fit. Split memory remaining in 33 * the chunk is always returned immediately to the heap for other 34 * allocation. 35 * 36 * Excellent performance with firmly bounded runtime. All operations 37 * are constant time (though there is a search of the smallest bucket 38 * that has a compile-time-configurable upper bound, setting this to 39 * extreme values results in an effectively linear search of the 40 * list), objectively fast (~hundred instructions) and and amenable to 41 * locked operation. 42 */ 43 44 /* Note: the init_mem/bytes fields are for the static initializer to 45 * have somewhere to put the arguments. The actual heap metadata at 46 * runtime lives in the heap memory itself and this struct simply 47 * functions as an opaque pointer. Would be good to clean this up and 48 * put the two values somewhere else, though it would make 49 * SYS_HEAP_DEFINE a little hairy to write. 50 */ 51 struct sys_heap { 52 struct z_heap *heap; 53 void *init_mem; 54 size_t init_bytes; 55 }; 56 57 struct z_heap_stress_result { 58 uint32_t total_allocs; 59 uint32_t successful_allocs; 60 uint32_t total_frees; 61 uint64_t accumulated_in_use_bytes; 62 }; 63 64 /** @brief Initialize sys_heap 65 * 66 * Initializes a sys_heap struct to manage the specified memory. 67 * 68 * @param heap Heap to initialize 69 * @param mem Untyped pointer to unused memory 70 * @param bytes Size of region pointed to by @a mem 71 */ 72 void sys_heap_init(struct sys_heap *heap, void *mem, size_t bytes); 73 74 /** @brief Allocate memory from a sys_heap 75 * 76 * Returns a pointer to a block of unused memory in the heap. This 77 * memory will not otherwise be used until it is freed with 78 * sys_heap_free(). If no memory can be allocated, NULL will be 79 * returned. The allocated memory is guaranteed to have a starting 80 * address which is a multiple of sizeof(void *). If a bigger alignment 81 * is necessary then sys_heap_aligned_alloc() should be used instead. 82 * 83 * @note The sys_heap implementation is not internally synchronized. 84 * No two sys_heap functions should operate on the same heap at the 85 * same time. All locking must be provided by the user. 86 * 87 * @param heap Heap from which to allocate 88 * @param bytes Number of bytes requested 89 * @return Pointer to memory the caller can now use 90 */ 91 void *sys_heap_alloc(struct sys_heap *heap, size_t bytes); 92 93 /** @brief Allocate aligned memory from a sys_heap 94 * 95 * Behaves in all ways like sys_heap_alloc(), except that the returned 96 * memory (if available) will have a starting address in memory which 97 * is a multiple of the specified power-of-two alignment value in 98 * bytes. With align=0 this behaves exactly like sys_heap_alloc(). 99 * The resulting memory can be returned to the heap using sys_heap_free(). 100 * 101 * @param heap Heap from which to allocate 102 * @param align Alignment in bytes, must be a power of two 103 * @param bytes Number of bytes requested 104 * @return Pointer to memory the caller can now use 105 */ 106 void *sys_heap_aligned_alloc(struct sys_heap *heap, size_t align, size_t bytes); 107 108 /** @brief Free memory into a sys_heap 109 * 110 * De-allocates a pointer to memory previously returned from 111 * sys_heap_alloc such that it can be used for other purposes. The 112 * caller must not use the memory region after entry to this function. 113 * 114 * @note The sys_heap implementation is not internally synchronized. 115 * No two sys_heap functions should operate on the same heap at the 116 * same time. All locking must be provided by the user. 117 * 118 * @param heap Heap to which to return the memory 119 * @param mem A pointer previously returned from sys_heap_alloc() 120 */ 121 void sys_heap_free(struct sys_heap *heap, void *mem); 122 123 /** @brief Expand the size of an existing allocation 124 * 125 * Returns a pointer to a new memory region with the same contents, 126 * but a different allocated size. If the new allocation can be 127 * expanded in place, the pointer returned will be identical. 128 * Otherwise the data will be copies to a new block and the old one 129 * will be freed as per sys_heap_free(). If the specified size is 130 * smaller than the original, the block will be truncated in place and 131 * the remaining memory returned to the heap. If the allocation of a 132 * new block fails, then NULL will be returned and the old block will 133 * not be freed or modified. 134 * 135 * @note The return of a NULL on failure is a different behavior than 136 * POSIX realloc(), which specifies that the original pointer will be 137 * returned (i.e. it is not possible to safely detect realloc() 138 * failure in POSIX, but it is here). 139 * 140 * @param heap Heap from which to allocate 141 * @param ptr Original pointer returned from a previous allocation 142 * @param align Alignment in bytes, must be a power of two 143 * @param bytes Number of bytes requested for the new block 144 * @return Pointer to memory the caller can now use, or NULL 145 */ 146 void *sys_heap_aligned_realloc(struct sys_heap *heap, void *ptr, 147 size_t align, size_t bytes); 148 149 #define sys_heap_realloc(heap, ptr, bytes) \ 150 sys_heap_aligned_realloc(heap, ptr, 0, bytes) 151 152 /** @brief Validate heap integrity 153 * 154 * Validates the internal integrity of a sys_heap. Intended for unit 155 * test and validation code, though potentially useful as a user API 156 * for applications with complicated runtime reliability requirements. 157 * Note: this cannot catch every possible error, but if it returns 158 * true then the heap is in a consistent state and can correctly 159 * handle any sys_heap_alloc() request and free any live pointer 160 * returned from a previou allocation. 161 * 162 * @param heap Heap to validate 163 * @return true, if the heap is valid, otherwise false 164 */ 165 bool sys_heap_validate(struct sys_heap *heap); 166 167 /** @brief sys_heap stress test rig 168 * 169 * Test rig for heap allocation validation. This will loop for @a 170 * op_count cycles, in each iteration making a random choice to 171 * allocate or free a pointer of randomized (power law) size based on 172 * heuristics designed to keep the heap in a state where it is near @a 173 * target_percent full. Allocation and free operations are provided 174 * by the caller as callbacks (i.e. this can in theory test any heap). 175 * Results, including counts of frees and successful/unsuccessful 176 * allocations, are returnewd via the @result struct. 177 * 178 * @param alloc_fn Callback to perform an allocation. Passes back the @a 179 * arg parameter as a context handle. 180 * @param free_fn Callback to perform a free of a pointer returned from 181 * @a alloc. Passes back the @a arg parameter as a 182 * context handle. 183 * @param arg Context handle to pass back to the callbacks 184 * @param total_bytes Size of the byte array the heap was initialized in 185 * @param op_count How many iterations to test 186 * @param scratch_mem A pointer to scratch memory to be used by the 187 * test. Should be about 1/2 the size of the heap 188 * for tests that need to stress fragmentation. 189 * @param scratch_bytes Size of the memory pointed to by @a scratch_mem 190 * @param target_percent Percentage fill value (1-100) to which the 191 * random allocation choices will seek. High 192 * values will result in significant allocation 193 * failures and a very fragmented heap. 194 * @param result Struct into which to store test results. 195 */ 196 void sys_heap_stress(void *(*alloc_fn)(void *arg, size_t bytes), 197 void (*free_fn)(void *arg, void *p), 198 void *arg, size_t total_bytes, 199 uint32_t op_count, 200 void *scratch_mem, size_t scratch_bytes, 201 int target_percent, 202 struct z_heap_stress_result *result); 203 204 /** @brief Print heap internal structure information to the console 205 * 206 * Print information on the heap structure such as its size, chunk buckets, 207 * chunk list and some statistics for debugging purpose. 208 * 209 * @param heap Heap to print information about 210 * @param dump_chunks True to print the entire heap chunk list 211 */ 212 void sys_heap_print_info(struct sys_heap *heap, bool dump_chunks); 213 214 #endif /* ZEPHYR_INCLUDE_SYS_SYS_HEAP_H_ */ 215
