From 0e83ca2fe0c94a6349e7dc14d9dc46833b0d7904 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 15 Oct 2019 14:38:45 -0400 Subject: [PATCH] maple_tree: Change mas_start to return the entry in a single pointer tree. There are now three cases of the mas_start return: If it's an empty tree: NULL & mas->node == MAS_NONE If it's a single entry: The entry & mas->node == MAS_ROOT If it's a tree: NULL & mas->node == safe root node. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 144 ++++++++++++++++++++++++++++-------------- lib/test_maple_tree.c | 2 + 2 files changed, 100 insertions(+), 46 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 793f3e18bbf3..f955ff9d01aa 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -158,6 +158,15 @@ static inline void mas_set_err(struct ma_state *mas, long err) { mas->node = MA_ERROR(err); } +static inline bool mas_is_ptr(struct ma_state *mas) +{ + return mas->node == MAS_ROOT; +} +static inline bool mas_is_none(struct ma_state *mas) +{ + return mas->node == MAS_NONE; +} + static inline bool mas_is_start(struct ma_state *mas) { return mas->node == MAS_START; @@ -945,27 +954,46 @@ static inline struct maple_node *mas_node_cnt(struct ma_state *ms, int count) return ms->alloc; } +/** Private + * Sets up maple state for operations by setting mas->min = 0 & mas->node to + * certain values. + * returns: + * - If it's an empty tree: NULL & mas->node == MAS_NONE + * - If it's a single entry: The entry & mas->node == MAS_ROOT + * - If it's a tree: NULL & mas->node == safe root node. + */ static inline struct maple_enode *mas_start(struct ma_state *mas) { + void *entry = NULL; + + if (mas_is_err(mas)) + goto done; + if (mas_is_start(mas)) { struct maple_enode *root; + mas->node = MAS_NONE; mas->min = 0; if (!mas->tree->ma_root) // empty tree. - return NULL; + goto done; + + root = mte_safe_root(mas->tree->ma_root); if (!xa_is_node(mas->tree->ma_root)) { + // Single entry tree. if (mas->index > 0) - return NULL; + goto done; + + entry = mas->tree->ma_root; mas->node = MAS_ROOT; mas_set_slot(mas, MAPLE_NODE_SLOTS); - return mas->node; + } else { + mas->node = root; } - root = mte_safe_root(mas->tree->ma_root); - mas->max = mt_node_max(root); - return root; } - return mas->node; + +done: + return entry; } /* Private @@ -2288,7 +2316,7 @@ static inline void mas_prev_node(struct ma_state *mas, unsigned long min) restart_prev_node: level = 0; slot = mas_get_slot(mas); - if (mte_is_root(mas->node)) + if (mte_is_root(mas->node) || mas->node == MAS_NONE) goto no_entry; while (1) { @@ -2377,12 +2405,14 @@ restart_next_node: struct maple_enode *mn; unsigned long prev_piv; + if (mte_is_root(mas->node) || mas->node == MAS_NONE) + goto no_entry; + mn = mas->node; slot = mas_get_slot(mas); start_piv = mas_get_safe_pivot(mas, slot); level++; - if (!mte_is_root(mas->node)) - mas_encoded_parent(mas); + mas_encoded_parent(mas); if (!mas_safe_slot(mas, &slot, 1)) { if (mte_is_root(mas->node)) @@ -3286,13 +3316,16 @@ done: static inline bool _mas_walk(struct ma_state *mas) { - mas->node = mas_start(mas); - if (!mas->node) { + void *entry = mas_start(mas); + if (entry) + return true; + + if (mas_is_none(mas)) { mas_set_slot(mas, MAPLE_NODE_SLOTS); return false; } - if (mas->node == MAS_ROOT) + if (mas_is_ptr(mas)) return true; mas_set_slot(mas, 0); @@ -3320,6 +3353,9 @@ 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 (mas->node == MAS_NONE) + return 0; + if (!mas->node) return 0; @@ -3360,8 +3396,7 @@ void *mas_find(struct ma_state *mas, unsigned long max) goto not_found; if (mas_is_start(mas)) { - _mas_walk(mas); - if (!mas->node) + if (!_mas_walk(mas)) return NULL; if (mas->node == MAS_ROOT) @@ -3369,6 +3404,9 @@ void *mas_find(struct ma_state *mas, unsigned long max) do {} while (mas_dead_node(mas, mas->index)); + if (mas->node == MAS_NONE) + goto not_found; + slot = mas_get_slot(mas); last_piv = mas_get_safe_pivot(mas, slot); @@ -3442,11 +3480,13 @@ void *mt_find(struct maple_tree *mt, unsigned long start, rcu_read_lock(); _mas_walk(&mas); - if (!mas.node) + + if (mas_is_none(&mas)) goto done; - if (mas.node == MAS_ROOT) { - entry = mas.tree->ma_root; + if (mas_is_ptr(&mas)) { + if (!start) + entry = mas.tree->ma_root; goto done; } @@ -3465,7 +3505,7 @@ void *mt_find(struct maple_tree *mt, unsigned long start, retry: mas_safe_next_entry(&mas, max); - if (mas.node == MAS_NONE) + if (mas_is_none(&mas)) goto done; @@ -3495,17 +3535,16 @@ void *mt_find_after(struct maple_tree *mt, unsigned long *index, rcu_read_lock(); _mas_walk(&mas); - if (!mas.node) + if (mas_is_none(&mas)) goto done; - if (mas.node == MAS_ROOT) { - entry = mas.tree->ma_root; + if (mas_is_ptr(&mas)) goto done; - } + retry: mas_set_slot(&mas, mas_get_slot(&mas) + 1); mas_safe_next_entry(&mas, max); - if (mas.node == MAS_NONE) + if (mas_is_none(&mas)) goto done; slot = mas_get_slot(&mas); @@ -3695,11 +3734,15 @@ static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) unsigned long last_piv; unsigned char slot, coalesce; - mas->node = mas_start(mas); - if (!mas->node) { + mas_start(mas); + if (mas_is_none(mas)) { mas_set_slot(mas, MAPLE_NODE_SLOTS); return; } + + if (mas_is_ptr(mas)) + return; + slot = mas_data_end(mas, mte_node_type(mas->node), &last_piv, &coalesce); mas_set_slot(mas, slot); @@ -3722,8 +3765,11 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size) { struct maple_enode *last = NULL; - mas->node = mas_start(mas); - if (!mas->node) + mas_start(mas); + if (mas_is_none(mas)) + return; + + if (mas_is_ptr(mas)) return; mas_set_slot(mas, 0); @@ -3781,8 +3827,11 @@ static inline int mas_add(struct ma_state *mas, void *entry, bool overwrite, leaf = _mas_walk(mas); slot = mas_get_slot(mas); - if (leaf == true && slot != MAPLE_NODE_SLOTS) { - if (!overwrite) { + if (leaf == true) { + if (slot == MAPLE_NODE_SLOTS) { + if (mas->index == 0 && !overwrite) + goto exists; + } else if (!overwrite) { void *entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) @@ -3828,29 +3877,26 @@ static int mas_fill_gap(struct ma_state *mas, void *entry, unsigned char slot, * and a size (size), find the lowest location in the min-max window in the * tree which this allocation fits and set index to that value. * - * Returns: 0 on success, -EBUSY otherwise. + * Returns: 0 on success, -ENOMEM if allocation fails, -EBUSY otherwise. */ static inline int ma_alloc(struct ma_state *mas, void *entry, unsigned long size, unsigned long *index) { unsigned char slot = MAPLE_NODE_SLOTS; unsigned long min; + mas_start(mas); - mas->node = mas_start(mas); - if (!mas->node) { - slot = 0; - goto empty_tree; - } - - if (!xa_is_node(rcu_dereference(mas->tree->ma_root))) { + if (mas_is_none(mas) || mas_is_ptr(mas)) { ma_root_expand(mas, entry); + if (mas_is_err(mas)) + return xa_err(mas->node); + if (!mas->index) return mte_get_pivot(mas->node, 0); return mte_get_pivot(mas->node, 1); } - mas_awalk(mas, size); - // cannot be an empty tree here. + mas_awalk(mas, size); // Must be walking a tree. if (mas_is_err(mas)) return xa_err(mas->node); @@ -3868,7 +3914,6 @@ static inline int ma_alloc(struct ma_state *mas, void *entry, if (mas->index < min) mas->index = min; -empty_tree: return mas_fill_gap(mas, entry, slot, size, index); no_gap: @@ -3888,13 +3933,14 @@ static inline int ma_rev_alloc(struct ma_state *mas, void *entry, { unsigned char slot = MAPLE_NODE_SLOTS; - mas->node = mas_start(mas); - if (!mas->node) { + mas_start(mas); + + if (mas_is_none(mas)) { slot = 0; goto empty_tree; } - if (!xa_is_node(rcu_dereference(mas->tree->ma_root))) { + if (mas_is_ptr(mas)) { ma_root_expand(mas, entry); if (!mas->index) return mte_get_pivot(mas->node, 0); @@ -3957,8 +4003,14 @@ void *mas_walk(struct ma_state *mas) leaf = _mas_walk(mas); slot = mas_get_slot(mas); - if (leaf == true && slot != MAPLE_NODE_SLOTS) - entry = mte_get_rcu_slot(mas->node, slot); + if (leaf == true) { + if (slot == MAPLE_NODE_SLOTS) { + if (mas->index == 0) + return root; + } else { + entry = mte_get_rcu_slot(mas->node, slot); + } + } return entry; } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 88131b4edc2f..0d71cfb2b1ee 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -951,8 +951,10 @@ static noinline void check_alloc_range(struct maple_tree *mt) check_insert_range(mt, range[i] >> 12, (range[i + 1] >> 12) - 1, xa_mk_value(range[i] >> 12), 0); } + mt_dump(mt); for (i = 0; i < req_range_cnt; i += 5) { + printk("%s: insert %i\n", __func__, i); check_mtree_alloc_range(mt, req_range[i] >> 12, // start req_range[i+1] >> 12, // end -- 2.50.1