?

Log in

No account? Create an account

Previous Entry | Next Entry

TL;DR: Do you know of additional publicly visible production uses of sequnce locking, hazard pointers, or RCU not already called out in the remainder of this blog post?

I am updating the deferred-processing chapter of “Is Parallel Programming Hard, And, If So, What Can You Do About It?” and would like to include a list of publicly visible production uses of sequence locking, hazard pointers, and RCU. I suppose I could also include reference counting, but given that it was well known before I was born, I expect that its list would be way too long to be useful!

The only production use of sequence locking that I am aware of is within the Linux kernel, but I would be surprised if it is not rather widely used. Can you tell me of more publicly visible production sequence-locking uses?

Hazard pointers is used within MongoDB (v3.0 and later) and within Facebook's Folly library, which is used in production at Facebook and perhaps elsewhere as well. It is also implemented by several libraries called out on its Wikipedia page (Concurrent Building Blocks, Concurrency Kit, Atomic Ptr Plus, and libcds). Hazard pointers is also sometimes called “safe memory reclamation” (SMR). Any other production hazard-pointers uses?

RCU is used within the Linux kernel, the FreeBSD kernel, the OpenBSD kernel, Linux Trace Toolkit Next Generation (LTTng), QEMU, Knot DNS, Netsniff-ng, Sheepdog, GlusterFS, and gdnsd. It is also implemented by several libraries, including Userspace RCU, Concurrency Kit, Facebook's Folly library, and libcds. RCU is also called “epochs” (from Keir Fraser), “generations” (from Tornado/K42), “passive serialization” (from IBM zVM), and probably other things as well. Any other production RCU uses?

So what do I mean by “publicly visible”? Open-source projects should qualify, as should scholarly publications regarding proprietary projects. Similarly, “production use” means use for getting some job done, as opposed to research, prototyping, or benchmarking. Not that there is necessarily anything wrong with research, prototyping, or benchmarking, but we are looking for things a little bit further along the hype cycle. ;-)

Comments

( 14 comments — Leave a comment )
paulmck
Mar. 5th, 2019 09:18 pm (UTC)
Social-media responses
NetBSD pserialize, which is based off of the zVM patent, but which appears to require readers to be in interrupt handlers or to disable interrupts or some such. Matt Wilson: https://twitter.com/_msw_/status/1103007534044962817

Facebook jemalloc uses seqlock. David Goldblatt: https://twitter.com/davidtgoldblatt/status/1103007339169243136
https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/seq.h
https://github.com/jemalloc/jemalloc/blob/dev/src/hook.c
paulmck
Mar. 5th, 2019 09:28 pm (UTC)
Private email response
A colleague said that he believes that the Android user-level platform code uses seqlock. A quick web search finds the Linux-kernel uses, being as the Linux kernel is a part of Android. Anyone have any pointers to the non-Linux-kernel Android uses of seqlock?

Edited at 2019-03-05 10:03 pm (UTC)
fanf
Mar. 5th, 2019 09:34 pm (UTC)
You already have Knot DNS, but version 2.8.0 was just released and it has some fun stuff in this area https://www.knot-dns.cz/2019-03-05-version-280.html

I enhanced their version of my qp trie data structure https://dotat.at/prog/qp/ to add a copy-on-write scheme based on one bit refcounts, to support single-writer-multiple reader updates. In previous versions, Knot had to copy the entire zone before updating it, which could be costly for bug zones.

This was my first attempt at a concurrent data structure, and I relied a lot on the existing RCU logistics, so I hope there aren’t lurking hazards I am not aware of!
paulmck
Mar. 5th, 2019 11:20 pm (UTC)
Looks plausible, but...
Nice -- and it does look plausible, but the only way to have much confidence is to hammer the code with a good solid multi-threaded stress test on the largest system you can get your hands on. Given that this is an open-source project, you do qualify for access to some large IBM Power servers, if that would help: https://osuosl.org/services/powerdev/
paulmck
Mar. 5th, 2019 11:27 pm (UTC)
Re: Looks plausible, but...
Ah, you also need to use rcu_dereference() when fetching a pointer to an RCU-protected structure. This protects you from a number of nasty things that the compiler can otherwise do to you, a fair number of which are listed in Section 15.3.2 of "Is Parallel Programming Hard, And, If So, What Can You Do About It?", which may be freely downloaded from here: https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html

For one immediate example, the compiler could decide to fetch the pointer twice, which could cause some of the fields to be loaded from one structure and others to be loaded from another structure, despite your code having one local variable that is used consistently.
fanf
Mar. 5th, 2019 11:28 pm (UTC)
RE: Looks plausible, but...
Thanks, really kind of you to take the time to have a look at it! And thanks for the pointer to the big test server :-)
Matt Wilson
Mar. 6th, 2019 12:25 am (UTC)
Re: More from Matt Wilson (thank you!)
You're welcome! Providing some links is very little compared to all the work you've done in this space. Thank you! :-)
paulmck
Mar. 6th, 2019 04:10 pm (UTC)
Nadav Har'El notes OSv use of RCU
See files include/osv/rcu.hh and core/rcu.cc here:
https://github.com/cloudius-systems/osv.git

Avi Kivity also calls out RCU-protected hashtable and list in include/osv/rcu-hashtable.hh and include/osv/rcu-list.hh.

Edited at 2019-03-06 04:28 pm (UTC)
paulmck
Mar. 6th, 2019 04:14 pm (UTC)
Dmitry Vyukov points out golang GC COW RCU-like usage
See the "Example (ReadMostly) here: https://golang.org/pkg/sync/atomic/#Value

Edited at 2019-03-06 04:15 pm (UTC)
paulmck
Mar. 8th, 2019 12:33 am (UTC)
Raul Guitterez S. notes envoyproxy use of RCU
paulmck
Mar. 8th, 2019 12:49 am (UTC)
@peo3 suggests OpenBSD's SRP implements hazard pointers
https://github.com/openbsd/src/commit/52776b7dd171c092a35f86a9ed8bd1c22cac9fb8

Checking with Maged. ;-)

But this more recent version looks much more like hazard pointers: https://github.com/openbsd/src/blob/HEAD/sys/kern/kern_srp.c

Confirmed, though membar_consumer() rather than membar_sync(). Also, numerous APIs seem to depend on KERNEL_LOCK(), which looks to be the OpenBSD counterpart to Linux-kernel's old BKL.

Edited at 2019-03-08 06:45 pm (UTC)
paulmck
Mar. 13th, 2019 12:18 am (UTC)
And these are now reflected in perfbook
After a few rounds with github and bibtex, these are now in perfbook. There are a few exceptions, for example, RCU is implemented in Folly, but I see no uses of that implementation.

Thank you all for all the pointers!!!
( 14 comments — Leave a comment )