lib/list_sort: strengthen self-test to expose a bug, then fix the bug

PATCH New [email protected] 1 participant 11 messages Aug 24, 2010 Library code

Share & tools

[email protected]

author

2010-08-24 16:02 UTC #0 lore raw

cover lib/list_sort: strengthen self-test to expose a bug, then fix the bug

Commit 835cc0c8477fdbc59e0217891d6f11061b1ac4e2 introduces a bug to list_sort(). Earlier patches in this series strengthen list_sort's self-test so as to expose the bug; the final patch fixes the bug.

[email protected]

author

2010-08-24 16:02 UTC #1 lore raw

PATCH 1/10 lib/list_sort: selftest: enabled with CONFIG_TEST_LIST_SORT

From: Artem Bityutskiy <[email protected]>

Enable the self-test, without editing of the code.

Signed-off-by Artem Bityutskiy <[email protected]>

Signed-off-by Don Mullis <[email protected]>

---
 lib/Kconfig.debug |    9 +++++++++
 lib/list_sort.c   |    4 ++--
 2 files changed, 11 insertions(+), 2 deletions(-)

lib/Kconfig.debug +9 -0

Index: linux-next/lib/Kconfig.debug
===================================================================
@@ -714,6 +714,15 @@ config DEBUG_LIST
 
 	  If unsure, say N.
 
+config TEST_LIST_SORT
+	bool "Linked list sorting test"
+	depends on DEBUG_KERNEL
+	help
+	  Enable this to turn on 'list_sort()' function test. This test is
+	  executed only once during system boot, so affects only boot time.
+
+	  If unsure, say N.
+
 config DEBUG_SG
 	bool "Debug SG table operations"
 	depends on DEBUG_KERNEL

lib/list_sort.c +2 -2

Index: linux-next/lib/list_sort.c
===================================================================
@@ -141,7 +141,7 @@ void list_sort(void *priv, struct list_h
 }
 EXPORT_SYMBOL(list_sort);
 
-#ifdef DEBUG_LIST_SORT
+#ifdef CONFIG_TEST_LIST_SORT
 struct debug_el {
 	struct list_head l_h;
 	int value;

@@ -214,4 +214,4 @@ static int __init list_sort_test(void)
 	return 0;
 }
 module_init(list_sort_test);
-#endif
+#endif /* CONFIG_TEST_LIST_SORT */

[email protected]

author

2010-08-24 16:02 UTC #2 lore raw

PATCH 2/10 lib/list_sort: selftest: use more appropriate printk levels

In reply to [email protected]

From: Artem Bityutskiy <[email protected]>

Use KERN_NORM and KERN_ERR levels for test error messages.

Signed-off-by Artem Bityutskiy <[email protected]>

Signed-off-by Don Mullis <[email protected]>

---
 lib/list_sort.c |   16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

lib/list_sort.c +8 -8

Index: linux-next/lib/list_sort.c
===================================================================
@@ -166,7 +166,7 @@ static int __init list_sort_test(void)
 	struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
 	struct list_head *cur;
 
-	printk(KERN_WARNING "testing list_sort()\n");
+	printk(KERN_DEBUG "testing list_sort()\n");
 
 	cur = head;
 	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {

@@ -189,17 +189,17 @@ static int __init list_sort_test(void)
 		struct debug_el *el = container_of(cur, struct debug_el, l_h);
 		int cmp_result = cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
-			printk(KERN_EMERG "list_sort() returned "
-						"a corrupted list!\n");
+			printk(KERN_ERR "list_sort() returned "
+					"a corrupted list!\n");
 			return 1;
 		} else if (cmp_result > 0) {
-			printk(KERN_EMERG "list_sort() failed to sort!\n");
+			printk(KERN_ERR "list_sort() failed to sort!\n");
 			return 1;
 		} else if (cmp_result == 0 &&
 				el->serial >= container_of(cur->next,
 					struct debug_el, l_h)->serial) {
-			printk(KERN_EMERG "list_sort() failed to preserve order"
-						 " of equivalent elements!\n");
+			printk(KERN_ERR "list_sort() failed to preserve order "
+					"of equivalent elements!\n");
 			return 1;
 		}
 		kfree(cur->prev);

@@ -207,8 +207,8 @@ static int __init list_sort_test(void)
 	}
 	kfree(cur);
 	if (count != LIST_SORT_TEST_LENGTH) {
-		printk(KERN_EMERG "list_sort() returned list of"
-						"different length!\n");
+		printk(KERN_ERR "list_sort() returned list of "
+				"different length!\n");
 		return 1;
 	}
 	return 0;

