too much timer simplification...

too much timer simplification...

[David Mosberger]

It appears to me that this changeset:

  http://linux.bkbits.net:8080/linux-2.5/diffs/kernel/timer.c@1.48

may have gone a little too far.

What I'm seeing is that if someone happens to arm a periodic timer at
exactly 256 jiffies (as ohci happens to do on platforms with HZ=1024),
then you end up getting an endless loop of timer activations, causing
a machine hang.

The problem is that __run_timers updates base->timer_jiffies _before_
running the callback routines.  If a callback re-arms the timer at
exactly 256 jiffies, add_timers() will reinsert the timer into the
list that we're currently processing, which of course will cause the
timer to expire immediately again, etc., etc., ad naseum...

I'll leave it as an exercise to the readers to come up with the proper
patch.  (The old code looked fine to me.  My cheesy quick workaround
is to round up 256 ticks to 257 ticks; might not make the soft RT
folks too happy though... ;-)

	--david

Re: too much timer simplification...

[Andrew Morton]

David Mosberger <davidm@napali.hpl.hp.com> wrote:
>
> It appears to me that this changeset:
> 
>   http://linux.bkbits.net:8080/linux-2.5/diffs/kernel/timer.c@1.48
> 
> may have gone a little too far.
> 
> What I'm seeing is that if someone happens to arm a periodic timer at
> exactly 256 jiffies (as ohci happens to do on platforms with HZ=1024),
> then you end up getting an endless loop of timer activations, causing
> a machine hang.
> 
> The problem is that __run_timers updates base->timer_jiffies _before_
> running the callback routines.  If a callback re-arms the timer at
> exactly 256 jiffies, add_timers() will reinsert the timer into the
> list that we're currently processing, which of course will cause the
> timer to expire immediately again, etc., etc., ad naseum...
> 

OK, well unless George can pull a rabbit out of the hat it may
be best to just revert it.

This gives us the same algorithm as 2.4, which I think is good.


