[RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

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



[-- Attachment #2: hrtimer-cache.patch --]
[-- Type: text/x-patch, Size: 7620 bytes --]

>From 6558900969ef1f4492aad4d9a2a87cd8900dee92 Mon Sep 17 00:00:00 2001
From: Ashwin Chaugule <ashwinc@quicinc.com>
Date: Thu, 27 Aug 2009 10:42:48 -0400
Subject: [PATCH][hrtimers]  Cache next hrtimer

	Cached the hrtimer which causes the expire_next
	value to change. This is to avoid unnecessary re-programming
	of the clock events device.

	modified:   include/linux/hrtimer.h
	modified:   kernel/hrtimer.c

	Signed-off-by: Ashwin Chaugule <ashwinc@quicinc.com>
---
 include/linux/hrtimer.h |    5 ++-
 kernel/hrtimer.c        |   81 +++++++++++++++++++++++++++++++---------------
 2 files changed, 58 insertions(+), 28 deletions(-)

diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index bd37078..dd8fa9b 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -4,7 +4,8 @@
  *  hrtimers - High-resolution kernel timers
  *
  *   Copyright(C) 2005, Thomas Gleixner <tglx@linutronix.de>
- *   Copyright(C) 2005, Red Hat, Inc., Ingo Molnar
+ *   Copyright(C) 2005, Red Hat, Inc., Ingo Molnar 
+ *   Copyright(C) 2009, Code Aurora Forum. All rights reserved.
  *
  *  data type definitions, declarations, prototypes
  *
@@ -157,6 +158,7 @@ struct hrtimer_clock_base {
  *			and timers
  * @clock_base:		array of clock bases for this cpu
  * @curr_timer:		the timer which is executing a callback right now
+ * @next_hrtimer:	the hrtimer that caused expires_next to change
  * @expires_next:	absolute time of the next event which was scheduled
  *			via clock_set_next_event()
  * @hres_active:	State of high resolution mode
@@ -169,6 +171,7 @@ struct hrtimer_cpu_base {
 	spinlock_t			lock;
 	struct hrtimer_clock_base	clock_base[HRTIMER_MAX_CLOCK_BASES];
 #ifdef CONFIG_HIGH_RES_TIMERS
+	struct hrtimer 			*next_hrtimer;
 	ktime_t				expires_next;
 	int				hres_active;
 	unsigned long			nr_events;
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index f394d2a..d823987 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -4,6 +4,8 @@
  *  Copyright(C) 2005-2006, Thomas Gleixner <tglx@linutronix.de>
  *  Copyright(C) 2005-2007, Red Hat, Inc., Ingo Molnar
  *  Copyright(C) 2006-2007  Timesys Corp., Thomas Gleixner
+ *  Copyright(C) 2009, Code Aurora Forum. All rights reserved.
+ *
  *
  *  High-resolution kernel timers
  *
@@ -508,8 +510,10 @@ static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
 		 */
 		if (expires.tv64 < 0)
 			expires.tv64 = 0;
-		if (expires.tv64 < cpu_base->expires_next.tv64)
+		if (expires.tv64 < cpu_base->expires_next.tv64) {
 			cpu_base->expires_next = expires;
+			cpu_base->next_hrtimer = timer;
+		}
 	}
 
 	if (cpu_base->expires_next.tv64 != KTIME_MAX)
@@ -529,6 +533,7 @@ static int hrtimer_reprogram(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base)
 {
 	ktime_t *expires_next = &__get_cpu_var(hrtimer_bases).expires_next;
+	struct hrtimer *next_hrtimer = __get_cpu_var(hrtimer_bases).next_hrtimer;
 	ktime_t expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
 	int res;
 
@@ -560,8 +565,10 @@ static int hrtimer_reprogram(struct hrtimer *timer,
 	 * Clockevents returns -ETIME, when the event was in the past.
 	 */
 	res = tick_program_event(expires, 0);
-	if (!IS_ERR_VALUE(res))
+	if (!IS_ERR_VALUE(res)) {
 		*expires_next = expires;
+		next_hrtimer = timer;
+	}
 	return res;
 }
 
@@ -634,6 +641,7 @@ static inline void hrtimer_init_hres(struct hrtimer_cpu_base *base)
 {
 	base->expires_next.tv64 = KTIME_MAX;
 	base->hres_active = 0;
+	base->next_hrtimer = NULL;
 }
 
 /*
@@ -843,16 +851,20 @@ static void __remove_hrtimer(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base,
 			     unsigned long newstate, int reprogram)
 {
-	if (timer->state & HRTIMER_STATE_ENQUEUED) {
+	struct hrtimer *next_hrtimer = __get_cpu_var(hrtimer_bases).next_hrtimer;
+
+	if (hrtimer_is_queued(timer)) {
 		/*
 		 * Remove the timer from the rbtree and replace the
 		 * first entry pointer if necessary.
 		 */
 		if (base->first == &timer->node) {
 			base->first = rb_next(&timer->node);
-			/* Reprogram the clock event device. if enabled */
-			if (reprogram && hrtimer_hres_active())
-				hrtimer_force_reprogram(base->cpu_base);
+			if (next_hrtimer == timer) {
+				/* Reprogram the clock event device. if enabled */
+				if (reprogram && hrtimer_hres_active())
+					hrtimer_force_reprogram(base->cpu_base);
+			}
 		}
 		rb_erase(&timer->node, &base->active);
 	}
@@ -865,25 +877,22 @@ static void __remove_hrtimer(struct hrtimer *timer,
 static inline int
 remove_hrtimer(struct hrtimer *timer, struct hrtimer_clock_base *base)
 {
-	if (hrtimer_is_queued(timer)) {
-		int reprogram;
+	int reprogram;
 
-		/*
-		 * Remove the timer and force reprogramming when high
-		 * resolution mode is active and the timer is on the current
-		 * CPU. If we remove a timer on another CPU, reprogramming is
-		 * skipped. The interrupt event on this CPU is fired and
-		 * reprogramming happens in the interrupt handler. This is a
-		 * rare case and less expensive than a smp call.
-		 */
-		debug_hrtimer_deactivate(timer);
-		timer_stats_hrtimer_clear_start_info(timer);
-		reprogram = base->cpu_base == &__get_cpu_var(hrtimer_bases);
-		__remove_hrtimer(timer, base, HRTIMER_STATE_INACTIVE,
-				 reprogram);
-		return 1;
-	}
-	return 0;
+	/*
+	 * Remove the timer and force reprogramming when high
+	 * resolution mode is active and the timer is on the current
+	 * CPU. If we remove a timer on another CPU, reprogramming is
+	 * skipped. The interrupt event on this CPU is fired and
+	 * reprogramming happens in the interrupt handler. This is a
+	 * rare case and less expensive than a smp call.
+	 */
+	debug_hrtimer_deactivate(timer);
+	timer_stats_hrtimer_clear_start_info(timer);
+	reprogram = base->cpu_base == &__get_cpu_var(hrtimer_bases);
+	__remove_hrtimer(timer, base, HRTIMER_STATE_INACTIVE,
+			reprogram);
+	return 1;
 }
 
 /**
@@ -903,12 +912,26 @@ hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim, unsigned long delta_n
 {
 	struct hrtimer_clock_base *base, *new_base;
 	unsigned long flags;
-	int ret, leftmost;
+	int ret = 0;
+        int leftmost;
 
 	base = lock_hrtimer_base(timer, &flags);
 
 	/* Remove an active timer from the queue: */
-	ret = remove_hrtimer(timer, base);
+	if (hrtimer_is_queued(timer)) {
+		if (timer == __get_cpu_var(hrtimer_bases).next_hrtimer)
+			ret = remove_hrtimer(timer, base);
+		else {
+			debug_hrtimer_deactivate(timer);
+			timer_stats_hrtimer_clear_start_info(timer);
+			if (base->first == &timer->node) {
+				base->first = rb_next(&timer->node);
+			}
+			rb_erase(&timer->node, &base->active);
+			timer->state = HRTIMER_STATE_INACTIVE;
+			ret = 1;
+		}
+	}
 
 	/* Switch the timer base, if necessary: */
 	new_base = switch_hrtimer_base(timer, base);
@@ -1196,6 +1219,7 @@ void hrtimer_interrupt(struct clock_event_device *dev)
 {
 	struct hrtimer_cpu_base *cpu_base = &__get_cpu_var(hrtimer_bases);
 	struct hrtimer_clock_base *base;
+	struct hrtimer *next_hrtimer = NULL;
 	ktime_t expires_next, now;
 	int nr_retries = 0;
 	int i;
@@ -1246,8 +1270,10 @@ void hrtimer_interrupt(struct clock_event_device *dev)
 
 				expires = ktime_sub(hrtimer_get_expires(timer),
 						    base->offset);
-				if (expires.tv64 < expires_next.tv64)
+				if (expires.tv64 < expires_next.tv64) {
 					expires_next = expires;
+					next_hrtimer = timer;
+				}
 				break;
 			}
 
@@ -1258,6 +1284,7 @@ void hrtimer_interrupt(struct clock_event_device *dev)
 	}
 
 	cpu_base->expires_next = expires_next;
+	cpu_base->next_hrtimer = next_hrtimer;
 
 	/* Reprogramming necessary ? */
 	if (expires_next.tv64 != KTIME_MAX) {
-- 
1.5.6.3

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Resending. This time with patch inlined.

 From 6558900969ef1f4492aad4d9a2a87cd8900dee92 Mon Sep 17 00:00:00 2001
From: Ashwin Chaugule <ashwinc@quicinc.com>
Date: Thu, 27 Aug 2009 10:42:48 -0400
Subject: [PATCH][hrtimers]  Cache next hrtimer

    Cached the hrtimer which causes the expire_next
    value to change. This is to avoid unnecessary re-programming
    of the clock events device.

    modified:   include/linux/hrtimer.h
    modified:   kernel/hrtimer.c

    Signed-off-by: Ashwin Chaugule <ashwinc@quicinc.com>
---
 include/linux/hrtimer.h |    5 ++-
 kernel/hrtimer.c        |   81 
+++++++++++++++++++++++++++++++---------------
 2 files changed, 58 insertions(+), 28 deletions(-)

diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index bd37078..dd8fa9b 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -4,7 +4,8 @@
  *  hrtimers - High-resolution kernel timers
  *
  *   Copyright(C) 2005, Thomas Gleixner <tglx@linutronix.de>
- *   Copyright(C) 2005, Red Hat, Inc., Ingo Molnar
+ *   Copyright(C) 2005, Red Hat, Inc., Ingo Molnar
+ *   Copyright(C) 2009, Code Aurora Forum. All rights reserved.
  *
  *  data type definitions, declarations, prototypes
  *
@@ -157,6 +158,7 @@ struct hrtimer_clock_base {
  *            and timers
  * @clock_base:        array of clock bases for this cpu
  * @curr_timer:        the timer which is executing a callback right now
+ * @next_hrtimer:    the hrtimer that caused expires_next to change
  * @expires_next:    absolute time of the next event which was scheduled
  *            via clock_set_next_event()
  * @hres_active:    State of high resolution mode
@@ -169,6 +171,7 @@ struct hrtimer_cpu_base {
     spinlock_t            lock;
     struct hrtimer_clock_base    clock_base[HRTIMER_MAX_CLOCK_BASES];
 #ifdef CONFIG_HIGH_RES_TIMERS
+    struct hrtimer             *next_hrtimer;
     ktime_t                expires_next;
     int                hres_active;
     unsigned long            nr_events;
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index f394d2a..d823987 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -4,6 +4,8 @@
  *  Copyright(C) 2005-2006, Thomas Gleixner <tglx@linutronix.de>
  *  Copyright(C) 2005-2007, Red Hat, Inc., Ingo Molnar
  *  Copyright(C) 2006-2007  Timesys Corp., Thomas Gleixner
+ *  Copyright(C) 2009, Code Aurora Forum. All rights reserved.
+ *
  *
  *  High-resolution kernel timers
  *
@@ -508,8 +510,10 @@ static void hrtimer_force_reprogram(struct 
hrtimer_cpu_base *cpu_base)
          */
         if (expires.tv64 < 0)
             expires.tv64 = 0;
-        if (expires.tv64 < cpu_base->expires_next.tv64)
+        if (expires.tv64 < cpu_base->expires_next.tv64) {
             cpu_base->expires_next = expires;
+            cpu_base->next_hrtimer = timer;
+        }
     }
 
     if (cpu_base->expires_next.tv64 != KTIME_MAX)
@@ -529,6 +533,7 @@ static int hrtimer_reprogram(struct hrtimer *timer,
                  struct hrtimer_clock_base *base)
 {
     ktime_t *expires_next = &__get_cpu_var(hrtimer_bases).expires_next;
+    struct hrtimer *next_hrtimer = 
__get_cpu_var(hrtimer_bases).next_hrtimer;
     ktime_t expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
     int res;
 
@@ -560,8 +565,10 @@ static int hrtimer_reprogram(struct hrtimer *timer,
      * Clockevents returns -ETIME, when the event was in the past.
      */
     res = tick_program_event(expires, 0);
-    if (!IS_ERR_VALUE(res))
+    if (!IS_ERR_VALUE(res)) {
         *expires_next = expires;
+        next_hrtimer = timer;
+    }
     return res;
 }
 
@@ -634,6 +641,7 @@ static inline void hrtimer_init_hres(struct 
hrtimer_cpu_base *base)
 {
     base->expires_next.tv64 = KTIME_MAX;
     base->hres_active = 0;
+    base->next_hrtimer = NULL;
 }
 
 /*
@@ -843,16 +851,20 @@ static void __remove_hrtimer(struct hrtimer *timer,
                  struct hrtimer_clock_base *base,
                  unsigned long newstate, int reprogram)
 {
-    if (timer->state & HRTIMER_STATE_ENQUEUED) {
+    struct hrtimer *next_hrtimer = 
__get_cpu_var(hrtimer_bases).next_hrtimer;
+
+    if (hrtimer_is_queued(timer)) {
         /*
          * Remove the timer from the rbtree and replace the
          * first entry pointer if necessary.
          */
         if (base->first == &timer->node) {
             base->first = rb_next(&timer->node);
-            /* Reprogram the clock event device. if enabled */
-            if (reprogram && hrtimer_hres_active())
-                hrtimer_force_reprogram(base->cpu_base);
+            if (next_hrtimer == timer) {
+                /* Reprogram the clock event device. if enabled */
+                if (reprogram && hrtimer_hres_active())
+                    hrtimer_force_reprogram(base->cpu_base);
+            }
         }
         rb_erase(&timer->node, &base->active);
     }
@@ -865,25 +877,22 @@ static void __remove_hrtimer(struct hrtimer *timer,
 static inline int
 remove_hrtimer(struct hrtimer *timer, struct hrtimer_clock_base *base)
 {
-    if (hrtimer_is_queued(timer)) {
-        int reprogram;
+    int reprogram;
 
-        /*
-         * Remove the timer and force reprogramming when high
-         * resolution mode is active and the timer is on the current
-         * CPU. If we remove a timer on another CPU, reprogramming is
-         * skipped. The interrupt event on this CPU is fired and
-         * reprogramming happens in the interrupt handler. This is a
-         * rare case and less expensive than a smp call.
-         */
-        debug_hrtimer_deactivate(timer);
-        timer_stats_hrtimer_clear_start_info(timer);
-        reprogram = base->cpu_base == &__get_cpu_var(hrtimer_bases);
-        __remove_hrtimer(timer, base, HRTIMER_STATE_INACTIVE,
-                 reprogram);
-        return 1;
-    }
-    return 0;
+    /*
+     * Remove the timer and force reprogramming when high
+     * resolution mode is active and the timer is on the current
+     * CPU. If we remove a timer on another CPU, reprogramming is
+     * skipped. The interrupt event on this CPU is fired and
+     * reprogramming happens in the interrupt handler. This is a
+     * rare case and less expensive than a smp call.
+     */
+    debug_hrtimer_deactivate(timer);
+    timer_stats_hrtimer_clear_start_info(timer);
+    reprogram = base->cpu_base == &__get_cpu_var(hrtimer_bases);
+    __remove_hrtimer(timer, base, HRTIMER_STATE_INACTIVE,
+            reprogram);
+    return 1;
 }
 
 /**
@@ -903,12 +912,26 @@ hrtimer_start_range_ns(struct hrtimer *timer, 
ktime_t tim, unsigned long delta_n
 {
     struct hrtimer_clock_base *base, *new_base;
     unsigned long flags;
-    int ret, leftmost;
+    int ret = 0;
+        int leftmost;
 
     base = lock_hrtimer_base(timer, &flags);
 
     /* Remove an active timer from the queue: */
-    ret = remove_hrtimer(timer, base);
+    if (hrtimer_is_queued(timer)) {
+        if (timer == __get_cpu_var(hrtimer_bases).next_hrtimer)
+            ret = remove_hrtimer(timer, base);
+        else {
+            debug_hrtimer_deactivate(timer);
+            timer_stats_hrtimer_clear_start_info(timer);
+            if (base->first == &timer->node) {
+                base->first = rb_next(&timer->node);
+            }
+            rb_erase(&timer->node, &base->active);
+            timer->state = HRTIMER_STATE_INACTIVE;
+            ret = 1;
+        }
+    }
 
     /* Switch the timer base, if necessary: */
     new_base = switch_hrtimer_base(timer, base);
@@ -1196,6 +1219,7 @@ void hrtimer_interrupt(struct clock_event_device *dev)
 {
     struct hrtimer_cpu_base *cpu_base = &__get_cpu_var(hrtimer_bases);
     struct hrtimer_clock_base *base;
+    struct hrtimer *next_hrtimer = NULL;
     ktime_t expires_next, now;
     int nr_retries = 0;
     int i;
@@ -1246,8 +1270,10 @@ void hrtimer_interrupt(struct clock_event_device 
*dev)
 
                 expires = ktime_sub(hrtimer_get_expires(timer),
                             base->offset);
-                if (expires.tv64 < expires_next.tv64)
+                if (expires.tv64 < expires_next.tv64) {
                     expires_next = expires;
+                    next_hrtimer = timer;
+                }
                 break;
             }
 
@@ -1258,6 +1284,7 @@ void hrtimer_interrupt(struct clock_event_device *dev)
     }
 
     cpu_base->expires_next = expires_next;
+    cpu_base->next_hrtimer = next_hrtimer;
 
     /* Reprogramming necessary ? */
     if (expires_next.tv64 != KTIME_MAX) {
-- 
1.5.6.3

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Thomas Gleixner]

On Thu, 27 Aug 2009, Ashwin Chaugule wrote:
>    Cached the hrtimer which causes the expire_next
>    value to change. This is to avoid unnecessary re-programming
>    of the clock events device.

You forgot to describe the application scenario which triggers this.
 
> @@ -843,16 +851,20 @@ static void __remove_hrtimer(struct hrtimer *timer,
>                  struct hrtimer_clock_base *base,
>                  unsigned long newstate, int reprogram)
> {
> -    if (timer->state & HRTIMER_STATE_ENQUEUED) {
> +    struct hrtimer *next_hrtimer = __get_cpu_var(hrtimer_bases).next_hrtimer;
> +
> +    if (hrtimer_is_queued(timer)) {
>         /*
>          * Remove the timer from the rbtree and replace the
>          * first entry pointer if necessary.
>          */
>         if (base->first == &timer->node) {
>             base->first = rb_next(&timer->node);
> -            /* Reprogram the clock event device. if enabled */
> -            if (reprogram && hrtimer_hres_active())
> -                hrtimer_force_reprogram(base->cpu_base);
> +            if (next_hrtimer == timer) {
> +                /* Reprogram the clock event device. if enabled */
> +                if (reprogram && hrtimer_hres_active())
> +                    hrtimer_force_reprogram(base->cpu_base);
> +            }
>         }
>         rb_erase(&timer->node, &base->active);

So if I'm not totally on the wrong track, that's the meat of the
patch.

Any reason why we can't solve that problem with checking
cpu_base->expires_next against the timer which is deleted ? 

See the patently untested patch below.

Another question which arises is whether we should bother with the
reprogramming at all and just let the last programmed event happen
even when the corresponding timer has been removed.

Thanks,

	tglx
---
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index 49da79a..91d099c 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -906,19 +906,30 @@ static void __remove_hrtimer(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base,
 			     unsigned long newstate, int reprogram)
 {
-	if (timer->state & HRTIMER_STATE_ENQUEUED) {
-		/*
-		 * Remove the timer from the rbtree and replace the
-		 * first entry pointer if necessary.
-		 */
-		if (base->first == &timer->node) {
-			base->first = rb_next(&timer->node);
-			/* Reprogram the clock event device. if enabled */
-			if (reprogram && hrtimer_hres_active())
-				hrtimer_force_reprogram(base->cpu_base);
-		}
-		rb_erase(&timer->node, &base->active);
-	}
+	ktime_t expires;
+
+	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
+		goto out;
+
+	/*
+	 * Remove the timer from the rbtree and replace the first
+	 * entry pointer if necessary.
+	 */
+	rb_erase(&timer->node, &base->active);
+
+	if (base->first != &timer->node)
+		goto out;
+
+	base->first = rb_next(&timer->node);
+	/* Reprogram the clock event device. if enabled */
+	if (!reprogram || !hrtimer_hres_active())
+		goto out;
+
+	expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
+	if (base->cpu_base->expires_next.tv64 == expires.tv64)
+		hrtimer_force_reprogram(base->cpu_base);
+
+out:
 	timer->state = newstate;
 }
 

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:
> You forgot to describe the application scenario which triggers this.
>  
>   
I didn't have anything specific running in userspace to trigger this. 
The sched_timer itself was causing most of the unnecessary 
reprogramming. I reckon, with more applications running, the timer_stats 
will show other timers (hrtimer_wakeup, it_real_fn etc.) that cause this 
effect too.
>> @@ -843,16 +851,20 @@ static void __remove_hrtimer(struct hrtimer *timer,
>>                  struct hrtimer_clock_base *base,
>>                  unsigned long newstate, int reprogram)
>> {
>> -    if (timer->state & HRTIMER_STATE_ENQUEUED) {
>> +    struct hrtimer *next_hrtimer = __get_cpu_var(hrtimer_bases).next_hrtimer;
>> +
>> +    if (hrtimer_is_queued(timer)) {
>>         /*
>>          * Remove the timer from the rbtree and replace the
>>          * first entry pointer if necessary.
>>          */
>>         if (base->first == &timer->node) {
>>             base->first = rb_next(&timer->node);
>> -            /* Reprogram the clock event device. if enabled */
>> -            if (reprogram && hrtimer_hres_active())
>> -                hrtimer_force_reprogram(base->cpu_base);
>> +            if (next_hrtimer == timer) {
>> +                /* Reprogram the clock event device. if enabled */
>> +                if (reprogram && hrtimer_hres_active())
>> +                    hrtimer_force_reprogram(base->cpu_base);
>> +            }
>>         }
>>         rb_erase(&timer->node, &base->active);
>>     
>
> So if I'm not totally on the wrong track, that's the meat of the
> patch.
>   
Yup.
> Any reason why we can't solve that problem with checking
> cpu_base->expires_next against the timer which is deleted ? 
>
> See the patently untested patch below.
>
> Another question which arises is whether we should bother with the
> reprogramming at all and just let the last programmed event happen
> even when the corresponding timer has been removed.
>   
Hm. Interesting approach. See below.
> ---
> diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
> index 49da79a..91d099c 100644
> --- a/kernel/hrtimer.c
> +++ b/kernel/hrtimer.c
> @@ -906,19 +906,30 @@ static void __remove_hrtimer(struct hrtimer *timer,
>  			     struct hrtimer_clock_base *base,
>  			     unsigned long newstate, int reprogram)
>  {
> -	if (timer->state & HRTIMER_STATE_ENQUEUED) {
> -		/*
> -		 * Remove the timer from the rbtree and replace the
> -		 * first entry pointer if necessary.
> -		 */
> -		if (base->first == &timer->node) {
> -			base->first = rb_next(&timer->node);
> -			/* Reprogram the clock event device. if enabled */
> -			if (reprogram && hrtimer_hres_active())
> -				hrtimer_force_reprogram(base->cpu_base);
> -		}
> -		rb_erase(&timer->node, &base->active);
> -	}
> +	ktime_t expires;
> +
> +	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
> +		goto out;
> +
> +	/*
> +	 * Remove the timer from the rbtree and replace the first
> +	 * entry pointer if necessary.
> +	 */
> +	rb_erase(&timer->node, &base->active);
> +
> +	if (base->first != &timer->node)
> +		goto out;
> +
> +	base->first = rb_next(&timer->node);
> +	/* Reprogram the clock event device. if enabled */
> +	if (!reprogram || !hrtimer_hres_active())
> +		goto out;
> +
> +	expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
> +	if (base->cpu_base->expires_next.tv64 == expires.tv64)
> +		hrtimer_force_reprogram(base->cpu_base);
> +
> +out:
>  	timer->state = newstate;
>  }
>
>   

So, you suggest checking the ktime of the hrtimer thats about to expire 
and compare it with expires_next ?
I guess, another reason to go with caching the hrtimer is to avoid 
looping through HRTIMER_MAX_CLOCK_BASES, which may increase to more than 
2 (?) for other architectures, and also all the code flow to arm the 
clock events device.
With the caching approach, I also saw a 4% speedup in various 
application startups too.


Cheers,
Ashwin

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Thomas Gleixner]

On Thu, 27 Aug 2009, Ashwin Chaugule wrote:
> Thomas Gleixner wrote:
> > You forgot to describe the application scenario which triggers this.
> >    
> I didn't have anything specific running in userspace to trigger this. The
> sched_timer itself was causing most of the unnecessary reprogramming. I
> reckon, with more applications running, the timer_stats will show other timers
> (hrtimer_wakeup, it_real_fn etc.) that cause this effect too.

Hmm. That's related to NOHZ I guess. Ok, that's a serious issue and we
need to look at that.

> > So if I'm not totally on the wrong track, that's the meat of the
> > patch.
> >   
> Yup.
> > Any reason why we can't solve that problem with checking
> > cpu_base->expires_next against the timer which is deleted ? 
> > See the patently untested patch below.
> > 
> > Another question which arises is whether we should bother with the
> > reprogramming at all and just let the last programmed event happen
> > even when the corresponding timer has been removed.
> >   
> Hm. Interesting approach. See below.
> 
> So, you suggest checking the ktime of the hrtimer thats about to expire and
> compare it with expires_next ?

What's wrong with that ?

> I guess, another reason to go with caching the hrtimer is to avoid looping
> through HRTIMER_MAX_CLOCK_BASES, which may increase to more than 2 (?) for
> other architectures, and also all the code flow to arm the clock events
> device.
> With the caching approach, I also saw a 4% speedup in various application
> startups too.

Can you reevaluate against my patch please ?

Thanks,

	tglx

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:

> Hmm. That's related to NOHZ I guess. Ok, that's a serious issue and we
> need to look at that.
>   
Yes. I'm running with NOHZ.

>> So, you suggest checking the ktime of the hrtimer thats about to expire and
>> compare it with expires_next ?
>>     
>
> What's wrong with that ?
>   
Nothing :) 

Just didn't know the following could have the same effect. (base->offset is confusing)

+	expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
+	if (base->cpu_base->expires_next.tv64 == expires.tv64)



> Can you reevaluate against my patch please ?
>
>   

The avg. startup time with your patch came to: 26.4 sec (10 runs) as against 25.8 sec (my patch).

To calculate the hit ratio, I made some changes to your code as shown below.

diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index 49da79a..91d099c 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -906,19 +906,30 @@ static void __remove_hrtimer(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base,
 			     unsigned long newstate, int reprogram)
 {
-	if (timer->state & HRTIMER_STATE_ENQUEUED) {
-		/*
-		 * Remove the timer from the rbtree and replace the
-		 * first entry pointer if necessary.
-		 */
-		if (base->first == &timer->node) {
-			base->first = rb_next(&timer->node);
-			/* Reprogram the clock event device. if enabled */
-			if (reprogram && hrtimer_hres_active())
-				hrtimer_force_reprogram(base->cpu_base);
-		}
-		rb_erase(&timer->node, &base->active);
-	}
+	ktime_t expires;
+
+	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
+		goto out;
+
+	/*
+	 * Remove the timer from the rbtree and replace the first
+	 * entry pointer if necessary.
+	 */
+	rb_erase(&timer->node, &base->active);
+
+	if (base->first != &timer->node)
+		goto out;
+
+	base->first = rb_next(&timer->node);
+	/* Reprogram the clock event device. if enabled */
+	if (!reprogram || !hrtimer_hres_active())
+		goto out;

	else
		timer->total_calls++

+
+	expires = ktime_sub(hrtimer_get_expires(timer), base->offset);
+	if (base->cpu_base->expires_next.tv64 == expires.tv64)
		{

			timer->cache_hits++

			hrtimer_force_reprogram(base->cpu_base);
		}
+
+out:
 	timer->state = newstate;
 }



So basically, total_count is the number of times the reprogram would have been forced, cache_hit is number of times it is reduced to.
In my patch I had these counters as follows:


@@ -858,10 +858,18 @@ static void __remove_hrtimer(struct hrtimer *timer,
 		 */
 		if (base->first == &timer->node) {
 			base->first = rb_next(&timer->node);
+#ifdef CONFIG_TIMER_STATS
+			if (reprogram && hrtimer_hres_active())
+				timer->total_calls++;
+#endif
 			if (next_hrtimer == timer) {
 				/* Reprogram the clock event device. if enabled */
-				if (reprogram && hrtimer_hres_active())
+				if (reprogram && hrtimer_hres_active()) {
 					hrtimer_force_reprogram(base->cpu_base);
+#ifdef CONFIG_TIMER_STATS
+					timer->cache_hits++;
+#endif
+				}


Both counters are init'd to 0 in hrtimer_init_hres(timer).

Your patch looks perfect but, total_calls is always equal to cache_hits ?! IOW, the timer we're removing is always the next one to expire, hence we see no benefit.



Cheers,
Ashwin

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Thomas Gleixner]

On Fri, 28 Aug 2009, Ashwin Chaugule wrote:
> Thomas Gleixner wrote:
> Just didn't know the following could have the same effect. (base->offset is
> confusing)

It's simple. We have CLOCK_MONOTONIC and CLOCK_REALTIME. The internal
time base is CLOCK_MONOTONIC. So we use base->offset to convert
CLOCK_REALTIME to CLOCK_MONOTONIC. In case the timer is
CLOCK_MONOTONIC we so the substraction as well, but it simply
subtracts 0 :)
 
> +	/*
> +	 * Remove the timer from the rbtree and replace the first
> +	 * entry pointer if necessary.
> +	 */
> +	rb_erase(&timer->node, &base->active);
> +
> +	if (base->first != &timer->node)
> +		goto out;
> +
> +	base->first = rb_next(&timer->node);

Gah. Looking at the patch with an awake brain makes me feel
stupid. Working version below.

Thanks,

	tglx
---
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index 49da79a..380682b 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -906,19 +906,28 @@ static void __remove_hrtimer(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base,
 			     unsigned long newstate, int reprogram)
 {
-	if (timer->state & HRTIMER_STATE_ENQUEUED) {
-		/*
-		 * Remove the timer from the rbtree and replace the
-		 * first entry pointer if necessary.
-		 */
-		if (base->first == &timer->node) {
-			base->first = rb_next(&timer->node);
-			/* Reprogram the clock event device. if enabled */
-			if (reprogram && hrtimer_hres_active())
+	ktime_t expires;
+
+	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
+		goto out;
+
+	/*
+	 * Remove the timer from the rbtree and replace the first
+	 * entry pointer if necessary.
+	 */
+	if (base->first == &timer->node) {
+		base->first = rb_next(&timer->node);
+		/* Reprogram the clock event device. if enabled */
+		if (reprogram && hrtimer_hres_active()) {
+			expires = ktime_sub(hrtimer_get_expires(timer),
+					    base->offset);
+			if (base->cpu_base->expires_next.tv64 == expires.tv64)
 				hrtimer_force_reprogram(base->cpu_base);
 		}
-		rb_erase(&timer->node, &base->active);
 	}
+
+	rb_erase(&timer->node, &base->active);
+out:
 	timer->state = newstate;
 }
 

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:

> On Fri, 28 Aug 2009, Ashwin Chaugule wrote:
>   
>> Thomas Gleixner wrote:
>> Just didn't know the following could have the same effect. (base->offset is
>> confusing)
>>     
>
> It's simple. We have CLOCK_MONOTONIC and CLOCK_REALTIME. The internal
> time base is CLOCK_MONOTONIC. So we use base->offset to convert
> CLOCK_REALTIME to CLOCK_MONOTONIC. In case the timer is
> CLOCK_MONOTONIC we so the substraction as well, but it simply
> subtracts 0 :)
>  
>   
Cool ! 

> Gah. Looking at the patch with an awake brain makes me feel
> stupid. Working version below.
>   
Um. Same thing happened again. See below .. :)

> ---
> diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
> index 49da79a..380682b 100644
> --- a/kernel/hrtimer.c
> +++ b/kernel/hrtimer.c
> @@ -906,19 +906,28 @@ static void __remove_hrtimer(struct hrtimer *timer,
>  			     struct hrtimer_clock_base *base,
>  			     unsigned long newstate, int reprogram)
>  {
> -	if (timer->state & HRTIMER_STATE_ENQUEUED) {
> -		/*
> -		 * Remove the timer from the rbtree and replace the
> -		 * first entry pointer if necessary.
> -		 */
> -		if (base->first == &timer->node) {
> -			base->first = rb_next(&timer->node);
> -			/* Reprogram the clock event device. if enabled */
> -			if (reprogram && hrtimer_hres_active())
> +	ktime_t expires;
> +
> +	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
> +		goto out;
> +
> +	/*
> +	 * Remove the timer from the rbtree and replace the first
> +	 * entry pointer if necessary.
> +	 */
> +	if (base->first == &timer->node) {
> +		base->first = rb_next(&timer->node);       
>   
> +		/* Reprogram the clock event device. if enabled */
> +		if (reprogram && hrtimer_hres_active()) {
>   

  			   timer->total_calls++;


> +			expires = ktime_sub(hrtimer_get_expires(timer),
> +					    base->offset);
> +			if (base->cpu_base->expires_next.tv64 == expires.tv64)
>   

                          {

                                   timer->cache_hits++;    

>  				hrtimer_force_reprogram(base->cpu_base);
>   
                          }

>  		}
> -		rb_erase(&timer->node, &base->active);
>  	}
> +
> +	rb_erase(&timer->node, &base->active);
> +out:
>  	timer->state = newstate;
>  }
>   
 

Avg startup time 26.4 (10 runs) same as last run.

total_calls is again equal to cache_hits ... 
Its been a while since I wrote my patch. I'll need to look deeper to see if I've done something more. B)
Just to make sure, I ran my patch again, I clearly see cache_hits is always less than total_calls.


Cheers,
Ashwin

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Thomas Gleixner]

On Fri, 28 Aug 2009, Ashwin Chaugule wrote:
> Thomas Gleixner wrote:
> Avg startup time 26.4 (10 runs) same as last run.
> 
> total_calls is again equal to cache_hits ... Its been a while since I wrote my
> patch. I'll need to look deeper to see if I've done something more. B)
> Just to make sure, I ran my patch again, I clearly see cache_hits is always
> less than total_calls.

Hmm. I'd really like to know why that's behaving different. 

Usually there are only timers in the CLOCK_MONOTONIC base during
boot. CLOCK_REALTIME base should be empty most of the time. If my
theory is correct then the number of reprogram events is correct as
well because base[MONOTONIC]->first is always the one which armed the
timer.

Can you add some debug which tells us to which base the removed timer
belongs ?

Thanks,

	tglx

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:
> On Fri, 28 Aug 2009, Ashwin Chaugule wrote:
>   
>> Thomas Gleixner wrote:
>> Avg startup time 26.4 (10 runs) same as last run.
>>
>> total_calls is again equal to cache_hits ... Its been a while since I wrote my
>> patch. I'll need to look deeper to see if I've done something more. B)
>> Just to make sure, I ran my patch again, I clearly see cache_hits is always
>> less than total_calls.
>>     
>
> Hmm. I'd really like to know why that's behaving different. 
>
> Usually there are only timers in the CLOCK_MONOTONIC base during
> boot. CLOCK_REALTIME base should be empty most of the time. If my
> theory is correct then the number of reprogram events is correct as
> well because base[MONOTONIC]->first is always the one which armed the
> timer.
>
> Can you add some debug which tells us to which base the removed timer
> belongs ?
>   

You're right about that. I confirmed that its MONOTONIC all the way. (I didn't think it'd be like that)
However, the reason for different results, *I think* is coming from hrtimer_reprogram,
where we check if the newly enqueued timer is going to expire before the currently armed timer.
Thats where I change /next_hrtimer/ as well.

So, if the expires_next value is changed as a result of hrtimer_enqueue_reprogram, we just raise HRTIMER_SOFTIRQ (rightfully),
but the latest patch doesn't do those checks in this path, coz, we don't call force_reprogram. 


Cheers,
Ashwin

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:

> Hmm. I'd really like to know why that's behaving different. 
>
> Usually there are only timers in the CLOCK_MONOTONIC base during
> boot. CLOCK_REALTIME base should be empty most of the time. If my
> theory is correct then the number of reprogram events is correct as
> well because base[MONOTONIC]->first is always the one which armed the
> timer.
>
>
>   
Okay, I think I figured this out :)

I added some debug to find out how many timers are going to expire_next. 

hrtimer_reprogram()

   if (expires.tv64 == expires_next->tv64)

                if (timer != next_hrtimer)

                        timer->realtime++;  
(lazily reusing realtime here, coz we know its always zero otherwise ;) )

Now timer->realtime is very much non-zero :)

So, now base->first has already changed (leftmost node in the rb tree) and is 
pointing to this new timer node which is also going to expire_next, but hasn't
changed the value of expire_next (we just returned 0).

Therefore, in remove_hrtimer()

+	if (base->first == &timer->node) {
+		base->first = rb_next(&timer->node);
+		/* Reprogram the clock event device. if enabled */
+		if (reprogram && hrtimer_hres_active()) {
+			expires = ktime_sub(hrtimer_get_expires(timer),
+					    base->offset);


timer->node is going to point to the latest timer enqueued which is going 
to expire_next.

With your latest patch, we will force reprogram, but the next node to arm
the timer will be needless, because, its expiry is equal to expires_next.

So, by having a pointer like next_hrtimer, helps to represent all the timers
that are going to expire next, and thats why timer->cache_hits was always less
than timer->total_count.IOW, we avoided re-programming the device, if the 
next timer was going to expire at the same time as the one we just removed.

Thoughts ?

Cheers,

Ashwin

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Thomas Gleixner]

On Sun, 30 Aug 2009, Ashwin Chaugule wrote:
> Thomas Gleixner wrote:
> 
> > Hmm. I'd really like to know why that's behaving different. 
> > Usually there are only timers in the CLOCK_MONOTONIC base during
> > boot. CLOCK_REALTIME base should be empty most of the time. If my
> > theory is correct then the number of reprogram events is correct as
> > well because base[MONOTONIC]->first is always the one which armed the
> > timer.
> >   
> Okay, I think I figured this out :)
> 
> With your latest patch, we will force reprogram, but the next node to arm
> the timer will be needless, because, its expiry is equal to expires_next.
> 
> So, by having a pointer like next_hrtimer, helps to represent all the timers
> that are going to expire next, and thats why timer->cache_hits was always less
> than timer->total_count.IOW, we avoided re-programming the device, if the next
> timer was going to expire at the same time as the one we just removed.

That's not hard to fix by allowing the reprogramming to skip when the
new expiry time is the same as the old one.

I think that allowing the reprogram to skip is catching more cases
than the cached pointer. If the cached pointer is the one which gets
removed we might still reprogram with the same expiry value.

Can you please try the delta patch on top of the last one I sent ?

Thanks,

	tglx
---

--- linux-2.6.orig/kernel/hrtimer.c
+++ linux-2.6/kernel/hrtimer.c
@@ -542,13 +542,14 @@ static inline int hrtimer_hres_active(vo
  * next event
  * Called with interrupts disabled and base->lock held
  */
-static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
+static void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base, int skip_equal)
 {
 	int i;
 	struct hrtimer_clock_base *base = cpu_base->clock_base;
-	ktime_t expires;
+	ktime_t expires, expires_next;
 
-	cpu_base->expires_next.tv64 = KTIME_MAX;
+	expires_next.tv64 = KTIME_MAX;
 
 	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) {
 		struct hrtimer *timer;
@@ -564,10 +565,15 @@ static void hrtimer_force_reprogram(stru
 		 */
 		if (expires.tv64 < 0)
 			expires.tv64 = 0;
-		if (expires.tv64 < cpu_base->expires_next.tv64)
-			cpu_base->expires_next = expires;
+		if (expires.tv64 < expires_next.tv64)
+			expires_next = expires;
 	}
 
+	if (skip_equal && expires_next.tv64 == cpu_base->expires_next.tv64)
+		return;
+
+	cpu_base->expires_next.tv64 = expires_next.tv64;
+
 	if (cpu_base->expires_next.tv64 != KTIME_MAX)
 		tick_program_event(cpu_base->expires_next, 1);
 }
@@ -650,7 +656,7 @@ static void retrigger_next_event(void *a
 	base->clock_base[CLOCK_REALTIME].offset =
 		timespec_to_ktime(realtime_offset);
 
-	hrtimer_force_reprogram(base);
+	hrtimer_force_reprogram(base, 0);
 	spin_unlock(&base->lock);
 }
 
@@ -763,7 +769,8 @@ static int hrtimer_switch_to_hres(void)
 static inline int hrtimer_hres_active(void) { return 0; }
 static inline int hrtimer_is_hres_enabled(void) { return 0; }
 static inline int hrtimer_switch_to_hres(void) { return 0; }
-static inline void hrtimer_force_reprogram(struct hrtimer_cpu_base *base) { }
+static inline void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *base, int skip_equal) { }
 static inline int hrtimer_enqueue_reprogram(struct hrtimer *timer,
 					    struct hrtimer_clock_base *base,
 					    int wakeup)
@@ -922,7 +929,7 @@ static void __remove_hrtimer(struct hrti
 			expires = ktime_sub(hrtimer_get_expires(timer),
 					    base->offset);
 			if (base->cpu_base->expires_next.tv64 == expires.tv64)
-				hrtimer_force_reprogram(base->cpu_base);
+				hrtimer_force_reprogram(base->cpu_base, 1);
 		}
 	}
 

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:

>   
> That's not hard to fix by allowing the reprogramming to skip when the
> new expiry time is the same as the old one.
>
> I think that allowing the reprogram to skip is catching more cases
> than the cached pointer. If the cached pointer is the one which gets
> removed we might still reprogram with the same expiry value.
>   
Um. Wouldn't the cached pointer point to the first (oldest) hrtimer in the 
series of timers with the same expires value ? Then it would be the last
hrtimer to be removed. I'm walking through the rbtree now to confirm this.

> Can you please try the delta patch on top of the last one I sent ?
>   
This looks very good ! 
Our results are almost similar now. However, I think that with this new
patch we're still arming the timer needlessly at least once. This is the
case when we're trying to remove the first (oldest) hrtimer with 
timer->expires = cpu->expires_next, but we forgo the reprogramming, when we 
really shouldn't. At this point, with the current scheme of things, we 
will needlessly wakeup and simply correct the expires_next value by
traversing up the rbtree, to the parent node.

If we knew in advance that this to-be-removed timer, was the oldest hrtimer
of the series, then we could force reprogram, such that we wake up only when the 
parent node timer is really going to expire. This may make a noticeable difference
in power for some devices. 

Another question is, what happens when base->first of REALTIME and MONOTONIC both 
have the same expires ?

Cheers,
Ashwin

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Thomas Gleixner]