[email protected]

author

2010-08-24 16:02 UTC #3 lore raw

PATCH 3/10 lib/list_sort: selftest: cleanups: use random32(), rename variables

In reply to [email protected]

From: Artem Bityutskiy <[email protected]>

- Instead of using own pseudo-random generator, use generic linux 'random32()' function.
- Shorter macro name for test list length
- Use traditional name 'list' for 'struct list_head' instance.

Signed-off-by Artem Bityutskiy <[email protected]>

Signed-off-by Don Mullis <[email protected]>

---
 lib/list_sort.c |   19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

lib/list_sort.c +10 -9

Index: linux-next/lib/list_sort.c
===================================================================
@@ -142,16 +142,17 @@ void list_sort(void *priv, struct list_h
 EXPORT_SYMBOL(list_sort);
 
 #ifdef CONFIG_TEST_LIST_SORT
+#include <linux/random.h>
 struct debug_el {
-	struct list_head l_h;
+	struct list_head list;
 	int value;
 	unsigned serial;
 };
 
 static int cmp(void *priv, struct list_head *a, struct list_head *b)
 {
-	return container_of(a, struct debug_el, l_h)->value
-	     - container_of(b, struct debug_el, l_h)->value;
+	return container_of(a, struct debug_el, list)->value
+	     - container_of(b, struct debug_el, list)->value;
 }
 
 /*

@@ -162,7 +163,7 @@ static int cmp(void *priv, struct list_h
 
 static int __init list_sort_test(void)
 {
-	int i, r = 1, count;
+	int i, count;
 	struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
 	struct list_head *cur;

@@ -173,11 +174,11 @@ static int __init list_sort_test(void)
 		struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
 		BUG_ON(!el);
 		 /* force some equivalencies */
-		el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
+		el->value = random32() % (LIST_SORT_TEST_LENGTH/3);
 		el->serial = i;
 
-		el->l_h.prev = cur;
-		cur->next = &el->l_h;
+		el->list.prev = cur;
+		cur->next = &el->list;
 		cur = cur->next;
 	}
 	head->prev = cur;

