aboutsummaryrefslogtreecommitdiffstats
path: root/lib/radix-tree.c
diff options
context:
space:
mode:
authorNick Piggin <nickpiggin@yahoo.com.au>2006-01-08 04:01:41 -0500
committerLinus Torvalds <torvalds@g5.osdl.org>2006-01-08 23:13:41 -0500
commitd5274261ea46f0aae93820fe36628249120d2f75 (patch)
treee95c41295270c55ef27a3534894f066f31719ecc /lib/radix-tree.c
parent6e954b9e90c3a7157c0c1457dd3919e2a1345d23 (diff)
[PATCH] radix tree: early termination of tag clearing
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. For example, if a tag is simply not set in the deleted item, nor anywhere up the tree, radix_tree_delete() would attempt to clear it up the entire height of the tree. Also, tag_set() was 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 <npiggin@suse.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'lib/radix-tree.c')
-rw-r--r--lib/radix-tree.c40
1 files changed, 23 insertions, 17 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1403e2c8bb3e..336852f23592 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -137,18 +137,17 @@ out:
137 137
138static inline void tag_set(struct radix_tree_node *node, int tag, int offset) 138static inline void tag_set(struct radix_tree_node *node, int tag, int offset)
139{ 139{
140 if (!test_bit(offset, &node->tags[tag][0])) 140 __set_bit(offset, node->tags[tag]);
141 __set_bit(offset, &node->tags[tag][0]);
142} 141}
143 142
144static inline void tag_clear(struct radix_tree_node *node, int tag, int offset) 143static inline void tag_clear(struct radix_tree_node *node, int tag, int offset)
145{ 144{
146 __clear_bit(offset, &node->tags[tag][0]); 145 __clear_bit(offset, node->tags[tag]);
147} 146}
148 147
149static inline int tag_get(struct radix_tree_node *node, int tag, int offset) 148static inline int tag_get(struct radix_tree_node *node, int tag, int offset)
150{ 149{
151 return test_bit(offset, &node->tags[tag][0]); 150 return test_bit(offset, node->tags[tag]);
152} 151}
153 152
154/* 153/*
@@ -375,7 +374,8 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
375 int offset; 374 int offset;
376 375
377 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 376 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
378 tag_set(slot, tag, offset); 377 if (!tag_get(slot, tag, offset))
378 tag_set(slot, tag, offset);
379 slot = slot->slots[offset]; 379 slot = slot->slots[offset];
380 BUG_ON(slot == NULL); 380 BUG_ON(slot == NULL);
381 shift -= RADIX_TREE_MAP_SHIFT; 381 shift -= RADIX_TREE_MAP_SHIFT;
@@ -435,6 +435,8 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
435 goto out; 435 goto out;
436 436
437 do { 437 do {
438 if (!tag_get(pathp->node, tag, pathp->offset))
439 goto out;
438 tag_clear(pathp->node, tag, pathp->offset); 440 tag_clear(pathp->node, tag, pathp->offset);
439 if (any_tag_set(pathp->node, tag)) 441 if (any_tag_set(pathp->node, tag))
440 goto out; 442 goto out;
@@ -695,6 +697,8 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
695 void *ret = NULL; 697 void *ret = NULL;
696 char tags[RADIX_TREE_TAGS]; 698 char tags[RADIX_TREE_TAGS];
697 int nr_cleared_tags; 699 int nr_cleared_tags;
700 int tag;
701 int offset;
698 702
699 height = root->height; 703 height = root->height;
700 if (index > radix_tree_maxindex(height)) 704 if (index > radix_tree_maxindex(height))
@@ -705,16 +709,14 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
705 slot = root->rnode; 709 slot = root->rnode;
706 710
707 for ( ; height > 0; height--) { 711 for ( ; height > 0; height--) {
708 int offset;
709
710 if (slot == NULL) 712 if (slot == NULL)
711 goto out; 713 goto out;
712 714
715 pathp++;
713 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 716 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
714 pathp[1].offset = offset; 717 pathp->offset = offset;
715 pathp[1].node = slot; 718 pathp->node = slot;
716 slot = slot->slots[offset]; 719 slot = slot->slots[offset];
717 pathp++;
718 shift -= RADIX_TREE_MAP_SHIFT; 720 shift -= RADIX_TREE_MAP_SHIFT;
719 } 721 }
720 722
@@ -727,24 +729,28 @@ void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
727 /* 729 /*
728 * Clear all tags associated with the just-deleted item 730 * Clear all tags associated with the just-deleted item
729 */ 731 */
730 memset(tags, 0, sizeof(tags)); 732 nr_cleared_tags = 0;
731 do { 733 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
732 int tag; 734 if (tag_get(pathp->node, tag, pathp->offset)) {
735 tag_clear(pathp->node, tag, pathp->offset);
736 tags[tag] = 0;
737 nr_cleared_tags++;
738 } else
739 tags[tag] = 1;
740 }
733 741
734 nr_cleared_tags = RADIX_TREE_TAGS; 742 for (pathp--; nr_cleared_tags && pathp->node; pathp--) {
735 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) { 743 for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
736 if (tags[tag]) 744 if (tags[tag])
737 continue; 745 continue;
738 746
739 tag_clear(pathp->node, tag, pathp->offset); 747 tag_clear(pathp->node, tag, pathp->offset);
740
741 if (any_tag_set(pathp->node, tag)) { 748 if (any_tag_set(pathp->node, tag)) {
742 tags[tag] = 1; 749 tags[tag] = 1;
743 nr_cleared_tags--; 750 nr_cleared_tags--;
744 } 751 }
745 } 752 }
746 pathp--; 753 }
747 } while (pathp->node && nr_cleared_tags);
748 754
749 /* Now free the nodes we do not need anymore */ 755 /* Now free the nodes we do not need anymore */
750 for (pathp = orig_pathp; pathp->node; pathp--) { 756 for (pathp = orig_pathp; pathp->node; pathp--) {