On Mon, 31 Aug 2009, Ashwin Chaugule wrote:
> Thomas Gleixner wrote:
> 
> >   That's not hard to fix by allowing the reprogramming to skip when the
> > new expiry time is the same as the old one.
> > 
> > I think that allowing the reprogram to skip is catching more cases
> > than the cached pointer. If the cached pointer is the one which gets
> > removed we might still reprogram with the same expiry value.
> >   
> Um. Wouldn't the cached pointer point to the first (oldest) hrtimer in the
> series of timers with the same expires value ? Then it would be the last
> hrtimer to be removed. I'm walking through the rbtree now to confirm this.
> 
> > Can you please try the delta patch on top of the last one I sent ?
> >   
> This looks very good ! Our results are almost similar now. However, I think
> that with this new
> patch we're still arming the timer needlessly at least once. This is the
> case when we're trying to remove the first (oldest) hrtimer with
> timer->expires = cpu->expires_next, but we forgo the reprogramming, when we
> really shouldn't. At this point, with the current scheme of things, we will
> needlessly wakeup and simply correct the expires_next value by
> traversing up the rbtree, to the parent node.

That only happens, when that timer is the last one in both trees. Then
the resulting reprogramming value is KTIME_MAX and we skip the
reprogramming. That's easy to fix by removing the KTIME_MAX check.
 
