locking/rwsem: Rwsem rearchitecture part 2

v8:
- Remove v7 patch 1 as it has been merged.
- Add patch 14 to make rwsem->owner an atomic_long_t as suggested by PeterZ.
- Incorporates other changes suggested by PeterZ like removing *_is_spinnable() and owner_without_flags() helpers.

v7:
- Fix a bug in patch 1 and include changes suggested by Linus.
- Refresh the other patches accordingly.

v6:
- Add a new patch 1 to fix an existing rwsem bug that allows both readers and writer to become rwsem owners simultaneously.
- Fix a missed wakeup bug (in patch 9) of the v5 series.
- Fix boot up hang problem on some kernel configurations caused by the patch that merge owner into count.
- Make the adaptive disabling of reader optimistic spinning more aggressive to further improve workloads that don't benefit from that.
- Add another patch to disable preemption during down_read() when owner is merged into count to prevent the possiblity of reader count overflow.
- Don't allow merging of owner into count if NR_CPUS is greater that the max supported reader count.
- Allow readers dropped out from the optimistic spinning loop to attempt a trylock if it is still in the right read phase.
- Fix incorrect DEBUG_RWSEMS_WARN_ON() warning.

This is part 2 of a 3-part (0/1/2) series to rearchitect the internal operation of rwsem. Both part 0 and part 1 are merged into tip.

This patchset revamps the current rwsem-xadd implementation to make it saner and easier to work with. It also implements the following 3 new features:

1) Waiter lock handoff
2) Reader optimistic spinning with adapative disabling
3) Store write-lock owner in the atomic count (x86-64 only for now)

Waiter lock handoff is similar to the mechanism currently in the mutex code. This ensures that lock starvation won't happen.

Reader optimistic spinning enables readers to acquire the lock more quickly. So workloads that use a mix of readers and writers should see an increase in performance as long as the reader critical sections are short. For those workloads that have long reader critical sections reader optimistic spinning may hurt performance, so an adaptive disabling mechanism is also implemented to disable it when reader-owned lock spinning timeouts happen.

Finally, storing the write-lock owner into the count will allow optimistic spinners to get to the lock holder's task structure more quickly and eliminating the timing gap where the write lock is acquired but the owner isn't known yet. This is important for RT tasks where spinning on a lock with an unknown owner is not allowed.

Because of the fact that multiple readers can share the same lock, there is a natural preference for readers when measuring in term of locking throughput as more readers are likely to get into the locking fast path than the writers. With waiter lock handoff, we are not going to starve the writers.

On a 2-socket 40-core 80-thread Skylake system with 40 reader and writer locking threads, the min/mean/max locking operations done in a 5-second testing window before the patchset were:

40 readers, Iterations Min/Mean/Max = 1,807/1,808/1,810 40 writers, Iterations Min/Mean/Max = 1,807/50,344/151,255

After the patchset, they became:

40 readers, Iterations Min/Mean/Max = 30,057/31,359/32,741 40 writers, Iterations Min/Mean/Max = 94,466/95,845/97,098

It can be seen that the performance improves for both readers and writers. It also makes rwsem fairer to readers as well as among different threads within the reader and writer groups.

Patch 1 makes owner a permanent member of the rw_semaphore structure and set it irrespective of CONFIG_RWSEM_SPIN_ON_OWNER.

Patch 2 removes rwsem_wake() wakeup optimization as it doesn't work with lock handoff.

Patch 3 implements a new rwsem locking scheme similar to what qrwlock is current doing. Write lock is done by atomic_cmpxchg() while read lock is still being done by atomic_add().

Patch 4 merges the content of rwsem.h and rwsem-xadd.c into rwsem.c just like the mutex. The rwsem-xadd.c is removed and a bare-bone rwsem.h is left for internal function declaration needed by percpu-rwsem.c.

Patch 5 optimizes the merged rwsem.c file to generate smaller object file and performs other miscellaneous code cleanups.

Patch 6 makes rwsem_spin_on_owner() returns owner state.

Patch 7 implments lock handoff to prevent lock starvation. It is expected that throughput will be lower on workloads with highly contended rwsems for better fairness.

Patch 8 makes sure that all wake_up_q() calls happened after dropping the wait_lock.

Patch 9 makes RT task's handling of NULL owner more optimal.

Patch 10 makes reader wakeup to wake up almost all the readers in the wait queue instead of just those in the front.

Patch 11 renames the RWSEM_ANONYMOUSLY_OWNED bit to RWSEM_NONSPINNABLE.

Patch 12 enables reader to spin on a writer-owned rwsem.

Patch 13 makes rwsem->owner an atomic_long_t as it is now holding some flags that may need to be atomically updated.

Patch 14 enables a writer to spin on a reader-owned rwsem for at most 25us and extends the RWSEM_NONSPINNABLE bit to 2 separate ones - one for readers and one for writers.

Patch 15 implements the adaptive disabling of reader optimistic spinning when the reader-owned rwsem spinning timeouts happen.

Patch 16 handles the case of too many readers by reserving the sign bit to designate that a reader lock attempt will fail and the locking reader will be put to sleep. This will ensure that we will not overflow the reader count.

Patch 17 merges the write-lock owner task pointer into the count. Only 64-bit count has enough space to provide a reasonable number of bits for reader count. This is for x86-64 only for the time being.

Patch 18 eliminates redundant computation of the merged owner-count.

Patch 19 disable preemption during the down_read() call to eliminate the remote possibility that the reader count may overflow.

With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 2-socket Skylake system with equal numbers of readers and writers (mixed) before and after this patchset were:

   # of Threads   Before Patch      After Patch
   ------------   ------------      -----------
        2            2,618             4,193
        4            1,202             3,726
        8              802             3,622
       16              729             3,359
       32              319             2,826
       64              102             2,744

On workloads where the rwsem reader critical section is relatively long (longer than the spinning period), optimistic of writer on reader-owned rwsem may not be that helpful. In fact, the performance may regress in some cases like the will-it-sclae page_fault1 microbenchmark. This is likely due to the fact that larger reader groups where the readers acquire the lock together are broken into smaller ones. So more work will be needed to better tune the rwsem code to that kind of workload.

The v7-to-v8 diff is attached at the end.

Waiman Long (19):
locking/rwsem: Make owner available even if
!CONFIG_RWSEM_SPIN_ON_OWNER
locking/rwsem: Remove rwsem_wake() wakeup optimization locking/rwsem: Implement a new locking scheme locking/rwsem: Merge rwsem.h and rwsem-xadd.c into rwsem.c locking/rwsem: Code cleanup after files merging locking/rwsem: Make rwsem_spin_on_owner() return owner state locking/rwsem: Implement lock handoff to prevent lock starvation locking/rwsem: Always release wait_lock before waking up tasks locking/rwsem: More optimal RT task handling of null owner locking/rwsem: Wake up almost all readers in wait queue locking/rwsem: Clarify usage of owner's nonspinaable bit locking/rwsem: Enable readers spinning on writer locking/rwsem: Make rwsem->owner an atomic_long_t locking/rwsem: Enable time-based spinning on reader-owned rwsem locking/rwsem: Adaptive disabling of reader optimistic spinning locking/rwsem: Guard against making count negative locking/rwsem: Merge owner into count on x86-64 locking/rwsem: Remove redundant computation of writer lock word locking/rwsem: Disable preemption in down_read*() if owner in count

 arch/x86/Kconfig                  |    6 +
 include/linux/percpu-rwsem.h      |    4 +-
 include/linux/rwsem.h             |   16 +-
 include/linux/sched/wake_q.h      |    5 +
 kernel/Kconfig.locks              |   12 +
 kernel/locking/Makefile           |    2 +-
 kernel/locking/lock_events_list.h |   12 +-
 kernel/locking/rwsem-xadd.c       |  745 -------------
 kernel/locking/rwsem.c            | 1668 ++++++++++++++++++++++++++++-
 kernel/locking/rwsem.h            |  306 +-----
 lib/Kconfig.debug                 |    8 +-
 11 files changed, 1694 insertions(+), 1090 deletions(-)
 delete mode 100644 kernel/locking/rwsem-xadd.c

index 03cb4b6f842e..0a43830f1932 100644
@@ -117,7 +117,7 @@ static inline void percpu_rwsem_release(struct percpu_rw_semaphore *sem,
 	lock_release(&sem->rw_sem.dep_map, 1, ip);
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	if (!read)
-		sem->rw_sem.owner = RWSEM_OWNER_UNKNOWN;
+		atomic_long_set(&sem->rw_sem.owner, RWSEM_OWNER_UNKNOWN);
 #endif
 }
 

@@ -127,7 +127,7 @@ static inline void percpu_rwsem_acquire(struct percpu_rw_semaphore *sem,
 	lock_acquire(&sem->rw_sem.dep_map, 0, 1, read, 1, NULL, ip);
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	if (!read)
-		sem->rw_sem.owner = current;
+		atomic_long_set(&sem->rw_sem.owner, (long)current);
 #endif
 }
 

