timers fixes/improvements

This patch replaces and updates 6 timer patches which are currently in -mm tree. This version does not play games with __TIMER_PENDING bit, so incremental patch is not suitable. It is against 2.6.12-rc1. Please comment. I am sending pseudo code in a separate message for easier review.

This patch tries to solve following problems:

1. del_timer_sync() is racy. The timer can be fired again after del_timer_sync have checked all cpus and before it will recheck timer_pending().

2. It has scalability problems. All cpus are scanned to determine if the timer is running on that cpu.

With this patch del_timer_sync is O(1) and no slower than plain del_timer(pending_timer), unless it has to actually wait for completion of the currently running timer.

The only restriction is that the recurring timer should not use add_timer_on().

3. The timers are not serialized wrt to itself.

If CPU_0 does mod_timer(jiffies+1) while the timer is currently running on CPU 1, it is quite possible that local interrupt on CPU_0 will start that timer before it finished on CPU_1.

4. The timers locking is suboptimal. __mod_timer() takes 3 locks at once and still requires wmb() in del_timer/run_timers.

The new implementation takes 2 locks sequentially and does not need memory barriers.

Currently ->base != NULL means that the timer is pending. In that case ->base.lock is used to lock the timer. __mod_timer also takes timer->lock because ->base can be == NULL.

This patch uses timer->entry.next != NULL as indication that the timer is pending. So it does __list_del(), entry->next = NULL instead of list_del() when the timer is deleted.

__run_timers(), del_timer() do not set ->base = NULL anymore, they only clear pending flag, so that del_timer_sync() can wait while timer->base->running_timer == timer.

The ->base field is used for hashed locking only. init_timer() sets ->base = per_cpu(tvec_bases) and it is changed only in __mod_timer(), when the timer changes CPU. Now the timer always can be locked through ->base->lock, so timer_list->lock can be killed and we don't need memory barriers in __run_timers/del_timer.

It is pointless to use ->base directly, it can change at any moment. This patch adds lock_timer_base() helper, which locks timer's base, and checks it is still the same. It also checks that ->base != NULL, see below.

__mod_timer() do not locks both bases at once. It locks timer via lock_timer_base(), __list_del(timer), sets ->base = NULL temporally, and unlocks old_base. Now:
1. This timer can't be seen in __run_timers() via ->entry, it is already removed from list.
2. Nobody can lock this timer because lock_timer_base() waits for ->base != NULL.
3. If the timer was pending - it is still pending, so concurrent del_timer() will spin in lock_timer_base().

Then __mod_timer() locks new_base and adds this timer. I hope it may improve scalability of timers. It also simplifies the code, because AB-BA deadlock is not possible.

On the other hand, when __run_timers()/migrate_timers() locks tvec_bases->lock it can safely traverse ->tvX lists, all timers have valid ->base != NULL and locked.

One problem. TIMER_INITIALIZER can't use per_cpu(tvec_bases). So this patch adds global

	struct timer_base_s {
		spinlock_t lock;
		struct timer_list *running_timer;
	} __init_timer_base;

which is used by TIMER_INITIALIZER. The corresponding fields in struct tvec_t_base_s are replaced by struct timer_base_s t_base.

It is indeed ugly. But this can't have scalability problems. The global __init_timer_base.lock is used only when __mod_timer() is called for the first time AND the timer was compile time initialized. After that the timer migrates to the local CPU.

This patch lessens timer.o size even without deleting now unneeded del_singleshot_timer_sync(). In my opinion it also simplifies the code.

@@ -6,45 +6,33 @@
 #include <linux/spinlock.h>
 #include <linux/stddef.h>
 
-struct tvec_t_base_s;
+struct timer_base_s;
 
 struct timer_list {
 	struct list_head entry;
 	unsigned long expires;
 
-	spinlock_t lock;
 	unsigned long magic;
 
 	void (*function)(unsigned long);
 	unsigned long data;
 
-	struct tvec_t_base_s *base;
+	struct timer_base_s *_base;
 };
 
 #define TIMER_MAGIC	0x4b87ad6e
 
+extern struct timer_base_s __init_timer_base;
+
 #define TIMER_INITIALIZER(_function, _expires, _data) {		\
 		.function = (_function),			\
 		.expires = (_expires),				\
 		.data = (_data),				\
-		.base = NULL,					\
+		._base = &__init_timer_base,			\
 		.magic = TIMER_MAGIC,				\
