2018-01-26 00:24:15 +01:00
|
|
|
/*
|
|
|
|
|
* Copyright (c) 2018 Intel Corporation
|
|
|
|
|
*
|
|
|
|
|
* SPDX-License-Identifier: Apache-2.0
|
|
|
|
|
*/
|
2018-09-14 00:06:35 +02:00
|
|
|
#ifndef ZEPHYR_KERNEL_INCLUDE_KSWAP_H_
|
|
|
|
|
#define ZEPHYR_KERNEL_INCLUDE_KSWAP_H_
|
2018-01-26 00:24:15 +01:00
|
|
|
|
|
|
|
|
#include <ksched.h>
|
2022-05-06 11:04:23 +02:00
|
|
|
#include <zephyr/spinlock.h>
|
2023-05-26 18:24:36 +02:00
|
|
|
#include <zephyr/sys/barrier.h>
|
2018-01-26 00:24:15 +01:00
|
|
|
#include <kernel_arch_func.h>
|
|
|
|
|
|
|
|
|
|
#ifdef CONFIG_STACK_SENTINEL
|
2019-03-08 22:19:05 +01:00
|
|
|
extern void z_check_stack_sentinel(void);
|
2018-01-26 00:24:15 +01:00
|
|
|
#else
|
2019-03-08 22:19:05 +01:00
|
|
|
#define z_check_stack_sentinel() /**/
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_STACK_SENTINEL */
|
2018-01-26 00:24:15 +01:00
|
|
|
|
2024-03-06 21:59:36 +01:00
|
|
|
extern struct k_spinlock _sched_spinlock;
|
2021-02-18 19:15:23 +01:00
|
|
|
|
kernel: Rework SMP irq_lock() compatibility layer
This was wrong in two ways, one subtle and one awful.
The subtle problem was that the IRQ lock isn't actually globally
recursive, it gets reset when you context switch (i.e. a _Swap()
implicitly releases and reacquires it). So the recursive count I was
keeping needs to be per-thread or else we risk deadlock any time we
swap away from a thread holding the lock.
And because part of my brain apparently knew this, there was an
"optimization" in the code that tested the current count vs. zero
outside the lock, on the argument that if it was non-zero we must
already hold the lock. Which would be true of a per-thread counter,
but NOT a global one: the other CPU may be holding that lock, and this
test will tell you *you* do. The upshot is that a recursive
irq_lock() would almost always SUCCEED INCORRECTLY when there was lock
contention. That this didn't break more things is amazing to me.
The rework is actually simpler than the original, thankfully. Though
there are some further subtleties:
* The lock state implied by irq_lock() allows the lock to be
implicitly released on context switch (i.e. you can _Swap() with the
lock held at a recursion level higher than 1, which needs to allow
other processes to run). So return paths into threads from _Swap()
and interrupt/exception exit need to check and restore the global
lock state, spinning as needed.
* The idle loop design specifies a k_cpu_idle() function that is on
common architectures expected to enable interrupts (for obvious
reasons), but there is no place to put non-arch code to wire it into
the global lock accounting. So on SMP, even CPU0 needs to use the
"dumb" spinning idle loop.
Finally this patch contains a simple bugfix too, found by inspection:
the interrupt return code used when CONFIG_SWITCH is enabled wasn't
correctly setting the active flag on the threads, opening up the
potential for a race that might result in a thread being scheduled on
two CPUs simultaneously.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2018-04-12 21:50:05 +02:00
|
|
|
/* In SMP, the irq_lock() is a spinlock which is implicitly released
|
|
|
|
|
* and reacquired on context switch to preserve the existing
|
|
|
|
|
* semantics. This means that whenever we are about to return to a
|
2019-03-08 22:19:05 +01:00
|
|
|
* thread (via either z_swap() or interrupt/exception return!) we need
|
kernel: Rework SMP irq_lock() compatibility layer
This was wrong in two ways, one subtle and one awful.
The subtle problem was that the IRQ lock isn't actually globally
recursive, it gets reset when you context switch (i.e. a _Swap()
implicitly releases and reacquires it). So the recursive count I was
keeping needs to be per-thread or else we risk deadlock any time we
swap away from a thread holding the lock.
And because part of my brain apparently knew this, there was an
"optimization" in the code that tested the current count vs. zero
outside the lock, on the argument that if it was non-zero we must
already hold the lock. Which would be true of a per-thread counter,
but NOT a global one: the other CPU may be holding that lock, and this
test will tell you *you* do. The upshot is that a recursive
irq_lock() would almost always SUCCEED INCORRECTLY when there was lock
contention. That this didn't break more things is amazing to me.
The rework is actually simpler than the original, thankfully. Though
there are some further subtleties:
* The lock state implied by irq_lock() allows the lock to be
implicitly released on context switch (i.e. you can _Swap() with the
lock held at a recursion level higher than 1, which needs to allow
other processes to run). So return paths into threads from _Swap()
and interrupt/exception exit need to check and restore the global
lock state, spinning as needed.
* The idle loop design specifies a k_cpu_idle() function that is on
common architectures expected to enable interrupts (for obvious
reasons), but there is no place to put non-arch code to wire it into
the global lock accounting. So on SMP, even CPU0 needs to use the
"dumb" spinning idle loop.
Finally this patch contains a simple bugfix too, found by inspection:
the interrupt return code used when CONFIG_SWITCH is enabled wasn't
correctly setting the active flag on the threads, opening up the
potential for a race that might result in a thread being scheduled on
two CPUs simultaneously.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2018-04-12 21:50:05 +02:00
|
|
|
* to restore the lock state to whatever the thread's counter
|
|
|
|
|
* expects.
|
|
|
|
|
*/
|
2019-03-08 22:19:05 +01:00
|
|
|
void z_smp_release_global_lock(struct k_thread *thread);
|
kernel: Rework SMP irq_lock() compatibility layer
This was wrong in two ways, one subtle and one awful.
The subtle problem was that the IRQ lock isn't actually globally
recursive, it gets reset when you context switch (i.e. a _Swap()
implicitly releases and reacquires it). So the recursive count I was
keeping needs to be per-thread or else we risk deadlock any time we
swap away from a thread holding the lock.
And because part of my brain apparently knew this, there was an
"optimization" in the code that tested the current count vs. zero
outside the lock, on the argument that if it was non-zero we must
already hold the lock. Which would be true of a per-thread counter,
but NOT a global one: the other CPU may be holding that lock, and this
test will tell you *you* do. The upshot is that a recursive
irq_lock() would almost always SUCCEED INCORRECTLY when there was lock
contention. That this didn't break more things is amazing to me.
The rework is actually simpler than the original, thankfully. Though
there are some further subtleties:
* The lock state implied by irq_lock() allows the lock to be
implicitly released on context switch (i.e. you can _Swap() with the
lock held at a recursion level higher than 1, which needs to allow
other processes to run). So return paths into threads from _Swap()
and interrupt/exception exit need to check and restore the global
lock state, spinning as needed.
* The idle loop design specifies a k_cpu_idle() function that is on
common architectures expected to enable interrupts (for obvious
reasons), but there is no place to put non-arch code to wire it into
the global lock accounting. So on SMP, even CPU0 needs to use the
"dumb" spinning idle loop.
Finally this patch contains a simple bugfix too, found by inspection:
the interrupt return code used when CONFIG_SWITCH is enabled wasn't
correctly setting the active flag on the threads, opening up the
potential for a race that might result in a thread being scheduled on
two CPUs simultaneously.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2018-04-12 21:50:05 +02:00
|
|
|
|
2018-01-26 00:24:15 +01:00
|
|
|
/* context switching and scheduling-related routines */
|
|
|
|
|
#ifdef CONFIG_USE_SWITCH
|
|
|
|
|
|
2023-05-26 18:12:51 +02:00
|
|
|
/* Spin, with the scheduler lock held (!), on a thread that is known
|
|
|
|
|
* (!!) to have released the lock and be on a path where it will
|
|
|
|
|
* deterministically (!!!) reach arch_switch() in very small constant
|
|
|
|
|
* time.
|
|
|
|
|
*
|
|
|
|
|
* This exists to treat an unavoidable SMP race when threads swap --
|
|
|
|
|
* their thread record is in the queue (and visible to other CPUs)
|
|
|
|
|
* before arch_switch() finishes saving state. We must spin for the
|
|
|
|
|
* switch handle before entering a new thread. See docs on
|
|
|
|
|
* arch_switch().
|
|
|
|
|
*
|
|
|
|
|
* Stated differently: there's a chicken and egg bug with the question
|
|
|
|
|
* of "is a thread running or not?". The thread needs to mark itself
|
|
|
|
|
* "not running" from its own context, but at that moment it obviously
|
|
|
|
|
* is still running until it reaches arch_switch()! Locking can't
|
|
|
|
|
* treat this because the scheduler lock can't be released by the
|
|
|
|
|
* switched-to thread, which is going to (obviously) be running its
|
|
|
|
|
* own code and doesn't know it was switched out.
|
2020-01-17 18:32:36 +01:00
|
|
|
*/
|
2023-05-26 18:12:51 +02:00
|
|
|
static inline void z_sched_switch_spin(struct k_thread *thread)
|
2020-01-17 18:32:36 +01:00
|
|
|
{
|
|
|
|
|
#ifdef CONFIG_SMP
|
|
|
|
|
volatile void **shp = (void *)&thread->switch_handle;
|
|
|
|
|
|
|
|
|
|
while (*shp == NULL) {
|
2023-05-26 18:24:36 +02:00
|
|
|
arch_spin_relax();
|
2020-01-17 18:32:36 +01:00
|
|
|
}
|
2023-05-26 18:24:36 +02:00
|
|
|
/* Read barrier: don't allow any subsequent loads in the
|
|
|
|
|
* calling code to reorder before we saw switch_handle go
|
|
|
|
|
* non-null.
|
|
|
|
|
*/
|
|
|
|
|
barrier_dmem_fence_full();
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_SMP */
|
2020-01-17 18:32:36 +01:00
|
|
|
}
|
|
|
|
|
|
2019-11-07 21:43:29 +01:00
|
|
|
/* New style context switching. arch_switch() is a lower level
|
2018-01-26 00:24:15 +01:00
|
|
|
* primitive that doesn't know about the scheduler or return value.
|
|
|
|
|
* Needed for SMP, where the scheduler requires spinlocking that we
|
|
|
|
|
* don't want to have to do in per-architecture assembly.
|
2018-07-24 19:42:12 +02:00
|
|
|
*
|
|
|
|
|
* Note that is_spinlock is a compile-time construct which will be
|
|
|
|
|
* optimized out when this function is expanded.
|
2018-01-26 00:24:15 +01:00
|
|
|
*/
|
2018-07-24 19:42:12 +02:00
|
|
|
static ALWAYS_INLINE unsigned int do_swap(unsigned int key,
|
|
|
|
|
struct k_spinlock *lock,
|
2022-07-19 22:30:17 +02:00
|
|
|
bool is_spinlock)
|
2018-01-26 00:24:15 +01:00
|
|
|
{
|
2018-07-24 19:42:12 +02:00
|
|
|
ARG_UNUSED(lock);
|
2018-01-26 00:24:15 +01:00
|
|
|
struct k_thread *new_thread, *old_thread;
|
|
|
|
|
|
2021-05-14 01:22:03 +02:00
|
|
|
#ifdef CONFIG_SPIN_VALIDATE
|
|
|
|
|
/* Make sure the key acts to unmask interrupts, if it doesn't,
|
|
|
|
|
* then we are context switching out of a nested lock
|
|
|
|
|
* (i.e. breaking the lock of someone up the stack) which is
|
|
|
|
|
* forbidden! The sole exception are dummy threads used
|
|
|
|
|
* during initialization (where we start with interrupts
|
|
|
|
|
* masked and switch away to begin scheduling) and the case of
|
|
|
|
|
* a dead current thread that was just aborted (where the
|
|
|
|
|
* damage was already done by the abort anyway).
|
|
|
|
|
*
|
|
|
|
|
* (Note that this is disabled on ARM64, where system calls
|
|
|
|
|
* can sometimes run with interrupts masked in ways that don't
|
|
|
|
|
* represent lock state. See #35307)
|
|
|
|
|
*/
|
|
|
|
|
# ifndef CONFIG_ARM64
|
|
|
|
|
__ASSERT(arch_irq_unlocked(key) ||
|
|
|
|
|
_current->base.thread_state & (_THREAD_DUMMY | _THREAD_DEAD),
|
|
|
|
|
"Context switching while holding lock!");
|
2024-03-08 12:00:10 +01:00
|
|
|
# endif /* CONFIG_ARM64 */
|
|
|
|
|
#endif /* CONFIG_SPIN_VALIDATE */
|
2021-05-14 01:22:03 +02:00
|
|
|
|
2018-01-26 01:39:35 +01:00
|
|
|
old_thread = _current;
|
2018-01-26 00:24:15 +01:00
|
|
|
|
2019-03-08 22:19:05 +01:00
|
|
|
z_check_stack_sentinel();
|
2018-01-26 00:24:15 +01:00
|
|
|
|
2021-10-22 18:09:22 +02:00
|
|
|
old_thread->swap_retval = -EAGAIN;
|
|
|
|
|
|
2021-02-18 19:15:23 +01:00
|
|
|
/* We always take the scheduler spinlock if we don't already
|
|
|
|
|
* have it. We "release" other spinlocks here. But we never
|
|
|
|
|
* drop the interrupt lock.
|
|
|
|
|
*/
|
2024-03-06 21:59:36 +01:00
|
|
|
if (is_spinlock && lock != NULL && lock != &_sched_spinlock) {
|
2018-07-24 19:42:12 +02:00
|
|
|
k_spin_release(lock);
|
|
|
|
|
}
|
2024-03-06 21:59:36 +01:00
|
|
|
if (!is_spinlock || lock != &_sched_spinlock) {
|
|
|
|
|
(void) k_spin_lock(&_sched_spinlock);
|
2021-02-18 19:15:23 +01:00
|
|
|
}
|
2018-07-24 19:42:12 +02:00
|
|
|
|
2021-02-18 19:15:23 +01:00
|
|
|
new_thread = z_swap_next_thread();
|
2018-01-26 00:24:15 +01:00
|
|
|
|
2018-05-14 23:46:27 +02:00
|
|
|
if (new_thread != old_thread) {
|
kernel/sched: Add "thread_usage" API for thread runtime cycle monitoring
This is an alternate backend that does what THREAD_RUNTIME_STATS is
doing currently, but with a few advantages:
* Correctly synchronized: you can't race against a running thread
(potentially on another CPU!) while querying its usage.
* Realtime results: you get the right answer always, up to timer
precision, even if a thread has been running for a while
uninterrupted and hasn't updated its total.
* Portable, no need for per-architecture code at all for the simple
case. (It leverages the USE_SWITCH layer to do this, so won't work
on older architectures)
* Faster/smaller: minimizes use of 64 bit math; lower overhead in
thread struct (keeps the scratch "started" time in the CPU struct
instead). One 64 bit counter per thread and a 32 bit scratch
register in the CPU struct.
* Standalone. It's a core (but optional) scheduler feature, no
dependence on para-kernel configuration like the tracing
infrastructure.
* More precise: allows architectures to optionally call a trivial
zero-argument/no-result cdecl function out of interrupt entry to
avoid accounting for ISR runtime in thread totals. No configuration
needed here, if it's called then you get proper ISR accounting, and
if not you don't.
For right now, pending unification, it's added side-by-side with the
older API and left as a z_*() internal symbol.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2021-09-27 17:22:43 +02:00
|
|
|
z_sched_usage_switch(new_thread);
|
2019-08-17 06:29:26 +02:00
|
|
|
|
2018-01-29 23:55:20 +01:00
|
|
|
#ifdef CONFIG_SMP
|
2018-05-30 20:23:02 +02:00
|
|
|
_current_cpu->swap_ok = 0;
|
2019-11-07 21:43:29 +01:00
|
|
|
new_thread->base.cpu = arch_curr_cpu()->id;
|
kernel: Rework SMP irq_lock() compatibility layer
This was wrong in two ways, one subtle and one awful.
The subtle problem was that the IRQ lock isn't actually globally
recursive, it gets reset when you context switch (i.e. a _Swap()
implicitly releases and reacquires it). So the recursive count I was
keeping needs to be per-thread or else we risk deadlock any time we
swap away from a thread holding the lock.
And because part of my brain apparently knew this, there was an
"optimization" in the code that tested the current count vs. zero
outside the lock, on the argument that if it was non-zero we must
already hold the lock. Which would be true of a per-thread counter,
but NOT a global one: the other CPU may be holding that lock, and this
test will tell you *you* do. The upshot is that a recursive
irq_lock() would almost always SUCCEED INCORRECTLY when there was lock
contention. That this didn't break more things is amazing to me.
The rework is actually simpler than the original, thankfully. Though
there are some further subtleties:
* The lock state implied by irq_lock() allows the lock to be
implicitly released on context switch (i.e. you can _Swap() with the
lock held at a recursion level higher than 1, which needs to allow
other processes to run). So return paths into threads from _Swap()
and interrupt/exception exit need to check and restore the global
lock state, spinning as needed.
* The idle loop design specifies a k_cpu_idle() function that is on
common architectures expected to enable interrupts (for obvious
reasons), but there is no place to put non-arch code to wire it into
the global lock accounting. So on SMP, even CPU0 needs to use the
"dumb" spinning idle loop.
Finally this patch contains a simple bugfix too, found by inspection:
the interrupt return code used when CONFIG_SWITCH is enabled wasn't
correctly setting the active flag on the threads, opening up the
potential for a race that might result in a thread being scheduled on
two CPUs simultaneously.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2018-04-12 21:50:05 +02:00
|
|
|
|
2018-07-24 19:42:12 +02:00
|
|
|
if (!is_spinlock) {
|
2019-03-08 22:19:05 +01:00
|
|
|
z_smp_release_global_lock(new_thread);
|
2018-07-24 19:42:12 +02:00
|
|
|
}
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_SMP */
|
2020-08-28 01:12:01 +02:00
|
|
|
z_thread_mark_switched_out();
|
2023-05-26 18:12:51 +02:00
|
|
|
z_sched_switch_spin(new_thread);
|
kernel: Add cache coherence management framework
Zephyr SMP kernels need to be able to run on architectures with
incoherent caches. Naive implementation of synchronization on such
architectures requires extensive cache flushing (e.g. flush+invalidate
everything on every spin lock operation, flush on every unlock!) and
is a performance problem.
Instead, many of these systems will have access to separate "coherent"
(usually uncached) and "incoherent" regions of memory. Where this is
available, place all writable data sections by default into the
coherent region. An "__incoherent" attribute flag is defined for data
regions that are known to be CPU-local and which should use the cache.
By default, this is used for stack memory.
Stack memory will be incoherent by default, as by definition it is
local to its current thread. This requires special cache management
on context switch, so an arch API has been added for that.
Also, when enabled, add assertions to strategic places to ensure that
shared kernel data is indeed coherent. We check thread objects, the
_kernel struct, waitq's, timeouts and spinlocks. In practice almost
all kernel synchronization is built on top of these structures, and
any shared data structs will contain at least one of them.
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
Signed-off-by: Anas Nashif <anas.nashif@intel.com>
2020-05-13 17:34:04 +02:00
|
|
|
_current_cpu->current = new_thread;
|
|
|
|
|
|
2021-12-01 03:26:26 +01:00
|
|
|
#ifdef CONFIG_TIMESLICING
|
|
|
|
|
z_reset_time_slice(new_thread);
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_TIMESLICING */
|
2021-12-01 03:26:26 +01:00
|
|
|
|
2021-02-18 19:15:23 +01:00
|
|
|
#ifdef CONFIG_SPIN_VALIDATE
|
2024-03-06 21:59:36 +01:00
|
|
|
z_spin_lock_set_owner(&_sched_spinlock);
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_SPIN_VALIDATE */
|
2021-02-18 19:15:23 +01:00
|
|
|
|
2021-02-24 23:47:35 +01:00
|
|
|
arch_cohere_stacks(old_thread, NULL, new_thread);
|
|
|
|
|
|
kernel/sched: Fix rare SMP deadlock
It was possible with pathological timing (see below) for the scheduler
to pick a cycle of threads on each CPU and enter the context switch
path on all of them simultaneously.
Example:
* CPU0 is idle, CPU1 is running thread A
* CPU1 makes high priority thread B runnable
* CPU1 reaches a schedule point (or returns from an interrupt) and
decides to run thread B instead
* CPU0 simultaneously takes its IPI and returns, selecting thread A
Now both CPUs enter wait_for_switch() to spin, waiting for the context
switch code on the other thread to finish and mark the thread
runnable. So we have a deadlock, each CPU is spinning waiting for the
other!
Actually, in practice this seems not to happen on existing hardware
platforms, it's only exercisable in emulation. The reason is that the
hardware IPI time is much faster than the software paths required to
reach a schedule point or interrupt exit, so CPU1 always selects the
newly scheduled thread and no deadlock appears. I tried for a bit to
make this happen with a cycle of three threads, but it's complicated
to get right and I still couldn't get the timing to hit correctly. In
qemu, though, the IPI is implemented as a Unix signal sent to the
thread running the other CPU, which is far slower and opens the window
to see this happen.
The solution is simple enough: don't store the _current thread in the
run queue until we are on the tail end of the context switch path,
after wait_for_switch() and going to reach the end in guaranteed time.
Note that this requires changing a little logic to handle the yield
case: because we can no longer rely on _current's position in the run
queue to suppress it, we need to do the priority comparison directly
based on the existing "swap_ok" flag (which has always meant
"yielded", and maybe should be renamed).
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2021-02-08 17:28:54 +01:00
|
|
|
#ifdef CONFIG_SMP
|
2023-05-26 18:12:51 +02:00
|
|
|
/* Now add _current back to the run queue, once we are
|
|
|
|
|
* guaranteed to reach the context switch in finite
|
|
|
|
|
* time. See z_sched_switch_spin().
|
kernel/sched: Fix rare SMP deadlock
It was possible with pathological timing (see below) for the scheduler
to pick a cycle of threads on each CPU and enter the context switch
path on all of them simultaneously.
Example:
* CPU0 is idle, CPU1 is running thread A
* CPU1 makes high priority thread B runnable
* CPU1 reaches a schedule point (or returns from an interrupt) and
decides to run thread B instead
* CPU0 simultaneously takes its IPI and returns, selecting thread A
Now both CPUs enter wait_for_switch() to spin, waiting for the context
switch code on the other thread to finish and mark the thread
runnable. So we have a deadlock, each CPU is spinning waiting for the
other!
Actually, in practice this seems not to happen on existing hardware
platforms, it's only exercisable in emulation. The reason is that the
hardware IPI time is much faster than the software paths required to
reach a schedule point or interrupt exit, so CPU1 always selects the
newly scheduled thread and no deadlock appears. I tried for a bit to
make this happen with a cycle of three threads, but it's complicated
to get right and I still couldn't get the timing to hit correctly. In
qemu, though, the IPI is implemented as a Unix signal sent to the
thread running the other CPU, which is far slower and opens the window
to see this happen.
The solution is simple enough: don't store the _current thread in the
run queue until we are on the tail end of the context switch path,
after wait_for_switch() and going to reach the end in guaranteed time.
Note that this requires changing a little logic to handle the yield
case: because we can no longer rely on _current's position in the run
queue to suppress it, we need to do the priority comparison directly
based on the existing "swap_ok" flag (which has always meant
"yielded", and maybe should be renamed).
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2021-02-08 17:28:54 +01:00
|
|
|
*/
|
|
|
|
|
z_requeue_current(old_thread);
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_SMP */
|
2021-02-05 17:15:02 +01:00
|
|
|
void *newsh = new_thread->switch_handle;
|
|
|
|
|
|
kernel/sched: Fix rare SMP deadlock
It was possible with pathological timing (see below) for the scheduler
to pick a cycle of threads on each CPU and enter the context switch
path on all of them simultaneously.
Example:
* CPU0 is idle, CPU1 is running thread A
* CPU1 makes high priority thread B runnable
* CPU1 reaches a schedule point (or returns from an interrupt) and
decides to run thread B instead
* CPU0 simultaneously takes its IPI and returns, selecting thread A
Now both CPUs enter wait_for_switch() to spin, waiting for the context
switch code on the other thread to finish and mark the thread
runnable. So we have a deadlock, each CPU is spinning waiting for the
other!
Actually, in practice this seems not to happen on existing hardware
platforms, it's only exercisable in emulation. The reason is that the
hardware IPI time is much faster than the software paths required to
reach a schedule point or interrupt exit, so CPU1 always selects the
newly scheduled thread and no deadlock appears. I tried for a bit to
make this happen with a cycle of three threads, but it's complicated
to get right and I still couldn't get the timing to hit correctly. In
qemu, though, the IPI is implemented as a Unix signal sent to the
thread running the other CPU, which is far slower and opens the window
to see this happen.
The solution is simple enough: don't store the _current thread in the
run queue until we are on the tail end of the context switch path,
after wait_for_switch() and going to reach the end in guaranteed time.
Note that this requires changing a little logic to handle the yield
case: because we can no longer rely on _current's position in the run
queue to suppress it, we need to do the priority comparison directly
based on the existing "swap_ok" flag (which has always meant
"yielded", and maybe should be renamed).
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2021-02-08 17:28:54 +01:00
|
|
|
if (IS_ENABLED(CONFIG_SMP)) {
|
2023-05-26 18:24:36 +02:00
|
|
|
/* Active threads must have a null here. And
|
|
|
|
|
* it must be seen before the scheduler lock
|
|
|
|
|
* is released!
|
|
|
|
|
*/
|
kernel/sched: Fix rare SMP deadlock
It was possible with pathological timing (see below) for the scheduler
to pick a cycle of threads on each CPU and enter the context switch
path on all of them simultaneously.
Example:
* CPU0 is idle, CPU1 is running thread A
* CPU1 makes high priority thread B runnable
* CPU1 reaches a schedule point (or returns from an interrupt) and
decides to run thread B instead
* CPU0 simultaneously takes its IPI and returns, selecting thread A
Now both CPUs enter wait_for_switch() to spin, waiting for the context
switch code on the other thread to finish and mark the thread
runnable. So we have a deadlock, each CPU is spinning waiting for the
other!
Actually, in practice this seems not to happen on existing hardware
platforms, it's only exercisable in emulation. The reason is that the
hardware IPI time is much faster than the software paths required to
reach a schedule point or interrupt exit, so CPU1 always selects the
newly scheduled thread and no deadlock appears. I tried for a bit to
make this happen with a cycle of three threads, but it's complicated
to get right and I still couldn't get the timing to hit correctly. In
qemu, though, the IPI is implemented as a Unix signal sent to the
thread running the other CPU, which is far slower and opens the window
to see this happen.
The solution is simple enough: don't store the _current thread in the
run queue until we are on the tail end of the context switch path,
after wait_for_switch() and going to reach the end in guaranteed time.
Note that this requires changing a little logic to handle the yield
case: because we can no longer rely on _current's position in the run
queue to suppress it, we need to do the priority comparison directly
based on the existing "swap_ok" flag (which has always meant
"yielded", and maybe should be renamed).
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2021-02-08 17:28:54 +01:00
|
|
|
new_thread->switch_handle = NULL;
|
2023-05-26 18:24:36 +02:00
|
|
|
barrier_dmem_fence_full(); /* write barrier */
|
kernel/sched: Fix rare SMP deadlock
It was possible with pathological timing (see below) for the scheduler
to pick a cycle of threads on each CPU and enter the context switch
path on all of them simultaneously.
Example:
* CPU0 is idle, CPU1 is running thread A
* CPU1 makes high priority thread B runnable
* CPU1 reaches a schedule point (or returns from an interrupt) and
decides to run thread B instead
* CPU0 simultaneously takes its IPI and returns, selecting thread A
Now both CPUs enter wait_for_switch() to spin, waiting for the context
switch code on the other thread to finish and mark the thread
runnable. So we have a deadlock, each CPU is spinning waiting for the
other!
Actually, in practice this seems not to happen on existing hardware
platforms, it's only exercisable in emulation. The reason is that the
hardware IPI time is much faster than the software paths required to
reach a schedule point or interrupt exit, so CPU1 always selects the
newly scheduled thread and no deadlock appears. I tried for a bit to
make this happen with a cycle of three threads, but it's complicated
to get right and I still couldn't get the timing to hit correctly. In
qemu, though, the IPI is implemented as a Unix signal sent to the
thread running the other CPU, which is far slower and opens the window
to see this happen.
The solution is simple enough: don't store the _current thread in the
run queue until we are on the tail end of the context switch path,
after wait_for_switch() and going to reach the end in guaranteed time.
Note that this requires changing a little logic to handle the yield
case: because we can no longer rely on _current's position in the run
queue to suppress it, we need to do the priority comparison directly
based on the existing "swap_ok" flag (which has always meant
"yielded", and maybe should be renamed).
Signed-off-by: Andy Ross <andrew.j.ross@intel.com>
2021-02-08 17:28:54 +01:00
|
|
|
}
|
2024-03-06 21:59:36 +01:00
|
|
|
k_spin_release(&_sched_spinlock);
|
2021-02-05 17:15:02 +01:00
|
|
|
arch_switch(newsh, &old_thread->switch_handle);
|
2021-02-18 19:15:23 +01:00
|
|
|
} else {
|
2024-03-06 21:59:36 +01:00
|
|
|
k_spin_release(&_sched_spinlock);
|
2019-11-30 17:10:25 +01:00
|
|
|
}
|
2018-07-04 15:03:03 +02:00
|
|
|
|
2018-07-24 19:42:12 +02:00
|
|
|
if (is_spinlock) {
|
2019-11-07 21:43:29 +01:00
|
|
|
arch_irq_unlock(key);
|
2018-07-24 19:42:12 +02:00
|
|
|
} else {
|
|
|
|
|
irq_unlock(key);
|
|
|
|
|
}
|
2018-01-26 00:24:15 +01:00
|
|
|
|
2018-12-04 22:26:44 +01:00
|
|
|
return _current->swap_retval;
|
2018-01-26 00:24:15 +01:00
|
|
|
}
|
|
|
|
|
|
2019-03-08 22:19:05 +01:00
|
|
|
static inline int z_swap_irqlock(unsigned int key)
|
2018-07-24 19:42:12 +02:00
|
|
|
{
|
2022-07-19 22:30:17 +02:00
|
|
|
return do_swap(key, NULL, false);
|
2018-07-24 19:42:12 +02:00
|
|
|
}
|
|
|
|
|
|
2019-03-08 22:19:05 +01:00
|
|
|
static inline int z_swap(struct k_spinlock *lock, k_spinlock_key_t key)
|
2018-07-24 19:42:12 +02:00
|
|
|
{
|
2022-07-19 22:30:17 +02:00
|
|
|
return do_swap(key.key, lock, true);
|
2018-07-24 19:42:12 +02:00
|
|
|
}
|
|
|
|
|
|
2019-03-08 22:19:05 +01:00
|
|
|
static inline void z_swap_unlocked(void)
|
2018-07-24 23:39:38 +02:00
|
|
|
{
|
2022-07-19 22:30:17 +02:00
|
|
|
(void) do_swap(arch_irq_lock(), NULL, true);
|
2018-07-24 23:39:38 +02:00
|
|
|
}
|
|
|
|
|
|
2018-01-26 00:24:15 +01:00
|
|
|
#else /* !CONFIG_USE_SWITCH */
|
|
|
|
|
|
2019-11-07 21:43:29 +01:00
|
|
|
extern int arch_swap(unsigned int key);
|
2018-01-26 00:24:15 +01:00
|
|
|
|
2023-05-26 18:12:51 +02:00
|
|
|
static inline void z_sched_switch_spin(struct k_thread *thread)
|
|
|
|
|
{
|
|
|
|
|
ARG_UNUSED(thread);
|
|
|
|
|
}
|
|
|
|
|
|
2019-03-08 22:19:05 +01:00
|
|
|
static inline int z_swap_irqlock(unsigned int key)
|
2018-01-26 00:24:15 +01:00
|
|
|
{
|
2018-09-12 03:33:37 +02:00
|
|
|
int ret;
|
2019-03-08 22:19:05 +01:00
|
|
|
z_check_stack_sentinel();
|
2019-11-07 21:43:29 +01:00
|
|
|
ret = arch_swap(key);
|
2018-07-04 15:03:03 +02:00
|
|
|
return ret;
|
2018-01-26 00:24:15 +01:00
|
|
|
}
|
2018-07-24 19:42:12 +02:00
|
|
|
|
|
|
|
|
/* If !USE_SWITCH, then spinlocks are guaranteed degenerate as we
|
|
|
|
|
* can't be in SMP. The k_spin_release() call is just for validation
|
|
|
|
|
* handling.
|
|
|
|
|
*/
|
2019-03-08 22:19:05 +01:00
|
|
|
static ALWAYS_INLINE int z_swap(struct k_spinlock *lock, k_spinlock_key_t key)
|
2018-07-24 19:42:12 +02:00
|
|
|
{
|
|
|
|
|
k_spin_release(lock);
|
2019-03-08 22:19:05 +01:00
|
|
|
return z_swap_irqlock(key.key);
|
2018-07-24 19:42:12 +02:00
|
|
|
}
|
|
|
|
|
|
2019-03-08 22:19:05 +01:00
|
|
|
static inline void z_swap_unlocked(void)
|
2018-07-24 23:39:38 +02:00
|
|
|
{
|
2019-11-07 21:43:29 +01:00
|
|
|
(void) z_swap_irqlock(arch_irq_lock());
|
2018-07-24 23:39:38 +02:00
|
|
|
}
|
|
|
|
|
|
2020-05-13 01:20:14 +02:00
|
|
|
#endif /* !CONFIG_USE_SWITCH */
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* Set up a "dummy" thread, used at early initialization to launch the
|
|
|
|
|
* first thread on a CPU.
|
|
|
|
|
*
|
|
|
|
|
* Needs to set enough fields such that the context switching code can
|
|
|
|
|
* use it to properly store state, which will just be discarded.
|
|
|
|
|
*
|
|
|
|
|
* The memory of the dummy thread can be completely uninitialized.
|
|
|
|
|
*/
|
|
|
|
|
static inline void z_dummy_thread_init(struct k_thread *dummy_thread)
|
|
|
|
|
{
|
|
|
|
|
dummy_thread->base.thread_state = _THREAD_DUMMY;
|
|
|
|
|
#ifdef CONFIG_SCHED_CPU_MASK
|
|
|
|
|
dummy_thread->base.cpu_mask = -1;
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_SCHED_CPU_MASK */
|
2020-05-13 01:20:14 +02:00
|
|
|
dummy_thread->base.user_options = K_ESSENTIAL;
|
|
|
|
|
#ifdef CONFIG_THREAD_STACK_INFO
|
|
|
|
|
dummy_thread->stack_info.start = 0U;
|
|
|
|
|
dummy_thread->stack_info.size = 0U;
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_THREAD_STACK_INFO */
|
2020-05-13 01:20:14 +02:00
|
|
|
#ifdef CONFIG_USERSPACE
|
2020-08-25 23:42:33 +02:00
|
|
|
dummy_thread->mem_domain_info.mem_domain = &k_mem_domain_default;
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_USERSPACE */
|
kernel: Introduce a way to specify minimum system heap size
There are several subsystems and boards which require a relatively large
system heap (used by k_malloc()) to function properly. This became even
more notable with the recent introduction of the ACPICA library, which
causes ACPI-using boards to require a system heap of up to several
megabytes in size.
Until now, subsystems and boards have tried to solve this by having
Kconfig overlays which modify the default value of HEAP_MEM_POOL_SIZE.
This works ok, except when applications start explicitly setting values
in their prj.conf files:
$ git grep CONFIG_HEAP_MEM_POOL_SIZE= tests samples|wc -l
157
The vast majority of values set by current sample or test applications
is much too small for subsystems like ACPI, which results in the
application not being able to run on such boards.
To solve this situation, we introduce support for subsystems to specify
their own custom system heap size requirement. Subsystems do
this by defining Kconfig options with the prefix HEAP_MEM_POOL_ADD_SIZE_.
The final value of the system heap is the sum of the custom
minimum requirements, or the value existing HEAP_MEM_POOL_SIZE option,
whichever is greater.
We also introduce a new HEAP_MEM_POOL_IGNORE_MIN Kconfig option which
applications can use to force a lower value than what subsystems have
specficied, however this behavior is disabled by default.
Whenever the minimum is greater than the requested value a CMake warning
will be issued in the build output.
This patch ends up modifying several places outside of kernel code,
since the presence of the system heap is no longer detected using a
non-zero CONFIG_HEAP_MEM_POOL_SIZE value, rather it's now detected using
a new K_HEAP_MEM_POOL_SIZE value that's evaluated at build.
Signed-off-by: Johan Hedberg <johan.hedberg@intel.com>
2023-11-29 10:22:39 +01:00
|
|
|
#if (K_HEAP_MEM_POOL_SIZE > 0)
|
2022-01-05 01:04:06 +01:00
|
|
|
k_thread_system_pool_assign(dummy_thread);
|
|
|
|
|
#else
|
|
|
|
|
dummy_thread->resource_pool = NULL;
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* K_HEAP_MEM_POOL_SIZE */
|
2018-01-26 00:24:15 +01:00
|
|
|
|
2022-07-29 05:09:41 +02:00
|
|
|
#ifdef CONFIG_TIMESLICE_PER_THREAD
|
|
|
|
|
dummy_thread->base.slice_ticks = 0;
|
2024-03-08 12:00:10 +01:00
|
|
|
#endif /* CONFIG_TIMESLICE_PER_THREAD */
|
2022-07-29 05:09:41 +02:00
|
|
|
|
2020-05-13 01:20:14 +02:00
|
|
|
_current_cpu->current = dummy_thread;
|
|
|
|
|
}
|
2018-09-14 00:06:35 +02:00
|
|
|
#endif /* ZEPHYR_KERNEL_INCLUDE_KSWAP_H_ */
|
