+ add-support-for-deferrable-timers.patch added to -mm tree

PATCH In review [email protected] 6 participants 15 messages Mar 21, 2007 – Mar 29, 2007 3 messages not in the archive

Subsystems (3)

CPU frequency scaling framework High-resolution timers, timer wheel, clockevents Workqueue

lore

Share & tools

lore

[email protected]

author tree notice

2007-03-21 23:54 UTC #0 lore raw

The patch titled
Add support for deferrable timers
has been added to the -mm tree. Its filename is
add-support-for-deferrable-timers.patch

*** Remember to use Documentation/SubmitChecklist when testing your code ***

See http://www.zip.com.au/~akpm/linux/patches/stuff/added-to-mm.txt to find out what to do about this

------------------------------------------------------
Subject: Add support for deferrable timers
From: Venkatesh Pallipadi <[email protected]>

Introduce a new flag for timers - 'deferrable timer' Timers that work normally when system is busy. But, will not cause CPU to come out of idle (just to service this timer), when CPU is idle. Instead, this timer will be serviced when CPU eventually wakes up with a subsequent non-deferrable timer or any other event.

The main advantage of this is to avoid unnecessary timer interrupts when CPU is idle. If the routine currently called by a timer can wait until next event without any issues, this new timer can be used while setting up timer for that routine. This, with dynticks, allows CPUs to be lazy, allowing them to stay in idle for extended period of time by reducing unnecesary wakeup and thereby reducing the power consumption.

This patch: Builds this new timer on top of existing timer infrastructure. It uses last bit in 'base' pointer of timer_list structure to store this deferrable timer flag. __next_timer_interrupt() function skips over these deferrable timers when CPU looks for next timer event for which it has to wake up.

This is exported by a new interface init_timer_deferrable() that can be called in place of regular init_timer().

Signed-off-by Venkatesh Pallipadi <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc john stultz <[email protected]>

Cc Oleg Nesterov <[email protected]>

Cc Dave Jones <[email protected]>

Signed-off-by Andrew Morton <[email protected]>

---

 include/linux/timer.h |    9 ++++
 kernel/timer.c        |   78 ++++++++++++++++++++++++++++++++++++----
 2 files changed, 81 insertions(+), 6 deletions(-)

include/linux/timer.h renamed from include/linux/timer.h~add-support-for-deferrable-timers +9 -0

diff -puN include/linux/timer.h~add-support-for-deferrable-timers include/linux/timer.h
@@ -8,6 +8,14 @@
 
 struct tvec_t_base_s;
 
