Kernel development

Kernel release status

The 3.20/4.0 merge window remains open, so there is no current development kernel. The flow of patches into the mainline repository continues; see the separate article below for details.

Stable updates: none have been released in the last week.

Comments (none posted)

Quotes of the week

— Alan Cox

— Steven Rostedt

Comments (1 posted)

3.20 merge window part 2

As of this writing, 7,849 non-merge changesets have been pulled into the mainline repository for this development cycle; about 4,200 of those have come in since last week's summary was written. Some of the more interesting user-visible changes found in those 4,200 patches include:

• The parallel NFS (pNFS) subsystem has gained support for the under-development FlexFile layout. This layout allows file metadata to be stored in a different location from the file contents.

• The persistent storage subsystem can optionally provide a new special file (/dev/pmsg0) allowing user-space programs to log data into the store.

• The Smack security module can now interface with the netfilter system, using security labels to filter packets.

• The ubifs filesystem now has multiqueue block layer support (increasing its performance) and support for security.* extended attributes (making security module support possible).

• The Android binder code has been equipped with security hooks allowing it to be brought under SELinux (or any other security module) policies.

• The I2O bus subsystem has been moved into the staging directory with the idea of removing it from the kernel entirely in the near future. As far as the developers can tell, nobody is using this code; if that impression is mistaken, now would be a good time to say something.

• See this posting for a description of the changes to the Intel graphics driver in this development cycle.

• The nonvolatile memory support patches have been merged, making it possible to host filesystems in persistent memory with good performance.

• The PA-RISC architecture is no longer able to run 32-bit HP-UX binaries. The number of users upset by this change is expected to be small.

• The lazytime filesystem option (with support in ext4, initially) has been merged. Lazytime allows accurate tracking of file access times without creating lots of write I/O to the filesystem.

• New hardware support includes:
  • Systems and processors: IBM s/390 z13 processors, Artesyn MVME2500 single board computers, Conexant Digicolor SoCs, NVIDIA Tegra132 SoCs, Freescale LS2085A SoCs, and Mediatek MT65xx & MT81xx ARMv8 SoCs,

  • Graphics: ATMEL HLCDC display controllers and Samsung Exynos7 SoC display controllers. Also, the "fbtfb" subsystem has been added to the staging tree; it provides support for a wide range of small TFT LCD display modules.

  • Industrial I/O: Solteam Opto JSA1212 proximity and ambient light sensors, Kionix KMX61 6-axis accelerometer/magnetometers, Freescale MMA9551L intelligent motion sensors, Freescale MMA9553L intelligent pedometers, Semtech SX9500 proximity sensors, Capella Microsystems cm3232 ambient light sensors, Qualcomm SPMI PMIC voltage analog-to-digital converters (ADCs), Cosmic Circuits 10001 ADCs, and Samsung Sensorhub microcontroller units.

  • Miscellaneous: APM X-Gene GPIO standby controllers, Fujitsu MB86S7x GPIO controllers, Altera mailbox units, Version 2.0 Trusted Platform Modules (TPMs), Abracon AB-RTCMC-32.768kHz-B5ZE-S3 realtime clocks, Armada 38x Marvell SoC realtime clocks, ETRAX FS serial ports, Alphascale ASM9260 timers, Rockchip rk3288 timers, Conexant Digicolor timers, and Dallas/Maxim DS1685 realtime clocks.

  • Pin control: Allwinner A31s SoC pin controllers, Amlogic Meson SoC pin controllers, and Xilinx Zynq pin controllers, Qualcomm 8916 pin controllers.

  • USB: Rockchip USB2 PHYs and NXP ISP1761 USB device controllers.

Changes visible to kernel developers include:

• The ARM I/O memory-management unit (IOMMU) layer has a new, generic page-table management API. See drivers/iomu/io-pgtable.c and io-pgtable.h for an overview of this API.

• The LED subsystem now has a new device class for LEDs operating in the "flash" (as in camera flash) mode.

• The kernel address sanitizer (KASan) has been merged. KASan monitors kernel memory references in an attempt to catch code reaching into memory it has no business touching. For now, KASan only works on the x86_64 architecture, and memory hotplug must be disabled.

