xref: /openbmc/linux/lib/test_ida.c (revision ffcaafdb)
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 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 static DEFINE_IDA(ida);
193 
ida_checks(void)194 static int ida_checks(void)
195 {
196 	IDA_BUG_ON(&ida, !ida_is_empty(&ida));
197 	ida_check_alloc(&ida);
198 	ida_check_destroy(&ida);
199 	ida_check_leaf(&ida, 0);
200 	ida_check_leaf(&ida, 1024);
201 	ida_check_leaf(&ida, 1024 * 64);
202 	ida_check_max(&ida);
203 	ida_check_conv(&ida);
204 	ida_check_bad_free(&ida);
205 
206 	printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
207 	return (tests_run != tests_passed) ? 0 : -EINVAL;
208 }
209 
ida_exit(void)210 static void ida_exit(void)
211 {
212 }
213 
214 module_init(ida_checks);
215 module_exit(ida_exit);
216 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
217 MODULE_LICENSE("GPL");
218