> If we knew in advance that this to-be-removed timer, was the oldest hrtimer
> of the series, then we could force reprogram, such that we wake up only when
> the parent node timer is really going to expire. This may make a noticeable
> difference in power for some devices. 
>
> Another question is, what happens when base->first of REALTIME and MONOTONIC
> both have the same expires ?

The skip_equal check covers both. We find out which timer of the two
bases is expiring next and compare the result against
cpu_base->expires_next. If both are identical we skip.

Thanks,

	tglx

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:

>> This looks very good ! Our results are almost similar now. However, I think
>> that with this new
>> patch we're still arming the timer needlessly at least once. This is the
>> case when we're trying to remove the first (oldest) hrtimer with
>> timer->expires = cpu->expires_next, but we forgo the reprogramming, when we
>> really shouldn't. At this point, with the current scheme of things, we will
>> needlessly wakeup and simply correct the expires_next value by
>> traversing up the rbtree, to the parent node.
>>     
>
> That only happens, when that timer is the last one in both trees. Then
> the resulting reprogramming value is KTIME_MAX and we skip the
> reprogramming. That's easy to fix by removing the KTIME_MAX check.
>  
>   
Hmm. Agreed. I'll fix this and send a patch in the next few days. Otherwise, I think all else looks good.


Cheers,
Ashwin