index bb76e82398b2..e401358c4e7e 100644
@@ -35,10 +35,11 @@
 struct rw_semaphore {
 	atomic_long_t count;
 	/*
-	 * Write owner or one of the read owners. Can be used as a
-	 * speculative check to see if the owner is running on the cpu.
+	 * Write owner or one of the read owners as well flags regarding
+	 * the current state of the rwsem. Can be used as a speculative
+	 * check to see if the write owner is running on the cpu.
 	 */
-	struct task_struct *owner;
+	atomic_long_t owner;
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	struct optimistic_spin_queue osq; /* spinner MCS lock */
 #endif

@@ -53,7 +54,7 @@ struct rw_semaphore {
  * Setting all bits of the owner field except bit 0 will indicate
  * that the rwsem is writer-owned with an unknown owner.
  */
-#define RWSEM_OWNER_UNKNOWN	((struct task_struct *)-2L)
+#define RWSEM_OWNER_UNKNOWN	(-2L)
 
 /* In all implementations count != 0 means locked */
 static inline int rwsem_is_locked(struct rw_semaphore *sem)

@@ -80,7 +81,7 @@ static inline int rwsem_is_locked(struct rw_semaphore *sem)
 
 #define __RWSEM_INITIALIZER(name)				\
 	{ __RWSEM_INIT_COUNT(name),				\
-	  .owner = NULL,					\
+	  .owner = ATOMIC_LONG_INIT(0),				\
 	  .wait_list = LIST_HEAD_INIT((name).wait_list),	\
 	  .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(name.wait_lock)	\
 	  __RWSEM_OPT_INIT(name)				\

The owner field in the rw_semaphore structure is used primarily for optimistic spinning. However, identifying the rwsem owner can also be helpful in debugging as well as tracing locking related issues when analyzing crash dump. The owner field may also store state information that can be important to the operation of the rwsem.

So the owner field is now made a permanent member of the rw_semaphore structure irrespective of CONFIG_RWSEM_SPIN_ON_OWNER.

---
 include/linux/rwsem.h       |  9 +++++----
 kernel/locking/rwsem-xadd.c |  2 +-
 kernel/locking/rwsem.h      | 23 -----------------------
 lib/Kconfig.debug           |  8 ++++----
 4 files changed, 10 insertions(+), 32 deletions(-)

index 2ea18a3def04..148983e21d47 100644
@@ -34,12 +34,12 @@
  */
 struct rw_semaphore {
 	atomic_long_t count;
-#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	/*
-	 * Write owner. Used as a speculative check to see
-	 * if the owner is running on the cpu.
+	 * Write owner or one of the read owners. Can be used as a
+	 * speculative check to see if the owner is running on the cpu.
 	 */
 	struct task_struct *owner;
+#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	struct optimistic_spin_queue osq; /* spinner MCS lock */
 #endif
 	raw_spinlock_t wait_lock;

@@ -73,13 +73,14 @@ static inline int rwsem_is_locked(struct rw_semaphore *sem)
 #endif
 
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
-#define __RWSEM_OPT_INIT(lockname) , .osq = OSQ_LOCK_UNLOCKED, .owner = NULL
+#define __RWSEM_OPT_INIT(lockname) , .osq = OSQ_LOCK_UNLOCKED
 #else
 #define __RWSEM_OPT_INIT(lockname)
 #endif
 
 #define __RWSEM_INITIALIZER(name)				\
 	{ __RWSEM_INIT_COUNT(name),				\
+	  .owner = NULL,					\
 	  .wait_list = LIST_HEAD_INIT((name).wait_list),	\
 	  .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(name.wait_lock)	\
 	  __RWSEM_OPT_INIT(name)				\

index 0b1f77957240..c0500679fd2f 100644
@@ -86,8 +86,8 @@ void __init_rwsem(struct rw_semaphore *sem, const char *name,
 	atomic_long_set(&sem->count, RWSEM_UNLOCKED_VALUE);
 	raw_spin_lock_init(&sem->wait_lock);
 	INIT_LIST_HEAD(&sem->wait_list);
-#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	sem->owner = NULL;
+#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	osq_lock_init(&sem->osq);
 #endif
 }

index 64877f5294e3..eb9c8534299b 100644
@@ -61,7 +61,6 @@
 #define RWSEM_ACTIVE_READ_BIAS		RWSEM_ACTIVE_BIAS
 #define RWSEM_ACTIVE_WRITE_BIAS		(RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
 
-#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 /*
  * All writes to owner are protected by WRITE_ONCE() to make sure that
  * store tearing can't happen as optimistic spinners may read and use

@@ -126,7 +125,6 @@ static inline bool rwsem_has_anonymous_owner(struct task_struct *owner)
  * real owner or one of the real owners. The only exception is when the
  * unlock is done by up_read_non_owner().
  */
-#define rwsem_clear_reader_owned rwsem_clear_reader_owned
 static inline void rwsem_clear_reader_owned(struct rw_semaphore *sem)
 {
 	unsigned long val = (unsigned long)current | RWSEM_READER_OWNED

@@ -135,28 +133,7 @@ static inline void rwsem_clear_reader_owned(struct rw_semaphore *sem)
 		cmpxchg_relaxed((unsigned long *)&sem->owner, val,
 				RWSEM_READER_OWNED | RWSEM_ANONYMOUSLY_OWNED);
 }
-#endif
-
 #else
-static inline void rwsem_set_owner(struct rw_semaphore *sem)
-{
-}
-
-static inline void rwsem_clear_owner(struct rw_semaphore *sem)
-{
-}
-
-static inline void __rwsem_set_reader_owned(struct rw_semaphore *sem,
-					   struct task_struct *owner)
-{
-}
-
-static inline void rwsem_set_reader_owned(struct rw_semaphore *sem)
-{
-}
-#endif
-
-#ifndef rwsem_clear_reader_owned
 static inline void rwsem_clear_reader_owned(struct rw_semaphore *sem)
 {
 }

index eae43952902e..60efaef4b6b2 100644
@@ -1094,7 +1094,7 @@ config PROVE_LOCKING
 	select DEBUG_SPINLOCK
 	select DEBUG_MUTEXES
 	select DEBUG_RT_MUTEXES if RT_MUTEXES
-	select DEBUG_RWSEMS if RWSEM_SPIN_ON_OWNER
+	select DEBUG_RWSEMS
 	select DEBUG_WW_MUTEX_SLOWPATH
 	select DEBUG_LOCK_ALLOC
 	select TRACE_IRQFLAGS

@@ -1198,10 +1198,10 @@ config DEBUG_WW_MUTEX_SLOWPATH
 
 config DEBUG_RWSEMS
 	bool "RW Semaphore debugging: basic checks"
-	depends on DEBUG_KERNEL && RWSEM_SPIN_ON_OWNER
+	depends on DEBUG_KERNEL
 	help
-	  This debugging feature allows mismatched rw semaphore locks and unlocks
-	  to be detected and reported.
+	  This debugging feature allows mismatched rw semaphore locks
+	  and unlocks to be detected and reported.
 
 config DEBUG_LOCK_ALLOC
 	bool "Lock debugging: detect incorrect freeing of live locks"

2.18.1

With the commit 59aabfc7e959 ("locking/rwsem: Reduce spinlock contention in wakeup after up_read()/up_write()"), the rwsem_wake() forgoes doing a wakeup if the wait_lock cannot be directly acquired and an optimistic spinning locker is present. This can help performance by avoiding spinning on the wait_lock when it is contended.

With the later commit 133e89ef5ef3 ("locking/rwsem: Enable lockless waiter wakeup(s)"), the performance advantage of the above optimization diminishes as the average wait_lock hold time become much shorter.

With a later patch that supports rwsem lock handoff, we can no longer relies on the fact that the presence of an optimistic spinning locker will ensure that the lock will be acquired by a task soon and rwsem_wake() will be called later on to wake up waiters. This can lead to missed wakeup and application hang. So the commit 59aabfc7e959 ("locking/rwsem: Reduce spinlock contention in wakeup after up_read()/up_write()") will have to be reverted.

---
 kernel/locking/rwsem-xadd.c | 72 -------------------------------------
 1 file changed, 72 deletions(-)

index c0500679fd2f..3083fdf50447 100644
@@ -411,25 +411,11 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 	lockevent_cond_inc(rwsem_opt_fail, !taken);
 	return taken;
 }
-
-/*
- * Return true if the rwsem has active spinner
- */
-static inline bool rwsem_has_spinner(struct rw_semaphore *sem)
-{
-	return osq_is_locked(&sem->osq);
-}
-
 #else
 static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 {
 	return false;
 }
-
-static inline bool rwsem_has_spinner(struct rw_semaphore *sem)
-{
-	return false;
-}
 #endif
 
 /*

@@ -651,65 +637,7 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
 	unsigned long flags;
 	DEFINE_WAKE_Q(wake_q);
 
-	/*
-	* __rwsem_down_write_failed_common(sem)
-	*   rwsem_optimistic_spin(sem)
-	*     osq_unlock(sem->osq)
-	*   ...
-	*   atomic_long_add_return(&sem->count)
-	*
-	*      - VS -
-	*
-	*              __up_write()
-	*                if (atomic_long_sub_return_release(&sem->count) < 0)
-	*                  rwsem_wake(sem)
-	*                    osq_is_locked(&sem->osq)
-	*
-	* And __up_write() must observe !osq_is_locked() when it observes the
-	* atomic_long_add_return() in order to not miss a wakeup.
-	*
-	* This boils down to:
-	*
-	* [S.rel] X = 1                [RmW] r0 = (Y += 0)
-	*         MB                         RMB
-	* [RmW]   Y += 1               [L]   r1 = X
-	*
-	* exists (r0=1 /\ r1=0)
-	*/
-	smp_rmb();
-
-	/*
-	 * If a spinner is present, it is not necessary to do the wakeup.
-	 * Try to do wakeup only if the trylock succeeds to minimize
-	 * spinlock contention which may introduce too much delay in the
-	 * unlock operation.
-	 *
-	 *    spinning writer		up_write/up_read caller
-	 *    ---------------		-----------------------
-	 * [S]   osq_unlock()		[L]   osq
-	 *	 MB			      RMB
-	 * [RmW] rwsem_try_write_lock() [RmW] spin_trylock(wait_lock)
-	 *
-	 * Here, it is important to make sure that there won't be a missed
-	 * wakeup while the rwsem is free and the only spinning writer goes
-	 * to sleep without taking the rwsem. Even when the spinning writer
-	 * is just going to break out of the waiting loop, it will still do
-	 * a trylock in rwsem_down_write_failed() before sleeping. IOW, if
-	 * rwsem_has_spinner() is true, it will guarantee at least one
-	 * trylock attempt on the rwsem later on.
-	 */
-	if (rwsem_has_spinner(sem)) {
-		/*
-		 * The smp_rmb() here is to make sure that the spinner
-		 * state is consulted before reading the wait_lock.
-		 */
-		smp_rmb();
-		if (!raw_spin_trylock_irqsave(&sem->wait_lock, flags))
-			return sem;
-		goto locked;
-	}
 	raw_spin_lock_irqsave(&sem->wait_lock, flags);
-locked:
 
 	if (!list_empty(&sem->wait_list))
 		__rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);

2.18.1

The current way of using various reader, writer and waiting biases in the rwsem code are confusing and hard to understand. I have to reread the rwsem count guide in the rwsem-xadd.c file from time to time to remind myself how this whole thing works. It also makes the rwsem code harder to be optimized.

To make rwsem more sane, a new locking scheme similar to the one in qrwlock is now being used. The atomic long count has the following bit definitions:

  Bit  0   - writer locked bit
  Bit  1   - waiters present bit

Bits 2-7 - reserved for future extension
Bits 8-X - reader count (24/56 bits)

The cmpxchg instruction is now used to acquire the write lock. The read lock is still acquired with xadd instruction, so there is no change here. This scheme will allow up to 16M/64P active readers which should be more than enough. We can always use some more reserved bits if necessary.

With that change, we can deterministically know if a rwsem has been write-locked. Looking at the count alone, however, one cannot determine for certain if a rwsem is owned by readers or not as the readers that set the reader count bits may be in the process of backing out. So we still need the reader-owned bit in the owner field to be sure.

With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) of the benchmark on a 8-socket 120-core IvyBridge-EX system before and after the patch were as follows:

Before Patch After Patch

   # of Threads  wlock    rlock    wlock    rlock
   ------------  -----    -----    -----    -----
        1        30,659   31,341   31,055   31,283
        2         8,909   16,457    9,884   17,659
        4         9,028   15,823    8,933   20,233
        8         8,410   14,212    7,230   17,140
       16         8,217   25,240    7,479   24,607

The locking rates of the benchmark on a Power8 system were as follows:

Before Patch After Patch

   # of Threads  wlock    rlock    wlock    rlock
   ------------  -----    -----    -----    -----
        1        12,963   13,647   13,275   13,601
        2         7,570   11,569    7,902   10,829
        4         5,232    5,516    5,466    5,435
        8         5,233    3,386    5,467    3,168

The locking rates of the benchmark on a 2-socket ARM64 system were as follows:

Before Patch After Patch

   # of Threads  wlock    rlock    wlock    rlock
   ------------  -----    -----    -----    -----
        1        21,495   21,046   21,524   21,074
        2         5,293   10,502    5,333   10,504
        4         5,325   11,463    5,358   11,631
        8         5,391   11,712    5,470   11,680

The performance are roughly the same before and after the patch. There are run-to-run variations in performance. Runs with higher variances usually have higher throughput.

---
 kernel/locking/rwsem-xadd.c | 147 ++++++++++++------------------------
 kernel/locking/rwsem.h      |  74 +++++++++---------
 2 files changed, 85 insertions(+), 136 deletions(-)

index 3083fdf50447..7d537b50a849 100644
@@ -9,6 +9,8 @@
  *
  * Optimistic spinning by Tim Chen <[email protected]>
  * and Davidlohr Bueso <[email protected]>. Based on mutexes.
+ *
+ * Rwsem count bit fields re-definition by Waiman Long <[email protected]>.
  */
 #include <linux/rwsem.h>
 #include <linux/init.h>

@@ -22,52 +24,20 @@
 #include "rwsem.h"
 
 /*
- * Guide to the rw_semaphore's count field for common values.
- * (32-bit case illustrated, similar for 64-bit)
- *
- * 0x0000000X	(1) X readers active or attempting lock, no writer waiting
- *		    X = #active_readers + #readers attempting to lock
- *		    (X*ACTIVE_BIAS)
- *
- * 0x00000000	rwsem is unlocked, and no one is waiting for the lock or
- *		attempting to read lock or write lock.
- *
- * 0xffff000X	(1) X readers active or attempting lock, with waiters for lock
- *		    X = #active readers + # readers attempting lock
- *		    (X*ACTIVE_BIAS + WAITING_BIAS)
- *		(2) 1 writer attempting lock, no waiters for lock
- *		    X-1 = #active readers + #readers attempting lock
- *		    ((X-1)*ACTIVE_BIAS + ACTIVE_WRITE_BIAS)
- *		(3) 1 writer active, no waiters for lock
- *		    X-1 = #active readers + #readers attempting lock
- *		    ((X-1)*ACTIVE_BIAS + ACTIVE_WRITE_BIAS)
- *
- * 0xffff0001	(1) 1 reader active or attempting lock, waiters for lock
- *		    (WAITING_BIAS + ACTIVE_BIAS)
- *		(2) 1 writer active or attempting lock, no waiters for lock
- *		    (ACTIVE_WRITE_BIAS)
+ * Guide to the rw_semaphore's count field.
  *
- * 0xffff0000	(1) There are writers or readers queued but none active
- *		    or in the process of attempting lock.
- *		    (WAITING_BIAS)
- *		Note: writer can attempt to steal lock for this count by adding
- *		ACTIVE_WRITE_BIAS in cmpxchg and checking the old count
+ * When the RWSEM_WRITER_LOCKED bit in count is set, the lock is owned
+ * by a writer.
  *
- * 0xfffe0001	(1) 1 writer active, or attempting lock. Waiters on queue.
- *		    (ACTIVE_WRITE_BIAS + WAITING_BIAS)
- *
- * Note: Readers attempt to lock by adding ACTIVE_BIAS in down_read and checking
- *	 the count becomes more than 0 for successful lock acquisition,
- *	 i.e. the case where there are only readers or nobody has lock.
- *	 (1st and 2nd case above).
- *
- *	 Writers attempt to lock by adding ACTIVE_WRITE_BIAS in down_write and
- *	 checking the count becomes ACTIVE_WRITE_BIAS for successful lock
- *	 acquisition (i.e. nobody else has lock or attempts lock).  If
- *	 unsuccessful, in rwsem_down_write_failed, we'll check to see if there
- *	 are only waiters but none active (5th case above), and attempt to
- *	 steal the lock.
+ * The lock is owned by readers when
+ * (1) the RWSEM_WRITER_LOCKED isn't set in count,
+ * (2) some of the reader bits are set in count, and
+ * (3) the owner field has RWSEM_READ_OWNED bit set.
  *
+ * Having some reader bits set is not enough to guarantee a readers owned
+ * lock as the readers may be in the process of backing out from the count
+ * and a writer has just released the lock. So another writer may steal
+ * the lock immediately after that.
  */
 
 /*

@@ -113,9 +83,8 @@ enum rwsem_wake_type {
 
 /*
  * handle the lock release when processes blocked on it that can now run
- * - if we come here from up_xxxx(), then:
- *   - the 'active part' of count (&0x0000ffff) reached 0 (but may have changed)
- *   - the 'waiting part' of count (&0xffff0000) is -ve (and will still be so)
+ * - if we come here from up_xxxx(), then the RWSEM_FLAG_WAITERS bit must
+ *   have been set.
  * - there must be someone on the queue
  * - the wait_lock must be held by the caller
  * - tasks are marked for wakeup, the caller must later invoke wake_up_q()

@@ -160,22 +129,11 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
 	 * so we can bail out early if a writer stole the lock.
 	 */
 	if (wake_type != RWSEM_WAKE_READ_OWNED) {
-		adjustment = RWSEM_ACTIVE_READ_BIAS;
- try_reader_grant:
+		adjustment = RWSEM_READER_BIAS;
 		oldcount = atomic_long_fetch_add(adjustment, &sem->count);
-		if (unlikely(oldcount < RWSEM_WAITING_BIAS)) {
-			/*
-			 * If the count is still less than RWSEM_WAITING_BIAS
-			 * after removing the adjustment, it is assumed that
-			 * a writer has stolen the lock. We have to undo our
-			 * reader grant.
-			 */
-			if (atomic_long_add_return(-adjustment, &sem->count) <
-			    RWSEM_WAITING_BIAS)
-				return;
-
-			/* Last active locker left. Retry waking readers. */
-			goto try_reader_grant;
+		if (unlikely(oldcount & RWSEM_WRITER_MASK)) {
+			atomic_long_sub(adjustment, &sem->count);
+			return;
 		}
 		/*
 		 * Set it to reader-owned to give spinners an early

@@ -209,11 +167,11 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
 	}
 	list_cut_before(&wlist, &sem->wait_list, &waiter->list);
 
-	adjustment = woken * RWSEM_ACTIVE_READ_BIAS - adjustment;
+	adjustment = woken * RWSEM_READER_BIAS - adjustment;
 	lockevent_cond_inc(rwsem_wake_reader, woken);
 	if (list_empty(&sem->wait_list)) {
 		/* hit end of list above */
-		adjustment -= RWSEM_WAITING_BIAS;
+		adjustment -= RWSEM_FLAG_WAITERS;
 	}
 
 	if (adjustment)

@@ -248,22 +206,15 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
  */
 static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
 {
-	/*
-	 * Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS.
-	 */
-	if (count != RWSEM_WAITING_BIAS)
+	long new;
+
+	if (count & RWSEM_LOCK_MASK)
 		return false;
 
-	/*
-	 * Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there
-	 * are other tasks on the wait list, we need to add on WAITING_BIAS.
-	 */
-	count = list_is_singular(&sem->wait_list) ?
-			RWSEM_ACTIVE_WRITE_BIAS :
-			RWSEM_ACTIVE_WRITE_BIAS + RWSEM_WAITING_BIAS;
+	new = count + RWSEM_WRITER_LOCKED -
+	     (list_is_singular(&sem->wait_list) ? RWSEM_FLAG_WAITERS : 0);
 
-	if (atomic_long_cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS, count)
-							== RWSEM_WAITING_BIAS) {
+	if (atomic_long_try_cmpxchg_acquire(&sem->count, &count, new)) {
 		rwsem_set_owner(sem);
 		return true;
 	}

@@ -279,9 +230,9 @@ static inline bool rwsem_try_write_lock_unqueued(struct rw_semaphore *sem)
 {
 	long count = atomic_long_read(&sem->count);
 
-	while (!count || count == RWSEM_WAITING_BIAS) {
+	while (!(count & RWSEM_LOCK_MASK)) {
 		if (atomic_long_try_cmpxchg_acquire(&sem->count, &count,
-					count + RWSEM_ACTIVE_WRITE_BIAS)) {
+					count + RWSEM_WRITER_LOCKED)) {
 			rwsem_set_owner(sem);
 			lockevent_inc(rwsem_opt_wlock);
 			return true;

@@ -424,7 +375,7 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 static inline struct rw_semaphore __sched *
 __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)
 {
-	long count, adjustment = -RWSEM_ACTIVE_READ_BIAS;
+	long count, adjustment = -RWSEM_READER_BIAS;
 	struct rwsem_waiter waiter;
 	DEFINE_WAKE_Q(wake_q);
 

@@ -436,16 +387,16 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)
 		/*
 		 * In case the wait queue is empty and the lock isn't owned
 		 * by a writer, this reader can exit the slowpath and return
-		 * immediately as its RWSEM_ACTIVE_READ_BIAS has already
-		 * been set in the count.
+		 * immediately as its RWSEM_READER_BIAS has already been
+		 * set in the count.
 		 */
-		if (atomic_long_read(&sem->count) >= 0) {
+		if (!(atomic_long_read(&sem->count) & RWSEM_WRITER_MASK)) {
 			raw_spin_unlock_irq(&sem->wait_lock);
 			rwsem_set_reader_owned(sem);
 			lockevent_inc(rwsem_rlock_fast);
 			return sem;
 		}
-		adjustment += RWSEM_WAITING_BIAS;
+		adjustment += RWSEM_FLAG_WAITERS;
 	}
 	list_add_tail(&waiter.list, &sem->wait_list);
 

@@ -458,9 +409,8 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)
 	 * If there are no writers and we are first in the queue,
 	 * wake our own waiter to join the existing active readers !
 	 */
-	if (count == RWSEM_WAITING_BIAS ||
-	    (count > RWSEM_WAITING_BIAS &&
-	     adjustment != -RWSEM_ACTIVE_READ_BIAS))
+	if (!(count & RWSEM_LOCK_MASK) ||
+	   (!(count & RWSEM_WRITER_MASK) && (adjustment & RWSEM_FLAG_WAITERS)))
 		__rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);
 
 	raw_spin_unlock_irq(&sem->wait_lock);

@@ -488,7 +438,7 @@ __rwsem_down_read_failed_common(struct rw_semaphore *sem, int state)
 out_nolock:
 	list_del(&waiter.list);
 	if (list_empty(&sem->wait_list))
-		atomic_long_add(-RWSEM_WAITING_BIAS, &sem->count);
+		atomic_long_andnot(RWSEM_FLAG_WAITERS, &sem->count);
 	raw_spin_unlock_irq(&sem->wait_lock);
 	__set_current_state(TASK_RUNNING);
 	lockevent_inc(rwsem_rlock_fail);

@@ -521,9 +471,6 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
 	struct rw_semaphore *ret = sem;
 	DEFINE_WAKE_Q(wake_q);
 
-	/* undo write bias from down_write operation, stop active locking */
-	count = atomic_long_sub_return(RWSEM_ACTIVE_WRITE_BIAS, &sem->count);
-
 	/* do optimistic spinning and steal lock if possible */
 	if (rwsem_optimistic_spin(sem))
 		return sem;

@@ -543,16 +490,18 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
 
 	list_add_tail(&waiter.list, &sem->wait_list);
 
-	/* we're now waiting on the lock, but no longer actively locking */
+	/* we're now waiting on the lock */
 	if (waiting) {
 		count = atomic_long_read(&sem->count);
 
 		/*
 		 * If there were already threads queued before us and there are
-		 * no active writers, the lock must be read owned; so we try to
-		 * wake any read locks that were queued ahead of us.
+		 * no active writers and some readers, the lock must be read
+		 * owned; so we try to  any read locks that were queued ahead
+		 * of us.
 		 */
-		if (count > RWSEM_WAITING_BIAS) {
+		if (!(count & RWSEM_WRITER_MASK) &&
+		     (count & RWSEM_READER_MASK)) {
 			__rwsem_mark_wake(sem, RWSEM_WAKE_READERS, &wake_q);
 			/*
 			 * The wakeup is normally called _after_ the wait_lock

@@ -569,8 +518,9 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
 			wake_q_init(&wake_q);
 		}
 
-	} else
-		count = atomic_long_add_return(RWSEM_WAITING_BIAS, &sem->count);
+	} else {
+		count = atomic_long_add_return(RWSEM_FLAG_WAITERS, &sem->count);
+	}
 
 	/* wait until we successfully acquire the lock */
 	set_current_state(state);

@@ -587,7 +537,8 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
 			schedule();
 			lockevent_inc(rwsem_sleep_writer);
 			set_current_state(state);
-		} while ((count = atomic_long_read(&sem->count)) & RWSEM_ACTIVE_MASK);
+			count = atomic_long_read(&sem->count);
+		} while (count & RWSEM_LOCK_MASK);
 
 		raw_spin_lock_irq(&sem->wait_lock);
 	}

@@ -603,7 +554,7 @@ __rwsem_down_write_failed_common(struct rw_semaphore *sem, int state)
 	raw_spin_lock_irq(&sem->wait_lock);
 	list_del(&waiter.list);
 	if (list_empty(&sem->wait_list))
-		atomic_long_add(-RWSEM_WAITING_BIAS, &sem->count);
+		atomic_long_andnot(RWSEM_FLAG_WAITERS, &sem->count);
 	else
 		__rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q);
 	raw_spin_unlock_irq(&sem->wait_lock);

2.18.1

Now we only have one implementation of rwsem. Even though we still use xadd to handle reader locking, we use cmpxchg for writer instead. So the filename rwsem-xadd.c is not strictly correct. Also no one outside of the rwsem code need to know the internal implementation other than function prototypes for two internal functions that are called directly from percpu-rwsem.c.

So the rwsem-xadd.c and rwsem.h files are now merged into rwsem.c in the following order:

<upper part of rwsem.h>
<rwsem-xadd.c>
<lower part of rwsem.h>
<rwsem.c>

The rwsem.h file now contains only 2 function declarations for __up_read() and __down_read().

This is a code relocation patch with no code change at all except making __up_read() and __down_read() non-static functions so they can be used by percpu-rwsem.c.

---
 kernel/locking/Makefile     |   2 +-
 kernel/locking/rwsem-xadd.c | 624 -------------------------
 kernel/locking/rwsem.c      | 884 ++++++++++++++++++++++++++++++++++++
 kernel/locking/rwsem.h      | 281 +-----------
 4 files changed, 891 insertions(+), 900 deletions(-)
 delete mode 100644 kernel/locking/rwsem-xadd.c

index 6fe2f333aecb..45452facff3b 100644
@@ -3,7 +3,7 @@
 # and is generally not a function of system call inputs.
 KCOV_INSTRUMENT		:= n
 
-obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o rwsem-xadd.o
+obj-y += mutex.o semaphore.o rwsem.o percpu-rwsem.o
 
 ifdef CONFIG_FUNCTION_TRACER
 CFLAGS_REMOVE_lockdep.o = $(CC_FLAGS_FTRACE)

2.18.1

After merging all the relevant rwsem code into one single file, there are a number of optimizations and cleanups that can be done:

1) Remove all the EXPORT_SYMBOL() calls for functions that are not accessed elsewhere.
2) Remove all the __visible tags as none of the functions will be called from assembly code anymore.
3) Make all the internal functions static.
4) Remove some unneeded blank lines.
5) Remove the intermediate rwsem_down_{read|write}_failed*() functions and rename __rwsem_down_{read|write}_failed_common() to rwsem_down_{read|write}_slowpath().
6) Remove "__" prefix of __rwsem_mark_wake().
7) Use atomic_long_try_cmpxchg_acquire() as much as possible.
8) Remove the rwsem_rtrylock and rwsem_wtrylock lock events as they are not that useful.

