uprobes: register/unregister can race with fork

This patch adds the new sleeping lock, brw_mutex. Unlike rw_semaphore it allows multiple writers too, just "read" and "write" are mutually exclusive.

brw_start_read() and brw_end_read() are extremely cheap, they only do this_cpu_inc(read_ctr) + atomic_read() if there are no waiting writers.

OTOH it is write-biased, any brw_start_write() blocks the new readers. But "write" is slow, it does synchronize_sched() to serialize with preempt_disable() in brw_start_read(), and wait_event(write_waitq) can have a lot of extra wakeups before percpu-counter-sum becomes zero.

Signed-off-by Oleg Nesterov <[email protected]>

---
 include/linux/brw_mutex.h |   22 +++++++++++++++
 lib/Makefile              |    2 +-
 lib/brw_mutex.c           |   67 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 90 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/brw_mutex.h
 create mode 100644 lib/brw_mutex.c

include/linux/brw_mutex.h new file +22 -0

new file mode 100644
index 0000000..16b8d5f
@@ -0,0 +1,22 @@
+#ifndef _LINUX_BRW_MUTEX_H
+#define _LINUX_BRW_MUTEX_H
+
+#include <linux/percpu.h>
+#include <linux/wait.h>
+
+struct brw_mutex {
+	long __percpu		*read_ctr;
+	atomic_t		write_ctr;
+	wait_queue_head_t	read_waitq;
+	wait_queue_head_t	write_waitq;
+};
+
+extern int brw_mutex_init(struct brw_mutex *brw);
+
+extern void brw_start_read(struct brw_mutex *brw);
+extern void brw_end_read(struct brw_mutex *brw);
+
+extern void brw_start_write(struct brw_mutex *brw);
+extern void brw_end_write(struct brw_mutex *brw);
+
+#endif

lib/Makefile +1 -1

index 3128e35..18f2876 100644
@@ -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
+	 is_single_threaded.o plist.o decompress.o brw_mutex.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o

lib/brw_mutex.c new file +13 -0

new file mode 100644
index 0000000..41984a6
@@ -0,0 +1,67 @@
+#include <linux/brw_mutex.h>
+#include <linux/rcupdate.h>
+#include <linux/sched.h>
+
+int brw_mutex_init(struct brw_mutex *brw)
+{
+	atomic_set(&brw->write_ctr, 0);
+	init_waitqueue_head(&brw->read_waitq);
+	init_waitqueue_head(&brw->write_waitq);
+	brw->read_ctr = alloc_percpu(long);
+	return brw->read_ctr ? 0 : -ENOMEM;
+}
+

lib/brw_mutex.c new file +10 -0

+static inline long brw_read_ctr(struct brw_mutex *brw)
+{
+	long sum = 0;
+	int cpu;
+
+	for_each_possible_cpu(cpu)
+		sum += per_cpu(*brw->read_ctr, cpu);
+
+	return sum;
+}

lib/brw_mutex.c new file +7 -0

+}
+
+void brw_end_write(struct brw_mutex *brw)
+{
+	if (atomic_dec_and_test(&brw->write_ctr))
+		wake_up_all(&brw->read_waitq);
+}

Signature · 1 line

1.5.5.1

lib/brw_mutex.c line 23

Quoted 11 lines

lib/brw_mutex.c new file +10 -0