@@ -186,7 +187,7 @@ static int __init list_sort_test(void)
 
 	count = 1;
 	for (cur = head->next; cur->next != head; cur = cur->next) {
-		struct debug_el *el = container_of(cur, struct debug_el, l_h);
+		struct debug_el *el = container_of(cur, struct debug_el, list);
 		int cmp_result = cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
 			printk(KERN_ERR "list_sort() returned "

@@ -197,7 +198,7 @@ static int __init list_sort_test(void)
 			return 1;
 		} else if (cmp_result == 0 &&
 				el->serial >= container_of(cur->next,
-					struct debug_el, l_h)->serial) {
+					struct debug_el, list)->serial) {
 			printk(KERN_ERR "list_sort() failed to preserve order "
 					"of equivalent elements!\n");
 			return 1;

[email protected]

author

2010-08-24 16:03 UTC #4 lore raw

PATCH 4/10 lib/list_sort: selftest: permit normal boot after test failure

In reply to [email protected]

From: Artem Bityutskiy <[email protected]>

Don't panic the kernel if kmalloc() fails, and free memory if self-test fails.

Related cleanups:
- make 'head' a stack variable instead of 'kmalloc()'ed, which simplifies code a bit
- introduce temporary variable to improve readability

Signed-off-by Artem Bityutskiy <[email protected]>

Signed-off-by Don Mullis <[email protected]>

---
 lib/list_sort.c |   51 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 31 insertions(+), 20 deletions(-)

lib/list_sort.c +31 ~~-20~~

Index: linux-next/lib/list_sort.c
===================================================================
@@ -163,16 +163,20 @@ static int cmp(void *priv, struct list_h
 
 static int __init list_sort_test(void)
 {
-	int i, count;
-	struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
-	struct list_head *cur;
+	int i, count, err = -EINVAL;
+	struct list_head head;
+	struct list_head *cur, *tmp;
 
 	printk(KERN_DEBUG "testing list_sort()\n");
 
-	cur = head;
+	cur = &head;
 	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
 		struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
-		BUG_ON(!el);
+		if (!el) {
+			printk(KERN_ERR "cannot	allocate memory -- "
+					"testing aborted\n");
+			goto exit;
+		}
 		 /* force some equivalencies */
 		el->value = random32() % (LIST_SORT_TEST_LENGTH/3);
 		el->serial = i;

@@ -181,38 +185,45 @@ static int __init list_sort_test(void)
 		cur->next = &el->list;
 		cur = cur->next;
 	}
-	head->prev = cur;
+	head.prev = cur;
 
-	list_sort(NULL, head, cmp);
+	list_sort(NULL, &head, cmp);
 
 	count = 1;
-	for (cur = head->next; cur->next != head; cur = cur->next) {
-		struct debug_el *el = container_of(cur, struct debug_el, list);
+	for (cur = head.next; cur->next != &head; cur = cur->next) {
+		struct debug_el *el;
+		struct debug_el *el_next;
 		int cmp_result = cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
 			printk(KERN_ERR "list_sort() returned "
 					"a corrupted list!\n");
-			return 1;
-		} else if (cmp_result > 0) {
+			goto exit;
+		}
+		if (cmp_result > 0) {
 			printk(KERN_ERR "list_sort() failed to sort!\n");
-			return 1;
-		} else if (cmp_result == 0 &&
-				el->serial >= container_of(cur->next,
-					struct debug_el, list)->serial) {
+			goto exit;
+		}
+		el = container_of(cur, struct debug_el, list);
+		el_next = container_of(cur->next, struct debug_el, list);
+		if (cmp_result == 0 && el->serial >= el_next->serial) {
 			printk(KERN_ERR "list_sort() failed to preserve order "
 					"of equivalent elements!\n");
-			return 1;
+			goto exit;
 		}
-		kfree(cur->prev);
 		count++;
 	}
-	kfree(cur);
 	if (count != LIST_SORT_TEST_LENGTH) {
 		printk(KERN_ERR "list_sort() returned list of "
 				"different length!\n");
-		return 1;
+		goto exit;
+	}
+	err = 0;
+exit:
+	list_for_each_safe(cur, tmp, &head) {
+		list_del(cur);
+		kfree(container_of(cur, struct debug_el, list));
 	}
-	return 0;
+	return err;
 }
 module_init(list_sort_test);
 #endif /* CONFIG_TEST_LIST_SORT */

[email protected]

author

2010-08-24 16:02 UTC #5 lore raw

PATCH 5/10 lib/list_sort: selftest: improve printk wording

In reply to [email protected]

From: Artem Bityutskiy <[email protected]>

Start boot printk's with "list_sort_test:" prefix to make it obvious for users where the messages come from; other wording improvements.

Signed-off-by Artem Bityutskiy <[email protected]>

Signed-off-by Don Mullis <[email protected]>

---
 lib/list_sort.c |   18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

lib/list_sort.c +8 ~~-10~~

Index: linux-next/lib/list_sort.c
===================================================================
@@ -167,14 +167,14 @@ static int __init list_sort_test(void)
 	struct list_head head;
 	struct list_head *cur, *tmp;
 
-	printk(KERN_DEBUG "testing list_sort()\n");
+	printk(KERN_DEBUG "list_sort_test: starting\n");
 
 	cur = &head;
 	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
 		struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
 		if (!el) {
-			printk(KERN_ERR "cannot	allocate memory -- "
-					"testing aborted\n");
+			printk(KERN_ERR "list_sort_test: cannot	allocate memory"
+					" -- testing aborted\n");
 			goto exit;
 		}
 		 /* force some equivalencies */

@@ -195,26 +195,24 @@ static int __init list_sort_test(void)
 		struct debug_el *el_next;
 		int cmp_result = cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
-			printk(KERN_ERR "list_sort() returned "
-					"a corrupted list!\n");
+			printk(KERN_ERR "list_sort_test: list corrupted\n");
 			goto exit;
 		}
 		if (cmp_result > 0) {
-			printk(KERN_ERR "list_sort() failed to sort!\n");
+			printk(KERN_ERR "list_sort_test: failed to sort\n");
 			goto exit;
 		}
 		el = container_of(cur, struct debug_el, list);
 		el_next = container_of(cur->next, struct debug_el, list);
 		if (cmp_result == 0 && el->serial >= el_next->serial) {
-			printk(KERN_ERR "list_sort() failed to preserve order "
-					"of equivalent elements!\n");
+			printk(KERN_ERR "list_sort_test: failed to preserve"
+					" order of equivalent elements\n");
 			goto exit;
 		}
 		count++;
 	}
 	if (count != LIST_SORT_TEST_LENGTH) {
-		printk(KERN_ERR "list_sort() returned list of "
-				"different length!\n");
+		printk(KERN_ERR "list_sort_test: list length changed\n");
 		goto exit;
 	}
 	err = 0;