Re: [RFC] [PATCH 1/1] hrtimers: Cache next hrtimer

[Ashwin Chaugule]

Thomas Gleixner wrote:

>>>   
>>>       
>> This looks very good ! Our results are almost similar now. However, I think
>> that with this new
>> patch we're still arming the timer needlessly at least once. This is the
>> case when we're trying to remove the first (oldest) hrtimer with
>> timer->expires = cpu->expires_next, but we forgo the reprogramming, when we
>> really shouldn't. At this point, with the current scheme of things, we will
>> needlessly wakeup and simply correct the expires_next value by
>> traversing up the rbtree, to the parent node.
>>     
>
> That only happens, when that timer is the last one in both trees. Then
> the resulting reprogramming value is KTIME_MAX and we skip the
> reprogramming. That's easy to fix by removing the KTIME_MAX check.
>  
>   
Thinking more about this, I realized that the said case is already taken 
care of by hrtimer_interrupt. We have a while loop there which will traverse
to the parents on both trees and get the correct expires_next value.

In the case in remove_hrtimer, we actually don't want to reprogram the device,
because, the base->first node on the other tree with timer->expires = cpu->expires_next
hasn't expired yet.

Attached final patch here. Is this okay with you ?


>From 867753d2300c358e2a980b70b26beaee40efaf9f Mon Sep 17 00:00:00 2001
From: Ashwin Chaugule <ashwinc@quicinc.com>
Date: Tue, 1 Sep 2009 23:03:33 -0400


	hrtimer: Eliminate needless reprogramming of clock events
 	device.

	On NOHZ systems the following timers,

	-  tick_nohz_restart_sched_tick (tick_sched_timer)
	-  hrtimer_start (tick_sched_timer)

	were reprogramming the clock events device far more often than needed.
	No specific test case was required to observe this effect. This
	occurred because, there was no check to see if the currently removed
	or restarted hrtimer was:

	1) the one which previously armed the clock events device.
	2) going to be replaced by another timer which has the same expiry time.

	This patch avoids the extra programming and results in faster application
 	startup time by ~4% amongst other benefits.

	modified:   kernel/hrtimer.c

	[tglx: simplified code]

	Signed-off-by: Ashwin Chaugule <ashwinc@quicinc.com>
