linux-kernel - Re: [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr

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-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20231005141408.GB743@noisy.programming.kicks-ass.net>
Date:   Thu, 5 Oct 2023 16:14:08 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Youssef Esmat <youssefesmat@...omium.org>
Cc:     Daniel Jordan <daniel.m.jordan@...cle.com>, mingo@...nel.org,
        vincent.guittot@...aro.org, linux-kernel@...r.kernel.org,
        juri.lelli@...hat.com, dietmar.eggemann@....com,
        rostedt@...dmis.org, bsegall@...gle.com, mgorman@...e.de,
        bristot@...hat.com, corbet@....net, qyousef@...alina.io,
        chris.hyser@...cle.com, patrick.bellasi@...bug.net, pjt@...gle.com,
        pavel@....cz, qperret@...gle.com, tim.c.chen@...ux.intel.com,
        joshdon@...gle.com, timj@....org, kprateek.nayak@....com,
        yu.c.chen@...el.com, joel@...lfernandes.org, efault@....de,
        tglx@...utronix.de
Subject: Re: [PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr

On Thu, Oct 05, 2023 at 02:05:57PM +0200, Peter Zijlstra wrote:

> Using the attached program (I got *REALLY* fed up trying to draw these
> diagrams by hand), let us illustrate the difference between Earliest
> *Eligible* Virtual Deadline First and the one with the Eligible test
> taken out: EVDF.
> 
> Specifically, the program was used with the following argument for
> EEVDF:
> 
>   ./eevdf -e "0,1024,6" -e "1,1024,2" -e "2,1024,18" -v 19 
> 
> and with an additional '-n' for the EVDF column.
> 

<snip a metric ton of diagrams>

> 
> As I wrote before; EVDF has worse lag bounds, but this is not
> insurmountable. The biggest problem that I can see is that of wakeup
> preemption. Currently we allow to preempt when 'current' has reached V
> (RUN_TO_PARITY in pick_eevdf()).
> 
> With these rules, when EEVDF schedules C (our large slice task) at t=10
> above, it is only a little behind C and can be reaily preempted after
> about 2 time units.
> 
> However, EVDF will delay scheduling C until much later, see how A and B
> walk far ahead of V until t=36. Only when will we pick C. But this means
> that we're firmly stuck with C for at least 11 time units. A newly
> placed task will be around V and will have no chance to preempt.
> 
> That said, I do have me a patch to cure some of that:
> 
>   https://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git/commit/?h=sched/eevdf&id=d7edbe431f31762e516f2730196f41322edcc621
> 
> That would allow a task with a shorter request time to preempt in spite
> of RUN_TO_PARITY.
> 

So, doing all that gave me an idea, see queue/sched/eevdf BIAS_ELIGIBLE.

It pushes the eligibility threshold (V) right by one average request.
The below patch is against eevdf.c.

I've not yet ran it through the normal set of hackbench,netperf etc.. so
it might eat your pet and set your granny on fire.


--- eevdf.c.orig	2023-10-05 16:11:35.821114320 +0200
+++ eevdf.c	2023-10-05 16:08:38.387080327 +0200
@@ -7,6 +7,7 @@
 #include <sys/param.h>
 
 bool eligible = true;
+bool bias = false;
 unsigned long V_lim = 20;
 
 struct entity {
@@ -79,16 +80,17 @@
 
 struct entity *pick_entity(int nr, struct entity *es)
 {
-	unsigned long W = 0, V = 0;
+	unsigned long W = 0, V = 0, R = 0;
 	struct entity *e = NULL;
 
 	for (int i = 0; i < nr; i++) {
 		V += es[i].weight * es[i].vruntime;
+		R += es[i].request;
 		W += es[i].weight;
 	}
 
 	for (int i = 0; i < nr; i++) {
-		if (eligible && W*es[i].vruntime > V)
+		if (eligible && W*es[i].vruntime > V + (bias * R))
 			continue;
 
 		if (!e || es[i].vdeadline < e->vdeadline)
@@ -169,10 +171,14 @@
 
 	const int N = sizeof(es) / sizeof(es[0]);
 
-	while ((opt = getopt(argc, argv, "nv:e:")) != -1) {
+	while ((opt = getopt(argc, argv, "bnv:e:")) != -1) {
 		unsigned int v,w,r;
 
 		switch (opt) {
+		case 'b':
+			bias = true;
+			break;
+
 		case 'n':
 			eligible = false;
 			break;