• Developers working with the GDB debugger may want to look at the new set of helper scripts added under scripts/gdb.

• The printk() family of functions has a new format type (%pb) for the printing of bitmaps. The number of bits in the bitmap must be specified as the field width in the format string.

So far, this development cycle seems to be a relatively slow one, as was suggested before the merge window opened. Still, the emphasis should be on "relatively"; nearly 8,000 patches is not a small number.

The version number for this kernel is yet to be determined. Linus ran a poll on Google+ that came out in favor of calling it 4.0, but he has not said what he will actually do. Tune in next week for the final changes that come in for this cycle and, presumably, an answer to the naming question.

Comments (1 posted)

Epoll evolving

Epoll is a set of Linux-specific system calls intended to provide fast polling for large numbers of file descriptors. The API has been in use since it was merged during the 2.5 development series but, like many interfaces, there is always room for improvement. There are currently two patch sets making the rounds that would add functionality to this set of system calls.

An epoll overview

Epoll is designed to function somewhat like select() or poll(), but with more options and with higher performance when large numbers of file descriptors are in use. Each call to select() or poll() can involve an entirely new set of file descriptors, so the kernel must go through the process of validating each one, checking for I/O readiness, and adding the polling process to the appropriate wait queue. But the actual list of file descriptors tends not to change much between calls, so much of that work is unnecessary duplicated effort. The epoll calls get around this problem by separating that setup work from the act of waiting for a file descriptor to become ready.

A process using this API must begin by creating a special file descriptor to use with polling; that is done with a call to one of:

    #include <sys/epoll.h>

    int epoll_create(int size);
    int epoll_create1(int flags);

Either call will return a file descriptor to be used with the remaining epoll functions. The size parameter to epoll_create() is no longer used; the flags argument added for epoll_create1() can be used to set the close-on-exec flag for the resulting file descriptor.

The next step is to add all of the file descriptors that are to be monitored, using:

    int epoll_ctl(int efd, int op, int fd, struct epoll_event *event);

If op is EPOLL_CTL_ADD, the given fd will be added to the set. The event parameter is used to describe which events will be polled for; see the man page for details. epoll_ctl() can also be used to remove file descriptors or to modify how the polling is done.

Finally, actually waiting for one of the file descriptors in the set to become ready is done with:

    int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
    int epoll_pwait(int epfd, struct epoll_event *events, int maxevents, int timeout,
                    const sigset_t *sigmask);

The events that cause epoll_wait() to return (up to maxevents) will be stored in the events array; the timeout parameter is specified in milliseconds. The epoll_pwait() version also allows the specification of a set of signals to be blocked (or unblocked) during the call. Again, see the man page for details.

epoll_ctl_batch() and epoll_pwait1()

This patch set from Fam Zheng introduces two new system calls to the epoll family. The first of these addresses a performance problem that comes up in situations where it is often necessary to make changes to the file descriptors in the epoll set. A call to epoll_ctl() can only add, modify, or delete a single file descriptor; if a lot of descriptors need to be changed, there will need to be a lot of epoll_ctl() calls to get that work done. The proposed epoll_ctl_batch() system call gets around that problem by processing multiple file descriptors in a single call:

    int epoll_ctl_batch(int epfd, int flags, int ncmds, struct epoll_ctl_cmd *cmds);

The cmds structure essentially duplicates all of the arguments that would have been passed to an epoll_ctl() call. By passing an array of these structures, a program can perform operations on multiple file descriptors with a single system call.

Fam's other change is to add a new system call to perform the actual polling:

    struct epoll_wait_params {
	int clockid;
	struct timespec timeout;
	sigset_t *sigmask;
	size_t sigsetsize;
    };

    int epoll_pwait1(int epfd, int flags,
                     struct epoll_event *events, int maxevents,
                     struct epoll_wait_params *params);

This version of epoll_wait() adds a new flags parameter, but does not define any flag values, so flags must be zero. The parameters shuffled off into the params structure are mainly intended to give the application more control over timeout processing. The millisecond-resolution timeout understood by epoll_wait() has proved to be too coarse for a number of use cases. The new system call defines a timeout with nanosecond resolution, getting around that problem.

