Kernel development

Kernel release status

The current development kernel is 4.2-rc5, released on August 2. Linus is wishing things were going a bit more smoothly. "We're getting up there to the later rc's, but it's looking like 4.2 might be one of the releases needing more than the usual seven rc releases - things aren't calming down like I would wish, and we've still had some fairly annoying issues pop up."

Stable updates: 4.1.4, 3.14.49, and 3.10.85 were released on August 3.

Comments (none posted)

Quotes of the week

— Geert Uytterhoeven

— Steve Rostedt

— Dave Airlie

Comments (none posted)

Real-world use of Linux multipath TCP

LWN looked at the Linux multipath TCP implementation back in 2013. That code remains out of tree, but it now seems that it is being used in some Samsung phones in Korea. "This service enables smartphone users to reach bandwidth of up to 1 Gbps on existing smartphones. This is probably the fastest commercially deployed mobile network. They achieve this high bandwidth by combining both fast LTE (with carrier aggregation) and fast WiFi networks on Multipath TCP enabled smartphones." (Thanks to Oliver Bonaventure).

Comments (11 posted)

ioremap() and memremap()

Like user space, the kernel accesses memory through page tables; as a result, when kernel code needs to access memory-mapped I/O devices, it must first set up an appropriate kernel page-table mapping. The in-kernel tool for that job has long been ioremap(), which has a number of variants. It turns out that some of those variants are not always the right tool for the job, leading to a certain amount of workaround code in the kernel. That situation may change, though, as part of a move away from ioremap() for the problematic cases.

A successful call to ioremap() returns a kernel virtual address corresponding to start of the requested physical address range. This address is not normally meant to be dereferenced directly, though, for a number of (often architecture-specific) reasons. Instead, accessor functions like readb() or iowrite32() should be used. To enforce this rule, the return address from ioremap() is annotated with the __iomem marker; that will cause the sparse checker to complain about accesses that do not use the proper functions.

There is also the little matter of caching. The CPU normally caches data from memory, but that is a bad idea when I/O is involved for a number of reasons. Attempts to read a full cache line from I/O memory can have no end of unexpected side effects, and delaying writes to I/O memory can change the way the device operates. I/O memory should normally function as a direct control channel to the device; to that end, ioremap() disables caching on device memory — on the x86 architecture, at least.

In truth, the caching status of a memory range obtained from ioremap() is not fully defined. As a general rule, uncached is the default, but there is still an ioremap_nocache() that can be called by code that wants to be absolutely sure that there will be no cache between it and its device memory.

In some cases, though, I/O memory is just memory; the video memory used by a graphics adapter is a classic example. With this kind of memory, direct pointer references can be expected to work and caching in the CPU may be acceptable; indeed, it may be required to get reasonable performance. For such cases, there is an ioremap_cache() that creates a cached mapping if possible. Most architectures also have a couple of variants that allow caching of reads but limit caching of writes. In particular, ioremap_wc() allows combining of write operations and ioremap_wt() causes writes to go directly to device memory. With these variants, driver writers can obtain the kind of mapping they need for a specific piece of device memory.

Dan Williams recently ran into a couple of problems with this family of functions, though. One is that they all return pointers with the __iomem annotation. A driver that is mapping I/O memory with caching enabled almost certainly will treat the resulting address range as if it were ordinary memory — including directly dereferencing pointers into that range. To do so, they must either cast away the __iomem annotation or simply ignore it. In the former case, the code is noisier than it would otherwise be; in the latter case, anybody running sparse on the code will have to ignore the resulting warnings.

Beyond that, many architectures do not support all of the various caching modes, so the architecture-specific header files are full of lines like:

    #define ioremap_wt ioremap_nocache

The result is that callers of functions like ioremap_wt() may silently fail to get the writethrough caching that they are asking for.

Dan's answer to both problems is a patch set adding a new function for the mapping of device memory that behaves like memory:

    void *memremap(resource_size_t offset, size_t size, unsigned long flags);

This function will (on success) return an address for a mapping to the device memory found at the given physical offset and of the given size (in bytes). The flags argument can be either MEMREMAP_WB for full writeback caching or MEMREMAP_WT for writethrough caching. The returned address does not have the __iomem annotation. If the requested caching behavior cannot be provided, memremap() will return NULL rather than fall back to a different type of caching.

The patch set converts most in-kernel code over to the new interface.

This work is in its third revision as of this writing, and the (few) review comments made have been addressed. It clarifies the driver API, clearly separating two different use cases for the mapping of device memory, and it should result in less sparse warning noise. There is not much to dislike at this point, so there shouldn't be much keeping it out of the 4.3 merge window.

Comments (none posted)

Atomic mode setting design overview, part 1

Over the past few years, two big trends forged the need for a completely new kernel display driver interface. On one hand, people stopped appreciating partial redrawing and windows torn to pieces when anything changed in their GUI. New compositors like Wayland have been created with the slogan that "every frame is perfect". On the other hand, there are battery-powered phones and tablets with fancy graphical interfaces, but serious limits on power consumption. And that brought along an explosion of special-purpose display hardware to help out the rather power-hungry, but more general purpose, GPU in compositing screen contents. Bringing these trends together yields the need to update a lot of display hardware state in an all-or-nothing, atomic manner to ensure every frame is perfect and all the power-usage-optimized hardware is used as much as possible.

