Kernel development

Kernel release status

The current development kernel is 4.11-rc1, released on March 5. Linus said: "This looks like a fairly regular release. It's on the smallish side, but mainly just compared to 4.9 and 4.10 - so it's not really _unusually_ small (in recent kernels, 4.1, 4.3, 4.5, 4.7 and now 4.11 all had about the same number of commits in the merge window)." There were 10,960 non-merge commits pulled in the end, so it's definitely not unusually small.

Stable updates: none have been released in the last week.

Comments (none posted)

Quotes of the week

— Daniel Vetter

— Paul McKenney

Comments (none posted)

The end of the 4.11 merge window

By the time Linus Torvalds released 4.11-rc1 and closed the merge window for this development cycle, 10,960 non-merge commits had been pulled into the mainline repository. Just over 800 of those were pulled after the writing of last week's summary. Thus, there is a relatively small set of patches to cover here, but a couple of the more significant changes were saved for last.

• The long-awaited statx() system call has been merged. This new version of stat(), which has been in the works since 2010, adds a number of new features and efficiency improvements. See the commit changelog for details.

• New hardware support includes: Renesas R-Car Gen3 thermal sensors, ZTE zx2967 SoC thermal sensors, and QLogic QEDF 25/40/100Gb FCoE initiators

• As predicted, the large sched.h refactoring work has been merged. In theory, all kernel code that needs to be fixed in responses to these changes has indeed been fixed, but there may still be a few loose ends here and there.

The 4.11 kernel has now entered the stabilization period. If things go according to the normal schedule, the final 4.11 release can be expected on April 16 or 23.

Comments (none posted)

March 6 Kernel Podcast

Jon Masters's kernel podcast for March 6 is out. "In this week’s kernel podcast: Linus Torvalds announces Linux 4.11-rc1, rants about folks not correctly leveraging linux-next, the remainder of this cycle’s merge window pulls, and announcements concerning end of life for some features."

Comments (none posted)

Per-task CPU-frequency control

The kernel's power-management code attempts to run each processor on the system at a level that minimizes power consumption while ensuring that sufficient CPU time is available for the currently running tasks. CPU frequency management has, over the last few years, become more closely tied to the scheduler, since that is where the information about the current workload resides. The scheduler, however, does not know which processes are most important to the user. Various attempts to fill in that information have been made over time, with none making it into the mainline; the latest version takes a different approach.

