sched/wait: abort_exclusive_wait() should pass TASK_NORMAL to wake_up()

To simplify the review see the code with the patch applied:

int __sched
__wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
wait_bit_action_f *action, unsigned mode)

{
	int ret = 0;

	for (;;) {
		prepare_to_wait_exclusive(wq, &q->wait, mode);
		if (test_bit(q->key.bit_nr, q->key.flags)) {
			ret = action(&q->key, mode);
			/*
			 * Ensure that clear_bit() + wake_up() right after
			 * test_and_set_bit() below can't see us; it should
			 * wake up another exclusive waiter if we fail.
			 */
			if (ret)
				finish_wait(wq, &q->wait);
		}
		if (!test_and_set_bit(q->key.bit_nr, q->key.flags)) {
			if (!ret)
				finish_wait(wq, &q->wait);
			return 0;
		} else if (ret) {
			return ret;
		}
	}
}

Otherwise this logic only works if mode is "compatible" with another exclusive waiter.

If some wq has both TASK_INTERRUPTIBLE and TASK_UNINTERRUPTIBLE waiters, abort_exclusive_wait() won't wait an uninterruptible waiter.

The main user is __wait_on_bit_lock() and currently it is fine but only because TASK_KILLABLE includes TASK_UNINTERRUPTIBLE and we do not have lock_page_interruptible() yet.

Just use TASK_NORMAL and remove the "mode" arg from abort_exclusive_wait(). Yes, this means that (say) wake_up_interruptible() can wake up the non- interruptible waiter(s), but I think this is fine. And in fact I think that abort_exclusive_wait() must die, see the next change.

---
 include/linux/wait.h | 6 +++---
 kernel/sched/wait.c  | 8 +++-----
 2 files changed, 6 insertions(+), 8 deletions(-)

index 27d7a0a..329f796 100644
@@ -281,8 +281,8 @@ wait_queue_head_t *bit_waitqueue(void *, int);
 		if (___wait_is_interruptible(state) && __int) {		\
 			__ret = __int;					\
 			if (exclusive) {				\
-				abort_exclusive_wait(&wq, &__wait,	\
-						     state, NULL);	\
+				abort_exclusive_wait(&wq, &__wait, 	\
+						     NULL);		\
 				goto __out;				\
 			}						\
 			break;						\

@@ -976,7 +976,7 @@ void prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state);
 void prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state);
 long prepare_to_wait_event(wait_queue_head_t *q, wait_queue_t *wait, int state);
 void finish_wait(wait_queue_head_t *q, wait_queue_t *wait);
-void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait, unsigned int mode, void *key);
+void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait, void *key);
 long wait_woken(wait_queue_t *wait, unsigned mode, long timeout);
 int woken_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key);
 int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key);

index f15d6b6..2bbba01 100644
@@ -259,7 +259,6 @@ EXPORT_SYMBOL(finish_wait);
  * abort_exclusive_wait - abort exclusive waiting in a queue
  * @q: waitqueue waited on
  * @wait: wait descriptor
- * @mode: runstate of the waiter to be woken
  * @key: key to identify a wait bit queue or %NULL
  *
  * Sets current thread back to running state and removes

@@ -273,8 +272,7 @@ EXPORT_SYMBOL(finish_wait);
  * aborts and is woken up concurrently and no one wakes up
  * the next waiter.
  */
-void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait,
-			unsigned int mode, void *key)
+void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait, void *key)
 {
 	unsigned long flags;
 

@@ -283,7 +281,7 @@ void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait,
 	if (!list_empty(&wait->task_list))
 		list_del_init(&wait->task_list);
 	else if (waitqueue_active(q))
-		__wake_up_locked_key(q, mode, key);
+		__wake_up_locked_key(q, TASK_NORMAL, key);
 	spin_unlock_irqrestore(&q->lock, flags);
 }
 EXPORT_SYMBOL(abort_exclusive_wait);

@@ -434,7 +432,7 @@ __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
 		ret = action(&q->key, mode);
 		if (!ret)
 			continue;
