| Message ID | 20130122073315.13822.27093.stgit@srivatsabhat.in.ibm.com (mailing list archive) |
|---|---|
| State | Not Applicable |
| Headers | show |
On Tue, 22 Jan 2013 13:03:22 +0530 "Srivatsa S. Bhat" <srivatsa.bhat@linux.vnet.ibm.com> wrote: > A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer > locks can also lead to too many deadlock possibilities which can make it very > hard/impossible to use. This is explained in the example below, which helps > justify the need for a different algorithm to implement flexible Per-CPU > Reader-Writer locks. > > We can use global rwlocks as shown below safely, without fear of deadlocks: > > Readers: > > CPU 0 CPU 1 > ------ ------ > > 1. spin_lock(&random_lock); read_lock(&my_rwlock); > > > 2. read_lock(&my_rwlock); spin_lock(&random_lock); > > > Writer: > > CPU 2: > ------ > > write_lock(&my_rwlock); > > > We can observe that there is no possibility of deadlocks or circular locking > dependencies here. Its perfectly safe. > > Now consider a blind/straight-forward conversion of global rwlocks to per-CPU > rwlocks like this: > > The reader locks its own per-CPU rwlock for read, and proceeds. > > Something like: read_lock(per-cpu rwlock of this cpu); > > The writer acquires all per-CPU rwlocks for write and only then proceeds. > > Something like: > > for_each_online_cpu(cpu) > write_lock(per-cpu rwlock of 'cpu'); > > > Now let's say that for performance reasons, the above scenario (which was > perfectly safe when using global rwlocks) was converted to use per-CPU rwlocks. > > > CPU 0 CPU 1 > ------ ------ > > 1. spin_lock(&random_lock); read_lock(my_rwlock of CPU 1); > > > 2. read_lock(my_rwlock of CPU 0); spin_lock(&random_lock); > > > Writer: > > CPU 2: > ------ > > for_each_online_cpu(cpu) > write_lock(my_rwlock of 'cpu'); > > > Consider what happens if the writer begins his operation in between steps 1 > and 2 at the reader side. It becomes evident that we end up in a (previously > non-existent) deadlock due to a circular locking dependency between the 3 > entities, like this: > > > (holds Waiting for > random_lock) CPU 0 -------------> CPU 2 (holds my_rwlock of CPU 0 > for write) > ^ | > | | > Waiting| | Waiting > for | | for > | V > ------ CPU 1 <------ > > (holds my_rwlock of > CPU 1 for read) > > > > So obviously this "straight-forward" way of implementing percpu rwlocks is > deadlock-prone. One simple measure for (or characteristic of) safe percpu > rwlock should be that if a user replaces global rwlocks with per-CPU rwlocks > (for performance reasons), he shouldn't suddenly end up in numerous deadlock > possibilities which never existed before. The replacement should continue to > remain safe, and perhaps improve the performance. > > Observing the robustness of global rwlocks in providing a fair amount of > deadlock safety, we implement per-CPU rwlocks as nothing but global rwlocks, > as a first step. > > > Cc: David Howells <dhowells@redhat.com> > Signed-off-by: Srivatsa S. Bhat <srivatsa.bhat@linux.vnet.ibm.com> We got rid of brlock years ago, do we have to reintroduce it like this? The problem was that brlock caused starvation.
On Tue, 2013-01-22 at 13:03 +0530, Srivatsa S. Bhat wrote: > A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer > locks can also lead to too many deadlock possibilities which can make it very > hard/impossible to use. This is explained in the example below, which helps > justify the need for a different algorithm to implement flexible Per-CPU > Reader-Writer locks. > > We can use global rwlocks as shown below safely, without fear of deadlocks: > > Readers: > > CPU 0 CPU 1 > ------ ------ > > 1. spin_lock(&random_lock); read_lock(&my_rwlock); > > > 2. read_lock(&my_rwlock); spin_lock(&random_lock); > > > Writer: > > CPU 2: > ------ > > write_lock(&my_rwlock); > I thought global locks are now fair. That is, a reader will block if a writer is waiting. Hence, the above should deadlock on the current rwlock_t types. We need to fix those locations (or better yet, remove all rwlocks ;-) -- Steve
On 01/23/2013 12:15 AM, Stephen Hemminger wrote: > On Tue, 22 Jan 2013 13:03:22 +0530 > "Srivatsa S. Bhat" <srivatsa.bhat@linux.vnet.ibm.com> wrote: > >> A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer >> locks can also lead to too many deadlock possibilities which can make it very >> hard/impossible to use. This is explained in the example below, which helps >> justify the need for a different algorithm to implement flexible Per-CPU >> Reader-Writer locks. >> >> We can use global rwlocks as shown below safely, without fear of deadlocks: >> >> Readers: >> >> CPU 0 CPU 1 >> ------ ------ >> >> 1. spin_lock(&random_lock); read_lock(&my_rwlock); >> >> >> 2. read_lock(&my_rwlock); spin_lock(&random_lock); >> >> >> Writer: >> >> CPU 2: >> ------ >> >> write_lock(&my_rwlock); >> >> >> We can observe that there is no possibility of deadlocks or circular locking >> dependencies here. Its perfectly safe. >> >> Now consider a blind/straight-forward conversion of global rwlocks to per-CPU >> rwlocks like this: >> >> The reader locks its own per-CPU rwlock for read, and proceeds. >> >> Something like: read_lock(per-cpu rwlock of this cpu); >> >> The writer acquires all per-CPU rwlocks for write and only then proceeds. >> >> Something like: >> >> for_each_online_cpu(cpu) >> write_lock(per-cpu rwlock of 'cpu'); >> >> >> Now let's say that for performance reasons, the above scenario (which was >> perfectly safe when using global rwlocks) was converted to use per-CPU rwlocks. >> >> >> CPU 0 CPU 1 >> ------ ------ >> >> 1. spin_lock(&random_lock); read_lock(my_rwlock of CPU 1); >> >> >> 2. read_lock(my_rwlock of CPU 0); spin_lock(&random_lock); >> >> >> Writer: >> >> CPU 2: >> ------ >> >> for_each_online_cpu(cpu) >> write_lock(my_rwlock of 'cpu'); >> >> >> Consider what happens if the writer begins his operation in between steps 1 >> and 2 at the reader side. It becomes evident that we end up in a (previously >> non-existent) deadlock due to a circular locking dependency between the 3 >> entities, like this: >> >> >> (holds Waiting for >> random_lock) CPU 0 -------------> CPU 2 (holds my_rwlock of CPU 0 >> for write) >> ^ | >> | | >> Waiting| | Waiting >> for | | for >> | V >> ------ CPU 1 <------ >> >> (holds my_rwlock of >> CPU 1 for read) >> >> >> >> So obviously this "straight-forward" way of implementing percpu rwlocks is >> deadlock-prone. One simple measure for (or characteristic of) safe percpu >> rwlock should be that if a user replaces global rwlocks with per-CPU rwlocks >> (for performance reasons), he shouldn't suddenly end up in numerous deadlock >> possibilities which never existed before. The replacement should continue to >> remain safe, and perhaps improve the performance. >> >> Observing the robustness of global rwlocks in providing a fair amount of >> deadlock safety, we implement per-CPU rwlocks as nothing but global rwlocks, >> as a first step. >> >> >> Cc: David Howells <dhowells@redhat.com> >> Signed-off-by: Srivatsa S. Bhat <srivatsa.bhat@linux.vnet.ibm.com> > > We got rid of brlock years ago, do we have to reintroduce it like this? > The problem was that brlock caused starvation. > Um? I still see it in include/linux/lglock.h and its users in fs/ directory. BTW, I'm not advocating that everybody start converting their global reader-writer locks to per-cpu rwlocks, because such a conversion probably won't make sense in all scenarios. The thing is, for CPU hotplug in particular, the "preempt_disable() at the reader; stop_machine() at the writer" scheme had some very desirable properties at the reader side (even though people might hate stop_machine() with all their heart ;-)), namely : At the reader side: o No need to hold locks to prevent CPU offline o Extremely fast/optimized updates (the preempt count) o No need for heavy memory barriers o Extremely flexible nesting rules So this made perfect sense at the reader for CPU hotplug, because it is expected that CPU hotplug operations are very infrequent, and it is well-known that quite a few atomic hotplug readers are in very hot paths. The problem was that the stop_machine() at the writer was not only a little too heavy, but also inflicted real-time latencies on the system because it needed cooperation from _all_ CPUs synchronously, to take one CPU down. So the idea is to get rid of stop_machine() without hurting the reader side. And this scheme of per-cpu rwlocks comes close to ensuring that. (You can look at the previous versions of this patchset [links given in cover letter] to see what other schemes we hashed out before coming to this one). The only reason I exposed this as a generic locking scheme was because Tejun pointed out that, complex locking schemes implemented in individual subsystems is not such a good idea. And also this comes at a time when per-cpu rwsemaphores have just been introduced in the kernel and Oleg had ideas about converting the cpu hotplug (sleepable) locking to use them. Regards, Srivatsa S. Bhat
On 01/23/2013 01:02 AM, Steven Rostedt wrote: > On Tue, 2013-01-22 at 13:03 +0530, Srivatsa S. Bhat wrote: >> A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer >> locks can also lead to too many deadlock possibilities which can make it very >> hard/impossible to use. This is explained in the example below, which helps >> justify the need for a different algorithm to implement flexible Per-CPU >> Reader-Writer locks. >> >> We can use global rwlocks as shown below safely, without fear of deadlocks: >> >> Readers: >> >> CPU 0 CPU 1 >> ------ ------ >> >> 1. spin_lock(&random_lock); read_lock(&my_rwlock); >> >> >> 2. read_lock(&my_rwlock); spin_lock(&random_lock); >> >> >> Writer: >> >> CPU 2: >> ------ >> >> write_lock(&my_rwlock); >> > > I thought global locks are now fair. That is, a reader will block if a > writer is waiting. Hence, the above should deadlock on the current > rwlock_t types. > Oh is it? Last I checked, lockdep didn't complain about this ABBA scenario! > We need to fix those locations (or better yet, remove all rwlocks ;-) > :-) The challenge with stop_machine() removal is that the replacement on the reader side must have the (locking) flexibility comparable to preempt_disable(). Otherwise, that solution most likely won't be viable because we'll hit way too many locking problems and go crazy by the time we convert them over..(if we can, that is!) Regards, Srivatsa S. Bhat
On Wed, 2013-01-23 at 01:28 +0530, Srivatsa S. Bhat wrote: > > I thought global locks are now fair. That is, a reader will block if a > > writer is waiting. Hence, the above should deadlock on the current > > rwlock_t types. > > > > Oh is it? Last I checked, lockdep didn't complain about this ABBA scenario! It doesn't and Peter Zijlstra said we need to fix that ;-) It only recently became an issue with the new "fair" locking of rwlocks. -- Steve
On Tue, Jan 22, 2013 at 11:32 AM, Steven Rostedt <rostedt@goodmis.org> wrote: > On Tue, 2013-01-22 at 13:03 +0530, Srivatsa S. Bhat wrote: >> A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer >> locks can also lead to too many deadlock possibilities which can make it very >> hard/impossible to use. This is explained in the example below, which helps >> justify the need for a different algorithm to implement flexible Per-CPU >> Reader-Writer locks. >> >> We can use global rwlocks as shown below safely, without fear of deadlocks: >> >> Readers: >> >> CPU 0 CPU 1 >> ------ ------ >> >> 1. spin_lock(&random_lock); read_lock(&my_rwlock); >> >> >> 2. read_lock(&my_rwlock); spin_lock(&random_lock); >> >> >> Writer: >> >> CPU 2: >> ------ >> >> write_lock(&my_rwlock); >> > > I thought global locks are now fair. That is, a reader will block if a > writer is waiting. Hence, the above should deadlock on the current > rwlock_t types. I believe you are mistaken here. struct rw_semaphore is fair (and blocking), but rwlock_t is unfair. The reason we can't easily make rwlock_t fair is because tasklist_lock currently depends on the rwlock_t unfairness - tasklist_lock readers typically don't disable local interrupts, and tasklist_lock may be acquired again from within an interrupt, which would deadlock if rwlock_t was fair and a writer was queued by the time the interrupt is processed. > We need to fix those locations (or better yet, remove all rwlocks ;-) tasklist_lock is the main remaining user. I'm not sure about removing rwlock_t, but I would like to at least make it fair somehow :)
On 01/23, Michel Lespinasse wrote: > > On Tue, Jan 22, 2013 at 11:32 AM, Steven Rostedt <rostedt@goodmis.org> wrote: > > > > I thought global locks are now fair. That is, a reader will block if a > > writer is waiting. Hence, the above should deadlock on the current > > rwlock_t types. > > I believe you are mistaken here. struct rw_semaphore is fair (and > blocking), but rwlock_t is unfair. The reason we can't easily make > rwlock_t fair is because tasklist_lock currently depends on the > rwlock_t unfairness - tasklist_lock readers typically don't disable > local interrupts, and tasklist_lock may be acquired again from within > an interrupt, which would deadlock if rwlock_t was fair and a writer > was queued by the time the interrupt is processed. Yes. And, iirc, it was even documented somewhere that while rwlock_t is not really nice, it is good to share the locking with interrupts. You do not need to disable irqs. Oleg.
Srivatsa S. Bhat <srivatsa.bhat@linux.vnet.ibm.com> wrote: > We can use global rwlocks as shown below safely, without fear of deadlocks: > > Readers: > > CPU 0 CPU 1 > ------ ------ > > 1. spin_lock(&random_lock); read_lock(&my_rwlock); > > > 2. read_lock(&my_rwlock); spin_lock(&random_lock); The lock order on CPU 0 is unsafe if CPU2 can do: write_lock(&my_rwlock); spin_lock(&random_lock); and on CPU 1 if CPU2 can do: spin_lock(&random_lock); write_lock(&my_rwlock); I presume you were specifically excluding these situations? David
On 02/11/2013 06:11 PM, David Howells wrote: > Srivatsa S. Bhat <srivatsa.bhat@linux.vnet.ibm.com> wrote: > >> We can use global rwlocks as shown below safely, without fear of deadlocks: >> >> Readers: >> >> CPU 0 CPU 1 >> ------ ------ >> >> 1. spin_lock(&random_lock); read_lock(&my_rwlock); >> >> >> 2. read_lock(&my_rwlock); spin_lock(&random_lock); > > The lock order on CPU 0 is unsafe if CPU2 can do: > > write_lock(&my_rwlock); > spin_lock(&random_lock); > > and on CPU 1 if CPU2 can do: > > spin_lock(&random_lock); > write_lock(&my_rwlock); > Right.. > I presume you were specifically excluding these situations? > Yes.. Those cases are simple to find out and fix (by changing the lock ordering). My main problem was with CPU 0 and CPU 1 as shown above.. ... and using a global rwlock helps ease that part out. Regards, Srivatsa S. Bhat
diff --git a/include/linux/percpu-rwlock.h b/include/linux/percpu-rwlock.h new file mode 100644 index 0000000..45620d0 --- /dev/null +++ b/include/linux/percpu-rwlock.h @@ -0,0 +1,49 @@ +/* + * Flexible Per-CPU Reader-Writer Locks + * (with relaxed locking rules and reduced deadlock-possibilities) + * + * Copyright (C) IBM Corporation, 2012-2013 + * Author: Srivatsa S. Bhat <srivatsa.bhat@linux.vnet.ibm.com> + * + * With lots of invaluable suggestions from: + * Oleg Nesterov <oleg@redhat.com> + * Tejun Heo <tj@kernel.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + */ + +#ifndef _LINUX_PERCPU_RWLOCK_H +#define _LINUX_PERCPU_RWLOCK_H + +#include <linux/percpu.h> +#include <linux/lockdep.h> +#include <linux/spinlock.h> + +struct percpu_rwlock { + rwlock_t global_rwlock; +}; + +extern void percpu_read_lock(struct percpu_rwlock *); +extern void percpu_read_unlock(struct percpu_rwlock *); + +extern void percpu_write_lock(struct percpu_rwlock *); +extern void percpu_write_unlock(struct percpu_rwlock *); + +extern int __percpu_init_rwlock(struct percpu_rwlock *, + const char *, struct lock_class_key *); + +#define percpu_init_rwlock(pcpu_rwlock) \ +({ static struct lock_class_key rwlock_key; \ + __percpu_init_rwlock(pcpu_rwlock, #pcpu_rwlock, &rwlock_key); \ +}) + +#endif diff --git a/lib/Kconfig b/lib/Kconfig index 75cdb77..32fb0b9 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -45,6 +45,9 @@ config STMP_DEVICE config PERCPU_RWSEM boolean +config PERCPU_RWLOCK + boolean + config CRC_CCITT tristate "CRC-CCITT functions" help diff --git a/lib/Makefile b/lib/Makefile index 02ed6c0..1854b5e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -41,6 +41,7 @@ obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock_debug.o lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o lib-$(CONFIG_PERCPU_RWSEM) += percpu-rwsem.o +lib-$(CONFIG_PERCPU_RWLOCK) += percpu-rwlock.o CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS)) obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o diff --git a/lib/percpu-rwlock.c b/lib/percpu-rwlock.c new file mode 100644 index 0000000..af0c714 --- /dev/null +++ b/lib/percpu-rwlock.c @@ -0,0 +1,63 @@ +/* + * Flexible Per-CPU Reader-Writer Locks + * (with relaxed locking rules and reduced deadlock-possibilities) + * + * Copyright (C) IBM Corporation, 2012-2013 + * Author: Srivatsa S. Bhat <srivatsa.bhat@linux.vnet.ibm.com> + * + * With lots of invaluable suggestions from: + * Oleg Nesterov <oleg@redhat.com> + * Tejun Heo <tj@kernel.org> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + */ + +#include <linux/spinlock.h> +#include <linux/percpu.h> +#include <linux/lockdep.h> +#include <linux/percpu-rwlock.h> +#include <linux/errno.h> + + +int __percpu_init_rwlock(struct percpu_rwlock *pcpu_rwlock, + const char *name, struct lock_class_key *rwlock_key) +{ + /* ->global_rwlock represents the whole percpu_rwlock for lockdep */ +#ifdef CONFIG_DEBUG_SPINLOCK + __rwlock_init(&pcpu_rwlock->global_rwlock, name, rwlock_key); +#else + pcpu_rwlock->global_rwlock = + __RW_LOCK_UNLOCKED(&pcpu_rwlock->global_rwlock); +#endif + return 0; +} + +void percpu_read_lock(struct percpu_rwlock *pcpu_rwlock) +{ + read_lock(&pcpu_rwlock->global_rwlock); +} + +void percpu_read_unlock(struct percpu_rwlock *pcpu_rwlock) +{ + read_unlock(&pcpu_rwlock->global_rwlock); +} + +void percpu_write_lock(struct percpu_rwlock *pcpu_rwlock) +{ + write_lock(&pcpu_rwlock->global_rwlock); +} + +void percpu_write_unlock(struct percpu_rwlock *pcpu_rwlock) +{ + write_unlock(&pcpu_rwlock->global_rwlock); +} +
A straight-forward (and obvious) algorithm to implement Per-CPU Reader-Writer locks can also lead to too many deadlock possibilities which can make it very hard/impossible to use. This is explained in the example below, which helps justify the need for a different algorithm to implement flexible Per-CPU Reader-Writer locks. We can use global rwlocks as shown below safely, without fear of deadlocks: Readers: CPU 0 CPU 1 ------ ------ 1. spin_lock(&random_lock); read_lock(&my_rwlock); 2. read_lock(&my_rwlock); spin_lock(&random_lock); Writer: CPU 2: ------ write_lock(&my_rwlock); We can observe that there is no possibility of deadlocks or circular locking dependencies here. Its perfectly safe. Now consider a blind/straight-forward conversion of global rwlocks to per-CPU rwlocks like this: The reader locks its own per-CPU rwlock for read, and proceeds. Something like: read_lock(per-cpu rwlock of this cpu); The writer acquires all per-CPU rwlocks for write and only then proceeds. Something like: for_each_online_cpu(cpu) write_lock(per-cpu rwlock of 'cpu'); Now let's say that for performance reasons, the above scenario (which was perfectly safe when using global rwlocks) was converted to use per-CPU rwlocks. CPU 0 CPU 1 ------ ------ 1. spin_lock(&random_lock); read_lock(my_rwlock of CPU 1); 2. read_lock(my_rwlock of CPU 0); spin_lock(&random_lock); Writer: CPU 2: ------ for_each_online_cpu(cpu) write_lock(my_rwlock of 'cpu'); Consider what happens if the writer begins his operation in between steps 1 and 2 at the reader side. It becomes evident that we end up in a (previously non-existent) deadlock due to a circular locking dependency between the 3 entities, like this: (holds Waiting for random_lock) CPU 0 -------------> CPU 2 (holds my_rwlock of CPU 0 for write) ^ | | | Waiting| | Waiting for | | for | V ------ CPU 1 <------ (holds my_rwlock of CPU 1 for read) So obviously this "straight-forward" way of implementing percpu rwlocks is deadlock-prone. One simple measure for (or characteristic of) safe percpu rwlock should be that if a user replaces global rwlocks with per-CPU rwlocks (for performance reasons), he shouldn't suddenly end up in numerous deadlock possibilities which never existed before. The replacement should continue to remain safe, and perhaps improve the performance. Observing the robustness of global rwlocks in providing a fair amount of deadlock safety, we implement per-CPU rwlocks as nothing but global rwlocks, as a first step. Cc: David Howells <dhowells@redhat.com> Signed-off-by: Srivatsa S. Bhat <srivatsa.bhat@linux.vnet.ibm.com> --- include/linux/percpu-rwlock.h | 49 ++++++++++++++++++++++++++++++++ lib/Kconfig | 3 ++ lib/Makefile | 1 + lib/percpu-rwlock.c | 63 +++++++++++++++++++++++++++++++++++++++++ 4 files changed, 116 insertions(+) create mode 100644 include/linux/percpu-rwlock.h create mode 100644 lib/percpu-rwlock.c