Re: [PATCH v6 08/71] Maple Tree: Add new data structure

[Liam Howlett <liam.howlett@oracle.com>]

* Vasily Gorbik <gor@linux.ibm.com> [220226 20:12]:
> Hi Liam,
> 
> there is an endianness issue with maple_metadata. This is broken on
> all big endian architectures. Tests are crashing. See potential fixup
> below. Feel free to apply it or fix the issue in your own way. This does
> not resolve all the issues with the patch series though.

The endianness isn't what's causing the issues.  The slots hold a
pointer.  Either we can use the entire slot or none of the slot
space.  You are just moving the metatdata around in the last slot.

> 
> With current definition of struct maple_range_64 on big endian systems
> metadata end and gap fields are aligned with the most significant bytes
> of slot[15], rather than least significant.
> 
> (gdb) ptype /o struct maple_range_64
> /* offset    |  size */  type = struct maple_range_64 {
> /*    0      |     8 */    struct maple_pnode *parent;
> /*    8      |   120 */    unsigned long pivot[15];
> /*  128      |   128 */    union {
> /*               128 */        void *slot[16];
> /*               128 */        struct {
> /*  128      |   120 */            void *pad[15];
> /*  248      |     2 */            struct maple_metadata {
> /*  248      |     1 */                unsigned char end;
> /*  249      |     1 */                unsigned char gap;
> 
>                                        /* total size (bytes):    2 */
>                                    } meta;
> /* XXX  6-byte padding  */
> 
>                                    /* total size (bytes):  128 */
>                                };
> 
>                                /* total size (bytes):  128 */
>                            };
> 
>                            /* total size (bytes):  256 */
>                          }
> 

You may have been confused about my comment, which I believe is
outdated, that talks about maple_arange_64, not maple_range_64.  I added
maple_range_64 metadata and use the previous pivot to see if the slot
contains data or not. If piv[14] == 0 or mas->max means we can use the
slot for metadata.

