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 4
  20 #define TAG 0
  21 static pthread_mutex_t tree_lock = PTHREAD_MUTEX_INITIALIZER;
  22 static pthread_t threads[NUM_THREADS];
  23 static unsigned int seeds[3];
  24 RADIX_TREE(tree, GFP_KERNEL);
  25 bool test_complete;
  26
  27 /* relentlessly fill the tree with tagged entries */
  28 static void *add_entries_fn(void *arg)
  29 {
  30         int pgoff;
  31
  32         rcu_register_thread();
  33
  34         while (!test_complete) {
  35                 for (pgoff = 0; pgoff < 100; pgoff++) {
  36                         pthread_mutex_lock(&tree_lock);
  37                         if (item_insert(&tree, pgoff) == 0)
  38                                 item_tag_set(&tree, pgoff, TAG);
  39                         pthread_mutex_unlock(&tree_lock);
  40                 }
  41         }
  42
  43         rcu_unregister_thread();
  44
  45         return NULL;
  46 }
  47
  48 /*
  49  * Iterate over the tagged entries, doing a radix_tree_iter_retry() as we find
  50  * things that have been removed and randomly resetting our iteration to the
  51  * next chunk with radix_tree_iter_next().  Both radix_tree_iter_retry() and
  52  * radix_tree_iter_next() cause radix_tree_next_slot() to be called with a
  53  * NULL 'slot' variable.
  54  */
  55 static void *tagged_iteration_fn(void *arg)
  56 {
  57         struct radix_tree_iter iter;
  58         void **slot;
  59
  60         rcu_register_thread();
  61
  62         while (!test_complete) {
  63                 rcu_read_lock();
  64                 radix_tree_for_each_tagged(slot, &tree, &iter, 0, TAG) {
  65                         void *entry;
  66                         int i;
  67
  68                         /* busy wait to let removals happen */
  69                         for (i = 0; i < 1000000; i++)
  70                                 ;
  71
  72                         entry = radix_tree_deref_slot(slot);
  73                         if (unlikely(!entry))
  74                                 continue;
  75
  76                         if (radix_tree_deref_retry(entry)) {
  77                                 slot = radix_tree_iter_retry(&iter);
  78                                 continue;
  79                         }
  80
  81                         if (rand_r(&seeds[0]) % 50 == 0) {
  82                                 slot = radix_tree_iter_next(&iter);
  83                                 rcu_read_unlock();
  84                                 rcu_barrier();
  85                                 rcu_read_lock();
  86                         }
  87                 }
  88                 rcu_read_unlock();
  89         }
  90
  91         rcu_unregister_thread();
  92
  93         return NULL;
  94 }
  95
  96 /*
  97  * Iterate over the entries, doing a radix_tree_iter_retry() as we find things
  98  * that have been removed and randomly resetting our iteration to the next
  99  * chunk with radix_tree_iter_next().  Both radix_tree_iter_retry() and
 100  * radix_tree_iter_next() cause radix_tree_next_slot() to be called with a
 101  * NULL 'slot' variable.
 102  */
 103 static void *untagged_iteration_fn(void *arg)
 104 {
 105         struct radix_tree_iter iter;
 106         void **slot;
 107
 108         rcu_register_thread();
 109
 110         while (!test_complete) {
 111                 rcu_read_lock();
 112                 radix_tree_for_each_slot(slot, &tree, &iter, 0) {
 113                         void *entry;
 114                         int i;
 115
 116                         /* busy wait to let removals happen */
 117                         for (i = 0; i < 1000000; i++)
 118                                 ;
 119
 120                         entry = radix_tree_deref_slot(slot);
 121                         if (unlikely(!entry))
 122                                 continue;
 123
 124                         if (radix_tree_deref_retry(entry)) {
 125                                 slot = radix_tree_iter_retry(&iter);
 126                                 continue;
 127                         }
 128
 129                         if (rand_r(&seeds[1]) % 50 == 0) {
 130                                 slot = radix_tree_iter_next(&iter);
 131                                 rcu_read_unlock();
 132                                 rcu_barrier();
 133                                 rcu_read_lock();
 134                         }
 135                 }
 136                 rcu_read_unlock();
 137         }
 138
 139         rcu_unregister_thread();
 140
 141         return NULL;
 142 }
 143
 144 /*
 145  * Randomly remove entries to help induce radix_tree_iter_retry() calls in the
 146  * two iteration functions.
 147  */
 148 static void *remove_entries_fn(void *arg)
 149 {
 150         rcu_register_thread();
 151
 152         while (!test_complete) {
 153                 int pgoff;
 154
 155                 pgoff = rand_r(&seeds[2]) % 100;
 156
 157                 pthread_mutex_lock(&tree_lock);
 158                 item_delete(&tree, pgoff);
 159                 pthread_mutex_unlock(&tree_lock);
 160         }
 161
 162         rcu_unregister_thread();
 163
 164         return NULL;
 165 }
 166
 167 /* This is a unit test for a bug found by the syzkaller tester */
 168 void iteration_test(void)
 169 {
 170         int i;
 171
 172         printf("Running iteration tests for 10 seconds\n");
 173
 174         test_complete = false;
 175
 176         for (i = 0; i < 3; i++)
 177                 seeds[i] = rand();
 178
 179         if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
 180                 perror("pthread_create");
 181                 exit(1);
 182         }
 183         if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
 184                 perror("pthread_create");
 185                 exit(1);
 186         }
 187         if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
 188                 perror("pthread_create");
 189                 exit(1);
 190         }
 191         if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
 192                 perror("pthread_create");
 193                 exit(1);
 194         }
 195
 196         sleep(10);
 197         test_complete = true;
 198
 199         for (i = 0; i < NUM_THREADS; i++) {
 200                 if (pthread_join(threads[i], NULL)) {
 201                         perror("pthread_join");
 202                         exit(1);
 203                 }
 204         }
 205
 206         item_kill_tree(&tree);
 207 }