1. 18 Oct, 2018 1 commit
  2. 25 Jul, 2018 1 commit
  3. 31 Mar, 2018 1 commit
  4. 20 Sep, 2016 1 commit
    • Herbert Xu's avatar
      rhashtable: Add rhlist interface · ca26893f
      Herbert Xu authored
      The insecure_elasticity setting is an ugly wart brought out by
      users who need to insert duplicate objects (that is, distinct
      objects with identical keys) into the same table.
      
      In fact, those users have a much bigger problem.  Once those
      duplicate objects are inserted, they don't have an interface to
      find them (unless you count the walker interface which walks
      over the entire table).
      
      Some users have resorted to doing a manual walk over the hash
      table which is of course broken because they don't handle the
      potential existence of multiple hash tables.  The result is that
      they will break sporadically when they encounter a hash table
      resize/rehash.
      
      This patch provides a way out for those users, at the expense
      of an extra pointer per object.  Essentially each object is now
      a list of objects carrying the same key.  The hash table will
      only see the lists so nothing changes as far as rhashtable is
      concerned.
      
      To use this new interface, you need to insert a struct rhlist_head
      into your objects instead of struct rhash_head.  While the hash
      table is unchanged, for type-safety you'll need to use struct
      rhltable instead of struct rhashtable.  All the existing interfaces
      have been duplicated for rhlist, including the hash table walker.
      
      One missing feature is nulls marking because AFAIK the only potential
      user of it does not need duplicate objects.  Should anyone need
      this it shouldn't be too hard to add.
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      Acked-by: default avatarThomas Graf <tgraf@suug.ch>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      ca26893f
  5. 27 Aug, 2016 1 commit
  6. 26 Aug, 2016 1 commit
    • Pablo Neira Ayuso's avatar
      rhashtable: add rhashtable_lookup_get_insert_key() · 5ca8cc5b
      Pablo Neira Ayuso authored
      This patch modifies __rhashtable_insert_fast() so it returns the
      existing object that clashes with the one that you want to insert.
      In case the object is successfully inserted, NULL is returned.
      Otherwise, you get an error via ERR_PTR().
      
      This patch adapts the existing callers of __rhashtable_insert_fast()
      so they handle this new logic, and it adds a new
      rhashtable_lookup_get_insert_key() interface to fetch this existing
      object.
      
      nf_tables needs this change to improve handling of EEXIST cases via
      honoring the NLM_F_EXCL flag and by checking if the data part of the
      mapping matches what we have.
      
      Cc: Herbert Xu <herbert@gondor.apana.org.au>
      Cc: Thomas Graf <tgraf@suug.ch>
      Signed-off-by: default avatarPablo Neira Ayuso <pablo@netfilter.org>
      Acked-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      5ca8cc5b
  7. 19 Aug, 2016 1 commit
    • Herbert Xu's avatar
      rhashtable: Remove GFP flag from rhashtable_walk_init · 246779dd
      Herbert Xu authored
      The commit 8f6fd83c ("rhashtable:
      accept GFP flags in rhashtable_walk_init") added a GFP flag argument
      to rhashtable_walk_init because some users wish to use the walker
      in an unsleepable context.
      
      In fact we don't need to allocate memory in rhashtable_walk_init
      at all.  The walker is always paired with an iterator so we could
      just stash ourselves there.
      
      This patch does that by introducing a new enter function to replace
      the existing init function.  This way we don't have to churn all
      the existing users again.
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      246779dd
  8. 15 Aug, 2016 2 commits
    • Vegard Nossum's avatar
      rhashtable: fix shift by 64 when shrinking · 12311959
      Vegard Nossum authored
      I got this:
      
          ================================================================================
          UBSAN: Undefined behaviour in ./include/linux/log2.h:63:13
          shift exponent 64 is too large for 64-bit type 'long unsigned int'
          CPU: 1 PID: 721 Comm: kworker/1:1 Not tainted 4.8.0-rc1+ #87
          Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS rel-1.9.3-0-ge2fc41e-prebuilt.qemu-project.org 04/01/2014
          Workqueue: events rht_deferred_worker
           0000000000000000 ffff88011661f8d8 ffffffff82344f50 0000000041b58ab3
           ffffffff84f98000 ffffffff82344ea4 ffff88011661f900 ffff88011661f8b0
           0000000000000001 ffff88011661f6b8 dffffc0000000000 ffffffff867f7640
          Call Trace:
           [<ffffffff82344f50>] dump_stack+0xac/0xfc
           [<ffffffff82344ea4>] ? _atomic_dec_and_lock+0xc4/0xc4
           [<ffffffff8242f5b8>] ubsan_epilogue+0xd/0x8a
           [<ffffffff82430c41>] __ubsan_handle_shift_out_of_bounds+0x255/0x29a
           [<ffffffff824309ec>] ? __ubsan_handle_out_of_bounds+0x180/0x180
           [<ffffffff84003436>] ? nl80211_req_set_reg+0x256/0x2f0
           [<ffffffff812112ba>] ? print_context_stack+0x8a/0x160
           [<ffffffff81200031>] ? amd_pmu_reset+0x341/0x380
           [<ffffffff823af808>] rht_deferred_worker+0x1618/0x1790
           [<ffffffff823af808>] ? rht_deferred_worker+0x1618/0x1790
           [<ffffffff823ae1f0>] ? rhashtable_jhash2+0x370/0x370
           [<ffffffff8134c12d>] ? process_one_work+0x6fd/0x1970
           [<ffffffff8134c1cf>] process_one_work+0x79f/0x1970
           [<ffffffff8134c12d>] ? process_one_work+0x6fd/0x1970
           [<ffffffff8134ba30>] ? try_to_grab_pending+0x4c0/0x4c0
           [<ffffffff8134d564>] ? worker_thread+0x1c4/0x1340
           [<ffffffff8134d8ff>] worker_thread+0x55f/0x1340
           [<ffffffff845e904f>] ? __schedule+0x4df/0x1d40
           [<ffffffff8134d3a0>] ? process_one_work+0x1970/0x1970
           [<ffffffff8134d3a0>] ? process_one_work+0x1970/0x1970
           [<ffffffff813642f7>] kthread+0x237/0x390
           [<ffffffff813640c0>] ? __kthread_parkme+0x280/0x280
           [<ffffffff845f8c93>] ? _raw_spin_unlock_irq+0x33/0x50
           [<ffffffff845f95df>] ret_from_fork+0x1f/0x40
           [<ffffffff813640c0>] ? __kthread_parkme+0x280/0x280
          ================================================================================
      
      roundup_pow_of_two() is undefined when called with an argument of 0, so
      let's avoid the call and just fall back to ht->p.min_size (which should
      never be smaller than HASH_MIN_SIZE).
      
      Cc: Herbert Xu <herbert@gondor.apana.org.au>
      Signed-off-by: default avatarVegard Nossum <vegard.nossum@oracle.com>
      Acked-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      12311959
    • Florian Westphal's avatar
      rhashtable: avoid large lock-array allocations · 4cf0b354
      Florian Westphal authored
      Sander reports following splat after netfilter nat bysrc table got
      converted to rhashtable:
      
      swapper/0: page allocation failure: order:3, mode:0x2084020(GFP_ATOMIC|__GFP_COMP)
       CPU: 0 PID: 0 Comm: swapper/0 Not tainted 4.8.0-rc1 [..]
       [<ffffffff811633ed>] warn_alloc_failed+0xdd/0x140
       [<ffffffff811638b1>] __alloc_pages_nodemask+0x3e1/0xcf0
       [<ffffffff811a72ed>] alloc_pages_current+0x8d/0x110
       [<ffffffff8117cb7f>] kmalloc_order+0x1f/0x70
       [<ffffffff811aec19>] __kmalloc+0x129/0x140
       [<ffffffff8146d561>] bucket_table_alloc+0xc1/0x1d0
       [<ffffffff8146da1d>] rhashtable_insert_rehash+0x5d/0xe0
       [<ffffffff819fcfff>] nf_nat_setup_info+0x2ef/0x400
      
      The failure happens when allocating the spinlock array.
      Even with GFP_KERNEL its unlikely for such a large allocation
      to succeed.
      
      Thomas Graf pointed me at inet_ehash_locks_alloc(), so in addition
      to adding NOWARN for atomic allocations this also makes the bucket-array
      sizing more conservative.
      
      In commit 095dc8e0 ("tcp: fix/cleanup inet_ehash_locks_alloc()"),
      Eric Dumazet says: "Budget 2 cache lines per cpu worth of 'spinlocks'".
      IOW, consider size needed by a single spinlock when determining
      number of locks per cpu.  So with 64 byte per cacheline and 4 byte per
      spinlock this gives 32 locks per cpu.
      
      Resulting size of the lock-array (sizeof(spinlock) == 4):
      
      cpus:    1   2   4   8   16   32   64
      old:    1k  1k  4k  8k  16k  16k  16k
      new:   128 256 512  1k   2k   4k   8k
      
      8k allocation should have decent chance of success even
      with GFP_ATOMIC, and should not fail with GFP_KERNEL.
      
      With 72-byte spinlock (LOCKDEP):
      cpus :   1   2
      old:    9k 18k
      new:   ~2k ~4k
      Reported-by: default avatarSander Eikelenboom <linux@eikelenboom.it>
      Suggested-by: default avatarThomas Graf <tgraf@suug.ch>
      Signed-off-by: default avatarFlorian Westphal <fw@strlen.de>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      4cf0b354
  9. 05 Apr, 2016 1 commit
  10. 19 Dec, 2015 1 commit
  11. 16 Dec, 2015 2 commits
    • Herbert Xu's avatar
      rhashtable: Fix walker list corruption · c6ff5268
      Herbert Xu authored
      The commit ba7c95ea ("rhashtable:
      Fix sleeping inside RCU critical section in walk_stop") introduced
      a new spinlock for the walker list.  However, it did not convert
      all existing users of the list over to the new spin lock.  Some
      continued to use the old mutext for this purpose.  This obviously
      led to corruption of the list.
      
      The fix is to use the spin lock everywhere where we touch the list.
      
      This also allows us to do rcu_rad_lock before we take the lock in
      rhashtable_walk_start.  With the old mutex this would've deadlocked
      but it's safe with the new spin lock.
      
      Fixes: ba7c95ea ("rhashtable: Fix sleeping inside RCU...")
      Reported-by: default avatarColin Ian King <colin.king@canonical.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      c6ff5268
    • Herbert Xu's avatar
      rhashtable: Enforce minimum size on initial hash table · 3a324606
      Herbert Xu authored
      William Hua <william.hua@canonical.com> wrote:
      >
      > I wasn't aware there was an enforced minimum size. I simply set the
      > nelem_hint in the rhastable_params struct to 1, expecting it to grow as
      > needed. This caused a segfault afterwards when trying to insert an
      > element.
      
      OK we're doing the size computation before we enforce the limit
      on min_size.
      
      ---8<---
      We need to do the initial hash table size computation after we
      have obtained the correct min_size/max_size parameters.  Otherwise
      we may end up with a hash table whose size is outside the allowed
      envelope.
      
      Fixes: a998f712 ("rhashtable: Round up/down min/max_size to...")
      Reported-by: default avatarWilliam Hua <william.hua@canonical.com>
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      3a324606
  12. 09 Dec, 2015 1 commit
  13. 06 Dec, 2015 1 commit
  14. 04 Dec, 2015 2 commits
  15. 23 Sep, 2015 1 commit
  16. 08 Jul, 2015 1 commit
    • Phil Sutter's avatar
      rhashtable: fix for resize events during table walk · 142b942a
      Phil Sutter authored
      If rhashtable_walk_next detects a resize operation in progress, it jumps
      to the new table and continues walking that one. But it misses to drop
      the reference to it's current item, leading it to continue traversing
      the new table's bucket in which the current item is sorted into, and
      after reaching that bucket's end continues traversing the new table's
      second bucket instead of the first one, thereby potentially missing
      items.
      
      This fixes the rhashtable runtime test for me. Bug probably introduced
      by Herbert Xu's patch eddee5ba ("rhashtable: Fix walker behaviour during
      rehash") although not explicitly tested.
      
      Fixes: eddee5ba ("rhashtable: Fix walker behaviour during rehash")
      Signed-off-by: default avatarPhil Sutter <phil@nwl.cc>
      Acked-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      142b942a
  17. 07 Jun, 2015 1 commit
  18. 16 May, 2015 1 commit
    • Herbert Xu's avatar
      rhashtable: Add cap on number of elements in hash table · 07ee0722
      Herbert Xu authored
      We currently have no limit on the number of elements in a hash table.
      This is a problem because some users (tipc) set a ceiling on the
      maximum table size and when that is reached the hash table may
      degenerate.  Others may encounter OOM when growing and if we allow
      insertions when that happens the hash table perofrmance may also
      suffer.
      
      This patch adds a new paramater insecure_max_entries which becomes
      the cap on the table.  If unset it defaults to max_size * 2.  If
      it is also zero it means that there is no cap on the number of
      elements in the table.  However, the table will grow whenever the
      utilisation hits 100% and if that growth fails, you will get ENOMEM
      on insertion.
      
      As allowing oversubscription is potentially dangerous, the name
      contains the word insecure.
      
      Note that the cap is not a hard limit.  This is done for performance
      reasons as enforcing a hard limit will result in use of atomic ops
      that are heavier than the ones we currently use.
      
      The reasoning is that we're only guarding against a gross over-
      subscription of the table, rather than a small breach of the limit.
      Signed-off-by: default avatarHerbert Xu <herbert@gondor.apana.org.au>
      Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
      07ee0722
  19. 05 May, 2015 1 commit
  20. 22 Apr, 2015 2 commits
  21. 25 Mar, 2015 1 commit
  22. 24 Mar, 2015 11 commits
  23. 20 Mar, 2015 4 commits