add_wait_queue() (unintentional?) behavior change in v4.13

add_wait_queue() (unintentional?) behavior change in v4.13

[Omar Sandoval]

Hi, Ingo,

Commit 50816c48997a ("sched/wait: Standardize internal naming of
wait-queue entries") changed the behavior of add_wait_queue() from
inserting the wait entry at the head of the wait queue to the tail of
the wait queue. This is the relevant hunk:

-void add_wait_queue(wait_queue_head_t *q, wait_queue_entry_t *wait)
+void add_wait_queue(wait_queue_head_t *q, struct wait_queue_entry *wq_entry)
 {
        unsigned long flags;

-       wait->flags &= ~WQ_FLAG_EXCLUSIVE;
+       wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
        spin_lock_irqsave(&q->lock, flags);
-       __add_wait_queue(q, wait);
+       __add_wait_queue_entry_tail(q, wq_entry);
        spin_unlock_irqrestore(&q->lock, flags);
 }
 EXPORT_SYMBOL(add_wait_queue);

Note the change from __add_wait_queue() to
__add_wait_queue_entry_tail(). I'm assuming this was a typo since the
commit message doesn't mention any functional changes. This patch
restores the old behavior:

diff --git a/kernel/sched/wait.c b/kernel/sched/wait.c
index 98feab7933c7..929ecb7d6b78 100644
--- a/kernel/sched/wait.c
+++ b/kernel/sched/wait.c
@@ -27,7 +27,7 @@ void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq
 
 	wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
 	spin_lock_irqsave(&wq_head->lock, flags);
-	__add_wait_queue_entry_tail(wq_head, wq_entry);
+	__add_wait_queue(wq_head, wq_entry);
 	spin_unlock_irqrestore(&wq_head->lock, flags);
 }
 EXPORT_SYMBOL(add_wait_queue);

I didn't go through and audit callers of add_wait_queue(), but from a
quick code read this makes it so that non-exclusive waiters will not be
woken up if they are behind enough exclusive waiters, and I bet that'll
cause some bugs.

Re: add_wait_queue() (unintentional?) behavior change in v4.13

[Linus Torvalds]

On Wed, Nov 29, 2017 at 4:58 PM, Omar Sandoval <osandov@osandov.com> wrote:
>
> Note the change from __add_wait_queue() to
> __add_wait_queue_entry_tail(). I'm assuming this was a typo since the
> commit message doesn't mention any functional changes. This patch
> restores the old behavior:
>   [...]
> I didn't go through and audit callers of add_wait_queue(), but from a
> quick code read this makes it so that non-exclusive waiters will not be
> woken up if they are behind enough exclusive waiters, and I bet that'll
> cause some bugs.

This sounds right to me.

Ingo?

The "add to head of wait-queue" is nasty and causes unfair waiter
behavior, but it does have that exclusive waiter reason going for it.

