One possible bugfix for CLOCK_REALTIME timer.

PATCH In review Hu, Boris 3 participants 9 messages Jun 3, 2004 – Jun 30, 2004 Scheduler

lore

Share & tools

lore

Hu, Boris

author

2004-06-03 09:57 UTC #0 lore raw

Thanks for your detailed comments. :)

Quoted 9 lines

Quoted 7 lines · Boris
<<posix-abs_timer-bugfix.diff>> George,
There is one bug of CLOCK_REALTIME timer reported by Adam at
http://sources.redhat.com/ml/libc-alpha/2004-05/msg00177.html.
Here is one possible bugfix and it is against linux-2.6.6. All TIMER_ABSTIME cloks will be collected in k_clock struct and updated

Quoted 7 lines

Quoted 1 line
sys_clock_settime. Could you review it? Thanks.
Thanks for the poke :). Could you make the following changes:
First, put the list in the posix timer structure (k_itimer), not in timer_list.
This means one more dereference when doing things, but it does not

push

Quoted 2 lines

into
the timer_list structure which is mostly used for other things.

Done.

Quoted 2 lines

Second, I don't see the timer being removed from the list (should

happen

Quoted 2 lines

when
ever it is inactive). Timers that repeat should be out of the list

while

Quoted 1 line

waiting for the signal to be picked up and put back in when add_timer

Quoted 2 lines

again
called.

I tried to add the removed codes to set_timer_inactive() but it would trigger a strange oops. I am still investigating on it. Is there any recommending places except set_timer_inactive()?

Quoted 2 lines

Also, you should test to see if the clock is one that can be set prior

Quoted 1 line

putting the timer in the abs timer list. We must not correct timers

Quoted 1 line

CLOCK_MONOTONIC.

Done.

Quoted 2 lines

Now, for the correction. Sys_clock_settime() is the wrong place for

this

Quoted 3 lines

as the
clock can also be set a number of other ways. The right place is in clock_was_set(), which is called if time is set in any of the several

ways.

Quoted 2 lines

The
next thing is to determine how far the clock was moved. I think the

best

Quoted 6 lines

way to
do this is to keep a copy of the wall_to_monotonic var in a private location.
This should be set to be exactly wall_to_monotonic when the system is booted (in
the same function you are setting up the clock lists) and at the end

Quoted 1 line

clock_was_set(). When clock_was_set() is called the difference

between

Quoted 2 lines

this
value and wall_to_monotonic is exactly how far the clock was moved.

(Be

Quoted 3 lines

careful
on the sign of this movement.)

Done.

Quoted 1 line

Finally, be careful about races. Timers can expire while

clock_was_set()

Quoted 4 lines

is
running. The removal code should take the timer lock as well as the abs_time
list lock (at least I think this would be wise, but I could be wrong

here).

Quoted 1 line

IMHO, we need not take the timer locks. We del_timer() first and if the timer has expired, we simply removed it from the abs_timer_list which is protected by abs_timer_lock.

Quoted 1 line

And a minor issue, the community seems to prefer the C comment style

Quoted 3 lines

the C++
style of comments...

Done.

Quoted 16 lines

Thanks for your effort in this matter.
George
Quoted 13 lines
diff -urN -X rt.ia32/base/dontdiff
linux-2.6.6/include/linux/posix-timers.h
linux-2.6.6.dev/include/linux/posix-timers.h
--- linux-2.6.6/include/linux/posix-timers.h 2004-05-10
10:32:29.000000000 +0800
+++ linux-2.6.6.dev/include/linux/posix-timers.h 2004-06-02
10:30:57.000000000 +0800
(quoted diff) +0 -0
@@ -1,9 +1,14 @@
 #ifndef _linux_POSIX_TIMERS_H
 #define _linux_POSIX_TIMERS_H
 

Quoted 15 lines

Quoted 12 lines

(quoted diff) +6 -1

