It is currently Sun, 09 Aug 2020 02:13:13 GMT



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

--
 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 de{*filter*}' 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'
...

read more »



 Thu, 17 Mar 2005 07:10:03 GMT   
 2.5.39 list_head debugging

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.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 07:20:04 GMT   
 2.5.39 list_head debugging

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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 07:30:06 GMT   
 2.5.39 list_head debugging

+       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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 09:30:09 GMT   
 2.5.39 list_head debugging

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

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.

try a double list_add().  these will pass, but the list is not a happy
camper :)

I'd love that.  It was just a bit of sugar to help the medicine go down.

--
 zach
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 15:40:06 GMT   
 2.5.39 list_head debugging

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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 15:40:10 GMT   
 2.5.39 list_head debugging

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.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 15:40:10 GMT   
 2.5.39 list_head debugging
 > +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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 18:30:04 GMT   
 2.5.39 list_head debugging

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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/



 Thu, 17 Mar 2005 21:30:12 GMT   
 
   [ 9 post ] 

Similar Threads

1. list_head debugging patch

2. list_head debugging?

3. list_head debugging

4. list_head debugging

5. 2.5.39 - bad: scheduling while atomic! && also ISAPNP kills 2.5.39

6. [patch 2.5.39] allow kernel to be virtually mapp ed from any physi cal address

7. 2.5.39: Oracle 9.2 goes OOM on startup

8. benchmarks 2.5.40-mm1 and 2.5.39 on quad xeon

9. Problem: [2.5.39] Loss of the mouse control

10. Problem: [2.5.39] Cannot mount IDE cdrom if SCSI-emulated


 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software