1*2025cf9eSThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only
2eec48525SRoss Zwisler /*
347e0fab2SMatthew Wilcox * iteration_check.c: test races having to do with xarray iteration
4eec48525SRoss Zwisler * Copyright (c) 2016 Intel Corporation
5eec48525SRoss Zwisler * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
6eec48525SRoss Zwisler */
7eec48525SRoss Zwisler #include <pthread.h>
8eec48525SRoss Zwisler #include "test.h"
9eec48525SRoss Zwisler
103e3cdc68SMatthew Wilcox #define NUM_THREADS 5
113e3cdc68SMatthew Wilcox #define MAX_IDX 100
12372266baSMatthew Wilcox #define TAG XA_MARK_0
13372266baSMatthew Wilcox #define NEW_TAG XA_MARK_1
143e3cdc68SMatthew Wilcox
15eec48525SRoss Zwisler static pthread_t threads[NUM_THREADS];
16061ef393SMatthew Wilcox static unsigned int seeds[3];
1747e0fab2SMatthew Wilcox static DEFINE_XARRAY(array);
183e3cdc68SMatthew Wilcox static bool test_complete;
193e3cdc68SMatthew Wilcox static int max_order;
20eec48525SRoss Zwisler
my_item_insert(struct xarray * xa,unsigned long index)2147e0fab2SMatthew Wilcox void my_item_insert(struct xarray *xa, unsigned long index)
2247e0fab2SMatthew Wilcox {
2347e0fab2SMatthew Wilcox XA_STATE(xas, xa, index);
2447e0fab2SMatthew Wilcox struct item *item = item_create(index, 0);
2547e0fab2SMatthew Wilcox int order;
2647e0fab2SMatthew Wilcox
2747e0fab2SMatthew Wilcox retry:
2847e0fab2SMatthew Wilcox xas_lock(&xas);
2947e0fab2SMatthew Wilcox for (order = max_order; order >= 0; order--) {
3047e0fab2SMatthew Wilcox xas_set_order(&xas, index, order);
3147e0fab2SMatthew Wilcox item->order = order;
3247e0fab2SMatthew Wilcox if (xas_find_conflict(&xas))
3347e0fab2SMatthew Wilcox continue;
3447e0fab2SMatthew Wilcox xas_store(&xas, item);
3547e0fab2SMatthew Wilcox xas_set_mark(&xas, TAG);
3647e0fab2SMatthew Wilcox break;
3747e0fab2SMatthew Wilcox }
3847e0fab2SMatthew Wilcox xas_unlock(&xas);
3947e0fab2SMatthew Wilcox if (xas_nomem(&xas, GFP_KERNEL))
4047e0fab2SMatthew Wilcox goto retry;
4147e0fab2SMatthew Wilcox if (order < 0)
4247e0fab2SMatthew Wilcox free(item);
4347e0fab2SMatthew Wilcox }
4447e0fab2SMatthew Wilcox
4547e0fab2SMatthew Wilcox /* relentlessly fill the array with tagged entries */
add_entries_fn(void * arg)46eec48525SRoss Zwisler static void *add_entries_fn(void *arg)
47eec48525SRoss Zwisler {
48ba20cd60SMatthew Wilcox rcu_register_thread();
49ba20cd60SMatthew Wilcox
50eec48525SRoss Zwisler while (!test_complete) {
513e3cdc68SMatthew Wilcox unsigned long pgoff;
523e3cdc68SMatthew Wilcox
533e3cdc68SMatthew Wilcox for (pgoff = 0; pgoff < MAX_IDX; pgoff++) {
5447e0fab2SMatthew Wilcox my_item_insert(&array, pgoff);
55eec48525SRoss Zwisler }
56eec48525SRoss Zwisler }
57eec48525SRoss Zwisler
58ba20cd60SMatthew Wilcox rcu_unregister_thread();
59ba20cd60SMatthew Wilcox
60eec48525SRoss Zwisler return NULL;
61eec48525SRoss Zwisler }
62eec48525SRoss Zwisler
63eec48525SRoss Zwisler /*
6447e0fab2SMatthew Wilcox * Iterate over tagged entries, retrying when we find ourselves in a deleted
6547e0fab2SMatthew Wilcox * node and randomly pausing the iteration.
66eec48525SRoss Zwisler */
tagged_iteration_fn(void * arg)67eec48525SRoss Zwisler static void *tagged_iteration_fn(void *arg)
68eec48525SRoss Zwisler {
6947e0fab2SMatthew Wilcox XA_STATE(xas, &array, 0);
7047e0fab2SMatthew Wilcox void *entry;
71eec48525SRoss Zwisler
72ba20cd60SMatthew Wilcox rcu_register_thread();
73ba20cd60SMatthew Wilcox
74eec48525SRoss Zwisler while (!test_complete) {
7547e0fab2SMatthew Wilcox xas_set(&xas, 0);
76eec48525SRoss Zwisler rcu_read_lock();
7747e0fab2SMatthew Wilcox xas_for_each_marked(&xas, entry, ULONG_MAX, TAG) {
7847e0fab2SMatthew Wilcox if (xas_retry(&xas, entry))
79eec48525SRoss Zwisler continue;
80eec48525SRoss Zwisler
81ba20cd60SMatthew Wilcox if (rand_r(&seeds[0]) % 50 == 0) {
8247e0fab2SMatthew Wilcox xas_pause(&xas);
83ba20cd60SMatthew Wilcox rcu_read_unlock();
84ba20cd60SMatthew Wilcox rcu_barrier();
85ba20cd60SMatthew Wilcox rcu_read_lock();
86ba20cd60SMatthew Wilcox }
87eec48525SRoss Zwisler }
88eec48525SRoss Zwisler rcu_read_unlock();
89eec48525SRoss Zwisler }
90eec48525SRoss Zwisler
91ba20cd60SMatthew Wilcox rcu_unregister_thread();
92ba20cd60SMatthew Wilcox
93eec48525SRoss Zwisler return NULL;
94eec48525SRoss Zwisler }
95eec48525SRoss Zwisler
96eec48525SRoss Zwisler /*
9747e0fab2SMatthew Wilcox * Iterate over the entries, retrying when we find ourselves in a deleted
9847e0fab2SMatthew Wilcox * node and randomly pausing the iteration.
99eec48525SRoss Zwisler */
untagged_iteration_fn(void * arg)100eec48525SRoss Zwisler static void *untagged_iteration_fn(void *arg)
101eec48525SRoss Zwisler {
10247e0fab2SMatthew Wilcox XA_STATE(xas, &array, 0);
10347e0fab2SMatthew Wilcox void *entry;
104eec48525SRoss Zwisler
105ba20cd60SMatthew Wilcox rcu_register_thread();
106ba20cd60SMatthew Wilcox
107eec48525SRoss Zwisler while (!test_complete) {
10847e0fab2SMatthew Wilcox xas_set(&xas, 0);
109eec48525SRoss Zwisler rcu_read_lock();
11047e0fab2SMatthew Wilcox xas_for_each(&xas, entry, ULONG_MAX) {
11147e0fab2SMatthew Wilcox if (xas_retry(&xas, entry))
112eec48525SRoss Zwisler continue;
113eec48525SRoss Zwisler
114ba20cd60SMatthew Wilcox if (rand_r(&seeds[1]) % 50 == 0) {
11547e0fab2SMatthew Wilcox xas_pause(&xas);
116ba20cd60SMatthew Wilcox rcu_read_unlock();
117ba20cd60SMatthew Wilcox rcu_barrier();
118ba20cd60SMatthew Wilcox rcu_read_lock();
119ba20cd60SMatthew Wilcox }
120eec48525SRoss Zwisler }
121eec48525SRoss Zwisler rcu_read_unlock();
122eec48525SRoss Zwisler }
123eec48525SRoss Zwisler
124ba20cd60SMatthew Wilcox rcu_unregister_thread();
125ba20cd60SMatthew Wilcox
126eec48525SRoss Zwisler return NULL;
127eec48525SRoss Zwisler }
128eec48525SRoss Zwisler
129eec48525SRoss Zwisler /*
13047e0fab2SMatthew Wilcox * Randomly remove entries to help induce retries in the
131eec48525SRoss Zwisler * two iteration functions.
132eec48525SRoss Zwisler */
remove_entries_fn(void * arg)133eec48525SRoss Zwisler static void *remove_entries_fn(void *arg)
134eec48525SRoss Zwisler {
135ba20cd60SMatthew Wilcox rcu_register_thread();
136ba20cd60SMatthew Wilcox
137eec48525SRoss Zwisler while (!test_complete) {
138eec48525SRoss Zwisler int pgoff;
13947e0fab2SMatthew Wilcox struct item *item;
140eec48525SRoss Zwisler
1413e3cdc68SMatthew Wilcox pgoff = rand_r(&seeds[2]) % MAX_IDX;
142eec48525SRoss Zwisler
14347e0fab2SMatthew Wilcox item = xa_erase(&array, pgoff);
14447e0fab2SMatthew Wilcox if (item)
14547e0fab2SMatthew Wilcox item_free(item, pgoff);
146eec48525SRoss Zwisler }
147eec48525SRoss Zwisler
148ba20cd60SMatthew Wilcox rcu_unregister_thread();
149ba20cd60SMatthew Wilcox
150eec48525SRoss Zwisler return NULL;
151eec48525SRoss Zwisler }
152eec48525SRoss Zwisler
tag_entries_fn(void * arg)1533e3cdc68SMatthew Wilcox static void *tag_entries_fn(void *arg)
1543e3cdc68SMatthew Wilcox {
1553e3cdc68SMatthew Wilcox rcu_register_thread();
1563e3cdc68SMatthew Wilcox
1573e3cdc68SMatthew Wilcox while (!test_complete) {
15847e0fab2SMatthew Wilcox tag_tagged_items(&array, 0, MAX_IDX, 10, TAG, NEW_TAG);
1593e3cdc68SMatthew Wilcox }
1603e3cdc68SMatthew Wilcox rcu_unregister_thread();
1613e3cdc68SMatthew Wilcox return NULL;
1623e3cdc68SMatthew Wilcox }
1633e3cdc68SMatthew Wilcox
164eec48525SRoss Zwisler /* This is a unit test for a bug found by the syzkaller tester */
iteration_test(unsigned order,unsigned test_duration)1653e3cdc68SMatthew Wilcox void iteration_test(unsigned order, unsigned test_duration)
166eec48525SRoss Zwisler {
167eec48525SRoss Zwisler int i;
168eec48525SRoss Zwisler
16973bc029bSRehas Sachdeva printv(1, "Running %siteration tests for %d seconds\n",
1703e3cdc68SMatthew Wilcox order > 0 ? "multiorder " : "", test_duration);
171eec48525SRoss Zwisler
1723e3cdc68SMatthew Wilcox max_order = order;
173eec48525SRoss Zwisler test_complete = false;
174eec48525SRoss Zwisler
175061ef393SMatthew Wilcox for (i = 0; i < 3; i++)
176061ef393SMatthew Wilcox seeds[i] = rand();
177061ef393SMatthew Wilcox
178eec48525SRoss Zwisler if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
1793e3cdc68SMatthew Wilcox perror("create tagged iteration thread");
180eec48525SRoss Zwisler exit(1);
181eec48525SRoss Zwisler }
182eec48525SRoss Zwisler if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
1833e3cdc68SMatthew Wilcox perror("create untagged iteration thread");
184eec48525SRoss Zwisler exit(1);
185eec48525SRoss Zwisler }
186eec48525SRoss Zwisler if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
1873e3cdc68SMatthew Wilcox perror("create add entry thread");
188eec48525SRoss Zwisler exit(1);
189eec48525SRoss Zwisler }
190eec48525SRoss Zwisler if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
1913e3cdc68SMatthew Wilcox perror("create remove entry thread");
1923e3cdc68SMatthew Wilcox exit(1);
1933e3cdc68SMatthew Wilcox }
1943e3cdc68SMatthew Wilcox if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) {
1953e3cdc68SMatthew Wilcox perror("create tag entry thread");
196eec48525SRoss Zwisler exit(1);
197eec48525SRoss Zwisler }
198eec48525SRoss Zwisler
1993e3cdc68SMatthew Wilcox sleep(test_duration);
200eec48525SRoss Zwisler test_complete = true;
201eec48525SRoss Zwisler
202eec48525SRoss Zwisler for (i = 0; i < NUM_THREADS; i++) {
203eec48525SRoss Zwisler if (pthread_join(threads[i], NULL)) {
204eec48525SRoss Zwisler perror("pthread_join");
205eec48525SRoss Zwisler exit(1);
206eec48525SRoss Zwisler }
207eec48525SRoss Zwisler }
208eec48525SRoss Zwisler
20947e0fab2SMatthew Wilcox item_kill_tree(&array);
210eec48525SRoss Zwisler }
211