[PATCH] 2.5.39 list_head debugging

[PATCH] 2.5.39 list_head debugging

[Zach Brown]

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.

-- 
 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
 fi

Re: [PATCH] 2.5.39 list_head debugging

[Andrew Morton]

Zach Brown wrote:
> 
> ...
> +       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.

Re: [PATCH] 2.5.39 list_head debugging

[Zach Brown]

> 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

Re: [PATCH] 2.5.39 list_head debugging

[Ingo Molnar]

> 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

Re: [PATCH] 2.5.39 list_head debugging

[Zach Brown]

> > 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?

sure, it's just nice to get the message immediately.

> +	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.

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.

> so i think we only need the following two checks:
> 
> +	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 :)

> 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.

-- 
 zach

Re: [PATCH] 2.5.39 list_head debugging

[Martin J. Bligh]

>> 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.

Re: [PATCH] 2.5.39 list_head debugging

[Zach Brown]

> > 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);

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

Re: [PATCH] 2.5.39 list_head debugging

[Dave Jones]

On Sun, Sep 29, 2002 at 01:58:52AM -0400, Zach Brown wrote:
 > +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

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

-- 
| Dave Jones.        http://www.codemonkey.org.uk
| SuSE Labs

Re: [PATCH] 2.5.39 list_head debugging

[Zach Brown]

> 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