From e488c76ab93d502505d110132a2492669f9db693 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 7 Jan 2019 14:45:10 -0500 Subject: [PATCH] maple_tree: Fix potential race condition in _ma_insert The pivots protect readers from reading invalid data. Without a wmb between overwriting the end pivot (of zero), there is a potential that the writes could be reordered and a race condition would exist between updating both values and a reader interleaving those writes. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 28643f8aba5d..de7a6b2657fe 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -9,6 +9,7 @@ #include #include #include +#include #define MA_ROOT_PARENT 1 @@ -323,25 +324,31 @@ static int _ma_insert(struct ma_state *ms, void *entry, unsigned char slot) if (o_end == slot) { // Appending /* zero the new end if the pivot exists. */ if (n_end < MAPLE_RANGE64_SLOTS - 2) - mr64->pivot[n_end+1] = 0; + mr64->pivot[n_end + 1] = 0; } else { while (o_end > slot) { + RCU_INIT_POINTER(mr64->slot[n_end], + mr64->slot[o_end]); if (n_end < MAPLE_RANGE64_SLOTS - 2) mr64->pivot[n_end] = mr64->pivot[o_end]; - RCU_INIT_POINTER(mr64->slot[n_end--], - mr64->slot[o_end--]); + n_end--; + o_end--; } } - /* Set the entry value */ - mr64->pivot[n_end] = ms->last; - RCU_INIT_POINTER(mr64->slot[n_end--], entry); - - /* Create a NULL gap, if necessary */ - if ((ms->index - 1 != mr64->pivot[n_end]) || + RCU_INIT_POINTER(mr64->slot[n_end], entry); + if ((ms->index - 1 != mr64->pivot[n_end - 1]) || (ms->index != ms->last)) { + /* Set the entry value */ + mr64->pivot[n_end--] = ms->last; + /* Create a NULL gap */ RCU_INIT_POINTER(mr64->slot[n_end], NULL); + wmb(); /* slot needs to be written before readers can see. */ mr64->pivot[n_end] = ms->index - 1; + } else { + wmb(); /* slot needs to be written before readers can see. */ + /* Set the entry value */ + mr64->pivot[n_end] = ms->last; } return added; } @@ -591,7 +598,7 @@ exists: void *mas_walk(struct ma_state *ms) { void *entry = mas_start(ms); - unsigned char slot; + unsigned char slot = MAPLE_NODE_SLOTS; /* Outside this nodes range, it doesn't exist. */ if (ms->min > ms->index || -- 2.50.1