Skip to contentSkip to conversation

locking/rwsem: Make owner store task pointer of last owning reader

PATCH In review Waiman Long 4 participants 10 messages Sep 6, 2018 – Sep 11, 2018 Locking primitives

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

PATCH 1/1 locking/rwsem: Make owner store task pointer of last owning reader

Currently, when a reader acquires a lock, it only sets the RWSEM_READER_OWNED bit in the owner field. The other bits are simply not used. When debugging hanging cases involving rwsems and readers, the owner value does not provide much useful information at all.

This patch modifies the current behavior to always store the task_struct pointer of the last rwsem-acquiring reader in a reader-owned rwsem. This may be useful in debugging rwsem hanging cases especially if only one reader is involved. However, the task in the owner field may not the real owner or one of the real owners at all when the owner value is examined, for example, in a crash dump. So it is just an additional hint about the past history.

If CONFIG_DEBUG_RWSEMS is enabled, the owner field will be checked at unlock time too to make sure the task pointer value is valid. That does have a slight performance cost and so is only enabled as part of that debug option.

From the performance point of view, it is expected that the changes shouldn't have any noticeable performance impact. A rwsem microbenchmark (with 48 worker threads and 1:1 reader/writer ratio) was ran on a 2-socket 24-core 48-thread Haswell system. The locking rates on a 4.19-rc1 based kernel were as follows:

1) Unpatched kernel: 543.3 kops/s
2) Patched kernel: 549.2 kops/s
3) Patched kernel (CONFIG_DEBUG_RWSEMS on): 546.6 kops/s

There was actually a slight increase in performance (1.1%) in this particular case. Maybe it was caused by the elimination of a branch or just a testing noise. Turning on the CONFIG_DEBUG_RWSEMS option also had less than the expected impact on performance.

The least significant 2 bits of the owner value are now used to designate the rwsem is readers owned and the owners are anonymous.

---
 include/linux/rwsem.h       |  4 +-
 kernel/locking/rwsem-xadd.c |  2 +-
 kernel/locking/rwsem.c      |  7 ++--
 kernel/locking/rwsem.h      | 95 +++++++++++++++++++++++++++++++++------------
 4 files changed, 78 insertions(+), 30 deletions(-)
include/linux/rwsem.h +2 -2
index ab93b6e..67dbb57 100644
@@ -45,10 +45,10 @@ struct rw_semaphore {
 };
 
 /*
- * Setting bit 0 of the owner field with other non-zero bits will indicate
+ * Setting bit 1 of the owner field but not bit 0 will indicate
  * that the rwsem is writer-owned with an unknown owner.
  */
-#define RWSEM_OWNER_UNKNOWN	((struct task_struct *)-1L)
+#define RWSEM_OWNER_UNKNOWN	((struct task_struct *)-2L)
 
 extern struct rw_semaphore *rwsem_down_read_failed(struct rw_semaphore *sem);
 extern struct rw_semaphore *rwsem_down_read_failed_killable(struct rw_semaphore *sem);
kernel/locking/rwsem-xadd.c +1 -1
index 01fcb80..09b1800 100644
@@ -180,7 +180,7 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
 		 * but it gives the spinners an early indication that the
 		 * readers now have the lock.
 		 */
