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