xref: /linux/tools/testing/radix-tree/regression1.c (revision a1c613ae4c322ddd58d5a8539dbfba2a0380a8c0)
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 
page_alloc(int index)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 
page_rcu_free(struct rcu_head * rcu)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 
page_free(struct page * p)74 static void page_free(struct page *p)
75 {
76 	call_rcu(&p->rcu, page_rcu_free);
77 }
78 
find_get_pages(unsigned long start,unsigned int nr_pages,struct page ** pages)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, 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);
109 	}
110 	rcu_read_unlock();
111 	return ret;
112 }
113 
114 static pthread_barrier_t worker_barrier;
115 
regression1_fn(void * arg)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(0);
128 			xa_lock(&mt_tree);
129 			radix_tree_insert(&mt_tree, 0, p);
130 			xa_unlock(&mt_tree);
131 
132 			p = page_alloc(1);
133 			xa_lock(&mt_tree);
134 			radix_tree_insert(&mt_tree, 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(0, 10, pages);
160 		}
161 	}
162 
163 	rcu_unregister_thread();
164 
165 	return NULL;
166 }
167 
168 static pthread_t *threads;
regression1_test(void)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