11#include "exceptions.h"
13#include "os_helpers.h"
23#define PAYLOAD_ALIGNEMENT 4
25#define PAYLOAD_DATA_ALIGNEMENT 8
27#define ALLOC_CHUNK_HEADER_SIZE 4
29#define FREE_CHUNK_HEADER_SIZE 8
31#define MAX_BLOCK_SIZE 0x7FFF
33#define HEAP_HEADER_SIZE \
34 ((sizeof(heap_t) + PAYLOAD_DATA_ALIGNEMENT - 1) & ~(PAYLOAD_DATA_ALIGNEMENT - 1))
37#define NB_LINEAR_SEGMENTS 5
50#define NB_MAX_SEGMENTS 10
52#define NB_SUB_SEGMENTS 4
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)
58#define GET_SEGMENT(_size) MAX(NB_LINEAR_SEGMENTS, (31 - __builtin_clz(size)))
63#if defined(__has_feature)
64#if __has_feature(address_sanitizer)
68#if defined(__SANITIZE_ADDRESS__) && !defined(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))
77#define MEM_POISON(_addr, _size) ((void) (_addr), (void) (_size))
78#define MEM_UNPOISON(_addr, _size) ((void) (_addr), (void) (_size))
83#if defined(MEM_ALLOC_ASAN) && defined(FUZZING)
84#define MEM_REDZONE_SIZE 8
86#define MEM_REDZONE_SIZE 0
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)
151 sub_segment = (size >> (seg - 1)) & 0x3;
155 sub_segment = (size >> (seg - 2)) & 0x3;
173 size_t sub_segment_size;
179 sub_segment_size = (1 << (seg - 1));
183 sub_segment_size = (1 << (seg - 2));
187 size += sub_segment_size - 1;
188 size &= ~(sub_segment_size - 1);
194 sub_segment = (size >> (seg - 1)) & 0x3;
198 sub_segment = (size >> (seg - 2)) & 0x3;
215 header->
fprev = fprev;
222 header->
fnext = fnext;
231 uint16_t fprev = elem_ptr->
fprev;
232 uint16_t fnext = elem_ptr->
fnext;
235 if (*first_free == elem) {
262 if (first_idx ==
GET_IDX(heap, header)) {
267 header->
fnext = first_idx;
272 if (first_idx != 0) {
282 uint8_t *block = (uint8_t *) header;
285 || ((block + header->
size) > (uint8_t *) heap->
end)) {
286 PRINTF(
"invalid size: header->size = %d!\n", header->
size);
287 THROW(EXCEPTION_CORRUPT);
292 block = (uint8_t *) heap;
294 PRINTF(
"corrupted prev_chunk\n");
295 THROW(EXCEPTION_CORRUPT);
298 if ((((uint8_t *) prev) + prev->
size) != (uint8_t *) header) {
299 PRINTF(
"corrupted prev_chunk\n");
300 THROW(EXCEPTION_CORRUPT);
308 uint16_t neighbour_idx =
GET_IDX(heap, neighbour);
315 if (seg_index >= 0) {
320 if (header < neighbour) {
321 next = (
header_t *) (((uint8_t *) neighbour) + neighbour->size);
322 if ((
void *) next < heap->end) {
325 header->
size += neighbour->size;
328 memset(neighbour, 0,
sizeof(*neighbour));
331 next = (
header_t *) (((uint8_t *) header) + header->size);
333 if ((
void *) next < heap->end) {
336 neighbour->
size += header->size;
338 memset(header, 0,
sizeof(*header));
346static bool parse_callback(
void *data, uint8_t *addr,
bool allocated,
size_t size)
385 if (heap_start == NULL) {
398 heap->
end = ((uint8_t *) heap_start) + heap_size;
431 size_t requested = nb_bytes;
460 if (chunk_idx != 0) {
466 if (nb_bytes > header->
size) {
470 uint8_t *block = (uint8_t *) header;
479 new_free->
size = header->
size - nb_bytes;
484 if ((
void *) next < heap->end) {
489 header->
size = nb_bytes;
536 PRINTF(
"invalid pointer passed to realloc: 0x%p!\n", ptr);
563 size_t old_block_size = header->
size;
573 size_t remainder = old_block_size - new_block_size;
581 new_free->
size = remainder;
585 if ((
void *) next < heap->end) {
592 header->
size = new_block_size;
603 if (new_ptr == NULL) {
610 size_t copy_size =
MIN(old_payload_size, size);
612 memcpy(new_ptr, ptr, copy_size);
643 if ((block + header->
size) < (uint8_t *) heap->
end) {
670#ifdef DEBUG_FREE_SEGMENTS
671 for (
size_t i = 0; i < heap->
nb_segs; i++) {
682 while (header != NULL) {
683 uint8_t *block = (uint8_t *) header;
685 if (callback(data, block, header->
allocated, header->
size)) {
688 if (&block[header->
size] < (uint8_t *) heap->
end) {
static int seglist_index(heap_t *heap, size_t size)
#define GET_PTR(_heap, index)
static void set_fprev(header_t *header, uint16_t fprev)
#define ALLOC_CHUNK_HEADER_SIZE
#define MEM_UNPOISON(_addr, _size)
void * mem_realloc(mem_ctx_t ctx, void *ptr, size_t size)
Reallocates a buffer to a new size.
static header_t * coalesce(heap_t *heap, header_t *header, header_t *neighbour)
#define PAYLOAD_ALIGNEMENT
static size_t align_alloc_size(size_t size)
#define LINKS_POISON(_ptr)
static void set_fnext(header_t *header, uint16_t fnext)
#define GET_SEGMENT(_size)
mem_ctx_t mem_init(void *heap_start, size_t heap_size)
initializes the heap for this allocator
#define NB_LINEAR_SEGMENTS
void * mem_alloc(mem_ctx_t ctx, size_t nb_bytes)
allocates a buffer of the given size, if possible
#define MEM_POISON(_addr, _size)
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
static void list_push(heap_t *heap, header_t *header)
#define FREE_CHUNK_HEADER_SIZE
void mem_free(mem_ctx_t ctx, void *ptr)
frees the given buffer
static int seglist_index_up(heap_t *heap, size_t size)
#define LINKS_UNPOISON(_ptr)
void mem_parse(mem_ctx_t ctx, mem_parse_callback_t callback, void *data)
parse the heap
static void list_remove(heap_t *heap, uint16_t *first_free, uint16_t elem)
static bool parse_callback(void *data, uint8_t *addr, bool allocated, size_t size)
static void ensure_chunk_valid(heap_t *heap, header_t *header)
#define GET_IDX(_heap, _ptr)
Dynamic memory allocation API.
void * mem_ctx_t
type shared externally
bool(* mem_parse_callback_t)(void *data, uint8_t *addr, bool allocated, size_t size)
function called for each chunk found in the heap.
void * end
end of headp buffer, for consistency check
size_t nb_segs
actual number of used segments
uint16_t free_segments[NB_MAX_SEGMENTS *NB_SUB_SEGMENTS]
this structure, filled by mem_stat
size_t allocated_size
nb bytes allocated in the heap (including headers)
size_t total_size
total size of the heap (including allocator internal data)
uint32_t nb_allocated
number of allocated chunks
uint32_t nb_chunks
total number of chunks