tools/testing/radix-tree/iteration_check.c

   1 /*
   2  * iteration_check.c: test races having to do with radix tree iteration
   3  * Copyright (c) 2016 Intel Corporation
   4  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
   5  *
   6  * This program is free software; you can redistribute it and/or modify it
   7  * under the terms and conditions of the GNU General Public License,
   8  * version 2, as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  13  * more details.
  14  */
  15 #include <linux/radix-tree.h>
  16 #include <pthread.h>
  17 #include "test.h"
  18
  19 #define NUM_THREADS     5
  20 #define MAX_IDX         100
  21 #define TAG             0
  22 #define NEW_TAG         1
  23
  24 static pthread_mutex_t tree_lock = PTHREAD_MUTEX_INITIALIZER;
  25 static pthread_t threads[NUM_THREADS];
  26 static unsigned int seeds[3];
  27 static RADIX_TREE(tree, GFP_KERNEL);
  28 static bool test_complete;
  29 static int max_order;
  30
  31 /* relentlessly fill the tree with tagged entries */
  32 static void *add_entries_fn(void *arg)
  33 {
  34         rcu_register_thread();
  35
  36         while (!test_complete) {
  37                 unsigned long pgoff;
  38                 int order;
  39
  40                 for (pgoff = 0; pgoff < MAX_IDX; pgoff++) {
  41                         pthread_mutex_lock(&tree_lock);
  42                         for (order = max_order; order >= 0; order--) {
  43                                 if (item_insert_order(&tree, pgoff, order)
  44                                                 == 0) {
  45                                         item_tag_set(&tree, pgoff, TAG);
  46                                         break;
  47                                 }
  48                         }
  49                         pthread_mutex_unlock(&tree_lock);
  50                 }
  51         }
  52
  53         rcu_unregister_thread();
  54
  55         return NULL;
  56 }
  57
  58 /*
  59  * Iterate over the tagged entries, doing a radix_tree_iter_retry() as we find
  60  * things that have been removed and randomly resetting our iteration to the
  61  * next chunk with radix_tree_iter_resume().  Both radix_tree_iter_retry() and
  62  * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a
  63  * NULL 'slot' variable.
  64  */
  65 static void *tagged_iteration_fn(void *arg)
  66 {
  67         struct radix_tree_iter iter;
  68         void **slot;
  69
  70         rcu_register_thread();
  71
  72         while (!test_complete) {
  73                 rcu_read_lock();
  74                 radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) {
  75                         void *entry = radix_tree_deref_slot(slot);
  76                         if (unlikely(!entry))
  77                                 continue;
  78
  79                         if (radix_tree_deref_retry(entry)) {
  80                                 slot = radix_tree_iter_retry(&iter);
  81                                 continue;
  82                         }
  83
  84                         if (rand_r(&seeds[0]) % 50 == 0) {
  85                                 slot = radix_tree_iter_resume(slot, &iter);
  86                                 rcu_read_unlock();
  87                                 rcu_barrier();
  88                                 rcu_read_lock();
  89                         }
  90                 }
  91                 rcu_read_unlock();
  92         }
  93
  94         rcu_unregister_thread();
  95
  96         return NULL;
  97 }
  98
  99 /*
 100  * Iterate over the entries, doing a radix_tree_iter_retry() as we find things
 101  * that have been removed and randomly resetting our iteration to the next
 102  * chunk with radix_tree_iter_resume().  Both radix_tree_iter_retry() and
 103  * radix_tree_iter_resume() cause radix_tree_next_slot() to be called with a
 104  * NULL 'slot' variable.
 105  */
 106 static void *untagged_iteration_fn(void *arg)
 107 {
 108         struct radix_tree_iter iter;
 109         void **slot;
 110
 111         rcu_register_thread();
 112
 113         while (!test_complete) {
 114                 rcu_read_lock();
 115                 radix_tree_for_each_slot(slot, &tree, &iter, 0) {
 116                         void *entry = radix_tree_deref_slot(slot);
 117                         if (unlikely(!entry))
 118                                 continue;
 119
 120                         if (radix_tree_deref_retry(entry)) {
 121                                 slot = radix_tree_iter_retry(&iter);
 122                                 continue;
 123                         }
 124
 125                         if (rand_r(&seeds[1]) % 50 == 0) {
 126                                 slot = radix_tree_iter_resume(slot, &iter);
 127                                 rcu_read_unlock();
 128                                 rcu_barrier();
 129                                 rcu_read_lock();
 130                         }
 131                 }
 132                 rcu_read_unlock();
 133         }
 134
 135         rcu_unregister_thread();
 136
 137         return NULL;
 138 }
 139
 140 /*
 141  * Randomly remove entries to help induce radix_tree_iter_retry() calls in the
 142  * two iteration functions.
 143  */
 144 static void *remove_entries_fn(void *arg)
 145 {
 146         rcu_register_thread();
 147
 148         while (!test_complete) {
 149                 int pgoff;
 150
 151                 pgoff = rand_r(&seeds[2]) % MAX_IDX;
 152
 153                 pthread_mutex_lock(&tree_lock);
 154                 item_delete(&tree, pgoff);
 155                 pthread_mutex_unlock(&tree_lock);
 156         }
 157
 158         rcu_unregister_thread();
 159
 160         return NULL;
 161 }
 162
 163 static void *tag_entries_fn(void *arg)
 164 {
 165         rcu_register_thread();
 166
 167         while (!test_complete) {
 168                 tag_tagged_items(&tree, &tree_lock, 0, MAX_IDX, 10, TAG,
 169                                         NEW_TAG);
 170         }
 171         rcu_unregister_thread();
 172         return NULL;
 173 }
 174
 175 /* This is a unit test for a bug found by the syzkaller tester */
 176 void iteration_test(unsigned order, unsigned test_duration)
 177 {
 178         int i;
 179
 180         printv(1, "Running %siteration tests for %d seconds\n",
 181                         order > 0 ? "multiorder " : "", test_duration);
 182
 183         max_order = order;
 184         test_complete = false;
 185
 186         for (i = 0; i < 3; i++)
 187                 seeds[i] = rand();
 188
 189         if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
 190                 perror("create tagged iteration thread");
 191                 exit(1);
 192         }
 193         if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
 194                 perror("create untagged iteration thread");
 195                 exit(1);
 196         }
 197         if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
 198                 perror("create add entry thread");
 199                 exit(1);
 200         }
 201         if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
 202                 perror("create remove entry thread");
 203                 exit(1);
 204         }
 205         if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) {
 206                 perror("create tag entry thread");
 207                 exit(1);
 208         }
 209
 210         sleep(test_duration);
 211         test_complete = true;
 212
 213         for (i = 0; i < NUM_THREADS; i++) {
 214                 if (pthread_join(threads[i], NULL)) {
 215                         perror("pthread_join");
 216                         exit(1);
 217                 }
 218         }
 219
 220         item_kill_tree(&tree);
 221 }