Announcing a major update for BFS for linux-4.7 based kernels.
BFS by itself:
-ck branded linux-4.7-ck2 patches:
This is the largest BFS update in a long time. The various problems that had been accumulating forced me to spend a more extended period fixing BFS to work with the latest mainline changes and encouraged me to overhaul some areas that had long been needing it.
The changes are:
- Fixed the crash when SMT NICE is configured in on a CPU without SMT.
- Added my skiplist implementation.
- Converted BFS from its long-standing O(n) lookup to use skiplists.
- Fix crash when SMT NICE is enabled on some hardware
- Fix try_preempt missing the locality diff effect in non-interactive mode
- Ignore busy threads/caches when still on the same core
- Reworked the testing of idle threads and cores for less overhead and to correctly identify idle siblings
- Fix the CPU load that's passed to the cpu frequency governor, fixing a crash and non-working schedutil governor.
Actually incorporating the skiplists that I had experimented with a long time ago was decided on by the fact that I was able to trim the skiplist overhead further and maintain identical semantics for process selection (maintaining interactivity) whereas on the previous experiment I had never completed the work. Throughput testing shows virtually identical performance on normal workloads and theoretically would be helpful in extreme overload cases.
The original post regarding skip lists was here:
This now means that BFS is no longer O(n) lookup after O(1) insertion. It is now O(log(n)) insertion, O(1) lookup and O(k) removal where k <= 16, thereby tackling a long-standing criticism of the overall design.
I did not find a specific cause for peoples' inability to suspend to ram so I doubt this has been fixed despite the large code update.
The list of patches making up bfs480 is as follows:
bfs472-fix_set_task_cpu.patch skiplists.patch bfs472-skiplist.patch bfs-delay-smt-siblings.patch bfs-fix-noninteractive-try-preempt.patch bfs-ignore_local_busy.patch bfs-rework-idles.patch bfs-fix-schedutil.patch bfs-v480.patch
As always I'm giving this to you not long after I've finished coding it so all the usual warnings apply, especially with an update of this size.
EDIT: Uniprocessor build fix: bfs480-fix-upbuild.patch
EDIT2: Here is a test patch to try and improve cpufreq behaviour: bfs480-rework_cpufreq.patch