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

[Paul E. McKenney]

On Sat, Jul 21, 2018 at 12:25:41PM +1000, NeilBrown wrote:
> On Fri, Jul 20 2018, Paul E. McKenney wrote:
> 
> > 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@xxxxxxxx>
> >> 
> >> ...
> >> 
> >> > @@ -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.
> 
> I don't follow that last line.  If some other thread has already called
> rcu_read_lock() when call_rcu() is called, then that other threads
> rcu_read_lock() will certainly help to ensure that the object doesn't
> get freed.  This code assumes that it also ensures that rcu.func will
> not be changed before the other thread calls rcu_read_unlock() and
> allows the grace period to end.
> (There is nothing explicitly about rcu lists here, just rcu.func).
> 
> >
> > 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
> 
> When rhashtable_rehash_table() has copied all objects out of a
> bucket_table, it must then disconnect any paused walkers and free the
> table. (a 'paused' walker has called rhashtable_walk_stop() and dropped
> the rcu read lock).
> It sets walk->tbl=NULL (thus implicitly removing from the list) and
> calls call_rcu(...,bucket_table_free_rcu) under a spinlock.
> 
> When rhashtable_walk_stop() is called, it needs to know whether it is
> safe to attach the walker to the bucket_table().
> It takes the same spin lock as above while still holding the
> rcu_read_lock that it took some time ago.
> If it gets the spinlock before rhashtable_rehash_table() gets it, then
> rcu.func will be NULL (tables are allocated with kzalloc) and the walker
> is attached to the table.  If it gets the spinlock after
> rhashtable_rehash_table() gets it, then rcu.func will not be NULL and
> the walker will not be attached to the table.
> 
> The only interesting question is whether RCU might ever set rcu.func to
> NULL (or change it at all) *after* call_rcu() has been called, and
> *before* the current grace period ends.
> If you don't want to guarantee that it doesn't, I can add an extra flag
> field to the table to say "this table must not be attached walkers", but
> I currently think that should be unnecessary.

One issue is that the ->func pointer can legitimately be NULL while on
RCU's callback lists.  This happens when someone invokes kfree_rcu()
with the rcu_head structure at the beginning of the enclosing structure.
I could add an offset to avoid this, or perhaps the kmalloc() folks
could be persuaded Rao Shoaib's patch moving kfree_rcu() handling to
the slab allocators, so that RCU only ever sees function pointers in
the ->func field.

Either way, this should be hidden behind an API to allow adjustments
to be made if needed.  Maybe something like is_after_call_rcu()?
This would (for example) allow debug-object checks to be used to catch
check-after-free bugs.

Would something of that sort work for you?

							Thanx, Paul