Kernel development

Kernel release status

The current development kernel is 3.13-rc4, released by a slightly grumpy Linus on December 15. "So I delayed this a couple of days to get back to my normal Sunday release schedule, but I'm not entirely happy with the result. Things aren't calming down the way they should be, and -rc4 is bigger than previous rc's. And I don't think I can just blame the two extra days."

Stable updates: 3.12.5, 3.10.24, and 3.4.74 were released on December 11. The 3.12.6, 3.10.25, and 3.4.75 updates are in the review process as of this writing; they can be expected on or after December 20.

Comments (none posted)

Quotes of the week

— Hugh Dickins

— Al Viro ponders a better mount()

Comments (2 posted)

Simple wait queues

A "wait queue" in the Linux kernel is a data structure to manage threads that are waiting for some condition to become true; they are the normal means by which threads block (or "sleep") in kernel space. Over the years, the wait queue mechanism has evolved into a fairly elaborate and complicated kernel subsystem. Now, however, there is a move afoot to simplify that code, using a wait queue variant developed for the realtime tree; the result could be a fair amount of code churn in the kernel.

A look at <linux/wait.h> from the 2.0 kernel reveals a simple data structure: a basic linked list of waiting threads. A wake_up() call on a wait queue would walk the list, putting each thread into the runnable state; there was not a whole more to it than that. Then, in 1999, the infamous Mindcraft study pointed out some performance deficiencies in Linux; one of those was the "thundering herd" problem where multiple processes would be awakened and contend for a resource that only one of them could obtain. As a result, the "exclusive wait" functionality — where only the first of possibly many waiting threads would wake — was added. Then a callback mechanism was added in the 2.5 series so that the new asynchronous I/O facility could step in when things would otherwise block. And so on.

The end result is a data structure that is far larger and more complex than it was in the 2.0 days. It is the callback feature that was most problematic for the realtime tree, though; since those callbacks can sleep, they prevent the use of "raw" spinlocks to protect the wait queues themselves. To work around this problem, Thomas Gleixner created a new "simple wait queue" mechanism that would dispense with most of the added functionality and, thus, be suitable for use in the realtime kernel.

The 2013 Realtime Linux Workshop identified this code as a candidate for a relatively easy move into the mainline. In response, Paul Gortmaker has extracted the simple wait queue facility and posted the resulting patch series for review.

The code looks a lot like a return to the 2.0 kernel; much of the functionality that wait queues have gained in the meantime has been stripped away, leaving a familiar-looking linked list of waiting threads. There is no exclusive wakeup feature, no callback feature, and not much of anything else. What there is, though, is a wait queue mechanism that is sufficient for the needs of most wait queue users (of which there are many) in the kernel.

The API is similar to that of existing wait queues. Wait queue entries and wait queue heads are defined with:

    #include <linux/swait.h>

    DEFINE_SWAITER(name);
    DEFINE_SWAIT_HEAD(name);

The low-level API, which requires a direct call to schedule() to put the calling thread to sleep, looks like this:

    void swait_prepare(struct swait_queue_head *head, struct swaiter *w, int state);
    void swait_finish(struct swait_queue_head *head, struct swaiter *w);

The swait_prepare() call is used to add the process to the given wait queue head and put it into the appropriate sleeping state. After performing any necessary checks and calling schedule(), the newly woken thread will call swait_finish() to remove itself from the queue and clean up.

The current wait queue implementation has an extensive set of macros to simplify the task of waiting for a condition; there is a similar, but much smaller set for simple wait queues:

    void swait_event(queue, condition);
    int swait_event_interruptible(queue, condition);
    void swait_event_timeout(queue, condition, timeout);
    int swait_event_interruptible_timeout(queue, condition, timeout);

Most of the other versions of wait_event(), including the "killable" variants, are not provided. It is amusing to look at a list of wait_event() macros that lack equivalents in the new API, just to see how this interface has grown over the years:

    wait_event_cmd(wq, condition, cmd1, cmd2);
    wait_event_hrtimeout(wq, condition, timeout);
    wait_event_killable(wq, condition);
    wait_event_lock_irq_cmd(wq, condition, lock, cmd);
    wait_event_lock_irq(wq, condition, lock);
    wait_event_interruptible_hrtimeout(wq, condition, timeout);
    wait_event_interruptible_exclusive(wq, condition);
    wait_event_interruptible_locked(wq, condition);
    wait_event_interruptible_locked_irq(wq, condition);
    wait_event_interruptible_exclusive_locked(wq, condition);
    wait_event_interruptible_exclusive_locked_irq(wq, condition);
    wait_event_interruptible_lock_irq_cmd(wq, condition, lock, cmd);
    wait_event_interruptible_lock_irq(wq, condition, lock);
    wait_event_interruptible_lock_irq_timeout(wq, condition, lock, timeout);

