Real-Time Preemption, another mutex implementation.
Subsystems (5)
PATCH 1/1 Real-Time Preemption, another mutex implementation.
I wanted to participate the in making Linux into a real-time system.
I figured that one of the building blocks missing was a mutex with priority inheritance. So I started to build a such as soon as Ingo's patch got stable enough for me to use on my labtop (-U9.2).
Notice that this mutex implementation itself is not coupled too much to the real-time patch. It could be used upstream as it is as well. But the heavy usage of it ofcourse comes from the real-time patch.
Ingo have since implemented one a priority inheritance machanism. I have not looked into it in much detail - I have had fun playing with my own :-) - but I think that the algorithm I have used have some slight advantages in timing:
Let us say each mutex has up to N waiters. Each task holds up to M muteces and the maximum length of the dependency list ("task waits on a mutex which is owned by a task waiting on a mutex, which is owner by a task waiting on a mutex...") is L.
My implementation:
Worst case time with spinlock held: O(N+M). Total time for locking a mutex
O(L*(N+M)). Worst case for releasing a mutex O(M) (with a spinlock held).
Ingo's: Time for giving a mutex to another: O(N*M) with spinlocks held!.
The main reason for this speedup is that I only keep the highest priority waiter on each mutex held by task on the list corresponding to task->pi_waiters and I keep the list sorted.
Furthermore, I can't see (without reading it too carefully) that Ingo's take care of traversing the whole dependency list and boosting all the mutex owners priority.
My implementation have a problem that RTOS people will not be happy about:
On a RTOS the time you have to wait for getting a mutex is worst case the maximum time in which the mutex is locked by a task. In certain cases (SMB or badly written real-time applications on UP) it is 2 times the maximum time a task can lock the mutex. It is still deterministic, though.
There is a full analyzes in a comment in the patch below.
Some people might argue that O(N+M) is not good enough when holding spinlocks - especially if user space futexes shall also use this mechanism. Well, the queus can easily made into full scheduler wait-queues such it will be O(1). But the O(L) can never be avoided as far as I can see. Also notice: At leasst one commercial RTOSs certified for safety critical applications also uses a sorted linked list in muteces.
There is a still a lot to do:
1) Test that it really works. I have only tested that my UP labtop is stable. I need to run some tests veryfying that the priority inheritance mechanism actually works.
2) I haven't tested it on a SMB system as I don't have any.
3) I traverse the dependency list with recursion, risking stack-overflow. It needs to be changed to iteration.
4) Make sure it compiles and works with CONFIG_PRIORITY_MUTEX off :-)
5) Integrate it better into the kernel much, wrt. debugging etc. I don't know the kernel internals - I am brand new to kernel coding - so I am not sure how to do this. I do have a deadlock detection mechanism but it doesn't report stuff very well.
But even though it is far from finshed I don't want to just sit on the work anymore. I think it is best to get the idea out.
Esben
arch/i386/Kconfig +17 -0
@@ -586,6 +586,23 @@ system. Say N if you are unsure. +config PRIORITY_MUTEX + bool "Use priority based muteces" + default y + depends on PREEMPT_REALTIME + help + Use priority sorted mutexes with priority inheritance + +config MUTEX_DEADLOCK_DETECTION + bool "Try to detect deadlocks when taking muteces" + default n + depends on PRIORITY_MUTEX + help + When a mutex is taken extra the taker runs checks wether the task + owning the mutex waits on a mutex and if the owner of this mutex + waits on a mutex etc. If it ends up with waiting on a mutex owned + by the current task we have a deadlock. + config X86_UP_APIC bool "Local APIC support on uniprocessors" if !SMP depends on !(X86_VISWS || X86_VOYAGER)
include/linux/init_task.h +5 -0
@@ -79,6 +79,11 @@ .mm = NULL, \ .active_mm = &init_mm, \ .run_list = LIST_HEAD_INIT(tsk.run_list), \ + .muteces_held = LIST_HEAD_INIT(tsk.muteces_held), \ + .mutex_waiters_lock = RAW_SPIN_LOCK_UNLOCKED, \ + .mutex_waiters = LIST_HEAD_INIT(tsk.mutex_waiters), \ + .waiting_on_mutex_lock = RAW_RW_LOCK_UNLOCKED, \ + .waiting_on_mutex = NULL, \ .time_slice = HZ, \ .tasks = LIST_HEAD_INIT(tsk.tasks), \ .ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children), \
include/linux/list.h +30 -0
@@ -492,6 +492,36 @@for ((pos) = (pos)->next,prefetch ((pos)->next); (pos) != (head); \ (pos) =rcu_dereference ((pos)->next),prefetch ((pos)->next)) + +/** +* list_insert_sorted: Insert in a list by iterating from the beginning and +insert your element when your condition say it is a good place. +Meant for having sorted lists. +* @elem the &struct list_head to insert +* @head: the head for your list. +* @member: list-element in the list: +* @condition the code you use to test wether a place is +ok to elem before element "pos". + */ +#define list_insert_sorted (elem, head, member, condition) \ + do { \ + int found = 0; \ + struct list_head *nhead = (head); \ + typeof(*elem) *pos; \ + list_for_each_entry(pos, nhead, member) { \ + if(condition) { \ + __list_add(&elem->member, pos->member.prev, \ + &pos->member); \ + found = 1; \ + break; \ + } \ + } \ + if(!found) { \ + list_add_tail(&elem->member, nhead); \ + } \ + } while(0); \ + +/* * Double linked lists with a single pointer list head. * Mostly useful for hash tables where the two pointer list head is
include/linux/mutex.h +30 -0
@@ -0,0 +1,30 @@ +#ifndef MUTEX_H +#define MUTEX_H + +#include <linux/wait.h> + +typedef struct mutex_held +{ +struct task_struct *owner; +int times_taken; +int prev_prio; +struct list_head held_list; +}mutex_held_t ; + +typedef struct mutex +{ +int initialized; +mutex_held_t held; +wait_queue_head_t waiters; +}mutex_t ; + +extern void mutex_init (mutex_t *m); +extern void mutex_lock (mutex_t *m); +unsigned long mutex_lock_irqsave (mutex_t *mutex); +void mutex_unlock_wait (mutex_t *mutex); +extern int mutex_trylock (mutex_t *m); +extern void mutex_unlock (mutex_t *m); +extern int mutex_is_locked (mutex_t *m); +extern int atomic_dec_and_mutex_lock (atomic_t *atomic,mutex_t *mutex); + +#endif
include/linux/realtime_lock.h +7 -2
@@ -94,13 +94,18 @@#endif #ifdef CONFIG_PREEMPT_REALTIME - +# ifdef CONFIG_PRIORITY_MUTEX +# include <linux/mutex.h> +typedef mutex_t _mutex_t ; +# define SPIN_LOCK_UNLOCKED (mutex_t) { 0, } +# else typedef struct {unsigned int initialized;struct semaphore lock;unsigned int break_lock; }_mutex_t ; -# define SPIN_LOCK_UNLOCKED (_mutex_t) { 0, } +# define SPIN_LOCK_UNLOCKED (_mutex_t) { 0, } +# endif #else typedef raw_spinlock_t _mutex_t ;# define SPIN_LOCK_UNLOCKED RAW_SPIN_LOCK_UNLOCKED
include/linux/sched.h +28 -0
@@ -583,6 +583,29 @@struct list_head run_list;prio_array_t *array; +#ifdef CONFIG_PRIORITY_MUTEX +int original_prio;/* Priority before getting the first mutex */ + +/* List of held muteces. Can only be manipulated and used +by the task itself */ +struct list_head muteces_held; + +/* List of struct mutex_wait_elem (mutex.c). On this list is only +the highest priority waiters. The list is sorted by priority. +One must have the lock to manipulate the list. The lock is the +inner-most lock, i.e. you can not take any other lock while holding +this lock */ +raw_spinlock_t mutex_waiters_lock; +struct list_head mutex_waiters; + +/* This pointer is set/unset by the task itself while having a write +lock. Others must use read lock while taking it. +This write lock must be taken before the mutex lock */ +struct mutex_wait_elem *waiting_on_mutex; +raw_rwlock_t waiting_on_mutex_lock; +#endif + +unsigned long sleep_avg;long interactive_credit;unsigned long long timestamp, last_ran;
@@ -1227,4 +1250,9 @@#endif /* __KERNEL__ */ +#ifdef CONFIG_PRIORITY_MUTEX +extern void mutex_set_task_priority_up (task_t *p,int new_prio); +extern void mutex_set_task_priority_back_down (int prev_prio); +#endif +#endif
include/linux/spinlock.h +18 -0
@@ -417,6 +417,23 @@extern int __bad_spinlock_type (void ); +#ifdef CONFIG_PRIORITY_MUTEX +#include <linux/mutex.h> +#define _mutex_lock mutex_lock +#define _mutex_lock_bh mutex_lock +#define _mutex_lock_irq mutex_lock +#define _mutex_lock_irqsave mutex_lock_irqsave +#define _mutex_lock_wait mutex_lock_wait +#define _mutex_unlock mutex_unlock +#define _mutex_unlock_wait mutex_unlock_wait +#define _mutex_unlock_bh mutex_unlock +#define _mutex_unlock_irq mutex_unlock +#define _mutex_unlock_irqrestore (m,f) mutex_unlock(m) +#define _mutex_trylock mutex_trylock +#define _mutex_trylock_bh mutex_trylock +#define _mutex_is_locked mutex_is_locked +#define _mutex_lock_init mutex_init +#else /* CONFIG_PRIORITY_MUTEX */ extern void _mutex_lock (_mutex_t *mutex);extern void _mutex_lock_bh (_mutex_t *mutex);extern void _mutex_lock_irq (_mutex_t *mutex);
@@ -431,6 +448,7 @@extern int _mutex_is_locked (_mutex_t *mutex);extern int atomic_dec_and_mutex_lock (atomic_t *atomic,_mutex_t *mutex);extern void _mutex_lock_init (_mutex_t *mutex); +#endif /* CONFIG_PRIORITY_MUTEX */ #define TYPE_EQUAL (lock, type) \ __builtin_types_compatible_p(typeof(lock), type *)
include/linux/wait.h +9 -0
@@ -292,6 +292,15 @@__add_wait_queue_tail (q, wait); } + +/* +* Insert your task into the list sorted by priority. +* Must be called with the spinlock in the wait_queue_head_t held. +*/ +extern void add_wait_queue_sorted_exclusive_locked (wait_queue_head_t *q, +wait_queue_t * wait); + +/* * Must be called with the spinlock in the wait_queue_head_t held. */
kernel/fork.c +8 -0
@@ -172,6 +172,14 @@INIT_LIST_HEAD (&tsk->private_pages); tsk->private_pages_count =0 ; +#ifdef CONFIG_PRIORITY_MUTEX +INIT_LIST_HEAD (&tsk->muteces_held); + tsk->mutex_waiters_lock =RAW_SPIN_LOCK_UNLOCKED ; +INIT_LIST_HEAD (&tsk->mutex_waiters); + tsk->waiting_on_mutex_lock =RAW_RW_LOCK_UNLOCKED ; + tsk->waiting_on_mutex =NULL ; +#endif +/* One for us, one for whoever does the "release_task()" (usually parent) */ atomic_set (&tsk->usage,2 );return tsk;
kernel/mutex.c +800 -2
833 lines not on this page · raw message
kernel/mutex.c.bak +640 -0
640 lines not on this page · raw message
kernel/sched.c +103 -0
121 lines not on this page · raw message
kernel/wait.c +9 -0
@@ -33,6 +33,15 @@ }EXPORT_SYMBOL (add_wait_queue_exclusive); +void add_wait_queue_sorted_exclusive_locked (wait_queue_head_t *q, +wait_queue_t * wait) +{ + wait->flags |=WQ_FLAG_EXCLUSIVE ; +list_insert_sorted (wait, &q->task_list, task_list, + wait->task->prio < pos->task->prio); +} +EXPORT_SYMBOL (add_wait_queue_sorted_exclusive_locked); + void fastcall remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait) {unsigned long flags;
Makefile +1 -1
@@ -1,7 +1,7 @@ VERSION = 2 PATCHLEVEL = 6 SUBLEVEL = 9 -EXTRAVERSION = -rc4-mm1-RT-U9.1 +EXTRAVERSION = -rc4-mm1-RT-U9.2-priom NAME=Zonked Quokka # *DOCUMENTATION*
usr/Makefile +2 -1
@@ -27,7 +27,7 @@ cmd_gen_list = $(shell \ if test -f $(CONFIG_INITRAMFS_SOURCE); then \ if [ $(CONFIG_INITRAMFS_SOURCE) != $@ ]; then \ - echo 'cp -f $(CONFIG_INITRAMFS_SOURCE) $@'; \ + echo 'cp -f -p $(CONFIG_INITRAMFS_SOURCE) $@'; \ else \ echo 'echo Using shipped $@'; \ fi; \
@@ -35,6 +35,7 @@ echo 'scripts/gen_initramfs_list.sh $(CONFIG_INITRAMFS_SOURCE) > $@'; \ else \ echo 'echo Using shipped $@'; \ + cp -f -p $(KBUILD_SRC)/usr/initramfs_list ./usr/; \ fi)
Quoted 3 lines · Esben Nielsen
The main reason for this speedup is that I only keep the highest priority waiter on each mutex held by task on the list corresponding to
task->pi_waitersand I keep the list sorted.
interesting, but it would be nice to see some actual benchmark results as well. You made the 'task blocks' case faster at the expense of making the (more common) 'task doesnt block' case slower. Which one wins depends on benchmarks.
Ingo