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 31b7677a13SMatthew Wilcox static void *xa_mk_index(unsigned long index) 32b7677a13SMatthew Wilcox { 33b7677a13SMatthew Wilcox return xa_mk_value(index & LONG_MAX); 34b7677a13SMatthew Wilcox } 35b7677a13SMatthew Wilcox 36ad3d6c72SMatthew Wilcox static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp) 37ad3d6c72SMatthew Wilcox { 38b7677a13SMatthew Wilcox return xa_store(xa, index, xa_mk_index(index), gfp); 39ad3d6c72SMatthew Wilcox } 40ad3d6c72SMatthew Wilcox 41371c752dSMatthew Wilcox static void xa_alloc_index(struct xarray *xa, unsigned long index, gfp_t gfp) 42371c752dSMatthew Wilcox { 43371c752dSMatthew Wilcox u32 id = 0; 44371c752dSMatthew Wilcox 45b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, xa_mk_index(index), 46371c752dSMatthew Wilcox gfp) != 0); 47371c752dSMatthew Wilcox XA_BUG_ON(xa, id != index); 48371c752dSMatthew Wilcox } 49371c752dSMatthew Wilcox 50ad3d6c72SMatthew Wilcox static void xa_erase_index(struct xarray *xa, unsigned long index) 51ad3d6c72SMatthew Wilcox { 52b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_erase(xa, index) != xa_mk_index(index)); 5358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, index) != NULL); 5458d6ea30SMatthew Wilcox } 5558d6ea30SMatthew Wilcox 5658d6ea30SMatthew Wilcox /* 5758d6ea30SMatthew Wilcox * If anyone needs this, please move it to xarray.c. We have no current 5858d6ea30SMatthew Wilcox * users outside the test suite because all current multislot users want 5958d6ea30SMatthew Wilcox * to use the advanced API. 6058d6ea30SMatthew Wilcox */ 6158d6ea30SMatthew Wilcox static void *xa_store_order(struct xarray *xa, unsigned long index, 6258d6ea30SMatthew Wilcox unsigned order, void *entry, gfp_t gfp) 6358d6ea30SMatthew Wilcox { 6458d6ea30SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 6558d6ea30SMatthew Wilcox void *curr; 6658d6ea30SMatthew Wilcox 6758d6ea30SMatthew Wilcox do { 6858d6ea30SMatthew Wilcox xas_lock(&xas); 6958d6ea30SMatthew Wilcox curr = xas_store(&xas, entry); 7058d6ea30SMatthew Wilcox xas_unlock(&xas); 7158d6ea30SMatthew Wilcox } while (xas_nomem(&xas, gfp)); 7258d6ea30SMatthew Wilcox 7358d6ea30SMatthew Wilcox return curr; 7458d6ea30SMatthew Wilcox } 7558d6ea30SMatthew Wilcox 7658d6ea30SMatthew Wilcox static noinline void check_xa_err(struct xarray *xa) 7758d6ea30SMatthew Wilcox { 7858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 0, GFP_NOWAIT)) != 0); 7958d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_erase(xa, 0)) != 0); 8058d6ea30SMatthew Wilcox #ifndef __KERNEL__ 8158d6ea30SMatthew Wilcox /* The kernel does not fail GFP_NOWAIT allocations */ 8258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM); 8358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_NOWAIT)) != -ENOMEM); 8458d6ea30SMatthew Wilcox #endif 8558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store_index(xa, 1, GFP_KERNEL)) != 0); 8658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_store(xa, 1, xa_mk_value(0), GFP_KERNEL)) != 0); 8758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_err(xa_erase(xa, 1)) != 0); 8858d6ea30SMatthew Wilcox // kills the test-suite :-( 8958d6ea30SMatthew Wilcox // XA_BUG_ON(xa, xa_err(xa_store(xa, 0, xa_mk_internal(0), 0)) != -EINVAL); 90ad3d6c72SMatthew Wilcox } 91ad3d6c72SMatthew Wilcox 92b803b428SMatthew Wilcox static noinline void check_xas_retry(struct xarray *xa) 93b803b428SMatthew Wilcox { 94b803b428SMatthew Wilcox XA_STATE(xas, xa, 0); 95b803b428SMatthew Wilcox void *entry; 96b803b428SMatthew Wilcox 97b803b428SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 98b803b428SMatthew Wilcox xa_store_index(xa, 1, GFP_KERNEL); 99b803b428SMatthew Wilcox 100b803b428SMatthew Wilcox rcu_read_lock(); 101b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_value(0)); 102b803b428SMatthew Wilcox xa_erase_index(xa, 1); 103b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_is_retry(xas_reload(&xas))); 104b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_retry(&xas, NULL)); 105b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_retry(&xas, xa_mk_value(0))); 106b803b428SMatthew Wilcox xas_reset(&xas); 107b803b428SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node != XAS_RESTART); 108b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0)); 109b803b428SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node != NULL); 110bd54211bSMatthew Wilcox rcu_read_unlock(); 111b803b428SMatthew Wilcox 112b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL); 113bd54211bSMatthew Wilcox 114bd54211bSMatthew Wilcox rcu_read_lock(); 115b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_is_internal(xas_reload(&xas))); 116b803b428SMatthew Wilcox xas.xa_node = XAS_RESTART; 117b803b428SMatthew Wilcox XA_BUG_ON(xa, xas_next_entry(&xas, ULONG_MAX) != xa_mk_value(0)); 118b803b428SMatthew Wilcox rcu_read_unlock(); 119b803b428SMatthew Wilcox 120b803b428SMatthew Wilcox /* Make sure we can iterate through retry entries */ 121b803b428SMatthew Wilcox xas_lock(&xas); 122b803b428SMatthew Wilcox xas_set(&xas, 0); 123b803b428SMatthew Wilcox xas_store(&xas, XA_RETRY_ENTRY); 124b803b428SMatthew Wilcox xas_set(&xas, 1); 125b803b428SMatthew Wilcox xas_store(&xas, XA_RETRY_ENTRY); 126b803b428SMatthew Wilcox 127b803b428SMatthew Wilcox xas_set(&xas, 0); 128b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 129b7677a13SMatthew Wilcox xas_store(&xas, xa_mk_index(xas.xa_index)); 130b803b428SMatthew Wilcox } 131b803b428SMatthew Wilcox xas_unlock(&xas); 132b803b428SMatthew Wilcox 133b803b428SMatthew Wilcox xa_erase_index(xa, 0); 134b803b428SMatthew Wilcox xa_erase_index(xa, 1); 135b803b428SMatthew Wilcox } 136b803b428SMatthew Wilcox 137ad3d6c72SMatthew Wilcox static noinline void check_xa_load(struct xarray *xa) 138ad3d6c72SMatthew Wilcox { 139ad3d6c72SMatthew Wilcox unsigned long i, j; 140ad3d6c72SMatthew Wilcox 141ad3d6c72SMatthew Wilcox for (i = 0; i < 1024; i++) { 142ad3d6c72SMatthew Wilcox for (j = 0; j < 1024; j++) { 143ad3d6c72SMatthew Wilcox void *entry = xa_load(xa, j); 144ad3d6c72SMatthew Wilcox if (j < i) 145ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, xa_to_value(entry) != j); 146ad3d6c72SMatthew Wilcox else 147ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, entry); 148ad3d6c72SMatthew Wilcox } 149ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 150ad3d6c72SMatthew Wilcox } 151ad3d6c72SMatthew Wilcox 152ad3d6c72SMatthew Wilcox for (i = 0; i < 1024; i++) { 153ad3d6c72SMatthew Wilcox for (j = 0; j < 1024; j++) { 154ad3d6c72SMatthew Wilcox void *entry = xa_load(xa, j); 155ad3d6c72SMatthew Wilcox if (j >= i) 156ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, xa_to_value(entry) != j); 157ad3d6c72SMatthew Wilcox else 158ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, entry); 159ad3d6c72SMatthew Wilcox } 160ad3d6c72SMatthew Wilcox xa_erase_index(xa, i); 161ad3d6c72SMatthew Wilcox } 162ad3d6c72SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 163ad3d6c72SMatthew Wilcox } 164ad3d6c72SMatthew Wilcox 1659b89a035SMatthew Wilcox static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index) 1669b89a035SMatthew Wilcox { 16758d6ea30SMatthew Wilcox unsigned int order; 16858d6ea30SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 8 : 1; 16958d6ea30SMatthew Wilcox 1709b89a035SMatthew Wilcox /* NULL elements have no marks set */ 1719b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1729b89a035SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 1739b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1749b89a035SMatthew Wilcox 1759b89a035SMatthew Wilcox /* Storing a pointer will not make a mark appear */ 1769b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL); 1779b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1789b89a035SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 1799b89a035SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0)); 1809b89a035SMatthew Wilcox 1819b89a035SMatthew Wilcox /* Setting one mark will not set another mark */ 1829b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0)); 1839b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1)); 1849b89a035SMatthew Wilcox 1859b89a035SMatthew Wilcox /* Storing NULL clears marks, and they can't be set again */ 1869b89a035SMatthew Wilcox xa_erase_index(xa, index); 1879b89a035SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1889b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 1899b89a035SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 1909b89a035SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 19158d6ea30SMatthew Wilcox 19258d6ea30SMatthew Wilcox /* 19358d6ea30SMatthew Wilcox * Storing a multi-index entry over entries with marks gives the 19458d6ea30SMatthew Wilcox * entire entry the union of the marks 19558d6ea30SMatthew Wilcox */ 19658d6ea30SMatthew Wilcox BUG_ON((index % 4) != 0); 19758d6ea30SMatthew Wilcox for (order = 2; order < max_order; order++) { 19858d6ea30SMatthew Wilcox unsigned long base = round_down(index, 1UL << order); 19958d6ea30SMatthew Wilcox unsigned long next = base + (1UL << order); 20058d6ea30SMatthew Wilcox unsigned long i; 20158d6ea30SMatthew Wilcox 20258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, index + 1, GFP_KERNEL)); 20358d6ea30SMatthew Wilcox xa_set_mark(xa, index + 1, XA_MARK_0); 20458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, index + 2, GFP_KERNEL)); 205d69d287aSMatthew Wilcox xa_set_mark(xa, index + 2, XA_MARK_2); 20658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL)); 207b7677a13SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_index(index), 20858d6ea30SMatthew Wilcox GFP_KERNEL); 20958d6ea30SMatthew Wilcox for (i = base; i < next; i++) { 21093eb07f7SMatthew Wilcox XA_STATE(xas, xa, i); 21193eb07f7SMatthew Wilcox unsigned int seen = 0; 21293eb07f7SMatthew Wilcox void *entry; 21393eb07f7SMatthew Wilcox 21458d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0)); 215d69d287aSMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_1)); 216d69d287aSMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_2)); 21793eb07f7SMatthew Wilcox 21893eb07f7SMatthew Wilcox /* We should see two elements in the array */ 219fffc9a26SMatthew Wilcox rcu_read_lock(); 22093eb07f7SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) 22193eb07f7SMatthew Wilcox seen++; 222fffc9a26SMatthew Wilcox rcu_read_unlock(); 22393eb07f7SMatthew Wilcox XA_BUG_ON(xa, seen != 2); 22493eb07f7SMatthew Wilcox 22593eb07f7SMatthew Wilcox /* One of which is marked */ 22693eb07f7SMatthew Wilcox xas_set(&xas, 0); 22793eb07f7SMatthew Wilcox seen = 0; 228fffc9a26SMatthew Wilcox rcu_read_lock(); 22993eb07f7SMatthew Wilcox xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) 23093eb07f7SMatthew Wilcox seen++; 231fffc9a26SMatthew Wilcox rcu_read_unlock(); 23293eb07f7SMatthew Wilcox XA_BUG_ON(xa, seen != 1); 23358d6ea30SMatthew Wilcox } 23458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_0)); 23558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_1)); 23658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, next, XA_MARK_2)); 23758d6ea30SMatthew Wilcox xa_erase_index(xa, index); 23858d6ea30SMatthew Wilcox xa_erase_index(xa, next); 23958d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 24058d6ea30SMatthew Wilcox } 24158d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 2429b89a035SMatthew Wilcox } 2439b89a035SMatthew Wilcox 244adb9d9c4SMatthew Wilcox static noinline void check_xa_mark_2(struct xarray *xa) 245adb9d9c4SMatthew Wilcox { 246adb9d9c4SMatthew Wilcox XA_STATE(xas, xa, 0); 247adb9d9c4SMatthew Wilcox unsigned long index; 248adb9d9c4SMatthew Wilcox unsigned int count = 0; 249adb9d9c4SMatthew Wilcox void *entry; 250adb9d9c4SMatthew Wilcox 251adb9d9c4SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 252adb9d9c4SMatthew Wilcox xa_set_mark(xa, 0, XA_MARK_0); 253adb9d9c4SMatthew Wilcox xas_lock(&xas); 254adb9d9c4SMatthew Wilcox xas_load(&xas); 255adb9d9c4SMatthew Wilcox xas_init_marks(&xas); 256adb9d9c4SMatthew Wilcox xas_unlock(&xas); 257adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, 0, XA_MARK_0) == 0); 258adb9d9c4SMatthew Wilcox 259adb9d9c4SMatthew Wilcox for (index = 3500; index < 4500; index++) { 260adb9d9c4SMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 261adb9d9c4SMatthew Wilcox xa_set_mark(xa, index, XA_MARK_0); 262adb9d9c4SMatthew Wilcox } 263adb9d9c4SMatthew Wilcox 264adb9d9c4SMatthew Wilcox xas_reset(&xas); 265adb9d9c4SMatthew Wilcox rcu_read_lock(); 266adb9d9c4SMatthew Wilcox xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_0) 267adb9d9c4SMatthew Wilcox count++; 268adb9d9c4SMatthew Wilcox rcu_read_unlock(); 269adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, count != 1000); 270adb9d9c4SMatthew Wilcox 271adb9d9c4SMatthew Wilcox xas_lock(&xas); 272adb9d9c4SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 273adb9d9c4SMatthew Wilcox xas_init_marks(&xas); 274adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, xas.xa_index, XA_MARK_0)); 275adb9d9c4SMatthew Wilcox XA_BUG_ON(xa, !xas_get_mark(&xas, XA_MARK_0)); 276adb9d9c4SMatthew Wilcox } 277adb9d9c4SMatthew Wilcox xas_unlock(&xas); 278adb9d9c4SMatthew Wilcox 279adb9d9c4SMatthew Wilcox xa_destroy(xa); 280adb9d9c4SMatthew Wilcox } 281adb9d9c4SMatthew Wilcox 2829b89a035SMatthew Wilcox static noinline void check_xa_mark(struct xarray *xa) 2839b89a035SMatthew Wilcox { 2849b89a035SMatthew Wilcox unsigned long index; 2859b89a035SMatthew Wilcox 2869b89a035SMatthew Wilcox for (index = 0; index < 16384; index += 4) 2879b89a035SMatthew Wilcox check_xa_mark_1(xa, index); 288adb9d9c4SMatthew Wilcox 289adb9d9c4SMatthew Wilcox check_xa_mark_2(xa); 2909b89a035SMatthew Wilcox } 2919b89a035SMatthew Wilcox 29258d6ea30SMatthew Wilcox static noinline void check_xa_shrink(struct xarray *xa) 29358d6ea30SMatthew Wilcox { 29458d6ea30SMatthew Wilcox XA_STATE(xas, xa, 1); 29558d6ea30SMatthew Wilcox struct xa_node *node; 29693eb07f7SMatthew Wilcox unsigned int order; 29793eb07f7SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 15 : 1; 29858d6ea30SMatthew Wilcox 29958d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 30058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 0, GFP_KERNEL) != NULL); 30158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 1, GFP_KERNEL) != NULL); 30258d6ea30SMatthew Wilcox 30358d6ea30SMatthew Wilcox /* 30458d6ea30SMatthew Wilcox * Check that erasing the entry at 1 shrinks the tree and properly 30558d6ea30SMatthew Wilcox * marks the node as being deleted. 30658d6ea30SMatthew Wilcox */ 30758d6ea30SMatthew Wilcox xas_lock(&xas); 30858d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_load(&xas) != xa_mk_value(1)); 30958d6ea30SMatthew Wilcox node = xas.xa_node; 31058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != xa_mk_value(0)); 31158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1)); 31258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != NULL); 31358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node != XAS_BOUNDS); 31458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_entry_locked(xa, node, 0) != XA_RETRY_ENTRY); 31558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xas_load(&xas) != NULL); 31658d6ea30SMatthew Wilcox xas_unlock(&xas); 31758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 31858d6ea30SMatthew Wilcox xa_erase_index(xa, 0); 31958d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 32093eb07f7SMatthew Wilcox 32193eb07f7SMatthew Wilcox for (order = 0; order < max_order; order++) { 32293eb07f7SMatthew Wilcox unsigned long max = (1UL << order) - 1; 32393eb07f7SMatthew Wilcox xa_store_order(xa, 0, order, xa_mk_value(0), GFP_KERNEL); 32493eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != xa_mk_value(0)); 32593eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL); 32693eb07f7SMatthew Wilcox rcu_read_lock(); 32793eb07f7SMatthew Wilcox node = xa_head(xa); 32893eb07f7SMatthew Wilcox rcu_read_unlock(); 32993eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, ULONG_MAX, GFP_KERNEL) != 33093eb07f7SMatthew Wilcox NULL); 33193eb07f7SMatthew Wilcox rcu_read_lock(); 33293eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_head(xa) == node); 33393eb07f7SMatthew Wilcox rcu_read_unlock(); 33493eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max + 1) != NULL); 33593eb07f7SMatthew Wilcox xa_erase_index(xa, ULONG_MAX); 33693eb07f7SMatthew Wilcox XA_BUG_ON(xa, xa->xa_head != node); 33793eb07f7SMatthew Wilcox xa_erase_index(xa, 0); 33893eb07f7SMatthew Wilcox } 33958d6ea30SMatthew Wilcox } 34058d6ea30SMatthew Wilcox 34141aec91fSMatthew Wilcox static noinline void check_cmpxchg(struct xarray *xa) 34241aec91fSMatthew Wilcox { 34341aec91fSMatthew Wilcox void *FIVE = xa_mk_value(5); 34441aec91fSMatthew Wilcox void *SIX = xa_mk_value(6); 34541aec91fSMatthew Wilcox void *LOTS = xa_mk_value(12345678); 34641aec91fSMatthew Wilcox 34741aec91fSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 34841aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 12345678, GFP_KERNEL) != NULL); 349fd9dc93eSMatthew Wilcox XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EBUSY); 35041aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS); 35141aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS); 35241aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE); 35341aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL); 35441aec91fSMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL); 35541aec91fSMatthew Wilcox xa_erase_index(xa, 12345678); 35641aec91fSMatthew Wilcox xa_erase_index(xa, 5); 35741aec91fSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 35841aec91fSMatthew Wilcox } 35941aec91fSMatthew Wilcox 3609f14d4f1SMatthew Wilcox static noinline void check_reserve(struct xarray *xa) 3619f14d4f1SMatthew Wilcox { 3629f14d4f1SMatthew Wilcox void *entry; 3634a31896cSMatthew Wilcox unsigned long index; 3649f14d4f1SMatthew Wilcox 3659f14d4f1SMatthew Wilcox /* An array with a reserved entry is not empty */ 3669f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3679f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3689f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 3699f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 12345678)); 3709f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3719f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3729f14d4f1SMatthew Wilcox 3739f14d4f1SMatthew Wilcox /* Releasing a used entry does nothing */ 3749f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3759f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 12345678, 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 3809f14d4f1SMatthew Wilcox /* cmpxchg sees a reserved entry as NULL */ 3819f14d4f1SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 3829f14d4f1SMatthew Wilcox XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, NULL, xa_mk_value(12345678), 3839f14d4f1SMatthew Wilcox GFP_NOWAIT) != NULL); 3849f14d4f1SMatthew Wilcox xa_release(xa, 12345678); 3859f14d4f1SMatthew Wilcox xa_erase_index(xa, 12345678); 3869f14d4f1SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3879f14d4f1SMatthew Wilcox 388b0606fedSMatthew Wilcox /* But xa_insert does not */ 3894c0608f4SMatthew Wilcox xa_reserve(xa, 12345678, GFP_KERNEL); 390b0606fedSMatthew Wilcox XA_BUG_ON(xa, xa_insert(xa, 12345678, xa_mk_value(12345678), 0) != 391fd9dc93eSMatthew Wilcox -EBUSY); 392b0606fedSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 393b0606fedSMatthew Wilcox XA_BUG_ON(xa, xa_erase(xa, 12345678) != NULL); 3944c0608f4SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 3954c0608f4SMatthew Wilcox 3969f14d4f1SMatthew Wilcox /* Can iterate through a reserved entry */ 3979f14d4f1SMatthew Wilcox xa_store_index(xa, 5, GFP_KERNEL); 3989f14d4f1SMatthew Wilcox xa_reserve(xa, 6, GFP_KERNEL); 3999f14d4f1SMatthew Wilcox xa_store_index(xa, 7, GFP_KERNEL); 4009f14d4f1SMatthew Wilcox 4014a31896cSMatthew Wilcox xa_for_each(xa, index, entry) { 4029f14d4f1SMatthew Wilcox XA_BUG_ON(xa, index != 5 && index != 7); 4039f14d4f1SMatthew Wilcox } 4049f14d4f1SMatthew Wilcox xa_destroy(xa); 4059f14d4f1SMatthew Wilcox } 4069f14d4f1SMatthew Wilcox 407b803b428SMatthew Wilcox static noinline void check_xas_erase(struct xarray *xa) 408b803b428SMatthew Wilcox { 409b803b428SMatthew Wilcox XA_STATE(xas, xa, 0); 410b803b428SMatthew Wilcox void *entry; 411b803b428SMatthew Wilcox unsigned long i, j; 412b803b428SMatthew Wilcox 413b803b428SMatthew Wilcox for (i = 0; i < 200; i++) { 414b803b428SMatthew Wilcox for (j = i; j < 2 * i + 17; j++) { 415b803b428SMatthew Wilcox xas_set(&xas, j); 416b803b428SMatthew Wilcox do { 417b803b428SMatthew Wilcox xas_lock(&xas); 418b7677a13SMatthew Wilcox xas_store(&xas, xa_mk_index(j)); 419b803b428SMatthew Wilcox xas_unlock(&xas); 420b803b428SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 421b803b428SMatthew Wilcox } 422b803b428SMatthew Wilcox 423b803b428SMatthew Wilcox xas_set(&xas, ULONG_MAX); 424b803b428SMatthew Wilcox do { 425b803b428SMatthew Wilcox xas_lock(&xas); 426b803b428SMatthew Wilcox xas_store(&xas, xa_mk_value(0)); 427b803b428SMatthew Wilcox xas_unlock(&xas); 428b803b428SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 429b803b428SMatthew Wilcox 430b803b428SMatthew Wilcox xas_lock(&xas); 431b803b428SMatthew Wilcox xas_store(&xas, NULL); 432b803b428SMatthew Wilcox 433b803b428SMatthew Wilcox xas_set(&xas, 0); 434b803b428SMatthew Wilcox j = i; 435b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 436b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(j)); 437b803b428SMatthew Wilcox xas_store(&xas, NULL); 438b803b428SMatthew Wilcox j++; 439b803b428SMatthew Wilcox } 440b803b428SMatthew Wilcox xas_unlock(&xas); 441b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 442b803b428SMatthew Wilcox } 443b803b428SMatthew Wilcox } 444b803b428SMatthew Wilcox 4454f06d630SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 4464f06d630SMatthew Wilcox static noinline void check_multi_store_1(struct xarray *xa, unsigned long index, 4474f06d630SMatthew Wilcox unsigned int order) 4484f06d630SMatthew Wilcox { 4494f06d630SMatthew Wilcox XA_STATE(xas, xa, index); 4504f06d630SMatthew Wilcox unsigned long min = index & ~((1UL << order) - 1); 4514f06d630SMatthew Wilcox unsigned long max = min + (1UL << order); 4524f06d630SMatthew Wilcox 453b7677a13SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL); 454b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(index)); 455b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(index)); 4564f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != NULL); 4574f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 4584f06d630SMatthew Wilcox 459fffc9a26SMatthew Wilcox xas_lock(&xas); 460b7677a13SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(min)) != xa_mk_index(index)); 461fffc9a26SMatthew Wilcox xas_unlock(&xas); 462b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min) != xa_mk_index(min)); 463b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max - 1) != xa_mk_index(min)); 4644f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, max) != NULL); 4654f06d630SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, min - 1) != NULL); 4664f06d630SMatthew Wilcox 4674f06d630SMatthew Wilcox xa_erase_index(xa, min); 4684f06d630SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 4694f06d630SMatthew Wilcox } 4704f06d630SMatthew Wilcox 4714f06d630SMatthew Wilcox static noinline void check_multi_store_2(struct xarray *xa, unsigned long index, 4724f06d630SMatthew Wilcox unsigned int order) 4734f06d630SMatthew Wilcox { 4744f06d630SMatthew Wilcox XA_STATE(xas, xa, index); 4754f06d630SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_value(0), GFP_KERNEL); 4764f06d630SMatthew Wilcox 477fffc9a26SMatthew Wilcox xas_lock(&xas); 4784f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_value(1)) != xa_mk_value(0)); 4794f06d630SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != index); 4804f06d630SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, NULL) != xa_mk_value(1)); 481fffc9a26SMatthew Wilcox xas_unlock(&xas); 4824f06d630SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 4834f06d630SMatthew Wilcox } 4844f145cd6SMatthew Wilcox 4854f145cd6SMatthew Wilcox static noinline void check_multi_store_3(struct xarray *xa, unsigned long index, 4864f145cd6SMatthew Wilcox unsigned int order) 4874f145cd6SMatthew Wilcox { 4884f145cd6SMatthew Wilcox XA_STATE(xas, xa, 0); 4894f145cd6SMatthew Wilcox void *entry; 4904f145cd6SMatthew Wilcox int n = 0; 4914f145cd6SMatthew Wilcox 4924f145cd6SMatthew Wilcox xa_store_order(xa, index, order, xa_mk_index(index), GFP_KERNEL); 4934f145cd6SMatthew Wilcox 4944f145cd6SMatthew Wilcox xas_lock(&xas); 4954f145cd6SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 4964f145cd6SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(index)); 4974f145cd6SMatthew Wilcox n++; 4984f145cd6SMatthew Wilcox } 4994f145cd6SMatthew Wilcox XA_BUG_ON(xa, n != 1); 5004f145cd6SMatthew Wilcox xas_set(&xas, index + 1); 5014f145cd6SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 5024f145cd6SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(index)); 5034f145cd6SMatthew Wilcox n++; 5044f145cd6SMatthew Wilcox } 5054f145cd6SMatthew Wilcox XA_BUG_ON(xa, n != 2); 5064f145cd6SMatthew Wilcox xas_unlock(&xas); 5074f145cd6SMatthew Wilcox 5084f145cd6SMatthew Wilcox xa_destroy(xa); 5094f145cd6SMatthew Wilcox } 5104f06d630SMatthew Wilcox #endif 5114f06d630SMatthew Wilcox 51258d6ea30SMatthew Wilcox static noinline void check_multi_store(struct xarray *xa) 51358d6ea30SMatthew Wilcox { 51458d6ea30SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 51558d6ea30SMatthew Wilcox unsigned long i, j, k; 51658d6ea30SMatthew Wilcox unsigned int max_order = (sizeof(long) == 4) ? 30 : 60; 51758d6ea30SMatthew Wilcox 51858d6ea30SMatthew Wilcox /* Loading from any position returns the same value */ 51958d6ea30SMatthew Wilcox xa_store_order(xa, 0, 1, xa_mk_value(0), GFP_KERNEL); 52058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 52158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0)); 52258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != NULL); 52358d6ea30SMatthew Wilcox rcu_read_lock(); 52458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 2); 52558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2); 52658d6ea30SMatthew Wilcox rcu_read_unlock(); 52758d6ea30SMatthew Wilcox 52858d6ea30SMatthew Wilcox /* Storing adjacent to the value does not alter the value */ 52958d6ea30SMatthew Wilcox xa_store(xa, 3, xa, GFP_KERNEL); 53058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(0)); 53158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(0)); 53258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != NULL); 53358d6ea30SMatthew Wilcox rcu_read_lock(); 53458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 3); 53558d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 2); 53658d6ea30SMatthew Wilcox rcu_read_unlock(); 53758d6ea30SMatthew Wilcox 53858d6ea30SMatthew Wilcox /* Overwriting multiple indexes works */ 53958d6ea30SMatthew Wilcox xa_store_order(xa, 0, 2, xa_mk_value(1), GFP_KERNEL); 54058d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 0) != xa_mk_value(1)); 54158d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 1) != xa_mk_value(1)); 54258d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 2) != xa_mk_value(1)); 54358d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 3) != xa_mk_value(1)); 54458d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, 4) != NULL); 54558d6ea30SMatthew Wilcox rcu_read_lock(); 54658d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->count != 4); 54758d6ea30SMatthew Wilcox XA_BUG_ON(xa, xa_to_node(xa_head(xa))->nr_values != 4); 54858d6ea30SMatthew Wilcox rcu_read_unlock(); 54958d6ea30SMatthew Wilcox 55058d6ea30SMatthew Wilcox /* We can erase multiple values with a single store */ 5515404a7f1SMatthew Wilcox xa_store_order(xa, 0, BITS_PER_LONG - 1, NULL, GFP_KERNEL); 55258d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 55358d6ea30SMatthew Wilcox 55458d6ea30SMatthew Wilcox /* Even when the first slot is empty but the others aren't */ 55558d6ea30SMatthew Wilcox xa_store_index(xa, 1, GFP_KERNEL); 55658d6ea30SMatthew Wilcox xa_store_index(xa, 2, GFP_KERNEL); 55758d6ea30SMatthew Wilcox xa_store_order(xa, 0, 2, NULL, GFP_KERNEL); 55858d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 55958d6ea30SMatthew Wilcox 56058d6ea30SMatthew Wilcox for (i = 0; i < max_order; i++) { 56158d6ea30SMatthew Wilcox for (j = 0; j < max_order; j++) { 562b7677a13SMatthew Wilcox xa_store_order(xa, 0, i, xa_mk_index(i), GFP_KERNEL); 563b7677a13SMatthew Wilcox xa_store_order(xa, 0, j, xa_mk_index(j), GFP_KERNEL); 56458d6ea30SMatthew Wilcox 56558d6ea30SMatthew Wilcox for (k = 0; k < max_order; k++) { 56658d6ea30SMatthew Wilcox void *entry = xa_load(xa, (1UL << k) - 1); 56758d6ea30SMatthew Wilcox if ((i < k) && (j < k)) 56858d6ea30SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 56958d6ea30SMatthew Wilcox else 570b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(j)); 57158d6ea30SMatthew Wilcox } 57258d6ea30SMatthew Wilcox 57358d6ea30SMatthew Wilcox xa_erase(xa, 0); 57458d6ea30SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 57558d6ea30SMatthew Wilcox } 57658d6ea30SMatthew Wilcox } 5774f06d630SMatthew Wilcox 5784f06d630SMatthew Wilcox for (i = 0; i < 20; i++) { 5794f06d630SMatthew Wilcox check_multi_store_1(xa, 200, i); 5804f06d630SMatthew Wilcox check_multi_store_1(xa, 0, i); 5814f06d630SMatthew Wilcox check_multi_store_1(xa, (1UL << i) + 1, i); 5824f06d630SMatthew Wilcox } 5834f06d630SMatthew Wilcox check_multi_store_2(xa, 4095, 9); 5844f145cd6SMatthew Wilcox 5854f145cd6SMatthew Wilcox for (i = 1; i < 20; i++) { 5864f145cd6SMatthew Wilcox check_multi_store_3(xa, 0, i); 5874f145cd6SMatthew Wilcox check_multi_store_3(xa, 1UL << i, i); 5884f145cd6SMatthew Wilcox } 58958d6ea30SMatthew Wilcox #endif 59058d6ea30SMatthew Wilcox } 59158d6ea30SMatthew Wilcox 592371c752dSMatthew Wilcox static DEFINE_XARRAY_ALLOC(xa0); 593371c752dSMatthew Wilcox 594371c752dSMatthew Wilcox static noinline void check_xa_alloc(void) 595371c752dSMatthew Wilcox { 596371c752dSMatthew Wilcox int i; 597371c752dSMatthew Wilcox u32 id; 598371c752dSMatthew Wilcox 599371c752dSMatthew Wilcox /* An empty array should assign 0 to the first alloc */ 600371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 601371c752dSMatthew Wilcox 602371c752dSMatthew Wilcox /* Erasing it should make the array empty again */ 603371c752dSMatthew Wilcox xa_erase_index(&xa0, 0); 604371c752dSMatthew Wilcox XA_BUG_ON(&xa0, !xa_empty(&xa0)); 605371c752dSMatthew Wilcox 606371c752dSMatthew Wilcox /* And it should assign 0 again */ 607371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 608371c752dSMatthew Wilcox 609371c752dSMatthew Wilcox /* The next assigned ID should be 1 */ 610371c752dSMatthew Wilcox xa_alloc_index(&xa0, 1, GFP_KERNEL); 611371c752dSMatthew Wilcox xa_erase_index(&xa0, 1); 612371c752dSMatthew Wilcox 613371c752dSMatthew Wilcox /* Storing a value should mark it used */ 614371c752dSMatthew Wilcox xa_store_index(&xa0, 1, GFP_KERNEL); 615371c752dSMatthew Wilcox xa_alloc_index(&xa0, 2, GFP_KERNEL); 616371c752dSMatthew Wilcox 617371c752dSMatthew Wilcox /* If we then erase 0, it should be free */ 618371c752dSMatthew Wilcox xa_erase_index(&xa0, 0); 619371c752dSMatthew Wilcox xa_alloc_index(&xa0, 0, GFP_KERNEL); 620371c752dSMatthew Wilcox 621371c752dSMatthew Wilcox xa_erase_index(&xa0, 1); 622371c752dSMatthew Wilcox xa_erase_index(&xa0, 2); 623371c752dSMatthew Wilcox 624371c752dSMatthew Wilcox for (i = 1; i < 5000; i++) { 625371c752dSMatthew Wilcox xa_alloc_index(&xa0, i, GFP_KERNEL); 626371c752dSMatthew Wilcox } 627371c752dSMatthew Wilcox 628371c752dSMatthew Wilcox xa_destroy(&xa0); 629371c752dSMatthew Wilcox 630371c752dSMatthew Wilcox id = 0xfffffffeU; 631b7677a13SMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_index(id), 632371c752dSMatthew Wilcox GFP_KERNEL) != 0); 633371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xfffffffeU); 634b7677a13SMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_index(id), 635371c752dSMatthew Wilcox GFP_KERNEL) != 0); 636371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xffffffffU); 637b7677a13SMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, UINT_MAX, xa_mk_index(id), 638371c752dSMatthew Wilcox GFP_KERNEL) != -ENOSPC); 639371c752dSMatthew Wilcox XA_BUG_ON(&xa0, id != 0xffffffffU); 640371c752dSMatthew Wilcox xa_destroy(&xa0); 64148483614SMatthew Wilcox 64248483614SMatthew Wilcox id = 10; 64348483614SMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, 5, xa_mk_index(id), 64448483614SMatthew Wilcox GFP_KERNEL) != -ENOSPC); 64548483614SMatthew Wilcox XA_BUG_ON(&xa0, xa_store_index(&xa0, 3, GFP_KERNEL) != 0); 64648483614SMatthew Wilcox XA_BUG_ON(&xa0, xa_alloc(&xa0, &id, 5, xa_mk_index(id), 64748483614SMatthew Wilcox GFP_KERNEL) != -ENOSPC); 64848483614SMatthew Wilcox xa_erase_index(&xa0, 3); 64948483614SMatthew Wilcox XA_BUG_ON(&xa0, !xa_empty(&xa0)); 650371c752dSMatthew Wilcox } 651371c752dSMatthew Wilcox 6524e99d4e9SMatthew Wilcox static noinline void __check_store_iter(struct xarray *xa, unsigned long start, 6534e99d4e9SMatthew Wilcox unsigned int order, unsigned int present) 6544e99d4e9SMatthew Wilcox { 6554e99d4e9SMatthew Wilcox XA_STATE_ORDER(xas, xa, start, order); 6564e99d4e9SMatthew Wilcox void *entry; 6574e99d4e9SMatthew Wilcox unsigned int count = 0; 6584e99d4e9SMatthew Wilcox 6594e99d4e9SMatthew Wilcox retry: 6604e99d4e9SMatthew Wilcox xas_lock(&xas); 6614e99d4e9SMatthew Wilcox xas_for_each_conflict(&xas, entry) { 6624e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_is_value(entry)); 663b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry < xa_mk_index(start)); 664b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry > xa_mk_index(start + (1UL << order) - 1)); 6654e99d4e9SMatthew Wilcox count++; 6664e99d4e9SMatthew Wilcox } 667b7677a13SMatthew Wilcox xas_store(&xas, xa_mk_index(start)); 6684e99d4e9SMatthew Wilcox xas_unlock(&xas); 6694e99d4e9SMatthew Wilcox if (xas_nomem(&xas, GFP_KERNEL)) { 6704e99d4e9SMatthew Wilcox count = 0; 6714e99d4e9SMatthew Wilcox goto retry; 6724e99d4e9SMatthew Wilcox } 6734e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 6744e99d4e9SMatthew Wilcox XA_BUG_ON(xa, count != present); 675b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, start) != xa_mk_index(start)); 6764e99d4e9SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, start + (1UL << order) - 1) != 677b7677a13SMatthew Wilcox xa_mk_index(start)); 6784e99d4e9SMatthew Wilcox xa_erase_index(xa, start); 6794e99d4e9SMatthew Wilcox } 6804e99d4e9SMatthew Wilcox 6814e99d4e9SMatthew Wilcox static noinline void check_store_iter(struct xarray *xa) 6824e99d4e9SMatthew Wilcox { 6834e99d4e9SMatthew Wilcox unsigned int i, j; 6844e99d4e9SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 20 : 1; 6854e99d4e9SMatthew Wilcox 6864e99d4e9SMatthew Wilcox for (i = 0; i < max_order; i++) { 6874e99d4e9SMatthew Wilcox unsigned int min = 1 << i; 6884e99d4e9SMatthew Wilcox unsigned int max = (2 << i) - 1; 6894e99d4e9SMatthew Wilcox __check_store_iter(xa, 0, i, 0); 6904e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6914e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 0); 6924e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6934e99d4e9SMatthew Wilcox 6944e99d4e9SMatthew Wilcox xa_store_index(xa, min, GFP_KERNEL); 6954e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 1); 6964e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 6974e99d4e9SMatthew Wilcox xa_store_index(xa, max, GFP_KERNEL); 6984e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, 1); 6994e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 7004e99d4e9SMatthew Wilcox 7014e99d4e9SMatthew Wilcox for (j = 0; j < min; j++) 7024e99d4e9SMatthew Wilcox xa_store_index(xa, j, GFP_KERNEL); 7034e99d4e9SMatthew Wilcox __check_store_iter(xa, 0, i, min); 7044e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 7054e99d4e9SMatthew Wilcox for (j = 0; j < min; j++) 7064e99d4e9SMatthew Wilcox xa_store_index(xa, min + j, GFP_KERNEL); 7074e99d4e9SMatthew Wilcox __check_store_iter(xa, min, i, min); 7084e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 7094e99d4e9SMatthew Wilcox } 7104e99d4e9SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 7114e99d4e9SMatthew Wilcox xa_store_index(xa, 63, GFP_KERNEL); 7124e99d4e9SMatthew Wilcox xa_store_index(xa, 65, GFP_KERNEL); 7134e99d4e9SMatthew Wilcox __check_store_iter(xa, 64, 2, 1); 7144e99d4e9SMatthew Wilcox xa_erase_index(xa, 63); 7154e99d4e9SMatthew Wilcox #endif 7164e99d4e9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 7174e99d4e9SMatthew Wilcox } 7184e99d4e9SMatthew Wilcox 719b803b428SMatthew Wilcox static noinline void check_multi_find(struct xarray *xa) 720b803b428SMatthew Wilcox { 721b803b428SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 722b803b428SMatthew Wilcox unsigned long index; 723b803b428SMatthew Wilcox 724b803b428SMatthew Wilcox xa_store_order(xa, 12, 2, xa_mk_value(12), GFP_KERNEL); 725b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, 16, GFP_KERNEL) != NULL); 726b803b428SMatthew Wilcox 727b803b428SMatthew Wilcox index = 0; 728b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != 729b803b428SMatthew Wilcox xa_mk_value(12)); 730b803b428SMatthew Wilcox XA_BUG_ON(xa, index != 12); 731b803b428SMatthew Wilcox index = 13; 732b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != 733b803b428SMatthew Wilcox xa_mk_value(12)); 734b803b428SMatthew Wilcox XA_BUG_ON(xa, (index < 12) || (index >= 16)); 735b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) != 736b803b428SMatthew Wilcox xa_mk_value(16)); 737b803b428SMatthew Wilcox XA_BUG_ON(xa, index != 16); 738b803b428SMatthew Wilcox 739b803b428SMatthew Wilcox xa_erase_index(xa, 12); 740b803b428SMatthew Wilcox xa_erase_index(xa, 16); 741b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 742b803b428SMatthew Wilcox #endif 743b803b428SMatthew Wilcox } 744b803b428SMatthew Wilcox 745b803b428SMatthew Wilcox static noinline void check_multi_find_2(struct xarray *xa) 746b803b428SMatthew Wilcox { 747b803b428SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 10 : 1; 748b803b428SMatthew Wilcox unsigned int i, j; 749b803b428SMatthew Wilcox void *entry; 750b803b428SMatthew Wilcox 751b803b428SMatthew Wilcox for (i = 0; i < max_order; i++) { 752b803b428SMatthew Wilcox unsigned long index = 1UL << i; 753b803b428SMatthew Wilcox for (j = 0; j < index; j++) { 754b803b428SMatthew Wilcox XA_STATE(xas, xa, j + index); 755b803b428SMatthew Wilcox xa_store_index(xa, index - 1, GFP_KERNEL); 756b7677a13SMatthew Wilcox xa_store_order(xa, index, i, xa_mk_index(index), 757b803b428SMatthew Wilcox GFP_KERNEL); 758b803b428SMatthew Wilcox rcu_read_lock(); 759b803b428SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 760b803b428SMatthew Wilcox xa_erase_index(xa, index); 761b803b428SMatthew Wilcox } 762b803b428SMatthew Wilcox rcu_read_unlock(); 763b803b428SMatthew Wilcox xa_erase_index(xa, index - 1); 764b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 765b803b428SMatthew Wilcox } 766b803b428SMatthew Wilcox } 767b803b428SMatthew Wilcox } 768b803b428SMatthew Wilcox 7698229706eSMatthew Wilcox static noinline void check_find_1(struct xarray *xa) 770b803b428SMatthew Wilcox { 771b803b428SMatthew Wilcox unsigned long i, j, k; 772b803b428SMatthew Wilcox 773b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 774b803b428SMatthew Wilcox 775b803b428SMatthew Wilcox /* 776b803b428SMatthew Wilcox * Check xa_find with all pairs between 0 and 99 inclusive, 777b803b428SMatthew Wilcox * starting at every index between 0 and 99 778b803b428SMatthew Wilcox */ 779b803b428SMatthew Wilcox for (i = 0; i < 100; i++) { 780b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 781b803b428SMatthew Wilcox xa_set_mark(xa, i, XA_MARK_0); 782b803b428SMatthew Wilcox for (j = 0; j < i; j++) { 783b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, j, GFP_KERNEL) != 784b803b428SMatthew Wilcox NULL); 785b803b428SMatthew Wilcox xa_set_mark(xa, j, XA_MARK_0); 786b803b428SMatthew Wilcox for (k = 0; k < 100; k++) { 787b803b428SMatthew Wilcox unsigned long index = k; 788b803b428SMatthew Wilcox void *entry = xa_find(xa, &index, ULONG_MAX, 789b803b428SMatthew Wilcox XA_PRESENT); 790b803b428SMatthew Wilcox if (k <= j) 791b803b428SMatthew Wilcox XA_BUG_ON(xa, index != j); 792b803b428SMatthew Wilcox else if (k <= i) 793b803b428SMatthew Wilcox XA_BUG_ON(xa, index != i); 794b803b428SMatthew Wilcox else 795b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 796b803b428SMatthew Wilcox 797b803b428SMatthew Wilcox index = k; 798b803b428SMatthew Wilcox entry = xa_find(xa, &index, ULONG_MAX, 799b803b428SMatthew Wilcox XA_MARK_0); 800b803b428SMatthew Wilcox if (k <= j) 801b803b428SMatthew Wilcox XA_BUG_ON(xa, index != j); 802b803b428SMatthew Wilcox else if (k <= i) 803b803b428SMatthew Wilcox XA_BUG_ON(xa, index != i); 804b803b428SMatthew Wilcox else 805b803b428SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 806b803b428SMatthew Wilcox } 807b803b428SMatthew Wilcox xa_erase_index(xa, j); 808b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, j, XA_MARK_0)); 809b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_get_mark(xa, i, XA_MARK_0)); 810b803b428SMatthew Wilcox } 811b803b428SMatthew Wilcox xa_erase_index(xa, i); 812b803b428SMatthew Wilcox XA_BUG_ON(xa, xa_get_mark(xa, i, XA_MARK_0)); 813b803b428SMatthew Wilcox } 814b803b428SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 8158229706eSMatthew Wilcox } 8168229706eSMatthew Wilcox 8178229706eSMatthew Wilcox static noinline void check_find_2(struct xarray *xa) 8188229706eSMatthew Wilcox { 8198229706eSMatthew Wilcox void *entry; 8204a31896cSMatthew Wilcox unsigned long i, j, index; 8218229706eSMatthew Wilcox 8224a31896cSMatthew Wilcox xa_for_each(xa, index, entry) { 8238229706eSMatthew Wilcox XA_BUG_ON(xa, true); 8248229706eSMatthew Wilcox } 8258229706eSMatthew Wilcox 8268229706eSMatthew Wilcox for (i = 0; i < 1024; i++) { 8278229706eSMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 8288229706eSMatthew Wilcox j = 0; 8294a31896cSMatthew Wilcox xa_for_each(xa, index, entry) { 830b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_mk_index(index) != entry); 8318229706eSMatthew Wilcox XA_BUG_ON(xa, index != j++); 8328229706eSMatthew Wilcox } 8338229706eSMatthew Wilcox } 8348229706eSMatthew Wilcox 8358229706eSMatthew Wilcox xa_destroy(xa); 8368229706eSMatthew Wilcox } 8378229706eSMatthew Wilcox 83848483614SMatthew Wilcox static noinline void check_find_3(struct xarray *xa) 83948483614SMatthew Wilcox { 84048483614SMatthew Wilcox XA_STATE(xas, xa, 0); 84148483614SMatthew Wilcox unsigned long i, j, k; 84248483614SMatthew Wilcox void *entry; 84348483614SMatthew Wilcox 84448483614SMatthew Wilcox for (i = 0; i < 100; i++) { 84548483614SMatthew Wilcox for (j = 0; j < 100; j++) { 846490fd30fSMatthew Wilcox rcu_read_lock(); 84748483614SMatthew Wilcox for (k = 0; k < 100; k++) { 84848483614SMatthew Wilcox xas_set(&xas, j); 84948483614SMatthew Wilcox xas_for_each_marked(&xas, entry, k, XA_MARK_0) 85048483614SMatthew Wilcox ; 85148483614SMatthew Wilcox if (j > k) 85248483614SMatthew Wilcox XA_BUG_ON(xa, 85348483614SMatthew Wilcox xas.xa_node != XAS_RESTART); 85448483614SMatthew Wilcox } 855490fd30fSMatthew Wilcox rcu_read_unlock(); 85648483614SMatthew Wilcox } 85748483614SMatthew Wilcox xa_store_index(xa, i, GFP_KERNEL); 85848483614SMatthew Wilcox xa_set_mark(xa, i, XA_MARK_0); 85948483614SMatthew Wilcox } 86048483614SMatthew Wilcox xa_destroy(xa); 86148483614SMatthew Wilcox } 86248483614SMatthew Wilcox 8638229706eSMatthew Wilcox static noinline void check_find(struct xarray *xa) 8648229706eSMatthew Wilcox { 8658229706eSMatthew Wilcox check_find_1(xa); 8668229706eSMatthew Wilcox check_find_2(xa); 86748483614SMatthew Wilcox check_find_3(xa); 868b803b428SMatthew Wilcox check_multi_find(xa); 869b803b428SMatthew Wilcox check_multi_find_2(xa); 870b803b428SMatthew Wilcox } 871b803b428SMatthew Wilcox 872e21a2955SMatthew Wilcox /* See find_swap_entry() in mm/shmem.c */ 873e21a2955SMatthew Wilcox static noinline unsigned long xa_find_entry(struct xarray *xa, void *item) 874e21a2955SMatthew Wilcox { 875e21a2955SMatthew Wilcox XA_STATE(xas, xa, 0); 876e21a2955SMatthew Wilcox unsigned int checked = 0; 877e21a2955SMatthew Wilcox void *entry; 878e21a2955SMatthew Wilcox 879e21a2955SMatthew Wilcox rcu_read_lock(); 880e21a2955SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) { 881e21a2955SMatthew Wilcox if (xas_retry(&xas, entry)) 882e21a2955SMatthew Wilcox continue; 883e21a2955SMatthew Wilcox if (entry == item) 884e21a2955SMatthew Wilcox break; 885e21a2955SMatthew Wilcox checked++; 886e21a2955SMatthew Wilcox if ((checked % 4) != 0) 887e21a2955SMatthew Wilcox continue; 888e21a2955SMatthew Wilcox xas_pause(&xas); 889e21a2955SMatthew Wilcox } 890e21a2955SMatthew Wilcox rcu_read_unlock(); 891e21a2955SMatthew Wilcox 892e21a2955SMatthew Wilcox return entry ? xas.xa_index : -1; 893e21a2955SMatthew Wilcox } 894e21a2955SMatthew Wilcox 895e21a2955SMatthew Wilcox static noinline void check_find_entry(struct xarray *xa) 896e21a2955SMatthew Wilcox { 897e21a2955SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 898e21a2955SMatthew Wilcox unsigned int order; 899e21a2955SMatthew Wilcox unsigned long offset, index; 900e21a2955SMatthew Wilcox 901e21a2955SMatthew Wilcox for (order = 0; order < 20; order++) { 902e21a2955SMatthew Wilcox for (offset = 0; offset < (1UL << (order + 3)); 903e21a2955SMatthew Wilcox offset += (1UL << order)) { 904e21a2955SMatthew Wilcox for (index = 0; index < (1UL << (order + 5)); 905e21a2955SMatthew Wilcox index += (1UL << order)) { 906e21a2955SMatthew Wilcox xa_store_order(xa, index, order, 907b7677a13SMatthew Wilcox xa_mk_index(index), GFP_KERNEL); 908e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, index) != 909b7677a13SMatthew Wilcox xa_mk_index(index)); 910e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, 911b7677a13SMatthew Wilcox xa_mk_index(index)) != index); 912e21a2955SMatthew Wilcox } 913e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 914e21a2955SMatthew Wilcox xa_destroy(xa); 915e21a2955SMatthew Wilcox } 916e21a2955SMatthew Wilcox } 917e21a2955SMatthew Wilcox #endif 918e21a2955SMatthew Wilcox 919e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 920e21a2955SMatthew Wilcox xa_store_index(xa, ULONG_MAX, GFP_KERNEL); 921e21a2955SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa) != -1); 922b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_find_entry(xa, xa_mk_index(ULONG_MAX)) != -1); 923e21a2955SMatthew Wilcox xa_erase_index(xa, ULONG_MAX); 924e21a2955SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 925e21a2955SMatthew Wilcox } 926e21a2955SMatthew Wilcox 92764d3e9a9SMatthew Wilcox static noinline void check_move_small(struct xarray *xa, unsigned long idx) 92864d3e9a9SMatthew Wilcox { 92964d3e9a9SMatthew Wilcox XA_STATE(xas, xa, 0); 93064d3e9a9SMatthew Wilcox unsigned long i; 93164d3e9a9SMatthew Wilcox 93264d3e9a9SMatthew Wilcox xa_store_index(xa, 0, GFP_KERNEL); 93364d3e9a9SMatthew Wilcox xa_store_index(xa, idx, GFP_KERNEL); 93464d3e9a9SMatthew Wilcox 93564d3e9a9SMatthew Wilcox rcu_read_lock(); 93664d3e9a9SMatthew Wilcox for (i = 0; i < idx * 4; i++) { 93764d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 93864d3e9a9SMatthew Wilcox if (i <= idx) 93964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node == XAS_RESTART); 94064d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 94164d3e9a9SMatthew Wilcox if (i == 0 || i == idx) 942b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(i)); 94364d3e9a9SMatthew Wilcox else 94464d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 94564d3e9a9SMatthew Wilcox } 94664d3e9a9SMatthew Wilcox xas_next(&xas); 94764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 94864d3e9a9SMatthew Wilcox 94964d3e9a9SMatthew Wilcox do { 95064d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 95164d3e9a9SMatthew Wilcox i--; 95264d3e9a9SMatthew Wilcox if (i <= idx) 95364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node == XAS_RESTART); 95464d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != i); 95564d3e9a9SMatthew Wilcox if (i == 0 || i == idx) 956b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(i)); 95764d3e9a9SMatthew Wilcox else 95864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 95964d3e9a9SMatthew Wilcox } while (i > 0); 96064d3e9a9SMatthew Wilcox 96164d3e9a9SMatthew Wilcox xas_set(&xas, ULONG_MAX); 96264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_next(&xas) != NULL); 96364d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 96464d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_next(&xas) != xa_mk_value(0)); 96564d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != 0); 96664d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 96764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 96864d3e9a9SMatthew Wilcox rcu_read_unlock(); 96964d3e9a9SMatthew Wilcox 97064d3e9a9SMatthew Wilcox xa_erase_index(xa, 0); 97164d3e9a9SMatthew Wilcox xa_erase_index(xa, idx); 97264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 97364d3e9a9SMatthew Wilcox } 97464d3e9a9SMatthew Wilcox 97564d3e9a9SMatthew Wilcox static noinline void check_move(struct xarray *xa) 97664d3e9a9SMatthew Wilcox { 97764d3e9a9SMatthew Wilcox XA_STATE(xas, xa, (1 << 16) - 1); 97864d3e9a9SMatthew Wilcox unsigned long i; 97964d3e9a9SMatthew Wilcox 98064d3e9a9SMatthew Wilcox for (i = 0; i < (1 << 16); i++) 98164d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 98264d3e9a9SMatthew Wilcox 98364d3e9a9SMatthew Wilcox rcu_read_lock(); 98464d3e9a9SMatthew Wilcox do { 98564d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 98664d3e9a9SMatthew Wilcox i--; 987b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(i)); 98864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 98964d3e9a9SMatthew Wilcox } while (i != 0); 99064d3e9a9SMatthew Wilcox 99164d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 99264d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 99364d3e9a9SMatthew Wilcox 99464d3e9a9SMatthew Wilcox do { 99564d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 996b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(i)); 99764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 99864d3e9a9SMatthew Wilcox i++; 99964d3e9a9SMatthew Wilcox } while (i < (1 << 16)); 100064d3e9a9SMatthew Wilcox rcu_read_unlock(); 100164d3e9a9SMatthew Wilcox 100264d3e9a9SMatthew Wilcox for (i = (1 << 8); i < (1 << 15); i++) 100364d3e9a9SMatthew Wilcox xa_erase_index(xa, i); 100464d3e9a9SMatthew Wilcox 100564d3e9a9SMatthew Wilcox i = xas.xa_index; 100664d3e9a9SMatthew Wilcox 100764d3e9a9SMatthew Wilcox rcu_read_lock(); 100864d3e9a9SMatthew Wilcox do { 100964d3e9a9SMatthew Wilcox void *entry = xas_prev(&xas); 101064d3e9a9SMatthew Wilcox i--; 101164d3e9a9SMatthew Wilcox if ((i < (1 << 8)) || (i >= (1 << 15))) 1012b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(i)); 101364d3e9a9SMatthew Wilcox else 101464d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 101564d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 101664d3e9a9SMatthew Wilcox } while (i != 0); 101764d3e9a9SMatthew Wilcox 101864d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas_prev(&xas) != NULL); 101964d3e9a9SMatthew Wilcox XA_BUG_ON(xa, xas.xa_index != ULONG_MAX); 102064d3e9a9SMatthew Wilcox 102164d3e9a9SMatthew Wilcox do { 102264d3e9a9SMatthew Wilcox void *entry = xas_next(&xas); 102364d3e9a9SMatthew Wilcox if ((i < (1 << 8)) || (i >= (1 << 15))) 1024b7677a13SMatthew Wilcox XA_BUG_ON(xa, entry != xa_mk_index(i)); 102564d3e9a9SMatthew Wilcox else 102664d3e9a9SMatthew Wilcox XA_BUG_ON(xa, entry != NULL); 102764d3e9a9SMatthew Wilcox XA_BUG_ON(xa, i != xas.xa_index); 102864d3e9a9SMatthew Wilcox i++; 102964d3e9a9SMatthew Wilcox } while (i < (1 << 16)); 103064d3e9a9SMatthew Wilcox rcu_read_unlock(); 103164d3e9a9SMatthew Wilcox 103264d3e9a9SMatthew Wilcox xa_destroy(xa); 103364d3e9a9SMatthew Wilcox 103464d3e9a9SMatthew Wilcox for (i = 0; i < 16; i++) 103564d3e9a9SMatthew Wilcox check_move_small(xa, 1UL << i); 103664d3e9a9SMatthew Wilcox 103764d3e9a9SMatthew Wilcox for (i = 2; i < 16; i++) 103864d3e9a9SMatthew Wilcox check_move_small(xa, (1UL << i) - 1); 103964d3e9a9SMatthew Wilcox } 104064d3e9a9SMatthew Wilcox 10412264f513SMatthew Wilcox static noinline void xa_store_many_order(struct xarray *xa, 10422264f513SMatthew Wilcox unsigned long index, unsigned order) 10432264f513SMatthew Wilcox { 10442264f513SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 10452264f513SMatthew Wilcox unsigned int i = 0; 10462264f513SMatthew Wilcox 10472264f513SMatthew Wilcox do { 10482264f513SMatthew Wilcox xas_lock(&xas); 10492264f513SMatthew Wilcox XA_BUG_ON(xa, xas_find_conflict(&xas)); 10502264f513SMatthew Wilcox xas_create_range(&xas); 10512264f513SMatthew Wilcox if (xas_error(&xas)) 10522264f513SMatthew Wilcox goto unlock; 10532264f513SMatthew Wilcox for (i = 0; i < (1U << order); i++) { 1054b7677a13SMatthew Wilcox XA_BUG_ON(xa, xas_store(&xas, xa_mk_index(index + i))); 10552264f513SMatthew Wilcox xas_next(&xas); 10562264f513SMatthew Wilcox } 10572264f513SMatthew Wilcox unlock: 10582264f513SMatthew Wilcox xas_unlock(&xas); 10592264f513SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 10602264f513SMatthew Wilcox 10612264f513SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 10622264f513SMatthew Wilcox } 10632264f513SMatthew Wilcox 10642264f513SMatthew Wilcox static noinline void check_create_range_1(struct xarray *xa, 10652264f513SMatthew Wilcox unsigned long index, unsigned order) 10662264f513SMatthew Wilcox { 10672264f513SMatthew Wilcox unsigned long i; 10682264f513SMatthew Wilcox 10692264f513SMatthew Wilcox xa_store_many_order(xa, index, order); 10702264f513SMatthew Wilcox for (i = index; i < index + (1UL << order); i++) 10712264f513SMatthew Wilcox xa_erase_index(xa, i); 10722264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 10732264f513SMatthew Wilcox } 10742264f513SMatthew Wilcox 10752264f513SMatthew Wilcox static noinline void check_create_range_2(struct xarray *xa, unsigned order) 10762264f513SMatthew Wilcox { 10772264f513SMatthew Wilcox unsigned long i; 10782264f513SMatthew Wilcox unsigned long nr = 1UL << order; 10792264f513SMatthew Wilcox 10802264f513SMatthew Wilcox for (i = 0; i < nr * nr; i += nr) 10812264f513SMatthew Wilcox xa_store_many_order(xa, i, order); 10822264f513SMatthew Wilcox for (i = 0; i < nr * nr; i++) 10832264f513SMatthew Wilcox xa_erase_index(xa, i); 10842264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 10852264f513SMatthew Wilcox } 10862264f513SMatthew Wilcox 10872264f513SMatthew Wilcox static noinline void check_create_range_3(void) 10882264f513SMatthew Wilcox { 10892264f513SMatthew Wilcox XA_STATE(xas, NULL, 0); 10902264f513SMatthew Wilcox xas_set_err(&xas, -EEXIST); 10912264f513SMatthew Wilcox xas_create_range(&xas); 10922264f513SMatthew Wilcox XA_BUG_ON(NULL, xas_error(&xas) != -EEXIST); 10932264f513SMatthew Wilcox } 10942264f513SMatthew Wilcox 10952264f513SMatthew Wilcox static noinline void check_create_range_4(struct xarray *xa, 10962264f513SMatthew Wilcox unsigned long index, unsigned order) 10972264f513SMatthew Wilcox { 10982264f513SMatthew Wilcox XA_STATE_ORDER(xas, xa, index, order); 10992264f513SMatthew Wilcox unsigned long base = xas.xa_index; 11002264f513SMatthew Wilcox unsigned long i = 0; 11012264f513SMatthew Wilcox 11022264f513SMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 11032264f513SMatthew Wilcox do { 11042264f513SMatthew Wilcox xas_lock(&xas); 11052264f513SMatthew Wilcox xas_create_range(&xas); 11062264f513SMatthew Wilcox if (xas_error(&xas)) 11072264f513SMatthew Wilcox goto unlock; 11082264f513SMatthew Wilcox for (i = 0; i < (1UL << order); i++) { 1109b7677a13SMatthew Wilcox void *old = xas_store(&xas, xa_mk_index(base + i)); 11102264f513SMatthew Wilcox if (xas.xa_index == index) 1111b7677a13SMatthew Wilcox XA_BUG_ON(xa, old != xa_mk_index(base + i)); 11122264f513SMatthew Wilcox else 11132264f513SMatthew Wilcox XA_BUG_ON(xa, old != NULL); 11142264f513SMatthew Wilcox xas_next(&xas); 11152264f513SMatthew Wilcox } 11162264f513SMatthew Wilcox unlock: 11172264f513SMatthew Wilcox xas_unlock(&xas); 11182264f513SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 11192264f513SMatthew Wilcox 11202264f513SMatthew Wilcox XA_BUG_ON(xa, xas_error(&xas)); 11212264f513SMatthew Wilcox 11222264f513SMatthew Wilcox for (i = base; i < base + (1UL << order); i++) 11232264f513SMatthew Wilcox xa_erase_index(xa, i); 11242264f513SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 11252264f513SMatthew Wilcox } 11262264f513SMatthew Wilcox 11272264f513SMatthew Wilcox static noinline void check_create_range(struct xarray *xa) 11282264f513SMatthew Wilcox { 11292264f513SMatthew Wilcox unsigned int order; 11302264f513SMatthew Wilcox unsigned int max_order = IS_ENABLED(CONFIG_XARRAY_MULTI) ? 12 : 1; 11312264f513SMatthew Wilcox 11322264f513SMatthew Wilcox for (order = 0; order < max_order; order++) { 11332264f513SMatthew Wilcox check_create_range_1(xa, 0, order); 11342264f513SMatthew Wilcox check_create_range_1(xa, 1U << order, order); 11352264f513SMatthew Wilcox check_create_range_1(xa, 2U << order, order); 11362264f513SMatthew Wilcox check_create_range_1(xa, 3U << order, order); 11372264f513SMatthew Wilcox check_create_range_1(xa, 1U << 24, order); 11382264f513SMatthew Wilcox if (order < 10) 11392264f513SMatthew Wilcox check_create_range_2(xa, order); 11402264f513SMatthew Wilcox 11412264f513SMatthew Wilcox check_create_range_4(xa, 0, order); 11422264f513SMatthew Wilcox check_create_range_4(xa, 1U << order, order); 11432264f513SMatthew Wilcox check_create_range_4(xa, 2U << order, order); 11442264f513SMatthew Wilcox check_create_range_4(xa, 3U << order, order); 11452264f513SMatthew Wilcox check_create_range_4(xa, 1U << 24, order); 11462264f513SMatthew Wilcox 11472264f513SMatthew Wilcox check_create_range_4(xa, 1, order); 11482264f513SMatthew Wilcox check_create_range_4(xa, (1U << order) + 1, order); 11492264f513SMatthew Wilcox check_create_range_4(xa, (2U << order) + 1, order); 11502264f513SMatthew Wilcox check_create_range_4(xa, (2U << order) - 1, order); 11512264f513SMatthew Wilcox check_create_range_4(xa, (3U << order) + 1, order); 11522264f513SMatthew Wilcox check_create_range_4(xa, (3U << order) - 1, order); 11532264f513SMatthew Wilcox check_create_range_4(xa, (1U << 24) + 1, order); 11542264f513SMatthew Wilcox } 11552264f513SMatthew Wilcox 11562264f513SMatthew Wilcox check_create_range_3(); 11572264f513SMatthew Wilcox } 11582264f513SMatthew Wilcox 11590e9446c3SMatthew Wilcox static noinline void __check_store_range(struct xarray *xa, unsigned long first, 11600e9446c3SMatthew Wilcox unsigned long last) 11610e9446c3SMatthew Wilcox { 11620e9446c3SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 1163b7677a13SMatthew Wilcox xa_store_range(xa, first, last, xa_mk_index(first), GFP_KERNEL); 11640e9446c3SMatthew Wilcox 1165b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, first) != xa_mk_index(first)); 1166b7677a13SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, last) != xa_mk_index(first)); 11670e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, first - 1) != NULL); 11680e9446c3SMatthew Wilcox XA_BUG_ON(xa, xa_load(xa, last + 1) != NULL); 11690e9446c3SMatthew Wilcox 11700e9446c3SMatthew Wilcox xa_store_range(xa, first, last, NULL, GFP_KERNEL); 11710e9446c3SMatthew Wilcox #endif 11720e9446c3SMatthew Wilcox 11730e9446c3SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 11740e9446c3SMatthew Wilcox } 11750e9446c3SMatthew Wilcox 11760e9446c3SMatthew Wilcox static noinline void check_store_range(struct xarray *xa) 11770e9446c3SMatthew Wilcox { 11780e9446c3SMatthew Wilcox unsigned long i, j; 11790e9446c3SMatthew Wilcox 11800e9446c3SMatthew Wilcox for (i = 0; i < 128; i++) { 11810e9446c3SMatthew Wilcox for (j = i; j < 128; j++) { 11820e9446c3SMatthew Wilcox __check_store_range(xa, i, j); 11830e9446c3SMatthew Wilcox __check_store_range(xa, 128 + i, 128 + j); 11840e9446c3SMatthew Wilcox __check_store_range(xa, 4095 + i, 4095 + j); 11850e9446c3SMatthew Wilcox __check_store_range(xa, 4096 + i, 4096 + j); 11860e9446c3SMatthew Wilcox __check_store_range(xa, 123456 + i, 123456 + j); 11875404a7f1SMatthew Wilcox __check_store_range(xa, (1 << 24) + i, (1 << 24) + j); 11880e9446c3SMatthew Wilcox } 11890e9446c3SMatthew Wilcox } 11900e9446c3SMatthew Wilcox } 11910e9446c3SMatthew Wilcox 119276b4e529SMatthew Wilcox static void check_align_1(struct xarray *xa, char *name) 119376b4e529SMatthew Wilcox { 119476b4e529SMatthew Wilcox int i; 119576b4e529SMatthew Wilcox unsigned int id; 119676b4e529SMatthew Wilcox unsigned long index; 119776b4e529SMatthew Wilcox void *entry; 119876b4e529SMatthew Wilcox 119976b4e529SMatthew Wilcox for (i = 0; i < 8; i++) { 120076b4e529SMatthew Wilcox id = 0; 120176b4e529SMatthew Wilcox XA_BUG_ON(xa, xa_alloc(xa, &id, UINT_MAX, name + i, GFP_KERNEL) 120276b4e529SMatthew Wilcox != 0); 120376b4e529SMatthew Wilcox XA_BUG_ON(xa, id != i); 120476b4e529SMatthew Wilcox } 120576b4e529SMatthew Wilcox xa_for_each(xa, index, entry) 120676b4e529SMatthew Wilcox XA_BUG_ON(xa, xa_is_err(entry)); 120776b4e529SMatthew Wilcox xa_destroy(xa); 120876b4e529SMatthew Wilcox } 120976b4e529SMatthew Wilcox 121076b4e529SMatthew Wilcox static noinline void check_align(struct xarray *xa) 121176b4e529SMatthew Wilcox { 121276b4e529SMatthew Wilcox char name[] = "Motorola 68000"; 121376b4e529SMatthew Wilcox 121476b4e529SMatthew Wilcox check_align_1(xa, name); 121576b4e529SMatthew Wilcox check_align_1(xa, name + 1); 121676b4e529SMatthew Wilcox check_align_1(xa, name + 2); 121776b4e529SMatthew Wilcox check_align_1(xa, name + 3); 121876b4e529SMatthew Wilcox // check_align_2(xa, name); 121976b4e529SMatthew Wilcox } 122076b4e529SMatthew Wilcox 1221a97e7904SMatthew Wilcox static LIST_HEAD(shadow_nodes); 1222a97e7904SMatthew Wilcox 1223a97e7904SMatthew Wilcox static void test_update_node(struct xa_node *node) 1224a97e7904SMatthew Wilcox { 1225a97e7904SMatthew Wilcox if (node->count && node->count == node->nr_values) { 1226a97e7904SMatthew Wilcox if (list_empty(&node->private_list)) 1227a97e7904SMatthew Wilcox list_add(&shadow_nodes, &node->private_list); 1228a97e7904SMatthew Wilcox } else { 1229a97e7904SMatthew Wilcox if (!list_empty(&node->private_list)) 1230a97e7904SMatthew Wilcox list_del_init(&node->private_list); 1231a97e7904SMatthew Wilcox } 1232a97e7904SMatthew Wilcox } 1233a97e7904SMatthew Wilcox 1234a97e7904SMatthew Wilcox static noinline void shadow_remove(struct xarray *xa) 1235a97e7904SMatthew Wilcox { 1236a97e7904SMatthew Wilcox struct xa_node *node; 1237a97e7904SMatthew Wilcox 1238a97e7904SMatthew Wilcox xa_lock(xa); 1239a97e7904SMatthew Wilcox while ((node = list_first_entry_or_null(&shadow_nodes, 1240a97e7904SMatthew Wilcox struct xa_node, private_list))) { 1241a97e7904SMatthew Wilcox XA_STATE(xas, node->array, 0); 1242a97e7904SMatthew Wilcox XA_BUG_ON(xa, node->array != xa); 1243a97e7904SMatthew Wilcox list_del_init(&node->private_list); 1244a97e7904SMatthew Wilcox xas.xa_node = xa_parent_locked(node->array, node); 1245a97e7904SMatthew Wilcox xas.xa_offset = node->offset; 1246a97e7904SMatthew Wilcox xas.xa_shift = node->shift + XA_CHUNK_SHIFT; 1247a97e7904SMatthew Wilcox xas_set_update(&xas, test_update_node); 1248a97e7904SMatthew Wilcox xas_store(&xas, NULL); 1249a97e7904SMatthew Wilcox } 1250a97e7904SMatthew Wilcox xa_unlock(xa); 1251a97e7904SMatthew Wilcox } 1252a97e7904SMatthew Wilcox 1253a97e7904SMatthew Wilcox static noinline void check_workingset(struct xarray *xa, unsigned long index) 1254a97e7904SMatthew Wilcox { 1255a97e7904SMatthew Wilcox XA_STATE(xas, xa, index); 1256a97e7904SMatthew Wilcox xas_set_update(&xas, test_update_node); 1257a97e7904SMatthew Wilcox 1258a97e7904SMatthew Wilcox do { 1259a97e7904SMatthew Wilcox xas_lock(&xas); 1260a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(0)); 1261a97e7904SMatthew Wilcox xas_next(&xas); 1262a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(1)); 1263a97e7904SMatthew Wilcox xas_unlock(&xas); 1264a97e7904SMatthew Wilcox } while (xas_nomem(&xas, GFP_KERNEL)); 1265a97e7904SMatthew Wilcox 1266a97e7904SMatthew Wilcox XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1267a97e7904SMatthew Wilcox 1268a97e7904SMatthew Wilcox xas_lock(&xas); 1269a97e7904SMatthew Wilcox xas_next(&xas); 1270a97e7904SMatthew Wilcox xas_store(&xas, &xas); 1271a97e7904SMatthew Wilcox XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1272a97e7904SMatthew Wilcox 1273a97e7904SMatthew Wilcox xas_store(&xas, xa_mk_value(2)); 1274a97e7904SMatthew Wilcox xas_unlock(&xas); 1275a97e7904SMatthew Wilcox XA_BUG_ON(xa, list_empty(&shadow_nodes)); 1276a97e7904SMatthew Wilcox 1277a97e7904SMatthew Wilcox shadow_remove(xa); 1278a97e7904SMatthew Wilcox XA_BUG_ON(xa, !list_empty(&shadow_nodes)); 1279a97e7904SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1280a97e7904SMatthew Wilcox } 1281a97e7904SMatthew Wilcox 1282d6427f81SMatthew Wilcox /* 1283d6427f81SMatthew Wilcox * Check that the pointer / value / sibling entries are accounted the 1284d6427f81SMatthew Wilcox * way we expect them to be. 1285d6427f81SMatthew Wilcox */ 1286d6427f81SMatthew Wilcox static noinline void check_account(struct xarray *xa) 1287d6427f81SMatthew Wilcox { 1288d6427f81SMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 1289d6427f81SMatthew Wilcox unsigned int order; 1290d6427f81SMatthew Wilcox 1291d6427f81SMatthew Wilcox for (order = 1; order < 12; order++) { 1292d6427f81SMatthew Wilcox XA_STATE(xas, xa, 1 << order); 1293d6427f81SMatthew Wilcox 1294d6427f81SMatthew Wilcox xa_store_order(xa, 0, order, xa, GFP_KERNEL); 1295fffc9a26SMatthew Wilcox rcu_read_lock(); 1296d6427f81SMatthew Wilcox xas_load(&xas); 1297d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count == 0); 1298d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count > (1 << order)); 1299d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1300fffc9a26SMatthew Wilcox rcu_read_unlock(); 1301d6427f81SMatthew Wilcox 1302b7677a13SMatthew Wilcox xa_store_order(xa, 1 << order, order, xa_mk_index(1UL << order), 1303d6427f81SMatthew Wilcox GFP_KERNEL); 1304d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->count != xas.xa_node->nr_values * 2); 1305d6427f81SMatthew Wilcox 1306d6427f81SMatthew Wilcox xa_erase(xa, 1 << order); 1307d6427f81SMatthew Wilcox XA_BUG_ON(xa, xas.xa_node->nr_values != 0); 1308d6427f81SMatthew Wilcox 1309d6427f81SMatthew Wilcox xa_erase(xa, 0); 1310d6427f81SMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1311d6427f81SMatthew Wilcox } 1312d6427f81SMatthew Wilcox #endif 1313d6427f81SMatthew Wilcox } 1314d6427f81SMatthew Wilcox 1315687149fcSMatthew Wilcox static noinline void check_destroy(struct xarray *xa) 1316687149fcSMatthew Wilcox { 1317687149fcSMatthew Wilcox unsigned long index; 1318687149fcSMatthew Wilcox 1319687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1320687149fcSMatthew Wilcox 1321687149fcSMatthew Wilcox /* Destroying an empty array is a no-op */ 1322687149fcSMatthew Wilcox xa_destroy(xa); 1323687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1324687149fcSMatthew Wilcox 1325687149fcSMatthew Wilcox /* Destroying an array with a single entry */ 1326687149fcSMatthew Wilcox for (index = 0; index < 1000; index++) { 1327687149fcSMatthew Wilcox xa_store_index(xa, index, GFP_KERNEL); 1328687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1329687149fcSMatthew Wilcox xa_destroy(xa); 1330687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1331687149fcSMatthew Wilcox } 1332687149fcSMatthew Wilcox 1333687149fcSMatthew Wilcox /* Destroying an array with a single entry at ULONG_MAX */ 1334687149fcSMatthew Wilcox xa_store(xa, ULONG_MAX, xa, GFP_KERNEL); 1335687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1336687149fcSMatthew Wilcox xa_destroy(xa); 1337687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1338687149fcSMatthew Wilcox 1339687149fcSMatthew Wilcox #ifdef CONFIG_XARRAY_MULTI 1340687149fcSMatthew Wilcox /* Destroying an array with a multi-index entry */ 1341687149fcSMatthew Wilcox xa_store_order(xa, 1 << 11, 11, xa, GFP_KERNEL); 1342687149fcSMatthew Wilcox XA_BUG_ON(xa, xa_empty(xa)); 1343687149fcSMatthew Wilcox xa_destroy(xa); 1344687149fcSMatthew Wilcox XA_BUG_ON(xa, !xa_empty(xa)); 1345687149fcSMatthew Wilcox #endif 1346687149fcSMatthew Wilcox } 1347687149fcSMatthew Wilcox 134858d6ea30SMatthew Wilcox static DEFINE_XARRAY(array); 1349ad3d6c72SMatthew Wilcox 1350ad3d6c72SMatthew Wilcox static int xarray_checks(void) 1351ad3d6c72SMatthew Wilcox { 135258d6ea30SMatthew Wilcox check_xa_err(&array); 1353b803b428SMatthew Wilcox check_xas_retry(&array); 1354ad3d6c72SMatthew Wilcox check_xa_load(&array); 13559b89a035SMatthew Wilcox check_xa_mark(&array); 135658d6ea30SMatthew Wilcox check_xa_shrink(&array); 1357b803b428SMatthew Wilcox check_xas_erase(&array); 135841aec91fSMatthew Wilcox check_cmpxchg(&array); 13599f14d4f1SMatthew Wilcox check_reserve(&array); 136058d6ea30SMatthew Wilcox check_multi_store(&array); 1361371c752dSMatthew Wilcox check_xa_alloc(); 1362b803b428SMatthew Wilcox check_find(&array); 1363e21a2955SMatthew Wilcox check_find_entry(&array); 1364d6427f81SMatthew Wilcox check_account(&array); 1365687149fcSMatthew Wilcox check_destroy(&array); 136664d3e9a9SMatthew Wilcox check_move(&array); 13672264f513SMatthew Wilcox check_create_range(&array); 13680e9446c3SMatthew Wilcox check_store_range(&array); 13694e99d4e9SMatthew Wilcox check_store_iter(&array); 137076b4e529SMatthew Wilcox check_align(&xa0); 1371ad3d6c72SMatthew Wilcox 1372a97e7904SMatthew Wilcox check_workingset(&array, 0); 1373a97e7904SMatthew Wilcox check_workingset(&array, 64); 1374a97e7904SMatthew Wilcox check_workingset(&array, 4096); 1375a97e7904SMatthew Wilcox 1376ad3d6c72SMatthew Wilcox printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); 1377ad3d6c72SMatthew Wilcox return (tests_run == tests_passed) ? 0 : -EINVAL; 1378ad3d6c72SMatthew Wilcox } 1379ad3d6c72SMatthew Wilcox 1380ad3d6c72SMatthew Wilcox static void xarray_exit(void) 1381ad3d6c72SMatthew Wilcox { 1382ad3d6c72SMatthew Wilcox } 1383ad3d6c72SMatthew Wilcox 1384ad3d6c72SMatthew Wilcox module_init(xarray_checks); 1385ad3d6c72SMatthew Wilcox module_exit(xarray_exit); 1386ad3d6c72SMatthew Wilcox MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>"); 1387ad3d6c72SMatthew Wilcox MODULE_LICENSE("GPL"); 1388