aboutsummaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorNick Piggin <npiggin@suse.de>2007-10-16 04:24:42 -0400
committerLinus Torvalds <torvalds@woody.linux-foundation.org>2007-10-16 12:42:53 -0400
commitc0bc9875b701c588e448302d41181995c21e8040 (patch)
treec320855d4c04bd51ded6b4888bc5895ab539165f /include
parentb55ed816235cf41c29159d22a4cdeec7deb5821c (diff)
radix-tree: use indirect bit
Rather than sign direct radix-tree pointers with a special bit, sign the indirect one that hangs off the root. This means that, given a lookup_slot operation, the invalid result will be differentiated from the valid (previously, valid results could have the bit either set or clear). This does not affect slot lookups which occur under lock -- they can never return an invalid result. Is needed in future for lockless pagecache. Signed-off-by: Nick Piggin <npiggin@suse.de> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Hugh Dickins <hugh@veritas.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'include')
-rw-r--r--include/linux/radix-tree.h38
1 files changed, 21 insertions, 17 deletions
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 430e4a8c1382..b6116b4445c7 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -26,28 +26,31 @@
26#include <linux/rcupdate.h> 26#include <linux/rcupdate.h>
27 27
28/* 28/*
29 * A direct pointer (root->rnode pointing directly to a data item, 29 * An indirect pointer (root->rnode pointing to a radix_tree_node, rather
30 * rather than another radix_tree_node) is signalled by the low bit 30 * than a data item) is signalled by the low bit set in the root->rnode
31 * set in the root->rnode pointer. 31 * pointer.
32 * 32 *
33 * In this case root->height is also NULL, but the direct pointer tests are 33 * In this case root->height is > 0, but the indirect pointer tests are
34 * needed for RCU lookups when root->height is unreliable. 34 * needed for RCU lookups (because root->height is unreliable). The only
35 * time callers need worry about this is when doing a lookup_slot under
36 * RCU.
35 */ 37 */
36#define RADIX_TREE_DIRECT_PTR 1 38#define RADIX_TREE_INDIRECT_PTR 1
39#define RADIX_TREE_RETRY ((void *)-1UL)
37 40
38static inline void *radix_tree_ptr_to_direct(void *ptr) 41static inline void *radix_tree_ptr_to_indirect(void *ptr)
39{ 42{
40 return (void *)((unsigned long)ptr | RADIX_TREE_DIRECT_PTR); 43 return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
41} 44}
42 45
43static inline void *radix_tree_direct_to_ptr(void *ptr) 46static inline void *radix_tree_indirect_to_ptr(void *ptr)
44{ 47{
45 return (void *)((unsigned long)ptr & ~RADIX_TREE_DIRECT_PTR); 48 return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
46} 49}
47 50
48static inline int radix_tree_is_direct_ptr(void *ptr) 51static inline int radix_tree_is_indirect_ptr(void *ptr)
49{ 52{
50 return (int)((unsigned long)ptr & RADIX_TREE_DIRECT_PTR); 53 return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
51} 54}
52 55
53/*** radix-tree API starts here ***/ 56/*** radix-tree API starts here ***/
@@ -130,7 +133,10 @@ do { \
130 */ 133 */
131static inline void *radix_tree_deref_slot(void **pslot) 134static inline void *radix_tree_deref_slot(void **pslot)
132{ 135{
133 return radix_tree_direct_to_ptr(*pslot); 136 void *ret = *pslot;
137 if (unlikely(radix_tree_is_indirect_ptr(ret)))
138 ret = RADIX_TREE_RETRY;
139 return ret;
134} 140}
135/** 141/**
136 * radix_tree_replace_slot - replace item in a slot 142 * radix_tree_replace_slot - replace item in a slot
@@ -142,10 +148,8 @@ static inline void *radix_tree_deref_slot(void **pslot)
142 */ 148 */
143static inline void radix_tree_replace_slot(void **pslot, void *item) 149static inline void radix_tree_replace_slot(void **pslot, void *item)
144{ 150{
145 BUG_ON(radix_tree_is_direct_ptr(item)); 151 BUG_ON(radix_tree_is_indirect_ptr(item));
146 rcu_assign_pointer(*pslot, 152 rcu_assign_pointer(*pslot, item);
147 (void *)((unsigned long)item |
148 ((unsigned long)*pslot & RADIX_TREE_DIRECT_PTR)));
149} 153}
150 154
151int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); 155int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);