itimer oddness in 2.6.12

itimer oddness in 2.6.12

[Tom Marshall]

[-- Attachment #1: Type: text/plain, Size: 962 bytes --]

The patch to fix "setitimer timer expires too early" is causing issues for
the Helix server.  We have a timer processs that updates the server's
timestamp on an itimer and it expects the signal to be delivered at roughly
the interval retrieved from getitimer.  This is very consistent on every
platform, including Linux up to 2.6.11, but breaks on 2.6.12.  On 2.6.12,
setting the itimer to 10ms and retrieving the actual interval from getitimer
reports 10.998ms, but the timer interrupts are consistently delivered at
roughly 11.998ms.  This behavior was pointed out as problematic in the patch
submission:

  http://www.kernel.org/hg/linux-2.6/?cmd=changeset;node=36e9195dc9f43467671344332f4c342f183647f7

Would it be possible to resolve this discrepancy for 2.6.13?

Please cc: me on replies, I am not subscribed.

-- 
I stayed up all night playing poker with tarot cards.  I got a full
house and four people died.
        -- Steven Wright

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: itimer oddness in 2.6.12

[Paulo Marques]

Tom Marshall wrote:
> The patch to fix "setitimer timer expires too early" is causing issues for
> the Helix server.  We have a timer processs that updates the server's
> timestamp on an itimer and it expects the signal to be delivered at roughly
> the interval retrieved from getitimer.  This is very consistent on every
> platform, including Linux up to 2.6.11, but breaks on 2.6.12.  On 2.6.12,
> setting the itimer to 10ms and retrieving the actual interval from getitimer
> reports 10.998ms, but the timer interrupts are consistently delivered at
> roughly 11.998ms.  

Unfortunately, this is not so clear cut as it seems :(

I tested this on my system again, and if I set the timer to 9900us and 
put the system to some load I get intervals as low as 10022us with a 
vanilla 2.6.12.2 kernel. Removing this patch would cause the system to 
give me 9022us intervals which is just unnacceptable.

The reason this misbehaves in your case is that 10ms is converted into 
11 jiffies. I'm not really an expert in the time subsystem, but I guess 
this happens because 1000HZ aren't _exactly_ 1000HZ, they're probably a 
little more, so to guarantee 10 ms, we need 11 jiffies (or there is a 
bug in the timeval->jiffies conversions).

If HZ is slightly greater than 1000, this means that each tick will come 
in slightly less than 1 ms. Lets assume we want 2 ms intervals:


---|------------|------------|------------|------------|------
     ^          ^                          ^            ^
     0          1                          2            3

If you place your request at instant "1" and the time between ticks is 
slightly less than 1 ms, at instant "2" there is no guarantee that the 
time has ellapsed, only at instant "3" that is 4 ticks away. If you 
place that request at instant "0", you'll get almost 4ms.

So, the fact that 10 ms are converted to 11 jiffies explains why 
getitimer returns 10.998ms.

The fact that you are getting consistently 11.998ms just means that 
either your system is pretty idle, or the process that is requesting 
this timer has a very high priority so that it is able to request the 
timer again right after the timer tick (like in instant "0").

If this process is delayed for some reason and just requests the timer 
in the middle of the tick you would start seing values like 11.5ms.

If 10ms in jiffies would be just 10, then you would see 11ms between 
alarms, and getitimer would report 10ms.

The only way this could be better was if we knew "where" inside the tick 
we were when we set the timer (as discussed in the thread you 
mentioned), but in your case, even this wouldn't help because you're 
requesting a 10ms timer and to absolutely conform to the setitimer 
specification we can't just give you a 9.9ms interval.

Anyway, making the software depend on the time a timer takes to expire 
when the man page states "Timers will never expire before the requested 
time, ... the delivery will be offset by a small time dependent on the 
system loading" doesn't seem like a very robust software design to me...

-- 
Paulo Marques
Software Development Department - Grupo PIE, S.A.
Phone: +351 252 290600, Fax: +351 252 290601
Web: www.grupopie.com

It is a mistake to think you can solve any major problems
just with potatoes.
Douglas Adams

Re: itimer oddness in 2.6.12

[Tom Marshall]

[-- Attachment #1: Type: text/plain, Size: 1863 bytes --]

On Fri, Jul 22, 2005 at 08:21:25PM +0100, Paulo Marques wrote:
> Tom Marshall wrote:
> >The patch to fix "setitimer timer expires too early" is causing issues for
> >the Helix server.  We have a timer processs that updates the server's
> >timestamp on an itimer and it expects the signal to be delivered at roughly
> >the interval retrieved from getitimer.  This is very consistent on every
> >platform, including Linux up to 2.6.11, but breaks on 2.6.12.  On 2.6.12,
> >setting the itimer to 10ms and retrieving the actual interval from 
> >getitimer
> >reports 10.998ms, but the timer interrupts are consistently delivered at
> >roughly 11.998ms.  
> 
> Unfortunately, this is not so clear cut as it seems :(

Yes, I am sure that it is not a simple problem.  I am not a kernel developer
but I imagine that issues such as NTP adjustments would complicate this
issue.  I must also admit that I am not intimately familiar with the POSIX
spec regarding itimers.

Our current code does a setitimer followed by getitimer, then uses the
actual interval retrieved by getitimer to set a global timer delta.  On each
timer signal, it updates the notion of the current time by the timer delta. 
As mentioned, this works on every other platform (Solaris, BSD, HPUX, AIX,
DGUX, IRIX, Tru64, and Linux up to 2.6.11) but breaks on 2.6.12.

This is not an insurmountable problem for userspace.  It can be easily
solved by using gettimeofday in the timer interrupt instead of adding the
delta to the current time blindly.  No big deal.  I just wanted to point
this issue out and ensure that (1) it was a known issue, and (2) it is the
direction that the Linux kernel intends to take.  If so, no big deal and we
can modify the timer code to take that into account.

-- 
Apathy Club meeting this Friday.  If you want to come, you're not invited.

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

[PATCH] Re: itimer oddness in 2.6.12

[George Anzinger]

[-- Attachment #1: Type: text/plain, Size: 2299 bytes --]

Tom Marshall wrote:
> On Fri, Jul 22, 2005 at 08:21:25PM +0100, Paulo Marques wrote:
> 
>>Tom Marshall wrote:
>>
>>>The patch to fix "setitimer timer expires too early" is causing issues for
>>>the Helix server.  We have a timer processs that updates the server's
>>>timestamp on an itimer and it expects the signal to be delivered at roughly
>>>the interval retrieved from getitimer.  This is very consistent on every
>>>platform, including Linux up to 2.6.11, but breaks on 2.6.12.  On 2.6.12,
>>>setting the itimer to 10ms and retrieving the actual interval from 
>>>getitimer
>>>reports 10.998ms, but the timer interrupts are consistently delivered at
>>>roughly 11.998ms.  
>>
>>Unfortunately, this is not so clear cut as it seems :(

Oops!  That patch is wrong.  The +1 should be applied to the initial 
interval _only_.  We KNOW when the repeating intervals start (i.e. at 
the jiffie edge) and don't need to adjust them.  The patch, however, 
incorrectly, rolls them all into one.  The attach patch should fix the 
problem.  Warnning, it compiles and boots, but I have not tested it.

George
-- 
> 
> 
> Yes, I am sure that it is not a simple problem.  I am not a kernel developer
> but I imagine that issues such as NTP adjustments would complicate this
> issue.  I must also admit that I am not intimately familiar with the POSIX
> spec regarding itimers.
> 
> Our current code does a setitimer followed by getitimer, then uses the
> actual interval retrieved by getitimer to set a global timer delta.  On each
> timer signal, it updates the notion of the current time by the timer delta. 
> As mentioned, this works on every other platform (Solaris, BSD, HPUX, AIX,
> DGUX, IRIX, Tru64, and Linux up to 2.6.11) but breaks on 2.6.12.

> 
> This is not an insurmountable problem for userspace.  It can be easily
> solved by using gettimeofday in the timer interrupt instead of adding the
> delta to the current time blindly.  No big deal.  I just wanted to point
> this issue out and ensure that (1) it was a known issue, and (2) it is the
> direction that the Linux kernel intends to take.  If so, no big deal and we
> can modify the timer code to take that into account.
> 

-- 
George Anzinger   george@mvista.com
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/

[-- Attachment #2: itimer.patch --]
[-- Type: text/plain, Size: 3151 bytes --]

Source: MontaVista Software, Inc. <george@mvista.com>
Type: Defect Fix
Disposition: 
Description:

This changes setitimer as follows:
1. The repeating timer is figured using the requested time 
	(not +1 as we know where we are in the jiffie).
2. The tests for interval too large are left to the time_val to jiffie code.


Signed-off-by: George Anzinger <george@mvista.com>
 itimer.c |   37 ++++++++++++++++---------------------
 1 files changed, 16 insertions(+), 21 deletions(-)

Index: linux-2.6.13-rc/kernel/itimer.c
===================================================================
--- linux-2.6.13-rc.orig/kernel/itimer.c
+++ linux-2.6.13-rc/kernel/itimer.c
@@ -112,28 +112,11 @@ asmlinkage long sys_getitimer(int which,
 	return error;
 }
 
-/*
- * Called with P->sighand->siglock held and P->signal->real_timer inactive.
- * If interval is nonzero, arm the timer for interval ticks from now.
- */
-static inline void it_real_arm(struct task_struct *p, unsigned long interval)
-{
-	p->signal->it_real_value = interval; /* XXX unnecessary field?? */
-	if (interval == 0)
-		return;
-	if (interval > (unsigned long) LONG_MAX)
-		interval = LONG_MAX;
-	/* the "+ 1" below makes sure that the timer doesn't go off before
-	 * the interval requested. This could happen if
-	 * time requested % (usecs per jiffy) is more than the usecs left
-	 * in the current jiffy */
-	p->signal->real_timer.expires = jiffies + interval + 1;
-	add_timer(&p->signal->real_timer);
-}
 
 void it_real_fn(unsigned long __data)
 {
 	struct task_struct * p = (struct task_struct *) __data;
+	unsigned long inc = p->signal->it_real_incr;
 
 	send_group_sig_info(SIGALRM, SEND_SIG_PRIV, p);
 
@@ -141,14 +124,23 @@ void it_real_fn(unsigned long __data)
 	 * Now restart the timer if necessary.  We don't need any locking
 	 * here because do_setitimer makes sure we have finished running
 	 * before it touches anything.
+	 * Note, we KNOW we are (or should be) at a jiffie edge here so 
+	 * we don't need the +1 stuff.  Also, we want to use the prior
+	 * expire value so as to not "slip" a jiffie if we are late.
+	 * Deal with requesting a time prior to "now" here rather than
+	 * in add_timer.
 	 */
-	it_real_arm(p, p->signal->it_real_incr);
+	if (!inc)
+		return;
+	while (time_before_eq(p->signal->real_timer.expires, jiffies))
+		p->signal->real_timer.expires += inc;
+	add_timer(&p->signal->real_timer);	
 }
 
 int do_setitimer(int which, struct itimerval *value, struct itimerval *ovalue)
 {
 	struct task_struct *tsk = current;
- 	unsigned long val, interval;
+ 	unsigned long val, interval, expires;
 	cputime_t cval, cinterval, nval, ninterval;
 
 	switch (which) {
@@ -160,7 +152,10 @@ int do_setitimer(int which, struct itime
 			del_timer_sync(&tsk->signal->real_timer);
 		tsk->signal->it_real_incr =
 			timeval_to_jiffies(&value->it_interval);
-		it_real_arm(tsk, timeval_to_jiffies(&value->it_value));
+		expires = timeval_to_jiffies(&value->it_value);
+		if (expires)
+			mod_timer(&tsk->signal->real_timer,
+				  jiffies + 1 + expires);
 		spin_unlock_irq(&tsk->sighand->siglock);
 		if (ovalue) {
 			jiffies_to_timeval(val, &ovalue->it_value);

Re: [PATCH] Re: itimer oddness in 2.6.12

[Paulo Marques]

George Anzinger wrote:
> Tom Marshall wrote:
>> On Fri, Jul 22, 2005 at 08:21:25PM +0100, Paulo Marques wrote:
>>>[...]
>>> Unfortunately, this is not so clear cut as it seems :(
> 
> Oops!  That patch is wrong.  The +1 should be applied to the initial 
> interval _only_.  We KNOW when the repeating intervals start (i.e. at 
> the jiffie edge) and don't need to adjust them.  The patch, however, 
> incorrectly, rolls them all into one.  The attach patch should fix the 
> problem.  Warnning, it compiles and boots, but I have not tested it.

Yes, this seems to be the Right Thing :)

Acked-by: Paulo Marques <pmarques@grupopie.com>

-- 
Paulo Marques - www.grupopie.com

It is a mistake to think you can solve any major problems
just with potatoes.
Douglas Adams

Re: [PATCH] Re: itimer oddness in 2.6.12

[Bill Davidsen]

George Anzinger wrote:
> Tom Marshall wrote:
> 
>> On Fri, Jul 22, 2005 at 08:21:25PM +0100, Paulo Marques wrote:
>>
>>> Tom Marshall wrote:
>>>
>>>> The patch to fix "setitimer timer expires too early" is causing 
>>>> issues for
>>>> the Helix server.  We have a timer processs that updates the server's
>>>> timestamp on an itimer and it expects the signal to be delivered at 
>>>> roughly
>>>> the interval retrieved from getitimer.  This is very consistent on 
>>>> every
>>>> platform, including Linux up to 2.6.11, but breaks on 2.6.12.  On 
>>>> 2.6.12,
>>>> setting the itimer to 10ms and retrieving the actual interval from 
>>>> getitimer
>>>> reports 10.998ms, but the timer interrupts are consistently 
>>>> delivered at
>>>> roughly 11.998ms.  
>>>
>>>
>>> Unfortunately, this is not so clear cut as it seems :(
> 
> 
> Oops!  That patch is wrong.  The +1 should be applied to the initial 
> interval _only_.  We KNOW when the repeating intervals start (i.e. at 
> the jiffie edge) and don't need to adjust them.  The patch, however, 
> incorrectly, rolls them all into one.  The attach patch should fix the 
> problem.  Warnning, it compiles and boots, but I have not tested it.

Can this get into 2.6.13? Or stable if it's too late? This would appear 
to be a fix to a visible problem.

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: [PATCH] Re: itimer oddness in 2.6.12

[Andrew Morton]

George Anzinger <george@mvista.com> wrote:
>
> +	while (time_before_eq(p->signal->real_timer.expires, jiffies))
> +		p->signal->real_timer.expires += inc;

It gives me the creeps when I see timer code doing this, and it seems to be
done relatively frequently.

Surely it can be calculated arithmetically?  If not, are you really sure
that it is not exploitable by malicious code?

Re: [PATCH] Re: itimer oddness in 2.6.12

[George Anzinger]

Andrew Morton wrote:
> George Anzinger <george@mvista.com> wrote:
> 
>>+	while (time_before_eq(p->signal->real_timer.expires, jiffies))
>>+		p->signal->real_timer.expires += inc;
> 
> 
> It gives me the creeps when I see timer code doing this, and it seems to be
> done relatively frequently.
> 
> Surely it can be calculated arithmetically?  If not, are you really sure
> that it is not exploitable by malicious code?

Hm.. the system only falls into a loop here if the system is loaded to 
the point where we are a jiffie or more late.  The prior code just did 
the "+=" and called add_timer, possibly with a time in the past.  I 
suspect that way of doing this would never catch up if the user asked 
for a one jiffie repeat time.  Also, this is faster than the div, mpy if 
you are not late (or even if you are several jiffies late).

A possible alternative might be:
	p->signal->real_timer.expires += inc;	
	if (time_before_eq(p->signal->real_timer.expires, jiffies))
		p->signal->real_timer.expires += ((jiffies - 
p->signal->real_timer.expires + inc -1) / inc) * inc;

Both a div and a mpy in there.  I really think the "while" is ok, but if 
you prefer...	

The last time you questioned this sort of thing was in the code to 
correct an absolute timer.  In that case we were adjusting after a clock 
set and, yes, it was possibly exploitable (assuming you could set the 
clock).  Here we don't have that possibility, i.e. we only get into the 
loop if the system is late.
> -
-- 
George Anzinger   george@mvista.com
HRT (High-res-timers):  http://sourceforge.net/projects/high-res-timers/