Keeping the Kernel

The 2.6 kernel includes many new features and improvements over previous releases. Kernel developer Andrew Morton provides a personal tour, describes what lay ahead for 2.7 and beyond, and explains how others can contribute to the Linux core.

By the time the 2.6.0 production kernel was released last December, the kernels in the 2.5.x development tree had been stable for more than a year. There was little drama associated with the release of the new code (compared to previous stable kernel introductions) as the Open Source Development Labs (OSDL), IBM, and others had been performing consistent, rigorous testing and the kernel team remain determined to keep the development kernel stable and usable at all times. In the end, going to 2.6.0 was mainly a re-labeling exercise.

In this article, I’ll discuss the major changes in the new production kernel, explain some subtle shifts in how kernel development works now [also see the sidebar "Linux Changes Linux Process" on page 40], detail what we hope to accomplish with 2.6, and, finally, recommend how individual developers and the growing number of corporate engineering groups that work on Linux can make contributions to the kernel.

Scaling Up and Down

A significant change in the 2.6 kernel is its ability to scale both up and down.

Scaling up has received most of the attention, but significant advances have also been made in the kernel’s ability to scale down to small systems. In particular, the work of the uClinux Microcontroller project (http://www.uclinux.org) was merged into the mainstream kernel. With that integration, 2.6 now supports embedded devices that lack a memory management unit, such as Hitachi’s H8/300, NEC’s v850, and Motorola’s m68k.

We reduced the kernel’s memory footprint, and work on that is continuing. We expect that people will see a lot more of Linux in the embedded and consumer electronics markets over the next couple of years. [For more information on embedded Linux systems, see "Embedded Linux" on page 32.]

Significant attention was also paid to the needs of desktop computer users, particularly peripheral hardware and multimedia. The 2.6 kernel plays much better with new hardware such as serial ATA drives and Universal Serial Bus 2.0 (USB 2.0) devices, including hot plug support. 2.6 adds support for Bluetooth and improvements for IrDA. It offers a new sound system, the Advanced Linux Sound Architecture, bringing studio-quality sound to Linux (without requiring a kernel patch).

As mentioned before, scaling up was also greatly enhanced in 2.6. The new kernel scales up to very large systems. Testing has been performed on systems with thousands of disks and hundreds of CPUs. Much has been written about this, but I will point out the highlights, as well as the work the kernel team must still complete before shifting to maintenance mode.

The 2.4 kernel’s disk I/O scheduler had some serious starvation and fairness problems under some workloads. These workloads are somewhat uncommon, involving situations where two or more programs are heavily accessing the same disk. The new anticipatory disk scheduler brought huge performance gains in this area. The disk I/O scheduler is the most performance-critical part of the kernel.

The anticipatory scheduler was a great contribution (see the sidebar “Building a New Scheduler”) and typifies the performance problems that were addressed in the 2.5 development cycle. Generally, when used for normal things, the 2.4 kernel performs nicely. But sometimes, when asked to do unusual things, the 2.4 kernel can perform very poorly. And unfortunately some people regularly ask their computers to do those unusual things. We knew about these problems and worked to fix them with well-architected solutions. So, the 2.4 and 2.6 kernels have similar performance for “usual” things, but 2.6 often performs much better when doing “unusual” things.

Building a New Scheduler

Inspired by a paper on an anticipatory scheduler by Peter Druschel and Sitaram Iyer (http://www.cs.rice.edu/~ssiyer/r/antsched), a young Australian developer named Nick Piggin came out of the woodwork to ask Jens Axboe [another seasoned kernel developer] and Andrew Morton questions about the existing I/O scheduler. Per Morton’s suggestion and with Morton’s encouragement, Piggin implemented the scheduler on Linux. Six months and 140 patches later (90 percent of the contributions from Piggin), the new scheduler was stabilized and merged into the mainline kernel.

We also spent considerable time on an improved threading model, adding support for the Native POSIX Thread Library (NPTL). NPTL delivers performance gains for heavily threaded applications, including Java virtual machines.

Another important advance in 2.6 was the new “O(1)” (pronounced “order one”) process scheduler, the part of the kernel that divides the processor’s time among running programs. The new scheduler increases scalability on multiprocessor systems without harming performance on single-CPU systems. The new CPU scheduler scales cleanly to hundreds of CPUs, thousands of tasks, and hundreds of thousands of context switches per second.

We added enhanced support for Non-Uniform Memory Access (NUMA), an architecture on which massive multiprocessor systems are built. NUMA systems address memory bus bottlenecks with multiple memory buses.

Some of the other major improvements include a pre-emptible kernel, support for hot plug and hot unplug of CPUs, support for access control lists through the extended file system attributes, support for the Journaling File System (JFS), support for the eXtended File System (XFS), support for symmetric multithreading, and much-improved multiprocessor scalability in the ext3 file system.

Steps to 2.7

Before Linus opens the 2.7 development tree, however, the kernel development team must finish up work on some items that weren’t completed in time for the 2.6.0 release. These include a NUMA memory API; the NUMA+ hyperthreading CPU scheduler; rewriting memory management; and improving the Ext3 block allocator.

Linus and I continue to work on 2.6 in much the same manner as with the 2.5 development tree. For 2.6, I actually run a development kernel. I work with the subsystem maintainers, keeping things separate and clean, and making sure all of the interested parties review and test the new code. Then we go through a stabilization period. Only after that period ends do I push the new code out to Linus to fold into the main kernel. Since 2.6.0 was released, each point release has taken three to four weeks.

Once the remaining development tasks have been completed, my job will become a lot more mundane: bug fixing, incorporating new device drivers, and keeping the various vendors trees roughly in-sync by incorporating their features as they mature.

A big part of my job will focus on maintenance, but I’ll also work with vendors to ensure that the base kernel has the features they feel they need, as well as encouraging developers who aren’t as familiar with how the Linux kernel works.

Undoubtedly, the 2.6.x stream will be the focus of development for at least several more years, since it will live on for quite some time after 2.8 comes out.

One of my major goals with 2.6 is to keep the mainstream kernel more closely synchronized with the efforts under way at different projects and at the distribution vendors. It’s an open secret that that some of the 2.4-based distros are shipping with quite differently patched kernels. Divergence between vendor kernels creates a perception that applications require a particular vendor’s kernel to work properly. Nobody likes this, and we will work to minimize divergence by promptly pulling new features into the base kernel.

For me, it’s a red flag if a vendor ships a kernel with any patches at all. Each patch needs to be examined to decide whether the patch genuinely addresses an inadequacy in the kernel or whether it’s something best left maintained outside the main, public tree.

Submitting Patches

At this point in time I am managing an average of 400 patches, most of which are targeted for Linus’s 2.6.x tree. These patches are flowing from my tree into Linus’s at about 130 patches per week.

Linus and many other kernel maintainers use the Bitkeeper source code management (SCM) package to manage their kernel branches. However, I’ve learned that a conventional SCM is unsuitable for managing a string of differences against someone else’s tree. Instead, I’ve developed a suite of patch management scripts that a number of other kernel developers now use.

These scripts are really quite awful, and a group of developers took the basic idea and turned it into a free software product called quilt, located at https://savannah.nongnu.org/projects/quilt.

The process of getting patches into the kernel is straightforward and is described in detail in an FAQ on the kernel.org site. Usually developers will get their changes into the kernel by emailing me or one of the subsystem maintainers. We prefer a single patch per email, placed in the body of the email, with a nice, descriptive subject. Each patch should encapsulate a single concept, and should, if possible, have no dependencies upon the patches that follow it.

The patch should include a comprehensive changelog at the top of the email, and should be copied to the appropriate mailing lists and subsystem maintainers. I generally prefer to delegate reviewing of the patch to the developer who specializes in the affected kernel component.

A patch needs to be well tested before I will forward it on to Linus for inclusion. Usually this testing occurs via the patch’s inclusion in my public -mm kernel tree, although I will often specifically ask other developers for test results.

Testing is very important. I very much like people to send test results, regressions, crashes, and other evidence that they’ve put the code through its paces. During the 2.5 development cycle, OSDL provided some very useful testing that helped us stabilize the kernel and get to 2.6 sooner.

Call for Participation

I’d like to encourage corporate developers to become more involved and to contribute more to Linux. There are some cultural and even legal problems, as well as some common pitfalls for corporations working with the kernel and the open source development process.

Developers should always work with their management and in-house counsel to be clear about IP issues and internal processes. Each company needs to individually address these issues.

Companies should try to avoid what I call the “SourceForge Syndrome.” A company will set up a big project and then beaver away at it independently for months. Suddenly a 50,000-line patch appears on a mailing list and no one understands what it does or why it does it. Such large patches usually have significant architectural problems and even duplication of other efforts. By this stage the originating development team is deeply invested in their current code and may even have run out of budget for rework, but the code may be unacceptable. It’s generally a disaster.

Companies must understand that there are significant advantages for them to merge their code into the mainstream kernel. This reduces their maintenance effort and costs, increases their tester and reviewer base, and encourages other developers to contribute additional feature work. Other people will magically fix your bugs for you.

In this scenario, the cost to corporations is that more work must be performed up front in the development cycle. Companies need to introduce code the right way. Submit at the early stage. Get the right people to review the code and buy into it. Rather than setting up an external SourceForge project, you should aim to get a small core of your feature into the base kernel and develop against that, introducing new features on a frequent basis.

For the individual developer, it can be daunting to display code to the legendary “thousands of eyeballs,” especially when some of the owners of those eyeballs can be a little rude. But don’t worry about that: it’s not personal. It’s all about the code. Companies may want to nominate a lead individual as their contact point with the rest of the kernel development team.

Corporate developers need to persist. If no one responds to your email then try again, perhaps with a wider audience. Do not assume that a lack of feedback implies a lack of interest. Don’t be afraid to disagree with comments that are made about the code or about the concepts that lie behind it. Attempt to rapidly reach agreement upon any rework and then resubmit the patches. You might have to explain the same thing to multiple people multiple times, so be prepared to create and to maintain a succinct description of what the code is trying to achieve and how it achieves it.

A developer new to the Linux kernel should also sign up for some of the lists at kernel.org. Please observe the email etiquette and avoid general corporate email practices that generally get you tagged as a newbie or worse, clueless. Use plain text in your email messages, hit ENTER every 70 columns or so, place your answer below the text to which you are replying, and edit away irrelevant sections of the email to which you are composing a reply. You’ll win bonus marks among kernel developers for using an email client that correctly implements the References and In-Reply-To headers.

If a company’s development group has designated an individual as the “kernel contact person” then it is appropriate that this person spend time following the external mailing lists.

Linus Changes Linux Process

As Linux Magazine went to press, OSDL announced that it was enhancing the Linux kernel development process to more accurately track contributions to the kernel and to ensure that developers receive credit for those contributions.

Under the enhanced kernel submission process, contributions to the Linux kernel may only be made by individuals who acknowledge their right to make the contribution under an appropriate open source license. The acknowledgement, called the Developer’s Certificate of Origin (DCO), tracks contributions and contributors. The DCO ensures that appropriate attribution is given to developers of original contributions and derivative works, as well to those contributors who receive submissions and pass them unchanged up the kernel tree. All contributors are called upon to “sign off” on a submission before it may be considered for inclusion in the kernel.

OSDL has committed to providing resources to ensure that contributions made to the kernel adhere to the DCO and the process improvements. The Lab will review the content of the contributions to confirm that submissions to the kernel have been signed off by contributors in accordance with the DCO.

Both Linux creator Linus Torvalds and Linux 2.6 lead Andrew Morton said they adopted the revised process after obtaining input and broad support from key kernel subsystem maintainers and others in the open source community.

The full text of the DCO can be found at http://www.osdl.org/newsroom/press_releases/2004/2004_05_24_dco.html.

A Cast of Thousands

Sometimes I’m asked if managing the development process around the Linux kernel is a skill set transferable to other big software projects. Does Linux have something to teach the software development world at large?

I don’t think so. Many large corporate software projects are green field things. Frequently they involve the development of complex new features that require a significant requirements analysis phase and formal development processes. Kernel work tends more toward small, single-person jobs. Large multi-person development projects are rare. Also, there’s little need for requirements analysis work in the kernel project because the requirements are generally obvious: we implement the POSIX API and we control industry-standard hardware.

That’s also why the kernel development team works well. Approximately 1,000 individuals contributed to the 2.5 and 2.6 kernels. For the Linux kernel the “20/80″ rule very much applies. About 20 people did 80 percent of the work. Or maybe it was “10/90.”

The kernel has become a lot more complex than it was in the 2.0 days, and the learning curve is longer and steeper. A committed developer who’s competent in C can begin to contribute usefully after as little as a few weeks of study. (For an example, see the sidebar “Building a New Scheduler.”) In general, it probably takes six to twelve months of full-time work to reach the level of a mainstream kernel contributor.

Linux Goes Mainstream with the 2.6 Kernel

The 2.6 kernel promises to profoundly impact the adoption of Linux. The features that Andrew Morton has described take Linux to the heart of the datacenter, extend its reach throughout the telecommunications industry, push it down into embedded systems, and help establish Linux as a mainstream alternative on business desktops.

The new 2.6 kernel is reaching mainstream users much faster than the previous production kernel, 2.4. Due to extensive testing at the Open Source Development Labs (ODSL) and other labs around the world, the 2.6 kernel shipped with far fewer bugs than the 2.4 kernel did. Adoption by distributions has been phenomenal. Several leading Linux distributions were shipping production release products with the 2.6 kernel within the first six months of its introduction.

Linux is much more scalable for large servers. It’s ready for high-load, enterprise infrastructure. If you’re an enterprise independent software vendor (ISV), you can anticipate more demand for your software than with the 2.4 kernel, helping to overcome the traditional “chicken and egg” problem of when to port to Linux. Linux will replace more of the workloads that have been traditionally handled by proprietary UNIX servers.

Linux used to be relegated to the “edge,” but is now clearly moving closer to the core of the datacenter. Today, enterprises are rolling out pilot projects that take advantage of the new scalability of the 2.6 kernel, with production systems soon to follow.

The adoption of 2.6 is also being hastened by hardware manufacturers, which are widely and greatly supportive of Linux development. Hardware vendors and the Linux development community are working much more closely than ever before. Prior to the release of 2.6, the development community was able to isolate and resolve potential hardware compatibility problems before release of the kernel. Much of that work occurred and continues at OSDL. Every major hardware vendor has a Linux strategy and invests significant engineering and testing resources to ensure that their hardware systems work with Linux.

OSDL is focused on accelerating the adoption of Linux in the enterprise. We bring vendors, enterprise customers, and the Linux development community together to address common challenges and advance the use of Linux.

We think our contributions have helped establish an important center of gravity for the Linux industry. We strongly believe that Linux has arrived. Most of the work now hinges on building comfort and confidence with customers and vendors.

– Stuart Cohen

Stuart Cohen is the Chief Executive Officer of Open Source Development Labs.

Of course, new developers are encouraged and are always welcome. We always need help with drivers, bug fixing, tuning, and testing. A new developer may choose to go through the kernel Bugzilla database and identify any problems that appear to be unresolved. See if you can reproduce the problem, work it with the originator, and then develop a fix. Similarly, the various development mailing lists are a good source of current bug reports.

And based on personal experience (see the sidebar “Colonel of the Kernel”), I can say that fixing bugs in unfamiliar code is a great way to become familiar with the kernel.

Colonel of the Kernel

I started as a kernel developer four years ago, beginning with a 2,000-line patch to make my $9 network card work. Much to my surprise, Linus accepted it.

After that, I spent two years working partly on network drivers, but mainly on bug fixing. It didn’t matter where in the kernel the bug was, I’d try to fix it. That was a great way to learn how the kernel worked.

I then moved into Ext3 filesytem development, and then memory management and I/O work.

Linus asked me to take on the job of 2.6 kernel maintainer about a year ago.

– Andrew Morton

Andrew Morton has twenty years of development and engineering management experience, and is the maintainer of the Linux 2.6 kernel. Sponsored by OSDL, Andrew works full-time on Linux kernel development. Andrew has been principal engineer at Digeo and a product development manager at Nortel. He holds an honors degree in Electrical Engineering from the University of New South Wales in Australia. You can reach Andrew at akpm@zip.com.au. You can read an extensive interview with Andrew in the September 2003 issue of Linux Magazine, available online at http://www.linux-mag.com/2003-09/morton_01.html.

Comments are closed.