Skip to contentSkip to conversation

mutex debug: add generic blocked_on usage

PATCH In review Daniel Walker 4 participants 15 messages May 23, 2008 – May 24, 2008

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

PATCH 1/3 mutex debug: add generic blocked_on usage

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.

---
 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(-)
include/linux/sched.h +22 -5
Index: 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;
kernel/fork.c +0 -2
Index: 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);
kernel/mutex-debug.c +17 -6
Index: 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;
kernel/mutex-debug.h +3 -1
Index: 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);
kernel/mutex.c +6 -1
Index: 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);
#1 lore raw

PATCH 2/3 rtmutex: add generic blocked_on usage

Modify the rtmutex to use the generic blocked_on field.

---
 include/linux/sched.h |    2 --
 kernel/fork.c         |    1 -
 kernel/rtmutex.c      |   35 ++++++++++++++++++++++++-----------
 3 files changed, 24 insertions(+), 14 deletions(-)
include/linux/sched.h +0 -2
Index: 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
 
 	/*
kernel/fork.c +0 -1
Index: 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
 }
 
kernel/rtmutex.c +24 -11
Index: 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
#2 lore raw

PATCH 3/3 futex: fix miss ordered wakeups

In reply to Daniel Walker

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.

---
 include/linux/sched.h |    2 ++
 kernel/futex.c        |   45 +++++++++++++++++++++++++++++++++++++++++++++
 kernel/sched.c        |    1 +
 3 files changed, 48 insertions(+)
include/linux/sched.h +2 -0
Index: 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);
kernel/futex.c +45 -0

69 lines not on this page · raw message

kernel/sched.c +1 -0
Index: 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;
 }
#3 lore raw

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

Quoted 2 lines · Daniel Walker

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.

#4 lore raw

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

Quoted 7 lines · Ulrich Drepper
Quoted 2 lines · Daniel Walker

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

#5 lore raw

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

Quoted 3 lines · Daniel Walker

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.

#6 lore raw

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

Quoted 8 lines · Ulrich Drepper
Quoted 3 lines · Daniel Walker

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

#7 lore raw

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

Quoted 2 lines · Daniel Walker

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.

#8 lore raw

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

In reply to Daniel Walker
Quoted 5 lines · Daniel Walker

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.

Quoted 2 lines

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:

kernel/futex.c static int get_futex_value_locked(u32 *d · line 362

Quoted 9 lines
kernel/futex.c +8 -0
+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.

Review static int futex_wait(u32 __user *uaddr,

Quoted 1 line
(quoted diff) +0 -0
@@ -1155,6 +1191,8 @@ static int futex_wait(u32 __user *uaddr,

{
....

        hb = queue_lock(&q);

kernel/futex.c static int futex_wait(u32 __user *uaddr, · line 1258

Quoted 3 lines
kernel/futex.c +3 -0
+	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

#9 lore raw

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

Quoted 4 lines · Thomas Gleixner

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.

Quoted 1 line

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.

Quoted 17 lines

kernel/futex.c static int get_futex_value_locked(u32 *d · line 362

Quoted 9 lines
kernel/futex.c +8 -0
+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.

Review static int futex_wait(u32 __user *uaddr,

Quoted 1 line
(quoted diff) +0 -0
@@ -1155,6 +1191,8 @@ static int futex_wait(u32 __user *uaddr,

{
....

        hb = queue_lock(&q);
Quoted 7 lines

kernel/futex.c static int futex_wait(u32 __user *uaddr, · line 1258

Quoted 3 lines
kernel/futex.c +3 -0
+	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

#10 lore raw

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

Quoted 8 lines · Daniel Walker
Quoted 4 lines · Thomas Gleixner

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

Quoted 3 lines

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.

Quoted 3 lines

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.

Quoted 4 lines
Quoted 1 line

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.

Quoted 6 lines
Quoted 3 lines

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

#11 lore raw

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

Quoted 8 lines · Thomas Gleixner
Quoted 7 lines · Daniel Walker
Quoted 4 lines · Thomas Gleixner

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 ?

Quoted 4 lines
Quoted 1 line

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.

Quoted 2 lines

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.

Quoted 6 lines
Quoted 4 lines
Quoted 1 line

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?

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

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

#12 lore raw

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

Quoted 9 lines · Daniel Walker
Quoted 8 lines · Thomas Gleixner
Quoted 7 lines · Daniel Walker
Quoted 4 lines · Thomas Gleixner

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 ?

Quoted 6 lines
Quoted 4 lines
Quoted 1 line

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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 10 lines
Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

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

#13 lore raw

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

Quoted 10 lines · Thomas Gleixner
Quoted 4 lines
Quoted 2 lines

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 ..

Quoted 7 lines

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?

Quoted 5 lines

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

#14 lore raw

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

Quoted 7 lines · On Sat, 24 May 2008 12:19:34 -0700 Daniel Walker <[email protected]> wrote:
Quoted 3 lines

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.