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

[Peter Zijlstra <peterz@infradead.org>]

On Tue, 2013-03-26 at 15:01 +0100, Stanislaw Gruszka wrote:
> Thoughts?

Would something like the below work?

(warning: it's never even been near a compiler)

---
 kernel/sched/cputime.c | 78 +++++++++++++++++++++++++++++++++++---------------
 1 file changed, 55 insertions(+), 23 deletions(-)

diff --git a/kernel/sched/cputime.c b/kernel/sched/cputime.c
index 699d597..465f6db 100644
--- a/kernel/sched/cputime.c
+++ b/kernel/sched/cputime.c
@@ -522,35 +522,67 @@ void account_idle_ticks(unsigned long ticks)
 }
 
 /*
- * Perform (stime * rtime) / total with reduced chances
- * of multiplication overflows by using smaller factors
- * like quotient and remainders of divisions between
- * rtime and total.
+ * Perform: (stime * rtime) / total
  */
 static cputime_t scale_stime(u64 stime, u64 rtime, u64 total)
 {
-	u64 rem, res, scaled;
+	int stime_fls = fls64(stime);
+	int total_fls = fls64(total);
+	int rtime_fls = fls64(rtime);
+	int shift, res_fls;
+	u32 rtime_hi = rtime >> 32, rtime_lo = rtime;
+	u64 hi, lo, t;
 
-	if (rtime >= total) {
-		/*
-		 * Scale up to rtime / total then add
-		 * the remainder scaled to stime / total.
-		 */
-		res = div64_u64_rem(rtime, total, &rem);
-		scaled = stime * res;
-		scaled += div64_u64(stime * rem, total);
-	} else {
-		/*
-		 * Same in reverse: scale down to total / rtime
-		 * then substract that result scaled to
-		 * to the remaining part.
-		 */
-		res = div64_u64_rem(total, rtime, &rem);
-		scaled = div64_u64(stime, res);
-		scaled -= div64_u64(scaled * rem, total);
+	/*
+	 * 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;
+	
+	/*
+	 * 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;
 }
 
 /*