rhashtable: Fix reader/rehash race
Subsystems (4)
Herbert Xu
maintainerThere is a potential race condition between readers and the rehasher. In particular, the rehasher could have started a rehash while the reader finishes a scan of the old table but fails to see the new table pointer.
This patch closes this window by adding smp_wmb/smp_rmb.
lib/rhashtable.c +6 -0
@@ -271,6 +271,9 @@ static void rhashtable_rehash(struct rhashtable *ht,*/ rcu_assign_pointer (ht->future_tbl, new_tbl); +/* Ensure the new table is visible to readers. */ +smp_wmb (); +for (old_hash =0 ; old_hash < old_tbl->size; old_hash++)rhashtable_rehash_chain (ht, old_hash);
@@ -618,6 +621,9 @@ restart:return rht_obj (ht, he); } +/* Ensure we see any new tables. */ +smp_rmb (); + old_tbl = tbl; tbl =rht_dereference_rcu (ht->future_tbl, ht);if (unlikely (tbl != old_tbl))
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Thomas Graf
maintainerQuoted 8 lines · Herbert Xu
There is a potential race condition between readers and the rehasher. In particular, the rehasher could have started a rehash while the reader finishes a scan of the old table but fails to see the new table pointer.
This patch closes this window by adding smp_wmb/smp_rmb.
Signed-off-by Herbert Xu <[email protected]>
Are you sure this is sufficient? I think it is still possible for a rehash to preempt a reader in between:
tbl = rht_dereference_rcu(ht->future_tbl, ht);
if (unlikely(tbl != old_tbl))in which case old entries will be moved to the new table without the reader seeing them. I don't see how ensuring order solves this.
Thomas Graf
maintainerPATCH 1/1 rhashtable: Fix race between rehashing and readers
Rehashing can occur in parallel to readers. Readers are aware of this situation so new readers are allowed while the rehashing is in process. Existing readers may have already fetched the tbl and future_tbl and may thus assume no rehashing is in progress. The rehashing must thus wait for all existing readers to complete after publihsing the future_tbl to make sure all parallel readers see the table before we start moving entries.
---
Herbert: This is what I think is needed to fix this properly.
lib/rhashtable.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-)
lib/rhashtable.c +4 -2
@@ -275,10 +275,12 @@ static void rhashtable_rehash(struct rhashtable *ht,/* 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. +* The synchronize_rcu() guarantees that readers have either completed +* or are aware of both the new and old table before we start moving +* entries to the new table. */ rcu_assign_pointer (ht->future_tbl, new_tbl); +synchronize_rcu ();for (old_hash =0 ; old_hash < old_tbl->size; old_hash++)rhashtable_rehash_chain (ht, old_hash);
Signature · 1 line
1.9.3
Herbert Xu
maintainerRe: [PATCH net-next] rhashtable: Fix race between rehashing and readers
Quoted 8 lines · Thomas Graf
Rehashing can occur in parallel to readers. Readers are aware of this situation so new readers are allowed while the rehashing is in process. Existing readers may have already fetched the tbl and
future_tbland may thus assume no rehashing is in progress. The rehashing must thus wait for all existing readers to complete after publihsing thefuture_tblto make sure all parallel readers see the table before we start moving entries.
Quoted 4 lines
Fixes aa34a6cb0478 ("rhashtable: Add arbitrary rehash function")Signed-off-by Thomas Graf <[email protected]>---
Herbert: This is what I think is needed to fix this properly.
Nack. Please see my previous email.
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Herbert Xu
maintainerQuoted 13 lines · Thomas Graf
Quoted 8 lines · Herbert Xu
There is a potential race condition between readers and the rehasher. In particular, the rehasher could have started a rehash while the reader finishes a scan of the old table but fails to see the new table pointer.
This patch closes this window by adding smp_wmb/smp_rmb.
Signed-off-by Herbert Xu <[email protected]>Are you sure this is sufficient? I think it is still possible for a rehash to preempt a reader in between:
Quoted 6 lines
tbl = rht_dereference_rcu(ht->future_tbl, ht); if (unlikely(tbl != old_tbl))in which case old entries will be moved to the new table without the reader seeing them. I don't see how ensuring order solves this.
It doesn't matter. The wmb/smb guarauntees that if the reader cannot find the element in the old table then it must see the new table pointer. Vice versa if it cannot see the new table pointer then the element (if it existed at all) must be in the old table.
Cheers,
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Thomas Graf
maintainerQuoted 5 lines · Herbert Xu
It doesn't matter. The wmb/smb guarauntees that if the reader cannot find the element in the old table then it must see the new table pointer. Vice versa if it cannot see the new table pointer then the element (if it existed at all) must be in the old table.
I understand what you are doing now. I was still thinking of entries being on both lists in parallel.
One last question though. What about rhashtable_remove()? The spin_unlock_bh() in __rhashtable_remove() only guarantees for loads before the release to be completed. The future_tbl load could still be reordered before the traversal is complete. I think it needs an smp_rmb() as well.
Herbert Xu
maintainerQuoted 6 lines · Thomas Graf
One last question though. What about
rhashtable_remove()? Thespin_unlock_bh()in__rhashtable_remove()only guarantees for loads before the release to be completed. Thefuture_tblload could still be reordered before the traversal is complete. I think it needs ansmp_rmb()as well.
rhashtable_remove is fine because the rehasher has to take the same lock to move things over. That's what guarantees the new future_tbl to be visible if it moved the to-be-removed object over to the new table.
IOW if rhashtable_remove couldn't see the future_tbl then that can only mean that the rehasher has yet to take the lock on that bucket which implies that the object if it existed at all is still in that bucket.
Cheers,
Signature · 3 lines
Email: Herbert Xu <[email protected]> Home Page: http://gondor.apana.org.au/~herbert/ PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
Thomas Graf
maintainerQuoted 9 lines · Herbert Xu
rhashtable_removeis fine because the rehasher has to take the same lock to move things over. That's what guarantees the newfuture_tblto be visible if it moved the to-be-removed object over to the new table.IOW if
rhashtable_removecouldn't see thefuture_tblthen that can only mean that the rehasher has yet to take the lock on that bucket which implies that the object if it existed at all is still in that bucket.
Ah, it works because the future_tbl load can't be reordered in front of the acquire. Thanks for the explanation.
From: Herbert Xu <[email protected]>
Date: Thu, 12 Mar 2015 22:07:49 +1100
Quoted 8 lines
There is a potential race condition between readers and the rehasher. In particular, the rehasher could have started a rehash while the reader finishes a scan of the old table but fails to see the new table pointer.
This patch closes this window by adding smp_wmb/smp_rmb.
Signed-off-by Herbert Xu <[email protected]>
Applied.