MISRA-C Rule 5.3 states that identifiers in inner scope should
not hide identifiers in outer scope.
In the function sys_heap_alloc(), the variable "chunksz"
collide with function named chunksz(). So rename those variable.
Signed-off-by: Daniel Leung <daniel.leung@intel.com>
After commit 8a6b02b5bf ("lib/os/heap: some code simplification in
sys_heap_aligned_alloc()") it is no longer required to have a "big"
heap for aligned allocations to work on 32-bit targets. While the
natural alignment for returned memory has an offset of 4 within a chunk
unit due to the smaller header size, returning to a chunkid from a
memory pointer with an offset of 8 will fall back onto the proper chunk
number once the 4 is substracted and then divided by 8.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The code is doing a split in split_alloc(), adding the leftover to the
free list, then splitting the suffix away in sys_heap_aligned_alloc(),
removing the former leftover from the free list, combining it with the
suffix and finally adding the combined chunk back to the free list.
Instead, let's have each allocator do their own splitting only once by
moving the split_alloc() processing upstream rather than downstream.
This also allows for the "used" flag to be set only once at the end
rather than being overwritten along the way.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Instead of limiting the excess split-off to sufficiently large chunks
in split_alloc(), let's allow normal allocations to create "solo free
headers" just like with aligned allocations. There is no point leaving
them in the allocated chunk if the user didn't ask for it. Doing so
makes them eligible for merging at the next opportunity and potentially
reusable sooner.
Also make the validation code aware of them.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
This makes the code cleaner wrt bucket_idx() usage on chunks for which
solo_free_header() is true. In such case the bucket_idx() computation
is useless, and potentially undefined anyway.
In the same vain, move the clearing of the used flag out of
free_chunks() as only one of its callers actually needs that.
Makes free_chunks singular as there is only one chunk (potentially
spanning multiple chunk units) to free.
Also some cosmetic changes for better code uniformity.
No functional changes.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Some checks in sys_heap_init() depend on the externally provided size
parameter. If the check fails, this would be a bug outside of the heap
code and therefore should be flagged despite the value of
CONFIG_SYS_HEAP_VALIDATE.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Add support for a C11-style aligned_alloc() in the heap
implementation. This is properly optimized, in the sense that unused
prefix/suffix data around the chosen allocation is returned to the
heap and made available for general allocation.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
Miscellaneous refactoring and simplification. No behavioral changes:
Make split_alloc() take and return chunk IDs and not memory pointers,
leaving the conversion between memory/chunks the job of the higher
level sys_heap_alloc() API. This cleans up the internals for code
that wants to do allocation but has its own ideas about what to do
with the resulting chunks.
Add split_chunks() and merge_chunks() utilities to own the linear/size
pointers and have split_alloc() and free_chunks() use them instead of
doing the list management directly.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
This struct is taking up most of the heap's constant footprint overhead.
We can easily get rid of the list_size member as it is mostly used to
determine if the list is empty, and that can be determined through
other means.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Make the LEFT_SIZE field first and SIZE_AND_USED field last (for an
allocated chunk) so they sit right next to the allocated memory. The
current chunk's SIZE_AND_USED field points to the next (right) chunk,
and from there the LEFT_SIZE field should point back to the current
chunk. Many trivial memory overflows should trip that test.
One way to make this test more robust could involve xor'ing the values
within respective accessor pairs. But at least the fact that the size
value is shifted by one bit already prevent fooling the test with a
same-byte corruption.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
We already have chunk #0 containing our struct z_heap and marked as
used. We can add a partial chunk at the very end that is also marked
as used. By doing so there is no longer a need for checking heap
boundaries at run time when merging/splitting chunks meaning fewer
conditionals in the code's hot path.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
It is possible to remove a few fields from struct z_heap, removing
some runtime indirections by doing so:
- The buf pointer is actually the same as the struct z_heap pointer
itself. So let's simply create chunk_buf() that perform a type
conversion. That type is also chunk_unit_t now rather than u64_t so
it can be defined based on CHUNK_UNIT.
- Replace the struct z_heap_bucket pointer by a zero-sized array at the
end of struct z_heap.
- Make chunk #0 into an actual chunk with its own header. This allows
for removing the chunk0 field and streamlining the code. This way
h->chunk0 becomes right_chunk(h, 0). This sets the table for further
simplifications to come.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
By storing the used flag in the LSB, it is no longer necessary to have
a size_mask variable to locate that flag. This produces smaller and
faster code.
Replace the validation check in chunk_set() to base it on the storage
type.
Also clarify the semantics of set_chunk_size() which allows for clearing
the used flag bit unconditionally which simplifies the code further.
The idea of moving the used flag bit into the LEFT_SIZE field was
raised. It turns out that this isn't as beneficial as it may seem
because the used bit is set only once i.e. when the memory is handed off
to a user and the size field becomes frozen at that point. Modifications
on the leftward chunk may still occur and extra instructions to preserve
that bit would be necessary if it were moved there.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Let's provide accessors for getting and setting every field to make the
chunk header layout abstracted away from the main code. Those are:
SIZE_AND_USED: chunk_used(), chunk_size(), set_chunk_used() and
chunk_size().
LEFT_SIZE: left_chunk() and set_left_chunk_size().
FREE_PREV: prev_free_chunk() and set_prev_free_chunk().
FREE_NEXT: next_free_chunk() and set_next_free_chunk().
To be consistent, the former chunk_set_used() is now set_chunk_used().
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
First, some renames to make accessors more explicit:
size() --> chunk_size()
used() --> chunk_used()
free_prev() --> prev_free_chunk()
free_next() --> next_free_chunk()
Then, the return type of chunk_size() is changed from chunkid_t to
size_t, and chunk_used() from chunkid_t to bool.
The left_size() accessor is used only once and can be easily substituted
by left_chunk(), so it is removed.
And in free_list_add() the variable b is renamed to bi so to be
consistent with usage in sys_heap_alloc().
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
The existing mem_pool implementation has been an endless source of
frustration. It's had alignment bugs, it's had racy behavior. It's
never been particularly fast. It's outrageously complicated to
configure statically. And while its fragmentation resistance and
overhead on small blocks is good, it's space efficiencey has always
been very poor due to the four-way buddy scheme.
This patch introduces sys_heap. It's a more or less conventional
segregated fit allocator with power-of-two buckets. It doesn't expose
its level structure to the user at all, simply taking an arbitrarily
aligned pointer to memory. It stores all metadata inside the heap
region. It allocates and frees by simple pointer and not block ID.
Static initialization is trivial, and runtime initialization is only a
few cycles to format and add one block to a list header.
It has 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.
It has 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.
It has 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 (about a hundred instructions) and amenable to
locked operation. No more need for fragile lock relaxation trickery.
It also contains an extensive validation and stress test framework,
something that was sorely lacking in the previous implementation.
Note that sys_heap is not a compatible API with sys_mem_pool and
k_mem_pool. Partial wrappers for those (now-) legacy APIs will appear
later and a deprecation strategy needs to be chosen.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