-		rwsem_set_reader_owned(sem);
+		__rwsem_set_reader_owned(sem, waiter->task);
 	}
 
 	/*
kernel/locking/rwsem.c +4 -3
index 776308d..e586f0d 100644
@@ -117,8 +117,9 @@ int down_write_trylock(struct rw_semaphore *sem)
 void up_read(struct rw_semaphore *sem)
 {
 	rwsem_release(&sem->dep_map, 1, _RET_IP_);
-	DEBUG_RWSEMS_WARN_ON(sem->owner != RWSEM_READER_OWNED);
+	DEBUG_RWSEMS_WARN_ON(!((unsigned long)sem->owner & RWSEM_READER_OWNED));
 
+	rwsem_clear_reader_owned(sem);
 	__up_read(sem);
 }
 
@@ -181,7 +182,7 @@ void down_read_non_owner(struct rw_semaphore *sem)
 	might_sleep();
 
 	__down_read(sem);
-	rwsem_set_reader_owned(sem);
+	__rwsem_set_reader_owned(sem, NULL);
 }
 
 EXPORT_SYMBOL(down_read_non_owner);
@@ -215,7 +216,7 @@ int __sched down_write_killable_nested(struct rw_semaphore *sem, int subclass)
 
 void up_read_non_owner(struct rw_semaphore *sem)
 {
-	DEBUG_RWSEMS_WARN_ON(sem->owner != RWSEM_READER_OWNED);
+	DEBUG_RWSEMS_WARN_ON(!((unsigned long)sem->owner & RWSEM_READER_OWNED));
 	__up_read(sem);
 }
 
kernel/locking/rwsem.h +71 -24

123 lines not on this page · raw message

Signature · 1 line
1.8.3.1
maintainer
#1 lore raw
Quoted 28 lines · Waiman Long

Currently, when a reader acquires a lock, it only sets the RWSEM_READER_OWNED bit in the owner field. The other bits are simply not used. When debugging hanging cases involving rwsems and readers, the owner value does not provide much useful information at all.

This patch modifies the current behavior to always store the task_struct pointer of the last rwsem-acquiring reader in a reader-owned rwsem. This may be useful in debugging rwsem hanging cases especially if only one reader is involved. However, the task in the owner field may not the real owner or one of the real owners at all when the owner value is examined, for example, in a crash dump. So it is just an additional hint about the past history.

If CONFIG_DEBUG_RWSEMS is enabled, the owner field will be checked at unlock time too to make sure the task pointer value is valid. That does have a slight performance cost and so is only enabled as part of that debug option.

From the performance point of view, it is expected that the changes shouldn't have any noticeable performance impact. A rwsem microbenchmark (with 48 worker threads and 1:1 reader/writer ratio) was ran on a 2-socket 24-core 48-thread Haswell system. The locking rates on a 4.19-rc1 based kernel were as follows:

1) Unpatched kernel: 543.3 kops/s
2) Patched kernel: 549.2 kops/s
3) Patched kernel (CONFIG_DEBUG_RWSEMS on): 546.6 kops/s

Quoted 7 lines

There was actually a slight increase in performance (1.1%) in this particular case. Maybe it was caused by the elimination of a branch or just a testing noise. Turning on the CONFIG_DEBUG_RWSEMS option also had less than the expected impact on performance.

The least significant 2 bits of the owner value are now used to designate the rwsem is readers owned and the owners are anonymous.

So no immediate objection; but I'm still hoping to some day rewrite the whole rwsem thing along the lines we did mutex and merge the 'count' and 'owner' fields into one.

[ RT has something along those lines, and I have half a patch that
starts doing that too, but I never found enough time to really work on it :-( ]

Anyway, when we do something like that, this goes out the window of course.

author reviewer
#2 lore raw
Quoted 40 lines · Peter Zijlstra
Quoted 28 lines · Waiman Long

Currently, when a reader acquires a lock, it only sets the RWSEM_READER_OWNED bit in the owner field. The other bits are simply not used. When debugging hanging cases involving rwsems and readers, the owner value does not provide much useful information at all.

This patch modifies the current behavior to always store the task_struct pointer of the last rwsem-acquiring reader in a reader-owned rwsem. This may be useful in debugging rwsem hanging cases especially if only one reader is involved. However, the task in the owner field may not the real owner or one of the real owners at all when the owner value is examined, for example, in a crash dump. So it is just an additional hint about the past history.

If CONFIG_DEBUG_RWSEMS is enabled, the owner field will be checked at unlock time too to make sure the task pointer value is valid. That does have a slight performance cost and so is only enabled as part of that debug option.

From the performance point of view, it is expected that the changes shouldn't have any noticeable performance impact. A rwsem microbenchmark (with 48 worker threads and 1:1 reader/writer ratio) was ran on a 2-socket 24-core 48-thread Haswell system. The locking rates on a 4.19-rc1 based kernel were as follows:

1) Unpatched kernel: 543.3 kops/s
2) Patched kernel: 549.2 kops/s
3) Patched kernel (CONFIG_DEBUG_RWSEMS on): 546.6 kops/s

Quoted 7 lines

There was actually a slight increase in performance (1.1%) in this particular case. Maybe it was caused by the elimination of a branch or just a testing noise. Turning on the CONFIG_DEBUG_RWSEMS option also had less than the expected impact on performance.

The least significant 2 bits of the owner value are now used to designate the rwsem is readers owned and the owners are anonymous.

So no immediate objection; but I'm still hoping to some day rewrite the whole rwsem thing along the lines we did mutex and merge the 'count' and 'owner' fields into one.

Quoted 6 lines

[ RT has something along those lines, and I have half a patch that
starts doing that too, but I never found enough time to really work on it :-( ]

Anyway, when we do something like that, this goes out the window of course.

That may not be the case. I have also thought about merging owner and count. For writer, it can write its owner value to the combined count/owner. For readers, I think we will need to keep a reader count and so cannot store its owner value there. In that case, we could have a debug-only field for the reader-owner value.

One major issue with a combined count/owner is that we may have to use cmpxchg for reader lock which will certainly impact reader-heavy workloads. I have also thought about ways to compress the task pointer address so that it can use fewer bits and leave the rests for reader count. It is probably doable on 64-bit systems, but likely not on 32-bit system given that there are less bits to play around.

I would certainly like to hear your thought on how to handle these dilemmas as I may be able to find time to work on that. I had a reader optimistic spinning patch that was sent out a while ago. I know it won't get serious time for review until we can resolve this combine owner/count issue first.

Cheers,
Longman

#3 lore raw
Quoted 6 lines · Waiman Long

One major issue with a combined count/owner is that we may have to use cmpxchg for reader lock which will certainly impact reader-heavy workloads. I have also thought about ways to compress the task pointer address so that it can use fewer bits and leave the rests for reader count. It is probably doable on 64-bit systems, but likely not on 32-bit system given that there are less bits to play around.

Yeah we've discussed this before. As a cleanup it would obviously be good, but I fear about raw performance loss when using cmpxchg instead of xadd.

Thanks,
Davidlohr

author reviewer
#4 lore raw
Quoted 9 lines · Davidlohr Bueso
Quoted 6 lines · Waiman Long

One major issue with a combined count/owner is that we may have to use cmpxchg for reader lock which will certainly impact reader-heavy workloads. I have also thought about ways to compress the task pointer address so that it can use fewer bits and leave the rests for reader count. It is probably doable on 64-bit systems, but likely not on 32-bit system given that there are less bits to play around.

Quoted 3 lines

Yeah we've discussed this before. As a cleanup it would obviously be good,
but I fear about raw performance loss when using cmpxchg instead of xadd.

I don't think using cmpxchg for writers will be a performance issue. However, using cmpxchg for readers will be. One thought that I have is to use the tid of the writer on the lower half and use the upper half for reader count. However, there is some overhead in translating tid to task pointer. So I don't know how useful that may be. So we may still need to keep the owner field around.

Cheers,
Longman

maintainer
#5 lore raw
In reply to Davidlohr Bueso
Quoted 11 lines · Davidlohr Bueso
Quoted 6 lines · Waiman Long

One major issue with a combined count/owner is that we may have to use cmpxchg for reader lock which will certainly impact reader-heavy workloads. I have also thought about ways to compress the task pointer address so that it can use fewer bits and leave the rests for reader count. It is probably doable on 64-bit systems, but likely not on 32-bit system given that there are less bits to play around.

Yeah we've discussed this before. As a cleanup it would obviously be good, but I fear about raw performance loss when using cmpxchg instead of xadd.

Does it really matter though? Last time I looked at something similar (refcount_t) the "LOCK INCL" vs "LOCK CMPXCHG" was something like 15 vs 23 cycles (and that was with the cmpxchg loop actually doing a lot more).

Do we really care about the down_read() path _that_ much? I thought that with the main pain point, pagefaults, the problem was mostly the line bouncing, not a few extra cycles.

author reviewer
#6 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 10 lines · Davidlohr Bueso
Quoted 6 lines · Waiman Long

One major issue with a combined count/owner is that we may have to use cmpxchg for reader lock which will certainly impact reader-heavy workloads. I have also thought about ways to compress the task pointer address so that it can use fewer bits and leave the rests for reader count. It is probably doable on 64-bit systems, but likely not on 32-bit system given that there are less bits to play around.

Yeah we've discussed this before. As a cleanup it would obviously be good, but I fear about raw performance loss when using cmpxchg instead of xadd.

Quoted 8 lines

Does it really matter though? Last time I looked at something similar (refcount_t) the "LOCK INCL" vs "LOCK CMPXCHG" was something like 15 vs 23 cycles (and that was with the cmpxchg loop actually doing a lot more).

Do we really care about the down_read() path _that_ much? I thought that with the main pain point, pagefaults, the problem was mostly the line bouncing, not a few extra cycles.

It is not simply that cmpxchg needs more cycles to run, it is the fact that a few retries may be necessary to actually increment the count in case of contention leading to more RMW cycles than with xadd. I am not saying that we can't do that, but there is a price we need to pay.

Cheers,
Longman

#7 lore raw
In reply to Peter Zijlstra
Quoted 3 lines · Peter Zijlstra

[ RT has something along those lines, and I have half a patch that
starts doing that too, but I never found enough time to really work on it :-( ]

But don't rt rwsems act pretty much like a regular mutex in that it only allows readers to nest, not share the lock because of priority inversion scenarios.

Also, wrt rtmutex, will that top-spinner thing ever make it in?

Thanks,
Davidlohr

maintainer
#8 lore raw
Quoted 11 lines · Davidlohr Bueso
Quoted 3 lines · Peter Zijlstra

[ RT has something along those lines, and I have half a patch that
starts doing that too, but I never found enough time to really work on it :-( ]

But don't rt rwsems act pretty much like a regular mutex in that it only allows readers to nest, not share the lock because of priority inversion scenarios.

Also, wrt rtmutex, will that top-spinner thing ever make it in?

Nah, tglx rewrote that a while ago. It's something semi clever now. Lemme see if I can find the patch.

https://git.kernel.org/pub/scm/linux/kernel/git/rt/linux-rt-devel.git/commit/kernel/locking/rwsem-rt.c?h=linux-4.18.y-rt&id=1a42d0b3c3f34895cb5d63e1cd2be02f6077919b

#9 lore raw
In reply to Waiman Long
locking/rwsem: Make owner store task pointer of last owning reader
Commit-ID:  925b9cd1b89a94b7124d128c80dfc48f78a63098
Gitweb:     https://git.kernel.org/tip/925b9cd1b89a94b7124d128c80dfc48f78a63098
Author:     Waiman Long <[email protected]>
AuthorDate: Thu, 6 Sep 2018 16:18:34 -0400
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 10 Sep 2018 12:04:07 +0200

locking/rwsem: Make owner store task pointer of last owning reader

Currently, when a reader acquires a lock, it only sets the RWSEM_READER_OWNED bit in the owner field. The other bits are simply not used. When debugging hanging cases involving rwsems and readers, the owner value does not provide much useful information at all.

This patch modifies the current behavior to always store the task_struct pointer of the last rwsem-acquiring reader in a reader-owned rwsem. This may be useful in debugging rwsem hanging cases especially if only one reader is involved. However, the task in the owner field may not the real owner or one of the real owners at all when the owner value is examined, for example, in a crash dump. So it is just an additional hint about the past history.

If CONFIG_DEBUG_RWSEMS=y is enabled, the owner field will be checked at unlock time too to make sure the task pointer value is valid. That does have a slight performance cost and so is only enabled as part of that debug option.

From the performance point of view, it is expected that the changes shouldn't have any noticeable performance impact. A rwsem microbenchmark (with 48 worker threads and 1:1 reader/writer ratio) was ran on a 2-socket 24-core 48-thread Haswell system. The locking rates on a 4.19-rc1 based kernel were as follows:

1) Unpatched kernel: 543.3 kops/s
2) Patched kernel: 549.2 kops/s
3) Patched kernel (CONFIG_DEBUG_RWSEMS on): 546.6 kops/s

There was actually a slight increase in performance (1.1%) in this particular case. Maybe it was caused by the elimination of a branch or just a testing noise. Turning on the CONFIG_DEBUG_RWSEMS option also had less than the expected impact on performance.

The least significant 2 bits of the owner value are now used to designate the rwsem is readers owned and the owners are anonymous.

---
 include/linux/rwsem.h       |  4 +-
 kernel/locking/rwsem-xadd.c |  2 +-
 kernel/locking/rwsem.c      |  7 ++--
 kernel/locking/rwsem.h      | 95 +++++++++++++++++++++++++++++++++------------
 4 files changed, 78 insertions(+), 30 deletions(-)
include/linux/rwsem.h +2 -2
index ab93b6eae696..67dbb57508b1 100644
@@ -45,10 +45,10 @@ struct rw_semaphore {
 };
 
 /*
- * Setting bit 0 of the owner field with other non-zero bits will indicate
+ * Setting bit 1 of the owner field but not bit 0 will indicate
  * that the rwsem is writer-owned with an unknown owner.
  */
