linux-kernel - [tip:core/locking] x86/smp: Implement proportional backoff for ticket spinlocks

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 13 Feb 2013 04:07:24 -0800
From:	tip-bot for Rik van Riel <riel@...hat.com>
To:	linux-tip-commits@...r.kernel.org
Cc:	linux-kernel@...r.kernel.org, hpa@...or.com, mingo@...nel.org,
	a.p.zijlstra@...llo.nl, torvalds@...ux-foundation.org,
	riel@...hat.com, aquini@...hat.com, akpm@...ux-foundation.org,
	tglx@...utronix.de, walken@...gle.com
Subject: [tip:core/locking] x86/smp:
  Implement proportional backoff for ticket spinlocks

Commit-ID:  4c13d231339a8dc7ca056476fa10d95369080c8c
Gitweb:     http://git.kernel.org/tip/4c13d231339a8dc7ca056476fa10d95369080c8c
Author:     Rik van Riel <riel@...hat.com>
AuthorDate: Wed, 6 Feb 2013 15:04:42 -0500
Committer:  Ingo Molnar <mingo@...nel.org>
CommitDate: Wed, 13 Feb 2013 09:06:29 +0100

x86/smp: Implement proportional backoff for ticket spinlocks

Add simple fixed value proportional backoff for ticket spinlocks.

By pounding on the cacheline with the spin lock less often,
bus traffic is reduced. In cases of a data structure with
embedded spinlock, the lock holder has a better chance of
making progress.

If we are next in line behind the current holder of the
lock, we do a fast spin, so as not to waste any time when
the lock is released.

The number 50 is likely to be wrong for many setups, and
this patch is mostly to illustrate the concept of proportional
backup. The next patch automatically tunes the delay value.

Signed-off-by: Rik van Riel <riel@...hat.com>
Signed-off-by: Michel Lespinasse <walken@...gle.com>
Acked-by: Rafael Aquini <aquini@...hat.com>
Cc: eric.dumazet@...il.com
Cc: lwoodman@...hat.com
Cc: knoel@...hat.com
Cc: chegu_vinod@...com
Cc: raghavendra.kt@...ux.vnet.ibm.com
Cc: Linus Torvalds <torvalds@...ux-foundation.org>
Cc: Andrew Morton <akpm@...ux-foundation.org>
Cc: Peter Zijlstra <a.p.zijlstra@...llo.nl>
Cc: Thomas Gleixner <tglx@...utronix.de>
Link: http://lkml.kernel.org/r/20130206150442.1ffd017c@cuia.bos.redhat.com
Signed-off-by: Ingo Molnar <mingo@...nel.org>
---
 arch/x86/kernel/smp.c | 23 ++++++++++++++++++++---
 1 file changed, 20 insertions(+), 3 deletions(-)

diff --git a/arch/x86/kernel/smp.c b/arch/x86/kernel/smp.c
index 20da354..aa743e9 100644
--- a/arch/x86/kernel/smp.c
+++ b/arch/x86/kernel/smp.c
@@ -117,11 +117,28 @@ static bool smp_no_nmi_ipi = false;
  */
 void ticket_spin_lock_wait(arch_spinlock_t *lock, struct __raw_tickets inc)
 {
+	__ticket_t head = inc.head, ticket = inc.tail;
+	__ticket_t waiters_ahead;
+	unsigned loops;
+
 	for (;;) {
-		cpu_relax();
-		inc.head = ACCESS_ONCE(lock->tickets.head);
+		waiters_ahead = ticket - head - 1;
+		/*
+		 * We are next after the current lock holder. Check often
+		 * to avoid wasting time when the lock is released.
+		 */
+		if (!waiters_ahead) {
+			do {
+				cpu_relax();
+			} while (ACCESS_ONCE(lock->tickets.head) != ticket);
+			break;
+		}
+		loops = 50 * waiters_ahead;
+		while (loops--)
+			cpu_relax();
 
-		if (inc.head == inc.tail)
+		head = ACCESS_ONCE(lock->tickets.head);
+		if (head == ticket)
 			break;
 	}
 }
--
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/