After a few years of development, the atomic display update ioctl() for Direct Rendering Manager (DRM) drivers is finally ready for prime time with the 4.2 pull request from Dave Airlie. It's been a long road, with a lot of drivers already converted over to atomic and even more in progress, and the atomic helper libraries and support code in the DRM subsystem sufficiently polished. But what's really missing is a design overview of what the overall atomic infrastructure looks like and why some decisions and details are implemented the way they are.

This article, which is first of the two articles in a series, will start with a recap of the history of kernel display mode-setting support to explain how the older interfaces came to be and why they're no longer suitable. It will then look at out-of-tree solutions and finally cover what the merged atomic display update interface looks like. The second article will delve deeper into some of the details of the implementation.

Before digging into all the details, a quick overview over how display hardware is represented today in the DRM subsystem is needed. First there is struct drm_connector which represents a screen, whether that's an integrated panel or an external screen. Note that connectors can be hot-plugged nowadays, since DisplayPort supports branching and multiplexing of multiple devices over one cable, similar to other peripheral buses. At the other end there's struct drm_plane, representing a scanout engine that reads pixel data from memory represented by a struct drm_framebuffer and provides it to the display hardware.

To allow drivers to support hardware features beyond what's possible with the core control data for each object, DRM supports properties that can be attached to any DRM object. There are different types of properties that accept different inputs like enumerations (e.g. for selecting between upscaling modes like pillarbox or letterbox) or integer ranges (e.g. for brightness control).

With fancy hardware, a plane can be freely positioned in the output rectangle, scaled or otherwise adjusted. Both ends are tied together with a struct drm_crtc which represents a display pipeline. Note that CRTC means "cathode ray tube controller" and hence is one of those abbreviations that only make historical sense. Multiple planes can be connected to a single CRTC to provide it with input data, and such a display pipeline then, in turn, connects to one or more drm_connectors to actually show something on screens. Besides being the central object for routing, a CRTC also keeps track of other settings like the display mode (i.e. refresh rate and resolution) used by the display pipeline and the background color that should be shown where no plane is visible at all.

The old world — A pile of ioctl() commands and properties

There's a much better and detailed writeup of the mode-setting history around, so I'll just focus on the more recent bits. The new age of display drivers in the kernel started in earnest almost seven years ago with the initial merge of the KMS (kernel mode setting) support. Well, there was always fbdev, but that subsystem never gained dearly needed support for proper graphics memory management, didn't have a clean separation between display and rendering, and never solved a host of other troubles.

Initial KMS ioctl() commands were modeled after X's user-space mode-setting protocol XRandR, which means they were good enough to set modes on screens individually and connect a single primary framebuffer object (representing a driver-specific memory buffer) with that display. This was all designed when rotating desktop cubes were all the rage and everyone wanted to use the 3D rendering engine for desktop compositing only — old-style video overlay planes seriously fell out of favor (you can't wobble them!) and hence weren't supported at all.

Well, there was one exception: cursor support. But that was just a bolted-on ioctl() that didn't even use the KMS framebuffer abstraction. And cursor updates couldn't be synced to anything, neither primary framebuffer updates nor the vertical blank — X didn't need it and couldn't use it. Without synchronizing to the vertical blanking (Vsync for short), the screen redrawing can race with the update and result in ugly tearing effects. Later on non-blocking updates for the primary plane were added to have support for proper Vsynced, non-tearing updates of the primary plane.

Of course, then smartphones and tablets showed up, so it wasn't cool to blow through power for display anymore. Suddenly overlay planes became important again since they're much more power-efficient in some narrow but popular use cases like video playback. KMS gained support for them in the form of additional plane objects and a new set of ioctl() commands.

But, like cursor updates, plane updates couldn't be synced to anything else, neither plane updates nor Vsync, again because X couldn't do more and nothing else cared about upstream graphics. The result was a mess of three different ioctl() interfaces for essentially just different instances of the same hardware. Planes, whether primary, cursor, or overlay, all take a framebuffer object that then all get blended together somehow, before being fed to a display pipeline (represented by a CRTC object in kernel mode setting), which feeds the connectors and panels. Unifying the plane interfaces was fairly simple: primary and cursor planes simply had to be exported as such, optionally, in order to not confuse existing user space.

But there was still no unified ioctl() that could do it all; for example, only the primary plane supported non-blocking updates with precise completion events. And there was no interface to update multiple planes together — user space had to make multiple ioctl() calls and hope that the updates all happened in the same frame. That's obviously a no-go for modern compositors like Wayland that want to guarantee pixel-perfect updates for every frame.

The other thing that happened is adding property support to all KMS objects to easily expose additional features like controlling the blending between planes, setting a background color, or rotating planes or the entire output. Of course, that was again done with a separate ioctl(). And, again, because X couldn't do any better back when this was introduced, there's no way to synchronize updates. Which means broken updates become ever more likely, as, for example when the rotation value is already updated but the plane contents aren't yet updated to match. If it's possible at all — some values can only be changed together or in a specific order, like disabling an additional plane before switching the primary one to a more memory-bandwidth-demanding mode.

It was all a mess and in dire need of a solution.

Android's Atomic Display Framework

