1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * iteration_check.c: test races having to do with xarray iteration 4 * Copyright (c) 2016 Intel Corporation 5 * Author: Ross Zwisler <ross.zwisler@linux.intel.com> 6 */ 7 #include <pthread.h> 8 #include "test.h" 9 10 #define NUM_THREADS 5 11 #define MAX_IDX 100 12 #define TAG XA_MARK_0 13 #define NEW_TAG XA_MARK_1 14 15 static pthread_t threads[NUM_THREADS]; 16 static unsigned int seeds[3]; 17 static DEFINE_XARRAY(array); 18 static bool test_complete; 19 static int max_order; 20 21 void my_item_insert(struct xarray *xa, unsigned long index) 22 { 23 XA_STATE(xas, xa, index); 24 struct item *item = item_create(index, 0); 25 int order; 26 27 retry: 28 xas_lock(&xas); 29 for (order = max_order; order >= 0; order--) { 30 xas_set_order(&xas, index, order); 31 item->order = order; 32 if (xas_find_conflict(&xas)) 33 continue; 34 xas_store(&xas, item); 35 xas_set_mark(&xas, TAG); 36 break; 37 } 38 xas_unlock(&xas); 39 if (xas_nomem(&xas, GFP_KERNEL)) 40 goto retry; 41 if (order < 0) 42 free(item); 43 } 44 45 /* relentlessly fill the array with tagged entries */ 46 static void *add_entries_fn(void *arg) 47 { 48 rcu_register_thread(); 49 50 while (!test_complete) { 51 unsigned long pgoff; 52 53 for (pgoff = 0; pgoff < MAX_IDX; pgoff++) { 54 my_item_insert(&array, pgoff); 55 } 56 } 57 58 rcu_unregister_thread(); 59 60 return NULL; 61 } 62 63 /* 64 * Iterate over tagged entries, retrying when we find ourselves in a deleted 65 * node and randomly pausing the iteration. 66 */ 67 static void *tagged_iteration_fn(void *arg) 68 { 69 XA_STATE(xas, &array, 0); 70 void *entry; 71 72 rcu_register_thread(); 73 74 while (!test_complete) { 75 xas_set(&xas, 0); 76 rcu_read_lock(); 77 xas_for_each_marked(&xas, entry, ULONG_MAX, TAG) { 78 if (xas_retry(&xas, entry)) 79 continue; 80 81 if (rand_r(&seeds[0]) % 50 == 0) { 82 xas_pause(&xas); 83 rcu_read_unlock(); 84 rcu_barrier(); 85 rcu_read_lock(); 86 } 87 } 88 rcu_read_unlock(); 89 } 90 91 rcu_unregister_thread(); 92 93 return NULL; 94 } 95 96 /* 97 * Iterate over the entries, retrying when we find ourselves in a deleted 98 * node and randomly pausing the iteration. 99 */ 100 static void *untagged_iteration_fn(void *arg) 101 { 102 XA_STATE(xas, &array, 0); 103 void *entry; 104 105 rcu_register_thread(); 106 107 while (!test_complete) { 108 xas_set(&xas, 0); 109 rcu_read_lock(); 110 xas_for_each(&xas, entry, ULONG_MAX) { 111 if (xas_retry(&xas, entry)) 112 continue; 113 114 if (rand_r(&seeds[1]) % 50 == 0) { 115 xas_pause(&xas); 116 rcu_read_unlock(); 117 rcu_barrier(); 118 rcu_read_lock(); 119 } 120 } 121 rcu_read_unlock(); 122 } 123 124 rcu_unregister_thread(); 125 126 return NULL; 127 } 128 129 /* 130 * Randomly remove entries to help induce retries in the 131 * two iteration functions. 132 */ 133 static void *remove_entries_fn(void *arg) 134 { 135 rcu_register_thread(); 136 137 while (!test_complete) { 138 int pgoff; 139 struct item *item; 140 141 pgoff = rand_r(&seeds[2]) % MAX_IDX; 142 143 item = xa_erase(&array, pgoff); 144 if (item) 145 item_free(item, pgoff); 146 } 147 148 rcu_unregister_thread(); 149 150 return NULL; 151 } 152 153 static void *tag_entries_fn(void *arg) 154 { 155 rcu_register_thread(); 156 157 while (!test_complete) { 158 tag_tagged_items(&array, 0, MAX_IDX, 10, TAG, NEW_TAG); 159 } 160 rcu_unregister_thread(); 161 return NULL; 162 } 163 164 /* This is a unit test for a bug found by the syzkaller tester */ 165 void iteration_test(unsigned order, unsigned test_duration) 166 { 167 int i; 168 169 printv(1, "Running %siteration tests for %d seconds\n", 170 order > 0 ? "multiorder " : "", test_duration); 171 172 max_order = order; 173 test_complete = false; 174 175 for (i = 0; i < 3; i++) 176 seeds[i] = rand(); 177 178 if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) { 179 perror("create tagged iteration thread"); 180 exit(1); 181 } 182 if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) { 183 perror("create untagged iteration thread"); 184 exit(1); 185 } 186 if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) { 187 perror("create add entry thread"); 188 exit(1); 189 } 190 if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) { 191 perror("create remove entry thread"); 192 exit(1); 193 } 194 if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) { 195 perror("create tag entry thread"); 196 exit(1); 197 } 198 199 sleep(test_duration); 200 test_complete = true; 201 202 for (i = 0; i < NUM_THREADS; i++) { 203 if (pthread_join(threads[i], NULL)) { 204 perror("pthread_join"); 205 exit(1); 206 } 207 } 208 209 item_kill_tree(&array); 210 } 211