x86_64 : support atomic ops with 64 bits integer values

x86_64 add/sub atomic ops does not seems to accept integer values bigger than 32 bits as immediates. Intel's add/sub documentation specifies they have to be passed as registers.

http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Machine-Constraints.html#Machine-Constraints

states :

e
32-bit signed integer constant, or a symbolic reference known to fit that range (for immediate operands in sign-extending x86-64 instructions).
Z
32-bit unsigned integer constant, or a symbolic reference known to fit that range (for immediate operands in zero-extending x86-64 instructions).

Since add/sub does sign extension, using the "e" constraint seems appropriate.

It applies to 2.6.27-rc, 2.6.26, 2.6.25...

---
 include/asm-x86/atomic_64.h |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

Index: linux-2.6-lttng/include/asm-x86/atomic_64.h
===================================================================
@@ -228,7 +228,7 @@ static inline void atomic64_add(long i, 
 {
 	asm volatile(LOCK_PREFIX "addq %1,%0"
 		     : "=m" (v->counter)
-		     : "ir" (i), "m" (v->counter));
+		     : "er" (i), "m" (v->counter));
 }
 
 /**

@@ -242,7 +242,7 @@ static inline void atomic64_sub(long i, 
 {
 	asm volatile(LOCK_PREFIX "subq %1,%0"
 		     : "=m" (v->counter)
-		     : "ir" (i), "m" (v->counter));
+		     : "er" (i), "m" (v->counter));
 }
 
 /**

@@ -260,7 +260,7 @@ static inline int atomic64_sub_and_test(
 
 	asm volatile(LOCK_PREFIX "subq %2,%0; sete %1"
 		     : "=m" (v->counter), "=qm" (c)
-		     : "ir" (i), "m" (v->counter) : "memory");
+	  	     : "er" (i), "m" (v->counter) : "memory");
 	return c;
 }
 

@@ -341,7 +341,7 @@ static inline int atomic64_add_negative(
 
 	asm volatile(LOCK_PREFIX "addq %2,%0; sets %1"
 		     : "=m" (v->counter), "=qm" (c)
-		     : "ir" (i), "m" (v->counter) : "memory");
+		     : "er" (i), "m" (v->counter) : "memory");
 	return c;
 }
 

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

This is correct; this is in fact true for all instructions except "mov".

Whether it's sign- or zero-extending is sometimes subtle, but not in these cases.

Do you happen to know if this is a manifest bug in the current kernel (i.e. if there is anywhere we're using more than ±2 GB as a constant to these functions?)

Either way, I'll queue this up to tip:x86/urgent if Ingo hasn't already since this is a pure bug fix.

-hpa

No, I did not hit this on current kernel code and the effect is quite esasy to detect : the assembler spits an error.

I have hit this problem when tying to implement a better rwlock design than is currently in the mainline kernel (I know the RT kernel has a hard time with rwlocks), and had to play with add/sub of large values. The idea is to bring down the interrupt latency caused by rwlocks shared between fast read-side interrupt handlers and slow thread context read-sides (tasklist_lock is the perfect example). In that case, the worse case interrupt latency is caused by the irq-disabled writer lock when contended by the slow readers. I will probably post a RFC about this in a near future.

Mathieu

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Have you looked at my sleping rwlock trial thing?

It's very different from a spinning one, but I think the fast path should be identical, and that's the one I tried to make fairly optimal.

See

http://git.kernel.org/?p=linux/kernel/git/torvalds/rwlock.git;a=summary

for a git tree. The sleeping version has two extra words for the sleep events, but those would be irrelevant for the spinning version.

The fastpath is

	movl $4,%eax
	lock ; xaddl %eax,(%rdi)
	testl $3,%eax
	jne __my_rwlock_rdlock

for the read-lock (the two low bits are contention bits, so you can make contention have any behaviour you want - including fairish, prefer-reads, or prefer-writes).

The write fastpath is

	xorl %eax,%eax
	movl $1,%edx
	lock ; cmpxchgl %edx,(%rdi)
	jne __my_rwlock_wrlock

and the "unlock" case is actually unnecessarily complex in my implementation, because it needs to

- wake things up in case of a conflict (not true of a spinning version, of course)
- it's pthreads-compatible, so the same function needs to handle both a read-unlock and a write-unlock.

but a spinning version should be much simpler.

Anyway, I haven't tried turning it into a spinning version, but it was very much designed to

- work with both 32-bit and 64-bit x86 by making the fastpath only do 32-bit locked accesses
- have any number of pending readers/writers (which is not a big deal for a spinning one, but at least there are no CPU count overflows).
- and because it is designed for sleeping, I'm pretty sure that you can easily drop interrupts in the contention path, to make write_lock_irq[save]() be reasonable.

In particular, the third bullet is the important one: because it's designed to have a "contention" path that has _extra_ information for the contended case, you could literally make the extra information have things like a list of pending writers, so that you can drop interrupts on one CPU, while you adding information to let the reader side know that if the read-lock happens on that CPU, it needs to be able to continue in order to not deadlock.

Linus

[...]

No, I just had a look at it, thanks for the pointer!

Tweakable contention behavior seems interesting, but I don't think it deals with the fact that on a mainline kernel, when an interrupt handler comes in and asks for a read lock, it has to get it on the spot. (RT kernels can get away with that using threaded threaded interrupts, but that's a completely different scheme). Therefore, the impact is that interrupts must be disabled around write lock usage, and we end up in the situation where this interrupt disable section can last for a long time, given it waits for every readers (including ones which does not disable interrupts nor softirqs) to complete.

Actually, I just used LTTng traces and eventually made a small patch to lockdep to detect whenever a spinlock or a rwlock is used both with interrupts enabled and disabled. Those sites are likely to produce very high latencies and should IMHO be considered as bogus. The basic bogus scenario is to have a spinlock held on CPU A with interrupts enabled being interrupted and then a softirq runs. On CPU B, the same lock is acquired with interrupts off. We therefore disable interrupts on CPU B for the duration of the softirq currently running on the CPU A, which is really not something that helps keeping short latencies. My preliminary results shows that there are a lot of inconsistent spinlock/rwlock irq on/off uses in the kernel.

This kind of scenario is pretty easy to fix for spinlocks (either move the interrupt disable within the spinlock section if the spinlock is never used by an interrupt handler or make sure that every users has interrupts disabled).

The problem comes with rwlocks : it is correct to have readers both with and without irq disable, even when interrupt handlers use the read lock. However, the write lock has to disable interrupt in that case, and we suffer from the high latency I pointed out. The tasklist_lock is the perfect example of this. In the following patch, I try to address this issue.

The core idea is this :

This "fair" rwlock locks out the threads first, then disables softirqs, then locks out the softirqs, then disables irqs and locks out softirqs. Only then is the writer allowed to modify the data structure.

A spinlock is used to insure writer mutual exclusion.

The test module is available at :

http://ltt.polymtl.ca/svn/trunk/tests/kernel/test-fair-rwlock.c

---
 include/linux/fair-rwlock.h |   64 +++++++++++
 lib/Makefile                |    2 
 lib/fair-rwlock.c           |  244 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 310 insertions(+)

Index: linux-2.6-lttng/include/linux/fair-rwlock.h
===================================================================
@@ -0,0 +1,64 @@
+/*
+ * Fair rwlock
+ *
+ * Allows more fairness than the standard rwlock for this kind of common
+ * scenario (tasklist_lock) :
+ *
+ * - rwlock shared between
+ *   - Rare update in thread context
+ *   - Frequent slow read in thread context (task list iteration)
+ *   - Fast interrupt handler read
+ *
+ * The slow write must therefore disable interrupts around the write lock,
+ * but will therefore add up to the global interrupt latency; worse case being
+ * the duration of the slow read.
+ *
+ * This "fair" rwlock locks out the threads first, then disables softirqs,
+ * then locks out the softirqs, then disables irqs and locks out softirqs. Only
+ * then is the writer allowed to modify the data structure.
+ *
+ * A spinlock is used to insure writer mutual exclusion.
+ *
+ * Mathieu Desnoyers <[email protected]>
+ * August 2008
+ */
+
+#include <linux/spinlock.h>
+#include <asm/atomic.h>
+
+struct fair_rwlock {
+	atomic_long_t value;
+	spinlock_t wlock;
+};
+
+/* Reader lock */
+
+/*
+ * many readers, from irq/softirq/thread context.
+ * protects against writers.
+ */
+void fair_read_lock(struct fair_rwlock *rwlock);
+void fair_read_unlock(struct fair_rwlock *rwlock);
+
+/* Writer Lock */
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against irq/softirq/thread readers.
+ */
+void fair_write_lock_irq(struct fair_rwlock *rwlock);
+void fair_write_unlock_irq(struct fair_rwlock *rwlock);
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against softirq/thread readers.
+ */
+void fair_write_lock_bh(struct fair_rwlock *rwlock);
+void fair_write_unlock_bh(struct fair_rwlock *rwlock);
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against thread readers.
+ */
+void fair_write_lock(struct fair_rwlock *rwlock);
+void fair_write_unlock(struct fair_rwlock *rwlock);

Index: linux-2.6-lttng/lib/Makefile
===================================================================
@@ -43,6 +43,8 @@ obj-$(CONFIG_DEBUG_PREEMPT) += smp_proce
 obj-$(CONFIG_DEBUG_LIST) += list_debug.o
 obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
 
+obj-y += fair-rwlock.o
+
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
   lib-y += dec_and_lock.o
 endif

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Right. Which is exactly why I'd suggest using the extra space for saying "this CPU is busy-looping waiting for a write lock", and then the read-lock contention case can say

- ok, there's a pending write lock holder on _my_ CPU, so I need to just succeed right away despite the fact that there is contention.

In other words, there are a few cases:

- you actually *got* the write lock

interrupts obviously have to be disabled here, because any reader can simply not get the lock.

- you are waiting to get the write lock.

Mark this CPU as "pending" in the rwlock (by making the extended thing be a queue, or by simply only ever allowing a single pendign CPU), and re-enable interrupts while you wait for it. An interrupt that comes in and wants a read-lock sees that it's pending, so it should then ignore the contention bit, and only wait for the write bit to go away.

See? This way you only need to actually disable interrupts while holding literally the lock, not while waiting for it. While still giving priority to writers (except for the _one_ CPU, where new readers will have to get through).

So this way you can be fair, and not allow readers to starve a writer. The only reader that is allowed past a waiting writer is the reader on that same CPU.

And notice how the fast-path needs no spinlock or anything else - it's still just a single locked instruction. In comparison, if I read your example code right, it is absolutely horrid and has an extra spinlock access for the fair_write_lock case.

Linus

[...]

Hi Linus,

Using a writer subscription to the rwlock to make sure the readers stop taking the lock when a writer is waiting for it is indeed a good way to insure fairness. I just fixed the issues you pointed in my patch (spinlock removed, added a write fastpath with a single atomic op) and also used the subscription idea to get fairness for writers. Contention delay tests shows that fairness is achieved pretty well. For periodical writers, busy looping readers and periodical interrupt readers :

6 thread readers (busy-looping)
3 thread writers (1ms period)
2 periodical interrupt readers on 7/8 cpus (IPIs).

- 21us max. contention for writer
- 154us max. contention for thread readers
- 16us max. contention for interrupt readers

(benchmark details below)

I still perceive two potential problems with your approach. It's not related to fairness between readers and writers, but more on the effect on interrupt latency on the system. This is actually what my patch try to address.

First there is a long interrupt handler scenario, as bad as disabling interrupts for a long time period, which is not fixed by your solution :

CPU A
thread context, takes the read lock, gets interrupted, softirq runs.

CPU B
thread context, subscribes for the writer lock, busy loops waiting for CPU A. (in your solution, interrupts are enabled here so interrupt handlers on CPU B can come in)

CPU C
interrupt context, takes the read lock, contended because CPU B busy loops waiting for the writer lock.

-> CPU C will have an interrupt handler running for the duration of the softirq on CPU A, which will impact interrupt latency on CPU C.

Second, I tend to think this it might be difficult to atomically set the writer state and disable interrupts, unless we disable interrupts, cmpxchg the writer test, reenable interrupts if it fails in a loop, which does not seem very neat.

Fair low-latency rwlock v3

Changelog since v2 :
Add writer fairness in addition to fairness wrt interrupts and softirqs. Added contention delays performance tests for thread and interrupt contexts to changelog.

Changelog since v1 :
- No more spinlock to protect against concurrent writes, it is done within the existing atomic variable.
- Write fastpath with a single atomic op.

[...]

No, I just had a look at it, thanks for the pointer!

Tweakable contention behavior seems interesting, but I don't think it deals with the fact that on a mainline kernel, when an interrupt handler comes in and asks for a read lock, it has to get it on the spot. (RT kernels can get away with that using threaded threaded interrupts, but that's a completely different scheme). Therefore, the impact is that interrupts must be disabled around write lock usage, and we end up in the situation where this interrupt disable section can last for a long time, given it waits for every readers (including ones which does not disable interrupts nor softirqs) to complete.