---
 kernel/hrtimer.c |   53 +++++++++++++++++++++++++++++++++++------------------
 1 files changed, 35 insertions(+), 18 deletions(-)

diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index 49da79a..24c8cc3 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -4,6 +4,7 @@
  *  Copyright(C) 2005-2006, Thomas Gleixner <tglx@linutronix.de>
  *  Copyright(C) 2005-2007, Red Hat, Inc., Ingo Molnar
  *  Copyright(C) 2006-2007  Timesys Corp., Thomas Gleixner
+ *  Copyright(C) 2009 Code Aurora Forum., Ashwin Chaugule
  *
  *  High-resolution kernel timers
  *
@@ -542,13 +543,14 @@ static inline int hrtimer_hres_active(void)
  * next event
  * Called with interrupts disabled and base->lock held
  */
-static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
+static void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base, int skip_equal)
 {
 	int i;
 	struct hrtimer_clock_base *base = cpu_base->clock_base;
-	ktime_t expires;
+	ktime_t expires, expires_next;
 
-	cpu_base->expires_next.tv64 = KTIME_MAX;
+	expires_next.tv64 = KTIME_MAX;
 
 	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) {
 		struct hrtimer *timer;
@@ -564,10 +566,15 @@ static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
 		 */
 		if (expires.tv64 < 0)
 			expires.tv64 = 0;
-		if (expires.tv64 < cpu_base->expires_next.tv64)
-			cpu_base->expires_next = expires;
+		if (expires.tv64 < expires_next.tv64)
+			expires_next = expires;
 	}
 
