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
| ||
|
Message-ID: <54D81F22.7070900@windriver.com> Date: Mon, 9 Feb 2015 10:44:50 +0800 From: Ying Xue <ying.xue@...driver.com> To: Thomas Graf <tgraf@...g.ch> CC: <davem@...emloft.net>, <netdev@...r.kernel.org>, <herbert@...dor.apana.org.au> Subject: Re: [PATCH net-next] rhashtable: Fix remove logic to avoid cross references between buckets On 02/07/2015 12:08 AM, Thomas Graf wrote: > The remove logic properly searched the remaining chain for a matching > entry with an identical hash but it did this while searching from both > the old and new table. Instead in order to not leave stale references > behind we need to: > > 1. When growing and searching from the new table: > Search remaining chain for entry with same hash to avoid having > the new table directly point to a entry with a different hash. > > 2. When shrinking and searching from the old table: > Check if the element after the removed would create a cross > reference and avoid it if so. > > These bugs were present from the beginning in nft_hash. > > Also, both insert functions calculated the hash based on the mask of > the new table. This worked while growing. Wwhile shrinking, the mask > of the inew table is smaller than the mask of the old table. This lead > to a bit not being taken into account when selecting the bucket lock > and thus caused the wrong bucket to be locked eventually. > Good Job! My previously reported issue has been gone, thanks for your hard work! Regards, Ying > Fixes: 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table") > Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking") > Reported-by: Ying Xue <ying.xue@...driver.com> > Signed-off-by: Thomas Graf <tgraf@...g.ch> > --- > lib/rhashtable.c | 28 +++++++++++++++++----------- > 1 file changed, 17 insertions(+), 11 deletions(-) > > diff --git a/lib/rhashtable.c b/lib/rhashtable.c > index 5919d63..e96fc00 100644 > --- a/lib/rhashtable.c > +++ b/lib/rhashtable.c > @@ -552,8 +552,10 @@ static void rhashtable_wakeup_worker(struct rhashtable *ht) > static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj, > struct bucket_table *tbl, u32 hash) > { > - struct rhash_head *head = rht_dereference_bucket(tbl->buckets[hash], > - tbl, hash); > + struct rhash_head *head; > + > + hash = rht_bucket_index(tbl, hash); > + head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash); > > ASSERT_BUCKET_LOCK(ht, tbl, hash); > > @@ -593,7 +595,7 @@ void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj) > > tbl = rht_dereference_rcu(ht->future_tbl, ht); > old_tbl = rht_dereference_rcu(ht->tbl, ht); > - hash = head_hashfn(ht, tbl, obj); > + hash = obj_raw_hashfn(ht, rht_obj(ht, obj)); > > lock_buckets(tbl, old_tbl, hash); > __rhashtable_insert(ht, obj, tbl, hash); > @@ -627,8 +629,8 @@ bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj) > bool ret = false; > > rcu_read_lock(); > - tbl = old_tbl = rht_dereference_rcu(ht->tbl, ht); > - new_tbl = rht_dereference_rcu(ht->future_tbl, ht); > + old_tbl = rht_dereference_rcu(ht->tbl, ht); > + tbl = new_tbl = rht_dereference_rcu(ht->future_tbl, ht); > new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj)); > > lock_buckets(new_tbl, old_tbl, new_hash); > @@ -643,15 +645,19 @@ restart: > > ASSERT_BUCKET_LOCK(ht, tbl, hash); > > - if (unlikely(new_tbl != tbl)) { > - rht_for_each_continue(he2, he->next, tbl, hash) { > + if (old_tbl->size > new_tbl->size && tbl == old_tbl && > + !rht_is_a_nulls(obj->next) && > + head_hashfn(ht, tbl, obj->next) != hash) { > + rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash)); > + } else if (unlikely(old_tbl->size < new_tbl->size && tbl == new_tbl)) { > + rht_for_each_continue(he2, obj->next, tbl, hash) { > if (head_hashfn(ht, tbl, he2) == hash) { > rcu_assign_pointer(*pprev, he2); > goto found; > } > } > > - INIT_RHT_NULLS_HEAD(*pprev, ht, hash); > + rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash)); > } else { > rcu_assign_pointer(*pprev, obj->next); > } > @@ -666,8 +672,8 @@ found: > * resizing. Thus traversing both is fine and the added cost is > * very rare. > */ > - if (tbl != new_tbl) { > - tbl = new_tbl; > + if (tbl != old_tbl) { > + tbl = old_tbl; > goto restart; > } > > @@ -835,7 +841,7 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht, > rcu_read_lock(); > old_tbl = rht_dereference_rcu(ht->tbl, ht); > new_tbl = rht_dereference_rcu(ht->future_tbl, ht); > - new_hash = head_hashfn(ht, new_tbl, obj); > + new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj)); > > lock_buckets(new_tbl, old_tbl, new_hash); > > -- 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
Powered by blists - more mailing lists