1 /*
2  * idr-test.c: Test the IDR API
3  * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org>
4  *
5  * This program is free software; you can redistribute it and/or modify it
6  * under the terms and conditions of the GNU General Public License,
7  * version 2, as published by the Free Software Foundation.
8  *
9  * This program is distributed in the hope it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
12  * more details.
13  */
14 #include <linux/bitmap.h>
15 #include <linux/idr.h>
16 #include <linux/slab.h>
17 #include <linux/kernel.h>
18 #include <linux/errno.h>
19 
20 #include "test.h"
21 
22 #define DUMMY_PTR	((void *)0x12)
23 
24 int item_idr_free(int id, void *p, void *data)
25 {
26 	struct item *item = p;
27 	assert(item->index == id);
28 	free(p);
29 
30 	return 0;
31 }
32 
33 void item_idr_remove(struct idr *idr, int id)
34 {
35 	struct item *item = idr_find(idr, id);
36 	assert(item->index == id);
37 	idr_remove(idr, id);
38 	free(item);
39 }
40 
41 void idr_alloc_test(void)
42 {
43 	unsigned long i;
44 	DEFINE_IDR(idr);
45 
46 	assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0);
47 	assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd);
48 	idr_remove(&idr, 0x3ffd);
49 	idr_remove(&idr, 0);
50 
51 	for (i = 0x3ffe; i < 0x4003; i++) {
52 		int id;
53 		struct item *item;
54 
55 		if (i < 0x4000)
56 			item = item_create(i, 0);
57 		else
58 			item = item_create(i - 0x3fff, 0);
59 
60 		id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL);
61 		assert(id == item->index);
62 	}
63 
64 	idr_for_each(&idr, item_idr_free, &idr);
65 	idr_destroy(&idr);
66 }
67 
68 void idr_replace_test(void)
69 {
70 	DEFINE_IDR(idr);
71 
72 	idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL);
73 	idr_replace(&idr, &idr, 10);
74 
75 	idr_destroy(&idr);
76 }
77 
78 /*
79  * Unlike the radix tree, you can put a NULL pointer -- with care -- into
80  * the IDR.  Some interfaces, like idr_find() do not distinguish between
81  * "present, value is NULL" and "not present", but that's exactly what some
82  * users want.
83  */
84 void idr_null_test(void)
85 {
86 	int i;
87 	DEFINE_IDR(idr);
88 
89 	assert(idr_is_empty(&idr));
90 
91 	assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
92 	assert(!idr_is_empty(&idr));
93 	idr_remove(&idr, 0);
94 	assert(idr_is_empty(&idr));
95 
96 	assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
97 	assert(!idr_is_empty(&idr));
98 	idr_destroy(&idr);
99 	assert(idr_is_empty(&idr));
100 
101 	for (i = 0; i < 10; i++) {
102 		assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i);
103 	}
104 
105 	assert(idr_replace(&idr, DUMMY_PTR, 3) == NULL);
106 	assert(idr_replace(&idr, DUMMY_PTR, 4) == NULL);
107 	assert(idr_replace(&idr, NULL, 4) == DUMMY_PTR);
108 	assert(idr_replace(&idr, DUMMY_PTR, 11) == ERR_PTR(-ENOENT));
109 	idr_remove(&idr, 5);
110 	assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5);
111 	idr_remove(&idr, 5);
112 
113 	for (i = 0; i < 9; i++) {
114 		idr_remove(&idr, i);
115 		assert(!idr_is_empty(&idr));
116 	}
117 	idr_remove(&idr, 8);
118 	assert(!idr_is_empty(&idr));
119 	idr_remove(&idr, 9);
120 	assert(idr_is_empty(&idr));
121 
122 	assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
123 	assert(idr_replace(&idr, DUMMY_PTR, 3) == ERR_PTR(-ENOENT));
124 	assert(idr_replace(&idr, DUMMY_PTR, 0) == NULL);
125 	assert(idr_replace(&idr, NULL, 0) == DUMMY_PTR);
126 
127 	idr_destroy(&idr);
128 	assert(idr_is_empty(&idr));
129 
130 	for (i = 1; i < 10; i++) {
131 		assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i);
132 	}
133 
134 	idr_destroy(&idr);
135 	assert(idr_is_empty(&idr));
136 }
137 
138 void idr_nowait_test(void)
139 {
140 	unsigned int i;
141 	DEFINE_IDR(idr);
142 
143 	idr_preload(GFP_KERNEL);
144 
145 	for (i = 0; i < 3; i++) {
146 		struct item *item = item_create(i, 0);
147 		assert(idr_alloc(&idr, item, i, i + 1, GFP_NOWAIT) == i);
148 	}
149 
150 	idr_preload_end();
151 
152 	idr_for_each(&idr, item_idr_free, &idr);
153 	idr_destroy(&idr);
154 }
155 
156 void idr_get_next_test(void)
157 {
158 	unsigned long i;
159 	int nextid;
160 	DEFINE_IDR(idr);
161 
162 	int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
163 
164 	for(i = 0; indices[i]; i++) {
165 		struct item *item = item_create(indices[i], 0);
166 		assert(idr_alloc(&idr, item, indices[i], indices[i+1],
167 				 GFP_KERNEL) == indices[i]);
168 	}
169 
170 	for(i = 0, nextid = 0; indices[i]; i++) {
171 		idr_get_next(&idr, &nextid);
172 		assert(nextid == indices[i]);
173 		nextid++;
174 	}
175 
176 	idr_for_each(&idr, item_idr_free, &idr);
177 	idr_destroy(&idr);
178 }
179 
180 void idr_checks(void)
181 {
182 	unsigned long i;
183 	DEFINE_IDR(idr);
184 
185 	for (i = 0; i < 10000; i++) {
186 		struct item *item = item_create(i, 0);
187 		assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i);
188 	}
189 
190 	assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0);
191 
192 	for (i = 0; i < 5000; i++)
193 		item_idr_remove(&idr, i);
194 
195 	idr_remove(&idr, 3);
196 
197 	idr_for_each(&idr, item_idr_free, &idr);
198 	idr_destroy(&idr);
199 
200 	assert(idr_is_empty(&idr));
201 
202 	idr_remove(&idr, 3);
203 	idr_remove(&idr, 0);
204 
205 	for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
206 		struct item *item = item_create(i, 0);
207 		assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
208 	}
209 	assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC);
210 
211 	idr_for_each(&idr, item_idr_free, &idr);
212 	idr_destroy(&idr);
213 	idr_destroy(&idr);
214 
215 	assert(idr_is_empty(&idr));
216 
217 	for (i = 1; i < 10000; i++) {
218 		struct item *item = item_create(i, 0);
219 		assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i);
220 	}
221 
222 	idr_for_each(&idr, item_idr_free, &idr);
223 	idr_destroy(&idr);
224 
225 	idr_replace_test();
226 	idr_alloc_test();
227 	idr_null_test();
228 	idr_nowait_test();
229 	idr_get_next_test();
230 }
231 
232 /*
233  * Check that we get the correct error when we run out of memory doing
234  * allocations.  To ensure we run out of memory, just "forget" to preload.
235  * The first test is for not having a bitmap available, and the second test
236  * is for not being able to allocate a level of the radix tree.
237  */
238 void ida_check_nomem(void)
239 {
240 	DEFINE_IDA(ida);
241 	int id, err;
242 
243 	err = ida_get_new_above(&ida, 256, &id);
244 	assert(err == -EAGAIN);
245 	err = ida_get_new_above(&ida, 1UL << 30, &id);
246 	assert(err == -EAGAIN);
247 }
248 
249 /*
250  * Check what happens when we fill a leaf and then delete it.  This may
251  * discover mishandling of IDR_FREE.
252  */
253 void ida_check_leaf(void)
254 {
255 	DEFINE_IDA(ida);
256 	int id;
257 	unsigned long i;
258 
259 	for (i = 0; i < IDA_BITMAP_BITS; i++) {
260 		assert(ida_pre_get(&ida, GFP_KERNEL));
261 		assert(!ida_get_new(&ida, &id));
262 		assert(id == i);
263 	}
264 
265 	ida_destroy(&ida);
266 	assert(ida_is_empty(&ida));
267 
268 	assert(ida_pre_get(&ida, GFP_KERNEL));
269 	assert(!ida_get_new(&ida, &id));
270 	assert(id == 0);
271 	ida_destroy(&ida);
272 	assert(ida_is_empty(&ida));
273 }
274 
275 /*
276  * Check handling of conversions between exceptional entries and full bitmaps.
277  */
278 void ida_check_conv(void)
279 {
280 	DEFINE_IDA(ida);
281 	int id;
282 	unsigned long i;
283 
284 	for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
285 		assert(ida_pre_get(&ida, GFP_KERNEL));
286 		assert(!ida_get_new_above(&ida, i + 1, &id));
287 		assert(id == i + 1);
288 		assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id));
289 		assert(id == i + BITS_PER_LONG);
290 		ida_remove(&ida, i + 1);
291 		ida_remove(&ida, i + BITS_PER_LONG);
292 		assert(ida_is_empty(&ida));
293 	}
294 
295 	assert(ida_pre_get(&ida, GFP_KERNEL));
296 
297 	for (i = 0; i < IDA_BITMAP_BITS * 2; i++) {
298 		assert(ida_pre_get(&ida, GFP_KERNEL));
299 		assert(!ida_get_new(&ida, &id));
300 		assert(id == i);
301 	}
302 
303 	for (i = IDA_BITMAP_BITS * 2; i > 0; i--) {
304 		ida_remove(&ida, i - 1);
305 	}
306 	assert(ida_is_empty(&ida));
307 
308 	for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) {
309 		assert(ida_pre_get(&ida, GFP_KERNEL));
310 		assert(!ida_get_new(&ida, &id));
311 		assert(id == i);
312 	}
313 
314 	for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) {
315 		ida_remove(&ida, i - 1);
316 	}
317 	assert(ida_is_empty(&ida));
318 
319 	radix_tree_cpu_dead(1);
320 	for (i = 0; i < 1000000; i++) {
321 		int err = ida_get_new(&ida, &id);
322 		if (err == -EAGAIN) {
323 			assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2));
324 			assert(ida_pre_get(&ida, GFP_KERNEL));
325 			err = ida_get_new(&ida, &id);
326 		} else {
327 			assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2));
328 		}
329 		assert(!err);
330 		assert(id == i);
331 	}
332 	ida_destroy(&ida);
333 }
334 
335 /*
336  * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
337  * Allocating up to 2^31-1 should succeed, and then allocating the next one
338  * should fail.
339  */
340 void ida_check_max(void)
341 {
342 	DEFINE_IDA(ida);
343 	int id, err;
344 	unsigned long i, j;
345 
346 	for (j = 1; j < 65537; j *= 2) {
347 		unsigned long base = (1UL << 31) - j;
348 		for (i = 0; i < j; i++) {
349 			assert(ida_pre_get(&ida, GFP_KERNEL));
350 			assert(!ida_get_new_above(&ida, base, &id));
351 			assert(id == base + i);
352 		}
353 		assert(ida_pre_get(&ida, GFP_KERNEL));
354 		err = ida_get_new_above(&ida, base, &id);
355 		assert(err == -ENOSPC);
356 		ida_destroy(&ida);
357 		assert(ida_is_empty(&ida));
358 		rcu_barrier();
359 	}
360 }
361 
362 void ida_check_random(void)
363 {
364 	DEFINE_IDA(ida);
365 	DECLARE_BITMAP(bitmap, 2048);
366 	int id, err;
367 	unsigned int i;
368 	time_t s = time(NULL);
369 
370  repeat:
371 	memset(bitmap, 0, sizeof(bitmap));
372 	for (i = 0; i < 100000; i++) {
373 		int i = rand();
374 		int bit = i & 2047;
375 		if (test_bit(bit, bitmap)) {
376 			__clear_bit(bit, bitmap);
377 			ida_remove(&ida, bit);
378 		} else {
379 			__set_bit(bit, bitmap);
380 			do {
381 				ida_pre_get(&ida, GFP_KERNEL);
382 				err = ida_get_new_above(&ida, bit, &id);
383 			} while (err == -ENOMEM);
384 			assert(!err);
385 			assert(id == bit);
386 		}
387 	}
388 	ida_destroy(&ida);
389 	if (time(NULL) < s + 10)
390 		goto repeat;
391 }
392 
393 void ida_simple_get_remove_test(void)
394 {
395 	DEFINE_IDA(ida);
396 	unsigned long i;
397 
398 	for (i = 0; i < 10000; i++) {
399 		assert(ida_simple_get(&ida, 0, 20000, GFP_KERNEL) == i);
400 	}
401 	assert(ida_simple_get(&ida, 5, 30, GFP_KERNEL) < 0);
402 
403 	for (i = 0; i < 10000; i++) {
404 		ida_simple_remove(&ida, i);
405 	}
406 	assert(ida_is_empty(&ida));
407 
408 	ida_destroy(&ida);
409 }
410 
411 void ida_checks(void)
412 {
413 	DEFINE_IDA(ida);
414 	int id;
415 	unsigned long i;
416 
417 	radix_tree_cpu_dead(1);
418 	ida_check_nomem();
419 
420 	for (i = 0; i < 10000; i++) {
421 		assert(ida_pre_get(&ida, GFP_KERNEL));
422 		assert(!ida_get_new(&ida, &id));
423 		assert(id == i);
424 	}
425 
426 	ida_remove(&ida, 20);
427 	ida_remove(&ida, 21);
428 	for (i = 0; i < 3; i++) {
429 		assert(ida_pre_get(&ida, GFP_KERNEL));
430 		assert(!ida_get_new(&ida, &id));
431 		if (i == 2)
432 			assert(id == 10000);
433 	}
434 
435 	for (i = 0; i < 5000; i++)
436 		ida_remove(&ida, i);
437 
438 	assert(ida_pre_get(&ida, GFP_KERNEL));
439 	assert(!ida_get_new_above(&ida, 5000, &id));
440 	assert(id == 10001);
441 
442 	ida_destroy(&ida);
443 
444 	assert(ida_is_empty(&ida));
445 
446 	assert(ida_pre_get(&ida, GFP_KERNEL));
447 	assert(!ida_get_new_above(&ida, 1, &id));
448 	assert(id == 1);
449 
450 	ida_remove(&ida, id);
451 	assert(ida_is_empty(&ida));
452 	ida_destroy(&ida);
453 	assert(ida_is_empty(&ida));
454 
455 	assert(ida_pre_get(&ida, GFP_KERNEL));
456 	assert(!ida_get_new_above(&ida, 1, &id));
457 	ida_destroy(&ida);
458 	assert(ida_is_empty(&ida));
459 
460 	assert(ida_pre_get(&ida, GFP_KERNEL));
461 	assert(!ida_get_new_above(&ida, 1, &id));
462 	assert(id == 1);
463 	assert(ida_pre_get(&ida, GFP_KERNEL));
464 	assert(!ida_get_new_above(&ida, 1025, &id));
465 	assert(id == 1025);
466 	assert(ida_pre_get(&ida, GFP_KERNEL));
467 	assert(!ida_get_new_above(&ida, 10000, &id));
468 	assert(id == 10000);
469 	ida_remove(&ida, 1025);
470 	ida_destroy(&ida);
471 	assert(ida_is_empty(&ida));
472 
473 	ida_check_leaf();
474 	ida_check_max();
475 	ida_check_conv();
476 	ida_check_random();
477 	ida_simple_get_remove_test();
478 
479 	radix_tree_cpu_dead(1);
480 }
481 
482 static void *ida_random_fn(void *arg)
483 {
484 	rcu_register_thread();
485 	ida_check_random();
486 	rcu_unregister_thread();
487 	return NULL;
488 }
489 
490 void ida_thread_tests(void)
491 {
492 	pthread_t threads[10];
493 	int i;
494 
495 	for (i = 0; i < ARRAY_SIZE(threads); i++)
496 		if (pthread_create(&threads[i], NULL, ida_random_fn, NULL)) {
497 			perror("creating ida thread");
498 			exit(1);
499 		}
500 
501 	while (i--)
502 		pthread_join(threads[i], NULL);
503 }
504 
505 int __weak main(void)
506 {
507 	radix_tree_init();
508 	idr_checks();
509 	ida_checks();
510 	ida_thread_tests();
511 	radix_tree_cpu_dead(1);
512 	rcu_barrier();
513 	if (nr_allocated)
514 		printf("nr_allocated = %d\n", nr_allocated);
515 	return 0;
516 }
517