+	if (skip_equal && expires_next.tv64 == cpu_base->expires_next.tv64)
+		return;
+
+	cpu_base->expires_next.tv64 = expires_next.tv64;
+
 	if (cpu_base->expires_next.tv64 != KTIME_MAX)
 		tick_program_event(cpu_base->expires_next, 1);
 }
@@ -650,7 +657,7 @@ static void retrigger_next_event(void *arg)
 	base->clock_base[CLOCK_REALTIME].offset =
 		timespec_to_ktime(realtime_offset);
 
-	hrtimer_force_reprogram(base);
+	hrtimer_force_reprogram(base, 0);
 	spin_unlock(&base->lock);
 }
 
@@ -763,7 +770,8 @@ static int hrtimer_switch_to_hres(void)
 static inline int hrtimer_hres_active(void) { return 0; }
 static inline int hrtimer_is_hres_enabled(void) { return 0; }
 static inline int hrtimer_switch_to_hres(void) { return 0; }
-static inline void hrtimer_force_reprogram(struct hrtimer_cpu_base *base) { }
+static inline void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *base, int skip_equal) { }
 static inline int hrtimer_enqueue_reprogram(struct hrtimer *timer,
 					    struct hrtimer_clock_base *base,
 					    int wakeup)
@@ -906,19 +914,28 @@ static void __remove_hrtimer(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base,
 			     unsigned long newstate, int reprogram)
 {
-	if (timer->state & HRTIMER_STATE_ENQUEUED) {
-		/*
-		 * Remove the timer from the rbtree and replace the
-		 * first entry pointer if necessary.
-		 */
-		if (base->first == &timer->node) {
-			base->first = rb_next(&timer->node);
-			/* Reprogram the clock event device. if enabled */
-			if (reprogram && hrtimer_hres_active())
-				hrtimer_force_reprogram(base->cpu_base);
+	ktime_t expires;
+
+	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
+		goto out;
+
+	/*
+	 * Remove the timer from the rbtree and replace the first
+	 * entry pointer if necessary.
+	 */
+	if (base->first == &timer->node) {
+		base->first = rb_next(&timer->node);
+		/* Reprogram the clock event device. if enabled */
+		if (reprogram && hrtimer_hres_active()) {
+			expires = ktime_sub(hrtimer_get_expires(timer),
+					    base->offset);
+			if (base->cpu_base->expires_next.tv64 == expires.tv64)
+				hrtimer_force_reprogram(base->cpu_base, 1);
 		}
-		rb_erase(&timer->node, &base->active);
 	}
+
+	rb_erase(&timer->node, &base->active);
+out:
 	timer->state = newstate;
 }
 
-- 
1.5.6.3


Cheers,
Ashwin

[tip:timers/core] hrtimer: Eliminate needless reprogramming of clock events device

[tip-bot for Ashwin Chaugule]

Commit-ID:  6198f0b6b0473bb13992fd7fe9ef8145df2d0a30
Gitweb:     http://git.kernel.org/tip/6198f0b6b0473bb13992fd7fe9ef8145df2d0a30
Author:     Ashwin Chaugule <ashwinc@quicinc.com>
AuthorDate: Tue, 1 Sep 2009 23:03:33 -0400
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Tue, 15 Sep 2009 11:02:31 +0200

hrtimer: Eliminate needless reprogramming of clock events device

On NOHZ systems the following timers,

-  tick_nohz_restart_sched_tick (tick_sched_timer)
-  hrtimer_start (tick_sched_timer)

are reprogramming the clock events device far more often than needed
because there is no check to see if the currently removed or restarted
hrtimer is:

1) the one which previously armed the clock events device.
2) going to be replaced by another timer which has the same expiry time.