Better multi-threaded behavior

Jason Baron (of Akamai) has run into a different problem that only comes up with a relatively uncommon usage pattern. Normally, there will only be one process using a polling function to monitor a given file descriptor. But, in Jason's use case, there can be multiple threads, each of which is using epoll to track the same set of file descriptors. In this setting, an event on any given file descriptor will cause all of the waiting processes to wake up, even though only one of them will be able to actually handle the event. This thundering-herd problem is something that Jason would like to avoid.

His response is this patch adding a couple of new flags to be attached to file descriptors via epoll_ctl(). The first of these, EPOLLEXCLUSIVE, requests that only one process be woken up to handle an event on the associated file descriptor. Internally, the change is a simple matter of using add_wait_queue_exclusive() instead of add_wait_queue() when setting up the polling. Obviously, all processes polling the same file descriptor would have to use the exclusive mode to get down to a single wakeup per event.

That change did not entirely solve Jason's problem, though, in that it ended up with the same process waking up in response to each event. Since one of the reasons for epoll's existence is to allow processes to be left on all of the file-descriptor-specific wait queues between calls to epoll_wait(), the process that is at the head of any given queue will remain there. It will thus be the one to receive all of the exclusive wakeups. But the whole point of having multiple processes polling the same file descriptor is to spread the work around; waking the same process every time thwarts that objective. To deal with that, Jason added another flag, called EPOLLROUNDROBIN, that causes the kernel to work through each of the polling processes in turn.

Support for this mode was added to the scheduler in the form of a new wait queue function:

    void add_wait_queue_rr(wait_queue_head_t *q, wait_queue_t *wait);

When waiting is done using add_wait_queue_rr(), only a single process will wake, just like with add_wait_queue_exclusive(). But, in addition, the process at the head of the wait queue will be moved to the tail, so it will not see another wakeup until all of the other processes have had their turn.

Jason's patch posting includes results from a little benchmark program showing a nearly 50% reduction in execution time when the exclusive mode is used. When there are a lot of wakeups happening (as can be the case for many network-oriented workloads), the extra overhead caused by thundering herds can be crippling.

Both patches have received a fair number of review comments, and Fam's patches in particular have evolved quite a bit since the first posting in January. Your editor's unscientific impression is that API-related patches are getting more attention than they once did. That, of course, would be a good thing; APIs live forever, so it's better to get them right before shipping them to users and being committed to supporting them forever. These patches seem close to being ready, though; they might make an appearance in the next merge window.

Comments (9 posted)

Creating scalable APIs

Non-scaling APIs—those that perform poorly on systems with large numbers of CPUs—are a painful fact of life, an unavoidable consequence of many of these APIs having been created on uniprocessors by people with little or no experience with parallelism. However, designing scalable APIs can be a challenge even for those of us with significant parallel-programming experience.

Therefore, it should come as no surprise that Austin T. Clements's Ph.D. dissertation [PDF] entitled “The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors” received a well-deserved SIGOPS Dennis M. Ritchie award in 2014. The most important points are covered in the corresponding 2013 Symposium on Operating System Principles (SOSP) paper [PDF] and ACM Transactions on Computer Systems (TOCS) article (both co-authored by M. Frans Kaashoek, Nickolai Zeldovich, Robert T. Morris, and Eddie Kohler), which are further summarized here. This work resembles the Laws of Order paper covered by an LWN article back in 2011. However, as you might guess from the name, the scalable commutativity rule is concerned with scalability, in contrast with the memory-barrier focus of Laws of Order.

Overview of the scalable commutativity rule

We all learned about the commutative law of addition, which states that X + Y gives the same value as Y + X, for all possible values of X and Y. The scalable commutativity rule uses a more general definition of commutativity that encompasses the order of execution of concurrent operations as well as the order of arguments to a single operator or function. For example, suppose that one CPU atomically adds the value X to variable A at about the same time that another CPU atomically adds the value Y to this same variable. Because addition is commutative in this more concurrent sense, we know that regardless of the order of execution, the overall effect will be to add X + Y to A.

