[PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[Qiuxu Zhuo]

1. There may be concurrent locker CPUs to set the qspinlock pending bit.

   The first CPU (called pending CPU) of these CPUs sets the pending
   bit to make the state transition (the qspinlock pending bit is set):

         0,0,* -> 0,1,*

   The rest of these CPUs are queued to the MCS queue to make the state
   transition (the qspinlock tail is updated):

         0,1,* -> *,1,*

   The pending CPU waits until the locker owner goes away to make
   the state transition (the qspinlock locked field is set to zero):

         *,1,* -> *,1,0

   The pending CPU takes the ownership and clears the pending bit
   to make the state transition:

         *,1,0 -> *,0,1

2. The header of the MCS queue takes the ownership and calls set_locked()
   to make the state transition:

         *,*,0 -> *,*,1

Fix the state-transition changes above in the code comments accordingly.

Signed-off-by: Qiuxu Zhuo <qiuxu.zhuo@intel.com>
---
 kernel/locking/qspinlock.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index ebe6b8ec7cb3..efebbf19f887 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -257,7 +257,7 @@ static __always_inline u32 queued_fetch_set_pending_acquire(struct qspinlock *lo
  * set_locked - Set the lock bit and own the lock
  * @lock: Pointer to queued spinlock structure
  *
- * *,*,0 -> *,0,1
+ * *,*,0 -> *,*,1
  */
 static __always_inline void set_locked(struct qspinlock *lock)
 {
@@ -348,7 +348,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 	/*
 	 * trylock || pending
 	 *
-	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
+	 * 0,0,* -> 0,1,* -> ... -> *,0,1 pending, trylock
 	 */
 	val = queued_fetch_set_pending_acquire(lock);
 
@@ -358,6 +358,8 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 	 * Undo and queue; our setting of PENDING might have made the
 	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
 	 * on @next to become !NULL.
+	 *
+	 * 0,1,* -> *,1,*
 	 */
 	if (unlikely(val & ~_Q_LOCKED_MASK)) {
 
@@ -371,7 +373,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 -> *,1,0
+	 * *,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
@@ -385,7 +387,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 	/*
 	 * take ownership and clear the pending bit.
 	 *
-	 * 0,1,0 -> 0,0,1
+	 * *,1,0 -> *,0,1
 	 */
 	clear_pending_set_locked(lock);
 	lockevent_inc(lock_pending);
-- 
2.17.1

Re: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[Waiman Long]

On 5/6/23 02:29, Qiuxu Zhuo wrote:
> 1. There may be concurrent locker CPUs to set the qspinlock pending bit.
>
>     The first CPU (called pending CPU) of these CPUs sets the pending
>     bit to make the state transition (the qspinlock pending bit is set):
>
>           0,0,* -> 0,1,*
>
>     The rest of these CPUs are queued to the MCS queue to make the state
>     transition (the qspinlock tail is updated):
>
>           0,1,* -> *,1,*
>
>     The pending CPU waits until the locker owner goes away to make
>     the state transition (the qspinlock locked field is set to zero):
>
>           *,1,* -> *,1,0
>
>     The pending CPU takes the ownership and clears the pending bit
>     to make the state transition:
>
>           *,1,0 -> *,0,1
>
> 2. The header of the MCS queue takes the ownership and calls set_locked()
>     to make the state transition:
>
>           *,*,0 -> *,*,1

That is not true. The pending bit owner has priority over the MCS queue 
head. So the pending bit must be 0 before the MCS queue head can take 
over the lock. So

     *,0,0 -> *,0,1

>
> Fix the state-transition changes above in the code comments accordingly.
>
> Signed-off-by: Qiuxu Zhuo <qiuxu.zhuo@intel.com>
> ---
>   kernel/locking/qspinlock.c | 10 ++++++----
>   1 file changed, 6 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index ebe6b8ec7cb3..efebbf19f887 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -257,7 +257,7 @@ static __always_inline u32 queued_fetch_set_pending_acquire(struct qspinlock *lo
>    * set_locked - Set the lock bit and own the lock
>    * @lock: Pointer to queued spinlock structure
>    *
> - * *,*,0 -> *,0,1
> + * *,*,0 -> *,*,1
set_locked() can only be called when it is sure that the pending bit 
isn't set.
>    */
>   static __always_inline void set_locked(struct qspinlock *lock)
>   {
> @@ -348,7 +348,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>   	/*
>   	 * trylock || pending
>   	 *
> -	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
> +	 * 0,0,* -> 0,1,* -> ... -> *,0,1 pending, trylock

By the time trylock is done, there may be entries in the queue. However, 
I doubt it helps by adding "..." in between possible multiple transitions.


>   	 */
>   	val = queued_fetch_set_pending_acquire(lock);
>   
> @@ -358,6 +358,8 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>   	 * Undo and queue; our setting of PENDING might have made the
>   	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
>   	 * on @next to become !NULL.
> +	 *
> +	 * 0,1,* -> *,1,*
There is already a "n,0,0 -> 0,0,0" above, adding a new one may just 
confuse people.
>   	 */
>   	if (unlikely(val & ~_Q_LOCKED_MASK)) {
>   
> @@ -371,7 +373,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 -> *,1,0
> +	 * *,1,* -> *,1,0

This refers to the wait loop. We don't need to wait if the owner has gone.


>   	 *
>   	 * this wait loop must be a load-acquire such that we match the
>   	 * store-release that clears the locked bit and create lock
> @@ -385,7 +387,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>   	/*
>   	 * take ownership and clear the pending bit.
>   	 *
> -	 * 0,1,0 -> 0,0,1
> +	 * *,1,0 -> *,0,1

That is the part that we can make the change in the transition diagram 
as noted.

Cheers,
Longman

RE: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[Zhuo, Qiuxu]

Hi Wainman,

Thanks for your review. Please see the comments below.

> From: Waiman Long <longman@redhat.com>
> Sent: Monday, May 8, 2023 11:29 PM
> To: Zhuo, Qiuxu <qiuxu.zhuo@intel.com>; Peter Zijlstra
> <peterz@infradead.org>; Ingo Molnar <mingo@redhat.com>; Will Deacon
> <will@kernel.org>
> Cc: Boqun Feng <boqun.feng@gmail.com>; linux-kernel@vger.kernel.org
> Subject: Re: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in
> comments
> 
> 
> On 5/6/23 02:29, Qiuxu Zhuo wrote:
> > 1. There may be concurrent locker CPUs to set the qspinlock pending bit.
> >
> >     The first CPU (called pending CPU) of these CPUs sets the pending
> >     bit to make the state transition (the qspinlock pending bit is set):
> >
> >           0,0,* -> 0,1,*
> >
> >     The rest of these CPUs are queued to the MCS queue to make the state
> >     transition (the qspinlock tail is updated):
> >
> >           0,1,* -> *,1,*
> >
> >     The pending CPU waits until the locker owner goes away to make
> >     the state transition (the qspinlock locked field is set to zero):
> >
> >           *,1,* -> *,1,0
> >
> >     The pending CPU takes the ownership and clears the pending bit
> >     to make the state transition:
> >
> >           *,1,0 -> *,0,1
> >
> > 2. The header of the MCS queue takes the ownership and calls set_locked()
> >     to make the state transition:
> >
> >           *,*,0 -> *,*,1
> 
> That is not true. The pending bit owner has priority over the MCS queue
> head. So the pending bit must be 0 before the MCS queue head can take over
> the lock. So
> 
>      *,0,0 -> *,0,1

Yes, the pending bit must be 0 before the header can take the lock. 
But as the statement "There may be concurrent locker CPUs to set the qspinlock pending bit " at
the beginning. So just after the header takes over the lock, there is also a possible concurrent locker CPU
to set the pending bit. That means at this time point here, the pending bit could be either 0 or 1.

> >
> > Fix the state-transition changes above in the code comments accordingly.
> >
> > Signed-off-by: Qiuxu Zhuo <qiuxu.zhuo@intel.com>
> > ---
> >   kernel/locking/qspinlock.c | 10 ++++++----
> >   1 file changed, 6 insertions(+), 4 deletions(-)
> >
> > diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> > index ebe6b8ec7cb3..efebbf19f887 100644
> > --- a/kernel/locking/qspinlock.c
> > +++ b/kernel/locking/qspinlock.c
> > @@ -257,7 +257,7 @@ static __always_inline u32
> queued_fetch_set_pending_acquire(struct qspinlock *lo
> >    * set_locked - Set the lock bit and own the lock
> >    * @lock: Pointer to queued spinlock structure
> >    *
> > - * *,*,0 -> *,0,1
> > + * *,*,0 -> *,*,1
> set_locked() can only be called when it is sure that the pending bit isn't set.
> >    */
> >   static __always_inline void set_locked(struct qspinlock *lock)
> >   {
> > @@ -348,7 +348,7 @@ void __lockfunc queued_spin_lock_slowpath(struct
> qspinlock *lock, u32 val)
> >   	/*
> >   	 * trylock || pending
> >   	 *
> > -	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
> > +	 * 0,0,* -> 0,1,* -> ... -> *,0,1 pending, trylock
> 
> By the time trylock is done, there may be entries in the queue. However, I
> doubt it helps by adding "..." in between possible multiple transitions.
> 

The added "..." means there could be entries in the queue before trylock done.
This is just for making the state transitions more complete ;-). 
If you think it doesn't help, I can remove it in the next version.

> >   	 */
> >   	val = queued_fetch_set_pending_acquire(lock);
> >
> > @@ -358,6 +358,8 @@ void __lockfunc queued_spin_lock_slowpath(struct
> qspinlock *lock, u32 val)
> >   	 * Undo and queue; our setting of PENDING might have made the
> >   	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
> >   	 * on @next to become !NULL.
> > +	 *
> > +	 * 0,1,* -> *,1,*
> There is already a "n,0,0 -> 0,0,0" above, adding a new one may just
> confuse people.
> >   	 */
> >   	if (unlikely(val & ~_Q_LOCKED_MASK)) {
> >
> > @@ -371,7 +373,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 -> *,1,0
> > +	 * *,1,* -> *,1,0
> 
> This refers to the wait loop. We don't need to wait if the owner has gone.

But just before we wait for the locked field, the locked field could be
either 0 (the locker can release the lock at any time) or 1.

> 
> >   	 *
> >   	 * this wait loop must be a load-acquire such that we match the
> >   	 * store-release that clears the locked bit and create lock
> > @@ -385,7 +387,7 @@ void __lockfunc queued_spin_lock_slowpath(struct
> qspinlock *lock, u32 val)
> >   	/*
> >   	 * take ownership and clear the pending bit.
> >   	 *
> > -	 * 0,1,0 -> 0,0,1
> > +	 * *,1,0 -> *,0,1
> 
> That is the part that we can make the change in the transition diagram
> as noted.

Sorry, I'm not clear about your request. 
Did you mean just make the change "*,1,0 -> *,0,1" above in the transition diagram or
all the changes above in the transition diagram? 

Thanks!
-Qiuxu

> Cheers,
> Longman

Re: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[Waiman Long]

On 5/8/23 22:03, Zhuo, Qiuxu wrote:
> Hi Wainman,
>
> Thanks for your review. Please see the comments below.
>
>> From: Waiman Long <longman@redhat.com>
>> Sent: Monday, May 8, 2023 11:29 PM
>> To: Zhuo, Qiuxu <qiuxu.zhuo@intel.com>; Peter Zijlstra
>> <peterz@infradead.org>; Ingo Molnar <mingo@redhat.com>; Will Deacon
>> <will@kernel.org>
>> Cc: Boqun Feng <boqun.feng@gmail.com>; linux-kernel@vger.kernel.org
>> Subject: Re: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in
>> comments
>>
>>
>> On 5/6/23 02:29, Qiuxu Zhuo wrote:
>>> 1. There may be concurrent locker CPUs to set the qspinlock pending bit.
>>>
>>>      The first CPU (called pending CPU) of these CPUs sets the pending
>>>      bit to make the state transition (the qspinlock pending bit is set):
>>>
>>>            0,0,* -> 0,1,*
>>>
>>>      The rest of these CPUs are queued to the MCS queue to make the state
>>>      transition (the qspinlock tail is updated):
>>>
>>>            0,1,* -> *,1,*
>>>
>>>      The pending CPU waits until the locker owner goes away to make
>>>      the state transition (the qspinlock locked field is set to zero):
>>>
>>>            *,1,* -> *,1,0
>>>
>>>      The pending CPU takes the ownership and clears the pending bit
>>>      to make the state transition:
>>>
>>>            *,1,0 -> *,0,1
>>>
>>> 2. The header of the MCS queue takes the ownership and calls set_locked()
>>>      to make the state transition:
>>>
>>>            *,*,0 -> *,*,1
>> That is not true. The pending bit owner has priority over the MCS queue
>> head. So the pending bit must be 0 before the MCS queue head can take over
>> the lock. So
>>
>>       *,0,0 -> *,0,1
> Yes, the pending bit must be 0 before the header can take the lock.
> But as the statement "There may be concurrent locker CPUs to set the qspinlock pending bit " at
> the beginning. So just after the header takes over the lock, there is also a possible concurrent locker CPU
> to set the pending bit. That means at this time point here, the pending bit could be either 0 or 1.

OK, I am looking from the point of view of the CPU doing the transition. 
Otherwise, for an arch with very weak memory ordering, anything is 
possible. i.e. *,*,* -> *,*,* if we have to consider what all the CPUs 
in the system can see.


>
>>> Fix the state-transition changes above in the code comments accordingly.
>>>
>>> Signed-off-by: Qiuxu Zhuo <qiuxu.zhuo@intel.com>
>>> ---
>>>    kernel/locking/qspinlock.c | 10 ++++++----
>>>    1 file changed, 6 insertions(+), 4 deletions(-)
>>>
>>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
>>> index ebe6b8ec7cb3..efebbf19f887 100644
>>> --- a/kernel/locking/qspinlock.c
>>> +++ b/kernel/locking/qspinlock.c
>>> @@ -257,7 +257,7 @@ static __always_inline u32
>> queued_fetch_set_pending_acquire(struct qspinlock *lo
>>>     * set_locked - Set the lock bit and own the lock
>>>     * @lock: Pointer to queued spinlock structure
>>>     *
>>> - * *,*,0 -> *,0,1
>>> + * *,*,0 -> *,*,1
>> set_locked() can only be called when it is sure that the pending bit isn't set.
>>>     */
>>>    static __always_inline void set_locked(struct qspinlock *lock)
>>>    {
>>> @@ -348,7 +348,7 @@ void __lockfunc queued_spin_lock_slowpath(struct
>> qspinlock *lock, u32 val)
>>>    	/*
>>>    	 * trylock || pending
>>>    	 *
>>> -	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
>>> +	 * 0,0,* -> 0,1,* -> ... -> *,0,1 pending, trylock
>> By the time trylock is done, there may be entries in the queue. However, I
>> doubt it helps by adding "..." in between possible multiple transitions.
>>
> The added "..." means there could be entries in the queue before trylock done.
> This is just for making the state transitions more complete ;-).
> If you think it doesn't help, I can remove it in the next version.

The transition flow does not show whether there is entry in the queue or 
not. It just shows the state of the lock word.


>
>>>    	 */
>>>    	val = queued_fetch_set_pending_acquire(lock);
>>>
>>> @@ -358,6 +358,8 @@ void __lockfunc queued_spin_lock_slowpath(struct
>> qspinlock *lock, u32 val)
>>>    	 * Undo and queue; our setting of PENDING might have made the
>>>    	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
>>>    	 * on @next to become !NULL.
>>> +	 *
>>> +	 * 0,1,* -> *,1,*
>> There is already a "n,0,0 -> 0,0,0" above, adding a new one may just
>> confuse people.
>>>    	 */
>>>    	if (unlikely(val & ~_Q_LOCKED_MASK)) {
>>>
>>> @@ -371,7 +373,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 -> *,1,0
>>> +	 * *,1,* -> *,1,0
>> This refers to the wait loop. We don't need to wait if the owner has gone.
> But just before we wait for the locked field, the locked field could be
> either 0 (the locker can release the lock at any time) or 1.

Again, I take the viewpoint of the CPU doing the wait. It will only wait 
if it observes that the lock isn't free.


>
>>>    	 *
>>>    	 * this wait loop must be a load-acquire such that we match the
>>>    	 * store-release that clears the locked bit and create lock
>>> @@ -385,7 +387,7 @@ void __lockfunc queued_spin_lock_slowpath(struct
>> qspinlock *lock, u32 val)
>>>    	/*
>>>    	 * take ownership and clear the pending bit.
>>>    	 *
>>> -	 * 0,1,0 -> 0,0,1
>>> +	 * *,1,0 -> *,0,1
>> That is the part that we can make the change in the transition diagram
>> as noted.
> Sorry, I'm not clear about your request.
> Did you mean just make the change "*,1,0 -> *,0,1" above in the transition diagram or
> all the changes above in the transition diagram?

What I meant is that this particular change is correct AFAICS. Sorry for 
the confusion.

Cheers,
Longman

RE: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[Zhuo, Qiuxu]

Hi Longman,

OK, so, you are from the point of view of the CPU (the lock word value it read last time)
doing state transition in the uncontended scenario: 

     [1]:  Old lock word value (this CPU read it last time) ---> New lock word value

I'm from the point of view of the current lock word possible value that its state is 
transited to the new lock word possible value (I don't think I'm the only one from 
this point of view when reading the qspinlock code ;-).

     [2]: Current lock word possible value ---> New lock word possible value 

I'm fine to keep the view of [1] in the current code and get [2] as the backup.
I'll send out a v2 with just two minor comments' fixes. 

Thanks!
-Qiuxu

> From: Waiman Long <longman@redhat.com>
> Sent: Tuesday, May 9, 2023 10:31 AM
> To: Zhuo, Qiuxu <qiuxu.zhuo@intel.com>; Peter Zijlstra
> <peterz@infradead.org>; Ingo Molnar <mingo@redhat.com>; Will Deacon
> <will@kernel.org>
> Cc: Boqun Feng <boqun.feng@gmail.com>; linux-kernel@vger.kernel.org
> Subject: Re: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in
> comments
> 
> On 5/8/23 22:03, Zhuo, Qiuxu wrote:
> > Hi Wainman,
> >
> > Thanks for your review. Please see the comments below.
> >
> >> From: Waiman Long <longman@redhat.com>
> >> Sent: Monday, May 8, 2023 11:29 PM
> >> To: Zhuo, Qiuxu <qiuxu.zhuo@intel.com>; Peter Zijlstra
> >> <peterz@infradead.org>; Ingo Molnar <mingo@redhat.com>; Will Deacon
> >> <will@kernel.org>
> >> Cc: Boqun Feng <boqun.feng@gmail.com>; linux-kernel@vger.kernel.org
> >> Subject: Re: [PATCH 1/1] locking/qspinlock: Fix state-transition
> >> changes in comments
> >>
> >>
> >> On 5/6/23 02:29, Qiuxu Zhuo wrote:
> >>> 1. There may be concurrent locker CPUs to set the qspinlock pending bit.
> >>>
> >>>      The first CPU (called pending CPU) of these CPUs sets the pending
> >>>      bit to make the state transition (the qspinlock pending bit is set):
> >>>
> >>>            0,0,* -> 0,1,*
> >>>
> >>>      The rest of these CPUs are queued to the MCS queue to make the
> state
> >>>      transition (the qspinlock tail is updated):
> >>>
> >>>            0,1,* -> *,1,*
> >>>
> >>>      The pending CPU waits until the locker owner goes away to make
> >>>      the state transition (the qspinlock locked field is set to zero):
> >>>
> >>>            *,1,* -> *,1,0
> >>>
> >>>      The pending CPU takes the ownership and clears the pending bit
> >>>      to make the state transition:
> >>>
> >>>            *,1,0 -> *,0,1
> >>>
> >>> 2. The header of the MCS queue takes the ownership and calls
> set_locked()
> >>>      to make the state transition:
> >>>
> >>>            *,*,0 -> *,*,1
> >> That is not true. The pending bit owner has priority over the MCS
> >> queue head. So the pending bit must be 0 before the MCS queue head
> >> can take over the lock. So
> >>
> >>       *,0,0 -> *,0,1
> > Yes, the pending bit must be 0 before the header can take the lock.
> > But as the statement "There may be concurrent locker CPUs to set the
> > qspinlock pending bit " at the beginning. So just after the header
> > takes over the lock, there is also a possible concurrent locker CPU to set the
> pending bit. That means at this time point here, the pending bit could be
> either 0 or 1.
> 
> OK, I am looking from the point of view of the CPU doing the transition.
> Otherwise, for an arch with very weak memory ordering, anything is possible.
> i.e. *,*,* -> *,*,* if we have to consider what all the CPUs in the system can
> see.
> 
> 
> >
> >>> Fix the state-transition changes above in the code comments accordingly.
> >>>
> >>> Signed-off-by: Qiuxu Zhuo <qiuxu.zhuo@intel.com>
> >>> ---
> >>>    kernel/locking/qspinlock.c | 10 ++++++----
> >>>    1 file changed, 6 insertions(+), 4 deletions(-)
> >>>
> >>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> >>> index ebe6b8ec7cb3..efebbf19f887 100644
> >>> --- a/kernel/locking/qspinlock.c
> >>> +++ b/kernel/locking/qspinlock.c
> >>> @@ -257,7 +257,7 @@ static __always_inline u32
> >> queued_fetch_set_pending_acquire(struct qspinlock *lo
> >>>     * set_locked - Set the lock bit and own the lock
> >>>     * @lock: Pointer to queued spinlock structure
> >>>     *
> >>> - * *,*,0 -> *,0,1
> >>> + * *,*,0 -> *,*,1
> >> set_locked() can only be called when it is sure that the pending bit isn't set.
> >>>     */
> >>>    static __always_inline void set_locked(struct qspinlock *lock)
> >>>    {
> >>> @@ -348,7 +348,7 @@ void __lockfunc
> queued_spin_lock_slowpath(struct
> >> qspinlock *lock, u32 val)
> >>>    	/*
> >>>    	 * trylock || pending
> >>>    	 *
> >>> -	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
> >>> +	 * 0,0,* -> 0,1,* -> ... -> *,0,1 pending, trylock
> >> By the time trylock is done, there may be entries in the queue.
> >> However, I doubt it helps by adding "..." in between possible multiple
> transitions.
> >>
> > The added "..." means there could be entries in the queue before trylock
> done.
> > This is just for making the state transitions more complete ;-).
> > If you think it doesn't help, I can remove it in the next version.
> 
> The transition flow does not show whether there is entry in the queue or not.
> It just shows the state of the lock word.
> 
> 
> >
> >>>    	 */
> >>>    	val = queued_fetch_set_pending_acquire(lock);
> >>>
> >>> @@ -358,6 +358,8 @@ void __lockfunc
> queued_spin_lock_slowpath(struct
> >> qspinlock *lock, u32 val)
> >>>    	 * Undo and queue; our setting of PENDING might have made the
> >>>    	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
> >>>    	 * on @next to become !NULL.
> >>> +	 *
> >>> +	 * 0,1,* -> *,1,*
> >> There is already a "n,0,0 -> 0,0,0" above, adding a new one may just
> >> confuse people.
> >>>    	 */
> >>>    	if (unlikely(val & ~_Q_LOCKED_MASK)) {
> >>>
> >>> @@ -371,7 +373,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 -> *,1,0
> >>> +	 * *,1,* -> *,1,0
> >> This refers to the wait loop. We don't need to wait if the owner has gone.
> > But just before we wait for the locked field, the locked field could be
> > either 0 (the locker can release the lock at any time) or 1.
> 
> Again, I take the viewpoint of the CPU doing the wait. It will only wait
> if it observes that the lock isn't free.
> 
> 
> >
> >>>    	 *
> >>>    	 * this wait loop must be a load-acquire such that we match the
> >>>    	 * store-release that clears the locked bit and create lock
> >>> @@ -385,7 +387,7 @@ void __lockfunc
> queued_spin_lock_slowpath(struct
> >> qspinlock *lock, u32 val)
> >>>    	/*
> >>>    	 * take ownership and clear the pending bit.
> >>>    	 *
> >>> -	 * 0,1,0 -> 0,0,1
> >>> +	 * *,1,0 -> *,0,1
> >> That is the part that we can make the change in the transition diagram
> >> as noted.
> > Sorry, I'm not clear about your request.
> > Did you mean just make the change "*,1,0 -> *,0,1" above in the transition
> diagram or
> > all the changes above in the transition diagram?
> 
> What I meant is that this particular change is correct AFAICS. Sorry for
> the confusion.
> 
> Cheers,
> Longman

[PATCH v2 1/1] locking/qspinlock: Fix state-transition changes in comments

[Qiuxu Zhuo]

1. set_locked() only sets the locked field to 1 and doesn't touch
   the pending field. So the correct lock state transition is:

         *,*,0 -> *,*,1

2. The initial lock state when calling clear_pending_set_locked() is
   the state just after waiting for the locker goes away. So the
   state transition for clear_pending_set_locked() is:

         *,1,0 -> *,0,1

Signed-off-by: Qiuxu Zhuo <qiuxu.zhuo@intel.com>
---
 v1->v2:
 - Drop the state transition comments fixes (viewed from the current lock word value).
 - Update the commit message accordingly.

 kernel/locking/qspinlock.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index ebe6b8ec7cb3..256021c87ac1 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -257,7 +257,7 @@ static __always_inline u32 queued_fetch_set_pending_acquire(struct qspinlock *lo
  * set_locked - Set the lock bit and own the lock
  * @lock: Pointer to queued spinlock structure
  *
- * *,*,0 -> *,0,1
+ * *,*,0 -> *,*,1
  */
 static __always_inline void set_locked(struct qspinlock *lock)
 {
@@ -385,7 +385,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
 	/*
 	 * take ownership and clear the pending bit.
 	 *
-	 * 0,1,0 -> 0,0,1
+	 * *,1,0 -> *,0,1
 	 */
 	clear_pending_set_locked(lock);
 	lockevent_inc(lock_pending);
-- 
2.17.1

Re: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[Waiman Long]

On 5/9/23 02:57, Zhuo, Qiuxu wrote:
> Hi Longman,
>
> OK, so, you are from the point of view of the CPU (the lock word value it read last time)
> doing state transition in the uncontended scenario:
>
>       [1]:  Old lock word value (this CPU read it last time) ---> New lock word value
>
> I'm from the point of view of the current lock word possible value that its state is
> transited to the new lock word possible value (I don't think I'm the only one from
> this point of view when reading the qspinlock code ;-).
>
>       [2]: Current lock word possible value ---> New lock word possible value
>
> I'm fine to keep the view of [1] in the current code and get [2] as the backup.
> I'll send out a v2 with just two minor comments' fixes.

The purpose of those transition flow charts is to help understand what 
the code is doing. So they should reflect the running CPU point of view. 
If you want to show what all the possible values can be, you have to 
explicitly state that to avoid the confusion.

Thanks,
Longman

Re: [PATCH v2 1/1] locking/qspinlock: Fix state-transition changes in comments

[Waiman Long]

On 5/9/23 03:29, Qiuxu Zhuo wrote:
> 1. set_locked() only sets the locked field to 1 and doesn't touch
>     the pending field. So the correct lock state transition is:
>
>           *,*,0 -> *,*,1
>
> 2. The initial lock state when calling clear_pending_set_locked() is
>     the state just after waiting for the locker goes away. So the
>     state transition for clear_pending_set_locked() is:
>
>           *,1,0 -> *,0,1
>
> Signed-off-by: Qiuxu Zhuo <qiuxu.zhuo@intel.com>
> ---
>   v1->v2:
>   - Drop the state transition comments fixes (viewed from the current lock word value).
>   - Update the commit message accordingly.
>
>   kernel/locking/qspinlock.c | 4 ++--
>   1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index ebe6b8ec7cb3..256021c87ac1 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -257,7 +257,7 @@ static __always_inline u32 queued_fetch_set_pending_acquire(struct qspinlock *lo
>    * set_locked - Set the lock bit and own the lock
>    * @lock: Pointer to queued spinlock structure
>    *
> - * *,*,0 -> *,0,1
> + * *,*,0 -> *,*,1
>    */
>   static __always_inline void set_locked(struct qspinlock *lock)
>   {
> @@ -385,7 +385,7 @@ void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
>   	/*
>   	 * take ownership and clear the pending bit.
>   	 *
> -	 * 0,1,0 -> 0,0,1
> +	 * *,1,0 -> *,0,1
>   	 */
>   	clear_pending_set_locked(lock);
>   	lockevent_inc(lock_pending);
Acked-by: Waiman Long <longman@redhat.com>

RE: [PATCH 1/1] locking/qspinlock: Fix state-transition changes in comments

[Zhuo, Qiuxu]

> From: Waiman Long <longman@redhat.com>
> ...
> >
> > OK, so, you are from the point of view of the CPU (the lock word value
> > it read last time) doing state transition in the uncontended scenario:
> >
> >       [1]:  Old lock word value (this CPU read it last time) ---> New
> > lock word value
> >
> > I'm from the point of view of the current lock word possible value
> > that its state is transited to the new lock word possible value (I
> > don't think I'm the only one from this point of view when reading the
> qspinlock code ;-).
> >
> >       [2]: Current lock word possible value ---> New lock word
> > possible value
> >
> > I'm fine to keep the view of [1] in the current code and get [2] as the
> backup.
> > I'll send out a v2 with just two minor comments' fixes.
> 
> The purpose of those transition flow charts is to help understand what the
> code is doing. So they should reflect the running CPU point of view.
> If you want to show what all the possible values can be, you have to explicitly
> state that to avoid the confusion.

Yes, from the uncontended case view can help readers understand the qspinlock code.
After that, readers find that the qspinlock code also works for contended cases. 

Thank you for the clarification of the purpose of those state transition comments.

-Qiuxu

> Thanks,
> Longman