Skip to contentSkip to conversation

Priority Sifting Reader-Writer Lock v13

RFC PATCH New Mathieu Desnoyers 1 participant 6 messages Sep 9, 2008

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

cover Priority Sifting Reader-Writer Lock v13

Hi,

Here is the reworked version of what was initially called "Fair rwlock", then "writer-biased rwlock". Hopefully the naming should now better represent the innovation in this reader-writer locking scheme.

Thanks to Linus' patient explanations, it uses a single atomic op on a 32 bit variable in the fast path. The bright side of this is instruction-wise compactness of the fast path and that there is practically no limitation on the number of readers or writers. The downside is added memory ordering complexity between fast and slow path variables in the slow path.

Mathieu

Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#1 lore raw

RFC PATCH 1/5 Priority Sifting Reader-Writer Lock v13

Priority Sifting Reader-Writer Lock (psrwlock) excludes reader execution contexts one at a time, thus increasing the writer priority in stages. It favors writers against readers, but lets higher priority readers access the lock even when there are subscribed writers waiting for the lock at a lower priority. Very frequent writers could starve reader threads.

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.

TODO :
- Add writer-writer fairness using "tickets" instead of single-bit mutexes

- Add lockdep support
- Create a compatibility layer to make port of current rwlock easier
- Use priority barrel (shifting the reader priority bits in a loop to generalize the number of reader priority up to a maximum of 64 with a u64).
- For -rt : support priority inheritance

Other name ideas (RFC) :
- Priority Sifting Reader-Writer Lock
- Staircase Reader-Writer Lock
- Staged Priority Elevation Reader-Writer Lock

CC Linus Torvalds <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
CC Jeremy Fitzhardinge <[email protected]>
CC Andrew Morton <[email protected]>
CC Ingo Molnar <[email protected]>
CC "Paul E. McKenney" <[email protected]>
CC Peter Zijlstra <[email protected]>
CC Joe Perches <[email protected]>
CC Wei Weng <[email protected]>
---
 include/linux/psrwlock-types.h |   92 ++++
 include/linux/psrwlock.h       |  384 ++++++++++++++++++
 lib/Kconfig.debug              |    3 
 lib/Makefile                   |    3 
 lib/psrwlock.c                 |  839 +++++++++++++++++++++++++++++++++++++++++
 5 files changed, 1321 insertions(+)
