Skip to contentSkip to conversation

locking/rwsem: optimize rwsem_wakeup()

PATCH In review Waiman Long 5 participants 8 messages Apr 30, 2015 – May 8, 2015 Locking primitives

lore
Share & tools
lore
#0 lore raw

v4 cover locking/rwsem: optimize rwsem_wakeup()

v3->v4:
- Break out the active writer check into a separate patch and move it from __rwsem_do_wake() to rwsem_wake().
- Use smp_rmb() instead of the incorrect smp_mb__after_atomic() as suggested by PeterZ.

v2->v3:
- Fix errors in commit log.

v1->v2:
- Add a memory barrier before calling spin_trylock for proper memory ordering.

This patch set aims to reduce spinlock contention in the wait_lock due to excessive activity in the rwsem_wake code path. This, in turn, reduces up_write/up_read latency and improve performance when the rwsem is heavily contended.

On an 8-socket Westmere-EX server (80 cores, HT off), running AIM7's high_systime workload (1000 users) on a vanilla 4.0 kernel produced the following perf profile for spinlock contention:

9.23% reaim [kernel.kallsyms] [k] _raw_spin_lock_irqsave

              |--97.39%-- rwsem_wake
              |--0.69%-- try_to_wake_up
              |--0.52%-- release_pages
               --1.40%-- [...]

1.70% reaim [kernel.kallsyms] [k] _raw_spin_lock_irq

              |--96.61%-- rwsem_down_write_failed
              |--2.03%-- __schedule
              |--0.50%-- run_timer_softirq
               --0.86%-- [...]

Here the contended rwsems are the mmap_sem (mm_struct) and the i_mmap_rwsem (address_space) with mostly write locking. With a patched 4.0 kernel, the perf profile became:

1.87% reaim [kernel.kallsyms] [k] _raw_spin_lock_irqsave

              |--87.64%-- rwsem_wake
              |--2.80%-- release_pages
              |--2.56%-- try_to_wake_up
              |--1.10%-- __wake_up
              |--1.06%-- pagevec_lru_move_fn
              |--0.93%-- prepare_to_wait_exclusive
              |--0.71%-- free_pid
              |--0.58%-- get_page_from_freelist
              |--0.57%-- add_device_randomness
               --2.04%-- [...]

0.80% reaim [kernel.kallsyms] [k] _raw_spin_lock_irq

              |--92.49%-- rwsem_down_write_failed
              |--4.24%-- __schedule
              |--1.37%-- run_timer_softirq
               --1.91%-- [...]

The table below shows the % improvement in throughput (1100-2000 users) in the various AIM7's workloads:

	Workload	% increase in throughput
	--------	------------------------
	custom			 3.8%
	five-sec		 3.5%
	fserver			 4.1%
	high_systime		22.2%
	shared			 2.1%
	short			10.1%

Waiman Long (2):
locking/rwsem: reduce spinlock contention in wakeup after
up_read/up_write
locking/rwsem: check for active writer before wakeup

 include/linux/osq_lock.h    |    5 +++
 kernel/locking/rwsem-xadd.c |   65 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 68 insertions(+), 2 deletions(-)
#1 lore raw

PATCH v4 1/2 locking/rwsem: reduce spinlock contention in wakeup after up_read/up_write

In up_write()/up_read(), rwsem_wake() will be called whenever it detects that some writers/readers are waiting. The rwsem_wake() function will take the wait_lock and call __rwsem_do_wake() to do the real wakeup. For a heavily contended rwsem, doing a spin_lock() on wait_lock will cause further contention on the heavily contended rwsem cacheline resulting in delay in the completion of the up_read/up_write operations.

This patch makes the wait_lock taking and the call to __rwsem_do_wake() optional if at least one spinning writer is present. The spinning writer will be able to take the rwsem and call rwsem_wake() later when it calls up_write(). With the presence of a spinning writer, rwsem_wake() will now try to acquire the lock using trylock. If that fails, it will just quit.

---
 include/linux/osq_lock.h    |    5 ++++
 kernel/locking/rwsem-xadd.c |   44 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 0 deletions(-)
