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