aboutsummaryrefslogtreecommitdiffstats
path: root/lib/list_sort.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/list_sort.c')
-rw-r--r--lib/list_sort.c172
1 files changed, 123 insertions, 49 deletions
diff --git a/lib/list_sort.c b/lib/list_sort.c
index a7616fa3162..d7325c6b103 100644
--- a/lib/list_sort.c
+++ b/lib/list_sort.c
@@ -141,77 +141,151 @@ void list_sort(void *priv, struct list_head *head,
}
EXPORT_SYMBOL(list_sort);
-#ifdef DEBUG_LIST_SORT
+#ifdef CONFIG_TEST_LIST_SORT
+
+#include <linux/random.h>
+
+/*
+ * The pattern of set bits in the list length determines which cases
+ * are hit in list_sort().
+ */
+#define TEST_LIST_LEN (512+128+2) /* not including head */
+
+#define TEST_POISON1 0xDEADBEEF
+#define TEST_POISON2 0xA324354C
+
struct debug_el {
- struct list_head l_h;
+ unsigned int poison1;
+ struct list_head list;
+ unsigned int poison2;
int value;
unsigned serial;
};
-static int cmp(void *priv, struct list_head *a, struct list_head *b)
+/* Array, containing pointers to all elements in the test list */
+static struct debug_el **elts __initdata;
+
+static int __init check(struct debug_el *ela, struct debug_el *elb)
{
- return container_of(a, struct debug_el, l_h)->value
- - container_of(b, struct debug_el, l_h)->value;
+ if (ela->serial >= TEST_LIST_LEN) {
+ printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
+ ela->serial);
+ return -EINVAL;
+ }
+ if (elb->serial >= TEST_LIST_LEN) {
+ printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
+ elb->serial);
+ return -EINVAL;
+ }
+ if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
+ printk(KERN_ERR "list_sort_test: error: phantom element\n");
+ return -EINVAL;
+ }
+ if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
+ printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
+ ela->poison1, ela->poison2);
+ return -EINVAL;
+ }
+ if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
+ printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
+ elb->poison1, elb->poison2);
+ return -EINVAL;
+ }
+ return 0;
}
-/*
- * The pattern of set bits in the list length determines which cases
- * are hit in list_sort().
- */
-#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
+static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
+{
+ struct debug_el *ela, *elb;
+
+ ela = container_of(a, struct debug_el, list);
+ elb = container_of(b, struct debug_el, list);
+
+ check(ela, elb);
+ return ela->value - elb->value;
+}
static int __init list_sort_test(void)
{
- int i, r = 1, count;
- struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
- struct list_head *cur;
+ int i, count = 1, err = -EINVAL;
+ struct debug_el *el;
+ struct list_head *cur, *tmp;
+ LIST_HEAD(head);
+
+ printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
- printk(KERN_WARNING "testing list_sort()\n");
+ elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL);
+ if (!elts) {
+ printk(KERN_ERR "list_sort_test: error: cannot allocate "
+ "memory\n");
+ goto exit;
+ }
- cur = head;
- for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
- struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
- BUG_ON(!el);
+ for (i = 0; i < TEST_LIST_LEN; i++) {
+ el = kmalloc(sizeof(*el), GFP_KERNEL);
+ if (!el) {
+ printk(KERN_ERR "list_sort_test: error: cannot "
+ "allocate memory\n");
+ goto exit;
+ }
/* force some equivalencies */
- el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
+ el->value = random32() % (TEST_LIST_LEN/3);
el->serial = i;
-
- el->l_h.prev = cur;
- cur->next = &el->l_h;
- cur = cur->next;
+ el->poison1 = TEST_POISON1;
+ el->poison2 = TEST_POISON2;
+ elts[i] = el;
+ list_add_tail(&el->list, &head);
}
- head->prev = cur;
- list_sort(NULL, head, cmp);
+ list_sort(NULL, &head, cmp);
+
+ for (cur = head.next; cur->next != &head; cur = cur->next) {
+ struct debug_el *el1;
+ int cmp_result;
- count = 1;
- for (cur = head->next; cur->next != head; cur = cur->next) {
- 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");
- return 1;
- } else if (cmp_result > 0) {
- printk(KERN_EMERG "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");
- return 1;
+ printk(KERN_ERR "list_sort_test: error: list is "
+ "corrupted\n");
+ goto exit;
+ }
+
+ cmp_result = cmp(NULL, cur, cur->next);
+ if (cmp_result > 0) {
+ printk(KERN_ERR "list_sort_test: error: list is not "
+ "sorted\n");
+ goto exit;
+ }
+
+ el = container_of(cur, struct debug_el, list);
+ el1 = container_of(cur->next, struct debug_el, list);
+ if (cmp_result == 0 && el->serial >= el1->serial) {
+ printk(KERN_ERR "list_sort_test: error: order of "
+ "equivalent elements not preserved\n");
+ goto exit;
+ }
+
+ if (check(el, el1)) {
+ printk(KERN_ERR "list_sort_test: error: element check "
+ "failed\n");
+ goto exit;
}
- kfree(cur->prev);
count++;
}
- kfree(cur);
- if (count != LIST_SORT_TEST_LENGTH) {
- printk(KERN_EMERG "list_sort() returned list of"
- "different length!\n");
- return 1;
+
+ if (count != TEST_LIST_LEN) {
+ printk(KERN_ERR "list_sort_test: error: bad list length %d",
+ count);
+ goto exit;
}
- return 0;
+
+ err = 0;
+exit:
+ kfree(elts);
+ list_for_each_safe(cur, tmp, &head) {
+ list_del(cur);
+ kfree(container_of(cur, struct debug_el, list));
+ }
+ return err;
}
module_init(list_sort_test);
-#endif
+#endif /* CONFIG_TEST_LIST_SORT */