From 7cbed2d45594325ece7a1164febaa7b8bb390916 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 10 Oct 2019 15:08:29 -0400 Subject: [PATCH] maple_tree: Standardize names of functions anything that takes a struct ma_state as the first argument is named mas_ anything that takes a struct maple_enode as the first argument is name mte_ Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 1293 +++++++++++++++--------------- lib/test_maple_tree.c | 34 +- tools/testing/radix-tree/maple.c | 2 +- 3 files changed, 660 insertions(+), 669 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index bd005880d007..1680659dbce1 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -64,7 +64,7 @@ unsigned long mt_max[] = { [maple_range_64] = ULONG_MAX, [maple_arange_64] = ULONG_MAX, }; -#define mt_node_max(x) mt_max[mt_node_type(x)] +#define mt_node_max(x) mt_max[mte_node_type(x)] unsigned char mt_slots[] = { @@ -83,7 +83,7 @@ unsigned char mt_slots[] = { [maple_range_64] = MAPLE_RANGE64_SLOTS, [maple_arange_64] = MAPLE_ARANGE64_SLOTS, }; -#define mt_slot_count(x) mt_slots[mt_node_type(x)] +#define mt_slot_count(x) mt_slots[mte_node_type(x)] unsigned char mt_pivots[] = { [maple_dense] = 0, @@ -101,7 +101,7 @@ unsigned char mt_pivots[] = { [maple_range_64] = MAPLE_RANGE64_SLOTS - 1, [maple_arange_64] = MAPLE_ARANGE64_SLOTS - 1, }; -#define mt_pivot_count(x) mt_pivots[mt_node_type(x)] +#define mt_pivot_count(x) mt_pivots[mte_node_type(x)] unsigned char mt_min_slots[] = { [maple_dense] = MAPLE_NODE_SLOTS / 2, @@ -119,7 +119,7 @@ unsigned char mt_min_slots[] = { [maple_range_64] = MAPLE_RANGE64_SLOTS / 2, [maple_arange_64] = (MAPLE_ARANGE64_SLOTS + 1) / 2, }; -#define mt_min_slot_cnt(x) mt_min_slots[mt_node_type(x)] +#define mt_min_slot_cnt(x) mt_min_slots[mte_node_type(x)] // Functions static struct maple_node *mt_alloc_one(gfp_t gfp) @@ -134,13 +134,13 @@ static void mt_free_rcu(struct rcu_head *head) kmem_cache_free(maple_node_cache, node); } -static void mt_free(struct maple_node *node) +static void ma_free(struct maple_node *node) { node->parent = ma_parent_ptr(node); call_rcu(&node->rcu, mt_free_rcu); } -static inline enum maple_type mt_node_type(const struct maple_enode *entry) +static inline enum maple_type mte_node_type(const struct maple_enode *entry) { return ((unsigned long)entry >> 3) & 15; } @@ -150,9 +150,9 @@ static inline bool ma_is_leaf(const enum maple_type type) return type < maple_range_16; } -static inline bool mt_is_leaf(const struct maple_enode *entry) +static inline bool mte_is_leaf(const struct maple_enode *entry) { - return ma_is_leaf(mt_node_type(entry)); + return ma_is_leaf(mte_node_type(entry)); } static inline enum maple_type mt_node_hole(const void *entry) @@ -188,9 +188,9 @@ static inline void mas_set_err(struct ma_state *mas, long err) { mas->node = MA_ERROR(err); } -static inline bool mas_is_start(struct ma_state *ms) +static inline bool mas_is_start(struct ma_state *mas) { - return ms->node == MAS_START; + return mas->node == MAS_START; } void mas_reset(struct ma_state *mas) @@ -198,14 +198,14 @@ void mas_reset(struct ma_state *mas) mas->node = MAS_START; } -static inline struct maple_node *mt_to_node(const struct maple_enode *entry) +static inline struct maple_node *mte_to_node(const struct maple_enode *entry) { return (struct maple_node *)((unsigned long)entry & ~127); } static void mte_free(struct maple_enode *enode) { - mt_free(mt_to_node(enode)); + ma_free(mte_to_node(enode)); } static inline struct maple_enode *mt_mk_node(const struct maple_node *node, @@ -214,23 +214,23 @@ static inline struct maple_enode *mt_mk_node(const struct maple_node *node, } static inline -void *mt_mk_root(const struct maple_enode *node) +void *mte_mk_root(const struct maple_enode *node) { return (void *)((unsigned long)node | 2); } static inline -void *mt_safe_root(const struct maple_enode *node) +void *mte_safe_root(const struct maple_enode *node) { return (void *)((unsigned long)node & ~2); } static inline -void *mt_is_full(const struct maple_enode *node) +void *mte_is_full(const struct maple_enode *node) { return (void *)((unsigned long)node & ~4); } static inline -void mt_set_full(const struct maple_enode *node) +void mte_set_full(const struct maple_enode *node) { node = (void *)((unsigned long)node | 4); } @@ -240,11 +240,11 @@ static inline bool mas_is_err(struct ma_state *mas) return xa_is_err(mas->node); } -static inline unsigned int mt_slot_mask(const struct maple_enode *node) +static inline unsigned int mte_slot_mask(const struct maple_enode *node) { unsigned int bitmask = 0x78; // Bits 3-6 - if (mt_node_type(node) == MAPLE_RANGE16_SLOTS) + if (mte_node_type(node) == MAPLE_RANGE16_SLOTS) bitmask |= 0x04; // Set bit 2. return bitmask; } @@ -253,9 +253,9 @@ static inline bool _ma_is_root(struct maple_node *node) return ((unsigned long)node->parent & MA_ROOT_PARENT); } -static inline bool ma_is_root(struct maple_enode *node) +static inline bool mte_is_root(struct maple_enode *node) { - return _ma_is_root(mt_to_node(node)); + return _ma_is_root(mte_to_node(node)); } static inline bool mt_is_alloc(struct maple_tree *mt) @@ -264,14 +264,14 @@ static inline bool mt_is_alloc(struct maple_tree *mt) } -static inline unsigned int mt_parent_shift(unsigned long parent) +static inline unsigned int mte_parent_shift(unsigned long parent) { if (!(parent & 2)) return 2; // maple_range_16 return 3; } -static inline enum maple_type mt_parent_range_enum(unsigned long parent) +static inline enum maple_type mte_parent_range_enum(unsigned long parent) { switch (parent) { case 6: @@ -284,7 +284,7 @@ static inline enum maple_type mt_parent_range_enum(unsigned long parent) return maple_dense; } -static inline enum maple_type mt_parent_alloc_enum(unsigned long parent) +static inline enum maple_type mte_parent_alloc_enum(unsigned long parent) { switch (parent) { case 6: @@ -293,21 +293,21 @@ static inline enum maple_type mt_parent_alloc_enum(unsigned long parent) return maple_dense; } -static inline enum maple_type mt_parent_enum(struct ma_state *mas, +static inline enum maple_type mas_parent_enum(struct ma_state *mas, struct maple_enode *node) { unsigned long parent = 6; unsigned long slot_shift; - if (!ma_is_root(mas->node)) { - parent = (unsigned long) mt_to_node(node)->parent; - slot_shift = mt_parent_shift(parent); + if (!mte_is_root(mas->node)) { + parent = (unsigned long) mte_to_node(node)->parent; + slot_shift = mte_parent_shift(parent); parent &= (1 << slot_shift) - 1; } if (mt_is_alloc(mas->tree)) - return mt_parent_alloc_enum(parent); - return mt_parent_range_enum(parent); + return mte_parent_alloc_enum(parent); + return mte_parent_range_enum(parent); } /* Private @@ -322,7 +322,7 @@ 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_enode *node, +static inline void mte_set_parent(struct maple_enode *node, const struct maple_enode *parent, unsigned char slot) { @@ -331,7 +331,7 @@ static inline void mt_set_parent(struct maple_enode *node, unsigned long val = (unsigned long) parent; unsigned long type = 0; - switch (mt_node_type(parent)) { + switch (mte_node_type(parent)) { case maple_range_64: case maple_arange_64: type |= 4; @@ -350,14 +350,14 @@ static inline void mt_set_parent(struct maple_enode *node, val &= ~bitmask; // Remove any old slot number. val |= (slot << slot_shift); // Set the slot. val |= type; - mt_to_node(node)->parent = ma_parent_ptr(val); + mte_to_node(node)->parent = ma_parent_ptr(val); } -static inline unsigned int mt_parent_slot(const struct maple_enode *node) +static inline unsigned int mte_parent_slot(const struct maple_enode *node) { unsigned long bitmask = 0x7C; - unsigned long val = (unsigned long) mt_to_node(node)->parent; - unsigned long slot_shift = mt_parent_shift(val); + unsigned long val = (unsigned long) mte_to_node(node)->parent; + unsigned long slot_shift = mte_parent_shift(val); if (val & 1) return 0; // Root. @@ -366,23 +366,23 @@ static inline unsigned int mt_parent_slot(const struct maple_enode *node) } -static inline struct maple_node *mt_parent(const struct maple_enode *node) +static inline struct maple_node *mte_parent(const struct maple_enode *node) { unsigned long bitmask = 0x7F; - return (void *)((unsigned long)(mt_to_node(node)->parent) & ~bitmask); + return (void *)((unsigned long)(mte_to_node(node)->parent) & ~bitmask); } -static inline bool mt_dead_node(const struct maple_enode *enode) +static inline bool mte_dead_node(const struct maple_enode *enode) { - struct maple_node *parent, *node = mt_to_node(enode); + struct maple_node *parent, *node = mte_to_node(enode); - parent = mt_parent(enode); + parent = mte_parent(enode); return (parent == node); } -static inline struct maple_node *ma_get_alloc(const struct ma_state *ms) +static inline struct maple_node *mas_get_alloc(const struct ma_state *ms) { return (struct maple_node *)((unsigned long)ms->alloc & ~0x7F); } @@ -407,9 +407,9 @@ static inline int ma_get_node_alloc_cnt(const struct maple_node *node) return ret; } -static inline int ma_get_alloc_cnt(const struct ma_state *ms) +static inline int mas_get_alloc_cnt(const struct ma_state *mas) { - struct maple_node *node = ma_get_alloc(ms); + struct maple_node *node = mas_get_alloc(mas); if (!node) return 0; @@ -417,304 +417,299 @@ static inline int ma_get_alloc_cnt(const struct ma_state *ms) return ma_get_node_alloc_cnt(node); } -static inline void ma_set_alloc_req(struct ma_state *ms, int count) +static inline void mas_set_alloc_req(struct ma_state *mas, int count) { - ms->alloc = (struct maple_node *)((unsigned long)ms->alloc & ~0x7F); - ms->alloc = (struct maple_node *)((unsigned long)ms->alloc | count); + mas->alloc = (struct maple_node *)((unsigned long)mas->alloc & ~0x7F); + mas->alloc = (struct maple_node *)((unsigned long)mas->alloc | count); } -static inline int ma_get_alloc_req(const struct ma_state *ms) +static inline int mas_get_alloc_req(const struct ma_state *mas) { - return (int)(((unsigned long)ms->alloc & 0x7F)); + return (int)(((unsigned long)mas->alloc & 0x7F)); } -static inline int ma_get_slot(const struct ma_state *ms) +static inline int mas_get_slot(const struct ma_state *mas) { - return ma_get_alloc_req(ms); + return mas_get_alloc_req(mas); } -static inline void ma_set_slot(struct ma_state *ms, int slot) +static inline void mas_set_slot(struct ma_state *mas, int slot) { - ma_set_alloc_req(ms, slot); + mas_set_alloc_req(mas, slot); } -static inline unsigned long _ma_get_pivot(const struct maple_enode *mn, +static inline unsigned long _mte_get_pivot(const struct maple_enode *mn, unsigned char slot, enum maple_type type) { switch (type) { case maple_arange_64: - return mt_to_node(mn)->ma64.pivot[slot]; + return mte_to_node(mn)->ma64.pivot[slot]; case maple_range_64: case maple_leaf_64: - return mt_to_node(mn)->mr64.pivot[slot]; + return mte_to_node(mn)->mr64.pivot[slot]; case maple_sparse_6: - return mt_to_node(mn)->ms6.pivot; + return mte_to_node(mn)->ms6.pivot; case maple_sparse_9: - return mt_to_node(mn)->ms9.pivot[slot]; + return mte_to_node(mn)->ms9.pivot[slot]; case maple_sparse_16: - return mt_to_node(mn)->ms16.pivot[slot]; + return mte_to_node(mn)->ms16.pivot[slot]; case maple_sparse_21: - return mt_to_node(mn)->ms21.pivot[slot]; + return mte_to_node(mn)->ms21.pivot[slot]; case maple_sparse_32: - return mt_to_node(mn)->ms32.pivot[slot]; + return mte_to_node(mn)->ms32.pivot[slot]; case maple_sparse_64: - return mt_to_node(mn)->ms64.pivot[slot]; + return mte_to_node(mn)->ms64.pivot[slot]; case maple_range_16: case maple_leaf_16: - return mt_to_node(mn)->mr16.pivot[slot]; + return mte_to_node(mn)->mr16.pivot[slot]; case maple_range_32: case maple_leaf_32: - return mt_to_node(mn)->mr32.pivot[slot]; + return mte_to_node(mn)->mr32.pivot[slot]; case maple_dense: default: return 0; } } -static inline unsigned long ma_get_pivot(const struct maple_enode *mn, +static inline unsigned long mte_get_pivot(const struct maple_enode *mn, unsigned char slot) { - return _ma_get_pivot(mn, slot, mt_node_type(mn)); + return _mte_get_pivot(mn, slot, mte_node_type(mn)); } - -/* ma_get_safe_pivot() - Return the pivot or the mas->max. - * - * Return: The pivot (including mas->max for the final slot) - */ -static inline unsigned long _ma_get_safe_pivot(const struct ma_state *mas, +static inline unsigned long _mas_get_safe_pivot(const struct ma_state *mas, unsigned char slot, enum maple_type type) { if (slot >= mt_pivots[type]) return mas->max; - return _ma_get_pivot(mas->node, slot, type); + return _mte_get_pivot(mas->node, slot, type); } -static inline unsigned long ma_get_safe_pivot(const struct ma_state *mas, +/** Private + * mas_get_safe_pivot() - Return the pivot or the mas->max. + * + * Return: The pivot (including mas->max for the final slot) + */ +static inline unsigned long mas_get_safe_pivot(const struct ma_state *mas, unsigned char slot) { - enum maple_type type = mt_node_type(mas->node); - return _ma_get_safe_pivot(mas, slot, type); + enum maple_type type = mte_node_type(mas->node); + return _mas_get_safe_pivot(mas, slot, type); } -static inline void ma_set_pivot(struct maple_enode *mn, unsigned char slot, +static inline void mte_set_pivot(struct maple_enode *mn, unsigned char slot, unsigned long val) { - enum maple_type type = mt_node_type(mn); + enum maple_type type = mte_node_type(mn); switch (type) { default: case maple_range_64: case maple_leaf_64: - (&mt_to_node(mn)->mr64)->pivot[slot] = val; + (&mte_to_node(mn)->mr64)->pivot[slot] = val; break; case maple_arange_64: - (&mt_to_node(mn)->ma64)->pivot[slot] = val; + (&mte_to_node(mn)->ma64)->pivot[slot] = val; case maple_dense: break; case maple_sparse_6: - (&mt_to_node(mn)->ms6)->pivot = val; + (&mte_to_node(mn)->ms6)->pivot = val; break; case maple_sparse_9: - (&mt_to_node(mn)->ms9)->pivot[slot] = val; + (&mte_to_node(mn)->ms9)->pivot[slot] = val; break; case maple_sparse_16: - (&mt_to_node(mn)->ms16)->pivot[slot] = val; + (&mte_to_node(mn)->ms16)->pivot[slot] = val; break; case maple_sparse_21: - (&mt_to_node(mn)->ms21)->pivot[slot] = val; + (&mte_to_node(mn)->ms21)->pivot[slot] = val; break; case maple_sparse_32: - (&mt_to_node(mn)->ms32)->pivot[slot] = val; + (&mte_to_node(mn)->ms32)->pivot[slot] = val; break; case maple_sparse_64: - (&mt_to_node(mn)->ms64)->pivot[slot] = val; + (&mte_to_node(mn)->ms64)->pivot[slot] = val; break; case maple_range_16: case maple_leaf_16: - (&mt_to_node(mn)->mr16)->pivot[slot] = val; + (&mte_to_node(mn)->mr16)->pivot[slot] = val; break; case maple_range_32: case maple_leaf_32: - (&mt_to_node(mn)->mr32)->pivot[slot] = val; + (&mte_to_node(mn)->mr32)->pivot[slot] = val; break; } } static inline void mas_set_safe_pivot(struct ma_state *mas, unsigned char slot, unsigned long val) { - enum maple_type type = mt_node_type(mas->node); + enum maple_type type = mte_node_type(mas->node); if (slot >= mt_pivots[type]) { unsigned char p_slot; struct maple_enode *me = mas->node; - if (_ma_is_root(mt_parent(mas->node))) + if (_ma_is_root(mte_parent(mas->node))) return; - p_slot = mt_parent_slot(mas->node); + p_slot = mte_parent_slot(mas->node); mas_set_safe_pivot(mas, p_slot + 1, val); mas->node = me; return; } - ma_set_pivot(mas->node, slot, val); -} -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)); + mte_set_pivot(mas->node, slot, val); } -static inline struct maple_enode *__ma_get_rcu_slot( +static inline struct maple_enode *__mte_get_rcu_slot( const struct maple_enode *mn, unsigned char slot, enum maple_type type) { switch (type) { case maple_range_64: case maple_leaf_64: - return rcu_dereference(mt_to_node(mn)->mr64.slot[slot]); + return rcu_dereference(mte_to_node(mn)->mr64.slot[slot]); default: case maple_dense: - return rcu_dereference(mt_to_node(mn)->slot[slot]); + return rcu_dereference(mte_to_node(mn)->slot[slot]); case maple_arange_64: - return rcu_dereference(mt_to_node(mn)->ma64.slot[slot]); + return rcu_dereference(mte_to_node(mn)->ma64.slot[slot]); case maple_sparse_6: - return rcu_dereference(mt_to_node(mn)->ms6.slot[slot]); + return rcu_dereference(mte_to_node(mn)->ms6.slot[slot]); case maple_sparse_9: - return rcu_dereference(mt_to_node(mn)->ms9.slot[slot]); + return rcu_dereference(mte_to_node(mn)->ms9.slot[slot]); case maple_sparse_16: - return rcu_dereference(mt_to_node(mn)->ms16.slot[slot]); + return rcu_dereference(mte_to_node(mn)->ms16.slot[slot]); case maple_sparse_21: - return rcu_dereference(mt_to_node(mn)->ms21.slot[slot]); + return rcu_dereference(mte_to_node(mn)->ms21.slot[slot]); case maple_sparse_32: - return rcu_dereference(mt_to_node(mn)->ms32.slot[slot]); + return rcu_dereference(mte_to_node(mn)->ms32.slot[slot]); case maple_sparse_64: - return rcu_dereference(mt_to_node(mn)->ms64.slot[slot]); + return rcu_dereference(mte_to_node(mn)->ms64.slot[slot]); case maple_range_16: case maple_leaf_16: - return rcu_dereference(mt_to_node(mn)->mr16.slot[slot]); + return rcu_dereference(mte_to_node(mn)->mr16.slot[slot]); case maple_range_32: case maple_leaf_32: - return rcu_dereference(mt_to_node(mn)->mr32.slot[slot]); + return rcu_dereference(mte_to_node(mn)->mr32.slot[slot]); } } -static inline struct maple_enode *_ma_get_rcu_slot( +static inline struct maple_enode *_mte_get_rcu_slot( const struct maple_enode *mn, unsigned char slot, enum maple_type type) { - struct maple_enode *p = __ma_get_rcu_slot(mn, slot, type); + struct maple_enode *p = __mte_get_rcu_slot(mn, slot, type); - if (mt_dead_node(mn)) + if (mte_dead_node(mn)) return MAS_START; return p; } -static inline struct maple_enode *ma_get_rcu_slot(const struct maple_enode *mn, +static inline struct maple_enode *mte_get_rcu_slot(const struct maple_enode *mn, unsigned char slot) { - return _ma_get_rcu_slot(mn, slot, mt_node_type(mn)); + return _mte_get_rcu_slot(mn, slot, mte_node_type(mn)); } -static inline void ma_set_rcu_slot(const struct maple_enode *mn, +static inline void mte_set_rcu_slot(const struct maple_enode *mn, unsigned char slot, void *val) { - enum maple_type type = mt_node_type(mn); + enum maple_type type = mte_node_type(mn); switch (type) { default: case maple_dense: - RCU_INIT_POINTER(mt_to_node(mn)->slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->slot[slot], val); break; case maple_sparse_6: - RCU_INIT_POINTER(mt_to_node(mn)->ms6.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->ms6.slot[slot], val); break; case maple_sparse_9: - RCU_INIT_POINTER(mt_to_node(mn)->ms9.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->ms9.slot[slot], val); break; case maple_sparse_16: - RCU_INIT_POINTER(mt_to_node(mn)->ms16.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->ms16.slot[slot], val); break; case maple_sparse_21: - RCU_INIT_POINTER(mt_to_node(mn)->ms21.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->ms21.slot[slot], val); break; case maple_sparse_32: - RCU_INIT_POINTER(mt_to_node(mn)->ms32.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->ms32.slot[slot], val); break; case maple_sparse_64: - RCU_INIT_POINTER(mt_to_node(mn)->ms64.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->ms64.slot[slot], val); break; case maple_range_16: case maple_leaf_16: - RCU_INIT_POINTER(mt_to_node(mn)->mr16.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->mr16.slot[slot], val); break; case maple_range_32: case maple_leaf_32: - RCU_INIT_POINTER(mt_to_node(mn)->mr32.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->mr32.slot[slot], val); break; case maple_range_64: case maple_leaf_64: - RCU_INIT_POINTER(mt_to_node(mn)->mr64.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->mr64.slot[slot], val); break; case maple_arange_64: - RCU_INIT_POINTER(mt_to_node(mn)->ma64.slot[slot], val); + RCU_INIT_POINTER(mte_to_node(mn)->ma64.slot[slot], val); break; } } /** Private - * ma_cp_rcu_slot() = Copy from one node to anther. Upon seeing a retry, + * mte_cp_rcu_slot() = Copy from one node to anther. Upon seeing a retry, * copies NULL. */ -static inline void ma_cp_rcu_slot(struct maple_enode *dst, +static inline void mte_cp_rcu_slot(struct maple_enode *dst, unsigned char dloc, struct maple_enode *src, unsigned long sloc) { - void *entry = ma_get_rcu_slot(src, sloc); + void *entry = mte_get_rcu_slot(src, sloc); if (mt_is_empty(entry) || xa_is_retry(entry)) entry = NULL; - ma_set_rcu_slot(dst, dloc, entry); + mte_set_rcu_slot(dst, dloc, entry); } -static inline void ma_update_rcu_slot(const struct maple_enode *mn, +static inline void mte_update_rcu_slot(const struct maple_enode *mn, unsigned char slot, void *val) { - enum maple_type type = mt_node_type(mn); + enum maple_type type = mte_node_type(mn); switch (type) { case maple_range_64: case maple_leaf_64: - rcu_assign_pointer(mt_to_node(mn)->mr64.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->mr64.slot[slot], val); break; default: case maple_dense: - rcu_assign_pointer(mt_to_node(mn)->slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->slot[slot], val); break; case maple_arange_64: - rcu_assign_pointer(mt_to_node(mn)->ma64.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->ma64.slot[slot], val); break; case maple_sparse_6: - rcu_assign_pointer(mt_to_node(mn)->ms6.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->ms6.slot[slot], val); break; case maple_sparse_9: - rcu_assign_pointer(mt_to_node(mn)->ms9.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->ms9.slot[slot], val); break; case maple_sparse_16: - rcu_assign_pointer(mt_to_node(mn)->ms16.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->ms16.slot[slot], val); break; case maple_sparse_21: - rcu_assign_pointer(mt_to_node(mn)->ms21.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->ms21.slot[slot], val); break; case maple_sparse_32: - rcu_assign_pointer(mt_to_node(mn)->ms32.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->ms32.slot[slot], val); break; case maple_sparse_64: - rcu_assign_pointer(mt_to_node(mn)->ms64.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->ms64.slot[slot], val); break; case maple_range_16: case maple_leaf_16: - rcu_assign_pointer(mt_to_node(mn)->mr16.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->mr16.slot[slot], val); break; case maple_range_32: case maple_leaf_32: - rcu_assign_pointer(mt_to_node(mn)->mr32.slot[slot], val); + rcu_assign_pointer(mte_to_node(mn)->mr32.slot[slot], val); break; } } @@ -729,77 +724,77 @@ static inline unsigned long _ma_get_gap(const struct maple_node *mn, return 0; } } -static inline unsigned long ma_get_gap(const struct maple_enode *mn, +static inline unsigned long mte_get_gap(const struct maple_enode *mn, unsigned char gap) { - return _ma_get_gap(mt_to_node(mn), gap, mt_node_type(mn)); + return _ma_get_gap(mte_to_node(mn), gap, mte_node_type(mn)); } -static inline void ma_set_gap(const struct maple_enode *mn, +static inline void mte_set_gap(const struct maple_enode *mn, unsigned char gap, unsigned long val) { - enum maple_type type = mt_node_type(mn); + enum maple_type type = mte_node_type(mn); switch (type) { default: break; case maple_arange_64: - mt_to_node(mn)->ma64.gap[gap] = val; + mte_to_node(mn)->ma64.gap[gap] = val; break; } } -static inline void ma_cp_gap(struct maple_enode *dst, +static inline void mte_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)); + mte_set_gap(dst, dloc, mte_get_gap(src, sloc)); } -static inline void mas_update_limits(struct ma_state *ms, unsigned char slot, +static inline void mas_update_limits(struct ma_state *mas, unsigned char slot, enum maple_type type) { if (slot > 0) - ms->min = _ma_get_pivot(ms->node, slot - 1, type) + 1; + mas->min = _mte_get_pivot(mas->node, slot - 1, type) + 1; if (slot < mt_pivots[type]) - ms->max = _ma_get_pivot(ms->node, slot, type); + mas->max = _mte_get_pivot(mas->node, slot, type); } -static inline void ma_encoded_parent(struct ma_state *mas) +static inline void mas_encoded_parent(struct ma_state *mas) { struct maple_enode *p_enode, *gp_enode; enum maple_type ptype, gptype; unsigned char slot; - ptype = mt_parent_enum(mas, mas->node); - p_enode = mt_mk_node(mt_parent(mas->node), ptype); - if (_ma_is_root(mt_parent(mas->node))) { + ptype = mas_parent_enum(mas, mas->node); + p_enode = mt_mk_node(mte_parent(mas->node), ptype); + if (_ma_is_root(mte_parent(mas->node))) { mas->node = p_enode; - ma_set_slot(mas, 0); // No slot. + mas_set_slot(mas, 0); // No slot. mas->min = 0; mas->max = mt_max[ptype]; return; } - gptype = mt_parent_enum(mas, p_enode); - gp_enode = mt_mk_node(mt_parent(p_enode), gptype); - slot = mt_parent_slot(p_enode); + gptype = mas_parent_enum(mas, p_enode); + gp_enode = mt_mk_node(mte_parent(p_enode), gptype); + slot = mte_parent_slot(p_enode); mas->node = gp_enode; - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); mas_update_limits(mas, slot, gptype); mas->node = p_enode; } -/* ma_get_prev_pivot() - Return the previous pivot. +/* mas_get_prev_pivot() - Return the previous pivot. * * Mainly for extracting the previous pivot in the case of slot = 0. * Walk up the tree until the minimum changes, then get the previous pivot. * */ -static inline unsigned long ma_get_prev_pivot(const struct ma_state *mas, +static inline unsigned long mas_get_prev_pivot(const struct ma_state *mas, unsigned char slot) { unsigned char p_slot = MAPLE_NODE_SLOTS; // parent slot. if (slot > 0) - return ma_get_safe_pivot(mas, slot - 1); + return mas_get_safe_pivot(mas, slot - 1); if (mas->min == 0) return 0; @@ -810,16 +805,16 @@ static inline unsigned long ma_get_prev_pivot(const struct ma_state *mas, prev_piv.min = mas->min; while (prev_piv.min == mas->min) { - p_slot = mt_parent_slot(prev_piv.node); - ma_encoded_parent(&prev_piv); + p_slot = mte_parent_slot(prev_piv.node); + mas_encoded_parent(&prev_piv); if (p_slot) break; } p_slot--; - return ma_get_pivot(prev_piv.node, slot); + return mte_get_pivot(prev_piv.node, slot); } -static inline struct maple_node *ma_next_alloc(struct ma_state *ms) +static inline struct maple_node *mas_next_alloc(struct ma_state *ms) { int cnt; struct maple_node *mn, *smn; @@ -827,8 +822,8 @@ static inline struct maple_node *ma_next_alloc(struct ma_state *ms) if (!ms->alloc) return NULL; - cnt = ma_get_alloc_cnt(ms); - mn = ma_get_alloc(ms); + cnt = mas_get_alloc_cnt(ms); + mn = mas_get_alloc(ms); if (cnt == 1) { ms->alloc = NULL; } else { @@ -851,14 +846,14 @@ static inline struct maple_node *ma_next_alloc(struct ma_state *ms) return mn; } -static inline void ma_push_node(struct ma_state *mas, struct maple_enode *used) +static inline void mas_push_node(struct ma_state *mas, struct maple_enode *used) { - struct maple_node *reuse = mt_to_node(used); - struct maple_node *node = ma_get_alloc(mas); + struct maple_node *reuse = mte_to_node(used); + struct maple_node *node = mas_get_alloc(mas); int cnt; memset(reuse, 0, sizeof(*reuse)); - cnt = ma_get_alloc_cnt(mas); + cnt = mas_get_alloc_cnt(mas); if (cnt == 0) { mas->alloc = reuse; } else if (cnt <= 16) { @@ -871,20 +866,20 @@ static inline void ma_push_node(struct ma_state *mas, struct maple_enode *used) smn = node->slot[cnt/15]; smn->slot[cnt % 15] = reuse; } - if (cnt != ma_get_alloc_cnt(mas) + 1) + if (cnt != mas_get_alloc_cnt(mas) + 1) BUG_ON(0); } -static inline void ma_new_node(struct ma_state *ms, gfp_t gfp) +static inline void mas_node_node(struct ma_state *ms, gfp_t gfp) { struct maple_node *mn, *smn; - int req = ma_get_alloc_req(ms); - int allocated = ma_get_alloc_cnt(ms); + int req = mas_get_alloc_req(ms); + int allocated = mas_get_alloc_cnt(ms); int slot; if (!req) return; - mn = ma_get_alloc(ms); + mn = mas_get_alloc(ms); if (!mn) { mn = mt_alloc_one(gfp); if (!mn) @@ -917,7 +912,7 @@ static inline void ma_new_node(struct ma_state *ms, gfp_t gfp) } slot_failed: - ma_set_alloc_req(ms, req); + mas_set_alloc_req(ms, req); list_failed: if (req > 0) @@ -925,13 +920,13 @@ list_failed: } // Free the allocations. -static inline void mas_free_alloc(struct maple_node *node) +static inline void ma_free_alloc(struct maple_node *node) { int alloc = 0; while (alloc < MAPLE_NODE_SLOTS && node->slot[alloc]) { if (ma_mnode_ptr(node->slot[alloc])->slot[0]) - mas_free_alloc(node->slot[alloc]); + ma_free_alloc(node->slot[alloc]); else kfree(node->slot[alloc]); alloc++; @@ -947,35 +942,35 @@ bool mas_nomem(struct ma_state *ms, gfp_t gfp) __must_hold(ms->tree->lock) { if (ms->node != MA_ERROR(-ENOMEM)) { - struct maple_node *node = ma_get_alloc(ms); + struct maple_node *node = mas_get_alloc(ms); if (node) - mas_free_alloc(node); + ma_free_alloc(node); ms->alloc = NULL; return false; } if (gfpflags_allow_blocking(gfp)) { mtree_unlock(ms->tree); - ma_new_node(ms, gfp); + mas_node_node(ms, gfp); mtree_lock(ms->tree); } else { - ma_new_node(ms, gfp); + mas_node_node(ms, gfp); } - if (!ma_get_alloc(ms)) + if (!mas_get_alloc(ms)) return false; ms->node = MAS_START; return true; } static inline struct maple_node *mas_node_cnt(struct ma_state *ms, int count) { - int allocated = ma_get_alloc_cnt(ms); + int allocated = mas_get_alloc_cnt(ms); BUG_ON(count > 127); if (allocated < count) { - ma_set_alloc_req(ms, count - allocated); - ma_new_node(ms, GFP_NOWAIT | __GFP_NOWARN); + mas_set_alloc_req(ms, count - allocated); + mas_node_node(ms, GFP_NOWAIT | __GFP_NOWARN); } return ms->alloc; } @@ -988,10 +983,10 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) if (mas->index > 0) return NULL; mas->node = MAS_ROOT; - ma_set_slot(mas, MAPLE_NODE_SLOTS); + mas_set_slot(mas, MAPLE_NODE_SLOTS); return NULL; } - struct maple_enode *root = mt_safe_root( + struct maple_enode *root = mte_safe_root( mas->tree->ma_root); mas->max = mt_node_max(root); return root; @@ -1002,7 +997,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) /* Private * Returns the last slot that contains data. */ -static inline unsigned char ma_data_end(const struct ma_state *mas, +static inline unsigned char mas_data_end(const struct ma_state *mas, const enum maple_type type, unsigned long *last_piv, unsigned char *coalesce) { @@ -1011,9 +1006,9 @@ static inline unsigned char ma_data_end(const struct ma_state *mas, struct maple_enode *mn = mas->node; *coalesce = 0; - prev_piv = _ma_get_safe_pivot(mas, 0, type); + prev_piv = _mas_get_safe_pivot(mas, 0, type); for (data_end = 1; data_end < mt_slot_count(mn); data_end++) { - *last_piv = _ma_get_safe_pivot(mas, data_end, type); + *last_piv = _mas_get_safe_pivot(mas, data_end, type); if (*last_piv == 0) { *last_piv = prev_piv; return data_end - 1; @@ -1021,7 +1016,7 @@ static inline unsigned char ma_data_end(const struct ma_state *mas, if (prev_piv == *last_piv) (*coalesce)++; - else if (mt_will_coalesce(_ma_get_rcu_slot(mn, data_end, type))) + else if (mt_will_coalesce(_mte_get_rcu_slot(mn, data_end, type))) (*coalesce)++; if (*last_piv == mas->max) @@ -1046,36 +1041,36 @@ static inline unsigned char ma_hard_data(unsigned long end, return end - coalesce; } -#define ma_calc_split ma_no_dense_calc_split +#define mas_calc_split mas_no_dense_calc_split -static inline unsigned char ma_no_dense_calc_split(struct ma_state *mas, +static inline unsigned char mas_no_dense_calc_split(struct ma_state *mas, struct maple_enode **left, struct maple_enode **right) { char i, j; unsigned long min = mas->min; unsigned long max = min; - enum maple_type type = mt_node_type(mas->node); + enum maple_type type = mte_node_type(mas->node); unsigned long pivot_cnt = mt_pivots[type]; unsigned long half = mt_slots[type] / 2; unsigned long last_pivot; unsigned char coalesce; - unsigned char data_end = ma_data_end(mas, type, &last_pivot, &coalesce); + unsigned char data_end = mas_data_end(mas, type, &last_pivot, &coalesce); - *left = (struct maple_enode *)ma_next_alloc(mas); + *left = (struct maple_enode *)mas_next_alloc(mas); *left = mt_mk_node(ma_mnode_ptr(*left), type); - *right = (struct maple_enode *)ma_next_alloc(mas); + *right = (struct maple_enode *)mas_next_alloc(mas); *right = mt_mk_node(ma_mnode_ptr(*right), type); - if (ma_get_pivot(mas->node, half) > mas->index) + if (mte_get_pivot(mas->node, half) > mas->index) return half; return half + 1; - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) return half; for (i = 0; i < data_end; i++) { - max = ma_get_pivot(mas->node, i); + max = mte_get_pivot(mas->node, i); if (max == mt_max[type] && i) return i - 1; @@ -1093,14 +1088,14 @@ static inline unsigned char ma_no_dense_calc_split(struct ma_state *mas, return i; if (data_end < pivot_cnt) - max = ma_get_pivot(mas->node, data_end); + max = mte_get_pivot(mas->node, data_end); else max = mas->max; j = data_end; do { j--; - min = ma_get_pivot(mas->node, j); + min = mte_get_pivot(mas->node, j); if ((max - min) > 15) { j++; break; @@ -1112,29 +1107,29 @@ static inline unsigned char ma_no_dense_calc_split(struct ma_state *mas, return half; } -static inline unsigned char ma_dense_calc_split(struct ma_state *mas, +static inline unsigned char mas_dense_calc_split(struct ma_state *mas, struct maple_enode **left, struct maple_enode **right) { char i, j; unsigned long min = mas->min; unsigned long max = min; - enum maple_type type = mt_node_type(mas->node); + enum maple_type type = mte_node_type(mas->node); unsigned long pivot_cnt = mt_pivots[type]; unsigned long half = mt_slots[type] / 2; unsigned long last_pivot; unsigned char coalesce; - unsigned char data_end = ma_data_end(mas, type, &last_pivot, &coalesce); + unsigned char data_end = mas_data_end(mas, type, &last_pivot, &coalesce); - if (ma_is_root(mas->node)) { + if (mte_is_root(mas->node)) { i = half; - *left = (struct maple_enode *)ma_next_alloc(mas); - *right = (struct maple_enode *)ma_next_alloc(mas); + *left = (struct maple_enode *)mas_next_alloc(mas); + *right = (struct maple_enode *)mas_next_alloc(mas); goto even_split; } - *left = (struct maple_enode *)ma_next_alloc(mas); + *left = (struct maple_enode *)mas_next_alloc(mas); for (i = 0; i < data_end; i++) { - max = ma_get_pivot(mas->node, i); + max = mte_get_pivot(mas->node, i); if ((max - min) > 15) { if (i) i--; @@ -1145,7 +1140,7 @@ static inline unsigned char ma_dense_calc_split(struct ma_state *mas, if (i >= data_end) { *left = mt_mk_node(ma_mnode_ptr(*left), maple_dense); if (mas->last >= mas->min + mt_max[type]) { - *right = (struct maple_enode *)ma_next_alloc(mas); + *right = (struct maple_enode *)mas_next_alloc(mas); *right = mt_mk_node(ma_mnode_ptr(*right), type); } if (!i) @@ -1153,7 +1148,7 @@ static inline unsigned char ma_dense_calc_split(struct ma_state *mas, return i; } - *right = (struct maple_enode *)ma_next_alloc(mas); + *right = (struct maple_enode *)mas_next_alloc(mas); if (i >= half) { *left = mt_mk_node(ma_mnode_ptr(*left), maple_dense); *right = mt_mk_node(ma_mnode_ptr(*right), type); @@ -1161,14 +1156,14 @@ static inline unsigned char ma_dense_calc_split(struct ma_state *mas, } if (data_end < pivot_cnt) - max = ma_get_pivot(mas->node, data_end); + max = mte_get_pivot(mas->node, data_end); else max = mas->max; j = data_end; do { j--; - min = ma_get_pivot(mas->node, j); + min = mte_get_pivot(mas->node, j); if ((max - min) > 15) { j++; break; @@ -1186,7 +1181,7 @@ even_split: return i > 2 ? i : half - 1; } -static inline void ma_dense_cp(struct ma_state *mas, struct ma_cp *cp) +static inline void mas_dense_cp(struct ma_state *mas, struct ma_cp *cp) { unsigned char sloc = cp->src_start; // src location unsigned char pivot_cnt = mt_pivot_count(cp->src); @@ -1196,16 +1191,16 @@ static inline void ma_dense_cp(struct ma_state *mas, struct ma_cp *cp) if (!sloc) min = mas->min; else - min = ma_get_pivot(cp->src, sloc - 1) + 1; + min = mte_get_pivot(cp->src, sloc - 1) + 1; piv = min; while (sloc <= cp->src_end) { unsigned long end; unsigned char slot, end_slot; - ptr = ma_get_rcu_slot(cp->src, sloc); + ptr = mte_get_rcu_slot(cp->src, sloc); if (sloc < pivot_cnt) { - end = ma_get_pivot(cp->src, sloc); + end = mte_get_pivot(cp->src, sloc); } else { if (!ptr) break; @@ -1215,23 +1210,23 @@ static inline void ma_dense_cp(struct ma_state *mas, struct ma_cp *cp) slot = piv - min; end_slot = end - min; for (; slot <= end_slot; slot++) - ma_set_rcu_slot(cp->dst, slot, ptr); + mte_set_rcu_slot(cp->dst, slot, ptr); piv = end + 1; sloc++; } } -static inline unsigned long ma_leaf_max_gap(struct ma_state *mas) +static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) { - enum maple_type mt = mt_node_type(mas->node); + enum maple_type mt = mte_node_type(mas->node); unsigned long max_gap = 0; unsigned long gap = 0; unsigned long pstart, pend; if (mt == maple_dense) { for (int i = 0; i < mt_slot_count(mas->node); i++) { - if (ma_get_rcu_slot(mas->node, i)) { + if (mte_get_rcu_slot(mas->node, i)) { if (gap > max_gap) max_gap = gap; gap = 0; @@ -1246,7 +1241,7 @@ static inline unsigned long ma_leaf_max_gap(struct ma_state *mas) pstart = mas->min; for (int i = 0; i < mt_slots[mt]; i++) { - pend = ma_get_safe_pivot(mas, i); + pend = mas_get_safe_pivot(mas, i); if (i && !pend) break; @@ -1257,7 +1252,7 @@ static inline unsigned long ma_leaf_max_gap(struct ma_state *mas) gap = mas->max - pstart; } - if (ma_get_rcu_slot(mas->node, i)) + if (mte_get_rcu_slot(mas->node, i)) goto next; if (!gap) @@ -1276,7 +1271,7 @@ done: return max_gap; } -static inline unsigned long ma_max_gap(struct ma_state *mas, +static inline unsigned long mas_max_gap(struct ma_state *mas, unsigned char *slot) { unsigned long max_gap = 0; @@ -1285,7 +1280,7 @@ static inline unsigned long ma_max_gap(struct ma_state *mas, for (i = 0; i < mt_slot_count(mas->node); i++) { unsigned long gap; - gap = ma_get_gap(mas->node, i); + gap = mte_get_gap(mas->node, i); if (gap > max_gap) { *slot = i; max_gap = gap; @@ -1294,47 +1289,47 @@ static inline unsigned long ma_max_gap(struct ma_state *mas, return max_gap; } -static inline void ma_parent_gap(struct ma_state *mas, unsigned char slot, +static inline void mas_parent_gap(struct ma_state *mas, unsigned char slot, unsigned long new) { unsigned long max_gap = 0; unsigned char max_slot = 0; - ma_encoded_parent(mas); - ma_set_gap(mas->node, slot, new); + mas_encoded_parent(mas); + mte_set_gap(mas->node, slot, new); - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) return; - max_gap = ma_max_gap(mas, &max_slot); + max_gap = mas_max_gap(mas, &max_slot); if (slot == max_slot || max_gap < new) - ma_parent_gap(mas, mt_parent_slot(mas->node), new); + mas_parent_gap(mas, mte_parent_slot(mas->node), new); } /* Private */ -static inline void ma_update_gap(struct ma_state *mas) +static inline void mas_update_gap(struct ma_state *mas) { unsigned char pslot; unsigned long p_gap, max_gap = 0; - if (!mt_is_leaf(mas->node)) + if (!mte_is_leaf(mas->node)) return; - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) return; /* Get the largest gap in this leaf and check it against the reported * largest. */ - max_gap = ma_leaf_max_gap(mas); - pslot = mt_parent_slot(mas->node); - p_gap = _ma_get_gap(mt_parent(mas->node), pslot, - mt_parent_enum(mas, mas->node)); + max_gap = mas_leaf_max_gap(mas); + pslot = mte_parent_slot(mas->node); + p_gap = _ma_get_gap(mte_parent(mas->node), pslot, + mas_parent_enum(mas, mas->node)); if (p_gap != max_gap) - ma_parent_gap(mas, pslot, max_gap); + mas_parent_gap(mas, pslot, max_gap); } @@ -1349,25 +1344,25 @@ static inline void ma_update_gap(struct ma_state *mas) static inline unsigned long mas_first_node(struct ma_state *mas, unsigned long max) { - unsigned char slot = ma_get_slot(mas) - 1; + unsigned char slot = mas_get_slot(mas) - 1; unsigned char count = mt_slot_count(mas->node); while (++slot < count) { struct maple_enode *mn; unsigned long pivot; - pivot = ma_get_safe_pivot(mas, slot); + pivot = mas_get_safe_pivot(mas, slot); if (pivot > max) goto no_entry; - mn = ma_get_rcu_slot(mas->node, slot); + mn = mte_get_rcu_slot(mas->node, slot); if (mt_is_empty(mn)) continue; - if (!mt_is_leaf(mas->node)) + if (!mte_is_leaf(mas->node)) mas->node = mn; - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); return pivot; } @@ -1390,18 +1385,18 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, if (mas->node == MAS_NONE) return pivot; - if (mt_is_leaf(mas->node)) + if (mte_is_leaf(mas->node)) return pivot; - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); } } -void ma_destroy_walk(struct maple_enode *mn) +void mte_destroy_walk(struct maple_enode *mn) { struct maple_enode *node; - unsigned int type = mt_node_type(mn); + unsigned int type = mte_node_type(mn); unsigned char slot_cnt = mt_slot_count(mn); int i; @@ -1411,22 +1406,22 @@ void ma_destroy_walk(struct maple_enode *mn) case maple_range_64: case maple_arange_64: for (i = 0; i < slot_cnt; i++) { - node = ma_get_rcu_slot(mn, i); + node = mte_get_rcu_slot(mn, i); if (!mt_is_empty(node)) - ma_destroy_walk(node); + mte_destroy_walk(node); } break; default: break; } - mt_free(mt_to_node(mn)); + mte_free(mn); } -static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) +static inline void mas_copy(struct ma_state *mas, struct ma_cp *cp) { unsigned char sloc = cp->src_start; // src location unsigned char dloc = cp->dst_start; // dst location - enum maple_type type = mt_node_type(cp->src); + enum maple_type type = mte_node_type(cp->src); enum maple_type dtype; unsigned char pivot_cnt = mt_pivots[type]; unsigned long piv, prev_piv = mas->min; @@ -1437,14 +1432,14 @@ 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 = mt_mk_node(ma_next_alloc(mas), type); + cp->dst = mt_mk_node(mas_next_alloc(mas), type); } if (!mt_pivot_count(cp->dst)) { - ma_dense_cp(mas, cp); + mas_dense_cp(mas, cp); return; } - dtype = mt_node_type(cp->dst); + dtype = mte_node_type(cp->dst); while (sloc <= cp->src_end && dloc <= cp->dst_end) { @@ -1453,15 +1448,15 @@ static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) break; if (sloc < pivot_cnt) - piv = ma_get_pivot(cp->src, sloc); + piv = mte_get_pivot(cp->src, sloc); else piv = mas->max; // Last entry. if (dloc && (piv == mas->max || !piv)) { - if (!ma_get_rcu_slot(cp->dst, dloc -1) && - ! ma_get_rcu_slot(cp->src, sloc)) { - ma_set_pivot(cp->dst, dloc -1, 0); + if (!mte_get_rcu_slot(cp->dst, dloc -1) && + ! mte_get_rcu_slot(cp->src, sloc)) { + mte_set_pivot(cp->dst, dloc -1, 0); break; } } @@ -1476,12 +1471,12 @@ static inline void ma_copy(struct ma_state *mas, struct ma_cp *cp) goto next_src_slot; if (dloc < pivot_cnt) - ma_set_pivot(cp->dst, dloc, piv); + mte_set_pivot(cp->dst, dloc, piv); if (dtype == maple_arange_64) - ma_cp_gap(cp->dst, dloc, cp->src, sloc); + mte_cp_gap(cp->dst, dloc, cp->src, sloc); - ma_cp_rcu_slot(cp->dst, dloc++, cp->src, sloc); + mte_cp_rcu_slot(cp->dst, dloc++, cp->src, sloc); prev_piv = piv; next_src_slot: sloc++; @@ -1490,13 +1485,13 @@ next_src_slot: cp->dst_start = dloc; cp->src_start = sloc; } -static inline int ma_split_data(struct ma_state *mas, struct maple_enode *left, +static inline int mas_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); - ma_copy(mas, &cp); + mas_copy(mas, &cp); cp.src_start = split + 1; if (cp.src_start > mt_node_max(mas->node)) @@ -1506,83 +1501,79 @@ static inline int ma_split_data(struct ma_state *mas, struct maple_enode *left, if (right) { cp.dst = right; cp.dst_start = 0; - ma_copy(mas, &cp); + mas_copy(mas, &cp); } return split; } -static inline void ma_adopt_children(struct maple_enode *parent) +static inline void mte_adopt_children(struct maple_enode *parent) { - enum maple_type type = mt_node_type(parent); + enum maple_type type = mte_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 && - _ma_get_pivot(parent, slot, type) == 0) + _mte_get_pivot(parent, slot, type) == 0) break; - child = _ma_get_rcu_slot(parent, slot, type); + child = _mte_get_rcu_slot(parent, slot, type); if (child) - mt_set_parent(child, parent, slot); + mte_set_parent(child, parent, slot); } -} -static inline void ma_recursive_adopt(struct maple_enode *parent) -{ - } /* Private - * _mt_replace() - Replace a maple node in the tree with mas->node. Uses the + * _mas_replace() - Replace a maple node in the tree with mas->node. Uses the * parent encoding to locate the maple node in the tree. * @free: Free the old node * @push: push the old node onto the allocated nodes in mas->alloc * */ -static inline void _mt_replace(struct ma_state *mas, bool free, bool push) +static inline void _mas_replace(struct ma_state *mas, bool free, bool push) { - struct maple_node *mn = mt_to_node(mas->node); + struct maple_node *mn = mte_to_node(mas->node); struct maple_enode *parent = NULL; struct maple_enode *prev; unsigned char slot = 0; - if (ma_is_root(mas->node)) { + if (mte_is_root(mas->node)) { prev = mas->tree->ma_root; } else { - enum maple_type ptype = mt_parent_enum(mas, mas->node); + enum maple_type ptype = mas_parent_enum(mas, mas->node); - parent = mt_mk_node(mt_parent(mas->node), ptype); - slot = mt_parent_slot(mas->node); - prev = ma_get_rcu_slot(parent, slot); + parent = mt_mk_node(mte_parent(mas->node), ptype); + slot = mte_parent_slot(mas->node); + prev = mte_get_rcu_slot(parent, slot); } - if (mt_to_node(prev) == mn) + if (mte_to_node(prev) == mn) return; - if (!mt_is_leaf(mas->node)) - ma_adopt_children(mas->node); + if (!mte_is_leaf(mas->node)) + mte_adopt_children(mas->node); - if (ma_is_root(mas->node)) { + if (mte_is_root(mas->node)) { mn->parent = ma_parent_ptr( ((unsigned long)mas->tree | MA_ROOT_PARENT)); - rcu_assign_pointer(mas->tree->ma_root, mt_mk_root(mas->node)); + rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); } else { - ma_update_rcu_slot(parent, slot, mas->node); + mte_update_rcu_slot(parent, slot, mas->node); } if (free) { - mt_free(mt_to_node(prev)); + mte_free(prev); return; } if (push) - ma_push_node(mas, prev); + mas_push_node(mas, prev); } -static inline void mt_replace(struct ma_state *mas) +static inline void mas_replace(struct ma_state *mas) { - _mt_replace(mas, true, false); + _mas_replace(mas, true, false); } /* Private @@ -1597,15 +1588,15 @@ static inline void mas_partial_copy(struct ma_state *mas, unsigned char end) { MA_CP(cp, mas->node, NULL, 0, end); - ma_copy(mas, &cp); + mas_copy(mas, &cp); if (mas_is_err(mas)) return; - mt_to_node(cp.dst)->parent = mt_to_node(cp.src)->parent; + mte_to_node(cp.dst)->parent = mte_to_node(cp.src)->parent; mas->node = cp.dst; } -static inline void ma_gap_link(struct ma_state *mas, struct maple_enode *parent, +static inline void mas_gap_link(struct ma_state *mas, struct maple_enode *parent, unsigned char slot, unsigned long pivot) { unsigned long gap, max; @@ -1613,29 +1604,29 @@ static inline void ma_gap_link(struct ma_state *mas, struct maple_enode *parent, max = mas->max; if (slot) - mas->min = ma_get_pivot(parent, slot - 1) + 1; + mas->min = mte_get_pivot(parent, slot - 1) + 1; mas->max = pivot; - if (!mt_is_leaf(mas->node)) - gap = ma_max_gap(mas, &max_slot); + if (!mte_is_leaf(mas->node)) + gap = mas_max_gap(mas, &max_slot); else - gap = ma_leaf_max_gap(mas); + gap = mas_leaf_max_gap(mas); - ma_set_gap(parent, slot, gap); + mte_set_gap(parent, slot, gap); mas->max = max; } -static inline void ma_link(struct maple_enode *new, struct maple_enode *parent, +static inline void mte_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]; - mt_set_parent(new, parent, slot); + mte_set_parent(new, parent, slot); if (slot < pivot_cnt) - ma_set_pivot(parent, slot, pivot); + mte_set_pivot(parent, slot, pivot); - ma_set_rcu_slot(parent, slot, new); - if (!mt_is_leaf(new)) - ma_adopt_children(new); + mte_set_rcu_slot(parent, slot, new); + if (!mte_is_leaf(new)) + mte_adopt_children(new); } /* @@ -1654,7 +1645,7 @@ static inline void ma_link(struct maple_enode *new, struct maple_enode *parent, * 8. set up ma_state for return. * */ -static inline int ma_split(struct ma_state *mas, unsigned char slot, +static inline int mas_split(struct ma_state *mas, unsigned char slot, bool active) { struct maple_enode *full = mas->node; @@ -1665,7 +1656,7 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot, unsigned long pivot; unsigned long p_max = 0; - if (ma_is_root(mas->node)) { + if (mte_is_root(mas->node)) { old_parent = full; if (mt_is_alloc(mas->tree)) ptype = maple_arange_64; @@ -1676,27 +1667,27 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot, unsigned long last_pivot; unsigned char coalesce; - p_slot = mt_parent_slot(mas->node); - ma_encoded_parent(mas); + p_slot = mte_parent_slot(mas->node); + mas_encoded_parent(mas); old_parent = mas->node; - ptype = mt_node_type(mas->node); - p_end = ma_data_end(mas, ptype, &last_pivot, &coalesce); + ptype = mte_node_type(mas->node); + p_end = mas_data_end(mas, ptype, &last_pivot, &coalesce); if (p_end - coalesce >= mt_slots[ptype] - 1) { /* Must split the parent */ - split = ma_split(mas, p_slot, active); + split = mas_split(mas, p_slot, active); if (mas_is_err(mas)) return 0; if (split < p_slot) p_slot -= split + 1; // Split will return the parent. old_parent = mas->node; - ma_set_slot(mas, p_slot); + mas_set_slot(mas, p_slot); } - ptype = mt_node_type(mas->node); + ptype = mte_node_type(mas->node); p_max = mas->max; - p_end = ma_data_end(mas, ptype, &last_pivot, &coalesce); + p_end = mas_data_end(mas, ptype, &last_pivot, &coalesce); mas_update_limits(mas, p_slot, ptype); - mas->node = ma_get_rcu_slot(old_parent, p_slot); + mas->node = mte_get_rcu_slot(old_parent, p_slot); } mas_node_cnt(mas, 3); @@ -1705,10 +1696,10 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot, } // Allocations. - new_parent = mt_mk_node(ma_next_alloc(mas), ptype); + new_parent = mt_mk_node(mas_next_alloc(mas), ptype); // Copy the parents information - if (!ma_is_root(full)) { + if (!mte_is_root(full)) { unsigned long c_max = mas->max; mas->max = p_max; @@ -1716,42 +1707,42 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot, // replaced. MA_CP(cp, old_parent, new_parent, 0, p_slot - 1); if (p_slot) - ma_copy(mas, &cp); + mas_copy(mas, &cp); if (p_slot < mt_slots[ptype] - 2) { cp.src_start = p_slot + 1; cp.dst_start += 2; cp.src_end = p_end; - ma_copy(mas, &cp); + mas_copy(mas, &cp); } mas->max = c_max; } // calculate the split location. - split = ma_calc_split(mas, &left, &right); + split = mas_calc_split(mas, &left, &right); // the node type for the children types. // Node types must be set to copy data into them. - ma_split_data(mas, left, right, split); + mas_split_data(mas, left, right, split); if (right) { - pivot = ma_get_pivot(left, split); + pivot = mte_get_pivot(left, split); if (!pivot) // dense node pivot = mas->min + split - 1; } else { pivot = mt_node_max(left); - if (!p_slot || mt_node_type(left) == maple_dense) + if (!p_slot || mte_node_type(left) == maple_dense) pivot += mas->min; else - pivot += ma_get_pivot(new_parent, p_slot - 1); + pivot += mte_get_pivot(new_parent, p_slot - 1); } - ma_link(left, new_parent, p_slot, pivot, ptype); + mte_link(left, new_parent, p_slot, pivot, ptype); if (right) { unsigned long r_max = mas->max; if (mt_node_max(right) < mas->max) r_max = pivot + mt_node_max(right); - ma_link(right, new_parent, p_slot + 1, r_max, ptype); + mte_link(right, new_parent, p_slot + 1, r_max, ptype); } if (mt_is_alloc(mas->tree)) { @@ -1759,22 +1750,22 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot, unsigned long min = mas->min; mas->node = right; - ma_gap_link(mas, new_parent, p_slot + 1, mas->max); + mas_gap_link(mas, new_parent, p_slot + 1, mas->max); mas->min = min; } mas->node = left; - ma_gap_link(mas, new_parent, p_slot, pivot); + mas_gap_link(mas, new_parent, p_slot, pivot); } // Copy grand parent to the parent, including slot encoding. - mt_to_node(new_parent)->parent = mt_to_node(old_parent)->parent; + mte_to_node(new_parent)->parent = mte_to_node(old_parent)->parent; // Update encoded slots in children - ma_adopt_children(new_parent); + mte_adopt_children(new_parent); // Set up maple state to replace the parent node in the grandparent. mas->node = new_parent; // Replace the parent node & free the old parent. - _mt_replace(mas, active, true); + _mas_replace(mas, active, true); // Set up the ma_state for the return. Point to the correct node for // the insert or subsequent split. @@ -1800,17 +1791,17 @@ static inline int ma_split(struct ma_state *mas, unsigned char slot, // Free the full node. if (old_parent != full) { if (!active) - ma_push_node(mas, full); + mas_push_node(mas, full); else - mt_free(mt_to_node(full)); + mte_free(full); } return split; } -static inline enum maple_type ma_ptype_leaf(struct ma_state *mas) +static inline enum maple_type mas_ptype_leaf(struct ma_state *mas) { - enum maple_type pt = mt_node_type(mas->node); + enum maple_type pt = mte_node_type(mas->node); switch (pt) { case maple_arange_64: @@ -1821,26 +1812,26 @@ static inline enum maple_type ma_ptype_leaf(struct ma_state *mas) } /* Private * - * When inserting into non-leaf nodes in _ma_insert, a type is needed. + * When inserting into non-leaf nodes in _mas_insert, a type is needed. * * Try to determine that type here. */ -static inline enum maple_type ma_determine_type(struct ma_state *mas, +static inline enum maple_type mas_determine_type(struct ma_state *mas, unsigned long min, unsigned char slot) { struct maple_enode *sibling; unsigned char sibling_slot = slot; - enum maple_type stype, mt = ma_ptype_leaf(mas); + enum maple_type stype, mt = mas_ptype_leaf(mas); if (slot > 0) sibling_slot -= 1; else sibling_slot += 1; - sibling = ma_get_rcu_slot(mas->node, sibling_slot); + sibling = mte_get_rcu_slot(mas->node, sibling_slot); if (!sibling) return mt; - stype = mt_node_type(sibling); + stype = mte_node_type(sibling); if (mt_max[stype] >= min - mas->index) return stype; @@ -1849,9 +1840,9 @@ static inline enum maple_type ma_determine_type(struct ma_state *mas, -static inline int ma_add(struct ma_state *mas, void *entry, bool overwrite, +static inline int mas_add(struct ma_state *mas, void *entry, bool overwrite, bool active); -static inline int _ma_add_dense(struct ma_state *mas, void *entry, +static inline int _mas_add_dense(struct ma_state *mas, void *entry, unsigned char slot, bool overwrite, enum maple_type this_type, bool active) { @@ -1865,18 +1856,18 @@ static inline int _ma_add_dense(struct ma_state *mas, void *entry, // FIXME: Check entire range, not what we would insert this time. if (!overwrite) { do { - if (_ma_get_rcu_slot(mas->node, min++, this_type)) + if (_mte_get_rcu_slot(mas->node, min++, this_type)) return 0; } while (min < max); } do { - ma_update_rcu_slot(mas->node, min++, entry); + mte_update_rcu_slot(mas->node, min++, entry); } while (min < max); if (max != mas->last - mas->min) { mas->index = mas->min + max + 1; - ma_add(mas, entry, overwrite, active); + mas_add(mas, entry, overwrite, active); } ret = max - min + 1; @@ -1899,22 +1890,22 @@ static inline int _ma_add_dense(struct ma_state *mas, void *entry, * Returns the number of slots used on success, the slot number on failure. */ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry); -static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, +static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, bool active) { struct maple_enode *prev_enode = NULL; - enum maple_type this_type = mt_node_type(mas->node); + enum maple_type this_type = mte_node_type(mas->node); unsigned long last_piv; unsigned long max = mas->max; unsigned long min = mas->min; unsigned char slot_cnt = mt_slots[this_type] - 1; unsigned char pivot_cnt = mt_pivots[this_type]; unsigned char coalesce; - unsigned char slot = ma_get_slot(mas); + unsigned char slot = mas_get_slot(mas); bool spans_range = false; bool append = false; bool null_entry = false; - int old_end = ma_data_end(mas, this_type, &last_piv, &coalesce); + int old_end = mas_data_end(mas, this_type, &last_piv, &coalesce); int new_end = old_end; int ret = 1; @@ -1929,7 +1920,7 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, } /* Dense node type */ if (!pivot_cnt) { - ret = _ma_add_dense(mas, entry, slot, this_type, overwrite, + ret = _mas_add_dense(mas, entry, slot, this_type, overwrite, active); if (!ret) return ret; @@ -1941,12 +1932,12 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, /* Calculate the range of this slot */ // Set the range max - if (slot < pivot_cnt && ma_get_pivot(mas->node, slot) != 0) - max = ma_get_pivot(mas->node, slot); + if (slot < pivot_cnt && mte_get_pivot(mas->node, slot) != 0) + max = mte_get_pivot(mas->node, slot); // Set the range min. if (slot > 0) - min = ma_get_pivot(mas->node, slot - 1) + 1; + min = mte_get_pivot(mas->node, slot - 1) + 1; if (mas->last > max) spans_range = true; @@ -1957,7 +1948,7 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, if (spans_range) goto busy; - entry = ma_get_rcu_slot(mas->node, slot); + entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) goto busy; } @@ -1972,7 +1963,7 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, null_entry = true; if (mas->index == min && mas->last == max) { - ma_set_rcu_slot(mas->node, slot, entry); + mte_set_rcu_slot(mas->node, slot, entry); ret = 1; goto complete; } @@ -1988,7 +1979,7 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, // Detect duplicate null entries and don't copy them. if (null_entry && slot > 0) { - struct maple_enode *slot_val = ma_get_rcu_slot(mas->node, + struct maple_enode *slot_val = mte_get_rcu_slot(mas->node, slot - 1); if (!slot_val) { slot--; @@ -2000,7 +1991,7 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, new_end += ret - coalesce; if (new_end > slot_cnt) { /* Not enough space in the node */ - unsigned char split = ma_split(mas, slot, active); + unsigned char split = mas_split(mas, slot, active); if (mas_is_err(mas)) return 0; @@ -2009,13 +2000,13 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, if (split <= slot) slot = slot - split; - ma_set_slot(mas, slot); - return _ma_add(mas, entry, overwrite, active); + mas_set_slot(mas, slot); + return _mas_add(mas, entry, overwrite, active); } prev_enode = mas->node; - if (!mt_is_leaf(mas->node)) { + if (!mte_is_leaf(mas->node)) { struct maple_enode *leaf; enum maple_type mt; // Old limits. @@ -2029,17 +2020,17 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, return 0; // Set the new leaf parent and type. - mt = ma_determine_type(mas, min, slot); - leaf = mt_mk_node(ma_next_alloc(mas), mt); - mt_set_parent(leaf, mas->node, slot); + mt = mas_determine_type(mas, min, slot); + leaf = mt_mk_node(mas_next_alloc(mas), mt); + mte_set_parent(leaf, mas->node, slot); // Put the new range in the new leaf. mas->node = leaf; mas->min = mas->index; mas->max = max; if (null_entry) child_slot = 1; - ma_set_slot(mas, child_slot); - _ma_add(mas, entry, overwrite, active); + mas_set_slot(mas, child_slot); + _mas_add(mas, entry, overwrite, active); // Restore old values and continue inserting. null_entry = false; mas->min = o_min; @@ -2068,33 +2059,33 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, */ /* Write the entry */ - ma_set_rcu_slot(mas->node, ++slot, entry); + mte_set_rcu_slot(mas->node, ++slot, entry); if (slot < pivot_cnt) - ma_set_pivot(mas->node, slot, mas->last); + mte_set_pivot(mas->node, slot, mas->last); /* Write NULL entry */ - ma_set_rcu_slot(mas->node, --slot, NULL); + mte_set_rcu_slot(mas->node, --slot, NULL); if (append) wmb(); /* NULL needs to be written before pivot. */ - ma_set_pivot(mas->node, slot, mas->index - 1); + mte_set_pivot(mas->node, slot, mas->index - 1); if (mt_is_alloc(mas->tree)) { unsigned long gap = mas->min; if (slot > 0) - gap = ma_get_pivot(mas->node, slot - 1); + gap = mte_get_pivot(mas->node, slot - 1); gap = (mas->index - 1) - gap; - ma_set_gap(mas->node, slot, gap); + mte_set_gap(mas->node, slot, gap); } slot += 2; } else { /* Write the entry */ - ma_set_rcu_slot(mas->node, slot, entry); + mte_set_rcu_slot(mas->node, slot, entry); if (old_end == new_end + 1) // Append. wmb(); /* Entry needs to be visible prior to pivot. */ if (slot < pivot_cnt) - ma_set_pivot(mas->node, slot++, mas->last); + mte_set_pivot(mas->node, slot++, mas->last); } /* Skip possible duplicate entry that contains a NULL */ @@ -2106,7 +2097,7 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, if (old_end >= slot_cnt -1 ) break; - if (ma_get_pivot(prev_enode, old_end) <= mas->last) + if (mte_get_pivot(prev_enode, old_end) <= mas->last) old_end++; else break; @@ -2118,16 +2109,16 @@ static inline int _ma_add(struct ma_state *mas, void *entry, bool overwrite, cp.dst_end = mt_slot_count(cp.dst) - 1; cp.start_piv = mas->last; cp.src_end = mt_slot_count(cp.src) - 1; // copy to the end to collapse last slot null. - ma_copy(mas, &cp); + mas_copy(mas, &cp); } complete: if (prev_enode != mas->node) - _mt_replace(mas, active, true); + _mas_replace(mas, active, true); update_gap: if (mt_is_alloc(mas->tree)) - ma_update_gap(mas); + mas_update_gap(mas); return ret; @@ -2135,31 +2126,31 @@ busy: mas_set_err(mas, -EBUSY); return 0; } -static inline int _ma_insert(struct ma_state *mas, void *entry, +static inline int _mas_insert(struct ma_state *mas, void *entry, unsigned char slot) { - ma_set_slot(mas, slot); - return _ma_add(mas, entry, false, true); + mas_set_slot(mas, slot); + return _mas_add(mas, entry, false, true); } static inline int _ma_store(struct ma_state *mas, void *entry, unsigned char slot) { - ma_set_slot(mas, slot); - return _ma_add(mas, entry, true, true); + mas_set_slot(mas, slot); + return _mas_add(mas, entry, true, true); } static inline void ma_root_expand(struct ma_state *ms, void *entry) { void *r_entry = rcu_dereference(ms->tree->ma_root); // root entry struct maple_node *mn; - enum maple_type mt = ma_ptype_leaf(ms); + enum maple_type mt = mas_ptype_leaf(ms); int slot = 0; mas_node_cnt(ms, 1); if (mas_is_err(ms)) return; - mn = ma_next_alloc(ms); + mn = mas_next_alloc(ms); ms->node = mt_mk_node(mn, mt); mn->parent = ma_parent_ptr( ((unsigned long)ms->tree | MA_ROOT_PARENT)); @@ -2167,13 +2158,13 @@ static inline void ma_root_expand(struct ma_state *ms, void *entry) if (ms->index != 0) { slot++; /* Assign the old entry to slot 0, or set it to null. */ - ma_set_rcu_slot(ms->node, 0, r_entry); + mte_set_rcu_slot(ms->node, 0, r_entry); if (!r_entry) - ma_set_pivot(ms->node, 0, ms->index - 1); + mte_set_pivot(ms->node, 0, ms->index - 1); } // FIXME: When task_size / page_size -1 works, check to ensure we are // not inserting above this. - _ma_insert(ms, entry, slot); + _mas_insert(ms, entry, slot); if (mas_is_err(ms)) return; @@ -2182,13 +2173,13 @@ static inline void ma_root_expand(struct ma_state *ms, void *entry) // FIXME: ms->index = TASK_SIZE / PAGE_SIZE - 1; ms->index = 0x2000000000000UL; ms->last = mt_max[mt]; - _ma_insert(ms, XA_ZERO_ENTRY, 2); + _mas_insert(ms, XA_ZERO_ENTRY, 2); if (mas_is_err(ms)) return; } /* swap the new root into the tree */ - rcu_assign_pointer(ms->tree->ma_root, mt_mk_root(ms->node)); + rcu_assign_pointer(ms->tree->ma_root, mte_mk_root(ms->node)); } static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot, @@ -2202,20 +2193,20 @@ static inline void mas_next_slot(struct ma_state *mas, unsigned long max) // walk up. while (1) { - slot = mt_parent_slot(mas->node); + slot = mte_parent_slot(mas->node); walk_again: - ma_encoded_parent(mas); + mas_encoded_parent(mas); if (mas->max > max) goto no_entry; if (slot < mt_slot_count(mas->node) - 1) { - if (!ma_get_safe_pivot(mas, slot + 1)) + if (!mas_get_safe_pivot(mas, slot + 1)) continue; slot++; goto walk_down; } - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) goto no_entry; } @@ -2224,9 +2215,9 @@ walk_down: do { void *entry = NULL; if (slot) - mas->min = ma_get_safe_pivot(mas, slot - 1); - mas->max = ma_get_safe_pivot(mas, slot); - entry = ma_get_rcu_slot(mas->node, slot); + mas->min = mas_get_safe_pivot(mas, slot - 1); + mas->max = mas_get_safe_pivot(mas, slot); + entry = mte_get_rcu_slot(mas->node, slot); if (xa_is_skip(entry)) { if (mas->max >= max) { goto no_entry; @@ -2242,14 +2233,14 @@ walk_down: if (mt_is_empty(mas->node)) goto no_entry; - if (mt_is_leaf(mas->node)) + if (mte_is_leaf(mas->node)) goto done; slot = 0; } while (1); done: - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); return; no_entry: @@ -2270,8 +2261,8 @@ static inline void mas_prev_slot(struct ma_state *mas, unsigned long min) // Walk up. while (1) { - slot = mt_parent_slot(mas->node); - ma_encoded_parent(mas); + slot = mte_parent_slot(mas->node); + mas_encoded_parent(mas); if (mas->min < min) goto no_entry; @@ -2279,28 +2270,28 @@ static inline void mas_prev_slot(struct ma_state *mas, unsigned long min) slot--; goto walk_down; } - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) goto no_entry; } walk_down: do { if (slot) - mas->min = ma_get_safe_pivot(mas, slot - 1); - mas->max = ma_get_safe_pivot(mas, slot); - mas->node = ma_get_rcu_slot(mas->node, slot); + mas->min = mas_get_safe_pivot(mas, slot - 1); + mas->max = mas_get_safe_pivot(mas, slot); + mas->node = mte_get_rcu_slot(mas->node, slot); if (mt_is_empty(mas->node)) goto done; - if (mt_is_leaf(mas->node)) + if (mte_is_leaf(mas->node)) goto done; - slot = ma_data_end(mas, mt_node_type(mas->node), &mas->max, + slot = mas_data_end(mas, mte_node_type(mas->node), &mas->max, &coalesce); } while (1); done: - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); return; no_entry: @@ -2310,7 +2301,7 @@ no_entry: /** Private * mas_prev_node() - Find the prev non-null entry at the same level in the - * tree. The prev value will be mas->node[ma_get_slot(mas)] or MAS_NONE. + * tree. The prev value will be mas->node[mas_get_slot(mas)] or MAS_NONE. */ static inline void mas_prev_node(struct ma_state *mas, unsigned long min) { @@ -2318,16 +2309,16 @@ static inline void mas_prev_node(struct ma_state *mas, unsigned long min) unsigned char slot; unsigned long start_piv; - slot = ma_get_slot(mas); - start_piv = ma_get_safe_pivot(mas, slot); + slot = mas_get_slot(mas); + start_piv = mas_get_safe_pivot(mas, slot); restart_prev_node: level = 0; - slot = ma_get_slot(mas); - if (ma_is_root(mas->node)) + slot = mas_get_slot(mas); + if (mte_is_root(mas->node)) goto no_entry; while (1) { - ma_encoded_parent(mas); + mas_encoded_parent(mas); level++; if (!mas_safe_slot(mas, &slot, -1)) @@ -2343,7 +2334,7 @@ restart_prev_node: do { struct maple_enode *mn; unsigned long last_pivot; - unsigned long pivot = ma_get_safe_pivot(mas, slot); + unsigned long pivot = mas_get_safe_pivot(mas, slot); unsigned char coalesce; if (pivot < min) @@ -2352,12 +2343,12 @@ restart_prev_node: if (slot != 0 && pivot == 0) break; - mn = ma_get_rcu_slot(mas->node, slot); + mn = mte_get_rcu_slot(mas->node, slot); if (!mn) continue; if (level == 1) { - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); mas->node = mn; if (mas_dead_node(mas, start_piv)) goto restart_prev_node; @@ -2366,15 +2357,15 @@ restart_prev_node: level--; mas->node = mn; - slot = ma_data_end(mas, mt_node_type(mn), &last_pivot, + slot = mas_data_end(mas, mte_node_type(mn), &last_pivot, &coalesce); } while (slot-- > 0); ascend: - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) goto no_entry; - slot = mt_parent_slot(mas->node); + slot = mte_parent_slot(mas->node); } no_entry: @@ -2383,7 +2374,7 @@ no_entry: /* * Find the next non-null entry at the same level in the tree. The next value - * will be mas->node[ma_get_slot(mas)] or MAS_NONE. + * will be mas->node[mas_get_slot(mas)] or MAS_NONE. * * * Node: Not safe to call with mas->node == root @@ -2402,14 +2393,14 @@ restart_next_node: unsigned long prev_piv; mn = mas->node; - slot = ma_get_slot(mas); - start_piv = ma_get_safe_pivot(mas, slot); + slot = mas_get_slot(mas); + start_piv = mas_get_safe_pivot(mas, slot); level++; - if (!ma_is_root(mas->node)) - ma_encoded_parent(mas); + if (!mte_is_root(mas->node)) + mas_encoded_parent(mas); if (!mas_safe_slot(mas, &slot, 1)) { - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) goto no_entry; goto restart_next_node; } @@ -2419,10 +2410,10 @@ restart_next_node: count = mt_slot_count(mas->node); - prev_piv = ma_get_safe_pivot(mas, slot); + prev_piv = mas_get_safe_pivot(mas, slot); while (++slot < count) { - unsigned long pivot = ma_get_safe_pivot(mas, slot); + unsigned long pivot = mas_get_safe_pivot(mas, slot); if (prev_piv > max) goto no_entry; @@ -2430,7 +2421,7 @@ restart_next_node: if (slot != 0 && pivot == 0) break; - mn = ma_get_rcu_slot(mas->node, slot); + mn = mte_get_rcu_slot(mas->node, slot); if (!mn) { prev_piv = pivot; continue; @@ -2440,7 +2431,7 @@ restart_next_node: mas->max = pivot; if (level == 1) { - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); mas->node = mn; if (mas_dead_node(mas, start_piv)) goto restart_next_node; @@ -2453,7 +2444,7 @@ restart_next_node: count = mt_slot_count(mas->node); } - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) goto no_entry; } @@ -2470,7 +2461,7 @@ static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long min, unsigned long *piv) { unsigned long pivot; - unsigned char slot = ma_get_slot(mas); + unsigned char slot = mas_get_slot(mas); void *entry; if (!slot) @@ -2478,12 +2469,12 @@ static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long min, slot--; do { - pivot = ma_get_safe_pivot(mas, slot); + pivot = mas_get_safe_pivot(mas, slot); if (pivot < min) goto no_entry; *piv = pivot; - entry = ma_get_rcu_slot(mas->node, slot); + entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) goto found; } while (slot--); @@ -2492,7 +2483,7 @@ no_entry: return false; found: - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); return true; } @@ -2503,19 +2494,19 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, unsigned long *piv) { unsigned long pivot = mas->min; - unsigned char slot = ma_get_slot(mas); + unsigned char slot = mas_get_slot(mas); unsigned char count = mt_slot_count(mas->node); void *entry; while (slot < count) { - pivot = ma_get_safe_pivot(mas, slot); + pivot = mas_get_safe_pivot(mas, slot); if (slot != 0 && pivot == 0) goto no_entry; *piv = pivot; - entry = ma_get_rcu_slot(mas->node, slot); + entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) goto found; @@ -2530,7 +2521,7 @@ no_entry: return false; found: - ma_set_slot(mas, slot); + mas_set_slot(mas, slot); return true; } @@ -2543,7 +2534,7 @@ static inline unsigned long mas_next_entry(struct ma_state *mas, if (mas->node == MAS_NONE) return max; - if (!mt_is_leaf(mas->node)) + if (!mte_is_leaf(mas->node)) pivot = mas_first_entry(mas, max); else { while (mas->node != MAS_NONE) { @@ -2552,11 +2543,11 @@ static inline unsigned long mas_next_entry(struct ma_state *mas, if (mas_next_nentry(mas, max, &pivot)) break; - p_slot = mt_parent_slot(mas->node); - ma_set_slot(mas, p_slot); + p_slot = mte_parent_slot(mas->node); + mas_set_slot(mas, p_slot); mas_next_node(mas, max); if (mas->node != MAS_NONE) - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); } } return pivot; @@ -2582,7 +2573,7 @@ static inline int mas_coalesce_node(struct ma_state *mas, unsigned char end, if (mas_is_err(mas)) return 0; if (replace) - mt_replace(mas); + mas_replace(mas); return ma_hard_data(end, coalesce); } @@ -2590,8 +2581,8 @@ static inline void mas_coalesce_empty(struct ma_state *mas, struct maple_enode *eparent, unsigned char p_slot) { - ma_set_rcu_slot(eparent, p_slot, XA_DELETED_ENTRY); - ma_set_slot(mas, p_slot); + mte_set_rcu_slot(eparent, p_slot, XA_DELETED_ENTRY); + mas_set_slot(mas, p_slot); } /** Private @@ -2633,56 +2624,56 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, if (coalesce) coalesce--; l_slot_cnt = ma_hard_data(end, coalesce); - if (ma_is_root(this_enode)) + if (mte_is_root(this_enode)) return mas_coalesce_node(mas, end, coalesce, true); - this_p_slot = mt_parent_slot(this_enode); - ma_encoded_parent(mas); - ma_set_slot(mas, this_p_slot + 1); + this_p_slot = mte_parent_slot(this_enode); + mas_encoded_parent(mas); + mas_set_slot(mas, this_p_slot + 1); if (!mas_next_nentry(mas, ULONG_MAX, &r_piv)) { // this_enode is the right-most node. BUG_ON(!l_slot_cnt); mas->node = this_enode; mas->max = this_max; mas->min = this_min; - ma_set_slot(mas, this_p_slot); - ma_encoded_parent(mas); - ma_set_slot(mas, this_p_slot); + mas_set_slot(mas, this_p_slot); + mas_encoded_parent(mas); + mas_set_slot(mas, this_p_slot); // If there is a single entry, rebalance the parent. if (mas_prev_nentry(mas, 0, &r_piv)) { mas->node = - ma_get_rcu_slot(mas->node, ma_get_slot(mas)); - end = ma_data_end(mas, mt_node_type(mas->node), + mte_get_rcu_slot(mas->node, mas_get_slot(mas)); + end = mas_data_end(mas, mte_node_type(mas->node), &l_piv, &coalesce); return mas_rebalance(mas, end, coalesce); } mas->node = this_enode; mas->max = this_max; mas->min = this_min; - ma_set_slot(mas, this_p_slot); - ma_encoded_parent(mas); + mas_set_slot(mas, this_p_slot); + mas_encoded_parent(mas); mas_coalesce(mas); } // If we reached here, then the node to the right exists. // set the ma_state information and save a copy for this slot. - mas->min = ma_get_safe_pivot(mas, ma_get_slot(mas) - 1); // safe as it is a right node. - mas->max = ma_get_safe_pivot(mas, ma_get_slot(mas)); - mas->node = ma_get_rcu_slot(mas->node, ma_get_slot(mas)); + mas->min = mas_get_safe_pivot(mas, mas_get_slot(mas) - 1); // safe as it is a right node. + mas->max = mas_get_safe_pivot(mas, mas_get_slot(mas)); + mas->node = mte_get_rcu_slot(mas->node, mas_get_slot(mas)); r_min = mas->min; r_max = mas->max; r_enode = mas->node; - r_end = ma_data_end(mas, mt_node_type(r_enode), &l_piv, &r_coalesce); + r_end = mas_data_end(mas, mte_node_type(r_enode), &l_piv, &r_coalesce); r_slot_cnt = ma_hard_data(r_end, r_coalesce); // Add 1 for slot 0 on the right. all_slots = r_slot_cnt + 1 + l_slot_cnt; // check if left ends in NULL, right start in NULL.. - if ((mt_will_coalesce(ma_get_rcu_slot(this_enode, end)) || - !ma_get_rcu_slot(this_enode, end)) && - (mt_will_coalesce(ma_get_rcu_slot(mas->node, 0)) || - !ma_get_rcu_slot(mas->node, 0))) { + if ((mt_will_coalesce(mte_get_rcu_slot(this_enode, end)) || + !mte_get_rcu_slot(this_enode, end)) && + (mt_will_coalesce(mte_get_rcu_slot(mas->node, 0)) || + !mte_get_rcu_slot(mas->node, 0))) { all_slots--; trimmed = 1; } @@ -2702,7 +2693,7 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, // Coalesce this_enode into a new node. MA_CP(cp, mas->node, NULL, 0, end); cp.dst_end = l_slot_cnt - trimmed; - ma_copy(mas, &cp); // cp.dst now has coalesced this_enode. + mas_copy(mas, &cp); // cp.dst now has coalesced this_enode. // Restore the right state. mas->max = r_max; @@ -2715,15 +2706,15 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, else cp.dst_end = (all_slots + 1)/ 2; // Take 1/2 the entries. - ma_copy(mas, &cp); // cp.dst is now complete, place it in the tree. - mt_to_node(cp.dst)->parent = mt_to_node(this_enode)->parent; - new_type = mt_node_type(cp.dst); + mas_copy(mas, &cp); // cp.dst is now complete, place it in the tree. + mte_to_node(cp.dst)->parent = mte_to_node(this_enode)->parent; + new_type = mte_node_type(cp.dst); mas->node = cp.dst; - mt_replace(mas); - l_piv = ma_get_safe_pivot(mas, cp.dst_start - 1); + mas_replace(mas); + l_piv = mas_get_safe_pivot(mas, cp.dst_start - 1); ret = mt_slot_count(mas->node) - cp.dst_start + 1; - ma_encoded_parent(mas); - ma_set_pivot(mas->node, this_p_slot, l_piv); + mas_encoded_parent(mas); + mte_set_pivot(mas->node, this_p_slot, l_piv); mas->node = r_enode; mas->max = r_max; @@ -2736,10 +2727,10 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, entry = NULL; ret = mt_slots[new_type] - all_slots; - r_p_slot = mt_parent_slot(r_enode); - ma_encoded_parent(mas); - ma_set_rcu_slot(mas->node, r_p_slot, entry); - mt_free(mt_to_node(r_enode)); + r_p_slot = mte_parent_slot(r_enode); + mas_encoded_parent(mas); + mte_set_rcu_slot(mas->node, r_p_slot, entry); + mte_free(r_enode); p_coalesce = true; goto right_done; } @@ -2748,19 +2739,19 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, cp.dst = NULL; cp.dst_start = 0; cp.dst_end = r_end; - ma_copy(mas, &cp); // cp.dst is coalesced remainder of r_enode. - mt_to_node(cp.dst)->parent = mt_to_node(r_enode)->parent; + mas_copy(mas, &cp); // cp.dst is coalesced remainder of r_enode. + mte_to_node(cp.dst)->parent = mte_to_node(r_enode)->parent; mas->node = cp.dst; - r_piv = ma_get_safe_pivot(mas, cp.dst_start - 1); - r_p_slot = mt_parent_slot(r_enode); - mt_replace(mas); - ma_encoded_parent(mas); - ma_set_pivot(mas->node, r_p_slot, r_piv); + r_piv = mas_get_safe_pivot(mas, cp.dst_start - 1); + r_p_slot = mte_parent_slot(r_enode); + mas_replace(mas); + mas_encoded_parent(mas); + mte_set_pivot(mas->node, r_p_slot, r_piv); right_done: while (r_p_slot-- > this_p_slot) { - ma_set_pivot(mas->node, r_p_slot, l_piv); + mte_set_pivot(mas->node, r_p_slot, l_piv); } /* If there is a freed node, then mas->node must point to the parent @@ -2783,18 +2774,18 @@ static inline void mas_coalesce_root(struct ma_state *mas) unsigned long piv; this_enode = mas->node; - this_type = mt_node_type(this_enode); - end = ma_data_end(mas, this_type, &piv, &coalesce); + this_type = mte_node_type(this_enode); + end = mas_data_end(mas, this_type, &piv, &coalesce); hard_data = ma_hard_data(end, coalesce); if ((end <= coalesce)) { - if(!mt_is_leaf(this_enode)) { + if(!mte_is_leaf(this_enode)) { // Remove level in tree. - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); mas_first_node(mas, ULONG_MAX); - mt_to_node(mas->node)->parent = - mt_to_node(this_enode)->parent; - mas->node = mt_mk_root(mas->node); - mt_replace(mas); + mte_to_node(mas->node)->parent = + mte_to_node(this_enode)->parent; + mas->node = mte_mk_root(mas->node); + mas_replace(mas); return; } @@ -2803,12 +2794,12 @@ static inline void mas_coalesce_root(struct ma_state *mas) return; } - if (mt_is_leaf(this_enode) && hard_data == 1) { + if (mte_is_leaf(this_enode) && hard_data == 1) { void *entry; - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); if (!mas_first_entry(mas, ULONG_MAX)) { - entry = ma_get_rcu_slot(mas->node, - ma_get_slot(mas)); + entry = mte_get_rcu_slot(mas->node, + mas_get_slot(mas)); if (((unsigned long) (entry) & 3) != 2) { rcu_assign_pointer(mas->tree->ma_root, entry); @@ -2819,15 +2810,15 @@ static inline void mas_coalesce_root(struct ma_state *mas) } if (hard_data < mt_min_slots[this_type] - 1) { MA_CP(cp, mas->node, NULL, 0, end); - ma_copy(mas, &cp); + mas_copy(mas, &cp); if (mas_is_err(mas)) return; mas->node = cp.dst; - mt_to_node(mas->node)->parent = - mt_to_node(this_enode)->parent; - mas->node = mt_mk_root(mas->node); - mt_replace(mas); + mte_to_node(mas->node)->parent = + mte_to_node(this_enode)->parent; + mas->node = mte_mk_root(mas->node); + mas_replace(mas); } } @@ -2855,12 +2846,12 @@ static inline void mas_coalesce(struct ma_state *mas) void *entry; bool check_parent = false; - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) return mas_coalesce_root(mas); start: this_enode = mas->node; - this_type = mt_node_type(this_enode); - end = ma_data_end(mas, this_type, &piv, &coalesce); + this_type = mte_node_type(this_enode); + end = mas_data_end(mas, this_type, &piv, &coalesce); /* If there is any space to save, try to reallocate */ @@ -2875,11 +2866,11 @@ start: /* Group the gaps together. Acquire any data from the next node, if * necessary */ - p_slot = mt_parent_slot(this_enode); - eparent = mt_mk_node(mt_parent(this_enode), - mt_parent_enum(mas, this_enode)); + p_slot = mte_parent_slot(this_enode); + eparent = mt_mk_node(mte_parent(this_enode), + mas_parent_enum(mas, this_enode)); - entry = ma_get_rcu_slot(this_enode, end); + entry = mte_get_rcu_slot(this_enode, end); if (!mt_is_empty(entry)) goto check_start; @@ -2894,20 +2885,20 @@ start: goto check_start; if (mt_is_empty(mas->node) || - mt_is_empty(ma_get_rcu_slot(mas->node, 0))) { + mt_is_empty(mte_get_rcu_slot(mas->node, 0))) { unsigned char slot = end; if (check_parent) slot = 0; while (slot > 0) { - if (!mt_is_empty(ma_get_rcu_slot(this_enode, slot))) + if (!mt_is_empty(mte_get_rcu_slot(this_enode, slot))) break; slot--; } mas->node = eparent; - mas_update_limits(mas, p_slot, mt_node_type(mas->node)); + mas_update_limits(mas, p_slot, mte_node_type(mas->node)); mas->node = this_enode; if (!slot) { @@ -2916,11 +2907,11 @@ start: check_parent = true; piv = mas->min; } else { - piv = ma_get_safe_pivot(mas, slot); + piv = mas_get_safe_pivot(mas, slot); } if (p_slot <= mt_pivot_count(eparent)) - ma_set_pivot(eparent, p_slot, piv); + mte_set_pivot(eparent, p_slot, piv); // Walk up checking for the old pivot and set to piv. if (!slot) @@ -2928,12 +2919,12 @@ start: // Indicate value has been moved. while (++slot <= end) - ma_set_rcu_slot(this_enode, slot, XA_RETRY_ENTRY); + mte_set_rcu_slot(this_enode, slot, XA_RETRY_ENTRY); } check_start: mas->node = this_enode; - entry = ma_get_rcu_slot(this_enode, 0); + entry = mte_get_rcu_slot(this_enode, 0); if (mt_is_empty(entry)) { unsigned char prev_end; // Check the previous node. @@ -2942,17 +2933,17 @@ check_start: goto done; if (!mt_is_empty(mas->node)) { - prev_end = ma_data_end(mas, mt_node_type(mas->node), + prev_end = mas_data_end(mas, mte_node_type(mas->node), &piv, &coalesce); - if (!mt_is_empty(ma_get_rcu_slot(mas->node, prev_end))) + if (!mt_is_empty(mte_get_rcu_slot(mas->node, prev_end))) goto done; } else { piv = mas->min; } if (p_slot) - ma_set_pivot(eparent, p_slot - 1, piv); + mte_set_pivot(eparent, p_slot - 1, piv); // Walk up and set all the pivots to piv @@ -2961,13 +2952,13 @@ done: mas->node = this_enode; if (check_parent) { check_parent = false; - ma_encoded_parent(mas); + mas_encoded_parent(mas); mte_free(this_enode); goto start; } if (mt_is_alloc(mas->tree)) - ma_update_gap(mas); + mas_update_gap(mas); return; } @@ -2980,8 +2971,8 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) unsigned char pivot_cnt, i; bool found = false; - type = mt_node_type(mas->node); - i = ma_get_slot(mas); + type = mte_node_type(mas->node); + i = mas_get_slot(mas); min = mas->min; max = mas->max; @@ -2992,7 +2983,7 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) if (i >= pivot_cnt - 1) max = mas->max; else - max = _ma_get_pivot(mas->node, i, type); + max = _mte_get_pivot(mas->node, i, type); do { unsigned long this_gap = 0; @@ -3001,7 +2992,7 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) if (!i) min = mas->min; else - min = _ma_get_pivot(mas->node, i - 1, + min = _mte_get_pivot(mas->node, i - 1, type) + 1; /* last is below this range */ @@ -3015,7 +3006,7 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) } /* check if this slot is full */ - entry = _ma_get_rcu_slot(mas->node, i, type); + entry = _mte_get_rcu_slot(mas->node, i, type); if (entry) goto next_slot; @@ -3041,7 +3032,7 @@ next_slot: if (!i) min = mas->min; else - min = _ma_get_pivot(mas->node, i - 1, + min = _mte_get_pivot(mas->node, i - 1, type) + 1; @@ -3056,7 +3047,7 @@ next_slot: return false; } - this_gap = ma_get_gap(mas->node, i); + this_gap = mte_get_gap(mas->node, i); /* Not big enough */ if (size > this_gap) goto next; @@ -3088,25 +3079,25 @@ next: struct maple_enode *next; unsigned char coalesce; - next = _ma_get_rcu_slot(mas->node, i, type); + next = _mte_get_rcu_slot(mas->node, i, type); mas->min = min; mas->max = max; if (next) { mas->node = next; - i = ma_data_end(mas, mt_node_type(next), &max, + i = mas_data_end(mas, mte_node_type(next), &max, &coalesce); } else { found = true; // this is a non-leaf hole. } } - ma_set_slot(mas, i); + mas_set_slot(mas, i); return found; ascend: - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) mas_set_err(mas, -EBUSY); - ma_set_slot(mas, i); + mas_set_slot(mas, i); return found; } @@ -3120,7 +3111,7 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) min = mas->min; max = mas->max; - type = mt_node_type(mas->node); + type = mte_node_type(mas->node); pivot_cnt = mt_pivots[type]; switch (type) { @@ -3129,7 +3120,7 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) unsigned long this_gap = 0; void *entry = NULL; - pivot = _ma_get_safe_pivot(mas, i, type); + pivot = _mas_get_safe_pivot(mas, i, type); /* End of data in this leaf */ if (i && !pivot) @@ -3145,7 +3136,7 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) if (mas->index > pivot) goto next; - entry = _ma_get_rcu_slot(mas->node, i, type); + entry = _mte_get_rcu_slot(mas->node, i, type); if (unlikely(xa_is_skip(entry))) goto next; @@ -3170,15 +3161,15 @@ next: break; default: pivot = 0; - i = ma_get_slot(mas); + i = mas_get_slot(mas); for (; i < pivot_cnt; i++) { unsigned long this_gap; - pivot = _ma_get_pivot(mas->node, i, type); + pivot = _mte_get_pivot(mas->node, i, type); if (i && !pivot) goto ascend; - this_gap = ma_get_gap(mas->node, i); + this_gap = mte_get_gap(mas->node, i); if (size <= this_gap) { if (mas->index <= pivot) { max = pivot; @@ -3195,7 +3186,7 @@ next: // Final slot. if ((i == pivot_cnt - 1) && (mas->index > pivot)) { - if (size > ma_get_gap(mas->node, ++i)) + if (size > mte_get_gap(mas->node, ++i)) goto ascend; } @@ -3212,7 +3203,7 @@ next: if (!ma_is_leaf(type)) { //descend struct maple_enode *next; - next = _ma_get_rcu_slot(mas->node, i, type); + next = _mte_get_rcu_slot(mas->node, i, type); mas->min = min; mas->max = max; if (!mt_is_empty(next)) { @@ -3223,13 +3214,13 @@ next: } } - ma_set_slot(mas, i); + mas_set_slot(mas, i); return found; ascend: - if (ma_is_root(mas->node)) + if (mte_is_root(mas->node)) found = true; - ma_set_slot(mas, i); + mas_set_slot(mas, i); return found; } /* @@ -3247,7 +3238,7 @@ static inline bool __mas_walk(struct ma_state *mas) max = mas->max; while (true) { - type = mt_node_type(mas->node); + type = mte_node_type(mas->node); pivot_cnt = mt_pivots[type]; if (ma_is_leaf(type)) // Leaf. @@ -3256,8 +3247,8 @@ static inline bool __mas_walk(struct ma_state *mas) skip_entry: switch (type) { default: - for (i = ma_get_slot(mas); i < pivot_cnt; i++) { - pivot = _ma_get_pivot(mas->node, i, type); + for (i = mas_get_slot(mas); i < pivot_cnt; i++) { + pivot = _mte_get_pivot(mas->node, i, type); if (i != 0 && pivot == 0) { i = MAPLE_NODE_SLOTS; goto done; @@ -3283,9 +3274,9 @@ skip_entry: goto done; } - next = _ma_get_rcu_slot(mas->node, i, type); + next = _mte_get_rcu_slot(mas->node, i, type); if (unlikely(xa_is_skip(next))) { - ma_set_slot(mas, i + 1); + mas_set_slot(mas, i + 1); goto skip_entry; } @@ -3298,13 +3289,13 @@ skip_entry: mas->node = next; } done: - ma_set_slot(mas, i); + mas_set_slot(mas, i); return ret; } static inline bool _mas_walk(struct ma_state *mas) { mas->node = mas_start(mas); - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); return __mas_walk(mas); } @@ -3320,7 +3311,7 @@ static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot, if (0 > delta) limit = 0; while (*slot != limit) { - if (!mt_is_empty(ma_get_rcu_slot(mas->node, *slot + delta))) + if (!mt_is_empty(mte_get_rcu_slot(mas->node, *slot + delta))) return true; *slot += delta; } @@ -3328,7 +3319,7 @@ static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot, } static inline int mas_dead_node(struct ma_state *mas, unsigned long index) { - if (!mt_dead_node(mas->node)) + if (!mte_dead_node(mas->node)) return 0; mas->index = index; @@ -3360,11 +3351,11 @@ void *mas_find(struct ma_state *mas, unsigned long max) _mas_walk(mas); do {} while (mas_dead_node(mas, mas->index)); - slot = ma_get_slot(mas); + slot = mas_get_slot(mas); - last_piv = ma_get_safe_pivot(mas, slot); + last_piv = mas_get_safe_pivot(mas, slot); if (slot != MAPLE_NODE_SLOTS) - entry = ma_get_rcu_slot(mas->node, slot); + entry = mte_get_rcu_slot(mas->node, slot); if (entry) { mas->index = last_piv; @@ -3379,16 +3370,16 @@ void *mas_find(struct ma_state *mas, unsigned long max) goto not_found; - slot = ma_get_slot(mas); - entry = ma_get_rcu_slot(mas->node, slot); + slot = mas_get_slot(mas); + entry = mte_get_rcu_slot(mas->node, slot); if (!entry) goto not_found; - mas->index = ma_get_prev_pivot(mas, slot) + 1; + mas->index = mas_get_prev_pivot(mas, slot) + 1; done: mas->last = last_piv; - ma_set_slot(mas, slot + 1); + mas_set_slot(mas, slot + 1); return entry; not_found: @@ -3431,9 +3422,9 @@ void *mt_find(struct maple_tree *mt, unsigned long start, _mas_walk(&mas); do {} while (mas_dead_node(&mas, mas.index)); - slot = ma_get_slot(&mas); + slot = mas_get_slot(&mas); if (slot != MAPLE_NODE_SLOTS) - entry = ma_get_rcu_slot(mas.node, slot); + entry = mte_get_rcu_slot(mas.node, slot); if (xa_is_zero(entry)) @@ -3448,8 +3439,8 @@ retry: goto done; - slot = ma_get_slot(&mas); - entry = ma_get_rcu_slot(mas.node, slot); + slot = mas_get_slot(&mas); + entry = mte_get_rcu_slot(mas.node, slot); if (xa_is_zero(entry)) goto retry; @@ -3474,17 +3465,17 @@ void *mt_find_after(struct maple_tree *mt, unsigned long *index, rcu_read_lock(); _mas_walk(&mas); retry: - ma_set_slot(&mas, ma_get_slot(&mas) + 1); + mas_set_slot(&mas, mas_get_slot(&mas) + 1); mas_safe_next_entry(&mas, max); if (mas.node == MAS_NONE) goto done; - slot = ma_get_slot(&mas); - entry = ma_get_rcu_slot(mas.node, slot); + slot = mas_get_slot(&mas); + entry = mte_get_rcu_slot(mas.node, slot); if (xa_is_zero(entry)) goto retry; - *index = ma_get_safe_pivot(&mas, slot); + *index = mas_get_safe_pivot(&mas, slot); done: rcu_read_unlock(); return entry; @@ -3501,8 +3492,8 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) unsigned char r_slot = 0, slot; MA_STATE(r_mas, mas->tree, mas->last + 1, mas->last + 1); - slot_cnt = 1 + ma_get_slot(mas); - ma_set_slot(mas, mt_parent_slot(mas->node)); + slot_cnt = 1 + mas_get_slot(mas); + mas_set_slot(mas, mte_parent_slot(mas->node)); while (mas->node != MAS_NONE) { last = mas->node; mas_prev_node(mas, 0); @@ -3511,20 +3502,20 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) mas->node = last; _mas_walk(&r_mas); - if (ma_get_slot(&r_mas) != MAPLE_NODE_SLOTS) { + if (mas_get_slot(&r_mas) != MAPLE_NODE_SLOTS) { unsigned long piv; unsigned char coalesce; - r_slot_cnt += ma_data_end(&r_mas, mt_node_type(r_mas.node), + r_slot_cnt += mas_data_end(&r_mas, mte_node_type(r_mas.node), &piv, &coalesce); if (piv != ULONG_MAX) { - unsigned char p_slot = mt_parent_slot(r_mas.node); + unsigned char p_slot = mte_parent_slot(r_mas.node); r_node = r_mas.node; - r_slot = ma_get_slot(&r_mas); + r_slot = mas_get_slot(&r_mas); r_slot_cnt -= r_slot; slot_cnt += r_slot_cnt; - ma_set_slot(&r_mas, p_slot); + mas_set_slot(&r_mas, p_slot); while (r_mas.node != MAS_NONE) { last = r_mas.node; mas_next_node(&r_mas, ULONG_MAX); @@ -3560,9 +3551,9 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) mas->alloc = NULL; // Copy left side - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); new_mas.last = mas_first_entry(mas, mas->index); - slot = ma_get_slot(mas); + slot = mas_get_slot(mas); do { new_mas.index = mas->min; new_mas.last = mas->min; @@ -3570,20 +3561,20 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) if (new_mas.index == mas->index) { break; } - new_mas.last = ma_get_safe_pivot(mas, slot); + new_mas.last = mas_get_safe_pivot(mas, slot); if (!new_mas.last && slot) break; if (new_mas.last > mas->index) new_mas.last = mas->index - 1; - entry = ma_get_rcu_slot(mas->node, slot); + entry = mte_get_rcu_slot(mas->node, slot); if (entry) { - int cnt = ma_get_alloc_cnt(&new_mas); + int cnt = mas_get_alloc_cnt(&new_mas); ma_inactive_insert(&new_mas, entry); if (mas_is_err(&new_mas)) BUG_ON(1); - if (cnt < ma_get_alloc_cnt(&new_mas) - 1) + if (cnt < mas_get_alloc_cnt(&new_mas) - 1) BUG_ON(1); } @@ -3594,7 +3585,7 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) slot++; } - ma_set_slot(mas, mt_parent_slot(mas->node)); + mas_set_slot(mas, mte_parent_slot(mas->node)); mas_next_node(mas, mas->index); slot = 0; } while (mas->node != MAS_NONE && mas->min < mas->index); @@ -3618,21 +3609,21 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) goto skip_right; new_mas.index = new_mas.last + 1; - new_mas.last = ma_get_pivot(r_node, r_slot); + new_mas.last = mte_get_pivot(r_node, r_slot); - ma_set_slot(mas, r_slot); + mas_set_slot(mas, r_slot); mas->node = r_node; mas->min = new_mas.index; do { new_mas.index = mas->min; new_mas.last = mas->min; - slot = ma_get_slot(mas); + slot = mas_get_slot(mas); while (slot++ < mt_slot_count(mas->node)) { - new_mas.last = ma_get_safe_pivot(mas, slot); + new_mas.last = mas_get_safe_pivot(mas, slot); if (!new_mas.last) break; - entry = ma_get_rcu_slot(mas->node, slot); + entry = mte_get_rcu_slot(mas->node, slot); if (entry) { ma_inactive_insert(&new_mas, entry); if (mas_is_err(&new_mas)) @@ -3642,17 +3633,17 @@ static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) new_mas.index = new_mas.last + 1; } mas_next_node(mas, mas->index); - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); } while (mas->node != MAS_NONE); skip_right: r_node = mas->tree->ma_root; mas->node = new_tree.ma_root; - _mt_replace(mas, false, false); + _mas_replace(mas, false, false); mas->node = 0; mas->alloc = new_mas.alloc; - ma_destroy_walk(r_node); + mte_destroy_walk(r_node); // Copy right side return node_cnt; @@ -3665,8 +3656,8 @@ static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) unsigned char slot, coalesce; mas->node = mas_start(mas); - slot = ma_data_end(mas, mt_node_type(mas->node), &last_piv, &coalesce); - ma_set_slot(mas, slot); + slot = mas_data_end(mas, mte_node_type(mas->node), &last_piv, &coalesce); + mas_set_slot(mas, slot); /* There are 4 options: @@ -3688,7 +3679,7 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size) struct maple_enode *last = NULL; mas->node = mas_start(mas); - ma_set_slot(mas, 0); + mas_set_slot(mas, 0); /* There are 4 options: * go to child (descend) @@ -3727,7 +3718,7 @@ exists: return 0; } -static inline int ma_add(struct ma_state *mas, void *entry, bool overwrite, +static inline int mas_add(struct ma_state *mas, void *entry, bool overwrite, bool active) { unsigned char slot = MAPLE_NODE_SLOTS; @@ -3742,10 +3733,10 @@ static inline int ma_add(struct ma_state *mas, void *entry, bool overwrite, return ret; leaf = _mas_walk(mas); - slot = ma_get_slot(mas); + slot = mas_get_slot(mas); if (leaf == true && slot != MAPLE_NODE_SLOTS) { if (!overwrite) { - void *entry = ma_get_rcu_slot(mas->node, slot); + void *entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) goto exists; @@ -3753,7 +3744,7 @@ static inline int ma_add(struct ma_state *mas, void *entry, bool overwrite, } /* Do the add */ - return _ma_add(mas, entry, overwrite, active); + return _mas_add(mas, entry, overwrite, active); exists: mas_set_err(mas, -EEXIST); @@ -3762,11 +3753,11 @@ exists: static inline void ma_inactive_insert(struct ma_state *mas, void *entry) { - ma_add(mas, entry, false, false); + mas_add(mas, entry, false, false); } -static inline void ma_insert(struct ma_state *mas, void *entry) +static inline void mas_insert(struct ma_state *mas, void *entry) { - ma_add(mas, entry, false, true); + mas_add(mas, entry, false, true); } static int mas_fill_gap(struct ma_state *mas, void *entry, unsigned char slot, @@ -3779,7 +3770,7 @@ static int mas_fill_gap(struct ma_state *mas, void *entry, unsigned char slot, *index = mas->index; mas->last = mas->index + size - 1; - _ma_insert(mas, entry, slot); + _mas_insert(mas, entry, slot); return 0; } @@ -3802,15 +3793,15 @@ static inline int ma_alloc(struct ma_state *mas, void *entry, if (!xa_is_node(rcu_dereference(mas->tree->ma_root))) { ma_root_expand(mas, entry); if (!mas->index) - return ma_get_pivot(mas->node, 0); - return ma_get_pivot(mas->node, 1); + return mte_get_pivot(mas->node, 0); + return mte_get_pivot(mas->node, 1); } mas_awalk(mas, size); if (mas_is_err(mas)) return xa_err(mas->node); - slot = ma_get_slot(mas); + slot = mas_get_slot(mas); if (slot == MAPLE_NODE_SLOTS) goto no_gap; @@ -3818,7 +3809,7 @@ static inline int ma_alloc(struct ma_state *mas, void *entry, // slot that has a sufficient gap. min = mas->min; if (slot) - min = ma_get_pivot(mas->node, slot - 1) + 1; + min = mte_get_pivot(mas->node, slot - 1) + 1; if (mas->index < min) mas->index = min; @@ -3846,15 +3837,15 @@ static inline int ma_rev_alloc(struct ma_state *mas, void *entry, if (!xa_is_node(rcu_dereference(mas->tree->ma_root))) { ma_root_expand(mas, entry); if (!mas->index) - return ma_get_pivot(mas->node, 0); - return ma_get_pivot(mas->node, 1); + return mte_get_pivot(mas->node, 0); + return mte_get_pivot(mas->node, 1); } mas_rev_awalk(mas, size); if (mas_is_err(mas)) return xa_err(mas->node); - slot = ma_get_slot(mas); + slot = mas_get_slot(mas); if (slot == MAPLE_NODE_SLOTS) goto no_gap; @@ -3902,9 +3893,9 @@ void *mas_walk(struct ma_state *mas) } leaf = _mas_walk(mas); - slot = ma_get_slot(mas); + slot = mas_get_slot(mas); if (leaf == true && slot != MAPLE_NODE_SLOTS) - entry = ma_get_rcu_slot(mas->node, slot); + entry = mte_get_rcu_slot(mas->node, slot); return entry; } @@ -3914,20 +3905,20 @@ static inline bool mas_rewind_node(struct ma_state *mas) unsigned char slot; do { - if (ma_is_root(mas->node)) { - slot = ma_get_slot(mas); + if (mte_is_root(mas->node)) { + slot = mas_get_slot(mas); if (!slot) { mas_set_err(mas, -EBUSY); return false; } } else { - slot = mt_parent_slot(mas->node); - ma_encoded_parent(mas); + slot = mte_parent_slot(mas->node); + mas_encoded_parent(mas); } } while (!slot); - ma_set_slot(mas, --slot); - mas_update_limits(mas, slot, mt_node_type(mas->node)); + mas_set_slot(mas, --slot); + mas_update_limits(mas, slot, mte_node_type(mas->node)); return true; } /* Skip this slot in the parent. */ @@ -3936,20 +3927,20 @@ static inline bool mas_skip_node(struct ma_state *mas) unsigned char slot; do { - if (ma_is_root(mas->node)) { - slot = ma_get_slot(mas); + if (mte_is_root(mas->node)) { + slot = mas_get_slot(mas); if (slot > mt_slot_count(mas->node) - 1) { mas_set_err(mas, -EBUSY); return false; } } else { - slot = mt_parent_slot(mas->node); - ma_encoded_parent(mas); + slot = mte_parent_slot(mas->node); + mas_encoded_parent(mas); } } while (slot > mt_slot_count(mas->node) - 1); - ma_set_slot(mas, ++slot); - mas_update_limits(mas, slot, mt_node_type(mas->node)); + mas_set_slot(mas, ++slot); + mas_update_limits(mas, slot, mte_node_type(mas->node)); return true; } /* Private @@ -3961,14 +3952,14 @@ static inline bool mas_skip_node(struct ma_state *mas) */ static inline int ma_erase(struct ma_state *mas) { - enum maple_type type = mt_node_type(mas->node); + enum maple_type type = mte_node_type(mas->node); unsigned char slot_cnt = mt_slots[type]; unsigned char pivot_cnt = mt_pivots[type]; unsigned long piv_val; int slot, ret = 1; - slot = ma_get_slot(mas); - ma_update_rcu_slot(mas->node, slot, XA_DELETED_ENTRY); + slot = mas_get_slot(mas); + mte_update_rcu_slot(mas->node, slot, XA_DELETED_ENTRY); // dense nodes only need to set a single value. if (!pivot_cnt) return ret; @@ -3976,15 +3967,15 @@ static inline int ma_erase(struct ma_state *mas) if ((slot >= slot_cnt - 1)) piv_val = mas->max; else - piv_val = ma_get_pivot(mas->node, slot); + piv_val = mte_get_pivot(mas->node, slot); while ((slot < pivot_cnt - 1)) { - unsigned long this_pivot = ma_get_pivot(mas->node, slot + 1); + unsigned long this_pivot = mte_get_pivot(mas->node, slot + 1); if (!this_pivot) // end of node. break; // There is data for this pivot. - if (ma_get_rcu_slot(mas->node, slot + 1)) + if (mte_get_rcu_slot(mas->node, slot + 1)) break; // empty slot above the erase. @@ -3994,12 +3985,12 @@ static inline int ma_erase(struct ma_state *mas) /* Walk down and set all the previous pivots with NULLs to piv_val */ while (--slot >= 0) { - void *entry = ma_get_rcu_slot(mas->node, slot); + void *entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) break; - ma_set_pivot(mas->node, slot, piv_val); + mte_set_pivot(mas->node, slot, piv_val); ret++; } @@ -4052,7 +4043,7 @@ int mtree_store_range(struct maple_tree *mt, unsigned long first, mtree_lock(mas.tree); retry: - ma_add(&mas, entry, true, true); + mas_add(&mas, entry, true, true); if (mas_nomem(&mas, gfp)) goto retry; @@ -4083,7 +4074,7 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first, mtree_lock(ms.tree); retry: - ma_insert(&ms, entry); + mas_insert(&ms, entry); if (mas_nomem(&ms, gfp)) goto retry; @@ -4197,7 +4188,7 @@ int mtree_erase(struct maple_tree *mt, unsigned long index) mtree_lock(mt); _mas_walk(&mas); - slot = ma_get_slot(&mas); + slot = mas_get_slot(&mas); if (slot != MAPLE_NODE_SLOTS) ret = ma_erase(&mas); @@ -4213,7 +4204,7 @@ void mtree_destroy(struct maple_tree *mt) mtree_lock(mt); destroyed = mt->ma_root; if (xa_is_node(destroyed)) - ma_destroy_walk(destroyed); + mte_destroy_walk(destroyed); mt->ma_flags = 0; rcu_assign_pointer(mt->ma_root, NULL); @@ -4261,8 +4252,8 @@ void mt_dump_entry(void *entry, unsigned long min, unsigned long max, void mt_dump_range64(void *entry, unsigned long min, unsigned long max, unsigned int depth) { - struct maple_range_64 *node = &mt_to_node(entry)->mr64; - bool leaf = mt_is_leaf(entry); + struct maple_range_64 *node = &mte_to_node(entry)->mr64; + bool leaf = mte_is_leaf(entry); unsigned long first = min; int i; @@ -4275,7 +4266,7 @@ void mt_dump_range64(void *entry, unsigned long min, unsigned long max, if (i < (MAPLE_RANGE64_SLOTS - 1)) last = node->pivot[i]; - else if (node->slot[i] == NULL && max != mt_max[mt_node_type(entry)]) + else if (node->slot[i] == NULL && max != mt_max[mte_node_type(entry)]) break; if (last == 0 && i > 0) break; @@ -4301,8 +4292,8 @@ void mt_dump_range64(void *entry, unsigned long min, unsigned long max, void mt_dump_arange64(void *entry, unsigned long min, unsigned long max, unsigned int depth) { - struct maple_arange_64 *node = &mt_to_node(entry)->ma64; - bool leaf = mt_is_leaf(entry); + struct maple_arange_64 *node = &mte_to_node(entry)->ma64; + bool leaf = mte_is_leaf(entry); unsigned long first = min; int i; @@ -4345,8 +4336,8 @@ void mt_dump_arange64(void *entry, unsigned long min, unsigned long max, void mt_dump_node(void *entry, unsigned long min, unsigned long max, unsigned int depth) { - struct maple_node *node = mt_to_node(entry); - unsigned int type = mt_node_type(entry); + struct maple_node *node = mte_to_node(entry); + unsigned int type = mte_node_type(entry); unsigned int i; mt_dump_range(min, max, depth); @@ -4384,7 +4375,7 @@ void mt_dump(const struct maple_tree *mt) if (!xa_is_node(entry)) mt_dump_entry(entry, 0, 0, 0); else if (entry) - mt_dump_node(entry, 0, mt_max[mt_node_type(entry)], 0); + mt_dump_node(entry, 0, mt_max[mte_node_type(entry)], 0); } extern void kmem_cache_set_non_kernel(struct kmem_cache *, unsigned int); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 746a013e1052..be76a04d2526 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -188,14 +188,14 @@ static noinline void check_nomem(struct maple_tree *mt) * userspace test suite. */ mtree_lock(mt); - ma_insert(&ms, &ms); // insert 1 -> &ms, fails. + mas_insert(&ms, &ms); // insert 1 -> &ms, fails. MT_BUG_ON(mt, ms.node != MA_ERROR(-ENOMEM)); mas_nomem(&ms, GFP_KERNEL); // Node allocated in here. MT_BUG_ON(mt, ms.node != MAS_START); mtree_unlock(mt); MT_BUG_ON(mt, mtree_insert(mt, 2, mt, GFP_KERNEL) != 0); mtree_lock(mt); - ma_insert(&ms, &ms); // insert 1 -> &ms + mas_insert(&ms, &ms); // insert 1 -> &ms mas_nomem(&ms, GFP_KERNEL); // Node allocated in here. mtree_unlock(mt); mtree_destroy(mt); @@ -214,13 +214,13 @@ static noinline void check_new_node(struct maple_tree *mt) // request 3 nodes to be allocated. mas_node_cnt(&mas, 3); // Allocation request of 3. - MT_BUG_ON(mt, ma_get_alloc_req(&mas) != 3); + MT_BUG_ON(mt, mas_get_alloc_req(&mas) != 3); // Allocate failed. MT_BUG_ON(mt, mas.node != MA_ERROR(-ENOMEM)); MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); - MT_BUG_ON(mt, ma_get_alloc_cnt(&mas) != 3); - mn = ma_get_alloc(&mas); + MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 3); + mn = mas_get_alloc(&mas); MT_BUG_ON(mt, mn == NULL); MT_BUG_ON(mt, mn->slot[0] == NULL); MT_BUG_ON(mt, mn->slot[1] == NULL); @@ -231,36 +231,36 @@ static noinline void check_new_node(struct maple_tree *mt) /* Try allocating 1 node, then 2 more */ mtree_lock(mt); // Set allocation request to 1. - ma_set_alloc_req(&mas, 1); + mas_set_alloc_req(&mas, 1); // Check Allocation request of 1. - MT_BUG_ON(mt, ma_get_alloc_req(&mas) != 1); + MT_BUG_ON(mt, mas_get_alloc_req(&mas) != 1); mas_set_err(&mas, -ENOMEM); // Validate allocation request. MT_BUG_ON(mt, !mas_nomem(&mas, GFP_KERNEL)); // Eat the requested node. - mn = ma_next_alloc(&mas); + mn = mas_next_alloc(&mas); MT_BUG_ON(mt, mn == NULL); MT_BUG_ON(mt, mn->slot[0] != NULL); MT_BUG_ON(mt, mn->slot[1] != NULL); - MT_BUG_ON(mt, ma_get_alloc_cnt(&mas) != 0); + MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 0); - mt_free(mn); + ma_free(mn); // Allocate 3 nodes, will fail. mas_node_cnt(&mas, 3); // Drop the lock and allocate 3 nodes. mas_nomem(&mas, GFP_KERNEL); // Ensure 3 are allocated. - MT_BUG_ON(mt, ma_get_alloc_cnt(&mas) != 3); + MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 3); // Allocation request of 0. - MT_BUG_ON(mt, ma_get_alloc_req(&mas) != 0); + MT_BUG_ON(mt, mas_get_alloc_req(&mas) != 0); mn = mas.alloc; MT_BUG_ON(mt, mn == NULL); MT_BUG_ON(mt, mn->slot[0] == NULL); MT_BUG_ON(mt, mn->slot[1] == NULL); // Ensure we counted 3. - MT_BUG_ON(mt, ma_get_alloc_cnt(&mas) != 3); + MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 3); // Free. mas_nomem(&mas, GFP_KERNEL); @@ -268,7 +268,7 @@ static noinline void check_new_node(struct maple_tree *mt) mas_node_cnt(&mas, 127); // Drop the lock and allocate 3 nodes. mas_nomem(&mas, GFP_KERNEL); - mn = ma_get_alloc(&mas); + mn = mas_get_alloc(&mas); MT_BUG_ON(mt, mn == NULL); cnt++; for (int i = 0; i < 7; i++) { @@ -294,9 +294,9 @@ static noinline void check_new_node(struct maple_tree *mt) cnt++; } - MT_BUG_ON(mt, ma_get_alloc_cnt(&mas) != 127); + MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 127); mas_nomem(&mas, GFP_KERNEL); // Free. - MT_BUG_ON(mt, ma_get_alloc_cnt(&mas) != 0); + MT_BUG_ON(mt, mas_get_alloc_cnt(&mas) != 0); mtree_unlock(mt); mtree_destroy(mt); @@ -577,7 +577,7 @@ static noinline void check_erase_testset(struct maple_tree *mt) // Should be a new node. MT_BUG_ON(mt, root_node == mt->ma_root); // Should not have split. - MT_BUG_ON(mt, !mt_is_leaf(mt->ma_root)); + MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root)); // Coalesce testing diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 896e3c0264c1..224717d7cbb7 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -37,7 +37,7 @@ void farmer_tests(void) tree.ma_root = mt_mk_node(node, maple_leaf_64); mt_dump(&tree); - mt_free(node); + ma_free(node); } void maple_tree_tests(void) -- 2.50.1