1 // SPDX-License-Identifier: GPL-2.0 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <unistd.h> 5 #include <time.h> 6 #include <assert.h> 7 #include <limits.h> 8 9 #include <linux/slab.h> 10 #include <linux/radix-tree.h> 11 12 #include "test.h" 13 #include "regression.h" 14 15 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop) 16 { 17 long idx; 18 RADIX_TREE(tree, GFP_KERNEL); 19 20 middle = 1 << 30; 21 22 for (idx = -down; idx < up; idx++) 23 item_insert(&tree, middle + idx); 24 25 item_check_absent(&tree, middle - down - 1); 26 for (idx = -down; idx < up; idx++) 27 item_check_present(&tree, middle + idx); 28 item_check_absent(&tree, middle + up); 29 30 if (chunk > 0) { 31 item_gang_check_present(&tree, middle - down, up + down, 32 chunk, hop); 33 item_full_scan(&tree, middle - down, down + up, chunk); 34 } 35 item_kill_tree(&tree); 36 } 37 38 void gang_check(void) 39 { 40 __gang_check(1UL << 30, 128, 128, 35, 2); 41 __gang_check(1UL << 31, 128, 128, 32, 32); 42 __gang_check(1UL << 31, 128, 128, 32, 100); 43 __gang_check(1UL << 31, 128, 128, 17, 7); 44 __gang_check(0xffff0000UL, 0, 65536, 17, 7); 45 __gang_check(0xfffffffeUL, 1, 1, 17, 7); 46 } 47 48 void __big_gang_check(void) 49 { 50 unsigned long start; 51 int wrapped = 0; 52 53 start = 0; 54 do { 55 unsigned long old_start; 56 57 // printf("0x%08lx\n", start); 58 __gang_check(start, rand() % 113 + 1, rand() % 71, 59 rand() % 157, rand() % 91 + 1); 60 old_start = start; 61 start += rand() % 1000000; 62 start %= 1ULL << 33; 63 if (start < old_start) 64 wrapped = 1; 65 } while (!wrapped); 66 } 67 68 void big_gang_check(bool long_run) 69 { 70 int i; 71 72 for (i = 0; i < (long_run ? 1000 : 3); i++) { 73 __big_gang_check(); 74 printv(2, "%d ", i); 75 fflush(stdout); 76 } 77 } 78 79 void add_and_check(void) 80 { 81 RADIX_TREE(tree, GFP_KERNEL); 82 83 item_insert(&tree, 44); 84 item_check_present(&tree, 44); 85 item_check_absent(&tree, 43); 86 item_kill_tree(&tree); 87 } 88 89 void dynamic_height_check(void) 90 { 91 int i; 92 RADIX_TREE(tree, GFP_KERNEL); 93 tree_verify_min_height(&tree, 0); 94 95 item_insert(&tree, 42); 96 tree_verify_min_height(&tree, 42); 97 98 item_insert(&tree, 1000000); 99 tree_verify_min_height(&tree, 1000000); 100 101 assert(item_delete(&tree, 1000000)); 102 tree_verify_min_height(&tree, 42); 103 104 assert(item_delete(&tree, 42)); 105 tree_verify_min_height(&tree, 0); 106 107 for (i = 0; i < 1000; i++) { 108 item_insert(&tree, i); 109 tree_verify_min_height(&tree, i); 110 } 111 112 i--; 113 for (;;) { 114 assert(item_delete(&tree, i)); 115 if (i == 0) { 116 tree_verify_min_height(&tree, 0); 117 break; 118 } 119 i--; 120 tree_verify_min_height(&tree, i); 121 } 122 123 item_kill_tree(&tree); 124 } 125 126 void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag) 127 { 128 int i; 129 130 for (i = 0; i < count; i++) { 131 /* if (i % 1000 == 0) 132 putchar('.'); */ 133 if (idx[i] < start || idx[i] > end) { 134 if (item_tag_get(tree, idx[i], totag)) { 135 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, 136 end, idx[i], item_tag_get(tree, idx[i], 137 fromtag), 138 item_tag_get(tree, idx[i], totag)); 139 } 140 assert(!item_tag_get(tree, idx[i], totag)); 141 continue; 142 } 143 if (item_tag_get(tree, idx[i], fromtag) ^ 144 item_tag_get(tree, idx[i], totag)) { 145 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end, 146 idx[i], item_tag_get(tree, idx[i], fromtag), 147 item_tag_get(tree, idx[i], totag)); 148 } 149 assert(!(item_tag_get(tree, idx[i], fromtag) ^ 150 item_tag_get(tree, idx[i], totag))); 151 } 152 } 153 154 #define ITEMS 50000 155 156 void copy_tag_check(void) 157 { 158 RADIX_TREE(tree, GFP_KERNEL); 159 unsigned long idx[ITEMS]; 160 unsigned long start, end, count = 0, tagged, cur, tmp; 161 int i; 162 163 // printf("generating radix tree indices...\n"); 164 start = rand(); 165 end = rand(); 166 if (start > end && (rand() % 10)) { 167 cur = start; 168 start = end; 169 end = cur; 170 } 171 /* Specifically create items around the start and the end of the range 172 * with high probability to check for off by one errors */ 173 cur = rand(); 174 if (cur & 1) { 175 item_insert(&tree, start); 176 if (cur & 2) { 177 if (start <= end) 178 count++; 179 item_tag_set(&tree, start, 0); 180 } 181 } 182 if (cur & 4) { 183 item_insert(&tree, start-1); 184 if (cur & 8) 185 item_tag_set(&tree, start-1, 0); 186 } 187 if (cur & 16) { 188 item_insert(&tree, end); 189 if (cur & 32) { 190 if (start <= end) 191 count++; 192 item_tag_set(&tree, end, 0); 193 } 194 } 195 if (cur & 64) { 196 item_insert(&tree, end+1); 197 if (cur & 128) 198 item_tag_set(&tree, end+1, 0); 199 } 200 201 for (i = 0; i < ITEMS; i++) { 202 do { 203 idx[i] = rand(); 204 } while (item_lookup(&tree, idx[i])); 205 206 item_insert(&tree, idx[i]); 207 if (rand() & 1) { 208 item_tag_set(&tree, idx[i], 0); 209 if (idx[i] >= start && idx[i] <= end) 210 count++; 211 } 212 /* if (i % 1000 == 0) 213 putchar('.'); */ 214 } 215 216 // printf("\ncopying tags...\n"); 217 tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1); 218 219 // printf("checking copied tags\n"); 220 assert(tagged == count); 221 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1); 222 223 /* Copy tags in several rounds */ 224 // printf("\ncopying tags...\n"); 225 tmp = rand() % (count / 10 + 2); 226 tagged = tag_tagged_items(&tree, start, end, tmp, XA_MARK_0, XA_MARK_2); 227 assert(tagged == count); 228 229 // printf("%lu %lu %lu\n", tagged, tmp, count); 230 // printf("checking copied tags\n"); 231 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2); 232 verify_tag_consistency(&tree, 0); 233 verify_tag_consistency(&tree, 1); 234 verify_tag_consistency(&tree, 2); 235 // printf("\n"); 236 item_kill_tree(&tree); 237 } 238 239 static void single_thread_tests(bool long_run) 240 { 241 int i; 242 243 printv(1, "starting single_thread_tests: %d allocated, preempt %d\n", 244 nr_allocated, preempt_count); 245 multiorder_checks(); 246 rcu_barrier(); 247 printv(2, "after multiorder_check: %d allocated, preempt %d\n", 248 nr_allocated, preempt_count); 249 tag_check(); 250 rcu_barrier(); 251 printv(2, "after tag_check: %d allocated, preempt %d\n", 252 nr_allocated, preempt_count); 253 gang_check(); 254 rcu_barrier(); 255 printv(2, "after gang_check: %d allocated, preempt %d\n", 256 nr_allocated, preempt_count); 257 add_and_check(); 258 rcu_barrier(); 259 printv(2, "after add_and_check: %d allocated, preempt %d\n", 260 nr_allocated, preempt_count); 261 dynamic_height_check(); 262 rcu_barrier(); 263 printv(2, "after dynamic_height_check: %d allocated, preempt %d\n", 264 nr_allocated, preempt_count); 265 idr_checks(); 266 ida_tests(); 267 rcu_barrier(); 268 printv(2, "after idr_checks: %d allocated, preempt %d\n", 269 nr_allocated, preempt_count); 270 big_gang_check(long_run); 271 rcu_barrier(); 272 printv(2, "after big_gang_check: %d allocated, preempt %d\n", 273 nr_allocated, preempt_count); 274 for (i = 0; i < (long_run ? 2000 : 3); i++) { 275 copy_tag_check(); 276 printv(2, "%d ", i); 277 fflush(stdout); 278 } 279 rcu_barrier(); 280 printv(2, "after copy_tag_check: %d allocated, preempt %d\n", 281 nr_allocated, preempt_count); 282 } 283 284 int main(int argc, char **argv) 285 { 286 bool long_run = false; 287 int opt; 288 unsigned int seed = time(NULL); 289 290 while ((opt = getopt(argc, argv, "ls:v")) != -1) { 291 if (opt == 'l') 292 long_run = true; 293 else if (opt == 's') 294 seed = strtoul(optarg, NULL, 0); 295 else if (opt == 'v') 296 test_verbose++; 297 } 298 299 printf("random seed %u\n", seed); 300 srand(seed); 301 302 printf("running tests\n"); 303 304 rcu_register_thread(); 305 radix_tree_init(); 306 307 xarray_tests(); 308 regression1_test(); 309 regression2_test(); 310 regression3_test(); 311 regression4_test(); 312 iteration_test(0, 10 + 90 * long_run); 313 iteration_test(7, 10 + 90 * long_run); 314 single_thread_tests(long_run); 315 316 /* Free any remaining preallocated nodes */ 317 radix_tree_cpu_dead(0); 318 319 benchmark(); 320 321 rcu_barrier(); 322 printv(2, "after rcu_barrier: %d allocated, preempt %d\n", 323 nr_allocated, preempt_count); 324 rcu_unregister_thread(); 325 326 printf("tests completed\n"); 327 328 exit(0); 329 } 330