-		.lock = SPIN_LOCK_UNLOCKED,			\
 	}
 
-/***
- * init_timer - initialize a timer.
- * @timer: the timer to be initialized
- *
- * init_timer() must be done to a timer prior calling *any* of the
- * other timer functions.
- */
-static inline void init_timer(struct timer_list * timer)
-{
-	timer->base = NULL;
-	timer->magic = TIMER_MAGIC;
-	spin_lock_init(&timer->lock);
-}
+void fastcall init_timer(struct timer_list * timer);
 
 /***
  * timer_pending - is a timer pending?

@@ -58,7 +46,7 @@ static inline void init_timer(struct tim
  */
 static inline int timer_pending(const struct timer_list * timer)
 {
-	return timer->base != NULL;
+	return timer->entry.next != NULL;
 }
 
 extern void add_timer_on(struct timer_list *timer, int cpu);

@@ -89,12 +77,12 @@ static inline void add_timer(struct time
 
 #ifdef CONFIG_SMP
   extern int del_timer_sync(struct timer_list *timer);
-  extern int del_singleshot_timer_sync(struct timer_list *timer);
 #else
 # define del_timer_sync(t) del_timer(t)
-# define del_singleshot_timer_sync(t) del_timer(t)
 #endif
 
+#define del_singleshot_timer_sync(t) del_timer_sync(t)
+
 extern void init_timers(void);
 extern void run_local_timers(void);
 extern void it_real_fn(unsigned long);

_

Here it is code snippets for easier review.

typedef struct timer_base_s {
	spinlock_t lock;
	struct timer_list *running_timer;
} timer_base_t;

struct tvec_t_base_s {
	timer_base_t t_base;
	...
} tvec_bases[];

struct timer_list {
	...
	timer_base_t *_base;
};

int timer_pending(struct timer_list * timer)

{
	return timer->entry.next != NULL;
}

void init_timer(struct timer_list *timer)

{
	timer->entry.next = NULL;
	timer->_base = &per_cpu(tvec_bases).t_base;
}

timer_base_t *lock_timer_base(struct timer_list *timer, unsigned long *flags)

{
	for (;;) {
		timer_base_t *base = timer->_base;
		if (base != NULL) {
			spin_lock_irqsave(&base->lock, *flags);
			if (base == timer->_base)
				return base;
			spin_unlock_irqrestore(&base->lock, *flags);
		}
	}
}

int __mod_timer(struct timer_list *timer, unsigned long expires)

{
	timer_base_t *base;
	tvec_base_t *new_base;
	int ret = -1;

	do {
		base = lock_timer_base(timer, &flags);
		new_base = &__get_cpu_var(tvec_bases);

		/* Ensure the timer is serialized. */
		if (base != &new_base->t_base
			&& base->running_timer == timer)
			goto unlock;

		ret = 0;
		if (timer_pending(timer)) {
			__list_del(timer->entry);
			ret = 1;
		}

		if (base != &new_base->t_base) {
			timer->_base = NULL;
			spin_unlock(&base->lock);
			base = &new_base->t_base;
			spin_lock(&base->lock);
			timer->_base = base;
		}

		timer->expires = expires;
		internal_add_timer(new_base, timer);
unlock:
		spin_unlock_irqrestore(&base->lock, flags);
	} while (ret < 0);

	return ret;
}

void detach_timer(struct timer_list *timer)

{
	__list_del(timer->entry);
	entry->next = NULL;
}

int del_timer(struct timer_list *timer)

{
	int ret = 0;

	if (timer_pending(timer)) {
		timer_base_t *base = lock_timer_base(timer);
		if (timer_pending(timer)) {
			detach_timer(timer);
			ret = 1;
		}
		spin_unlock_irqrestore(&base->lock, flags);
	}

	return ret;
}

int del_timer_sync(struct timer_list *timer)

{
	int ret = -1;

	do {
		timer_base_t *base = lock_timer_base(timer);

		if (base->running_timer == timer)
			goto unlock;

		ret = 0;
		if (timer_pending(timer)) {
			detach_timer(timer);
			ret = 1;
		}
unlock:
		spin_unlock_irqrestore(&base->lock, flags);
	} while (ret < 0);

	return ret;
}

void __run_timers(tvec_base_t *base)

{
	spin_lock_irq(&base->t_base.lock);

	for_each_expired_timer(timer) {
		base->t_base.running_timer = timer;
		detach_timer(timer);
		spin_unlock(&base->t_base.lock);
		timer->function(data);
		spin_lock(&base->t_base.lock);
	}
}

namespace cleanliness: i'd suggest s/_base/base.

another detail:

[...]

so we keep looping in __mod_timer() when the timer is running? Couldnt this be a performance hit?

Ingo

I deliberately renamed it to '_base' because then it is much more grepable. But I don't mind doing s/_base/base/ if you prefer.

I hope it is unlikely that __mod_timer() would hit the already running timer, so hopefully this will not degrade the performance. And I don't see a simple alternative to ensure the timer's serialization. At least it spins without interrupts disabling.

Oleg.

i like it. This is nice too:

 2 files changed, 152 insertions(+), 193 deletions(-)

Ingo

Looks ok by me. Andrew, should we let it cook in -mm, or what?

Linus

Sure. Christoph and (I think) Ken have been seeing mysterious misbehaviour which _might_ be due to Oleg's first round of timer patches. I assume C&K will test this new patch?

Yes will be tested. The hangs disappeared here when we removed Oleg's patches.

Andrew Morton wrote on Friday, April 01, 2005 10:33 AM

Yes, we saw kernel hang with previous timer patches. I will give this one a try.

Oh, It never ends. Andrew, please apply this too. Or I can send you updated previous patch if your prefer.

[PATCH] timers fixes/improvements fix

1. Fix compilation with CONFIG_NO_IDLE_HZ:
s/->lock/->t_base.lock/

2. s/_base/base as Ingo suggested.

@@ -17,7 +17,7 @@ struct timer_list {
 	void (*function)(unsigned long);
 	unsigned long data;
 
-	struct timer_base_s *_base;
+	struct timer_base_s *base;
 };
 
 #define TIMER_MAGIC	0x4b87ad6e

@@ -28,7 +28,7 @@ extern struct timer_base_s __init_timer_
 		.function = (_function),			\
 		.expires = (_expires),				\
 		.data = (_data),				\
-		._base = &__init_timer_base,			\
+		.base = &__init_timer_base,			\
 		.magic = TIMER_MAGIC,				\
 	}
 

