Skip to contentSkip to conversation

PI-futex: rt-mutex core

PATCH In review Ingo Molnar 4 participants 12 messages Mar 25, 2006 – Apr 1, 2006

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

PATCH 5/10 PI-futex: rt-mutex core

From: Ingo Molnar <[email protected]>

core functions for the rt-mutex subsystem.

----

 include/linux/init_task.h        |    1 
 include/linux/rtmutex.h          |  106 ++++
 include/linux/rtmutex_internal.h |  157 ++++++
 include/linux/sched.h            |   11 
 init/Kconfig                     |    5 
 kernel/Makefile                  |    1 
 kernel/fork.c                    |    3 
 kernel/rtmutex.c                 |  941 +++++++++++++++++++++++++++++++++++++++
 kernel/rtmutex.h                 |   28 +
 9 files changed, 1253 insertions(+)
include/linux/init_task.h +1 -0
Index: linux-pi-futex.mm.q/include/linux/init_task.h
===================================================================
@@ -123,6 +123,7 @@ extern struct group_info init_groups;
 	.journal_info	= NULL,						\
 	.cpu_timers	= INIT_CPU_TIMERS(tsk.cpu_timers),		\
 	.fs_excl	= ATOMIC_INIT(0),				\
+	INIT_RT_MUTEXES(tsk)						\
 }
 
 
include/linux/rtmutex.h new file +106 -0

106 lines not on this page · raw message

include/linux/rtmutex_internal.h new file +157 -0

157 lines not on this page · raw message

include/linux/sched.h +11 -0
Index: linux-pi-futex.mm.q/include/linux/sched.h
===================================================================
@@ -36,6 +36,7 @@
 #include <linux/seccomp.h>
 #include <linux/rcupdate.h>
 #include <linux/futex.h>
+#include <linux/rtmutex.h>
 
 #include <linux/auxvec.h>	/* For AT_VECTOR_SIZE */
 
