Embedded SDK
Embedded SDK
Loading...
Searching...
No Matches
mem_alloc.c
Go to the documentation of this file.
1
5
6/*********************
7 * INCLUDES
8 *********************/
9#include <stdio.h>
10#include <string.h>
11#include "exceptions.h"
12#include "errors.h"
13#include "os_helpers.h"
14#include "os_math.h"
15#include "os_print.h"
16#include "os_utils.h"
17#include "mem_alloc.h"
18
19/*********************
20 * DEFINES
21 *********************/
22// Alignment for payload data size
23#define PAYLOAD_ALIGNEMENT 4
24// Alignment for returned payload
25#define PAYLOAD_DATA_ALIGNEMENT 8
26// sizeof of header for a allocated chunk
27#define ALLOC_CHUNK_HEADER_SIZE 4
28// sizeof of header for a free chunk
29#define FREE_CHUNK_HEADER_SIZE 8
30// maximum block size storable in the 15-bit header size field
31#define MAX_BLOCK_SIZE 0x7FFF
32// size of heap header
33#define HEAP_HEADER_SIZE \
34 ((sizeof(heap_t) + PAYLOAD_DATA_ALIGNEMENT - 1) & ~(PAYLOAD_DATA_ALIGNEMENT - 1))
35
36// number of 2^N segments aggregated as linear
37#define NB_LINEAR_SEGMENTS 5
38// 10 segments (the first one is linear) enable using up to ~32k bytes chunks, which is more than
39// enough
40/* Segregated free list bucket sizes:
41- 0: 1-63 bytes
42- 1: 64-127 bytes
43- 2: 128-255 bytes
44- 4: 512-1023 bytes
45- 6: 2048-4095 bytes
46- 7: 4096-8191 bytes
47- n: 2^(n+5)-(2^(n+6)-1) bytes
48- 9: 16384-32767 bytes
49*/
50#define NB_MAX_SEGMENTS 10
51// 4 sub-segments to have a better segregation of each segments
52#define NB_SUB_SEGMENTS 4
53
54// index is basically the offset in u64 from beginning of full heap buffer
55#define GET_PTR(_heap, index) ((header_t *) (((uint8_t *) _heap) + ((index) << 3)))
56#define GET_IDX(_heap, _ptr) ((((uint8_t *) (_ptr)) - ((uint8_t *) _heap)) >> 3)
57
58#define GET_SEGMENT(_size) MAX(NB_LINEAR_SEGMENTS, (31 - __builtin_clz(size)))
59
60// Under AddressSanitizer, the bytes of a chunk its caller does not own are poisoned, so an
61// overflow into a neighbouring chunk or a use after free is reported. Only the size/phys_prev
62// header word stays addressable; free-list links are unpoisoned just for the allocator's accesses.
63#if defined(__has_feature)
64#if __has_feature(address_sanitizer)
65#define MEM_ALLOC_ASAN
66#endif
67#endif
68#if defined(__SANITIZE_ADDRESS__) && !defined(MEM_ALLOC_ASAN)
69#define MEM_ALLOC_ASAN
70#endif
71
72#ifdef MEM_ALLOC_ASAN
73#include <sanitizer/asan_interface.h>
74#define MEM_POISON(_addr, _size) ASAN_POISON_MEMORY_REGION((_addr), (_size))
75#define MEM_UNPOISON(_addr, _size) ASAN_UNPOISON_MEMORY_REGION((_addr), (_size))
76#else
77#define MEM_POISON(_addr, _size) ((void) (_addr), (void) (_size))
78#define MEM_UNPOISON(_addr, _size) ((void) (_addr), (void) (_size))
79#endif
80
81// Fuzzing builds reserve a poisoned gap after every allocation, so an overflow is caught even on
82// an exact fit. Other builds keep the exact chunk geometry.
83#if defined(MEM_ALLOC_ASAN) && defined(FUZZING)
84#define MEM_REDZONE_SIZE 8
85#else
86#define MEM_REDZONE_SIZE 0
87#endif
88
89// free-list links of a free chunk, overlapping the first payload bytes
90#define LINKS_ADDR(_ptr) (((uint8_t *) (_ptr)) + ALLOC_CHUNK_HEADER_SIZE)
91#define LINKS_SIZE (FREE_CHUNK_HEADER_SIZE - ALLOC_CHUNK_HEADER_SIZE)
92#define LINKS_UNPOISON(_ptr) MEM_UNPOISON(LINKS_ADDR(_ptr), LINKS_SIZE)
93#define LINKS_POISON(_ptr) MEM_POISON(LINKS_ADDR(_ptr), LINKS_SIZE)
94
95/**********************
96 * TYPEDEFS
97 **********************/
98typedef struct header_s {
99 uint16_t size : 15; // the biggest size is 0x7FFF = 0x32767
100 uint16_t allocated : 1;
101
102 uint16_t phys_prev;
103
104 uint16_t fprev;
105 uint16_t fnext;
107
108typedef struct {
109 void *end;
110 size_t nb_segs;
112} heap_t;
113
114/**********************
115 * STATIC VARIABLES
116 **********************/
117
118/**********************
119 * STATIC PROTOTYPES
120 **********************/
121
122/**********************
123 * LOCAL FUNCTIONS
124 **********************/
125static inline size_t align_alloc_size(size_t size)
126{
127 // Add alignment - 1 to prepare for rounding up if needed
128 // This trick ensures already aligned sizes are not changed
129 size += PAYLOAD_ALIGNEMENT - 1;
130 // Mask off lower bits to align size down to nearest alignment boundary
131 size &= ~(PAYLOAD_ALIGNEMENT - 1);
132 // Either add 4 bytes (if size is 8N+4) or 8 bytes (if size is 8N) so the full
133 // 8-byte header structure fits while preserving alignment.
136 return size;
137}
138
139// This function returns the index into the array segregated explicit free lists
140// corresponding to the given size.
141// For 2^n <= size < 2^(n+1), this function returns n.
142static inline int seglist_index(heap_t *heap, size_t size)
143{
144 size_t seg;
145 uint8_t sub_segment;
146
147 seg = GET_SEGMENT(size);
148 if (seg == NB_LINEAR_SEGMENTS) {
149 // for the aggregated segment, the sub-segmant size is 1/NB_SUB_SEGMENTS of the size of the
150 // segment
151 sub_segment = (size >> (seg - 1)) & 0x3;
152 }
153 else {
154 // sub segment size is 1/(NB_SUB_SEGMENTS*2) of the size of the segment
155 sub_segment = (size >> (seg - 2)) & 0x3;
156 }
157 // from size in [0 : 63[, segment is 0 to 5 but is forced to 0
158 // from size in [2^6 : 2^13[, segment is [6 : 12] but is forced to [1 : 7]
159 seg -= NB_LINEAR_SEGMENTS;
160 // check consistency
161 if (seg >= heap->nb_segs) {
162 return -1;
163 }
164 return seg * NB_SUB_SEGMENTS + sub_segment;
165}
166
167// This function returns the index into the array segregated explicit free lists
168// corresponding to the given size, being sure to be big enough (so rounded to next sub-segment).
169static inline int seglist_index_up(heap_t *heap, size_t size)
170{
171 size_t seg;
172 uint8_t sub_segment;
173 size_t sub_segment_size;
174
175 seg = GET_SEGMENT(size);
176 if (seg == NB_LINEAR_SEGMENTS) {
177 // for the aggregated segment, the sub-segmant size is 1/NB_SUB_SEGMENTS of the size of the
178 // segment
179 sub_segment_size = (1 << (seg - 1));
180 }
181 else {
182 // sub segment size is 1/(NB_SUB_SEGMENTS*2) of the size of the segment
183 sub_segment_size = (1 << (seg - 2));
184 }
185
186 // round size to next sub-segment
187 size += sub_segment_size - 1;
188 size &= ~(sub_segment_size - 1);
189
190 seg = GET_SEGMENT(size);
191 if (seg == NB_LINEAR_SEGMENTS) {
192 // for the aggregated segment, the sub-segmant size is 1/NB_SUB_SEGMENTS of the size of the
193 // segment
194 sub_segment = (size >> (seg - 1)) & 0x3;
195 }
196 else {
197 // sub segment size is 1/(NB_SUB_SEGMENTS*2) of the size of the segment
198 sub_segment = (size >> (seg - 2)) & 0x3;
199 }
200
201 // from size in [0 : 63[, segment is 0 to 5 but is forced to 0
202 // from size in [2^6 : 2^13[, segment is [6 : 12] but is forced to [1 : 7]
203 seg -= NB_LINEAR_SEGMENTS;
204
205 // check consistency
206 if (seg >= heap->nb_segs) {
207 return -1;
208 }
209 return seg * NB_SUB_SEGMENTS + sub_segment;
210}
211
212static inline void set_fprev(header_t *header, uint16_t fprev)
213{
214 LINKS_UNPOISON(header);
215 header->fprev = fprev;
216 LINKS_POISON(header);
217}
218
219static inline void set_fnext(header_t *header, uint16_t fnext)
220{
221 LINKS_UNPOISON(header);
222 header->fnext = fnext;
223 LINKS_POISON(header);
224}
225
226// remove item from linked list
227static inline void list_remove(heap_t *heap, uint16_t *first_free, uint16_t elem)
228{
229 header_t *elem_ptr = GET_PTR(heap, elem);
230 LINKS_UNPOISON(elem_ptr);
231 uint16_t fprev = elem_ptr->fprev;
232 uint16_t fnext = elem_ptr->fnext;
233 LINKS_POISON(elem_ptr);
234 // if was the first, set a new first
235 if (*first_free == elem) {
236 *first_free = fnext;
237 // if the current first was not alone
238 if (*first_free) {
239 set_fprev(GET_PTR(heap, *first_free), 0);
240 }
241 return;
242 }
243 // link previous to following, if existing previous
244 if (fprev) {
245 set_fnext(GET_PTR(heap, fprev), fnext);
246 }
247 // link following to previous, if existing following
248 if (fnext) {
249 set_fprev(GET_PTR(heap, fnext), fprev);
250 }
251}
252
253// add item in LIFO
254static inline void list_push(heap_t *heap, header_t *header)
255{
256 int seg_index = seglist_index(heap, header->size);
257 if (seg_index < 0) {
258 return;
259 }
260 uint16_t first_idx = heap->free_segments[seg_index];
261 // if it's already the first item, nothing to do
262 if (first_idx == GET_IDX(heap, header)) {
263 return;
264 }
265 // link this new first to following (previous first)
266 LINKS_UNPOISON(header);
267 header->fnext = first_idx;
268 header->fprev = 0;
269 LINKS_POISON(header);
270 header->allocated = 0;
271 // link following (previous first) to new first
272 if (first_idx != 0) {
273 set_fprev(GET_PTR(heap, first_idx), GET_IDX(heap, header));
274 }
275 // replace new first
276 heap->free_segments[seg_index] = GET_IDX(heap, header);
277}
278
279// ensure the chunk is valid
280static inline void ensure_chunk_valid(heap_t *heap, header_t *header)
281{
282 uint8_t *block = (uint8_t *) header;
283 // ensure size is valid (multiple of pointers) and minimal size of 4 pointers)
284 if ((header->size & (PAYLOAD_ALIGNEMENT - 1)) || (header->size < FREE_CHUNK_HEADER_SIZE)
285 || ((block + header->size) > (uint8_t *) heap->end)) {
286 PRINTF("invalid size: header->size = %d!\n", header->size);
287 THROW(EXCEPTION_CORRUPT);
288 }
289 // ensure phys_prev is valid
290 if (header->phys_prev != 0) {
291 header_t *prev = GET_PTR(heap, header->phys_prev);
292 block = (uint8_t *) heap;
293 if (((uint8_t *) prev < &block[HEAP_HEADER_SIZE]) || ((void *) prev > heap->end)) {
294 PRINTF("corrupted prev_chunk\n");
295 THROW(EXCEPTION_CORRUPT);
296 }
297 // ensure that next of prev is current
298 if ((((uint8_t *) prev) + prev->size) != (uint8_t *) header) {
299 PRINTF("corrupted prev_chunk\n");
300 THROW(EXCEPTION_CORRUPT);
301 }
302 }
303}
304
305// coalesce the two given chunks
306static header_t *coalesce(heap_t *heap, header_t *header, header_t *neighbour)
307{
308 uint16_t neighbour_idx = GET_IDX(heap, neighbour);
309 ensure_chunk_valid(heap, neighbour);
310
311 // if not allocated, coalesce
312 if (!neighbour->allocated) {
313 int seg_index = seglist_index(heap, neighbour->size);
314 // remove this neighbour from its free list
315 if (seg_index >= 0) {
316 list_remove(heap, &heap->free_segments[seg_index], neighbour_idx);
317 }
318 // link the current next physical chunk (if existing) to this new chunk
319 header_t *next;
320 if (header < neighbour) {
321 next = (header_t *) (((uint8_t *) neighbour) + neighbour->size);
322 if ((void *) next < heap->end) {
323 next->phys_prev = GET_IDX(heap, header);
324 }
325 header->size += neighbour->size;
326 // clean-up neighbour to avoid leaking
327 LINKS_UNPOISON(neighbour);
328 memset(neighbour, 0, sizeof(*neighbour));
329 }
330 else {
331 next = (header_t *) (((uint8_t *) header) + header->size);
332 // ensure next is valid (inside the heap buffer) before linking it
333 if ((void *) next < heap->end) {
334 next->phys_prev = neighbour_idx;
335 }
336 neighbour->size += header->size;
337 // clean-up header to avoid leaking
338 memset(header, 0, sizeof(*header));
339 // header points now to neighbour
340 header = neighbour;
341 }
342 }
343 return header;
344}
345
346static bool parse_callback(void *data, uint8_t *addr, bool allocated, size_t size)
347{
348 mem_stat_t *stat = (mem_stat_t *) data;
349
350 UNUSED(addr);
351 // error reached
352 if (size == 0) {
353 return true;
354 }
355 stat->nb_chunks++;
356 if (allocated) {
357 stat->nb_allocated++;
358 stat->allocated_size += size;
359 }
360 else {
361 stat->free_size += size;
362 }
363 stat->total_size += size;
364
365 return false;
366}
367
368/**********************
369 * GLOBAL FUNCTIONS
370 **********************/
371
380mem_ctx_t mem_init(void *heap_start, size_t heap_size)
381{
382 heap_t *heap = (heap_t *) heap_start;
383
384 // heap_start must not be NULL
385 if (heap_start == NULL) {
386 return NULL;
387 }
388
389 // size must be a multiple of 8, and at least 200 bytes
390 if ((heap_size & (FREE_CHUNK_HEADER_SIZE - 1)) || (heap_size < 200)
391 || (heap_size > (0x7FF8 + HEAP_HEADER_SIZE))) {
392 return NULL;
393 }
394
395 // a previous allocator on this buffer may have left it poisoned
396 MEM_UNPOISON(heap_start, heap_size);
397
398 heap->end = ((uint8_t *) heap_start) + heap_size;
399
400 // compute number of segments
401 heap->nb_segs = 31 - __builtin_clz(heap_size - HEAP_HEADER_SIZE) - NB_LINEAR_SEGMENTS + 1;
402 if (heap->nb_segs > NB_MAX_SEGMENTS) {
403 return NULL;
404 }
405 memset(heap->free_segments, 0, heap->nb_segs * NB_SUB_SEGMENTS * sizeof(uint16_t));
406
407 // initiate free chunk LIFO with the whole heap as a free chunk
408 header_t *first_free = (header_t *) (((uint8_t *) heap) + HEAP_HEADER_SIZE);
409 first_free->size = heap_size - HEAP_HEADER_SIZE;
410 first_free->phys_prev = 0;
411 list_push(heap, first_free);
412 MEM_POISON(((uint8_t *) first_free) + ALLOC_CHUNK_HEADER_SIZE,
413 first_free->size - ALLOC_CHUNK_HEADER_SIZE);
414
415 return (mem_ctx_t) heap_start;
416}
417
427void *mem_alloc(mem_ctx_t ctx, size_t nb_bytes)
428{
429 heap_t *heap = (heap_t *) ctx;
430 int seg;
431 size_t requested = nb_bytes;
432
433 // nb_bytes must be > 0
434 if (nb_bytes == 0) {
435 return NULL;
436 }
437
438 // Reject sizes that would overflow the unsigned arithmetic below
439 // or exceed the maximum chunk size storable in the header.
440 if (nb_bytes > MAX_BLOCK_SIZE
442 + MEM_REDZONE_SIZE)) {
443 return NULL;
444 }
445
446 // Adjust size to include header and satisfy alignment requirements, etc.
447 nb_bytes = align_alloc_size(nb_bytes + MEM_REDZONE_SIZE);
448
449 // get the segment sure to be holding this size
450 // if nb_bytes == 2^n , all chunks in [2^n: 2^(n+1)[ are ok
451 // if nb_bytes > 2^n , all chunks in [2^(n+1): 2^(n+2)[ are ok
452 seg = seglist_index_up(heap, nb_bytes);
453 if (seg < 0) {
454 return NULL;
455 }
456 // Loop through all increasing size segments
457 while ((size_t) seg < (heap->nb_segs * NB_SUB_SEGMENTS)) {
458 uint16_t chunk_idx = heap->free_segments[seg];
459 // if this segment is not empty, it must contain a big-enough chunk
460 if (chunk_idx != 0) {
461 header_t *header = GET_PTR(heap, chunk_idx);
462
463 // ensure chunk is consistent
464 ensure_chunk_valid(heap, header);
465 // this block shall always be big enough
466 if (nb_bytes > header->size) {
467 // probably a big issue, maybe necessary to throw an exception
468 return NULL;
469 }
470 uint8_t *block = (uint8_t *) header;
471
472 // remove the block from the segregated list
473 list_remove(heap, &heap->free_segments[seg], chunk_idx);
474 // We could turn the excess bytes into a new free block
475 // the minimum size is the size of an empty chunk
476 if (header->size >= (nb_bytes + FREE_CHUNK_HEADER_SIZE)) {
477 header_t *new_free = (header_t *) &block[nb_bytes];
479 new_free->size = header->size - nb_bytes;
480 // link this new chunk to previous (found) one
481 new_free->phys_prev = chunk_idx;
482 // link the current next physical chunk to this new chunk (if existing)
483 header_t *next = (header_t *) &block[header->size];
484 if ((void *) next < heap->end) {
485 next->phys_prev = GET_IDX(heap, new_free);
486 }
487 list_push(heap, new_free);
488 // change size only if new chunk is created
489 header->size = nb_bytes;
490 }
491
492 // Update the chunk's header to set the allocated bit
493 header->allocated = 0x1;
494
495 // clean-up previous empty header info
496 LINKS_UNPOISON(header);
497 header->fnext = header->fprev = 0;
498
499 // the caller owns the requested bytes only, not the redzone and alignment padding
500 MEM_UNPOISON(block + ALLOC_CHUNK_HEADER_SIZE, requested);
501 MEM_POISON(block + ALLOC_CHUNK_HEADER_SIZE + requested,
502 header->size - ALLOC_CHUNK_HEADER_SIZE - requested);
503
504 // Return a pointer to the payload
505 return block + ALLOC_CHUNK_HEADER_SIZE;
506 }
507 // not found in current segment, let's try in bigger segment
508 seg++;
509 }
510 return NULL;
511}
512
525void *mem_realloc(mem_ctx_t ctx, void *ptr, size_t size)
526{
527 heap_t *heap = (heap_t *) ctx;
528
529 // Use mem_alloc if original pointer is NULL
530 if (ptr == NULL) {
531 return mem_alloc(ctx, size);
532 }
533
534 // Check ptr is valid
535 if (ptr < (void *) (((uint8_t *) heap) + HEAP_HEADER_SIZE) || ptr >= (void *) heap->end) {
536 PRINTF("invalid pointer passed to realloc: 0x%p!\n", ptr);
537 return NULL;
538 }
539
540 // Free the original block if new size is zero
541 if (size == 0) {
542 mem_free(ctx, ptr);
543 return NULL;
544 }
545
546 // Reject sizes that would overflow the unsigned arithmetic in
547 // align_alloc_size (which adds up to PAYLOAD_ALIGNEMENT - 1 +
548 // ALLOC_CHUNK_HEADER_SIZE + PAYLOAD_ALIGNEMENT bytes of overhead).
549 if (size > MAX_BLOCK_SIZE
551 + MEM_REDZONE_SIZE)) {
552 return NULL;
553 }
554
555 // Get the header of the current block
556 uint8_t *block = ((uint8_t *) ptr) - ALLOC_CHUNK_HEADER_SIZE;
557 header_t *header = (header_t *) block;
558
559 // Ensure this is a valid chunk before we try to read its size.
560 ensure_chunk_valid(heap, header);
561
562 // Save the size of the old block
563 size_t old_block_size = header->size;
564 // Save the size of the data portion of the old block
565 size_t old_payload_size = old_block_size - ALLOC_CHUNK_HEADER_SIZE;
566 // Adjust size of the new block to include header and satisfy alignment requirements, etc.
567 size_t new_block_size = align_alloc_size(size + MEM_REDZONE_SIZE);
568
569 // If the old block is already big enough, return the same pointer
570 if (old_payload_size >= size + MEM_REDZONE_SIZE) {
571 // Shrink optimization : split the original block in two
572 // if remaining size is enough for a free chunk
573 size_t remainder = old_block_size - new_block_size;
574 if (remainder >= FREE_CHUNK_HEADER_SIZE) {
575 // Save pointer to next physical chunk
576 header_t *next = (header_t *) &block[old_block_size];
577 // Create new free chunk in the remaining space,
578 // located just after the resized block
579 header_t *new_free = (header_t *) &block[new_block_size];
581 new_free->size = remainder;
582 // The new chunk predecessor is the resized chunk (still the same)
583 new_free->phys_prev = GET_IDX(heap, header);
584 // Link the current next physical chunk to this new chunk (if existing)
585 if ((void *) next < heap->end) {
586 next->phys_prev = GET_IDX(heap, new_free);
587 }
588 list_push(heap, new_free);
589 MEM_POISON(((uint8_t *) new_free) + ALLOC_CHUNK_HEADER_SIZE,
590 remainder - ALLOC_CHUNK_HEADER_SIZE);
591 // Adjust the size of the allocated block
592 header->size = new_block_size;
593 }
594 // the caller now owns exactly the new size
595 MEM_UNPOISON(ptr, size);
596 MEM_POISON(((uint8_t *) ptr) + size, header->size - ALLOC_CHUNK_HEADER_SIZE - size);
597 // Return the original block pointer as it is still valid
598 return ptr;
599 }
600
601 // Allocate new block
602 void *new_ptr = mem_alloc(ctx, size);
603 if (new_ptr == NULL) {
604 return NULL;
605 }
606
607 // We copy only the amount of data that existed in the OLD block, capped to the new size.
608 // This guarantees we never read past the end of the old allocated buffer.
609 // The old padding is copied too, so it must be readable.
610 size_t copy_size = MIN(old_payload_size, size);
611 MEM_UNPOISON(ptr, copy_size);
612 memcpy(new_ptr, ptr, copy_size);
613
614 // Free the old block
615 mem_free(ctx, ptr);
616
617 // Return the new block pointer
618 return new_ptr;
619}
620
627void mem_free(mem_ctx_t ctx, void *ptr)
628{
629 heap_t *heap = (heap_t *) ctx;
630 uint8_t *block = ((uint8_t *) ptr) - ALLOC_CHUNK_HEADER_SIZE;
631 header_t *header = (header_t *) block;
632
633 // ensure size is consistent
634 ensure_chunk_valid(heap, header);
635 // if not allocated, return
636 if (!header->allocated) {
637 return;
638 }
639 // the free-list links of the header overlap the start of the payload
641 // try to coalesce with adjacent physical chunks (after and before)
642 // try with next physical chunk
643 if ((block + header->size) < (uint8_t *) heap->end) {
644 header = coalesce(heap, header, (header_t *) (block + header->size));
645 }
646 // try previous chunk
647 if (header->phys_prev != 0) {
648 header = coalesce(heap, header, GET_PTR(heap, header->phys_prev));
649 }
650
651 // free chunk and add it on top of free chunk LIFO
652 list_push(heap, header);
653 MEM_POISON(((uint8_t *) header) + ALLOC_CHUNK_HEADER_SIZE,
654 header->size - ALLOC_CHUNK_HEADER_SIZE);
655}
656
666void mem_parse(mem_ctx_t ctx, mem_parse_callback_t callback, void *data)
667{
668 heap_t *heap = (heap_t *) ctx;
669 header_t *header = (header_t *) (((uint8_t *) heap) + HEAP_HEADER_SIZE);
670#ifdef DEBUG_FREE_SEGMENTS
671 for (size_t i = 0; i < heap->nb_segs; i++) {
672 if (heap->free_segments[i] != NULL) {
673 header_t *head = heap->free_segments[i];
674 int nb_elemts = 0;
675 while (head) {
676 nb_elemts++;
677 head = head->fnext;
678 }
679 }
680 }
681#endif // DEBUG_FREE_SEGMENTS
682 while (header != NULL) {
683 uint8_t *block = (uint8_t *) header;
684 // break the loop if the callback returns true
685 if (callback(data, block, header->allocated, header->size)) {
686 return;
687 }
688 if (&block[header->size] < (uint8_t *) heap->end) {
689 header = (header_t *) &block[header->size];
690 }
691 else {
692 return;
693 }
694 }
695}
696
707{
708 memset(stat, 0, sizeof(mem_stat_t));
710 mem_parse(ctx, parse_callback, stat);
711}
static int seglist_index(heap_t *heap, size_t size)
Definition mem_alloc.c:142
#define GET_PTR(_heap, index)
Definition mem_alloc.c:55
static void set_fprev(header_t *header, uint16_t fprev)
Definition mem_alloc.c:212
#define ALLOC_CHUNK_HEADER_SIZE
Definition mem_alloc.c:27
#define MEM_UNPOISON(_addr, _size)
Definition mem_alloc.c:78
void * mem_realloc(mem_ctx_t ctx, void *ptr, size_t size)
Reallocates a buffer to a new size.
Definition mem_alloc.c:525
static header_t * coalesce(heap_t *heap, header_t *header, header_t *neighbour)
Definition mem_alloc.c:306
struct header_s header_t
#define PAYLOAD_ALIGNEMENT
Definition mem_alloc.c:23
static size_t align_alloc_size(size_t size)
Definition mem_alloc.c:125
#define LINKS_POISON(_ptr)
Definition mem_alloc.c:93
static void set_fnext(header_t *header, uint16_t fnext)
Definition mem_alloc.c:219
#define GET_SEGMENT(_size)
Definition mem_alloc.c:58
mem_ctx_t mem_init(void *heap_start, size_t heap_size)
initializes the heap for this allocator
Definition mem_alloc.c:380
#define NB_LINEAR_SEGMENTS
Definition mem_alloc.c:37
#define NB_SUB_SEGMENTS
Definition mem_alloc.c:52
void * mem_alloc(mem_ctx_t ctx, size_t nb_bytes)
allocates a buffer of the given size, if possible
Definition mem_alloc.c:427
#define NB_MAX_SEGMENTS
Definition mem_alloc.c:50
#define HEAP_HEADER_SIZE
Definition mem_alloc.c:33
#define MEM_POISON(_addr, _size)
Definition mem_alloc.c:77
#define MAX_BLOCK_SIZE
Definition mem_alloc.c:31
void mem_stat(mem_ctx_t ctx, mem_stat_t *stat)
function used to get statistics (nb chunks, nb allocated chunks, total size) about the heap
Definition mem_alloc.c:706
static void list_push(heap_t *heap, header_t *header)
Definition mem_alloc.c:254
#define FREE_CHUNK_HEADER_SIZE
Definition mem_alloc.c:29
void mem_free(mem_ctx_t ctx, void *ptr)
frees the given buffer
Definition mem_alloc.c:627
static int seglist_index_up(heap_t *heap, size_t size)
Definition mem_alloc.c:169
#define LINKS_UNPOISON(_ptr)
Definition mem_alloc.c:92
void mem_parse(mem_ctx_t ctx, mem_parse_callback_t callback, void *data)
parse the heap
Definition mem_alloc.c:666
static void list_remove(heap_t *heap, uint16_t *first_free, uint16_t elem)
Definition mem_alloc.c:227
#define MEM_REDZONE_SIZE
Definition mem_alloc.c:86
static bool parse_callback(void *data, uint8_t *addr, bool allocated, size_t size)
Definition mem_alloc.c:346
static void ensure_chunk_valid(heap_t *heap, header_t *header)
Definition mem_alloc.c:280
#define GET_IDX(_heap, _ptr)
Definition mem_alloc.c:56
Dynamic memory allocation API.
void * mem_ctx_t
type shared externally
Definition mem_alloc.h:27
bool(* mem_parse_callback_t)(void *data, uint8_t *addr, bool allocated, size_t size)
function called for each chunk found in the heap.
Definition mem_alloc.h:40
#define MIN(x, y)
Definition nbgl_types.h:131
uint16_t fprev
previous free chunk in the same segment
Definition mem_alloc.c:104
uint16_t size
Definition mem_alloc.c:99
uint16_t phys_prev
physical previous chunk
Definition mem_alloc.c:102
uint16_t fnext
next free chunk in the same segment
Definition mem_alloc.c:105
uint16_t allocated
Definition mem_alloc.c:100
void * end
end of headp buffer, for consistency check
Definition mem_alloc.c:109
size_t nb_segs
actual number of used segments
Definition mem_alloc.c:110
uint16_t free_segments[NB_MAX_SEGMENTS *NB_SUB_SEGMENTS]
Definition mem_alloc.c:111
this structure, filled by mem_stat
Definition mem_alloc.h:46
size_t allocated_size
nb bytes allocated in the heap (including headers)
Definition mem_alloc.h:50
size_t total_size
total size of the heap (including allocator internal data)
Definition mem_alloc.h:47
uint32_t nb_allocated
number of allocated chunks
Definition mem_alloc.h:52
size_t free_size
Definition mem_alloc.h:48
uint32_t nb_chunks
total number of chunks
Definition mem_alloc.h:51