From 4c0d859ef03a19feab889b0cf6a9562a65d2818e Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 17 Dec 2018 11:37:17 -0500 Subject: [PATCH] maple_tree: Add parent slot to maple state. Parent slot is needed when splitting and such, so keep track of it during walks of the tree. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 14 +++++++------- 2 files changed, 8 insertions(+), 7 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 7ba0432c8c40..b2e5300356f6 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -128,6 +128,7 @@ struct maple_state { unsigned long min; /* The smallest index to be found in %node */ unsigned long max; /* The largest index to be found in %node */ unsigned long slot_idx; /* The slot index from %node */ + unsigned long pslot_idx; /* The slot index from the parent %node */ struct maple_node *alloc; /* Allocated for this operation */ short flags; /* Different stuff */ }; diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 7b272ebdab59..85470e348109 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -206,6 +206,7 @@ static void *_maple_walk_4(struct maple_state *ms) { struct maple_node_4 *mn4 = &ms->node->map4; + ms->pslot_idx = ms->slot_idx; ms->slot_idx = ms->index - ms->min; return rcu_dereference(mn4->slot[ms->slot_idx]); } @@ -222,6 +223,7 @@ static void *_maple_walk_64(struct maple_state *ms, unsigned long val) break; } while (i++ < MAPLE_NODE64_MAX_SLOT - 1); + ms->pslot_idx = ms->slot_idx; ms->slot_idx = i; return rcu_dereference(mn64->slot[i]); } @@ -389,6 +391,7 @@ static void _maple_root_expand(struct maple_state *ms) if (r_entry != NULL) { RCU_INIT_POINTER(mn->map64.slot[0], r_entry); mn->map64.pivot[0] = 1; + ms->pslot_idx = 0; ms->slot_idx = 1; } @@ -539,18 +542,15 @@ void maple_link_node(struct maple_state *ms, left->parent = full->parent; right->parent = full->parent; - /* Get the slot_idx to overwrite in the parent */ - ms->node = full->parent; - _maple_walk_64(ms, ms->index); /* Shift the data over */ - maple_shift_64(target, ms->slot_idx, 1); + maple_shift_64(target, ms->pslot_idx, 1); /* Overwrite the duplicate slot data with the new right node */ - target->slot[ms->slot_idx + 1] = ma_mk_node(right); + target->slot[ms->pslot_idx + 1] = ma_mk_node(right); /* Overwrite the first pivot with the new value. This is fine * as the current slot has valid entries for this pivot */ - target->pivot[ms->slot_idx] = left64->pivot[l_end]; + target->pivot[ms->pslot_idx] = left64->pivot[l_end]; /* Set the first slot to the node with less pivots */ - target->slot[ms->slot_idx] = ma_mk_node(left); + target->slot[ms->pslot_idx] = ma_mk_node(left); /* Update the new nodes children's parent setting */ maple_update_parent(left); maple_update_parent(right); -- 2.50.1