Kernel development

Kernel release status

The current development kernel is 4.5-rc7, released on March 6. Linus said: "So things have finally calmed down this past week, and I think we'll end up with a normal release where rc7 is the last rc."

Stable updates: 4.4.4, 3.14.63, and 3.10.99 were released on March 3. The 4.4.5, 3.14.64, and 3.10.100 updates are in the review process as of this writing; they can be expected on or after March 10.

Comments (none posted)

Some departures from linux-next

In his role as the maintainer of the linux-next tree, Stephen Rothwell has a comprehensive view of development activity across the kernel. He has recently announced his intention to drop a number of repositories that have been inactive for a year or more from linux-next. The list is interesting, as it highlights areas of past (and possibly present) interest where development activity has come to a halt.

The trees being removed are:

• APM (the obsolete power-management mechanism).
• The bcm2835 driver.
• kgdb: merged, and, presumably, not needing further work.
• lblnet (labeled networking, also merged).
• llvmlinux (building the kernel with the LLVM compiler).
• mips-fixes; MIPS patches follow other paths now.
• MMC: MultiMediaCard device support. MMC patches seem to go via other trees now.
• Random-number generation.
• rpmsg: the remote processor messaging subsystem.
• The squashfs compressed filesystem.
• Tiny, the home of the kernel tinification project.

So far, none of the maintainers who have responded have objected to the removal of their trees. That does not necessarily mean that the projects are dead; as Stephen pointed out, adding the trees back to linux-next is easily done should they become active again.

Comments (none posted)

Some 4.5 Development statistics

When Linus released the 4.5-rc7 prepatch, he indicated that it would probably be the last one prior to the official 4.5 release. That means we're running a bit late for the traditional article full of statistics for this development cycle. So, without further ado, here is a look at the changes that came in during the 4.5 cycle and where they came from.

As of this writing, just over 12,000 non-merge changesets have landed in the mainline repository for 4.5. That makes 4.5 one of the quieter development cycles in the last year; less than 4.2 and 4.4 (both over 13,000 changesets) but approximately equal to 4.1 and 4.3. All things are relative, of course; not that long ago, 12,000 changes would have been one of the busiest cycles. Even when the kernel community slows down a bit, there is a lot going on.

These changes were contributed by 1,528 developers — short of the 1,575 seen in 4.4 or the 1,625 in 4.3, but, once again, a fair crowd of contributors. The most active of these developers were:

Most active 4.5 developers

By changesets Linus Walleij 236 2.0% Arnd Bergmann 226 1.9% Leo Kim 210 1.7% Mauro Carvalho Chehab 169 1.4% Geert Uytterhoeven 159 1.3% Ville Syrjälä 126 1.0% Kuninori Morimoto 112 0.9% Takashi Iwai 108 0.9% Jiri Olsa 104 0.9% Christoph Hellwig 102 0.8% Julia Lawall 101 0.8% Glen Lee 101 0.8% Javier Martinez Canillas 89 0.7% Geliang Tang 89 0.7% Dan Carpenter 85 0.7% Daniel Vetter 81 0.7% Boris Brezillon 80 0.7% Alex Deucher 80 0.7% Kirill A. Shutemov 77 0.6% Thierry Reding 74 0.6%

By changed lines Doug Ledford 53086 7.7% Tomi Valkeinen 36631 5.3% Eric Huang 22714 3.3% Alex Deucher 16604 2.4% yanyang1 11129 1.6% Igal Liberman 10569 1.5% Thierry Reding 9842 1.4% Bard Liao 9762 1.4% Christoph Hellwig 9680 1.4% Arnd Bergmann 9233 1.3% Geert Uytterhoeven 8325 1.2% Stephen Boyd 8183 1.2% Paul E. McKenney 7485 1.1% Rex Zhu 7382 1.1% The etnaviv authors 7238 1.1% Jammy Zhou 7175 1.0% Mauro Carvalho Chehab 6473 0.9% Eric Anholt 6234 0.9% Maruthi Srinivas Bayyavarapu 5239 0.8% Adam Thomson 5153 0.7%

