LWN.net Weekly Edition for April 1, 2021

Welcome to the LWN.net Weekly Edition for April 1, 2021

This edition contains the following feature content:

• HPy: a better C API for Python?: the Python C API is holding back the language; perhaps HPy can improve that situation.
• The uninvited Internet of things: we are losing the ability to control our gadgets' ability to phone home.
• Patching until the COWs come home (part 2): unintended consequences from a memory-management fix.
• Lockless patterns: some final topics: the closing chapter of the lockless patterns series.
• GDB and io_uring: a 5.12 io_uring change has some surprising side effects.

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.

Comments (none posted)

HPy: a better C API for Python?

The HPy project has been around for more than a year now; it is meant to provide an alternate C API for Python that allows extensions to the language to run, and run well, in more environments. It first came to our attention in a report of a talk at the 2020 Python Language Summit (LWN coverage), but it goes back to some discussions that were held at EuroPython 2019. There are a number of ways that the existing C API holds back innovation for Python, but there are also some hugely important extensions (e.g. NumPy) that use it; any change to the API needs to take those into account.

Background

There are other efforts to improve the C API, notably, Victor Stinner's PEP 620 ("Hide implementation details from the C API"), but those have generally been incremental improvements, with the intent of keeping the existing extensions working. In some sense HPy is similar, because it does not seek to replace the existing API, at least anytime soon. But the project does seek to make sweeping changes to the API in pursuit of its goals.

The current Python C API is closely tied to the CPython implementation of the language, which is part of what makes it hard to adapt the API to other implementations, such as PyPy. The C API effectively embeds the reference-counting garbage collector into the language extensions, which means that alternative garbage-collecting approaches cannot be used (or only used painfully) when trying to run those extensions. It also holds back CPython because it is well-nigh impossible to, for example, remove or alter the global interpreter lock (GIL) without changing the API, thus requiring changes to the extensions.

So HPy seeks to provide a more streamlined C API that is not intimately tied to CPython, but that can run extensions with the same performance as those that use the existing API. Extensions written to use HPy will be "much faster" on alternatives like PyPy or Python on GraalVM, according to the home page. HPy also provides a way to build "universal binaries" for extensions that will run unmodified on various Pythons, and a "debug mode" that is intended to catch common mistakes made in extensions. Beyond that, it is meant to bring:

Nicer API: the standard Python/C API shows its age. HPy is designed to overcome some of its limitations, be more consistent, produce better quality extensions and to make it harder to introduce bugs.

Obviously, HPy is an ambitious project. It has also largely been flying under the radar, which is something that the project would like to change. To that end, it put out its first blog post, titled "Hello, HPy", on March 29; it was penned by Antonio Cuni, who also gave the talk at the language summit. The post goes through an example of a simple Python extension that adds two integers using both the existing C API and HPy.

The first major difference that will be apparent is that instead of PyObject pointers, Python objects are represented by opaque handles (of type HPy), which simply need to be closed once when they are no longer needed (rather than requiring manual reference-counting operations using Py_INCREF()/Py_DECREF()). The HPy debug mode helps track the handles to ensure they are closed properly. As might be guessed, the "H" in HPy comes from "handle".

In addition, HPy adds an explicit context parameter (an HPyContext) for each call in order to explicitly manage the local state of the interpreter. It is meant to allow future versions where different threads each have their own interpreter or a process contains multiple interpreters (such as different versions or implementations). It also allows current features like the universal binaries.

If you squint at the code for the HPy example, it does not look wildly different than the equivalent using the existing API. That is not a surprise, especially given the lack of complexity in the example; obviously adding two integers is a far cry from something like NumPy. But the blog post also shows how to build extensions for CPython, GraalVM, and as a universal binary that will run in PyPy, GraalVM, or CPython. It is a compelling story even if the example extension is trivial.

Status

As noted on the home page, HPy is still in its infancy; there have been no official releases, for example. In addition, it only supports a small subset of the existing API:

The Python/C API is huge and at the moment only a small fraction of it is available in HPy. We are experimenting by porting existing extensions to HPy and adding/designing new functionalities on a per-need basis.

So far, three extensions have been targeted for conversion to using HPy. The UltraJSON-HPy extension is an experiment to port the UltraJSON (ujson) module that provides a fast, C-based JSON parser. It was the "first real-world module to be ported to HPy". Since it only exports functions—not types—and needs only a small subset of the API, it was a "nice fit" for what HPy has available.

The other two experimental ports show the importance of NumPy for any proposed change to the Python C API. PicoNumpy is a tiny portion of NumPy that provides a one-dimensional array type, indexing, a len() function, element-wise addition of two arrays, and element-wise multiplication and division by a single value. Beyond that NumPy-HPy is an early-stage experiment in porting all of NumPy to HPy. Neither of those looks to be all that far along at this point, however.

HPy itself is hosted on GitHub. There is an hpy-dev mailing list, though it is fairly quiet these days, and the #hpy IRC channel on freenode.net, as well. It would seem that part of the reason for the push to raise the project profile is to try to attract more developers to it.

