Timer sync lock checking
cover Timer sync lock checking
Hi,
Here are two patches that implement checking with lockdep that nobody tries to implement something like this:
void timerfn(unsigned long data)
{
spin_lock(&lock);
...
spin_unlock(&lock);
}...
setup
spin_lock_init(&lock); setup_timer(&timer, timerfn, 0);
...
tear_down
spin_lock_bh(&lock); del_timer_sync(&timer); spin_unlock_bh(&lock);
Because of the usage of the fake lock in the timer code, I first needed to teach lockdep about a new "check" value which means that it doesn't check irq-safety. This is required because we patch 2 takes a fake lock around the timerfn, and del_timer_sync() also takes this fake lock, but quite obviously the former runs in softirq context and the latter doesn't necessarily, but clearly it doesn't need to disable softirqs either.
Unlike with the workqueue debugging where I did the same thing, I don't actually know about any such bug. My test code resulted in the warning below, as expected.
johannes
[ 75.083150] =======================================================
[ 75.083163] [ INFO: possible circular locking dependency detected ]
[ 75.083170] 2.6.27-wl-03435-g9b45bb6-dirty #92
[ 75.083177] -------------------------------------------------------
[ 75.083184] rmmod/4365 is trying to acquire lock:
[ 75.083191] (&test_timer){-...}, at: [<c00000000005c834>] .del_timer_sync+0x0/0x94
[ 75.083219]
[ 75.083220] but task is already holding lock:
[ 75.083228] (&lock){-+..}, at: [<d0000000001090b4>] .modexit+0x38/0x70 [timer_test]
[ 75.083253]
[ 75.083254] which lock already depends on the new lock.
[ 75.083257]
[ 75.083263]
[ 75.083265] the existing dependency chain (in reverse order) is:
[ 75.083272]
[ 75.083273] -> #1 (&lock){-+..}:
[ 75.083290] [<c00000000007fc4c>] .lock_acquire+0xa4/0xec
[ 75.083305] [<c0000000003ee0ec>] ._spin_lock+0x50/0xac
[ 75.083320] [<d00000000010902c>] .timerfn+0x2c/0x7c [timer_test]
[ 75.083331] [<c00000000005bdcc>] .run_timer_softirq+0x214/0x2e4
[ 75.083343] [<c0000000000560cc>] .__do_softirq+0xd8/0x1c4
[ 75.083354] [<c00000000000c298>] .do_softirq+0x5c/0xb8
[ 75.083366] [<c000000000055b08>] .irq_exit+0x74/0xe0
[ 75.083376] [<c00000000001e0e8>] .timer_interrupt+0xe4/0x12c
[ 75.083389] [<c000000000003614>] decrementer_common+0x114/0x180
[ 75.083400] [<c000000000011ea8>] .cpu_idle+0xd0/0x200
[ 75.083411] [<c0000000003eee04>] .rest_init+0x8c/0xa4
[ 75.083423] [<c000000000588bc0>] .start_kernel+0x4a0/0x4c8
[ 75.083437] [<c000000000007568>] .start_here_common+0x3c/0x54
[ 75.083449]
[ 75.083450] -> #0 (&test_timer){-...}:
[ 75.083464] [<c00000000007fc4c>] .lock_acquire+0xa4/0xec
[ 75.083474] [<c00000000005c878>] .del_timer_sync+0x44/0x94
[ 75.083486] [<d0000000001090c0>] .modexit+0x44/0x70 [timer_test]
[ 75.083497] [<c00000000008c320>] .sys_delete_module+0x278/0x314
[ 75.083509] [<c0000000000076d4>] syscall_exit+0x0/0x40
[ 75.083520]
[ 75.083521] other info that might help us debug this:
[ 75.083523]
[ 75.083530] 1 lock held by rmmod/4365:
[ 75.083536] #0: (&lock){-+..}, at: [<d0000000001090b4>] .modexit+0x38/0x70 [timer_test]
[ 75.083557]
[ 75.083558] stack backtrace:
[ 75.083563] Call Trace:
[ 75.083571] [c00000020ed8b8d0] [c00000000000f860] .show_stack+0x6c/0x174 (unreliable)
[ 75.083586] [c00000020ed8b980] [c00000000007e008] .print_circular_bug_tail+0xc8/0xec
[ 75.083598] [c00000020ed8ba50] [c00000000007f4d0] .__lock_acquire+0x10ac/0x1784
[ 75.083609] [c00000020ed8bb50] [c00000000007fc4c] .lock_acquire+0xa4/0xec
[ 75.083621] [c00000020ed8bc10] [c00000000005c878] .del_timer_sync+0x44/0x94
[ 75.083633] [c00000020ed8bca0] [d0000000001090c0] .modexit+0x44/0x70 [timer_test]
[ 75.083645] [c00000020ed8bd30] [c00000000008c320] .sys_delete_module+0x278/0x314
[ 75.083657] [c00000020ed8be30] [c0000000000076d4] syscall_exit+0x0/0x40PATCH 1/2 lockdep: implement full check without irq checking
This patch implements a new check type "3" which means "full validation but without irq tracing" in order to allow some certain fake locks that are only added for deadlock detection to not cause inconsistent state warnings which would be inappropriate for them.
--- include/linux/lockdep.h | 4 ++++ kernel/lockdep.c | 2 +- 2 files changed, 5 insertions(+), 1 deletion(-)
include/linux/lockdep.h +4 -0
@@ -301,6 +301,7 @@ extern void lockdep_init_map(struct lock* 0: disabled * 1: simple checks (freeing, held-at-exit-time, etc.) * 2: full validation +* 3: full validation without irq tracing */ extern void lock_acquire(struct lockdep_map *lock, unsigned int subclass, int trylock, int read, int check,
@@ -471,12 +472,15 @@ static inline void print_irqtrace_events#ifdef CONFIG_DEBUG_LOCK_ALLOC # ifdef CONFIG_PROVE_LOCKING # define lock_map_acquire (l) lock_acquire(l, 0, 0, 0, 2, NULL, _THIS_IP_) +# define lock_map_acquire_noirq (l) lock_acquire(l, 0, 0, 0, 3, NULL, _THIS_IP_)# else # define lock_map_acquire (l) lock_acquire(l, 0, 0, 0, 1, NULL, _THIS_IP_) +# define lock_map_acquire_noirq (l) lock_acquire(l, 0, 0, 0, 1, NULL, _THIS_IP_)# endif # define lock_map_release (l) lock_release(l, 1, _THIS_IP_)#else # define lock_map_acquire (l) do { } while (0) +# define lock_map_acquire_noirq (l) do { } while (0)# define lock_map_release (l) do { } while (0)#endif
kernel/lockdep.c +1 -1
@@ -1695,7 +1695,7 @@ static int validate_chain(struct task_st* (If lookup_chain_cache() returns with 1 it acquires * graph_lock for us) */ -if (!hlock->trylock && (hlock->check ==2 ) && +if (!hlock->trylock && (hlock->check >=2 ) &&lookup_chain_cache (curr, hlock, chain_key)) {/* * Check whether last held lock:
Peter Zijlstra
maintainerRe: [PATCH 1/2] lockdep: implement full check without irq checking
Quoted 4 lines · Johannes Berg
This patch implements a new check type "3" which means "full validation but without irq tracing" in order to allow some certain fake locks that are only added for deadlock detection to not cause inconsistent state warnings which would be inappropriate for them.
This thing worries me, can you help my exhausted brain a long a little..
So I take it the idea is to couple the lock chains of the site calling del_timer_sync and the actual timer.
We do this by holding a fake lock while executing the timer, so that its lock chain starts with that lock.
We then acquire the fake lock on del_timer_sync so as to establish a relation.
Now you get warnings about using a lock in hardirq context that was previously used !irq-safe, right?
So why not simply write something like:
del_timer_sync():
local_irq_save(flags); lock_aquire(my fake timer lock); lock_release(...); local_irq_restore(flags);
and make that conditional CONFIG_PROVE_LOCKING and or wrap it up somewhere..
Re: [PATCH 1/2] lockdep: implement full check without irq checking
Quoted 10 lines · Peter Zijlstra
This thing worries me, can you help my exhausted brain a long a little..
So I take it the idea is to couple the lock chains of the site calling
del_timer_syncand the actual timer.We do this by holding a fake lock while executing the timer, so that its lock chain starts with that lock.
We then acquire the fake lock on
del_timer_syncso as to establish a relation.
Right. Same way as the workqueue code. Mind you, I'm not sure this is even worth it, in running it I haven't found a bug and I because timer code may not sleep you can only take spinlocks in them, and I suspect that it's unlikely somebody will try to cancel_sync a timer under a spinlock, though it is of course possible.
Quoted 8 lines
Now you get warnings about using a lock in hardirq context that was previously used !irq-safe, right?
So why not simply write something like:
del_timer_sync():
Quoted 7 lines
local_irq_save(flags); lock_aquire(my fake timer lock); lock_release(...); local_irq_restore(flags);and make that conditional
CONFIG_PROVE_LOCKINGand or wrap it up somewhere..
Yeah, that is possible, but it seemed to me that would affect the performance of del_timer_sync() quite a bit. Not sure it matters. And on powerpc (which I care about) it won't actually affect performance much because we lazily disable IRQs, but still. The >= 2 change also seemed to generate smaller code?
johannes
Peter Zijlstra
maintainerRe: [PATCH 1/2] lockdep: implement full check without irq checking
Quoted 7 lines · Johannes Berg
Quoted 7 lines
del_timer_sync():local_irq_save(flags); lock_aquire(my fake timer lock); lock_release(...); local_irq_restore(flags);
Quoted 8 lines
Quoted 2 lines
and make that conditional
CONFIG_PROVE_LOCKINGand or wrap it up somewhere..Yeah, that is possible, but it seemed to me that would affect the performance of
del_timer_sync()quite a bit. Not sure it matters. And on powerpc (which I care about) it won't actually affect performance much because we lazily disable IRQs, but still. The >= 2 change also seemed to generate smaller code?
Its debug code, and I the >= 2 change makes the code much less obvious.
So I prefer the slightly less performant but conceptually cleaner IRQ disable variant.
Re: [PATCH 1/2] lockdep: implement full check without irq checking
Quoted 18 lines · Peter Zijlstra
Quoted 7 lines · Johannes Berg
Quoted 7 lines
del_timer_sync():local_irq_save(flags); lock_aquire(my fake timer lock); lock_release(...); local_irq_restore(flags);Quoted 8 lines
Quoted 2 lines
and make that conditional
CONFIG_PROVE_LOCKINGand or wrap it up somewhere..Yeah, that is possible, but it seemed to me that would affect the performance of
del_timer_sync()quite a bit. Not sure it matters. And on powerpc (which I care about) it won't actually affect performance much because we lazily disable IRQs, but still. The >= 2 change also seemed to generate smaller code?
Quoted 4 lines
Its debug code, and I the >= 2 change makes the code much less obvious.
So I prefer the slightly less performant but conceptually cleaner IRQ disable variant.
Alright. Thomas, shout if you want this code at all, then I'll clean it up and resend, I don't particularly care, just did it to see if it was possible.
johannes
PATCH 2/2 timer: implement lockdep deadlock detection
In reply to Johannes BergThis modifies the timer code in a way to allow lockdep to detect deadlocks resulting from a lock being taken in the timer function as well as around the del_timer_sync() call.
--- include/linux/timer.h | 93 +++++++++++++++++++++++++++++++++++++++++--------- kernel/timer.c | 40 +++++++++++++++------ 2 files changed, 106 insertions(+), 27 deletions(-)
include/linux/timer.h +78 -15
@@ -21,52 +21,115 @@ struct timer_list {char start_comm[16 ];int start_pid;#endif +#ifdef CONFIG_LOCKDEP +struct lockdep_map lockdep_map; +#endif };extern struct tvec_base boot_tvec_bases; -#define TIMER_INITIALIZER (_function, _expires, _data) { \ - .entry = { .prev = TIMER_ENTRY_STATIC }, \ - .function = (_function), \ - .expires = (_expires), \ - .data = (_data), \ - .base = &boot_tvec_bases, \ +#ifdef CONFIG_LOCKDEP +#define __TIMER_LOCKDEP_MAP_INITIALIZER (fn, name) \ + .lockdep_map = STATIC_LOCKDEP_MAP_INIT(name, fn), +#else +#define __TIMER_LOCKDEP_MAP_INITIALIZER (fn, name) +#endif + +#define TIMER_INITIALIZER (_function, _expires, _data) { \ + .entry = { .prev = TIMER_ENTRY_STATIC }, \ + .function = (_function), \ + .expires = (_expires), \ + .data = (_data), \ + .base = &boot_tvec_bases, \ + __TIMER_LOCKDEP_MAP_INITIALIZER((_function), #_function)\ }#define DEFINE_TIMER (_name, _function, _expires, _data) \ struct timer_list _name = \ TIMER_INITIALIZER(_function, _expires, _data) -void init_timer (struct timer_list *timer); -void init_timer_deferrable (struct timer_list *timer); +void init_timer_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key); +void init_timer_deferrable_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key); + +#ifdef CONFIG_LOCKDEP +#define init_timer (timer) \ + do { \ + static struct lock_class_key __key; \ + init_timer_key((timer), #timer, &__key); \ + } while (0) +#define init_timer_deferrable (timer) \ + do { \ + static struct lock_class_key __key; \ + init_timer_deferrable_key((timer), #timer, &__key); \ + } while (0) +#define init_timer_on_stack (timer) \ + do { \ + static struct lock_class_key __key; \ + init_timer_on_stack_key((timer), #timer, &__key); \ + } while (0) +#define setup_timer (timer, fn, data) \ + do { \ + static struct lock_class_key __key; \ + setup_timer_key((timer), #timer, &__key, (fn), (data));\ + } while (0) +#define setup_timer_on_stack (timer, fn, data) \ + do { \ + static struct lock_class_key __key; \ + setup_timer_on_stack_key((timer), #timer, &__key, \ + (fn), (data)); \ + } while (0) +#else +#define init_timer (timer)\ + init_timer_key((timer), NULL, NULL) +#define init_timer_deferrable (timer)\ + init_timer_deferrable_key((timer), NULL, NULL) +#define init_timer_on_stack (timer)\ + init_timer_on_stack_key((timer)), NULL, NULL) +#define setup_timer (timer, fn, data)\ + setup_timer_key((timer), NULL, NULL, (fn), (data)) +#define setup_timer_on_stack (timer, fn, data)\ + setup_timer_on_stack_key((timer), NULL, NULL, (fn), (data)) +#endif #ifdef CONFIG_DEBUG_OBJECTS_TIMERS -extern void init_timer_on_stack (struct timer_list *timer); +extern void init_timer_on_stack_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key);extern void destroy_timer_on_stack (struct timer_list *timer);#else static inline void destroy_timer_on_stack (struct timer_list *timer) { } -static inline void init_timer_on_stack (struct timer_list *timer) +static inline void init_timer_on_stack_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key) { -init_timer (timer); +init_timer_key (timer, name, key); }#endif -static inline void setup_timer (struct timer_list * timer, +static inline void setup_timer_key (struct timer_list * timer, +const char *name, +struct lock_class_key *key,void (*function)(unsigned long ),unsigned long data) { timer->function = function; timer->data = data; -init_timer (timer); +init_timer_key (timer, name, key); } -static inline void setup_timer_on_stack (struct timer_list *timer, +static inline void setup_timer_on_stack_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key,void (*function)(unsigned long ),unsigned long data) { timer->function = function; timer->data = data; -init_timer_on_stack (timer); +init_timer_on_stack_key (timer, name, key); }/**
kernel/timer.c +28 -12
@@ -422,14 +422,18 @@ static inline void debug_timer_free(strudebug_object_free (timer, &timer_debug_descr); } -static void __init_timer (struct timer_list *timer); - -void init_timer_on_stack (struct timer_list *timer) +static void __init_timer (struct timer_list *timer, +const char *name, +struct lock_class_key *key); + +void init_timer_on_stack_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key) {debug_object_init_on_stack (timer, &timer_debug_descr); -__init_timer (timer); +__init_timer (timer, name, key); } -EXPORT_SYMBOL_GPL (init_timer_on_stack); +EXPORT_SYMBOL_GPL (init_timer_on_stack_key);void destroy_timer_on_stack (struct timer_list *timer) {
@@ -443,7 +447,9 @@ static inline void debug_timer_activate(static inline void debug_timer_deactivate (struct timer_list *timer) { }#endif -static void __init_timer (struct timer_list *timer) +static void __init_timer (struct timer_list *timer, +const char *name, +struct lock_class_key *key) { timer->entry.next =NULL ; timer->base =__raw_get_cpu_var (tvec_bases);
@@ -452,6 +458,7 @@ static void __init_timer(struct timer_li timer->start_pid =-1 ;memset (timer->start_comm,0 ,TASK_COMM_LEN );#endif +lockdep_init_map (&timer->lockdep_map, name, key,0 ); }/**
@@ -461,19 +468,23 @@ static void __init_timer(struct timer_li* init_timer() must be done to a timer prior calling *any* of the * other timer functions. */ -void init_timer (struct timer_list *timer) +void init_timer_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key) {debug_timer_init (timer); -__init_timer (timer); +__init_timer (timer, name, key); } -EXPORT_SYMBOL (init_timer); +EXPORT_SYMBOL (init_timer_key); -void init_timer_deferrable (struct timer_list *timer) +void init_timer_deferrable_key (struct timer_list *timer, +const char *name, +struct lock_class_key *key) { -init_timer (timer); +init_timer_key (timer, name, key);timer_set_deferrable (timer); } -EXPORT_SYMBOL (init_timer_deferrable); +EXPORT_SYMBOL (init_timer_deferrable_key);static inline void detach_timer (struct timer_list *timer,int clear_pending)
@@ -720,6 +731,9 @@ EXPORT_SYMBOL(try_to_del_timer_sync);*/ int del_timer_sync (struct timer_list *timer) { +lock_map_acquire_noirq (&timer->lockdep_map); +lock_map_release (&timer->lockdep_map); +for (;;) {int ret =try_to_del_timer_sync (timer);if (ret >=0 )
@@ -795,7 +809,9 @@ static inline void __run_timers(struct tspin_unlock_irq (&base->lock); {int preempt_count =preempt_count (); +lock_map_acquire_noirq (&timer->lockdep_map);fn (data); +lock_map_release (&timer->lockdep_map);if (preempt_count !=preempt_count ()) {printk (KERN_ERR "huh, entered %p " "with preempt_count %08x, exited"
[PATCH 3/2] tasklet: implement lockdep deadlock detection
In reply to Johannes BergThe tasklet code can deadlock when you try to disable a tasklet under a lock that the tasklet requires. This patch implements lockdep checking for this situation.
---
I don't have an actual instance of this in the kernel either, but my test case triggers correctly.
This was easy, but I think it's probably unlikely that somebody will do this mistake.
include/linux/interrupt.h | 41 ++++++++++++++++++++++++++++++++++++----- kernel/softirq.c | 10 +++++++--- 2 files changed, 43 insertions(+), 8 deletions(-)
include/linux/interrupt.h +36 -5
@@ -299,13 +299,31 @@ struct tasklet_structatomic_t count;void (*func)(unsigned long );unsigned long data; +#ifdef CONFIG_LOCKDEP +struct lockdep_map lock_map; +#endif }; -#define DECLARE_TASKLET (name, func, data) \ -struct tasklet_struct name = { NULL, 0, ATOMIC_INIT(0), func, data } +#ifdef CONFIG_LOCKDEP +#define __TASKLET_LOCK_INIT (n, k) .lock_map = STATIC_LOCKDEP_MAP_INIT(n, k), +#else +#define __TASKLET_LOCK_INIT (n, k) +#endif +#define __DECLARE_TASKLET (name, _func, _data, c)\ +struct tasklet_struct name = { \ + .next = NULL, \ + .state = 0, \ + .count = ATOMIC_INIT(c), \ + .func = _func, \ + .data = _data, \ + __TASKLET_LOCK_INIT(#name, &name) \ +} + +#define DECLARE_TASKLET (name, func, data) \ + __DECLARE_TASKLET(name, func, data, 0)#define DECLARE_TASKLET_DISABLED (name, func, data) \ -struct tasklet_struct name = { NULL, 0, ATOMIC_INIT(1), func, data } + __DECLARE_TASKLET(name, func, data, 1) enum
@@ -328,6 +346,8 @@ static inline void tasklet_unlock(structstatic inline void tasklet_unlock_wait (struct tasklet_struct *t) { +lock_map_acquire_noirq (&t->lock_map); +lock_map_release (&t->lock_map);while (test_bit (TASKLET_STATE_RUN , &(t)->state)) {barrier (); } }#else
@@ -380,8 +400,19 @@ static inline void tasklet_hi_enable(strextern void tasklet_kill (struct tasklet_struct *t);extern void tasklet_kill_immediate (struct tasklet_struct *t,unsigned int cpu); -extern void tasklet_init (struct tasklet_struct *t, -void (*func)(unsigned long ),unsigned long data); +extern void tasklet_init_key (struct tasklet_struct *t, +const char *name,struct lock_class_key *key, +void (*func)(unsigned long ),unsigned long data); + +#ifdef CONFIG_LOCKDEP +#define tasklet_init (t, f, d) \ + do { \ + static struct lock_class_key __key; \ + tasklet_init_key((t), #t, &__key, (f), (d)); \ + } while (0) +#else +#define tasklet_init (t, f, d) tasklet_init_key((t), NULL, NULL, (f), (d)) +#endif /* * Autoprobing for irqs:
kernel/softirq.c +7 -3
@@ -383,7 +383,9 @@ static void tasklet_action(struct softirif (!atomic_read (&t->count)) {if (!test_and_clear_bit (TASKLET_STATE_SCHED , &t->state))BUG (); +lock_map_acquire_noirq (&t->lock_map); t->func (t->data); +lock_map_release (&t->lock_map);tasklet_unlock (t);continue ; }
@@ -435,17 +437,19 @@ static void tasklet_hi_action(struct sof } -void tasklet_init (struct tasklet_struct *t, -void (*func)(unsigned long ),unsigned long data) +void tasklet_init_key (struct tasklet_struct *t, +const char *name,struct lock_class_key *key, +void (*func)(unsigned long ),unsigned long data) { t->next =NULL ; t->state =0 ;atomic_set (&t->count,0 ); t->func = func; t->data = data; +lockdep_init_map (&t->lock_map, name, key,0 ); } -EXPORT_SYMBOL (tasklet_init); +EXPORT_SYMBOL (tasklet_init_key);void tasklet_kill (struct tasklet_struct *t) {