linux-kernel - Re: [PATCH 2/5] rhashtable: don't hold lock on first table throughout insertion.

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 for Android: free password hash cracker in your pocket

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

Message-Id: <20180720144152.GW12945@linux.vnet.ibm.com>
Date:   Fri, 20 Jul 2018 07:41:52 -0700
From:   "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:     Herbert Xu <herbert@...dor.apana.org.au>
Cc:     NeilBrown <neilb@...e.com>, Thomas Graf <tgraf@...g.ch>,
        netdev@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 2/5] rhashtable: don't hold lock on first table
 throughout insertion.

On Fri, Jul 20, 2018 at 03:54:09PM +0800, Herbert Xu wrote:
> On Fri, Jul 06, 2018 at 05:22:30PM +1000, NeilBrown wrote:
> > rhashtable_try_insert() currently hold a lock on the bucket in
> > the first table, while also locking buckets in subsequent tables.
> > This is unnecessary and looks like a hold-over from some earlier
> > version of the implementation.
> > 
> > As insert and remove always lock a bucket in each table in turn, and
> > as insert only inserts in the final table, there cannot be any races
> > that are not covered by simply locking a bucket in each table in turn.
> > 
> > When an insert call reaches that last table it can be sure that there
> > is no match entry in any other table as it has searched them all, and
> > insertion never happens anywhere but in the last table.  The fact that
> > code tests for the existence of future_tbl while holding a lock on
> > the relevant bucket ensures that two threads inserting the same key
> > will make compatible decisions about which is the "last" table.
> > 
> > This simplifies the code and allows the ->rehash field to be
> > discarded.
> > 
> > We still need a way to ensure that a dead bucket_table is never
> > re-linked by rhashtable_walk_stop().  This can be achieved by
> > calling call_rcu() inside the locked region, and checking
> > ->rcu.func in rhashtable_walk_stop().  If it is not NULL, then
> > the bucket table is empty and dead.
> > 
> > Signed-off-by: NeilBrown <neilb@...e.com>
> 
> ...
> 
> > @@ -339,13 +338,16 @@ static int rhashtable_rehash_table(struct rhashtable *ht)
> >  	spin_lock(&ht->lock);
> >  	list_for_each_entry(walker, &old_tbl->walkers, list)
> >  		walker->tbl = NULL;
> > -	spin_unlock(&ht->lock);
> >  
> >  	/* Wait for readers. All new readers will see the new
> >  	 * table, and thus no references to the old table will
> >  	 * remain.
> > +	 * We do this inside the locked region so that
> > +	 * rhashtable_walk_stop() can check ->rcu.func and know
> > +	 * not to re-link the table.
> >  	 */
> >  	call_rcu(&old_tbl->rcu, bucket_table_free_rcu);
> > +	spin_unlock(&ht->lock);
> >  
> >  	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
> >  }
> 
> ...
> 
> > @@ -964,7 +942,7 @@ void rhashtable_walk_stop(struct rhashtable_iter *iter)
> >  	ht = iter->ht;
> >  
> >  	spin_lock(&ht->lock);
> > -	if (tbl->rehash < tbl->size)
> > +	if (tbl->rcu.func == NULL)
> >  		list_add(&iter->walker.list, &tbl->walkers);
> >  	else
> >  		iter->walker.tbl = NULL;
> 
> This appears to be relying on implementation details within RCU.
> Paul, are you OK with rhashtable doing this trick?

The notion of accessing objects that are already on RCU's callback lists
makes me -very- nervous because this sort of thing is not easy to
get right.  After all, if you are accessing something that is already
on one of RCU's callback lists, RCU might invoke the callback it at any
time (thus freeing it in this case), and because it is already on RCU's
callback lists, rcu_read_lock() is going to be of no help whatsoever.

In addition, RCU does no ordering on its store to ->func, but the ht->lock
compensates in this case.  But suppose rhashtable_walk_stop() sees the
pointer as non-NULL.  What prevents RCU from freeing the bucket table out
from under rhashtable_walk_stop()?  In v4.17, bucket_table_free_rcu()
just does some calls to various deallocators, which does not provide
the necessary synchronization.

Does the rhashtable_iter structure use some trick to make this safe?
Or has synchronization been added to bucket_table_free_rcu()?  Or is
some other trick in use?

							Thanx, Paul