Leading items

Welcome to the LWN.net Weekly Edition for August 17, 2017

This edition contains the following feature content:

• Debian debates software for proprietary services: should the distribution ship a library whose job is mainly to interface with a proprietary network service?
• A canary for timer-expiration functions: hardening the kernel against timer-overwrite attacks.
• Scaling the kernel's MAINTAINERS file: as the kernel community grows, even the MAINTAINERS file needs maintenance — and perhaps a process change as well.
• Another attempt at speculative page-fault handling: a memory-management scalability technique that has been eight years in the making.
• Reducing Python's startup time: it takes too long to start a Python program; developers are looking at one way of making things better.

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)

Debian debates software for proprietary services

Distributions like Debian have a clear policy on the software they ship; as a general rule, only free software can be considered for inclusion. How that policy should be applied to software that interacts with proprietary systems is not entirely clear, though. A recent discussion on a package that interfaces with a proprietary network service seems unlikely to lead to any changes in policy, but it does highlight a fault line within the Debian community.

Back in February, Jonas Smedegaard filed a bug against the "certspotter" package, complaining that the package's description advertises the proprietary SSLMate service. On August 4, the maintainer of that package, Faidon Liambotis, got around to answering the bug, saying that the description is helpful for users searching for the package and will not be removed. At that point, Smedegaard took the discussion to the debian-project mailing list in an attempt to rally the Debian developer community against the offending package description.

The ensuing discussion, though, quickly got away from the question of the description and into the area of whether Debian should host software that interfaces with proprietary services in its "main" repository, or whether such software should be relegated to "contrib" instead. The answer to this question carries some consequences. If a package moves to contrib, any package that depends on it (or even recommends it) must also move to contrib. The contrib repository is not enabled by default in a new Debian installation, and packages in contrib do not normally get security updates. So a move to contrib signals a clear second-class-citizen status that would almost certainly result in a significant reduction in the number of users who even know that the package exists, much less use it.

We are talking about Debian here, so one can expect to find a written policy addressing the issue. In this case, though, the policy manual is mostly silent, with one exception. Section 2.2, which describes the repository areas, says: "None of the packages in the main archive area require software outside of that area to function". Some Debian developers interpret this sentence as saying that the packages in main cannot link to proprietary software; others say that use of a proprietary web service is enough to disqualify a package from main.

If the latter view holds, there are quite a few ongoing policy violations in need of attention. The classic example, raised by a number of participants in the discussion, is the venerable ICQ messaging service. This service is proprietary, but a number of ICQ clients exist in the Debian main repository. In this case, the fact that the client itself is free software has generally been deemed good enough for inclusion in main.

If that is no longer the case, then a number of other packages need review as well. Vincent Bernat raised s3cmd, a tool for managing Amazon S3 services. But perhaps s3cmd is different because there are now a couple of free tools that emulate the S3 API. Another one, also pointed out by Bernat, is rclone, which specializes in synchronizing files between local systems and cloud-storage services, which are generally commercial. This tool is not just useful for ongoing use of those services; it can also be used as a means for escape from a cloud service — which is generally considered beneficial.

On August 9, Smedegaard carried the discussion to the debian-devel list, in the apparent hope of finding more support there. The result was perhaps less than he had hoped for. There were some developers, such as Bas Wijnen, who argued for expelling all such software from main:

Others disagreed, making the point that, if one looks closely enough, there is little software indeed that doesn't require proprietary software — in the CPU's microcode if not elsewhere — to function. Russ Allbery argued strongly against pushing out such software, saying: "I believe this would be hugely counter-productive for free software. It would hurt us way more than it would hurt proprietary services". He added that "writing a library specifically to interact with a non-free service is *good software engineering*" and that such libraries should be allowed in Debian. After that, the discussion slowed considerably.

Once again, this is Debian, so the possibility of this disagreement snowballing into a huge general-resolution fight is real. But a reading of the discussion does not appear to reveal an appetite for that kind of battle. A more likely outcome is that the issue will slowly fade from view with no significant changes to existing practice. But, this being Debian, one can probably predict with reasonable certainty that the topic will return to the lists in the not-too-distant future.

