Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

core: implement core_mutex_priority_inheritance #17040

Merged
merged 2 commits into from
Aug 5, 2022
Merged

core: implement core_mutex_priority_inheritance #17040

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
8be03dc
core: implement core_mutex_mitigate_priority_inversion
Mar 9, 2022
3446752
tests/thread_priority_inversion: clean up and automate
Oct 22, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions core/Kconfig
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -39,6 +39,9 @@ config MODULE_CORE_MSG_BUS
help
Messaging Bus API for inter process message broadcast.

config MODULE_CORE_MUTEX_PRIORITY_INHERITANCE
bool "Use priority inheritance to mitigate priority inversion for mutexes"

config MODULE_CORE_PANIC
bool "Kernel crash handling module"
default y
Expand Down
42 changes: 40 additions & 2 deletions core/include/mutex.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -12,6 +12,12 @@
* @ingroup core_sync
* @brief Mutex for thread synchronization
*
* @warning By default, no mitigation against priority inversion is
* employed. If your application is subject to priority inversion
* and cannot tolerate the additional delay this can cause, use
* module `core_mutex_priority_inheritance` to employ
* priority inheritance as mitigation.
*
* Mutex Implementation Basics
* ===========================
*
Expand Down Expand Up @@ -127,6 +133,24 @@ typedef struct {
* @internal
*/
list_node_t queue;
#if defined(DOXYGEN) || defined(MODULE_CORE_MUTEX_PRIORITY_INHERITANCE)
/**
* @brief The current owner of the mutex or `NULL`
* @note Only available if module core_mutex_priority_inheritance
* is used.
*
* If either the mutex is not locked or the mutex is not locked by a thread
* (e.g. because it is used to synchronize a thread with an ISR completion),
* this will have the value of `NULL`.
*/
kernel_pid_t owner;
/**
* @brief Original priority of the owner
* @note Only available if module core_mutex_priority_inheritance
* is used.
*/
uint8_t owner_original_priority;
#endif
} mutex_t;

/**
Expand All @@ -141,16 +165,21 @@ typedef struct {
uint8_t cancelled; /**< Flag whether the mutex has been cancelled */
} mutex_cancel_t;

#ifndef __cplusplus
/**
* @brief Static initializer for mutex_t.
* @details This initializer is preferable to mutex_init().
*/
#define MUTEX_INIT { { NULL } }
# define MUTEX_INIT { .queue = { .next = NULL } }

/**
* @brief Static initializer for mutex_t with a locked mutex
*/
#define MUTEX_INIT_LOCKED { { MUTEX_LOCKED } }
# define MUTEX_INIT_LOCKED { .queue = { .next = MUTEX_LOCKED } }
#else
# define MUTEX_INIT {}
# define MUTEX_INIT_LOCKED { { MUTEX_LOCKED } }
#endif /* __cplusplus */

/**
* @cond INTERNAL
Expand Down Expand Up @@ -231,6 +260,15 @@ static inline int mutex_trylock(mutex_t *mutex)

if (mutex->queue.next == NULL) {
mutex->queue.next = MUTEX_LOCKED;
#ifdef MODULE_CORE_MUTEX_PRIORITY_INHERITANCE
mutex->owner = KERNEL_PID_UNDEF;
thread_t *t = thread_get_active();
/* in case mutex_trylock() is not called from thread context */
if (t) {
mutex->owner = t->pid;
mutex->owner_original_priority = t->priority;
}
#endif
retval = 1;
}
irq_restore(irq_state);
Expand Down
31 changes: 31 additions & 0 deletions core/mutex.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -66,6 +66,17 @@ static inline __attribute__((always_inline)) void _block(mutex_t *mutex,
thread_add_to_list(&mutex->queue, me);
}

#ifdef MODULE_CORE_MUTEX_PRIORITY_INHERITANCE
thread_t *owner = thread_get(mutex->owner);
if ((owner) && (owner->priority > me->priority)) {
DEBUG("PID[%" PRIkernel_pid "] prio of %" PRIkernel_pid
": %u --> %u\n",
thread_getpid(), mutex->owner,
(unsigned)owner->priority, (unsigned)me->priority);
sched_change_priority(owner, me->priority);
}
#endif

