linux-kernel - Re: [tip:sched/core] sched: Lower chances of cputime scaling overflow

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: <1365701469.10217.6.camel@laptop>
Date:	Thu, 11 Apr 2013 19:31:09 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Stanislaw Gruszka <sgruszka@...hat.com>
Cc:	linux-kernel@...r.kernel.org, mingo@...nel.org, hpa@...or.com,
	fweisbec@...il.com, rostedt@...dmis.org, akpm@...ux-foundation.org,
	tglx@...utronix.de, linux-tip-commits@...r.kernel.org,
	Linus Torvalds <torvalds@...ux-foundation.org>
Subject: Re: [tip:sched/core] sched: Lower chances of cputime scaling
 overflow

On Thu, 2013-04-11 at 16:50 +0200, Stanislaw Gruszka wrote:

> > +	/*
> > +	 * Since the stime:utime ratio is already an approximation through
> > +	 * the sampling, reducing its resolution isn't too big a deal.
> > +	 * And since total = stime+utime; the total_fls will be the biggest
> > +	 * of the two;
> > +	 */
> > +	if (total_fls > 32) {
> > +		shift = total_fls - 32; /* a = 2^shift */
> > +		stime >>= shift;
> > +		total >>= shift;
> > +		stime_fls -= shift;
> > +		total_fls -= shift;
> > +	}
> > +
> > +	/*
> > +	 * Since we limited stime to 32bits the multiplication reduced to 96bit.
> > +	 *   stime * rtime = stime * (rl + rh * 2^32) = 
> > +	 *                   stime * rl + stime * rh * 2^32
> > +	 */
> > +	lo = stime * rtime_lo;
> > +	hi = stime * rtime_hi;
> > +	t = hi << 32;
> > +	lo += t;
> > +	if (lo < t) /* overflow */
> > +		hi += 0x100000000L;
> > +	hi >>= 32;
> 
> I do not understand why we shift hi value here, is that correct?

Yes.. remember that we have:

  stime * rl + stime * rh * 2^32

How we get this 96bit value but our two 64bit values overlap:

 | w3 | w2 | w1 | w0 |
 +----+----+----+----+
           |    lo   |
       |   hi   |

So what I do is I add the low word of hi to lo and shift the high word
of hi to get:

 |     hi  |    lo   |

Two non-overlapping 64bit values where the high word of hi is always 0.

> > +	/*
> > +	 * Pick the 64 most significant bits for division into @lo.
> > +	 * 
> > +	 * NOTE: res_fls is an approximation (upper-bound) do we want to
> > +	 *       properly calculate?
> > +	 */
> > +	shift = 0;
> > +	res_fls = stime_fls + rtime_fls;
> > +	if (res_fls > 64) {
> > +		shift = res_fls - 64; /* b = 2^shift */
> > +		lo >>= shift;
> > +		hi <<= 64 - shift;
> > +		lo |= hi;
> >  	}
> > -	return (__force cputime_t) scaled;
> > +	/*
> > +	 * So here we do:
> > +	 *
> > +	 *    ((stime / a) * rtime / b)
> > +	 *    --------------------------- / b
> > +	 *           (total / a)
> > +	 */
> > +	return div_u64(lo, total) >> shift;
> 
> I think it should be:
> 
>  ((stime / a) * rtime / b)
> --------------------------- * b
>         (total / a)
> 
> return div_u64(lo, total) << shift;

I think you're very right about that.. got my head twisted by staring
at this stuff too long.

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