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 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 /** 70 * @defgroup low_level_heap_allocator Low Level Heap Allocator 71 * @ingroup heaps 72 * @{ 73 */ 74 75 #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS 76 77 /** 78 * @brief Get the runtime statistics of a sys_heap 79 * 80 * @param heap Pointer to specified sys_heap 81 * @param stats_t Pointer to struct to copy statistics into 82 * @return -EINVAL if null pointers, otherwise 0 83 */ 84 int sys_heap_runtime_stats_get(struct sys_heap *heap, 85 struct sys_memory_stats *stats); 86 87 /** 88 * @brief Reset the maximum heap usage. 89 * 90 * Set the statistic measuring the maximum number of allocated bytes to the 91 * current number of allocated bytes. 92 * 93 * @param heap Pointer to sys_heap 94 * @return -EINVAL if null pointer was passed, otherwise 0 95 */ 96 int sys_heap_runtime_stats_reset_max(struct sys_heap *heap); 97 98 #endif 99 100 /** @brief Initialize sys_heap 101 * 102 * Initializes a sys_heap struct to manage the specified memory. 103 * 104 * @param heap Heap to initialize 105 * @param mem Untyped pointer to unused memory 106 * @param bytes Size of region pointed to by @a mem 107 */ 108 void sys_heap_init(struct sys_heap *heap, void *mem, size_t bytes); 109 110 /** @brief Allocate memory from a sys_heap 111 * 112 * Returns a pointer to a block of unused memory in the heap. This 113 * memory will not otherwise be used until it is freed with 114 * sys_heap_free(). If no memory can be allocated, NULL will be 115 * returned. The allocated memory is guaranteed to have a starting 116 * address which is a multiple of sizeof(void *). If a bigger alignment 117 * is necessary then sys_heap_aligned_alloc() should be used instead. 118 * 119 * @note The sys_heap implementation is not internally synchronized. 120 * No two sys_heap functions should operate on the same heap at the 121 * same time. All locking must be provided by the user. 122 * 123 * @param heap Heap from which to allocate 124 * @param bytes Number of bytes requested 125 * @return Pointer to memory the caller can now use 126 */ 127 void *sys_heap_alloc(struct sys_heap *heap, size_t bytes); 128 129 /** @brief Allocate aligned memory from a sys_heap 130 * 131 * Behaves in all ways like sys_heap_alloc(), except that the returned 132 * memory (if available) will have a starting address in memory which 133 * is a multiple of the specified power-of-two alignment value in 134 * bytes. With align=0 this behaves exactly like sys_heap_alloc(). 135 * The resulting memory can be returned to the heap using sys_heap_free(). 136 * 137 * @param heap Heap from which to allocate 138 * @param align Alignment in bytes, must be a power of two 139 * @param bytes Number of bytes requested 140 * @return Pointer to memory the caller can now use 141 */ 142 void *sys_heap_aligned_alloc(struct sys_heap *heap, size_t align, size_t bytes); 143 144 /** @brief Free memory into a sys_heap 145 * 146 * De-allocates a pointer to memory previously returned from 147 * sys_heap_alloc such that it can be used for other purposes. The 148 * caller must not use the memory region after entry to this function. 149 * 150 * @note The sys_heap implementation is not internally synchronized. 151 * No two sys_heap functions should operate on the same heap at the 152 * same time. All locking must be provided by the user. 153 * 154 * @param heap Heap to which to return the memory 155 * @param mem A pointer previously returned from sys_heap_alloc() 156 */ 157 void sys_heap_free(struct sys_heap *heap, void *mem); 158 159 /** @brief Expand the size of an existing allocation 160 * 161 * Returns a pointer to a new memory region with the same contents, 162 * but a different allocated size. If the new allocation can be 163 * expanded in place, the pointer returned will be identical. 164 * Otherwise the data will be copies to a new block and the old one 165 * will be freed as per sys_heap_free(). If the specified size is 166 * smaller than the original, the block will be truncated in place and 167 * the remaining memory returned to the heap. If the allocation of a 168 * new block fails, then NULL will be returned and the old block will 169 * not be freed or modified. 170 * 171 * @param heap Heap from which to allocate 172 * @param ptr Original pointer returned from a previous allocation 173 * @param align Alignment in bytes, must be a power of two 174 * @param bytes Number of bytes requested for the new block 175 * @return Pointer to memory the caller can now use, or NULL 176 */ 177 void *sys_heap_aligned_realloc(struct sys_heap *heap, void *ptr, 178 size_t align, size_t bytes); 179 180 #define sys_heap_realloc(heap, ptr, bytes) \ 181 sys_heap_aligned_realloc(heap, ptr, 0, bytes) 182 183 /** @brief Return allocated memory size 184 * 185 * Returns the size, in bytes, of a block returned from a successful 186 * sys_heap_alloc() or sys_heap_alloc_aligned() call. The value 187 * returned is the size of the heap-managed memory, which may be 188 * larger than the number of bytes requested due to allocation 189 * granularity. The heap code is guaranteed to make no access to this 190 * region of memory until a subsequent sys_heap_free() on the same 191 * pointer. 192 * 193 * @param heap Heap containing the block 194 * @param mem Pointer to memory allocated from this heap 195 * @return Size in bytes of the memory region 196 */ 197 size_t sys_heap_usable_size(struct sys_heap *heap, void *mem); 198 199 /** @brief Validate heap integrity 200 * 201 * Validates the internal integrity of a sys_heap. Intended for unit 202 * test and validation code, though potentially useful as a user API 203 * for applications with complicated runtime reliability requirements. 204 * Note: this cannot catch every possible error, but if it returns 205 * true then the heap is in a consistent state and can correctly 206 * handle any sys_heap_alloc() request and free any live pointer 207 * returned from a previous allocation. 208 * 209 * @param heap Heap to validate 210 * @return true, if the heap is valid, otherwise false 211 */ 212 bool sys_heap_validate(struct sys_heap *heap); 213 214 /** @brief sys_heap stress test rig 215 * 216 * Test rig for heap allocation validation. This will loop for @a 217 * op_count cycles, in each iteration making a random choice to 218 * allocate or free a pointer of randomized (power law) size based on 219 * heuristics designed to keep the heap in a state where it is near @a 220 * target_percent full. Allocation and free operations are provided 221 * by the caller as callbacks (i.e. this can in theory test any heap). 222 * Results, including counts of frees and successful/unsuccessful 223 * allocations, are returned via the @a result struct. 224 * 225 * @param alloc_fn Callback to perform an allocation. Passes back the @a 226 * arg parameter as a context handle. 227 * @param free_fn Callback to perform a free of a pointer returned from 228 * @a alloc. Passes back the @a arg parameter as a 229 * context handle. 230 * @param arg Context handle to pass back to the callbacks 231 * @param total_bytes Size of the byte array the heap was initialized in 232 * @param op_count How many iterations to test 233 * @param scratch_mem A pointer to scratch memory to be used by the 234 * test. Should be about 1/2 the size of the heap 235 * for tests that need to stress fragmentation. 236 * @param scratch_bytes Size of the memory pointed to by @a scratch_mem 237 * @param target_percent Percentage fill value (1-100) to which the 238 * random allocation choices will seek. High 239 * values will result in significant allocation 240 * failures and a very fragmented heap. 241 * @param result Struct into which to store test results. 242 */ 243 void sys_heap_stress(void *(*alloc_fn)(void *arg, size_t bytes), 244 void (*free_fn)(void *arg, void *p), 245 void *arg, size_t total_bytes, 246 uint32_t op_count, 247 void *scratch_mem, size_t scratch_bytes, 248 int target_percent, 249 struct z_heap_stress_result *result); 250 251 /** @brief Print heap internal structure information to the console 252 * 253 * Print information on the heap structure such as its size, chunk buckets, 254 * chunk list and some statistics for debugging purpose. 255 * 256 * @param heap Heap to print information about 257 * @param dump_chunks True to print the entire heap chunk list 258 */ 259 void sys_heap_print_info(struct sys_heap *heap, bool dump_chunks); 260 261 /** 262 * @} 263 */ 264 265 #ifdef __cplusplus 266 } 267 #endif 268 269 #endif /* ZEPHYR_INCLUDE_SYS_SYS_HEAP_H_ */ 270
