Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754714AbaLHJoy (ORCPT ); Mon, 8 Dec 2014 04:44:54 -0500 Received: from terminus.zytor.com ([198.137.202.10]:36578 "EHLO terminus.zytor.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752864AbaLHJov (ORCPT ); Mon, 8 Dec 2014 04:44:51 -0500 Date: Mon, 8 Dec 2014 01:43:46 -0800 From: tip-bot for Nicholas Mc Guire Message-ID: Cc: mingo@kernel.org, torvalds@linux-foundation.org, hpa@zytor.com, der.herr@hofr.at, c.emde@osadl.org, corbet@lwn.net, tglx@linutronix.de, linux-kernel@vger.kernel.org, akpm@linux-foundation.org, peterz@infradead.org, paulmck@linux.vnet.ibm.com, rostedt@goodmis.org Reply-To: rostedt@goodmis.org, paulmck@linux.vnet.ibm.com, peterz@infradead.org, akpm@linux-foundation.org, tglx@linutronix.de, linux-kernel@vger.kernel.org, corbet@lwn.net, c.emde@osadl.org, der.herr@hofr.at, hpa@zytor.com, torvalds@linux-foundation.org, mingo@kernel.org In-Reply-To: <20141208083326.GA29895@opentech.at> References: <20141208083326.GA29895@opentech.at> To: linux-tip-commits@vger.kernel.org Subject: [tip:core/locking] locking/lglocks: Add documentation of current lglocks implementation Git-Commit-ID: 9fd7fc34cfcaf9f6c932ee1710cce83da3b7bd59 X-Mailer: tip-git-log-daemon Robot-ID: Robot-Unsubscribe: Contact to get blacklisted from these emails MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8 Content-Disposition: inline Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Commit-ID: 9fd7fc34cfcaf9f6c932ee1710cce83da3b7bd59 Gitweb: http://git.kernel.org/tip/9fd7fc34cfcaf9f6c932ee1710cce83da3b7bd59 Author: Nicholas Mc Guire AuthorDate: Mon, 8 Dec 2014 09:33:26 +0100 Committer: Ingo Molnar CommitDate: Mon, 8 Dec 2014 09:55:00 +0100 locking/lglocks: Add documentation of current lglocks implementation Local/global locks are currently not documented anywhere other than in an somewhat out-of-date LWN article - this is an attempt to document the current state of lglocks. This patch is against linux-next 3.18.0-rc6 Signed-off-by: Nicholas Mc Guire Cc: Paul E. McKenney Cc: Carsten Emde Cc: Steven Rostedt Cc: Jonathan Corbet Cc: Linus Torvalds Cc: Andrew Morton Cc: Peter Zijlstra Link: http://lkml.kernel.org/r/20141208083326.GA29895@opentech.at Signed-off-by: Ingo Molnar --- Documentation/locking/lglock.txt | 166 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 166 insertions(+) diff --git a/Documentation/locking/lglock.txt b/Documentation/locking/lglock.txt new file mode 100644 index 0000000..a6971e3 --- /dev/null +++ b/Documentation/locking/lglock.txt @@ -0,0 +1,166 @@ +lglock - local/global locks for mostly local access patterns +------------------------------------------------------------ + +Origin: Nick Piggin's VFS scalability series introduced during + 2.6.35++ [1] [2] +Location: kernel/locking/lglock.c + include/linux/lglock.h +Users: currently only the VFS and stop_machine related code + +Design Goal: +------------ + +Improve scalability of globally used large data sets that are +distributed over all CPUs as per_cpu elements. + +To manage global data structures that are partitioned over all CPUs +as per_cpu elements but can be mostly handled by CPU local actions +lglock will be used where the majority of accesses are cpu local +reading and occasional cpu local writing with very infrequent +global write access. + + +* deal with things locally whenever possible + - very fast access to the local per_cpu data + - reasonably fast access to specific per_cpu data on a different + CPU +* while making global action possible when needed + - by expensive access to all CPUs locks - effectively + resulting in a globally visible critical section. + +Design: +------- + +Basically it is an array of per_cpu spinlocks with the +lg_local_lock/unlock accessing the local CPUs lock object and the +lg_local_lock_cpu/unlock_cpu accessing a remote CPUs lock object +the lg_local_lock has to disable preemption as migration protection so +that the reference to the local CPUs lock does not go out of scope. +Due to the lg_local_lock/unlock only touching cpu-local resources it +is fast. Taking the local lock on a different CPU will be more +expensive but still relatively cheap. + +One can relax the migration constraints by acquiring the current +CPUs lock with lg_local_lock_cpu, remember the cpu, and release that +lock at the end of the critical section even if migrated. This should +give most of the performance benefits without inhibiting migration +though needs careful considerations for nesting of lglocks and +consideration of deadlocks with lg_global_lock. + +The lg_global_lock/unlock locks all underlying spinlocks of all +possible CPUs (including those off-line). The preemption disable/enable +are needed in the non-RT kernels to prevent deadlocks like: + + on cpu 1 + + task A task B + lg_global_lock + got cpu 0 lock + <<<< preempt <<<< + lg_local_lock_cpu for cpu 0 + spin on cpu 0 lock + +On -RT this deadlock scenario is resolved by the arch_spin_locks in the +lglocks being replaced by rt_mutexes which resolve the above deadlock +by boosting the lock-holder. + + +Implementation: +--------------- + +The initial lglock implementation from Nick Piggin used some complex +macros to generate the lglock/brlock in lglock.h - they were later +turned into a set of functions by Andi Kleen [7]. The change to functions +was motivated by the presence of multiple lock users and also by them +being easier to maintain than the generating macros. This change to +functions is also the basis to eliminated the restriction of not +being initializeable in kernel modules (the remaining problem is that +locks are not explicitly initialized - see lockdep-design.txt) + +Declaration and initialization: +------------------------------- + + #include + + DEFINE_LGLOCK(name) + or: + DEFINE_STATIC_LGLOCK(name); + + lg_lock_init(&name, "lockdep_name_string"); + + on UP this is mapped to DEFINE_SPINLOCK(name) in both cases, note + also that as of 3.18-rc6 all declaration in use are of the _STATIC_ + variant (and it seems that the non-static was never in use). + lg_lock_init is initializing the lockdep map only. + +Usage: +------ + +From the locking semantics it is a spinlock. It could be called a +locality aware spinlock. lg_local_* behaves like a per_cpu +spinlock and lg_global_* like a global spinlock. +No surprises in the API. + + lg_local_lock(*lglock); + access to protected per_cpu object on this CPU + lg_local_unlock(*lglock); + + lg_local_lock_cpu(*lglock, cpu); + access to protected per_cpu object on other CPU cpu + lg_local_unlock_cpu(*lglock, cpu); + + lg_global_lock(*lglock); + access all protected per_cpu objects on all CPUs + lg_global_unlock(*lglock); + + There are no _trylock variants of the lglocks. + +Note that the lg_global_lock/unlock has to iterate over all possible +CPUs rather than the actually present CPUs or a CPU could go off-line +with a held lock [4] and that makes it very expensive. A discussion on +these issues can be found at [5] + +Constraints: +------------ + + * currently the declaration of lglocks in kernel modules is not + possible, though this should be doable with little change. + * lglocks are not recursive. + * suitable for code that can do most operations on the CPU local + data and will very rarely need the global lock + * lg_global_lock/unlock is *very* expensive and does not scale + * on UP systems all lg_* primitives are simply spinlocks + * in PREEMPT_RT the spinlock becomes an rt-mutex and can sleep but + does not change the tasks state while sleeping [6]. + * in PREEMPT_RT the preempt_disable/enable in lg_local_lock/unlock + is downgraded to a migrate_disable/enable, the other + preempt_disable/enable are downgraded to barriers [6]. + The deadlock noted for non-RT above is resolved due to rt_mutexes + boosting the lock-holder in this case which arch_spin_locks do + not do. + +lglocks were designed for very specific problems in the VFS and probably +only are the right answer in these corner cases. Any new user that looks +at lglocks probably wants to look at the seqlock and RCU alternatives as +her first choice. There are also efforts to resolve the RCU issues that +currently prevent using RCU in place of view remaining lglocks. + +Note on brlock history: +----------------------- + +The 'Big Reader' read-write spinlocks were originally introduced by +Ingo Molnar in 2000 (2.4/2.5 kernel series) and removed in 2003. They +later were introduced by the VFS scalability patch set in 2.6 series +again as the "big reader lock" brlock [2] variant of lglock which has +been replaced by seqlock primitives or by RCU based primitives in the +3.13 kernel series as was suggested in [3] in 2003. The brlock was +entirely removed in the 3.13 kernel series. + +Link: 1 http://lkml.org/lkml/2010/8/2/81 +Link: 2 http://lwn.net/Articles/401738/ +Link: 3 http://lkml.org/lkml/2003/3/9/205 +Link: 4 https://lkml.org/lkml/2011/8/24/185 +Link: 5 http://lkml.org/lkml/2011/12/18/189 +Link: 6 https://www.kernel.org/pub/linux/kernel/projects/rt/ + patch series - lglocks-rt.patch.patch +Link: 7 http://lkml.org/lkml/2012/3/5/26 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/