diff options
| -rw-r--r-- | include/linux/math64.h | 19 | ||||
| -rw-r--r-- | kernel/sched/cputime.c | 46 | ||||
| -rw-r--r-- | lib/div64.c | 19 |
3 files changed, 65 insertions, 19 deletions
diff --git a/include/linux/math64.h b/include/linux/math64.h index b8ba855..931a619 100644 --- a/include/linux/math64.h +++ b/include/linux/math64.h @@ -30,6 +30,15 @@ static inline s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder) } /** + * div64_u64_rem - unsigned 64bit divide with 64bit divisor + */ +static inline u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder) +{ + *remainder = dividend % divisor; + return dividend / divisor; +} + +/** * div64_u64 - unsigned 64bit divide with 64bit divisor */ static inline u64 div64_u64(u64 dividend, u64 divisor) @@ -61,8 +70,16 @@ static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder) extern s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder); #endif +#ifndef div64_u64_rem +extern u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder); +#endif + #ifndef div64_u64 -extern u64 div64_u64(u64 dividend, u64 divisor); +static inline u64 div64_u64(u64 dividend, u64 divisor) +{ + u64 remainder; + return div64_u64_rem(dividend, divisor, &remainder); +} #endif #ifndef div64_s64 diff --git a/kernel/sched/cputime.c b/kernel/sched/cputime.c index 024fe19..699d597 100644 --- a/kernel/sched/cputime.c +++ b/kernel/sched/cputime.c @@ -521,18 +521,36 @@ void account_idle_ticks(unsigned long ticks) account_idle_time(jiffies_to_cputime(ticks)); } -static cputime_t scale_stime(cputime_t stime, cputime_t rtime, cputime_t total) +/* + * Perform (stime * rtime) / total with reduced chances + * of multiplication overflows by using smaller factors + * like quotient and remainders of divisions between + * rtime and total. + */ +static cputime_t scale_stime(u64 stime, u64 rtime, u64 total) { - u64 temp = (__force u64) rtime; + u64 rem, res, scaled; - temp *= (__force u64) stime; - - if (sizeof(cputime_t) == 4) - temp = div_u64(temp, (__force u32) total); - else - temp = div64_u64(temp, (__force u64) total); + 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); + } - return (__force cputime_t) temp; + return (__force cputime_t) scaled; } /* @@ -566,10 +584,14 @@ static void cputime_adjust(struct task_cputime *curr, */ rtime = nsecs_to_cputime(curr->sum_exec_runtime); - if (total) - stime = scale_stime(stime, rtime, total); - else + if (!rtime) { + stime = 0; + } else if (!total) { stime = rtime; + } else { + stime = scale_stime((__force u64)stime, + (__force u64)rtime, (__force u64)total); + } /* * If the tick based count grows faster than the scheduler one, diff --git a/lib/div64.c b/lib/div64.c index a163b6c..3af5728 100644 --- a/lib/div64.c +++ b/lib/div64.c @@ -79,9 +79,10 @@ EXPORT_SYMBOL(div_s64_rem); #endif /** - * div64_u64 - unsigned 64bit divide with 64bit divisor + * div64_u64_rem - unsigned 64bit divide with 64bit divisor and 64bit remainder * @dividend: 64bit dividend * @divisor: 64bit divisor + * @remainder: 64bit remainder * * This implementation is a modified version of the algorithm proposed * by the book 'Hacker's Delight'. The original source and full proof @@ -89,27 +90,33 @@ EXPORT_SYMBOL(div_s64_rem); * * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c.txt' */ -#ifndef div64_u64 -u64 div64_u64(u64 dividend, u64 divisor) +#ifndef div64_u64_rem +u64 div64_u64_rem(u64 dividend, u64 divisor, u64 *remainder) { u32 high = divisor >> 32; u64 quot; if (high == 0) { - quot = div_u64(dividend, divisor); + u32 rem32; + quot = div_u64_rem(dividend, divisor, &rem32); + *remainder = rem32; } else { int n = 1 + fls(high); quot = div_u64(dividend >> n, divisor >> n); if (quot != 0) quot--; - if ((dividend - quot * divisor) >= divisor) + + *remainder = dividend - quot * divisor; + if (*remainder >= divisor) { quot++; + *remainder -= divisor; + } } return quot; } -EXPORT_SYMBOL(div64_u64); +EXPORT_SYMBOL(div64_u64_rem); #endif /** |