Avoid the reprogramming in hrtimer_force_reprogram when the new expiry
value which is evaluated from the clock bases is equal to
cpu_base->expires_next.

This results in faster application startup time by ~4%.

[ tglx: simplified initial solution ]

Signed-off-by: Ashwin Chaugule <ashwinc@quicinc.com>
LKML-Reference: <4AA00165.90609@codeaurora.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>


---
 kernel/hrtimer.c |   52 ++++++++++++++++++++++++++++++++++------------------
 1 files changed, 34 insertions(+), 18 deletions(-)

diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index e2f91ec..b53e7ef 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -486,13 +486,14 @@ static inline int hrtimer_hres_active(void)
  * next event
  * Called with interrupts disabled and base->lock held
  */
-static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
+static void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base, int skip_equal)
 {
 	int i;
 	struct hrtimer_clock_base *base = cpu_base->clock_base;
-	ktime_t expires;
+	ktime_t expires, expires_next;
 
-	cpu_base->expires_next.tv64 = KTIME_MAX;
+	expires_next.tv64 = KTIME_MAX;
 
 	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) {
 		struct hrtimer *timer;
@@ -508,10 +509,15 @@ static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
 		 */
 		if (expires.tv64 < 0)
 			expires.tv64 = 0;
-		if (expires.tv64 < cpu_base->expires_next.tv64)
-			cpu_base->expires_next = expires;
+		if (expires.tv64 < expires_next.tv64)
+			expires_next = expires;
 	}
 