+#include <linux/list.h>
+#include <linux/spinlock.h>
+
 struct k_clock {
 	int res;		/* in nano seconds */
-	int (*clock_set) (struct timespec * tp);
+        struct list_head abs_timer_list;
+        spinlock_t abs_timer_lock;
+        int (*clock_set) (struct timespec * tp);
 	int (*clock_get) (struct timespec * tp);
 	int (*nsleep) (int flags,
 		       struct timespec * new_setting,

Quoted 3 lines

diff -urN -X rt.ia32/base/dontdiff linux-2.6.6/include/linux/timer.h linux-2.6.6.dev/include/linux/timer.h
--- linux-2.6.6/include/linux/timer.h 2004-05-10

10:32:54.000000000

Quoted 10 lines

Quoted 10 lines
+0800
+++ linux-2.6.6.dev/include/linux/timer.h 2004-06-02
19:16:08.000000000 +0800
(quoted diff) +1 -0
@@ -9,6 +9,7 @@
 
 struct timer_list {
 	struct list_head entry;
+	struct list_head abs_timer_entry;
 	unsigned long expires;
 

Quoted 4 lines

Quoted 4 lines
(quoted diff) +0 -0
 	spinlock_t lock;
diff -urN -X rt.ia32/base/dontdiff linux-2.6.6/kernel/posix-timers.c linux-2.6.6.dev/kernel/posix-timers.c
--- linux-2.6.6/kernel/posix-timers.c 2004-05-10

10:32:37.000000000

Quoted 4 lines

Quoted 4 lines
+0800
+++ linux-2.6.6.dev/kernel/posix-timers.c 2004-06-02
19:12:31.000000000 +0800
(quoted diff) +0 -0
@@ -7,6 +7,9 @@

Quoted 8 lines

Quoted 8 lines
(quoted diff) +0 -0
  *
  *			     Copyright (C) 2002 2003 by MontaVista
Software.
*
+ * 2004-06-01 Fix CLOCK_REALTIME clock/timer TIMER_ABSTIME bug.
+ * Copyright (C) 2004 Boris Hu
+ *
* This program is free software; you can redistribute it and/or

modify

Quoted 1 line

Quoted 1 line
* it under the terms of the GNU General Public License as

published by

Quoted 1 line

Quoted 1 line
* the Free Software Foundation; either version 2 of the License,

Quoted 20 lines

(at

(quoted diff) +3 -1

@@ -200,7 +203,9 @@
  */
 static __init int init_posix_timers(void)
 {
-	struct k_clock clock_realtime = {.res = CLOCK_REALTIME_RES };
+	struct k_clock clock_realtime = {.res = CLOCK_REALTIME_RES,
+                .abs_timer_lock = SPIN_LOCK_UNLOCKED
 
+        };
 	struct k_clock clock_monotonic = {.res = CLOCK_REALTIME_RES,
 		.clock_get = do_posix_clock_monotonic_gettime,

(quoted diff) +1 -0

 		.clock_set = do_posix_clock_monotonic_settime

@@ -388,6 +393,7 @@
 		return;
 	}
 	posix_clocks[clock_id] = *new_clock;
+        INIT_LIST_HEAD(&posix_clocks[clock_id].abs_timer_list);
 }

Quoted 16 lines

Quoted 6 lines

(quoted diff) +0 -0

 static struct k_itimer * alloc_posix_timer(void)

@@ -843,8 +849,15 @@
 	if (((timr->it_sigev_notify & ~SIGEV_THREAD_ID) != SIGEV_NONE))
 {
 		if (timr->it_timer.expires == jiffies)
 			timer_notify_task(timr);

Review line 861

Quoted 10 lines

(quoted diff) +6 -1

-		else
+		else {
 			add_timer(&timr->it_timer);
+                        if (flags & TIMER_ABSTIME) {
+                                spin_lock(&clock->abs_timer_lock);
+
 list_add_tail(&(timr->it_timer.abs_timer_entry),
+
 &(clock->abs_timer_list));
+

spin_unlock(&clock->abs_timer_lock);

Quoted 7 lines

Review line 1098

Quoted 7 lines

(quoted diff) +2 -0

+                        }
+                }

(quoted diff) +0 -0

 	}
 	return 0;
 }

@@ -1085,16 +1098,61 @@
 sys_clock_settime(clockid_t which_clock, const struct timespec

__user

Quoted 46 lines

(quoted diff) +33 -3

 *tp)
 {
 	struct timespec new_tp;
+        struct timespec before, now;
+        struct k_clock *clock;
+        long ret;
+        struct timer_list *timer, *tmp;
+        struct timespec delta;
+        u64 exp = 0;
 
-	if ((unsigned) which_clock >= MAX_CLOCKS ||
+        if ((unsigned) which_clock >= MAX_CLOCKS ||
 					!posix_clocks[which_clock].res)
 		return -EINVAL;
-	if (copy_from_user(&new_tp, tp, sizeof (*tp)))
+
+        clock = &posix_clocks[which_clock];
+
+        if (copy_from_user(&new_tp, tp, sizeof (*tp)))
 		return -EFAULT;
 	if (posix_clocks[which_clock].clock_set)
 		return posix_clocks[which_clock].clock_set(&new_tp);
 
-	return do_sys_settimeofday(&new_tp, NULL);
+        do_posix_gettime(clock, &before);
+
+	ret = do_sys_settimeofday(&new_tp, NULL);
+
+        /*
+         * Check if there exist TIMER_ABSTIME timers to update.
+         */
+        if (which_clock != CLOCK_REALTIME ||
+            list_empty(&clock->abs_timer_list))
+                return ret;
+
+        do_posix_gettime(clock, &now);
+        delta.tv_sec = before.tv_sec - now.tv_sec;
+        delta.tv_nsec = before.tv_nsec - now.tv_nsec;
+        while (delta.tv_nsec >= NSEC_PER_SEC) {
+                delta.tv_sec ++;
+                delta.tv_nsec -= NSEC_PER_SEC;
+        }
+        while (delta.tv_nsec < 0) {
+                delta.tv_sec --;
+                delta.tv_nsec += NSEC_PER_SEC;
+        }

Quoted 8 lines

Review line 1149

Quoted 8 lines

(quoted diff) +8 -0

+
+        tstojiffie(&delta, clock->res, &exp);
+
+        spin_lock(&(clock->abs_timer_lock));
+        list_for_each_entry_safe(timer, tmp,
+                                 &clock->abs_timer_list,
+                                 abs_timer_entry) {
+                if (timer && del_timer(timer)) { //the timer has

not

Quoted 29 lines

Quoted 12 lines
run
(quoted diff) +7 -0
+                        timer->expires += exp;
+                        add_timer(timer);
+                } else
+                        list_del(&timer->abs_timer_entry);
+        }
+        spin_unlock(&(clock->abs_timer_lock));
+        return ret;
 }
 
 asmlinkage long
Quoted 12 lines
Good Luck !
Boris Hu (Hu Jiangtao)
Intel China Software Center
86-021-5257-4545#1277
iNET: 8-752-1277
************************************
There are my thoughts, not my employer's.
************************************
"gpg --recv-keys --keyserver wwwkeys.pgp.net 0FD7685F" {0FD7685F:CFD6 6F5C A2CB 7881 725B CEA0 956F 9F14 0FD7 685F}
--
George Anzinger [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

George Anzinger

2004-06-04 00:37 UTC #1 lore raw

Quoted 45 lines · Boris

Thanks for your detailed comments. :)
Quoted 9 lines
Quoted 7 lines · Boris
<<posix-abs_timer-bugfix.diff>> George,
There is one bug of CLOCK_REALTIME timer reported by Adam at
http://sources.redhat.com/ml/libc-alpha/2004-05/msg00177.html.
Here is one possible bugfix and it is against linux-2.6.6. All TIMER_ABSTIME cloks will be collected in k_clock struct and updated
in
Quoted 7 lines
Quoted 1 line
sys_clock_settime. Could you review it? Thanks.
Thanks for the poke :). Could you make the following changes:
First, put the list in the posix timer structure (k_itimer), not in timer_list.
This means one more dereference when doing things, but it does not
push
Quoted 2 lines
into
the timer_list structure which is mostly used for other things.
Done.
Quoted 1 line
Second, I don't see the timer being removed from the list (should
happen
Quoted 2 lines
when
ever it is inactive). Timers that repeat should be out of the list
while
Quoted 1 line
waiting for the signal to be picked up and put back in when add_timer
is

Quoted 7 lines

Quoted 2 lines
again
called.
I tried to add the removed codes to set_timer_inactive() but it would trigger a strange oops. I am still investigating on it. Is there any recommending places except set_timer_inactive()?

Hm, set_timer_inactive() is called from the timer create routine. Should not need to remove it here... Also, this function is used for SMP issues and, in some cases (do_timer_settime is one) it is not called if not on an SMP system. Also, it seems not to be called from sys_timer_delete(). This last would be a real problem as we are about to return the memory the list runs through it.

So, I think you will just have to find the places were we delete a timer, that and the timer call back function should do it.

Quoted 67 lines

Quoted 3 lines
Also, you should test to see if the clock is one that can be set prior
to
Quoted 1 line
putting the timer in the abs timer list. We must not correct timers
on
Quoted 1 line
CLOCK_MONOTONIC.
Done.
Quoted 1 line
Now, for the correction. Sys_clock_settime() is the wrong place for
this
Quoted 3 lines
as the
clock can also be set a number of other ways. The right place is in clock_was_set(), which is called if time is set in any of the several
ways.
Quoted 2 lines
The
next thing is to determine how far the clock was moved. I think the
best
Quoted 6 lines
way to
do this is to keep a copy of the wall_to_monotonic var in a private location.
This should be set to be exactly wall_to_monotonic when the system is booted (in
the same function you are setting up the clock lists) and at the end
of
Quoted 1 line
clock_was_set(). When clock_was_set() is called the difference
between
Quoted 2 lines
this
value and wall_to_monotonic is exactly how far the clock was moved.
(Be
Quoted 3 lines
careful
on the sign of this movement.)
Done.
Quoted 1 line
Finally, be careful about races. Timers can expire while
clock_was_set()
Quoted 4 lines
is
running. The removal code should take the timer lock as well as the abs_time
list lock (at least I think this would be wise, but I could be wrong

Quoted 6 lines

here).
IMHO, we need not take the timer locks. We del_timer() first and if the timer has expired, we simply removed it from the abs_timer_list which is protected by abs_timer_lock.

Me thinks you will need to do a bit more to convince me that locks are not needed here. Lets see if I can explain my concerns.

First, I think the clock_was_set() function needs to serialize it self so only one cpu/ task can be in it at a time. This, I think, can/is done with the abs list lock.

Second there is the possibility that a timer in the list will already be set via the correct time. To avoid this possibility I suggest (this is a change from my suggestion of yesterday) putting the current value of wall_to_monotonic in the k_timer structure when the timer is calculated. This value must be obtained under the xtime read lock (which we already take to calculate the timer). In this way of doing things, clock_was_set() would take the xtime write lock, possibly for each entry in the abs list. It would use the wall_to_monotonic time in the structure rather than keeping a local copy, and it would update that time once the correction was made.

We still haven't covered the case where time is set while a timer is being set.
I.e. where the expire time is calculated but the result has not yet been put
in the timer structure and add_timer has not yet been called. It is here that the timer lock would seem to be the right thing to do. We would require that the timer be put in the abs list while the xtime read lock is held (careful here as this is now a sequence lock and we only want to add the timer to the list once). This is complicated. We must take the locks in the same order so we can not take the timer lock while holding the abs list lock. The, IMHO, simple thing to do is to have clock_was_set() copy the whole abs list (this is just a simple pointer manipulation). Then it can scan this list and move each entry to the abs list as it updates the timers. The timer lock would be taken for each timer during this update. This is to allow timers that are on the way to add_timer to get there. This code should not remove timers from the abs list, or rather, each timer it finds in the moved list should be put back in the abs list even if it is not in the system timer list (it just means that someone else is removing it). Both the removal from the moved list and the insert into the abs list should be done under the same abs list lock but it must be dropped while taking the timer lock.

There is a possible race here with the timer delete code. Here is how I would solve this. First, with the list being moved, you need only be concerned with the first entry in the list (as you will remove it as part of processing and then do the next first entry). So, first lock the abs list. Then find the timer ID for the first entry. Unlock the abs list, and lock the timer using the ID. The existing lock code will take care of possible races WRT existence. Once the timer is locked, re lock the abs list and if the given timer is still the first entry, a.) remove it b.) if the system delete timer fails, just take the abs list lock and reinsert the timer, else under the xtime readlock compare wall_to_monotonic with the timers value c.) and put it in the abs list and the add_timer list.

