[PATCH resend4 2/3] itimers: fix periodic tics precision

[PATCH resend4 2/3] itimers: fix periodic tics precision

[Stanislaw Gruszka]

Measure ITIMER_PROF and ITIMER_VIRT timers interval error between real ticks
and requested by user. Take it into account when scheduling next tick.

This patch introduce possibility where time between two consecutive tics is
smaller then requested interval, it preserve however dependency that n tick
is generated not earlier than n*interval time - counting from the beginning
of periodic signal generation.

Signed-off-by: Stanislaw Gruszka <sgruszka@redhat.com>
---
Compared to previous patch Thomas idea of calculating ticks is used. I'm not
using ktime anymore as all calculations can be done in 32 bits.

 include/linux/sched.h     |    2 ++
 kernel/itimer.c           |   21 ++++++++++++++++++---
 kernel/posix-cpu-timers.c |   20 +++++++++++++++++---
 3 files changed, 37 insertions(+), 6 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index a29aab8..237542a 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -457,6 +457,8 @@ struct pacct_struct {
 struct cpu_itimer {
 	cputime_t expires;
 	cputime_t incr;
+	u32 error;
+	u32 incr_error;
 };
 
 /**
diff --git a/kernel/itimer.c b/kernel/itimer.c
index 852c88d..c645793 100644
--- a/kernel/itimer.c
+++ b/kernel/itimer.c
@@ -42,7 +42,7 @@ static struct timeval itimer_get_remtime(struct hrtimer *timer)
 }
 
 static void get_cpu_itimer(struct task_struct *tsk, unsigned int clock_id,
-			   struct itimerval *value)
+			   struct itimerval *const value)
 {
 	cputime_t cval, cinterval;
 	struct cpu_itimer *it = &tsk->signal->it[clock_id];
@@ -127,14 +127,29 @@ enum hrtimer_restart it_real_fn(struct hrtimer *timer)
 	return HRTIMER_NORESTART;
 }
 
+#define CPUTIME_SUB_NS(ct, real_ns) ({ 		\
+	struct timespec ts;			\
+	s64 cpu_ns;				\
+	cputime_to_timespec(ct, &ts); 		\
+	cpu_ns = timespec_to_ns(&ts);		\
+	cpu_ns - real_ns;	 		\
+})
+
 static void set_cpu_itimer(struct task_struct *tsk, unsigned int clock_id,
-			   struct itimerval *value, struct itimerval *ovalue)
+			   const struct itimerval *const value,
+			   struct itimerval *const ovalue)
 {
-	cputime_t cval, cinterval, nval, ninterval;
+	cputime_t cval, nval, cinterval, ninterval;
+	s64 ns_ninterval, ns_nval;
 	struct cpu_itimer *it = &tsk->signal->it[clock_id];
 
 	nval = timeval_to_cputime(&value->it_value);
+	ns_nval = timeval_to_ns(&value->it_value);
 	ninterval = timeval_to_cputime(&value->it_interval);
+	ns_ninterval = timeval_to_ns(&value->it_interval);
+
+	it->incr_error = CPUTIME_SUB_NS(ninterval, ns_ninterval);
+	it->error = CPUTIME_SUB_NS(nval, ns_nval);
 
 	spin_lock_irq(&tsk->sighand->siglock);
 
diff --git a/kernel/posix-cpu-timers.c b/kernel/posix-cpu-timers.c
index 9b2d5e4..b60d644 100644
--- a/kernel/posix-cpu-timers.c
+++ b/kernel/posix-cpu-timers.c
@@ -1070,6 +1070,8 @@ static void stop_process_timers(struct task_struct *tsk)
 	spin_unlock_irqrestore(&cputimer->lock, flags);
 }
 
+static u32 onecputick;
+
 static void check_cpu_itimer(struct task_struct *tsk, struct cpu_itimer *it,
 			     cputime_t *expires, cputime_t cur_time, int signo)
 {
@@ -1077,9 +1079,16 @@ static void check_cpu_itimer(struct task_struct *tsk, struct cpu_itimer *it,
 		return;
 
 	if (cputime_ge(cur_time, it->expires)) {
-		it->expires = it->incr;
-		if (!cputime_eq(it->expires, cputime_zero))
-			it->expires = cputime_add(it->expires, cur_time);
+		if (!cputime_eq(it->incr, cputime_zero)) {
+			it->expires = cputime_add(it->expires, it->incr);
+			it->error += it->incr_error;
+			if (it->error >= onecputick) {
+				it->expires = cputime_sub(it->expires,
+							jiffies_to_cputime(1));
+				it->error -= onecputick;
+			}
+		} else
+			it->expires = cputime_zero;
 
 		__group_send_sig_info(signo, SEND_SIG_PRIV, tsk);
 	}
@@ -1696,10 +1705,15 @@ static __init int init_posix_cpu_timers(void)
 		.nsleep = thread_cpu_nsleep,
 		.nsleep_restart = thread_cpu_nsleep_restart,
 	};
+	struct timespec ts;
 
 	register_posix_clock(CLOCK_PROCESS_CPUTIME_ID, &process);
 	register_posix_clock(CLOCK_THREAD_CPUTIME_ID, &thread);
 
+	cputime_to_timespec(jiffies_to_cputime(1), &ts);
+	onecputick = ts.tv_nsec;
+	WARN_ON(ts.tv_sec != 0);
+
 	return 0;
 }
 __initcall(init_posix_cpu_timers);
-- 
1.5.5.6

Re: [PATCH resend4 2/3] itimers: fix periodic tics precision

[Thomas Gleixner]

On Fri, 22 May 2009, Stanislaw Gruszka wrote:
>  
> +#define CPUTIME_SUB_NS(ct, real_ns) ({ 		\
> +	struct timespec ts;			\
> +	s64 cpu_ns;				\
> +	cputime_to_timespec(ct, &ts); 		\
> +	cpu_ns = timespec_to_ns(&ts);		\
> +	cpu_ns - real_ns;	 		\
> +})
> +

  Please make this an inline function. Also this should have a sanity
  check for values < 0, which might happen due to rounding errors. In
  that case you set it simply to 0.

>  	if (cputime_ge(cur_time, it->expires)) {
> -		it->expires = it->incr;
> -		if (!cputime_eq(it->expires, cputime_zero))
> -			it->expires = cputime_add(it->expires, cur_time);
> +		if (!cputime_eq(it->incr, cputime_zero)) {
> +			it->expires = cputime_add(it->expires, it->incr);
> +			it->error += it->incr_error;
> +			if (it->error >= onecputick) {
> +				it->expires = cputime_sub(it->expires,
> +							jiffies_to_cputime(1));
> +				it->error -= onecputick;
> +			}

  Yep, that's a sane solution except for jiffies_to_cputime(), which
  can be precomputed as well.

Thanks,

	tglx

Re: [PATCH resend4 2/3] itimers: fix periodic tics precision

[Stanislaw Gruszka]

On Fri, 22 May 2009 16:27:40 +0200 (CEST)
Thomas Gleixner <tglx@linutronix.de> wrote:

> On Fri, 22 May 2009, Stanislaw Gruszka wrote:
> >  
> > +#define CPUTIME_SUB_NS(ct, real_ns) ({ 		\
> > +	struct timespec ts;			\
> > +	s64 cpu_ns;				\
> > +	cputime_to_timespec(ct, &ts); 		\
> > +	cpu_ns = timespec_to_ns(&ts);		\
> > +	cpu_ns - real_ns;	 		\
> > +})
> > +
> 
>   Please make this an inline function. Also this should have a sanity
>   check for values < 0, which might happen due to rounding errors. In
>   that case you set it simply to 0.

Ok.

 
> >  	if (cputime_ge(cur_time, it->expires)) {
> > -		it->expires = it->incr;
> > -		if (!cputime_eq(it->expires, cputime_zero))
> > -			it->expires = cputime_add(it->expires, cur_time);
> > +		if (!cputime_eq(it->incr, cputime_zero)) {
> > +			it->expires = cputime_add(it->expires, it->incr);
> > +			it->error += it->incr_error;
> > +			if (it->error >= onecputick) {
> > +				it->expires = cputime_sub(it->expires,
> > +							jiffies_to_cputime(1));
> > +				it->error -= onecputick;
> > +			}
> 
>   Yep, that's a sane solution except for jiffies_to_cputime(), which
>   can be precomputed as well.

Ok, I forgot PPC exist.

Thanks
Stanislaw

Re: [PATCH resend4 2/3] itimers: fix periodic tics precision

[Stanislaw Gruszka]

(linuxppc-dev CC added)

On Fri, 22 May 2009 16:27:40 +0200 (CEST)
Thomas Gleixner <tglx@linutronix.de> wrote:

> >  	if (cputime_ge(cur_time, it->expires)) {
> > -		it->expires = it->incr;
> > -		if (!cputime_eq(it->expires, cputime_zero))
> > -			it->expires = cputime_add(it->expires, cur_time);
> > +		if (!cputime_eq(it->incr, cputime_zero)) {
> > +			it->expires = cputime_add(it->expires, it->incr);
> > +			it->error += it->incr_error;
> > +			if (it->error >= onecputick) {
> > +				it->expires = cputime_sub(it->expires,
> > +							jiffies_to_cputime(1));
> > +				it->error -= onecputick;
> > +			}
> 
>   Yep, that's a sane solution except for jiffies_to_cputime(), which
>   can be precomputed as well.

I think precomputed is only needed for PPC where jiffies_to_cputime(1) is not
compile time constant. To not affect other architectures, I wrote a patch with
cputime_one value, it is global variable for PPC and preprocessor definition
for others. This patch is against current Linus' tree. I send it as RFC, it
was only compile tested for x86.

diff --git a/arch/ia64/include/asm/cputime.h b/arch/ia64/include/asm/cputime.h
index d20b998..df88b07 100644
--- a/arch/ia64/include/asm/cputime.h
+++ b/arch/ia64/include/asm/cputime.h
@@ -30,6 +30,7 @@ typedef u64 cputime_t;
 typedef u64 cputime64_t;
 
 #define cputime_zero			((cputime_t)0)
+#define cputime_one			jiffies_to_cputime(1)
 #define cputime_max			((~((cputime_t)0) >> 1) - 1)
 #define cputime_add(__a, __b)		((__a) +  (__b))
 #define cputime_sub(__a, __b)		((__a) -  (__b))
diff --git a/arch/powerpc/include/asm/cputime.h b/arch/powerpc/include/asm/cputime.h
index f42e623..e57f951 100644
--- a/arch/powerpc/include/asm/cputime.h
+++ b/arch/powerpc/include/asm/cputime.h
@@ -48,6 +48,8 @@ typedef u64 cputime64_t;
 
 #ifdef __KERNEL__
 
+extern cputime_t cputime_one;
+
 /*
  * Convert cputime <-> jiffies
  */
diff --git a/arch/powerpc/kernel/time.c b/arch/powerpc/kernel/time.c
index 48571ac..e46e210 100644
--- a/arch/powerpc/kernel/time.c
+++ b/arch/powerpc/kernel/time.c
@@ -498,6 +498,7 @@ static int __init iSeries_tb_recal(void)
 				tb_to_xs = divres.result_low;
 				vdso_data->tb_ticks_per_sec = tb_ticks_per_sec;
 				vdso_data->tb_to_xs = tb_to_xs;
+				cputime_one = jiffies_to_cputime(1);
 			}
 			else {
 				printk( "Titan recalibrate: FAILED (difference > 4 percent)\n"
@@ -904,6 +905,7 @@ void __init time_init(void)
 	tb_ticks_per_usec = ppc_tb_freq / 1000000;
 	tb_to_us = mulhwu_scale_factor(ppc_tb_freq, 1000000);
 	calc_cputime_factors();
+	cputime_one = jiffies_to_cputime(1);
 
 	/*
 	 * Calculate the length of each tick in ns.  It will not be
diff --git a/arch/s390/include/asm/cputime.h b/arch/s390/include/asm/cputime.h
index 941384f..f7bbdc9 100644
--- a/arch/s390/include/asm/cputime.h
+++ b/arch/s390/include/asm/cputime.h
@@ -39,6 +39,7 @@ __div(unsigned long long n, unsigned int base)
 #endif /* __s390x__ */
 
 #define cputime_zero			(0ULL)
+#define cputime_one			jiffies_to_cputime(1)
 #define cputime_max			((~0UL >> 1) - 1)
 #define cputime_add(__a, __b)		((__a) +  (__b))
 #define cputime_sub(__a, __b)		((__a) -  (__b))
diff --git a/include/asm-generic/cputime.h b/include/asm-generic/cputime.h
index 1c1fa42..f2b18be 100644
--- a/include/asm-generic/cputime.h
+++ b/include/asm-generic/cputime.h
@@ -7,6 +7,7 @@
 typedef unsigned long cputime_t;
 
 #define cputime_zero			(0UL)
+#define cputime_one			(1UL)
 #define cputime_max			((~0UL >> 1) - 1)
 #define cputime_add(__a, __b)		((__a) +  (__b))
 #define cputime_sub(__a, __b)		((__a) -  (__b))
diff --git a/kernel/itimer.c b/kernel/itimer.c
index 58762f7..ba378c6 100644
--- a/kernel/itimer.c
+++ b/kernel/itimer.c
@@ -65,7 +65,7 @@ int do_getitimer(int which, struct itimerval *value)
 			thread_group_cputimer(tsk, &cputime);
 			utime = cputime.utime;
 			if (cputime_le(cval, utime)) { /* about to fire */
-				cval = jiffies_to_cputime(1);
+				cval = cputime_one;
 			} else {
 				cval = cputime_sub(cval, utime);
 			}
@@ -85,7 +85,7 @@ int do_getitimer(int which, struct itimerval *value)
 			thread_group_cputimer(tsk, &times);
 			ptime = cputime_add(times.utime, times.stime);
 			if (cputime_le(cval, ptime)) { /* about to fire */
-				cval = jiffies_to_cputime(1);
+				cval = cputime_one;
 			} else {
 				cval = cputime_sub(cval, ptime);
 			}
@@ -182,8 +182,7 @@ again:
 		if (!cputime_eq(cval, cputime_zero) ||
 		    !cputime_eq(nval, cputime_zero)) {
 			if (cputime_gt(nval, cputime_zero))
-				nval = cputime_add(nval,
-						   jiffies_to_cputime(1));
+				nval = cputime_add(nval, cputime_one);
 			set_process_cpu_timer(tsk, CPUCLOCK_VIRT,
 					      &nval, &cval);
 		}
@@ -204,8 +203,7 @@ again:
 		if (!cputime_eq(cval, cputime_zero) ||
 		    !cputime_eq(nval, cputime_zero)) {
 			if (cputime_gt(nval, cputime_zero))
-				nval = cputime_add(nval,
-						   jiffies_to_cputime(1));
+				nval = cputime_add(nval, cputime_one);
 			set_process_cpu_timer(tsk, CPUCLOCK_PROF,
 					      &nval, &cval);
 		}
diff --git a/kernel/posix-cpu-timers.c b/kernel/posix-cpu-timers.c
index bece7c0..a86333c 100644
--- a/kernel/posix-cpu-timers.c
+++ b/kernel/posix-cpu-timers.c
@@ -1456,7 +1456,7 @@ void set_process_cpu_timer(struct task_struct *tsk, unsigned int clock_idx,
 		if (!cputime_eq(*oldval, cputime_zero)) {
 			if (cputime_le(*oldval, now.cpu)) {
 				/* Just about to fire. */
-				*oldval = jiffies_to_cputime(1);
+				*oldval = cputime_one;
 			} else {
 				*oldval = cputime_sub(*oldval, now.cpu);
 			}
diff --git a/kernel/sched.c b/kernel/sched.c
index 26efa47..b17fe3c 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -4726,17 +4726,16 @@ void account_idle_time(cputime_t cputime)
  */
 void account_process_tick(struct task_struct *p, int user_tick)
 {
-	cputime_t one_jiffy = jiffies_to_cputime(1);
-	cputime_t one_jiffy_scaled = cputime_to_scaled(one_jiffy);
+	cputime_t one_jiffy_scaled = cputime_to_scaled(cputime_one);
 	struct rq *rq = this_rq();
 
 	if (user_tick)
-		account_user_time(p, one_jiffy, one_jiffy_scaled);
+		account_user_time(p, cputime_one, one_jiffy_scaled);
 	else if ((p != rq->idle) || (irq_count() != HARDIRQ_OFFSET))
-		account_system_time(p, HARDIRQ_OFFSET, one_jiffy,
+		account_system_time(p, HARDIRQ_OFFSET, cputime_one,
 				    one_jiffy_scaled);
 	else
-		account_idle_time(one_jiffy);
+		account_idle_time(cputime_one);
 }
 
 /*

Re: [PATCH resend4 2/3] itimers: fix periodic tics precision

[Thomas Gleixner]

On Mon, 25 May 2009, Stanislaw Gruszka wrote:
> @@ -904,6 +905,7 @@ void __init time_init(void)
>  	tb_ticks_per_usec = ppc_tb_freq / 1000000;
>  	tb_to_us = mulhwu_scale_factor(ppc_tb_freq, 1000000);
>  	calc_cputime_factors();
> +	cputime_one = jiffies_to_cputime(1);

  1) The variable name is misleading.

  2) The patch breaks all powerpc platforms which have
  CONFIG_VIRT_CPU_ACCOUNTING=n and ia64 with
  CONFIG_VIRT_CPU_ACCOUNTING=y

Thanks,

	tglx

Re: [PATCH resend4 2/3] itimers: fix periodic tics precision

[Stanislaw Gruszka]

On Mon, 25 May 2009 14:32:14 +0200 (CEST)
Thomas Gleixner <tglx@linutronix.de> wrote:

> On Mon, 25 May 2009, Stanislaw Gruszka wrote:
> > @@ -904,6 +905,7 @@ void __init time_init(void)
> >  	tb_ticks_per_usec = ppc_tb_freq / 1000000;
> >  	tb_to_us = mulhwu_scale_factor(ppc_tb_freq, 1000000);
> >  	calc_cputime_factors();
> > +	cputime_one = jiffies_to_cputime(1);
> 
>   1) The variable name is misleading.

What about cputime_one_jiffy ?

>   2) The patch breaks all powerpc platforms which have
>   CONFIG_VIRT_CPU_ACCOUNTING=n and ia64 with
>   CONFIG_VIRT_CPU_ACCOUNTING=y

Stupid me, in asm-generic/cputime.h should be 
#define cputime_one jiffies_to_cputime(1)

Thanks
Stanislaw

Re: [PATCH resend4 2/3] itimers: fix periodic tics precision

[Stanislaw Gruszka]

On Mon, 25 May 2009 14:51:32 +0200
Stanislaw Gruszka <sgruszka@redhat.com> wrote:

> On Mon, 25 May 2009 14:32:14 +0200 (CEST)
> Thomas Gleixner <tglx@linutronix.de> wrote:
> 
> > On Mon, 25 May 2009, Stanislaw Gruszka wrote:
> > > @@ -904,6 +905,7 @@ void __init time_init(void)
> > >  	tb_ticks_per_usec = ppc_tb_freq / 1000000;
> > >  	tb_to_us = mulhwu_scale_factor(ppc_tb_freq, 1000000);
> > >  	calc_cputime_factors();
> > > +	cputime_one = jiffies_to_cputime(1);
> > 
> >   1) The variable name is misleading.
> 
> What about cputime_one_jiffy ?
> 
> >   2) The patch breaks all powerpc platforms which have
> >   CONFIG_VIRT_CPU_ACCOUNTING=n and ia64 with
> >   CONFIG_VIRT_CPU_ACCOUNTING=y
> 
> Stupid me, in asm-generic/cputime.h should be 
> #define cputime_one jiffies_to_cputime(1)

Hmmm, I'm confused. Perhaps I missed something, but I think patch was ok.
For powerpc and ia64 and CONFIG_VIRT_CPU_ACCOUNTING=n definitions from
asm-generic/cputime.h where used. In this file was:

#define cputime_one (1UL) 

and that correct as jiffies_to_cputime(x) is just (x)

For CONFIG_VIRT_CPU_ACCOUTING=y:
- For powerpc additional variable was  declared and computed in
  initialization  time. Declaration of was in __KERENEL__ scope.
- For ia64: cputime_one was defined as jiffies_to_cputime(1)

Anyway I didn't try to even compile the patch on other architectures than x86.
Of cource I will test my patch, but first I would like to know what You think?
Does we really need such optimization (because before usage of
jiffies_to_cputime(1) was just fine) ?

Cheers
Stanislaw

Re: [PATCH resend4 2/3] itimers: fix periodic tics precision

[Thomas Gleixner]

On Tue, 26 May 2009, Stanislaw Gruszka wrote:
> On Mon, 25 May 2009 14:51:32 +0200
> Stanislaw Gruszka <sgruszka@redhat.com> wrote:
> 
> > On Mon, 25 May 2009 14:32:14 +0200 (CEST)
> > Thomas Gleixner <tglx@linutronix.de> wrote:
> > 
> > > On Mon, 25 May 2009, Stanislaw Gruszka wrote:
> > > > @@ -904,6 +905,7 @@ void __init time_init(void)
> > > >  	tb_ticks_per_usec = ppc_tb_freq / 1000000;
> > > >  	tb_to_us = mulhwu_scale_factor(ppc_tb_freq, 1000000);
> > > >  	calc_cputime_factors();
> > > > +	cputime_one = jiffies_to_cputime(1);
> > > 
> > >   1) The variable name is misleading.
> > 
> > What about cputime_one_jiffy ?
> > 
> > >   2) The patch breaks all powerpc platforms which have
> > >   CONFIG_VIRT_CPU_ACCOUNTING=n and ia64 with
> > >   CONFIG_VIRT_CPU_ACCOUNTING=y
> > 
> > Stupid me, in asm-generic/cputime.h should be 
> > #define cputime_one jiffies_to_cputime(1)
> 
> Hmmm, I'm confused. Perhaps I missed something, but I think patch was ok.
> For powerpc and ia64 and CONFIG_VIRT_CPU_ACCOUNTING=n definitions from
> asm-generic/cputime.h where used. In this file was:
> 
> #define cputime_one (1UL) 

  In time_init you add unconditionally:

> > > > @@ -904,6 +905,7 @@ void __init time_init(void)
> > > >         tb_ticks_per_usec = ppc_tb_freq / 1000000;
> > > >         tb_to_us = mulhwu_scale_factor(ppc_tb_freq, 1000000);
> > > >         calc_cputime_factors();
> > > > +       cputime_one = jiffies_to_cputime(1);

  I doubt that the compiler will happy about that as it expands to

      (1UL) = jiffies_to_cputime(1)
  or 
      jiffies_to_cputime(1) = jiffies_to_cputime(1)

  in the CONFIG_VIRT_CPU_ACCOUTING=n case.
 
> and that correct as jiffies_to_cputime(x) is just (x)
> 
> For CONFIG_VIRT_CPU_ACCOUTING=y:
> - For powerpc additional variable was  declared and computed in
>   initialization  time. Declaration of was in __KERENEL__ scope.
> - For ia64: cputime_one was defined as jiffies_to_cputime(1)

  My bad, I missed the ia64 hunk.
 
> Does we really need such optimization (because before usage of
> jiffies_to_cputime(1) was just fine) ?

Well, there is a subtle difference between working and nobody noticing
the overhead.

If we notice such heavy instructions in a code path we change then
ignoring the optimization with the argument that it worked before is
just plain wrong.

Thanks,

	tglx