1ad3d6c72SMatthew Wilcox // SPDX-License-Identifier: GPL-2.0+ 2ad3d6c72SMatthew Wilcox /* 3ad3d6c72SMatthew Wilcox * test_xarray.c: Test the XArray API 4ad3d6c72SMatthew Wilcox * Copyright (c) 2017-2018 Microsoft Corporation 5ad3d6c72SMatthew Wilcox * Author: Matthew Wilcox <willy@infradead.org> 6ad3d6c72SMatthew Wilcox */ 7ad3d6c72SMatthew Wilcox 8ad3d6c72SMatthew Wilcox #include <linux/xarray.h> 9ad3d6c72SMatthew Wilcox #include <linux/module.h> 10ad3d6c72SMatthew Wilcox 11ad3d6c72SMatthew Wilcox static unsigned int tests_run; 12ad3d6c72SMatthew Wilcox static unsigned int tests_passed; 13ad3d6c72SMatthew Wilcox 14ad3d6c72SMatthew Wilcox #ifndef XA_DEBUG 15ad3d6c72SMatthew Wilcox # ifdef __KERNEL__ 16ad3d6c72SMatthew Wilcox void xa_dump(const struct xarray *xa) { } 17ad3d6c72SMatthew Wilcox # endif 18ad3d6c72SMatthew Wilcox #undef XA_BUG_ON 19ad3d6c72SMatthew Wilcox #define XA_BUG_ON(xa, x) do { \ 20ad3d6c72SMatthew Wilcox tests_run++; \ 21ad3d6c72SMatthew Wilcox if (x) { \ 22ad3d6c72SMatthew Wilcox printk("BUG at %s:%d\n", __func__, __LINE__); \ 23ad3d6c72SMatthew Wilcox xa_dump(xa); \ 24ad3d6c72SMatthew Wilcox dump_stack(); \ 25ad3d6c72SMatthew Wilcox } else { \ 26ad3d6c72SMatthew Wilcox tests_passed++; \ 27ad3d6c72SMatthew Wilcox } \ 28ad3d6c72SMatthew Wilcox } while (0) 29ad3d6c72SMatthew Wilcox #endif 30ad3d6c72SMatthew Wilcox 31ad3d6c72SMatthew Wilcox static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp) 32ad3d6c72SMatthew Wilcox { 3358d6ea30SMatthew Wilcox return xa_store(xa, index, xa_mk_value(index & LONG_MAX), gfp); 34ad3d6c72SMatthew Wilcox } 35ad3d6c72SMatthew Wilcox 36371c752dSMatthew Wilcox static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp) 37371c752dSMatthew Wilcox { 38371c752dSMatthew Wilcox u32 id = 0; 39371c752dSMatthew Wilcox 40371c752dSMatthew Wilcox XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_value(index & LONG_MAX), 41371c752dSMatthew Wilcox gfp) != 0); 42371c752dSMatthew Wilcox XA_BUG_ON(xa, id != index); 43371c752dSMatthew Wilcox } 44371c752dSMatthew Wilcox 45ad3d6c72SMatthew Wilcox static void xa_erase_index(struct xarray *xa, unsigned long index) 46ad3d6c72SMatthew Wilcox { 4758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_value(index & LONG_MAX)); 4858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, index) != NULL); 4958d6ea30SMatthew Wilcox } 5058d6ea30SMatthew Wilcox 5158d6ea30SMatthew Wilcox /* 5258d6ea30SMatthew Wilcox * If anyone needs this, please move it to xarray.c. We have no current 5358d6ea30SMatthew Wilcox * users outside the test suite because all current multislot users want 5458d6ea30SMatthew Wilcox * to use the advanced API. 5558d6ea30SMatthew Wilcox */ 5658d6ea30SMatthew Wilcox static void *xa_store_order(struct xarray *xa, unsigned long index, 5758d6ea30SMatthew Wilcox unsigned order, void *entry, gfp_t gfp) 5858d6ea30SMatthew Wilcox { 5958d6ea30SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 6058d6ea30SMatthew Wilcox void *curr; 6158d6ea30SMatthew Wilcox 6258d6ea30SMatthew Wilcox do { 6358d6ea30SMatthew Wilcox xas_lock(&xas); 6458d6ea30SMatthew Wilcox curr = xas_store(&xas, entry); 6558d6ea30SMatthew Wilcox xas_unlock(&xas); 6658d6ea30SMatthew Wilcox } while (xas_nomem(&xas, gfp)); 6758d6ea30SMatthew Wilcox 6858d6ea30SMatthew Wilcox return curr; 6958d6ea30SMatthew Wilcox } 7058d6ea30SMatthew Wilcox 7158d6ea30SMatthew Wilcox static noinline void check_xa_err(struct xarray *xa) 7258d6ea30SMatthew Wilcox { 7358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0); 7458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0); 7558d6ea30SMatthew Wilcox #ifndef __KERNEL__ 7658d6ea30SMatthew Wilcox /* The kernel does not fail GFP_NOWAIT allocations */ 7758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM); 7858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM); 7958d6ea30SMatthew Wilcox #endif 8058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0); 8158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0); 8258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0); 8358d6ea30SMatthew Wilcox // kills the test-suite :-( 8458d6ea30SMatthew Wilcox // XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL); 85ad3d6c72SMatthew Wilcox } 86ad3d6c72SMatthew Wilcox 87b803b428SMatthew Wilcox static noinline void check_xas_retry(struct xarray *xa) 88b803b428SMatthew Wilcox { 89b803b428SMatthew Wilcox XA_STATE(xas, xa, 0); 90b803b428SMatthew Wilcox void *entry; 91b803b428SMatthew Wilcox 92b803b428SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 93b803b428SMatthew Wilcox xa_store_index(xa, 1, GFP_KERNEL); 94b803b428SMatthew Wilcox 95b803b428SMatthew Wilcox rcu_read_lock(); 96b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0)); 97b803b428SMatthew Wilcox xa_erase_index(xa, 1); 98b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas))); 99b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_retry(&xas, NULL)); 100b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0))); 101b803b428SMatthew Wilcox xas_reset(&xas); 102b803b428SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node != XAS_RESTART); 103b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0)); 104b803b428SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node != NULL); 105b803b428SMatthew Wilcox 106b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL); 107b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas))); 108b803b428SMatthew Wilcox xas.xa_node = XAS_RESTART; 109b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0)); 110b803b428SMatthew Wilcox rcu_read_unlock(); 111b803b428SMatthew Wilcox 112b803b428SMatthew Wilcox /* Make sure we can iterate through retry entries */ 113b803b428SMatthew Wilcox xas_lock(&xas); 114b803b428SMatthew Wilcox xas_set(&xas, 0); 115b803b428SMatthew Wilcox xas_store(&xas, XA_RETRY_ENTRY); 116b803b428SMatthew Wilcox xas_set(&xas, 1); 117b803b428SMatthew Wilcox xas_store(&xas, XA_RETRY_ENTRY); 118b803b428SMatthew Wilcox 119b803b428SMatthew Wilcox xas_set(&xas, 0); 120b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 121b803b428SMatthew Wilcox xas_store(&xas, xa_mk_value(xas.xa_index)); 122b803b428SMatthew Wilcox } 123b803b428SMatthew Wilcox xas_unlock(&xas); 124b803b428SMatthew Wilcox 125b803b428SMatthew Wilcox xa_erase_index(xa, 0); 126b803b428SMatthew Wilcox xa_erase_index(xa, 1); 127b803b428SMatthew Wilcox } 128b803b428SMatthew Wilcox 129ad3d6c72SMatthew Wilcox static noinline void check_xa_load(struct xarray *xa) 130ad3d6c72SMatthew Wilcox { 131ad3d6c72SMatthew Wilcox unsigned long i, j; 132ad3d6c72SMatthew Wilcox 133ad3d6c72SMatthew Wilcox for (i = 0; i < 1024; i++) { 134ad3d6c72SMatthew Wilcox for (j = 0; j < 1024; j++) { 135ad3d6c72SMatthew Wilcox void *entry = xa_load(xa, j); 136ad3d6c72SMatthew Wilcox if (j < i) 137ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, xa_to_value(entry) != j); 138ad3d6c72SMatthew Wilcox else 139ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, entry); 140ad3d6c72SMatthew Wilcox } 141ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 142ad3d6c72SMatthew Wilcox } 143ad3d6c72SMatthew Wilcox 144ad3d6c72SMatthew Wilcox for (i = 0; i < 1024; i++) { 145ad3d6c72SMatthew Wilcox for (j = 0; j < 1024; j++) { 146ad3d6c72SMatthew Wilcox void *entry = xa_load(xa, j); 147ad3d6c72SMatthew Wilcox if (j >= i) 148ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, xa_to_value(entry) != j); 149ad3d6c72SMatthew Wilcox else 150ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, entry); 151ad3d6c72SMatthew Wilcox } 152ad3d6c72SMatthew Wilcox xa_erase_index(xa, i); 153ad3d6c72SMatthew Wilcox } 154ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 155ad3d6c72SMatthew Wilcox } 156ad3d6c72SMatthew Wilcox 1579b89a035SMatthew Wilcox static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index) 1589b89a035SMatthew Wilcox { 15958d6ea30SMatthew Wilcox unsigned int order; 16058d6ea30SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1; 16158d6ea30SMatthew Wilcox 1629b89a035SMatthew Wilcox /* NULL elements have no marks set */ 1639b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1649b89a035SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 1659b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1669b89a035SMatthew Wilcox 1679b89a035SMatthew Wilcox /* Storing a pointer will not make a mark appear */ 1689b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL); 1699b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1709b89a035SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 1719b89a035SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0)); 1729b89a035SMatthew Wilcox 1739b89a035SMatthew Wilcox /* Setting one mark will not set another mark */ 1749b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0)); 1759b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1)); 1769b89a035SMatthew Wilcox 1779b89a035SMatthew Wilcox /* Storing NULL clears marks, and they can't be set again */ 1789b89a035SMatthew Wilcox xa_erase_index(xa, index); 1799b89a035SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1809b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1819b89a035SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 1829b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 18358d6ea30SMatthew Wilcox 18458d6ea30SMatthew Wilcox /* 18558d6ea30SMatthew Wilcox * Storing a multi-index entry over entries with marks gives the 18658d6ea30SMatthew Wilcox * entire entry the union of the marks 18758d6ea30SMatthew Wilcox */ 18858d6ea30SMatthew Wilcox BUG_ON((index % 4) != 0); 18958d6ea30SMatthew Wilcox for (order = 2; order < max_order; order++) { 19058d6ea30SMatthew Wilcox unsigned long base = round_down(index, 1UL << order); 19158d6ea30SMatthew Wilcox unsigned long next = base + (1UL << order); 19258d6ea30SMatthew Wilcox unsigned long i; 19358d6ea30SMatthew Wilcox 19458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL)); 19558d6ea30SMatthew Wilcox xa_set_mark(xa, index + 1, XA_MARK_0); 19658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL)); 19758d6ea30SMatthew Wilcox xa_set_mark(xa, index + 2, XA_MARK_1); 19858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL)); 19958d6ea30SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_value(index), 20058d6ea30SMatthew Wilcox GFP_KERNEL); 20158d6ea30SMatthew Wilcox for (i = base; i < next; i++) { 20293eb07f7SMatthew Wilcox XA_STATE(xas, xa, i); 20393eb07f7SMatthew Wilcox unsigned int seen = 0; 20493eb07f7SMatthew Wilcox void *entry; 20593eb07f7SMatthew Wilcox 20658d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0)); 20758d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_1)); 20858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_2)); 20993eb07f7SMatthew Wilcox 21093eb07f7SMatthew Wilcox /* We should see two elements in the array */ 21193eb07f7SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) 21293eb07f7SMatthew Wilcox seen++; 21393eb07f7SMatthew Wilcox XA_BUG_ON(xa, seen != 2); 21493eb07f7SMatthew Wilcox 21593eb07f7SMatthew Wilcox /* One of which is marked */ 21693eb07f7SMatthew Wilcox xas_set(&xas, 0); 21793eb07f7SMatthew Wilcox seen = 0; 21893eb07f7SMatthew Wilcox xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) 21993eb07f7SMatthew Wilcox seen++; 22093eb07f7SMatthew Wilcox XA_BUG_ON(xa, seen != 1); 22158d6ea30SMatthew Wilcox } 22258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0)); 22358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1)); 22458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2)); 22558d6ea30SMatthew Wilcox xa_erase_index(xa, index); 22658d6ea30SMatthew Wilcox xa_erase_index(xa, next); 22758d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 22858d6ea30SMatthew Wilcox } 22958d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 2309b89a035SMatthew Wilcox } 2319b89a035SMatthew Wilcox 232adb9d9c4SMatthew Wilcox static noinline void check_xa_mark_2(struct xarray *xa) 233adb9d9c4SMatthew Wilcox { 234adb9d9c4SMatthew Wilcox XA_STATE(xas, xa, 0); 235adb9d9c4SMatthew Wilcox unsigned long index; 236adb9d9c4SMatthew Wilcox unsigned int count = 0; 237adb9d9c4SMatthew Wilcox void *entry; 238adb9d9c4SMatthew Wilcox 239adb9d9c4SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 240adb9d9c4SMatthew Wilcox xa_set_mark(xa, 0, XA_MARK_0); 241adb9d9c4SMatthew Wilcox xas_lock(&xas); 242adb9d9c4SMatthew Wilcox xas_load(&xas); 243adb9d9c4SMatthew Wilcox xas_init_marks(&xas); 244adb9d9c4SMatthew Wilcox xas_unlock(&xas); 245adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0); 246adb9d9c4SMatthew Wilcox 247adb9d9c4SMatthew Wilcox for (index = 3500; index < 4500; index++) { 248adb9d9c4SMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 249adb9d9c4SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 250adb9d9c4SMatthew Wilcox } 251adb9d9c4SMatthew Wilcox 252adb9d9c4SMatthew Wilcox xas_reset(&xas); 253adb9d9c4SMatthew Wilcox rcu_read_lock(); 254adb9d9c4SMatthew Wilcox xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) 255adb9d9c4SMatthew Wilcox count++; 256adb9d9c4SMatthew Wilcox rcu_read_unlock(); 257adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, count != 1000); 258adb9d9c4SMatthew Wilcox 259adb9d9c4SMatthew Wilcox xas_lock(&xas); 260adb9d9c4SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 261adb9d9c4SMatthew Wilcox xas_init_marks(&xas); 262adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0)); 263adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0)); 264adb9d9c4SMatthew Wilcox } 265adb9d9c4SMatthew Wilcox xas_unlock(&xas); 266adb9d9c4SMatthew Wilcox 267adb9d9c4SMatthew Wilcox xa_destroy(xa); 268adb9d9c4SMatthew Wilcox } 269adb9d9c4SMatthew Wilcox 2709b89a035SMatthew Wilcox static noinline void check_xa_mark(struct xarray *xa) 2719b89a035SMatthew Wilcox { 2729b89a035SMatthew Wilcox unsigned long index; 2739b89a035SMatthew Wilcox 2749b89a035SMatthew Wilcox for (index = 0; index < 16384; index += 4) 2759b89a035SMatthew Wilcox check_xa_mark_1(xa, index); 276adb9d9c4SMatthew Wilcox 277adb9d9c4SMatthew Wilcox check_xa_mark_2(xa); 2789b89a035SMatthew Wilcox } 2799b89a035SMatthew Wilcox 28058d6ea30SMatthew Wilcox static noinline void check_xa_shrink(struct xarray *xa) 28158d6ea30SMatthew Wilcox { 28258d6ea30SMatthew Wilcox XA_STATE(xas, xa, 1); 28358d6ea30SMatthew Wilcox struct xa_node *node; 28493eb07f7SMatthew Wilcox unsigned int order; 28593eb07f7SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1; 28658d6ea30SMatthew Wilcox 28758d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 28858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL); 28958d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL); 29058d6ea30SMatthew Wilcox 29158d6ea30SMatthew Wilcox /* 29258d6ea30SMatthew Wilcox * Check that erasing the entry at 1 shrinks the tree and properly 29358d6ea30SMatthew Wilcox * marks the node as being deleted. 29458d6ea30SMatthew Wilcox */ 29558d6ea30SMatthew Wilcox xas_lock(&xas); 29658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1)); 29758d6ea30SMatthew Wilcox node = xas.xa_node; 29858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0)); 29958d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1)); 30058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != NULL); 30158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS); 30258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY); 30358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_load(&xas) != NULL); 30458d6ea30SMatthew Wilcox xas_unlock(&xas); 30558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 30658d6ea30SMatthew Wilcox xa_erase_index(xa, 0); 30758d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 30893eb07f7SMatthew Wilcox 30993eb07f7SMatthew Wilcox for (order = 0; order < max_order; order++) { 31093eb07f7SMatthew Wilcox unsigned long max = (1UL << order) - 1; 31193eb07f7SMatthew Wilcox xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL); 31293eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0)); 31393eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL); 31493eb07f7SMatthew Wilcox rcu_read_lock(); 31593eb07f7SMatthew Wilcox node = xa_head(xa); 31693eb07f7SMatthew Wilcox rcu_read_unlock(); 31793eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) != 31893eb07f7SMatthew Wilcox NULL); 31993eb07f7SMatthew Wilcox rcu_read_lock(); 32093eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_head(xa) == node); 32193eb07f7SMatthew Wilcox rcu_read_unlock(); 32293eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL); 32393eb07f7SMatthew Wilcox xa_erase_index(xa, ULONG_MAX); 32493eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa->xa_head != node); 32593eb07f7SMatthew Wilcox xa_erase_index(xa, 0); 32693eb07f7SMatthew Wilcox } 32758d6ea30SMatthew Wilcox } 32858d6ea30SMatthew Wilcox 32941aec91fSMatthew Wilcox static noinline void check_cmpxchg(struct xarray *xa) 33041aec91fSMatthew Wilcox { 33141aec91fSMatthew Wilcox void *FIVE = xa_mk_value(5); 33241aec91fSMatthew Wilcox void *SIX = xa_mk_value(6); 33341aec91fSMatthew Wilcox void *LOTS = xa_mk_value(12345678); 33441aec91fSMatthew Wilcox 33541aec91fSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 33641aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL); 33741aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EEXIST); 33841aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS); 33941aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS); 34041aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE); 34141aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL); 34241aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL); 34341aec91fSMatthew Wilcox xa_erase_index(xa, 12345678); 34441aec91fSMatthew Wilcox xa_erase_index(xa, 5); 34541aec91fSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 34641aec91fSMatthew Wilcox } 34741aec91fSMatthew Wilcox 3489f14d4f1SMatthew Wilcox static noinline void check_reserve(struct xarray *xa) 3499f14d4f1SMatthew Wilcox { 3509f14d4f1SMatthew Wilcox void *entry; 3519f14d4f1SMatthew Wilcox unsigned long index = 0; 3529f14d4f1SMatthew Wilcox 3539f14d4f1SMatthew Wilcox /* An array with a reserved entry is not empty */ 3549f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3559f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3569f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 3579f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 12345678)); 3589f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3599f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3609f14d4f1SMatthew Wilcox 3619f14d4f1SMatthew Wilcox /* Releasing a used entry does nothing */ 3629f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3639f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL); 3649f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3659f14d4f1SMatthew Wilcox xa_erase_index(xa, 12345678); 3669f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3679f14d4f1SMatthew Wilcox 3689f14d4f1SMatthew Wilcox /* cmpxchg sees a reserved entry as NULL */ 3699f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3709f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, NULL, xa_mk_value(12345678), 3719f14d4f1SMatthew Wilcox GFP_NOWAIT) != NULL); 3729f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3739f14d4f1SMatthew Wilcox xa_erase_index(xa, 12345678); 3749f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3759f14d4f1SMatthew Wilcox 3769f14d4f1SMatthew Wilcox /* Can iterate through a reserved entry */ 3779f14d4f1SMatthew Wilcox xa_store_index(xa, 5, GFP_KERNEL); 3789f14d4f1SMatthew Wilcox xa_reserve(xa, 6, GFP_KERNEL); 3799f14d4f1SMatthew Wilcox xa_store_index(xa, 7, GFP_KERNEL); 3809f14d4f1SMatthew Wilcox 3819f14d4f1SMatthew Wilcox xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 3829f14d4f1SMatthew Wilcox XA_BUG_ON(xa, index != 5 && index != 7); 3839f14d4f1SMatthew Wilcox } 3849f14d4f1SMatthew Wilcox xa_destroy(xa); 3859f14d4f1SMatthew Wilcox } 3869f14d4f1SMatthew Wilcox 387b803b428SMatthew Wilcox static noinline void check_xas_erase(struct xarray *xa) 388b803b428SMatthew Wilcox { 389b803b428SMatthew Wilcox XA_STATE(xas, xa, 0); 390b803b428SMatthew Wilcox void *entry; 391b803b428SMatthew Wilcox unsigned long i, j; 392b803b428SMatthew Wilcox 393b803b428SMatthew Wilcox for (i = 0; i < 200; i++) { 394b803b428SMatthew Wilcox for (j = i; j < 2 * i + 17; j++) { 395b803b428SMatthew Wilcox xas_set(&xas, j); 396b803b428SMatthew Wilcox do { 397b803b428SMatthew Wilcox xas_lock(&xas); 398b803b428SMatthew Wilcox xas_store(&xas, xa_mk_value(j)); 399b803b428SMatthew Wilcox xas_unlock(&xas); 400b803b428SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 401b803b428SMatthew Wilcox } 402b803b428SMatthew Wilcox 403b803b428SMatthew Wilcox xas_set(&xas, ULONG_MAX); 404b803b428SMatthew Wilcox do { 405b803b428SMatthew Wilcox xas_lock(&xas); 406b803b428SMatthew Wilcox xas_store(&xas, xa_mk_value(0)); 407b803b428SMatthew Wilcox xas_unlock(&xas); 408b803b428SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 409b803b428SMatthew Wilcox 410b803b428SMatthew Wilcox xas_lock(&xas); 411b803b428SMatthew Wilcox xas_store(&xas, NULL); 412b803b428SMatthew Wilcox 413b803b428SMatthew Wilcox xas_set(&xas, 0); 414b803b428SMatthew Wilcox j = i; 415b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 416b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(j)); 417b803b428SMatthew Wilcox xas_store(&xas, NULL); 418b803b428SMatthew Wilcox j++; 419b803b428SMatthew Wilcox } 420b803b428SMatthew Wilcox xas_unlock(&xas); 421b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 422b803b428SMatthew Wilcox } 423b803b428SMatthew Wilcox } 424b803b428SMatthew Wilcox 4254f06d630SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 4264f06d630SMatthew Wilcox static noinline void check_multi_store_1(struct xarray *xa, unsigned long index, 4274f06d630SMatthew Wilcox unsigned int order) 4284f06d630SMatthew Wilcox { 4294f06d630SMatthew Wilcox XA_STATE(xas, xa, index); 4304f06d630SMatthew Wilcox unsigned long min = index & ~((1UL << order) - 1); 4314f06d630SMatthew Wilcox unsigned long max = min + (1UL << order); 4324f06d630SMatthew Wilcox 4334f06d630SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_value(index), GFP_KERNEL); 4344f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(index)); 4354f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(index)); 4364f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != NULL); 4374f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 4384f06d630SMatthew Wilcox 4394f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(min)) != xa_mk_value(index)); 4404f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(min)); 4414f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(min)); 4424f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != NULL); 4434f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 4444f06d630SMatthew Wilcox 4454f06d630SMatthew Wilcox xa_erase_index(xa, min); 4464f06d630SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 4474f06d630SMatthew Wilcox } 4484f06d630SMatthew Wilcox 4494f06d630SMatthew Wilcox static noinline void check_multi_store_2(struct xarray *xa, unsigned long index, 4504f06d630SMatthew Wilcox unsigned int order) 4514f06d630SMatthew Wilcox { 4524f06d630SMatthew Wilcox XA_STATE(xas, xa, index); 4534f06d630SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL); 4544f06d630SMatthew Wilcox 4554f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0)); 4564f06d630SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != index); 4574f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1)); 4584f06d630SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 4594f06d630SMatthew Wilcox } 4604f06d630SMatthew Wilcox #endif 4614f06d630SMatthew Wilcox 46258d6ea30SMatthew Wilcox static noinline void check_multi_store(struct xarray *xa) 46358d6ea30SMatthew Wilcox { 46458d6ea30SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 46558d6ea30SMatthew Wilcox unsigned long i, j, k; 46658d6ea30SMatthew Wilcox unsigned int max_order = (sizeof(long) == 4) ? 30 : 60; 46758d6ea30SMatthew Wilcox 46858d6ea30SMatthew Wilcox /* Loading from any position returns the same value */ 46958d6ea30SMatthew Wilcox xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL); 47058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 47158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0)); 47258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != NULL); 47358d6ea30SMatthew Wilcox rcu_read_lock(); 47458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2); 47558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2); 47658d6ea30SMatthew Wilcox rcu_read_unlock(); 47758d6ea30SMatthew Wilcox 47858d6ea30SMatthew Wilcox /* Storing adjacent to the value does not alter the value */ 47958d6ea30SMatthew Wilcox xa_store(xa, 3, xa, GFP_KERNEL); 48058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 48158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0)); 48258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != NULL); 48358d6ea30SMatthew Wilcox rcu_read_lock(); 48458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3); 48558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2); 48658d6ea30SMatthew Wilcox rcu_read_unlock(); 48758d6ea30SMatthew Wilcox 48858d6ea30SMatthew Wilcox /* Overwriting multiple indexes works */ 48958d6ea30SMatthew Wilcox xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL); 49058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1)); 49158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1)); 49258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1)); 49358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1)); 49458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 4) != NULL); 49558d6ea30SMatthew Wilcox rcu_read_lock(); 49658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4); 49758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4); 49858d6ea30SMatthew Wilcox rcu_read_unlock(); 49958d6ea30SMatthew Wilcox 50058d6ea30SMatthew Wilcox /* We can erase multiple values with a single store */ 50158d6ea30SMatthew Wilcox xa_store_order(xa, 0, 63, NULL, GFP_KERNEL); 50258d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 50358d6ea30SMatthew Wilcox 50458d6ea30SMatthew Wilcox /* Even when the first slot is empty but the others aren't */ 50558d6ea30SMatthew Wilcox xa_store_index(xa, 1, GFP_KERNEL); 50658d6ea30SMatthew Wilcox xa_store_index(xa, 2, GFP_KERNEL); 50758d6ea30SMatthew Wilcox xa_store_order(xa, 0, 2, NULL, GFP_KERNEL); 50858d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 50958d6ea30SMatthew Wilcox 51058d6ea30SMatthew Wilcox for (i = 0; i < max_order; i++) { 51158d6ea30SMatthew Wilcox for (j = 0; j < max_order; j++) { 51258d6ea30SMatthew Wilcox xa_store_order(xa, 0, i, xa_mk_value(i), GFP_KERNEL); 51358d6ea30SMatthew Wilcox xa_store_order(xa, 0, j, xa_mk_value(j), GFP_KERNEL); 51458d6ea30SMatthew Wilcox 51558d6ea30SMatthew Wilcox for (k = 0; k < max_order; k++) { 51658d6ea30SMatthew Wilcox void *entry = xa_load(xa, (1UL << k) - 1); 51758d6ea30SMatthew Wilcox if ((i < k) && (j < k)) 51858d6ea30SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 51958d6ea30SMatthew Wilcox else 52058d6ea30SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(j)); 52158d6ea30SMatthew Wilcox } 52258d6ea30SMatthew Wilcox 52358d6ea30SMatthew Wilcox xa_erase(xa, 0); 52458d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 52558d6ea30SMatthew Wilcox } 52658d6ea30SMatthew Wilcox } 5274f06d630SMatthew Wilcox 5284f06d630SMatthew Wilcox for (i = 0; i < 20; i++) { 5294f06d630SMatthew Wilcox check_multi_store_1(xa, 200, i); 5304f06d630SMatthew Wilcox check_multi_store_1(xa, 0, i); 5314f06d630SMatthew Wilcox check_multi_store_1(xa, (1UL << i) + 1, i); 5324f06d630SMatthew Wilcox } 5334f06d630SMatthew Wilcox check_multi_store_2(xa, 4095, 9); 53458d6ea30SMatthew Wilcox #endif 53558d6ea30SMatthew Wilcox } 53658d6ea30SMatthew Wilcox 537371c752dSMatthew Wilcox static DEFINE_XARRAY_ALLOC(xa0); 538371c752dSMatthew Wilcox 539371c752dSMatthew Wilcox static noinline void check_xa_alloc(void) 540371c752dSMatthew Wilcox { 541371c752dSMatthew Wilcox int i; 542371c752dSMatthew Wilcox u32 id; 543371c752dSMatthew Wilcox 544371c752dSMatthew Wilcox /* An empty array should assign 0 to the first alloc */ 545371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 546371c752dSMatthew Wilcox 547371c752dSMatthew Wilcox /* Erasing it should make the array empty again */ 548371c752dSMatthew Wilcox xa_erase_index(&xa0, 0); 549371c752dSMatthew Wilcox XA_BUG_ON(&xa0, !xa_empty(&xa0)); 550371c752dSMatthew Wilcox 551371c752dSMatthew Wilcox /* And it should assign 0 again */ 552371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 553371c752dSMatthew Wilcox 554371c752dSMatthew Wilcox /* The next assigned ID should be 1 */ 555371c752dSMatthew Wilcox xa_alloc_index(&xa0, 1, GFP_KERNEL); 556371c752dSMatthew Wilcox xa_erase_index(&xa0, 1); 557371c752dSMatthew Wilcox 558371c752dSMatthew Wilcox /* Storing a value should mark it used */ 559371c752dSMatthew Wilcox xa_store_index(&xa0, 1, GFP_KERNEL); 560371c752dSMatthew Wilcox xa_alloc_index(&xa0, 2, GFP_KERNEL); 561371c752dSMatthew Wilcox 562371c752dSMatthew Wilcox /* If we then erase 0, it should be free */ 563371c752dSMatthew Wilcox xa_erase_index(&xa0, 0); 564371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 565371c752dSMatthew Wilcox 566371c752dSMatthew Wilcox xa_erase_index(&xa0, 1); 567371c752dSMatthew Wilcox xa_erase_index(&xa0, 2); 568371c752dSMatthew Wilcox 569371c752dSMatthew Wilcox for (i = 1; i < 5000; i++) { 570371c752dSMatthew Wilcox xa_alloc_index(&xa0, i, GFP_KERNEL); 571371c752dSMatthew Wilcox } 572371c752dSMatthew Wilcox 573371c752dSMatthew Wilcox xa_destroy(&xa0); 574371c752dSMatthew Wilcox 575371c752dSMatthew Wilcox id = 0xfffffffeU; 576371c752dSMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), 577371c752dSMatthew Wilcox GFP_KERNEL) != 0); 578371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xfffffffeU); 579371c752dSMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), 580371c752dSMatthew Wilcox GFP_KERNEL) != 0); 581371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xffffffffU); 582371c752dSMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), 583371c752dSMatthew Wilcox GFP_KERNEL) != -ENOSPC); 584371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xffffffffU); 585371c752dSMatthew Wilcox xa_destroy(&xa0); 586371c752dSMatthew Wilcox } 587371c752dSMatthew Wilcox 5884e99d4e9SMatthew Wilcox static noinline void __check_store_iter(struct xarray *xa, unsigned long start, 5894e99d4e9SMatthew Wilcox unsigned int order, unsigned int present) 5904e99d4e9SMatthew Wilcox { 5914e99d4e9SMatthew Wilcox XA_STATE_ORDER(xas, xa, start, order); 5924e99d4e9SMatthew Wilcox void *entry; 5934e99d4e9SMatthew Wilcox unsigned int count = 0; 5944e99d4e9SMatthew Wilcox 5954e99d4e9SMatthew Wilcox retry: 5964e99d4e9SMatthew Wilcox xas_lock(&xas); 5974e99d4e9SMatthew Wilcox xas_for_each_conflict(&xas, entry) { 5984e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_is_value(entry)); 5994e99d4e9SMatthew Wilcox XA_BUG_ON(xa, entry < xa_mk_value(start)); 6004e99d4e9SMatthew Wilcox XA_BUG_ON(xa, entry > xa_mk_value(start + (1UL << order) - 1)); 6014e99d4e9SMatthew Wilcox count++; 6024e99d4e9SMatthew Wilcox } 6034e99d4e9SMatthew Wilcox xas_store(&xas, xa_mk_value(start)); 6044e99d4e9SMatthew Wilcox xas_unlock(&xas); 6054e99d4e9SMatthew Wilcox if (xas_nomem(&xas, GFP_KERNEL)) { 6064e99d4e9SMatthew Wilcox count = 0; 6074e99d4e9SMatthew Wilcox goto retry; 6084e99d4e9SMatthew Wilcox } 6094e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 6104e99d4e9SMatthew Wilcox XA_BUG_ON(xa, count != present); 6114e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_value(start)); 6124e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) != 6134e99d4e9SMatthew Wilcox xa_mk_value(start)); 6144e99d4e9SMatthew Wilcox xa_erase_index(xa, start); 6154e99d4e9SMatthew Wilcox } 6164e99d4e9SMatthew Wilcox 6174e99d4e9SMatthew Wilcox static noinline void check_store_iter(struct xarray *xa) 6184e99d4e9SMatthew Wilcox { 6194e99d4e9SMatthew Wilcox unsigned int i, j; 6204e99d4e9SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; 6214e99d4e9SMatthew Wilcox 6224e99d4e9SMatthew Wilcox for (i = 0; i < max_order; i++) { 6234e99d4e9SMatthew Wilcox unsigned int min = 1 << i; 6244e99d4e9SMatthew Wilcox unsigned int max = (2 << i) - 1; 6254e99d4e9SMatthew Wilcox __check_store_iter(xa, 0, i, 0); 6264e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6274e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 0); 6284e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6294e99d4e9SMatthew Wilcox 6304e99d4e9SMatthew Wilcox xa_store_index(xa, min, GFP_KERNEL); 6314e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 1); 6324e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6334e99d4e9SMatthew Wilcox xa_store_index(xa, max, GFP_KERNEL); 6344e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 1); 6354e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6364e99d4e9SMatthew Wilcox 6374e99d4e9SMatthew Wilcox for (j = 0; j < min; j++) 6384e99d4e9SMatthew Wilcox xa_store_index(xa, j, GFP_KERNEL); 6394e99d4e9SMatthew Wilcox __check_store_iter(xa, 0, i, min); 6404e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6414e99d4e9SMatthew Wilcox for (j = 0; j < min; j++) 6424e99d4e9SMatthew Wilcox xa_store_index(xa, min + j, GFP_KERNEL); 6434e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, min); 6444e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6454e99d4e9SMatthew Wilcox } 6464e99d4e9SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 6474e99d4e9SMatthew Wilcox xa_store_index(xa, 63, GFP_KERNEL); 6484e99d4e9SMatthew Wilcox xa_store_index(xa, 65, GFP_KERNEL); 6494e99d4e9SMatthew Wilcox __check_store_iter(xa, 64, 2, 1); 6504e99d4e9SMatthew Wilcox xa_erase_index(xa, 63); 6514e99d4e9SMatthew Wilcox #endif 6524e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6534e99d4e9SMatthew Wilcox } 6544e99d4e9SMatthew Wilcox 655b803b428SMatthew Wilcox static noinline void check_multi_find(struct xarray *xa) 656b803b428SMatthew Wilcox { 657b803b428SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 658b803b428SMatthew Wilcox unsigned long index; 659b803b428SMatthew Wilcox 660b803b428SMatthew Wilcox xa_store_order(xa, 12, 2, xa_mk_value(12), GFP_KERNEL); 661b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 16, GFP_KERNEL) != NULL); 662b803b428SMatthew Wilcox 663b803b428SMatthew Wilcox index = 0; 664b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != 665b803b428SMatthew Wilcox xa_mk_value(12)); 666b803b428SMatthew Wilcox XA_BUG_ON(xa, index != 12); 667b803b428SMatthew Wilcox index = 13; 668b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != 669b803b428SMatthew Wilcox xa_mk_value(12)); 670b803b428SMatthew Wilcox XA_BUG_ON(xa, (index < 12) || (index >= 16)); 671b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) != 672b803b428SMatthew Wilcox xa_mk_value(16)); 673b803b428SMatthew Wilcox XA_BUG_ON(xa, index != 16); 674b803b428SMatthew Wilcox 675b803b428SMatthew Wilcox xa_erase_index(xa, 12); 676b803b428SMatthew Wilcox xa_erase_index(xa, 16); 677b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 678b803b428SMatthew Wilcox #endif 679b803b428SMatthew Wilcox } 680b803b428SMatthew Wilcox 681b803b428SMatthew Wilcox static noinline void check_multi_find_2(struct xarray *xa) 682b803b428SMatthew Wilcox { 683b803b428SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1; 684b803b428SMatthew Wilcox unsigned int i, j; 685b803b428SMatthew Wilcox void *entry; 686b803b428SMatthew Wilcox 687b803b428SMatthew Wilcox for (i = 0; i < max_order; i++) { 688b803b428SMatthew Wilcox unsigned long index = 1UL << i; 689b803b428SMatthew Wilcox for (j = 0; j < index; j++) { 690b803b428SMatthew Wilcox XA_STATE(xas, xa, j + index); 691b803b428SMatthew Wilcox xa_store_index(xa, index - 1, GFP_KERNEL); 692b803b428SMatthew Wilcox xa_store_order(xa, index, i, xa_mk_value(index), 693b803b428SMatthew Wilcox GFP_KERNEL); 694b803b428SMatthew Wilcox rcu_read_lock(); 695b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 696b803b428SMatthew Wilcox xa_erase_index(xa, index); 697b803b428SMatthew Wilcox } 698b803b428SMatthew Wilcox rcu_read_unlock(); 699b803b428SMatthew Wilcox xa_erase_index(xa, index - 1); 700b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 701b803b428SMatthew Wilcox } 702b803b428SMatthew Wilcox } 703b803b428SMatthew Wilcox } 704b803b428SMatthew Wilcox 7058229706eSMatthew Wilcox static noinline void check_find_1(struct xarray *xa) 706b803b428SMatthew Wilcox { 707b803b428SMatthew Wilcox unsigned long i, j, k; 708b803b428SMatthew Wilcox 709b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 710b803b428SMatthew Wilcox 711b803b428SMatthew Wilcox /* 712b803b428SMatthew Wilcox * Check xa_find with all pairs between 0 and 99 inclusive, 713b803b428SMatthew Wilcox * starting at every index between 0 and 99 714b803b428SMatthew Wilcox */ 715b803b428SMatthew Wilcox for (i = 0; i < 100; i++) { 716b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 717b803b428SMatthew Wilcox xa_set_mark(xa, i, XA_MARK_0); 718b803b428SMatthew Wilcox for (j = 0; j < i; j++) { 719b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) != 720b803b428SMatthew Wilcox NULL); 721b803b428SMatthew Wilcox xa_set_mark(xa, j, XA_MARK_0); 722b803b428SMatthew Wilcox for (k = 0; k < 100; k++) { 723b803b428SMatthew Wilcox unsigned long index = k; 724b803b428SMatthew Wilcox void *entry = xa_find(xa, &index, ULONG_MAX, 725b803b428SMatthew Wilcox XA_PRESENT); 726b803b428SMatthew Wilcox if (k <= j) 727b803b428SMatthew Wilcox XA_BUG_ON(xa, index != j); 728b803b428SMatthew Wilcox else if (k <= i) 729b803b428SMatthew Wilcox XA_BUG_ON(xa, index != i); 730b803b428SMatthew Wilcox else 731b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 732b803b428SMatthew Wilcox 733b803b428SMatthew Wilcox index = k; 734b803b428SMatthew Wilcox entry = xa_find(xa, &index, ULONG_MAX, 735b803b428SMatthew Wilcox XA_MARK_0); 736b803b428SMatthew Wilcox if (k <= j) 737b803b428SMatthew Wilcox XA_BUG_ON(xa, index != j); 738b803b428SMatthew Wilcox else if (k <= i) 739b803b428SMatthew Wilcox XA_BUG_ON(xa, index != i); 740b803b428SMatthew Wilcox else 741b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 742b803b428SMatthew Wilcox } 743b803b428SMatthew Wilcox xa_erase_index(xa, j); 744b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0)); 745b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0)); 746b803b428SMatthew Wilcox } 747b803b428SMatthew Wilcox xa_erase_index(xa, i); 748b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0)); 749b803b428SMatthew Wilcox } 750b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 7518229706eSMatthew Wilcox } 7528229706eSMatthew Wilcox 7538229706eSMatthew Wilcox static noinline void check_find_2(struct xarray *xa) 7548229706eSMatthew Wilcox { 7558229706eSMatthew Wilcox void *entry; 7568229706eSMatthew Wilcox unsigned long i, j, index = 0; 7578229706eSMatthew Wilcox 7588229706eSMatthew Wilcox xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 7598229706eSMatthew Wilcox XA_BUG_ON(xa, true); 7608229706eSMatthew Wilcox } 7618229706eSMatthew Wilcox 7628229706eSMatthew Wilcox for (i = 0; i < 1024; i++) { 7638229706eSMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 7648229706eSMatthew Wilcox j = 0; 7658229706eSMatthew Wilcox index = 0; 7668229706eSMatthew Wilcox xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 7678229706eSMatthew Wilcox XA_BUG_ON(xa, xa_mk_value(index) != entry); 7688229706eSMatthew Wilcox XA_BUG_ON(xa, index != j++); 7698229706eSMatthew Wilcox } 7708229706eSMatthew Wilcox } 7718229706eSMatthew Wilcox 7728229706eSMatthew Wilcox xa_destroy(xa); 7738229706eSMatthew Wilcox } 7748229706eSMatthew Wilcox 7758229706eSMatthew Wilcox static noinline void check_find(struct xarray *xa) 7768229706eSMatthew Wilcox { 7778229706eSMatthew Wilcox check_find_1(xa); 7788229706eSMatthew Wilcox check_find_2(xa); 779b803b428SMatthew Wilcox check_multi_find(xa); 780b803b428SMatthew Wilcox check_multi_find_2(xa); 781b803b428SMatthew Wilcox } 782b803b428SMatthew Wilcox 783e21a2955SMatthew Wilcox /* See find_swap_entry() in mm/shmem.c */ 784e21a2955SMatthew Wilcox static noinline unsigned long xa_find_entry(struct xarray *xa, void *item) 785e21a2955SMatthew Wilcox { 786e21a2955SMatthew Wilcox XA_STATE(xas, xa, 0); 787e21a2955SMatthew Wilcox unsigned int checked = 0; 788e21a2955SMatthew Wilcox void *entry; 789e21a2955SMatthew Wilcox 790e21a2955SMatthew Wilcox rcu_read_lock(); 791e21a2955SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 792e21a2955SMatthew Wilcox if (xas_retry(&xas, entry)) 793e21a2955SMatthew Wilcox continue; 794e21a2955SMatthew Wilcox if (entry == item) 795e21a2955SMatthew Wilcox break; 796e21a2955SMatthew Wilcox checked++; 797e21a2955SMatthew Wilcox if ((checked % 4) != 0) 798e21a2955SMatthew Wilcox continue; 799e21a2955SMatthew Wilcox xas_pause(&xas); 800e21a2955SMatthew Wilcox } 801e21a2955SMatthew Wilcox rcu_read_unlock(); 802e21a2955SMatthew Wilcox 803e21a2955SMatthew Wilcox return entry ? xas.xa_index : -1; 804e21a2955SMatthew Wilcox } 805e21a2955SMatthew Wilcox 806e21a2955SMatthew Wilcox static noinline void check_find_entry(struct xarray *xa) 807e21a2955SMatthew Wilcox { 808e21a2955SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 809e21a2955SMatthew Wilcox unsigned int order; 810e21a2955SMatthew Wilcox unsigned long offset, index; 811e21a2955SMatthew Wilcox 812e21a2955SMatthew Wilcox for (order = 0; order < 20; order++) { 813e21a2955SMatthew Wilcox for (offset = 0; offset < (1UL << (order + 3)); 814e21a2955SMatthew Wilcox offset += (1UL << order)) { 815e21a2955SMatthew Wilcox for (index = 0; index < (1UL << (order + 5)); 816e21a2955SMatthew Wilcox index += (1UL << order)) { 817e21a2955SMatthew Wilcox xa_store_order(xa, index, order, 818e21a2955SMatthew Wilcox xa_mk_value(index), GFP_KERNEL); 819e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, index) != 820e21a2955SMatthew Wilcox xa_mk_value(index)); 821e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, 822e21a2955SMatthew Wilcox xa_mk_value(index)) != index); 823e21a2955SMatthew Wilcox } 824e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 825e21a2955SMatthew Wilcox xa_destroy(xa); 826e21a2955SMatthew Wilcox } 827e21a2955SMatthew Wilcox } 828e21a2955SMatthew Wilcox #endif 829e21a2955SMatthew Wilcox 830e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 831e21a2955SMatthew Wilcox xa_store_index(xa, ULONG_MAX, GFP_KERNEL); 832e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 833e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_value(LONG_MAX)) != -1); 834e21a2955SMatthew Wilcox xa_erase_index(xa, ULONG_MAX); 835e21a2955SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 836e21a2955SMatthew Wilcox } 837e21a2955SMatthew Wilcox 83864d3e9a9SMatthew Wilcox static noinline void check_move_small(struct xarray *xa, unsigned long idx) 83964d3e9a9SMatthew Wilcox { 84064d3e9a9SMatthew Wilcox XA_STATE(xas, xa, 0); 84164d3e9a9SMatthew Wilcox unsigned long i; 84264d3e9a9SMatthew Wilcox 84364d3e9a9SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 84464d3e9a9SMatthew Wilcox xa_store_index(xa, idx, GFP_KERNEL); 84564d3e9a9SMatthew Wilcox 84664d3e9a9SMatthew Wilcox rcu_read_lock(); 84764d3e9a9SMatthew Wilcox for (i = 0; i < idx * 4; i++) { 84864d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 84964d3e9a9SMatthew Wilcox if (i <= idx) 85064d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node == XAS_RESTART); 85164d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 85264d3e9a9SMatthew Wilcox if (i == 0 || i == idx) 85364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 85464d3e9a9SMatthew Wilcox else 85564d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 85664d3e9a9SMatthew Wilcox } 85764d3e9a9SMatthew Wilcox xas_next(&xas); 85864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 85964d3e9a9SMatthew Wilcox 86064d3e9a9SMatthew Wilcox do { 86164d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 86264d3e9a9SMatthew Wilcox i--; 86364d3e9a9SMatthew Wilcox if (i <= idx) 86464d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node == XAS_RESTART); 86564d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 86664d3e9a9SMatthew Wilcox if (i == 0 || i == idx) 86764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 86864d3e9a9SMatthew Wilcox else 86964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 87064d3e9a9SMatthew Wilcox } while (i > 0); 87164d3e9a9SMatthew Wilcox 87264d3e9a9SMatthew Wilcox xas_set(&xas, ULONG_MAX); 87364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_next(&xas) != NULL); 87464d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 87564d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0)); 87664d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != 0); 87764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 87864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 87964d3e9a9SMatthew Wilcox rcu_read_unlock(); 88064d3e9a9SMatthew Wilcox 88164d3e9a9SMatthew Wilcox xa_erase_index(xa, 0); 88264d3e9a9SMatthew Wilcox xa_erase_index(xa, idx); 88364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 88464d3e9a9SMatthew Wilcox } 88564d3e9a9SMatthew Wilcox 88664d3e9a9SMatthew Wilcox static noinline void check_move(struct xarray *xa) 88764d3e9a9SMatthew Wilcox { 88864d3e9a9SMatthew Wilcox XA_STATE(xas, xa, (1 << 16) - 1); 88964d3e9a9SMatthew Wilcox unsigned long i; 89064d3e9a9SMatthew Wilcox 89164d3e9a9SMatthew Wilcox for (i = 0; i < (1 << 16); i++) 89264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 89364d3e9a9SMatthew Wilcox 89464d3e9a9SMatthew Wilcox rcu_read_lock(); 89564d3e9a9SMatthew Wilcox do { 89664d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 89764d3e9a9SMatthew Wilcox i--; 89864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 89964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 90064d3e9a9SMatthew Wilcox } while (i != 0); 90164d3e9a9SMatthew Wilcox 90264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 90364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 90464d3e9a9SMatthew Wilcox 90564d3e9a9SMatthew Wilcox do { 90664d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 90764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 90864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 90964d3e9a9SMatthew Wilcox i++; 91064d3e9a9SMatthew Wilcox } while (i < (1 << 16)); 91164d3e9a9SMatthew Wilcox rcu_read_unlock(); 91264d3e9a9SMatthew Wilcox 91364d3e9a9SMatthew Wilcox for (i = (1 << 8); i < (1 << 15); i++) 91464d3e9a9SMatthew Wilcox xa_erase_index(xa, i); 91564d3e9a9SMatthew Wilcox 91664d3e9a9SMatthew Wilcox i = xas.xa_index; 91764d3e9a9SMatthew Wilcox 91864d3e9a9SMatthew Wilcox rcu_read_lock(); 91964d3e9a9SMatthew Wilcox do { 92064d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 92164d3e9a9SMatthew Wilcox i--; 92264d3e9a9SMatthew Wilcox if ((i < (1 << 8)) || (i >= (1 << 15))) 92364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 92464d3e9a9SMatthew Wilcox else 92564d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 92664d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 92764d3e9a9SMatthew Wilcox } while (i != 0); 92864d3e9a9SMatthew Wilcox 92964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 93064d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 93164d3e9a9SMatthew Wilcox 93264d3e9a9SMatthew Wilcox do { 93364d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 93464d3e9a9SMatthew Wilcox if ((i < (1 << 8)) || (i >= (1 << 15))) 93564d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 93664d3e9a9SMatthew Wilcox else 93764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 93864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 93964d3e9a9SMatthew Wilcox i++; 94064d3e9a9SMatthew Wilcox } while (i < (1 << 16)); 94164d3e9a9SMatthew Wilcox rcu_read_unlock(); 94264d3e9a9SMatthew Wilcox 94364d3e9a9SMatthew Wilcox xa_destroy(xa); 94464d3e9a9SMatthew Wilcox 94564d3e9a9SMatthew Wilcox for (i = 0; i < 16; i++) 94664d3e9a9SMatthew Wilcox check_move_small(xa, 1UL << i); 94764d3e9a9SMatthew Wilcox 94864d3e9a9SMatthew Wilcox for (i = 2; i < 16; i++) 94964d3e9a9SMatthew Wilcox check_move_small(xa, (1UL << i) - 1); 95064d3e9a9SMatthew Wilcox } 95164d3e9a9SMatthew Wilcox 9522264f513SMatthew Wilcox static noinline void xa_store_many_order(struct xarray *xa, 9532264f513SMatthew Wilcox unsigned long index, unsigned order) 9542264f513SMatthew Wilcox { 9552264f513SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 9562264f513SMatthew Wilcox unsigned int i = 0; 9572264f513SMatthew Wilcox 9582264f513SMatthew Wilcox do { 9592264f513SMatthew Wilcox xas_lock(&xas); 9602264f513SMatthew Wilcox XA_BUG_ON(xa, xas_find_conflict(&xas)); 9612264f513SMatthew Wilcox xas_create_range(&xas); 9622264f513SMatthew Wilcox if (xas_error(&xas)) 9632264f513SMatthew Wilcox goto unlock; 9642264f513SMatthew Wilcox for (i = 0; i < (1U << order); i++) { 9652264f513SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(index + i))); 9662264f513SMatthew Wilcox xas_next(&xas); 9672264f513SMatthew Wilcox } 9682264f513SMatthew Wilcox unlock: 9692264f513SMatthew Wilcox xas_unlock(&xas); 9702264f513SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 9712264f513SMatthew Wilcox 9722264f513SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 9732264f513SMatthew Wilcox } 9742264f513SMatthew Wilcox 9752264f513SMatthew Wilcox static noinline void check_create_range_1(struct xarray *xa, 9762264f513SMatthew Wilcox unsigned long index, unsigned order) 9772264f513SMatthew Wilcox { 9782264f513SMatthew Wilcox unsigned long i; 9792264f513SMatthew Wilcox 9802264f513SMatthew Wilcox xa_store_many_order(xa, index, order); 9812264f513SMatthew Wilcox for (i = index; i < index + (1UL << order); i++) 9822264f513SMatthew Wilcox xa_erase_index(xa, i); 9832264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 9842264f513SMatthew Wilcox } 9852264f513SMatthew Wilcox 9862264f513SMatthew Wilcox static noinline void check_create_range_2(struct xarray *xa, unsigned order) 9872264f513SMatthew Wilcox { 9882264f513SMatthew Wilcox unsigned long i; 9892264f513SMatthew Wilcox unsigned long nr = 1UL << order; 9902264f513SMatthew Wilcox 9912264f513SMatthew Wilcox for (i = 0; i < nr * nr; i += nr) 9922264f513SMatthew Wilcox xa_store_many_order(xa, i, order); 9932264f513SMatthew Wilcox for (i = 0; i < nr * nr; i++) 9942264f513SMatthew Wilcox xa_erase_index(xa, i); 9952264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 9962264f513SMatthew Wilcox } 9972264f513SMatthew Wilcox 9982264f513SMatthew Wilcox static noinline void check_create_range_3(void) 9992264f513SMatthew Wilcox { 10002264f513SMatthew Wilcox XA_STATE(xas, NULL, 0); 10012264f513SMatthew Wilcox xas_set_err(&xas, -EEXIST); 10022264f513SMatthew Wilcox xas_create_range(&xas); 10032264f513SMatthew Wilcox XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST); 10042264f513SMatthew Wilcox } 10052264f513SMatthew Wilcox 10062264f513SMatthew Wilcox static noinline void check_create_range_4(struct xarray *xa, 10072264f513SMatthew Wilcox unsigned long index, unsigned order) 10082264f513SMatthew Wilcox { 10092264f513SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 10102264f513SMatthew Wilcox unsigned long base = xas.xa_index; 10112264f513SMatthew Wilcox unsigned long i = 0; 10122264f513SMatthew Wilcox 10132264f513SMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 10142264f513SMatthew Wilcox do { 10152264f513SMatthew Wilcox xas_lock(&xas); 10162264f513SMatthew Wilcox xas_create_range(&xas); 10172264f513SMatthew Wilcox if (xas_error(&xas)) 10182264f513SMatthew Wilcox goto unlock; 10192264f513SMatthew Wilcox for (i = 0; i < (1UL << order); i++) { 10202264f513SMatthew Wilcox void *old = xas_store(&xas, xa_mk_value(base + i)); 10212264f513SMatthew Wilcox if (xas.xa_index == index) 10222264f513SMatthew Wilcox XA_BUG_ON(xa, old != xa_mk_value(base + i)); 10232264f513SMatthew Wilcox else 10242264f513SMatthew Wilcox XA_BUG_ON(xa, old != NULL); 10252264f513SMatthew Wilcox xas_next(&xas); 10262264f513SMatthew Wilcox } 10272264f513SMatthew Wilcox unlock: 10282264f513SMatthew Wilcox xas_unlock(&xas); 10292264f513SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 10302264f513SMatthew Wilcox 10312264f513SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 10322264f513SMatthew Wilcox 10332264f513SMatthew Wilcox for (i = base; i < base + (1UL << order); i++) 10342264f513SMatthew Wilcox xa_erase_index(xa, i); 10352264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 10362264f513SMatthew Wilcox } 10372264f513SMatthew Wilcox 10382264f513SMatthew Wilcox static noinline void check_create_range(struct xarray *xa) 10392264f513SMatthew Wilcox { 10402264f513SMatthew Wilcox unsigned int order; 10412264f513SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1; 10422264f513SMatthew Wilcox 10432264f513SMatthew Wilcox for (order = 0; order < max_order; order++) { 10442264f513SMatthew Wilcox check_create_range_1(xa, 0, order); 10452264f513SMatthew Wilcox check_create_range_1(xa, 1U << order, order); 10462264f513SMatthew Wilcox check_create_range_1(xa, 2U << order, order); 10472264f513SMatthew Wilcox check_create_range_1(xa, 3U << order, order); 10482264f513SMatthew Wilcox check_create_range_1(xa, 1U << 24, order); 10492264f513SMatthew Wilcox if (order < 10) 10502264f513SMatthew Wilcox check_create_range_2(xa, order); 10512264f513SMatthew Wilcox 10522264f513SMatthew Wilcox check_create_range_4(xa, 0, order); 10532264f513SMatthew Wilcox check_create_range_4(xa, 1U << order, order); 10542264f513SMatthew Wilcox check_create_range_4(xa, 2U << order, order); 10552264f513SMatthew Wilcox check_create_range_4(xa, 3U << order, order); 10562264f513SMatthew Wilcox check_create_range_4(xa, 1U << 24, order); 10572264f513SMatthew Wilcox 10582264f513SMatthew Wilcox check_create_range_4(xa, 1, order); 10592264f513SMatthew Wilcox check_create_range_4(xa, (1U << order) + 1, order); 10602264f513SMatthew Wilcox check_create_range_4(xa, (2U << order) + 1, order); 10612264f513SMatthew Wilcox check_create_range_4(xa, (2U << order) - 1, order); 10622264f513SMatthew Wilcox check_create_range_4(xa, (3U << order) + 1, order); 10632264f513SMatthew Wilcox check_create_range_4(xa, (3U << order) - 1, order); 10642264f513SMatthew Wilcox check_create_range_4(xa, (1U << 24) + 1, order); 10652264f513SMatthew Wilcox } 10662264f513SMatthew Wilcox 10672264f513SMatthew Wilcox check_create_range_3(); 10682264f513SMatthew Wilcox } 10692264f513SMatthew Wilcox 10700e9446c3SMatthew Wilcox static noinline void __check_store_range(struct xarray *xa, unsigned long first, 10710e9446c3SMatthew Wilcox unsigned long last) 10720e9446c3SMatthew Wilcox { 10730e9446c3SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 10740e9446c3SMatthew Wilcox xa_store_range(xa, first, last, xa_mk_value(first), GFP_KERNEL); 10750e9446c3SMatthew Wilcox 10760e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_value(first)); 10770e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_value(first)); 10780e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL); 10790e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL); 10800e9446c3SMatthew Wilcox 10810e9446c3SMatthew Wilcox xa_store_range(xa, first, last, NULL, GFP_KERNEL); 10820e9446c3SMatthew Wilcox #endif 10830e9446c3SMatthew Wilcox 10840e9446c3SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 10850e9446c3SMatthew Wilcox } 10860e9446c3SMatthew Wilcox 10870e9446c3SMatthew Wilcox static noinline void check_store_range(struct xarray *xa) 10880e9446c3SMatthew Wilcox { 10890e9446c3SMatthew Wilcox unsigned long i, j; 10900e9446c3SMatthew Wilcox 10910e9446c3SMatthew Wilcox for (i = 0; i < 128; i++) { 10920e9446c3SMatthew Wilcox for (j = i; j < 128; j++) { 10930e9446c3SMatthew Wilcox __check_store_range(xa, i, j); 10940e9446c3SMatthew Wilcox __check_store_range(xa, 128 + i, 128 + j); 10950e9446c3SMatthew Wilcox __check_store_range(xa, 4095 + i, 4095 + j); 10960e9446c3SMatthew Wilcox __check_store_range(xa, 4096 + i, 4096 + j); 10970e9446c3SMatthew Wilcox __check_store_range(xa, 123456 + i, 123456 + j); 10980e9446c3SMatthew Wilcox __check_store_range(xa, UINT_MAX + i, UINT_MAX + j); 10990e9446c3SMatthew Wilcox } 11000e9446c3SMatthew Wilcox } 11010e9446c3SMatthew Wilcox } 11020e9446c3SMatthew Wilcox 1103a97e7904SMatthew Wilcox static LIST_HEAD(shadow_nodes); 1104a97e7904SMatthew Wilcox 1105a97e7904SMatthew Wilcox static void test_update_node(struct xa_node *node) 1106a97e7904SMatthew Wilcox { 1107a97e7904SMatthew Wilcox if (node->count && node->count == node->nr_values) { 1108a97e7904SMatthew Wilcox if (list_empty(&node->private_list)) 1109a97e7904SMatthew Wilcox list_add(&shadow_nodes, &node->private_list); 1110a97e7904SMatthew Wilcox } else { 1111a97e7904SMatthew Wilcox if (!list_empty(&node->private_list)) 1112a97e7904SMatthew Wilcox list_del_init(&node->private_list); 1113a97e7904SMatthew Wilcox } 1114a97e7904SMatthew Wilcox } 1115a97e7904SMatthew Wilcox 1116a97e7904SMatthew Wilcox static noinline void shadow_remove(struct xarray *xa) 1117a97e7904SMatthew Wilcox { 1118a97e7904SMatthew Wilcox struct xa_node *node; 1119a97e7904SMatthew Wilcox 1120a97e7904SMatthew Wilcox xa_lock(xa); 1121a97e7904SMatthew Wilcox while ((node = list_first_entry_or_null(&shadow_nodes, 1122a97e7904SMatthew Wilcox struct xa_node, private_list))) { 1123a97e7904SMatthew Wilcox XA_STATE(xas, node->array, 0); 1124a97e7904SMatthew Wilcox XA_BUG_ON(xa, node->array != xa); 1125a97e7904SMatthew Wilcox list_del_init(&node->private_list); 1126a97e7904SMatthew Wilcox xas.xa_node = xa_parent_locked(node->array, node); 1127a97e7904SMatthew Wilcox xas.xa_offset = node->offset; 1128a97e7904SMatthew Wilcox xas.xa_shift = node->shift + XA_CHUNK_SHIFT; 1129a97e7904SMatthew Wilcox xas_set_update(&xas, test_update_node); 1130a97e7904SMatthew Wilcox xas_store(&xas, NULL); 1131a97e7904SMatthew Wilcox } 1132a97e7904SMatthew Wilcox xa_unlock(xa); 1133a97e7904SMatthew Wilcox } 1134a97e7904SMatthew Wilcox 1135a97e7904SMatthew Wilcox static noinline void check_workingset(struct xarray *xa, unsigned long index) 1136a97e7904SMatthew Wilcox { 1137a97e7904SMatthew Wilcox XA_STATE(xas, xa, index); 1138a97e7904SMatthew Wilcox xas_set_update(&xas, test_update_node); 1139a97e7904SMatthew Wilcox 1140a97e7904SMatthew Wilcox do { 1141a97e7904SMatthew Wilcox xas_lock(&xas); 1142a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(0)); 1143a97e7904SMatthew Wilcox xas_next(&xas); 1144a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(1)); 1145a97e7904SMatthew Wilcox xas_unlock(&xas); 1146a97e7904SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 1147a97e7904SMatthew Wilcox 1148a97e7904SMatthew Wilcox XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1149a97e7904SMatthew Wilcox 1150a97e7904SMatthew Wilcox xas_lock(&xas); 1151a97e7904SMatthew Wilcox xas_next(&xas); 1152a97e7904SMatthew Wilcox xas_store(&xas, &xas); 1153a97e7904SMatthew Wilcox XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1154a97e7904SMatthew Wilcox 1155a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(2)); 1156a97e7904SMatthew Wilcox xas_unlock(&xas); 1157a97e7904SMatthew Wilcox XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1158a97e7904SMatthew Wilcox 1159a97e7904SMatthew Wilcox shadow_remove(xa); 1160a97e7904SMatthew Wilcox XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1161a97e7904SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1162a97e7904SMatthew Wilcox } 1163a97e7904SMatthew Wilcox 1164d6427f81SMatthew Wilcox /* 1165d6427f81SMatthew Wilcox * Check that the pointer / value / sibling entries are accounted the 1166d6427f81SMatthew Wilcox * way we expect them to be. 1167d6427f81SMatthew Wilcox */ 1168d6427f81SMatthew Wilcox static noinline void check_account(struct xarray *xa) 1169d6427f81SMatthew Wilcox { 1170d6427f81SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 1171d6427f81SMatthew Wilcox unsigned int order; 1172d6427f81SMatthew Wilcox 1173d6427f81SMatthew Wilcox for (order = 1; order < 12; order++) { 1174d6427f81SMatthew Wilcox XA_STATE(xas, xa, 1 << order); 1175d6427f81SMatthew Wilcox 1176d6427f81SMatthew Wilcox xa_store_order(xa, 0, order, xa, GFP_KERNEL); 1177d6427f81SMatthew Wilcox xas_load(&xas); 1178d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count == 0); 1179d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count > (1 << order)); 1180d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1181d6427f81SMatthew Wilcox 1182d6427f81SMatthew Wilcox xa_store_order(xa, 1 << order, order, xa_mk_value(1 << order), 1183d6427f81SMatthew Wilcox GFP_KERNEL); 1184d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2); 1185d6427f81SMatthew Wilcox 1186d6427f81SMatthew Wilcox xa_erase(xa, 1 << order); 1187d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1188d6427f81SMatthew Wilcox 1189d6427f81SMatthew Wilcox xa_erase(xa, 0); 1190d6427f81SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1191d6427f81SMatthew Wilcox } 1192d6427f81SMatthew Wilcox #endif 1193d6427f81SMatthew Wilcox } 1194d6427f81SMatthew Wilcox 1195687149fcSMatthew Wilcox static noinline void check_destroy(struct xarray *xa) 1196687149fcSMatthew Wilcox { 1197687149fcSMatthew Wilcox unsigned long index; 1198687149fcSMatthew Wilcox 1199687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1200687149fcSMatthew Wilcox 1201687149fcSMatthew Wilcox /* Destroying an empty array is a no-op */ 1202687149fcSMatthew Wilcox xa_destroy(xa); 1203687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1204687149fcSMatthew Wilcox 1205687149fcSMatthew Wilcox /* Destroying an array with a single entry */ 1206687149fcSMatthew Wilcox for (index = 0; index < 1000; index++) { 1207687149fcSMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 1208687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1209687149fcSMatthew Wilcox xa_destroy(xa); 1210687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1211687149fcSMatthew Wilcox } 1212687149fcSMatthew Wilcox 1213687149fcSMatthew Wilcox /* Destroying an array with a single entry at ULONG_MAX */ 1214687149fcSMatthew Wilcox xa_store(xa, ULONG_MAX, xa, GFP_KERNEL); 1215687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1216687149fcSMatthew Wilcox xa_destroy(xa); 1217687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1218687149fcSMatthew Wilcox 1219687149fcSMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 1220687149fcSMatthew Wilcox /* Destroying an array with a multi-index entry */ 1221687149fcSMatthew Wilcox xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL); 1222687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1223687149fcSMatthew Wilcox xa_destroy(xa); 1224687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1225687149fcSMatthew Wilcox #endif 1226687149fcSMatthew Wilcox } 1227687149fcSMatthew Wilcox 122858d6ea30SMatthew Wilcox static DEFINE_XARRAY(array); 1229ad3d6c72SMatthew Wilcox 1230ad3d6c72SMatthew Wilcox static int xarray_checks(void) 1231ad3d6c72SMatthew Wilcox { 123258d6ea30SMatthew Wilcox check_xa_err(&array); 1233b803b428SMatthew Wilcox check_xas_retry(&array); 1234ad3d6c72SMatthew Wilcox check_xa_load(&array); 12359b89a035SMatthew Wilcox check_xa_mark(&array); 123658d6ea30SMatthew Wilcox check_xa_shrink(&array); 1237b803b428SMatthew Wilcox check_xas_erase(&array); 123841aec91fSMatthew Wilcox check_cmpxchg(&array); 12399f14d4f1SMatthew Wilcox check_reserve(&array); 124058d6ea30SMatthew Wilcox check_multi_store(&array); 1241371c752dSMatthew Wilcox check_xa_alloc(); 1242b803b428SMatthew Wilcox check_find(&array); 1243e21a2955SMatthew Wilcox check_find_entry(&array); 1244d6427f81SMatthew Wilcox check_account(&array); 1245687149fcSMatthew Wilcox check_destroy(&array); 124664d3e9a9SMatthew Wilcox check_move(&array); 12472264f513SMatthew Wilcox check_create_range(&array); 12480e9446c3SMatthew Wilcox check_store_range(&array); 12494e99d4e9SMatthew Wilcox check_store_iter(&array); 1250ad3d6c72SMatthew Wilcox 1251a97e7904SMatthew Wilcox check_workingset(&array, 0); 1252a97e7904SMatthew Wilcox check_workingset(&array, 64); 1253a97e7904SMatthew Wilcox check_workingset(&array, 4096); 1254a97e7904SMatthew Wilcox 1255ad3d6c72SMatthew Wilcox printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); 1256ad3d6c72SMatthew Wilcox return (tests_run == tests_passed) ? 0 : -EINVAL; 1257ad3d6c72SMatthew Wilcox } 1258ad3d6c72SMatthew Wilcox 1259ad3d6c72SMatthew Wilcox static void xarray_exit(void) 1260ad3d6c72SMatthew Wilcox { 1261ad3d6c72SMatthew Wilcox } 1262ad3d6c72SMatthew Wilcox 1263ad3d6c72SMatthew Wilcox module_init(xarray_checks); 1264ad3d6c72SMatthew Wilcox module_exit(xarray_exit); 1265ad3d6c72SMatthew Wilcox MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>"); 1266ad3d6c72SMatthew Wilcox MODULE_LICENSE("GPL"); 1267