blob: a268fc528b999d852d0633ba87d7e05ca19f1f36 [file] [log] [blame]
/*
* Copyright (c) 2019 Intel Corporation
*
* SPDX-License-Identifier: Apache-2.0
*/
#ifndef ZEPHYR_INCLUDE_LIB_OS_HEAP_H_
#define ZEPHYR_INCLUDE_LIB_OS_HEAP_H_
/*
* Internal heap APIs
*/
/* Theese validation checks are non-trivially expensive, so enable
* only when debugging the heap code. They shouldn't be routine
* assertions.
*/
#ifdef CONFIG_SYS_HEAP_VALIDATE
#define CHECK(x) __ASSERT(x, "")
#else
#define CHECK(x) /**/
#endif
/* Chunks are identified by their offset in 8 byte units from the
* first address in the buffer (a zero-valued chunkid_t is used as a
* null; that chunk would always point into the metadata at the start
* of the heap and cannot be allocated). They are prefixed by a
* variable size header that depends on the size of the heap. Heaps
* with fewer than 2^15 units (256kb) of storage use shorts to store
* the fields, otherwise the units are 32 bit integers for a 16Gb heap
* space (larger spaces really aren't in scope for this code, but
* could be handled similarly I suppose). Because of that design
* there's a certain amount of boilerplate API needed to expose the
* field accessors since we can't use natural syntax.
*
* The fields are:
* LEFT_SIZE: The size of the left (next lower chunk in memory)
* neighbor chunk.
* SIZE_AND_USED: the total size (including header) of the chunk in
* 8-byte units. The bottom bit stores a "used" flag.
* FREE_PREV: Chunk ID of the previous node in a free list.
* FREE_NEXT: Chunk ID of the next node in a free list.
*
* The free lists are circular lists, one for each power-of-two size
* category. The free list pointers exist only for free chunks,
* obviously. This memory is part of the user's buffer when
* allocated.
*
* The field order is so that allocated buffers are immediately bounded
* by SIZE_AND_USED of the current chunk at the bottom, and LEFT_SIZE of
* the following chunk at the top. This ordering allows for quick buffer
* overflow detection by testing left_chunk(c + chunk_size(c)) == c.
*/
enum chunk_fields { LEFT_SIZE, SIZE_AND_USED, FREE_PREV, FREE_NEXT };
#define CHUNK_UNIT 8U
typedef struct { char bytes[CHUNK_UNIT]; } chunk_unit_t;
/* big_heap needs uint32_t, small_heap needs uint16_t */
typedef uint32_t chunkid_t;
typedef uint32_t chunksz_t;
struct z_heap_bucket {
chunkid_t next;
};
struct z_heap {
chunkid_t chunk0_hdr[2];
chunkid_t end_chunk;
uint32_t avail_buckets;
struct z_heap_bucket buckets[0];
};
static inline bool big_heap_chunks(chunksz_t chunks)
{
return sizeof(void *) > 4U || chunks > 0x7fffU;
}
static inline bool big_heap_bytes(size_t bytes)
{
return big_heap_chunks(bytes / CHUNK_UNIT);
}
static inline bool big_heap(struct z_heap *h)
{
return big_heap_chunks(h->end_chunk);
}
static inline chunk_unit_t *chunk_buf(struct z_heap *h)
{
/* the struct z_heap matches with the first chunk */
return (chunk_unit_t *)h;
}
static inline chunkid_t chunk_field(struct z_heap *h, chunkid_t c,
enum chunk_fields f)
{
chunk_unit_t *buf = chunk_buf(h);
void *cmem = &buf[c];
if (big_heap(h)) {
return ((uint32_t *)cmem)[f];
} else {
return ((uint16_t *)cmem)[f];
}
}
static inline void chunk_set(struct z_heap *h, chunkid_t c,
enum chunk_fields f, chunkid_t val)
{
CHECK(c <= h->end_chunk);
chunk_unit_t *buf = chunk_buf(h);
void *cmem = &buf[c];
if (big_heap(h)) {
CHECK(val == (uint32_t)val);
((uint32_t *)cmem)[f] = val;
} else {
CHECK(val == (uint16_t)val);
((uint16_t *)cmem)[f] = val;
}
}
static inline bool chunk_used(struct z_heap *h, chunkid_t c)
{
return chunk_field(h, c, SIZE_AND_USED) & 1U;
}
static inline chunksz_t chunk_size(struct z_heap *h, chunkid_t c)
{
return chunk_field(h, c, SIZE_AND_USED) >> 1;
}
static inline void set_chunk_used(struct z_heap *h, chunkid_t c, bool used)
{
chunk_unit_t *buf = chunk_buf(h);
void *cmem = &buf[c];
if (big_heap(h)) {
if (used) {
((uint32_t *)cmem)[SIZE_AND_USED] |= 1U;
} else {
((uint32_t *)cmem)[SIZE_AND_USED] &= ~1U;
}
} else {
if (used) {
((uint16_t *)cmem)[SIZE_AND_USED] |= 1U;
} else {
((uint16_t *)cmem)[SIZE_AND_USED] &= ~1U;
}
}
}
/*
* Note: no need to preserve the used bit here as the chunk is never in use
* when its size is modified, and potential set_chunk_used() is always
* invoked after set_chunk_size().
*/
static inline void set_chunk_size(struct z_heap *h, chunkid_t c, chunksz_t size)
{
chunk_set(h, c, SIZE_AND_USED, size << 1);
}
static inline chunkid_t prev_free_chunk(struct z_heap *h, chunkid_t c)
{
return chunk_field(h, c, FREE_PREV);
}
static inline chunkid_t next_free_chunk(struct z_heap *h, chunkid_t c)
{
return chunk_field(h, c, FREE_NEXT);
}
static inline void set_prev_free_chunk(struct z_heap *h, chunkid_t c,
chunkid_t prev)
{
chunk_set(h, c, FREE_PREV, prev);
}
static inline void set_next_free_chunk(struct z_heap *h, chunkid_t c,
chunkid_t next)
{
chunk_set(h, c, FREE_NEXT, next);
}
static inline chunkid_t left_chunk(struct z_heap *h, chunkid_t c)
{
return c - chunk_field(h, c, LEFT_SIZE);
}
static inline chunkid_t right_chunk(struct z_heap *h, chunkid_t c)
{
return c + chunk_size(h, c);
}
static inline void set_left_chunk_size(struct z_heap *h, chunkid_t c,
chunksz_t size)
{
chunk_set(h, c, LEFT_SIZE, size);
}
static inline bool solo_free_header(struct z_heap *h, chunkid_t c)
{
return big_heap(h) && chunk_size(h, c) == 1U;
}
static inline size_t chunk_header_bytes(struct z_heap *h)
{
return big_heap(h) ? 8 : 4;
}
static inline size_t heap_footer_bytes(size_t size)
{
return big_heap_bytes(size) ? 8 : 4;
}
static inline chunksz_t chunksz(size_t bytes)
{
return (bytes + CHUNK_UNIT - 1U) / CHUNK_UNIT;
}
static inline chunksz_t bytes_to_chunksz(struct z_heap *h, size_t bytes)
{
return chunksz(chunk_header_bytes(h) + bytes);
}
static inline chunksz_t min_chunk_size(struct z_heap *h)
{
return bytes_to_chunksz(h, 1);
}
static inline size_t chunksz_to_bytes(struct z_heap *h, chunksz_t chunksz_in)
{
return chunksz_in * CHUNK_UNIT - chunk_header_bytes(h);
}
static inline int bucket_idx(struct z_heap *h, chunksz_t sz)
{
unsigned int usable_sz = sz - min_chunk_size(h) + 1;
return 31 - __builtin_clz(usable_sz);
}
static inline bool size_too_big(struct z_heap *h, size_t bytes)
{
/*
* Quick check to bail out early if size is too big.
* Also guards against potential arithmetic overflows elsewhere.
*/
return (bytes / CHUNK_UNIT) >= h->end_chunk;
}
/* For debugging */
void heap_print_info(struct z_heap *h, bool dump_chunks);
#endif /* ZEPHYR_INCLUDE_LIB_OS_HEAP_H_ */