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