aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorMatthew Wilcox <willy@linux.intel.com>2016-05-20 20:02:17 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2016-05-20 20:58:30 -0400
commitafe0e395b6d1817fa5393f1ad6fcbf71406b016d (patch)
tree9b455efe13df6db7997f8a56602c4d93bf7dc4d2 /lib
parent4f3755d1ae3cd856a5c7da3dea12cced8dc51fbf (diff)
radix-tree: fix several shrinking bugs with multiorder entries
Setting the indirect bit on the user data entry used to be unambiguous because the tree walking code knew not to expect internal nodes in the last level of the tree. Multiorder entries can appear at any level of the tree, and a leaf with the indirect bit set is indistinguishable from a pointer to a node. Introduce a special entry (RADIX_TREE_RETRY) which is neither a valid user entry, nor a valid pointer to a node. The radix_tree_deref_retry() function continues to work the same way, but tree walking code can distinguish it from a pointer to a node. Also fix the condition for setting slot->parent to NULL; it does not matter what height the tree is, it only matters whether slot is an indirect pointer. Move this code above the comment which is referring to the assignment to root->rnode. Also fix the condition for preventing the tree from shrinking to a single entry if it's a multiorder entry. Add a test-case to the test suite that checks that the tree goes back down to its original height after an item is inserted & deleted from a higher index in the tree. Signed-off-by: Matthew Wilcox <willy@linux.intel.com> Reviewed-by: Ross Zwisler <ross.zwisler@linux.intel.com> Cc: Konstantin Khlebnikov <koct9i@gmail.com> Cc: Kirill Shutemov <kirill.shutemov@linux.intel.com> Cc: Jan Kara <jack@suse.com> Cc: Neil Brown <neilb@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/radix-tree.c23
1 files changed, 12 insertions, 11 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index f13ddbba8ace..a1ba41730071 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -80,6 +80,8 @@ static inline void *indirect_to_ptr(void *ptr)
80 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR); 80 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
81} 81}
82 82
83#define RADIX_TREE_RETRY ptr_to_indirect(NULL)
84
83#ifdef CONFIG_RADIX_TREE_MULTIORDER 85#ifdef CONFIG_RADIX_TREE_MULTIORDER
84/* Sibling slots point directly to another slot in the same node */ 86/* Sibling slots point directly to another slot in the same node */
85static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node) 87static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node)
@@ -1443,6 +1445,14 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
1443 slot = to_free->slots[0]; 1445 slot = to_free->slots[0];
1444 if (!slot) 1446 if (!slot)
1445 break; 1447 break;
1448 if (!radix_tree_is_indirect_ptr(slot) && (root->height > 1))
1449 break;
1450
1451 if (radix_tree_is_indirect_ptr(slot)) {
1452 slot = indirect_to_ptr(slot);
1453 slot->parent = NULL;
1454 slot = ptr_to_indirect(slot);
1455 }
1446 1456
1447 /* 1457 /*
1448 * We don't need rcu_assign_pointer(), since we are simply 1458 * We don't need rcu_assign_pointer(), since we are simply
@@ -1451,14 +1461,6 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
1451 * (to_free->slots[0]), it will be safe to dereference the new 1461 * (to_free->slots[0]), it will be safe to dereference the new
1452 * one (root->rnode) as far as dependent read barriers go. 1462 * one (root->rnode) as far as dependent read barriers go.
1453 */ 1463 */
1454 if (root->height > 1) {
1455 if (!radix_tree_is_indirect_ptr(slot))
1456 break;
1457
1458 slot = indirect_to_ptr(slot);
1459 slot->parent = NULL;
1460 slot = ptr_to_indirect(slot);
1461 }
1462 root->rnode = slot; 1464 root->rnode = slot;
1463 root->height--; 1465 root->height--;
1464 1466
@@ -1480,9 +1482,8 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
1480 * also results in a stale slot). So tag the slot as indirect 1482 * also results in a stale slot). So tag the slot as indirect
1481 * to force callers to retry. 1483 * to force callers to retry.
1482 */ 1484 */
1483 if (root->height == 0) 1485 if (!radix_tree_is_indirect_ptr(slot))
1484 *((unsigned long *)&to_free->slots[0]) |= 1486 to_free->slots[0] = RADIX_TREE_RETRY;
1485 RADIX_TREE_INDIRECT_PTR;
1486 1487
1487 radix_tree_node_free(to_free); 1488 radix_tree_node_free(to_free);
1488 } 1489 }