There is little impediment to adding "simple" versions of most of the above macros should the need arise; it will be interesting to see how many of them show up in the coming years. Needless to say, there is also nothing like the archaic sleep_on() interface; it is safe to say nobody will try to add a version of that.

Paul's posting notes that adding the simple wait queues makes the kernel smaller, even when they are only used in a couple of places. Given the size reduction and the relative simplicity of the interface, it is unsurprising that there has been no opposition to adding this code so far. The only real question is how that addition is to be done. Christoph Hellwig suggested that the simple wait queues could simply replace the current implementation, with the few places needing the fancier functionality being changed to use the older code under a new name. Paul, though, worried that such a wholesale change would create a flag day with problems being associated with the wait queue change in mysterious ways.

Nobody wants that kind of situation, so it seems more likely that simple wait queues will retain their "swait" naming scheme. The kernel might see a wholesale naming change for the existing wait queues to make it clear that there is now a choice to be made, though. Thus, we may see a large patch changing wait_event() to cwait_event(), and so on, without changing functionality; after that, individual call sites could be changed to simple wait queues at leisure. The result would be a fair amount of code churn, but that churn should leave a smaller and simpler kernel in its wake.

Comments (2 posted)

A proposal for "silent" port knocking

Port knocking is a longstanding technique to evade port scans that is typically implemented in user space. A recent patch proposed for the kernel would change that by adding support for port knocking into the TCP/IP stack itself. Beyond just allowing administrators to hide open ports, the patch would also provide some ability to thwart man-in-the-middle attackers either from making their own connections to those hidden ports or from hijacking those established by friendly clients. But the patch is facing some pushback from the network developers who think that user space is a better place to handle features like port knocking.

The details of the "knock" vary, but the basic idea for port knocking is that a protected port on a server will not respond to the normal connection-establishment protocol; instead, some special steps will be required to make a connection to the port. Those steps might include making a connection attempt to a different port, or to a series of ports, that show the server that the client knows the secret knock to gain entry to the clubhouse. Since port scanning programs generally don't know the secret knock and it is expensive to try lots of possibilities, the services behind the knock are hidden from view.

There are a few different reasons to hide a service. One is that the server program may have vulnerabilities, either because it has not been kept up-to-date or because there are unknown flaws in the code. If only trusted people know about the knock, it reduces the threat of someone exploiting the hole. In addition, hiding services like SSH will avoid brute-force username/password guessing attacks.

But there is another reason to hide the existence of a service: it may be illegal in certain jurisdictions or running it may draw unwanted attention to the host and its owner. Folks running Tor bridges or other privacy-oriented services may see them blacklisted by government-controlled internet service providers—or prompt a visit from some secret service.

Existing port knocking solutions generally either monitor firewall logs or capture packets from user space, then modify the firewall to open the port when the proper knock is detected. The Knock project—a part of the GNUnet project—looks to turn that on its head. With a few-hundred-line patch, authors Maurice Leclair, Julian Kirsch, and Christian Grothoff would move the port-knocking logic into the Linux networking stack. That would allow clients and servers to communicate, while hiding behind a port knock, simply by using the new TCP_STEALTH option to setsockopt(). If the code were widely available in most Linux kernels, users could rely on the feature being available, without having to install and configure some other port knocking solution.

Knock is different than other solutions in a couple of other ways. To start with, it is meant to be undetectable to a man in the middle. It just looks like a normal connection establishment to a particular port—there is no extra sequences of connections to other ports or other special knocks. It uses a technique called "silent knocking" that requires sharing a secret between the client and server using some unspecified, out-of-band mechanism. That secret is used to calculate the sequence number of the initial SYN packet that is sent to initiate the three-way handshake that starts TCP connections. Any SYN with an improper sequence number gets an RST reply; exactly what it would get for a closed port.

In addition, using the TCP_STEALTH_INTEGRITY option allows the the first bytes of the payload data to be protected by a hash-based message authentication code (HMAC), which effectively stops active man-in-the-middle attackers from hijacking the connection once it has been established. Essentially, the top 16 bits of the sequence number in the SYN packet correspond to the HMAC, while the low 16 bits are the authentication code that comes from the MD5 of the shared secret.

The 32-bit authentication code for stealth-only mode is calculated with one round of MD5 using the shared secret along with the destination IP address and port. In stealth+integrity mode, the client and server must agree on the number of payload bytes to be covered by the HMAC, which also uses MD5. A short paper [PDF] about Knock noted that using MD5 may be something of a surprise, but that it is already used by the kernel for initial TCP sequence number calculation as well as for SYN cookies. But in the linux-kernel mailing list thread, Jacob Appelbaum (who assisted in the design of Knock) was not particularly happy with the choice of MD5:

