See also: last week's Kernel page.

Kernel development

There is no 2.4.0-test12 prepatch available as of this writing. Alan Cox has come out with 2.4.0-test11-ac1 which contains a whole set of fixes that, for one reason or another, have not yet made it into the official Linus tree.

The current stable kernel release is still 2.2.17. The 2.2.18 prepatch is up to 2.2.18pre22. Some outstanding issues remain, so the 2.2.18 prepatch series is not done yet.

Riding the elevator. Discussion of the Linux elevator algorithm resumed this week with this posting complaining about occasional request starvation. That seems like as good a cue as any to look at how the 2.4.0 elevator works, so...

The job of the elevator is to sort I/O requests to disk drives for maximum performance. These algorithms have traditionally worked by keeping the disk head moving in the same direction for as long as possible, in a way similar to the way normal building elevators work. Sorting requests in this way, it is hoped, minimizes head movement (which is expensive) and insures that every request will be satisfied within a reasonable time period.

The Linux elevator does not currently work quite this way - and it occasionally produces results that are similar to those of the elevators in Les Suites at the Ottawa Linux Symposium. Whether you are a pending disk I/O request or an OLS attendee heading to dinner, starvation is a real possibility.

The problem on the Linux side is twofold. The first is that the system currently does not use a pure elevator; it will put requests with a low sector number at the top of the queue regardless of the current head position. Doing things this way was a deliberate design decision. The second problem is one of simple tuning of the code which is intended to prevent starvation.

Every request in the queue contains a sequence number; every time that request is passed over (another request is put ahead of it) that sequence number is reduced by one. When the sequence number reaches zero, the request has waited too long and will have no other requests placed in front of it. That should be sufficient to prevent request starvation, except that the default sequence numbers in 2.4.0-test11 are 1,000,000 for read requests, and 2,000,000 for writes. By the time an I/O request is passed over a million times, it will have been waiting for a very long time.

Help is available in the form of the elvtune utility, written by Andrea Arcangeli. elvtune was added to the util-linux package in version 2.10h. For now, the only thing you can do with elvtune is query the read and write latencies (default sequence numbers) and set them; Andrea recommends values of 500 and 1000, respectively. The longer-term plan is clearly to make it possible to plug in different elevator algorithms entirely, but that has not been implemented at this point.

For most system loads out there, playing with the elevator parameters will not change things much. The system must be generating enough I/O requests to create a reasonably full request queue, and those requests must be spread out over the disk. Big, busy servers may well benefit from elevator tuning; the typical desktop user will be hard put to see a difference.

LWN did some highly scientific tests to try to determine the effects of elevator tuning. They were: (1) build the kernel with make -j 10, (2) copy a 1GB file, and (3) compare the 1GB file and its copy. The results were as follows:

Test	Read/Write latency	Clock time
Kernel compile	1M/2M	3:58
	500/1000	3:54
	0/0	3:48
Copy	1M/2M	7:17
	500/1000	7:15
	0/0	7:37
Compare	1M/2M	10:00
	500/1000	10:01
	0/0	8:16

The results, clearly, are mostly in the noise, with one interesting exception. With the latencies set to zero (essentially disabling the elevator) the compare operation went much faster.

(Those wanting to install elvtune will likely have to build it by source, since a number of distributions have a version of util-linux which is too old to have it. The source is available from kernel.org. Beware, though, that completely reinstalling util-linux has a high probability of breaking your system if you are not careful; it's probably better to build and install elvtune only).

O'Reilly launches new Linux kernel book. O'Reilly and Associates has announced the availability of Understanding The Linux Kernel, by Daniel P. Bovet and Marco Cesati.

A look at CML2. Eric Raymond's CML2 language is intended, by Eric at least, to replace the current kernel configuration and build system in the 2.5 development series. The busy folks down at LWN Labs finally got it together to pull down cml2-0.8.3 from the CML2 site and give it a try.

Eric has publicly expressed a desire to see more people playing with the CML2 system. A this stage, however, it isn't really set up for casual experimentation. The CML2 tarball unpacks into a directory full of Python code and a basic README file. People accustomed to kernel add-ons might expect a patch that can be applied to hook CML2 into an existing kernel tree, but no such thing exists. For now, CML2 has to be run separately, with the resulting configuration file being copied into a kernel tree for building.

The process starts with a 2800 line kernel-rules.cml file describing all of the various kernel configuration options and how they relate to each other. It's fairly dense stuff, if you dig into it. A brief example:

    menu eth_3com_drivers # 3Com Ethernet cards
        EL1? EL2? ELPLUS?
        EL16? EL3? ISA3C515?
        ELMC? ELMC_II? VORTEX?
        APOLLO_ELPLUS?

The first step is to compile this file into a binary format for the other tools. This process took about 30 seconds on a Pentium 450 system - long enough that some people will certainly complain. Then you can run the cmlconfigure program, which will actually take you through the options and build a kernel configuration. This program supports the customary three modes of configuration - simple TTY mode, curses menu mode, and a graphical, window-oriented mode. It does not appear to have an equivalent of the important "make oldconfig" mode, however.

cmlconfigure needs some work. It has 15 options but no documentation of what they do (update: there is a cml2.sgml file with documentation that your inept editor missed the first time through). It complains if you don't specify a "macro file," but it's unclear what such a file would do. The graphical mode continually resizes its window, and requires a lot of "back" navigation. The defaults on many of the options make little sense. And so on - all stuff that can be worked out without too much trouble.

It produces a perfectly fine kernel configuration file at the end.

CML2 has most of what it needs to become the new kernel configuration scheme once the 2.5 series starts. The main thing remaining at this point is a Makefile patch that will enable prospective users to simply plug it in and type make config. And a bit of user interface work. Once it's easy to play with, people will see that it simply works and the only remaining issue will be whether certain kernel hackers will be able to get over having a Python-based tool in the kernel build process.

Other patches and updates released this week include:

• Adam Richter has released isapnpmodules, a program which will figure out which modules correspond to ISA PNP devices installed on the system.

• Jeff Garzik released a guide to submitting kernel patches, otherwise known as "The Unofficial Linus HOWTO."

• Jeff Dike has updated user-mode Linux to 2.4.0-test11.

• A new DC10plus video capture card driver was released by Serguei Miridonov.

• Mikael Pettersson has announced version 1.6 of his x86 performance monitoring counters driver.

• ulogd 0.9, which implements advanced logging in netfilter, was released by Harald Welte.

Section Editor: Jonathan Corbet

For other kernel news, see: Kernel traffic Kernel Newsflash Kernel Trap 2.5 Status

Other resources: L-K mailing list FAQ Linux-MM Linux Scalability Effort Kernel Newbies Linux Device Drivers

Next: Distributions