This patch series applies on top of the radix-fixes series I sent
recently.
It aims to improve the radix tree by making the code more understandable
and has the nice side-effect of shrinking the code size on i386-tinyconfig
by about 250 bytes. The 'height' concept is entirely gone from the code
by patch 7 of the series. We eliminate most of the tricky arithmetic
on index. This paves the way towards allowing different shift amounts
at different layers of the tree, something I know various people are
interested in.
It integrates two of the patches from Neil Brown which are pre-requisites
for locking exceptional entries.
We end up deleting almost a hundred lines of code from the kernel
(excluding the test-suite).
Matthew Wilcox (18):
drivers/hwspinlock: Use correct radix tree API
radix-tree: Miscellaneous fixes
radix-tree: Split node->path into offset and height
radix-tree: Replace node->height with node->shift
radix-tree: Remove a use of root->height from delete_node
radix tree test suite: Remove dependencies on height
radix-tree: Remove root->height
radix-tree: Rename INDIRECT_PTR to INTERNAL_NODE
radix-tree: Rename ptr_to_indirect() to node_to_entry()
radix-tree: Rename indirect_to_ptr() to entry_to_node()
radix-tree: Rename radix_tree_is_indirect_ptr()
radix-tree: Change naming conventions in radix_tree_shrink
radix-tree: Tidy up next_chunk
radix-tree: Tidy up range_tag_if_tagged
radix-tree: Tidy up __radix_tree_create()
radix-tree: Introduce radix_tree_replace_clear_tags()
radix-tree: Make radix_tree_descend() more useful
radix-tree: Free up the bottom bit of exceptional entries for reuse
NeilBrown (1):
dax: move RADIX_DAX_ definitions to dax.c
drivers/hwspinlock/hwspinlock_core.c | 2 +-
fs/dax.c | 9 +
include/linux/radix-tree.h | 94 +++---
lib/radix-tree.c | 577 +++++++++++++++-------------------
mm/filemap.c | 23 +-
tools/testing/radix-tree/multiorder.c | 99 +++---
tools/testing/radix-tree/test.c | 36 ++-
tools/testing/radix-tree/test.h | 4 +-
8 files changed, 385 insertions(+), 459 deletions(-)
--
2.8.0.rc3
radix_tree_is_indirect_ptr() is an internal API. The correct call to use
is radix_tree_deref_retry() which has the appropriate unlikely() annotation.
Fixes: c6400ba7e13a ("drivers/hwspinlock: fix race between radix tree insertion and lookup")
Signed-off-by: Matthew Wilcox <[email protected]>
---
drivers/hwspinlock/hwspinlock_core.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/drivers/hwspinlock/hwspinlock_core.c b/drivers/hwspinlock/hwspinlock_core.c
index d50c701..4074441 100644
--- a/drivers/hwspinlock/hwspinlock_core.c
+++ b/drivers/hwspinlock/hwspinlock_core.c
@@ -313,7 +313,7 @@ int of_hwspin_lock_get_id(struct device_node *np, int index)
hwlock = radix_tree_deref_slot(slot);
if (unlikely(!hwlock))
continue;
- if (radix_tree_is_indirect_ptr(hwlock)) {
+ if (radix_tree_deref_retry(hwlock)) {
slot = radix_tree_iter_retry(&iter);
continue;
}
--
2.8.0.rc3
We are guaranteed that pointers to radix_tree_nodes always have the
bottom two bits clear (because they come from a slab cache, and slab
caches have a minimum alignment of sizeof(void *)), so we can redefine
'radix_tree_is_internal_node' to only return true if the bottom two bits
have value '01'. This frees up one quarter of the potential values
for use by the user.
Idea from Neil Brown <[email protected]>
Signed-off-by: Matthew Wilcox <[email protected]>
---
include/linux/radix-tree.h | 38 +++++++++++++++++++++++---------------
1 file changed, 23 insertions(+), 15 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index c2f69e2..cb4b7e8 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -29,28 +29,37 @@
#include <linux/rcupdate.h>
/*
- * Entries in the radix tree have the low bit set if they refer to a
- * radix_tree_node. If the low bit is clear then the entry is user data.
- *
- * We also use the low bit to indicate that the slot will be freed in the
- * next RCU idle period, and users need to re-walk the tree to find the
- * new slot for the index that they were looking for. See the comment in
- * radix_tree_shrink() for details.
+ * The bottom two bits of the slot determine how the remaining bits in the
+ * slot are interpreted:
+ *
+ * 00 - data pointer
+ * 01 - internal entry
+ * 10 - exceptional entry
+ * 11 - locked exceptional entry
+ *
+ * The internal entry may be a pointer to the next level in the tree, a
+ * sibling entry, or an indicator that the entry in this slot has been moved
+ * to another location in the tree and the lookup should be restarted. While
+ * NULL fits the 'data pointer' pattern, it means that there is no entry in
+ * the tree for this index (no matter what level of the tree it is found at).
+ * This means that you cannot store NULL in the tree as a value for the index.
*/
-#define RADIX_TREE_INTERNAL_NODE 1
+#define RADIX_TREE_ENTRY_MASK 3UL
+#define RADIX_TREE_INTERNAL_NODE 1UL
/*
- * A common use of the radix tree is to store pointers to struct pages;
- * but shmem/tmpfs needs also to store swap entries in the same tree:
- * those are marked as exceptional entries to distinguish them.
+ * Most users of the radix tree store pointers but shmem/tmpfs stores swap
+ * entries in the same tree. They are marked as exceptional entries to
+ * distinguish them from pointers to struct page.
* EXCEPTIONAL_ENTRY tests the bit, EXCEPTIONAL_SHIFT shifts content past it.
*/
#define RADIX_TREE_EXCEPTIONAL_ENTRY 2
#define RADIX_TREE_EXCEPTIONAL_SHIFT 2
-static inline int radix_tree_is_internal_node(void *ptr)
+static inline bool radix_tree_is_internal_node(void *ptr)
{
- return (int)((unsigned long)ptr & RADIX_TREE_INTERNAL_NODE);
+ return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
+ RADIX_TREE_INTERNAL_NODE;
}
/*** radix-tree API starts here ***/
@@ -236,8 +245,7 @@ static inline int radix_tree_exceptional_entry(void *arg)
*/
static inline int radix_tree_exception(void *arg)
{
- return unlikely((unsigned long)arg &
- (RADIX_TREE_INTERNAL_NODE | RADIX_TREE_EXCEPTIONAL_ENTRY));
+ return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK);
}
/**
--
2.8.0.rc3
From: NeilBrown <[email protected]>
These don't belong in radix-tree.h any more than PAGECACHE_TAG_* do.
Let's try to maintain the idea that radix-tree simply implements an
abstract data type.
Signed-off-by: NeilBrown <[email protected]>
Reviewed-by: Ross Zwisler <[email protected]>
Reviewed-by: Jan Kara <[email protected]>
Signed-off-by: Matthew Wilcox <[email protected]>
---
fs/dax.c | 9 +++++++++
include/linux/radix-tree.h | 9 ---------
2 files changed, 9 insertions(+), 9 deletions(-)
diff --git a/fs/dax.c b/fs/dax.c
index 90322eb..735a608 100644
--- a/fs/dax.c
+++ b/fs/dax.c
@@ -32,6 +32,15 @@
#include <linux/pfn_t.h>
#include <linux/sizes.h>
+#define RADIX_DAX_MASK 0xf
+#define RADIX_DAX_SHIFT 4
+#define RADIX_DAX_PTE (0x4 | RADIX_TREE_EXCEPTIONAL_ENTRY)
+#define RADIX_DAX_PMD (0x8 | RADIX_TREE_EXCEPTIONAL_ENTRY)
+#define RADIX_DAX_TYPE(entry) ((unsigned long)entry & RADIX_DAX_MASK)
+#define RADIX_DAX_SECTOR(entry) (((unsigned long)entry >> RADIX_DAX_SHIFT))
+#define RADIX_DAX_ENTRY(sector, pmd) ((void *)((unsigned long)sector << \
+ RADIX_DAX_SHIFT | (pmd ? RADIX_DAX_PMD : RADIX_DAX_PTE)))
+
static long dax_map_atomic(struct block_device *bdev, struct blk_dax_ctl *dax)
{
struct request_queue *q = bdev->bd_queue;
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 11c8e7c..c2f69e2 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -48,15 +48,6 @@
#define RADIX_TREE_EXCEPTIONAL_ENTRY 2
#define RADIX_TREE_EXCEPTIONAL_SHIFT 2
-#define RADIX_DAX_MASK 0xf
-#define RADIX_DAX_SHIFT 4
-#define RADIX_DAX_PTE (0x4 | RADIX_TREE_EXCEPTIONAL_ENTRY)
-#define RADIX_DAX_PMD (0x8 | RADIX_TREE_EXCEPTIONAL_ENTRY)
-#define RADIX_DAX_TYPE(entry) ((unsigned long)entry & RADIX_DAX_MASK)
-#define RADIX_DAX_SECTOR(entry) (((unsigned long)entry >> RADIX_DAX_SHIFT))
-#define RADIX_DAX_ENTRY(sector, pmd) ((void *)((unsigned long)sector << \
- RADIX_DAX_SHIFT | (pmd ? RADIX_DAX_PMD : RADIX_DAX_PTE)))
-
static inline int radix_tree_is_internal_node(void *ptr)
{
return (int)((unsigned long)ptr & RADIX_TREE_INTERNAL_NODE);
--
2.8.0.rc3
In addition to replacing the entry, we also clear all associated tags.
This is really a one-off special for page_cache_tree_delete() which had
far too much detailed knowledge about how the radix tree works.
For efficiency, factor node_tag_clear() out of radix_tree_tag_clear()
It can be used by radix_tree_delete_item() as well as
radix_tree_replace_clear_tags().
Signed-off-by: Matthew Wilcox <[email protected]>
---
include/linux/radix-tree.h | 9 ++++--
lib/radix-tree.c | 76 ++++++++++++++++++++++++++++------------------
mm/filemap.c | 23 ++------------
3 files changed, 56 insertions(+), 52 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index bad6310..11c8e7c 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -281,9 +281,12 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
struct radix_tree_node *node);
void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
void *radix_tree_delete(struct radix_tree_root *, unsigned long);
-unsigned int
-radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
- unsigned long first_index, unsigned int max_items);
+struct radix_tree_node *radix_tree_replace_clear_tags(
+ struct radix_tree_root *root,
+ unsigned long index, void *entry);
+unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
+ void **results, unsigned long first_index,
+ unsigned int max_items);
unsigned int radix_tree_gang_lookup_slot(struct radix_tree_root *root,
void ***results, unsigned long *indices,
unsigned long first_index, unsigned int max_items);
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 9a57b70..4574848 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -740,6 +740,26 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
}
EXPORT_SYMBOL(radix_tree_tag_set);
+static void node_tag_clear(struct radix_tree_root *root,
+ struct radix_tree_node *node,
+ unsigned int tag, unsigned int offset)
+{
+ while (node) {
+ if (!tag_get(node, tag, offset))
+ return;
+ tag_clear(node, tag, offset);
+ if (any_tag_set(node, tag))
+ return;
+
+ offset = node->offset;
+ node = node->parent;
+ }
+
+ /* clear the root's tag bit */
+ if (root_tag_get(root, tag))
+ root_tag_clear(root, tag);
+}
+
/**
* radix_tree_tag_clear - clear a tag on a radix tree node
* @root: radix tree root
@@ -776,28 +796,9 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
offset = radix_tree_descend(parent, &node, offset);
}
- if (node == NULL)
- goto out;
+ if (node)
+ node_tag_clear(root, parent, tag, offset);
- index >>= shift;
-
- while (parent) {
- if (!tag_get(parent, tag, offset))
- goto out;
- tag_clear(parent, tag, offset);
- if (any_tag_set(parent, tag))
- goto out;
-
- index >>= RADIX_TREE_MAP_SHIFT;
- offset = index & RADIX_TREE_MAP_MASK;
- parent = parent->parent;
- }
-
- /* clear the root's tag bit */
- if (root_tag_get(root, tag))
- root_tag_clear(root, tag);
-
-out:
return node;
}
EXPORT_SYMBOL(radix_tree_tag_clear);
@@ -1526,14 +1527,9 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
offset = get_slot_offset(node, slot);
- /*
- * Clear all tags associated with the item to be deleted.
- * This way of doing it would be inefficient, but seldom is any set.
- */
- for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
- if (tag_get(node, tag, offset))
- radix_tree_tag_clear(root, index, tag);
- }
+ /* Clear all tags associated with the item to be deleted. */
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ node_tag_clear(root, node, tag, offset);
delete_sibling_entries(node, node_to_entry(slot), offset);
node->slots[offset] = NULL;
@@ -1560,6 +1556,28 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
}
EXPORT_SYMBOL(radix_tree_delete);
+struct radix_tree_node *radix_tree_replace_clear_tags(
+ struct radix_tree_root *root,
+ unsigned long index, void *entry)
+{
+ struct radix_tree_node *node;
+ void **slot;
+
+ __radix_tree_lookup(root, index, &node, &slot);
+
+ if (node) {
+ unsigned int tag, offset = get_slot_offset(node, slot);
+ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
+ node_tag_clear(root, node, tag, offset);
+ } else {
+ /* Clear root node tags */
+ root->gfp_mask &= __GFP_BITS_MASK;
+ }
+
+ radix_tree_replace_slot(slot, entry);
+ return node;
+}
+
/**
* radix_tree_tagged - test whether any items in the tree are tagged
* @root: radix tree root
diff --git a/mm/filemap.c b/mm/filemap.c
index a8c69c8..027ea96 100644
--- a/mm/filemap.c
+++ b/mm/filemap.c
@@ -114,14 +114,11 @@ static void page_cache_tree_delete(struct address_space *mapping,
struct page *page, void *shadow)
{
struct radix_tree_node *node;
- unsigned long index;
- unsigned int offset;
- unsigned int tag;
- void **slot;
VM_BUG_ON(!PageLocked(page));
- __radix_tree_lookup(&mapping->page_tree, page->index, &node, &slot);
+ node = radix_tree_replace_clear_tags(&mapping->page_tree, page->index,
+ shadow);
if (shadow) {
mapping->nrexceptional++;
@@ -135,23 +132,9 @@ static void page_cache_tree_delete(struct address_space *mapping,
}
mapping->nrpages--;
- if (!node) {
- /* Clear direct pointer tags in root node */
- mapping->page_tree.gfp_mask &= __GFP_BITS_MASK;
- radix_tree_replace_slot(slot, shadow);
+ if (!node)
return;
- }
-
- /* Clear tree tags for the removed page */
- index = page->index;
- offset = index & RADIX_TREE_MAP_MASK;
- for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
- if (test_bit(offset, node->tags[tag]))
- radix_tree_tag_clear(&mapping->page_tree, index, tag);
- }
- /* Delete page, swap shadow entry */
- radix_tree_replace_slot(slot, shadow);
workingset_node_pages_dec(node);
if (shadow)
workingset_node_shadows_inc(node);
--
2.8.0.rc3
If radix_tree_shrink returns whether it managed to shrink, then
__radix_tree_delete_node doesn't ned to query the tree to find out
whether it did any work or not.
Signed-off-by: Matthew Wilcox <[email protected]>
---
lib/radix-tree.c | 14 ++++++++------
1 file changed, 8 insertions(+), 6 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index e963823..f85c8f5 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1416,8 +1416,10 @@ unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
* radix_tree_shrink - shrink height of a radix tree to minimal
* @root radix tree root
*/
-static inline void radix_tree_shrink(struct radix_tree_root *root)
+static inline bool radix_tree_shrink(struct radix_tree_root *root)
{
+ bool shrunk = false;
+
/* try to shrink tree height */
while (root->height > 0) {
struct radix_tree_node *to_free = root->rnode;
@@ -1477,7 +1479,10 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
to_free->slots[0] = RADIX_TREE_RETRY;
radix_tree_node_free(to_free);
+ shrunk = true;
}
+
+ return shrunk;
}
/**
@@ -1500,11 +1505,8 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
struct radix_tree_node *parent;
if (node->count) {
- if (node == indirect_to_ptr(root->rnode)) {
- radix_tree_shrink(root);
- if (root->height == 0)
- deleted = true;
- }
+ if (node == indirect_to_ptr(root->rnode))
+ deleted |= radix_tree_shrink(root);
return deleted;
}
--
2.8.0.rc3
Use the more standard 'node' and 'child' instead of 'to_free' and 'slot'.
Signed-off-by: Matthew Wilcox <[email protected]>
---
lib/radix-tree.c | 30 +++++++++++++++---------------
1 file changed, 15 insertions(+), 15 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 145dcb1..094dfc0 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1396,37 +1396,37 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
bool shrunk = false;
for (;;) {
- struct radix_tree_node *to_free = root->rnode;
- struct radix_tree_node *slot;
+ struct radix_tree_node *node = root->rnode;
+ struct radix_tree_node *child;
- if (!radix_tree_is_internal_node(to_free))
+ if (!radix_tree_is_internal_node(node))
break;
- to_free = entry_to_node(to_free);
+ node = entry_to_node(node);
/*
* The candidate node has more than one child, or its child
* is not at the leftmost slot, or the child is a multiorder
* entry, we cannot shrink.
*/
- if (to_free->count != 1)
+ if (node->count != 1)
break;
- slot = to_free->slots[0];
- if (!slot)
+ child = node->slots[0];
+ if (!child)
break;
- if (!radix_tree_is_internal_node(slot) && to_free->shift)
+ if (!radix_tree_is_internal_node(child) && node->shift)
break;
- if (radix_tree_is_internal_node(slot))
- entry_to_node(slot)->parent = NULL;
+ if (radix_tree_is_internal_node(child))
+ entry_to_node(child)->parent = NULL;
/*
* We don't need rcu_assign_pointer(), since we are simply
* moving the node from one part of the tree to another: if it
* was safe to dereference the old pointer to it
- * (to_free->slots[0]), it will be safe to dereference the new
+ * (node->slots[0]), it will be safe to dereference the new
* one (root->rnode) as far as dependent read barriers go.
*/
- root->rnode = slot;
+ root->rnode = child;
/*
* We have a dilemma here. The node's slot[0] must not be
@@ -1446,10 +1446,10 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
* also results in a stale slot). So tag the slot as indirect
* to force callers to retry.
*/
- if (!radix_tree_is_internal_node(slot))
- to_free->slots[0] = RADIX_TREE_RETRY;
+ if (!radix_tree_is_internal_node(child))
+ node->slots[0] = RADIX_TREE_RETRY;
- radix_tree_node_free(to_free);
+ radix_tree_node_free(node);
shrunk = true;
}
--
2.8.0.rc3
Now that the shift amount is stored in the node, radix_tree_descend()
can calculate offset itself from index, which removes several lines of
code from each of the tree walkers.
Signed-off-by: Matthew Wilcox <[email protected]>
---
lib/radix-tree.c | 78 +++++++++++++++++++-------------------------------------
1 file changed, 26 insertions(+), 52 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 4574848..8ee2447 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -94,9 +94,10 @@ static inline unsigned long get_slot_offset(struct radix_tree_node *parent,
return slot - parent->slots;
}
-static unsigned radix_tree_descend(struct radix_tree_node *parent,
- struct radix_tree_node **nodep, unsigned offset)
+static unsigned int radix_tree_descend(struct radix_tree_node *parent,
+ struct radix_tree_node **nodep, unsigned long index)
{
+ unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
void **entry = rcu_dereference_raw(parent->slots[offset]);
#ifdef CONFIG_RADIX_TREE_MULTIORDER
@@ -536,8 +537,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
/* Go a level down */
node = entry_to_node(child);
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- offset = radix_tree_descend(node, &child, offset);
+ offset = radix_tree_descend(node, &child, index);
slot = &node->slots[offset];
}
@@ -625,13 +625,12 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
{
struct radix_tree_node *node, *parent;
unsigned long maxindex;
- unsigned int shift;
void **slot;
restart:
parent = NULL;
slot = (void **)&root->rnode;
- shift = radix_tree_load_root(root, &node, &maxindex);
+ radix_tree_load_root(root, &node, &maxindex);
if (index > maxindex)
return NULL;
@@ -641,9 +640,7 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
if (node == RADIX_TREE_RETRY)
goto restart;
parent = entry_to_node(node);
- shift -= RADIX_TREE_MAP_SHIFT;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- offset = radix_tree_descend(parent, &node, offset);
+ offset = radix_tree_descend(parent, &node, index);
slot = parent->slots + offset;
}
@@ -713,19 +710,15 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
{
struct radix_tree_node *node, *parent;
unsigned long maxindex;
- unsigned int shift;
- shift = radix_tree_load_root(root, &node, &maxindex);
+ radix_tree_load_root(root, &node, &maxindex);
BUG_ON(index > maxindex);
while (radix_tree_is_internal_node(node)) {
unsigned offset;
- shift -= RADIX_TREE_MAP_SHIFT;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-
parent = entry_to_node(node);
- offset = radix_tree_descend(parent, &node, offset);
+ offset = radix_tree_descend(parent, &node, index);
BUG_ON(!node);
if (!tag_get(parent, tag, offset))
@@ -779,21 +772,17 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
{
struct radix_tree_node *node, *parent;
unsigned long maxindex;
- unsigned int shift;
int uninitialized_var(offset);
- shift = radix_tree_load_root(root, &node, &maxindex);
+ radix_tree_load_root(root, &node, &maxindex);
if (index > maxindex)
return NULL;
parent = NULL;
while (radix_tree_is_internal_node(node)) {
- shift -= RADIX_TREE_MAP_SHIFT;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-
parent = entry_to_node(node);
- offset = radix_tree_descend(parent, &node, offset);
+ offset = radix_tree_descend(parent, &node, index);
}
if (node)
@@ -823,25 +812,21 @@ int radix_tree_tag_get(struct radix_tree_root *root,
{
struct radix_tree_node *node, *parent;
unsigned long maxindex;
- unsigned int shift;
if (!root_tag_get(root, tag))
return 0;
- shift = radix_tree_load_root(root, &node, &maxindex);
+ radix_tree_load_root(root, &node, &maxindex);
if (index > maxindex)
return 0;
if (node == NULL)
return 0;
while (radix_tree_is_internal_node(node)) {
- int offset;
-
- shift -= RADIX_TREE_MAP_SHIFT;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+ unsigned offset;
parent = entry_to_node(node);
- offset = radix_tree_descend(parent, &node, offset);
+ offset = radix_tree_descend(parent, &node, index);
if (!node)
return 0;
@@ -874,7 +859,7 @@ static inline void __set_iter_shift(struct radix_tree_iter *iter,
void **radix_tree_next_chunk(struct radix_tree_root *root,
struct radix_tree_iter *iter, unsigned flags)
{
- unsigned shift, tag = flags & RADIX_TREE_ITER_TAG_MASK;
+ unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
struct radix_tree_node *node, *child;
unsigned long index, offset, maxindex;
@@ -895,7 +880,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
return NULL;
restart:
- shift = radix_tree_load_root(root, &child, &maxindex);
+ radix_tree_load_root(root, &child, &maxindex);
if (index > maxindex)
return NULL;
if (!child)
@@ -912,9 +897,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
do {
node = entry_to_node(child);
- shift -= RADIX_TREE_MAP_SHIFT;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- offset = radix_tree_descend(node, &child, offset);
+ offset = radix_tree_descend(node, &child, index);
if ((flags & RADIX_TREE_ITER_TAGGED) ?
!tag_get(node, tag, offset) : !child) {
@@ -936,7 +919,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
break;
}
index &= ~node_maxindex(node);
- index += offset << shift;
+ index += offset << node->shift;
/* Overflow after ~0UL */
if (!index)
return NULL;
@@ -952,7 +935,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
/* Update the iterator state */
iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
iter->next_index = (index | node_maxindex(node)) + 1;
- __set_iter_shift(iter, shift);
+ __set_iter_shift(iter, node->shift);
/* Construct iter->tags bit-mask from node->tags[tag] array */
if (flags & RADIX_TREE_ITER_TAGGED) {
@@ -1010,10 +993,10 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
{
struct radix_tree_node *parent, *node, *child;
unsigned long maxindex;
- unsigned int shift = radix_tree_load_root(root, &child, &maxindex);
unsigned long tagged = 0;
unsigned long index = *first_indexp;
+ radix_tree_load_root(root, &child, &maxindex);
last_index = min(last_index, maxindex);
if (index > last_index)
return 0;
@@ -1030,11 +1013,9 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
}
node = entry_to_node(child);
- shift -= RADIX_TREE_MAP_SHIFT;
for (;;) {
- unsigned offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- offset = radix_tree_descend(node, &child, offset);
+ unsigned offset = radix_tree_descend(node, &child, index);
if (!child)
goto next;
if (!tag_get(node, iftag, offset))
@@ -1042,7 +1023,6 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
/* Sibling slots never have tags set on them */
if (radix_tree_is_internal_node(child)) {
node = entry_to_node(child);
- shift -= RADIX_TREE_MAP_SHIFT;
continue;
}
@@ -1063,12 +1043,12 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
tag_set(parent, settag, offset);
}
next:
- /* Go to next item at level determined by 'shift' */
- index = ((index >> shift) + 1) << shift;
+ /* Go to next entry in node */
+ index = ((index >> node->shift) + 1) << node->shift;
/* Overflow can happen when last_index is ~0UL... */
if (index > last_index || !index)
break;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+ offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
while (offset == 0) {
/*
* We've fully scanned this node. Go up. Because
@@ -1076,8 +1056,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
* we do below cannot wander astray.
*/
node = node->parent;
- shift += RADIX_TREE_MAP_SHIFT;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+ offset = (index >> node->shift) & RADIX_TREE_MAP_MASK;
}
if (is_sibling_entry(node, node->slots[offset]))
goto next;
@@ -1275,13 +1254,10 @@ struct locate_info {
static unsigned long __locate(struct radix_tree_node *slot, void *item,
unsigned long index, struct locate_info *info)
{
- unsigned int shift;
unsigned long base, i;
- shift = slot->shift + RADIX_TREE_MAP_SHIFT;
-
do {
- shift -= RADIX_TREE_MAP_SHIFT;
+ unsigned int shift = slot->shift;
base = index & ~((1UL << shift) - 1);
for (i = (index >> shift) & RADIX_TREE_MAP_MASK;
@@ -1305,9 +1281,7 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item,
slot = node;
break;
}
- if (i == RADIX_TREE_MAP_SIZE)
- break;
- } while (shift);
+ } while (i < RADIX_TREE_MAP_SIZE);
out:
if ((index == 0) && (i == RADIX_TREE_MAP_SIZE))
--
2.8.0.rc3
The only remaining references to root->height were in extend and shrink,
where it was updated. Now we can remove it entirely.
Signed-off-by: Matthew Wilcox <[email protected]>
Reviewed-by: Ross Zwisler <[email protected]>
---
include/linux/radix-tree.h | 3 --
lib/radix-tree.c | 106 +++++++++++++--------------------------------
2 files changed, 31 insertions(+), 78 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 0374582..c0d223c 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -110,13 +110,11 @@ struct radix_tree_node {
/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
struct radix_tree_root {
- unsigned int height;
gfp_t gfp_mask;
struct radix_tree_node __rcu *rnode;
};
#define RADIX_TREE_INIT(mask) { \
- .height = 0, \
.gfp_mask = (mask), \
.rnode = NULL, \
}
@@ -126,7 +124,6 @@ struct radix_tree_root {
#define INIT_RADIX_TREE(root, mask) \
do { \
- (root)->height = 0; \
(root)->gfp_mask = (mask); \
(root)->rnode = NULL; \
} while (0)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index f85c8f5..909527a 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -39,12 +39,6 @@
/*
- * The height_to_maxindex array needs to be one deeper than the maximum
- * path as height 0 holds only 1 entry.
- */
-static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
-
-/*
* Radix tree node cache.
*/
static struct kmem_cache *radix_tree_node_cachep;
@@ -218,8 +212,7 @@ radix_tree_find_next_bit(const unsigned long *addr,
}
#ifndef __KERNEL__
-static void dump_node(struct radix_tree_node *node,
- unsigned shift, unsigned long index)
+static void dump_node(struct radix_tree_node *node, unsigned long index)
{
unsigned long i;
@@ -229,8 +222,8 @@ static void dump_node(struct radix_tree_node *node,
node->shift, node->count, node->parent);
for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
- unsigned long first = index | (i << shift);
- unsigned long last = first | ((1UL << shift) - 1);
+ unsigned long first = index | (i << node->shift);
+ unsigned long last = first | ((1UL << node->shift) - 1);
void *entry = node->slots[i];
if (!entry)
continue;
@@ -243,8 +236,7 @@ static void dump_node(struct radix_tree_node *node,
pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
entry, i, first, last);
} else {
- dump_node(indirect_to_ptr(entry),
- shift - RADIX_TREE_MAP_SHIFT, first);
+ dump_node(indirect_to_ptr(entry), first);
}
}
}
@@ -252,13 +244,12 @@ static void dump_node(struct radix_tree_node *node,
/* For debug */
static void radix_tree_dump(struct radix_tree_root *root)
{
- pr_debug("radix root: %p height %d rnode %p tags %x\n",
- root, root->height, root->rnode,
+ pr_debug("radix root: %p rnode %p tags %x\n",
+ root, root->rnode,
root->gfp_mask >> __GFP_BITS_SHIFT);
if (!radix_tree_is_indirect_ptr(root->rnode))
return;
- dump_node(indirect_to_ptr(root->rnode),
- (root->height - 1) * RADIX_TREE_MAP_SHIFT, 0);
+ dump_node(indirect_to_ptr(root->rnode), 0);
}
#endif
@@ -411,14 +402,8 @@ int radix_tree_maybe_preload(gfp_t gfp_mask)
EXPORT_SYMBOL(radix_tree_maybe_preload);
/*
- * Return the maximum key which can be store into a
- * radix tree with height HEIGHT.
+ * The maximum index which can be stored in a radix tree
*/
-static inline unsigned long radix_tree_maxindex(unsigned int height)
-{
- return height_to_maxindex[height];
-}
-
static inline unsigned long shift_maxindex(unsigned int shift)
{
return (RADIX_TREE_MAP_SIZE << shift) - 1;
@@ -450,24 +435,22 @@ static unsigned radix_tree_load_root(struct radix_tree_root *root,
* Extend a radix tree so it can store key @index.
*/
static int radix_tree_extend(struct radix_tree_root *root,
- unsigned long index)
+ unsigned long index, unsigned int shift)
{
struct radix_tree_node *slot;
- unsigned int height;
+ unsigned int maxshift;
int tag;
- /* Figure out what the height should be. */
- height = root->height + 1;
- while (index > radix_tree_maxindex(height))
- height++;
+ /* Figure out what the shift should be. */
+ maxshift = shift;
+ while (index > shift_maxindex(maxshift))
+ maxshift += RADIX_TREE_MAP_SHIFT;
- if (root->rnode == NULL) {
- root->height = height;
+ slot = root->rnode;
+ if (!slot)
goto out;
- }
do {
- unsigned int newheight;
struct radix_tree_node *node = radix_tree_node_alloc(root);
if (!node)
@@ -479,14 +462,11 @@ static int radix_tree_extend(struct radix_tree_root *root,
tag_set(node, tag, 0);
}
- /* Increase the height. */
- newheight = root->height;
- BUG_ON(newheight > BITS_PER_LONG);
- node->shift = newheight * RADIX_TREE_MAP_SHIFT;
+ BUG_ON(shift > BITS_PER_LONG);
+ node->shift = shift;
node->offset = 0;
node->count = 1;
node->parent = NULL;
- slot = root->rnode;
if (radix_tree_is_indirect_ptr(slot)) {
slot = indirect_to_ptr(slot);
slot->parent = node;
@@ -495,10 +475,11 @@ static int radix_tree_extend(struct radix_tree_root *root,
node->slots[0] = slot;
node = ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
- root->height = ++newheight;
- } while (height > root->height);
+ shift += RADIX_TREE_MAP_SHIFT;
+ slot = node;
+ } while (shift <= maxshift);
out:
- return height * RADIX_TREE_MAP_SHIFT;
+ return maxshift + RADIX_TREE_MAP_SHIFT;
}
/**
@@ -531,15 +512,13 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
/* Make sure the tree is high enough. */
if (max > maxindex) {
- int error = radix_tree_extend(root, max);
+ int error = radix_tree_extend(root, max, shift);
if (error < 0)
return error;
shift = error;
slot = root->rnode;
- if (order == shift) {
+ if (order == shift)
shift += RADIX_TREE_MAP_SHIFT;
- root->height++;
- }
}
offset = 0; /* uninitialised var warning */
@@ -1413,32 +1392,32 @@ unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
#endif /* CONFIG_SHMEM && CONFIG_SWAP */
/**
- * radix_tree_shrink - shrink height of a radix tree to minimal
+ * radix_tree_shrink - shrink radix tree to minimum height
* @root radix tree root
*/
static inline bool radix_tree_shrink(struct radix_tree_root *root)
{
bool shrunk = false;
- /* try to shrink tree height */
- while (root->height > 0) {
+ for (;;) {
struct radix_tree_node *to_free = root->rnode;
struct radix_tree_node *slot;
- BUG_ON(!radix_tree_is_indirect_ptr(to_free));
+ if (!radix_tree_is_indirect_ptr(to_free))
+ break;
to_free = indirect_to_ptr(to_free);
/*
* The candidate node has more than one child, or its child
- * is not at the leftmost slot, or it is a multiorder entry,
- * we cannot shrink.
+ * is not at the leftmost slot, or the child is a multiorder
+ * entry, we cannot shrink.
*/
if (to_free->count != 1)
break;
slot = to_free->slots[0];
if (!slot)
break;
- if (!radix_tree_is_indirect_ptr(slot) && (root->height > 1))
+ if (!radix_tree_is_indirect_ptr(slot) && to_free->shift)
break;
if (radix_tree_is_indirect_ptr(slot)) {
@@ -1455,7 +1434,6 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
* one (root->rnode) as far as dependent read barriers go.
*/
root->rnode = slot;
- root->height--;
/*
* We have a dilemma here. The node's slot[0] must not be
@@ -1516,7 +1494,6 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
parent->count--;
} else {
root_tag_clear_all(root);
- root->height = 0;
root->rnode = NULL;
}
@@ -1632,26 +1609,6 @@ radix_tree_node_ctor(void *arg)
INIT_LIST_HEAD(&node->private_list);
}
-static __init unsigned long __maxindex(unsigned int height)
-{
- unsigned int width = height * RADIX_TREE_MAP_SHIFT;
- int shift = RADIX_TREE_INDEX_BITS - width;
-
- if (shift < 0)
- return ~0UL;
- if (shift >= BITS_PER_LONG)
- return 0UL;
- return ~0UL >> shift;
-}
-
-static __init void radix_tree_init_maxindex(void)
-{
- unsigned int i;
-
- for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
- height_to_maxindex[i] = __maxindex(i);
-}
-
static int radix_tree_callback(struct notifier_block *nfb,
unsigned long action, void *hcpu)
{
@@ -1678,6 +1635,5 @@ void __init radix_tree_init(void)
sizeof(struct radix_tree_node), 0,
SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
radix_tree_node_ctor);
- radix_tree_init_maxindex();
hotcpu_notifier(radix_tree_callback, 0);
}
--
2.8.0.rc3
Neither piece of information we're storing in node->path can be larger
than 64, so store each in its own unsigned char instead of shifting
and masking to store them both in an unsigned int.
Signed-off-by: Matthew Wilcox <[email protected]>
Reviewed-by: Ross Zwisler <[email protected]>
---
include/linux/radix-tree.h | 7 ++-----
lib/radix-tree.c | 38 +++++++++++++++++---------------------
2 files changed, 19 insertions(+), 26 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 8558d52..2d2ad9d 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -84,16 +84,13 @@ static inline int radix_tree_is_indirect_ptr(void *ptr)
#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
RADIX_TREE_MAP_SHIFT))
-/* Height component in node->path */
-#define RADIX_TREE_HEIGHT_SHIFT (RADIX_TREE_MAX_PATH + 1)
-#define RADIX_TREE_HEIGHT_MASK ((1UL << RADIX_TREE_HEIGHT_SHIFT) - 1)
-
/* Internally used bits of node->count */
#define RADIX_TREE_COUNT_SHIFT (RADIX_TREE_MAP_SHIFT + 1)
#define RADIX_TREE_COUNT_MASK ((1UL << RADIX_TREE_COUNT_SHIFT) - 1)
struct radix_tree_node {
- unsigned int path; /* Offset in parent & height from the bottom */
+ unsigned char height; /* From the bottom */
+ unsigned char offset; /* Slot offset in parent */
unsigned int count;
union {
struct {
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 746a240..d42c5b5 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -218,15 +218,15 @@ radix_tree_find_next_bit(const unsigned long *addr,
}
#ifndef __KERNEL__
-static void dump_node(struct radix_tree_node *node, unsigned offset,
+static void dump_node(struct radix_tree_node *node,
unsigned shift, unsigned long index)
{
unsigned long i;
- pr_debug("radix node: %p offset %d tags %lx %lx %lx path %x count %d parent %p\n",
- node, offset,
+ pr_debug("radix node: %p offset %d tags %lx %lx %lx height %d count %d parent %p\n",
+ node, node->offset,
node->tags[0][0], node->tags[1][0], node->tags[2][0],
- node->path, node->count, node->parent);
+ node->height, node->count, node->parent);
for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
unsigned long first = index | (i << shift);
@@ -243,7 +243,7 @@ static void dump_node(struct radix_tree_node *node, unsigned offset,
pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
entry, i, first, last);
} else {
- dump_node(indirect_to_ptr(entry), i,
+ dump_node(indirect_to_ptr(entry),
shift - RADIX_TREE_MAP_SHIFT, first);
}
}
@@ -257,7 +257,7 @@ static void radix_tree_dump(struct radix_tree_root *root)
root->gfp_mask >> __GFP_BITS_SHIFT);
if (!radix_tree_is_indirect_ptr(root->rnode))
return;
- dump_node(indirect_to_ptr(root->rnode), 0,
+ dump_node(indirect_to_ptr(root->rnode),
(root->height - 1) * RADIX_TREE_MAP_SHIFT, 0);
}
#endif
@@ -421,7 +421,7 @@ static inline unsigned long radix_tree_maxindex(unsigned int height)
static inline unsigned long node_maxindex(struct radix_tree_node *node)
{
- return radix_tree_maxindex(node->path & RADIX_TREE_HEIGHT_MASK);
+ return radix_tree_maxindex(node->height);
}
static unsigned radix_tree_load_root(struct radix_tree_root *root,
@@ -434,8 +434,7 @@ static unsigned radix_tree_load_root(struct radix_tree_root *root,
if (likely(radix_tree_is_indirect_ptr(node))) {
node = indirect_to_ptr(node);
*maxindex = node_maxindex(node);
- return (node->path & RADIX_TREE_HEIGHT_MASK) *
- RADIX_TREE_MAP_SHIFT;
+ return node->height * RADIX_TREE_MAP_SHIFT;
}
*maxindex = 0;
@@ -476,9 +475,10 @@ static int radix_tree_extend(struct radix_tree_root *root,
}
/* Increase the height. */
- newheight = root->height+1;
- BUG_ON(newheight & ~RADIX_TREE_HEIGHT_MASK);
- node->path = newheight;
+ newheight = root->height + 1;
+ BUG_ON(newheight > BITS_PER_LONG);
+ node->height = newheight;
+ node->offset = 0;
node->count = 1;
node->parent = NULL;
slot = root->rnode;
@@ -546,13 +546,13 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
slot = radix_tree_node_alloc(root);
if (!slot)
return -ENOMEM;
- slot->path = height;
+ slot->height = height;
+ slot->offset = offset;
slot->parent = node;
if (node) {
rcu_assign_pointer(node->slots[offset],
ptr_to_indirect(slot));
node->count++;
- slot->path |= offset << RADIX_TREE_HEIGHT_SHIFT;
} else
rcu_assign_pointer(root->rnode,
ptr_to_indirect(slot));
@@ -1319,11 +1319,10 @@ struct locate_info {
static unsigned long __locate(struct radix_tree_node *slot, void *item,
unsigned long index, struct locate_info *info)
{
- unsigned int shift, height;
+ unsigned int shift;
unsigned long base, i;
- height = slot->path & RADIX_TREE_HEIGHT_MASK;
- shift = height * RADIX_TREE_MAP_SHIFT;
+ shift = slot->height * RADIX_TREE_MAP_SHIFT;
do {
shift -= RADIX_TREE_MAP_SHIFT;
@@ -1509,10 +1508,7 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
parent = node->parent;
if (parent) {
- unsigned int offset;
-
- offset = node->path >> RADIX_TREE_HEIGHT_SHIFT;
- parent->slots[offset] = NULL;
+ parent->slots[node->offset] = NULL;
parent->count--;
} else {
root_tag_clear_all(root);
--
2.8.0.rc3
1. Rename the existing variable 'slot' to 'child'.
2. Introduce a new variable called 'slot' which is the address of the
slot we're dealing with. This lets us simplify the tree insertion,
and removes the recalculation of 'slot' at the end of the function.
3. Using 'slot' in the sibling pointer insertion part makes the code
more readable.
Signed-off-by: Matthew Wilcox <[email protected]>
---
lib/radix-tree.c | 48 +++++++++++++++++++++++-------------------------
1 file changed, 23 insertions(+), 25 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 412dc35..9a57b70 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -499,12 +499,13 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
unsigned order, struct radix_tree_node **nodep,
void ***slotp)
{
- struct radix_tree_node *node = NULL, *slot;
+ struct radix_tree_node *node = NULL, *child;
+ void **slot = (void **)&root->rnode;
unsigned long maxindex;
- unsigned int shift, offset;
+ unsigned int shift, offset = 0;
unsigned long max = index | ((1UL << order) - 1);
- shift = radix_tree_load_root(root, &slot, &maxindex);
+ shift = radix_tree_load_root(root, &child, &maxindex);
/* Make sure the tree is high enough. */
if (max > maxindex) {
@@ -512,51 +513,48 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
if (error < 0)
return error;
shift = error;
- slot = root->rnode;
+ child = root->rnode;
if (order == shift)
shift += RADIX_TREE_MAP_SHIFT;
}
- offset = 0; /* uninitialised var warning */
while (shift > order) {
shift -= RADIX_TREE_MAP_SHIFT;
- if (slot == NULL) {
+ if (child == NULL) {
/* Have to add a child node. */
- slot = radix_tree_node_alloc(root);
- if (!slot)
+ child = radix_tree_node_alloc(root);
+ if (!child)
return -ENOMEM;
- slot->shift = shift;
- slot->offset = offset;
- slot->parent = node;
- if (node) {
- rcu_assign_pointer(node->slots[offset],
- node_to_entry(slot));
+ child->shift = shift;
+ child->offset = offset;
+ child->parent = node;
+ rcu_assign_pointer(*slot, node_to_entry(child));
+ if (node)
node->count++;
- } else
- rcu_assign_pointer(root->rnode,
- node_to_entry(slot));
- } else if (!radix_tree_is_internal_node(slot))
+ } else if (!radix_tree_is_internal_node(child))
break;
/* Go a level down */
- node = entry_to_node(slot);
+ node = entry_to_node(child);
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- offset = radix_tree_descend(node, &slot, offset);
+ offset = radix_tree_descend(node, &child, offset);
+ slot = &node->slots[offset];
}
#ifdef CONFIG_RADIX_TREE_MULTIORDER
/* Insert pointers to the canonical entry */
if (order > shift) {
- int i, n = 1 << (order - shift);
+ unsigned i, n = 1 << (order - shift);
offset = offset & ~(n - 1);
- slot = node_to_entry(&node->slots[offset]);
+ slot = &node->slots[offset];
+ child = node_to_entry(slot);
for (i = 0; i < n; i++) {
- if (node->slots[offset + i])
+ if (slot[i])
return -EEXIST;
}
for (i = 1; i < n; i++) {
- rcu_assign_pointer(node->slots[offset + i], slot);
+ rcu_assign_pointer(slot[i], child);
node->count++;
}
}
@@ -565,7 +563,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
if (nodep)
*nodep = node;
if (slotp)
- *slotp = node ? node->slots + offset : (void **)&root->rnode;
+ *slotp = slot;
return 0;
}
--
2.8.0.rc3
Convert radix_tree_range_tag_if_tagged to name the nodes parent, node and
child instead of node & slot.
Use parent->offset instead of playing games with 'upindex'.
Signed-off-by: Matthew Wilcox <[email protected]>
---
lib/radix-tree.c | 39 +++++++++++++++++----------------------
1 file changed, 17 insertions(+), 22 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index fab4485..412dc35 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -1009,9 +1009,9 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
unsigned long nr_to_tag,
unsigned int iftag, unsigned int settag)
{
- struct radix_tree_node *slot, *node = NULL;
+ struct radix_tree_node *parent, *node, *child;
unsigned long maxindex;
- unsigned int shift = radix_tree_load_root(root, &slot, &maxindex);
+ unsigned int shift = radix_tree_load_root(root, &child, &maxindex);
unsigned long tagged = 0;
unsigned long index = *first_indexp;
@@ -1024,28 +1024,25 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
*first_indexp = last_index + 1;
return 0;
}
- if (!radix_tree_is_internal_node(slot)) {
+ if (!radix_tree_is_internal_node(child)) {
*first_indexp = last_index + 1;
root_tag_set(root, settag);
return 1;
}
- node = entry_to_node(slot);
+ node = entry_to_node(child);
shift -= RADIX_TREE_MAP_SHIFT;
for (;;) {
- unsigned long upindex;
- unsigned offset;
-
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- offset = radix_tree_descend(node, &slot, offset);
- if (!slot)
+ unsigned offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+ offset = radix_tree_descend(node, &child, offset);
+ if (!child)
goto next;
if (!tag_get(node, iftag, offset))
goto next;
/* Sibling slots never have tags set on them */
- if (radix_tree_is_internal_node(slot)) {
- node = entry_to_node(slot);
+ if (radix_tree_is_internal_node(child)) {
+ node = entry_to_node(child);
shift -= RADIX_TREE_MAP_SHIFT;
continue;
}
@@ -1054,20 +1051,18 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
tagged++;
tag_set(node, settag, offset);
- slot = node->parent;
/* walk back up the path tagging interior nodes */
- upindex = index >> shift;
- while (slot) {
- upindex >>= RADIX_TREE_MAP_SHIFT;
- offset = upindex & RADIX_TREE_MAP_MASK;
-
+ parent = node;
+ for (;;) {
+ offset = parent->offset;
+ parent = parent->parent;
+ if (!parent)
+ break;
/* stop if we find a node with the tag already set */
- if (tag_get(slot, settag, offset))
+ if (tag_get(parent, settag, offset))
break;
- tag_set(slot, settag, offset);
- slot = slot->parent;
+ tag_set(parent, settag, offset);
}
-
next:
/* Go to next item at level determined by 'shift' */
index = ((index >> shift) + 1) << shift;
--
2.8.0.rc3
As with indirect_to_ptr(), ptr_to_indirect() and RADIX_TREE_INDIRECT_PTR,
change radix_tree_is_indirect_ptr() to radix_tree_is_internal_node().
Signed-off-by: Matthew Wilcox <[email protected]>
---
include/linux/radix-tree.h | 10 ++++-----
lib/radix-tree.c | 48 ++++++++++++++++++++---------------------
tools/testing/radix-tree/test.c | 4 ++--
3 files changed, 31 insertions(+), 31 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index b94aa19..bad6310 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -57,7 +57,7 @@
#define RADIX_DAX_ENTRY(sector, pmd) ((void *)((unsigned long)sector << \
RADIX_DAX_SHIFT | (pmd ? RADIX_DAX_PMD : RADIX_DAX_PTE)))
-static inline int radix_tree_is_indirect_ptr(void *ptr)
+static inline int radix_tree_is_internal_node(void *ptr)
{
return (int)((unsigned long)ptr & RADIX_TREE_INTERNAL_NODE);
}
@@ -224,7 +224,7 @@ static inline void *radix_tree_deref_slot_protected(void **pslot,
*/
static inline int radix_tree_deref_retry(void *arg)
{
- return unlikely(radix_tree_is_indirect_ptr(arg));
+ return unlikely(radix_tree_is_internal_node(arg));
}
/**
@@ -259,7 +259,7 @@ static inline int radix_tree_exception(void *arg)
*/
static inline void radix_tree_replace_slot(void **pslot, void *item)
{
- BUG_ON(radix_tree_is_indirect_ptr(item));
+ BUG_ON(radix_tree_is_internal_node(item));
rcu_assign_pointer(*pslot, item);
}
@@ -468,7 +468,7 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
if (unlikely(!iter->tags))
return NULL;
while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_indirect_ptr(slot[1])) {
+ radix_tree_is_internal_node(slot[1])) {
if (entry_to_node(slot[1]) == canon) {
iter->tags >>= 1;
iter->index = __radix_tree_iter_add(iter, 1);
@@ -498,7 +498,7 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
iter->index = __radix_tree_iter_add(iter, 1);
if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
- radix_tree_is_indirect_ptr(*slot)) {
+ radix_tree_is_internal_node(*slot)) {
if (entry_to_node(*slot) == canon)
continue;
iter->next_index = iter->index;
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 675e85f..145dcb1 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -100,7 +100,7 @@ static unsigned radix_tree_descend(struct radix_tree_node *parent,
void **entry = rcu_dereference_raw(parent->slots[offset]);
#ifdef CONFIG_RADIX_TREE_MULTIORDER
- if (radix_tree_is_indirect_ptr(entry)) {
+ if (radix_tree_is_internal_node(entry)) {
unsigned long siboff = get_slot_offset(parent, entry);
if (siboff < RADIX_TREE_MAP_SIZE) {
offset = siboff;
@@ -232,7 +232,7 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
entry, i,
*(void **)entry_to_node(entry),
first, last);
- } else if (!radix_tree_is_indirect_ptr(entry)) {
+ } else if (!radix_tree_is_internal_node(entry)) {
pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
entry, i, first, last);
} else {
@@ -247,7 +247,7 @@ static void radix_tree_dump(struct radix_tree_root *root)
pr_debug("radix root: %p rnode %p tags %x\n",
root, root->rnode,
root->gfp_mask >> __GFP_BITS_SHIFT);
- if (!radix_tree_is_indirect_ptr(root->rnode))
+ if (!radix_tree_is_internal_node(root->rnode))
return;
dump_node(entry_to_node(root->rnode), 0);
}
@@ -302,7 +302,7 @@ radix_tree_node_alloc(struct radix_tree_root *root)
ret = kmem_cache_alloc(radix_tree_node_cachep,
gfp_mask | __GFP_ACCOUNT);
out:
- BUG_ON(radix_tree_is_indirect_ptr(ret));
+ BUG_ON(radix_tree_is_internal_node(ret));
return ret;
}
@@ -421,7 +421,7 @@ static unsigned radix_tree_load_root(struct radix_tree_root *root,
*nodep = node;
- if (likely(radix_tree_is_indirect_ptr(node))) {
+ if (likely(radix_tree_is_internal_node(node))) {
node = entry_to_node(node);
*maxindex = node_maxindex(node);
return node->shift + RADIX_TREE_MAP_SHIFT;
@@ -467,7 +467,7 @@ static int radix_tree_extend(struct radix_tree_root *root,
node->offset = 0;
node->count = 1;
node->parent = NULL;
- if (radix_tree_is_indirect_ptr(slot))
+ if (radix_tree_is_internal_node(slot))
entry_to_node(slot)->parent = node;
node->slots[0] = slot;
slot = node_to_entry(node);
@@ -535,7 +535,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
} else
rcu_assign_pointer(root->rnode,
node_to_entry(slot));
- } else if (!radix_tree_is_indirect_ptr(slot))
+ } else if (!radix_tree_is_internal_node(slot))
break;
/* Go a level down */
@@ -585,7 +585,7 @@ int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
void **slot;
int error;
- BUG_ON(radix_tree_is_indirect_ptr(item));
+ BUG_ON(radix_tree_is_internal_node(item));
error = __radix_tree_create(root, index, order, &node, &slot);
if (error)
@@ -637,7 +637,7 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
if (index > maxindex)
return NULL;
- while (radix_tree_is_indirect_ptr(node)) {
+ while (radix_tree_is_internal_node(node)) {
unsigned offset;
if (node == RADIX_TREE_RETRY)
@@ -720,7 +720,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
shift = radix_tree_load_root(root, &node, &maxindex);
BUG_ON(index > maxindex);
- while (radix_tree_is_indirect_ptr(node)) {
+ while (radix_tree_is_internal_node(node)) {
unsigned offset;
shift -= RADIX_TREE_MAP_SHIFT;
@@ -770,7 +770,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
parent = NULL;
- while (radix_tree_is_indirect_ptr(node)) {
+ while (radix_tree_is_internal_node(node)) {
shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
@@ -835,7 +835,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
if (node == NULL)
return 0;
- while (radix_tree_is_indirect_ptr(node)) {
+ while (radix_tree_is_internal_node(node)) {
int offset;
shift -= RADIX_TREE_MAP_SHIFT;
@@ -900,7 +900,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
if (index > maxindex)
return NULL;
- if (radix_tree_is_indirect_ptr(rnode)) {
+ if (radix_tree_is_internal_node(rnode)) {
rnode = entry_to_node(rnode);
} else if (rnode) {
/* Single-slot tree */
@@ -957,7 +957,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
if ((slot == NULL) || (slot == RADIX_TREE_RETRY))
goto restart;
- if (!radix_tree_is_indirect_ptr(slot))
+ if (!radix_tree_is_internal_node(slot))
break;
node = entry_to_node(slot);
@@ -1039,7 +1039,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
*first_indexp = last_index + 1;
return 0;
}
- if (!radix_tree_is_indirect_ptr(slot)) {
+ if (!radix_tree_is_internal_node(slot)) {
*first_indexp = last_index + 1;
root_tag_set(root, settag);
return 1;
@@ -1059,7 +1059,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
if (!tag_get(node, iftag, offset))
goto next;
/* Sibling slots never have tags set on them */
- if (radix_tree_is_indirect_ptr(slot)) {
+ if (radix_tree_is_internal_node(slot)) {
node = entry_to_node(slot);
shift -= RADIX_TREE_MAP_SHIFT;
continue;
@@ -1152,7 +1152,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
results[ret] = rcu_dereference_raw(*slot);
if (!results[ret])
continue;
- if (radix_tree_is_indirect_ptr(results[ret])) {
+ if (radix_tree_is_internal_node(results[ret])) {
slot = radix_tree_iter_retry(&iter);
continue;
}
@@ -1235,7 +1235,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
results[ret] = rcu_dereference_raw(*slot);
if (!results[ret])
continue;
- if (radix_tree_is_indirect_ptr(results[ret])) {
+ if (radix_tree_is_internal_node(results[ret])) {
slot = radix_tree_iter_retry(&iter);
continue;
}
@@ -1312,7 +1312,7 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item,
rcu_dereference_raw(slot->slots[i]);
if (node == RADIX_TREE_RETRY)
goto out;
- if (!radix_tree_is_indirect_ptr(node)) {
+ if (!radix_tree_is_internal_node(node)) {
if (node == item) {
info->found_index = index;
info->stop = true;
@@ -1358,7 +1358,7 @@ unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
do {
rcu_read_lock();
node = rcu_dereference_raw(root->rnode);
- if (!radix_tree_is_indirect_ptr(node)) {
+ if (!radix_tree_is_internal_node(node)) {
rcu_read_unlock();
if (node == item)
info.found_index = 0;
@@ -1399,7 +1399,7 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
struct radix_tree_node *to_free = root->rnode;
struct radix_tree_node *slot;
- if (!radix_tree_is_indirect_ptr(to_free))
+ if (!radix_tree_is_internal_node(to_free))
break;
to_free = entry_to_node(to_free);
@@ -1413,10 +1413,10 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
slot = to_free->slots[0];
if (!slot)
break;
- if (!radix_tree_is_indirect_ptr(slot) && to_free->shift)
+ if (!radix_tree_is_internal_node(slot) && to_free->shift)
break;
- if (radix_tree_is_indirect_ptr(slot))
+ if (radix_tree_is_internal_node(slot))
entry_to_node(slot)->parent = NULL;
/*
@@ -1446,7 +1446,7 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
* also results in a stale slot). So tag the slot as indirect
* to force callers to retry.
*/
- if (!radix_tree_is_indirect_ptr(slot))
+ if (!radix_tree_is_internal_node(slot))
to_free->slots[0] = RADIX_TREE_RETRY;
radix_tree_node_free(to_free);
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index 7b0bc1f..a6e8099 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -193,7 +193,7 @@ static int verify_node(struct radix_tree_node *slot, unsigned int tag,
void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
{
struct radix_tree_node *node = root->rnode;
- if (!radix_tree_is_indirect_ptr(node))
+ if (!radix_tree_is_internal_node(node))
return;
verify_node(node, tag, !!root_tag_get(root, tag));
}
@@ -222,7 +222,7 @@ void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
{
unsigned shift;
struct radix_tree_node *node = root->rnode;
- if (!radix_tree_is_indirect_ptr(node)) {
+ if (!radix_tree_is_internal_node(node)) {
assert(maxindex == 0);
return;
}
--
2.8.0.rc3
Convert radix_tree_next_chunk to use 'child' instead of 'slot' as the name
of the child node. Also use node_maxindex() where it makes sense.
The 'rnode' variable was unnecessary; it doesn't overlap in usage with
'node', so we can just use 'node' the whole way through the function.
Improve the testcase to start the walk from every index in the carefully
constructed tree, and to accept any index within the range covered by
the entry.
Signed-off-by: Matthew Wilcox <[email protected]>
---
lib/radix-tree.c | 53 +++++++------------
tools/testing/radix-tree/multiorder.c | 99 +++++++++++++++++++----------------
2 files changed, 74 insertions(+), 78 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 094dfc0..fab4485 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -876,7 +876,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
struct radix_tree_iter *iter, unsigned flags)
{
unsigned shift, tag = flags & RADIX_TREE_ITER_TAG_MASK;
- struct radix_tree_node *rnode, *node;
+ struct radix_tree_node *node, *child;
unsigned long index, offset, maxindex;
if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
@@ -896,38 +896,29 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
return NULL;
restart:
- shift = radix_tree_load_root(root, &rnode, &maxindex);
+ shift = radix_tree_load_root(root, &child, &maxindex);
if (index > maxindex)
return NULL;
+ if (!child)
+ return NULL;
- if (radix_tree_is_internal_node(rnode)) {
- rnode = entry_to_node(rnode);
- } else if (rnode) {
+ if (!radix_tree_is_internal_node(child)) {
/* Single-slot tree */
iter->index = index;
iter->next_index = maxindex + 1;
iter->tags = 1;
- __set_iter_shift(iter, shift);
+ __set_iter_shift(iter, 0);
return (void **)&root->rnode;
- } else
- return NULL;
-
- shift -= RADIX_TREE_MAP_SHIFT;
- offset = index >> shift;
-
- node = rnode;
- while (1) {
- struct radix_tree_node *slot;
- unsigned new_off = radix_tree_descend(node, &slot, offset);
+ }
- if (new_off < offset) {
- offset = new_off;
- index &= ~((RADIX_TREE_MAP_SIZE << shift) - 1);
- index |= offset << shift;
- }
+ do {
+ node = entry_to_node(child);
+ shift -= RADIX_TREE_MAP_SHIFT;
+ offset = (index >> shift) & RADIX_TREE_MAP_MASK;
+ offset = radix_tree_descend(node, &child, offset);
if ((flags & RADIX_TREE_ITER_TAGGED) ?
- !tag_get(node, tag, offset) : !slot) {
+ !tag_get(node, tag, offset) : !child) {
/* Hole detected */
if (flags & RADIX_TREE_ITER_CONTIG)
return NULL;
@@ -945,29 +936,23 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
if (slot)
break;
}
- index &= ~((RADIX_TREE_MAP_SIZE << shift) - 1);
+ index &= ~node_maxindex(node);
index += offset << shift;
/* Overflow after ~0UL */
if (!index)
return NULL;
if (offset == RADIX_TREE_MAP_SIZE)
goto restart;
- slot = rcu_dereference_raw(node->slots[offset]);
+ child = rcu_dereference_raw(node->slots[offset]);
}
- if ((slot == NULL) || (slot == RADIX_TREE_RETRY))
+ if ((child == NULL) || (child == RADIX_TREE_RETRY))
goto restart;
- if (!radix_tree_is_internal_node(slot))
- break;
-
- node = entry_to_node(slot);
- shift -= RADIX_TREE_MAP_SHIFT;
- offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- }
+ } while (radix_tree_is_internal_node(child));
/* Update the iterator state */
- iter->index = index & ~((1 << shift) - 1);
- iter->next_index = (index | ((RADIX_TREE_MAP_SIZE << shift) - 1)) + 1;
+ iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
+ iter->next_index = (index | node_maxindex(node)) + 1;
__set_iter_shift(iter, shift);
/* Construct iter->tags bit-mask from node->tags[tag] array */
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index c061f4b..39d9b95 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -202,7 +202,7 @@ void multiorder_iteration(void)
RADIX_TREE(tree, GFP_KERNEL);
struct radix_tree_iter iter;
void **slot;
- int i, err;
+ int i, j, err;
printf("Multiorder iteration test\n");
@@ -215,29 +215,21 @@ void multiorder_iteration(void)
assert(!err);
}
- i = 0;
- /* start from index 1 to verify we find the multi-order entry at 0 */
- radix_tree_for_each_slot(slot, &tree, &iter, 1) {
- int height = order[i] / RADIX_TREE_MAP_SHIFT;
- int shift = height * RADIX_TREE_MAP_SHIFT;
-
- assert(iter.index == index[i]);
- assert(iter.shift == shift);
- i++;
- }
-
- /*
- * Now iterate through the tree starting at an elevated multi-order
- * entry, beginning at an index in the middle of the range.
- */
- i = 8;
- radix_tree_for_each_slot(slot, &tree, &iter, 70) {
- int height = order[i] / RADIX_TREE_MAP_SHIFT;
- int shift = height * RADIX_TREE_MAP_SHIFT;
-
- assert(iter.index == index[i]);
- assert(iter.shift == shift);
- i++;
+ for (j = 0; j < 256; j++) {
+ for (i = 0; i < NUM_ENTRIES; i++)
+ if (j <= (index[i] | ((1 << order[i]) - 1)))
+ break;
+
+ radix_tree_for_each_slot(slot, &tree, &iter, j) {
+ int height = order[i] / RADIX_TREE_MAP_SHIFT;
+ int shift = height * RADIX_TREE_MAP_SHIFT;
+ int mask = (1 << order[i]) - 1;
+
+ assert(iter.index >= (index[i] &~ mask));
+ assert(iter.index <= (index[i] | mask));
+ assert(iter.shift == shift);
+ i++;
+ }
}
item_kill_tree(&tree);
@@ -249,7 +241,7 @@ void multiorder_tagged_iteration(void)
struct radix_tree_iter iter;
void **slot;
unsigned long first = 0;
- int i;
+ int i, j;
printf("Multiorder tagged iteration test\n");
@@ -268,30 +260,49 @@ void multiorder_tagged_iteration(void)
for (i = 0; i < TAG_ENTRIES; i++)
assert(radix_tree_tag_set(&tree, tag_index[i], 1));
- i = 0;
- /* start from index 1 to verify we find the multi-order entry at 0 */
- radix_tree_for_each_tagged(slot, &tree, &iter, 1, 1) {
- assert(iter.index == tag_index[i]);
- i++;
- }
-
- /*
- * Now iterate through the tree starting at an elevated multi-order
- * entry, beginning at an index in the middle of the range.
- */
- i = 4;
- radix_tree_for_each_slot(slot, &tree, &iter, 70) {
- assert(iter.index == tag_index[i]);
- i++;
+ for (j = 0; j < 256; j++) {
+ int mask, k;
+
+ for (i = 0; i < TAG_ENTRIES; i++) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ if (j <= (index[k] | ((1 << order[k]) - 1)))
+ break;
+ }
+
+ radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ mask = (1 << order[k]) - 1;
+
+ assert(iter.index >= (tag_index[i] &~ mask));
+ assert(iter.index <= (tag_index[i] | mask));
+ i++;
+ }
}
radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
MT_NUM_ENTRIES, 1, 2);
- i = 0;
- radix_tree_for_each_tagged(slot, &tree, &iter, 1, 2) {
- assert(iter.index == tag_index[i]);
- i++;
+ for (j = 0; j < 256; j++) {
+ int mask, k;
+
+ for (i = 0; i < TAG_ENTRIES; i++) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ if (j <= (index[k] | ((1 << order[k]) - 1)))
+ break;
+ }
+
+ radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
+ for (k = i; index[k] < tag_index[i]; k++)
+ ;
+ mask = (1 << order[k]) - 1;
+
+ assert(iter.index >= (tag_index[i] &~ mask));
+ assert(iter.index <= (tag_index[i] | mask));
+ i++;
+ }
}
first = 1;
--
2.8.0.rc3
verify_node() can use node->shift instead of the height.
tree_verify_min_height() can be converted over to using node_maxindex()
and shift_maxindex() instead of radix_tree_maxindex().
Signed-off-by: Matthew Wilcox <[email protected]>
---
tools/testing/radix-tree/test.c | 34 +++++++++++++++++++++++-----------
tools/testing/radix-tree/test.h | 3 ++-
2 files changed, 25 insertions(+), 12 deletions(-)
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index da54f11..3004c58 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -143,7 +143,7 @@ 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;
@@ -159,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++)
@@ -171,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++) {
@@ -191,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_indirect_ptr(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)
@@ -218,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_indirect_ptr(node)) {
+ assert(maxindex == 0);
+ return;
+ }
+
+ node = indirect_to_ptr(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);
}
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 67217c9..866c8c6 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -42,4 +42,5 @@ extern int nr_allocated;
void *indirect_to_ptr(void *ptr);
void radix_tree_dump(struct radix_tree_root *root);
int root_tag_get(struct radix_tree_root *root, unsigned int tag);
-unsigned long radix_tree_maxindex(unsigned int height);
+unsigned long node_maxindex(struct radix_tree_node *);
+unsigned long shift_maxindex(unsigned int shift);
--
2.8.0.rc3
Mirrors the earlier commit introducing node_to_entry().
Also change the type returned to be a struct radix_tree_node pointer.
That lets us simplify a couple of places in the radix tree shrink & extend
paths where we could convert an entry into a pointer, modify the node, then
convert the pointer back into an entry.
Signed-off-by: Matthew Wilcox <[email protected]>
---
include/linux/radix-tree.h | 12 +++++------
lib/radix-tree.c | 48 ++++++++++++++++++-----------------------
tools/testing/radix-tree/test.c | 4 ++--
tools/testing/radix-tree/test.h | 1 -
4 files changed, 28 insertions(+), 37 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index c8cc879..b94aa19 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -442,7 +442,7 @@ radix_tree_chunk_size(struct radix_tree_iter *iter)
return (iter->next_index - iter->index) >> iter_shift(iter);
}
-static inline void *indirect_to_ptr(void *ptr)
+static inline struct radix_tree_node *entry_to_node(void *ptr)
{
return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
}
@@ -469,7 +469,7 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
return NULL;
while (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
radix_tree_is_indirect_ptr(slot[1])) {
- if (indirect_to_ptr(slot[1]) == canon) {
+ if (entry_to_node(slot[1]) == canon) {
iter->tags >>= 1;
iter->index = __radix_tree_iter_add(iter, 1);
slot++;
@@ -499,12 +499,10 @@ radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
if (IS_ENABLED(CONFIG_RADIX_TREE_MULTIORDER) &&
radix_tree_is_indirect_ptr(*slot)) {
- if (indirect_to_ptr(*slot) == canon)
+ if (entry_to_node(*slot) == canon)
continue;
- else {
- iter->next_index = iter->index;
- break;
- }
+ iter->next_index = iter->index;
+ break;
}
if (likely(*slot))
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index f7a0cf7..675e85f 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -230,13 +230,13 @@ static void dump_node(struct radix_tree_node *node, unsigned long index)
if (is_sibling_entry(node, entry)) {
pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n",
entry, i,
- *(void **)indirect_to_ptr(entry),
+ *(void **)entry_to_node(entry),
first, last);
} else if (!radix_tree_is_indirect_ptr(entry)) {
pr_debug("radix entry %p offset %ld indices %ld-%ld\n",
entry, i, first, last);
} else {
- dump_node(indirect_to_ptr(entry), first);
+ dump_node(entry_to_node(entry), first);
}
}
}
@@ -249,7 +249,7 @@ static void radix_tree_dump(struct radix_tree_root *root)
root->gfp_mask >> __GFP_BITS_SHIFT);
if (!radix_tree_is_indirect_ptr(root->rnode))
return;
- dump_node(indirect_to_ptr(root->rnode), 0);
+ dump_node(entry_to_node(root->rnode), 0);
}
#endif
@@ -422,7 +422,7 @@ static unsigned radix_tree_load_root(struct radix_tree_root *root,
*nodep = node;
if (likely(radix_tree_is_indirect_ptr(node))) {
- node = indirect_to_ptr(node);
+ node = entry_to_node(node);
*maxindex = node_maxindex(node);
return node->shift + RADIX_TREE_MAP_SHIFT;
}
@@ -467,11 +467,8 @@ static int radix_tree_extend(struct radix_tree_root *root,
node->offset = 0;
node->count = 1;
node->parent = NULL;
- if (radix_tree_is_indirect_ptr(slot)) {
- slot = indirect_to_ptr(slot);
- slot->parent = node;
- slot = node_to_entry(slot);
- }
+ if (radix_tree_is_indirect_ptr(slot))
+ entry_to_node(slot)->parent = node;
node->slots[0] = slot;
slot = node_to_entry(node);
rcu_assign_pointer(root->rnode, slot);
@@ -542,7 +539,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
break;
/* Go a level down */
- node = indirect_to_ptr(slot);
+ node = entry_to_node(slot);
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
offset = radix_tree_descend(node, &slot, offset);
}
@@ -645,7 +642,7 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
if (node == RADIX_TREE_RETRY)
goto restart;
- parent = indirect_to_ptr(node);
+ parent = entry_to_node(node);
shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
offset = radix_tree_descend(parent, &node, offset);
@@ -729,7 +726,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- parent = indirect_to_ptr(node);
+ parent = entry_to_node(node);
offset = radix_tree_descend(parent, &node, offset);
BUG_ON(!node);
@@ -777,7 +774,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- parent = indirect_to_ptr(node);
+ parent = entry_to_node(node);
offset = radix_tree_descend(parent, &node, offset);
}
@@ -844,7 +841,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- parent = indirect_to_ptr(node);
+ parent = entry_to_node(node);
offset = radix_tree_descend(parent, &node, offset);
if (!node)
@@ -904,7 +901,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
return NULL;
if (radix_tree_is_indirect_ptr(rnode)) {
- rnode = indirect_to_ptr(rnode);
+ rnode = entry_to_node(rnode);
} else if (rnode) {
/* Single-slot tree */
iter->index = index;
@@ -963,7 +960,7 @@ void **radix_tree_next_chunk(struct radix_tree_root *root,
if (!radix_tree_is_indirect_ptr(slot))
break;
- node = indirect_to_ptr(slot);
+ node = entry_to_node(slot);
shift -= RADIX_TREE_MAP_SHIFT;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
}
@@ -1048,7 +1045,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
return 1;
}
- node = indirect_to_ptr(slot);
+ node = entry_to_node(slot);
shift -= RADIX_TREE_MAP_SHIFT;
for (;;) {
@@ -1063,7 +1060,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
goto next;
/* Sibling slots never have tags set on them */
if (radix_tree_is_indirect_ptr(slot)) {
- node = indirect_to_ptr(slot);
+ node = entry_to_node(slot);
shift -= RADIX_TREE_MAP_SHIFT;
continue;
}
@@ -1323,7 +1320,7 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item,
}
continue;
}
- node = indirect_to_ptr(node);
+ node = entry_to_node(node);
if (is_sibling_entry(slot, node))
continue;
slot = node;
@@ -1368,7 +1365,7 @@ unsigned long radix_tree_locate_item(struct radix_tree_root *root, void *item)
break;
}
- node = indirect_to_ptr(node);
+ node = entry_to_node(node);
max_index = node_maxindex(node);
if (cur_index > max_index) {
@@ -1404,7 +1401,7 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
if (!radix_tree_is_indirect_ptr(to_free))
break;
- to_free = indirect_to_ptr(to_free);
+ to_free = entry_to_node(to_free);
/*
* The candidate node has more than one child, or its child
@@ -1419,11 +1416,8 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
if (!radix_tree_is_indirect_ptr(slot) && to_free->shift)
break;
- if (radix_tree_is_indirect_ptr(slot)) {
- slot = indirect_to_ptr(slot);
- slot->parent = NULL;
- slot = node_to_entry(slot);
- }
+ if (radix_tree_is_indirect_ptr(slot))
+ entry_to_node(slot)->parent = NULL;
/*
* We don't need rcu_assign_pointer(), since we are simply
@@ -1482,7 +1476,7 @@ bool __radix_tree_delete_node(struct radix_tree_root *root,
struct radix_tree_node *parent;
if (node->count) {
- if (node == indirect_to_ptr(root->rnode))
+ if (node == entry_to_node(root->rnode))
deleted |= radix_tree_shrink(root);
return deleted;
}
diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c
index 3004c58..7b0bc1f 100644
--- a/tools/testing/radix-tree/test.c
+++ b/tools/testing/radix-tree/test.c
@@ -149,7 +149,7 @@ static int verify_node(struct radix_tree_node *slot, unsigned int tag,
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++) {
@@ -227,7 +227,7 @@ void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
return;
}
- node = indirect_to_ptr(node);
+ node = entry_to_node(node);
assert(maxindex <= node_maxindex(node));
shift = node->shift;
diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h
index 866c8c6..e851313 100644
--- a/tools/testing/radix-tree/test.h
+++ b/tools/testing/radix-tree/test.h
@@ -39,7 +39,6 @@ void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag);
extern int nr_allocated;
/* Normally private parts of lib/radix-tree.c */
-void *indirect_to_ptr(void *ptr);
void radix_tree_dump(struct radix_tree_root *root);
int root_tag_get(struct radix_tree_root *root, unsigned int tag);
unsigned long node_maxindex(struct radix_tree_node *);
--
2.8.0.rc3
The name RADIX_TREE_INDIRECT_PTR doesn't really match the meaning.
RADIX_TREE_INTERNAL_NODE is a better name.
Signed-off-by: Matthew Wilcox <[email protected]>
---
include/linux/radix-tree.h | 30 +++++++++++++-----------------
lib/radix-tree.c | 2 +-
2 files changed, 14 insertions(+), 18 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index c0d223c..c8cc879 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -29,20 +29,16 @@
#include <linux/rcupdate.h>
/*
- * An indirect pointer (root->rnode pointing to a radix_tree_node, rather
- * than a data item) is signalled by the low bit set in the root->rnode
- * pointer.
- *
- * In this case root->height is > 0, but the indirect pointer tests are
- * needed for RCU lookups (because root->height is unreliable). The only
- * time callers need worry about this is when doing a lookup_slot under
- * RCU.
- *
- * Indirect pointer in fact is also used to tag the last pointer of a node
- * when it is shrunk, before we rcu free the node. See shrink code for
- * details.
+ * Entries in the radix tree have the low bit set if they refer to a
+ * radix_tree_node. If the low bit is clear then the entry is user data.
+ *
+ * We also use the low bit to indicate that the slot will be freed in the
+ * next RCU idle period, and users need to re-walk the tree to find the
+ * new slot for the index that they were looking for. See the comment in
+ * radix_tree_shrink() for details.
*/
-#define RADIX_TREE_INDIRECT_PTR 1
+#define RADIX_TREE_INTERNAL_NODE 1
+
/*
* A common use of the radix tree is to store pointers to struct pages;
* but shmem/tmpfs needs also to store swap entries in the same tree:
@@ -63,7 +59,7 @@
static inline int radix_tree_is_indirect_ptr(void *ptr)
{
- return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
+ return (int)((unsigned long)ptr & RADIX_TREE_INTERNAL_NODE);
}
/*** radix-tree API starts here ***/
@@ -228,7 +224,7 @@ static inline void *radix_tree_deref_slot_protected(void **pslot,
*/
static inline int radix_tree_deref_retry(void *arg)
{
- return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR);
+ return unlikely(radix_tree_is_indirect_ptr(arg));
}
/**
@@ -250,7 +246,7 @@ static inline int radix_tree_exceptional_entry(void *arg)
static inline int radix_tree_exception(void *arg)
{
return unlikely((unsigned long)arg &
- (RADIX_TREE_INDIRECT_PTR | RADIX_TREE_EXCEPTIONAL_ENTRY));
+ (RADIX_TREE_INTERNAL_NODE | RADIX_TREE_EXCEPTIONAL_ENTRY));
}
/**
@@ -448,7 +444,7 @@ radix_tree_chunk_size(struct radix_tree_iter *iter)
static inline void *indirect_to_ptr(void *ptr)
{
- return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
+ return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
}
/**
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 909527a..1fe546c 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -68,7 +68,7 @@ static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
static inline void *ptr_to_indirect(void *ptr)
{
- return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
+ return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
}
#define RADIX_TREE_RETRY ptr_to_indirect(NULL)
--
2.8.0.rc3
ptr_to_indirect() was a bad name. What it really means is "Convert this
pointer to a node into an entry suitable for storing in the radix tree".
So node_to_entry() seemed like a better name.
Signed-off-by: Matthew Wilcox <[email protected]>
---
lib/radix-tree.c | 21 ++++++++++-----------
1 file changed, 10 insertions(+), 11 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1fe546c..f7a0cf7 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -66,12 +66,12 @@ struct radix_tree_preload {
};
static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
-static inline void *ptr_to_indirect(void *ptr)
+static inline void *node_to_entry(void *ptr)
{
return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
}
-#define RADIX_TREE_RETRY ptr_to_indirect(NULL)
+#define RADIX_TREE_RETRY node_to_entry(NULL)
#ifdef CONFIG_RADIX_TREE_MULTIORDER
/* Sibling slots point directly to another slot in the same node */
@@ -470,13 +470,12 @@ static int radix_tree_extend(struct radix_tree_root *root,
if (radix_tree_is_indirect_ptr(slot)) {
slot = indirect_to_ptr(slot);
slot->parent = node;
- slot = ptr_to_indirect(slot);
+ slot = node_to_entry(slot);
}
node->slots[0] = slot;
- node = ptr_to_indirect(node);
- rcu_assign_pointer(root->rnode, node);
+ slot = node_to_entry(node);
+ rcu_assign_pointer(root->rnode, slot);
shift += RADIX_TREE_MAP_SHIFT;
- slot = node;
} while (shift <= maxshift);
out:
return maxshift + RADIX_TREE_MAP_SHIFT;
@@ -534,11 +533,11 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
slot->parent = node;
if (node) {
rcu_assign_pointer(node->slots[offset],
- ptr_to_indirect(slot));
+ node_to_entry(slot));
node->count++;
} else
rcu_assign_pointer(root->rnode,
- ptr_to_indirect(slot));
+ node_to_entry(slot));
} else if (!radix_tree_is_indirect_ptr(slot))
break;
@@ -553,7 +552,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
if (order > shift) {
int i, n = 1 << (order - shift);
offset = offset & ~(n - 1);
- slot = ptr_to_indirect(&node->slots[offset]);
+ slot = node_to_entry(&node->slots[offset]);
for (i = 0; i < n; i++) {
if (node->slots[offset + i])
return -EEXIST;
@@ -1423,7 +1422,7 @@ static inline bool radix_tree_shrink(struct radix_tree_root *root)
if (radix_tree_is_indirect_ptr(slot)) {
slot = indirect_to_ptr(slot);
slot->parent = NULL;
- slot = ptr_to_indirect(slot);
+ slot = node_to_entry(slot);
}
/*
@@ -1564,7 +1563,7 @@ void *radix_tree_delete_item(struct radix_tree_root *root,
radix_tree_tag_clear(root, index, tag);
}
- delete_sibling_entries(node, ptr_to_indirect(slot), offset);
+ delete_sibling_entries(node, node_to_entry(slot), offset);
node->slots[offset] = NULL;
node->count--;
--
2.8.0.rc3
Typos, whitespace, grammar, line length, using the correct types, etc.
Signed-off-by: Matthew Wilcox <[email protected]>
Reviewed-by: Ross Zwisler <[email protected]>
---
lib/radix-tree.c | 70 +++++++++++++++++++++++++++++---------------------------
1 file changed, 36 insertions(+), 34 deletions(-)
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index cd7dc59..746a240 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -66,7 +66,7 @@ static struct kmem_cache *radix_tree_node_cachep;
* Per-cpu pool of preloaded nodes
*/
struct radix_tree_preload {
- int nr;
+ unsigned nr;
/* nodes->private_data points to next preallocated node */
struct radix_tree_node *nodes;
};
@@ -147,7 +147,7 @@ static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
}
-static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
+static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
{
root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
}
@@ -159,7 +159,7 @@ static inline void root_tag_clear_all(struct radix_tree_root *root)
static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
- return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
+ return (__force int)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
}
static inline unsigned root_tags_get(struct radix_tree_root *root)
@@ -173,7 +173,7 @@ static inline unsigned root_tags_get(struct radix_tree_root *root)
*/
static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
{
- int idx;
+ unsigned idx;
for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
if (node->tags[tag][idx])
return 1;
@@ -273,9 +273,9 @@ radix_tree_node_alloc(struct radix_tree_root *root)
gfp_t gfp_mask = root_gfp_mask(root);
/*
- * Preload code isn't irq safe and it doesn't make sence to use
- * preloading in the interrupt anyway as all the allocations have to
- * be atomic. So just do normal allocation when in interrupt.
+ * Preload code isn't irq safe and it doesn't make sense to use
+ * preloading during an interrupt anyway as all the allocations have
+ * to be atomic. So just do normal allocation when in interrupt.
*/
if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) {
struct radix_tree_preload *rtp;
@@ -448,7 +448,6 @@ static unsigned radix_tree_load_root(struct radix_tree_root *root,
static int radix_tree_extend(struct radix_tree_root *root,
unsigned long index)
{
- struct radix_tree_node *node;
struct radix_tree_node *slot;
unsigned int height;
int tag;
@@ -465,7 +464,9 @@ static int radix_tree_extend(struct radix_tree_root *root,
do {
unsigned int newheight;
- if (!(node = radix_tree_node_alloc(root)))
+ struct radix_tree_node *node = radix_tree_node_alloc(root);
+
+ if (!node)
return -ENOMEM;
/* Propagate the aggregated tag info into the new root */
@@ -542,7 +543,8 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
while (shift > order) {
if (slot == NULL) {
/* Have to add a child node. */
- if (!(slot = radix_tree_node_alloc(root)))
+ slot = radix_tree_node_alloc(root);
+ if (!slot)
return -ENOMEM;
slot->path = height;
slot->parent = node;
@@ -722,13 +724,13 @@ EXPORT_SYMBOL(radix_tree_lookup);
* radix_tree_tag_set - set a tag on a radix tree node
* @root: radix tree root
* @index: index key
- * @tag: tag index
+ * @tag: tag index
*
* Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
* corresponding to @index in the radix tree. From
* the root all the way down to the leaf node.
*
- * Returns the address of the tagged item. Setting a tag on a not-present
+ * Returns the address of the tagged item. Setting a tag on a not-present
* item is a bug.
*/
void *radix_tree_tag_set(struct radix_tree_root *root,
@@ -767,11 +769,11 @@ EXPORT_SYMBOL(radix_tree_tag_set);
* radix_tree_tag_clear - clear a tag on a radix tree node
* @root: radix tree root
* @index: index key
- * @tag: tag index
+ * @tag: tag index
*
* Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
- * corresponding to @index in the radix tree. If
- * this causes the leaf node to have no tags set then clear the tag in the
+ * corresponding to @index in the radix tree. If this causes
+ * the leaf node to have no tags set then clear the tag in the
* next-to-leaf node, etc.
*
* Returns the address of the tagged item on success, else NULL. ie:
@@ -829,7 +831,7 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
* radix_tree_tag_get - get a tag on a radix tree node
* @root: radix tree root
* @index: index key
- * @tag: tag index (< RADIX_TREE_MAX_TAGS)
+ * @tag: tag index (< RADIX_TREE_MAX_TAGS)
*
* Return values:
*
@@ -1035,7 +1037,7 @@ EXPORT_SYMBOL(radix_tree_next_chunk);
* set is outside the range we are scanning. This reults in dangling tags and
* can lead to problems with later tag operations (e.g. livelocks on lookups).
*
- * The function returns number of leaves where the tag was set and sets
+ * The function returns the number of leaves where the tag was set and sets
* *first_indexp to the first unscanned index.
* WARNING! *first_indexp can wrap if last_index is ULONG_MAX. Caller must
* be prepared to handle that.
@@ -1153,9 +1155,10 @@ EXPORT_SYMBOL(radix_tree_range_tag_if_tagged);
*
* Like radix_tree_lookup, radix_tree_gang_lookup may be called under
* rcu_read_lock. In this case, rather than the returned results being
- * an atomic snapshot of the tree at a single point in time, the semantics
- * of an RCU protected gang lookup are as though multiple radix_tree_lookups
- * have been issued in individual locks, and results stored in 'results'.
+ * an atomic snapshot of the tree at a single point in time, the
+ * semantics of an RCU protected gang lookup are as though multiple
+ * radix_tree_lookups have been issued in individual locks, and results
+ * stored in 'results'.
*/
unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
@@ -1461,7 +1464,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
* their slot to become empty sooner or later.
*
* For example, lockless pagecache will look up a slot, deref
- * the page pointer, and if the page is 0 refcount it means it
+ * the page pointer, and if the page has 0 refcount it means it
* was concurrently deleted from pagecache so try the deref
* again. Fortunately there is already a requirement for logic
* to retry the entire slot lookup -- the indirect pointer
@@ -1650,24 +1653,23 @@ static __init void radix_tree_init_maxindex(void)
}
static int radix_tree_callback(struct notifier_block *nfb,
- unsigned long action,
- void *hcpu)
+ unsigned long action, void *hcpu)
{
- int cpu = (long)hcpu;
- struct radix_tree_preload *rtp;
- struct radix_tree_node *node;
-
- /* Free per-cpu pool of perloaded nodes */
- if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
- rtp = &per_cpu(radix_tree_preloads, cpu);
- while (rtp->nr) {
+ int cpu = (long)hcpu;
+ struct radix_tree_preload *rtp;
+ struct radix_tree_node *node;
+
+ /* Free per-cpu pool of preloaded nodes */
+ if (action == CPU_DEAD || action == CPU_DEAD_FROZEN) {
+ rtp = &per_cpu(radix_tree_preloads, cpu);
+ while (rtp->nr) {
node = rtp->nodes;
rtp->nodes = node->private_data;
kmem_cache_free(radix_tree_node_cachep, node);
rtp->nr--;
- }
- }
- return NOTIFY_OK;
+ }
+ }
+ return NOTIFY_OK;
}
void __init radix_tree_init(void)
--
2.8.0.rc3
node->shift represents the shift necessary for looking in the slots
array at this level. It is equal to the old
(node->height - 1) * RADIX_TREE_MAP_SHIFT.
Signed-off-by: Matthew Wilcox <[email protected]>
Reviewed-by: Ross Zwisler <[email protected]>
---
include/linux/radix-tree.h | 2 +-
lib/radix-tree.c | 30 ++++++++++++++++--------------
2 files changed, 17 insertions(+), 15 deletions(-)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 2d2ad9d..0374582 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -89,7 +89,7 @@ static inline int radix_tree_is_indirect_ptr(void *ptr)
#define RADIX_TREE_COUNT_MASK ((1UL << RADIX_TREE_COUNT_SHIFT) - 1)
struct radix_tree_node {
- unsigned char height; /* From the bottom */
+ unsigned char shift; /* Bits remaining in each slot */
unsigned char offset; /* Slot offset in parent */
unsigned int count;
union {
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index d42c5b5..e963823 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -223,10 +223,10 @@ static void dump_node(struct radix_tree_node *node,
{
unsigned long i;
- pr_debug("radix node: %p offset %d tags %lx %lx %lx height %d count %d parent %p\n",
+ pr_debug("radix node: %p offset %d tags %lx %lx %lx shift %d count %d parent %p\n",
node, node->offset,
node->tags[0][0], node->tags[1][0], node->tags[2][0],
- node->height, node->count, node->parent);
+ node->shift, node->count, node->parent);
for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
unsigned long first = index | (i << shift);
@@ -419,9 +419,14 @@ static inline unsigned long radix_tree_maxindex(unsigned int height)
return height_to_maxindex[height];
}
+static inline unsigned long shift_maxindex(unsigned int shift)
+{
+ return (RADIX_TREE_MAP_SIZE << shift) - 1;
+}
+
static inline unsigned long node_maxindex(struct radix_tree_node *node)
{
- return radix_tree_maxindex(node->height);
+ return shift_maxindex(node->shift);
}
static unsigned radix_tree_load_root(struct radix_tree_root *root,
@@ -434,7 +439,7 @@ static unsigned radix_tree_load_root(struct radix_tree_root *root,
if (likely(radix_tree_is_indirect_ptr(node))) {
node = indirect_to_ptr(node);
*maxindex = node_maxindex(node);
- return node->height * RADIX_TREE_MAP_SHIFT;
+ return node->shift + RADIX_TREE_MAP_SHIFT;
}
*maxindex = 0;
@@ -475,9 +480,9 @@ static int radix_tree_extend(struct radix_tree_root *root,
}
/* Increase the height. */
- newheight = root->height + 1;
+ newheight = root->height;
BUG_ON(newheight > BITS_PER_LONG);
- node->height = newheight;
+ node->shift = newheight * RADIX_TREE_MAP_SHIFT;
node->offset = 0;
node->count = 1;
node->parent = NULL;
@@ -490,7 +495,7 @@ static int radix_tree_extend(struct radix_tree_root *root,
node->slots[0] = slot;
node = ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
- root->height = newheight;
+ root->height = ++newheight;
} while (height > root->height);
out:
return height * RADIX_TREE_MAP_SHIFT;
@@ -519,7 +524,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
{
struct radix_tree_node *node = NULL, *slot;
unsigned long maxindex;
- unsigned int height, shift, offset;
+ unsigned int shift, offset;
unsigned long max = index | ((1UL << order) - 1);
shift = radix_tree_load_root(root, &slot, &maxindex);
@@ -537,16 +542,15 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
}
}
- height = root->height;
-
offset = 0; /* uninitialised var warning */
while (shift > order) {
+ shift -= RADIX_TREE_MAP_SHIFT;
if (slot == NULL) {
/* Have to add a child node. */
slot = radix_tree_node_alloc(root);
if (!slot)
return -ENOMEM;
- slot->height = height;
+ slot->shift = shift;
slot->offset = offset;
slot->parent = node;
if (node) {
@@ -560,8 +564,6 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
break;
/* Go a level down */
- height--;
- shift -= RADIX_TREE_MAP_SHIFT;
node = indirect_to_ptr(slot);
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
offset = radix_tree_descend(node, &slot, offset);
@@ -1322,7 +1324,7 @@ static unsigned long __locate(struct radix_tree_node *slot, void *item,
unsigned int shift;
unsigned long base, i;
- shift = slot->height * RADIX_TREE_MAP_SHIFT;
+ shift = slot->shift + RADIX_TREE_MAP_SHIFT;
do {
shift -= RADIX_TREE_MAP_SHIFT;
--
2.8.0.rc3
On Fri, Apr 15 2016, Matthew Wilcox wrote:
> Typos, whitespace, grammar, line length, using the correct types, etc.
>
> Signed-off-by: Matthew Wilcox <[email protected]>
> Reviewed-by: Ross Zwisler <[email protected]>
>
> -static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
> +static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
Changing "unsigned int" to "unsigned" - Bold.
> {
> root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
> }
> @@ -159,7 +159,7 @@ static inline void root_tag_clear_all(struct radix_tree_root *root)
>
> static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
Not doing it uniformly - Priceless.
NeilBrown