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 Cc: Artem Bityutskiy --- 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 */ -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/