locking/qspinlock: Optimize pending state waiting for unlock
PATCH 1/1 locking/qspinlock: Optimize pending state waiting for unlock
From: Guo Ren <[email protected]>
When we're pending, we only care about lock value. The xchg_tail wouldn't affect the pending state. That means the hardware thread could stay in a sleep state and leaves the rest execution units' resources of pipeline to other hardware threads. This optimization may work only for SMT scenarios because the granularity between cores is cache-block.
--- kernel/locking/qspinlock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/locking/qspinlock.c +2 -2
@@ -371,7 +371,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)/* * We're pending, wait for the owner to go away. * -* 0,1,1 -> 0,1,0 +* 0,1,1 -> *,1,0 * * this wait loop must be a load-acquire such that we match the * store-release that clears the locked bit and create lock
@@ -380,7 +380,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* barriers. */ if (val & _Q_LOCKED_MASK) -atomic_cond_read_acquire (&lock->val, !(VAL & _Q_LOCKED_MASK)); +smp_cond_load_acquire (&lock->locked, !VAL );/* * take ownership and clear the pending bit.
Signature · 1 line
2.36.1
Waiman Long
reviewerQuoted 25 lines · On 12/24/22 07:05, [email protected] wrote:
From: Guo Ren <[email protected]>
When we're pending, we only care about lock value. The
xchg_tailwouldn't affect the pending state. That means the hardware thread could stay in a sleep state and leaves the rest execution units' resources of pipeline to other hardware threads. This optimization may work only for SMT scenarios because the granularity between cores is cache-block.Signed-off-by Guo Ren <[email protected]>Signed-off-by Guo Ren <[email protected]>Cc Waiman Long <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Boqun Feng <[email protected]>Cc Will Deacon <[email protected]>Cc Ingo Molnar <[email protected]>--- kernel/locking/qspinlock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)kernel/locking/qspinlock.c +0
-0
kernel/locking/qspinlock.c void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 377
Quoted 8 lines
kernel/locking/qspinlock.c +1
-1@@ -371,7 +371,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)/* * We're pending, wait for the owner to go away. * -* 0,1,1 -> 0,1,0 +* 0,1,1 -> *,1,0 * * this wait loop must be a load-acquire such that we match the * store-release that clears the locked bit and create lock
Yes, we don't care about the tail.
kernel/locking/qspinlock.c void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 386
Quoted 9 lines
kernel/locking/qspinlock.c +1
-1@@ -380,7 +380,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* barriers. */ if (val & _Q_LOCKED_MASK) -atomic_cond_read_acquire (&lock->val, !(VAL & _Q_LOCKED_MASK)); +smp_cond_load_acquire (&lock->locked, !VAL );/* * take ownership and clear the pending bit.
We may save an AND operation here which may be a cycle or two. I remember that it may be more costly to load a byte instead of an integer in some arches. So it doesn't seem like that much of an optimization from my point of view. I know that arm64 will enter a low power state in this *cond_load_acquire() loop, but I believe any change in the state of the the lock cacheline will wake it up. So it doesn't really matter if you are checking a byte or an int.
Do you have any other data point to support your optimization claim?
Cheers,
Longman
Quoted 10 lines · Waiman Long
Quoted 8 lines · On 12/24/22 07:05, [email protected] wrote:
From: Guo Ren <[email protected]>
When we're pending, we only care about lock value. The
xchg_tailwouldn't affect the pending state. That means the hardware thread could stay in a sleep state and leaves the rest execution units' resources of pipeline to other hardware threads. This optimization may work only for SMT scenarios because the granularity between cores is cache-block.
Please have a look at the comment I've written.
Quoted 33 lines
Quoted 17 lines
Signed-off-by Guo Ren <[email protected]>Signed-off-by Guo Ren <[email protected]>Cc Waiman Long <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Boqun Feng <[email protected]>Cc Will Deacon <[email protected]>Cc Ingo Molnar <[email protected]>--- kernel/locking/qspinlock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)kernel/locking/qspinlock.c +0
-0kernel/locking/qspinlock.c void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 377
Quoted 8 lines
kernel/locking/qspinlock.c +1
-1@@ -371,7 +371,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)/* * We're pending, wait for the owner to go away. * -* 0,1,1 -> 0,1,0 +* 0,1,1 -> *,1,0 * * this wait loop must be a load-acquire such that we match the * store-release that clears the locked bit and create lock Yes, we don't care about the tail.
Quoted 7 lines
kernel/locking/qspinlock.c +1
-1@@ -380,7 +380,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* barriers. */ if (val & _Q_LOCKED_MASK) -atomic_cond_read_acquire (&lock->val, !(VAL & _Q_LOCKED_MASK)); +smp_cond_load_acquire (&lock->locked, !VAL );
Quoted 7 lines
kernel/locking/qspinlock.c void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 386
Quoted 2 lines
kernel/locking/qspinlock.c +0
-0/* * take ownership and clear the pending bit. We may save an AND operation here which may be a cycle or two. I remember that it may be more costly to load a byte instead of an integer in some arches. So it doesn't seem like that much of an optimization from my point of view.
The reason is, of course, not here. See my commit comment.
Quoted 4 lines
I know that arm64 will enter a low power state in
this*cond_load_acquire()loop, but I believe any change in the state of the the lock cacheline will wake it up. So it doesn't really matter if you are checking a byte or an int.
The situation is the SMT scenarios in the same core. Not an entering low-power state situation. Of course, the granularity between cores is "cacheline", but the granularity between SMT hw threads of the same core could be "byte" which internal LSU handles. For example, when a hw-thread yields the resources of the core to other hw-threads, this patch could help the hw-thread stay in the sleep state and prevent it from being woken up by other hw-threads xchg_tail.
Finally, from the software semantic view, does the patch make it more accurate? (We don't care about the tail here.)
Quoted 6 lines
Do you have any other data point to support your optimization claim?
Cheers,
Longman
Signature · 2 lines
Best Regards Guo Ren
Quoted 64 lines · Guo Ren
Quoted 9 lines · Waiman Long
Quoted 8 lines · On 12/24/22 07:05, [email protected] wrote:
From: Guo Ren <[email protected]>
When we're pending, we only care about lock value. The
xchg_tailwouldn't affect the pending state. That means the hardware thread could stay in a sleep state and leaves the rest execution units' resources of pipeline to other hardware threads. This optimization may work only for SMT scenarios because the granularity between cores is cache-block.Please have a look at the comment I've written.
Quoted 32 lines
Quoted 16 lines
Signed-off-by Guo Ren <[email protected]>Signed-off-by Guo Ren <[email protected]>Cc Waiman Long <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Boqun Feng <[email protected]>Cc Will Deacon <[email protected]>Cc Ingo Molnar <[email protected]>--- kernel/locking/qspinlock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)kernel/locking/qspinlock.c +0
-0kernel/locking/qspinlock.c void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 377
Quoted 8 lines
kernel/locking/qspinlock.c +1
-1@@ -371,7 +371,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)/* * We're pending, wait for the owner to go away. * -* 0,1,1 -> 0,1,0 +* 0,1,1 -> *,1,0 * * this wait loop must be a load-acquire such that we match the * store-release that clears the locked bit and create lock Yes, we don't care about the tail.
Quoted 7 lines
kernel/locking/qspinlock.c +1
-1@@ -380,7 +380,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)* barriers. */ if (val & _Q_LOCKED_MASK) -atomic_cond_read_acquire (&lock->val, !(VAL & _Q_LOCKED_MASK)); +smp_cond_load_acquire (&lock->locked, !VAL );Quoted 6 lines
kernel/locking/qspinlock.c void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) · line 386
Quoted 2 lines
kernel/locking/qspinlock.c +0
-0/* * take ownership and clear the pending bit. We may save an AND operation here which may be a cycle or two. I remember that it may be more costly to load a byte instead of an integer in some arches. So it doesn't seem like that much of an optimization from my point of view.
The reason is, of course, not here. See my commit comment.
Quoted 4 lines
I know that arm64 will enter a low power state in
this*cond_load_acquire()loop, but I believe any change in the state of the the lock cacheline will wake it up. So it doesn't really matter if you are checking a byte or an int.The situation is the SMT scenarios in the same core. Not an entering low-power state situation. Of course, the granularity between cores is "cacheline", but the granularity between SMT hw threads of the same core could be "byte" which internal LSU handles. For example, when a hw-thread yields the resources of the core to other hw-threads, this patch could help the hw-thread stay in the sleep state and prevent it from being woken up by other hw-threads
xchg_tail.
Quoted 2 lines
Finally, from the software semantic view, does the patch make it more accurate? (We don't care about the tail here.)
Thanks for the clarification.
I am not arguing for the simplification part. I just want to clarify my limited understanding of how the CPU hardware are actually dealing with these conditions.
With that, I am fine with this patch. It would be nice if you can elaborate a bit more in your commit log.
Waiman Long
reviewerQuoted 71 lines · Waiman Long
Quoted 67 lines · Guo Ren
Quoted 9 lines · Waiman Long
Quoted 8 lines · On 12/24/22 07:05, [email protected] wrote:
From: Guo Ren <[email protected]>
When we're pending, we only care about lock value. The
xchg_tailwouldn't affect the pending state. That means the hardware thread could stay in a sleep state and leaves the rest execution units' resources of pipeline to other hardware threads. This optimization may work only for SMT scenarios because the granularity between cores is cache-block.Please have a look at the comment I've written.
Quoted 35 lines
Quoted 24 lines
Signed-off-by Guo Ren <[email protected]>Signed-off-by Guo Ren <[email protected]>Cc Waiman Long <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Boqun Feng <[email protected]>Cc Will Deacon <[email protected]>Cc Ingo Molnar <[email protected]>---
kernel/locking/qspinlock.c| 4 ++--1 file changed, 2 insertions(+), 2 deletions(-)kernel/locking/qspinlock.c +1
-1@@ -371,7 +371,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val) /** We're pending, wait for the owner to go away. * -* 0,1,1 -> 0,1,0 +* 0,1,1 -> *,1,0 * * this wait loop must be a load-acquire such that we match the Quoted 1 line
* store-release that clears the locked bit and create lock
Yes, we don't care about the tail.
Quoted 9 lines
kernel/locking/qspinlock.c +1
-1@@ -380,7 +380,7 @@ void __lockfuncqueued_spin_lock_slowpath(struct qspinlock *lock, u32 val) * barriers. */ if (val & _Q_LOCKED_MASK) - atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_MASK)); + smp_cond_load_acquire(&lock->locked, !VAL);Quoted 6 lines
Quoted 2 lines
/*
* take ownership and clear the pending bit.We may save an AND operation here which may be a cycle or two. I remember that it may be more costly to load a byte instead of an integer in some arches. So it doesn't seem like that much of an optimization from my point of view.
The reason is, of course, not here. See my commit comment.
Quoted 4 lines
I know that arm64 will enter a low power state in
this*cond_load_acquire()loop, but I believe any change in the state of the the lock cacheline will wake it up. So it doesn't really matter if you are checking a byte or an int.The situation is the SMT scenarios in the same core. Not an entering low-power state situation. Of course, the granularity between cores is "cacheline", but the granularity between SMT hw threads of the same core could be "byte" which internal LSU handles. For example, when a hw-thread yields the resources of the core to other hw-threads, this patch could help the hw-thread stay in the sleep state and prevent it from being woken up by other hw-threads
xchg_tail.Quoted 2 lines
Finally, from the software semantic view, does the patch make it more accurate? (We don't care about the tail here.)
Quoted 8 lines
Thanks for the clarification.
I am not arguing for the simplification part. I just want to clarify my limited understanding of how the CPU hardware are actually dealing with these conditions.
With that, I am fine with this patch. It would be nice if you can elaborate a bit more in your commit log.
Acked-by Waiman Long <[email protected]>
BTW, have you actually observe any performance improvement with this patch?
Cheers,
Longman
Quoted 81 lines · Waiman Long
Quoted 79 lines · Waiman Long
Quoted 69 lines · Guo Ren
Quoted 9 lines · Waiman Long
Quoted 8 lines · On 12/24/22 07:05, [email protected] wrote:
From: Guo Ren <[email protected]>
When we're pending, we only care about lock value. The
xchg_tailwouldn't affect the pending state. That means the hardware thread could stay in a sleep state and leaves the rest execution units' resources of pipeline to other hardware threads. This optimization may work only for SMT scenarios because the granularity between cores is cache-block.Please have a look at the comment I've written.
Quoted 35 lines
Quoted 24 lines
Signed-off-by Guo Ren <[email protected]>Signed-off-by Guo Ren <[email protected]>Cc Waiman Long <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Boqun Feng <[email protected]>Cc Will Deacon <[email protected]>Cc Ingo Molnar <[email protected]>--- kernel/locking/qspinlock.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)kernel/locking/qspinlock.c +1
-1@@ -371,7 +371,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)/* * We're pending, wait for the owner to go away. * -* 0,1,1 -> 0,1,0 +* 0,1,1 -> *,1,0 * * this wait loop must be a load-acquire such that we match the Quoted 1 line
* store-release that clears the locked bit and create lock
Yes, we don't care about the tail.
Quoted 9 lines
kernel/locking/qspinlock.c +1
-1@@ -380,7 +380,7 @@ void __lockfuncqueued_spin_lock_slowpath(struct qspinlock *lock, u32 val) * barriers. */ if (val & _Q_LOCKED_MASK) -atomic_cond_read_acquire (&lock->val, !(VAL & _Q_LOCKED_MASK)); +smp_cond_load_acquire (&lock->locked, !VAL );Quoted 7 lines
Quoted 2 lines
/*
* take ownership and clear the pending bit.We may save an AND operation here which may be a cycle or two. I remember that it may be more costly to load a byte instead of an integer
in some arches. So it doesn't seem like that much of an optimization from my point of view.The reason is, of course, not here. See my commit comment.
Quoted 5 lines
I know that arm64 will enter a low power state in
this*cond_load_acquire()loop, but I believe any change in the state of
the the lock cacheline will wake it up. So it doesn't really matter if you are checking a byte or an int.The situation is the SMT scenarios in the same core. Not an entering low-power state situation. Of course, the granularity between cores is "cacheline", but the granularity between SMT hw threads of the same core could be "byte" which internal LSU handles. For example, when a hw-thread yields the resources of the core to other hw-threads, this patch could help the hw-thread stay in the sleep state and prevent it from being woken up by other hw-threads
xchg_tail.Quoted 2 lines
Finally, from the software semantic view, does the patch make it more accurate? (We don't care about the tail here.)
Thanks for the clarification.
I am not arguing for the simplification part. I just want to clarify my limited understanding of how the CPU hardware are actually dealing with these conditions.
Quoted 6 lines
Quoted 5 lines
With that, I am fine with this patch. It would be nice if you can elaborate a bit more in your commit log.
Acked-by Waiman Long <[email protected]>BTW, have you actually observe any performance improvement with this patch?
Not yet. I'm researching how the hardware could satisfy qspinlock better. Here are three points I concluded:
1. Atomic forward progress guarantee: Prevent unnecessary LL/SC
retry, which may cause expensive bus transactions when crossing the NUMA nodes.
2. Sub-word atomic primitive: Enable freedom from interference
between locked, pending, and tail.
3. Load-cond primitive: Prevent processor from wasting loop
operations for detection.
For points 2 & 3, I have a continuous proposal to add new atomic_read_cond_mask & smp_load_cond_mask for Linux atomic primitives [1].
[1]: https://lore.kernel.org/lkml/[email protected]/
Quoted 4 lines
Cheers,
Longman
--
Best Regards
Guo Ren
Quoted 23 lines · Guo Ren
Quoted 17 lines
Quoted 17 lines
Quoted 10 lines
The situation is the SMT scenarios in the same core. Not an entering low-power state situation. Of course, the granularity between cores is "cacheline", but the granularity between SMT hw threads of the same core could be "byte" which internal LSU handles. For example, when a hw-thread yields the resources of the core to other hw-threads, this patch could help the hw-thread stay in the sleep state and prevent it from being woken up by other hw-threads
xchg_tail.Finally, from the software semantic view, does the patch make it more accurate? (We don't care about the tail here.)
Thanks for the clarification.
I am not arguing for the simplification part. I just want to clarify my limited understanding of how the CPU hardware are actually dealing with these conditions.
Quoted 6 lines
Quoted 5 lines
With that, I am fine with this patch. It would be nice if you can elaborate a bit more in your commit log.
Acked-by Waiman Long <[email protected]>BTW, have you actually observe any performance improvement with this patch?
Quoted 9 lines
Not yet. I'm researching how the hardware could satisfy qspinlock better. Here are three points I concluded:
1. Atomic forward progress guarantee: Prevent unnecessary LL/SC
retry, which may cause expensive bus transactions when crossing the NUMA nodes.
2. Sub-word atomic primitive: Enable freedom from interference
between locked, pending, and tail.
3. Load-cond primitive: Prevent processor from wasting loop
operations for detection.
As to this patch, please send a -v2 version of this patch that has this discussion & explanation included in the changelog, as requested by Waiman.
Thanks,
Ingo
Quoted 37 lines · Ingo Molnar
Quoted 23 lines · Guo Ren
Quoted 17 lines
Quoted 17 lines
Quoted 10 lines
The situation is the SMT scenarios in the same core. Not an entering low-power state situation. Of course, the granularity between cores is "cacheline", but the granularity between SMT hw threads of the same core could be "byte" which internal LSU handles. For example, when a hw-thread yields the resources of the core to other hw-threads, this patch could help the hw-thread stay in the sleep state and prevent it from being woken up by other hw-threads
xchg_tail.Finally, from the software semantic view, does the patch make it more accurate? (We don't care about the tail here.)
Thanks for the clarification.
I am not arguing for the simplification part. I just want to clarify my limited understanding of how the CPU hardware are actually dealing with these conditions.
Quoted 6 lines
Quoted 5 lines
With that, I am fine with this patch. It would be nice if you can elaborate a bit more in your commit log.
Acked-by Waiman Long <[email protected]>BTW, have you actually observe any performance improvement with this patch?
Quoted 9 lines
Not yet. I'm researching how the hardware could satisfy qspinlock better. Here are three points I concluded:
1. Atomic forward progress guarantee: Prevent unnecessary LL/SC
retry, which may cause expensive bus transactions when crossing the NUMA nodes.
2. Sub-word atomic primitive: Enable freedom from interference
between locked, pending, and tail.
3. Load-cond primitive: Prevent processor from wasting loop
operations for detection.
Quoted 2 lines
As to this patch, please send a -v2 version of this patch that has this discussion & explanation included in the changelog, as requested by Waiman.
Done
https://lore.kernel.org/lkml/[email protected]/
Quoted 4 lines
Thanks,
Ingo
Signature · 2 lines
Best Regards Guo Ren
Ingo Molnar
AppliedQuoted 38 lines · Guo Ren
Quoted 37 lines · Ingo Molnar
Quoted 32 lines · Guo Ren
Quoted 17 lines
Quoted 17 lines
Quoted 10 lines
The situation is the SMT scenarios in the same core. Not an entering low-power state situation. Of course, the granularity between cores is "cacheline", but the granularity between SMT hw threads of the same core could be "byte" which internal LSU handles. For example, when a hw-thread yields the resources of the core to other hw-threads, this patch could help the hw-thread stay in the sleep state and prevent it from being woken up by other hw-threads
xchg_tail.Finally, from the software semantic view, does the patch make it more accurate? (We don't care about the tail here.)
Thanks for the clarification.
I am not arguing for the simplification part. I just want to clarify my limited understanding of how the CPU hardware are actually dealing with these conditions.
Quoted 6 lines
Quoted 5 lines
With that, I am fine with this patch. It would be nice if you can elaborate a bit more in your commit log.
Acked-by Waiman Long <[email protected]>BTW, have you actually observe any performance improvement with this patch?
Not yet. I'm researching how the hardware could satisfy qspinlock better. Here are three points I concluded:
1. Atomic forward progress guarantee: Prevent unnecessary LL/SC
retry, which may cause expensive bus transactions when crossing the NUMA nodes.
2. Sub-word atomic primitive: Enable freedom from interference
between locked, pending, and tail.
3. Load-cond primitive: Prevent processor from wasting loop
operations for detection.
Quoted 5 lines
Quoted 2 lines
As to this patch, please send a -v2 version of this patch that has this discussion & explanation included in the changelog, as requested by Waiman.
Done
Applied to tip:locking/core for a v6.3 merge, thanks!
Ingo