@@ -858,6 +859,16 @@ struct task_struct {
 	/* Protection of the PI data structures: */
 	spinlock_t pi_lock;
 
+#ifdef CONFIG_RT_MUTEXES
+	/* PI waiters blocked on a rt_mutex held by this task */
+	struct plist_head pi_waiters;
+	/* Deadlock detection and priority inheritance handling */
+	struct rt_mutex_waiter *pi_blocked_on;
+	/* PI locking helpers */
+	struct task_struct *pi_locked_by;
+	struct list_head pi_lock_chain;
+#endif
+
 #ifdef CONFIG_DEBUG_MUTEXES
 	/* mutex deadlock detection */
 	struct mutex_waiter *blocked_on;
init/Kconfig +5 -0
Index: linux-pi-futex.mm.q/init/Kconfig
===================================================================
@@ -361,9 +361,14 @@ config BASE_FULL
 	  kernel data structures. This saves memory on small machines,
 	  but may reduce performance.
 
+config RT_MUTEXES
+	boolean
+	select PLIST
+
 config FUTEX
 	bool "Enable futex support" if EMBEDDED
 	default y
+	select RT_MUTEXES
 	help
 	  Disabling this option will cause the kernel to be built without
 	  support for "fast userspace mutexes".  The resulting kernel may not
kernel/Makefile +1 -0
Index: linux-pi-futex.mm.q/kernel/Makefile
===================================================================
@@ -16,6 +16,7 @@ obj-$(CONFIG_FUTEX) += futex.o
 ifeq ($(CONFIG_COMPAT),y)
 obj-$(CONFIG_FUTEX) += futex_compat.o
 endif
+obj-$(CONFIG_RT_MUTEXES) += rtmutex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
 obj-$(CONFIG_SMP) += cpu.o spinlock.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
kernel/fork.c +3 -0
Index: linux-pi-futex.mm.q/kernel/fork.c
===================================================================
@@ -104,6 +104,7 @@ static kmem_cache_t *mm_cachep;
 void free_task(struct task_struct *tsk)
 {
 	free_thread_info(tsk->thread_info);
+	rt_mutex_debug_task_free(tsk);
 	free_task_struct(tsk);
 }
 EXPORT_SYMBOL(free_task);
@@ -1042,6 +1043,8 @@ static task_t *copy_process(unsigned lon
 	mpol_fix_fork_child_flag(p);
 #endif
 
+	rt_mutex_init_task(p);
+
 #ifdef CONFIG_DEBUG_MUTEXES
 	p->blocked_on = NULL; /* not blocked yet */
 #endif
kernel/rtmutex.c new file +941 -0

941 lines not on this page · raw message

kernel/rtmutex.h new file +28 -0
Index: linux-pi-futex.mm.q/kernel/rtmutex.h
===================================================================
@@ -0,0 +1,28 @@
+/*
+ * RT-Mutexes: blocking mutual exclusion locks with PI support
+ *
+ * started by Ingo Molnar and Thomas Gleixner:
+ *
+ *  Copyright (C) 2004-2006 Red Hat, Inc., Ingo Molnar <[email protected]>
+ *  Copyright (C) 2006, Timesys Corp., Thomas Gleixner <[email protected]>
+ *
+ * This file contains macros used solely by rtmutex.c.
+ * Non-debug version.
+ */
+
+#define __IP_DECL__
+#define __IP__
+#define __RET_IP__
+#define rt_mutex_deadlock_check(l)			(0)
+#define rt_mutex_deadlock_account_lock(m, t)		do { } while (0)
+#define rt_mutex_deadlock_account_unlock(l)		do { } while (0)
+#define debug_rt_mutex_init_waiter(w)			do { } while (0)
+#define debug_rt_mutex_free_waiter(w)			do { } while (0)
+#define debug_rt_mutex_lock(l)				do { } while (0)
+#define debug_rt_mutex_proxy_unlock(l)			do { } while (0)
+#define debug_rt_mutex_unlock(l)			do { } while (0)
+#define debug_rt_mutex_init(m, n)			do { } while (0)
+#define debug_rt_mutex_deadlock(d, a ,l)		do { } while (0)
+#define debug_rt_mutex_print_deadlock(w)		do { } while (0)
+#define debug_rt_mutex_detect_deadlock(d)		(d)
+#define debug_rt_mutex_reset_waiter(w)			do { } while (0)
#1 lore raw
Quoted 7 lines · Ingo Molnar

--- linux-pi-futex.mm.q.orig/init/Kconfig
+++ linux-pi-futex.mm.q/init/Kconfig
@@ -361,9 +361,14 @@ config BASE_FULL
kernel data structures. This saves memory on small machines, but may reduce performance.

Quoted 9 lines

+config RT_MUTEXES
+ boolean
+ select PLIST
+
config FUTEX
bool "Enable futex support" if EMBEDDED
default y
+ select RT_MUTEXES
help

We can't turn these things off unless we also turn off futexes. There goes another 8.7 kbytes...

#3 lore raw
In reply to Ingo Molnar
Quoted 13 lines · Ingo Molnar

From: Ingo Molnar <[email protected]>

include/linux/rtmutex.h new file +10 -0
+/*
+ * The rt_mutex structure
+ *
+ * @wait_lock:	spinlock to protect the structure
+ * @wait_list:	pilist head to enqueue waiters in priority order
+ * @owner:	the mutex owner
+ */
+struct rt_mutex {
+	spinlock_t		wait_lock;
+	struct plist_head	wait_list;

include/linux/rtmutex.h line 38

Quoted 10 lines
include/linux/rtmutex.h new file +10 -0
+	struct task_struct	*owner;
+# ifdef CONFIG_DEBUG_RT_MUTEXES
+	int			save_state;
+	struct list_head	held_list;
+	unsigned long		acquire_ip;
+	const char 		*name, *file;
+	int			line;
+	void			*magic;
+# endif
+};

The indented #-statments make some sense when we're using nested #ifs (although I tend to accidentally-on-purpose delete them). But the above ones aren't even nested..

include/linux/rtmutex.h line 86

Quoted 13 lines
include/linux/rtmutex.h new file +13 -0
+extern void fastcall __rt_mutex_init(struct rt_mutex *lock, const char *name);
+extern void fastcall rt_mutex_destroy(struct rt_mutex *lock);
+
+extern void fastcall rt_mutex_lock(struct rt_mutex *lock);
+extern int fastcall rt_mutex_lock_interruptible(struct rt_mutex *lock,
+						int detect_deadlock);
+extern int fastcall rt_mutex_timed_lock(struct rt_mutex *lock,
+					struct hrtimer_sleeper *timeout,
+					int detect_deadlock);
+
+extern int fastcall rt_mutex_trylock(struct rt_mutex *lock);
+
+extern void fastcall rt_mutex_unlock(struct rt_mutex *lock);

Does fastcall actually do any good? Isn't CONFIG_REGPARM equivalent to
that anyway? It's a bit of an eyesore.

include/linux/rtmutex.h line 96

Quoted 9 lines
include/linux/rtmutex.h new file +9 -0
+#ifdef CONFIG_RT_MUTEXES
+# define rt_mutex_init_task(p)						\
+ do {									\
+	spin_lock_init(&p->pi_lock);					\
+	plist_head_init(&p->pi_waiters);				\
+	p->pi_blocked_on = NULL;					\
+	p->pi_locked_by = NULL;						\
+	INIT_LIST_HEAD(&p->pi_lock_chain);				\
+ } while (0)

Somewhere in there is a C function struggling to escape.

Quoted 1 line

Index: linux-pi-futex.mm.q/include/linux/rtmutex_internal.h

Perhaps this could go in kernel/. If you think that's valuable.

Quoted 6 lines
include/linux/rtmutex_internal.h new file +6 -0
+/*
+ * Plist wrapper macros
+ */
+#define rt_mutex_has_waiters(lock)	(!plist_head_empty(&lock->wait_list))
+
+#define rt_mutex_top_waiter(lock) 	\

include/linux/rtmutex_internal.h line 52

Quoted 10 lines
include/linux/rtmutex_internal.h new file +10 -0
+({ struct rt_mutex_waiter *__w = plist_first_entry(&lock->wait_list, \
+					struct rt_mutex_waiter, list_entry); \
+	BUG_ON(__w->lock != lock);	\
+	__w;				\
+})
+
+#define task_has_pi_waiters(task)	(!plist_head_empty(&task->pi_waiters))
+
+#define task_top_pi_waiter(task) 	\
+	plist_first_entry(&task->pi_waiters, struct rt_mutex_waiter, pi_list_entry)

All of these can become C functions, yes?

Quoted 7 lines
include/linux/rtmutex_internal.h new file +7 -0
+#define rt_mutex_owner(lock)						\
+({									\
+	typecheck(struct rt_mutex *,(lock));				\
+ 	((struct task_struct *)((unsigned long)((lock)->owner) & ~RT_MUTEX_OWNER_MASKALL)); \
+})
+
+#define rt_mutex_real_owner(lock)					\

include/linux/rtmutex_internal.h line 100

Quoted 10 lines
include/linux/rtmutex_internal.h new file +10 -0
+({									\
+	typecheck(struct rt_mutex *,(lock));				\
+ 	((struct task_struct *)((unsigned long)((lock)->owner) & ~RT_MUTEX_HAS_WAITERS)); \
+})
+
+#define rt_mutex_owner_pending(lock)					\
+({									\
+	typecheck(struct rt_mutex *,(lock));				\
+	((unsigned long)((lock)->owner) & RT_MUTEX_OWNER_PENDING);	\
+})

Bizarre. The `typecheck' thingies were added, I assume, because these macros really wanted to be C functions?

include/linux/rtmutex_internal.h line 111

Quoted 10 lines
include/linux/rtmutex_internal.h new file +10 -0
+static inline void rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner,
+				      unsigned long msk)
+{
+	unsigned long val = ((unsigned long) owner) | msk;
+
+	if (rt_mutex_has_waiters(lock))
+		val |= RT_MUTEX_HAS_WAITERS;
+
+	lock->owner = (struct task_struct *)(val);
+}

Might be getting a bit large for inlining.

Quoted 44 lines
kernel/rtmutex.c new file +44 -0
+/*
+ * Lock the full boosting chain.
+ *
+ * If 'try' is set, we have to backout if we hit a owner who is
+ * running its own pi chain operation. We go back and take the slow
+ * path via the pi_conflicts_lock.
+ */
+static int lock_pi_chain(struct rt_mutex *act_lock,
+			 struct rt_mutex_waiter *waiter,
+			 struct list_head *lock_chain,
+			 int try, int detect_deadlock)
+{
+	struct task_struct *owner;
+	struct rt_mutex *nextlock, *lock = act_lock;
+	struct rt_mutex_waiter *nextwaiter;
+
+	/*
+	 * Debugging might turn deadlock detection on, unconditionally:
+	 */
+	detect_deadlock = debug_rt_mutex_detect_deadlock(detect_deadlock);
+
+	for (;;) {
+		owner = rt_mutex_owner(lock);
+
+		/* Check for circular dependencies */
+		if (unlikely(owner->pi_locked_by == current)) {
+			debug_rt_mutex_deadlock(detect_deadlock, waiter, lock);
+			return detect_deadlock ? -EDEADLK : 0;
+		}
+
+		while (!spin_trylock(&owner->pi_lock)) {
+			/*
+			 * Owner runs its own chain. Go back and take
+			 * the slow path
+			 */
+			if (try && owner->pi_locked_by == owner)
+				return -EBUSY;
+			cpu_relax();
+		}
+
+		BUG_ON(owner->pi_locked_by);
+		owner->pi_locked_by = current;
+		BUG_ON(!list_empty(&owner->pi_lock_chain));
+		list_add(&owner->pi_lock_chain, lock_chain);

kernel/rtmutex.c line 137

Quoted 10 lines
kernel/rtmutex.c new file +10 -0
+
+		/*
+		 * When the owner is blocked on a lock, try to take
+		 * the lock:
+		 */
+		nextwaiter = owner->pi_blocked_on;
+
+		/* End of chain? */
+		if (!nextwaiter)
+			return 0;

We return zero with the spinlock held? I guess that's the point of the whole function.

kernel/rtmutex.c line 150

Quoted 12 lines
kernel/rtmutex.c new file +12 -0
+		nextlock = nextwaiter->lock;
+
+		/* Check for circular dependencies: */
+		if (unlikely(nextlock == act_lock ||
+			     rt_mutex_owner(nextlock) == current)) {
+			debug_rt_mutex_deadlock(detect_deadlock, waiter,
+						nextlock);
+			list_del_init(&owner->pi_lock_chain);
+			owner->pi_locked_by = NULL;
+			spin_unlock(&owner->pi_lock);
+			return detect_deadlock ? -EDEADLK : 0;
+		}

But here we can return zero without having locked anything. How does the caller know what locks are held?

This function needs a better covering description, IMO.

kernel/rtmutex.c line 159

Quoted 8 lines
kernel/rtmutex.c new file +8 -0
+		/* Try to get nextlock->wait_lock: */
+		if (unlikely(!spin_trylock(&nextlock->wait_lock))) {
+			list_del_init(&owner->pi_lock_chain);
+			owner->pi_locked_by = NULL;
+			spin_unlock(&owner->pi_lock);
+			cpu_relax();
+			continue;
+		}

All these trylocks and cpu_relaxes are a worry.

Quoted 7 lines
kernel/rtmutex.c new file +7 -0
+/*
+ * Do the priority (un)boosting along the chain:
+ */
+static void adjust_pi_chain(struct rt_mutex *lock,
+			    struct rt_mutex_waiter *waiter,
+			    struct rt_mutex_waiter *top_waiter,
+			    struct list_head *lock_chain)

kernel/rtmutex.c line 225

Quoted 10 lines
kernel/rtmutex.c new file +10 -0
+{
+	struct task_struct *owner = rt_mutex_owner(lock);
+	struct list_head *curr = lock_chain->prev;
+
+	for (;;) {
+		if (top_waiter)
+			plist_del(&top_waiter->pi_list_entry,
+				  &owner->pi_waiters);
+
+		if (waiter && waiter == rt_mutex_top_waiter(lock)) {

rt_mutex_top_waiter() can never return NULL, so the test for NULL could be removed.

kernel/rtmutex.c line 612

Quoted 8 lines
kernel/rtmutex.c new file +8 -0
+/*
+ * Slow path lock function:
+ */
+static int fastcall noinline __sched
+rt_mutex_slowlock(struct rt_mutex *lock, int state,
+		  struct hrtimer_sleeper *timeout,
+		  int detect_deadlock __IP_DECL__)
+{

heh, fastcall slowpath. Why's it noinline?

Quoted 8 lines
kernel/rtmutex.c new file +8 -0
+	struct rt_mutex_waiter waiter;
+	int ret = 0;
+	unsigned long flags;
+
+	debug_rt_mutex_init_waiter(&waiter);
+	waiter.task = NULL;
+
+	spin_lock_irqsave(&lock->wait_lock, flags);

kernel/rtmutex.c line 630

Quoted 10 lines
kernel/rtmutex.c new file +10 -0
+
+	/* Try to acquire the lock again: */
+	if (try_to_take_rt_mutex(lock __IP__)) {
+		spin_unlock_irqrestore(&lock->wait_lock, flags);
+		return 0;
+	}
+
+	BUG_ON(rt_mutex_owner(lock) == current);
+
+	set_task_state(current, state);

set_current_state() (Several more below)

kernel/rtmutex.c line 941

Quoted 9 lines
kernel/rtmutex.c new file +9 -0
+void fastcall __rt_mutex_init(struct rt_mutex *lock, const char *name)
+{
+	lock->owner = NULL;
+	spin_lock_init(&lock->wait_lock);
+	plist_head_init(&lock->wait_list);
+
+	debug_rt_mutex_init(lock, name);
+}
+EXPORT_SYMBOL_GPL(__rt_mutex_init);

What's the export for?

Anyway. Tricky-looking stuff.

#4 lore raw

PATCH 1/1 PI-futex: -V2

Quoted 9 lines · Andrew Morton

Review

Quoted 5 lines
(quoted diff) +5 -0
+struct rt_mutex {
+	spinlock_t		wait_lock;
+	struct plist_head	wait_list;
+	struct task_struct	*owner;
+# ifdef CONFIG_DEBUG_RT_MUTEXES

The indented #-statments make some sense when we're using nested #ifs (although I tend to accidentally-on-purpose delete them). But the above ones aren't even nested..

fixed.

Quoted 5 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+extern void fastcall __rt_mutex_init(struct rt_mutex *lock, const char *name);
+extern void fastcall rt_mutex_destroy(struct rt_mutex *lock);

Does fastcall actually do any good? Isn't CONFIG_REGPARM equivalent to that anyway? It's a bit of an eyesore.

it's not needed - i removed all of them. (This code was started before REGPARM was reliable enough for distros to enable.)

Quoted 11 lines

Review

Quoted 9 lines
(quoted diff) +9 -0
+#ifdef CONFIG_RT_MUTEXES
+# define rt_mutex_init_task(p)						\
+ do {									\
+	spin_lock_init(&p->pi_lock);					\
+	plist_head_init(&p->pi_waiters);				\
+	p->pi_blocked_on = NULL;					\
+	p->pi_locked_by = NULL;						\
+	INIT_LIST_HEAD(&p->pi_lock_chain);				\
+ } while (0)

Somewhere in there is a C function struggling to escape.

ok, i've moved this to fork.c, into an inline function.

Quoted 3 lines
Quoted 1 line

Index: linux-pi-futex.mm.q/include/linux/rtmutex_internal.h

Perhaps this could go in kernel/. If you think that's valuable.

agreed, i moved it. (i also renamed it to rtmutex_common.h, and cleaned it up some more.)

Quoted 4 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+#define task_top_pi_waiter(task) 	\
+	plist_first_entry(&task->pi_waiters, struct rt_mutex_waiter, pi_list_entry)

All of these can become C functions, yes?

agreed, done.

Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+#define rt_mutex_owner_pending(lock)					\
+({									\
+	typecheck(struct rt_mutex *,(lock));				\
+	((unsigned long)((lock)->owner) & RT_MUTEX_OWNER_PENDING);	\
+})

Bizarre. The `typecheck' thingies were added, I assume, because these macros really wanted to be C functions?

correct - i converted them to C inline functions. (These macros are the side-effect of them being in the generic rtmutex.h file for a long time
- and that file gets included early on in the -rt tree, when various structures used by these macros are not defined yet.)

Quoted 4 lines
Quoted 4 lines
(quoted diff) +4 -0
+static inline void rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner,
+				      unsigned long msk)
+{
+	unsigned long val = ((unsigned long) owner) | msk;
Quoted 8 lines

Review

Quoted 6 lines
(quoted diff) +6 -0
+
+	if (rt_mutex_has_waiters(lock))
+		val |= RT_MUTEX_HAS_WAITERS;
+
+	lock->owner = (struct task_struct *)(val);
+}

Might be getting a bit large for inlining.

agreed. I moved these functions to rtmutex.c and uninlined the bigger ones.

Quoted 6 lines

Review

Quoted 3 lines
(quoted diff) +3 -0
+		/* End of chain? */
+		if (!nextwaiter)
+			return 0;

We return zero with the spinlock held? I guess that's the point of the whole function.

correct. It's a "lock this chain" function call.

Quoted 7 lines
Quoted 7 lines
(quoted diff) +7 -0
+		nextlock = nextwaiter->lock;
+
+		/* Check for circular dependencies: */
+		if (unlikely(nextlock == act_lock ||
+			     rt_mutex_owner(nextlock) == current)) {
+			debug_rt_mutex_deadlock(detect_deadlock, waiter,
+						nextlock);
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+			list_del_init(&owner->pi_lock_chain);
+			owner->pi_locked_by = NULL;
+			spin_unlock(&owner->pi_lock);
+			return detect_deadlock ? -EDEADLK : 0;
+		}

But here we can return zero without having locked anything. How does the caller know what locks are held?

this is a loop, and we might have taken other locks up to this point. The locks taken are the ones put into the p->pi_lock_chain list ... which list is walked at lock-release time.

Quoted 1 line

This function needs a better covering description, IMO.

ok, added some more comments explaining it better.

Quoted 10 lines

Review

Quoted 8 lines
(quoted diff) +8 -0
+		/* Try to get nextlock->wait_lock: */
+		if (unlikely(!spin_trylock(&nextlock->wait_lock))) {
+			list_del_init(&owner->pi_lock_chain);
+			owner->pi_locked_by = NULL;
+			spin_unlock(&owner->pi_lock);
+			cpu_relax();
+			continue;
+		}

All these trylocks and cpu_relaxes are a worry.

this is a typical lock-order solution we use in other places in the
kernel: the common locking order is ->wait_lock + ->pi_lock - but in this case we have to take ->pi_lock first - hence the ->trylock, pi_lock-release, cpu_relax() and redoing of the pi_lock.

Quoted 12 lines
Quoted 12 lines
(quoted diff) +12 -0
+/*
+ * Do the priority (un)boosting along the chain:
+ */
+static void adjust_pi_chain(struct rt_mutex *lock,
+			    struct rt_mutex_waiter *waiter,
+			    struct rt_mutex_waiter *top_waiter,
+			    struct list_head *lock_chain)
+{
+	struct task_struct *owner = rt_mutex_owner(lock);
+	struct list_head *curr = lock_chain->prev;
+
+	for (;;) {
Quoted 8 lines

Review

Quoted 5 lines
(quoted diff) +5 -0
+		if (top_waiter)
+			plist_del(&top_waiter->pi_list_entry,
+				  &owner->pi_waiters);
+
+		if (waiter && waiter == rt_mutex_top_waiter(lock)) {

rt_mutex_top_waiter() can never return NULL, so the test for NULL could be removed.

it might be NULL if adjust_pi_chain() is called from remove_waiter(), and next_waiter there is NULL (because !rt_mutex_has_waiters() after the removal of the current waiter).

Quoted 10 lines

Review

Quoted 8 lines
(quoted diff) +8 -0
+/*
+ * Slow path lock function:
+ */
+static int fastcall noinline __sched
+rt_mutex_slowlock(struct rt_mutex *lock, int state,
+		  struct hrtimer_sleeper *timeout,
+		  int detect_deadlock __IP_DECL__)
+{

heh, fastcall slowpath. Why's it noinline?

leftovers of cycle-level optimizations from the -rt tree. I've removed it, it's not needed anymore.

Quoted 3 lines

Review

Quoted 1 line
(quoted diff) +1 -0
+	set_task_state(current, state);

set_current_state() (Several more below)

fixed.

Quoted 3 lines
Quoted 1 line

+EXPORT_SYMBOL_GPL(__rt_mutex_init);

What's the export for?

for the -rt tree. (latest -rt trees are based on this patch-queue and rt-mutex subsystem as-is) Right now the rt-tester code uses it - which isnt modular (but it could be made modular). Should i remove the export?

find below a delta patch to the current patch-queue you have in -mm. Most of the patches in the -V2 queue were changed, so there are only two
options: a full updated queue or to add this all-included update patch.

this update includes the fixes for the things you noticed, plus a couple of more cleanups, and a fix from Esben Nielsen for the PI logic. I have merged the -V2 queue to the -rt tree [and have released 2.6.16-rt8] and have re-checked the PI code under load - it's all looking good.

Ingo

------
From: Ingo Molnar <[email protected]>

clean up the code as per Andrew's suggestions:

- '# ifdef' => '#ifdef'
- fastcall removal
- lots of macro -> C function conversions
- move rtmutex_internals.h to kernel/rtmutex_common.h
- uninline two larger functions
- remove noinline
- explain locking better
- set_task_state(current, state) => set_current_state(state)

- fix the PI code (Esben Nielsen)

 include/linux/rtmutex_internal.h |  187 ---------------------------------------
 linux/include/linux/rtmutex.h    |   29 ++----
 linux/kernel/fork.c              |   11 ++
 linux/kernel/futex.c             |    3 
 linux/kernel/rtmutex-debug.c     |    2 
 linux/kernel/rtmutex-debug.h     |    2 
 linux/kernel/rtmutex.c           |  116 ++++++++++++++++++++----
 linux/kernel/rtmutex_common.h    |  123 +++++++++++++++++++++++++
 linux/kernel/sched.c             |    2 
 9 files changed, 247 insertions(+), 228 deletions(-)
include/linux/rtmutex.h +10 -19
Index: linux/include/linux/rtmutex.h
===================================================================
@@ -27,14 +27,14 @@ struct rt_mutex {
 	spinlock_t		wait_lock;
 	struct plist_head	wait_list;
 	struct task_struct	*owner;
-# ifdef CONFIG_DEBUG_RT_MUTEXES
+#ifdef CONFIG_DEBUG_RT_MUTEXES
 	int			save_state;
 	struct list_head	held_list;
 	unsigned long		acquire_ip;
 	const char 		*name, *file;
 	int			line;
 	void			*magic;
-# endif
+#endif
 };
 
 struct rt_mutex_waiter;
@@ -79,40 +79,31 @@ struct hrtimer_sleeper;
  *
  * Returns 1 if the mutex is locked, 0 if unlocked.
  */
-static inline int fastcall rt_mutex_is_locked(struct rt_mutex *lock)
+static inline int rt_mutex_is_locked(struct rt_mutex *lock)
 {
 	return lock->owner != NULL;
 }
 
-extern void fastcall __rt_mutex_init(struct rt_mutex *lock, const char *name);
-extern void fastcall rt_mutex_destroy(struct rt_mutex *lock);
+extern void __rt_mutex_init(struct rt_mutex *lock, const char *name);
+extern void rt_mutex_destroy(struct rt_mutex *lock);
 
-extern void fastcall rt_mutex_lock(struct rt_mutex *lock);
-extern int fastcall rt_mutex_lock_interruptible(struct rt_mutex *lock,
+extern void rt_mutex_lock(struct rt_mutex *lock);
+extern int rt_mutex_lock_interruptible(struct rt_mutex *lock,
 						int detect_deadlock);
-extern int fastcall rt_mutex_timed_lock(struct rt_mutex *lock,
+extern int rt_mutex_timed_lock(struct rt_mutex *lock,
 					struct hrtimer_sleeper *timeout,
 					int detect_deadlock);
 
-extern int fastcall rt_mutex_trylock(struct rt_mutex *lock);
+extern int rt_mutex_trylock(struct rt_mutex *lock);
 
-extern void fastcall rt_mutex_unlock(struct rt_mutex *lock);
+extern void rt_mutex_unlock(struct rt_mutex *lock);
 
 #ifdef CONFIG_RT_MUTEXES
-# define rt_mutex_init_task(p)						\
- do {									\
-	spin_lock_init(&p->pi_lock);					\
-	plist_head_init(&p->pi_waiters);				\
-	p->pi_blocked_on = NULL;					\
-	p->pi_locked_by = NULL;						\
-	INIT_LIST_HEAD(&p->pi_lock_chain);				\
- } while (0)
 # define INIT_RT_MUTEXES(tsk)						\
 	.pi_waiters	= PLIST_HEAD_INIT(tsk.pi_waiters),		\
 	.pi_lock	= SPIN_LOCK_UNLOCKED,				\
 	.pi_lock_chain	= LIST_HEAD_INIT(tsk.pi_lock_chain),
 #else
-# define rt_mutex_init_task(p)		do { } while (0)
 # define INIT_RT_MUTEXES(tsk)
 #endif
 
include/linux/rtmutex_internal.h deleted +0 -187

187 lines not on this page · raw message

kernel/fork.c +11 -0
Index: linux/kernel/fork.c
===================================================================
@@ -922,6 +922,17 @@ asmlinkage long sys_set_tid_address(int 
 	return current->pid;
 }
 
+static inline void rt_mutex_init_task(struct task_struct *p)
+{
+#ifdef CONFIG_RT_MUTEXES
+	spin_lock_init(&p->pi_lock);
+	plist_head_init(&p->pi_waiters);
+	p->pi_blocked_on = NULL;
+	p->pi_locked_by = NULL;
+	INIT_LIST_HEAD(&p->pi_lock_chain);
+#endif
+}
+
 /*
  * This creates a new process as a copy of the old one,
  * but does not actually start it yet.
kernel/futex.c +2 -1
Index: linux/kernel/futex.c
===================================================================
@@ -48,9 +48,10 @@
 #include <linux/pagemap.h>
 #include <linux/syscalls.h>
 #include <linux/signal.h>
-#include <linux/rtmutex_internal.h>
 #include <asm/futex.h>
 
+#include "rtmutex_common.h"
+
 #define FUTEX_HASHBITS (CONFIG_BASE_SMALL ? 4 : 8)
 
 /*
kernel/rtmutex-debug.c +1 -1
Index: linux/kernel/rtmutex-debug.c
===================================================================
@@ -27,7 +27,7 @@
 #include <linux/plist.h>
 #include <linux/fs.h>
 
-#include <linux/rtmutex_internal.h>
+#include "rtmutex_common.h"
 
 #ifdef CONFIG_DEBUG_RT_MUTEXES
 # include "rtmutex-debug.h"
kernel/rtmutex-debug.h +0 -2
Index: linux/kernel/rtmutex-debug.h
===================================================================
@@ -9,8 +9,6 @@
  * This file contains macros used solely by rtmutex.c. Debug version.
  */
 
-#include <linux/rtmutex_internal.h>
-
 #define __IP_DECL__		, unsigned long ip
 #define __IP__			, ip
 #define __RET_IP__		, (unsigned long)__builtin_return_address(0)
kernel/rtmutex.c +99 -17

226 lines not on this page · raw message

kernel/rtmutex_common.h new file +123 -0

123 lines not on this page · raw message

kernel/sched.c +1 -1
Index: linux/kernel/sched.c
===================================================================
@@ -3895,7 +3895,7 @@ static void __setscheduler(struct task_s
 	p->rt_priority = prio;
 
 	p->normal_prio = normal_prio(p);
-	/* we are holding p->pi_list already */
+	/* we are holding p->pi_lock already */
 	p->prio = rt_mutex_getprio(p);
 	/*
 	 * SCHED_BATCH tasks are treated as perpetual CPU hogs:
#5 lore raw

Re: [patch] PI-futex: -V2

Quoted 11 lines · Ingo Molnar
Quoted 10 lines

Review

Quoted 7 lines
(quoted diff) +6 -0
+	for (;;) {
+		if (top_waiter)
+			plist_del(&top_waiter->pi_list_entry,
+				  &owner->pi_waiters);
+
+		if (waiter && waiter == rt_mutex_top_waiter(lock)) {

rt_mutex_top_waiter() can never return NULL, so the test for NULL could be removed.

Quoted 3 lines

it might be NULL if adjust_pi_chain() is called from remove_waiter(), and next_waiter there is NULL (because !rt_mutex_has_waiters() after the removal of the current waiter).

Yes, `waiter' might be NULL. But rt_mutex_top_waiter() will never return NULL. So it might be possible to just do

	if (waiter == rt_mutex_top_waiter(lock))

Which might actually be less efficient, and more obscure. Just pointing it out.

#7 lore raw

PATCH 1/1 PI-futex: -V3

In reply to Ingo Molnar

this is version -V3 of the PI-futex patchset (ontop of current -mm plus the -V2 delta patch). Changes since -V2:

- do the -> set_current_state() cleanups for real
- make plist_add() more readable
- whitespace cleanups in kernel/futex.c
- further cleanups in rtmutex_common.h
- fix cornercase race in the PI-locking code (it triggered in the -rt tree)

----

 kernel/futex.c          |    4 
 kernel/rtmutex.c        |  245 +++++++++++++++++++++++++-----------------------
 kernel/rtmutex_common.h |    6 -
 lib/plist.c             |    3 
 4 files changed, 136 insertions(+), 122 deletions(-)
kernel/futex.c +2 -2
Index: linux-pi-futex.mm.q/kernel/futex.c
===================================================================
@@ -425,7 +425,7 @@ void exit_pi_state_list(struct task_stru
 	 */
 	spin_lock(&curr->pi_lock);
 	while (!list_empty(head)) {
-		
+
 		next = head->next;
 		pi_state = list_entry(next, struct futex_pi_state, list);
 		key = pi_state->key;
@@ -439,7 +439,7 @@ void exit_pi_state_list(struct task_stru
 			spin_unlock(&hb->lock);
 			continue;
 		}
-		
+
 		list_del_init(&pi_state->list);
 
 		WARN_ON(pi_state->owner != curr);
kernel/rtmutex.c +129 -116

337 lines not on this page · raw message

kernel/rtmutex_common.h +3 -3
Index: linux-pi-futex.mm.q/kernel/rtmutex_common.h
===================================================================
@@ -98,18 +98,18 @@ task_top_pi_waiter(struct task_struct *p
 static inline struct task_struct *rt_mutex_owner(struct rt_mutex *lock)
 {
 	return (struct task_struct *)
-		((unsigned long)((lock)->owner) & ~RT_MUTEX_OWNER_MASKALL);
+		((unsigned long)lock->owner & ~RT_MUTEX_OWNER_MASKALL);
 }
 
 static inline struct task_struct *rt_mutex_real_owner(struct rt_mutex *lock)
 {
  	return (struct task_struct *)
-		((unsigned long)((lock)->owner) & ~RT_MUTEX_HAS_WAITERS);
+		((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS);
 }
 
 static inline unsigned long rt_mutex_owner_pending(struct rt_mutex *lock)
 {
-	return ((unsigned long)((lock)->owner) & RT_MUTEX_OWNER_PENDING);
+	return (unsigned long)lock->owner & RT_MUTEX_OWNER_PENDING;
 }
 
 /*
lib/plist.c +2 -1
Index: linux-pi-futex.mm.q/lib/plist.c
===================================================================
@@ -38,7 +38,7 @@ void plist_add(struct plist_node *node, 
 
 	WARN_ON(!plist_node_empty(node));
 
-	list_for_each_entry(iter, &head->prio_list, plist.prio_list)
+	list_for_each_entry(iter, &head->prio_list, plist.prio_list) {
 		if (node->prio < iter->prio)
 			goto lt_prio;
 		else if (node->prio == iter->prio) {
@@ -46,6 +46,7 @@ void plist_add(struct plist_node *node, 
 					struct plist_node, plist.prio_list);
 			goto eq_prio;
 		}
+	}
 
 lt_prio:
 	list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
#6 lore raw

Re: [patch] PI-futex: -V2

In reply to Andrew Morton
Quoted 12 lines · Andrew Morton
Quoted 11 lines · Ingo Molnar
Quoted 10 lines

Review

Quoted 7 lines
(quoted diff) +6 -0
+	for (;;) {
+		if (top_waiter)
+			plist_del(&top_waiter->pi_list_entry,
+				  &owner->pi_waiters);
+
+		if (waiter && waiter == rt_mutex_top_waiter(lock)) {

rt_mutex_top_waiter() can never return NULL, so the test for NULL could be removed.

Quoted 8 lines
Quoted 3 lines

it might be NULL if adjust_pi_chain() is called from remove_waiter(), and next_waiter there is NULL (because !rt_mutex_has_waiters() after the removal of the current waiter).

Yes, `waiter' might be NULL. But rt_mutex_top_waiter() will never return NULL. So it might be possible to just do

	if (waiter == rt_mutex_top_waiter(lock))

ah, indeed, you are right.

Quoted 2 lines

Which might actually be less efficient, and more obscure. Just pointing it out.

ok, i left it as-is for now.

Ingo

#2 lore raw
In reply to Andrew Morton
Quoted 18 lines · Andrew Morton
Quoted 7 lines · Ingo Molnar

--- linux-pi-futex.mm.q.orig/init/Kconfig
+++ linux-pi-futex.mm.q/init/Kconfig
@@ -361,9 +361,14 @@ config BASE_FULL
kernel data structures. This saves memory on small machines, but may reduce performance.

Quoted 9 lines

+config RT_MUTEXES
+ boolean
+ select PLIST
+
config FUTEX
bool "Enable futex support" if EMBEDDED
default y
+ select RT_MUTEXES
help

Quoted 2 lines

We can't turn these things off unless we also turn off futexes. There goes another 8.7 kbytes...

do we want to make the futex API so splintered via .config? 8.7 kbytes on SMP boxes, a bit less on UP boxes. RAM-starving embedded platforms will want to turn off all things futexes i guess.

Ingo

#8 lore raw

[patch-mm2] PI-futex: fix timeout race

In reply to Ingo Molnar

The futex code has consequently the same timeout race as generic sleeper based nanosleep. Call hrtimer_cancel() unconditionally.

kernel/rtmutex.c +1 -1
Index: linux-2.6.16-mm2/kernel/rtmutex.c
===================================================================
@@ -789,7 +789,7 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 	spin_unlock_irqrestore(&lock->wait_lock, flags);
 
 	/* Remove pending timer: */
-	if (unlikely(timeout && timeout->task))
+	if (unlikely(timeout))
 		hrtimer_cancel(&timeout->timer);
 
 	/*
#9 lore raw

PATCH 1/1 PI-futex patchset: -V4

In reply to Ingo Molnar

this is version -V4 of the PI-futex patchset (ontop of current -mm2, which includes -V3.)

A clean queue of split-up patches can be found at:

http://redhat.com/~mingo/PI-futex-patches/PI-futex-patches-V4.tar.gz

the -V4 codebase has been tested on the glibc code (all testcases pass) and under load as well. (The -V4 code is included in the 2.6.16-rt12 code as well that i released earlier today.)

Changes since -V3:

- added Esben Nielsen's PI locking code, Thomas Gleixner made it work in cornercases and under load. This is significantly simpler (it removes 50 lines of code from rtmutex.c). The main difference is that instead of holding all locks along a dependency chain, this code propagates PI priorities (and detects deadlocks) by holding at most two locks at once, and by being preemptible between such steps.

- Jakub Jelinek did a detailed review of the new futex code and found some new races, which Thomas Gleixner fixed.

- to fix a pthread_mutex_trylock() related race, FUTEX_TRYLOCK_PI has been added (Thomas Gleixner)

- documentation fixes based on feedback from Tim Bird

- added Documentation/pi-futex.txt (in addition to rt-mutex.txt)

- added the plist debugging patch (which was part of -rt but wasnt part of the pi-futex queue before). This caught a couple of SMP bugs in the past.

- implemented more scalable held-locks debugging - it's now a per-task list of held locks, instead of a global list. This is similarly effective to the global list, but much more scalable. (This approach will also be added to the stock kernel/mutex.c code.)

- do not fiddle with irq flags in rtmutex.c - it's not needed.

- clone/fork fix: do not let parent's potential PI priority 'leak' into child threads or processes.

- added /proc/sys/kernel/max_lock_depth with a default limit of 1024, to limit the amount of deadlock-checking the kernel will do.

- small enhancement to the t3-l1-pi-signal.tst testcase.

--

 Documentation/rtmutex.txt                                 |   60 -
 linux-pi-futex.mm.q/Documentation/pi-futex.txt            |  121 +++
 linux-pi-futex.mm.q/Documentation/robust-futexes.txt      |    2 
 linux-pi-futex.mm.q/Documentation/rt-mutex.txt            |   74 +
 linux-pi-futex.mm.q/include/linux/futex.h                 |    1 
 linux-pi-futex.mm.q/include/linux/rtmutex.h               |   16 
 linux-pi-futex.mm.q/include/linux/sched.h                 |    9 
 linux-pi-futex.mm.q/include/linux/sysctl.h                |    1 
 linux-pi-futex.mm.q/kernel/fork.c                         |    8 
 linux-pi-futex.mm.q/kernel/futex.c                        |   88 +-
 linux-pi-futex.mm.q/kernel/rtmutex-debug.c                |  186 ++--
 linux-pi-futex.mm.q/kernel/rtmutex-debug.h                |    9 
 linux-pi-futex.mm.q/kernel/rtmutex.c                      |  560 +++++---------
 linux-pi-futex.mm.q/kernel/rtmutex.h                      |    3 
 linux-pi-futex.mm.q/kernel/sched.c                        |    8 
 linux-pi-futex.mm.q/kernel/sysctl.c                       |   15 
 linux-pi-futex.mm.q/scripts/rt-tester/t3-l1-pi-signal.tst |    3 
 17 files changed, 631 insertions(+), 533 deletions(-)
Documentation/pi-futex.txt new file +121 -0
Index: linux-pi-futex.mm.q/Documentation/pi-futex.txt
===================================================================
@@ -0,0 +1,121 @@
+Lightweight PI-futexes
+----------------------
+
+We are calling them lightweight for 3 reasons:
+
+ - in the user-space fastpath a PI-enabled futex involves no kernel work
+   (or any other PI complexity) at all. No registration, no extra kernel
+   calls - just pure fast atomic ops in userspace.
+
+ - even in the slowpath, the system call and scheduling pattern is very
+   similar to normal futexes.
+
+ - the in-kernel PI implementation is streamlined around the mutex
+   abstraction, with strict rules that keep the implementation
+   relatively simple: only a single owner may own a lock (i.e. no
+   read-write lock support), only the owner may unlock a lock, no
+   recursive locking, etc.
+
+Priority Inheritance - why?
+---------------------------
+
+The short reply: user-space PI helps achieving/improving determinism for
+user-space applications. In the best-case, it can help achieve
+determinism and well-bound latencies. Even in the worst-case, PI will
+improve the statistical distribution of locking related application
+delays.
+
+The longer reply:
+-----------------
+
+Firstly, sharing locks between multiple tasks is a common programming
+technique that often cannot be replaced with lockless algorithms. As we
+can see it in the kernel [which is a quite complex program in itself],
+lockless structures are rather the exception than the norm - the current
+ratio of lockless vs. locky code for shared data structures is somewhere
+between 1:10 and 1:100. Lockless is hard, and the complexity of lockless
+algorithms often endangers to ability to do robust reviews of said code.
+I.e. critical RT apps often choose lock structures to protect critical
+data structures, instead of lockless algorithms. Furthermore, there are
+cases (like shared hardware, or other resource limits) where lockless
+access is mathematically impossible.
+
+Media players (such as Jack) are an example of reasonable application
+design with multiple tasks (with multiple priority levels) sharing
+short-held locks: for example, a highprio audio playback thread is
+combined with medium-prio construct-audio-data threads and low-prio
+display-colory-stuff threads. Add video and decoding to the mix and
+we've got even more priority levels.
+
+So once we accept that synchronization objects (locks) are an
+unavoidable fact of life, and once we accept that multi-task userspace
+apps have a very fair expectation of being able to use locks, we've got
+to think about how to offer the option of a deterministic locking
+implementation to user-space.
+
+Most of the technical counter-arguments against doing priority
+inheritance only apply to kernel-space locks. But user-space locks are
+different, there we cannot disable interrupts or make the task
+non-preemptible in a critical section, so the 'use spinlocks' argument
+does not apply (user-space spinlocks have the same priority inversion
+problems as other user-space locking constructs). Fact is, pretty much
+the only technique that currently enables good determinism for userspace
+locks (such as futex-based pthread mutexes) is priority inheritance:
+
+Currently (without PI), if a high-prio and a low-prio task shares a lock
+[this is a quite common scenario for most non-trivial RT applications],
+even if all critical sections are coded carefully to be deterministic
+(i.e. all critical sections are short in duration and only execute a
+limited number of instructions), the kernel cannot guarantee any
+deterministic execution of the high-prio task: any medium-priority task
+could preempt the low-prio task while it holds the shared lock and
+executes the critical section, and could delay it indefinitely.
+
+Implementation:
+---------------
+
+As mentioned before, the userspace fastpath of PI-enabled pthread
+mutexes involves no kernel work at all - they behave quite similarly to
+normal futex-based locks: a 0 value means unlocked, and a value==TID
+means locked. (This is the same method as used by list-based robust
+futexes.) Userspace uses atomic ops to lock/unlock these mutexes without
+entering the kernel.
+
+To handle the slowpath, we have added two new futex ops:
+
+  FUTEX_LOCK_PI
+  FUTEX_UNLOCK_PI
+
+If the lock-acquire fastpath fails, [i.e. an atomic transition from 0 to
+TID fails], then FUTEX_LOCK_PI is called. The kernel does all the
+remaining work: if there is no futex-queue attached to the futex address
+yet then the code looks up the task that owns the futex [it has put its
+own TID into the futex value], and attaches a 'PI state' structure to
+the futex-queue. The pi_state includes an rt-mutex, which is a PI-aware,
+kernel-based synchronization object. The 'other' task is made the owner
+of the rt-mutex, and the FUTEX_WAITERS bit is atomically set in the
+futex value. Then this task tries to lock the rt-mutex, on which it
+blocks. Once it returns, it has the mutex acquired, and it sets the
+futex value to its own TID and returns. Userspace has no other work to
+perform - it now owns the lock, and futex value contains
+FUTEX_WAITERS|TID.
+
+If the unlock side fastpath succeeds, [i.e. userspace manages to do a
+TID -> 0 atomic transition of the futex value], then no kernel work is
+triggered.
+
+If the unlock fastpath fails (because the FUTEX_WAITERS bit is set),
+then FUTEX_UNLOCK_PI is called, and the kernel unlocks the futex on the
+behalf of userspace - and it also unlocks the attached
+pi_state->rt_mutex and thus wakes up any potential waiters.
+
+Note that under this approach, contrary to previous PI-futex approaches,
+there is no prior 'registration' of a PI-futex. [which is not quite
+possible anyway, due to existing ABI properties of pthread mutexes.]
+
+Also, under this scheme, 'robustness' and 'PI' are two orthogonal
+properties of futexes, and all four combinations are possible: futex,
+robust-futex, PI-futex, robust+PI-futex.
+
+More details about priority inheritance can be found in
+Documentation/rtmutex.txt.
Documentation/robust-futexes.txt +1 -1
Index: linux-pi-futex.mm.q/Documentation/robust-futexes.txt
===================================================================
@@ -95,7 +95,7 @@ comparison. If the thread has registered
 is empty. If the thread/process crashed or terminated in some incorrect
 way then the list might be non-empty: in this case the kernel carefully
 walks the list [not trusting it], and marks all locks that are owned by
-this thread with the FUTEX_OWNER_DEAD bit, and wakes up one waiter (if
+this thread with the FUTEX_OWNER_DIED bit, and wakes up one waiter (if
 any).
 
 The list is guaranteed to be private and per-thread at do_exit() time,
Documentation/rt-mutex.txt new file +74 -0

74 lines not on this page · raw message

Documentation/rtmutex.txt deleted +0 -60

60 lines not on this page · raw message

include/linux/futex.h +1 -0
Index: linux-pi-futex.mm.q/include/linux/futex.h
===================================================================
@@ -14,6 +14,7 @@
 #define FUTEX_WAKE_OP		5
 #define FUTEX_LOCK_PI		6
 #define FUTEX_UNLOCK_PI		7
+#define FUTEX_TRYLOCK_PI	8
 
 /*
  * Support for robust futexes: the kernel cleans up held futexes at
include/linux/rtmutex.h +12 -4
Index: linux-pi-futex.mm.q/include/linux/rtmutex.h
===================================================================
@@ -29,7 +29,7 @@ struct rt_mutex {
 	struct task_struct	*owner;
 #ifdef CONFIG_DEBUG_RT_MUTEXES
 	int			save_state;
-	struct list_head	held_list;
+	struct list_head	held_list_entry;
 	unsigned long		acquire_ip;
 	const char 		*name, *file;
 	int			line;
@@ -66,7 +66,7 @@ struct hrtimer_sleeper;
 
 #define __RT_MUTEX_INITIALIZER(mutexname) \
 	{ .wait_lock = SPIN_LOCK_UNLOCKED \
-	, .wait_list = PLIST_HEAD_INIT(mutexname.wait_list) \
+	, .wait_list = PLIST_HEAD_INIT(mutexname.wait_list, mutexname.wait_lock) \
 	, .owner = NULL \
 	__DEBUG_RT_MUTEX_INITIALIZER(mutexname)}
 
@@ -98,11 +98,19 @@ extern int rt_mutex_trylock(struct rt_mu
 
 extern void rt_mutex_unlock(struct rt_mutex *lock);
 
+#ifdef CONFIG_DEBUG_RT_MUTEXES
+# define INIT_RT_MUTEX_DEBUG(tsk)					\
+	.held_list_head	= LIST_HEAD_INIT(tsk.held_list_head),		\
+	.held_list_lock	= SPIN_LOCK_UNLOCKED
+#else
+# define INIT_RT_MUTEX_DEBUG(tsk)
+#endif
+
 #ifdef CONFIG_RT_MUTEXES
 # define INIT_RT_MUTEXES(tsk)						\
-	.pi_waiters	= PLIST_HEAD_INIT(tsk.pi_waiters),		\
+	.pi_waiters	= PLIST_HEAD_INIT(tsk.pi_waiters, tsk.pi_lock),	\
 	.pi_lock	= SPIN_LOCK_UNLOCKED,				\
-	.pi_lock_chain	= LIST_HEAD_INIT(tsk.pi_lock_chain),
+	INIT_RT_MUTEX_DEBUG(tsk)
 #else
 # define INIT_RT_MUTEXES(tsk)
 #endif
include/linux/sched.h +5 -4
Index: linux-pi-futex.mm.q/include/linux/sched.h
===================================================================
@@ -865,9 +865,10 @@ struct task_struct {
 	struct plist_head pi_waiters;
 	/* Deadlock detection and priority inheritance handling */
 	struct rt_mutex_waiter *pi_blocked_on;
-	/* PI locking helpers */
-	struct task_struct *pi_locked_by;
-	struct list_head pi_lock_chain;
+# ifdef CONFIG_DEBUG_RT_MUTEXES
+	spinlock_t held_list_lock;
+	struct list_head held_list_head;
+# endif
 #endif
 
 #ifdef CONFIG_DEBUG_MUTEXES
@@ -984,7 +985,7 @@ static inline void put_task_struct(struc
 #define PF_SPREAD_PAGE	0x04000000	/* Spread page cache over cpuset */
 #define PF_SPREAD_SLAB	0x08000000	/* Spread some slab caches over cpuset */
 #define PF_MEMPOLICY	0x10000000	/* Non-default NUMA mempolicy */
-#define PF_MUTEX_TESTER	0x20000000	/* Thread belongs to the rt mutex tester */
+#define PF_MUTEX_TESTER	0x02000000	/* Thread belongs to the rt mutex tester */
 
 /*
  * Only the _current_ task can read/write to tsk->flags, but other
include/linux/sysctl.h +1 -0
Index: linux-pi-futex.mm.q/include/linux/sysctl.h
===================================================================
@@ -148,6 +148,7 @@ enum
 	KERN_SPIN_RETRY=70,	/* int: number of spinlock retries */
 	KERN_ACPI_VIDEO_FLAGS=71, /* int: flags for setting up video after ACPI sleep */
 	KERN_IA64_UNALIGNED=72, /* int: ia64 unaligned userland trap enable */
+	KERN_MAX_LOCK_DEPTH=73
 };
 
 
kernel/fork.c +5 -3
Index: linux-pi-futex.mm.q/kernel/fork.c
===================================================================
@@ -926,10 +926,12 @@ static inline void rt_mutex_init_task(st
 {
 #ifdef CONFIG_RT_MUTEXES
 	spin_lock_init(&p->pi_lock);
-	plist_head_init(&p->pi_waiters);
+	plist_head_init(&p->pi_waiters, &p->pi_lock);
 	p->pi_blocked_on = NULL;
-	p->pi_locked_by = NULL;
-	INIT_LIST_HEAD(&p->pi_lock_chain);
+# ifdef CONFIG_DEBUG_RT_MUTEXES
+	spin_lock_init(&p->held_list_lock);
+	INIT_LIST_HEAD(&p->held_list_head);
+# endif
 #endif
 }
 
kernel/futex.c +75 -13

155 lines not on this page · raw message

kernel/rtmutex-debug.c +94 -92

322 lines not on this page · raw message

kernel/rtmutex-debug.h +8 -1
Index: linux-pi-futex.mm.q/kernel/rtmutex-debug.h
===================================================================
@@ -21,10 +21,17 @@ extern void debug_rt_mutex_free_waiter(s
 extern void debug_rt_mutex_init(struct rt_mutex *lock, const char *name);
 extern void debug_rt_mutex_lock(struct rt_mutex *lock __IP_DECL__);
 extern void debug_rt_mutex_unlock(struct rt_mutex *lock);
+extern void debug_rt_mutex_proxy_lock(struct rt_mutex *lock,
+				      struct task_struct *powner __IP_DECL__);
 extern void debug_rt_mutex_proxy_unlock(struct rt_mutex *lock);
 extern void debug_rt_mutex_deadlock(int detect, struct rt_mutex_waiter *waiter,
 				    struct rt_mutex *lock);
 extern void debug_rt_mutex_print_deadlock(struct rt_mutex_waiter *waiter);
-# define debug_rt_mutex_detect_deadlock(d)		(1)
 # define debug_rt_mutex_reset_waiter(w)			\
 	do { (w)->deadlock_lock = NULL; } while (0)
+
+static inline int debug_rt_mutex_detect_deadlock(struct rt_mutex_waiter *waiter,
+						 int detect)
+{
+	return (waiter != NULL);
+}
kernel/rtmutex.c +208 -352

781 lines not on this page · raw message

kernel/rtmutex.h +2 -1
Index: linux-pi-futex.mm.q/kernel/rtmutex.h
===================================================================
@@ -19,10 +19,11 @@
 #define debug_rt_mutex_init_waiter(w)			do { } while (0)
 #define debug_rt_mutex_free_waiter(w)			do { } while (0)
 #define debug_rt_mutex_lock(l)				do { } while (0)
+#define debug_rt_mutex_proxy_lock(l,p)			do { } while (0)
 #define debug_rt_mutex_proxy_unlock(l)			do { } while (0)
 #define debug_rt_mutex_unlock(l)			do { } while (0)
 #define debug_rt_mutex_init(m, n)			do { } while (0)
 #define debug_rt_mutex_deadlock(d, a ,l)		do { } while (0)
 #define debug_rt_mutex_print_deadlock(w)		do { } while (0)
-#define debug_rt_mutex_detect_deadlock(d)		(d)
+#define debug_rt_mutex_detect_deadlock(w,d)		(d)
 #define debug_rt_mutex_reset_waiter(w)			do { } while (0)
kernel/sched.c +6 -2
Index: linux-pi-futex.mm.q/kernel/sched.c
===================================================================
@@ -1522,6 +1522,12 @@ void fastcall sched_fork(task_t *p, int 
 	 * event cannot wake it up and insert it on the runqueue either.
 	 */
 	p->state = TASK_RUNNING;
+
+	/*
+	 * Make sure we do not leak PI boosting priority to the child:
+	 */
+	p->prio = current->normal_prio;
+
 	INIT_LIST_HEAD(&p->run_list);
 	p->array = NULL;
 #ifdef CONFIG_SCHEDSTATS
@@ -3893,7 +3899,6 @@ static void __setscheduler(struct task_s
 	BUG_ON(p->array);
 	p->policy = policy;
 	p->rt_priority = prio;
-
 	p->normal_prio = normal_prio(p);
 	/* we are holding p->pi_lock already */
 	p->prio = rt_mutex_getprio(p);
@@ -3902,7 +3907,6 @@ static void __setscheduler(struct task_s
 	 */
 	if (policy == SCHED_BATCH)
 		p->sleep_avg = 0;
-
 	set_load_weight(p);
 }
 
kernel/sysctl.c +15 -0
Index: linux-pi-futex.mm.q/kernel/sysctl.c
===================================================================
@@ -132,6 +132,10 @@ extern int acct_parm[];
 extern int no_unaligned_warning;
 #endif
 
+#ifdef CONFIG_RT_MUTEXES
+extern int max_lock_depth;
+#endif
+
 static int parse_table(int __user *, int, void __user *, size_t __user *, void __user *, size_t,
 		       ctl_table *, void **);
 static int proc_doutsstring(ctl_table *table, int write, struct file *filp,
@@ -684,6 +688,17 @@ static ctl_table kern_table[] = {
 		.proc_handler	= &proc_dointvec,
 	},
 #endif
+#ifdef CONFIG_RT_MUTEXES
+	{
+		.ctl_name	= KERN_MAX_LOCK_DEPTH,
+		.procname	= "max_lock_depth",
+		.data		= &max_lock_depth,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec,
+	},
+#endif
+
 	{ .ctl_name = 0 }
 };
 
scripts/rt-tester/t3-l1-pi-signal.tst +3 -0
Index: linux-pi-futex.mm.q/scripts/rt-tester/t3-l1-pi-signal.tst
===================================================================
@@ -69,15 +69,18 @@ W: locked:		0: 	0
 C: locknowait:		1: 	0
 W: blocked:		1: 	0
 T: prioeq:		0:	80
+T: prioeq:		1:	80
 
 # T2 lock L0 interruptible, no wait in the wakeup path
 C: lockintnowait:	2:	0
 W: blocked:		2: 	0
 T: prioeq:		0:	81
+T: prioeq:		1:	80
 
 # Interrupt T2
 C: signal:		2:	2
 W: unlocked:		2:	0
+T: prioeq:		1:	80
 T: prioeq:		0:	80
 
 T: locked:		0:	0
#10 lore raw

Re: [patch] PI-futex patchset: -V4

Quoted 6 lines · Ingo Molnar

this is version -V4 of the PI-futex patchset (ontop of current -mm2, which includes -V3.)

A clean queue of split-up patches can be found at:

http://redhat.com/~mingo/PI-futex-patches/PI-futex-patches-V4.tar.gz

oops, the plist debugging changes were missing from the delta. Find incremental patch ontop of -V4 below. The tarball above contains all the needed patches.

Ingo

-----
PI-futex -V4 part #2

--

 include/asm-generic/bug.h |    6 ++++++
 include/linux/plist.h     |   29 +++++++++++++++++++++++++----
 lib/plist.c               |   45 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 76 insertions(+), 4 deletions(-)
include/asm-generic/bug.h +6 -0
Index: linux-pi-futex.mm.q/include/asm-generic/bug.h
===================================================================
@@ -39,4 +39,10 @@
 #endif
 #endif
 
+#ifdef CONFIG_SMP
+# define WARN_ON_SMP(x)			WARN_ON(x)
+#else
+# define WARN_ON_SMP(x)			do { } while (0)
+#endif
+
 #endif
include/linux/plist.h +25 -4
Index: linux-pi-futex.mm.q/include/linux/plist.h
===================================================================
@@ -79,6 +79,9 @@
 struct plist_head {
 	struct list_head prio_list;
 	struct list_head node_list;
+#ifdef CONFIG_DEBUG_PI_LIST
+	spinlock_t *lock;
+#endif
 };
 
 struct plist_node {
@@ -86,15 +89,22 @@ struct plist_node {
 	struct plist_head	plist;
 };
 
+#ifdef CONFIG_DEBUG_PI_LIST
+# define PLIST_HEAD_LOCK_INIT(_lock)	.lock = _lock
+#else
+# define PLIST_HEAD_LOCK_INIT(_lock)
+#endif
+
 /**
  * #PLIST_HEAD_INIT - static struct plist_head initializer
  *
  * @head:	struct plist_head variable name
  */
-#define PLIST_HEAD_INIT(head)				\
+#define PLIST_HEAD_INIT(head, _lock)			\
 {							\
 	.prio_list = LIST_HEAD_INIT((head).prio_list),	\
 	.node_list = LIST_HEAD_INIT((head).node_list),	\
+	PLIST_HEAD_LOCK_INIT(&(_lock))			\
 }
 
 /**
@@ -115,10 +125,13 @@ struct plist_node {
  * @head:	&struct plist_head pointer
  */
 static inline void
-plist_head_init(struct plist_head *head)
+plist_head_init(struct plist_head *head, spinlock_t *lock)
 {
 	INIT_LIST_HEAD(&head->prio_list);
 	INIT_LIST_HEAD(&head->node_list);
+#ifdef CONFIG_DEBUG_PI_LIST
+	head->lock = lock;
+#endif
 }
 
 /**
@@ -130,7 +143,7 @@ plist_head_init(struct plist_head *head)
 static inline void plist_node_init(struct plist_node *node, int prio)
 {
 	node->prio = prio;
-	plist_head_init(&node->plist);
+	plist_head_init(&node->plist, NULL);
 }
 
 extern void plist_add(struct plist_node *node, struct plist_head *head);
@@ -207,8 +220,16 @@ static inline int plist_node_empty(const
  * @type:	the type of the struct this is embedded in.
  * @member:	the name of the list_struct within the struct.
  */
-#define plist_first_entry(head, type, member)	\
+#ifdef CONFIG_DEBUG_PI_LIST
+# define plist_first_entry(head, type, member)	\
+({ \
+	WARN_ON(plist_head_empty(head)); \
+	container_of(plist_first(head), type, member); \
+})
+#else
+# define plist_first_entry(head, type, member)	\
 	container_of(plist_first(head), type, member)
+#endif
 
 /**
  * plist_first - return the first node (and thus, highest priority)
lib/plist.c +45 -0

73 lines not on this page · raw message

#11 lore raw

Re: [patch] PI-futex patchset: -V4

In reply to Ingo Molnar
Quoted 38 lines · Ingo Molnar

this is version -V4 of the PI-futex patchset (ontop of current -mm2, which includes -V3.)

A clean queue of split-up patches can be found at:

http://redhat.com/~mingo/PI-futex-patches/PI-futex-patches-V4.tar.gz

the -V4 codebase has been tested on the glibc code (all testcases pass) and under load as well. (The -V4 code is included in the 2.6.16-rt12 code as well that i released earlier today.)

Changes since -V3:

- added Esben Nielsen's PI locking code, Thomas Gleixner made it work in cornercases and under load. This is significantly simpler (it removes 50 lines of code from rtmutex.c). The main difference is that instead of holding all locks along a dependency chain, this code propagates PI priorities (and detects deadlocks) by holding at most two locks at once, and by being preemptible between such steps.

- Jakub Jelinek did a detailed review of the new futex code and found some new races, which Thomas Gleixner fixed.

- to fix a pthread_mutex_trylock() related race, FUTEX_TRYLOCK_PI has been added (Thomas Gleixner)

- documentation fixes based on feedback from Tim Bird

- added Documentation/pi-futex.txt (in addition to rt-mutex.txt)

- added the plist debugging patch (which was part of -rt but wasnt part of the pi-futex queue before). This caught a couple of SMP bugs in the past.

- implemented more scalable held-locks debugging - it's now a per-task list of held locks, instead of a global list. This is similarly effective to the global list, but much more scalable. (This approach will also be added to the stock kernel/mutex.c code.)

- do not fiddle with irq flags in rtmutex.c - it's not needed.

Quoted 7 lines

- clone/fork fix: do not let parent's potential PI priority 'leak' into child threads or processes.

- added /proc/sys/kernel/max_lock_depth with a default limit of 1024, to limit the amount of deadlock-checking the kernel will do.

- small enhancement to the t3-l1-pi-signal.tst testcase.

Wouldn't this be a good opportunity to redefine SCHED_BATCH as 4 instead of 3 so that you can use ((p->policy & (SCHED_FIFO|SCHED_RR)) == 0) instead of (p->policy != SCHED_NORMAL && p->policy != SCHED_BATCH)? That expression will be called fairly frequently and SCHED_BATCH hasn't been around long enough for a change of value to break very much use space code.

Peter

Signature · 4 lines
Peter Williams                                   [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
 -- Ambrose Bierce