From 25b5cff660df1c9bfc6fca1ca8f29bb4cda474f7 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 28 Aug 2020 13:54:57 -0400 Subject: [PATCH] maple_tree: Compress ma_height into ma_flags Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 11 +++++----- lib/maple_tree.c | 43 +++++++++++++++++++++++++++----------- 2 files changed, 37 insertions(+), 17 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 2137836ed7fa..b38b39f6b67b 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -181,14 +181,16 @@ enum maple_type { /* Flags: - * MAPLE_ALLOC_RANGE - This tree is used to store allocation ranges. Use - * alloc range types (MAPLE_ARANGE_*) + * MAPLE_ALLOC_RANGE Use allocation ranges (tracks gaps) in this tree + * MAPLE_RCU Operate in read/copy/update mode for multi-readers. */ -#define MAPLE_ALLOC_RANGE 1 +#define MAPLE_ALLOC_RANGE 1 // Bit 0 +#define MAPLE_RCU 2 // Bit 1 +#define MAPLE_HEIGHT_OFFSET 2 // Bits 2-4 +#define MAPLE_HEIGHT 28 // Bits 2-4 struct maple_tree { spinlock_t ma_lock; unsigned int ma_flags; - unsigned int ma_height; void __rcu *ma_root; }; @@ -197,7 +199,6 @@ struct maple_tree { .ma_lock = __SPIN_LOCK_UNLOCKED(name.ma_lock), \ .ma_flags = flags, \ .ma_root = NULL, \ - .ma_height = 0, \ } #define DEFINE_MTREE(name) \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 3abf37f4a4d9..3e6a87224995 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -142,6 +142,23 @@ static void ma_free_rcu(struct maple_node *node) call_rcu(&node->rcu, mt_free_rcu); } +static unsigned int mt_height(const struct maple_tree *mt) +{ + return (mt->ma_flags & MAPLE_HEIGHT) >> MAPLE_HEIGHT_OFFSET; +} + +static void mas_set_height(struct ma_state *mas) +{ + unsigned int new_flags = mas->tree->ma_flags; + new_flags &= ~MAPLE_HEIGHT; + new_flags |= mas->depth << MAPLE_HEIGHT_OFFSET; + mas->tree->ma_flags = new_flags; +} + +static unsigned int mas_mt_height(struct ma_state *mas) +{ + return mt_height(mas->tree); +} static inline enum maple_type mte_node_type(const struct maple_enode *entry) { @@ -1391,7 +1408,7 @@ static inline void mas_replace(struct ma_state *mas, bool advanced) mn->parent = ma_parent_ptr( ((unsigned long)mas->tree | MA_ROOT_PARENT)); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - mas->tree->ma_height = mas->depth; + mas_set_height(mas); } else { mte_set_rcu_slot(parent, slot, mas->node); } @@ -2157,7 +2174,7 @@ static inline bool mast_new_root(struct maple_subtree_state *mast, mast_topiary(mast); } while (!mte_is_root(mast->orig_l->node)); } else if ((mast->orig_l->node != mas->node) && - (mast->l->depth > mas->tree->ma_height)) { + (mast->l->depth > mas_mt_height(mas))) { mat_add(mast->free, mas->node); } @@ -2411,6 +2428,7 @@ static inline bool mas_split_final_node(struct maple_subtree_state *mast, struct ma_state *mas, int height) { struct maple_enode *ancestor; + unsigned int mas_height = mas_mt_height(mas); if (height <= mas->full_cnt) return false; @@ -2430,8 +2448,10 @@ static inline bool mas_split_final_node(struct maple_subtree_state *mast, mte_set_parent(mast->r->node, ancestor, mas_get_slot(mast->r)); mte_to_node(ancestor)->parent = mas_mn(mas)->parent; // New root requires a new height. - if (mas->full_cnt >= mas->tree->ma_height) - mas->tree->ma_height++; + if (mas->full_cnt >= mas_height) { + mas->depth = mas_height + 1; + mas_set_height(mas); + } mast->l->node = ancestor; mab_mas_cp(mast->bn, 0, mt_slots[mast->bn->type] - 1, mast->l); @@ -2637,7 +2657,7 @@ static inline int mas_commit_b_node(struct ma_state *mas, if ((b_node->b_end < mt_min_slot_cnt(mas->node)) && (!mte_is_root(mas->node)) && - (mas->tree->ma_height > 1)) + (mas_mt_height(mas) > 1)) return mas_rebalance(mas, b_node); @@ -2702,7 +2722,8 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) #endif /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); - mas->tree->ma_height = 1; + mas->depth = 1; + mas_set_height(mas); return slot; } static inline int ma_root_ptr(struct ma_state *mas, void *entry, @@ -3008,7 +3029,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) /* Node rebalancing may occur due to this store, so there may be two new * entries per level plus a new root. */ - node_cnt += 1 + mas->tree->ma_height * 2; + node_cnt += 1 + mas_mt_height(mas) * 2; mas_node_cnt(mas, node_cnt); if (mas_is_err(mas)) return 0; @@ -3064,7 +3085,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) l_mas.index = l_mas.last = mas->index; // Calc the number of iterations of combining and splitting that will // need to occur. - count = mas_cnt_positive(mas) + mas->tree->ma_height - mas->depth + 1; + count = mas_cnt_positive(mas) + mas_mt_height(mas) - mas->depth + 1; // Combine l_mas and r_mas and split them up evenly again. return mas_spanning_rebalance(mas, &mast, count); @@ -4457,7 +4478,7 @@ static inline void mas_dup_tree_start(struct ma_state *oldmas, if (!mte_is_leaf(oldmas->node)) { *node_cnt += mas_data_end(oldmas) + 1; - *node_cnt *= 1 << (4 * (oldmas->tree->ma_height - 2)); // assume all other levels full. + *node_cnt *= 1 << (4 * (mas_mt_height(oldmas) - 2)); // assume all other levels full. } mas_dup_alloc(mas, node_cnt); @@ -4811,7 +4832,6 @@ void mtree_direct_destroy(struct maple_tree *mt) } mt->ma_flags = 0; - mt->ma_height = 0; mt->ma_root = NULL; mtree_unlock(mt); } @@ -4824,7 +4844,6 @@ void mtree_destroy(struct maple_tree *mt) mte_destroy_walk(mt->ma_root, mt); mt->ma_flags = 0; - mt->ma_height = 0; rcu_assign_pointer(mt->ma_root, NULL); mtree_unlock(mt); } @@ -4996,7 +5015,7 @@ void mt_dump(const struct maple_tree *mt) void *entry = mt->ma_root; pr_info("maple_tree("MA_PTR") flags %X, height %u root "MA_PTR"\n", - mt, mt->ma_flags, mt->ma_height, entry); + mt, mt->ma_flags, mt_height(mt), entry); if (!xa_is_node(entry)) mt_dump_entry(entry, 0, 0, 0); else if (entry) -- 2.50.1