Skip to contentSkip to conversation

sched: prevent compiler from optimising sched_avg_update loop

PATCH In review Will Deacon 3 participants 5 messages Mar 23, 2010 1 message not in the archive

lore
Share & tools
lore
#0 lore raw

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.

Cc Catalin Marinas <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 kernel/sched.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)
kernel/sched.c +3 -4
index 9ab3cd7..6b74f21 100644
@@ -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
#1 lore raw
Quoted 30 lines · Will Deacon

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.

Cc Catalin Marinas <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 kernel/sched.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)
kernel/sched.c +1 -0
index 9ab3cd7..6b74f21 100644
@@ -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]

#3 lore raw
Quoted 27 lines · Will Deacon

Hello Eric,

Thanks for looking at the patch.

Quoted 18 lines
Quoted 18 lines
kernel/sched.c +3 -4
index 9ab3cd7..6b74f21 100644
@@ -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 -0
 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.

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.

#4 lore raw
In reply to Will Deacon
Quoted 28 lines · Will Deacon

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.

Cc Catalin Marinas <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 kernel/sched.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)
kernel/sched.c +0 -0
index 9ab3cd7..6b74f21 100644
@@ -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 -4
 	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;
 }

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;

}

?

#5 lore raw

PATCH 1/1 sched: prevent compiler from optimising sched_avg_update loop

In reply to Will Deacon

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] introduces a fake data hazard to the loop body to prevent the compiler optimising the loop away.

Cc Catalin Marinas <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Peter Zijlstra <[email protected]>
---
 kernel/sched.c |    6 ++++++
 1 files changed, 6 insertions(+), 0 deletions(-)
kernel/sched.c +6 -0
index 9ab3cd7..0846815 100644
@@ -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