2.5.39 list_head debugging
PATCH 1/1 2.5.39 list_head debugging
Linus,
This patch adds some straight-forward assertions that check the
validity of arguments to the list_* inlines. It tries to simply check that a list member is really on a doubly linked list and that the 4 links it's involved with aren't crap. It should be constant-time on stuff that is likely to be in cache anyway.
The patch already caught some list_heads that were not being
maintained properly ; list_empty was failing on them even though they weren't on lists. (their pointers had slab poison, were NULL, etc. )
With those two errors fixed, and I think akpm is going to send
you the patches, the box appears to run fine with very light testing.
Signature · 359 lines
zach
===== include/linux/list.h 1.17 vs edited =====
--- 1.17/include/linux/list.h Mon Sep 23 10:03:52 2002
+++ linux-2.5.39/include/linux/list.h Fri Sep 27 18:28:30 2002
@@ -3,6 +3,7 @@
#if defined(__KERNEL__) || defined(_LVM_H_INCLUDE)
+#include <linux/kernel.h> /* ouch.. just for bug_on */
#include <linux/prefetch.h>
/*
@@ -28,6 +29,26 @@
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
+#ifdef CONFIG_DEBUG_LIST_HEAD
+
+static inline struct list_head * __list_valid(struct list_head *list)
+{
+ BUG_ON(list == NULL);
+ BUG_ON(list->next == NULL);
+ BUG_ON(list->prev == NULL);
+ BUG_ON(list->next->prev != list);
+ BUG_ON(list->prev->next != list);
+ BUG_ON((list->next == list) && (list->prev != list));
+ BUG_ON((list->prev == list) && (list->next != list));
+
+ return list;
+}
+#else
+
+#define __list_valid(args...)
+
+#endif
+
/*
* Insert a new entry between two known consecutive entries.
*
@@ -54,7 +75,9 @@
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
+ __list_valid(head);
__list_add(new, head, head->next);
+ __list_valid(new);
}
/**
@@ -67,7 +90,9 @@
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
+ __list_valid(head);
__list_add(new, head->prev, head);
+ __list_valid(new);
}
/*
@@ -90,6 +115,7 @@
*/
static inline void list_del(struct list_head *entry)
{
+ __list_valid(entry);
__list_del(entry->prev, entry->next);
entry->next = (void *) 0;
entry->prev = (void *) 0;
@@ -101,6 +127,7 @@
*/
static inline void list_del_init(struct list_head *entry)
{
+ __list_valid(entry);
__list_del(entry->prev, entry->next);
INIT_LIST_HEAD(entry);
}
@@ -112,6 +139,7 @@
*/
static inline void list_move(struct list_head *list, struct list_head *head)
{
+ __list_valid(list);
__list_del(list->prev, list->next);
list_add(list, head);
}
@@ -124,6 +152,7 @@
static inline void list_move_tail(struct list_head *list,
struct list_head *head)
{
+ __list_valid(list);
__list_del(list->prev, list->next);
list_add_tail(list, head);
}
@@ -134,6 +163,7 @@
*/
static inline int list_empty(struct list_head *head)
{
+ __list_valid(head);
return head->next == head;
}
@@ -158,6 +188,8 @@
*/
static inline void list_splice(struct list_head *list, struct list_head *head)
{
+ __list_valid(list);
+ __list_valid(head);
if (!list_empty(list))
__list_splice(list, head);
}
@@ -172,6 +204,8 @@
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
+ __list_valid(list);
+ __list_valid(head);
if (!list_empty(list)) {
__list_splice(list, head);
INIT_LIST_HEAD(list);
@@ -193,8 +227,9 @@
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
- for (pos = (head)->next, prefetch(pos->next); pos != (head); \
- pos = pos->next, prefetch(pos->next))
+ for (pos = (head)->next, prefetch(pos->next); \
+ __list_valid(pos), pos != (head); \
+ __list_valid(pos), pos = pos->next, prefetch(pos->next))
/**
* __list_for_each - iterate over a list
@@ -207,7 +242,9 @@
* or 1 entry) most of the time.
*/
#define __list_for_each(pos, head) \
- for (pos = (head)->next; pos != (head); pos = pos->next)
+ for (pos = (head)->next; \
+ __list_valid(pos), pos != (head); \
+ __list_valid(pos), pos = pos->next)
/**
* list_for_each_prev - iterate over a list backwards
@@ -215,8 +252,9 @@
* @head: the head for your list.
*/
#define list_for_each_prev(pos, head) \
- for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
- pos = pos->prev, prefetch(pos->prev))
+ for (pos = (head)->prev, prefetch(pos->prev); \
+ __list_valid(pos), pos != (head); \
+ __list_valid(pos), pos = pos->prev, prefetch(pos->prev))
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
@@ -225,7 +263,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 (pos = (head)->next, n = pos->next; \
+ __list_valid(pos), pos != (head); \
pos = n, n = pos->next)
/**
@@ -237,7 +276,7 @@
#define list_for_each_entry(pos, head, member) \
for (pos = list_entry((head)->next, typeof(*pos), member), \
prefetch(pos->member.next); \
- &pos->member != (head); \
+ __list_valid(&pos->member), &pos->member != (head); \
pos = list_entry(pos->member.next, typeof(*pos), member), \
prefetch(pos->member.next))
===== arch/alpha/config.in 1.29 vs edited =====
--- 1.29/arch/alpha/config.in Wed Aug 28 11:16:05 2002
+++ linux-2.5.39/arch/alpha/config.in Fri Sep 27 18:09:38 2002
@@ -390,6 +390,7 @@
bool ' Spinlock debugging' CONFIG_DEBUG_SPINLOCK
bool ' Read-write spinlock debugging' CONFIG_DEBUG_RWLOCK
bool ' Semaphore debugging' CONFIG_DEBUG_SEMAPHORE
+ bool ' struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
else
define_tristate CONFIG_MATHEMU y
fi
===== arch/arm/config.in 1.38 vs edited =====
--- 1.38/arch/arm/config.in Mon Jul 15 09:54:04 2002
+++ linux-2.5.39/arch/arm/config.in Fri Sep 27 18:10:03 2002
@@ -669,6 +669,7 @@
dep_bool ' Magic SysRq key' CONFIG_MAGIC_SYSRQ $CONFIG_DEBUG_KERNEL
dep_bool ' Spinlock debugging' CONFIG_DEBUG_SPINLOCK $CONFIG_DEBUG_KERNEL
dep_bool ' Wait queue debugging' CONFIG_DEBUG_WAITQ $CONFIG_DEBUG_KERNEL
+dep_bool ' struct list_head debugging' CONFIG_DEBUG_LIST_HEAD $CONFIG_DEBUG_KERNEL
dep_bool ' Verbose BUG() reporting (adds 70K)' CONFIG_DEBUG_BUGVERBOSE $CONFIG_DEBUG_KERNEL
dep_bool ' Verbose kernel error messages' CONFIG_DEBUG_ERRORS $CONFIG_DEBUG_KERNEL
# These options are only for real kernel hackers who want to get their hands dirty.
===== arch/i386/config.in 1.49 vs edited =====
--- 1.49/arch/i386/config.in Thu Sep 26 08:27:16 2002
+++ linux-2.5.39/arch/i386/config.in Fri Sep 27 18:10:29 2002
@@ -432,6 +432,7 @@
bool ' Memory mapped I/O debugging' CONFIG_DEBUG_IOVIRT
bool ' Magic SysRq key' CONFIG_MAGIC_SYSRQ
bool ' Spinlock debugging' CONFIG_DEBUG_SPINLOCK
+ bool ' struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
if [ "$CONFIG_HIGHMEM" = "y" ]; then
bool ' Highmem debugging' CONFIG_DEBUG_HIGHMEM
fi
===== arch/ia64/config.in 1.33 vs edited =====
--- 1.33/arch/ia64/config.in Sat Sep 21 01:25:52 2002
+++ linux-2.5.39/arch/ia64/config.in Fri Sep 27 18:10:42 2002
@@ -277,6 +277,7 @@
fi
bool ' Debug memory allocations' CONFIG_DEBUG_SLAB
bool ' Spinlock debugging' CONFIG_DEBUG_SPINLOCK
+ bool ' struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
bool ' Turn on compare-and-exchange bug checking (slow!)' CONFIG_IA64_DEBUG_CMPXCHG
bool ' Turn on irq debug checks (slow!)' CONFIG_IA64_DEBUG_IRQ
fi
===== arch/m68k/config.in 1.19 vs edited =====
--- 1.19/arch/m68k/config.in Tue Aug 13 03:33:49 2002
+++ linux-2.5.39/arch/m68k/config.in Fri Sep 27 18:10:57 2002
@@ -541,6 +541,7 @@
bool ' Magic SysRq key' CONFIG_MAGIC_SYSRQ
bool ' Debug memory allocations' CONFIG_DEBUG_SLAB
bool ' Verbose BUG() reporting' CONFIG_DEBUG_BUGVERBOSE
+ bool ' struct list_head debuggiing' CONFIG_DEBUG_LIST_HEAD
fi
endmenu
===== arch/mips/config.in 1.19 vs edited =====
--- 1.19/arch/mips/config.in Wed Aug 28 11:16:05 2002
+++ linux-2.5.39/arch/mips/config.in Fri Sep 27 18:12:26 2002
@@ -489,6 +489,7 @@
bool 'Low-level debugging' CONFIG_LL_DEBUG
fi
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
if [ "$CONFIG_SMP" != "y" ]; then
bool 'Run uncached' CONFIG_MIPS_UNCACHED
fi
===== arch/mips64/config.in 1.18 vs edited =====
--- 1.18/arch/mips64/config.in Wed Aug 28 11:16:05 2002
+++ linux-2.5.39/arch/mips64/config.in Fri Sep 27 18:12:08 2002
@@ -243,6 +243,7 @@
fi
bool 'Remote GDB kernel debugging' CONFIG_REMOTE_DEBUG
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
if [ "$CONFIG_SMP" != "y" ]; then
bool 'Run uncached' CONFIG_MIPS_UNCACHED
fi
===== arch/parisc/config.in 1.12 vs edited =====
--- 1.12/arch/parisc/config.in Sun Aug 25 15:44:57 2002
+++ linux-2.5.39/arch/parisc/config.in Fri Sep 27 18:12:41 2002
@@ -188,6 +188,7 @@
#bool 'Debug kmalloc/kfree' CONFIG_DEBUG_MALLOC
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
endmenu
source security/Config.in
===== arch/ppc/config.in 1.43 vs edited =====
--- 1.43/arch/ppc/config.in Thu Sep 19 21:35:59 2002
+++ linux-2.5.39/arch/ppc/config.in Fri Sep 27 18:13:11 2002
@@ -585,6 +585,7 @@
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
bool 'Spinlock debugging' CONFIG_DEBUG_SPINLOCK
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
bool 'Include kgdb kernel debugger' CONFIG_KGDB
if [ "$CONFIG_KGDB" = "y" ]; then
choice 'Serial Port' \
===== arch/ppc64/config.in 1.16 vs edited =====
--- 1.16/arch/ppc64/config.in Wed Aug 28 23:26:41 2002
+++ linux-2.5.39/arch/ppc64/config.in Fri Sep 27 18:12:58 2002
@@ -196,6 +196,7 @@
if [ "$CONFIG_DEBUG_KERNEL" != "n" ]; then
bool ' Debug memory allocations' CONFIG_DEBUG_SLAB
bool ' Magic SysRq key' CONFIG_MAGIC_SYSRQ
+ bool ' struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
bool ' Include xmon kernel debugger' CONFIG_XMON
if [ "$CONFIG_XMON" = "y" ]; then
bool ' Enable xmon by default' CONFIG_XMON_DEFAULT
===== arch/s390/config.in 1.10 vs edited =====
--- 1.10/arch/s390/config.in Mon Jul 22 11:54:56 2002
+++ linux-2.5.39/arch/s390/config.in Fri Sep 27 18:13:23 2002
@@ -73,6 +73,7 @@
# bool 'Remote GDB kernel debugging' CONFIG_REMOTE_DEBUG
#fi
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
endmenu
source security/Config.in
===== arch/s390x/config.in 1.9 vs edited =====
--- 1.9/arch/s390x/config.in Mon Jul 22 11:54:56 2002
+++ linux-2.5.39/arch/s390x/config.in Fri Sep 27 18:13:36 2002
@@ -76,6 +76,7 @@
# bool 'Remote GDB kernel debugging' CONFIG_REMOTE_DEBUG
#fi
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
endmenu
source security/Config.in
===== arch/sh/config.in 1.16 vs edited =====
--- 1.16/arch/sh/config.in Sun Aug 25 15:41:58 2002
+++ linux-2.5.39/arch/sh/config.in Fri Sep 27 18:13:50 2002
@@ -362,6 +362,7 @@
comment 'Kernel hacking'
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
bool 'Use LinuxSH standard BIOS' CONFIG_SH_STANDARD_BIOS
if [ "$CONFIG_SH_STANDARD_BIOS" = "y" ]; then
bool 'Early printk support' CONFIG_SH_EARLY_PRINTK
===== arch/sparc/config.in 1.24 vs edited =====
--- 1.24/arch/sparc/config.in Wed Sep 18 16:20:23 2002
+++ linux-2.5.39/arch/sparc/config.in Fri Sep 27 18:14:09 2002
@@ -239,6 +239,7 @@
bool 'Debug memory allocations' CONFIG_DEBUG_SLAB
bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
bool 'Spinlock debugging' CONFIG_DEBUG_SPINLOCK
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
endmenu
===== arch/sparc64/config.in 1.37 vs edited =====
--- 1.37/arch/sparc64/config.in Wed Sep 18 16:20:23 2002
+++ linux-2.5.39/arch/sparc64/config.in Fri Sep 27 18:13:59 2002
@@ -281,6 +281,7 @@
bool ' Debug memory allocations' CONFIG_DEBUG_SLAB
bool ' Magic SysRq key' CONFIG_MAGIC_SYSRQ
bool ' Spinlock debugging' CONFIG_DEBUG_SPINLOCK
+ bool ' struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
bool ' Verbose BUG() reporting (adds 70K)' CONFIG_DEBUG_BUGVERBOSE
bool ' D-cache flush debugging' CONFIG_DEBUG_DCFLUSH
fi
===== arch/um/config.in 1.1 vs edited =====
--- 1.1/arch/um/config.in Fri Sep 6 10:29:28 2002
+++ linux-2.5.39/arch/um/config.in Fri Sep 27 18:14:22 2002
@@ -77,6 +77,7 @@
comment 'Kernel hacking'
bool 'Debug memory allocations' CONFIG_DEBUG_SLAB
bool 'Enable kernel debugging symbols' CONFIG_DEBUGSYM
+bool 'struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
if [ "$CONFIG_XTERM_CHAN" = "y" ]; then
dep_bool 'Enable ptrace proxy' CONFIG_PT_PROXY $CONFIG_DEBUGSYM
else
===== arch/x86_64/config.in 1.14 vs edited =====
--- 1.14/arch/x86_64/config.in Sun Aug 25 15:42:58 2002
+++ linux-2.5.39/arch/x86_64/config.in Fri Sep 27 18:14:33 2002
@@ -221,6 +221,7 @@
# bool ' Memory mapped I/O debugging' CONFIG_DEBUG_IOVIRT
bool ' Magic SysRq key' CONFIG_MAGIC_SYSRQ
bool ' Spinlock debugging' CONFIG_DEBUG_SPINLOCK
+ bool ' struct list_head debugging' CONFIG_DEBUG_LIST_HEAD
bool ' Additional run-time checks' CONFIG_CHECKING
bool ' Debug __init statements' CONFIG_INIT_DEBUG
fiReview
Quoted 10 lines · Zach Brown
...
(quoted diff) +8
-0+ BUG_ON(list == NULL); + BUG_ON(list->next == NULL); + BUG_ON(list->prev == NULL); + BUG_ON(list->next->prev != list); + BUG_ON(list->prev->next != list); + BUG_ON((list->next == list) && (list->prev != list)); + BUG_ON((list->prev == list) && (list->next != list)); +
Could we make these just do a printk+dump_stack and continue on? A BUG is a bit severe.
If you do this, I suggest you add the text "warning" to the printk. People tend to think that the dump_stack output is an actual oops, and they get all worried.
Quoted 2 lines
Could we make these just do a printk+dump_stack and continue on? A BUG is a bit severe.
sure. I was taking the overzealous avoidance of possible memory corruption, but I'm sure you're right that its better to be a little forgiving. I'll fixup and resend.
- z
Quoted 3 lines
This patch adds some straight-forward assertions that check the validity of arguments to the list_* inlines. [...]
+ BUG_ON(list == NULL);
+ BUG_ON(list->next == NULL);
+ BUG_ON(list->prev == NULL);
these checks are not needed - they'll trivially be oopsing when trying to use them, right?
+ BUG_ON(list->next->prev != list);
+ BUG_ON(list->prev->next != list);
these two are indeed nice to have.
+ BUG_ON((list->next == list) && (list->prev != list));
+ BUG_ON((list->prev == list) && (list->next != list));
arent these redundant? If list->next->prev == list and list->prev->next == list, then if list->next == list then list->prev == list. Ditto for the other rule.
so i think we only need the following two checks:
+ BUG_ON(list->next->prev != list);
+ BUG_ON(list->prev->next != list);
and we could as well add these unconditionally (no .config complexity needed), until 2.6.0 or so, hm?
Ingo
Quoted 9 lines
Quoted 2 lines
This patch adds some straight-forward assertions that check the validity of arguments to the list_* inlines. [...]
(quoted diff) +3
-0+ BUG_ON(list == NULL); + BUG_ON(list->next == NULL); + BUG_ON(list->prev == NULL);these checks are not needed - they'll trivially be oopsing when trying to use them, right?
sure, it's just nice to get the message immediately.
Quoted 6 lines
(quoted diff) +2
-0+ BUG_ON((list->next == list) && (list->prev != list)); + BUG_ON((list->prev == list) && (list->next != list));arent these redundant? If
list->next->prev== list andlist->prev->next== list, then iflist->next== list thenlist->prev== list. Ditto for the other rule.
I don't think so. these check for the very strange list state that results from double list_adds. its an accident of the ordering of our member assignments that result in a pretty strange looking list state after a double_add. it passes all the double-linked assertions (list->{next,prev}->{prev,next} == list) but doesn't follow the rule that both prev and next must point to list if either of them do.
Review
Quoted 4 lines
so i think we only need the following two checks:
(quoted diff) +2
-0+ BUG_ON(list->next->prev != list); + BUG_ON(list->prev->next != list);
try a double list_add(). these will pass, but the list is not a happy camper :)
Quoted 2 lines
and we could as well add these unconditionally (no .config complexity needed), until 2.6.0 or so, hm?
I'd love that. It was just a bit of sugar to help the medicine go down.
Signature · 1 line
zach
Quoted 4 lines
Quoted 2 lines
and we could as well add these unconditionally (no .config complexity needed), until 2.6.0 or so, hm?
I'd love that. It was just a bit of sugar to help the medicine go down.
Could you leave the config option in, and just default it to on? Some of us are foolish enough to be doing benchmarking on 2.5 - we need to do the performance tweaking ;-)
M.
Review
Quoted 6 lines
Quoted 2 lines
This patch adds some straight-forward assertions that check the validity of arguments to the list_* inlines. [...]
(quoted diff) +3
-0+ BUG_ON(list == NULL); + BUG_ON(list->next == NULL); + BUG_ON(list->prev == NULL);
oh, sorry, I'm reminded that list->next == NULL check is indeed needed. list_empty(list) will fail when the elements are null (list->NULL != list) but the entry isn't on any lists.
so we can lose the first check, sure, it was just cute, but I'd like to keep checking for null member pointers. They already found a bug in vmscan.c where list_empty(mapping->blahblah) was failing for the swapper mapping even though it was on no lists. (harmless? perhaps, but not the symantics list_head is trying to provide)
- z
Quoted 7 lines · Zach Brown
(quoted diff) +7
-0+static inline struct list_head * __list_valid(struct list_head *list) +{ + BUG_ON(list == NULL); + BUG_ON(list->next == NULL); + BUG_ON(list->prev == NULL); + BUG_ON(list->next->prev != list); + BUG_ON(list->prev->next != list);
Review
Quoted 10 lines
(quoted diff) +10
-0+ BUG_ON((list->next == list) && (list->prev != list)); + BUG_ON((list->prev == list) && (list->next != list)); + + return list; +} +#else + +#define __list_valid(args...) + +#endif
Two points (both related to return type).
1, why is it needed ? none of the macros seems to check it. 2, will this work for the #define __list_valid(args...) case ?
Dave
Signature · 2 lines
| Dave Jones. http://www.codemonkey.org.uk | SuSE Labs
Quoted 3 lines
Two points (both related to return type).
1, why is it needed ? none of the macros seems to check it. 2, will this work for the #define__list_valid(args...)case ?
its to appease its use with the , operator in the for(;;).. I vaguely rememebered there being some rule that the types of all the expressions have to be the same.. though it certainly works without the return. are there any language ninjas around who can call me insane?
I can certainly remove it if it makes people sad.
- z