The key insight behind the scalable commutativity rule is that if the ordering of a pair of operations is irrelevant according to the API, then it should be possible to implement those operations so as to avoid scalability bottlenecks. In contrast, if the ordering of the two operations is critically important, then it is most likely impossible to avoid the bottlenecks between these operations.

For example, suppose that the two operations are inserting two objects, each with its own key, into a search data structure not already containing elements with those keys. Suppose further that this structure does not allow duplicate keys. No matter which of the two operations executes first, the result is the same: both objects are successfully inserted. Therefore, the scalable commutativity rule holds that a scalable implementation is possible, and there is, in fact, a wealth of scalable implementations of search structures, ranging from hash tables to radix trees to dense arrays.

In contrast, suppose that the two operations are inserting two objects with the same key into a search data structure that does not already contain an object with that key. Now the order is critically important, because the first operation will succeed and the second will fail. That operation is unlikely to be scalable. For example, in a hash table with per-bucket locking, both operations would attempt to acquire the same lock, thus preventing them from executing concurrently.

But pure mathematical commutativity requires that a given pair of concurrent operations always give the same result, regardless of not only execution order, but also initial state and argument values. This means that pure mathematical commutativity is too restrictive to be useful for predicting scalability in practice. For example, conditional lock acquisition is non-commutative from a pure mathematical viewpoint because if two CPUs attempt to conditionally acquire a given lock at the same time, one of the CPUs will acquire the lock and the other will get a failure indication. Which CPU acquires and which gets a failure indication depends on the order of execution, hence the non-commutativity from a pure mathematical viewpoint.

Of course, in practice, we usually work hard to make sure that different CPUs are attempting to acquire different locks, and in this case, conditional lock acquisition is independent of execution order. In other words, from a pure mathematical viewpoint, conditional lock acquisition is not commutative, but for common use cases in practice, it commutes—and scales—just fine. The authors therefore define a alternative notion of commutativity that is state-dependent, interface-dependent, and monotonic, which they abbreviate as “SIM commutativity”. Because this type of commutativity depends on the values of the arguments of the function in question (unlike mathematical commutativity), conditional locking is SIM commutative because if the two CPUs are acquiring different locks, the results will be independent of the order of acquisition. This definition is, therefore, compatible with the long-standing parallel-programming advice to “lock data, not code.”

API analysis and the Linux kernel

As with the Laws of Order, a key strength of the scalable commutativity rule is that it can be applied to an API, even before the implementation is written. In fact, the authors have constructed a tool named Commuter that can analyze whether or not a given API is SIM commutative. They applied this tool to a subset of 18 POSIX system calls, which produced no fewer than 13,664 test cases exercising commutative pairs of operations.

Of course, the fact that an API is commutative does not necessarily mean that a given implementation scales. For example, a kernel that relied solely on a Big Kernel Lock for synchronization would not scale well regardless of the API. Therefore, the authors also created a tool named mtrace that, in conjunction with other tools described in Section 5 of the SOSP paper, analyzes the Linux kernel to find bottlenecks that the scalable commutativity rule indicates could be avoided. This set of tools uses a modified version of QEMU to carry out this analysis, and take the test cases mentioned earlier as input.

The Linux kernel did surprisingly well, avoiding violations of the scalable commutativity rule for 9,389 of the 13,664 test cases, or almost 70% of them. But the authors figured that it was possible to do better. Unfortunately, their time budget did not permit them to rewrite the Linux kernel, so they instead created a research OS kernel named sv6. This kernel avoided violations of the scalable commutativity rule for 13,528 of the 13,664 test cases, or more than 99% of them.

API analysis and POSIX

The authors' tool also identifies POSIX operations that do not commute, which thus might be harder to implement scalably. One example is fork(), which copies an entire process, thus failing to commute with pretty much anything that process might do. This is, of course, especially painful when invoking fork() from a multithreaded process. This can be particularly annoying if the child immediately does an exec(), thus rendering almost all fork()-based non-commutativity irrelevant. They suggest using the obscure posix_spawn() in place of fork()/exec() because posix_spawn() is equivalent to those two calls but is much more commutable.

