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                 return err;
  81
  82         for (i = 0; i < TEST_LIST_LEN; i++) {
  83                 el = kmalloc(sizeof(*el), GFP_KERNEL);
  84                 if (!el)
  85                         goto exit;
  86
  87                  /* force some equivalencies */
  88                 el->value = prandom_u32() % (TEST_LIST_LEN / 3);
  89                 el->serial = i;
  90                 el->poison1 = TEST_POISON1;
  91                 el->poison2 = TEST_POISON2;
  92                 elts[i] = el;
  93                 list_add_tail(&el->list, &head);
  94         }
  95
  96         list_sort(NULL, &head, cmp);
  97
  98         err = -EINVAL;
  99         for (cur = head.next; cur->next != &head; cur = cur->next) {
 100                 struct debug_el *el1;
 101                 int cmp_result;
 102
 103                 if (cur->next->prev != cur) {
 104                         pr_err("error: list is corrupted\n");
 105                         goto exit;
 106                 }
 107
 108                 cmp_result = cmp(NULL, cur, cur->next);
 109                 if (cmp_result > 0) {
 110                         pr_err("error: list is not sorted\n");
 111                         goto exit;
 112                 }
 113
 114                 el = container_of(cur, struct debug_el, list);
 115                 el1 = container_of(cur->next, struct debug_el, list);
 116                 if (cmp_result == 0 && el->serial >= el1->serial) {
 117                         pr_err("error: order of equivalent elements not "
 118                                 "preserved\n");
 119                         goto exit;
 120                 }
 121
 122                 if (check(el, el1)) {
 123                         pr_err("error: element check failed\n");
 124                         goto exit;
 125                 }
 126                 count++;
 127         }
 128         if (head.prev != cur) {
 129                 pr_err("error: list is corrupted\n");
 130                 goto exit;
 131         }
 132
 133
 134         if (count != TEST_LIST_LEN) {
 135                 pr_err("error: bad list length %d", count);
 136                 goto exit;
 137         }
 138
 139         err = 0;
 140 exit:
 141         for (i = 0; i < TEST_LIST_LEN; i++)
 142                 kfree(elts[i]);
 143         kfree(elts);
 144         return err;
 145 }
 146 module_init(list_sort_test);
 147 MODULE_LICENSE("GPL");