linux-kernel - Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

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 for Android: free password hash cracker in your pocket

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

Message-ID: <xhsmhh6c2ubq4.mognet@vschneid-thinkpadt14sgen2i.remote.csb>
Date: Fri, 02 Aug 2024 18:32:35 +0200
From: Valentin Schneider <vschneid@...hat.com>
To: Peter Zijlstra <peterz@...radead.org>
Cc: mingo@...hat.com, juri.lelli@...hat.com, vincent.guittot@...aro.org,
 dietmar.eggemann@....com, rostedt@...dmis.org, bsegall@...gle.com,
 mgorman@...e.de, linux-kernel@...r.kernel.org, kprateek.nayak@....com,
 wuyun.abel@...edance.com, youssefesmat@...omium.org, tglx@...utronix.de,
 efault@....de
Subject: Re: [PATCH 17/24] sched/fair: Implement delayed dequeue

On 02/08/24 16:59, Peter Zijlstra wrote:
> On Fri, Aug 02, 2024 at 04:39:08PM +0200, Valentin Schneider wrote:
>>
>> On 27/07/24 12:27, Peter Zijlstra wrote:
>> > Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
>> > noting that lag is fundamentally a temporal measure. It should not be
>> > carried around indefinitely.
>> >
>> > OTOH it should also not be instantly discarded, doing so will allow a
>> > task to game the system by purposefully (micro) sleeping at the end of
>> > its time quantum.
>> >
>> > Since lag is intimately tied to the virtual time base, a wall-time
>> > based decay is also insufficient, notably competition is required for
>> > any of this to make sense.
>> >
>> > Instead, delay the dequeue and keep the 'tasks' on the runqueue,
>> > competing until they are eligible.
>> >
>> > Strictly speaking, we only care about keeping them until the 0-lag
>> > point, but that is a difficult proposition, instead carry them around
>> > until they get picked again, and dequeue them at that point.
>> >
>>
>> Question from a lazy student who just caught up to the current state of
>> EEVDF...
>>
>> IIUC this makes it so time spent sleeping increases an entity's lag, rather
>> than it being frozen & restored via the place_entity() magic.
>>
>> So entities with negative lag get closer to their 0-lag point, after which
>> they can get picked & dequeued if still not runnable.
>
> Right.
>
>> However, don't entities with positive lag get *further* away from their
>> 0-lag point?
>
> Which is why we only delay de dequeue when !eligible, IOW when lag is
> negative.
>
> The next patch additionally truncates lag to 0 (for delayed entities),
> so they can never earn extra time.

Gotcha, thanks for pointing that out, I think I'm (slowly) getting it :D