In the page bit-wait queues, we actually did this change
_intentionally_ a few months ago (see commits

  3510ca20ece0 Minor page waitqueue cleanups
  9c3a815f471a page waitqueue: always add new entries at the end

but there it was intentional: an exclusive waiter on the bit
wait-queues is going to acquire the bit lock, which in turn means that
they'll eventually release the bit lock and then wake up any
subsequent non-exclusive waiters, so the non-exclusive ones _will_ get
woken up eventually (and in a fair order).

Sadly, when it comes to wait-queues in general, we don't have those
kinds of guarantees. An exclusive waiter is going to use the resource,
but there's no fundamental reason to believe that non-exclusive
waiters will be woken up again (although in practice it's probably
very rare that they wouldn't).

                Linus

[PATCH] sched/wait: fix add_wait_queue() behavior change

[Omar Sandoval]

From: Omar Sandoval <osandov@fb.com>

Commit 50816c48997a ("sched/wait: Standardize internal naming of
wait-queue entries") changed the behavior of add_wait_queue() from
inserting the wait entry at the head of the wait queue to the tail of
the wait queue. That commit was a cleanup and didn't mention any
functional changes so it was likely unintentional. This change in
behavior theoretically breaks wait queues which mix exclusive and
non-exclusive waiters, as non-exclusive waiters will not be woken up if
they are queued behind enough exclusive waiters.

Signed-off-by: Omar Sandoval <osandov@fb.com>
---
Since Ingo hasn't replied, here's a proper patch.

 kernel/sched/wait.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/sched/wait.c b/kernel/sched/wait.c
index 98feab7933c7..929ecb7d6b78 100644
--- a/kernel/sched/wait.c
+++ b/kernel/sched/wait.c
@@ -27,7 +27,7 @@ void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq
 
 	wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
 	spin_lock_irqsave(&wq_head->lock, flags);
-	__add_wait_queue_entry_tail(wq_head, wq_entry);
+	__add_wait_queue(wq_head, wq_entry);
 	spin_unlock_irqrestore(&wq_head->lock, flags);
 }
 EXPORT_SYMBOL(add_wait_queue);
-- 
2.15.1

Re: [PATCH] sched/wait: fix add_wait_queue() behavior change

[Jens Axboe]

On 12/06/2017 12:15 AM, Omar Sandoval wrote:
> From: Omar Sandoval <osandov@fb.com>
> 
> Commit 50816c48997a ("sched/wait: Standardize internal naming of
> wait-queue entries") changed the behavior of add_wait_queue() from
> inserting the wait entry at the head of the wait queue to the tail of
> the wait queue. That commit was a cleanup and didn't mention any
> functional changes so it was likely unintentional. This change in
> behavior theoretically breaks wait queues which mix exclusive and
> non-exclusive waiters, as non-exclusive waiters will not be woken up if
> they are queued behind enough exclusive waiters.

Ingo? You've been silent on this issue, which is somewhat odd since
your cosmetic renaming patch introduced this behavioral change.

Omar, should probably turn that into a proper Fixes: line as
well.

> Signed-off-by: Omar Sandoval <osandov@fb.com>

Reviewed-by: Jens Axboe <axboe@kernel.dk>

-- 
Jens Axboe

Re: [PATCH] sched/wait: fix add_wait_queue() behavior change

[Ingo Molnar]

* Jens Axboe <axboe@kernel.dk> wrote:

> On 12/06/2017 12:15 AM, Omar Sandoval wrote:
> > From: Omar Sandoval <osandov@fb.com>
> > 
> > Commit 50816c48997a ("sched/wait: Standardize internal naming of
> > wait-queue entries") changed the behavior of add_wait_queue() from
> > inserting the wait entry at the head of the wait queue to the tail of
> > the wait queue. That commit was a cleanup and didn't mention any
> > functional changes so it was likely unintentional. This change in
> > behavior theoretically breaks wait queues which mix exclusive and
> > non-exclusive waiters, as non-exclusive waiters will not be woken up if
> > they are queued behind enough exclusive waiters.
> 
> Ingo? You've been silent on this issue, which is somewhat odd since
> your cosmetic renaming patch introduced this behavioral change.
> 
> Omar, should probably turn that into a proper Fixes: line as
> well.
> 
> > Signed-off-by: Omar Sandoval <osandov@fb.com>
> 
> Reviewed-by: Jens Axboe <axboe@kernel.dk>

Thanks!

I've applied the fix and will send it to Linus later today.

Thanks,

	Ingo

[tip:sched/core] sched/wait: Fix add_wait_queue() behavioral change

[tip-bot for Omar Sandoval]

Commit-ID:  c6b9d9a33029014446bd9ed84c1688f6d3d4eab9
Gitweb:     https://git.kernel.org/tip/c6b9d9a33029014446bd9ed84c1688f6d3d4eab9
Author:     Omar Sandoval <osandov@fb.com>
AuthorDate: Tue, 5 Dec 2017 23:15:31 -0800
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Wed, 6 Dec 2017 19:30:34 +0100

sched/wait: Fix add_wait_queue() behavioral change

The following cleanup commit:

  50816c48997a ("sched/wait: Standardize internal naming of wait-queue entries")

... unintentionally changed the behavior of add_wait_queue() from
inserting the wait entry at the head of the wait queue to the tail
of the wait queue.

Beyond a negative performance impact this change in behavior
theoretically also breaks wait queues which mix exclusive and
non-exclusive waiters, as non-exclusive waiters will not be
woken up if they are queued behind enough exclusive waiters.

Signed-off-by: Omar Sandoval <osandov@fb.com>
Reviewed-by: Jens Axboe <axboe@kernel.dk>
Acked-by: Peter Zijlstra <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: kernel-team@fb.com
Fixes: ("sched/wait: Standardize internal naming of wait-queue entries")
Link: http://lkml.kernel.org/r/a16c8ccffd39bd08fdaa45a5192294c784b803a7.1512544324.git.osandov@fb.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/sched/wait.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/sched/wait.c b/kernel/sched/wait.c
index 98feab7..929ecb7 100644
--- a/kernel/sched/wait.c
+++ b/kernel/sched/wait.c
@@ -27,7 +27,7 @@ void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq
 
 	wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
 	spin_lock_irqsave(&wq_head->lock, flags);
-	__add_wait_queue_entry_tail(wq_head, wq_entry);
+	__add_wait_queue(wq_head, wq_entry);
 	spin_unlock_irqrestore(&wq_head->lock, flags);
 }
 EXPORT_SYMBOL(add_wait_queue);

Re: add_wait_queue() (unintentional?) behavior change in v4.13

[Ingo Molnar]

* Linus Torvalds <torvalds@linux-foundation.org> wrote:

> On Wed, Nov 29, 2017 at 4:58 PM, Omar Sandoval <osandov@osandov.com> wrote:
> >
> > Note the change from __add_wait_queue() to
> > __add_wait_queue_entry_tail(). I'm assuming this was a typo since the
> > commit message doesn't mention any functional changes. This patch
> > restores the old behavior:
> >   [...]
> > I didn't go through and audit callers of add_wait_queue(), but from a
> > quick code read this makes it so that non-exclusive waiters will not be
> > woken up if they are behind enough exclusive waiters, and I bet that'll
> > cause some bugs.
> 
> This sounds right to me.
> 
> Ingo?

Yeah, it's indeed unintended and it's a bug - I have applied the fix and will get 
it to you ASAP.

Thanks,

	Ingo

Re: add_wait_queue() (unintentional?) behavior change in v4.13

[Fubo Chen]

On Wed, Nov 29, 2017 at 4:58 PM, Omar Sandoval <osandov@osandov.com> wrote:
> diff --git a/kernel/sched/wait.c b/kernel/sched/wait.c
> index 98feab7933c7..929ecb7d6b78 100644
> --- a/kernel/sched/wait.c
> +++ b/kernel/sched/wait.c
> @@ -27,7 +27,7 @@ void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq
>
>         wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
>         spin_lock_irqsave(&wq_head->lock, flags);
> -       __add_wait_queue_entry_tail(wq_head, wq_entry);
> +       __add_wait_queue(wq_head, wq_entry);
>         spin_unlock_irqrestore(&wq_head->lock, flags);
>  }
>  EXPORT_SYMBOL(add_wait_queue);

Reviewed-by: Fubo Chen <fubo.chen@gmail.com>