1 /* 2 * rcuq_test.c 3 * 4 * usage: rcuq_test <readers> <duration> 5 * 6 * This program is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * This program is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 19 * 20 * Copyright (c) 2013 Mike D. Day, IBM Corporation. 21 */ 22 23 #include "qemu/osdep.h" 24 #include "qemu/atomic.h" 25 #include "qemu/rcu.h" 26 #include "qemu/thread.h" 27 #include "qemu/rcu_queue.h" 28 29 /* 30 * Test variables. 31 */ 32 33 static QemuMutex counts_mutex; 34 static long long n_reads = 0LL; 35 static long long n_updates = 0LL; 36 static long long n_reclaims = 0LL; 37 static long long n_nodes_removed = 0LL; 38 static long long n_nodes = 0LL; 39 static int g_test_in_charge = 0; 40 41 static int nthreadsrunning; 42 43 #define GOFLAG_INIT 0 44 #define GOFLAG_RUN 1 45 #define GOFLAG_STOP 2 46 47 static volatile int goflag = GOFLAG_INIT; 48 49 #define RCU_READ_RUN 1000 50 #define RCU_UPDATE_RUN 10 51 #define NR_THREADS 100 52 #define RCU_Q_LEN 100 53 54 static QemuThread threads[NR_THREADS]; 55 static struct rcu_reader_data *data[NR_THREADS]; 56 static int n_threads; 57 58 static int select_random_el(int max) 59 { 60 return (rand() % max); 61 } 62 63 64 static void create_thread(void *(*func)(void *)) 65 { 66 if (n_threads >= NR_THREADS) { 67 fprintf(stderr, "Thread limit of %d exceeded!\n", NR_THREADS); 68 exit(-1); 69 } 70 qemu_thread_create(&threads[n_threads], "test", func, &data[n_threads], 71 QEMU_THREAD_JOINABLE); 72 n_threads++; 73 } 74 75 static void wait_all_threads(void) 76 { 77 int i; 78 79 for (i = 0; i < n_threads; i++) { 80 qemu_thread_join(&threads[i]); 81 } 82 n_threads = 0; 83 } 84 85 86 struct list_element { 87 QLIST_ENTRY(list_element) entry; 88 struct rcu_head rcu; 89 }; 90 91 static void reclaim_list_el(struct rcu_head *prcu) 92 { 93 struct list_element *el = container_of(prcu, struct list_element, rcu); 94 g_free(el); 95 /* Accessed only from call_rcu thread. */ 96 n_reclaims++; 97 } 98 99 static QLIST_HEAD(q_list_head, list_element) Q_list_head; 100 101 static void *rcu_q_reader(void *arg) 102 { 103 long long n_reads_local = 0; 104 struct list_element *el; 105 106 rcu_register_thread(); 107 108 *(struct rcu_reader_data **)arg = &rcu_reader; 109 atomic_inc(&nthreadsrunning); 110 while (goflag == GOFLAG_INIT) { 111 g_usleep(1000); 112 } 113 114 while (goflag == GOFLAG_RUN) { 115 rcu_read_lock(); 116 QLIST_FOREACH_RCU(el, &Q_list_head, entry) { 117 n_reads_local++; 118 if (goflag == GOFLAG_STOP) { 119 break; 120 } 121 } 122 rcu_read_unlock(); 123 124 g_usleep(100); 125 } 126 qemu_mutex_lock(&counts_mutex); 127 n_reads += n_reads_local; 128 qemu_mutex_unlock(&counts_mutex); 129 130 rcu_unregister_thread(); 131 return NULL; 132 } 133 134 135 static void *rcu_q_updater(void *arg) 136 { 137 int j, target_el; 138 long long n_nodes_local = 0; 139 long long n_updates_local = 0; 140 long long n_removed_local = 0; 141 struct list_element *el, *prev_el; 142 143 *(struct rcu_reader_data **)arg = &rcu_reader; 144 atomic_inc(&nthreadsrunning); 145 while (goflag == GOFLAG_INIT) { 146 g_usleep(1000); 147 } 148 149 while (goflag == GOFLAG_RUN) { 150 target_el = select_random_el(RCU_Q_LEN); 151 j = 0; 152 /* FOREACH_RCU could work here but let's use both macros */ 153 QLIST_FOREACH_SAFE_RCU(prev_el, &Q_list_head, entry, el) { 154 j++; 155 if (target_el == j) { 156 QLIST_REMOVE_RCU(prev_el, entry); 157 /* may be more than one updater in the future */ 158 call_rcu1(&prev_el->rcu, reclaim_list_el); 159 n_removed_local++; 160 break; 161 } 162 } 163 if (goflag == GOFLAG_STOP) { 164 break; 165 } 166 target_el = select_random_el(RCU_Q_LEN); 167 j = 0; 168 QLIST_FOREACH_RCU(el, &Q_list_head, entry) { 169 j++; 170 if (target_el == j) { 171 prev_el = g_new(struct list_element, 1); 172 n_nodes += n_nodes_local; 173 QLIST_INSERT_BEFORE_RCU(el, prev_el, entry); 174 break; 175 } 176 } 177 178 n_updates_local += 2; 179 synchronize_rcu(); 180 } 181 synchronize_rcu(); 182 qemu_mutex_lock(&counts_mutex); 183 n_nodes += n_nodes_local; 184 n_updates += n_updates_local; 185 n_nodes_removed += n_removed_local; 186 qemu_mutex_unlock(&counts_mutex); 187 return NULL; 188 } 189 190 static void rcu_qtest_init(void) 191 { 192 struct list_element *new_el; 193 int i; 194 nthreadsrunning = 0; 195 srand(time(0)); 196 for (i = 0; i < RCU_Q_LEN; i++) { 197 new_el = g_new(struct list_element, 1); 198 QLIST_INSERT_HEAD_RCU(&Q_list_head, new_el, entry); 199 } 200 qemu_mutex_lock(&counts_mutex); 201 n_nodes += RCU_Q_LEN; 202 qemu_mutex_unlock(&counts_mutex); 203 } 204 205 static void rcu_qtest_run(int duration, int nreaders) 206 { 207 int nthreads = nreaders + 1; 208 while (atomic_read(&nthreadsrunning) < nthreads) { 209 g_usleep(1000); 210 } 211 212 goflag = GOFLAG_RUN; 213 sleep(duration); 214 goflag = GOFLAG_STOP; 215 wait_all_threads(); 216 } 217 218 219 static void rcu_qtest(const char *test, int duration, int nreaders) 220 { 221 int i; 222 long long n_removed_local = 0; 223 224 struct list_element *el, *prev_el; 225 226 rcu_qtest_init(); 227 for (i = 0; i < nreaders; i++) { 228 create_thread(rcu_q_reader); 229 } 230 create_thread(rcu_q_updater); 231 rcu_qtest_run(duration, nreaders); 232 233 QLIST_FOREACH_SAFE_RCU(prev_el, &Q_list_head, entry, el) { 234 QLIST_REMOVE_RCU(prev_el, entry); 235 call_rcu1(&prev_el->rcu, reclaim_list_el); 236 n_removed_local++; 237 } 238 qemu_mutex_lock(&counts_mutex); 239 n_nodes_removed += n_removed_local; 240 qemu_mutex_unlock(&counts_mutex); 241 synchronize_rcu(); 242 while (n_nodes_removed > n_reclaims) { 243 g_usleep(100); 244 synchronize_rcu(); 245 } 246 if (g_test_in_charge) { 247 g_assert_cmpint(n_nodes_removed, ==, n_reclaims); 248 } else { 249 printf("%s: %d readers; 1 updater; nodes read: " \ 250 "%lld, nodes removed: %lld; nodes reclaimed: %lld\n", 251 test, nthreadsrunning - 1, n_reads, n_nodes_removed, n_reclaims); 252 exit(0); 253 } 254 } 255 256 static void usage(int argc, char *argv[]) 257 { 258 fprintf(stderr, "Usage: %s duration nreaders\n", argv[0]); 259 exit(-1); 260 } 261 262 static int gtest_seconds; 263 264 static void gtest_rcuq_one(void) 265 { 266 rcu_qtest("rcuqtest", gtest_seconds / 4, 1); 267 } 268 269 static void gtest_rcuq_few(void) 270 { 271 rcu_qtest("rcuqtest", gtest_seconds / 4, 5); 272 } 273 274 static void gtest_rcuq_many(void) 275 { 276 rcu_qtest("rcuqtest", gtest_seconds / 2, 20); 277 } 278 279 280 int main(int argc, char *argv[]) 281 { 282 int duration = 0, readers = 0; 283 284 qemu_mutex_init(&counts_mutex); 285 if (argc >= 2) { 286 if (argv[1][0] == '-') { 287 g_test_init(&argc, &argv, NULL); 288 if (g_test_quick()) { 289 gtest_seconds = 4; 290 } else { 291 gtest_seconds = 20; 292 } 293 g_test_add_func("/rcu/qlist/single-threaded", gtest_rcuq_one); 294 g_test_add_func("/rcu/qlist/short-few", gtest_rcuq_few); 295 g_test_add_func("/rcu/qlist/long-many", gtest_rcuq_many); 296 g_test_in_charge = 1; 297 return g_test_run(); 298 } 299 duration = strtoul(argv[1], NULL, 0); 300 } 301 if (argc >= 3) { 302 readers = strtoul(argv[2], NULL, 0); 303 } 304 if (duration && readers) { 305 rcu_qtest(argv[0], duration, readers); 306 return 0; 307 } 308 309 usage(argc, argv); 310 return -1; 311 } 312