[PATCH v6 08/71] Maple Tree: Add new data structure
Liam Howlett
liam.howlett at oracle.com
Mon Feb 28 06:36:40 PST 2022
* Vasily Gorbik <gor at 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 at 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
>
>
More information about the maple-tree
mailing list