LWN Weekly Edition
Front pageSecurity
Kernel development
Distributions
Development
Linux in the news
Announcements
->One big page
This page
Previous weekFollowing week
Recent Features
| |||||||||||||
Kernel developmentBrief items Kernel release statusThe current stable 2.6 kernel is 2.6.16.1, released on March 27. 2.6.15.7 was released at the same time. Both patches contain a fair number of important fixes, some of which are security-related.There has been no 2.6 development prepatch released over the last week. Patches are flowing into the mainline git repository at a high rate, however; see below for a list. The current -mm tree is 2.6.16-mm2. Recent changes to -mm include the ability to call poll() on sysfs files (LWN coverage), support for 64-bit I/O and memory resources, priority-inheriting futex support, and a new set of central time management patches.
Kernel development news What's going into 2.6.17, part 2The flood of patches heading into the mainline continues at full rate - though the merge window should be closing soon. The following is the highlights from code merged since last week's summary, starting with the user-visible changes:
Internal kernel API changes merged include:
If the usual pattern holds, the merging of new features will stop sometime around the end of the month, with 2.6.17-rc1 being released shortly thereafter.
A framework for page replacement policies"Holy cow."That was Andrew Morton's reaction to a 34-part patch, posted by Peter Zijlstra, which creates an abstract API for page replacement policies. The page replacement code is at the core of the virtual memory system; it is, essentially, a set of heuristics which must decide which pages should be evicted from main memory and made available for other uses. Page replacement is a bit of a black art; it is easy to see when a system is managing memory poorly, but path to improvements is often far from clear. Memory management in Linux was a sore point for many years, but it seems to work well for most loads now. Given that all this tricky code has finally been beaten into reasonably good shape, why would anybody want to mess with it now? The answer is that there is quite a bit of research work going into alternative page replacement mechanisms, and Linux might just be able to benefit from some of that work. After all, few people would say that Linux virtual memory works so well that there is no room for improvement. This massive patch set creates an API for page replacement algorithms, allowing them to be changed at will. Or, at least, changed at reboot; there is currently no provision for loading replacement algorithms as modules or swapping them out on the fly. But, by selecting a page replacement scheme at kernel configuration time, system administrators can choose one which best suits their workload. Virtual memory hackers and others can play with different algorithms to see how they work out. And there is no need to pick one in particular as the page replacement algorithm for the Linux kernel. To work with this API, a page replacement algorithm must define a set of specific functions. Thus, for example, there is a pair of initialization functions:
void page_replace_init(void);
void page_replace_init_zone(struct zone *zone);
These functions, called at boot time, prepare the page replacement code to work with the system it finds itself running on. When the core kernel knows something about the use of specific pages, it can tell the replacement algorithm with these calls:
void page_replace_hint_active(struct page *page);
void page_replace_hint_use_once(struct page *page);
The first is called when the kernel notes that the page is in active use, while the second indicates that the page is unlikely to be used again in the near future. There are various other functions for helping with the housekeeping, but the core of the API is this function here:
void page_replace_candidates(struct zone *zone, int count,
struct list_head *list);
This function must select up to count pages from the given zone as candidates for eviction. This is where the page replacement code will gaze into its crystal ball to figure out which pages will not be used again anytime soon; those are the ones which will be singled out and passed back to the core kernel. Quite a few other functions exist. They deal with issues like page migration, tracking of non-resident pages, printing out information from the page replacement code, and more. See the documentation file for a full list and brief explanation of those other functions. The patch set also contains four different page replacement mechanisms. One is the modified least-recently-used (LRU) code found in current kernels, reworked to use the new API. Another is the CLOCK-PRO algorithm, covered here last August. There is an implementation of the CART technique, discussed in this paper [PDF]. Then there is a simple random replacement scheme, seemingly just for the fun of it. Actually, the random replacement patch is, due to its simplicity, a good place to start for somebody interested in seeing what a modularized page replacement algorithm looks like. This patch looks somewhat similar to the pluggable CPU schedulers patch, which allows the scheduling algorithm to be changed. That patch continues to be maintained, but, since its initial posting in 2004, it has never been seriously considered for inclusion into the mainline kernel. There is a strong preference toward figuring out what's wrong - if anything - with the current code and fixing it, rather than creating a mechanism for playing with entirely different implementations. Thus, Andrew Morton followed his initial response with:
Rather than replacing the whole lot four times I'd really prefer to
see precise descriptions of these problems, see if we can improve
the situation incrementally rather than wholesale slash-n-burn...
Linus has a similar opinion, and, additionally, is not convinced that page replacement is really an issue needing a great deal of attention. "It smells like university research to me." The proponents of this patch respond that there are, indeed, situations where the current code falls apart. Given that, the next logical step would seem to be gathering information on the cases where Linux memory management fails. Then the developers can start to think about what needs to be done to address those failures. Even if the page replacement framework patches are never merged, it looks like they may help to drive forward the next phase of work in Linux memory management algorithms. That should be a good thing regardless.
The new pselect() system callApplications like network servers that need to monitor multiple file descriptors using select(), poll(), or (on Linux) epoll_wait() sometimes face a problem: how to wait until either one of the file descriptors becomes ready, or a signal (say, SIGINT) is delivered. These system calls, as it turns out, do not interact entirely well with signals. A seemingly obvious solution would be to write an empty handler for the signal, so that the signal delivery interrupts the select() call:
static void handler(int sig) { /* do nothing */ }
int main(int argc, char *argv[])
{
fd_set readfds;
struct sigaction sa;
int nfds, ready;
sa.sa_handler = handler; /* Establish signal handler */
sigemptyset(&sa.sa_mask);
sa.sa_flags = 0;
sigaction(SIGINT, &sa, NULL);
/* ... */
ready = select(nfds, &readfds, NULL, NULL, NULL);
/* ... */
After select() returns we can determine what happened by looking at the function result and errno. If errno comes back as EINTR, we know that the select() call was interrupted by a signal, and can act accordingly. But this solution suffers from a race condition: if the SIGINT signal is delivered after the call to sigaction(), but before the call to select(), it will fail to interrupt that select() call and will thus be lost. We can try playing various games like setting a global flag within the signal handler and monitoring that flag in the main program, and using sigprocmask() to block the signal until just before the select() call. However, none of these techniques can entirely eliminate the race condition: there is always some interval, no matter how brief, where the signal could be handled before the select() call is started. The traditional solution to this problem is the so-called self-pipe trick, often credited to D J Bernstein. Using this technique, a program establishes a signal handler that writes a byte to a specially created pipe whose read end is also monitored by the select(). The self-pipe trick cleverly solves the problem of safely waiting either for a file descriptor to become ready or a signal to be delivered. However, it requires a relatively large amount of code to implement a requirement that is essentially simple. (For example, a robust solution requires marking both the read and write ends of the pipe non-blocking.) For this reason, the POSIX.1g committee devised an enhanced version of select(), called pselect(). The major difference between select() and pselect() is that the latter call has a signal mask (sigset_t) as an additional argument:
int pselect(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
const struct timespec *timeout, const sigset_t *sigmask);
The
sigmask
argument specifies a set of signals that should be blocked during the
pselect()
call; it overrides the current signal mask for the duration of that call.
So, when we make the following call:
ready = pselect(nfds, &readfds, &writefds, &exceptfds,
timeout, &sigmask);
the kernel performs a sequence of steps that
is equivalent to atomically performing the following system calls:
sigset_t sigsaved;
sigprocmask(SIG_SETMASK, &sigmask, &sigsaved);
ready = select(nfds, &readfds, &writefds, &exceptfds, timeout);
sigprocmask(SIG_SETMASK, &sigsaved, NULL);
For some time now, glibc has provided a library implementation of pselect() that actually uses the above sequence of system calls. The problem is that this implementation remains vulnerable to the very race condition that pselect() was designed to avoid, because the separate system calls are not executed as an atomic unit. Using pselect(), we can safely wait for either a signal to be delivered or a file descriptor to become ready, by replacing the first part of our example program with the following code:
sigset_t emptyset, blockset;
sigemptyset(&blockset); /* Block SIGINT */
sigaddset(&blockset, SIGINT);
sigprocmask(SIG_BLOCK, &blockset, NULL);
sa.sa_handler = handler; /* Establish signal handler */
sa.sa_flags = 0;
sigemptyset(&sa.sa_mask);
sigaction(SIGINT, &sa, NULL);
/* Initialize nfds and readfds, and perhaps do other work here */
/* Unblock signal, then wait for signal or ready file descriptor */
sigemptyset(&emptyset);
ready = pselect(nfds, &readfds, NULL, NULL, NULL, &emptyset);
...
This code works because the SIGINT signal is only unblocked once control has passed to the kernel. As a result, there is no point where the signal can be delivered before pselect() executes. If the signal is generated while pselect() is blocked, then, as with select(), the system call is interrupted, and the signal is delivered before the system call returns. Although pselect() was conceived several years ago, and was already publicized in 1998 by W. Richard Stevens in his Unix Network Programming, vol. 1, 2nd ed., actual implementations have been slow to appear. Their eventual appearance in recent releases of various Unix implementations has been driven in part by the fact that the 2001 revision of the POSIX.1 standard requires a conforming system to support pselect(). With the 2.6.16 kernel release, and the required wrapper function that appears in the recently released glibc 2.4, pselect() also becomes available on Linux. Linux 2.6.16 also includes a new (but nonstandard) ppoll() system call, which adds a signal mask argument to the traditional poll() interface:
int ppoll(struct pollfd *fds, nfds_t nfds, const struct timespec *timeout,
const sigset_t *sigmask);
This system call adds the same functionality to poll() that pselect() adds to select(). Not to be left in the cold, the epoll maintainer has patches in the pipeline to add similar functionality in the form of a new epoll_pwait() system call. There are a few other, minor differences between pselect() and ppoll() and their traditional counterparts. For example the type of the timeout is:
struct timespec {
long tv_sec; /* Seconds */
long tv_nsec; /* Nanoseconds */
};
This allows the timeout interval to be specified with greater precision than
is available with the older system calls.
The glibc wrappers for pselect() and ppoll() also hide a couple of details of the underlying system calls. First, the system calls actually expect the signal mask argument to be described by two arguments, one of which is a pointer to a sigset_t structure, while the other is an integer that indicates the size of that structure in bytes. This allows for the possibility of a larger sigset_t type in the future. The underlying system calls also modify their timeout argument so that on an early return (because a file descriptor became ready, or a signal was delivered), the caller knows how much of the timeout remained. However, the respective wrapper functions hide this detail by making a local copy of the timeout argument and passing that copy to the underlying system calls. (The Linux select() system call also modifies its timeout argument, and this behavior is visible to applications. However, many other select() implementations don't modify this argument. POSIX.1 permits either behavior in a select() implementation.) Further details of pselect() and ppoll() can be found in the latest versions of the select(2) and poll(2) man pages, which can be found here.
Patches and updates Kernel trees
Core kernel code
Development tools
Device drivers
Documentation
Filesystems and block I/O
Memory management
Networking
Architecture-specific
Virtualization and containers
Miscellaneous
Page editor: Jonathan Corbet |
|||||||||||||