LXR linux/lib/test_list

   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
  20struct 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 */
  29static struct debug_el **elts __initdata;
  30
  31static 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
  58static 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
  69static 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;
 140exit:
 141        for (i = 0; i < TEST_LIST_LEN; i++)
 142                kfree(elts[i]);
 143        kfree(elts);
 144        return err;
 145}
 146module_init(list_sort_test);
 147MODULE_LICENSE("GPL");
 148