sched: prevent compiler from optimising sched_avg_update loop
PATCH 1/1 sched: prevent compiler from optimising sched_avg_update loop
GCC 4.4.1 on ARM has been observed to replace the while loop in sched_avg_update with a call to uldivmod, resulting in the following build failure at link-time:
kernel/built-in.o: In function `sched_avg_update':
/linux-2.6/kernel/sched.c:1261: undefined reference to __aeabi_uldivmod' /linux-2.6/kernel/sched.c:1261: undefined reference to __aeabi_uldivmod'
make: *** [.tmp_vmlinux1] Error 1
This patch [taken against 2.6.34-rc2] replaces the loop with a call to div_s64 which allows the Kernel to link.
--- kernel/sched.c | 7 +++---- 1 files changed, 3 insertions(+), 4 deletions(-)
kernel/sched.c +3 -4
@@ -1238,11 +1238,10 @@ static u64 sched_avg_period(void)static void sched_avg_update (struct rq *rq) {s64 period =sched_avg_period (); +s64 elapsed_periods =div_s64 (rq->clock - rq->age_stamp -1 , period); -while ((s64)(rq->clock - rq->age_stamp) > period) { - rq->age_stamp += period; - rq->rt_avg /=2 ; - } + rq->age_stamp += (u64)(elapsed_periods * period); + rq->rt_avg >>= elapsed_periods; }static void sched_rt_avg_update (struct rq *rq,u64 rt_delta)
Signature · 1 line
1.6.3.3
Quoted 30 lines · Will Deacon
GCC 4.4.1 on ARM has been observed to replace the while loop in
sched_avg_updatewith a call to uldivmod, resulting in the following build failure at link-time:
kernel/built-in.o: In function `sched_avg_update':
/linux-2.6/kernel/sched.c:1261: undefined reference to__aeabi_uldivmod' /linux-2.6/kernel/sched.c:1261: undefined reference to__aeabi_uldivmod'
make: *** [.tmp_vmlinux1] Error 1This patch [taken against 2.6.34-rc2] replaces the loop with a call to
div_s64which allows the Kernel to link.Cc Catalin Marinas <[email protected]>Cc Ingo Molnar <[email protected]>Cc Andrew Morton <[email protected]>Cc Peter Zijlstra <[email protected]>Signed-off-by Will Deacon <[email protected]>--- kernel/sched.c | 7 +++---- 1 files changed, 3 insertions(+), 4 deletions(-)kernel/sched.c +1
-0@@ -1238,11 +1238,10 @@ static u64 sched_avg_period(void)static void sched_avg_update (struct rq *rq) {s64 period =sched_avg_period (); +s64 elapsed_periods =div_s64 (rq->clock - rq->age_stamp -1 , period);
kernel/sched.c static u64 sched_avg_period(void) · line 1247
Quoted 10 lines
kernel/sched.c +2
-4-while ((s64)(rq->clock - rq->age_stamp) > period) { - rq->age_stamp += period; - rq->rt_avg /=2 ; - } + rq->age_stamp += (u64)(elapsed_periods * period); + rq->rt_avg >>= elapsed_periods; }static void sched_rt_avg_update (struct rq *rq,u64 rt_delta)
Please take a look at __iter_div_u64_rem() , because we had a similar problem in the past. We want to avoid this div_s64() call.
A message that is not in the archive (sent off-list or not yet received): 000101cacab3$25af90a0$710eb1e0$@[email protected]
Quoted 27 lines · Will Deacon
Hello Eric,
Thanks for looking at the patch.
Quoted 18 lines
Quoted 18 lines
kernel/sched.c +3
-4@@ -1238,11 +1238,10 @@ static u64 sched_avg_period(void)static void sched_avg_update (struct rq *rq) {s64 period =sched_avg_period (); +s64 elapsed_periods =div_s64 (rq->clock - rq->age_stamp -1 , period); -while ((s64)(rq->clock - rq->age_stamp) > period) { - rq->age_stamp += period; - rq->rt_avg /=2 ; - } + rq->age_stamp += (u64)(elapsed_periods * period); + rq->rt_avg >>= elapsed_periods; }Quoted 4 lines
kernel/sched.c static u64 sched_avg_period(void) · line 1247
Quoted 1 line
kernel/sched.c +0
-0static void sched_rt_avg_update (struct rq *rq,u64 rt_delta)Please take a look at
__iter_div_u64_rem(), because we had a similar problem in the past. We want to avoid thisdiv_s64()call.
Quoted 4 lines
Yes, I saw the inline assembly fix there. I avoided that fix because I was trying not to execute the loop body multiple times. Is the iterative approach preferred over a single call to
div_s64? I don't have a handle on how many iterations are typically executed for this loop.
I expect it to be mostly 0 and occasionally 1 cycle, except when someone pokes at a sysctl with funny values, at which point it might go round much much faster.
Quoted 28 lines · Will Deacon
GCC 4.4.1 on ARM has been observed to replace the while loop in
sched_avg_updatewith a call to uldivmod, resulting in the following build failure at link-time:
kernel/built-in.o: In function `sched_avg_update':
/linux-2.6/kernel/sched.c:1261: undefined reference to__aeabi_uldivmod' /linux-2.6/kernel/sched.c:1261: undefined reference to__aeabi_uldivmod'
make: *** [.tmp_vmlinux1] Error 1This patch [taken against 2.6.34-rc2] replaces the loop with a call to
div_s64which allows the Kernel to link.Cc Catalin Marinas <[email protected]>Cc Ingo Molnar <[email protected]>Cc Andrew Morton <[email protected]>Cc Peter Zijlstra <[email protected]>Signed-off-by Will Deacon <[email protected]>--- kernel/sched.c | 7 +++---- 1 files changed, 3 insertions(+), 4 deletions(-)kernel/sched.c +0
-0@@ -1238,11 +1238,10 @@ static u64 sched_avg_period(void)static void sched_avg_update (struct rq *rq) {
kernel/sched.c static u64 sched_avg_period(void) · line 1245
Quoted 10 lines
kernel/sched.c +3
-4s64 period =sched_avg_period (); +s64 elapsed_periods =div_s64 (rq->clock - rq->age_stamp -1 , period); -while ((s64)(rq->clock - rq->age_stamp) > period) { - rq->age_stamp += period; - rq->rt_avg /=2 ; - } + rq->age_stamp += (u64)(elapsed_periods * period); + rq->rt_avg >>= elapsed_periods; }
Hmm, and that does an unconditional division, thing is, I don't expect (under normal circumstances) for that loop to go round more than once so that division will hurt for no reason.
Should we maybe write it like so:
if ((s64)(rq->clock - rq->age_stamp) > period) {
rq->age_stamp += period;
rq->rt_avg >>= 1;
}
if (unlikely((s64)(rq->clock - rq->age_stamp) > period)) {
s64 overflows = div_s64(rq->clocks - rq->age_stamp, period);
int width = sizeof(rq->rt_avg) * 8; rq->age_stamp += overflows * period;
if (unlikely(overflows >= width))
rq->rt_avg = 0;
else
rq->rt_avg >>= overflows;}
?
PATCH 1/1 sched: prevent compiler from optimising sched_avg_update loop
In reply to Will DeaconGCC 4.4.1 on ARM has been observed to replace the while loop in sched_avg_update with a call to uldivmod, resulting in the following build failure at link-time:
kernel/built-in.o: In function `sched_avg_update':
/linux-2.6/kernel/sched.c:1261: undefined reference to __aeabi_uldivmod' /linux-2.6/kernel/sched.c:1261: undefined reference to __aeabi_uldivmod'
make: *** [.tmp_vmlinux1] Error 1
This patch [taken against 2.6.34-rc2] introduces a fake data hazard to the loop body to prevent the compiler optimising the loop away.
--- kernel/sched.c | 6 ++++++ 1 files changed, 6 insertions(+), 0 deletions(-)
kernel/sched.c +6 -0
@@ -1240,6 +1240,12 @@ static void sched_avg_update(struct rq *rq)s64 period =sched_avg_period ();while ((s64)(rq->clock - rq->age_stamp) > period) { +/* +* Inline assembly required to prevent the compiler +* optimising this loop into a divmod call. +* See __iter_div_u64_rem() for another example of this. +*/ + asm("" :"+rm" (rq->age_stamp)); rq->age_stamp += period; rq->rt_avg /=2 ; }
Signature · 1 line
1.6.3.3