Actually, I just used LTTng traces and eventually made a small patch to lockdep to detect whenever a spinlock or a rwlock is used both with interrupts enabled and disabled. Those sites are likely to produce very high latencies and should IMHO be considered as bogus. The basic bogus scenario is to have a spinlock held on CPU A with interrupts enabled being interrupted and then a softirq runs. On CPU B, the same lock is acquired with interrupts off. We therefore disable interrupts on CPU B for the duration of the softirq currently running on the CPU A, which is really not something that helps keeping short latencies. My preliminary results shows that there are a lot of inconsistent spinlock/rwlock irq on/off uses in the kernel.

This kind of scenario is pretty easy to fix for spinlocks (either move the interrupt disable within the spinlock section if the spinlock is never used by an interrupt handler or make sure that every users has interrupts disabled).

The problem comes with rwlocks : it is correct to have readers both with and without irq disable, even when interrupt handlers use the read lock. However, the write lock has to disable interrupt in that case, and we suffer from the high latency I pointed out. The tasklist_lock is the perfect example of this. In the following patch, I try to address this issue.

The core idea is this :

This "fair" rwlock writer subscribes to the lock, which locks out the reader threads. Then, it takes waits until all reader threads exited their critical section and takes the mutex (1 bit within the "long"). Then it disables softirqs, locks out the softirqs, waits for all softirqs to exit their critical section, disables irqs and locks out irqs. It then waits for irqs to exit their critical section. Only then is the writer allowed to modify the data structure.

The writer fast path checks for a non-contended lock (all bits set to 0) and does an atomic cmpxchg to set the subscription, mutex, softirq exclusion and irq exclusion bits.

The reader does an atomic cmpxchg to check if there is a subscribed writer. If not, it increments the reader count for its context (thread, softirq, irq).

The test module is available at :

http://ltt.polymtl.ca/svn/trunk/tests/kernel/test-fair-rwlock.c

** Performance tests

Dual quad-core Xeon 2.0GHz E5405

* Lock contention delays, per context, 30s test

6 thread readers (no delay loop)
3 thread writers (no delay loop)
2 periodical interrupt readers on 7/8 cpus (IPIs).

writer_thread/0 iterations : 2757002, max contention 561144 cycles writer_thread/1 iterations : 2550357, max contention 606036 cycles writer_thread/2 iterations : 2561024, max contention 593082 cycles reader_thread/0 iterations : 199444, max contention 5776327560 cycles reader_thread/1 iterations : 129680, max contention 5768277564 cycles reader_thread/2 iterations : 76323, max contention 5775994128 cycles reader_thread/3 iterations : 110571, max contention 4336139232 cycles reader_thread/4 iterations : 120402, max contention 5513734818 cycles reader_thread/5 iterations : 227301, max contention 4510503438 cycles interrupt_reader_thread/0 iterations : 225
interrupt readers on CPU 0, max contention : 46056 cycles interrupt readers on CPU 1, max contention : 32694 cycles interrupt readers on CPU 2, max contention : 57432 cycles interrupt readers on CPU 3, max contention : 29520 cycles interrupt readers on CPU 4, max contention : 25908 cycles interrupt readers on CPU 5, max contention : 36246 cycles interrupt readers on CPU 6, max contention : 17916 cycles interrupt readers on CPU 7, max contention : 34866 cycles

* Lock contention delays, per context, 600s test

6 thread readers (no delay loop)
3 thread writers (1ms period)
2 periodical interrupt readers on 7/8 cpus (IPIs).

writer_thread/0 iterations : 75001, max contention 42168 cycles writer_thread/1 iterations : 75008, max contention 43674 cycles writer_thread/2 iterations : 74999, max contention 43656 cycles reader_thread/0 iterations : 256202476, max contention 307458 cycles reader_thread/1 iterations : 270441472, max contention 261648 cycles reader_thread/2 iterations : 258978159, max contention 171468 cycles reader_thread/3 iterations : 247473522, max contention 97344 cycles reader_thread/4 iterations : 285541056, max contention 136842 cycles reader_thread/5 iterations : 269070814, max contention 134052 cycles interrupt_reader_thread/0 iterations : 5772
interrupt readers on CPU 0, max contention : 13602 cycles interrupt readers on CPU 1, max contention : 20082 cycles interrupt readers on CPU 2, max contention : 12846 cycles interrupt readers on CPU 3, max contention : 17892 cycles interrupt readers on CPU 4, max contention : 31572 cycles interrupt readers on CPU 5, max contention : 27444 cycles interrupt readers on CPU 6, max contention : 16140 cycles interrupt readers on CPU 7, max contention : 16026 cycles

---
 include/linux/fair-rwlock.h |   51 ++++++
 lib/Makefile                |    2 
 lib/fair-rwlock.c           |  368 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 421 insertions(+)

Index: linux-2.6-lttng/include/linux/fair-rwlock.h
===================================================================
@@ -0,0 +1,51 @@
+#ifndef _LINUX_FAIR_RWLOCK_H
+#define _LINUX_FAIR_RWLOCK_H
+
+/*
+ * Fair low-latency rwlock
+ *
+ * Allows writer fairness wrt readers and also minimally impact the irq latency
+ * of the system.
+ *
+ * Mathieu Desnoyers <[email protected]>
+ * August 2008
+ */
+
+#include <asm/atomic.h>
+
+struct fair_rwlock {
+	atomic_long_t value;
+};
+
+/* Reader lock */
+
+/*
+ * many readers, from irq/softirq/thread context.
+ * protects against writers.
+ */
+void fair_read_lock(struct fair_rwlock *rwlock);
+void fair_read_unlock(struct fair_rwlock *rwlock);
+
+/* Writer Lock */
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against irq/softirq/thread readers.
+ */
+void fair_write_lock_irq(struct fair_rwlock *rwlock);
+void fair_write_unlock_irq(struct fair_rwlock *rwlock);
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against softirq/thread readers.
+ */
+void fair_write_lock_bh(struct fair_rwlock *rwlock);
+void fair_write_unlock_bh(struct fair_rwlock *rwlock);
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against thread readers.
+ */
+void fair_write_lock(struct fair_rwlock *rwlock);
+void fair_write_unlock(struct fair_rwlock *rwlock);
+#endif /* _LINUX_FAIR_RWLOCK_H */

Index: linux-2.6-lttng/lib/Makefile
===================================================================
@@ -43,6 +43,8 @@ obj-$(CONFIG_DEBUG_PREEMPT) += smp_proce
 obj-$(CONFIG_DEBUG_LIST) += list_debug.o
 obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
 
+obj-y += fair-rwlock.o
+
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
   lib-y += dec_and_lock.o
 endif

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Ah, you are right. This new version implements a "single cmpxchg" uncontended code path, changes the _fast semantic for "trylock uncontended" and also adds the trylock primitives.

Thanks for the input,

Mathieu

Fair low-latency rwlock v5

Fair low-latency rwlock provides fairness for writers against reader threads, but lets softirq and irq readers in even when there are subscribed writers waiting for the lock. Writers could starve reader threads.

Changelog since v4 :
rename _fast -> trylock uncontended
Remove the read from the uncontended read and write cases : just do a cmpxchg expecting "sub_expect", 0 for "lock", 1 subscriber for a "trylock". Use the value returned by the first cmpxchg as following value instead of doing an unnecessary read.

Here is why read + rmw is wrong (quoting Linus) :

"This is actually potentially very slow.

Why? If the lock is uncontended, but is not in the current CPU's caches, the read -> rmw operation generates multiple cache coherency protocol events. First it gets the line in shared mode (for the read), and then later it turns it into exclusive mode."

Changelog since v3 :
Added writer subscription and fair trylock. The writer subscription keeps the reader threads out of the lock.

Changelog since v2 :
Add writer fairness in addition to fairness wrt interrupts and softirqs. Added contention delays performance tests for thread and interrupt contexts to changelog.

Changelog since v1 :
- No more spinlock to protect against concurrent writes, it is done within the existing atomic variable.
- Write fastpath with a single atomic op.

[...]

No, I just had a look at it, thanks for the pointer!

Tweakable contention behavior seems interesting, but I don't think it deals with the fact that on a mainline kernel, when an interrupt handler comes in and asks for a read lock, it has to get it on the spot. (RT kernels can get away with that using threaded threaded interrupts, but that's a completely different scheme). Therefore, the impact is that interrupts must be disabled around write lock usage, and we end up in the situation where this interrupt disable section can last for a long time, given it waits for every readers (including ones which does not disable interrupts nor softirqs) to complete.

Actually, I just used LTTng traces and eventually made a small patch to lockdep to detect whenever a spinlock or a rwlock is used both with interrupts enabled and disabled. Those sites are likely to produce very high latencies and should IMHO be considered as bogus. The basic bogus scenario is to have a spinlock held on CPU A with interrupts enabled being interrupted and then a softirq runs. On CPU B, the same lock is acquired with interrupts off. We therefore disable interrupts on CPU B for the duration of the softirq currently running on the CPU A, which is really not something that helps keeping short latencies. My preliminary results shows that there are a lot of inconsistent spinlock/rwlock irq on/off uses in the kernel.

This kind of scenario is pretty easy to fix for spinlocks (either move the interrupt disable within the spinlock section if the spinlock is never used by an interrupt handler or make sure that every users has interrupts disabled).

The problem comes with rwlocks : it is correct to have readers both with and without irq disable, even when interrupt handlers use the read lock. However, the write lock has to disable interrupt in that case, and we suffer from the high latency I pointed out. The tasklist_lock is the perfect example of this. In the following patch, I try to address this issue.

The core idea is this :

This "fair" rwlock writer subscribes to the lock, which locks out the reader threads. Then, it takes waits until all reader threads exited their critical section and takes the mutex (1 bit within the "long"). Then it disables softirqs, locks out the softirqs, waits for all softirqs to exit their critical section, disables irqs and locks out irqs. It then waits for irqs to exit their critical section. Only then is the writer allowed to modify the data structure.

The writer fast path checks for a non-contended lock (all bits set to 0) and does an atomic cmpxchg to set the subscription, mutex, softirq exclusion and irq exclusion bits.

The reader does an atomic cmpxchg to check if there is a subscribed writer. If not, it increments the reader count for its context (thread, softirq, irq).

The test module is available at :

http://ltt.polymtl.ca/svn/trunk/tests/kernel/test-fair-rwlock.c

** Performance tests

Dual quad-core Xeon 2.0GHz E5405

* Lock contention delays, per context, 60s test

6 thread readers (no delay loop)
3 thread writers (10us period)
2 periodical interrupt readers on 7/8 cpus (IPIs).

writer_thread/0 iterations : 2980374, max contention 1007442 cycles writer_thread/1 iterations : 2992675, max contention 917364 cycles trylock_writer_thread/0 iterations : 13533386, successful iterations : 3357015 trylock_writer_thread/1 iterations : 13310980, successful iterations : 3278394 reader_thread/0 iterations : 13624664, max contention 1296450 cycles reader_thread/1 iterations : 12183042, max contention 1524810 cycles reader_thread/2 iterations : 13302985, max contention 1017834 cycles reader_thread/3 iterations : 13398307, max contention 1016700 cycles trylock_reader_thread/0 iterations : 60849620, successful iterations : 14708736 trylock_reader_thread/1 iterations : 63830891, successful iterations : 15827695 interrupt_reader_thread/0 iterations : 559
interrupt readers on CPU 0, max contention : 13914 cycles
interrupt readers on CPU 1, max contention : 16446 cycles
interrupt readers on CPU 2, max contention : 11604 cycles
interrupt readers on CPU 3, max contention : 14124 cycles
interrupt readers on CPU 4, max contention : 16494 cycles
interrupt readers on CPU 5, max contention : 12930 cycles
interrupt readers on CPU 6, max contention : 9432 cycles
interrupt readers on CPU 7, max contention : 14514 cycles trylock_interrupt_reader_thread/0 iterations : 573
trylock interrupt readers on CPU 0, iterations 1249, successful iterations : 1135 trylock interrupt readers on CPU 1, iterations 1152, successful iterations : 1064 trylock interrupt readers on CPU 2, iterations 1239, successful iterations : 1135 trylock interrupt readers on CPU 3, iterations 1227, successful iterations : 1130 trylock interrupt readers on CPU 4, iterations 1029, successful iterations : 908 trylock interrupt readers on CPU 5, iterations 1161, successful iterations : 1063 trylock interrupt readers on CPU 6, iterations 612, successful iterations : 578 trylock interrupt readers on CPU 7, iterations 1007, successful iterations : 932

---
 include/linux/fair-rwlock.h |   61 ++++
 lib/Makefile                |    2 
 lib/fair-rwlock.c           |  557 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 620 insertions(+)

