From 4136102410e71f09bf5d2329d8155cfdde5bb663 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 29 Jan 2019 15:06:00 -0500 Subject: [PATCH] maple_tree: Fix error in splitting on the right side When splitting on the right side, there were a number of logical errors: 1. Finding the parents type needed the parent to be encoded, so move the logic to a location better suited to use the encoded node. 2. ma_copy had an incorrect range (off by one). 3. mt_replace was not using the encoded node to find the parent's slot. This would always return zero. 4. ma_link had a potential overflow in the pivot. 5. The ma_state's min/max was not being updated and so the pivots were not always correct when using the min/max. 6. The data end detection needed to be updated to also check for ULONG_MAX. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 34 ++++++++++++++++++++-------------- lib/test_maple_tree.c | 39 ++++++++++++++++++++++++++++++++++++--- 2 files changed, 56 insertions(+), 17 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f50476304547..a07b73462e78 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -185,6 +185,7 @@ static inline bool ma_is_root(struct maple_node *node) return false; } +static void mas_update_limits(struct ma_state *ms, unsigned char slot); static inline void ma_encoded_parent(struct ma_state *mas) { struct maple_node *parent, *gparent; @@ -192,12 +193,16 @@ static inline void ma_encoded_parent(struct ma_state *mas) if (ma_is_root(mt_to_node(mas->node)->parent)) { mas->node = mt_safe_root(rcu_dereference(mas->tree->ma_root)); + mas->max = ULONG_MAX; + mas->min = 0; return; } parent = mt_parent(mas->node); gparent = mt_parent(parent); slot = mt_parent_slot(parent); + mas->node = gparent; + mas_update_limits(mas, slot); mas->node = rcu_dereference(gparent->mr64.slot[slot]); return; } @@ -340,6 +345,8 @@ unsigned char ma_data_end_r64(const struct maple_range_64 *mr64, last = mr64->pivot[data_end]; if (last == 0 && data_end > 0) return data_end; + if (last == ULONG_MAX) + return data_end; } if (mr64->slot[data_end] != NULL) @@ -381,14 +388,14 @@ void ma_copy(struct ma_state *mas, struct ma_cp *cp) while (sloc <= cp->src_end && dloc <= cp->dst_end) { - if (sloc != 0 && sloc < MAPLE_RANGE64_SLOTS - 2 && + if (sloc != 0 && sloc < MAPLE_RANGE64_SLOTS - 1 && src64->pivot[sloc] == 0) break; if (sloc < MAPLE_RANGE64_SLOTS - 1 && dloc < MAPLE_RANGE64_SLOTS - 1) dst64->pivot[dloc] = src64->pivot[sloc]; - else if (dloc > MAPLE_RANGE64_SLOTS - 1) + else if (dloc < MAPLE_RANGE64_SLOTS - 1) dst64->pivot[dloc] = mas->max; RCU_INIT_POINTER(dst64->slot[dloc], src64->slot[sloc]); @@ -441,7 +448,7 @@ void mt_replace(struct ma_state *mas) struct maple_node *mn = mt_to_node(mas->node); struct maple_node *parent; struct maple_range_64 *p64; - unsigned char slot = mt_parent_slot(mn); + unsigned char slot = mt_parent_slot(mas->node); struct maple_node *prev; if (ma_is_root(mas->node)) { @@ -495,7 +502,8 @@ static void ma_link(struct maple_node *new, struct maple_node *parent, struct maple_node *new_enc = mt_mk_node(new, type); mt_set_parent(new, parent, slot); - p64->pivot[slot] = pivot; + if (slot < MAPLE_RANGE64_SLOTS - 1) + p64->pivot[slot] = pivot; RCU_INIT_POINTER(p64->slot[slot], new_enc); if (!mt_is_leaf(new_enc)) ma_adopt_children(new); @@ -508,16 +516,18 @@ static int ma_split(struct ma_state *mas, unsigned char slot, unsigned char split, p_slot = 0, p_end = 0; struct maple_node *old_parent, *new_parent, *left, *right; enum maple_type ctype; // Child type. + enum maple_type ptype; // parent type. unsigned long pivot; if (ma_is_root(full)) { old_parent = full; + ptype = maple_range_64; } else { old_parent = mt_parent(mas->node); + p_slot = mt_parent_slot(mas->node); p_end = ma_data_end_r64(&old_parent->mr64, UINT_MAX); if (p_end >= MAPLE_RANGE64_SLOTS - 1) { /* Must split the parent */ - p_slot = mt_parent_slot(mas->node); ma_encoded_parent(mas); split = ma_split(mas, p_slot, p_end, 1); if (mas_is_err(mas)) @@ -526,8 +536,11 @@ static int ma_split(struct ma_state *mas, unsigned char slot, p_slot -= split; // Split will return the parent. old_parent = mt_to_node(mas->node); - mas->node = old_parent->mr64.slot[p_slot]; + } else { + ma_encoded_parent(mas); } + ptype = mt_node_type(mas->node); + mas->node = old_parent->mr64.slot[p_slot]; } mas_node_cnt(mas, 3); @@ -577,14 +590,7 @@ static int ma_split(struct ma_state *mas, unsigned char slot, // Set up maple state for replacement of node. // Note: old_parent may be the old parent or the full node. - if (ma_is_root(old_parent)) { - mas->node = mt_mk_node(new_parent, maple_range_64); - } else { - struct maple_node *gparent = mt_parent(old_parent); - - old_parent = gparent->mr64.slot[mt_parent_slot(old_parent)]; - mas->node = mt_mk_node(new_parent, mt_node_type(old_parent)); - } + mas->node = mt_mk_node(new_parent, ptype); // Replace the parent node & free the old parent. mt_replace(mas); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index b77d8d78ec93..807160e282b6 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -204,25 +204,56 @@ static noinline void check_seq(struct maple_tree *mt) mtree_destroy(mt); } -static noinline void check_double_insert_leaf(struct maple_tree *mt) +static noinline void check_lb_not_empty(struct maple_tree *mt) { unsigned long i, j; unsigned long huge = 4000UL * 1000 * 1000; - MT_BUG_ON(mt, !mtree_empty(mt)); i = huge; while (i > 4096) { check_insert(mt, i, (void*) i); for (j = huge; j >= i; j /= 2) { + check_load(mt, j-1, NULL); check_load(mt, j, (void*) j); check_load(mt, j+1, NULL); } i /= 2; } mtree_destroy(mt); + +} +static noinline void check_lower_bound_split(struct maple_tree *mt) +{ + MT_BUG_ON(mt, !mtree_empty(mt)); + check_lb_not_empty(mt); } +static noinline void check_upper_bound_split(struct maple_tree *mt) +{ + unsigned long i, j; + unsigned long huge = 4000UL * 1000 * 1000; + + MT_BUG_ON(mt, !mtree_empty(mt)); + i = 4096; + while (i < huge) { + check_insert(mt, i, (void*) i); + for (j = i; j >= huge; j *= 2) { + check_load(mt, j-1, NULL); + check_load(mt, j, (void*) j); + check_load(mt, j+1, NULL); + } + i *= 2; + } + mtree_destroy(mt); +} +static noinline void check_mid_split(struct maple_tree *mt) +{ + unsigned long huge = 8000UL * 1000 * 1000; + check_insert(mt, huge, (void*) huge); + check_insert(mt, 0, (void*) 0); + check_lb_not_empty(mt); +} static DEFINE_MTREE(tree); static int maple_tree_seed(void) @@ -237,7 +268,9 @@ static int maple_tree_seed(void) mtree_init(&tree); check_new_node(&tree); - check_double_insert_leaf(&tree); + check_lower_bound_split(&tree); + check_upper_bound_split(&tree); + check_mid_split(&tree); check_load(&tree, set[0], NULL); // See if 15 -> NULL -- 2.50.1