Skip to contentSkip to conversation

locking/qspinlock: Optimize pending state waiting for unlock

PATCH Applied [email protected] 3 participants 9 messages Dec 24, 2022 – Jan 5, 2023 Locking primitives

v1 of 2 Applied Latest is v2 →

lore
Share & tools
lore
#0 lore raw

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.

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 +2 -2
index 2b23378775fe..ebe6b8ec7cb3 100644
@@ -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
reviewer
#1 lore raw
Quoted 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_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.

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
index 2b23378775fe..ebe6b8ec7cb3 100644

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

author
#2 lore raw
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_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.

Please have a look at the comment I've written.

Quoted 33 lines
Quoted 17 lines
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
index 2b23378775fe..ebe6b8ec7cb3 100644

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.

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
reviewer Acked-by
#3 lore raw
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_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.

Please have a look at the comment I've written.

Quoted 32 lines
Quoted 16 lines
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
index 2b23378775fe..ebe6b8ec7cb3 100644

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.

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.

reviewer
#4 lore raw
Quoted 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_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.

Please have a look at the comment I've written.

Quoted 35 lines
Quoted 24 lines
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
index 2b23378775fe..ebe6b8ec7cb3 100644
@@ -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 __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
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.

BTW, have you actually observe any performance improvement with this patch?

Cheers,
Longman

author
#5 lore raw
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_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.

Please have a look at the comment I've written.

Quoted 35 lines
Quoted 24 lines
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
index 2b23378775fe..ebe6b8ec7cb3 100644
@@ -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 __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
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.

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

#6 lore raw
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.

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

author
#7 lore raw
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.

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
Applied
#8 lore raw
Quoted 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.

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

https://lore.kernel.org/lkml/[email protected]/

Applied to tip:locking/core for a v6.3 merge, thanks!

Ingo