lib/test_list_sort.c

   1 #define pr_fmt(fmt) "list_sort_test: " fmt
   2
   3 #include <linux/kernel.h>
   4 #include <linux/list_sort.h>
   5 #include <linux/list.h>
   6 #include <linux/module.h>
   7 #include <linux/printk.h>
   8 #include <linux/slab.h>
   9 #include <linux/random.h>
  10
  11 /*
  12  * The pattern of set bits in the list length determines which cases
  13  * are hit in list_sort().
  14  */
  15 #define TEST_LIST_LEN (512+128+2) /* not including head */
  16
  17 #define TEST_POISON1 0xDEADBEEF
  18 #define TEST_POISON2 0xA324354C
  19
  20 struct debug_el {
  21         unsigned int poison1;
  22         struct list_head list;
  23         unsigned int poison2;
  24         int value;
  25         unsigned serial;
  26 };
  27
  28 /* Array, containing pointers to all elements in the test list */
  29 static struct debug_el **elts __initdata;
  30
  31 static int __init check(struct debug_el *ela, struct debug_el *elb)
  32 {
  33         if (ela->serial >= TEST_LIST_LEN) {
  34                 pr_err("error: incorrect serial %d\n", ela->serial);
  35                 return -EINVAL;
  36         }
  37         if (elb->serial >= TEST_LIST_LEN) {
  38                 pr_err("error: incorrect serial %d\n", elb->serial);
  39                 return -EINVAL;
  40         }
  41         if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
  42                 pr_err("error: phantom element\n");
  43                 return -EINVAL;
  44         }
  45         if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
  46                 pr_err("error: bad poison: %#x/%#x\n",
  47                         ela->poison1, ela->poison2);
  48                 return -EINVAL;
  49         }
  50         if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
  51                 pr_err("error: bad poison: %#x/%#x\n",
  52                         elb->poison1, elb->poison2);
  53                 return -EINVAL;
  54         }
  55         return 0;
  56 }
  57
  58 static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
  59 {
  60         struct debug_el *ela, *elb;
  61
  62         ela = container_of(a, struct debug_el, list);
  63         elb = container_of(b, struct debug_el, list);
  64
  65         check(ela, elb);
  66         return ela->value - elb->value;
  67 }
  68
  69 static int __init list_sort_test(void)
  70 {
  71         int i, count = 1, err = -ENOMEM;
  72         struct debug_el *el;
  73         struct list_head *cur;
  74         LIST_HEAD(head);
  75
  76         pr_debug("start testing list_sort()\n");
  77
  78         elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
  79         if (!elts) {
  80                 pr_err("error: cannot allocate memory\n");
  81                 return err;
  82         }
  83
  84         for (i = 0; i < TEST_LIST_LEN; i++) {
  85                 el = kmalloc(sizeof(*el), GFP_KERNEL);
  86                 if (!el) {
  87                         pr_err("error: cannot allocate memory\n");
  88                         goto exit;
  89                 }
  90                  /* force some equivalencies */
  91                 el->value = prandom_u32() % (TEST_LIST_LEN / 3);
  92                 el->serial = i;
  93                 el->poison1 = TEST_POISON1;
  94                 el->poison2 = TEST_POISON2;
  95                 elts[i] = el;
  96                 list_add_tail(&el->list, &head);
  97         }
  98
  99         list_sort(NULL, &head, cmp);
 100
 101         err = -EINVAL;
 102         for (cur = head.next; cur->next != &head; cur = cur->next) {
 103                 struct debug_el *el1;
 104                 int cmp_result;
 105
 106                 if (cur->next->prev != cur) {
 107                         pr_err("error: list is corrupted\n");
 108                         goto exit;
 109                 }
 110
 111                 cmp_result = cmp(NULL, cur, cur->next);
 112                 if (cmp_result > 0) {
 113                         pr_err("error: list is not sorted\n");
 114                         goto exit;
 115                 }
 116
 117                 el = container_of(cur, struct debug_el, list);
 118                 el1 = container_of(cur->next, struct debug_el, list);
 119                 if (cmp_result == 0 && el->serial >= el1->serial) {
 120                         pr_err("error: order of equivalent elements not "
 121                                 "preserved\n");
 122                         goto exit;
 123                 }
 124
 125                 if (check(el, el1)) {
 126                         pr_err("error: element check failed\n");
 127                         goto exit;
 128                 }
 129                 count++;
 130         }
 131         if (head.prev != cur) {
 132                 pr_err("error: list is corrupted\n");
 133                 goto exit;
 134         }
 135
 136
 137         if (count != TEST_LIST_LEN) {
 138                 pr_err("error: bad list length %d", count);
 139                 goto exit;
 140         }
 141
 142         err = 0;
 143 exit:
 144         for (i = 0; i < TEST_LIST_LEN; i++)
 145                 kfree(elts[i]);
 146         kfree(elts);
 147         return err;
 148 }
 149 module_init(list_sort_test);
 150 MODULE_LICENSE("GPL");