[PATCH 0/1] x86, ticketlock: spin_unlock_wait() can livelock

[PATCH 0/1] x86, ticketlock: spin_unlock_wait() can livelock

[Oleg Nesterov]

Please review, I'm afraid I could miss something.

OTOH, this almost looks like a bug to me. And in fact I have a bug
report which looks as if spin_unlock_wait() actually spins "forever"
until the system panics, although most probably the are other problems
in kernel/sched which lead to rq->lock contention.

Do we need a barrier() in arch_spin_unlock_wait() ? I guess no, and
the current code doesn't have it.

Perhaps it should use __ticket_lock_spinning() like arch_spin_lock() ?

And probably we should add the lockdep annotations.

Oleg.

[PATCH 1/1] x86, ticketlock: spin_unlock_wait() can livelock

[Oleg Nesterov]

arch_spin_unlock_wait() looks very suboptimal, to the point I think
this is just wrong and can lead to livelock: if the lock is heavily
contended we can never see head == tail.

But we do not need to wait for arch_spin_is_locked() == F. If it is
locked we only need to wait until the current owner drops this lock.
So we could simply spin until old_head != lock->tickets.head in this
case, but .head can overflow and thus we can't check "unlocked" only
once before the main loop.

Also, the "unlocked" check can ignore TICKET_SLOWPATH_FLAG bit.

Signed-off-by: Oleg Nesterov <oleg@redhat.com>
---
 arch/x86/include/asm/spinlock.h |   14 +++++++++++++-
 1 files changed, 13 insertions(+), 1 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 9295016..a4efe47 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -183,8 +183,20 @@ static __always_inline void arch_spin_lock_flags(arch_spinlock_t *lock,
 
 static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)
 {
-	while (arch_spin_is_locked(lock))
+	__ticket_t head = ACCESS_ONCE(lock->tickets.head);
+
+	for (;;) {
+		struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
+		/*
+		 * We need to check "unlocked" in a loop, tmp.head == head
+		 * can be false positive because of overflow.
+		 */
+		if (tmp.head == (tmp.tail & ~TICKET_SLOWPATH_FLAG) ||
+		    tmp.head != head)
+			break;
+
 		cpu_relax();
+	}
 }
 
 /*
-- 
1.5.5.1

Re: [PATCH 1/1] x86, ticketlock: spin_unlock_wait() can livelock

[Linus Torvalds]

On Mon, Dec 1, 2014 at 1:34 PM, Oleg Nesterov <oleg@redhat.com> wrote:
>
> But we do not need to wait for arch_spin_is_locked() == F. If it is
> locked we only need to wait until the current owner drops this lock.
> So we could simply spin until old_head != lock->tickets.head in this
> case, but .head can overflow and thus we can't check "unlocked" only
> once before the main loop.

Ack. Looks like a good idea. Can you point to the report that you
think this might be the cause of?

                    Linus

Re: [PATCH 1/1] x86, ticketlock: spin_unlock_wait() can livelock

[Oleg Nesterov]

On 12/01, Linus Torvalds wrote:
>
> Can you point to the report that you
> think this might be the cause of?

Please look at https://bugzilla.redhat.com/show_bug.cgi?id=1128995

but let me repeat, so far this is just my speculation. Plus this is
the old rhel6 kernel.

Oleg.

Re: [PATCH 1/1] x86, ticketlock: spin_unlock_wait() can livelock

[Linus Torvalds]

On Mon, Dec 1, 2014 at 2:09 PM, Oleg Nesterov <oleg@redhat.com> wrote:
>
> Please look at https://bugzilla.redhat.com/show_bug.cgi?id=1128995

Heh. That's a RH-only bugzilla, I'm not authorized to see it.

              Linus

[tip:core/locking] x86/ticketlock: Fix spin_unlock_wait() livelock

[tip-bot for Oleg Nesterov]

Commit-ID:  78bff1c8684fb94f1ae7283688f90188b53fc433
Gitweb:     http://git.kernel.org/tip/78bff1c8684fb94f1ae7283688f90188b53fc433
Author:     Oleg Nesterov <oleg@redhat.com>
AuthorDate: Mon, 1 Dec 2014 22:34:17 +0100
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Mon, 8 Dec 2014 11:36:44 +0100

x86/ticketlock: Fix spin_unlock_wait() livelock

arch_spin_unlock_wait() looks very suboptimal, to the point I
think this is just wrong and can lead to livelock: if the lock
is heavily contended we can never see head == tail.

But we do not need to wait for arch_spin_is_locked() == F. If it
is locked we only need to wait until the current owner drops
this lock. So we could simply spin until old_head !=
lock->tickets.head in this case, but .head can overflow and thus
we can't check "unlocked" only once before the main loop.

Also, the "unlocked" check can ignore TICKET_SLOWPATH_FLAG bit.

Signed-off-by: Oleg Nesterov <oleg@redhat.com>
Acked-by: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Jeremy Fitzhardinge <jeremy@goop.org>
Cc: Paul E.McKenney <paulmck@linux.vnet.ibm.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Waiman Long <Waiman.Long@hp.com>
Link: http://lkml.kernel.org/r/20141201213417.GA5842@redhat.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 arch/x86/include/asm/spinlock.h | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index bf156de..abc34e9 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -184,8 +184,20 @@ static __always_inline void arch_spin_lock_flags(arch_spinlock_t *lock,
 
 static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)
 {
-	while (arch_spin_is_locked(lock))
+	__ticket_t head = ACCESS_ONCE(lock->tickets.head);
+
+	for (;;) {
+		struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
+		/*
+		 * We need to check "unlocked" in a loop, tmp.head == head
+		 * can be false positive because of overflow.
+		 */
+		if (tmp.head == (tmp.tail & ~TICKET_SLOWPATH_FLAG) ||
+		    tmp.head != head)
+			break;
+
 		cpu_relax();
+	}
 }
 
 /*