The authors also call out the non-commutativity inherent in the POSIX rule requiring that open() return the lowest-numbered available file descriptor. They point out that this non-commutativity could be eliminated via an O_ANYFD flag to open(). These and other suggestions are described in the next section.

Design and implementation guidance

Sections 4 and 6.3 of the SOSP paper provide some design and implementation guidance.

Decompose compound operations. The paper gives two examples of commutativity-challenged compound operations: fork() and stat(). As noted above, the fork() system call copies a process, and most of the time most of this work is discarded by a subsequent exec(). However, all this copying causes fork() to be non-commutative with everything from memory writes to open() and close() system calls. Decomposing the fork() system call to eliminate most of the doomed copy operations, and then combining it with exec() results in something called posix_spawn(), which avoids much of the fork() system call's non-commutativity. In theory, then, posix_spawn() should be much more scalable than is fork().

Similarly, the stat() system call returns so much information on the specified file that it becomes non-commutative with almost any access to that same file—and most of the information is ignored by any particular caller. Providing a way to return only the information of interest would greatly increase commutativity, and should, in theory, increase scalability.

In practice, it is not clear that the non-commutativity of fork() and stat() are the most urgent bottlenecks in the Linux kernel. On the other hand, Figure 7 of the SOSP paper does show some benchmark results that indicate that the Linux kernel does have some potential room for improvement.

Embrace specification non-determinism. Interestingly enough, this was one of the loopholes to the Laws of Order, which reappears here as a way to improve the commutativity of APIs in order to permit more highly scalable implementations. Here, the authors take aim at the POSIX standard's insistence that open() and friends return the lowest-numbered available file descriptor, which was mentioned above. Although this restriction was helpful back in the days of 16-bit Unix systems that lacked the dup2() system call, for almost all of us, those days are thankfully long gone. This requirement makes a pair of concurrent open() calls non-commutative, thus imposing a limit on scalability. In contrast, if open() and friends were permitted to return an arbitrarily selected file descriptor, then file descriptor allocation would not necessarily impose a scalability bottleneck.

Permit weak ordering. This was another of the loopholes to the Laws of Order, which reappears here as another way to improve the commutativity of APIs in order to permit more highly scalable implementations. The paper gives the example of strict ordering of messages sent on Unix-domain sockets, especially for the SOCK_DGRAM sockets where the user might have neither need nor desire for any sort of ordering. Presumably, weak ordering would also help in the case of the stat() system call.

Release resources asynchronously. Asynchronous freeing of memory is, of course, used heavily by read-copy update (RCU), but the authors note that it also applies in many other cases. For example, an munmap() system call executed in a multithreaded process requires synchronous TLB shootdowns in order to prevent other threads from doing “doomed” writes to memory that is in the process of being unmapped. This, in turn, means that the munmap() system call cannot commute with a memory write to the unmapped region, again imposing a limit on scalability. The authors suggest that an madvise() flag be provided to allow asynchronous munmap(), increasing commutativity and, in turn, potentially increasing performance and scalability.

Layer scalability. The authors note that their research operating system's filesystem uses scalable data structures with naturally commutative operations. Doing this at each layer of the software stack would clearly make it easier to get good results further up the stack.

Defer work. To the best of my knowledge, this good advice was first stated in Alexia Massalin's dissertation [.ps.gz]. However, the advice bears repeating, and the authors describe its application to generating unique identifiers (specifically inode numbers). Their approach uses a per-CPU counter concatenated with the ID of the CPU generating the identifier. This approach ensures that these identifiers never repeat, and thus that each CPU can safely generate inode numbers without any sort of synchronization with the other CPUs. Deferring the synchronization ensures that identifier generation need never be a scalability bottleneck.

Compatibility considerations might make this approach to identifier generation difficult to apply in some cases, but the general approach of deferring work can be quite useful. For but one example, work deferral is used heavily by RCU.

