4/5
--
SUSE Labs, Novell Inc.
Correctly determine the tags to be cleared in radix_tree_delete so we
don't keep moving up the tree clearing tags that we don't need to.
Also, tag_set was probably just made conditional so as not to dirty
too many cachelines high up in the radix tree. Instead, put this
logic into radix_tree_tag_set.
Signed-off-by: Nick Piggin <[email protected]>
Index: linux-2.6/lib/radix-tree.c
===================================================================
--- linux-2.6.orig/lib/radix-tree.c
+++ linux-2.6/lib/radix-tree.c
@@ -135,18 +135,17 @@ out:
static inline void tag_set(struct radix_tree_node *node, int tag, int offset)
{
- if (!test_bit(offset, &node->tags[tag][0]))
- __set_bit(offset, &node->tags[tag][0]);
+ __set_bit(offset, node->tags[tag]);
}
static inline void tag_clear(struct radix_tree_node *node, int tag, int offset)
{
- __clear_bit(offset, &node->tags[tag][0]);
+ __clear_bit(offset, node->tags[tag]);
}
static inline int tag_get(struct radix_tree_node *node, int tag, int offset)
{
- return test_bit(offset, &node->tags[tag][0]);
+ return test_bit(offset, node->tags[tag]);
}
/*
@@ -373,7 +372,8 @@ void *radix_tree_tag_set(struct radix_tr
int offset;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- tag_set(slot, tag, offset);
+ if (!tag_get(slot, tag, offset))
+ tag_set(slot, tag, offset);
slot = slot->slots[offset];
BUG_ON(slot == NULL);
shift -= RADIX_TREE_MAP_SHIFT;
@@ -433,6 +433,8 @@ void *radix_tree_tag_clear(struct radix_
goto out;
do {
+ if (!tag_get(pathp->node, tag, pathp->offset))
+ goto out;
tag_clear(pathp->node, tag, pathp->offset);
if (tag_get_any_node(pathp->node, tag))
goto out;
@@ -693,6 +695,8 @@ void *radix_tree_delete(struct radix_tre
void *ret = NULL;
char tags[RADIX_TREE_TAGS];
int nr_cleared_tags;
+ int tag;
+ int offset;
height = root->height;
if (index > radix_tree_maxindex(height))
@@ -703,16 +707,14 @@ void *radix_tree_delete(struct radix_tre
slot = root->rnode;
for ( ; height > 0; height--) {
- int offset;
-
if (slot == NULL)
goto out;
+ pathp++;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- pathp[1].offset = offset;
- pathp[1].node = slot;
+ pathp->offset = offset;
+ pathp->node = slot;
slot = slot->slots[offset];
- pathp++;
shift -= RADIX_TREE_MAP_SHIFT;
}
@@ -725,24 +727,28 @@ void *radix_tree_delete(struct radix_tre
/*
* Clear all tags associated with the just-deleted item
*/
- memset(tags, 0, sizeof(tags));
- do {
- int tag;
+ nr_cleared_tags = 0;
+ for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
+ if (tag_get(pathp->node, tag, pathp->offset)) {
+ tag_clear(pathp->node, tag, pathp->offset);
+ tags[tag] = 0;
+ nr_cleared_tags++;
+ } else
+ tags[tag] = 1;
+ }
- nr_cleared_tags = RADIX_TREE_TAGS;
+ for (pathp--; nr_cleared_tags && pathp->node; pathp--) {
for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
if (tags[tag])
continue;
tag_clear(pathp->node, tag, pathp->offset);
-
if (tag_get_any_node(pathp->node, tag)) {
tags[tag] = 1;
nr_cleared_tags--;
}
}
- pathp--;
- } while (pathp->node && nr_cleared_tags);
+ }
/* Now free the nodes we do not need anymore */
for (pathp = orig_pathp; pathp->node; pathp--) {
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
