test_list_sort.c 3.3 KB

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