Re: [PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

Re: [PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Alex Kogan]

----- longman@redhat.com wrote:

> On 11/25/19 4:07 PM, Alex Kogan wrote:
> > @@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct
> qspinlock *lock,
> >  	struct cna_node *cn = (struct cna_node *)node;
> >  
> >  	/*
> > -	 * setting @pre_scan_result to 1 indicates that no post-scan
> > +	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
> >  	 * should be made in cna_pass_lock()
> >  	 */
> >  	cn->pre_scan_result =
> > -		cn->intra_count == intra_node_handoff_threshold ?
> > -			1 : cna_scan_main_queue(node, node);
> > +		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
> > +			1 : cn->intra_count == intra_node_handoff_threshold ?
> > +			2 : cna_scan_main_queue(node, node);
> >  
> >  	return 0;
> >  }
> > @@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct
> mcs_spinlock *node,
> >  
> >  	u32 scan = cn->pre_scan_result;
> >  
> > +	if (scan == 1)
> > +		goto pass_lock;
> > +
> >  	/*
> >  	 * check if a successor from the same numa node has not been found
> in
> >  	 * pre-scan, and if so, try to find it in post-scan starting from
> the
> >  	 * node where pre-scan stopped (stored in @pre_scan_result)
> >  	 */
> > -	if (scan > 1)
> > +	if (scan > 2)
> >  		scan = cna_scan_main_queue(node, decode_tail(scan));
> >  
> >  	if (!scan) { /* if found a successor from the same numa node */
> > @@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct
> mcs_spinlock *node,
> >  		tail_2nd->next = next;
> >  	}
> >  
> > +pass_lock:
> >  	arch_mcs_pass_lock(&next_holder->locked, val);
> >  }
> 
> I think you might have mishandled the proper accounting of
> intra_count.
> How about something like:
> 
> diff --git a/kernel/locking/qspinlock_cna.h
> b/kernel/locking/qspinlock_cna.h
> index f1eef6bece7b..03f8fdec2b80 100644
> --- a/kernel/locking/qspinlock_cna.h
> +++ b/kernel/locking/qspinlock_cna.h
> @@ -268,7 +268,7 @@ __always_inline u32 cna_pre_scan(struct qspinlock
> *lock,
>          */
>         cn->pre_scan_result =
>                 (node->locked <= 1 &&
> probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
> -                       1 : cn->intra_count ==
> intra_node_handoff_threshold ?
> +                       1 : cn->intra_count >=
> intra_node_handoff_threshold ?

We reset ‘intra_count' in cna_init_node(), which is called before we enter 
the slow path, and set it at most once when we pass the internal (CNA) lock
by taking the owner’s value + 1. Only after we get the internal lock, we
call this cna_pre_scan() function, where we check the threshold. 
IOW, having 'intra_count > intra_node_handoff_threshold' would mean a bug, 
and having “>=“ would mask it. 
Perhaps I can add WARN_ON(cn->intra_count > intra_node_handoff_threshold)
here instead, although I'm not sure if that is a good idea performance-wise.

>                         2 : cna_scan_main_queue(node, node);
>  
>         return 0;
> @@ -283,9 +283,6 @@ static inline void cna_pass_lock(struct
> mcs_spinlock
> *node,
>  
>         u32 scan = cn->pre_scan_result;
>  
> -       if (scan == 1)
> -               goto pass_lock;
> -
The thing is that we want to avoid as much of the shuffling-related overhead
as we can when the spinlock is only lightly contended. That's why we have this
early exit here that avoids the rest of the logic of triaging through possible
'scan' values.

>         /*
>          * check if a successor from the same numa node has not been
> found in
>          * pre-scan, and if so, try to find it in post-scan starting
> from the
> @@ -294,7 +291,13 @@ static inline void cna_pass_lock(struct
> mcs_spinlock *node,
>         if (scan > 2)
>                 scan = cna_scan_main_queue(node, decode_tail(scan));
>  
> -       if (!scan) { /* if found a successor from the same numa node
> */
> +       if (scan <= 1) { /* if found a successor from the same numa
> node */
> +               /* inc @intra_count if the secondary queue is not
> empty */
> +               ((struct cna_node *)next_holder)->intra_count =
> +                       cn->intra_count + (node->locked > 1);
> +               if ((scan == 1)
> +                       goto pass_lock;
> +
Hmm, I am not sure this makes the code any better/more readable,
while this does add the overhead of going through 3 branches before
jumping to 'pass_lock'.

>                 next_holder = node->next;
>                 /*
>                  * we unlock successor by passing a non-zero value,
> @@ -302,9 +305,6 @@ static inline void cna_pass_lock(struct
> mcs_spinlock
> *node,
>                  * if we acquired the MCS lock when its queue was
> empty
>                  */
>                 val = node->locked ? node->locked : 1;
> -               /* inc @intra_count if the secondary queue is not
> empty */
> -               ((struct cna_node *)next_holder)->intra_count =
> -                       cn->intra_count + (node->locked > 1);
>         } else if (node->locked > 1) {    /* if secondary queue is
> not
> empty */
>                 /* next holder will be the first node in the
> secondary
> queue */
>                 tail_2nd = decode_tail(node->locked);
> 
> The meaning of scan value:
> 
> 0 - pass to next cna node, which is in the same numa node. Additional
> cna node may or may not be added to the secondary queue
> 
> 1 - pass to next cna node, which may not be in the same numa node. No
> change to secondary queue
> 
> 2 - exceed intra node handoff threshold, unconditionally merge back
> the
> secondary queue cna nodes, if available
> 
> >2 no cna node of the same numa node found, unconditionally merge
> back
> the secondary queue cna nodes, if available
'scan' passes information from pre_scan to pass_lock.
The way I see its values is similar, but slightly different:

1 - pass to next cna node, which may not be in the same numa node. No
change to secondary queue.

2 - exceed intra node handoff threshold, unconditionally merge back
the secondary queue cna nodes, if available.

0 - pass to next cna node, which is in the same numa node. pre_scan found 
that node, and no further changes to the secondary queue are necessary.

>2 pre_scan could not find cna node in the same numa node. Scan the main
queue from the point where pre_scan stopped, and pass the lock according
to the result of this scan.

> 
> The code will be easier to read if symbolic names instead of just
> numbers.
I agree with that. I guess the challenge would be to find short enough symbols
that would convey the meaning of various values. I will think about that.

Best regards,
-- Alex

Re: [PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Alex Kogan]

----- longman@redhat.com wrote:

> On 11/25/19 4:07 PM, Alex Kogan wrote:
> > @@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct
> qspinlock *lock,
> >  	struct cna_node *cn = (struct cna_node *)node;
> >  
> >  	/*
> > -	 * setting @pre_scan_result to 1 indicates that no post-scan
> > +	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
> >  	 * should be made in cna_pass_lock()
> >  	 */
> >  	cn->pre_scan_result =
> > -		cn->intra_count == intra_node_handoff_threshold ?
> > -			1 : cna_scan_main_queue(node, node);
> > +		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
> > +			1 : cn->intra_count == intra_node_handoff_threshold ?
> > +			2 : cna_scan_main_queue(node, node);
> >  
> >  	return 0;
> >  }
> > @@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct
> mcs_spinlock *node,
> >  
> >  	u32 scan = cn->pre_scan_result;
> >  
> > +	if (scan == 1)
> > +		goto pass_lock;
> > +
> >  	/*
> >  	 * check if a successor from the same numa node has not been found
> in
> >  	 * pre-scan, and if so, try to find it in post-scan starting from
> the
> >  	 * node where pre-scan stopped (stored in @pre_scan_result)
> >  	 */
> > -	if (scan > 1)
> > +	if (scan > 2)
> >  		scan = cna_scan_main_queue(node, decode_tail(scan));
> >  
> >  	if (!scan) { /* if found a successor from the same numa node */
> > @@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct
> mcs_spinlock *node,
> >  		tail_2nd->next = next;
> >  	}
> >  
> > +pass_lock:
> >  	arch_mcs_pass_lock(&next_holder->locked, val);
> >  }
> 
> I think you might have mishandled the proper accounting of
> intra_count.
> How about something like:
> 
> diff --git a/kernel/locking/qspinlock_cna.h
> b/kernel/locking/qspinlock_cna.h
> index f1eef6bece7b..03f8fdec2b80 100644
> --- a/kernel/locking/qspinlock_cna.h
> +++ b/kernel/locking/qspinlock_cna.h
> @@ -268,7 +268,7 @@ __always_inline u32 cna_pre_scan(struct qspinlock
> *lock,
>          */
>         cn->pre_scan_result =
>                 (node->locked <= 1 &&
> probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
> -                       1 : cn->intra_count ==
> intra_node_handoff_threshold ?
> +                       1 : cn->intra_count >=
> intra_node_handoff_threshold ?

We reset ‘intra_count' in cna_init_node(), which is called before we enter 
the slow path, and set it at most once when we pass the internal (CNA) lock
by taking the owner’s value + 1. Only after we get the internal lock, we
call this cna_pre_scan() function, where we check the threshold. 
IOW, having 'intra_count > intra_node_handoff_threshold' would mean a bug, 
and having “>=“ would mask it. 
Perhaps I can add WARN_ON(cn->intra_count > intra_node_handoff_threshold)
here instead, although I'm not sure if that is a good idea performance-wise.

>                         2 : cna_scan_main_queue(node, node);
>  
>         return 0;
> @@ -283,9 +283,6 @@ static inline void cna_pass_lock(struct
> mcs_spinlock
> *node,
>  
>         u32 scan = cn->pre_scan_result;
>  
> -       if (scan == 1)
> -               goto pass_lock;
> -
The thing is that we want to avoid as much of the shuffling-related overhead
as we can when the spinlock is only lightly contended. That's why we have this
early exit here that avoids the rest of the logic of triaging through possible
'scan' values.

>         /*
>          * check if a successor from the same numa node has not been
> found in
>          * pre-scan, and if so, try to find it in post-scan starting
> from the
> @@ -294,7 +291,13 @@ static inline void cna_pass_lock(struct
> mcs_spinlock *node,
>         if (scan > 2)
>                 scan = cna_scan_main_queue(node, decode_tail(scan));
>  
> -       if (!scan) { /* if found a successor from the same numa node
> */
> +       if (scan <= 1) { /* if found a successor from the same numa
> node */
> +               /* inc @intra_count if the secondary queue is not
> empty */
> +               ((struct cna_node *)next_holder)->intra_count =
> +                       cn->intra_count + (node->locked > 1);
> +               if ((scan == 1)
> +                       goto pass_lock;
> +
Hmm, I am not sure this makes the code any better/more readable,
while this does add the overhead of going through 3 branches before
jumping to 'pass_lock'.

>                 next_holder = node->next;
>                 /*
>                  * we unlock successor by passing a non-zero value,
> @@ -302,9 +305,6 @@ static inline void cna_pass_lock(struct
> mcs_spinlock
> *node,
>                  * if we acquired the MCS lock when its queue was
> empty
>                  */
>                 val = node->locked ? node->locked : 1;
> -               /* inc @intra_count if the secondary queue is not
> empty */
> -               ((struct cna_node *)next_holder)->intra_count =
> -                       cn->intra_count + (node->locked > 1);
>         } else if (node->locked > 1) {    /* if secondary queue is
> not
> empty */
>                 /* next holder will be the first node in the
> secondary
> queue */
>                 tail_2nd = decode_tail(node->locked);
> 
> The meaning of scan value:
> 
> 0 - pass to next cna node, which is in the same numa node. Additional
> cna node may or may not be added to the secondary queue
> 
> 1 - pass to next cna node, which may not be in the same numa node. No
> change to secondary queue
> 
> 2 - exceed intra node handoff threshold, unconditionally merge back
> the
> secondary queue cna nodes, if available
> 
> >2 no cna node of the same numa node found, unconditionally merge
> back
> the secondary queue cna nodes, if available
'scan' passes information from pre_scan to pass_lock.
The way I see its values is similar, but slightly different:

1 - pass to next cna node, which may not be in the same numa node. No
change to secondary queue.

2 - exceed intra node handoff threshold, unconditionally merge back
the secondary queue cna nodes, if available.

0 - pass to next cna node, which is in the same numa node. pre_scan found 
that node, and no further changes to the secondary queue are necessary.

>2 pre_scan could not find cna node in the same numa node. Scan the main
queue from the point where pre_scan stopped, and pass the lock according
to the result of this scan.

> 
> The code will be easier to read if symbolic names instead of just
> numbers.
I agree with that. I guess the challenge would be to find short enough symbols
that would convey the meaning of various values. I will think about that.

Best regards,
-- Alex

Re: [PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Waiman Long]

On 12/10/19 1:56 PM, Alex Kogan wrote:
> ----- longman@redhat.com wrote:
>
>> On 11/25/19 4:07 PM, Alex Kogan wrote:
>>> @@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct
>> qspinlock *lock,
>>>  	struct cna_node *cn = (struct cna_node *)node;
>>>  
>>>  	/*
>>> -	 * setting @pre_scan_result to 1 indicates that no post-scan
>>> +	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
>>>  	 * should be made in cna_pass_lock()
>>>  	 */
>>>  	cn->pre_scan_result =
>>> -		cn->intra_count == intra_node_handoff_threshold ?
>>> -			1 : cna_scan_main_queue(node, node);
>>> +		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
>>> +			1 : cn->intra_count == intra_node_handoff_threshold ?
>>> +			2 : cna_scan_main_queue(node, node);
>>>  
>>>  	return 0;
>>>  }
>>> @@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock *node,
>>>  
>>>  	u32 scan = cn->pre_scan_result;
>>>  
>>> +	if (scan == 1)
>>> +		goto pass_lock;
>>> +
>>>  	/*
>>>  	 * check if a successor from the same numa node has not been found
>> in
>>>  	 * pre-scan, and if so, try to find it in post-scan starting from
>> the
>>>  	 * node where pre-scan stopped (stored in @pre_scan_result)
>>>  	 */
>>> -	if (scan > 1)
>>> +	if (scan > 2)
>>>  		scan = cna_scan_main_queue(node, decode_tail(scan));
>>>  
>>>  	if (!scan) { /* if found a successor from the same numa node */
>>> @@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock *node,
>>>  		tail_2nd->next = next;
>>>  	}
>>>  
>>> +pass_lock:
>>>  	arch_mcs_pass_lock(&next_holder->locked, val);
>>>  }
>> I think you might have mishandled the proper accounting of
>> intra_count.
>> How about something like:
>>
>> diff --git a/kernel/locking/qspinlock_cna.h
>> b/kernel/locking/qspinlock_cna.h
>> index f1eef6bece7b..03f8fdec2b80 100644
>> --- a/kernel/locking/qspinlock_cna.h
>> +++ b/kernel/locking/qspinlock_cna.h
>> @@ -268,7 +268,7 @@ __always_inline u32 cna_pre_scan(struct qspinlock
>> *lock,
>>          */
>>         cn->pre_scan_result =
>>                 (node->locked <= 1 &&
>> probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
>> -                       1 : cn->intra_count ==
>> intra_node_handoff_threshold ?
>> +                       1 : cn->intra_count >=
>> intra_node_handoff_threshold ?
> We reset ‘intra_count' in cna_init_node(), which is called before we enter 
> the slow path, and set it at most once when we pass the internal (CNA) lock
> by taking the owner’s value + 1. Only after we get the internal lock, we
> call this cna_pre_scan() function, where we check the threshold. 
> IOW, having 'intra_count > intra_node_handoff_threshold' would mean a bug, 
> and having “>=“ would mask it. 
> Perhaps I can add WARN_ON(cn->intra_count > intra_node_handoff_threshold)
> here instead, although I'm not sure if that is a good idea performance-wise.

The code that I added below could have the possibility of making
intra_count > intra_node_handoff_threshold. I agree with your assessment
of the current code. This conditional check is fine if no further change
is made.


>>                         2 : cna_scan_main_queue(node, node);
>>  
>>         return 0;
>> @@ -283,9 +283,6 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock
>> *node,
>>  
>>         u32 scan = cn->pre_scan_result;
>>  
>> -       if (scan == 1)
>> -               goto pass_lock;
>> -
> The thing is that we want to avoid as much of the shuffling-related overhead
> as we can when the spinlock is only lightly contended. That's why we have this
> early exit here that avoids the rest of the logic of triaging through possible
> 'scan' values.
That is a valid point. Maybe you can document that fact you are
optimizing for performance instead of better correctness.
>>         /*
>>          * check if a successor from the same numa node has not been
>> found in
>>          * pre-scan, and if so, try to find it in post-scan starting
>> from the
>> @@ -294,7 +291,13 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock *node,
>>         if (scan > 2)
>>                 scan = cna_scan_main_queue(node, decode_tail(scan));
>>  
>> -       if (!scan) { /* if found a successor from the same numa node
>> */
>> +       if (scan <= 1) { /* if found a successor from the same numa
>> node */
>> +               /* inc @intra_count if the secondary queue is not
>> empty */
>> +               ((struct cna_node *)next_holder)->intra_count =
>> +                       cn->intra_count + (node->locked > 1);
>> +               if ((scan == 1)
>> +                       goto pass_lock;
>> +
> Hmm, I am not sure this makes the code any better/more readable,
> while this does add the overhead of going through 3 branches before
> jumping to 'pass_lock'.
>
This is just a suggestion for improving the correctness of the code. I
am fine if you opt for better performance.

Cheers,
Longman

Re: [PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Waiman Long]

On 12/10/19 1:56 PM, Alex Kogan wrote:
> ----- longman@redhat.com wrote:
>
>> On 11/25/19 4:07 PM, Alex Kogan wrote:
>>> @@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct
>> qspinlock *lock,
>>>  	struct cna_node *cn = (struct cna_node *)node;
>>>  
>>>  	/*
>>> -	 * setting @pre_scan_result to 1 indicates that no post-scan
>>> +	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
>>>  	 * should be made in cna_pass_lock()
>>>  	 */
>>>  	cn->pre_scan_result =
>>> -		cn->intra_count == intra_node_handoff_threshold ?
>>> -			1 : cna_scan_main_queue(node, node);
>>> +		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
>>> +			1 : cn->intra_count == intra_node_handoff_threshold ?
>>> +			2 : cna_scan_main_queue(node, node);
>>>  
>>>  	return 0;
>>>  }
>>> @@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock *node,
>>>  
>>>  	u32 scan = cn->pre_scan_result;
>>>  
>>> +	if (scan == 1)
>>> +		goto pass_lock;
>>> +
>>>  	/*
>>>  	 * check if a successor from the same numa node has not been found
>> in
>>>  	 * pre-scan, and if so, try to find it in post-scan starting from
>> the
>>>  	 * node where pre-scan stopped (stored in @pre_scan_result)
>>>  	 */
>>> -	if (scan > 1)
>>> +	if (scan > 2)
>>>  		scan = cna_scan_main_queue(node, decode_tail(scan));
>>>  
>>>  	if (!scan) { /* if found a successor from the same numa node */
>>> @@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock *node,
>>>  		tail_2nd->next = next;
>>>  	}
>>>  
>>> +pass_lock:
>>>  	arch_mcs_pass_lock(&next_holder->locked, val);
>>>  }
>> I think you might have mishandled the proper accounting of
>> intra_count.
>> How about something like:
>>
>> diff --git a/kernel/locking/qspinlock_cna.h
>> b/kernel/locking/qspinlock_cna.h
>> index f1eef6bece7b..03f8fdec2b80 100644
>> --- a/kernel/locking/qspinlock_cna.h
>> +++ b/kernel/locking/qspinlock_cna.h
>> @@ -268,7 +268,7 @@ __always_inline u32 cna_pre_scan(struct qspinlock
>> *lock,
>>          */
>>         cn->pre_scan_result =
>>                 (node->locked <= 1 &&
>> probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
>> -                       1 : cn->intra_count ==
>> intra_node_handoff_threshold ?
>> +                       1 : cn->intra_count >=
>> intra_node_handoff_threshold ?
> We reset ‘intra_count' in cna_init_node(), which is called before we enter 
> the slow path, and set it at most once when we pass the internal (CNA) lock
> by taking the owner’s value + 1. Only after we get the internal lock, we
> call this cna_pre_scan() function, where we check the threshold. 
> IOW, having 'intra_count > intra_node_handoff_threshold' would mean a bug, 
> and having “>=“ would mask it. 
> Perhaps I can add WARN_ON(cn->intra_count > intra_node_handoff_threshold)
> here instead, although I'm not sure if that is a good idea performance-wise.

The code that I added below could have the possibility of making
intra_count > intra_node_handoff_threshold. I agree with your assessment
of the current code. This conditional check is fine if no further change
is made.


>>                         2 : cna_scan_main_queue(node, node);
>>  
>>         return 0;
>> @@ -283,9 +283,6 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock
>> *node,
>>  
>>         u32 scan = cn->pre_scan_result;
>>  
>> -       if (scan == 1)
>> -               goto pass_lock;
>> -
> The thing is that we want to avoid as much of the shuffling-related overhead
> as we can when the spinlock is only lightly contended. That's why we have this
> early exit here that avoids the rest of the logic of triaging through possible
> 'scan' values.
That is a valid point. Maybe you can document that fact you are
optimizing for performance instead of better correctness.
>>         /*
>>          * check if a successor from the same numa node has not been
>> found in
>>          * pre-scan, and if so, try to find it in post-scan starting
>> from the
>> @@ -294,7 +291,13 @@ static inline void cna_pass_lock(struct
>> mcs_spinlock *node,
>>         if (scan > 2)
>>                 scan = cna_scan_main_queue(node, decode_tail(scan));
>>  
>> -       if (!scan) { /* if found a successor from the same numa node
>> */
>> +       if (scan <= 1) { /* if found a successor from the same numa
>> node */
>> +               /* inc @intra_count if the secondary queue is not
>> empty */
>> +               ((struct cna_node *)next_holder)->intra_count =
>> +                       cn->intra_count + (node->locked > 1);
>> +               if ((scan == 1)
>> +                       goto pass_lock;
>> +
> Hmm, I am not sure this makes the code any better/more readable,
> while this does add the overhead of going through 3 branches before
> jumping to 'pass_lock'.
>
This is just a suggestion for improving the correctness of the code. I
am fine if you opt for better performance.

Cheers,
Longman

[PATCH v7 0/5] Add NUMA-awareness to qspinlock

[Alex Kogan]

Minor change from v6:
---------------------

- fixed a 32-bit build failure by adding dependency on 64BIT in Kconfig.
Reported-by: kbuild test robot <lkp@intel.com>


Summary
-------

Lock throughput can be increased by handing a lock to a waiter on the
same NUMA node as the lock holder, provided care is taken to avoid
starvation of waiters on other NUMA nodes. This patch introduces CNA
(compact NUMA-aware lock) as the slow path for qspinlock. It is
enabled through a configuration option (NUMA_AWARE_SPINLOCKS).

CNA is a NUMA-aware version of the MCS lock. Spinning threads are
organized in two queues, a main queue for threads running on the same
node as the current lock holder, and a secondary queue for threads
running on other nodes. Threads store the ID of the node on which
they are running in their queue nodes. After acquiring the MCS lock and
before acquiring the spinlock, the lock holder scans the main queue
looking for a thread running on the same node (pre-scan). If found (call
it thread T), all threads in the main queue between the current lock
holder and T are moved to the end of the secondary queue.  If such T
is not found, we make another scan of the main queue after acquiring 
the spinlock when unlocking the MCS lock (post-scan), starting at the
node where pre-scan stopped. If both scans fail to find such T, the
MCS lock is passed to the first thread in the secondary queue. If the
secondary queue is empty, the MCS lock is passed to the next thread in the
main queue. To avoid starvation of threads in the secondary queue, those
threads are moved back to the head of the main queue after a certain
number of intra-node lock hand-offs.

More details are available at https://arxiv.org/abs/1810.05600.

The series applies on top of v5.4.0, commit eae56099de85.
Performance numbers are available in previous revisions
of the series.

Further comments are welcome and appreciated.

Alex Kogan (5):
  locking/qspinlock: Rename mcs lock/unlock macros and make them more
    generic
  locking/qspinlock: Refactor the qspinlock slow path
  locking/qspinlock: Introduce CNA into the slow path of qspinlock
  locking/qspinlock: Introduce starvation avoidance into CNA
  locking/qspinlock: Introduce the shuffle reduction optimization into
    CNA

 .../admin-guide/kernel-parameters.txt         |  18 +
 arch/arm/include/asm/mcs_spinlock.h           |   6 +-
 arch/x86/Kconfig                              |  20 ++
 arch/x86/include/asm/qspinlock.h              |   4 +
 arch/x86/kernel/alternative.c                 |  70 ++++
 include/asm-generic/mcs_spinlock.h            |   4 +-
 kernel/locking/mcs_spinlock.h                 |  20 +-
 kernel/locking/qspinlock.c                    |  77 ++++-
 kernel/locking/qspinlock_cna.h                | 319 ++++++++++++++++++
 kernel/locking/qspinlock_paravirt.h           |   2 +-
 10 files changed, 517 insertions(+), 23 deletions(-)
 create mode 100644 kernel/locking/qspinlock_cna.h

-- 
2.21.0 (Apple Git-122.2)

[PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Alex Kogan]

This optimization reduces the probability threads will be shuffled between
the main and secondary queues when the secondary queue is empty.
It is helpful when the lock is only lightly contended.

Signed-off-by: Alex Kogan <alex.kogan@oracle.com>
Reviewed-by: Steve Sistare <steven.sistare@oracle.com>
---
 kernel/locking/qspinlock_cna.h | 50 ++++++++++++++++++++++++++++------
 1 file changed, 42 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/qspinlock_cna.h b/kernel/locking/qspinlock_cna.h
index dcb2bcfd2d94..f1eef6bece7b 100644
--- a/kernel/locking/qspinlock_cna.h
+++ b/kernel/locking/qspinlock_cna.h
@@ -4,6 +4,7 @@
 #endif
 
 #include <linux/topology.h>
+#include <linux/random.h>
 
 /*
  * Implement a NUMA-aware version of MCS (aka CNA, or compact NUMA-aware lock).
@@ -50,7 +51,7 @@ struct cna_node {
 	struct mcs_spinlock	mcs;
 	int			numa_node;
 	u32			encoded_tail;
-	u32			pre_scan_result; /* 0, 1 or encoded tail */
+	u32			pre_scan_result; /* 0, 1, 2 or encoded tail */
 	u32			intra_count;
 };
 
@@ -60,6 +61,34 @@ struct cna_node {
  */
 extern int intra_node_handoff_threshold;
 
+/*
+ * Controls the probability for enabling the scan of the main queue when
+ * the secondary queue is empty. The chosen value reduces the amount of
+ * unnecessary shuffling of threads between the two waiting queues when
+ * the contention is low, while responding fast enough and enabling
+ * the shuffling when the contention is high.
+ */
+#define SHUFFLE_REDUCTION_PROB_ARG  (7)
+
+/* Per-CPU pseudo-random number seed */
+static DEFINE_PER_CPU(u32, seed);
+
+/*
+ * Return false with probability 1 / 2^@num_bits.
+ * Intuitively, the larger @num_bits the less likely false is to be returned.
+ * @num_bits must be a number between 0 and 31.
+ */
+static bool probably(unsigned int num_bits)
+{
+	u32 s;
+
+	s = this_cpu_read(seed);
+	s = next_pseudo_random32(s);
+	this_cpu_write(seed, s);
+
+	return s & ((1 << num_bits) - 1);
+}
+
 static void __init cna_init_nodes_per_cpu(unsigned int cpu)
 {
 	struct mcs_spinlock *base = per_cpu_ptr(&qnodes[0].mcs, cpu);
@@ -72,11 +101,11 @@ static void __init cna_init_nodes_per_cpu(unsigned int cpu)
 		cn->numa_node = numa_node;
 		cn->encoded_tail = encode_tail(cpu, i);
 		/*
-		 * @encoded_tail has to be larger than 1, so we do not confuse
+		 * @encoded_tail has to be larger than 2, so we do not confuse
 		 * it with other valid values for @locked or @pre_scan_result
-		 * (0 or 1)
+		 * (0, 1 or 2)
 		 */
-		WARN_ON(cn->encoded_tail <= 1);
+		WARN_ON(cn->encoded_tail <= 2);
 	}
 }
 
@@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct qspinlock *lock,
 	struct cna_node *cn = (struct cna_node *)node;
 
 	/*
-	 * setting @pre_scan_result to 1 indicates that no post-scan
+	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
 	 * should be made in cna_pass_lock()
 	 */
 	cn->pre_scan_result =
-		cn->intra_count == intra_node_handoff_threshold ?
-			1 : cna_scan_main_queue(node, node);
+		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
+			1 : cn->intra_count == intra_node_handoff_threshold ?
+			2 : cna_scan_main_queue(node, node);
 
 	return 0;
 }
@@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
 
 	u32 scan = cn->pre_scan_result;
 
+	if (scan == 1)
+		goto pass_lock;
+
 	/*
 	 * check if a successor from the same numa node has not been found in
 	 * pre-scan, and if so, try to find it in post-scan starting from the
 	 * node where pre-scan stopped (stored in @pre_scan_result)
 	 */
-	if (scan > 1)
+	if (scan > 2)
 		scan = cna_scan_main_queue(node, decode_tail(scan));
 
 	if (!scan) { /* if found a successor from the same numa node */
@@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
 		tail_2nd->next = next;
 	}
 
+pass_lock:
 	arch_mcs_pass_lock(&next_holder->locked, val);
 }
-- 
2.21.0 (Apple Git-122.2)

[PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Alex Kogan]

This optimization reduces the probability threads will be shuffled between
the main and secondary queues when the secondary queue is empty.
It is helpful when the lock is only lightly contended.

Signed-off-by: Alex Kogan <alex.kogan@oracle.com>
Reviewed-by: Steve Sistare <steven.sistare@oracle.com>
---
 kernel/locking/qspinlock_cna.h | 50 ++++++++++++++++++++++++++++------
 1 file changed, 42 insertions(+), 8 deletions(-)

diff --git a/kernel/locking/qspinlock_cna.h b/kernel/locking/qspinlock_cna.h
index dcb2bcfd2d94..f1eef6bece7b 100644
--- a/kernel/locking/qspinlock_cna.h
+++ b/kernel/locking/qspinlock_cna.h
@@ -4,6 +4,7 @@
 #endif
 
 #include <linux/topology.h>
+#include <linux/random.h>
 
 /*
  * Implement a NUMA-aware version of MCS (aka CNA, or compact NUMA-aware lock).
@@ -50,7 +51,7 @@ struct cna_node {
 	struct mcs_spinlock	mcs;
 	int			numa_node;
 	u32			encoded_tail;
-	u32			pre_scan_result; /* 0, 1 or encoded tail */
+	u32			pre_scan_result; /* 0, 1, 2 or encoded tail */
 	u32			intra_count;
 };
 
@@ -60,6 +61,34 @@ struct cna_node {
  */
 extern int intra_node_handoff_threshold;
 
+/*
+ * Controls the probability for enabling the scan of the main queue when
+ * the secondary queue is empty. The chosen value reduces the amount of
+ * unnecessary shuffling of threads between the two waiting queues when
+ * the contention is low, while responding fast enough and enabling
+ * the shuffling when the contention is high.
+ */
+#define SHUFFLE_REDUCTION_PROB_ARG  (7)
+
+/* Per-CPU pseudo-random number seed */
+static DEFINE_PER_CPU(u32, seed);
+
+/*
+ * Return false with probability 1 / 2^@num_bits.
+ * Intuitively, the larger @num_bits the less likely false is to be returned.
+ * @num_bits must be a number between 0 and 31.
+ */
+static bool probably(unsigned int num_bits)
+{
+	u32 s;
+
+	s = this_cpu_read(seed);
+	s = next_pseudo_random32(s);
+	this_cpu_write(seed, s);
+
+	return s & ((1 << num_bits) - 1);
+}
+
 static void __init cna_init_nodes_per_cpu(unsigned int cpu)
 {
 	struct mcs_spinlock *base = per_cpu_ptr(&qnodes[0].mcs, cpu);
@@ -72,11 +101,11 @@ static void __init cna_init_nodes_per_cpu(unsigned int cpu)
 		cn->numa_node = numa_node;
 		cn->encoded_tail = encode_tail(cpu, i);
 		/*
-		 * @encoded_tail has to be larger than 1, so we do not confuse
+		 * @encoded_tail has to be larger than 2, so we do not confuse
 		 * it with other valid values for @locked or @pre_scan_result
-		 * (0 or 1)
+		 * (0, 1 or 2)
 		 */
-		WARN_ON(cn->encoded_tail <= 1);
+		WARN_ON(cn->encoded_tail <= 2);
 	}
 }
 
@@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct qspinlock *lock,
 	struct cna_node *cn = (struct cna_node *)node;
 
 	/*
-	 * setting @pre_scan_result to 1 indicates that no post-scan
+	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
 	 * should be made in cna_pass_lock()
 	 */
 	cn->pre_scan_result =
-		cn->intra_count == intra_node_handoff_threshold ?
-			1 : cna_scan_main_queue(node, node);
+		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
+			1 : cn->intra_count == intra_node_handoff_threshold ?
+			2 : cna_scan_main_queue(node, node);
 
 	return 0;
 }
@@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
 
 	u32 scan = cn->pre_scan_result;
 
+	if (scan == 1)
+		goto pass_lock;
+
 	/*
 	 * check if a successor from the same numa node has not been found in
 	 * pre-scan, and if so, try to find it in post-scan starting from the
 	 * node where pre-scan stopped (stored in @pre_scan_result)
 	 */
-	if (scan > 1)
+	if (scan > 2)
 		scan = cna_scan_main_queue(node, decode_tail(scan));
 
 	if (!scan) { /* if found a successor from the same numa node */
@@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
 		tail_2nd->next = next;
 	}
 
+pass_lock:
 	arch_mcs_pass_lock(&next_holder->locked, val);
 }
-- 
2.21.0 (Apple Git-122.2)

Re: [PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Waiman Long]

On 11/25/19 4:07 PM, Alex Kogan wrote:
> @@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct qspinlock *lock,
>  	struct cna_node *cn = (struct cna_node *)node;
>  
>  	/*
> -	 * setting @pre_scan_result to 1 indicates that no post-scan
> +	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
>  	 * should be made in cna_pass_lock()
>  	 */
>  	cn->pre_scan_result =
> -		cn->intra_count == intra_node_handoff_threshold ?
> -			1 : cna_scan_main_queue(node, node);
> +		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
> +			1 : cn->intra_count == intra_node_handoff_threshold ?
> +			2 : cna_scan_main_queue(node, node);
>  
>  	return 0;
>  }
> @@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
>  
>  	u32 scan = cn->pre_scan_result;
>  
> +	if (scan == 1)
> +		goto pass_lock;
> +
>  	/*
>  	 * check if a successor from the same numa node has not been found in
>  	 * pre-scan, and if so, try to find it in post-scan starting from the
>  	 * node where pre-scan stopped (stored in @pre_scan_result)
>  	 */
> -	if (scan > 1)
> +	if (scan > 2)
>  		scan = cna_scan_main_queue(node, decode_tail(scan));
>  
>  	if (!scan) { /* if found a successor from the same numa node */
> @@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
>  		tail_2nd->next = next;
>  	}
>  
> +pass_lock:
>  	arch_mcs_pass_lock(&next_holder->locked, val);
>  }

I think you might have mishandled the proper accounting of intra_count.
How about something like:

diff --git a/kernel/locking/qspinlock_cna.h b/kernel/locking/qspinlock_cna.h
index f1eef6bece7b..03f8fdec2b80 100644
--- a/kernel/locking/qspinlock_cna.h
+++ b/kernel/locking/qspinlock_cna.h
@@ -268,7 +268,7 @@ __always_inline u32 cna_pre_scan(struct qspinlock *lock,
         */
        cn->pre_scan_result =
                (node->locked <= 1 &&
probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
-                       1 : cn->intra_count ==
intra_node_handoff_threshold ?
+                       1 : cn->intra_count >=
intra_node_handoff_threshold ?
                        2 : cna_scan_main_queue(node, node);
 
        return 0;
@@ -283,9 +283,6 @@ static inline void cna_pass_lock(struct mcs_spinlock
*node,
 
        u32 scan = cn->pre_scan_result;
 
-       if (scan == 1)
-               goto pass_lock;
-
        /*
         * check if a successor from the same numa node has not been
found in
         * pre-scan, and if so, try to find it in post-scan starting
from the
@@ -294,7 +291,13 @@ static inline void cna_pass_lock(struct
mcs_spinlock *node,
        if (scan > 2)
                scan = cna_scan_main_queue(node, decode_tail(scan));
 
-       if (!scan) { /* if found a successor from the same numa node */
+       if (scan <= 1) { /* if found a successor from the same numa node */
+               /* inc @intra_count if the secondary queue is not empty */
+               ((struct cna_node *)next_holder)->intra_count =
+                       cn->intra_count + (node->locked > 1);
+               if ((scan == 1)
+                       goto pass_lock;
+
                next_holder = node->next;
                /*
                 * we unlock successor by passing a non-zero value,
@@ -302,9 +305,6 @@ static inline void cna_pass_lock(struct mcs_spinlock
*node,
                 * if we acquired the MCS lock when its queue was empty
                 */
                val = node->locked ? node->locked : 1;
-               /* inc @intra_count if the secondary queue is not empty */
-               ((struct cna_node *)next_holder)->intra_count =
-                       cn->intra_count + (node->locked > 1);
        } else if (node->locked > 1) {    /* if secondary queue is not
empty */
                /* next holder will be the first node in the secondary
queue */
                tail_2nd = decode_tail(node->locked);

The meaning of scan value:

0 - pass to next cna node, which is in the same numa node. Additional
cna node may or may not be added to the secondary queue

1 - pass to next cna node, which may not be in the same numa node. No
change to secondary queue

2 - exceed intra node handoff threshold, unconditionally merge back the
secondary queue cna nodes, if available

>2 no cna node of the same numa node found, unconditionally merge back
the secondary queue cna nodes, if available

The code will be easier to read if symbolic names instead of just numbers.

Cheers,
Longman

Re: [PATCH v7 5/5] locking/qspinlock: Introduce the shuffle reduction optimization into CNA

[Waiman Long]

On 11/25/19 4:07 PM, Alex Kogan wrote:
> @@ -234,12 +263,13 @@ __always_inline u32 cna_pre_scan(struct qspinlock *lock,
>  	struct cna_node *cn = (struct cna_node *)node;
>  
>  	/*
> -	 * setting @pre_scan_result to 1 indicates that no post-scan
> +	 * setting @pre_scan_result to 1 or 2 indicates that no post-scan
>  	 * should be made in cna_pass_lock()
>  	 */
>  	cn->pre_scan_result =
> -		cn->intra_count == intra_node_handoff_threshold ?
> -			1 : cna_scan_main_queue(node, node);
> +		(node->locked <= 1 && probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
> +			1 : cn->intra_count == intra_node_handoff_threshold ?
> +			2 : cna_scan_main_queue(node, node);
>  
>  	return 0;
>  }
> @@ -253,12 +283,15 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
>  
>  	u32 scan = cn->pre_scan_result;
>  
> +	if (scan == 1)
> +		goto pass_lock;
> +
>  	/*
>  	 * check if a successor from the same numa node has not been found in
>  	 * pre-scan, and if so, try to find it in post-scan starting from the
>  	 * node where pre-scan stopped (stored in @pre_scan_result)
>  	 */
> -	if (scan > 1)
> +	if (scan > 2)
>  		scan = cna_scan_main_queue(node, decode_tail(scan));
>  
>  	if (!scan) { /* if found a successor from the same numa node */
> @@ -281,5 +314,6 @@ static inline void cna_pass_lock(struct mcs_spinlock *node,
>  		tail_2nd->next = next;
>  	}
>  
> +pass_lock:
>  	arch_mcs_pass_lock(&next_holder->locked, val);
>  }

I think you might have mishandled the proper accounting of intra_count.
How about something like:

diff --git a/kernel/locking/qspinlock_cna.h b/kernel/locking/qspinlock_cna.h
index f1eef6bece7b..03f8fdec2b80 100644
--- a/kernel/locking/qspinlock_cna.h
+++ b/kernel/locking/qspinlock_cna.h
@@ -268,7 +268,7 @@ __always_inline u32 cna_pre_scan(struct qspinlock *lock,
         */
        cn->pre_scan_result =
                (node->locked <= 1 &&
probably(SHUFFLE_REDUCTION_PROB_ARG)) ?
-                       1 : cn->intra_count ==
intra_node_handoff_threshold ?
+                       1 : cn->intra_count >=
intra_node_handoff_threshold ?
                        2 : cna_scan_main_queue(node, node);
 
        return 0;
@@ -283,9 +283,6 @@ static inline void cna_pass_lock(struct mcs_spinlock
*node,
 
        u32 scan = cn->pre_scan_result;
 
-       if (scan == 1)
-               goto pass_lock;
-
        /*
         * check if a successor from the same numa node has not been
found in
         * pre-scan, and if so, try to find it in post-scan starting
from the
@@ -294,7 +291,13 @@ static inline void cna_pass_lock(struct
mcs_spinlock *node,
        if (scan > 2)
                scan = cna_scan_main_queue(node, decode_tail(scan));
 
-       if (!scan) { /* if found a successor from the same numa node */
+       if (scan <= 1) { /* if found a successor from the same numa node */
+               /* inc @intra_count if the secondary queue is not empty */
+               ((struct cna_node *)next_holder)->intra_count =
+                       cn->intra_count + (node->locked > 1);
+               if ((scan == 1)
+                       goto pass_lock;
+
                next_holder = node->next;
                /*
                 * we unlock successor by passing a non-zero value,
@@ -302,9 +305,6 @@ static inline void cna_pass_lock(struct mcs_spinlock
*node,
                 * if we acquired the MCS lock when its queue was empty
                 */
                val = node->locked ? node->locked : 1;
-               /* inc @intra_count if the secondary queue is not empty */
-               ((struct cna_node *)next_holder)->intra_count =
-                       cn->intra_count + (node->locked > 1);
        } else if (node->locked > 1) {    /* if secondary queue is not
empty */
                /* next holder will be the first node in the secondary
queue */
                tail_2nd = decode_tail(node->locked);

The meaning of scan value:

0 - pass to next cna node, which is in the same numa node. Additional
cna node may or may not be added to the secondary queue

1 - pass to next cna node, which may not be in the same numa node. No
change to secondary queue

2 - exceed intra node handoff threshold, unconditionally merge back the
secondary queue cna nodes, if available

>2 no cna node of the same numa node found, unconditionally merge back
the secondary queue cna nodes, if available

The code will be easier to read if symbolic names instead of just numbers.

Cheers,
Longman