include/linux/osq_lock.h +5 -0
index 3a6490e..703ea5c 100644
@@ -32,4 +32,9 @@ static inline void osq_lock_init(struct optimistic_spin_queue *lock)
 extern bool osq_lock(struct optimistic_spin_queue *lock);
 extern void osq_unlock(struct optimistic_spin_queue *lock);
 
+static inline bool osq_is_locked(struct optimistic_spin_queue *lock)
+{
+	return atomic_read(&lock->tail) != OSQ_UNLOCKED_VAL;
+}
+
 #endif
kernel/locking/rwsem-xadd.c +44 -0

62 lines not on this page · raw message

Signature · 1 line
1.7.1
Acked-by on v4 1/2
#2 lore raw

Re: [PATCH v4 1/2] locking/rwsem: reduce spinlock contention in wakeup after up_read/up_write

Quoted 15 lines · Waiman Long

In up_write()/up_read(), rwsem_wake() will be called whenever it detects that some writers/readers are waiting. The rwsem_wake() function will take the wait_lock and call __rwsem_do_wake() to do the real wakeup. For a heavily contended rwsem, doing a spin_lock() on wait_lock will cause further contention on the heavily contended rwsem cacheline resulting in delay in the completion of the up_read/up_write operations.

This patch makes the wait_lock taking and the call to __rwsem_do_wake() optional if at least one spinning writer is present. The spinning writer will be able to take the rwsem and call rwsem_wake() later when it calls up_write(). With the presence of a spinning writer, rwsem_wake() will now try to acquire the lock using trylock. If that fails, it will just quit.

Quoted 2 lines
maintainer
#3 lore raw

Re: [PATCH v4 1/2] locking/rwsem: reduce spinlock contention in wakeup after up_read/up_write

In reply to Waiman Long
Quoted 15 lines · Waiman Long

In up_write()/up_read(), rwsem_wake() will be called whenever it detects that some writers/readers are waiting. The rwsem_wake() function will take the wait_lock and call __rwsem_do_wake() to do the real wakeup. For a heavily contended rwsem, doing a spin_lock() on wait_lock will cause further contention on the heavily contended rwsem cacheline resulting in delay in the completion of the up_read/up_write operations.

This patch makes the wait_lock taking and the call to __rwsem_do_wake() optional if at least one spinning writer is present. The spinning writer will be able to take the rwsem and call rwsem_wake() later when it calls up_write(). With the presence of a spinning writer, rwsem_wake() will now try to acquire the lock using trylock. If that fails, it will just quit.

Quoted 3 lines

---

Thanks!

Reviewed-by on v4 1/2
#4 lore raw

Re: [PATCH v4 1/2] locking/rwsem: reduce spinlock contention in wakeup after up_read/up_write

In reply to Waiman Long
Quoted 15 lines · Waiman Long

In up_write()/up_read(), rwsem_wake() will be called whenever it detects that some writers/readers are waiting. The rwsem_wake() function will take the wait_lock and call __rwsem_do_wake() to do the real wakeup. For a heavily contended rwsem, doing a spin_lock() on wait_lock will cause further contention on the heavily contended rwsem cacheline resulting in delay in the completion of the up_read/up_write operations.

This patch makes the wait_lock taking and the call to __rwsem_do_wake() optional if at least one spinning writer is present. The spinning writer will be able to take the rwsem and call rwsem_wake() later when it calls up_write(). With the presence of a spinning writer, rwsem_wake() will now try to acquire the lock using trylock. If that fails, it will just quit.

Quoted 2 lines
#5 lore raw

Re: [PATCH v4 1/2] locking/rwsem: reduce spinlock contention in wakeup after up_read/up_write

Quoted 1 line · Davidlohr Bueso

A nit, but it would be useful if the benchmark/perf numbers were also in this changelog, for future references.

Thanks,
Davidlohr

#6 lore raw

[tip:locking/core] locking/rwsem: Reduce spinlock contention in wakeup after up_read()/up_write()

