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 } 181