Hi all,
This series introduces __mt_dup() to improve the performance of fork(). During
the duplication process of mmap, all VMAs are traversed and inserted one by one
into the new maple tree, causing the maple tree to be rebalanced multiple times.
Balancing the maple tree is a costly operation. To duplicate VMAs more
efficiently, mtree_dup() and __mt_dup() are introduced for the maple tree. They
can efficiently duplicate a maple tree. By applying __mt_dup() to dup_mmap(),
better performance is achieved compared to the original method. After using this
method, the average time complexity decreases from O(n * log(n)) to O(n).
Here are some algorithmic details about {mtree, __mt}_dup(). We perform a DFS
pre-order traversal of all nodes in the source maple tree. During this process,
we fully copy the nodes from the source tree to the new tree. This involves
memory allocation, and when encountering a new node, if it is a non-leaf node,
all its child nodes are allocated at once.
Some previous discussions can be referred to as [1].
There is a "spawn" in byte-unixbench[2], which can be used to test the
performance of fork(). I modified it slightly to make it work with
different number of VMAs.
Below are the test results. By default, there are 21 VMAs. The first row
shows the number of additional VMAs added on top of the default. The last
two rows show the number of fork() calls per ten seconds. The test results
were obtained with CPU binding to avoid scheduler load balancing that
could cause unstable results. There are still some fluctuations in the
test results, but at least they are better than the original performance.
Increment of VMAs: 0 100 200 400 800 1600 3200 6400
next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
+3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
Thanks to kernel test robot <[email protected]> for reporting the warning
about nested locks.
Thanks to Liam for all the suggestions.
Changes since v2:
- Some minor modifications to mtree_dup(), __mt_dup() and their test code.
- Introduce {mtree, mas}_lock_nested() to address lockdep warnings.
- Update the documentation for maple tree.
- Introduce undo_dup_mmap() to address the failure of dup_mmap().
- Performance data was retested based on the latest next-20230921, and there
were some fluctuations in the results which were expected.
[1] https://lore.kernel.org/lkml/[email protected]/
[2] https://github.com/kdlucas/byte-unixbench/tree/master
v1: https://lore.kernel.org/lkml/[email protected]/
v2: https://lore.kernel.org/lkml/[email protected]/
Peng Zhang (9):
maple_tree: Add mt_free_one() and mt_attr() helpers
maple_tree: Introduce {mtree,mas}_lock_nested()
maple_tree: Introduce interfaces __mt_dup() and mtree_dup()
maple_tree: Add test for mtree_dup()
maple_tree: Update the documentation of maple tree
maple_tree: Skip other tests when BENCH is enabled
maple_tree: Update check_forking() and bench_forking()
maple_tree: Preserve the tree attributes when destroying maple tree
fork: Use __mt_dup() to duplicate maple tree in dup_mmap()
Documentation/core-api/maple_tree.rst | 4 +
include/linux/maple_tree.h | 7 +
include/linux/mm.h | 1 +
kernel/fork.c | 34 ++-
lib/maple_tree.c | 300 ++++++++++++++++++++-
lib/test_maple_tree.c | 69 +++--
mm/internal.h | 3 +-
mm/memory.c | 7 +-
mm/mmap.c | 52 +++-
tools/include/linux/spinlock.h | 1 +
tools/testing/radix-tree/maple.c | 363 ++++++++++++++++++++++++++
11 files changed, 787 insertions(+), 54 deletions(-)
--
2.20.1
When destroying maple tree, preserve its attributes and then turn it
into an empty tree. This allows it to be reused without needing to be
reinitialized.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index ed8847b4f1ff..ad06105f1a54 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6670,7 +6670,7 @@ void __mt_destroy(struct maple_tree *mt)
if (xa_is_node(root))
mte_destroy_walk(root, mt);
- mt->ma_flags = 0;
+ mt->ma_flags = mt_attr(mt);
}
EXPORT_SYMBOL_GPL(__mt_destroy);
--
2.20.1
In some cases, nested locks may be needed, so {mtree,mas}_lock_nested is
introduced. For example, when duplicating maple tree, we need to hold
the locks of two trees, in which case nested locks are needed.
At the same time, add the definition of spin_lock_nested() in tools for
testing.
Signed-off-by: Peng Zhang <[email protected]>
---
include/linux/maple_tree.h | 4 ++++
tools/include/linux/spinlock.h | 1 +
2 files changed, 5 insertions(+)
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index e41c70ac7744..666a3764ed89 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -256,6 +256,8 @@ struct maple_tree {
struct maple_tree name = MTREE_INIT(name, 0)
#define mtree_lock(mt) spin_lock((&(mt)->ma_lock))
+#define mtree_lock_nested(mas, subclass) \
+ spin_lock_nested((&(mt)->ma_lock), subclass)
#define mtree_unlock(mt) spin_unlock((&(mt)->ma_lock))
/*
@@ -406,6 +408,8 @@ struct ma_wr_state {
};
#define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock))
+#define mas_lock_nested(mas, subclass) \
+ spin_lock_nested(&((mas)->tree->ma_lock), subclass)
#define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock))
diff --git a/tools/include/linux/spinlock.h b/tools/include/linux/spinlock.h
index 622266b197d0..a6cdf25b6b9d 100644
--- a/tools/include/linux/spinlock.h
+++ b/tools/include/linux/spinlock.h
@@ -11,6 +11,7 @@
#define spin_lock_init(x) pthread_mutex_init(x, NULL)
#define spin_lock(x) pthread_mutex_lock(x)
+#define spin_lock_nested(x, subclass) pthread_mutex_lock(x)
#define spin_unlock(x) pthread_mutex_unlock(x)
#define spin_lock_bh(x) pthread_mutex_lock(x)
#define spin_unlock_bh(x) pthread_mutex_unlock(x)
--
2.20.1
Introduce the new interface mtree_dup() in the documentation.
Signed-off-by: Peng Zhang <[email protected]>
---
Documentation/core-api/maple_tree.rst | 4 ++++
1 file changed, 4 insertions(+)
diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
index 45defcf15da7..3d8a1edf6d04 100644
--- a/Documentation/core-api/maple_tree.rst
+++ b/Documentation/core-api/maple_tree.rst
@@ -81,6 +81,9 @@ section.
Sometimes it is necessary to ensure the next call to store to a maple tree does
not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case.
+You can use mtree_dup() to duplicate an identical tree. It is a more efficient
+way than inserting all elements one by one into a new tree.
+
Finally, you can remove all entries from a maple tree by calling
mtree_destroy(). If the maple tree entries are pointers, you may wish to free
the entries first.
@@ -112,6 +115,7 @@ Takes ma_lock internally:
* mtree_insert()
* mtree_insert_range()
* mtree_erase()
+ * mtree_dup()
* mtree_destroy()
* mt_set_in_rcu()
* mt_clear_in_rcu()
--
2.20.1
Introduce interfaces __mt_dup() and mtree_dup(), which are used to
duplicate a maple tree. They duplicate a maple tree in Depth-First
Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the
source tree and allocate new child nodes in non-leaf nodes. The new node
is exactly the same as the source node except for all the addresses
stored in it. It will be faster than traversing all elements in the
source tree and inserting them one by one into the new tree. The time
complexity of these two functions is O(n).
The difference between __mt_dup() and mtree_dup() is that mtree_dup()
handles locks internally.
Signed-off-by: Peng Zhang <[email protected]>
---
include/linux/maple_tree.h | 3 +
lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++
2 files changed, 289 insertions(+)
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 666a3764ed89..de5a4056503a 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index,
void *entry, gfp_t gfp);
void *mtree_erase(struct maple_tree *mt, unsigned long index);
+int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
+int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
+
void mtree_destroy(struct maple_tree *mt);
void __mt_destroy(struct maple_tree *mt);
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 3fe5652a8c6c..ed8847b4f1ff 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6370,6 +6370,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
}
EXPORT_SYMBOL(mtree_erase);
+/*
+ * mas_dup_free() - Free an incomplete duplication of a tree.
+ * @mas: The maple state of a incomplete tree.
+ *
+ * The parameter @mas->node passed in indicates that the allocation failed on
+ * this node. This function frees all nodes starting from @mas->node in the
+ * reverse order of mas_dup_build(). There is no need to hold the source tree
+ * lock at this time.
+ */
+static void mas_dup_free(struct ma_state *mas)
+{
+ struct maple_node *node;
+ enum maple_type type;
+ void __rcu **slots;
+ unsigned char count, i;
+
+ /* Maybe the first node allocation failed. */
+ if (mas_is_none(mas))
+ return;
+
+ while (!mte_is_root(mas->node)) {
+ mas_ascend(mas);
+
+ if (mas->offset) {
+ mas->offset--;
+ do {
+ mas_descend(mas);
+ mas->offset = mas_data_end(mas);
+ } while (!mte_is_leaf(mas->node));
+
+ mas_ascend(mas);
+ }
+
+ node = mte_to_node(mas->node);
+ type = mte_node_type(mas->node);
+ slots = ma_slots(node, type);
+ count = mas_data_end(mas) + 1;
+ for (i = 0; i < count; i++)
+ ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK;
+
+ mt_free_bulk(count, slots);
+ }
+
+ node = mte_to_node(mas->node);
+ mt_free_one(node);
+}
+
+/*
+ * mas_copy_node() - Copy a maple node and replace the parent.
+ * @mas: The maple state of source tree.
+ * @new_mas: The maple state of new tree.
+ * @parent: The parent of the new node.
+ *
+ * Copy @mas->node to @new_mas->node, set @parent to be the parent of
+ * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM.
+ */
+static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas,
+ struct maple_pnode *parent)
+{
+ struct maple_node *node = mte_to_node(mas->node);
+ struct maple_node *new_node = mte_to_node(new_mas->node);
+ unsigned long val;
+
+ /* Copy the node completely. */
+ memcpy(new_node, node, sizeof(struct maple_node));
+
+ /* Update the parent node pointer. */
+ val = (unsigned long)node->parent & MAPLE_NODE_MASK;
+ new_node->parent = ma_parent_ptr(val | (unsigned long)parent);
+}
+
+/*
+ * mas_dup_alloc() - Allocate child nodes for a maple node.
+ * @mas: The maple state of source tree.
+ * @new_mas: The maple state of new tree.
+ * @gfp: The GFP_FLAGS to use for allocations.
+ *
+ * This function allocates child nodes for @new_mas->node during the duplication
+ * process. If memory allocation fails, @mas is set to -ENOMEM.
+ */
+static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas,
+ gfp_t gfp)
+{
+ struct maple_node *node = mte_to_node(mas->node);
+ struct maple_node *new_node = mte_to_node(new_mas->node);
+ enum maple_type type;
+ unsigned char request, count, i;
+ void __rcu **slots;
+ void __rcu **new_slots;
+ unsigned long val;
+
+ /* Allocate memory for child nodes. */
+ type = mte_node_type(mas->node);
+ new_slots = ma_slots(new_node, type);
+ request = mas_data_end(mas) + 1;
+ count = mt_alloc_bulk(gfp, request, (void **)new_slots);
+ if (unlikely(count < request)) {
+ if (count) {
+ mt_free_bulk(count, new_slots);
+ memset(new_slots, 0, count * sizeof(unsigned long));
+ }
+ mas_set_err(mas, -ENOMEM);
+ return;
+ }
+
+ /* Restore node type information in slots. */
+ slots = ma_slots(node, type);
+ for (i = 0; i < count; i++) {
+ val = (unsigned long)mt_slot_locked(mas->tree, slots, i);
+ val &= MAPLE_NODE_MASK;
+ ((unsigned long *)new_slots)[i] |= val;
+ }
+}
+
+/*
+ * mas_dup_build() - Build a new maple tree from a source tree
+ * @mas: The maple state of source tree.
+ * @new_mas: The maple state of new tree.
+ * @gfp: The GFP_FLAGS to use for allocations.
+ *
+ * This function builds a new tree in DFS preorder. If the memory allocation
+ * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the
+ * last node. mas_dup_free() will free the incomplete duplication of a tree.
+ *
+ * Note that the attributes of the two trees need to be exactly the same, and the
+ * new tree needs to be empty, otherwise -EINVAL will be set in @mas.
+ */
+static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas,
+ gfp_t gfp)
+{
+ struct maple_node *node;
+ struct maple_pnode *parent = NULL;
+ struct maple_enode *root;
+ enum maple_type type;
+
+ if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) ||
+ unlikely(!mtree_empty(new_mas->tree))) {
+ mas_set_err(mas, -EINVAL);
+ return;
+ }
+
+ mas_start(mas);
+ if (mas_is_ptr(mas) || mas_is_none(mas)) {
+ root = mt_root_locked(mas->tree);
+ goto set_new_tree;
+ }
+
+ node = mt_alloc_one(gfp);
+ if (!node) {
+ new_mas->node = MAS_NONE;
+ mas_set_err(mas, -ENOMEM);
+ return;
+ }
+
+ type = mte_node_type(mas->node);
+ root = mt_mk_node(node, type);
+ new_mas->node = root;
+ new_mas->min = 0;
+ new_mas->max = ULONG_MAX;
+ root = mte_mk_root(root);
+
+ while (1) {
+ mas_copy_node(mas, new_mas, parent);
+
+ if (!mte_is_leaf(mas->node)) {
+ /* Only allocate child nodes for non-leaf nodes. */
+ mas_dup_alloc(mas, new_mas, gfp);
+ if (unlikely(mas_is_err(mas)))
+ return;
+ } else {
+ /*
+ * This is the last leaf node and duplication is
+ * completed.
+ */
+ if (mas->max == ULONG_MAX)
+ goto done;
+
+ /* This is not the last leaf node and needs to go up. */
+ do {
+ mas_ascend(mas);
+ mas_ascend(new_mas);
+ } while (mas->offset == mas_data_end(mas));
+
+ /* Move to the next subtree. */
+ mas->offset++;
+ new_mas->offset++;
+ }
+
+ mas_descend(mas);
+ parent = ma_parent_ptr(mte_to_node(new_mas->node));
+ mas_descend(new_mas);
+ mas->offset = 0;
+ new_mas->offset = 0;
+ }
+done:
+ /* Specially handle the parent of the root node. */
+ mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas));
+set_new_tree:
+ /* Make them the same height */
+ new_mas->tree->ma_flags = mas->tree->ma_flags;
+ rcu_assign_pointer(new_mas->tree->ma_root, root);
+}
+
+/**
+ * __mt_dup(): Duplicate a maple tree
+ * @mt: The source maple tree
+ * @new: The new maple tree
+ * @gfp: The GFP_FLAGS to use for allocations
+ *
+ * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
+ * traversal. It uses memcopy() to copy nodes in the source tree and allocate
+ * new child nodes in non-leaf nodes. The new node is exactly the same as the
+ * source node except for all the addresses stored in it. It will be faster than
+ * traversing all elements in the source tree and inserting them one by one into
+ * the new tree.
+ * The user needs to ensure that the attributes of the source tree and the new
+ * tree are the same, and the new tree needs to be an empty tree, otherwise
+ * -EINVAL will be returned.
+ * Note that the user needs to manually lock the source tree and the new tree.
+ *
+ * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
+ * the attributes of the two trees are different or the new tree is not an empty
+ * tree.
+ */
+int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
+{
+ int ret = 0;
+ MA_STATE(mas, mt, 0, 0);
+ MA_STATE(new_mas, new, 0, 0);
+
+ mas_dup_build(&mas, &new_mas, gfp);
+
+ if (unlikely(mas_is_err(&mas))) {
+ ret = xa_err(mas.node);
+ if (ret == -ENOMEM)
+ mas_dup_free(&new_mas);
+ }
+
+ return ret;
+}
+EXPORT_SYMBOL(__mt_dup);
+
+/**
+ * mtree_dup(): Duplicate a maple tree
+ * @mt: The source maple tree
+ * @new: The new maple tree
+ * @gfp: The GFP_FLAGS to use for allocations
+ *
+ * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
+ * traversal. It uses memcopy() to copy nodes in the source tree and allocate
+ * new child nodes in non-leaf nodes. The new node is exactly the same as the
+ * source node except for all the addresses stored in it. It will be faster than
+ * traversing all elements in the source tree and inserting them one by one into
+ * the new tree.
+ * The user needs to ensure that the attributes of the source tree and the new
+ * tree are the same, and the new tree needs to be an empty tree, otherwise
+ * -EINVAL will be returned.
+ *
+ * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
+ * the attributes of the two trees are different or the new tree is not an empty
+ * tree.
+ */
+int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
+{
+ int ret = 0;
+ MA_STATE(mas, mt, 0, 0);
+ MA_STATE(new_mas, new, 0, 0);
+
+ mas_lock(&new_mas);
+ mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
+
+ mas_dup_build(&mas, &new_mas, gfp);
+ mas_unlock(&mas);
+
+ if (unlikely(mas_is_err(&mas))) {
+ ret = xa_err(mas.node);
+ if (ret == -ENOMEM)
+ mas_dup_free(&new_mas);
+ }
+
+ mas_unlock(&new_mas);
+
+ return ret;
+}
+EXPORT_SYMBOL(mtree_dup);
+
/**
* __mt_destroy() - Walk and free all nodes of a locked maple tree.
* @mt: The maple tree
--
2.20.1
Skip other tests when BENCH is enabled so that performance can be
measured in user space.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/test_maple_tree.c | 8 ++++----
tools/testing/radix-tree/maple.c | 2 ++
2 files changed, 6 insertions(+), 4 deletions(-)
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 0674aebd4423..0ec0c6a7c0b5 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -3514,10 +3514,6 @@ static int __init maple_tree_seed(void)
pr_info("\nTEST STARTING\n\n");
- mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
- check_root_expand(&tree);
- mtree_destroy(&tree);
-
#if defined(BENCH_SLOT_STORE)
#define BENCH
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
@@ -3575,6 +3571,10 @@ static int __init maple_tree_seed(void)
goto skip;
#endif
+ mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+ check_root_expand(&tree);
+ mtree_destroy(&tree);
+
mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
check_iteration(&tree);
mtree_destroy(&tree);
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index 12b3390e9591..cb5358674521 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -36299,7 +36299,9 @@ void farmer_tests(void)
void maple_tree_tests(void)
{
+#if !defined(BENCH)
farmer_tests();
+#endif
maple_tree_seed();
maple_tree_harvest();
}
--
2.20.1
Add two helpers:
1. mt_free_one(), used to free a maple node.
2. mt_attr(), used to obtain the attributes of maple tree.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/maple_tree.c | 12 +++++++++++-
1 file changed, 11 insertions(+), 1 deletion(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index b0229271c24e..3fe5652a8c6c 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -165,6 +165,11 @@ static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes)
return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes);
}
+static inline void mt_free_one(struct maple_node *node)
+{
+ kmem_cache_free(maple_node_cache, node);
+}
+
static inline void mt_free_bulk(size_t size, void __rcu **nodes)
{
kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes);
@@ -205,6 +210,11 @@ static unsigned int mas_mt_height(struct ma_state *mas)
return mt_height(mas->tree);
}
+static inline unsigned int mt_attr(struct maple_tree *mt)
+{
+ return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK;
+}
+
static inline enum maple_type mte_node_type(const struct maple_enode *entry)
{
return ((unsigned long)entry >> MAPLE_NODE_TYPE_SHIFT) &
@@ -5520,7 +5530,7 @@ void mas_destroy(struct ma_state *mas)
mt_free_bulk(count, (void __rcu **)&node->slot[1]);
total -= count;
}
- kmem_cache_free(maple_node_cache, node);
+ mt_free_one(ma_mnode_ptr(node));
total--;
}
--
2.20.1
Updated check_forking() and bench_forking() to use __mt_dup() to
duplicate maple tree.
Signed-off-by: Peng Zhang <[email protected]>
---
lib/test_maple_tree.c | 61 +++++++++++++++++++++----------------------
1 file changed, 30 insertions(+), 31 deletions(-)
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 0ec0c6a7c0b5..485d308a1ca7 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -1837,36 +1837,37 @@ static noinline void __init check_forking(struct maple_tree *mt)
{
struct maple_tree newmt;
- int i, nr_entries = 134;
+ int i, nr_entries = 134, ret;
void *val;
MA_STATE(mas, mt, 0, 0);
- MA_STATE(newmas, mt, 0, 0);
+ MA_STATE(newmas, &newmt, 0, 0);
+
+ mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
for (i = 0; i <= nr_entries; i++)
mtree_store_range(mt, i*10, i*10 + 5,
xa_mk_value(i), GFP_KERNEL);
+
mt_set_non_kernel(99999);
- mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
- newmas.tree = &newmt;
- mas_reset(&newmas);
- mas_reset(&mas);
mas_lock(&newmas);
- mas.index = 0;
- mas.last = 0;
- if (mas_expected_entries(&newmas, nr_entries)) {
+ mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
+
+ ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN);
+ if (ret) {
pr_err("OOM!");
BUG_ON(1);
}
- rcu_read_lock();
- mas_for_each(&mas, val, ULONG_MAX) {
- newmas.index = mas.index;
- newmas.last = mas.last;
+
+ mas_set(&newmas, 0);
+ mas_for_each(&newmas, val, ULONG_MAX) {
mas_store(&newmas, val);
}
- rcu_read_unlock();
- mas_destroy(&newmas);
+
+ mas_unlock(&mas);
mas_unlock(&newmas);
+
+ mas_destroy(&newmas);
mt_validate(&newmt);
mt_set_non_kernel(0);
mtree_destroy(&newmt);
@@ -1974,12 +1975,11 @@ static noinline void __init check_mas_store_gfp(struct maple_tree *mt)
#if defined(BENCH_FORK)
static noinline void __init bench_forking(struct maple_tree *mt)
{
-
struct maple_tree newmt;
- int i, nr_entries = 134, nr_fork = 80000;
+ int i, nr_entries = 134, nr_fork = 80000, ret;
void *val;
MA_STATE(mas, mt, 0, 0);
- MA_STATE(newmas, mt, 0, 0);
+ MA_STATE(newmas, &newmt, 0, 0);
for (i = 0; i <= nr_entries; i++)
mtree_store_range(mt, i*10, i*10 + 5,
@@ -1988,25 +1988,24 @@ static noinline void __init bench_forking(struct maple_tree *mt)
for (i = 0; i < nr_fork; i++) {
mt_set_non_kernel(99999);
mt_init_flags(&newmt, MT_FLAGS_ALLOC_RANGE);
- newmas.tree = &newmt;
- mas_reset(&newmas);
- mas_reset(&mas);
- mas.index = 0;
- mas.last = 0;
- rcu_read_lock();
+
mas_lock(&newmas);
- if (mas_expected_entries(&newmas, nr_entries)) {
- printk("OOM!");
+ mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
+ ret = __mt_dup(mt, &newmt, GFP_NOWAIT | __GFP_NOWARN);
+ if (ret) {
+ pr_err("OOM!");
BUG_ON(1);
}
- mas_for_each(&mas, val, ULONG_MAX) {
- newmas.index = mas.index;
- newmas.last = mas.last;
+
+ mas_set(&newmas, 0);
+ mas_for_each(&newmas, val, ULONG_MAX) {
mas_store(&newmas, val);
}
- mas_destroy(&newmas);
+
+ mas_unlock(&mas);
mas_unlock(&newmas);
- rcu_read_unlock();
+
+ mas_destroy(&newmas);
mt_validate(&newmt);
mt_set_non_kernel(0);
mtree_destroy(&newmt);
--
2.20.1
Add test for mtree_dup().
Test by duplicating different maple trees and then comparing the two
trees. Includes tests for duplicating full trees and memory allocation
failures on different nodes.
Signed-off-by: Peng Zhang <[email protected]>
---
tools/testing/radix-tree/maple.c | 361 +++++++++++++++++++++++++++++++
1 file changed, 361 insertions(+)
diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c
index e5da1cad70ba..12b3390e9591 100644
--- a/tools/testing/radix-tree/maple.c
+++ b/tools/testing/radix-tree/maple.c
@@ -35857,6 +35857,363 @@ static noinline void __init check_locky(struct maple_tree *mt)
mt_clear_in_rcu(mt);
}
+/*
+ * Compares two nodes except for the addresses stored in the nodes.
+ * Returns zero if they are the same, otherwise returns non-zero.
+ */
+static int __init compare_node(struct maple_enode *enode_a,
+ struct maple_enode *enode_b)
+{
+ struct maple_node *node_a, *node_b;
+ struct maple_node a, b;
+ void **slots_a, **slots_b; /* Do not use the rcu tag. */
+ enum maple_type type;
+ int i;
+
+ if (((unsigned long)enode_a & MAPLE_NODE_MASK) !=
+ ((unsigned long)enode_b & MAPLE_NODE_MASK)) {
+ pr_err("The lower 8 bits of enode are different.\n");
+ return -1;
+ }
+
+ type = mte_node_type(enode_a);
+ node_a = mte_to_node(enode_a);
+ node_b = mte_to_node(enode_b);
+ a = *node_a;
+ b = *node_b;
+
+ /* Do not compare addresses. */
+ if (ma_is_root(node_a) || ma_is_root(node_b)) {
+ a.parent = (struct maple_pnode *)((unsigned long)a.parent &
+ MA_ROOT_PARENT);
+ b.parent = (struct maple_pnode *)((unsigned long)b.parent &
+ MA_ROOT_PARENT);
+ } else {
+ a.parent = (struct maple_pnode *)((unsigned long)a.parent &
+ MAPLE_NODE_MASK);
+ b.parent = (struct maple_pnode *)((unsigned long)b.parent &
+ MAPLE_NODE_MASK);
+ }
+
+ if (a.parent != b.parent) {
+ pr_err("The lower 8 bits of parents are different. %p %p\n",
+ a.parent, b.parent);
+ return -1;
+ }
+
+ /*
+ * If it is a leaf node, the slots do not contain the node address, and
+ * no special processing of slots is required.
+ */
+ if (ma_is_leaf(type))
+ goto cmp;
+
+ slots_a = ma_slots(&a, type);
+ slots_b = ma_slots(&b, type);
+
+ for (i = 0; i < mt_slots[type]; i++) {
+ if (!slots_a[i] && !slots_b[i])
+ break;
+
+ if (!slots_a[i] || !slots_b[i]) {
+ pr_err("The number of slots is different.\n");
+ return -1;
+ }
+
+ /* Do not compare addresses in slots. */
+ ((unsigned long *)slots_a)[i] &= MAPLE_NODE_MASK;
+ ((unsigned long *)slots_b)[i] &= MAPLE_NODE_MASK;
+ }
+
+cmp:
+ /*
+ * Compare all contents of two nodes, including parent (except address),
+ * slots (except address), pivots, gaps and metadata.
+ */
+ return memcmp(&a, &b, sizeof(struct maple_node));
+}
+
+/*
+ * Compare two trees and return 0 if they are the same, non-zero otherwise.
+ */
+static int __init compare_tree(struct maple_tree *mt_a, struct maple_tree *mt_b)
+{
+ MA_STATE(mas_a, mt_a, 0, 0);
+ MA_STATE(mas_b, mt_b, 0, 0);
+
+ if (mt_a->ma_flags != mt_b->ma_flags) {
+ pr_err("The flags of the two trees are different.\n");
+ return -1;
+ }
+
+ mas_dfs_preorder(&mas_a);
+ mas_dfs_preorder(&mas_b);
+
+ if (mas_is_ptr(&mas_a) || mas_is_ptr(&mas_b)) {
+ if (!(mas_is_ptr(&mas_a) && mas_is_ptr(&mas_b))) {
+ pr_err("One is MAS_ROOT and the other is not.\n");
+ return -1;
+ }
+ return 0;
+ }
+
+ while (!mas_is_none(&mas_a) || !mas_is_none(&mas_b)) {
+
+ if (mas_is_none(&mas_a) || mas_is_none(&mas_b)) {
+ pr_err("One is MAS_NONE and the other is not.\n");
+ return -1;
+ }
+
+ if (mas_a.min != mas_b.min ||
+ mas_a.max != mas_b.max) {
+ pr_err("mas->min, mas->max do not match.\n");
+ return -1;
+ }
+
+ if (compare_node(mas_a.node, mas_b.node)) {
+ pr_err("The contents of nodes %p and %p are different.\n",
+ mas_a.node, mas_b.node);
+ mt_dump(mt_a, mt_dump_dec);
+ mt_dump(mt_b, mt_dump_dec);
+ return -1;
+ }
+
+ mas_dfs_preorder(&mas_a);
+ mas_dfs_preorder(&mas_b);
+ }
+
+ return 0;
+}
+
+static __init void mas_subtree_max_range(struct ma_state *mas)
+{
+ unsigned long limit = mas->max;
+ MA_STATE(newmas, mas->tree, 0, 0);
+ void *entry;
+
+ mas_for_each(mas, entry, limit) {
+ if (mas->last - mas->index >=
+ newmas.last - newmas.index) {
+ newmas = *mas;
+ }
+ }
+
+ *mas = newmas;
+}
+
+/*
+ * build_full_tree() - Build a full tree.
+ * @mt: The tree to build.
+ * @flags: Use @flags to build the tree.
+ * @height: The height of the tree to build.
+ *
+ * Build a tree with full leaf nodes and internal nodes. Note that the height
+ * should not exceed 3, otherwise it will take a long time to build.
+ * Return: zero if the build is successful, non-zero if it fails.
+ */
+static __init int build_full_tree(struct maple_tree *mt, unsigned int flags,
+ int height)
+{
+ MA_STATE(mas, mt, 0, 0);
+ unsigned long step;
+ int ret = 0, cnt = 1;
+ enum maple_type type;
+
+ mt_init_flags(mt, flags);
+ mtree_insert_range(mt, 0, ULONG_MAX, xa_mk_value(5), GFP_KERNEL);
+
+ mtree_lock(mt);
+
+ while (1) {
+ mas_set(&mas, 0);
+ if (mt_height(mt) < height) {
+ mas.max = ULONG_MAX;
+ goto store;
+ }
+
+ while (1) {
+ mas_dfs_preorder(&mas);
+ if (mas_is_none(&mas))
+ goto unlock;
+
+ type = mte_node_type(mas.node);
+ if (mas_data_end(&mas) + 1 < mt_slots[type]) {
+ mas_set(&mas, mas.min);
+ goto store;
+ }
+ }
+store:
+ mas_subtree_max_range(&mas);
+ step = mas.last - mas.index;
+ if (step < 1) {
+ ret = -1;
+ goto unlock;
+ }
+
+ step /= 2;
+ mas.last = mas.index + step;
+ mas_store_gfp(&mas, xa_mk_value(5),
+ GFP_KERNEL);
+ ++cnt;
+ }
+unlock:
+ mtree_unlock(mt);
+
+ MT_BUG_ON(mt, mt_height(mt) != height);
+ /* pr_info("height:%u number of elements:%d\n", mt_height(mt), cnt); */
+ return ret;
+}
+
+static noinline void __init check_mtree_dup(struct maple_tree *mt)
+{
+ DEFINE_MTREE(new);
+ int i, j, ret, count = 0;
+ unsigned int rand_seed = 17, rand;
+
+ /* store a value at [0, 0] */
+ mt_init_flags(mt, 0);
+ mtree_store_range(mt, 0, 0, xa_mk_value(0), GFP_KERNEL);
+ ret = mtree_dup(mt, &new, GFP_KERNEL);
+ MT_BUG_ON(&new, ret);
+ mt_validate(&new);
+ if (compare_tree(mt, &new))
+ MT_BUG_ON(&new, 1);
+
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+
+ /* The two trees have different attributes. */
+ mt_init_flags(mt, 0);
+ mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE);
+ ret = mtree_dup(mt, &new, GFP_KERNEL);
+ MT_BUG_ON(&new, ret != -EINVAL);
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+
+ /* The new tree is not empty */
+ mt_init_flags(mt, 0);
+ mt_init_flags(&new, 0);
+ mtree_store(&new, 5, xa_mk_value(5), GFP_KERNEL);
+ ret = mtree_dup(mt, &new, GFP_KERNEL);
+ MT_BUG_ON(&new, ret != -EINVAL);
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+
+ /* Test for duplicating full trees. */
+ for (i = 1; i <= 3; i++) {
+ ret = build_full_tree(mt, 0, i);
+ MT_BUG_ON(mt, ret);
+ mt_init_flags(&new, 0);
+
+ ret = mtree_dup(mt, &new, GFP_KERNEL);
+ MT_BUG_ON(&new, ret);
+ mt_validate(&new);
+ if (compare_tree(mt, &new))
+ MT_BUG_ON(&new, 1);
+
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+ }
+
+ for (i = 1; i <= 3; i++) {
+ ret = build_full_tree(mt, MT_FLAGS_ALLOC_RANGE, i);
+ MT_BUG_ON(mt, ret);
+ mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE);
+
+ ret = mtree_dup(mt, &new, GFP_KERNEL);
+ MT_BUG_ON(&new, ret);
+ mt_validate(&new);
+ if (compare_tree(mt, &new))
+ MT_BUG_ON(&new, 1);
+
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+ }
+
+ /* Test for normal duplicating. */
+ for (i = 0; i < 1000; i += 3) {
+ if (i & 1) {
+ mt_init_flags(mt, 0);
+ mt_init_flags(&new, 0);
+ } else {
+ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+ mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE);
+ }
+
+ for (j = 0; j < i; j++) {
+ mtree_store_range(mt, j * 10, j * 10 + 5,
+ xa_mk_value(j), GFP_KERNEL);
+ }
+
+ ret = mtree_dup(mt, &new, GFP_KERNEL);
+ MT_BUG_ON(&new, ret);
+ mt_validate(&new);
+ if (compare_tree(mt, &new))
+ MT_BUG_ON(&new, 1);
+
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+ }
+
+ /* Test memory allocation failed. */
+ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+ for (i = 0; i < 30; i += 3) {
+ mtree_store_range(mt, j * 10, j * 10 + 5,
+ xa_mk_value(j), GFP_KERNEL);
+ }
+
+ /* Failed at the first node. */
+ mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE);
+ mt_set_non_kernel(0);
+ ret = mtree_dup(mt, &new, GFP_NOWAIT);
+ mt_set_non_kernel(0);
+ MT_BUG_ON(&new, ret != -ENOMEM);
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+
+ /* Random maple tree fails at a random node. */
+ for (i = 0; i < 1000; i += 3) {
+ if (i & 1) {
+ mt_init_flags(mt, 0);
+ mt_init_flags(&new, 0);
+ } else {
+ mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
+ mt_init_flags(&new, MT_FLAGS_ALLOC_RANGE);
+ }
+
+ for (j = 0; j < i; j++) {
+ mtree_store_range(mt, j * 10, j * 10 + 5,
+ xa_mk_value(j), GFP_KERNEL);
+ }
+ /*
+ * The rand() library function is not used, so we can generate
+ * the same random numbers on any platform.
+ */
+ rand_seed = rand_seed * 1103515245 + 12345;
+ rand = rand_seed / 65536 % 128;
+ mt_set_non_kernel(rand);
+
+ ret = mtree_dup(mt, &new, GFP_NOWAIT);
+ mt_set_non_kernel(0);
+ if (ret != 0) {
+ MT_BUG_ON(&new, ret != -ENOMEM);
+ count++;
+ mtree_destroy(mt);
+ continue;
+ }
+
+ mt_validate(&new);
+ if (compare_tree(mt, &new))
+ MT_BUG_ON(&new, 1);
+
+ mtree_destroy(mt);
+ mtree_destroy(&new);
+ }
+
+ /* pr_info("mtree_dup() fail %d times\n", count); */
+ BUG_ON(!count);
+}
+
extern void test_kmem_cache_bulk(void);
void farmer_tests(void)
@@ -35904,6 +36261,10 @@ void farmer_tests(void)
check_null_expand(&tree);
mtree_destroy(&tree);
+ mt_init_flags(&tree, 0);
+ check_mtree_dup(&tree);
+ mtree_destroy(&tree);
+
/* RCU testing */
mt_init_flags(&tree, 0);
check_erase_testset(&tree);
--
2.20.1
In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
directly replacing the entries of VMAs in the new maple tree can result
in better performance. __mt_dup() uses DFS pre-order to duplicate the
maple tree, so it is very efficient. The average time complexity of
duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
effect is proportional to the number of VMAs.
As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
fails, there will be a portion of VMAs that have not been duplicated in
the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
To solve this problem, undo_dup_mmap() is introduced to handle the failure
of dup_mmap(). I have carefully tested the failure path and so far it
seems there are no issues.
There is a "spawn" in byte-unixbench[1], which can be used to test the
performance of fork(). I modified it slightly to make it work with
different number of VMAs.
Below are the test results. By default, there are 21 VMAs. The first row
shows the number of additional VMAs added on top of the default. The last
two rows show the number of fork() calls per ten seconds. The test results
were obtained with CPU binding to avoid scheduler load balancing that
could cause unstable results. There are still some fluctuations in the
test results, but at least they are better than the original performance.
Increment of VMAs: 0 100 200 400 800 1600 3200 6400
next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
+3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
[1] https://github.com/kdlucas/byte-unixbench/tree/master
Signed-off-by: Peng Zhang <[email protected]>
---
include/linux/mm.h | 1 +
kernel/fork.c | 34 ++++++++++++++++++++----------
mm/internal.h | 3 ++-
mm/memory.c | 7 ++++---
mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
5 files changed, 80 insertions(+), 17 deletions(-)
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 1f1d0d6b8f20..10c59dc7ffaa 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
unsigned long addr, unsigned long len, pgoff_t pgoff,
bool *need_rmap_locks);
+extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
extern void exit_mmap(struct mm_struct *);
static inline int check_data_rlimit(unsigned long rlim,
diff --git a/kernel/fork.c b/kernel/fork.c
index 7ae36c2e7290..2f3d83e89fe6 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
int retval;
unsigned long charge = 0;
LIST_HEAD(uf);
- VMA_ITERATOR(old_vmi, oldmm, 0);
VMA_ITERATOR(vmi, mm, 0);
uprobe_start_dup_mmap();
@@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
goto out;
khugepaged_fork(mm, oldmm);
- retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
- if (retval)
+ /* Use __mt_dup() to efficiently build an identical maple tree. */
+ retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
+ if (unlikely(retval))
goto out;
mt_clear_in_rcu(vmi.mas.tree);
- for_each_vma(old_vmi, mpnt) {
+ for_each_vma(vmi, mpnt) {
struct file *file;
vma_start_write(mpnt);
if (mpnt->vm_flags & VM_DONTCOPY) {
+ mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
+
+ /* If failed, undo all completed duplications. */
+ if (unlikely(mas_is_err(&vmi.mas))) {
+ retval = xa_err(vmi.mas.node);
+ goto loop_out;
+ }
+
vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
continue;
}
@@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
if (is_vm_hugetlb_page(tmp))
hugetlb_dup_vma_private(tmp);
- /* Link the vma into the MT */
- if (vma_iter_bulk_store(&vmi, tmp))
- goto fail_nomem_vmi_store;
+ /*
+ * Link the vma into the MT. After using __mt_dup(), memory
+ * allocation is not necessary here, so it cannot fail.
+ */
+ mas_store(&vmi.mas, tmp);
mm->map_count++;
if (!(tmp->vm_flags & VM_WIPEONFORK))
@@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
if (tmp->vm_ops && tmp->vm_ops->open)
tmp->vm_ops->open(tmp);
- if (retval)
+ if (retval) {
+ mpnt = vma_next(&vmi);
goto loop_out;
+ }
}
/* a new mm has just been created */
retval = arch_dup_mmap(oldmm, mm);
loop_out:
vma_iter_free(&vmi);
- if (!retval)
+ if (likely(!retval))
mt_set_in_rcu(vmi.mas.tree);
+ else
+ undo_dup_mmap(mm, mpnt);
out:
mmap_write_unlock(mm);
flush_tlb_mm(oldmm);
@@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
uprobe_end_dup_mmap();
return retval;
-fail_nomem_vmi_store:
- unlink_anon_vmas(tmp);
fail_nomem_anon_vma_fork:
mpol_put(vma_policy(tmp));
fail_nomem_policy:
diff --git a/mm/internal.h b/mm/internal.h
index 7a961d12b088..288ec81770cb 100644
--- a/mm/internal.h
+++ b/mm/internal.h
@@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
struct vm_area_struct *start_vma, unsigned long floor,
- unsigned long ceiling, bool mm_wr_locked);
+ unsigned long ceiling, unsigned long tree_end,
+ bool mm_wr_locked);
void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
struct zap_details;
diff --git a/mm/memory.c b/mm/memory.c
index 983a40f8ee62..1fd66a0d5838 100644
--- a/mm/memory.c
+++ b/mm/memory.c
@@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
struct vm_area_struct *vma, unsigned long floor,
- unsigned long ceiling, bool mm_wr_locked)
+ unsigned long ceiling, unsigned long tree_end,
+ bool mm_wr_locked)
{
do {
unsigned long addr = vma->vm_start;
@@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
* Note: USER_PGTABLES_CEILING may be passed as ceiling and may
* be 0. This will underflow and is okay.
*/
- next = mas_find(mas, ceiling - 1);
+ next = mas_find(mas, tree_end - 1);
/*
* Hide vma from rmap and truncate_pagecache before freeing
@@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
while (next && next->vm_start <= vma->vm_end + PMD_SIZE
&& !is_vm_hugetlb_page(next)) {
vma = next;
- next = mas_find(mas, ceiling - 1);
+ next = mas_find(mas, tree_end - 1);
if (mm_wr_locked)
vma_start_write(vma);
unlink_anon_vmas(vma);
diff --git a/mm/mmap.c b/mm/mmap.c
index 2ad950f773e4..daed3b423124 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
mas_set(mas, mt_start);
free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
next ? next->vm_start : USER_PGTABLES_CEILING,
- mm_wr_locked);
+ tree_end, mm_wr_locked);
tlb_finish_mmu(&tlb);
}
@@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
}
EXPORT_SYMBOL(vm_brk);
+void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
+{
+ unsigned long tree_end;
+ VMA_ITERATOR(vmi, mm, 0);
+ struct vm_area_struct *vma;
+ unsigned long nr_accounted = 0;
+ int count = 0;
+
+ /*
+ * vma_end points to the first VMA that has not been duplicated. We need
+ * to unmap all VMAs before it.
+ * If vma_end is NULL, it means that all VMAs in the maple tree have
+ * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
+ * when using it.
+ */
+ if (vma_end) {
+ tree_end = vma_end->vm_start;
+ if (tree_end == 0)
+ goto destroy;
+ } else
+ tree_end = 0;
+
+ vma = mas_find(&vmi.mas, tree_end - 1);
+
+ if (vma) {
+ arch_unmap(mm, vma->vm_start, tree_end);
+ unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
+ tree_end, true);
+
+ mas_set(&vmi.mas, vma->vm_end);
+ do {
+ if (vma->vm_flags & VM_ACCOUNT)
+ nr_accounted += vma_pages(vma);
+ remove_vma(vma, true);
+ count++;
+ cond_resched();
+ vma = mas_find(&vmi.mas, tree_end - 1);
+ } while (vma != NULL);
+
+ BUG_ON(count != mm->map_count);
+
+ vm_unacct_memory(nr_accounted);
+ }
+
+destroy:
+ __mt_destroy(&mm->mm_mt);
+}
+
/* Release all mmaps. */
void exit_mmap(struct mm_struct *mm)
{
@@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
mt_clear_in_rcu(&mm->mm_mt);
mas_set(&mas, vma->vm_end);
free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
- USER_PGTABLES_CEILING, true);
+ USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
tlb_finish_mmu(&tlb);
/*
--
2.20.1
* Peng Zhang <[email protected]> [230924 23:58]:
> Introduce interfaces __mt_dup() and mtree_dup(), which are used to
> duplicate a maple tree. They duplicate a maple tree in Depth-First
> Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the
> source tree and allocate new child nodes in non-leaf nodes. The new node
> is exactly the same as the source node except for all the addresses
> stored in it. It will be faster than traversing all elements in the
> source tree and inserting them one by one into the new tree. The time
> complexity of these two functions is O(n).
>
> The difference between __mt_dup() and mtree_dup() is that mtree_dup()
> handles locks internally.
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> include/linux/maple_tree.h | 3 +
> lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++
> 2 files changed, 289 insertions(+)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index 666a3764ed89..de5a4056503a 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index,
> void *entry, gfp_t gfp);
> void *mtree_erase(struct maple_tree *mt, unsigned long index);
>
> +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
> +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
> +
> void mtree_destroy(struct maple_tree *mt);
> void __mt_destroy(struct maple_tree *mt);
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 3fe5652a8c6c..ed8847b4f1ff 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6370,6 +6370,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
> }
> EXPORT_SYMBOL(mtree_erase);
>
> +/*
> + * mas_dup_free() - Free an incomplete duplication of a tree.
> + * @mas: The maple state of a incomplete tree.
> + *
> + * The parameter @mas->node passed in indicates that the allocation failed on
> + * this node. This function frees all nodes starting from @mas->node in the
> + * reverse order of mas_dup_build(). There is no need to hold the source tree
> + * lock at this time.
> + */
> +static void mas_dup_free(struct ma_state *mas)
> +{
> + struct maple_node *node;
> + enum maple_type type;
> + void __rcu **slots;
> + unsigned char count, i;
> +
> + /* Maybe the first node allocation failed. */
> + if (mas_is_none(mas))
> + return;
> +
> + while (!mte_is_root(mas->node)) {
> + mas_ascend(mas);
> +
> + if (mas->offset) {
> + mas->offset--;
> + do {
> + mas_descend(mas);
> + mas->offset = mas_data_end(mas);
> + } while (!mte_is_leaf(mas->node));
> +
> + mas_ascend(mas);
> + }
> +
> + node = mte_to_node(mas->node);
> + type = mte_node_type(mas->node);
> + slots = ma_slots(node, type);
> + count = mas_data_end(mas) + 1;
> + for (i = 0; i < count; i++)
> + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK;
> +
> + mt_free_bulk(count, slots);
> + }
> +
> + node = mte_to_node(mas->node);
> + mt_free_one(node);
> +}
> +
> +/*
> + * mas_copy_node() - Copy a maple node and replace the parent.
> + * @mas: The maple state of source tree.
> + * @new_mas: The maple state of new tree.
> + * @parent: The parent of the new node.
> + *
> + * Copy @mas->node to @new_mas->node, set @parent to be the parent of
> + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM.
> + */
> +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas,
> + struct maple_pnode *parent)
> +{
> + struct maple_node *node = mte_to_node(mas->node);
> + struct maple_node *new_node = mte_to_node(new_mas->node);
> + unsigned long val;
> +
> + /* Copy the node completely. */
> + memcpy(new_node, node, sizeof(struct maple_node));
> +
> + /* Update the parent node pointer. */
> + val = (unsigned long)node->parent & MAPLE_NODE_MASK;
> + new_node->parent = ma_parent_ptr(val | (unsigned long)parent);
> +}
> +
> +/*
> + * mas_dup_alloc() - Allocate child nodes for a maple node.
> + * @mas: The maple state of source tree.
> + * @new_mas: The maple state of new tree.
> + * @gfp: The GFP_FLAGS to use for allocations.
> + *
> + * This function allocates child nodes for @new_mas->node during the duplication
> + * process. If memory allocation fails, @mas is set to -ENOMEM.
> + */
> +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas,
> + gfp_t gfp)
> +{
> + struct maple_node *node = mte_to_node(mas->node);
> + struct maple_node *new_node = mte_to_node(new_mas->node);
> + enum maple_type type;
> + unsigned char request, count, i;
> + void __rcu **slots;
> + void __rcu **new_slots;
> + unsigned long val;
> +
> + /* Allocate memory for child nodes. */
> + type = mte_node_type(mas->node);
> + new_slots = ma_slots(new_node, type);
> + request = mas_data_end(mas) + 1;
> + count = mt_alloc_bulk(gfp, request, (void **)new_slots);
> + if (unlikely(count < request)) {
> + if (count) {
> + mt_free_bulk(count, new_slots);
If you look at mm/slab.c: kmem_cache_alloc(), you will see that the
error path already bulk frees for you - but does not zero the array.
This bulk free will lead to double free, but you do need the below
memset(). Also, it will return !count or request. So, I think this code
is never executed as it is written.
I don't think this will show up in your testcases because the test code
doesn't leave dangling pointers and simply returns 0 if there isn't
enough nodes.
> + memset(new_slots, 0, count * sizeof(unsigned long));
> + }
> + mas_set_err(mas, -ENOMEM);
> + return;
> + }
> +
> + /* Restore node type information in slots. */
> + slots = ma_slots(node, type);
> + for (i = 0; i < count; i++) {
> + val = (unsigned long)mt_slot_locked(mas->tree, slots, i);
> + val &= MAPLE_NODE_MASK;
> + ((unsigned long *)new_slots)[i] |= val;
> + }
> +}
> +
> +/*
> + * mas_dup_build() - Build a new maple tree from a source tree
> + * @mas: The maple state of source tree.
> + * @new_mas: The maple state of new tree.
> + * @gfp: The GFP_FLAGS to use for allocations.
> + *
> + * This function builds a new tree in DFS preorder. If the memory allocation
> + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the
> + * last node. mas_dup_free() will free the incomplete duplication of a tree.
> + *
> + * Note that the attributes of the two trees need to be exactly the same, and the
> + * new tree needs to be empty, otherwise -EINVAL will be set in @mas.
> + */
> +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas,
> + gfp_t gfp)
> +{
> + struct maple_node *node;
> + struct maple_pnode *parent = NULL;
> + struct maple_enode *root;
> + enum maple_type type;
> +
> + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) ||
> + unlikely(!mtree_empty(new_mas->tree))) {
Would it be worth checking mas_is_start() for both mas and new_mas here?
Otherwise mas_start() will not do what you want below. I think it is
implied that both are at MAS_START but never checked?
> + mas_set_err(mas, -EINVAL);
> + return;
> + }
> +
> + mas_start(mas);
> + if (mas_is_ptr(mas) || mas_is_none(mas)) {
> + root = mt_root_locked(mas->tree);
> + goto set_new_tree;
> + }
> +
> + node = mt_alloc_one(gfp);
> + if (!node) {
> + new_mas->node = MAS_NONE;
> + mas_set_err(mas, -ENOMEM);
> + return;
> + }
> +
> + type = mte_node_type(mas->node);
> + root = mt_mk_node(node, type);
> + new_mas->node = root;
> + new_mas->min = 0;
> + new_mas->max = ULONG_MAX;
> + root = mte_mk_root(root);
> +
> + while (1) {
> + mas_copy_node(mas, new_mas, parent);
> +
> + if (!mte_is_leaf(mas->node)) {
> + /* Only allocate child nodes for non-leaf nodes. */
> + mas_dup_alloc(mas, new_mas, gfp);
> + if (unlikely(mas_is_err(mas)))
> + return;
> + } else {
> + /*
> + * This is the last leaf node and duplication is
> + * completed.
> + */
> + if (mas->max == ULONG_MAX)
> + goto done;
> +
> + /* This is not the last leaf node and needs to go up. */
> + do {
> + mas_ascend(mas);
> + mas_ascend(new_mas);
> + } while (mas->offset == mas_data_end(mas));
> +
> + /* Move to the next subtree. */
> + mas->offset++;
> + new_mas->offset++;
> + }
> +
> + mas_descend(mas);
> + parent = ma_parent_ptr(mte_to_node(new_mas->node));
> + mas_descend(new_mas);
> + mas->offset = 0;
> + new_mas->offset = 0;
> + }
> +done:
> + /* Specially handle the parent of the root node. */
> + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas));
> +set_new_tree:
> + /* Make them the same height */
> + new_mas->tree->ma_flags = mas->tree->ma_flags;
> + rcu_assign_pointer(new_mas->tree->ma_root, root);
> +}
> +
> +/**
> + * __mt_dup(): Duplicate a maple tree
> + * @mt: The source maple tree
> + * @new: The new maple tree
> + * @gfp: The GFP_FLAGS to use for allocations
> + *
> + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
> + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
> + * new child nodes in non-leaf nodes. The new node is exactly the same as the
> + * source node except for all the addresses stored in it. It will be faster than
> + * traversing all elements in the source tree and inserting them one by one into
> + * the new tree.
> + * The user needs to ensure that the attributes of the source tree and the new
> + * tree are the same, and the new tree needs to be an empty tree, otherwise
> + * -EINVAL will be returned.
> + * Note that the user needs to manually lock the source tree and the new tree.
> + *
> + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
> + * the attributes of the two trees are different or the new tree is not an empty
> + * tree.
> + */
> +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
> +{
> + int ret = 0;
> + MA_STATE(mas, mt, 0, 0);
> + MA_STATE(new_mas, new, 0, 0);
> +
> + mas_dup_build(&mas, &new_mas, gfp);
> +
> + if (unlikely(mas_is_err(&mas))) {
> + ret = xa_err(mas.node);
> + if (ret == -ENOMEM)
> + mas_dup_free(&new_mas);
> + }
> +
> + return ret;
> +}
> +EXPORT_SYMBOL(__mt_dup);
> +
> +/**
> + * mtree_dup(): Duplicate a maple tree
> + * @mt: The source maple tree
> + * @new: The new maple tree
> + * @gfp: The GFP_FLAGS to use for allocations
> + *
> + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
> + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
> + * new child nodes in non-leaf nodes. The new node is exactly the same as the
> + * source node except for all the addresses stored in it. It will be faster than
> + * traversing all elements in the source tree and inserting them one by one into
> + * the new tree.
> + * The user needs to ensure that the attributes of the source tree and the new
> + * tree are the same, and the new tree needs to be an empty tree, otherwise
> + * -EINVAL will be returned.
The requirement to duplicate the entire tree should be mentioned and
maybe the mas_is_start() requirement (as I asked about above?)
I can see someone thinking they are going to make a super fast sub-tree
of existing data using this - which won't (always?) work.
> + *
> + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
> + * the attributes of the two trees are different or the new tree is not an empty
> + * tree.
> + */
> +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
> +{
> + int ret = 0;
> + MA_STATE(mas, mt, 0, 0);
> + MA_STATE(new_mas, new, 0, 0);
> +
> + mas_lock(&new_mas);
> + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
> +
> + mas_dup_build(&mas, &new_mas, gfp);
> + mas_unlock(&mas);
> +
> + if (unlikely(mas_is_err(&mas))) {
> + ret = xa_err(mas.node);
> + if (ret == -ENOMEM)
> + mas_dup_free(&new_mas);
> + }
> +
> + mas_unlock(&new_mas);
> +
> + return ret;
> +}
> +EXPORT_SYMBOL(mtree_dup);
> +
> /**
> * __mt_destroy() - Walk and free all nodes of a locked maple tree.
> * @mt: The maple tree
> --
> 2.20.1
>
* Peng Zhang <[email protected]> [230924 23:58]:
> Introduce the new interface mtree_dup() in the documentation.
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> Documentation/core-api/maple_tree.rst | 4 ++++
> 1 file changed, 4 insertions(+)
>
> diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
> index 45defcf15da7..3d8a1edf6d04 100644
> --- a/Documentation/core-api/maple_tree.rst
> +++ b/Documentation/core-api/maple_tree.rst
> @@ -81,6 +81,9 @@ section.
> Sometimes it is necessary to ensure the next call to store to a maple tree does
> not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case.
>
> +You can use mtree_dup() to duplicate an identical tree. It is a more efficient
"You can use mtree_dup() to create an identical tree." duplicate an
identical tree seems redundant.
> +way than inserting all elements one by one into a new tree.
> +
> Finally, you can remove all entries from a maple tree by calling
> mtree_destroy(). If the maple tree entries are pointers, you may wish to free
> the entries first.
> @@ -112,6 +115,7 @@ Takes ma_lock internally:
> * mtree_insert()
> * mtree_insert_range()
> * mtree_erase()
> + * mtree_dup()
> * mtree_destroy()
> * mt_set_in_rcu()
> * mt_clear_in_rcu()
> --
> 2.20.1
>
* Peng Zhang <[email protected]> [230924 23:58]:
> In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
> directly replacing the entries of VMAs in the new maple tree can result
> in better performance. __mt_dup() uses DFS pre-order to duplicate the
> maple tree, so it is very efficient. The average time complexity of
> duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
> effect is proportional to the number of VMAs.
I am not confident in the big O calculations here. Although the addition
of the tree is reduced, adding a VMA still needs to create the nodes
above it - which are a function of n. How did you get O(n * log(n)) for
the existing fork?
I would think your new algorithm is n * log(n/16), while the
previous was n * log(n/16) * f(n). Where f(n) would be something
to do with the decision to split/rebalance in bulk insert mode.
It's certainly a better algorithm to duplicate trees, but I don't think
it is O(n). Can you please explain?
>
> As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
> fails, there will be a portion of VMAs that have not been duplicated in
> the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
> To solve this problem, undo_dup_mmap() is introduced to handle the failure
> of dup_mmap(). I have carefully tested the failure path and so far it
> seems there are no issues.
>
> There is a "spawn" in byte-unixbench[1], which can be used to test the
> performance of fork(). I modified it slightly to make it work with
> different number of VMAs.
>
> Below are the test results. By default, there are 21 VMAs. The first row
> shows the number of additional VMAs added on top of the default. The last
> two rows show the number of fork() calls per ten seconds. The test results
> were obtained with CPU binding to avoid scheduler load balancing that
> could cause unstable results. There are still some fluctuations in the
> test results, but at least they are better than the original performance.
>
> Increment of VMAs: 0 100 200 400 800 1600 3200 6400
> next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
> Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
> +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
>
> [1] https://github.com/kdlucas/byte-unixbench/tree/master
>
> Signed-off-by: Peng Zhang <[email protected]>
> ---
> include/linux/mm.h | 1 +
> kernel/fork.c | 34 ++++++++++++++++++++----------
> mm/internal.h | 3 ++-
> mm/memory.c | 7 ++++---
> mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
> 5 files changed, 80 insertions(+), 17 deletions(-)
>
> diff --git a/include/linux/mm.h b/include/linux/mm.h
> index 1f1d0d6b8f20..10c59dc7ffaa 100644
> --- a/include/linux/mm.h
> +++ b/include/linux/mm.h
> @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
> extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
> unsigned long addr, unsigned long len, pgoff_t pgoff,
> bool *need_rmap_locks);
> +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
> extern void exit_mmap(struct mm_struct *);
>
> static inline int check_data_rlimit(unsigned long rlim,
> diff --git a/kernel/fork.c b/kernel/fork.c
> index 7ae36c2e7290..2f3d83e89fe6 100644
> --- a/kernel/fork.c
> +++ b/kernel/fork.c
> @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> int retval;
> unsigned long charge = 0;
> LIST_HEAD(uf);
> - VMA_ITERATOR(old_vmi, oldmm, 0);
> VMA_ITERATOR(vmi, mm, 0);
>
> uprobe_start_dup_mmap();
> @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> goto out;
> khugepaged_fork(mm, oldmm);
>
> - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
> - if (retval)
> + /* Use __mt_dup() to efficiently build an identical maple tree. */
> + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
> + if (unlikely(retval))
> goto out;
>
> mt_clear_in_rcu(vmi.mas.tree);
> - for_each_vma(old_vmi, mpnt) {
> + for_each_vma(vmi, mpnt) {
> struct file *file;
>
> vma_start_write(mpnt);
> if (mpnt->vm_flags & VM_DONTCOPY) {
> + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
> +
> + /* If failed, undo all completed duplications. */
> + if (unlikely(mas_is_err(&vmi.mas))) {
> + retval = xa_err(vmi.mas.node);
> + goto loop_out;
> + }
> +
> vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
> continue;
> }
> @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> if (is_vm_hugetlb_page(tmp))
> hugetlb_dup_vma_private(tmp);
>
> - /* Link the vma into the MT */
> - if (vma_iter_bulk_store(&vmi, tmp))
> - goto fail_nomem_vmi_store;
> + /*
> + * Link the vma into the MT. After using __mt_dup(), memory
> + * allocation is not necessary here, so it cannot fail.
> + */
> + mas_store(&vmi.mas, tmp);
>
> mm->map_count++;
> if (!(tmp->vm_flags & VM_WIPEONFORK))
> @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> if (tmp->vm_ops && tmp->vm_ops->open)
> tmp->vm_ops->open(tmp);
>
> - if (retval)
> + if (retval) {
> + mpnt = vma_next(&vmi);
> goto loop_out;
> + }
> }
> /* a new mm has just been created */
> retval = arch_dup_mmap(oldmm, mm);
> loop_out:
> vma_iter_free(&vmi);
> - if (!retval)
> + if (likely(!retval))
> mt_set_in_rcu(vmi.mas.tree);
> + else
> + undo_dup_mmap(mm, mpnt);
> out:
> mmap_write_unlock(mm);
> flush_tlb_mm(oldmm);
> @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> uprobe_end_dup_mmap();
> return retval;
>
> -fail_nomem_vmi_store:
> - unlink_anon_vmas(tmp);
> fail_nomem_anon_vma_fork:
> mpol_put(vma_policy(tmp));
> fail_nomem_policy:
> diff --git a/mm/internal.h b/mm/internal.h
> index 7a961d12b088..288ec81770cb 100644
> --- a/mm/internal.h
> +++ b/mm/internal.h
> @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
>
> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> struct vm_area_struct *start_vma, unsigned long floor,
> - unsigned long ceiling, bool mm_wr_locked);
> + unsigned long ceiling, unsigned long tree_end,
> + bool mm_wr_locked);
> void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
>
> struct zap_details;
> diff --git a/mm/memory.c b/mm/memory.c
> index 983a40f8ee62..1fd66a0d5838 100644
> --- a/mm/memory.c
> +++ b/mm/memory.c
> @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
>
> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> struct vm_area_struct *vma, unsigned long floor,
> - unsigned long ceiling, bool mm_wr_locked)
> + unsigned long ceiling, unsigned long tree_end,
> + bool mm_wr_locked)
> {
> do {
> unsigned long addr = vma->vm_start;
> @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
> * be 0. This will underflow and is okay.
> */
> - next = mas_find(mas, ceiling - 1);
> + next = mas_find(mas, tree_end - 1);
>
> /*
> * Hide vma from rmap and truncate_pagecache before freeing
> @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> while (next && next->vm_start <= vma->vm_end + PMD_SIZE
> && !is_vm_hugetlb_page(next)) {
> vma = next;
> - next = mas_find(mas, ceiling - 1);
> + next = mas_find(mas, tree_end - 1);
> if (mm_wr_locked)
> vma_start_write(vma);
> unlink_anon_vmas(vma);
> diff --git a/mm/mmap.c b/mm/mmap.c
> index 2ad950f773e4..daed3b423124 100644
> --- a/mm/mmap.c
> +++ b/mm/mmap.c
> @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
> mas_set(mas, mt_start);
> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
> next ? next->vm_start : USER_PGTABLES_CEILING,
> - mm_wr_locked);
> + tree_end, mm_wr_locked);
> tlb_finish_mmu(&tlb);
> }
>
> @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
> }
> EXPORT_SYMBOL(vm_brk);
>
> +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
> +{
> + unsigned long tree_end;
> + VMA_ITERATOR(vmi, mm, 0);
> + struct vm_area_struct *vma;
> + unsigned long nr_accounted = 0;
> + int count = 0;
> +
> + /*
> + * vma_end points to the first VMA that has not been duplicated. We need
> + * to unmap all VMAs before it.
> + * If vma_end is NULL, it means that all VMAs in the maple tree have
> + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
> + * when using it.
> + */
> + if (vma_end) {
> + tree_end = vma_end->vm_start;
> + if (tree_end == 0)
> + goto destroy;
> + } else
> + tree_end = 0;
> +
> + vma = mas_find(&vmi.mas, tree_end - 1);
> +
> + if (vma) {
> + arch_unmap(mm, vma->vm_start, tree_end);
> + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
> + tree_end, true);
next is vma_end, as per your comment above. Using next = vma_end allows
you to avoid adding another argument to free_pgtables().
> +
> + mas_set(&vmi.mas, vma->vm_end);
> + do {
> + if (vma->vm_flags & VM_ACCOUNT)
> + nr_accounted += vma_pages(vma);
> + remove_vma(vma, true);
> + count++;
> + cond_resched();
> + vma = mas_find(&vmi.mas, tree_end - 1);
> + } while (vma != NULL);
> +
> + BUG_ON(count != mm->map_count);
> +
> + vm_unacct_memory(nr_accounted);
> + }
> +
> +destroy:
> + __mt_destroy(&mm->mm_mt);
> +}
> +
> /* Release all mmaps. */
> void exit_mmap(struct mm_struct *mm)
> {
> @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
> mt_clear_in_rcu(&mm->mm_mt);
> mas_set(&mas, vma->vm_end);
> free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
> - USER_PGTABLES_CEILING, true);
> + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
> tlb_finish_mmu(&tlb);
>
> /*
> --
> 2.20.1
>
在 2023/10/4 02:45, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230924 23:58]:
>> Introduce interfaces __mt_dup() and mtree_dup(), which are used to
>> duplicate a maple tree. They duplicate a maple tree in Depth-First
>> Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the
>> source tree and allocate new child nodes in non-leaf nodes. The new node
>> is exactly the same as the source node except for all the addresses
>> stored in it. It will be faster than traversing all elements in the
>> source tree and inserting them one by one into the new tree. The time
>> complexity of these two functions is O(n).
>>
>> The difference between __mt_dup() and mtree_dup() is that mtree_dup()
>> handles locks internally.
>>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> include/linux/maple_tree.h | 3 +
>> lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++
>> 2 files changed, 289 insertions(+)
>>
>> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
>> index 666a3764ed89..de5a4056503a 100644
>> --- a/include/linux/maple_tree.h
>> +++ b/include/linux/maple_tree.h
>> @@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index,
>> void *entry, gfp_t gfp);
>> void *mtree_erase(struct maple_tree *mt, unsigned long index);
>>
>> +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
>> +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
>> +
>> void mtree_destroy(struct maple_tree *mt);
>> void __mt_destroy(struct maple_tree *mt);
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 3fe5652a8c6c..ed8847b4f1ff 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -6370,6 +6370,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
>> }
>> EXPORT_SYMBOL(mtree_erase);
>>
>> +/*
>> + * mas_dup_free() - Free an incomplete duplication of a tree.
>> + * @mas: The maple state of a incomplete tree.
>> + *
>> + * The parameter @mas->node passed in indicates that the allocation failed on
>> + * this node. This function frees all nodes starting from @mas->node in the
>> + * reverse order of mas_dup_build(). There is no need to hold the source tree
>> + * lock at this time.
>> + */
>> +static void mas_dup_free(struct ma_state *mas)
>> +{
>> + struct maple_node *node;
>> + enum maple_type type;
>> + void __rcu **slots;
>> + unsigned char count, i;
>> +
>> + /* Maybe the first node allocation failed. */
>> + if (mas_is_none(mas))
>> + return;
>> +
>> + while (!mte_is_root(mas->node)) {
>> + mas_ascend(mas);
>> +
>> + if (mas->offset) {
>> + mas->offset--;
>> + do {
>> + mas_descend(mas);
>> + mas->offset = mas_data_end(mas);
>> + } while (!mte_is_leaf(mas->node));
>> +
>> + mas_ascend(mas);
>> + }
>> +
>> + node = mte_to_node(mas->node);
>> + type = mte_node_type(mas->node);
>> + slots = ma_slots(node, type);
>> + count = mas_data_end(mas) + 1;
>> + for (i = 0; i < count; i++)
>> + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK;
>> +
>> + mt_free_bulk(count, slots);
>> + }
>> +
>> + node = mte_to_node(mas->node);
>> + mt_free_one(node);
>> +}
>> +
>> +/*
>> + * mas_copy_node() - Copy a maple node and replace the parent.
>> + * @mas: The maple state of source tree.
>> + * @new_mas: The maple state of new tree.
>> + * @parent: The parent of the new node.
>> + *
>> + * Copy @mas->node to @new_mas->node, set @parent to be the parent of
>> + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM.
>> + */
>> +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas,
>> + struct maple_pnode *parent)
>> +{
>> + struct maple_node *node = mte_to_node(mas->node);
>> + struct maple_node *new_node = mte_to_node(new_mas->node);
>> + unsigned long val;
>> +
>> + /* Copy the node completely. */
>> + memcpy(new_node, node, sizeof(struct maple_node));
>> +
>> + /* Update the parent node pointer. */
>> + val = (unsigned long)node->parent & MAPLE_NODE_MASK;
>> + new_node->parent = ma_parent_ptr(val | (unsigned long)parent);
>> +}
>> +
>> +/*
>> + * mas_dup_alloc() - Allocate child nodes for a maple node.
>> + * @mas: The maple state of source tree.
>> + * @new_mas: The maple state of new tree.
>> + * @gfp: The GFP_FLAGS to use for allocations.
>> + *
>> + * This function allocates child nodes for @new_mas->node during the duplication
>> + * process. If memory allocation fails, @mas is set to -ENOMEM.
>> + */
>> +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas,
>> + gfp_t gfp)
>> +{
>> + struct maple_node *node = mte_to_node(mas->node);
>> + struct maple_node *new_node = mte_to_node(new_mas->node);
>> + enum maple_type type;
>> + unsigned char request, count, i;
>> + void __rcu **slots;
>> + void __rcu **new_slots;
>> + unsigned long val;
>> +
>> + /* Allocate memory for child nodes. */
>> + type = mte_node_type(mas->node);
>> + new_slots = ma_slots(new_node, type);
>> + request = mas_data_end(mas) + 1;
>> + count = mt_alloc_bulk(gfp, request, (void **)new_slots);
>> + if (unlikely(count < request)) {
>> + if (count) {
>> + mt_free_bulk(count, new_slots);
>
> If you look at mm/slab.c: kmem_cache_alloc(), you will see that the
> error path already bulk frees for you - but does not zero the array.
> This bulk free will lead to double free, but you do need the below
> memset(). Also, it will return !count or request. So, I think this code
> is never executed as it is written.
If kmem_cache_alloc() is called to allocate memory in mt_alloc_bulk(),
then this code will not be executed because it only returns 0 or
request. However, I am concerned that changes to mt_alloc_bulk() like
[1] may be merged, which could potentially lead to memory leaks. To
improve robustness, I wrote it this way.
How do you think it should be handled? Is it okay to do this like the
code below?
if (unlikely(count < request)) {
memset(new_slots, 0, request * sizeof(unsigned long));
mas_set_err(mas, -ENOMEM);
return;
}
[1] https://lore.kernel.org/lkml/[email protected]/
>
> I don't think this will show up in your testcases because the test code
> doesn't leave dangling pointers and simply returns 0 if there isn't
> enough nodes.
Yes, no testing here.
>
>> + memset(new_slots, 0, count * sizeof(unsigned long));
>> + }
>> + mas_set_err(mas, -ENOMEM);
>> + return;
>> + }
>> +
>> + /* Restore node type information in slots. */
>> + slots = ma_slots(node, type);
>> + for (i = 0; i < count; i++) {
>> + val = (unsigned long)mt_slot_locked(mas->tree, slots, i);
>> + val &= MAPLE_NODE_MASK;
>> + ((unsigned long *)new_slots)[i] |= val;
>> + }
>> +}
>> +
>> +/*
>> + * mas_dup_build() - Build a new maple tree from a source tree
>> + * @mas: The maple state of source tree.
>> + * @new_mas: The maple state of new tree.
>> + * @gfp: The GFP_FLAGS to use for allocations.
>> + *
>> + * This function builds a new tree in DFS preorder. If the memory allocation
>> + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the
>> + * last node. mas_dup_free() will free the incomplete duplication of a tree.
>> + *
>> + * Note that the attributes of the two trees need to be exactly the same, and the
>> + * new tree needs to be empty, otherwise -EINVAL will be set in @mas.
>> + */
>> +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas,
>> + gfp_t gfp)
>> +{
>> + struct maple_node *node;
>> + struct maple_pnode *parent = NULL;
>> + struct maple_enode *root;
>> + enum maple_type type;
>> +
>> + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) ||
>> + unlikely(!mtree_empty(new_mas->tree))) {
>
> Would it be worth checking mas_is_start() for both mas and new_mas here?
> Otherwise mas_start() will not do what you want below. I think it is
> implied that both are at MAS_START but never checked?
This function is an internal function and is currently only called by
{mtree,__mt}_dup(). It is ensured that both 'mas' and 'new_mas' are
MAS_START when called. Do you think we really need to check it? Maybe we
just need to explain it in the comments?
>
>> + mas_set_err(mas, -EINVAL);
>> + return;
>> + }
>> +
>> + mas_start(mas);
>> + if (mas_is_ptr(mas) || mas_is_none(mas)) {
>> + root = mt_root_locked(mas->tree);
>> + goto set_new_tree;
>> + }
>> +
>> + node = mt_alloc_one(gfp);
>> + if (!node) {
>> + new_mas->node = MAS_NONE;
>> + mas_set_err(mas, -ENOMEM);
>> + return;
>> + }
>> +
>> + type = mte_node_type(mas->node);
>> + root = mt_mk_node(node, type);
>> + new_mas->node = root;
>> + new_mas->min = 0;
>> + new_mas->max = ULONG_MAX;
>> + root = mte_mk_root(root);
>> +
>> + while (1) {
>> + mas_copy_node(mas, new_mas, parent);
>> +
>> + if (!mte_is_leaf(mas->node)) {
>> + /* Only allocate child nodes for non-leaf nodes. */
>> + mas_dup_alloc(mas, new_mas, gfp);
>> + if (unlikely(mas_is_err(mas)))
>> + return;
>> + } else {
>> + /*
>> + * This is the last leaf node and duplication is
>> + * completed.
>> + */
>> + if (mas->max == ULONG_MAX)
>> + goto done;
>> +
>> + /* This is not the last leaf node and needs to go up. */
>> + do {
>> + mas_ascend(mas);
>> + mas_ascend(new_mas);
>> + } while (mas->offset == mas_data_end(mas));
>> +
>> + /* Move to the next subtree. */
>> + mas->offset++;
>> + new_mas->offset++;
>> + }
>> +
>> + mas_descend(mas);
>> + parent = ma_parent_ptr(mte_to_node(new_mas->node));
>> + mas_descend(new_mas);
>> + mas->offset = 0;
>> + new_mas->offset = 0;
>> + }
>> +done:
>> + /* Specially handle the parent of the root node. */
>> + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas));
>> +set_new_tree:
>> + /* Make them the same height */
>> + new_mas->tree->ma_flags = mas->tree->ma_flags;
>> + rcu_assign_pointer(new_mas->tree->ma_root, root);
>> +}
>> +
>> +/**
>> + * __mt_dup(): Duplicate a maple tree
>> + * @mt: The source maple tree
>> + * @new: The new maple tree
>> + * @gfp: The GFP_FLAGS to use for allocations
>> + *
>> + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
>> + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
>> + * new child nodes in non-leaf nodes. The new node is exactly the same as the
>> + * source node except for all the addresses stored in it. It will be faster than
>> + * traversing all elements in the source tree and inserting them one by one into
>> + * the new tree.
>> + * The user needs to ensure that the attributes of the source tree and the new
>> + * tree are the same, and the new tree needs to be an empty tree, otherwise
>> + * -EINVAL will be returned.
>> + * Note that the user needs to manually lock the source tree and the new tree.
>> + *
>> + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
>> + * the attributes of the two trees are different or the new tree is not an empty
>> + * tree.
>> + */
>> +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
>> +{
>> + int ret = 0;
>> + MA_STATE(mas, mt, 0, 0);
>> + MA_STATE(new_mas, new, 0, 0);
>> +
>> + mas_dup_build(&mas, &new_mas, gfp);
>> +
>> + if (unlikely(mas_is_err(&mas))) {
>> + ret = xa_err(mas.node);
>> + if (ret == -ENOMEM)
>> + mas_dup_free(&new_mas);
>> + }
>> +
>> + return ret;
>> +}
>> +EXPORT_SYMBOL(__mt_dup);
>> +
>> +/**
>> + * mtree_dup(): Duplicate a maple tree
>> + * @mt: The source maple tree
>> + * @new: The new maple tree
>> + * @gfp: The GFP_FLAGS to use for allocations
>> + *
>> + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
>> + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
>> + * new child nodes in non-leaf nodes. The new node is exactly the same as the
>> + * source node except for all the addresses stored in it. It will be faster than
>> + * traversing all elements in the source tree and inserting them one by one into
>> + * the new tree.
>> + * The user needs to ensure that the attributes of the source tree and the new
>> + * tree are the same, and the new tree needs to be an empty tree, otherwise
>> + * -EINVAL will be returned.
>
> The requirement to duplicate the entire tree should be mentioned and
> maybe the mas_is_start() requirement (as I asked about above?)
Okay, I will add a comment saying 'This duplicates the entire tree'. But
'mas_is_start()' is not a requirement for calling this function because
the function's parameter is 'maple_tree', not 'ma_state'. I think
'mas_is_start()' should be added to the comment for 'mas_dup_build()'.
>
> I can see someone thinking they are going to make a super fast sub-tree
> of existing data using this - which won't (always?) work.
>
>> + *
>> + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
>> + * the attributes of the two trees are different or the new tree is not an empty
>> + * tree.
>> + */
>> +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
>> +{
>> + int ret = 0;
>> + MA_STATE(mas, mt, 0, 0);
>> + MA_STATE(new_mas, new, 0, 0);
>> +
>> + mas_lock(&new_mas);
>> + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
>> +
>> + mas_dup_build(&mas, &new_mas, gfp);
>> + mas_unlock(&mas);
>> +
>> + if (unlikely(mas_is_err(&mas))) {
>> + ret = xa_err(mas.node);
>> + if (ret == -ENOMEM)
>> + mas_dup_free(&new_mas);
>> + }
>> +
>> + mas_unlock(&new_mas);
>> +
>> + return ret;
>> +}
>> +EXPORT_SYMBOL(mtree_dup);
>> +
>> /**
>> * __mt_destroy() - Walk and free all nodes of a locked maple tree.
>> * @mt: The maple tree
>> --
>> 2.20.1
>>
>
在 2023/10/4 02:46, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230924 23:58]:
>> Introduce the new interface mtree_dup() in the documentation.
>>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> Documentation/core-api/maple_tree.rst | 4 ++++
>> 1 file changed, 4 insertions(+)
>>
>> diff --git a/Documentation/core-api/maple_tree.rst b/Documentation/core-api/maple_tree.rst
>> index 45defcf15da7..3d8a1edf6d04 100644
>> --- a/Documentation/core-api/maple_tree.rst
>> +++ b/Documentation/core-api/maple_tree.rst
>> @@ -81,6 +81,9 @@ section.
>> Sometimes it is necessary to ensure the next call to store to a maple tree does
>> not allocate memory, please see :ref:`maple-tree-advanced-api` for this use case.
>>
>> +You can use mtree_dup() to duplicate an identical tree. It is a more efficient
>
> "You can use mtree_dup() to create an identical tree." duplicate an
> identical tree seems redundant.
Okay, I will modify this sentence. Thank you.
>
>> +way than inserting all elements one by one into a new tree.
>> +
>> Finally, you can remove all entries from a maple tree by calling
>> mtree_destroy(). If the maple tree entries are pointers, you may wish to free
>> the entries first.
>> @@ -112,6 +115,7 @@ Takes ma_lock internally:
>> * mtree_insert()
>> * mtree_insert_range()
>> * mtree_erase()
>> + * mtree_dup()
>> * mtree_destroy()
>> * mt_set_in_rcu()
>> * mt_clear_in_rcu()
>> --
>> 2.20.1
>>
>
在 2023/10/4 02:46, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [230924 23:58]:
>> In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
>> directly replacing the entries of VMAs in the new maple tree can result
>> in better performance. __mt_dup() uses DFS pre-order to duplicate the
>> maple tree, so it is very efficient. The average time complexity of
>> duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
>> effect is proportional to the number of VMAs.
>
> I am not confident in the big O calculations here. Although the addition
> of the tree is reduced, adding a VMA still needs to create the nodes
> above it - which are a function of n. How did you get O(n * log(n)) for
> the existing fork?
>
> I would think your new algorithm is n * log(n/16), while the
> previous was n * log(n/16) * f(n). Where f(n) would be something
> to do with the decision to split/rebalance in bulk insert mode.
>
> It's certainly a better algorithm to duplicate trees, but I don't think
> it is O(n). Can you please explain?
The following is a non-professional analysis of the algorithm.
Let's first analyze the average time complexity of the new algorithm, as
it is relatively easy to analyze. The maximum number of branches for
internal nodes in a maple tree in allocation mode is 10. However, to
simplify the analysis, we will not consider this case and assume that
all nodes have a maximum of 16 branches.
The new algorithm assumes that there is no case where a VMA with the
VM_DONTCOPY flag is deleted. If such a case exists, this analysis cannot
be applied.
The operations of the new algorithm consist of three parts:
1. DFS traversal of each node in the source tree
2. For each node in the source tree, create a copy and construct a new
node
3. Traverse the new tree using mas_find() and replace each element
If there are a total of n elements in the maple tree, we can conclude
that there are n/16 leaf nodes. Regarding the second-to-last level, we
can conclude that there are n/16^2 nodes. The total number of nodes in
the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1.
This is a geometric progression with a total of log base 16 of n terms.
According to the formula for the sum of a geometric progression, the sum
is (n-1)/15. So, this tree has a total of (n-1)/15 nodes and
(n-1)/15 - 1 edges.
For the operations in the first part of this algorithm, since DFS
traverses each edge twice, the time complexity would be
2*((n-1)/15 - 1).
For the second part, each operation involves copying a node and making
necessary modifications. Therefore, the time complexity is
16*(n-1)/15.
For the third part, we use mas_find() to traverse and replace each
element, which is essentially similar to the combination of the first
and second parts. mas_find() traverses all nodes and within each node,
it iterates over all elements and performs replacements. The time
complexity of traversing the nodes is 2*((n-1)/15 - 1), and for all
nodes, the time complexity of replacing all their elements is
16*(n-1)/15.
By ignoring all constant factors, each of the three parts of the
algorithm has a time complexity of O(n). Therefore, this new algorithm
is O(n).
The exact time complexity of the old algorithm is difficult to analyze.
I can only provide an upper bound estimation. There are two possible
scenarios for each insertion:
1. Appending at the end of a node.
2. Splitting nodes multiple times.
For the first scenario, the individual operation has a time complexity
of O(1). As for the second scenario, it involves node splitting. The
challenge lies in determining which insertions trigger splits and how
many splits occur each time, which is difficult to calculate. In the
worst-case scenario, each insertion requires splitting the tree's height
log(n) times. Assuming every insertion is in the worst-case scenario,
the time complexity would be n*log(n). However, not every insertion
requires splitting, and the number of splits each time may not
necessarily be log(n). Therefore, this is an estimation of the upper
bound.
>
>>
>> As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
>> fails, there will be a portion of VMAs that have not been duplicated in
>> the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
>> To solve this problem, undo_dup_mmap() is introduced to handle the failure
>> of dup_mmap(). I have carefully tested the failure path and so far it
>> seems there are no issues.
>>
>> There is a "spawn" in byte-unixbench[1], which can be used to test the
>> performance of fork(). I modified it slightly to make it work with
>> different number of VMAs.
>>
>> Below are the test results. By default, there are 21 VMAs. The first row
>> shows the number of additional VMAs added on top of the default. The last
>> two rows show the number of fork() calls per ten seconds. The test results
>> were obtained with CPU binding to avoid scheduler load balancing that
>> could cause unstable results. There are still some fluctuations in the
>> test results, but at least they are better than the original performance.
>>
>> Increment of VMAs: 0 100 200 400 800 1600 3200 6400
>> next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
>> Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
>> +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
>>
>> [1] https://github.com/kdlucas/byte-unixbench/tree/master
>>
>> Signed-off-by: Peng Zhang <[email protected]>
>> ---
>> include/linux/mm.h | 1 +
>> kernel/fork.c | 34 ++++++++++++++++++++----------
>> mm/internal.h | 3 ++-
>> mm/memory.c | 7 ++++---
>> mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
>> 5 files changed, 80 insertions(+), 17 deletions(-)
>>
>> diff --git a/include/linux/mm.h b/include/linux/mm.h
>> index 1f1d0d6b8f20..10c59dc7ffaa 100644
>> --- a/include/linux/mm.h
>> +++ b/include/linux/mm.h
>> @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
>> extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
>> unsigned long addr, unsigned long len, pgoff_t pgoff,
>> bool *need_rmap_locks);
>> +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
>> extern void exit_mmap(struct mm_struct *);
>>
>> static inline int check_data_rlimit(unsigned long rlim,
>> diff --git a/kernel/fork.c b/kernel/fork.c
>> index 7ae36c2e7290..2f3d83e89fe6 100644
>> --- a/kernel/fork.c
>> +++ b/kernel/fork.c
>> @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>> int retval;
>> unsigned long charge = 0;
>> LIST_HEAD(uf);
>> - VMA_ITERATOR(old_vmi, oldmm, 0);
>> VMA_ITERATOR(vmi, mm, 0);
>>
>> uprobe_start_dup_mmap();
>> @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>> goto out;
>> khugepaged_fork(mm, oldmm);
>>
>> - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
>> - if (retval)
>> + /* Use __mt_dup() to efficiently build an identical maple tree. */
>> + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
>> + if (unlikely(retval))
>> goto out;
>>
>> mt_clear_in_rcu(vmi.mas.tree);
>> - for_each_vma(old_vmi, mpnt) {
>> + for_each_vma(vmi, mpnt) {
>> struct file *file;
>>
>> vma_start_write(mpnt);
>> if (mpnt->vm_flags & VM_DONTCOPY) {
>> + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
>> +
>> + /* If failed, undo all completed duplications. */
>> + if (unlikely(mas_is_err(&vmi.mas))) {
>> + retval = xa_err(vmi.mas.node);
>> + goto loop_out;
>> + }
>> +
>> vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
>> continue;
>> }
>> @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>> if (is_vm_hugetlb_page(tmp))
>> hugetlb_dup_vma_private(tmp);
>>
>> - /* Link the vma into the MT */
>> - if (vma_iter_bulk_store(&vmi, tmp))
>> - goto fail_nomem_vmi_store;
>> + /*
>> + * Link the vma into the MT. After using __mt_dup(), memory
>> + * allocation is not necessary here, so it cannot fail.
>> + */
>> + mas_store(&vmi.mas, tmp);
>>
>> mm->map_count++;
>> if (!(tmp->vm_flags & VM_WIPEONFORK))
>> @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>> if (tmp->vm_ops && tmp->vm_ops->open)
>> tmp->vm_ops->open(tmp);
>>
>> - if (retval)
>> + if (retval) {
>> + mpnt = vma_next(&vmi);
>> goto loop_out;
>> + }
>> }
>> /* a new mm has just been created */
>> retval = arch_dup_mmap(oldmm, mm);
>> loop_out:
>> vma_iter_free(&vmi);
>> - if (!retval)
>> + if (likely(!retval))
>> mt_set_in_rcu(vmi.mas.tree);
>> + else
>> + undo_dup_mmap(mm, mpnt);
>> out:
>> mmap_write_unlock(mm);
>> flush_tlb_mm(oldmm);
>> @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>> uprobe_end_dup_mmap();
>> return retval;
>>
>> -fail_nomem_vmi_store:
>> - unlink_anon_vmas(tmp);
>> fail_nomem_anon_vma_fork:
>> mpol_put(vma_policy(tmp));
>> fail_nomem_policy:
>> diff --git a/mm/internal.h b/mm/internal.h
>> index 7a961d12b088..288ec81770cb 100644
>> --- a/mm/internal.h
>> +++ b/mm/internal.h
>> @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
>>
>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>> struct vm_area_struct *start_vma, unsigned long floor,
>> - unsigned long ceiling, bool mm_wr_locked);
>> + unsigned long ceiling, unsigned long tree_end,
>> + bool mm_wr_locked);
>> void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
>>
>> struct zap_details;
>> diff --git a/mm/memory.c b/mm/memory.c
>> index 983a40f8ee62..1fd66a0d5838 100644
>> --- a/mm/memory.c
>> +++ b/mm/memory.c
>> @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
>>
>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>> struct vm_area_struct *vma, unsigned long floor,
>> - unsigned long ceiling, bool mm_wr_locked)
>> + unsigned long ceiling, unsigned long tree_end,
>> + bool mm_wr_locked)
>> {
>> do {
>> unsigned long addr = vma->vm_start;
>> @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>> * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
>> * be 0. This will underflow and is okay.
>> */
>> - next = mas_find(mas, ceiling - 1);
>> + next = mas_find(mas, tree_end - 1);
>>
>> /*
>> * Hide vma from rmap and truncate_pagecache before freeing
>> @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>> while (next && next->vm_start <= vma->vm_end + PMD_SIZE
>> && !is_vm_hugetlb_page(next)) {
>> vma = next;
>> - next = mas_find(mas, ceiling - 1);
>> + next = mas_find(mas, tree_end - 1);
>> if (mm_wr_locked)
>> vma_start_write(vma);
>> unlink_anon_vmas(vma);
>> diff --git a/mm/mmap.c b/mm/mmap.c
>> index 2ad950f773e4..daed3b423124 100644
>> --- a/mm/mmap.c
>> +++ b/mm/mmap.c
>> @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
>> mas_set(mas, mt_start);
>> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
>> next ? next->vm_start : USER_PGTABLES_CEILING,
>> - mm_wr_locked);
>> + tree_end, mm_wr_locked);
>> tlb_finish_mmu(&tlb);
>> }
>>
>> @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
>> }
>> EXPORT_SYMBOL(vm_brk);
>>
>> +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
>> +{
>> + unsigned long tree_end;
>> + VMA_ITERATOR(vmi, mm, 0);
>> + struct vm_area_struct *vma;
>> + unsigned long nr_accounted = 0;
>> + int count = 0;
>> +
>> + /*
>> + * vma_end points to the first VMA that has not been duplicated. We need
>> + * to unmap all VMAs before it.
>> + * If vma_end is NULL, it means that all VMAs in the maple tree have
>> + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
>> + * when using it.
>> + */
>> + if (vma_end) {
>> + tree_end = vma_end->vm_start;
>> + if (tree_end == 0)
>> + goto destroy;
>> + } else
>> + tree_end = 0;
>> +
>> + vma = mas_find(&vmi.mas, tree_end - 1);
>> +
>> + if (vma) {
>> + arch_unmap(mm, vma->vm_start, tree_end);
>> + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
>> + tree_end, true);
>
> next is vma_end, as per your comment above. Using next = vma_end allows
> you to avoid adding another argument to free_pgtables().
Unfortunately, it cannot be done this way. I fell into this trap before,
and it caused incomplete page table cleanup. To solve this problem, the
only solution I can think of right now is to add an additional
parameter.
free_pgtables() will be called in unmap_region() to free the page table,
like this:
free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
next ? next->vm_start : USER_PGTABLES_CEILING,
mm_wr_locked);
The problem is with 'next'. Our 'vma_end' does not exist in the actual
mmap because it has not been duplicated and cannot be used as 'next'.
If there is a real 'next', we can use 'next->vm_start' as the ceiling,
which is not a problem. If there is no 'next' (next is 'vma_end'), we
can only use 'USER_PGTABLES_CEILING' as the ceiling. Using
'vma_end->vm_start' as the ceiling will cause the page table not to be
fully freed, which may be related to alignment in 'free_pgd_range()'. To
solve this problem, we have to introduce 'tree_end', and separating
'tree_end' and 'ceiling' can solve this problem.
>
>> +
>> + mas_set(&vmi.mas, vma->vm_end);
>> + do {
>> + if (vma->vm_flags & VM_ACCOUNT)
>> + nr_accounted += vma_pages(vma);
>> + remove_vma(vma, true);
>> + count++;
>> + cond_resched();
>> + vma = mas_find(&vmi.mas, tree_end - 1);
>> + } while (vma != NULL);
>> +
>> + BUG_ON(count != mm->map_count);
>> +
>> + vm_unacct_memory(nr_accounted);
>> + }
>> +
>> +destroy:
>> + __mt_destroy(&mm->mm_mt);
>> +}
>> +
>> /* Release all mmaps. */
>> void exit_mmap(struct mm_struct *mm)
>> {
>> @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
>> mt_clear_in_rcu(&mm->mm_mt);
>> mas_set(&mas, vma->vm_end);
>> free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
>> - USER_PGTABLES_CEILING, true);
>> + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
>> tlb_finish_mmu(&tlb);
>>
>> /*
>> --
>> 2.20.1
>>
>
* Peng Zhang <[email protected]> [231004 05:09]:
>
>
> 在 2023/10/4 02:45, Liam R. Howlett 写道:
> > * Peng Zhang <[email protected]> [230924 23:58]:
> > > Introduce interfaces __mt_dup() and mtree_dup(), which are used to
> > > duplicate a maple tree. They duplicate a maple tree in Depth-First
> > > Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the
> > > source tree and allocate new child nodes in non-leaf nodes. The new node
> > > is exactly the same as the source node except for all the addresses
> > > stored in it. It will be faster than traversing all elements in the
> > > source tree and inserting them one by one into the new tree. The time
> > > complexity of these two functions is O(n).
> > >
> > > The difference between __mt_dup() and mtree_dup() is that mtree_dup()
> > > handles locks internally.
> > >
> > > Signed-off-by: Peng Zhang <[email protected]>
> > > ---
> > > include/linux/maple_tree.h | 3 +
> > > lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++
> > > 2 files changed, 289 insertions(+)
> > >
> > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> > > index 666a3764ed89..de5a4056503a 100644
> > > --- a/include/linux/maple_tree.h
> > > +++ b/include/linux/maple_tree.h
> > > @@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index,
> > > void *entry, gfp_t gfp);
> > > void *mtree_erase(struct maple_tree *mt, unsigned long index);
> > > +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
> > > +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
> > > +
> > > void mtree_destroy(struct maple_tree *mt);
> > > void __mt_destroy(struct maple_tree *mt);
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 3fe5652a8c6c..ed8847b4f1ff 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -6370,6 +6370,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
> > > }
> > > EXPORT_SYMBOL(mtree_erase);
> > > +/*
> > > + * mas_dup_free() - Free an incomplete duplication of a tree.
> > > + * @mas: The maple state of a incomplete tree.
> > > + *
> > > + * The parameter @mas->node passed in indicates that the allocation failed on
> > > + * this node. This function frees all nodes starting from @mas->node in the
> > > + * reverse order of mas_dup_build(). There is no need to hold the source tree
> > > + * lock at this time.
> > > + */
> > > +static void mas_dup_free(struct ma_state *mas)
> > > +{
> > > + struct maple_node *node;
> > > + enum maple_type type;
> > > + void __rcu **slots;
> > > + unsigned char count, i;
> > > +
> > > + /* Maybe the first node allocation failed. */
> > > + if (mas_is_none(mas))
> > > + return;
> > > +
> > > + while (!mte_is_root(mas->node)) {
> > > + mas_ascend(mas);
> > > +
> > > + if (mas->offset) {
> > > + mas->offset--;
> > > + do {
> > > + mas_descend(mas);
> > > + mas->offset = mas_data_end(mas);
> > > + } while (!mte_is_leaf(mas->node));
> > > +
> > > + mas_ascend(mas);
> > > + }
> > > +
> > > + node = mte_to_node(mas->node);
> > > + type = mte_node_type(mas->node);
> > > + slots = ma_slots(node, type);
> > > + count = mas_data_end(mas) + 1;
> > > + for (i = 0; i < count; i++)
> > > + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK;
> > > +
> > > + mt_free_bulk(count, slots);
> > > + }
> > > +
> > > + node = mte_to_node(mas->node);
> > > + mt_free_one(node);
> > > +}
> > > +
> > > +/*
> > > + * mas_copy_node() - Copy a maple node and replace the parent.
> > > + * @mas: The maple state of source tree.
> > > + * @new_mas: The maple state of new tree.
> > > + * @parent: The parent of the new node.
> > > + *
> > > + * Copy @mas->node to @new_mas->node, set @parent to be the parent of
> > > + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM.
> > > + */
> > > +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas,
> > > + struct maple_pnode *parent)
> > > +{
> > > + struct maple_node *node = mte_to_node(mas->node);
> > > + struct maple_node *new_node = mte_to_node(new_mas->node);
> > > + unsigned long val;
> > > +
> > > + /* Copy the node completely. */
> > > + memcpy(new_node, node, sizeof(struct maple_node));
> > > +
> > > + /* Update the parent node pointer. */
> > > + val = (unsigned long)node->parent & MAPLE_NODE_MASK;
> > > + new_node->parent = ma_parent_ptr(val | (unsigned long)parent);
> > > +}
> > > +
> > > +/*
> > > + * mas_dup_alloc() - Allocate child nodes for a maple node.
> > > + * @mas: The maple state of source tree.
> > > + * @new_mas: The maple state of new tree.
> > > + * @gfp: The GFP_FLAGS to use for allocations.
> > > + *
> > > + * This function allocates child nodes for @new_mas->node during the duplication
> > > + * process. If memory allocation fails, @mas is set to -ENOMEM.
> > > + */
> > > +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas,
> > > + gfp_t gfp)
> > > +{
> > > + struct maple_node *node = mte_to_node(mas->node);
> > > + struct maple_node *new_node = mte_to_node(new_mas->node);
> > > + enum maple_type type;
> > > + unsigned char request, count, i;
> > > + void __rcu **slots;
> > > + void __rcu **new_slots;
> > > + unsigned long val;
> > > +
> > > + /* Allocate memory for child nodes. */
> > > + type = mte_node_type(mas->node);
> > > + new_slots = ma_slots(new_node, type);
> > > + request = mas_data_end(mas) + 1;
> > > + count = mt_alloc_bulk(gfp, request, (void **)new_slots);
> > > + if (unlikely(count < request)) {
> > > + if (count) {
> > > + mt_free_bulk(count, new_slots);
> >
> > If you look at mm/slab.c: kmem_cache_alloc(), you will see that the
> > error path already bulk frees for you - but does not zero the array.
> > This bulk free will lead to double free, but you do need the below
> > memset(). Also, it will return !count or request. So, I think this code
> > is never executed as it is written.
> If kmem_cache_alloc() is called to allocate memory in mt_alloc_bulk(),
> then this code will not be executed because it only returns 0 or
> request. However, I am concerned that changes to mt_alloc_bulk() like
> [1] may be merged, which could potentially lead to memory leaks. To
> improve robustness, I wrote it this way.
>
> How do you think it should be handled? Is it okay to do this like the
> code below?
>
> if (unlikely(count < request)) {
> memset(new_slots, 0, request * sizeof(unsigned long));
> mas_set_err(mas, -ENOMEM);
> return;
> }
>
> [1] https://lore.kernel.org/lkml/[email protected]/
Ah, I see.
We should keep the same functionality as before. The code you are
referencing is an RFC and won't be merged as-is. We should be sure to
keep an eye on this happening.
I think the code you have there is correct.
> >
> > I don't think this will show up in your testcases because the test code
> > doesn't leave dangling pointers and simply returns 0 if there isn't
> > enough nodes.
> Yes, no testing here.
Yeah :/ I think we should update the test code at some point to behave
the same as the real code. Don't worry about it here though.
> >
> > > + memset(new_slots, 0, count * sizeof(unsigned long));
> > > + }
> > > + mas_set_err(mas, -ENOMEM);
> > > + return;
> > > + }
> > > +
> > > + /* Restore node type information in slots. */
> > > + slots = ma_slots(node, type);
> > > + for (i = 0; i < count; i++) {
> > > + val = (unsigned long)mt_slot_locked(mas->tree, slots, i);
> > > + val &= MAPLE_NODE_MASK;
> > > + ((unsigned long *)new_slots)[i] |= val;
> > > + }
> > > +}
> > > +
> > > +/*
> > > + * mas_dup_build() - Build a new maple tree from a source tree
> > > + * @mas: The maple state of source tree.
> > > + * @new_mas: The maple state of new tree.
> > > + * @gfp: The GFP_FLAGS to use for allocations.
> > > + *
> > > + * This function builds a new tree in DFS preorder. If the memory allocation
> > > + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the
> > > + * last node. mas_dup_free() will free the incomplete duplication of a tree.
> > > + *
> > > + * Note that the attributes of the two trees need to be exactly the same, and the
> > > + * new tree needs to be empty, otherwise -EINVAL will be set in @mas.
> > > + */
> > > +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas,
> > > + gfp_t gfp)
> > > +{
> > > + struct maple_node *node;
> > > + struct maple_pnode *parent = NULL;
> > > + struct maple_enode *root;
> > > + enum maple_type type;
> > > +
> > > + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) ||
> > > + unlikely(!mtree_empty(new_mas->tree))) {
> >
> > Would it be worth checking mas_is_start() for both mas and new_mas here?
> > Otherwise mas_start() will not do what you want below. I think it is
> > implied that both are at MAS_START but never checked?
> This function is an internal function and is currently only called by
> {mtree,__mt}_dup(). It is ensured that both 'mas' and 'new_mas' are
> MAS_START when called. Do you think we really need to check it? Maybe we
> just need to explain it in the comments?
Yes, just document that it is expected to be MAS_START.
> >
> > > + mas_set_err(mas, -EINVAL);
> > > + return;
> > > + }
> > > +
> > > + mas_start(mas);
> > > + if (mas_is_ptr(mas) || mas_is_none(mas)) {
> > > + root = mt_root_locked(mas->tree);
> > > + goto set_new_tree;
> > > + }
> > > +
> > > + node = mt_alloc_one(gfp);
> > > + if (!node) {
> > > + new_mas->node = MAS_NONE;
> > > + mas_set_err(mas, -ENOMEM);
> > > + return;
> > > + }
> > > +
> > > + type = mte_node_type(mas->node);
> > > + root = mt_mk_node(node, type);
> > > + new_mas->node = root;
> > > + new_mas->min = 0;
> > > + new_mas->max = ULONG_MAX;
> > > + root = mte_mk_root(root);
> > > +
> > > + while (1) {
> > > + mas_copy_node(mas, new_mas, parent);
> > > +
> > > + if (!mte_is_leaf(mas->node)) {
> > > + /* Only allocate child nodes for non-leaf nodes. */
> > > + mas_dup_alloc(mas, new_mas, gfp);
> > > + if (unlikely(mas_is_err(mas)))
> > > + return;
> > > + } else {
> > > + /*
> > > + * This is the last leaf node and duplication is
> > > + * completed.
> > > + */
> > > + if (mas->max == ULONG_MAX)
> > > + goto done;
> > > +
> > > + /* This is not the last leaf node and needs to go up. */
> > > + do {
> > > + mas_ascend(mas);
> > > + mas_ascend(new_mas);
> > > + } while (mas->offset == mas_data_end(mas));
> > > +
> > > + /* Move to the next subtree. */
> > > + mas->offset++;
> > > + new_mas->offset++;
> > > + }
> > > +
> > > + mas_descend(mas);
> > > + parent = ma_parent_ptr(mte_to_node(new_mas->node));
> > > + mas_descend(new_mas);
> > > + mas->offset = 0;
> > > + new_mas->offset = 0;
> > > + }
> > > +done:
> > > + /* Specially handle the parent of the root node. */
> > > + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas));
> > > +set_new_tree:
> > > + /* Make them the same height */
> > > + new_mas->tree->ma_flags = mas->tree->ma_flags;
> > > + rcu_assign_pointer(new_mas->tree->ma_root, root);
> > > +}
> > > +
> > > +/**
> > > + * __mt_dup(): Duplicate a maple tree
> > > + * @mt: The source maple tree
> > > + * @new: The new maple tree
> > > + * @gfp: The GFP_FLAGS to use for allocations
> > > + *
> > > + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
> > > + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
> > > + * new child nodes in non-leaf nodes. The new node is exactly the same as the
> > > + * source node except for all the addresses stored in it. It will be faster than
> > > + * traversing all elements in the source tree and inserting them one by one into
> > > + * the new tree.
> > > + * The user needs to ensure that the attributes of the source tree and the new
> > > + * tree are the same, and the new tree needs to be an empty tree, otherwise
> > > + * -EINVAL will be returned.
> > > + * Note that the user needs to manually lock the source tree and the new tree.
> > > + *
> > > + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
> > > + * the attributes of the two trees are different or the new tree is not an empty
> > > + * tree.
> > > + */
> > > +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
> > > +{
> > > + int ret = 0;
> > > + MA_STATE(mas, mt, 0, 0);
> > > + MA_STATE(new_mas, new, 0, 0);
> > > +
> > > + mas_dup_build(&mas, &new_mas, gfp);
> > > +
> > > + if (unlikely(mas_is_err(&mas))) {
> > > + ret = xa_err(mas.node);
> > > + if (ret == -ENOMEM)
> > > + mas_dup_free(&new_mas);
> > > + }
> > > +
> > > + return ret;
> > > +}
> > > +EXPORT_SYMBOL(__mt_dup);
> > > +
> > > +/**
> > > + * mtree_dup(): Duplicate a maple tree
> > > + * @mt: The source maple tree
> > > + * @new: The new maple tree
> > > + * @gfp: The GFP_FLAGS to use for allocations
> > > + *
> > > + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
> > > + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
> > > + * new child nodes in non-leaf nodes. The new node is exactly the same as the
> > > + * source node except for all the addresses stored in it. It will be faster than
> > > + * traversing all elements in the source tree and inserting them one by one into
> > > + * the new tree.
> > > + * The user needs to ensure that the attributes of the source tree and the new
> > > + * tree are the same, and the new tree needs to be an empty tree, otherwise
> > > + * -EINVAL will be returned.
> >
> > The requirement to duplicate the entire tree should be mentioned and
> > maybe the mas_is_start() requirement (as I asked about above?)
> Okay, I will add a comment saying 'This duplicates the entire tree'. But
> 'mas_is_start()' is not a requirement for calling this function because
> the function's parameter is 'maple_tree', not 'ma_state'. I think
> 'mas_is_start()' should be added to the comment for 'mas_dup_build()'.
Oh right, thanks.
> >
> > I can see someone thinking they are going to make a super fast sub-tree
> > of existing data using this - which won't (always?) work.
> >
> > > + *
> > > + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
> > > + * the attributes of the two trees are different or the new tree is not an empty
> > > + * tree.
> > > + */
> > > +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
> > > +{
> > > + int ret = 0;
> > > + MA_STATE(mas, mt, 0, 0);
> > > + MA_STATE(new_mas, new, 0, 0);
> > > +
> > > + mas_lock(&new_mas);
> > > + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
> > > +
> > > + mas_dup_build(&mas, &new_mas, gfp);
> > > + mas_unlock(&mas);
> > > +
> > > + if (unlikely(mas_is_err(&mas))) {
> > > + ret = xa_err(mas.node);
> > > + if (ret == -ENOMEM)
> > > + mas_dup_free(&new_mas);
> > > + }
> > > +
> > > + mas_unlock(&new_mas);
> > > +
> > > + return ret;
> > > +}
> > > +EXPORT_SYMBOL(mtree_dup);
> > > +
> > > /**
> > > * __mt_destroy() - Walk and free all nodes of a locked maple tree.
> > > * @mt: The maple tree
> > > --
> > > 2.20.1
> > >
> >
* Peng Zhang <[email protected]> [231004 05:10]:
>
>
> 在 2023/10/4 02:46, Liam R. Howlett 写道:
> > * Peng Zhang <[email protected]> [230924 23:58]:
> > > In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
> > > directly replacing the entries of VMAs in the new maple tree can result
> > > in better performance. __mt_dup() uses DFS pre-order to duplicate the
> > > maple tree, so it is very efficient. The average time complexity of
> > > duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
> > > effect is proportional to the number of VMAs.
> >
> > I am not confident in the big O calculations here. Although the addition
> > of the tree is reduced, adding a VMA still needs to create the nodes
> > above it - which are a function of n. How did you get O(n * log(n)) for
> > the existing fork?
> >
> > I would think your new algorithm is n * log(n/16), while the
> > previous was n * log(n/16) * f(n). Where f(n) would be something
> > to do with the decision to split/rebalance in bulk insert mode.
> >
> > It's certainly a better algorithm to duplicate trees, but I don't think
> > it is O(n). Can you please explain?
>
> The following is a non-professional analysis of the algorithm.
>
> Let's first analyze the average time complexity of the new algorithm, as
> it is relatively easy to analyze. The maximum number of branches for
> internal nodes in a maple tree in allocation mode is 10. However, to
> simplify the analysis, we will not consider this case and assume that
> all nodes have a maximum of 16 branches.
>
> The new algorithm assumes that there is no case where a VMA with the
> VM_DONTCOPY flag is deleted. If such a case exists, this analysis cannot
> be applied.
>
> The operations of the new algorithm consist of three parts:
>
> 1. DFS traversal of each node in the source tree
> 2. For each node in the source tree, create a copy and construct a new
> node
> 3. Traverse the new tree using mas_find() and replace each element
>
> If there are a total of n elements in the maple tree, we can conclude
> that there are n/16 leaf nodes. Regarding the second-to-last level, we
> can conclude that there are n/16^2 nodes. The total number of nodes in
> the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1.
> This is a geometric progression with a total of log base 16 of n terms.
> According to the formula for the sum of a geometric progression, the sum
> is (n-1)/15. So, this tree has a total of (n-1)/15 nodes and
> (n-1)/15 - 1 edges.
>
> For the operations in the first part of this algorithm, since DFS
> traverses each edge twice, the time complexity would be
> 2*((n-1)/15 - 1).
>
> For the second part, each operation involves copying a node and making
> necessary modifications. Therefore, the time complexity is
> 16*(n-1)/15.
>
> For the third part, we use mas_find() to traverse and replace each
> element, which is essentially similar to the combination of the first
> and second parts. mas_find() traverses all nodes and within each node,
> it iterates over all elements and performs replacements. The time
> complexity of traversing the nodes is 2*((n-1)/15 - 1), and for all
> nodes, the time complexity of replacing all their elements is
> 16*(n-1)/15.
>
> By ignoring all constant factors, each of the three parts of the
> algorithm has a time complexity of O(n). Therefore, this new algorithm
> is O(n).
Thanks for the detailed analysis! I didn't mean to cause so much work
with this question. I wanted to know so that future work could rely on
this calculation to demonstrate if it is worth implementing without
going through the effort of coding and benchmarking - after all, this
commit message will most likely be examined during that process.
I asked because O(n) vs O(n*log(n)) doesn't seem to fit with your
benchmarking.
>
> The exact time complexity of the old algorithm is difficult to analyze.
> I can only provide an upper bound estimation. There are two possible
> scenarios for each insertion:
>
> 1. Appending at the end of a node.
> 2. Splitting nodes multiple times.
>
> For the first scenario, the individual operation has a time complexity
> of O(1). As for the second scenario, it involves node splitting. The
> challenge lies in determining which insertions trigger splits and how
> many splits occur each time, which is difficult to calculate. In the
> worst-case scenario, each insertion requires splitting the tree's height
> log(n) times. Assuming every insertion is in the worst-case scenario,
> the time complexity would be n*log(n). However, not every insertion
> requires splitting, and the number of splits each time may not
> necessarily be log(n). Therefore, this is an estimation of the upper
> bound.
Saying every insert causes a split and adding in n*log(n) is more than
an over estimation. At worst there is some n + n/16 * log(n) going on
there.
During the building of a tree, we are in bulk insert mode. This favours
balancing the tree to the left to maximize the number of inserts being
append operations. The algorithm inserts as many to the left as we can
leaving the minimum number on the right.
We also reduce the number of splits by pushing data to the left whenever
possible, at every level.
> >
> > >
> > > As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
> > > fails, there will be a portion of VMAs that have not been duplicated in
> > > the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
> > > To solve this problem, undo_dup_mmap() is introduced to handle the failure
> > > of dup_mmap(). I have carefully tested the failure path and so far it
> > > seems there are no issues.
> > >
> > > There is a "spawn" in byte-unixbench[1], which can be used to test the
> > > performance of fork(). I modified it slightly to make it work with
> > > different number of VMAs.
> > >
> > > Below are the test results. By default, there are 21 VMAs. The first row
> > > shows the number of additional VMAs added on top of the default. The last
> > > two rows show the number of fork() calls per ten seconds. The test results
> > > were obtained with CPU binding to avoid scheduler load balancing that
> > > could cause unstable results. There are still some fluctuations in the
> > > test results, but at least they are better than the original performance.
> > >
> > > Increment of VMAs: 0 100 200 400 800 1600 3200 6400
> > > next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
> > > Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
> > > +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
delta 4179 10502 12592 11461 8972 5310 2935 1622
Looking at this data, it is difficult to see what is going on because
there is a doubling of the VMAs per fork per column while the count is
forks per 10 seconds. So this table is really a logarithmic table with
increases growing by 10%. Adding the delta row makes it seem like the
number are not growing apart as I would expect.
If we normalize this to VMAs per second by dividing the forks by 10,
then multiplying by the number of VMAs we get this:
VMA Count: 21 121 221 421 821 1621 3221 6421
log(VMA) 1.32 2.00 2.30 2.60 2.90 3.20 3.36 3.81
next-20230921: 258349.8 928268.7 1215996.7 1464383.7 1707725.0 1842916.5 1420514.5 2044440.9
this: 267961.5 1057443.3 1496798.3 1949184.0 2446120.6 2704729.5 2102315.0 3086251.5
delta 9611.7 129174.6 280801.6 484800.3 738395.6 861813.0 681800.5 1041810.6
The first thing that I noticed was that we hit some dip in the numbers
at 3221. I first thought that might be something else running on the
host machine, but both runs are affected by around the same percent.
Here, we do see the delta growing apart, but peaking in growth around
821 VMAs. Again that 3221 number is out of line.
If we discard 21 and anything above 1621, we still see both lines are
asymptotic curves. I would expect that the new algorithm would be more
linear to represent O(n), but there is certainly a curve when graphed
with a normalized X-axis. The older algorithm, O(n*log(n)) should be
the opposite curve all together, and with a diminishing return, but it
seems the more elements we have, the more operations we can perform in a
second.
Thinking about what is going on here, I cannot come up with a reason
that there would be a curve to the line at all. If we took more
measurements, I would think the samples would be an ever-increasing line
with variability for some function of 16 - a saw toothed increasing
line. At least, until an upper limit is reached. We can see that the
upper limit was still not achieved at 1621 since 6421 is higher for both
runs, but a curve is evident on both methods, which suggests something
else is a significant contributor.
I would think each VMA requires the same amount of work, so a constant.
The allocations would again, be some function that would linearly
increase with the existing method over-estimating by a huge number of
nodes.
I'm not trying to nitpick here, but it is important to be accurate in
the statements because it may alter choices on how to proceed in
improving this performance later. It may be others looking through
these commit messages to see if something can be improved.
I also feel like your notes on your algorithm are worth including in the
commit because it could prove rather valuable if we revisit forking in
the future.
The more I look at this, the more questions I have that I cannot answer.
One thing we can see is that the new method is faster in this
micro-benchmark.
> > >
> > > [1] https://github.com/kdlucas/byte-unixbench/tree/master
> > >
> > > Signed-off-by: Peng Zhang <[email protected]>
> > > ---
> > > include/linux/mm.h | 1 +
> > > kernel/fork.c | 34 ++++++++++++++++++++----------
> > > mm/internal.h | 3 ++-
> > > mm/memory.c | 7 ++++---
> > > mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
> > > 5 files changed, 80 insertions(+), 17 deletions(-)
> > >
> > > diff --git a/include/linux/mm.h b/include/linux/mm.h
> > > index 1f1d0d6b8f20..10c59dc7ffaa 100644
> > > --- a/include/linux/mm.h
> > > +++ b/include/linux/mm.h
> > > @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
> > > extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
> > > unsigned long addr, unsigned long len, pgoff_t pgoff,
> > > bool *need_rmap_locks);
> > > +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
> > > extern void exit_mmap(struct mm_struct *);
> > > static inline int check_data_rlimit(unsigned long rlim,
> > > diff --git a/kernel/fork.c b/kernel/fork.c
> > > index 7ae36c2e7290..2f3d83e89fe6 100644
> > > --- a/kernel/fork.c
> > > +++ b/kernel/fork.c
> > > @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > int retval;
> > > unsigned long charge = 0;
> > > LIST_HEAD(uf);
> > > - VMA_ITERATOR(old_vmi, oldmm, 0);
> > > VMA_ITERATOR(vmi, mm, 0);
> > > uprobe_start_dup_mmap();
> > > @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > goto out;
> > > khugepaged_fork(mm, oldmm);
> > > - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
> > > - if (retval)
> > > + /* Use __mt_dup() to efficiently build an identical maple tree. */
> > > + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
> > > + if (unlikely(retval))
> > > goto out;
> > > mt_clear_in_rcu(vmi.mas.tree);
> > > - for_each_vma(old_vmi, mpnt) {
> > > + for_each_vma(vmi, mpnt) {
> > > struct file *file;
> > > vma_start_write(mpnt);
> > > if (mpnt->vm_flags & VM_DONTCOPY) {
> > > + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
> > > +
> > > + /* If failed, undo all completed duplications. */
> > > + if (unlikely(mas_is_err(&vmi.mas))) {
> > > + retval = xa_err(vmi.mas.node);
> > > + goto loop_out;
> > > + }
> > > +
> > > vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
> > > continue;
> > > }
> > > @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > if (is_vm_hugetlb_page(tmp))
> > > hugetlb_dup_vma_private(tmp);
> > > - /* Link the vma into the MT */
> > > - if (vma_iter_bulk_store(&vmi, tmp))
> > > - goto fail_nomem_vmi_store;
> > > + /*
> > > + * Link the vma into the MT. After using __mt_dup(), memory
> > > + * allocation is not necessary here, so it cannot fail.
> > > + */
> > > + mas_store(&vmi.mas, tmp);
> > > mm->map_count++;
> > > if (!(tmp->vm_flags & VM_WIPEONFORK))
> > > @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > if (tmp->vm_ops && tmp->vm_ops->open)
> > > tmp->vm_ops->open(tmp);
> > > - if (retval)
> > > + if (retval) {
> > > + mpnt = vma_next(&vmi);
> > > goto loop_out;
> > > + }
> > > }
> > > /* a new mm has just been created */
> > > retval = arch_dup_mmap(oldmm, mm);
> > > loop_out:
> > > vma_iter_free(&vmi);
> > > - if (!retval)
> > > + if (likely(!retval))
> > > mt_set_in_rcu(vmi.mas.tree);
> > > + else
> > > + undo_dup_mmap(mm, mpnt);
> > > out:
> > > mmap_write_unlock(mm);
> > > flush_tlb_mm(oldmm);
> > > @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > uprobe_end_dup_mmap();
> > > return retval;
> > > -fail_nomem_vmi_store:
> > > - unlink_anon_vmas(tmp);
> > > fail_nomem_anon_vma_fork:
> > > mpol_put(vma_policy(tmp));
> > > fail_nomem_policy:
> > > diff --git a/mm/internal.h b/mm/internal.h
> > > index 7a961d12b088..288ec81770cb 100644
> > > --- a/mm/internal.h
> > > +++ b/mm/internal.h
> > > @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
> > > void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > struct vm_area_struct *start_vma, unsigned long floor,
> > > - unsigned long ceiling, bool mm_wr_locked);
> > > + unsigned long ceiling, unsigned long tree_end,
> > > + bool mm_wr_locked);
> > > void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
> > > struct zap_details;
> > > diff --git a/mm/memory.c b/mm/memory.c
> > > index 983a40f8ee62..1fd66a0d5838 100644
> > > --- a/mm/memory.c
> > > +++ b/mm/memory.c
> > > @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
> > > void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > struct vm_area_struct *vma, unsigned long floor,
> > > - unsigned long ceiling, bool mm_wr_locked)
> > > + unsigned long ceiling, unsigned long tree_end,
> > > + bool mm_wr_locked)
> > > {
> > > do {
> > > unsigned long addr = vma->vm_start;
> > > @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
> > > * be 0. This will underflow and is okay.
> > > */
> > > - next = mas_find(mas, ceiling - 1);
> > > + next = mas_find(mas, tree_end - 1);
> > > /*
> > > * Hide vma from rmap and truncate_pagecache before freeing
> > > @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > while (next && next->vm_start <= vma->vm_end + PMD_SIZE
> > > && !is_vm_hugetlb_page(next)) {
> > > vma = next;
> > > - next = mas_find(mas, ceiling - 1);
> > > + next = mas_find(mas, tree_end - 1);
> > > if (mm_wr_locked)
> > > vma_start_write(vma);
> > > unlink_anon_vmas(vma);
> > > diff --git a/mm/mmap.c b/mm/mmap.c
> > > index 2ad950f773e4..daed3b423124 100644
> > > --- a/mm/mmap.c
> > > +++ b/mm/mmap.c
> > > @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
> > > mas_set(mas, mt_start);
> > > free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
> > > next ? next->vm_start : USER_PGTABLES_CEILING,
> > > - mm_wr_locked);
> > > + tree_end, mm_wr_locked);
> > > tlb_finish_mmu(&tlb);
> > > }
> > > @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
> > > }
> > > EXPORT_SYMBOL(vm_brk);
> > > +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
> > > +{
> > > + unsigned long tree_end;
> > > + VMA_ITERATOR(vmi, mm, 0);
> > > + struct vm_area_struct *vma;
> > > + unsigned long nr_accounted = 0;
> > > + int count = 0;
> > > +
> > > + /*
> > > + * vma_end points to the first VMA that has not been duplicated. We need
> > > + * to unmap all VMAs before it.
> > > + * If vma_end is NULL, it means that all VMAs in the maple tree have
> > > + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
> > > + * when using it.
> > > + */
> > > + if (vma_end) {
> > > + tree_end = vma_end->vm_start;
> > > + if (tree_end == 0)
> > > + goto destroy;
> > > + } else
> > > + tree_end = 0;
> > > +
> > > + vma = mas_find(&vmi.mas, tree_end - 1);
> > > +
> > > + if (vma) {
> > > + arch_unmap(mm, vma->vm_start, tree_end);
> > > + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
> > > + tree_end, true);
> >
> > next is vma_end, as per your comment above. Using next = vma_end allows
> > you to avoid adding another argument to free_pgtables().
> Unfortunately, it cannot be done this way. I fell into this trap before,
> and it caused incomplete page table cleanup. To solve this problem, the
> only solution I can think of right now is to add an additional
> parameter.
>
> free_pgtables() will be called in unmap_region() to free the page table,
> like this:
>
> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
> next ? next->vm_start : USER_PGTABLES_CEILING,
> mm_wr_locked);
>
> The problem is with 'next'. Our 'vma_end' does not exist in the actual
> mmap because it has not been duplicated and cannot be used as 'next'.
> If there is a real 'next', we can use 'next->vm_start' as the ceiling,
> which is not a problem. If there is no 'next' (next is 'vma_end'), we
> can only use 'USER_PGTABLES_CEILING' as the ceiling. Using
> 'vma_end->vm_start' as the ceiling will cause the page table not to be
> fully freed, which may be related to alignment in 'free_pgd_range()'. To
> solve this problem, we have to introduce 'tree_end', and separating
> 'tree_end' and 'ceiling' can solve this problem.
Can you just use ceiling? That is, just not pass in next and keep the
code as-is? This is how exit_mmap() does it and should avoid any
alignment issues. I assume you tried that and something went wrong as
well?
>
> >
> > > +
> > > + mas_set(&vmi.mas, vma->vm_end);
> > > + do {
> > > + if (vma->vm_flags & VM_ACCOUNT)
> > > + nr_accounted += vma_pages(vma);
> > > + remove_vma(vma, true);
> > > + count++;
> > > + cond_resched();
> > > + vma = mas_find(&vmi.mas, tree_end - 1);
> > > + } while (vma != NULL);
> > > +
> > > + BUG_ON(count != mm->map_count);
> > > +
> > > + vm_unacct_memory(nr_accounted);
> > > + }
> > > +
> > > +destroy:
> > > + __mt_destroy(&mm->mm_mt);
> > > +}
> > > +
> > > /* Release all mmaps. */
> > > void exit_mmap(struct mm_struct *mm)
> > > {
> > > @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
> > > mt_clear_in_rcu(&mm->mm_mt);
> > > mas_set(&mas, vma->vm_end);
> > > free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
> > > - USER_PGTABLES_CEILING, true);
> > > + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
> > > tlb_finish_mmu(&tlb);
> > > /*
> > > --
> > > 2.20.1
> > >
> >
>
在 2023/10/5 03:53, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [231004 05:10]:
>>
>>
>> 在 2023/10/4 02:46, Liam R. Howlett 写道:
>>> * Peng Zhang <[email protected]> [230924 23:58]:
>>>> In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
>>>> directly replacing the entries of VMAs in the new maple tree can result
>>>> in better performance. __mt_dup() uses DFS pre-order to duplicate the
>>>> maple tree, so it is very efficient. The average time complexity of
>>>> duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
>>>> effect is proportional to the number of VMAs.
>>>
>>> I am not confident in the big O calculations here. Although the addition
>>> of the tree is reduced, adding a VMA still needs to create the nodes
>>> above it - which are a function of n. How did you get O(n * log(n)) for
>>> the existing fork?
>>>
>>> I would think your new algorithm is n * log(n/16), while the
>>> previous was n * log(n/16) * f(n). Where f(n) would be something
>>> to do with the decision to split/rebalance in bulk insert mode.
>>>
>>> It's certainly a better algorithm to duplicate trees, but I don't think
>>> it is O(n). Can you please explain?
>>
>> The following is a non-professional analysis of the algorithm.
>>
>> Let's first analyze the average time complexity of the new algorithm, as
>> it is relatively easy to analyze. The maximum number of branches for
>> internal nodes in a maple tree in allocation mode is 10. However, to
>> simplify the analysis, we will not consider this case and assume that
>> all nodes have a maximum of 16 branches.
>>
>> The new algorithm assumes that there is no case where a VMA with the
>> VM_DONTCOPY flag is deleted. If such a case exists, this analysis cannot
>> be applied.
>>
>> The operations of the new algorithm consist of three parts:
>>
>> 1. DFS traversal of each node in the source tree
>> 2. For each node in the source tree, create a copy and construct a new
>> node
>> 3. Traverse the new tree using mas_find() and replace each element
>>
>> If there are a total of n elements in the maple tree, we can conclude
>> that there are n/16 leaf nodes. Regarding the second-to-last level, we
>> can conclude that there are n/16^2 nodes. The total number of nodes in
>> the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1.
>> This is a geometric progression with a total of log base 16 of n terms.
>> According to the formula for the sum of a geometric progression, the sum
>> is (n-1)/15. So, this tree has a total of (n-1)/15 nodes and
>> (n-1)/15 - 1 edges.
>>
>> For the operations in the first part of this algorithm, since DFS
>> traverses each edge twice, the time complexity would be
>> 2*((n-1)/15 - 1).
>>
>> For the second part, each operation involves copying a node and making
>> necessary modifications. Therefore, the time complexity is
>> 16*(n-1)/15.
>>
>> For the third part, we use mas_find() to traverse and replace each
>> element, which is essentially similar to the combination of the first
>> and second parts. mas_find() traverses all nodes and within each node,
>> it iterates over all elements and performs replacements. The time
>> complexity of traversing the nodes is 2*((n-1)/15 - 1), and for all
>> nodes, the time complexity of replacing all their elements is
>> 16*(n-1)/15.
>>
>> By ignoring all constant factors, each of the three parts of the
>> algorithm has a time complexity of O(n). Therefore, this new algorithm
>> is O(n).
>
> Thanks for the detailed analysis! I didn't mean to cause so much work
> with this question. I wanted to know so that future work could rely on
> this calculation to demonstrate if it is worth implementing without
> going through the effort of coding and benchmarking - after all, this
> commit message will most likely be examined during that process.
>
> I asked because O(n) vs O(n*log(n)) doesn't seem to fit with your
> benchmarking.
It may not be well reflected in the benchmarking of fork() because all
the aforementioned time complexity analysis is related to the part
involving the maple tree, specifically the time complexity of
constructing a new maple tree. However, fork() also includes many other
behaviors.
>
>>
>> The exact time complexity of the old algorithm is difficult to analyze.
>> I can only provide an upper bound estimation. There are two possible
>> scenarios for each insertion:
>>
>> 1. Appending at the end of a node.
>> 2. Splitting nodes multiple times.
>>
>> For the first scenario, the individual operation has a time complexity
>> of O(1). As for the second scenario, it involves node splitting. The
>> challenge lies in determining which insertions trigger splits and how
>> many splits occur each time, which is difficult to calculate. In the
>> worst-case scenario, each insertion requires splitting the tree's height
>> log(n) times. Assuming every insertion is in the worst-case scenario,
>> the time complexity would be n*log(n). However, not every insertion
>> requires splitting, and the number of splits each time may not
>> necessarily be log(n). Therefore, this is an estimation of the upper
>> bound.
>
> Saying every insert causes a split and adding in n*log(n) is more than
> an over estimation. At worst there is some n + n/16 * log(n) going on
> there.
>
> During the building of a tree, we are in bulk insert mode. This favours
> balancing the tree to the left to maximize the number of inserts being
> append operations. The algorithm inserts as many to the left as we can
> leaving the minimum number on the right.
>
> We also reduce the number of splits by pushing data to the left whenever
> possible, at every level.
Yes, but I don't think pushing data would occur when inserting in
ascending order in bulk mode because the left nodes are all full, while
there are no nodes on the right side. However, I'm not entirely certain
about this since I only briefly looked at the implementation of this
part.
>
>
>>>
>>>>
>>>> As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
>>>> fails, there will be a portion of VMAs that have not been duplicated in
>>>> the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
>>>> To solve this problem, undo_dup_mmap() is introduced to handle the failure
>>>> of dup_mmap(). I have carefully tested the failure path and so far it
>>>> seems there are no issues.
>>>>
>>>> There is a "spawn" in byte-unixbench[1], which can be used to test the
>>>> performance of fork(). I modified it slightly to make it work with
>>>> different number of VMAs.
>>>>
>>>> Below are the test results. By default, there are 21 VMAs. The first row
>>>> shows the number of additional VMAs added on top of the default. The last
>>>> two rows show the number of fork() calls per ten seconds. The test results
>>>> were obtained with CPU binding to avoid scheduler load balancing that
>>>> could cause unstable results. There are still some fluctuations in the
>>>> test results, but at least they are better than the original performance.
>>>>
>>>> Increment of VMAs: 0 100 200 400 800 1600 3200 6400
>>>> next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
>>>> Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
>>>> +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
> delta 4179 10502 12592 11461 8972 5310 2935 1622
>
> Looking at this data, it is difficult to see what is going on because
> there is a doubling of the VMAs per fork per column while the count is
> forks per 10 seconds. So this table is really a logarithmic table with
> increases growing by 10%. Adding the delta row makes it seem like the
> number are not growing apart as I would expect.
>
> If we normalize this to VMAs per second by dividing the forks by 10,
> then multiplying by the number of VMAs we get this:
>
> VMA Count: 21 121 221 421 821 1621 3221 6421
> log(VMA) 1.32 2.00 2.30 2.60 2.90 3.20 3.36 3.81
> next-20230921: 258349.8 928268.7 1215996.7 1464383.7 1707725.0 1842916.5 1420514.5 2044440.9
> this: 267961.5 1057443.3 1496798.3 1949184.0 2446120.6 2704729.5 2102315.0 3086251.5
> delta 9611.7 129174.6 280801.6 484800.3 738395.6 861813.0 681800.5 1041810.6
>
> The first thing that I noticed was that we hit some dip in the numbers
> at 3221. I first thought that might be something else running on the
> host machine, but both runs are affected by around the same percent.
>
> Here, we do see the delta growing apart, but peaking in growth around
> 821 VMAs. Again that 3221 number is out of line.
>
> If we discard 21 and anything above 1621, we still see both lines are
> asymptotic curves. I would expect that the new algorithm would be more
> linear to represent O(n), but there is certainly a curve when graphed
> with a normalized X-axis. The older algorithm, O(n*log(n)) should be
> the opposite curve all together, and with a diminishing return, but it
> seems the more elements we have, the more operations we can perform in a
> second.
Thank you for your detailed analysis.
So, are you expecting the transformed data to be close to a constant
value?
Please note that besides constructing a new maple tree, there are many
other operations in fork(). As the number of VMAs increases, the number
of fork() calls decreases. Therefore, the overall cost spent on other
operations becomes smaller, while the cost spent on duplicating VMAs
increases. That's why this data grows with the increase of VMAs. I
speculate that if the number of VMAs is large enough to neglect the time
spent on other operations in fork(), this data will approach a constant
value.
If we want to achieve the expected curve, I think we should simulate the
process of constructing the maple tree in user space to avoid the impact
of other operations in fork(), just like in the current bench_forking().
>
> Thinking about what is going on here, I cannot come up with a reason
> that there would be a curve to the line at all. If we took more
> measurements, I would think the samples would be an ever-increasing line
> with variability for some function of 16 - a saw toothed increasing
> line. At least, until an upper limit is reached. We can see that the
> upper limit was still not achieved at 1621 since 6421 is higher for both
> runs, but a curve is evident on both methods, which suggests something
> else is a significant contributor.
>
> I would think each VMA requires the same amount of work, so a constant.
> The allocations would again, be some function that would linearly
> increase with the existing method over-estimating by a huge number of
> nodes.
>
> I'm not trying to nitpick here, but it is important to be accurate in
> the statements because it may alter choices on how to proceed in
> improving this performance later. It may be others looking through
> these commit messages to see if something can be improved.
Thank you for pointing that out. I will try to describe it more
accurately in the commit log and see if I can measure the expected curve
in user space.
>
> I also feel like your notes on your algorithm are worth including in the
> commit because it could prove rather valuable if we revisit forking in
> the future.
Do you mean that I should write the analysis of the time complexity of
the new algorithm in the commit log?
>
> The more I look at this, the more questions I have that I cannot answer.
> One thing we can see is that the new method is faster in this
> micro-benchmark.
Yes. It should be noted that in the field of computer science, if the
test results don't align with the expected mathematical calculations,
it indicates an error in the calculations. This is because accurate
calculations will always be reflected in the test results. ????
>
>>>>
>>>> [1] https://github.com/kdlucas/byte-unixbench/tree/master
>>>>
>>>> Signed-off-by: Peng Zhang <[email protected]>
>>>> ---
>>>> include/linux/mm.h | 1 +
>>>> kernel/fork.c | 34 ++++++++++++++++++++----------
>>>> mm/internal.h | 3 ++-
>>>> mm/memory.c | 7 ++++---
>>>> mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
>>>> 5 files changed, 80 insertions(+), 17 deletions(-)
>>>>
>>>> diff --git a/include/linux/mm.h b/include/linux/mm.h
>>>> index 1f1d0d6b8f20..10c59dc7ffaa 100644
>>>> --- a/include/linux/mm.h
>>>> +++ b/include/linux/mm.h
>>>> @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
>>>> extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
>>>> unsigned long addr, unsigned long len, pgoff_t pgoff,
>>>> bool *need_rmap_locks);
>>>> +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
>>>> extern void exit_mmap(struct mm_struct *);
>>>> static inline int check_data_rlimit(unsigned long rlim,
>>>> diff --git a/kernel/fork.c b/kernel/fork.c
>>>> index 7ae36c2e7290..2f3d83e89fe6 100644
>>>> --- a/kernel/fork.c
>>>> +++ b/kernel/fork.c
>>>> @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>> int retval;
>>>> unsigned long charge = 0;
>>>> LIST_HEAD(uf);
>>>> - VMA_ITERATOR(old_vmi, oldmm, 0);
>>>> VMA_ITERATOR(vmi, mm, 0);
>>>> uprobe_start_dup_mmap();
>>>> @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>> goto out;
>>>> khugepaged_fork(mm, oldmm);
>>>> - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
>>>> - if (retval)
>>>> + /* Use __mt_dup() to efficiently build an identical maple tree. */
>>>> + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
>>>> + if (unlikely(retval))
>>>> goto out;
>>>> mt_clear_in_rcu(vmi.mas.tree);
>>>> - for_each_vma(old_vmi, mpnt) {
>>>> + for_each_vma(vmi, mpnt) {
>>>> struct file *file;
>>>> vma_start_write(mpnt);
>>>> if (mpnt->vm_flags & VM_DONTCOPY) {
>>>> + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
>>>> +
>>>> + /* If failed, undo all completed duplications. */
>>>> + if (unlikely(mas_is_err(&vmi.mas))) {
>>>> + retval = xa_err(vmi.mas.node);
>>>> + goto loop_out;
>>>> + }
>>>> +
>>>> vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
>>>> continue;
>>>> }
>>>> @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>> if (is_vm_hugetlb_page(tmp))
>>>> hugetlb_dup_vma_private(tmp);
>>>> - /* Link the vma into the MT */
>>>> - if (vma_iter_bulk_store(&vmi, tmp))
>>>> - goto fail_nomem_vmi_store;
>>>> + /*
>>>> + * Link the vma into the MT. After using __mt_dup(), memory
>>>> + * allocation is not necessary here, so it cannot fail.
>>>> + */
>>>> + mas_store(&vmi.mas, tmp);
>>>> mm->map_count++;
>>>> if (!(tmp->vm_flags & VM_WIPEONFORK))
>>>> @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>> if (tmp->vm_ops && tmp->vm_ops->open)
>>>> tmp->vm_ops->open(tmp);
>>>> - if (retval)
>>>> + if (retval) {
>>>> + mpnt = vma_next(&vmi);
>>>> goto loop_out;
>>>> + }
>>>> }
>>>> /* a new mm has just been created */
>>>> retval = arch_dup_mmap(oldmm, mm);
>>>> loop_out:
>>>> vma_iter_free(&vmi);
>>>> - if (!retval)
>>>> + if (likely(!retval))
>>>> mt_set_in_rcu(vmi.mas.tree);
>>>> + else
>>>> + undo_dup_mmap(mm, mpnt);
>>>> out:
>>>> mmap_write_unlock(mm);
>>>> flush_tlb_mm(oldmm);
>>>> @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>> uprobe_end_dup_mmap();
>>>> return retval;
>>>> -fail_nomem_vmi_store:
>>>> - unlink_anon_vmas(tmp);
>>>> fail_nomem_anon_vma_fork:
>>>> mpol_put(vma_policy(tmp));
>>>> fail_nomem_policy:
>>>> diff --git a/mm/internal.h b/mm/internal.h
>>>> index 7a961d12b088..288ec81770cb 100644
>>>> --- a/mm/internal.h
>>>> +++ b/mm/internal.h
>>>> @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
>>>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>> struct vm_area_struct *start_vma, unsigned long floor,
>>>> - unsigned long ceiling, bool mm_wr_locked);
>>>> + unsigned long ceiling, unsigned long tree_end,
>>>> + bool mm_wr_locked);
>>>> void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
>>>> struct zap_details;
>>>> diff --git a/mm/memory.c b/mm/memory.c
>>>> index 983a40f8ee62..1fd66a0d5838 100644
>>>> --- a/mm/memory.c
>>>> +++ b/mm/memory.c
>>>> @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
>>>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>> struct vm_area_struct *vma, unsigned long floor,
>>>> - unsigned long ceiling, bool mm_wr_locked)
>>>> + unsigned long ceiling, unsigned long tree_end,
>>>> + bool mm_wr_locked)
>>>> {
>>>> do {
>>>> unsigned long addr = vma->vm_start;
>>>> @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>> * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
>>>> * be 0. This will underflow and is okay.
>>>> */
>>>> - next = mas_find(mas, ceiling - 1);
>>>> + next = mas_find(mas, tree_end - 1);
>>>> /*
>>>> * Hide vma from rmap and truncate_pagecache before freeing
>>>> @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>> while (next && next->vm_start <= vma->vm_end + PMD_SIZE
>>>> && !is_vm_hugetlb_page(next)) {
>>>> vma = next;
>>>> - next = mas_find(mas, ceiling - 1);
>>>> + next = mas_find(mas, tree_end - 1);
>>>> if (mm_wr_locked)
>>>> vma_start_write(vma);
>>>> unlink_anon_vmas(vma);
>>>> diff --git a/mm/mmap.c b/mm/mmap.c
>>>> index 2ad950f773e4..daed3b423124 100644
>>>> --- a/mm/mmap.c
>>>> +++ b/mm/mmap.c
>>>> @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
>>>> mas_set(mas, mt_start);
>>>> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
>>>> next ? next->vm_start : USER_PGTABLES_CEILING,
>>>> - mm_wr_locked);
>>>> + tree_end, mm_wr_locked);
>>>> tlb_finish_mmu(&tlb);
>>>> }
>>>> @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
>>>> }
>>>> EXPORT_SYMBOL(vm_brk);
>>>> +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
>>>> +{
>>>> + unsigned long tree_end;
>>>> + VMA_ITERATOR(vmi, mm, 0);
>>>> + struct vm_area_struct *vma;
>>>> + unsigned long nr_accounted = 0;
>>>> + int count = 0;
>>>> +
>>>> + /*
>>>> + * vma_end points to the first VMA that has not been duplicated. We need
>>>> + * to unmap all VMAs before it.
>>>> + * If vma_end is NULL, it means that all VMAs in the maple tree have
>>>> + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
>>>> + * when using it.
>>>> + */
>>>> + if (vma_end) {
>>>> + tree_end = vma_end->vm_start;
>>>> + if (tree_end == 0)
>>>> + goto destroy;
>>>> + } else
>>>> + tree_end = 0;
>>>> +
>>>> + vma = mas_find(&vmi.mas, tree_end - 1);
>>>> +
>>>> + if (vma) {
>>>> + arch_unmap(mm, vma->vm_start, tree_end);
>>>> + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
>>>> + tree_end, true);
>>>
>>> next is vma_end, as per your comment above. Using next = vma_end allows
>>> you to avoid adding another argument to free_pgtables().
>> Unfortunately, it cannot be done this way. I fell into this trap before,
>> and it caused incomplete page table cleanup. To solve this problem, the
>> only solution I can think of right now is to add an additional
>> parameter.
>>
>> free_pgtables() will be called in unmap_region() to free the page table,
>> like this:
>>
>> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
>> next ? next->vm_start : USER_PGTABLES_CEILING,
>> mm_wr_locked);
>>
>> The problem is with 'next'. Our 'vma_end' does not exist in the actual
>> mmap because it has not been duplicated and cannot be used as 'next'.
>> If there is a real 'next', we can use 'next->vm_start' as the ceiling,
>> which is not a problem. If there is no 'next' (next is 'vma_end'), we
>> can only use 'USER_PGTABLES_CEILING' as the ceiling. Using
>> 'vma_end->vm_start' as the ceiling will cause the page table not to be
>> fully freed, which may be related to alignment in 'free_pgd_range()'. To
>> solve this problem, we have to introduce 'tree_end', and separating
>> 'tree_end' and 'ceiling' can solve this problem.
>
> Can you just use ceiling? That is, just not pass in next and keep the
> code as-is? This is how exit_mmap() does it and should avoid any
> alignment issues. I assume you tried that and something went wrong as
> well?
I tried that, but it didn't work either. In free_pgtables(), the
following line of code is used to iterate over VMAs:
mas_find(mas, ceiling - 1);
If next is passed as NULL, ceiling will be 0, resulting in iterating
over all the VMAs in the maple tree, including the last portion that was
not duplicated.
>
>>
>>>
>>>> +
>>>> + mas_set(&vmi.mas, vma->vm_end);
>>>> + do {
>>>> + if (vma->vm_flags & VM_ACCOUNT)
>>>> + nr_accounted += vma_pages(vma);
>>>> + remove_vma(vma, true);
>>>> + count++;
>>>> + cond_resched();
>>>> + vma = mas_find(&vmi.mas, tree_end - 1);
>>>> + } while (vma != NULL);
>>>> +
>>>> + BUG_ON(count != mm->map_count);
>>>> +
>>>> + vm_unacct_memory(nr_accounted);
>>>> + }
>>>> +
>>>> +destroy:
>>>> + __mt_destroy(&mm->mm_mt);
>>>> +}
>>>> +
>>>> /* Release all mmaps. */
>>>> void exit_mmap(struct mm_struct *mm)
>>>> {
>>>> @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
>>>> mt_clear_in_rcu(&mm->mm_mt);
>>>> mas_set(&mas, vma->vm_end);
>>>> free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
>>>> - USER_PGTABLES_CEILING, true);
>>>> + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
>>>> tlb_finish_mmu(&tlb);
>>>> /*
>>>> --
>>>> 2.20.1
>>>>
>>>
>>
>
在 2023/10/4 22:25, Liam R. Howlett 写道:
> * Peng Zhang <[email protected]> [231004 05:09]:
>>
>>
>> 在 2023/10/4 02:45, Liam R. Howlett 写道:
>>> * Peng Zhang <[email protected]> [230924 23:58]:
>>>> Introduce interfaces __mt_dup() and mtree_dup(), which are used to
>>>> duplicate a maple tree. They duplicate a maple tree in Depth-First
>>>> Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the
>>>> source tree and allocate new child nodes in non-leaf nodes. The new node
>>>> is exactly the same as the source node except for all the addresses
>>>> stored in it. It will be faster than traversing all elements in the
>>>> source tree and inserting them one by one into the new tree. The time
>>>> complexity of these two functions is O(n).
>>>>
>>>> The difference between __mt_dup() and mtree_dup() is that mtree_dup()
>>>> handles locks internally.
>>>>
>>>> Signed-off-by: Peng Zhang <[email protected]>
>>>> ---
>>>> include/linux/maple_tree.h | 3 +
>>>> lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++
>>>> 2 files changed, 289 insertions(+)
>>>>
>>>> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
>>>> index 666a3764ed89..de5a4056503a 100644
>>>> --- a/include/linux/maple_tree.h
>>>> +++ b/include/linux/maple_tree.h
>>>> @@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index,
>>>> void *entry, gfp_t gfp);
>>>> void *mtree_erase(struct maple_tree *mt, unsigned long index);
>>>> +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
>>>> +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
>>>> +
>>>> void mtree_destroy(struct maple_tree *mt);
>>>> void __mt_destroy(struct maple_tree *mt);
>>>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>>>> index 3fe5652a8c6c..ed8847b4f1ff 100644
>>>> --- a/lib/maple_tree.c
>>>> +++ b/lib/maple_tree.c
>>>> @@ -6370,6 +6370,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
>>>> }
>>>> EXPORT_SYMBOL(mtree_erase);
>>>> +/*
>>>> + * mas_dup_free() - Free an incomplete duplication of a tree.
>>>> + * @mas: The maple state of a incomplete tree.
>>>> + *
>>>> + * The parameter @mas->node passed in indicates that the allocation failed on
>>>> + * this node. This function frees all nodes starting from @mas->node in the
>>>> + * reverse order of mas_dup_build(). There is no need to hold the source tree
>>>> + * lock at this time.
>>>> + */
>>>> +static void mas_dup_free(struct ma_state *mas)
>>>> +{
>>>> + struct maple_node *node;
>>>> + enum maple_type type;
>>>> + void __rcu **slots;
>>>> + unsigned char count, i;
>>>> +
>>>> + /* Maybe the first node allocation failed. */
>>>> + if (mas_is_none(mas))
>>>> + return;
>>>> +
>>>> + while (!mte_is_root(mas->node)) {
>>>> + mas_ascend(mas);
>>>> +
>>>> + if (mas->offset) {
>>>> + mas->offset--;
>>>> + do {
>>>> + mas_descend(mas);
>>>> + mas->offset = mas_data_end(mas);
>>>> + } while (!mte_is_leaf(mas->node));
>>>> +
>>>> + mas_ascend(mas);
>>>> + }
>>>> +
>>>> + node = mte_to_node(mas->node);
>>>> + type = mte_node_type(mas->node);
>>>> + slots = ma_slots(node, type);
>>>> + count = mas_data_end(mas) + 1;
>>>> + for (i = 0; i < count; i++)
>>>> + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK;
>>>> +
>>>> + mt_free_bulk(count, slots);
>>>> + }
>>>> +
>>>> + node = mte_to_node(mas->node);
>>>> + mt_free_one(node);
>>>> +}
>>>> +
>>>> +/*
>>>> + * mas_copy_node() - Copy a maple node and replace the parent.
>>>> + * @mas: The maple state of source tree.
>>>> + * @new_mas: The maple state of new tree.
>>>> + * @parent: The parent of the new node.
>>>> + *
>>>> + * Copy @mas->node to @new_mas->node, set @parent to be the parent of
>>>> + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM.
>>>> + */
>>>> +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas,
>>>> + struct maple_pnode *parent)
>>>> +{
>>>> + struct maple_node *node = mte_to_node(mas->node);
>>>> + struct maple_node *new_node = mte_to_node(new_mas->node);
>>>> + unsigned long val;
>>>> +
>>>> + /* Copy the node completely. */
>>>> + memcpy(new_node, node, sizeof(struct maple_node));
>>>> +
>>>> + /* Update the parent node pointer. */
>>>> + val = (unsigned long)node->parent & MAPLE_NODE_MASK;
>>>> + new_node->parent = ma_parent_ptr(val | (unsigned long)parent);
>>>> +}
>>>> +
>>>> +/*
>>>> + * mas_dup_alloc() - Allocate child nodes for a maple node.
>>>> + * @mas: The maple state of source tree.
>>>> + * @new_mas: The maple state of new tree.
>>>> + * @gfp: The GFP_FLAGS to use for allocations.
>>>> + *
>>>> + * This function allocates child nodes for @new_mas->node during the duplication
>>>> + * process. If memory allocation fails, @mas is set to -ENOMEM.
>>>> + */
>>>> +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas,
>>>> + gfp_t gfp)
>>>> +{
>>>> + struct maple_node *node = mte_to_node(mas->node);
>>>> + struct maple_node *new_node = mte_to_node(new_mas->node);
>>>> + enum maple_type type;
>>>> + unsigned char request, count, i;
>>>> + void __rcu **slots;
>>>> + void __rcu **new_slots;
>>>> + unsigned long val;
>>>> +
>>>> + /* Allocate memory for child nodes. */
>>>> + type = mte_node_type(mas->node);
>>>> + new_slots = ma_slots(new_node, type);
>>>> + request = mas_data_end(mas) + 1;
>>>> + count = mt_alloc_bulk(gfp, request, (void **)new_slots);
>>>> + if (unlikely(count < request)) {
>>>> + if (count) {
>>>> + mt_free_bulk(count, new_slots);
>>>
>>> If you look at mm/slab.c: kmem_cache_alloc(), you will see that the
>>> error path already bulk frees for you - but does not zero the array.
>>> This bulk free will lead to double free, but you do need the below
>>> memset(). Also, it will return !count or request. So, I think this code
>>> is never executed as it is written.
>> If kmem_cache_alloc() is called to allocate memory in mt_alloc_bulk(),
>> then this code will not be executed because it only returns 0 or
>> request. However, I am concerned that changes to mt_alloc_bulk() like
>> [1] may be merged, which could potentially lead to memory leaks. To
>> improve robustness, I wrote it this way.
>>
>> How do you think it should be handled? Is it okay to do this like the
>> code below?
>>
>> if (unlikely(count < request)) {
>> memset(new_slots, 0, request * sizeof(unsigned long));
>> mas_set_err(mas, -ENOMEM);
>> return;
>> }
>>
>> [1] https://lore.kernel.org/lkml/[email protected]/
>
> Ah, I see.
>
> We should keep the same functionality as before. The code you are
> referencing is an RFC and won't be merged as-is. We should be sure to
> keep an eye on this happening.
>
> I think the code you have there is correct.
>
>>>
>>> I don't think this will show up in your testcases because the test code
>>> doesn't leave dangling pointers and simply returns 0 if there isn't
>>> enough nodes.
>> Yes, no testing here.
>
> Yeah :/ I think we should update the test code at some point to behave
> the same as the real code. Don't worry about it here though.
If we want to test this here, we need to modify the
kmem_cache_alloc_bulk() in the user space to allocate a portion of
memory. This will cause it to behave differently from the corresponding
function in the kernel space. I'm not sure if this modification is
acceptable.
Also, I might need to move the memset() outside of the if
statement (if (unlikely(count < request)){}) to use it for cleaning up
residual pointers.
>
>>>
>>>> + memset(new_slots, 0, count * sizeof(unsigned long));
>>>> + }
>>>> + mas_set_err(mas, -ENOMEM);
>>>> + return;
>>>> + }
>>>> +
>>>> + /* Restore node type information in slots. */
>>>> + slots = ma_slots(node, type);
>>>> + for (i = 0; i < count; i++) {
>>>> + val = (unsigned long)mt_slot_locked(mas->tree, slots, i);
>>>> + val &= MAPLE_NODE_MASK;
>>>> + ((unsigned long *)new_slots)[i] |= val;
>>>> + }
>>>> +}
>>>> +
>>>> +/*
>>>> + * mas_dup_build() - Build a new maple tree from a source tree
>>>> + * @mas: The maple state of source tree.
>>>> + * @new_mas: The maple state of new tree.
>>>> + * @gfp: The GFP_FLAGS to use for allocations.
>>>> + *
>>>> + * This function builds a new tree in DFS preorder. If the memory allocation
>>>> + * fails, the error code -ENOMEM will be set in @mas, and @new_mas points to the
>>>> + * last node. mas_dup_free() will free the incomplete duplication of a tree.
>>>> + *
>>>> + * Note that the attributes of the two trees need to be exactly the same, and the
>>>> + * new tree needs to be empty, otherwise -EINVAL will be set in @mas.
>>>> + */
>>>> +static inline void mas_dup_build(struct ma_state *mas, struct ma_state *new_mas,
>>>> + gfp_t gfp)
>>>> +{
>>>> + struct maple_node *node;
>>>> + struct maple_pnode *parent = NULL;
>>>> + struct maple_enode *root;
>>>> + enum maple_type type;
>>>> +
>>>> + if (unlikely(mt_attr(mas->tree) != mt_attr(new_mas->tree)) ||
>>>> + unlikely(!mtree_empty(new_mas->tree))) {
>>>
>>> Would it be worth checking mas_is_start() for both mas and new_mas here?
>>> Otherwise mas_start() will not do what you want below. I think it is
>>> implied that both are at MAS_START but never checked?
>> This function is an internal function and is currently only called by
>> {mtree,__mt}_dup(). It is ensured that both 'mas' and 'new_mas' are
>> MAS_START when called. Do you think we really need to check it? Maybe we
>> just need to explain it in the comments?
>
> Yes, just document that it is expected to be MAS_START.
>
>>>
>>>> + mas_set_err(mas, -EINVAL);
>>>> + return;
>>>> + }
>>>> +
>>>> + mas_start(mas);
>>>> + if (mas_is_ptr(mas) || mas_is_none(mas)) {
>>>> + root = mt_root_locked(mas->tree);
>>>> + goto set_new_tree;
>>>> + }
>>>> +
>>>> + node = mt_alloc_one(gfp);
>>>> + if (!node) {
>>>> + new_mas->node = MAS_NONE;
>>>> + mas_set_err(mas, -ENOMEM);
>>>> + return;
>>>> + }
>>>> +
>>>> + type = mte_node_type(mas->node);
>>>> + root = mt_mk_node(node, type);
>>>> + new_mas->node = root;
>>>> + new_mas->min = 0;
>>>> + new_mas->max = ULONG_MAX;
>>>> + root = mte_mk_root(root);
>>>> +
>>>> + while (1) {
>>>> + mas_copy_node(mas, new_mas, parent);
>>>> +
>>>> + if (!mte_is_leaf(mas->node)) {
>>>> + /* Only allocate child nodes for non-leaf nodes. */
>>>> + mas_dup_alloc(mas, new_mas, gfp);
>>>> + if (unlikely(mas_is_err(mas)))
>>>> + return;
>>>> + } else {
>>>> + /*
>>>> + * This is the last leaf node and duplication is
>>>> + * completed.
>>>> + */
>>>> + if (mas->max == ULONG_MAX)
>>>> + goto done;
>>>> +
>>>> + /* This is not the last leaf node and needs to go up. */
>>>> + do {
>>>> + mas_ascend(mas);
>>>> + mas_ascend(new_mas);
>>>> + } while (mas->offset == mas_data_end(mas));
>>>> +
>>>> + /* Move to the next subtree. */
>>>> + mas->offset++;
>>>> + new_mas->offset++;
>>>> + }
>>>> +
>>>> + mas_descend(mas);
>>>> + parent = ma_parent_ptr(mte_to_node(new_mas->node));
>>>> + mas_descend(new_mas);
>>>> + mas->offset = 0;
>>>> + new_mas->offset = 0;
>>>> + }
>>>> +done:
>>>> + /* Specially handle the parent of the root node. */
>>>> + mte_to_node(root)->parent = ma_parent_ptr(mas_tree_parent(new_mas));
>>>> +set_new_tree:
>>>> + /* Make them the same height */
>>>> + new_mas->tree->ma_flags = mas->tree->ma_flags;
>>>> + rcu_assign_pointer(new_mas->tree->ma_root, root);
>>>> +}
>>>> +
>>>> +/**
>>>> + * __mt_dup(): Duplicate a maple tree
>>>> + * @mt: The source maple tree
>>>> + * @new: The new maple tree
>>>> + * @gfp: The GFP_FLAGS to use for allocations
>>>> + *
>>>> + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
>>>> + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
>>>> + * new child nodes in non-leaf nodes. The new node is exactly the same as the
>>>> + * source node except for all the addresses stored in it. It will be faster than
>>>> + * traversing all elements in the source tree and inserting them one by one into
>>>> + * the new tree.
>>>> + * The user needs to ensure that the attributes of the source tree and the new
>>>> + * tree are the same, and the new tree needs to be an empty tree, otherwise
>>>> + * -EINVAL will be returned.
>>>> + * Note that the user needs to manually lock the source tree and the new tree.
>>>> + *
>>>> + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
>>>> + * the attributes of the two trees are different or the new tree is not an empty
>>>> + * tree.
>>>> + */
>>>> +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
>>>> +{
>>>> + int ret = 0;
>>>> + MA_STATE(mas, mt, 0, 0);
>>>> + MA_STATE(new_mas, new, 0, 0);
>>>> +
>>>> + mas_dup_build(&mas, &new_mas, gfp);
>>>> +
>>>> + if (unlikely(mas_is_err(&mas))) {
>>>> + ret = xa_err(mas.node);
>>>> + if (ret == -ENOMEM)
>>>> + mas_dup_free(&new_mas);
>>>> + }
>>>> +
>>>> + return ret;
>>>> +}
>>>> +EXPORT_SYMBOL(__mt_dup);
>>>> +
>>>> +/**
>>>> + * mtree_dup(): Duplicate a maple tree
>>>> + * @mt: The source maple tree
>>>> + * @new: The new maple tree
>>>> + * @gfp: The GFP_FLAGS to use for allocations
>>>> + *
>>>> + * This function duplicates a maple tree in Depth-First Search (DFS) pre-order
>>>> + * traversal. It uses memcopy() to copy nodes in the source tree and allocate
>>>> + * new child nodes in non-leaf nodes. The new node is exactly the same as the
>>>> + * source node except for all the addresses stored in it. It will be faster than
>>>> + * traversing all elements in the source tree and inserting them one by one into
>>>> + * the new tree.
>>>> + * The user needs to ensure that the attributes of the source tree and the new
>>>> + * tree are the same, and the new tree needs to be an empty tree, otherwise
>>>> + * -EINVAL will be returned.
>>>
>>> The requirement to duplicate the entire tree should be mentioned and
>>> maybe the mas_is_start() requirement (as I asked about above?)
>> Okay, I will add a comment saying 'This duplicates the entire tree'. But
>> 'mas_is_start()' is not a requirement for calling this function because
>> the function's parameter is 'maple_tree', not 'ma_state'. I think
>> 'mas_is_start()' should be added to the comment for 'mas_dup_build()'.
>
> Oh right, thanks.
>
>>>
>>> I can see someone thinking they are going to make a super fast sub-tree
>>> of existing data using this - which won't (always?) work.
>>>
>>>> + *
>>>> + * Return: 0 on success, -ENOMEM if memory could not be allocated, -EINVAL If
>>>> + * the attributes of the two trees are different or the new tree is not an empty
>>>> + * tree.
>>>> + */
>>>> +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
>>>> +{
>>>> + int ret = 0;
>>>> + MA_STATE(mas, mt, 0, 0);
>>>> + MA_STATE(new_mas, new, 0, 0);
>>>> +
>>>> + mas_lock(&new_mas);
>>>> + mas_lock_nested(&mas, SINGLE_DEPTH_NESTING);
>>>> +
>>>> + mas_dup_build(&mas, &new_mas, gfp);
>>>> + mas_unlock(&mas);
>>>> +
>>>> + if (unlikely(mas_is_err(&mas))) {
>>>> + ret = xa_err(mas.node);
>>>> + if (ret == -ENOMEM)
>>>> + mas_dup_free(&new_mas);
>>>> + }
>>>> +
>>>> + mas_unlock(&new_mas);
>>>> +
>>>> + return ret;
>>>> +}
>>>> +EXPORT_SYMBOL(mtree_dup);
>>>> +
>>>> /**
>>>> * __mt_destroy() - Walk and free all nodes of a locked maple tree.
>>>> * @mt: The maple tree
>>>> --
>>>> 2.20.1
>>>>
>>>
>
* Peng Zhang <[email protected]> [231005 11:55]:
>
>
> 在 2023/10/4 22:25, Liam R. Howlett 写道:
> > * Peng Zhang <[email protected]> [231004 05:09]:
> > >
> > >
> > > 在 2023/10/4 02:45, Liam R. Howlett 写道:
> > > > * Peng Zhang <[email protected]> [230924 23:58]:
> > > > > Introduce interfaces __mt_dup() and mtree_dup(), which are used to
> > > > > duplicate a maple tree. They duplicate a maple tree in Depth-First
> > > > > Search (DFS) pre-order traversal. It uses memcopy() to copy nodes in the
> > > > > source tree and allocate new child nodes in non-leaf nodes. The new node
> > > > > is exactly the same as the source node except for all the addresses
> > > > > stored in it. It will be faster than traversing all elements in the
> > > > > source tree and inserting them one by one into the new tree. The time
> > > > > complexity of these two functions is O(n).
> > > > >
> > > > > The difference between __mt_dup() and mtree_dup() is that mtree_dup()
> > > > > handles locks internally.
> > > > >
> > > > > Signed-off-by: Peng Zhang <[email protected]>
> > > > > ---
> > > > > include/linux/maple_tree.h | 3 +
> > > > > lib/maple_tree.c | 286 +++++++++++++++++++++++++++++++++++++
> > > > > 2 files changed, 289 insertions(+)
> > > > >
> > > > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> > > > > index 666a3764ed89..de5a4056503a 100644
> > > > > --- a/include/linux/maple_tree.h
> > > > > +++ b/include/linux/maple_tree.h
> > > > > @@ -329,6 +329,9 @@ int mtree_store(struct maple_tree *mt, unsigned long index,
> > > > > void *entry, gfp_t gfp);
> > > > > void *mtree_erase(struct maple_tree *mt, unsigned long index);
> > > > > +int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
> > > > > +int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp);
> > > > > +
> > > > > void mtree_destroy(struct maple_tree *mt);
> > > > > void __mt_destroy(struct maple_tree *mt);
> > > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > > > index 3fe5652a8c6c..ed8847b4f1ff 100644
> > > > > --- a/lib/maple_tree.c
> > > > > +++ b/lib/maple_tree.c
> > > > > @@ -6370,6 +6370,292 @@ void *mtree_erase(struct maple_tree *mt, unsigned long index)
> > > > > }
> > > > > EXPORT_SYMBOL(mtree_erase);
> > > > > +/*
> > > > > + * mas_dup_free() - Free an incomplete duplication of a tree.
> > > > > + * @mas: The maple state of a incomplete tree.
> > > > > + *
> > > > > + * The parameter @mas->node passed in indicates that the allocation failed on
> > > > > + * this node. This function frees all nodes starting from @mas->node in the
> > > > > + * reverse order of mas_dup_build(). There is no need to hold the source tree
> > > > > + * lock at this time.
> > > > > + */
> > > > > +static void mas_dup_free(struct ma_state *mas)
> > > > > +{
> > > > > + struct maple_node *node;
> > > > > + enum maple_type type;
> > > > > + void __rcu **slots;
> > > > > + unsigned char count, i;
> > > > > +
> > > > > + /* Maybe the first node allocation failed. */
> > > > > + if (mas_is_none(mas))
> > > > > + return;
> > > > > +
> > > > > + while (!mte_is_root(mas->node)) {
> > > > > + mas_ascend(mas);
> > > > > +
> > > > > + if (mas->offset) {
> > > > > + mas->offset--;
> > > > > + do {
> > > > > + mas_descend(mas);
> > > > > + mas->offset = mas_data_end(mas);
> > > > > + } while (!mte_is_leaf(mas->node));
> > > > > +
> > > > > + mas_ascend(mas);
> > > > > + }
> > > > > +
> > > > > + node = mte_to_node(mas->node);
> > > > > + type = mte_node_type(mas->node);
> > > > > + slots = ma_slots(node, type);
> > > > > + count = mas_data_end(mas) + 1;
> > > > > + for (i = 0; i < count; i++)
> > > > > + ((unsigned long *)slots)[i] &= ~MAPLE_NODE_MASK;
> > > > > +
> > > > > + mt_free_bulk(count, slots);
> > > > > + }
> > > > > +
> > > > > + node = mte_to_node(mas->node);
> > > > > + mt_free_one(node);
> > > > > +}
> > > > > +
> > > > > +/*
> > > > > + * mas_copy_node() - Copy a maple node and replace the parent.
> > > > > + * @mas: The maple state of source tree.
> > > > > + * @new_mas: The maple state of new tree.
> > > > > + * @parent: The parent of the new node.
> > > > > + *
> > > > > + * Copy @mas->node to @new_mas->node, set @parent to be the parent of
> > > > > + * @new_mas->node. If memory allocation fails, @mas is set to -ENOMEM.
> > > > > + */
> > > > > +static inline void mas_copy_node(struct ma_state *mas, struct ma_state *new_mas,
> > > > > + struct maple_pnode *parent)
> > > > > +{
> > > > > + struct maple_node *node = mte_to_node(mas->node);
> > > > > + struct maple_node *new_node = mte_to_node(new_mas->node);
> > > > > + unsigned long val;
> > > > > +
> > > > > + /* Copy the node completely. */
> > > > > + memcpy(new_node, node, sizeof(struct maple_node));
> > > > > +
> > > > > + /* Update the parent node pointer. */
> > > > > + val = (unsigned long)node->parent & MAPLE_NODE_MASK;
> > > > > + new_node->parent = ma_parent_ptr(val | (unsigned long)parent);
> > > > > +}
> > > > > +
> > > > > +/*
> > > > > + * mas_dup_alloc() - Allocate child nodes for a maple node.
> > > > > + * @mas: The maple state of source tree.
> > > > > + * @new_mas: The maple state of new tree.
> > > > > + * @gfp: The GFP_FLAGS to use for allocations.
> > > > > + *
> > > > > + * This function allocates child nodes for @new_mas->node during the duplication
> > > > > + * process. If memory allocation fails, @mas is set to -ENOMEM.
> > > > > + */
> > > > > +static inline void mas_dup_alloc(struct ma_state *mas, struct ma_state *new_mas,
> > > > > + gfp_t gfp)
> > > > > +{
> > > > > + struct maple_node *node = mte_to_node(mas->node);
> > > > > + struct maple_node *new_node = mte_to_node(new_mas->node);
> > > > > + enum maple_type type;
> > > > > + unsigned char request, count, i;
> > > > > + void __rcu **slots;
> > > > > + void __rcu **new_slots;
> > > > > + unsigned long val;
> > > > > +
> > > > > + /* Allocate memory for child nodes. */
> > > > > + type = mte_node_type(mas->node);
> > > > > + new_slots = ma_slots(new_node, type);
> > > > > + request = mas_data_end(mas) + 1;
> > > > > + count = mt_alloc_bulk(gfp, request, (void **)new_slots);
> > > > > + if (unlikely(count < request)) {
> > > > > + if (count) {
> > > > > + mt_free_bulk(count, new_slots);
> > > >
> > > > If you look at mm/slab.c: kmem_cache_alloc(), you will see that the
> > > > error path already bulk frees for you - but does not zero the array.
> > > > This bulk free will lead to double free, but you do need the below
> > > > memset(). Also, it will return !count or request. So, I think this code
> > > > is never executed as it is written.
> > > If kmem_cache_alloc() is called to allocate memory in mt_alloc_bulk(),
> > > then this code will not be executed because it only returns 0 or
> > > request. However, I am concerned that changes to mt_alloc_bulk() like
> > > [1] may be merged, which could potentially lead to memory leaks. To
> > > improve robustness, I wrote it this way.
> > >
> > > How do you think it should be handled? Is it okay to do this like the
> > > code below?
> > >
> > > if (unlikely(count < request)) {
> > > memset(new_slots, 0, request * sizeof(unsigned long));
> > > mas_set_err(mas, -ENOMEM);
> > > return;
> > > }
> > >
> > > [1] https://lore.kernel.org/lkml/[email protected]/
> >
> > Ah, I see.
> >
> > We should keep the same functionality as before. The code you are
> > referencing is an RFC and won't be merged as-is. We should be sure to
> > keep an eye on this happening.
> >
> > I think the code you have there is correct.
> >
> > > >
> > > > I don't think this will show up in your testcases because the test code
> > > > doesn't leave dangling pointers and simply returns 0 if there isn't
> > > > enough nodes.
> > > Yes, no testing here.
> >
> > Yeah :/ I think we should update the test code at some point to behave
> > the same as the real code. Don't worry about it here though.
> If we want to test this here, we need to modify the
> kmem_cache_alloc_bulk() in the user space to allocate a portion of
> memory. This will cause it to behave differently from the corresponding
> function in the kernel space. I'm not sure if this modification is
> acceptable.
Well, no. We can change the test code to do the same as the kernel -
if there aren't enough nodes then put pointers to the ones we have in
the array but don't actually allocate them (or free them). This way we
will catch double-frees or memory leaks. Essentially leaving the
partial data in the array.
If you want to test it in-kernel, then you could alter the kernel
function to check the task name with some global counter to cause it to
fail out after some count. That would just be a one-off test though.
>
> Also, I might need to move the memset() outside of the if
> statement (if (unlikely(count < request)){}) to use it for cleaning up
> residual pointers.
Outside the "if (count)" statement? Yes. I think you have this above in
the "code below" section, right?
Thanks,
Liam
* Peng Zhang <[email protected]> [231005 11:56]:
>
>
> 在 2023/10/5 03:53, Liam R. Howlett 写道:
> > * Peng Zhang <[email protected]> [231004 05:10]:
> > >
> > >
> > > 在 2023/10/4 02:46, Liam R. Howlett 写道:
> > > > * Peng Zhang <[email protected]> [230924 23:58]:
> > > > > In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
> > > > > directly replacing the entries of VMAs in the new maple tree can result
> > > > > in better performance. __mt_dup() uses DFS pre-order to duplicate the
> > > > > maple tree, so it is very efficient. The average time complexity of
> > > > > duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
> > > > > effect is proportional to the number of VMAs.
> > > >
> > > > I am not confident in the big O calculations here. Although the addition
> > > > of the tree is reduced, adding a VMA still needs to create the nodes
> > > > above it - which are a function of n. How did you get O(n * log(n)) for
> > > > the existing fork?
> > > >
> > > > I would think your new algorithm is n * log(n/16), while the
> > > > previous was n * log(n/16) * f(n). Where f(n) would be something
> > > > to do with the decision to split/rebalance in bulk insert mode.
> > > >
> > > > It's certainly a better algorithm to duplicate trees, but I don't think
> > > > it is O(n). Can you please explain?
> > >
> > > The following is a non-professional analysis of the algorithm.
> > >
> > > Let's first analyze the average time complexity of the new algorithm, as
> > > it is relatively easy to analyze. The maximum number of branches for
> > > internal nodes in a maple tree in allocation mode is 10. However, to
> > > simplify the analysis, we will not consider this case and assume that
> > > all nodes have a maximum of 16 branches.
> > >
> > > The new algorithm assumes that there is no case where a VMA with the
> > > VM_DONTCOPY flag is deleted. If such a case exists, this analysis cannot
> > > be applied.
> > >
> > > The operations of the new algorithm consist of three parts:
> > >
> > > 1. DFS traversal of each node in the source tree
> > > 2. For each node in the source tree, create a copy and construct a new
> > > node
> > > 3. Traverse the new tree using mas_find() and replace each element
> > >
> > > If there are a total of n elements in the maple tree, we can conclude
> > > that there are n/16 leaf nodes. Regarding the second-to-last level, we
> > > can conclude that there are n/16^2 nodes. The total number of nodes in
> > > the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1.
> > > This is a geometric progression with a total of log base 16 of n terms.
> > > According to the formula for the sum of a geometric progression, the sum
> > > is (n-1)/15. So, this tree has a total of (n-1)/15 nodes and
> > > (n-1)/15 - 1 edges.
> > >
> > > For the operations in the first part of this algorithm, since DFS
> > > traverses each edge twice, the time complexity would be
> > > 2*((n-1)/15 - 1).
> > >
> > > For the second part, each operation involves copying a node and making
> > > necessary modifications. Therefore, the time complexity is
> > > 16*(n-1)/15.
> > >
> > > For the third part, we use mas_find() to traverse and replace each
> > > element, which is essentially similar to the combination of the first
> > > and second parts. mas_find() traverses all nodes and within each node,
> > > it iterates over all elements and performs replacements. The time
> > > complexity of traversing the nodes is 2*((n-1)/15 - 1), and for all
> > > nodes, the time complexity of replacing all their elements is
> > > 16*(n-1)/15.
> > >
> > > By ignoring all constant factors, each of the three parts of the
> > > algorithm has a time complexity of O(n). Therefore, this new algorithm
> > > is O(n).
> >
> > Thanks for the detailed analysis! I didn't mean to cause so much work
> > with this question. I wanted to know so that future work could rely on
> > this calculation to demonstrate if it is worth implementing without
> > going through the effort of coding and benchmarking - after all, this
> > commit message will most likely be examined during that process.
> >
> > I asked because O(n) vs O(n*log(n)) doesn't seem to fit with your
> > benchmarking.
> It may not be well reflected in the benchmarking of fork() because all
> the aforementioned time complexity analysis is related to the part
> involving the maple tree, specifically the time complexity of
> constructing a new maple tree. However, fork() also includes many other
> behaviors.
The forking is allocating VMAs, etc but all a 1-1 mapping per VMA so it
should be linear, if not near-linear. There is some setup time involved
with the mm struct too, but that should become less as more VMAs are
added per fork.
> >
> > >
> > > The exact time complexity of the old algorithm is difficult to analyze.
> > > I can only provide an upper bound estimation. There are two possible
> > > scenarios for each insertion:
> > >
> > > 1. Appending at the end of a node.
> > > 2. Splitting nodes multiple times.
> > >
> > > For the first scenario, the individual operation has a time complexity
> > > of O(1). As for the second scenario, it involves node splitting. The
> > > challenge lies in determining which insertions trigger splits and how
> > > many splits occur each time, which is difficult to calculate. In the
> > > worst-case scenario, each insertion requires splitting the tree's height
> > > log(n) times. Assuming every insertion is in the worst-case scenario,
> > > the time complexity would be n*log(n). However, not every insertion
> > > requires splitting, and the number of splits each time may not
> > > necessarily be log(n). Therefore, this is an estimation of the upper
> > > bound.
> >
> > Saying every insert causes a split and adding in n*log(n) is more than
> > an over estimation. At worst there is some n + n/16 * log(n) going on
> > there.
> >
> > During the building of a tree, we are in bulk insert mode. This favours
> > balancing the tree to the left to maximize the number of inserts being
> > append operations. The algorithm inserts as many to the left as we can
> > leaving the minimum number on the right.
> >
> > We also reduce the number of splits by pushing data to the left whenever
> > possible, at every level.
> Yes, but I don't think pushing data would occur when inserting in
> ascending order in bulk mode because the left nodes are all full, while
> there are no nodes on the right side. However, I'm not entirely certain
> about this since I only briefly looked at the implementation of this
> part.
They are not full, the right node has enough entries to have a
sufficient node, so the left node will have that many spaces for push.
mab_calc_split():
if (unlikely((mas->mas_flags & MA_STATE_BULK))) {
*mid_split = 0;
split = b_end - mt_min_slots[bn->type];
> >
> >
> > > >
> > > > >
> > > > > As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
> > > > > fails, there will be a portion of VMAs that have not been duplicated in
> > > > > the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
> > > > > To solve this problem, undo_dup_mmap() is introduced to handle the failure
> > > > > of dup_mmap(). I have carefully tested the failure path and so far it
> > > > > seems there are no issues.
> > > > >
> > > > > There is a "spawn" in byte-unixbench[1], which can be used to test the
> > > > > performance of fork(). I modified it slightly to make it work with
> > > > > different number of VMAs.
> > > > >
> > > > > Below are the test results. By default, there are 21 VMAs. The first row
> > > > > shows the number of additional VMAs added on top of the default. The last
> > > > > two rows show the number of fork() calls per ten seconds. The test results
> > > > > were obtained with CPU binding to avoid scheduler load balancing that
> > > > > could cause unstable results. There are still some fluctuations in the
> > > > > test results, but at least they are better than the original performance.
> > > > >
> > > > > Increment of VMAs: 0 100 200 400 800 1600 3200 6400
> > > > > next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
> > > > > Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
> > > > > +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
> > delta 4179 10502 12592 11461 8972 5310 2935 1622
> >
> > Looking at this data, it is difficult to see what is going on because
> > there is a doubling of the VMAs per fork per column while the count is
> > forks per 10 seconds. So this table is really a logarithmic table with
> > increases growing by 10%. Adding the delta row makes it seem like the
> > number are not growing apart as I would expect.
> >
> > If we normalize this to VMAs per second by dividing the forks by 10,
> > then multiplying by the number of VMAs we get this:
> >
> > VMA Count: 21 121 221 421 821 1621 3221 6421
> > log(VMA) 1.32 2.00 2.30 2.60 2.90 3.20 3.36 3.81
> > next-20230921: 258349.8 928268.7 1215996.7 1464383.7 1707725.0 1842916.5 1420514.5 2044440.9
> > this: 267961.5 1057443.3 1496798.3 1949184.0 2446120.6 2704729.5 2102315.0 3086251.5
> > delta 9611.7 129174.6 280801.6 484800.3 738395.6 861813.0 681800.5 1041810.6
> >
> > The first thing that I noticed was that we hit some dip in the numbers
> > at 3221. I first thought that might be something else running on the
> > host machine, but both runs are affected by around the same percent.
> >
> > Here, we do see the delta growing apart, but peaking in growth around
> > 821 VMAs. Again that 3221 number is out of line.
> >
> > If we discard 21 and anything above 1621, we still see both lines are
> > asymptotic curves. I would expect that the new algorithm would be more
> > linear to represent O(n), but there is certainly a curve when graphed
> > with a normalized X-axis. The older algorithm, O(n*log(n)) should be
> > the opposite curve all together, and with a diminishing return, but it
> > seems the more elements we have, the more operations we can perform in a
> > second.
> Thank you for your detailed analysis.
>
> So, are you expecting the transformed data to be close to a constant
> value?
I would expect it to increase linearly, but it's a curve. Also, it
seems that both methods are near the identical curve, including the dip
at 3221. I expect the new method to have a different curve, especially
at the higher numbers where the fork() overhead is much less, but it
seems they both curve asymptotically. That is, they seen to be the same
complexity related to n, but with different constants.
> Please note that besides constructing a new maple tree, there are many
> other operations in fork(). As the number of VMAs increases, the number
> of fork() calls decreases. Therefore, the overall cost spent on other
> operations becomes smaller, while the cost spent on duplicating VMAs
> increases. That's why this data grows with the increase of VMAs. I
> speculate that if the number of VMAs is large enough to neglect the time
> spent on other operations in fork(), this data will approach a constant
> value.
If it were the other parts of fork() causing the non-linear growth, then
I would expect 800 -> 1600 to increase to +53% instead of +46%, and if
we were hitting the limit of fork affecting the data, then I would
expect the delta of VMAs/second to not be so high at the upper 6421 -
both algorithms have more room to get more performance at least until
6421 VMAs/fork.
>
> If we want to achieve the expected curve, I think we should simulate the
> process of constructing the maple tree in user space to avoid the impact
> of other operations in fork(), just like in the current bench_forking().
> >
> > Thinking about what is going on here, I cannot come up with a reason
> > that there would be a curve to the line at all. If we took more
> > measurements, I would think the samples would be an ever-increasing line
> > with variability for some function of 16 - a saw toothed increasing
> > line. At least, until an upper limit is reached. We can see that the
> > upper limit was still not achieved at 1621 since 6421 is higher for both
> > runs, but a curve is evident on both methods, which suggests something
> > else is a significant contributor.
> >
> > I would think each VMA requires the same amount of work, so a constant.
> > The allocations would again, be some function that would linearly
> > increase with the existing method over-estimating by a huge number of
> > nodes.
> >
> > I'm not trying to nitpick here, but it is important to be accurate in
> > the statements because it may alter choices on how to proceed in
> > improving this performance later. It may be others looking through
> > these commit messages to see if something can be improved.
> Thank you for pointing that out. I will try to describe it more
> accurately in the commit log and see if I can measure the expected curve
> in user space.
> >
> > I also feel like your notes on your algorithm are worth including in the
> > commit because it could prove rather valuable if we revisit forking in
> > the future.
> Do you mean that I should write the analysis of the time complexity of
> the new algorithm in the commit log?
Yes, I think it's worth capturing. What do you think?
> >
> > The more I look at this, the more questions I have that I cannot answer.
> > One thing we can see is that the new method is faster in this
> > micro-benchmark.
> Yes. It should be noted that in the field of computer science, if the
> test results don't align with the expected mathematical calculations,
> it indicates an error in the calculations. This is because accurate
> calculations will always be reflected in the test results. ????
> >
> > > > >
> > > > > [1] https://github.com/kdlucas/byte-unixbench/tree/master
> > > > >
> > > > > Signed-off-by: Peng Zhang <[email protected]>
> > > > > ---
> > > > > include/linux/mm.h | 1 +
> > > > > kernel/fork.c | 34 ++++++++++++++++++++----------
> > > > > mm/internal.h | 3 ++-
> > > > > mm/memory.c | 7 ++++---
> > > > > mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
> > > > > 5 files changed, 80 insertions(+), 17 deletions(-)
> > > > >
> > > > > diff --git a/include/linux/mm.h b/include/linux/mm.h
> > > > > index 1f1d0d6b8f20..10c59dc7ffaa 100644
> > > > > --- a/include/linux/mm.h
> > > > > +++ b/include/linux/mm.h
> > > > > @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
> > > > > extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
> > > > > unsigned long addr, unsigned long len, pgoff_t pgoff,
> > > > > bool *need_rmap_locks);
> > > > > +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
> > > > > extern void exit_mmap(struct mm_struct *);
> > > > > static inline int check_data_rlimit(unsigned long rlim,
> > > > > diff --git a/kernel/fork.c b/kernel/fork.c
> > > > > index 7ae36c2e7290..2f3d83e89fe6 100644
> > > > > --- a/kernel/fork.c
> > > > > +++ b/kernel/fork.c
> > > > > @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > int retval;
> > > > > unsigned long charge = 0;
> > > > > LIST_HEAD(uf);
> > > > > - VMA_ITERATOR(old_vmi, oldmm, 0);
> > > > > VMA_ITERATOR(vmi, mm, 0);
> > > > > uprobe_start_dup_mmap();
> > > > > @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > goto out;
> > > > > khugepaged_fork(mm, oldmm);
> > > > > - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
> > > > > - if (retval)
> > > > > + /* Use __mt_dup() to efficiently build an identical maple tree. */
> > > > > + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
> > > > > + if (unlikely(retval))
> > > > > goto out;
> > > > > mt_clear_in_rcu(vmi.mas.tree);
> > > > > - for_each_vma(old_vmi, mpnt) {
> > > > > + for_each_vma(vmi, mpnt) {
> > > > > struct file *file;
> > > > > vma_start_write(mpnt);
> > > > > if (mpnt->vm_flags & VM_DONTCOPY) {
> > > > > + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
> > > > > +
> > > > > + /* If failed, undo all completed duplications. */
> > > > > + if (unlikely(mas_is_err(&vmi.mas))) {
> > > > > + retval = xa_err(vmi.mas.node);
> > > > > + goto loop_out;
> > > > > + }
> > > > > +
> > > > > vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
> > > > > continue;
> > > > > }
> > > > > @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > if (is_vm_hugetlb_page(tmp))
> > > > > hugetlb_dup_vma_private(tmp);
> > > > > - /* Link the vma into the MT */
> > > > > - if (vma_iter_bulk_store(&vmi, tmp))
> > > > > - goto fail_nomem_vmi_store;
> > > > > + /*
> > > > > + * Link the vma into the MT. After using __mt_dup(), memory
> > > > > + * allocation is not necessary here, so it cannot fail.
> > > > > + */
> > > > > + mas_store(&vmi.mas, tmp);
> > > > > mm->map_count++;
> > > > > if (!(tmp->vm_flags & VM_WIPEONFORK))
> > > > > @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > if (tmp->vm_ops && tmp->vm_ops->open)
> > > > > tmp->vm_ops->open(tmp);
> > > > > - if (retval)
> > > > > + if (retval) {
> > > > > + mpnt = vma_next(&vmi);
> > > > > goto loop_out;
> > > > > + }
> > > > > }
> > > > > /* a new mm has just been created */
> > > > > retval = arch_dup_mmap(oldmm, mm);
> > > > > loop_out:
> > > > > vma_iter_free(&vmi);
> > > > > - if (!retval)
> > > > > + if (likely(!retval))
> > > > > mt_set_in_rcu(vmi.mas.tree);
> > > > > + else
> > > > > + undo_dup_mmap(mm, mpnt);
> > > > > out:
> > > > > mmap_write_unlock(mm);
> > > > > flush_tlb_mm(oldmm);
> > > > > @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > uprobe_end_dup_mmap();
> > > > > return retval;
> > > > > -fail_nomem_vmi_store:
> > > > > - unlink_anon_vmas(tmp);
> > > > > fail_nomem_anon_vma_fork:
> > > > > mpol_put(vma_policy(tmp));
> > > > > fail_nomem_policy:
> > > > > diff --git a/mm/internal.h b/mm/internal.h
> > > > > index 7a961d12b088..288ec81770cb 100644
> > > > > --- a/mm/internal.h
> > > > > +++ b/mm/internal.h
> > > > > @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
> > > > > void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > struct vm_area_struct *start_vma, unsigned long floor,
> > > > > - unsigned long ceiling, bool mm_wr_locked);
> > > > > + unsigned long ceiling, unsigned long tree_end,
> > > > > + bool mm_wr_locked);
> > > > > void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
> > > > > struct zap_details;
> > > > > diff --git a/mm/memory.c b/mm/memory.c
> > > > > index 983a40f8ee62..1fd66a0d5838 100644
> > > > > --- a/mm/memory.c
> > > > > +++ b/mm/memory.c
> > > > > @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
> > > > > void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > struct vm_area_struct *vma, unsigned long floor,
> > > > > - unsigned long ceiling, bool mm_wr_locked)
> > > > > + unsigned long ceiling, unsigned long tree_end,
> > > > > + bool mm_wr_locked)
> > > > > {
> > > > > do {
> > > > > unsigned long addr = vma->vm_start;
> > > > > @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
> > > > > * be 0. This will underflow and is okay.
> > > > > */
> > > > > - next = mas_find(mas, ceiling - 1);
> > > > > + next = mas_find(mas, tree_end - 1);
> > > > > /*
> > > > > * Hide vma from rmap and truncate_pagecache before freeing
> > > > > @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > while (next && next->vm_start <= vma->vm_end + PMD_SIZE
> > > > > && !is_vm_hugetlb_page(next)) {
> > > > > vma = next;
> > > > > - next = mas_find(mas, ceiling - 1);
> > > > > + next = mas_find(mas, tree_end - 1);
> > > > > if (mm_wr_locked)
> > > > > vma_start_write(vma);
> > > > > unlink_anon_vmas(vma);
> > > > > diff --git a/mm/mmap.c b/mm/mmap.c
> > > > > index 2ad950f773e4..daed3b423124 100644
> > > > > --- a/mm/mmap.c
> > > > > +++ b/mm/mmap.c
> > > > > @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
> > > > > mas_set(mas, mt_start);
> > > > > free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
> > > > > next ? next->vm_start : USER_PGTABLES_CEILING,
> > > > > - mm_wr_locked);
> > > > > + tree_end, mm_wr_locked);
> > > > > tlb_finish_mmu(&tlb);
> > > > > }
> > > > > @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
> > > > > }
> > > > > EXPORT_SYMBOL(vm_brk);
> > > > > +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
> > > > > +{
> > > > > + unsigned long tree_end;
> > > > > + VMA_ITERATOR(vmi, mm, 0);
> > > > > + struct vm_area_struct *vma;
> > > > > + unsigned long nr_accounted = 0;
> > > > > + int count = 0;
> > > > > +
> > > > > + /*
> > > > > + * vma_end points to the first VMA that has not been duplicated. We need
> > > > > + * to unmap all VMAs before it.
> > > > > + * If vma_end is NULL, it means that all VMAs in the maple tree have
> > > > > + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
> > > > > + * when using it.
> > > > > + */
> > > > > + if (vma_end) {
> > > > > + tree_end = vma_end->vm_start;
> > > > > + if (tree_end == 0)
> > > > > + goto destroy;
> > > > > + } else
> > > > > + tree_end = 0;
You need to enclose this statement to meet the coding style. You could
just set tree_end = 0 at the start of the function instead, actually I
think tree_end = USER_PGTABLES_CEILING unless there is a vma_end.
> > > > > +
> > > > > + vma = mas_find(&vmi.mas, tree_end - 1);
vma = vma_find(&vmi, tree_end);
> > > > > +
> > > > > + if (vma) {
Probably would be cleaner to jump to destroy here too:
if (!vma)
goto destroy;
> > > > > + arch_unmap(mm, vma->vm_start, tree_end);
> > > > > + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
> > > > > + tree_end, true);
> > > >
> > > > next is vma_end, as per your comment above. Using next = vma_end allows
> > > > you to avoid adding another argument to free_pgtables().
> > > Unfortunately, it cannot be done this way. I fell into this trap before,
> > > and it caused incomplete page table cleanup. To solve this problem, the
> > > only solution I can think of right now is to add an additional
> > > parameter.
> > >
> > > free_pgtables() will be called in unmap_region() to free the page table,
> > > like this:
> > >
> > > free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
> > > next ? next->vm_start : USER_PGTABLES_CEILING,
> > > mm_wr_locked);
> > >
> > > The problem is with 'next'. Our 'vma_end' does not exist in the actual
> > > mmap because it has not been duplicated and cannot be used as 'next'.
> > > If there is a real 'next', we can use 'next->vm_start' as the ceiling,
> > > which is not a problem. If there is no 'next' (next is 'vma_end'), we
> > > can only use 'USER_PGTABLES_CEILING' as the ceiling. Using
> > > 'vma_end->vm_start' as the ceiling will cause the page table not to be
> > > fully freed, which may be related to alignment in 'free_pgd_range()'. To
> > > solve this problem, we have to introduce 'tree_end', and separating
> > > 'tree_end' and 'ceiling' can solve this problem.
> >
> > Can you just use ceiling? That is, just not pass in next and keep the
> > code as-is? This is how exit_mmap() does it and should avoid any
> > alignment issues. I assume you tried that and something went wrong as
> > well?
> I tried that, but it didn't work either. In free_pgtables(), the
> following line of code is used to iterate over VMAs:
> mas_find(mas, ceiling - 1);
> If next is passed as NULL, ceiling will be 0, resulting in iterating
> over all the VMAs in the maple tree, including the last portion that was
> not duplicated.
If vma_end is NULL, it means that all VMAs in the maple tree have been
duplicated, so shouldn't the correct action in this case be freeing up
to ceiling?
If it isn't null, then vma_end->vm_start should work as the end of the
area to free.
With your mas_find(mas, tree_end - 1), then the vma_end will be avoided,
but free_pgd_range() will use ceiling anyways:
free_pgd_range(tlb, addr, vma->vm_end, floor, next ? next->vm_start : ceiling);
Passing in vma_end as next to unmap_region() functions in my testing
without adding arguments to free_pgtables().
How are you producing the accounting issue you mention above? Maybe I
missed something?
> >
> > >
> > > >
> > > > > +
> > > > > + mas_set(&vmi.mas, vma->vm_end);
vma_iter_set(&vmi, vma->vm_end);
> > > > > + do {
> > > > > + if (vma->vm_flags & VM_ACCOUNT)
> > > > > + nr_accounted += vma_pages(vma);
> > > > > + remove_vma(vma, true);
> > > > > + count++;
> > > > > + cond_resched();
> > > > > + vma = mas_find(&vmi.mas, tree_end - 1);
> > > > > + } while (vma != NULL);
You can write this as:
do { ... } for_each_vma_range(vmi, vma, tree_end);
> > > > > +
> > > > > + BUG_ON(count != mm->map_count);
> > > > > +
> > > > > + vm_unacct_memory(nr_accounted);
> > > > > + }
> > > > > +
> > > > > +destroy:
> > > > > + __mt_destroy(&mm->mm_mt);
> > > > > +}
> > > > > +
> > > > > /* Release all mmaps. */
> > > > > void exit_mmap(struct mm_struct *mm)
> > > > > {
> > > > > @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
> > > > > mt_clear_in_rcu(&mm->mm_mt);
> > > > > mas_set(&mas, vma->vm_end);
> > > > > free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
> > > > > - USER_PGTABLES_CEILING, true);
> > > > > + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
> > > > > tlb_finish_mmu(&tlb);
> > > > > /*
> > > > > --
> > > > > 2.20.1
> > > > >
> > > >
> > >
> >
* Liam R. Howlett <[email protected]> [231006 21:11]:
> * Peng Zhang <[email protected]> [231005 11:56]:
> >
> >
> > 在 2023/10/5 03:53, Liam R. Howlett 写道:
> > > * Peng Zhang <[email protected]> [231004 05:10]:
> > > >
> > > >
> > > > 在 2023/10/4 02:46, Liam R. Howlett 写道:
> > > > > * Peng Zhang <[email protected]> [230924 23:58]:
> > > > > > In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
> > > > > > directly replacing the entries of VMAs in the new maple tree can result
> > > > > > in better performance. __mt_dup() uses DFS pre-order to duplicate the
> > > > > > maple tree, so it is very efficient. The average time complexity of
> > > > > > duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
> > > > > > effect is proportional to the number of VMAs.
> > > > >
> > > > > I am not confident in the big O calculations here. Although the addition
> > > > > of the tree is reduced, adding a VMA still needs to create the nodes
> > > > > above it - which are a function of n. How did you get O(n * log(n)) for
> > > > > the existing fork?
> > > > >
> > > > > I would think your new algorithm is n * log(n/16), while the
> > > > > previous was n * log(n/16) * f(n). Where f(n) would be something
> > > > > to do with the decision to split/rebalance in bulk insert mode.
> > > > >
> > > > > It's certainly a better algorithm to duplicate trees, but I don't think
> > > > > it is O(n). Can you please explain?
> > > >
> > > > The following is a non-professional analysis of the algorithm.
> > > >
> > > > Let's first analyze the average time complexity of the new algorithm, as
> > > > it is relatively easy to analyze. The maximum number of branches for
> > > > internal nodes in a maple tree in allocation mode is 10. However, to
> > > > simplify the analysis, we will not consider this case and assume that
> > > > all nodes have a maximum of 16 branches.
> > > >
> > > > The new algorithm assumes that there is no case where a VMA with the
> > > > VM_DONTCOPY flag is deleted. If such a case exists, this analysis cannot
> > > > be applied.
> > > >
> > > > The operations of the new algorithm consist of three parts:
> > > >
> > > > 1. DFS traversal of each node in the source tree
> > > > 2. For each node in the source tree, create a copy and construct a new
> > > > node
> > > > 3. Traverse the new tree using mas_find() and replace each element
> > > >
> > > > If there are a total of n elements in the maple tree, we can conclude
> > > > that there are n/16 leaf nodes. Regarding the second-to-last level, we
> > > > can conclude that there are n/16^2 nodes. The total number of nodes in
> > > > the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1.
> > > > This is a geometric progression with a total of log base 16 of n terms.
> > > > According to the formula for the sum of a geometric progression, the sum
> > > > is (n-1)/15. So, this tree has a total of (n-1)/15 nodes and
> > > > (n-1)/15 - 1 edges.
> > > >
> > > > For the operations in the first part of this algorithm, since DFS
> > > > traverses each edge twice, the time complexity would be
> > > > 2*((n-1)/15 - 1).
> > > >
> > > > For the second part, each operation involves copying a node and making
> > > > necessary modifications. Therefore, the time complexity is
> > > > 16*(n-1)/15.
> > > >
> > > > For the third part, we use mas_find() to traverse and replace each
> > > > element, which is essentially similar to the combination of the first
> > > > and second parts. mas_find() traverses all nodes and within each node,
> > > > it iterates over all elements and performs replacements. The time
> > > > complexity of traversing the nodes is 2*((n-1)/15 - 1), and for all
> > > > nodes, the time complexity of replacing all their elements is
> > > > 16*(n-1)/15.
> > > >
> > > > By ignoring all constant factors, each of the three parts of the
> > > > algorithm has a time complexity of O(n). Therefore, this new algorithm
> > > > is O(n).
> > >
> > > Thanks for the detailed analysis! I didn't mean to cause so much work
> > > with this question. I wanted to know so that future work could rely on
> > > this calculation to demonstrate if it is worth implementing without
> > > going through the effort of coding and benchmarking - after all, this
> > > commit message will most likely be examined during that process.
> > >
> > > I asked because O(n) vs O(n*log(n)) doesn't seem to fit with your
> > > benchmarking.
> > It may not be well reflected in the benchmarking of fork() because all
> > the aforementioned time complexity analysis is related to the part
> > involving the maple tree, specifically the time complexity of
> > constructing a new maple tree. However, fork() also includes many other
> > behaviors.
>
> The forking is allocating VMAs, etc but all a 1-1 mapping per VMA so it
> should be linear, if not near-linear. There is some setup time involved
> with the mm struct too, but that should become less as more VMAs are
> added per fork.
>
> > >
> > > >
> > > > The exact time complexity of the old algorithm is difficult to analyze.
> > > > I can only provide an upper bound estimation. There are two possible
> > > > scenarios for each insertion:
> > > >
> > > > 1. Appending at the end of a node.
> > > > 2. Splitting nodes multiple times.
> > > >
> > > > For the first scenario, the individual operation has a time complexity
> > > > of O(1). As for the second scenario, it involves node splitting. The
> > > > challenge lies in determining which insertions trigger splits and how
> > > > many splits occur each time, which is difficult to calculate. In the
> > > > worst-case scenario, each insertion requires splitting the tree's height
> > > > log(n) times. Assuming every insertion is in the worst-case scenario,
> > > > the time complexity would be n*log(n). However, not every insertion
> > > > requires splitting, and the number of splits each time may not
> > > > necessarily be log(n). Therefore, this is an estimation of the upper
> > > > bound.
> > >
> > > Saying every insert causes a split and adding in n*log(n) is more than
> > > an over estimation. At worst there is some n + n/16 * log(n) going on
> > > there.
> > >
> > > During the building of a tree, we are in bulk insert mode. This favours
> > > balancing the tree to the left to maximize the number of inserts being
> > > append operations. The algorithm inserts as many to the left as we can
> > > leaving the minimum number on the right.
> > >
> > > We also reduce the number of splits by pushing data to the left whenever
> > > possible, at every level.
> > Yes, but I don't think pushing data would occur when inserting in
> > ascending order in bulk mode because the left nodes are all full, while
> > there are no nodes on the right side. However, I'm not entirely certain
> > about this since I only briefly looked at the implementation of this
> > part.
>
> They are not full, the right node has enough entries to have a
> sufficient node, so the left node will have that many spaces for push.
> mab_calc_split():
> if (unlikely((mas->mas_flags & MA_STATE_BULK))) {
> *mid_split = 0;
> split = b_end - mt_min_slots[bn->type];
>
> > >
> > >
> > > > >
> > > > > >
> > > > > > As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
> > > > > > fails, there will be a portion of VMAs that have not been duplicated in
> > > > > > the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
> > > > > > To solve this problem, undo_dup_mmap() is introduced to handle the failure
> > > > > > of dup_mmap(). I have carefully tested the failure path and so far it
> > > > > > seems there are no issues.
> > > > > >
> > > > > > There is a "spawn" in byte-unixbench[1], which can be used to test the
> > > > > > performance of fork(). I modified it slightly to make it work with
> > > > > > different number of VMAs.
> > > > > >
> > > > > > Below are the test results. By default, there are 21 VMAs. The first row
> > > > > > shows the number of additional VMAs added on top of the default. The last
> > > > > > two rows show the number of fork() calls per ten seconds. The test results
> > > > > > were obtained with CPU binding to avoid scheduler load balancing that
> > > > > > could cause unstable results. There are still some fluctuations in the
> > > > > > test results, but at least they are better than the original performance.
> > > > > >
> > > > > > Increment of VMAs: 0 100 200 400 800 1600 3200 6400
> > > > > > next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
> > > > > > Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
> > > > > > +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
> > > delta 4179 10502 12592 11461 8972 5310 2935 1622
> > >
> > > Looking at this data, it is difficult to see what is going on because
> > > there is a doubling of the VMAs per fork per column while the count is
> > > forks per 10 seconds. So this table is really a logarithmic table with
> > > increases growing by 10%. Adding the delta row makes it seem like the
> > > number are not growing apart as I would expect.
> > >
> > > If we normalize this to VMAs per second by dividing the forks by 10,
> > > then multiplying by the number of VMAs we get this:
> > >
> > > VMA Count: 21 121 221 421 821 1621 3221 6421
> > > log(VMA) 1.32 2.00 2.30 2.60 2.90 3.20 3.36 3.81
> > > next-20230921: 258349.8 928268.7 1215996.7 1464383.7 1707725.0 1842916.5 1420514.5 2044440.9
> > > this: 267961.5 1057443.3 1496798.3 1949184.0 2446120.6 2704729.5 2102315.0 3086251.5
> > > delta 9611.7 129174.6 280801.6 484800.3 738395.6 861813.0 681800.5 1041810.6
> > >
> > > The first thing that I noticed was that we hit some dip in the numbers
> > > at 3221. I first thought that might be something else running on the
> > > host machine, but both runs are affected by around the same percent.
> > >
> > > Here, we do see the delta growing apart, but peaking in growth around
> > > 821 VMAs. Again that 3221 number is out of line.
> > >
> > > If we discard 21 and anything above 1621, we still see both lines are
> > > asymptotic curves. I would expect that the new algorithm would be more
> > > linear to represent O(n), but there is certainly a curve when graphed
> > > with a normalized X-axis. The older algorithm, O(n*log(n)) should be
> > > the opposite curve all together, and with a diminishing return, but it
> > > seems the more elements we have, the more operations we can perform in a
> > > second.
> > Thank you for your detailed analysis.
> >
> > So, are you expecting the transformed data to be close to a constant
> > value?
>
> I would expect it to increase linearly, but it's a curve. Also, it
> seems that both methods are near the identical curve, including the dip
> at 3221. I expect the new method to have a different curve, especially
> at the higher numbers where the fork() overhead is much less, but it
> seems they both curve asymptotically. That is, they seen to be the same
> complexity related to n, but with different constants.
>
> > Please note that besides constructing a new maple tree, there are many
> > other operations in fork(). As the number of VMAs increases, the number
> > of fork() calls decreases. Therefore, the overall cost spent on other
> > operations becomes smaller, while the cost spent on duplicating VMAs
> > increases. That's why this data grows with the increase of VMAs. I
> > speculate that if the number of VMAs is large enough to neglect the time
> > spent on other operations in fork(), this data will approach a constant
> > value.
>
> If it were the other parts of fork() causing the non-linear growth, then
> I would expect 800 -> 1600 to increase to +53% instead of +46%, and if
> we were hitting the limit of fork affecting the data, then I would
> expect the delta of VMAs/second to not be so high at the upper 6421 -
> both algorithms have more room to get more performance at least until
> 6421 VMAs/fork.
>
> >
> > If we want to achieve the expected curve, I think we should simulate the
> > process of constructing the maple tree in user space to avoid the impact
> > of other operations in fork(), just like in the current bench_forking().
> > >
> > > Thinking about what is going on here, I cannot come up with a reason
> > > that there would be a curve to the line at all. If we took more
> > > measurements, I would think the samples would be an ever-increasing line
> > > with variability for some function of 16 - a saw toothed increasing
> > > line. At least, until an upper limit is reached. We can see that the
> > > upper limit was still not achieved at 1621 since 6421 is higher for both
> > > runs, but a curve is evident on both methods, which suggests something
> > > else is a significant contributor.
> > >
> > > I would think each VMA requires the same amount of work, so a constant.
> > > The allocations would again, be some function that would linearly
> > > increase with the existing method over-estimating by a huge number of
> > > nodes.
> > >
> > > I'm not trying to nitpick here, but it is important to be accurate in
> > > the statements because it may alter choices on how to proceed in
> > > improving this performance later. It may be others looking through
> > > these commit messages to see if something can be improved.
> > Thank you for pointing that out. I will try to describe it more
> > accurately in the commit log and see if I can measure the expected curve
> > in user space.
> > >
> > > I also feel like your notes on your algorithm are worth including in the
> > > commit because it could prove rather valuable if we revisit forking in
> > > the future.
> > Do you mean that I should write the analysis of the time complexity of
> > the new algorithm in the commit log?
>
> Yes, I think it's worth capturing. What do you think?
>
> > >
> > > The more I look at this, the more questions I have that I cannot answer.
> > > One thing we can see is that the new method is faster in this
> > > micro-benchmark.
> > Yes. It should be noted that in the field of computer science, if the
> > test results don't align with the expected mathematical calculations,
> > it indicates an error in the calculations. This is because accurate
> > calculations will always be reflected in the test results. ????
> > >
> > > > > >
> > > > > > [1] https://github.com/kdlucas/byte-unixbench/tree/master
> > > > > >
> > > > > > Signed-off-by: Peng Zhang <[email protected]>
> > > > > > ---
> > > > > > include/linux/mm.h | 1 +
> > > > > > kernel/fork.c | 34 ++++++++++++++++++++----------
> > > > > > mm/internal.h | 3 ++-
> > > > > > mm/memory.c | 7 ++++---
> > > > > > mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
> > > > > > 5 files changed, 80 insertions(+), 17 deletions(-)
> > > > > >
> > > > > > diff --git a/include/linux/mm.h b/include/linux/mm.h
> > > > > > index 1f1d0d6b8f20..10c59dc7ffaa 100644
> > > > > > --- a/include/linux/mm.h
> > > > > > +++ b/include/linux/mm.h
> > > > > > @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
> > > > > > extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
> > > > > > unsigned long addr, unsigned long len, pgoff_t pgoff,
> > > > > > bool *need_rmap_locks);
> > > > > > +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
> > > > > > extern void exit_mmap(struct mm_struct *);
> > > > > > static inline int check_data_rlimit(unsigned long rlim,
> > > > > > diff --git a/kernel/fork.c b/kernel/fork.c
> > > > > > index 7ae36c2e7290..2f3d83e89fe6 100644
> > > > > > --- a/kernel/fork.c
> > > > > > +++ b/kernel/fork.c
> > > > > > @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > > int retval;
> > > > > > unsigned long charge = 0;
> > > > > > LIST_HEAD(uf);
> > > > > > - VMA_ITERATOR(old_vmi, oldmm, 0);
> > > > > > VMA_ITERATOR(vmi, mm, 0);
> > > > > > uprobe_start_dup_mmap();
> > > > > > @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > > goto out;
> > > > > > khugepaged_fork(mm, oldmm);
> > > > > > - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
> > > > > > - if (retval)
> > > > > > + /* Use __mt_dup() to efficiently build an identical maple tree. */
> > > > > > + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
> > > > > > + if (unlikely(retval))
> > > > > > goto out;
> > > > > > mt_clear_in_rcu(vmi.mas.tree);
> > > > > > - for_each_vma(old_vmi, mpnt) {
> > > > > > + for_each_vma(vmi, mpnt) {
> > > > > > struct file *file;
> > > > > > vma_start_write(mpnt);
> > > > > > if (mpnt->vm_flags & VM_DONTCOPY) {
> > > > > > + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
> > > > > > +
> > > > > > + /* If failed, undo all completed duplications. */
> > > > > > + if (unlikely(mas_is_err(&vmi.mas))) {
> > > > > > + retval = xa_err(vmi.mas.node);
> > > > > > + goto loop_out;
> > > > > > + }
> > > > > > +
> > > > > > vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
> > > > > > continue;
> > > > > > }
> > > > > > @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > > if (is_vm_hugetlb_page(tmp))
> > > > > > hugetlb_dup_vma_private(tmp);
> > > > > > - /* Link the vma into the MT */
> > > > > > - if (vma_iter_bulk_store(&vmi, tmp))
> > > > > > - goto fail_nomem_vmi_store;
> > > > > > + /*
> > > > > > + * Link the vma into the MT. After using __mt_dup(), memory
> > > > > > + * allocation is not necessary here, so it cannot fail.
> > > > > > + */
> > > > > > + mas_store(&vmi.mas, tmp);
> > > > > > mm->map_count++;
> > > > > > if (!(tmp->vm_flags & VM_WIPEONFORK))
> > > > > > @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > > if (tmp->vm_ops && tmp->vm_ops->open)
> > > > > > tmp->vm_ops->open(tmp);
> > > > > > - if (retval)
> > > > > > + if (retval) {
> > > > > > + mpnt = vma_next(&vmi);
> > > > > > goto loop_out;
> > > > > > + }
> > > > > > }
> > > > > > /* a new mm has just been created */
> > > > > > retval = arch_dup_mmap(oldmm, mm);
> > > > > > loop_out:
> > > > > > vma_iter_free(&vmi);
> > > > > > - if (!retval)
> > > > > > + if (likely(!retval))
> > > > > > mt_set_in_rcu(vmi.mas.tree);
> > > > > > + else
> > > > > > + undo_dup_mmap(mm, mpnt);
> > > > > > out:
> > > > > > mmap_write_unlock(mm);
> > > > > > flush_tlb_mm(oldmm);
> > > > > > @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
> > > > > > uprobe_end_dup_mmap();
> > > > > > return retval;
> > > > > > -fail_nomem_vmi_store:
> > > > > > - unlink_anon_vmas(tmp);
> > > > > > fail_nomem_anon_vma_fork:
> > > > > > mpol_put(vma_policy(tmp));
> > > > > > fail_nomem_policy:
> > > > > > diff --git a/mm/internal.h b/mm/internal.h
> > > > > > index 7a961d12b088..288ec81770cb 100644
> > > > > > --- a/mm/internal.h
> > > > > > +++ b/mm/internal.h
> > > > > > @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
> > > > > > void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > > struct vm_area_struct *start_vma, unsigned long floor,
> > > > > > - unsigned long ceiling, bool mm_wr_locked);
> > > > > > + unsigned long ceiling, unsigned long tree_end,
> > > > > > + bool mm_wr_locked);
> > > > > > void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
> > > > > > struct zap_details;
> > > > > > diff --git a/mm/memory.c b/mm/memory.c
> > > > > > index 983a40f8ee62..1fd66a0d5838 100644
> > > > > > --- a/mm/memory.c
> > > > > > +++ b/mm/memory.c
> > > > > > @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
> > > > > > void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > > struct vm_area_struct *vma, unsigned long floor,
> > > > > > - unsigned long ceiling, bool mm_wr_locked)
> > > > > > + unsigned long ceiling, unsigned long tree_end,
> > > > > > + bool mm_wr_locked)
> > > > > > {
> > > > > > do {
> > > > > > unsigned long addr = vma->vm_start;
> > > > > > @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > > * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
> > > > > > * be 0. This will underflow and is okay.
> > > > > > */
> > > > > > - next = mas_find(mas, ceiling - 1);
> > > > > > + next = mas_find(mas, tree_end - 1);
> > > > > > /*
> > > > > > * Hide vma from rmap and truncate_pagecache before freeing
> > > > > > @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
> > > > > > while (next && next->vm_start <= vma->vm_end + PMD_SIZE
> > > > > > && !is_vm_hugetlb_page(next)) {
> > > > > > vma = next;
> > > > > > - next = mas_find(mas, ceiling - 1);
> > > > > > + next = mas_find(mas, tree_end - 1);
> > > > > > if (mm_wr_locked)
> > > > > > vma_start_write(vma);
> > > > > > unlink_anon_vmas(vma);
> > > > > > diff --git a/mm/mmap.c b/mm/mmap.c
> > > > > > index 2ad950f773e4..daed3b423124 100644
> > > > > > --- a/mm/mmap.c
> > > > > > +++ b/mm/mmap.c
> > > > > > @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
> > > > > > mas_set(mas, mt_start);
> > > > > > free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
> > > > > > next ? next->vm_start : USER_PGTABLES_CEILING,
> > > > > > - mm_wr_locked);
> > > > > > + tree_end, mm_wr_locked);
> > > > > > tlb_finish_mmu(&tlb);
> > > > > > }
> > > > > > @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
> > > > > > }
> > > > > > EXPORT_SYMBOL(vm_brk);
> > > > > > +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
> > > > > > +{
> > > > > > + unsigned long tree_end;
> > > > > > + VMA_ITERATOR(vmi, mm, 0);
> > > > > > + struct vm_area_struct *vma;
> > > > > > + unsigned long nr_accounted = 0;
> > > > > > + int count = 0;
> > > > > > +
> > > > > > + /*
> > > > > > + * vma_end points to the first VMA that has not been duplicated. We need
> > > > > > + * to unmap all VMAs before it.
> > > > > > + * If vma_end is NULL, it means that all VMAs in the maple tree have
> > > > > > + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
> > > > > > + * when using it.
> > > > > > + */
> > > > > > + if (vma_end) {
> > > > > > + tree_end = vma_end->vm_start;
> > > > > > + if (tree_end == 0)
> > > > > > + goto destroy;
> > > > > > + } else
> > > > > > + tree_end = 0;
>
> You need to enclose this statement to meet the coding style. You could
> just set tree_end = 0 at the start of the function instead, actually I
> think tree_end = USER_PGTABLES_CEILING unless there is a vma_end.
>
> > > > > > +
> > > > > > + vma = mas_find(&vmi.mas, tree_end - 1);
>
> vma = vma_find(&vmi, tree_end);
>
> > > > > > +
> > > > > > + if (vma) {
>
> Probably would be cleaner to jump to destroy here too:
> if (!vma)
> goto destroy;
>
> > > > > > + arch_unmap(mm, vma->vm_start, tree_end);
One more thing, it seems the maple state that is passed into
unmap_region() needs to point to the _next_ element, or the reset
doesn't work right between the unmap_vmas() and free_pgtables() call:
vma_iter_set(&vmi, vma->vm_end);
> > > > > > + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
> > > > > > + tree_end, true);
> > > > >
> > > > > next is vma_end, as per your comment above. Using next = vma_end allows
> > > > > you to avoid adding another argument to free_pgtables().
> > > > Unfortunately, it cannot be done this way. I fell into this trap before,
> > > > and it caused incomplete page table cleanup. To solve this problem, the
> > > > only solution I can think of right now is to add an additional
> > > > parameter.
> > > >
> > > > free_pgtables() will be called in unmap_region() to free the page table,
> > > > like this:
> > > >
> > > > free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
> > > > next ? next->vm_start : USER_PGTABLES_CEILING,
> > > > mm_wr_locked);
> > > >
> > > > The problem is with 'next'. Our 'vma_end' does not exist in the actual
> > > > mmap because it has not been duplicated and cannot be used as 'next'.
> > > > If there is a real 'next', we can use 'next->vm_start' as the ceiling,
> > > > which is not a problem. If there is no 'next' (next is 'vma_end'), we
> > > > can only use 'USER_PGTABLES_CEILING' as the ceiling. Using
> > > > 'vma_end->vm_start' as the ceiling will cause the page table not to be
> > > > fully freed, which may be related to alignment in 'free_pgd_range()'. To
> > > > solve this problem, we have to introduce 'tree_end', and separating
> > > > 'tree_end' and 'ceiling' can solve this problem.
> > >
> > > Can you just use ceiling? That is, just not pass in next and keep the
> > > code as-is? This is how exit_mmap() does it and should avoid any
> > > alignment issues. I assume you tried that and something went wrong as
> > > well?
> > I tried that, but it didn't work either. In free_pgtables(), the
> > following line of code is used to iterate over VMAs:
> > mas_find(mas, ceiling - 1);
> > If next is passed as NULL, ceiling will be 0, resulting in iterating
> > over all the VMAs in the maple tree, including the last portion that was
> > not duplicated.
>
> If vma_end is NULL, it means that all VMAs in the maple tree have been
> duplicated, so shouldn't the correct action in this case be freeing up
> to ceiling?
>
> If it isn't null, then vma_end->vm_start should work as the end of the
> area to free.
>
> With your mas_find(mas, tree_end - 1), then the vma_end will be avoided,
> but free_pgd_range() will use ceiling anyways:
>
> free_pgd_range(tlb, addr, vma->vm_end, floor, next ? next->vm_start : ceiling);
>
> Passing in vma_end as next to unmap_region() functions in my testing
> without adding arguments to free_pgtables().
>
> How are you producing the accounting issue you mention above? Maybe I
> missed something?
>
>
> > >
> > > >
> > > > >
> > > > > > +
> > > > > > + mas_set(&vmi.mas, vma->vm_end);
> vma_iter_set(&vmi, vma->vm_end);
> > > > > > + do {
> > > > > > + if (vma->vm_flags & VM_ACCOUNT)
> > > > > > + nr_accounted += vma_pages(vma);
> > > > > > + remove_vma(vma, true);
> > > > > > + count++;
> > > > > > + cond_resched();
> > > > > > + vma = mas_find(&vmi.mas, tree_end - 1);
> > > > > > + } while (vma != NULL);
>
> You can write this as:
> do { ... } for_each_vma_range(vmi, vma, tree_end);
>
> > > > > > +
> > > > > > + BUG_ON(count != mm->map_count);
> > > > > > +
> > > > > > + vm_unacct_memory(nr_accounted);
> > > > > > + }
> > > > > > +
> > > > > > +destroy:
> > > > > > + __mt_destroy(&mm->mm_mt);
> > > > > > +}
> > > > > > +
> > > > > > /* Release all mmaps. */
> > > > > > void exit_mmap(struct mm_struct *mm)
> > > > > > {
> > > > > > @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
> > > > > > mt_clear_in_rcu(&mm->mm_mt);
> > > > > > mas_set(&mas, vma->vm_end);
> > > > > > free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
> > > > > > - USER_PGTABLES_CEILING, true);
> > > > > > + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
> > > > > > tlb_finish_mmu(&tlb);
> > > > > > /*
> > > > > > --
> > > > > > 2.20.1
> > > > > >
> > > > >
> > > >
> > >
在 2023/10/7 09:32, Liam R. Howlett 写道:
...
>>>>
>>>>>>>
>>>>>>> [1] https://github.com/kdlucas/byte-unixbench/tree/master
>>>>>>>
>>>>>>> Signed-off-by: Peng Zhang <[email protected]>
>>>>>>> ---
>>>>>>> include/linux/mm.h | 1 +
>>>>>>> kernel/fork.c | 34 ++++++++++++++++++++----------
>>>>>>> mm/internal.h | 3 ++-
>>>>>>> mm/memory.c | 7 ++++---
>>>>>>> mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
>>>>>>> 5 files changed, 80 insertions(+), 17 deletions(-)
>>>>>>>
>>>>>>> diff --git a/include/linux/mm.h b/include/linux/mm.h
>>>>>>> index 1f1d0d6b8f20..10c59dc7ffaa 100644
>>>>>>> --- a/include/linux/mm.h
>>>>>>> +++ b/include/linux/mm.h
>>>>>>> @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
>>>>>>> extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
>>>>>>> unsigned long addr, unsigned long len, pgoff_t pgoff,
>>>>>>> bool *need_rmap_locks);
>>>>>>> +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
>>>>>>> extern void exit_mmap(struct mm_struct *);
>>>>>>> static inline int check_data_rlimit(unsigned long rlim,
>>>>>>> diff --git a/kernel/fork.c b/kernel/fork.c
>>>>>>> index 7ae36c2e7290..2f3d83e89fe6 100644
>>>>>>> --- a/kernel/fork.c
>>>>>>> +++ b/kernel/fork.c
>>>>>>> @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> int retval;
>>>>>>> unsigned long charge = 0;
>>>>>>> LIST_HEAD(uf);
>>>>>>> - VMA_ITERATOR(old_vmi, oldmm, 0);
>>>>>>> VMA_ITERATOR(vmi, mm, 0);
>>>>>>> uprobe_start_dup_mmap();
>>>>>>> @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> goto out;
>>>>>>> khugepaged_fork(mm, oldmm);
>>>>>>> - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
>>>>>>> - if (retval)
>>>>>>> + /* Use __mt_dup() to efficiently build an identical maple tree. */
>>>>>>> + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
>>>>>>> + if (unlikely(retval))
>>>>>>> goto out;
>>>>>>> mt_clear_in_rcu(vmi.mas.tree);
>>>>>>> - for_each_vma(old_vmi, mpnt) {
>>>>>>> + for_each_vma(vmi, mpnt) {
>>>>>>> struct file *file;
>>>>>>> vma_start_write(mpnt);
>>>>>>> if (mpnt->vm_flags & VM_DONTCOPY) {
>>>>>>> + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
>>>>>>> +
>>>>>>> + /* If failed, undo all completed duplications. */
>>>>>>> + if (unlikely(mas_is_err(&vmi.mas))) {
>>>>>>> + retval = xa_err(vmi.mas.node);
>>>>>>> + goto loop_out;
>>>>>>> + }
>>>>>>> +
>>>>>>> vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
>>>>>>> continue;
>>>>>>> }
>>>>>>> @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> if (is_vm_hugetlb_page(tmp))
>>>>>>> hugetlb_dup_vma_private(tmp);
>>>>>>> - /* Link the vma into the MT */
>>>>>>> - if (vma_iter_bulk_store(&vmi, tmp))
>>>>>>> - goto fail_nomem_vmi_store;
>>>>>>> + /*
>>>>>>> + * Link the vma into the MT. After using __mt_dup(), memory
>>>>>>> + * allocation is not necessary here, so it cannot fail.
>>>>>>> + */
>>>>>>> + mas_store(&vmi.mas, tmp);
>>>>>>> mm->map_count++;
>>>>>>> if (!(tmp->vm_flags & VM_WIPEONFORK))
>>>>>>> @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> if (tmp->vm_ops && tmp->vm_ops->open)
>>>>>>> tmp->vm_ops->open(tmp);
>>>>>>> - if (retval)
>>>>>>> + if (retval) {
>>>>>>> + mpnt = vma_next(&vmi);
>>>>>>> goto loop_out;
>>>>>>> + }
>>>>>>> }
>>>>>>> /* a new mm has just been created */
>>>>>>> retval = arch_dup_mmap(oldmm, mm);
>>>>>>> loop_out:
>>>>>>> vma_iter_free(&vmi);
>>>>>>> - if (!retval)
>>>>>>> + if (likely(!retval))
>>>>>>> mt_set_in_rcu(vmi.mas.tree);
>>>>>>> + else
>>>>>>> + undo_dup_mmap(mm, mpnt);
>>>>>>> out:
>>>>>>> mmap_write_unlock(mm);
>>>>>>> flush_tlb_mm(oldmm);
>>>>>>> @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> uprobe_end_dup_mmap();
>>>>>>> return retval;
>>>>>>> -fail_nomem_vmi_store:
>>>>>>> - unlink_anon_vmas(tmp);
>>>>>>> fail_nomem_anon_vma_fork:
>>>>>>> mpol_put(vma_policy(tmp));
>>>>>>> fail_nomem_policy:
>>>>>>> diff --git a/mm/internal.h b/mm/internal.h
>>>>>>> index 7a961d12b088..288ec81770cb 100644
>>>>>>> --- a/mm/internal.h
>>>>>>> +++ b/mm/internal.h
>>>>>>> @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
>>>>>>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> struct vm_area_struct *start_vma, unsigned long floor,
>>>>>>> - unsigned long ceiling, bool mm_wr_locked);
>>>>>>> + unsigned long ceiling, unsigned long tree_end,
>>>>>>> + bool mm_wr_locked);
>>>>>>> void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
>>>>>>> struct zap_details;
>>>>>>> diff --git a/mm/memory.c b/mm/memory.c
>>>>>>> index 983a40f8ee62..1fd66a0d5838 100644
>>>>>>> --- a/mm/memory.c
>>>>>>> +++ b/mm/memory.c
>>>>>>> @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
>>>>>>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> struct vm_area_struct *vma, unsigned long floor,
>>>>>>> - unsigned long ceiling, bool mm_wr_locked)
>>>>>>> + unsigned long ceiling, unsigned long tree_end,
>>>>>>> + bool mm_wr_locked)
>>>>>>> {
>>>>>>> do {
>>>>>>> unsigned long addr = vma->vm_start;
>>>>>>> @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
>>>>>>> * be 0. This will underflow and is okay.
>>>>>>> */
>>>>>>> - next = mas_find(mas, ceiling - 1);
>>>>>>> + next = mas_find(mas, tree_end - 1);
>>>>>>> /*
>>>>>>> * Hide vma from rmap and truncate_pagecache before freeing
>>>>>>> @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> while (next && next->vm_start <= vma->vm_end + PMD_SIZE
>>>>>>> && !is_vm_hugetlb_page(next)) {
>>>>>>> vma = next;
>>>>>>> - next = mas_find(mas, ceiling - 1);
>>>>>>> + next = mas_find(mas, tree_end - 1);
>>>>>>> if (mm_wr_locked)
>>>>>>> vma_start_write(vma);
>>>>>>> unlink_anon_vmas(vma);
>>>>>>> diff --git a/mm/mmap.c b/mm/mmap.c
>>>>>>> index 2ad950f773e4..daed3b423124 100644
>>>>>>> --- a/mm/mmap.c
>>>>>>> +++ b/mm/mmap.c
>>>>>>> @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
>>>>>>> mas_set(mas, mt_start);
>>>>>>> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
>>>>>>> next ? next->vm_start : USER_PGTABLES_CEILING,
>>>>>>> - mm_wr_locked);
>>>>>>> + tree_end, mm_wr_locked);
>>>>>>> tlb_finish_mmu(&tlb);
>>>>>>> }
>>>>>>> @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
>>>>>>> }
>>>>>>> EXPORT_SYMBOL(vm_brk);
>>>>>>> +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
>>>>>>> +{
>>>>>>> + unsigned long tree_end;
>>>>>>> + VMA_ITERATOR(vmi, mm, 0);
>>>>>>> + struct vm_area_struct *vma;
>>>>>>> + unsigned long nr_accounted = 0;
>>>>>>> + int count = 0;
>>>>>>> +
>>>>>>> + /*
>>>>>>> + * vma_end points to the first VMA that has not been duplicated. We need
>>>>>>> + * to unmap all VMAs before it.
>>>>>>> + * If vma_end is NULL, it means that all VMAs in the maple tree have
>>>>>>> + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
>>>>>>> + * when using it.
>>>>>>> + */
>>>>>>> + if (vma_end) {
>>>>>>> + tree_end = vma_end->vm_start;
>>>>>>> + if (tree_end == 0)
>>>>>>> + goto destroy;
>>>>>>> + } else
>>>>>>> + tree_end = 0;
>>
>> You need to enclose this statement to meet the coding style. You could
>> just set tree_end = 0 at the start of the function instead, actually I
>> think tree_end = USER_PGTABLES_CEILING unless there is a vma_end.
>>
>>>>>>> +
>>>>>>> + vma = mas_find(&vmi.mas, tree_end - 1);
>>
>> vma = vma_find(&vmi, tree_end);
>>
>>>>>>> +
>>>>>>> + if (vma) {
>>
>> Probably would be cleaner to jump to destroy here too:
>> if (!vma)
>> goto destroy;
>>
>>>>>>> + arch_unmap(mm, vma->vm_start, tree_end);
>
> One more thing, it seems the maple state that is passed into
> unmap_region() needs to point to the _next_ element, or the reset
> doesn't work right between the unmap_vmas() and free_pgtables() call:
>
> vma_iter_set(&vmi, vma->vm_end);
>
>
>>>>>>> + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
>>>>>>> + tree_end, true);
>>>>>>
>>>>>> next is vma_end, as per your comment above. Using next = vma_end allows
>>>>>> you to avoid adding another argument to free_pgtables().
>>>>> Unfortunately, it cannot be done this way. I fell into this trap before,
>>>>> and it caused incomplete page table cleanup. To solve this problem, the
>>>>> only solution I can think of right now is to add an additional
>>>>> parameter.
>>>>>
>>>>> free_pgtables() will be called in unmap_region() to free the page table,
>>>>> like this:
>>>>>
>>>>> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
>>>>> next ? next->vm_start : USER_PGTABLES_CEILING,
>>>>> mm_wr_locked);
>>>>>
>>>>> The problem is with 'next'. Our 'vma_end' does not exist in the actual
>>>>> mmap because it has not been duplicated and cannot be used as 'next'.
>>>>> If there is a real 'next', we can use 'next->vm_start' as the ceiling,
>>>>> which is not a problem. If there is no 'next' (next is 'vma_end'), we
>>>>> can only use 'USER_PGTABLES_CEILING' as the ceiling. Using
>>>>> 'vma_end->vm_start' as the ceiling will cause the page table not to be
>>>>> fully freed, which may be related to alignment in 'free_pgd_range()'. To
>>>>> solve this problem, we have to introduce 'tree_end', and separating
>>>>> 'tree_end' and 'ceiling' can solve this problem.
>>>>
>>>> Can you just use ceiling? That is, just not pass in next and keep the
>>>> code as-is? This is how exit_mmap() does it and should avoid any
>>>> alignment issues. I assume you tried that and something went wrong as
>>>> well?
>>> I tried that, but it didn't work either. In free_pgtables(), the
>>> following line of code is used to iterate over VMAs:
>>> mas_find(mas, ceiling - 1);
>>> If next is passed as NULL, ceiling will be 0, resulting in iterating
>>> over all the VMAs in the maple tree, including the last portion that was
>>> not duplicated.
>>
>> If vma_end is NULL, it means that all VMAs in the maple tree have been
>> duplicated, so shouldn't the correct action in this case be freeing up
>> to ceiling?
Yes, that's correct.
>>
>> If it isn't null, then vma_end->vm_start should work as the end of the
>> area to free.
But there's an issue here. I initially thought the same way, but the
behavior of free_pgtables() is very strange. For the last VMA, it seems
that the ceiling passed to free_pgd_range() must be
USER_PGTABLES_CEILING.
It cannot be used vma_end->vm_start as the ceiling, possibly due to the
peculiar alignment behavior in free_pgd_range().
The code is from free_pgd_range():
if (ceiling) {
ceiling &= PMD_MASK;
if (!ceiling)
return;
}
I suspect it is related to this part. The behavior differs when the
ceiling is equal to 0 or non-zero. However, I cannot comprehend all the
details here.
>>
>> With your mas_find(mas, tree_end - 1), then the vma_end will be avoided,
>> but free_pgd_range() will use ceiling anyways:
>>
>> free_pgd_range(tlb, addr, vma->vm_end, floor, next ? next->vm_start : ceiling);
>>
>> Passing in vma_end as next to unmap_region() functions in my testing
>> without adding arguments to free_pgtables().
>>
>> How are you producing the accounting issue you mention above? Maybe I
>> missed something?
You can apply the patch provided at the bottom, and then use the test
program in Attachment 1 to reproduce the issue.
In dmesg, the kernel will report the following error:
[ 14.829561] BUG: non-zero pgtables_bytes on freeing mm: 12288
[ 14.832445] BUG: non-zero pgtables_bytes on freeing mm: 12288
diff --git a/kernel/fork.c b/kernel/fork.c
index 5f24f6d68ea4..fcc66acac480 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -688,7 +688,11 @@ static __latent_entropy int dup_mmap(struct
mm_struct *mm,
vma_start_write(mpnt);
if (mpnt->vm_flags & VM_DONTCOPY) {
- mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
+ if (!strcmp(current->comm, "fork_test") && ktime_get_ns() % 2) {
+ vmi.mas.node = MA_ERROR(-ENOMEM);
+ } else {
+ mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
+ }
/* If failed, undo all completed duplications. */
if (unlikely(mas_is_err(&vmi.mas))) {
>>
>>
>>>>
>>>>>
>>>>>>
>>>>>>> +
>>>>>>> + mas_set(&vmi.mas, vma->vm_end);
>> vma_iter_set(&vmi, vma->vm_end);
>>>>>>> + do {
>>>>>>> + if (vma->vm_flags & VM_ACCOUNT)
>>>>>>> + nr_accounted += vma_pages(vma);
>>>>>>> + remove_vma(vma, true);
>>>>>>> + count++;
>>>>>>> + cond_resched();
>>>>>>> + vma = mas_find(&vmi.mas, tree_end - 1);
>>>>>>> + } while (vma != NULL);
>>
>> You can write this as:
>> do { ... } for_each_vma_range(vmi, vma, tree_end);
>>
>>>>>>> +
>>>>>>> + BUG_ON(count != mm->map_count);
>>>>>>> +
>>>>>>> + vm_unacct_memory(nr_accounted);
>>>>>>> + }
>>>>>>> +
>>>>>>> +destroy:
>>>>>>> + __mt_destroy(&mm->mm_mt);
>>>>>>> +}
>>>>>>> +
>>>>>>> /* Release all mmaps. */
>>>>>>> void exit_mmap(struct mm_struct *mm)
>>>>>>> {
>>>>>>> @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
>>>>>>> mt_clear_in_rcu(&mm->mm_mt);
>>>>>>> mas_set(&mas, vma->vm_end);
>>>>>>> free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
>>>>>>> - USER_PGTABLES_CEILING, true);
>>>>>>> + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
>>>>>>> tlb_finish_mmu(&tlb);
>>>>>>> /*
>>>>>>> --
>>>>>>> 2.20.1
>>>>>>>
>>>>>>
>>>>>
>>>>
>
在 2023/10/7 09:32, Liam R. Howlett 写道:
> * Liam R. Howlett <[email protected]> [231006 21:11]:
>> * Peng Zhang <[email protected]> [231005 11:56]:
>>>
>>>
>>> 在 2023/10/5 03:53, Liam R. Howlett 写道:
>>>> * Peng Zhang <[email protected]> [231004 05:10]:
>>>>>
>>>>>
>>>>> 在 2023/10/4 02:46, Liam R. Howlett 写道:
>>>>>> * Peng Zhang <[email protected]> [230924 23:58]:
>>>>>>> In dup_mmap(), using __mt_dup() to duplicate the old maple tree and then
>>>>>>> directly replacing the entries of VMAs in the new maple tree can result
>>>>>>> in better performance. __mt_dup() uses DFS pre-order to duplicate the
>>>>>>> maple tree, so it is very efficient. The average time complexity of
>>>>>>> duplicating VMAs is reduced from O(n * log(n)) to O(n). The optimization
>>>>>>> effect is proportional to the number of VMAs.
>>>>>>
>>>>>> I am not confident in the big O calculations here. Although the addition
>>>>>> of the tree is reduced, adding a VMA still needs to create the nodes
>>>>>> above it - which are a function of n. How did you get O(n * log(n)) for
>>>>>> the existing fork?
>>>>>>
>>>>>> I would think your new algorithm is n * log(n/16), while the
>>>>>> previous was n * log(n/16) * f(n). Where f(n) would be something
>>>>>> to do with the decision to split/rebalance in bulk insert mode.
>>>>>>
>>>>>> It's certainly a better algorithm to duplicate trees, but I don't think
>>>>>> it is O(n). Can you please explain?
>>>>>
>>>>> The following is a non-professional analysis of the algorithm.
>>>>>
>>>>> Let's first analyze the average time complexity of the new algorithm, as
>>>>> it is relatively easy to analyze. The maximum number of branches for
>>>>> internal nodes in a maple tree in allocation mode is 10. However, to
>>>>> simplify the analysis, we will not consider this case and assume that
>>>>> all nodes have a maximum of 16 branches.
>>>>>
>>>>> The new algorithm assumes that there is no case where a VMA with the
>>>>> VM_DONTCOPY flag is deleted. If such a case exists, this analysis cannot
>>>>> be applied.
>>>>>
>>>>> The operations of the new algorithm consist of three parts:
>>>>>
>>>>> 1. DFS traversal of each node in the source tree
>>>>> 2. For each node in the source tree, create a copy and construct a new
>>>>> node
>>>>> 3. Traverse the new tree using mas_find() and replace each element
>>>>>
>>>>> If there are a total of n elements in the maple tree, we can conclude
>>>>> that there are n/16 leaf nodes. Regarding the second-to-last level, we
>>>>> can conclude that there are n/16^2 nodes. The total number of nodes in
>>>>> the entire tree is given by the sum of n/16 + n/16^2 + n/16^3 + ... + 1.
>>>>> This is a geometric progression with a total of log base 16 of n terms.
>>>>> According to the formula for the sum of a geometric progression, the sum
>>>>> is (n-1)/15. So, this tree has a total of (n-1)/15 nodes and
>>>>> (n-1)/15 - 1 edges.
>>>>>
>>>>> For the operations in the first part of this algorithm, since DFS
>>>>> traverses each edge twice, the time complexity would be
>>>>> 2*((n-1)/15 - 1).
>>>>>
>>>>> For the second part, each operation involves copying a node and making
>>>>> necessary modifications. Therefore, the time complexity is
>>>>> 16*(n-1)/15.
>>>>>
>>>>> For the third part, we use mas_find() to traverse and replace each
>>>>> element, which is essentially similar to the combination of the first
>>>>> and second parts. mas_find() traverses all nodes and within each node,
>>>>> it iterates over all elements and performs replacements. The time
>>>>> complexity of traversing the nodes is 2*((n-1)/15 - 1), and for all
>>>>> nodes, the time complexity of replacing all their elements is
>>>>> 16*(n-1)/15.
>>>>>
>>>>> By ignoring all constant factors, each of the three parts of the
>>>>> algorithm has a time complexity of O(n). Therefore, this new algorithm
>>>>> is O(n).
>>>>
>>>> Thanks for the detailed analysis! I didn't mean to cause so much work
>>>> with this question. I wanted to know so that future work could rely on
>>>> this calculation to demonstrate if it is worth implementing without
>>>> going through the effort of coding and benchmarking - after all, this
>>>> commit message will most likely be examined during that process.
>>>>
>>>> I asked because O(n) vs O(n*log(n)) doesn't seem to fit with your
>>>> benchmarking.
>>> It may not be well reflected in the benchmarking of fork() because all
>>> the aforementioned time complexity analysis is related to the part
>>> involving the maple tree, specifically the time complexity of
>>> constructing a new maple tree. However, fork() also includes many other
>>> behaviors.
>>
>> The forking is allocating VMAs, etc but all a 1-1 mapping per VMA so it
>> should be linear, if not near-linear. There is some setup time involved
>> with the mm struct too, but that should become less as more VMAs are
>> added per fork.
>>
>>>>
>>>>>
>>>>> The exact time complexity of the old algorithm is difficult to analyze.
>>>>> I can only provide an upper bound estimation. There are two possible
>>>>> scenarios for each insertion:
>>>>>
>>>>> 1. Appending at the end of a node.
>>>>> 2. Splitting nodes multiple times.
>>>>>
>>>>> For the first scenario, the individual operation has a time complexity
>>>>> of O(1). As for the second scenario, it involves node splitting. The
>>>>> challenge lies in determining which insertions trigger splits and how
>>>>> many splits occur each time, which is difficult to calculate. In the
>>>>> worst-case scenario, each insertion requires splitting the tree's height
>>>>> log(n) times. Assuming every insertion is in the worst-case scenario,
>>>>> the time complexity would be n*log(n). However, not every insertion
>>>>> requires splitting, and the number of splits each time may not
>>>>> necessarily be log(n). Therefore, this is an estimation of the upper
>>>>> bound.
>>>>
>>>> Saying every insert causes a split and adding in n*log(n) is more than
>>>> an over estimation. At worst there is some n + n/16 * log(n) going on
>>>> there.
>>>>
>>>> During the building of a tree, we are in bulk insert mode. This favours
>>>> balancing the tree to the left to maximize the number of inserts being
>>>> append operations. The algorithm inserts as many to the left as we can
>>>> leaving the minimum number on the right.
>>>>
>>>> We also reduce the number of splits by pushing data to the left whenever
>>>> possible, at every level.
>>> Yes, but I don't think pushing data would occur when inserting in
>>> ascending order in bulk mode because the left nodes are all full, while
>>> there are no nodes on the right side. However, I'm not entirely certain
>>> about this since I only briefly looked at the implementation of this
>>> part.
>>
>> They are not full, the right node has enough entries to have a
>> sufficient node, so the left node will have that many spaces for push.
>> mab_calc_split():
>> if (unlikely((mas->mas_flags & MA_STATE_BULK))) {
>> *mid_split = 0;
>> split = b_end - mt_min_slots[bn->type];
Oh, thank you.
>>
>>>>
>>>>
>>>>>>
>>>>>>>
>>>>>>> As the entire maple tree is duplicated using __mt_dup(), if dup_mmap()
>>>>>>> fails, there will be a portion of VMAs that have not been duplicated in
>>>>>>> the maple tree. This makes it impossible to unmap all VMAs in exit_mmap().
>>>>>>> To solve this problem, undo_dup_mmap() is introduced to handle the failure
>>>>>>> of dup_mmap(). I have carefully tested the failure path and so far it
>>>>>>> seems there are no issues.
>>>>>>>
>>>>>>> There is a "spawn" in byte-unixbench[1], which can be used to test the
>>>>>>> performance of fork(). I modified it slightly to make it work with
>>>>>>> different number of VMAs.
>>>>>>>
>>>>>>> Below are the test results. By default, there are 21 VMAs. The first row
>>>>>>> shows the number of additional VMAs added on top of the default. The last
>>>>>>> two rows show the number of fork() calls per ten seconds. The test results
>>>>>>> were obtained with CPU binding to avoid scheduler load balancing that
>>>>>>> could cause unstable results. There are still some fluctuations in the
>>>>>>> test results, but at least they are better than the original performance.
>>>>>>>
>>>>>>> Increment of VMAs: 0 100 200 400 800 1600 3200 6400
>>>>>>> next-20230921: 112326 75469 54529 34619 20750 11355 6115 3183
>>>>>>> Apply this: 116505 85971 67121 46080 29722 16665 9050 4805
>>>>>>> +3.72% +13.92% +23.09% +33.11% +43.24% +46.76% +48.00% +50.96%
>>>> delta 4179 10502 12592 11461 8972 5310 2935 1622
>>>>
>>>> Looking at this data, it is difficult to see what is going on because
>>>> there is a doubling of the VMAs per fork per column while the count is
>>>> forks per 10 seconds. So this table is really a logarithmic table with
>>>> increases growing by 10%. Adding the delta row makes it seem like the
>>>> number are not growing apart as I would expect.
>>>>
>>>> If we normalize this to VMAs per second by dividing the forks by 10,
>>>> then multiplying by the number of VMAs we get this:
>>>>
>>>> VMA Count: 21 121 221 421 821 1621 3221 6421
>>>> log(VMA) 1.32 2.00 2.30 2.60 2.90 3.20 3.36 3.81
>>>> next-20230921: 258349.8 928268.7 1215996.7 1464383.7 1707725.0 1842916.5 1420514.5 2044440.9
>>>> this: 267961.5 1057443.3 1496798.3 1949184.0 2446120.6 2704729.5 2102315.0 3086251.5
>>>> delta 9611.7 129174.6 280801.6 484800.3 738395.6 861813.0 681800.5 1041810.6
>>>>
>>>> The first thing that I noticed was that we hit some dip in the numbers
>>>> at 3221. I first thought that might be something else running on the
>>>> host machine, but both runs are affected by around the same percent.
>>>>
>>>> Here, we do see the delta growing apart, but peaking in growth around
>>>> 821 VMAs. Again that 3221 number is out of line.
>>>>
>>>> If we discard 21 and anything above 1621, we still see both lines are
>>>> asymptotic curves. I would expect that the new algorithm would be more
>>>> linear to represent O(n), but there is certainly a curve when graphed
>>>> with a normalized X-axis. The older algorithm, O(n*log(n)) should be
>>>> the opposite curve all together, and with a diminishing return, but it
>>>> seems the more elements we have, the more operations we can perform in a
>>>> second.
>>> Thank you for your detailed analysis.
>>>
>>> So, are you expecting the transformed data to be close to a constant
>>> value?
>>
>> I would expect it to increase linearly, but it's a curve. Also, it
>> seems that both methods are near the identical curve, including the dip
>> at 3221. I expect the new method to have a different curve, especially
>> at the higher numbers where the fork() overhead is much less, but it
>> seems they both curve asymptotically. That is, they seen to be the same
>> complexity related to n, but with different constants.
I conducted a test on the quantity of VMAs at an extremely large scale.
old:
VMAs: 21 121 221 421 821 1621 3221 6421
forks/10s: 114156 76512 54409 34390 20138 11234 5999 3102
VMAs * forks/10s: 2397276 9257952 12024389 14478190 16533298 18210314 19322779 19917942
VMAs: 12821 25621 51221 102421 204821 409621 819221 1638421
forks/10s: 1600 806 393 172 88 41 21 11
VMAs * forks/10s: 20513600 20650526 20129853 17616412 18024248 16794461 17203641 18022631
new:
VMAs: 21 121 221 421 821 1621 3221 6421
forks/10s: 115523 86424 66484 45040 27462 15247 8435 4552
VMAs * forks/10s: 2425983 10457304 14692964 18961840 22546302 24715387 27169135 29228392
VMAs: 12821 25621 51221 102421 204821 409621 819221 1638421
forks/10s: 2446 1253 603 267 132 67 33 17
VMAs * forks/10s: 31360166 32103113 30886263 27346407 27036372 27444607 27034293 27853157
When the quantity of VMAs is sufficiently large, we can disregard the
other overheads of forking. VMAs * forks/10s can be considered as the
number of VMAs that can be duplicated in 10 seconds.
It can be observed that both the old algorithm and the new algorithm
reach a stable number of duplicated VMAs in 10 seconds when the quantity
of VMAs exceeds 6421. The approximate numbers are around 2e7 and 3e7,
respectively. However, after reaching 102,421, both algorithms show some
performance degradation that I cannot explain adequately. It is speculated
that the deterioration may be due to a decrease in memory allocation
performance. Nevertheless, even with the decline, they both converge to a
relatively stable value between 102,421 and 1,638,421.
The new algorithm can be proven to have an O(n) complexity, and the test
data roughly aligns with this theoretical analysis. It is challenging to
analyze the old algorithm theoretically, but based on the test data, it
is also likely to have an O(n) complexity. However, I cannot provide any
formal proof for this claim. So, in the next version, I will correct the
commit log, as nlog(n) may not be correct.
>>
>>> Please note that besides constructing a new maple tree, there are many
>>> other operations in fork(). As the number of VMAs increases, the number
>>> of fork() calls decreases. Therefore, the overall cost spent on other
>>> operations becomes smaller, while the cost spent on duplicating VMAs
>>> increases. That's why this data grows with the increase of VMAs. I
>>> speculate that if the number of VMAs is large enough to neglect the time
>>> spent on other operations in fork(), this data will approach a constant
>>> value.
>>
>> If it were the other parts of fork() causing the non-linear growth, then
>> I would expect 800 -> 1600 to increase to +53% instead of +46%, and if
>> we were hitting the limit of fork affecting the data, then I would
>> expect the delta of VMAs/second to not be so high at the upper 6421 -
>> both algorithms have more room to get more performance at least until
>> 6421 VMAs/fork.
>>
>>>
>>> If we want to achieve the expected curve, I think we should simulate the
>>> process of constructing the maple tree in user space to avoid the impact
>>> of other operations in fork(), just like in the current bench_forking().
>>>>
>>>> Thinking about what is going on here, I cannot come up with a reason
>>>> that there would be a curve to the line at all. If we took more
>>>> measurements, I would think the samples would be an ever-increasing line
>>>> with variability for some function of 16 - a saw toothed increasing
>>>> line. At least, until an upper limit is reached. We can see that the
>>>> upper limit was still not achieved at 1621 since 6421 is higher for both
>>>> runs, but a curve is evident on both methods, which suggests something
>>>> else is a significant contributor.
>>>>
>>>> I would think each VMA requires the same amount of work, so a constant.
>>>> The allocations would again, be some function that would linearly
>>>> increase with the existing method over-estimating by a huge number of
>>>> nodes.
>>>>
>>>> I'm not trying to nitpick here, but it is important to be accurate in
>>>> the statements because it may alter choices on how to proceed in
>>>> improving this performance later. It may be others looking through
>>>> these commit messages to see if something can be improved.
>>> Thank you for pointing that out. I will try to describe it more
>>> accurately in the commit log and see if I can measure the expected curve
>>> in user space.
>>>>
>>>> I also feel like your notes on your algorithm are worth including in the
>>>> commit because it could prove rather valuable if we revisit forking in
>>>> the future.
>>> Do you mean that I should write the analysis of the time complexity of
>>> the new algorithm in the commit log?
>>
>> Yes, I think it's worth capturing. What do you think?
Okay, I will update it in the commit log.
>>
>>>>
>>>> The more I look at this, the more questions I have that I cannot answer.
>>>> One thing we can see is that the new method is faster in this
>>>> micro-benchmark.
>>> Yes. It should be noted that in the field of computer science, if the
>>> test results don't align with the expected mathematical calculations,
>>> it indicates an error in the calculations. This is because accurate
>>> calculations will always be reflected in the test results. ????
>>>>
>>>>>>>
>>>>>>> [1] https://github.com/kdlucas/byte-unixbench/tree/master
>>>>>>>
>>>>>>> Signed-off-by: Peng Zhang <[email protected]>
>>>>>>> ---
>>>>>>> include/linux/mm.h | 1 +
>>>>>>> kernel/fork.c | 34 ++++++++++++++++++++----------
>>>>>>> mm/internal.h | 3 ++-
>>>>>>> mm/memory.c | 7 ++++---
>>>>>>> mm/mmap.c | 52 ++++++++++++++++++++++++++++++++++++++++++++--
>>>>>>> 5 files changed, 80 insertions(+), 17 deletions(-)
>>>>>>>
>>>>>>> diff --git a/include/linux/mm.h b/include/linux/mm.h
>>>>>>> index 1f1d0d6b8f20..10c59dc7ffaa 100644
>>>>>>> --- a/include/linux/mm.h
>>>>>>> +++ b/include/linux/mm.h
>>>>>>> @@ -3242,6 +3242,7 @@ extern void unlink_file_vma(struct vm_area_struct *);
>>>>>>> extern struct vm_area_struct *copy_vma(struct vm_area_struct **,
>>>>>>> unsigned long addr, unsigned long len, pgoff_t pgoff,
>>>>>>> bool *need_rmap_locks);
>>>>>>> +extern void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end);
>>>>>>> extern void exit_mmap(struct mm_struct *);
>>>>>>> static inline int check_data_rlimit(unsigned long rlim,
>>>>>>> diff --git a/kernel/fork.c b/kernel/fork.c
>>>>>>> index 7ae36c2e7290..2f3d83e89fe6 100644
>>>>>>> --- a/kernel/fork.c
>>>>>>> +++ b/kernel/fork.c
>>>>>>> @@ -650,7 +650,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> int retval;
>>>>>>> unsigned long charge = 0;
>>>>>>> LIST_HEAD(uf);
>>>>>>> - VMA_ITERATOR(old_vmi, oldmm, 0);
>>>>>>> VMA_ITERATOR(vmi, mm, 0);
>>>>>>> uprobe_start_dup_mmap();
>>>>>>> @@ -678,16 +677,25 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> goto out;
>>>>>>> khugepaged_fork(mm, oldmm);
>>>>>>> - retval = vma_iter_bulk_alloc(&vmi, oldmm->map_count);
>>>>>>> - if (retval)
>>>>>>> + /* Use __mt_dup() to efficiently build an identical maple tree. */
>>>>>>> + retval = __mt_dup(&oldmm->mm_mt, &mm->mm_mt, GFP_KERNEL);
>>>>>>> + if (unlikely(retval))
>>>>>>> goto out;
>>>>>>> mt_clear_in_rcu(vmi.mas.tree);
>>>>>>> - for_each_vma(old_vmi, mpnt) {
>>>>>>> + for_each_vma(vmi, mpnt) {
>>>>>>> struct file *file;
>>>>>>> vma_start_write(mpnt);
>>>>>>> if (mpnt->vm_flags & VM_DONTCOPY) {
>>>>>>> + mas_store_gfp(&vmi.mas, NULL, GFP_KERNEL);
>>>>>>> +
>>>>>>> + /* If failed, undo all completed duplications. */
>>>>>>> + if (unlikely(mas_is_err(&vmi.mas))) {
>>>>>>> + retval = xa_err(vmi.mas.node);
>>>>>>> + goto loop_out;
>>>>>>> + }
>>>>>>> +
>>>>>>> vm_stat_account(mm, mpnt->vm_flags, -vma_pages(mpnt));
>>>>>>> continue;
>>>>>>> }
>>>>>>> @@ -749,9 +757,11 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> if (is_vm_hugetlb_page(tmp))
>>>>>>> hugetlb_dup_vma_private(tmp);
>>>>>>> - /* Link the vma into the MT */
>>>>>>> - if (vma_iter_bulk_store(&vmi, tmp))
>>>>>>> - goto fail_nomem_vmi_store;
>>>>>>> + /*
>>>>>>> + * Link the vma into the MT. After using __mt_dup(), memory
>>>>>>> + * allocation is not necessary here, so it cannot fail.
>>>>>>> + */
>>>>>>> + mas_store(&vmi.mas, tmp);
>>>>>>> mm->map_count++;
>>>>>>> if (!(tmp->vm_flags & VM_WIPEONFORK))
>>>>>>> @@ -760,15 +770,19 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> if (tmp->vm_ops && tmp->vm_ops->open)
>>>>>>> tmp->vm_ops->open(tmp);
>>>>>>> - if (retval)
>>>>>>> + if (retval) {
>>>>>>> + mpnt = vma_next(&vmi);
>>>>>>> goto loop_out;
>>>>>>> + }
>>>>>>> }
>>>>>>> /* a new mm has just been created */
>>>>>>> retval = arch_dup_mmap(oldmm, mm);
>>>>>>> loop_out:
>>>>>>> vma_iter_free(&vmi);
>>>>>>> - if (!retval)
>>>>>>> + if (likely(!retval))
>>>>>>> mt_set_in_rcu(vmi.mas.tree);
>>>>>>> + else
>>>>>>> + undo_dup_mmap(mm, mpnt);
>>>>>>> out:
>>>>>>> mmap_write_unlock(mm);
>>>>>>> flush_tlb_mm(oldmm);
>>>>>>> @@ -778,8 +792,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
>>>>>>> uprobe_end_dup_mmap();
>>>>>>> return retval;
>>>>>>> -fail_nomem_vmi_store:
>>>>>>> - unlink_anon_vmas(tmp);
>>>>>>> fail_nomem_anon_vma_fork:
>>>>>>> mpol_put(vma_policy(tmp));
>>>>>>> fail_nomem_policy:
>>>>>>> diff --git a/mm/internal.h b/mm/internal.h
>>>>>>> index 7a961d12b088..288ec81770cb 100644
>>>>>>> --- a/mm/internal.h
>>>>>>> +++ b/mm/internal.h
>>>>>>> @@ -111,7 +111,8 @@ void folio_activate(struct folio *folio);
>>>>>>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> struct vm_area_struct *start_vma, unsigned long floor,
>>>>>>> - unsigned long ceiling, bool mm_wr_locked);
>>>>>>> + unsigned long ceiling, unsigned long tree_end,
>>>>>>> + bool mm_wr_locked);
>>>>>>> void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
>>>>>>> struct zap_details;
>>>>>>> diff --git a/mm/memory.c b/mm/memory.c
>>>>>>> index 983a40f8ee62..1fd66a0d5838 100644
>>>>>>> --- a/mm/memory.c
>>>>>>> +++ b/mm/memory.c
>>>>>>> @@ -362,7 +362,8 @@ void free_pgd_range(struct mmu_gather *tlb,
>>>>>>> void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> struct vm_area_struct *vma, unsigned long floor,
>>>>>>> - unsigned long ceiling, bool mm_wr_locked)
>>>>>>> + unsigned long ceiling, unsigned long tree_end,
>>>>>>> + bool mm_wr_locked)
>>>>>>> {
>>>>>>> do {
>>>>>>> unsigned long addr = vma->vm_start;
>>>>>>> @@ -372,7 +373,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> * Note: USER_PGTABLES_CEILING may be passed as ceiling and may
>>>>>>> * be 0. This will underflow and is okay.
>>>>>>> */
>>>>>>> - next = mas_find(mas, ceiling - 1);
>>>>>>> + next = mas_find(mas, tree_end - 1);
>>>>>>> /*
>>>>>>> * Hide vma from rmap and truncate_pagecache before freeing
>>>>>>> @@ -393,7 +394,7 @@ void free_pgtables(struct mmu_gather *tlb, struct ma_state *mas,
>>>>>>> while (next && next->vm_start <= vma->vm_end + PMD_SIZE
>>>>>>> && !is_vm_hugetlb_page(next)) {
>>>>>>> vma = next;
>>>>>>> - next = mas_find(mas, ceiling - 1);
>>>>>>> + next = mas_find(mas, tree_end - 1);
>>>>>>> if (mm_wr_locked)
>>>>>>> vma_start_write(vma);
>>>>>>> unlink_anon_vmas(vma);
>>>>>>> diff --git a/mm/mmap.c b/mm/mmap.c
>>>>>>> index 2ad950f773e4..daed3b423124 100644
>>>>>>> --- a/mm/mmap.c
>>>>>>> +++ b/mm/mmap.c
>>>>>>> @@ -2312,7 +2312,7 @@ static void unmap_region(struct mm_struct *mm, struct ma_state *mas,
>>>>>>> mas_set(mas, mt_start);
>>>>>>> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
>>>>>>> next ? next->vm_start : USER_PGTABLES_CEILING,
>>>>>>> - mm_wr_locked);
>>>>>>> + tree_end, mm_wr_locked);
>>>>>>> tlb_finish_mmu(&tlb);
>>>>>>> }
>>>>>>> @@ -3178,6 +3178,54 @@ int vm_brk(unsigned long addr, unsigned long len)
>>>>>>> }
>>>>>>> EXPORT_SYMBOL(vm_brk);
>>>>>>> +void undo_dup_mmap(struct mm_struct *mm, struct vm_area_struct *vma_end)
>>>>>>> +{
>>>>>>> + unsigned long tree_end;
>>>>>>> + VMA_ITERATOR(vmi, mm, 0);
>>>>>>> + struct vm_area_struct *vma;
>>>>>>> + unsigned long nr_accounted = 0;
>>>>>>> + int count = 0;
>>>>>>> +
>>>>>>> + /*
>>>>>>> + * vma_end points to the first VMA that has not been duplicated. We need
>>>>>>> + * to unmap all VMAs before it.
>>>>>>> + * If vma_end is NULL, it means that all VMAs in the maple tree have
>>>>>>> + * been duplicated, so setting tree_end to 0 will overflow to ULONG_MAX
>>>>>>> + * when using it.
>>>>>>> + */
>>>>>>> + if (vma_end) {
>>>>>>> + tree_end = vma_end->vm_start;
>>>>>>> + if (tree_end == 0)
>>>>>>> + goto destroy;
>>>>>>> + } else
>>>>>>> + tree_end = 0;
>>
>> You need to enclose this statement to meet the coding style. You could
>> just set tree_end = 0 at the start of the function instead, actually I
>> think tree_end = USER_PGTABLES_CEILING unless there is a vma_end.
>>
>>>>>>> +
>>>>>>> + vma = mas_find(&vmi.mas, tree_end - 1);
>>
>> vma = vma_find(&vmi, tree_end);
>>
>>>>>>> +
>>>>>>> + if (vma) {
>>
>> Probably would be cleaner to jump to destroy here too:
>> if (!vma)
>> goto destroy;
>>
>>>>>>> + arch_unmap(mm, vma->vm_start, tree_end);
>
> One more thing, it seems the maple state that is passed into
> unmap_region() needs to point to the _next_ element, or the reset
> doesn't work right between the unmap_vmas() and free_pgtables() call:
>
> vma_iter_set(&vmi, vma->vm_end);
Thank you, this is indeed an issue, it's surprising that it wasn't
detected during testing.
>
>
>>>>>>> + unmap_region(mm, &vmi.mas, vma, NULL, NULL, 0, tree_end,
>>>>>>> + tree_end, true);
>>>>>>
>>>>>> next is vma_end, as per your comment above. Using next = vma_end allows
>>>>>> you to avoid adding another argument to free_pgtables().
>>>>> Unfortunately, it cannot be done this way. I fell into this trap before,
>>>>> and it caused incomplete page table cleanup. To solve this problem, the
>>>>> only solution I can think of right now is to add an additional
>>>>> parameter.
>>>>>
>>>>> free_pgtables() will be called in unmap_region() to free the page table,
>>>>> like this:
>>>>>
>>>>> free_pgtables(&tlb, mas, vma, prev ? prev->vm_end : FIRST_USER_ADDRESS,
>>>>> next ? next->vm_start : USER_PGTABLES_CEILING,
>>>>> mm_wr_locked);
>>>>>
>>>>> The problem is with 'next'. Our 'vma_end' does not exist in the actual
>>>>> mmap because it has not been duplicated and cannot be used as 'next'.
>>>>> If there is a real 'next', we can use 'next->vm_start' as the ceiling,
>>>>> which is not a problem. If there is no 'next' (next is 'vma_end'), we
>>>>> can only use 'USER_PGTABLES_CEILING' as the ceiling. Using
>>>>> 'vma_end->vm_start' as the ceiling will cause the page table not to be
>>>>> fully freed, which may be related to alignment in 'free_pgd_range()'. To
>>>>> solve this problem, we have to introduce 'tree_end', and separating
>>>>> 'tree_end' and 'ceiling' can solve this problem.
>>>>
>>>> Can you just use ceiling? That is, just not pass in next and keep the
>>>> code as-is? This is how exit_mmap() does it and should avoid any
>>>> alignment issues. I assume you tried that and something went wrong as
>>>> well?
>>> I tried that, but it didn't work either. In free_pgtables(), the
>>> following line of code is used to iterate over VMAs:
>>> mas_find(mas, ceiling - 1);
>>> If next is passed as NULL, ceiling will be 0, resulting in iterating
>>> over all the VMAs in the maple tree, including the last portion that was
>>> not duplicated.
>>
>> If vma_end is NULL, it means that all VMAs in the maple tree have been
>> duplicated, so shouldn't the correct action in this case be freeing up
>> to ceiling?
>>
>> If it isn't null, then vma_end->vm_start should work as the end of the
>> area to free.
>>
>> With your mas_find(mas, tree_end - 1), then the vma_end will be avoided,
>> but free_pgd_range() will use ceiling anyways:
>>
>> free_pgd_range(tlb, addr, vma->vm_end, floor, next ? next->vm_start : ceiling);
>>
>> Passing in vma_end as next to unmap_region() functions in my testing
>> without adding arguments to free_pgtables().
>>
>> How are you producing the accounting issue you mention above? Maybe I
>> missed something?
>>
>>
>>>>
>>>>>
>>>>>>
>>>>>>> +
>>>>>>> + mas_set(&vmi.mas, vma->vm_end);
>> vma_iter_set(&vmi, vma->vm_end);
>>>>>>> + do {
>>>>>>> + if (vma->vm_flags & VM_ACCOUNT)
>>>>>>> + nr_accounted += vma_pages(vma);
>>>>>>> + remove_vma(vma, true);
>>>>>>> + count++;
>>>>>>> + cond_resched();
>>>>>>> + vma = mas_find(&vmi.mas, tree_end - 1);
>>>>>>> + } while (vma != NULL);
>>
>> You can write this as:
>> do { ... } for_each_vma_range(vmi, vma, tree_end);
>>
>>>>>>> +
>>>>>>> + BUG_ON(count != mm->map_count);
>>>>>>> +
>>>>>>> + vm_unacct_memory(nr_accounted);
>>>>>>> + }
>>>>>>> +
>>>>>>> +destroy:
>>>>>>> + __mt_destroy(&mm->mm_mt);
>>>>>>> +}
>>>>>>> +
>>>>>>> /* Release all mmaps. */
>>>>>>> void exit_mmap(struct mm_struct *mm)
>>>>>>> {
>>>>>>> @@ -3217,7 +3265,7 @@ void exit_mmap(struct mm_struct *mm)
>>>>>>> mt_clear_in_rcu(&mm->mm_mt);
>>>>>>> mas_set(&mas, vma->vm_end);
>>>>>>> free_pgtables(&tlb, &mas, vma, FIRST_USER_ADDRESS,
>>>>>>> - USER_PGTABLES_CEILING, true);
>>>>>>> + USER_PGTABLES_CEILING, USER_PGTABLES_CEILING, true);
>>>>>>> tlb_finish_mmu(&tlb);
>>>>>>> /*
>>>>>>> --
>>>>>>> 2.20.1
>>>>>>>
>>>>>>
>>>>>
>>>>
>