| 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: <CA+q576MLvCwH2YQFx3V2tf3f4n6JUze7jkpqqTx97UPsOHewhg@mail.gmail.com>
Date: Thu, 5 Oct 2023 13:23:14 -0500
From: Youssef Esmat <youssefesmat@...omium.org>
To: Peter Zijlstra <peterz@...radead.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 5, 2023 at 7:06 AM Peter Zijlstra <peterz@...radead.org> wrote:
>
> 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.
>
Thank you for the detailed analysis! I am still in the process of
digesting everything.
I do have a quick question, this will only be the case if we adjust
C's runtime without adjusting nice value, correct? So it does not
currently apply to the submitted code where the only way to change the
deadline is to also change the nice value and thus how fast/slow
vruntime accumulates. In other words without the sched_runtime
patch[1] we should not run into this scenario, correct?
[1] https://lore.kernel.org/lkml/20230915124354.416936110@noisy.programming.kicks-ass.net/
> 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.
Powered by blists - more mailing lists