Skip to contentSkip to conversation

locking/rwsem: Take read lock immediate if queue empty with no writer

PATCH Superseded Waiman Long 3 participants 6 messages Jul 13, 2018 – Jul 23, 2018 Locking primitives

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

PATCH v2 1/1 locking/rwsem: Take read lock immediate if queue empty with no writer

It was discovered that a constant stream of readers might cause the count to go negative most of the time after an initial trigger by a writer even if no writer was present afterward. As a result, most of the readers would have to go through the slowpath reducing their performance.

To avoid that from happening, an additional check is added to detect the special case that the reader in the critical section is the only one in the wait queue and no writer is present. When that happens, it can just have the lock and return immediately without further action. Other incoming readers won't see a waiter is present and be forced into the slowpath.

The additional code is in the slowpath and so should not have an impact on rwsem performance. However, in the special case listed above, it may greatly improve performance.

The issue was found in a customer site where they had an application that pounded on the pread64 syscalls heavily on an XFS filesystem. The application was run in a recent 4-socket boxes with a lot of CPUs. They saw significant spinlock contention in the rwsem_down_read_failed() call. With this patch applied, the system CPU usage went from 85% to 57%, and the spinlock contention in the pread64 syscalls was gone.

v2: Add customer testing results and remove wording that may cause
confusion.

---
 kernel/locking/rwsem-xadd.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)
kernel/locking/rwsem-xadd.c +12 -1
index 3064c50..bf0570e 100644
@@ -233,8 +233,19 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
 	waiter.type = RWSEM_WAITING_FOR_READ;
 
 	raw_spin_lock_irq(&sem->wait_lock);
-	if (list_empty(&sem->wait_list))
+	if (list_empty(&sem->wait_list)) {
+		/*
+		 * In the unlikely event that the task is the only one in
+		 * the wait queue and a writer isn't present, it can have
+		 * the lock and return immediately without going through
+		 * the remaining slowpath code.
+		 */
+		if (unlikely(atomic_long_read(&sem->count) >= 0)) {
+			raw_spin_unlock_irq(&sem->wait_lock);
+			return sem;
+		}
 		adjustment += RWSEM_WAITING_BIAS;
+	}
 	list_add_tail(&waiter.list, &sem->wait_list);
 
 	/* we're now waiting on the lock, but no longer actively locking */
Signature · 1 line
1.8.3.1
author reviewer
#1 lore raw
Quoted 46 lines · Waiman Long

It was discovered that a constant stream of readers might cause the count to go negative most of the time after an initial trigger by a writer even if no writer was present afterward. As a result, most of the readers would have to go through the slowpath reducing their performance.

To avoid that from happening, an additional check is added to detect the special case that the reader in the critical section is the only one in the wait queue and no writer is present. When that happens, it can just have the lock and return immediately without further action. Other incoming readers won't see a waiter is present and be forced into the slowpath.

The additional code is in the slowpath and so should not have an impact on rwsem performance. However, in the special case listed above, it may greatly improve performance.

The issue was found in a customer site where they had an application that pounded on the pread64 syscalls heavily on an XFS filesystem. The application was run in a recent 4-socket boxes with a lot of CPUs. They saw significant spinlock contention in the rwsem_down_read_failed() call. With this patch applied, the system CPU usage went from 85% to 57%, and the spinlock contention in the pread64 syscalls was gone.

v2: Add customer testing results and remove wording that may cause
confusion.

---
 kernel/locking/rwsem-xadd.c | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)
kernel/locking/rwsem-xadd.c +6 -1
index 3064c50..bf0570e 100644
@@ -233,8 +233,19 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
 	waiter.type = RWSEM_WAITING_FOR_READ;
 
 	raw_spin_lock_irq(&sem->wait_lock);
-	if (list_empty(&sem->wait_list))
+	if (list_empty(&sem->wait_list)) {
+		/*
+		 * In the unlikely event that the task is the only one in
+		 * the wait queue and a writer isn't present, it can have
+		 * the lock and return immediately without going through
+		 * the remaining slowpath code.

kernel/locking/rwsem-xadd.c static void __rwsem_mark_wake(struct rw_semaphore *sem, · line 251

Quoted 10 lines
kernel/locking/rwsem-xadd.c +6 -0
+		 */
+		if (unlikely(atomic_long_read(&sem->count) >= 0)) {
+			raw_spin_unlock_irq(&sem->wait_lock);
+			return sem;
+		}
 		adjustment += RWSEM_WAITING_BIAS;
+	}
 	list_add_tail(&waiter.list, &sem->wait_list);
 
 	/* we're now waiting on the lock, but no longer actively locking */

