hrtimers: Cache next hrtimer

From: Ashwin Chaugule <[email protected]>
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

---
 include/linux/hrtimer.h |    5 ++-
 kernel/hrtimer.c        |   81 +++++++++++++++++++++++++++++++---------------
 2 files changed, 58 insertions(+), 28 deletions(-)

index bd37078..dd8fa9b 100644
@@ -4,7 +4,8 @@
  *  hrtimers - High-resolution kernel timers
  *
  *   Copyright(C) 2005, Thomas Gleixner <[email protected]>
- *   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;

1.5.6.3

Resending. This time with patch inlined.

From 6558900969ef1f4492aad4d9a2a87cd8900dee92 Mon Sep 17 00:00:00 2001
From: Ashwin Chaugule <[email protected]>
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

---
include/linux/hrtimer.h | 5 ++-
kernel/hrtimer.c | 81 +++++++++++++++++++++++++++++++---------------

2 files changed, 58 insertions(+), 28 deletions(-)

index bd37078..dd8fa9b 100644
@@ -4,7 +4,8 @@
 *  hrtimers - High-resolution kernel timers
 *
 *   Copyright(C) 2005, Thomas Gleixner <[email protected]>
- *   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;

index f394d2a..d823987 100644
@@ -4,6 +4,8 @@
 *  Copyright(C) 2005-2006, Thomas Gleixner <[email protected]>
 *  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

You forgot to describe the application scenario which triggers this.

index 49da79a..91d099c 100644
@@ -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;
 }
 

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.

Yup.

Hm. Interesting approach. See below.

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

What's wrong with that ?

Can you reevaluate against my patch please ?

Thanks,

tglx

Yes. I'm running with NOHZ.

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)

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.

index 49da79a..91d099c 100644
@@ -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

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 :)

index 49da79a..380682b 100644
@@ -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;
 }
 

Cool !

Um. Same thing happened again. See below .. :)

                         {

                                  timer->cache_hits++;    

                         }

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

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

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

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
---

@@ -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);
 		}
 	}
 

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.

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

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.

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

Hmm. Agreed. I'll fix this and send a patch in the next few days. Otherwise, I think all else looks good.

Cheers,
Ashwin

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: Ashwin Chaugule <[email protected]>
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]

---
kernel/hrtimer.c | 53 +++++++++++++++++++++++++++++++++++------------------

1 files changed, 35 insertions(+), 18 deletions(-)

index 49da79a..24c8cc3 100644
@@ -4,6 +4,7 @@
 *  Copyright(C) 2005-2006, Thomas Gleixner <[email protected]>
 *  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

Commit-ID:  6198f0b6b0473bb13992fd7fe9ef8145df2d0a30
Gitweb:     http://git.kernel.org/tip/6198f0b6b0473bb13992fd7fe9ef8145df2d0a30
Author:     Ashwin Chaugule <[email protected]>
AuthorDate: Tue, 1 Sep 2009 23:03:33 -0400
Committer:  Thomas Gleixner <[email protected]>
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 ]

LKML-Reference: <[email protected]>

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

index e2f91ec..b53e7ef 100644
@@ -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;
 }
 

Commit-ID:  7403f41f19574d6805197e9b97dfa7592003be10
Gitweb:     http://git.kernel.org/tip/7403f41f19574d6805197e9b97dfa7592003be10
Author:     Ashwin Chaugule <[email protected]>
AuthorDate: Tue, 1 Sep 2009 23:03:33 -0400
Committer:  Thomas Gleixner <[email protected]>
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 ]

LKML-Reference: <[email protected]>

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

index e2f91ec..1363c1a 100644
@@ -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;
 }