1 // SPDX-License-Identifier: GPL-2.0+ 2 /* 3 * test_xarray.c: Test the XArray API 4 * Copyright (c) 2017-2018 Microsoft Corporation 5 * Author: Matthew Wilcox <[email protected]> 6 */ 7 8 #include <linux/xarray.h> 9 #include <linux/module.h> 10 11 static unsigned int tests_run; 12 static unsigned int tests_passed; 13 14 #ifndef XA_DEBUG 15 # ifdef __KERNEL__ 16 void xa_dump(const struct xarray *xa) { } 17 # endif 18 #undef XA_BUG_ON 19 #define XA_BUG_ON(xa, x) do { \ 20 tests_run++; \ 21 if (x) { \ 22 printk("BUG at %s:%d\n", __func__, __LINE__); \ 23 xa_dump(xa); \ 24 dump_stack(); \ 25 } else { \ 26 tests_passed++; \ 27 } \ 28 } while (0) 29 #endif 30 31 static void *xa_store_index(struct xarray *xa, unsigned long index, gfp_t gfp) 32 { 33 radix_tree_insert(xa, index, xa_mk_value(index)); 34 return NULL; 35 } 36 37 static void xa_erase_index(struct xarray *xa, unsigned long index) 38 { 39 radix_tree_delete(xa, index); 40 } 41 42 static noinline void check_xa_load(struct xarray *xa) 43 { 44 unsigned long i, j; 45 46 for (i = 0; i < 1024; i++) { 47 for (j = 0; j < 1024; j++) { 48 void *entry = xa_load(xa, j); 49 if (j < i) 50 XA_BUG_ON(xa, xa_to_value(entry) != j); 51 else 52 XA_BUG_ON(xa, entry); 53 } 54 XA_BUG_ON(xa, xa_store_index(xa, i, GFP_KERNEL) != NULL); 55 } 56 57 for (i = 0; i < 1024; i++) { 58 for (j = 0; j < 1024; j++) { 59 void *entry = xa_load(xa, j); 60 if (j >= i) 61 XA_BUG_ON(xa, xa_to_value(entry) != j); 62 else 63 XA_BUG_ON(xa, entry); 64 } 65 xa_erase_index(xa, i); 66 } 67 XA_BUG_ON(xa, !xa_empty(xa)); 68 } 69 70 static noinline void check_xa_mark_1(struct xarray *xa, unsigned long index) 71 { 72 /* NULL elements have no marks set */ 73 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 74 xa_set_mark(xa, index, XA_MARK_0); 75 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 76 77 /* Storing a pointer will not make a mark appear */ 78 XA_BUG_ON(xa, xa_store_index(xa, index, GFP_KERNEL) != NULL); 79 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 80 xa_set_mark(xa, index, XA_MARK_0); 81 XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0)); 82 83 /* Setting one mark will not set another mark */ 84 XA_BUG_ON(xa, xa_get_mark(xa, index + 1, XA_MARK_0)); 85 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_1)); 86 87 /* Storing NULL clears marks, and they can't be set again */ 88 xa_erase_index(xa, index); 89 XA_BUG_ON(xa, !xa_empty(xa)); 90 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 91 xa_set_mark(xa, index, XA_MARK_0); 92 XA_BUG_ON(xa, xa_get_mark(xa, index, XA_MARK_0)); 93 } 94 95 static noinline void check_xa_mark(struct xarray *xa) 96 { 97 unsigned long index; 98 99 for (index = 0; index < 16384; index += 4) 100 check_xa_mark_1(xa, index); 101 } 102 103 static RADIX_TREE(array, GFP_KERNEL); 104 105 static int xarray_checks(void) 106 { 107 check_xa_load(&array); 108 check_xa_mark(&array); 109 110 printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); 111 return (tests_run == tests_passed) ? 0 : -EINVAL; 112 } 113 114 static void xarray_exit(void) 115 { 116 } 117 118 module_init(xarray_checks); 119 module_exit(xarray_exit); 120 MODULE_AUTHOR("Matthew Wilcox <[email protected]>"); 121 MODULE_LICENSE("GPL"); 122