The ideas behind HPy seem sound, but it is a sprawling project that will require a great deal of development effort to get far. The existing Python C API has hampered a number of initiatives for Python, while, of course, that same API has contributed greatly to the huge and growing ecosystem around the language. In particular, though, projects aimed at improving the performance of Python tend to run aground on the need to support the API. HPy looks like a project to keep an eye on to see how things might change in that area down the road.

Comments (none posted)

The uninvited Internet of things

The "Internet of things" (IoT), being the future paradise that awaits us when all of our devices are connected to the net, is a worrisome prospect to just about anybody who has thought about its security and privacy implications. It would be problematic even if the design of all connected devices included security and privacy as absolute requirements — but that is not the way these devices are made. Currently, it is possible to opt out of much of the IoT experience with a bit of attention and discipline. In the near future, though, that situation is likely to change and it is not clear what we can do about it.

Your editor recently moved house; part of that move involved carefully packing up the dust-covered household television set, gently transporting it to the new home, and lovingly moving it to its new location — followed by gracelessly dropping it on the floor while lifting it into place. The search for a replacement involved asking a salesman for a reasonable "non-smart" television, a request that was met with mirthful incredulity. It would appear that such things no longer exist; all televisions are built to be placed on the network now.

The abuses associated with "smart" televisions are well understood. They phone home to report on one's viewing habits. They have cameras and microphones to record the environment and send that data back home as well. This sort of antifeature was just not in your editor's vision for the new living room. The good news is that, with a WiFi-connected television, there are options. Control of the router can be used to limit the device's connectivity to the world. Or, as your editor did, one can simply ignore the devices plaintive whining and not connect it to the net at all.

Control over a device's connectivity gives a certain amount of control over its behavior. The "do not connect it at all" option is especially powerful. Amazingly, devices like washing machines, frying pans, ovens, doorknobs, etc. have worked for many years without a mothership to report to; many of them still will. Keeping them off the net can block a lot of unpleasantness.

Now consider this enthusiastic product placement on BoingBoing, which used to be a site that understood issues like privacy concerns. This particular blurb is promoting "Particle EtherSIM", which is intended to provide widespread connectivity to IoT devices. According to the text: "This is exciting and is going to open a lot of new possibilities for IoT".

One of those possibilities is certainly connectivity that is now completely outside of the control of the "owner" of these devices. The EtherSIM page is clear about this:

Over time, our cellular platform has become increasingly popular. The biggest reason for this is that cellular connectivity "just works". Wi-Fi devices have to be connected to the network by the user, which creates a lot of customer onboarding friction and often low connectivity rates (a lot of Wi-Fi devices never come online).

By putting a cellular modem and SIM directly in a device, the problem of it never coming online can be solved; it will be able to report home whether the "owner" wants it to or not. The vendor will retain control and will be able to, for example, disable the device at will. People who purchase such devices and bring them into their homes will not be able to control that connectivity; indeed, they may not ever even know that it exists.

This problem can already be seen in the area of automobiles, many of which have had their own cellular connectivity for some time. Tesla famously uses that link to track its cars, push software updates, and remotely disable features when cars are resold. Location data from many car brands is continuously fed upstream where it is put to any number of undisclosed uses, including being sold to military organizations. Some vendors give owners some control over this data stream; others explicitly do not.

Can there be any doubt that the purveyors of other connected devices will be attracted by network connectivity that does not require the customer's cooperation? The sorts of data streams that we see from cars now will soon be generated by household appliances, cameras, medical implants, lawn mowers, sex toys, water faucets, articles of clothing, and many other things that product designers are surely thinking of right now. These streams will not flow over networks we control; short of living in a Faraday cage, there will be little we can do about them. We have not begun to see the kinds of spectacular security issues, including surveillance, stalking, fraud, and repression, that will result.

The fact that most of these devices will be running Linux internally provides surprisingly little comfort, somehow.

What is to be done about this problem is far from clear. Legal approaches can be attempted; no device should phone home without explicit permission from its owner, for example. Perhaps someday we'll all have 5G femtocells that restore a bit of control within the home, at least. But getting this genie back into the bottle will not be an easy task; somehow we will need to find a way to live with it while retaining some control.

Comments (85 posted)

Patching until the COWs come home (part 2)

Part 1 of this series described the copy-on-write (COW) mechanism used to avoid unnecessary copying of pages in memory, then went into the details of a bug in that mechanism that could result in the disclosure of sensitive data. A patch written by Linus Torvalds and merged for the 5.8 kernel appeared to fix that problem without unfortunate side effects elsewhere in the system. But COW is a complicated beast and surprises are not uncommon; this particular story was nowhere near as close to an end as had been thought.

Torvalds's expectations quickly turned out to be overly optimistic. In August 2020, a bug was reported by Peter Xu; it affected userfaultfd(), which is a subsystem for handling page faults in a user-space process. This mechanism allows the handling process to (among other things) write-protect ranges of memory and be notified of attempts to write to that range. One use case for this feature is to prevent pages from being modified while the monitoring process writes their contents to secondary storage. That write can, however, result in a read-only get_user_pages() (GUP) call on the write-protected pages, which should be fine. Remember, though, that Torvalds's fix worked by changing read-only get_user_pages() calls to look like calls for write access; this was done to force the breaking of COW references on the pages in question. In the userfaultfd() case, that generates an unexpected write fault in the monitoring process, with the result that this process hangs.

