1 | // SPDX-License-Identifier: GPL-2.0 |
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); |
47 | |
48 | struct page { |
49 | pthread_mutex_t lock; |
50 | struct rcu_head rcu; |
51 | int count; |
52 | unsigned long index; |
53 | }; |
54 | |
55 | static struct page *page_alloc(int index) |
56 | { |
57 | struct page *p; |
58 | p = malloc(sizeof(struct page)); |
59 | p->count = 1; |
60 | p->index = index; |
61 | pthread_mutex_init(&p->lock, NULL); |
62 | |
63 | return p; |
64 | } |
65 | |
66 | static void page_rcu_free(struct rcu_head *rcu) |
67 | { |
68 | struct page *p = container_of(rcu, struct page, rcu); |
69 | assert(!p->count); |
70 | pthread_mutex_destroy(&p->lock); |
71 | free(p); |
72 | } |
73 | |
74 | static void page_free(struct page *p) |
75 | { |
76 | call_rcu(head: &p->rcu, func: page_rcu_free); |
77 | } |
78 | |
79 | static unsigned find_get_pages(unsigned long start, |
80 | unsigned int nr_pages, struct page **pages) |
81 | { |
82 | XA_STATE(xas, &mt_tree, start); |
83 | struct page *page; |
84 | unsigned int ret = 0; |
85 | |
86 | rcu_read_lock(); |
87 | xas_for_each(&xas, page, ULONG_MAX) { |
88 | if (xas_retry(xas: &xas, entry: page)) |
89 | continue; |
90 | |
91 | pthread_mutex_lock(&page->lock); |
92 | if (!page->count) |
93 | goto unlock; |
94 | |
95 | /* don't actually update page refcount */ |
96 | pthread_mutex_unlock(&page->lock); |
97 | |
98 | /* Has the page moved? */ |
99 | if (unlikely(page != xas_reload(&xas))) |
100 | goto put_page; |
101 | |
102 | pages[ret] = page; |
103 | ret++; |
104 | continue; |
105 | unlock: |
106 | pthread_mutex_unlock(&page->lock); |
107 | put_page: |
108 | xas_reset(xas: &xas); |
109 | } |
110 | rcu_read_unlock(); |
111 | return ret; |
112 | } |
113 | |
114 | static pthread_barrier_t worker_barrier; |
115 | |
116 | static void *regression1_fn(void *arg) |
117 | { |
118 | rcu_register_thread(); |
119 | |
120 | if (pthread_barrier_wait(&worker_barrier) == |
121 | PTHREAD_BARRIER_SERIAL_THREAD) { |
122 | int j; |
123 | |
124 | for (j = 0; j < 1000000; j++) { |
125 | struct page *p; |
126 | |
127 | p = page_alloc(index: 0); |
128 | xa_lock(&mt_tree); |
129 | radix_tree_insert(&mt_tree, index: 0, p); |
130 | xa_unlock(&mt_tree); |
131 | |
132 | p = page_alloc(index: 1); |
133 | xa_lock(&mt_tree); |
134 | radix_tree_insert(&mt_tree, index: 1, p); |
135 | xa_unlock(&mt_tree); |
136 | |
137 | xa_lock(&mt_tree); |
138 | p = radix_tree_delete(&mt_tree, 1); |
139 | pthread_mutex_lock(&p->lock); |
140 | p->count--; |
141 | pthread_mutex_unlock(&p->lock); |
142 | xa_unlock(&mt_tree); |
143 | page_free(p); |
144 | |
145 | xa_lock(&mt_tree); |
146 | p = radix_tree_delete(&mt_tree, 0); |
147 | pthread_mutex_lock(&p->lock); |
148 | p->count--; |
149 | pthread_mutex_unlock(&p->lock); |
150 | xa_unlock(&mt_tree); |
151 | page_free(p); |
152 | } |
153 | } else { |
154 | int j; |
155 | |
156 | for (j = 0; j < 100000000; j++) { |
157 | struct page *pages[10]; |
158 | |
159 | find_get_pages(start: 0, nr_pages: 10, pages); |
160 | } |
161 | } |
162 | |
163 | rcu_unregister_thread(); |
164 | |
165 | return NULL; |
166 | } |
167 | |
168 | static pthread_t *threads; |
169 | void regression1_test(void) |
170 | { |
171 | int nr_threads; |
172 | int i; |
173 | long arg; |
174 | |
175 | /* Regression #1 */ |
176 | printv(1, "running regression test 1, should finish in under a minute\n" ); |
177 | nr_threads = 2; |
178 | pthread_barrier_init(&worker_barrier, NULL, nr_threads); |
179 | |
180 | threads = malloc(nr_threads * sizeof(*threads)); |
181 | |
182 | for (i = 0; i < nr_threads; i++) { |
183 | arg = i; |
184 | if (pthread_create(&threads[i], NULL, regression1_fn, (void *)arg)) { |
185 | perror("pthread_create" ); |
186 | exit(1); |
187 | } |
188 | } |
189 | |
190 | for (i = 0; i < nr_threads; i++) { |
191 | if (pthread_join(threads[i], NULL)) { |
192 | perror("pthread_join" ); |
193 | exit(1); |
194 | } |
195 | } |
196 | |
197 | free(threads); |
198 | |
199 | printv(1, "regression test 1, done\n" ); |
200 | } |
201 | |