@@ -172,7 +172,7 @@ EXPORT_SYMBOL(__init_timer_base);
 void fastcall init_timer(struct timer_list *timer)
 {
 	timer->entry.next = NULL;
-	timer->_base = &per_cpu(tvec_bases,
+	timer->base = &per_cpu(tvec_bases,
 			__smp_processor_id()).t_base;
 	timer->magic = TIMER_MAGIC;
 }

@@ -195,11 +195,11 @@ static timer_base_t *lock_timer_base(str
 	timer_base_t *base;
 
 	for (;;) {
-		base = timer->_base;
+		base = timer->base;
 		/* Can be NULL while __mod_timer switches bases */
 		if (likely(base != NULL)) {
 			spin_lock_irqsave(&base->lock, *flags);
-			if (likely(base == timer->_base))
+			if (likely(base == timer->base))
 				return base;
 			spin_unlock_irqrestore(&base->lock, *flags);
 		}

@@ -233,13 +233,13 @@ int __mod_timer(struct timer_list *timer
 		}
 
 		if (base != &new_base->t_base) {
-			timer->_base = NULL;
+			timer->base = NULL;
 			/* Safe: the timer can't be seen via ->entry,
-			 * and lock_timer_base checks ->_base != 0. */
+			 * and lock_timer_base checks ->base != 0. */
 			spin_unlock(&base->lock);
 			base = &new_base->t_base;
 			spin_lock(&base->lock);
-			timer->_base = base;
+			timer->base = base;
 		}
 
 		timer->expires = expires;

@@ -270,7 +270,7 @@ void add_timer_on(struct timer_list *tim
 	check_timer(timer);
 
 	spin_lock_irqsave(&base->t_base.lock, flags);
-	timer->_base = &base->t_base;
+	timer->base = &base->t_base;
 	internal_add_timer(base, timer);
 	spin_unlock_irqrestore(&base->t_base.lock, flags);
 }

@@ -409,7 +409,7 @@ static int cascade(tvec_base_t *base, tv
 		struct timer_list *tmp;
 
 		tmp = list_entry(curr, struct timer_list, entry);
-		BUG_ON(tmp->_base != &base->t_base);
+		BUG_ON(tmp->base != &base->t_base);
 		curr = curr->next;
 		internal_add_timer(base, tmp);
 	}

@@ -491,7 +491,7 @@ unsigned long next_timer_interrupt(void)
 	int i, j;
 
 	base = &__get_cpu_var(tvec_bases);
-	spin_lock(&base->lock);
+	spin_lock(&base->t_base.lock);
 	expires = base->timer_jiffies + (LONG_MAX >> 1);
 	list = 0;
 

@@ -539,7 +539,7 @@ found:
 				expires = nte->expires;
 		}
 	}
-	spin_unlock(&base->lock);
+	spin_unlock(&base->t_base.lock);
 	return expires;
 }
 #endif