That enables the compiler to do better optimization and reduce code size. The text+data size of rwsem.o on an x86-64 machine with gcc8 was reduced from 10237 bytes to 5030 bytes with this change.

---
 kernel/locking/lock_events_list.h |   2 -
 kernel/locking/rwsem.c            | 135 ++++++++++--------------------
 2 files changed, 42 insertions(+), 95 deletions(-)

index ad7668cfc9da..11187a1d40b8 100644
@@ -61,7 +61,5 @@ LOCK_EVENT(rwsem_opt_fail)	/* # of failed opt-spinnings		*/
 LOCK_EVENT(rwsem_rlock)		/* # of read locks acquired		*/
 LOCK_EVENT(rwsem_rlock_fast)	/* # of fast read locks acquired	*/
 LOCK_EVENT(rwsem_rlock_fail)	/* # of failed read lock acquisitions	*/
-LOCK_EVENT(rwsem_rtrylock)	/* # of read trylock calls		*/
 LOCK_EVENT(rwsem_wlock)		/* # of write locks acquired		*/
 LOCK_EVENT(rwsem_wlock_fail)	/* # of failed write lock acquisitions	*/
-LOCK_EVENT(rwsem_wtrylock)	/* # of write trylock calls		*/

2.18.1

This patch modifies rwsem_spin_on_owner() to return four possible values to better reflect the state of lock holder which enables us to make a better decision of what to do next.