Note that the case of an expired timer that is still in the abs list is handled by just reinserting the timer. This means that the expire call back code needs to check for a clock reset that may have made the expire invalid.

I am sure there are other ways of doing this, but the main locking issues are:

1.) Getting the timer's value pegged to a given clock set value (done by copying wall_to_monotonic to the k_timer struct)., This must be done under the xtime read lock.

2.) Covering the race between the timer adjustment code and possible POSIX timer deletion (done by NOT assuming the timer is there just because we found it in the abs timer list, although we do pin it down long enough to get it's ID by locking this list). This also requires us to take the timer lock which means we have to drop the abs list lock.

3.) Covering the race between the timer expiring during the system clock setting processing. Done by having the timer call back code verify that the same value of wall_to_monotonic is still in play.

We note that the time used for NOW in the repeating timer update needs to also satisfy 1. above.

And in passing, note that the overrun count will show something going on when the clock is moved forward and not when it is move backward.

Quoted 227 lines

Quoted 3 lines
And a minor issue, the community seems to prefer the C comment style
to
Quoted 3 lines
the C++
style of comments...
Done.
Quoted 16 lines
Thanks for your effort in this matter.
George
Quoted 12 lines
diff -urN -X rt.ia32/base/dontdiff
linux-2.6.6/include/linux/posix-timers.h
linux-2.6.6.dev/include/linux/posix-timers.h
--- linux-2.6.6/include/linux/posix-timers.h 2004-05-10
10:32:29.000000000 +0800
+++ linux-2.6.6.dev/include/linux/posix-timers.h 2004-06-02
10:30:57.000000000 +0800
(quoted diff) +0 -0
@@ -1,9 +1,14 @@
 #ifndef _linux_POSIX_TIMERS_H
 #define _linux_POSIX_TIMERS_H
 
