Re: [PATCH 1/1] cputime: Make the reported utime+stime correspond to the actual runtime.

[Frederic Weisbecker <fweisbec@gmail.com>]

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! :-)