Re: [PATCH 2/3] radix-tree: make 'indirect' bit available to exception entries.

From: Ross Zwisler
Date: Tue Mar 01 2016 - 17:00:00 EST


On Mon, Feb 29, 2016 at 02:41:55PM +0000, Wilcox, Matthew R wrote:
> So based on the bottom two bits, we can tell what this entry is:
>
> 00 - data pointer
> 01 - indirect entry (pointer to another level of the radix tree)
> 10 - exceptional entry
> 11 - locked exceptional entry
>
> I was concerned that this patch would clash with the support for multi-order
> entries in the radix tree, but after some thought, I now believe that it
> doesn't. The multi-order entries changes permit finding data pointers or
> exceptional entries in the tree where before only indirect entries could be
> found, but with the changes to radix_tree_is_indirect_ptr below, everything
> should work fine.

Yep, this seems workable to me.

> -----Original Message-----
> From: NeilBrown [mailto:neilb@xxxxxxxx]
> Sent: Saturday, February 27, 2016 9:09 PM
> To: Ross Zwisler; Wilcox, Matthew R; Andrew Morton; Jan Kara
> Cc: linux-kernel@xxxxxxxxxxxxxxx; linux-fsdevel@xxxxxxxxxxxxxxx; linux-mm@xxxxxxxxx
> Subject: [PATCH 2/3] radix-tree: make 'indirect' bit available to exception entries.
>
> A pointer to a radix_tree_node will always have the 'exception'
> bit cleared, so if the exception bit is set the value cannot
> be an indirect pointer. Thus it is safe to make the 'indirect bit'
> available to store extra information in exception entries.
>
> This patch adds a 'PTR_MASK' and a value is only treated as
> an indirect (pointer) entry the 2 ls-bits are '01'.
>
> The change in radix-tree.c ensures the stored value still looks like an
> indirect pointer, and saves a load as well.
>
> We could swap the two bits and so keep all the exectional bits contigious.
> But I have other plans for that bit....
>
> Signed-off-by: NeilBrown <neilb@xxxxxxxx>
> ---
> include/linux/radix-tree.h | 11 +++++++++--
> lib/radix-tree.c | 2 +-
> 2 files changed, 10 insertions(+), 3 deletions(-)
>
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 968150ab8a1c..450c12b546b7 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -40,8 +40,13 @@
> * Indirect pointer in fact is also used to tag the last pointer of a node
> * when it is shrunk, before we rcu free the node. See shrink code for
> * details.
> + *
> + * To allow an exception entry to only lose one bit, we ignore
> + * the INDIRECT bit when the exception bit is set. So an entry is
> + * indirect if the least significant 2 bits are 01.
> */
> #define RADIX_TREE_INDIRECT_PTR 1
> +#define RADIX_TREE_INDIRECT_MASK 3
> /*
> * A common use of the radix tree is to store pointers to struct pages;
> * but shmem/tmpfs needs also to store swap entries in the same tree:
> @@ -53,7 +58,8 @@
>
> static inline int radix_tree_is_indirect_ptr(void *ptr)
> {
> - return (int)((unsigned long)ptr & RADIX_TREE_INDIRECT_PTR);
> + return ((unsigned long)ptr & RADIX_TREE_INDIRECT_MASK)
> + == RADIX_TREE_INDIRECT_PTR;
> }
>
> /*** radix-tree API starts here ***/
> @@ -221,7 +227,8 @@ static inline void *radix_tree_deref_slot_protected(void **pslot,
> */
> static inline int radix_tree_deref_retry(void *arg)
> {
> - return unlikely((unsigned long)arg & RADIX_TREE_INDIRECT_PTR);
> + return unlikely(((unsigned long)arg & RADIX_TREE_INDIRECT_MASK)
> + == RADIX_TREE_INDIRECT_PTR);
> }
>
> /**
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 6b79e9026e24..37d4643ab5c0 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -1305,7 +1305,7 @@ static inline void radix_tree_shrink(struct radix_tree_root *root)
> * to force callers to retry.
> */
> if (root->height == 0)
> - *((unsigned long *)&to_free->slots[0]) |=
> + *((unsigned long *)&to_free->slots[0]) =
> RADIX_TREE_INDIRECT_PTR;
>
> radix_tree_node_free(to_free);
>
>