Linus Walleij topped the by-changesets list with a lot of low-level work, mostly near the GPIO subsystem and drivers that use it. Arnd Bergmann works all over the tree, mostly dealing with build problems and improving ARM multiplatform support. Leo Kim worked exclusively on cleaning up the wilc1000 driver in the staging tree, Mauro Carvalho Chehab made many improvements as the maintainer of the media subsystem, and Geert Uytterhoeven did a lot of work in the ARM and related driver subsystems.

In many development cycles, this list has been dominated by developers working in the staging subsystem, but 4.5 is an exception: only two of the developers in the by-changesets column had any significant work in the staging tree at all. Both of them, as it turns out, were working on the wilc1000 driver.

In the lines-changed column, longtime contributor Doug Ledford got to the top with three changesets removing three unloved staging drivers, deleting 53,000 lines of code. Tomi Valkeinen did a lot of work with the TI OMAP subarchitecture, while Eric Huang, Alex Deucher, and "yanyang1" all added functionality to the AMD graphics drivers. Further down that list, "the etnaviv authors" is an alias that was used for a single patch adding the Etnaviv graphics driver; it represents the work of Christian Gmeiner, Russell King, and Lucas Stach.

Work on the 4.5 kernel was supported by just over 200 companies that we could identify — a typical number. The employers supporting the most work this time were:

Most active 4.5 employers

By changesets Intel 1734 14.4% (Unknown) 975 8.1% Red Hat 732 6.1% Linaro 723 6.0% (None) 628 5.2% Samsung 513 4.3% SUSE 382 3.2% Atmel 380 3.2% Renesas Electronics 360 3.0% IBM 346 2.9% AMD 283 2.4% Mellanox 275 2.3% (Consultant) 245 2.0% Broadcom 208 1.7% Oracle 179 1.5% Google 160 1.3% Texas Instruments 152 1.3% Huawei Technologies 141 1.2% NVidia 137 1.1% ARM 127 1.1%

By lines changed Red Hat 83657 12.1% Intel 80160 11.6% AMD 74673 10.8% Texas Instruments 41808 6.1% (Unknown) 27958 4.1% IBM 25433 3.7% Linaro 22198 3.2% (None) 21929 3.2% Mellanox 19558 2.8% Samsung 19190 2.8% Renesas Electronics 17964 2.6% (Consultant) 15593 2.3% NVidia 15038 2.2% Freescale 13964 2.0% Code Aurora Forum 13514 2.0% Atmel 10845 1.6% Realtek 10090 1.5% Rockchip 9735 1.4% Huawei Technologies 7992 1.2% Broadcom 7930 1.2%

Intel is, by now, the dominant contributor; it would have been at the top of both lists except for the aforementioned drivers removed by Doug Ledford. Red Hat, which once reliably sat at the top of the list, may soon be overshadowed by companies working in the mobile and embedded space. In general, though, this table looks much like it has for some time.

If we look at non-author signoffs — the addition of Signed-off-by tags to patches by developers other than the author — the story looks just a little different:

Most non-author signoffs in 4.5
Developers Greg Kroah-Hartman 1009 9.0% David S. Miller 950 8.5% Mark Brown 585 5.2% Andrew Morton 451 4.0% Martin K. Petersen 264 2.4% Arnaldo Carvalho de Melo 263 2.3% Mauro Carvalho Chehab 235 2.1% Glen Lee 210 1.9% Rafael J. Wysocki 205 1.8% Kalle Valo 193 1.7%	Companies Red Hat 1981 17.8% Intel 1459 13.1% Linux Foundation 1029 9.2% Linaro 1003 9.0% Google 632 5.7% Samsung 447 4.0% (None) 361 3.2% Oracle 295 2.7% IBM 288 2.6% SUSE 265 2.4%