The core idea behind workload-sensitive power management is that the user (or, more likely, some sort of policy daemon working on the user's behalf) may want to influence how decisions are made depending on which processes are running. For processes that the user would like to see run quickly — those currently running in the foreground on a handset, for example — it may be desirable to run the CPU at a higher rate than is strictly necessary to get the expected amount of work done. On the other hand, if only a low-priority background task is running, it may be best to put an upper limit on how fast the CPU runs, even if that task has a lot of work to do. At the moment, however, the power-management code cannot distinguish those types of process from each other, so the same frequency-scaling policies apply to all of them.

Recent attempts to solve this problem have taken the form of a control-group controller called SchedTune. This controller allowed a "boost" value to be applied to processes in a specific control group. Those processes would be made to appear to require more CPU time than they actually needed, causing the CPU-frequency governor to pick a higher frequency than it otherwise would have. This approach worked, but one might argue that the approach of distorting the apparent load to influence frequency selection lacked elegance.

At the end of February, Patrick Bellasi posted a new patch set that takes a different approach. The separate SchedTune controller is no more; instead, CPU-frequency policy has been moved into the core CPU controller, where it can be found alongside the other scheduling parameters for any given control group.

The "boost" value and the load-distorting algorithm it used are gone. In their place are two new control knobs, called capacity_min and capacity_max. They place bounds on the CPU frequency choices that can be made when any process in the group is running. The capacity_min value describes the slowest allowable CPU speed; by default, it is set to zero, meaning that even the slowest CPU frequency is acceptable. The maximum allowable frequency is set by capacity_max; the default value here is 1024, allowing the CPU to go to its maximum speed. An important process can thus be guaranteed a certain minimum CPU performance by setting capacity_min to an appropriate value, while low-priority tasks can be prevented from pushing the CPU frequency too high with capacity_max.

At any given time, there may be multiple runnable processes, and they may not all have the same capacity_min and capacity_max parameters. Changing the CPU's operating parameters is a relatively expensive operation, so it does not make sense to change the operating frequency every time a new process is given access to the CPU. One could also argue that, when a process with relatively high CPU-power requirements is waiting, the other processes should be run at just as high a power level to avoid delaying that process excessively.

The end result is that the scheduler needs to pick a set of parameters that is suitable for all of the processes that are currently runnable. To meet that requirement, the controller will apply the maximum value of both parameters. That ensures that the process(es) with the highest values will actually get those values, and no process will run at a lower CPU frequency than it is entitled to. Implementing this policy requires adding two red-black trees to each control group tracking the processes with the highest capacity_min and capacity_max values.

When multiple levels of control groups are in use, subgroups are only allowed to tighten the constraints set in their parent groups. So capacity_min in a subgroup cannot go below that value in the parent, while capacity_max cannot exceed the parent's value.

In previous patch sets, this feature has been focused on the SCHED_OTHER (normal) scheduling class. With this patch set, though, it has also been extended to the realtime and deadline scheduling classes. In current kernels, those classes are run at the maximum speed the processor supports. With this change, realtime and deadline scheduling can be used in a more power-friendly mode. Needless to say, tuning of these parameters with such workloads will need to be done carefully to avoid configuring a system that cannot meet its realtime requirements.

As of this writing, there have been no comments on the new patch set. That, perhaps, is one of the hazards of posting core-kernel patches during the merge window. One might guess that this version offers relatively little to complain about, but experience suggests that one might easily guess incorrectly when it comes to scheduler patches. Once the scheduler developers have a chance to look at this code, we'll have a better idea of whether it's likely to get into the mainline in its current form.

Comments (none posted)

RCU and the mid-boot dead zone

When discussing RCU with mainstream formal-verification researchers, there often comes a time when they ask for RCU's specification. There is of course a specification of a sort, which was first published here, here, and here; it is currently maintained in the Linux-kernel source tree. However, these “specifications” are empirical in nature: As hardware, other parts of the kernel, and workloads change, RCU's specification also changes. This is not what mainstream formal-verification researchers want to hear, so I usually tell them stories of how I learned about various aspects of the RCU specification. This article tells one of those stories.

But first, let's review RCU's grace-period guarantee. This guarantee requires that RCU's synchronous grace-period primitives wait for any pre-existing RCU read-side critical sections. For example, consider the following two in-kernel tasks:

int x, y, r1, r2;

void task0(void)
{
	WRITE_ONCE(x, 1);
	synchronize_rcu();
	WRITE_ONCE(y, 1);
}

void task1(void)
{
	rcu_read_lock();
	r1 = READ_ONCE(x);
	r2 = READ_ONCE(y);
	rcu_read_unlock();
}

Suppose that task1()'s load from x returns zero. This means that some part of task1()'s RCU read-side critical section (delimited by rcu_read_lock() and rcu_read_unlock()) executed prior to task0()'s store to x, which in turn means that this critical section started before task0()'s RCU grace period. RCU therefore guarantees that the rest of task1()'s critical section section completes before that grace period ends, which in turn means that the read from y will return zero. Similarly, if task1()'s read from y returns one, part of task1()'s RCU read-side critical section has executed after task0()'s RCU grace period. RCU therefore guarantees that the entirety of task1()'s critical section executes after the start of the grace period, which in turn means that the read from x will return one.

In short, RCU read-side critical sections are not permitted to completely overlap RCU grace periods.

During early boot, it is trivially easy to provide this guarantee because there is only one task and preemption is disabled. This means that the fact that synchronize_rcu() has been called means that all pre-existing readers must have been completed. Therefore, RCU's grace-period primitives can be no-ops during early boot. But early boot ends as soon as the kernel starts spawning kthreads.

At run time, RCU's grace-period guarantee is provided by the run-time RCU machinery, which by that time has been fully initialized. But the run-time RCU machinery cannot operate correctly until after all of RCU's kthreads have been spawned and initialized, which clearly cannot happen until some time after the kernel starts spawning kthreads.

Let's call time period between early boot and run time the mid-boot dead zone. This dead zone starts when the kernel spawns the first kthread, and ends once all of RCU's kthreads have been spawned and are ready. As noted here, RCU's synchronous grace periods might well deadlock during the mid-boot dead zone.

Hoping that nobody calls for a synchronous grace period during the mid-boot phase worked well for some years. However, I made the mistake of accidentally causing synchronize_rcu_expedited(), synchronize_rcu_bh_expedited(), and synchronize_sched_expedited() to operate correctly during the mid-boot dead zone. The ACPI developers noticed that these primitives worked, and promptly took full advantage of my lapse, perhaps completely unintentionally. Because I didn't make these functions log a warning if used during the dead zone, these developers had absolutely no hint that they were skating on thin ice. Had they built with CONFIG_SMP=n or booted with the rcu_normal kernel-boot parameter, RCU would have complained bitterly. However CONFIG_SMP=n is used primarily for deep embedded systems, and rcu_normal is used primarily on realtime systems, so it is not all that surprising that they didn't test them.

However, the ACPI developers did notice once v4.9 came out, because that was the release in which I switched synchronize_rcu_expedited(), synchronize_rcu_bh_expedited(), and synchronize_sched_expedited() to workqueues. This change eliminated some ugly interactions with POSIX signals, however it also re-introduced the mid-boot dead zone, which had the minor downside of complete and utter failure for the ACPI developers.

Although this could be fixed in ACPI, it is easy to imagine a use case that really needed a real RCU grace period. It is therefore preferable to get RCU's mid-boot dead zone out of ACPI's way. If nothing else, eliminating RCU's mid-boot dead zone should save me considerable time explaining that dead zone to future Linux-kernel developers. As usual, this was easier said than done.

My first thought was to spawn RCU's kthreads much earlier in the boot process, thus narrowing the mid-boot dead zone, so that the ACPI use fell outside of that zone. However, RCU creates different numbers and types of kthreads under different kernel configurations, which complicates the task of creating all these kthreads at one point in the code. This approach therefore did not make it past the design phase, although it did consume at least its share of paper and ink.

My second thought was to introduce kthreads into RCU's expedited grace-period primitives, given that the expedited code can be driven by a single kthread. Once this is in place, non-expedited synchronous grace periods can be forced to use the expedited code path during the dead zone, which would allow full functionality. This is much simpler than the first approach, and resulted in this reasonably simple patch. Borislav Petkov tested this patch and found that it fixed the problem, which was another plus.

However, this patch had the disadvantage of turning RCU into a special kernel subsystem that creates its kthreads before any other kernel subsystem. This might work fine for awhile, but Murphy says that it is only a matter of time before some other kernel subsystem also needs to be the first to spawn its kthreads. In addition, there is still a dead zone, albeit a very short one. But if kthread creation itself ever needed to invoke synchronous RCU grace periods, this approach would be completely broken. It would be much better if RCU grace periods simply worked throughout the entire boot process.

My third thought was to make expedited RCU grace periods go back to their 4.8 behavior, so that the requesting task drives the expedited grace period. In order to avoid the ugliness involving POSIX signals, expedited grace periods would switch back to workqueues as soon as RCU's kthreads had been spawned. This assumes that in-kernel tasks never send each other POSIX signals during the mid-boot dead zone, which seems a safe assumption for the moment, and which can be worked around if needed. In addition, it results in a reasonably small patch.

The great strength of this approach is that there is no longer a mid-boot dead zone: synchronize_rcu_expedited(), synchronize_rcu_bh_expedited(), synchronize_sched_expedited(), synchronize_rcu(), synchronize_rcu_bh(), and synchronize_sched() may be invoked throughout the entire boot process. This in turn simplifies RCU's specification, at a price of only about seventy lines of code added to the kernel, and without the addition of any kthreads. In addition, RCU can continue to spawn its kthreads at early_initcall() time, so that RCU need not be the special first subsystem to create kthreads. Finally, the switch to normal run-time operation can happen at core_initcall() time: there is no need to switch to run-time mode immediately after RCU's kthreads have been spawned.

It is still early days for this patch, but current results are quite encouraging.

This experience resulted in several lessons (re)learned:

1. Maintaining uniform semantics across the Linux kernel's boot-time and run-time code can be quite challenging, but greatly improves ease-of-use.
2. If you don't make it warn, it won't be considered illegal.
3. If you didn't make it warn, but then make it no longer work, you will likely have unhappy users.

Last, but by no means least, RCU's specification is empirical, and this is the story of how I learned about yet another new-to-me aspect of that specification.

Acknowledgments

I own thanks to Lv Zheng, Borislav Petkov, Stan Kain, Ivan (AKA waffolz@hotmail.com), Emanuel Castelo, Bruno Pesavento, Frederic Bezies, and Rafael J. Wysocki for reporting, reviewing, testing, and otherwise keeping me honest. I also owe thanks to Jim Wasko for his support of this effort.

Quick Quiz answer

Quick Quiz: But wouldn't this mid-boot dead zone end when workqueues are initialized, which happens much earlier than the spawning of RCU's kthreads?

Answer: In theory, yes. In practice, the kernel might have been booted with rcu_normal, which would cause the expedited grace periods to use the non-expedited code path. So in this case, the mid-boot dead zone for synchronize_rcu_expedited(), synchronize_rcu_bh_expedited(), and synchronize_sched_expedited() is exactly the same as that for synchronize_rcu(), synchronize_rcu_bh(), and synchronize_sched(), which ends after RCU's kthreads has been spawned.

Back to Quick Quiz 1.

Comments (2 posted)