linux-kernel - Re: [patch 13/15] sched: expire slack quota using generation counters

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: <1302089181.2225.1380.camel@twins>
Date:	Wed, 06 Apr 2011 13:26:21 +0200
From:	Peter Zijlstra <a.p.zijlstra@...llo.nl>
To:	Paul Turner <pjt@...gle.com>
Cc:	linux-kernel@...r.kernel.org,
	Bharata B Rao <bharata@...ux.vnet.ibm.com>,
	Dhaval Giani <dhaval.giani@...il.com>,
	Balbir Singh <balbir@...ux.vnet.ibm.com>,
	Vaidyanathan Srinivasan <svaidy@...ux.vnet.ibm.com>,
	Srivatsa Vaddagiri <vatsa@...ibm.com>,
	Kamalesh Babulal <kamalesh@...ux.vnet.ibm.com>,
	Ingo Molnar <mingo@...e.hu>, Pavel Emelyanov <xemul@...nvz.org>
Subject: Re: [patch 13/15] sched: expire slack quota using generation
 counters

On Wed, 2011-04-06 at 00:22 -0700, Paul Turner wrote:
> 
> scratches head... erm right, I meant to pair this with a read barrier
> on querying the generation but balked when I realized that still
> yields an lfence on x86 since I didn't want to introduce that to the
> update_curr() path.
> 
> While we can probably do away with the barrier completely (it's not
> critical that we line them up perfectly with the new generation), I've
> been thinking about this one and I think I have something a little
> nicer that also reduces the shared cache hits.
> 
> We can take advantage of the fact that sched_clocks are already
> synchronized within 2 jiffies and store the quota's expiration,
> instead of a generation, when we refresh.
> 
> This effectively yields a fairly simple control flow (we can use
> rq->clock since we're always paired with update_rq_clock operations):
> a) our rq->clock < expiration always implies quota is valid
> 
> Obviously if our cpu clock is ahead of the one that issued the quota,
> our quota is still valid since the real deadline is even further
> behind
> Even if our cpu's clock is behind the max 1.99 jiffies the amount of
> time that the stale quota can remain valid is basically already within
> our potential margin of error since for a long running process we
> check on each tick edge anyway.
> 
>  b) our rq->clock > expiration
> 
> Again there's two cases, if our cpu clock is behind (or equal) then
> the deadline has indeed passed and the quota is expired.  This can be
> confirmed by comparing the global deadline with our local one (the
> global expiration will have advanced with quota refresh for this to be
> true).
> 
> We can also catch that our cpu is potentially ahead -- by the fact
> that our rq->clock > expiration but that the global expiration has not
> yet advanced.  In this case we recognize that our quota is still valid
> and extend our local expiration time by either the maximum margin of
> error or some fraction there of (say 1 jiffy) which is guaranteed to
> push us back in case a) above.  Again this is within our existing
> margin of error due to entity_tick() alignment.
> 
> This ends up looking a lot simpler and avoids much of the pressure on
> the global variable since we need to compare against it in the case
> where our clock passes expiration, once a quota period (as the
> extension will put us in case a where we know we don't need to
> consider it).
> 
> This ends up simpler than the generation muck and can be introduced
> cleanly earlier in the series, avoiding the churn mentioned above.
> 
> Make sense? 

Yes, that ought to work.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/