Skip to content

L
linux
Switch branch/tag
  1. 08 Feb, 2015 36 commits
  3. 06 Feb, 2015 4 commits
    • Thomas Graf's avatar
      rhashtable: Fix remove logic to avoid cross references between buckets · 020219a6
      Thomas Graf authored 
      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.

Fixes: 7e1e7763 ("lib: Resizable, Scalable, Concurrent Hash Table")
Fixes: 97defe1e ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Reported-by: default avatarYing Xue <ying.xue@windriver.com>
Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      020219a6
    • David S. Miller's avatar
      Merge branch 'rhashtable-next' · 41e8b206
      David S. Miller authored 
      Thomas Graf says:

====================
rhashtable fixes

This series fixes all remaining known issues with rhashtable that
have been reported. In particular the race condition reported by
Ying Xue.
====================
Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      41e8b206
    • Thomas Graf's avatar
      rhashtable: Avoid bucket cross reference after removal · cf52d52f
      Thomas Graf authored 
      During a resize, when two buckets in the larger table map to
a single bucket in the smaller table and the new table has already
been (partially) linked to the old table. Removal of an element
may result the bucket in the larger table to point to entries
which all hash to a different value than the bucket index. Thus
causing two buckets to point to the same sub chain after unzipping.
This is not illegal *during* the resize phase but after it has
completed.

Keep the old table around until all of the unzipping is done to
allow the removal code to only search for matching hashed entries
during this special period.
Reported-by: default avatarYing Xue <ying.xue@windriver.com>
Fixes: 97defe1e ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      cf52d52f
    • Thomas Graf's avatar
      rhashtable: Add more lock verification · 7cd10db8
      Thomas Graf authored 
      Catch hash miscalculations which result in hard to track down race
conditions.
Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      7cd10db8
GitLab Nexedi Edition | About GitLab | About Nexedi | 沪ICP备2021021310号-2 | 沪ICP备2021021310号-7