---
 kernel/locking/rwsem.c | 65 ++++++++++++++++++++++++++++++------------
 1 file changed, 47 insertions(+), 18 deletions(-)

index f56329240ef1..8d0f2acfe13d 100644
@@ -414,17 +414,54 @@ static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem)
 }
 
 /*
- * Return true only if we can still spin on the owner field of the rwsem.
+ * The rwsem_spin_on_owner() function returns the folowing 4 values
+ * depending on the lock owner state.
+ *   OWNER_NULL  : owner is currently NULL
+ *   OWNER_WRITER: when owner changes and is a writer
+ *   OWNER_READER: when owner changes and the new owner may be a reader.
+ *   OWNER_NONSPINNABLE:
+ *		   when optimistic spinning has to stop because either the
+ *		   owner stops running, is unknown, or its timeslice has
+ *		   been used up.
  */
-static noinline bool rwsem_spin_on_owner(struct rw_semaphore *sem)
+enum owner_state {
+	OWNER_NULL		= 1 << 0,
+	OWNER_WRITER		= 1 << 1,
+	OWNER_READER		= 1 << 2,
+	OWNER_NONSPINNABLE	= 1 << 3,
+};
+#define OWNER_SPINNABLE		(OWNER_NULL | OWNER_WRITER)
+
+static inline enum owner_state rwsem_owner_state(unsigned long owner)
 {
-	struct task_struct *owner = READ_ONCE(sem->owner);
+	if (!owner)
+		return OWNER_NULL;
 
-	if (!is_rwsem_owner_spinnable(owner))
-		return false;
+	if (owner & RWSEM_ANONYMOUSLY_OWNED)
+		return OWNER_NONSPINNABLE;
+
+	if (owner & RWSEM_READER_OWNED)
+		return OWNER_READER;
+
+	return OWNER_WRITER;
+}
+
+static noinline enum owner_state rwsem_spin_on_owner(struct rw_semaphore *sem)
+{
+	struct task_struct *tmp, *owner = READ_ONCE(sem->owner);
+	enum owner_state state = rwsem_owner_state((unsigned long)owner);
+
+	if (state != OWNER_WRITER)
+		return state;
 
 	rcu_read_lock();
-	while (owner && (READ_ONCE(sem->owner) == owner)) {
+	for (;;) {
+		tmp = READ_ONCE(sem->owner);
+		if (tmp != owner) {
+			state = rwsem_owner_state((unsigned long)tmp);
+			break;
+		}
+
 		/*
 		 * Ensure we emit the owner->on_cpu, dereference _after_
 		 * checking sem->owner still matches owner, if that fails,

@@ -433,24 +470,16 @@ static noinline bool rwsem_spin_on_owner(struct rw_semaphore *sem)
 		 */
 		barrier();
 
-		/*
-		 * abort spinning when need_resched or owner is not running or
-		 * owner's cpu is preempted.
-		 */
 		if (need_resched() || !owner_on_cpu(owner)) {
-			rcu_read_unlock();
-			return false;
+			state = OWNER_NONSPINNABLE;
+			break;
 		}
 
 		cpu_relax();
 	}
 	rcu_read_unlock();
 
-	/*
-	 * If there is a new owner or the owner is not set, we continue
-	 * spinning.
-	 */
-	return is_rwsem_owner_spinnable(READ_ONCE(sem->owner));
+	return state;
 }
 
 static bool rwsem_optimistic_spin(struct rw_semaphore *sem)

@@ -473,7 +502,7 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 	 *  2) readers own the lock as we can't determine if they are
 	 *     actively running or not.
 	 */
