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
9 #include <linux/idr.h>
10 #include <linux/module.h>
11
12 static unsigned int tests_run;
13 static unsigned int tests_passed;
14
15 #ifdef __KERNEL__
ida_dump(struct ida * ida)16 static void ida_dump(struct ida *ida) { }
17 #endif
18 #define IDA_BUG_ON(ida, x) do { \
19 tests_run++; \
20 if (x) { \
21 ida_dump(ida); \
22 dump_stack(); \
23 } else { \
24 tests_passed++; \
25 } \
26 } while (0)
27
28 /*
29 * Straightforward checks that allocating and freeing IDs work.
30 */
ida_check_alloc(struct ida * ida)31 static void ida_check_alloc(struct ida *ida)
32 {
33 int i, id;
34
35 for (i = 0; i < 10000; i++)
36 IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
37
38 ida_free(ida, 20);
39 ida_free(ida, 21);
40 for (i = 0; i < 3; i++) {
41 id = ida_alloc(ida, GFP_KERNEL);
42 IDA_BUG_ON(ida, id < 0);
43 if (i == 2)
44 IDA_BUG_ON(ida, id != 10000);
45 }
46
47 for (i = 0; i < 5000; i++)
48 ida_free(ida, i);
49
50 IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
51 ida_destroy(ida);
52
53 IDA_BUG_ON(ida, !ida_is_empty(ida));
54 }
55
56 /* Destroy an IDA with a single entry at @base */
ida_check_destroy_1(struct ida * ida,unsigned int base)57 static void ida_check_destroy_1(struct ida *ida, unsigned int base)
58 {
59 IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
60 IDA_BUG_ON(ida, ida_is_empty(ida));
61 ida_destroy(ida);
62 IDA_BUG_ON(ida, !ida_is_empty(ida));
63 }
64
65 /* Check that ida_destroy and ida_is_empty work */
ida_check_destroy(struct ida * ida)66 static void ida_check_destroy(struct ida *ida)
67 {
68 /* Destroy an already-empty IDA */
69 IDA_BUG_ON(ida, !ida_is_empty(ida));
70 ida_destroy(ida);
71 IDA_BUG_ON(ida, !ida_is_empty(ida));
72
73 ida_check_destroy_1(ida, 0);
74 ida_check_destroy_1(ida, 1);
75 ida_check_destroy_1(ida, 1023);
76 ida_check_destroy_1(ida, 1024);
77 ida_check_destroy_1(ida, 12345678);
78 }
79
80 /*
81 * Check what happens when we fill a leaf and then delete it. This may
82 * discover mishandling of IDR_FREE.
83 */
ida_check_leaf(struct ida * ida,unsigned int base)84 static void ida_check_leaf(struct ida *ida, unsigned int base)
85 {
86 unsigned long i;
87
88 for (i = 0; i < IDA_BITMAP_BITS; i++) {
89 IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
90 base + i);
91 }
92
93 ida_destroy(ida);
94 IDA_BUG_ON(ida, !ida_is_empty(ida));
95
96 IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
97 IDA_BUG_ON(ida, ida_is_empty(ida));
98 ida_free(ida, 0);
99 IDA_BUG_ON(ida, !ida_is_empty(ida));
100 }
101
102 /*
103 * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
104 * Allocating up to 2^31-1 should succeed, and then allocating the next one
105 * should fail.
106 */
ida_check_max(struct ida * ida)107 static void ida_check_max(struct ida *ida)
108 {
109 unsigned long i, j;
110
111 for (j = 1; j < 65537; j *= 2) {
112 unsigned long base = (1UL << 31) - j;
113 for (i = 0; i < j; i++) {
114 IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
115 base + i);
116 }
117 IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
118 -ENOSPC);
119 ida_destroy(ida);
120 IDA_BUG_ON(ida, !ida_is_empty(ida));
121 }
122 }
123
124 /*
125 * Check handling of conversions between exceptional entries and full bitmaps.
126 */
ida_check_conv(struct ida * ida)127 static void ida_check_conv(struct ida *ida)
128 {
129 unsigned long i;
130
131 for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
132 IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
133 IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
134 GFP_KERNEL) != i + BITS_PER_LONG);
135 ida_free(ida, i + 1);
136 ida_free(ida, i + BITS_PER_LONG);
137 IDA_BUG_ON(ida, !ida_is_empty(ida));
138 }
139
140 for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
141 IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
142 for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
143 ida_free(ida, i - 1);
144 IDA_BUG_ON(ida, !ida_is_empty(ida));
145
146 for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
147 IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
148 for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
149 ida_free(ida, i - 1);
150 IDA_BUG_ON(ida, !ida_is_empty(ida));
151 }
152
153 /*
154 * Check various situations where we attempt to free an ID we don't own.
155 */
ida_check_bad_free(struct ida * ida)156 static void ida_check_bad_free(struct ida *ida)
157 {
158 unsigned long i;
159
160 printk("vvv Ignore \"not allocated\" warnings\n");
161 /* IDA is empty; all of these will fail */
162 ida_free(ida, 0);
163 for (i = 0; i < 31; i++)
164 ida_free(ida, 1 << i);
165
166 /* IDA contains a single value entry */
167 IDA_BUG_ON(ida, ida_alloc_min(ida, 3, GFP_KERNEL) != 3);
168 ida_free(ida, 0);
169 for (i = 0; i < 31; i++)
170 ida_free(ida, 1 << i);
171
172 /* IDA contains a single bitmap */
173 IDA_BUG_ON(ida, ida_alloc_min(ida, 1023, GFP_KERNEL) != 1023);
174 ida_free(ida, 0);
175 for (i = 0; i < 31; i++)
176 ida_free(ida, 1 << i);
177
178 /* IDA contains a tree */
179 IDA_BUG_ON(ida, ida_alloc_min(ida, (1 << 20) - 1, GFP_KERNEL) != (1 << 20) - 1);
180 ida_free(ida, 0);
181 for (i = 0; i < 31; i++)
182 ida_free(ida, 1 << i);
183 printk("^^^ \"not allocated\" warnings over\n");
184
185 ida_free(ida, 3);
186 ida_free(ida, 1023);
187 ida_free(ida, (1 << 20) - 1);
188
189 IDA_BUG_ON(ida, !ida_is_empty(ida));
190 }
191
192 /*
193 * Check ida_find_first_range() and varriants.
194 */
ida_check_find_first(struct ida * ida)195 static void ida_check_find_first(struct ida *ida)
196 {
197 /* IDA is empty; all of the below should be not exist */
198 IDA_BUG_ON(ida, ida_exists(ida, 0));
199 IDA_BUG_ON(ida, ida_exists(ida, 3));
200 IDA_BUG_ON(ida, ida_exists(ida, 63));
201 IDA_BUG_ON(ida, ida_exists(ida, 1023));
202 IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
203
204 /* IDA contains a single value entry */
205 IDA_BUG_ON(ida, ida_alloc_min(ida, 3, GFP_KERNEL) != 3);
206 IDA_BUG_ON(ida, ida_exists(ida, 0));
207 IDA_BUG_ON(ida, !ida_exists(ida, 3));
208 IDA_BUG_ON(ida, ida_exists(ida, 63));
209 IDA_BUG_ON(ida, ida_exists(ida, 1023));
210 IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
211
212 IDA_BUG_ON(ida, ida_alloc_min(ida, 63, GFP_KERNEL) != 63);
213 IDA_BUG_ON(ida, ida_exists(ida, 0));
214 IDA_BUG_ON(ida, !ida_exists(ida, 3));
215 IDA_BUG_ON(ida, !ida_exists(ida, 63));
216 IDA_BUG_ON(ida, ida_exists(ida, 1023));
217 IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
218
219 /* IDA contains a single bitmap */
220 IDA_BUG_ON(ida, ida_alloc_min(ida, 1023, GFP_KERNEL) != 1023);
221 IDA_BUG_ON(ida, ida_exists(ida, 0));
222 IDA_BUG_ON(ida, !ida_exists(ida, 3));
223 IDA_BUG_ON(ida, !ida_exists(ida, 63));
224 IDA_BUG_ON(ida, !ida_exists(ida, 1023));
225 IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
226
227 /* IDA contains a tree */
228 IDA_BUG_ON(ida, ida_alloc_min(ida, (1 << 20) - 1, GFP_KERNEL) != (1 << 20) - 1);
229 IDA_BUG_ON(ida, ida_exists(ida, 0));
230 IDA_BUG_ON(ida, !ida_exists(ida, 3));
231 IDA_BUG_ON(ida, !ida_exists(ida, 63));
232 IDA_BUG_ON(ida, !ida_exists(ida, 1023));
233 IDA_BUG_ON(ida, !ida_exists(ida, (1 << 20) - 1));
234
235 /* Now try to find first */
236 IDA_BUG_ON(ida, ida_find_first(ida) != 3);
237 IDA_BUG_ON(ida, ida_find_first_range(ida, -1, 2) != -EINVAL);
238 IDA_BUG_ON(ida, ida_find_first_range(ida, 0, 2) != -ENOENT); // no used ID
239 IDA_BUG_ON(ida, ida_find_first_range(ida, 0, 3) != 3);
240 IDA_BUG_ON(ida, ida_find_first_range(ida, 1, 3) != 3);
241 IDA_BUG_ON(ida, ida_find_first_range(ida, 3, 3) != 3);
242 IDA_BUG_ON(ida, ida_find_first_range(ida, 2, 4) != 3);
243 IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 3) != -ENOENT); // min > max, fail
244 IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 60) != -ENOENT); // no used ID
245 IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 64) != 63);
246 IDA_BUG_ON(ida, ida_find_first_range(ida, 63, 63) != 63);
247 IDA_BUG_ON(ida, ida_find_first_range(ida, 64, 1026) != 1023);
248 IDA_BUG_ON(ida, ida_find_first_range(ida, 1023, 1023) != 1023);
249 IDA_BUG_ON(ida, ida_find_first_range(ida, 1023, (1 << 20) - 1) != 1023);
250 IDA_BUG_ON(ida, ida_find_first_range(ida, 1024, (1 << 20) - 1) != (1 << 20) - 1);
251 IDA_BUG_ON(ida, ida_find_first_range(ida, (1 << 20), INT_MAX) != -ENOENT);
252
253 ida_free(ida, 3);
254 ida_free(ida, 63);
255 ida_free(ida, 1023);
256 ida_free(ida, (1 << 20) - 1);
257
258 IDA_BUG_ON(ida, !ida_is_empty(ida));
259 }
260
261 static DEFINE_IDA(ida);
262
ida_checks(void)263 static int ida_checks(void)
264 {
265 IDA_BUG_ON(&ida, !ida_is_empty(&ida));
266 ida_check_alloc(&ida);
267 ida_check_destroy(&ida);
268 ida_check_leaf(&ida, 0);
269 ida_check_leaf(&ida, 1024);
270 ida_check_leaf(&ida, 1024 * 64);
271 ida_check_max(&ida);
272 ida_check_conv(&ida);
273 ida_check_bad_free(&ida);
274 ida_check_find_first(&ida);
275
276 printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
277 return (tests_run != tests_passed) ? 0 : -EINVAL;
278 }
279
ida_exit(void)280 static void ida_exit(void)
281 {
282 }
283
284 module_init(ida_checks);
285 module_exit(ida_exit);
286 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
287 MODULE_DESCRIPTION("Test the IDA API");
288 MODULE_LICENSE("GPL");
289