Date: Tue, 7 Jul 2015 17:34:13 +0200
From: Peter Zijlstra <peterz@infradead.org>
To: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Fredrik =?iso-8859-1?Q?Markstr=F6m?= 
	<fredrik.markstrom@gmail.com>,
        mingo@redhat.com, linux-kernel@vger.kernel.org,
        Rik van Riel <riel@redhat.com>, Jason Low <jason.low2@hp.com>
Subject: Re: [PATCH 1/1] cputime: Make the reported utime+stime correspond to
 the actual runtime.
Message-ID: <20150707153413.GS3644@twins.programming.kicks-ass.net>
References: <20150630093054.GK19282@twins.programming.kicks-ass.net>
 <CAKdL+dR68T7LMZ_ndwihvMo_SaUB1G++JaZ28RXiqaHs9gpP0g@mail.gmail.com>
 <20150630121812.GG3644@twins.programming.kicks-ass.net>
 <CAKdL+dTTgfKrskE5d6OxktxJ4SHeMvmRPka4oAQ97LJmDefn6A@mail.gmail.com>
 <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20150707133420.GA20498@lerouge>
User-Agent: Mutt/1.5.21 (2012-12-30)
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2694
Lines: 83

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.

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.

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?


--
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/