-	while (rwsem_spin_on_owner(sem)) {
+	while (rwsem_spin_on_owner(sem) & OWNER_SPINNABLE) {
 		/*
 		 * Try to acquire the lock
 		 */

2.18.1

Because of writer lock stealing, it is possible that a constant stream of incoming writers will cause a waiting writer or reader to wait indefinitely leading to lock starvation.

This patch implements a lock handoff mechanism to disable lock stealing and force lock handoff to the first waiter or waiters (for readers) in the queue after at least a 4ms waiting period unless it is a RT writer task which doesn't need to wait. The waiting period is used to avoid discouraging lock stealing too much to affect performance.

The setting and clearing of the handoff bit is serialized by the wait_lock. So racing is not possible.

A rwsem microbenchmark was run for 5 seconds on a 2-socket 40-core 80-thread Skylake system with a v5.1 based kernel and 240 write_lock threads with 5us sleep critical section.

Before the patch, the min/mean/max numbers of locking operations for the locking threads were 1/7,792/173,696. After the patch, the figures became 5,842/6,542/7,458. It can be seen that the rwsem became much more fair, though there was a drop of about 16% in the mean locking operations done which was a tradeoff of having better fairness.

Making the waiter set the handoff bit right after the first wakeup can impact performance especially with a mixed reader/writer workload. With the same microbenchmark with short critical section and equal number of reader and writer threads (40/40), the reader/writer locking operation counts with the current patch were:

40 readers, Iterations Min/Mean/Max = 1,793/1,794/1,796 40 writers, Iterations Min/Mean/Max = 1,793/34,956/86,081

By making waiter set handoff bit immediately after wakeup:

40 readers, Iterations Min/Mean/Max = 43/44/46 40 writers, Iterations Min/Mean/Max = 43/1,263/3,191

---
 kernel/locking/lock_events_list.h |   2 +
 kernel/locking/rwsem.c            | 225 +++++++++++++++++++++++-------
 2 files changed, 173 insertions(+), 54 deletions(-)

index 11187a1d40b8..634b47fd8b5e 100644
@@ -61,5 +61,7 @@ LOCK_EVENT(rwsem_opt_fail)	/* # of failed opt-spinnings		*/
 LOCK_EVENT(rwsem_rlock)		/* # of read locks acquired		*/
 LOCK_EVENT(rwsem_rlock_fast)	/* # of fast read locks acquired	*/
 LOCK_EVENT(rwsem_rlock_fail)	/* # of failed read lock acquisitions	*/
+LOCK_EVENT(rwsem_rlock_handoff)	/* # of read lock handoffs		*/
 LOCK_EVENT(rwsem_wlock)		/* # of write locks acquired		*/
 LOCK_EVENT(rwsem_wlock_fail)	/* # of failed write lock acquisitions	*/
+LOCK_EVENT(rwsem_wlock_handoff)	/* # of write lock handoffs		*/

2.18.1

Hi Waiman,

I was working on a patchset to solve read-write lock deadlock detection problem (https://lkml.org/lkml/2019/5/16/93).

One of the mistakes in that work is that I considered the following case as deadlock:

T1 T2
-- --

down_read1 down_write2

down_write2 down_read1

So I was trying to understand what really went wrong and find the problem is that if I understand correctly the current rwsem design isn't showing real fairness but priority in favor of write locks, and thus one of the bad effects is that read locks can be starved if write locks keep coming.

Luckily, I noticed you are revamping rwsem and seem to have thought about it already. I am not crystal sure what is your work's ramification on the above case, so hope that you can shed some light and perhaps share your thoughts on this.

Thanks,
Yuyang

Sorry everyone, but let me rephrase:

One of the mistakes in that work is that I considered the following case as no deadlock:

Not sure I understand the whole context here, but isn't adding a third independent task makes this a deadlock?

	 T1            T2		T3
	 --            --		--

	 down_read1    down_write2
	 				down_write1
	 down_write2   down_read1

from the perspective of lockdep, we cannot be sure whether there will a T3 or not.

In case that I mis-understood you, maybe your point is about in the above case whether "down_read1" on T2 can *gauranteedly* steal (in the sense of breaking the fairness) the read lock after Waiman modification? If so, I will wait for Waiman's response ;-)

Regards,
Boqun

Yes, that will be a deadlock even with the my rwsem patch applied, as it will still try to preserve the reader-writer ordering. So it will certainly be safer to have the same lock ordering for both tasks.

With my patchset applied, the reader-writer ordering is still supposed to be preserved. Of course, there can be exceptions depending on the exact timing, but we can't rely on that to prevent deadlock.

Cheers,
Longman

Hi Waiman,

This is exactly what I want to know. Thanks for the reply.

Thanks,
Yuyang

Yes, that combination shouldn't cause a deadlock. However, the lockdep code isn't able to recognize this case and so you may still see splat about possible deadlock scenario when lockdep checking is enabled. So the general advise is still to try to rearrange the lock ordering, if possible.

Lock starvation is certainly possible with the current rwsem code. Why don't try to apply the patch to see if it can remedy your problem?

Cheers,
Longman

With the use of wake_q, we can do task wakeups without holding the wait_lock. There is one exception in the rwsem code, though. It is when the writer in the slowpath detects that there are waiters ahead but the rwsem is not held by a writer. This can lead to a long wait_lock hold time especially when a large number of readers are to be woken up.

Remediate this situation by releasing the wait_lock before waking up tasks and re-acquiring it afterward. The rwsem_try_write_lock() function is also modified to read the rwsem count directly to avoid stale count value.

---
 include/linux/sched/wake_q.h |  5 +++++
 kernel/locking/rwsem.c       | 31 +++++++++++++++----------------
 2 files changed, 20 insertions(+), 16 deletions(-)

index ad826d2a4557..26a2013ac39c 100644
@@ -51,6 +51,11 @@ static inline void wake_q_init(struct wake_q_head *head)
 	head->lastp = &head->first;
 }
 
+static inline bool wake_q_empty(struct wake_q_head *head)
+{
+	return head->first == WAKE_Q_TAIL;
+}
+
 extern void wake_q_add(struct wake_q_head *head, struct task_struct *task);
 extern void wake_q_add_safe(struct wake_q_head *head, struct task_struct *task);
 extern void wake_up_q(struct wake_q_head *head);

index 0c8aef065acb..36aed5236bd2 100644
@@ -400,13 +400,14 @@ static void rwsem_mark_wake(struct rw_semaphore *sem,
  * If wstate is WRITER_HANDOFF, it will make sure that either the handoff
  * bit is set or the lock is acquired with handoff bit cleared.
  */
-static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem,
+static inline bool rwsem_try_write_lock(struct rw_semaphore *sem,
 					enum writer_wait_state wstate)
 {
-	long new;
+	long count, new;
 
 	lockdep_assert_held(&sem->wait_lock);
 
+	count = atomic_long_read(&sem->count);
 	do {
 		bool has_handoff = !!(count & RWSEM_FLAG_HANDOFF);
 

@@ -751,26 +752,25 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem, int state)
 					? RWSEM_WAKE_READERS
 					: RWSEM_WAKE_ANY, &wake_q);
 
-		/*
-		 * The wakeup is normally called _after_ the wait_lock
-		 * is released, but given that we are proactively waking
-		 * readers we can deal with the wake_q overhead as it is
-		 * similar to releasing and taking the wait_lock again
-		 * for attempting rwsem_try_write_lock().
-		 */
-		wake_up_q(&wake_q);
-
-		/* We need wake_q again below, reinitialize */
-		wake_q_init(&wake_q);
+		if (!wake_q_empty(&wake_q)) {
+			/*
+			 * We want to minimize wait_lock hold time especially
+			 * when a large number of readers are to be woken up.
+			 */
+			raw_spin_unlock_irq(&sem->wait_lock);
+			wake_up_q(&wake_q);
+			wake_q_init(&wake_q);	/* Used again, reinit */
+			raw_spin_lock_irq(&sem->wait_lock);
+		}
 	} else {
-		count = atomic_long_add_return(RWSEM_FLAG_WAITERS, &sem->count);
+		atomic_long_or(RWSEM_FLAG_WAITERS, &sem->count);
 	}
 
 wait:
 	/* wait until we successfully acquire the lock */
 	set_current_state(state);
 	while (true) {
-		if (rwsem_try_write_lock(count, sem, wstate))
+		if (rwsem_try_write_lock(sem, wstate))
 			break;
 
 		raw_spin_unlock_irq(&sem->wait_lock);

@@ -811,7 +811,6 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem, int state)
 		}
 
 		raw_spin_lock_irq(&sem->wait_lock);
-		count = atomic_long_read(&sem->count);
 	}
 	__set_current_state(TASK_RUNNING);
 	list_del(&waiter.list);

2.18.1

An RT task can do optimistic spinning only if the lock holder is actually running. If the state of the lock holder isn't known, there is a possibility that high priority of the RT task may block forward progress of the lock holder if it happens to reside on the same CPU. This will lead to deadlock. So we have to make sure that an RT task will not spin on a reader-owned rwsem.

When the owner is temporarily set to NULL, there are two cases where we may want to continue spinning:

1) The lock owner is in the process of releasing the lock, sem->owner is cleared but the lock has not been released yet.

2) The lock was free and owner cleared, but another task just comes in and acquire the lock before we try to get it. The new owner may be a spinnable writer.

So an RT task is now made to retry one more time to see if it can acquire the lock or continue spinning on the new owning writer.

When testing on a 8-socket IvyBridge-EX system, the one additional retry seems to improve locking performance of RT write locking threads under heavy contentions. The table below shows the locking rates (in kops/s) with various write locking threads before and after the patch.

    Locking threads     Pre-patch     Post-patch
    ---------------     ---------     -----------
            4             2,753          2,608
            8             2,529          2,520
           16             1,727          1,918
           32             1,263          1,956
           64               889          1,343

---
 kernel/locking/rwsem.c | 51 ++++++++++++++++++++++++++++++++++++------
 1 file changed, 44 insertions(+), 7 deletions(-)

index 36aed5236bd2..eb43201b89b4 100644
@@ -566,6 +566,7 @@ static noinline enum owner_state rwsem_spin_on_owner(struct rw_semaphore *sem)
 static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 {
 	bool taken = false;
+	int prev_owner_state = OWNER_NULL;
 
 	preempt_disable();
 

@@ -583,7 +584,12 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 	 *  2) readers own the lock as we can't determine if they are
 	 *     actively running or not.
 	 */
