Messages in this thread | | | Date | Sun, 22 Jul 2018 14:54:46 -0700 | From | "Paul E. McKenney" <> | Subject | Re: [PATCH 2/5] rhashtable: don't hold lock on first table throughout insertion. |
| |
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@suse.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. > > 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
| |