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
46static RADIX_TREE(mt_tree, GFP_KERNEL);
47
48struct page {
49	pthread_mutex_t lock;
50	struct rcu_head rcu;
51	int count;
52	unsigned long index;
53};
54
55static 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
66static 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
74static void page_free(struct page *p)
75{
76	call_rcu(&p->rcu, page_rcu_free);
77}
78
79static 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;
105unlock:
106		pthread_mutex_unlock(&page->lock);
107put_page:
108		xas_reset(&xas);
109	}
110	rcu_read_unlock();
111	return ret;
112}
113
114static pthread_barrier_t worker_barrier;
115
116static 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
168static pthread_t *threads;
169void 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