+extern struct tvec_t_base_s boot_tvec_bases;
+/*
+ * Note that all tvec_bases is 2 byte aligned and lower bit of
+ * base in timer_list is guaranteed to be zero. Use the LSB for
+ * the new flag to indicate whether the timer is deferrable
+ */
+#define TBASE_DEFERRABLE_FLAG		(0x1)
+
 struct timer_list {
 	struct list_head entry;
 	unsigned long expires;

@@ -37,6 +45,7 @@ extern struct tvec_t_base_s boot_tvec_ba
 		TIMER_INITIALIZER(_function, _expires, _data)
 
 void fastcall init_timer(struct timer_list * timer);
+void fastcall init_timer_deferrable(struct timer_list * timer);
 
 static inline void setup_timer(struct timer_list * timer,
 				void (*function)(unsigned long),

kernel/timer.c renamed from kernel/timer.c~add-support-for-deferrable-timers +72 -6

155 lines not on this page · raw message

Patches currently in -mm which might be from [email protected] are

git-acpi.patch workqueue-fix-freezeable-workqueues-implementation.patch workqueue-fix-flush_workqueue-vs-cpu_dead-race.patch workqueue-dont-clear-cwq-thread-until-it-exits.patch workqueue-dont-migrate-pending-works-from-the-dead-cpu.patch add-support-for-deferrable-timers.patch add-support-for-deferrable-timers-tidy.patch export-deferrable-timer-through-workqueue-and-use-it-in-ondemand-governor.patch export-deferrable-timer-through-workqueue-and-use-it-in-ondemand-governor-tidy.patch

A message that is not in the archive (sent off-list or not yet received): [email protected]

Venki Pallipadi

2007-03-27 20:44 UTC #4 lore raw

PATCH 1/1 Add support for deferrable timers (respun)

Quoted 21 lines · Oleg Nesterov

Perhaps we can do something like this,

	struct deferrable_timer {
		struct timer_list timer;
		void (*real_function)(struct deferrable_timer *self);
	};

	static void deferrable_timer_fn(unsigned long data)
	{
		struct deferrable_timer dtimer = (void*)data;
		dtimer->real_function(dtimer);
	}

	void setup_deferrable_timer(struct deferrable_timer *dtimer,
				void (*function)(struct deferrable_timer *self))
	{
		setup_timer(&dtimer->timer, deferrable_timer_fn, dtimer);
		dtimer->real_function = function;
	}

Quoted 6 lines

Now next_timer_interrupt() can check "nte->function == deferrable_timer_fn" to detect a deferrable_timer. I can't say I like this idea very much, though.
However, it would be nice to avoid timer->base manipulation and minimize the changes in timer.c, if possible.

I looked at the above option. It seems more complicated than the patch below, mainly because now we have to have a new set of interfaces for this deferrable_timer exported, which will include init_deferrable_timer, setup_timer, mod_timer etc (in order to do it cleanly) and workqueue needs to change as well to include this deferrable_timer.

So, that got me back to my original patch. I tried to reduce the amount of changes and overhead and hopefully I have gooten it right this time.

Patch below.

Thanks,
Venki

---

Introduce a new flag for timers - deferrable:
Timers that work normally when system is busy. But, will not cause CPU to come out of idle (just to service this timer), when CPU is idle. Instead, this timer will be serviced when CPU eventually wakes up with a subsequent non-deferrable timer.

The main advantage of this is to avoid unnecessary timer interrupts when CPU is idle. If the routine currently called by a timer can wait until next event without any issues, this new timer can be used to setup timer event for that routine. This, with dynticks, allows CPUs to be lazy, allowing them to stay in idle for extended period of time by reducing unnecesary wakeup and thereby reducing the power consumption.

This patch:
Builds this new timer on top of existing timer infrastructure. It uses last bit in 'base' pointer of timer_list structure to store this deferrable timer flag. __next_timer_interrupt() function skips over these deferrable timers when CPU looks for
next timer event for which it has to wake up.

This is exported by a new interface init_timer_deferrable() that can be called in place of regular init_timer().

Signed-off-by Venkatesh Pallipadi <[email protected]>

kernel/timer.c +61 -7

Index: new/kernel/timer.c
===================================================================
@@ -74,7 +74,7 @@
 	tvec_t tv3;
 	tvec_t tv4;
 	tvec_t tv5;
-} ____cacheline_aligned_in_smp;
+} ____cacheline_aligned;
 
 typedef struct tvec_t_base_s tvec_base_t;

@@ -82,6 +82,41 @@
 EXPORT_SYMBOL(boot_tvec_bases);
 static DEFINE_PER_CPU(tvec_base_t *, tvec_bases) = &boot_tvec_bases;
 
+/*
+ * The lowest bit of base ptr in timer is used as a flag to indicate
+ * 'deferrable' nature of the timer. Functions below help us manage that flag.
+ */
+static inline unsigned int tbase_get_deferrable(struct tvec_t_base_s *base)
+{
+	return ((unsigned int)base & TBASE_DEFERRABLE_FLAG);
+}
+
+static inline unsigned int timer_get_deferrable(struct timer_list *timer)
+{
+	return tbase_get_deferrable(timer->base);
+}
+
+static inline struct tvec_t_base_s *timer_get_base(struct timer_list *timer)
+{
+	return ((struct tvec_t_base_s *)((unsigned long)(timer->base) &
+	                                 ~TBASE_DEFERRABLE_FLAG));
+}
+
+static inline void timer_set_deferrable(struct timer_list *timer)
+{
+	timer->base = ((struct tvec_t_base_s *)((unsigned long)(timer->base) |
+	                                        TBASE_DEFERRABLE_FLAG));
+}
+
+/* new_base is guaranteed to have last bit not set, in all callers below */
+static inline void timer_set_base(struct timer_list *timer,
+					struct tvec_t_base_s *old_base,
+					struct tvec_t_base_s *new_base)
+{
+	timer->base = (struct tvec_t_base_s *)((unsigned long)(new_base) |
+	                                       tbase_get_deferrable(old_base));
+}
+
 /**
  * __round_jiffies - function to round jiffies to a full second
  * @j: the time in (absolute) jiffies that should be rounded

@@ -295,6 +330,13 @@
 }
 EXPORT_SYMBOL(init_timer);
 
+void fastcall init_timer_deferrable(struct timer_list *timer)
+{
+	init_timer(timer);
+	timer_set_deferrable(timer);
+}
+EXPORT_SYMBOL(init_timer_deferrable);
+
 static inline void detach_timer(struct timer_list *timer,
 				int clear_pending)
 {

@@ -325,10 +367,11 @@
 	tvec_base_t *base;
 
 	for (;;) {
-		base = timer->base;
+		tvec_base_t *prelock_base = timer->base;
+		base = timer_get_base(timer);
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
-			if (likely(base == timer->base))
+			if (likely(prelock_base == timer->base))
 				return base;
 			/* The timer has migrated to another CPU */
 			spin_unlock_irqrestore(&base->lock, *flags);

