[PATCH 00/10] lib/list_sort: strengthen self-test to expose a bug, then fix the bug

[PATCH 00/10] lib/list_sort: strengthen self-test to expose a bug, then fix the bug

[don.mullis]

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.

[PATCH 01/10] lib/list_sort: selftest: enabled with CONFIG_TEST_LIST_SORT

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest-enabled-with-CONFIG_TEST_LIST_SORT.patch --]
[-- Type: text/plain, Size: 1576 bytes --]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

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

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: Don Mullis <don.mullis@gmail.com>
---
 lib/Kconfig.debug |    9 +++++++++
 lib/list_sort.c   |    4 ++--
 2 files changed, 11 insertions(+), 2 deletions(-)

Index: linux-next/lib/Kconfig.debug
===================================================================
--- linux-next.orig/lib/Kconfig.debug	2010-08-23 22:51:13.888053055 -0700
+++ linux-next/lib/Kconfig.debug	2010-08-23 22:51:19.674177607 -0700
@@ -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
Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:13.888053055 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:56.494053043 -0700
@@ -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 */

[PATCH 02/10] lib/list_sort: selftest: use more appropriate printk levels

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest_-use-more-appropriate-printk-levels-2.patch --]
[-- Type: text/plain, Size: 2055 bytes --]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

Use KERN_NORM and KERN_ERR levels for test error messages.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: Don Mullis <don.mullis@gmail.com>
---
 lib/list_sort.c |   16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.674177607 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:56.351052205 -0700
@@ -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;

[PATCH 03/10] lib/list_sort: selftest: cleanups: use random32(), rename variables

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest_-cleanups_-use-random32___-rename-variables-2.patch --]
[-- Type: text/plain, Size: 2688 bytes --]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

 - 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 <Artem.Bityutskiy@nokia.com>
Signed-off-by: Don Mullis <don.mullis@gmail.com>
---
 lib/list_sort.c |   19 ++++++++++---------
 1 file changed, 10 insertions(+), 9 deletions(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.684177611 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:56.170177671 -0700
@@ -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;

[PATCH 04/10] lib/list_sort: selftest: permit normal boot after test failure

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest_-permit-normal-boot-after-test-failure-2.patch --]
[-- Type: text/plain, Size: 3153 bytes --]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

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 <Artem.Bityutskiy@nokia.com>
Signed-off-by: Don Mullis <don.mullis@gmail.com>
---
 lib/list_sort.c |   51 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 31 insertions(+), 20 deletions(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.693177820 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:56.033177095 -0700
@@ -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 */

[PATCH 05/10] lib/list_sort: selftest: improve printk wording

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest_-improve-printk-wording-2.patch --]
[-- Type: text/plain, Size: 2308 bytes --]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

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 <Artem.Bityutskiy@nokia.com>
Signed-off-by: Don Mullis <don.mullis@gmail.com>
---
 lib/list_sort.c |   18 ++++++++----------
 1 file changed, 8 insertions(+), 10 deletions(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.703177580 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:55.854177312 -0700
@@ -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;

[PATCH 06/10] lib/list_sort: selftest: cleanups: use signed arithmetic, noinline

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest_-cleanups_-use-signed-arithmetic_-noinline-7.patch --]
[-- Type: text/plain, Size: 3112 bytes --]

 - 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 <don.mullis@gmail.com>
Cc: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |   29 +++++++++++++++--------------
 1 file changed, 15 insertions(+), 14 deletions(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.732177016 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:55.714177340 -0700
@@ -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;
 }

[PATCH 07/10] lib/list_sort: selftest: strengthen checking to expose corner case

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest_-strengthen-checking-in-selftest_s-cmp__-function-8.patch --]
[-- Type: text/plain, Size: 2849 bytes --]

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

Signed-off-by: Don Mullis <don.mullis@gmail.com>
Cc: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 lib/list_sort.c |   42 +++++++++++++++++++++++++++++++++---------
 1 file changed, 33 insertions(+), 9 deletions(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.745177187 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:55.544177510 -0700
@@ -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));
 	}

[PATCH 08/10] lib/list_sort: selftest: stress algorithm with lists of various lengths

[don.mullis]

[-- Attachment #1: lib_list_sort_-selftest_-expose-bug-with-various-list-lengths-9.patch --]
[-- Type: text/plain, Size: 2986 bytes --]

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 <don.mullis@gmail.com>
Cc: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
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(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.752177567 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:55.391052193 -0700
@@ -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 */

[PATCH 09/10] lib/list_sort: improve list_sort() function documentation

[don.mullis]

[-- Attachment #1: lib_list_sort_-Improve-list_sort__-function-comment-3.patch --]
[-- Type: text/plain, Size: 1306 bytes --]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

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

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: Don Mullis <don.mullis@gmail.com>
---
 lib/list_sort.c |    7 +++++++
 1 file changed, 7 insertions(+)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:51:19.761177595 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:55.242052357 -0700
@@ -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,

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

[don.mullis]

[-- Attachment #1: lib_list_sort_-fix-bad-args-in-callback-to-client_s-cmp__.patch --]
[-- Type: text/plain, Size: 1494 bytes --]

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 <don.mullis@gmail.com>
Tested-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
To: Alex Elder <aelder@sgi.com>
To: David Airlie <airlied@linux.ie>
Cc: stable@kernel.org
---
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(-)

Index: linux-next/lib/list_sort.c
===================================================================
--- linux-next.orig/lib/list_sort.c	2010-08-23 22:59:59.899177219 -0700
+++ linux-next/lib/list_sort.c	2010-08-23 23:01:48.007177492 -0700
@@ -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;