tools/testing/radix-tree/regression1.c

   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 }