xarray: Replace exceptional entries
Introduce xarray value entries and tagged pointers to replace radix
tree exceptional entries. This is a slight change in encoding to allow
the use of an extra bit (we can now store BITS_PER_LONG - 1 bits in a
value entry). It is also a change in emphasis; exceptional entries are
intimidating and different. As the comment explains, you can choose
to store values or pointers in the xarray and they are both first-class
citizens.
Signed-off-by: Matthew Wilcox <willy@infradead.org>
Reviewed-by: Josef Bacik <jbacik@fb.com>
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index f620c83..a5a4494 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -19,7 +19,7 @@
#include "test.h"
-#define DUMMY_PTR ((void *)0x12)
+#define DUMMY_PTR ((void *)0x10)
int item_idr_free(int id, void *p, void *data)
{
@@ -411,11 +411,11 @@ void ida_check_conv_user(void)
int id = ida_alloc(&ida, GFP_NOWAIT);
if (id == -ENOMEM) {
IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) !=
- BITS_PER_LONG - 2);
+ BITS_PER_XA_VALUE);
id = ida_alloc(&ida, GFP_KERNEL);
} else {
IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) ==
- BITS_PER_LONG - 2);
+ BITS_PER_XA_VALUE);
}
IDA_BUG_ON(&ida, id != i);
}
diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h
index 24f13d2..d1635a5 100644
--- a/tools/testing/radix-tree/linux/radix-tree.h
+++ b/tools/testing/radix-tree/linux/radix-tree.h
@@ -2,7 +2,6 @@
#ifndef _TEST_RADIX_TREE_H
#define _TEST_RADIX_TREE_H
-#include "generated/map-shift.h"
#include "../../../../include/linux/radix-tree.h"
extern int kmalloc_verbose;
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index 7bf4056..2b4f4db 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -39,12 +39,11 @@ static void __multiorder_tag_test(int index, int order)
/*
* Verify we get collisions for covered indices. We try and fail to
- * insert an exceptional entry so we don't leak memory via
+ * insert a value entry so we don't leak memory via
* item_insert_order().
*/
for_each_index(i, base, order) {
- err = __radix_tree_insert(&tree, i, order,
- (void *)(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY));
+ err = __radix_tree_insert(&tree, i, order, xa_mk_value(0xA0));
assert(err == -EEXIST);
}
@@ -380,8 +379,8 @@ static void multiorder_join1(unsigned long index,
}
/*
- * Check that the accounting of exceptional entries is handled correctly
- * by joining an exceptional entry to a normal pointer.
+ * Check that the accounting of value entries is handled correctly
+ * by joining a value entry to a normal pointer.
*/
static void multiorder_join2(unsigned order1, unsigned order2)
{
@@ -391,9 +390,9 @@ static void multiorder_join2(unsigned order1, unsigned order2)
void *item2;
item_insert_order(&tree, 0, order2);
- radix_tree_insert(&tree, 1 << order2, (void *)0x12UL);
+ radix_tree_insert(&tree, 1 << order2, xa_mk_value(5));
item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL);
- assert(item2 == (void *)0x12UL);
+ assert(item2 == xa_mk_value(5));
assert(node->exceptional == 1);
item2 = radix_tree_lookup(&tree, 0);
@@ -407,7 +406,7 @@ static void multiorder_join2(unsigned order1, unsigned order2)
}
/*
- * This test revealed an accounting bug for exceptional entries at one point.
+ * This test revealed an accounting bug for value entries at one point.
* Nodes were being freed back into the pool with an elevated exception count
* by radix_tree_join() and then radix_tree_split() was failing to zero the
* count of exceptional entries.
@@ -421,16 +420,16 @@ static void multiorder_join3(unsigned int order)
unsigned long i;
for (i = 0; i < (1 << order); i++) {
- radix_tree_insert(&tree, i, (void *)0x12UL);
+ radix_tree_insert(&tree, i, xa_mk_value(5));
}
- radix_tree_join(&tree, 0, order, (void *)0x16UL);
+ radix_tree_join(&tree, 0, order, xa_mk_value(7));
rcu_barrier();
radix_tree_split(&tree, 0, 0);
radix_tree_for_each_slot(slot, &tree, &iter, 0) {
- radix_tree_iter_replace(&tree, &iter, slot, (void *)0x12UL);
+ radix_tree_iter_replace(&tree, &iter, slot, xa_mk_value(5));
}
__radix_tree_lookup(&tree, 0, &node, NULL);
@@ -517,10 +516,10 @@ static void __multiorder_split2(int old_order, int new_order)
struct radix_tree_node *node;
void *item;
- __radix_tree_insert(&tree, 0, old_order, (void *)0x12);
+ __radix_tree_insert(&tree, 0, old_order, xa_mk_value(5));
item = __radix_tree_lookup(&tree, 0, &node, NULL);
- assert(item == (void *)0x12);
+ assert(item == xa_mk_value(5));
assert(node->exceptional > 0);
radix_tree_split(&tree, 0, new_order);
@@ -530,7 +529,7 @@ static void __multiorder_split2(int old_order, int new_order)
}
item = __radix_tree_lookup(&tree, 0, &node, NULL);
- assert(item != (void *)0x12);
+ assert(item != xa_mk_value(5));
assert(node->exceptional == 0);
item_kill_tree(&tree);
@@ -544,40 +543,40 @@ static void __multiorder_split3(int old_order, int new_order)
struct radix_tree_node *node;
void *item;
- __radix_tree_insert(&tree, 0, old_order, (void *)0x12);
+ __radix_tree_insert(&tree, 0, old_order, xa_mk_value(5));
item = __radix_tree_lookup(&tree, 0, &node, NULL);
- assert(item == (void *)0x12);
+ assert(item == xa_mk_value(5));
assert(node->exceptional > 0);
radix_tree_split(&tree, 0, new_order);
radix_tree_for_each_slot(slot, &tree, &iter, 0) {
- radix_tree_iter_replace(&tree, &iter, slot, (void *)0x16);
+ radix_tree_iter_replace(&tree, &iter, slot, xa_mk_value(7));
}
item = __radix_tree_lookup(&tree, 0, &node, NULL);
- assert(item == (void *)0x16);
+ assert(item == xa_mk_value(7));
assert(node->exceptional > 0);
item_kill_tree(&tree);
- __radix_tree_insert(&tree, 0, old_order, (void *)0x12);
+ __radix_tree_insert(&tree, 0, old_order, xa_mk_value(5));
item = __radix_tree_lookup(&tree, 0, &node, NULL);
- assert(item == (void *)0x12);
+ assert(item == xa_mk_value(5));
assert(node->exceptional > 0);
radix_tree_split(&tree, 0, new_order);
radix_tree_for_each_slot(slot, &tree, &iter, 0) {
if (iter.index == (1 << new_order))
radix_tree_iter_replace(&tree, &iter, slot,
- (void *)0x16);
+ xa_mk_value(7));
else
radix_tree_iter_replace(&tree, &iter, slot, NULL);
}
item = __radix_tree_lookup(&tree, 1 << new_order, &node, NULL);
- assert(item == (void *)0x16);
+ assert(item == xa_mk_value(7));
assert(node->count == node->exceptional);
do {
node = node->parent;
@@ -610,13 +609,13 @@ static void multiorder_account(void)
item_insert_order(&tree, 0, 5);
- __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12);
+ __radix_tree_insert(&tree, 1 << 5, 5, xa_mk_value(5));
__radix_tree_lookup(&tree, 0, &node, NULL);
assert(node->count == node->exceptional * 2);
radix_tree_delete(&tree, 1 << 5);
assert(node->exceptional == 0);
- __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12);
+ __radix_tree_insert(&tree, 1 << 5, 5, xa_mk_value(5));
__radix_tree_lookup(&tree, 1 << 5, &node, &slot);
assert(node->count == node->exceptional * 2);
__radix_tree_replace(&tree, node, slot, NULL, NULL);
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index def6015..62de66c 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -295,7 +295,7 @@ void item_kill_tree(struct radix_tree_root *root)
int nfound;
radix_tree_for_each_slot(slot, root, &iter, 0) {
- if (radix_tree_exceptional_entry(*slot))
+ if (xa_is_value(*slot))
radix_tree_delete(root, iter.index);
}