@@ -364,12 +407,13 @@
 		 * the timer is serialized wrt itself.
 		 */
 		if (likely(base->running_timer != timer)) {
+			tvec_base_t *old_base = timer->base;
 			/* See the comment in lock_timer_base() */
 			timer->base = NULL;
 			spin_unlock(&base->lock);
 			base = new_base;
 			spin_lock(&base->lock);
-			timer->base = base;
+			timer_set_base(timer, old_base, base);
 		}
 	}

@@ -397,7 +441,7 @@
 	timer_stats_timer_set_start_info(timer);
   	BUG_ON(timer_pending(timer) || !timer->function);
 	spin_lock_irqsave(&base->lock, flags);
-	timer->base = base;
+	timer_set_base(timer, timer->base, base);
 	internal_add_timer(base, timer);
 	spin_unlock_irqrestore(&base->lock, flags);
 }

@@ -548,7 +592,7 @@
 	 * don't have to detach them individually.
 	 */
 	list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
-		BUG_ON(timer->base != base);
+		BUG_ON(timer_get_base(timer) != base);
 		internal_add_timer(base, timer);
 	}

@@ -634,6 +678,9 @@
 	index = slot = timer_jiffies & TVR_MASK;
 	do {
 		list_for_each_entry(nte, base->tv1.vec + slot, entry) {
+ 			if (timer_get_deferrable(nte))
+ 				continue;
+ 
 			found = 1;
 			expires = nte->expires;
 			/* Look at the cascade bucket(s)? */

@@ -1602,6 +1649,13 @@
 						cpu_to_node(cpu));
 			if (!base)
 				return -ENOMEM;
+
+			/* Make sure that tvec_base is 2 byte aligned */
+			if (tbase_get_deferrable(base)) {
+				WARN_ON(1);
+				kfree(base);
+				return -ENOMEM;
+			}
 			memset(base, 0, sizeof(*base));
 			per_cpu(tvec_bases, cpu) = base;
 		} else {

@@ -1643,7 +1697,7 @@
 	while (!list_empty(head)) {
 		timer = list_entry(head->next, struct timer_list, entry);
 		detach_timer(timer, 0);
-		timer->base = new_base;
+		timer_set_base(timer, timer->base, new_base);
 		internal_add_timer(new_base, timer);
 	}
 }

include/linux/timer.h +9 -0

Index: new/include/linux/timer.h
===================================================================
@@ -8,6 +8,14 @@
 
 struct tvec_t_base_s;
 