[email protected]

author

2010-08-24 16:03 UTC #6 lore raw

PATCH 6/10 lib/list_sort: selftest: cleanups: use signed arithmetic, noinline

In reply to [email protected]

- change list struct field to "int", from "unsigned", to avoid needless perils of unsigned arithmetic
- noinline the test "cmp" function, for better stack traces
- rename list struct for more consistency
- " ? : " not "?:"

Signed-off-by Don Mullis <[email protected]>

Cc Artem Bityutskiy <[email protected]>

---
 lib/list_sort.c |   29 +++++++++++++++--------------
 1 file changed, 15 insertions(+), 14 deletions(-)

lib/list_sort.c +15 ~~-14~~

Index: linux-next/lib/list_sort.c
===================================================================
@@ -29,7 +29,7 @@ static struct list_head *merge(void *pri
 		}
 		tail = tail->next;
 	}
-	tail->next = a?:b;
+	tail->next = a ? : b;
 	return head.next;
 }

@@ -143,16 +143,17 @@ EXPORT_SYMBOL(list_sort);
 
 #ifdef CONFIG_TEST_LIST_SORT
 #include <linux/random.h>
-struct debug_el {
+struct test_el {
 	struct list_head list;
 	int value;
-	unsigned serial;
+	int serial;
 };
 
-static int cmp(void *priv, struct list_head *a, struct list_head *b)
+static noinline int __init test_cmp(void *priv, struct list_head *a,
+						struct list_head *b)
 {
-	return container_of(a, struct debug_el, list)->value
-	     - container_of(b, struct debug_el, list)->value;
+	return container_of(a, struct test_el, list)->value
+	     - container_of(b, struct test_el, list)->value;
 }
 
 /*

@@ -171,7 +172,7 @@ static int __init list_sort_test(void)
 
 	cur = &head;
 	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
-		struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
+		struct test_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
 		if (!el) {
 			printk(KERN_ERR "list_sort_test: cannot	allocate memory"
 					" -- testing aborted\n");

@@ -187,13 +188,13 @@ static int __init list_sort_test(void)
 	}
 	head.prev = cur;
 
-	list_sort(NULL, &head, cmp);
+	list_sort(NULL, &head, test_cmp);
 
 	count = 1;
 	for (cur = head.next; cur->next != &head; cur = cur->next) {
-		struct debug_el *el;
-		struct debug_el *el_next;
-		int cmp_result = cmp(NULL, cur, cur->next);
+		struct test_el *el;
+		struct test_el *el_next;
+		int cmp_result = test_cmp(NULL, cur, cur->next);
 		if (cur->next->prev != cur) {
 			printk(KERN_ERR "list_sort_test: list corrupted\n");
 			goto exit;

@@ -202,8 +203,8 @@ static int __init list_sort_test(void)
 			printk(KERN_ERR "list_sort_test: failed to sort\n");
 			goto exit;
 		}
-		el = container_of(cur, struct debug_el, list);
-		el_next = container_of(cur->next, struct debug_el, list);
+		el = container_of(cur, struct test_el, list);
+		el_next = container_of(cur->next, struct test_el, list);
 		if (cmp_result == 0 && el->serial >= el_next->serial) {
 			printk(KERN_ERR "list_sort_test: failed to preserve"
 					" order of equivalent elements\n");

@@ -219,7 +220,7 @@ static int __init list_sort_test(void)
 exit:
 	list_for_each_safe(cur, tmp, &head) {
 		list_del(cur);
-		kfree(container_of(cur, struct debug_el, list));
+		kfree(container_of(cur, struct test_el, list));
 	}
 	return err;
 }

[email protected]

author

2010-08-24 16:02 UTC #7 lore raw

PATCH 7/10 lib/list_sort: selftest: strengthen checking to expose corner case

In reply to [email protected]

Strengthen checking in selftest's cmp() function, to expose power-of-two corner case.

Signed-off-by Don Mullis <[email protected]>

Cc Artem Bityutskiy <[email protected]>

---
 lib/list_sort.c |   42 +++++++++++++++++++++++++++++++++---------
 1 file changed, 33 insertions(+), 9 deletions(-)

lib/list_sort.c +33 -9

Index: linux-next/lib/list_sort.c
===================================================================
@@ -149,11 +149,27 @@ struct test_el {
 	int serial;
 };
 
+struct test_priv {
+	int err_from_test_cmp;
+	int max_serial;
+};
+
 static noinline int __init test_cmp(void *priv, struct list_head *a,
 						struct list_head *b)
 {
-	return container_of(a, struct test_el, list)->value
-	     - container_of(b, struct test_el, list)->value;
+	struct test_el *el_a = container_of(a, struct test_el, list);
+	struct test_el *el_b = container_of(b, struct test_el, list);
+	struct test_priv *test_p = (struct test_priv *)priv;
+
+	if ((el_a->serial > test_p->max_serial) ||
+	    (el_b->serial > test_p->max_serial)) {
+		printk(KERN_ERR "list_sort_test: test_cmp() found invalid"
+							 " serial number\n");
+		test_p->err_from_test_cmp = -EINVAL;
+	}
+
+	return el_a->value
+	     - el_b->value;
 }
 
 /*

@@ -165,12 +181,18 @@ static noinline int __init test_cmp(void
 static int __init list_sort_test(void)
 {
 	int i, count, err = -EINVAL;
-	struct list_head head;
+	struct test_el fat_head;
 	struct list_head *cur, *tmp;
+	struct test_priv test_p;
 
 	printk(KERN_DEBUG "list_sort_test: starting\n");
 
-	cur = &head;
+	test_p.err_from_test_cmp = 0;
+
+	fat_head.value = INT_MAX;
+	fat_head.serial = INT_MAX;
+
+	cur = &fat_head.list;
 	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
 		struct test_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
 		if (!el) {

@@ -186,15 +208,17 @@ static int __init list_sort_test(void)
 		cur->next = &el->list;
 		cur = cur->next;
 	}
-	head.prev = cur;
+	fat_head.list.prev = cur;
+	test_p.max_serial = i;
 
-	list_sort(NULL, &head, test_cmp);
+	list_sort(&test_p, &fat_head.list, test_cmp);
 
 	count = 1;
-	for (cur = head.next; cur->next != &head; cur = cur->next) {
+	for (cur = fat_head.list.next; cur->next != &fat_head.list;
+							cur = cur->next) {
 		struct test_el *el;
 		struct test_el *el_next;
-		int cmp_result = test_cmp(NULL, cur, cur->next);
+		int cmp_result = test_cmp(&test_p, cur, cur->next);
 		if (cur->next->prev != cur) {
 			printk(KERN_ERR "list_sort_test: list corrupted\n");
 			goto exit;

@@ -218,7 +242,7 @@ static int __init list_sort_test(void)
 	}
 	err = 0;
 exit:
-	list_for_each_safe(cur, tmp, &head) {
+	list_for_each_safe(cur, tmp, &fat_head.list) {
 		list_del(cur);
 		kfree(container_of(cur, struct test_el, list));
 	}

[email protected]

author

2010-08-24 16:03 UTC #8 lore raw

PATCH 8/10 lib/list_sort: selftest: stress algorithm with lists of various lengths

In reply to [email protected]

Add a loop that tests lists of various lengths, including some powers-of-two, which are a corner case for this algorithm.

Signed-off-by Don Mullis <[email protected]>

Cc Artem Bityutskiy <[email protected]>

---
Testing verifies that the powers-of-two bug is reported on the boot console.

 lib/list_sort.c |   32 ++++++++++++++++++++++++--------
 1 file changed, 24 insertions(+), 8 deletions(-)

lib/list_sort.c +24 -8

Index: linux-next/lib/list_sort.c
===================================================================
@@ -174,18 +174,19 @@ static noinline int __init test_cmp(void
 
 /*
  * The pattern of set bits in the list length determines which cases
- * are hit in list_sort().
+ * are hit in list_sort().  Lengths are payload data, excluding the head.
  */
-#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
+static int list_lengths[] = { 512+128+2, 1024-2, 1024-1, 1024, 1024+1, 1, 0 };
 
-static int __init list_sort_test(void)
+static int __init test_one_case(int list_length)
 {
 	int i, count, err = -EINVAL;
 	struct test_el fat_head;
 	struct list_head *cur, *tmp;
 	struct test_priv test_p;
 
-	printk(KERN_DEBUG "list_sort_test: starting\n");
+	printk(KERN_DEBUG "list_sort_test: testing list of length %d\n",
+								list_length);
 
 	test_p.err_from_test_cmp = 0;

@@ -193,7 +194,8 @@ static int __init list_sort_test(void)
 	fat_head.serial = INT_MAX;
 
 	cur = &fat_head.list;
-	for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
+	fat_head.list.next = &fat_head.list;  /* required by zero-length test */
+	for (i = 0; i < list_length; i++) {
 		struct test_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
 		if (!el) {
 			printk(KERN_ERR "list_sort_test: cannot	allocate memory"

@@ -201,7 +203,7 @@ static int __init list_sort_test(void)
 			goto exit;
 		}
 		 /* force some equivalencies */
-		el->value = random32() % (LIST_SORT_TEST_LENGTH/3);
+		el->value = random32() % list_length / 3;
 		el->serial = i;
 
 		el->list.prev = cur;

@@ -213,7 +215,10 @@ static int __init list_sort_test(void)
 
 	list_sort(&test_p, &fat_head.list, test_cmp);
 
-	count = 1;
+	/* zero-length lists are a special case, alas */
+	if (list_length == 0)
+		return 0;
+	count = 0;
 	for (cur = fat_head.list.next; cur->next != &fat_head.list;
 							cur = cur->next) {
 		struct test_el *el;

@@ -236,7 +241,7 @@ static int __init list_sort_test(void)
 		}
 		count++;
 	}
-	if (count != LIST_SORT_TEST_LENGTH) {
+	if (count+1 != list_length) {
 		printk(KERN_ERR "list_sort_test: list length changed\n");
 		goto exit;
 	}

@@ -248,5 +253,16 @@ exit:
 	}
 	return err;
 }
+
+static int __init list_sort_test(void)
+{
+	int i;
+	for (i = 0; i < ARRAY_SIZE(list_lengths); i++) {
+		int err = test_one_case(list_lengths[i]);
+		if (err)
+			return err;
+	}
+	return 0;
+}
 module_init(list_sort_test);
 #endif /* CONFIG_TEST_LIST_SORT */

[email protected]

author

2010-08-24 16:03 UTC #9 lore raw

PATCH 9/10 lib/list_sort: improve list_sort() function documentation

In reply to [email protected]

From: Artem Bityutskiy <[email protected]>

Remind users that degenerate callbacks to cmp(a, b), with a==b, are normal.

Signed-off-by Artem Bityutskiy <[email protected]>

Signed-off-by Don Mullis <[email protected]>

---
 lib/list_sort.c |    7 +++++++
 1 file changed, 7 insertions(+)

lib/list_sort.c +7 -0

Index: linux-next/lib/list_sort.c
===================================================================
@@ -93,6 +93,13 @@ static void merge_and_restore_back_links
  * should sort before @b, and a positive value if @a should sort after
  * @b. If @a and @b are equivalent, and their original relative
  * ordering is to be preserved, @cmp must return 0.
+ *
+ * This function may be used in atomic context, and may be
+ * long-running, in which case @cmp must take care of calling
+ * 'cond_resched()' when needed. And 'list_sort()' will sometimes call
+ * @cmp with @a == @b, just to let the user call 'cond_resched()'.
+ * This "degenerate" callback comes from a loop that requires no
+ * actual comparison results, but nevertheless runs in O(n) time.
  */
 void list_sort(void *priv, struct list_head *head,
 		int (*cmp)(void *priv, struct list_head *a,

[email protected]

author

2010-08-24 16:03 UTC #10 lore raw

PATCH 10/10 lib/list_sort: fix bad args in callback to clients cmp()

In reply to [email protected]

Commit 835cc0c8477fdbc59e0217891d6f11061b1ac4e2 introduced the bug that if the list to be sorted is a power-of-two in length, cmp() may be passed pointers to the list header rather than to a list element. This typically causes the caller's cmp() to read from invalid memory locations off one end or the other of the list_head struct.

Signed-off-by Don Mullis <[email protected]>

Tested-by Artem Bityutskiy <[email protected]>

Signed-off-by Artem Bityutskiy <[email protected]>

To: Alex Elder <[email protected]>
To: David Airlie <[email protected]>
Cc: [email protected]
---
Examination of client code in xfs_buf.c and drm_modes.c showed no obvious vulnerability to crashing: memory at offsets reachable by cmp() appeared to always be readable, and the cmp() functions do not dereference any pointers in the struct that they assume they have been passed.

 lib/list_sort.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

lib/list_sort.c +1 -1

Index: linux-next/lib/list_sort.c
===================================================================
@@ -70,7 +70,7 @@ static void merge_and_restore_back_links
 		 * element comparison is needed, so the client's cmp()
 		 * routine can invoke cond_resched() periodically.
 		 */
-		(*cmp)(priv, tail, tail);
+		(*cmp)(priv, tail->next, tail->next);
 
 		tail->next->prev = tail;
 		tail = tail->next;