summaryrefslogtreecommitdiff
path: root/tools/testing/radix-tree/test.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2016-05-20 22:31:33 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2016-05-20 22:31:33 -0700
commit5469dc270cd44c451590d40c031e6a71c1f637e8 (patch)
tree5ca6330c2d754dbe82bfa75964a7f828f364e48f /tools/testing/radix-tree/test.c
parent2f37dd131c5d3a2eac21cd5baf80658b1b02a8ac (diff)
parentea9b50133ffebbd580cb5cd0aa222784d7a2fcb1 (diff)
downloadlinux-5469dc270cd44c451590d40c031e6a71c1f637e8.tar.gz
Merge branch 'akpm' (patches from Andrew)
Merge more updates from Andrew Morton: - the rest of MM - KASAN updates - procfs updates - exit, fork updates - printk updates - lib/ updates - radix-tree testsuite updates - checkpatch updates - kprobes updates - a few other misc bits * emailed patches from Andrew Morton <akpm@linux-foundation.org>: (162 commits) samples/kprobes: print out the symbol name for the hooks samples/kprobes: add a new module parameter kprobes: add the "tls" argument for j_do_fork init/main.c: simplify initcall_blacklisted() fs/efs/super.c: fix return value checkpatch: improve --git <commit-count> shortcut checkpatch: reduce number of `git log` calls with --git checkpatch: add support to check already applied git commits checkpatch: add --list-types to show message types to show or ignore checkpatch: advertise the --fix and --fix-inplace options more checkpatch: whine about ACCESS_ONCE checkpatch: add test for keywords not starting on tabstops checkpatch: improve CONSTANT_COMPARISON test for structure members checkpatch: add PREFER_IS_ENABLED test lib/GCD.c: use binary GCD algorithm instead of Euclidean radix-tree: free up the bottom bit of exceptional entries for reuse dax: move RADIX_DAX_ definitions to dax.c radix-tree: make radix_tree_descend() more useful radix-tree: introduce radix_tree_replace_clear_tags() radix-tree: tidy up __radix_tree_create() ...
Diffstat (limited to 'tools/testing/radix-tree/test.c')
-rw-r--r--tools/testing/radix-tree/test.c49
1 files changed, 34 insertions, 15 deletions
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index 2bebf34cdc27..a6e8099eaf4f 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -24,14 +24,21 @@ int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
return radix_tree_tag_get(root, index, tag);
}
-int __item_insert(struct radix_tree_root *root, struct item *item)
+int __item_insert(struct radix_tree_root *root, struct item *item,
+ unsigned order)
{
- return radix_tree_insert(root, item->index, item);
+ return __radix_tree_insert(root, item->index, order, item);
}
int item_insert(struct radix_tree_root *root, unsigned long index)
{
- return __item_insert(root, item_create(index));
+ return __item_insert(root, item_create(index), 0);
+}
+
+int item_insert_order(struct radix_tree_root *root, unsigned long index,
+ unsigned order)
+{
+ return __item_insert(root, item_create(index), order);
}
int item_delete(struct radix_tree_root *root, unsigned long index)
@@ -136,13 +143,13 @@ void item_full_scan(struct radix_tree_root *root, unsigned long start,
}
static int verify_node(struct radix_tree_node *slot, unsigned int tag,
- unsigned int height, int tagged)
+ int tagged)
{
int anyset = 0;
int i;
int j;
- slot = indirect_to_ptr(slot);
+ slot = entry_to_node(slot);
/* Verify consistency at this level */
for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
@@ -152,7 +159,8 @@ static int verify_node(struct radix_tree_node *slot, unsigned int tag,
}
}
if (tagged != anyset) {
- printf("tag: %u, height %u, tagged: %d, anyset: %d\n", tag, height, tagged, anyset);
+ printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",
+ tag, slot->shift, tagged, anyset);
for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
printf("tag %d: ", j);
for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
@@ -164,10 +172,10 @@ static int verify_node(struct radix_tree_node *slot, unsigned int tag,
assert(tagged == anyset);
/* Go for next level */
- if (height > 1) {
+ if (slot->shift > 0) {
for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
if (slot->slots[i])
- if (verify_node(slot->slots[i], tag, height - 1,
+ if (verify_node(slot->slots[i], tag,
!!test_bit(i, slot->tags[tag]))) {
printf("Failure at off %d\n", i);
for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
@@ -184,9 +192,10 @@ static int verify_node(struct radix_tree_node *slot, unsigned int tag,
void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
{
- if (!root->height)
+ struct radix_tree_node *node = root->rnode;
+ if (!radix_tree_is_internal_node(node))
return;
- verify_node(root->rnode, tag, root->height, !!root_tag_get(root, tag));
+ verify_node(node, tag, !!root_tag_get(root, tag));
}
void item_kill_tree(struct radix_tree_root *root)
@@ -211,9 +220,19 @@ void item_kill_tree(struct radix_tree_root *root)
void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
{
- assert(radix_tree_maxindex(root->height) >= maxindex);
- if (root->height > 1)
- assert(radix_tree_maxindex(root->height-1) < maxindex);
- else if (root->height == 1)
- assert(radix_tree_maxindex(root->height-1) <= maxindex);
+ unsigned shift;
+ struct radix_tree_node *node = root->rnode;
+ if (!radix_tree_is_internal_node(node)) {
+ assert(maxindex == 0);
+ return;
+ }
+
+ node = entry_to_node(node);
+ assert(maxindex <= node_maxindex(node));
+
+ shift = node->shift;
+ if (shift > 0)
+ assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));
+ else
+ assert(maxindex > 0);
}