The stealth-only mode is vulnerable to replay attacks as a man in the middle can observe the proper sequence number to unlock the port and replicate it in their own packets (without knowing the secret). Stealth-only is also vulnerable to brute force attacks (trying all possible sequence numbers), but that could be expensive in terms of time and it is not particularly stealthy, so the attack might well be noticed. The stealth+integrity mode is more resistant, as the HMAC-protected bytes could be used to transfer a public key that is used to encrypt the rest of the data.

There are some other downsides to the idea that were briefly explored in the thread. For one thing, network address translation (NAT) implementations that change the sequence number in the SYN packet will not work at all with this technique. As David Miller pointed out, sequence number alteration is done in netfilter for tracking the SIP and FTP protocols as well as for virtual server load balancing.

Others were more explicitly suggesting that handling this kind of port knocking (or, seemingly, any kind of port knocking) would be best done outside of the TCP core—in user space. Both Stephen Hemminger and Andi Kleen suggested that user space was a better home for the code. But Grothoff, who signed off on the patch and posted it, was surprised by that attitude: "I mean, if this was a patch for GNU Hurd, I'd at least understand the strong urge to do everything in userspace". Kleen, though, noted that keeping port knocking in user space meant that "the risk of adding exploitable holes to the kernel is [significantly] lower".

Eric Dumazet was also critical of the idea. He suggested allowing user space to implement parts of the TCP protocol, which would also help other proposals (like TCP Minion):

Dumazet is also concerned that reusing the initial sequence number (ISN) will make it difficult for servers to distinguish duplicated packets. He didn't mention it, but duplicate ISNs (i.e. the sequence number sent with the SYN) might also make the port knocking more obvious to a man in the middle. Overall, though, Dumazet felt that the paper was too short to explore the idea: "You really need more than 3 pages to fully investigate all the pros/cons of this idea."

He also hinted at a possible direction for getting Knock upstream: looking at TCP fast open, which is somewhat similar and was merged into the mainline. If Knock could be more like fast open, or use it directly, it might have more of a chance to be added to the networking core. The concerns raised by Dumazet and others are reflections of the complexity of the networking stack, that there are a lot of moving parts all of which need to work well together. That's part of the reasoning behind relegating features like port knocking to user space.

On the other hand, Grothoff is not convinced that the small patch he posted "really warrants moving TCP into user land". But the reception from core network developers like Miller, Hemminger, and Dumazet would seem to make it fairly unlikely the patch will make it into the kernel. Working on ways to either move some pieces of TCP handling into user space or to extend netfilter to allow for both silent knocking and payload protection would likely be the best way forward. It is an interesting idea, though not without flaws, but getting it into the kernel itself is going to be an uphill battle.

Comments (10 posted)

Btrfs: Getting started

This is the second article in a series on the Btrfs filesystem; those who have not seen the first segment may wish to take a quick look. This installment will cover the basics of finding the requisite software and getting started with a Btrfs filesystem, while leaving the advanced features for the future. Using Btrfs as a simple Unix-style filesystem is a straightforward matter once the proper tools are in place.

The Btrfs filesystem code itself has been in the mainline kernel since the 2.6.29 release in early 2009. Since then, development of the in-kernel code has mostly been done upstream, so the mainline kernel contains all of the code that is deemed ready for use. In general, users wanting to use Btrfs for real work are probably best advised to stay close to the current mainline releases. Fixes are still being made at a high rate; it is probably preferable to run the fixed code than to get a demonstration of why the fixes were necessary. One can get even newer code by pulling from the Btrfs development repository, but that may be a bit too new for anybody who is not actively developing Btrfs.

The current user-space tools, which handle the creation and management of Btrfs filesystems, can be pulled from the repository at:

    git://git.kernel.org/pub/scm/linux/kernel/git/mason/btrfs-progs.git

Until recently, the last "release" of btrfs-progs was 0.19, made in June 2009. Toward the end of November, though, the version number was set to "v3.12", inaugurating a new era in which version numbering will be tied to kernel releases. Btrfs developer Chris Mason noted at the time that he expected to make btrfs-progs releases with approximately the same frequency as the kernel going forward. Since much of the needed work is on the user-space side, this should be a welcome development for Btrfs users.

Once again, those wanting to make serious use of Btrfs are likely to want to run something close to the current versions of the supporting user-space utilities. A lot of work (and bug fixes) is going into this code, but one needs to stay current to take advantage of that work. Some distributions follow progress in the btrfs-progs repository more closely than others; Fedora 19 already has v3.12, for example, so there is no real need for Fedora users to build their own version. Users whose distribution does not track the btrfs-progs repository so closely may want to install their own version built from the repository.

