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

[don.mullis@gmail.com]

[-- 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 */