Index: linux-2.6-lttng/include/linux/fair-rwlock.h
===================================================================
@@ -0,0 +1,61 @@
+#ifndef _LINUX_FAIR_RWLOCK_H
+#define _LINUX_FAIR_RWLOCK_H
+
+/*
+ * Fair low-latency rwlock
+ *
+ * Allows writer fairness wrt readers and also minimally impact the irq latency
+ * of the system.
+ *
+ * Mathieu Desnoyers <[email protected]>
+ * August 2008
+ */
+
+#include <asm/atomic.h>
+
+struct fair_rwlock {
+	atomic_long_t value;
+};
+
+/* Reader lock */
+
+/*
+ * many readers, from irq/softirq/thread context.
+ * protects against writers.
+ */
+void fair_read_lock(struct fair_rwlock *rwlock);
+int fair_read_trylock(struct fair_rwlock *rwlock);
+void fair_read_unlock(struct fair_rwlock *rwlock);
+
+/* Writer Lock */
+
+/*
+ * Subscription for write lock. Must be used for write trylock only.
+ * Insures fairness wrt reader threads.
+ */
+void fair_write_subscribe(struct fair_rwlock *rwlock);
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against irq/softirq/thread readers.
+ */
+void fair_write_lock_irq(struct fair_rwlock *rwlock);
+int fair_write_trylock_subscribed_irq(struct fair_rwlock *rwlock);
+void fair_write_unlock_irq(struct fair_rwlock *rwlock);
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against softirq/thread readers.
+ */
+void fair_write_lock_bh(struct fair_rwlock *rwlock);
+int fair_write_trylock_subscribed_bh(struct fair_rwlock *rwlock);
+void fair_write_unlock_bh(struct fair_rwlock *rwlock);
+
+/*
+ * Safe against other writers in thread context.
+ * Safe against thread readers.
+ */
+void fair_write_lock(struct fair_rwlock *rwlock);
+int fair_write_trylock_subscribed(struct fair_rwlock *rwlock);
+void fair_write_unlock(struct fair_rwlock *rwlock);
+#endif /* _LINUX_FAIR_RWLOCK_H */

Index: linux-2.6-lttng/lib/Makefile
===================================================================
@@ -43,6 +43,8 @@ obj-$(CONFIG_DEBUG_PREEMPT) += smp_proce
 obj-$(CONFIG_DEBUG_LIST) += list_debug.o
 obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
 
+obj-y += fair-rwlock.o
+
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
   lib-y += dec_and_lock.o
 endif

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Here are some updated benchmarks of the rwlock v5, showing [min,avg,max] delays in non-contended and contended cases :

The test module is available at :

http://ltt.polymtl.ca/svn/trunk/tests/kernel/test-fair-rwlock.c

** Performance tests

Dual quad-core Xeon 2.0GHz E5405

* Lock contention delays, per context, 60s test

** get_cycles calibration **
get_cycles takes [min,avg,max] 78,79,84 cycles, results calibrated on avg

** Single writer test, no contention **
writer_thread/0 iterations : 964054, lock delay [min,avg,max] 149,157,5933 cycles

** Single reader test, no contention **
reader_thread/0 iterations : 37591763, lock delay [min,avg,max] 59,65,21383 cycles

** Multiple readers test, no contention **
reader_thread/0 iterations : 9062919, lock delay [min,avg,max] 59,921,42593 cycles reader_thread/1 iterations : 9014846, lock delay [min,avg,max] 59,928,42065 cycles reader_thread/2 iterations : 9394114, lock delay [min,avg,max] 59,897,46877 cycles reader_thread/3 iterations : 9459081, lock delay [min,avg,max] 59,896,38207 cycles

** High contention test **
4 thread readers (no delay loop)
2 thread trylock readers (no delay loop)
2 thread writers (10us period)
2 thread trylock writers (10us period)
1 periodical interrupt readers on 7/8 cpus (IPIs). 1 periodical interrupt trylock readers on 7/8 cpus (IPIs).

writer_thread/0 iterations : 2864146, lock delay [min,avg,max] 179,9493,102563 cycles writer_thread/1 iterations : 2986492, lock delay [min,avg,max] 179,9332,66923 cycles trylock_writer_thread/0 iterations : 12789892, successful iterations : 3257203 trylock_writer_thread/1 iterations : 12747023, successful iterations : 3268997 reader_thread/0 iterations : 13091562, lock delay [min,avg,max] 59,5806,141053 cycles reader_thread/1 iterations : 12574027, lock delay [min,avg,max] 59,5706,141839 cycles reader_thread/2 iterations : 12805706, lock delay [min,avg,max] 59,5738,138725 cycles reader_thread/3 iterations : 13352731, lock delay [min,avg,max] 59,5606,137585 cycles trylock_reader_thread/0 iterations : 63135422, successful iterations : 15204229 trylock_reader_thread/1 iterations : 62306024, successful iterations : 15123824 interrupt_reader_thread/0 iterations : 559
interrupt readers on CPU 0, lock delay [min,avg,max] 167,984,16271 cycles interrupt readers on CPU 1, lock delay [min,avg,max] 179,1185,9125 cycles interrupt readers on CPU 2, lock delay [min,avg,max] 155,940,8081 cycles interrupt readers on CPU 3, lock delay [min,avg,max] 83,1158,13355 cycles interrupt readers on CPU 4, lock delay [min,avg,max] 77,863,6371 cycles interrupt readers on CPU 5, lock delay [min,avg,max] 173,1169,16331 cycles interrupt readers on CPU 6, lock delay [min,avg,max] 155,834,8705 cycles interrupt readers on CPU 7, lock delay [min,avg,max] 173,1159,10115 cycles trylock_interrupt_reader_thread/0 iterations : 570
trylock interrupt readers on CPU 0, iterations 280, successful iterations : 239 trylock interrupt readers on CPU 1, iterations 590, successful iterations : 538 trylock interrupt readers on CPU 2, iterations 431, successful iterations : 372 trylock interrupt readers on CPU 3, iterations 605, successful iterations : 570 trylock interrupt readers on CPU 4, iterations 659, successful iterations : 570 trylock interrupt readers on CPU 5, iterations 616, successful iterations : 570 trylock interrupt readers on CPU 6, iterations 675, successful iterations : 570 trylock interrupt readers on CPU 7, iterations 597, successful iterations : 561

Mathieu

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Can you also finally

- separate out the fastpaths more clearly. The slowpaths should not be even visible in the I$ footprint. The fastpaths are probably better off as a separate "fastpath.S" file to make sure that the compiler doesn't inline the slowpath or do other insane things.

If the fastpath isn't just a few instructions, there's something wrong. It should be written in assembly, so that it's very clear what the fastpath is. Because most of the time, the fastpath is all that really matters (at least as long as there is some reasonable slow-path and contention behaviour - the slowpath matters int hat it shouldn't ever be a _problem_).

- don't call these "fair". They may be fairER than the regular rwlocks, but you'd really need to explain that, and true fairness you (a) can't really get without explicit queueing and (b) probably don't even want, because the only starvation people tend to worry about is reader vs writer, and writer-writer fairness tends to be unimportant. So it's not that people want the (expensive) "fairness" it's really that they want something _reasonably_ fair considering the normal worries.

(ie if you have so much write activity that you get into write-write fairness worries, you shouldn't be using a rwlock to begin with, so that level of fairness is simply not very interesting).

People react emotionally and too strongly to to words like "fairness" or "freedom". Different people have different ideas on what they mean, and take them to pointless extremes. So just don't use the words, they just detract from the real issue.

Also, the performance numbers on their own are pretty irrelevant, since there's nothing to compare them to. It would be much more relevant if you had a "this is what the standard rwlock" does as a comparison for each number.

Linus

Interesting approach! Questions and comments interspersed below.

Thanx, Paul

Agreed. I am careful about overdesigning for RT though, given that once we get it right for the current thread vs softirq vs hardirq mess, the solution for preemptable critical sections might come more naturally.

See below about RT kernel.

Technical detail : x86_64 cannot pass immediate values > 2^32 to most instructions; it must load an immediate value in a register, which would add a few instructions. Therefore, I prefer to use the lowest bits possible given the NR_CPUS configuration.

Actually, given that softirqs and hardirqs are really just tasks in -RT, I guess threads could be given the whole 45 bits available for threads, softirqs and irqs (0 .. 3*log_2(NR_CPUS)-1).

However, in that case, we would also like to have as much preempable writer critical sections as we have reader critical sections. Therefore, it would be best to split the 60 bits in two :

30 bits for reader threads
30 bits for writer threads

However, I wonder if the whole algorithm included in this rwlock primitive to make sure that interrupt latency < softirq latency < thread latency won't just vanish in -rt kernels. We might want to group those threads by priority (e.g. grouping irq threads together and maybe leaving softirq and normal threads in the same bunch), but we would then impact softirq latency a little bit more.

The problem of this approach wrt RT kernels is that we cannot provide enough "priority groups" (current irq, softirq and threads in mainline kernel) for all the subtile priority levels of RT kernels. The more groups we add, the less threads we allow on the system.

So basically, the relationship between the max number of threads (T) and the number of reader priorities goes as follow on a 64 bits machine :

T writers subscribed count bits
1 bit for writer mutex

for first priority group :
T reader count bits
(no need of reader exclusion bit because the writer subscribed count bits and the writer mutex act as exclusion)

for each other priority group :
T reader count bits
1 reader exclusion bit (set by the writer)

We have the inequality :

64 >= (T + 1) + T + (NR_PRIORITIES - 1) * (T + 1)

64 >= (2T + 1) + (NR_PRIORITIES - 1) * (T + 1)
63 - 2T >= (NR_PRIORITIES - 1) * (T + 1)
((63 - 2T) / (T + 1)) + 1 >= NR_PRIORITIES

Therefore :

Thread bits  |  Max number of threads  |  Number of priorities
  31         |    2147483648           |          1
  20         |       1048576           |          2
  15         |         32768           |          3
  12         |          4096           |          4
   9         |           512           |          5
   8         |           256           |          6
   7         |           128           |          7
   6         |            64           |          8
   5         |            32           |          9
   4         |            16           |         10
   3         |             8           |         15

Starting from here, we have more priority groups than threads in the system, which becomes somewhat pointless... :)

So currently, for the mainline kernel, I chose 3 priority levels thread, softirq, irq), which gives me 32768 max CPU in the system because I choose to disable preemption. However, we can think of ways to tune that in the direction we prefer. We could also hybrid those : having more bits for some groups which have preemptable threads (for which we need a max. of nr. threads) and less bits for other groups where preemption is disabled (where we only need enough bits to cound NR_CPUS)

Ideas are welcome...

I thought it would have been sane to make is a power of two, but you are right.. I should use the neat "roundup_pow_of_two()" :)

gcc is smart nowadays, it gets inlined automatically when it is small enough and just called once.

Good point, will fix. The atomic_long_cmpxchg executed before we exit the busy loop takes care of ordering.

Yep, I've done that in my fast/slowpath rewrite. Will be posted soonish.

Yep.

What would make sure that we have correct read ordering between rwlock->value and the data we are trying to protect then ?

Given that we are a writer, we might argue that we are not interested in ordering memory reads, only writes.

Yeah, given that all we are interested to know is when a reader has exited its critical section (we are not actually interested in reading any other data that this reader might have written for us), it should be ok to just use a barrier().

Actually, I changed it quite a bit in the new version. I merged the subscription with the first "trylock" so we can do the two in a single operation, which either gets the critical section quickly, or subscribes.

Yes, but it's more than that. I'll do a table resuming what is allowed by reader contexts :

IRQ reader context can access the reader lock when :

- Lock not contended
- Reader threads are holding the lock
- Writers are subscribed
- A writer is holding the WRITE_MUTEX (which excludes other writers)
- A writer is locking out softirqs.

SoftIRQ reader context can access the reader lock when :

- Lock not contended
- Reader threads are holding the lock
- Writers are subscribed
- A writer is holding the WRITE_MUTEX (which excludes other writers)

Thread reader context can access the reader lock when :

- Lock not contended
- Reader threads are holding the lock

Note that the fact that "Writers are subscribed" is not present for the thread reader condition to obtain the lock implies that we favor writers against thread readers. This is however not the case for IRQ and Softirq.

In fair_write_trylock_irq_uncontended(), which becomes the fastpath in the new patch version, I disable softirqs and irqs, and try to get the lock in one go if not contended. If that fails, then I start to lock-out execution contexts from the lock, one at a time.

I am not sure that I understand your comment completely though.

Right.

If interrupts would be disabled before calling :

It would be busy-looping, waiting for softirqs to exit their read-side critical section, while interrupts are disabled. Given that those softirqs can run for longer than the duration for which we would like to disable interrupts (the ciritical section itself can be long, but softirqs could also be interrupted, and more than once), it's better to let softirqs exit their critical sections before disabling irqs.

:)

Because we do

in fair_write_unlock_irq().

Actually, if we could do, in the slow path :

