4 * usage: rcuq_test <readers> <duration>
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.
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.
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.
20 * Copyright (c) 2013 Mike D. Day, IBM Corporation.
23 #include "qemu/osdep.h"
24 #include "qemu/atomic.h"
26 #include "qemu/thread.h"
27 #include "qemu/rcu_queue.h"
33 static QemuMutex counts_mutex
;
34 static long long n_reads
= 0LL;
35 static long long n_updates
= 0LL;
36 static int64_t n_reclaims
;
37 static int64_t n_nodes_removed
;
38 static long long n_nodes
= 0LL;
39 static int g_test_in_charge
= 0;
41 static int nthreadsrunning
;
47 static int goflag
= GOFLAG_INIT
;
49 #define RCU_READ_RUN 1000
50 #define RCU_UPDATE_RUN 10
51 #define NR_THREADS 100
54 static QemuThread threads
[NR_THREADS
];
55 static struct rcu_reader_data
*data
[NR_THREADS
];
58 static int select_random_el(int max
)
60 return (rand() % max
);
64 static void create_thread(void *(*func
)(void *))
66 if (n_threads
>= NR_THREADS
) {
67 fprintf(stderr
, "Thread limit of %d exceeded!\n", NR_THREADS
);
70 qemu_thread_create(&threads
[n_threads
], "test", func
, &data
[n_threads
],
71 QEMU_THREAD_JOINABLE
);
75 static void wait_all_threads(void)
79 for (i
= 0; i
< n_threads
; i
++) {
80 qemu_thread_join(&threads
[i
]);
85 #ifndef TEST_LIST_TYPE
86 #define TEST_LIST_TYPE 1
90 #if TEST_LIST_TYPE == 1
91 QLIST_ENTRY(list_element
) entry
;
92 #elif TEST_LIST_TYPE == 2
93 QSIMPLEQ_ENTRY(list_element
) entry
;
94 #elif TEST_LIST_TYPE == 3
95 QTAILQ_ENTRY(list_element
) entry
;
97 #error Invalid TEST_LIST_TYPE
102 static void reclaim_list_el(struct rcu_head
*prcu
)
104 struct list_element
*el
= container_of(prcu
, struct list_element
, rcu
);
106 /* Accessed only from call_rcu thread. */
107 atomic_set_i64(&n_reclaims
, n_reclaims
+ 1);
110 #if TEST_LIST_TYPE == 1
111 static QLIST_HEAD(, list_element
) Q_list_head
;
113 #define TEST_NAME "qlist"
114 #define TEST_LIST_REMOVE_RCU QLIST_REMOVE_RCU
115 #define TEST_LIST_INSERT_AFTER_RCU QLIST_INSERT_AFTER_RCU
116 #define TEST_LIST_INSERT_HEAD_RCU QLIST_INSERT_HEAD_RCU
117 #define TEST_LIST_FOREACH_RCU QLIST_FOREACH_RCU
118 #define TEST_LIST_FOREACH_SAFE_RCU QLIST_FOREACH_SAFE_RCU
120 #elif TEST_LIST_TYPE == 2
121 static QSIMPLEQ_HEAD(, list_element
) Q_list_head
=
122 QSIMPLEQ_HEAD_INITIALIZER(Q_list_head
);
124 #define TEST_NAME "qsimpleq"
125 #define TEST_LIST_REMOVE_RCU(el, f) \
126 QSIMPLEQ_REMOVE_RCU(&Q_list_head, el, list_element, f)
128 #define TEST_LIST_INSERT_AFTER_RCU(list_el, el, f) \
129 QSIMPLEQ_INSERT_AFTER_RCU(&Q_list_head, list_el, el, f)
131 #define TEST_LIST_INSERT_HEAD_RCU QSIMPLEQ_INSERT_HEAD_RCU
132 #define TEST_LIST_FOREACH_RCU QSIMPLEQ_FOREACH_RCU
133 #define TEST_LIST_FOREACH_SAFE_RCU QSIMPLEQ_FOREACH_SAFE_RCU
135 #elif TEST_LIST_TYPE == 3
136 static QTAILQ_HEAD(, list_element
) Q_list_head
;
138 #define TEST_NAME "qtailq"
139 #define TEST_LIST_REMOVE_RCU(el, f) QTAILQ_REMOVE_RCU(&Q_list_head, el, f)
141 #define TEST_LIST_INSERT_AFTER_RCU(list_el, el, f) \
142 QTAILQ_INSERT_AFTER_RCU(&Q_list_head, list_el, el, f)
144 #define TEST_LIST_INSERT_HEAD_RCU QTAILQ_INSERT_HEAD_RCU
145 #define TEST_LIST_FOREACH_RCU QTAILQ_FOREACH_RCU
146 #define TEST_LIST_FOREACH_SAFE_RCU QTAILQ_FOREACH_SAFE_RCU
148 #error Invalid TEST_LIST_TYPE
151 static void *rcu_q_reader(void *arg
)
153 long long n_reads_local
= 0;
154 struct list_element
*el
;
156 rcu_register_thread();
158 *(struct rcu_reader_data
**)arg
= &rcu_reader
;
159 atomic_inc(&nthreadsrunning
);
160 while (atomic_read(&goflag
) == GOFLAG_INIT
) {
164 while (atomic_read(&goflag
) == GOFLAG_RUN
) {
166 TEST_LIST_FOREACH_RCU(el
, &Q_list_head
, entry
) {
168 if (atomic_read(&goflag
) == GOFLAG_STOP
) {
176 qemu_mutex_lock(&counts_mutex
);
177 n_reads
+= n_reads_local
;
178 qemu_mutex_unlock(&counts_mutex
);
180 rcu_unregister_thread();
185 static void *rcu_q_updater(void *arg
)
188 long long n_nodes_local
= 0;
189 long long n_updates_local
= 0;
190 long long n_removed_local
= 0;
191 struct list_element
*el
, *prev_el
;
193 *(struct rcu_reader_data
**)arg
= &rcu_reader
;
194 atomic_inc(&nthreadsrunning
);
195 while (atomic_read(&goflag
) == GOFLAG_INIT
) {
199 while (atomic_read(&goflag
) == GOFLAG_RUN
) {
200 target_el
= select_random_el(RCU_Q_LEN
);
202 /* FOREACH_RCU could work here but let's use both macros */
203 TEST_LIST_FOREACH_SAFE_RCU(prev_el
, &Q_list_head
, entry
, el
) {
205 if (target_el
== j
) {
206 TEST_LIST_REMOVE_RCU(prev_el
, entry
);
207 /* may be more than one updater in the future */
208 call_rcu1(&prev_el
->rcu
, reclaim_list_el
);
213 if (atomic_read(&goflag
) == GOFLAG_STOP
) {
216 target_el
= select_random_el(RCU_Q_LEN
);
218 TEST_LIST_FOREACH_RCU(el
, &Q_list_head
, entry
) {
220 if (target_el
== j
) {
221 struct list_element
*new_el
= g_new(struct list_element
, 1);
222 n_nodes
+= n_nodes_local
;
223 TEST_LIST_INSERT_AFTER_RCU(el
, new_el
, entry
);
228 n_updates_local
+= 2;
232 qemu_mutex_lock(&counts_mutex
);
233 n_nodes
+= n_nodes_local
;
234 n_updates
+= n_updates_local
;
235 atomic_set_i64(&n_nodes_removed
, n_nodes_removed
+ n_removed_local
);
236 qemu_mutex_unlock(&counts_mutex
);
240 static void rcu_qtest_init(void)
242 struct list_element
*new_el
;
246 for (i
= 0; i
< RCU_Q_LEN
; i
++) {
247 new_el
= g_new(struct list_element
, 1);
248 TEST_LIST_INSERT_HEAD_RCU(&Q_list_head
, new_el
, entry
);
250 qemu_mutex_lock(&counts_mutex
);
251 n_nodes
+= RCU_Q_LEN
;
252 qemu_mutex_unlock(&counts_mutex
);
255 static void rcu_qtest_run(int duration
, int nreaders
)
257 int nthreads
= nreaders
+ 1;
258 while (atomic_read(&nthreadsrunning
) < nthreads
) {
262 atomic_set(&goflag
, GOFLAG_RUN
);
264 atomic_set(&goflag
, GOFLAG_STOP
);
269 static void rcu_qtest(const char *test
, int duration
, int nreaders
)
272 long long n_removed_local
= 0;
274 struct list_element
*el
, *prev_el
;
277 for (i
= 0; i
< nreaders
; i
++) {
278 create_thread(rcu_q_reader
);
280 create_thread(rcu_q_updater
);
281 rcu_qtest_run(duration
, nreaders
);
283 TEST_LIST_FOREACH_SAFE_RCU(prev_el
, &Q_list_head
, entry
, el
) {
284 TEST_LIST_REMOVE_RCU(prev_el
, entry
);
285 call_rcu1(&prev_el
->rcu
, reclaim_list_el
);
288 qemu_mutex_lock(&counts_mutex
);
289 atomic_set_i64(&n_nodes_removed
, n_nodes_removed
+ n_removed_local
);
290 qemu_mutex_unlock(&counts_mutex
);
292 while (atomic_read_i64(&n_nodes_removed
) > atomic_read_i64(&n_reclaims
)) {
296 if (g_test_in_charge
) {
297 g_assert_cmpint(atomic_read_i64(&n_nodes_removed
), ==,
298 atomic_read_i64(&n_reclaims
));
300 printf("%s: %d readers; 1 updater; nodes read: " \
301 "%lld, nodes removed: %"PRIi64
"; nodes reclaimed: %"PRIi64
"\n",
302 test
, nthreadsrunning
- 1, n_reads
,
303 atomic_read_i64(&n_nodes_removed
), atomic_read_i64(&n_reclaims
));
308 static void usage(int argc
, char *argv
[])
310 fprintf(stderr
, "Usage: %s duration nreaders\n", argv
[0]);
314 static int gtest_seconds
;
316 static void gtest_rcuq_one(void)
318 rcu_qtest("rcuqtest", gtest_seconds
/ 4, 1);
321 static void gtest_rcuq_few(void)
323 rcu_qtest("rcuqtest", gtest_seconds
/ 4, 5);
326 static void gtest_rcuq_many(void)
328 rcu_qtest("rcuqtest", gtest_seconds
/ 2, 20);
332 int main(int argc
, char *argv
[])
334 int duration
= 0, readers
= 0;
336 qemu_mutex_init(&counts_mutex
);
338 if (argv
[1][0] == '-') {
339 g_test_init(&argc
, &argv
, NULL
);
340 if (g_test_quick()) {
345 g_test_add_func("/rcu/"TEST_NAME
"/single-threaded", gtest_rcuq_one
);
346 g_test_add_func("/rcu/"TEST_NAME
"/short-few", gtest_rcuq_few
);
347 g_test_add_func("/rcu/"TEST_NAME
"/long-many", gtest_rcuq_many
);
348 g_test_in_charge
= 1;
351 duration
= strtoul(argv
[1], NULL
, 0);
354 readers
= strtoul(argv
[2], NULL
, 0);
356 if (duration
&& readers
) {
357 rcu_qtest(argv
[0], duration
, readers
);