To a first approximation, this table represents the most active subsystem maintainers — the developers who make the decision to accept any given patch. While the more traditional, enterprise-oriented companies remain at the top of this list, the curve has been flattening over time as more companies take responsibility for the maintenance of parts of the kernel.

Finally, it has been a while since we looked at what the most active companies are most interested in. That is a simple matter of picking out the patches contributed by a given company's developers and noting which files were touched. So, for example, here is where Intel works:

Intel
%	Subsystem	Notes
67%	drivers/	29% gpu, 15% net, 5% staging
12%	include/
9%	sound/
5%	net/
5%	arch/	3.3% x86
4%	kernel/
4%	mm/

Intel, clearly, is focused on drivers for its hardware and CPUs, as one might expect. The picture for Red Hat is a bit different:

Red Hat
%	Subsystem	Notes
29%	drivers/	6% gpu, 5% net, 3% tty
22%	tools/	19% perf
17%	fs/	4% xfs, 3% nfs, 3% gfs2, 2% namei.c, 1% btrfs, 1% ceph, 1% f2fs, 1% ext4
14%	include/
13%	arch/	4% x86, 2% arm, 2% s390, 1% powerpc, 1% sparc
7%	kernel/
5%	net/
3%	crypto/

Red Hat's contribution to the tools directory (and the perf tool in particular) has increased over the years, but the company still works all over the kernel, putting a significant part of its effort into the core kernel code.

What about Linaro, which has been increasing its contributions over the years?

Linaro
%	Subsystem	Notes
66%	drivers/	17% gpio, 7% clocksource, 7% pinctrl, 4% mfd, 4% staging, 4% net
25%	arch/	19% arm, 4% arm64, 1% mips
6%	include/
3%	sound/
3%	Documentation/

Linaro is all about hardware enablement, and its work shows that. Even the work in the documentation directory is aimed that way: almost all of it happened in the devicetree subdirectory. (Lest anybody worry that the numbers add up to over 100%, remember that many patches touch more than one subdirectory, and are thus counted more than once).

Many of the other companies on the list have similar patterns; they tend to be interested in support for their own hardware, so that is where their work is done. Something slightly different can be seen if one skips down the list and looks at Google, though:

Google
%	Subsystem	Notes
29%	drivers/	9% net, 8% input, 5% usb, 4% md, 3% pci
31%	net/	15% ipv4, 9% core, 8% ipv6
17%	include/
15%	arch/	10% x86, 3% powerpc, 2% arm, 2% arm64
6%	fs/	3% ext4

Many of the improvements to the networking subsystem have, in recent years, come from Google; the numbers here show that Google is still interested in making Linux networking better.

All of this activity is the result of around 200 companies and numerous individuals, all working in pursuit of their own interests without any sort of overall control. As one might expect, the outcome can be a bit patchy at times; less energy goes into areas like documentation and security than one might like. But we still get a quickly evolving, highly capable kernel out of it, and that doesn't look like it will change anytime soon.

Comments (3 posted)

In-band deduplication for Btrfs

"In-band deduplication" is the process of detecting and unifying duplicate data blocks as files are being written, rather than at some later time. Btrfs support for this feature has been under development since at least early 2013. Quite recently it reached the point where developer Qu Wenruo thought it was sufficiently ready to send Btrfs maintainer Chris Mason a pull request (as yet unanswered) hoping that it might be added to the kernel during the 4.6 merge window. While this is far from a magic bullet that will suddenly remove all the waste in your filesystem that is caused by duplicate data, there are use cases where it could bring real benefits.

Offline and in-band

