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