From bbd08f83d3c07e136c2621a57d5d22dea000fa3b Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 10 Jan 2019 15:18:01 -0500 Subject: [PATCH] maple_tree: Avoid coalescing on insert if it is not needed. On insert, iterate over the pivots looking for matching ones to determine if slots need to be coalesced. Erase always needs to coalesce, so don't check there. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 35 +++++++++++++++++++++++++++++------ 1 file changed, 29 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 343a7996765b..c088620ffad7 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -564,7 +564,12 @@ bool ma_reserved(void *entry) */ void mt_replace(struct ma_state *mas, void *p_entry, bool leaf) { - struct maple_node *mn = mt_to_node(mas->node); + struct maple_node *mn; + + if (mas->node == p_entry) + return; + + mn = mt_to_node(mas->node); mn->parent = mt_to_node(p_entry)->parent; if (!leaf) ma_adopt_children(mn); @@ -579,13 +584,18 @@ void mt_replace(struct ma_state *mas, void *p_entry, bool leaf) RCU_INIT_POINTER(parent->slot[slot], mas->node); } - mt_free(mt_to_node(p_entry)); + mt_free(mt_to_node(p_entry)); } + void *ma_insert(struct ma_state *mas, void *entry) { void *p_entry; // Previous entry. unsigned char slot = MAPLE_NODE_SLOTS; + unsigned long last = mas->max; + struct maple_range_64 *src; + bool coalesce = false; + unsigned char s_slot; bool leaf; @@ -608,17 +618,28 @@ void *ma_insert(struct ma_state *mas, void *entry) leaf = _mas_walk(mas); slot = ma_get_slot(mas); + src = mt_to_node(mas->node); if (leaf == true && slot != MAPLE_NODE_SLOTS) { - if (mt_to_node(mas->node)->slot[slot]) { + if (src->slot[slot]) { mas_set_err(mas, -EEXIST); goto exists; } } p_entry = mas->node; - mas_coalesce(mas); - if (mas_is_err(mas)) - goto error; + for (s_slot = 0; s_slot < MAPLE_RANGE64_SLOTS - 1; s_slot++) { + if (last == src->pivot[s_slot]) { + coalesce = true; + break; + } + last = src->pivot[s_slot]; + } + + if (coalesce) { + mas_coalesce(mas); + if (mas_is_err(mas)) + goto error; + } /* Do the insert */ _ma_insert(mas, entry, slot); @@ -711,6 +732,7 @@ int ma_erase(struct ma_state *mas) mas_coalesce(mas); if (mas_is_err(mas)) goto error; + mt_replace(mas, p_entry, leaf); error: @@ -940,6 +962,7 @@ void mt_dump(const struct maple_tree *mt) else mt_dump_node(entry, 0, mt_max[mt_node_type(entry)], 0); } + void mt_set_non_kernel(unsigned int val) { kmem_cache_set_non_kernel(maple_node_cache, val); -- 2.50.1