* [PATCH 2/2] maple_tree: Clean up mas_wr_append()
2023-08-17 19:15 [PATCH 1/2] maple_tree: Disable mas_wr_append() when other readers are possible Liam R. Howlett
@ 2023-08-17 19:15 ` Liam R. Howlett
2023-08-17 23:56 ` [PATCH 1/2] maple_tree: Disable mas_wr_append() when other readers are possible Liam R. Howlett
1 sibling, 0 replies; 3+ messages in thread
From: Liam R. Howlett @ 2023-08-17 19:15 UTC (permalink / raw)
To: Andrew Morton; +Cc: maple-tree, linux-mm, linux-kernel, Liam R. Howlett
Avoid setting the variables until necessary, and actually use the
variables where applicable. Introducing a variable for the slots array
avoids spanning multiple lines.
Add the missing argument to the documentation.
Use the node type when setting the metadata instead of blindly assuming
the type.
Finally, add a trace point to the function for successful store.
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
lib/maple_tree.c | 34 ++++++++++++++++++++--------------
1 file changed, 20 insertions(+), 14 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 05d5db255c39..ee1ff0c59fd7 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4106,6 +4106,7 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
/*
* mas_wr_append: Attempt to append
* @wr_mas: the maple write state
+ * @new_end: The end of the node after the modification
*
* This is currently unsafe in rcu mode since the end of the node may be cached
* by readers while the node contents may be updated which could result in
@@ -4114,42 +4115,46 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
* Return: True if appended, false otherwise
*/
static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
- unsigned char new_end)
+ unsigned char new_end)
{
- unsigned char end = wr_mas->node_end;
- struct ma_state *mas = wr_mas->mas;
- unsigned char node_pivots = mt_pivots[wr_mas->type];
+ struct ma_state *mas;
+ void __rcu **slots;
+ unsigned char end;
+ mas = wr_mas->mas;
if (mt_in_rcu(mas->tree))
return false;
if (mas->offset != wr_mas->node_end)
return false;
- if (new_end < node_pivots) {
+ end = wr_mas->node_end;
+ if (mas->offset != end)
+ return false;
+
+ if (new_end < mt_pivots[wr_mas->type]) {
wr_mas->pivots[new_end] = wr_mas->pivots[end];
- ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
+ ma_set_meta(wr_mas->node, wr_mas->type, 0, new_end);
}
- if (new_end == wr_mas->node_end + 1) {
+ slots = wr_mas->slots;
+ if (new_end == end + 1) {
if (mas->last == wr_mas->r_max) {
/* Append to end of range */
- rcu_assign_pointer(wr_mas->slots[new_end],
- wr_mas->entry);
+ rcu_assign_pointer(slots[new_end], wr_mas->entry);
wr_mas->pivots[end] = mas->index - 1;
mas->offset = new_end;
} else {
/* Append to start of range */
- rcu_assign_pointer(wr_mas->slots[new_end],
- wr_mas->content);
+ rcu_assign_pointer(slots[new_end], wr_mas->content);
wr_mas->pivots[end] = mas->last;
- rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
+ rcu_assign_pointer(slots[end], wr_mas->entry);
}
} else {
/* Append to the range without touching any boundaries. */
- rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->content);
+ rcu_assign_pointer(slots[new_end], wr_mas->content);
wr_mas->pivots[end + 1] = mas->last;
- rcu_assign_pointer(wr_mas->slots[end + 1], wr_mas->entry);
+ rcu_assign_pointer(slots[end + 1], wr_mas->entry);
wr_mas->pivots[end] = mas->index - 1;
mas->offset = end + 1;
}
@@ -4157,6 +4162,7 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
if (!wr_mas->content || !wr_mas->entry)
mas_update_gap(mas);
+ trace_ma_write(__func__, mas, new_end, wr_mas->entry);
return true;
}
--
2.39.2
^ permalink raw reply [flat|nested] 3+ messages in thread* Re: [PATCH 1/2] maple_tree: Disable mas_wr_append() when other readers are possible
2023-08-17 19:15 [PATCH 1/2] maple_tree: Disable mas_wr_append() when other readers are possible Liam R. Howlett
2023-08-17 19:15 ` [PATCH 2/2] maple_tree: Clean up mas_wr_append() Liam R. Howlett
@ 2023-08-17 23:56 ` Liam R. Howlett
1 sibling, 0 replies; 3+ messages in thread
From: Liam R. Howlett @ 2023-08-17 23:56 UTC (permalink / raw)
To: Andrew Morton; +Cc: maple-tree, linux-mm, linux-kernel, stable
I forgot the fixes tag, I will include that in v2.
* Liam R. Howlett <Liam.Howlett@oracle.com> [230817 15:15]:
> The current implementation of append may cause duplicate data and/or
> incorrect ranges to be returned to a reader during an update. Although
> this has not been reported or seen, disable the append write operation
> while the tree is in rcu mode out of an abundance of caution.
>
> During the analysis of the mas_next_slot() the following was
> artificially created by separating the writer and reader code:
>
> Writer: reader:
> mas_wr_append
> set end pivot
> updates end metata
> Detects write to last slot
> last slot write is to start of slot
> store current contents in slot
> overwrite old end pivot
> mas_next_slot():
> read end metadata
> read old end pivot
> return with incorrect range
> store new value
>
> Alternatively:
>
> Writer: reader:
> mas_wr_append
> set end pivot
> updates end metata
> Detects write to last slot
> last lost write to end of slot
> store value
> mas_next_slot():
> read end metadata
> read old end pivot
> read new end pivot
> return with incorrect range
> set old end pivot
>
> There may be other accesses that are not safe since we are now updating
> both metadata and pointers, so disabling append if there could be rcu
> readers is the safest action.
>
> Cc: stable@vger.kernel.org
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> ---
> lib/maple_tree.c | 7 +++++++
> 1 file changed, 7 insertions(+)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index ffb9d15bd815..05d5db255c39 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4107,6 +4107,10 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
> * mas_wr_append: Attempt to append
> * @wr_mas: the maple write state
> *
> + * This is currently unsafe in rcu mode since the end of the node may be cached
> + * by readers while the node contents may be updated which could result in
> + * inaccurate information.
> + *
> * Return: True if appended, false otherwise
> */
> static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
> @@ -4116,6 +4120,9 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
> struct ma_state *mas = wr_mas->mas;
> unsigned char node_pivots = mt_pivots[wr_mas->type];
>
> + if (mt_in_rcu(mas->tree))
> + return false;
> +
> if (mas->offset != wr_mas->node_end)
> return false;
>
> --
> 2.39.2
>
^ permalink raw reply [flat|nested] 3+ messages in thread