linux-kernel - Re: [RFC PATCH 1/1] kernel/rcu/tree.c: simplify force_quiescent

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <53A07336.7030704@hp.com>
Date:	Tue, 17 Jun 2014 12:56:22 -0400
From:	Waiman Long <waiman.long@...com>
To:	Romanov Arya <romanov.arya@...il.com>
CC:	Paul McKenney <paulmck@...ux.vnet.ibm.com>,
	Pranith Kumar <bobby.prani@...il.com>,
	Josh Triplett <josh@...htriplett.org>,
	LKML <linux-kernel@...r.kernel.org>,
	Peter Zijlstra <peterz@...radead.org>,
	torvalds@...ux-foundation.org
Subject: Re: [RFC PATCH 1/1] kernel/rcu/tree.c: simplify force_quiescent_state()

On 06/17/2014 12:01 PM, Romanov Arya wrote:
> On Tue, Jun 17, 2014 at 10:54 AM, Paul E. McKenney
> <paulmck@...ux.vnet.ibm.com>  wrote:
>> On Mon, Jun 16, 2014 at 10:55:29PM -0400, Pranith Kumar wrote:
>>> This might sound really naive, but please bear with me.
>>>
>>> force_quiescent_state() used to do a lot of things in the past in addition to
>>> forcing a quiescent state. (In my reading of the mailing list I found state
>>> transitions for one).
>>>
>>> Now according to the code, what is being done is multiple callers try to go up
>>> the hierarchy of nodes to see who reaches the root node. The caller reaching the
>>> root node wins and it acquires root node lock and it gets to set rsp->gp_flags!
>>>
>>> At each level of the hierarchy we try to acquire fqslock. This is the only place
>>> which actually uses fqslock.
>>>
>>> I guess this was being done to avoid the contention on fqslock, but all we are
>>> doing here is setting one flag. This way of acquiring locks might reduce
>>> contention if every update is trying to do some independent work, but here all
>>> we are doing is setting the same flag with same value.
>> Actually, to reduce contention on rnp_root->lock.
>>
>> The trick is that the "losers" at each level of ->fqslock acquisition go
>> away.  The "winner" ends up doing the real work of setting RCU_GP_FLAG_FQS.
>>
>>> We can also remove fqslock completely if we do not need this. Also using
>>> cmpxchg() to set the value of the flag looks like a good idea to avoid taking
>>> the root node lock. Thoughts?
>> The ->fqslock funnel was needed to avoid lockups on large systems (many
>> hundreds or even thousands of CPUs).  Moving grace-period responsibilities
>> from softirq to the grace-period kthreads might have reduced contention
>> sufficienty to make the ->fqslock funnel unnecessary.  However, given
>> that I don't usually have access to such a large system, I will leave it,
>> at least for the time being.
> Sounds like a good case study for using the newly introduced MCS based
> locks(qspinlock.h).
> Waiman, Peter?

The ticket trylock and queue trylock are similar in the sense they both 
do a read to check if the lock is free first and then use cmpxchg() to 
acquire the lock. So if it is a problem to use ticket spinlock, it will 
be a problem for the queue spinlock as well. The advantage of the queue 
spinlock in a heavily contended case is that the lock waiters except the 
one in the head of the queue will not be contending the lock cacheline.
> Btw, is doing the following a bad idea? It reduces contention on
> rnp_root->lock using fqslock
> which seems to be the lock which needs to be taken while forcing a
> quiescent state:

I don't see any problem with the existing code as long as the number of 
funnel levels is small. You really need to have some performance data to 
show that your approach is better.

>
> diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> index f1ba773..f5a0e7e 100644
> --- a/kernel/rcu/tree.c
> +++ b/kernel/rcu/tree.c
> @@ -2401,34 +2401,24 @@ static void force_quiescent_state(struct rcu_state *rsp)
>       unsigned long flags;
>       bool ret;
>       struct rcu_node *rnp;
> -    struct rcu_node *rnp_old = NULL;
> -
> -    /* Funnel through hierarchy to reduce memory contention. */
> -    rnp = per_cpu_ptr(rsp->rda, raw_smp_processor_id())->mynode;
> -    for (; rnp != NULL; rnp = rnp->parent) {
> -        ret = (ACCESS_ONCE(rsp->gp_flags)&  RCU_GP_FLAG_FQS) ||
> -              !raw_spin_trylock(&rnp->fqslock);
> -        if (rnp_old != NULL)
> -            raw_spin_unlock(&rnp_old->fqslock);
> -        if (ret) {
> -            ACCESS_ONCE(rsp->n_force_qs_lh)++;
> -            return;
> -        }
> -        rnp_old = rnp;
> +    struct rcu_node *rnp_root = rcu_get_root(rsp);
> +
> +    if (!raw_spin_trylock(rnp_root->fqslock)) {
> +        ACCESS_ONCE(rsp->n_force_qs_lh)++;
> +        return;  /* Someone is already trying to force */
>       }

I think it is better to check the gp_flags first before doing a trylock.

-Longman
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/