Leading items
Welcome to the LWN.net Weekly Edition for July 18, 2019
This edition contains the following feature content:
- What's coming in Python 3.8: a look at the new features in the Python release coming in October.
- Fedora, GNOME Software, and snap: removing the snap plugin from GNOME Software in Fedora 31.
- Who's afraid of a big bad optimizing compiler?: a summary of potential pitfalls from compilers for developers of the kernel and other concurrent code bases.
- Bcachefs gets closer: a new filesystem, with origins in the bcache caching layer, takes a step toward the mainline.
- 5.3 Merge window, part 1: a look at what has gone into the mainline for 5.3 so far.
- The third Operating-System-Directed
Power-Management summit — the completion of the set of contributed
reports from OSPM:
This week's edition also includes these inner pages:
- Brief items: Brief news items from throughout the community.
- Announcements: Newsletters, conferences, security updates, patches, and more.
Please enjoy this week's edition, and, as always, thank you for supporting LWN.net.
What's coming in Python 3.8
The Python 3.8 beta cycle is already underway, with Python 3.8.0b1 released on June 4, followed by the second beta on July 4. That means that Python 3.8 is feature complete at this point, which makes it a good time to see what will be part of it when the final release is made. That is currently scheduled for October, so users don't have that long to wait to start using those new features.
The walrus operator
The headline feature for Python 3.8 is also its most contentious. The process for deciding on PEP 572 ("Assignment Expressions") was a rather bumpy ride that eventually resulted in a new governance model for the language. That model meant that a new steering council would replace longtime benevolent dictator for life (BDFL) Guido van Rossum for decision-making, after Van Rossum stepped down in part due to the "PEP 572 mess".
Out of that came a new operator, however, that is often called the "walrus operator" due to its visual appearance. Using ":=" in an if or while statement allows assigning a value to a variable while testing it. It is intended to simplify things like multiple-pattern matches and the so-called loop and a half, so:
m = re.match(p1, line)
if m:
return m.group(1)
else:
m = re.match(p2, line)
if m:
return m.group(2)
else:
m = re.match(p3, line)
...
becomes:
if m := re.match(p1, line):
return m.group(1)
elif m := re.match(p2, line):
return m.group(2)
elif m := re.match(p3, line):
...
And a loop over a non-iterable
object, such as:
ent = obj.next_entry()
while ent:
... # process ent
ent = obj.next_entry()
can become:
while ent := obj.next_entry():
... # process ent
These and other uses (e.g. in list and dict comprehensions)
help make the intent of the programmer clearer. It is a feature that many
other languages have, but Python has, of course, gone without it for nearly
30 years at this point. In the end, it is actually a fairly small change
for all of the uproar it caused.
Debug support for f-strings
The f-strings (or formatted strings) added into Python 3.6 are quite useful, but Pythonistas often found that they were using them the same way in debugging output. So Eric V. Smith proposed some additional syntax for f-strings to help with debugging output. The original idea came from Larry Hastings and the syntax has gone through some changes, as documented in two feature-request issues at bugs.python.org. The end result is that instead of the somewhat cumbersome:
print(f'foo={foo} bar={bar}')
Python 3.8 programmers will be able to do:
print(f'{foo=} {bar=}')
In both cases, the output will be as follows:
>>> foo = 42
>>> bar = 'answer ...'
>>> print(f'{foo=} {bar=}')
foo=42 bar=answer ...
Beyond that, some modifiers can be used to change the output, "!s" uses the str() representation, rather than the default repr() value and "!f" will be available to access formatting controls. They can be used as follows:
>>> import datetime
>>> now = datetime.datetime.now()
>>> print(f'{now=} {now=!s}')
now=datetime.datetime(2019, 7, 16, 16, 58, 0, 680222) now=2019-07-16 16:58:00.680222
>>> import math
>>> print(f'{math.pi=!f:.2f}')
math.pi=3.14
One more useful feature, though it is mostly cosmetic (as is the whole feature in some sense), is the preservation of spaces in the f-string "expression":
>>> a = 37
>>> print(f'{a = }, {a = }')
a = 37, a = 37
The upshot of all of that is that users will be able to pretty-print their
debugging, log, and other messages more easily. It may seem somewhat
trivial in the grand scheme, but it is sure to see a lot of use. F-strings
have completely replaced other string interpolation mechanisms for this
Python programmer and I suspect I am far from the only one.
Positional-only parameters
Another change for 3.8 affords pure-Python functions the same options for parameters that those implemented in C already have. PEP 570 ("Python Positional-Only Parameters") introduces new syntax that can be used in function definitions to denote positional-only arguments—parameters that cannot be passed as keyword arguments. For example, the builtin pow() function must be called with bare arguments:
>>> pow(2, 3)
8
>>> pow(x=2, y=3)
...
TypeError: pow() takes no keyword arguments
But if pow() were a pure-Python function, as an alternative Python implementation might want, there is no easy way to force that behavior. A function could accept only *args and **kwargs, then enforce the condition that kwargs is empty, but that obscures what the function is trying to do. There are other reasons described in the PEP, but many, perhaps most, are not things that the majority of Python programmers will encounter very often.
Those that do, however, will probably be pleased that they can write a pure-Python pow() function, which will behave the same as the builtin, as follows:
def pow(x, y, z=None, /):
r = x**y
if z is not None:
r %= z
return r
The "/" denotes the end of the positional-only parameters in an
argument list. The idea is similar to the "*" that can be used in
an argument list to delimit keyword-only arguments (those that must be
passed as keyword=...), which was specified in PEP 3102
("Keyword-Only Arguments"). So a declaration like:
def fun(a, b, /, c, d, *, e, f):
...
Says that a and b must be passed positionally, c
and d can be passed as either positional or by keyword, and
e and f must be passed by keyword. So:
fun(1, 2, 3, 4, e=5, f=6) # legal
fun(1, 2, 3, d=4, e=5, f=6) # legal
fun(a=1, b=2, c=3, d=4, e=5, f=6) # illegal
It seems likely that most Python programmers have not encountered
"*"; "/" encounter rates are likely to be similar.
A movable __pycache__
The __pycache__ directory is created by the Python 3 interpreter (starting with 3.2) to hold .pyc files. Those files contain the byte code that is cached after the interpreter compiles .py files. Earlier Python versions simply dropped the .pyc file next to its .py counterpart, but PEP 3147 ("PYC Repository Directories") changed that.
The intent was to support multiple installed versions of Python, along with the possibility that some of those might not be CPython at all (e.g. PyPy). So, for example, standard library files could be compiled and cached by each Python version as needed. Each would write a file of the form "name.interp-version.pyc" into __pycache__. So, for example, on my Fedora system, foo.py will be compiled when it is first used and __pycache__/foo.cpython-37.pyc will be created.
That's great from an efficiency standpoint, but may not be optimal for other reasons. Carl Meyer filed a feature request asking for an environment variable to tell Python where to find (and put) these cache files. He was running into problems with permissions in his system and was disabling cache files as a result. So, he added a PYTHONPYCACHEPREFIX environment variable (also accessible via the -X pycache_prefix=PATH command-line flag) to point the interpreter elsewhere for storing those files.
And more
Python 3.8 will add a faster calling convention for C extensions based on the existing "fastcall" convention that is used internally by CPython. It is exposed in experimental fashion (i.e. names prefixed with underscores) for Python 3.8, but is expected to be finalized and fully released in 3.9. The configuration handling in the interpreter has also been cleaned up so that the language can be more easily embedded into other programs without having environment variables and other configuration mechanisms interfere with the installed system Python.
There are new features in various standard library modules as well. For example, the ast module for processing Python abstract syntax trees has new features, as do statistics and typing. And on and on. The draft "What's New In Python 3.8" document has lots more information on these changes and many others. It is an excellent reference for what's coming in a few months.
The status of PEP 594 ("Removing dead batteries from the standard library") is not entirely clear, at least to me. The idea of removing old Python standard library modules has been in the works for a while, the PEP was proposed in May, and it was extensively discussed after that. Removing unloved standard library modules is not particularly controversial—at least in the abstract—until your favorite module is targeted, anyway.
The steering council has not made a pronouncement on the PEP, nor has it delegated to a so-called BDFL-delegate. But the PEP is clear that even if it were accepted, the changes for 3.8 would be minimal. Some of the modules may start raising the PendingDeprecationWarning exception (many already do since they have been deemed deprecated for some time), but the main change will be in the documentation. All of the 30 or so modules will be documented as being on their way out, but the actual removal will not happen until the 3.10 release—three or so years from now.
The future Python release cadence is still under discussion; currently Python 3.9 is scheduled for a June 2020 release, much sooner than usual. Python is on an 18-month cycle, but that is proposed to change to nine months (or perhaps a year). In any case, we can be sure that Python 3.8 will be here with the features above (and plenty more) sometime before Halloween on October 31.
Fedora, GNOME Software, and snap
A question about the future of package distribution is at the heart of a disagreement about the snap plugin for the GNOME Software application in Fedora. In a Fedora devel mailing list thread, Richard Hughes raised multiple issues about the plugin and the direction that he sees Canonical taking with snaps for Ubuntu. He plans to remove support for the plugin for GNOME Software in Fedora 31.
There are currently two major players for cross-distribution application bundles these days: snaps, which were developed by Canonical for Ubuntu and the Snap Store, and Flatpak, which was developed by Alexander Larsson of Red Hat as part of freedesktop.org. Both systems are available for multiple Linux distributions. They are meant to give an "app-like" experience, where users simply install an application, which comes with any dependencies it has that are not provided by the snap or Flatpak runtime.
The GNOME Software application has a snap plugin that, when enabled, supports the distribution, installation, and management of snaps. The Fedora project currently provides the snap plugin as a package in Fedora 30, though it is not installed by default. Hughes is the Fedora maintainer for the plugin; he announced his intention to disable the plugin since, he says, he was told that Canonical was not going to be installing GNOME Software in the next Ubuntu Long Term Support (LTS) release.
Hughes is also concerned about the stability of the snap plugin, noting that
"the existing snap plugin is not very well tested and I don't want
to be the one responsible when it breaks
". Additionally, Hughes
outlined a
few other areas of concern that have led him to plan to drop support
for the snap plugin in Fedora.
The other issue that Hughes raised is that in his view, enabling the snap plugin would also enable the Snap Store, which would be a violation of Fedora rules for enabling access to non-free software (the same is true of enabling Flathub support, he said). He noted that he expects that the decision will be controversial and that there will be those that want it turned back on in GNOME Software. He suggested a path forward if there were developers interested in maintaining snap support for GNOME Software:
In a blog post, Hughes provided his views on the situation and the bigger picture. The post was of the form of an extended automotive analogy that took issue with companies that are not working toward enabling an open ecosystem supported and used by multiple parties. Overall, it was a thinly veiled swipe at Canonical.
Among those that disagreed with the decision was Fedora contributor Neal Gompa who disputed many of Hughes's assertions, including the claim that snaps are not sandboxed.
We've been working very hard upstream on improving this story for Fedora, and we've made tremendous progress.
Canonical responds
At the core of the issue of whether Fedora will or won't ship the snap plugin is whether or not Ubuntu will be moving away from GNOME Software and just use its own Snap Store by default for the next Ubuntu LTS release. It's a question that Canonical has not definitively answered, though it has stated that it plans to keep supporting the snap plugin for GNOME Software.
LWN contacted Canonical to ask about Hughes's claims. In an email, Will Cooke, desktop engineering director at Canonical, said that in the last week there have been several discussions at the company about the Snap Store. "To date, there has been no decision on this potential change, nor have any announcements been made to this effect," he said. "We remain committed to maintaining snap support in GNOME Software and ensuring users who wish to use snaps can do so regardless of their Linux distribution."
In the mailing list thread, Canonical developer Robert Ancell
emphasized that Canonical is committed to maintaining the GNOME Software
snap plugin. He also extended an offer of support to help Fedora
include the snap-plugin in a way that is stable. "We're happy for the snap
plugin to be built in a separate source package for Fedora if that's
necessary and we're obviously keen to see snapd-glib up to date in
Fedora
", Ancell wrote. "The
dependencies are fairly light so it should be quick to
update but let us know if there is anything we can do to make this
easier.
"
Gompa responded, wondering how the situation had deteriorated to the point where the plugin was seen by Hughes as being unstable. Rather than building a Fedora-specific source package, Gompa would prefer everything to be done upstream, and is hopeful for more communication to help identify any issues.
Flatpak vs. snap
Red Hat is a big supporter of Flatpak. The Fedora Silverblue distribution is designed with Flatpak as a core component, for example. In an interview with LWN, Fedora Project Leader Matthew Miller said that, in his view, Flatpak and snap can both happily coexist. "Obviously Red Hat's desktop team is heavily invested in Flatpak, and we also have members of the Fedora community who are very interested in snaps — and I include Canonical employees working on snap in that," he said.
Of concern to Miller is the source of snaps and in making sure that there are multiple developers and organizations that are producing snaps that are available via GNOME Software. Miller noted that the Fedora project is not just a producer of a base operating system, or just a desktop without apps, it also has a long history of contributors working on packaging end-user applications. "We have a project where Flatpaks in Fedora are actually automatically generated from our existing packages, and some Fedora developers are working on a plan for doing a similar thing with Snaps," Miller said. "We have a talk on that at our upcoming Flock conference and I'm looking forward to learning more."
Decision time
From a governance perspective, Miller explained that Fedora has a defined change process and it's ideally used for anything with a large impact. In Hughes's view, the snap plugin change would only have limited impact. Hughes said that the snap plugin was never shipped for Red Hat Enterprise Linux (RHEL) and it's not a feature that is installed by default for Fedora. The change would only impact a small number of people, he said, so it may not need a full-on change proposal. Fedora program manager Ben Cotton said that while a change proposal would be nice, it probably isn't needed; adding something to the Fedora 31 release notes should do.
Decisions on minor changes can be handled by Fedora maintainers. Miller noted that if Hughes feels like he can't reasonably maintain a feature, that's a judgement call. "Ultimately we do put a lot of trust in our maintainers, and I personally have a lot of trust for Richard here," Miller said. But Miller noted that currently it sounds like there is community interest in preserving the snap plugin and he thinks it's likely that someone will step up to do that. "This is still a developing conversation," he said.
From a user perspective, however, even if Fedora 31 disabled the snap plugin in GNOME Software, users could still download GNOME Software directly from upstream, which still has the plugin."Either the functionality will have a strong owner and support, in which case there will be no problem in Fedora, or else it'll become clear that it's not maintained in which case it will be dropped upstream as well," Miller explained.
The discussion is likely to continue for a while longer as different developers and community members make their voices heard on the topic. Fedora 31 is currently scheduled for release in October, with a beta freeze set for August, so there is still plenty of time for a final decision to be made.
Who's afraid of a big bad optimizing compiler?
This article was contributed by Jade Alglave, Will Deacon, Boqun Feng, David Howells, Daniel Lustig, Luc Maranget, Paul E. McKenney, Andrea Parri, Nicholas Piggin, Alan Stern, Akira Yokosawa, and Peter Zijlstra.When compiling Linux-kernel code that does a plain C-language load or store, as in "a=b", the C standard grants the compiler the right to assume that the affected variables are neither accessed nor modified by any other thread at the time of that load or store. The compiler is therefore permitted to carry out a large number of transformations, a couple of which were discussed in this ACCESS_ONCE() LWN article, and another of which is described in Dmitry Vyukov's KTSAN wiki page. However, our increasingly aggressive modern compilers produce increasingly surprising code optimizations. Some of these optimizations might be especially surprising to developers who assume that each plain C-language load or store will always result in an assembly-language load or store. Although this article is written for Linux kernel developers, many of these scenarios also apply to other concurrent code bases, keeping in mind that "concurrent code bases" also includes single-threaded code bases that use interrupts or signals.
The ongoing trend in compilers makes us wonder: "Just how afraid should we be?". The following sections should help answer this question:
- Load tearing
- Store tearing
- Load fusing
- Store fusing
- Code reordering
- Invented loads
- Invented stores
Quick quiz 1: But we shouldn't be afraid at all for things like on-stack or per-CPU variables, right?
Answer - Store-to-load transformations
- Dead-code elimination
- How real is all this?
This is followed by the ineludible answers to the quick quizzes.
Load tearing
Load tearing occurs when the compiler uses multiple load instructions for a single access. For example, the compiler could, in theory, compile the load from global_ptr on line 1 of the following code as a series of one-byte loads.
1 ptr = global_ptr; /* BUGGY if load tearing possible. */ 2 if (ptr != NULL && ptr < high_address) /* BUGGY!!! */ 3 do_low(ptr);If some other thread was concurrently setting global_ptr to NULL, the result might have all but one byte of the pointer set to zero, thus forming a "wild pointer". Stores using such a wild pointer could corrupt arbitrary regions of memory, resulting in rare and difficult-to-debug crashes.
Worse yet, on (say) an eight-bit system with 16-bit pointers, the compiler might have no choice but to use a pair of eight-bit instructions to access a given pointer. And even on today's 32-bit and 64-bit systems, a misaligned or too-large access could tear. Because the C standard must support all manner of systems, the standard cannot rule out load tearing in the general case.
Answer
Store tearing
Store tearing occurs when the compiler uses multiple store instructions for a single access. For example, one thread might store 0x12345678 to a four-byte integer variable at the same time as another thread stored 0xabcdef00. If the compiler used 16-bit stores for either access, the result might well be 0x1234ef00, which could come as quite a surprise to code loading from this integer. Nor is this a strictly theoretical issue. For example, there are CPUs that feature small immediate values, and on such CPUs, the compiler can be tempted to split a 64-bit store into two 32-bit stores in order to reduce the overhead of explicitly forming the 64-bit constant in a register, even on a 64-bit CPU. There are historical reports of this actually happening in the wild, but there is also a recent report. Note that this tearing can happen even on properly aligned and machine-word-sized accesses, and in this particular case, even for volatile stores. Some might argue that this behavior constitutes a bug in the compiler, but either way it illustrates the perceived value of store tearing from a compiler-writer viewpoint.
Of course, the compiler simply has no choice but to tear some stores in the general case, given the possibility of code using 64-bit integers running on a 32-bit system. But for properly aligned machine-sized stores, WRITE_ONCE() will prevent store tearing.
Load fusing
Load fusing occurs when the compiler uses the result of a prior load from a given variable instead of repeating the load. Not only is this sort of optimization just fine in single-threaded code, it is often just fine in multithreaded code. Unfortunately, the word "often" hides some truly annoying exceptions, including the one called out in the ACCESS_ONCE() article.
For example, suppose that a realtime system needs to invoke a function named do_something_quickly() repeatedly until the variable need_to_stop is set, and that the compiler can see that do_something_quickly() does not store to need_to_stop. One (unsafe) way to code this might look like:
1 while (!need_to_stop) /* BUGGY!!! */ 2 do_something_quickly();
The compiler might reasonably unroll this loop sixteen times in order to reduce the per-invocation overhead of the backwards branch at the end of the loop. Worse yet, because the compiler knows that do_something_quickly() does not store to need_to_stop, the compiler could quite reasonably decide to check this variable only once, resulting in the code shown below:
1 /* Optimized code */
2 if (!need_to_stop)
3 for (;;) {
4 do_something_quickly();
5 do_something_quickly();
6 do_something_quickly();
7 do_something_quickly();
8 do_something_quickly();
9 do_something_quickly();
10 do_something_quickly();
11 do_something_quickly();
12 do_something_quickly();
13 do_something_quickly();
14 do_something_quickly();
15 do_something_quickly();
16 do_something_quickly();
17 do_something_quickly();
18 do_something_quickly();
19 do_something_quickly();
20 }
Once entered, the loop on lines 3-20 will never stop, regardless of how many times some other thread stores a non-zero value to need_to_stop. The result will at best be disappointment, and might also include severe physical damage.
The compiler can fuse loads across surprisingly large spans of code. For example, in this code:
1 int *gp;
2
3 void t0(void)
4 {
5 WRITE_ONCE(gp, &myvar);
6 }
7
8 void t1(void)
9 {
10 p1 = gp; /* BUGGY!!! */
11 do_something(p1);
12 p2 = READ_ONCE(gp);
13 if (p2) {
14 do_something_else();
15 p3 = *gp; /* BUGGY!!! */
16 }
17 }
t0() and t1() run concurrently, and
do_something() and do_something_else() are inline functions.
Line 1 declares the pointer gp, which C initializes to
NULL by default.
At some point, line 5 of t0() stores a non-NULL
pointer to gp.
Meanwhile, t1() loads from gp three times on
lines 10, 12, and 15.
Given that line 13 finds that gp is non-NULL, one might
hope that the dereference on line 15 would be guaranteed never
to fault.
Unfortunately, the compiler is within its rights to fuse the reads on lines 10 and 15 which means that if line 10 loads NULL and line 12 loads &myvar, line 15 could dereference NULL, resulting in a fault. Note that the intervening READ_ONCE() does not prevent the other two loads from being fused, despite the fact that all three are loading from the same variable. It might seem that no real compiler would ever do this, but Will Deacon reports that this has actually happened in the Linux kernel.
Answer
Store fusing
Store fusing can occur when the compiler notices a pair of successive stores to a given variable with no intervening loads from that variable. In this case, the compiler is within its rights to omit the first store. This is never a problem in single-threaded code, and in fact it is usually the case that it is not a problem in correctly written concurrent code. After all, if the two stores are executed in quick succession, there is very little chance that some other thread could load the value from the first store.
However, there are exceptions, for example as shown below:
1 void shut_it_down(void)
2 {
3 status = SHUTTING_DOWN; /* BUGGY!!! */
4 start_shutdown();
5 while (!other_task_ready) /* BUGGY!!! */
6 continue;
7 finish_shutdown();
8 status = SHUT_DOWN; /* BUGGY!!! */
9 do_something_else();
10 }
11
12 void work_until_shut_down(void)
13 {
14 while (status != SHUTTING_DOWN) /* BUGGY!!! */
15 do_more_work();
16 other_task_ready = 1; /* BUGGY!!! */
17 }
The function shut_it_down() stores to the shared variable status on lines 3 and 8. Assuming that neither start_shutdown() nor finish_shutdown() access status, the compiler could reasonably remove the store to status on line 3. Unfortunately, this would mean that work_until_shut_down() would never exit its loop spanning lines 14 and 15, and thus would never set other_task_ready, which would in turn mean that shut_it_down() would never exit its loop spanning lines 5 and 6, even if the compiler chooses not to fuse the successive loads from other_task_ready on line 5. Although WRITE_ONCE() prevents store fusing, smp_store_release() (or stronger) is often preferable, to ensure that other changes made before the store will be visible to other threads that see the store.
And there are other problems with that code, including code reordering.
Code reordering
Code reordering is a common compilation technique used to combine common subexpressions, reduce register pressure, and improve utilization of the many functional units available on modern superscalar microprocessors. It is also another reason why the code above is buggy. For example, suppose that the do_more_work() function on line 15 does not access other_task_ready. Then the compiler would be within its rights to move the assignment to other_task_ready on line 16 to precede line 14, which might be a great disappointment for anyone hoping that the last call to do_more_work() on line 15 happens before the call to finish_shutdown() on line 7.
It might seem futile to prevent the compiler from changing the order of accesses in cases where the underlying hardware is free to reorder them. For example, even on a single-CPU machine, what would happen if the hardware reorders two accesses and then an interrupt occurs right in the middle? What values would the interrupt handler see?
As it turns out, this isn't a problem. Modern machines have "exact exceptions" and "exact interrupts", meaning that any interrupt or exception will appear to have happened at a specific place in the instruction stream. Consequently, the handler will see the effect of all prior instructions, but won't see the effect of any subsequent instructions. READ_ONCE(), WRITE_ONCE(), and barrier() can therefore be used to control communication between interrupted code and interrupt handlers, independent of any reordering carried out by the underlying hardware. That said, should you write user-space code, the various standards committees would prefer that you use atomics or variables of type sig_atomic_t instead of READ_ONCE() and WRITE_ONCE().
However, when interacting with some other CPU, stronger primitives are required, such as smp_load_acquire() and smp_store_release().
Invented loads
Invented loads are illustrated by the code below, in which the compiler has optimized away a temporary variable from the code shown in the load-tearing example above.
1 /* Optimized code */ 2 if (global_ptr != NULL && 3 global_ptr < high_address) 4 do_low(global_ptr);
Answer
Invented loads can also be a performance hazard. These hazards can occur when a load of variable in a "hot" cacheline is hoisted out of an if statement. These hoisting optimizations are not uncommon, and can cause significant increases in cache misses, and thus significant degradation of both performance and scalability.
Avoid invented loads by using READ_ONCE().
Invented stores
Invented stores can occur in a number of situations. For example, a compiler emitting code for work_until_shut_down() in the store-fusing example above might notice that other_task_ready is stored to on line 16 and is not accessed by do_more_work(). If do_more_work() was a complex inline function, it might be necessary to do a register spill, in which case one attractive place to use for temporary storage is other_task_ready. After all, there are no accesses to it, so what is the harm?
Of course, a non-zero store to this variable at just the wrong time would result in the while loop on line 5 terminating prematurely, again allowing finish_shutdown() to run concurrently with do_more_work(). Given that the entire point of this while appears to be to prevent such concurrency, this is not a good thing.
Using a stored-to variable as a temporary might seem outlandish, and we are not aware of any compilers that actually invent stores, but invented stores really are permitted by the standard. Nevertheless, readers might be justified in wanting a less outlandish example, which is duly provided below:
1 if (condition) 2 a = 1; /* BUGGY!!! */ 3 else 4 do_a_bunch_of_stuff();
A compiler emitting code for this example might know that the value of a is initially zero, which might tempt the compiler to optimize away one branch by transforming this code to something like:
1 /* Optimized code */
2 a = 1;
3 if (!condition) {
4 a = 0;
5 do_a_bunch_of_stuff();
6 }
Answer
Pre-C11 compilers could invent stores to unrelated variables that happened to be adjacent to written-to variables (see Section 4.2 of Hans Boehm's classic Threads cannot be implemented as a library). This variant of invented stores has been outlawed by the C11 prohibition against compiler optimizations that create data races.
Unfortunately, there is an exception to this rule: if there is a later plain store without some sort of ordering directive beforehand, then a data race involving an invented store necessarily implies that there was already a data race involving that later plain store. In this case, the compiler believes that it is not introducing a data race, but rather expanding on an already-existing data race. And the compiler is OK with this, even if your code is not. For example:
1 struct foo {
2 short a;
3 char b;
4 char c;
5 };
6
7 void do_something(struct foo *fp)
8 {
9 fp->a = 0x1234;
10 fp->b = 0x56;
11 do_something_else();
12 fp->c = 0x42;
13 }
If the definition of do_something_else() is visible to the compiler, and if it contains no ordering directives like barrier() or stronger, then the developer's write to fp->c tells the compiler that there are no concurrent reads or writes to that field, whether that was the developer's intention or not. The compiler would then be within its rights to do the following optimization (assuming a big-endian system):
1 struct foo {
2 short a;
3 char b;
4 char c;
5 };
6
7 void do_something(struct foo *fp)
8 {
9 *(long *)fp = 0x123456ff;
10 do_something_else();
11 fp->c = 0x42;
12 }
The momentary appearance of 0xff might come as quite a surprise to any concurrent loads from fp->c. Please note that this is not a theoretical transformation: A later store to a variable is taken as permission to clobber that variable. In addition, older compilers can and do invent stores to unrelated variables, even without the provocation of a later plain C-language store to such an unrelated variable. Use barrier() or WRITE_ONCE() to avoid all of these types of invented stores.
Store-to-load transformations
Store-to-load transformations can occur when the compiler notices that a plain C-language store might not actually change the value in memory. For example, consider this code:
1 int r1, x, y;
2
3 void cpu1(void)
4 {
5 WRITE_ONCE(y, 1);
6 smp_mb();
7 WRITE_ONCE(x, 1);
8 }
9
10 void cpu2(void)
11 {
12 r1 = READ_ONCE(x);
13 if (r1 == 1)
14 y = 0; // BUGGY!!!
15 }
Here CPU 1 executes cpu1(), which uses WRITE_ONCE() to store the value one to each of y and then x, separated by a full memory barrier. CPU 2 executes cpu2(), which uses READ_ONCE() to load x, and only if the result is 1, line 14 does a plain store of zero to y. One would expect that if r1 ends up with the value one, that the final value of y must necessarily be zero.
Unfortunately, the compiler is within its rights to transform line 14 into the load-compare-store sequence shown on lines 14 and 15 below:
1 int r1, x, y;
2
3 void cpu1(void)
4 {
5 WRITE_ONCE(y, 1);
6 smp_mb();
7 WRITE_ONCE(x, 1);
8 }
9
10 void cpu2(void)
11 {
12 r1 = READ_ONCE(x);
13 if (r1 == 1)
14 if (y != 0)
15 y = 0;
16 }
Given this code, CPU 2 may reorder the load of y on line 14 before the READ_ONCE. If it does so, it might observe the original zero value of y and therefore skip the store on line 15. Thus y could indeed end up containing one.
Why would the compiler do such a thing? Please understand that to the best of our knowledge, this transformation is strictly theoretical. However, it does not take too much imagination to see how this might occur given feedback-driven optimization. So if you want your store to remain a store, for current and any future compilers, use WRITE_ONCE() or stronger.
Dead-code elimination
Dead-code elimination can occur when the compiler notices that the value from a load is never used, or when a variable is stored to, but never loaded from. This can of course eliminate an access to a shared variable, which can in turn defeat a memory-ordering primitive, which could cause your concurrent code to act in surprising ways. Experience thus far indicates that relatively few such surprises will be at all pleasant. Elimination of store-only variables is especially dangerous in cases where external code locates the variable via symbol tables; the compiler is necessarily ignorant of such external-code accesses, and might thus eliminate a variable that the external code relies on.
Reliable concurrent code clearly needs a way to cause the compiler to preserve the number, order, and type of important accesses to shared memory, which is why the Linux kernel provides READ_ONCE(), WRITE_ONCE(), barrier(), and a wide variety of memory barriers and atomic read-modify-write operations.
How real is all this?
Some of the transformations called out in the preceding sections are more likely to actually occur than are others.
| Occurs in the Wild? | |
|---|---|
| Transformation | (Properly Aligned, Machine-Word Sized) |
| Load Tearing | Yes |
| Store Tearing | Yes, for constants (to be fixed?) |
| Load Fusing | Yes |
| Store Fusing | Yes |
| Code Reordering | Yes |
| Invented Loads | Yes |
| Invented Stores | In some cases |
| Store-to-Load Transformations | Unknown |
| Dead-Code Elimination | Yes |
So what is a Linux kernel developer to do? There is a range of possibilities, each of which applies READ_ONCE() and WRITE_ONCE() in different situations:
- Never.
- For any access to any shared variable for which there is a possibility of a data race, and for which it can be clearly shown that specific compiler optimizations could result in bugs.
- For any access to a shared variable for which there is a possibility of a data race for at least one of those accesses.
- For all accesses to all shared variables.
There is without doubt some code somewhere in the Linux kernel corresponding to each of these possibilities. However, developers and maintainers opting for one of the first two possibilities are taking on the responsibility of ensuring that new releases of the compiler won't break their code. For these developers and maintainers, a significant level of fear of the big bad optimizing compiler is a very healthy thing, and the rest of us should hope that they continue to maintain an appropriate level of fear.
Answer
Quick quiz 8:
Given the risk, why not simply require that all accesses to
shared variables use READ_ONCE() and
WRITE_ONCE()?
Answer
On the other hand, developers and maintainers who instead opt for one of the last two possibilities need not fear the big bad optimizing compiler, or at least they need not fear it quite so much. However, they could benefit from a tool that determines when READ_ONCE() and WRITE_ONCE() (or stronger) are needed to defend not just against present-day optimizing compilers, but also the bigger and badder optimizing compilers that the future will bring. The next article in this series describes a recent change to the Linux kernel memory model that does just that.
Acknowledgments
We owe thanks to a surprisingly large number of compiler writers and members of the C and C++ standards committees who introduced us to some of the things a big bad optimizing compiler can do, and to Junchang Wang, SeongJae Park, and Slavomir Kaslev for their help making an earlier draft of this material human-readable. We are also grateful to Mark Figley and Kara Todd for their support of this effort.
Answers to quick quizzes
Quick quiz 1: But we shouldn't be afraid at all for things like on-stack or per-CPU variables, right?
Answer: Although on-stack and per-CPU variables are often guaranteed to be untouched by other CPUs and tasks, the kernel really does allow them to be concurrently accessed in many cases. You do have to go out of your way to make this happen, say by explicitly passing the address of such a variable to another thread, but it's certainly not impossible.
For example, the _wait_rcu_gp() macro uses an on-stack __rs_array[] array of rcu_synchronize structures that, in turn, contain rcu_head and completion structures. The address of the rcu_head structure is passed to call_rcu(), which results in concurrent accesses to this structure, and eventually also to the completion structure.
Similar access patterns may be found for per-CPU variables.
Quick quiz 2: But there are lots of plain loads from shared variables in the Linux kernel. These cannot possibly all be buggy, can they?
Answer: This turns out to be a matter of the context in which these plain loads execute and just how vigilant the developers and maintainers wish to be.
Starting with context, if a given variable is only ever accessed under the protection of a given exclusive lock or mutex, then use of plain loads (and stores, for that matter) is perfectly safe.
Less restrictive contexts also suffice. If stores to a given variable can never execute concurrently with any other accesses to that variable, then use of plain loads and stores is again perfectly safe. For example, if all loads from a given variable are under the protection of a reader-writer lock or mutex, and if all stores to that same variable are under the write-side protection of that same reader-writer lock or mutex, use of plain loads and stores is perfectly safe. Alternatively, if all stores to a given variable are carried out by a given kernel thread, and that same variable is only ever loaded by subsequently spawned child threads, plain loads and stores are yet again perfectly safe. Similarly, if all stores to a given structure happen before it is made visible to readers via rcu_assign_pointer(), and the readers, having gained access via rcu_dereference(), only ever load from that structure, plain loads and stores are once more perfectly safe. There are numerous additional variations on this theme.
But there is no shortage of plain loads in the kernel that really can execute concurrently with stores to that same variable, which brings us to vigilance. For example, if the variable only ever transitions from zero to one, no matter how the compiler dices and slices the load, the result will be either a zero or a one. Give or take the possibility of invented loads, which could get the effect of both a zero and a one being loaded, though if the value loaded is only used once, one would hope that this confusing possibility would be avoided.
In other words, when using plain loads from shared variables, it is the developers' and maintainers' responsibility to either prevent concurrent stores to that same variable on the one hand or to ensure that the compiler cannot optimize their algorithms out of existence on the other.
So are the Linux kernel's plain loads from shared variables buggy? If the relevant developers and maintainers are either carefully controlling the contexts from which those variables are accessed on the one hand or vigilantly considering what optimizing compilers can do to their code on the other, perhaps not!
Quick quiz 3: Why does it matter whether do_something() and do_something_else() are inline functions?
Answer: Because gp is not a static variable, if either do_something() or do_something_else() were separately compiled, the compiler would have to assume that either or both of these two functions might change the value of gp. This possibility would force the compiler to reload gp on line 15, thus avoiding the NULL-pointer dereference.
In the absence of link-time optimizations (LTO), that is. As optimizing compilers become more aggressive, developers and maintainers must become aggressive about disabling destructive optimizations, whether that be via command-line arguments to the compiler or via source-code decorations such as barrier(), READ_ONCE(), and WRITE_ONCE().
Quick quiz 4: But line 2 specifically checks for NULL. So how can do_low() possibly be invoked with a NULL pointer?
Answer: Imagine the following sequence of events:
- Line 2 loads a non-NULL pointer from global_ptr.
- Some other CPU stores NULL to global_ptr.
- Line 3 loads the newly stored NULL from global_ptr, and this compares less than high_address.
- Surprise! There is now a call to do_low() with a NULL pointer.
Quick quiz 5: Ouch! So can't the compiler invent a store to a normal variable pretty much any time it likes?
Answer: Thankfully, the answer is no. This is because the compiler is forbidden from introducing data races. The case of inventing a store just before a normal store is quite special: It is not possible for some other entity, be it CPU, thread, signal handler, or interrupt handler, to be able to see the invented store unless the code already has a data race, even without the invented store. And if the code already has a data race, it already invokes the dreaded specter of undefined behavior, which allows the compiler to generate pretty much whatever code it wants, regardless of the wishes of the developer.
But if the original store is volatile, as in WRITE_ONCE(), for all the compiler knows, there might be a side effect associated with the store that could signal some other thread, allowing data-race-free access to the variable. By inventing the store, the compiler might be introducing a data race, which it is not permitted to do. And this is one reason why memory-barriers.txt requires WRITE_ONCE() for stores that are to be ordered by control dependencies. Another reason may be gleaned from the Store-to-Load Transformations section.
In the case of volatile and atomic variables, the compiler is specifically forbidden from inventing writes.
Quick quiz 6: What exactly is a "data race”?
Answer: A data race occurs when there are multiple concurrent accesses to a given variable, at least one of which is a plain C-language access and at least one of which is a store.
Quick quiz 7: This paper has covered all of the transformations that an optimizing compiler can carry out, right?
Answer: Wrong.
There are a great many more, which should not be a surprise given the large number of situations where the C standard specifies undefined behavior, each of which potentially points the way to interesting compiler optimizations. There are some efforts under way to rein in compiler optimizations to at least some extent (for example, here, here [PDF], and here [PDF]), but compiler developers and standards-committee members are not necessarily as supportive of such efforts as might be hoped by maintainers and developers working with concurrent code.
Quick quiz 8: Given the risk, why not simply require that all accesses to shared variables use READ_ONCE() and WRITE_ONCE()?
Answer: One can certainly argue that they should be used more heavily than they currently are, but it is not all that hard to get too much of a good thing. For example, as mentioned in the answer to an earlier quick quiz, any number of in-kernel mechanisms, perhaps most notably locking, can provide mutual exclusion so that READ_ONCE() and WRITE_ONCE() are not needed.
In addition, although READ_ONCE() and WRITE_ONCE() are low cost, they are not free due to the fact that they constrain compiler optimizations. For example, the compiler is required to emit the accesses for a pair of consecutive READ_ONCE() invocations in order, and it might well be just fine (and perhaps also cheaper) for those to invocations to be reordered. Some fast paths might therefore need plain C-language accesses, though one would hope that the developers and maintainers would see fit to take pity on people reading their code by providing appropriate comments.
And there are guarantees that the Linux kernel relies on that are provided by usage restrictions rather than by compiler directives. Examples include address and data dependencies, for which the usage restrictions are documented in rcu_dereference.txt as well as control dependencies, for which the usage restrictions are documented in the CONTROL DEPENDENCIES section of memory-barriers.txt.
However, we should continue to expect increasingly aggressive compiler optimizations over time. This will likely increase the development and maintenance burden incurred by those making use of plain C-language loads and stores to shared variables in cases where data races exist. This prospect might help explain why the use of things like READ_ONCE() and WRITE_ONCE() has been increasing steadily within the Linux kernel.
Bcachefs gets closer
When it comes to new filesystems for Linux, patience is certainly a virtue. Btrfs took years to mature and, according to some, still isn't ready yet. Tux3 has kept users waiting since at least 2008; as of 2018 its developer still said that it was progressing. By these measures, bcachefs is a relative youngster, having been first announced a mere four years ago. Development of this next-generation filesystem continues, and bcachefs developer Kent Overstreet recently proclaimed his desire to "get this sucker merged", but there are some obstacles to overcome still.
Bcachefs has its origins in the bcache caching layer, though it is a separate project at this point. Like most of the newer filesystems out there, it uses a copy-on-write approach — data is copied to a new location when changed rather than overwritten. That enables the implementation of a number of interesting features; those intended for bcachefs include data checksumming, compression, multiple-device and RAID support, hierarchical storage management, snapshots, and, naturally, good performance. Work on bcachefs has apparently been slowed by the fact that there is relatively little interest in supporting this work; Overstreet has been soliciting donations on Patreon to be able to push the project forward. He has seemingly had some success in this area, and feels that the filesystem is now getting close to ready:
Those who wish to play with this new filesystem will quickly discover that one of the places where development has lagged is documentation. For the most part, users have to pull down the code and stumble through the process of setting up a filesystem. There is, at least, a man page for the bcachefs command that makes a good starting point.
Overstreet said that the bcachefs code is in a state where it is ready for merging into the mainline. Users will have to be patient for a little while longer, though, as it seems that there are still a few obstacles in the way, starting with a number of complaints from Linus Torvalds on how the repository itself is managed. Simply cleaning things up at that level is likely to require a fair amount of work.
Core-kernel changes
But, beyond that, there are a number of core-kernel changes that will have to go in to support bcachefs. Overstreet surely knew that this is where any initial resistance might come from; code that is buried within a filesystem implementation is unlikely to hurt people who do not actually use it, but core-kernel changes can have wider repercussions. So, while the bcachefs code itself has not been seen on the kernel mailing lists in recent times, the core changes were all posted for review.
One of those changes is the addition of a new locking primitive called a SIX lock. These locks are reader/writer locks, but with a twist. Normal reader/writer locks allow any number of readers to access the protected data concurrently, but a writer has exclusive access. SIX locks tweak the model by turning the writer side into a two-step process. Any code that wishes to have write access to a protected data structure must first obtain an "intent" lock. Only one holder of an intent lock may exist, so the second thread that tries to obtain one will block until the first releases its lock. But holding the intent lock does not block readers, who can continue to access the data structure.
Before actually making any changes, though, the holder of the intent lock must upgrade it to a write lock, which will ensure that everybody else, including readers, is excluded. The intent lock, thus, gives a writer access to a data structure that will not change while allowing that writer to minimize the amount of time that it holds exclusive access to the data structure.
Overstreet said that SIX locks "seem to be pretty
uncontroversial
" and, for the most part, the (lack of) complaints
would seem to bear that out. That said, Torvalds did suggest that it might
be better to add the "intent" level to the kernel's rwsem locks rather than
introducing an entirely new locking primitive. Dave Chinner objected
to this idea, though, saying that rwsems are already too fragile and should
not be complicated further. A definitive resolution has not been reached
here, but it seems likely that SIX locks will be merged with the rest when
the time comes.
Then, there is another locking primitive called pagecache_lock.
There is one of these locks for each address space; its job is to regulate
the addition of pages to the page cache. This lock can be acquired in two
modes, called "add" and "block"; the former is for adding pages, while the
latter is for preventing others from adding pages. Any number of threads
can hold the lock simultaneously as long as they all use the same mode, so
many threads can be adding pages concurrently, for example. Changing the
mode of the lock may require a wait, though. Torvalds didn't like this
lock, saying "we don't do those hacky recursive things
".
Overstreet agreed that this lock is not ideal; in the patch-set cover
letter he said it was "intentionally ugly in the hopes that someone
else will come up with a magical elegant solution
" — an approach
that is often surprisingly effective. He defended the need for the lock,
though. In current kernels, a number of operations, such as direct I/O,
will remove pages from the page cache to prevent data corruption resulting
from an operation that bypasses the cache. But there is nothing that
prevents the system from faulting those pages back into the cache; that can
happen as a result of user-space code, automatic readahead in the kernel,
or any of a number of other things. If pages re-enter the cache at the
wrong time, data corruption could result.
The existence of the problem is not in doubt, but opinions differ on how it might be solved. Torvalds suggested that some sort of page-level locking mechanism would be better. Chinner is working on range locks as a possible solution; he also said that more and more I/O is likely to bypass the page cache altogether. Matthew Wilcox suggested another approach where buffered I/O operations would not be able to add pages to the cache while direct I/O is underway, but where direct I/O would also just act like buffered I/O when the relevant pages already exist in the cache.
Unsurprisingly, this problem was not solved in the mailing-list discussion. A number of ideas were raised, though, and Overstreet is left with the task of showing that his solution remains the best — a tall order.
Finally, there is the "closure" mechanism that is currently used inside the bcache code. A closure is essentially a reference count with some supporting code to make it easy to wait for specific things to happen. Overstreet wants to move the closure code into the lib directory to make it more widely available. Most people seem not to care, but Christoph Hellwig seems strongly opposed to the idea. He has not yet responded to a request for more information on why he dislikes it, though.
Thus, as can be seen, there are a few problems that need to be solved yet — and that is before anybody has looked at the bcachefs code itself. That is likely to get close scrutiny as well when the time comes; some filesystem developers have been clear in their belief that merging filesystem code before it is ready has led to long-term problems in the past. So, while bcachefs looks like an interesting feature that is actively progressing, the smart money would still not be on it landing in the mainline kernel in the near future.
5.3 Merge window, part 1
As of this writing, exactly 6,666 non-merge changesets have been pulled into the mainline repository for the 5.3 development cycle. The merge window has thus just begun, there is still quite a bit in the way of interesting changes to look at. Read on for a list of what has been merged so far.
Architecture-specific
- The x86 umonitor, umwait, and tpause instructions are now supported for use by user-space code; they make it possible to efficiently execute small delays without the need for busy loops. A knob has been provided to allow system administrators to control the maximum period for which the CPU can be paused.
- The pa-risc architecture now supports dynamic ftrace.
Core kernel
- The scheduler utilization clamping patch set has been merged. This feature allows an administrator to cause specific processes to appear to create more or less load than they actually do; that, in turn, will affect how the CPU frequency governor responds when those processes become runnable. So, for example, an interactive process could be made to appear to have heavy CPU requirements, causing an immediate increase in CPU frequency when that process wakes up.
- The pidfd_open() system call has been added; it allows a process to obtain a pidfd for another, existing process. It is also now possible to use poll() on a pidfd to get notification when the associated process dies.
- Also added is the clone3() system call, which reorganizes the clone() interface, makes it more extensible, and adds space for more flags.
- The new bpf_send_signal() helper allows a BPF program to send a signal to an arbitrary process.
- The BPF verifier is now able to handle programs with loops, as long as the execution of the loop is bounded and cannot cause the program to exceed the maximum instruction count; that removes a major limitation that has irritated BPF developers for some time. Note that this is not the bounded-loop work that was under discussion late last year; it is a new implementation. It seems that the verifier efficiency improvements merged for 5.2 made this task rather simpler.
Filesystems and block layer
- The NFSv4 server now creates a directory under /proc/fs/nfsd/clients with information about current NFS clients, including which files they have open.
Hardware support
- Audio: Conexant CX2072X codecs, Rhythm Tech rt1011 and rt1308 amplifiers, and Cirrus Logic CS47L35, CS47L85, and CS47L90 codecs.
- Industrial I/O: Infineon DPS310 pressure and temperature sensors, Analog Devices ADF4371 and ADF4372 wideband synthesizers, Analog Devices AD8366 gain amplifiers, and ChromeOS EC lid-angle sensors.
- Media: Allegro DVT video control units and Amlogic video decoders.
- Miscellaneous: Freescale i.MX8 DDR performance monitors, Renesas RZ/A1 interrupt controllers, Annapurna Labs fabric interrupt controllers, Atmel SHA204A random-number generators, TI LM3697, LM36274, and LM36274 LED controllers, Dialog Semiconductor SLG51000 regulators, Socionext SynQuacer SPI controllers, Freescale i.MX8M CPU-frequency controllers, Infineon PXE1610 voltage regulators, Infineon IRPS5401 power-management ICs, NXP i.MX8 SCU on-chip OTP controllers, Mixel MIPI DSI PHYs, Fairchild Semiconductor FSA9480 microUSB switches, and ChromeOS embedded controllers.
- Networking: NXP TJA11xx PHYs, Google Virtual NICs, and Hisilicon HI13X1 network interfaces.
- USB: Qualcomm PCIe Gen2 PHYs.
- Removals: the isdn4linux ISDN driver subsystem has been removed entirely; it doesn't appear to have been used for some time. The separate CAPI subsystem is also on its way out, but it has only been moved to the staging directory for now. The mISDN subsystem will remain for now. See this commit for details.
Networking
- The kernel will now accept IPv4 addresses in the 0.0.0.0/8 range as valid. Getting the Internet as a whole to allow that is a work in progress but, once it happens, it will make 16 million more IPv4 addresses available for use.
- It is now possible to attach BPF programs (at the control-group level) to the setsockopt() and getsockopt() system calls. That allows the imposition of administrator policy on those calls; see this commit for some documentation.
- There is also a new socket-level hook to call a BPF program once every round-trip-time interval.
Security-related
- Cryptographic keys can now be tied to a specific user or network namespace, making them unavailable outside of that namespace. Keys are also now protected by access control lists; see this commit for details. (Note that the ACL patch was subsequently reverted though it may be back before the end of the merge window).
Internal kernel changes
- force_sig() has always taken the target task as a parameter, but it has never actually been safe to use for anything other than the current task. That parameter has been removed and a large number of callers have been updated.
Linus Torvalds has been a little grumpy during this merge window, having encountered multiple regressions that affected his machine. Most of those have been worked out for now; with luck things will go more smoothly from here on out. If the usual schedule holds, the 5.3 merge window will close on July 21, with the final 5.3 release expected in early-to-mid September.
Reworking CFS load balancing
The Linux scheduler is made of the main types of scheduling which are the Completely Fair Scheduler (CFS), the realtime (RT), and the more recent deadline scheduler. The CFS class is the default and most commonly used one, which aims at sharing the running time of CPUs between tasks according to their priority. It was introduced in 2007 and has seen several major changes since. One of these major changes was the introduction of per-entity load tracking (PELT), which gives more details about the utilization of CPUs by tasks.
The load-balancing algorithm of the scheduler has the key responsibility of placing tasks on CPUs to optimize the overall throughput of the system. It periodically monitors the system and decides when tasks have to migrate to ensure a fair distribution of compute capacity and an optimal use of resources. But that hasn't really changed to take full advantage of these new metrics and it is still only using the load as the unit to migrate tasks, even when the root cause of an imbalance is not linked to load but to the available compute capacity of CPUs, for example.
In order to quantify how imbalanced the system is, load balancing uses some virtual and somewhat meaningless values like the average load per task. This is often used as a fallback when the load is not the right metric to express the imbalance but "should" be enough to fix the problem. In other cases, it can even bias the statistics to make a group look overloaded when it is not to force task migration between groups. But these hooks are not always enough and some use cases still show some sub-optimal task placement.
As an example, we can have a look at how load balancing handles asymmetries between groups of CPUs and how it sometimes fails to ensure that there is one task per CPU. This asymmetry can come from CPU microarchitecture, the time stolen by other scheduling classes, or because of thermal mitigation that can temporarily decrease the maximum compute capacity of a CPU. Let's take the case of a big.LITTLE platform made of four LITTLE cores and four big cores. If there are only eight tasks running on the system, the scheduler should place one task on each CPU, but it puts five tasks on the cluster made of big cores instead.
If you only look at the load, the decision makes sense because there is much more compute capacity in this group and the average load is balanced between tasks, but it also leaves one LITTLE core idle while two tasks have to share a core. This is one typical case where comparing load doesn't make sense and using the number of idle cores is more appropriate. A few other use cases have been described during the talks to highlight that some information is missing to make better decisions.
Those examples demonstrated that it's probably time for the load-balancing algorithm to be cleaned up and reworked to use new metrics, remove the bypasses that have been inserted over time, and to remove the old heuristics, which have lost their meaning.
With all metrics available in the scheduler, a group of CPUs can be better classified and its imbalance better identified. That's why the first step is to classify the groups of CPUs into categories after collecting statistics:
- Groups that have spare capacity to be used by some other tasks.
- Groups that are fully busy and all cores are fully used.
- Groups that are overloaded and have to share the running time between tasks.
In addition to these generic states, some special cases also have to be identified:
- The need to move any task, but at least one to unblock a pinned related imbalance
- Move a minimum level of utilization
- Move a specific task
Once classified, load balancing can easily select the group it should pull some imbalance to and also what needs to be moved:
- Is it load to ensure fair time sharing between tasks when CPUs are overloaded ?
- Is it a number of tasks to fill idle CPUs in other groups ?
- Is it a dedicated task that doesn't fit into its local CPUs ?
That's what a rework of the load balancing will have to address.
Frequency scale-invariance on x86_64
The utilization and load signals computed with the PELT algorithm are affected by the processor's clock frequency: loosely speaking, a task looks bigger if the machine is running slower. The remedy to this problem is called "frequency scale-invariance" and consists in normalizing all interesting quantities via the scaling factor current_frequency / max_frequency. At the time of this writing only the Arm architecture implements it; a session at the third OSPM summit in Pisa discussed a possible way forward for x86_64 systems.
The reader may recall that, in PELT, time is partitioned in segments and, for each of those, the on-CPU time of a task is recorded (in the case of utilization; for load, the quantity of interest is on-run-queue time). This implies that a given task would score a higher utilization and load if the CPU is running at a lower frequency: generally speaking, a slower running CPU makes tasks run for longer; a longer running time produces larger values of the PELT signals. This effect of the PELT formula is undesired, because utilization and load of tasks and run queues cannot be compared across CPUs or across time, since the operating frequency might be different.
The PELT framework offers a mechanism to rescale quantities and make them invariant to changes of frequency: some architecture-specific code has to implement the function arch_scale_freq_capacity() to return an appropriate scaling factor which, ideally, is going to be the ratio current_frequency / max_frequency — PELT will then use this factor where appropriate. As of today, only the Arm architecture implements arch_scale_freq_capacity(), thus it's the only architecture that can claim to have frequency scale-invariant load and utilization.
We just said that rescaling quantities to be invariant to changes of frequency requires knowing the maximum frequency that a CPU can run at; on x86_64 this isn't simple. Intel and AMD x86_64 processors generally implement a feature, called Intel Turbo Boost and AMD Turbo Core, respectively, that makes the maximum frequency available to a core be a function of the overall power consumption of the socket; with most cores idle, the few active ones can get to higher speeds not normally accessible. Given the turbo mechanism, "maximum frequency" becomes a value that varies over time. It's also not easily known; the hardware doesn't expose this value explicitly, all we can query for is the average frequency seen in the recent past. If the OS doesn't request the maximum value, that wouldn't show up among the recently observed frequencies and the only possible thing to do is guess.
A number of approaches to solve this problem have been proposed in the past:
- Pretend that the maximum frequency is constant over time, using a fixed value within the turbo range for the calculations. One could, for example, compute the normalizing factor using the one-core turbo level (a frequency attainable only when all but one cores are idle) instead of the unknown true maximum, or some other turbo level.
- Use power consumption data, which can be read from a Model-Specific Register (MSR), to infer the maximum available frequency.
- Keep a running average of frequencies observed in the recent past and normalize against that value.
The OSPM audience was presented the results of performance benchmarks from the implementation of the first option above, where some turbo level is used in lieu of the maximum frequency for normalization purposes.
So far we've been vague regarding what has to be rescaled using the factor computed in arch_scale_freq_capacity(). Prior to Linux 5.2, the answer would have been "individual PELT contributions". The PELT sum for, say, utilization is built by summing the running time of a task during PELT time intervals, each of which has to be made invariant to changes of frequency. Since 5.2 a novel algorithm by Vincent Guittot has improved the accuracy of calculations by using the frequency scaling factor to dilate time instead of scaling components of the PELT sum. When PELT is updated, the time since the last update has to be computed; this value is immediately multiplied by the coefficient from arch_scale_freq_capacity(). As an effect of this change, the length of PELT time intervals isn't fixed anymore to 1024 microseconds, but increases as frequency decreases.
Using a turbo frequency level to normalize PELT calculations was first proposed by Peter Zijlstra in a patch from May 2018. Zijlstra's patch normalized PELT using the one-core turbo level, (i.e. made arch_scale_freq_capacity() return current_frequency / one_core_turbo_frequency). It's not hard to see why this coefficient rarely reaches one: that happens only if exactly one core is active and all others are idle. Back when this change was proposed, the consensus was that the denominator of this coefficient is too large; Juri Lelli formalized this objection showing in a test case that if two cores were active at the same time, none of them could reach the maximum utilization value of 1024 even if they were fully busy. Zijlstra agreed but added that he designed his frequency-normalization strategy for Guittot's new time-scaling approach, which at the time was already in the works.
Performance testing
The performance testing work presented at the OSPM summit consisted of taking Zijlstra's patch, together with Guittot's new invariance machinery, and seeing how that performs in a few standard benchmarks. Four variants of the patch were evaluated: using one-core turbo and max-cores turbo (a lower frequency, still in the turbo range, defined as the level sustainable by the maximum number of cores simultaneously) as turbo levels of reference against which to normalize, with and without Guittot's new invariance to better understand how time scaling interacts with the rest.
All of the four variations of Zijlstra's patch showed a marked performance improvement over the 5.0 baseline, specifically the I/O benchmark dbench (10% improvement on average across all values for the number of I/O clients), its networking counterpart tbench (around 15% average improvement), and the Linux kernel compilation test kernbench (between 10% and 15% average improvement). It would seem that frequency-invariant load information leads to better predictions by the frequency-scaling governor.
Another benchmark consisted of running the unit-test suite of the Git source control system and measuring the elapsed time. This workload is taken as representative of long-running shell scripts, and received a whopping 30% to 50% speed boost depending on the test machine. Most of the benchmarks are parameterized so that the OS can be tested under a varying degree of load; kernbench, for example, is run with one compilation job, then two, four, eight, and so on, up to twice the number of cores of the test machine.
Looking at the detailed gains observed in dbench, tbench, and kernbench shows that the test cases contributing the most to the overall scores are those where the machine is lightly loaded. For example the four-client, eight-client, and 16-client cases for tbench on a dual-socket Haswell machine with 48 total cores yield gains of respectively 38%, 66%, and 52% compared to the baseline. Kernel compilation on the same machine showed the largest gain with two, four, and eight jobs (16%, 14% and 12%, respectively). On a dual-socket Broadwell machine with 80 cores in total, dbench benefits the most on the two-client and four-client cases, 17% and 18%, respectively. Of all the tests mentioned, the over-utilization scenario (i.e. when the machine is fully saturated and has the maximum number of jobs or clients depending on the test) does not regress.
The tests allowed determining which scaling factor is best suited and to what extent Guittot's rewrite of PELT invariance affects this patch. It seems like normalizing against the max-cores turbo level gives a slight advantage on some benchmarks (compared to using the one-core turbo value in the scaling factor), especially for the read-only flavor of pgbench, an I/O benchmark shipped with PostgreSQL. All in all it doesn't seem like the time scaling-based invariance mechanism influences the outcome a whole lot, at least from a performance perspective. Benchmark data shows no change along that axis, from which we learn that the two features don't play against each other — a welcome conclusion.
Paul Turner and Rafael Wysocki suggested trying the four-core turbo level as the normalization factor, and see how it compares to the ones already tested. The rationale is that the curve of turbo levels is generally very steep, with the one-, two-, three-, and four-core values being a lot higher than the rest. From the experimental results, the max-cores turbo value seems to be a slightly better normalization choice than one-core turbo, but it has the downside of considering every frequency above that level as if it was the absolute maximum, due to clipping; a large portion of the frequency range is collapsed into a single value. Using the four-core turbo level, or "the lowest among high turbo levels", is likely to be a more sensible compromise.
Up to now we have described a prototype to approximate frequency scale-invariance for x86_64 and enumerated a list of exciting performance improvements that such a change would bring, but haven't discussed why the new code performs so differently than the baseline. The audience agreed on a likely explanation for this phenomenon: the schedutil frequency-scaling governor makes better predictions when the utilization data it consumes is frequency-invariant.
PELT signals (load and utilization) are used in three locations: the wake-up path, the load-balance path, and the schedutil governor. The observed performance benefits are of the kind compatible with improved frequency selection: substantial when the machine is lightly loaded, negligible at saturation. Furthermore schedutil employs a different formula depending on whether the input utilization is invariant or not; in the invariant case it uses:
next_freq = 1.25 * max_freq * util
otherwise the frequency is selected with a formula that takes the current
frequency into account:
next_freq = 1.25 * curr_freq * util
The latter expression contains a feedback loop (the clock frequency to be requested depends on the frequency the CPU is currently running at) and is subject to instabilities, especially around the boundaries of turbo levels. Switching to the first formula (which we're allowed to use since util has the desired property of being invariant) improves the governor's behavior.
This work considered Intel Core and Xeon processors; as a closing remark, Wysocki suggested looking at the source code of the intel_pstate frequency-scaling driver to learn how to read turbo levels from Atom processors, and Zijlstra added that AMD processors will require some further study as well.
How can we make schedutil even more effective?
Mobile platforms can feature some operating power points (OPPs) that are more energy-efficient than others at lower frequencies. The inefficient low-frequency OPPs can therefore be avoided in normal conditions, leading to better latency at no cost. The power cost of OPPs does not increase linearly with frequency, which gives some opportunities for smarter decisions: if the frequency can be increased when it would be beneficial for a low power bill, why not do it?
The proposed solution allows skipping low-frequency inefficient OPPs, as well as boosting the frequency when the CPU-utilization increase needs to be backed by a frequency increase. Since the reused heuristic does not perform well for that use case, a better alternative has been proposed by the audience: comparing some utilization signals to detect frequency ramp-up phases.
Scheduler soft affinity
As systems are getting bigger with more and more CPU cores, multiple instances of workloads are being consolidated on a single system. For example, multiple virtual machines (VMs) or containers on the same host is a common use case. Currently the Linux scheduler provides a few ways to partition multiple workload instances: hard partitioning using the sched_setaffinity() system call or the cpuset.cpus control group interface that binds the thread to a specific set of CPUs, or by using control group CPU shares (cpu.shares) that divide the CPU cycles of the system among multiple instances using fair sharing.
But there is a need to have a way of dynamically partitioning workload instances so that one instance can use the available CPUs of another instance if they are idle, but only use the CPUs of its own partition when other partitions are busy. For example, the Oracle database has a multi-tenancy feature that can enable the root-level database instance to house multiple lightweight Pluggable Database (PDB) instances, each of which can be partitioned to use a NUMA node in a multi-socket system. Hard partitioning is not an option here, as one PDB instance needs to be able to burst out of its partition and use other available idle CPUs when other PDBs are idle. Hence CPU shares are used in this case. But this has the disadvantage of cache-coherence overhead (i.e. each instance running on all sockets will incur the cross-socket cache-coherence penalty due to data sharing).
So there needs to be a notion of "soft affinity" where it can be specified to the scheduler to prefer a set of CPUs while scheduling a task, but to use other CPUs if they are not all busy. One way of potentially achieving this behavior is using the Linux AutoNUMA balancer. If the memory of each instance is pinned to a socket (NUMA node), the AutoNUMA balancer should migrate threads of instances to their corresponding nodes when all are busy.
The disadvantages of this approach are that it will only work for NUMA-level partitions, the reaction time is high due to the periodic scanning mechanism of AutoNUMA, and it will not work in cases where memory is spread among all NUMA nodes. Some motivational experiments with numactl to restrict memory allocation in a NUMA node in fact shows that AutoNUMA still moves memory pages after the initial allocation. Also there is no improvement in performance with AutoNUMA migrating pages and threads as compared to disabling AutoNUMA in the case of two database instances running online transaction processing (OLTP) workloads on a two-socket system.
This further reinforces the need for soft affinity, either via a new system call or a control group interface. A prototype implementation introduces a new cpu_preferred CPU set in addition to the existing cpu_allowed CPU set in the task structure. During the first-level search (wake_affine()), the scheduler uses the cpu_preferred set to find a last-level cache (LLC) domain (typically a NUMA node) and in the second level (in the LLC domain), searches the cpu_preferred set first and then the rest of the CPUs in the cpu_allowed set.
This only changes the scheduler wakeup path, but keeps the idle-balancing unchanged. This is intentional as one half of the scheduler will try to choose from cpu_preferred while the other half will steal threads indiscriminately, thus giving the overall "softness" in affinity. With such a basic implementation, experiments with two instances of hackbench and two instances of the database both show improvement as compared to running them with no affinity on a two-socket system. Also, with only one instance running, the database performed similarly to no affinity, but substantial regressions were seen with hackbench. This showed that soft affinity was not soft enough in this case, as all the CPUs in the system were not being utilized.
Further investigation led to the idea of load-based soft affinity, where the scheduler will choose the cpu_preferred or the cpu_allowed set based on the CPU utilization of those sets. This decision will be made in the first-level search and if the CPU utilization of cpu_preferred is too high compared to cpu_allowed, it will chose the latter, thus bursting out of the partition.
It is important to note that iterating over all the CPUs to find the total utilization will add significant overhead, therefore one sample CPU is picked from each set and compared in O(1) to decide. With such an implementation, the user now has scheduler tunables to tune the softness of soft affinity. Experiments showed that the regressions of one-instance hackbench were gone when a softer soft affinity was used, while retaining the improvements of the two-instance case. For the databases, harder soft affinity worked better, which behaved similarly to the initial basic implementation. While a global scheduler tunable may work for homogeneous workload consolidation, one size may not fit all in case of heterogeneous consolidations. Per-process tunables can be potentially used in that case.
SCHED_DEADLINE on heterogeneous multicores
As already mentioned in other talks, the SCHED_DEADLINE policy currently does not consider the capacities or the running frequencies of the various CPU cores. This mainly impacts two different aspects: admission control and task placement.
The SCHED_DEADLINE admission control is designed with two goals: avoiding overload (that is, avoid starving non-deadline tasks) and providing performance guarantees to deadline tasks. Unfortunately, the current code assumes that all of the CPU cores have the same maximum capacity (which is assumed to be equal to the maximum capacity of the fastest core), and this assumption breaks the admission-control mechanism. A simple experiment (creating SCHED_DEADLINE tasks until the admission control fails) shows that on a big.LITTLE CPU, it is currently possible to starve non-deadline tasks. A first patch that has been submitted to the Linux kernel mailing list fixes this issue by considering the maximum capacity of each CPU core when performing the admission control. Repeating the experiment shows that the patch is effective (until thermal throttling slows down the CPU, but this is a different issue).
Other patches submitted to the Linux kernel mailing list and discussed in this presentation try to fix the SCHED_DEADLINE migration mechanism so that deadline tasks are placed on CPU cores based the cores' capacities. In particular, the patches try make sure that deadline tasks are not scheduled on cores that are too slow (the scheduler checks if a task "fits" on a core — that is, the task can be scheduled on the core without missing a deadline — before migration) or too fast (the scheduler tries to select the slowest core where the task fits). The first check is needed for the correctness of the scheduler, while the second one is useful for power saving or to leave fast cores idle for other (maybe more time-consuming) tasks.
During the presentation, some possible issues with the patch set's approach were discussed. The discussion also covered some possible alternative implementations: in particular, in how to check if a core is fast enough to run a deadline task:
- For the task, should we consider the static runtime and period, or the current runtime and scheduling deadline?
- For the core, should we consider its capacity at the current running frequency, or its maximum capacity at the highest running frequency?
Finally, some experimental results were presented, showing that the patch set makes the scheduler more correct (some missed deadlines due to incorrect task placement are avoided) and reduces the energy consumption.
TurboSched
Parth Shah discussed the problem of sustaining "turbo" frequencies on SMP systems. Modern multicore systems have support for turbo frequencies, which are frequencies above the range of the rated frequencies that can be sustained by a small number of CPUs in the chip under certain power and thermal constraints. However, due to these very power and thermal constraints, it is harder to sustain these turbo frequencies for longer durations. Shah said that IBM POWER9 systems have a margin of around 18% for turbo range and sustaining these frequencies can provide better single-threaded performance.
In real-world scenarios such as high-performance computing, tasks are classified into two categories:
- CPU-intensive: Tasks that benefit from a higher frequency and typically run for longer durations.
- Jitter: These are short-lived, low-utilization tasks, typically performing some housekeeping operations.
Experimentation showed that when we run a mix of these two types of tasks, the task wakeup logic would wake up an idle core even for a jitter task. This would result in an increase in the power consumption, which would, in most cases, throttle the frequency on the other busy cores that were running in a turbo frequency range.
So Shah suggested that if there were a mechanism to classify the tasks as jitter tasks, then the CFS wakeup logic could be tweaked to pick an already running core with spare capacity. This task-packing policy will ensure that idle cores aren't woken up to run jitter tasks, thereby allowing the busy cores to sustain turbo frequency for a longer duration. He further showed that this approach proved to be better than isolating all the jitter tasks into a small group of cores. Thus, there was scope for doing task packing from the kernel scheduler in a dynamic manner.
Shah also discussed the challenge of determining the spare capacity left in the core before deciding whether the jitter task can be packed into such a core. In general, determining the capacity of the core from the capacities of the constituent threads is not straightforward. On POWER processors, Shah currently uses a formula that would compute the core-capacity in terms of the online threads of the core, such that SMT2 (two threads per core) would have 1.25x the capacity of a single thread, SMT4 would have 1.5x capacity of a single thread and SMT8 would have 2x the capacity of a single thread. However, there is scope for improvement. With this, Shah determines whether a jitter task can be packed into one of the already running cores, as long as it has spare capacity to accommodate the jitter task.
To test his solution, Shah used a synthetic workload generator that can spawn the aforementioned types of tasks. On this workload, he was able to demonstrate that with his approach we could sustain the turbo frequency for 16% longer compared to the existing CFS task-wakeup logic. This translated to 12% benefit in operations per second when compared to the CFS algorithm.
For classifying the tasks as jitter, he is currently using the UCLAMP framework in which tasks that have their max-utilization set to the lowest value are considered to be jitter tasks. This has an added advantage that even when the jitter tasks are running on potentially idle cores, the schedutil governor will be running them at the lowest frequency.
He further clarified that the existing Energy-Aware Scheduling that got merged earlier this year was not applicable in its current form for SMT systems. It wasn't trivial to extend the model to SMT systems.
He concluded his session saying that he is willing to explore the option of extending the EAS model if it can allow for sustaining turbo frequencies for a longer duration. He also solicited feedback on his patch set posted on the kernel mailing list.
[LWN looked at TurboSched in early July.]
New approaches to thermal management
Volker Eckert presented results from his experiments to use the CFS bandwidth controller for thermal management. The fundamental idea is to use less CPU bandwidth while running low-priority (background) tasks and thus keep the power budget available for more important tasks. This led to two interesting discussions: how to solve the per-entity load tracking (PELT) utilization issues for throttled tasks, and the idea, pushed by Morten Rasmussen, that thermal management should be applied to tasks rather than CPUs. Following this overall design approach, which was also backed by Paul Turner, the CFS bandwidth controller could play an essential role in a thermal-management architecture for future mobile systems.
Turner further suggested that the utilization should be scaled by using a non-throttled clock as a possible solution for the PELT problem. Another interesting point was raised as to whether the PELT utilization has to be propagated through the task-group hierarchy since there are no users of it for task groups. There is definitely some overlapping with the current "flatten CPU controller runqueues" patch set by Rik van Riel.
Eckert plans to continue his work by delivering a patch for this issue so it can be further discussed at the Linux Plumbers Conference later this year.
Proxy execution
At the risk of playing defense, Juri Lelli started his talk by saying that he was going to be quick, as he didn't actually have any updates from what he presented last year at the Linux Plumbers Conference and from the first RFC posted on the Linux kernel mailing list. The main goal of his session was to understand if there is still interest in this line of work.
Proxy execution can be simply thought of as a "better" priority-inheritance mechanism, which a mutex owner can potentially run using (inheriting) the scheduling context (properties) of other tasks blocked on the same mutex (avoiding priority inversions). For the SCHED_DEADLINE scheduling policy, this translates to the possibility for a mutex owner to run "inside" donors' (mutex waiters) bandwidth, fixing a longstanding issue of policy: priority-boosted tasks are currently allowed to run outside of runtime enforcement, as they only inherit donors' deadline.
With examples, Lelli showed why not having any priority-inheritance mechanism is bad (priority inversions), and why the current one is actually worse (can cause deadline misses on tasks not even using the same mutex). He finally got into some details of how proxy execution is implemented: by separating scheduling and execution contexts and dynamically building the proxy chain.
After suggesting that the proxy execution idea is general enough that it could be potentially applied to several other synchronization mechanisms (e.g., condition variables, binder calls, yield_to semantic types of calls), he addressed the audience for comments and indications that all this is still relevant. Peter Zijlstra promptly stated that this is still something that we want to have, even though it might take a while to get it right. Dhaval Giani mentioned that control-group-aware unbound workqueues might find this mechanism useful, because it would allow a proxy task to temporarily assume the control group characteristics from another task so that it can use the other task's control-group-related information to run, but the feasibility of this idea wasn't clear in the end.
Zijlstra and Paul Turner then discussed how proxy execution would work with futexes. Potential problems that arise when taking into consideration task affinities were discussed as well. The current implementation migrates potential donors to the mutex-holder CPU (so that the holder can keep running on the same CPU and thus respect its affinity), but this might not work well for SCHED_DEADLINE since freely moving donors' bandwidth might break admission-control guarantees; discussion continued off-line, since the problem doesn't seem to be an easy one to solve.
Page editor: Jonathan Corbet
Next page:
Brief items>>