[PATCH v6 08/71] Maple Tree: Add new data structure
Vasily Gorbik
gor at linux.ibm.com
Sat Feb 26 17:11:52 PST 2022
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.
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 */
}
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