From c0ef7be00f10d760e43f119f3df3c59e9d760fc0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 21 Apr 2020 15:50:51 -0400 Subject: [PATCH] maple_tree: Fix overrunning end of node into RETRY entries. When entries are moved and replaced with a RETRY, the node will end prior to hitting a 0 pivot or the end of the node. Fix this scenario by detecting the pivot > mas->max and handle these cases correctly. This also fixes the validation code to avoid checking the range on RETRY entries. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 43 +++++++++++++++++++++++++++++++------------ 1 file changed, 31 insertions(+), 12 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9a1aa95dafea..bcf03a1fcceb 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1174,7 +1174,7 @@ done: } /* Private - * mas_data_end() - Find the end of the data (slot +1). Sets the value of the + * mas_data_end() - Find the end of the data (slot). Sets the value of the * last pivot to @last_piv, sets @coalesce to the number of slots that can be * removed by coalescing. */ @@ -1183,7 +1183,7 @@ static inline unsigned char _mas_data_end(const struct ma_state *mas, unsigned char *coalesce) { struct maple_enode *mn = mas->node; - unsigned long piv = mas->min, prev_piv = mas->min; + unsigned long piv = mas->min, prev_piv = mas->min - 1; unsigned char slot; unsigned char counted_null = 0; @@ -1192,7 +1192,9 @@ static inline unsigned char _mas_data_end(const struct ma_state *mas, void *entry; piv = _mas_get_safe_pivot(mas, slot, type); - if (!piv && slot) { // Past the end of data. + if ((piv == 0 && slot != 0) || + (piv > mas->max)) { + // Past the end of data. slot--; piv = prev_piv; // At this point, we are saying the previous slot is @@ -1214,7 +1216,7 @@ static inline unsigned char _mas_data_end(const struct ma_state *mas, entry = _mte_get_rcu_slot(mn, slot, type, mas->tree); if (mt_will_coalesce(entry)) { - if (piv == prev_piv || !slot) + if (piv == prev_piv) (*coalesce)++; } else if (entry == NULL) { @@ -1446,6 +1448,9 @@ static inline unsigned char mas_append_calc_split(struct ma_state *mas, if (!piv && slot) return ret; + if (piv > mas->max) // possibly a retry. + return ret; + range = piv - mas->min; if (range >= 8) { if (slot > half) @@ -1705,6 +1710,9 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) if (!pend && i) pend = mas->max; + if (pend > mas->max) // possibly a retry. + break; + gap = pend - pstart + 1; entry = mas_get_rcu_slot(mas, i); @@ -2403,6 +2411,9 @@ static inline int __mas_add_slot_cnt(struct ma_state *mas, if (!this_piv && this_slot) break; + if (this_piv > mas->max) // possibly a retry. + break; + if (this_piv == prev_piv && this_slot) goto skip_slot; @@ -2626,6 +2637,9 @@ static inline int mas_spanning_add(struct ma_state *mas, void *entry, if (!piv) break; + if (piv > r_mas.max) // possibly a retry. + break; + if (piv > r_mas.last) break; @@ -3228,6 +3242,9 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, while (slot < count) { pivot = mas_get_safe_pivot(mas, slot); + if (pivot > mas->max) // possibly a retry. + goto no_entry; + if (slot != 0 && pivot == 0) goto no_entry; @@ -5540,8 +5557,8 @@ void mas_validate_limits(struct ma_state *mas) entry = mas_get_rcu_slot(mas, i); if (prev_piv > piv) { if (!mt_will_coalesce(entry)) { - pr_err(MA_PTR"[%u] %lu < %lu\n", mas_mn(mas), i, - piv, prev_piv); + pr_err(MA_PTR"[%u] piv %lu < prev_piv %lu\n", + mas_mn(mas), i, piv, prev_piv); mt_dump(mas->tree); MT_BUG_ON(mas->tree, piv < prev_piv); } @@ -5558,13 +5575,15 @@ void mas_validate_limits(struct ma_state *mas) MT_BUG_ON(mas->tree, piv < mas->min); } } - if ((piv > mas->max) && !xa_is_retry(entry)) { - pr_err(MA_PTR"[%u] %lu > %lu\n", mas_mn(mas), i, piv, - mas->max); - mt_dump(mas->tree); - MT_BUG_ON(mas->tree, piv > mas->max); + if (!xa_is_retry(entry)) { + if ((piv > mas->max)) { + pr_err(MA_PTR"[%u] %lu > %lu\n", mas_mn(mas), i, + piv, mas->max); + mt_dump(mas->tree); + MT_BUG_ON(mas->tree, piv > mas->max); + } + prev_piv = piv; } - prev_piv = piv; } } -- 2.50.1