| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <8a788f3fbf2ad1316e462bf5aae623bab9d38319.1314922370.git.jeremy.fitzhardinge@citrix.com>
Date: Thu, 1 Sep 2011 17:54:59 -0700
From: Jeremy Fitzhardinge <jeremy@...p.org>
To: "H. Peter Anvin" <hpa@...or.com>
Cc: Linus Torvalds <torvalds@...ux-foundation.org>,
Peter Zijlstra <peterz@...radead.org>,
Ingo Molnar <mingo@...e.hu>,
the arch/x86 maintainers <x86@...nel.org>,
Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
Nick Piggin <npiggin@...nel.dk>, Avi Kivity <avi@...hat.com>,
Marcelo Tosatti <mtosatti@...hat.com>,
KVM <kvm@...r.kernel.org>, Andi Kleen <andi@...stfloor.org>,
Xen Devel <xen-devel@...ts.xensource.com>,
Jeremy Fitzhardinge <jeremy.fitzhardinge@...rix.com>
Subject: [PATCH 06/13] x86/ticketlock: add slowpath logic
From: Jeremy Fitzhardinge <jeremy.fitzhardinge@...rix.com>
Maintain a flag in both LSBs of the ticket lock which indicates whether
anyone is in the lock slowpath and may need kicking when the current
holder unlocks. The flags are set when the first locker enters
the slowpath, and cleared when unlocking to an empty queue.
In the specific implementation of lock_spinning(), make sure to set
the slowpath flags on the lock just before blocking. We must do
this before the last-chance pickup test to prevent a deadlock
with the unlocker:
Unlocker Locker
test for lock pickup
-> fail
test slowpath + unlock
-> false
set slowpath flags
block
Whereas this works in any ordering:
Unlocker Locker
set slowpath flags
test for lock pickup
-> fail
block
test slowpath + unlock
-> true, kick
Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@...rix.com>
---
arch/x86/include/asm/spinlock.h | 41 +++++++++++++++++++++++++++++---
arch/x86/include/asm/spinlock_types.h | 2 +
arch/x86/kernel/paravirt-spinlocks.c | 37 +++++++++++++++++++++++++++++
arch/x86/xen/spinlock.c | 4 +++
4 files changed, 80 insertions(+), 4 deletions(-)
diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 6028b01..2135a48 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -41,7 +41,38 @@
/* How long a lock should spin before we consider blocking */
#define SPIN_THRESHOLD (1 << 11)
-#ifndef CONFIG_PARAVIRT_SPINLOCKS
+/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as
+ * well leave the prototype always visible. */
+extern void __ticket_unlock_release_slowpath(struct arch_spinlock *lock);
+
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+
+/*
+ * Return true if someone is in the slowpath on this lock. This
+ * should only be used by the current lock-holder.
+ */
+static inline bool __ticket_in_slowpath(struct arch_spinlock *lock)
+{
+ return !!(lock->tickets.tail & TICKET_SLOWPATH_FLAG);
+}
+
+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
+{
+ if (sizeof(lock->tickets.tail) == sizeof(u8))
+ asm (LOCK_PREFIX "orb %1, %0"
+ : "+m" (lock->tickets.tail)
+ : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+ else
+ asm (LOCK_PREFIX "orw %1, %0"
+ : "+m" (lock->tickets.tail)
+ : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}
+
+#else /* !CONFIG_PARAVIRT_SPINLOCKS */
+static inline bool __ticket_in_slowpath(struct arch_spinlock *lock)
+{
+ return false;
+}
static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
{
@@ -86,6 +117,7 @@ static __always_inline void arch_spin_lock(struct arch_spinlock *lock)
register struct __raw_tickets inc = { .tail = TICKET_LOCK_INC };
inc = xadd(&lock->tickets, inc);
+ inc.tail &= ~TICKET_SLOWPATH_FLAG;
for (;;) {
unsigned count = SPIN_THRESHOLD;
@@ -135,10 +167,11 @@ static __always_inline void __ticket_unlock_release(arch_spinlock_t *lock)
static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
{
- __ticket_t next = lock->tickets.head + TICKET_LOCK_INC;
- __ticket_unlock_release(lock);
- __ticket_unlock_kick(lock, next);
+ if (unlikely(__ticket_in_slowpath(lock)))
+ __ticket_unlock_release_slowpath(lock);
+ else
+ __ticket_unlock_release(lock);
}
static inline int arch_spin_is_locked(arch_spinlock_t *lock)
diff --git a/arch/x86/include/asm/spinlock_types.h b/arch/x86/include/asm/spinlock_types.h
index 0553c0b..7b383e2 100644
--- a/arch/x86/include/asm/spinlock_types.h
+++ b/arch/x86/include/asm/spinlock_types.h
@@ -9,8 +9,10 @@
#ifdef CONFIG_PARAVIRT_SPINLOCKS
#define __TICKET_LOCK_INC 2
+#define TICKET_SLOWPATH_FLAG ((__ticket_t)1)
#else
#define __TICKET_LOCK_INC 1
+#define TICKET_SLOWPATH_FLAG ((__ticket_t)0)
#endif
#if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))
diff --git a/arch/x86/kernel/paravirt-spinlocks.c b/arch/x86/kernel/paravirt-spinlocks.c
index 4251c1d..21b6986 100644
--- a/arch/x86/kernel/paravirt-spinlocks.c
+++ b/arch/x86/kernel/paravirt-spinlocks.c
@@ -15,3 +15,40 @@ struct pv_lock_ops pv_lock_ops = {
};
EXPORT_SYMBOL(pv_lock_ops);
+
+/*
+ * If we're unlocking and we're leaving the lock uncontended (there's
+ * nobody else waiting for the lock), then we can clear the slowpath
+ * bits. However, we need to be careful about this because someone
+ * may just be entering as we leave, and enter the slowpath.
+ */
+void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+{
+ struct arch_spinlock old, new;
+
+ BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
+
+ old = ACCESS_ONCE(*lock);
+
+ new = old;
+ new.tickets.head += TICKET_LOCK_INC;
+
+ /* Clear the slowpath flag */
+ new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+
+ /*
+ * If there's currently people waiting or someone snuck in
+ * since we read the lock above, then do a normal unlock and
+ * kick. If we managed to unlock with no queued waiters, then
+ * we can clear the slowpath flag.
+ */
+ if (new.tickets.head != new.tickets.tail ||
+ cmpxchg(&lock->head_tail,
+ old.head_tail, new.head_tail) != old.head_tail) {
+ /* still people waiting */
+ __ticket_unlock_release(lock);
+ }
+
+ __ticket_unlock_kick(lock, new.tickets.head);
+}
+EXPORT_SYMBOL(__ticket_unlock_release_slowpath);
diff --git a/arch/x86/xen/spinlock.c b/arch/x86/xen/spinlock.c
index b133865..4c46144 100644
--- a/arch/x86/xen/spinlock.c
+++ b/arch/x86/xen/spinlock.c
@@ -119,6 +119,10 @@ static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
/* Only check lock once pending cleared */
barrier();
+ /* Mark entry to slowpath before doing the pickup test to make
+ sure we don't deadlock with an unlocker. */
+ __ticket_enter_slowpath(lock);
+
/* check again make sure it didn't become free while
we weren't looking */
if (ACCESS_ONCE(lock->tickets.head) == want) {
--
1.7.6
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists