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(&p->rcu, 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, 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 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; 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(pthread_t *)); 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