LWN.net Weekly Edition for September 4, 2008

Feature removal sparks Git flamewar

Removing features from a tool is never easy. Once there is enough of a user base to complain about annoyances, there is also a vocal group that uses and likes those same annoyances. The recent removal of the git-foo style commands from Git is just such a case, but many of those using those commands did not find out about the removal until after the change was made, which only served to increase their outrage.

Until version 1.6.0, Git has always had two ways to invoke the same functionality: git foo and git-foo. This was done by installing many—usually more than 100—different entries into /usr/bin for all of the different git subcommands. Some were concerned that Git was polluting that directory, but the bigger issue was the effect on new users. Partially because of shell autocompletion, a new user might be overwhelmed by the number of different Git commands available; even regular users might find it difficult to find the command they are looking for if they have to sort through 100 or more.

Many of the Git subcommands that exist are not necessarily regularly used. There are quite a number of "plumbing" commands that rarely, if ever, should be invoked by users. Those are best hidden from view, which can be done by moving them out of /usr/bin. This has been done for the 1.6.0 release, but Junio Hamano opened up a can of worms when he posted a request for discussion about taking the next step to the Git mailing list.

In the 1.6.0 release, the only things exposed in /usr/bin are the git binary itself along with a few other utilities; the rest have been moved to /usr/libexec/git-core. The hard links for each of the git-foo commands have been maintained in the new location, which allows folks that still want the old behavior to get it by adding:

    PATH="$PATH:$(git --exec-path)"

Unfortunately, for many users, the first they heard about this change was when things stopped working after they installed 1.6.0. The Git team admittedly did not get the word out very well; by trying to be nice, they missed an opportunity to make users notice the change. As Hamano puts it:

Hamano got caught in the middle to some extent as he wasn't particularly in favor of the original change, but at the time it was decided, there were few advocates for keeping 100+ commands in /usr/bin. There were several complaints about having that many commands, but chief amongst them was confusion for new users. By removing them from /usr/bin and providing an autocompletion script for bash that completes only a subset of the git subcommands, users will have fewer options to scan through—and to be scared of.

The original plan called for moving the dash-style commands out, which has been done, but also eventually removing the links for any of the git-foo commands that are implemented in the core git binary. Over time, much of the functionality that was handled by external commands has migrated into the main git program. It is the eventual removal of the links that Hamano is asking about in his message, but much of the response was flames about the step already taken; some could not see any advantage to moving the git-foo commands out of /usr/bin.

David Woodhouse is one of those who wants things to remain the same:

Several others agreed, but that particular horse had already left the barn. Throughout the thread, Linus Torvalds was increasingly strident about the $PATH-based workaround, which effectively ends the discussion that Hamano was trying to have. For that workaround to continue working, the links must be installed in /usr/libexec/git-core. Though it strays from the original intent, it is a reasonable compromise, one that will serve git-traditionalists as well as new users and others who no longer want the git-foo syntax.

Two things have helped keep the controversy alive: some documentation, test, and example scripts still refer to dash-style commands, but worse than that, one must do man git-foo to get the man page for that subcommand. It is a convention within the Git community to use the dash style when referring to commands in text, which explains some of the usage. Because man requires a single argument, the dash style is used there as well, though git help foo is a reasonable alternative. For users who started relatively early with Git, and are aware of the dash style commands, these examples further muddy the water.

It is a difficult problem. Projects must have room to change, but once users become used to a particular way of doing things, they will resist changing—sometimes quite loudly. As Petr "Pasky" Baudis points out, though, Git is still evolving:

The Git developers still see it as a young tool that may still undergo some fairly substantial modifications, while the hardcore users see it is a fixed tool that they use daily—or more frequently—to get work done. The tension between those two views is what leads to flamewars like we have seen here. Certainly the Git folks could have done a much better job in getting the word out—Hamano was looking for suggestions on how to do that better in his original post—but users are going to have to be flexible as well.

Comments (22 posted)

DRI, BSD, and Linux

The DRI project makes its home at freedesktop.org. Among other things, the project maintains a set of git repositories representing various views of the current state of DRI development (and the direct rendering manager (DRM) work in particular). This much is not unusual; most Linux kernel subsystems have their own repository at this point. The DRM repository is different, though, in that it is not based on any Linux kernel tree; it is, instead, an entirely separate line of development.

