linux-stable.git/lib/rhashtable.c, branch v6.12.109

rhashtable: clear stale iter->p on table restart

2026-08-09T18:23:10+00:00

[ Upstream commit 8173f7e2ce67e6ca1d4763f3da14e5b01ce77456 ]

rhashtable_walk_start_check() has two restart paths when resuming a walk.
When iter->walker.tbl is valid, it re-validates iter->p against the table
and sets iter->p = NULL if the object is gone.  When iter->walker.tbl is
NULL (table was freed during resize), it resets slot and skip but forgets
to clear iter->p.

rhashtable_walk_next() then dereferences the stale iter->p, reading
freed memory.  This is a use-after-free.

Any caller that does multi-fragment rhashtable walks across
walk_stop/walk_start boundaries is affected.  Concrete cases include
netlink_diag (__netlink_diag_dump in net/netlink/diag.c) and TIPC
(tipc_nl_sk_walk in net/tipc/socket.c).

Crash stack (netlink_diag):
  BUG: KASAN: slab-use-after-free in rhashtable_walk_next+0x365/0x3c0
  Read of size 8 at addr ffff88801a9d2438 (freed kmalloc-2k, offset 1080)
  Call Trace:
   rhashtable_walk_next+0x365/0x3c0 (lib/rhashtable.c:1016)
   __netlink_diag_dump+0x160/0x760 (net/netlink/diag.c:122)
   netlink_diag_dump+0xc2/0x240
   netlink_dump+0x5bc/0x1270
   netlink_recvmsg+0x7a3/0x980
   sock_recvmsg+0x1bc/0x200
   __sys_recvfrom+0x1d4/0x2c0

Fixes: 5d240a8936f6 ("rhashtable: improve rhashtable_walk stability when stop/start used.")
Cc: 
Reported-by: AutonomousCodeSecurity@microsoft.com
Reported-by: Yuan Tan 
Closes: https://lore.kernel.org/linux-crypto/CAB8m9Wh559e+=n8z51gB8DrbEyCc2mc0MgGjrRR6_VXBmU=2AQ@mail.gmail.com
Signed-off-by: Cen Zhang (Microsoft) 
Reviewed-by: NeilBrown 
Signed-off-by: Herbert Xu 
Signed-off-by: Sasha Levin

rhashtable: Fix rhashtable_try_insert test

2025-02-08T08:57:35+00:00

[ Upstream commit 9d4f8e54cef2c42e23ef258833dbd06a1eaff89b ]

The test on whether rhashtable_insert_one did an insertion relies
on the value returned by rhashtable_lookup_one.  Unfortunately that
value is overwritten after rhashtable_insert_one returns.  Fix this
by moving the test before data gets overwritten.

Simplify the test as only data == NULL matters.

Finally move atomic_inc back within the lock as otherwise it may
be reordered with the atomic_dec on the removal side, potentially
leading to an underflow.

Reported-by: Michael Kelley 
Fixes: e1d3422c95f0 ("rhashtable: Fix potential deadlock by moving schedule_work outside lock")
Signed-off-by: Herbert Xu 
Tested-by: Michael Kelley 
Reviewed-by: Breno Leitao 
Tested-by: Mikhail Zaslonko 
Signed-off-by: Herbert Xu 
Signed-off-by: Sasha Levin

rhashtable: Fix potential deadlock by moving schedule_work outside lock

2025-02-08T08:57:29+00:00

[ Upstream commit e1d3422c95f003eba241c176adfe593c33e8a8f6 ]

Move the hash table growth check and work scheduling outside the
rht lock to prevent a possible circular locking dependency.

The original implementation could trigger a lockdep warning due to
a potential deadlock scenario involving nested locks between
rhashtable bucket, rq lock, and dsq lock. By relocating the
growth check and work scheduling after releasing the rth lock, we break
this potential deadlock chain.

This change expands the flexibility of rhashtable by removing
restrictive locking that previously limited its use in scheduler
and workqueue contexts.

Import to say that this calls rht_grow_above_75(), which reads from
struct rhashtable without holding the lock, if this is a problem, we can
move the check to the lock, and schedule the workqueue after the lock.

Fixes: f0e1a0643a59 ("sched_ext: Implement BPF extensible scheduler class")
Suggested-by: Tejun Heo 
Signed-off-by: Breno Leitao 

Modified so that atomic_inc is also moved outside of the bucket
lock along with the growth above 75% check.

Signed-off-by: Herbert Xu 
Signed-off-by: Sasha Levin

lib/rhashtable: cleanup fallback check in bucket_table_alloc()

2024-09-02T03:43:32+00:00

Upon allocation failure, the current check with the nofail bits is
unnecessary, and further stands in the way of discouraging direct use of
__GFP_NOFAIL.  Remove this and replace with the proper way of determining
if doing a non-blocking allocation for the nested table case.

