// SPDX-License-Identifier: GPL-2.0
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <assert.h>
#include <limits.h>
#include <linux/slab.h>
#include <linux/radix-tree.h>
#include "test.h"
#include "regression.h"
void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
{
long idx;
RADIX_TREE(tree, GFP_KERNEL);
middle = 1 << 30;
for (idx = -down; idx < up; idx++)
item_insert(&tree, middle + idx);
item_check_absent(&tree, middle - down - 1);
for (idx = -down; idx < up; idx++)
item_check_present(&tree, middle + idx);
item_check_absent(&tree, middle + up);
if (chunk > 0) {
item_gang_check_present(&tree, middle - down, up + down,
chunk, hop);
item_full_scan(&tree, middle - down, down + up, chunk);
}
item_kill_tree(&tree);
}
void gang_check(void)
{
__gang_check(1UL << 30, 128, 128, 35, 2);
__gang_check(1UL << 31, 128, 128, 32, 32);
__gang_check(1UL << 31, 128, 128, 32, 100);
__gang_check(1UL << 31, 128, 128, 17, 7);
__gang_check(0xffff0000UL, 0, 65536, 17, 7);
__gang_check(0xfffffffeUL, 1, 1, 17, 7);
}
void __big_gang_check(void)
{
unsigned long start;
int wrapped = 0;
start = 0;
do {
unsigned long old_start;
// printf("0x%08lx\n", start);
__gang_check(start, rand() % 113 + 1, rand() % 71,
rand() % 157, rand() % 91 + 1);
old_start = start;
start += rand() % 1000000;
start %= 1ULL << 33;
if (start < old_start)
wrapped = 1;
} while (!wrapped);
}
void big_gang_check(bool long_run)
{
int i;
for (i = 0; i < (long_run ? 1000 : 3); i++) {
__big_gang_check();
printv(2, "%d ", i);
fflush(stdout);
}
}
void add_and_check(void)
{
RADIX_TREE(tree, GFP_KERNEL);
item_insert(&tree, 44);
item_check_present(&tree, 44);
item_check_absent(&tree, 43);
item_kill_tree(&tree);
}
void dynamic_height_check(void)
{
int i;
RADIX_TREE(tree, GFP_KERNEL);
tree_verify_min_height(&tree, 0);
item_insert(&tree, 42);
tree_verify_min_height(&tree, 42);
item_insert(&tree, 1000000);
tree_verify_min_height(&tree, 1000000);
assert(item_delete(&tree, 1000000));
tree_verify_min_height(&tree, 42);
assert(item_delete(&tree, 42));
tree_verify_min_height(&tree, 0);
for (i = 0; i < 1000; i++) {
item_insert(&tree, i);
tree_verify_min_height(&tree, i);
}
i--;
for (;;) {
assert(item_delete(&tree, i));
if (i == 0) {
tree_verify_min_height(&tree, 0);
break;
}
i--;
tree_verify_min_height(&tree, i);
}
item_kill_tree(&tree);
}
void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
{
int i;
for (i = 0; i < count; i++) {
/* if (i % 1000 == 0)
putchar('.'); */
if (idx[i] < start || idx[i] > end) {
if (item_tag_get(tree, idx[i], totag)) {
printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
end, idx[i], item_tag_get(tree, idx[i],
fromtag),
item_tag_get(tree, idx[i], totag));
}
assert(!item_tag_get(tree, idx[i], totag));
continue;
}
if (item_tag_get(tree, idx[i], fromtag) ^
item_tag_get(tree, idx[i], totag)) {
printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
idx[i], item_tag_get(tree, idx[i], fromtag),
item_tag_get(tree, idx[i], totag));
}
assert(!(item_tag_get(tree, idx[i], fromtag) ^
item_tag_get(tree, idx[i], totag)));
}
}
#define ITEMS 50000
void copy_tag_check(void)
{
RADIX_TREE(tree, GFP_KERNEL);
unsigned long idx[ITEMS];
unsigned long start, end, count = 0, tagged, cur, tmp;
int i;
// printf("generating radix tree indices...\n");
start = rand();
end = rand();
if (start > end && (rand() % 10)) {
cur = start;
start = end;
end = cur;
}
/* Specifically create items around the start and the end of the range
* with high probability to check for off by one errors */
cur = rand();
if (cur & 1) {
item_insert(&tree, start);
if (cur & 2) {
if (start <= end)
count++;
item_tag_set(&tree, start, 0);
}
}
if (cur & 4) {
item_insert(&tree, start-1);
if (cur & 8)
item_tag_set(&tree, start-1, 0);
}
if (cur & 16) {
item_insert(&tree, end);
if (cur & 32) {
if (start <= end)
count++;
item_tag_set(&tree, end, 0);
}
}
if (cur & 64) {
item_insert(&tree, end+1);
if (cur & 128)
item_tag_set(&tree, end+1, 0);
}
for (i = 0; i < ITEMS; i++) {
do {
idx[i] = rand();
} while (item_lookup(&tree, idx[i]));
item_insert(&tree, idx[i]);
if (rand() & 1) {
item_tag_set(&tree, idx[i], 0);
if (idx[i] >= start && idx[i] <= end)
count++;
}
/* if (i % 1000 == 0)
putchar('.'); */
}
// printf("\ncopying tags...\n");
tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);
// printf("checking copied tags\n");
assert(tagged == count);
check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
/* Copy tags in several rounds */
// printf("\ncopying tags...\n");
tmp = rand() % (count / 10 + 2);
tagged = tag_tagged_items(&tree, start, end, tmp, XA_MARK_0, XA_MARK_2);
assert(tagged == count);
// printf("%lu %lu %lu\n", tagged, tmp, count);
// printf("checking copied tags\n");
check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
verify_tag_consistency(&tree, 0);
verify_tag_consistency(&tree, 1);
verify_tag_consistency(&tree, 2);
// printf("\n");
item_kill_tree(&tree);
}
static void single_thread_tests(bool long_run)
{
int i;
printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
multiorder_checks();
rcu_barrier();
printv(2, "after multiorder_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
tag_check();
rcu_barrier();
printv(2, "after tag_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
gang_check();
rcu_barrier();
printv(2, "after gang_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
add_and_check();
rcu_barrier();
printv(2, "after add_and_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
dynamic_height_check();
rcu_barrier();
printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
idr_checks();
ida_tests();
rcu_barrier();
printv(2, "after idr_checks: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
big_gang_check(long_run);
rcu_barrier();
printv(2, "after big_gang_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
for (i = 0; i < (long_run ? 2000 : 3); i++) {
copy_tag_check();
printv(2, "%d ", i);
fflush(stdout);
}
rcu_barrier();
printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
}
int main(int argc, char **argv)
{
bool long_run = false;
int opt;
unsigned int seed = time(NULL);
while ((opt = getopt(argc, argv, "ls:v")) != -1) {
if (opt == 'l')
long_run = true;
else if (opt == 's')
seed = strtoul(optarg, NULL, 0);
else if (opt == 'v')
test_verbose++;
}
printf("random seed %u\n", seed);
srand(seed);
printf("running tests\n");
rcu_register_thread();
radix_tree_init();
xarray_tests();
regression1_test();
regression2_test();
regression3_test();
regression4_test();
iteration_test(0, 10 + 90 * long_run);
iteration_test(7, 10 + 90 * long_run);
iteration_test2(10 + 90 * long_run);
single_thread_tests(long_run);
/* Free any remaining preallocated nodes */
radix_tree_cpu_dead(0);
benchmark();
rcu_barrier();
printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
nr_allocated, preempt_count);
rcu_unregister_thread();
printf("tests completed\n");
exit(0);
}
Codebase Browser
linux