From 87b1fb9adc1b50bcf9b695ff6f0205ee9f84d021 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 19 Dec 2019 11:32:14 -0500 Subject: [PATCH] maple_tree: Fix mas_find to skip empty nodes and set mas.index correctly Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 57 ++++++++++++++----------------------------- lib/test_maple_tree.c | 1 + 2 files changed, 19 insertions(+), 39 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 8053dc9cfb28..1d355286e793 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1172,7 +1172,6 @@ static inline unsigned char mas_no_dense_split(struct ma_state *mas, } } - // Insert happens in leaf if (attempt_insert && (cp.index <= piv)) { if (written_piv != cp.index - 1) { // Insert a previous entry.. @@ -1632,35 +1631,6 @@ static inline unsigned long mas_copy(struct ma_state *mas, struct ma_cp *cp) return _mas_copy(mas, cp, mas->min); } -static inline int mas_split_data(struct ma_state *mas, struct maple_enode *left, - struct maple_enode *right, unsigned char split, - unsigned long r_max) -{ - - MA_CP(cp, mas->node, left, 0, split); - - mas_copy(mas, &cp); - cp.src_start = split + 1; - - if (cp.src_start > mt_node_max(mas->node)) - return split; - - cp.src_end = mt_slot_count(mas->node) - 1; - if (right) { - cp.dst = right; - cp.dst_start = 0; - mas_copy(mas, &cp); - if (cp.dst_start + split >= mt_pivot_count(cp.dst)) { - unsigned char slot = cp.dst_start; - - if (mt_is_empty(mte_get_rcu_slot(right, slot))) - slot--; - mte_set_pivot(right, slot, r_max); - } - } - return split; -} - static inline void mte_adopt_children(struct maple_enode *parent) { @@ -2118,6 +2088,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, goto update_gap; } + printk("slot %u\n", slot); if (slot > slot_cnt) slot = old_end + 1; @@ -2161,8 +2132,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, if (new_end > slot_cnt) { /* Not enough space in the node */ - unsigned char split = mas_split(mas, slot, active, new_end, - entry); + mas_split(mas, slot, active, new_end, entry); if (mas_is_err(mas)) return 0; @@ -2670,11 +2640,15 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, unsigned long *range_start) { unsigned long pivot = mas->min; - unsigned long r_start = *range_start; + unsigned long r_start = mas->min; unsigned char slot = mas_get_slot(mas); unsigned char count = mt_slot_count(mas->node); void *entry; + if (slot) + r_start = mas_get_safe_pivot(mas, slot - 1) + 1; + + printk("next entry starting slot %u\n", slot); while (slot < count) { pivot = mas_get_safe_pivot(mas, slot); @@ -2768,19 +2742,24 @@ retry: *range_start = mas->last + 1; while (!mas_is_none(mas)) { - unsigned char p_slot = 0; + struct maple_enode *last_node = mas->node; + slot = mas_get_slot(mas); if (slot > mt_slot_count(mas->node)) goto next_node; if (!mte_is_leaf(mas->node) || !mas_get_slot(mas)) { *range_start = mas_first_entry(mas, limit); - if (mas_is_none(mas)) - return NULL; + if (mas_is_none(mas)) { + mas->node = last_node; + goto next_node; + } } - if (mas_next_nentry(mas, limit, range_start)) + if (mas_next_nentry(mas, limit, range_start)) { + printk("nentry break\n"); break; + } if (*range_start > limit) return NULL; @@ -3708,7 +3687,6 @@ skip_entry: mas_set_slot(mas, 0); } done: - printk("Set min %lu\n", min); mas_set_slot(mas, i); *range_max = max; *range_min = min; @@ -3974,9 +3952,10 @@ skip_r_count: mas->alloc = NULL; // Copy left side + mas_reset(&l_mas); mas_for_each(&l_mas, entry, mas->index - 1) { new_mas.index = l_mas.index; - new_mas.last = mas_get_safe_pivot(&l_mas, mas_get_slot(&l_mas)); + new_mas.last = l_mas.index; printk("Insert %lu->%lu\n", new_mas.index, new_mas.last); ma_inactive_insert(&new_mas, entry); if (mas_is_err(&new_mas)) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index d578bfe524f4..3a8a0e2122bd 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -962,6 +962,7 @@ static noinline void check_erase2_testset(struct maple_tree *mt, mas_reset(&mas); mas.index = 0; mas_for_each(&mas, foo, ULONG_MAX) { + printk("%lu-%lu -> %p\n", mas.index, mas.last, foo); if (mas_retry(&mas, foo)) continue; check++; -- 2.50.1