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