It has been possible to unify duplicated blocks in Btrfs since Linux 3.12 when the BTRFS_IOC_FILE_EXTENT_SAME ioctl() command was added (it has since been renamed FIDEDUPERANGE when the basic ioctl() handling was moved to the VFS, so it could someday be used by other filesystems). This ioctl() is given a range of bytes in the file (which must be aligned to the filesystem block size) and a list of offsets in other files (or possibly the same file). This identifies two or more ranges of the same size that are claimed to be identical. Btrfs reads all the blocks, checks that they are in fact identical, and then changes its internal bookkeeping so that all files point to one set of blocks on the storage medium. The space used by the other copies of the data will typically become free space available for reallocation.

To understand how this works it is necessary to understand how Btrfs makes use of "extents". An extent is a contiguous set of blocks on the storage device and also a contiguous set of blocks in a file (at least initially). It has a "logical address" that is mapped to a physical location on one, or perhaps more, of the underlying devices. An extent can become part of several different files, either through snapshots, reflinks, or deduplication. To allow this storage space to ultimately be reused, Btrfs maintains a reference count for each extent and will not re-use any of the space until that count becomes zero.

It is not generally possible to split an extent. If a single block is written into the middle of a large extent, the "copy on write" design of Btrfs requires that either the whole extent be copied or that the file's indexing information be changed to point to the first half of the extent, then the new block, then the remainder of the extent. Btrfs takes the latter approach.

When FIDEDUPERANGE is used, the file indexes will be updated to point to the relevant extents or partial extents of the source file, and the reference counts on the various extents will be increased or decreased as appropriate. This may not release quite as much space as expected since there may have been extents that were only partially identical between two files. The identical part in one extent may have no files including it any more, but the space will not be freed until the whole extent is no longer referenced.

duperemove is a tool that can be used to examine a set of files, look for duplicated regions, and call the ioctl to remove that duplication from the underlying storage. This can be useful anywhere that files are likely to be completely or largely the same, but where they need to be kept separate for administrative or other practical reasons. A common use case is filesystem images used for virtualization or the multiple similar-but-not-identical file sets used by containers. Running duperemove from time to time could save a lot of disk space.

This functionality was referred to in the initial commit as "offline deduplication", which is a little confusing since "offline" in the context of filesystems usually implies that the filesystem isn't mounted, and that is not the case here. It is more like "on-demand" deduplication and is sometimes referred to as "batch" deduplication. This contrasts with the new work that could be called "time-of-write" or transparent deduplication, but is called "in-band" deduplication in this patch set.

When duperemove runs, it computes a hash value for every block in every file and then compares these, looking for ranges of matching blocks. When it finds suitable ranges, it requests the deduplication. In-band deduplication uses the same idea of hashing blocks of data, but in many other respects it is quite different.

In-band duplication works in units of extents of a specific size — a deduplication block size of up to 8MB can be configured; the default is 128KB. When data is written out to storage, blocks are gathered into extents of this size whenever possible. If there are only sufficient blocks being written for a smaller extent, that extent will be written without deduplication. For every extent of the target size, the hash (currently SHA-256, though possibly configurable in the future) is calculated. If another extent can be found with the same hash, then a new reference is added to that extent and the new data is not written. If no match is found, the data is written as normal and the hash is stored together with the logical address of the extent so that it is available for future matching.

This process can be enabled for a whole Btrfs filesystem using the "btrfs dedup enable" command and then disabled for individual files or directories by using the "btrfs property set" command to set the "dedup" property to "disable". Setting this on a directory causes all files or directories created within that directory to inherit the setting. This means that enabling deduplication on only a subset of a filesystem is possible, but a little bit clumsy.

Two back-ends

There are two separate back-ends for storing the mapping between hashes and extents; the fact that the implementation of these back-ends is kept cleanly separate from their use is rightfully highlighted as a strength of this patch set.