-#define RWSEM_OWNER_UNKNOWN	((struct task_struct *)-1L)
+#define RWSEM_OWNER_UNKNOWN	((struct task_struct *)-2L)
 
 extern struct rw_semaphore *rwsem_down_read_failed(struct rw_semaphore *sem);
 extern struct rw_semaphore *rwsem_down_read_failed_killable(struct rw_semaphore *sem);
kernel/locking/rwsem-xadd.c +1 -1
index 01fcb807598c..09b180063ee1 100644
@@ -180,7 +180,7 @@ static void __rwsem_mark_wake(struct rw_semaphore *sem,
 		 * but it gives the spinners an early indication that the
 		 * readers now have the lock.
 		 */
-		rwsem_set_reader_owned(sem);
+		__rwsem_set_reader_owned(sem, waiter->task);
 	}
 
 	/*
kernel/locking/rwsem.c +4 -3
index 776308d2fa9e..e586f0d03ad3 100644
@@ -117,8 +117,9 @@ EXPORT_SYMBOL(down_write_trylock);
 void up_read(struct rw_semaphore *sem)
 {
 	rwsem_release(&sem->dep_map, 1, _RET_IP_);
-	DEBUG_RWSEMS_WARN_ON(sem->owner != RWSEM_READER_OWNED);
+	DEBUG_RWSEMS_WARN_ON(!((unsigned long)sem->owner & RWSEM_READER_OWNED));
 
+	rwsem_clear_reader_owned(sem);
 	__up_read(sem);
 }
 
@@ -181,7 +182,7 @@ void down_read_non_owner(struct rw_semaphore *sem)
 	might_sleep();
 
 	__down_read(sem);
-	rwsem_set_reader_owned(sem);
+	__rwsem_set_reader_owned(sem, NULL);
 }
 
 EXPORT_SYMBOL(down_read_non_owner);
@@ -215,7 +216,7 @@ EXPORT_SYMBOL(down_write_killable_nested);
 
 void up_read_non_owner(struct rw_semaphore *sem)
 {
-	DEBUG_RWSEMS_WARN_ON(sem->owner != RWSEM_READER_OWNED);
+	DEBUG_RWSEMS_WARN_ON(!((unsigned long)sem->owner & RWSEM_READER_OWNED));
 	__up_read(sem);
 }
 
kernel/locking/rwsem.h +71 -24

123 lines not on this page · raw message