From patchwork Thu Jul 7 15:50:24 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lorenzo Pieralisi X-Patchwork-Id: 953412 Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) by demeter2.kernel.org (8.14.4/8.14.4) with ESMTP id p67G1UjC024663 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Thu, 7 Jul 2011 16:01:51 GMT Received: from canuck.infradead.org ([2001:4978:20e::1]) by merlin.infradead.org with esmtps (Exim 4.76 #1 (Red Hat Linux)) id 1Qeqyv-00026U-SO; Thu, 07 Jul 2011 15:59:15 +0000 Received: from localhost ([127.0.0.1] helo=canuck.infradead.org) by canuck.infradead.org with esmtp (Exim 4.76 #1 (Red Hat Linux)) id 1QeqvE-00062u-C0; Thu, 07 Jul 2011 15:55:24 +0000 Received: from service88.mimecast.com ([195.130.217.12]) by canuck.infradead.org with smtp (Exim 4.76 #1 (Red Hat Linux)) id 1Qequ3-0005hQ-MH for linux-arm-kernel@lists.infradead.org; Thu, 07 Jul 2011 15:54:14 +0000 Received: from cam-owa2.Emea.Arm.com (fw-tnat.cambridge.arm.com [217.140.96.21]) by service87.mimecast.com; Thu, 07 Jul 2011 16:52:02 +0100 Received: from e102568-lin.cambridge.arm.com ([10.1.255.212]) by cam-owa2.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Thu, 7 Jul 2011 16:50:52 +0100 From: Lorenzo Pieralisi To: linux-arm-kernel@lists.infradead.org Subject: [RFC PATCH 11/17] ARM: kernel: add support for Lamport's bakery locks Date: Thu, 7 Jul 2011 16:50:24 +0100 Message-Id: <1310053830-23779-12-git-send-email-lorenzo.pieralisi@arm.com> X-Mailer: git-send-email 1.7.4.4 In-Reply-To: <1310053830-23779-1-git-send-email-lorenzo.pieralisi@arm.com> References: <1310053830-23779-1-git-send-email-lorenzo.pieralisi@arm.com> X-OriginalArrivalTime: 07 Jul 2011 15:50:52.0686 (UTC) FILETIME=[A68102E0:01CC3CBD] X-MC-Unique: 111070716520222401 X-CRM114-Version: 20090807-BlameThorstenAndJenny ( TRE 0.7.6 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20110707_115413_189283_35693C48 X-CRM114-Status: GOOD ( 24.57 ) X-Spam-Score: -0.7 (/) X-Spam-Report: SpamAssassin version 3.3.1 on canuck.infradead.org summary: Content analysis details: (-0.7 points) pts rule name description ---- ---------------------- -------------------------------------------------- -0.7 RCVD_IN_DNSWL_LOW RBL: Sender listed at http://www.dnswl.org/, low trust [195.130.217.12 listed in list.dnswl.org] Cc: Kevin Hilman , Lorenzo Pieralisi , Russell King , Catalin Marinas , Amit Kucheria , Frank Hofmann , Magnus Damm , Santosh Shilimkar , Amit Kachhap , Colin Cross , Linaro Dev X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: linux-arm-kernel-bounces@lists.infradead.org Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.6 (demeter2.kernel.org [140.211.167.43]); Thu, 07 Jul 2011 16:01:51 +0000 (UTC) NOTE: This toy locking algorithm is there waiting for a warm-boot protocol to be defined for ARM SMP platforms. It is there to prevent races that will never show up in real platforms (ie multiple CPUs coming out of low-power at once from cluster shutdown with no HW/SW control so that they might try to renable shared resources like SCU concurrently). When a warm-boot protocol is defined this patch can be and must be simply ignored; it is provided for completeness. The current implementation of spinlocks on ARM relies on ldrex/strex which are only functional if and only if the D$ is looked-up and the CPU is within the coherency domain. When a CPU has to be powered down, it has to turn off D$ look-up to clean and invalidate L1 dirty lines, and on an SMP system it must be taken out of the coherency domain it belongs to. This means that after the point of no return on power down (cache look-up disabled and SMP bit cleared) ldrex/strex cacheable spinlocks become unusable. Normal non-cacheable memory based ldrex/strex require a global monitor which is not available in all HW configurations. In order to ensure atomicity of complex operations like cleaning/invalidating/disabling L2 and reset the SCU, this patch adds the Lamport's bakery algorithm, which does not rely on any low-level atomic operation, to the Linux kernel. Unless restrictions are put in place in HW, processors can be powered down and powered up at random times (e.g IRQ), which means that the ordering is not really controlled by SW, so lock coordination is required to make the code generic. Memory allocated to LB spinlocks must be strongly ordered and the algorithm relies on strongly and coherent writes ordering among processors to guarantee atomicity. It is slow and it must be avoided (see NOTE); it is not meant to provide a definitive solution. Tested on dual-core A9 with processors being powered-down and up according to CPU idle workloads. Signed-off-by: Lorenzo Pieralisi --- arch/arm/include/asm/lb_lock.h | 34 ++++++++++++++++ arch/arm/kernel/lb_lock.c | 85 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 119 insertions(+), 0 deletions(-) create mode 100644 arch/arm/include/asm/lb_lock.h create mode 100644 arch/arm/kernel/lb_lock.c diff --git a/arch/arm/include/asm/lb_lock.h b/arch/arm/include/asm/lb_lock.h new file mode 100644 index 0000000..2ed722c --- /dev/null +++ b/arch/arm/include/asm/lb_lock.h @@ -0,0 +1,34 @@ +/* + * Copyright (C) 2008-2011 ARM Limited + * + * Author(s): Jon Callan, Lorenzo Pieralisi + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + */ + +#ifndef __ASM_ARM_LB_LOCK_H +#define __ASM_ARM_LB_LOCK_H + +/* + * Lamport's Bakery algorithm for spinlock handling + * + * Note that the algorithm requires the bakery struct + * to be in Strongly-Ordered memory. + */ + +/* + * Bakery structure - declare/allocate one of these for each lock. + * A pointer to this struct is passed to the lock/unlock functions. + */ +struct bakery { + unsigned int number[CONFIG_NR_CPUS]; + char entering[CONFIG_NR_CPUS]; +}; + +extern void initialize_spinlock(struct bakery *bakery); +extern void get_spinlock(unsigned cpuid, struct bakery *bakery); +extern void release_spinlock(unsigned cpuid, struct bakery *bakery); +#endif diff --git a/arch/arm/kernel/lb_lock.c b/arch/arm/kernel/lb_lock.c new file mode 100644 index 0000000..199e79e --- /dev/null +++ b/arch/arm/kernel/lb_lock.c @@ -0,0 +1,85 @@ +/* + * Copyright (C) 2008-2011 ARM Limited + * + * Author(s): Jon Callan, Lorenzo Pieralisi + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * Lamport's Bakery algorithm for spinlock handling + * + * Note that the algorithm requires the bakery struct to be in + * Strongly-Ordered memory. + */ + +#include +#include +#include +#include + +/* + * Initialize a bakery - only required if the bakery is + * on the stack or heap, as static data is zeroed anyway. + */ +void initialize_spinlock(struct bakery *bakery) +{ + memset(bakery, 0, sizeof(struct bakery)); +} + +/* + * Claim a bakery lock. Function does not return until + * lock has been obtained. + */ +void notrace get_spinlock(unsigned cpuid, struct bakery *bakery) +{ + unsigned i, my_full_number, his_full_number, max = 0; + + /* Get a ticket */ + __raw_writeb(1, bakery->entering + cpuid); + /* + * The order of writes is paramount to the algorithm + * dsb() ensures the write happens in order here + */ + dsb(); + for (i = 0; i < CONFIG_NR_CPUS; ++i) { + if (__raw_readl(bakery->number + i) > max) + max = __raw_readl(bakery->number + i); + } + ++max; + /* + * The order of writes is paramount to the algorithm + * dsb() ensures the write happens in order here + */ + __raw_writel(max, bakery->number + cpuid); + dsb(); + __raw_writeb(0, bakery->entering + cpuid); + + /* Wait for our turn */ + my_full_number = (max << 8) + cpuid; + for (i = 0; i < CONFIG_NR_CPUS; ++i) { + while (__raw_readb(bakery->entering + i)) + ; + /* + * Wait since another CPU might be taking our + * same ticket number and have higher priority + */ + do { + his_full_number = __raw_readl(bakery->number + i); + if (his_full_number) + his_full_number = + (his_full_number << 8) + i; + + } while (his_full_number && (his_full_number < my_full_number)); + } + dsb(); +} + +/* + * Release a bakery lock. + */ +void release_spinlock(unsigned cpuid, struct bakery *bakery) +{ + dsb(); + __raw_writel(0, bakery->number + cpuid); +}