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>
Just as NULL pointers should not be dereferenced, they should
not be called either.
Fixes 26723
Signed-off-by: Pete Skeggs <peter.skeggs@nordicsemi.no>
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>
One fundamental validation criteria is to never have consecutive free
chunks. If that ever happens we failed to merge them. That means a free
chunk must always be surrounded by used chunks.
It is a pain to extend valid_chunk() with new rules as it is.
So a VALIDATE() macro is introduced to make things easier to work with.
It also allows for isolating each test, possibly making VALIDATE() into
__ASSERT() to determine exactly which test is tripping when debugging.
Finally, because of that new validation rule, sys_heap_validate() must
be modified so not to use valid_chunk() while it is flipping all the
"used" flags. So let's run valid_chunk() up front before alterating
chunk headers.
Now sys_heap_validate() has become justifiably more expensive and a few
emulated targets are about to bust the tests/lib/heap test timeout. So
bump the timeout as well.
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>
Currently printk isn't synchronized except at the byte output level,
leading to interleaving of messages on SMP systems that try to log
simultaneously. This is actually fairly amusing, and actually helpful
occasionally to validate inter-CPU contention down to the "few cycles"
level.
Still, when you're printing data you need to read, you need to be able
to read it. Put a spinlock around each buffered line. This has to
happen in a few places, as there are three different code paths taken
for !USERSPACE, syscall, and user mode.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
The width for %p on 32-bit targets should be 8 regardless of
CONFIG_PRINTK64. Adjust the test accordingly.
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 64 bit conversions in a uniformly expressable way by
printing values backwards into a buffer on the stack first. This
allows all operations to work on the low bits of the value and so the
code doesn't need to care (beyond the size of that buffer) about the
word size. This trick also doesn't care about the specifics of the
base value, so in the process this unifies the decimal and hex printk
conversion code to a single function.
This comes at a mild cost in CPU cycles to the decimal converter and
somewhat higher cost to hex (because it's now doing a full div/mod
operation instead of shifting and masking). And stack usage has grown
by a few words to hold the temporary. But the benefits in code size
are substantial (e.g. ~250 bytes of .text on arm32).
Note that this also contains a change to tests/kernel/common to
address what appears to have been a bug in the original converters.
The printk test uses a format string that looks like "%-4x%-2p" and
feeds it the literal arguments "0xABCDEF" and "(char *)42".
Now... clearly both those results are going to overflow the 4 and
2-byte field sizes, so there shouldn't be any whitespace between these
fields. But the test was written to expect two spaces, inexplicably
(yes, I checked: POSIX-compatible printf implementations don't have
those spaces either).
The new code is definitely doing the right thing, so fix the test
instead.
Signed-off-by: Andy Ross <andrew.j.ross@intel.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 library supports the declaration of JSON arrays as both nested and
top-level elements. However, as the provided encoding functions
json_obj_encode() and json_obj_encode_buf() interpret all input
structures as objects, top-level arrays are encoded as
{"<field_name>":[{...},...,{...}]}
instead of
[{...},...,{...}].
Add new functions json_arr_encode() and json_arr_encode_buf() that
enable top-level JSON array encoding.
Signed-off-by: Markus Fuchs <markus.fuchs@de.sauter-bc.com>
Anytime a file descriptor context object is updated, we need to
reset its access permissions and initialization state. This
is the most centralized place to do it.
Signed-off-by: Andrew Boie <andrew.p.boie@intel.com>
The bounds check failed to account for the additional space required
for the terminating NUL after the encoded value was written.
Signed-off-by: Peter Bigot <peter.bigot@nordicsemi.no>
The previous architecture proved unable to support user expectations,
so the API has been rebuilt from first principles. Backward
compatibility cannot be maintained for this change.
Key changes include:
* Formerly the service-provided transition functions were allowed to
sleep, and the manager took care to not invoke them from ISR
context, instead returning an error if unable to initiate a
transition. In the new architecture transition functions are
required to work regardless of calling context: it is the service's
responsibility to guarantee the transition will proceed even if it
needs to be transferred to a thread. This eliminates state machine
complexities related to calling context.
* Constants identifying the visible state of the manager are exposed
to clients through both notification callbacks and a new monitor API
that allows clients to be notified of all state changes.
* Formerly the release operation was async, and would be delayed for the
last release to ensure a client would exist to be notified of any
failures. It is now synchronous.
* Formerly the cancel operation would fail on the last client associated
with a transition. The cancel operation is now synchronous.
* A helper function is provided to safely synchronously release a
request regardless of whether it has completed or is in progress,
satisfying the use case underlying #22974.
* The user-data parameter to asynchronous notification callbacks has
been removed as user data can be retrieved from the CONTAINER_OF
the client data.
Signed-off-by: Peter Bigot <peter.bigot@nordicsemi.no>
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>
The original API was misnamed, as the intent was to provide a manager
that decoupled state management from the service that needed to be
turned on or off. Update all the names, shortening them where
appropriate removing unncessary internal components like _service.
Also remove some API that misled developers into believing that onoff
managers are normally expected to be exposed directly to consumers.
While this is a use case, in most situations there are service or
client-specific actions that need to be coupled to transition events.
Signed-off-by: Peter Bigot <peter.bigot@nordicsemi.no>
k_poll() for a signal is often desired for notification of completion
of asynchronous operations, but there are APIs where it may be
necessary to invoke "asynchronous" operations from contexts where
sleep is disallowed, or before the kernel has been initialized.
Extract the general notification solution from the on-off service into
a utility that can be used for other APIs.
Also move documentation out to a resource management section.
Signed-off-by: Peter Bigot <peter.bigot@nordicsemi.no>
Extracted transition functions from onoff structure to external one
which allows to keep them in flash.
Signed-off-by: Krzysztof Chruscinski <krzysztof.chruscinski@nordicsemi.no>
Add a k_timeout_t type, and use it everywhere that kernel API
functions were accepting a millisecond timeout argument. Instead of
forcing milliseconds everywhere (which are often not integrally
representable as system ticks), do the conversion to ticks at the
point where the timeout is created. This avoids an extra unit
conversion in some application code, and allows us to express the
timeout in units other than milliseconds to achieve greater precision.
The existing K_MSEC() et. al. macros now return initializers for a
k_timeout_t.
The K_NO_WAIT and K_FOREVER constants have now become k_timeout_t
values, which means they cannot be operated on as integers.
Applications which have their own APIs that need to inspect these
vs. user-provided timeouts can now use a K_TIMEOUT_EQ() predicate to
test for equality.
Timer drivers, which receive an integer tick count in ther
z_clock_set_timeout() functions, now use the integer-valued
K_TICKS_FOREVER constant instead of K_FOREVER.
For the initial release, to preserve source compatibility, a
CONFIG_LEGACY_TIMEOUT_API kconfig is provided. When true, the
k_timeout_t will remain a compatible 32 bit value that will work with
any legacy Zephyr application.
Some subsystems present timeout (or timeout-like) values to their own
users as APIs that would re-use the kernel's own constants and
conventions. These will require some minor design work to adapt to
the new scheme (in most cases just using k_timeout_t directly in their
own API), and they have not been changed in this patch, instead
selecting CONFIG_LEGACY_TIMEOUT_API via kconfig. These subsystems
include: CAN Bus, the Microbit display driver, I2S, LoRa modem
drivers, the UART Async API, Video hardware drivers, the console
subsystem, and the network buffer abstraction.
k_sleep() now takes a k_timeout_t argument, with a k_msleep() variant
provided that works identically to the original API.
Most of the changes here are just type/configuration management and
documentation, but there are logic changes in mempool, where a loop
that used a timeout numerically has been reworked using a new
z_timeout_end_calc() predicate. Also in queue.c, a (when POLL was
enabled) a similar loop was needlessly used to try to retry the
k_poll() call after a spurious failure. But k_poll() does not fail
spuriously, so the loop was removed.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
Private type, internal to the kernel, not directly associated
with any k_object_* APIs. Is the return value of z_object_find().
Rename to struct z_object.
Signed-off-by: Andrew Boie <andrew.p.boie@intel.com>
Rather than stuffing various values in a uintptr_t based on
type using casts, use a union for this instead.
No functional difference, but the semantics of the data member
are now much clearer to the casual observer since it is now
formally defined by this union.
Signed-off-by: Andrew Boie <andrew.p.boie@intel.com>
There are various situations where it's necessary to support turning
devices on or off at runtime, includin power rails, clocks, other
peripherals, and binary device power management. The complexity of
properly managing multiple consumers of a device in a multithreaded
system suggests that a shared implementation is desirable. This
commit provides an API that supports managing on-off resources.
Signed-off-by: Peter A. Bigot <pab@pabigot.com>
Completely remove the file info and condition expression from the
the print statement if they are not enabled. This saves a little code
space which adds up when there are many assert calls.
In bluetooth shell test this saves around 4.5k bytes.
Signed-off-by: Joakim Andersson <joakim.andersson@nordicsemi.no>
The intention of disabling CONFIG_PRINTK is that all
invocations of it will compile to nothing, saving a lot
of runtime overhead and footprint since all the format
strings are completely dropped; instances of printk()
and related functions are no-ops.
However, some subsystems need snprintk() for string
processing, since the snprintf() implementations in even
minimal C library are too costly in text footprint or
stack usage for some applications. This processing is
required for the application to even function.
This patch continues to have disabling CONFIG_PRINTK to
cause the non snprintk functions to become no-ops, but
now we always compile the necessary bits for snprintk(),
relying on gc-sections to discard them if unused.
z_vprintk() is now unconditionally defined in the header
since it is not tied to any particular output sink and
is intended for users who know exactly what they are
doing (it's in zephyr private scope).
Relates to: #21564
Signed-off-by: Andrew Boie <andrew.p.boie@intel.com>
Remove leading/trailing blank lines in .c, .h, .py, .rst, .yml, and
.yaml files.
Will avoid failures with the new CI test in
https://github.com/zephyrproject-rtos/ci-tools/pull/112, though it only
checks changed files.
Move the 'target-notes' target in boards/xtensa/odroid_go/doc/index.rst
to get rid of the trailing blank line there. It was probably misplaced.
Signed-off-by: Ulf Magnusson <Ulf.Magnusson@nordicsemi.no>
Promote the private z_arch_* namespace, which specifies
the interface between the core kernel and the
architecture code, to a new top-level namespace named
arch_*.
This allows our documentation generation to create
online documentation for this set of interfaces,
and this set of interfaces is worth treating in a
more formal way anyway.
Signed-off-by: Andrew Boie <andrew.p.boie@intel.com>
A double-free could cause very hard to find bugs when using the mempool
allocator as the same memory would end up being allocated twice
afterwards.
Now that bits in the block bitmap are cleared only when actually freeing
a block, we may simply ensure those bits are still set before clearing
them, effectively catching most double-free cases.
The alloc_bit_is_set() function is made static inline so that when
assertion checks are disabled the compiler won't complain about unused
code.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
Use this short header style in all Kconfig files:
# <description>
# <copyright>
# <license>
...
Also change all <description>s from
# Kconfig[.extension] - Foo-related options
to just
# Foo-related options
It's clear enough that it's about Kconfig.
The <description> cleanup was done with this command, along with some
manual cleanup (big letter at the start, etc.)
git ls-files '*Kconfig*' | \
xargs sed -i -E '1 s/#\s*Kconfig[\w.-]*\s*-\s*/# /'
Signed-off-by: Ulf Magnusson <Ulf.Magnusson@nordicsemi.no>
When small blocks are recombined to create a single block at a shallower
level, it is sufficient to remove those blocks from the free list. There
is no need to mark those small blocks as allocated in the bitmap.
This, in turn, removes the need to mark small blocks back as unallocated
when splitting up a big blocks as they'll already be so marked.
Only the first small block needs to be marked allocated and the
remaining blocks only need to be added to the free list.
This makes the code smaller and more efficient, especially since those
removed bit manipulations were located within loops.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
This turns the free-bit flag into an alloc-bit flag effectively
reversing its semantic. This is to make further changes more natural
and easier to understand.
No need to clear the alloc bits at init time as they're located in .bss
and all clear already.
The code remains functionally equivalent after this change.
Signed-off-by: Nicolas Pitre <npitre@baylibre.com>
