+ lock_page_killable-avoid-lost-wakeups.patch added to -mm tree

int __lock_page_killable(struct page *page)
{

(quoted diff) +2 -1

 	DEFINE_WAIT_BIT(wait, &page->flags, PG_locked);
+	int ret;
 
-	return __wait_on_bit_lock(page_waitqueue(page), &wait,
+	ret = __wait_on_bit_lock(page_waitqueue(page), &wait,

I think the patch is correct, just a question,

Quoted 7 lines

int __lock_page_killable(struct page *page)
{

(quoted diff) +2 -1

 	DEFINE_WAIT_BIT(wait, &page->flags, PG_locked);
+	int ret;
 
-	return __wait_on_bit_lock(page_waitqueue(page), &wait,
+	ret = __wait_on_bit_lock(page_waitqueue(page), &wait,

Review

Quoted 10 lines

(quoted diff) +9 -0

 					sync_page_killable, TASK_KILLABLE);
+	/*
+	 * wait_on_bit_lock uses prepare_to_wait_exclusive, so if multiple
+	 * procs were waiting on this page, we were the only proc woken up.
+	 *
+	 * if ret != 0, we didn't actually get the lock.  We need to
+	 * make sure any other waiters don't sleep forever.
+	 */
+	if (ret)
+		wake_up_page(page, PG_locked);

This patch assumes that nobody else calls __wait_on_bit_lock() with action which can return !0. Currently this is correct, but perhaps it makes sense to move this wake_up_page() into __wait_on_bit_lock ?

Note that we need to "transfer" the wakeup only if wake_up_page() has already removed us from page_waitqueue(page), this means we don't need to check ret != 0 twice in __wait_on_bit_lock(), afaics we can do

	if ((ret = (*action)(q->key.flags))) {
		__wake_up_bit(wq, q->key.flags, q->key.bit_nr);
		// or just __wake_up(wq, TASK_NORMAL, 1, &q->key);
		break;
	}

IOW, imho __wait_on_bit_lock() is buggy, not __lock_page_killable(), no?

Quoted 9 lines · Oleg Nesterov

	if ((ret = (*action)(q->key.flags))) {
		__wake_up_bit(wq, q->key.flags, q->key.bit_nr);
		// or just __wake_up(wq, TASK_NORMAL, 1, &q->key);
		break;
	}

IOW, imho __wait_on_bit_lock() is buggy, not __lock_page_killable(), no?

I agree with you, already replied with a patch to linux-mm where Chris posted it originally.

Peter noted that we have a spurious wake up in the case where A holds the page lock, B and C wait, B gets killed and does a wake up, then A unlocks and does a wake up. Your proposal has this problem too, right?

kernel/wait.c +1 -1

@@ -182,8 +182,20 @@ __wait_on_bit_lock(wait_queue_head_t *wq
 	do {
 		prepare_to_wait_exclusive(wq, &q->wait, mode);
 		if (test_bit(q->key.bit_nr, q->key.flags)) {
-			if ((ret = (*action)(q->key.flags)))
+			ret = action(q->key.flags);

Quoted 12 lines · Johannes Weiner

Quoted 9 lines · Oleg Nesterov

	if ((ret = (*action)(q->key.flags))) {
		__wake_up_bit(wq, q->key.flags, q->key.bit_nr);
		// or just __wake_up(wq, TASK_NORMAL, 1, &q->key);
		break;
	}

IOW, imho __wait_on_bit_lock() is buggy, not __lock_page_killable(), no?

Quoted 7 lines

I agree with you, already replied with a patch to linux-mm where Chris posted it originally.

Peter noted that we have a spurious wake up in the case where A holds the page lock, B and C wait, B gets killed and does a wake up, then A unlocks and does a wake up. Your proposal has this problem too, right?

Yes sure. But I can't see how it is possible to avoid the false wakeup for sure, please see below.

Quoted 6 lines

kernel/wait.c +1 -1

@@ -182,8 +182,20 @@ __wait_on_bit_lock(wait_queue_head_t *wq
 	do {
 		prepare_to_wait_exclusive(wq, &q->wait, mode);
 		if (test_bit(q->key.bit_nr, q->key.flags)) {
-			if ((ret = (*action)(q->key.flags)))
+			ret = action(q->key.flags);

kernel/wait.c __wait_on_bit_lock(wait_queue_head_t *wq · line 195

Quoted 10 lines

kernel/wait.c +10 -0

+			if (ret) {
+				/*
+				 * Contenders are woken exclusively.  If
+				 * we do not take the lock when woken up
+				 * from an unlock, we have to make sure to
+				 * wake the next waiter in line or noone
+				 * will and shkle will wait forever.
+				 */
+				if (!test_bit(q->key.bit_nr, q->key.flags))
+					__wake_up_bit(wq, q->key.flags,

Afaics, the spurious wake up is still possible if SIGKILL and unlock_page() happen "at the same time".

	__wait_on_bit_lock:			unlock_page:

						clear_bit_unlock()
	test_bit() == T

	__wake_up_bit()				wake_up_page()

Note that sync_page_killable() returns with ->state == TASK_RUNNING, __wake_up() will "ignore" us.

But, more importantly, I'm afraid we can also have the false negative, this "if (!test_bit())" test lacks the barriers. This can't happen with sync_page_killable() because it always calls schedule(). But let's suppose we modify it to check signal_pending() first:

	static int sync_page_killable(void *word)
	{
		if (fatal_signal_pending(current))
			return -EINTR;
		return sync_page(word);
	}

It is still correct, but unless I missed something now __wait_on_bit_lock() has problems again.

But don't get me wrong, I think you are right and it is better to minimize the possibility of the false wakeup.

Oleg.

Quoted 13 lines

But, more importantly, I'm afraid we can also have the false negative, this "if (!test_bit())" test lacks the barriers. This can't happen with sync_page_killable() because it always calls schedule(). But let's suppose we modify it to check signal_pending() first:

	static int sync_page_killable(void *word)
	{
		if (fatal_signal_pending(current))
			return -EINTR;
		return sync_page(word);
	}

Quoted 2 lines

It is still correct, but unless I missed something now __wait_on_bit_lock() has problems again.

Hm, this would require the lock bit to be set without someone else doing the wakeup. How could this happen?

I could think of wake_up_page() happening BEFORE clear_bit_unlock() and we have to be on the front of the waitqueue. Then we are already running, the wake up is a nop, the !test_bit() is false and noone wakes up the next real contender.

But the wake up side uses a smp barrier after clearing the bit, so if the bit is not cleared we can expect a wake up, no?

Or do we still need a read-side barrier before the test bit?

Quoted 19 lines · Johannes Weiner

Quoted 13 lines

But, more importantly, I'm afraid we can also have the false negative, this "if (!test_bit())" test lacks the barriers. This can't happen with sync_page_killable() because it always calls schedule(). But let's suppose we modify it to check signal_pending() first:

	static int sync_page_killable(void *word)
	{
		if (fatal_signal_pending(current))
			return -EINTR;
		return sync_page(word);
	}

Quoted 2 lines

It is still correct, but unless I missed something now __wait_on_bit_lock() has problems again.

Hm, this would require the lock bit to be set without someone else doing the wakeup. How could this happen?

Quoted 7 lines

I could think of wake_up_page() happening BEFORE clear_bit_unlock() and we have to be on the front of the waitqueue. Then we are already running, the wake up is a nop, the !test_bit() is false and noone wakes up the next real contender.

But the wake up side uses a smp barrier after clearing the bit, so if the bit is not cleared we can expect a wake up, no?

Yes we have the barriers on the "wakeup", but this doesn't mean the woken task must see the result of clear_bit() (unless it was really unscheduled of course).

Quoted 1 line

Or do we still need a read-side barrier before the test bit?

Even this can't help afaics.

Because the the whole clear_bit + wakeup sequence can happen after the "if (!test_bit()) check and before finish_wait(). Please note that from the waker's pov we are sleeping in TASK_KILLABLE state, it will wake up us if we are at the front of the waitqueue.

kernel/wait.c +14 -0

@@ -187,6 +187,31 @@ __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
 		}
 	} while (test_and_set_bit(q->key.bit_nr, q->key.flags));
 	finish_wait(wq, &q->wait);
+	if (unlikely(ret)) {
+		/*
+		 * Contenders are woken exclusively.  If we were woken
+		 * by an unlock we have to take the lock ourselves and
+		 * wake the next contender on unlock.  But the waiting
+		 * function failed, we do not take the lock and won't
+		 * unlock in the future.  Make sure the next contender
+		 * does not wait forever on an unlocked bit.
+		 *
+		 * We can also get here without being woken through
+		 * the waitqueue, so there is a small chance of doing a
+		 * bogus wake up between an unlock clearing the bit and
+		 * the next contender being woken up and setting it again.
+		 *

Quoted 24 lines

kernel/wait.c +19 -0

@@ -187,6 +187,31 @@ __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
              }
      } while (test_and_set_bit(q->key.bit_nr, q->key.flags));
      finish_wait(wq, &q->wait);
+     if (unlikely(ret)) {
+             /*
+              * Contenders are woken exclusively.  If we were woken
+              * by an unlock we have to take the lock ourselves and
+              * wake the next contender on unlock.  But the waiting
+              * function failed, we do not take the lock and won't
+              * unlock in the future.  Make sure the next contender
+              * does not wait forever on an unlocked bit.
+              *
+              * We can also get here without being woken through
+              * the waitqueue, so there is a small chance of doing a
+              * bogus wake up between an unlock clearing the bit and
+              * the next contender being woken up and setting it again.
+              *
+              * It does no harm, though, the scheduler will ignore it
+              * as the process in question is already running.
+              *
+              * The unlock path clears the bit and then wakes up the
+              * next contender.  If the next contender is us, the

kernel/wait.c __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q, · line 213

Quoted 5 lines

kernel/wait.c +5 -0

+              * barrier makes sure we also see the bit cleared.
+              */
+             smp_rmb();
+             if (!test_bit(q->key.bit_nr, q->key.flags)))
+                     __wake_up_bit(wq, q->key.flags, q->key.bit_nr);

I think this is correct, and (unfortunately ;) you are right:
we need rmb() even after finish_wait().

For example, don't we have the similar problems with wait_event_interruptible_exclusive() ?

Oleg.

2009/1/22 Oleg Nesterov <[email protected]>:

Quoted 3 lines

I think this is correct, and (unfortunately ;) you are right:
we need rmb() even after finish_wait().

Hum, I think it's actually not necessary in this particular case when
(1) "the next contender is us" and (2) we are in the "ret != 0" path so that the only thing we really care about -- if we were exclusivly woken up, then wake up somebody else [*].

"the next contender is us" implies that we were still on the 'wq' queue when __wake_up_bit() -> __wake_up() has been called, meaning that wq->lock has also been taken (in __wake_up()).

Now, on our side, we are definitely on the 'wq' queue before calling finish_wait(), meaning that we also take the wq->lock.

In short, wq->lock is a sync. mechanism in this case. The scheme is as follows:

our side:

[ finish_wait() ]

lock(wq->lock);

p.s. if the explanation is vague or heh even wrong, it's definitely due to the lack of sleep ;-))

Quoted 19 lines · Johannes Weiner

kernel/wait.c +14 -0

@@ -187,6 +187,31 @@ __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
 		}
 	} while (test_and_set_bit(q->key.bit_nr, q->key.flags));
 	finish_wait(wq, &q->wait);
+	if (unlikely(ret)) {
+		/*
+		 * Contenders are woken exclusively.  If we were woken
+		 * by an unlock we have to take the lock ourselves and
+		 * wake the next contender on unlock.  But the waiting
+		 * function failed, we do not take the lock and won't
+		 * unlock in the future.  Make sure the next contender
+		 * does not wait forever on an unlocked bit.
+		 *
+		 * We can also get here without being woken through
+		 * the waitqueue, so there is a small chance of doing a
+		 * bogus wake up between an unlock clearing the bit and
+		 * the next contender being woken up and setting it again.
+		 *

kernel/wait.c __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q, · line 213

Quoted 10 lines

kernel/wait.c +10 -0

+		 * It does no harm, though, the scheduler will ignore it
+		 * as the process in question is already running.
+		 *
+		 * The unlock path clears the bit and then wakes up the
+		 * next contender.  If the next contender is us, the
+		 * barrier makes sure we also see the bit cleared.
+		 */
+		smp_rmb();
+		if (!test_bit(q->key.bit_nr, q->key.flags)))
+			__wake_up_bit(wq, q->key.flags, q->key.bit_nr);

I think this is correct, and (unfortunately ;) you are right:
we need rmb() even after finish_wait().

And we have to check ret twice, and the false wakeup is still possible. This is minor, but just for discussion, can't we do this differently?

	int finish_wait_xxx(wait_queue_head_t *q, wait_queue_t *wait)
	{
		unsigned long flags;
		int woken;

		__set_current_state(TASK_RUNNING);
		spin_lock_irqsave(&q->lock, flags);
		woken = list_empty(&wait->task_list);
		list_del_init(&wait->task_list);
		spin_unlock_irqrestore(&q->lock, flags);

		return woken;
	}

Now, __wait_on_bit_lock() does:

		if (test_bit(q->key.bit_nr, q->key.flags)) {
			if ((ret = (*action)(q->key.flags))) {
				if (finish_wait_xxx(...))
					__wake_up_bit(...);
				return ret;
			}
		}

Or we can introduce

	int finish_wait_yyy(wait_queue_head_t *q, wait_queue_t *wait,
				int mode, void *key)
	{
		unsigned long flags;
		int woken;

		__set_current_state(TASK_RUNNING);
		spin_lock_irqsave(&q->lock, flags);
		woken = list_empty(&wait->task_list);
		if (woken)
			__wake_up_common(q, mode, 1, key);
		else
			list_del_init(&wait->task_list);
		spin_unlock_irqrestore(&q->lock, flags);

		return woken;
	}

Perhaps a bit too much for this particular case, but I am thinking about other cases when we need to abort the exclusive wait.

For example, don't we have the similar problems with wait_event_interruptible_exclusive() ?

Oleg.

Quoted 22 lines

2009/1/22 Oleg Nesterov <[email protected]>:

Quoted 3 lines

I think this is correct, and (unfortunately ;) you are right:
we need rmb() even after finish_wait().

Hum, I think it's actually not necessary in this particular case when
(1) "the next contender is us" and (2) we are in the "ret != 0" path so that the only thing we really care about -- if we were exclusivly woken up, then wake up somebody else [*].

"the next contender is us" implies that we were still on the 'wq' queue when __wake_up_bit() -> __wake_up() has been called, meaning that wq->lock has also been taken (in __wake_up()).

Now, on our side, we are definitely on the 'wq' queue before calling finish_wait(), meaning that we also take the wq->lock.

In short, wq->lock is a sync. mechanism in this case. The scheme is as follows:

our side:

Quoted 3 lines

[ finish_wait() ]

lock(wq->lock);

But we can skip lock(wq->lock), afaics.

Without rmb(), test_bit() can be re-ordered with list_empty_careful() in finish_wait() and even with __set_task_state(TASK_RUNNING).

Oleg.

2009/1/23 Oleg Nesterov <[email protected]>:

Quoted 6 lines · Dmitry Adamushko

Quoted 5 lines

In short, wq->lock is a sync. mechanism in this case. The scheme is as follows:

our side:

Quoted 8 lines

Quoted 3 lines

[ finish_wait() ]

lock(wq->lock);

But we can skip lock(wq->lock), afaics.

Without rmb(), test_bit() can be re-ordered with list_empty_careful() in finish_wait() and even with __set_task_state(TASK_RUNNING).

But taking into account the constraints of this special case, namely (1), we can't skip lock(wq->lock).

(1) "the next contender is us"

In this particular situation, we are only interested in the case when we were woken up by __wake_up_bit().

that means we are _on_ the 'wq' list when we do finish_wait() -> we do take the 'wq->lock'.

Moreover, imagine the following case (roughly similar to finish_wait()):

if (LOAD(a) == 1) {
    // do something here
    mb();
}

LOAD(b);

Can LOAD(b) be reordered with LOAD(a)?

Quoted 13 lines · Oleg Nesterov

Quoted 1 line · Johannes Weiner

	int finish_wait_xxx(wait_queue_head_t *q, wait_queue_t *wait)
	{
		unsigned long flags;
		int woken;

		__set_current_state(TASK_RUNNING);
		spin_lock_irqsave(&q->lock, flags);
		woken = list_empty(&wait->task_list);
		list_del_init(&wait->task_list);
		spin_unlock_irqrestore(&q->lock, flags);

Quoted 2 lines

		return woken;
	}

Hehe, there is only n solutions to this problem. I had thought about that too, even written it down. But I was not sure if taking the spinlock, toggling irqs and (re)storing the flags is better than an untaken branch. ;)

Quoted 7 lines

		if (test_bit(q->key.bit_nr, q->key.flags)) {
			if ((ret = (*action)(q->key.flags))) {
				if (finish_wait_xxx(...))
					__wake_up_bit(...);
				return ret;
			}
		}

If you don't mind putting a second finish_wait() in there (you still need the one after the loop, right?), we can fix up my version to not check ret twice but do finish_wait() as you describe and then the test_bit() && wake up:

	do {
		if (test_bit())
			if ((ret = action())) {
				finish_wait()
				smp_rmb()
				if (!test_bit())
					__wake_up_bit()

Quoted 18 lines

	int finish_wait_yyy(wait_queue_head_t *q, wait_queue_t *wait,
				int mode, void *key)
	{
		unsigned long flags;
		int woken;

		__set_current_state(TASK_RUNNING);
		spin_lock_irqsave(&q->lock, flags);
		woken = list_empty(&wait->task_list);
		if (woken)
			__wake_up_common(q, mode, 1, key);
		else
			list_del_init(&wait->task_list);
		spin_unlock_irqrestore(&q->lock, flags);

		return woken;
	}

Quoted 5 lines

Perhaps a bit too much for this particular case, but I am thinking about other cases when we need to abort the exclusive wait.

For example, don't we have the similar problems with wait_event_interruptible_exclusive() ?

Yeah, we do IIUC. Then having finish_wait() extended is probably a good idea.

Quoted 17 lines

2009/1/23 Oleg Nesterov <[email protected]>:

Quoted 6 lines · Dmitry Adamushko

Quoted 5 lines

In short, wq->lock is a sync. mechanism in this case. The scheme is as follows:

our side:

Quoted 8 lines

Quoted 3 lines

[ finish_wait() ]

lock(wq->lock);

But we can skip lock(wq->lock), afaics.

Without rmb(), test_bit() can be re-ordered with list_empty_careful() in finish_wait() and even with __set_task_state(TASK_RUNNING).

Quoted 7 lines

But taking into account the constraints of this special case, namely (1), we can't skip lock(wq->lock).

(1) "the next contender is us"

In this particular situation, we are only interested in the case when we were woken up by __wake_up_bit().

Yes,

Quoted 2 lines

that means we are _on_ the 'wq' list when we do finish_wait() -> we do take the 'wq->lock'.

Hmm. No?

We are doing exclusive wait, and we use autoremove_wake_function(). If we were woken, we are removed from ->task_list.

Oleg.

It is no that I think this new helper is really needed for this particular case, personally I agree with the patch you sent.

But if we have other places with the similar problem, then perhaps it is better to introduce the special finish_wait_exclusive() or whatever.

Quoted 15 lines · Johannes Weiner

Quoted 13 lines · Oleg Nesterov

Quoted 1 line · Johannes Weiner

	int finish_wait_xxx(wait_queue_head_t *q, wait_queue_t *wait)
	{
		unsigned long flags;
		int woken;

		__set_current_state(TASK_RUNNING);
		spin_lock_irqsave(&q->lock, flags);
		woken = list_empty(&wait->task_list);
		list_del_init(&wait->task_list);
		spin_unlock_irqrestore(&q->lock, flags);

Quoted 7 lines

Quoted 2 lines

		return woken;
	}

Hehe, there is only n solutions to this problem. I had thought about that too, even written it down. But I was not sure if taking the spinlock, toggling irqs and (re)storing the flags is better than an untaken branch. ;)

Yes. Fortunately, this is "unlikely" path.

Quoted 13 lines

Quoted 7 lines

		if (test_bit(q->key.bit_nr, q->key.flags)) {
			if ((ret = (*action)(q->key.flags))) {
				if (finish_wait_xxx(...))
					__wake_up_bit(...);
				return ret;
			}
		}

If you don't mind putting a second finish_wait() in there (you still need the one after the loop, right?), we can fix up my version to not check ret twice but do finish_wait() as you describe and then the test_bit() && wake up:

Quoted 7 lines

	do {
		if (test_bit())
			if ((ret = action())) {
				finish_wait()
				smp_rmb()
				if (!test_bit())
					__wake_up_bit()

Yes sure. Except this wakeup can be false.

Quoted 18 lines

Quoted 18 lines

	int finish_wait_yyy(wait_queue_head_t *q, wait_queue_t *wait,
				int mode, void *key)
	{
		unsigned long flags;
		int woken;

		__set_current_state(TASK_RUNNING);
		spin_lock_irqsave(&q->lock, flags);
		woken = list_empty(&wait->task_list);
		if (woken)
			__wake_up_common(q, mode, 1, key);
		else
			list_del_init(&wait->task_list);
		spin_unlock_irqrestore(&q->lock, flags);

		return woken;
	}

Quoted 8 lines

Quoted 5 lines

Perhaps a bit too much for this particular case, but I am thinking about other cases when we need to abort the exclusive wait.

For example, don't we have the similar problems with wait_event_interruptible_exclusive() ?

Yeah, we do IIUC. Then having finish_wait() extended is probably a good idea.

Yes.

It is no that I think this new helper is really needed for this particular case, personally I agree with the patch you sent.

But if we have other places with the similar problem, then perhaps it is better to introduce the special finish_wait_exclusive() or whatever.

Quoted 7 lines · Oleg Nesterov

It is no that I think this new helper is really needed for this particular case, personally I agree with the patch you sent.

But if we have other places with the similar problem, then perhaps it is better to introduce the special finish_wait_exclusive() or whatever.

To clarify, I suggest something like this.

	int finish_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait,
					int ret, int state, void *key)
	{
		unsigned long flags;

		__set_current_state(TASK_RUNNING);

		if (ret || !list_empty_careful(&wait->task_list)) {
			spin_lock_irqsave(&q->lock, flags);
			if (list_empty(&wait->task_list))
				 __wake_up_common(q, state, 1, key);
			else
				list_del_init(&wait->task_list);
			spin_unlock_irqrestore(&q->lock, flags);
		}

		return ret;
	}

Now, __wait_on_bit_lock() becomes:

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

		do {
			prepare_to_wait_exclusive(wq, &q->wait, mode);
			if (test_bit(q->key.bit_nr, q->key.flags) &&
			   (ret = (*action)(q->key.flags))
				break;
		} while (test_and_set_bit(q->key.bit_nr, q->key.flags));

		return finish_wait_exclusive(wq, &q->wait, ret, mode, &q->key);
	}

And __wait_event_interruptible_exclusive:

	#define __wait_event_interruptible_exclusive(wq, condition, ret)	\
	do {									\
		DEFINE_WAIT(__wait);						\
										\
		for (;;) {							\
			prepare_to_wait_exclusive(&wq, &__wait,			\
						TASK_INTERRUPTIBLE);		\
			if (condition)						\
				break;						\
			if (!signal_pending(current)) {				\
				schedule();					\
				continue;					\
			}							\
			ret = -ERESTARTSYS;					\
			break;							\
		}								\
		finish_wait_exclusive(&wq, &__wait,				\
					ret, TASK_INTERRUPTIBLE, NULL);		\
	} while (0)

But I can't convince myself this is what we really want. So I am not sending the patch. And yes, we have to check ret twice.

Another iteration. I didn't use a general finish_wait_exclusive() but a version of this function that just returns whether we were woken through the queue or not.

include/linux/wait.h +1 -1

@@ -333,16 +333,20 @@ do {									\
 	for (;;) {							\
 		prepare_to_wait_exclusive(&wq, &__wait,			\
 					TASK_INTERRUPTIBLE);		\
-		if (condition)						\
+		if (condition) {					\

Quoted 4 lines · Johannes Weiner

Another iteration. I didn't use a general finish_wait_exclusive() but a version of this function that just returns whether we were woken through the queue or not.

But if your helper (finish_wait_woken) returns true, we always need to wakeup the next waiter, or we don't need to use it. So why not place the wakeup in the helper itself?

Quoted 12 lines

include/linux/wait.h +3 -1

@@ -333,16 +333,20 @@ do {									\
 	for (;;) {							\
 		prepare_to_wait_exclusive(&wq, &__wait,			\
 					TASK_INTERRUPTIBLE);		\
-		if (condition)						\
+		if (condition) {					\
+			finish_wait(&wq, &__wait);			\
 			break;						\
+		}							\
 		if (!signal_pending(current)) {				\

include/linux/wait.h do { \ · line 346

Quoted 6 lines

include/linux/wait.h +2 -0

 			schedule();					\
 			continue;					\
 		}							\
 		ret = -ERESTARTSYS;					\
+		if (finish_wait_woken(&wq, &__wait))			\
+			__wake_up_common(&wq, TASK_INTERRUPTIBLE,	\

No, we can't use __wake_up_common() without wq->lock.

int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key) {

kernel/wait.c +2 -2

 	int ret = default_wake_function(wait, mode, sync, key);

@@ -177,17 +218,19 @@ int __sched
 __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
 			int (*action)(void *), unsigned mode)
 {
-	int ret = 0;
-
 	do {
+		int ret;
+

kernel/wait.c void finish_wait(wait_queue_head_t *q, wait_queue_t *wait) · line 147

Quoted 8 lines · Johannes Weiner

kernel/wait.c +7 -0

+void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait)
+{
+	unsigned long flags;
+
+	__set_current_state(TASK_RUNNING);
+	spin_lock_irqsave(&q->lock, flags);
+	if (list_empty(&wait->task_list))

Hmm... it should be !list_empty() ?

kernel/wait.c void finish_wait(wait_queue_head_t *q, wait_queue_t *wait) · line 158

Quoted 12 lines

kernel/wait.c +11 -0

+		list_del_init(&wait->task_list);
+	/*
+	 * If we were woken through the waitqueue (waker removed
+	 * us from the list) we must ensure the next waiter down
+	 * the line is woken up.  The callsite will not do it as
+	 * it didn't finish waiting successfully.
+	 */
+	else if (waitqueue_active(q))
+		__wake_up_locked(q, TASK_INTERRUPTIBLE);
+	spin_unlock_irqrestore(&q->lock, flags);
+}

Well, personally I don't care, but this is against CodingStyle rules ;)

Quoted 12 lines

int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key) {

kernel/wait.c +2 -2

 	int ret = default_wake_function(wait, mode, sync, key);

@@ -177,17 +218,19 @@ int __sched
 __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
 			int (*action)(void *), unsigned mode)
 {
-	int ret = 0;
-
 	do {
+		int ret;
+

kernel/wait.c int __sched · line 229

Quoted 10 lines

kernel/wait.c +5 -4

 		prepare_to_wait_exclusive(wq, &q->wait, mode);
-		if (test_bit(q->key.bit_nr, q->key.flags)) {
-			if ((ret = (*action)(q->key.flags)))
-				break;
-		}
+		if (!test_bit(q->key.bit_nr, q->key.flags))
+			continue;
+		if (!(ret = action(q->key.flags)))
+			continue;
+		abort_exclusive_wait(wq, &q->wait);

No, no. We should use the same key in abort_exclusive_wait(). Otherwise, how can we wakeup the next waiter which needs this bit in the same page->flags?

That is why I suggested finish_wait_exclusive(..., void *key) which should we passed to __wake_up_common().

Add abort_exclusive_wait() which removes the process' wait descriptor from the waitqueue, iff still queued, or wakes up the next waiter otherwise. It does so under the waitqueue lock. Racing with a wake up means the aborting process is either already woken (removed from the queue) and will wake up the next waiter, or it will remove itself from the queue and the concurrent wake up will apply to the next waiter after it.

Use abort_exclusive_wait() in __wait_event_interruptible_exclusive() and __wait_on_bit_lock() when they were interrupted by other means than a wake up through the queue.

Quoted 9 lines · Johannes Weiner

Add abort_exclusive_wait() which removes the process' wait descriptor from the waitqueue, iff still queued, or wakes up the next waiter otherwise. It does so under the waitqueue lock. Racing with a wake up means the aborting process is either already woken (removed from the queue) and will wake up the next waiter, or it will remove itself from the queue and the concurrent wake up will apply to the next waiter after it.

Quoted 3 lines

Use abort_exclusive_wait() in __wait_event_interruptible_exclusive() and __wait_on_bit_lock() when they were interrupted by other means than a wake up through the queue.

Imho, this all is right, and this patch should replace lock_page_killable-avoid-lost-wakeups.patch (except for stable tree).

Quoted 14 lines · On Thu, 29 Jan 2009 05:42:27 +0100 Oleg Nesterov <[email protected]> wrote:

Quoted 12 lines · Johannes Weiner

Add abort_exclusive_wait() which removes the process' wait descriptor from the waitqueue, iff still queued, or wakes up the next waiter otherwise. It does so under the waitqueue lock. Racing with a wake up means the aborting process is either already woken (removed from the queue) and will wake up the next waiter, or it will remove itself from the queue and the concurrent wake up will apply to the next waiter after it.

Use abort_exclusive_wait() in __wait_event_interruptible_exclusive() and __wait_on_bit_lock() when they were interrupted by other means than a wake up through the queue.

Quoted 2 lines

Imho, this all is right, and this patch should replace lock_page_killable-avoid-lost-wakeups.patch (except for stable tree).

I dropped lock_page_killable-avoid-lost-wakeups.patch a while ago.

So I think we're saying that lock_page_killable-avoid-lost-wakeups.patch actually did fix the bug?

And that "[RFC v7] wait: prevent exclusive waiter starvation" fixes it as well, and in a preferable manner, but not a manner which we consider suitable for -stable? (why?)

And hence that lock_page_killable-avoid-lost-wakeups.patch is the appropriate fix for -stable?

If so, that's a bit unusual, and the -stable maintainers may choose to take the patch which we're putting into 2.6.29.

Quoted 17 lines · Andrew Morton

Quoted 14 lines · On Thu, 29 Jan 2009 05:42:27 +0100 Oleg Nesterov <[email protected]> wrote:

Quoted 12 lines · Johannes Weiner

Add abort_exclusive_wait() which removes the process' wait descriptor from the waitqueue, iff still queued, or wakes up the next waiter otherwise. It does so under the waitqueue lock. Racing with a wake up means the aborting process is either already woken (removed from the queue) and will wake up the next waiter, or it will remove itself from the queue and the concurrent wake up will apply to the next waiter after it.

Use abort_exclusive_wait() in __wait_event_interruptible_exclusive() and __wait_on_bit_lock() when they were interrupted by other means than a wake up through the queue.

Quoted 7 lines

Quoted 2 lines

Imho, this all is right, and this patch should replace lock_page_killable-avoid-lost-wakeups.patch (except for stable tree).

I dropped lock_page_killable-avoid-lost-wakeups.patch a while ago.

So I think we're saying that lock_page_killable-avoid-lost-wakeups.patch actually did fix the bug?

I think yes,

Quoted 3 lines

And that "[RFC v7] wait: prevent exclusive waiter starvation" fixes it as well, and in a preferable manner, but not a manner which we consider suitable for -stable? (why?)

I meant that lock_page_killable-avoid-lost-wakeups.patch is much simpler, and thus it looks more "safe" for -stable.

But it is not optimal, and Johannes's patch is also more generic, it fixes wait_event_interruptible_exclusive() as well.

Quoted 3 lines

And hence that lock_page_killable-avoid-lost-wakeups.patch is the appropriate fix for -stable?

Quoted 2 lines

If so, that's a bit unusual, and the -stable maintainers may choose to take the patch which we're putting into 2.6.29.

Well, I don't know ;)

But Johannes's looks good to me, if you already dropped the old patch, then I think this one can go into -stable after some testing. Hopefully maintainers can review it.

Quoted 21 lines · On Thu, 29 Jan 2009 09:31:08 +0100 Oleg Nesterov <[email protected]> wrote:

Quoted 20 lines · Andrew Morton

Quoted 16 lines · On Thu, 29 Jan 2009 05:42:27 +0100 Oleg Nesterov <[email protected]> wrote:

Quoted 9 lines · Johannes Weiner

Add abort_exclusive_wait() which removes the process' wait descriptor from the waitqueue, iff still queued, or wakes up the next waiter otherwise. It does so under the waitqueue lock. Racing with a wake up means the aborting process is either already woken (removed from the queue) and will wake up the next waiter, or it will remove itself from the queue and the concurrent wake up will apply to the next waiter after it.

Quoted 3 lines

Use abort_exclusive_wait() in __wait_event_interruptible_exclusive() and __wait_on_bit_lock() when they were interrupted by other means than a wake up through the queue.

Imho, this all is right, and this patch should replace lock_page_killable-avoid-lost-wakeups.patch (except for stable tree).

Quoted 7 lines

Quoted 4 lines

I dropped lock_page_killable-avoid-lost-wakeups.patch a while ago.

So I think we're saying that lock_page_killable-avoid-lost-wakeups.patch actually did fix the bug?

I think yes,

Quoted 5 lines

Quoted 5 lines

Quoted 2 lines

So I think we're saying that lock_page_killable-avoid-lost-wakeups.patch actually did fix the bug?

I think yes,

Our test case that was able to reliably trigger the bug was fixed by lock_page_killable-avoid-lost-wakeups.patch.

I'll ask them to test v7 as well. The run takes about a day, so confirmation will take a bit.