tools/testing/radix-tree/iteration_check.c

   1 /*
   2  * iteration_check.c: test races having to do with xarray iteration
   3  * Copyright (c) 2016 Intel Corporation
   4  * Author: Ross Zwisler <[email protected]>
   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 <pthread.h>
  16 #include "test.h"
  17
  18 #define NUM_THREADS     5
  19 #define MAX_IDX         100
  20 #define TAG             XA_MARK_0
  21 #define NEW_TAG         XA_MARK_1
  22
  23 static pthread_t threads[NUM_THREADS];
  24 static unsigned int seeds[3];
  25 static DEFINE_XARRAY(array);
  26 static bool test_complete;
  27 static int max_order;
  28
  29 void my_item_insert(struct xarray *xa, unsigned long index)
  30 {
  31         XA_STATE(xas, xa, index);
  32         struct item *item = item_create(index, 0);
  33         int order;
  34
  35 retry:
  36         xas_lock(&xas);
  37         for (order = max_order; order >= 0; order--) {
  38                 xas_set_order(&xas, index, order);
  39                 item->order = order;
  40                 if (xas_find_conflict(&xas))
  41                         continue;
  42                 xas_store(&xas, item);
  43                 xas_set_mark(&xas, TAG);
  44                 break;
  45         }
  46         xas_unlock(&xas);
  47         if (xas_nomem(&xas, GFP_KERNEL))
  48                 goto retry;
  49         if (order < 0)
  50                 free(item);
  51 }
  52
  53 /* relentlessly fill the array with tagged entries */
  54 static void *add_entries_fn(void *arg)
  55 {
  56         rcu_register_thread();
  57
  58         while (!test_complete) {
  59                 unsigned long pgoff;
  60
  61                 for (pgoff = 0; pgoff < MAX_IDX; pgoff++) {
  62                         my_item_insert(&array, pgoff);
  63                 }
  64         }
  65
  66         rcu_unregister_thread();
  67
  68         return NULL;
  69 }
  70
  71 /*
  72  * Iterate over tagged entries, retrying when we find ourselves in a deleted
  73  * node and randomly pausing the iteration.
  74  */
  75 static void *tagged_iteration_fn(void *arg)
  76 {
  77         XA_STATE(xas, &array, 0);
  78         void *entry;
  79
  80         rcu_register_thread();
  81
  82         while (!test_complete) {
  83                 xas_set(&xas, 0);
  84                 rcu_read_lock();
  85                 xas_for_each_marked(&xas, entry, ULONG_MAX, TAG) {
  86                         if (xas_retry(&xas, entry))
  87                                 continue;
  88
  89                         if (rand_r(&seeds[0]) % 50 == 0) {
  90                                 xas_pause(&xas);
  91                                 rcu_read_unlock();
  92                                 rcu_barrier();
  93                                 rcu_read_lock();
  94                         }
  95                 }
  96                 rcu_read_unlock();
  97         }
  98
  99         rcu_unregister_thread();
 100
 101         return NULL;
 102 }
 103
 104 /*
 105  * Iterate over the entries, retrying when we find ourselves in a deleted
 106  * node and randomly pausing the iteration.
 107  */
 108 static void *untagged_iteration_fn(void *arg)
 109 {
 110         XA_STATE(xas, &array, 0);
 111         void *entry;
 112
 113         rcu_register_thread();
 114
 115         while (!test_complete) {
 116                 xas_set(&xas, 0);
 117                 rcu_read_lock();
 118                 xas_for_each(&xas, entry, ULONG_MAX) {
 119                         if (xas_retry(&xas, entry))
 120                                 continue;
 121
 122                         if (rand_r(&seeds[1]) % 50 == 0) {
 123                                 xas_pause(&xas);
 124                                 rcu_read_unlock();
 125                                 rcu_barrier();
 126                                 rcu_read_lock();
 127                         }
 128                 }
 129                 rcu_read_unlock();
 130         }
 131
 132         rcu_unregister_thread();
 133
 134         return NULL;
 135 }
 136
 137 /*
 138  * Randomly remove entries to help induce retries in the
 139  * two iteration functions.
 140  */
 141 static void *remove_entries_fn(void *arg)
 142 {
 143         rcu_register_thread();
 144
 145         while (!test_complete) {
 146                 int pgoff;
 147                 struct item *item;
 148
 149                 pgoff = rand_r(&seeds[2]) % MAX_IDX;
 150
 151                 item = xa_erase(&array, pgoff);
 152                 if (item)
 153                         item_free(item, pgoff);
 154         }
 155
 156         rcu_unregister_thread();
 157
 158         return NULL;
 159 }
 160
 161 static void *tag_entries_fn(void *arg)
 162 {
 163         rcu_register_thread();
 164
 165         while (!test_complete) {
 166                 tag_tagged_items(&array, 0, MAX_IDX, 10, TAG, NEW_TAG);
 167         }
 168         rcu_unregister_thread();
 169         return NULL;
 170 }
 171
 172 /* This is a unit test for a bug found by the syzkaller tester */
 173 void iteration_test(unsigned order, unsigned test_duration)
 174 {
 175         int i;
 176
 177         printv(1, "Running %siteration tests for %d seconds\n",
 178                         order > 0 ? "multiorder " : "", test_duration);
 179
 180         max_order = order;
 181         test_complete = false;
 182
 183         for (i = 0; i < 3; i++)
 184                 seeds[i] = rand();
 185
 186         if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
 187                 perror("create tagged iteration thread");
 188                 exit(1);
 189         }
 190         if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
 191                 perror("create untagged iteration thread");
 192                 exit(1);
 193         }
 194         if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
 195                 perror("create add entry thread");
 196                 exit(1);
 197         }
 198         if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
 199                 perror("create remove entry thread");
 200                 exit(1);
 201         }
 202         if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) {
 203                 perror("create tag entry thread");
 204                 exit(1);
 205         }
 206
 207         sleep(test_duration);
 208         test_complete = true;
 209
 210         for (i = 0; i < NUM_THREADS; i++) {
 211                 if (pthread_join(threads[i], NULL)) {
 212                         perror("pthread_join");
 213                         exit(1);
 214                 }
 215         }
 216
 217         item_kill_tree(&array);
 218 }