That separation is important; it means that its development is almost entirely disconnected from mainline kernel development. DRM patches going into the kernel must be pulled out of the DRM tree and put into a form suitable for merging, and any changes made within the kernel tree must be carefully carried back to the DRM tree by hand. So this work is not just an out-of-tree project; it's an entirely separate project producing code which is occasionally turned into a patch for the Linux kernel. It is not surprising that DRM and the mainline tend not to follow each other well. As Jesse Barnes put it recently:

The result of all this has been a lot of developer frustration, trouble getting code merged, concerns that the project is hard for new developers to join, and more. As the DRM developers look to merge more significant chunks of code (GEM, for example), the pressure for changes to the development process has been growing. So Dave Airlie's recent announcement of a proposed new DRM development process did not entirely come as a surprise. There are a number of changes being contemplated, but the core ones are these:

• The DRM tree will be based on the mainline kernel, allowing for the easy flow of patches in both directions. The old tree will be no more.

• A more standard process for getting patches to the upstream kernel will be adopted; these will include standard techniques like topic branches and review of patches on the relevant mailing lists.

• Users of the DRM interface will not ship any releases depending on DRM features which are not yet present in the mainline kernel.

The result of all this, it is hoped, will be a development process which is more efficient, more tightly coupled to the upstream kernel, and more accessible for developers outside of the current "DRM cabal." These are all worthy objectives, but there may also be a cost associated with these changes resulting from the unique role the DRI/DRM project has in the free software community.

There is clearly a great deal of code shared between Linux and other free operating systems, and with the BSD variants in particular. But that sharing tends not to happen at the kernel level. The Linux kernel is vastly different from anything BSD-derived, so moving code between them is never a straightforward task. GPL-licensed code is not welcome in BSD-licensed kernels, naturally, making it hard for code move from Linux to BSD even when it makes sense from a technical point of view. When code moves from BSD to Linux, it often brings a certain amount of acrimony with it. So, while ideas can and do move freely, there is little sharing of code between free kernels.

One significant exception is the DRM project, which is also used in most versions of BSD. One of the reasons behind the DRM project's current repository organization is the facilitation of that cooperation; there are separate directories for Linux code, BSD code, and code which is common to both. Developers from all systems contribute to the code (though the BSD developers are far outnumbered by their Linux counterparts), and they are all able to use the code in their kernels. When working in the common code directory, developers know to be careful about not breaking other systems. All told, it is a bit of welcome collaboration in an area where development resources have tended to be in short supply - even if it benefits the BSD side more than Linux.

Changing the organization of the DRM tree to be more directly based on Linux seems unlikely to make life easier for the BSD developers. Space for BSD-specific code will remain available in the DRM repository, but turning the "shared-code" directory into code in the Linux driver tree will make its shared status less clear, and, thus, easier for Linux developers to break on BSD. Additionally, it seems clear that this code may become more Linux-specific; Dave Airlie says:

Much of this functionality can be reproduced through compatibility layers on the BSD side, but it must carry a bit of a second-class citizen feel. Dave has, in fact, made that state of affairs clear:

The fact that fewer people will be able to commit to the new repository - in fact, it may be limited to Dave Airlie - also does not help. So FreeBSD developer Robert Noland, while calling this proposal "the most fair" of any he has heard, is far from sure that he will be able to work with it:

On the other hand, it's worth noting that OpenBSD developer Owain Ainsworth already works in his own repository and seems generally supportive of these changes.

Given the difference between the numbers of Linux-based and BSD-based developers, it seems almost certain that a more Linux-friendly process will win over. There is one rumored change which will not be happening, though: nobody is proposing to relicense the DRM code to the GPL. The DRM developers are only willing to support BSD to a certain point, but they certainly are not looking to make life harder for the BSD community. So they will try to accommodate the BSD developers while moving to a more Linux-centric development model; that is how things are likely to go until such a time as the BSD community is able to bring more developers to the party.

Comments (27 posted)

The Kernel Hacker's Bookshelf: UNIX Internals