Outside of upstream graphics, especially in Android-land, the situation was even worse. Every GPU vendor had its own kernel/user-space interfaces and all the drivers were reinventing the same wheels, but broken in slightly different ways. Google was unhappy about the state of things and created the Atomic Display Framework (ADF). It was inspired a bit by the upstream kernel mode-setting support, but was a completely new subsystem otherwise. For our tour, the overall design isn't useful to look at, but it's interesting to look at where ADF fell short for upstream use:

• ADF supports only one update queue for the entire device. That's a perfect fit for Android's SurfaceFlinger, which just has one draw loop, and it's totally sufficient for phones and tablets where, in most cases, you only ever have one screen. But if you have multiple screens, which usually run at slightly different refresh rates, then one update queue isn't enough. You have to either stall the faster screen or drop frames on the slower one, both of which will result in not-perfectly-smooth animations. The non-blocking primary plane updates in upstream are already fully decoupled and compositors like Wayland already have per-output redraw loops. This was a big omission from ADF.
• ADF describes atomic updates in a driver-specific blob of data. That's fine for Android where you have a GPU-specific counterpart driver in user space behind the Hardware Composer interface (similar to an X device driver like xf86-video-intel). But upstream also wants to support generic user-space compositors like Wayland or the xf86-video-modesetting X driver. ADF has a generic interface for updates, but it's only really good enough for a simple boot splash. Of course there will always be some features specific to one driver, but by standardizing properties across drivers, upstream DRM already has the infrastructure to support arbitrary functionality in generic user-space code.
• ADF was only atomic for plane updates and not for reconfiguring the output routing. Again, this is not a problem if you only really care about the single-screen case, but on modern GPUs there are lots of shared resources when using more than one output. And the naive way of reconfiguring by just looping over all outputs can easily end up in a state that isn't supported by the hardware, for example because the driver ran out of display clock generators for the interim configuration. Hence atomic updates for the entire pipeline across all outputs was definitely needed in upstream. More important was some means to figure out whether a change would work out or not before applying it and risking being stuck with a black screen.
• ADF was implemented as a monolithic mid-layer subsystem. That's great if your goal is to improve the state of the art for 90% of all drivers and a real pain if your driver is one of the 10% where the mid-layer just doesn't fit. Despite some horror shows in some upstream DRM legacy subsystems, the mode-setting part is nicely structured by exposing the full interface from the ioctl() to the driver hooks and providing a big helper library for all the common cases. Definitely something to keep.
• ADF also has a completely new user-space ABI and driver interface, which would mean separate drivers for everything. Not desirable from a backward compatibility and maintenance point of view.

Of course solving these problems isn't all that easy. The following sections in this article and the next one will look at some of them in more detail and describe how it's done in the atomic support that was merged.

A generic driver interface that's actually useful

Since DRM already has properties, it was fairly clear to reuse them as the generic transport for the user-space ABI. User space simply supplies a list of (object_id, property_id, value) triples. And that immediately takes care of extensibility — user space that doesn't understand a given property just doesn't ever change it. As long as a driver initializes everything to something sane (like setting the rotation property to unrotated) then older generic user space will keep on working when new features get added.

Of course there were some gaps with that plan — properties for all the existing metadata had to be added, with a special flag to only expose them to atomic-aware user space. A new property type has been created that accepts kernel mode-setting objects as values to set up routing links. And a few other bits needed adjustments, like extending blob properties to make them usable for atomic updates.

Allowing partial updates also solved the in-kernel backward compatibility problem: All the old KMS ioctl() commands did partial updates, only allowing full updates would have meant that drivers needed to support both legacy and atomic interfaces. With partial atomic update support, legacy driver hooks can instead be implemented in terms of the atomic driver entry points in a generic helper library.