One of the two back-ends is an in-memory mapping. Two red-black trees are created when the filesystem is mounted; whenever new data is written to a file on which deduplication is enabled, new entries are added to the trees. One tree maps from hash to logical address and is used to see if a suitable extent exists that already stores the required data. The second provides a reverse mapping that allows hash entries to be deleted when an extent is freed after its reference count reaches zero. The size of these trees is limited by a configurable entry count that defaults to 32768. It would not be surprising to see that replaced or augmented with a "shrinker" callback from the memory management subsystem, so that it could shrink only when memory is tight.

The second mechanism stores these mappings in the filesystem. Btrfs has flexible data structures for storing all sorts of metadata and data on disk using a number of distinct B-trees, one for each subvolume, one for the extent reference counts, one for storing checksums, etc. The in-band deduplication patchset adds another B-tree that has two types of keys: one for lookup by hash and another for lookup by extent address.

Looking up the hash in the B-tree is not quite so straightforward as one might hope, since Btrfs has a fixed format for the lookup key: a 64-bit object-ID, an eight-bit type, and a 64-bit offset. It is not possible to store the full 256-bit hash in the key and even storing 128 bits in the two 64-bit fields would be problematic. Btrfs requires that all keys be unique, so that approach would effectively limit the hash size to 128 bits.

The approach chosen is to store 64 bits of the hash in the object-ID, and the logical address of the extent in the offset field. Each key is accompanied by a variable-length data field and this is used to store the full hash. If the hashes of two extents collide in those 64 bits, the offsets will still be different, so the keys will be unique.

To handle these collisions a lookup first performs a regular B-tree search for a key with the appropriate hash bits in the object-ID and U64_MAX in the offset field. This will provide the last possible location where the target hash could be stored. A linear search is then performed searching backward and comparing the full hash until a match is found or there are no more keys with the required hash fragment.

Unlike with in-memory lookup there is no mechanism to limit the number of hash entries stored, beyond normal filesystem-full checks that might prevent a new extent from being written.

One difference between this in-band deduplication and the on-demand approach that is worth highlighting is the dependence placed on the hash. duperemove uses a hash only to guide the search for duplicate blocks — the hash is not authoritative and Btrfs will not allow the deduplication to happen if the identified regions are not byte-for-byte identical. In-band duplication as currently implemented does not perform that comparison. If the hash matches, then the extents are assumed to match. This means the correctness of the deduplication is completely dependent on the uniqueness of the hash, so the extra effort to make use of all 256 bits is easy to justify. Whether that complete dependence is itself justified is not an easy question to answer. It is certainly extremely unlikely for two distinct blocks to have the same hash, but it is also certainly quite possible. It would only need to cause corruption once to be extremely embarrassing. Adding byte-for-byte comparison is on the planned feature list but, according to Wenruo, "not anytime soon".

In-band deduplication brings the benefit of being automatic, but has a cost that it will probably miss duplication that duperemove could find. Different alignment of extents between files would completely defeat the duplicate detection, as would creating files before deduplication was enabled. The former could be improved to some degree with a smaller extent size, though that would brings costs of its own. As is so often the case, finding the most effective solution — which could include a mix of offline and in-band deduplication — will be highly dependent on each particular use case.

Test, test, and test

Wenruo assures us that this patch set has seen quite a lot of testing and that it has been some time since the last of the bugs found by that testing was fixed, which is encouraging. Some new tests have been submitted for the xfstests test suite specifically to exercise the deduplication and to check for some of the bugs that have been found and fixed.

One aspect of testing that seemed strangely absent from the pull request was any hint of how in-band deduplication affects performance. It is to be expected that this sort of functionality would slow writes down, particularly when the table of hashes is not kept in memory. It could also speed up some writes if lots of duplicate extents are found. Some indication of the sort of performance change experienced would certainly help to complete the picture.

But maybe the hope is to crowdsource that testing. There are so many different possible hardware configurations and usage scenarios to test that it is hard for one developer to even begin to give meaningful results. A large community, on the other hand, can try lots of things in parallel. As Wenruo noted in his pull request, there is still work to be done, but it should be quite ready for people to test.

