Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2019 Intel Corporation
3 : : *
4 : : * SPDX-License-Identifier: Apache-2.0
5 : : */
6 : : #include <zephyr/sys/sys_heap.h>
7 : : #include <zephyr/sys/util.h>
8 : : #include <zephyr/sys/heap_listener.h>
9 : : #include <zephyr/kernel.h>
10 : : #include <zephyr/logging/log.h>
11 : : #include <string.h>
12 : : #include "heap.h"
13 : :
14 : : LOG_MODULE_REGISTER(os_heap, CONFIG_SYS_HEAP_LOG_LEVEL);
15 : : #ifdef CONFIG_MSAN
16 : : #include <sanitizer/msan_interface.h>
17 : : #endif
18 : :
19 : :
20 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
21 : : static inline void increase_allocated_bytes(struct z_heap *h, size_t num_bytes)
22 : : {
23 : : h->allocated_bytes += num_bytes;
24 : : h->max_allocated_bytes = max(h->max_allocated_bytes, h->allocated_bytes);
25 : : }
26 : : #endif
27 : :
28 : : #ifdef CONFIG_SYS_HEAP_CANARIES
29 : : #define HEAP_CANARY_MAGIC 0x5A6B7C8D9EAFB0C1ULL
30 : : #define HEAP_CANARY_POISON 0xDEADBEEFDEADBEEFULL
31 : :
32 : : /*
33 : : * Compute a per-chunk canary from its address and size. This is
34 : : * sufficient to detect accidental corruption but is not cryptographically
35 : : * secure — a determined attacker who knows the heap layout could forge
36 : : * a valid canary. A stronger scheme (e.g. SipHash with a random key)
37 : : * could replace this if needed.
38 : : */
39 : : static inline uint64_t compute_canary(struct z_heap *h, chunkid_t c)
40 : : {
41 : : uintptr_t addr = (uintptr_t)&chunk_buf(h)[c];
42 : : chunksz_t size = chunk_size(h, c);
43 : :
44 : : return (addr ^ size) ^ HEAP_CANARY_MAGIC;
45 : : }
46 : :
47 : : static inline void set_chunk_canary(struct z_heap *h, chunkid_t c)
48 : : {
49 : : chunk_trailer(h, c)->canary = compute_canary(h, c);
50 : : }
51 : :
52 : : static inline void verify_chunk_canary(struct z_heap *h, chunkid_t c, void *mem)
53 : : {
54 : : uint64_t expected = compute_canary(h, c);
55 : : uint64_t found = chunk_trailer(h, c)->canary;
56 : :
57 : : if (found != expected) {
58 : : if (found == HEAP_CANARY_POISON) {
59 : : LOG_ERR("heap canary: double free at %p", mem);
60 : : } else {
61 : : LOG_ERR("heap canary: corruption at %p", mem);
62 : : }
63 : : k_panic();
64 : : }
65 : : }
66 : :
67 : : static inline void poison_chunk_canary(struct z_heap *h, chunkid_t c)
68 : : {
69 : : chunk_trailer(h, c)->canary = HEAP_CANARY_POISON;
70 : : }
71 : : #else
72 : : #define set_chunk_canary(h, c) do { } while (false)
73 : : #define verify_chunk_canary(h, c, mem) do { } while (false)
74 : : #define poison_chunk_canary(h, c) do { } while (false)
75 : : #endif /* CONFIG_SYS_HEAP_CANARIES */
76 : :
77 : 0 : static void *chunk_mem(struct z_heap *h, chunkid_t c)
78 : : {
79 : 0 : chunk_unit_t *buf = chunk_buf(h);
80 : 0 : uint8_t *ret = ((uint8_t *)&buf[c]) + chunk_header_bytes(h);
81 : :
82 : 0 : CHECK(!(((uintptr_t)ret) & (big_heap(h) ? 7 : 3)));
83 : :
84 : 0 : return ret;
85 : : }
86 : :
87 : 0 : static void free_list_remove_bidx(struct z_heap *h, chunkid_t c, int bidx)
88 : : {
89 : 0 : struct z_heap_bucket *b = &h->buckets[bidx];
90 : :
91 : 0 : CHECK(b->next != 0);
92 : 0 : CHECK(h->avail_buckets & BIT(bidx));
93 : :
94 [ # # ]: 0 : if (next_free_chunk(h, c) == c) {
95 : : /* this is the last chunk */
96 : 0 : h->avail_buckets &= ~BIT(bidx);
97 : 0 : b->next = 0;
98 : : } else {
99 : 0 : chunkid_t first = prev_free_chunk(h, c),
100 : 0 : second = next_free_chunk(h, c);
101 : :
102 : 0 : if (SYS_HEAP_HARDENING_MODERATE &&
103 [ # # ]: 0 : (next_free_chunk(h, first) != c ||
104 [ # # ]: 0 : prev_free_chunk(h, second) != c)) {
105 : 0 : LOG_ERR("heap corruption (free list linkage)");
106 : 0 : k_panic();
107 : : }
108 : :
109 : 0 : b->next = second;
110 : 0 : set_next_free_chunk(h, first, second);
111 : 0 : set_prev_free_chunk(h, second, first);
112 : : }
113 : :
114 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
115 : : h->free_bytes -= chunk_usable_bytes(h, c);
116 : : #endif
117 : 0 : }
118 : :
119 : 0 : static void free_list_remove(struct z_heap *h, chunkid_t c)
120 : : {
121 [ # # ]: 0 : if (!undersized_chunk(h, c)) {
122 : 0 : int bidx = bucket_idx(h, chunk_size(h, c));
123 : 0 : free_list_remove_bidx(h, c, bidx);
124 : : }
125 : 0 : }
126 : :
127 : 0 : static void free_list_add_bidx(struct z_heap *h, chunkid_t c, int bidx)
128 : : {
129 : 0 : struct z_heap_bucket *b = &h->buckets[bidx];
130 : :
131 [ # # ]: 0 : if (b->next == 0U) {
132 : 0 : CHECK((h->avail_buckets & BIT(bidx)) == 0);
133 : :
134 : : /* Empty list, first item */
135 : 0 : h->avail_buckets |= BIT(bidx);
136 : 0 : b->next = c;
137 : 0 : set_prev_free_chunk(h, c, c);
138 : 0 : set_next_free_chunk(h, c, c);
139 : : } else {
140 : 0 : CHECK(h->avail_buckets & BIT(bidx));
141 : :
142 : : /* Insert before (!) the "next" pointer */
143 : 0 : chunkid_t second = b->next;
144 : 0 : chunkid_t first = prev_free_chunk(h, second);
145 : :
146 : 0 : if (SYS_HEAP_HARDENING_MODERATE &&
147 [ # # ]: 0 : next_free_chunk(h, first) != second) {
148 : 0 : LOG_ERR("heap corruption (free list linkage)");
149 : 0 : k_panic();
150 : : }
151 : :
152 : 0 : set_prev_free_chunk(h, c, first);
153 : 0 : set_next_free_chunk(h, c, second);
154 : 0 : set_next_free_chunk(h, first, c);
155 : 0 : set_prev_free_chunk(h, second, c);
156 : : }
157 : :
158 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
159 : : h->free_bytes += chunk_usable_bytes(h, c);
160 : : #endif
161 : 0 : }
162 : :
163 : 0 : static void free_list_add(struct z_heap *h, chunkid_t c)
164 : : {
165 [ # # ]: 0 : if (!undersized_chunk(h, c)) {
166 : 0 : int bidx = bucket_idx(h, chunk_size(h, c));
167 : 0 : free_list_add_bidx(h, c, bidx);
168 : : }
169 : 0 : }
170 : :
171 : : /*
172 : : * Validate a free chunk's structural integrity before trusting its
173 : : * header fields. Called before free list removal or merge operations.
174 : : * @left_trusted: true if the left neighbor was already validated by
175 : : * the caller (e.g. the chunk being freed), false if its canary
176 : : * should be verified to detect overflow into this free chunk.
177 : : */
178 : 0 : static void free_chunk_check(struct z_heap *h, chunkid_t c, bool left_trusted)
179 : : {
180 : 0 : if (SYS_HEAP_HARDENING_MODERATE &&
181 [ # # ]: 0 : (chunk_used(h, c) ||
182 [ # # ]: 0 : left_chunk(h, right_chunk(h, c)) != c ||
183 [ # # ]: 0 : right_chunk(h, left_chunk(h, c)) != c)) {
184 : 0 : LOG_ERR("heap corruption (free chunk linkage)");
185 : 0 : k_panic();
186 : : }
187 : :
188 : : /*
189 : : * Free chunks have no canary of their own, but their header
190 : : * can be corrupted by a buffer overflow from the used chunk
191 : : * to their left:
192 : : *
193 : : * [used_L] [data_L] [trailer_L] [hdr_F] [free...]
194 : : * overflow ------>
195 : : *
196 : : * Validating left's trailer canary before trusting hdr_F's
197 : : * metadata substitutes for a per-free-chunk canary: the
198 : : * overflow must corrupt trailer_L before reaching hdr_F.
199 : : */
200 : 0 : if (SYS_HEAP_HARDENING_FULL && !left_trusted) {
201 : 0 : verify_chunk_canary(h, left_chunk(h, c),
202 : : chunk_mem(h, left_chunk(h, c)));
203 : : }
204 : 0 : }
205 : :
206 : : /* Splits a chunk "lc" into a left chunk and a right chunk at "rc".
207 : : * Leaves both chunks marked "free"
208 : : */
209 : 0 : static void split_chunks(struct z_heap *h, chunkid_t lc, chunkid_t rc)
210 : : {
211 : 0 : CHECK(rc > lc);
212 : 0 : CHECK(rc - lc < chunk_size(h, lc));
213 : :
214 : 0 : chunksz_t sz0 = chunk_size(h, lc);
215 : 0 : chunksz_t lsz = rc - lc;
216 : 0 : chunksz_t rsz = sz0 - lsz;
217 : :
218 : 0 : set_chunk_size(h, lc, lsz);
219 : 0 : set_chunk_size(h, rc, rsz);
220 : 0 : set_left_chunk_size(h, rc, lsz);
221 : 0 : set_left_chunk_size(h, right_chunk(h, rc), rsz);
222 : 0 : }
223 : :
224 : : /* Does not modify free list */
225 : 0 : static void merge_chunks(struct z_heap *h, chunkid_t lc, chunkid_t rc)
226 : : {
227 : 0 : chunksz_t newsz = chunk_size(h, lc) + chunk_size(h, rc);
228 : :
229 : 0 : set_chunk_size(h, lc, newsz);
230 : 0 : set_left_chunk_size(h, right_chunk(h, rc), newsz);
231 : 0 : }
232 : :
233 : 0 : static void free_chunk(struct z_heap *h, chunkid_t c)
234 : : {
235 : 0 : chunkid_t rc = right_chunk(h, c);
236 : :
237 : : /* Merge with free right chunk? */
238 [ # # ]: 0 : if (!chunk_used(h, rc)) {
239 : 0 : free_chunk_check(h, rc, true);
240 : 0 : free_list_remove(h, rc);
241 : 0 : merge_chunks(h, c, rc);
242 : : }
243 : :
244 : 0 : chunkid_t lc = left_chunk(h, c);
245 : :
246 : : /* Merge with free left chunk? */
247 [ # # ]: 0 : if (!chunk_used(h, lc)) {
248 : 0 : free_chunk_check(h, lc, false);
249 : 0 : free_list_remove(h, lc);
250 : 0 : merge_chunks(h, lc, c);
251 : 0 : c = lc;
252 : : } else if (SYS_HEAP_HARDENING_FULL) {
253 : : /*
254 : : * Left neighbor is used. Verify its canary to detect
255 : : * an overflow from the left that corrupted our header
256 : : * (specifically LEFT_SIZE) without touching our trailer.
257 : : */
258 : 0 : verify_chunk_canary(h, lc, chunk_mem(h, lc));
259 : : }
260 : :
261 : 0 : free_list_add(h, c);
262 : 0 : }
263 : :
264 : : /*
265 : : * Return the closest chunk ID corresponding to given memory pointer.
266 : : * Here "closest" is only meaningful in the context of sys_heap_aligned_alloc()
267 : : * where wanted alignment might not always correspond to a chunk header
268 : : * boundary.
269 : : */
270 : 0 : static chunkid_t mem_to_chunkid(struct z_heap *h, void *p)
271 : : {
272 : 0 : uint8_t *mem = p, *base = (uint8_t *)chunk_buf(h);
273 : 0 : return (mem - chunk_header_bytes(h) - base) / CHUNK_UNIT;
274 : : }
275 : :
276 : 0 : void sys_heap_free(struct sys_heap *heap, void *mem)
277 : : {
278 [ # # ]: 0 : if (mem == NULL) {
279 : : return; /* ISO C free() semantics */
280 : : }
281 : 0 : struct z_heap *h = heap->heap;
282 : 0 : chunkid_t c = mem_to_chunkid(h, mem);
283 : :
284 [ # # ]: 0 : if (SYS_HEAP_HARDENING_BASIC && !chunk_used(h, c)) {
285 : 0 : LOG_ERR("heap corruption (double free?) at %p", mem);
286 : 0 : k_panic();
287 : : }
288 : :
289 : : /*
290 : : * Header fields are ordered as LEFT_SIZE then SIZE_AND_USED.
291 : : * This places SIZE_AND_USED immediately before the user data,
292 : : * and LEFT_SIZE of the following chunk immediately after:
293 : : *
294 : : * chunk c right_chunk(c)
295 : : * +-----------+---------+-----------+---------+
296 : : * | SIZE (1) | data | L_SIZE (2)| SIZE |
297 : : * +-----------+---------+-----------+---------+
298 : : *
299 : : * A buffer overflow from c's data corrupts field (2).
300 : : * Checking left(right(c)) == c catches this because
301 : : * right(c) reads field (1) and left() reads field (2):
302 : : * the two fields straddle the data buffer, so the
303 : : * round-trip fails if either side was corrupted.
304 : : */
305 : 0 : if (SYS_HEAP_HARDENING_BASIC &&
306 [ # # ]: 0 : left_chunk(h, right_chunk(h, c)) != c) {
307 : 0 : LOG_ERR("heap corruption (buffer overflow?) at %p", mem);
308 : 0 : k_panic();
309 : : }
310 : :
311 : : /*
312 : : * The above check validated SIZE_AND_USED using a field from
313 : : * the next chunk. Now validate LEFT_SIZE: if it was corrupted
314 : : * (by an overflow from the left neighbor or an underflow from
315 : : * our own buffer) then right(left(c)) won't return to c.
316 : : */
317 : 0 : if (SYS_HEAP_HARDENING_MODERATE &&
318 [ # # ]: 0 : right_chunk(h, left_chunk(h, c)) != c) {
319 : 0 : LOG_ERR("heap corruption (left neighbor?) at %p", mem);
320 : 0 : k_panic();
321 : : }
322 : :
323 : 0 : if (SYS_HEAP_HARDENING_FULL) {
324 : 0 : verify_chunk_canary(h, c, mem);
325 : 0 : poison_chunk_canary(h, c);
326 : : }
327 : :
328 : 0 : if (SYS_HEAP_HARDENING_EXTREME && !z_heap_full_check(h)) {
329 : : LOG_ERR("heap validation failed");
330 : 0 : k_panic();
331 : : }
332 : :
333 : 0 : set_chunk_used(h, c, false);
334 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
335 : : h->allocated_bytes -= chunk_usable_bytes(h, c);
336 : : #endif
337 : :
338 : : #ifdef CONFIG_SYS_HEAP_LISTENER
339 : : heap_listener_notify_free(HEAP_ID_FROM_POINTER(heap), mem,
340 : : chunk_usable_bytes(h, c) - mem_align_gap(h, mem));
341 : : #endif
342 : :
343 : 0 : free_chunk(h, c);
344 : : }
345 : :
346 : 0 : size_t sys_heap_usable_size(struct sys_heap *heap, void *mem)
347 : : {
348 : 0 : struct z_heap *h = heap->heap;
349 : 0 : chunkid_t c = mem_to_chunkid(h, mem);
350 : :
351 : 0 : if (SYS_HEAP_HARDENING_FULL) {
352 : 0 : verify_chunk_canary(h, c, mem);
353 : : }
354 : :
355 : 0 : return chunk_usable_bytes(h, c) - mem_align_gap(h, mem);
356 : : }
357 : :
358 : 0 : static chunkid_t alloc_chunk(struct z_heap *h, chunksz_t sz)
359 : : {
360 : 0 : if (SYS_HEAP_HARDENING_EXTREME && !z_heap_full_check(h)) {
361 : : LOG_ERR("heap validation failed");
362 : 0 : k_panic();
363 : : }
364 : :
365 : 0 : int bi = bucket_idx(h, sz);
366 : 0 : struct z_heap_bucket *b = &h->buckets[bi];
367 : :
368 : 0 : CHECK(bi <= bucket_idx(h, h->end_chunk));
369 : :
370 : : /* First try a bounded count of items from the minimal bucket
371 : : * size. These may not fit, trying (e.g.) three means that
372 : : * (assuming that chunk sizes are evenly distributed[1]) we
373 : : * have a 7/8 chance of finding a match, thus keeping the
374 : : * number of such blocks consumed by allocation higher than
375 : : * the number of smaller blocks created by fragmenting larger
376 : : * ones.
377 : : *
378 : : * [1] In practice, they are never evenly distributed, of
379 : : * course. But even in pathological situations we still
380 : : * maintain our constant time performance and at worst see
381 : : * fragmentation waste of the order of the block allocated
382 : : * only.
383 : : */
384 [ # # ]: 0 : if (b->next != 0U) {
385 : : chunkid_t first = b->next;
386 : : int i = CONFIG_SYS_HEAP_ALLOC_LOOPS;
387 : 0 : do {
388 : 0 : chunkid_t c = b->next;
389 [ # # ]: 0 : if (chunk_size(h, c) >= sz) {
390 : 0 : free_chunk_check(h, c, false);
391 : 0 : free_list_remove_bidx(h, c, bi);
392 : 0 : return c;
393 : : }
394 : 0 : b->next = next_free_chunk(h, c);
395 : 0 : CHECK(b->next != 0);
396 [ # # # # ]: 0 : } while (--i && b->next != first);
397 : : }
398 : :
399 : : /* Otherwise pick the smallest non-empty bucket guaranteed to
400 : : * fit and use that unconditionally.
401 : : */
402 : 0 : uint32_t bmask = h->avail_buckets & ~BIT_MASK(bi + 1);
403 : :
404 [ # # ]: 0 : if (bmask != 0U) {
405 : 0 : int minbucket = __builtin_ctz(bmask);
406 : 0 : chunkid_t c = h->buckets[minbucket].next;
407 : :
408 : 0 : free_chunk_check(h, c, false);
409 : 0 : free_list_remove_bidx(h, c, minbucket);
410 : 0 : CHECK(chunk_size(h, c) >= sz);
411 : 0 : return c;
412 : : }
413 : :
414 : : return 0;
415 : : }
416 : :
417 : 0 : void *sys_heap_alloc(struct sys_heap *heap, size_t bytes)
418 : : {
419 : 0 : struct z_heap *h = heap->heap;
420 : 0 : void *mem;
421 : :
422 [ # # ]: 0 : if (bytes == 0U) {
423 : : return NULL;
424 : : }
425 : :
426 : 0 : chunksz_t chunk_sz = bytes_to_chunksz(h, bytes, 0);
427 : 0 : chunkid_t c = alloc_chunk(h, chunk_sz);
428 : :
429 [ # # ]: 0 : if (c == 0U) {
430 : : return NULL;
431 : : }
432 : :
433 : : /* Split off remainder if any */
434 [ # # ]: 0 : if (chunk_size(h, c) > chunk_sz) {
435 : 0 : split_chunks(h, c, c + chunk_sz);
436 : 0 : free_list_add(h, c + chunk_sz);
437 : : }
438 : :
439 : 0 : set_chunk_used(h, c, true);
440 : 0 : if (SYS_HEAP_HARDENING_FULL) {
441 : 0 : set_chunk_canary(h, c);
442 : : }
443 : :
444 : 0 : mem = chunk_mem(h, c);
445 : :
446 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
447 : : increase_allocated_bytes(h, chunk_usable_bytes(h, c));
448 : : #endif
449 : :
450 : : #ifdef CONFIG_SYS_HEAP_LISTENER
451 : : heap_listener_notify_alloc(HEAP_ID_FROM_POINTER(heap), mem,
452 : : chunk_usable_bytes(h, c));
453 : : #endif
454 : :
455 : 0 : IF_ENABLED(CONFIG_MSAN, (__msan_allocated_memory(mem, bytes)));
456 : 0 : return mem;
457 : : }
458 : :
459 : 0 : void *sys_heap_noalign_alloc(struct sys_heap *heap, size_t align, size_t bytes)
460 : : {
461 : 0 : ARG_UNUSED(align);
462 : :
463 : 0 : return sys_heap_alloc(heap, bytes);
464 : : }
465 : :
466 : 0 : void *sys_heap_aligned_alloc(struct sys_heap *heap, size_t align, size_t bytes)
467 : : {
468 : 0 : struct z_heap *h = heap->heap;
469 : 0 : size_t gap, rew;
470 : :
471 : : /*
472 : : * Split align and rewind values (if any).
473 : : * We allow for one bit of rewind in addition to the alignment
474 : : * value to efficiently accommodate z_alloc_helper().
475 : : * So if e.g. align = 0x28 (32 | 8) this means we align to a 32-byte
476 : : * boundary and then rewind 8 bytes.
477 : : */
478 : 0 : rew = align & -align;
479 [ # # ]: 0 : if (align != rew) {
480 : 0 : align -= rew;
481 : 0 : gap = min(rew, chunk_header_bytes(h));
482 : : } else {
483 [ # # ]: 0 : if (align <= chunk_header_bytes(h)) {
484 : 0 : return sys_heap_alloc(heap, bytes);
485 : : }
486 : : rew = 0;
487 : : gap = chunk_header_bytes(h);
488 : : }
489 [ # # ]: 0 : __ASSERT((align & (align - 1)) == 0, "align must be a power of 2");
490 : :
491 [ # # ]: 0 : if (bytes == 0) {
492 : : return NULL;
493 : : }
494 : :
495 : : /*
496 : : * Find a free block that is guaranteed to fit.
497 : : * We over-allocate to account for alignment and then free
498 : : * the extra allocations afterwards.
499 : : */
500 : 0 : chunksz_t padded_sz = bytes_to_chunksz(h, bytes, align - gap);
501 : 0 : chunkid_t c0 = alloc_chunk(h, padded_sz);
502 : :
503 [ # # ]: 0 : if (c0 == 0) {
504 : : return NULL;
505 : : }
506 : 0 : uint8_t *mem = chunk_mem(h, c0);
507 : :
508 : : /* Align allocated memory */
509 : 0 : mem = (uint8_t *) ROUND_UP(mem + rew, align) - rew;
510 : 0 : chunk_unit_t *end = (chunk_unit_t *) ROUND_UP(mem + bytes, CHUNK_UNIT);
511 : :
512 : : /* Get corresponding chunks */
513 : 0 : chunkid_t c = mem_to_chunkid(h, mem);
514 : 0 : chunkid_t c_end = end - chunk_buf(h) + CHUNK_TRAILER_SIZE;
515 : 0 : CHECK(c >= c0 && c < c_end && c_end <= c0 + padded_sz);
516 : :
517 : : /* Split and free unused prefix */
518 [ # # ]: 0 : if (c > c0) {
519 : 0 : split_chunks(h, c0, c);
520 : 0 : free_list_add(h, c0);
521 : : }
522 : :
523 : : /* Split and free unused suffix */
524 [ # # ]: 0 : if (right_chunk(h, c) > c_end) {
525 : 0 : split_chunks(h, c, c_end);
526 : 0 : free_list_add(h, c_end);
527 : : }
528 : :
529 : 0 : set_chunk_used(h, c, true);
530 : 0 : if (SYS_HEAP_HARDENING_FULL) {
531 : 0 : set_chunk_canary(h, c);
532 : : }
533 : :
534 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
535 : : increase_allocated_bytes(h, chunk_usable_bytes(h, c));
536 : : #endif
537 : :
538 : : #ifdef CONFIG_SYS_HEAP_LISTENER
539 : : heap_listener_notify_alloc(HEAP_ID_FROM_POINTER(heap), mem,
540 : : chunk_usable_bytes(h, c) - mem_align_gap(h, mem));
541 : : #endif
542 : :
543 : 0 : IF_ENABLED(CONFIG_MSAN, (__msan_allocated_memory(mem, bytes)));
544 : 0 : return mem;
545 : : }
546 : :
547 : 0 : static bool inplace_realloc(struct sys_heap *heap, void *ptr, size_t bytes)
548 : : {
549 : 0 : struct z_heap *h = heap->heap;
550 : :
551 : 0 : chunkid_t c = mem_to_chunkid(h, ptr);
552 : 0 : size_t align_gap = mem_align_gap(h, ptr);
553 : :
554 : 0 : chunksz_t chunks_need = bytes_to_chunksz(h, bytes, align_gap);
555 : :
556 [ # # ]: 0 : if (SYS_HEAP_HARDENING_BASIC && !chunk_used(h, c)) {
557 : 0 : LOG_ERR("heap corruption (not in use?) at %p", ptr);
558 : 0 : k_panic();
559 : : }
560 : 0 : if (SYS_HEAP_HARDENING_BASIC &&
561 [ # # ]: 0 : left_chunk(h, right_chunk(h, c)) != c) {
562 : 0 : LOG_ERR("heap corruption (buffer overflow?) at %p", ptr);
563 : 0 : k_panic();
564 : : }
565 : 0 : if (SYS_HEAP_HARDENING_MODERATE &&
566 [ # # ]: 0 : right_chunk(h, left_chunk(h, c)) != c) {
567 : 0 : LOG_ERR("heap corruption (left neighbor?) at %p", ptr);
568 : 0 : k_panic();
569 : : }
570 : 0 : if (SYS_HEAP_HARDENING_FULL) {
571 : 0 : verify_chunk_canary(h, c, ptr);
572 : : }
573 : 0 : if (SYS_HEAP_HARDENING_EXTREME && !z_heap_full_check(h)) {
574 : : LOG_ERR("heap validation failed");
575 : 0 : k_panic();
576 : : }
577 : :
578 [ # # ]: 0 : if (chunk_size(h, c) == chunks_need) {
579 : : /* We're good already */
580 : : return true;
581 : : }
582 : :
583 [ # # ]: 0 : if (chunk_size(h, c) > chunks_need) {
584 : : /* Shrink in place, split off and free unused suffix */
585 : : #ifdef CONFIG_SYS_HEAP_LISTENER
586 : : size_t bytes_freed = chunk_usable_bytes(h, c) - align_gap;
587 : : #endif
588 : :
589 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
590 : : h->allocated_bytes -=
591 : : (chunk_size(h, c) - chunks_need) * CHUNK_UNIT;
592 : : #endif
593 : :
594 : 0 : split_chunks(h, c, c + chunks_need);
595 : 0 : set_chunk_used(h, c, true);
596 : 0 : if (SYS_HEAP_HARDENING_FULL) {
597 : 0 : set_chunk_canary(h, c);
598 : : }
599 : :
600 : : /* Left neighbor is c (used, just validated) so only
601 : : * attempt a right merge inline and add to free list.
602 : : */
603 : 0 : chunkid_t suffix = c + chunks_need;
604 : 0 : chunkid_t suffix_rc = right_chunk(h, suffix);
605 : :
606 [ # # ]: 0 : if (!chunk_used(h, suffix_rc)) {
607 : 0 : free_chunk_check(h, suffix_rc, true);
608 : 0 : free_list_remove(h, suffix_rc);
609 : 0 : merge_chunks(h, suffix, suffix_rc);
610 : : }
611 : 0 : free_list_add(h, suffix);
612 : :
613 : : #ifdef CONFIG_SYS_HEAP_LISTENER
614 : : heap_listener_notify_alloc(HEAP_ID_FROM_POINTER(heap), ptr,
615 : : chunk_usable_bytes(h, c) - align_gap);
616 : : heap_listener_notify_free(HEAP_ID_FROM_POINTER(heap), ptr,
617 : : bytes_freed);
618 : : #endif
619 : :
620 : 0 : return true;
621 : : }
622 : :
623 : 0 : chunkid_t rc = right_chunk(h, c);
624 : :
625 [ # # ]: 0 : if (!chunk_used(h, rc) &&
626 [ # # ]: 0 : (chunk_size(h, c) + chunk_size(h, rc) >= chunks_need)) {
627 : : /* Expand: split the right chunk and append */
628 : 0 : chunksz_t split_size = chunks_need - chunk_size(h, c);
629 : :
630 : : #ifdef CONFIG_SYS_HEAP_LISTENER
631 : : size_t bytes_freed = chunk_usable_bytes(h, c) - align_gap;
632 : : #endif
633 : :
634 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
635 : : increase_allocated_bytes(h, split_size * CHUNK_UNIT);
636 : : #endif
637 : :
638 : 0 : free_chunk_check(h, rc, true);
639 : 0 : free_list_remove(h, rc);
640 : :
641 [ # # ]: 0 : if (split_size < chunk_size(h, rc)) {
642 : 0 : split_chunks(h, rc, rc + split_size);
643 : 0 : free_list_add(h, rc + split_size);
644 : : }
645 : :
646 : 0 : merge_chunks(h, c, rc);
647 : 0 : set_chunk_used(h, c, true);
648 : 0 : if (SYS_HEAP_HARDENING_FULL) {
649 : 0 : set_chunk_canary(h, c);
650 : : }
651 : :
652 : : #ifdef CONFIG_SYS_HEAP_LISTENER
653 : : heap_listener_notify_alloc(HEAP_ID_FROM_POINTER(heap), ptr,
654 : : chunk_usable_bytes(h, c) - align_gap);
655 : : heap_listener_notify_free(HEAP_ID_FROM_POINTER(heap), ptr,
656 : : bytes_freed);
657 : : #endif
658 : :
659 : 0 : return true;
660 : : }
661 : :
662 : : return false;
663 : : }
664 : :
665 : 0 : void *sys_heap_realloc(struct sys_heap *heap, void *ptr, size_t bytes)
666 : : {
667 : : /* special realloc semantics */
668 [ # # ]: 0 : if (ptr == NULL) {
669 : 0 : return sys_heap_alloc(heap, bytes);
670 : : }
671 [ # # ]: 0 : if (bytes == 0) {
672 : 0 : sys_heap_free(heap, ptr);
673 : 0 : return NULL;
674 : : }
675 : :
676 [ # # ]: 0 : if (inplace_realloc(heap, ptr, bytes)) {
677 : : return ptr;
678 : : }
679 : :
680 : : /* In-place realloc was not possible: fallback to allocate and copy. */
681 : 0 : void *ptr2 = sys_heap_alloc(heap, bytes);
682 : :
683 [ # # ]: 0 : if (ptr2 != NULL) {
684 : 0 : size_t prev_size = sys_heap_usable_size(heap, ptr);
685 : :
686 : 0 : memcpy(ptr2, ptr, min(prev_size, bytes));
687 : 0 : sys_heap_free(heap, ptr);
688 : : }
689 : : return ptr2;
690 : : }
691 : :
692 : 0 : void *sys_heap_aligned_realloc(struct sys_heap *heap, void *ptr,
693 : : size_t align, size_t bytes)
694 : : {
695 : : /* special realloc semantics */
696 [ # # ]: 0 : if (ptr == NULL) {
697 : 0 : return sys_heap_aligned_alloc(heap, align, bytes);
698 : : }
699 [ # # ]: 0 : if (bytes == 0) {
700 : 0 : sys_heap_free(heap, ptr);
701 : 0 : return NULL;
702 : : }
703 : :
704 [ # # ]: 0 : __ASSERT((align & (align - 1)) == 0, "align must be a power of 2");
705 : :
706 [ # # # # : 0 : if ((align == 0 || ((uintptr_t)ptr & (align - 1)) == 0) &&
# # ]
707 : 0 : inplace_realloc(heap, ptr, bytes)) {
708 : : return ptr;
709 : : }
710 : :
711 : : /*
712 : : * Either ptr is not sufficiently aligned for in-place realloc or
713 : : * in-place realloc was not possible: fallback to allocate and copy.
714 : : */
715 : 0 : void *ptr2 = sys_heap_aligned_alloc(heap, align, bytes);
716 : :
717 [ # # ]: 0 : if (ptr2 != NULL) {
718 : 0 : size_t prev_size = sys_heap_usable_size(heap, ptr);
719 : :
720 : 0 : memcpy(ptr2, ptr, min(prev_size, bytes));
721 : 0 : sys_heap_free(heap, ptr);
722 : : }
723 : : return ptr2;
724 : : }
725 : :
726 : 0 : void sys_heap_init(struct sys_heap *heap, void *mem, size_t bytes)
727 : : {
728 : 0 : IF_ENABLED(CONFIG_MSAN, (__sanitizer_dtor_callback(mem, bytes)));
729 : :
730 : 0 : if (IS_ENABLED(CONFIG_SYS_HEAP_SMALL_ONLY)) {
731 : : /* Must fit in a 15 bit count of HUNK_UNIT */
732 [ # # ]: 0 : __ASSERT(bytes / CHUNK_UNIT <= 0x7fffU, "heap size is too big");
733 : : } else {
734 : : /* Must fit in a 31 bit count of HUNK_UNIT */
735 : 0 : __ASSERT(bytes / CHUNK_UNIT <= 0x7fffffffU, "heap size is too big");
736 : : }
737 : :
738 : : /* Reserve the end marker chunk's header */
739 [ # # ]: 0 : __ASSERT(bytes > heap_footer_bytes(bytes), "heap size is too small");
740 : 0 : bytes -= heap_footer_bytes(bytes);
741 : :
742 : : /* Round the start up, the end down */
743 : 0 : uintptr_t addr = ROUND_UP(mem, CHUNK_UNIT);
744 : 0 : uintptr_t end = ROUND_DOWN((uint8_t *)mem + bytes, CHUNK_UNIT);
745 : 0 : chunksz_t heap_sz = (end - addr) / CHUNK_UNIT;
746 : :
747 : 0 : CHECK(end > addr);
748 [ # # ]: 0 : __ASSERT(heap_sz > chunksz(sizeof(struct z_heap)), "heap size is too small");
749 : :
750 : 0 : struct z_heap *h = (struct z_heap *)addr;
751 : 0 : heap->heap = h;
752 : 0 : h->end_chunk = heap_sz;
753 : 0 : h->avail_buckets = 0;
754 : :
755 : : #ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
756 : : h->free_bytes = 0;
757 : : h->allocated_bytes = 0;
758 : : h->max_allocated_bytes = 0;
759 : : #endif
760 : :
761 : : #if CONFIG_SYS_HEAP_ARRAY_SIZE
762 : : sys_heap_array_save(heap);
763 : : #endif
764 : :
765 : 0 : int nb_buckets = bucket_idx(h, heap_sz) + 1;
766 : 0 : chunksz_t chunk0_size = chunksz(sizeof(struct z_heap) +
767 : 0 : nb_buckets * sizeof(struct z_heap_bucket)) +
768 : : CHUNK_TRAILER_SIZE;
769 : :
770 [ # # ]: 0 : __ASSERT(chunk0_size + min_chunk_size(h) <= heap_sz, "heap size is too small");
771 : :
772 [ # # ]: 0 : for (int i = 0; i < nb_buckets; i++) {
773 : 0 : h->buckets[i].next = 0;
774 : : }
775 : :
776 : : /* chunk containing our struct z_heap */
777 : 0 : set_chunk_size(h, 0, chunk0_size);
778 : 0 : set_left_chunk_size(h, 0, 0);
779 : 0 : set_chunk_used(h, 0, true);
780 : 0 : if (SYS_HEAP_HARDENING_FULL) {
781 : 0 : set_chunk_canary(h, 0);
782 : : }
783 : :
784 : : /* chunk containing the free heap */
785 : 0 : set_chunk_size(h, chunk0_size, heap_sz - chunk0_size);
786 : 0 : set_left_chunk_size(h, chunk0_size, chunk0_size);
787 : :
788 : : /* the end marker chunk */
789 : 0 : set_chunk_size(h, heap_sz, 0);
790 : 0 : set_left_chunk_size(h, heap_sz, heap_sz - chunk0_size);
791 : 0 : set_chunk_used(h, heap_sz, true);
792 : :
793 : 0 : free_list_add(h, chunk0_size);
794 : 0 : }
|
