[PATCH -mm 0/3] percpu_rw_semaphore: lockdep + config

[PATCH -mm 0/3] percpu_rw_semaphore: lockdep + config

[Oleg Nesterov]

On 11/11, Oleg Nesterov wrote:
>
> To remind, once/if I am sure you agree with this patch I'll send 2 additional
> and simple patches:
>
> 	1. lockdep annotations
>
> 	2. CONFIG_PERCPU_RWSEM

It turns out, lockdep annotations are not that simple due to internal
locks used by percpu_rw_semaphore. To clarify, it is actually simple
but lockdep_set_novalidate_class() doesn't seem to actually work, and
more importantly, it must not be used according to checkpatch.pl. And
I guess ->lockdep_recursion should not be used too.

However, without some tricks, the output from lockdep (when it finds
the problem) does not look very clear because it blames those internal
locks instead of "the whole" percpu_rw_semaphore.

So this series starts with the small optimization which I was going to
do later. It removes ->writer_mutex and greatly simplifies 2/3.

Oleg.

[PATCH 1/3] percpu_rw_semaphore: kill ->writer_mutex, add ->write_ctr

[Oleg Nesterov]

percpu_rw_semaphore->writer_mutex was only added to simplify the
initial rewrite, the only thing it protects is clear_fast_ctr()
which otherwise could be called by multiple writers. ->rw_sem is
enough to serialize the writers.

Kill this mutex and add "atomic_t write_ctr" instead. The writers
increment/decrement this counter, the readers check it is zero
instead of mutex_is_locked().

Move atomic_add(clear_fast_ctr(), slow_read_ctr) under down_write()
to avoid the race with other writers. This is a bit sub-optimal,
only the first writer needs this and we do not need to exclude the
readers at this stage. But this is simple, we do not want another
internal lock until we add more features.

And this speeds up the write-contended case. Before this patch the
racing writers sleep in synchronize_sched() sequentially, with this
patch multiple synchronize_sched's can "overlap" with each other.
Note: we can do more optimizations, this is only the first step.

Signed-off-by: Oleg Nesterov <oleg@redhat.com>
---
 include/linux/percpu-rwsem.h |    4 ++--
 lib/percpu-rwsem.c           |   34 ++++++++++++++++------------------
 2 files changed, 18 insertions(+), 20 deletions(-)

diff --git a/include/linux/percpu-rwsem.h b/include/linux/percpu-rwsem.h
index 592f0d6..d2146a4 100644
--- a/include/linux/percpu-rwsem.h
+++ b/include/linux/percpu-rwsem.h
@@ -1,14 +1,14 @@
 #ifndef _LINUX_PERCPU_RWSEM_H
 #define _LINUX_PERCPU_RWSEM_H
 