local_bh_disable();
wait for bh to exit
local_irq_disable();
local_bh_enable();
wait for irq to exit

We could then remove the local_bh_enable() from the unlock and therefore remove the local_bh_disable/enable pair from the fast path.

However, is it legal to reenable bottom-halves when interrupts are off, or is there some check done like the preempt_check_resched() code which forbids that ?

Considering what I see in _local_bh_enable_ip(), it seems wrong :

  WARN_ON_ONCE(in_irq() || irqs_disabled());

Ah, and there is a preempt_check_resched(); call at the end of _local_bh_enable_ip. That explains it. I wonder if there would be some way around that limitation. Given this comment :

/*
* Special-case - softirqs can safely be enabled in
* cond_resched_softirq(), or by __do_softirq(),
* without processing still-pending softirqs:
*/
void _local_bh_enable(void)

There seems to be a few special-cases, which gives me hope (but no clear solution). :/

Good idea, I'll add a check in the slowpath, but I'll leave it out of the fast path to keep it, well, fast.

This fair_write_lock should _only_ be used if there are no bh nor irq readers for this lock. Therefore we do not disable interrupts. Actually, I should add a WARN_ON here to be certain it is used properly. A reader thread which reads this data structure with interrupts disabled is considered as reading from interrupt context in my semantic (implemented in the new patch version).

Actually, all my writer slow paths should have the following :

  WARN_ON_ONCE(in_interrupt() || irqs_disabled());

Which checks if bh are disabled, if I am in irq context or in bh context and checks if irqs are disabled. All these requirements must be met to be able to correctly wait for contended reader threads without increasing the irq or softirq latency.

It's updated in the following version, the use case is found in comment in the code.

Thanks a lot for the review !

Mathieu

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

* Mathieu Desnoyers ([email protected]) wrote:
[...]

It strikes me that Intel has a nice (probably slow?) cmpxchg16b instruction on x86_64. Therefore, we could atomically update 128 bits, which gives the following table :

((127 - 2T) / (T + 1)) + 1 >= NR_PRIORITIES

Thread bits  |  Max number of threads  |  Number of priorities
63           |            2^63         |            1
42           |            2^42         |            2
31           |            2^31         |            3
24           |            2^24         |            4
20           |            2^20         |            5
17           |          131072         |            6
15           |           32768         |            7
13           |            8192         |            8
11           |            2048         |            9
10           |            1024         |           10
9            |             512         |           11
8            |             256         |           13
7            |             128         |           15
6            |              64         |           17
5            |              32         |           20
4            |              16         |           24

.. where we have more priorities than threads.

So I wonder if having in the surrounding of 10 priorities, which could dynamically adapt the number of threads to the number of priorities available, could be interesting for the RT kernel ?

That would however depend on the very architecture-specific cmpxchg16b.

Mathieu

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Still thinking about RT :

The good news is : we don't really need all those bits to be updated atomically. The bit groups which must be atomically updated are :

- Writer and first priority group
T writers subscribed count bits
1 bit for writer mutex
T reader count bits

- For each other priority group :
T reader count bits
1 reader exclusion bit (set by the writer)

I also noticed that the writer and the first reader priority group happen to be at the same priority level. When the writer want to exclude readers from higher priority groups, it must take their priority, exclude them using the reader exclusion bit, wait for all readers of that group to be out of their critical section and then proceed to the next priority group until all the groups are locked.

The reader of the first priority group must check that both the writer mutex and the writers subscribed count bits are not set.

The readers in the other groups only have to check the reader exclusion bit associated to their own group.

So if we simplify the problem a bit for RT, let's fix a maximum of 32768 threads on the system (15 bits). Let's also assume we have 19 priorities.

- Writer and first priority group (fits in 31 bits) 15 bits for writers subscribed count
1 bit for writer mutex
15 bits reader count

Then we have an array of 18 : (each fit in 16 bits) 15 reader count bits
1 reader exclusion bit

Therefore, the whole data would fit in 40 bytes.

The only thing we would not have is the ability to do a single cmpxchg on all the bits in the writer fast path, making the writer common case much much slower.

However, the reader side would still be lightning-fast as it would only have to do a cmpxchg on its own 16 or 32 bits bitfield.

Mathieu

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Stop this crapola.

Take a look at the rwsem thing I pointed you to. After you understand that, come back.

The WHOLE POINT of that thing was to use only 32-bit atomics on the hot path. Don't even start think9ing about cmpxchg16b. If you cannot do your atomics in 32-bit, they're broken.

Please. I realize that the rwsem implementation I did is subtle. But really. Spend the time to understand it.

Linus

