liburcu: userspace read-copy-update in four flavours

Read-copy-update for userspace programs

liburcu is an LGPL v2.1 licensed userspace read-copy-update library, and the repository description states the property that makes it interesting: the read-side access scales linearly with the number of cores.

The implementation is by Mathieu Desnoyers and Paul E. McKenney, whose names on the readme are the quickest way to place the project. The same file is the readme of the upstream project, and the repository description notes that this repository is a mirror of the official userspace-rcu git at git.lttng.org, which is worth keeping in mind for anything you might want to change.

The idea itself is the well known one. A reader takes a read lock, reads the shared structure, and releases it, and a writer publishes a new version of the structure and then waits for a grace period, meaning that every reader that was active before the publication has finished, before reclaiming the old one. What liburcu provides is that machinery outside the kernel, with a read side cheap enough to leave in place permanently.

The library exposes its API through a set of prefixes, and the readme lists the documentation file for each: rcu_ for the read-copy-update calls themselves, cmm_ for the concurrent memory model, caa_ for the concurrent architecture abstraction, cds_ for the concurrent data structures and uatomic_ for the userspace atomic operations.

The library is a synchronisation primitive rather than a framework: it does not give you threads, it gives you a way to publish a new version of a shared structure and reclaim the old one safely, and the surrounding application keeps its own threading model.

Four flavours, and the choice is speed against cooperation

There are four flavours of the library, and the readme gives each of them a paragraph explaining the trade.

The API members are prefixed with the flavour name, so urcu_memb_read_lock for one flavour and urcu_qsbr_read_lock for another, which means the flavours are separate libraries that share a naming scheme rather than one library with a runtime switch.

liburcu-memb is described as the preferred version in terms of grace-period detection speed, read-side speed and flexibility. liburcu-qsbr is the fastest on the read side at the expense of more intrusiveness in the application code. liburcu-mb uses memory barriers on the writer and reader sides, which results in faster grace-period detection but slower reads. And liburcu-bp stands for bulletproof, and is specifically designed to help a tracing library hook onto applications without requiring those applications to be modified.

That last one is the unusual case. In the bulletproof flavour, urcu_bp_init() and urcu_bp_unregister_thread() become no-ops, and calling urcu_bp_register_thread() becomes optional, with the state handled by the library internally at the expense of read-side and write-side performance. The trade is deliberate: a tracer that has to be attached to a program it did not write cannot ask that program to call a registration function, so the bulletproof flavour moves the cost into the library.

Whichever flavour you pick, the usage pattern is the same two steps, an include of the flavour header and linking against the matching library.

The memb flavour asks the kernel for help and falls back if it cannot

The memb flavour is the interesting one technically, because it uses a kernel facility when the kernel has it.

The readme says liburcu-memb dynamically detects kernel support for sys_membarrier(), and falls back on the urcu-mb scheme if support is not present, which has a slower read side. There is a configure option, --disable-sys-membarrier-fallback, that disables the fallback so that sys_membarrier() is required.

The reasoning is stated too. When sys_membarrier() is supported by the kernel, requiring it gives a small speedup, and the library aborts in the constructor if it is not supported, so a misconfigured deployment fails immediately and visibly rather than running slowly forever.

That is a well made decision for a library of this kind, and it is the kind of detail that is usually invisible in the documentation. The fallback means the library works everywhere, the configure option means a performance-sensitive deployment can insist on the fast path, and the abort in the constructor means the difference is discovered at startup rather than in a profile.

The grace period detection is where the read side is won, and the flavour that detects it fastest is the one that uses the kernel's memory barrier primitive when it is available.

QSBR moves the cost into the application, and says so

The QSBR flavour is the one that requires the most from the program using it, and the readme describes the requirement without hedging.

The QSBR flavour of RCU needs each reader thread to execute rcu_quiescent_state() periodically to progress. In other words, the thread has to tell the library that it is not currently inside a read-side critical section, and the library cannot reclaim anything until every thread has said so.

The readme also mentions the escape hatch for the awkward case: rcu_thread_online() and rcu_thread_offline() can be used to mark long periods for which the threads are not active. A thread that will sit idle for an hour should say so, otherwise it holds back the grace period for that hour.

The payoff is stated too: it provides the fastest read side at the expense of more intrusiveness in the application code. The read side is fastest because the thread does not have to publish or check anything to take a read lock, it just has to not be in a critical section.

The general rule for all four flavours is in the readme's initialisation section. Each thread that has reader critical sections, meaning any thread that uses urcu_<flavor>_read_lock() and urcu_<flavor>_read_unlock(), must first register to the library by calling urcu_<flavor>_register_thread(), and there is an unregistration call to match. For QSBR that is the price of the speed, and for the bulletproof flavour it is the one call that can be skipped.

