From 04b40c0ba90a9c1b4a06386be95c4b5c6d58bc03 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 18 Mar 2019 15:57:30 -0400 Subject: [PATCH] maple_tree: typedef maple_enode for encoded node. Use the compiler to check if an encoded node or a regular node is used Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 15 ++-- lib/maple_tree.c | 147 +++++++++++++++++++------------------ 2 files changed, 84 insertions(+), 78 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index f6ac40a87f65..0dc1c5e5da86 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -41,6 +41,7 @@ /* Need to do corresponding calculations for 32-bit kernels */ #endif +typedef struct maple_enode *maple_enode; // encoded node. typedef struct maple_pnode *maple_pnode; // parent node. /* * We can be more cache-efficient if we interleave pivots and slots. @@ -192,8 +193,8 @@ static inline bool mtree_empty(const struct maple_tree *mt) } struct ma_cp { - struct maple_node *src; - struct maple_node *dst; + struct maple_enode *src; + struct maple_enode *dst; unsigned char src_start; unsigned char src_end; unsigned char dst_start; @@ -215,7 +216,7 @@ struct ma_state { struct maple_tree *tree; /* The tree we're operating in */ unsigned long index; /* The index we're operating on */ unsigned long last; /* The last index we're operating on */ - struct maple_node *node; /* The node containing this entry */ + struct maple_enode *node; /* The node containing this entry */ unsigned long min; /* The minimum index of this node */ unsigned long max; /* The maximum index of this node */ struct maple_node *alloc; /* Allocated nodes for this operation */ @@ -236,10 +237,10 @@ struct ma_state { * to resolve the error, the walk would have to be restarted from the * top of the tree as the tree may have been modified. */ -#define MAS_START ((struct maple_node *)1UL) -#define MAS_ROOT ((struct maple_node *)5UL) -#define MAS_NONE ((struct maple_node *)9UL) -#define MA_ERROR(err) ((struct maple_node *)(((unsigned long)err << 2) | 2UL)) +#define MAS_START ((struct maple_enode *)1UL) +#define MAS_ROOT ((struct maple_enode *)5UL) +#define MAS_NONE ((struct maple_enode *)9UL) +#define MA_ERROR(err) ((struct maple_enode *)(((unsigned long)err << 2) | 2UL)) #define MA_STATE(name, mt, first, end) \ struct ma_state name = { \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 980bba8b2554..49980c400c22 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -12,7 +12,8 @@ #include #define MA_ROOT_PARENT 1 -#define ma_parent_ptr(x) ((struct maple_pnode*)x) +#define ma_parent_ptr(x) ((struct maple_pnode*)(x)) +#define ma_mnode_ptr(x) ((struct maple_node*)(x)) static struct kmem_cache *maple_node_cache; unsigned long mt_max[] = { @@ -89,12 +90,12 @@ static void mt_free(struct maple_node *node) call_rcu(&node->rcu, mt_free_rcu); } -static inline enum maple_type mt_node_type(const void *entry) +static inline enum maple_type mt_node_type(const struct maple_enode *entry) { return ((unsigned long)entry >> 3) & 15; } -static inline bool mt_is_leaf(const void *entry) +static inline bool mt_is_leaf(const struct maple_enode *entry) { return mt_node_type(entry) < maple_range_16; } @@ -122,35 +123,34 @@ static inline bool mas_is_start(struct ma_state *ms) return ms->node == MAS_START; } -static inline struct maple_node *mt_to_node(const void *entry) +static inline struct maple_node *mt_to_node(const struct maple_enode *entry) { return (struct maple_node *)((unsigned long)entry & ~127); } -static inline -void *mt_mk_node(const struct maple_node *node, enum maple_type type) -{ +static inline struct maple_enode *mt_mk_node(const struct maple_node *node, + enum maple_type type) { return (void *)((unsigned long)node | (type << 3) | 4); } static inline -void *mt_mk_root(const struct maple_node *node) +void *mt_mk_root(const struct maple_enode *node) { return (void *)((unsigned long)node | 2); } static inline -void *mt_safe_root(const struct maple_node *node) +void *mt_safe_root(const struct maple_enode *node) { return (void *)((unsigned long)node & ~2); } static inline -void *mt_is_full(const struct maple_node *node) +void *mt_is_full(const struct maple_enode *node) { return (void *)((unsigned long)node & ~4); } static inline -void mt_set_full(const struct maple_node *node) +void mt_set_full(const struct maple_enode *node) { node = (void *)((unsigned long)node | 4); } @@ -160,7 +160,7 @@ static inline bool mas_is_err(struct ma_state *mas) return xa_is_err(mas->node); } -static inline unsigned int mt_slot_mask(struct maple_node *node) +static inline unsigned int mt_slot_mask(const struct maple_enode *node) { unsigned int bitmask = 0x78; // Bits 3-6 @@ -168,12 +168,16 @@ static inline unsigned int mt_slot_mask(struct maple_node *node) bitmask |= 0x04; // Set bit 2. return bitmask; } -static inline bool ma_is_root(struct maple_node *node) +static inline bool _ma_is_root(struct maple_node *node) { - if (((unsigned long)mt_to_node(node)->parent & MA_ROOT_PARENT) == 1) + if (((unsigned long)node->parent & MA_ROOT_PARENT) == 1) return true; return false; } +static inline bool ma_is_root(struct maple_enode *node) +{ + return _ma_is_root(mt_to_node(node)); +} static inline bool mt_is_alloc(struct maple_tree *mt) { @@ -210,7 +214,7 @@ static inline enum maple_type mt_parent_alloc_enum(unsigned long parent) } static inline enum maple_type mt_parent_enum(struct ma_state *mas, - struct maple_node *node) + struct maple_enode *node) { unsigned long parent = (unsigned long) mt_to_node(node)->parent; unsigned long slot_shift = mt_parent_shift(parent); @@ -233,8 +237,9 @@ static inline enum maple_type mt_parent_enum(struct ma_state *mas, * range_32, slot number is encoded in bits 3-6 * [a]range_64, slot number is encoded in bits 3-6 */ -static inline void mt_set_parent(struct maple_node *node, - struct maple_node *parent, unsigned char slot) +static inline void mt_set_parent(struct maple_enode *node, + const struct maple_enode *parent, + unsigned char slot) { unsigned long bitmask = 0x78; unsigned long slot_shift = 3; @@ -263,7 +268,7 @@ static inline void mt_set_parent(struct maple_node *node, mt_to_node(node)->parent = ma_parent_ptr(val); } -static inline unsigned int mt_parent_slot(struct maple_node *node) +static inline unsigned int mt_parent_slot(const struct maple_enode *node) { unsigned long bitmask = 0x7C; unsigned long val = (unsigned long) mt_to_node(node)->parent; @@ -276,7 +281,7 @@ static inline unsigned int mt_parent_slot(struct maple_node *node) } -static inline void *mt_parent(struct maple_node *node) +static inline struct maple_node *mt_parent(const struct maple_enode *node) { unsigned long bitmask = 0x7F; @@ -323,7 +328,7 @@ static inline void ma_set_slot(struct ma_state *ms, int slot) ma_set_alloc_req(ms, slot); } -static inline unsigned long _ma_get_pivot(const struct maple_node *mn, +static inline unsigned long _ma_get_pivot(const struct maple_enode *mn, unsigned char slot, enum maple_type type) { switch (type) { @@ -356,12 +361,12 @@ static inline unsigned long _ma_get_pivot(const struct maple_node *mn, return 0; } } -static inline unsigned long ma_get_pivot(const struct maple_node *mn, +static inline unsigned long ma_get_pivot(const struct maple_enode *mn, unsigned char slot) { return _ma_get_pivot(mn, slot, mt_node_type(mn)); } -static inline void ma_set_pivot(struct maple_node *mn, unsigned char slot, +static inline void ma_set_pivot(struct maple_enode *mn, unsigned char slot, unsigned long val) { enum maple_type type = mt_node_type(mn); @@ -406,12 +411,12 @@ static inline void ma_set_pivot(struct maple_node *mn, unsigned char slot, } return; } -static inline void ma_cp_pivot(struct maple_node *dst, - unsigned char dloc, struct maple_node *src, unsigned long sloc) +static inline void ma_cp_pivot(struct maple_enode *dst, + unsigned char dloc, struct maple_enode *src, unsigned long sloc) { ma_set_pivot(dst, dloc, ma_get_pivot(src, sloc)); } -static inline void __rcu *_ma_get_rcu_slot(const struct maple_node *mn, +static inline struct maple_enode *_ma_get_rcu_slot(const struct maple_enode *mn, unsigned char slot, enum maple_type type) { switch (type) { @@ -444,13 +449,13 @@ static inline void __rcu *_ma_get_rcu_slot(const struct maple_node *mn, return rcu_dereference(mt_to_node(mn)->mr32.slot[slot]); } } -static inline void __rcu *ma_get_rcu_slot(const struct maple_node *mn, +static inline struct maple_enode *ma_get_rcu_slot(const struct maple_enode *mn, unsigned char slot) { return _ma_get_rcu_slot(mn, slot, mt_node_type(mn)); } -static inline void ma_set_rcu_slot(const struct maple_node *mn, - unsigned char slot, void *val) +static inline void ma_set_rcu_slot(const struct maple_enode *mn, + unsigned char slot, struct maple_enode *val) { enum maple_type type = mt_node_type(mn); @@ -495,12 +500,12 @@ static inline void ma_set_rcu_slot(const struct maple_node *mn, break; } } -static inline void ma_cp_rcu_slot(struct maple_node *dst, - unsigned char dloc, struct maple_node *src, unsigned long sloc) +static inline void ma_cp_rcu_slot(struct maple_enode *dst, + unsigned char dloc, struct maple_enode *src, unsigned long sloc) { ma_set_rcu_slot(dst, dloc, ma_get_rcu_slot(src, sloc)); } -static inline void ma_update_rcu_slot(const struct maple_node *mn, +static inline void ma_update_rcu_slot(const struct maple_enode *mn, unsigned char slot, void *val) { enum maple_type type = mt_node_type(mn); @@ -547,7 +552,7 @@ static inline void ma_update_rcu_slot(const struct maple_node *mn, } } -static inline unsigned long ma_get_gap(const struct maple_node *mn, +static inline unsigned long ma_get_gap(const struct maple_enode *mn, unsigned char gap, enum maple_type type) { switch (type) { @@ -557,7 +562,7 @@ static inline unsigned long ma_get_gap(const struct maple_node *mn, return 0; } } -static inline void ma_set_gap(const struct maple_node *mn, +static inline void ma_set_gap(const struct maple_enode *mn, unsigned char gap, unsigned long val) { enum maple_type type = mt_node_type(mn); @@ -569,8 +574,8 @@ static inline void ma_set_gap(const struct maple_node *mn, break; } } -static inline void ma_cp_gap(struct maple_node *dst, - unsigned char dloc, struct maple_node *src, unsigned long sloc) +static inline void ma_cp_gap(struct maple_enode *dst, + unsigned char dloc, struct maple_enode *src, unsigned long sloc) { ma_set_gap(dst, dloc, ma_get_gap(src, sloc, mt_node_type(src))); } @@ -589,7 +594,7 @@ static inline void ma_encoded_parent(struct ma_state *mas) void *parent, *gparent; unsigned char slot; - if (ma_is_root(mt_parent(mas->node))) { + if (_ma_is_root(mt_parent(mas->node))) { mas->node = mt_safe_root(rcu_dereference(mas->tree->ma_root)); mas->min = 0; mas->max = mt_node_max(mas->node); @@ -597,7 +602,7 @@ static inline void ma_encoded_parent(struct ma_state *mas) } /* Go up 2 levels */ - parent = mt_parent(mt_to_node(mas->node)); + parent = mt_parent(mas->node); gparent = mt_parent(parent); /* Get the parents slot in the grand parent */ slot = mt_parent_slot(parent); @@ -712,7 +717,7 @@ static inline struct maple_node *mas_node_cnt(struct ma_state *ms, int count) return ms->alloc; } -static inline void *mas_start(struct ma_state *mas) +static inline struct maple_enode *mas_start(struct ma_state *mas) { if (mas->node == MAS_START) { if (!xa_is_node(mas->tree->ma_root)) { @@ -728,7 +733,7 @@ static inline void *mas_start(struct ma_state *mas) return mas->node; } -static inline unsigned char ma_data_end(const struct maple_node *mn, +static inline unsigned char ma_data_end(const struct maple_enode *mn, const enum maple_type type) { unsigned char data_end = 0; @@ -747,9 +752,9 @@ static inline unsigned char ma_data_end(const struct maple_node *mn, return data_end; } - +// FIXME: don't use the same pointers for maple_node and maple_enode static inline unsigned char ma_calc_split(struct ma_state *mas, - struct maple_node **left, struct maple_node **right) + struct maple_enode **left, struct maple_enode **right) { char i, j; unsigned long min = mas->min; @@ -759,7 +764,7 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, unsigned long half = mt_slots[type] / 2; unsigned char data_end = ma_data_end(mas->node, type); - *left = ma_next_alloc(mas); + *left = (struct maple_enode*)ma_next_alloc(mas); for (i = 0; i < data_end; i++) { max = ma_get_pivot(mas->node, i); if ((max - min) > 15) { @@ -770,14 +775,14 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, } if (i >= data_end) { - *left = mt_mk_node(*left, maple_dense); + *left = mt_mk_node(ma_mnode_ptr(*left), maple_dense); return i; } - *right = ma_next_alloc(mas); + *right = (struct maple_enode*)ma_next_alloc(mas); if (i >= half) { - *left = mt_mk_node(*left, maple_dense); - *right = mt_mk_node(*right, type); + *left = mt_mk_node(ma_mnode_ptr(*left), maple_dense); + *right = mt_mk_node(ma_mnode_ptr(*right), type); return i; } @@ -797,12 +802,12 @@ static inline unsigned char ma_calc_split(struct ma_state *mas, } while (j > 0); if (data_end - j >= half) { - *left = mt_mk_node(*left, type); - *right = mt_mk_node(*right, maple_dense); + *left = mt_mk_node(ma_mnode_ptr(*left), type); + *right = mt_mk_node(ma_mnode_ptr(*right), maple_dense); return j; } else { - *left = mt_mk_node(*left, type); - *right = mt_mk_node(*right, type); + *left = mt_mk_node(ma_mnode_ptr(*left), type); + *right = mt_mk_node(ma_mnode_ptr(*right), type); } return i > 2 ? i : half - 1; @@ -860,8 +865,7 @@ static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) mas_node_cnt(mas, 1); if (mas_is_err(mas)) return; - cp->dst = ma_next_alloc(mas); - cp->dst = mt_mk_node(cp->dst, type); + cp->dst = mt_mk_node(ma_next_alloc(mas), type); } if (!mt_pivot_count(cp->dst)) { @@ -890,8 +894,8 @@ static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) } cp->dst_start = dloc; } -static inline int ma_split_data(struct ma_state *mas, struct maple_node *left, - struct maple_node *right, unsigned char split) +static inline int ma_split_data(struct ma_state *mas, struct maple_enode *left, + struct maple_enode *right, unsigned char split) { MA_CP(cp, mas->node, left, 0, split); @@ -907,13 +911,13 @@ static inline int ma_split_data(struct ma_state *mas, struct maple_node *left, return split; } -static inline void ma_adopt_children(struct maple_node *parent) +static inline void ma_adopt_children(struct maple_enode *parent) { - struct maple_node *child; - unsigned char slot; enum maple_type type = mt_node_type(parent); unsigned char slot_cnt = mt_slots[type]; + struct maple_enode *child; + unsigned char slot; for (slot = 0; slot < slot_cnt; slot++) { if (slot != 0 && slot < slot_cnt - 1 && @@ -933,8 +937,8 @@ static inline void mt_replace(struct ma_state *mas) { struct maple_node *mn = mt_to_node(mas->node); struct maple_node *parent; + struct maple_enode *prev; unsigned char slot = 0; - struct maple_node *prev; if (ma_is_root(mas->node)) { prev = mas->tree->ma_root; @@ -945,7 +949,7 @@ static inline void mt_replace(struct ma_state *mas) prev = ma_get_rcu_slot(mt_mk_node(parent, ptype), slot); } - if (prev == mn) + if (mt_to_node(prev) == mn) return; if (!mt_is_leaf(mas->node)) @@ -982,7 +986,7 @@ static inline void mas_partial_copy(struct ma_state *mas, return; } -static inline void ma_link(struct maple_node *new, struct maple_node *parent, +static inline void ma_link(struct maple_enode *new, struct maple_enode *parent, unsigned char slot, unsigned long pivot, enum maple_type type) { unsigned char pivot_cnt = mt_pivots[type]; @@ -1014,9 +1018,10 @@ static inline void ma_link(struct maple_node *new, struct maple_node *parent, */ static inline int ma_split(struct ma_state *mas, unsigned char slot) { - struct maple_node *full = (mas->node); + struct maple_enode *full = (mas->node); unsigned char split, p_slot = 0, p_end = 0; - struct maple_node *old_parent, *new_parent, *left = NULL, *right = NULL; + struct maple_enode *old_parent, *new_parent; + struct maple_enode *left = NULL, *right = NULL; enum maple_type ptype; // parent type. unsigned long pivot; unsigned char slot_cnt = mt_slot_count(mas->node); @@ -1156,7 +1161,7 @@ static inline enum maple_type ma_ptype_leaf(struct ma_state *mas) { static inline enum maple_type ma_determine_type(struct ma_state *mas, unsigned long min, unsigned char slot) { - struct maple_node *sibling; + struct maple_enode *sibling; unsigned char sibling_slot = slot; enum maple_type stype, mt = ma_ptype_leaf(mas);; @@ -1191,7 +1196,7 @@ static inline enum maple_type ma_determine_type(struct ma_state *mas, static inline int _ma_insert(struct ma_state *mas, void *entry, unsigned char slot) { - struct maple_node *p_mn; + struct maple_enode *p_mn; int o_end = ma_data_end(mas->node, mt_node_type(mas->node)); // Old end int n_end = o_end; // New end unsigned long max = mas->max; @@ -1245,7 +1250,7 @@ static inline int _ma_insert(struct ma_state *mas, void *entry, p_mn = mas->node; if (!mt_is_leaf(mas->node)) { - struct maple_node *leaf; + struct maple_enode *leaf; enum maple_type mt; unsigned long o_min = mas->min; unsigned long o_max = mas->max; @@ -1349,7 +1354,7 @@ static inline void ma_root_expand(struct ma_state *ms, void *entry) ((unsigned long)ms->tree | MA_ROOT_PARENT)); /* Assign the old entry to slot 0, or set it to null. */ - ma_set_rcu_slot(mn, 0, r_entry); + ma_set_rcu_slot(ms->node, 0, r_entry); if (!r_entry) ma_set_pivot(ms->node, 0, ms->index - 1); @@ -1367,8 +1372,8 @@ static inline void ma_root_expand(struct ma_state *ms, void *entry) */ static inline int mas_coalesce(struct ma_state *mas) { - struct maple_node *src = mas->node; - struct maple_node *dst = NULL; + struct maple_enode *src = mas->node; + struct maple_enode *dst = NULL; unsigned char s_slot, d_slot = 0; unsigned long last = 0; int ret = 0; @@ -1424,7 +1429,7 @@ done: static inline bool _mas_walk(struct ma_state *mas) { enum maple_type type; - struct maple_node *next; + struct maple_enode *next; unsigned long pivot = 0; unsigned long pivot_cnt, max, min, i; bool ret = false; @@ -1611,7 +1616,7 @@ int ma_erase(struct ma_state *mas) return cnt; } -void ma_destroy_walk(struct maple_node *mn) +void ma_destroy_walk(struct maple_enode *mn) { unsigned int type = mt_node_type(mn); unsigned char slot_cnt = mt_slot_count(mn); @@ -1733,7 +1738,7 @@ int mtree_erase(struct maple_tree *mt, unsigned long index) void mtree_destroy(struct maple_tree *mt) { mtree_lock(mt); - struct maple_node *destroyed = mt->ma_root; + struct maple_enode *destroyed = mt->ma_root; rcu_assign_pointer(mt->ma_root, NULL); if (xa_is_node(destroyed)) { -- 2.50.1