@@ -1301,7 +1301,7 @@ static void migrate_timer_list(tvec_base
 	while (!list_empty(head)) {
 		timer = list_entry(head->next, struct timer_list, entry);
 		detach_timer(timer, 0);
-		timer->_base = &new_base->t_base;
+		timer->base = &new_base->t_base;
 		internal_add_timer(new_base, timer);
 	}
 }

We have some strange race conditions as a result of the timer scalability fixes.

ptype_all is set to 0x10:0x10 on faster systems (Xeon 3.6Ghz). Slower systems do fine(Xeon 3.0Ghz) and do not corrupt ptype_all.

Its not clear to me how ptype_all could relate to timer operations but if I apply these timer patches I get ptype_all corruption.

timers-fixes-improvements.patch timers-fixes-improvements-smp_processor_id-fix.patch timers-fixes-improvements-fix.patch timer-deadlock-fix
(It does not matter if the last three are applied)

I put some printk's in an get the following output (2.6.12-rc4 + patches):

net_dev_init: ptype_all = c0569e20:c0569e20
Machine check exception polling timer started.
No per-cpu room for modules.
highmem bounce pool size: 64 pages
Installing knfsd (copyright (C) 1996 [email protected]).
SGI XFS with large block numbers, no debug enabled
Intel E7520/7320/7525 detected.<6>ACPI: Power Button (FF) [PWRF]
PNP: No PS/2 controller found. Probing ports directly.
serio: i8042 AUX port at 0x60,0x64 irq 12
serio: i8042 KBD port at 0x60,0x64 irq 1
Serial: 8250/16550 driver $Revision: 1.90 $ 8 ports, IRQ sharing disabled
ttyS0 at I/O 0x3f8 (irq = 4) is a 16550A
io scheduler noop registered
io scheduler anticipatory registered
io scheduler deadline registered
io scheduler cfq registered
floppy0: no floppy controllers found
loop: loaded (max 8 devices)
Intel(R) PRO/1000 Network Driver - version 5.7.6-k2
Copyright (c) 1999-2004 Intel Corporation.
ACPI: PCI Interrupt
register_netdevice eth%d: ptype_all = 00000010:00000010
ptype_all corrupted = 00000010:00000010. ptype_all fixed up
10 9e 56 c0 10 9e 56 c0 18 9e 56 c0 18 9e 56 c0 10 00 00 00 10 00 00 00 00 00 00 00 00 00 00 00
e1000: eth0: e1000_probe: Intel(R) PRO/1000 Network Connection
ACPI: PCI Interrupt
register_netdevice eth%d: ptype_all = c0569e20:c0569e20

I'd do `nm -n vmlinux', see which data structures the linker placed nearby to ptype_all and then go looking for overruns against them.

ptype_base is an array, but I cannot see any race around ptype_base. So look to see if ptype_base is corrupted as well, keep walking back through memory, see where the scribble starts.

2.6.12-rc3-mm3 has different patches:

timers-fixes-improvements.patch timers-fixes-improvements-smp_processor_id-fix.patch timers-fixes-improvements-fix.patch timers-fix-__mod_timer-vs-__run_timers-deadlock.patch timers-fix-__mod_timer-vs-__run_timers-deadlock-tidy.patch timers-comments-update.patch kernel-timerc-remove-a-goto-construct.patch

There is no corruption around ptype_all as you can see from the log. There is a list of hex numbers which are from ptype_all -8 to ptype_all +8. Looks okay to me.

Ok. Will try these.

Still ptype_all could be accessed (and corrupted) as ptype_base[16].

Christoph, could you please reboot with this patch? Just to be sure.

@@ -157,7 +157,9 @@
 
 static DEFINE_SPINLOCK(ptype_lock);
 static struct list_head ptype_base[16];	/* 16 way hashed list */
+static unsigned long ptype_before[4] = { [0 ... 3] = -1 };
 static struct list_head ptype_all;		/* Taps */
