tests/unit/test-rcu-list.c

   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, see <https://www.gnu.org/licenses/>.
  18  *
  19  * Copyright (c) 2013 Mike D. Day, IBM Corporation.
  20  */
  21
  22 #include "qemu/osdep.h"
  23 #include "qemu/atomic.h"
  24 #include "qemu/rcu.h"
  25 #include "qemu/thread.h"
  26 #include "qemu/rcu_queue.h"
  27
  28 /*
  29  * Test variables.
  30  */
  31
  32 static QemuMutex counts_mutex;
  33 static long long n_reads = 0LL;
  34 static long long n_updates = 0LL;
  35 static int64_t n_reclaims;
  36 static int64_t n_nodes_removed;
  37 static long long n_nodes = 0LL;
  38 static int g_test_in_charge = 0;
  39
  40 static int nthreadsrunning;
  41
  42 #define GOFLAG_INIT 0
  43 #define GOFLAG_RUN  1
  44 #define GOFLAG_STOP 2
  45
  46 static int goflag = GOFLAG_INIT;
  47
  48 #define RCU_READ_RUN 1000
  49 #define RCU_UPDATE_RUN 10
  50 #define NR_THREADS 100
  51 #define RCU_Q_LEN 100
  52
  53 static QemuThread threads[NR_THREADS];
  54 static struct rcu_reader_data *data[NR_THREADS];
  55 static int n_threads;
  56
  57 static int select_random_el(int max)
  58 {
  59     return (rand() % max);
  60 }
  61
  62
  63 static void create_thread(void *(*func)(void *))
  64 {
  65     if (n_threads >= NR_THREADS) {
  66         fprintf(stderr, "Thread limit of %d exceeded!\n", NR_THREADS);
  67         exit(-1);
  68     }
  69     qemu_thread_create(&threads[n_threads], "test", func, &data[n_threads],
  70                        QEMU_THREAD_JOINABLE);
  71     n_threads++;
  72 }
  73
  74 static void wait_all_threads(void)
  75 {
  76     int i;
  77
  78     for (i = 0; i < n_threads; i++) {
  79         qemu_thread_join(&threads[i]);
  80     }
  81     n_threads = 0;
  82 }
  83
  84 #ifndef TEST_LIST_TYPE
  85 #define TEST_LIST_TYPE 1
  86 #endif
  87
  88 struct list_element {
  89 #if TEST_LIST_TYPE == 1
  90     QLIST_ENTRY(list_element) entry;
  91 #elif TEST_LIST_TYPE == 2
  92     QSIMPLEQ_ENTRY(list_element) entry;
  93 #elif TEST_LIST_TYPE == 3
  94     QTAILQ_ENTRY(list_element) entry;
  95 #elif TEST_LIST_TYPE == 4
  96     QSLIST_ENTRY(list_element) entry;
  97 #else
  98 #error Invalid TEST_LIST_TYPE
  99 #endif
 100     struct rcu_head rcu;
 101 };
 102
 103 static void reclaim_list_el(struct rcu_head *prcu)
 104 {
 105     struct list_element *el = container_of(prcu, struct list_element, rcu);
 106     g_free(el);
 107     /* Accessed only from call_rcu thread.  */
 108     qatomic_set_i64(&n_reclaims, n_reclaims + 1);
 109 }
 110
 111 #if TEST_LIST_TYPE == 1
 112 static QLIST_HEAD(, list_element) Q_list_head;
 113
 114 #define TEST_NAME "qlist"
 115 #define TEST_LIST_REMOVE_RCU        QLIST_REMOVE_RCU
 116 #define TEST_LIST_INSERT_AFTER_RCU  QLIST_INSERT_AFTER_RCU
 117 #define TEST_LIST_INSERT_HEAD_RCU   QLIST_INSERT_HEAD_RCU
 118 #define TEST_LIST_FOREACH_RCU       QLIST_FOREACH_RCU
 119 #define TEST_LIST_FOREACH_SAFE_RCU  QLIST_FOREACH_SAFE_RCU
 120
 121 #elif TEST_LIST_TYPE == 2
 122 static QSIMPLEQ_HEAD(, list_element) Q_list_head =
 123     QSIMPLEQ_HEAD_INITIALIZER(Q_list_head);
 124
 125 #define TEST_NAME "qsimpleq"
 126 #define TEST_LIST_REMOVE_RCU(el, f)                             \
 127          QSIMPLEQ_REMOVE_RCU(&Q_list_head, el, list_element, f)
 128
 129 #define TEST_LIST_INSERT_AFTER_RCU(list_el, el, f)               \
 130          QSIMPLEQ_INSERT_AFTER_RCU(&Q_list_head, list_el, el, f)
 131
 132 #define TEST_LIST_INSERT_HEAD_RCU   QSIMPLEQ_INSERT_HEAD_RCU
 133 #define TEST_LIST_FOREACH_RCU       QSIMPLEQ_FOREACH_RCU
 134 #define TEST_LIST_FOREACH_SAFE_RCU  QSIMPLEQ_FOREACH_SAFE_RCU
 135
 136 #elif TEST_LIST_TYPE == 3
 137 static QTAILQ_HEAD(, list_element) Q_list_head;
 138
 139 #define TEST_NAME "qtailq"
 140 #define TEST_LIST_REMOVE_RCU(el, f) QTAILQ_REMOVE_RCU(&Q_list_head, el, f)
 141
 142 #define TEST_LIST_INSERT_AFTER_RCU(list_el, el, f)               \
 143            QTAILQ_INSERT_AFTER_RCU(&Q_list_head, list_el, el, f)
 144
 145 #define TEST_LIST_INSERT_HEAD_RCU   QTAILQ_INSERT_HEAD_RCU
 146 #define TEST_LIST_FOREACH_RCU       QTAILQ_FOREACH_RCU
 147 #define TEST_LIST_FOREACH_SAFE_RCU  QTAILQ_FOREACH_SAFE_RCU
 148
 149 #elif TEST_LIST_TYPE == 4
 150 static QSLIST_HEAD(, list_element) Q_list_head;
 151
 152 #define TEST_NAME "qslist"
 153 #define TEST_LIST_REMOVE_RCU(el, f)                              \
 154          QSLIST_REMOVE_RCU(&Q_list_head, el, list_element, f)
 155
 156 #define TEST_LIST_INSERT_AFTER_RCU(list_el, el, f)               \
 157          QSLIST_INSERT_AFTER_RCU(&Q_list_head, list_el, el, f)
 158
 159 #define TEST_LIST_INSERT_HEAD_RCU   QSLIST_INSERT_HEAD_RCU
 160 #define TEST_LIST_FOREACH_RCU       QSLIST_FOREACH_RCU
 161 #define TEST_LIST_FOREACH_SAFE_RCU  QSLIST_FOREACH_SAFE_RCU
 162 #else
 163 #error Invalid TEST_LIST_TYPE
 164 #endif
 165
 166 static void *rcu_q_reader(void *arg)
 167 {
 168     long long n_reads_local = 0;
 169     struct list_element *el;
 170
 171     rcu_register_thread();
 172
 173     *(struct rcu_reader_data **)arg = get_ptr_rcu_reader();
 174     qatomic_inc(&nthreadsrunning);
 175     while (qatomic_read(&goflag) == GOFLAG_INIT) {
 176         g_usleep(1000);
 177     }
 178
 179     while (qatomic_read(&goflag) == GOFLAG_RUN) {
 180         rcu_read_lock();
 181         TEST_LIST_FOREACH_RCU(el, &Q_list_head, entry) {
 182             n_reads_local++;
 183             if (qatomic_read(&goflag) == GOFLAG_STOP) {
 184                 break;
 185             }
 186         }
 187         rcu_read_unlock();
 188
 189         g_usleep(100);
 190     }
 191     qemu_mutex_lock(&counts_mutex);
 192     n_reads += n_reads_local;
 193     qemu_mutex_unlock(&counts_mutex);
 194
 195     rcu_unregister_thread();
 196     return NULL;
 197 }
 198
 199
 200 static void *rcu_q_updater(void *arg)
 201 {
 202     int j, target_el;
 203     long long n_nodes_local = 0;
 204     long long n_updates_local = 0;
 205     long long n_removed_local = 0;
 206     struct list_element *el, *prev_el;
 207
 208     *(struct rcu_reader_data **)arg = get_ptr_rcu_reader();
 209     qatomic_inc(&nthreadsrunning);
 210     while (qatomic_read(&goflag) == GOFLAG_INIT) {
 211         g_usleep(1000);
 212     }
 213
 214     while (qatomic_read(&goflag) == GOFLAG_RUN) {
 215         target_el = select_random_el(RCU_Q_LEN);
 216         j = 0;
 217         /* FOREACH_RCU could work here but let's use both macros */
 218         TEST_LIST_FOREACH_SAFE_RCU(prev_el, &Q_list_head, entry, el) {
 219             j++;
 220             if (target_el == j) {
 221                 TEST_LIST_REMOVE_RCU(prev_el, entry);
 222                 /* may be more than one updater in the future */
 223                 call_rcu1(&prev_el->rcu, reclaim_list_el);
 224                 n_removed_local++;
 225                 break;
 226             }
 227         }
 228         if (qatomic_read(&goflag) == GOFLAG_STOP) {
 229             break;
 230         }
 231         target_el = select_random_el(RCU_Q_LEN);
 232         j = 0;
 233         TEST_LIST_FOREACH_RCU(el, &Q_list_head, entry) {
 234             j++;
 235             if (target_el == j) {
 236                 struct list_element *new_el = g_new(struct list_element, 1);
 237                 n_nodes_local++;
 238                 TEST_LIST_INSERT_AFTER_RCU(el, new_el, entry);
 239                 break;
 240             }
 241         }
 242
 243         n_updates_local += 2;
 244         synchronize_rcu();
 245     }
 246     synchronize_rcu();
 247     qemu_mutex_lock(&counts_mutex);
 248     n_nodes += n_nodes_local;
 249     n_updates += n_updates_local;
 250     qatomic_set_i64(&n_nodes_removed, n_nodes_removed + n_removed_local);
 251     qemu_mutex_unlock(&counts_mutex);
 252     return NULL;
 253 }
 254
 255 static void rcu_qtest_init(void)
 256 {
 257     struct list_element *new_el;
 258     int i;
 259     nthreadsrunning = 0;
 260     srand(time(0));
 261     for (i = 0; i < RCU_Q_LEN; i++) {
 262         new_el = g_new(struct list_element, 1);
 263         TEST_LIST_INSERT_HEAD_RCU(&Q_list_head, new_el, entry);
 264     }
 265     qemu_mutex_lock(&counts_mutex);
 266     n_nodes += RCU_Q_LEN;
 267     qemu_mutex_unlock(&counts_mutex);
 268 }
 269
 270 static void rcu_qtest_run(int duration, int nreaders)
 271 {
 272     int nthreads = nreaders + 1;
 273     while (qatomic_read(&nthreadsrunning) < nthreads) {
 274         g_usleep(1000);
 275     }
 276
 277     qatomic_set(&goflag, GOFLAG_RUN);
 278     sleep(duration);
 279     qatomic_set(&goflag, GOFLAG_STOP);
 280     wait_all_threads();
 281 }
 282
 283
 284 static void rcu_qtest(const char *test, int duration, int nreaders)
 285 {
 286     int i;
 287     long long n_removed_local = 0;
 288
 289     struct list_element *el, *prev_el;
 290
 291     rcu_qtest_init();
 292     for (i = 0; i < nreaders; i++) {
 293         create_thread(rcu_q_reader);
 294     }
 295     create_thread(rcu_q_updater);
 296     rcu_qtest_run(duration, nreaders);
 297
 298     TEST_LIST_FOREACH_SAFE_RCU(prev_el, &Q_list_head, entry, el) {
 299         TEST_LIST_REMOVE_RCU(prev_el, entry);
 300         call_rcu1(&prev_el->rcu, reclaim_list_el);
 301         n_removed_local++;
 302     }
 303     qemu_mutex_lock(&counts_mutex);
 304     qatomic_set_i64(&n_nodes_removed, n_nodes_removed + n_removed_local);
 305     qemu_mutex_unlock(&counts_mutex);
 306     synchronize_rcu();
 307     while (qatomic_read_i64(&n_nodes_removed) >
 308            qatomic_read_i64(&n_reclaims)) {
 309         g_usleep(100);
 310         synchronize_rcu();
 311     }
 312     if (g_test_in_charge) {
 313         g_assert_cmpint(qatomic_read_i64(&n_nodes_removed), ==,
 314                         qatomic_read_i64(&n_reclaims));
 315     } else {
 316         printf("%s: %d readers; 1 updater; nodes read: "  \
 317                "%lld, nodes removed: %"PRIi64"; nodes reclaimed: %"PRIi64"\n",
 318                test, nthreadsrunning - 1, n_reads,
 319                qatomic_read_i64(&n_nodes_removed),
 320                qatomic_read_i64(&n_reclaims));
 321         exit(0);
 322     }
 323 }
 324
 325 static void usage(int argc, char *argv[])
 326 {
 327     fprintf(stderr, "Usage: %s duration nreaders\n", argv[0]);
 328     exit(-1);
 329 }
 330
 331 static int gtest_seconds;
 332
 333 static void gtest_rcuq_one(void)
 334 {
 335     rcu_qtest("rcuqtest", gtest_seconds / 4, 1);
 336 }
 337
 338 static void gtest_rcuq_few(void)
 339 {
 340     rcu_qtest("rcuqtest", gtest_seconds / 4, 5);
 341 }
 342
 343 static void gtest_rcuq_many(void)
 344 {
 345     rcu_qtest("rcuqtest", gtest_seconds / 2, 20);
 346 }
 347
 348
 349 int main(int argc, char *argv[])
 350 {
 351     int duration = 0, readers = 0;
 352
 353     qemu_mutex_init(&counts_mutex);
 354     if (argc >= 2) {
 355         if (argv[1][0] == '-') {
 356             g_test_init(&argc, &argv, NULL);
 357             if (g_test_quick()) {
 358                 gtest_seconds = 4;
 359             } else {
 360                 gtest_seconds = 20;
 361             }
 362             g_test_add_func("/rcu/"TEST_NAME"/single-threaded", gtest_rcuq_one);
 363             g_test_add_func("/rcu/"TEST_NAME"/short-few", gtest_rcuq_few);
 364             g_test_add_func("/rcu/"TEST_NAME"/long-many", gtest_rcuq_many);
 365             g_test_in_charge = 1;
 366             return g_test_run();
 367         }
 368         duration = strtoul(argv[1], NULL, 0);
 369     }
 370     if (argc >= 3) {
 371         readers = strtoul(argv[2], NULL, 0);
 372     }
 373     if (duration && readers) {
 374         rcu_qtest(argv[0], duration, readers);
 375         return 0;
 376     }
 377
 378     usage(argc, argv);
 379     return -1;
 380 }