diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 10:05:51 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 10:05:51 +0000 |
commit | 5d1646d90e1f2cceb9f0828f4b28318cd0ec7744 (patch) | |
tree | a94efe259b9009378be6d90eb30d2b019d95c194 /tools/testing/radix-tree/tag_check.c | |
parent | Initial commit. (diff) | |
download | linux-430c2fc249ea5c0536abd21c23382884005c9093.tar.xz linux-430c2fc249ea5c0536abd21c23382884005c9093.zip |
Adding upstream version 5.10.209.upstream/5.10.209upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'tools/testing/radix-tree/tag_check.c')
-rw-r--r-- | tools/testing/radix-tree/tag_check.c | 351 |
1 files changed, 351 insertions, 0 deletions
diff --git a/tools/testing/radix-tree/tag_check.c b/tools/testing/radix-tree/tag_check.c new file mode 100644 index 000000000..f898957b1 --- /dev/null +++ b/tools/testing/radix-tree/tag_check.c @@ -0,0 +1,351 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <string.h> + +#include <linux/slab.h> +#include <linux/radix-tree.h> + +#include "test.h" + + +static void +__simple_checks(struct radix_tree_root *tree, unsigned long index, int tag) +{ + unsigned long first = 0; + int ret; + + item_check_absent(tree, index); + assert(item_tag_get(tree, index, tag) == 0); + + item_insert(tree, index); + assert(item_tag_get(tree, index, tag) == 0); + item_tag_set(tree, index, tag); + ret = item_tag_get(tree, index, tag); + assert(ret != 0); + ret = tag_tagged_items(tree, first, ~0UL, 10, tag, !tag); + assert(ret == 1); + ret = item_tag_get(tree, index, !tag); + assert(ret != 0); + ret = item_delete(tree, index); + assert(ret != 0); + item_insert(tree, index); + ret = item_tag_get(tree, index, tag); + assert(ret == 0); + ret = item_delete(tree, index); + assert(ret != 0); + ret = item_delete(tree, index); + assert(ret == 0); +} + +void simple_checks(void) +{ + unsigned long index; + RADIX_TREE(tree, GFP_KERNEL); + + for (index = 0; index < 10000; index++) { + __simple_checks(&tree, index, 0); + __simple_checks(&tree, index, 1); + } + verify_tag_consistency(&tree, 0); + verify_tag_consistency(&tree, 1); + printv(2, "before item_kill_tree: %d allocated\n", nr_allocated); + item_kill_tree(&tree); + rcu_barrier(); + printv(2, "after item_kill_tree: %d allocated\n", nr_allocated); +} + +/* + * Check that tags propagate correctly when extending a tree. + */ +static void extend_checks(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + + item_insert(&tree, 43); + assert(item_tag_get(&tree, 43, 0) == 0); + item_tag_set(&tree, 43, 0); + assert(item_tag_get(&tree, 43, 0) == 1); + item_insert(&tree, 1000000); + assert(item_tag_get(&tree, 43, 0) == 1); + + item_insert(&tree, 0); + item_tag_set(&tree, 0, 0); + item_delete(&tree, 1000000); + assert(item_tag_get(&tree, 43, 0) != 0); + item_delete(&tree, 43); + assert(item_tag_get(&tree, 43, 0) == 0); /* crash */ + assert(item_tag_get(&tree, 0, 0) == 1); + + verify_tag_consistency(&tree, 0); + + item_kill_tree(&tree); +} + +/* + * Check that tags propagate correctly when contracting a tree. + */ +static void contract_checks(void) +{ + struct item *item; + int tmp; + RADIX_TREE(tree, GFP_KERNEL); + + tmp = 1<<RADIX_TREE_MAP_SHIFT; + item_insert(&tree, tmp); + item_insert(&tree, tmp+1); + item_tag_set(&tree, tmp, 0); + item_tag_set(&tree, tmp, 1); + item_tag_set(&tree, tmp+1, 0); + item_delete(&tree, tmp+1); + item_tag_clear(&tree, tmp, 1); + + assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1); + assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0); + + assert(item_tag_get(&tree, tmp, 0) == 1); + assert(item_tag_get(&tree, tmp, 1) == 0); + + verify_tag_consistency(&tree, 0); + item_kill_tree(&tree); +} + +/* + * Stupid tag thrasher + * + * Create a large linear array corresponding to the tree. Each element in + * the array is coherent with each node in the tree + */ + +enum { + NODE_ABSENT = 0, + NODE_PRESENT = 1, + NODE_TAGGED = 2, +}; + +#define THRASH_SIZE (1000 * 1000) +#define N 127 +#define BATCH 33 + +static void gang_check(struct radix_tree_root *tree, + char *thrash_state, int tag) +{ + struct item *items[BATCH]; + int nr_found; + unsigned long index = 0; + unsigned long last_index = 0; + + while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items, + index, BATCH, tag))) { + int i; + + for (i = 0; i < nr_found; i++) { + struct item *item = items[i]; + + while (last_index < item->index) { + assert(thrash_state[last_index] != NODE_TAGGED); + last_index++; + } + assert(thrash_state[last_index] == NODE_TAGGED); + last_index++; + } + index = items[nr_found - 1]->index + 1; + } +} + +static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag) +{ + int insert_chunk; + int delete_chunk; + int tag_chunk; + int untag_chunk; + int total_tagged = 0; + int total_present = 0; + + for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N) + for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N) + for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N) + for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) { + int i; + unsigned long index; + int nr_inserted = 0; + int nr_deleted = 0; + int nr_tagged = 0; + int nr_untagged = 0; + int actual_total_tagged; + int actual_total_present; + + for (i = 0; i < insert_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] != NODE_ABSENT) + continue; + item_check_absent(tree, index); + item_insert(tree, index); + assert(thrash_state[index] != NODE_PRESENT); + thrash_state[index] = NODE_PRESENT; + nr_inserted++; + total_present++; + } + + for (i = 0; i < delete_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] == NODE_ABSENT) + continue; + item_check_present(tree, index); + if (item_tag_get(tree, index, tag)) { + assert(thrash_state[index] == NODE_TAGGED); + total_tagged--; + } else { + assert(thrash_state[index] == NODE_PRESENT); + } + item_delete(tree, index); + assert(thrash_state[index] != NODE_ABSENT); + thrash_state[index] = NODE_ABSENT; + nr_deleted++; + total_present--; + } + + for (i = 0; i < tag_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] != NODE_PRESENT) { + if (item_lookup(tree, index)) + assert(item_tag_get(tree, index, tag)); + continue; + } + item_tag_set(tree, index, tag); + item_tag_set(tree, index, tag); + assert(thrash_state[index] != NODE_TAGGED); + thrash_state[index] = NODE_TAGGED; + nr_tagged++; + total_tagged++; + } + + for (i = 0; i < untag_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] != NODE_TAGGED) + continue; + item_check_present(tree, index); + assert(item_tag_get(tree, index, tag)); + item_tag_clear(tree, index, tag); + item_tag_clear(tree, index, tag); + assert(thrash_state[index] != NODE_PRESENT); + thrash_state[index] = NODE_PRESENT; + nr_untagged++; + total_tagged--; + } + + actual_total_tagged = 0; + actual_total_present = 0; + for (index = 0; index < THRASH_SIZE; index++) { + switch (thrash_state[index]) { + case NODE_ABSENT: + item_check_absent(tree, index); + break; + case NODE_PRESENT: + item_check_present(tree, index); + assert(!item_tag_get(tree, index, tag)); + actual_total_present++; + break; + case NODE_TAGGED: + item_check_present(tree, index); + assert(item_tag_get(tree, index, tag)); + actual_total_present++; + actual_total_tagged++; + break; + } + } + + gang_check(tree, thrash_state, tag); + + printv(2, "%d(%d) %d(%d) %d(%d) %d(%d) / " + "%d(%d) present, %d(%d) tagged\n", + insert_chunk, nr_inserted, + delete_chunk, nr_deleted, + tag_chunk, nr_tagged, + untag_chunk, nr_untagged, + total_present, actual_total_present, + total_tagged, actual_total_tagged); + } +} + +static void thrash_tags(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + char *thrash_state; + + thrash_state = malloc(THRASH_SIZE); + memset(thrash_state, 0, THRASH_SIZE); + + do_thrash(&tree, thrash_state, 0); + + verify_tag_consistency(&tree, 0); + item_kill_tree(&tree); + free(thrash_state); +} + +static void leak_check(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + + item_insert(&tree, 1000000); + item_delete(&tree, 1000000); + item_kill_tree(&tree); +} + +static void __leak_check(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); + item_insert(&tree, 1000000); + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); + item_delete(&tree, 1000000); + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); + item_kill_tree(&tree); + printv(2, "%d: nr_allocated=%d\n", __LINE__, nr_allocated); +} + +static void single_check(void) +{ + struct item *items[BATCH]; + RADIX_TREE(tree, GFP_KERNEL); + int ret; + unsigned long first = 0; + + item_insert(&tree, 0); + item_tag_set(&tree, 0, 0); + ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0); + assert(ret == 1); + ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0); + assert(ret == 0); + verify_tag_consistency(&tree, 0); + verify_tag_consistency(&tree, 1); + ret = tag_tagged_items(&tree, first, 10, 10, XA_MARK_0, XA_MARK_1); + assert(ret == 1); + ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 1); + assert(ret == 1); + item_tag_clear(&tree, 0, 0); + ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0); + assert(ret == 0); + item_kill_tree(&tree); +} + +void tag_check(void) +{ + single_check(); + extend_checks(); + contract_checks(); + rcu_barrier(); + printv(2, "after extend_checks: %d allocated\n", nr_allocated); + __leak_check(); + leak_check(); + rcu_barrier(); + printv(2, "after leak_check: %d allocated\n", nr_allocated); + simple_checks(); + rcu_barrier(); + printv(2, "after simple_checks: %d allocated\n", nr_allocated); + thrash_tags(); + rcu_barrier(); + printv(2, "after thrash_tags: %d allocated\n", nr_allocated); +} |