In reply to Waiman Long
locking/rwsem: Reduce spinlock contention in wakeup after up_read()/up_write()
Commit-ID:  59aabfc7e959f5f213e4e5cc7567ab4934da2adf
Gitweb:     http://git.kernel.org/tip/59aabfc7e959f5f213e4e5cc7567ab4934da2adf
Author:     Waiman Long <[email protected]>
AuthorDate: Thu, 30 Apr 2015 17:12:16 -0400
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 8 May 2015 12:27:59 +0200

locking/rwsem: Reduce spinlock contention in wakeup after up_read()/up_write()

In up_write()/up_read(), rwsem_wake() will be called whenever it detects that some writers/readers are waiting. The rwsem_wake() function will take the wait_lock and call __rwsem_do_wake() to do the real wakeup. For a heavily contended rwsem, doing a spin_lock() on wait_lock will cause further contention on the heavily contended rwsem cacheline resulting in delay in the completion of the up_read/up_write operations.

This patch makes the wait_lock taking and the call to __rwsem_do_wake() optional if at least one spinning writer is present. The spinning writer will be able to take the rwsem and call rwsem_wake() later when it calls up_write(). With the presence of a spinning writer, rwsem_wake() will now try to acquire the lock using trylock. If that fails, it will just quit.

---
 include/linux/osq_lock.h    |  5 +++++
 kernel/locking/rwsem-xadd.c | 44 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+)
include/linux/osq_lock.h +5 -0
index 3a6490e..703ea5c 100644
@@ -32,4 +32,9 @@ static inline void osq_lock_init(struct optimistic_spin_queue *lock)
 extern bool osq_lock(struct optimistic_spin_queue *lock);
 extern void osq_unlock(struct optimistic_spin_queue *lock);
 
+static inline bool osq_is_locked(struct optimistic_spin_queue *lock)
+{
+	return atomic_read(&lock->tail) != OSQ_UNLOCKED_VAL;
+}
+
 #endif
kernel/locking/rwsem-xadd.c +44 -0

62 lines not on this page · raw message

#7 lore raw

PATCH v4 2/2 locking/rwsem: check for active writer before wakeup

In reply to Waiman Long

On a highly contended rwsem, spinlock contention due to the slow rwsem_wake() call can be a significant portion of the total CPU cycles used. With writer lock stealing and writer optimistic spinning, there is also a chance that the lock may have been stolen by the time that the wait_lock is acquired.

This patch adds a low cost checking code after acquiring the wait_lock to look for active writer. The presence of an active writer will abort the wakeup operation.

---
 kernel/locking/rwsem-xadd.c |   21 +++++++++++++++++++--
 1 files changed, 19 insertions(+), 2 deletions(-)
kernel/locking/rwsem-xadd.c +19 -2
index 2bb25e2..815f0cc 100644
@@ -399,6 +399,15 @@ static inline bool rwsem_has_spinner(struct rw_semaphore *sem)
 	return osq_is_locked(&sem->osq);
 }
 
+/*
+ * Return true if there is an active writer by checking the owner field which
+ * should be set if there is one.
+ */
+static inline bool rwsem_has_active_writer(struct rw_semaphore *sem)
+{
+	return READ_ONCE(sem->owner) != NULL;
+}
+
 #else
 static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
 {
@@ -409,6 +418,11 @@ static inline bool rwsem_has_spinner(struct rw_semaphore *sem)
 {
 	return false;
 }
+
+static inline bool rwsem_has_active_writer(struct rw_semaphore *sem)
+{
+	return false;	/* Assume it has no active writer */
+}
 #endif
 
 /*
@@ -524,8 +538,11 @@ struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem)
 	raw_spin_lock_irqsave(&sem->wait_lock, flags);
 locked:
 
-	/* do nothing if list empty */
-	if (!list_empty(&sem->wait_list))
+	/*
+	 * Do nothing if list empty or the lock has just been stolen by a
+	 * writer after a possibly long wait in getting the wait_lock.
+	 */
+	if (!list_empty(&sem->wait_list) && !rwsem_has_active_writer(sem))
 		sem = __rwsem_do_wake(sem, RWSEM_WAKE_ANY);
 
 	raw_spin_unlock_irqrestore(&sem->wait_lock, flags);
Signature · 1 line
1.7.1