-		abort_exclusive_wait(wq, &q->wait, mode, &q->key);
+		abort_exclusive_wait(wq, &q->wait, &q->key);
 		return ret;
 	} while (test_and_set_bit(q->key.bit_nr, q->key.flags));
 	finish_wait(wq, &q->wait);

2.5.0

To clarify, this can't fix the lock_page() hang reported by Bart, __wait_on_bit_lock() is fine even if abort_exclusive_wait() is buggy.

Still should be fixed I think. And perhaps we should simply kill abort_exclusive_wait() ? See 2/2.

And this reminds me... I still fail to understand why/how the commit 68985633bccb60 "sched/wait: Fix signal handling in bit wait helpers" can help. Apart from s/return 1/return -EINTR/. Peter, do you have any theory?

Oleg.

I think it would be nice to kill abort_exclusive_wait(). This patch changes __wait_on_bit_lock(), but we can do a similar change to remove it from ___wait_event().

We do not need anything tricky to avoid the race, we can just call finish_wait() if action() fails. test_and_set_bit() implies mb() so the lockless list_empty_careful() case is fine, we can not miss the condition if we race with unlock_page().

I am not sure we even want to conditionalize both finish_wait()'s, we could simply call it unconditionally and once before test_and_set(), the spurious wakeup is unlikely case.

---
 kernel/sched/wait.c | 32 ++++++++++++++++++++------------
 1 file changed, 20 insertions(+), 12 deletions(-)

index 2bbba01..c10e904 100644
@@ -423,20 +423,28 @@ int __sched
 __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
 			wait_bit_action_f *action, unsigned mode)
 {
-	do {
-		int ret;
+	int ret = 0;
 
+	for (;;) {
 		prepare_to_wait_exclusive(wq, &q->wait, mode);
-		if (!test_bit(q->key.bit_nr, q->key.flags))
-			continue;
-		ret = action(&q->key, mode);
-		if (!ret)
-			continue;
-		abort_exclusive_wait(wq, &q->wait, &q->key);
-		return ret;
-	} while (test_and_set_bit(q->key.bit_nr, q->key.flags));
-	finish_wait(wq, &q->wait);
-	return 0;
+		if (test_bit(q->key.bit_nr, q->key.flags)) {
+			ret = action(&q->key, mode);
+			/*
+			 * Ensure that clear_bit() + wake_up() right after
+			 * test_and_set_bit() below can't see us; it should
+			 * wake up another exclusive waiter if we fail.
+			 */
+			if (ret)
+				finish_wait(wq, &q->wait);
+		}
+		if (!test_and_set_bit(q->key.bit_nr, q->key.flags)) {
+			if (!ret)
+				finish_wait(wq, &q->wait);
+			return 0;
+		} else if (ret) {
+			return ret;
+		}
+	}
 }
 EXPORT_SYMBOL(__wait_on_bit_lock);
 

2.5.0

No, I was (and still am) completely puzzled by that one.

So mixing INTERRUPTIBLE and UNINTERRUPTIBLE and then not using TASK_NORMAL for wakeups is a mis-feature/abuse of waitqueues IMO.

That said, people do 'creative' things, so maybe we should add some debug infra to detect this mis-match.

Something like the below perhaps? It will miss people using the (old) add_wait_queue() (which are plenty :/) but there's nothing quick we can do about those.

Completely untested..

---
 include/linux/wait.h | 13 ++++++++++++-
 kernel/sched/wait.c  | 27 +++++++++++++++++++++++++++
 2 files changed, 39 insertions(+), 1 deletion(-)