Creating and mounting Btrfs filesystems

The utility to create a Btrfs filesystem is, unsurprisingly, mkfs.btrfs; it can be invoked directly or via the mkfs program. In its simplest form, it can be run as:

    mkfs.btrfs /dev/partition-name

Where partition-name is, of course, the actual name of the partition that is to contain the filesystem.

Naturally, mkfs.btrfs has a fair number of options, though fewer than some other filesystems offer. Some of those that are relevant for basic usage include --force (necessary to convince mkfs.btrfs to overwrite an existing filesystem on the target partition), --label to set a label, and --version to just print out the version number and exit. One can also specify --mixed to cause the filesystem to mix data and metadata blocks together. Normally that will slow things down, so it is only recommended for situations where space is at an absolute premium; the man page suggests only using it for filesystems up to 1GB in size.

Btrfs filesystems are made accessible via the mount command as usual. Like most non-trivial filesystems, Btrfs has a number of specialized mount options that can be used to control its behavior. Some of these options will be discussed in later installments; a few that are of general interest include:

autodefrag

Enables automatic defragmentation of the filesystem in the background while it is running. Comments in the documentation suggest that this feature is still under development and may not produce optimal results for all workloads.

compress [=zlib|lzo|no]

Turn on compression of data. With an argument, it specifies which compression algorithm should be used. The compress-force option forces the use of compression even on files that do not compress well.

nodatacow

Turns off the copy-on-write mechanism, but only for newly created files. Turning off COW removes an important integrity mechanism and disables compression and data checksumming. In a few situations (the documentation says "large database files") there may be a significant performance improvement, but most users will probably not want to use this option.

nodatasum

Turns off the creation of data checksums for newly created files.

A mounted Btrfs filesystem feels mostly like any other Linux filesystem. Every now and then, some differences leak out. It can be disconcerting, for example, to delete a large file and not see an increase in the amount of available free space. Look back a minute or two later, though, and the missing space will have reappeared — assuming, of course, that said large file does not exist in any snapshots. Btrfs does a lot more work in the background than many other filesystems do.

Other Btrfs tools

The btrfs-progs repository contains a number of programs beyond mkfs.btrfs. One of the more recent additions is the btrfsck filesystem check and repair tool. The man page makes the newness of this tool clear: "Considering it is not well-tested in real-life situations yet, if you have a broken Btrfs filesystem, btrfsck may not repair but cause additional damages." So users will want to think hard before running btrfsck in the --repair mode and, probably, make use of the "restore" functionality described below.

The lack of a battle-hardened btrfsck utility remains one of the top reasons why system administrators often shy away from this filesystem. But the sad truth is that the only way to really make a truly comprehensive filesystem repair tool is to observe, over time, the ways in which a filesystem can become corrupted and come up with ways to fix those problems. So btrfsck will eventually mature into a tool that can handle a wide variety of problems, but there are no easy ways to shortcut that process.

Meanwhile, anybody working with Btrfs will eventually need to make use of another tool, called simply btrfs. This tool is the Swiss Army Knife of the Btrfs world; it can be used to perform a wide variety of actions on a Btrfs filesystem. Thus, unsurprisingly, btrfs implements a large number of commands, many of which will be examined in the later parts of this series. A few that merit mention now are:

btrfs filesystem df filesystem

Provides free space information about the given filesystem with more detail than is available from the standard df command.

btrfs filesystem show [filesystem]

Print information about one or more of the available Btrfs filesystems.

btrfs filesystem defragment [file...]

Perform online defragmentation of a Btrfs filesystem; defragmentation is limited to the given files if they are specified.

btrfs restore device

This command will try to extract the data from the given device, which, presumably, contains a filesystem with problems. By using this tool prior to attempting to repair the filesystem with btrfsck, a system administrator can maximize the chances of retrieving the data from the device even if btrfsck fails badly. See this wiki page for details on how to use this tool.

btrfs scrub filesystem

Launch a "scrub" operation on the given filesystem; scrubbing involves checking metadata and data against the checksums stored in the filesystem and correcting any errors found. Scrubbing can take some time, needless to say; it can be paused and resumed with variants of the btrfs scrub command if need be.

btrfs send subvol

btrfs receive mount

Controls the send/receive functionality, which can be used to replicate filesystems remotely or to implement incremental backup operations.

The basics described thus far are enough to get started with Btrfs, treating it as just another Unix-style filesystem, possibly with added compression and data checksumming. But it's the advanced features of the Btrfs filesystem that make it truly unique in the Linux world. One of those features — the built-in multiple-device and RAID functionality — will be the subject of the next installment in this series.

Comments (13 posted)