From 183ab83e77d682d47d41c4497c3299a7bcfbff5d Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 17 Jul 2020 17:08:37 -0400 Subject: [PATCH] maple_tree: Drop deleted/retry/skip logic Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 66 +++++++++---------------------------------- lib/test_maple_tree.c | 4 +-- 2 files changed, 15 insertions(+), 55 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index be68f2890701..b10e34451b30 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1127,7 +1127,7 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) if (ma_is_dense(mt)) { for (i = 0; i < mt_slot_count(mas->node); i++) { entry = mas_get_rcu_slot(mas, i); - if (!mt_is_empty(entry) || xa_is_retry(entry)) { + if (!mt_is_empty(entry)) { if (gap > max_gap) max_gap = gap; gap = 0; @@ -1149,7 +1149,7 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) gap = pend - pstart + 1; entry = mas_get_rcu_slot(mas, i); - if (!mt_is_empty(entry) || xa_is_retry(entry)) + if (!mt_is_empty(entry)) goto next; if (gap > max_gap) @@ -2981,7 +2981,6 @@ static inline void mas_next_slot(struct ma_state *mas, unsigned long max) // walk up. while (1) { slot = mte_parent_slot(mas->node); -walk_again: if (mte_is_root(mas->node)) goto no_entry; @@ -3008,19 +3007,6 @@ walk_down: mas->min = mas_get_safe_pivot(mas, slot - 1) + 1; mas->max = mas_get_safe_pivot(mas, slot); entry = mas_get_rcu_slot(mas, slot); - if (xa_is_skip(entry)) { - if (mas->max >= max) { - goto no_entry; - } else if (slot < mt_slot_count(mas->node)) { - slot++; - goto walk_down; - } else if (mte_is_root(mas->node)) { - goto no_entry; - } else { - goto walk_again; - } - } - mas->node = entry; if (mt_is_empty(mas->node)) goto no_entry; @@ -3138,7 +3124,7 @@ restart_prev_node: break; mn = mas_get_rcu_slot(mas, slot); - if (mt_is_empty(mn) || xa_is_retry(mn)) + if (mt_is_empty(mn)) continue; if (level == 1) { @@ -3213,7 +3199,7 @@ restart_next_node: break; mn = mas_get_rcu_slot(mas, slot); - if (mt_is_empty(mn) || xa_is_retry(mn)) { + if (mt_is_empty(mn)) { prev_piv = pivot; continue; } @@ -3534,7 +3520,7 @@ static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) /* check if this slot is full */ entry = mas_get_rcu_slot(mas, i); - if (entry && !xa_is_deleted(entry)) { + if (entry) { this_gap = 0; goto next_slot; } @@ -4178,7 +4164,7 @@ no_gap: * */ void *mas_range_load(struct ma_state *mas, unsigned long *range_min, - unsigned long *range_max, bool skip_retry) + unsigned long *range_max) { void *entry = NULL; @@ -4201,12 +4187,9 @@ retry: if (mas_is_none(mas)) return NULL; - if (!entry || xa_is_deleted(entry)) + if (!entry) return NULL; - if (skip_retry && xa_is_retry(entry)) - goto retry; - return entry; } @@ -4214,7 +4197,7 @@ void *mas_load(struct ma_state *mas) { unsigned long range_max, range_min; - return mas_range_load(mas, &range_min, &range_max, true); + return mas_range_load(mas, &range_min, &range_max); } /** Private @@ -4234,7 +4217,7 @@ static inline void *_mas_next(struct ma_state *mas, unsigned long limit, if (!mas->node || mas_is_start(mas)) {// First run. *range_start = 0; mas_start(mas); - entry = mas_range_load(mas, range_start, &range_max, false); + entry = mas_range_load(mas, range_start, &range_max); mas->last = range_max; } @@ -4296,7 +4279,7 @@ void *_mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max, entry = mas_get_rcu_slot(&mas, slot); mas.last = range_end; - if (mt_is_empty(entry) || xa_is_zero(entry) || xa_is_retry(entry)) + if (mt_is_empty(entry) || xa_is_zero(entry)) entry = NULL; while (mas_search_cont(&mas, range_start, max, entry)) { @@ -4315,11 +4298,11 @@ void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max) { return _mt_find(mt, index, max, true); } EXPORT_SYMBOL(mt_find); + /* * mas_next() - Get the next entry. Can return the zero entry. mas->node * must be a valid node and not a special value. Unsafe for single entry * trees. - * */ void *mas_next(struct ma_state *mas, unsigned long max) { @@ -4340,7 +4323,7 @@ static inline void *mas_erase(struct ma_state *mas) unsigned long r_max, r_min; void *entry = NULL; - entry = mas_range_load(mas, &r_min, &r_max, true); + entry = mas_range_load(mas, &r_min, &r_max); retry: mas->node = MAS_START; mas->index = r_min; @@ -4602,12 +4585,6 @@ void mt_dump_entry(void *entry, unsigned long min, unsigned long max, xa_to_value(entry), entry); else if (xa_is_zero(entry)) pr_cont("zero (%ld)\n", xa_to_internal(entry)); - else if (xa_is_deleted(entry)) - pr_cont("deleted (%ld)\n", xa_to_internal(entry)); - else if (xa_is_skip(entry)) - pr_cont("skip (%ld)\n", xa_to_internal(entry)); - else if (xa_is_retry(entry)) - pr_cont("retry (%ld)\n", xa_to_internal(entry)); else if (mt_is_reserved(entry)) pr_cont("UNKNOWN ENTRY ("MA_PTR")\n", entry); else @@ -4637,12 +4614,6 @@ void mt_dump_range64(void *entry, unsigned long min, unsigned long max, break; if (leaf) mt_dump_entry(node->slot[i], first, last, depth + 1); - else if (xa_is_deleted(node->slot[i])) - mt_dump_entry(node->slot[i], first, last, depth + 1); - else if (xa_is_skip(node->slot[i])) - mt_dump_entry(node->slot[i], first, last, depth + 1); - else if (xa_is_retry(node->slot[i])) - mt_dump_entry(node->slot[i], first, last, depth + 1); else if (node->slot[i]) mt_dump_node(node->slot[i], first, last, depth + 1); @@ -4683,12 +4654,6 @@ void mt_dump_arange64(void *entry, unsigned long min, unsigned long max, break; if (leaf) mt_dump_entry(node->slot[i], first, last, depth + 1); - else if (xa_is_deleted(node->slot[i])) - mt_dump_entry(node->slot[i], first, last, depth + 1); - else if (xa_is_skip(node->slot[i])) - mt_dump_entry(node->slot[i], first, last, depth + 1); - else if (xa_is_retry(node->slot[i])) - mt_dump_entry(node->slot[i], first, last, depth + 1); else if (node->slot[i]) mt_dump_node(node->slot[i], first, last, depth + 1); @@ -4789,13 +4754,8 @@ void mas_validate_gaps(struct ma_state *mas) } else { void *entry = mas_get_rcu_slot(mas, i); gap = mte_get_gap(mte, i); - if (xa_is_skip(entry)) { - //pr_err("%s: skip entry missed by spanning add?\n"); - } else if (mt_is_empty(entry) || xa_is_retry(entry)) { + if (mt_is_empty(entry)) { if (gap != p_end - p_start + 1) { - if (xa_is_retry(entry)) - pr_err("retry\n"); - pr_err(MA_PTR"[%u] -> "MA_PTR" %lu != %lu - %lu + 1\n", mas_mn(mas), i, mas_get_rcu_slot(mas, i), gap, diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 0c4ffd5a177d..ab5af923e746 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -905,8 +905,8 @@ static noinline void check_erase2_testset(struct maple_tree *mt, set[i+1], set[i+2]); #endif - s_entry = mas_range_load(&mas_start, &s_min, &s_max, false); - e_entry = mas_range_load(&mas_end, &e_min, &e_max, false); + s_entry = mas_range_load(&mas_start, &s_min, &s_max); + e_entry = mas_range_load(&mas_end, &e_min, &e_max); switch (set[i]) { case SNULL: -- 2.50.1