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