LWN Weekly Edition
Front pageSecurity
Kernel development
Distributions
Development
Announcements
->One big page
This page
Previous weekFollowing week
| |||||||||||||
Kernel developmentBrief items Kernel release statusThe 3.0 kernel is out, released on July 21. Linus said:
As already mentioned several times, there are no special
landmark features or incompatibilities related to the version number
change, it's simply a way to drop an inconvenient numbering system in honor
of twenty years of Linux. In fact, the 3.0 merge window was calmer than
most, and apart from some excitement from RCU I'd have called it really
smooth.
Beyond the numbering scheme change, this kernel includes POSIX alarm timer support, a just-in-time compiler for BPF packet filters, a new sendmmsg() system call, ICMP sockets, the merging of the Xen backend driver (completing the long process of getting Xen Dom0 support into the kernel), namespace file descriptors, and more. See the KernelNewbies 3.0 page for lots of details. Stable updates: no stable updates have been released in the last week. The 2.6.35.14 update is in the review process as of this writing.
Quotes of the week
I am quite at ease not participating in netfilter/iptables anymore
while the discussion about IPv6 NAT becomes an issue again: I
always indicated "over my dead body", and now that I am no longer
in charge, nobody will have to kill me ;)
-- Harald Welte
Working on an update kernel for Fedora 15, rebasing from 2.6.38 to
3.0. As we know a bunch of userspace packages need updating to
deal with the 2.6 -> 3.x transition, we made a decision to ship
3.0, but call it 2.6.40 rather than ship a ton of updates, and risk
breaking other code that we don't ship.
-- OMG
Dave Jones FORKS LINUX!
I look forward to the "OMG, RED HAT FORKS LINUX" posts on slashdot.
Thanks to git send-email I know exactly what networking patches
every Linux vendor is backporting into their kernel.
-- David
Miller
Garrett: Further adventures in EFI bootingMatthew Garrett continues his investigation into the subtleties of booting Linux with EFI. "GPT, or the GUID Partition Table, is the EFI era's replacement for MBR partitions. It has two main advantages over MBR - firstly it can cover partitions larger than 2TB without having to increase sector size, and secondly it doesn't have the primary/logical partition horror that still makes MBR more difficult than it has any right to be. The format is pretty simple - you have a header block 1 logical block into the media (so 512 bytes on a typical USB stick), and then a pointer to a list of partitions. There's then a secondary table one block from the end of the disk, which points at another list of partitions. Both blocks have multiple CRCs that guarantee that neither the header nor the partition list have been corrupted. It turns out to be a relatively straightforward modification of isohybrid to get it to look for a secondary EFI image and construct a GPT entry pointing at it. This works surprisingly well, and media prepared this way will boot EFI machines if burned to a CD or written to a USB stick."
Kernel development news 3.1 merge window part 1As of this writing, almost 5,400 non-merge changesets have been pulled into the mainline repository for the 3.1 development cycle. It's a wide-ranging set of changes, but many of them are cleanups - almost 600 of those changes have the word "remove" in the title, and the total growth of the kernel is less than 5,000 lines. A number of trees remain unpulled, though, so there is plenty of scope for the kernel to grow yet.User-visible changes merged for 3.1 include:
Changes visible to kernel developers include:
It is not clear when this merge window will close; Linus is about to go on vacation, and, as he has noted, connectivity tends to be poor when one is under water in scuba gear. If he is unable to get everything merged while he is traveling, the merge window may be extended a little past the normal two weeks. Or he could decide he has pulled enough and close things early. Stay tuned for an update next week.
Per-CPU variables and the realtime treeOne of the problems with relying on out-of-tree kernel code is that one can never be sure when that code might be updated for newer kernels. Keeping up with the kernel can be painful even for maintainers of small patches; it's much more so for those who maintain a large, invasive patch series. It is probably safe to say that, if the realtime preemption developers do not keep their patches current, there are very few other developers who are in a position to take on that work. So it was certainly discouraging for some realtime users to watch multiple kernel releases go by while the realtime patch series remained stuck at 2.6.33.The good news is that the roadblock has been overcome and there is now a new realtime tree for the 3.0 kernel. Even better news is that the realtime developers may have come up with a solution for one of the most vexing problems keeping the realtime code out of the mainline. The only potential down side is that this approach relies on an interesting assumption about how per-CPU data is used; this assumption will have to be verified with a lot of testing and, likely, a number of fixes throughout the kernel. Symmetric multiprocessing systems are nice in that they offer equal access to memory from all CPUs. But taking advantage of the feature is a guaranteed way to create a slow system. Shared data requires mutual exclusion to avoid concurrent access; that means locking and the associated bottlenecks. Even in the absence of lock contention, simply moving cache lines between CPUs can wreck performance. The key to performance on SMP systems is minimizing the sharing of data, so it is not surprising that a great deal of scalability work in the kernel depends on the use of per-CPU data. A per-CPU variable in the Linux kernel is actually an array with one instance of the variable for each processor. Each processor works with its own copy of the variable; this can be done with no locking, and with no worries about cache line bouncing. For example, some slab allocators maintain per-CPU lists of free objects and/or pages; these allow quick allocation and deallocation without the need for locking to exclude any other CPUs. Without these per-CPU lists, memory allocation would scale poorly as the number of processors grows. Safe access to per-CPU data requires a couple of constraints, though: the thread working with the data cannot be preempted and it cannot be migrated while it manipulates per-CPU variables. If the thread is preempted, the thread that replaces it could try to work with the same variable; migration to another CPU could cause confusion for fairly obvious reasons. To avoid these hazards, access to per-CPU variables is normally bracketed with calls to get_cpu_var() and put_cpu_var(); the get_cpu_var() call, along with providing the address for the processor's version of the variable, disables preemption. So code which obtains a reference to a per-CPU data will not be scheduled out of the CPU until it releases that reference. Needless to say, any such code must be atomic. The conflict with realtime operation should be obvious: in the realtime world, anything that disables preemption is a possible source of unwanted latency. Realtime developers want the highest-priority process to run at all times; they have little patience for waiting while a low-priority thread gets around to releasing a per-CPU variable reference. In the past, this problem has been worked around by protecting per-CPU variables with spinlocks. These locks keep the code preemptable, but they wreck the scalability that per-CPU variables were created to provide and complicate the code. It has been clear for some time that a different solution would need to be found. With the 3.0-rc7-rt0 announcement, Thomas Gleixner noted that "the number of sites which need to be patched is way too large and the resulting mess in the code is neither acceptable nor maintainable." So he and Peter Zijlstra sat down to come up with a better solution for per-CPU data. The solution they came up with is surprisingly simple: whenever a process acquires a spinlock or obtains a CPU reference with get_cpu(), the scheduler will refrain from migrating that process to any other CPU. That process remains preemptable - code holding spinlocks can be preempted in the realtime world - but it will not be moved to another processor. Disabling migration avoids one clear source of trouble: a process which is migrated in the middle of manipulating a per-CPU variable will end up working with the wrong CPU's instance of that variable. But what happens if a process is preempted by another process that needs to access the same variable? If preemption is no longer disabled, this unfortunate event seems like a distinct possibility. After puzzling over this problem for a bit, the path to enlightenment became clear: just ask Thomas what they are thinking with this change. What they are thinking, it turns out, is that any access to per-CPU data needs to be protected by some sort of lock. If need be, the lock itself can be per-CPU, so the locking need not reintroduce the cache line bouncing that the per-CPU variable is intended to prevent. In many cases, that locking is already there for other purposes. The realtime developers are making the bet that this locking is already there in almost every place where per-CPU data is manipulated, and that the exceptions are mostly for data like statistics used for debugging where an occasional error is not really a problem. When it comes to locking, though, a gut feeling that things are right is just not good enough; locking problems have a way of lurking undetected for long periods of time until some real damage can be done. Fortunately, this is a place where computers can help; the realtime tree will probably soon acquire an extension to the locking validator that checks for consistent locking around per-CPU data accesses. Lockdep is very good at finding subtle locking problems which are difficult or impossible to expose with ordinary testing. So, once this extension has been implemented and the resulting problem reports investigated and resolved, the assumption that all per-CPU accesses are protected by locking will be supportable. That process will likely take some time and, probably, a number of fixes to the mainline kernel. For example, there may well be bugs now where per-CPU variables are manipulated in interrupt handlers but non-interrupt code does not disable interrupts; the resulting race will be hard to hit, but possibly devastating when it happens. So, as has happened before, the realtime effort is likely to result in fixes which improve things for non-realtime users as well. Some churn will be involved, but, once it is done, there should be a couple of significant benefits: the realtime kernel will be more scalable on multiprocessor systems, and the realtime patches should be that much closer to being ready for merging into the mainline.
3.0 and RCU: what went wrongMy goal has always been for my code to go in without so much as a ripple. Although I don't always meet that goal, I can't recall any recent failure quite as spectacular as RCU in v3.0. My v3.0 code didn't just cause a few ripples, it bellyflopped. It is therefore worthwhile to review what happened and why it happened in order to avoid future bellyflops and trainwrecks. This post-mortem will cover the following topics:
Overview of preemptible RCU read-side codeUnderstanding the trainwreck requires reviewing a small amount of
1 void __rcu_read_lock(void)
2 {
3 current->rcu_read_lock_nesting++;
4 barrier();
5 }
This is quite straightforward: line 3 increments the per-task
The
1 void __rcu_read_unlock(void)
2 {
3 struct task_struct *t = current;
4
5 barrier();
6 --t->rcu_read_lock_nesting;
7 barrier();
8 if (t->rcu_read_lock_nesting == 0 &&
9 unlikely(ACCESS_ONCE(t->rcu_read_unlock_special)))
10 rcu_read_unlock_special(t);
11 }
Line 5 prevents the compiler from bleeding code from the
RCU read-side critical section out past the However, if the value of the nesting counter is now zero,
we now need to check to see if anything unusual happened
during the just-ended RCU read-side critical section,
which is the job of lines 8 and 9.
Line 7 prevents the compiler from moving this check to precede
the decrement on line 6 because otherwise something unusual might
happen just after the check but before the decrement, which would
in turn mean that
In either case, the per-task
1 static void rcu_read_unlock_special(struct task_struct *t)
2 {
3 int empty;
4 int empty_exp;
5 unsigned long flags;
6 struct rcu_node *rnp;
7 int special;
8
9 if (in_nmi())
10 return;
11 local_irq_save(flags);
12 special = t->rcu_read_unlock_special;
13 if (special & RCU_READ_UNLOCK_NEED_QS) {
14 rcu_preempt_qs(smp_processor_id());
15 }
16 if (in_irq()) {
17 local_irq_restore(flags);
18 return;
19 }
20 if (special & RCU_READ_UNLOCK_BLOCKED) {
21 t->rcu_read_unlock_special &= ~RCU_READ_UNLOCK_BLOCKED;
22
23 /* Clean up after blocking. */
24
25 }
26 }
Lines 9 and 10 take an early exit if we are executing in
non-maskable interrupt (NMI) context.
The reason for this early exit is that NMIs cannot be interrupted
or preempted, so there should be no Lines 16 through 18 take an early exit if we are executing in a hardware interrupt handler. This is appropriate given that hardware interrupt handlers cannot block, so it is not possible to preempt or to block within an RCU read-side critical section running within a hardware interrupt handler. (Of course, threaded interrupt handlers are another story altogether.) Finally, line 20 checks to see if we blocked or were
preempted within the
just-ended RCU read-side critical section, clearing the corresponding
bit and cleaning up after blockage or preemption if so.
The exact details of the cleanup are not important (and are therefore
omitted from the code fragment above), although curious
readers are referred to Because the scheduler disables interrupts when acquiring the
runqueue and the priority-inheritance locks, an RCU read-side
critical section that lies entirely within one of these locks'
critical sections cannot be interrupted, preempted, or blocked.
Therefore, such an RCU read-side critical section should not
enter Quick Quiz 1:
But what about RCU read-side critical sections that begin
before a runqueue lock is acquired and end within that lock's
critical section?
Answer
As we will see later, a number of self-deadlock scenarios can be
avoided via the
Steaming towards the trainwreckBefore we leave the station, please keep in mind thatin_irq() can return inaccurate results because
it consults the preempt_count() bitmask, which is updated
in software.
At the start of the interrupt, there is therefore a period of
time before preempt_count() is updated to record the
start of the interrupt, during which time the interrupt handler
has started executing, but in_irq() returns false.
Similarly, at the end of the interrupt, there is a period of
time after preempt_count() is updated to record
the end of the interrupt, during which time the interrupt
handler has not completed executing, but again
in_irq() returns false.
This last is most emphatically the case when the end-of-interrupt
processing kicks off softirq handling.
With that background, the sequence of commits leading to the trainwreck is as follows:
Although this appears to open the door to an obvious deadlock scenario where the RCU read-side critical section under the runqueue lock is the last one blocking a preemptible-RCU expedited grace period, this cannot happen as long as the runqueue lock is held across the entire duration of the RCU read-side critical section. Continuing down the tracks toward the trainwreck:
FixesThe fixes applied to the RCU trainwreck are as follows:
Current statusThe Linux 3.0 version of RCU finally seems stable, but the following potential vulnerabilities remain:
Preventing future bellyflops and trainwrecksPrevention is better than cure, so what preventative measures should be taken? The most important preventative measure is to do a full review of the RCU code, documenting it as I go. In the past, I documented new RCU functionality as a matter of course, before that functionality was accepted into the kernel. However, over the past few years, I have gotten out of that habit. Although some of the bugs would probably have escaped me, I would likely have spotted a significant fraction. In addition, the documentation might have helped others better understand RCU, which in turn might have helped some of them to spot the bugs. Although no one has yet reported similar bugs in
Another important preventative measure is to
question long-held assumptions.
My unquestioning faith in Dealing with the trainwreck also exposed some shortcomings in my test setup, which emphasizes thoroughness over fast turnaround. Although there is no substitute for a heavy round of testing on a number of different configurations, it would be good to be able to validate debug patches and experimental fixes much more quickly. I have therefore started setting up an RCU testing environment using KVM. This testing environment also has the great advantage of working even when I don't have Internet access. Additionally, use of KVM looks like it will shorten the edit-compile-debug cycle, which is quite important when chasing bugs that I actually can reproduce. Finally, I need to update my test configurations. Some of the bugs reproduce more quickly when threaded interrupt handlers are enabled, so I need to add these to my test regime. Another bug was specific to 32-bit kernels, which I currently don't test, but which KVM makes it easy to test. In fact, on my current laptop, 32-bit kernels are all that KVM is capable of testing. Hopefully these changes will avoid future late-in-cycle RCU trainwrecks. AcknowledgmentsI am grateful to Steven Rostedt, Peter Zijlstra, Thomas Gleixner, Ingo Molnar, Ben Greear, Julie Sullivan, and Ed Tomlinson for finding bugs, creating patches, and lots of testing. I owe thanks to Jim Wasko for his support of this effort. Answers to Quick QuizzesQuick Quiz 1: But what about RCU read-side critical sections that begin before a runqueue lock is acquired and end within that lock's critical section? Answer: That would be very bad. The scheduler is therefore forbidden from doing this. Quick Quiz 2:
Suppose that an RCU read-side critical section is enclosed within
a runqueue-lock critical section.
Why couldn't that RCU read-side critical section
be the last RCU read-side critical section blocking a
Answer:
No, it cannot.
To see why, note that
the Of course, the last link in the above chain of logic was broken by a later bug, but read on... Quick Quiz 3: Why can't we avoid this whole mess by treating interrupt-disabled segments of code as if they were RCU read-side critical sections? Answer: For two reasons:
Quick Quiz 4:
Exactly what vulnerability did commit Answer: Suppose that an RCU read-side critical section is the last one blocking
an expedited grace period, and that its Quick Quiz 5: How could you remove the restriction on possibly-preempted RCU read-side critical sections ending with runqueue or priority-inheritance locks held? Answer: Here are some possibilities:
Patches and updates Kernel trees
Core kernel code
Development tools
Device drivers
Filesystems and block I/O
Memory management
Networking
Architecture-specific
Virtualization and containers
Miscellaneous
Page editor: Jonathan Corbet |
|||||||||||||