You are right, before posting my new version, let's review your rwsem implementation. Let's pseudo-code the fastpath in C (I don't like to review the instruction set when thinking conceptually). Comments inlined. My new patch follows.

* Read lock fast path

my_rwlock_rdlock :
int v = atomic_add_return(0x4, &lock);
if (v & 0x3)
__my_rwlock_rdlock(lock);
return

Ok, so the reader just say "hey, I'm there" by adding itself to the reader could. Unlikely to overflow, but could. Then checks the writer mask, if set, call the read slowpath. In my solution, I do basically the same as the writer fast path you did : I expect all bits to be 0. Therefore, if there are many readers at once, I use the slow path even though there is not "real" contention on the lock. Given that I need to limit the number of readers to a smaller amount of bits, I need to detect overflow before-the-fact (this is my new v8 implementation, will be posted shortly). BTW, you could accelerate the slow path by passing "v" :

my_rwlock_rdlock :
int v = atomic_add_return(0x4, &lock);
if (v & 0x3)
__my_rwlock_rdlock(lock, v);
return;

* Write lock fast path

my_rwlock_wrlock :
if (cmpcxhg(&lock, 0, 0x1) != 0)
__my_rwlock_wrlock(lock);
return;

Writer expects all bits to be 0 (lock uncontended). If true, take the lock by setting 0x1, else take the slow path. Yes, that's more or less what I have too. Here too, you could accelerate the write slow path by passing v.

my_rwlock_wrlock :
int v = cmpcxhg(&lock, 0, 0x1);
if (v)
__my_rwlock_wrlock(lock, v);
return;

* Read and write unlock fastpath

my_rwlock_unlock :
int v = atomic_read(&lock);
if (!(v & 0x1)) {
/* unlock reader */
v = atomic_sub_return(0x4, &lock);
if (v & 0x3)

    __my_rwlock_rdunlock(lock);

return;
} else {
/* unlock writer */
if (!(v == 0x1))

    __my_rwlock_wrunlock(lock);
  if (cmpxchg(&lock, v, 0) != v)
    __my_rwlock_wrunlock(lock);

return;
}

Hrm, why don't you split the unlocks ? You could remove the initial read from the writer unlock. You could also accelerate the slow path by passing v.

my_rwlock_rdunlock:
int v = atomic_read(&lock);
/* unlock reader */
v = atomic_sub_return(0x4, &lock);
if (v & 0x3)

    __my_rwlock_rdunlock(lock, v);

return;

my_rwlock_wrunlock:
/* unlock writer */
int v = cmpxchg(&lock, 0x1, 0);
if (v != 0x1)

    __my_rwlock_wrunlock(lock, v);

return;

Ok, so I've looks at the slow paths, and I must say it looks pretty much like what I have, except that :

- I keep reader and writer "pending" counts for each execution context. This allow me to keep very low interrupt and softirq latency by moving a pending writer successively up in execution priorities. Because I need more counters, I need to deal with overflow beforehand by busy-looping if a counter overflow is detected.
- I don't need the contention bit, because no contention is indicated by the whole bits being 0. Given that I need to detect overflows, I have to do a cmpxchg instead of a xadd, which implies that I need to know the value beforehand and don't have the ability to use a mask like you do in the read fast path. Given that I do a cmpxchg which also changes the reader count, I can't afford to try to only consider parts of the word in this cmpxchg.

Note that my v8 now implements support for readers in any execution context :
- preemptable
- non-preemptable
- softirq
- irq

Writer-biased low-latency rwlock v8

Writer subscription low-latency rwlock favors writers against reader threads, but lets softirq and irq readers in even when there are subscribed writers waiting for the lock. Very frequent writers could starve reader threads.

Changelog since v7 :
Allow both preemptable and non-preemptable thread readers and writers. Allow preemptable readers and writers to sleep using a wait queue. Use two bits for the wait queue : WQ_ACTIVE (there is a thread waiting to be woken up) and WQ_MUTEX (wait queue protection, single bit).

Changelog since v6 :
Made many single-instruction functions static inline, moved to the header. Separated in slowpath and fastpath C file implementations. The fastpath is meant to be reimplemented in assembly. Architectures which choose to implement an optimized fast path must define HAVE_WBIAS_RWLOCK_FASTPATH, which will disable the generic C version.
Rename to wbias-rwlock.c
Added support for IRQ/Softirq/preemption latency profiling, provided by a separate patch.
Readers and writers will busy loop if the counter for their context is full. We can now have less bits reserved for almost unused context (e.g. softirq). This let us remove any NR_CPUS limitation.

Changelog since v5 :
Test irqs_disabled() in the reader to select the appropriate read context when interrupts are disabled. Softirqs are already tested with in_softirq(), which includes softirq disabled sections.
Change subscription behavior : A writer is subscribed until it gets into the "mutex held" section. Reader threads test for subscription mask or writer mutex to detect writers. It makes the trylock/subscription API much more efficient. Updated benchmarks in changelog, with [min,avg,max] delays for each lock use (contended and uncontended case). Also include "reader thread protection only" scenario where the writer does not disable interrupts nor bottom-halves.

Changelog since v4 :
rename _fast -> trylock uncontended
Remove the read from the uncontended read and write cases : just do a cmpxchg expecting "sub_expect", 0 for "lock", 1 subscriber for a "trylock". Use the value returned by the first cmpxchg as following value instead of doing an unnecessary read.

Here is why read + rmw is wrong (quoting Linus) :

"This is actually potentially very slow.

Why? If the lock is uncontended, but is not in the current CPU's caches, the read -> rmw operation generates multiple cache coherency protocol events. First it gets the line in shared mode (for the read), and then later it turns it into exclusive mode."

Changelog since v3 :
Added writer subscription and trylock. The writer subscription keeps the reader threads out of the lock.

Changelog since v2 :
Add writer bias in addition to low-latency wrt interrupts and softirqs. Added contention delays performance tests for thread and interrupt contexts to changelog.

Changelog since v1 :
- No more spinlock to protect against concurrent writes, it is done within the existing atomic variable.
- Write fastpath with a single atomic op.

I used LTTng traces and eventually made a small patch to lockdep to detect whenever a spinlock or a rwlock is used both with interrupts enabled and disabled. Those sites are likely to produce very high latencies and should IMHO be considered as bogus. The basic bogus scenario is to have a spinlock held on CPU A with interrupts enabled being interrupted and then a softirq runs. On CPU B, the same lock is acquired with interrupts off. We therefore disable interrupts on CPU B for the duration of the softirq currently running on the CPU A, which is really not something that helps keeping short latencies. My preliminary results shows that there are a lot of inconsistent spinlock/rwlock irq on/off uses in the kernel.

This kind of scenario is pretty easy to fix for spinlocks (either move the interrupt disable within the spinlock section if the spinlock is never used by an interrupt handler or make sure that every users has interrupts disabled).

The problem comes with rwlocks : it is correct to have readers both with and without irq disable, even when interrupt handlers use the read lock. However, the write lock has to disable interrupt in that case, and we suffer from the high latency I pointed out. The tasklist_lock is the perfect example of this. In the following patch, I try to address this issue.

The core idea is this :

This writer biased rwlock writer subscribes to the preemptable lock, which locks out the preemptable reader threads. It waits for all the preemptable reader threads to exit their critical section. Then, it disables preemption, subscribes for the non-preemptable lock. Then, it waits until all non-preemptable reader threads exited their critical section and takes the mutex (1 bit within the "long"). Then it disables softirqs, locks out the softirqs, waits for all softirqs to exit their critical section, disables irqs and locks out irqs. It then waits for irqs to exit their critical section. Only then is the writer allowed to modify the data structure.

The writer fast path checks for a non-contended lock (all bits set to 0) and does an atomic cmpxchg to set the subscriptions, witer mutex, softirq exclusion and irq exclusion bits.

The reader does an atomic cmpxchg to check if there is any contention on the lock. If not, it increments the reader count for its context (preemptable thread, non-preemptable thread, softirq, irq).

The test module is available at :

http://ltt.polymtl.ca/svn/trunk/tests/kernel/test-wbias-rwlock.c

** Performance tests

Dual quad-core Xeon 2.0GHz E5405

* Latency

This section presents the detailed breakdown of latency preemption, softirq and interrupt latency generated by the Writer-biased rwlocks. In the "High contention" section, is compares the "irqoff latency tracer" results between standard Linux kernel rwlocks and the wbias-rwlocks.

get_cycles takes [min,avg,max] 72,75,78 cycles, results calibrated on avg

** Single writer test, no contention **
SINGLE_WRITER_TEST_DURATION 10s

IRQ latency for cpu 6 disabled 99490 times, [min,avg,max] 471,485,1527 cycles SoftIRQ latency for cpu 6 disabled 99490 times, [min,avg,max] 693,704,3969 cycles Preemption latency for cpu 6 disabled 99490 times, [min,avg,max] 909,917,4593 cycles

** Single trylock writer test, no contention **
SINGLE_WRITER_TEST_DURATION 10s

IRQ latency for cpu 2 disabled 10036 times, [min,avg,max] 393,396,849 cycles SoftIRQ latency for cpu 2 disabled 10036 times, [min,avg,max] 609,614,1317 cycles Preemption latency for cpu 2 disabled 10036 times, [min,avg,max] 825,826,1971 cycles

** Single reader test, no contention **
SINGLE_READER_TEST_DURATION 10s

Preemption latency for cpu 2 disabled 31596702 times, [min,avg,max] 502,508,54256 cycles

** Multiple readers test, no contention (4 readers, busy-loop) ** MULTIPLE_READERS_TEST_DURATION 10s
NR_READERS 4

Preemption latency for cpu 1 disabled 9302974 times, [min,avg,max] 502,2039,88060 cycles Preemption latency for cpu 3 disabled 9270742 times, [min,avg,max] 508,2045,61342 cycles Preemption latency for cpu 6 disabled 13331943 times, [min,avg,max] 508,1387,309088 cycles Preemption latency for cpu 7 disabled 4781453 times, [min,avg,max] 508,4092,230752 cycles

** High contention test **
TEST_DURATION 60s
NR_WRITERS 2
NR_TRYLOCK_WRITERS 1
NR_READERS 4
NR_TRYLOCK_READERS 1
WRITER_DELAY 100us
TRYLOCK_WRITER_DELAY 1000us
TRYLOCK_WRITERS_FAIL_ITER 100
THREAD_READER_DELAY 0 /* busy loop */
INTERRUPT_READER_DELAY 100ms

Standard Linux rwlock

irqsoff latency trace v1.1.5 on 2.6.27-rc3-trace
--------------------------------------------------------------------
latency: 2902 us, #3/3, CPU#5 | (M:preempt VP:0, KP:0, SP:0 HP:0 #P:8)

    -----------------
    | task: wbiasrwlock_wri-4984 (uid:0 nice:-5 policy:0 rt_prio:0)
    -----------------

=> started at: _write_lock_irq
=> ended at: _write_unlock_irq

# _------=> CPU#
# / _-----=> irqs-off

#              | / _----=> need-resched    
#              || / _---=> hardirq/softirq 
#              ||| / _--=> preempt-depth   
#              |||| /                      
#              |||||     delay             
#  cmd     pid ||||| time  |   caller      
#     \   /    |||||   \   |   /           
wbiasrwl-4984  5d..1    0us!: _write_lock_irq (0)
wbiasrwl-4984  5d..2 2902us : _write_unlock_irq (0)
wbiasrwl-4984  5d..3 2903us : trace_hardirqs_on (_write_unlock_irq)

Writer-biased rwlock, same test routine

irqsoff latency trace v1.1.5 on 2.6.27-rc3-trace
--------------------------------------------------------------------
latency: 33 us, #3/3, CPU#7 | (M:preempt VP:0, KP:0, SP:0 HP:0 #P:8)

    -----------------
    | task: events/7-27 (uid:0 nice:-5 policy:0 rt_prio:0)
    -----------------

=> started at: _spin_lock_irqsave
=> ended at: _spin_unlock_irqrestore

# _------=> CPU#
# / _-----=> irqs-off

#              | / _----=> need-resched    
#              || / _---=> hardirq/softirq 
#              ||| / _--=> preempt-depth   
#              |||| /                      
#              |||||     delay             
#  cmd     pid ||||| time  |   caller      
#     \   /    |||||   \   |   /           
events/7-27    7d...    0us+: _spin_lock_irqsave (0)
events/7-27    7d..1   33us : _spin_unlock_irqrestore (0)
events/7-27    7d..2   33us : trace_hardirqs_on (_spin_unlock_irqrestore)

(latency unrelated to the tests, therefore irq latency <= 33us)

wbias rwlock instrumentation (below) shows that interrupt latency has been 14176 cycles, for a total of 7us.

Detailed writer-biased rwlock latency breakdown :

IRQ latency for cpu 0 disabled 1086419 times, [min,avg,max] 316,2833,14176 cycles IRQ latency for cpu 1 disabled 1099517 times, [min,avg,max] 316,1820,8254 cycles IRQ latency for cpu 3 disabled 159088 times, [min,avg,max] 316,1409,5632 cycles IRQ latency for cpu 4 disabled 161 times, [min,avg,max] 340,1882,5206 cycles SoftIRQ latency for cpu 0 disabled 1086419 times, [min,avg,max] 2212,5350,166402 cycles SoftIRQ latency for cpu 1 disabled 1099517 times, [min,avg,max] 2230,4265,138988 cycles SoftIRQ latency for cpu 3 disabled 159088 times, [min,avg,max] 2212,3319,14992 cycles SoftIRQ latency for cpu 4 disabled 161 times, [min,avg,max] 2266,3802,7138 cycles Preemption latency for cpu 3 disabled 59855 times, [min,avg,max] 5266,15706,53494 cycles Preemption latency for cpu 4 disabled 72 times, [min,avg,max] 5728,14132,28042 cycles Preemption latency for cpu 5 disabled 55586612 times, [min,avg,max] 196,2080,126526 cycles

Note : preemptable critical sections has been implemented after the previous latency tests. It should be noted that the worse latency obtained in wbias rwlock comes from the busy-loop for the wait queue protection mutex (100us) :

IRQ latency for cpu 3 disabled 2822178 times, [min,avg,max] 256,8892,209926 cycles disable : [<ffffffff803acff5>] rwlock_wait+0x265/0x2c0

* Lock contention delays, per context, 60s test (number of cycles required to take the lock are benchmarked)

** get_cycles calibration **
get_cycles takes [min,avg,max] 72,77,78 cycles, results calibrated on avg

** Single writer test, no contention **
A bit slower here on the fast path both for lock/unlock probably due to preempt disable+bh disable+irq disable in wbias rwlock :

* Writer-biased rwlocks v8
writer_thread/0 iterations : 100348, lock delay [min,avg,max] 51,58,279 cycles writer_thread/0 iterations : 100348, unlock delay [min,avg,max] 57,59,3633 cycles

* Standard rwlock, kernel 2.6.27-rc3
writer_thread/0 iterations : 100322, lock delay [min,avg,max] 37,40,4537 cycles writer_thread/0 iterations : 100322, unlock delay [min,avg,max] 37,40,25435 cycles

** Single preemptable reader test, no contention **
Writer-biased rwlock has a twice faster lock and unlock uncontended fast path. Note that wbias rwlock support preemptable readers. Standard rwlocks disables preemption.

* Writer-biased rwlocks v8
preader_thread/0 iterations : 34204828, lock delay [min,avg,max] 21,23,48537 cycles preader_thread/0 iterations : 34204828, unlock delay [min,avg,max] 15,22,22497 cycles

* Standard rwlock, kernel 2.6.27-rc3
preader_thread/0 iterations : 31993512, lock delay [min,avg,max] 37,39,264955 cycles preader_thread/0 iterations : 31993512, unlock delay [min,avg,max] 37,42,151201 cycles

** Single non-preemptable reader test, no contention **
wbias rwlock read is still twice faster than standard rwlock even for read done in non-preemptable context.

* Writer-biased rwlocks v8
npreader_thread/0 iterations : 33631953, lock delay [min,avg,max] 21,23,14919 cycles npreader_thread/0 iterations : 33631953, unlock delay [min,avg,max] 15,21,16635 cycles

* Standard rwlock, kernel 2.6.27-rc3
npreader_thread/0 iterations : 31639225, lock delay [min,avg,max] 37,39,127111 cycles npreader_thread/0 iterations : 31639225, unlock delay [min,avg,max] 37,42,215587 cycles

** Multiple p(reemptable)/n(on-)p(reemptable) readers test, no contention ** This contended case where multiple readers try to access the data structure in loop, without any writer, shows that standard rwlock average is a little bit better than wbias rwlock. It could be explained by the fact that wbias rwlock cmpxchg operation, which is used to keep the count of active readers, may fail if there is contention and must therefore be retried. The fastpath actually expects the number of readers to be 0, which isn't the case here.

* Writer-biased rwlocks v8
npreader_thread/0 iterations : 16781774, lock delay [min,avg,max] 33,421,33435 cycles npreader_thread/0 iterations : 16781774, unlock delay [min,avg,max] 21,222,35925 cycles npreader_thread/1 iterations : 16819056, lock delay [min,avg,max] 21,421,24957 cycles npreader_thread/1 iterations : 16819056, unlock delay [min,avg,max] 21,222,37707 cycles preader_thread/0 iterations : 17151363, lock delay [min,avg,max] 21,425,47745 cycles preader_thread/0 iterations : 17151363, unlock delay [min,avg,max] 21,223,33207 cycles preader_thread/1 iterations : 17248440, lock delay [min,avg,max] 21,423,689061 cycles preader_thread/1 iterations : 17248440, unlock delay [min,avg,max] 15,222,685935 cycles

* Standard rwlock, kernel 2.6.27-rc3
npreader_thread/0 iterations : 19248438, lock delay [min,avg,max] 37,273,364459 cycles npreader_thread/0 iterations : 19248438, unlock delay [min,avg,max] 43,216,272539 cycles npreader_thread/1 iterations : 19251717, lock delay [min,avg,max] 37,242,365719 cycles npreader_thread/1 iterations : 19251717, unlock delay [min,avg,max] 43,249,162847 cycles preader_thread/0 iterations : 19557931, lock delay [min,avg,max] 37,250,334921 cycles preader_thread/0 iterations : 19557931, unlock delay [min,avg,max] 37,245,266377 cycles preader_thread/1 iterations : 19671318, lock delay [min,avg,max] 37,258,390913 cycles preader_thread/1 iterations : 19671318, unlock delay [min,avg,max] 37,234,604507 cycles

** High contention test **

In high contention test :

TEST_DURATION 60s
NR_WRITERS 2
NR_TRYLOCK_WRITERS 1
NR_PREEMPTABLE_READERS 2
NR_NON_PREEMPTABLE_READERS 2
NR_TRYLOCK_READERS 1
WRITER_DELAY 100us
TRYLOCK_WRITER_DELAY 1000us
TRYLOCK_WRITERS_FAIL_ITER 100
THREAD_READER_DELAY 0 /* busy loop */
INTERRUPT_READER_DELAY 100ms

* Preemptable writers

* Writer-biased rwlocks v8
writer_thread/0 iterations : 556371, lock delay [min,avg,max] 153,9020,3138519 cycles writer_thread/0 iterations : 556371, unlock delay [min,avg,max] 171,7277,1134309 cycles writer_thread/1 iterations : 558540, lock delay [min,avg,max] 147,7047,3048447 cycles writer_thread/1 iterations : 558540, unlock delay [min,avg,max] 171,8554,99633 cycles

* Standard rwlock, kernel 2.6.27-rc3
writer_thread/0 iterations : 222797, lock delay [min,avg,max] 127,336611,4710367 cycles writer_thread/0 iterations : 222797, unlock delay [min,avg,max] 151,2009,714115 cycles writer_thread/1 iterations : 6845, lock delay [min,avg,max] 139,17271138,352848961 cycles writer_thread/1 iterations : 6845, unlock delay [min,avg,max] 217,93935,1991509 cycles

* Non-preemptable readers

* Writer-biased rwlocks v8
npreader_thread/0 iterations : 53472673, lock delay [min,avg,max] 21,804,119709 cycles npreader_thread/0 iterations : 53472673, unlock delay [min,avg,max] 15,890,90213 cycles npreader_thread/1 iterations : 53883582, lock delay [min,avg,max] 21,804,120225 cycles npreader_thread/1 iterations : 53883582, unlock delay [min,avg,max] 15,876,82809 cycles

* Standard rwlock, kernel 2.6.27-rc3
npreader_thread/0 iterations : 68298472, lock delay [min,avg,max] 37,640,733423 cycles npreader_thread/0 iterations : 68298472, unlock delay [min,avg,max] 37,565,672241 cycles npreader_thread/1 iterations : 70331311, lock delay [min,avg,max] 37,603,393925 cycles npreader_thread/1 iterations : 70331311, unlock delay [min,avg,max] 37,558,373477 cycles

* Preemptable readers

* Writer-biased rwlocks v8 (note : preemption enabled, explains higher numbers) preader_thread/0 iterations : 40652556, lock delay [min,avg,max] 21,1237,5796567 cycles preader_thread/0 iterations : 40652556, unlock delay [min,avg,max] 15,1196,1655289 cycles preader_thread/1 iterations : 18260923, lock delay [min,avg,max] 21,4833,3181587 cycles preader_thread/1 iterations : 18260923, unlock delay [min,avg,max] 21,1228,862395 cycles

* Standard rwlock, kernel 2.6.27-rc3 (note : std rwlock disables preemption) preader_thread/0 iterations : 69683738, lock delay [min,avg,max] 37,622,742165 cycles preader_thread/0 iterations : 69683738, unlock delay [min,avg,max] 37,566,1331971 cycles preader_thread/1 iterations : 79758111, lock delay [min,avg,max] 37,543,757315 cycles preader_thread/1 iterations : 79758111, unlock delay [min,avg,max] 37,427,813199 cycles

* Interrupt context readers

* Writer-biased rwlocks v8 (note : some of the higher unlock delays (38us) are caused by the wakeup of the wait queue done at the exit of the critical section if the waitqueue is active)
interrupt readers on CPU 0, lock delay [min,avg,max] 153,975,8607 cycles interrupt readers on CPU 0, unlock delay [min,avg,max] 9,2186,45843 cycles interrupt readers on CPU 1, lock delay [min,avg,max] 69,813,13557 cycles interrupt readers on CPU 1, unlock delay [min,avg,max] 9,2323,76005 cycles interrupt readers on CPU 2, lock delay [min,avg,max] 147,949,9111 cycles interrupt readers on CPU 2, unlock delay [min,avg,max] 9,3232,64269 cycles interrupt readers on CPU 3, lock delay [min,avg,max] 69,850,22137 cycles interrupt readers on CPU 3, unlock delay [min,avg,max] 15,1760,46509 cycles interrupt readers on CPU 4, lock delay [min,avg,max] 135,804,8559 cycles interrupt readers on CPU 4, unlock delay [min,avg,max] 9,1898,57009 cycles interrupt readers on CPU 6, lock delay [min,avg,max] 129,904,11877 cycles interrupt readers on CPU 6, unlock delay [min,avg,max] 9,3009,81321 cycles interrupt readers on CPU 7, lock delay [min,avg,max] 135,1239,21489 cycles interrupt readers on CPU 7, unlock delay [min,avg,max] 9,2215,68991 cycles

* Standard rwlock, kernel 2.6.27-rc3 (note : these numbers are not that bad, but they do not take interrupt latency in account. See tests above for discussion of this issue)
interrupt readers on CPU 0, lock delay [min,avg,max] 55,573,4417 cycles interrupt readers on CPU 0, unlock delay [min,avg,max] 43,529,1591 cycles interrupt readers on CPU 1, lock delay [min,avg,max] 139,591,5731 cycles interrupt readers on CPU 1, unlock delay [min,avg,max] 31,534,2395 cycles interrupt readers on CPU 2, lock delay [min,avg,max] 127,671,6043 cycles interrupt readers on CPU 2, unlock delay [min,avg,max] 37,401,1567 cycles interrupt readers on CPU 3, lock delay [min,avg,max] 151,676,5569 cycles interrupt readers on CPU 3, unlock delay [min,avg,max] 127,536,2797 cycles interrupt readers on CPU 5, lock delay [min,avg,max] 127,531,15397 cycles interrupt readers on CPU 5, unlock delay [min,avg,max] 31,323,1747 cycles interrupt readers on CPU 6, lock delay [min,avg,max] 121,548,29125 cycles interrupt readers on CPU 6, unlock delay [min,avg,max] 31,435,2089 cycles interrupt readers on CPU 7, lock delay [min,avg,max] 37,613,5485 cycles interrupt readers on CPU 7, unlock delay [min,avg,max] 49,541,1645 cycles

---
 include/linux/wbias-rwlock.h |  548 ++++++++++++++++++++++++++++++++++
 lib/Kconfig                  |    3 
 lib/Kconfig.debug            |    4 
 lib/Makefile                 |    7 
 lib/wbias-rwlock-fastpath.c  |  204 ++++++++++++
 lib/wbias-rwlock.c           |  679 +++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 1445 insertions(+)

Index: linux-2.6-lttng/include/linux/wbias-rwlock.h
===================================================================
@@ -0,0 +1,548 @@
+#ifndef _LINUX_WBIAS_RWLOCK_H
+#define _LINUX_WBIAS_RWLOCK_H
+
+/*
+ * Writer-biased low-latency rwlock
+ *
+ * Allows writer bias wrt readers threads and also minimally impact the irq
+ * latency of the system.
+ *
+ * Mathieu Desnoyers <[email protected]>
+ * August 2008
+ */
+
+#include <linux/hardirq.h>
+#include <linux/wait.h>
+
+#include <asm/atomic.h>
+
+/*
+ * Those are the maximum number of writers and readers for each context.
+ * Carefully chosen using a precise rule of thumb.
+ * The readers and writers will busy-loop when the count reaches its max,
+ * therefore no overflow is possible. The number of execution threads which can
+ * enter a specific lock or subscribe for it is MAX - 1 (because 0 has to be
+ * counted). Therefore, the minimum values for those MAX is 2, which allows 0 or
+ * 1 execution context to hold the lock or subscribe at any given time.
+ *
+ * General rule : there should be no reader from context lower than the priority
+ * of the writer. e.g. if a writer lock is taken in softirq context or when
+ * softirqs are disabled, only softirq and irq readers are allowed.
+ *
+ * A writer should use the lock primitives protecting it against the highest
+ * reader priority which reads the structure.
+ *
+ * Must keep 5 more bits for writer :
+ * WRITER_MUTEX, SOFTIRQ_WMASK, HARDIRQ_WOFFSET, WQ_MUTEX, WQ_ACTIVE
+ *
+ * PTHREAD stands for preemptable thread.
+ * NPTHREAD stands for non-preemptable thread.
+ *
+ * The ordering of WQ_MUTEX, ACTIVE_MUTEX wrt the checks done by the
+ * busy-looping/waiting threads is tricky. WQ_MUTEX protects the waitqueue and
+ * ACTIVE_MUTEX changes. WQ_MUTEX must be taken with interrupts off.
+ *
+ * Upon unlock, the following sequence is done :
+ * - atomically unlock and return the lock value, which contains the WQ_MUTEX
+ *   and ACTIVE_MUTEX at the moment of the unlock.
+ * - check if either ACTIVE_MUTEX or WQ_MUTEX are set, if so :
+ *   - take WQ_MUTEX
+ *   - wake a thread
+ *   - release WQ_MUTEX
+ *
+ * When a thread is ready to be added to the wait queue :
+ * - the last busy-looping iteration fails.
+ * - take the WQ_MUTEX
+ * - check again for the failed condition, since its status may have changed
+ *   since the busy-loop failed. If the condition now succeeds, return to
+ *   busy-looping after releasing the WQ_MUTEX.
+ * - Add the current thread to the wait queue, change state.
+ * - Atomically release WQ_MUTEX and set WQ_ACTIVE if the list passed from
+ *   inactive to active.
+ *
+ * Upon wakeup :
+ * - take WQ_MUTEX
+ * - Set state to running, remove from the wait queue.
+ * - Atomically release WQ_MUTEX and clear WQ_ACTIVE if the list passed to
+ *   inactive.
+ */
+
+#ifdef CONFIG_DEBUG_WBIAS_RWLOCK
+#define PTHREAD_RMAX	2
+#define NPTHREAD_RMAX	2
+#define SOFTIRQ_RMAX	2
+#define HARDIRQ_RMAX	2
+
+#define PTHREAD_WMAX	2
+#define NPTHREAD_WMAX	2
+#elif (BITS_PER_LONG == 32)
+#define PTHREAD_RMAX	64
+#define NPTHREAD_RMAX	16
+#define SOFTIRQ_RMAX	16
+#define HARDIRQ_RMAX	8
+
+#define PTHREAD_WMAX	32
+#define NPTHREAD_WMAX	16
+#else
+#define PTHREAD_RMAX	16384
+#define NPTHREAD_RMAX	2048
+#define SOFTIRQ_RMAX	512
+#define HARDIRQ_RMAX	256
+
+#define PTHREAD_WMAX	512
+#define NPTHREAD_WMAX	256
+#endif
+
+#define PTHREAD_ROFFSET		1UL
+#define PTHREAD_RMASK		((PTHREAD_RMAX - 1) * PTHREAD_ROFFSET)
+#define NPTHREAD_ROFFSET	(PTHREAD_RMASK + 1)
+#define NPTHREAD_RMASK		((NPTHREAD_RMAX - 1) * NPTHREAD_ROFFSET)
+#define SOFTIRQ_ROFFSET		((NPTHREAD_RMASK | PTHREAD_RMASK) + 1)
+#define SOFTIRQ_RMASK		((SOFTIRQ_RMAX - 1) * SOFTIRQ_ROFFSET)
+#define HARDIRQ_ROFFSET		\
+	((SOFTIRQ_RMASK | NPTHREAD_RMASK | PTHREAD_RMASK) + 1)
+#define HARDIRQ_RMASK		((HARDIRQ_RMAX - 1) * HARDIRQ_ROFFSET)
+
+#define PTHREAD_WOFFSET	\
+	((HARDIRQ_RMASK | SOFTIRQ_RMASK | NPTHREAD_RMASK | PTHREAD_RMASK) + 1)
+#define PTHREAD_WMASK	((PTHREAD_WMAX - 1) * PTHREAD_WOFFSET)
+#define NPTHREAD_WOFFSET ((PTHREAD_WMASK | HARDIRQ_RMASK | SOFTIRQ_RMASK | \
+			NPTHREAD_RMASK | PTHREAD_RMASK) + 1)
+#define NPTHREAD_WMASK	((NPTHREAD_WMAX - 1) * NPTHREAD_WOFFSET)
+#define WRITER_MUTEX	((PTHREAD_WMASK | NPTHREAD_WMASK | HARDIRQ_RMASK | \
+			SOFTIRQ_RMASK | NPTHREAD_RMASK | PTHREAD_RMASK) + 1)
+#define SOFTIRQ_WMASK		(WRITER_MUTEX << 1)
+#define SOFTIRQ_WOFFSET		SOFTIRQ_WMASK
+#define HARDIRQ_WMASK		(SOFTIRQ_WMASK << 1)
+#define HARDIRQ_WOFFSET		HARDIRQ_WMASK
+#define WQ_MUTEX		(HARDIRQ_WMASK << 1)
+#define WQ_ACTIVE		(WQ_MUTEX << 1)
+
+#define NR_PREEMPT_BUSY_LOOPS	100
+
+typedef struct wbias_rwlock {
+	atomic_long_t v;
+	wait_queue_head_t wq_read;	/* Preemptable readers wait queue */
+	wait_queue_head_t wq_write;	/* Preemptable writers wait queue */
+} wbias_rwlock_t;
+
+#define __RAW_WBIAS_RWLOCK_UNLOCKED	{ 0 }
+
+#define __WBIAS_RWLOCK_UNLOCKED(x)					\
+	{								\
+		.v = __RAW_WBIAS_RWLOCK_UNLOCKED,			\
+		.wq_read = __WAIT_QUEUE_HEAD_INITIALIZER((x).wq_read),	\
+		.wq_write = __WAIT_QUEUE_HEAD_INITIALIZER((x).wq_write),\
+	}
+
+#define DEFINE_WBIAS_RWLOCK(x)	wbias_rwlock_t x = __WBIAS_RWLOCK_UNLOCKED(x)
+
+/*
+ * Internal slow paths.
+ */
+extern int _wbias_read_lock_slow(wbias_rwlock_t *rwlock,
+		long v, long roffset, long rmask, long wmask, int trylock);
+extern int _wbias_read_lock_slow_preempt(wbias_rwlock_t *rwlock,
+		long v, long roffset, long rmask, long wmask, int trylock);
+extern void _wbias_write_lock_irq_slow(wbias_rwlock_t *rwlock, long v);
+extern int _wbias_write_trylock_irq_else_subscribe_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern int _wbias_write_trylock_irq_subscribed_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern void _wbias_write_lock_bh_slow(wbias_rwlock_t *rwlock, long v);
+extern int _wbias_write_trylock_bh_else_subscribe_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern int _wbias_write_trylock_bh_subscribed_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern void _wbias_write_lock_atomic_slow(wbias_rwlock_t *rwlock, long v);
+extern int
+_wbias_write_trylock_atomic_else_subscribe_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern int _wbias_write_trylock_atomic_subscribed_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern void _wbias_write_lock_slow(wbias_rwlock_t *rwlock, long v);
+extern int _wbias_write_trylock_else_subscribe_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern int _wbias_write_trylock_subscribed_slow(wbias_rwlock_t *rwlock,
+		long v);
+extern void _wbias_rwlock_wakeup(wbias_rwlock_t *rwlock, long v);
+
+static inline void wbias_rwlock_preempt_check(wbias_rwlock_t *rwlock, long v)
+{
+	if (unlikely(v & (WQ_ACTIVE | WQ_MUTEX)))
+		_wbias_rwlock_wakeup(rwlock, v);
+}
+
+/*
+ * rwlock-specific latency tracing, maps to standard macros by default.
+ */
+#ifdef CONFIG_WBIAS_RWLOCK_LATENCY_TEST
+#include <linux/wbias-latency-trace.h>
+#else
+static inline void wbias_rwlock_profile_latency_reset(void)
+{ }
+static inline void wbias_rwlock_profile_latency_print(void)
+{ }
+
+#define wbias_rwlock_irq_save(flags)	local_irq_save(flags)
+#define wbias_rwlock_irq_restore(flags)	local_irq_restore(flags)
+#define wbias_rwlock_irq_disable()	local_irq_disable()
+#define wbias_rwlock_irq_enable()	local_irq_enable()
+#define wbias_rwlock_bh_disable()	local_bh_disable()
+#define wbias_rwlock_bh_enable()	local_bh_enable()
+#define wbias_rwlock_bh_enable_ip(ip)	local_bh_enable_ip(ip)
+#define wbias_rwlock_preempt_disable()	preempt_disable()
+#define wbias_rwlock_preempt_enable()	preempt_enable()
+#define wbias_rwlock_preempt_enable_no_resched()	\
+		preempt_enable_no_resched()
+#endif
+
+
+/*
+ * API
+ */
+
+
+/*
+ * This table represents which write lock should be taken depending on the
+ * highest priority read context and the write context used.
+ *
+ * e.g. given the highest priority context from which we take the read lock is
+ * interrupt context (IRQ) and that we always use the write lock from
+ * non-preemptable context (NP), we should use the IRQ version of the write
+ * lock.
+ *
+ * X means : don't !
+ *
+ * Highest priority reader context / Writer context   P     NP    BH    IRQ
+ * ------------------------------------------------------------------------
+ * P                                                | P     X     X     X
+ * NP                                               | NP    NP    X     X
+ * BH                                               | BH    BH    BH    X
+ * IRQ                                              | IRQ   IRQ   IRQ   IRQ
+ */
+
+
+/* Reader lock */
+
+/*
+ * many readers, from irq/softirq/thread context.
+ * protects against writers.
+ */
+
+/*
+ * Called from interrupt disabled or interrupt context.
+ */
+static inline void wbias_read_lock_irq(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, HARDIRQ_ROFFSET);
+	if (likely(!v))
+		return;
+	_wbias_read_lock_slow(rwlock, v,
+		HARDIRQ_ROFFSET, HARDIRQ_RMASK, HARDIRQ_WMASK, 0);
+}
+
+static inline int wbias_read_trylock_irq(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, HARDIRQ_ROFFSET);
+	if (likely(!v))
+		return 1;
+	return _wbias_read_lock_slow(rwlock, v,
+		HARDIRQ_ROFFSET, HARDIRQ_RMASK, HARDIRQ_WMASK, 1);
+}
+
+static inline void wbias_read_unlock_irq(wbias_rwlock_t *rwlock)
+{
+	long v;
+	v = atomic_long_sub_return(HARDIRQ_ROFFSET, &rwlock->v);
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+
+/*
+ * Called from softirq context.
+ */
+
+static inline void wbias_read_lock_bh(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, SOFTIRQ_ROFFSET);
+	if (likely(!v))
+		return;
+	_wbias_read_lock_slow(rwlock, v,
+		SOFTIRQ_ROFFSET, SOFTIRQ_RMASK, SOFTIRQ_WMASK, 0);
+}
+
+static inline int wbias_read_trylock_bh(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, SOFTIRQ_ROFFSET);
+	if (likely(!v))
+		return 1;
+	return _wbias_read_lock_slow(rwlock, v,
+		SOFTIRQ_ROFFSET, SOFTIRQ_RMASK, SOFTIRQ_WMASK, 1);
+}
+
+static inline void wbias_read_unlock_bh(wbias_rwlock_t *rwlock)
+{
+	long v;
+	v = atomic_long_sub_return(SOFTIRQ_ROFFSET, &rwlock->v);
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+
+/*
+ * Called from non-preemptable thread context.
+ */
+
+static inline void wbias_read_lock_inatomic(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, NPTHREAD_ROFFSET);
+	if (likely(!v))
+		return;
+	_wbias_read_lock_slow(rwlock, v,
+		NPTHREAD_ROFFSET, NPTHREAD_RMASK,
+		NPTHREAD_WMASK | WRITER_MUTEX, 0);
+}
+
+static inline int wbias_read_trylock_inatomic(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, NPTHREAD_ROFFSET);
+	if (likely(!v))
+		return 1;
+	return _wbias_read_lock_slow(rwlock, v,
+		NPTHREAD_ROFFSET, NPTHREAD_RMASK,
+		NPTHREAD_WMASK | WRITER_MUTEX, 1);
+}
+
+static inline void wbias_read_unlock_inatomic(wbias_rwlock_t *rwlock)
+{
+	long v;
+	v = atomic_long_sub_return(NPTHREAD_ROFFSET, &rwlock->v);
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+
+/*
+ * Called from preemptable thread context.
+ */
+
+static inline void wbias_read_lock(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, PTHREAD_ROFFSET);
+	if (likely(!v))
+		return;
+	_wbias_read_lock_slow_preempt(rwlock, v,
+		PTHREAD_ROFFSET, PTHREAD_RMASK,
+		PTHREAD_WMASK | NPTHREAD_WMASK | WRITER_MUTEX, 0);
+}
+
+static inline int wbias_read_trylock(wbias_rwlock_t *rwlock)
+{
+	long v = atomic_long_cmpxchg(&rwlock->v, 0, PTHREAD_ROFFSET);
+	if (likely(!v))
+		return 1;
+	return _wbias_read_lock_slow_preempt(rwlock, v,
+		PTHREAD_ROFFSET, PTHREAD_RMASK,
+		PTHREAD_WMASK | NPTHREAD_WMASK | WRITER_MUTEX, 1);
+}
+
+static inline void wbias_read_unlock(wbias_rwlock_t *rwlock)
+{
+	long v;
+	v = atomic_long_sub_return(PTHREAD_ROFFSET, &rwlock->v);
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+
+/*
+ * Automatic selection of the right locking primitive depending on the
+ * current context. Should be used when the context cannot be statically
+ * determined or as a compatibility layer for the old rwlock.
+ */
+static inline void wbias_read_lock_generic(wbias_rwlock_t *rwlock)
+{
+	if (in_irq() || irqs_disabled())
+		wbias_read_lock_irq(rwlock);
+	else if (in_softirq())
+		wbias_read_lock_bh(rwlock);
+	else if (in_atomic())
+		wbias_read_lock_inatomic(rwlock);
+	else
+		wbias_read_lock(rwlock);
+}
+
+static inline int wbias_read_trylock_generic(wbias_rwlock_t *rwlock)
+{
+	if (in_irq() || irqs_disabled())
+		return wbias_read_trylock_irq(rwlock);
+	else if (in_softirq())
+		return wbias_read_trylock_bh(rwlock);
+	else if (in_atomic())
+		return wbias_read_trylock_inatomic(rwlock);
+	else
+		return wbias_read_trylock(rwlock);
+}
+
+static inline void wbias_read_unlock_generic(wbias_rwlock_t *rwlock)
+{
+	if (in_irq() || irqs_disabled())
+		wbias_read_unlock_irq(rwlock);
+	else if (in_softirq())
+		wbias_read_unlock_bh(rwlock);
+	else if (in_atomic())
+		wbias_read_unlock_inatomic(rwlock);
+	else
+		wbias_read_unlock(rwlock);
+}
+
+/* Writer Lock */
+
+
+/*
+ * Safe against other writers in same context.
+ * If used in irq handler or with irq off context, safe against :
+ * - irq readers.
+ * If used in softirq handler or softirq off context, safe against :
+ * - irq/softirq readers.
+ * If used in non-preemptable context, safe against :
+ * - irq/softirq/non-preemptable readers.
+ * If used in preemptable context, safe against :
+ * - irq/softirq/non-preemptable/preemptable readers.
+ *
+ * Write lock use :
+ *  wbias_write_lock_irq(&lock);
+ *  ...
+ *  wbias_write_unlock_irq(&lock);
+ *
+ * or
+ *
+ * int i;
+ *
+ * repeat:
+ *  if (wbias_write_trylock_irq_else_subscribe(&lock))
+ *    goto locked;
+ *  for (i = 0; i < NR_LOOPS; i++)
+ *    if (wbias_write_trylock_irq_subscribed(&lock))
+ *      goto locked;
+ *  do_failed_to_grab_lock(...);
+ *  wbias_write_unsubscribe(&lock);
+ *  goto repeat;
+ * locked:
+ *  ...
+ * unlock:
+ *  wbias_write_unlock_irq(&lock);
+ */
+void wbias_write_lock_irq(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_irq_else_subscribe(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_irq_subscribed(wbias_rwlock_t *rwlock);
+
+static inline void wbias_write_unlock_irq(wbias_rwlock_t *rwlock)
+{
+	long v;
+	/*
+	 * atomic_long_sub makes sure we commit the data before reenabling
+	 * the lock.
+	 */
+	v = atomic_long_sub_return(HARDIRQ_WOFFSET
+			| SOFTIRQ_WOFFSET | WRITER_MUTEX,
+			&rwlock->v);
+	wbias_rwlock_irq_enable();
+	wbias_rwlock_bh_enable();
+	wbias_rwlock_preempt_enable();
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+/*
+ * Safe against other writers in same context.
+ * If used in softirq handler or softirq off context, safe against :
+ * - softirq readers.
+ * If used in non-preemptable context, safe against :
+ * - softirq/npthread readers.
+ * If used in preemptable context, safe against :
+ * - softirq/npthread/pthread readers.
+ */
+void wbias_write_lock_bh(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_bh_else_subscribe(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_bh_subscribed(wbias_rwlock_t *rwlock);
+
+static inline void wbias_write_unlock_bh(wbias_rwlock_t *rwlock)
+{
+	long v;
+	/*
+	 * atomic_long_sub makes sure we commit the data before reenabling
+	 * the lock.
+	 */
+	v = atomic_long_sub_return(SOFTIRQ_WOFFSET | WRITER_MUTEX, &rwlock->v);
+	wbias_rwlock_bh_enable();
+	wbias_rwlock_preempt_enable();
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+/*
+ * Safe against other writers in same context.
+ * If used in non-preemptable context, safe against :
+ * - non-preemptable readers.
+ * If used in preemptable context, safe against :
+ * - non-preemptable and preemptable thread readers.
+ */
+void wbias_write_lock_atomic(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_atomic_else_subscribe(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_atomic_subscribed(wbias_rwlock_t *rwlock);
+
+static inline void wbias_write_unlock_atomic(wbias_rwlock_t *rwlock)
+{
+	long v;
+	/*
+	 * atomic_long_sub makes sure we commit the data before reenabling
+	 * the lock.
+	 */
+	v = atomic_long_sub_return(WRITER_MUTEX, &rwlock->v);
+	wbias_rwlock_preempt_enable();
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+/*
+ * Safe against other writers in same context.
+ * Safe against preemptable thread readers.
+ */
+void wbias_write_lock(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_else_subscribe(wbias_rwlock_t *rwlock);
+int wbias_write_trylock_subscribed(wbias_rwlock_t *rwlock);
+
+static inline void wbias_write_unlock(wbias_rwlock_t *rwlock)
+{
+	long v;
+	/*
+	 * atomic_long_sub makes sure we commit the data before reenabling
+	 * the lock.
+	 */
+	v = atomic_long_sub_return(WRITER_MUTEX, &rwlock->v);
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+/*
+ * Unsubscribe writer after a failed trylock.
+ * Should not be called after a successful trylock, since it unsubscribes
+ * when the lock is successfully taken.
+ */
+static inline void wbias_write_unsubscribe_atomic(wbias_rwlock_t *rwlock)
+{
+	long v;
+	v = atomic_long_sub_return(PTHREAD_WOFFSET | NPTHREAD_WOFFSET,
+		&rwlock->v);
+	wbias_rwlock_preempt_enable();
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+#define wbias_write_unsubscribe_irq(rwlock)	\
+	wbias_write_unsubscribe_atomic(rwlock)
+#define wbias_write_unsubscribe_bh(rwlock)	\
+	wbias_write_unsubscribe_atomic(rwlock)
+
+static inline void wbias_write_unsubscribe(wbias_rwlock_t *rwlock)
+{
+	long v;
+	v = atomic_long_sub_return(PTHREAD_WOFFSET, &rwlock->v);
+	wbias_rwlock_preempt_check(rwlock, v);
+}
+
+#endif /* _LINUX_WBIAS_RWLOCK_H */

Index: linux-2.6-lttng/lib/Makefile
===================================================================
@@ -43,6 +43,13 @@ obj-$(CONFIG_DEBUG_PREEMPT) += smp_proce
 obj-$(CONFIG_DEBUG_LIST) += list_debug.o
 obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
 
+obj-y += wbias-rwlock.o
+ifneq ($(CONFIG_HAVE_WBIAS_RWLOCK_FASTPATH),y)
+obj-y += wbias-rwlock-fastpath.o
+endif
+obj-$(CONFIG_WBIAS_RWLOCK_LATENCY_TEST) += wbias-rwlock-latency-trace.o
+
+
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
   lib-y += dec_and_lock.o
 endif

Index: linux-2.6-lttng/lib/Kconfig
===================================================================
@@ -157,4 +157,7 @@ config CHECK_SIGNATURE
 config HAVE_LMB
 	boolean
 
+config HAVE_WBIAS_RWLOCK_FASTPATH
+	def_bool n
+
 endmenu

Index: linux-2.6-lttng/lib/Kconfig.debug
===================================================================
@@ -680,6 +680,10 @@ config FAULT_INJECTION_STACKTRACE_FILTER
 	help
 	  Provide stacktrace filter for fault-injection capabilities
 
+config DEBUG_WBIAS_RWLOCK
+	boolean "Debug writer-biased rwlock"
+	help
+
 config LATENCYTOP
 	bool "Latency measuring infrastructure"
 	select FRAME_POINTER if !MIPS

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

I stopped reading right there.

Why?

Because that is already crap.

Go look at my code once more. Go look at how it has 128 bits of data, exactly so that it DOES NOT HAVE TO LIMIT THE NUMBER OF READERS.

And then go look at it again.

Look at it five times, and until you can understand that it still uses just a 32-bit word for the fast-path and no unnecessarily crap in it, but it actually has 128 bits of data for all the slow paths, don't bother emailing me any new versions.

Please. You -still- apparently haven't looked at it, at least not enough to understand the _point_ of it. You still go on about trying to fit in three or four different numbers in that one word. Even though the whole point of my rwlock is that you need exactly _one_ count (active writers), and _one_ bit (active reader) and _one_ extra bit ("contention, go to slow path, look at the other bits ONLY IN THE SLOW PATH!")

That leaves 30 bits for readers. If you still think you need to "limit the number of readers", then you aren't getting it.

Linus

Side note: the actual main rwlock thing is designed for a 64-bit word and the waiters separately as two 32-bit words, so it doesn't really do what I describe, but that's actually because the whole sleeping thing is _harder_ than a spinning thing, and has races with wakeups etc.

A spinning thing, in contrast, is pretty trivial.

So here's what I think your code should be like:

rdlock:

	movl $4,%eax
	lock ; xaddl %eax,(%rdi)
	testl $3,%eax
	jne __rdlock_slowpath
	ret

rwlock:

	xorl %eax,%eax
	movl $1,%edx
	lock ; cmpxchgl %edx,(%rdi)
	jne __rwlock_slowpath
	ret

rdunlock:

	lock ; subl $4,(%rdi)
	ret

rwunlock:

	lock ; andl $~1,(%rdi)
	ret

and I'm pretty damn sure that that should be totally sufficient for a spinning rwlock. The non-spinning one is more complex just because the unlock paths need to guarantee that something gets woken up, that just isn't an issue when you do spinlocks.

Now, in the slow-path:
- on the rwlock slowpath side, set bit#1 to make sure that readers get caught in the slowpath
- then do a *separate* count of how many pending readers and writers (ie the ones that got caught into the slowpath) you have (one word each is probably fine), and then the slowpaths can just do the right thing depending on whether there are pending readers/writers.

See? The main lock needs not worry about number of writers AT ALL, because it's totally irrelevant. So don't worry about running out of bits. You won't. Just put those counts somewhere else! The only thing that matters for the main lock word is whether there are active readers (30 bits), and whether there is an active writer (there can only ever be one: 1 bit), and whether new readers should be trapped (1 bit).

If you worry about overflows, you're doing something wrong.

Linus

Ok, so change that "testl" to "andl" to shave two bytes, and then make the whole lock structure look something like this:

	struct rwlock {
		u32 fastpath;
		u32 pending_readers;
		u32 pending_writers;
	};

and then the slowpath would look something like this:

	void __rdlock_slowpath(struct rwlock *lock)
	{
		/* Move the read count to the pending path and undo our xadd */
		atomic_add(1, &lock->pending_readers);
		atomic_sub(4, &lock->fastpath);

		for (;;) {
			unsigned fastpath;
			while (lock->pending_writers)
				cpu_relax();
			while ((fastpath = lock->fastpath) & 1)
				cpu_relax();
			/* This will also undo the contention bit */
			if (atomic_cmpxchg(&lock->fastpath, fastpath, (fastpath & ~2)+4)) == fastpath);
				break;
		}
		atomic_sub(1, &lock->pending_readers);
	}

and yes, there are more atomic accesses in there than would be necessary, in that if you can cram the whole thing into a single 64-bit word you can do both the initial pending fixup and the final cmpxchg/pending_readers thing as a single locked 64-bit op, but hey, the above is fairly simple.

You could also just use a spinlock to protect all the other data, of course.

There are fairness issues here too - do you really want to wait for pending writes every time, or just the first time through the loop? It depends on just how much you want to prefer writers.

The slow-paths for writers is similar, and has similar issues for the fairness issue. For example, instead of a simple "pending_writers" count, maybe you want to use a ticket lock there, to make writers be fair among themselves? Of course, the hope would be that there would never be that kind of contention by pure writers, so that sounds like overdesign, but the thing I'm trying to point out here is that this is all a separate decision from the actual fast-path, and having fair writers doesn't necessarily mean that the fastpath has to even know/care.

The placement of the counts is also something that can be optimized. For example, on teh assumption that readers are much more common than writers, I put the "pending_readers" next to the "fastpath" lock, exactly so that you -can- do the update of both with a single 64-bit locked access, even if the fastpath just used a 32-bit one. But then you should at least add a "__attribute__((aligned(8)))" to the structure definition.

And maybe you want to share the slowpath between all the irq-off etc versions, in which case you need to make the "irq enable while waiting" thing be conditional.

And if the write path wants to wait for pending readers, and you want to make _that_ fair too, then you want to have that punch through if the writer is in an interrupt, to avoid deadlocks. And again, you might want to make the reader thing be some kind of ticket-based system, so that writers can wait for the readers that came in _before_ that writer, but not to later ones.

But again - none of that has anything to do with the fast-path. The fast-path remains exactly the same for all these issues.

And finally: NONE of the code is at all tested. It's all just written in my MUA. Caveat emptor.

Linus

[...]

Hi Linus,

After having had a look 15 times more at your rwlock code, and again at your answer, in loops, I come to the conclusion that I made a terrible job at explaining the core idea beneath my rwlock design. So let's try to make it more obvious. I am going to keep this explanation short.

First, the goal : to kill latency induced by rwlocks.

Now, let me explain why I need at least not one, but _four different_ contention bits. Simply because there are four types of contention, one for each execution context which may take the read lock. (irq, softirq, non-preemptable, preemptable)

So let's suppose I share the rwlock between non-preemptable writers, non-preemptable readers and interrupt context readers. The idea is this:
If I want to take the write lock, I'll have to protect against both non-preemptable and interrupt readers (and also against other writers).

A way to do that without inducing high interrupt latency with current rwlocks would be for the writer to take _two_ locks, not just one. The first excludes preemptable readers and the second excludes irqs. So we have :

For the writer :

preempt_disable();
write_lock(&preempt_rwlock);

local_irq_disable();
write_lock(&irq_rwlock);

/* Write access */

write_unlock(&irq_rwlock);
local_irq_enable();

write_unlock(&preempt_rwlock);
preempt_enable();

And the readers :

Interrupt :
read_lock(&irq_rwlock);
...
read_unlock(&irq_rwlock);

non-preemptable :
read_lock(&preempt_rwlock);
...
read_unlock(&preempt_rwlock);

If you still wonder why I need to take two locks, thus elevating the context priority by exluding one context at a time, we can go to this example showing why current rwlock use in the kernel produces such high latencies. The current use is :

For the writer, we exclude all the readers in one go :

local_irq_disable();
write_lock(&big_lock_against_all_readers);

/* Write access */

write_unlock(&big_lock_against_all_readers);
local_irq_enable();

write_unlock(&preempt_rwlock);
preempt_enable();

And for the readers :

Interrupt :
read_lock(&big_lock_against_all_readers);
...
read_unlock(&big_lock_against_all_readers);

non-preemptable :
read_lock(&big_lock_against_all_readers);
...
read_unlock(&big_lock_against_all_readers);

And where is the problem ? In the following execution sequence :
- non-preemptable reader takes the read lock
- writer disables irqs
- writer takes the write lock, contended by the reader
- hrm, the reader can take a while to complete, may be iterating on the tasklist, interrupted by irqs and softirqs...

This contention is pretty bad because interrupts are disabled while we busy-loop. And yes, the new implementation you proposed *does* suffer from the same problem. Now if you go in the multiple locks scenario I explained above, you'll notice that you don't have this problem. Then comes the question : how can we efficiently take many locks, one per reader execution context we want to exclude.

This is where we need to have at _least_ one contention bit _per context_. Because at a given moment, non-preemptable readers can be contended, but not irq readers. But we also have to know when a particular reader execution context is locked out so that the writer knows it has exclusive access and can therefore either disable interrupts and exclude interrupt readers or finally access the critical section. Therefore, we need to keep one reader count _per context_, which makes that 4 reader counts (irq, softirq, non-preemptable, preemptable). And that's where we start being short on bits.

But my current maximums for number of readers is not a problem, especially because I detect overflow beforehand using cmpxchg and busy-loop in the rare event these counters would be full. And I am not limited to NR_CPUS _at all_ anymore, as shows these constants :

#define PTHREAD_RMAX    16384
#define NPTHREAD_RMAX   2048
#define SOFTIRQ_RMAX    512
#define HARDIRQ_RMAX    256

So, before discussing optimization or implementation details further, I'd like to know if I made myself clear enough about the design goal. If not, then again I must be doing a terrible job at explaining it and please let me know. I made a big patch cleanup after v8, so you might want to wait for us to come to an understanding before going through a next patch release.

Mathieu

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

No. You need _one_ contention bit in the fast-path.

Then, as you get into the slow-path, you can decide on four different behaviours.

Quite frankly, I don't think this discussion is going anywhere. I don't think I'd take anything from you, since you seem to have a really hard time separating out the issue of fast-path and slow-path. So I'm simply not going to bother, and I'm not going to expect to merge your work.

Sorry, but it simply isn't worth my time or effort.

Linus

Hi,

OK, I now see how I can apply this contention bit idea to my algo. Actually, the point I just fixed in my head is that this bit will be a "MAY_CONTEND" bit, which could let higher priority readers access the lock in the slow path. Only one fast path reader count will be required, just as you said.

Sorry about taking that much time to get my head around this. Thanks for your helpful explanations and your time.

Mathieu

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

EXACTLY.

It's not even necessarily a "contention" bit per se - it's literally a "readers have to take the slow-path" bit (writers will obviously _always_ take the slowpath if there is any non-zero value at all, so they don't need it).

Then, the slow-path might actually decide that "hey, there is no _actual_ writer there yet - just some _waiting_ writer, but since this read lock is in an interrupt context, we have to let it go through _despite_ the fact that the lock is contended in order to avoid deadlock".

So it allows a fast-path for the trivial cases that is literally just a couple of instructions long, and that is nice not just because of performance issues, but because it then means that you can entirely ignore all those things in the slow path. It also means that everybody can look at the fast-path and decide that "ok, the fast-path really is optimal".

That fast-path is what a lot of people care more about than just about anything else.

The slow-path, in comparison, can be in C, and can do all those checks like "are we in an (sw-)interrupt handler?" and basically prioritize certain classes of people.

Linus

First of all, let me say I don't pretend to understand formally how you deal with overflow-after-the-fact, as unlikely as it is.

However, it seems to me to be an easy way to avoid it. Simply by changing the read-test mask to $0x80000003, you will kick the code down the slow path once the read counter reaches $0x80000004 (2^29+1 readers), where you can do any necessary fixup -- or BUG() -- at leisure.

This fastpath ends up being identical in size and performance to the one you posted, although yours could be reduced by changing the test to a testb instruction -- at the almost certainly unacceptable expense of taking a partial-register stall on the CPUs that have those.

-hpa

Just make sure it can't overflow. With spinlocks, you are guaranteed that you won't have more than NR_CPU's thing, so 20 bits is pretty safe. 30 bits is ridiculously safe.

Sure, you could do things like that, but that sounds like a separate "debugging" version, not the main one.

Well, you could just change the "testl $3,%eax" into an "andl $3,%eax", and it will be two bytes shorter with no partial register stall.

I forgot that "testl" doesn't have the byte immediate version.

Linus

New lock types should come with lockdep support.

Also, if you're serious about -rt, you'll need to consider full PI.