Link: https://lkml.kernel.org/r/20240806153927.184515-1-dave@stgolabs.net
Signed-off-by: Davidlohr Bueso 
Suggested-by: Michal Hocko 
Cc: Davidlohr Bueso 
Cc: Herbert Xu 
Signed-off-by: Andrew Morton

rhashtable: plumb through alloc tag

2024-04-26T03:55:57+00:00

This gives better memory allocation profiling results; rhashtable
allocations will be accounted to the code that initialized the rhashtable.

[surenb@google.com: undo _noprof additions in the documentation]
  Link: https://lkml.kernel.org/r/20240326231453.1206227-1-surenb@google.com
Link: https://lkml.kernel.org/r/20240321163705.3067592-32-surenb@google.com
Signed-off-by: Kent Overstreet 
Signed-off-by: Suren Baghdasaryan 
Tested-by: Kees Cook 
Cc: Alexander Viro 
Cc: Alex Gaynor 
Cc: Alice Ryhl 
Cc: Andreas Hindborg 
Cc: Benno Lossin 
Cc: "Björn Roy Baron" 
Cc: Boqun Feng 
Cc: Christoph Lameter 
Cc: Dennis Zhou 
Cc: Gary Guo 
Cc: Miguel Ojeda 
Cc: Pasha Tatashin 
Cc: Peter Zijlstra 
Cc: Tejun Heo 
Cc: Vlastimil Babka 
Cc: Wedson Almeida Filho 
Signed-off-by: Andrew Morton

rhashtable: Allow rhashtable to be used from irq-safe contexts

2022-12-09T10:42:56+00:00

rhashtable currently only does bh-safe synchronization making it impossible
to use from irq-safe contexts. Switch it to use irq-safe synchronization to
remove the restriction.

v2: Update the lock functions to return the ulong flags value and unlock
    functions to take the value directly instead of passing around the
    pointer. Suggested by Linus.

Signed-off-by: Tejun Heo 
Reviewed-by: David Vernet 
Acked-by: Josh Don 
Acked-by: Hao Luo 
Acked-by: Barret Rhoden 
Cc: Linus Torvalds 
Signed-off-by: David S. Miller

lib: fix spelling mistakes

2021-07-08T18:48:20+00:00

Fix some spelling mistakes in comments:
permanentely ==> permanently
wont ==> won't
remaning ==> remaining
succed ==> succeed
shouldnt ==> shouldn't
alpha-numeric ==> alphanumeric
storeing ==> storing
funtion ==> function
documenation ==> documentation
Determin ==> Determine
intepreted ==> interpreted
ammount ==> amount
obious ==> obvious
interupts ==> interrupts
occured ==> occurred
asssociated ==> associated
taking into acount ==> taking into account
squence ==> sequence
stil ==> still
contiguos ==> contiguous
matchs ==> matches

Link: https://lkml.kernel.org/r/20210607072555.12416-1-thunder.leizhen@huawei.com
Signed-off-by: Zhen Lei 
Reviewed-by: Jacob Keller 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rhashtable: Restore RCU marking on rhash_lock_head

2020-07-29T00:09:49+00:00

This patch restores the RCU marking on bucket_table->buckets as
it really does need RCU protection.  Its removal had led to a fatal
bug.

Signed-off-by: Herbert Xu 
Signed-off-by: David S. Miller

rhashtable: Drop raw RCU deref in nested_table_free

2020-06-06T22:51:17+00:00

This patch replaces some unnecessary uses of rcu_dereference_raw
in the rhashtable code with rcu_dereference_protected.

The top-level nested table entry is only marked as RCU because it
shares the same type as the tree entries underneath it.  So it
doesn't need any RCU protection.

We also don't need RCU protection when we're freeing a nested RCU
table because by this stage we've long passed a memory barrier
when anyone could change the nested table.

Signed-off-by: Herbert Xu 
Signed-off-by: David S. Miller

treewide: Replace GPLv2 boilerplate/reference with SPDX - rule 500

2019-06-19T15:09:55+00:00

Based on 2 normalized pattern(s):

  this program is free software you can redistribute it and or modify
  it under the terms of the gnu general public license version 2 as
  published by the free software foundation

  this program is free software you can redistribute it and or modify
  it under the terms of the gnu general public license version 2 as
  published by the free software foundation #

extracted by the scancode license scanner the SPDX license identifier

  GPL-2.0-only

has been chosen to replace the boilerplate/reference in 4122 file(s).

Signed-off-by: Thomas Gleixner 
Reviewed-by: Enrico Weigelt 
Reviewed-by: Kate Stewart 
Reviewed-by: Allison Randal 
Cc: linux-spdx@vger.kernel.org
Link: https://lkml.kernel.org/r/20190604081206.933168790@linutronix.de
Signed-off-by: Greg Kroah-Hartman