tools/testing/radix-tree/iteration_check.c

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