Messages in this thread Patch in this message | | | From | Yuyang Du <> | Subject | [RFC PATCH 5/9] sched/fair: Change the variable to hold the number of periods to 32-bit | Date | Mon, 16 May 2016 02:59:30 +0800 |
| |
In sched average update, a period is about 1ms, so a 32-bit unsigned integer can approximately hold a maximum of 49 (=2^32/1000/3600/24) days.
For usual cases, 32-bit is big enough and 64-bit is needless. But if a task sleeps longer than it, there can be two outcomes:
Consider a task sleeps m milliseconds (m > U32_MAX), let n = (u32)m
1. If n >= 32*64, then the task's sched avgs will be surely decayed to 0. In this case, it really doesn't matter that the 32-bit is not big enough to hold m. In other words, a task sleeps 2 secs or sleeps 50 days are the same from sched average point of view.
2. If n < 32*64, first, the chance to be here is very low, which is about 0.5 in a million (=32*64/2^32), but if so, the task's sched avgs MAY NOT be decayed to 0, depending on how big its sums are, and the chance to 0 is still good as load_sum is way less than ~0ULL and util_sum way less than ~0U.
Nevertheless, what really maters is what happens in the worst-case scenario, which is when (u32)m = 0? So in that case, it would be like after so long a sleep, we treat the task as it never slept, and it has the same sched averages as before. At any rate, it should hurt nothing and there is nothing to worry about.
Signed-off-by: Yuyang Du <yuyang.du@intel.com> --- kernel/sched/fair.c | 31 ++++++++++++++++--------------- 1 file changed, 16 insertions(+), 15 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index fddaa61..1fac2bf 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2617,21 +2617,18 @@ static const u32 __accumulated_sum_N32[] = { /* * val * y^n, where y^m ~= 0.5 * - * n is the number of periods past; a period is ~1ms + * n is the number of periods past. A period is ~1ms, so a 32bit + * integer can hold approximately a maximum of 49 (=2^32/1000/3600/24) days. + * * m is half-life in exponential decay; here it is SCHED_AVG_HALFLIFE=32. */ -static __always_inline u64 __decay_sum(u64 val, u64 n) +static __always_inline u64 __decay_sum(u64 val, u32 n) { - unsigned int local_n; - if (!n) return val; else if (unlikely(n > SCHED_AVG_HALFLIFE * 63)) return 0; - /* after bounds checking we can collapse to 32-bit */ - local_n = n; - /* * As y^HALFLIFE = 1/2, we can combine * y^n = 1/2^(n/HALFLIFE) * y^(n%HALFLIFE) @@ -2639,12 +2636,12 @@ static __always_inline u64 __decay_sum(u64 val, u64 n) * * To achieve constant time __decay_load. */ - if (unlikely(local_n >= SCHED_AVG_HALFLIFE)) { - val >>= local_n / SCHED_AVG_HALFLIFE; - local_n %= SCHED_AVG_HALFLIFE; + if (unlikely(n >= SCHED_AVG_HALFLIFE)) { + val >>= n / SCHED_AVG_HALFLIFE; + n %= SCHED_AVG_HALFLIFE; } - val = mul_u64_u32_shr(val, __decay_inv_multiply_N[local_n], 32); + val = mul_u64_u32_shr(val, __decay_inv_multiply_N[n], 32); return val; } @@ -2655,7 +2652,7 @@ static __always_inline u64 __decay_sum(u64 val, u64 n) * We can compute this efficiently by combining: * y^32 = 1/2 with precomputed \Sum 1024*y^n (where n < 32) */ -static u32 __accumulate_sum(u64 n) +static u32 __accumulate_sum(u32 n) { u32 contrib = 0; @@ -2705,8 +2702,8 @@ static __always_inline int __update_sched_avg(u64 now, int cpu, struct sched_avg *sa, unsigned long weight, int running, struct cfs_rq *cfs_rq) { - u64 delta, scaled_delta, periods; - u32 contrib; + u64 delta, scaled_delta; + u32 contrib, periods; unsigned int delta_w, scaled_delta_w, decayed = 0; unsigned long scale_freq, scale_cpu; @@ -2759,7 +2756,11 @@ __update_sched_avg(u64 now, int cpu, struct sched_avg *sa, delta -= delta_w; - /* Figure out how many additional periods this update spans */ + /* + * Figure out how many additional periods this update spans. + * A period is 1024*1024ns or ~1ms, so a 32bit integer can hold + * approximately a maximum of 49 (=2^32/1000/3600/24) days. + */ periods = delta / 1024; delta %= 1024; -- 1.7.9.5
| |