--- 25/kernel/timer.c~timer-simplification-revert	2003-04-11 00:19:48.000000000 -0700
+++ 25-akpm/kernel/timer.c	2003-04-11 00:19:48.000000000 -0700
@@ -56,6 +56,7 @@ struct tvec_t_base_s {
 	spinlock_t lock;
 	unsigned long timer_jiffies;
 	struct timer_list *running_timer;
+	struct list_head *run_timer_list_running;
 	tvec_root_t tv1;
 	tvec_t tv2;
 	tvec_t tv3;
@@ -100,6 +101,12 @@ static inline void check_timer(struct ti
 		check_timer_failed(timer);
 }
 
+/*
+ * If a timer handler re-adds the timer with expires == jiffies, the timer
+ * running code can lock up.  So here we detect that situation and park the
+ * timer onto base->run_timer_list_running.  It will be added to the main timer
+ * structures later, by __run_timers().
+ */
 
 static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
 {
@@ -107,7 +114,9 @@ static void internal_add_timer(tvec_base
 	unsigned long idx = expires - base->timer_jiffies;
 	struct list_head *vec;
 
-	if (idx < TVR_SIZE) {
+	if (base->run_timer_list_running) {
+		vec = base->run_timer_list_running;
+	} else if (idx < TVR_SIZE) {
 		int i = expires & TVR_MASK;
 		vec = base->tv1.vec + i;
 	} else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
@@ -397,6 +406,7 @@ static inline void __run_timers(tvec_bas
 
 	spin_lock_irq(&base->lock);
 	while (time_after_eq(jiffies, base->timer_jiffies)) {
+		LIST_HEAD(deferred_timers);
 		struct list_head *head;
  		int index = base->timer_jiffies & TVR_MASK;
  
@@ -408,7 +418,7 @@ static inline void __run_timers(tvec_bas
 				(!cascade(base, &base->tv3, INDEX(1))) &&
 					!cascade(base, &base->tv4, INDEX(2)))
 			cascade(base, &base->tv5, INDEX(3));
-		++base->timer_jiffies; 
+		base->run_timer_list_running = &deferred_timers;
 repeat:
 		head = base->tv1.vec + index;
 		if (!list_empty(head)) {
@@ -427,6 +437,14 @@ repeat:
 			spin_lock_irq(&base->lock);
 			goto repeat;
 		}
+		base->run_timer_list_running = NULL;
+		++base->timer_jiffies; 
+		while (!list_empty(&deferred_timers)) {
+			timer = list_entry(deferred_timers.prev,
+						struct timer_list, entry);
+			list_del(&timer->entry);
+			internal_add_timer(base, timer);
+		}
 	}
 	set_running_timer(base, NULL);
 	spin_unlock_irq(&base->lock);

_

Re: too much timer simplification...

[george anzinger]

Andrew Morton wrote:
> David Mosberger <davidm@napali.hpl.hp.com> wrote:
> 
>>It appears to me that this changeset:
>>
>>  http://linux.bkbits.net:8080/linux-2.5/diffs/kernel/timer.c@1.48
>>
>>may have gone a little too far.
>>
>>What I'm seeing is that if someone happens to arm a periodic timer at
>>exactly 256 jiffies (as ohci happens to do on platforms with HZ=1024),
>>then you end up getting an endless loop of timer activations, causing
>>a machine hang.
>>
>>The problem is that __run_timers updates base->timer_jiffies _before_
>>running the callback routines.  If a callback re-arms the timer at
>>exactly 256 jiffies, add_timers() will reinsert the timer into the
>>list that we're currently processing, which of course will cause the
>>timer to expire immediately again, etc., etc., ad naseum...
>>
> 
> 
> OK, well unless George can pull a rabbit out of the hat it may
> be best to just revert it.
> 
I think the answer here is to move the whole expired list to a local 
header and to not look back.  I will work this into a patch...

-g

> This gives us the same algorithm as 2.4, which I think is good.
> 
> 
> --- 25/kernel/timer.c~timer-simplification-revert	2003-04-11 00:19:48.000000000 -0700
> +++ 25-akpm/kernel/timer.c	2003-04-11 00:19:48.000000000 -0700
> @@ -56,6 +56,7 @@ struct tvec_t_base_s {
>  	spinlock_t lock;
>  	unsigned long timer_jiffies;
>  	struct timer_list *running_timer;
> +	struct list_head *run_timer_list_running;
>  	tvec_root_t tv1;
>  	tvec_t tv2;
>  	tvec_t tv3;
> @@ -100,6 +101,12 @@ static inline void check_timer(struct ti
>  		check_timer_failed(timer);
>  }
>  
> +/*
> + * If a timer handler re-adds the timer with expires == jiffies, the timer
> + * running code can lock up.  So here we detect that situation and park the
> + * timer onto base->run_timer_list_running.  It will be added to the main timer
> + * structures later, by __run_timers().
> + */
>  
>  static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
>  {
> @@ -107,7 +114,9 @@ static void internal_add_timer(tvec_base
>  	unsigned long idx = expires - base->timer_jiffies;
>  	struct list_head *vec;
>  
> -	if (idx < TVR_SIZE) {
> +	if (base->run_timer_list_running) {
> +		vec = base->run_timer_list_running;
> +	} else if (idx < TVR_SIZE) {
>  		int i = expires & TVR_MASK;
>  		vec = base->tv1.vec + i;
>  	} else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
> @@ -397,6 +406,7 @@ static inline void __run_timers(tvec_bas
>  
>  	spin_lock_irq(&base->lock);
>  	while (time_after_eq(jiffies, base->timer_jiffies)) {
> +		LIST_HEAD(deferred_timers);
>  		struct list_head *head;
>   		int index = base->timer_jiffies & TVR_MASK;
>   
> @@ -408,7 +418,7 @@ static inline void __run_timers(tvec_bas
>  				(!cascade(base, &base->tv3, INDEX(1))) &&
>  					!cascade(base, &base->tv4, INDEX(2)))
>  			cascade(base, &base->tv5, INDEX(3));
> -		++base->timer_jiffies; 
> +		base->run_timer_list_running = &deferred_timers;
>  repeat:
>  		head = base->tv1.vec + index;
>  		if (!list_empty(head)) {
> @@ -427,6 +437,14 @@ repeat:
>  			spin_lock_irq(&base->lock);
>  			goto repeat;
>  		}
> +		base->run_timer_list_running = NULL;
> +		++base->timer_jiffies; 
> +		while (!list_empty(&deferred_timers)) {
> +			timer = list_entry(deferred_timers.prev,
> +						struct timer_list, entry);
> +			list_del(&timer->entry);
> +			internal_add_timer(base, timer);
> +		}
>  	}
>  	set_running_timer(base, NULL);
>  	spin_unlock_irq(&base->lock);
> 
> _
> 
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

Re: too much timer simplification...

[george anzinger]

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

Andrew Morton wrote:
> David Mosberger <davidm@napali.hpl.hp.com> wrote:
> 
>>It appears to me that this changeset:
>>
>>  http://linux.bkbits.net:8080/linux-2.5/diffs/kernel/timer.c@1.48
>>
>>may have gone a little too far.
>>
>>What I'm seeing is that if someone happens to arm a periodic timer at
>>exactly 256 jiffies (as ohci happens to do on platforms with HZ=1024),
>>then you end up getting an endless loop of timer activations, causing
>>a machine hang.
>>
>>The problem is that __run_timers updates base->timer_jiffies _before_
>>running the callback routines.  If a callback re-arms the timer at
>>exactly 256 jiffies, add_timers() will reinsert the timer into the
>>list that we're currently processing, which of course will cause the
>>timer to expire immediately again, etc., etc., ad naseum...
>>
> 
> 
> OK, well unless George can pull a rabbit out of the hat it may
> be best to just revert it.

Lets try the attached...  works for me.

> 
> This gives us the same algorithm as 2.4, which I think is good.
> 
> 
> --- 25/kernel/timer.c~timer-simplification-revert	2003-04-11 00:19:48.000000000 -0700
> +++ 25-akpm/kernel/timer.c	2003-04-11 00:19:48.000000000 -0700
> @@ -56,6 +56,7 @@ struct tvec_t_base_s {
>  	spinlock_t lock;
>  	unsigned long timer_jiffies;
>  	struct timer_list *running_timer;
> +	struct list_head *run_timer_list_running;
>  	tvec_root_t tv1;
>  	tvec_t tv2;
>  	tvec_t tv3;
> @@ -100,6 +101,12 @@ static inline void check_timer(struct ti
>  		check_timer_failed(timer);
>  }
>  
> +/*
> + * If a timer handler re-adds the timer with expires == jiffies, the timer
> + * running code can lock up.  So here we detect that situation and park the
> + * timer onto base->run_timer_list_running.  It will be added to the main timer
> + * structures later, by __run_timers().
> + */
>  
>  static void internal_add_timer(tvec_base_t *base, struct timer_list *timer)
>  {
> @@ -107,7 +114,9 @@ static void internal_add_timer(tvec_base
>  	unsigned long idx = expires - base->timer_jiffies;
>  	struct list_head *vec;
>  
> -	if (idx < TVR_SIZE) {
> +	if (base->run_timer_list_running) {
> +		vec = base->run_timer_list_running;
> +	} else if (idx < TVR_SIZE) {
>  		int i = expires & TVR_MASK;
>  		vec = base->tv1.vec + i;
>  	} else if (idx < 1 << (TVR_BITS + TVN_BITS)) {
> @@ -397,6 +406,7 @@ static inline void __run_timers(tvec_bas
>  
>  	spin_lock_irq(&base->lock);
>  	while (time_after_eq(jiffies, base->timer_jiffies)) {
> +		LIST_HEAD(deferred_timers);
>  		struct list_head *head;
>   		int index = base->timer_jiffies & TVR_MASK;
>   
> @@ -408,7 +418,7 @@ static inline void __run_timers(tvec_bas
>  				(!cascade(base, &base->tv3, INDEX(1))) &&
>  					!cascade(base, &base->tv4, INDEX(2)))
>  			cascade(base, &base->tv5, INDEX(3));
> -		++base->timer_jiffies; 
> +		base->run_timer_list_running = &deferred_timers;
>  repeat:
>  		head = base->tv1.vec + index;
>  		if (!list_empty(head)) {
> @@ -427,6 +437,14 @@ repeat:
>  			spin_lock_irq(&base->lock);
>  			goto repeat;
>  		}
> +		base->run_timer_list_running = NULL;
> +		++base->timer_jiffies; 
> +		while (!list_empty(&deferred_timers)) {
> +			timer = list_entry(deferred_timers.prev,
> +						struct timer_list, entry);
> +			list_del(&timer->entry);
> +			internal_add_timer(base, timer);
> +		}
>  	}
>  	set_running_timer(base, NULL);
>  	spin_unlock_irq(&base->lock);
> 
> _
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

-- 
George Anzinger   george@mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml

[-- Attachment #2: run_timer_fix2-2.5.67-bk1-1.0.patch --]
[-- Type: text/plain, Size: 742 bytes --]

--- linux-2.5.67-bk1-org/kernel/timer.c	2003-03-24 23:34:15.000000000 -0800
+++ linux/kernel/timer.c	2003-04-11 15:29:11.000000000 -0700
@@ -397,7 +397,8 @@
 
 	spin_lock_irq(&base->lock);
 	while (time_after_eq(jiffies, base->timer_jiffies)) {
-		struct list_head *head;
+		struct list_head work_list = LIST_HEAD_INIT(work_list);
+		struct list_head *head = &work_list;
  		int index = base->timer_jiffies & TVR_MASK;
  
 		/*
@@ -409,8 +410,8 @@
 					!cascade(base, &base->tv4, INDEX(2)))
 			cascade(base, &base->tv5, INDEX(3));
 		++base->timer_jiffies; 
+		list_splice_init(base->tv1.vec + index, &work_list);
 repeat:
-		head = base->tv1.vec + index;
 		if (!list_empty(head)) {
 			void (*fn)(unsigned long);
 			unsigned long data;