Re: [PATCH v3 3/5] locking/qspinlock: Introduce CNA into the slow path of qspinlock

[Waiman Long]

On 7/17/19 3:44 AM, Peter Zijlstra wrote:
> On Tue, Jul 16, 2019 at 10:16:29PM -0400, Waiman Long wrote:
>>  A simple graphic to illustrate those queues will help too, for example
> Very much yes!
>
>> /*
>> Â* MCS lock holder
>> Â* ===============
>> Â*ÂÂÂ mcs_node
>> Â*ÂÂ +--------+ÂÂÂÂÂ +----+ÂÂÂÂÂÂÂÂ +----+
>> Â* | next | ---> |next| -> ... |next| -> NULL [Main queue]
>> Â*ÂÂ | locked | -+ÂÂ +----+ÂÂÂÂÂÂÂÂ +----+
>> Â*ÂÂ +--------+Â |
>> Â*ÂÂÂÂÂÂÂÂÂÂÂÂÂÂ |ÂÂ +----+ÂÂÂÂÂÂÂÂ +----+
>> Â* +-> |next| -> ... |next| -> X [Secondary queue]
>> Â*ÂÂÂ cna_nodeÂÂÂÂÂÂ +----+ÂÂÂÂÂÂÂÂ +----+
>> Â*ÂÂ +--------*ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ ^
>> Â*ÂÂ | tailÂÂ | ----------------------+
>> Â*ÂÂ +--------*ÂÂÂ
> Almost; IIUC that cna_node is the same as the one from locked, so you
> end up with something like:
>
>> Â*ÂÂÂ mcs_node
>> Â*ÂÂ +--------+ÂÂÂÂÂ +----+ÂÂÂÂÂÂÂÂ +----+
>> Â* | next | ---> |next| -> ... |next| -> NULL [Main queue]
>> Â*ÂÂ | locked | -+ÂÂ +----+ÂÂÂÂÂÂÂÂ +----+
>> Â*ÂÂ +--------+Â |
>> Â*ÂÂÂÂÂÂÂÂÂÂÂÂÂÂ |ÂÂ +---------+ÂÂÂÂÂÂÂÂ +----+
>> Â* +-> |mcs::next| -> ... |next| -> NULL [Secondary queue]
>>  *                   |cna::tail| -+      +----+
>> Â*ÂÂÂ          ÂÂÂÂÂ +---------+  |        ^
>>  *                                +--------+
>> Â*
>> Â* N.B. locked = 1 if secondary queue is absent.
>> Â*/

Yes, you are right. Thanks for the correction.

Cheers,
Longman