Improving idle behavior in tickless systems [LWN.net]

Improving idle behavior in tickless systems

Posted Dec 28, 2018 19:18 UTC (Fri) by rweikusat2 (subscriber, #117920)
Parent article: Improving idle behavior in tickless systems

Input devices don't generate interrupts at predictable intervals because these happen in response to unpredictable, external events. Timing of keyboard and mouse events is considered a high quality source of randomness. The only reason network input isn't is that some 'external adversary' could control the timing of network input events, at least to a degree.

to post comments

Improving idle behavior in tickless systems

Posted Dec 28, 2018 20:07 UTC (Fri) by Paf (subscriber, #91811) [Link] (7 responses)

The article does not seem to suggest or mention using input devices. It just says “devices”. I took this to mean non-input devices, which I would expect to have predictable-ish interrupt rates.

Improving idle behavior in tickless systems

Posted Dec 28, 2018 20:20 UTC (Fri) by rweikusat2 (subscriber, #117920) [Link] (6 responses)

The article said "devices". "Input devices" are a subset of "devices", hence, they weren't excluded. And their interrupt timing is not predictable (actually, the very reason for interrupts is that they notify the CPU of unpredictable, external events).

Improving idle behavior in tickless systems

Posted Dec 29, 2018 0:53 UTC (Sat) by Paf (subscriber, #91811) [Link] (5 responses)

I guess I assumed the author and the large group of kernel developers reviewing these patches were also aware of these facts about user input devices. At least among kernel developers, they are common knowledge.

Improving idle behavior in tickless systems

Posted Dec 31, 2018 21:24 UTC (Mon) by rweikusat2 (subscriber, #117920) [Link] (4 responses)

The article contained the following statement:

Devices cause interrupts at (more or less) predictable intervals that depend on the applications that are running; a cpuidle governor can measure these intervals to make predictions for when the next device interrupt will occur.

And this is simply not true. A NIC will generate interrupts in response to uncontrollable, external events for both sending and receiving. The same is true for any other kind of interrupt-using device not driven by the computer itself. As I already wrote, the very reason interrupts exist is to notify a CPU of some unpredictable change in state which needs to be handled now (or as close to now as possible) regardless of whatever else the CPU happened to be doing at the time of the event.

The code also doesn't even try to "predict" anything. After heuristically selecting some idle state based on the time until the next timer event, it compares the length of the last 8 idle periods against the 'target residency' of the selected state (in a seriously contorted way, BTW) and if more than half of them were smaller, selects a different idle state (simplification).

Improving idle behavior in tickless systems

Posted Dec 31, 2018 21:37 UTC (Mon) by corbet (editor, #1) [Link] (2 responses)

I'm sorry, but I think you're trying a little too hard here.

An individual interrupt is not predictable, but, as with the weather, a prediction that "things will happen in the future much like they have in the recent past" is relatively likely to be true. Interrupts are not quantum events, they are the result of the workload and the environment that the system is in. So there is value in a heuristic that looks at residency times and predicts that something similar will happen next.

Perhaps it's time to give this a rest?

Improving idle behavior in tickless systems

Posted Dec 31, 2018 21:46 UTC (Mon) by rweikusat2 (subscriber, #117920) [Link] (1 responses)

The code still doesn't and cannot predict device interrupts. That's something the article simply got wrong. Some part of it is based on the assumption that an idle state shouldn't be used if more than 4 of the last 8 measured idle periods were shorter than its so-called target residency. There doesn't seem to be any published rationale for this design and small powers of 2 always raise the suspicion of someone picking a number from a hat.

This may well be a sensible heuristic but a heuristic it remains --- no fortune telling aka "prediction" involved.

Improving idle behavior in tickless systems

Posted Dec 31, 2018 23:48 UTC (Mon) by rahulsundaram (subscriber, #21946) [Link]

> This may well be a sensible heuristic but a heuristic it remains --- no fortune telling aka "prediction" involved.

Prediction != fortune telling. There are multiple meanings for the same word.

https://www.merriam-webster.com/dictionary/prediction

One of them is forecast which is defined as

"to calculate or predict (some future event or condition) usually as a result of study and analysis of available pertinent data"

Improving idle behavior in tickless systems

Posted Jan 2, 2019 7:33 UTC (Wed) by flussence (guest, #85566) [Link]

>And this is simply not true. A NIC will generate interrupts in response to uncontrollable, external events for both sending and receiving. The same is true for any other kind of interrupt-using device not driven by the computer itself.
Input devices are some of the most predictable, actually. A pointer interrupt is statistically almost certain to be followed by another (thanks to Newton's laws of physics), and at regularly spaced intervals (grep MOUSE_DPI /lib/udev/hwdb.d/70-mouse.hwdb). A keyboard key down event is often followed by a corresponding key up a few milliseconds later, or some action on a known timeout.

Strong assumptions can also be made about network interrupts due to the earliest departure time queueing algorithm, wifi packet intervals, characteristics of low-spec consumer ISP hardware, timer quantization everywhere else in the stack. I just left wireshark open for a minute and saw several flows with regularly spaced packets.

Algorithmically generated inputs are really not good sources of entropy, if they were servers wouldn't need hardware RNGs.

Improving idle behavior in tickless systems

Posted Dec 29, 2018 7:38 UTC (Sat) by matthias (subscriber, #94967) [Link]

There are essentially two reasons, why this should not be a big problem for this prediction code:

First, user generated input interrupts are very few. Most people do not generate hundreds of keystrokes per second. And especially the average is really low. Therefore these interrupts hardly make a difference.

Second, while the user is producing input, especially moving the mouse, the interrupts are not that random as suggested. To generate randomness from these interrupts, one uses the least significant bits of the timing, i.e. nano- and microseconds. For power saving, we only need a rough estimate of the length of the idle period. Guessing the first bit that is not zero should be more than enough for this.

For network traffic, this is the same. Either there are few interrupts, or there is an ongoing transmission, which produces interrupts at quite regular intervals (or no interrupts at all, because the kernel switches to polling).