Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758058AbbGGQ1B (ORCPT ); Tue, 7 Jul 2015 12:27:01 -0400 Received: from mail-wi0-f172.google.com ([209.85.212.172]:36353 "EHLO mail-wi0-f172.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757449AbbGGQ0w (ORCPT ); Tue, 7 Jul 2015 12:26:52 -0400 Date: Tue, 7 Jul 2015 18:26:49 +0200 From: Frederic Weisbecker To: Peter Zijlstra Cc: Fredrik =?iso-8859-1?Q?Markstr=F6m?= , mingo@redhat.com, linux-kernel@vger.kernel.org, Rik van Riel , Jason Low Subject: Re: [PATCH 1/1] cputime: Make the reported utime+stime correspond to the actual runtime. Message-ID: <20150707162647.GG20498@lerouge> References: <20150630121812.GG3644@twins.programming.kicks-ass.net> <20150702121126.GP3644@twins.programming.kicks-ass.net> <20150702130701.GP18673@twins.programming.kicks-ass.net> <20150707005135.GH4981@lerouge> <20150707075954.GN3644@twins.programming.kicks-ass.net> <20150707080913.GT18673@twins.programming.kicks-ass.net> <20150707133420.GA20498@lerouge> <20150707153413.GS3644@twins.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20150707153413.GS3644@twins.programming.kicks-ass.net> User-Agent: Mutt/1.5.23 (2014-03-12) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3024 Lines: 88 On Tue, Jul 07, 2015 at 05:34:13PM +0200, Peter Zijlstra wrote: > On Tue, Jul 07, 2015 at 03:34:22PM +0200, Frederic Weisbecker wrote: > > Imagine the following rounds: > > > > utime:2 stime:2 rtime:4 --> prev->utime = 2 prev->stime = 2 > > > > utime:2 stime:6 rtime:8 --> prev->utime = 2 prev->stime = 6 > > > > So here if I apply your above formula we have: > > > > utime_i+1:2 = rtime_i+1:8 - stime_i:2 > > > > Which doesn't work, so probably I still misunderstand those _i things... > > Yes :-) > > So its an iterative definition, but a partial one, remember this is for > the case where we preserve stime monotonicity. In your example we > clearly do not take this branch. > > I'll try to elucidate by giving the full function (either that or I'll > confuse you more still). Lets define the whole thing as: > > {stime, utime}_i+1 = F(rtime_i+1, {ssamples, usamples}_i+1, {stime, utime}_i) > > with the constraints: > > rtime_i+1 >= rtime_i > > providing: > > stime + utime == rtime, > stime_i+1 >= stime_i, > utime_i+1 >= utime_i > > That is an iterative function computing the new state: stime_i+1, > utime_i+1, from the new input: rtime_i+1, ssamples_i+1, usamples_i+1 and > the old state: stime_i, utime_i. > > This function has a bunch of cases; the trivial ones (omitting the > subscript when they're all the same): > > A) stime = 0, utime = rtime ; when ssamples == 0 > B) utime = 0, stime = rtime ; when usamples == 0 > > And the complex ones: > > sfrac = ssamples * rtime / (ssamples + usamples) > > C) stime_i+1 = max(stime_i, sfrac_i+1) ; when rtime_i+1 - max(stime_i, sfrac_i+1) >= utime_i > utime_i+1 = rtime_i+1 - stime_i+1 > > D) stime_i+1 = rtime_i+1 - utime_i ; when rtime_i+1 - max(stime_i, sfrac_i+1) < utime_i > utime_i+1 = utime_i > > Note that we can further split C: > > C1) stime_i+1 = stime_i ; when sfrac_i+1 < stime_i && ... > utime_i+1 = rtime_i+1 - stime_1 > > C2) stime_i+1 = sfrac_i+1 ; when sfrac_i+1 >= stime_i && ... > utime_i+1 = rtime_i+1 - sfrac_i+1 > > This gives us a total of 5 cases, each selected purely on input. Alright, when put it that way it makes perfect sense! > Now, in your case, you end up in C2, because we advance stime but do not > need to guard utime. In that case we have a different formula for > utime_i+1 -- therefore your application of the formula was wrong, hence > the wrong result. Indeed! > And the proof given was for C1, which in turn is analogous to the proof > (not given) for D. > > The proof for C2 should be evident at this point (stime is advanced, > otherwise C1 and utime is advanced, otherwise D). > > Did that help -- or did I hopelessly confuse you? Makes perfect sense now! Thanks for your patience! :-) -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/