Name: Spinlock Data Debugging Status: Untested Signed-off-by: Rusty Russell Netfilter has its own list macros, predating the list.h ones, which call a checker which ensures we are holding the right lock, in the right mode. Instead, we should use the generic list macros, but it'd be nice not to lose the debugging checks: they really helped when playing with the code. So add a __check_lock() macro which takes a pointer and a "needs write access" flag, and sprinkle it throughout list.h and a few other strategic places. Index: linux-2.6.11-rc2-bk2-Netfilter/init/Kconfig =================================================================== --- linux-2.6.11-rc2-bk2-Netfilter.orig/init/Kconfig 2005-01-24 11:14:10.000000000 +1100 +++ linux-2.6.11-rc2-bk2-Netfilter/init/Kconfig 2005-01-25 16:01:53.000000000 +1100 @@ -276,6 +276,16 @@ reported. KALLSYMS_EXTRA_PASS is only a temporary workaround while you wait for kallsyms to be fixed. +config DEBUG_LOCKING + bool "Check spinlocks around structures" + depends on DEBUG_KERNEL && SMP + help + Extra (slow) checks apply to all list iteration, and + several other places, where code has registered which locks + cover which datastructures. Useful for checking new code. + + Say N. + config FUTEX bool "Enable futex support" if EMBEDDED default y Index: linux-2.6.11-rc2-bk2-Netfilter/kernel/Makefile =================================================================== --- linux-2.6.11-rc2-bk2-Netfilter.orig/kernel/Makefile 2005-01-25 15:56:35.000000000 +1100 +++ linux-2.6.11-rc2-bk2-Netfilter/kernel/Makefile 2005-01-25 16:01:53.000000000 +1100 @@ -26,6 +26,7 @@ obj-$(CONFIG_KPROBES) += kprobes.o obj-$(CONFIG_SYSFS) += ksysfs.o obj-$(CONFIG_GENERIC_HARDIRQS) += irq/ +obj-$(CONFIG_DEBUG_LOCKING) += lockdebug.o ifneq ($(CONFIG_IA64),y) # According to Alan Modra , the -fno-omit-frame-pointer is Index: linux-2.6.11-rc2-bk2-Netfilter/kernel/lockdebug.c =================================================================== --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ linux-2.6.11-rc2-bk2-Netfilter/kernel/lockdebug.c 2005-01-25 16:04:32.906389944 +1100 @@ -0,0 +1,186 @@ +#include +#include +#include +#include +#include +#include +#include + +/* We use an rbtree for locks which don't overlap, and linked list for + * locks which do. */ +struct lock_check +{ + struct rb_node rb; + + /* Inclusive range. */ + unsigned long start, end; + /* Called with preempt disabled, must not sleep. */ + int (*check)(const void *addr, void *info, int writable); + + void *info; + + struct lock_check *subset; +}; + +static spinlock_t lock = SPIN_LOCK_UNLOCKED; +static struct rb_root lock_root = RB_ROOT; + +static inline struct lock_check *rb_search_lock(unsigned long addr) +{ + struct rb_node *n = lock_root.rb_node; + + while (n) { + struct lock_check *l; + + l = rb_entry(n, struct lock_check, rb); + + if (addr < l->start) + n = n->rb_left; + else if (addr > l->end) + n = n->rb_right; + else + return l; + } + return NULL; +} + +static inline void rb_insert_lock(struct lock_check *new) +{ + struct rb_node **p = &lock_root.rb_node; + struct rb_node *parent = NULL; + + while (*p) { + struct lock_check *l; + + parent = *p; + l = rb_entry(parent, struct lock_check, rb); + + if (new->end < l->start) + p = &(*p)->rb_left; + else if (new->start > l->end) + p = &(*p)->rb_right; + else { + /* If a struct subset, add to list. */ + if (new->start >= l->start && new->end <= l->end) { + new->subset = l->subset; + l->subset = new; + } else if (l->start>=new->start && l->end<=new->end) { + rb_replace_node(&l->rb, &new->rb, &lock_root); + new->subset = l; + } else { + printk("%08lx-%08lx overlaps %08lx-%08lx\n", + l->start, l->end, new->start, new->end); + BUG(); + } + return; + } + } + rb_link_node(&new->rb, parent, p); + rb_insert_color(&new->rb, &lock_root); +} + +static int failed_already; + +/* Returns true if addr OK, but caller usually doesn't care. */ +int __check_lock(const void *addr, int writable) +{ + struct lock_check *l; + int ret = 1; + unsigned long flags; + + /* Don't go recursive-crazy. */ + if (failed_already) + return 1; + + spin_lock_irqsave(&lock, flags); + for (l = rb_search_lock((unsigned long)addr); l && ret; l = l->subset){ + if ((unsigned long)addr >= l->start + && (unsigned long)addr <= l->end) + ret = l->check(addr, l->info, writable); + } + spin_unlock_irqrestore(&lock, flags); + + if (!ret) { + failed_already = 1; + BUG(); + } + return ret; +} + +int __check_spinlock(const void *addr, void *info, int writable) +{ + return spin_is_locked((spinlock_t *)info); +} + +int __check_rwlock(const void *addr, void *info, int writable) +{ + if (writable) + return !read_can_lock((rwlock_t *)info); + return rwlock_is_locked((rwlock_t *)info); +} + +int __check_mutex(const void *addr, void *info, int writable) +{ + return atomic_read(&((struct semaphore *)info)->count) == 0; +} + +int __check_rwsem(const void *addr, void *info, int writable) +{ + struct rw_semaphore *sem = info; + + if (writable) + return sem->count < 0; + + return sem->count != RWSEM_UNLOCKED_VALUE; +} + +void register_check_lock(void *start, unsigned long len, + int (*check)(const void *, void *, int), + void *info) +{ + struct lock_check *l = kmalloc(sizeof(*l), GFP_KERNEL); + + BUG_ON(!len); + + /* We can fail, but since this is for debug purposes only, + * let's not burden callers: it doesn't matter. */ + if (!l) { + WARN_ON(1); + return; + } + + l->start = (unsigned long)start; + l->end = l->start + len - 1; + l->check = check; + l->info = info; + l->subset = NULL; + + spin_lock_irq(&lock); + rb_insert_lock(l); + spin_unlock_irq(&lock); +} + +void unregister_check_lock(void *start) +{ + struct lock_check *l; + + spin_lock_irq(&lock); + l = rb_search_lock((unsigned long)start); + if (l) { + rb_erase(&l->rb, &lock_root); + BUG_ON(l->start != (unsigned long)start); + kfree(l); + } + spin_unlock_irq(&lock); + + /* If not due to OOM, it's a real bug. */ + WARN_ON(!l); +} + +EXPORT_SYMBOL(__check_lock); +EXPORT_SYMBOL(__check_spinlock); +EXPORT_SYMBOL(__check_rwlock); +EXPORT_SYMBOL(__check_mutex); +EXPORT_SYMBOL(__check_rwsem); +EXPORT_SYMBOL(unregister_check_lock); +EXPORT_SYMBOL(register_check_lock); Index: linux-2.6.11-rc2-bk2-Netfilter/include/linux/kernel.h =================================================================== --- linux-2.6.11-rc2-bk2-Netfilter.orig/include/linux/kernel.h 2005-01-24 11:14:07.000000000 +1100 +++ linux-2.6.11-rc2-bk2-Netfilter/include/linux/kernel.h 2005-01-25 16:01:53.000000000 +1100 @@ -13,6 +13,7 @@ #include #include #include +#include #include #include @@ -241,6 +242,7 @@ * */ #define container_of(ptr, type, member) ({ \ + __check_lock(ptr, 0); \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) Index: linux-2.6.11-rc2-bk2-Netfilter/kernel/module.c =================================================================== --- linux-2.6.11-rc2-bk2-Netfilter.orig/kernel/module.c 2005-01-24 11:14:10.000000000 +1100 +++ linux-2.6.11-rc2-bk2-Netfilter/kernel/module.c 2005-01-25 16:01:53.000000000 +1100 @@ -1077,7 +1077,7 @@ { /* Delete from various lists */ spin_lock_irq(&modlist_lock); - list_del(&mod->list); + list_del(&mod->list, &modules); spin_unlock_irq(&modlist_lock); remove_sect_attrs(mod); @@ -1811,6 +1811,16 @@ return 0; } +static int __init init_lock_debug(void) +{ + register_check_lock(&modules, sizeof(modules), __check_spinlock, + &modlist_lock); + register_check_lock(&modules, sizeof(modules), __check_mutex, + &module_mutex); + return 0; +} +__initcall(init_lock_debug); + static inline int within(unsigned long addr, void *start, unsigned long size) { return ((void *)addr >= start && (void *)addr < start + size); Index: linux-2.6.11-rc2-bk2-Netfilter/include/linux/lockdebug.h =================================================================== --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ linux-2.6.11-rc2-bk2-Netfilter/include/linux/lockdebug.h 2005-01-25 16:01:53.000000000 +1100 @@ -0,0 +1,45 @@ +#ifndef _LINUX_LOCKDEBUG_H +#define _LINUX_LOCKDEBUG_H + +/* Often, a list or object is statically associated with a given + * lock: this can be usefully checked at runtime. */ +#include +#include + +#ifdef CONFIG_DEBUG_LOCKING +/* Returns true if addr OK, but caller usually doesn't care. */ +int __check_lock(const void *addr, int writable); + +void register_check_lock(void *start, unsigned long len, + int (*check)(const void *addr, void *info, int writable), + void *info); +void unregister_check_lock(void *start); + +/* Convenient helpers */ +int __check_spinlock(const void *addr, void *info, int writable); +int __check_rwlock(const void *addr, void *info, int writable); +int __check_mutex(const void *addr, void *info, int writable); +int __check_rwsem(const void *addr, void *info, int writable); +#else +static inline int __check_lock(const void *addr, int writable) +{ + return 1; +} + +#define __check_spinlock 0 +#define __check_rwlock 0 +#define __check_mutex 0 +#define __check_rwsem 0 + +static inline void register_check_lock(void *start, unsigned long len, + int (*check)(const void *, void *, int), + void *info) +{ +} + +static inline void unregister_check_lock(void *addr) +{ +} +#endif /* CONFIG_DEBUG_LOCKING */ + +#endif /* _LINUX_LOCKDEBUG_H */ Index: linux-2.6.11-rc2-bk2-Netfilter/include/linux/list.h =================================================================== --- linux-2.6.11-rc2-bk2-Netfilter.orig/include/linux/list.h 2005-01-24 11:14:07.000000000 +1100 +++ linux-2.6.11-rc2-bk2-Netfilter/include/linux/list.h 2005-01-25 16:01:53.000000000 +1100 @@ -5,6 +5,7 @@ #include #include +#include #include /* @@ -64,6 +65,7 @@ */ static inline void list_add(struct list_head *new, struct list_head *head) { + __check_lock(head, 1); __list_add(new, head, head->next); } @@ -77,6 +79,7 @@ */ static inline void list_add_tail(struct list_head *new, struct list_head *head) { + __check_lock(head, 1); __list_add(new, head->prev, head); } @@ -114,6 +117,7 @@ */ static inline void list_add_rcu(struct list_head *new, struct list_head *head) { + __check_lock(head, 1); __list_add_rcu(new, head, head->next); } @@ -136,6 +140,7 @@ static inline void list_add_tail_rcu(struct list_head *new, struct list_head *head) { + __check_lock(head, 1); __list_add_rcu(new, head->prev, head); } @@ -148,6 +153,9 @@ */ static inline void __list_del(struct list_head * prev, struct list_head * next) { + /* Don't know where head is: this might get it.. */ + __check_lock(prev, 1); + __check_lock(next, 1); next->prev = prev; prev->next = next; } @@ -227,6 +235,7 @@ */ static inline void list_move(struct list_head *list, struct list_head *head) { + __check_lock(head, 1); __list_del(list->prev, list->next); list_add(list, head); } @@ -239,6 +248,7 @@ static inline void list_move_tail(struct list_head *list, struct list_head *head) { + __check_lock(head, 1); __list_del(list->prev, list->next); list_add_tail(list, head); } @@ -249,6 +259,7 @@ */ static inline int list_empty(const struct list_head *head) { + __check_lock(head, 0); return head->next == head; } @@ -267,6 +278,7 @@ static inline int list_empty_careful(const struct list_head *head) { struct list_head *next = head->next; + __check_lock(head, 0); return (next == head) && (next == head->prev); } @@ -277,6 +289,9 @@ struct list_head *last = list->prev; struct list_head *at = head->next; + __check_lock(head, 1); + __check_lock(list, 1); + first->prev = head; head->next = first; @@ -326,7 +341,8 @@ * @head: the head for your list. */ #define list_for_each(pos, head) \ - for (pos = (head)->next; prefetch(pos->next), pos != (head); \ + for (__check_lock((head),0), pos = (head)->next, prefetch(pos->next); \ + pos != (head); \ pos = pos->next) /** @@ -340,7 +356,7 @@ * or 1 entry) most of the time. */ #define __list_for_each(pos, head) \ - for (pos = (head)->next; pos != (head); pos = pos->next) + for (__check_lock((head), 0), pos = (head)->next; pos != (head); pos = pos->next) /** * list_for_each_prev - iterate over a list backwards @@ -348,7 +364,8 @@ * @head: the head for your list. */ #define list_for_each_prev(pos, head) \ - for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \ + for (__check_lock((head), 0), pos = (head)->prev; \ + prefetch(pos->prev), pos != (head); \ pos = pos->prev) /** @@ -358,7 +375,8 @@ * @head: the head for your list. */ #define list_for_each_safe(pos, n, head) \ - for (pos = (head)->next, n = pos->next; pos != (head); \ + for (__check_lock((head), 1), pos = (head)->next, n = pos->next; \ + pos != (head); \ pos = n, n = pos->next) /** @@ -368,7 +386,8 @@ * @member: the name of the list_struct within the struct. */ #define list_for_each_entry(pos, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member); \ + for (__check_lock((head), 0), \ + pos = list_entry((head)->next, typeof(*pos), member); \ prefetch(pos->member.next), &pos->member != (head); \ pos = list_entry(pos->member.next, typeof(*pos), member)) @@ -379,7 +398,8 @@ * @member: the name of the list_struct within the struct. */ #define list_for_each_entry_reverse(pos, head, member) \ - for (pos = list_entry((head)->prev, typeof(*pos), member); \ + for (__check_lock((head), 0), \ + pos = list_entry((head)->prev, typeof(*pos), member); \ prefetch(pos->member.prev), &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member)) @@ -413,7 +433,8 @@ * @member: the name of the list_struct within the struct. */ #define list_for_each_entry_safe(pos, n, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member), \ + for (__check_lock(head, 1), \ + pos = list_entry((head)->next, typeof(*pos), member), \ n = list_entry(pos->member.next, typeof(*pos), member); \ &pos->member != (head); \ pos = n, n = list_entry(n->member.next, typeof(*n), member)) @@ -503,11 +524,13 @@ static inline int hlist_unhashed(const struct hlist_node *h) { + __check_lock(h, 0); return !h->pprev; } static inline int hlist_empty(const struct hlist_head *h) { + __check_lock(h, 0); return !h->first; } @@ -515,6 +538,7 @@ { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; + __check_lock(n, 1); *pprev = next; if (next) next->pprev = pprev; @@ -563,6 +587,7 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { struct hlist_node *first = h->first; + __check_lock(h, 1); n->next = first; if (first) first->pprev = &n->next; @@ -591,6 +616,7 @@ struct hlist_head *h) { struct hlist_node *first = h->first; + __check_lock(h, 1); n->next = first; n->pprev = &h->first; smp_wmb(); @@ -603,6 +629,7 @@ static inline void hlist_add_before(struct hlist_node *n, struct hlist_node *next) { + __check_lock(n, 1); n->pprev = next->pprev; n->next = next; next->pprev = &n->next; @@ -612,6 +639,7 @@ static inline void hlist_add_after(struct hlist_node *n, struct hlist_node *next) { + __check_lock(n, 1); next->next = n->next; n->next = next; next->pprev = &n->next; @@ -623,11 +651,13 @@ #define hlist_entry(ptr, type, member) container_of(ptr,type,member) #define hlist_for_each(pos, head) \ - for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \ + for (__check_lock((head), 0), pos = (head)->first; \ + pos && ({ prefetch(pos->next); 1; }); \ pos = pos->next) #define hlist_for_each_safe(pos, n, head) \ - for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ + for (__check_lock((head), 1), pos = (head)->first; \ + pos && ({ n = pos->next; 1; }); \ pos = n) #define hlist_for_each_rcu(pos, head) \ @@ -642,7 +672,7 @@ * @member: the name of the hlist_node within the struct. */ #define hlist_for_each_entry(tpos, pos, head, member) \ - for (pos = (head)->first; \ + for (__check_lock((head), 0), pos = (head)->first; \ pos && ({ prefetch(pos->next); 1;}) && \ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ pos = pos->next) @@ -679,7 +709,7 @@ * @member: the name of the hlist_node within the struct. */ #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ - for (pos = (head)->first; \ + for (__check_lock((head), 1), pos = (head)->first; \ pos && ({ n = pos->next; 1; }) && \ ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ pos = n)