> Assuming we don't want to end up with smth like this in a code which
> otherwise relies on shifts and endianness independent.
> 
>  #if defined(__BYTE_ORDER) ? __BYTE_ORDER == __LITTLE_ENDIAN : defined(__LITTLE_ENDIAN)
> 
>  struct maple_metadata {
>         unsigned char end;
>         unsigned char gap;
>  };
> 
>  #else
> 
>  struct maple_metadata {
>         unsigned char unused[6];
>         unsigned char gap;
>         unsigned char end;
>  };
> 
>  #endif
> 
> rewrite node matadata access in endianness independent shifts based
> approach as well.
> 
> Signed-off-by: Vasily Gorbik <gor@linux.ibm.com>
> ---
>  include/linux/maple_tree.h | 33 ++++++++++++++--------------
>  lib/maple_tree.c           | 45 +++++++++++++++++++++-----------------
>  2 files changed, 41 insertions(+), 37 deletions(-)
> 
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index e808794e06a5..e0c9f356ba4e 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -76,21 +76,6 @@ typedef struct maple_enode *maple_enode; /* encoded node */
>  typedef struct maple_pnode *maple_pnode; /* parent node */
>  
>  
> -/*
> - * The node->meta is currently only supported in allocation range 64 (arange_64)
> - * node type.  As a result of tracking gaps, there is a small area that is not
> - * used for data storage in this node type.  This area is reused to store
> - * metadata related to the node itself including the data end and the largest
> - * gap location.  This metadata is used to optimize the gap updating code and in
> - * reverse searching for gaps or any other code that needs to find the end of
> - * the data.
> - */
> -struct maple_metadata {
> -	unsigned char end;
> -	unsigned char gap;
> -
> -};
> -
>  /*
>   * Leaf nodes do not store pointers to nodes, they store user data.  Users may
>   * store almost any bit pattern.  As noted above, the optimisation of storing an
> @@ -110,8 +95,22 @@ struct maple_metadata {
>   * subtree with an entry attached to the value whereas keys are unique to a
>   * specific position of a B-tree.  Pivot values are inclusive of the slot with
>   * the same index.
> + *
> + * The node->meta is currently only supported in allocation range 64 (arange_64)
> + * node type.  As a result of tracking gaps, there is a small area that is not
> + * used for data storage in this node type.  This area is reused to store
> + * metadata related to the node itself including the data end and the largest
> + * gap location.  This metadata is used to optimize the gap updating code and in
> + * reverse searching for gaps or any other code that needs to find the end of
> + * the data.
>   */
>  
> +#define MN_META_MASK		0xFFFF
> +#define MN_META_GAP_MASK	0xFF00
> +#define MN_META_END_MASK	0x00FF
> +#define MN_META_GAP_SHIFT	8
> +#define MN_META_END_SHIFT	0
> +
>  struct maple_range_64 {
>  	struct maple_pnode *parent;
>  	unsigned long pivot[MAPLE_RANGE64_SLOTS - 1];
> @@ -119,7 +118,7 @@ struct maple_range_64 {
>  		void __rcu *slot[MAPLE_RANGE64_SLOTS];
>  		struct {
>  			void __rcu *pad[MAPLE_RANGE64_SLOTS - 1];
> -			struct maple_metadata meta;
> +			unsigned long meta;
>  		};
>  	};
>  };
> @@ -138,7 +137,7 @@ struct maple_arange_64 {
>  	unsigned long pivot[MAPLE_ARANGE64_SLOTS - 1];
>  	void __rcu *slot[MAPLE_ARANGE64_SLOTS];
>  	unsigned long gap[MAPLE_ARANGE64_SLOTS];
> -	struct maple_metadata meta;
> +	unsigned long meta;
>  };
>  
>  struct maple_alloc {
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 7ebb34964c68..02be5a5314de 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -868,15 +868,22 @@ static inline void *mas_root_locked(struct ma_state *mas)
>  	return mt_root_locked(mas->tree);
>  }
>  
> -static inline struct maple_metadata *ma_meta(struct maple_node *mn,
> -					     enum maple_type mt)
> +static inline unsigned long ma_get_meta_raw(struct maple_node *mn,
> +					    enum maple_type mt)
>  {
> -	switch (mt) {
> -	case maple_arange_64:
> -		return &mn->ma64.meta;
> -	default:
> -		return &mn->mr64.meta;
> -	}
> +	if (mt == maple_arange_64)
> +		return mn->ma64.meta;
> +	else
> +		return mn->mr64.meta;
> +}
> +
> +static inline void ma_set_meta_raw(struct maple_node *mn, enum maple_type mt,
> +				   unsigned long meta)
> +{
> +	if (mt == maple_arange_64)
> +		mn->ma64.meta = meta;
> +	else
> +		mn->mr64.meta = meta;
>  }
>  
>  /*
> @@ -889,10 +896,10 @@ static inline struct maple_metadata *ma_meta(struct maple_node *mn,
>  static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
>  			       unsigned char offset, unsigned char end)
>  {
> -	struct maple_metadata *meta = ma_meta(mn, mt);
> +	unsigned long mnm = ma_get_meta_raw(mn, mt) & ~MN_META_MASK;
>  
> -	meta->gap = offset;
> -	meta->end = end;
> +	mnm |= offset << MN_META_GAP_SHIFT | end << MN_META_END_SHIFT;
> +	ma_set_meta_raw(mn, mt, mnm);
>  }
>  
>  /*
> @@ -903,9 +910,7 @@ static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
>  static inline unsigned char ma_meta_end(struct maple_node *mn,
>  					enum maple_type mt)
>  {
> -	struct maple_metadata *meta = ma_meta(mn, mt);
> -
> -	return meta->end;
> +	return (ma_get_meta_raw(mn, mt) & MN_META_END_MASK) >> MN_META_END_SHIFT;
>  }
>  
>  /*
> @@ -916,8 +921,7 @@ static inline unsigned char ma_meta_end(struct maple_node *mn,
>  static inline unsigned char ma_meta_gap(struct maple_node *mn,
>  					enum maple_type mt)
>  {
> -
> -	return mn->ma64.meta.gap;
> +	return (ma_get_meta_raw(mn, mt) & MN_META_GAP_MASK) >> MN_META_GAP_SHIFT;
>  }
>  
>  /*
> @@ -929,10 +933,9 @@ static inline unsigned char ma_meta_gap(struct maple_node *mn,
>  static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt,
>  				   unsigned char offset)
>  {
> +	unsigned long mnm = ma_get_meta_raw(mn, mt) & ~MN_META_GAP_MASK;
>  
> -	struct maple_metadata *meta = ma_meta(mn, mt);
> -
> -	meta->gap = offset;
> +	ma_set_meta_raw(mn, mt, mnm | offset << MN_META_GAP_SHIFT);
>  }
>  
>  /*
> @@ -6590,7 +6593,9 @@ void mt_dump_arange64(const struct maple_tree *mt, void *entry,
>  	pr_cont(" contents: ");
>  	for (i = 0; i < MAPLE_ARANGE64_SLOTS; i++)
>  		pr_cont("%lu ", node->gap[i]);
> -	pr_cont("| %02X %02X| ", node->meta.end, node->meta.gap);
> +	pr_cont("| %02lX %02lX| ",
> +		(node->meta & MN_META_END_MASK) >> MN_META_END_SHIFT,
> +		(node->meta & MN_META_GAP_MASK) >> MN_META_GAP_SHIFT);
>  	for (i = 0; i < MAPLE_ARANGE64_SLOTS - 1; i++)
>  		pr_cont(MA_PTR" %lu ", node->slot[i], node->pivot[i]);
>  	pr_cont(MA_PTR"\n", node->slot[i]);
> -- 
> 2.35.1
> 
>