test_ida.c

  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
 12static unsigned int tests_run;
 13static unsigned int tests_passed;
 14
 15#ifdef __KERNEL__
 16static 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 */
 31static 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 */
 57static 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 */
 66static 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 */
 84static 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 */
107static 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 */
127static 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 */
156static 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 */
195static 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
261static DEFINE_IDA(ida);
262
263static 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
280static void ida_exit(void)
281{
282}
283
284module_init(ida_checks);
285module_exit(ida_exit);
286MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
287MODULE_DESCRIPTION("Test the IDA API");
288MODULE_LICENSE("GPL");