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 */ 211fffc9a26SMatthew Wilcox rcu_read_lock(); 21293eb07f7SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) 21393eb07f7SMatthew Wilcox seen++; 214fffc9a26SMatthew Wilcox rcu_read_unlock(); 21593eb07f7SMatthew Wilcox XA_BUG_ON(xa, seen != 2); 21693eb07f7SMatthew Wilcox 21793eb07f7SMatthew Wilcox /* One of which is marked */ 21893eb07f7SMatthew Wilcox xas_set(&xas, 0); 21993eb07f7SMatthew Wilcox seen = 0; 220fffc9a26SMatthew Wilcox rcu_read_lock(); 22193eb07f7SMatthew Wilcox xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) 22293eb07f7SMatthew Wilcox seen++; 223fffc9a26SMatthew Wilcox rcu_read_unlock(); 22493eb07f7SMatthew Wilcox XA_BUG_ON(xa, seen != 1); 22558d6ea30SMatthew Wilcox } 22658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0)); 22758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1)); 22858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2)); 22958d6ea30SMatthew Wilcox xa_erase_index(xa, index); 23058d6ea30SMatthew Wilcox xa_erase_index(xa, next); 23158d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 23258d6ea30SMatthew Wilcox } 23358d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 2349b89a035SMatthew Wilcox } 2359b89a035SMatthew Wilcox 236adb9d9c4SMatthew Wilcox static noinline void check_xa_mark_2(struct xarray *xa) 237adb9d9c4SMatthew Wilcox { 238adb9d9c4SMatthew Wilcox XA_STATE(xas, xa, 0); 239adb9d9c4SMatthew Wilcox unsigned long index; 240adb9d9c4SMatthew Wilcox unsigned int count = 0; 241adb9d9c4SMatthew Wilcox void *entry; 242adb9d9c4SMatthew Wilcox 243adb9d9c4SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 244adb9d9c4SMatthew Wilcox xa_set_mark(xa, 0, XA_MARK_0); 245adb9d9c4SMatthew Wilcox xas_lock(&xas); 246adb9d9c4SMatthew Wilcox xas_load(&xas); 247adb9d9c4SMatthew Wilcox xas_init_marks(&xas); 248adb9d9c4SMatthew Wilcox xas_unlock(&xas); 249adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0); 250adb9d9c4SMatthew Wilcox 251adb9d9c4SMatthew Wilcox for (index = 3500; index < 4500; index++) { 252adb9d9c4SMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 253adb9d9c4SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 254adb9d9c4SMatthew Wilcox } 255adb9d9c4SMatthew Wilcox 256adb9d9c4SMatthew Wilcox xas_reset(&xas); 257adb9d9c4SMatthew Wilcox rcu_read_lock(); 258adb9d9c4SMatthew Wilcox xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) 259adb9d9c4SMatthew Wilcox count++; 260adb9d9c4SMatthew Wilcox rcu_read_unlock(); 261adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, count != 1000); 262adb9d9c4SMatthew Wilcox 263adb9d9c4SMatthew Wilcox xas_lock(&xas); 264adb9d9c4SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 265adb9d9c4SMatthew Wilcox xas_init_marks(&xas); 266adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0)); 267adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0)); 268adb9d9c4SMatthew Wilcox } 269adb9d9c4SMatthew Wilcox xas_unlock(&xas); 270adb9d9c4SMatthew Wilcox 271adb9d9c4SMatthew Wilcox xa_destroy(xa); 272adb9d9c4SMatthew Wilcox } 273adb9d9c4SMatthew Wilcox 2749b89a035SMatthew Wilcox static noinline void check_xa_mark(struct xarray *xa) 2759b89a035SMatthew Wilcox { 2769b89a035SMatthew Wilcox unsigned long index; 2779b89a035SMatthew Wilcox 2789b89a035SMatthew Wilcox for (index = 0; index < 16384; index += 4) 2799b89a035SMatthew Wilcox check_xa_mark_1(xa, index); 280adb9d9c4SMatthew Wilcox 281adb9d9c4SMatthew Wilcox check_xa_mark_2(xa); 2829b89a035SMatthew Wilcox } 2839b89a035SMatthew Wilcox 28458d6ea30SMatthew Wilcox static noinline void check_xa_shrink(struct xarray *xa) 28558d6ea30SMatthew Wilcox { 28658d6ea30SMatthew Wilcox XA_STATE(xas, xa, 1); 28758d6ea30SMatthew Wilcox struct xa_node *node; 28893eb07f7SMatthew Wilcox unsigned int order; 28993eb07f7SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1; 29058d6ea30SMatthew Wilcox 29158d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 29258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL); 29358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL); 29458d6ea30SMatthew Wilcox 29558d6ea30SMatthew Wilcox /* 29658d6ea30SMatthew Wilcox * Check that erasing the entry at 1 shrinks the tree and properly 29758d6ea30SMatthew Wilcox * marks the node as being deleted. 29858d6ea30SMatthew Wilcox */ 29958d6ea30SMatthew Wilcox xas_lock(&xas); 30058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1)); 30158d6ea30SMatthew Wilcox node = xas.xa_node; 30258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0)); 30358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1)); 30458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != NULL); 30558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS); 30658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY); 30758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_load(&xas) != NULL); 30858d6ea30SMatthew Wilcox xas_unlock(&xas); 30958d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 31058d6ea30SMatthew Wilcox xa_erase_index(xa, 0); 31158d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 31293eb07f7SMatthew Wilcox 31393eb07f7SMatthew Wilcox for (order = 0; order < max_order; order++) { 31493eb07f7SMatthew Wilcox unsigned long max = (1UL << order) - 1; 31593eb07f7SMatthew Wilcox xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL); 31693eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0)); 31793eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL); 31893eb07f7SMatthew Wilcox rcu_read_lock(); 31993eb07f7SMatthew Wilcox node = xa_head(xa); 32093eb07f7SMatthew Wilcox rcu_read_unlock(); 32193eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) != 32293eb07f7SMatthew Wilcox NULL); 32393eb07f7SMatthew Wilcox rcu_read_lock(); 32493eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_head(xa) == node); 32593eb07f7SMatthew Wilcox rcu_read_unlock(); 32693eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL); 32793eb07f7SMatthew Wilcox xa_erase_index(xa, ULONG_MAX); 32893eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa->xa_head != node); 32993eb07f7SMatthew Wilcox xa_erase_index(xa, 0); 33093eb07f7SMatthew Wilcox } 33158d6ea30SMatthew Wilcox } 33258d6ea30SMatthew Wilcox 33341aec91fSMatthew Wilcox static noinline void check_cmpxchg(struct xarray *xa) 33441aec91fSMatthew Wilcox { 33541aec91fSMatthew Wilcox void *FIVE = xa_mk_value(5); 33641aec91fSMatthew Wilcox void *SIX = xa_mk_value(6); 33741aec91fSMatthew Wilcox void *LOTS = xa_mk_value(12345678); 33841aec91fSMatthew Wilcox 33941aec91fSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 34041aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL); 34141aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EEXIST); 34241aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS); 34341aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS); 34441aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE); 34541aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL); 34641aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL); 34741aec91fSMatthew Wilcox xa_erase_index(xa, 12345678); 34841aec91fSMatthew Wilcox xa_erase_index(xa, 5); 34941aec91fSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 35041aec91fSMatthew Wilcox } 35141aec91fSMatthew Wilcox 3529f14d4f1SMatthew Wilcox static noinline void check_reserve(struct xarray *xa) 3539f14d4f1SMatthew Wilcox { 3549f14d4f1SMatthew Wilcox void *entry; 3559f14d4f1SMatthew Wilcox unsigned long index = 0; 3569f14d4f1SMatthew Wilcox 3579f14d4f1SMatthew Wilcox /* An array with a reserved entry is not empty */ 3589f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3599f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3609f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 3619f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 12345678)); 3629f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3639f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3649f14d4f1SMatthew Wilcox 3659f14d4f1SMatthew Wilcox /* Releasing a used entry does nothing */ 3669f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3679f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_NOWAIT) != NULL); 3689f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3699f14d4f1SMatthew Wilcox xa_erase_index(xa, 12345678); 3709f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3719f14d4f1SMatthew Wilcox 3729f14d4f1SMatthew Wilcox /* cmpxchg sees a reserved entry as NULL */ 3739f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3749f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, NULL, xa_mk_value(12345678), 3759f14d4f1SMatthew Wilcox GFP_NOWAIT) != NULL); 3769f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3779f14d4f1SMatthew Wilcox xa_erase_index(xa, 12345678); 3789f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3799f14d4f1SMatthew Wilcox 3804c0608f4SMatthew Wilcox /* And so does xa_insert */ 3814c0608f4SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3824c0608f4SMatthew Wilcox XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) != 0); 3834c0608f4SMatthew Wilcox xa_erase_index(xa, 12345678); 3844c0608f4SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3854c0608f4SMatthew Wilcox 3869f14d4f1SMatthew Wilcox /* Can iterate through a reserved entry */ 3879f14d4f1SMatthew Wilcox xa_store_index(xa, 5, GFP_KERNEL); 3889f14d4f1SMatthew Wilcox xa_reserve(xa, 6, GFP_KERNEL); 3899f14d4f1SMatthew Wilcox xa_store_index(xa, 7, GFP_KERNEL); 3909f14d4f1SMatthew Wilcox 3919f14d4f1SMatthew Wilcox xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 3929f14d4f1SMatthew Wilcox XA_BUG_ON(xa, index != 5 && index != 7); 3939f14d4f1SMatthew Wilcox } 3949f14d4f1SMatthew Wilcox xa_destroy(xa); 3959f14d4f1SMatthew Wilcox } 3969f14d4f1SMatthew Wilcox 397b803b428SMatthew Wilcox static noinline void check_xas_erase(struct xarray *xa) 398b803b428SMatthew Wilcox { 399b803b428SMatthew Wilcox XA_STATE(xas, xa, 0); 400b803b428SMatthew Wilcox void *entry; 401b803b428SMatthew Wilcox unsigned long i, j; 402b803b428SMatthew Wilcox 403b803b428SMatthew Wilcox for (i = 0; i < 200; i++) { 404b803b428SMatthew Wilcox for (j = i; j < 2 * i + 17; j++) { 405b803b428SMatthew Wilcox xas_set(&xas, j); 406b803b428SMatthew Wilcox do { 407b803b428SMatthew Wilcox xas_lock(&xas); 408b803b428SMatthew Wilcox xas_store(&xas, xa_mk_value(j)); 409b803b428SMatthew Wilcox xas_unlock(&xas); 410b803b428SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 411b803b428SMatthew Wilcox } 412b803b428SMatthew Wilcox 413b803b428SMatthew Wilcox xas_set(&xas, ULONG_MAX); 414b803b428SMatthew Wilcox do { 415b803b428SMatthew Wilcox xas_lock(&xas); 416b803b428SMatthew Wilcox xas_store(&xas, xa_mk_value(0)); 417b803b428SMatthew Wilcox xas_unlock(&xas); 418b803b428SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 419b803b428SMatthew Wilcox 420b803b428SMatthew Wilcox xas_lock(&xas); 421b803b428SMatthew Wilcox xas_store(&xas, NULL); 422b803b428SMatthew Wilcox 423b803b428SMatthew Wilcox xas_set(&xas, 0); 424b803b428SMatthew Wilcox j = i; 425b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 426b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(j)); 427b803b428SMatthew Wilcox xas_store(&xas, NULL); 428b803b428SMatthew Wilcox j++; 429b803b428SMatthew Wilcox } 430b803b428SMatthew Wilcox xas_unlock(&xas); 431b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 432b803b428SMatthew Wilcox } 433b803b428SMatthew Wilcox } 434b803b428SMatthew Wilcox 4354f06d630SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 4364f06d630SMatthew Wilcox static noinline void check_multi_store_1(struct xarray *xa, unsigned long index, 4374f06d630SMatthew Wilcox unsigned int order) 4384f06d630SMatthew Wilcox { 4394f06d630SMatthew Wilcox XA_STATE(xas, xa, index); 4404f06d630SMatthew Wilcox unsigned long min = index & ~((1UL << order) - 1); 4414f06d630SMatthew Wilcox unsigned long max = min + (1UL << order); 4424f06d630SMatthew Wilcox 4434f06d630SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_value(index), GFP_KERNEL); 4444f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(index)); 4454f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(index)); 4464f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != NULL); 4474f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 4484f06d630SMatthew Wilcox 449fffc9a26SMatthew Wilcox xas_lock(&xas); 4504f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(min)) != xa_mk_value(index)); 451fffc9a26SMatthew Wilcox xas_unlock(&xas); 4524f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_value(min)); 4534f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_value(min)); 4544f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != NULL); 4554f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 4564f06d630SMatthew Wilcox 4574f06d630SMatthew Wilcox xa_erase_index(xa, min); 4584f06d630SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 4594f06d630SMatthew Wilcox } 4604f06d630SMatthew Wilcox 4614f06d630SMatthew Wilcox static noinline void check_multi_store_2(struct xarray *xa, unsigned long index, 4624f06d630SMatthew Wilcox unsigned int order) 4634f06d630SMatthew Wilcox { 4644f06d630SMatthew Wilcox XA_STATE(xas, xa, index); 4654f06d630SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL); 4664f06d630SMatthew Wilcox 467fffc9a26SMatthew Wilcox xas_lock(&xas); 4684f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0)); 4694f06d630SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != index); 4704f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1)); 471fffc9a26SMatthew Wilcox xas_unlock(&xas); 4724f06d630SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 4734f06d630SMatthew Wilcox } 4744f06d630SMatthew Wilcox #endif 4754f06d630SMatthew Wilcox 47658d6ea30SMatthew Wilcox static noinline void check_multi_store(struct xarray *xa) 47758d6ea30SMatthew Wilcox { 47858d6ea30SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 47958d6ea30SMatthew Wilcox unsigned long i, j, k; 48058d6ea30SMatthew Wilcox unsigned int max_order = (sizeof(long) == 4) ? 30 : 60; 48158d6ea30SMatthew Wilcox 48258d6ea30SMatthew Wilcox /* Loading from any position returns the same value */ 48358d6ea30SMatthew Wilcox xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL); 48458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 48558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0)); 48658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != NULL); 48758d6ea30SMatthew Wilcox rcu_read_lock(); 48858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2); 48958d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2); 49058d6ea30SMatthew Wilcox rcu_read_unlock(); 49158d6ea30SMatthew Wilcox 49258d6ea30SMatthew Wilcox /* Storing adjacent to the value does not alter the value */ 49358d6ea30SMatthew Wilcox xa_store(xa, 3, xa, GFP_KERNEL); 49458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 49558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0)); 49658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != NULL); 49758d6ea30SMatthew Wilcox rcu_read_lock(); 49858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3); 49958d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2); 50058d6ea30SMatthew Wilcox rcu_read_unlock(); 50158d6ea30SMatthew Wilcox 50258d6ea30SMatthew Wilcox /* Overwriting multiple indexes works */ 50358d6ea30SMatthew Wilcox xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL); 50458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1)); 50558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1)); 50658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1)); 50758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1)); 50858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 4) != NULL); 50958d6ea30SMatthew Wilcox rcu_read_lock(); 51058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4); 51158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4); 51258d6ea30SMatthew Wilcox rcu_read_unlock(); 51358d6ea30SMatthew Wilcox 51458d6ea30SMatthew Wilcox /* We can erase multiple values with a single store */ 5155404a7f1SMatthew Wilcox xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL); 51658d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 51758d6ea30SMatthew Wilcox 51858d6ea30SMatthew Wilcox /* Even when the first slot is empty but the others aren't */ 51958d6ea30SMatthew Wilcox xa_store_index(xa, 1, GFP_KERNEL); 52058d6ea30SMatthew Wilcox xa_store_index(xa, 2, GFP_KERNEL); 52158d6ea30SMatthew Wilcox xa_store_order(xa, 0, 2, NULL, GFP_KERNEL); 52258d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 52358d6ea30SMatthew Wilcox 52458d6ea30SMatthew Wilcox for (i = 0; i < max_order; i++) { 52558d6ea30SMatthew Wilcox for (j = 0; j < max_order; j++) { 52658d6ea30SMatthew Wilcox xa_store_order(xa, 0, i, xa_mk_value(i), GFP_KERNEL); 52758d6ea30SMatthew Wilcox xa_store_order(xa, 0, j, xa_mk_value(j), GFP_KERNEL); 52858d6ea30SMatthew Wilcox 52958d6ea30SMatthew Wilcox for (k = 0; k < max_order; k++) { 53058d6ea30SMatthew Wilcox void *entry = xa_load(xa, (1UL << k) - 1); 53158d6ea30SMatthew Wilcox if ((i < k) && (j < k)) 53258d6ea30SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 53358d6ea30SMatthew Wilcox else 53458d6ea30SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(j)); 53558d6ea30SMatthew Wilcox } 53658d6ea30SMatthew Wilcox 53758d6ea30SMatthew Wilcox xa_erase(xa, 0); 53858d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 53958d6ea30SMatthew Wilcox } 54058d6ea30SMatthew Wilcox } 5414f06d630SMatthew Wilcox 5424f06d630SMatthew Wilcox for (i = 0; i < 20; i++) { 5434f06d630SMatthew Wilcox check_multi_store_1(xa, 200, i); 5444f06d630SMatthew Wilcox check_multi_store_1(xa, 0, i); 5454f06d630SMatthew Wilcox check_multi_store_1(xa, (1UL << i) + 1, i); 5464f06d630SMatthew Wilcox } 5474f06d630SMatthew Wilcox check_multi_store_2(xa, 4095, 9); 54858d6ea30SMatthew Wilcox #endif 54958d6ea30SMatthew Wilcox } 55058d6ea30SMatthew Wilcox 551371c752dSMatthew Wilcox static DEFINE_XARRAY_ALLOC(xa0); 552371c752dSMatthew Wilcox 553371c752dSMatthew Wilcox static noinline void check_xa_alloc(void) 554371c752dSMatthew Wilcox { 555371c752dSMatthew Wilcox int i; 556371c752dSMatthew Wilcox u32 id; 557371c752dSMatthew Wilcox 558371c752dSMatthew Wilcox /* An empty array should assign 0 to the first alloc */ 559371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 560371c752dSMatthew Wilcox 561371c752dSMatthew Wilcox /* Erasing it should make the array empty again */ 562371c752dSMatthew Wilcox xa_erase_index(&xa0, 0); 563371c752dSMatthew Wilcox XA_BUG_ON(&xa0, !xa_empty(&xa0)); 564371c752dSMatthew Wilcox 565371c752dSMatthew Wilcox /* And it should assign 0 again */ 566371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 567371c752dSMatthew Wilcox 568371c752dSMatthew Wilcox /* The next assigned ID should be 1 */ 569371c752dSMatthew Wilcox xa_alloc_index(&xa0, 1, GFP_KERNEL); 570371c752dSMatthew Wilcox xa_erase_index(&xa0, 1); 571371c752dSMatthew Wilcox 572371c752dSMatthew Wilcox /* Storing a value should mark it used */ 573371c752dSMatthew Wilcox xa_store_index(&xa0, 1, GFP_KERNEL); 574371c752dSMatthew Wilcox xa_alloc_index(&xa0, 2, GFP_KERNEL); 575371c752dSMatthew Wilcox 576371c752dSMatthew Wilcox /* If we then erase 0, it should be free */ 577371c752dSMatthew Wilcox xa_erase_index(&xa0, 0); 578371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 579371c752dSMatthew Wilcox 580371c752dSMatthew Wilcox xa_erase_index(&xa0, 1); 581371c752dSMatthew Wilcox xa_erase_index(&xa0, 2); 582371c752dSMatthew Wilcox 583371c752dSMatthew Wilcox for (i = 1; i < 5000; i++) { 584371c752dSMatthew Wilcox xa_alloc_index(&xa0, i, GFP_KERNEL); 585371c752dSMatthew Wilcox } 586371c752dSMatthew Wilcox 587371c752dSMatthew Wilcox xa_destroy(&xa0); 588371c752dSMatthew Wilcox 589371c752dSMatthew Wilcox id = 0xfffffffeU; 590371c752dSMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), 591371c752dSMatthew Wilcox GFP_KERNEL) != 0); 592371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xfffffffeU); 593371c752dSMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), 594371c752dSMatthew Wilcox GFP_KERNEL) != 0); 595371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xffffffffU); 596371c752dSMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_value(0), 597371c752dSMatthew Wilcox GFP_KERNEL) != -ENOSPC); 598371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xffffffffU); 599371c752dSMatthew Wilcox xa_destroy(&xa0); 600371c752dSMatthew Wilcox } 601371c752dSMatthew Wilcox 6024e99d4e9SMatthew Wilcox static noinline void __check_store_iter(struct xarray *xa, unsigned long start, 6034e99d4e9SMatthew Wilcox unsigned int order, unsigned int present) 6044e99d4e9SMatthew Wilcox { 6054e99d4e9SMatthew Wilcox XA_STATE_ORDER(xas, xa, start, order); 6064e99d4e9SMatthew Wilcox void *entry; 6074e99d4e9SMatthew Wilcox unsigned int count = 0; 6084e99d4e9SMatthew Wilcox 6094e99d4e9SMatthew Wilcox retry: 6104e99d4e9SMatthew Wilcox xas_lock(&xas); 6114e99d4e9SMatthew Wilcox xas_for_each_conflict(&xas, entry) { 6124e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_is_value(entry)); 6134e99d4e9SMatthew Wilcox XA_BUG_ON(xa, entry < xa_mk_value(start)); 6144e99d4e9SMatthew Wilcox XA_BUG_ON(xa, entry > xa_mk_value(start + (1UL << order) - 1)); 6154e99d4e9SMatthew Wilcox count++; 6164e99d4e9SMatthew Wilcox } 6174e99d4e9SMatthew Wilcox xas_store(&xas, xa_mk_value(start)); 6184e99d4e9SMatthew Wilcox xas_unlock(&xas); 6194e99d4e9SMatthew Wilcox if (xas_nomem(&xas, GFP_KERNEL)) { 6204e99d4e9SMatthew Wilcox count = 0; 6214e99d4e9SMatthew Wilcox goto retry; 6224e99d4e9SMatthew Wilcox } 6234e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 6244e99d4e9SMatthew Wilcox XA_BUG_ON(xa, count != present); 6254e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_value(start)); 6264e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) != 6274e99d4e9SMatthew Wilcox xa_mk_value(start)); 6284e99d4e9SMatthew Wilcox xa_erase_index(xa, start); 6294e99d4e9SMatthew Wilcox } 6304e99d4e9SMatthew Wilcox 6314e99d4e9SMatthew Wilcox static noinline void check_store_iter(struct xarray *xa) 6324e99d4e9SMatthew Wilcox { 6334e99d4e9SMatthew Wilcox unsigned int i, j; 6344e99d4e9SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; 6354e99d4e9SMatthew Wilcox 6364e99d4e9SMatthew Wilcox for (i = 0; i < max_order; i++) { 6374e99d4e9SMatthew Wilcox unsigned int min = 1 << i; 6384e99d4e9SMatthew Wilcox unsigned int max = (2 << i) - 1; 6394e99d4e9SMatthew Wilcox __check_store_iter(xa, 0, i, 0); 6404e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6414e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 0); 6424e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6434e99d4e9SMatthew Wilcox 6444e99d4e9SMatthew Wilcox xa_store_index(xa, min, GFP_KERNEL); 6454e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 1); 6464e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6474e99d4e9SMatthew Wilcox xa_store_index(xa, max, GFP_KERNEL); 6484e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 1); 6494e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6504e99d4e9SMatthew Wilcox 6514e99d4e9SMatthew Wilcox for (j = 0; j < min; j++) 6524e99d4e9SMatthew Wilcox xa_store_index(xa, j, GFP_KERNEL); 6534e99d4e9SMatthew Wilcox __check_store_iter(xa, 0, i, min); 6544e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6554e99d4e9SMatthew Wilcox for (j = 0; j < min; j++) 6564e99d4e9SMatthew Wilcox xa_store_index(xa, min + j, GFP_KERNEL); 6574e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, min); 6584e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6594e99d4e9SMatthew Wilcox } 6604e99d4e9SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 6614e99d4e9SMatthew Wilcox xa_store_index(xa, 63, GFP_KERNEL); 6624e99d4e9SMatthew Wilcox xa_store_index(xa, 65, GFP_KERNEL); 6634e99d4e9SMatthew Wilcox __check_store_iter(xa, 64, 2, 1); 6644e99d4e9SMatthew Wilcox xa_erase_index(xa, 63); 6654e99d4e9SMatthew Wilcox #endif 6664e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6674e99d4e9SMatthew Wilcox } 6684e99d4e9SMatthew Wilcox 669b803b428SMatthew Wilcox static noinline void check_multi_find(struct xarray *xa) 670b803b428SMatthew Wilcox { 671b803b428SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 672b803b428SMatthew Wilcox unsigned long index; 673b803b428SMatthew Wilcox 674b803b428SMatthew Wilcox xa_store_order(xa, 12, 2, xa_mk_value(12), GFP_KERNEL); 675b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 16, GFP_KERNEL) != NULL); 676b803b428SMatthew Wilcox 677b803b428SMatthew Wilcox index = 0; 678b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != 679b803b428SMatthew Wilcox xa_mk_value(12)); 680b803b428SMatthew Wilcox XA_BUG_ON(xa, index != 12); 681b803b428SMatthew Wilcox index = 13; 682b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != 683b803b428SMatthew Wilcox xa_mk_value(12)); 684b803b428SMatthew Wilcox XA_BUG_ON(xa, (index < 12) || (index >= 16)); 685b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) != 686b803b428SMatthew Wilcox xa_mk_value(16)); 687b803b428SMatthew Wilcox XA_BUG_ON(xa, index != 16); 688b803b428SMatthew Wilcox 689b803b428SMatthew Wilcox xa_erase_index(xa, 12); 690b803b428SMatthew Wilcox xa_erase_index(xa, 16); 691b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 692b803b428SMatthew Wilcox #endif 693b803b428SMatthew Wilcox } 694b803b428SMatthew Wilcox 695b803b428SMatthew Wilcox static noinline void check_multi_find_2(struct xarray *xa) 696b803b428SMatthew Wilcox { 697b803b428SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1; 698b803b428SMatthew Wilcox unsigned int i, j; 699b803b428SMatthew Wilcox void *entry; 700b803b428SMatthew Wilcox 701b803b428SMatthew Wilcox for (i = 0; i < max_order; i++) { 702b803b428SMatthew Wilcox unsigned long index = 1UL << i; 703b803b428SMatthew Wilcox for (j = 0; j < index; j++) { 704b803b428SMatthew Wilcox XA_STATE(xas, xa, j + index); 705b803b428SMatthew Wilcox xa_store_index(xa, index - 1, GFP_KERNEL); 706b803b428SMatthew Wilcox xa_store_order(xa, index, i, xa_mk_value(index), 707b803b428SMatthew Wilcox GFP_KERNEL); 708b803b428SMatthew Wilcox rcu_read_lock(); 709b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 710b803b428SMatthew Wilcox xa_erase_index(xa, index); 711b803b428SMatthew Wilcox } 712b803b428SMatthew Wilcox rcu_read_unlock(); 713b803b428SMatthew Wilcox xa_erase_index(xa, index - 1); 714b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 715b803b428SMatthew Wilcox } 716b803b428SMatthew Wilcox } 717b803b428SMatthew Wilcox } 718b803b428SMatthew Wilcox 7198229706eSMatthew Wilcox static noinline void check_find_1(struct xarray *xa) 720b803b428SMatthew Wilcox { 721b803b428SMatthew Wilcox unsigned long i, j, k; 722b803b428SMatthew Wilcox 723b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 724b803b428SMatthew Wilcox 725b803b428SMatthew Wilcox /* 726b803b428SMatthew Wilcox * Check xa_find with all pairs between 0 and 99 inclusive, 727b803b428SMatthew Wilcox * starting at every index between 0 and 99 728b803b428SMatthew Wilcox */ 729b803b428SMatthew Wilcox for (i = 0; i < 100; i++) { 730b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 731b803b428SMatthew Wilcox xa_set_mark(xa, i, XA_MARK_0); 732b803b428SMatthew Wilcox for (j = 0; j < i; j++) { 733b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) != 734b803b428SMatthew Wilcox NULL); 735b803b428SMatthew Wilcox xa_set_mark(xa, j, XA_MARK_0); 736b803b428SMatthew Wilcox for (k = 0; k < 100; k++) { 737b803b428SMatthew Wilcox unsigned long index = k; 738b803b428SMatthew Wilcox void *entry = xa_find(xa, &index, ULONG_MAX, 739b803b428SMatthew Wilcox XA_PRESENT); 740b803b428SMatthew Wilcox if (k <= j) 741b803b428SMatthew Wilcox XA_BUG_ON(xa, index != j); 742b803b428SMatthew Wilcox else if (k <= i) 743b803b428SMatthew Wilcox XA_BUG_ON(xa, index != i); 744b803b428SMatthew Wilcox else 745b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 746b803b428SMatthew Wilcox 747b803b428SMatthew Wilcox index = k; 748b803b428SMatthew Wilcox entry = xa_find(xa, &index, ULONG_MAX, 749b803b428SMatthew Wilcox XA_MARK_0); 750b803b428SMatthew Wilcox if (k <= j) 751b803b428SMatthew Wilcox XA_BUG_ON(xa, index != j); 752b803b428SMatthew Wilcox else if (k <= i) 753b803b428SMatthew Wilcox XA_BUG_ON(xa, index != i); 754b803b428SMatthew Wilcox else 755b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 756b803b428SMatthew Wilcox } 757b803b428SMatthew Wilcox xa_erase_index(xa, j); 758b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0)); 759b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0)); 760b803b428SMatthew Wilcox } 761b803b428SMatthew Wilcox xa_erase_index(xa, i); 762b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0)); 763b803b428SMatthew Wilcox } 764b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 7658229706eSMatthew Wilcox } 7668229706eSMatthew Wilcox 7678229706eSMatthew Wilcox static noinline void check_find_2(struct xarray *xa) 7688229706eSMatthew Wilcox { 7698229706eSMatthew Wilcox void *entry; 7708229706eSMatthew Wilcox unsigned long i, j, index = 0; 7718229706eSMatthew Wilcox 7728229706eSMatthew Wilcox xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 7738229706eSMatthew Wilcox XA_BUG_ON(xa, true); 7748229706eSMatthew Wilcox } 7758229706eSMatthew Wilcox 7768229706eSMatthew Wilcox for (i = 0; i < 1024; i++) { 7778229706eSMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 7788229706eSMatthew Wilcox j = 0; 7798229706eSMatthew Wilcox index = 0; 7808229706eSMatthew Wilcox xa_for_each(xa, entry, index, ULONG_MAX, XA_PRESENT) { 7818229706eSMatthew Wilcox XA_BUG_ON(xa, xa_mk_value(index) != entry); 7828229706eSMatthew Wilcox XA_BUG_ON(xa, index != j++); 7838229706eSMatthew Wilcox } 7848229706eSMatthew Wilcox } 7858229706eSMatthew Wilcox 7868229706eSMatthew Wilcox xa_destroy(xa); 7878229706eSMatthew Wilcox } 7888229706eSMatthew Wilcox 7898229706eSMatthew Wilcox static noinline void check_find(struct xarray *xa) 7908229706eSMatthew Wilcox { 7918229706eSMatthew Wilcox check_find_1(xa); 7928229706eSMatthew Wilcox check_find_2(xa); 793b803b428SMatthew Wilcox check_multi_find(xa); 794b803b428SMatthew Wilcox check_multi_find_2(xa); 795b803b428SMatthew Wilcox } 796b803b428SMatthew Wilcox 797e21a2955SMatthew Wilcox /* See find_swap_entry() in mm/shmem.c */ 798e21a2955SMatthew Wilcox static noinline unsigned long xa_find_entry(struct xarray *xa, void *item) 799e21a2955SMatthew Wilcox { 800e21a2955SMatthew Wilcox XA_STATE(xas, xa, 0); 801e21a2955SMatthew Wilcox unsigned int checked = 0; 802e21a2955SMatthew Wilcox void *entry; 803e21a2955SMatthew Wilcox 804e21a2955SMatthew Wilcox rcu_read_lock(); 805e21a2955SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 806e21a2955SMatthew Wilcox if (xas_retry(&xas, entry)) 807e21a2955SMatthew Wilcox continue; 808e21a2955SMatthew Wilcox if (entry == item) 809e21a2955SMatthew Wilcox break; 810e21a2955SMatthew Wilcox checked++; 811e21a2955SMatthew Wilcox if ((checked % 4) != 0) 812e21a2955SMatthew Wilcox continue; 813e21a2955SMatthew Wilcox xas_pause(&xas); 814e21a2955SMatthew Wilcox } 815e21a2955SMatthew Wilcox rcu_read_unlock(); 816e21a2955SMatthew Wilcox 817e21a2955SMatthew Wilcox return entry ? xas.xa_index : -1; 818e21a2955SMatthew Wilcox } 819e21a2955SMatthew Wilcox 820e21a2955SMatthew Wilcox static noinline void check_find_entry(struct xarray *xa) 821e21a2955SMatthew Wilcox { 822e21a2955SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 823e21a2955SMatthew Wilcox unsigned int order; 824e21a2955SMatthew Wilcox unsigned long offset, index; 825e21a2955SMatthew Wilcox 826e21a2955SMatthew Wilcox for (order = 0; order < 20; order++) { 827e21a2955SMatthew Wilcox for (offset = 0; offset < (1UL << (order + 3)); 828e21a2955SMatthew Wilcox offset += (1UL << order)) { 829e21a2955SMatthew Wilcox for (index = 0; index < (1UL << (order + 5)); 830e21a2955SMatthew Wilcox index += (1UL << order)) { 831e21a2955SMatthew Wilcox xa_store_order(xa, index, order, 832e21a2955SMatthew Wilcox xa_mk_value(index), GFP_KERNEL); 833e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, index) != 834e21a2955SMatthew Wilcox xa_mk_value(index)); 835e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, 836e21a2955SMatthew Wilcox xa_mk_value(index)) != index); 837e21a2955SMatthew Wilcox } 838e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 839e21a2955SMatthew Wilcox xa_destroy(xa); 840e21a2955SMatthew Wilcox } 841e21a2955SMatthew Wilcox } 842e21a2955SMatthew Wilcox #endif 843e21a2955SMatthew Wilcox 844e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 845e21a2955SMatthew Wilcox xa_store_index(xa, ULONG_MAX, GFP_KERNEL); 846e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 847e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_value(LONG_MAX)) != -1); 848e21a2955SMatthew Wilcox xa_erase_index(xa, ULONG_MAX); 849e21a2955SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 850e21a2955SMatthew Wilcox } 851e21a2955SMatthew Wilcox 85264d3e9a9SMatthew Wilcox static noinline void check_move_small(struct xarray *xa, unsigned long idx) 85364d3e9a9SMatthew Wilcox { 85464d3e9a9SMatthew Wilcox XA_STATE(xas, xa, 0); 85564d3e9a9SMatthew Wilcox unsigned long i; 85664d3e9a9SMatthew Wilcox 85764d3e9a9SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 85864d3e9a9SMatthew Wilcox xa_store_index(xa, idx, GFP_KERNEL); 85964d3e9a9SMatthew Wilcox 86064d3e9a9SMatthew Wilcox rcu_read_lock(); 86164d3e9a9SMatthew Wilcox for (i = 0; i < idx * 4; i++) { 86264d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 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 } 87164d3e9a9SMatthew Wilcox xas_next(&xas); 87264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 87364d3e9a9SMatthew Wilcox 87464d3e9a9SMatthew Wilcox do { 87564d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 87664d3e9a9SMatthew Wilcox i--; 87764d3e9a9SMatthew Wilcox if (i <= idx) 87864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node == XAS_RESTART); 87964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 88064d3e9a9SMatthew Wilcox if (i == 0 || i == idx) 88164d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 88264d3e9a9SMatthew Wilcox else 88364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 88464d3e9a9SMatthew Wilcox } while (i > 0); 88564d3e9a9SMatthew Wilcox 88664d3e9a9SMatthew Wilcox xas_set(&xas, ULONG_MAX); 88764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_next(&xas) != NULL); 88864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 88964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0)); 89064d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != 0); 89164d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 89264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 89364d3e9a9SMatthew Wilcox rcu_read_unlock(); 89464d3e9a9SMatthew Wilcox 89564d3e9a9SMatthew Wilcox xa_erase_index(xa, 0); 89664d3e9a9SMatthew Wilcox xa_erase_index(xa, idx); 89764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 89864d3e9a9SMatthew Wilcox } 89964d3e9a9SMatthew Wilcox 90064d3e9a9SMatthew Wilcox static noinline void check_move(struct xarray *xa) 90164d3e9a9SMatthew Wilcox { 90264d3e9a9SMatthew Wilcox XA_STATE(xas, xa, (1 << 16) - 1); 90364d3e9a9SMatthew Wilcox unsigned long i; 90464d3e9a9SMatthew Wilcox 90564d3e9a9SMatthew Wilcox for (i = 0; i < (1 << 16); i++) 90664d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 90764d3e9a9SMatthew Wilcox 90864d3e9a9SMatthew Wilcox rcu_read_lock(); 90964d3e9a9SMatthew Wilcox do { 91064d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 91164d3e9a9SMatthew Wilcox i--; 91264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 91364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 91464d3e9a9SMatthew Wilcox } while (i != 0); 91564d3e9a9SMatthew Wilcox 91664d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 91764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 91864d3e9a9SMatthew Wilcox 91964d3e9a9SMatthew Wilcox do { 92064d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 92164d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 92264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 92364d3e9a9SMatthew Wilcox i++; 92464d3e9a9SMatthew Wilcox } while (i < (1 << 16)); 92564d3e9a9SMatthew Wilcox rcu_read_unlock(); 92664d3e9a9SMatthew Wilcox 92764d3e9a9SMatthew Wilcox for (i = (1 << 8); i < (1 << 15); i++) 92864d3e9a9SMatthew Wilcox xa_erase_index(xa, i); 92964d3e9a9SMatthew Wilcox 93064d3e9a9SMatthew Wilcox i = xas.xa_index; 93164d3e9a9SMatthew Wilcox 93264d3e9a9SMatthew Wilcox rcu_read_lock(); 93364d3e9a9SMatthew Wilcox do { 93464d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 93564d3e9a9SMatthew Wilcox i--; 93664d3e9a9SMatthew Wilcox if ((i < (1 << 8)) || (i >= (1 << 15))) 93764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 93864d3e9a9SMatthew Wilcox else 93964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 94064d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 94164d3e9a9SMatthew Wilcox } while (i != 0); 94264d3e9a9SMatthew Wilcox 94364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 94464d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 94564d3e9a9SMatthew Wilcox 94664d3e9a9SMatthew Wilcox do { 94764d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 94864d3e9a9SMatthew Wilcox if ((i < (1 << 8)) || (i >= (1 << 15))) 94964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_value(i)); 95064d3e9a9SMatthew Wilcox else 95164d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 95264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 95364d3e9a9SMatthew Wilcox i++; 95464d3e9a9SMatthew Wilcox } while (i < (1 << 16)); 95564d3e9a9SMatthew Wilcox rcu_read_unlock(); 95664d3e9a9SMatthew Wilcox 95764d3e9a9SMatthew Wilcox xa_destroy(xa); 95864d3e9a9SMatthew Wilcox 95964d3e9a9SMatthew Wilcox for (i = 0; i < 16; i++) 96064d3e9a9SMatthew Wilcox check_move_small(xa, 1UL << i); 96164d3e9a9SMatthew Wilcox 96264d3e9a9SMatthew Wilcox for (i = 2; i < 16; i++) 96364d3e9a9SMatthew Wilcox check_move_small(xa, (1UL << i) - 1); 96464d3e9a9SMatthew Wilcox } 96564d3e9a9SMatthew Wilcox 9662264f513SMatthew Wilcox static noinline void xa_store_many_order(struct xarray *xa, 9672264f513SMatthew Wilcox unsigned long index, unsigned order) 9682264f513SMatthew Wilcox { 9692264f513SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 9702264f513SMatthew Wilcox unsigned int i = 0; 9712264f513SMatthew Wilcox 9722264f513SMatthew Wilcox do { 9732264f513SMatthew Wilcox xas_lock(&xas); 9742264f513SMatthew Wilcox XA_BUG_ON(xa, xas_find_conflict(&xas)); 9752264f513SMatthew Wilcox xas_create_range(&xas); 9762264f513SMatthew Wilcox if (xas_error(&xas)) 9772264f513SMatthew Wilcox goto unlock; 9782264f513SMatthew Wilcox for (i = 0; i < (1U << order); i++) { 9792264f513SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(index + i))); 9802264f513SMatthew Wilcox xas_next(&xas); 9812264f513SMatthew Wilcox } 9822264f513SMatthew Wilcox unlock: 9832264f513SMatthew Wilcox xas_unlock(&xas); 9842264f513SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 9852264f513SMatthew Wilcox 9862264f513SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 9872264f513SMatthew Wilcox } 9882264f513SMatthew Wilcox 9892264f513SMatthew Wilcox static noinline void check_create_range_1(struct xarray *xa, 9902264f513SMatthew Wilcox unsigned long index, unsigned order) 9912264f513SMatthew Wilcox { 9922264f513SMatthew Wilcox unsigned long i; 9932264f513SMatthew Wilcox 9942264f513SMatthew Wilcox xa_store_many_order(xa, index, order); 9952264f513SMatthew Wilcox for (i = index; i < index + (1UL << order); i++) 9962264f513SMatthew Wilcox xa_erase_index(xa, i); 9972264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 9982264f513SMatthew Wilcox } 9992264f513SMatthew Wilcox 10002264f513SMatthew Wilcox static noinline void check_create_range_2(struct xarray *xa, unsigned order) 10012264f513SMatthew Wilcox { 10022264f513SMatthew Wilcox unsigned long i; 10032264f513SMatthew Wilcox unsigned long nr = 1UL << order; 10042264f513SMatthew Wilcox 10052264f513SMatthew Wilcox for (i = 0; i < nr * nr; i += nr) 10062264f513SMatthew Wilcox xa_store_many_order(xa, i, order); 10072264f513SMatthew Wilcox for (i = 0; i < nr * nr; i++) 10082264f513SMatthew Wilcox xa_erase_index(xa, i); 10092264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 10102264f513SMatthew Wilcox } 10112264f513SMatthew Wilcox 10122264f513SMatthew Wilcox static noinline void check_create_range_3(void) 10132264f513SMatthew Wilcox { 10142264f513SMatthew Wilcox XA_STATE(xas, NULL, 0); 10152264f513SMatthew Wilcox xas_set_err(&xas, -EEXIST); 10162264f513SMatthew Wilcox xas_create_range(&xas); 10172264f513SMatthew Wilcox XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST); 10182264f513SMatthew Wilcox } 10192264f513SMatthew Wilcox 10202264f513SMatthew Wilcox static noinline void check_create_range_4(struct xarray *xa, 10212264f513SMatthew Wilcox unsigned long index, unsigned order) 10222264f513SMatthew Wilcox { 10232264f513SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 10242264f513SMatthew Wilcox unsigned long base = xas.xa_index; 10252264f513SMatthew Wilcox unsigned long i = 0; 10262264f513SMatthew Wilcox 10272264f513SMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 10282264f513SMatthew Wilcox do { 10292264f513SMatthew Wilcox xas_lock(&xas); 10302264f513SMatthew Wilcox xas_create_range(&xas); 10312264f513SMatthew Wilcox if (xas_error(&xas)) 10322264f513SMatthew Wilcox goto unlock; 10332264f513SMatthew Wilcox for (i = 0; i < (1UL << order); i++) { 10342264f513SMatthew Wilcox void *old = xas_store(&xas, xa_mk_value(base + i)); 10352264f513SMatthew Wilcox if (xas.xa_index == index) 10362264f513SMatthew Wilcox XA_BUG_ON(xa, old != xa_mk_value(base + i)); 10372264f513SMatthew Wilcox else 10382264f513SMatthew Wilcox XA_BUG_ON(xa, old != NULL); 10392264f513SMatthew Wilcox xas_next(&xas); 10402264f513SMatthew Wilcox } 10412264f513SMatthew Wilcox unlock: 10422264f513SMatthew Wilcox xas_unlock(&xas); 10432264f513SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 10442264f513SMatthew Wilcox 10452264f513SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 10462264f513SMatthew Wilcox 10472264f513SMatthew Wilcox for (i = base; i < base + (1UL << order); i++) 10482264f513SMatthew Wilcox xa_erase_index(xa, i); 10492264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 10502264f513SMatthew Wilcox } 10512264f513SMatthew Wilcox 10522264f513SMatthew Wilcox static noinline void check_create_range(struct xarray *xa) 10532264f513SMatthew Wilcox { 10542264f513SMatthew Wilcox unsigned int order; 10552264f513SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1; 10562264f513SMatthew Wilcox 10572264f513SMatthew Wilcox for (order = 0; order < max_order; order++) { 10582264f513SMatthew Wilcox check_create_range_1(xa, 0, order); 10592264f513SMatthew Wilcox check_create_range_1(xa, 1U << order, order); 10602264f513SMatthew Wilcox check_create_range_1(xa, 2U << order, order); 10612264f513SMatthew Wilcox check_create_range_1(xa, 3U << order, order); 10622264f513SMatthew Wilcox check_create_range_1(xa, 1U << 24, order); 10632264f513SMatthew Wilcox if (order < 10) 10642264f513SMatthew Wilcox check_create_range_2(xa, order); 10652264f513SMatthew Wilcox 10662264f513SMatthew Wilcox check_create_range_4(xa, 0, order); 10672264f513SMatthew Wilcox check_create_range_4(xa, 1U << order, order); 10682264f513SMatthew Wilcox check_create_range_4(xa, 2U << order, order); 10692264f513SMatthew Wilcox check_create_range_4(xa, 3U << order, order); 10702264f513SMatthew Wilcox check_create_range_4(xa, 1U << 24, order); 10712264f513SMatthew Wilcox 10722264f513SMatthew Wilcox check_create_range_4(xa, 1, order); 10732264f513SMatthew Wilcox check_create_range_4(xa, (1U << order) + 1, order); 10742264f513SMatthew Wilcox check_create_range_4(xa, (2U << order) + 1, order); 10752264f513SMatthew Wilcox check_create_range_4(xa, (2U << order) - 1, order); 10762264f513SMatthew Wilcox check_create_range_4(xa, (3U << order) + 1, order); 10772264f513SMatthew Wilcox check_create_range_4(xa, (3U << order) - 1, order); 10782264f513SMatthew Wilcox check_create_range_4(xa, (1U << 24) + 1, order); 10792264f513SMatthew Wilcox } 10802264f513SMatthew Wilcox 10812264f513SMatthew Wilcox check_create_range_3(); 10822264f513SMatthew Wilcox } 10832264f513SMatthew Wilcox 10840e9446c3SMatthew Wilcox static noinline void __check_store_range(struct xarray *xa, unsigned long first, 10850e9446c3SMatthew Wilcox unsigned long last) 10860e9446c3SMatthew Wilcox { 10870e9446c3SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 10880e9446c3SMatthew Wilcox xa_store_range(xa, first, last, xa_mk_value(first), GFP_KERNEL); 10890e9446c3SMatthew Wilcox 10900e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_value(first)); 10910e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_value(first)); 10920e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL); 10930e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL); 10940e9446c3SMatthew Wilcox 10950e9446c3SMatthew Wilcox xa_store_range(xa, first, last, NULL, GFP_KERNEL); 10960e9446c3SMatthew Wilcox #endif 10970e9446c3SMatthew Wilcox 10980e9446c3SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 10990e9446c3SMatthew Wilcox } 11000e9446c3SMatthew Wilcox 11010e9446c3SMatthew Wilcox static noinline void check_store_range(struct xarray *xa) 11020e9446c3SMatthew Wilcox { 11030e9446c3SMatthew Wilcox unsigned long i, j; 11040e9446c3SMatthew Wilcox 11050e9446c3SMatthew Wilcox for (i = 0; i < 128; i++) { 11060e9446c3SMatthew Wilcox for (j = i; j < 128; j++) { 11070e9446c3SMatthew Wilcox __check_store_range(xa, i, j); 11080e9446c3SMatthew Wilcox __check_store_range(xa, 128 + i, 128 + j); 11090e9446c3SMatthew Wilcox __check_store_range(xa, 4095 + i, 4095 + j); 11100e9446c3SMatthew Wilcox __check_store_range(xa, 4096 + i, 4096 + j); 11110e9446c3SMatthew Wilcox __check_store_range(xa, 123456 + i, 123456 + j); 11125404a7f1SMatthew Wilcox __check_store_range(xa, (1 << 24) + i, (1 << 24) + j); 11130e9446c3SMatthew Wilcox } 11140e9446c3SMatthew Wilcox } 11150e9446c3SMatthew Wilcox } 11160e9446c3SMatthew Wilcox 1117a97e7904SMatthew Wilcox static LIST_HEAD(shadow_nodes); 1118a97e7904SMatthew Wilcox 1119a97e7904SMatthew Wilcox static void test_update_node(struct xa_node *node) 1120a97e7904SMatthew Wilcox { 1121a97e7904SMatthew Wilcox if (node->count && node->count == node->nr_values) { 1122a97e7904SMatthew Wilcox if (list_empty(&node->private_list)) 1123a97e7904SMatthew Wilcox list_add(&shadow_nodes, &node->private_list); 1124a97e7904SMatthew Wilcox } else { 1125a97e7904SMatthew Wilcox if (!list_empty(&node->private_list)) 1126a97e7904SMatthew Wilcox list_del_init(&node->private_list); 1127a97e7904SMatthew Wilcox } 1128a97e7904SMatthew Wilcox } 1129a97e7904SMatthew Wilcox 1130a97e7904SMatthew Wilcox static noinline void shadow_remove(struct xarray *xa) 1131a97e7904SMatthew Wilcox { 1132a97e7904SMatthew Wilcox struct xa_node *node; 1133a97e7904SMatthew Wilcox 1134a97e7904SMatthew Wilcox xa_lock(xa); 1135a97e7904SMatthew Wilcox while ((node = list_first_entry_or_null(&shadow_nodes, 1136a97e7904SMatthew Wilcox struct xa_node, private_list))) { 1137a97e7904SMatthew Wilcox XA_STATE(xas, node->array, 0); 1138a97e7904SMatthew Wilcox XA_BUG_ON(xa, node->array != xa); 1139a97e7904SMatthew Wilcox list_del_init(&node->private_list); 1140a97e7904SMatthew Wilcox xas.xa_node = xa_parent_locked(node->array, node); 1141a97e7904SMatthew Wilcox xas.xa_offset = node->offset; 1142a97e7904SMatthew Wilcox xas.xa_shift = node->shift + XA_CHUNK_SHIFT; 1143a97e7904SMatthew Wilcox xas_set_update(&xas, test_update_node); 1144a97e7904SMatthew Wilcox xas_store(&xas, NULL); 1145a97e7904SMatthew Wilcox } 1146a97e7904SMatthew Wilcox xa_unlock(xa); 1147a97e7904SMatthew Wilcox } 1148a97e7904SMatthew Wilcox 1149a97e7904SMatthew Wilcox static noinline void check_workingset(struct xarray *xa, unsigned long index) 1150a97e7904SMatthew Wilcox { 1151a97e7904SMatthew Wilcox XA_STATE(xas, xa, index); 1152a97e7904SMatthew Wilcox xas_set_update(&xas, test_update_node); 1153a97e7904SMatthew Wilcox 1154a97e7904SMatthew Wilcox do { 1155a97e7904SMatthew Wilcox xas_lock(&xas); 1156a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(0)); 1157a97e7904SMatthew Wilcox xas_next(&xas); 1158a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(1)); 1159a97e7904SMatthew Wilcox xas_unlock(&xas); 1160a97e7904SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 1161a97e7904SMatthew Wilcox 1162a97e7904SMatthew Wilcox XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1163a97e7904SMatthew Wilcox 1164a97e7904SMatthew Wilcox xas_lock(&xas); 1165a97e7904SMatthew Wilcox xas_next(&xas); 1166a97e7904SMatthew Wilcox xas_store(&xas, &xas); 1167a97e7904SMatthew Wilcox XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1168a97e7904SMatthew Wilcox 1169a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(2)); 1170a97e7904SMatthew Wilcox xas_unlock(&xas); 1171a97e7904SMatthew Wilcox XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1172a97e7904SMatthew Wilcox 1173a97e7904SMatthew Wilcox shadow_remove(xa); 1174a97e7904SMatthew Wilcox XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1175a97e7904SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1176a97e7904SMatthew Wilcox } 1177a97e7904SMatthew Wilcox 1178d6427f81SMatthew Wilcox /* 1179d6427f81SMatthew Wilcox * Check that the pointer / value / sibling entries are accounted the 1180d6427f81SMatthew Wilcox * way we expect them to be. 1181d6427f81SMatthew Wilcox */ 1182d6427f81SMatthew Wilcox static noinline void check_account(struct xarray *xa) 1183d6427f81SMatthew Wilcox { 1184d6427f81SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 1185d6427f81SMatthew Wilcox unsigned int order; 1186d6427f81SMatthew Wilcox 1187d6427f81SMatthew Wilcox for (order = 1; order < 12; order++) { 1188d6427f81SMatthew Wilcox XA_STATE(xas, xa, 1 << order); 1189d6427f81SMatthew Wilcox 1190d6427f81SMatthew Wilcox xa_store_order(xa, 0, order, xa, GFP_KERNEL); 1191fffc9a26SMatthew Wilcox rcu_read_lock(); 1192d6427f81SMatthew Wilcox xas_load(&xas); 1193d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count == 0); 1194d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count > (1 << order)); 1195d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1196fffc9a26SMatthew Wilcox rcu_read_unlock(); 1197d6427f81SMatthew Wilcox 1198d6427f81SMatthew Wilcox xa_store_order(xa, 1 << order, order, xa_mk_value(1 << order), 1199d6427f81SMatthew Wilcox GFP_KERNEL); 1200d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2); 1201d6427f81SMatthew Wilcox 1202d6427f81SMatthew Wilcox xa_erase(xa, 1 << order); 1203d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1204d6427f81SMatthew Wilcox 1205d6427f81SMatthew Wilcox xa_erase(xa, 0); 1206d6427f81SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1207d6427f81SMatthew Wilcox } 1208d6427f81SMatthew Wilcox #endif 1209d6427f81SMatthew Wilcox } 1210d6427f81SMatthew Wilcox 1211687149fcSMatthew Wilcox static noinline void check_destroy(struct xarray *xa) 1212687149fcSMatthew Wilcox { 1213687149fcSMatthew Wilcox unsigned long index; 1214687149fcSMatthew Wilcox 1215687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1216687149fcSMatthew Wilcox 1217687149fcSMatthew Wilcox /* Destroying an empty array is a no-op */ 1218687149fcSMatthew Wilcox xa_destroy(xa); 1219687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1220687149fcSMatthew Wilcox 1221687149fcSMatthew Wilcox /* Destroying an array with a single entry */ 1222687149fcSMatthew Wilcox for (index = 0; index < 1000; index++) { 1223687149fcSMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 1224687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1225687149fcSMatthew Wilcox xa_destroy(xa); 1226687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1227687149fcSMatthew Wilcox } 1228687149fcSMatthew Wilcox 1229687149fcSMatthew Wilcox /* Destroying an array with a single entry at ULONG_MAX */ 1230687149fcSMatthew Wilcox xa_store(xa, ULONG_MAX, xa, GFP_KERNEL); 1231687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1232687149fcSMatthew Wilcox xa_destroy(xa); 1233687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1234687149fcSMatthew Wilcox 1235687149fcSMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 1236687149fcSMatthew Wilcox /* Destroying an array with a multi-index entry */ 1237687149fcSMatthew Wilcox xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL); 1238687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1239687149fcSMatthew Wilcox xa_destroy(xa); 1240687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1241687149fcSMatthew Wilcox #endif 1242687149fcSMatthew Wilcox } 1243687149fcSMatthew Wilcox 124458d6ea30SMatthew Wilcox static DEFINE_XARRAY(array); 1245ad3d6c72SMatthew Wilcox 1246ad3d6c72SMatthew Wilcox static int xarray_checks(void) 1247ad3d6c72SMatthew Wilcox { 124858d6ea30SMatthew Wilcox check_xa_err(&array); 1249b803b428SMatthew Wilcox check_xas_retry(&array); 1250ad3d6c72SMatthew Wilcox check_xa_load(&array); 12519b89a035SMatthew Wilcox check_xa_mark(&array); 125258d6ea30SMatthew Wilcox check_xa_shrink(&array); 1253b803b428SMatthew Wilcox check_xas_erase(&array); 125441aec91fSMatthew Wilcox check_cmpxchg(&array); 12559f14d4f1SMatthew Wilcox check_reserve(&array); 125658d6ea30SMatthew Wilcox check_multi_store(&array); 1257371c752dSMatthew Wilcox check_xa_alloc(); 1258b803b428SMatthew Wilcox check_find(&array); 1259e21a2955SMatthew Wilcox check_find_entry(&array); 1260d6427f81SMatthew Wilcox check_account(&array); 1261687149fcSMatthew Wilcox check_destroy(&array); 126264d3e9a9SMatthew Wilcox check_move(&array); 12632264f513SMatthew Wilcox check_create_range(&array); 12640e9446c3SMatthew Wilcox check_store_range(&array); 12654e99d4e9SMatthew Wilcox check_store_iter(&array); 1266ad3d6c72SMatthew Wilcox 1267a97e7904SMatthew Wilcox check_workingset(&array, 0); 1268a97e7904SMatthew Wilcox check_workingset(&array, 64); 1269a97e7904SMatthew Wilcox check_workingset(&array, 4096); 1270a97e7904SMatthew Wilcox 1271ad3d6c72SMatthew Wilcox printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); 1272ad3d6c72SMatthew Wilcox return (tests_run == tests_passed) ? 0 : -EINVAL; 1273ad3d6c72SMatthew Wilcox } 1274ad3d6c72SMatthew Wilcox 1275ad3d6c72SMatthew Wilcox static void xarray_exit(void) 1276ad3d6c72SMatthew Wilcox { 1277ad3d6c72SMatthew Wilcox } 1278ad3d6c72SMatthew Wilcox 1279ad3d6c72SMatthew Wilcox module_init(xarray_checks); 1280ad3d6c72SMatthew Wilcox module_exit(xarray_exit); 1281ad3d6c72SMatthew Wilcox MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>"); 1282ad3d6c72SMatthew Wilcox MODULE_LICENSE("GPL"); 1283