[PATCH] Extend list debugging to cover hlists

[PATCH] Extend list debugging to cover hlists

[Matthew Wilcox]

We've seen a couple of recent reports which point to corrupt hlists.
The DEBUG_LIST config option only checks regular lists, but it's not hard
to cover hlists too.

Signed-off-by: Matthew Wilcox <willy@linux.intel.com>

diff --git a/include/linux/list.h b/include/linux/list.h
index 08cf4f6..a325d9f 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -714,10 +714,17 @@ static inline int hlist_empty(const struct hlist_head *h)
 	return !h->first;
 }
 
+#ifdef CONFIG_DEBUG_LIST
+extern void hlist_check(struct hlist_node *n);
+#else
+#define hlist_check(n)		do { } while (0)
+#endif
+
 static inline void __hlist_del(struct hlist_node *n)
 {
 	struct hlist_node *next = n->next;
 	struct hlist_node **pprev = n->pprev;
+	hlist_check(n);
 	*pprev = next;
 	if (next)
 		next->pprev = pprev;
@@ -775,6 +782,7 @@ static inline void hlist_replace_rcu(struct hlist_node *old,
 {
 	struct hlist_node *next = old->next;
 
+	hlist_check(old);
 	new->next = next;
 	new->pprev = old->pprev;
 	smp_wmb();
@@ -830,6 +838,7 @@ static inline void hlist_add_head_rcu(struct hlist_node *n,
 static inline void hlist_add_before(struct hlist_node *n,
 					struct hlist_node *next)
 {
+	hlist_check(next);
 	n->pprev = next->pprev;
 	n->next = next;
 	next->pprev = &n->next;
@@ -839,6 +848,7 @@ static inline void hlist_add_before(struct hlist_node *n,
 static inline void hlist_add_after(struct hlist_node *n,
 					struct hlist_node *next)
 {
+	hlist_check(next);
 	next->next = n->next;
 	n->next = next;
 	next->pprev = &n->next;
@@ -868,6 +878,7 @@ static inline void hlist_add_after(struct hlist_node *n,
 static inline void hlist_add_before_rcu(struct hlist_node *n,
 					struct hlist_node *next)
 {
+	hlist_check(next);
 	n->pprev = next->pprev;
 	n->next = next;
 	smp_wmb();
@@ -896,6 +907,7 @@ static inline void hlist_add_before_rcu(struct hlist_node *n,
 static inline void hlist_add_after_rcu(struct hlist_node *prev,
 				       struct hlist_node *n)
 {
+	hlist_check(prev);
 	n->next = prev->next;
 	n->pprev = &prev->next;
 	smp_wmb();
diff --git a/lib/list_debug.c b/lib/list_debug.c
index 4350ba9..00b56bf 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -1,5 +1,8 @@
 /*
  * Copyright 2006, Red Hat, Inc., Dave Jones
+ * Copyright 2008 Intel Corporation
+ * Author: Matthew Wilcox <willy@linux.intel.com>
+ *
  * Released under the General Public License (GPL).
  *
  * This file contains the linked list implementations for
@@ -76,3 +79,18 @@ void list_del(struct list_head *entry)
 	entry->prev = LIST_POISON2;
 }
 EXPORT_SYMBOL(list_del);
+
+void hlist_check(struct hlist_node *n)
+{
+	if (unlikely(*n->pprev != n)) {
+		printk(KERN_ERR "hlist corruption. *pprev should be %p, "
+				"but was %p\n", n, *n->pprev);
+		BUG();
+	}
+	if (unlikely(n->next != NULL && n->next->pprev != &n->next)) {
+		printk(KERN_ERR "hlist corruption. n->next->pprev should be"
+				"%p, but was %p\n", &n->next, n->next->pprev);
+		BUG();
+	}
+}
+EXPORT_SYMBOL(hlist_check);

-- 
Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH] Extend list debugging to cover hlists

[Arjan van de Ven]

On Fri, 2 May 2008 12:27:46 -0600
Matthew Wilcox <matthew@wil.cx> wrote:

> +void hlist_check(struct hlist_node *n)
> +{
> +	if (unlikely(*n->pprev != n)) {
> +		printk(KERN_ERR "hlist corruption. *pprev should be
> %p, "
> +				"but was %p\n", n, *n->pprev);
> +		BUG();
> +	}
> +	if (unlikely(n->next != NULL && n->next->pprev != &n->next))
> {
> +		printk(KERN_ERR "hlist corruption. n->next->pprev
> should be"
> +				"%p, but was %p\n", &n->next,
> n->next->pprev);
> +		BUG();
> +	}
> +}
> +EXPORT_SYMBOL(hlist_check);
> 


Hi,
I like the concept of the patch; however...
BUG() is a tad on the rude side... how about WARN_ON(1) ?

Re: [PATCH] Extend list debugging to cover hlists

[Matthew Wilcox]

On Thu, May 01, 2008 at 01:32:09PM -0700, Arjan van de Ven wrote:
> I like the concept of the patch; however...
> BUG() is a tad on the rude side... how about WARN_ON(1) ?

I'm just copying the conventions of the code above.  If those should be
WARN_ON(1) then that should be a followup patch.

-- 
Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH] Extend list debugging to cover hlists

[Dave Jones]

On Fri, May 02, 2008 at 12:49:22PM -0600, Matthew Wilcox wrote:
 > On Thu, May 01, 2008 at 01:32:09PM -0700, Arjan van de Ven wrote:
 > > I like the concept of the patch; however...
 > > BUG() is a tad on the rude side... how about WARN_ON(1) ?
 > 
 > I'm just copying the conventions of the code above.  If those should be
 > WARN_ON(1) then that should be a followup patch.

No objections from me either way.  I chose to BUG originally because
the bug I was chasing was corrupting memory in such a way that we'd
die horribly shortly afterwards anyway.

	Dave

-- 
http://www.codemonkey.org.uk

[PATCH] Make

[Dave Jones]

Arjan noted that the list_head debugging is BUG'ing when it detects
corruption.  By causing the box to panic immediately, we're possibly
losing some bug reports.   Changing this to a WARN_ON should mean
we at the least start seeing reports collected at kerneloops.org

[ I chose to BUG() when I first added that code, because I was
  chasing a bug which caused a lockup anyway, so it made little difference
  to me. ]

Signed-off-by: Dave Jones <davej@redhat.com>

diff --git a/lib/list_debug.c b/lib/list_debug.c
index 4350ba9..09f28bf 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -24,13 +24,13 @@ void __list_add(struct list_head *new,
 		printk(KERN_ERR "list_add corruption. next->prev should be "
 			"prev (%p), but was %p. (next=%p).\n",
 			prev, next->prev, next);
-		BUG();
+		WARN_ON(1);
 	}
 	if (unlikely(prev->next != next)) {
 		printk(KERN_ERR "list_add corruption. prev->next should be "
 			"next (%p), but was %p. (prev=%p).\n",
 			next, prev->next, prev);
-		BUG();
+		WARN_ON(1);
 	}
 	next->prev = new;
 	new->next = next;
@@ -64,12 +64,12 @@ void list_del(struct list_head *entry)
 	if (unlikely(entry->prev->next != entry)) {
 		printk(KERN_ERR "list_del corruption. prev->next should be %p, "
 				"but was %p\n", entry, entry->prev->next);
-		BUG();
+		WARN_ON(1);
 	}
 	if (unlikely(entry->next->prev != entry)) {
 		printk(KERN_ERR "list_del corruption. next->prev should be %p, "
 				"but was %p\n", entry, entry->next->prev);
-		BUG();
+		WARN_ON(1);
 	}
 	__list_del(entry->prev, entry->next);
 	entry->next = LIST_POISON1;

-- 
http://www.codemonkey.org.uk

Re: [PATCH] Make

[Arjan van de Ven]

On Mon, 19 May 2008 23:24:48 -0400
Dave Jones <davej@redhat.com> wrote:

>  		printk(KERN_ERR "list_add corruption. next->prev
> should be " "prev (%p), but was %p. (next=%p).\n",
>  			prev, next->prev, next);
> -		BUG();
> +		WARN_ON(1);
>  	}


now that -mm has a WARN(condition, printk arguments), could we make
this use it? The advantage (apart from smaller C code) is that it puts
the printk inside the ---[ cut here ]--- which makes it more likely that
reporters (and kerneloops.org) get the actual text....

Re: [PATCH] Make

[Dave Jones]

On Tue, May 20, 2008 at 07:14:58AM -0700, Arjan van de Ven wrote:
 > On Mon, 19 May 2008 23:24:48 -0400
 > Dave Jones <davej@redhat.com> wrote:
 > 
 > >  		printk(KERN_ERR "list_add corruption. next->prev
 > > should be " "prev (%p), but was %p. (next=%p).\n",
 > >  			prev, next->prev, next);
 > > -		BUG();
 > > +		WARN_ON(1);
 > >  	}
 > 
 > 
 > now that -mm has a WARN(condition, printk arguments), could we make
 > this use it? The advantage (apart from smaller C code) is that it puts
 > the printk inside the ---[ cut here ]--- which makes it more likely that
 > reporters (and kerneloops.org) get the actual text....

Like this ?  (I don't have a -mm handy, so guessed based on mm-commits mail,
  patch uncompiled, but should dtrt if I understood your diff correctly)

	Dave

diff --git a/lib/list_debug.c b/lib/list_debug.c
index 4350ba9..d8dee53 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -21,16 +21,14 @@ void __list_add(struct list_head *new,
 			      struct list_head *next)
 {
 	if (unlikely(next->prev != prev)) {
-		printk(KERN_ERR "list_add corruption. next->prev should be "
+		WARN(1, "list_add corruption. next->prev should be "
 			"prev (%p), but was %p. (next=%p).\n",
 			prev, next->prev, next);
-		BUG();
 	}
 	if (unlikely(prev->next != next)) {
-		printk(KERN_ERR "list_add corruption. prev->next should be "
+		WARN(1, "list_add corruption. prev->next should be "
 			"next (%p), but was %p. (prev=%p).\n",
 			next, prev->next, prev);
-		BUG();
 	}
 	next->prev = new;
 	new->next = next;
@@ -62,14 +60,12 @@ EXPORT_SYMBOL(list_add);
 void list_del(struct list_head *entry)
 {
 	if (unlikely(entry->prev->next != entry)) {
-		printk(KERN_ERR "list_del corruption. prev->next should be %p, "
+		WARN(1, "list_del corruption. prev->next should be %p, "
 				"but was %p\n", entry, entry->prev->next);
-		BUG();
 	}
 	if (unlikely(entry->next->prev != entry)) {
-		printk(KERN_ERR "list_del corruption. next->prev should be %p, "
+		WARN(1, "list_del corruption. next->prev should be %p, "
 				"but was %p\n", entry, entry->next->prev);
-		BUG();
 	}
 	__list_del(entry->prev, entry->next);
 	entry->next = LIST_POISON1;
-- 
http://www.codemonkey.org.uk

Re: [PATCH] Make

[Linus Torvalds]

On Tue, 20 May 2008, Dave Jones wrote:
> 
> Like this ?  (I don't have a -mm handy, so guessed based on mm-commits mail,
>   patch uncompiled, but should dtrt if I understood your diff correctly)
> 
> diff --git a/lib/list_debug.c b/lib/list_debug.c
> index 4350ba9..d8dee53 100644
> --- a/lib/list_debug.c
> +++ b/lib/list_debug.c
> @@ -21,16 +21,14 @@ void __list_add(struct list_head *new,
>  			      struct list_head *next)
>  {
>  	if (unlikely(next->prev != prev)) {
> -		printk(KERN_ERR "list_add corruption. next->prev should be "
> +		WARN(1, "list_add corruption. next->prev should be "
>  			"prev (%p), but was %p. (next=%p).\n",
>  			prev, next->prev, next);
> -		BUG();
>  	}

I think Arjan meant like

	WARN(next->prev != prev,
		"list_add corruption. next->prev should be "
		"prev (%p), but was %p. (next=%p).\n",
		prev, next->prev, next);

without any "if()" statement at all.

			Linus

Re: [PATCH] Make

[Dave Jones]

On Tue, May 20, 2008 at 07:54:10AM -0700, Linus Torvalds wrote:

 > I think Arjan meant like
 > 
 > 	WARN(next->prev != prev,
 > 		"list_add corruption. next->prev should be "
 > 		"prev (%p), but was %p. (next=%p).\n",
 > 		prev, next->prev, next);
 > 
 > without any "if()" statement at all.

Nice. I like that.


diff --git a/lib/list_debug.c b/lib/list_debug.c
index 4350ba9..311ffab 100644
--- a/lib/list_debug.c
+++ b/lib/list_debug.c
@@ -20,18 +20,14 @@ void __list_add(struct list_head *new,
 			      struct list_head *prev,
 			      struct list_head *next)
 {
-	if (unlikely(next->prev != prev)) {
-		printk(KERN_ERR "list_add corruption. next->prev should be "
-			"prev (%p), but was %p. (next=%p).\n",
-			prev, next->prev, next);
-		BUG();
-	}
-	if (unlikely(prev->next != next)) {
-		printk(KERN_ERR "list_add corruption. prev->next should be "
-			"next (%p), but was %p. (prev=%p).\n",
-			next, prev->next, prev);
-		BUG();
-	}
+	WARN(next->prev != prev,
+		"list_add corruption. next->prev should be "
+		"prev (%p), but was %p. (next=%p).\n",
+		prev, next->prev, next);
+	WARN(prev->next != next,
+		"list_add corruption. prev->next should be "
+		"next (%p), but was %p. (prev=%p).\n",
+		next, prev->next, prev);
 	next->prev = new;
 	new->next = next;
 	new->prev = prev;
@@ -61,16 +57,12 @@ EXPORT_SYMBOL(list_add);
  */
 void list_del(struct list_head *entry)
 {
-	if (unlikely(entry->prev->next != entry)) {
-		printk(KERN_ERR "list_del corruption. prev->next should be %p, "
-				"but was %p\n", entry, entry->prev->next);
-		BUG();
-	}
-	if (unlikely(entry->next->prev != entry)) {
-		printk(KERN_ERR "list_del corruption. next->prev should be %p, "
-				"but was %p\n", entry, entry->next->prev);
-		BUG();
-	}
+	WARN(entry->prev->next != entry,
+		"list_del corruption. prev->next should be %p, "
+		"but was %p\n", entry, entry->prev->next);
+	WARN(entry->next->prev != entry,
+		"list_del corruption. next->prev should be %p, "
+		"but was %p\n", entry, entry->next->prev);
 	__list_del(entry->prev, entry->next);
 	entry->next = LIST_POISON1;
 	entry->prev = LIST_POISON2;

-- 
http://www.codemonkey.org.uk

Re: [PATCH] Make

[Arjan van de Ven]

On Tue, 20 May 2008 07:54:10 -0700 (PDT)
Linus Torvalds <torvalds@linux-foundation.org> wrote:

> 
> 
> On Tue, 20 May 2008, Dave Jones wrote:
> > 
> > Like this ?  (I don't have a -mm handy, so guessed based on
> > mm-commits mail, patch uncompiled, but should dtrt if I understood
> > your diff correctly)
> > 
> > diff --git a/lib/list_debug.c b/lib/list_debug.c
> > index 4350ba9..d8dee53 100644
> > --- a/lib/list_debug.c
> > +++ b/lib/list_debug.c
> > @@ -21,16 +21,14 @@ void __list_add(struct list_head *new,
> >  			      struct list_head *next)
> >  {
> >  	if (unlikely(next->prev != prev)) {
> > -		printk(KERN_ERR "list_add corruption. next->prev
> > should be "
> > +		WARN(1, "list_add corruption. next->prev should be
> > " "prev (%p), but was %p. (next=%p).\n",
> >  			prev, next->prev, next);
> > -		BUG();
> >  	}
> 
> I think Arjan meant like
> 
> 	WARN(next->prev != prev,
> 		"list_add corruption. next->prev should be "
> 		"prev (%p), but was %p. (next=%p).\n",
> 		prev, next->prev, next);
> 
> without any "if()" statement at all.

Dave...what Linus said ;)


would be nice to get WARN() into mainline soon... ;)

Re: [PATCH] Make

[Alexey Dobriyan]

On 5/20/08, Dave Jones <davej@redhat.com> wrote:
> On Tue, May 20, 2008 at 07:14:58AM -0700, Arjan van de Ven wrote:
>  > On Mon, 19 May 2008 23:24:48 -0400
>  > Dave Jones <davej@redhat.com> wrote:
>  >
>  > >  		printk(KERN_ERR "list_add corruption. next->prev
>  > > should be " "prev (%p), but was %p. (next=%p).\n",
>  > >  			prev, next->prev, next);
>  > > -		BUG();
>  > > +		WARN_ON(1);

Why list_head corruptions are special?

Re: [PATCH] Make

[Linus Torvalds]

On Tue, 20 May 2008, Alexey Dobriyan wrote:
> 
> Why list_head corruptions are special?

It's not that list corruptions are special, but:
 - *any* corruption is very interesting, and the earlier we find it the 
   better
 - we have a lot of lists in the kernel, so testing pointers is actually 
   likely to find stuff.
 - and lists are something we can *test* for corruption

That third one is important. Most random pointers we can't sanely test 
because they don't have trivial and important patterns.

The second one is relevant too: some of the pointers that we *could* test 
(struct task has a pointer to the thread struct and back, and we could 
test that) are just not common enough to be worth testing. And other 
concepts don't have any nice centralized routines for adding the test.

So no, lists aren't "special" in any inherent way, they are just special 
in these kinds of "incidentally, a lot of random data structure corruption 
has traditionally shown up in lists, because there are so many of them".

			Linus

Re: [PATCH] Make

[Dave Jones]

On Tue, May 20, 2008 at 08:12:41AM -0700, Linus Torvalds wrote:

 > So no, lists aren't "special" in any inherent way, they are just special 
 > in these kinds of "incidentally, a lot of random data structure corruption 
 > has traditionally shown up in lists, because there are so many of them".

It's also been _really_ useful for showing up random bit flips in bad hardware.

"hey, if that bit had been a 1, this pointer would have looked valid and we
 wouldn't have oopsed" has led to quite a few cases where the reporter then
found a session with memtest86 enlightening.

	Dave

-- 
http://www.codemonkey.org.uk

Re: [PATCH] Make (LIST_DEBUG WARN not BUG)

[Alexey Dobriyan]

On Tue, May 20, 2008 at 11:22:27AM -0400, Dave Jones wrote:
> On Tue, May 20, 2008 at 08:12:41AM -0700, Linus Torvalds wrote:
> 
>  > So no, lists aren't "special" in any inherent way, they are just special 
>  > in these kinds of "incidentally, a lot of random data structure corruption 
>  > has traditionally shown up in lists, because there are so many of them".
> 
> It's also been _really_ useful for showing up random bit flips in bad hardware.
> 
> "hey, if that bit had been a 1, this pointer would have looked valid and we
>  wouldn't have oopsed" has led to quite a few cases where the reporter then
> found a session with memtest86 enlightening.

Affirmative, LIST_DEBUG is very useful.

Let's look again at what patch actually does: writes to corrupted memory
will be done even if it's known for sure it's corrupted.

There is

	BUG_ON(!list_empty(&father->children));

in forget_original_parent(). Should it be changed to WARN_ON? Why [not]?

Re: [PATCH] Extend list debugging to cover hlists

[Andrew Morton]

On Fri, 2 May 2008 12:27:46 -0600
Matthew Wilcox <matthew@wil.cx> wrote:

> 
> We've seen a couple of recent reports which point to corrupt hlists.
> The DEBUG_LIST config option only checks regular lists, but it's not hard
> to cover hlists too.
>

patching file include/linux/list.h
Hunk #1 succeeded at 499 (offset -215 lines).
Hunk #2 FAILED at 567.
Hunk #3 succeeded at 545 (offset -293 lines).
Hunk #4 succeeded at 555 (offset -293 lines).
Hunk #5 FAILED at 585.
Hunk #6 FAILED at 614.
3 out of 6 hunks FAILED -- saving rejects to file include/linux/list.h.rej
patching file lib/list_debug.c
Failed to apply extend-list-debugging-to-cover-hlists

linux-next is a better tree against which to prepare 2.6.x+1 patches.

Re: [PATCH] Extend list debugging to cover hlists

[Matthew Wilcox]

On Fri, May 02, 2008 at 04:14:03PM -0700, Andrew Morton wrote:
> linux-next is a better tree against which to prepare 2.6.x+1 patches.

Is there a reason to wait for 2.6.x+1?  People are having problems today
with corrupt hlists.

-- 
Intel are signing my paycheques ... these opinions are still mine
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH] Extend list debugging to cover hlists

[Andrew Morton]

On Fri, 2 May 2008 17:17:27 -0600
Matthew Wilcox <matthew@wil.cx> wrote:

> On Fri, May 02, 2008 at 04:14:03PM -0700, Andrew Morton wrote:
> > linux-next is a better tree against which to prepare 2.6.x+1 patches.
> 
> Is there a reason to wait for 2.6.x+1?  People are having problems today
> with corrupt hlists.

dunno, really.  Merging it would bust git-sched and linux-next, which is of
course solveable, but a hassle.  If there are bugs in there then linux-next
and -mm testing will pick up some of them.  Mainline testing would pick up
more.  Is that delta worth it?  dunno, really.

Experience tells us that decent testing of new debug infrastructure
(especially that which goes BUG) before it goes mainline is a good idea.

<looks at the patch>

diff --git a/include/linux/list.h b/include/linux/list.h
> index 08cf4f6..a325d9f 100644
> --- a/include/linux/list.h
> +++ b/include/linux/list.h
> @@ -714,10 +714,17 @@ static inline int hlist_empty(const struct hlist_head *h)
>  	return !h->first;
>  }
>  
> +#ifdef CONFIG_DEBUG_LIST
> +extern void hlist_check(struct hlist_node *n);
> +#else
> +#define hlist_check(n)		do { } while (0)

a static inline would be better.

- It matches the other version, which is aesthetically pleasing

- It provides type-checking when CONFIG_DEBUG_LIST=n