lib/test_list_sort.c

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