sys_heap.h

Go to the documentation of this file.

/*
 * Copyright (c) 2019 Intel Corporation
 *
 * SPDX-License-Identifier: Apache-2.0
 */
#ifndef ZEPHYR_INCLUDE_SYS_SYS_HEAP_H_
#define ZEPHYR_INCLUDE_SYS_SYS_HEAP_H_
 
#include <stddef.h>
#include <stdbool.h>
#include <zephyr/types.h>
 
/* Simple, fast heap implementation.
 *
 * A more or less conventional segregated fit allocator with
 * power-of-two buckets.
 *
 * Excellent space efficiency.  Chunks can be split arbitrarily in 8
 * byte units.  Overhead is only four bytes per allocated chunk (eight
 * bytes for heaps >256kb or on 64 bit systems), plus a log2-sized
 * array of 2-word bucket headers.  No coarse alignment restrictions
 * on blocks, they can be split and merged (in units of 8 bytes)
 * arbitrarily.
 *
 * Simple API.  Initialize at runtime with any blob of memory and not
 * a macro-generated, carefully aligned static array.  Allocate and
 * free by user pointer and not an opaque block handle.
 *
 * Good fragmentation resistance.  Freed blocks are always immediately
 * merged with adjacent free blocks.  Allocations are attempted from a
 * sample of the smallest bucket that might fit, falling back rapidly
 * to the smallest block guaranteed to fit.  Split memory remaining in
 * the chunk is always returned immediately to the heap for other
 * allocation.
 *
 * Excellent performance with firmly bounded runtime.  All operations
 * are constant time (though there is a search of the smallest bucket
 * that has a compile-time-configurable upper bound, setting this to
 * extreme values results in an effectively linear search of the
 * list), objectively fast (~hundred instructions) and and amenable to
 * locked operation.
 */
 
/* Note: the init_mem/bytes fields are for the static initializer to
 * have somewhere to put the arguments.  The actual heap metadata at
 * runtime lives in the heap memory itself and this struct simply
 * functions as an opaque pointer.  Would be good to clean this up and
 * put the two values somewhere else, though it would make
 * SYS_HEAP_DEFINE a little hairy to write.
 */
struct sys_heap {
        struct z_heap *heap;
        void *init_mem;
        size_t init_bytes;
};
 
struct z_heap_stress_result {
        uint32_t total_allocs;
        uint32_t successful_allocs;
        uint32_t total_frees;
        uint64_t accumulated_in_use_bytes;
};
 
#ifdef CONFIG_SYS_HEAP_RUNTIME_STATS
 
struct sys_heap_runtime_stats {
        size_t free_bytes;
        size_t allocated_bytes;
};
 
int sys_heap_runtime_stats_get(struct sys_heap *heap,
                struct sys_heap_runtime_stats *stats);
 
#endif
 
void sys_heap_init(struct sys_heap *heap, void *mem, size_t bytes);
 
void *sys_heap_alloc(struct sys_heap *heap, size_t bytes);
 
void *sys_heap_aligned_alloc(struct sys_heap *heap, size_t align, size_t bytes);
 
void sys_heap_free(struct sys_heap *heap, void *mem);
 
void *sys_heap_aligned_realloc(struct sys_heap *heap, void *ptr,
                               size_t align, size_t bytes);
 
#define sys_heap_realloc(heap, ptr, bytes) \
        sys_heap_aligned_realloc(heap, ptr, 0, bytes)
 
bool sys_heap_validate(struct sys_heap *heap);
 
void sys_heap_stress(void *(*alloc_fn)(void *arg, size_t bytes),
                     void (*free_fn)(void *arg, void *p),
                     void *arg, size_t total_bytes,
                     uint32_t op_count,
                     void *scratch_mem, size_t scratch_bytes,
                     int target_percent,
                     struct z_heap_stress_result *result);
 
void sys_heap_print_info(struct sys_heap *heap, bool dump_chunks);
 
#endif /* ZEPHYR_INCLUDE_SYS_SYS_HEAP_H_ */