| 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
| ||
|
Message-ID: <20231005120557.GA743@noisy.programming.kicks-ass.net>
Date: Thu, 5 Oct 2023 14:05:57 +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 Mon, Oct 02, 2023 at 08:41:36PM +0200, Peter Zijlstra wrote:
> When mixing request sizes things become a little more interesting.
>
> Let me ponder this a little bit more.
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.
EEVDF EVDF
d = 6 d = 6
d = 2 d = 2
d = 18 d = 18
q = 2 q = 2
t=0 V=1 t=0 V=1
A |----< A |----<
>B |< >B |<
C |----------------< C |----------------<
|*--------|---------|---------|---------|---- |*--------|---------|---------|---------|----
t=2 V=1 t=2 V=1
>A |----< A |----<
B |< >B |<
C |----------------< C |----------------<
|*--------|---------|---------|---------|---- |*--------|---------|---------|---------|----
t=8 V=3 t=4 V=2
A |----< >A |----<
>B |< B |<
C |----------------< C |----------------<
|--*------|---------|---------|---------|---- |-*-------|---------|---------|---------|----
t=10 V=4 t=10 V=4
A |----< A |----<
B |< >B |<
>C |----------------< C |----------------<
|---*-----|---------|---------|---------|---- |---*-----|---------|---------|---------|----
t=28 V=10 t=12 V=5
A |----< A |----<
>B |< >B |<
C |----------------< C |----------------<
|---------*---------|---------|---------|---- |----*----|---------|---------|---------|----
t=30 V=11 t=14 V=5
A |----< A |----<
>B |< >B |<
C |----------------< C |----------------<
|---------|*--------|---------|---------|---- |----*----|---------|---------|---------|----
t=32 V=11 t=16 V=6
A |----< >A |----<
>B |< B |<
C |----------------< C |----------------<
|---------|*--------|---------|---------|---- |-----*---|---------|---------|---------|----
t=34 V=12 t=22 V=8
>A |----< A |----<
B |< >B |<
C |----------------< C |----------------<
|---------|-*-------|---------|---------|---- |-------*-|---------|---------|---------|----
t=40 V=14 t=24 V=9
A |----< A |----<
>B |< >B |<
C |----------------< C |----------------<
|---------|---*-----|---------|---------|---- |--------*|---------|---------|---------|----
t=42 V=15 t=26 V=9
A |----< A |----<
>B |< >B |<
C |----------------< C |----------------<
|---------|----*----|---------|---------|---- |--------*|---------|---------|---------|----
t=44 V=15 t=28 V=10
A |----< >A |----<
>B |< B |<
C |----------------< C |----------------<
|---------|----*----|---------|---------|---- |---------*---------|---------|---------|----
t=46 V=16 t=34 V=12
>A |----< A |----<
B |< >B |<
C |----------------< C |----------------<
|---------|-----*---|---------|---------|---- |---------|-*-------|---------|---------|----
t=52 V=18 t=36 V=13
A |----< A |----<
>B |< B |<
C |----------------< >C |----------------<
|---------|-------*-|---------|---------|---- |---------|--*------|---------|---------|----
t=54 V=19 t=54 V=19
A |----< A |----<
>B |< >B |<
C |----------------< C |----------------<
|---------|--------*|---------|---------|---- |---------|--------*|---------|---------|----
lags: -10, 6 lags: -7, 11
BAaaBCccccccccBBBAaaBBBAaaBB BBAaaBBBAaaBBBAaaBCccccccccB
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.
However, in this example V is only 2/3 of the way to C's deadline, but
it we were to have many more tasks, you'll see V gets closer and closer
to C's deadline and it will become harder and harder to place such that
preemption becomes viable.
Adding 4 more tasks:
./eevdf -e "0,1024,6" -e "1,1024,2" -e "2,1024,18" -v 19 -n -e "3,1024,2" -e "4,1024,2" -e "5,1024,2" -e "6,1024,2"
t=92 V=16
A |----<
B |<
>C |----------------<
D |<
E |<
F |<
G |<
|---------|-----*---|---------|---------|----
And I worry this will create very real latency spikes.
That said; I do see not having the eligibility check can help. So I'm
not opposed to having a sched_feat for this, but I would not want to
default to EVDF.
View attachment "eevdf.c" of type "text/x-csrc" (4010 bytes)
Powered by blists - more mailing lists