Back in 2001, I landed my (then) dream job as a full-time Linux kernel developer and distribution maintainer for a small embedded systems company. I was thrilled - and horrified. I'd only been working as a programmer for a couple of years and I was sure it was only a matter of time before my new employer figured out they'd hired an idiot. The only solution was to learn more about operating systems, and quickly. So I pulled out my favorite operating systems textbook and read and re-read it obsessively over the course of the next year. It worked well enough that my company tried very hard to convince me not to quit when I got bored with my "dream job" and left to work at Sun.

That operating systems textbook was UNIX Internals by Uresh Vahalia. UNIX Internals is a careful, detailed examination of multiple UNIX implementations as they evolved over time, from the perspective of both the academic theorist and the practical kernel developer. What makes this book particularly valuable to the practicing operating systems developer is that the review of each operating systems concept - say, processes and threads - is accompanied by descriptions of specific implementations and their histories - say, threading in Solaris, Mach, and Digital UNIX. Each implementation is then compared on a number of practical levels, including performance, effect on programming interfaces, portability, and long-term maintenance burden - factors that Linux developers care passionately about, but are seldom considered in the academic operating systems literature.

UNIX Internals was published in 1996. A valid question is whether a book on the implementation details of UNIX operating systems published so long ago is still useful today. For example, Linux is only mentioned briefly in the introduction, and many of the UNIX variants described are now defunct. It is true that UNIX Internals holds relatively little value for the developer actively staying up to date with the latest research and development in a particular area. However, my personal experience has been that many of the problems facing today's Linux developers are described in this book - and so are many of the proposed solutions, complete with the unsolved implementation problems. More importantly, the analysis is often detailed enough that it describes exactly the changes needed to improve the technique, if only anyone took the time to implement them.

In the rest of this review, we'll cover two chapters of UNIX Internals in detail, "Kernel Memory Allocation" and "File System Implementations." The chapter on kernel memory allocation is an example of the historical, cross-platform review and analysis that sets this book apart, covering eight popular allocators from several different flavors of UNIX. The chapter on file system implementations shows how lessons learned from the oldest and most basic file system implementations can be useful when solving the latest and hottest file system design problems.

Kernel Memory Allocation

The kernel memory allocator (KMA) is one of the most performance-critical kernel subsystems. A poor KMA implementation will hurt performance in every code path that needs to allocate or free memory. Worse, it will fragment and waste precious kernel memory - memory that can't be easily freed or paged out - and pollute hardware caches with instructions and data used for allocation management. Historically, a KMA was considered pretty good if it only wasted 50% of the total memory allocated by the kernel.

Vahalia begins with a short conceptual description of kernel memory allocation and then immediately dives into practical implementation, starting with page-level allocation in BSD. Next, he describes memory allocation in the very earliest UNIX systems: a collection of fixed-size tables for structures like inodes and process table entries, occasional "borrowing" of blocks from the buffer cache, and a few subsystem-specific ad hoc allocators. This primitive approach required a great deal of tuning, wasted a lot of memory, and made the system fragile.

What constitutes a good KMA? After a quick review of the functional requirements, Vahalia lays out the criteria he'll use to judge the allocators: low waste (fragmentation), good performance, simple interface appropriate for many different users, good alignment, efficient under changing workloads, reassignment of memory allocated for one buffer size to another, and integration with the paging system. He also takes into consideration more subtle points, such as the cache and TLB footprint of the KMA's code, along with cache and lock contention in multi-processor systems.

[PULL QUOTE: This is an example of how even the oldest and clunkiest algorithms can influence the design of the latest and greatest. END QUOTE] The first KMA reviewed is the resource map allocator, an extremely simple allocator using a list of <base, size> pairs describing each free segment of memory, sorted by base address. The charms of the resource map allocator include simplicity and allocation of exactly the size requested; the vices include high fragmentation and poor performance under nearly every workload. Even this allocation algorithm is useful under the right circumstances; Vahalia describes several subsystems that still use it (System V semaphore allocation and management of free space in directory blocks on some systems) and some minor tweaks that improve the algorithm. One tweak to the resource map allocator keeps the description of each free region in the first few bytes of the region, a technique later used in the state-of-the-art SLUB allocator in the Linux kernel. This is an example of how even the oldest and clunkiest algorithms can influence the design of the latest and greatest.

