[RFC PATCH 0/4] Add hazard pointers to kernel

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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





[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux