Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
1366c37e MW |
2 | /* |
3 | * Regression1 | |
4 | * Description: | |
5 | * Salman Qazi describes the following radix-tree bug: | |
6 | * | |
7 | * In the following case, we get can get a deadlock: | |
8 | * | |
9 | * 0. The radix tree contains two items, one has the index 0. | |
10 | * 1. The reader (in this case find_get_pages) takes the rcu_read_lock. | |
11 | * 2. The reader acquires slot(s) for item(s) including the index 0 item. | |
12 | * 3. The non-zero index item is deleted, and as a consequence the other item | |
13 | * is moved to the root of the tree. The place where it used to be is queued | |
14 | * for deletion after the readers finish. | |
15 | * 3b. The zero item is deleted, removing it from the direct slot, it remains in | |
16 | * the rcu-delayed indirect node. | |
17 | * 4. The reader looks at the index 0 slot, and finds that the page has 0 ref | |
18 | * count | |
19 | * 5. The reader looks at it again, hoping that the item will either be freed | |
20 | * or the ref count will increase. This never happens, as the slot it is | |
21 | * looking at will never be updated. Also, this slot can never be reclaimed | |
22 | * because the reader is holding rcu_read_lock and is in an infinite loop. | |
23 | * | |
24 | * The fix is to re-use the same "indirect" pointer case that requires a slot | |
25 | * lookup retry into a general "retry the lookup" bit. | |
26 | * | |
27 | * Running: | |
28 | * This test should run to completion in a few seconds. The above bug would | |
29 | * cause it to hang indefinitely. | |
30 | * | |
31 | * Upstream commit: | |
32 | * Not yet | |
33 | */ | |
34 | #include <linux/kernel.h> | |
35 | #include <linux/gfp.h> | |
36 | #include <linux/slab.h> | |
37 | #include <linux/radix-tree.h> | |
38 | #include <linux/rcupdate.h> | |
39 | #include <stdlib.h> | |
40 | #include <pthread.h> | |
41 | #include <stdio.h> | |
42 | #include <assert.h> | |
43 | ||
44 | #include "regression.h" | |
45 | ||
46 | static RADIX_TREE(mt_tree, GFP_KERNEL); | |
e0176a2f | 47 | static pthread_mutex_t mt_lock = PTHREAD_MUTEX_INITIALIZER; |
1366c37e MW |
48 | |
49 | struct page { | |
50 | pthread_mutex_t lock; | |
51 | struct rcu_head rcu; | |
52 | int count; | |
53 | unsigned long index; | |
54 | }; | |
55 | ||
56 | static struct page *page_alloc(void) | |
57 | { | |
58 | struct page *p; | |
59 | p = malloc(sizeof(struct page)); | |
60 | p->count = 1; | |
61 | p->index = 1; | |
62 | pthread_mutex_init(&p->lock, NULL); | |
63 | ||
64 | return p; | |
65 | } | |
66 | ||
67 | static void page_rcu_free(struct rcu_head *rcu) | |
68 | { | |
69 | struct page *p = container_of(rcu, struct page, rcu); | |
70 | assert(!p->count); | |
71 | pthread_mutex_destroy(&p->lock); | |
72 | free(p); | |
73 | } | |
74 | ||
75 | static void page_free(struct page *p) | |
76 | { | |
77 | call_rcu(&p->rcu, page_rcu_free); | |
78 | } | |
79 | ||
80 | static unsigned find_get_pages(unsigned long start, | |
81 | unsigned int nr_pages, struct page **pages) | |
82 | { | |
83 | unsigned int i; | |
84 | unsigned int ret; | |
85 | unsigned int nr_found; | |
86 | ||
87 | rcu_read_lock(); | |
88 | restart: | |
89 | nr_found = radix_tree_gang_lookup_slot(&mt_tree, | |
90 | (void ***)pages, NULL, start, nr_pages); | |
91 | ret = 0; | |
92 | for (i = 0; i < nr_found; i++) { | |
93 | struct page *page; | |
94 | repeat: | |
95 | page = radix_tree_deref_slot((void **)pages[i]); | |
96 | if (unlikely(!page)) | |
97 | continue; | |
98 | ||
99 | if (radix_tree_exception(page)) { | |
100 | if (radix_tree_deref_retry(page)) { | |
101 | /* | |
102 | * Transient condition which can only trigger | |
103 | * when entry at index 0 moves out of or back | |
104 | * to root: none yet gotten, safe to restart. | |
105 | */ | |
106 | assert((start | i) == 0); | |
107 | goto restart; | |
108 | } | |
109 | /* | |
110 | * No exceptional entries are inserted in this test. | |
111 | */ | |
112 | assert(0); | |
113 | } | |
114 | ||
115 | pthread_mutex_lock(&page->lock); | |
116 | if (!page->count) { | |
117 | pthread_mutex_unlock(&page->lock); | |
118 | goto repeat; | |
119 | } | |
120 | /* don't actually update page refcount */ | |
121 | pthread_mutex_unlock(&page->lock); | |
122 | ||
123 | /* Has the page moved? */ | |
124 | if (unlikely(page != *((void **)pages[i]))) { | |
125 | goto repeat; | |
126 | } | |
127 | ||
128 | pages[ret] = page; | |
129 | ret++; | |
130 | } | |
131 | rcu_read_unlock(); | |
132 | return ret; | |
133 | } | |
134 | ||
135 | static pthread_barrier_t worker_barrier; | |
136 | ||
137 | static void *regression1_fn(void *arg) | |
138 | { | |
139 | rcu_register_thread(); | |
140 | ||
141 | if (pthread_barrier_wait(&worker_barrier) == | |
142 | PTHREAD_BARRIER_SERIAL_THREAD) { | |
143 | int j; | |
144 | ||
145 | for (j = 0; j < 1000000; j++) { | |
146 | struct page *p; | |
147 | ||
148 | p = page_alloc(); | |
149 | pthread_mutex_lock(&mt_lock); | |
150 | radix_tree_insert(&mt_tree, 0, p); | |
151 | pthread_mutex_unlock(&mt_lock); | |
152 | ||
153 | p = page_alloc(); | |
154 | pthread_mutex_lock(&mt_lock); | |
155 | radix_tree_insert(&mt_tree, 1, p); | |
156 | pthread_mutex_unlock(&mt_lock); | |
157 | ||
158 | pthread_mutex_lock(&mt_lock); | |
159 | p = radix_tree_delete(&mt_tree, 1); | |
160 | pthread_mutex_lock(&p->lock); | |
161 | p->count--; | |
162 | pthread_mutex_unlock(&p->lock); | |
163 | pthread_mutex_unlock(&mt_lock); | |
164 | page_free(p); | |
165 | ||
166 | pthread_mutex_lock(&mt_lock); | |
167 | p = radix_tree_delete(&mt_tree, 0); | |
168 | pthread_mutex_lock(&p->lock); | |
169 | p->count--; | |
170 | pthread_mutex_unlock(&p->lock); | |
171 | pthread_mutex_unlock(&mt_lock); | |
172 | page_free(p); | |
173 | } | |
174 | } else { | |
175 | int j; | |
176 | ||
177 | for (j = 0; j < 100000000; j++) { | |
178 | struct page *pages[10]; | |
179 | ||
180 | find_get_pages(0, 10, pages); | |
181 | } | |
182 | } | |
183 | ||
184 | rcu_unregister_thread(); | |
185 | ||
186 | return NULL; | |
187 | } | |
188 | ||
189 | static pthread_t *threads; | |
190 | void regression1_test(void) | |
191 | { | |
192 | int nr_threads; | |
193 | int i; | |
194 | long arg; | |
195 | ||
196 | /* Regression #1 */ | |
73bc029b | 197 | printv(1, "running regression test 1, should finish in under a minute\n"); |
1366c37e MW |
198 | nr_threads = 2; |
199 | pthread_barrier_init(&worker_barrier, NULL, nr_threads); | |
200 | ||
201 | threads = malloc(nr_threads * sizeof(pthread_t *)); | |
202 | ||
203 | for (i = 0; i < nr_threads; i++) { | |
204 | arg = i; | |
205 | if (pthread_create(&threads[i], NULL, regression1_fn, (void *)arg)) { | |
206 | perror("pthread_create"); | |
207 | exit(1); | |
208 | } | |
209 | } | |
210 | ||
211 | for (i = 0; i < nr_threads; i++) { | |
212 | if (pthread_join(threads[i], NULL)) { | |
213 | perror("pthread_join"); | |
214 | exit(1); | |
215 | } | |
216 | } | |
217 | ||
218 | free(threads); | |
219 | ||
73bc029b | 220 | printv(1, "regression test 1, done\n"); |
1366c37e | 221 | } |