The initial version of Xu's fix went in the direction of more fine-grained rules for breaking COW by GUP, as had been anticipated in the original fix, and added some userfaultfd()-specific handling. But during the discussion, Torvalds instead proposed a completely different approach, which resulted in another patch set from Xu. These patches essentially revert Torvalds's change and abandon the approach of always breaking COW for GUP calls. Instead, do_wp_page(), which handles write faults to a write-protected page, is modified by commit 09854ba94c6a ("mm: do_wp_page() simplification") to more strictly check if the page is shared by multiple processes.

With that commit in place, writes to a page without breaking COW are only allowed if the page is mapped by a single process and its reference count is not otherwise elevated (such as by an outstanding GUP). In the original vmsplice() PoC, the result is that the child process calling vmsplice() is again able to get the reference to the page shared with the parent, and retain the reference after unmapping the page from its own page tables. However, as soon as the parent tries to write to the page, the page-fault handler notices its elevated reference count and decides to break COW, giving the parent a new copy that the child cannot access. The idea and implementation is also simpler and should have performance benefits thanks to reduced page locking, as Torvalds expected and the Intel testing bot later confirmed.

Another bug was reported in September by Mikulas Patocka, who observed that running strace on a DAX filesystem (a filesystem providing direct access to the persistent memory on which it is stored) triggers a kernel warning and kills the traced process. That bug was apparently not fully analyzed for the root cause, but git bisect pointed to the same COW fix, and the patches intended to fix the userfaultfd() bug also fixed the strace bug.

Trouble with RDMA

At the time, apparently only Hugh Dickins was concerned about relying on the elevated reference count for this decision. He cited several examples where this kind of approach had created problems in the 2.6 days. His worries went unanswered, though, and the patch set was merged by Torvalds few days later; it was released in Linux 5.9-rc5. But Dickins's worries turned out to be justified; Jason Gunthorpe reported just one day later that the new approach broke the RDMA self-tests.

The problem this time appears to be that the RDMA self-test creates an anonymous private mapping and then calls a special form of GUP called pin_user_pages() which is, broadly speaking, a kernel interface allowing drivers (such as RDMA) to ensure that pages do not go away from under them while they perform data transfers to or from those pages. Then the self-test calls fork() to spawn a short-lived child. The child process does not actually touch the pages but, due to the fork() call, the page-table entries become write-protected for COW, and remain write-protected after the child exits. Further writes from the parent process to the pages are expected to modify the pages pinned for the RDMA operations. But, due to the elevated reference count, the writes result in an "unexpected" COW break, even if the process is the only one mapping the pages — a direct result of commit 09854ba94c6a.

Note that it would be possible to fix this test by calling madvise(MADV_DONTFORK) on the mapping submitted to RDMA, which would prevent that mapping from being included in the child's address space. That change would make the test more robust, because relying on the child process to exit quickly enough might be unreliable and lead to unexpected COW breaks even before commit 09854ba94c6a. However, there might be other programs that use RDMA and do not call madvise(MADV_DONTFORK) before fork(); even if these programs might not be fully robust, it would not be acceptable to break them with a kernel change. Also, as Gunthorpe noted, it is not easy to fix every RDMA (or page-pinning in general) user, even when one wants to.

The 5.9 kernel was late in the release-candidate phase at this point, so an urgent fix was needed; it eventually appeared in the form of yet another patch set from Xu. There was no fundamental change of approach this time. During a fork() call, if any pinned pages are encountered, the child will get a copy immediately instead of sharing a COW page with the parent. The test for a page being pinned is not exact and may have false-positive results if the page has a significantly increased reference count for other reasons, but copying a few more pages during fork() than is strictly needed should not hurt performance. To minimize the increased fork() overhead, a preparatory patch caused the pin_user_pages() call to mark the process with a flag indicating that the process has pinned some pages at some point; that allows the newly added checks for pinned pages to be skipped for all processes that do not call pin_user_pages() before fork(), which should be the majority of them.

With some minor follow-up fixes, the final 5.9 kernel was released in October with the RDMA issue addressed. More followup work was done to address a theoretical case where the parent process would perform page pinning in parallel with a fork() call; those patches were eventually merged for 5.11-rc1.

An unwanted holiday present

That should have concluded our saga. Shortly before Christmas, though, Nadav Amit reported a userfaultfd() self-test failure that was eventually linked by Yu Zhao to commit 09854ba94c6a. Again, a write-protected page (created by a userfaultfd() operation) was being copied due to its elevated reference count, this time leaving another CPU with a stale TLB entry pointing to the original page. The rather complicated full scenario is described in the latest version of the fix, which notes that the missing TLB flush is actually an old bug, but the more aggressive COW breaking of commit 09854ba94c6a made it visible.