Each following KMA is discussed in terms of the problems it solves from previous allocators, along with the problems it introduces. The resource map's sorted list of base/size pairs is followed by power-of-two free lists with a one-word in-buffer header (better performance, low external fragmentation, but high internal fragmentation, esp. for exact power-of-two allocations), the McKusick-Karels allocator (power-of-two free lists optimized for power-of-two allocation; extremely fast, but prone to external fragmentation), the buddy allocator (buffer splitting on power-of-two boundaries plus coalescing of adjacent free buffers; poor performance due to unnecessary splitting and coalescing), and the lazy buddy allocator (buddy plus delayed buffer coalescing; good steady-state performance but unpredictable under changing workloads). The accompanying diagrams of the data structures and buffers used to implement each allocator are particularly helpful in understanding the structure of the allocators.

After covering the simpler KMAs, we get into more interesting territory: the zone allocator from Mach, the hierarchical allocator from Dynix, and the SLAB allocator, originally implemented on Solaris and later adopted by several UNIXes, including Linux and the BSDs. Mach's zone allocator is the only fully garbage-collected KMA studied, with the concomitant unpredictable system-wide performance slowdowns during garbage collection, which would strike it from most developers' lists of useful KMAs. But as with the resource map allocator, we still have lessons to learn from the zone allocator. Many of the features of the zone allocator also appear in the SLAB allocator, commonly considered the current best-of-breed KMA.

The zone allocator creates a "zone" of memory reserved for each class of object allocated (e.g., inodes), similar to kmem caches in the later SLAB allocator. Pages are allocated to a zone as needed, up to a limit set at zone allocation time. Objects are packed tightly within each zone, even across pages, for very low internal fragmentation. Anonymous power-of-two zones are also available. Each zone has its own free list and once a zone is set up, allocation and freeing simply add and remove items from the per-zone free list (free list structures are also allocated from a zone). Memory is reclaimed on a per-page basis by the garbage collector, which runs as part of the swapper task. It uses a two-pass algorithm: the first pass counts up the number of free objects in each page, and the second pass frees empty pages. Overall, the zone allocator was a major improvement on previous KMAs: fast, space efficient, and easy to use, marred only by the inefficient and unpredictable garbage collection algorithm.

The next KMA on the list is the hierarchical memory allocator for Dynix, which ran on the highly parallel Sequent S2000. One of the major designers and implementers is our own Paul McKenney, familiar to many LWN readers as the progenitor of the read-copy-update (RCU) system used in many places in the Linux kernel. The goal of the Dynix allocator was efficient parallel memory allocation, in particular avoiding lock contention between processors. The solution was to create several layers in the memory allocation system, with per-cpu caches at the bottom and collections of large free segments at the top. As memory is freed or allocated, regions move up and down one level of the hierarchy in batches. For example, each per-cpu cache has two free lists, one in active use and the other in reserve. When the active list runs out of free buffers, the free buffers from the reserve list are moved onto it, and the reserve list replenishes itself with buffers from the global list. All the work requiring synchronization between multiple CPUs happens in one big transaction, rather than incurring synchronization overhead on each buffer allocation.

The Dynix allocator was a major advance: 3 - 5 times faster than the BSD allocator even on a single CPU. Its memory reclamation system was far more efficient than the zone allocator's, performed on an on-going basis with bounded worst case performance on each operation. Performance on SMP systems was unparalleled.

The final KMA in this chapter is the SLAB allocator, initially implemented on Solaris and later re-implemented on Linux and BSD. The SLAB allocator refined some existing techniques (simple allocation/free computations for small cache footprint, per-object caches) and introduced several new ones (cache coloring, efficient object reuse). The result is an allocator that was both the best performing and the most efficient by a wide margin - only 14% fragmentation versus 27% for the SunOS 4.1.3 sequential-fit allocator, 45% for the 4.4BSD McKusick-Karel allocator, and 46% for the SunOS 5.x buddy allocator.

Like the zone allocator, SLAB allocates per-object caches (along with anonymous caches in useful sizes) called kmem caches. Each cache has an associated optional constructor and destructor function run on the objects in a newly allocated and newly freed page, respectively (though the destructor has since been removed in the Linux allocator). Each cache is a doubly-linked list of slabs - large contiguous chunks of memory. Each slab keeps its slab data structure at the end of the slab, and divides the rest of the space into objects. Any leftover free space in the slab is divided between the beginning and end of the objects in order to vary the offset of objects with respect to the CPU cache, improving cache utilization (in other words, cache coloring). Each object has an associated 4-byte free list pointer.