+	if (skip_equal && expires_next.tv64 == cpu_base->expires_next.tv64)
+		return;
+
+	cpu_base->expires_next.tv64 = expires_next.tv64;
+
 	if (cpu_base->expires_next.tv64 != KTIME_MAX)
 		tick_program_event(cpu_base->expires_next, 1);
 }
@@ -594,7 +600,7 @@ static void retrigger_next_event(void *arg)
 	base->clock_base[CLOCK_REALTIME].offset =
 		timespec_to_ktime(realtime_offset);
 
-	hrtimer_force_reprogram(base);
+	hrtimer_force_reprogram(base, 0);
 	spin_unlock(&base->lock);
 }
 
@@ -707,7 +713,8 @@ static int hrtimer_switch_to_hres(void)
 static inline int hrtimer_hres_active(void) { return 0; }
 static inline int hrtimer_is_hres_enabled(void) { return 0; }
 static inline int hrtimer_switch_to_hres(void) { return 0; }
-static inline void hrtimer_force_reprogram(struct hrtimer_cpu_base *base) { }
+static inline void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *base, int skip_equal) { }
 static inline int hrtimer_enqueue_reprogram(struct hrtimer *timer,
 					    struct hrtimer_clock_base *base,
 					    int wakeup)
@@ -850,19 +857,28 @@ static void __remove_hrtimer(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base,
 			     unsigned long newstate, int reprogram)
 {
-	if (timer->state & HRTIMER_STATE_ENQUEUED) {
-		/*
-		 * Remove the timer from the rbtree and replace the
-		 * first entry pointer if necessary.
-		 */
-		if (base->first == &timer->node) {
-			base->first = rb_next(&timer->node);
-			/* Reprogram the clock event device. if enabled */
-			if (reprogram && hrtimer_hres_active())
-				hrtimer_force_reprogram(base->cpu_base);
+	ktime_t expires;
+
+	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
+		goto out;
+
+	/*
+	 * Remove the timer from the rbtree and replace the first
+	 * entry pointer if necessary.
+	 */
+	if (base->first == &timer->node) {
+		base->first = rb_next(&timer->node);
+		/* Reprogram the clock event device. if enabled */
+		if (reprogram && hrtimer_hres_active()) {
+			expires = ktime_sub(hrtimer_get_expires(timer),
+					    base->offset);
+			if (base->cpu_base->expires_next.tv64 == expires.tv64)
+				hrtimer_force_reprogram(base->cpu_base, 1);
 		}
-		rb_erase(&timer->node, &base->active);
 	}
+
+	rb_erase(&timer->node, &base->active);
+out:
 	timer->state = newstate;
 }
 

[tip:timers/core] hrtimer: Eliminate needless reprogramming of clock events device

[tip-bot for Ashwin Chaugule]

Commit-ID:  7403f41f19574d6805197e9b97dfa7592003be10
Gitweb:     http://git.kernel.org/tip/7403f41f19574d6805197e9b97dfa7592003be10
Author:     Ashwin Chaugule <ashwinc@quicinc.com>
AuthorDate: Tue, 1 Sep 2009 23:03:33 -0400
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Tue, 15 Sep 2009 17:09:44 +0200

hrtimer: Eliminate needless reprogramming of clock events device

On NOHZ systems the following timers,

-  tick_nohz_restart_sched_tick (tick_sched_timer)
-  hrtimer_start (tick_sched_timer)

are reprogramming the clock events device far more often than needed.
No specific test case was required to observe this effect. This
occurres because there was no check to see if the currently removed or
restarted hrtimer was:

1) the one which previously armed the clock events device.
2) going to be replaced by another timer which has the same expiry time.

Avoid the reprogramming in hrtimer_force_reprogram when the new expiry
value which is evaluated from the clock bases is equal to
cpu_base->expires_next. This results in faster application startup
time by ~4%.

[ tglx: simplified initial solution ]

Signed-off-by: Ashwin Chaugule <ashwinc@quicinc.com>
LKML-Reference: <4AA00165.90609@codeaurora.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>


---
 kernel/hrtimer.c |   53 +++++++++++++++++++++++++++++++++++------------------
 1 files changed, 35 insertions(+), 18 deletions(-)

diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index e2f91ec..1363c1a 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -486,13 +486,14 @@ static inline int hrtimer_hres_active(void)
  * next event
  * Called with interrupts disabled and base->lock held
  */
-static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
+static void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base, int skip_equal)
 {
 	int i;
 	struct hrtimer_clock_base *base = cpu_base->clock_base;
-	ktime_t expires;
+	ktime_t expires, expires_next;
 
-	cpu_base->expires_next.tv64 = KTIME_MAX;
+	expires_next.tv64 = KTIME_MAX;
 
 	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++, base++) {
 		struct hrtimer *timer;
@@ -508,10 +509,15 @@ static void hrtimer_force_reprogram(struct hrtimer_cpu_base *cpu_base)
 		 */
 		if (expires.tv64 < 0)
 			expires.tv64 = 0;
-		if (expires.tv64 < cpu_base->expires_next.tv64)
-			cpu_base->expires_next = expires;
+		if (expires.tv64 < expires_next.tv64)
+			expires_next = expires;
 	}
 
+	if (skip_equal && expires_next.tv64 == cpu_base->expires_next.tv64)
+		return;
+
+	cpu_base->expires_next.tv64 = expires_next.tv64;
+
 	if (cpu_base->expires_next.tv64 != KTIME_MAX)
 		tick_program_event(cpu_base->expires_next, 1);
 }
@@ -594,7 +600,7 @@ static void retrigger_next_event(void *arg)
 	base->clock_base[CLOCK_REALTIME].offset =
 		timespec_to_ktime(realtime_offset);
 
-	hrtimer_force_reprogram(base);
+	hrtimer_force_reprogram(base, 0);
 	spin_unlock(&base->lock);
 }
 
@@ -707,7 +713,8 @@ static int hrtimer_switch_to_hres(void)
 static inline int hrtimer_hres_active(void) { return 0; }
 static inline int hrtimer_is_hres_enabled(void) { return 0; }
 static inline int hrtimer_switch_to_hres(void) { return 0; }
-static inline void hrtimer_force_reprogram(struct hrtimer_cpu_base *base) { }
+static inline void
+hrtimer_force_reprogram(struct hrtimer_cpu_base *base, int skip_equal) { }
 static inline int hrtimer_enqueue_reprogram(struct hrtimer *timer,
 					    struct hrtimer_clock_base *base,
 					    int wakeup)
@@ -850,19 +857,29 @@ static void __remove_hrtimer(struct hrtimer *timer,
 			     struct hrtimer_clock_base *base,
 			     unsigned long newstate, int reprogram)
 {
-	if (timer->state & HRTIMER_STATE_ENQUEUED) {
-		/*
-		 * Remove the timer from the rbtree and replace the
-		 * first entry pointer if necessary.
-		 */
-		if (base->first == &timer->node) {
-			base->first = rb_next(&timer->node);
-			/* Reprogram the clock event device. if enabled */
-			if (reprogram && hrtimer_hres_active())
-				hrtimer_force_reprogram(base->cpu_base);
+	if (!(timer->state & HRTIMER_STATE_ENQUEUED))
+		goto out;
+
+	/*
+	 * Remove the timer from the rbtree and replace the first
+	 * entry pointer if necessary.
+	 */
+	if (base->first == &timer->node) {
+		base->first = rb_next(&timer->node);
+#ifdef CONFIG_HIGH_RES_TIMERS
+		/* Reprogram the clock event device. if enabled */
+		if (reprogram && hrtimer_hres_active()) {
+			ktime_t expires;
+
+			expires = ktime_sub(hrtimer_get_expires(timer),
+					    base->offset);
+			if (base->cpu_base->expires_next.tv64 == expires.tv64)
+				hrtimer_force_reprogram(base->cpu_base, 1);
 		}
-		rb_erase(&timer->node, &base->active);
+#endif
 	}
+	rb_erase(&timer->node, &base->active);
+out:
 	timer->state = newstate;
 }