(resend) [PATCH] Real-Time Preemption, another mutex implementation.
Subsystems (5)
I resend this because I gotten a few mails complaining over missing fields in the previous mail. I hope you will not be offended by my "spam". I oppologise for my lack of understanding of mail-headers.
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)