The slabs within each kmem cache are in a doubly linked list, sorted so that free slabs are located at one end, fully allocated slabs at the other, and partially allocated slabs in the middle. Allocations always come from partially allocated slabs before touching free slabs. Freeing an object is simple: since slabs are always the same size and alignment, the base address of the slab can be calculated from the address of the object being freed. This address is used to find the slab on the doubly linked list. Free counts are maintained on an on-going basis. When memory pressure occurs, the slab allocator walks the kmem caches freeing the free slabs at the end of the cache's slab list. Slabs for larger objects are organized differently, with the slab management structure allocated separately and additional buffer management data included.

This section of UNIX Internals has aged particularly well, partly because the SLAB allocator continues to work well on modern systems. As Vahalia notes, the SLAB allocator initially lacked optimizations for multi-processor systems, but these were added shortly afterward, using many of the same techniques as the Dynix hierarchical allocator. Since then, most production kernel memory allocators have been SLAB-based. Recently, Christoph Lameter rewrote SLAB to get the SLUB allocator for Linux; both are available as kernel configuration options. (The third option, the SLOB allocator, is not related to SLAB - it is a simple allocator optimized for small embedded systems.) When viewed in isolation, the SLAB allocator may appear arbitrary or over-complex; when viewed in the context of previous memory allocators and their problems, the motivation behind each design decision is intuitive and clear.

File Systems Implementations

UNIX Internals includes four chapters on file systems, covering the user and kernel file system interface (VFS/vnode), implementations of on-disk and in-memory file systems, distributed/network file systems, and "advanced" file system topics - journaling, log-structured file systems, etc. Despite the intervening years, these four chapters are the most comprehensive and practical description of file systems design and implementation I have yet seen. I definitely recommend it over UNIX File System Design and Implementation - a massive sprawling book which lacks the focus and advanced implementation details of UNIX Internals.

The chapter on file systems implementations is too packed with useful detail to review fully in this article, so I'll focus on the points that are relevant to current hot file system design problems. The chapter describes the System V File System (s5fs) and Berkeley Fast File System (FFS) implementations in great detail, followed by a survey of useful in-memory file systems, including tmpfs, procfs (a.k.a. /proc file system), an early variant of a device file system called specfs, and a sysfs-style interface for managing processors. This chapter also covers the implementation of buffer caches, inode caches, directory entry caches, etc. One of the features of this chapter (as elsewhere in the book) is the carefully chosen bibliography. Bibliographies in research papers serve a double purpose as demonstrations of the authors' breadth of knowledge in the area and tend to be cluttered with more marginal references; the per-chapter bibliographies in UNIX Internals list only the most relevant publications and make excellent supplementary reading guides.

System V File System (s5fs) evolved from the first UNIX file system. The on-disk layout consisted of a boot block followed by a superblock followed by a single monolithic inode table. The remainder of the disk is used for data and indirect blocks. File data blocks are located via a standard single/double/triple indirect block scheme. s5fs has no block or inode allocation bitmaps; instead it maintains on-disk free lists. The inode free list is partial; when no more free inodes are on the list, it is replenished by scanning the inode table. Free blocks are tracked in a singly linked list rooted in the superblock - a truly terrifying design from the point of view of file system repair, especially given the lack of backup superblocks.

In many respects, s5fs is simultaneously the simplest and the worst UNIX file system possible: its throughput was commonly as little as 5% of the raw disk bandwidth, it was easily corrupted, it had a 14 character limit on file names, and so on. On the other hand, elements of the s5fs design have come back into vogue, often without addressing the inherent drawbacks still unsolved in the intervening decades.

The most striking example of a new/old design principle illustrated by s5fs is the placement of most of the metadata in one spot. This turned out to be a key performance problem for s5fs, as every uncached file read virtually guaranteed a disk seek of non-trivial magnitude between the location of the metadata at the beginning of the disk and the file data, located anywhere except the beginning of the disk. One of the major advances of FFS was to distribute inodes and bitmaps evenly across the disk and allocate associated file data and indirect blocks nearby. Recently, collecting metadata in one place has returned as a way to optimize file system check and repair time as well as other metadata-intensive operations. It also appears in designs that keep metadata on a separate high-performance device (usually solid state storage).

