Skip to contentSkip to conversation

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

PATCH Applied Omar Sandoval 6 participants 8 messages Nov 30, 2017 – Dec 6, 2017 Scheduler

lore
Share & tools
lore
#0 lore raw

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:

kernel/sched/wait.c +1 -1
index 98feab7933c7..929ecb7d6b78 100644
@@ -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.

#1 lore raw
Quoted 10 lines · Omar Sandoval

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

Reviewed-by
#7 lore raw
In reply to Omar Sandoval

kernel/sched/wait.c void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq · line 33

Quoted 13 lines · Omar Sandoval
kernel/sched/wait.c +1 -1
index 98feab7933c7..929ecb7d6b78 100644
@@ -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 lore raw

PATCH 1/1 sched/wait: fix add_wait_queue() behavior change

In reply to Linus Torvalds

From: Omar Sandoval <[email protected]>

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.

---
Since Ingo hasn't replied, here's a proper patch.

 kernel/sched/wait.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/wait.c +1 -1
index 98feab7933c7..929ecb7d6b78 100644
@@ -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);
Signature · 1 line
2.15.1
Reviewed-by on v1 1/1
#3 lore raw

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

Quoted 10 lines · Omar Sandoval

From: Omar Sandoval <[email protected]>

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.

Quoted 1 line
Signature · 1 line
Jens Axboe
#6 lore raw
In reply to Linus Torvalds
Quoted 12 lines · Linus Torvalds
Quoted 10 lines · Omar Sandoval

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.

Quoted 3 lines

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

Applied
#4 lore raw

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

In reply to Jens Axboe
Quoted 15 lines · Jens Axboe
Quoted 10 lines · Omar Sandoval

From: Omar Sandoval <[email protected]>

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.

Quoted 6 lines

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

Quoted 1 line

Thanks!

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

Thanks,

Ingo

#5 lore raw

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

In reply to Omar Sandoval
sched/wait: Fix add_wait_queue() behavioral change
Commit-ID:  c6b9d9a33029014446bd9ed84c1688f6d3d4eab9
Gitweb:     https://git.kernel.org/tip/c6b9d9a33029014446bd9ed84c1688f6d3d4eab9
Author:     Omar Sandoval <[email protected]>
AuthorDate: Tue, 5 Dec 2017 23:15:31 -0800
Committer:  Ingo Molnar <[email protected]>
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.

---
 kernel/sched/wait.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/wait.c +1 -1
index 98feab7..929ecb7 100644
@@ -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);