Precede pessimism with optimism. The idea here is to have a highly scalable optimistic stage followed by a less scalable, more general, and hopefully rarely used pessimistic stage. The paper gives double-checked locking as one example, and handling of special cases of the rename() system call as another. However, many other examples of this approach come to mind, for example, the per-CPU-cached memory allocators within the Linux kernel. This design approach has also been called “parallel fastpath”, for example here and in Section 6.4 of my book, Is Parallel Programming Hard, And, If So, What Can You Do About It?.

Don't read unless necessary. Most kernel hackers avoid unnecessary writes in order to avoid the resulting cache misses, but the authors point out that unnecessary reads can also limit scalability, especially if safely carrying out the read requires acquiring locks. They give pathname lookup as an example, pointing out that a typical implementation of the old-school Unix namei() function (lookup_fast() and lookup_slow() in the Linux kernel, though still living in namei.c) returns the inode in addition to checking whether the pathname exists. The fact that it returns the inode makes it non-commutative with a number of other operations, including rename(). The sv6 research OS's ScaleFS therefore provides a separate internal interface that checks for the pathname without accessing the inode in order to avoid this potential scalability bottleneck.

This is a good list of scalability techniques, and most of them focus on promoting commutativity, at least in the common case. However, embrace specification non-determinism, permit weak ordering, and defer work represent a different approach that is discussed in the next section.

Scaling despite non-commutativity

The scalable commutativity rule states that whenever interface operations commute, they can be implemented in a way that scales. It is tempting to assume that the inverse rule also applies, namely, that whenever interface operations fail to commute, there can be no scalable implementation. However, the inverse does not always apply, as evidenced by the following exceptions:

1. If the hardware provides a register containing a fine-grained, strictly increasing time, objects could be scalably “updated” by using a timestamped per-thread log.
2. If the hardware allows certain communications patterns to scale, then non-commutative operations using those patterns might scale. In our search-structure example, a hardware content-addressable memory might allow a search structure to be constructed that scaled well even with concurrent operations on the same key.
3. If the algorithm can tolerate weak ordering, then permit weak ordering in order to decouple mechanisms that would otherwise impose a non-commutativity scalability bottleneck on the system.
4. If the algorithm can tolerate non-determinism, then embrace specification non-determinism in order to decouple mechanisms that would otherwise impose a non-commutativity scalability bottleneck on the system.
5. If the algorithm can tolerate latency, then defer work in order to avoid scalability bottlenecks by delaying potentially conflicting operations until there is no longer the potential for contention.

There have been any number of efforts to provide hardware acceleration in order to take advantage of the first and second exceptions. RCU and some forms of scalable counters take full advantage of the third, fourth, and fifth exceptions. The first and second exceptions to the inverse are also exceptions to the scalable commutativity rule itself because they invalidate hardware assumptions underpinning the formal proof of that rule.

Given that both RCU read-side critical sections and counter addition are commutative, it is quite reasonable to ask why they would need to take advantage of any of these exceptions.

For RCU, the problem is that although RCU readers commute with each other, they do not commute with grace periods: If a given rcu_read_lock() executes just before a given synchronize_rcu() begins, then that synchronize_rcu() must wait on the RCU read-side critical section started by that rcu_read_lock(). If the order of these two operations is reversed, then synchronize_rcu() need not wait. RCU can nevertheless avoid scalability bottlenecks by delaying both the beginnings and the ends of grace periods. This permits batching, which allows the overhead of a given grace-period operation to be amortized over an arbitrarily large number of updates, thus providing excellent scalability despite the non-commutativity.

Similarly, although a pair of additions to a given counter are commutative, additions to a counter do not commute with reads from that counter. Also, if you run a “scalable” counter on a large system with (say) 50% updates and 50% reads, the results probably will not be pretty and definitely will not be scalable. However, this scalability bottleneck can be avoided by allowing counter reads to return outdated values for the counter, in effect adding a delay between the time an update happens and the time it is visible to readers. This added delay allows readers to fetch the value of a single counter that is periodically updated at a rate low enough to avoid scalability problems, as described in Section 5.2.4 of Is Parallel Programming Hard, And, If So, What Can You Do About It?.

Conclusions

