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

[Ross Zwisler]

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);
> 
>