+static unsigned long ptype_after[4] = { [0 ... 3] = -1 };
 
 #ifdef OFFLINE_SAMPLE
 static void sample_queue(unsigned long dummy);

Ok. I added padding before and after ptype_all.
With padding the problem no longer occurs.

However, if the padding is put before ptype_base and after ptype_all then the problem occurs.

So it looks like this is due to writes intended for ptype_base going out of bounds. However, there nothing in the code in net/core/dev.c that would allow this to happen. Also why is the list head set to 0x10:0x10?

I wonder if this problem might benifit from the "breakpoint on write" capability in kgdb. If you are using the kgdb in the mm patch, look in Documentation/i386/kgdb/gdbinit.hw at the hwwbrk macro. You will, of course, have to source this file from gdb to load the macro. Then you can use the gdb command: help hwwbrk to get info on how to use it.

If the location is not written to too often this should help find the offender.

George

George Anzinger   [email protected]
High-res-timers:  http://sourceforge.net/projects/high-res-timers/

So. ptype_base/ptype_all is corrupted before e1000_probe()->register_netdev().

Christoph, please, could you try this patch?

Make sure you are booting with 'init=/bin/sh', kernel should oops.

My kernel oops (as expected) in arp_init()->dev_add_pack(), after 2 successful register_netdevice() calls.

Oleg.

@@ -542,7 +542,7 @@ void __init early_cpu_init(void)
 	umc_init_cpu();
 	early_cpu_detect();
 
-#ifdef CONFIG_DEBUG_PAGEALLOC
+#if	1
 	/* pse is not compatible with on-the-fly unmapping,
 	 * disable it even if the cpus claim to support it.
 	 */

-

We found that this has nothing to do with the timer patches. There is a scribble in pcie_rootport_aspm_quirk that overwrites ptype_all.

quirk_aspm_offset[GET_INDEX(pdev->device, dev->devfn)]= cap_base + 0x10;

does the evil deed. The array offset calculated by GET_INDEX is out of bounds.

The definition of GET_INDEX is suspect:

#define GET_INDEX(a, b) (((a - PCI_DEVICE_ID_INTEL_MCH_PA) << 3) + b)

should this not be

#define GET_INDEX(a, b) ((((a) - PCI_DEVICE_ID_INTEL_MCH_PA) << 3) + \
				((b) & 7))

?

Ick.

Dely, any thoughts about this, or know who would know about it?

thanks,

greg k-h

Btw, i think that drivers/net/e1000/e1000_main.c:e1000_down() is buggy.

It calls del_timer_sync(&adapter->watchdog_timer), but e1000_watchdog() calls schedule_work(e1000_watchdog_task), so the work could be queued after del_timer_sync().

And e1000_watchdog_task() arms timers again.

Note that it's not enough to do flush_scheduled_work() here.

Oleg.

John Linville, who originally proposed the patch (to add e1000_watchdog_task and related code) has since withdrawn the patch.

e1000_down may still be suffering from the del_timer_sync race condition that Oleg identified at the start of this thread.

ganesh.

Tried these. Result is the same:

register_netdevice eth%d: ptype_all = 00000010:00000010 ptype_all corrupted = 00000010:00000010. ptype_all fixed up
10 9e 56 c0 10 9e 56 c0 18 9e 56 c0 18 9e 56 c0 10 00 00 00 10 00 00 00 00 00 00 00 00 00 00 00

__smp_processor_id() is not implemented on all architectures. I'll switch this to _smp_processor_id().

The smp_processor_id() stuff is all rather a twisty maze (looks at Ingo).

It's a rather odd thing which you're doing there. Why does a not-yet-scheduled timer need a ->_base?

Wow, I did not know.

Because all locking goes through timer_list->base->lock now. That is why timer_list->lock can be deleted. The timer is always locked via loc_timer_base().

timer->base == NULL only temporally when __mod_timer() does while switching timer's base:

	base = lock_timer_base(timer);
	timer->base = NULL;
	unlock(base->lock);
		// Nobody can use this timer, lock_timer_base()
		// will spin waiting for ->base != 0
	lock(new_base->lock);
	timer->base = new_base;
	unlock(new_base);

So ->base == NULL means that timer itself is locked, not it's base. That is why __mod_timer() do not need to hold 2 spinlocks at once.

Oleg.

_smp_processor_id() is fine in this case - we pick a CPU at init_timer() time, but we dont need to be non-preemptible when we do so.

Ingo