From 8322d74ba009d87de0617d1dc6fbd6f1945c4109 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 10 Jan 2019 11:06:23 -0500 Subject: [PATCH] maple_tree: Fix several off-by-one errors. When counting through the slots/pivots, the pivots overflow before the slots which is an area of confusion sometimes. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ca7d4245a890..5fa94bf2aa39 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -323,7 +323,7 @@ unsigned char ma_data_end_r64(const struct ma_state *ms) } /* Private * - * Insert entry into a node. + * Insert entry into a node that is not visible to readers. * * This is done by: * 1. Calculating the range of slot. @@ -357,12 +357,11 @@ static int _ma_insert(struct ma_state *ms, void *entry, unsigned char slot) if (min != ms->index - 1) n_end++; - /* Copy the data over */ while (o_end >= slot) { RCU_INIT_POINTER(mr64->slot[n_end], mr64->slot[o_end]); - if (n_end < MAPLE_RANGE64_SLOTS - 2) + if (n_end < MAPLE_RANGE64_SLOTS - 1) mr64->pivot[n_end] = mr64->pivot[o_end]; n_end--; o_end--; @@ -455,7 +454,7 @@ static void *mas_coalesce(struct ma_state *mas) mn = ma_next_alloc(mas); dst = &mn->mr64; - for (s_slot = 0; s_slot < MAPLE_RANGE64_SLOTS; s_slot++) { + for (s_slot = 0; s_slot < MAPLE_RANGE64_SLOTS - 1; s_slot++) { if (last == src->pivot[s_slot]) continue; @@ -494,7 +493,7 @@ static bool mas_search_slots(struct ma_state *ms, unsigned long val) int i = 0; mr64 = &mt_to_node(ms->node)->mr64; - for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++) { + for (i = 0; i <= MAPLE_RANGE64_SLOTS - 1; i++) { if (i != 0 && mr64->pivot[i] == 0) { ma_set_slot(ms, MAPLE_NODE_SLOTS); return false; @@ -505,7 +504,7 @@ static bool mas_search_slots(struct ma_state *ms, unsigned long val) } if (i == MAPLE_RANGE64_SLOTS - 2) { - if (val <= mr64->pivot[i]) + if (val > mr64->pivot[i]) i++; } @@ -781,6 +780,8 @@ EXPORT_SYMBOL(mtree_destroy); #ifdef MT_DEBUG +void mt_dump_node(void *entry, unsigned long min, unsigned long max, + unsigned int depth); void mt_dump_range(unsigned long min, unsigned long max) { if (min == max) -- 2.50.1