Skip to contentSkip to conversation

Extend list debugging to cover hlists

PATCH In review Matthew Wilcox 7 participants 17 messages May 2, 2008 – May 20, 2008 Library code

lore
Share & tools
lore

Matthew Wilcox

author
#0 lore raw

PATCH 1/1 Extend list debugging to cover hlists

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 <[email protected]>
include/linux/list.h +12 -0
index 08cf4f6..a325d9f 100644
@@ -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();
lib/list_debug.c +18 -0
index 4350ba9..00b56bf 100644
@@ -1,5 +1,8 @@
 /*
  * Copyright 2006, Red Hat, Inc., Dave Jones
+ * Copyright 2008 Intel Corporation
+ * Author: Matthew Wilcox <[email protected]>
+ *
  * 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);
Signature · 4 lines
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."
#1 lore raw
Quoted 15 lines · On Fri, 2 May 2008 12:27:46 -0600 Matthew Wilcox <[email protected]> wrote:
lib/list_debug.c +4 -0
+void hlist_check(struct hlist_node *n)
+{
+	if (unlikely(*n->pprev != n)) {
+		printk(KERN_ERR "hlist corruption. *pprev should be

%p, "

lib/list_debug.c +4 -0
+				"but was %p\n", n, *n->pprev);
+		BUG();
+	}
+	if (unlikely(n->next != NULL && n->next->pprev != &n->next))

{

(quoted diff) +1 -0
+		printk(KERN_ERR "hlist corruption. n->next->pprev

should be"

(quoted diff) +1 -0
+				"%p, but was %p\n", &n->next,

n->next->pprev);

lib/list_debug.c void list_del(struct list_head *entry) · line 96

Quoted 4 lines
lib/list_debug.c +4 -0
+		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) ?

author
#2 lore raw
Quoted 2 lines · Arjan van de Ven

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.

Signature · 4 lines
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."
#3 lore raw
Quoted 6 lines · Matthew Wilcox
Quoted 2 lines · Arjan van de Ven

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

Signature · 1 line
http://www.codemonkey.org.uk
maintainer
#14 lore raw
In reply to Matthew Wilcox
Quoted 5 lines · On Fri, 2 May 2008 12:27:46 -0600 Matthew Wilcox <[email protected]> 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.

author
#15 lore raw
Quoted 1 line · Andrew Morton

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.

Signature · 4 lines
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."
maintainer
#16 lore raw
Quoted 5 lines · On Fri, 2 May 2008 17:17:27 -0600 Matthew Wilcox <[email protected]> wrote:
Quoted 1 line · Andrew Morton

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>

include/linux/list.h +0 -0

include/linux/list.h static inline int hlist_empty(const struct hlist_head *h) · line 720

Quoted 11 lines

index 08cf4f6..a325d9f 100644

include/linux/list.h +4 -0
@@ -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

#4 lore raw

PATCH 1/1 Make

In reply to Matthew Wilcox

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 <[email protected]>
lib/list_debug.c +4 -4
index 4350ba9..09f28bf 100644
@@ -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;
Signature · 1 line
http://www.codemonkey.org.uk
#5 lore raw

Re: [PATCH] Make

lib/list_debug.c void __list_add(struct list_head *new, · line 28

Quoted 6 lines · On Mon, 19 May 2008 23:24:48 -0400 Dave Jones <[email protected]> wrote:

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

lib/list_debug.c +1 -1
 			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....

#6 lore raw

Re: [PATCH] Make

Quoted 15 lines · Arjan van de Ven

Review

Quoted 6 lines · On Mon, 19 May 2008 23:24:48 -0400 Dave Jones <[email protected]> wrote:

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

(quoted diff) +1 -1
 			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

lib/list_debug.c +4 -8
index 4350ba9..d8dee53 100644
@@ -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;
Signature · 1 line
http://www.codemonkey.org.uk
#7 lore raw

Re: [PATCH] Make

Quoted 9 lines · Dave Jones

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)

lib/list_debug.c +0 -0
index 4350ba9..d8dee53 100644

lib/list_debug.c void __list_add(struct list_head *new, · line 27

Quoted 9 lines
lib/list_debug.c +1 -2
@@ -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

#10 lore raw

Re: [PATCH] Make

In reply to Dave Jones
Quoted 9 lines · Dave Jones
Quoted 8 lines · Arjan van de Ven

lib/list_debug.c void __list_add(struct list_head *new,

Quoted 5 lines · On Mon, 19 May 2008 23:24:48 -0400 Dave Jones <[email protected]> wrote:

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

lib/list_debug.c +1 -1
 			prev, next->prev, next);
-		BUG();
+		WARN_ON(1);

Why list_head corruptions are special?

#11 lore raw

Re: [PATCH] Make

Quoted 2 lines · Alexey Dobriyan

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

#8 lore raw

Re: [PATCH] Make

In reply to Linus Torvalds
Quoted 26 lines · On Tue, 20 May 2008 07:54:10 -0700 (PDT) Linus Torvalds…
Quoted 17 lines · Dave Jones

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)

lib/list_debug.c +0 -1
index 4350ba9..d8dee53 100644
@@ -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 "

lib/list_debug.c +1 -0
+		WARN(1, "list_add corruption. next->prev should be

" "prev (%p), but was %p. (next=%p).\n",

lib/list_debug.c void __list_add(struct list_head *new, · line 27

Quoted 3 lines
lib/list_debug.c +0 -1
 			prev, next->prev, next);
-		BUG();
 	}

I think Arjan meant like

Quoted 6 lines
	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... ;)

#12 lore raw

Re: [PATCH] Make

In reply to Linus Torvalds
Quoted 3 lines · Linus Torvalds

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

Signature · 1 line
http://www.codemonkey.org.uk
#9 lore raw

Re: [PATCH] Make

In reply to Linus Torvalds
Quoted 8 lines · Linus Torvalds

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.

lib/list_debug.c +14 -22
index 4350ba9..311ffab 100644
@@ -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;
Signature · 1 line
http://www.codemonkey.org.uk
#13 lore raw

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

In reply to Dave Jones
Quoted 11 lines · Dave Jones
Quoted 3 lines · Linus Torvalds

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