Some clean ups, mainly to make the code of maple tree more concise.
This patchset has passed the self-test.
0006-0009 - Make mas_wr_modify() and its subfunctions clearer. Make the
store operation of maple tree more efficient in some cases.
Thanks Liam and Matthew.
Changes since v1:
- Rework mtree_alloc_{range,rrange}() instead of removing it. [01/10]
- Fix the arguments to __must_hold() instead of removing it. [03/10]
- Keep the fast path. Expand the compact code. [04/10]
- Drop "maple_tree: Wrap the replace operation with an inline
function.". [v1 06/10]
- Remove some comments. [07/10] [08/10]
- Avoid modifying wr_mas->offset_end in mas_wr_modify(). [09/10]
- Add a patch to relocate mas_empty_area_rev(). [10/10]
Peng Zhang (10):
maple_tree: Rework mtree_alloc_{range,rrange}()
maple_tree: Drop mas_{rev_}alloc() and mas_fill_gap()
maple_tree: Fix the arguments to __must_hold()
maple_tree: Simplify mas_is_span_wr()
maple_tree: Make the code symmetrical in mas_wr_extend_null()
maple_tree: Add mas_wr_new_end() to calculate new_end accurately
maple_tree: Add comments and some minor cleanups to mas_wr_append()
maple_tree: Rework mas_wr_slot_store() to be cleaner and more
efficient.
maple_tree: Simplify and clean up mas_wr_node_store()
maple_tree: Relocate the declaration of mas_empty_area_rev().
include/linux/maple_tree.h | 12 +-
lib/maple_tree.c | 455 +++++++++++++------------------------
2 files changed, 160 insertions(+), 307 deletions(-)
--
2.20.1
Just make the code symmetrical to improve readability.
Signed-off-by: Peng Zhang <[email protected]>
Reviewed-by: Liam R. Howlett <[email protected]>
---
lib/maple_tree.c | 26 ++++++++++++++------------
1 file changed, 14 insertions(+), 12 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 82dccc660889..f881bce1a9f6 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4262,19 +4262,21 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
{
struct ma_state *mas = wr_mas->mas;
- if (mas->last < wr_mas->end_piv && !wr_mas->slots[wr_mas->offset_end])
+ if (!wr_mas->slots[wr_mas->offset_end]) {
+ /* If this one is null, the next and prev are not */
mas->last = wr_mas->end_piv;
-
- /* Check next slot(s) if we are overwriting the end */
- if ((mas->last == wr_mas->end_piv) &&
- (wr_mas->node_end != wr_mas->offset_end) &&
- !wr_mas->slots[wr_mas->offset_end + 1]) {
- wr_mas->offset_end++;
- if (wr_mas->offset_end == wr_mas->node_end)
- mas->last = mas->max;
- else
- mas->last = wr_mas->pivots[wr_mas->offset_end];
- wr_mas->end_piv = mas->last;
+ } else {
+ /* Check next slot(s) if we are overwriting the end */
+ if ((mas->last == wr_mas->end_piv) &&
+ (wr_mas->node_end != wr_mas->offset_end) &&
+ !wr_mas->slots[wr_mas->offset_end + 1]) {
+ wr_mas->offset_end++;
+ if (wr_mas->offset_end == wr_mas->node_end)
+ mas->last = mas->max;
+ else
+ mas->last = wr_mas->pivots[wr_mas->offset_end];
+ wr_mas->end_piv = mas->last;
+ }
}
if (!wr_mas->content) {
--
2.20.1
Fix the arguments to __must_hold() to make sparse work.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index c8176f360dc2..bec9906b0c8c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1752,7 +1752,7 @@ static inline void mas_adopt_children(struct ma_state *mas,
* leave the node (true) and handle the adoption and free elsewhere.
*/
static inline void mas_replace(struct ma_state *mas, bool advanced)
- __must_hold(mas->tree->lock)
+ __must_hold(mas->tree->ma_lock)
{
struct maple_node *mn = mas_mn(mas);
struct maple_enode *old_enode;
@@ -1792,7 +1792,7 @@ static inline void mas_replace(struct ma_state *mas, bool advanced)
* @child: the maple state to store the child.
*/
static inline bool mas_new_child(struct ma_state *mas, struct ma_state *child)
- __must_hold(mas->tree->lock)
+ __must_hold(mas->tree->ma_lock)
{
enum maple_type mt;
unsigned char offset;
@@ -6204,7 +6204,7 @@ EXPORT_SYMBOL_GPL(mas_erase);
* Return: true on allocation, false otherwise.
*/
bool mas_nomem(struct ma_state *mas, gfp_t gfp)
- __must_hold(mas->tree->lock)
+ __must_hold(mas->tree->ma_lock)
{
if (likely(mas->node != MA_ERROR(-ENOMEM))) {
mas_destroy(mas);
--
2.20.1
Add comment for mas_wr_append(), move mas_update_gap() into
mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 33 ++++++++++++++++++++-------------
1 file changed, 20 insertions(+), 13 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3b9d227f3d7d..bbe4c6f2858c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4308,6 +4308,12 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
return new_end;
}
+/*
+ * mas_wr_append: Attempt to append
+ * @wr_mas: the maple write state
+ *
+ * Return: True if appended, false otherwise
+ */
static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
{
unsigned char end = wr_mas->node_end;
@@ -4315,7 +4321,11 @@ 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 (!(mas->offset == wr_mas->node_end))
+ return false;
+
if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) {
+ /* Append to end of range */
if (new_end < node_pivots)
wr_mas->pivots[new_end] = wr_mas->pivots[end];
@@ -4323,13 +4333,10 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
- mas->offset = new_end;
wr_mas->pivots[end] = mas->index - 1;
-
- return true;
- }
-
- if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
+ mas->offset = new_end;
+ } else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
+ /* Append to start of range */
if (new_end < node_pivots)
wr_mas->pivots[new_end] = wr_mas->pivots[end];
@@ -4339,10 +4346,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
wr_mas->pivots[end] = mas->last;
rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
- return true;
+ } else {
+ return false;
}
- return false;
+ if (!wr_mas->content || !wr_mas->entry)
+ mas_update_gap(mas);
+ return true;
}
/*
@@ -4382,12 +4392,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
if (new_end >= mt_slots[wr_mas->type])
goto slow_path;
- if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
- (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
- if (!wr_mas->content || !wr_mas->entry)
- mas_update_gap(mas);
+ /* Attempt to append */
+ if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
return;
- }
if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
return;
--
2.20.1
Simplify and clean up mas_wr_node_store(), remove unnecessary code.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 87 +++++++++++++++---------------------------------
1 file changed, 26 insertions(+), 61 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 25a8b7d5d598..b86001ad4632 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -4072,52 +4072,27 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
*
* Return: True if stored, false otherwise
*/
-static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
+static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
+ unsigned char new_end)
{
struct ma_state *mas = wr_mas->mas;
void __rcu **dst_slots;
unsigned long *dst_pivots;
- unsigned char dst_offset;
- unsigned char new_end = wr_mas->node_end;
- unsigned char offset;
- unsigned char node_slots = mt_slots[wr_mas->type];
+ unsigned char dst_offset, offset_end = wr_mas->offset_end;
struct maple_node reuse, *newnode;
- unsigned char copy_size, max_piv = mt_pivots[wr_mas->type];
+ unsigned char copy_size, node_pivots = mt_pivots[wr_mas->type];
bool in_rcu = mt_in_rcu(mas->tree);
- offset = mas->offset;
- if (mas->last == wr_mas->r_max) {
- /* runs right to the end of the node */
- if (mas->last == mas->max)
- new_end = offset;
- /* don't copy this offset */
- wr_mas->offset_end++;
- } else if (mas->last < wr_mas->r_max) {
- /* new range ends in this range */
- if (unlikely(wr_mas->r_max == ULONG_MAX))
- mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
-
- new_end++;
- } else {
- if (wr_mas->end_piv == mas->last)
- wr_mas->offset_end++;
-
- new_end -= wr_mas->offset_end - offset - 1;
- }
-
- /* new range starts within a range */
- if (wr_mas->r_min < mas->index)
- new_end++;
-
- /* Not enough room */
- if (new_end >= node_slots)
- return false;
-
- /* Not enough data. */
+ /* Check if there is enough data. The room is enough. */
if (!mte_is_root(mas->node) && (new_end <= mt_min_slots[wr_mas->type]) &&
!(mas->mas_flags & MA_STATE_BULK))
return false;
+ if (mas->last == wr_mas->end_piv)
+ offset_end++; /* don't copy this offset */
+ else if (unlikely(wr_mas->r_max == ULONG_MAX))
+ mas_bulk_rebalance(mas, wr_mas->node_end, wr_mas->type);
+
/* set up node. */
if (in_rcu) {
mas_node_count(mas, 1);
@@ -4134,47 +4109,36 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas)
dst_pivots = ma_pivots(newnode, wr_mas->type);
dst_slots = ma_slots(newnode, wr_mas->type);
/* Copy from start to insert point */
- memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * (offset + 1));
- memcpy(dst_slots, wr_mas->slots, sizeof(void *) * (offset + 1));
- dst_offset = offset;
+ memcpy(dst_pivots, wr_mas->pivots, sizeof(unsigned long) * mas->offset);
+ memcpy(dst_slots, wr_mas->slots, sizeof(void *) * mas->offset);
/* Handle insert of new range starting after old range */
if (wr_mas->r_min < mas->index) {
- mas->offset++;
- rcu_assign_pointer(dst_slots[dst_offset], wr_mas->content);
- dst_pivots[dst_offset++] = mas->index - 1;
+ rcu_assign_pointer(dst_slots[mas->offset], wr_mas->content);
+ dst_pivots[mas->offset++] = mas->index - 1;
}
/* Store the new entry and range end. */
- if (dst_offset < max_piv)
- dst_pivots[dst_offset] = mas->last;
- mas->offset = dst_offset;
- rcu_assign_pointer(dst_slots[dst_offset], wr_mas->entry);
+ if (mas->offset < node_pivots)
+ dst_pivots[mas->offset] = mas->last;
+ rcu_assign_pointer(dst_slots[mas->offset], wr_mas->entry);
/*
* this range wrote to the end of the node or it overwrote the rest of
* the data
*/
- if (wr_mas->offset_end > wr_mas->node_end || mas->last >= mas->max) {
- new_end = dst_offset;
+ if (offset_end > wr_mas->node_end)
goto done;
- }
- dst_offset++;
+ dst_offset = mas->offset + 1;
/* Copy to the end of node if necessary. */
- copy_size = wr_mas->node_end - wr_mas->offset_end + 1;
- memcpy(dst_slots + dst_offset, wr_mas->slots + wr_mas->offset_end,
+ copy_size = wr_mas->node_end - offset_end + 1;
+ memcpy(dst_slots + dst_offset, wr_mas->slots + offset_end,
sizeof(void *) * copy_size);
- if (dst_offset < max_piv) {
- if (copy_size > max_piv - dst_offset)
- copy_size = max_piv - dst_offset;
-
- memcpy(dst_pivots + dst_offset,
- wr_mas->pivots + wr_mas->offset_end,
- sizeof(unsigned long) * copy_size);
- }
+ memcpy(dst_pivots + dst_offset, wr_mas->pivots + offset_end,
+ sizeof(unsigned long) * (copy_size - 1));
- if ((wr_mas->node_end == node_slots - 1) && (new_end < node_slots - 1))
+ if (new_end < node_pivots)
dst_pivots[new_end] = mas->max;
done:
@@ -4387,7 +4351,8 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
if (new_end == wr_mas->node_end && mas_wr_slot_store(wr_mas))
return;
- else if (mas_wr_node_store(wr_mas))
+
+ if (mas_wr_node_store(wr_mas, new_end))
return;
if (mas_is_err(mas))
--
2.20.1
* Peng Zhang <[email protected]> [230517 04:59]:
> Add comment for mas_wr_append(), move mas_update_gap() into
> mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner.
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> lib/maple_tree.c | 33 ++++++++++++++++++++-------------
> 1 file changed, 20 insertions(+), 13 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 3b9d227f3d7d..bbe4c6f2858c 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -4308,6 +4308,12 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
> return new_end;
> }
>
> +/*
> + * mas_wr_append: Attempt to append
> + * @wr_mas: the maple write state
> + *
> + * Return: True if appended, false otherwise
> + */
> static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
> {
> unsigned char end = wr_mas->node_end;
> @@ -4315,7 +4321,11 @@ 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 (!(mas->offset == wr_mas->node_end))
> + return false;
> +
> if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) {
> + /* Append to end of range */
> if (new_end < node_pivots)
> wr_mas->pivots[new_end] = wr_mas->pivots[end];
>
> @@ -4323,13 +4333,10 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
> ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
>
> rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
> - mas->offset = new_end;
> wr_mas->pivots[end] = mas->index - 1;
> -
> - return true;
> - }
> -
> - if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
> + mas->offset = new_end;
> + } else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
> + /* Append to start of range */
> if (new_end < node_pivots)
> wr_mas->pivots[new_end] = wr_mas->pivots[end];
>
> @@ -4339,10 +4346,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>
> wr_mas->pivots[end] = mas->last;
> rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
> - return true;
> + } else {
> + return false;
I don't think we can get here with your changes, what do you think? If
so, we can move the metadata setting to the outside of the if/else. I
checked by adding a BUG_ON() and the test code never gets here.
My thinking is, we know offset == node_end and new_end == node_end + 1..
so we must be inserting into the last slot and only adding one entry.
> }
>
> - return false;
> + if (!wr_mas->content || !wr_mas->entry)
> + mas_update_gap(mas);
> + return true;
> }
>
> /*
> @@ -4382,12 +4392,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
> if (new_end >= mt_slots[wr_mas->type])
> goto slow_path;
>
> - if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
> - (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
> - if (!wr_mas->content || !wr_mas->entry)
> - mas_update_gap(mas);
> + /* Attempt to append */
> + if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
> return;
> - }
>
> if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
> return;
> --
> 2.20.1
>
在 2023/5/18 03:33, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230517 04:59]:
>> Add comment for mas_wr_append(), move mas_update_gap() into
>> mas_wr_append(), and other cleanups to make mas_wr_modify() cleaner.
>>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> lib/maple_tree.c | 33 ++++++++++++++++++++-------------
>> 1 file changed, 20 insertions(+), 13 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 3b9d227f3d7d..bbe4c6f2858c 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -4308,6 +4308,12 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
>> return new_end;
>> }
>>
>> +/*
>> + * mas_wr_append: Attempt to append
>> + * @wr_mas: the maple write state
>> + *
>> + * Return: True if appended, false otherwise
>> + */
>> static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>> {
>> unsigned char end = wr_mas->node_end;
>> @@ -4315,7 +4321,11 @@ 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 (!(mas->offset == wr_mas->node_end))
>> + return false;
>> +
>> if ((mas->index != wr_mas->r_min) && (mas->last == wr_mas->r_max)) {
>> + /* Append to end of range */
>> if (new_end < node_pivots)
>> wr_mas->pivots[new_end] = wr_mas->pivots[end];
>>
>> @@ -4323,13 +4333,10 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>> ma_set_meta(wr_mas->node, maple_leaf_64, 0, new_end);
>>
>> rcu_assign_pointer(wr_mas->slots[new_end], wr_mas->entry);
>> - mas->offset = new_end;
>> wr_mas->pivots[end] = mas->index - 1;
>> -
>> - return true;
>> - }
>> -
>> - if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
>> + mas->offset = new_end;
>> + } else if ((mas->index == wr_mas->r_min) && (mas->last < wr_mas->r_max)) {
>> + /* Append to start of range */
>> if (new_end < node_pivots)
>> wr_mas->pivots[new_end] = wr_mas->pivots[end];
>>
>> @@ -4339,10 +4346,13 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas)
>>
>> wr_mas->pivots[end] = mas->last;
>> rcu_assign_pointer(wr_mas->slots[end], wr_mas->entry);
>> - return true;
>> + } else {
>> + return false;
>
> I don't think we can get here with your changes, what do you think? If
> so, we can move the metadata setting to the outside of the if/else. I
> checked by adding a BUG_ON() and the test code never gets here.
>
> My thinking is, we know offset == node_end and new_end == node_end + 1..
> so we must be inserting into the last slot and only adding one entry.
Yes, I'll address this in v3. Thanks.
>
>> }
>>
>> - return false;
>> + if (!wr_mas->content || !wr_mas->entry)
>> + mas_update_gap(mas);
>> + return true;
>> }
>>
>> /*
>> @@ -4382,12 +4392,9 @@ static inline void mas_wr_modify(struct ma_wr_state *wr_mas)
>> if (new_end >= mt_slots[wr_mas->type])
>> goto slow_path;
>>
>> - if (wr_mas->entry && (wr_mas->node_end < mt_slots[wr_mas->type] - 1) &&
>> - (mas->offset == wr_mas->node_end) && mas_wr_append(wr_mas)) {
>> - if (!wr_mas->content || !wr_mas->entry)
>> - mas_update_gap(mas);
>> + /* Attempt to append */
>> + if (new_end == wr_mas->node_end + 1 && mas_wr_append(wr_mas))
>> return;
>> - }
>>
>> if ((wr_mas->offset_end - mas->offset <= 1) && mas_wr_slot_store(wr_mas))
>> return;
>> --
>> 2.20.1
>>