[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <20241024132009.2267260-10-yukuai1@huaweicloud.com>
Date: Thu, 24 Oct 2024 21:19:50 +0800
From: Yu Kuai <yukuai1@...weicloud.com>
To: stable@...r.kernel.org,
gregkh@...uxfoundation.org,
harry.wentland@....com,
sunpeng.li@....com,
Rodrigo.Siqueira@....com,
alexander.deucher@....com,
christian.koenig@....com,
Xinhui.Pan@....com,
airlied@...il.com,
daniel@...ll.ch,
viro@...iv.linux.org.uk,
brauner@...nel.org,
Liam.Howlett@...cle.com,
akpm@...ux-foundation.org,
hughd@...gle.com,
willy@...radead.org,
sashal@...nel.org,
srinivasan.shanmugam@....com,
chiahsuan.chung@....com,
mingo@...nel.org,
mgorman@...hsingularity.net,
yukuai3@...wei.com,
chengming.zhou@...ux.dev,
zhangpeng.00@...edance.com,
chuck.lever@...cle.com
Cc: amd-gfx@...ts.freedesktop.org,
dri-devel@...ts.freedesktop.org,
linux-kernel@...r.kernel.org,
linux-fsdevel@...r.kernel.org,
maple-tree@...ts.infradead.org,
linux-mm@...ck.org,
yukuai1@...weicloud.com,
yi.zhang@...wei.com,
yangerkun@...wei.com
Subject: [PATCH 6.6 09/28] maple_tree: add end of node tracking to the maple state
From: "Liam R. Howlett" <Liam.Howlett@...cle.com>
commit 31c532a8af57513228c2b12d281104198ff412b8 upstream.
Analysis of the mas_for_each() iteration showed that there is a
significant time spent finding the end of a node. This time can be
greatly reduced if the end of the node is cached in the maple state. Care
must be taken to update & invalidate as necessary.
Link: https://lkml.kernel.org/r/20231101171629.3612299-5-Liam.Howlett@oracle.com
Signed-off-by: Liam R. Howlett <Liam.Howlett@...cle.com>
Cc: Peng Zhang <zhangpeng.00@...edance.com>
Signed-off-by: Andrew Morton <akpm@...ux-foundation.org>
Signed-off-by: Yu Kuai <yukuai3@...wei.com>
---
include/linux/maple_tree.h | 1 +
lib/maple_tree.c | 7 +++++++
tools/testing/radix-tree/maple.c | 1 +
3 files changed, 9 insertions(+)
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index b5d5992578c9..0b82efe0cf1e 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -393,6 +393,7 @@ struct ma_state {
unsigned char depth; /* depth of tree descent during write */
unsigned char offset;
unsigned char mas_flags;
+ unsigned char end; /* The end of the node */
};
struct ma_wr_state {
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index e4d0df3980e0..d19fb14a9635 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -2843,6 +2843,7 @@ static inline void *mtree_range_walk(struct ma_state *mas)
goto dead_node;
} while (!ma_is_leaf(type));
+ mas->end = end;
mas->offset = offset;
mas->index = min;
mas->last = max;
@@ -3509,6 +3510,7 @@ static noinline_for_kasan int mas_commit_b_node(struct ma_wr_state *wr_mas,
mas_replace_node(wr_mas->mas, old_enode);
reuse_node:
mas_update_gap(wr_mas->mas);
+ wr_mas->mas->end = b_end;
return 1;
}
@@ -4010,6 +4012,7 @@ static inline bool mas_wr_node_store(struct ma_wr_state *wr_mas,
}
trace_ma_write(__func__, mas, 0, wr_mas->entry);
mas_update_gap(mas);
+ mas->end = new_end;
return true;
}
@@ -4190,6 +4193,7 @@ static inline bool mas_wr_append(struct ma_wr_state *wr_mas,
if (!wr_mas->content || !wr_mas->entry)
mas_update_gap(mas);
+ mas->end = new_end;
trace_ma_write(__func__, mas, new_end, wr_mas->entry);
return true;
}
@@ -4428,6 +4432,7 @@ static inline int mas_prev_node(struct ma_state *mas, unsigned long min)
if (unlikely(mte_dead_node(mas->node)))
return 1;
+ mas->end = mas->offset;
return 0;
no_entry:
@@ -5074,6 +5079,7 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
if (mas->index < min)
mas->index = min;
mas->last = mas->index + size - 1;
+ mas->end = mas_data_end(mas);
return 0;
}
EXPORT_SYMBOL_GPL(mas_empty_area);
@@ -5134,6 +5140,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
mas->last = max;
mas->index = mas->last - size + 1;
+ mas->end = mas_data_end(mas);
return 0;
}
EXPORT_SYMBOL_GPL(mas_empty_area_rev);
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 576b825d6bb1..27a3a31ba662 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -945,6 +945,7 @@ static inline bool mas_tree_walk(struct ma_state *mas, unsigned long *range_min,
goto retry;
}
+ mas->end = mas_data_end(mas);
return ret;
not_found:
--
2.39.2
Powered by blists - more mailing lists