linux-kernel - SCHED_DEADLINE cpudeadline.{h,c} fixup

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <1471184828-12644-1-git-send-email-tommaso.cucinotta@sssup.it>
Date:	Sun, 14 Aug 2016 16:27:05 +0200
From:	Tommaso Cucinotta <tommaso.cucinotta@...up.it>
To:	Luca Abeni <luca.abeni@...tn.it>,
	Juri Lelli <juri.lelli@...il.com>,
	Peter Zijlstra <peterz@...radead.org>,
	Ingo Molnar <mingo@...hat.com>
Cc:	linux-kernel@...r.kernel.org, linux-dl@...is.sssup.it,
	Tommaso Cucinotta <tommaso.cucinotta@...up.it>
Subject: SCHED_DEADLINE cpudeadline.{h,c} fixup

Hi,

this is a rework of the cpudeadline bugfix and speed-up patch-set, that
integrates all comments received so far from Luca, Juri and Peter.

Compared with the previous post, here:
-) I'm keeping out the minimally invasive bugfix, as it's already been
   merged in tip/sched/core
-) I moved some little code refactory around change_key_dl() out of the
  (now) 2nd patch, to the 1st one. Now the 2nd (speed-up) patch just
  changes the heapify_up/down() functions
-) I rebased on top of commit f0b22e39
-) I repeated an extensive set of tests through the framework published
   separately at: https://github.com/tomcucinotta/cpudl-bench
   repeating new no-behavior-change tests, new heap-consistency tests,
   and new a/b benchmarks (I'm working on a new i5 laptop now), results at:
     https://github.com/tomcucinotta/cpudl-bench/blob/master/cpudl-100000.pdf
   highlighting up to a 14% speed-up when averaging over 100K ops. See the
   enclosed README in that repo for more info.

I'm leaving below the original description of all 4 patches.

--
The first patch is a minimally invasive (1-line) fix for the deadline
wrap-around bug. This leaves some weirdness in how cpudl_change_key() is
called. Therefore, the second patch does a minimum of refactory to make
things more explicit and clear.

The 3rd patch contains now the actual performance enhancement (avoiding
unneeded swaps during heapify operations), which has been measured to
achieve up to 14% of speed-up for cpudl_set() calls.
This has been measured with a randomly generated workload of 1K,10K,100K
random heap insertions and deletions (75% cpudl_set() calls with is_valid=1
and 25% with is_valid=0), and randomly generated cpu IDs, with up to 256
CPUs. Benchmarking code at: https://github.com/tomcucinotta/cpudl-bench

Finally, the 4th patch is another clear-up patch touching cpudeadline.{h,c}
and deadline.c. Now you call cpudl_clear(cp, cpu) and cpudl_set(cp, cpu, dl)
instead of cpudl_set(cp, cpu, 0 /* dl */, 0  /* is_valid */) and
cpudl_set(cp, cpu, dl, 1 /* is_valid */).

Any further comment is welcome, thanks!

  Tommaso
--