include/linux/psrwlock.h new file +384 -0
Index: linux-2.6-lttng/include/linux/psrwlock.h
===================================================================
@@ -0,0 +1,384 @@
+#ifndef _LINUX_PSRWLOCK_H
+#define _LINUX_PSRWLOCK_H
+
+/*
+ * Priority Sifting Reader-Writer Lock
+ *
+ * Priority Sifting Reader-Writer Lock (psrwlock) excludes reader execution
+ * contexts one at a time, thus increasing the writer priority in stages. It
+ * favors writers against reader threads, but lets higher priority readers in
+ * even when there are subscribed writers waiting for the lock at a given lower
+ * priority. Very frequent writers could starve reader threads.
+ *
+ * See psrwlock-types.h for types definitions.
+ * See psrwlock.c for algorithmic details.
+ *
+ * Mathieu Desnoyers <[email protected]>
+ * August 2008
+ */
+
+#include <linux/hardirq.h>
+#include <linux/wait.h>
+#include <linux/psrwlock-types.h>
+
+#include <asm/atomic.h>
+
+#define NR_PREEMPT_BUSY_LOOPS	100
+
+/*
+ * Uncontended word bits (32 bits)
+ *
+ * Because we deal with overflow by busy-looping waiting for the counter to
+ * decrement, make sure the maximum allowed for lower-priority execution
+ * contexts is lower than the maximum for higher priority execution contexts.
+ * Therefore, all contexts use the same counter bits, but they reach their
+ * overflow capacity one bit apart from each other (only used in the slow path).
+ *
+ * 3 bits for status
+ * 29 bits for reader count
+ *   reserve 1 high bit for irqs
+ *   reserve 1 high bit for bh
+ *   reserve 1 high bit for non-preemptable threads
+ *   26 bits left for preemptable readers count
+ */
+#define UC_READER_MAX		(1U << 29)
+#define UC_HARDIRQ_READER_MAX	UC_READER_MAX
+#define UC_SOFTIRQ_READER_MAX	(UC_HARDIRQ_READER_MAX >> 1)
+#define UC_NPTHREAD_READER_MAX	(UC_SOFTIRQ_READER_MAX >> 1)
+#define UC_PTHREAD_READER_MAX	(UC_NPTHREAD_READER_MAX >> 1)
+
+#define UC_WRITER		(1U << 0)
+#define UC_SLOW_WRITER		(1U << 1)
+#define UC_WQ_ACTIVE		(1U << 2)
+#define UC_READER_OFFSET	(1U << 3)
+#define UC_HARDIRQ_READER_MASK	((UC_HARDIRQ_READER_MAX - 1) * UC_READER_OFFSET)
+#define UC_SOFTIRQ_READER_MASK	((UC_SOFTIRQ_READER_MAX - 1) * UC_READER_OFFSET)
+#define UC_NPTHREAD_READER_MASK		\
+	((UC_NPTHREAD_READER_MAX - 1) * UC_READER_OFFSET)
+#define UC_PTHREAD_READER_MASK	((UC_PTHREAD_READER_MAX - 1) * UC_READER_OFFSET)
+#define UC_READER_MASK		UC_HARDIRQ_READER_MASK
+
+
+/*
+ * Writers in slow path count and mutexes (32 bits)
+ *
+ * 1 bit for WS_WQ_MUTEX (wait queue mutex, always taken with irqs off)
+ * 1 bit for WS_COUNT_MUTEX (protects writer count and UC_SLOW_WRITER updates,
+ *                           taken in initial writer context).
+ * 1 bit for WS_LOCK_MUTEX (single writer in critical section)
+ * 29 bits for writer count.
+ */
+#define WS_WQ_MUTEX		(1U << 0)
+#define WS_COUNT_MUTEX		(1U << 1)
+#define WS_LOCK_MUTEX		(1U << 2)
+
+#define WS_MAX			(1U << 29)
+#define WS_OFFSET		(1U << 3)
+#define WS_MASK			((WS_MAX - 1) * WS_OFFSET)
+
+
+/*
+ * Per-context slow path reader and writer count maximum, offset and mask.
+ * unsigned long type. Used to atomically detect that there is no contention in
+ * a given slow path context and subscribe a writer or let a reader take the
+ * slow path context lock.
+ */
+#define CTX_WOFFSET		(1UL << 0)
+#define CTX_WMAX		(1UL << (BITS_PER_LONG/2))
+#define CTX_WMASK		((CTX_WMAX - 1) * CTX_WOFFSET)
+
+#define CTX_ROFFSET		CTX_WMAX
+#define CTX_RMAX		(1UL << (BITS_PER_LONG/2))
+#define CTX_RMASK		((CTX_RMAX - 1) * CTX_ROFFSET)
+
+
+/*
+ * Internal slow paths.
+ */
+extern asmregparm
+void _psread_lock_slow_irq(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+int _psread_trylock_slow_irq(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+void _psread_lock_slow_bh(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+int _psread_trylock_slow_bh(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+void _psread_lock_slow_inatomic(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+int _psread_trylock_slow_inatomic(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+void _psread_lock_slow(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+int _psread_trylock_slow(unsigned int uc, psrwlock_t *rwlock);
+
+extern asmregparm
+void _pswrite_lock_slow(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+int _pswrite_trylock_slow(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+void _pswrite_unlock_slow(unsigned int uc, psrwlock_t *rwlock);
+extern asmregparm
+void _psrwlock_wakeup(unsigned int uc, psrwlock_t *rwlock);
+
+#ifdef CONFIG_HAVE_PSRWLOCK_ASM_CALL
+#include <asm/call_64.h>
+#else
+#define psread_lock_slow_irq		_psread_lock_slow_irq
+#define psread_trylock_slow_irq		_psread_trylock_slow_irq
+#define psread_lock_slow_bh		_psread_lock_slow_bh
+#define psread_trylock_slow_bh		_psread_trylock_slow_bh
+#define psread_lock_slow_inatomic	_psread_lock_slow_inatomic
+#define psread_trylock_slow_inatomic	_psread_trylock_slow_inatomic
+#define psread_lock_slow		_psread_lock_slow
+#define psread_trylock_slow		_psread_trylock_slow
+
+#define pswrite_lock_slow		_pswrite_lock_slow
+#define pswrite_trylock_slow		_pswrite_trylock_slow
+#define pswrite_unlock_slow		_pswrite_unlock_slow
+#define psrwlock_wakeup			_psrwlock_wakeup
+#endif
+
+/*
+ * psrwlock-specific latency tracing, maps to standard macros by default.
+ */
+#ifdef CONFIG_PSRWLOCK_LATENCY_TEST
+#include <linux/psrwlock-latency-trace.h>
+#else
+static inline void psrwlock_profile_latency_reset(void)
+{ }
+static inline void psrwlock_profile_latency_print(void)
+{ }
+
+#define psrwlock_irq_save(flags)		local_irq_save(flags)
+#define psrwlock_irq_restore(flags)		local_irq_restore(flags)
+#define psrwlock_irq_disable()			local_irq_disable()
+#define psrwlock_irq_enable()			local_irq_enable()
+#define psrwlock_bh_disable()			local_bh_disable()
+#define psrwlock_bh_enable()			local_bh_enable()
+#define psrwlock_bh_enable_ip(ip)		local_bh_enable_ip(ip)
+#define psrwlock_preempt_disable()		preempt_disable()
+#define psrwlock_preempt_enable()		preempt_enable()
+#define psrwlock_preempt_enable_no_resched()	preempt_enable_no_resched()
+#endif
+
+/*
+ * Internal preemption/softirq/irq disabling helpers. Optimized into simple use
+ * of standard local_irq_disable, local_bh_disable, preempt_disable by the
+ * compiler since wctx and rctx are constant.
+ */
+
+static inline void write_context_disable(enum psrw_prio wctx, u32 rctx)
+{
+	if (wctx != PSRW_PRIO_IRQ && (rctx & PSR_IRQ))
+		psrwlock_irq_disable();
+	else if (wctx != PSRW_PRIO_BH && (rctx & PSR_BH))
+		psrwlock_bh_disable();
+	else if (wctx != PSRW_PRIO_NP && (rctx & PSR_NPTHREAD))
+		psrwlock_preempt_disable();
+}
+
+static inline void write_context_enable(enum psrw_prio wctx, u32 rctx)
+{
+	if (wctx != PSRW_PRIO_IRQ && (rctx & PSR_IRQ))
+		psrwlock_irq_enable();
+	else if (wctx != PSRW_PRIO_BH && (rctx & PSR_BH))
+		psrwlock_bh_enable();
+	else if (wctx != PSRW_PRIO_NP && (rctx & PSR_NPTHREAD))
+		psrwlock_preempt_enable();
+}
+
+/*
+ * psrwlock_preempt_check must have a uc parameter read with a memory
+ * barrier making sure the slow path variable writes and the UC_WQ_ACTIVE flag
+ * read are done in this order (either a smp_mb() or a atomic_sub_return()).
+ */
+static inline void psrwlock_preempt_check(unsigned int uc,
+		psrwlock_t *rwlock)
+{
+	if (unlikely(uc & UC_WQ_ACTIVE))
+		psrwlock_wakeup(uc, rwlock);
+}
+
+
+/*
+ * API
+ */
+
+/* Reader lock */
+
+/*
+ * many readers, from irq/softirq/non preemptable and preemptable thread
+ * context. Protects against writers.
+ *
+ * Read lock fastpath :
+ *
+ * A cmpxchg is used here and _not_ a simple add because a lower-priority reader
+ * could block the writer while it is waiting for readers to clear the
+ * uncontended path. This would happen if, for instance, the reader gets
+ * interrupted between the add and the moment it gets to the slow path.
+ */
+
+/*
+ * Called from any context.
+ */
+static inline void psread_unlock(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_sub_return(UC_READER_OFFSET, &rwlock->uc);
+	psrwlock_preempt_check(uc, rwlock);
+}
+
+/*
+ * Called from interrupt disabled or interrupt context.
+ */
+static inline void psread_lock_irq(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return;
+	psread_lock_slow_irq(uc, rwlock);
+}
+
+static inline int psread_trylock_irq(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return 1;
+	return psread_trylock_slow_irq(uc, rwlock);
+}
+
+/*
+ * Called from softirq context.
+ */
+
+static inline void psread_lock_bh(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return;
+	psread_lock_slow_bh(uc, rwlock);
+}
+
+static inline int psread_trylock_bh(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return 1;
+	return psread_trylock_slow_bh(uc, rwlock);
+}
+
+
+/*
+ * Called from non-preemptable thread context.
+ */
+
+static inline void psread_lock_inatomic(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return;
+	psread_lock_slow_inatomic(uc, rwlock);
+}
+
+static inline int psread_trylock_inatomic(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return 1;
+	return psread_trylock_slow_inatomic(uc, rwlock);
+}
+
+
+/*
+ * Called from preemptable thread context.
+ */
+
+static inline void psread_lock(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return;
+	psread_lock_slow(uc, rwlock);
+}
+
+static inline int psread_trylock(psrwlock_t *rwlock)
+{
+	unsigned int uc = atomic_cmpxchg(&rwlock->uc, 0, UC_READER_OFFSET);
+	if (likely(!uc))
+		return 1;
+	return psread_trylock_slow(uc, rwlock);
+}
+
+
+/* Writer Lock */
+
+/*
+ * ctx is the context map showing which contexts can take the read lock and
+ * which context is using the write lock.
+ *
+ * Write lock use example, where the lock is used by readers in interrupt,
+ * preemptable context and non-preemptable context. The writer lock is taken in
+ * preemptable context.
+ *
+ * static DEFINE_PSRWLOCK(lock, PSRW_PRIO_P, PSR_IRQ | PSR_PTHREAD);
+ * CHECK_PSRWLOCK_MAP(lock, PSRW_PRIO_P, PSR_IRQ | PSR_PTHREAD);
+ *
+ *  pswrite_lock(&lock, PSRW_PRIO_P, PSR_IRQ | PSR_PTHREAD);
+ *  ...
+ *  pswrite_unlock(&lock, PSRW_PRIO_P, PSR_IRQ | PSR_PTHREAD);
+ */
+static inline
+void pswrite_lock(psrwlock_t *rwlock, enum psrw_prio wctx, u32 rctx)
+{
+	unsigned int uc;
+
+	write_context_disable(wctx, rctx);
+	/* no other reader nor writer present, try to take the lock */
+	uc = atomic_cmpxchg(&rwlock->uc, 0, UC_WRITER);
+	if (likely(!uc))
+		return;
+	else
+		pswrite_lock_slow(uc, rwlock);
+}
+
+static inline
+int pswrite_trylock(psrwlock_t *rwlock, enum psrw_prio wctx, u32 rctx)
+{
+	unsigned int uc;
+
+	write_context_disable(wctx, rctx);
+	/* no other reader nor writer present, try to take the lock */
+	uc = atomic_cmpxchg(&rwlock->uc, 0, UC_WRITER);
+	if (likely(!uc))
+		return 1;
+	else
+		return pswrite_trylock_slow(uc, rwlock);
+}
+
+static inline
+void pswrite_unlock(psrwlock_t *rwlock, enum psrw_prio wctx, u32 rctx)
+{
+	unsigned int uc;
+
+	/*
+	 * atomic_cmpxchg makes sure we commit the data before reenabling
+	 * the lock. Will take the slow path if there are active readers, if
+	 * UC_SLOW_WRITER is set or if there are threads in the wait queue.
+	 */
+	uc = atomic_cmpxchg(&rwlock->uc, UC_WRITER, 0);
+	if (likely(uc == UC_WRITER)) {
+		write_context_enable(wctx, rctx);
+		/*
+		 * no need to check preempt because all wait queue masks
+		 * were 0. An active wait queue would trigger the slow path.
+		 */
+		return;
+	}
+	/*
+	 * Go through the slow unlock path to check if we must clear the
+	 * UC_SLOW_WRITER bit.
+	 */
+	pswrite_unlock_slow(uc, rwlock);
+}
+
+#endif /* _LINUX_PSRWLOCK_H */
lib/Makefile +3 -0
Index: linux-2.6-lttng/lib/Makefile
===================================================================
@@ -43,6 +43,9 @@ obj-$(CONFIG_DEBUG_PREEMPT) += smp_proce
 obj-$(CONFIG_DEBUG_LIST) += list_debug.o
 obj-$(CONFIG_DEBUG_OBJECTS) += debugobjects.o
 
+obj-y += psrwlock.o
+obj-$(CONFIG_PSRWLOCK_LATENCY_TEST) += psrwlock-latency-trace.o
+
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
   lib-y += dec_and_lock.o
 endif
lib/psrwlock.c new file +839 -0

839 lines not on this page · raw message

lib/Kconfig.debug +3 -0
Index: linux-2.6-lttng/lib/Kconfig.debug
===================================================================
@@ -680,6 +680,9 @@ config FAULT_INJECTION_STACKTRACE_FILTER
 	help
 	  Provide stacktrace filter for fault-injection capabilities
 
+config HAVE_PSRWLOCK_ASM_CALL
+	def_bool n
+
 config LATENCYTOP
 	bool "Latency measuring infrastructure"
 	select FRAME_POINTER if !MIPS
include/linux/psrwlock-types.h new file +92 -0

92 lines not on this page · raw message

Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#2 lore raw

RFC PATCH 2/5 Priority Sifting Reader-Writer Lock Documentation

In reply to Mathieu Desnoyers

Design goal, algorithmic description and performance tests.

CC Linus Torvalds <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
CC Jeremy Fitzhardinge <[email protected]>
CC Andrew Morton <[email protected]>
CC Ingo Molnar <[email protected]>
CC "Paul E. McKenney" <[email protected]>
CC Peter Zijlstra <[email protected]>
CC Joe Perches <[email protected]>
CC Wei Weng <[email protected]>
---
 Documentation/psrwlock.txt |  440 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 440 insertions(+)
Documentation/psrwlock.txt new file +440 -0
Index: linux-2.6-lttng/Documentation/psrwlock.txt
===================================================================
@@ -0,0 +1,440 @@
+                 Priority Sifting Reader-Writer Locks
+                     Design and Performance tests
+                       Mathieu Desnoyers, 2008
+
+
+****** Design Goal ******
+
+The main design goal is to lessen the rwlock impact on the irq and softirq
+latency of the system.
+
+A typical case leading to long interrupt latencies :
+
+- 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.
+
+
+****** Description of the psrwlock algorithm ******
+
+The writer fast path uses a single bit to indicate that a fast path writer is
+active (UC_WRITER). The uncontended case is done by upgrading the priority to
+the priority of the highest priority reader (e.g. by disabling interrupts) and
+by doing a cmpxchg which sets the UC_WRITER bit atomically only if there is no
+other writer nor reader in their critical section. If there is contention caused
+by either a reader or a writer, the writer falls in the slow path.
+
+The writer slow path first sets the UC_SLOW_WRITER bit and increments the WS
+(writers in slow path) counter (the two operations are made atomic by using the
+WS_COUNT_MUTEX bit as a mutex) and then subscribes to the preemptable lock,
+which locks out the preemptable reader threads. It waits for all the preemptable
+reader threads in the slow path to exit their critical section. It then waits
+for all the "in-flight" fast path readers to exit their critical section. Then,
+it upgrades its priority by disabling preemption and does the same
+(subscription, wait for slow path readers, wait for fast path readers) for
+preemptable readers. The same is then done for bottom halves and interrupt
+contexts. One all the reader contexts has been excluded, the writer takes the
+slow path mutex, accesses the data structure.
+
+In its unlock, the writer detects if it was a fast or slow path writer by
+checking the UC_WRITER bit. A fast path writer has to clear the UC_WRITER bit
+and bring its priority back to its original state (e.g. reenabling interrupts).
+The slow path writer must unlock the mutex, lower its priority stage by stage
+(reenabling interrupt, bh, preemption). At each stage, it unsubscribes from the
+specific context. Then, it checks if it is the last writer in the slow path by
+decrementing and testing the WS counter (writers in slow path) bit. If it is the
+last writer, it clears the UC_SLOW_WRITER bit (count and bit are made atomic by
+the WS_COUNT_MUTEX bit used as a mutex).
+
+The reader does an atomic cmpxchg to check if there is any contention on the
+lock (other readers or writers in their critical section). If not, it increments
+the reader count. If there are other active readers, the first cmpxchg will
+fail, but a second cmpxchg will be taken at the beginning of the slow path if
+there are no writers contending the lock. A cmpxchg is used to take the reader
+lock instead of a simple addition because we cannot afford to take the read
+fast-path lock, even for a short period of time, while we are in a lower
+execution context while there is a writer in an higher priority execution
+context waiting for the lock. Failure to do so would result in priority
+inversion.
+
+The reader slow path waits for the slow path writer subscription count in its
+particular context to become 0. When it does, the reader atomically increments
+the reader count for this context. Then, it waits for all the fast path writers
+to exit their critical section and increments the fast path reader count. Before
+returning from the reader lock primitive, it decrements the slow path reader
+count for the context it subscribed to, behaving exactly as a fast path reader.
+
+The unlock primitive is then exactly the same for the fast and slow path
+readers: They only have to decrement the fastpath reader count.
+
+WS_WQ_MUTEX protects the waitqueue and UC_WQ_ACTIVE changes. WS_WQ_MUTEX must be
+taken with interrupts off. The ordering of operations dealing with preemptable
+threads involves that any code path which can cause a thread to be added to the
+wait queue must end with a check for UC_WQ_ACTIVE flag which leads to a wake up
+if there are pending threads in the wait queue. Also, any point where a thread
+can be woken up from the wait queue must be followed by a UC_WQ_ACTIVE check.
+Given that the UC_WQ_ACTIVE flag is tested without taking the WS_WQ_MUTEX, we
+must make sure that threads added to the waitqueue first set the UC_WQ_ACTIVE
+flag and then re-test for the condition which led them to be put to sleep.
+
+Upon unlock, the following sequence is done :
+- atomically unlock and return the lock value, which contains the UC_WQ_ACTIVE
+  bit status at the moment the unlock is done.
+- if UC_WQ_ACTIVE is set :
+  - take WS_WQ_MUTEX
+  - wake a thread
+  - release WS_WQ_MUTEX
+
+When a thread is ready to be added to the wait queue :
+- the last busy-looping iteration fails.
+- take the WS_WQ_MUTEX
+- set the UC_WQ_ACTIVE bit if the list about to pass from inactive to active.
+- 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 putting the UC_WQ_ACTIVE bit back to its original state and
+  releasing the WS_WQ_MUTEX.
+- add the current thread to the wait queue, change state.
+- release WS_WQ_MUTEX.
+
+Upon wakeup :
+- take WS_WQ_MUTEX
+- set state to running, remove from the wait queue.
+- clear UC_WQ_ACTIVE if the list passed to inactive.
+- release WS_WQ_MUTEX.
+
+A sequence similar to the unlock must be done when a trylock fails.
+
+
+****** Performance tests ******
+
+The test module is available at :
+
+http://ltt.polymtl.ca/svn/trunk/tests/kernel/test-psrwlock.c
+
+Dual quad-core Xeon 2.0GHz E5405
+
+
+**** Latency ****
+
+This section presents the detailed breakdown of latency preemption, softirq and
+interrupt latency generated by the psrwlock. In the "High contention" section,
+is compares the "irqoff latency tracer" results between standard Linux kernel
+rwlocks and the psrwlocks (tests done on wbias-rwlock v8).
+
+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 psrwlock 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 ****
+
+Number of cycles required to take the lock are benchmarked for each context.
+
+
+** get_cycles calibration **
+get_cycles takes [min,avg,max] 72,75,78 cycles, results calibrated on avg
+
+
+** Single writer test, no contention **
+
+* Writer-biased rwlocks v13
+
+writer_thread/0 iterations : 100274, lock delay [min,avg,max] 27,33,249 cycles
+writer_thread/0 iterations : 100274, unlock delay [min,avg,max] 27,30,10407 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 v13
+
+preader_thread/0 iterations : 33856510, lock delay [min,avg,max] 27,29,34035 cycles
+preader_thread/0 iterations : 33856510, unlock delay [min,avg,max] 15,20,34701 cycles
+
+* Standard rwlock, kernel 2.6.27-rc3
+
+N/A : preemption must be disabled with standard rwlocks.
+
+
+** 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 v13
+
+npreader_thread/0 iterations : 33461225, lock delay [min,avg,max] 27,30,16329 cycles
+npreader_thread/0 iterations : 33461225, unlock delay [min,avg,max] 15,19,21657 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 v13
+
+npreader_thread/0 iterations : 16885001, lock delay [min,avg,max] 27,425,40239 cycles
+npreader_thread/0 iterations : 16885001, unlock delay [min,avg,max] 15,220,18153 cycles
+npreader_thread/1 iterations : 16832690, lock delay [min,avg,max] 33,433,26841 cycles
+npreader_thread/1 iterations : 16832690, unlock delay [min,avg,max] 15,219,22329 cycles
+preader_thread/0 iterations : 17185174, lock delay [min,avg,max] 27,438,31437 cycles
+preader_thread/0 iterations : 17185174, unlock delay [min,avg,max] 15,211,30465 cycles
+preader_thread/1 iterations : 17293655, lock delay [min,avg,max] 27,435,53301 cycles
+preader_thread/1 iterations : 17293655, unlock delay [min,avg,max] 15,209,63921 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 v13
+
+writer_thread/0 iterations : 537678, lock delay [min,avg,max] 123,14021,8580813 cycles
+writer_thread/0 iterations : 537678, unlock delay [min,avg,max] 387,9070,1450053 cycles
+writer_thread/1 iterations : 536944, lock delay [min,avg,max] 123,13179,8687331 cycles
+writer_thread/1 iterations : 536944, unlock delay [min,avg,max] 363,10430,1400835 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 v13
+
+npreader_thread/0 iterations : 64652609, lock delay [min,avg,max] 27,828,67497 cycles
+npreader_thread/0 iterations : 64652609, unlock delay [min,avg,max] 15,485,202773 cycles
+npreader_thread/1 iterations : 65143310, lock delay [min,avg,max] 27,817,64569 cycles
+npreader_thread/1 iterations : 65143310, unlock delay [min,avg,max] 15,484,133611 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 v13
+
+preader_thread/0 iterations : 38484022, lock delay [min,avg,max] 27,2207,89363619 cycles
+preader_thread/0 iterations : 38484022, unlock delay [min,avg,max] 15,392,1965315 cycles
+preader_thread/1 iterations : 44661191, lock delay [min,avg,max] 27,1672,8708253 cycles
+preader_thread/1 iterations : 44661191, unlock delay [min,avg,max] 15,495,142119 cycles
+
+* Standard rwlock, kernel 2.6.27-rc3
+
+N/A : preemption must be disabled with standard rwlocks.
+
+
+* Interrupt context readers
+
+* Writer-biased rwlocks v13 (note : the highest unlock delays (32us) 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] 135,1603,28119 cycles
+interrupt readers on CPU 0, unlock delay [min,avg,max] 9,1712,35355 cycles
+interrupt readers on CPU 1, lock delay [min,avg,max] 39,1756,18285 cycles
+interrupt readers on CPU 1, unlock delay [min,avg,max] 9,2628,58257 cycles
+interrupt readers on CPU 2, lock delay [min,avg,max] 129,1450,16533 cycles
+interrupt readers on CPU 2, unlock delay [min,avg,max] 27,2354,49647 cycles
+interrupt readers on CPU 3, lock delay [min,avg,max] 75,1758,27051 cycles
+interrupt readers on CPU 3, unlock delay [min,avg,max] 9,2446,63603 cycles
+interrupt readers on CPU 4, lock delay [min,avg,max] 159,1707,27903 cycles
+interrupt readers on CPU 4, unlock delay [min,avg,max] 9,1822,39957 cycles
+interrupt readers on CPU 6, lock delay [min,avg,max] 105,1635,24489 cycles
+interrupt readers on CPU 6, unlock delay [min,avg,max] 9,2390,36771 cycles
+interrupt readers on CPU 7, lock delay [min,avg,max] 135,1614,22995 cycles
+interrupt readers on CPU 7, unlock delay [min,avg,max] 9,2052,43479 cycles
+
+* Standard rwlock, kernel 2.6.27-rc3 (note : these numbers seems good, but
+  they do not take interrupt latency in account. See interrupt latency 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
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#3 lore raw

RFC PATCH 3/5 Priority Sifting Reader-Writer Lock x86_64 Optimised Call

In reply to Mathieu Desnoyers

Create a specialized calling convention for x86_64 where the first argument is passed in rax. Use a trampoline to move it to the rdi register. Useful to re-use the return value of a cmpxchg without moving registers in-line.

CC Linus Torvalds <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
CC Jeremy Fitzhardinge <[email protected]>
CC Andrew Morton <[email protected]>
CC Ingo Molnar <[email protected]>
CC "Paul E. McKenney" <[email protected]>
CC Peter Zijlstra <[email protected]>
CC Joe Perches <[email protected]>
CC Wei Weng <[email protected]>
---
 arch/x86/Kconfig                 |    1 
 arch/x86/kernel/Makefile         |    3 +
 arch/x86/kernel/call_64.S        |   45 +++++++++++++++++++++++++
 arch/x86/kernel/call_export_64.c |   36 ++++++++++++++++++++
 include/asm-x86/call_64.h        |   68 +++++++++++++++++++++++++++++++++++++++
 5 files changed, 153 insertions(+)
arch/x86/kernel/Makefile +3 -0
Index: linux-2.6-lttng/arch/x86/kernel/Makefile
===================================================================
@@ -99,6 +99,9 @@ scx200-y			+= scx200_32.o
 
 obj-$(CONFIG_OLPC)		+= olpc.o
 
+obj-y				+= call_64.o
+obj-y				+= call_export_64.o
+
 ###
 # 64 bit specific files
 ifeq ($(CONFIG_X86_64),y)
arch/x86/kernel/call_64.S new file +45 -0

45 lines not on this page · raw message

arch/x86/kernel/call_export_64.c new file +36 -0
Index: linux-2.6-lttng/arch/x86/kernel/call_export_64.c
===================================================================
@@ -0,0 +1,36 @@
+/*
+ * linux/arch/x86/kernel/call_64.c -- special 64-bits calling conventions
+ *
+ * Export function symbols of special calling convention functions.
+ *
+ * Copyright (C) 2008 Mathieu Desnoyers
+ */
+
+#include <linux/module.h>
+#include <asm/call_64.h>
+
+void asm_psread_lock_slow_irq(void);
+EXPORT_SYMBOL_GPL(asm_psread_lock_slow_irq);
+void asm_psread_trylock_slow_irq(void);
+EXPORT_SYMBOL_GPL(asm_psread_trylock_slow_irq);
+void asm_psread_lock_slow_bh(void);
+EXPORT_SYMBOL_GPL(asm_psread_lock_slow_bh);
+void asm_psread_trylock_slow_bh(void);
+EXPORT_SYMBOL_GPL(asm_psread_trylock_slow_bh);
+void asm_psread_lock_slow_inatomic(void);
+EXPORT_SYMBOL_GPL(asm_psread_lock_slow_inatomic);
+void asm_psread_trylock_slow_inatomic(void);
+EXPORT_SYMBOL_GPL(asm_psread_trylock_slow_inatomic);
+void asm_psread_lock_slow(void);
+EXPORT_SYMBOL_GPL(asm_psread_lock_slow);
+void asm_psread_trylock_slow(void);
+EXPORT_SYMBOL_GPL(asm_psread_trylock_slow);
+
+void asm_pswrite_lock_slow(void);
+EXPORT_SYMBOL_GPL(asm_pswrite_lock_slow);
+void asm_pswrite_trylock_slow(void);
+EXPORT_SYMBOL_GPL(asm_pswrite_trylock_slow);
+void asm_pswrite_unlock_slow(void);
+EXPORT_SYMBOL_GPL(asm_pswrite_unlock_slow);
+void asm_psrwlock_wakeup(void);
+EXPORT_SYMBOL_GPL(asm_psrwlock_wakeup);
include/asm-x86/call_64.h new file +68 -0

68 lines not on this page · raw message

arch/x86/Kconfig +1 -0
Index: linux-2.6-lttng/arch/x86/Kconfig
===================================================================
@@ -31,6 +31,7 @@ config X86
 	select HAVE_ARCH_KGDB if !X86_VOYAGER
 	select HAVE_GENERIC_DMA_COHERENT if X86_32
 	select HAVE_EFFICIENT_UNALIGNED_ACCESS
+	select HAVE_PSRWLOCK_ASM_CALL
 
 config ARCH_DEFCONFIG
 	string
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#4 lore raw

RFC PATCH 4/5 Priority Sifting Reader-Writer Lock Sample

In reply to Mathieu Desnoyers

Sample module to show how to use psrwlock.

CC Linus Torvalds <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
CC Jeremy Fitzhardinge <[email protected]>
CC Andrew Morton <[email protected]>
CC Ingo Molnar <[email protected]>
CC "Paul E. McKenney" <[email protected]>
CC Peter Zijlstra <[email protected]>
CC Joe Perches <[email protected]>
CC Wei Weng <[email protected]>
---
 samples/Kconfig                     |    5 +
 samples/Makefile                    |    2 
 samples/psrwlock/Makefile           |    4 
 samples/psrwlock/psrwlock_example.c |  173 ++++++++++++++++++++++++++++++++++++
 4 files changed, 183 insertions(+), 1 deletion(-)
samples/Makefile +1 -1
Index: linux-2.6-lttng/samples/Makefile
===================================================================
@@ -1,3 +1,3 @@
 # Makefile for Linux samples code
 
-obj-$(CONFIG_SAMPLES)	+= markers/ kobject/ kprobes/
+obj-$(CONFIG_SAMPLES)	+= markers/ kobject/ kprobes/ psrwlock/
samples/psrwlock/Makefile new file +4 -0
Index: linux-2.6-lttng/samples/psrwlock/Makefile
===================================================================
@@ -0,0 +1,4 @@
+# builds the writer-biased rwlock example kernel modules;
+# then to use one (as root):  insmod <module_name.ko>
+
+obj-$(CONFIG_SAMPLE_PSRWLOCK) += psrwlock_example.o
samples/psrwlock/psrwlock_example.c new file +173 -0

173 lines not on this page · raw message

samples/Kconfig +5 -0
Index: linux-2.6-lttng/samples/Kconfig
===================================================================
@@ -33,5 +33,10 @@ config SAMPLE_KRETPROBES
 	default m
 	depends on SAMPLE_KPROBES && KRETPROBES
 
+config SAMPLE_PSRWLOCK
+	tristate "Build psrwlock example -- loadable modules only"
+	default m
+	depends on m
+
 endif # SAMPLES
 
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#5 lore raw

RFC PATCH 5/5 Priority Sifting Reader-Writer Lock Latency Trace

In reply to Mathieu Desnoyers

Trace preempt/softirqs off/irqsoff latency in rwlock. Can be used to perform precise measurement on the impact of these primitives without being lost in the kernel noise.

CC Linus Torvalds <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
CC Jeremy Fitzhardinge <[email protected]>
CC Andrew Morton <[email protected]>
CC Ingo Molnar <[email protected]>
CC "Paul E. McKenney" <[email protected]>
---
 include/linux/psrwlock-latency-trace.h |  104 +++++++++++
 lib/Kconfig.debug                      |    4 
 lib/psrwlock-latency-trace.c           |  288 +++++++++++++++++++++++++++++++++
 3 files changed, 396 insertions(+)
lib/Kconfig.debug +4 -0
Index: linux-2.6-lttng/lib/Kconfig.debug
===================================================================
@@ -683,6 +683,10 @@ config FAULT_INJECTION_STACKTRACE_FILTER
 config HAVE_PSRWLOCK_ASM_CALL
 	def_bool n
 
+config PSRWLOCK_LATENCY_TEST
+	boolean "Testing API for psrwlock latency test"
+	help
+
 config LATENCYTOP
 	bool "Latency measuring infrastructure"
 	select FRAME_POINTER if !MIPS
include/linux/psrwlock-latency-trace.h new file +104 -0

104 lines not on this page · raw message

lib/psrwlock-latency-trace.c new file +288 -0

288 lines not on this page · raw message

Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68