Inlining small functions has a licence consequence and a version consequence

The quick start section is where the library is most careful, and it deals with the awkward question of what happens when a permissive or proprietary application links with an LGPL library.

The first point is that you define _LGPL_SOURCE, and only that macro, before including the urcu.h or urcu-qsbr.h header, if your code is LGPL or GPL compatible. If your application is distributed under another licence, function calls are generated instead of inlines, so your application can link with the library. Linking with one of the libraries is always necessary even for LGPL and GPL applications.

The second point is URCU_INLINE_SMALL_FUNCTIONS. Define it before including the Userspace RCU headers if you want small functions, ten lines or less, to be inlined into your application. The readme states that it can be used by applications distributed under any kind of licence and that it does not make the application a derived work of Userspace RCU.

The price of that is a version constraint. Those small inlined functions are guaranteed to match the library content as long as the library major version is unchanged, so the application must be compiled with headers matching the library major version number. And applications using URCU_INLINE_SMALL_FUNCTIONS may be unable to use the debugging features of Userspace RCU without being recompiled.

That last sentence is the one to remember. The inlining option is a performance win with a real operational cost, because a debugging session against a mismatched build will not behave the way the documentation implies.

Sixteen architectures, four operating systems, and a very old compiler floor

The portability section of the readme is long, and the detail matters for a library that goes into other people's builds.

Sixteen architectures are listed as supported, from x86 in its i486, i586 and i686 forms and amd64 through PowerPC in 32 and 64 bit, S390 and S390x, ARM in 32 and 64 bit, MIPS, NIOS2, Alpha, ia64, Sparcv9, Tilera, hppa and PA-RISC, m68k, RISC-V and LoongArch. Linux is tested on all of them. Beyond that, FreeBSD 13 on x86 and amd64, Cygwin and macOS on amd64 and arm64 are tested, while Android, NetBSD 5, OpenBSD and Solaris are listed as things that should also work, with the readme adding that more testing is needed before claiming support for them. That distinction between tested and probably fine is the kind of precision that helps.

The toolchain floor is C99 for the C compiler and C++11 for the C++ compiler, and the oldest officially supported and tested GCC is 4.8. The readme then lists the exceptions in detail, and they are specific: GCC 3.3 and 3.4 have a bug that prevents them generating volatile accesses to offsets in a TLS structure on 32-bit x86, so those versions are not compatible on i486, i586 and i686, and GCC 3.3 cannot match the xchg instruction on a 32-bit x86 build. Alpha, ia64 and ARM need GCC 4.x with atomic builtins support, and Linux aarch64 needs GCC 5.1 or better because earlier versions perform unsafe access to deallocated stack. Clang 3.0 is supported, and glibc 2.4 or newer should work, with 2.17 as the version tested against.

Those notes read like the accumulated experience of a library that has been built in awkward environments for a long time.

The build is autotools, and the tree is a mirror

Building from the git tree takes five steps, and the first one is the one people forget:

./bootstrap
./configure
make
make install
ldconfig

The bootstrap script is skipped if you use a tarball, and it calls the GNU tools needed to prepare the tree configuration. The readme lists what that needs: GNU autotools with automake 1.12 or newer and autoconf 2.69 or newer, with a warning to make sure the system wide automake points to a recent version, GNU Libtool 2.2 or newer, and GNU Make.

The test scripts in the tests directory depend on bash and the seq program, which is a small thing to know before a build fails on a minimal container.

The repository layout matches a mature autotools project: a Makefile.am at the root, configure.ac, the bootstrap script, an m4 directory for the macros, src for the implementation, include for the headers, doc for the API documentation, extras, scripts and tests, plus a ChangeLog, a CodingStyle.md, a LICENSE.md, a LICENSES directory and a file called lgpl-relicensing.md that exists for the relicensing of older LGPL code.

The last practical point is the mirror. The repository description says this is a mirror of the official userspace-rcu git at git.littng.org, so if you find a bug or want to contribute, the upstream tree is where that belongs, and the mirror is for reading and for fetching a specific revision.

Editorial conclusion

liburcu fits a C program that reads shared data far more often than it writes it, on a many-core machine, because the read path is a couple of instructions and the grace period detection is handled by the library, and because the four flavours let you choose how much the application has to cooperate. It is the wrong choice for a program that writes as often as it reads, where a lock is simpler, and it is the wrong choice if you want a threading library rather than a synchronisation primitive, since liburcu does not give you threads, it gives you a way to publish and reclaim data safely. Before you adopt it, pick the flavour for your workload, read the inline small functions section carefully because it affects your licence position and your build, and remember that this repository is a mirror of the upstream git at git.lttng.org, so patches belong upstream.

Frequently asked questions

Official sources

1. Issues
2. Project website
3. README
4. urcu/userspace-rcu on GitHub