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