Ping!

Any comment on this one?

Cheers,
Longman

maintainer
#2 lore raw
In reply to Waiman Long
Quoted 4 lines · Waiman Long

It was discovered that a constant stream of readers might cause the count to go negative most of the time after an initial trigger by a writer even if no writer was present afterward. As a result, most of the readers would have to go through the slowpath reducing their performance.

I'm slightly confused, what happens to trigger this?

(also, I'm forever confused by the whole BIAS scheme)

kernel/locking/rwsem-xadd.c static void __rwsem_mark_wake(struct rw_semaphore *sem,

Quoted 17 lines

To avoid that from happening, an additional check is added to detect the special case that the reader in the critical section is the only one in the wait queue and no writer is present. When that happens, it can just have the lock and return immediately without further action. Other incoming readers won't see a waiter is present and be forced into the slowpath.

The additional code is in the slowpath and so should not have an impact on rwsem performance. However, in the special case listed above, it may greatly improve performance.

kernel/locking/rwsem-xadd.c +0 -0
index 3064c50..bf0570e 100644
@@ -233,8 +233,19 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,

your diff function thingy is busted, this is in fact __rwsem_down_read_failed_common you're patching.

Quoted 8 lines
kernel/locking/rwsem-xadd.c +4 -1
 	waiter.type = RWSEM_WAITING_FOR_READ;
 
 	raw_spin_lock_irq(&sem->wait_lock);
-	if (list_empty(&sem->wait_list))
+	if (list_empty(&sem->wait_list)) {
+		/*
+		 * In the unlikely event that the task is the only one in
+		 * the wait queue and a writer isn't present, it can have

kernel/locking/rwsem-xadd.c static void __rwsem_mark_wake(struct rw_semaphore *sem, · line 249

Quoted 10 lines
kernel/locking/rwsem-xadd.c +8 -0
+		 * the lock and return immediately without going through
+		 * the remaining slowpath code.
+		 */
+		if (unlikely(atomic_long_read(&sem->count) >= 0)) {
+			raw_spin_unlock_irq(&sem->wait_lock);
+			return sem;
+		}
 		adjustment += RWSEM_WAITING_BIAS;
+	}
 	list_add_tail(&waiter.list, &sem->wait_list);

So without this, we would add ourselves to the list and then immediately call __rwsem_mark_wake() on ourselves and fall through the wait-loop, ow what?

author reviewer
#3 lore raw
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · Waiman Long

It was discovered that a constant stream of readers might cause the count to go negative most of the time after an initial trigger by a writer even if no writer was present afterward. As a result, most of the readers would have to go through the slowpath reducing their performance.

I'm slightly confused, what happens to trigger this?

(also, I'm forever confused by the whole BIAS scheme)

As I said before, an occasional writer among a stream of incoming readers can cause this problem.

Quoted 7 lines
Quoted 7 lines

To avoid that from happening, an additional check is added to detect the special case that the reader in the critical section is the only one in the wait queue and no writer is present. When that happens, it can just have the lock and return immediately without further action. Other incoming readers won't see a waiter is present and be forced into the slowpath.

The last sentence above is the key. It is what the other incoming readers observe that cause the vicious cycle. See below.

Quoted 5 lines
Quoted 4 lines

The additional code is in the slowpath and so should not have an impact on rwsem performance. However, in the special case listed above, it may greatly improve performance.

Quoted 7 lines

kernel/locking/rwsem-xadd.c static void __rwsem_mark_wake(struct rw_semaphore *sem,

Quoted 5 lines
kernel/locking/rwsem-xadd.c +0 -0
index 3064c50..bf0570e 100644
@@ -233,8 +233,19 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,

your diff function thingy is busted, this is in fact __rwsem_down_read_failed_common you're patching.

Yes, I am patching __rwsem_down_read_failed_common().

Quoted 14 lines
Quoted 14 lines
kernel/locking/rwsem-xadd.c +9 -1
 	waiter.type = RWSEM_WAITING_FOR_READ;
 
 	raw_spin_lock_irq(&sem->wait_lock);
-	if (list_empty(&sem->wait_list))
+	if (list_empty(&sem->wait_list)) {
+		/*
+		 * In the unlikely event that the task is the only one in
+		 * the wait queue and a writer isn't present, it can have
+		 * the lock and return immediately without going through
+		 * the remaining slowpath code.
+		 */
+		if (unlikely(atomic_long_read(&sem->count) >= 0)) {
+			raw_spin_unlock_irq(&sem->wait_lock);
Quoted 8 lines

kernel/locking/rwsem-xadd.c static void __rwsem_mark_wake(struct rw_semaphore *sem, · line 249

Quoted 5 lines
kernel/locking/rwsem-xadd.c +3 -0
+			return sem;
+		}
 		adjustment += RWSEM_WAITING_BIAS;
+	}
 	list_add_tail(&waiter.list, &sem->wait_list);

So without this, we would add ourselves to the list and then immediately call __rwsem_mark_wake() on ourselves and fall through the wait-loop, ow what?

The key here is that we don't want other incoming readers to observe that there are waiters in the wait queue and hence have to go into the slowpath until the single waiter in the queue is sure that it probably will need to go to sleep if there is writer.

With a constant stream of incoming readers, a major portion of them will observe the a negative count and be serialized to enter the slowpath. There are certainly other readers that do not observe the negative count in the in between period after one reader clear the count in the unlock path and a waiter set the count to negative again. Those readers can go ahead and do the read in parallel. But it is the serialized readers that cause the performance loss and the observation of spinlock contention in the perf output.

It is the constant stream of incoming readers that sustain the spinlock queue and the repeated clearing and negative setting of the count.

I can reword the commit log and comment with a v3 patch if you think that is helpful.

Cheers,
Longman

#4 lore raw
Quoted 5 lines · Waiman Long

The key here is that we don't want other incoming readers to observe that there are waiters in the wait queue and hence have to go into the slowpath until the single waiter in the queue is sure that it probably will need to go to sleep if there is writer.

Quoted 8 lines

With a constant stream of incoming readers, a major portion of them will observe the a negative count and be serialized to enter the slowpath. There are certainly other readers that do not observe the negative count in the in between period after one reader clear the count in the unlock path and a waiter set the count to negative again. Those readers can go ahead and do the read in parallel. But it is the serialized readers that cause the performance loss and the observation of spinlock contention in the perf output.

This makes sense and seems feasible in that the optimization is done with the wait_lock held.

Quoted 3 lines

It is the constant stream of incoming readers that sustain the spinlock queue and the repeated clearing and negative setting of the count.

This would not affect optimistic spinners that haven't yet arrived at the waitqueue phase because the lock is anonymously owned, so they won't spin in the first place, right?

Thanks,
Davidlohr

author reviewer
#5 lore raw
Quoted 20 lines · Davidlohr Bueso
Quoted 5 lines · Waiman Long

The key here is that we don't want other incoming readers to observe that there are waiters in the wait queue and hence have to go into the slowpath until the single waiter in the queue is sure that it probably will need to go to sleep if there is writer.

Quoted 8 lines

With a constant stream of incoming readers, a major portion of them will observe the a negative count and be serialized to enter the slowpath. There are certainly other readers that do not observe the negative count in the in between period after one reader clear the count in the unlock path and a waiter set the count to negative again. Those readers can go ahead and do the read in parallel. But it is the serialized readers that cause the performance loss and the observation of spinlock contention in the perf output.

This makes sense and seems feasible in that the optimization is done with the wait_lock held.

Quoted 1 line
Quoted 6 lines
Quoted 2 lines

It is the constant stream of incoming readers that sustain the spinlock queue and the repeated clearing and negative setting of the count.

This would not affect optimistic spinners that haven't yet arrived at the waitqueue phase because the lock is anonymously owned, so they won't spin in the first place, right?

The reader fastpath would have incremented the active count before entering the slowpath. The spinning writer, seeing a non-zero active count, will not attempt to steal the lock until the reader decrement the count and set the waiting bias in one atomic op. Nothing will happen before that.

-Longman