A similar problem was reported by Zhao for the soft-dirty mechanism, which allows the monitoring (with low overhead but also low granularity) of which pages a process has written to. This is done by writing to the /proc/[pid]/clear_refs file, which causes all of the process's page-table entries to become write-protected. The page-fault handler then, in response to write faults, sets a soft-dirty bit in the page-table entry; these bits can be read from /proc/[pid]/pagemap to determine which pages were written to since the clear_refs operation.

Investigation of these bugs led to a long discussion during which even more issues became apparent, and there was some disagreement about the best approach to fix them. As Zhao noted, the core issue is a race between two actions within the kernel:

• The page-fault handler copying pages (where it previously wouldn't have), and
• The associated page-table entries being modified by either change_pte_range(), which is used by userfaultfd(), or clear_soft_dirty(), which handles writes to /proc/[pid]/clear_refs.

Both of the above actions happen under the mmap_lock, but that lock is taken for reading, allowing the actions to proceed concurrently. Torvalds argued that these write-protecting operations should thus simply take the mmap_lock for writing. Andrea Arcangeli was, however, unhappy about the solution, citing the absence of write locking as one of the advantages of userfaultfd() over mprotect().

Arcangeli proposed a different fix for the userfaultfd() issue; it was more complicated, but avoided taking the mmap_lock for writing. However, in the cover letter, he also argued that the page-reference-count-based test for breaking COW was still problematic and that the issues being fixed were just "the tip of the iceberg", with more breakage to be expected. Thus, he said, it would be best if all commits merged so far to fix the original vmsplice() vulnerability were reverted, and vmsplice() should become a privileged operation until specifically fixed. He also echoed Hugh's earlier worries about the approach of breaking COW depending solely on the elevated reference count, and said that, if there were issues with the "GUP causes COW break" approach of commit 17839856fd58, they should have been fixed instead. As a result, he self-NAKed his own userfaultfd() fix.

Torvalds, however, was not convinced; he noted that both approaches tried so far have corner cases, but the current one is conceptually much simpler for the core memory-management subsystem. He said that it would be better to stick to that one and deal with the exotic corner cases. Arcangeli then highlighted one concrete example of his worries by stating that the vmsplice() vulnerability becomes reproducible again after commit 09854ba94c6a if the PoC code is changed to use a transparent huge page (THP) instead of a base (4096-byte) page. He included the necessary patch for those who had access to the original reproducer, not aware that it was made public with the rest of the Project Zero issue. The author has verified that the patched PoC indeed reproduces the issue as of the 5.12-rc2 kernel.

Although the issue was acknowledged in subsequent discussion, it hasn't been fixed yet. The problem is that, while the code handling write faults on write-protected, base pages relies on the page's reference count, the THP variant relies on page_trans_huge_mapcount() which is equivalent to the page's mapping count. As explained earlier, the mapping count is equal to one after the child process unmaps the page from its own address space, even though the child retains access to the page through the vmsplice() pipe. Gunthorpe suggested that the GUP call performed by vmsplice() should be adjusted to break COW immediately — an approach that's again similar to the original fix in commit 17839856fd58, but limited only to a class of long-term pins by GUP, including those created by vmsplice(). So far, that idea doesn't seem to have been implemented; even if it were, there might be other, less obvious ways beside vmsplice() to exploit the underlying issue, although that concern might be just theoretical.

New rules

The last round of discussion so far (at least on the public mailing lists) occurred around the middle of January 2021. Arcangeli again proposed to effectively restore the state before Linux 5.8 and deal with the vmsplice() vulnerability in a different way. He included a PoC to demonstrate that, with the current page-reference-count-based approach for breaking COW, data loss can happen. A process that performs an O_DIRECT read() from a file to a buffer, while simultaneously writing (by the CPU) to a different buffer within the same page from another thread, might effectively lose the data being read if a third thread (or a different process) writes to the /proc/[pid]/clear_refs file. That constitutes an ABI break and, unlike the earlier TLB flush issues, is not fixed by taking mmap_lock for writing. He also reiterated the unfixed vmsplice() vulnerability with THPs.

Torvalds replied that, instead of the revert, the clear_refs implementation should be fixed and included a draft patch to that effect (he later merged this patch into 5.11-rc4 as commit 9348b73c2e1bf). The idea is that, if a page appears to be pinned, the clear_refs processing will simply not write-protect its page-table entry, and thus, later, the write from a CPU will not cause a page fault and COW break. Users of the soft-dirty mechanism will see the page as always dirty, which should be a fair result in the presence of DMA traffic that is allowed to write to the page. Then he expanded upon the general rules governing how to deal with pinning of pages for DMA transfers and write-protecting. They can be summarized as:

• When considering whether to just allow a write on a write-protected PTE, or to instead create a copy, and it is not certain that the process is the exclusive owner of the page, always create a copy. The elevated page reference count is an indication of not being an exclusive owner of the page.
• If the page is pinned with a cache-coherent GUP (such as for write DMA transfers) the page-table entry has to also be writable. It doesn't make sense to make it read-only if a DMA transfer can write to the page anyway.

While these rules are conceptually simple, the devil is still in the details. What if the DMA transfers are only meant for reading? Gunthorpe mentioned a virtual-machine, live-migration scenario where the machine's memory is pinned by RDMA and then clear_refs is used, presumably to detect which pages have to be migrated again because their contents changed. If clear_refs processing refuses to write-protect the pinned pages and leaves them marked as dirty, this scheme becomes inefficient, as all of the virtual machine's memory will appear to be dirty at all times. And, unlike clear_refs, userfaultfd() has not been patched at all, so in combination with RDMA, unexpected COW breaks would occur instead.

To fix these scenarios within the new COW rules, there might be better heuristics possible for determining exclusive ownership than the non-elevated page reference count or the PTE being writable. Similarly, the test for whether a page is pinned can have false positives — the function is called page_maybe_dma_pinned() after all. Several ideas were floated, such as adding a new page flag or more precise counting of both DMA pins and long-term pins, where the sub-counters would be carved out of the bits used for the general reference count. Neither idea would be easy to implement, given how packed struct page already is and the presence of known attacks for elevating the reference count and thus risking a denial of service attack if the limit on the reference count is reduced. But the discussion seems to have wound down without any concrete patches. The last statement, in the last message of the thread, from David Hildenbrand, sums it up well: "Complicated problem :)"

Are we done yet?

So where are we now? In order to fix an information-leak vulnerability with arguably limited potential for exploitation outside of Android, the 5.8 kernel was released with a major change to the COW mechanism. Due to the reported bugs, another major change was done in the 5.9 kernel and is now part of the 5.10 LTS series. More bugs have been fixed in 5.11 and a fix for the userfaultfd() TLB flushing issue seems to be on the way. However, some scenarios for using RDMA with either the soft-dirty or userfaultfd() mechanism may now be broken.

The current COW implementation is based on sound principles, and hopefully the worst corner cases have now been ironed out. So, as a result, we might have gotten to a better and more future-proof model for the copy-on-write mechanism than we had before the 5.8 kernel. Yet, given the history of this area, it would not be at all surprising to see more bug reports pop up in the future.

Somewhat ironically, the original vulnerability that triggered the whole ordeal is still exploitable when transparent huge pages are in use. At this point, a fix targeted just for vmsplice() to break COW immediately might be the safest option, especially for backporting to older LTS kernels. However, the unfixed THP vulnerability might also be a sign that transparent huge pages do not actually follow the new COW model created for base pages, and if it's not feasible to adjust them (reference counting for THPs is a complicated topic on its own), this might not be the end of the story.

[I would like to thank Jan Kara and Michal Hocko for their valuable feedback on an early version of the article.]

Comments (5 posted)

Lockless patterns: some final topics

So far, this series has covered five common lockless patterns in the Linux kernel; those are probably the five that you will most likely encounter when working on Linux. Throughout this series, some details have been left out and some simplifications were made in the name of clarity. In this final installment, I will sort out some of these loose ends and try to answer what is arguably the most important question of all: when should you use the lockless patterns that have been described here?

Data, address, and control dependencies

In the code examples that have been presented so far, the ordering of instructions in one thread was enforced either by acquire and release semantics or by memory barriers. Sometimes, however, it is simply impossible for the processor and/or the compiler to reorder instructions, because an instruction has a dependency on another instruction that comes before. In these cases, ordering between pairs of instructions is ensured even for relaxed loads and stores. These dependencies come in three forms.

Data dependencies exist when a write stores a value that comes from a previous load, or is based on such a value:

    int x = READ_ONCE(a);
    WRITE_ONCE(b, x + 1);

Data dependencies are the simplest of these three cases; the store cannot execute before the load, or the processor would not know the value that the store must write. Therefore, in this case, the read from a behaves as a load-acquire, at least with respect to the following WRITE_ONCE() statement. Unlike smp_load_acquire() or smp_rmb(), an ordering created by a data dependency is not guaranteed against all following memory operations. In the following example, the read of c might be reordered before the read of a, but the write of b cannot be:

    int x = READ_ONCE(a);
    WRITE_ONCE(b, x + 1);
    int y = READ_ONCE(c);

However, we've already seen that, most of the time, lockless code only cares about the ordering between specific memory operations; in some cases, loads can use READ_ONCE() safely because the only users of the value and the only operations that need to be ordered are data-dependent stores. That said, none of the patterns presented throughout the series have a store that follows a load in the same thread, so this optimization is not applicable.

Address dependencies exist when a read or a write operates on a location whose address comes from a previous load, or is based on such a value:

    int x = READ_ONCE(a);
    int y = READ_ONCE(b[x]);

    struct s *x = READ_ONCE(a);
    WRITE_ONCE(x->f, 1);

Address dependencies are, in theory, pretty simple as well. In the first example, the read of b[x] cannot occur prior to the read of x; in the second, the address to be written to cannot be known until the read is complete.

Similarly, in this code from part 1, the address of datum->x is only known after datum is loaded from message:

    thread 1                            thread 2
    --------------------------------    ------------------------------------
    a.x = 1;
    smp_store_release(&message, &a);    datum = smp_load_acquire(&message);
                                        printk("%x\n", datum->x);

How could the CPU fetch a value from memory, or store it, without knowing which location to operate on? Therefore, one would expect that it would be possible to write the first line of thread 2 as follows, without a load-acquire instruction:

    datum = READ_ONCE(message)

This is a reasonable expectation, and it is also true at the assembly language level for all processors that Linux has been ported to—except the Alpha, due to a peculiar cache architecture. As of version 4.15, Linux developers decided that it's okay to make READ_ONCE() more expensive on the Alpha, and therefore address-dependent loads are now always ordered after the loads they depend on. Note that address-dependent stores have never been a problem.

Finally, control dependencies exist when the value obtained by a read may cause a read or a write to not execute at all:

    int y = 0;
    if (READ_ONCE(a))
        y = READ_ONCE(b);        // *no* ordering here

    if (READ_ONCE(a))
        WRITE_ONCE(b, 1);        // write is ordered here

When a control dependency exists from one load to another load (as in the first example above), it will never introduce any ordering. A CPU can always perform the load speculatively before the test and ignore the result if the "then" branch turns out not to be executed. Control dependencies from a load to a store are the tricky ones this time. The CPU is not a problem, because the cache cannot store the new datum before it knows whether the store should actually happen; the problem is the compiler. Consider code like this:

    x = READ_ONCE(a);
    smp_store_release(&b, 1);
    if (x)
        do_something();
    else
        do_something_else();

A clever programmer might want to write it like this:

    x = READ_ONCE(a);
    if (x) {
        WRITE_ONCE(b, 1);
  	do_something();
    } else {
        WRITE_ONCE(b, 1);
  	do_something_else();
    }

and, indeed, the control dependency would cause the CPU to impose an ordering between reading a and writing b. However, the compiler could decide to hoist the writes before the conditional, and only test x afterward, leading to generated code that looks like:

    x = READ_ONCE(a);
    WRITE_ONCE(b, 1);
    if (x)
        do_something();
    else
        do_something_else();

Now the control dependency is gone and both the CPU and the compiler can move the store before a is read. As is often the case, these issues with control dependencies are solved simply by avoiding them and annotating each store properly as either acquire or release.

Of all these cases, address-dependent loads are probably the only ones that you will encounter in practice. The most common and self-explanatory case is retrieving a data structure with rcu_dereference() and srcu_dereference() and then reading its contents; on the Alpha, these RCU and SRCU primitives include the required memory barriers even on Linux versions prior to 4.15. However, you should be alert in the occasional case where RCU is not used and therefore both memory accesses use READ_ONCE().

Optimized memory barriers

Part 5 introduced atomic read-modify-write operations such as atomic_inc(). Linux defines operations that do not return a value to have relaxed semantics. Failed compare-and-swap operations also do not imply any memory barrier, while a successful compare-and-swap behaves as if the programmer had written a memory barrier on each side of the operation.

Some processors, however, do not have an instruction for a relaxed, read-modify-write operation. On those processors, writing something like this (a variation on the full memory barrier pattern from part 3) would be wasteful, with set_bit() (which must read the target location in order to change only the specified bit) and smp_mb() providing back-to-back memory barriers:

    set_bit(&flag1, FLAG_DONT_SLEEP);
    smp_mb();
    if (READ_ONCE(wake_me))
        wake(thread2);

For this purpose, Linux defines the optimized memory barriers smp_mb__before_atomic() and smp_mb__after_atomic(). They compile as either compiler-only barriers or full memory barriers, depending on architecture-specific details in the implementation of atomic read-modify-write operations. For example, all x86 read-modify-write operations imply a barrier on each side, therefore these optimized memory barriers are a compiler-only barrier on that architecture. On ARM, instead, it is possible to define relaxed read-modify-write operations and, therefore, the optimized memory barriers will emit a dmb instruction. They are used as a drop-in replacement for smp_mb():

    set_bit(&flag1, FLAG_DONT_SLEEP);
    smp_mb__after_atomic();
    if (READ_ONCE(wake_me))
        wake(thread2);

Another optimized memory barrier is smp_store_mb(), which is a replacement for WRITE_ONCE() followed by smp_mb(). For example:

    thread 1                               thread 2
    -------------------                    --------------------------
    smp_store_mb(dont_sleep, 1);           smp_store_mb(wake_me, 1);
    if (READ_ONCE(wake_me))                if (!READ_ONCE(dont_sleep))
        wake(thread2);                         sleep();

When to use lockless patterns?

Even though the previous installments of this series tried to use actual Linux kernel code in the examples, one could say that they only showed the theory. While the material in the articles should be enough to understand existing code, there was very little explanation of when to employ these patterns and why.

One thing that I did try to stress throughout the series is that lockless techniques are not an alternative to traditional synchronization primitives. They are only a means to an end, which is to limit the cost of synchronization (cacheline contention is also a kind of synchronization; it just happens in the processor rather than in your code). Expensive synchronization in concurrent code cannot be eliminated, but it is possible to limit the number of expensive instructions, or to move them out of the hottest paths. To this end, some design points that you should consider are:

• The interaction with existing locks and shared data accesses.
• The frequency of writes to shared data: every time a thread writes to a shared location, cache coherency traffic can end up creating a potential scalability bottleneck.
• The frequency of synchronization: the best way to keep multiple threads going is for them to be as independent as possible, because synchronization will always introduce overhead.

Let's say you want to gather some statistics while your code runs, for example counting how many packets are sent through a network interface, and you want the overhead to be minimal. Before rushing to implement the counter in a lockless manner, for example with an atomic increment instruction, you should investigate the ways in which sending a packet can be serializing. If sending a packet already takes a spinlock or mutex, for example, there is likely no performance to gain from a fancy implementation of the counter: if you ensure that the counter resides in a cache line that is already needed when sending a packet, incrementing a single memory location while the lock is already held will be almost free.

If there is no single lock that is always taken when sending a packet, lockless techniques may indeed be beneficial, but there's much more to them than atomic read-modify-write operations. For example, you could use multiple counters, so that you can increment them without a lock (making them per-CPU) or under a lock that you already take (say, per network queue). The counters can be summed in the (presumably rare) event of someone reading the statistics: this solution avoids concurrent writes to shared data and does not need any additional synchronization on the hot path.

In the example above, a coarse lock—for example, a lock that covers the operation of a network queue—does not necessarily imply loss of scalability: in a system that is designed to keep the threads mostly independent, contention on coarse locks will often be rare or nonexistent. Conversely, papering over an excessive amount of shared-data access with fine-grained locks can increase the cost of synchronization substantially, and bring performance down.

The cost of fine-grained locking is especially visible with read/write locks, where even the read side needs to write to the lock in order to take it. When writing scalable code, it can be useful to think of read/write locks as "shared/exclusive" locks. You can use coarse read/write locks to make sure that only hot paths have to handle concurrent execution: if less frequently executed code takes the lock for exclusive access, any lockless fast paths need not take that code into account at all. An example of this is the Linux mmap_sem; Linux performs many page table manipulations while holding it for "reading". But still, the relatively high cost of taking mmap_sem for reading has made it a known problem for scalability.

If fine-grained locking is needed for specific data structures, writes to these data structures will usually be rare in a scalable system. Instead of a read/write lock, you can try to protect the read-side critical sections with mechanisms such as seqlocks or RCU. SRCU can also be an interesting alternative to RCU whenever writers cannot bear the cost of synchronize_rcu() (think of it as subsystem RCU, not just sleepable RCU).

Even if the threads operate independently, there may be rare cases where they have to interact. In an implementation that needs to check a flag thousands or millions of times a second, taking a fine-grained lock around each check, the cost might become visible no matter how small and rare these interactions are. In these cases, applying lockless techniques to the fast path can be valuable.

For example, you could give each thread a queue of requests from other threads and manage them through single-consumer linked lists. Perhaps you can trigger the processing of requests using the cross-thread notification pattern from the article on full memory barriers. However, these techniques only make sense because the design of the whole system supports them. In other words, in a system that is designed to avoid scalability bottlenecks, common sub-problems tend to arise and can often be solved efficiently using the patterns that were presented here.

When seeking to improve the scalability of a system with lockless techniques, it is also important to distinguish between lock-free and wait-free algorithms. Lock-free algorithms guarantee that the system as a whole will progress, but do not guarantee that each thread will progress; lock-free algorithms are rarely fair, and if the number of operations per second exceeds a certain threshold, some threads might end up failing so often that the result is a livelock. Wait-free algorithms additionally ensure per-thread progress. Usually this comes with a significant price in terms of complexity, though not always; for example message passing and cross-thread notification are both wait-free.

Looking at the Linux llist primitives, llist_add() is lock-free; on the consumer side, llist_del_first() is lock-free, while llist_del_all() is wait-free. Therefore, llist may not be a good choice if many producers are expected to contend on calls to llist_add(); and using llist_del_all() is likely better than llist_del_first() unless constant-time consumption is an absolute requirement. For some architectures, the instruction set does not allow read-modify-write operations to be written as wait-free code; if that is the case, llist_del_all() will only be lock-free (but still preferable, because it lets the consumer perform fewer accesses to the shared data structure).

In any case, the definitive way to check the performance characteristics of your code is to benchmark it. Intuition and knowledge of some well-known patterns can guide you in both the design and the implementation phase, but be ready to be proven wrong by the numbers.

I'll conclude this series with a quote of Dave Chinner's excellent critique:

This is the art of concurrent programming—it's not enough just to know what a lockless algorithm is, you need to understand the data access patterns those algorithms result in and when those access patterns are going to become a limitation to the software. Of course, knowing when not to use a lockless algorithm because there are better ways to reduce shared data access is also part of the art.

Comments (2 posted)

GDB and io_uring

A problem reported when attaching GDB to programs that use io_uring has led to a flurry of potential solutions, and one that was merged into Linux 5.12-rc5. The problem stemmed from a change made in the 5.12 merge window to how the threads used by io_uring were created, such that they became associated with the process using io_uring. Those "I/O threads" were treated specially in the kernel, but that led to the problem with GDB (and likely other ptrace()-using programs). The solution is to treat them like other threads because it turned out that trying to make them special caused more problems than it solved.

Stefan Metzmacher reported the problem to the io-uring mailing list on March 20. He tried to attach GDB to the process of a program using io_uring, but the debugger went "into an endless loop because it can't attach to the io_threads". PF_IO_WORKER threads are used by io_uring for operations that might block; he followed up the bug report with two patch sets that would hide these threads in various ways. The idea behind hiding them is that if GDB cannot see the threads, it will not attempt to attach to them. Prior to 5.12, the threads existed but were not associated with the io_uring-using process, so GDB would not see them.

It is, of course, less than desirable for developers to be unable to run a debugger on code that uses io_uring, especially since io_uring support in their application is likely to be relatively new, thus it may need more in the way of debugging. The maintainer of the io_uring subsystem, Jens Axboe, quickly stepped in to help Metzmacher solve the problem. Axboe posted a patch set that included a way to hide the PF_IO_WORKER threads, along with some tweaks to the signal handling for these threads; in particular, he removed the ability for them to receive signals at all.

That made Eric W. Biederman somewhat uncomfortable; he asked why the io_uring threads could not take signals, and SIGSTOP in particular. In order to attach to a running process, ptrace() uses SIGSTOP, but the I/O threads lack much of the normal user-space context that would allow handling signals. Linus Torvalds explained that signal handling is done when a thread returns to user space, but that does not happen for kernel threads; he described that further in another message:

SIGSTOP handling is fundamentally done at signal handling time, and signal handling is fundamentally done at "return to user space" time.

End result: you cannot send kernel threads any signals at all, unless it _explicitly_ handles them manually. SIGSTOP isn't different from user space delivery of an "actual" signal handler in this respect.

And practically speaking, the only signal a kernel thread generally can handle is SIGKILL (and exit on it).

[...] I really think IO threads need to not participate, because they simply cannot handle signals in any sane manner.

A few days later, Axboe posted another version of the patch set with a longer description of the problem and the proposed solution:

Stefan reports that attaching to a task with io_uring will leave gdb very confused and just repeatedly attempting to attach to the IO threads, even though it receives an -EPERM every time. This patchset proposes to skip PF_IO_WORKER threads as same_thread_group(), except for accounting purposes which we still desire.

We also skip listing the IO threads in /proc/<pid>/task/ so that gdb doesn't think it should stop and attach to them. This makes us consistent with earlier kernels, where these async threads were not related to the ring owning task, and hence gdb (and others) ignored them anyway.

But it seems those patches went a bit too far; Biederman pointed out that the threads would no longer show up in /proc at all, which would hide them from top and other diagnostic tools. Torvalds noted that it also hides them from ps, which makes him "think that hiding them is the wrong model". There was some discussion of putting the threads under a different name in the /proc hierarchy, but Axboe thought it might work for some utilities but would likely "mess up _something_". Biederman said that there needed to be some mechanism to tell GDB (and other debuggers) that these threads are special: "I suspect getting -EPERM (or possibly a different error code) when attempting attach is the right [way] to know that a thread is not available to be debugged."

Axboe mentioned in the patch cover letter that the underlying problem might really be a GDB bug and Biederman seemed to agree, but Oleg Nesterov took exception to that: "The kernel changed the rules, and this broke gdb." But Biederman argued that it was not strictly a regression; "It is gdb not handling new functionality." Though, even if it was a GDB bug, Axboe said, it simply takes too long for updates to GDB to make their way to users to fix things that way; beyond that, "I doubt that gdb is the only thing that'd fall over, not expecting threads in there that it cannot attach to."

So, some kind of solution where everything "just works" was desired—and that is seemingly exactly what Torvalds came up with:

Actually, maybe the right model is to simply make all the io threads take signals, and get rid of all the special cases.

Sure, the signals will never be delivered to user space, but if we

• just made the thread loop do "get_signal()" when there are pending signals
• allowed ptrace_attach on them

they'd look pretty much like regular threads that just never do the user-space part of signal handling.

The whole "signals are very special for IO threads" thing has caused so many problems, that maybe the solution is simply to _not_ make them special?

Axboe agreed that it made more sense to "just embrace the signals, and have everything just work by default". To that end, he tried attaching GDB after making changes along those lines and was successful. That led to version 1 of the "allow signals for IO threads" patch set on March 25 and, after a few fixes, version 2 on March 26. The latter was promptly picked up for 5.12-rc5 on March 28; it also reverts some of the earlier attempts at fixes that had been picked up for 5.12-rc4 a week earlier.

The idea is that the I/O threads simply take signals like other threads and processes rather than be a special case, which cleans things up substantially. As Axboe put it in the cover letter of the first version, it is plain to see in hindsight:

As with most other good ideas, it's obvious once you hear it. The fact that we end up with _zero_ special cases with this is a clear sign that this is the right way to do it indeed. The fact that this series is 2/3rds revert further drives that point home.

In the end, it would seem that a much better solution came about; at least in part by Torvalds stepping back and reconsidering some of the assumptions. While PF_IO_WORKER threads cannot really do anything with signals that get sent to them, there is no real need to reject them either. Once that was recognized, the patches were fairly straightforward it seems. And, meanwhile, an unpleasant situation for developers of io_uring-using code was avoided.

Comments (3 posted)