The problems with these schemes are the same as the first time around. For the fsck optimization case, most normal workloads will suffer from the required seek for reads of file data from uncached inodes (in particular, system boot time would suffer greatly). In the separate metadata device case, the problem of keeping a single, easily-corrupted copy of important metadata returns. Currently, most solid-state storage is less reliable than disk, yet most proposals to move file system metadata to solid state storage make no provision for backup copies on disk.

Another cutting edge file system design issue first encountered in s5fs is backup, restore, and general manipulation of sparse files. System administrators quickly discovered that it was possible to create a user-level backup that could not be restored because the tools would attempt to actually write (and allocate) the zero-filled unallocated portions of sparse files. Even more intelligent tools that do not explicitly write zero-filled portions of files still had to pointlessly copy pages of zeroes out of the kernel when reading sparse files. In general, the file and socket I/O interface requires a lot of ultimately unnecessary copying of file data into and out of the kernel for common operations. It has only been in the last few years that more sophisticated file system interfaces have been proposed and implemented, including SEEK_HOLE/SEEK_DATA and splice() and friends.

The chapters on file systems are definitely frustratingly out of date, especially with regard to advances in on-disk file system design. You'll find little or no discussion of copy-on-write file systems, extents, btrees, or file system repair outside of the context of non-journaled file systems. Unfortunately, I can't offer much in the way of a follow-up reading list; most of the papers in my file systems reading list are covered in this book (exceptions include the papers on soft updates, WAFL, and XFS). File systems developers seem to publish less often than they used to; often the options for learning about the cutting edge are reading the code, browsing the project wiki, and attending presentations from the developers. Your next opportunity for the latter is the Linux Plumbers Conference, which has a number of file system-related talks.

Another major flaw in the book, and one of the few places where Vahalia was charmed by an on-going OS design fad, is the near-complete lack of coverage of TCP/IP and other networking topics (the index entry for TCP/IP lists only two pages!). Instead, we get an entire chapter devoted to streams, at the time considered the obvious next step in UNIX I/O. If you want to learn more about UNIX networking design and implementation, this is the wrong book; buy some of the Stevens and Comer networking books instead.

Summary

UNIX Internals was the original inspiration for the Kernel Hacker's Bookshelf series, simply because you could always find it on the bookshelf of every serious kernel hacker I knew. As the age of the book is its most serious weakness, I originally intended to wait until the planned second edition was released before reviewing it. To my intense regret, the planned release date came and went and the second edition now appears to have been canceled.

UNIX Internals is not the right operating systems book for everyone; in particular, it is not a good textbook for an introductory operating systems course (although I don't think I suffered too much from the experience). However, UNIX Internals remains a valuable reference book for the practicing kernel developer and a good starting point for the aspiring kernel developer.

Comments (38 posted)

Page editor: Jonathan Corbet

Inside this week's LWN.net Weekly Edition

• Security: Find SQL injection vulnerabilities with sqlmap; New vulnerabilities in ruby, slash, wordnet.
• Kernel: Linux 3.0?; High-resolution timeouts; SCHED_FIFO and realtime throttling.
• Distributions: Spinning Fedora; PLD Live 2.0 beta3; Webconverger update; Tin Hat Linux
• Development: Cinelerra 4 arrives, KDE development changes, Google Chrome comic book, Kuchling on Python 2.6, new versions of Rivendell, rsplib, MySQL Admin Tools, SQLite, ClamAV, oVirt, Apache Lenya, Senayan 3, Jokosher, Openbravo POS, KDE, Elisa, VMPK, SABnzbdPlus, Roundup, GCC, ftputil, LEO.
• Press: Strip mining of open source, CSI Stick grabs cell phone data, Intel acquires Opened Hand, interviews with Krita developers and Sam Ramji, reviews of Fermi Linux, iRex iLiad and Linux Twitter clients, Red Hat's Perl bug.
• Announcements: GNU Project's 25th anniversary, Perl Summer of Code status, Perl Grant results, World Day Against Software Patents, Novell and SGI financials, MySQL Conf cfp, LF end user summit, MontaVista Vision 2008.