index c3ff74d764fa..e99ea720c5f9 100644
@@ -39,6 +39,9 @@ struct wait_bit_queue {
 struct __wait_queue_head {
 	spinlock_t		lock;
 	struct list_head	task_list;
+#ifdef CONFIG_DEBUG_WAITQUEUE
+	unsigned int		state;
+#endif
 };
 typedef struct __wait_queue_head wait_queue_head_t;
 

@@ -48,6 +51,13 @@ struct task_struct;
  * Macros for declaration and initialisaton of the datatypes
  */
 
+#ifdef CONFIG_DEBUG_WAITQUEUE
+#define __DEBUG_WAIT_QUEUE_HEAD_INIT(name)				\
+	.state = -1,
+#else
+#define __DEBUG_WAIT_QUEUE_HEAD_INIT(name)
+#endif
+
 #define __WAITQUEUE_INITIALIZER(name, tsk) {				\
 	.private	= tsk,						\
 	.func		= default_wake_function,			\

@@ -58,7 +68,8 @@ struct task_struct;
 
 #define __WAIT_QUEUE_HEAD_INITIALIZER(name) {				\
 	.lock		= __SPIN_LOCK_UNLOCKED(name.lock),		\
-	.task_list	= { &(name).task_list, &(name).task_list } }
+	.task_list	= { &(name).task_list, &(name).task_list },	\
+	__DEBUG_WAIT_QUEUE_HEAD_INIT(name) }
 
 #define DECLARE_WAIT_QUEUE_HEAD(name) \
 	wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

index f15d6b6a538a..cb71c56c5e76 100644
@@ -16,6 +16,9 @@ void __init_waitqueue_head(wait_queue_head_t *q, const char *name, struct lock_c
 	spin_lock_init(&q->lock);
 	lockdep_set_class_and_name(&q->lock, key, name);
 	INIT_LIST_HEAD(&q->task_list);
+#ifdef CONFIG_DEBUG_WAITQUEUE
+	q->state = -1;
+#endif
 }
 
 EXPORT_SYMBOL(__init_waitqueue_head);

@@ -67,6 +70,16 @@ static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
 {
 	wait_queue_t *curr, *next;
 
+#ifdef CONFIG_DEBUG_WAITQUEUE
+	if (q->state != -1) {
+		/*
+		 * WARN if we have INTERRUPTIBLE and UNINTERRUPTIBLE
+		 * waiters and do not use TASK_NORMAL to wake.
+		 */
+		WARN_ON_ONCE(q->state != (mode & TASK_NORMAL));
+	}
+#endif
+
 	list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
 		unsigned flags = curr->flags;
 

@@ -156,6 +169,17 @@ void __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
 }
 EXPORT_SYMBOL_GPL(__wake_up_sync);	/* For internal use only */
 
+static inline void prepare_debug(struct wait_queue_head *q, int state)
+{
+#ifdef CONFIG_DEBUG_WAITQUEUE
+	if (q->state == -1) {
+		q->state = state & TASK_NORMAL;
+	} else {
+		q->state |= state & TASK_NORMAL;
+	}
+#endif
+}
+
 /*
  * Note: we use "set_current_state()" _after_ the wait-queue add,
  * because we need a memory barrier there on SMP, so that any

@@ -178,6 +202,7 @@ prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
 	if (list_empty(&wait->task_list))
 		__add_wait_queue(q, wait);
 	set_current_state(state);
+	prepare_debug(q, state);
 	spin_unlock_irqrestore(&q->lock, flags);
 }
 EXPORT_SYMBOL(prepare_to_wait);

@@ -192,6 +217,7 @@ prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state)
 	if (list_empty(&wait->task_list))
 		__add_wait_queue_tail(q, wait);
 	set_current_state(state);
+	prepare_debug(q, state);
 	spin_unlock_irqrestore(&q->lock, flags);
 }
 EXPORT_SYMBOL(prepare_to_wait_exclusive);

@@ -214,6 +240,7 @@ long prepare_to_wait_event(wait_queue_head_t *q, wait_queue_t *wait, int state)
 			__add_wait_queue(q, wait);
 	}
 	set_current_state(state);
+	prepare_debug(q, state);
 	spin_unlock_irqrestore(&q->lock, flags);
 
 	return 0;

This ^^^

Nope, because we need to do that finish_wait() before test_and_set_bit()..

Also the problem with doing finish_wait() unconditionally would be destroying the FIFO order. With a bit of bad luck you'd get starvation cases :/

Heh, agreed. When I was doing this fix I suddenly realize that I do not understand why do we have, say, wake_up_interruptible().

I mean, I can't imagine the "real" use-case when you actually want to wake up only the INTERRUPTIBLE tasks and leave the UNINTERRUPTIBLE sleeping. Exclusive or not.

It seems that wake_up_interruptible() is mostly used simply because the caller knows that UNINTERRUPTIBLE waiters are not possible, this is often the case.

The race being:

CPU0 CPU1 CPU2

			__wait_on_bit_lock()
			  bit_wait_io()
			    io_schedule()

clear_bit_unlock()
__wake_up_common(.nr_exclusive=1)
list_for_each_entry()

    if (curr->func() && --nr_exclusive)
      break

						signal()

			    if (signal_pending_state()) == TRUE
			      return -EINTR

And no progress because CPU1 exits without acquiring the lock and CPU0 thinks its done because it woke someone.

That would be bit_wait*() returning -EINTR because sigpending.

Sure, you can always call that, first thing through the loop does prepare again, so no harm. That however does not connect to your condition,.. /me puzzled

You're talking about this ordering?:

	finish_wait()			clear_bit_unlock();
	  list_empty_careful()

	/* MB implied */		smp_mb__after_atomic();
	test_and_set_bit()		wake_up_page()
					  ...
					    autoremove_wake_function()
					      list_del_init();