irq_restore(irq_state);
thread_yield_higher();
/* We were woken up by scheduler. Waker removed us from queue. */
Expand All @@ -80,6 +91,11 @@ void mutex_lock(mutex_t *mutex)
if (mutex->queue.next == NULL) {
/* mutex is unlocked. */
mutex->queue.next = MUTEX_LOCKED;
#ifdef MODULE_CORE_MUTEX_PRIORITY_INHERITANCE
thread_t *me = thread_get_active();
mutex->owner = me->pid;
mutex->owner_original_priority = me->priority;
#endif
DEBUG("PID[%" PRIkernel_pid "] mutex_lock(): early out.\n",
thread_getpid());
irq_restore(irq_state);
Expand Down Expand Up @@ -108,6 +124,11 @@ int mutex_lock_cancelable(mutex_cancel_t *mc)
if (mutex->queue.next == NULL) {
/* mutex is unlocked. */
mutex->queue.next = MUTEX_LOCKED;
#ifdef MODULE_CORE_MUTEX_PRIORITY_INHERITANCE
thread_t *me = thread_get_active();
mutex->owner = me->pid;
mutex->owner_original_priority = me->priority;
#endif
DEBUG("PID[%" PRIkernel_pid "] mutex_lock_cancelable() early out.\n",
thread_getpid());
irq_restore(irq_state);
Expand Down Expand Up @@ -136,6 +157,16 @@ void mutex_unlock(mutex_t *mutex)
return;
}

#ifdef MODULE_CORE_MUTEX_PRIORITY_INHERITANCE
thread_t *owner = thread_get(mutex->owner);
if ((owner) && (owner->priority != mutex->owner_original_priority)) {
DEBUG("PID[%" PRIkernel_pid "] prio %u --> %u\n",
owner->pid,
(unsigned)owner->priority, (unsigned)owner->priority);
sched_change_priority(owner, mutex->owner_original_priority);
}
#endif
benpicco marked this conversation as resolved.
Show resolved Hide resolved

if (mutex->queue.next == MUTEX_LOCKED) {
mutex->queue.next = NULL;
/* the mutex was locked and no thread was waiting for it */
Expand Down
2 changes: 1 addition & 1 deletion sys/cpp11-compat/include/riot/mutex.hpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -47,7 +47,7 @@ class mutex {
*/
using native_handle_type = mutex_t*;

inline constexpr mutex() noexcept : m_mtx{{0}} {}
inline constexpr mutex() noexcept : m_mtx{} {}
~mutex();

/**
Expand Down
13 changes: 12 additions & 1 deletion tests/thread_priority_inversion/Makefile
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,6 +1,17 @@
include ../Makefile.tests_common

USEMODULE += fmt
USEMODULE += core_mutex_priority_inheritance

USEMODULE += xtimer
ifneq ($(RIOT_CI_BUILD),1)
# For human beings add a busy delay to the mid priority task to make the problem more approachable
FANCY ?= 1
else
# Skip the fancy delay for the CI to not waste precious CI time
FANCY ?= 0
endif

include $(RIOTBASE)/Makefile.include

CFLAGS += -DFANCY=$(FANCY)
CFLAGS += -DTHREAD_STACKSIZE_MAIN=THREAD_STACKSIZE_SMALL
12 changes: 0 additions & 12 deletions tests/thread_priority_inversion/Makefile.ci
View file
Open in desktop

This file was deleted.

89 changes: 51 additions & 38 deletions tests/thread_priority_inversion/README.md
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,45 +1,58 @@
# thread_priority_inversion test application
Priority Inversion
==================

This application uses three threads for demonstrating the
priority inversion problem. In theory, the highest priority thread (**t_high**)
should be scheduled periodically and produce some output:
```
2017-07-17 17:00:29,337 - INFO # t_high: got resource.
...
2017-07-17 17:00:30,343 - INFO # t_high: freeing resource...
```
During this phase of 1s, **t_high** lockes the mutex **res_mtx** which
represents a shared resource. After unlocking the mutex, **t_high** waits 1s
before restaring its cycle again.
Scenario: A low priority thread holds a shared resource when a mid priority and a high
priority thread become runnable. The high priority thread needs exclusive access to the
resource the low priority one is holding and blocks. This mid priority thread does not
compete with the other for resources but takes a long to complete. The scheduler must
prefer the low priority thread over the mid priority thread while it is holding the
resource the high priority thread is waiting for - otherwise the high priority thread
effectively waits for the mid priority thread, which is an inversion of priority.

Output On Failure
-----------------

A low priority thread **t_low** is doing the same. Since both threads sharing
the same resource **res_mtx**, they have to wait for each other until the mutex
is unlocked. On startup, **t_low** starts immediately, while **t_high** waits
0.5s before so that **t_low** allocates the resource first. Together, the output
looks like this:
```
2017-07-17 17:00:28,339 - INFO # t_low: allocating resource...
2017-07-17 17:00:28,339 - INFO # t_low: got resource.
2017-07-17 17:00:28,340 - INFO # t_high: allocating resource...
2017-07-17 17:00:29,337 - INFO # t_low: freeing resource...
2017-07-17 17:00:29,337 - INFO # t_high: got resource.
2017-07-17 17:00:29,338 - INFO # t_low: freed resource.
2017-07-17 17:00:30,343 - INFO # t_high: freeing resource...
2017-07-17 17:00:30,344 - INFO # t_high: freed resource.
2017-07-17 17:00:30,345 - INFO # t_low: allocating resource...
2017-07-17 17:00:30,346 - INFO # t_low: got resource.
...
main(): This is RIOT! (Version: ...)
low priority thread has started
low priority thread started to work on its task
high priority thread has started
mid priority thread has started
mid priority thread started to work on its task
... this ...
... takes ...
... bloody ...
... ages ...
... to ...
... complete ...
mid priority thread is done
low priority thread is done
high priority thread started to work on its task
high priority thread is done
==> Priority inversion occurred
TEST FAILED
```

After 3s, a third thread with medium priority (**t_mid**) is started. This
thread does not touch **res_mtx**, but it runs an infinite loop without leaving
some CPU time to lower priority tasks. This prevents **t_low** from freeing the
resource and thus, **t_high** from running (**Priority Inversion**). In this
situation, the test program output stops with the following lines:

Output On Success
-----------------

```
2017-07-17 17:00:31,335 - INFO # t_mid: doing some stupid stuff...
2017-07-17 17:00:31,340 - INFO # t_high: allocating resource...
main(): This is RIOT! (Version: ...)
low priority thread has started
low priority thread started to work on its task
high priority thread has started
low priority thread is done
high priority thread started to work on its task
high priority thread is done
mid priority thread has started
mid priority thread started to work on its task
... this ...
... takes ...
... bloody ...
... ages ...
... to ...
... complete ...
mid priority thread is done
TEST PASSED
```

If the scheduler contains a mechanism for handling this problem, the program
should continue with output from **t_high**.
Loading