testing/radix-tree/iteration_check.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * iteration_check.c: test races having to do with xarray iteration
0004  * Copyright (c) 2016 Intel Corporation
0005  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
0006  */
0007 #include <pthread.h>
0008 #include "test.h"
0009
0010 #define NUM_THREADS 5
0011 #define MAX_IDX     100
0012 #define TAG     XA_MARK_0
0013 #define NEW_TAG     XA_MARK_1
0014
0015 static pthread_t threads[NUM_THREADS];
0016 static unsigned int seeds[3];
0017 static DEFINE_XARRAY(array);
0018 static bool test_complete;
0019 static int max_order;
0020
0021 void my_item_insert(struct xarray *xa, unsigned long index)
0022 {
0023     XA_STATE(xas, xa, index);
0024     struct item *item = item_create(index, 0);
0025     int order;
0026
0027 retry:
0028     xas_lock(&xas);
0029     for (order = max_order; order >= 0; order--) {
0030         xas_set_order(&xas, index, order);
0031         item->order = order;
0032         if (xas_find_conflict(&xas))
0033             continue;
0034         xas_store(&xas, item);
0035         xas_set_mark(&xas, TAG);
0036         break;
0037     }
0038     xas_unlock(&xas);
0039     if (xas_nomem(&xas, GFP_KERNEL))
0040         goto retry;
0041     if (order < 0)
0042         free(item);
0043 }
0044
0045 /* relentlessly fill the array with tagged entries */
0046 static void *add_entries_fn(void *arg)
0047 {
0048     rcu_register_thread();
0049
0050     while (!test_complete) {
0051         unsigned long pgoff;
0052
0053         for (pgoff = 0; pgoff < MAX_IDX; pgoff++) {
0054             my_item_insert(&array, pgoff);
0055         }
0056     }
0057
0058     rcu_unregister_thread();
0059
0060     return NULL;
0061 }
0062
0063 /*
0064  * Iterate over tagged entries, retrying when we find ourselves in a deleted
0065  * node and randomly pausing the iteration.
0066  */
0067 static void *tagged_iteration_fn(void *arg)
0068 {
0069     XA_STATE(xas, &array, 0);
0070     void *entry;
0071
0072     rcu_register_thread();
0073
0074     while (!test_complete) {
0075         xas_set(&xas, 0);
0076         rcu_read_lock();
0077         xas_for_each_marked(&xas, entry, ULONG_MAX, TAG) {
0078             if (xas_retry(&xas, entry))
0079                 continue;
0080
0081             if (rand_r(&seeds[0]) % 50 == 0) {
0082                 xas_pause(&xas);
0083                 rcu_read_unlock();
0084                 rcu_barrier();
0085                 rcu_read_lock();
0086             }
0087         }
0088         rcu_read_unlock();
0089     }
0090
0091     rcu_unregister_thread();
0092
0093     return NULL;
0094 }
0095
0096 /*
0097  * Iterate over the entries, retrying when we find ourselves in a deleted
0098  * node and randomly pausing the iteration.
0099  */
0100 static void *untagged_iteration_fn(void *arg)
0101 {
0102     XA_STATE(xas, &array, 0);
0103     void *entry;
0104
0105     rcu_register_thread();
0106
0107     while (!test_complete) {
0108         xas_set(&xas, 0);
0109         rcu_read_lock();
0110         xas_for_each(&xas, entry, ULONG_MAX) {
0111             if (xas_retry(&xas, entry))
0112                 continue;
0113
0114             if (rand_r(&seeds[1]) % 50 == 0) {
0115                 xas_pause(&xas);
0116                 rcu_read_unlock();
0117                 rcu_barrier();
0118                 rcu_read_lock();
0119             }
0120         }
0121         rcu_read_unlock();
0122     }
0123
0124     rcu_unregister_thread();
0125
0126     return NULL;
0127 }
0128
0129 /*
0130  * Randomly remove entries to help induce retries in the
0131  * two iteration functions.
0132  */
0133 static void *remove_entries_fn(void *arg)
0134 {
0135     rcu_register_thread();
0136
0137     while (!test_complete) {
0138         int pgoff;
0139         struct item *item;
0140
0141         pgoff = rand_r(&seeds[2]) % MAX_IDX;
0142
0143         item = xa_erase(&array, pgoff);
0144         if (item)
0145             item_free(item, pgoff);
0146     }
0147
0148     rcu_unregister_thread();
0149
0150     return NULL;
0151 }
0152
0153 static void *tag_entries_fn(void *arg)
0154 {
0155     rcu_register_thread();
0156
0157     while (!test_complete) {
0158         tag_tagged_items(&array, 0, MAX_IDX, 10, TAG, NEW_TAG);
0159     }
0160     rcu_unregister_thread();
0161     return NULL;
0162 }
0163
0164 /* This is a unit test for a bug found by the syzkaller tester */
0165 void iteration_test(unsigned order, unsigned test_duration)
0166 {
0167     int i;
0168
0169     printv(1, "Running %siteration tests for %d seconds\n",
0170             order > 0 ? "multiorder " : "", test_duration);
0171
0172     max_order = order;
0173     test_complete = false;
0174
0175     for (i = 0; i < 3; i++)
0176         seeds[i] = rand();
0177
0178     if (pthread_create(&threads[0], NULL, tagged_iteration_fn, NULL)) {
0179         perror("create tagged iteration thread");
0180         exit(1);
0181     }
0182     if (pthread_create(&threads[1], NULL, untagged_iteration_fn, NULL)) {
0183         perror("create untagged iteration thread");
0184         exit(1);
0185     }
0186     if (pthread_create(&threads[2], NULL, add_entries_fn, NULL)) {
0187         perror("create add entry thread");
0188         exit(1);
0189     }
0190     if (pthread_create(&threads[3], NULL, remove_entries_fn, NULL)) {
0191         perror("create remove entry thread");
0192         exit(1);
0193     }
0194     if (pthread_create(&threads[4], NULL, tag_entries_fn, NULL)) {
0195         perror("create tag entry thread");
0196         exit(1);
0197     }
0198
0199     sleep(test_duration);
0200     test_complete = true;
0201
0202     for (i = 0; i < NUM_THREADS; i++) {
0203         if (pthread_join(threads[i], NULL)) {
0204             perror("pthread_join");
0205             exit(1);
0206         }
0207     }
0208
0209     item_kill_tree(&array);
0210 }