[PATCH] list_head debugging?

[PATCH] list_head debugging?

[Zach Brown]

A friend recently was bitten by passing a list_head from list_for_each
to a code path that later moved the list_head around.  Does the attached
patch re-create some debugging wheel that's hiding off in a corner
somewhere?

Beyond catching the obvious use of uninitialized things, it also seems
to catch double adds, double deletes, and simple deletes of 'pos' in
list_for_each.  it even seems to bark about the seemingly hard-to-detect
movement of 'pos' from the iterating list to another, but probably only
in the rare case where you're unconditionally moving all 'pos' in the
loop body.  (you eventually iterate into the second list's head and try
to add it to itself)

I've only played with this in userspace but am glad to pretty it up with
CONFIG_s and bring it into 2.5 if people care.  its against 2.4.mumble.

-- 
 zach

--- ./list.h.debug	Thu Sep 19 15:58:47 2002
+++ ./list.h	Fri Sep 20 13:43:21 2002
@@ -21,6 +21,25 @@
 
 typedef struct list_head list_t;
 
+#define LIST_HEAD_DEBUGGING
+#ifdef LIST_HEAD_DEBUGGING
+
+static inline void __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));
+}
+#else 
+
+#define __list_valid(args...)
+
+#endif
+
 #define LIST_HEAD_INIT(name) { &(name), &(name) }
 
 #define LIST_HEAD(name) \
@@ -56,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);
 }
 
 /**
@@ -69,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);
 }
 
 /*
@@ -93,6 +116,7 @@
  */
 static __inline__ void list_del(struct list_head *entry)
 {
+	__list_valid(entry);
 	__list_del(entry->prev, entry->next);
 }
 
@@ -102,6 +126,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 +137,7 @@
  */
 static __inline__ int list_empty(struct list_head *head)
 {
+	__list_valid(head);
 	return head->next == head;
 }
 
@@ -124,6 +150,9 @@
 {
 	struct list_head *first = list->next;
 
+	__list_valid(list);
+	__list_valid(head);
+
 	if (first != list) {
 		struct list_head *last = list->prev;
 		struct list_head *at = head->next;
@@ -150,9 +179,10 @@
  * @pos:	the &struct list_head to use as a loop counter.
  * @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))
+#define list_for_each(pos, head) 			\
+	for (pos = (head)->next, prefetch(pos->next); \
+		__list_valid(pos), pos != (head); 	\
+        	__list_valid(pos), pos = pos->next, prefetch(pos->next))
         	
 /**
  * list_for_each_safe	-	iterate over a list safe against removal of list entry
@@ -170,8 +200,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))
         	
 
 #endif /* __KERNEL__ || _LVM_H_INCLUDE */

Re: [PATCH] list_head debugging?

[Robert Love]

On Fri, 2002-09-20 at 16:53, Zach Brown wrote:

> A friend recently was bitten by passing a list_head from list_for_each
> to a code path that later moved the list_head around.  Does the attached
> patch re-create some debugging wheel that's hiding off in a corner
> somewhere?
> 
> Beyond catching the obvious use of uninitialized things, it also seems
> to catch double adds, double deletes, and simple deletes of 'pos' in
> list_for_each.  it even seems to bark about the seemingly hard-to-detect
> movement of 'pos' from the iterating list to another, but probably only
> in the rare case where you're unconditionally moving all 'pos' in the
> loop body.  (you eventually iterate into the second list's head and try
> to add it to itself)

Hey, cool!

Yes, I think a lot of people would be all for something like this as a
CONFIG_DEBUG_LISTS or such.  Very nice.

	Robert Love

Re: [PATCH] list_head debugging?

[Thunder from the hill]

Hi,

Before Fri, 20 Sep 2002, Zach Brown wrote:

--- ./list.h.debug	Thu Sep 19 15:58:47 2002
+++ ./list.h	Fri Sep 20 13:43:21 2002
@@ -21,6 +21,25 @@
 
 typedef struct list_head list_t;
 
+#define LIST_HEAD_DEBUGGING
+#ifdef LIST_HEAD_DEBUGGING
+
+static inline void __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));
+}
+#else 

It's all cool, but I'm not entirely convinced why it must be a BUG macro. 
I'd rather have something said via printk here. If whatever we did was 
bad, it will show up with a BUG() just too soon.

I'd describe a macro.

#define list_assert(cond)				\
	if (cond) printk(KERN_ERR "%s failed!\n", #cond)

Or the like. BTW, I'd define LIST_HEAD_DEBUGGING as 1.

			Thunder
-- 
assert(typeof((fool)->next) == typeof(fool));	/* wrong */

Re: [PATCH] list_head debugging?

[Arnaldo Carvalho de Melo]

Em Fri, Sep 20, 2002 at 04:53:04PM -0400, Zach Brown escreveu:
> A friend recently was bitten by passing a list_head from list_for_each
> to a code path that later moved the list_head around.  Does the attached
> patch re-create some debugging wheel that's hiding off in a corner
> somewhere?

Cool! I'll be always using this while developing, thanks!

- Arnaldo