[PATCH] posix-cpu-timers and cputime_t divisons.

The posix cpu timers introduced code that will not work with an arbitrary
type for cputime_t.  In particular the division of two cputime_t values
broke the s390 build because cputime_t is define as an unsigned long long.

The first problem is the division of a cputime_t value by a number of
threads.  That is a cputime_t divided by an integer.  The patch adds
another macro cputime_div to the cputime macro regime which implements this
type of division and replaces all occurences of a cputime / nthread in the
posix cpu timer code.

Next problem is bump_cpu_timer. This function is severly broken:

1) In the body of the first if statement a timer->it.cpu.incr.sched is
   used as the second argument of do_div.  do_div expects an unsigned long
   as "base" parameter but timer->it.cpu.incr.sched is an unsigned long
   long.  If the timer increment ever happens to be >= 2^32 the result is
   wrong and if the lower 32 bits are zero this even crashes with a fixed
   point divide exception.

2) The cputime_le(now.cpu, timer->it.cpu.expires.cpu) in the else if
   condition is wrong.  The cputime_le() reads as "now.cpu <=
   timer->it.cpu.expires.cpu" and the subsequent cputime_ge() reads as
   "now.cpu >= timer.it.cpu.expires.cpu".  That means that the two values
   needs to be equal to make the body of the second if to have any effect. 
   The first cputime_le should be a cputime_ge.

3) timer->it.cpu.expires.cpu and delta in the else part of the if are of
   type cputime_t.  A division of two cputime_t values is undefined (think
   of cputime_t as e.g.  a struct timespec, that just doesn't work).  We
   could add a primitive for this type of division but we'd end up with a
   64 bit division or something even more complicated.

The solution for bump_cpu_timer is to use the "slow" division algorithm
that does shifts and subtracts.  That adds yet another cputime macro,
cputime_halve to do the right shift of a cputime value.

The next problem is in arm_timer.  The UPDATE_CLOCK macro does the wrong
thing for it_prof_expires and it_virt_expires.  Expanded the macro and
added the cputime magic to it_prof/it_virt.

The remaining problems are rather simple, timespec_to_jiffies instead of
timespec_to_cputime and several cases where cputime_eq with cputime_zero
needs to be used instead of "== 0".

What still worries me a bit is to use "timer->it.cpu.incr.sched == 0" as
check if the timer is armed at all.  It should work but its not really
clean.

Signed-off-by: Martin Schwidefsky <schwidefsky@de.ibm.com>
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>

1 files changed, 67 insertions, 39 deletions

diff --git a/kernel/posix-cpu-timers.c b/kernel/posix-cpu-timers.c
index 5dfd280631ae..ad85d3f0dcc4 100644
--- a/kernel/posix-cpu-timers.c
+++ b/kernel/posix-cpu-timers.c
@@ -38,7 +38,7 @@ timespec_to_sample(clockid_t which_clock, const struct timespec *tp)
 	if (CPUCLOCK_WHICH(which_clock) == CPUCLOCK_SCHED) {
 		ret.sched = tp->tv_sec * NSEC_PER_SEC + tp->tv_nsec;
 	} else {
-		ret.cpu = timespec_to_jiffies(tp);
+		ret.cpu = timespec_to_cputime(tp);
 	}
 	return ret;
 }
