1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * test_xarray.c: Test the XArray API
4 * Copyright (c) 2017-2018 Microsoft Corporation
5 * Copyright (c) 2019-2020 Oracle
6 * Author: Matthew Wilcox <willy@infradead.org>
7 */
8
9 #include <linux/xarray.h>
10 #include <linux/module.h>
11
12 static unsigned int tests_run;
13 static unsigned int tests_passed;
14
15 #ifndef XA_DEBUG
16 # ifdef __KERNEL__
xa_dump(const struct xarray * xa)17 void xa_dump(const struct xarray *xa) { }
18 # endif
19 #undef XA_BUG_ON
20 #define XA_BUG_ON(xa, x) do { \
21 tests_run++; \
22 if (x) { \
23 printk("BUG at %s:%d\n", __func__, __LINE__); \
24 xa_dump(xa); \
25 dump_stack(); \
26 } else { \
27 tests_passed++; \
28 } \
29 } while (0)
30 #endif
31
xa_mk_index(unsigned long index)32 static void *xa_mk_index(unsigned long index)
33 {
34 return xa_mk_value(index & LONG_MAX);
35 }
36
xa_store_index(struct xarray * xa,unsigned long index,gfp_t gfp)37 static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)
38 {
39 return xa_store(xa, index, xa_mk_index(index), gfp);
40 }
41
xa_insert_index(struct xarray * xa,unsigned long index)42 static void xa_insert_index(struct xarray *xa, unsigned long index)
43 {
44 XA_BUG_ON(xa, xa_insert(xa, index, xa_mk_index(index),
45 GFP_KERNEL) != 0);
46 }
47
xa_alloc_index(struct xarray * xa,unsigned long index,gfp_t gfp)48 static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)
49 {
50 u32 id;
51
52 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(index), xa_limit_32b,
53 gfp) != 0);
54 XA_BUG_ON(xa, id != index);
55 }
56
xa_erase_index(struct xarray * xa,unsigned long index)57 static void xa_erase_index(struct xarray *xa, unsigned long index)
58 {
59 XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_index(index));
60 XA_BUG_ON(xa, xa_load(xa, index) != NULL);
61 }
62
63 /*
64 * If anyone needs this, please move it to xarray.c. We have no current
65 * users outside the test suite because all current multislot users want
66 * to use the advanced API.
67 */
xa_store_order(struct xarray * xa,unsigned long index,unsigned order,void * entry,gfp_t gfp)68 static void *xa_store_order(struct xarray *xa, unsigned long index,
69 unsigned order, void *entry, gfp_t gfp)
70 {
71 XA_STATE_ORDER(xas, xa, index, order);
72 void *curr;
73
74 do {
75 xas_lock(&xas);
76 curr = xas_store(&xas, entry);
77 xas_unlock(&xas);
78 } while (xas_nomem(&xas, gfp));
79
80 return curr;
81 }
82
check_xa_err(struct xarray * xa)83 static noinline void check_xa_err(struct xarray *xa)
84 {
85 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0);
86 XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0);
87 #ifndef __KERNEL__
88 /* The kernel does not fail GFP_NOWAIT allocations */
89 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
90 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
91 #endif
92 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0);
93 XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0);
94 XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0);
95 // kills the test-suite :-(
96 // XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL);
97 }
98
check_xas_retry(struct xarray * xa)99 static noinline void check_xas_retry(struct xarray *xa)
100 {
101 XA_STATE(xas, xa, 0);
102 void *entry;
103
104 xa_store_index(xa, 0, GFP_KERNEL);
105 xa_store_index(xa, 1, GFP_KERNEL);
106
107 rcu_read_lock();
108 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));
109 xa_erase_index(xa, 1);
110 XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));
111 XA_BUG_ON(xa, xas_retry(&xas, NULL));
112 XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));
113 xas_reset(&xas);
114 XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
115 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
116 XA_BUG_ON(xa, xas.xa_node != NULL);
117 rcu_read_unlock();
118
119 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
120
121 rcu_read_lock();
122 XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
123 xas.xa_node = XAS_RESTART;
124 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
125 rcu_read_unlock();
126
127 /* Make sure we can iterate through retry entries */
128 xas_lock(&xas);
129 xas_set(&xas, 0);
130 xas_store(&xas, XA_RETRY_ENTRY);
131 xas_set(&xas, 1);
132 xas_store(&xas, XA_RETRY_ENTRY);
133
134 xas_set(&xas, 0);
135 xas_for_each(&xas, entry, ULONG_MAX) {
136 xas_store(&xas, xa_mk_index(xas.xa_index));
137 }
138 xas_unlock(&xas);
139
140 xa_erase_index(xa, 0);
141 xa_erase_index(xa, 1);
142 }
143
check_xa_load(struct xarray * xa)144 static noinline void check_xa_load(struct xarray *xa)
145 {
146 unsigned long i, j;
147
148 for (i = 0; i < 1024; i++) {
149 for (j = 0; j < 1024; j++) {
150 void *entry = xa_load(xa, j);
151 if (j < i)
152 XA_BUG_ON(xa, xa_to_value(entry) != j);
153 else
154 XA_BUG_ON(xa, entry);
155 }
156 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
157 }
158
159 for (i = 0; i < 1024; i++) {
160 for (j = 0; j < 1024; j++) {
161 void *entry = xa_load(xa, j);
162 if (j >= i)
163 XA_BUG_ON(xa, xa_to_value(entry) != j);
164 else
165 XA_BUG_ON(xa, entry);
166 }
167 xa_erase_index(xa, i);
168 }
169 XA_BUG_ON(xa, !xa_empty(xa));
170 }
171
check_xa_mark_1(struct xarray * xa,unsigned long index)172 static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
173 {
174 unsigned int order;
175 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1;
176
177 /* NULL elements have no marks set */
178 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
179 xa_set_mark(xa, index, XA_MARK_0);
180 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
181
182 /* Storing a pointer will not make a mark appear */
183 XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL);
184 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
185 xa_set_mark(xa, index, XA_MARK_0);
186 XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
187
188 /* Setting one mark will not set another mark */
189 XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0));
190 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1));
191
192 /* Storing NULL clears marks, and they can't be set again */
193 xa_erase_index(xa, index);
194 XA_BUG_ON(xa, !xa_empty(xa));
195 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
196 xa_set_mark(xa, index, XA_MARK_0);
197 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
198
199 /*
200 * Storing a multi-index entry over entries with marks gives the
201 * entire entry the union of the marks
202 */
203 BUG_ON((index % 4) != 0);
204 for (order = 2; order < max_order; order++) {
205 unsigned long base = round_down(index, 1UL << order);
206 unsigned long next = base + (1UL << order);
207 unsigned long i;
208
209 XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));
210 xa_set_mark(xa, index + 1, XA_MARK_0);
211 XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));
212 xa_set_mark(xa, index + 2, XA_MARK_2);
213 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));
214 xa_store_order(xa, index, order, xa_mk_index(index),
215 GFP_KERNEL);
216 for (i = base; i < next; i++) {
217 XA_STATE(xas, xa, i);
218 unsigned int seen = 0;
219 void *entry;
220
221 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
222 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1));
223 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2));
224
225 /* We should see two elements in the array */
226 rcu_read_lock();
227 xas_for_each(&xas, entry, ULONG_MAX)
228 seen++;
229 rcu_read_unlock();
230 XA_BUG_ON(xa, seen != 2);
231
232 /* One of which is marked */
233 xas_set(&xas, 0);
234 seen = 0;
235 rcu_read_lock();
236 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
237 seen++;
238 rcu_read_unlock();
239 XA_BUG_ON(xa, seen != 1);
240 }
241 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0));
242 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1));
243 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2));
244 xa_erase_index(xa, index);
245 xa_erase_index(xa, next);
246 XA_BUG_ON(xa, !xa_empty(xa));
247 }
248 XA_BUG_ON(xa, !xa_empty(xa));
249 }
250
check_xa_mark_2(struct xarray * xa)251 static noinline void check_xa_mark_2(struct xarray *xa)
252 {
253 XA_STATE(xas, xa, 0);
254 unsigned long index;
255 unsigned int count = 0;
256 void *entry;
257
258 xa_store_index(xa, 0, GFP_KERNEL);
259 xa_set_mark(xa, 0, XA_MARK_0);
260 xas_lock(&xas);
261 xas_load(&xas);
262 xas_init_marks(&xas);
263 xas_unlock(&xas);
264 XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0);
265
266 for (index = 3500; index < 4500; index++) {
267 xa_store_index(xa, index, GFP_KERNEL);
268 xa_set_mark(xa, index, XA_MARK_0);
269 }
270
271 xas_reset(&xas);
272 rcu_read_lock();
273 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
274 count++;
275 rcu_read_unlock();
276 XA_BUG_ON(xa, count != 1000);
277
278 xas_lock(&xas);
279 xas_for_each(&xas, entry, ULONG_MAX) {
280 xas_init_marks(&xas);
281 XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));
282 XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));
283 }
284 xas_unlock(&xas);
285
286 xa_destroy(xa);
287 }
288
check_xa_mark(struct xarray * xa)289 static noinline void check_xa_mark(struct xarray *xa)
290 {
291 unsigned long index;
292
293 for (index = 0; index < 16384; index += 4)
294 check_xa_mark_1(xa, index);
295
296 check_xa_mark_2(xa);
297 }
298
check_xa_shrink(struct xarray * xa)299 static noinline void check_xa_shrink(struct xarray *xa)
300 {
301 XA_STATE(xas, xa, 1);
302 struct xa_node *node;
303 unsigned int order;
304 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1;
305
306 XA_BUG_ON(xa, !xa_empty(xa));
307 XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL);
308 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
309
310 /*
311 * Check that erasing the entry at 1 shrinks the tree and properly
312 * marks the node as being deleted.
313 */
314 xas_lock(&xas);
315 XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));
316 node = xas.xa_node;
317 XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0));
318 XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
319 XA_BUG_ON(xa, xa_load(xa, 1) != NULL);
320 XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);
321 XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY);
322 XA_BUG_ON(xa, xas_load(&xas) != NULL);
323 xas_unlock(&xas);
324 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
325 xa_erase_index(xa, 0);
326 XA_BUG_ON(xa, !xa_empty(xa));
327
328 for (order = 0; order < max_order; order++) {
329 unsigned long max = (1UL << order) - 1;
330 xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL);
331 XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0));
332 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
333 rcu_read_lock();
334 node = xa_head(xa);
335 rcu_read_unlock();
336 XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) !=
337 NULL);
338 rcu_read_lock();
339 XA_BUG_ON(xa, xa_head(xa) == node);
340 rcu_read_unlock();
341 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
342 xa_erase_index(xa, ULONG_MAX);
343 XA_BUG_ON(xa, xa->xa_head != node);
344 xa_erase_index(xa, 0);
345 }
346 }
347
check_insert(struct xarray * xa)348 static noinline void check_insert(struct xarray *xa)
349 {
350 unsigned long i;
351
352 for (i = 0; i < 1024; i++) {
353 xa_insert_index(xa, i);
354 XA_BUG_ON(xa, xa_load(xa, i - 1) != NULL);
355 XA_BUG_ON(xa, xa_load(xa, i + 1) != NULL);
356 xa_erase_index(xa, i);
357 }
358
359 for (i = 10; i < BITS_PER_LONG; i++) {
360 xa_insert_index(xa, 1UL << i);
361 XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 1) != NULL);
362 XA_BUG_ON(xa, xa_load(xa, (1UL << i) + 1) != NULL);
363 xa_erase_index(xa, 1UL << i);
364
365 xa_insert_index(xa, (1UL << i) - 1);
366 XA_BUG_ON(xa, xa_load(xa, (1UL << i) - 2) != NULL);
367 XA_BUG_ON(xa, xa_load(xa, 1UL << i) != NULL);
368 xa_erase_index(xa, (1UL << i) - 1);
369 }
370
371 xa_insert_index(xa, ~0UL);
372 XA_BUG_ON(xa, xa_load(xa, 0UL) != NULL);
373 XA_BUG_ON(xa, xa_load(xa, ~1UL) != NULL);
374 xa_erase_index(xa, ~0UL);
375
376 XA_BUG_ON(xa, !xa_empty(xa));
377 }
378
check_cmpxchg(struct xarray * xa)379 static noinline void check_cmpxchg(struct xarray *xa)
380 {
381 void *FIVE = xa_mk_value(5);
382 void *SIX = xa_mk_value(6);
383 void *LOTS = xa_mk_value(12345678);
384
385 XA_BUG_ON(xa, !xa_empty(xa));
386 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);
387 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EBUSY);
388 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);
389 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);
390 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);
391 XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL);
392 XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL);
393 xa_erase_index(xa, 12345678);
394 xa_erase_index(xa, 5);
395 XA_BUG_ON(xa, !xa_empty(xa));
396 }
397
check_reserve(struct xarray * xa)398 static noinline void check_reserve(struct xarray *xa)
399 {
400 void *entry;
401 unsigned long index;
402 int count;
403
404 /* An array with a reserved entry is not empty */
405 XA_BUG_ON(xa, !xa_empty(xa));
406 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
407 XA_BUG_ON(xa, xa_empty(xa));
408 XA_BUG_ON(xa, xa_load(xa, 12345678));
409 xa_release(xa, 12345678);
410 XA_BUG_ON(xa, !xa_empty(xa));
411
412 /* Releasing a used entry does nothing */
413 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
414 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
415 xa_release(xa, 12345678);
416 xa_erase_index(xa, 12345678);
417 XA_BUG_ON(xa, !xa_empty(xa));
418
419 /* cmpxchg sees a reserved entry as ZERO */
420 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
421 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, XA_ZERO_ENTRY,
422 xa_mk_value(12345678), GFP_NOWAIT) != NULL);
423 xa_release(xa, 12345678);
424 xa_erase_index(xa, 12345678);
425 XA_BUG_ON(xa, !xa_empty(xa));
426
427 /* xa_insert treats it as busy */
428 XA_BUG_ON(xa, xa_reserve(xa, 12345678, GFP_KERNEL) != 0);
429 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) !=
430 -EBUSY);
431 XA_BUG_ON(xa, xa_empty(xa));
432 XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL);
433 XA_BUG_ON(xa, !xa_empty(xa));
434
435 /* Can iterate through a reserved entry */
436 xa_store_index(xa, 5, GFP_KERNEL);
437 XA_BUG_ON(xa, xa_reserve(xa, 6, GFP_KERNEL) != 0);
438 xa_store_index(xa, 7, GFP_KERNEL);
439
440 count = 0;
441 xa_for_each(xa, index, entry) {
442 XA_BUG_ON(xa, index != 5 && index != 7);
443 count++;
444 }
445 XA_BUG_ON(xa, count != 2);
446
447 /* If we free a reserved entry, we should be able to allocate it */
448 if (xa->xa_flags & XA_FLAGS_ALLOC) {
449 u32 id;
450
451 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(8),
452 XA_LIMIT(5, 10), GFP_KERNEL) != 0);
453 XA_BUG_ON(xa, id != 8);
454
455 xa_release(xa, 6);
456 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_value(6),
457 XA_LIMIT(5, 10), GFP_KERNEL) != 0);
458 XA_BUG_ON(xa, id != 6);
459 }
460
461 xa_destroy(xa);
462 }
463
check_xas_erase(struct xarray * xa)464 static noinline void check_xas_erase(struct xarray *xa)
465 {
466 XA_STATE(xas, xa, 0);
467 void *entry;
468 unsigned long i, j;
469
470 for (i = 0; i < 200; i++) {
471 for (j = i; j < 2 * i + 17; j++) {
472 xas_set(&xas, j);
473 do {
474 xas_lock(&xas);
475 xas_store(&xas, xa_mk_index(j));
476 xas_unlock(&xas);
477 } while (xas_nomem(&xas, GFP_KERNEL));
478 }
479
480 xas_set(&xas, ULONG_MAX);
481 do {
482 xas_lock(&xas);
483 xas_store(&xas, xa_mk_value(0));
484 xas_unlock(&xas);
485 } while (xas_nomem(&xas, GFP_KERNEL));
486
487 xas_lock(&xas);
488 xas_store(&xas, NULL);
489
490 xas_set(&xas, 0);
491 j = i;
492 xas_for_each(&xas, entry, ULONG_MAX) {
493 XA_BUG_ON(xa, entry != xa_mk_index(j));
494 xas_store(&xas, NULL);
495 j++;
496 }
497 xas_unlock(&xas);
498 XA_BUG_ON(xa, !xa_empty(xa));
499 }
500 }
501
502 #ifdef CONFIG_XARRAY_MULTI
check_multi_store_1(struct xarray * xa,unsigned long index,unsigned int order)503 static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,
504 unsigned int order)
505 {
506 XA_STATE(xas, xa, index);
507 unsigned long min = index & ~((1UL << order) - 1);
508 unsigned long max = min + (1UL << order);
509
510 xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
511 XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index));
512 XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index));
513 XA_BUG_ON(xa, xa_load(xa, max) != NULL);
514 XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
515
516 xas_lock(&xas);
517 XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index));
518 xas_unlock(&xas);
519 XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min));
520 XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min));
521 XA_BUG_ON(xa, xa_load(xa, max) != NULL);
522 XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
523
524 xa_erase_index(xa, min);
525 XA_BUG_ON(xa, !xa_empty(xa));
526 }
527
check_multi_store_2(struct xarray * xa,unsigned long index,unsigned int order)528 static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,
529 unsigned int order)
530 {
531 XA_STATE(xas, xa, index);
532 xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);
533
534 xas_lock(&xas);
535 XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
536 XA_BUG_ON(xa, xas.xa_index != index);
537 XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
538 xas_unlock(&xas);
539 XA_BUG_ON(xa, !xa_empty(xa));
540 }
541
check_multi_store_3(struct xarray * xa,unsigned long index,unsigned int order)542 static noinline void check_multi_store_3(struct xarray *xa, unsigned long index,
543 unsigned int order)
544 {
545 XA_STATE(xas, xa, 0);
546 void *entry;
547 int n = 0;
548
549 xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL);
550
551 xas_lock(&xas);
552 xas_for_each(&xas, entry, ULONG_MAX) {
553 XA_BUG_ON(xa, entry != xa_mk_index(index));
554 n++;
555 }
556 XA_BUG_ON(xa, n != 1);
557 xas_set(&xas, index + 1);
558 xas_for_each(&xas, entry, ULONG_MAX) {
559 XA_BUG_ON(xa, entry != xa_mk_index(index));
560 n++;
561 }
562 XA_BUG_ON(xa, n != 2);
563 xas_unlock(&xas);
564
565 xa_destroy(xa);
566 }
567 #endif
568
check_multi_store(struct xarray * xa)569 static noinline void check_multi_store(struct xarray *xa)
570 {
571 #ifdef CONFIG_XARRAY_MULTI
572 unsigned long i, j, k;
573 unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;
574
575 /* Loading from any position returns the same value */
576 xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);
577 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
578 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
579 XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
580 rcu_read_lock();
581 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);
582 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
583 rcu_read_unlock();
584
585 /* Storing adjacent to the value does not alter the value */
586 xa_store(xa, 3, xa, GFP_KERNEL);
587 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
588 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
589 XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
590 rcu_read_lock();
591 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);
592 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
593 rcu_read_unlock();
594
595 /* Overwriting multiple indexes works */
596 xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);
597 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));
598 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));
599 XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));
600 XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));
601 XA_BUG_ON(xa, xa_load(xa, 4) != NULL);
602 rcu_read_lock();
603 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);
604 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);
605 rcu_read_unlock();
606
607 /* We can erase multiple values with a single store */
608 xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);
609 XA_BUG_ON(xa, !xa_empty(xa));
610
611 /* Even when the first slot is empty but the others aren't */
612 xa_store_index(xa, 1, GFP_KERNEL);
613 xa_store_index(xa, 2, GFP_KERNEL);
614 xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);
615 XA_BUG_ON(xa, !xa_empty(xa));
616
617 for (i = 0; i < max_order; i++) {
618 for (j = 0; j < max_order; j++) {
619 xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL);
620 xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL);
621
622 for (k = 0; k < max_order; k++) {
623 void *entry = xa_load(xa, (1UL << k) - 1);
624 if ((i < k) && (j < k))
625 XA_BUG_ON(xa, entry != NULL);
626 else
627 XA_BUG_ON(xa, entry != xa_mk_index(j));
628 }
629
630 xa_erase(xa, 0);
631 XA_BUG_ON(xa, !xa_empty(xa));
632 }
633 }
634
635 for (i = 0; i < 20; i++) {
636 check_multi_store_1(xa, 200, i);
637 check_multi_store_1(xa, 0, i);
638 check_multi_store_1(xa, (1UL << i) + 1, i);
639 }
640 check_multi_store_2(xa, 4095, 9);
641
642 for (i = 1; i < 20; i++) {
643 check_multi_store_3(xa, 0, i);
644 check_multi_store_3(xa, 1UL << i, i);
645 }
646 #endif
647 }
648
check_xa_alloc_1(struct xarray * xa,unsigned int base)649 static noinline void check_xa_alloc_1(struct xarray *xa, unsigned int base)
650 {
651 int i;
652 u32 id;
653
654 XA_BUG_ON(xa, !xa_empty(xa));
655 /* An empty array should assign %base to the first alloc */
656 xa_alloc_index(xa, base, GFP_KERNEL);
657
658 /* Erasing it should make the array empty again */
659 xa_erase_index(xa, base);
660 XA_BUG_ON(xa, !xa_empty(xa));
661
662 /* And it should assign %base again */
663 xa_alloc_index(xa, base, GFP_KERNEL);
664
665 /* Allocating and then erasing a lot should not lose base */
666 for (i = base + 1; i < 2 * XA_CHUNK_SIZE; i++)
667 xa_alloc_index(xa, i, GFP_KERNEL);
668 for (i = base; i < 2 * XA_CHUNK_SIZE; i++)
669 xa_erase_index(xa, i);
670 xa_alloc_index(xa, base, GFP_KERNEL);
671
672 /* Destroying the array should do the same as erasing */
673 xa_destroy(xa);
674
675 /* And it should assign %base again */
676 xa_alloc_index(xa, base, GFP_KERNEL);
677
678 /* The next assigned ID should be base+1 */
679 xa_alloc_index(xa, base + 1, GFP_KERNEL);
680 xa_erase_index(xa, base + 1);
681
682 /* Storing a value should mark it used */
683 xa_store_index(xa, base + 1, GFP_KERNEL);
684 xa_alloc_index(xa, base + 2, GFP_KERNEL);
685
686 /* If we then erase base, it should be free */
687 xa_erase_index(xa, base);
688 xa_alloc_index(xa, base, GFP_KERNEL);
689
690 xa_erase_index(xa, base + 1);
691 xa_erase_index(xa, base + 2);
692
693 for (i = 1; i < 5000; i++) {
694 xa_alloc_index(xa, base + i, GFP_KERNEL);
695 }
696
697 xa_destroy(xa);
698
699 /* Check that we fail properly at the limit of allocation */
700 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX - 1),
701 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
702 GFP_KERNEL) != 0);
703 XA_BUG_ON(xa, id != 0xfffffffeU);
704 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(UINT_MAX),
705 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
706 GFP_KERNEL) != 0);
707 XA_BUG_ON(xa, id != 0xffffffffU);
708 id = 3;
709 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(0),
710 XA_LIMIT(UINT_MAX - 1, UINT_MAX),
711 GFP_KERNEL) != -EBUSY);
712 XA_BUG_ON(xa, id != 3);
713 xa_destroy(xa);
714
715 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
716 GFP_KERNEL) != -EBUSY);
717 XA_BUG_ON(xa, xa_store_index(xa, 3, GFP_KERNEL) != 0);
718 XA_BUG_ON(xa, xa_alloc(xa, &id, xa_mk_index(10), XA_LIMIT(10, 5),
719 GFP_KERNEL) != -EBUSY);
720 xa_erase_index(xa, 3);
721 XA_BUG_ON(xa, !xa_empty(xa));
722 }
723
check_xa_alloc_2(struct xarray * xa,unsigned int base)724 static noinline void check_xa_alloc_2(struct xarray *xa, unsigned int base)
725 {
726 unsigned int i, id;
727 unsigned long index;
728 void *entry;
729
730 /* Allocate and free a NULL and check xa_empty() behaves */
731 XA_BUG_ON(xa, !xa_empty(xa));
732 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
733 XA_BUG_ON(xa, id != base);
734 XA_BUG_ON(xa, xa_empty(xa));
735 XA_BUG_ON(xa, xa_erase(xa, id) != NULL);
736 XA_BUG_ON(xa, !xa_empty(xa));
737
738 /* Ditto, but check destroy instead of erase */
739 XA_BUG_ON(xa, !xa_empty(xa));
740 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
741 XA_BUG_ON(xa, id != base);
742 XA_BUG_ON(xa, xa_empty(xa));
743 xa_destroy(xa);
744 XA_BUG_ON(xa, !xa_empty(xa));
745
746 for (i = base; i < base + 10; i++) {
747 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b,
748 GFP_KERNEL) != 0);
749 XA_BUG_ON(xa, id != i);
750 }
751
752 XA_BUG_ON(xa, xa_store(xa, 3, xa_mk_index(3), GFP_KERNEL) != NULL);
753 XA_BUG_ON(xa, xa_store(xa, 4, xa_mk_index(4), GFP_KERNEL) != NULL);
754 XA_BUG_ON(xa, xa_store(xa, 4, NULL, GFP_KERNEL) != xa_mk_index(4));
755 XA_BUG_ON(xa, xa_erase(xa, 5) != NULL);
756 XA_BUG_ON(xa, xa_alloc(xa, &id, NULL, xa_limit_32b, GFP_KERNEL) != 0);
757 XA_BUG_ON(xa, id != 5);
758
759 xa_for_each(xa, index, entry) {
760 xa_erase_index(xa, index);
761 }
762
763 for (i = base; i < base + 9; i++) {
764 XA_BUG_ON(xa, xa_erase(xa, i) != NULL);
765 XA_BUG_ON(xa, xa_empty(xa));
766 }
767 XA_BUG_ON(xa, xa_erase(xa, 8) != NULL);
768 XA_BUG_ON(xa, xa_empty(xa));
769 XA_BUG_ON(xa, xa_erase(xa, base + 9) != NULL);
770 XA_BUG_ON(xa, !xa_empty(xa));
771
772 xa_destroy(xa);
773 }
774
check_xa_alloc_3(struct xarray * xa,unsigned int base)775 static noinline void check_xa_alloc_3(struct xarray *xa, unsigned int base)
776 {
777 struct xa_limit limit = XA_LIMIT(1, 0x3fff);
778 u32 next = 0;
779 unsigned int i, id;
780 unsigned long index;
781 void *entry;
782
783 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(1), limit,
784 &next, GFP_KERNEL) != 0);
785 XA_BUG_ON(xa, id != 1);
786
787 next = 0x3ffd;
788 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(0x3ffd), limit,
789 &next, GFP_KERNEL) != 0);
790 XA_BUG_ON(xa, id != 0x3ffd);
791 xa_erase_index(xa, 0x3ffd);
792 xa_erase_index(xa, 1);
793 XA_BUG_ON(xa, !xa_empty(xa));
794
795 for (i = 0x3ffe; i < 0x4003; i++) {
796 if (i < 0x4000)
797 entry = xa_mk_index(i);
798 else
799 entry = xa_mk_index(i - 0x3fff);
800 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, entry, limit,
801 &next, GFP_KERNEL) != (id == 1));
802 XA_BUG_ON(xa, xa_mk_index(id) != entry);
803 }
804
805 /* Check wrap-around is handled correctly */
806 if (base != 0)
807 xa_erase_index(xa, base);
808 xa_erase_index(xa, base + 1);
809 next = UINT_MAX;
810 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(UINT_MAX),
811 xa_limit_32b, &next, GFP_KERNEL) != 0);
812 XA_BUG_ON(xa, id != UINT_MAX);
813 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base),
814 xa_limit_32b, &next, GFP_KERNEL) != 1);
815 XA_BUG_ON(xa, id != base);
816 XA_BUG_ON(xa, xa_alloc_cyclic(xa, &id, xa_mk_index(base + 1),
817 xa_limit_32b, &next, GFP_KERNEL) != 0);
818 XA_BUG_ON(xa, id != base + 1);
819
820 xa_for_each(xa, index, entry)
821 xa_erase_index(xa, index);
822
823 XA_BUG_ON(xa, !xa_empty(xa));
824 }
825
826 static DEFINE_XARRAY_ALLOC(xa0);
827 static DEFINE_XARRAY_ALLOC1(xa1);
828
check_xa_alloc(void)829 static noinline void check_xa_alloc(void)
830 {
831 check_xa_alloc_1(&xa0, 0);
832 check_xa_alloc_1(&xa1, 1);
833 check_xa_alloc_2(&xa0, 0);
834 check_xa_alloc_2(&xa1, 1);
835 check_xa_alloc_3(&xa0, 0);
836 check_xa_alloc_3(&xa1, 1);
837 }
838
__check_store_iter(struct xarray * xa,unsigned long start,unsigned int order,unsigned int present)839 static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
840 unsigned int order, unsigned int present)
841 {
842 XA_STATE_ORDER(xas, xa, start, order);
843 void *entry;
844 unsigned int count = 0;
845
846 retry:
847 xas_lock(&xas);
848 xas_for_each_conflict(&xas, entry) {
849 XA_BUG_ON(xa, !xa_is_value(entry));
850 XA_BUG_ON(xa, entry < xa_mk_index(start));
851 XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1));
852 count++;
853 }
854 xas_store(&xas, xa_mk_index(start));
855 xas_unlock(&xas);
856 if (xas_nomem(&xas, GFP_KERNEL)) {
857 count = 0;
858 goto retry;
859 }
860 XA_BUG_ON(xa, xas_error(&xas));
861 XA_BUG_ON(xa, count != present);
862 XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start));
863 XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
864 xa_mk_index(start));
865 xa_erase_index(xa, start);
866 }
867
check_store_iter(struct xarray * xa)868 static noinline void check_store_iter(struct xarray *xa)
869 {
870 unsigned int i, j;
871 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
872
873 for (i = 0; i < max_order; i++) {
874 unsigned int min = 1 << i;
875 unsigned int max = (2 << i) - 1;
876 __check_store_iter(xa, 0, i, 0);
877 XA_BUG_ON(xa, !xa_empty(xa));
878 __check_store_iter(xa, min, i, 0);
879 XA_BUG_ON(xa, !xa_empty(xa));
880
881 xa_store_index(xa, min, GFP_KERNEL);
882 __check_store_iter(xa, min, i, 1);
883 XA_BUG_ON(xa, !xa_empty(xa));
884 xa_store_index(xa, max, GFP_KERNEL);
885 __check_store_iter(xa, min, i, 1);
886 XA_BUG_ON(xa, !xa_empty(xa));
887
888 for (j = 0; j < min; j++)
889 xa_store_index(xa, j, GFP_KERNEL);
890 __check_store_iter(xa, 0, i, min);
891 XA_BUG_ON(xa, !xa_empty(xa));
892 for (j = 0; j < min; j++)
893 xa_store_index(xa, min + j, GFP_KERNEL);
894 __check_store_iter(xa, min, i, min);
895 XA_BUG_ON(xa, !xa_empty(xa));
896 }
897 #ifdef CONFIG_XARRAY_MULTI
898 xa_store_index(xa, 63, GFP_KERNEL);
899 xa_store_index(xa, 65, GFP_KERNEL);
900 __check_store_iter(xa, 64, 2, 1);
901 xa_erase_index(xa, 63);
902 #endif
903 XA_BUG_ON(xa, !xa_empty(xa));
904 }
905
check_multi_find_1(struct xarray * xa,unsigned order)906 static noinline void check_multi_find_1(struct xarray *xa, unsigned order)
907 {
908 #ifdef CONFIG_XARRAY_MULTI
909 unsigned long multi = 3 << order;
910 unsigned long next = 4 << order;
911 unsigned long index;
912
913 xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL);
914 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL);
915 XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL);
916
917 index = 0;
918 XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
919 xa_mk_value(multi));
920 XA_BUG_ON(xa, index != multi);
921 index = multi + 1;
922 XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
923 xa_mk_value(multi));
924 XA_BUG_ON(xa, (index < multi) || (index >= next));
925 XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
926 xa_mk_value(next));
927 XA_BUG_ON(xa, index != next);
928 XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL);
929 XA_BUG_ON(xa, index != next);
930
931 xa_erase_index(xa, multi);
932 xa_erase_index(xa, next);
933 xa_erase_index(xa, next + 1);
934 XA_BUG_ON(xa, !xa_empty(xa));
935 #endif
936 }
937
check_multi_find_2(struct xarray * xa)938 static noinline void check_multi_find_2(struct xarray *xa)
939 {
940 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
941 unsigned int i, j;
942 void *entry;
943
944 for (i = 0; i < max_order; i++) {
945 unsigned long index = 1UL << i;
946 for (j = 0; j < index; j++) {
947 XA_STATE(xas, xa, j + index);
948 xa_store_index(xa, index - 1, GFP_KERNEL);
949 xa_store_order(xa, index, i, xa_mk_index(index),
950 GFP_KERNEL);
951 rcu_read_lock();
952 xas_for_each(&xas, entry, ULONG_MAX) {
953 xa_erase_index(xa, index);
954 }
955 rcu_read_unlock();
956 xa_erase_index(xa, index - 1);
957 XA_BUG_ON(xa, !xa_empty(xa));
958 }
959 }
960 }
961
check_find_1(struct xarray * xa)962 static noinline void check_find_1(struct xarray *xa)
963 {
964 unsigned long i, j, k;
965
966 XA_BUG_ON(xa, !xa_empty(xa));
967
968 /*
969 * Check xa_find with all pairs between 0 and 99 inclusive,
970 * starting at every index between 0 and 99
971 */
972 for (i = 0; i < 100; i++) {
973 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
974 xa_set_mark(xa, i, XA_MARK_0);
975 for (j = 0; j < i; j++) {
976 XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
977 NULL);
978 xa_set_mark(xa, j, XA_MARK_0);
979 for (k = 0; k < 100; k++) {
980 unsigned long index = k;
981 void *entry = xa_find(xa, &index, ULONG_MAX,
982 XA_PRESENT);
983 if (k <= j)
984 XA_BUG_ON(xa, index != j);
985 else if (k <= i)
986 XA_BUG_ON(xa, index != i);
987 else
988 XA_BUG_ON(xa, entry != NULL);
989
990 index = k;
991 entry = xa_find(xa, &index, ULONG_MAX,
992 XA_MARK_0);
993 if (k <= j)
994 XA_BUG_ON(xa, index != j);
995 else if (k <= i)
996 XA_BUG_ON(xa, index != i);
997 else
998 XA_BUG_ON(xa, entry != NULL);
999 }
1000 xa_erase_index(xa, j);
1001 XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
1002 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
1003 }
1004 xa_erase_index(xa, i);
1005 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
1006 }
1007 XA_BUG_ON(xa, !xa_empty(xa));
1008 }
1009
check_find_2(struct xarray * xa)1010 static noinline void check_find_2(struct xarray *xa)
1011 {
1012 void *entry;
1013 unsigned long i, j, index;
1014
1015 xa_for_each(xa, index, entry) {
1016 XA_BUG_ON(xa, true);
1017 }
1018
1019 for (i = 0; i < 1024; i++) {
1020 xa_store_index(xa, index, GFP_KERNEL);
1021 j = 0;
1022 xa_for_each(xa, index, entry) {
1023 XA_BUG_ON(xa, xa_mk_index(index) != entry);
1024 XA_BUG_ON(xa, index != j++);
1025 }
1026 }
1027
1028 xa_destroy(xa);
1029 }
1030
check_find_3(struct xarray * xa)1031 static noinline void check_find_3(struct xarray *xa)
1032 {
1033 XA_STATE(xas, xa, 0);
1034 unsigned long i, j, k;
1035 void *entry;
1036
1037 for (i = 0; i < 100; i++) {
1038 for (j = 0; j < 100; j++) {
1039 rcu_read_lock();
1040 for (k = 0; k < 100; k++) {
1041 xas_set(&xas, j);
1042 xas_for_each_marked(&xas, entry, k, XA_MARK_0)
1043 ;
1044 if (j > k)
1045 XA_BUG_ON(xa,
1046 xas.xa_node != XAS_RESTART);
1047 }
1048 rcu_read_unlock();
1049 }
1050 xa_store_index(xa, i, GFP_KERNEL);
1051 xa_set_mark(xa, i, XA_MARK_0);
1052 }
1053 xa_destroy(xa);
1054 }
1055
check_find_4(struct xarray * xa)1056 static noinline void check_find_4(struct xarray *xa)
1057 {
1058 unsigned long index = 0;
1059 void *entry;
1060
1061 xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1062
1063 entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1064 XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX));
1065
1066 entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT);
1067 XA_BUG_ON(xa, entry);
1068
1069 xa_erase_index(xa, ULONG_MAX);
1070 }
1071
check_find(struct xarray * xa)1072 static noinline void check_find(struct xarray *xa)
1073 {
1074 unsigned i;
1075
1076 check_find_1(xa);
1077 check_find_2(xa);
1078 check_find_3(xa);
1079 check_find_4(xa);
1080
1081 for (i = 2; i < 10; i++)
1082 check_multi_find_1(xa, i);
1083 check_multi_find_2(xa);
1084 }
1085
1086 /* See find_swap_entry() in mm/shmem.c */
xa_find_entry(struct xarray * xa,void * item)1087 static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
1088 {
1089 XA_STATE(xas, xa, 0);
1090 unsigned int checked = 0;
1091 void *entry;
1092
1093 rcu_read_lock();
1094 xas_for_each(&xas, entry, ULONG_MAX) {
1095 if (xas_retry(&xas, entry))
1096 continue;
1097 if (entry == item)
1098 break;
1099 checked++;
1100 if ((checked % 4) != 0)
1101 continue;
1102 xas_pause(&xas);
1103 }
1104 rcu_read_unlock();
1105
1106 return entry ? xas.xa_index : -1;
1107 }
1108
check_find_entry(struct xarray * xa)1109 static noinline void check_find_entry(struct xarray *xa)
1110 {
1111 #ifdef CONFIG_XARRAY_MULTI
1112 unsigned int order;
1113 unsigned long offset, index;
1114
1115 for (order = 0; order < 20; order++) {
1116 for (offset = 0; offset < (1UL << (order + 3));
1117 offset += (1UL << order)) {
1118 for (index = 0; index < (1UL << (order + 5));
1119 index += (1UL << order)) {
1120 xa_store_order(xa, index, order,
1121 xa_mk_index(index), GFP_KERNEL);
1122 XA_BUG_ON(xa, xa_load(xa, index) !=
1123 xa_mk_index(index));
1124 XA_BUG_ON(xa, xa_find_entry(xa,
1125 xa_mk_index(index)) != index);
1126 }
1127 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1128 xa_destroy(xa);
1129 }
1130 }
1131 #endif
1132
1133 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1134 xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
1135 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
1136 XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1);
1137 xa_erase_index(xa, ULONG_MAX);
1138 XA_BUG_ON(xa, !xa_empty(xa));
1139 }
1140
check_move_tiny(struct xarray * xa)1141 static noinline void check_move_tiny(struct xarray *xa)
1142 {
1143 XA_STATE(xas, xa, 0);
1144
1145 XA_BUG_ON(xa, !xa_empty(xa));
1146 rcu_read_lock();
1147 XA_BUG_ON(xa, xas_next(&xas) != NULL);
1148 XA_BUG_ON(xa, xas_next(&xas) != NULL);
1149 rcu_read_unlock();
1150 xa_store_index(xa, 0, GFP_KERNEL);
1151 rcu_read_lock();
1152 xas_set(&xas, 0);
1153 XA_BUG_ON(xa, xas_next(&xas) != xa_mk_index(0));
1154 XA_BUG_ON(xa, xas_next(&xas) != NULL);
1155 xas_set(&xas, 0);
1156 XA_BUG_ON(xa, xas_prev(&xas) != xa_mk_index(0));
1157 XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1158 rcu_read_unlock();
1159 xa_erase_index(xa, 0);
1160 XA_BUG_ON(xa, !xa_empty(xa));
1161 }
1162
check_move_small(struct xarray * xa,unsigned long idx)1163 static noinline void check_move_small(struct xarray *xa, unsigned long idx)
1164 {
1165 XA_STATE(xas, xa, 0);
1166 unsigned long i;
1167
1168 xa_store_index(xa, 0, GFP_KERNEL);
1169 xa_store_index(xa, idx, GFP_KERNEL);
1170
1171 rcu_read_lock();
1172 for (i = 0; i < idx * 4; i++) {
1173 void *entry = xas_next(&xas);
1174 if (i <= idx)
1175 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1176 XA_BUG_ON(xa, xas.xa_index != i);
1177 if (i == 0 || i == idx)
1178 XA_BUG_ON(xa, entry != xa_mk_index(i));
1179 else
1180 XA_BUG_ON(xa, entry != NULL);
1181 }
1182 xas_next(&xas);
1183 XA_BUG_ON(xa, xas.xa_index != i);
1184
1185 do {
1186 void *entry = xas_prev(&xas);
1187 i--;
1188 if (i <= idx)
1189 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
1190 XA_BUG_ON(xa, xas.xa_index != i);
1191 if (i == 0 || i == idx)
1192 XA_BUG_ON(xa, entry != xa_mk_index(i));
1193 else
1194 XA_BUG_ON(xa, entry != NULL);
1195 } while (i > 0);
1196
1197 xas_set(&xas, ULONG_MAX);
1198 XA_BUG_ON(xa, xas_next(&xas) != NULL);
1199 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1200 XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
1201 XA_BUG_ON(xa, xas.xa_index != 0);
1202 XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1203 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1204 rcu_read_unlock();
1205
1206 xa_erase_index(xa, 0);
1207 xa_erase_index(xa, idx);
1208 XA_BUG_ON(xa, !xa_empty(xa));
1209 }
1210
check_move(struct xarray * xa)1211 static noinline void check_move(struct xarray *xa)
1212 {
1213 XA_STATE(xas, xa, (1 << 16) - 1);
1214 unsigned long i;
1215
1216 for (i = 0; i < (1 << 16); i++)
1217 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
1218
1219 rcu_read_lock();
1220 do {
1221 void *entry = xas_prev(&xas);
1222 i--;
1223 XA_BUG_ON(xa, entry != xa_mk_index(i));
1224 XA_BUG_ON(xa, i != xas.xa_index);
1225 } while (i != 0);
1226
1227 XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1228 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1229
1230 do {
1231 void *entry = xas_next(&xas);
1232 XA_BUG_ON(xa, entry != xa_mk_index(i));
1233 XA_BUG_ON(xa, i != xas.xa_index);
1234 i++;
1235 } while (i < (1 << 16));
1236 rcu_read_unlock();
1237
1238 for (i = (1 << 8); i < (1 << 15); i++)
1239 xa_erase_index(xa, i);
1240
1241 i = xas.xa_index;
1242
1243 rcu_read_lock();
1244 do {
1245 void *entry = xas_prev(&xas);
1246 i--;
1247 if ((i < (1 << 8)) || (i >= (1 << 15)))
1248 XA_BUG_ON(xa, entry != xa_mk_index(i));
1249 else
1250 XA_BUG_ON(xa, entry != NULL);
1251 XA_BUG_ON(xa, i != xas.xa_index);
1252 } while (i != 0);
1253
1254 XA_BUG_ON(xa, xas_prev(&xas) != NULL);
1255 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
1256
1257 do {
1258 void *entry = xas_next(&xas);
1259 if ((i < (1 << 8)) || (i >= (1 << 15)))
1260 XA_BUG_ON(xa, entry != xa_mk_index(i));
1261 else
1262 XA_BUG_ON(xa, entry != NULL);
1263 XA_BUG_ON(xa, i != xas.xa_index);
1264 i++;
1265 } while (i < (1 << 16));
1266 rcu_read_unlock();
1267
1268 xa_destroy(xa);
1269
1270 check_move_tiny(xa);
1271
1272 for (i = 0; i < 16; i++)
1273 check_move_small(xa, 1UL << i);
1274
1275 for (i = 2; i < 16; i++)
1276 check_move_small(xa, (1UL << i) - 1);
1277 }
1278
xa_store_many_order(struct xarray * xa,unsigned long index,unsigned order)1279 static noinline void xa_store_many_order(struct xarray *xa,
1280 unsigned long index, unsigned order)
1281 {
1282 XA_STATE_ORDER(xas, xa, index, order);
1283 unsigned int i = 0;
1284
1285 do {
1286 xas_lock(&xas);
1287 XA_BUG_ON(xa, xas_find_conflict(&xas));
1288 xas_create_range(&xas);
1289 if (xas_error(&xas))
1290 goto unlock;
1291 for (i = 0; i < (1U << order); i++) {
1292 XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i)));
1293 xas_next(&xas);
1294 }
1295 unlock:
1296 xas_unlock(&xas);
1297 } while (xas_nomem(&xas, GFP_KERNEL));
1298
1299 XA_BUG_ON(xa, xas_error(&xas));
1300 }
1301
check_create_range_1(struct xarray * xa,unsigned long index,unsigned order)1302 static noinline void check_create_range_1(struct xarray *xa,
1303 unsigned long index, unsigned order)
1304 {
1305 unsigned long i;
1306
1307 xa_store_many_order(xa, index, order);
1308 for (i = index; i < index + (1UL << order); i++)
1309 xa_erase_index(xa, i);
1310 XA_BUG_ON(xa, !xa_empty(xa));
1311 }
1312
check_create_range_2(struct xarray * xa,unsigned order)1313 static noinline void check_create_range_2(struct xarray *xa, unsigned order)
1314 {
1315 unsigned long i;
1316 unsigned long nr = 1UL << order;
1317
1318 for (i = 0; i < nr * nr; i += nr)
1319 xa_store_many_order(xa, i, order);
1320 for (i = 0; i < nr * nr; i++)
1321 xa_erase_index(xa, i);
1322 XA_BUG_ON(xa, !xa_empty(xa));
1323 }
1324
check_create_range_3(void)1325 static noinline void check_create_range_3(void)
1326 {
1327 XA_STATE(xas, NULL, 0);
1328 xas_set_err(&xas, -EEXIST);
1329 xas_create_range(&xas);
1330 XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1331 }
1332
check_create_range_4(struct xarray * xa,unsigned long index,unsigned order)1333 static noinline void check_create_range_4(struct xarray *xa,
1334 unsigned long index, unsigned order)
1335 {
1336 XA_STATE_ORDER(xas, xa, index, order);
1337 unsigned long base = xas.xa_index;
1338 unsigned long i = 0;
1339
1340 xa_store_index(xa, index, GFP_KERNEL);
1341 do {
1342 xas_lock(&xas);
1343 xas_create_range(&xas);
1344 if (xas_error(&xas))
1345 goto unlock;
1346 for (i = 0; i < (1UL << order); i++) {
1347 void *old = xas_store(&xas, xa_mk_index(base + i));
1348 if (xas.xa_index == index)
1349 XA_BUG_ON(xa, old != xa_mk_index(base + i));
1350 else
1351 XA_BUG_ON(xa, old != NULL);
1352 xas_next(&xas);
1353 }
1354 unlock:
1355 xas_unlock(&xas);
1356 } while (xas_nomem(&xas, GFP_KERNEL));
1357
1358 XA_BUG_ON(xa, xas_error(&xas));
1359
1360 for (i = base; i < base + (1UL << order); i++)
1361 xa_erase_index(xa, i);
1362 XA_BUG_ON(xa, !xa_empty(xa));
1363 }
1364
check_create_range(struct xarray * xa)1365 static noinline void check_create_range(struct xarray *xa)
1366 {
1367 unsigned int order;
1368 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
1369
1370 for (order = 0; order < max_order; order++) {
1371 check_create_range_1(xa, 0, order);
1372 check_create_range_1(xa, 1U << order, order);
1373 check_create_range_1(xa, 2U << order, order);
1374 check_create_range_1(xa, 3U << order, order);
1375 check_create_range_1(xa, 1U << 24, order);
1376 if (order < 10)
1377 check_create_range_2(xa, order);
1378
1379 check_create_range_4(xa, 0, order);
1380 check_create_range_4(xa, 1U << order, order);
1381 check_create_range_4(xa, 2U << order, order);
1382 check_create_range_4(xa, 3U << order, order);
1383 check_create_range_4(xa, 1U << 24, order);
1384
1385 check_create_range_4(xa, 1, order);
1386 check_create_range_4(xa, (1U << order) + 1, order);
1387 check_create_range_4(xa, (2U << order) + 1, order);
1388 check_create_range_4(xa, (2U << order) - 1, order);
1389 check_create_range_4(xa, (3U << order) + 1, order);
1390 check_create_range_4(xa, (3U << order) - 1, order);
1391 check_create_range_4(xa, (1U << 24) + 1, order);
1392 }
1393
1394 check_create_range_3();
1395 }
1396
__check_store_range(struct xarray * xa,unsigned long first,unsigned long last)1397 static noinline void __check_store_range(struct xarray *xa, unsigned long first,
1398 unsigned long last)
1399 {
1400 #ifdef CONFIG_XARRAY_MULTI
1401 xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL);
1402
1403 XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first));
1404 XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first));
1405 XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
1406 XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
1407
1408 xa_store_range(xa, first, last, NULL, GFP_KERNEL);
1409 #endif
1410
1411 XA_BUG_ON(xa, !xa_empty(xa));
1412 }
1413
check_store_range(struct xarray * xa)1414 static noinline void check_store_range(struct xarray *xa)
1415 {
1416 unsigned long i, j;
1417
1418 for (i = 0; i < 128; i++) {
1419 for (j = i; j < 128; j++) {
1420 __check_store_range(xa, i, j);
1421 __check_store_range(xa, 128 + i, 128 + j);
1422 __check_store_range(xa, 4095 + i, 4095 + j);
1423 __check_store_range(xa, 4096 + i, 4096 + j);
1424 __check_store_range(xa, 123456 + i, 123456 + j);
1425 __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
1426 }
1427 }
1428 }
1429
check_align_1(struct xarray * xa,char * name)1430 static void check_align_1(struct xarray *xa, char *name)
1431 {
1432 int i;
1433 unsigned int id;
1434 unsigned long index;
1435 void *entry;
1436
1437 for (i = 0; i < 8; i++) {
1438 XA_BUG_ON(xa, xa_alloc(xa, &id, name + i, xa_limit_32b,
1439 GFP_KERNEL) != 0);
1440 XA_BUG_ON(xa, id != i);
1441 }
1442 xa_for_each(xa, index, entry)
1443 XA_BUG_ON(xa, xa_is_err(entry));
1444 xa_destroy(xa);
1445 }
1446
1447 /*
1448 * We should always be able to store without allocating memory after
1449 * reserving a slot.
1450 */
check_align_2(struct xarray * xa,char * name)1451 static void check_align_2(struct xarray *xa, char *name)
1452 {
1453 int i;
1454
1455 XA_BUG_ON(xa, !xa_empty(xa));
1456
1457 for (i = 0; i < 8; i++) {
1458 XA_BUG_ON(xa, xa_store(xa, 0, name + i, GFP_KERNEL) != NULL);
1459 xa_erase(xa, 0);
1460 }
1461
1462 for (i = 0; i < 8; i++) {
1463 XA_BUG_ON(xa, xa_reserve(xa, 0, GFP_KERNEL) != 0);
1464 XA_BUG_ON(xa, xa_store(xa, 0, name + i, 0) != NULL);
1465 xa_erase(xa, 0);
1466 }
1467
1468 XA_BUG_ON(xa, !xa_empty(xa));
1469 }
1470
check_align(struct xarray * xa)1471 static noinline void check_align(struct xarray *xa)
1472 {
1473 char name[] = "Motorola 68000";
1474
1475 check_align_1(xa, name);
1476 check_align_1(xa, name + 1);
1477 check_align_1(xa, name + 2);
1478 check_align_1(xa, name + 3);
1479 check_align_2(xa, name);
1480 }
1481
1482 static LIST_HEAD(shadow_nodes);
1483
test_update_node(struct xa_node * node)1484 static void test_update_node(struct xa_node *node)
1485 {
1486 if (node->count && node->count == node->nr_values) {
1487 if (list_empty(&node->private_list))
1488 list_add(&shadow_nodes, &node->private_list);
1489 } else {
1490 if (!list_empty(&node->private_list))
1491 list_del_init(&node->private_list);
1492 }
1493 }
1494
shadow_remove(struct xarray * xa)1495 static noinline void shadow_remove(struct xarray *xa)
1496 {
1497 struct xa_node *node;
1498
1499 xa_lock(xa);
1500 while ((node = list_first_entry_or_null(&shadow_nodes,
1501 struct xa_node, private_list))) {
1502 XA_STATE(xas, node->array, 0);
1503 XA_BUG_ON(xa, node->array != xa);
1504 list_del_init(&node->private_list);
1505 xas.xa_node = xa_parent_locked(node->array, node);
1506 xas.xa_offset = node->offset;
1507 xas.xa_shift = node->shift + XA_CHUNK_SHIFT;
1508 xas_set_update(&xas, test_update_node);
1509 xas_store(&xas, NULL);
1510 }
1511 xa_unlock(xa);
1512 }
1513
check_workingset(struct xarray * xa,unsigned long index)1514 static noinline void check_workingset(struct xarray *xa, unsigned long index)
1515 {
1516 XA_STATE(xas, xa, index);
1517 xas_set_update(&xas, test_update_node);
1518
1519 do {
1520 xas_lock(&xas);
1521 xas_store(&xas, xa_mk_value(0));
1522 xas_next(&xas);
1523 xas_store(&xas, xa_mk_value(1));
1524 xas_unlock(&xas);
1525 } while (xas_nomem(&xas, GFP_KERNEL));
1526
1527 XA_BUG_ON(xa, list_empty(&shadow_nodes));
1528
1529 xas_lock(&xas);
1530 xas_next(&xas);
1531 xas_store(&xas, &xas);
1532 XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1533
1534 xas_store(&xas, xa_mk_value(2));
1535 xas_unlock(&xas);
1536 XA_BUG_ON(xa, list_empty(&shadow_nodes));
1537
1538 shadow_remove(xa);
1539 XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1540 XA_BUG_ON(xa, !xa_empty(xa));
1541 }
1542
1543 /*
1544 * Check that the pointer / value / sibling entries are accounted the
1545 * way we expect them to be.
1546 */
check_account(struct xarray * xa)1547 static noinline void check_account(struct xarray *xa)
1548 {
1549 #ifdef CONFIG_XARRAY_MULTI
1550 unsigned int order;
1551
1552 for (order = 1; order < 12; order++) {
1553 XA_STATE(xas, xa, 1 << order);
1554
1555 xa_store_order(xa, 0, order, xa, GFP_KERNEL);
1556 rcu_read_lock();
1557 xas_load(&xas);
1558 XA_BUG_ON(xa, xas.xa_node->count == 0);
1559 XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1560 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1561 rcu_read_unlock();
1562
1563 xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order),
1564 GFP_KERNEL);
1565 XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1566
1567 xa_erase(xa, 1 << order);
1568 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1569
1570 xa_erase(xa, 0);
1571 XA_BUG_ON(xa, !xa_empty(xa));
1572 }
1573 #endif
1574 }
1575
check_destroy(struct xarray * xa)1576 static noinline void check_destroy(struct xarray *xa)
1577 {
1578 unsigned long index;
1579
1580 XA_BUG_ON(xa, !xa_empty(xa));
1581
1582 /* Destroying an empty array is a no-op */
1583 xa_destroy(xa);
1584 XA_BUG_ON(xa, !xa_empty(xa));
1585
1586 /* Destroying an array with a single entry */
1587 for (index = 0; index < 1000; index++) {
1588 xa_store_index(xa, index, GFP_KERNEL);
1589 XA_BUG_ON(xa, xa_empty(xa));
1590 xa_destroy(xa);
1591 XA_BUG_ON(xa, !xa_empty(xa));
1592 }
1593
1594 /* Destroying an array with a single entry at ULONG_MAX */
1595 xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
1596 XA_BUG_ON(xa, xa_empty(xa));
1597 xa_destroy(xa);
1598 XA_BUG_ON(xa, !xa_empty(xa));
1599
1600 #ifdef CONFIG_XARRAY_MULTI
1601 /* Destroying an array with a multi-index entry */
1602 xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
1603 XA_BUG_ON(xa, xa_empty(xa));
1604 xa_destroy(xa);
1605 XA_BUG_ON(xa, !xa_empty(xa));
1606 #endif
1607 }
1608
1609 static DEFINE_XARRAY(array);
1610
xarray_checks(void)1611 static int xarray_checks(void)
1612 {
1613 check_xa_err(&array);
1614 check_xas_retry(&array);
1615 check_xa_load(&array);
1616 check_xa_mark(&array);
1617 check_xa_shrink(&array);
1618 check_xas_erase(&array);
1619 check_insert(&array);
1620 check_cmpxchg(&array);
1621 check_reserve(&array);
1622 check_reserve(&xa0);
1623 check_multi_store(&array);
1624 check_xa_alloc();
1625 check_find(&array);
1626 check_find_entry(&array);
1627 check_account(&array);
1628 check_destroy(&array);
1629 check_move(&array);
1630 check_create_range(&array);
1631 check_store_range(&array);
1632 check_store_iter(&array);
1633 check_align(&xa0);
1634
1635 check_workingset(&array, 0);
1636 check_workingset(&array, 64);
1637 check_workingset(&array, 4096);
1638
1639 printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
1640 return (tests_run == tests_passed) ? 0 : -EINVAL;
1641 }
1642
xarray_exit(void)1643 static void xarray_exit(void)
1644 {
1645 }
1646
1647 module_init(xarray_checks);
1648 module_exit(xarray_exit);
1649 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
1650 MODULE_LICENSE("GPL");
1651