Skip to contentSkip to conversation

(resend) [PATCH] Real-Time Preemption, another mutex implementation.

PATCH [email protected] 1 participant 1 message Nov 13, 2004

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/arch/i386/Kconfig linux-2.6.9-rc4-mm1-U9.2-priom/arch/i386/Kconfig
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/include/linux/init_task.h linux-2.6.9-rc4-mm1-U9.2-priom/include/linux/init_task.h
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/include/linux/list.h linux-2.6.9-rc4-mm1-U9.2-priom/include/linux/list.h
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/include/linux/mutex.h linux-2.6.9-rc4-mm1-U9.2-priom/include/linux/mutex.h
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/include/linux/realtime_lock.h linux-2.6.9-rc4-mm1-U9.2-priom/include/linux/realtime_lock.h
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/include/linux/sched.h linux-2.6.9-rc4-mm1-U9.2-priom/include/linux/sched.h
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/include/linux/spinlock.h linux-2.6.9-rc4-mm1-U9.2-priom/include/linux/spinlock.h
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/include/linux/wait.h linux-2.6.9-rc4-mm1-U9.2-priom/include/linux/wait.h
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/kernel/fork.c linux-2.6.9-rc4-mm1-U9.2-priom/kernel/fork.c
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/kernel/wait.c linux-2.6.9-rc4-mm1-U9.2-priom/kernel/wait.c
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/Makefile linux-2.6.9-rc4-mm1-U9.2-priom/Makefile
@@ -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
diff -Naur linux-2.6.9-rc4-mm1-U9.2/usr/Makefile linux-2.6.9-rc4-mm1-U9.2-priom/usr/Makefile
@@ -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)