Comments (29 posted)

A canary for timer-expiration functions

A bug that allows an attacker to overwrite a function pointer in the kernel opens up a relatively easy way to compromise the kernel—doubly so, if an attacker simply needs to wait for the kernel use the compromised pointer. There are various techniques that can be used to protect kernel function pointers that are set at either compile or initialization time, but there are some pointers that are routinely set as the kernel runs; timer completion functions are a good example. An RFC patch posted to the kernel-hardening mailing list would add a way to detect that those function pointers have been changed in an unexpected way and to stop the kernel from executing that code.

The patch from Kees Cook is targeting a class of vulnerabilities that arrange to overwrite the function field in struct timer_list. That field is the function that will be called when the timer expires and it conveniently (from an attacker's perspective) passes the next field in that structure (data) to the function. So an attacker who finds a way to overwrite function can likely overwrite data as well, leading to a fairly straightforward way to call some code of interest and to pass it an argument. As Cook put it: "This provides attackers with a ROP-like primitive for performing limited kernel function calls without needing all the prerequisites to stage a ROP attack."

Exploits

In the patch, he pointed to two recent exploits that used this technique. The first was described by its discoverer, Philip Pettersson, in December 2016. It uses an AF_PACKET socket (for raw socket handling as used by tools like tcpdump) and manipulates the version of the packet-socket API requested using setsockopt(). By changing from TPACKET_V3 to TPACKET_V1 at just the right time (to take advantage of a race condition), his demonstration exploit will cause the memory containing a timer_list to be freed without deleting the timer.

So the timer object will be used by the kernel after it has been freed. By arranging for that memory to be reallocated somewhere that the attacker can write to (Pettersson mentions using the add_key() system call to do so), function and data can be overwritten. In the example, it actually does that twice, first to change the vsyscall table from read-only to read-write, then to register a world-writable sysctl (/proc/sys/hack) that sets the path of the modprobe executable. It arranges that the exploit program gets run as modprobe (as root), which leads to the execution of a root shell.

The second recent exploit was the subject of a lengthy Project Zero blog post in May by Andrey Konovalov, who discovered the flaw using the syzkaller fuzzer. It uses a heap buffer overflow in the AF_PACKET code. By arranging the heap appropriately and sending a packet with the contents of interest (the exploit code, effectively), it will place the code into memory. But that memory is user-space memory, and the Intel supervisor mode access protection (SMAP) and supervisor mode execution protection (SMEP) features will prevent the kernel from directly accessing or executing code there. So Konovalov used the same technique as Pettersson to simply disable those protections by calling native_write_cr4() to change the CR4 register bits as the expiration function of a socket timer.

Once that is done, it sets up a new compromised socket and ring buffer combination that turns a transmit function pointer into a pointer to a commit_creds(prepare_kernel_cred(0)) call in user space. Then simply transmitting a packet using the socket invokes the code, which gives the current process root privileges.

It is interesting to note that both of these vulnerabilities can be exploited by non-privileged users on distributions (e.g. Fedora, Ubuntu) where user namespaces are enabled and unrestricted. Both require the CAP_NET_RAW capability to create packet sockets, which can be acquired by unprivileged users by creating a new user namespace. While the problem is not directly attributable to the user namespace code itself, it does further highlight the dangers of expanding user privileges that namespaces provide. Both Pettersson and Konovalov warn against allowing unprivileged users to create user namespaces.

Both also avoid kernel address-space layout randomization (KASLR), SMAP, and SMEP protections. Pettersson's exploit uses hardcoded offsets for the calls of interest to avoid KASLR, while Konovalov reads dmesg to pluck out the kernel's text address. SMAP/SMEP are either bypassed by using kernel memory directly (Pettersson) or by explicitly disabling the features (Konovalov).

A possible fix

Cook's patch would add a canary field to struct timer_list just prior to the function field. When a timer is initialized, the canary would be set to a value calculated by XORing the addresses of the timer and the function, along with a random number that only the kernel would know. The idea is that the canary value would also be overwritten if the function pointer is. So, before calling the function when the timer expires, the canary would be recalculated and compared with the stored value; if they differ, the function pointer has been changed and will not be called. A warning will be logged as well.

Unfortunately, Cook soon realized that his patch was incomplete. He had addressed timers that were set up using the setup_timer_*() macros and the add_timer() function, but missed many static timer initializations that use DEFINE_TIMER(). He promised a revised version of the patch to handle that case.

But it turns out that will require some extensive refactoring of the timer code, he said in response to an email query. That is a bigger job than he expected, but does provide a nice cleanup, he said. He may also have to weaken the canary for the static timers, he said in the patch followup. As with many cross-subsystem patch sets that change code across the tree, getting something like that into the mainline may be difficult. Cook outlined some of the problems he and others have encountered trying to do so in a ksummit-discuss thread back in June.

As the two exploits showed, though, the problem is real. Some kind of solution that would simply eliminate that class of vulnerabilities would be welcome. Whether Cook's canary can be that solution remains to be seen, however.

Comments (12 posted)

Scaling the kernel's MAINTAINERS file

The kernel's development community is large, to the point that it is often far from obvious who a given patch should be sent to. As the community has grown, it has developed mechanisms for tracking that information centered on a text file called MAINTAINERS. But now it would appear that this scalability mechanism has scalability problems of its own.

The MAINTAINERS file sits at the top of the kernel's source tree; it is a plain-text file with a number of fields describing how various kernel subsystems are managed. For example, the following entry was consulted for a recent article on device-tree issues:

    OPEN FIRMWARE AND FLATTENED DEVICE TREE
    M:	Rob Herring <robh+dt@———>
    M:	Frank Rowand <frowand.list@———>
    L:	devicetree@vger.kernel.org
    W:	http://www.devicetree.org/
    T:	git git://git.kernel.org/pub/scm/linux/kernel/git/robh/linux.git
    S:	Maintained
    F:	drivers/of/
    F:	include/linux/of*.h
    F:	scripts/dtc/
    F:	Documentation/ABI/testing/sysfs-firmware-ofw

This entry says that the flattened device-tree subsystem has two maintainers (the "M:" fields), Rob Herring and Frank Rowand. The relevant mailing list (L:) and web site (W:) are given, as is the subsystem's Git tree (T:). The F: lines describe the files and directories that are considered to be a part of this subsystem. The file can be read in a text editor, but it is often consulted by way of the get_maintainer.pl script, which reads a patch and outputs a list of addresses to which the patch should be sent.

This file is over 14,000 lines long in current kernels and contains entries for over 1,700 subsystems in the kernel. Those subsystems are ostensibly listed in alphabetical order but, as Randy Dunlap noted in a patch posted in July, many of the entries are not in the right place. His patch sought to improve the situation, but that is where the real trouble started.

In a community as large as the kernel, changes to subsystems happen on a frequent basis. If the relevant maintainers are paying attention, those changes result in patches to the MAINTAINERS file — on the order of 100 patches in each development cycle. Needless to say, a certain number of those patches will conflict with each other, and Linus Torvalds gets to clean up the mess. When Dunlap's patch inevitably resulted in a merge conflict, Torvalds proclaimed his frustration with the MAINTAINERS file. Perhaps, he asked, there would be some way to split it up?

His original suggestion was to spread the maintainer information through the kernel source tree, like the kernel configuration file was split up starting in 1.3.36. He later suggested that the maintainer information could, in fact, live in the Kconfig files with the configuration options, though that idea did not get far. Regardless of the exact scheme used, he explained, splitting up the maintainer information would make resolving conflicts into a less frustrating task.

The advantages of a less frustrated Linus Torvalds are evident to most kernel developers, so interest in improving the MAINTAINERS file is relatively high. Joe Perches suggested splitting the file into a top-level MAINTAINERS directory; that would keep the information easy to find and easy for scripts to work with. And that would indeed appear to be way things are headed.

That leaves the question of how the file should be split. Yet another suggestion from Torvalds was to split the file by mailing list, so that all entries pointing to the same list would end up in the same file. But Perches came back with a script that splits the file by directory hierarchy instead. The result is 54 files in the MAINTAINERS directory with names like arch_arm64, drivers_gpu_drm, or filesystems. Any subsystem without enough entries to justify its own file ends up in MAINTAINERS/MAINTAINERS.

Torvalds tried it out but chose not to go with the result. He had a few quibbles with how the split is done, but concluded that "*some* of it looks really nice". But perhaps the concern that really stopped things was a familiar one: making this change will create merge conflicts with any subsystem tree containing changes to the MAINTAINERS file. The most likely solution to that problem is to make the change immediately after the 4.14-rc1 release. Torvalds has not committed to doing so, but it does seem likely that the MAINTAINERS split is coming in the relatively near future.

Comments (6 posted)

Another attempt at speculative page-fault handling

While the best way to avoid performance problems associated with page faults is usually to avoid faulting altogether, that is not always an option. Thus, it is important that the kernel handle page faults with a minimum of overhead. One particular pain point in current kernels comes about in multi-threaded workloads that are all incurring faults in the same address space. Speculative page-fault handling is an old idea for improving the scalability of such workloads that may finally be approaching a point where it can be considered for inclusion.

Memory-management performance with multi-threaded workloads is often bounded by the ability to acquire the mmap_sem reader/writer semaphore, which serializes access to the data structures describing a process's address space. The handling of page faults, in particular, requires mmap_sem, so a process with a large number of threads generating faults will see contention. Speculative page faults are an attempt to alleviate this contention by doing lockless reads of a process's virtual memory areas (VMA) without holding mmap_sem.

The speculative page-fault patches first appeared in 2009 and have been discussed and improved upon intermittently by various kernel developers through the years, but this work has not found its way into the kernel. Laurent Dufour has recently revived this effort by resubmitting the patches with fixes and improvements of his own, and an active discussion took place on the linux-kernel mailing list on its inclusion. Notably, Dufour reports a 20% speed improvement loading a 2TB database with the speculative page fault code.

As noted above, the mmap_sem semaphore can be a point of significant contention for multi-threaded workloads. In particular, page-fault handling requires access to a process's VMA structures that describe its memory layout, and that access requires mmap_sem. Even when only read locking is required (as is the case for page faults), frequent access to mmap_sem leads to cache-line bouncing and poor performance. The idea behind speculative page faults is to increase memory-management performance by avoiding the use of the mmap_sem in page-fault handling. Doing so requires a way to perform a lockless walk of the VMAs; that, in turn, means facing a number of problems that mmap_sem is explicitly there to prevent.

The first of these problems, naturally, is that the VMA describing the area where a fault occurs may, if mmap_sem is not held, change during the handling of the fault. The strategy taken to address this problem is to do as much work as possible that doesn't depend on the state of the VMA, then checking to see if anything has changed before changing the process's address space directly. So, for example, a free page can be allocated and its data read in from disk independently of the address space, but actually putting that page into the address space requires a consistent view of the VMA.

The kernel has a longstanding mechanism for this kind of access: the seqlock. So the patch set adds a seqlock to the VMA structure, along with the code to increment its sequence count everywhere that the VMA is changed. The speculative fault-handling code can then record the sequence number before doing any work and verify that the number has not changed at the end. If the sequence number does change, the VMA has been changed and the speculative work was done in vain; in this case the attempt fails and the fault is retried in the old-fashioned way.

The second problem is a bit trickier; without mmap_sem, a VMA may disappear entirely while a fault is being handled. This situation is avoided by using read-copy-update (RCU) to keep VMA structures around while a fault is being handled. SRCU (the sleepable variant of RCU) is used to serialize VMA updates and accommodate lockless reads of the VMA. SRCU is required because a number of fault-handling operations can sleep.

When handling a page fault speculatively, the kernel will do a lockless page-table walk and grab the finer-grained page-table lock. Then it does a srcu_read_lock() to do a VMA lookup, and checks the write-sequence count of the VMA. It will need to use the VMA to find the page that the address faulted on, but to do this it needs to drop the page table lock to honor locking order rules. Once the page is found, the VMA is validated again by repeating the page table walk, obtaining the page-table lock, and validating that the VMA sequence number did not change. If it didn't, the page is installed in the page table, and the page-table lock is released.

Another pitfall with speculative page-fault handling has to do with translation lookaside buffer (TLB) invalidation. Various actions, such as unmapping a memory area, can call for a TLB invalidation; that is handled by sending inter-processor interrupts (IPIs) to tell each CPU to invalidate its own TLB. The unmap path can lock specific page-table entries and perform the invalidation while that lock is held. The speculative fault-handling path, meanwhile, will attempt to take the page-table lock it needs with interrupts disabled. Should that attempt happen on a page-table entry that is held by the unmap path, the processor will spin in a loop with interrupts disabled, meaning it will never receive the TLB-invalidation IPI. The result is a deadlock, a situation that is even worse for performance than mmap_sem contention. Once this problem is understood the solution is straightforward: use a "trylock" operation to acquire the lock in the speculative path, and fall back to traditional fault handling if it fails.

The first speculative page fault patches were posted in 2009 by Hiroyuki Kamezawa. The ensuing discussion led Peter Zijlstra to create his own implementation based on the idea of using RCU to enable lockless reading of the VMA structures. Zijlstra's implementation had some issues of its own; no code was merged, and the discussion stalled and fizzled out. The idea was revived again by Zijlstra in 2014, because many of the issues blocking the progress of previous attempts had been solved. However, the discussion fizzled out again, and there was no push for merging the code. In June, Dufour forward-ported Zijlstra's patches and added some of his own. One of the problems Dufour addresses with his patches is the TLB invalidation issue.

Despite the two previous abandoned speculative page fault implementations, the idea is useful enough for another attempt to be made at trying to get this code merged into the kernel. Dufour's database-loading speed improvements led Michal Hocko to ask if there were any other tests or benchmarks that were run, such as kernbench or other highly threaded workloads. In response, the August 8 posting (linked above) includes a number of results from different benchmarks, showing modest to significant improvements depending on the test.

At this point, it would appear that the significant issues with this patch set have been addressed. Given that speculative page-fault handling shows significant improvements for some workloads, one might not be faulted for speculating that there is a reasonable chance that this work will be merged in the relatively near future — a mere eight years after the initial idea was floated.

[Thanks to Peter Zijlstra for answering my questions about this work.]

Comments (1 posted)

Reducing Python's startup time

The startup time for the Python interpreter has been discussed by the core developers and others numerous times over the years; optimization efforts are made periodically as well. Startup time can dominate the execution time of command-line programs written in Python, especially if they import a lot of other modules. Python startup time is worse than some other scripting languages and more recent versions of the language are taking more than twice as long to start up when compared to earlier versions (e.g. 3.7 versus 2.7). The most recent iteration of the startup time discussion has played out in the python-dev and python-ideas mailing lists since mid-July. This time, the focus has been on the collections.namedtuple() data structure that is used in multiple places throughout the standard library and in other Python modules, but the discussion has been more wide-ranging than simply that.

A "named tuple" is a way to assign field names to elements in a Python tuple object. The canonical example is to create a Point class using the namedtuple() factory:

    Point = namedtuple('Point', ['x', 'y'])
    p = Point(1,2)

The elements of the named tuple can then be accessed using the field names (e.g. p.x) in addition to the usual p[0] mechanism. A bug filed in November 2016 identified namedtuple() as a culprit in increasing the startup time for importing the functools standard library module. The suggested solution was to replace the namedtuple() call with its equivalent Python code that was copied from the _source attribute of a class created with namedtuple(). The _source attribute contains the pure Python implementation of the named tuple class, which eliminates the need to create and execute some of that code at import time (which is what namedtuple() does).

There are a few problems with that approach, including the fact that any updates or fixes to what namedtuple() produces would not be reflected in functools. Beyond that, though, named tuple developer Raymond Hettinger was not convinced there was a real problem:

Nick Coghlan agreed with Hettinger's assessment:

Hettinger closed the bug, though it was reopened in December to consider a different approach using Argument Clinic and subsequently closed again for more or less the same reasons. That's where it stood until mid-July when Jelle Zijlstra added a comment that pointed to a patch to speed up named tuple creation by avoiding some of the exec() calls. It was mostly compatible with the existing implementation, though it did not support the _source attribute. That led to a classic "bug war", of sorts, where people kept reopening the bug, only to see it be immediately closed again. It is clear that some felt that the arguments for closing the bug were not particularly compelling.

After several suggestions that the proper way to override the bug-closing decisions made by Hettinger and Coghlan was to take the issue to python-dev, Antoine Pitrou did just that. According to Pitrou, the two main complaints about the proposed fix were that it eliminated the _source attribute and that "optimizing startup cost is supposedly not worth the effort". Pitrou argued that _source is effectively unused by any Python code that he could find and that startup optimizations are quite useful:

In addition, the _source attribute is something of an odd duck in that it would seem to be part of the private interface because it is prefixed with an underscore, but also that it is meant to be used as a learning tool, which is not typical for Python objects. The underscore was used so that source could be used as a tuple field name but, as Hettinger noted, it probably should have been named differently (e.g. source_). But he is adamant that there are benefits to having that attribute, mostly from a learning and understanding standpoint.

Ever the pragmatist, Guido van Rossum offered something of a compromise. He agreed with Pitrou about the need to optimize named tuple class creation, but hoped that it would still be possible to support Hettinger's use case:

As might be guessed, a pronouncement like that from Van Rossum, Python's benevolent dictator for life (BDFL), led Hettinger to reconsider: "Okay, then Nick and I are overruled. I'll move Jelle's patch forward. We'll also need to lazily generate _source but I don't think that will be hard." He did add "one minor grumble", however, regarding the complexity of the CPython code:

That tradeoff between complexity and performance is one that has played out in many different development communities over the years—the kernel community faces it regularly. Part of the problem is that the negative effects of a performance optimization may not be seen for a long time. As Coghlan put it:

Van Rossum's pronouncement set off a predictable bikeshedding frenzy around named tuple enhancements that eventually moved to python-ideas and may be worthy of a further look at some point. But there was also some pushback regarding Hettinger's repeated contention that shaving a few milliseconds here and there from the Python startup time was not an important goal. As Barry Warsaw said:

Gregory P. Smith pointed to the commonly mentioned command-line utilities as one place where startup time matters, but also described another problematic area:

The discussion (and a somewhat dismissive tweet from Hettinger [Note: Hettinger strongly disclaims the "dismissive" characterization.]) led Victor Stinner to start a new thread on python-dev to directly discuss the interpreter startup time, separate from the named tuple issue. He collected some data that showed that the startup time for the in-development Python 3.7 is 2.3 times longer than Python 2.7. He also compared the startup of the Python-based Mercurial source code management system to that of Git (Mercurial is 45 times slower) as well as comparing the startup times of several other scripting languages (Python falls into the middle of the pack there). In the thread, Pitrou pointed out the importance of "anecdotal data", which Hettinger's tweet had dismissed:

Python has come a long way from its roots as a teaching language. There is clearly going to be some tension between the needs of languages geared toward teaching and those of languages used for production-quality applications of various kinds. That means there is a balance to be struck, which is something the core developers (and, in particular, Van Rossum) have been good at over the years. One suspects that startup time—and the named tuple implementation—can be optimized without sacrificing that.

Comments (13 posted)