]> git.ipfire.org Git - thirdparty/kernel/stable.git/blame - lib/test_xarray.c
projects / thirdparty / kernel / stable.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge branch 'drm-next-4.21' of git://people.freedesktop.org/~agd5f/linux into drm...
[thirdparty/kernel/stable.git] / lib / test_xarray.c
CommitLineData
ad3d6c72
MW		 1// SPDX-License-Identifier: GPL-2.0+
2/*
3 * test_xarray.c: Test the XArray API
4 * Copyright (c) 2017-2018 Microsoft Corporation
5 * Author: Matthew Wilcox <willy@infradead.org>
6 */
7
8#include <linux/xarray.h>
9#include <linux/module.h>
10
11static unsigned int tests_run;
12static unsigned int tests_passed;
13
14#ifndef XA_DEBUG
15# ifdef __KERNEL__
16void xa_dump(const struct xarray *xa) { }
17# endif
18#undef XA_BUG_ON
19#define XA_BUG_ON(xa, x) do { \
20 tests_run++; \
21 if (x) { \
22 printk("BUG at %s:%d\n", __func__, __LINE__); \
23 xa_dump(xa); \
24 dump_stack(); \
25 } else { \
26 tests_passed++; \
27 } \
28} while (0)
29#endif
30
31static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp)
32{
58d6ea30 33 return xa_store(xa, index, xa_mk_value(index & LONG_MAX), gfp);
ad3d6c72
MW		 34}
35
371c752d
MW		 36static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp)
37{
38 u32 id = 0;
39
40 XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_value(index & LONG_MAX),
41 gfp) != 0);
42 XA_BUG_ON(xa, id != index);
43}
44
ad3d6c72
MW		 45static void xa_erase_index(struct xarray *xa, unsigned long index)
46{
58d6ea30
MW		 47 XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_value(index & LONG_MAX));
48 XA_BUG_ON(xa, xa_load(xa, index) != NULL);
49}
50
51/*
52 * If anyone needs this, please move it to xarray.c. We have no current
53 * users outside the test suite because all current multislot users want
54 * to use the advanced API.
55 */
56static void *xa_store_order(struct xarray *xa, unsigned long index,
57 unsigned order, void *entry, gfp_t gfp)
58{
59 XA_STATE_ORDER(xas, xa, index, order);
60 void *curr;
61
62 do {
63 xas_lock(&xas);
64 curr = xas_store(&xas, entry);
65 xas_unlock(&xas);
66 } while (xas_nomem(&xas, gfp));
67
68 return curr;
69}
70
71static noinline void check_xa_err(struct xarray *xa)
72{
73 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0);
74 XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0);
75#ifndef __KERNEL__
76 /* The kernel does not fail GFP_NOWAIT allocations */
77 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
78 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM);
79#endif
80 XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0);
81 XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0);
82 XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0);
83// kills the test-suite :-(
84// XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL);
ad3d6c72
MW		 85}
86
b803b428
MW		 87static noinline void check_xas_retry(struct xarray *xa)
88{
89 XA_STATE(xas, xa, 0);
90 void *entry;
91
92 xa_store_index(xa, 0, GFP_KERNEL);
93 xa_store_index(xa, 1, GFP_KERNEL);
94
95 rcu_read_lock();
96 XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0));
97 xa_erase_index(xa, 1);
98 XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas)));
99 XA_BUG_ON(xa, xas_retry(&xas, NULL));
100 XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0)));
101 xas_reset(&xas);
102 XA_BUG_ON(xa, xas.xa_node != XAS_RESTART);
103 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
104 XA_BUG_ON(xa, xas.xa_node != NULL);
105
106 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
107 XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas)));
108 xas.xa_node = XAS_RESTART;
109 XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0));
110 rcu_read_unlock();
111
112 /* Make sure we can iterate through retry entries */
113 xas_lock(&xas);
114 xas_set(&xas, 0);
115 xas_store(&xas, XA_RETRY_ENTRY);
116 xas_set(&xas, 1);
117 xas_store(&xas, XA_RETRY_ENTRY);
118
119 xas_set(&xas, 0);
120 xas_for_each(&xas, entry, ULONG_MAX) {
121 xas_store(&xas, xa_mk_value(xas.xa_index));
122 }
123 xas_unlock(&xas);
124
125 xa_erase_index(xa, 0);
126 xa_erase_index(xa, 1);
127}
128
ad3d6c72
MW		 129static noinline void check_xa_load(struct xarray *xa)
130{
131 unsigned long i, j;
132
133 for (i = 0; i < 1024; i++) {
134 for (j = 0; j < 1024; j++) {
135 void *entry = xa_load(xa, j);
136 if (j < i)
137 XA_BUG_ON(xa, xa_to_value(entry) != j);
138 else
139 XA_BUG_ON(xa, entry);
140 }
141 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
142 }
143
144 for (i = 0; i < 1024; i++) {
145 for (j = 0; j < 1024; j++) {
146 void *entry = xa_load(xa, j);
147 if (j >= i)
148 XA_BUG_ON(xa, xa_to_value(entry) != j);
149 else
150 XA_BUG_ON(xa, entry);
151 }
152 xa_erase_index(xa, i);
153 }
154 XA_BUG_ON(xa, !xa_empty(xa));
155}
156
9b89a035
MW		 157static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index)
158{
58d6ea30
MW		 159 unsigned int order;
160 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1;
161
9b89a035
MW		 162 /* NULL elements have no marks set */
163 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
164 xa_set_mark(xa, index, XA_MARK_0);
165 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
166
167 /* Storing a pointer will not make a mark appear */
168 XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL);
169 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
170 xa_set_mark(xa, index, XA_MARK_0);
171 XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0));
172
173 /* Setting one mark will not set another mark */
174 XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0));
175 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1));
176
177 /* Storing NULL clears marks, and they can't be set again */
178 xa_erase_index(xa, index);
179 XA_BUG_ON(xa, !xa_empty(xa));
180 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
181 xa_set_mark(xa, index, XA_MARK_0);
182 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0));
58d6ea30
MW		 183
184 /*
185 * Storing a multi-index entry over entries with marks gives the
186 * entire entry the union of the marks
187 */
188 BUG_ON((index % 4) != 0);
189 for (order = 2; order < max_order; order++) {
190 unsigned long base = round_down(index, 1UL << order);
191 unsigned long next = base + (1UL << order);
192 unsigned long i;
193
194 XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL));
195 xa_set_mark(xa, index + 1, XA_MARK_0);
196 XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL));
197 xa_set_mark(xa, index + 2, XA_MARK_1);
198 XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL));
199 xa_store_order(xa, index, order, xa_mk_value(index),
200 GFP_KERNEL);
201 for (i = base; i < next; i++) {
93eb07f7
MW		 202 XA_STATE(xas, xa, i);
203 unsigned int seen = 0;
204 void *entry;
205
58d6ea30
MW		 206 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
207 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_1));
208 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_2));
93eb07f7
MW		 209
210 /* We should see two elements in the array */
fffc9a26 211 rcu_read_lock();
93eb07f7
MW		 212 xas_for_each(&xas, entry, ULONG_MAX)
213 seen++;
fffc9a26 214 rcu_read_unlock();
93eb07f7
MW		 215 XA_BUG_ON(xa, seen != 2);
216
217 /* One of which is marked */
218 xas_set(&xas, 0);
219 seen = 0;
fffc9a26 220 rcu_read_lock();
93eb07f7
MW		 221 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
222 seen++;
fffc9a26 223 rcu_read_unlock();
93eb07f7 224 XA_BUG_ON(xa, seen != 1);
58d6ea30
MW		 225 }
226 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0));
227 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1));
228 XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2));
229 xa_erase_index(xa, index);
230 xa_erase_index(xa, next);
231 XA_BUG_ON(xa, !xa_empty(xa));
232 }
233 XA_BUG_ON(xa, !xa_empty(xa));
9b89a035
MW		 234}
235
adb9d9c4
MW		 236static noinline void check_xa_mark_2(struct xarray *xa)
237{
238 XA_STATE(xas, xa, 0);
239 unsigned long index;
240 unsigned int count = 0;
241 void *entry;
242
243 xa_store_index(xa, 0, GFP_KERNEL);
244 xa_set_mark(xa, 0, XA_MARK_0);
245 xas_lock(&xas);
246 xas_load(&xas);
247 xas_init_marks(&xas);
248 xas_unlock(&xas);
249 XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0);
250
251 for (index = 3500; index < 4500; index++) {
252 xa_store_index(xa, index, GFP_KERNEL);
253 xa_set_mark(xa, index, XA_MARK_0);
254 }
255
256 xas_reset(&xas);
257 rcu_read_lock();
258 xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0)
259 count++;
260 rcu_read_unlock();
261 XA_BUG_ON(xa, count != 1000);
262
263 xas_lock(&xas);
264 xas_for_each(&xas, entry, ULONG_MAX) {
265 xas_init_marks(&xas);
266 XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0));
267 XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0));
268 }
269 xas_unlock(&xas);
270
271 xa_destroy(xa);
272}
273
9b89a035
MW		 274static noinline void check_xa_mark(struct xarray *xa)
275{
276 unsigned long index;
277
278 for (index = 0; index < 16384; index += 4)
279 check_xa_mark_1(xa, index);
adb9d9c4
MW		 280
281 check_xa_mark_2(xa);
9b89a035
MW		 282}
283
58d6ea30
MW		 284static noinline void check_xa_shrink(struct xarray *xa)
285{
286 XA_STATE(xas, xa, 1);
287 struct xa_node *node;
93eb07f7
MW		 288 unsigned int order;
289 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1;
58d6ea30
MW		 290
291 XA_BUG_ON(xa, !xa_empty(xa));
292 XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL);
293 XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL);
294
295 /*
296 * Check that erasing the entry at 1 shrinks the tree and properly
297 * marks the node as being deleted.
298 */
299 xas_lock(&xas);
300 XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1));
301 node = xas.xa_node;
302 XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0));
303 XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
304 XA_BUG_ON(xa, xa_load(xa, 1) != NULL);
305 XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS);
306 XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY);
307 XA_BUG_ON(xa, xas_load(&xas) != NULL);
308 xas_unlock(&xas);
309 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
310 xa_erase_index(xa, 0);
311 XA_BUG_ON(xa, !xa_empty(xa));
93eb07f7
MW		 312
313 for (order = 0; order < max_order; order++) {
314 unsigned long max = (1UL << order) - 1;
315 xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL);
316 XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0));
317 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
318 rcu_read_lock();
319 node = xa_head(xa);
320 rcu_read_unlock();
321 XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) !=
322 NULL);
323 rcu_read_lock();
324 XA_BUG_ON(xa, xa_head(xa) == node);
325 rcu_read_unlock();
326 XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL);
327 xa_erase_index(xa, ULONG_MAX);
328 XA_BUG_ON(xa, xa->xa_head != node);
329 xa_erase_index(xa, 0);
330 }
58d6ea30
MW		 331}
332
41aec91f
MW		 333static noinline void check_cmpxchg(struct xarray *xa)
334{
335 void *FIVE = xa_mk_value(5);
336 void *SIX = xa_mk_value(6);
337 void *LOTS = xa_mk_value(12345678);
338
339 XA_BUG_ON(xa, !xa_empty(xa));
340 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL);
341 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EEXIST);
342 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS);
343 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS);
344 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE);
345 XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL);
346 XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL);
347 xa_erase_index(xa, 12345678);
348 xa_erase_index(xa, 5);
349 XA_BUG_ON(xa, !xa_empty(xa));
350}
351
9f14d4f1
MW		 352static noinline void check_reserve(struct xarray *xa)
353{
354 void *entry;
355 unsigned long index = 0;
356
357 /* An array with a reserved entry is not empty */
358 XA_BUG_ON(xa, !xa_empty(xa));
359 xa_reserve(xa, 12345678, GFP_KERNEL);
360 XA_BUG_ON(xa, xa_empty(xa));
361 XA_BUG_ON(xa, xa_load(xa, 12345678));
362 xa_release(xa, 12345678);
363 XA_BUG_ON(xa, !xa_empty(xa));
364
365 /* Releasing a used entry does nothing */
366 xa_reserve(xa, 12345678, GFP_KERNEL);
367 XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL);
368 xa_release(xa, 12345678);
369 xa_erase_index(xa, 12345678);
370 XA_BUG_ON(xa, !xa_empty(xa));
371
372 /* cmpxchg sees a reserved entry as NULL */
373 xa_reserve(xa, 12345678, GFP_KERNEL);
374 XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, NULL, xa_mk_value(12345678),
375 GFP_NOWAIT) != NULL);
376 xa_release(xa, 12345678);
377 xa_erase_index(xa, 12345678);
378 XA_BUG_ON(xa, !xa_empty(xa));
379
4c0608f4
MW		 380 /* And so does xa_insert */
381 xa_reserve(xa, 12345678, GFP_KERNEL);
382 XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) != 0);
383 xa_erase_index(xa, 12345678);
384 XA_BUG_ON(xa, !xa_empty(xa));
385
9f14d4f1
MW		 386 /* Can iterate through a reserved entry */
387 xa_store_index(xa, 5, GFP_KERNEL);
388 xa_reserve(xa, 6, GFP_KERNEL);
389 xa_store_index(xa, 7, GFP_KERNEL);
390
391 xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) {
392 XA_BUG_ON(xa, index != 5 && index != 7);
393 }
394 xa_destroy(xa);
395}
396
b803b428
MW		 397static noinline void check_xas_erase(struct xarray *xa)
398{
399 XA_STATE(xas, xa, 0);
400 void *entry;
401 unsigned long i, j;
402
403 for (i = 0; i < 200; i++) {
404 for (j = i; j < 2 * i + 17; j++) {
405 xas_set(&xas, j);
406 do {
407 xas_lock(&xas);
408 xas_store(&xas, xa_mk_value(j));
409 xas_unlock(&xas);
410 } while (xas_nomem(&xas, GFP_KERNEL));
411 }
412
413 xas_set(&xas, ULONG_MAX);
414 do {
415 xas_lock(&xas);
416 xas_store(&xas, xa_mk_value(0));
417 xas_unlock(&xas);
418 } while (xas_nomem(&xas, GFP_KERNEL));
419
420 xas_lock(&xas);
421 xas_store(&xas, NULL);
422
423 xas_set(&xas, 0);
424 j = i;
425 xas_for_each(&xas, entry, ULONG_MAX) {
426 XA_BUG_ON(xa, entry != xa_mk_value(j));
427 xas_store(&xas, NULL);
428 j++;
429 }
430 xas_unlock(&xas);
431 XA_BUG_ON(xa, !xa_empty(xa));
432 }
433}
434
4f06d630
MW		 435#ifdef CONFIG_XARRAY_MULTI
436static noinline void check_multi_store_1(struct xarray *xa, unsigned long index,
437 unsigned int order)
438{
439 XA_STATE(xas, xa, index);
440 unsigned long min = index & ~((1UL << order) - 1);
441 unsigned long max = min + (1UL << order);
442
443 xa_store_order(xa, index, order, xa_mk_value(index), GFP_KERNEL);
444 XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(index));
445 XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(index));
446 XA_BUG_ON(xa, xa_load(xa, max) != NULL);
447 XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
448
fffc9a26 449 xas_lock(&xas);
4f06d630 450 XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(min)) != xa_mk_value(index));
fffc9a26 451 xas_unlock(&xas);
4f06d630
MW		 452 XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(min));
453 XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(min));
454 XA_BUG_ON(xa, xa_load(xa, max) != NULL);
455 XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL);
456
457 xa_erase_index(xa, min);
458 XA_BUG_ON(xa, !xa_empty(xa));
459}
460
461static noinline void check_multi_store_2(struct xarray *xa, unsigned long index,
462 unsigned int order)
463{
464 XA_STATE(xas, xa, index);
465 xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL);
466
fffc9a26 467 xas_lock(&xas);
4f06d630
MW		 468 XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0));
469 XA_BUG_ON(xa, xas.xa_index != index);
470 XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1));
fffc9a26 471 xas_unlock(&xas);
4f06d630
MW		 472 XA_BUG_ON(xa, !xa_empty(xa));
473}
474#endif
475
58d6ea30
MW		 476static noinline void check_multi_store(struct xarray *xa)
477{
478#ifdef CONFIG_XARRAY_MULTI
479 unsigned long i, j, k;
480 unsigned int max_order = (sizeof(long) == 4) ? 30 : 60;
481
482 /* Loading from any position returns the same value */
483 xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL);
484 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
485 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
486 XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
487 rcu_read_lock();
488 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2);
489 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
490 rcu_read_unlock();
491
492 /* Storing adjacent to the value does not alter the value */
493 xa_store(xa, 3, xa, GFP_KERNEL);
494 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0));
495 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0));
496 XA_BUG_ON(xa, xa_load(xa, 2) != NULL);
497 rcu_read_lock();
498 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3);
499 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2);
500 rcu_read_unlock();
501
502 /* Overwriting multiple indexes works */
503 xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL);
504 XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1));
505 XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1));
506 XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1));
507 XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1));
508 XA_BUG_ON(xa, xa_load(xa, 4) != NULL);
509 rcu_read_lock();
510 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4);
511 XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4);
512 rcu_read_unlock();
513
514 /* We can erase multiple values with a single store */
5404a7f1 515 xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL);
58d6ea30
MW		 516 XA_BUG_ON(xa, !xa_empty(xa));
517
518 /* Even when the first slot is empty but the others aren't */
519 xa_store_index(xa, 1, GFP_KERNEL);
520 xa_store_index(xa, 2, GFP_KERNEL);
521 xa_store_order(xa, 0, 2, NULL, GFP_KERNEL);
522 XA_BUG_ON(xa, !xa_empty(xa));
523
524 for (i = 0; i < max_order; i++) {
525 for (j = 0; j < max_order; j++) {
526 xa_store_order(xa, 0, i, xa_mk_value(i), GFP_KERNEL);
527 xa_store_order(xa, 0, j, xa_mk_value(j), GFP_KERNEL);
528
529 for (k = 0; k < max_order; k++) {
530 void *entry = xa_load(xa, (1UL << k) - 1);
531 if ((i < k) && (j < k))
532 XA_BUG_ON(xa, entry != NULL);
533 else
534 XA_BUG_ON(xa, entry != xa_mk_value(j));
535 }
536
537 xa_erase(xa, 0);
538 XA_BUG_ON(xa, !xa_empty(xa));
539 }
540 }
4f06d630
MW		 541
542 for (i = 0; i < 20; i++) {
543 check_multi_store_1(xa, 200, i);
544 check_multi_store_1(xa, 0, i);
545 check_multi_store_1(xa, (1UL << i) + 1, i);
546 }
547 check_multi_store_2(xa, 4095, 9);
58d6ea30
MW		 548#endif
549}
550
371c752d
MW		 551static DEFINE_XARRAY_ALLOC(xa0);
552
553static noinline void check_xa_alloc(void)
554{
555 int i;
556 u32 id;
557
558 /* An empty array should assign 0 to the first alloc */
559 xa_alloc_index(&xa0, 0, GFP_KERNEL);
560
561 /* Erasing it should make the array empty again */
562 xa_erase_index(&xa0, 0);
563 XA_BUG_ON(&xa0, !xa_empty(&xa0));
564
565 /* And it should assign 0 again */
566 xa_alloc_index(&xa0, 0, GFP_KERNEL);
567
568 /* The next assigned ID should be 1 */
569 xa_alloc_index(&xa0, 1, GFP_KERNEL);
570 xa_erase_index(&xa0, 1);
571
572 /* Storing a value should mark it used */
573 xa_store_index(&xa0, 1, GFP_KERNEL);
574 xa_alloc_index(&xa0, 2, GFP_KERNEL);
575
576 /* If we then erase 0, it should be free */
577 xa_erase_index(&xa0, 0);
578 xa_alloc_index(&xa0, 0, GFP_KERNEL);
579
580 xa_erase_index(&xa0, 1);
581 xa_erase_index(&xa0, 2);
582
583 for (i = 1; i < 5000; i++) {
584 xa_alloc_index(&xa0, i, GFP_KERNEL);
585 }
586
587 xa_destroy(&xa0);
588
589 id = 0xfffffffeU;
590 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0),
591 GFP_KERNEL) != 0);
592 XA_BUG_ON(&xa0, id != 0xfffffffeU);
593 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0),
594 GFP_KERNEL) != 0);
595 XA_BUG_ON(&xa0, id != 0xffffffffU);
596 XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0),
597 GFP_KERNEL) != -ENOSPC);
598 XA_BUG_ON(&xa0, id != 0xffffffffU);
599 xa_destroy(&xa0);
600}
601
4e99d4e9
MW		 602static noinline void __check_store_iter(struct xarray *xa, unsigned long start,
603 unsigned int order, unsigned int present)
604{
605 XA_STATE_ORDER(xas, xa, start, order);
606 void *entry;
607 unsigned int count = 0;
608
609retry:
610 xas_lock(&xas);
611 xas_for_each_conflict(&xas, entry) {
612 XA_BUG_ON(xa, !xa_is_value(entry));
613 XA_BUG_ON(xa, entry < xa_mk_value(start));
614 XA_BUG_ON(xa, entry > xa_mk_value(start + (1UL << order) - 1));
615 count++;
616 }
617 xas_store(&xas, xa_mk_value(start));
618 xas_unlock(&xas);
619 if (xas_nomem(&xas, GFP_KERNEL)) {
620 count = 0;
621 goto retry;
622 }
623 XA_BUG_ON(xa, xas_error(&xas));
624 XA_BUG_ON(xa, count != present);
625 XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_value(start));
626 XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) !=
627 xa_mk_value(start));
628 xa_erase_index(xa, start);
629}
630
631static noinline void check_store_iter(struct xarray *xa)
632{
633 unsigned int i, j;
634 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1;
635
636 for (i = 0; i < max_order; i++) {
637 unsigned int min = 1 << i;
638 unsigned int max = (2 << i) - 1;
639 __check_store_iter(xa, 0, i, 0);
640 XA_BUG_ON(xa, !xa_empty(xa));
641 __check_store_iter(xa, min, i, 0);
642 XA_BUG_ON(xa, !xa_empty(xa));
643
644 xa_store_index(xa, min, GFP_KERNEL);
645 __check_store_iter(xa, min, i, 1);
646 XA_BUG_ON(xa, !xa_empty(xa));
647 xa_store_index(xa, max, GFP_KERNEL);
648 __check_store_iter(xa, min, i, 1);
649 XA_BUG_ON(xa, !xa_empty(xa));
650
651 for (j = 0; j < min; j++)
652 xa_store_index(xa, j, GFP_KERNEL);
653 __check_store_iter(xa, 0, i, min);
654 XA_BUG_ON(xa, !xa_empty(xa));
655 for (j = 0; j < min; j++)
656 xa_store_index(xa, min + j, GFP_KERNEL);
657 __check_store_iter(xa, min, i, min);
658 XA_BUG_ON(xa, !xa_empty(xa));
659 }
660#ifdef CONFIG_XARRAY_MULTI
661 xa_store_index(xa, 63, GFP_KERNEL);
662 xa_store_index(xa, 65, GFP_KERNEL);
663 __check_store_iter(xa, 64, 2, 1);
664 xa_erase_index(xa, 63);
665#endif
666 XA_BUG_ON(xa, !xa_empty(xa));
667}
668
b803b428
MW		 669static noinline void check_multi_find(struct xarray *xa)
670{
671#ifdef CONFIG_XARRAY_MULTI
672 unsigned long index;
673
674 xa_store_order(xa, 12, 2, xa_mk_value(12), GFP_KERNEL);
675 XA_BUG_ON(xa, xa_store_index(xa, 16, GFP_KERNEL) != NULL);
676
677 index = 0;
678 XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
679 xa_mk_value(12));
680 XA_BUG_ON(xa, index != 12);
681 index = 13;
682 XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) !=
683 xa_mk_value(12));
684 XA_BUG_ON(xa, (index < 12) || (index >= 16));
685 XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) !=
686 xa_mk_value(16));
687 XA_BUG_ON(xa, index != 16);
688
689 xa_erase_index(xa, 12);
690 xa_erase_index(xa, 16);
691 XA_BUG_ON(xa, !xa_empty(xa));
692#endif
693}
694
695static noinline void check_multi_find_2(struct xarray *xa)
696{
697 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1;
698 unsigned int i, j;
699 void *entry;
700
701 for (i = 0; i < max_order; i++) {
702 unsigned long index = 1UL << i;
703 for (j = 0; j < index; j++) {
704 XA_STATE(xas, xa, j + index);
705 xa_store_index(xa, index - 1, GFP_KERNEL);
706 xa_store_order(xa, index, i, xa_mk_value(index),
707 GFP_KERNEL);
708 rcu_read_lock();
709 xas_for_each(&xas, entry, ULONG_MAX) {
710 xa_erase_index(xa, index);
711 }
712 rcu_read_unlock();
713 xa_erase_index(xa, index - 1);
714 XA_BUG_ON(xa, !xa_empty(xa));
715 }
716 }
717}
718
8229706e 719static noinline void check_find_1(struct xarray *xa)
b803b428
MW		 720{
721 unsigned long i, j, k;
722
723 XA_BUG_ON(xa, !xa_empty(xa));
724
725 /*
726 * Check xa_find with all pairs between 0 and 99 inclusive,
727 * starting at every index between 0 and 99
728 */
729 for (i = 0; i < 100; i++) {
730 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
731 xa_set_mark(xa, i, XA_MARK_0);
732 for (j = 0; j < i; j++) {
733 XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) !=
734 NULL);
735 xa_set_mark(xa, j, XA_MARK_0);
736 for (k = 0; k < 100; k++) {
737 unsigned long index = k;
738 void *entry = xa_find(xa, &index, ULONG_MAX,
739 XA_PRESENT);
740 if (k <= j)
741 XA_BUG_ON(xa, index != j);
742 else if (k <= i)
743 XA_BUG_ON(xa, index != i);
744 else
745 XA_BUG_ON(xa, entry != NULL);
746
747 index = k;
748 entry = xa_find(xa, &index, ULONG_MAX,
749 XA_MARK_0);
750 if (k <= j)
751 XA_BUG_ON(xa, index != j);
752 else if (k <= i)
753 XA_BUG_ON(xa, index != i);
754 else
755 XA_BUG_ON(xa, entry != NULL);
756 }
757 xa_erase_index(xa, j);
758 XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0));
759 XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0));
760 }
761 xa_erase_index(xa, i);
762 XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0));
763 }
764 XA_BUG_ON(xa, !xa_empty(xa));
8229706e
MW		 765}
766
767static noinline void check_find_2(struct xarray *xa)
768{
769 void *entry;
770 unsigned long i, j, index = 0;
771
772 xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) {
773 XA_BUG_ON(xa, true);
774 }
775
776 for (i = 0; i < 1024; i++) {
777 xa_store_index(xa, index, GFP_KERNEL);
778 j = 0;
779 index = 0;
780 xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) {
781 XA_BUG_ON(xa, xa_mk_value(index) != entry);
782 XA_BUG_ON(xa, index != j++);
783 }
784 }
785
786 xa_destroy(xa);
787}
788
789static noinline void check_find(struct xarray *xa)
790{
791 check_find_1(xa);
792 check_find_2(xa);
b803b428
MW		 793 check_multi_find(xa);
794 check_multi_find_2(xa);
795}
796
e21a2955
MW		 797/* See find_swap_entry() in mm/shmem.c */
798static noinline unsigned long xa_find_entry(struct xarray *xa, void *item)
799{
800 XA_STATE(xas, xa, 0);
801 unsigned int checked = 0;
802 void *entry;
803
804 rcu_read_lock();
805 xas_for_each(&xas, entry, ULONG_MAX) {
806 if (xas_retry(&xas, entry))
807 continue;
808 if (entry == item)
809 break;
810 checked++;
811 if ((checked % 4) != 0)
812 continue;
813 xas_pause(&xas);
814 }
815 rcu_read_unlock();
816
817 return entry ? xas.xa_index : -1;
818}
819
820static noinline void check_find_entry(struct xarray *xa)
821{
822#ifdef CONFIG_XARRAY_MULTI
823 unsigned int order;
824 unsigned long offset, index;
825
826 for (order = 0; order < 20; order++) {
827 for (offset = 0; offset < (1UL << (order + 3));
828 offset += (1UL << order)) {
829 for (index = 0; index < (1UL << (order + 5));
830 index += (1UL << order)) {
831 xa_store_order(xa, index, order,
832 xa_mk_value(index), GFP_KERNEL);
833 XA_BUG_ON(xa, xa_load(xa, index) !=
834 xa_mk_value(index));
835 XA_BUG_ON(xa, xa_find_entry(xa,
836 xa_mk_value(index)) != index);
837 }
838 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
839 xa_destroy(xa);
840 }
841 }
842#endif
843
844 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
845 xa_store_index(xa, ULONG_MAX, GFP_KERNEL);
846 XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1);
847 XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_value(LONG_MAX)) != -1);
848 xa_erase_index(xa, ULONG_MAX);
849 XA_BUG_ON(xa, !xa_empty(xa));
850}
851
64d3e9a9
MW		 852static noinline void check_move_small(struct xarray *xa, unsigned long idx)
853{
854 XA_STATE(xas, xa, 0);
855 unsigned long i;
856
857 xa_store_index(xa, 0, GFP_KERNEL);
858 xa_store_index(xa, idx, GFP_KERNEL);
859
860 rcu_read_lock();
861 for (i = 0; i < idx * 4; i++) {
862 void *entry = xas_next(&xas);
863 if (i <= idx)
864 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
865 XA_BUG_ON(xa, xas.xa_index != i);
866 if (i == 0 || i == idx)
867 XA_BUG_ON(xa, entry != xa_mk_value(i));
868 else
869 XA_BUG_ON(xa, entry != NULL);
870 }
871 xas_next(&xas);
872 XA_BUG_ON(xa, xas.xa_index != i);
873
874 do {
875 void *entry = xas_prev(&xas);
876 i--;
877 if (i <= idx)
878 XA_BUG_ON(xa, xas.xa_node == XAS_RESTART);
879 XA_BUG_ON(xa, xas.xa_index != i);
880 if (i == 0 || i == idx)
881 XA_BUG_ON(xa, entry != xa_mk_value(i));
882 else
883 XA_BUG_ON(xa, entry != NULL);
884 } while (i > 0);
885
886 xas_set(&xas, ULONG_MAX);
887 XA_BUG_ON(xa, xas_next(&xas) != NULL);
888 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
889 XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0));
890 XA_BUG_ON(xa, xas.xa_index != 0);
891 XA_BUG_ON(xa, xas_prev(&xas) != NULL);
892 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
893 rcu_read_unlock();
894
895 xa_erase_index(xa, 0);
896 xa_erase_index(xa, idx);
897 XA_BUG_ON(xa, !xa_empty(xa));
898}
899
900static noinline void check_move(struct xarray *xa)
901{
902 XA_STATE(xas, xa, (1 << 16) - 1);
903 unsigned long i;
904
905 for (i = 0; i < (1 << 16); i++)
906 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL);
907
908 rcu_read_lock();
909 do {
910 void *entry = xas_prev(&xas);
911 i--;
912 XA_BUG_ON(xa, entry != xa_mk_value(i));
913 XA_BUG_ON(xa, i != xas.xa_index);
914 } while (i != 0);
915
916 XA_BUG_ON(xa, xas_prev(&xas) != NULL);
917 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
918
919 do {
920 void *entry = xas_next(&xas);
921 XA_BUG_ON(xa, entry != xa_mk_value(i));
922 XA_BUG_ON(xa, i != xas.xa_index);
923 i++;
924 } while (i < (1 << 16));
925 rcu_read_unlock();
926
927 for (i = (1 << 8); i < (1 << 15); i++)
928 xa_erase_index(xa, i);
929
930 i = xas.xa_index;
931
932 rcu_read_lock();
933 do {
934 void *entry = xas_prev(&xas);
935 i--;
936 if ((i < (1 << 8)) || (i >= (1 << 15)))
937 XA_BUG_ON(xa, entry != xa_mk_value(i));
938 else
939 XA_BUG_ON(xa, entry != NULL);
940 XA_BUG_ON(xa, i != xas.xa_index);
941 } while (i != 0);
942
943 XA_BUG_ON(xa, xas_prev(&xas) != NULL);
944 XA_BUG_ON(xa, xas.xa_index != ULONG_MAX);
945
946 do {
947 void *entry = xas_next(&xas);
948 if ((i < (1 << 8)) || (i >= (1 << 15)))
949 XA_BUG_ON(xa, entry != xa_mk_value(i));
950 else
951 XA_BUG_ON(xa, entry != NULL);
952 XA_BUG_ON(xa, i != xas.xa_index);
953 i++;
954 } while (i < (1 << 16));
955 rcu_read_unlock();
956
957 xa_destroy(xa);
958
959 for (i = 0; i < 16; i++)
960 check_move_small(xa, 1UL << i);
961
962 for (i = 2; i < 16; i++)
963 check_move_small(xa, (1UL << i) - 1);
964}
965
2264f513
MW		 966static noinline void xa_store_many_order(struct xarray *xa,
967 unsigned long index, unsigned order)
968{
969 XA_STATE_ORDER(xas, xa, index, order);
970 unsigned int i = 0;
971
972 do {
973 xas_lock(&xas);
974 XA_BUG_ON(xa, xas_find_conflict(&xas));
975 xas_create_range(&xas);
976 if (xas_error(&xas))
977 goto unlock;
978 for (i = 0; i < (1U << order); i++) {
979 XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(index + i)));
980 xas_next(&xas);
981 }
982unlock:
983 xas_unlock(&xas);
984 } while (xas_nomem(&xas, GFP_KERNEL));
985
986 XA_BUG_ON(xa, xas_error(&xas));
987}
988
989static noinline void check_create_range_1(struct xarray *xa,
990 unsigned long index, unsigned order)
991{
992 unsigned long i;
993
994 xa_store_many_order(xa, index, order);
995 for (i = index; i < index + (1UL << order); i++)
996 xa_erase_index(xa, i);
997 XA_BUG_ON(xa, !xa_empty(xa));
998}
999
1000static noinline void check_create_range_2(struct xarray *xa, unsigned order)
1001{
1002 unsigned long i;
1003 unsigned long nr = 1UL << order;
1004
1005 for (i = 0; i < nr * nr; i += nr)
1006 xa_store_many_order(xa, i, order);
1007 for (i = 0; i < nr * nr; i++)
1008 xa_erase_index(xa, i);
1009 XA_BUG_ON(xa, !xa_empty(xa));
1010}
1011
1012static noinline void check_create_range_3(void)
1013{
1014 XA_STATE(xas, NULL, 0);
1015 xas_set_err(&xas, -EEXIST);
1016 xas_create_range(&xas);
1017 XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST);
1018}
1019
1020static noinline void check_create_range_4(struct xarray *xa,
1021 unsigned long index, unsigned order)
1022{
1023 XA_STATE_ORDER(xas, xa, index, order);
1024 unsigned long base = xas.xa_index;
1025 unsigned long i = 0;
1026
1027 xa_store_index(xa, index, GFP_KERNEL);
1028 do {
1029 xas_lock(&xas);
1030 xas_create_range(&xas);
1031 if (xas_error(&xas))
1032 goto unlock;
1033 for (i = 0; i < (1UL << order); i++) {
1034 void *old = xas_store(&xas, xa_mk_value(base + i));
1035 if (xas.xa_index == index)
1036 XA_BUG_ON(xa, old != xa_mk_value(base + i));
1037 else
1038 XA_BUG_ON(xa, old != NULL);
1039 xas_next(&xas);
1040 }
1041unlock:
1042 xas_unlock(&xas);
1043 } while (xas_nomem(&xas, GFP_KERNEL));
1044
1045 XA_BUG_ON(xa, xas_error(&xas));
1046
1047 for (i = base; i < base + (1UL << order); i++)
1048 xa_erase_index(xa, i);
1049 XA_BUG_ON(xa, !xa_empty(xa));
1050}
1051
1052static noinline void check_create_range(struct xarray *xa)
1053{
1054 unsigned int order;
1055 unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1;
1056
1057 for (order = 0; order < max_order; order++) {
1058 check_create_range_1(xa, 0, order);
1059 check_create_range_1(xa, 1U << order, order);
1060 check_create_range_1(xa, 2U << order, order);
1061 check_create_range_1(xa, 3U << order, order);
1062 check_create_range_1(xa, 1U << 24, order);
1063 if (order < 10)
1064 check_create_range_2(xa, order);
1065
1066 check_create_range_4(xa, 0, order);
1067 check_create_range_4(xa, 1U << order, order);
1068 check_create_range_4(xa, 2U << order, order);
1069 check_create_range_4(xa, 3U << order, order);
1070 check_create_range_4(xa, 1U << 24, order);
1071
1072 check_create_range_4(xa, 1, order);
1073 check_create_range_4(xa, (1U << order) + 1, order);
1074 check_create_range_4(xa, (2U << order) + 1, order);
1075 check_create_range_4(xa, (2U << order) - 1, order);
1076 check_create_range_4(xa, (3U << order) + 1, order);
1077 check_create_range_4(xa, (3U << order) - 1, order);
1078 check_create_range_4(xa, (1U << 24) + 1, order);
1079 }
1080
1081 check_create_range_3();
1082}
1083
0e9446c3
MW		 1084static noinline void __check_store_range(struct xarray *xa, unsigned long first,
1085 unsigned long last)
1086{
1087#ifdef CONFIG_XARRAY_MULTI
1088 xa_store_range(xa, first, last, xa_mk_value(first), GFP_KERNEL);
1089
1090 XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_value(first));
1091 XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_value(first));
1092 XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL);
1093 XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL);
1094
1095 xa_store_range(xa, first, last, NULL, GFP_KERNEL);
1096#endif
1097
1098 XA_BUG_ON(xa, !xa_empty(xa));
1099}
1100
1101static noinline void check_store_range(struct xarray *xa)
1102{
1103 unsigned long i, j;
1104
1105 for (i = 0; i < 128; i++) {
1106 for (j = i; j < 128; j++) {
1107 __check_store_range(xa, i, j);
1108 __check_store_range(xa, 128 + i, 128 + j);
1109 __check_store_range(xa, 4095 + i, 4095 + j);
1110 __check_store_range(xa, 4096 + i, 4096 + j);
1111 __check_store_range(xa, 123456 + i, 123456 + j);
5404a7f1 1112 __check_store_range(xa, (1 << 24) + i, (1 << 24) + j);
0e9446c3
MW		 1113 }
1114 }
1115}
1116
a97e7904
MW		 1117static LIST_HEAD(shadow_nodes);
1118
1119static void test_update_node(struct xa_node *node)
1120{
1121 if (node->count && node->count == node->nr_values) {
1122 if (list_empty(&node->private_list))
1123 list_add(&shadow_nodes, &node->private_list);
1124 } else {
1125 if (!list_empty(&node->private_list))
1126 list_del_init(&node->private_list);
1127 }
1128}
1129
1130static noinline void shadow_remove(struct xarray *xa)
1131{
1132 struct xa_node *node;
1133
1134 xa_lock(xa);
1135 while ((node = list_first_entry_or_null(&shadow_nodes,
1136 struct xa_node, private_list))) {
1137 XA_STATE(xas, node->array, 0);
1138 XA_BUG_ON(xa, node->array != xa);
1139 list_del_init(&node->private_list);
1140 xas.xa_node = xa_parent_locked(node->array, node);
1141 xas.xa_offset = node->offset;
1142 xas.xa_shift = node->shift + XA_CHUNK_SHIFT;
1143 xas_set_update(&xas, test_update_node);
1144 xas_store(&xas, NULL);
1145 }
1146 xa_unlock(xa);
1147}
1148
1149static noinline void check_workingset(struct xarray *xa, unsigned long index)
1150{
1151 XA_STATE(xas, xa, index);
1152 xas_set_update(&xas, test_update_node);
1153
1154 do {
1155 xas_lock(&xas);
1156 xas_store(&xas, xa_mk_value(0));
1157 xas_next(&xas);
1158 xas_store(&xas, xa_mk_value(1));
1159 xas_unlock(&xas);
1160 } while (xas_nomem(&xas, GFP_KERNEL));
1161
1162 XA_BUG_ON(xa, list_empty(&shadow_nodes));
1163
1164 xas_lock(&xas);
1165 xas_next(&xas);
1166 xas_store(&xas, &xas);
1167 XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1168
1169 xas_store(&xas, xa_mk_value(2));
1170 xas_unlock(&xas);
1171 XA_BUG_ON(xa, list_empty(&shadow_nodes));
1172
1173 shadow_remove(xa);
1174 XA_BUG_ON(xa, !list_empty(&shadow_nodes));
1175 XA_BUG_ON(xa, !xa_empty(xa));
1176}
1177
d6427f81
MW		 1178/*
1179 * Check that the pointer / value / sibling entries are accounted the
1180 * way we expect them to be.
1181 */
1182static noinline void check_account(struct xarray *xa)
1183{
1184#ifdef CONFIG_XARRAY_MULTI
1185 unsigned int order;
1186
1187 for (order = 1; order < 12; order++) {
1188 XA_STATE(xas, xa, 1 << order);
1189
1190 xa_store_order(xa, 0, order, xa, GFP_KERNEL);
fffc9a26 1191 rcu_read_lock();
d6427f81
MW		 1192 xas_load(&xas);
1193 XA_BUG_ON(xa, xas.xa_node->count == 0);
1194 XA_BUG_ON(xa, xas.xa_node->count > (1 << order));
1195 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
fffc9a26 1196 rcu_read_unlock();
d6427f81
MW		 1197
1198 xa_store_order(xa, 1 << order, order, xa_mk_value(1 << order),
1199 GFP_KERNEL);
1200 XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2);
1201
1202 xa_erase(xa, 1 << order);
1203 XA_BUG_ON(xa, xas.xa_node->nr_values != 0);
1204
1205 xa_erase(xa, 0);
1206 XA_BUG_ON(xa, !xa_empty(xa));
1207 }
1208#endif
1209}
1210
687149fc
MW		 1211static noinline void check_destroy(struct xarray *xa)
1212{
1213 unsigned long index;
1214
1215 XA_BUG_ON(xa, !xa_empty(xa));
1216
1217 /* Destroying an empty array is a no-op */
1218 xa_destroy(xa);
1219 XA_BUG_ON(xa, !xa_empty(xa));
1220
1221 /* Destroying an array with a single entry */
1222 for (index = 0; index < 1000; index++) {
1223 xa_store_index(xa, index, GFP_KERNEL);
1224 XA_BUG_ON(xa, xa_empty(xa));
1225 xa_destroy(xa);
1226 XA_BUG_ON(xa, !xa_empty(xa));
1227 }
1228
1229 /* Destroying an array with a single entry at ULONG_MAX */
1230 xa_store(xa, ULONG_MAX, xa, GFP_KERNEL);
1231 XA_BUG_ON(xa, xa_empty(xa));
1232 xa_destroy(xa);
1233 XA_BUG_ON(xa, !xa_empty(xa));
1234
1235#ifdef CONFIG_XARRAY_MULTI
1236 /* Destroying an array with a multi-index entry */
1237 xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL);
1238 XA_BUG_ON(xa, xa_empty(xa));
1239 xa_destroy(xa);
1240 XA_BUG_ON(xa, !xa_empty(xa));
1241#endif
1242}
1243
58d6ea30 1244static DEFINE_XARRAY(array);
ad3d6c72
MW		 1245
1246static int xarray_checks(void)
1247{
58d6ea30 1248 check_xa_err(&array);
b803b428 1249 check_xas_retry(&array);
ad3d6c72 1250 check_xa_load(&array);
9b89a035 1251 check_xa_mark(&array);
58d6ea30 1252 check_xa_shrink(&array);
b803b428 1253 check_xas_erase(&array);
41aec91f 1254 check_cmpxchg(&array);
9f14d4f1 1255 check_reserve(&array);
58d6ea30 1256 check_multi_store(&array);
371c752d 1257 check_xa_alloc();
b803b428 1258 check_find(&array);
e21a2955 1259 check_find_entry(&array);
d6427f81 1260 check_account(&array);
687149fc 1261 check_destroy(&array);
64d3e9a9 1262 check_move(&array);
2264f513 1263 check_create_range(&array);
0e9446c3 1264 check_store_range(&array);
4e99d4e9 1265 check_store_iter(&array);
ad3d6c72 1266
a97e7904
MW		 1267 check_workingset(&array, 0);
1268 check_workingset(&array, 64);
1269 check_workingset(&array, 4096);
1270
ad3d6c72
MW		 1271 printk("XArray: %u of %u tests passed\n", tests_passed, tests_run);
1272 return (tests_run == tests_passed) ? 0 : -EINVAL;
1273}
1274
1275static void xarray_exit(void)
1276{
1277}
1278
1279module_init(xarray_checks);
1280module_exit(xarray_exit);
1281MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
1282MODULE_LICENSE("GPL");
Mirror https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git