Commit | Line | Data |
---|---|---|
5ac62190 RZ |
1 | /* |
2 | * iteration_check.c: test races having to do with radix tree 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 <linux/radix-tree.h> | |
16 | #include <pthread.h> | |
17 | #include "test.h" | |
18 | ||
19 | #define NUM_THREADS 4 | |
20 | #define TAG 0 | |
21 | static pthread_mutex_t tree_lock = PTHREAD_MUTEX_INITIALIZER; | |
22 | static pthread_t threads[NUM_THREADS]; | |
23 | RADIX_TREE(tree, GFP_KERNEL); | |
24 | bool test_complete; | |
25 | ||
26 | /* relentlessly fill the tree with tagged entries */ | |
27 | static void *add_entries_fn(void *arg) | |
28 | { | |
29 | int pgoff; | |
30 | ||
31 | while (!test_complete) { | |
32 | for (pgoff = 0; pgoff < 100; pgoff++) { | |
33 | pthread_mutex_lock(&tree_lock); | |
34 | if (item_insert(&tree, pgoff) == 0) | |
35 | item_tag_set(&tree, pgoff, TAG); | |
36 | pthread_mutex_unlock(&tree_lock); | |
37 | } | |
38 | } | |
39 | ||
40 | return NULL; | |
41 | } | |
42 | ||
43 | /* | |
44 | * Iterate over the tagged entries, doing a radix_tree_iter_retry() as we find | |
45 | * things that have been removed and randomly resetting our iteration to the | |
46 | * next chunk with radix_tree_iter_next(). Both radix_tree_iter_retry() and | |
47 | * radix_tree_iter_next() cause radix_tree_next_slot() to be called with a | |
48 | * NULL 'slot' variable. | |
49 | */ | |
50 | static void *tagged_iteration_fn(void *arg) | |
51 | { | |
52 | struct radix_tree_iter iter; | |
53 | void **slot; | |
54 | ||
55 | while (!test_complete) { | |
56 | rcu_read_lock(); | |
57 | radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) { | |
58 | void *entry; | |
59 | int i; | |
60 | ||
61 | /* busy wait to let removals happen */ | |
62 | for (i = 0; i < 1000000; i++) | |
63 | ; | |
64 | ||
65 | entry = radix_tree_deref_slot(slot); | |
66 | if (unlikely(!entry)) | |
67 | continue; | |
68 | ||
69 | if (radix_tree_deref_retry(entry)) { | |
70 | slot = radix_tree_iter_retry(&iter); | |
71 | continue; | |
72 | } | |
73 | ||
74 | if (rand() % 50 == 0) | |
75 | slot = radix_tree_iter_next(&iter); | |
76 | } | |
77 | rcu_read_unlock(); | |
78 | } | |
79 | ||
80 | return NULL; | |
81 | } | |
82 | ||
83 | /* | |
84 | * Iterate over the entries, doing a radix_tree_iter_retry() as we find things | |
85 | * that have been removed and randomly resetting our iteration to the next | |
86 | * chunk with radix_tree_iter_next(). Both radix_tree_iter_retry() and | |
87 | * radix_tree_iter_next() cause radix_tree_next_slot() to be called with a | |
88 | * NULL 'slot' variable. | |
89 | */ | |
90 | static void *untagged_iteration_fn(void *arg) | |
91 | { | |
92 | struct radix_tree_iter iter; | |
93 | void **slot; | |
94 | ||
95 | while (!test_complete) { | |
96 | rcu_read_lock(); | |
97 | radix_tree_for_each_slot(slot, &tree, &iter, 0) { | |
98 | void *entry; | |
99 | int i; | |
100 | ||
101 | /* busy wait to let removals happen */ | |
102 | for (i = 0; i < 1000000; i++) | |
103 | ; | |
104 | ||
105 | entry = radix_tree_deref_slot(slot); | |
106 | if (unlikely(!entry)) | |
107 | continue; | |
108 | ||
109 | if (radix_tree_deref_retry(entry)) { | |
110 | slot = radix_tree_iter_retry(&iter); | |
111 | continue; | |
112 | } | |
113 | ||
114 | if (rand() % 50 == 0) | |
115 | slot = radix_tree_iter_next(&iter); | |
116 | } | |
117 | rcu_read_unlock(); | |
118 | } | |
119 | ||
120 | return NULL; | |
121 | } | |
122 | ||
123 | /* | |
124 | * Randomly remove entries to help induce radix_tree_iter_retry() calls in the | |
125 | * two iteration functions. | |
126 | */ | |
127 | static void *remove_entries_fn(void *arg) | |
128 | { | |
129 | while (!test_complete) { | |
130 | int pgoff; | |
131 | ||
132 | pgoff = rand() % 100; | |
133 | ||
134 | pthread_mutex_lock(&tree_lock); | |
135 | item_delete(&tree, pgoff); | |
136 | pthread_mutex_unlock(&tree_lock); | |
137 | } | |
138 | ||
139 | return NULL; | |
140 | } | |
141 | ||
142 | /* This is a unit test for a bug found by the syzkaller tester */ | |
143 | void iteration_test(void) | |
144 | { | |
145 | int i; | |
146 | ||
147 | printf("Running iteration tests for 10 seconds\n"); | |
148 | ||
149 | srand(time(0)); | |
150 | test_complete = false; | |
151 | ||
152 | if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) { | |
153 | perror("pthread_create"); | |
154 | exit(1); | |
155 | } | |
156 | if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) { | |
157 | perror("pthread_create"); | |
158 | exit(1); | |
159 | } | |
160 | if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) { | |
161 | perror("pthread_create"); | |
162 | exit(1); | |
163 | } | |
164 | if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) { | |
165 | perror("pthread_create"); | |
166 | exit(1); | |
167 | } | |
168 | ||
169 | sleep(10); | |
170 | test_complete = true; | |
171 | ||
172 | for (i = 0; i < NUM_THREADS; i++) { | |
173 | if (pthread_join(threads[i], NULL)) { | |
174 | perror("pthread_join"); | |
175 | exit(1); | |
176 | } | |
177 | } | |
178 | ||
179 | item_kill_tree(&tree); | |
180 | } |