From d1a8cee653624b2f07cdd7077461cd202fd0e479 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 15 Nov 2019 13:03:57 -0500 Subject: [PATCH] maple_tree: Fix mas_prev to wrap on mas->node == MAS_START When passed MAS_START and calling mas_prev, return the last entry. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 153 +++++++++++++++++++++++++++++++++++++---------- 1 file changed, 122 insertions(+), 31 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 172300cf246c..c85d6d9ba346 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1022,6 +1022,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) mas->node = MAS_NONE; mas->min = 0; mas->max = ULONG_MAX; + mas_set_slot(mas, 0); if (!mas->tree->ma_root) // empty tree. goto done; @@ -1377,10 +1378,10 @@ static inline void mas_update_gap(struct ma_state *mas) * mas->max if no node is found. Node is returned as mas->node which may be * MAS_NONE. * - * Note, the slot for the first node is not valid if it is a leaf. + * Note, if we descend to a leaf, then the slot is not valid. * * @mas: maple state - * @max: The maximum index to consider valid. + * @limit: The maximum index to consider valid. */ static inline unsigned long mas_first_node(struct ma_state *mas, unsigned long limit) @@ -1404,7 +1405,7 @@ static inline unsigned long mas_first_node(struct ma_state *mas, continue; } - + // Non-leaf nodes need to descend. if (!mte_is_leaf(mas->node)) { mas->max = pivot; mas->min = min; @@ -1420,7 +1421,9 @@ no_entry: } /* Private * - * Returns the first entry. + * Returns the pivot which points to the entry with the lowest index. + * @mas slot is set to the entry location. + * @limit is the maximum index to check. * */ static inline unsigned long mas_first_entry(struct ma_state *mas, @@ -1440,13 +1443,18 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, if (!mas_get_slot(mas)) return mas->min; else - return mas_get_safe_pivot(mas, mas_get_slot(mas)-1); + return mas_get_safe_pivot(mas, + mas_get_slot(mas) - 1); } mas_set_slot(mas, 0); } } + +/* Private + * mte_destroy_walk: Free the sub-tree from @mn and below. + */ void mte_destroy_walk(struct maple_enode *mn) { struct maple_enode *node; @@ -2436,18 +2444,6 @@ ascend: no_entry: mas->node = MAS_NONE; } - -static inline void* mas_prev_entry(struct ma_state *mas, unsigned long min) -{ - if (mas->node == MAS_NONE) - return NULL; - - mas_prev_node(mas, min); - if (mas->node == MAS_NONE) - return NULL; - - return mte_get_rcu_slot(mas->node, mas_get_slot(mas)); -} /* * Find the next non-null entry at the same level in the tree. The next value * will be mas->node[mas_get_slot(mas)] or MAS_NONE. @@ -2535,10 +2531,10 @@ no_entry: /** Private * prev node entry */ -static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long min, - unsigned long *piv) +static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long limit, + unsigned long *max) { - unsigned long pivot; + unsigned long pivot = mas->max; unsigned char slot = mas_get_slot(mas); void *entry; @@ -2548,10 +2544,9 @@ static inline bool mas_prev_nentry(struct ma_state *mas, unsigned long min, slot--; do { pivot = mas_get_safe_pivot(mas, slot); - if (pivot < min) + if (pivot < limit) goto no_entry; - *piv = pivot; entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) goto found; @@ -2561,6 +2556,7 @@ no_entry: return false; found: + *max = pivot; mas_set_slot(mas, slot); return true; } @@ -2606,6 +2602,47 @@ found: mas_set_slot(mas, slot); return true; } +/* Private + * + * Returns the pivot which points to the entry with the highest index. + * @mas slot is set to the entry location. + * @limit is the minimum index to check. + * + */ +static inline void* mas_last_entry(struct ma_state *mas, + unsigned long limit) +{ + unsigned long prev_min, prev_max, range_start = 0; + unsigned char slot = 1; + + if (mas_start(mas) || mas_is_none(mas)) + return NULL; + + prev_min = mas->min; + prev_max = mas->max; + while (range_start < limit) { + mas_set_slot(mas, slot); + if (!mas_next_nentry(mas, limit, &range_start)) { + void *entry = mte_get_rcu_slot(mas->node, slot - 1); + if (mte_is_leaf(mas->node)) { + mas->index = range_start; + return entry; + } + mas->max = prev_max; + mas->min = prev_min; + mas->node = entry; + slot = 0; + } else { + slot = mas_get_slot(mas) + 1; + prev_min = prev_max + 1; + if (range_start > prev_min) + prev_min = range_start; + range_start = prev_min; + prev_max = mas->last; + } + } + return NULL; +} /** Private * @@ -2650,6 +2687,7 @@ retry: entry = mte_get_rcu_slot(mas->node, mas_get_slot(mas)); if (mas_dead_node(mas, index)) goto retry; + return entry; } @@ -2670,6 +2708,7 @@ static inline void *_mas_next(struct ma_state *mas, unsigned long max, if (!mas->node || mas_is_start(mas)) { // First run. unsigned long range_max; + entry = mas_range_load(mas, range_start, &range_max); } @@ -2693,6 +2732,61 @@ static inline void *mas_next(struct ma_state *mas, unsigned long max) } EXPORT_SYMBOL_GPL(mas_next); +/* Private + * + * _mas_prev() - Find the previous entry from the current mas state. + * @mas the current maple state (must have a valid slot) + */ +static inline void* _mas_prev(struct ma_state *mas, unsigned long limit) +{ + unsigned long max = mas->max; + unsigned char slot; + + while(!mas_is_none(mas)) { + if (mas_prev_nentry(mas, limit, &max)) + break; + + mas_prev_node(mas, limit); + mas_set_slot(mas, mt_slot_count(mas->node) - 1); + } + + if (mas->node == MAS_NONE) + return NULL; + + mas->last = max; + slot = mas_get_slot(mas); + if (slot) + mas->index = mas_get_safe_pivot(mas, slot - 1) + 1; + else + mas->index = mas->min; + + return mte_get_rcu_slot(mas->node, mas_get_slot(mas)); +} + +/* + * mas_prev() - Get the previous entry. Can return the zero entry. + * + * + */ +static inline void *mas_prev(struct ma_state *mas, unsigned long min) +{ + void *entry; + if (mas->node && !mas_searchable(mas)) + return NULL; + + if (!mas->node) + mas->node = MAS_START; + + if (mas_is_start(mas)) { + mas_start(mas); + return mas_last_entry(mas, ULONG_MAX); + } + + entry = _mas_prev(mas, min); + return entry; +} +EXPORT_SYMBOL_GPL(mas_prev); + static inline int mas_coalesce_node(struct ma_state *mas, unsigned char end, unsigned char coalesce, bool replace) { @@ -2785,7 +2879,7 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, unsigned char all_slots; // Total slots needed for this and right node. unsigned char l_slot_cnt, r_slot_cnt; // left and right slot counts unsigned char trimmed = 0; // Trimmed terminating null range from left - unsigned long l_piv, r_piv; // left and right pivots + unsigned long l_piv, r_piv = 0; // left and right pivots unsigned char r_end, r_coalesce; // right node end and values that can be coalesced. unsigned char node_cnt; // Number of nodes to allocate unsigned long this_max = mas->max, this_min = mas->min; // ma state saves for this entry @@ -3453,7 +3547,7 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, enum maple_type type; struct maple_enode *next; unsigned long pivot = 0; - unsigned long pivot_cnt, max, min, i; + unsigned long max, min, i; bool ret = false; min = mas->min; @@ -3461,7 +3555,6 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, while (true) { type = mte_node_type(mas->node); - pivot_cnt = mt_pivots[type]; if (ma_is_leaf(type)) // Leaf. ret = true; @@ -3469,8 +3562,8 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, skip_entry: switch (type) { default: - for (i = mas_get_slot(mas); i < pivot_cnt; i++) { - pivot = _mte_get_pivot(mas->node, i, type); + for (i = mas_get_slot(mas); i < mt_slots[type]; i++) { + pivot = _mas_get_safe_pivot(mas, i, type); if (i != 0 && pivot == 0) { i = MAPLE_NODE_SLOTS; goto done; @@ -3483,9 +3576,6 @@ skip_entry: min = pivot + 1; } - if ((i == pivot_cnt - 1) && (mas->index > pivot)) - i++; - if (ret) goto done; break; @@ -3592,7 +3682,7 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index) */ void *mas_find(struct ma_state *mas, unsigned long max) { - unsigned long index = 0; + unsigned long index; void *entry = NULL; entry = _mas_next(mas, max, &index); @@ -4118,6 +4208,7 @@ retry: void *mas_load(struct ma_state *mas) { unsigned long range_max, range_min; + return mas_range_load(mas, &range_min, &range_max); } static inline bool mas_rewind_node(struct ma_state *mas) -- 2.50.1