@@ -94,28 +94,46 @@ static inline union cpu_time_count cpu_time_sub(clockid_t which_clock,
 static inline void bump_cpu_timer(struct k_itimer *timer,
 				  union cpu_time_count now)
 {
+	int i;
+
 	if (timer->it.cpu.incr.sched == 0)
 		return;
 
 	if (CPUCLOCK_WHICH(timer->it_clock) == CPUCLOCK_SCHED) {
-		long long delta;
-		delta = now.sched - timer->it.cpu.expires.sched;
-		if (delta >= 0) {
-			do_div(delta, timer->it.cpu.incr.sched);
-			delta++;
-			timer->it.cpu.expires.sched +=
-				delta * timer->it.cpu.incr.sched;
-			timer->it_overrun += (int) delta;
+		unsigned long long delta, incr;
+
+		if (now.sched < timer->it.cpu.expires.sched)
+			return;
+		incr = timer->it.cpu.incr.sched;
+		delta = now.sched + incr - timer->it.cpu.expires.sched;
+		/* Don't use (incr*2 < delta), incr*2 might overflow. */
+		for (i = 0; incr < delta - incr; i++)
+			incr = incr << 1;
+		for (; i >= 0; incr >>= 1, i--) {
+			if (delta <= incr)
+				continue;
+			timer->it.cpu.expires.sched += incr;
+			timer->it_overrun += 1 << i;
+			delta -= incr;
 		}
-	} else if (cputime_le(now.cpu, timer->it.cpu.expires.cpu)) {
-		cputime_t delta = cputime_sub(now.cpu,
-					      timer->it.cpu.expires.cpu);
-		if (cputime_ge(delta, cputime_zero)) {
-			long orun = 1 + (delta / timer->it.cpu.incr.cpu);
+	} else {
+		cputime_t delta, incr;
+
+		if (cputime_lt(now.cpu, timer->it.cpu.expires.cpu))
+			return;
+		incr = timer->it.cpu.incr.cpu;
+		delta = cputime_sub(cputime_add(now.cpu, incr),
+				    timer->it.cpu.expires.cpu);
+		/* Don't use (incr*2 < delta), incr*2 might overflow. */
+		for (i = 0; cputime_lt(incr, cputime_sub(delta, incr)); i++)
+			     incr = cputime_add(incr, incr);
+		for (; i >= 0; incr = cputime_halve(incr), i--) {
+			if (cputime_le(delta, incr))
+				continue;
 			timer->it.cpu.expires.cpu =
-				cputime_add(timer->it.cpu.expires.cpu,
-					    orun * timer->it.cpu.incr.cpu);
-			timer->it_overrun += orun;
+				cputime_add(timer->it.cpu.expires.cpu, incr);
+			timer->it_overrun += 1 << i;
+			delta = cputime_sub(delta, incr);
 		}
 	}
 }
@@ -479,8 +497,8 @@ static void process_timer_rebalance(struct task_struct *p,
 		BUG();
 		break;
 	case CPUCLOCK_PROF:
-		left = cputime_sub(expires.cpu, val.cpu)
-			/ nthreads;
+		left = cputime_div(cputime_sub(expires.cpu, val.cpu),
+				   nthreads);
 		do {
 			if (!unlikely(t->exit_state)) {
 				ticks = cputime_add(prof_ticks(t), left);
@@ -494,8 +512,8 @@ static void process_timer_rebalance(struct task_struct *p,
 		} while (t != p);
 		break;
 	case CPUCLOCK_VIRT:
-		left = cputime_sub(expires.cpu, val.cpu)
-			/ nthreads;
+		left = cputime_div(cputime_sub(expires.cpu, val.cpu),
+				   nthreads);
 		do {
 			if (!unlikely(t->exit_state)) {
 				ticks = cputime_add(virt_ticks(t), left);
@@ -587,17 +605,25 @@ static void arm_timer(struct k_itimer *timer, union cpu_time_count now)
 			switch (CPUCLOCK_WHICH(timer->it_clock)) {
 			default:
 				BUG();
-#define UPDATE_CLOCK(WHICH, c, n)			      		      \
-			case CPUCLOCK_##WHICH: 				      \
-				if (p->it_##c##_expires == 0 ||		      \
-				    p->it_##c##_expires > nt->expires.n) {    \
-					p->it_##c##_expires = nt->expires.n;  \
-				}					      \
-				break
-			UPDATE_CLOCK(PROF, prof, cpu);
-			UPDATE_CLOCK(VIRT, virt, cpu);
-			UPDATE_CLOCK(SCHED, sched, sched);
-#undef UPDATE_CLOCK
+			case CPUCLOCK_PROF:
+				if (cputime_eq(p->it_prof_expires,
+					       cputime_zero) ||
+				    cputime_gt(p->it_prof_expires,
+					       nt->expires.cpu))
+					p->it_prof_expires = nt->expires.cpu;
+				break;
+			case CPUCLOCK_VIRT:
+				if (cputime_eq(p->it_virt_expires,
+					       cputime_zero) ||
+				    cputime_gt(p->it_virt_expires,
+					       nt->expires.cpu))
+					p->it_virt_expires = nt->expires.cpu;
+				break;
+			case CPUCLOCK_SCHED:
+				if (p->it_sched_expires == 0 ||
+				    p->it_sched_expires > nt->expires.sched)
+					p->it_sched_expires = nt->expires.sched;
+				break;
 			}
 		} else {
 			/*
@@ -934,7 +960,7 @@ static void check_thread_timers(struct task_struct *tsk,
 {
 	struct list_head *timers = tsk->cpu_timers;
 
-	tsk->it_prof_expires = 0;
+	tsk->it_prof_expires = cputime_zero;
 	while (!list_empty(timers)) {
 		struct cpu_timer_list *t = list_entry(timers->next,
 						      struct cpu_timer_list,
@@ -948,7 +974,7 @@ static void check_thread_timers(struct task_struct *tsk,
 	}
 
 	++timers;
-	tsk->it_virt_expires = 0;
+	tsk->it_virt_expires = cputime_zero;
 	while (!list_empty(timers)) {
 		struct cpu_timer_list *t = list_entry(timers->next,
 						      struct cpu_timer_list,
@@ -1044,7 +1070,7 @@ static void check_process_timers(struct task_struct *tsk,
 	}
 
 	++timers;
-	sched_expires = cputime_zero;
+	sched_expires = 0;
 	while (!list_empty(timers)) {
 		struct cpu_timer_list *t = list_entry(timers->next,
 						      struct cpu_timer_list,
@@ -1132,9 +1158,11 @@ static void check_process_timers(struct task_struct *tsk,
 		unsigned long long sched_left, sched;
 		const unsigned int nthreads = atomic_read(&sig->live);
 
-		prof_left = cputime_sub(prof_expires,
-					cputime_add(utime, stime)) / nthreads;
-		virt_left = cputime_sub(virt_expires, utime) / nthreads;
+		prof_left = cputime_sub(prof_expires, utime);
+		prof_left = cputime_sub(prof_left, stime);
+		prof_left = cputime_div(prof_left, nthreads);
+		virt_left = cputime_sub(virt_expires, utime);
+		virt_left = cputime_div(virt_left, nthreads);
 		if (sched_expires) {
 			sched_left = sched_expires - sched_time;
 			do_div(sched_left, nthreads);
@@ -1245,7 +1273,7 @@ void run_posix_cpu_timers(struct task_struct *tsk)
 	BUG_ON(!irqs_disabled());
 
 #define UNEXPIRED(clock) \
-		(tsk->it_##clock##_expires == 0 || \
+		(cputime_eq(tsk->it_##clock##_expires, cputime_zero) || \
 		 cputime_lt(clock##_ticks(tsk), tsk->it_##clock##_expires))
 
 	if (UNEXPIRED(prof) && UNEXPIRED(virt) &&