[PATCH 1/3] mutex debug: add generic blocked_on usage

[PATCH 1/3] mutex debug: add generic blocked_on usage

[Daniel Walker]

[-- Attachment #1: blocked_on-mutex.patch --]
[-- Type: text/plain, Size: 5681 bytes --]

There are a couple of blocked on type structures. One for mutexes, and one
for rtmutexes, and we also need one for futexes.

Instead of just adding another one to the task struct I combined them all into
a union. Since a waiter can only be blocked on one of the types at any given
time this should be safe.

I also usurped the pi_lock as the lock which protects all the blocked_on types.

Signed-off-by: Daniel Walker <dwalker@mvista.com>

---
 include/linux/sched.h |   27 ++++++++++++++++++++++-----
 kernel/fork.c         |    2 --
 kernel/mutex-debug.c  |   23 +++++++++++++++++------
 kernel/mutex-debug.h  |    4 +++-
 kernel/mutex.c        |    7 ++++++-
 5 files changed, 48 insertions(+), 15 deletions(-)

Index: linux-2.6.25/include/linux/sched.h
===================================================================
--- linux-2.6.25.orig/include/linux/sched.h
+++ linux-2.6.25/include/linux/sched.h
@@ -1024,6 +1024,21 @@ struct sched_rt_entity {
 #endif
 };
 
+enum lock_waiter_type {
+	RT_MUTEX_WAITER = 1,
+	MUTEX_WAITER,
+	FUTEX_WAITER,
+};
+
+struct lock_waiter_state {
+	enum lock_waiter_type lock_type;
+	union {
+		struct rt_mutex_waiter *rt_blocked_on;
+		struct mutex_waiter *mutex_blocked_on;
+		struct futex_q *futex_blocked_on;
+	};
+};
+
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	void *stack;
@@ -1201,7 +1216,7 @@ struct task_struct {
 /* Protection of (de-)allocation: mm, files, fs, tty, keyrings */
 	spinlock_t alloc_lock;
 
-	/* Protection of the PI data structures: */
+	/* Protects blocked_on field and PI waiters list. */
 	spinlock_t pi_lock;
 
 #ifdef CONFIG_RT_MUTEXES
@@ -1211,10 +1226,12 @@ struct task_struct {
 	struct rt_mutex_waiter *pi_blocked_on;
 #endif
 
-#ifdef CONFIG_DEBUG_MUTEXES
-	/* mutex deadlock detection */
-	struct mutex_waiter *blocked_on;
-#endif
+	/*
+ 	 * Deadlock detection and priority inheritance handling,
+	 * and any other out of line mutex operations
+	 */
+	struct lock_waiter_state *blocked_on;
+
 #ifdef CONFIG_TRACE_IRQFLAGS
 	unsigned int irq_events;
 	int hardirqs_enabled;
Index: linux-2.6.25/kernel/fork.c
===================================================================
--- linux-2.6.25.orig/kernel/fork.c
+++ linux-2.6.25/kernel/fork.c
@@ -1158,9 +1158,7 @@ static struct task_struct *copy_process(
 	p->lockdep_recursion = 0;
 #endif
 
-#ifdef CONFIG_DEBUG_MUTEXES
 	p->blocked_on = NULL; /* not blocked yet */
-#endif
 
 	/* Perform scheduler related setup. Assign this task to a CPU. */
 	sched_fork(p, clone_flags);
Index: linux-2.6.25/kernel/mutex-debug.c
===================================================================
--- linux-2.6.25.orig/kernel/mutex-debug.c
+++ linux-2.6.25/kernel/mutex-debug.c
@@ -52,23 +52,34 @@ void debug_mutex_free_waiter(struct mute
 	memset(waiter, MUTEX_DEBUG_FREE, sizeof(*waiter));
 }
 
-void debug_mutex_add_waiter(struct mutex *lock, struct mutex_waiter *waiter,
+void debug_mutex_add_waiter(struct mutex *lock, struct lock_waiter_state *lock_waiter,
 			    struct thread_info *ti)
 {
+	struct task_struct *task = ti->task;
+
 	SMP_DEBUG_LOCKS_WARN_ON(!spin_is_locked(&lock->wait_lock));
 
 	/* Mark the current thread as blocked on the lock: */
-	ti->task->blocked_on = waiter;
-	waiter->lock = lock;
+	lock_waiter->mutex_blocked_on->lock = lock;
+	spin_lock(&task->pi_lock);
+	task->blocked_on = lock_waiter;
+	spin_unlock(&task->pi_lock);
 }
 
 void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter,
 			 struct thread_info *ti)
 {
+	struct task_struct *task = ti->task;
+
+	spin_lock(&task->pi_lock);
+
 	DEBUG_LOCKS_WARN_ON(list_empty(&waiter->list));
-	DEBUG_LOCKS_WARN_ON(waiter->task != ti->task);
-	DEBUG_LOCKS_WARN_ON(ti->task->blocked_on != waiter);
-	ti->task->blocked_on = NULL;
+	DEBUG_LOCKS_WARN_ON(waiter->task != task);
+	DEBUG_LOCKS_WARN_ON(task->blocked_on != NULL);
+	DEBUG_LOCKS_WARN_ON(task->blocked_on->mutex_blocked_on != waiter);
+
+	task->blocked_on = NULL;
+	spin_unlock(&task->pi_lock);
 
 	list_del_init(&waiter->list);
 	waiter->task = NULL;
Index: linux-2.6.25/kernel/mutex-debug.h
===================================================================
--- linux-2.6.25.orig/kernel/mutex-debug.h
+++ linux-2.6.25/kernel/mutex-debug.h
@@ -25,10 +25,12 @@ extern void debug_mutex_lock_common(stru
 				    struct mutex_waiter *waiter);
 extern void debug_mutex_wake_waiter(struct mutex *lock,
 				    struct mutex_waiter *waiter);
+
 extern void debug_mutex_free_waiter(struct mutex_waiter *waiter);
 extern void debug_mutex_add_waiter(struct mutex *lock,
-				   struct mutex_waiter *waiter,
+				   struct lock_waiter_state *lock_waiter,
 				   struct thread_info *ti);
+
 extern void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter,
 				struct thread_info *ti);
 extern void debug_mutex_unlock(struct mutex *lock);
Index: linux-2.6.25/kernel/mutex.c
===================================================================
--- linux-2.6.25.orig/kernel/mutex.c
+++ linux-2.6.25/kernel/mutex.c
@@ -131,11 +131,16 @@ __mutex_lock_common(struct mutex *lock, 
 	unsigned int old_val;
 	unsigned long flags;
 
+#ifdef CONFIG_DEBUG_MUTEXES
+	struct lock_waiter_state lock_waiter =
+		{ .lock_type = MUTEX_WAITER, { .mutex_blocked_on = &waiter} };
+#endif
+
 	spin_lock_mutex(&lock->wait_lock, flags);
 
 	debug_mutex_lock_common(lock, &waiter);
 	mutex_acquire(&lock->dep_map, subclass, 0, ip);
-	debug_mutex_add_waiter(lock, &waiter, task_thread_info(task));
+	debug_mutex_add_waiter(lock, &lock_waiter, task_thread_info(task));
 
 	/* add waiting tasks to the end of the waitqueue (FIFO): */
 	list_add_tail(&waiter.list, &lock->wait_list);

-- 

[PATCH 2/3] rtmutex: add generic blocked_on usage

[Daniel Walker]

[-- Attachment #1: blocked_on-rtmutex.patch --]
[-- Type: text/plain, Size: 5421 bytes --]

Modify the rtmutex to use the generic blocked_on field.

Signed-off-by: Daniel Walker <dwalker@mvista.com>

---
 include/linux/sched.h |    2 --
 kernel/fork.c         |    1 -
 kernel/rtmutex.c      |   35 ++++++++++++++++++++++++-----------
 3 files changed, 24 insertions(+), 14 deletions(-)

Index: linux-2.6.25/include/linux/sched.h
===================================================================
--- linux-2.6.25.orig/include/linux/sched.h
+++ linux-2.6.25/include/linux/sched.h
@@ -1222,8 +1222,6 @@ struct task_struct {
 #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;
 #endif
 
 	/*
Index: linux-2.6.25/kernel/fork.c
===================================================================
--- linux-2.6.25.orig/kernel/fork.c
+++ linux-2.6.25/kernel/fork.c
@@ -980,7 +980,6 @@ static void rt_mutex_init_task(struct ta
 	spin_lock_init(&p->pi_lock);
 #ifdef CONFIG_RT_MUTEXES
 	plist_head_init(&p->pi_waiters, &p->pi_lock);
-	p->pi_blocked_on = NULL;
 #endif
 }
 
Index: linux-2.6.25/kernel/rtmutex.c
===================================================================
--- linux-2.6.25.orig/kernel/rtmutex.c
+++ linux-2.6.25/kernel/rtmutex.c
@@ -74,6 +74,14 @@ static void fixup_rt_mutex_waiters(struc
 		clear_rt_mutex_waiters(lock);
 }
 
+static
+struct rt_mutex_waiter *rt_mutex_get_waiter(struct task_struct *task)
+{
+	if (task->blocked_on && task->blocked_on->lock_type == RT_MUTEX_WAITER)
+		return task->blocked_on->rt_blocked_on;
+	return NULL;
+}
+
 /*
  * We can speed up the acquire/release, if the architecture
  * supports cmpxchg and if there's no debugging state to be set up
@@ -197,7 +205,7 @@ static int rt_mutex_adjust_prio_chain(st
 	 */
 	spin_lock_irqsave(&task->pi_lock, flags);
 
-	waiter = task->pi_blocked_on;
+	waiter = rt_mutex_get_waiter(task);
 	/*
 	 * Check whether the end of the boosting chain has been
 	 * reached or the state of the chain has changed while we
@@ -411,6 +419,7 @@ static int try_to_take_rt_mutex(struct r
  */
 static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 				   struct rt_mutex_waiter *waiter,
+				   struct lock_waiter_state *lock_waiter,
 				   int detect_deadlock)
 {
 	struct task_struct *owner = rt_mutex_owner(lock);
@@ -430,7 +439,7 @@ static int task_blocks_on_rt_mutex(struc
 		top_waiter = rt_mutex_top_waiter(lock);
 	plist_add(&waiter->list_entry, &lock->wait_list);
 
-	current->pi_blocked_on = waiter;
+	current->blocked_on = lock_waiter;
 
 	spin_unlock_irqrestore(&current->pi_lock, flags);
 
@@ -440,7 +449,7 @@ static int task_blocks_on_rt_mutex(struc
 		plist_add(&waiter->pi_list_entry, &owner->pi_waiters);
 
 		__rt_mutex_adjust_prio(owner);
-		if (owner->pi_blocked_on)
+		if (rt_mutex_get_waiter(owner))
 			chain_walk = 1;
 		spin_unlock_irqrestore(&owner->pi_lock, flags);
 	}
@@ -501,7 +510,7 @@ static void wakeup_next_waiter(struct rt
 	spin_unlock_irqrestore(&current->pi_lock, flags);
 
 	/*
-	 * Clear the pi_blocked_on variable and enqueue a possible
+	 * Clear the blocked_on variable and enqueue a possible
 	 * waiter into the pi_waiters list of the pending owner. This
 	 * prevents that in case the pending owner gets unboosted a
 	 * waiter with higher priority than pending-owner->normal_prio
@@ -509,11 +518,12 @@ static void wakeup_next_waiter(struct rt
 	 */
 	spin_lock_irqsave(&pendowner->pi_lock, flags);
 
-	WARN_ON(!pendowner->pi_blocked_on);
-	WARN_ON(pendowner->pi_blocked_on != waiter);
-	WARN_ON(pendowner->pi_blocked_on->lock != lock);
+	WARN_ON(!pendowner->blocked_on);
+	WARN_ON(pendowner->blocked_on->lock_type != RT_MUTEX_WAITER);
+	WARN_ON(pendowner->blocked_on->rt_blocked_on != waiter);
+	WARN_ON(pendowner->blocked_on->rt_blocked_on->lock != lock);
 
-	pendowner->pi_blocked_on = NULL;
+	pendowner->blocked_on = NULL;
 
 	if (rt_mutex_has_waiters(lock)) {
 		struct rt_mutex_waiter *next;
@@ -542,7 +552,7 @@ static void remove_waiter(struct rt_mute
 	spin_lock_irqsave(&current->pi_lock, flags);
 	plist_del(&waiter->list_entry, &lock->wait_list);
 	waiter->task = NULL;
-	current->pi_blocked_on = NULL;
+	current->blocked_on = NULL;
 	spin_unlock_irqrestore(&current->pi_lock, flags);
 
 	if (first && owner != current) {
@@ -559,7 +569,7 @@ static void remove_waiter(struct rt_mute
 		}
 		__rt_mutex_adjust_prio(owner);
 
-		if (owner->pi_blocked_on)
+		if (rt_mutex_get_waiter(owner))
 			chain_walk = 1;
 
 		spin_unlock_irqrestore(&owner->pi_lock, flags);
@@ -592,7 +602,7 @@ void rt_mutex_adjust_pi(struct task_stru
 
 	spin_lock_irqsave(&task->pi_lock, flags);
 
-	waiter = task->pi_blocked_on;
+	waiter = rt_mutex_get_waiter(task);
 	if (!waiter || waiter->list_entry.prio == task->prio) {
 		spin_unlock_irqrestore(&task->pi_lock, flags);
 		return;
@@ -614,6 +624,8 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 		  int detect_deadlock)
 {
 	struct rt_mutex_waiter waiter;
+	struct lock_waiter_state lock_waiter =
+		{ .lock_type = RT_MUTEX_WAITER, { .rt_blocked_on = &waiter} };
 	int ret = 0;
 
 	debug_rt_mutex_init_waiter(&waiter);
@@ -663,6 +675,7 @@ rt_mutex_slowlock(struct rt_mutex *lock,
 		 */
 		if (!waiter.task) {
 			ret = task_blocks_on_rt_mutex(lock, &waiter,
+						      &lock_waiter,
 						      detect_deadlock);
 			/*
 			 * If we got woken up by the owner then start loop

-- 

[PATCH 3/3] futex: fix miss ordered wakeups

[Daniel Walker]

[-- Attachment #1: blocked_on-futex.patch --]
[-- Type: text/plain, Size: 3583 bytes --]

When the plist was added to futexes it added overhead to sort based
on priority for the futex waiters. If there is a miss order the value of
this, from my perspective, is lost. Since we don't re-order tasks
when their priority is changed after they sleep then we get a miss ordered
scenerio, and tasks aren't woken in priority order.

This patch corrects this issue, so the tasks are always woken in priority
order.

Signed-off-by: Daniel Walker <dwalker@mvista.com>

---
 include/linux/sched.h |    2 ++
 kernel/futex.c        |   45 +++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched.c        |    1 +
 3 files changed, 48 insertions(+)

Index: linux-2.6.25/include/linux/sched.h
===================================================================
--- linux-2.6.25.orig/include/linux/sched.h
+++ linux-2.6.25/include/linux/sched.h
@@ -1664,6 +1664,8 @@ static inline int rt_mutex_getprio(struc
 # define rt_mutex_adjust_pi(p)		do { } while (0)
 #endif
 
+extern void futex_adjust_waiters(struct task_struct *p);
+
 extern void set_user_nice(struct task_struct *p, long nice);
 extern int task_prio(const struct task_struct *p);
 extern int task_nice(const struct task_struct *p);
Index: linux-2.6.25/kernel/futex.c
===================================================================
--- linux-2.6.25.orig/kernel/futex.c
+++ linux-2.6.25/kernel/futex.c
@@ -326,6 +326,42 @@ static int get_futex_value_locked(u32 *d
 	return ret ? -EFAULT : 0;
 }
 
+void futex_adjust_waiters(struct task_struct *p)
+{
+	struct futex_hash_bucket *hb;
+	union futex_key key;
+	struct futex_q *q;
+	int prio;
+
+	spin_lock(&p->pi_lock);
+	if (p->blocked_on && p->blocked_on->lock_type == FUTEX_WAITER) {
+		q = p->blocked_on->futex_blocked_on;
+retry:
+		key = q->key;
+
+		hb = hash_futex(&key);
+		spin_lock(&hb->lock);
+
+		/*
+		 * Check if the waiter got requeued to a new page, if so retry.
+		 */
+		if (unlikely(!match_futex(&q->key, &key))) {
+			spin_unlock(&hb->lock);
+			goto retry;
+		}
+
+		if (likely(!plist_node_empty(&q->list))) {
+			plist_del(&q->list, &hb->chain);
+			prio = min(p->normal_prio, MAX_RT_PRIO);
+			plist_node_init(&q->list, prio);
+			plist_add(&q->list, &hb->chain);
+		}
+		spin_unlock(&hb->lock);
+	}
+	spin_unlock(&p->pi_lock);
+}
+
+
 /*
  * Fault handling.
  * if fshared is non NULL, current->mm->mmap_sem is already held
@@ -1155,6 +1191,8 @@ static int futex_wait(u32 __user *uaddr,
 	DECLARE_WAITQUEUE(wait, curr);
 	struct futex_hash_bucket *hb;
 	struct futex_q q;
+	struct lock_waiter_state blocked_on =
+		{ .lock_type = FUTEX_WAITER, { .futex_blocked_on = &q} };
 	u32 uval;
 	int ret;
 	struct hrtimer_sleeper t;
@@ -1215,6 +1253,10 @@ static int futex_wait(u32 __user *uaddr,
 	if (uval != val)
 		goto out_unlock_release_sem;
 
+	spin_lock(&current->pi_lock);
+	current->blocked_on = &blocked_on;
+	spin_unlock(&current->pi_lock);
+
 	/* Only actually queue if *uaddr contained val.  */
 	queue_me(&q, hb);
 
@@ -1272,6 +1314,9 @@ static int futex_wait(u32 __user *uaddr,
 	}
 	__set_current_state(TASK_RUNNING);
 
+	spin_lock(&current->pi_lock);
+	current->blocked_on = NULL;
+	spin_unlock(&current->pi_lock);
 	/*
 	 * NOTE: we don't remove ourselves from the waitqueue because
 	 * we are the only user of it.
Index: linux-2.6.25/kernel/sched.c
===================================================================
--- linux-2.6.25.orig/kernel/sched.c
+++ linux-2.6.25/kernel/sched.c
@@ -5209,6 +5209,7 @@ recheck:
 	spin_unlock_irqrestore(&p->pi_lock, flags);
 
 	rt_mutex_adjust_pi(p);
+	futex_adjust_waiters(p);
 
 	return 0;
 }

-- 

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Ulrich Drepper]

On Thu, May 22, 2008 at 12:00 AM, Daniel Walker <dwalker@mvista.com> wrote:
> This patch corrects this issue, so the tasks are always woken in priority
> order.

This is completely unnecessary overhead for 99.999% of all cases.  It
was deliberately not done.  You slowing things down for everybody.  If
you want priorities, then use PI futexes.

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Daniel Walker]

On Thu, 2008-05-22 at 22:02 -0700, Ulrich Drepper wrote:
> On Thu, May 22, 2008 at 12:00 AM, Daniel Walker <dwalker@mvista.com> wrote:
> > This patch corrects this issue, so the tasks are always woken in priority
> > order.
> 
> This is completely unnecessary overhead for 99.999% of all cases.  It
> was deliberately not done.  You slowing things down for everybody.  If
> you want priorities, then use PI futexes.

That's the problem we aren't just covering 99.99% we're trying to cover
100% of cases.. If we don't do it in that one case we may as well not do
it at all.

Daniel

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Ulrich Drepper]

On Thu, May 22, 2008 at 10:15 PM, Daniel Walker <dwalker@mvista.com> wrote:
> That's the problem we aren't just covering 99.99% we're trying to cover
> 100% of cases.. If we don't do it in that one case we may as well not do
> it at all.

I have no problem with removing the other ordering.  It was added
because it limited overhead.  It is completely wrong to have everybody
pay for the needs for a very small minority.

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Daniel Walker]

On Thu, 2008-05-22 at 22:24 -0700, Ulrich Drepper wrote:
> On Thu, May 22, 2008 at 10:15 PM, Daniel Walker <dwalker@mvista.com> wrote:
> > That's the problem we aren't just covering 99.99% we're trying to cover
> > 100% of cases.. If we don't do it in that one case we may as well not do
> > it at all.
> 
> I have no problem with removing the other ordering.  It was added
> because it limited overhead.  It is completely wrong to have everybody
> pay for the needs for a very small minority.

I think that ordering is something companies have been wanting for a
long time.. I had a lot of people asking about it, I was glad when it
was added.. However, it all falls down in the one case which we don't
handle. 

I don't think the overhead for this is all that bad.. Consider that the
worst performance case is the contended case, and this patch adds a very
small amount of code. The vast majority of cases are un-contended , and
it's already know to be slow in the cases which are contended.

Daniel

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Ulrich Drepper]

On Thu, May 22, 2008 at 10:36 PM, Daniel Walker <dwalker@mvista.com> wrote:
> I think that ordering is something companies have been wanting for a
> long time..

That's your claim.  Again, almost nobody outside the realm of embedded
fortunately uses priorities.  It's a complete waste of time almost all
programs, certainly all but one or two on any of my systems.

There is already a solution for priority wakeup.  Use it and don't
punish everybody else for your needs.

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Thomas Gleixner]

On Thu, 22 May 2008, Daniel Walker wrote:

> When the plist was added to futexes it added overhead to sort based
> on priority for the futex waiters. If there is a miss order the value of
> this, from my perspective, is lost. Since we don't re-order tasks
> when their priority is changed after they sleep then we get a miss ordered
> scenerio, and tasks aren't woken in priority order.

This is a solution looking for a problem. 

Normal futexes have no ordering guarantees at all. There is no
mechanism to prevent lock stealing from lower priority tasks. So why
should we care about the once a year case, where a sleepers priority
is modified ?

If you need ordering guarantees then use PI futexes.

> This patch corrects this issue, so the tasks are always woken in priority
> order.

The patch corrects a non issue and introduces lock order issues:

> +void futex_adjust_waiters(struct task_struct *p)
> +{
> +	spin_lock(&p->pi_lock);
> +		spin_lock(&hb->lock);
> ...
> +		spin_unlock(&hb->lock);
> +	}
> +	spin_unlock(&p->pi_lock);
> +}

vs.

> @@ -1155,6 +1191,8 @@ static int futex_wait(u32 __user *uaddr,
{
....
        hb = queue_lock(&q);

> +	spin_lock(&current->pi_lock);
> +	current->blocked_on = &blocked_on;
> +	spin_unlock(&current->pi_lock);

There are more issues vs. pi futexes as well. The simple case of
futex_wait() vs. futex_adjust_waiters will just upset lockdep, but
there are real dealocks vs. unqueue_me_pi waiting.

Thanks,
	tglx

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Daniel Walker]

On Sat, 2008-05-24 at 10:55 +0200, Thomas Gleixner wrote:

> Normal futexes have no ordering guarantees at all. There is no
> mechanism to prevent lock stealing from lower priority tasks. So why
> should we care about the once a year case, where a sleepers priority
> is modified ?

Lock stealing? The usage of sched_setscheduler is fairly pervasive in
userspace, if a task becomes SCHED_FIFO it did so via
sched_setscheduler. So I don't think this is at all "once a year". Tasks
shouldn't be forced to determine if a task is sleeping or not before it
calls sched_setscheduler. 

> If you need ordering guarantees then use PI futexes.

There are degree's of overhead with each step.. Someone may not need or
want priority inheritance.

> > +void futex_adjust_waiters(struct task_struct *p)
> > +{
> > +	spin_lock(&p->pi_lock);
> > +		spin_lock(&hb->lock);
> > ...
> > +		spin_unlock(&hb->lock);
> > +	}
> > +	spin_unlock(&p->pi_lock);
> > +}
> 
> vs.
> 
> > @@ -1155,6 +1191,8 @@ static int futex_wait(u32 __user *uaddr,
> {
> ....
>         hb = queue_lock(&q);
> 
> > +	spin_lock(&current->pi_lock);
> > +	current->blocked_on = &blocked_on;
> > +	spin_unlock(&current->pi_lock);
> 
> There are more issues vs. pi futexes as well. The simple case of
> futex_wait() vs. futex_adjust_waiters will just upset lockdep, but
> there are real dealocks vs. unqueue_me_pi waiting.

You mean the lock ordering would cause the deadlock vs. unqueue_me_pi ,
or are you talking about something else?

Daniel

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Thomas Gleixner]

On Sat, 24 May 2008, Daniel Walker wrote:
> On Sat, 2008-05-24 at 10:55 +0200, Thomas Gleixner wrote:
> 
> > Normal futexes have no ordering guarantees at all. There is no
> > mechanism to prevent lock stealing from lower priority tasks. So why
> > should we care about the once a year case, where a sleepers priority
> > is modified ?
> 
> Lock stealing?

Do you have the faintest idea how the futex code works at all ? There
is no guarantee that the task which is woken up first gets the futex.

A) A task on another CPU can get it independent of its priority
B) In case of multiple waiters wakeup there is no guarantee either

> The usage of sched_setscheduler is fairly pervasive in
> userspace, if a task becomes SCHED_FIFO it did so via
> sched_setscheduler.

Sigh. 

sched_setscheduler is usually done during the startup and not in the
middle of some operation.

> So I don't think this is at all "once a year". Tasks
> shouldn't be forced to determine if a task is sleeping or not before it
> calls sched_setscheduler. 

A sane written program which uses RT priorities does none of this and
I don't care about abstruse use cases at all.

> > If you need ordering guarantees then use PI futexes.
> 
> There are degree's of overhead with each step.. Someone may not need or
> want priority inheritance.

Then there is no need to add this artifical "correctness" at all.

> > There are more issues vs. pi futexes as well. The simple case of
> > futex_wait() vs. futex_adjust_waiters will just upset lockdep, but
> > there are real dealocks vs. unqueue_me_pi waiting.
> 
> You mean the lock ordering would cause the deadlock vs. unqueue_me_pi ,
> or are you talking about something else?

Do I write Chinese or what ?

Thanks,
	tglx

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Daniel Walker]

On Sat, 2008-05-24 at 19:03 +0200, Thomas Gleixner wrote:
> On Sat, 24 May 2008, Daniel Walker wrote:
> > On Sat, 2008-05-24 at 10:55 +0200, Thomas Gleixner wrote:
> > 
> > > Normal futexes have no ordering guarantees at all. There is no
> > > mechanism to prevent lock stealing from lower priority tasks. So why
> > > should we care about the once a year case, where a sleepers priority
> > > is modified ?
> > 
> > Lock stealing?
> 
> Do you have the faintest idea how the futex code works at all ? There
> is no guarantee that the task which is woken up first gets the futex.

Thomas if you want to be abusive, talk to someone else.

> A) A task on another CPU can get it independent of its priority
> B) In case of multiple waiters wakeup there is no guarantee either

This is how I would imagine the pre-plist code would work.

> > > If you need ordering guarantees then use PI futexes.
> > 
> > There are degree's of overhead with each step.. Someone may not need or
> > want priority inheritance.
> 
> Then there is no need to add this artifical "correctness" at all.

huh?

> > > There are more issues vs. pi futexes as well. The simple case of
> > > futex_wait() vs. futex_adjust_waiters will just upset lockdep, but
> > > there are real dealocks vs. unqueue_me_pi waiting.
> > 
> > You mean the lock ordering would cause the deadlock vs. unqueue_me_pi ,
> > or are you talking about something else?
> 
> Do I write Chinese or what ?

I guess so .. 

Daniel

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Thomas Gleixner]

On Sat, 24 May 2008, Daniel Walker wrote:
> On Sat, 2008-05-24 at 19:03 +0200, Thomas Gleixner wrote:
> > On Sat, 24 May 2008, Daniel Walker wrote:
> > > On Sat, 2008-05-24 at 10:55 +0200, Thomas Gleixner wrote:
> > > 
> > > > Normal futexes have no ordering guarantees at all. There is no
> > > > mechanism to prevent lock stealing from lower priority tasks. So why
> > > > should we care about the once a year case, where a sleepers priority
> > > > is modified ?
> > > 
> > > Lock stealing?
> > 
> > Do you have the faintest idea how the futex code works at all ? There
> > is no guarantee that the task which is woken up first gets the futex.
> 
> Thomas if you want to be abusive, talk to someone else.

See below.
 
> > A) A task on another CPU can get it independent of its priority
> > B) In case of multiple waiters wakeup there is no guarantee either
> 
> This is how I would imagine the pre-plist code would work.

And it works this way even after the plist code.

May I politely suggest, that you carefully read futex_wake() and the
corresponding libc implementation and figure out why there is no
guarantee and why there can't be one?

Sorry, I'm not abusive. You make claims about correctness and you seem
to believe that the plist code gives guarantees except for the
setscheduler corner case, but your hypothesis is simply wrong:

There is no kernel side controlled handover of a normal futex. The
woken up waiters race for it and a low prio thread on another CPU can
steal it even if there is a high prio waiter woken up.

So you try to tell me about the correctness of code where you just
imagine how it works. 

The plist add on works correct in most of the cases, nothing else. To
achieve full correctness there is much more necessary than this
setscheduler issue. The plist changes were accepted because the
overhead is really minimal, but achieving full correctness would hurt
performance badly.

> > > > There are more issues vs. pi futexes as well. The simple case of
> > > > futex_wait() vs. futex_adjust_waiters will just upset lockdep, but
> > > > there are real dealocks vs. unqueue_me_pi waiting.
> > > 
> > > You mean the lock ordering would cause the deadlock vs. unqueue_me_pi ,
> > > or are you talking about something else?
> > 
> > Do I write Chinese or what ?
> 
> I guess so .. 

So maybe you should take some private lessons in Chinese. Then we
could easier communicate.

Thanks,
	tglx

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Daniel Walker]

On Sat, 2008-05-24 at 20:35 +0200, Thomas Gleixner wrote: 
> > > A) A task on another CPU can get it independent of its priority
> > > B) In case of multiple waiters wakeup there is no guarantee either
> > 
> > This is how I would imagine the pre-plist code would work.
> 
> And it works this way even after the plist code.
> 
> May I politely suggest, that you carefully read futex_wake() and the
> corresponding libc implementation and figure out why there is no
> guarantee and why there can't be one?

Sure ..

> Sorry, I'm not abusive. You make claims about correctness and you seem
> to believe that the plist code gives guarantees except for the
> setscheduler corner case, but your hypothesis is simply wrong:
> 
> There is no kernel side controlled handover of a normal futex. The
> woken up waiters race for it and a low prio thread on another CPU can
> steal it even if there is a high prio waiter woken up.

After reading futex_wake, Doesn't it depend how many waiters are woken?
Given that comes from userspace, glibc could wake a single waiter and
obtain a priority ordering, couldn't it?

> The plist add on works correct in most of the cases, nothing else. To
> achieve full correctness there is much more necessary than this
> setscheduler issue. The plist changes were accepted because the
> overhead is really minimal, but achieving full correctness would hurt
> performance badly.

If that's the requirement then code that cleans up the corner case that
I've identified, which is also minimal should be acceptable .. Since
it's meeting the same requirement you layed out above for the original
plist changes.

Daniel

Re: [PATCH 3/3] futex: fix miss ordered wakeups

[Arjan van de Ven]

On Sat, 24 May 2008 12:19:34 -0700
Daniel Walker <dwalker@mvista.com> wrote:

> > There is no kernel side controlled handover of a normal futex. The
> > woken up waiters race for it and a low prio thread on another CPU
> > can steal it even if there is a high prio waiter woken up.
> 
> After reading futex_wake, Doesn't it depend how many waiters are
> woken? Given that comes from userspace, glibc could wake a single
> waiter and obtain a priority ordering, couldn't it?

nope. Don't look at the release path... look at the acquire path.
If a thread sees the futex is free, it'll take it, without even going
to the kernel at all. So you have the situation where the kernel spends
a lot of time finding the "perfect" candidate to wake up, but kaboom
some other thread just happens to try to get the mutex between the
wakeup and the acquire of the wakee.. and just "steal" the lock.