Introduce a binary min-heap implementation as a generic data structure
for use in kernel and application code. A min-heap always maintains
the smallest element at the root, making insertion and removal of the
minimum element efficient (O(log n)).
The API allows both static and dynamic initialization, supports custom
comparators.
Signed-off-by: Sayooj K Karun <sayooj@aerlync.com>
Updates the heap code to ensure that when converting the requested
number of bytes to chunks, we do not return a value that exceeds
the number of chunks in the heap.
Fixes#90306
Signed-off-by: Peter Mitsis <peter.mitsis@intel.com>
It's possible for newlib/picolib libc libraries to
internally call sysconf() which would execute zephyr's
implementation. However, if the _SC* defines do not have
matching values, then the incorrect switch case executes.
This issue arises when using newlib/picolib libc that includes
sysconf implementation for ARM. With current defaults, the
zephyr sysconf() overrides the original libc sysconf() so
we must ensure proper operation.
We will switch to the #define list just like newlib/picolib.
We can't currently use their unistd.h directly due to a domino
of declaration conflicts.
For the "small" macro implementation, we have to drop using
CONCAT to prevent pre-expansion of the new #defines
Signed-off-by: Nicholas Lowell <Nicholas.Lowell@lexmark.com>
match standard by having input void *buf parameter
for pwrite() marked as const, and avoid any potential
declaration conflicts
Signed-off-by: Nicholas Lowell <Nicholas.Lowell@lexmark.com>
static inline gethostname() in unistd.h can cause declaration collisions.
we should just move it to a normal function definition like the
rest of the network functions.
Signed-off-by: Nicholas Lowell <Nicholas.Lowell@lexmark.com>
When TF-M is enabled, Mbed TLS's MD module (which is used to generate
v5 UUIDs) will dispacth hash operations to TF-M. Unfortunately TF-M
does not support SHA-1 (because it's a weak algorithm) so the
computation will fail.
Signed-off-by: Valerio Setti <vsetti@baylibre.com>
This file is explicitly included by the espressif hal module. It's an
internal file provided by picolibc and newlib. Provide a stub to let
code designed for those to work with the minimal C library.
Signed-off-by: Keith Packard <keithp@keithp.com>
Signed-off-by: Anas Nashif <anas.nashif@intel.com>
Use the newly added timespec util functions to manipulate and
compare timespec structures with overflow detection.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Compiler gets confused and thinks base may be used uninitialized. This
shouldn't be possible, but to make the warning go away, initialize it.
Signed-off-by: Benjamin Cabé <benjamin@zephyrproject.org>
Implement the POSIX_CLOCK_SELECTION Option Group.
This was mostly already done, but compiled / linked in the wrong places.
E.g. pthread_condattr_getclock() and pthread_condattr_setclock() were
in pthread.c and part of POSIX_THREADS_BASE. clock_nanosleep() was in
clock.c and part of POSIX_TIMERS.
This change builds them as part of clock_selection.c with
CONFIG_POSIX_CLOCK_SELECTION.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
gettimeofday() was already implemented, but incorrectly lumped into
POSIX_TIMERS.
putenv() is really just a wrapper around setenv().
The only one left to implement was gethostid() which was relatively
trivial.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Move most implementations to clock_common.c in preparation for
moving gettimeofday() and clock_nanosleep() to different compilation
units.
We also take this as an opportunity to switch from using k_spinlock
to sys_sem.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
To facilitate moving gettimeofday() and clock_nanosleep() to separate
compilation units, make z_clock_nanosleep(), z_clock_gettime(),
and z_clock_settime() convenience functions.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Move most implementations to env-common.c in preparation for adding
putenv.c .
We also take this as an opportunity to switch from using k_spinlock
to sys_sem.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
To facilitate adding putenv in a separate compilation unit,
make z_getenv(), z_getenv_r(), z_setenv(), and z_unsetenv()
convenience functions.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Move creation of last section id from ld linker script LONG() usage to
C code with last section attribute.
The use of `LONG()` works correctly with ld but lld emits a warning
because .last_section section is not allocated as there are no matching
input sections and discards the `LONG()` call, meaning the last section
identifier will not be present in the flash.
> ld.lld: warning: ignoring memory region assignment for
> non-allocatable section '.last_section'
Placing the last section id in `.last_section` in C code makes lld
allocate the memory for the id and thereby create the output section
with the correct output.
Signed-off-by: Torsten Rasmussen <Torsten.Rasmussen@nordicsemi.no>
In uuid.h the function uuid_generate_v5 had a 'namespace'
parameter which is a reserved C++ keywork.
Renamed to 'ns'.
Signed-off-by: Daniel Nicoletti <dantti12@gmail.com>
Picolibc's retargetable locking is based upon having the user own the lock
type (struct __lock, along with typedef struct __lock *_LOCK_T), and then
having the picolibc internal code only refer to this type via the _LOCK_T
pointer typedef, leaving the actual struct undeclared there.
Zephyr wants to use 'struct k_mutex' for this type; the initial picolibc
port handled this by trying to redefine the picolibc locking to use 'void
*' instead of 'struct __lock *' by including '#define _LOCK_T void
*'. Which 'works' as long as the Zephyr code doesn't actually include
picolibc's sys/lock.h.
A recent picolibc change to support POSIX stdio locking has picolibc's
stdio.h including sys/lock.h, which breaks Zephyr's hack.
To fix this, create a real 'struct __lock' type as
struct __lock { struct k_mutex m; };
Define all of the required picolibc locking API with this real type,
referring to the mutex inside without needing any casts.
This required switching the definition of the C library global lock from
K_MUTEX_DEFINE to the open-coded version, STRUCT_SECTION_ITERABLE_ALTERNATE
so that it has the correct type and still lands in the same elf section.
The only mildly inappropriate code left is that lock are allocated using
k_object_alloc(K_OBJ_MUTEX), which "works" because the size of 'struct
__lock` will exactly match the size of 'struct k_mutex' because of C's
struct allocation rules.
Signed-off-by: Keith Packard <keithp@keithp.com>
The code was casting a byte array to 32-bit words without accounting for
alignment. On some platforms (e.g. Arm Cortex-M with multiple load/store
instructions) this will fault. Fix it by using the UNALIGED_GET() macro
whenever the array is passed unaligned.
Signed-off-by: Carles Cufi <carles.cufi@nordicsemi.no>
Update the casting of the 'attr' parameter in pthread_cond_init to use
the correct variable name 'att'. Thanks clang for spotting the typo.
Signed-off-by: Benjamin Cabé <benjamin@zephyrproject.org>
Use the tp_diff() macro as a means of converting an absolute timeout
with respect to a specific clock to a relative timeout, in ms.
Clamp the result between 0 and UINT32_MAX.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Move somewhat useful (but private and internal functions) that deal
with struct timespec to posix_clock.h until there is a better API
available for dealing with operations on struct timespec.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Always require the clockid_t argument to timespec_to_timeoutms() and
remove the unused variant that accepts no clockid_t parameter.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Use CLOCK_REALTIME for the default clock source throughout
the POSIX implementation and tests so that we are
consistent with the specification.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Add a common private function timespec_is_valid() that
can be used to check if a timespec object is valid, and
use that consistently in lib/posix/options.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Add definitions for struct posix_condattr and struct posix_cond, which
are internal variants of the external pthread_condattr_t and
pthread_cond_t types.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Provide a private internal function timespec_to_clock_timeoutms() to
complement timespec_to_timeoutms(). This new variant accepts a clock_t
parameter that allows the caller to specify which clock to use.
The original timespec_to_timeoutms() then just becomes a static inline
wrapper around the original.
Note: timespec_to_clock_timeoutms() and timespec_to_timeoutms() might
have a limited lifespan, since it might make sense to create a
common timespec manipulation library.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
Provide a single declaration of timespec_to_timeoutms() (which is
a private function), in the private header file posix_clock.h .
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
The implementation of POSIX_SEMAPHORES historically used heap allocation
and has not yet been transitioned to a pool allocator.
However, since 590258b381, the default heap-add with CONFIG_POSIX_API
has been reduced from 1 kiB which causes tests/posix/semaphores to fail
due to NULL being returned from a call to k_calloc().
Create a minimal heap-add for the POSIX_SEMAPHORES Option Group.
This can be removed at a future date if semaphores are changed to use
a pooled allocator and fixed-size name, rather than heap allocation.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
`pthread_setspecific` requires a stack in order to allocate the
`struct pthread_key_data` data structure. On 64 bit systems this data
structure is 32 bytes, resulting in 160 bytes usage for the default 5
supported threads.
Signed-off-by: Jordan Yates <jordan@embeint.com>
Don't `imply POSIX_MESSAGE_PASSING` when `POSIX_API=y` as this option
has a non-trivial RAM implication in `HEAP_MEM_POOL_ADD_SIZE_MQUEUE`.
The `mq_*` API is minimally used in-tree, with all users already
enabling the symbol directly.
Signed-off-by: Jordan Yates <jordan@embeint.com>
The signedness of the variable caused undefined behavior because the
sign bit is modified when it gets left-shifted.
This fixes that by changing it to an unsigned variable.
Signed-off-by: Daniel Hajjar <daniel.hajjar16@gmail.com>
If it is not possible to create a timer in timer_create(),
then the timer_obj associated with the timer must be freed.
However, the address of the pointer was mistakenly being
passed to k_mem_slab_free() rather than simply the
the pointer.
This caused a crash in tests which can easily be avoided
by passing the pointer rather than the address of the
pointer.
Signed-off-by: Chris Friedt <cfriedt@tenstorrent.com>
This adds the best HD=4 CRC32 polynomial. The discovery
is the result of research by Philip Koopman of Carnegie
Mellon University, and is well documented at
https://users.ece.cmu.edu/~koopman/crc/.
The user is given the option of trading 1024B of RAM to
improve the execution speed. The unit tests are parameterized
with this KConfig option.
Signed-off-by: JP Hutchins <jp@intercreate.io>
Support parsing and serializing of struct fields that are defined as a
char array.
Use the token JSON_TOK_STRING_BUF to parse and serialize a string for a
char array, for example:
struct foo {
const char *str;
char str_buf[30];
};
struct json_obj_descr foo_descr[] = {
JSON_OBJ_DESCR_PRIM(struct foo, str, JSON_TOK_STRING),
JSON_OBJ_DESCR_PRIM(struct foo, str_buf, JSON_TOK_STRING_BUF),
};
The struct 'json_obj_descr' now has an additional union member 'field'
to store the size of the struct field, which is used with the token
'JSON_TOK_STRING_BUF' to determine the element size.
Fixes: #65200
Signed-off-by: Christoph Winklhofer <cj.winklhofer@gmail.com>
