1 // SPDX-License-Identifier: GPL-2.0
5 * Salman Qazi describes the following radix-tree bug:
7 * In the following case, we get can get a deadlock:
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
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.
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.
28 * This test should run to completion in a few seconds. The above bug would
29 * cause it to hang indefinitely.
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>
44 #include "regression.h"
46 static RADIX_TREE(mt_tree, GFP_KERNEL);
47 static pthread_mutex_t mt_lock = PTHREAD_MUTEX_INITIALIZER;
56 static struct page *page_alloc(void)
59 p = malloc(sizeof(struct page));
62 pthread_mutex_init(&p->lock, NULL);
67 static void page_rcu_free(struct rcu_head *rcu)
69 struct page *p = container_of(rcu, struct page, rcu);
71 pthread_mutex_destroy(&p->lock);
75 static void page_free(struct page *p)
77 call_rcu(&p->rcu, page_rcu_free);
80 static unsigned find_get_pages(unsigned long start,
81 unsigned int nr_pages, struct page **pages)
85 unsigned int nr_found;
89 nr_found = radix_tree_gang_lookup_slot(&mt_tree,
90 (void ***)pages, NULL, start, nr_pages);
92 for (i = 0; i < nr_found; i++) {
95 page = radix_tree_deref_slot((void **)pages[i]);
99 if (radix_tree_exception(page)) {
100 if (radix_tree_deref_retry(page)) {
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.
106 assert((start | i) == 0);
110 * No exceptional entries are inserted in this test.
115 pthread_mutex_lock(&page->lock);
117 pthread_mutex_unlock(&page->lock);
120 /* don't actually update page refcount */
121 pthread_mutex_unlock(&page->lock);
123 /* Has the page moved? */
124 if (unlikely(page != *((void **)pages[i]))) {
135 static pthread_barrier_t worker_barrier;
137 static void *regression1_fn(void *arg)
139 rcu_register_thread();
141 if (pthread_barrier_wait(&worker_barrier) ==
142 PTHREAD_BARRIER_SERIAL_THREAD) {
145 for (j = 0; j < 1000000; j++) {
149 pthread_mutex_lock(&mt_lock);
150 radix_tree_insert(&mt_tree, 0, p);
151 pthread_mutex_unlock(&mt_lock);
154 pthread_mutex_lock(&mt_lock);
155 radix_tree_insert(&mt_tree, 1, p);
156 pthread_mutex_unlock(&mt_lock);
158 pthread_mutex_lock(&mt_lock);
159 p = radix_tree_delete(&mt_tree, 1);
160 pthread_mutex_lock(&p->lock);
162 pthread_mutex_unlock(&p->lock);
163 pthread_mutex_unlock(&mt_lock);
166 pthread_mutex_lock(&mt_lock);
167 p = radix_tree_delete(&mt_tree, 0);
168 pthread_mutex_lock(&p->lock);
170 pthread_mutex_unlock(&p->lock);
171 pthread_mutex_unlock(&mt_lock);
177 for (j = 0; j < 100000000; j++) {
178 struct page *pages[10];
180 find_get_pages(0, 10, pages);
184 rcu_unregister_thread();
189 static pthread_t *threads;
190 void regression1_test(void)
197 printv(1, "running regression test 1, should finish in under a minute\n");
199 pthread_barrier_init(&worker_barrier, NULL, nr_threads);
201 threads = malloc(nr_threads * sizeof(pthread_t *));
203 for (i = 0; i < nr_threads; i++) {
205 if (pthread_create(&threads[i], NULL, regression1_fn, (void *)arg)) {
206 perror("pthread_create");
211 for (i = 0; i < nr_threads; i++) {
212 if (pthread_join(threads[i], NULL)) {
213 perror("pthread_join");
220 printv(1, "regression test 1, done\n");