Finally, there was the question of exposing hardware and driver limitations to user space. There are many of those, and every time a new property is standardized it becomes more complex. Trying to describe constraints explicitly was quickly discarded as impossible; the only thing the kernel can do is reject requests for impossible states (or even just transitions, as sometimes that's the limiting factor). But that would require driver-specific user space, rendering all the effort with a generic interface moot.

Instead, the atomic ioctl() supports a DRM_MODE_ATOMIC_TEST_ONLY flag to not actually commit the update to the hardware. With this, generic user space can build up the state it wants step-by-step using some heuristics and test each time around whether the update will still work, until it's found the maximal configuration. For example, a compositor could add planes one-by-one in order of preference of what would save the most power when using a hardware plane to compose a given client buffer onto the screen and then fall back to using OpenGL for any remaining client buffers. It can then queue the real update once everything is ready with the assurance that it will work out. Assuming no bugs in drivers, of course. This way, generic user space can use hardware with really strange restrictions, without explicitly describing those restrictions in the interface. Of course it won't always make a perfect decision, but in most cases it will be good enough.

This was all settled fairly quickly and, except for some cosmetics, the upstream atomic user-space ABI has stayed unchanged since the first RFC was floated about three years ago. The big question that took a few years to settle was the core-to-driver interface. Just passing the same list of triples to drivers would have been easiest and was done for proof-of-concept implementations. But that would have meant a brittle and verbose interface for in-kernel users, and for the final atomic support there would be a lot of those to handle all the legacy ioctl() commands and legacy users like fbdev emulation. Simply passing decoded structures around, like with the old hooks, wasn't an option either because of the need for driver-private extensions and partial updates.

The currently merged solution is quite a bit of a beast. First there are generic state structures for each type of mode-setting object that you can assign properties for. The state structure for planes, for example, is:

    struct drm_plane_state {
	struct drm_plane *plane;

	struct drm_crtc *crtc;
	struct drm_framebuffer *fb;

	/* Signed dest location allows it to be partially off screen */
	int32_t crtc_x, crtc_y;
	uint32_t crtc_w, crtc_h;

	/* ... */

	struct drm_atomic_state *state;
    };

Every state structure has a pointer to the object the state is for. Then follows all the object-specific KMS state decoded into the kernel-internal representations. For planes, this is a pointer to the CRTC (which represents a display pipeline) the plane is attached to, and a pointer to the framebuffer it should scan out, the position of the plane on the display window, and a few other things left out for clarity. And, finally, a backpointer to a drm_atomic_state structure. This keeps track of all the various per-object states of an update, allowing partial updates at the object level.

When an update finally gets committed, a pointer to the state is stored in each object, here for planes that would be plane->state. When committing states, the plane->state->state backpointer is also cleared since, once committed, the state structure is owned by the driver and no longer owned by the update structure itself.

Partial updates within an object are done by duplicating the existing state. And support for driver-private extensions is handled by allowing drivers to embed struct drm_plane_state into their own structures. That means there's an ->atomic_duplicate_state() hook with a default implementation like drm_atomic_helper_plane_duplicate_state(). Since a few of the objects pointed at by state structures are reference counted (like framebuffers), there's also a ->atomic_destroy_state() hook to clean everything up. For all the hooks there's a default implementation even when there's not yet a need for it — that way it's easy to standardize the handling of some properties by moving them from driver-specific structures into the core ones.

This way, generic code and drivers that only implement generic properties never have to deal with the raw property IDs and values directly, as all the decoding is done in the core code implementing the atomic ioctl(). For fancy drivers, there's the ->atomic_set_property() and ->atomic_get_property() hooks that again operate on the state structures and are used for decoding additional properties.

Besides all these functions and hooks to handle per-object state structures, the main atomic driver interface is simple and consists of only two hooks:

• ->atomic_check() needs to make sure that the passed-in atomic update is possible. It is only allowed to look at and write to state structures for objects referenced from the passed-in struct drm_atomic_state. On one hand, this is needed to make sure that the TEST_ONLY mode doesn't accidentally change persistent hardware or software state. The other reason is to make sure that concurrent updates don't trample on each another by accident — duplicating a state also grabs the required locks behind the scenes. Locking will be discussed in more detail in the second part of this article series.
• ->atomic_commit() optionally commits the state that has been prepared and checked by ->atomic_check(). Drivers are allowed and encouraged to store derived state (like display clock configuration) in the driver-private part of their state objects to avoid duplicating logic between the check and commit hooks. Note that for robustness, such derived state should be cleared when duplicating state objects, to make sure that correct values are always computed. The commit function is only allowed to fail due to lack of memory or catastrophic hardware failure. Any other problem with the update (like lack of shared resources on the GPU) must be caught earlier in the check callback.

The next article will discuss a few more details of the interface around handling asynchronous updates and locking. Of course, drivers don't have to implement the main atomic hooks completely themselves, since that's anything but trivial — there's a large helper library that will also be covered.

Comments (10 posted)

RCU requirements part 2 — parallelism and software engineering

This is the second of a three-article series on the requirements that have driven the read-copy-update (RCU) design toward its current form. Part 1 covered the fundamental requirements that make RCU what it is. In this installment, we'll get into the issues that affect how those fundamental requirements are met; in particular, we'll look at:

• Parallelism facts of life
• Quality-of-implementation requirements
• Software-engineering requirements

Also, of course, no RCU article would be complete without the answers to the quick quizzes at the end.

Parallelism facts of life

These parallelism facts of life are by no means specific to RCU, but the RCU implementation must abide by them. They therefore bear repeating:

1. Any CPU or task may be delayed at any time, and any attempts to avoid these delays by disabling preemption, interrupts, or whatever are completely futile. This is most obvious in preemptible user-level environments and in virtualized environments (where a given guest OS's virtual CPUs can be preempted at any time by the underlying hypervisor), but can also happen in bare-metal environments due to ECC errors, NMIs, and other hardware events. Although a delay of more than about 20 seconds can result in warnings, the RCU implementation is obligated to use algorithms that can tolerate extremely long delays, but where “extremely long” is not long enough to allow wraparound when incrementing a 64-bit counter.
2. Both the compiler and the CPU can reorder memory accesses. Where it matters, RCU must use compiler directives and memory-barrier instructions to preserve ordering.
3. Conflicting writes to memory locations in any given cache line will result in expensive cache misses. Greater numbers of concurrent writes and more-frequent concurrent writes will result in more dramatic slowdowns. RCU is therefore obligated to use algorithms that have sufficient locality to avoid significant performance and scalability problems.
4. As a rough rule of thumb, only one CPU's worth of processing may be carried out under the protection of any given exclusive lock. RCU must therefore use scalable locking designs.
5. Counters are finite, especially on 32-bit systems. RCU's use of counters must therefore tolerate counter wrap, or be designed such that counter wrap would take way more time than a single system is likely to run. An uptime of ten years is quite possible, a runtime of a century much less so. As an example of the latter, RCU's dyntick-idle nesting counter allows 54 bits for the interrupt-nesting level (this counter is 64 bits even on a 32-bit system). Overflowing this counter requires 2⁵⁴ half-interrupts on a given CPU without that CPU ever going idle. If a half-interrupt happened every microsecond, it would take 570 years of runtime to overflow this counter, which is currently believed to be an acceptably long time.
6. Linux systems can have thousands of CPUs running a single Linux kernel in a single shared-memory environment. RCU must therefore pay close attention to high-end scalability.

This last parallelism fact of life means that RCU must pay special attention to the preceding facts of life. The idea that Linux might scale to systems with thousands of CPUs would have been met with some skepticism in the 1990s, but these requirements would have otherwise have been unsurprising, even in the early 1990s.

Quality-of-implementation requirements

These sections list quality-of-implementation requirements. Although an RCU implementation that ignores these requirements could still be used, it would likely be subject to limitations that would make it inappropriate for industrial-strength production use. Classes of quality-of-implementation requirements are as follows:

1. Specialization
2. Performance and scalability
3. Composability
4. Corner cases

These classes are covered in the following sections.

Specialization

RCU is and always has been intended primarily for read-mostly situations, as illustrated by the following figure. This means that RCU's read-side primitives are optimized, often at the expense of its update-side primitives.

This focus on read-mostly situations means that RCU must interoperate with other synchronization primitives. For example, the add_gp() and remove_gp_synchronous() examples discussed earlier use RCU to protect readers and locking to coordinate updaters. However, the need extends much farther, requiring that a variety of synchronization primitives be legal within RCU read-side critical sections, including spinlocks, sequence locks, atomic operations, reference counters, and memory barriers.

It often comes as a surprise that many algorithms do not require a consistent view of data, but many can function in that mode, with network routing being the poster child. Internet routing algorithms take significant time to propagate updates, so that by the time an update arrives at a given system, that system has been sending network traffic the wrong way for a considerable length of time. Having a few threads continue to send traffic the wrong way for a few more milliseconds is clearly not a problem: In the worst case, TCP retransmissions will eventually get the data where it needs to go. In general, when tracking the state of the universe outside of the computer, some level of inconsistency must be tolerated due to speed-of-light delays if nothing else.

Furthermore, uncertainty about external state is inherent in many cases. For example, a pair of veterinarians might use heartbeat to determine whether or not a given cat was alive. But how long should they wait after the last heartbeat to decide that the cat is in fact dead? Waiting less than 400 milliseconds makes no sense because this would mean that a relaxed cat would be considered to cycle between death and life more than 100 times per minute. Moreover, just as with human beings, a cat's heart might stop for some period of time, so the exact wait period is a judgment call. One of our pair of veterinarians might wait 30 seconds before pronouncing the cat dead, while the other might insist on waiting a full minute. The two veterinarians would then disagree on the state of the cat during the final 30 seconds of the minute following the last heartbeat.

Interestingly enough, this same situation applies to hardware. When push comes to shove, how do we tell whether or not some external server has failed? We send messages to it periodically, and declare it failed if we don't receive a response within a given period of time. Policy decisions can usually tolerate short periods of inconsistency. The policy was decided some time ago, and is only now being put into effect, so a few milliseconds of delay is normally inconsequential.

However, there are algorithms that absolutely must see consistent data. For example, the translation between a user-level System V semaphore ID to the corresponding in-kernel data structure is protected by RCU, but it is absolutely forbidden to update a semaphore that has just been removed. In the Linux kernel, this need for consistency is accommodated by acquiring spinlocks located in the in-kernel data structure from within the RCU read-side critical section, and this is indicated by the green box in the figure above. Many other techniques may be used, and are in fact used within the Linux kernel.

In short, RCU is not required to maintain consistency, and other mechanisms may be used in concert with RCU when consistency is required. RCU's specialization allows it to do its job extremely well, and its ability to interoperate with other synchronization mechanisms allows the right mix of synchronization tools to be used for a given job.

Performance and scalability

Energy efficiency is a critical component of performance today, and Linux-kernel RCU implementations must therefore avoid unnecessarily awakening idle CPUs. I cannot claim that this requirement was premeditated. In fact, I learned of it during a telephone conversation in which I was given “frank and open” feedback on the importance of energy efficiency in battery-powered systems and on specific energy-efficiency shortcomings of the Linux-kernel RCU implementation. In my experience, the battery-powered embedded community will consider any unnecessary wakeups to be extremely unfriendly acts. So much so that mere Linux-kernel-mailing-list posts are insufficient to vent their ire.

Memory consumption is not particularly important in most situations, and it has become decreasingly so as memory sizes have expanded and memory costs have plummeted. However, as I learned from Matt Mackall's bloatwatch efforts, memory footprint is critically important on single-CPU systems with non-preemptible (CONFIG_PREEMPT=n) kernels, and thus tiny RCU was born. Josh Triplett has since taken over the small-memory banner with his Linux kernel tinification project, which resulted in SRCU becoming optional for those kernels not needing it.

The remaining performance requirements are, for the most part, unsurprising. For example, in keeping with RCU's read-side specialization, rcu_dereference() should have negligible overhead (for example, suppression of a few minor compiler optimizations). Similarly, in non-preemptible environments, rcu_read_lock() and rcu_read_unlock() should have exactly zero overhead.

In preemptible environments, in the case where the RCU read-side critical section was not preempted (as will be the case for the highest-priority realtime process), rcu_read_lock() and rcu_read_unlock() should have minimal overhead. In particular, they should not contain atomic read-modify-write operations, memory-barrier instructions, preemption disabling, interrupt disabling, or backward branches. However, in the case where the RCU read-side critical section was preempted, rcu_read_unlock() may acquire spinlocks and disable interrupts. This is why it is better to nest an RCU read-side critical section within a preempt-disable region than vice versa, at least in cases where that critical section is short enough to avoid unduly degrading realtime latencies.

The synchronize_rcu() grace-period-wait primitive is optimized for throughput. It may therefore incur several milliseconds of latency in addition to the duration of the longest RCU read-side critical section. On the other hand, multiple concurrent invocations of synchronize_rcu() are required to use batching optimizations so that they can be satisfied by a single underlying grace-period-wait operation. For example, in the Linux kernel, it is not unusual for a single grace-period-wait operation to serve more than 1,000 separate invocations of synchronize_rcu(), thus amortizing the per-invocation overhead down to nearly zero. However, the grace-period optimization is also required to avoid measurable degradation of realtime scheduling and interrupt latencies.

In some cases, the multi-millisecond synchronize_rcu() latencies are unacceptable. In these cases, synchronize_rcu_expedited() may be used instead, reducing the grace-period latency down to a few tens of microseconds on small systems, at least in cases where the RCU read-side critical sections are short. There are currently no special latency requirements for synchronize_rcu_expedited() on large systems, but, consistent with the empirical nature of the RCU specification, that is subject to change. However, there most definitely are scalability requirements: a storm of synchronize_rcu_expedited() invocations on 4096 CPUs should at least make reasonable forward progress. In return for its shorter latencies, synchronize_rcu_expedited() is permitted to impose modest degradation of realtime latency on non-idle online CPUs. That said, it will likely be necessary to take further steps to reduce this degradation, hopefully to roughly that of a scheduling-clock interrupt.

There are a number of situations where even synchronize_rcu_expedited()'s reduced grace-period latency is unacceptable. In these situations, the asynchronous call_rcu() can be used in place of synchronize_rcu() as follows:

 1 struct foo {
 2   int a;
 3   int b;
 4   struct rcu_head rh;
 5 };
 6 
 7 static void remove_gp_cb(struct rcu_head *rhp)
 8 {
 9   struct foo *p = container_of(rhp, struct foo, rh);
10 
11   kfree(p);
12 }
13 
14 bool remove_gp_asynchronous(void)
15 {
16   struct foo *p;
17 
18   spin_lock(&gp_lock);
19   p = rcu_access_pointer(gp);
20   if (!p) {
21     spin_unlock(&gp_lock);
22     return false;
23   }
24   rcu_assign_pointer(gp, NULL);
25   call_rcu(&p->rh, remove_gp_cb);
26   spin_unlock(&gp_lock);
27   return true;
28 }

A definition of struct foo is finally needed, and appears on lines 1-5. The function remove_gp_cb() is passed to call_rcu() on line 25, and will be invoked after the end of a subsequent grace period. This gets the same effect as remove_gp_synchronous(), but without forcing the updater to wait for a grace period to elapse. The call_rcu() function may be used in a number of situations where neither synchronize_rcu() nor synchronize_rcu_expedited() would be legal, including within preempt-disable code, local_bh_disable() code, interrupt-disable code, and interrupt handlers. However, even call_rcu() is illegal within NMI handlers. The callback function (remove_gp_cb() in this case) will be executed within the softirq (software interrupt) environment within the Linux kernel (either within a real softirq handler or under the protection of local_bh_disable()). In both the Linux kernel and in user space, it is bad practice to write an RCU callback function that takes too long. Long-running operations should be relegated to separate threads or (in the Linux kernel) workqueues.

However, all that remove_gp_cb() is doing is invoking kfree() on the data element. This is a common idiom, and is supported by kfree_rcu(), which allows “fire and forget” operation as shown below:

 1 struct foo {
 2   int a;
 3   int b;
 4   struct rcu_head rh;
 5 };
 6 
 7 bool remove_gp_faf(void)
 8 {
 9   struct foo *p;
10 
11   spin_lock(&gp_lock);
12   p = rcu_dereference(gp);
13   if (!p) {
14     spin_unlock(&gp_lock);
15     return false;
16   }
17   rcu_assign_pointer(gp, NULL);
18   kfree_rcu(p, rh);
19   spin_unlock(&gp_lock);
20   return true;
21 }

Note that remove_gp_faf() simply invokes kfree_rcu() and proceeds, without any need to pay any further attention to the subsequent grace period and kfree(). It is permissible to invoke kfree_rcu() from the same environments as for call_rcu(). Interestingly enough, DYNIX/ptx had the equivalents of call_rcu() and kfree_rcu(), but not synchronize_rcu(). This was due to the fact that RCU was not heavily used within DYNIX/ptx, so the very few places that needed something like synchronize_rcu() simply open-coded it.

But what if the updater must wait for the completion of code to be executed after the end of the grace period, but has other tasks that can be carried out in the meantime? The polling-style get_state_synchronize_rcu() and cond_synchronize_rcu() functions may be used for this purpose, as shown below:

 1 bool remove_gp_poll(void)
 2 {
 3   struct foo *p;
 4   unsigned long s;
 5 
 6   spin_lock(&gp_lock);
 7   p = rcu_access_pointer(gp);
 8   if (!p) {
 9     spin_unlock(&gp_lock);
10     return false;
11   }
12   rcu_assign_pointer(gp, NULL);
13   spin_unlock(&gp_lock);
14   s = get_state_synchronize_rcu();
15   do_something_while_waiting();
16   cond_synchronize_rcu(s);
17   kfree(p);
18   return true;
19 }

On line 14, get_state_synchronize_rcu() obtains a “cookie” from RCU, then line 15 carries out other tasks, and finally, line 16 returns immediately if a grace period has elapsed in the meantime, but otherwise waits as required. The need for get_state_synchronize_rcu and cond_synchronize_rcu() has appeared quite recently, so it is too early to tell whether they will stand the test of time.

RCU thus provides a range of tools to allow updaters to strike the required tradeoff between latency, flexibility and CPU overhead.

Composability

Composability has received much attention in recent years, perhaps in part due to the collision of multicore hardware with object-oriented techniques designed in single-threaded environments for single-threaded use. And, in theory, RCU read-side critical sections may be composed, and in fact may be nested arbitrarily deeply. In practice, as with all real-world implementations of composable constructs, there are limitations.

Implementations of RCU for which rcu_read_lock() and rcu_read_unlock() generate no code, such as Linux-kernel RCU when CONFIG_PREEMPT=n, can be nested arbitrarily deeply. After all, there is no overhead. Except that if all these instances of rcu_read_lock() and rcu_read_unlock() are visible to the compiler, compilation will eventually fail due to exhausting memory, mass storage, or user patience, whichever comes first. If the nesting is not visible to the compiler, as is the case with mutually recursive functions each in its own translation unit, stack overflow will result. If the nesting takes the form of loops, either the control variable will overflow or (in the Linux kernel) you will get an RCU CPU stall warning. Nevertheless, this class of RCU implementations is one of the most composable constructs in existence.

RCU implementations that explicitly track nesting depth are limited by the nesting-depth counter. For example, the Linux kernel's preemptible RCU limits nesting to INT_MAX. This should suffice for almost all practical purposes. That said, a consecutive pair of RCU read-side critical sections between which there is an operation that waits for a grace period cannot be enclosed in another RCU read-side critical section. This is because it is not legal to wait for a grace period within an RCU read-side critical section: to do so would result either in deadlock or in RCU implicitly splitting the enclosing RCU read-side critical section, neither of which is conducive to a long-lived and prosperous kernel.

In short, although RCU read-side critical sections are highly composable, care is required in some situations, just as is the case for any other composable synchronization mechanism.

Corner cases

A given RCU workload might have an endless and intense stream of RCU read-side critical sections, perhaps even so intense that there was never a point in time during which there was not at least one RCU read-side critical section in flight. RCU cannot allow this situation to block grace periods: as long as all the RCU read-side critical sections are finite, grace periods must also be finite.

That said, preemptible RCU implementations could potentially result in RCU read-side critical sections being preempted for long durations, which has the effect of creating a long-duration RCU read-side critical section. This situation can arise only in heavily loaded systems, but systems using realtime priorities are of course more vulnerable. Therefore, RCU priority boosting is provided to help deal with this case. That said, the exact requirements on RCU priority boosting will likely evolve as more experience accumulates.

Other workloads might have very high update rates. Although one can argue that such workloads should instead use something other than RCU, the fact remains that RCU must handle such workloads gracefully. This requirement is another factor driving batching of grace periods, but it is also the driving force behind the checks for large numbers of queued RCU callbacks in the call_rcu() code path. Finally, high update rates should not delay RCU read-side critical sections, although some read-side delays can occur when using synchronize_rcu_expedited(), courtesy of this function's use of try_stop_cpus(). (In the future, synchronize_rcu_expedited() will be converted to use lighter-weight inter-processor interrupts (IPIs), but this will still disturb readers, though to a much smaller degree.)

Although all three of these corner cases were understood in the early 1990s, a simple user-level test consisting of close(open(path)) in a tight loop in the early 2000s suddenly provided a much deeper appreciation of the high-update-rate corner case. This test also motivated addition of some RCU code to react to high update rates, for example, if a given CPU finds itself with more than 10,000 RCU callbacks queued, it will cause RCU to take evasive action by more aggressively starting grace periods and more aggressively forcing completion of grace-period processing. This evasive action causes the grace period to complete more quickly, but at the cost of restricting RCU's batching optimizations, thus increasing the CPU overhead incurred by that grace period.

Software-engineering requirements

Between Murphy's Law and “to err is human”, it is necessary to guard against mishaps and misuse:

1. It is all too easy to forget to use rcu_read_lock() everywhere that it is needed, so kernels built with CONFIG_PROVE_RCU=y will complain if rcu_dereference() is used outside of an RCU read-side critical section. Update-side code can use rcu_dereference_protected(), which takes a lockdep expression to indicate what is providing the protection. If the indicated protection is not provided, a lockdep "splat" (a warning and traceback) is emitted.

   Code shared between readers and updaters can use rcu_dereference_check(), which also takes a lockdep expression, and emits a lockdep splat if neither rcu_read_lock() nor the indicated protection is in place. In addition, rcu_dereference_raw() is used in those (hopefully rare) cases where the required protection cannot be easily described. Finally, rcu_read_lock_held() is provided to allow a function to verify that it has been invoked within an RCU read-side critical section. I was made aware of this set of requirements shortly after Thomas Gleixner audited a number of RCU uses.

2. A given function might wish to check for RCU-related preconditions upon entry, before using any other RCU API. The rcu_lockdep_assert() does this job, asserting the expression in kernels having lockdep enabled and doing nothing otherwise.
3. It is also easy to forget to use rcu_assign_pointer() and rcu_dereference(), perhaps (incorrectly) substituting a simple assignment. To catch this sort of error, a given RCU-protected pointer may be tagged with __rcu, after which running sparse with CONFIG_SPARSE_RCU_POINTER=y will complain about simple-assignment accesses to that pointer. Arnd Bergmann made me aware of this requirement, and also supplied the needed patch series.
4. Kernels built with CONFIG_DEBUG_OBJECTS_RCU_HEAD=y will splat if a data element is passed to call_rcu() twice in a row, without a grace period in between. (This error is similar to a double free.) The corresponding rcu_head structures that are dynamically allocated are automatically tracked, but rcu_head structures allocated on the stack must be initialized with init_rcu_head_on_stack() and cleaned up with destroy_rcu_head_on_stack(). Similarly, statically allocated non-stack rcu_head structures must be initialized with init_rcu_head() and cleaned up with destroy_rcu_head(). Mathieu Desnoyers made me aware of this requirement, and also supplied the needed patch.
5. An infinite loop in an RCU read-side critical section will eventually trigger an RCU CPU stall-warning splat. However, RCU is not obligated to produce this splat unless there is a grace period waiting on that particular RCU read-side critical section. This requirement made itself known in the early 1990s, pretty much the first time that it was necessary to debug a CPU stall.
6. Although it would be very good to detect pointers leaking out of RCU read-side critical sections, there is currently no good way of doing this. One complication is the need to distinguish between pointers leaking and pointers that have been handed off from RCU to some other synchronization mechanism, for example, reference counting.
7. In kernels built with CONFIG_RCU_TRACE=y, RCU-related information is provided via both debugfs and event tracing.
8. Open-coded use of rcu_assign_pointer() and rcu_dereference() to create typical linked data structures can be surprisingly error-prone. Therefore, RCU-protected linked lists and, more recently, RCU-protected hash tables are available. Many other special-purpose RCU-protected data structures are available in the Linux kernel and the user-space RCU library.
9. Some linked structures are created at compile time, but still require __rcu checking. The RCU_POINTER_INITIALIZER() macro serves this purpose.
10. It is not necessary to use rcu_assign_pointer() when creating linked structures that are to be published via a single external pointer. The RCU_INIT_POINTER() macro is provided for this task and also for assigning NULL pointers at runtime.

This is not a hard-and-fast list: RCU's diagnostic capabilities will continue to be guided by the number and type of usage bugs found in real-world RCU usage.

The final installment in this series will cover issues specific to the Linux kernel and the future of RCU.

Answers to the quick quizzes

Quick Quiz 11: What about sleeping locks?

Answer: These are forbidden within Linux-kernel RCU read-side critical sections because it is not legal to place a quiescent state (in this case, voluntary context switch) within an RCU read-side critical section. However, sleeping locks may be used within user-space RCU read-side critical sections, and also within Linux-kernel sleepable RCU (SRCU) read-side critical sections. In addition, the -rt patchset turns spinlocks into a sleeping lock so that the corresponding critical sections can be preempted, which also means that these sleeplockified spinlocks (but not other sleeping locks!) may be acquired within -rt-Linux-kernel RCU read-side critical sections.

Note that it is legal for a normal RCU read-side critical section to conditionally acquire a sleeping lock (as in mutex_trylock()), but only as long as it does not loop indefinitely attempting to conditionally acquire that sleeping lock. The key point is that things like mutex_trylock() either return with the mutex held, or return an error indication if the mutex was not immediately available. Either way, mutex_trylock() returns immediately without sleeping.

Back to Quick Quiz 11.

Quick Quiz 12: Why does line 19 use rcu_access_pointer()? After all, call_rcu() on line 25 stores into the structure, which would interact badly with concurrent insertions. Doesn't this mean that rcu_dereference() is required?

Answer: Presumably the ->gp_lock acquired on line 18 excludes any changes, including any insertions that rcu_dereference() would protect against. Therefore, any insertions will be delayed until after ->gp_lock is released on line 25, which in turn means that rcu_access_pointer() suffices.

Back to Quick Quiz 12.

Quick Quiz 13: Earlier it was claimed that call_rcu() and kfree_rcu() allowed updaters to avoid being blocked by readers. But how can that be correct, given that the invocation of the callback and the freeing of the memory (respectively) must still wait for a grace period to elapse?

Answer: We could define things this way, but keep in mind that this sort of definition would say that updates in garbage-collected languages cannot complete until the next time the garbage collector runs, which does not seem at all reasonable. The key point is that in most cases, an updater using either call_rcu() or kfree_rcu() can proceed to the next update as soon as it has invoked call_rcu() or kfree_rcu(), without having to wait for a subsequent grace period.

Back to Quick Quiz 13.

Comments (6 posted)