+extern struct tvec_t_base_s boot_tvec_bases;
+/*
+ * Note that all tvec_bases is 2 byte aligned and lower bit of
+ * base in timer_list is guaranteed to be zero. Use the LSB for
+ * the new flag to indicate whether the timer is deferrable
+ */
+#define TBASE_DEFERRABLE_FLAG		(0x1)
+
 struct timer_list {
 	struct list_head entry;
 	unsigned long expires;

@@ -37,6 +45,7 @@
 		TIMER_INITIALIZER(_function, _expires, _data)
 
 void fastcall init_timer(struct timer_list * timer);
+void fastcall init_timer_deferrable(struct timer_list *timer);
 
 static inline void setup_timer(struct timer_list * timer,
 				void (*function)(unsigned long),

Oleg Nesterov

2007-03-27 21:11 UTC #5 lore raw

Re: [PATCH] Add support for deferrable timers (respun)

kernel/timer.c line 375

Quoted 10 lines · Venki Pallipadi

kernel/timer.c +3 -2

 	for (;;) {
-		base = timer->base;
+		tvec_base_t *prelock_base = timer->base;
+		base = timer_get_base(timer);
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
-			if (likely(base == timer->base))
+			if (likely(prelock_base == timer->base))
 				return base;

I don't think this is correct, at least in theory.

Suppose that

	tvec_base_t *prelock_base = timer->base;
	base = timer_get_base(timer);

are re-ordered (the second LOAD happens after the first one), and the timer changes its base in between. Now, we lock the old base, and return it because "prelock_base == timer->base" == true.

Oleg.

Venki Pallipadi

2007-03-27 21:56 UTC #6 lore raw

Re: [PATCH] Add support for deferrable timers (respun)

Quoted 14 lines · Oleg Nesterov

Review

Quoted 10 lines · Venki Pallipadi

(quoted diff) +3 -2

 	for (;;) {
-		base = timer->base;
+		tvec_base_t *prelock_base = timer->base;
+		base = timer_get_base(timer);
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
-			if (likely(base == timer->base))
+			if (likely(prelock_base == timer->base))
 				return base;

I don't think this is correct, at least in theory.

Quoted 9 lines

Suppose that
	tvec_base_t *prelock_base = timer->base;
	base = timer_get_base(timer);
are re-ordered (the second LOAD happens after the first one), and the timer changes its base in between. Now, we lock the old base, and return it because "prelock_base == timer->base" == true.

Great catch. Yes. this is a theoritical possibility, even though most compilers would load base only once and use it for prelock_base and 'and' it for base. Atleast that is what I see on i386/gcc.

Incremental patch below eliminates this race.

kernel/timer.c +4 -4

Index: new/kernel/timer.c
===================================================================
@@ -96,9 +96,9 @@
 	return tbase_get_deferrable(timer->base);
 }
 
-static inline struct tvec_t_base_s *timer_get_base(struct timer_list *timer)
+static inline struct tvec_t_base_s *tbase_get_base(struct tvec_t_base_s *base)
 {
-	return ((struct tvec_t_base_s *)((unsigned long)(timer->base) &
+	return ((struct tvec_t_base_s *)((unsigned long)base &
 	                                 ~TBASE_DEFERRABLE_FLAG));
 }

@@ -368,7 +368,7 @@
 
 	for (;;) {
 		tvec_base_t *prelock_base = timer->base;
-		base = timer_get_base(timer);
+		base = tbase_get_base(prelock_base);
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
 			if (likely(prelock_base == timer->base))

@@ -592,7 +592,7 @@
 	 * don't have to detach them individually.
 	 */
 	list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
-		BUG_ON(timer_get_base(timer) != base);
+		BUG_ON(tbase_get_base(timer->base) != base);
 		internal_add_timer(base, timer);
 	}

Oleg Nesterov

2007-03-27 22:22 UTC #7 lore raw

Re: [PATCH] Add support for deferrable timers (respun)

Quoted 20 lines · Venki Pallipadi

Incremental patch below eliminates this race.

Index: new/kernel/timer.c
===================================================================

kernel/timer.c +2 -2

@@ -96,9 +96,9 @@
 	return tbase_get_deferrable(timer->base);
 }
 
-static inline struct tvec_t_base_s *timer_get_base(struct timer_list *timer)
+static inline struct tvec_t_base_s *tbase_get_base(struct tvec_t_base_s *base)
 {
-	return ((struct tvec_t_base_s *)((unsigned long)(timer->base) &
+	return ((struct tvec_t_base_s *)((unsigned long)base &
 	                                 ~TBASE_DEFERRABLE_FLAG));
 }

kernel/timer.c line 374

Quoted 8 lines

kernel/timer.c +1 -1

@@ -368,7 +368,7 @@
 
 	for (;;) {
 		tvec_base_t *prelock_base = timer->base;
-		base = timer_get_base(timer);
+		base = tbase_get_base(prelock_base);
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
 			if (likely(prelock_base == timer->base))

Looks correct to me... Personally, I'd prefer

	static tvec_base_t *lock_timer_base(struct timer_list *timer,
						unsigned long *flags)
		__acquires(timer->base->lock)
	{
		tvec_base_t *base;

		for (;;) {
			base = timer_get_base(timer);
			if (likely(base != NULL)) {
				spin_lock_irqsave(&base->lock, *flags);
				if (likely(base == timer_get_base(timer))
					return base;
				/* The timer has migrated to another CPU */
				spin_unlock_irqrestore(&base->lock, *flags);
			}
			cpu_relax();
		}
	}

but this is a matter of taste.

A minor nitpick,

kernel/timer.c

Quoted 8 lines

kernel/timer.c +8 -0

+/* new_base is guaranteed to have last bit not set, in all callers below */
+static inline void timer_set_base(struct timer_list *timer,
+                                       struct tvec_t_base_s *old_base,
+                                       struct tvec_t_base_s *new_base)
+{
+       timer->base = (struct tvec_t_base_s *)((unsigned long)(new_base) |
+                                              tbase_get_deferrable(old_base));
+}

looks a little bit ugly, but may be this is just me. How about

	void timer_set_base(struct timer_list *timer, struct tvec_t_base_s *new_base)
	{
		timer->base = (struct tvec_t_base_s *)
			((unsigned long)(new_base) | tbase_get_deferrable(timer->base));
	}

__mod_timer:

	-	tvec_base_t *old_base = timer->base;
	-	timer->base = NULL;
	+	timer_set_base(timer, NULL);

kernel/timer.c

Quoted 6 lines

kernel/timer.c +6 -0

+                       /* Make sure that tvec_base is 2 byte aligned */
+                       if (tbase_get_deferrable(base)) {
+                               WARN_ON(1);
+                               kfree(base);
+                               return -ENOMEM;
+                       }

Not a comment, but a question: do we really need this?

Oleg.

Oleg Nesterov

2007-03-27 22:31 UTC #8 lore raw

Re: [PATCH] Add support for deferrable timers (respun)

Quoted 9 lines · Oleg Nesterov

looks a little bit ugly, but may be this is just me. How about

	void timer_set_base(struct timer_list *timer, struct tvec_t_base_s *new_base)
	{
		timer->base = (struct tvec_t_base_s *)
			((unsigned long)(new_base) | tbase_get_deferrable(timer->base));
	}

Quoted 6 lines

__mod_timer:

	-	tvec_base_t *old_base = timer->base;
	-	timer->base = NULL;
	+	timer_set_base(timer, NULL);

Damn, forgot to say. With this change timer_get_deferrable(timer) always works, even if changing the timer's base in progress.

Oleg.

Venki Pallipadi

2007-03-27 22:37 UTC #9 lore raw

Re: [PATCH] Add support for deferrable timers (respun)

In reply to Oleg Nesterov

Quoted 33 lines · Oleg Nesterov

kernel/timer.c line 374

Quoted 10 lines · Venki Pallipadi

kernel/timer.c +1 -1

@@ -368,7 +368,7 @@
 
 	for (;;) {
 		tvec_base_t *prelock_base = timer->base;
-		base = timer_get_base(timer);
+		base = tbase_get_base(prelock_base);
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
 			if (likely(prelock_base == timer->base))

Looks correct to me... Personally, I'd prefer

	static tvec_base_t *lock_timer_base(struct timer_list *timer,
						unsigned long *flags)
		__acquires(timer->base->lock)
	{
		tvec_base_t *base;

		for (;;) {
			base = timer_get_base(timer);
			if (likely(base != NULL)) {
				spin_lock_irqsave(&base->lock, *flags);
				if (likely(base == timer_get_base(timer))
					return base;
				/* The timer has migrated to another CPU */
				spin_unlock_irqrestore(&base->lock, *flags);
			}
			cpu_relax();
		}
	}

Quoted 1 line

but this is a matter of taste.

I thought about this. But, chose the other one just to save one additional 'and' overhead.

Quoted 20 lines

A minor nitpick,

Review

Quoted 8 lines

(quoted diff) +8 -0

+/* new_base is guaranteed to have last bit not set, in all callers below */
+static inline void timer_set_base(struct timer_list *timer,
+                                       struct tvec_t_base_s *old_base,
+                                       struct tvec_t_base_s *new_base)
+{
+       timer->base = (struct tvec_t_base_s *)((unsigned long)(new_base) |
+                                              tbase_get_deferrable(old_base));
+}

looks a little bit ugly, but may be this is just me. How about

	void timer_set_base(struct timer_list *timer, struct tvec_t_base_s *new_base)
	{
		timer->base = (struct tvec_t_base_s *)
			((unsigned long)(new_base) | tbase_get_deferrable(timer->base));
	}

Quoted 6 lines

__mod_timer:

	-	tvec_base_t *old_base = timer->base;
	-	timer->base = NULL;
	+	timer_set_base(timer, NULL);

I agree the above suggestion is clean. But, it will have one additional 'and' operation when we set NULL. I saw some concern from Andrew earlier on overhead this patch was adding.

Quoted 9 lines

Review

Quoted 7 lines

(quoted diff) +6 -0

+                       /* Make sure that tvec_base is 2 byte aligned */
+                       if (tbase_get_deferrable(base)) {
+                               WARN_ON(1);
+                               kfree(base);
+                               return -ENOMEM;
+                       }

Not a comment, but a question: do we really need this?

AFAIK, kmalloc_node should return an even address always. I was just being paranoid and wanted to assert it here as otherwise some normal timer may end up being deferred timer.

Thanks,
Venki

Venki Pallipadi

2007-03-28 23:01 UTC #10 lore raw

Re: [PATCH] Add support for deferrable timers (respun-Mar28)

In reply to Oleg Nesterov

Andrew,

Please drop the patch you included yesterday and two incremental patches and use the patch below.

This patch is - yesterday's patch + Your tidy cleanup + minor changes based on comments from Oleg and Andi. This is a lot cleaner (and smaller) than earlier patches.

Thanks,
Venki

The main advantage of this is to avoid unnecessary timer interrupts when CPU is idle. If the routine currently called by a timer can wait until next event without any issues, this new timer can be used to setup timer event for that routine. This, with dynticks, allows CPUs to be lazy, allowing them to stay in idle for extended period of time by reducing unnecesary wakeup and thereby reducing the power consumption.

This patch:
Builds this new timer on top of existing timer infrastructure. It uses last bit in 'base' pointer of timer_list structure to store this deferrable timer flag. __next_timer_interrupt() function skips over these deferrable timers when CPU looks for
next timer event for which it has to wake up.

This is exported by a new interface init_timer_deferrable() that can be called in place of regular init_timer().

Signed-off-by Venkatesh Pallipadi <[email protected]>

kernel/timer.c +57 -8

Index: new/kernel/timer.c
===================================================================
@@ -74,7 +74,7 @@
 	tvec_t tv3;
 	tvec_t tv4;
 	tvec_t tv5;
-} ____cacheline_aligned_in_smp;
+} ____cacheline_aligned;
 
 typedef struct tvec_t_base_s tvec_base_t;

@@ -82,6 +82,37 @@
 EXPORT_SYMBOL(boot_tvec_bases);
 static DEFINE_PER_CPU(tvec_base_t *, tvec_bases) = &boot_tvec_bases;
 
+/*
+ * Note that all tvec_bases is 2 byte aligned and lower bit of
+ * base in timer_list is guaranteed to be zero. Use the LSB for
+ * the new flag to indicate whether the timer is deferrable
+ */
+#define TBASE_DEFERRABLE_FLAG		(0x1)
+
+/* Functions below help us manage 'deferrable' flag */
+static inline unsigned int tbase_get_deferrable(tvec_base_t *base)
+{
+	return ((unsigned int)(unsigned long)base & TBASE_DEFERRABLE_FLAG);
+}
+
+static inline tvec_base_t *tbase_get_base(tvec_base_t *base)
+{
+	return ((tvec_base_t *)((unsigned long)base & ~TBASE_DEFERRABLE_FLAG));
+}
+
+static inline void timer_set_deferrable(struct timer_list *timer)
+{
+	timer->base = ((tvec_base_t *)((unsigned long)(timer->base) |
+	                               TBASE_DEFERRABLE_FLAG));
+}
+
+static inline void
+timer_set_base(struct timer_list *timer, tvec_base_t *new_base)
+{
+	timer->base = (tvec_base_t *)((unsigned long)(new_base) |
+	                              tbase_get_deferrable(timer->base));
+}
+
 /**
  * __round_jiffies - function to round jiffies to a full second
  * @j: the time in (absolute) jiffies that should be rounded

@@ -295,6 +326,13 @@
 }
 EXPORT_SYMBOL(init_timer);
 
+void fastcall init_timer_deferrable(struct timer_list *timer)
+{
+	init_timer(timer);
+	timer_set_deferrable(timer);
+}
+EXPORT_SYMBOL(init_timer_deferrable);
+
 static inline void detach_timer(struct timer_list *timer,
 				int clear_pending)
 {

@@ -325,10 +363,11 @@
 	tvec_base_t *base;
 
 	for (;;) {
-		base = timer->base;
+		tvec_base_t *prelock_base = timer->base;
+		base = tbase_get_base(prelock_base);
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
-			if (likely(base == timer->base))
+			if (likely(prelock_base == timer->base))
 				return base;
 			/* The timer has migrated to another CPU */
 			spin_unlock_irqrestore(&base->lock, *flags);

@@ -365,11 +404,11 @@
 		 */
 		if (likely(base->running_timer != timer)) {
 			/* See the comment in lock_timer_base() */
-			timer->base = NULL;
+			timer_set_base(timer, NULL);
 			spin_unlock(&base->lock);
 			base = new_base;
 			spin_lock(&base->lock);
-			timer->base = base;
+			timer_set_base(timer, base);
 		}
 	}

@@ -397,7 +436,7 @@
 	timer_stats_timer_set_start_info(timer);
   	BUG_ON(timer_pending(timer) || !timer->function);
 	spin_lock_irqsave(&base->lock, flags);
-	timer->base = base;
+	timer_set_base(timer, base);
 	internal_add_timer(base, timer);
 	spin_unlock_irqrestore(&base->lock, flags);
 }

@@ -548,7 +587,7 @@
 	 * don't have to detach them individually.
 	 */
 	list_for_each_entry_safe(timer, tmp, &tv_list, entry) {
-		BUG_ON(timer->base != base);
+		BUG_ON(tbase_get_base(timer->base) != base);
 		internal_add_timer(base, timer);
 	}

@@ -634,6 +673,9 @@
 	index = slot = timer_jiffies & TVR_MASK;
 	do {
 		list_for_each_entry(nte, base->tv1.vec + slot, entry) {
+ 			if (tbase_get_deferrable(nte->base))
+ 				continue;
+ 
 			found = 1;
 			expires = nte->expires;
 			/* Look at the cascade bucket(s)? */

@@ -1602,6 +1644,13 @@
 						cpu_to_node(cpu));
 			if (!base)
 				return -ENOMEM;
+
+			/* Make sure that tvec_base is 2 byte aligned */
+			if (tbase_get_deferrable(base)) {
+				WARN_ON(1);
+				kfree(base);
+				return -ENOMEM;
+			}
 			memset(base, 0, sizeof(*base));
 			per_cpu(tvec_bases, cpu) = base;
 		} else {

@@ -1643,7 +1692,7 @@
 	while (!list_empty(head)) {
 		timer = list_entry(head->next, struct timer_list, entry);
 		detach_timer(timer, 0);
-		timer->base = new_base;
+		timer_set_base(timer, new_base);
 		internal_add_timer(new_base, timer);
 	}
 }

include/linux/timer.h +1 -0

Index: new/include/linux/timer.h
===================================================================
@@ -37,6 +37,7 @@
 		TIMER_INITIALIZER(_function, _expires, _data)
 
 void fastcall init_timer(struct timer_list * timer);
+void fastcall init_timer_deferrable(struct timer_list *timer);
 
 static inline void setup_timer(struct timer_list * timer,
 				void (*function)(unsigned long),

Andrew Morton

author

2007-03-29 00:11 UTC #11 lore raw

Re: [PATCH] Add support for deferrable timers (respun-Mar28)

Quoted 2 lines · On Wed, 28 Mar 2007 16:00:21 -0700 Venki Pallipadi…

Please drop the patch you included yesterday and two incremental patches and use the patch below.

As you saw, I went and turned it into an incremental patch again. It makes it easier to see what changed, but harder to see the whole thing.

Quoted 1 line

Introduce a new flag for timers - deferrable:

OK, but there's nothing in-kernel whcih actually uses this.

It would be good to identify some timer users which can be switched over (as many as possible, really) so this thing actually gets some runtime testing.

Venki Pallipadi

2007-03-29 01:00 UTC #12 lore raw

Re: [PATCH] Add support for deferrable timers (respun-Mar28)

Quoted 9 lines · Andrew Morton

Quoted 2 lines · On Wed, 28 Mar 2007 16:00:21 -0700 Venki Pallipadi…
Please drop the patch you included yesterday and two incremental patches and use the patch below.
As you saw, I went and turned it into an incremental patch again. It makes it easier to see what changed, but harder to see the whole thing.

Quoted 6 lines

Quoted 1 line
Introduce a new flag for timers - deferrable:
OK, but there's nothing in-kernel whcih actually uses this.
It would be good to identify some timer users which can be switched over (as many as possible, really) so this thing actually gets some runtime testing.

ondemand is the biggest offender and the patch below reduces the number of interrupts by 50% or more (depending on HZ) on different test systems here.

Yes. There are quite a few other timers inside kernel that can be migrated. I will use timer_stats and track others and send in the patches soon.

Thanks,
Venki

------

Add a new deferrable delayed work init. This can be used to schedule work that are 'unimportant' when CPU is idle and can be called later, when CPU eventually comes out of idle.

Use this init in cpufreq ondemand governor.

Signed-off-by Venkatesh Pallipadi <[email protected]>

drivers/cpufreq/cpufreq_ondemand.c +1 -1

Index: new/drivers/cpufreq/cpufreq_ondemand.c
===================================================================
@@ -470,7 +470,7 @@
 	dbs_info->enable = 1;
 	ondemand_powersave_bias_init();
 	dbs_info->sample_type = DBS_NORMAL_SAMPLE;
-	INIT_DELAYED_WORK(&dbs_info->work, do_dbs_timer);
+	INIT_DELAYED_WORK_DEFERRABLE(&dbs_info->work, do_dbs_timer);
 	queue_delayed_work_on(dbs_info->cpu, kondemand_wq, &dbs_info->work,
 	                      delay);
 }

include/linux/workqueue.h +6 -0

Index: new/include/linux/workqueue.h
===================================================================
@@ -89,6 +89,12 @@
 		init_timer(&(_work)->timer);			\
 	} while (0)
 
+#define INIT_DELAYED_WORK_DEFERRABLE(_work, _func)			\
+	do {							\
+		INIT_WORK(&(_work)->work, (_func));		\
+		init_timer_deferrable(&(_work)->timer);		\
+	} while (0)
+
 /**
  * work_pending - Find out whether a work item is currently pending
  * @work: The work item in question

Andi Kleen

2007-03-29 11:41 UTC #13 lore raw

Re: [PATCH] Add support for deferrable timers (respun-Mar28)

Quoted 3 lines

ondemand is the biggest offender and the patch below reduces the number of interrupts by 50% or more (depending on HZ) on different test systems here.

Cool!

Quoted 3 lines

Yes. There are quite a few other timers inside kernel that can be migrated. I will use timer_stats and track others and send in the patches soon.

Longer term it might make sense to even expose this as a option to user space. Maybe as a new timer in setitimer()? This might safe power with "wiggling desktop applets" too.

-Andi

Kyle Moffett

2007-03-29 11:51 UTC #14 lore raw

Re: [PATCH] Add support for deferrable timers (respun-Mar28)

Quoted 7 lines · Andi Kleen

Quoted 1 line
ondemand is the biggest offender and the patch below reduces the number of interrupts by 50% or more (depending on HZ) on different test systems here.
Cool!
Quoted 1 line
Yes. There are quite a few other timers inside kernel that can be migrated. I will use timer_stats and track others and send in the patches soon.
Longer term it might make sense to even expose this as a option to user space. Maybe as a new timer in setitimer()? This might safe power with "wiggling desktop applets" too.

Might also be useful to add an extra option to "top" to reduce the polling frequency if the system is otherwise idle. A fixed 30-sec timer and a deferrable 1-sec timer or somesuch?

Cheers,
Kyle Moffett

Andi Kleen

2007-03-29 11:59 UTC #15 lore raw

Re: [PATCH] Add support for deferrable timers (respun-Mar28)

Quoted 4 lines

Might also be useful to add an extra option to "top" to reduce the polling frequency if the system is otherwise idle. A fixed 30-sec timer and a deferrable 1-sec timer or somesuch?

Hmm, i think the current implementation is per CPU. top really would like to have one that applies to all CPUs though.

Thinking about it for sane user space semantics it would probably need a global implementation anyways.

Perhaps it could use the same infrastructure as RCU does to handle this?

-Andi

Andi Kleen

2007-03-28 10:07 UTC #16 lore raw

Re: [PATCH] Add support for deferrable timers (respun)

In reply to Venki Pallipadi

kernel/timer.c line 77

Quoted 7 lines · Venki Pallipadi

+++ new/kernel/timer.c 2007-03-26 15:19:35.000000000 -0800
kernel/timer.c +1 -1
@@ -74,7 +74,7 @@
 	tvec_t tv3;
 	tvec_t tv4;
 	tvec_t tv5;
-} ____cacheline_aligned_in_smp;
+} ____cacheline_aligned;

Why this change? It should be aligned to 2 bytes anyways.

kernel/timer.c line 91

Quoted 9 lines

kernel/timer.c +7 -0

 static DEFINE_PER_CPU(tvec_base_t *, tvec_bases) = &boot_tvec_bases;
 
+/*
+ * The lowest bit of base ptr in timer is used as a flag to indicate
+ * 'deferrable' nature of the timer. Functions below help us manage that flag.
+ */
+static inline unsigned int tbase_get_deferrable(struct tvec_t_base_s *base)
+{
+	return ((unsigned int)base & TBASE_DEFERRABLE_FLAG);

This will warn on 64bit for cast ptr -> int

-Andi

Venki Pallipadi

2007-03-28 16:42 UTC #17 lore raw

Re: [PATCH] Add support for deferrable timers (respun)

Quoted 10 lines · Andi Kleen

kernel/timer.c line 77
Quoted 7 lines · Venki Pallipadi
+++ new/kernel/timer.c 2007-03-26 15:19:35.000000000 -0800
kernel/timer.c +1 -1
@@ -74,7 +74,7 @@
 	tvec_t tv3;
 	tvec_t tv4;
 	tvec_t tv5;
-} ____cacheline_aligned_in_smp;
+} ____cacheline_aligned;
Why this change? It should be aligned to 2 bytes anyways.

Just wanted to be cautious of all archs and all compilers.

Quoted 11 lines

kernel/timer.c line 91

Quoted 9 lines

kernel/timer.c +7 -0

 static DEFINE_PER_CPU(tvec_base_t *, tvec_bases) = &boot_tvec_bases;
 
+/*
+ * The lowest bit of base ptr in timer is used as a flag to indicate
+ * 'deferrable' nature of the timer. Functions below help us manage that flag.
+ */
+static inline unsigned int tbase_get_deferrable(struct tvec_t_base_s *base)
+{
+	return ((unsigned int)base & TBASE_DEFERRABLE_FLAG);

This will warn on 64bit for cast ptr -> int

OK. Will change this to ptr->long->int in the update patch.

Thanks,
Venki