Trying it out requires some patches to the btrfs-progs along with the Git tree from the pull request, but that should be no challenge for those who enjoy compiling their own kernels. I'm sure additional results would be most welcome.

Comments (21 posted)

Architecture emulation containers with binfmt_misc

Containers bring a lot of advantages in the areas of security and systems administration; they can be used to run lightweight virtual "systems" in isolation from each other and the host system. Since containers lack their own kernel — they run directly on the host-system kernel — one does not ordinarily expect them to be built for an architecture other than the host they are running on. But it turns out that there are use cases for such containers, and that they can be run using the somewhat obscure "binfmt_misc" kernel mechanism if a small patch set is applied.

binfmt_misc

When an executable file is provided to one of the exec*() system calls, the kernel normally expects to find a native binary for the system it is running on. The kernel has long had a mechanism by which it can recognize other executable-file formats and run them, though. The classic example is the module that looks for a file that begins with "#!" — the marker for a shell script. When such a file is recognized, the name of the interpreter for the script will be read from the first line of the file; the interpreter will then be run with the file as its standard input.

But one can imagine many other possible formats for executable files. These could be binaries built for a different operating system (DOS binaries that could be run with DOSEMU, for example) or byte-code binaries that need to run on a specific machine (such as Java byte code). One could try to code awareness of all these formats into the kernel, but that gets unwieldy after a while. It also lacks flexibility, which is unfortunate; the kernel developers are never going to know about all of the possible executable formats that might be of interest.

The obvious solution is to allow user space to describe new executable formats to the kernel; that is the role of the binfmt_misc mechanism. If this feature is configured into the kernel (as it usually is), a system administrator can add a new executable format by writing a special string to /proc/sys/fs/binfmt_misc/register. That string includes:

• A way for the kernel to recognize the new format. It can either be a particular file extension, or a "magic number" found near the beginning of the file.

• The name of the interpreter that is to be run to execute files with this format.

• Some flags that control how the argv array is created and, essentially, whether files in this format can be setuid or not.

The full details of how it all works can be found in Documentation/binfmt_misc.txt in the kernel source tree.

It is not hard to see how binfmt_misc can be used to run binaries built for a different architecture. It is a simple matter of describing those binaries and naming an emulator (QEMU, for example) that is able to run the binaries. That works well for binaries to be run directly on the host system, but it can be a bit more challenging to run a container that is built for another architecture.

Architecture emulation in containers

The problem, as James Bottomley pointed out in this brief patch set, is that binfmt_misc has to locate and run the interpreter binary at the time that the foreign binary is invoked. This invocation happens within the container, so the interpreter has to be visible in the container as well, but, likely as not, the container is running within a namespace intended to keep it from seeing the rest of the system. As a result, the interpreter must be placed inside the container itself. That complicates what would otherwise be containerized system built entirely for the emulated architecture. It also forces any orchestration system to be aware of the emulation within the container and set things up accordingly, making emulated containers less transparent than they would otherwise be.

The solution is to add a new mode for binfmt_misc wherein the interpreter binary is opened by the kernel when the new format is initially set up. When a binary in that format is encountered, the already-opened interpreter can be run, rather than seeking out and opening the interpreter at that time. This mechanism will work inside a container that otherwise has no access to the interpreter; the kernel already has the interpreter open, so it can run it directly.

This mode is set up by using the new "F" flag when describing the format to binfmt_misc. Once the kernel has opened the interpreter file, it will keep it open until the format is removed. That means that updates to the interpreter binary will not take effect unless the format is removed and reestablished. That should not ordinarily be a problem, but it could be a surprise for system administrators who are not aware of this behavior.

The patch set received a small number of generally favorable reviews. If it is merged, as seems likely, it will make it easier to run containers built for a number of machine architectures on the same host, making Linux containers more flexible in general.

Comments (9 posted)