-#include <linux/mutex.h>
+#include <linux/atomic.h>
 #include <linux/rwsem.h>
 #include <linux/percpu.h>
 #include <linux/wait.h>
 
 struct percpu_rw_semaphore {
 	unsigned int __percpu	*fast_read_ctr;
-	struct mutex		writer_mutex;
+	atomic_t		write_ctr;
 	struct rw_semaphore	rw_sem;
 	atomic_t		slow_read_ctr;
 	wait_queue_head_t	write_waitq;
diff --git a/lib/percpu-rwsem.c b/lib/percpu-rwsem.c
index 02bd157..e5a146e 100644
--- a/lib/percpu-rwsem.c
+++ b/lib/percpu-rwsem.c
@@ -1,4 +1,4 @@
-#include <linux/mutex.h>
+#include <linux/atomic.h>
 #include <linux/rwsem.h>
 #include <linux/percpu.h>
 #include <linux/wait.h>
@@ -13,8 +13,8 @@ int percpu_init_rwsem(struct percpu_rw_semaphore *brw)
 	if (unlikely(!brw->fast_read_ctr))
 		return -ENOMEM;
 
-	mutex_init(&brw->writer_mutex);
 	init_rwsem(&brw->rw_sem);
+	atomic_set(&brw->write_ctr, 0);
 	atomic_set(&brw->slow_read_ctr, 0);
 	init_waitqueue_head(&brw->write_waitq);
 	return 0;
@@ -28,7 +28,7 @@ void percpu_free_rwsem(struct percpu_rw_semaphore *brw)
 
 /*
  * This is the fast-path for down_read/up_read, it only needs to ensure
- * there is no pending writer (!mutex_is_locked() check) and inc/dec the
+ * there is no pending writer (atomic_read(write_ctr) == 0) and inc/dec the
  * fast per-cpu counter. The writer uses synchronize_sched() to serialize
  * with the preempt-disabled section below.
  *
@@ -44,7 +44,7 @@ void percpu_free_rwsem(struct percpu_rw_semaphore *brw)
  * If this helper fails the callers rely on the normal rw_semaphore and
  * atomic_dec_and_test(), so in this case we have the necessary barriers.
  *
- * But if it succeeds we do not have any barriers, mutex_is_locked() or
+ * But if it succeeds we do not have any barriers, atomic_read(write_ctr) or
  * __this_cpu_add() below can be reordered with any LOAD/STORE done by the
  * reader inside the critical section. See the comments in down_write and
  * up_write below.
@@ -54,7 +54,7 @@ static bool update_fast_ctr(struct percpu_rw_semaphore *brw, unsigned int val)
 	bool success = false;
 
 	preempt_disable();
-	if (likely(!mutex_is_locked(&brw->writer_mutex))) {
+	if (likely(!atomic_read(&brw->write_ctr))) {
 		__this_cpu_add(*brw->fast_read_ctr, val);
 		success = true;
 	}
@@ -101,9 +101,8 @@ static int clear_fast_ctr(struct percpu_rw_semaphore *brw)
 }
 
 /*
- * A writer takes ->writer_mutex to exclude other writers and to force the
- * readers to switch to the slow mode, note the mutex_is_locked() check in
- * update_fast_ctr().
+ * A writer increments ->write_ctr to force the readers to switch to the
+ * slow mode, note the atomic_read() check in update_fast_ctr().
  *
  * After that the readers can only inc/dec the slow ->slow_read_ctr counter,
  * ->fast_read_ctr is stable. Once the writer moves its sum into the slow
@@ -114,11 +113,10 @@ static int clear_fast_ctr(struct percpu_rw_semaphore *brw)
  */
 void percpu_down_write(struct percpu_rw_semaphore *brw)
 {
-	/* also blocks update_fast_ctr() which checks mutex_is_locked() */
-	mutex_lock(&brw->writer_mutex);
-
+	/* tell update_fast_ctr() there is a pending writer */
+	atomic_inc(&brw->write_ctr);
 	/*
-	 * 1. Ensures mutex_is_locked() is visible to any down_read/up_read
+	 * 1. Ensures that write_ctr != 0 is visible to any down_read/up_read
 	 *    so that update_fast_ctr() can't succeed.
 	 *
 	 * 2. Ensures we see the result of every previous this_cpu_add() in
@@ -130,25 +128,25 @@ void percpu_down_write(struct percpu_rw_semaphore *brw)
 	 */
 	synchronize_sched();
 
+	/* exclude other writers, and block the new readers completely */
+	down_write(&brw->rw_sem);
+
 	/* nobody can use fast_read_ctr, move its sum into slow_read_ctr */
 	atomic_add(clear_fast_ctr(brw), &brw->slow_read_ctr);
 
-	/* block the new readers completely */
-	down_write(&brw->rw_sem);
-
 	/* wait for all readers to complete their percpu_up_read() */
 	wait_event(brw->write_waitq, !atomic_read(&brw->slow_read_ctr));
 }
 
 void percpu_up_write(struct percpu_rw_semaphore *brw)
 {
-	/* allow the new readers, but only the slow-path */
+	/* release the lock, but the readers can't use the fast-path */
 	up_write(&brw->rw_sem);
-
 	/*
 	 * Insert the barrier before the next fast-path in down_read,
 	 * see W_R case in the comment above update_fast_ctr().
 	 */
 	synchronize_sched();
-	mutex_unlock(&brw->writer_mutex);
+	/* the last writer unblocks update_fast_ctr() */
+	atomic_dec(&brw->write_ctr);
 }
-- 
1.5.5.1

[PATCH 2/3] percpu_rw_semaphore: add the lockdep annotations

[Oleg Nesterov]

Add the lockdep annotations. Not only this can help to find the
potential problems, we do not want the false warnings if, say,
the task takes two different percpu_rw_semaphore's for reading.
IOW, at least ->rw_sem should not use a single class.

This patch exposes this internal lock to lockdep so that it
represents the whole percpu_rw_semaphore. This way we do not
need to add another "fake" ->lockdep_map and lock_class_key.
More importantly, this also makes the output from lockdep much
more understandable if it finds the problem.

In short, with this patch from lockdep pov percpu_down_read()
and percpu_up_read() acquire/release ->rw_sem for reading, this
matches the actual semantics. This abuses __up_read() but I hope
this is fine and in fact I'd like to have down_read_no_lockdep()
as well, percpu_down_read_recursive_readers() will need it.

Signed-off-by: Oleg Nesterov <oleg@redhat.com>
---
 include/linux/percpu-rwsem.h |   10 +++++++++-
 lib/percpu-rwsem.c           |   21 +++++++++++++++++----
 2 files changed, 26 insertions(+), 5 deletions(-)

diff --git a/include/linux/percpu-rwsem.h b/include/linux/percpu-rwsem.h
index d2146a4..3e88c9a 100644
--- a/include/linux/percpu-rwsem.h
+++ b/include/linux/percpu-rwsem.h
@@ -5,6 +5,7 @@
 #include <linux/rwsem.h>
 #include <linux/percpu.h>
 #include <linux/wait.h>
+#include <linux/lockdep.h>
 
 struct percpu_rw_semaphore {
 	unsigned int __percpu	*fast_read_ctr;
@@ -20,7 +21,14 @@ extern void percpu_up_read(struct percpu_rw_semaphore *);
 extern void percpu_down_write(struct percpu_rw_semaphore *);
 extern void percpu_up_write(struct percpu_rw_semaphore *);
 
-extern int percpu_init_rwsem(struct percpu_rw_semaphore *);
+extern int __percpu_init_rwsem(struct percpu_rw_semaphore *,
+				const char *, struct lock_class_key *);
 extern void percpu_free_rwsem(struct percpu_rw_semaphore *);
 
+#define percpu_init_rwsem(brw)	\
+({								\
+	static struct lock_class_key rwsem_key;			\
+	__percpu_init_rwsem(brw, #brw, &rwsem_key);		\
+})
+
 #endif
diff --git a/lib/percpu-rwsem.c b/lib/percpu-rwsem.c
index e5a146e..ba2708f 100644
--- a/lib/percpu-rwsem.c
+++ b/lib/percpu-rwsem.c
@@ -2,18 +2,21 @@
 #include <linux/rwsem.h>
 #include <linux/percpu.h>
 #include <linux/wait.h>
+#include <linux/lockdep.h>
 #include <linux/percpu-rwsem.h>
 #include <linux/rcupdate.h>
 #include <linux/sched.h>
 #include <linux/errno.h>
 
-int percpu_init_rwsem(struct percpu_rw_semaphore *brw)
+int __percpu_init_rwsem(struct percpu_rw_semaphore *brw,
+			const char *name, struct lock_class_key *rwsem_key)
 {
 	brw->fast_read_ctr = alloc_percpu(int);
 	if (unlikely(!brw->fast_read_ctr))
 		return -ENOMEM;
 
-	init_rwsem(&brw->rw_sem);
+	/* ->rw_sem represents the whole percpu_rw_semaphore for lockdep */
+	__init_rwsem(&brw->rw_sem, name, rwsem_key);
 	atomic_set(&brw->write_ctr, 0);
 	atomic_set(&brw->slow_read_ctr, 0);
 	init_waitqueue_head(&brw->write_waitq);
@@ -66,19 +69,29 @@ static bool update_fast_ctr(struct percpu_rw_semaphore *brw, unsigned int val)
 /*
  * Like the normal down_read() this is not recursive, the writer can
  * come after the first percpu_down_read() and create the deadlock.
+ *
+ * Note: returns with lock_is_held(brw->rw_sem) == T for lockdep,
+ * percpu_up_read() does rwsem_release(). This pairs with the usage
+ * of ->rw_sem in percpu_down/up_write().
  */
 void percpu_down_read(struct percpu_rw_semaphore *brw)
 {
-	if (likely(update_fast_ctr(brw, +1)))
+	might_sleep();
+	if (likely(update_fast_ctr(brw, +1))) {
+		rwsem_acquire_read(&brw->rw_sem.dep_map, 0, 0, _RET_IP_);
 		return;
+	}
 
 	down_read(&brw->rw_sem);
 	atomic_inc(&brw->slow_read_ctr);
-	up_read(&brw->rw_sem);
+	/* avoid up_read()->rwsem_release() */
+	__up_read(&brw->rw_sem);
 }
 
 void percpu_up_read(struct percpu_rw_semaphore *brw)
 {
+	rwsem_release(&brw->rw_sem.dep_map, 1, _RET_IP_);
+
 	if (likely(update_fast_ctr(brw, -1)))
 		return;
 
-- 
1.5.5.1

Re: [PATCH 2/3] percpu_rw_semaphore: add the lockdep annotations

[Andrew Morton]

On Sun, 18 Nov 2012 20:03:21 +0100
Oleg Nesterov <oleg@redhat.com> wrote:

> Add the lockdep annotations. Not only this can help to find the
> potential problems, we do not want the false warnings if, say,
> the task takes two different percpu_rw_semaphore's for reading.
> IOW, at least ->rw_sem should not use a single class.
> 
> This patch exposes this internal lock to lockdep so that it
> represents the whole percpu_rw_semaphore. This way we do not
> need to add another "fake" ->lockdep_map and lock_class_key.
> More importantly, this also makes the output from lockdep much
> more understandable if it finds the problem.
> 
> In short, with this patch from lockdep pov percpu_down_read()
> and percpu_up_read() acquire/release ->rw_sem for reading, this
> matches the actual semantics. This abuses __up_read() but I hope
> this is fine and in fact I'd like to have down_read_no_lockdep()
> as well, percpu_down_read_recursive_readers() will need it.
> 
> ...
>
> -extern int percpu_init_rwsem(struct percpu_rw_semaphore *);
> +extern int __percpu_init_rwsem(struct percpu_rw_semaphore *,
> +				const char *, struct lock_class_key *);
>  extern void percpu_free_rwsem(struct percpu_rw_semaphore *);
>  
> +#define percpu_init_rwsem(brw)	\

Should have been called percpu_rwsem_init().  The naming in this code does
seem to be rather inconsistent.  s/percpu_rw_semaphore/percpu_rwsem/g
would be a good start, then consistently use percpu_rwsem_foo where
practical.  But percpu_rwsem_down_read() doesn't sound practical :(


Is there much point in doing all these changes as five separate patches
(so far)?  Perhaps it should all blobbed into as little as one patch(es)?


You sent your uprobes changes to Ingo as a git pull, but I doubt if
Ingo's trees contain the percpu_rwsem_rw_semaphore changes.  What's
happening here?

Re: [PATCH 2/3] percpu_rw_semaphore: add the lockdep annotations

[Oleg Nesterov]

On 11/19, Andrew Morton wrote:
>
> On Sun, 18 Nov 2012 20:03:21 +0100
> Oleg Nesterov <oleg@redhat.com> wrote:
>
> > -extern int percpu_init_rwsem(struct percpu_rw_semaphore *);
> > +extern int __percpu_init_rwsem(struct percpu_rw_semaphore *,
> > +				const char *, struct lock_class_key *);
> >  extern void percpu_free_rwsem(struct percpu_rw_semaphore *);
> >
> > +#define percpu_init_rwsem(brw)	\
>
> Should have been called percpu_rwsem_init(). The naming in this code does
> seem to be rather inconsistent.

Oh, I agree with any naming.

I guess Mikulas chose this name because the regular rw_semaphore has
init_rwsem(), not rwsem_init(), so this looks consistent.

> s/percpu_rw_semaphore/percpu_rwsem/g
> would be a good start, then consistently use percpu_rwsem_foo where
> practical.  But percpu_rwsem_down_read() doesn't sound practical :(

But personally I agree, percpu_rwsem_* looks better, and I will be
happy to send the trivial patch.

But can we do this later? This patch should touch the code in blockdev
and uprobes, and currently there is no single tree which this rename
can be based on.

> Is there much point in doing all these changes as five separate patches

four ;) .fix will be folded, I guess.

> (so far)?  Perhaps it should all blobbed into as little as one patch(es)?

Well, I'd prefer to keep this particular change as a separate patch,
and probably 3/3 too (just because I know nothing about kbuild/etc).

But 1/3 can be folded, I agree. And I won't argue if you ask me to
resend everything as one patch.

> You sent your uprobes changes to Ingo as a git pull, but I doubt if
> Ingo's trees contain the percpu_rwsem_rw_semaphore changes.

No, it doesn't. But, correctness-wise, percpu_rw_semaphore works fine
even without these changes, just it is "too slow" as it used in uprobes.
I hope that that fix and these changes will meet together in 3.8.

Oleg.

[PATCH 3/3] percpu_rw_semaphore: introduce CONFIG_PERCPU_RWSEM

[Oleg Nesterov]

Currently only block_dev and uprobes use percpu_rw_semaphore,
add the config option selected by BLOCK || UPROBES.

Signed-off-by: Oleg Nesterov <oleg@redhat.com>
---
 arch/Kconfig  |    1 +
 block/Kconfig |    1 +
 lib/Kconfig   |    3 +++
 lib/Makefile  |    3 ++-
 4 files changed, 7 insertions(+), 1 deletions(-)

diff --git a/arch/Kconfig b/arch/Kconfig
index 366ec06..cf4efe6 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -80,6 +80,7 @@ config UPROBES
 	bool "Transparent user-space probes (EXPERIMENTAL)"
 	depends on UPROBE_EVENT && PERF_EVENTS
 	default n
+	select PERCPU_RWSEM
 	help
 	  Uprobes is the user-space counterpart to kprobes: they
 	  enable instrumentation applications (such as 'perf probe')
diff --git a/block/Kconfig b/block/Kconfig
index a7e40a7..4a85ccf 100644
--- a/block/Kconfig
+++ b/block/Kconfig
@@ -4,6 +4,7 @@
 menuconfig BLOCK
        bool "Enable the block layer" if EXPERT
        default y
+       select PERCPU_RWSEM
        help
 	 Provide block layer support for the kernel.
 
diff --git a/lib/Kconfig b/lib/Kconfig
index 4b31a46..75cdb77 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -42,6 +42,9 @@ config GENERIC_IO
 config STMP_DEVICE
 	bool
 
+config PERCPU_RWSEM
+	boolean
+
 config CRC_CCITT
 	tristate "CRC-CCITT functions"
 	help
diff --git a/lib/Makefile b/lib/Makefile
index 4dad4a7..20f7eda 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 idr.o int_sqrt.o extable.o \
 	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o percpu-rwsem.o
+	 is_single_threaded.o plist.o decompress.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
@@ -40,6 +40,7 @@ obj-$(CONFIG_DEBUG_LOCKING_API_SELFTESTS) += locking-selftest.o
 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
 
 CFLAGS_hweight.o = $(subst $(quote),,$(CONFIG_ARCH_HWEIGHT_CFLAGS))
 obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
-- 
1.5.5.1

Q: __lockdep_no_validate__ (Was: [PATCH -mm 0/3] percpu_rw_semaphore: lockdep + config)

[Oleg Nesterov]

On 11/18, Oleg Nesterov wrote:
>
> On 11/11, Oleg Nesterov wrote:
> >
> It turns out, lockdep annotations are not that simple due to internal
> locks used by percpu_rw_semaphore. To clarify, it is actually simple
> but lockdep_set_novalidate_class() doesn't seem to actually work, and
> more importantly, it must not be used according to checkpatch.pl.

Still, is __lockdep_no_validate__ logic correct? I am just curious.

Consider the following code,


	DEFINE_MUTEX(m1);
	DEFINE_MUTEX(m2);
	DEFINE_MUTEX(mx);

	static void trigger_lockdep_bug(bool novalidate)
	{
		if (novalidate)
			lockdep_set_novalidate_class(&mx);

		// m1 -> mx -> m2
		mutex_lock(&m1);
			mutex_lock(&mx);
		mutex_lock(&m2);
		mutex_unlock(&m2);
			mutex_unlock(&mx);
		mutex_unlock(&m1);


		// m2 -> m1 ; should trigger the warning

		mutex_lock(&m2);
		mutex_lock(&m1);
		mutex_unlock(&m1);
		mutex_unlock(&m2);

	}

trigger_lockdep_bug(false) works correctly, but novalidate => true
confuses (I think) lockdep and it doesn't detect the trivial deadlock.

check_prev_add(m1, mx) still adds the new dependency, but then it is
ignored because of __lockdep_no_validate__ check.

Certainly I do not understand this code (and I am sure I will never
understand it even if I try ;) But perhaps something like below makes
sense? Or I misunderstood the purpose of lockdep_set_novalidate_class?

Thanks,

Oleg.

--- x/kernel/lockdep.c
+++ x/kernel/lockdep.c
@@ -1935,7 +1939,8 @@ check_prevs_add(struct task_struct *curr, struct held_lock *next)
 		 * Only non-recursive-read entries get new dependencies
 		 * added:
 		 */
-		if (hlock->read != 2) {
+		if (hlock->read != 2 &&
+		    hlock->instance->key != &__lockdep_no_validate__) {
 			if (!check_prev_add(curr, hlock, next,
 						distance, trylock_loop))
 				return 0;