netdev - Re: [PATCH 2/2] rhashtable: Add arbitrary rehash function

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]

Date:	Wed, 11 Mar 2015 09:01:57 +1100
From:	Herbert Xu <herbert@...dor.apana.org.au>
To:	Thomas Graf <tgraf@...g.ch>
Cc:	David Miller <davem@...emloft.net>, netdev@...r.kernel.org,
	josh@...htriplett.org,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: Re: [PATCH 2/2] rhashtable: Add arbitrary rehash function

On Tue, Mar 10, 2015 at 06:17:20PM +0000, Thomas Graf wrote:
> 
> > +static void rhashtable_rehash(struct rhashtable *ht,
> > +			      struct bucket_table *new_tbl)
> >  {
> > -	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
> > +	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
> > +	unsigned old_hash;
> > +
> > +	get_random_bytes(&new_tbl->hash_rnd, sizeof(new_tbl->hash_rnd));
> > +
> > +	/* Make insertions go into the new, empty table right away. Deletions
> > +	 * and lookups will be attempted in both tables until we synchronize.
> > +	 * The synchronize_rcu() guarantees for the new table to be picked up
> > +	 * so no new additions go into the old table while we relink.
> > +	 */
> > +	rcu_assign_pointer(ht->future_tbl, new_tbl);
> 
> I think you need an rcu_synchronize() here. rhashtable_remove() must
> be guaranteed to either see tbl != old_tbl and thus consider both
> tables or the rehashing must be guaranteed to not start for an already
> started removal. 

You are right that there is a bug with respect to removal here.
But we don't need a complete synchronize.  I just need to move
the future_tbl read in rhashtable_remove so that it occurs after
__rhashtable_remove.

Because __rhashtable_remove would have already taken a spinlock
in the old table, this means that if future_tbl is not yet visible,
then the rehashing thread has yet to process that bucket (since it
takes every single bucket lock while processing) so the entry must
be visible there (if it exists).

BTW there is also a similar bug in rhashtable_lookup_compare_insert
which I will fix in the next update.

> > -static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
> > -				struct bucket_table *tbl,
> > -				const struct bucket_table *old_tbl, u32 hash)
> > +bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
> > +			 bool (*compare)(void *, void *), void *arg)
> 
> Why make this non-static? We already have rhashtable_lookup_compare_insert()
> exported.

Good catch.  Cut-n-paste error.

Thanks,
-- 
Email: Herbert Xu <herbert@...dor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html