+void brw_start_read(struct brw_mutex *brw)
+{
+	for (;;) {
+		bool done = false;
+
+		preempt_disable();
+		if (likely(!atomic_read(&brw->write_ctr))) {
+			__this_cpu_inc(*brw->read_ctr);
+			done = true;
+		}

brw_start_read() is not recursive -- attempting to call it recursively can result in deadlock if a writer has shown up in the meantime.

Which is often OK, but not sure what you intended.

Review

Quoted 2 lines

(quoted diff) +2 -0

+void brw_end_read(struct brw_mutex *brw)
+{

I believe that you need smp_mb() here.

The wake_up_all()'s memory barriers
do not suffice because some other reader might have awakened the writer between this_cpu_dec() and wake_up_all().

lib/brw_mutex.c line 39

Quoted 5 lines

lib/brw_mutex.c new file +5 -0

+	this_cpu_dec(*brw->read_ctr);
+
+	if (unlikely(atomic_read(&brw->write_ctr)))
+		wake_up_all(&brw->write_waitq);
+}

Of course, it would be good to avoid smp_mb on the fast path. Here is one way to avoid it:

void brw_end_read(struct brw_mutex *brw)

{
	if (unlikely(atomic_read(&brw->write_ctr))) {
		smp_mb();
		this_cpu_dec(*brw->read_ctr);
		wake_up_all(&brw->write_waitq);

Quoted 5 lines

lib/brw_mutex.c new file +5 -0

+void brw_start_write(struct brw_mutex *brw)
+{
+	atomic_inc(&brw->write_ctr);
+	synchronize_sched();
+	/*

lib/brw_mutex.c line 60

Quoted 4 lines

lib/brw_mutex.c new file +4 -0

+	 * Thereafter brw_*_read() must see write_ctr != 0,
+	 * and we should see the result of __this_cpu_inc().
+	 */
+	wait_event(brw->write_waitq, brw_read_ctr(brw) == 0);

This looks like it allows multiple writers to proceed concurrently. They both increment, do a synchronize_sched(), do the wait_event(), and then are both awakened by the last reader.

Was that the intent? (The implementation of brw_end_write() makes it look like it is in fact the intent.)

Paul, thanks for looking!

Quoted 14 lines · Paul E. McKenney

lib/brw_mutex.c line 23

Quoted 11 lines

lib/brw_mutex.c new file +10 -0

+void brw_start_read(struct brw_mutex *brw)
+{
+	for (;;) {
+		bool done = false;
+
+		preempt_disable();
+		if (likely(!atomic_read(&brw->write_ctr))) {
+			__this_cpu_inc(*brw->read_ctr);
+			done = true;
+		}

brw_start_read() is not recursive -- attempting to call it recursively can result in deadlock if a writer has shown up in the meantime.

Yes, yes, it is not recursive. Like rw_semaphore.

Quoted 1 line

Which is often OK, but not sure what you intended.

I forgot to document this in the changelog.

Quoted 4 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+void brw_end_read(struct brw_mutex *brw)
+{

I believe that you need smp_mb() here.

I don't understand why...

Quoted 3 lines

The wake_up_all()'s memory barriers
do not suffice because some other reader might have awakened the writer between this_cpu_dec() and wake_up_all().

But __wake_up(q) takes q->lock? And the same lock is taken by prepare_to_wait(), so how can the writer miss the result of _dec?

Quoted 9 lines

lib/brw_mutex.c line 39

Quoted 5 lines

lib/brw_mutex.c new file +5 -0

+	this_cpu_dec(*brw->read_ctr);
+
+	if (unlikely(atomic_read(&brw->write_ctr)))
+		wake_up_all(&brw->write_waitq);
+}

Of course, it would be good to avoid smp_mb on the fast path. Here is one way to avoid it:

Quoted 6 lines

void brw_end_read(struct brw_mutex *brw)

{
	if (unlikely(atomic_read(&brw->write_ctr))) {
		smp_mb();
		this_cpu_dec(*brw->read_ctr);
		wake_up_all(&brw->write_waitq);

Hmm... still can't understand.

It seems that this mb() is needed to ensure that brw_end_read() can't miss write_ctr != 0.

But we do not care unless the writer already does wait_event(). And before it does wait_event() it calls synchronize_sched() after it sets write_ctr != 0. Doesn't this mean that after that any preempt-disabled section must see write_ctr != 0 ?

This code actually checks write_ctr after preempt_disable + enable, but I think this doesn't matter?

Paul, most probably I misunderstood you. Could you spell please?

Quoted 5 lines

Quoted 5 lines

lib/brw_mutex.c new file +5 -0

+void brw_start_write(struct brw_mutex *brw)
+{
+	atomic_inc(&brw->write_ctr);
+	synchronize_sched();
+	/*

Quoted 8 lines

lib/brw_mutex.c line 60

Quoted 4 lines

lib/brw_mutex.c new file +4 -0

+	 * Thereafter brw_*_read() must see write_ctr != 0,
+	 * and we should see the result of __this_cpu_inc().
+	 */
+	wait_event(brw->write_waitq, brw_read_ctr(brw) == 0);

This looks like it allows multiple writers to proceed concurrently. They both increment, do a synchronize_sched(), do the wait_event(), and then are both awakened by the last reader.

Yes. From the changelog:

Unlike rw_semaphore it allows multiple writers too, just "read" and "write" are mutually exclusive.

Quoted 2 lines

Was that the intent? (The implementation of brw_end_write() makes it look like it is in fact the intent.)

Please look at 2/2.

Multiple uprobe_register() or uprobe_unregister() can run at the same time to install/remove the system-wide breakpoint, and brw_start_write() is used to block dup_mmap() to avoid the race. But they do not block each other.

Quoted 9 lines · Oleg Nesterov

Quoted 2 lines

I believe that you need smp_mb() here.

I don't understand why...

Quoted 3 lines

The wake_up_all()'s memory barriers
do not suffice because some other reader might have awakened the writer between this_cpu_dec() and wake_up_all().

Quoted 2 lines

But __wake_up(q) takes q->lock? And the same lock is taken by prepare_to_wait(), so how can the writer miss the result of _dec?

Suppose that the writer arrives and sees that the value of the counter is zero,

and thus never sleeps, and so is also not awakened?

Quoted 17 lines

Quoted 6 lines

void brw_end_read(struct brw_mutex *brw)

{
	if (unlikely(atomic_read(&brw->write_ctr))) {
		smp_mb();
		this_cpu_dec(*brw->read_ctr);
		wake_up_all(&brw->write_waitq);

Hmm... still can't understand.

It seems that this mb() is needed to ensure that brw_end_read() can't miss write_ctr != 0.

But we do not care unless the writer already does wait_event(). And before it does wait_event() it calls synchronize_sched() after it sets write_ctr != 0. Doesn't this mean that after that any preempt-disabled section must see write_ctr != 0 ?

Quoted 4 lines

This code actually checks write_ctr after preempt_disable + enable, but I think this doesn't matter?

Paul, most probably I misunderstood you. Could you spell please?

Let me try outlining the sequence of events that I am worried about...

1. Task A invokes brw_start_read(). There is no writer, so it
takes the fastpath.

2. Task B invokes brw_start_write(), atomically increments

	&brw->write_ctr, and executes synchronize_sched().

3. Task A invokes brw_end_read() and does this_cpu_dec().

4. Task B invokes wait_event(), which invokes brw_read_ctr()
and sees the result as zero.

Quoted 11 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 2 lines

I believe that you need smp_mb() here.

I don't understand why...

Quoted 3 lines

The wake_up_all()'s memory barriers
do not suffice because some other reader might have awakened the writer between this_cpu_dec() and wake_up_all().

Quoted 5 lines

Quoted 2 lines

But __wake_up(q) takes q->lock? And the same lock is taken by prepare_to_wait(), so how can the writer miss the result of _dec?

Suppose that the writer arrives and sees that the value of the counter is zero,

after synchronize_sched(). So there are no readers (but perhaps there are brw_end_read's in flight which already decremented read_ctr)

Quoted 1 line

and thus never sleeps, and so is also not awakened?

and why do we need wakeup in this case?

Quoted 30 lines

Quoted 17 lines

Quoted 6 lines

void brw_end_read(struct brw_mutex *brw)

{
	if (unlikely(atomic_read(&brw->write_ctr))) {
		smp_mb();
		this_cpu_dec(*brw->read_ctr);
		wake_up_all(&brw->write_waitq);

Hmm... still can't understand.

It seems that this mb() is needed to ensure that brw_end_read() can't miss write_ctr != 0.

But we do not care unless the writer already does wait_event(). And before it does wait_event() it calls synchronize_sched() after it sets write_ctr != 0. Doesn't this mean that after that any preempt-disabled section must see write_ctr != 0 ?

Quoted 4 lines

This code actually checks write_ctr after preempt_disable + enable, but I think this doesn't matter?

Paul, most probably I misunderstood you. Could you spell please?

Let me try outlining the sequence of events that I am worried about...

1. Task A invokes brw_start_read(). There is no writer, so it
takes the fastpath.

2. Task B invokes brw_start_write(), atomically increments

	&brw->write_ctr, and executes synchronize_sched().

Quoted 1 line

3. Task A invokes brw_end_read() and does this_cpu_dec().

OK. And to simplify this discussion, suppose that A invoked brw_start_read() on CPU_0 and thus incremented read_ctr[0], and then it migrates to CPU_1 and brw_end_read() uses read_ctr[1].

My understanding was, brw_start_write() must see read_ctr[0] == 1 after synchronize_sched().

Quoted 2 lines

4. Task B invokes wait_event(), which invokes brw_read_ctr()
and sees the result as zero.

So my understanding is completely wrong? I thought that after synchronize_sched() we should see the result of any operation which were done inside the preempt-disable section.

No?

Hmm. Suppose that we have long A = B = STOP = 0, and

	void func(void)
	{
		preempt_disable();
		if (!STOP) {
			A = 1;
			B = 1;
		}
		preempt_enable();
	}

Now, you are saying that this code

	STOP = 1;

	synchronize_sched();

	BUG_ON(A != B);

is not correct? (yes, yes, this example is not very good).

The comment above synchronize_sched() says:

return ... after all currently executing rcu-sched read-side critical sections have completed.

But if this code is wrong, then what "completed" actually means? I thought that it also means "all memory operations have completed", but this is not true?

From what I can see, your interpretation of synchronize_sched() is

Oleg.

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

This patch adds the new sleeping lock, brw_mutex. Unlike rw_semaphore it allows multiple writers too, just "read" and "write" are mutually exclusive.

Quoted 3 lines · Oleg Nesterov

This patch adds the new sleeping lock, brw_mutex. Unlike rw_semaphore it allows multiple writers too, just "read" and "write" are mutually exclusive.

So those semantics just don't sound sane. It's also not what any kind of normal "rw" lock ever does.

So can you explain why these particular insane semantics are useful, and what for?

Quoted 8 lines · Linus Torvalds

Quoted 3 lines · Oleg Nesterov

This patch adds the new sleeping lock, brw_mutex. Unlike rw_semaphore it allows multiple writers too, just "read" and "write" are mutually exclusive.

So those semantics just don't sound sane. It's also not what any kind of normal "rw" lock ever does.

Yes, this is not usual.

And initially I made brw_sem which allows only 1 writer, but then I changed this patch.

Quoted 2 lines

So can you explain why these particular insane semantics are useful, and what for?

To allow multiple uprobe_register/unregister at the same time. Mostly to not add the "regression", currently this is possible.

It is not that I think this is terribly important, but still. And personally I think that "multiple writers" is not necessarily insane in general. Suppose you have the complex object/subsystem, the readers can use a single brw_mutex to access it "lockless", start_read() is very cheap.

But start_write() is slow. Multiple writes can use the fine-grained inside the start_write/end_write section and do not block each other.

Quoted 5 lines · Oleg Nesterov

Quoted 3 lines · Paul E. McKenney

Suppose that the writer arrives and sees that the value of the counter is zero,

Quoted 2 lines

after synchronize_sched(). So there are no readers (but perhaps there are brw_end_read's in flight which already decremented read_ctr)

But the preempt_disable() region only covers read acquisition. So synchronize_sched() waits only for all the brw_start_read() calls to reach the preempt_enable()

-- it cannot wait for all the resulting readers to reach the corresponding brw_end_read().

Quoted 3 lines

Quoted 1 line

and thus never sleeps, and so is also not awakened?

and why do we need wakeup in this case?

To get the memory barriers required to keep the critical sections ordered -- to ensure that everyone sees the reader's critical section as ending before the writer's critical section starts.

Quoted 7 lines · Paul E. McKenney

Quoted 5 lines · Oleg Nesterov

Quoted 3 lines · Paul E. McKenney

Suppose that the writer arrives and sees that the value of the counter is zero,

Quoted 6 lines

Quoted 2 lines

after synchronize_sched(). So there are no readers (but perhaps there are brw_end_read's in flight which already decremented read_ctr)

But the preempt_disable() region only covers read acquisition. So synchronize_sched() waits only for all the brw_start_read() calls to reach the preempt_enable()

Yes.

Quoted 2 lines

-- it cannot wait for all the resulting readers to reach the corresponding brw_end_read().

Indeed.

Quoted 7 lines

Quoted 3 lines

Quoted 1 line

and thus never sleeps, and so is also not awakened?

and why do we need wakeup in this case?

To get the memory barriers required to keep the critical sections ordered -- to ensure that everyone sees the reader's critical section as ending before the writer's critical section starts.

And now I am starting to think I misunderstood your concern from the very beginning.

I thought that you meant that without mb() brw_start_write() can race with brw_end_read() and hang forever.

But probably you meant that we need the barriers to ensure that, say, if the reader does

	brw_start_read();
	CONDITION = 1;
	brw_end_read();

then the writer must see CONDITION != 0 after brw_start_write() ? (or vice-versa)

In this case we need the barrier, yes. Obviously brw_start_write() can return right after this_cpu_dec() and before wake_up_all().

2/2 doesn't need this guarantee but I agree, this doesn't look sane in gerenal...

Or I misunderstood you again?

Quoted 7 lines · Oleg Nesterov

I thought that you meant that without mb() brw_start_write() can race with brw_end_read() and hang forever.

But probably you meant that we need the barriers to ensure that, say, if the reader does

Quoted 6 lines

	brw_start_read();
	CONDITION = 1;
	brw_end_read();

then the writer must see CONDITION != 0 after brw_start_write() ? (or vice-versa)

Yes, this is exactly my concern.

Quoted 5 lines

In this case we need the barrier, yes. Obviously brw_start_write() can return right after this_cpu_dec() and before wake_up_all().

2/2 doesn't need this guarantee but I agree, this doesn't look sane in gerenal...

Or name it something not containing "lock". And clearly document the behavior and how it is to be used. ;-)

Ooooh. And I just noticed include/linux/percpu-rwsem.h which does something similar. Certainly it was not in my tree when I started this patch... percpu_down_write() doesn't allow multiple writers, but the main problem it uses msleep(1). It should not, I think.

But. It seems that percpu_up_write() is equally wrong? Doesn't it need synchronize_rcu() before "p->locked = false" ?

(add Mikulas)

Oleg.

Quoted 4 lines · Oleg Nesterov

Ooooh. And I just noticed include/linux/percpu-rwsem.h which does something similar. Certainly it was not in my tree when I started this patch... percpu_down_write() doesn't allow multiple writers, but the main problem it uses msleep(1). It should not, I think.

synchronize_rcu() can sleep for hundred milliseconds, so msleep(1) is not a big problem.

Quoted 8 lines · Mikulas Patocka

Quoted 4 lines · Oleg Nesterov

Ooooh. And I just noticed include/linux/percpu-rwsem.h which does something similar. Certainly it was not in my tree when I started this patch... percpu_down_write() doesn't allow multiple writers, but the main problem it uses msleep(1). It should not, I think.

Quoted 2 lines

synchronize_rcu() can sleep for hundred milliseconds, so msleep(1) is not a big problem.

That code is beyond ugly though.. it should really not have been merged.

There's absolutely no reason for it to use RCU except to make it more

complicated. And as Oleg pointed out that msleep() is very ill considered.

The very worst part of it seems to be that nobody who's usually involved with locking primitives was ever consulted (Linus, PaulMck, Oleg, Ingo, tglx, dhowells and me). It doesn't even have lockdep annotations :/

So the only reason you appear to use RCU is because you don't actually have a sane way to wait for count==0. And I'm contesting rcu_sync() is sane here -- for the very simple reason you still need while (count) loop right after it.

So it appears you want an totally reader biased, sleepable rw-lock like thing?

So did you consider keeping the inc/dec on the same per-cpu variable? Yes this adds a potential remote access to dec and requires you to use atomics, but I would not be surprised if the inc/dec were mostly on the same cpu most of the times -- which might be plenty fast for what you want.

If you've got coherent per-cpu counts, you can better do the waitqueue/wake condition for write_down.

It might also make sense to do away with the mutex, there's no point in serializing the wakeups in the p->locked case of down_read.

Furthermore,
p->locked seems a complete duplicate of the mutex state, so removing the mutex also removes that duplication.

Also, that CONFIG_x86 thing.. *shudder*...

So if you can do an alternative implementation without RCU, show it.

The
goal is - there should be no LOCK instructions on the read path and as few barriers as possible.

Quoted 5 lines

So did you consider keeping the inc/dec on the same per-cpu variable? Yes this adds a potential remote access to dec and requires you to use atomics, but I would not be surprised if the inc/dec were mostly on the same cpu most of the times -- which might be plenty fast for what you want.

Yes, I tried this approach - it involves doing LOCK instruction on read lock, remembering the cpu and doing another LOCK instruction on read unlock (which will hopefully be on the same CPU, so no cacheline bouncing happens in the common case). It was slower than the approach without any LOCK instructions (43.3 seconds seconds for the implementation with per-cpu LOCKed access, 42.7 seconds for this implementation without atomic instruction; the benchmark involved doing 512-byte direct-io reads and writes on a ramdisk with 8 processes on 8-core machine).

Quoted 2 lines

If you've got coherent per-cpu counts, you can better do the waitqueue/wake condition for write_down.

synchronize_rcu() is way slower than msleep(1) - so I don't see a reason why should it be complicated to avoid msleep(1).

Quoted 2 lines

It might also make sense to do away with the mutex, there's no point in serializing the wakeups in the p->locked case of down_read.

The advantage of a mutex is that it is already protected against starvation. If I replace the mutex with a wait queue and retry, there is no starvation protection.

Quoted 3 lines

Furthermore,
p->locked seems a complete duplicate of the mutex state, so removing the mutex also removes that duplication.

We could replace if (p->locked) with if (mutex_is_locked(p->mtx))

But using preempt_{disable,enable} and using synchronize_sched() would be better (for PREEMPT_RCU) although it wouldn't fix anything fundamental.

Fine goal, although somewhat arch specific. Also note that there's a relation between atomics and memory barriers, one isn't necessarily worse than the other, they all require synchronization of sorts.

Quoted 8 lines

Yes, I tried this approach - it involves doing LOCK instruction on read lock, remembering the cpu and doing another LOCK instruction on read unlock (which will hopefully be on the same CPU, so no cacheline bouncing happens in the common case). It was slower than the approach without any LOCK instructions (43.3 seconds seconds for the implementation with per-cpu LOCKed access, 42.7 seconds for this implementation without atomic instruction; the benchmark involved doing 512-byte direct-io reads and writes on a ramdisk with 8 processes on 8-core machine).

So why is that a problem? Surely that's already tons better then what you've currently got.

Quoted 11 lines · Peter Zijlstra

Quoted 8 lines

Yes, I tried this approach - it involves doing LOCK instruction on read lock, remembering the cpu and doing another LOCK instruction on read unlock (which will hopefully be on the same CPU, so no cacheline bouncing happens in the common case). It was slower than the approach without any LOCK instructions (43.3 seconds seconds for the implementation with per-cpu LOCKed access, 42.7 seconds for this implementation without atomic instruction; the benchmark involved doing 512-byte direct-io reads and writes on a ramdisk with 8 processes on 8-core machine).

So why is that a problem? Surely that's already tons better then what you've currently got.

Percpu rw-semaphores do not improve performance at all. I put them there to avoid performance regression, not to improve performance.

All Linux kernels have a race condition - when you change block size of a block device and you read or write the device at the same time, a crash may happen. This bug is there since ever. Recently, this bug started to cause major trouble - multiple high profile business sites report crashes because of this race condition.

You can fix this race by using a read lock around I/O paths and write lock around block size changing, but normal rw semaphore cause cache line bouncing when taken for read by multiple processors and I/O performance degradation because of it is measurable.

Quoted 25 lines · Mikulas Patocka

Quoted 11 lines · Peter Zijlstra

Quoted 8 lines

Yes, I tried this approach - it involves doing LOCK instruction on read lock, remembering the cpu and doing another LOCK instruction on read unlock (which will hopefully be on the same CPU, so no cacheline bouncing happens in the common case). It was slower than the approach without any LOCK instructions (43.3 seconds seconds for the implementation with per-cpu LOCKed access, 42.7 seconds for this implementation without atomic instruction; the benchmark involved doing 512-byte direct-io reads and writes on a ramdisk with 8 processes on 8-core machine).

So why is that a problem? Surely that's already tons better then what you've currently got.

Percpu rw-semaphores do not improve performance at all. I put them there to avoid performance regression, not to improve performance.

All Linux kernels have a race condition - when you change block size of a block device and you read or write the device at the same time, a crash may happen. This bug is there since ever. Recently, this bug started to cause major trouble - multiple high profile business sites report crashes because of this race condition.

Quoted 4 lines

You can fix this race by using a read lock around I/O paths and write lock around block size changing, but normal rw semaphore cause cache line bouncing when taken for read by multiple processors and I/O performance degradation because of it is measurable.

This doesn't sound like a new problem. Hasn't this global access, single modifier exclusion problem been solved before in the VFS? e.g. mnt_want_write()/mnt_make_readonly()

Cheers,

Dave.

Quoted 35 lines · Dave Chinner

Quoted 25 lines · Mikulas Patocka

Quoted 11 lines · Peter Zijlstra

Quoted 8 lines

Yes, I tried this approach - it involves doing LOCK instruction on read lock, remembering the cpu and doing another LOCK instruction on read unlock (which will hopefully be on the same CPU, so no cacheline bouncing happens in the common case). It was slower than the approach without any LOCK instructions (43.3 seconds seconds for the implementation with per-cpu LOCKed access, 42.7 seconds for this implementation without atomic instruction; the benchmark involved doing 512-byte direct-io reads and writes on a ramdisk with 8 processes on 8-core machine).

So why is that a problem? Surely that's already tons better then what you've currently got.

Percpu rw-semaphores do not improve performance at all. I put them there to avoid performance regression, not to improve performance.

All Linux kernels have a race condition - when you change block size of a block device and you read or write the device at the same time, a crash may happen. This bug is there since ever. Recently, this bug started to cause major trouble - multiple high profile business sites report crashes because of this race condition.

Quoted 4 lines

You can fix this race by using a read lock around I/O paths and write lock around block size changing, but normal rw semaphore cause cache line bouncing when taken for read by multiple processors and I/O performance degradation because of it is measurable.

This doesn't sound like a new problem. Hasn't this global access, single modifier exclusion problem been solved before in the VFS? e.g. mnt_want_write()/mnt_make_readonly()

Quoted 3 lines

Cheers,

Dave.

Yes, mnt_want_write()/mnt_make_readonly() do the same thing as percpu rw semaphores. I think you can convert mnt_want_write()/mnt_make_readonly() to use percpu rw semaphores and remove the duplicated code.

Quoted 4 lines · Mikulas Patocka

Yes, mnt_want_write()/mnt_make_readonly() do the same thing as percpu rw semaphores. I think you can convert mnt_want_write()/mnt_make_readonly() to use percpu rw semaphores and remove the duplicated code.

I think you misunderstood my point - that rather than re-inventing the wheel, why didn't you just copy something that is known to work?

Quoted 10 lines · Dave Chinner

Quoted 4 lines · Mikulas Patocka

Yes, mnt_want_write()/mnt_make_readonly() do the same thing as percpu rw semaphores. I think you can convert mnt_want_write()/mnt_make_readonly() to use percpu rw semaphores and remove the duplicated code.

I think you misunderstood my point - that rather than re-inventing the wheel, why didn't you just copy something that is known to work?

I don't understand why do you both think that __mnt_want_write() and mnt_make_readonly() provides the same functionality. I looked at this code before I started this patch, and unless I completely misread it this does very different things. It is not "lock" at all.

Oleg.

On Fri, 26 Oct 2012, Oleg Nesterov wrote:

I didn't know about. The code is not reusable, and it doesn't really do locking.

Quoted 6 lines

I don't understand why do you both think that __mnt_want_write() and mnt_make_readonly() provides the same functionality. I looked at this code before I started this patch, and unless I completely misread it this does very different things. It is not "lock" at all.

Oleg.

mnt_want_write uses percpu array of counters, just like percpu semaphores.

The code is different, but it can be changed to use percpu rw semaphores (if we add percpu_down_write_trylock).

As for the changing fs/namespace.c to use percpu_rwsem, I am not sure it is that simple and even worthwhile but I won't argue, I do not pretend I understand this code.

Quoted 2 lines

The code is different, but it can be changed to use percpu rw semaphores (if we add percpu_down_write_trylock).

I don't really understand how you can make percpu_down_write_trylock() atomic so that it can be called under br_write_lock(vfsmount_lock) in sb_prepare_remount_readonly(). So I guess you also need to replace vfsmount_lock at least. Or _trylock needs the barriers in _down_read. Or I missed something.

Oleg.

synchronize_rcu() is way slower than msleep(1) -

so I don't see a reason
why should it be complicated to avoid msleep(1).

Quoted 2 lines · Mikulas Patocka

synchronize_rcu() is way slower than msleep(1) -

This depends, I guess. but this doesn't mmatter,

Quoted 2 lines

so I don't see a reason
why should it be complicated to avoid msleep(1).

I don't think this really needs complications. Please look at this patch for example. Or initial (single writer) version below. It is not finished and lacks the barriers too, but I do not think it is more complex.

Oleg.

struct brw_sem {
	long __percpu		*read_ctr;
	wait_queue_head_t	read_waitq;
	struct mutex		writer_mutex;
	struct task_struct	*writer;
};

int brw_init(struct brw_sem *brw)

{
	brw->writer = NULL;
	mutex_init(&brw->writer_mutex);
	init_waitqueue_head(&brw->read_waitq);
	brw->read_ctr = alloc_percpu(long);
	return brw->read_ctr ? 0 : -ENOMEM;
}

void brw_down_read(struct brw_sem *brw)

{
	for (;;) {
		bool done = false;

		preempt_disable();
		if (likely(!brw->writer)) {
			__this_cpu_inc(*brw->read_ctr);
			done = true;
		}
		preempt_enable();

		if (likely(done))
			break;

		__wait_event(brw->read_waitq, !brw->writer);
	}
}

void brw_up_read(struct brw_sem *brw)

{
	struct task_struct *writer;

	preempt_disable();
	__this_cpu_dec(*brw->read_ctr);
	writer = ACCESS_ONCE(brw->writer);
	if (unlikely(writer))
		wake_up_process(writer);
	preempt_enable();
}

static inline long brw_read_ctr(struct brw_sem *brw)

{
	long sum = 0;
	int cpu;

	for_each_possible_cpu(cpu)
		sum += per_cpu(*brw->read_ctr, cpu);

	return sum;
}

void brw_down_write(struct brw_sem *brw)

{
	mutex_lock(&brw->writer_mutex);
	brw->writer = current;
	synchronize_sched();
	/*
	 * Thereafter brw_*_read() must see ->writer != NULL,
	 * and we should see the result of __this_cpu_inc().
	 */
	for (;;) {
		set_current_state(TASK_UNINTERRUPTIBLE);
		if (brw_read_ctr(brw) == 0)
			break;
		schedule();
	}
	__set_current_state(TASK_RUNNING);
	/*
	 * We can add another synchronize_sched() to avoid the
	 * spurious wakeups from brw_up_read() after return.
	 */
}

void brw_up_write(struct brw_sem *brw)

{
	brw->writer = NULL;
	synchronize_sched();

	wake_up_all(&brw->read_waitq);
	mutex_unlock(&brw->writer_mutex);
}

Quoted 4 lines · Oleg Nesterov

Quoted 2 lines · Mikulas Patocka

synchronize_rcu() is way slower than msleep(1) -

Quoted 8 lines

This depends, I guess. but this doesn't mmatter,

Quoted 2 lines

so I don't see a reason
why should it be complicated to avoid msleep(1).

I don't think this really needs complications. Please look at this patch for example. Or initial (single writer) version below. It is not finished and lacks the barriers too, but I do not think it is

Quoted 1 line

more complex.

Hi

My implementation has a smaller structure (it doesn't have wait_queue_head_t).

Your implementation is prone to starvation - if the writer has a high priority and if it is doing back-to-back write unlocks/locks, it may happen that the readers have no chance to run.

The use of mutex instead of a wait queue in my implementation is unusual, but I don't see anything wrong with it

Quoted 7 lines

static inline long brw_read_ctr(struct brw_sem *brw)

{
	long sum = 0;
	int cpu;

	for_each_possible_cpu(cpu)
		sum += per_cpu(*brw->read_ctr, cpu);

Integer overflow on signed types is undefined - you should use unsigned long - you can use -fwrapv option to gcc to make signed overflow defined, but Linux doesn't use it.

Quoted 4 lines

void brw_up_write(struct brw_sem *brw)

{
	brw->writer = NULL;
	synchronize_sched();

That synchronize_sched should be put before brw->writer = NULL.

I had this bug in my implementation too.

Quoted 13 lines · Paul E. McKenney

Quoted 11 lines · Oleg Nesterov

I thought that you meant that without mb() brw_start_write() can race with brw_end_read() and hang forever.

But probably you meant that we need the barriers to ensure that, say, if the reader does

	brw_start_read();
	CONDITION = 1;
	brw_end_read();

Quoted 4 lines

Quoted 2 lines

then the writer must see CONDITION != 0 after brw_start_write() ? (or vice-versa)

Yes, this is exactly my concern.

Oh, thanks at lot Paul (as always).

Quoted 8 lines

Quoted 5 lines

In this case we need the barrier, yes. Obviously brw_start_write() can return right after this_cpu_dec() and before wake_up_all().

2/2 doesn't need this guarantee but I agree, this doesn't look sane in gerenal...

Or name it something not containing "lock". And clearly document the behavior and how it is to be used. ;-)

this would be insane, I guess ;)

So. Ignoring the possible optimization you mentioned before, brw_end_read() should do:

	smp_mb();
	this_cpu_dec();

	wake_up_all();

And yes, we need the full mb(). wmb() is enough to ensure that the writer will see the memory modifications done by the reader. But we also need to ensure that any LOAD inside start_read/end_read can not be moved outside of the critical section.

But we should also ensure that "read" will see all modifications which were done under start_write/end_write. This means that brw_end_write() needs another synchronize_sched() before atomic_dec_and_test(), or brw_start_read() needs mb() in the fast-path.

Correct?

Ooooh. And I just noticed include/linux/percpu-rwsem.h which does something similar. Certainly it was not in my tree when I started this patch... percpu_down_write() doesn't allow multiple writers, but the main problem it uses msleep(1). It should not, I think.

But. It seems that percpu_up_write() is equally wrong? Doesn't it need synchronize_rcu() before "p->locked = false" ?

(add Mikulas)

Quoted 8 lines

Ooooh. And I just noticed include/linux/percpu-rwsem.h which does something similar. Certainly it was not in my tree when I started this patch... percpu_down_write() doesn't allow multiple writers, but the main problem it uses msleep(1). It should not, I think.

But. It seems that percpu_up_write() is equally wrong? Doesn't it need synchronize_rcu() before "p->locked = false" ?

Quoted 1 line

(add Mikulas)

Mikulas said something about doing an updated patch, so I figured I would look at his next version.

Thanx, Paul

Use rcu_read_lock_sched / rcu_read_unlock_sched / synchronize_sched instead of rcu_read_lock / rcu_read_unlock / synchronize_rcu.

This is an optimization. The RCU-protected region is very small, so there will be no latency problems if we disable preempt in this region.

So we use rcu_read_lock_sched / rcu_read_unlock_sched that translates to preempt_disable / preempt_disable. It is smaller (and supposedly faster) than preemptible rcu_read_lock / rcu_read_unlock.

Signed-off-by Mikulas Patocka <[email protected]>

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
	/*
	 * Decrement our count, but protected by RCU-sched so that
	 * the writer can force proper serialization.
	 */
	rcu_read_lock_sched();
	this_cpu_dec(*p->counters);
	rcu_read_unlock_sched();
}

Of course, it would be nice to get rid of the extra synchronize_sched(). One way to do this is to use SRCU, which allows blocking operations in its read-side critical sections (though also increasing read-side overhead a bit, and also untested):

------------------------------------------------------------------------

struct percpu_rw_semaphore {
	bool locked;
	struct mutex mtx; /* Could also be rw_semaphore. */
	struct srcu_struct s;
	wait_queue_head_t wq;
};

static inline void percpu_up_write(struct percpu_rw_semaphore *p)

{
	/* Allow others to proceed, but not yet locklessly. */
	mutex_unlock(&p->mtx);

	/*
	 * Ensure that all calls to percpu_down_read() that did not
	 * start unambiguously after the above mutex_unlock() still
	 * acquire the lock, forcing their critical sections to be
	 * serialized with the one terminated by this call to
	 * percpu_up_write().
	 */
	synchronize_sched();

Quoted 11 lines · Paul E. McKenney

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
	/*
	 * Decrement our count, but protected by RCU-sched so that
	 * the writer can force proper serialization.
	 */
	rcu_read_lock_sched();
	this_cpu_dec(*p->counters);
	rcu_read_unlock_sched();
}

Yes, the explicit lock/unlock makes the new assumptions about synchronize_sched && barriers unnecessary. And iiuc this could even written as

	rcu_read_lock_sched();
	rcu_read_unlock_sched();

	this_cpu_dec(*p->counters);

Quoted 5 lines

Of course, it would be nice to get rid of the extra synchronize_sched(). One way to do this is to use SRCU, which allows blocking operations in its read-side critical sections (though also increasing read-side overhead a bit, and also untested):

Quoted 8 lines

------------------------------------------------------------------------

struct percpu_rw_semaphore {
	bool locked;
	struct mutex mtx; /* Could also be rw_semaphore. */
	struct srcu_struct s;
	wait_queue_head_t wq;
};

but in this case I don't understand

Quoted 13 lines

static inline void percpu_up_write(struct percpu_rw_semaphore *p)

{
	/* Allow others to proceed, but not yet locklessly. */
	mutex_unlock(&p->mtx);

	/*
	 * Ensure that all calls to percpu_down_read() that did not
	 * start unambiguously after the above mutex_unlock() still
	 * acquire the lock, forcing their critical sections to be
	 * serialized with the one terminated by this call to
	 * percpu_up_write().
	 */
	synchronize_sched();

how this synchronize_sched() can help...

Quoted 17 lines · Oleg Nesterov

Quoted 11 lines · Paul E. McKenney

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
	/*
	 * Decrement our count, but protected by RCU-sched so that
	 * the writer can force proper serialization.
	 */
	rcu_read_lock_sched();
	this_cpu_dec(*p->counters);
	rcu_read_unlock_sched();
}

Yes, the explicit lock/unlock makes the new assumptions about synchronize_sched && barriers unnecessary. And iiuc this could even written as

Quoted 4 lines

	rcu_read_lock_sched();
	rcu_read_unlock_sched();

	this_cpu_dec(*p->counters);

But this would lose the memory barrier that is inserted by synchronize_sched() after the CPU's last RCU-sched read-side critical section.

Quoted 19 lines · Paul E. McKenney

Quoted 17 lines · Oleg Nesterov

Quoted 11 lines · Paul E. McKenney

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
	/*
	 * Decrement our count, but protected by RCU-sched so that
	 * the writer can force proper serialization.
	 */
	rcu_read_lock_sched();
	this_cpu_dec(*p->counters);
	rcu_read_unlock_sched();
}

Yes, the explicit lock/unlock makes the new assumptions about synchronize_sched && barriers unnecessary. And iiuc this could even written as

Quoted 8 lines

Quoted 4 lines

	rcu_read_lock_sched();
	rcu_read_unlock_sched();

	this_cpu_dec(*p->counters);

But this would lose the memory barrier that is inserted by synchronize_sched() after the CPU's last RCU-sched read-side critical section.

How? Afaics there is no need to synchronize with this_cpu_dec(), its result was already seen before the 2nd synchronize_sched() was called in percpu_down_write().

IOW, this memory barrier is only needed to synchronize with memory changes inside down_read/up_read.

To clarify, of course I do not suggest to write is this way. I am just trying to check my understanding.

Quoted 11 lines · Mikulas Patocka

Use rcu_read_lock_sched / rcu_read_unlock_sched / synchronize_sched instead of rcu_read_lock / rcu_read_unlock / synchronize_rcu.

This is an optimization. The RCU-protected region is very small, so there will be no latency problems if we disable preempt in this region.

So we use rcu_read_lock_sched / rcu_read_unlock_sched that translates to preempt_disable / preempt_disable. It is smaller (and supposedly faster) than preemptible rcu_read_lock / rcu_read_unlock.

Signed-off-by Mikulas Patocka <[email protected]>

OK, as promised/threatened, I finally got a chance to take a closer look.

The light_mb() and heavy_mb() definitions aren't doing much for me, the code would be cleared with them expanded inline. And while the approach of pairing barrier() with synchronize_sched() is interesting, it would be simpler to rely on RCU's properties. The key point is that if RCU cannot prove that a given RCU-sched read-side critical section is seen by all CPUs to have started after a given synchronize_sched(), then that synchronize_sched() must wait for that RCU-sched read-side critical section to complete.

Quoted 15 lines · Paul E. McKenney

Quoted 11 lines · Mikulas Patocka

Use rcu_read_lock_sched / rcu_read_unlock_sched / synchronize_sched instead of rcu_read_lock / rcu_read_unlock / synchronize_rcu.

This is an optimization. The RCU-protected region is very small, so there will be no latency problems if we disable preempt in this region.

So we use rcu_read_lock_sched / rcu_read_unlock_sched that translates to preempt_disable / preempt_disable. It is smaller (and supposedly faster) than preemptible rcu_read_lock / rcu_read_unlock.

Signed-off-by Mikulas Patocka <[email protected]>

OK, as promised/threatened, I finally got a chance to take a closer look.

Quoted 8 lines

The light_mb() and heavy_mb() definitions aren't doing much for me, the code would be cleared with them expanded inline. And while the approach of pairing barrier() with synchronize_sched() is interesting, it would be simpler to rely on RCU's properties. The key point is that if RCU cannot prove that a given RCU-sched read-side critical section is seen by all CPUs to have started after a given synchronize_sched(), then that synchronize_sched() must wait for that RCU-sched read-side critical section to complete.

Also note that you can define both light_mb() and heavy_mb() to be smp_mb() and slow down the reader path a bit and speed up the writer path.

On architectures with in-order memory access (and thus smp_mb() equals barrier()), it doesn't hurt the reader but helps the writer, for example:
#ifdef ARCH_HAS_INORDER_MEMORY_ACCESS
#define light_mb() smp_mb()
#define heavy_mb() smp_mb()
#else
#define light_mb() barrier()
#define heavy_mb() synchronize_sched()
#endif

Quoted 31 lines · Mikulas Patocka

Quoted 15 lines · Paul E. McKenney

Quoted 11 lines · Mikulas Patocka

Use rcu_read_lock_sched / rcu_read_unlock_sched / synchronize_sched instead of rcu_read_lock / rcu_read_unlock / synchronize_rcu.

This is an optimization. The RCU-protected region is very small, so there will be no latency problems if we disable preempt in this region.

So we use rcu_read_lock_sched / rcu_read_unlock_sched that translates to preempt_disable / preempt_disable. It is smaller (and supposedly faster) than preemptible rcu_read_lock / rcu_read_unlock.

Signed-off-by Mikulas Patocka <[email protected]>

OK, as promised/threatened, I finally got a chance to take a closer look.

Quoted 8 lines

The light_mb() and heavy_mb() definitions aren't doing much for me, the code would be cleared with them expanded inline. And while the approach of pairing barrier() with synchronize_sched() is interesting, it would be simpler to rely on RCU's properties. The key point is that if RCU cannot prove that a given RCU-sched read-side critical section is seen by all CPUs to have started after a given synchronize_sched(), then that synchronize_sched() must wait for that RCU-sched read-side critical section to complete.

Also note that you can define both light_mb() and heavy_mb() to be smp_mb() and slow down the reader path a bit and speed up the writer path.

Quoted 9 lines

On architectures with in-order memory access (and thus smp_mb() equals barrier()), it doesn't hurt the reader but helps the writer, for example:
#ifdef ARCH_HAS_INORDER_MEMORY_ACCESS
#define light_mb() smp_mb()
#define heavy_mb() smp_mb()
#else
#define light_mb() barrier()
#define heavy_mb() synchronize_sched()
#endif

Except that there are no systems running Linux with in-order memory access. Even x86 and s390 require a barrier instruction for smp_mb() on SMP=y builds.

Thanx, Paul

include/linux/percpu-rwsem.h +1 -12

 static inline void percpu_up_read(struct percpu_rw_semaphore *p)
 {
-	/*
-	 * On X86, write operation in this_cpu_dec serves as a memory unlock
-	 * barrier (i.e. memory accesses may be moved before the write, but
-	 * no memory accesses are moved past the write).
-	 * On other architectures this may not be the case, so we need smp_mb()
-	 * there.
-	 */
-#if defined(CONFIG_X86) && (!defined(CONFIG_X86_PPRO_FENCE) && !defined(CONFIG_X86_OOSTORE))
-	barrier();
-#else
-	smp_mb();
-#endif
+	light_mb(); /* B, between read of the data and write to p->counter, paired with C */
 	this_cpu_dec(*p->counters);
 }
 

Not really the comment, but the question...

Quoted 1 line · Mikulas Patocka

include/linux/percpu-rwsem.h static inline void percpu_down_read(stru · line 31

Quoted 9 lines

static inline void percpu_down_read(struct percpu_rw_semaphore *p) {

include/linux/percpu-rwsem.h +1 -0

 	rcu_read_lock();

@@ -24,22 +27,12 @@ static inline void percpu_down_read(stru
 	}
 	this_cpu_inc(*p->counters);
 	rcu_read_unlock();
+	light_mb(); /* A, between read of p->locked and read of data, paired with D */
 }

rcu_read_unlock() (or even preempt_enable) should have compiler barrier semantics... But I agree, this adds more documentation for free.

Quoted 19 lines

include/linux/percpu-rwsem.h +1 -12

 static inline void percpu_up_read(struct percpu_rw_semaphore *p)
 {
-	/*
-	 * On X86, write operation in this_cpu_dec serves as a memory unlock
-	 * barrier (i.e. memory accesses may be moved before the write, but
-	 * no memory accesses are moved past the write).
-	 * On other architectures this may not be the case, so we need smp_mb()
-	 * there.
-	 */
-#if defined(CONFIG_X86) && (!defined(CONFIG_X86_PPRO_FENCE) && !defined(CONFIG_X86_OOSTORE))
-	barrier();
-#else
-	smp_mb();
-#endif
+	light_mb(); /* B, between read of the data and write to p->counter, paired with C */
 	this_cpu_dec(*p->counters);
 }
 

include/linux/percpu-rwsem.h static inline void percpu_down_write(str · line 57

Quoted 5 lines

include/linux/percpu-rwsem.h +1 -1

@@ -61,11 +54,12 @@ static inline void percpu_down_write(str
 	synchronize_rcu();
 	while (__percpu_count(p->counters))
 		msleep(1);
-	smp_rmb(); /* paired with smp_mb() in percpu_sem_up_read() */
+	heavy_mb(); /* C, between read of p->counter and write to data, paired with B */

I _think_ this is correct.

Just I am wondering if this is strongly correct in theory, I would really like to know what Paul thinks.

Ignoring the current implementation, according to the documentation synchronize_sched() has all rights to return immediately if there is no active rcu_read_lock_sched() section. If this were possible, than percpu_up_read() lacks mb.

So _perhaps_ it makes sense to document that synchronize_sched() also guarantees that all pending loads/stores on other CPUs should be completed upon return? Or I misunderstood the patch?

Quoted 4 lines · Oleg Nesterov

Not really the comment, but the question...

Quoted 1 line · Mikulas Patocka

Quoted 12 lines

include/linux/percpu-rwsem.h static inline void percpu_down_read(stru · line 31

Quoted 9 lines

static inline void percpu_down_read(struct percpu_rw_semaphore *p) {

include/linux/percpu-rwsem.h +1 -0

 	rcu_read_lock();

@@ -24,22 +27,12 @@ static inline void percpu_down_read(stru
 	}
 	this_cpu_inc(*p->counters);
 	rcu_read_unlock();
+	light_mb(); /* A, between read of p->locked and read of data, paired with D */
 }

rcu_read_unlock() (or even preempt_enable) should have compiler barrier semantics... But I agree, this adds more documentation for free.

Although rcu_read_lock() does have compiler-barrier semantics if CONFIG_PREEMPT=y, it does not for CONFIG_PREEMPT=n. So the light_mb() (which appears to be barrier()) is needed in that case.

Quoted 4 lines

Ignoring the current implementation, according to the documentation synchronize_sched() has all rights to return immediately if there is no active rcu_read_lock_sched() section. If this were possible, than percpu_up_read() lacks mb.

Even if there happen to be no RCU-sched read-side critical sections at the current instant, synchronize_sched() is required to make sure that everyone agrees that whatever code is executed by the caller after synchronize_sched() returns happens after any of the preceding RCU read-side critical sections.

So, if we have this, with x==0 initially:

	Task 0					Task 1

						rcu_read_lock_sched();
						x = 1;
						rcu_read_unlock_sched();
	synchronize_sched();
	r1 = x;

Then the value of r1 had better be one.

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section whose beginning
* preceded the call to synchronize_sched(). Note that this guarantee
* includes CPUs that are offline, idle, or executing in user mode, as
* well as CPUs that are executing in the kernel. Furthermore, if CPU A
* invoked synchronize_sched(), which returned to its caller on CPU B,
* then both CPU A and CPU B are guaranteed to have executed a full memory
* barrier during the execution of synchronize_sched().

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

But this patch needs more? Or I misunderstood. There is no RCU unlock in percpu_up_read().

IOW. Suppose the code does

	percpu_down_read();
	x = PROTECTED_BY_THIS_RW_SEM;
	percpu_up_read();

Withoit mb() the load above can be reordered with this_cpu_dec() in percpu_up_read().

However, we do not care if we can guarantee that the next percpu_down_write() can not return (iow, the next "write" section can not start) until this load is complete.

And I _think_ that another synchronize_sched() in percpu_down_write() added by this patch should work.

But, "since the end of its last RCU read-side critical section" does not look enough.

Or I misundersood you/Mikulas/both ?

Quoted 6 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

Quoted 3 lines

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Quoted 16 lines

But this patch needs more? Or I misunderstood. There is no RCU unlock in percpu_up_read().

IOW. Suppose the code does

	percpu_down_read();
	x = PROTECTED_BY_THIS_RW_SEM;
	percpu_up_read();

Withoit mb() the load above can be reordered with this_cpu_dec() in percpu_up_read().

However, we do not care if we can guarantee that the next percpu_down_write() can not return (iow, the next "write" section can not start) until this load is complete.

Quoted 7 lines

And I _think_ that another synchronize_sched() in percpu_down_write() added by this patch should work.

But, "since the end of its last RCU read-side critical section" does not look enough.

Or I misundersood you/Mikulas/both ?

I clearly need to look more carefully at Mikulas's code...

Thanx, Paul

Quoted 7 lines · Paul E. McKenney

Quoted 6 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

Quoted 8 lines

Quoted 3 lines

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

And I should hasten to add that for synchronize_sched(), disabling preemption (including disabling irqs, further including NMI handlers) acts as an RCU-sched read-side critical section. (This is in the comment header for synchronize_sched() up above my addition to it.)

Thanx, Paul

Quoted 12 lines · Paul E. McKenney

Quoted 11 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

Quoted 4 lines

Quoted 4 lines

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Or you can write "each CPU that is executing a kernel code is guaranteed to have executed a full memory barrier".

It would be consistent with the current implementation and it would make it possible to use

barrier()-synchronize_sched() as biased memory barriers.

---

In percpu-rwlocks, CPU 1 executes

...make some writes in the critical section...
barrier();
this_cpu_dec(*p->counters);

and the CPU 2 executes

while (__percpu_count(p->counters))

	msleep(1);

synchronize_sched();

So, when CPU 2 finishes synchronize_sched(), we must make sure that all writes done by CPU 1 are visible to CPU 2.

The current implementation fulfills this requirement, you can just add it to the specification so that whoever changes the implementation keeps it.

Mikulas

Quoted 6 lines

And I should hasten to add that for synchronize_sched(), disabling preemption (including disabling irqs, further including NMI handlers) acts as an RCU-sched read-side critical section. (This is in the comment header for synchronize_sched() up above my addition to it.)

Thanx, Paul

Quoted 21 lines · Mikulas Patocka

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Quoted 2 lines

Or you can write "each CPU that is executing a kernel code is guaranteed to have executed a full memory barrier".

Perhaps I could, but it isn't needed, nor is it particularly helpful. Please see suggestions in preceding email.

Quoted 2 lines

The current implementation fulfills this requirement, you can just add it to the specification so that whoever changes the implementation keeps it.

I will consider doing that if and when someone shows me a situation where adding that requirement makes things simpler and/or faster. From what I can see, your example does not do so.

Thanx, Paul

Quoted 22 lines · Paul E. McKenney

Quoted 21 lines · Mikulas Patocka

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Quoted 5 lines

Quoted 2 lines

Or you can write "each CPU that is executing a kernel code is guaranteed to have executed a full memory barrier".

Perhaps I could, but it isn't needed, nor is it particularly helpful. Please see suggestions in preceding email.

It is helpful, because if you add this requirement (that already holds for the current implementation), you can drop rcu_read_lock_sched() and rcu_read_unlock_sched() from the following code that you submitted.

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
        /*
         * Decrement our count, but protected by RCU-sched so that
         * the writer can force proper serialization.
         */
        rcu_read_lock_sched();
        this_cpu_dec(*p->counters);
        rcu_read_unlock_sched();
}

Quoted 7 lines

Quoted 2 lines

The current implementation fulfills this requirement, you can just add it to the specification so that whoever changes the implementation keeps it.

I will consider doing that if and when someone shows me a situation where adding that requirement makes things simpler and/or faster. From what I can see, your example does not do so.

Quoted 1 line

Thanx, Paul

If you do, the above code can be simplified to:

{
	barrier();
	this_cpu_dec(*p->counters);
}

Quoted 54 lines · Mikulas Patocka

Quoted 22 lines · Paul E. McKenney

Quoted 21 lines · Mikulas Patocka

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Quoted 5 lines

Quoted 2 lines

Or you can write "each CPU that is executing a kernel code is guaranteed to have executed a full memory barrier".

Perhaps I could, but it isn't needed, nor is it particularly helpful. Please see suggestions in preceding email.

It is helpful, because if you add this requirement (that already holds for the current implementation), you can drop rcu_read_lock_sched() and rcu_read_unlock_sched() from the following code that you submitted.

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
        /*
         * Decrement our count, but protected by RCU-sched so that
         * the writer can force proper serialization.
         */
        rcu_read_lock_sched();
        this_cpu_dec(*p->counters);
        rcu_read_unlock_sched();
}

Quoted 7 lines

Quoted 2 lines

The current implementation fulfills this requirement, you can just add it to the specification so that whoever changes the implementation keeps it.

I will consider doing that if and when someone shows me a situation where adding that requirement makes things simpler and/or faster. From what I can see, your example does not do so.

Quoted 7 lines

Quoted 1 line

Thanx, Paul

If you do, the above code can be simplified to:

{
	barrier();
	this_cpu_dec(*p->counters);
}

The readers are lightweight enough that you are worried about the overhead of rcu_read_lock_sched() and rcu_read_unlock_sched()? Really???

Thanx, Paul

Quoted 63 lines · Paul E. McKenney

Quoted 61 lines · Mikulas Patocka

Quoted 22 lines · Paul E. McKenney

Quoted 21 lines · Mikulas Patocka

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Quoted 5 lines

Quoted 2 lines

Or you can write "each CPU that is executing a kernel code is guaranteed to have executed a full memory barrier".

Perhaps I could, but it isn't needed, nor is it particularly helpful. Please see suggestions in preceding email.

It is helpful, because if you add this requirement (that already holds for the current implementation), you can drop rcu_read_lock_sched() and rcu_read_unlock_sched() from the following code that you submitted.

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
        /*
         * Decrement our count, but protected by RCU-sched so that
         * the writer can force proper serialization.
         */
        rcu_read_lock_sched();
        this_cpu_dec(*p->counters);
        rcu_read_unlock_sched();
}

Quoted 8 lines

Quoted 2 lines

The current implementation fulfills this requirement, you can just add it to the specification so that whoever changes the implementation keeps it.

I will consider doing that if and when someone shows me a situation where adding that requirement makes things simpler and/or faster. From what I can see, your example does not do so.

Thanx, Paul

If you do, the above code can be simplified to:

{
	barrier();
	this_cpu_dec(*p->counters);
}

Quoted 4 lines

The readers are lightweight enough that you are worried about the overhead of rcu_read_lock_sched() and rcu_read_unlock_sched()? Really???

Thanx, Paul

There was no lock in previous kernels, so we should make it as simple as possible. Disabling and reenabling preemption is probably not a big deal, but if don't have to do it, why do it?

Quoted 70 lines · Mikulas Patocka

Quoted 66 lines · Paul E. McKenney

Quoted 54 lines · Mikulas Patocka

Quoted 22 lines · Paul E. McKenney

Quoted 21 lines · Mikulas Patocka

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Quoted 5 lines

Quoted 2 lines

Or you can write "each CPU that is executing a kernel code is guaranteed to have executed a full memory barrier".

Perhaps I could, but it isn't needed, nor is it particularly helpful. Please see suggestions in preceding email.

It is helpful, because if you add this requirement (that already holds for the current implementation), you can drop rcu_read_lock_sched() and rcu_read_unlock_sched() from the following code that you submitted.

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
        /*
         * Decrement our count, but protected by RCU-sched so that
         * the writer can force proper serialization.
         */
        rcu_read_lock_sched();
        this_cpu_dec(*p->counters);
        rcu_read_unlock_sched();
}

Quoted 7 lines

Quoted 2 lines

The current implementation fulfills this requirement, you can just add it to the specification so that whoever changes the implementation keeps it.

I will consider doing that if and when someone shows me a situation where adding that requirement makes things simpler and/or faster. From what I can see, your example does not do so.

Quoted 7 lines

Quoted 1 line

Thanx, Paul

If you do, the above code can be simplified to:

{
	barrier();
	this_cpu_dec(*p->counters);
}

The readers are lightweight enough that you are worried about the overhead of rcu_read_lock_sched() and rcu_read_unlock_sched()? Really???

Quoted 5 lines

Quoted 1 line

Thanx, Paul

There was no lock in previous kernels, so we should make it as simple as possible. Disabling and reenabling preemption is probably not a big deal, but if don't have to do it, why do it?

Because I don't consider the barrier()-paired-with-synchronize_sched() to be a simplification.

While we are discussing this, I have been assuming that readers must block from time to time. Is this the case?

Quoted 70 lines · Mikulas Patocka

Quoted 66 lines · Paul E. McKenney

Quoted 54 lines · Mikulas Patocka

Quoted 22 lines · Paul E. McKenney

Quoted 21 lines · Mikulas Patocka

Quoted 16 lines · Paul E. McKenney

Quoted 15 lines · Paul E. McKenney

Quoted 9 lines · Oleg Nesterov

Quoted 5 lines · Paul E. McKenney

* Note that this guarantee implies a further memory-ordering guarantee.
* On systems with more than one CPU, when synchronize_sched() returns,
* each CPU is guaranteed to have executed a full memory barrier since
* the end of its last RCU read-side critical section

         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Ah wait... I misread this comment.

And I miswrote it. It should say "since the end of its last RCU-sched read-side critical section." So, for example, RCU-sched need not force a CPU that is idle, offline, or (eventually) executing in user mode to execute a memory barrier. Fixed this.

Quoted 5 lines

Quoted 2 lines

Or you can write "each CPU that is executing a kernel code is guaranteed to have executed a full memory barrier".

Perhaps I could, but it isn't needed, nor is it particularly helpful. Please see suggestions in preceding email.

It is helpful, because if you add this requirement (that already holds for the current implementation), you can drop rcu_read_lock_sched() and rcu_read_unlock_sched() from the following code that you submitted.

static inline void percpu_up_read(struct percpu_rw_semaphore *p)

{
        /*
         * Decrement our count, but protected by RCU-sched so that
         * the writer can force proper serialization.
         */
        rcu_read_lock_sched();
        this_cpu_dec(*p->counters);
        rcu_read_unlock_sched();
}

Quoted 7 lines

Quoted 2 lines

The current implementation fulfills this requirement, you can just add it to the specification so that whoever changes the implementation keeps it.

I will consider doing that if and when someone shows me a situation where adding that requirement makes things simpler and/or faster. From what I can see, your example does not do so.

Quoted 7 lines

Quoted 1 line

Thanx, Paul

If you do, the above code can be simplified to:

{
	barrier();
	this_cpu_dec(*p->counters);
}

The readers are lightweight enough that you are worried about the overhead of rcu_read_lock_sched() and rcu_read_unlock_sched()? Really???

Quoted 5 lines

Quoted 1 line

Thanx, Paul

There was no lock in previous kernels, so we should make it as simple as possible. Disabling and reenabling preemption is probably not a big deal, but if don't have to do it, why do it?

Because I don't consider the barrier()-paired-with-synchronize_sched() to be a simplification.

While we are discussing this, I have been assuming that readers must block from time to time. Is this the case?

Thanx, Paul

Not really the comment, but the question...

I have to admit, I have
no idea how much cli/sti is slower compared to preempt_disable/enable.

        static void mb_ipi(void *arg)
        {
                smp_mb(); /* unneeded ? */
        }

        static void force_mb_on_each_cpu(void)
        {
                smp_mb();
                smp_call_function(mb_ipi, NULL, 1);
        } 

Quoted 11 lines · Oleg Nesterov

        static void mb_ipi(void *arg)
        {
                smp_mb(); /* unneeded ? */
        }

        static void force_mb_on_each_cpu(void)
        {
                smp_mb();
                smp_call_function(mb_ipi, NULL, 1);
        }

You know we're spending an awful lot of time and effort to get rid of such things, right? RT and HPC people absolutely hate these random IPI things.

Quoted 3 lines

I have to admit, I have
no idea how much cli/sti is slower compared to preempt_disable/enable.

A lot.. esp on stupid hardware (insert pentium-4 reference), but I think its more expensive for pretty much all hardware,

Quoted 2 lines · Oleg Nesterov

Not really the comment, but the question...

Damn. And another question.

Mikulas, I am sorry for this (almost) off-topic noise. Let me repeat just in case that I am not arguing with your patches.

So write_lock/write_unlock needs to call synchronize_sched() 3 times. I am wondering if it makes any sense to try to make it a bit heavier but faster.

What if we change the reader to use local_irq_disable/enable around this_cpu_inc/dec (instead of rcu read lock)? I have to admit, I have no idea how much cli/sti is slower compared to preempt_disable/enable.

Then the writer can use

	static void mb_ipi(void *arg)
	{
		smp_mb(); /* unneeded ? */
	}

	static void force_mb_on_each_cpu(void)
	{
		smp_mb();
		smp_call_function(mb_ipi, NULL, 1);
	}

to a) synchronise with irq_disable and b) to insert the necessary mb's.

Of course smp_call_function() means more work for each CPU, but write_lock() should be rare...

This can also wakeup the idle CPU's, but probably we can do on_each_cpu_cond(cond_func => !idle_cpu). Perhaps cond_func() can also return false if rcu_user_enter() was called...

Actually I was thinking about this from the very beginning, but I do not feel this looks like a good idea. Still I'd like to ask what do you think.

Oleg.

Quoted 5 lines

Quoted 5 lines

Ooooh. And I just noticed include/linux/percpu-rwsem.h which does something similar. Certainly it was not in my tree when I started this patch... percpu_down_write() doesn't allow multiple writers, but the main problem it uses msleep(1). It should not, I think.

Quoted 8 lines

Quoted 4 lines

But. It seems that percpu_up_write() is equally wrong? Doesn't it need synchronize_rcu() before "p->locked = false" ?

(add Mikulas)

Mikulas said something about doing an updated patch, so I figured I would look at his next version.

Quoted 1 line

Thanx, Paul

The best ideas proposed in this thread are:

Using heavy/light barries by Lai Jiangshan.

So. down_write/up_right does msleep() and it needs to call synchronize_sched() 3 times.

This looks too much. It is not that I am worried about the writers, the problem is that the new readers are blocked completely while the writer sleeps in msleep/synchronize_sched.

Paul, Mikulas, et al. Could you please look at the new implementation below? Completely untested/uncompiled, just for discussion.

Currently the writer does msleep() plus synchronize_sched() 3 times to acquire/release the semaphore, and during this time the readers are blocked completely. Even if the "write" section was not actually started or if it was already finished.

With this patch down_read/up_read does synchronize_sched() twice and down_read/up_read are still possible during this time, just they use the slow path.

Quoted 8 lines · Oleg Nesterov

Currently the writer does msleep() plus synchronize_sched() 3 times to acquire/release the semaphore, and during this time the readers are blocked completely. Even if the "write" section was not actually started or if it was already finished.

With this patch down_read/up_read does synchronize_sched() twice and down_read/up_read are still possible during this time, just they use the slow path.

The changelog is wrong (it's the write path, not read path, that does the synchronize_sched).

include/linux/percpu-rwsem.h line 10

Quoted 5 lines

struct percpu_rw_semaphore {

include/linux/percpu-rwsem.h +1 -3

-       unsigned __percpu *counters;
-       bool locked;
-       struct mutex mtx;
+       int __percpu            *fast_read_ctr;

This change is wrong.

You must not make the 'fast_read_ctr' thing be an int. Or at least you need to be a hell of a lot more careful about it.

Why?

Because the readers update the counters while possibly moving around cpu's, the increment and decrement of the counters may be on different CPU's. But that means that when you add all the counters together, things can overflow (only the final sum is meaningful). And THAT in turn means that you should not use a signed count, for the simple reason that signed integers don't have well-behaved overflow behavior in C.

Now, I doubt you'll find an architecture or C compiler where this will actually ever make a difference, but the fact remains that you shouldn't use signed integers for counters like this. You should use unsigned, and you should rely on the well-defined modulo-2**n semantics.

I'd also like to see a comment somewhere in the source code about the whole algorithm and the rules.

Other than that, I guess it looks ok.

Linus

Quoted 4 lines · Oleg Nesterov

With this patch down_read/up_read does synchronize_sched() twice and down_read/up_read are still possible during this time, just they use the slow path.

The changelog is wrong (it's the write path, not read path, that does the synchronize_sched).

include/linux/percpu-rwsem.h line 10

Quoted 5 lines

struct percpu_rw_semaphore {

include/linux/percpu-rwsem.h +1 -3

-       unsigned __percpu *counters;
-       bool locked;
-       struct mutex mtx;
+       int __percpu            *fast_read_ctr;

This change is wrong.

You must not make the 'fast_read_ctr' thing be an int. Or at least you need to be a hell of a lot more careful about it.

Why?

Because the readers update the counters while possibly moving around cpu's, the increment and decrement of the counters may be on different CPU's. But that means that when you add all the counters together, things can overflow (only the final sum is meaningful). And THAT in turn means that you should not use a signed count, for the simple reason that signed integers don't have well-behaved overflow behavior in C.

Now, I doubt you'll find an architecture or C compiler where this will actually ever make a difference,

but the fact remains that you
shouldn't use signed integers for counters like this. You should use unsigned, and you should rely on the well-defined modulo-2**n semantics.

I'd also like to see a comment somewhere in the source code about the whole algorithm and the rules.

Other than that, I guess it looks ok.

It looks sensible.

Here I'm sending an improvement of the patch - I changed it so that there are not two-level nested functions for the fast path and so that both percpu_down_read and percpu_up_read use the same piece of code (to reduce cache footprint).

Currently the writer does msleep() plus synchronize_sched() 3 times to acquire/release the semaphore, and during this time the readers are blocked completely. Even if the "write" section was not actually started or if it was already finished.

With this patch down_write/up_write does synchronize_sched() twice and down_read/up_read are still possible during this time, just they use the slow path.

percpu_down_write() first forces the readers to use rw_semaphore and increment the "slow" counter to take the lock for reading, then it takes that rw_semaphore for writing and blocks the readers.

Also. With this patch the code relies on the documented behaviour of synchronize_sched(), it doesn't try to pair synchronize_sched() with barrier.

Signed-off-by Oleg Nesterov <[email protected]>

Signed-off-by Mikulas Patocka <[email protected]>

---
 include/linux/percpu-rwsem.h |   80 ++++++-------------------------
 lib/Makefile                 |    2 
 lib/percpu-rwsem.c           |  110 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 127 insertions(+), 65 deletions(-)
 create mode 100644 lib/percpu-rwsem.c

Index: linux-3.6.6-fast/include/linux/percpu-rwsem.h
===================================================================

include/linux/percpu-rwsem.h +16 -64

@@ -2,82 +2,34 @@
 #define _LINUX_PERCPU_RWSEM_H
 
 #include <linux/mutex.h>
+#include <linux/rwsem.h>
 #include <linux/percpu.h>
-#include <linux/rcupdate.h>
-#include <linux/delay.h>
+#include <linux/wait.h>
 
 struct percpu_rw_semaphore {
-	unsigned __percpu *counters;
-	bool locked;
-	struct mutex mtx;
+	unsigned int __percpu	*fast_read_ctr;
+	struct mutex		writer_mutex;
+	struct rw_semaphore	rw_sem;
+	atomic_t		slow_read_ctr;
+	wait_queue_head_t	write_waitq;
 };
 
-#define light_mb()	barrier()
-#define heavy_mb()	synchronize_sched()
+extern void __percpu_down_up_read(struct percpu_rw_semaphore *, int);
 
-static inline void percpu_down_read(struct percpu_rw_semaphore *p)
-{
-	rcu_read_lock_sched();
-	if (unlikely(p->locked)) {
-		rcu_read_unlock_sched();
-		mutex_lock(&p->mtx);
-		this_cpu_inc(*p->counters);
-		mutex_unlock(&p->mtx);
-		return;
-	}
-	this_cpu_inc(*p->counters);
-	rcu_read_unlock_sched();
-	light_mb(); /* A, between read of p->locked and read of data, paired with D */
-}
-
-static inline void percpu_up_read(struct percpu_rw_semaphore *p)
-{
-	light_mb(); /* B, between read of the data and write to p->counter, paired with C */
-	this_cpu_dec(*p->counters);
-}
-
-static inline unsigned __percpu_count(unsigned __percpu *counters)
-{
-	unsigned total = 0;
-	int cpu;
-
-	for_each_possible_cpu(cpu)
-		total += ACCESS_ONCE(*per_cpu_ptr(counters, cpu));
+extern void percpu_down_write(struct percpu_rw_semaphore *);
+extern void percpu_up_write(struct percpu_rw_semaphore *);
 
-	return total;
-}
-
-static inline void percpu_down_write(struct percpu_rw_semaphore *p)
-{
-	mutex_lock(&p->mtx);
-	p->locked = true;
-	synchronize_sched(); /* make sure that all readers exit the rcu_read_lock_sched region */
-	while (__percpu_count(p->counters))
-		msleep(1);
-	heavy_mb(); /* C, between read of p->counter and write to data, paired with B */
-}
-
-static inline void percpu_up_write(struct percpu_rw_semaphore *p)
-{
-	heavy_mb(); /* D, between write to data and write to p->locked, paired with A */
-	p->locked = false;
-	mutex_unlock(&p->mtx);
-}
+extern int percpu_init_rwsem(struct percpu_rw_semaphore *);
+extern void percpu_free_rwsem(struct percpu_rw_semaphore *);
 
-static inline int percpu_init_rwsem(struct percpu_rw_semaphore *p)
+static inline void percpu_down_read(struct percpu_rw_semaphore *s)
 {
-	p->counters = alloc_percpu(unsigned);
-	if (unlikely(!p->counters))
-		return -ENOMEM;
-	p->locked = false;
-	mutex_init(&p->mtx);
-	return 0;
+	__percpu_down_up_read(s, 1);
 }
 
-static inline void percpu_free_rwsem(struct percpu_rw_semaphore *p)
+static inline void percpu_up_read(struct percpu_rw_semaphore *s)
 {
-	free_percpu(p->counters);
-	p->counters = NULL; /* catch use after free bugs */
+	__percpu_down_up_read(s, -1);
 }
 
 #endif

Index: linux-3.6.6-fast/lib/Makefile
===================================================================

lib/Makefile +1 -1

@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
 	 idr.o int_sqrt.o extable.o prio_tree.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
+	 is_single_threaded.o plist.o decompress.o percpu-rwsem.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o

Index: linux-3.6.6-fast/lib/percpu-rwsem.c
===================================================================

lib/percpu-rwsem.c new file +110 -0

@@ -0,0 +1,110 @@
+#include <linux/percpu-rwsem.h>
+#include <linux/rcupdate.h>
+#include <linux/sched.h>
+#include <linux/module.h>
+
+int percpu_init_rwsem(struct percpu_rw_semaphore *brw)
+{
+	brw->fast_read_ctr = alloc_percpu(int);
+	if (unlikely(!brw->fast_read_ctr))
+		return -ENOMEM;
+
+	mutex_init(&brw->writer_mutex);
+	init_rwsem(&brw->rw_sem);
+	atomic_set(&brw->slow_read_ctr, 0);
+	init_waitqueue_head(&brw->write_waitq);
+	return 0;
+}
+EXPORT_SYMBOL(percpu_init_rwsem);
+
+void percpu_free_rwsem(struct percpu_rw_semaphore *brw)
+{
+	free_percpu(brw->fast_read_ctr);
+	brw->fast_read_ctr = NULL; /* catch use after free bugs */
+}
+EXPORT_SYMBOL(percpu_free_rwsem);
+
+void __percpu_down_up_read(struct percpu_rw_semaphore *brw, int val)
+{
+	preempt_disable();
+	if (likely(!mutex_is_locked(&brw->writer_mutex))) {
+		__this_cpu_add(*brw->fast_read_ctr, val);
+		preempt_enable();
+		return;
+	}
+	preempt_enable();
+	if (val >= 0) {
+		down_read(&brw->rw_sem);
+		atomic_inc(&brw->slow_read_ctr);
+		up_read(&brw->rw_sem);
+	} else {
+		if (atomic_dec_and_test(&brw->slow_read_ctr))
+			wake_up_all(&brw->write_waitq);
+	}
+}
+EXPORT_SYMBOL(__percpu_down_up_read);
+
+static int clear_fast_ctr(struct percpu_rw_semaphore *brw)
+{
+	unsigned int sum = 0;
+	int cpu;
+
+	for_each_possible_cpu(cpu) {
+		sum += per_cpu(*brw->fast_read_ctr, cpu);
+		per_cpu(*brw->fast_read_ctr, cpu) = 0;
+	}
+
+	return sum;
+}
+
+/*
+ * 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().
+ *
+ * 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
+ * counter it represents the number of active readers.
+ *
+ * Finally the writer takes ->rw_sem for writing and blocks the new readers,
+ * then waits until the slow counter becomes zero.
+ */
+void percpu_down_write(struct percpu_rw_semaphore *brw)
+{
+	/* also blocks update_fast_ctr() which checks mutex_is_locked() */
+	mutex_lock(&brw->writer_mutex);
+
+	/*
+	 * 1. Ensures mutex_is_locked() 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
+	 *    update_fast_ctr().
+	 *
+	 * 3. Ensures that if any reader has exited its critical section via
+	 *    fast-path, it executes a full memory barrier before we return.
+	 */
+	synchronize_sched();
+
+	/* 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));
+}
+EXPORT_SYMBOL(percpu_down_write);
+
+void percpu_up_write(struct percpu_rw_semaphore *brw)
+{
+	/* allow the new readers, but only the slow-path */
+	up_write(&brw->rw_sem);
+
+	/* insert the barrier before the next fast-path in down_read */
+	synchronize_sched();
+
+	mutex_unlock(&brw->writer_mutex);
+}
+EXPORT_SYMBOL(percpu_up_write);

Quoted 7 lines · Mikulas Patocka

It looks sensible.

Here I'm sending an improvement of the patch - I changed it so that there are not two-level nested functions for the fast path and so that both percpu_down_read and percpu_up_read use the same piece of code (to reduce cache footprint).

IOW, the only change is that you eliminate "static update_fast_ctr()" and fold it into down/up_read which takes the additional argument.

Honestly, personally I do not think this is better, but I won't argue. I agree with everything but I guess we need the ack from Paul.

Quoted 12 lines · Oleg Nesterov

Quoted 7 lines · Mikulas Patocka

It looks sensible.

Here I'm sending an improvement of the patch - I changed it so that there are not two-level nested functions for the fast path and so that both percpu_down_read and percpu_up_read use the same piece of code (to reduce cache footprint).

IOW, the only change is that you eliminate "static update_fast_ctr()" and fold it into down/up_read which takes the additional argument.

Quoted 2 lines

Honestly, personally I do not think this is better, but I won't argue. I agree with everything but I guess we need the ack from Paul.

If you look at generated assembly (for x86-64), the footprint of my patch is 78 bytes shared for both percpu_down_read and percpu_up_read.

The footprint of your patch is 62 bytes for update_fast_ctr, 46 bytes for percpu_down_read and 20 bytes for percpu_up_read.

It looks sensible.

Here I'm sending an improvement of the patch - I changed it so that there are not two-level nested functions for the fast path and so that both percpu_down_read and percpu_up_read use the same piece of code (to reduce cache footprint).

---

Currently the writer does msleep() plus synchronize_sched() 3 times to acquire/release the semaphore, and during this time the readers are blocked completely. Even if the "write" section was not actually started or if it was already finished.

With this patch down_write/up_write does synchronize_sched() twice and down_read/up_read are still possible during this time, just they use the slow path.

percpu_down_write() first forces the readers to use rw_semaphore and increment the "slow" counter to take the lock for reading, then it takes that rw_semaphore for writing and blocks the readers.

Also. With this patch the code relies on the documented behaviour of synchronize_sched(), it doesn't try to pair synchronize_sched() with barrier.

Signed-off-by Oleg Nesterov <[email protected]>

Signed-off-by Mikulas Patocka <[email protected]>

From a memory-ordering viewpoint, this looks to me to work the same

---
 include/linux/percpu-rwsem.h |   80 ++++++-------------------------
 lib/Makefile                 |    2 
 lib/percpu-rwsem.c           |  110 +++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 127 insertions(+), 65 deletions(-)
 create mode 100644 lib/percpu-rwsem.c

Index: linux-3.6.6-fast/include/linux/percpu-rwsem.h
===================================================================

include/linux/percpu-rwsem.h +16 -64

@@ -2,82 +2,34 @@
 #define _LINUX_PERCPU_RWSEM_H
 
 #include <linux/mutex.h>
+#include <linux/rwsem.h>
 #include <linux/percpu.h>
-#include <linux/rcupdate.h>
-#include <linux/delay.h>
+#include <linux/wait.h>
 
 struct percpu_rw_semaphore {
-	unsigned __percpu *counters;
-	bool locked;
-	struct mutex mtx;
+	unsigned int __percpu	*fast_read_ctr;
+	struct mutex		writer_mutex;
+	struct rw_semaphore	rw_sem;
+	atomic_t		slow_read_ctr;
+	wait_queue_head_t	write_waitq;
 };
 
-#define light_mb()	barrier()
-#define heavy_mb()	synchronize_sched()
+extern void __percpu_down_up_read(struct percpu_rw_semaphore *, int);
 
-static inline void percpu_down_read(struct percpu_rw_semaphore *p)
-{
-	rcu_read_lock_sched();
-	if (unlikely(p->locked)) {
-		rcu_read_unlock_sched();
-		mutex_lock(&p->mtx);
-		this_cpu_inc(*p->counters);
-		mutex_unlock(&p->mtx);
-		return;
-	}
-	this_cpu_inc(*p->counters);
-	rcu_read_unlock_sched();
-	light_mb(); /* A, between read of p->locked and read of data, paired with D */
-}
-
-static inline void percpu_up_read(struct percpu_rw_semaphore *p)
-{
-	light_mb(); /* B, between read of the data and write to p->counter, paired with C */
-	this_cpu_dec(*p->counters);
-}
-
-static inline unsigned __percpu_count(unsigned __percpu *counters)
-{
-	unsigned total = 0;
-	int cpu;
-
-	for_each_possible_cpu(cpu)
-		total += ACCESS_ONCE(*per_cpu_ptr(counters, cpu));
+extern void percpu_down_write(struct percpu_rw_semaphore *);
+extern void percpu_up_write(struct percpu_rw_semaphore *);
 
-	return total;
-}
-
-static inline void percpu_down_write(struct percpu_rw_semaphore *p)
-{
-	mutex_lock(&p->mtx);
-	p->locked = true;
-	synchronize_sched(); /* make sure that all readers exit the rcu_read_lock_sched region */
-	while (__percpu_count(p->counters))
-		msleep(1);
-	heavy_mb(); /* C, between read of p->counter and write to data, paired with B */
-}
-
-static inline void percpu_up_write(struct percpu_rw_semaphore *p)
-{
-	heavy_mb(); /* D, between write to data and write to p->locked, paired with A */
-	p->locked = false;
-	mutex_unlock(&p->mtx);
-}
+extern int percpu_init_rwsem(struct percpu_rw_semaphore *);
+extern void percpu_free_rwsem(struct percpu_rw_semaphore *);
 
-static inline int percpu_init_rwsem(struct percpu_rw_semaphore *p)
+static inline void percpu_down_read(struct percpu_rw_semaphore *s)
 {
-	p->counters = alloc_percpu(unsigned);
-	if (unlikely(!p->counters))
-		return -ENOMEM;
-	p->locked = false;
-	mutex_init(&p->mtx);
-	return 0;
+	__percpu_down_up_read(s, 1);
 }
 
-static inline void percpu_free_rwsem(struct percpu_rw_semaphore *p)
+static inline void percpu_up_read(struct percpu_rw_semaphore *s)
 {
-	free_percpu(p->counters);
-	p->counters = NULL; /* catch use after free bugs */
+	__percpu_down_up_read(s, -1);
 }
 
 #endif

Index: linux-3.6.6-fast/lib/Makefile
===================================================================

lib/Makefile +1 -1

@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmd
 	 idr.o int_sqrt.o extable.o prio_tree.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
+	 is_single_threaded.o plist.o decompress.o percpu-rwsem.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o

Index: linux-3.6.6-fast/lib/percpu-rwsem.c
===================================================================

lib/percpu-rwsem.c new file +110 -0

@@ -0,0 +1,110 @@
+#include <linux/percpu-rwsem.h>
+#include <linux/rcupdate.h>
+#include <linux/sched.h>
+#include <linux/module.h>
+
+int percpu_init_rwsem(struct percpu_rw_semaphore *brw)
+{
+	brw->fast_read_ctr = alloc_percpu(int);
+	if (unlikely(!brw->fast_read_ctr))
+		return -ENOMEM;
+
+	mutex_init(&brw->writer_mutex);
+	init_rwsem(&brw->rw_sem);
+	atomic_set(&brw->slow_read_ctr, 0);
+	init_waitqueue_head(&brw->write_waitq);
+	return 0;
+}
+EXPORT_SYMBOL(percpu_init_rwsem);
+
+void percpu_free_rwsem(struct percpu_rw_semaphore *brw)
+{
+	free_percpu(brw->fast_read_ctr);
+	brw->fast_read_ctr = NULL; /* catch use after free bugs */
+}
+EXPORT_SYMBOL(percpu_free_rwsem);
+
+void __percpu_down_up_read(struct percpu_rw_semaphore *brw, int val)
+{
+	preempt_disable();
+	if (likely(!mutex_is_locked(&brw->writer_mutex))) {
+		__this_cpu_add(*brw->fast_read_ctr, val);
+		preempt_enable();
+		return;
+	}
+	preempt_enable();
+	if (val >= 0) {
+		down_read(&brw->rw_sem);
+		atomic_inc(&brw->slow_read_ctr);
+		up_read(&brw->rw_sem);
+	} else {
+		if (atomic_dec_and_test(&brw->slow_read_ctr))
+			wake_up_all(&brw->write_waitq);
+	}
+}
+EXPORT_SYMBOL(__percpu_down_up_read);
+
+static int clear_fast_ctr(struct percpu_rw_semaphore *brw)
+{
+	unsigned int sum = 0;
+	int cpu;
+
+	for_each_possible_cpu(cpu) {
+		sum += per_cpu(*brw->fast_read_ctr, cpu);
+		per_cpu(*brw->fast_read_ctr, cpu) = 0;
+	}
+
+	return sum;
+}
+
+/*
+ * 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().
+ *
+ * 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
+ * counter it represents the number of active readers.
+ *
+ * Finally the writer takes ->rw_sem for writing and blocks the new readers,
+ * then waits until the slow counter becomes zero.
+ */
+void percpu_down_write(struct percpu_rw_semaphore *brw)
+{
+	/* also blocks update_fast_ctr() which checks mutex_is_locked() */
+	mutex_lock(&brw->writer_mutex);
+
+	/*
+	 * 1. Ensures mutex_is_locked() 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
+	 *    update_fast_ctr().
+	 *
+	 * 3. Ensures that if any reader has exited its critical section via
+	 *    fast-path, it executes a full memory barrier before we return.
+	 */
+	synchronize_sched();
+
+	/* 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));
+}
+EXPORT_SYMBOL(percpu_down_write);
+
+void percpu_up_write(struct percpu_rw_semaphore *brw)
+{
+	/* allow the new readers, but only the slow-path */
+	up_write(&brw->rw_sem);
+
+	/* insert the barrier before the next fast-path in down_read */
+	synchronize_sched();
+
+	mutex_unlock(&brw->writer_mutex);
+}
+EXPORT_SYMBOL(percpu_up_write);

Currently the writer does msleep() plus synchronize_sched() 3 times to acquire/release the semaphore, and during this time the readers are blocked completely. Even if the "write" section was not actually started or if it was already finished.

With this patch down_write/up_write does synchronize_sched() twice and down_read/up_read are still possible during this time, just they use the slow path.

percpu_down_write() first forces the readers to use rw_semaphore and increment the "slow" counter to take the lock for reading, then it takes that rw_semaphore for writing and blocks the readers.

Also. With this patch the code relies on the documented behaviour of synchronize_sched(), it doesn't try to pair synchronize_sched() with barrier.

Signed-off-by Oleg Nesterov <[email protected]>

---
 include/linux/percpu-rwsem.h |   83 +++++------------------------
 lib/Makefile                 |    2 +-
 lib/percpu-rwsem.c           |  123 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 137 insertions(+), 71 deletions(-)
 create mode 100644 lib/percpu-rwsem.c

include/linux/percpu-rwsem.h +13 -70

index 250a4ac..592f0d6 100644
@@ -2,82 +2,25 @@
 #define _LINUX_PERCPU_RWSEM_H
 
 #include <linux/mutex.h>
+#include <linux/rwsem.h>
 #include <linux/percpu.h>
-#include <linux/rcupdate.h>
-#include <linux/delay.h>
+#include <linux/wait.h>
 
 struct percpu_rw_semaphore {
-	unsigned __percpu *counters;
-	bool locked;
-	struct mutex mtx;
+	unsigned int __percpu	*fast_read_ctr;
+	struct mutex		writer_mutex;
+	struct rw_semaphore	rw_sem;
+	atomic_t		slow_read_ctr;
+	wait_queue_head_t	write_waitq;
 };
 
-#define light_mb()	barrier()
-#define heavy_mb()	synchronize_sched()
+extern void percpu_down_read(struct percpu_rw_semaphore *);
+extern void percpu_up_read(struct percpu_rw_semaphore *);
 
-static inline void percpu_down_read(struct percpu_rw_semaphore *p)
-{
-	rcu_read_lock_sched();
-	if (unlikely(p->locked)) {
-		rcu_read_unlock_sched();
-		mutex_lock(&p->mtx);
-		this_cpu_inc(*p->counters);
-		mutex_unlock(&p->mtx);
-		return;
-	}
-	this_cpu_inc(*p->counters);
-	rcu_read_unlock_sched();
-	light_mb(); /* A, between read of p->locked and read of data, paired with D */
-}
+extern void percpu_down_write(struct percpu_rw_semaphore *);
+extern void percpu_up_write(struct percpu_rw_semaphore *);
 
-static inline void percpu_up_read(struct percpu_rw_semaphore *p)
-{
-	light_mb(); /* B, between read of the data and write to p->counter, paired with C */
-	this_cpu_dec(*p->counters);
-}
-
-static inline unsigned __percpu_count(unsigned __percpu *counters)
-{
-	unsigned total = 0;
-	int cpu;
-
-	for_each_possible_cpu(cpu)
-		total += ACCESS_ONCE(*per_cpu_ptr(counters, cpu));
-
-	return total;
-}
-
-static inline void percpu_down_write(struct percpu_rw_semaphore *p)
-{
-	mutex_lock(&p->mtx);
-	p->locked = true;
-	synchronize_sched(); /* make sure that all readers exit the rcu_read_lock_sched region */
-	while (__percpu_count(p->counters))
-		msleep(1);
-	heavy_mb(); /* C, between read of p->counter and write to data, paired with B */
-}
-
-static inline void percpu_up_write(struct percpu_rw_semaphore *p)
-{
-	heavy_mb(); /* D, between write to data and write to p->locked, paired with A */
-	p->locked = false;
-	mutex_unlock(&p->mtx);
-}
-
-static inline int percpu_init_rwsem(struct percpu_rw_semaphore *p)
-{
-	p->counters = alloc_percpu(unsigned);
-	if (unlikely(!p->counters))
-		return -ENOMEM;
-	p->locked = false;
-	mutex_init(&p->mtx);
-	return 0;
-}
-
-static inline void percpu_free_rwsem(struct percpu_rw_semaphore *p)
-{
-	free_percpu(p->counters);
-	p->counters = NULL; /* catch use after free bugs */
-}
+extern int percpu_init_rwsem(struct percpu_rw_semaphore *);
+extern void percpu_free_rwsem(struct percpu_rw_semaphore *);
 
 #endif

lib/Makefile +1 -1

index 821a162..4dad4a7 100644
@@ -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
+	 is_single_threaded.o plist.o decompress.o percpu-rwsem.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o

lib/percpu-rwsem.c new file +110 -0

new file mode 100644
index 0000000..0e3bc0f
@@ -0,0 +1,123 @@
+#include <linux/percpu-rwsem.h>
+#include <linux/rcupdate.h>
+#include <linux/sched.h>
+
+int percpu_init_rwsem(struct percpu_rw_semaphore *brw)
+{
+	brw->fast_read_ctr = alloc_percpu(int);
+	if (unlikely(!brw->fast_read_ctr))
+		return -ENOMEM;
+
+	mutex_init(&brw->writer_mutex);
+	init_rwsem(&brw->rw_sem);
+	atomic_set(&brw->slow_read_ctr, 0);
+	init_waitqueue_head(&brw->write_waitq);
+	return 0;
+}
+
+void percpu_free_rwsem(struct percpu_rw_semaphore *brw)
+{
+	free_percpu(brw->fast_read_ctr);
+	brw->fast_read_ctr = NULL; /* catch use after free bugs */
+}
+
+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))) {
+		__this_cpu_add(*brw->fast_read_ctr, val);
+		success = true;
+	}
+	preempt_enable();
+
+	return success;
+}
+
+/*
+ * Like the normal down_read() this is not recursive, the writer can
+ * come after the first percpu_down_read() and create the deadlock.
+ */
+void percpu_down_read(struct percpu_rw_semaphore *brw)
+{
+	if (likely(update_fast_ctr(brw, +1)))
+		return;
+
+	down_read(&brw->rw_sem);
+	atomic_inc(&brw->slow_read_ctr);
+	up_read(&brw->rw_sem);
+}
+
+void percpu_up_read(struct percpu_rw_semaphore *brw)
+{
+	if (likely(update_fast_ctr(brw, -1)))
+		return;
+
+	/* false-positive is possible but harmless */
+	if (atomic_dec_and_test(&brw->slow_read_ctr))
+		wake_up_all(&brw->write_waitq);
+}
+
+static int clear_fast_ctr(struct percpu_rw_semaphore *brw)
+{
+	unsigned int sum = 0;
+	int cpu;
+
+	for_each_possible_cpu(cpu) {
+		sum += per_cpu(*brw->fast_read_ctr, cpu);
+		per_cpu(*brw->fast_read_ctr, cpu) = 0;
+	}
+
+	return sum;
+}
+
+/*
+ * 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().
+ *
+ * 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
+ * counter it represents the number of active readers.
+ *
+ * Finally the writer takes ->rw_sem for writing and blocks the new readers,
+ * then waits until the slow counter becomes zero.
+ */
+void percpu_down_write(struct percpu_rw_semaphore *brw)
+{
+	/* also blocks update_fast_ctr() which checks mutex_is_locked() */
+	mutex_lock(&brw->writer_mutex);
+
+	/*
+	 * 1. Ensures mutex_is_locked() 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
+	 *    update_fast_ctr().
+	 *
+	 * 3. Ensures that if any reader has exited its critical section via
+	 *    fast-path, it executes a full memory barrier before we return.
+	 */
+	synchronize_sched();
+
+	/* 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() */