Quoted 15 lines
Quoted 12 lines
(quoted diff) +6 -1
+#include <linux/list.h>
+#include <linux/spinlock.h>
+
 struct k_clock {
 	int res;		/* in nano seconds */
-	int (*clock_set) (struct timespec * tp);
+        struct list_head abs_timer_list;
+        spinlock_t abs_timer_lock;
+        int (*clock_set) (struct timespec * tp);
 	int (*clock_get) (struct timespec * tp);
 	int (*nsleep) (int flags,
 		       struct timespec * new_setting,
Quoted 3 lines
diff -urN -X rt.ia32/base/dontdiff linux-2.6.6/include/linux/timer.h linux-2.6.6.dev/include/linux/timer.h
--- linux-2.6.6/include/linux/timer.h 2004-05-10
10:32:54.000000000
Quoted 10 lines
Quoted 10 lines
+0800
+++ linux-2.6.6.dev/include/linux/timer.h 2004-06-02
19:16:08.000000000 +0800
(quoted diff) +1 -0
@@ -9,6 +9,7 @@
 
 struct timer_list {
 	struct list_head entry;
+	struct list_head abs_timer_entry;
 	unsigned long expires;
 
Quoted 4 lines
Quoted 4 lines
(quoted diff) +0 -0
 	spinlock_t lock;
diff -urN -X rt.ia32/base/dontdiff linux-2.6.6/kernel/posix-timers.c linux-2.6.6.dev/kernel/posix-timers.c
--- linux-2.6.6/kernel/posix-timers.c 2004-05-10
10:32:37.000000000
Quoted 4 lines
Quoted 4 lines
+0800
+++ linux-2.6.6.dev/kernel/posix-timers.c 2004-06-02
19:12:31.000000000 +0800
(quoted diff) +0 -0
@@ -7,6 +7,9 @@
Quoted 8 lines
Quoted 8 lines
(quoted diff) +0 -0
 *
 *			     Copyright (C) 2002 2003 by MontaVista
Software.
*
+ * 2004-06-01 Fix CLOCK_REALTIME clock/timer TIMER_ABSTIME bug.
+ * Copyright (C) 2004 Boris Hu
+ *
* This program is free software; you can redistribute it and/or
modify
Quoted 1 line
Quoted 1 line
* it under the terms of the GNU General Public License as
published by
Quoted 1 line
Quoted 1 line
* the Free Software Foundation; either version 2 of the License,
or
Quoted 20 lines
Quoted 20 lines
(at
(quoted diff) +3 -1
@@ -200,7 +203,9 @@
 */
 static __init int init_posix_timers(void)
 {
-	struct k_clock clock_realtime = {.res = CLOCK_REALTIME_RES };
+	struct k_clock clock_realtime = {.res = CLOCK_REALTIME_RES,
+                .abs_timer_lock = SPIN_LOCK_UNLOCKED
 
+        };
 	struct k_clock clock_monotonic = {.res = CLOCK_REALTIME_RES,
 		.clock_get = do_posix_clock_monotonic_gettime,
.clock_set = do_posix_clock_monotonic_settime
(quoted diff) +1 -0
@@ -388,6 +393,7 @@
 		return;
 	}
 	posix_clocks[clock_id] = *new_clock;
+        INIT_LIST_HEAD(&posix_clocks[clock_id].abs_timer_list);
 }
 
Quoted 16 lines
Quoted 6 lines
(quoted diff) +0 -0
 static struct k_itimer * alloc_posix_timer(void)
@@ -843,8 +849,15 @@
 	if (((timr->it_sigev_notify & ~SIGEV_THREAD_ID) != SIGEV_NONE))
 {
 		if (timr->it_timer.expires == jiffies)
 			timer_notify_task(timr);
Review line 861
Quoted 10 lines
(quoted diff) +6 -1
-		else
+		else {
 			add_timer(&timr->it_timer);
+                        if (flags & TIMER_ABSTIME) {
+                                spin_lock(&clock->abs_timer_lock);
+
 list_add_tail(&(timr->it_timer.abs_timer_entry),
+
 &(clock->abs_timer_list));
+
spin_unlock(&clock->abs_timer_lock);
Quoted 7 lines
Quoted 7 lines
(quoted diff) +2 -0
+                        }
+                }
	}
	return 0;
}
(quoted diff) +0 -0
@@ -1085,16 +1098,61 @@
sys_clock_settime(clockid_t which_clock, const struct timespec
__user
Quoted 46 lines
Quoted 46 lines
*tp)
{
	struct timespec new_tp;
(quoted diff) +7 -1
+        struct timespec before, now;
+        struct k_clock *clock;
+        long ret;
+        struct timer_list *timer, *tmp;
+        struct timespec delta;
+        u64 exp = 0;
 
-	if ((unsigned) which_clock >= MAX_CLOCKS ||
+        if ((unsigned) which_clock >= MAX_CLOCKS ||
					!posix_clocks[which_clock].res)
		return -EINVAL;
(quoted diff) +4 -1
-	if (copy_from_user(&new_tp, tp, sizeof (*tp)))
+
+        clock = &posix_clocks[which_clock];
+
+        if (copy_from_user(&new_tp, tp, sizeof (*tp)))
		return -EFAULT;
	if (posix_clocks[which_clock].clock_set)
		return posix_clocks[which_clock].clock_set(&new_tp);
(quoted diff) +22 -1
-	return do_sys_settimeofday(&new_tp, NULL);
+        do_posix_gettime(clock, &before);
+
+	ret = do_sys_settimeofday(&new_tp, NULL);
+
+        /*
+         * Check if there exist TIMER_ABSTIME timers to update.
+         */
+        if (which_clock != CLOCK_REALTIME ||
+            list_empty(&clock->abs_timer_list))
+                return ret;
+
+        do_posix_gettime(clock, &now);
+        delta.tv_sec = before.tv_sec - now.tv_sec;
+        delta.tv_nsec = before.tv_nsec - now.tv_nsec;
+        while (delta.tv_nsec >= NSEC_PER_SEC) {
+                delta.tv_sec ++;
+                delta.tv_nsec -= NSEC_PER_SEC;
+        }
+        while (delta.tv_nsec < 0) {
+                delta.tv_sec --;
+                delta.tv_nsec += NSEC_PER_SEC;
+        }
Quoted 8 lines
Review
Quoted 8 lines
(quoted diff) +8 -0
+
+        tstojiffie(&delta, clock->res, &exp);
+
+        spin_lock(&(clock->abs_timer_lock));
+        list_for_each_entry_safe(timer, tmp,
+                                 &clock->abs_timer_list,
+                                 abs_timer_entry) {
+                if (timer && del_timer(timer)) { //the timer has
not
Quoted 29 lines
Quoted 12 lines
run
(quoted diff) +7 -0
+                        timer->expires += exp;
+                        add_timer(timer);
+                } else
+                        list_del(&timer->abs_timer_entry);
+        }
+        spin_unlock(&(clock->abs_timer_lock));
+        return ret;
}
asmlinkage long
Quoted 12 lines
Good Luck !
Boris Hu (Hu Jiangtao)
Intel China Software Center
86-021-5257-4545#1277
iNET: 8-752-1277
************************************
There are my thoughts, not my employer's.
************************************
"gpg --recv-keys --keyserver wwwkeys.pgp.net 0FD7685F" {0FD7685F:CFD6 6F5C A2CB 7881 725B CEA0 956F 9F14 0FD7 685F}
--
George Anzinger [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Signature · 3 lines

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

George Anzinger

2004-06-28 22:03 UTC #2 lore raw

PATCH 1/1 Bugfix for CLOCK_REALTIME absolute timer.

In reply to Hu, Boris

Andrew,

Boris and I have kicked this around enough. It think it is ready for prime time.

As required by the standard, this patch adds to POSIX ABSOLUTE timers the functionality of adjusting the timer when the clock is set so that it still expires at the specified time (provided that time has not passed, in which case the timer expires immeadiatly).

The standard is, IMNSOHO, a bit vague on just how repeating timers are to be handled so I made some choices:

1) If an absolute timer is to expire every N intervals, we assume that the expiries should happen at those specified times after clock setting. I.e. we adjust the repeat timer as well as the initial timer. (The other option would be to treat the repeating timers as relative and not to adjust them.)

2) If a clock set moves the the clock prior to the initial expiry time AND that time has already passed and been signaled, the current repeat timer is adjusted, i.e. we DO NOT go back to the initial time and repeat that. (The other option is to treat this case as a new request with the initial timer parameters (which by this time we have lost).)

3) If time is advanced such that it appears that several expiries have been missed, the overrun count will reflect the misses. (The other option is to not reflect this in the overrun.) At the same time, nothing is done to acknowledge, to the user, that we are repeating expiries when the clock is retarded.

Signed-off-by George Anzinger <[email protected]>

Signature · 3 lines

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

include/linux/posix-timers.h +8 -0

diff -urP -I '\$Id:.*Exp \$' -X /usr/src/patch.exclude linux-2.6.6-kbdw/include/linux/posix-timers.h linux/include/linux/posix-timers.h
@@ -1,8 +1,16 @@
 #ifndef _linux_POSIX_TIMERS_H
 #define _linux_POSIX_TIMERS_H
 
+#include <linux/spinlock.h>
+#include <linux/list.h>
+
+struct k_clock_abs {
+	struct list_head list;
+	spinlock_t lock;
+};
 struct k_clock {
 	int res;		/* in nano seconds */
+	struct k_clock_abs *abs_struct;
 	int (*clock_set) (struct timespec * tp);
 	int (*clock_get) (struct timespec * tp);
 	int (*nsleep) (int flags,

include/linux/sched.h +2 -0

diff -urP -I '\$Id:.*Exp \$' -X /usr/src/patch.exclude linux-2.6.6-kbdw/include/linux/sched.h linux/include/linux/sched.h
@@ -342,6 +342,8 @@
 	struct task_struct *it_process;	/* process to send signal to */
 	struct timer_list it_timer;
 	struct sigqueue *sigq;		/* signal queue entry. */
+	struct list_head abs_timer_entry; /* clock abs_timer_list */
+	struct timespec wall_to_prev;   /* wall_to_monotonic used when set */
 };

kernel/posix-timers.c +245 ~~-26~~

428 lines not on this page · raw message

Binary files linux-2.6.6-kbdw/scripts/bin2c and linux/scripts/bin2c differ

Andrew Morton

2004-06-28 22:18 UTC #3 lore raw

Re: [PATCH] Bugfix for CLOCK_REALTIME absolute timer.

Quoted 16 lines · George Anzinger

Andrew,
Boris and I have kicked this around enough. It think it is ready for prime time.
static void schedule_next_timer(struct k_itimer *timr) {
...
kernel/posix-timers.c +7 -0
+	do {
+		seq = read_seqbegin(&xtime_lock);
+		new_wall_to =	wall_to_monotonic;
+		posix_get_now(&now);
+	} while (read_seqretry(&xtime_lock, seq));
+
+	if (!list_empty(&timr->abs_timer_entry)) {

kernel/posix-timers.c line 331

Quoted 10 lines

kernel/posix-timers.c +6 -0

+		spin_lock(&abs_list.lock);
+		add_clockset_delta(timr, &new_wall_to);
+	}
+		    
 	do {
 		posix_bump_timer(timr);
 	}while (posix_time_before(&timr->it_timer, &now));
 
+	if (!list_empty(&timr->abs_timer_entry))
+		spin_unlock(&abs_list.lock);

The locking in here is a bit ugly. Does the lock actually need to be held while the timer is being bumped?

And what is the upper bound on that while loop?

kernel/posix-timers.c line 527

Quoted 3 lines

kernel/posix-timers.c +1 -0

 	tmr->it_id = (timer_t)-1;
+        INIT_LIST_HEAD(&tmr->abs_timer_entry);
 	if (unlikely(!(tmr->sigq = sigqueue_alloc()))) {

The cat ate your tab key? ;)

kernel/posix-timers.c line 945

Quoted 5 lines

kernel/posix-timers.c +5 -0

+	if (!list_empty(&timr->abs_timer_entry)) {
+		spin_lock(&abs_list.lock);
+		list_del_init(&timr->abs_timer_entry);
+		spin_unlock(&abs_list.lock);
+	}

This is repeated often. Does it merit its own function?

kernel/posix-timers.c line 1304

Quoted 4 lines

kernel/posix-timers.c +4 -0

+static DECLARE_MUTEX(clock_was_set_lock);
+#define mutex_enter(x) down(x)
+#define mutex_enter_interruptable(x) down_interruptible(x)
+#define mutex_exit(x) up(x)

Please open-code these operations.

George Anzinger

2004-06-28 22:56 UTC #4 lore raw

Re: [PATCH] Bugfix for CLOCK_REALTIME absolute timer.

Quoted 26 lines · Andrew Morton

Quoted 24 lines · George Anzinger
Andrew,
Boris and I have kicked this around enough. It think it is ready for prime time.
static void schedule_next_timer(struct k_itimer *timr) {
...
kernel/posix-timers.c +11 -0
+	do {
+		seq = read_seqbegin(&xtime_lock);
+		new_wall_to =	wall_to_monotonic;
+		posix_get_now(&now);
+	} while (read_seqretry(&xtime_lock, seq));
+
+	if (!list_empty(&timr->abs_timer_entry)) {
+		spin_lock(&abs_list.lock);
+		add_clockset_delta(timr, &new_wall_to);
+	}
+		    
	do {
		posix_bump_timer(timr);
	}while (posix_time_before(&timr->it_timer, &now));

Quoted 8 lines

kernel/posix-timers.c line 331
Quoted 2 lines
kernel/posix-timers.c +2 -0
+	if (!list_empty(&timr->abs_timer_entry))
+		spin_unlock(&abs_list.lock);
The locking in here is a bit ugly. Does the lock actually need to be held while the timer is being bumped?
And what is the upper bound on that while loop?

Yes, I agree that it is ugly. And on top of that, we are holding the timer lock which is an irq version. As to the need to hold it through the bump, we want the timers expire time to match what it should given the clock setting we are using, otherwise, the clock_was_set() code could come through and change that under us. (Not a pretty sight.)

Now, the bounding on the while, :( it depends on a) the interval and b) how far the clock was moved. The shorter the interval or the longer the time interval, the more we loop. I suppose the best thing to do here is an div, but will, most of the time, take longer.

Quoted 8 lines

Quoted 5 lines


	tmr->it_id = (timer_t)-1;
+        INIT_LIST_HEAD(&tmr->abs_timer_entry);
	if (unlikely(!(tmr->sigq = sigqueue_alloc()))) {

The cat ate your tab key? ;)

Oh, shit. And I thought I had the cat locked away in the back room. ;)

Quoted 10 lines

kernel/posix-timers.c line 945
Quoted 7 lines
kernel/posix-timers.c +5 -0
+	if (!list_empty(&timr->abs_timer_entry)) {
+		spin_lock(&abs_list.lock);
+		list_del_init(&timr->abs_timer_entry);
+		spin_unlock(&abs_list.lock);
+	}
This is repeated often. Does it merit its own function?

Ok.

Quoted 9 lines

kernel/posix-timers.c line 1304
Quoted 6 lines
kernel/posix-timers.c +4 -0
+static DECLARE_MUTEX(clock_was_set_lock);
+#define mutex_enter(x) down(x)
+#define mutex_enter_interruptable(x) down_interruptible(x)
+#define mutex_exit(x) up(x)
Please open-code these operations.

Eh? Seems funny that we have a definition for mutex (DECLARE_MUTEX) and don't have the defines to use them. But, ok.

Quoted 2 lines

Signature · 3 lines

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

George Anzinger

2004-06-29 04:49 UTC #5 lore raw

PATCH 1/1 Bugfix for CLOCK_REALTIME absolute timer.

In reply to Hu, Boris

Andrew,

Ok, I think this does it. I found that cat too :)

The standard is, IMNSOHO, a bit vague on just how repeating timers are to be handled so I made some choices:

Signed-off-by George Anzinger <[email protected]>

Signature · 3 lines

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

include/linux/posix-timers.h +18 -4

diff -urP -I '\$Id:.*Exp \$' -X /usr/src/patch.exclude linux-2.6.6-kbdw/include/linux/posix-timers.h linux/include/linux/posix-timers.h
@@ -1,8 +1,16 @@
 #ifndef _linux_POSIX_TIMERS_H
 #define _linux_POSIX_TIMERS_H
 
+#include <linux/spinlock.h>
+#include <linux/list.h>
+
+struct k_clock_abs {
+	struct list_head list;
+	spinlock_t lock;
+};
 struct k_clock {
 	int res;		/* in nano seconds */
+	struct k_clock_abs *abs_struct;
 	int (*clock_set) (struct timespec * tp);
 	int (*clock_get) (struct timespec * tp);
 	int (*nsleep) (int flags,

@@ -23,8 +31,14 @@
 #define posix_time_before(timer, now) \
                       time_before((timer)->expires, (now)->jiffies)
 
-#define posix_bump_timer(timr) do { \
-                        (timr)->it_timer.expires += (timr)->it_incr; \
-                        (timr)->it_overrun++;               \
-                       }while (0)
+#define posix_bump_timer(timr, now)					\
+         do {								\
+              long delta, orun;						\
+	      delta = now.jiffies - (timr)->it_timer.expires;		\
+              if (delta >= 0) {						\
+	           orun = 1 + (delta / (timr)->it_incr);		\
+	          (timr)->it_timer.expires += orun * (timr)->it_incr;	\
+                  (timr)->it_overrun += orun;				\
+              }								\
+            }while (0)
 #endif

include/linux/sched.h +2 -0

diff -urP -I '\$Id:.*Exp \$' -X /usr/src/patch.exclude linux-2.6.6-kbdw/include/linux/sched.h linux/include/linux/sched.h
@@ -342,6 +342,8 @@
 	struct task_struct *it_process;	/* process to send signal to */
 	struct timer_list it_timer;
 	struct sigqueue *sigq;		/* signal queue entry. */
+	struct list_head abs_timer_entry; /* clock abs_timer_list */
+	struct timespec wall_to_prev;   /* wall_to_monotonic used when set */
 };

kernel/posix-timers.c +245 ~~-30~~

436 lines not on this page · raw message

Binary files linux-2.6.6-kbdw/scripts/bin2c and linux/scripts/bin2c differ

Andrew Morton

2004-06-29 04:59 UTC #6 lore raw

Re: [PATCH] Bugfix for CLOCK_REALTIME absolute timer.

Quoted 2 lines · George Anzinger

Ok, I think this does it.

patching file kernel/posix-timers.c
Hunk #10 FAILED at 529.
Hunk #11 succeeded at 776 (offset 18 lines).
Hunk #13 succeeded at 863 (offset 18 lines).
Hunk #15 succeeded at 977 (offset 18 lines).
Hunk #17 succeeded at 1062 (offset 18 lines).
Hunk #19 succeeded at 1435 (offset 18 lines).
1 out of 20 hunks FAILED -- saving rejects to file kernel/posix-timers.c.rej

I fixed that up - please test next -mm, check that it all works?

+ do {
+ do {
+ seq = read_seqbegin(&xtime_lock);
+ new_wall_to = wall_to_monotonic;
+ } while (read_seqretry(&xtime_lock, seq));
+
+ spin_lock_irq(&abs_list.lock);
+ if (list_empty(&cws_list)) {
+ spin_unlock_irq(&abs_list.lock);
+ break;
+ }
+ timr = list_entry(cws_list.next, struct k_itimer,
+ abs_timer_entry);
+
+ list_del_init(&timr->abs_timer_entry);
+ if (add_clockset_delta(timr, &new_wall_to) &&
+ del_timer(&timr->it_timer)) /* timer run yet? */
+ add_timer(&timr->it_timer);
+ list_add(&timr->abs_timer_entry, &abs_list.list);
+ spin_unlock_irq(&abs_list.lock);
+ } while (1);

nanonit:

	for ( ; ; ) {
		...
	}

is more readable than

	do {
		...
	} while (1);

because you can see what it's doing as the eye enters the code...

George Anzinger

2004-06-29 08:45 UTC #7 lore raw

Re: [PATCH] Bugfix for CLOCK_REALTIME absolute timer.

Quoted 14 lines · Andrew Morton

Quoted 1 line · George Anzinger
Ok, I think this does it.
patching file kernel/posix-timers.c
Hunk #10 FAILED at 529.
Hunk #11 succeeded at 776 (offset 18 lines).
Hunk #13 succeeded at 863 (offset 18 lines).
Hunk #15 succeeded at 977 (offset 18 lines).
Hunk #17 succeeded at 1062 (offset 18 lines).
Hunk #19 succeeded at 1435 (offset 18 lines).
1 out of 20 hunks FAILED -- saving rejects to file kernel/posix-timers.c.rej

Quoted 1 line

I fixed that up - please test next -mm, check that it all works?

Will do.

Quoted 29 lines

+ do {
+ do {
+ seq = read_seqbegin(&xtime_lock);
+ new_wall_to = wall_to_monotonic;
+ } while (read_seqretry(&xtime_lock, seq));
+
+ spin_lock_irq(&abs_list.lock);
+ if (list_empty(&cws_list)) {
+ spin_unlock_irq(&abs_list.lock);
+ break;
+ }
+ timr = list_entry(cws_list.next, struct k_itimer,
+ abs_timer_entry);
+
+ list_del_init(&timr->abs_timer_entry);
+ if (add_clockset_delta(timr, &new_wall_to) &&
+ del_timer(&timr->it_timer)) /* timer run yet? */
+ add_timer(&timr->it_timer);
+ list_add(&timr->abs_timer_entry, &abs_list.list);
+ spin_unlock_irq(&abs_list.lock);
+ } while (1);
nanonit:
	for ( ; ; ) {
		...
	}

Quoted 8 lines

is more readable than
	do {
		...
	} while (1);
because you can see what it's doing as the eye enters the code...

Noted, thanks.

Signature · 3 lines

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

George Anzinger

2004-06-30 19:14 UTC #8 lore raw

Re: [PATCH] Bugfix for CLOCK_REALTIME absolute timer.

In reply to Andrew Morton

Andrew Morton wrote:
~

Quoted 1 line

I fixed that up - please test next -mm, check that it all works?

It passes all my tests. Boris gives a thumbs up also.

Signature · 3 lines

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml