Hi,
This series introduces hazard pointers [1] to kernel space. A TL;DR
description of hazard pointers is "a scalable refcounting mechanim
with RCU-like API". More information can be found at [2].
The problem we are trying to resolve here is refcount scalability
issues that cannot be resolved simply by RCU or SRCU (maybe due to the
requirement of an unbound protect duration). Neeraj has tried it in the
scalability issue[3] he has been working on, and he will share more
information in our LPC session [4] (and I will update in the list for
those who cannot make it to the session later).
My micro-benchmark shows the hazard pointers provide very good
scalability on par with percpu_ref/RCU/SRCU on the reader side:
(refscale in x86_64 + PREEMPT=y, avg reader duration in ns)
nreaders 1 8 32
percpu_ref 6.95123 10.0869 8.9674
rcu 2.97923 3.243 3.55077
hazptr 8.5991 8.40443 8.5762
srcu 16.7754 22.4807 20.2406
Things that we know are currently not working:
* Handling module unload, probably needs a hazptr_barrier()
similar to rcu_barrier().
* rcutorture support should be added to catch potential bugs (esp.
for callback handling).
* Improvement for updater side performance, currently all
callbacks are handled in one work, this can be improved by using
multiple work_structs or threads.
Of course, I might create some bugs, so please take a look. Also love to
hear anything on the current API. Any feedback is welcome!
Patch #1 is the implemenation of hazptr, Paul and Neeraj contributed a
lot, but all bugs are mine ;-)
Patch 2-3 add micro-benchmarks for hazptr and percpu_ref.
Patch #4 is a simple test I've used for development, I put it here just
in case someone wants to give a quick try, eventually, we need to add
hazptr to rcutorture (or has its own torture) for more testing.
Regards,
Boqun
[1]: M. M. Michael, "Hazard pointers: safe memory reclamation for
lock-free objects," in IEEE Transactions on Parallel and
Distributed Systems, vol. 15, no. 6, pp. 491-504, June 2004
[2]: https://docs.google.com/document/d/113WFjGlAW4m72xNbZWHUSE-yU2HIJnWpiXp91ShtgeE/
[3]: https://lore.kernel.org/lkml/20240916050811.473556-1-Neeraj.Upadhyay@xxxxxxx/
[4]: https://lpc.events/event/18/contributions/1731/
[5]: Herlihy, Maurice, Victor Luchangco, and Mark Moir. "The repeat
offender problem: A mechanism for supporting dynamic-sized,
lock-free data structures." International Symposium on Distributed
Computing. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002.
Boqun Feng (4):
hazptr: Add initial implementation of hazard pointers
refscale: Add benchmarks for hazptr
refscale: Add benchmarks for percpu_ref
WIP: hazptr: Add hazptr test sample
include/linux/hazptr.h | 83 +++++++
kernel/Makefile | 1 +
kernel/hazptr.c | 463 +++++++++++++++++++++++++++++++++++
kernel/rcu/refscale.c | 127 +++++++++-
samples/Kconfig | 6 +
samples/Makefile | 1 +
samples/hazptr/hazptr_test.c | 87 +++++++
7 files changed, 767 insertions(+), 1 deletion(-)
create mode 100644 include/linux/hazptr.h
create mode 100644 kernel/hazptr.c
create mode 100644 samples/hazptr/hazptr_test.c
--
2.45.2
