test_ida.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * test_ida.c: Test the IDA API
  4. * Copyright (c) 2016-2018 Microsoft Corporation
  5. * Copyright (c) 2018 Oracle Corporation
  6. * Author: Matthew Wilcox <willy@infradead.org>
  7. */
  8. #include <linux/idr.h>
  9. #include <linux/module.h>
  10. static unsigned int tests_run;
  11. static unsigned int tests_passed;
  12. #ifdef __KERNEL__
  13. void ida_dump(struct ida *ida) { }
  14. #endif
  15. #define IDA_BUG_ON(ida, x) do { \
  16. tests_run++; \
  17. if (x) { \
  18. ida_dump(ida); \
  19. dump_stack(); \
  20. } else { \
  21. tests_passed++; \
  22. } \
  23. } while (0)
  24. /*
  25. * Straightforward checks that allocating and freeing IDs work.
  26. */
  27. static void ida_check_alloc(struct ida *ida)
  28. {
  29. int i, id;
  30. for (i = 0; i < 10000; i++)
  31. IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  32. ida_free(ida, 20);
  33. ida_free(ida, 21);
  34. for (i = 0; i < 3; i++) {
  35. id = ida_alloc(ida, GFP_KERNEL);
  36. IDA_BUG_ON(ida, id < 0);
  37. if (i == 2)
  38. IDA_BUG_ON(ida, id != 10000);
  39. }
  40. for (i = 0; i < 5000; i++)
  41. ida_free(ida, i);
  42. IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
  43. ida_destroy(ida);
  44. IDA_BUG_ON(ida, !ida_is_empty(ida));
  45. }
  46. /* Destroy an IDA with a single entry at @base */
  47. static void ida_check_destroy_1(struct ida *ida, unsigned int base)
  48. {
  49. IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
  50. IDA_BUG_ON(ida, ida_is_empty(ida));
  51. ida_destroy(ida);
  52. IDA_BUG_ON(ida, !ida_is_empty(ida));
  53. }
  54. /* Check that ida_destroy and ida_is_empty work */
  55. static void ida_check_destroy(struct ida *ida)
  56. {
  57. /* Destroy an already-empty IDA */
  58. IDA_BUG_ON(ida, !ida_is_empty(ida));
  59. ida_destroy(ida);
  60. IDA_BUG_ON(ida, !ida_is_empty(ida));
  61. ida_check_destroy_1(ida, 0);
  62. ida_check_destroy_1(ida, 1);
  63. ida_check_destroy_1(ida, 1023);
  64. ida_check_destroy_1(ida, 1024);
  65. ida_check_destroy_1(ida, 12345678);
  66. }
  67. /*
  68. * Check what happens when we fill a leaf and then delete it. This may
  69. * discover mishandling of IDR_FREE.
  70. */
  71. static void ida_check_leaf(struct ida *ida, unsigned int base)
  72. {
  73. unsigned long i;
  74. for (i = 0; i < IDA_BITMAP_BITS; i++) {
  75. IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  76. base + i);
  77. }
  78. ida_destroy(ida);
  79. IDA_BUG_ON(ida, !ida_is_empty(ida));
  80. IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
  81. IDA_BUG_ON(ida, ida_is_empty(ida));
  82. ida_free(ida, 0);
  83. IDA_BUG_ON(ida, !ida_is_empty(ida));
  84. }
  85. /*
  86. * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
  87. * Allocating up to 2^31-1 should succeed, and then allocating the next one
  88. * should fail.
  89. */
  90. static void ida_check_max(struct ida *ida)
  91. {
  92. unsigned long i, j;
  93. for (j = 1; j < 65537; j *= 2) {
  94. unsigned long base = (1UL << 31) - j;
  95. for (i = 0; i < j; i++) {
  96. IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  97. base + i);
  98. }
  99. IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  100. -ENOSPC);
  101. ida_destroy(ida);
  102. IDA_BUG_ON(ida, !ida_is_empty(ida));
  103. }
  104. }
  105. /*
  106. * Check handling of conversions between exceptional entries and full bitmaps.
  107. */
  108. static void ida_check_conv(struct ida *ida)
  109. {
  110. unsigned long i;
  111. for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
  112. IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
  113. IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
  114. GFP_KERNEL) != i + BITS_PER_LONG);
  115. ida_free(ida, i + 1);
  116. ida_free(ida, i + BITS_PER_LONG);
  117. IDA_BUG_ON(ida, !ida_is_empty(ida));
  118. }
  119. for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
  120. IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  121. for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
  122. ida_free(ida, i - 1);
  123. IDA_BUG_ON(ida, !ida_is_empty(ida));
  124. for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
  125. IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  126. for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
  127. ida_free(ida, i - 1);
  128. IDA_BUG_ON(ida, !ida_is_empty(ida));
  129. }
  130. static DEFINE_IDA(ida);
  131. static int ida_checks(void)
  132. {
  133. IDA_BUG_ON(&ida, !ida_is_empty(&ida));
  134. ida_check_alloc(&ida);
  135. ida_check_destroy(&ida);
  136. ida_check_leaf(&ida, 0);
  137. ida_check_leaf(&ida, 1024);
  138. ida_check_leaf(&ida, 1024 * 64);
  139. ida_check_max(&ida);
  140. ida_check_conv(&ida);
  141. printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
  142. return (tests_run != tests_passed) ? 0 : -EINVAL;
  143. }
  144. static void ida_exit(void)
  145. {
  146. }
  147. module_init(ida_checks);
  148. module_exit(ida_exit);
  149. MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
  150. MODULE_LICENSE("GPL");