That could do with spelling out I feel.. :-)

	ret = 0;

	for (;;) {
		prepare_to_wait_exclusive(wq, &q->wait, mode);

		if (test_bit(&q->key.bit_nr, &q->key.flag))
			ret = action(&q->key, mode);

		if (!test_and_set_bit(&q->key.bit_nr, &q->key.flag)) {
			/* we got the lock anyway, ignore the signal */
			ret = 0;
			break;
		}

		if (ret)
			break;
	}
	finish_wait(wq, &q->wait);

	return ret;

Would not that work too?

FWIW, the way the mutex code avoids this issue is by doing the signal_pending test while holding the q->lock, that way its exclusive with wakeup.

I suspect the same.

I think its a fairly fundamental thing, its part of the semantics of TASK_KILLABLE. Namely its UNINTERRUPTIBLE, except you can interrupt it with fatal. A TASK_NORMAL wake should very much wake a TASK_KILLABLE sleep, and for that to happen they need to share a bit, namely UNINTERRUPTIBLE.

But I agree with you, all waitqueue wakeups _should_ simply be TASK_NORMAL. Like said, I don't see it ever makes sense to play games with it.

Now, let me try and get back to making sense of your abort abortion ;-)

Yes,

Hmm. Not sure I understand... Let me reply just in case, even if I am sure you get it right.

Yes, in the likely case we are going to fail with -EINTR, but only if test-and-set after thar fails.

If ->action() fails we will abort the loop in any case, prepare won't be called. So in this case finish_wait() does the right thing.

Yes, yes.

Yes. This way we eliminate the need for the additional wake_up.

Oleg.

Yes, I meant

	int __sched
	__wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
				wait_bit_action_f *action, unsigned mode)
	{
		int ret = 0;

		for (;;) {
			prepare_to_wait_exclusive(wq, &q->wait, mode);
			if (test_bit(q->key.bit_nr, q->key.flags))
				ret = action(&q->key, mode);

			finish_wait(wq, &q->wait);

			if (!test_and_set_bit(q->key.bit_nr, q->key.flags))
				return 0;
			else if (ret)
				return ret;

		}
	}

OK, I didn't think about that, thanks.

Oleg.

And __wait_event_interruptible_locked() too.

BTW it is buggy anyway, it needs the

	-	__add_wait_queue_tail(&(wq), &__wait);
	+	if (exclusive)
	+		__add_wait_queue_tail(&(wq), &__wait);
	+	else
	+		__add_wait_queue((&(wq), &__wait);

and in fact it should use __add_wait_queue_exclusive() so that we can remove another "if (exclusive)" but this is off-topic.

Yes, I considered this option, but to me the addtional finish_wait() looks simpler.

And, if you agree with this change I will try to change __wait_event() as well and kill abort_exclusive_wait().

And in this case we certainly do not want to check the "condition" with q->lock held, because this would mean that "condition" won't be able to take this lock.

Oleg.

its all relative, this stuff always makes my head hurt one way or the other ;-)

Yeah, I think this'll work. Please send a new series with 'enhanced' changelog so that when we have to look at this again in a few weeks/months time we won't be cursing at ourselves for how the heck it was supposed to work.