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