-	while (rwsem_spin_on_owner(sem) & OWNER_SPINNABLE) {
+	for (;;) {
+		enum owner_state owner_state = rwsem_spin_on_owner(sem);
+
+		if (!(owner_state & OWNER_SPINNABLE))
+			break;
+
 		/*
 		 * Try to acquire the lock
 		 */

@@ -593,13 +599,44 @@ static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 		}
 
 		/*
-		 * When there's no owner, we might have preempted between the
-		 * owner acquiring the lock and setting the owner field. If
-		 * we're an RT task that will live-lock because we won't let
-		 * the owner complete.
+		 * An RT task cannot do optimistic spinning if it cannot
+		 * be sure the lock holder is running or live-lock may
+		 * happen if the current task and the lock holder happen
+		 * to run in the same CPU. However, aborting optimistic
+		 * spinning while a NULL owner is detected may miss some
+		 * opportunity where spinning can continue without causing
+		 * problem.
+		 *
+		 * There are 2 possible cases where an RT task may be able
+		 * to continue spinning.
+		 *
+		 * 1) The lock owner is in the process of releasing the
+		 *    lock, sem->owner is cleared but the lock has not
+		 *    been released yet.
+		 * 2) The lock was free and owner cleared, but another
+		 *    task just comes in and acquire the lock before
+		 *    we try to get it. The new owner may be a spinnable
+		 *    writer.
+		 *
+		 * To take advantage of two scenarios listed agove, the RT
+		 * task is made to retry one more time to see if it can
+		 * acquire the lock or continue spinning on the new owning
+		 * writer. Of course, if the time lag is long enough or the
+		 * new owner is not a writer or spinnable, the RT task will
+		 * quit spinning.
+		 *
+		 * If the owner is a writer, the need_resched() check is
+		 * done inside rwsem_spin_on_owner(). If the owner is not
+		 * a writer, need_resched() check needs to be done here.
 		 */
-		if (!sem->owner && (need_resched() || rt_task(current)))
-			break;
+		if (owner_state != OWNER_WRITER) {
+			if (need_resched())
+				break;
+			if (rt_task(current) &&
+			   (prev_owner_state != OWNER_WRITER))
+				break;
+		}
+		prev_owner_state = owner_state;
 
 		/*
 		 * The cpu_relax() call is a compiler barrier which forces

2.18.1

When the front of the wait queue is a reader, other readers immediately following the first reader will also be woken up at the same time. However, if there is a writer in between. Those readers behind the writer will not be woken up.

Because of optimistic spinning, the lock acquisition order is not FIFO anyway. The lock handoff mechanism will ensure that lock starvation will not happen.

Assuming that the lock hold times of the other readers still in the queue will be about the same as the readers that are being woken up, there is really not much additional cost other than the additional latency due to the wakeup of additional tasks by the waker. Therefore all the readers up to a maximum of 256 in the queue are woken up when the first waiter is a reader to improve reader throughput. This is somewhat similar in concept to a phase-fair R/W lock.

With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 8-socket IvyBridge-EX system with equal numbers of readers and writers before and after this patch were as follows:

   # of Threads  Pre-Patch   Post-patch
   ------------  ---------   ----------
        4          1,641        1,674
        8            731        1,062
       16            564          924
       32             78          300
       64             38          195
      240             50          149

There is no performance gain at low contention level. At high contention level, however, this patch gives a pretty decent performance boost.

---
 kernel/locking/rwsem.c | 31 ++++++++++++++++++++++++++-----
 1 file changed, 26 insertions(+), 5 deletions(-)

index eb43201b89b4..b8e209c5fa55 100644
@@ -254,6 +254,14 @@ enum writer_wait_state {
  */
 #define RWSEM_WAIT_TIMEOUT	DIV_ROUND_UP(HZ, 250)
 
+/*
+ * Magic number to batch-wakeup waiting readers, even when writers are
+ * also present in the queue. This both limits the amount of work the
+ * waking thread must do and also prevents any potential counter overflow,
+ * however unlikely.
+ */
+#define MAX_READERS_WAKEUP	0x100
+
 /*
  * handle the lock release when processes blocked on it that can now run
  * - if we come here from up_xxxx(), then the RWSEM_FLAG_WAITERS bit must

@@ -329,11 +337,17 @@ static void rwsem_mark_wake(struct rw_semaphore *sem,
 	}
 
 	/*
-	 * Grant an infinite number of read locks to the readers at the front
-	 * of the queue. We know that woken will be at least 1 as we accounted
+	 * Grant up to MAX_READERS_WAKEUP read locks to all the readers in the
+	 * queue. We know that the woken will be at least 1 as we accounted
 	 * for above. Note we increment the 'active part' of the count by the
 	 * number of readers before waking any processes up.
 	 *
+	 * This is an adaptation of the phase-fair R/W locks where at the
+	 * reader phase (first waiter is a reader), all readers are eligible
+	 * to acquire the lock at the same time irrespective of their order
+	 * in the queue. The writers acquire the lock according to their
+	 * order in the queue.
+	 *
 	 * We have to do wakeup in 2 passes to prevent the possibility that
 	 * the reader count may be decremented before it is incremented. It
 	 * is because the to-be-woken waiter may not have slept yet. So it

@@ -345,13 +359,20 @@ static void rwsem_mark_wake(struct rw_semaphore *sem,
 	 * 2) For each waiters in the new list, clear waiter->task and
 	 *    put them into wake_q to be woken up later.
 	 */
-	list_for_each_entry(waiter, &sem->wait_list, list) {
+	INIT_LIST_HEAD(&wlist);
+	list_for_each_entry_safe(waiter, tmp, &sem->wait_list, list) {
 		if (waiter->type == RWSEM_WAITING_FOR_WRITE)
-			break;
+			continue;
 
 		woken++;
+		list_move_tail(&waiter->list, &wlist);
+
+		/*
+		 * Limit # of readers that can be woken up per wakeup call.
+		 */
+		if (woken >= MAX_READERS_WAKEUP)
+			break;
 	}
-	list_cut_before(&wlist, &sem->wait_list, &waiter->list);
 
 	adjustment = woken * RWSEM_READER_BIAS - adjustment;
 	lockevent_cond_inc(rwsem_wake_reader, woken);

2.18.1

Bit 1 of sem->owner (RWSEM_ANONYMOUSLY_OWNED) is used to designate an anonymous owner - readers or an anonymous writer. The setting of this anonymous bit is used as an indicator that optimistic spinning cannot be done on this rwsem.

With the upcoming reader optimistic spinning patches, a reader-owned rwsem can be spinned on for a limit period of time. We still need this bit to indicate a rwsem is nonspinnable, but not setting this bit loses its meaning that the owner is known. So rename the bit to RWSEM_NONSPINNABLE to clarify its meaning.

This patch also fixes a DEBUG_RWSEMS_WARN_ON() bug in __up_write().

---
 include/linux/rwsem.h  |  2 +-
 kernel/locking/rwsem.c | 43 +++++++++++++++++++++---------------------
 2 files changed, 22 insertions(+), 23 deletions(-)

index 148983e21d47..bb76e82398b2 100644
@@ -50,7 +50,7 @@ struct rw_semaphore {
 };
 
 /*
- * Setting bit 1 of the owner field but not bit 0 will indicate
+ * Setting all bits of the owner field except bit 0 will indicate
  * that the rwsem is writer-owned with an unknown owner.
  */
 #define RWSEM_OWNER_UNKNOWN	((struct task_struct *)-2L)

2.18.1

This patch enables readers to optimistically spin on a rwsem when it is owned by a writer instead of going to sleep directly. The rwsem_can_spin_on_owner() function is extracted out of rwsem_optimistic_spin() and is called directly by rwsem_down_read_slowpath() and rwsem_down_write_slowpath().

With a locking microbenchmark running on 5.1 based kernel, the total locking rates (in kops/s) on a 8-socket IvyBrige-EX system with equal numbers of readers and writers before and after the patch were as follows:

   # of Threads  Pre-patch    Post-patch
   ------------  ---------    ----------
        4          1,674        1,684
        8          1,062        1,074
       16            924          900
       32            300          458
       64            195          208
      128            164          168
      240            149          143

The performance change wasn't significant in this case, but this change is required by a follow-on patch.

---
 kernel/locking/lock_events_list.h |  1 +
 kernel/locking/rwsem.c            | 86 ++++++++++++++++++++++++++-----
 2 files changed, 75 insertions(+), 12 deletions(-)

index 634b47fd8b5e..ca954e4e00e4 100644
@@ -56,6 +56,7 @@ LOCK_EVENT(rwsem_sleep_reader)	/* # of reader sleeps			*/
 LOCK_EVENT(rwsem_sleep_writer)	/* # of writer sleeps			*/
 LOCK_EVENT(rwsem_wake_reader)	/* # of reader wakeups			*/
 LOCK_EVENT(rwsem_wake_writer)	/* # of writer wakeups			*/
+LOCK_EVENT(rwsem_opt_rlock)	/* # of read locks opt-spin acquired	*/
 LOCK_EVENT(rwsem_opt_wlock)	/* # of write locks opt-spin acquired	*/
 LOCK_EVENT(rwsem_opt_fail)	/* # of failed opt-spinnings		*/
 LOCK_EVENT(rwsem_rlock)		/* # of read locks acquired		*/

2.18.1

The rwsem->owner contains not just the task structure pointer, it also holds some flags for storing the current state of the rwsem. Some of the flags may have to be atomically updated. To reflect the new reality, the owner is now changed to an atomic_long_t type.

New helper functions are added to properly separate out the task structure pointer and the embedded flags.

---
 include/linux/percpu-rwsem.h |   4 +-
 include/linux/rwsem.h        |  11 +--
 kernel/locking/rwsem.c       | 125 ++++++++++++++++++++++-------------
 3 files changed, 88 insertions(+), 52 deletions(-)

index 03cb4b6f842e..0a43830f1932 100644
@@ -117,7 +117,7 @@ static inline void percpu_rwsem_release(struct percpu_rw_semaphore *sem,
 	lock_release(&sem->rw_sem.dep_map, 1, ip);
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	if (!read)
-		sem->rw_sem.owner = RWSEM_OWNER_UNKNOWN;
+		atomic_long_set(&sem->rw_sem.owner, RWSEM_OWNER_UNKNOWN);
 #endif
 }
 

@@ -127,7 +127,7 @@ static inline void percpu_rwsem_acquire(struct percpu_rw_semaphore *sem,
 	lock_acquire(&sem->rw_sem.dep_map, 0, 1, read, 1, NULL, ip);
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	if (!read)
-		sem->rw_sem.owner = current;
+		atomic_long_set(&sem->rw_sem.owner, (long)current);
 #endif
 }
 

index bb76e82398b2..e401358c4e7e 100644
@@ -35,10 +35,11 @@
 struct rw_semaphore {
 	atomic_long_t count;
 	/*
-	 * Write owner or one of the read owners. Can be used as a
-	 * speculative check to see if the owner is running on the cpu.
+	 * Write owner or one of the read owners as well flags regarding
+	 * the current state of the rwsem. Can be used as a speculative
+	 * check to see if the write owner is running on the cpu.
 	 */
-	struct task_struct *owner;
+	atomic_long_t owner;
 #ifdef CONFIG_RWSEM_SPIN_ON_OWNER
 	struct optimistic_spin_queue osq; /* spinner MCS lock */
 #endif

@@ -53,7 +54,7 @@ struct rw_semaphore {
  * Setting all bits of the owner field except bit 0 will indicate
  * that the rwsem is writer-owned with an unknown owner.
  */
-#define RWSEM_OWNER_UNKNOWN	((struct task_struct *)-2L)
+#define RWSEM_OWNER_UNKNOWN	(-2L)
 
 /* In all implementations count != 0 means locked */
 static inline int rwsem_is_locked(struct rw_semaphore *sem)

@@ -80,7 +81,7 @@ static inline int rwsem_is_locked(struct rw_semaphore *sem)
 
 #define __RWSEM_INITIALIZER(name)				\
 	{ __RWSEM_INIT_COUNT(name),				\
-	  .owner = NULL,					\
+	  .owner = ATOMIC_LONG_INIT(0),				\
 	  .wait_list = LIST_HEAD_INIT((name).wait_list),	\
 	  .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(name.wait_lock)	\
 	  __RWSEM_OPT_INIT(name)				\

2.18.1

Sorry for the confusion. I initially use "get", but I am afraid that it may get confused with "get/put" for reference counting. So I used read instead.

I am fine with getting rid of the "read" from the function names.

Cheers,
Longman

I started seeing KASAN use-after-free with current master, and a bisect showed me that this commit 94a9717b3c40 ("locking/rwsem: Make rwsem->owner an atomic_long_t") was the problem. Does it ring any bells? I can easily reproduce it with xfstests (generic/464).

Cheers,
--
Luís

[ 6380.820179] run fstests generic/464 at 2019-07-19 12:04:05
[ 6381.504693] libceph: mon0 (1)192.168.155.1:40786 session established
[ 6381.506790] libceph: client4572 fsid 86b39301-7192-4052-8427-a241af35a591
[ 6381.618830] libceph: mon0 (1)192.168.155.1:40786 session established
[ 6381.619993] libceph: client4573 fsid 86b39301-7192-4052-8427-a241af35a591
[ 6384.464561] ==================================================================
[ 6384.466165] BUG: KASAN: use-after-free in rwsem_down_write_slowpath+0x67d/0x8a0
[ 6384.468288] Read of size 4 at addr ffff8881d5dc9478 by task xfs_io/17238

[ 6384.469545] CPU: 1 PID: 17238 Comm: xfs_io Not tainted 5.2.0+ #444
[ 6384.469550] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.12.1-0-ga5cab58-prebuilt.qemu.org 04/01/2014
[ 6384.469554] Call Trace:
[ 6384.469563]  dump_stack+0x5b/0x90
[ 6384.469569]  print_address_description+0x6f/0x332
[ 6384.469573]  ? rwsem_down_write_slowpath+0x67d/0x8a0
[ 6384.469575]  ? rwsem_down_write_slowpath+0x67d/0x8a0
[ 6384.469579]  __kasan_report.cold+0x1a/0x3e
[ 6384.469583]  ? rwsem_down_write_slowpath+0x67d/0x8a0
[ 6384.469588]  kasan_report+0xe/0x12
[ 6384.469591]  rwsem_down_write_slowpath+0x67d/0x8a0
[ 6384.469596]  ? __ceph_caps_issued_mask+0xe7/0x280
[ 6384.469599]  ? find_held_lock+0xc9/0xf0
[ 6384.469604]  ? __ceph_do_getattr+0x19f/0x290
[ 6384.469608]  ? down_read_non_owner+0x1c0/0x1c0
[ 6384.469612]  ? do_raw_spin_unlock+0xa3/0x130
[ 6384.469617]  ? _raw_spin_unlock+0x24/0x30
[ 6384.469622]  ? __lock_acquire.isra.0+0x486/0x770
[ 6384.469629]  ? path_openat+0x7ef/0xfe0
[ 6384.469635]  ? down_write+0x11e/0x130
[ 6384.469638]  down_write+0x11e/0x130
[ 6384.469642]  ? down_read_killable+0x1e0/0x1e0
[ 6384.469646]  ? __sb_start_write+0x11c/0x170
[ 6384.469650]  ? __mnt_want_write+0xb4/0xd0
[ 6384.469655]  path_openat+0x7ef/0xfe0
[ 6384.469661]  ? path_mountpoint+0x4d0/0x4d0
[ 6384.469667]  ? __is_insn_slot_addr+0x93/0xb0
[ 6384.469671]  ? kernel_text_address+0x113/0x120
[ 6384.469674]  ? __kernel_text_address+0xe/0x30
[ 6384.469679]  ? unwind_get_return_address+0x2f/0x50
[ 6384.469683]  ? swiotlb_map.cold+0x25/0x25
[ 6384.469687]  ? arch_stack_walk+0x8f/0xe0
[ 6384.469692]  do_filp_open+0x12b/0x1c0
[ 6384.469695]  ? may_open_dev+0x50/0x50
[ 6384.469702]  ? __alloc_fd+0x115/0x280
[ 6384.469705]  ? lock_downgrade+0x350/0x350
[ 6384.469709]  ? do_raw_spin_lock+0x113/0x1d0
[ 6384.469713]  ? rwlock_bug.part.0+0x60/0x60
[ 6384.469718]  ? do_raw_spin_unlock+0xa3/0x130
[ 6384.469722]  ? _raw_spin_unlock+0x24/0x30
[ 6384.469725]  ? __alloc_fd+0x115/0x280
[ 6384.469731]  do_sys_open+0x1f0/0x2d0
[ 6384.469735]  ? filp_open+0x50/0x50
[ 6384.469738]  ? switch_fpu_return+0x13e/0x230
[ 6384.469742]  ? __do_page_fault+0x4b5/0x670
[ 6384.469748]  do_syscall_64+0x63/0x1c0
[ 6384.469753]  entry_SYSCALL_64_after_hwframe+0x44/0xa9
[ 6384.469756] RIP: 0033:0x7fe961434528
[ 6384.469760] Code: 00 00 41 00 3d 00 00 41 00 74 47 48 8d 05 20 4d 0d 00 8b 00 85 c0 75 6b 44 89 e2 48 89 ee bf 9c ff ff ff b8 01 01 00 00 0f 05 <48> 3d 00 f0 ff ff 0f 87 94 00 00 00 48 8b 4c 24 28 64 48 33 0c 25
[ 6384.469762] RSP: 002b:00007ffd9bbabb20 EFLAGS: 00000246 ORIG_RAX: 0000000000000101
[ 6384.469765] RAX: ffffffffffffffda RBX: 0000000000000242 RCX: 00007fe961434528
[ 6384.469767] RDX: 0000000000000242 RSI: 00007ffd9bbae2a5 RDI: 00000000ffffff9c
[ 6384.469769] RBP: 00007ffd9bbae2a5 R08: 0000000000000001 R09: 0000000000000000
[ 6384.469771] R10: 0000000000000180 R11: 0000000000000246 R12: 0000000000000242
[ 6384.469773] R13: 00007ffd9bbabe00 R14: 0000000000000180 R15: 0000000000000060

[ 6384.470018] Allocated by task 16593:
[ 6384.470562]  __kasan_kmalloc.part.0+0x3c/0xa0
[ 6384.470565]  kmem_cache_alloc+0xdc/0x240
[ 6384.470569]  copy_process+0x1dce/0x27b0
[ 6384.470572]  _do_fork+0xec/0x540
[ 6384.470576]  __se_sys_clone+0xb2/0x100
[ 6384.470581]  do_syscall_64+0x63/0x1c0
[ 6384.470586]  entry_SYSCALL_64_after_hwframe+0x44/0xa9

[ 6384.470823] Freed by task 9:
[ 6384.471235]  __kasan_slab_free+0x147/0x200
[ 6384.471240]  kmem_cache_free+0x111/0x330
[ 6384.471246]  rcu_core+0x2f9/0x830
[ 6384.471251]  __do_softirq+0x154/0x486

[ 6384.471493] The buggy address belongs to the object at ffff8881d5dc9440
                which belongs to the cache task_struct of size 4928
[ 6384.473081] The buggy address is located 56 bytes inside of
                4928-byte region [ffff8881d5dc9440, ffff8881d5dca780)
[ 6384.474453] The buggy address belongs to the page:
[ 6384.474989] page:ffffea0007577200 refcount:1 mapcount:0 mapping:ffff8881f6811800 index:0x0 compound_mapcount: 0
[ 6384.474993] flags: 0x8000000000010200(slab|head)
[ 6384.474997] raw: 8000000000010200 0000000000000000 0000000100000001 ffff8881f6811800
[ 6384.475000] raw: 0000000000000000 0000000000060006 00000001ffffffff 0000000000000000
[ 6384.475002] page dumped because: kasan: bad access detected

[ 6384.475176] Memory state around the buggy address:
[ 6384.475744]  ffff8881d5dc9300: fb fb fb fb fb fb fb fb fc fc fc fc fc fc fc fc
[ 6384.476571]  ffff8881d5dc9380: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[ 6384.477390] >ffff8881d5dc9400: fc fc fc fc fc fc fc fc fb fb fb fb fb fb fb fb
[ 6384.478214]                                                                 ^
[ 6384.479052]  ffff8881d5dc9480: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
[ 6384.479898]  ffff8881d5dc9500: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
[ 6384.481300] ==================================================================
[ 6384.482408] Disabling lock debugging due to kernel taint

This patch shouldn't change the behavior of the rwsem code. The code only access data within the rw_semaphore structures. I don't know why it will cause a KASAN error. I will have to reproduce it and figure out exactly which statement is doing the invalid access.

Thanks,
Longman

Yeah, screwing the bisection is something I've done in the past so I may have got the wrong commit. Another detail is that I was running xfstests against CephFS, I didn't tried with any other filesystem. I can try to reproduce with btrfs or xfs next week.

Cheers,

Luis

Oh, I don't have a CephFS setup. Will you use the scripts/decode_stacktrace.sh to find what line number is the offending statement? That will help in figuring out what has gone wrong.

Anyway, it seems like a structure that include a rwsem is freed while another cpu is still waiting to acquire the lock. It is probably a hidden bug in the filesystem code somewhere that the recent changes in rwsem behavior make it easier for  the problem to show up.

Cheers,
Longman

The stack traces should show line numbers if you run them through scripts/decode_stacktrace.sh.

You need to have debug info enabled for that, though.

Luis?

Linus

Yep, sure. And I should have done this in the initial report. It's a different trace, I had to recompile the kernel.

(I'm also adding Jeff to the CC list.)

Cheers,

Luis

[   39.801179] ==================================================================
[   39.801973] BUG: KASAN: use-after-free in rwsem_down_write_slowpath (/home/miguel/kernel/linux/kernel/locking/rwsem.c:669 /home/miguel/kernel/linux/kernel/locking/rwsem.c:1125) 
[   39.802733] Read of size 4 at addr ffff8881f1f65138 by task xfs_io/2145

[   39.803598] CPU: 0 PID: 2145 Comm: xfs_io Not tainted 5.2.0+ #460
[   39.803600] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.12.1-0-ga5cab58-prebuilt.qemu.org 04/01/2014
[   39.803602] Call Trace:
[   39.803609] dump_stack (/home/miguel/kernel/linux/lib/dump_stack.c:115) 
[   39.803615] print_address_description (/home/miguel/kernel/linux/mm/kasan/report.c:352) 
[   39.803618] ? rwsem_down_write_slowpath (/home/miguel/kernel/linux/kernel/locking/rwsem.c:669 /home/miguel/kernel/linux/kernel/locking/rwsem.c:1125) 
[   39.803621] ? rwsem_down_write_slowpath (/home/miguel/kernel/linux/kernel/locking/rwsem.c:669 /home/miguel/kernel/linux/kernel/locking/rwsem.c:1125) 
[   39.803624] __kasan_report.cold (/home/miguel/kernel/linux/mm/kasan/report.c:483) 
[   39.803629] ? rwsem_down_write_slowpath (/home/miguel/kernel/linux/kernel/locking/rwsem.c:669 /home/miguel/kernel/linux/kernel/locking/rwsem.c:1125) 
[   39.803633] kasan_report (/home/miguel/kernel/linux/./arch/x86/include/asm/smap.h:69 /home/miguel/kernel/linux/mm/kasan/common.c:613) 
[   39.803636] rwsem_down_write_slowpath (/home/miguel/kernel/linux/kernel/locking/rwsem.c:669 /home/miguel/kernel/linux/kernel/locking/rwsem.c:1125) 
[   39.803641] ? __ceph_caps_issued_mask (/home/miguel/kernel/linux/fs/ceph/caps.c:914) 
[   39.803644] ? find_held_lock (/home/miguel/kernel/linux/kernel/locking/lockdep.c:4004) 
[   39.803649] ? __ceph_do_getattr (/home/miguel/kernel/linux/fs/ceph/inode.c:2246) 
[   39.803653] ? down_read_non_owner (/home/miguel/kernel/linux/kernel/locking/rwsem.c:1116) 
[   39.803658] ? do_raw_spin_unlock (/home/miguel/kernel/linux/./include/linux/compiler.h:218 /home/miguel/kernel/linux/./include/asm-generic/qspinlock.h:94 /home/miguel/kernel/linux/kernel/locking/spinlock_debug.c:139) 
[   39.803663] ? _raw_spin_unlock (/home/miguel/kernel/linux/kernel/locking/spinlock.c:184) 
[   39.803667] ? __lock_acquire.isra.0 (/home/miguel/kernel/linux/kernel/locking/lockdep.c:3884) 
[   39.803674] ? path_openat (/home/miguel/kernel/linux/fs/namei.c:3322 /home/miguel/kernel/linux/fs/namei.c:3533) 
[   39.803680] ? down_write (/home/miguel/kernel/linux/kernel/locking/rwsem.c:1486) 
[   39.803683] down_write (/home/miguel/kernel/linux/kernel/locking/rwsem.c:1486) 
[   39.803687] ? down_read_killable (/home/miguel/kernel/linux/kernel/locking/rwsem.c:1482) 
[   39.803690] ? __sb_start_write (/home/miguel/kernel/linux/./include/linux/compiler.h:194 /home/miguel/kernel/linux/./include/linux/rcu_sync.h:38 /home/miguel/kernel/linux/./include/linux/percpu-rwsem.h:52 /home/miguel/kernel/linux/fs/super.c:1608) 
[   39.803694] ? __mnt_want_write (/home/miguel/kernel/linux/fs/namespace.c:253 /home/miguel/kernel/linux/fs/namespace.c:297 /home/miguel/kernel/linux/fs/namespace.c:337) 
[   39.803699] path_openat (/home/miguel/kernel/linux/fs/namei.c:3322 /home/miguel/kernel/linux/fs/namei.c:3533) 
[   39.803706] ? path_mountpoint (/home/miguel/kernel/linux/fs/namei.c:3518) 
[   39.803711] ? __is_insn_slot_addr (/home/miguel/kernel/linux/kernel/kprobes.c:291) 
[   39.803716] ? kernel_text_address (/home/miguel/kernel/linux/kernel/extable.c:113) 
[   39.803719] ? __kernel_text_address (/home/miguel/kernel/linux/kernel/extable.c:95) 
[   39.803724] ? unwind_get_return_address (/home/miguel/kernel/linux/arch/x86/kernel/unwind_orc.c:311 /home/miguel/kernel/linux/arch/x86/kernel/unwind_orc.c:306) 
[   39.803727] ? swiotlb_map.cold (/home/miguel/kernel/linux/kernel/stacktrace.c:83) 
[   39.803730] ? arch_stack_walk (/home/miguel/kernel/linux/arch/x86/kernel/stacktrace.c:26) 
[   39.803735] do_filp_open (/home/miguel/kernel/linux/fs/namei.c:3563) 
[   39.803739] ? may_open_dev (/home/miguel/kernel/linux/fs/namei.c:3557) 
[   39.803746] ? __alloc_fd (/home/miguel/kernel/linux/fs/file.c:536) 
[   39.803749] ? lock_downgrade (/home/miguel/kernel/linux/kernel/locking/lockdep.c:4422) 
[   39.803753] ? do_raw_spin_lock (/home/miguel/kernel/linux/kernel/locking/spinlock_debug.c:92 /home/miguel/kernel/linux/kernel/locking/spinlock_debug.c:115) 
[   39.803757] ? rwlock_bug.part.0 (/home/miguel/kernel/linux/kernel/locking/spinlock_debug.c:111) 
[   39.803762] ? do_raw_spin_unlock (/home/miguel/kernel/linux/./include/linux/compiler.h:218 /home/miguel/kernel/linux/./include/asm-generic/qspinlock.h:94 /home/miguel/kernel/linux/kernel/locking/spinlock_debug.c:139) 
[   39.803766] ? _raw_spin_unlock (/home/miguel/kernel/linux/kernel/locking/spinlock.c:184) 
[   39.803769] ? __alloc_fd (/home/miguel/kernel/linux/fs/file.c:536) 
[   39.803774] do_sys_open (/home/miguel/kernel/linux/fs/open.c:1070) 
[   39.803778] ? filp_open (/home/miguel/kernel/linux/fs/open.c:1056) 
[   39.803781] ? switch_fpu_return (/home/miguel/kernel/linux/./arch/x86/include/asm/bitops.h:76 /home/miguel/kernel/linux/./include/asm-generic/bitops-instrumented.h:57 /home/miguel/kernel/linux/./include/linux/thread_info.h:60 /home/miguel/kernel/linux/./arch/x86/include/asm/fpu/internal.h:547 /home/miguel/kernel/linux/arch/x86/kernel/fpu/core.c:343) 
[   39.803786] ? __do_page_fault (/home/miguel/kernel/linux/./include/linux/compiler.h:194 /home/miguel/kernel/linux/./arch/x86/include/asm/atomic.h:31 /home/miguel/kernel/linux/./include/asm-generic/atomic-instrumented.h:27 /home/miguel/kernel/linux/./include/linux/jump_label.h:254 /home/miguel/kernel/linux/./include/linux/jump_label.h:264 /home/miguel/kernel/linux/./include/linux/perf_event.h:1094 /home/miguel/kernel/linux/arch/x86/mm/fault.c:1485 /home/miguel/kernel/linux/arch/x86/mm/fault.c:1510) 
[   39.803792] do_syscall_64 (/home/miguel/kernel/linux/arch/x86/entry/common.c:296) 
[   39.803796] entry_SYSCALL_64_after_hwframe (/home/miguel/kernel/linux/arch/x86/entry/entry_64.S:184) 
[   39.803799] RIP: 0033:0x7f62b41a2528
[ 39.803803] Code: 00 00 41 00 3d 00 00 41 00 74 47 48 8d 05 20 4d 0d 00 8b 00 85 c0 75 6b 44 89 e2 48 89 ee bf 9c ff ff ff b8 01 01 00 00 0f 05 <48> 3d 00 f0 ff ff 0f 87 94 00 00 00 48 8b 4c 24 28 64 48 33 0c 25
All code
========
   0:	00 00                	add    %al,(%rax)
   2:	41 00 3d 00 00 41 00 	add    %dil,0x410000(%rip)        # 0x410009
   9:	74 47                	je     0x52
   b:	48 8d 05 20 4d 0d 00 	lea    0xd4d20(%rip),%rax        # 0xd4d32
  12:	8b 00                	mov    (%rax),%eax
  14:	85 c0                	test   %eax,%eax
  16:	75 6b                	jne    0x83
  18:	44 89 e2             	mov    %r12d,%edx
  1b:	48 89 ee             	mov    %rbp,%rsi
  1e:	bf 9c ff ff ff       	mov    $0xffffff9c,%edi
  23:	b8 01 01 00 00       	mov    $0x101,%eax
  28:	0f 05                	syscall 
  2a:*	48 3d 00 f0 ff ff    	cmp    $0xfffffffffffff000,%rax		<-- trapping instruction
  30:	0f 87 94 00 00 00    	ja     0xca
  36:	48 8b 4c 24 28       	mov    0x28(%rsp),%rcx
  3b:	64                   	fs
  3c:	48                   	rex.W
  3d:	33                   	.byte 0x33
  3e:	0c 25                	or     $0x25,%al

Code starting with the faulting instruction
===========================================
   0:	48 3d 00 f0 ff ff    	cmp    $0xfffffffffffff000,%rax
   6:	0f 87 94 00 00 00    	ja     0xa0
   c:	48 8b 4c 24 28       	mov    0x28(%rsp),%rcx
  11:	64                   	fs
  12:	48                   	rex.W
  13:	33                   	.byte 0x33
  14:	0c 25                	or     $0x25,%al
[   39.803805] RSP: 002b:00007ffe6c3359e0 EFLAGS: 00000246 ORIG_RAX: 0000000000000101
[   39.803808] RAX: ffffffffffffffda RBX: 0000000000000242 RCX: 00007f62b41a2528
[   39.803810] RDX: 0000000000000242 RSI: 00007ffe6c3382a5 RDI: 00000000ffffff9c
[   39.803812] RBP: 00007ffe6c3382a5 R08: 0000000000000001 R09: 0000000000000000
[   39.803814] R10: 0000000000000180 R11: 0000000000000246 R12: 0000000000000242
[   39.803816] R13: 00007ffe6c335cc0 R14: 0000000000000180 R15: 0000000000000060

[   39.803996] Allocated by task 2093:
[   39.804373] __kasan_kmalloc.part.0 (/home/miguel/kernel/linux/mm/kasan/common.c:69 /home/miguel/kernel/linux/mm/kasan/common.c:77 /home/miguel/kernel/linux/mm/kasan/common.c:487) 
[   39.804376] kmem_cache_alloc (/home/miguel/kernel/linux/mm/slab.h:522 /home/miguel/kernel/linux/mm/slub.c:2766 /home/miguel/kernel/linux/mm/slub.c:2774 /home/miguel/kernel/linux/mm/slub.c:2779) 
[   39.804380] copy_process (/home/miguel/kernel/linux/kernel/fork.c:852 /home/miguel/kernel/linux/kernel/fork.c:1856) 
[   39.804382] _do_fork (/home/miguel/kernel/linux/kernel/fork.c:2369) 
[   39.804385] __se_sys_clone (/home/miguel/kernel/linux/kernel/fork.c:2505) 
[   39.804387] do_syscall_64 (/home/miguel/kernel/linux/arch/x86/entry/common.c:296) 
[   39.804390] entry_SYSCALL_64_after_hwframe (/home/miguel/kernel/linux/arch/x86/entry/entry_64.S:184) 

[   39.804558] Freed by task 16:
[   39.804871] __kasan_slab_free (/home/miguel/kernel/linux/mm/kasan/common.c:69 /home/miguel/kernel/linux/mm/kasan/common.c:77 /home/miguel/kernel/linux/mm/kasan/common.c:449) 
[   39.804874] kmem_cache_free (/home/miguel/kernel/linux/mm/slub.c:1470 /home/miguel/kernel/linux/mm/slub.c:3012 /home/miguel/kernel/linux/mm/slub.c:3028) 
[   39.804877] rcu_core (/home/miguel/kernel/linux/./include/linux/rcupdate.h:213 /home/miguel/kernel/linux/kernel/rcu/rcu.h:223 /home/miguel/kernel/linux/kernel/rcu/tree.c:2114 /home/miguel/kernel/linux/kernel/rcu/tree.c:2314) 
[   39.804880] __do_softirq (/home/miguel/kernel/linux/./include/asm-generic/atomic-instrumented.h:26 /home/miguel/kernel/linux/./include/linux/jump_label.h:254 /home/miguel/kernel/linux/./include/linux/jump_label.h:264 /home/miguel/kernel/linux/./include/trace/events/irq.h:142 /home/miguel/kernel/linux/kernel/softirq.c:293) 

[   39.805048] The buggy address belongs to the object at ffff8881f1f65100
which belongs to the cache task_struct of size 4928
[   39.806345] The buggy address is located 56 bytes inside of
4928-byte region [ffff8881f1f65100, ffff8881f1f66440)
[   39.807543] The buggy address belongs to the page:
[   39.808045] page:ffffea0007c7d800 refcount:1 mapcount:0 mapping:ffff8881f6811800 index:0x0 compound_mapcount: 0
[   39.808049] flags: 0x8000000000010200(slab|head)
[   39.808053] raw: 8000000000010200 dead000000000100 dead000000000122 ffff8881f6811800
[   39.808056] raw: 0000000000000000 0000000000060006 00000001ffffffff 0000000000000000
[   39.808058] page dumped because: kasan: bad access detected

[   39.808224] Memory state around the buggy address:
[   39.808723]  ffff8881f1f65000: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[   39.809476]  ffff8881f1f65080: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
[   39.810220] >ffff8881f1f65100: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
[   39.810968]                                         ^
[   39.811504]  ffff8881f1f65180: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
[   39.812237]  ffff8881f1f65200: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
[   39.812972] ==================================================================
[   39.813710] Disabling lock debugging due to kernel taint

Ah, and I also managed to reproduce this on btrfs so I guess this rules out a bug in the filesystem code.

Cheers,

Luis

Just another detail (before I go completely offline until tomorrow evening): in the btrfs case I'm seeing the bug on the rwsem_down_read_slowpath path, not on rwsem_down_write_slowpath. But it seems to be on the same place (i.e. rwsem_can_spin_on_owner).

Cheers,

Luis

That's rwsem_can_spin_on_owner(), specifically line 669 seems to suggest owner_on_cpu().

So we'd somehow have a dead owner; I'm not immediately seeing how that can happen.

Thanks for the information. I think I know where the problem is. Would you mind applying the attached patch to see if it can fix the KASAN error.

Thanks,
Longman

From 445dc58add71f976c20359568d370f5059d30f77 Mon Sep 17 00:00:00 2001
From: Waiman Long <[email protected]>
Date: Sat, 20 Jul 2019 10:45:39 -0400
Subject: [PATCH] locking/rwsem: Don't call owner_on_cpu() on read-owner

For writer, the owner value is cleared on unlock. For reader, it is left intact on unlock for providing better debugging aid on crash dump and the unlock of one reader may not mean the lock is free.

As a result, the owner_on_cpu() shouldn't be used on read-owner as the task pointer value may not be valid and it might have been freed. That is the case in rwsem_spin_on_owner(), but not in rwsem_can_spin_on_owner(). This can lead to use-after-free error from KASAN. For example,

  BUG: KASAN: use-after-free in rwsem_down_write_slowpath
  (/home/miguel/kernel/linux/kernel/locking/rwsem.c:669
  /home/miguel/kernel/linux/kernel/locking/rwsem.c:1125)

Fix this by checking for RWSEM_READER_OWNED flag before calling owner_on_cpu().

---
 kernel/locking/rwsem.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

index 37524a47f002..bc91aacaab58 100644
@@ -666,7 +666,11 @@ static inline bool rwsem_can_spin_on_owner(struct rw_semaphore *sem,
 	preempt_disable();
 	rcu_read_lock();
 	owner = rwsem_owner_flags(sem, &flags);
-	if ((flags & nonspinnable) || (owner && !owner_on_cpu(owner)))
+	/*
+	 * Don't check the read-owner as the entry may be stale.
+	 */
+	if ((flags & nonspinnable) ||
+	    (owner && !(flags & RWSEM_READER_OWNED) && !owner_on_cpu(owner)))
 		ret = false;
 	rcu_read_unlock();
 	preempt_enable();

2.18.1