Re: [patch] radix-tree: use indirect bit
On Mon, Aug 06, 2007 at 11:40:55AM -0700, Andrew Morton wrote: > On Thu, 2 Aug 2007 07:24:46 +0200 Nick Piggin <[EMAIL PROTECTED]> wrote: > > > 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. > > so.. we added 30 bytes of text to radix-tree.o for no purpose? I guess no functional purpose at this stage. But I do like this scheme better anyway, because it means that locked API users are never exposed to the direct/indirect bit. It's a bit variable... on powerpc, it _removed_ 22 bytes, and if I delete the extra BUG_ON that I introduced, then it removes 128 bytes. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch] radix-tree: use indirect bit
On Thu, 2 Aug 2007 07:24:46 +0200 Nick Piggin <[EMAIL PROTECTED]> wrote: > 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. so.. we added 30 bytes of text to radix-tree.o for no purpose? - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch] radix-tree: use indirect bit
On Thu, 2 Aug 2007 07:24:46 +0200 Nick Piggin [EMAIL PROTECTED] wrote: 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. so.. we added 30 bytes of text to radix-tree.o for no purpose? - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch] radix-tree: use indirect bit
On Mon, Aug 06, 2007 at 11:40:55AM -0700, Andrew Morton wrote: On Thu, 2 Aug 2007 07:24:46 +0200 Nick Piggin [EMAIL PROTECTED] wrote: 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. so.. we added 30 bytes of text to radix-tree.o for no purpose? I guess no functional purpose at this stage. But I do like this scheme better anyway, because it means that locked API users are never exposed to the direct/indirect bit. It's a bit variable... on powerpc, it _removed_ 22 bytes, and if I delete the extra BUG_ON that I introduced, then it removes 128 bytes. - To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [patch] radix-tree: use indirect bit
On Thu, 2007-08-02 at 07:24 +0200, Nick Piggin wrote: > 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 <[EMAIL PROTECTED]> Acked-by: Peter Zijlstra <[EMAIL PROTECTED]> > > Index: linux-2.6/include/linux/radix-tree.h > === > --- linux-2.6.orig/include/linux/radix-tree.h > +++ linux-2.6/include/linux/radix-tree.h > @@ -26,28 +26,31 @@ > #include > > /* > - * A direct pointer (root->rnode pointing directly to a data item, > - * rather than another radix_tree_node) is signalled by the low bit > - * set in the root->rnode pointer. > - * > - * In this case root->height is also NULL, but the direct pointer tests are > - * needed for RCU lookups when root->height is unreliable. > + * 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. > */ > -#define RADIX_TREE_DIRECT_PTR1 > +#define RADIX_TREE_INDIRECT_PTR 1 > +#define RADIX_TREE_RETRY ((void *)-1UL) > > -static inline void *radix_tree_ptr_to_direct(void *ptr) > +static inline void *radix_tree_ptr_to_indirect(void *ptr) > { > - return (void *)((unsigned long)ptr | RADIX_TREE_DIRECT_PTR); > + return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); > } > > -static inline void *radix_tree_direct_to_ptr(void *ptr) > +static inline void *radix_tree_indirect_to_ptr(void *ptr) > { > - return (void *)((unsigned long)ptr & ~RADIX_TREE_DIRECT_PTR); > + return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR); > } > > -static inline int radix_tree_is_direct_ptr(void *ptr) > +static inline int radix_tree_is_indirect_ptr(void *ptr) > { > - return (int)((unsigned long)ptr & RADIX_TREE_DIRECT_PTR); > + return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR); > } > > /*** radix-tree API starts here ***/ > @@ -130,7 +133,10 @@ do { > \ > */ > static inline void *radix_tree_deref_slot(void **pslot) > { > - return radix_tree_direct_to_ptr(*pslot); > + void *ret = *pslot; > + if (unlikely(radix_tree_is_indirect_ptr(ret))) > + ret = RADIX_TREE_RETRY; > + return ret; > } > /** > * radix_tree_replace_slot - replace item in a slot > @@ -142,10 +148,8 @@ static inline void *radix_tree_deref_slo > */ > static inline void radix_tree_replace_slot(void **pslot, void *item) > { > - BUG_ON(radix_tree_is_direct_ptr(item)); > - rcu_assign_pointer(*pslot, > - (void *)((unsigned long)item | > - ((unsigned long)*pslot & RADIX_TREE_DIRECT_PTR))); > + BUG_ON(radix_tree_is_indirect_ptr(item)); > + rcu_assign_pointer(*pslot, item); > } > > int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); > Index: linux-2.6/lib/radix-tree.c > === > --- linux-2.6.orig/lib/radix-tree.c > +++ linux-2.6/lib/radix-tree.c > @@ -104,7 +104,7 @@ radix_tree_node_alloc(struct radix_tree_ > rtp->nr--; > } > } > - BUG_ON(radix_tree_is_direct_ptr(ret)); > + BUG_ON(radix_tree_is_indirect_ptr(ret)); > return ret; > } > > @@ -240,7 +240,7 @@ static int radix_tree_extend(struct radi > return -ENOMEM; > > /* Increase the height. */ > - node->slots[0] = radix_tree_direct_to_ptr(root->rnode); > + node->slots[0] = radix_tree_indirect_to_ptr(root->rnode); > > /* Propagate the aggregated tag info into the new root */ > for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { > @@ -251,6 +251,7 @@ static int radix_tree_extend(struct radi > newheight = root->height+1; > node->height = newheight; > node->count = 1; > + node = radix_tree_ptr_to_indirect(node); > rcu_assign_pointer(root->rnode, node); > root->height = newheight; > } while (height > root->height); > @@ -274,7 +275,7 @@ int radix_tree_insert(struct radix_tree_ > int offset; > int error; > > - BUG_ON(radix_tree_is_direct_ptr(item)); > + BUG_ON(radix_tree_is_indirect_ptr(item)); >
Re: [patch] radix-tree: use indirect bit
On Thu, 2007-08-02 at 07:24 +0200, Nick Piggin wrote: 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 [EMAIL PROTECTED] Acked-by: Peter Zijlstra [EMAIL PROTECTED] Index: linux-2.6/include/linux/radix-tree.h === --- linux-2.6.orig/include/linux/radix-tree.h +++ linux-2.6/include/linux/radix-tree.h @@ -26,28 +26,31 @@ #include linux/rcupdate.h /* - * A direct pointer (root-rnode pointing directly to a data item, - * rather than another radix_tree_node) is signalled by the low bit - * set in the root-rnode pointer. - * - * In this case root-height is also NULL, but the direct pointer tests are - * needed for RCU lookups when root-height is unreliable. + * 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. */ -#define RADIX_TREE_DIRECT_PTR1 +#define RADIX_TREE_INDIRECT_PTR 1 +#define RADIX_TREE_RETRY ((void *)-1UL) -static inline void *radix_tree_ptr_to_direct(void *ptr) +static inline void *radix_tree_ptr_to_indirect(void *ptr) { - return (void *)((unsigned long)ptr | RADIX_TREE_DIRECT_PTR); + return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); } -static inline void *radix_tree_direct_to_ptr(void *ptr) +static inline void *radix_tree_indirect_to_ptr(void *ptr) { - return (void *)((unsigned long)ptr ~RADIX_TREE_DIRECT_PTR); + return (void *)((unsigned long)ptr ~RADIX_TREE_INDIRECT_PTR); } -static inline int radix_tree_is_direct_ptr(void *ptr) +static inline int radix_tree_is_indirect_ptr(void *ptr) { - return (int)((unsigned long)ptr RADIX_TREE_DIRECT_PTR); + return (int)((unsigned long)ptr RADIX_TREE_INDIRECT_PTR); } /*** radix-tree API starts here ***/ @@ -130,7 +133,10 @@ do { \ */ static inline void *radix_tree_deref_slot(void **pslot) { - return radix_tree_direct_to_ptr(*pslot); + void *ret = *pslot; + if (unlikely(radix_tree_is_indirect_ptr(ret))) + ret = RADIX_TREE_RETRY; + return ret; } /** * radix_tree_replace_slot - replace item in a slot @@ -142,10 +148,8 @@ static inline void *radix_tree_deref_slo */ static inline void radix_tree_replace_slot(void **pslot, void *item) { - BUG_ON(radix_tree_is_direct_ptr(item)); - rcu_assign_pointer(*pslot, - (void *)((unsigned long)item | - ((unsigned long)*pslot RADIX_TREE_DIRECT_PTR))); + BUG_ON(radix_tree_is_indirect_ptr(item)); + rcu_assign_pointer(*pslot, item); } int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); Index: linux-2.6/lib/radix-tree.c === --- linux-2.6.orig/lib/radix-tree.c +++ linux-2.6/lib/radix-tree.c @@ -104,7 +104,7 @@ radix_tree_node_alloc(struct radix_tree_ rtp-nr--; } } - BUG_ON(radix_tree_is_direct_ptr(ret)); + BUG_ON(radix_tree_is_indirect_ptr(ret)); return ret; } @@ -240,7 +240,7 @@ static int radix_tree_extend(struct radi return -ENOMEM; /* Increase the height. */ - node-slots[0] = radix_tree_direct_to_ptr(root-rnode); + node-slots[0] = radix_tree_indirect_to_ptr(root-rnode); /* Propagate the aggregated tag info into the new root */ for (tag = 0; tag RADIX_TREE_MAX_TAGS; tag++) { @@ -251,6 +251,7 @@ static int radix_tree_extend(struct radi newheight = root-height+1; node-height = newheight; node-count = 1; + node = radix_tree_ptr_to_indirect(node); rcu_assign_pointer(root-rnode, node); root-height = newheight; } while (height root-height); @@ -274,7 +275,7 @@ int radix_tree_insert(struct radix_tree_ int offset; int error; - BUG_ON(radix_tree_is_direct_ptr(item)); + BUG_ON(radix_tree_is_indirect_ptr(item)); /* Make sure the tree is high enough. */ if (index radix_tree_maxindex(root-height)) { @@ -283,7 +284,8 @@ int
[patch] 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 <[EMAIL PROTECTED]> Index: linux-2.6/include/linux/radix-tree.h === --- linux-2.6.orig/include/linux/radix-tree.h +++ linux-2.6/include/linux/radix-tree.h @@ -26,28 +26,31 @@ #include /* - * A direct pointer (root->rnode pointing directly to a data item, - * rather than another radix_tree_node) is signalled by the low bit - * set in the root->rnode pointer. - * - * In this case root->height is also NULL, but the direct pointer tests are - * needed for RCU lookups when root->height is unreliable. + * 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. */ -#define RADIX_TREE_DIRECT_PTR 1 +#define RADIX_TREE_INDIRECT_PTR1 +#define RADIX_TREE_RETRY ((void *)-1UL) -static inline void *radix_tree_ptr_to_direct(void *ptr) +static inline void *radix_tree_ptr_to_indirect(void *ptr) { - return (void *)((unsigned long)ptr | RADIX_TREE_DIRECT_PTR); + return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); } -static inline void *radix_tree_direct_to_ptr(void *ptr) +static inline void *radix_tree_indirect_to_ptr(void *ptr) { - return (void *)((unsigned long)ptr & ~RADIX_TREE_DIRECT_PTR); + return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR); } -static inline int radix_tree_is_direct_ptr(void *ptr) +static inline int radix_tree_is_indirect_ptr(void *ptr) { - return (int)((unsigned long)ptr & RADIX_TREE_DIRECT_PTR); + return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR); } /*** radix-tree API starts here ***/ @@ -130,7 +133,10 @@ do { \ */ static inline void *radix_tree_deref_slot(void **pslot) { - return radix_tree_direct_to_ptr(*pslot); + void *ret = *pslot; + if (unlikely(radix_tree_is_indirect_ptr(ret))) + ret = RADIX_TREE_RETRY; + return ret; } /** * radix_tree_replace_slot - replace item in a slot @@ -142,10 +148,8 @@ static inline void *radix_tree_deref_slo */ static inline void radix_tree_replace_slot(void **pslot, void *item) { - BUG_ON(radix_tree_is_direct_ptr(item)); - rcu_assign_pointer(*pslot, - (void *)((unsigned long)item | - ((unsigned long)*pslot & RADIX_TREE_DIRECT_PTR))); + BUG_ON(radix_tree_is_indirect_ptr(item)); + rcu_assign_pointer(*pslot, item); } int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); Index: linux-2.6/lib/radix-tree.c === --- linux-2.6.orig/lib/radix-tree.c +++ linux-2.6/lib/radix-tree.c @@ -104,7 +104,7 @@ radix_tree_node_alloc(struct radix_tree_ rtp->nr--; } } - BUG_ON(radix_tree_is_direct_ptr(ret)); + BUG_ON(radix_tree_is_indirect_ptr(ret)); return ret; } @@ -240,7 +240,7 @@ static int radix_tree_extend(struct radi return -ENOMEM; /* Increase the height. */ - node->slots[0] = radix_tree_direct_to_ptr(root->rnode); + node->slots[0] = radix_tree_indirect_to_ptr(root->rnode); /* Propagate the aggregated tag info into the new root */ for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) { @@ -251,6 +251,7 @@ static int radix_tree_extend(struct radi newheight = root->height+1; node->height = newheight; node->count = 1; + node = radix_tree_ptr_to_indirect(node); rcu_assign_pointer(root->rnode, node); root->height = newheight; } while (height > root->height); @@ -274,7 +275,7 @@ int radix_tree_insert(struct radix_tree_ int offset; int error; - BUG_ON(radix_tree_is_direct_ptr(item)); + BUG_ON(radix_tree_is_indirect_ptr(item)); /* Make sure the tree is high enough. */ if (index > radix_tree_maxindex(root->height)) { @@ -283,7 +284,8 @@ int radix_tree_insert(struct radix_tree_ return error; } - slot = root->rnode; + slot =
[patch] 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 [EMAIL PROTECTED] Index: linux-2.6/include/linux/radix-tree.h === --- linux-2.6.orig/include/linux/radix-tree.h +++ linux-2.6/include/linux/radix-tree.h @@ -26,28 +26,31 @@ #include linux/rcupdate.h /* - * A direct pointer (root-rnode pointing directly to a data item, - * rather than another radix_tree_node) is signalled by the low bit - * set in the root-rnode pointer. - * - * In this case root-height is also NULL, but the direct pointer tests are - * needed for RCU lookups when root-height is unreliable. + * 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. */ -#define RADIX_TREE_DIRECT_PTR 1 +#define RADIX_TREE_INDIRECT_PTR1 +#define RADIX_TREE_RETRY ((void *)-1UL) -static inline void *radix_tree_ptr_to_direct(void *ptr) +static inline void *radix_tree_ptr_to_indirect(void *ptr) { - return (void *)((unsigned long)ptr | RADIX_TREE_DIRECT_PTR); + return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR); } -static inline void *radix_tree_direct_to_ptr(void *ptr) +static inline void *radix_tree_indirect_to_ptr(void *ptr) { - return (void *)((unsigned long)ptr ~RADIX_TREE_DIRECT_PTR); + return (void *)((unsigned long)ptr ~RADIX_TREE_INDIRECT_PTR); } -static inline int radix_tree_is_direct_ptr(void *ptr) +static inline int radix_tree_is_indirect_ptr(void *ptr) { - return (int)((unsigned long)ptr RADIX_TREE_DIRECT_PTR); + return (int)((unsigned long)ptr RADIX_TREE_INDIRECT_PTR); } /*** radix-tree API starts here ***/ @@ -130,7 +133,10 @@ do { \ */ static inline void *radix_tree_deref_slot(void **pslot) { - return radix_tree_direct_to_ptr(*pslot); + void *ret = *pslot; + if (unlikely(radix_tree_is_indirect_ptr(ret))) + ret = RADIX_TREE_RETRY; + return ret; } /** * radix_tree_replace_slot - replace item in a slot @@ -142,10 +148,8 @@ static inline void *radix_tree_deref_slo */ static inline void radix_tree_replace_slot(void **pslot, void *item) { - BUG_ON(radix_tree_is_direct_ptr(item)); - rcu_assign_pointer(*pslot, - (void *)((unsigned long)item | - ((unsigned long)*pslot RADIX_TREE_DIRECT_PTR))); + BUG_ON(radix_tree_is_indirect_ptr(item)); + rcu_assign_pointer(*pslot, item); } int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); Index: linux-2.6/lib/radix-tree.c === --- linux-2.6.orig/lib/radix-tree.c +++ linux-2.6/lib/radix-tree.c @@ -104,7 +104,7 @@ radix_tree_node_alloc(struct radix_tree_ rtp-nr--; } } - BUG_ON(radix_tree_is_direct_ptr(ret)); + BUG_ON(radix_tree_is_indirect_ptr(ret)); return ret; } @@ -240,7 +240,7 @@ static int radix_tree_extend(struct radi return -ENOMEM; /* Increase the height. */ - node-slots[0] = radix_tree_direct_to_ptr(root-rnode); + node-slots[0] = radix_tree_indirect_to_ptr(root-rnode); /* Propagate the aggregated tag info into the new root */ for (tag = 0; tag RADIX_TREE_MAX_TAGS; tag++) { @@ -251,6 +251,7 @@ static int radix_tree_extend(struct radi newheight = root-height+1; node-height = newheight; node-count = 1; + node = radix_tree_ptr_to_indirect(node); rcu_assign_pointer(root-rnode, node); root-height = newheight; } while (height root-height); @@ -274,7 +275,7 @@ int radix_tree_insert(struct radix_tree_ int offset; int error; - BUG_ON(radix_tree_is_direct_ptr(item)); + BUG_ON(radix_tree_is_indirect_ptr(item)); /* Make sure the tree is high enough. */ if (index radix_tree_maxindex(root-height)) { @@ -283,7 +284,8 @@ int radix_tree_insert(struct radix_tree_ return error; } - slot = root-rnode; + slot =