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