This does raise a question as to how severe non-commutativity problems really are and, of course, one ready answer is: “Clearly not severe enough to have been addressed yet”. That said, one great benefit of this work is that it allows developers to more easily determine whether a bottleneck is inherent in the API, or whether it is the fault of the implementation. Another welcome aspect of this paper is the discussion of ways to avoid non-commutativity bottlenecks, as is the demonstration of the benefits of avoiding these bottlenecks in the guise of the sv6 research OS. Finally, this paper has the virtue of making it quite clear exactly what is and is not commutative.

If I was to identify a shortcoming of this paper, it would be that the existence of non-commutativity (or perhaps non-scalable non-commutativity?) does not necessarily translate into a serious bottleneck. For example, a given instance of non-commutativity might only become a bottleneck for 1,000,000-CPU shared-memory systems, which currently face other types of bottlenecks so severe that to the best of my knowledge, no such system exists. It might therefore make no sense to eliminate this instance of non-commutativity. However, this is by no means a fatal flaw. It instead indicates that it is necessary to consider commutativity to be but one of many inputs to the task of creating a good API design, rather than blindly doing whatever the Commuter tool says to do. And perhaps this will be addressed in future work.

I nevertheless expect this important work to inform future API design, allowing future implementations to avoid a great many scalability bottlenecks. Or, at least, to avoid those bottlenecks that are not mandated by standards.

Acknowledgments

I owe thanks to Robert Morris and Austin Clements for their careful review and thoughtful comments. I am grateful to Jim Wasko for his support of this effort.

Answers to Quick Quizzes

Quick Quiz 1: Why bother with commutativity? Why not just partition the problem and get on with life?

Answer: It turns out that partitioning is in fact one way to promote commutativity. After all, when you partition the problem, operations acting on different partitions can happen in any order without changing the result. So partitioning is one way to achieve commutativity, but there are also other valuable techniques.

Back to Quick Quiz 1.

Quick Quiz 2: That is quite an improvement, when will these changes be applied to the Linux kernel?

Answer: Hopefully sooner rather than later.

That said, the authors did use some implementation techniques that might not be unanimously welcomed by Linux users. For one example, they completely dispensed with mass storage in favor of RAM-based filesystems (which might well be addressed in future work). In addition, some of the bottlenecks identified in Linux will be more important than others.

Back to Quick Quiz 2.

Quick Quiz 3: Isn't posix_spawn() perfectly commutable with everything?

Answer: Close, but not quite. The list of things that can fail to commute with posix_spawn() includes: exit(), fatal signals, writes to the memory containing the pathname of the executable, open(), and close(), among many others. Nevertheless, posix_spawn() is considerably more commutable than is fork().

Too bad about those software-engineering code-compatibility concerns.

Back to Quick Quiz 3.

Quick Quiz 4: But if the point of avoiding the read is to avoid acquiring a lock, aren't we really avoiding writes, not reads?

Answer: You can certainly look at it that way. Without the locks, namei() would make use of the permit weak ordering exception called out above, at least assuming that it avoided crashing in the process. However, the fact remains that names like lookup_fast() do not connote “write” to most people.

Interestingly enough, Linux's lookup_fast() can avoid most writing if it is able to stay on the fastpath. However, pathname coherence is guaranteed by a read-seqlock operation, which could, in theory, inflict a scalability bottleneck on lookup_fast() in the face of frequent path rearrangements. Such rearrangements could (again, in theory) cause the read-seqlock to always fail, limiting lookup_fast() even without considering any lookup_fast() writes.

So reads can result in scalability problems. Admittedly indirectly, and caused by someone else's writes, but the point still stands: reads really can harm your scalability and performance.

Back to Quick Quiz 4.

Quick Quiz 5: But the first two exceptions depend on hardware features that are not universally available, so why would anyone want their software to depend on such features?

Answer: Theory, meet portable practice.

That said, it all depends on the situation. The more you need the additional scalability, the more willing you will be to depend on specific hardware. And perhaps now that multicore hardware has well and truly arrived, additional hardware scalability optimizations will become available. Stranger things have happened.

Back to Quick Quiz 5.

Comments (29 posted)