Skip to contentSkip to conversation

Reduce preallocations for maple tree

PATCH Superseded Liam R. Howlett 5 participants 34 messages Jun 1, 2023 – Jun 6, 2023

Subsystems (8)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

cover Reduce preallocations for maple tree

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down. This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating. This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree
0005: Small cleanup of do_vmi_align_munmap()
0006-0013: mas_preallocate() calculation change
0014: Change the vma iterator order

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
maple_tree: Add benchmarking for mas_for_each
maple_tree: Add benchmarking for mas_prev()
mm: Move unmap_vmas() declaration to internal header
mm: Change do_vmi_align_munmap() side tree index
mm: Remove prev check from do_vmi_align_munmap()
maple_tree: Introduce __mas_set_range()
mm: Remove re-walk from mmap_region()
maple_tree: Re-introduce entry to mas_preallocate() arguments
mm: Use vma_iter_clear_gfp() in nommu
mm: Set up vma iterator for vma_iter_prealloc() calls
maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
maple_tree: Update mas_preallocate() testing
maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

 fs/exec.c                        |   1 +
 include/linux/maple_tree.h       |  23 ++++-
 include/linux/mm.h               |   4 -
 lib/maple_tree.c                 |  78 ++++++++++----
 lib/test_maple_tree.c            |  74 +++++++++++++
 mm/internal.h                    |  40 ++++++--
 mm/memory.c                      |  16 ++-
 mm/mmap.c                        | 171 ++++++++++++++++---------------
 mm/nommu.c                       |  45 ++++----
 tools/testing/radix-tree/maple.c |  59 ++++++-----
 10 files changed, 331 insertions(+), 180 deletions(-)
Signature · 1 line
2.39.2
#1 lore raw

PATCH 1/14 maple_tree: Add benchmarking for mas_for_each

Add a way to test the speed of mas_for_each() to the testing code.

---
 lib/test_maple_tree.c | 38 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 38 insertions(+)
lib/test_maple_tree.c +38 -0
index 9939be34e516..3dbf99c3f2b1 100644
@@ -44,6 +44,7 @@ atomic_t maple_tree_tests_passed;
 /* #define BENCH_WALK */
 /* #define BENCH_MT_FOR_EACH */
 /* #define BENCH_FORK */
+/* #define BENCH_MAS_FOR_EACH */
 
 #ifdef __KERNEL__
 #define mt_set_non_kernel(x)		do {} while (0)
@@ -1705,6 +1706,36 @@ static noinline void __init bench_mt_for_each(struct maple_tree *mt)
 }
 #endif
 
+#if defined(BENCH_MAS_FOR_EACH)
+static noinline void __init bench_mas_for_each(struct maple_tree *mt)
+{
+	int i, count = 1000000;
+	unsigned long max = 2500;
+	void *entry;
+	MA_STATE(mas, mt, 0, 0);
+
+	for (i = 0; i < max; i += 5) {
+		int gap = 4;
+		if (i % 30 == 0)
+			gap = 3;
+		mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
+	}
+
+	rcu_read_lock();
+	for (i = 0; i < count; i++) {
+		unsigned long j = 0;
+
+		mas_for_each(&mas, entry, max) {
+			MT_BUG_ON(mt, entry != xa_mk_value(j));
+			j += 5;
+		}
+		mas_set(&mas, 0);
+	}
+	rcu_read_unlock();
+
+}
+#endif
+
 /* check_forking - simulate the kernel forking sequence with the tree. */
 static noinline void __init check_forking(struct maple_tree *mt)
 {
@@ -3430,6 +3461,13 @@ static int __init maple_tree_seed(void)
 	mtree_destroy(&tree);
 	goto skip;
 #endif
+#if defined(BENCH_MAS_FOR_EACH)
+#define BENCH
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	bench_mas_for_each(&tree);
+	mtree_destroy(&tree);
+	goto skip;
+#endif
 
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
 	check_iteration(&tree);
Signature · 1 line
2.39.2
#2 lore raw

PATCH 2/14 maple_tree: Add benchmarking for mas_prev()

In reply to Liam R. Howlett
---
 lib/test_maple_tree.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
lib/test_maple_tree.c +36 -0
index 3dbf99c3f2b1..15d7b7bce7d6 100644
@@ -45,6 +45,7 @@ atomic_t maple_tree_tests_passed;
 /* #define BENCH_MT_FOR_EACH */
 /* #define BENCH_FORK */
 /* #define BENCH_MAS_FOR_EACH */
+/* #define BENCH_MAS_PREV */
 
 #ifdef __KERNEL__
 #define mt_set_non_kernel(x)		do {} while (0)
@@ -1735,7 +1736,35 @@ static noinline void __init bench_mas_for_each(struct maple_tree *mt)
 
 }
 #endif
+#if defined(BENCH_MAS_PREV)
+static noinline void __init bench_mas_prev(struct maple_tree *mt)
+{
+	int i, count = 1000000;
+	unsigned long max = 2500;
+	void *entry;
+	MA_STATE(mas, mt, 0, 0);
+
+	for (i = 0; i < max; i += 5) {
+		int gap = 4;
+		if (i % 30 == 0)
+			gap = 3;
+		mtree_store_range(mt, i, i + gap, xa_mk_value(i), GFP_KERNEL);
+	}
 
+	rcu_read_lock();
+	for (i = 0; i < count; i++) {
+		unsigned long j = 2495;
+
+		mas_set(&mas, ULONG_MAX);
+		while ((entry = mas_prev(&mas, 0)) != NULL) {
+			MT_BUG_ON(mt, entry != xa_mk_value(j));
+			j -= 5;
+		}
+	}
+	rcu_read_unlock();
+
+}
+#endif
 /* check_forking - simulate the kernel forking sequence with the tree. */
 static noinline void __init check_forking(struct maple_tree *mt)
 {
@@ -3468,6 +3497,13 @@ static int __init maple_tree_seed(void)
 	mtree_destroy(&tree);
 	goto skip;
 #endif
+#if defined(BENCH_MAS_PREV)
+#define BENCH
+	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
+	bench_mas_prev(&tree);
+	mtree_destroy(&tree);
+	goto skip;
+#endif
 
 	mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE);
 	check_iteration(&tree);
Signature · 1 line
2.39.2
#3 lore raw

PATCH 3/14 mm: Move unmap_vmas() declaration to internal header

In reply to Liam R. Howlett

unmap_vmas() is not used outside of the core mm code. Move the definition to mm/internal.h

---
 include/linux/mm.h | 4 ----
 mm/internal.h      | 4 ++++
 2 files changed, 4 insertions(+), 4 deletions(-)
include/linux/mm.h +0 -4
index 66032f0d515c..209fe13dc8a2 100644
@@ -2302,10 +2302,6 @@ static inline void zap_vma_pages(struct vm_area_struct *vma)
 	zap_page_range_single(vma, vma->vm_start,
 			      vma->vm_end - vma->vm_start, NULL);
 }
-void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
-		struct vm_area_struct *start_vma, unsigned long start,
-		unsigned long end, bool mm_wr_locked);
-
 struct mmu_notifier_range;
 
 void free_pgd_range(struct mmu_gather *tlb, unsigned long addr,
mm/internal.h +4 -0
index f45f5eb4514f..9b665c4e5fc0 100644
@@ -1099,6 +1099,10 @@ static inline int vma_iter_store_gfp(struct vma_iterator *vmi,
 	return 0;
 }
 
+void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
+		struct vm_area_struct *vma, unsigned long start_addr,
+		unsigned long end_addr, bool mm_wr_locked);
+
 /*
  * VMA lock generalization
  */
Signature · 1 line
2.39.2
#4 lore raw

PATCH 4/14 mm: Change do_vmi_align_munmap() side tree index

In reply to Liam R. Howlett

The majority of the calls to munmap a VMA is for a single vma. The maple tree is able to store a single entry at 0, with a size of 1 as a pointer and avoid any allocations. Change do_vmi_align_munmap() to store the VMAs being munmap()'ed into a tree indexed by the count. This will leverage the ability to store the first entry without a node allocation.

Storing the entries into a tree by the count and not the vma start and end means changing the functions which iterate over the entries. Update unmap_vmas() and free_pgtables() to take a maple state and a tree end address to support this functionality.

Passing through the same maple state to unmap_vmas() and free_pgtables() means the state needs to be reset between calls. This happens in the static unmap_region() and exit_mmap().

---
 mm/internal.h |  8 ++++----
 mm/memory.c   | 16 +++++++---------
 mm/mmap.c     | 41 ++++++++++++++++++++++++-----------------
 3 files changed, 35 insertions(+), 30 deletions(-)
mm/internal.h +4 -4
index 9b665c4e5fc0..24437f11d3c2 100644
@@ -103,7 +103,7 @@ bool __folio_end_writeback(struct folio *folio);
 void deactivate_file_folio(struct folio *folio);
 void folio_activate(struct folio *folio);
 
-void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
+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);
 void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
@@ -1099,9 +1099,9 @@ static inline int vma_iter_store_gfp(struct vma_iterator *vmi,
 	return 0;
 }
 
-void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
-		struct vm_area_struct *vma, unsigned long start_addr,
-		unsigned long end_addr, bool mm_wr_locked);
+void unmap_vmas(struct mmu_gather *tlb, struct ma_state *mas,
+		struct vm_area_struct *start_vma, unsigned long start,
+		unsigned long end, unsigned long tree_end, bool mm_wr_locked);
 
 /*
  * VMA lock generalization
mm/memory.c +7 -9
index 8358f3b853f2..6737263e17e3 100644
@@ -360,12 +360,10 @@ void free_pgd_range(struct mmu_gather *tlb,
 	} while (pgd++, addr = next, addr != end);
 }
 
-void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
+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)
 {
-	MA_STATE(mas, mt, vma->vm_end, vma->vm_end);
-
 	do {
 		unsigned long addr = vma->vm_start;
 		struct vm_area_struct *next;
@@ -374,7 +372,7 @@ void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
 		 * 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, ceiling - 1);
 
 		/*
 		 * Hide vma from rmap and truncate_pagecache before freeing
@@ -395,7 +393,7 @@ void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
 			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, ceiling - 1);
 				if (mm_wr_locked)
 					vma_start_write(vma);
 				unlink_anon_vmas(vma);
@@ -1700,9 +1698,10 @@ static void unmap_single_vma(struct mmu_gather *tlb,
  * ensure that any thus-far unmapped pages are flushed before unmap_vmas()
  * drops the lock and schedules.
  */
-void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
+void unmap_vmas(struct mmu_gather *tlb, struct ma_state *mas,
 		struct vm_area_struct *vma, unsigned long start_addr,
-		unsigned long end_addr, bool mm_wr_locked)
+		unsigned long end_addr, unsigned long tree_end,
+		bool mm_wr_locked)
 {
 	struct mmu_notifier_range range;
 	struct zap_details details = {
@@ -1710,7 +1709,6 @@ void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
 		/* Careful - we need to zap private pages too! */
 		.even_cows = true,
 	};
-	MA_STATE(mas, mt, vma->vm_end, vma->vm_end);
 
 	mmu_notifier_range_init(&range, MMU_NOTIFY_UNMAP, 0, vma->vm_mm,
 				start_addr, end_addr);
@@ -1718,7 +1716,7 @@ void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
 	do {
 		unmap_single_vma(tlb, vma, start_addr, end_addr, &details,
 				 mm_wr_locked);
-	} while ((vma = mas_find(&mas, end_addr - 1)) != NULL);
+	} while ((vma = mas_find(mas, tree_end - 1)) != NULL);
 	mmu_notifier_invalidate_range_end(&range);
 }
 
mm/mmap.c +24 -17

120 lines not on this page · raw message

Signature · 1 line
2.39.2
#5 lore raw

PATCH 5/14 mm: Remove prev check from do_vmi_align_munmap()

In reply to Liam R. Howlett

If the prev does not exist, the vma iterator will be set to MAS_NONE, which will be treated as a MAS_START when the mas_next or mas_find is used. In this case, the next caller will be the vma iterator, which uses mas_find() under the hood and will now do what the user expects.

---
 mm/mmap.c | 2 --
 1 file changed, 2 deletions(-)
mm/mmap.c +0 -2
index 8e5563668b18..fd3f505b40cc 100644
@@ -2402,8 +2402,6 @@ do_vmi_align_munmap(struct vma_iterator *vmi, struct vm_area_struct *vma,
 	}
 
 	prev = vma_prev(vmi);
-	if (unlikely((!prev)))
-		vma_iter_set(vmi, start);
 
 	/*
 	 * Detach a range of VMAs from the mm. Using next as a temp variable as
Signature · 1 line
2.39.2
#6 lore raw

PATCH 6/14 maple_tree: Introduce __mas_set_range()

In reply to Liam R. Howlett

mas_set_range() resets the node to MAS_START, which will cause a re-walk of the tree to the range. This is unnecessary when the maple state is already at the correct location of the write. Add a function that only sets the range to avoid unnecessary re-walking of the tree.

---
 include/linux/maple_tree.h | 21 ++++++++++++++++++---
 1 file changed, 18 insertions(+), 3 deletions(-)
include/linux/maple_tree.h +18 -3
index 295548cca8b3..ed50d8f459e6 100644
@@ -531,6 +531,22 @@ static inline void mas_reset(struct ma_state *mas)
  */
 #define mas_for_each(__mas, __entry, __max) \
 	while (((__entry) = mas_find((__mas), (__max))) != NULL)
+/**
+ * __mas_set_range() - Set up Maple Tree operation state to a sub-range of the
+ * current location.
+ * @mas: Maple Tree operation state.
+ * @start: New start of range in the Maple Tree.
+ * @last: New end of range in the Maple Tree.
+ *
+ * set the internal maple state values to a sub-range.
+ * Please use mas_set_range() if you do not know where you are in the tree.
+ */
+static inline void __mas_set_range(struct ma_state *mas, unsigned long start,
+		unsigned long last)
+{
+       mas->index = start;
+       mas->last = last;
+}
 
 /**
  * mas_set_range() - Set up Maple Tree operation state for a different index.
@@ -545,9 +561,8 @@ static inline void mas_reset(struct ma_state *mas)
 static inline
 void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last)
 {
-	       mas->index = start;
-	       mas->last = last;
-	       mas->node = MAS_START;
+	__mas_set_range(mas, start, last);
+	mas->node = MAS_START;
 }
 
 /**
Signature · 1 line
2.39.2
#7 lore raw

PATCH 7/14 mm: Remove re-walk from mmap_region()

In reply to Liam R. Howlett

Using vma_iter_set() will reset the tree and cause a re-walk. Use vmi_iter_config() to set the write to a sub-set of the range. Change the file case to also use vmi_iter_config() so that the end is correctly set.

---
 mm/internal.h | 8 ++++++++
 mm/mmap.c     | 4 ++--
 2 files changed, 10 insertions(+), 2 deletions(-)
mm/internal.h +8 -0
index 24437f11d3c2..cdf06f680d6e 100644
@@ -1034,6 +1034,14 @@ static inline bool vma_soft_dirty_enabled(struct vm_area_struct *vma)
 	return !(vma->vm_flags & VM_SOFTDIRTY);
 }
 
+static inline void vma_iter_config(struct vma_iterator *vmi,
+		unsigned long index, unsigned long last)
+{
+	MAS_BUG_ON(&vmi->mas, vmi->mas.node != MAS_START &&
+		   (vmi->mas.index > index || vmi->mas.last < index));
+	__mas_set_range(&vmi->mas, index, last - 1);
+}
+
 /*
  * VMA Iterator functions shared between nommu and mmap
  */
mm/mmap.c +2 -2
index fd3f505b40cc..8b3e58d6ac40 100644
@@ -2659,7 +2659,7 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		goto unacct_error;
 	}
 
-	vma_iter_set(&vmi, addr);
+	vma_iter_config(&vmi, addr, end);
 	vma->vm_start = addr;
 	vma->vm_end = end;
 	vm_flags_init(vma, vm_flags);
@@ -2686,7 +2686,7 @@ unsigned long mmap_region(struct file *file, unsigned long addr,
 		if (WARN_ON((addr != vma->vm_start)))
 			goto close_and_free_vma;
 
-		vma_iter_set(&vmi, addr);
+		vma_iter_config(&vmi, addr, end);
 		/*
 		 * If vm_flags changed after call_mmap(), we should try merge
 		 * vma again as we may succeed this time.
Signature · 1 line
2.39.2
#8 lore raw

PATCH 8/14 maple_tree: Re-introduce entry to mas_preallocate() arguments

In reply to Liam R. Howlett

The current preallocation strategy is to preallocate the absolute worst-case allocation for a tree modification. The entry (or NULL) is needed to know how many nodes are needed to write to the tree. Start by adding the argument to the mas_preallocate() definition.

---
 include/linux/maple_tree.h       |  2 +-
 lib/maple_tree.c                 |  3 ++-
 mm/internal.h                    |  2 +-
 mm/mmap.c                        |  4 ++--
 tools/testing/radix-tree/maple.c | 32 ++++++++++++++++----------------
 5 files changed, 22 insertions(+), 21 deletions(-)
include/linux/maple_tree.h +1 -1
index ed50d8f459e6..e18ecbefc7f7 100644
@@ -458,7 +458,7 @@ void *mas_find(struct ma_state *mas, unsigned long max);
 void *mas_find_range(struct ma_state *mas, unsigned long max);
 void *mas_find_rev(struct ma_state *mas, unsigned long min);
 void *mas_find_range_rev(struct ma_state *mas, unsigned long max);
-int mas_preallocate(struct ma_state *mas, gfp_t gfp);
+int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp);
 bool mas_is_err(struct ma_state *mas);
 
 bool mas_nomem(struct ma_state *mas, gfp_t gfp);
lib/maple_tree.c +2 -1
index bfffbb7cab26..34eccddb0b47 100644
@@ -5535,11 +5535,12 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
 /**
  * mas_preallocate() - Preallocate enough nodes for a store operation
  * @mas: The maple state
+ * @entry: The entry that will be stored
  * @gfp: The GFP_FLAGS to use for allocations.
  *
  * Return: 0 on success, -ENOMEM if memory could not be allocated.
  */
-int mas_preallocate(struct ma_state *mas, gfp_t gfp)
+int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 {
 	int ret;
 
mm/internal.h +1 -1
index cdf06f680d6e..2691deca9699 100644
@@ -1047,7 +1047,7 @@ static inline void vma_iter_config(struct vma_iterator *vmi,
  */
 static inline int vma_iter_prealloc(struct vma_iterator *vmi)
 {
-	return mas_preallocate(&vmi->mas, GFP_KERNEL);
+	return mas_preallocate(&vmi->mas, NULL, GFP_KERNEL);
 }
 
 static inline void vma_iter_clear(struct vma_iterator *vmi,
mm/mmap.c +2 -2
index 8b3e58d6ac40..75b2a86e1faa 100644
@@ -1982,7 +1982,7 @@ int expand_upwards(struct vm_area_struct *vma, unsigned long address)
 		/* Check that both stack segments have the same anon_vma? */
 	}
 
-	if (mas_preallocate(&mas, GFP_KERNEL))
+	if (mas_preallocate(&mas, vma, GFP_KERNEL))
 		return -ENOMEM;
 
 	/* We must make sure the anon_vma is allocated. */
@@ -2064,7 +2064,7 @@ int expand_downwards(struct vm_area_struct *vma, unsigned long address)
 			return -ENOMEM;
 	}
 
-	if (mas_preallocate(&mas, GFP_KERNEL))
+	if (mas_preallocate(&mas, vma, GFP_KERNEL))
 		return -ENOMEM;
 
 	/* We must make sure the anon_vma is allocated. */
tools/testing/radix-tree/maple.c +16 -16
index 03539d86cdf0..cfadc4b75d51 100644
@@ -35383,7 +35383,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	for (i = 0; i <= max; i++)
 		mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
@@ -35392,18 +35392,18 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	allocated = mas_allocated(&mas);
 	MT_BUG_ON(mt, allocated != 0);
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	mas_destroy(&mas);
 	allocated = mas_allocated(&mas);
 	MT_BUG_ON(mt, allocated != 0);
 
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
@@ -35412,26 +35412,26 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
 	mn->parent = ma_parent_ptr(mn);
 	ma_free_rcu(mn);
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	mas_destroy(&mas);
 	allocated = mas_allocated(&mas);
 	MT_BUG_ON(mt, allocated != 0);
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mn = mas_pop_node(&mas);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	mas_destroy(&mas);
 	allocated = mas_allocated(&mas);
 	MT_BUG_ON(mt, allocated != 0);
 	mn->parent = ma_parent_ptr(mn);
 	ma_free_rcu(mn);
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
@@ -35440,12 +35440,12 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
 	mas_push_node(&mas, mn);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated);
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	mas_destroy(&mas);
 	allocated = mas_allocated(&mas);
 	MT_BUG_ON(mt, allocated != 0);
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
@@ -35453,21 +35453,21 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mas_store_prealloc(&mas, ptr);
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
@@ -35475,14 +35475,14 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 	mt_set_non_kernel(1);
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL & GFP_NOWAIT) == 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated != 0);
 	mas_destroy(&mas);
 
 
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL) != 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated == 0);
@@ -35490,7 +35490,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 	mt_set_non_kernel(1);
-	MT_BUG_ON(mt, mas_preallocate(&mas, GFP_KERNEL & GFP_NOWAIT) == 0);
+	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
 	MT_BUG_ON(mt, allocated != 0);
Signature · 1 line
2.39.2
#9 lore raw

PATCH 9/14 mm: Use vma_iter_clear_gfp() in nommu

In reply to Liam R. Howlett

Move the definition of vma_iter_clear_gfp() from mmap.c to internal.h so it can be used in the nommu code. This will reduce node preallocations in nommu.

---
 mm/internal.h | 12 ++++++++++++
 mm/mmap.c     | 12 ------------
 mm/nommu.c    | 12 ++++--------
 3 files changed, 16 insertions(+), 20 deletions(-)
mm/internal.h +12 -0
index 2691deca9699..d78fd0fafa3b 100644
@@ -1057,6 +1057,18 @@ static inline void vma_iter_clear(struct vma_iterator *vmi,
 	mas_store_prealloc(&vmi->mas, NULL);
 }
 
+static inline int vma_iter_clear_gfp(struct vma_iterator *vmi,
+			unsigned long start, unsigned long end, gfp_t gfp)
+{
+	vmi->mas.index = start;
+	vmi->mas.last = end - 1;
+	mas_store_gfp(&vmi->mas, NULL, gfp);
+	if (unlikely(mas_is_err(&vmi->mas)))
+		return -ENOMEM;
+
+	return 0;
+}
+
 static inline struct vm_area_struct *vma_iter_load(struct vma_iterator *vmi)
 {
 	return mas_walk(&vmi->mas);
mm/mmap.c +0 -12
index 75b2a86e1faa..22c71dff762b 100644
@@ -154,18 +154,6 @@ static inline struct vm_area_struct *vma_prev_limit(struct vma_iterator *vmi,
 	return mas_prev(&vmi->mas, min);
 }
 
-static inline int vma_iter_clear_gfp(struct vma_iterator *vmi,
-			unsigned long start, unsigned long end, gfp_t gfp)
-{
-	vmi->mas.index = start;
-	vmi->mas.last = end - 1;
-	mas_store_gfp(&vmi->mas, NULL, gfp);
-	if (unlikely(mas_is_err(&vmi->mas)))
-		return -ENOMEM;
-
-	return 0;
-}
-
 /*
  * check_brk_limits() - Use platform specific check of range & verify mlock
  * limits.
mm/nommu.c +4 -8
index f670d9979a26..a764b86b132a 100644
@@ -1383,17 +1383,13 @@ static int vmi_shrink_vma(struct vma_iterator *vmi,
 
 	/* adjust the VMA's pointers, which may reposition it in the MM's tree
 	 * and list */
-	if (vma_iter_prealloc(vmi)) {
-		pr_warn("Allocation of vma tree for process %d failed\n",
-		       current->pid);
-		return -ENOMEM;
-	}
-
 	if (from > vma->vm_start) {
-		vma_iter_clear(vmi, from, vma->vm_end);
+		if (vma_iter_clear_gfp(vmi, from, vma->vm_end, GFP_KERNEL))
+			return -ENOMEM;
 		vma->vm_end = from;
 	} else {
-		vma_iter_clear(vmi, vma->vm_start, to);
+		if (vma_iter_clear_gfp(vmi, vma->vm_start, to, GFP_KERNEL))
+			return -ENOMEM;
 		vma->vm_start = to;
 	}
 
Signature · 1 line
2.39.2
#10 lore raw

PATCH 10/14 mm: Set up vma iterator for vma_iter_prealloc() calls

In reply to Liam R. Howlett

Set the correct limits for vma_iter_prealloc() calls so that the maple tree can be smarter about how many nodes are needed.

---
 fs/exec.c     |  1 +
 mm/internal.h | 18 +++++-------
 mm/mmap.c     | 81 +++++++++++++++++++++++++++++++--------------------
 mm/nommu.c    | 33 +++++++++------------
 4 files changed, 72 insertions(+), 61 deletions(-)
fs/exec.c +1 -0
index 25c65b64544b..dc0ba74ebb74 100644
@@ -697,6 +697,7 @@ static int shift_arg_pages(struct vm_area_struct *vma, unsigned long shift)
 	if (vma != vma_next(&vmi))
 		return -EFAULT;
 
+	vma_iter_prev_range(&vmi);
 	/*
 	 * cover the whole range: [new_start, old_end)
 	 */
mm/internal.h +7 -11
index d78fd0fafa3b..531b2e95146c 100644
@@ -1045,23 +1045,21 @@ static inline void vma_iter_config(struct vma_iterator *vmi,
 /*
  * VMA Iterator functions shared between nommu and mmap
  */
-static inline int vma_iter_prealloc(struct vma_iterator *vmi)
+static inline int vma_iter_prealloc(struct vma_iterator *vmi,
+		struct vm_area_struct *vma)
 {
-	return mas_preallocate(&vmi->mas, NULL, GFP_KERNEL);
+	return mas_preallocate(&vmi->mas, vma, GFP_KERNEL);
 }
 
-static inline void vma_iter_clear(struct vma_iterator *vmi,
-				  unsigned long start, unsigned long end)
+static inline void vma_iter_clear(struct vma_iterator *vmi)
 {
-	mas_set_range(&vmi->mas, start, end - 1);
 	mas_store_prealloc(&vmi->mas, NULL);
 }
 
 static inline int vma_iter_clear_gfp(struct vma_iterator *vmi,
 			unsigned long start, unsigned long end, gfp_t gfp)
 {
-	vmi->mas.index = start;
-	vmi->mas.last = end - 1;
+	__mas_set_range(&vmi->mas, start, end - 1);
 	mas_store_gfp(&vmi->mas, NULL, gfp);
 	if (unlikely(mas_is_err(&vmi->mas)))
 		return -ENOMEM;
@@ -1098,8 +1096,7 @@ static inline void vma_iter_store(struct vma_iterator *vmi,
 	    ((vmi->mas.index > vma->vm_start) || (vmi->mas.last < vma->vm_start)))
 		vma_iter_invalidate(vmi);
 
-	vmi->mas.index = vma->vm_start;
-	vmi->mas.last = vma->vm_end - 1;
+	__mas_set_range(&vmi->mas, vma->vm_start, vma->vm_end - 1);
 	mas_store_prealloc(&vmi->mas, vma);
 }
 
@@ -1110,8 +1107,7 @@ static inline int vma_iter_store_gfp(struct vma_iterator *vmi,
 	    ((vmi->mas.index > vma->vm_start) || (vmi->mas.last < vma->vm_start)))
 		vma_iter_invalidate(vmi);
 
-	vmi->mas.index = vma->vm_start;
-	vmi->mas.last = vma->vm_end - 1;
+	__mas_set_range(&vmi->mas, vma->vm_start, vma->vm_end - 1);
 	mas_store_gfp(&vmi->mas, vma, gfp);
 	if (unlikely(mas_is_err(&vmi->mas)))
 		return -ENOMEM;
mm/mmap.c +50 -31

211 lines not on this page · raw message

mm/nommu.c +14 -19
index a764b86b132a..a96b889cc17e 100644
@@ -583,7 +583,8 @@ static int delete_vma_from_mm(struct vm_area_struct *vma)
 {
 	VMA_ITERATOR(vmi, vma->vm_mm, vma->vm_start);
 
-	if (vma_iter_prealloc(&vmi)) {
+	vma_iter_config(&vmi, vma->vm_start, vma->vm_end);
+	if (vma_iter_prealloc(&vmi, vma)) {
 		pr_warn("Allocation of vma tree for process %d failed\n",
 		       current->pid);
 		return -ENOMEM;
@@ -591,7 +592,7 @@ static int delete_vma_from_mm(struct vm_area_struct *vma)
 	cleanup_vma_from_mm(vma);
 
 	/* remove from the MM's tree and list */
-	vma_iter_clear(&vmi, vma->vm_start, vma->vm_end);
+	vma_iter_clear(&vmi);
 	return 0;
 }
 /*
@@ -1041,9 +1042,6 @@ unsigned long do_mmap(struct file *file,
 	if (!vma)
 		goto error_getting_vma;
 
-	if (vma_iter_prealloc(&vmi))
-		goto error_vma_iter_prealloc;
-
 	region->vm_usage = 1;
 	region->vm_flags = vm_flags;
 	region->vm_pgoff = pgoff;
@@ -1185,6 +1183,10 @@ unsigned long do_mmap(struct file *file,
 
 share:
 	BUG_ON(!vma->vm_region);
+	vma_iter_config(&vmi, vma->vm_start, vma->vm_end);
+	if (vma_iter_prealloc(&vmi, vma))
+		goto error_just_free;
+
 	setup_vma_to_mm(vma, current->mm);
 	current->mm->map_count++;
 	/* add the VMA to the tree */
@@ -1231,14 +1233,6 @@ unsigned long do_mmap(struct file *file,
 			len, current->pid);
 	show_free_areas(0, NULL);
 	return -ENOMEM;
-
-error_vma_iter_prealloc:
-	kmem_cache_free(vm_region_jar, region);
-	vm_area_free(vma);
-	pr_warn("Allocation of vma tree for process %d failed\n", current->pid);
-	show_free_areas(0, NULL);
-	return -ENOMEM;
-
 }
 
 unsigned long ksys_mmap_pgoff(unsigned long addr, unsigned long len,
@@ -1323,12 +1317,6 @@ int split_vma(struct vma_iterator *vmi, struct vm_area_struct *vma,
 	if (!new)
 		goto err_vma_dup;
 
-	if (vma_iter_prealloc(vmi)) {
-		pr_warn("Allocation of vma tree for process %d failed\n",
-			current->pid);
-		goto err_vmi_preallocate;
-	}
-
 	/* most fields are the same, copy all, and then fixup */
 	*region = *vma->vm_region;
 	new->vm_region = region;
@@ -1342,6 +1330,13 @@ int split_vma(struct vma_iterator *vmi, struct vm_area_struct *vma,
 		region->vm_pgoff = new->vm_pgoff += npages;
 	}
 
+	vma_iter_config(vmi, new->vm_start, new->vm_end);
+	if (vma_iter_prealloc(vmi, vma)) {
+		pr_warn("Allocation of vma tree for process %d failed\n",
+			current->pid);
+		goto err_vmi_preallocate;
+	}
+
 	if (new->vm_ops && new->vm_ops->open)
 		new->vm_ops->open(new);
 
Signature · 1 line
2.39.2
#11 lore raw

PATCH 11/14 maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()

In reply to Liam R. Howlett

Relocate it and call mas_wr_extend_null() from within mas_wr_end_piv(). Extending the NULL may affect the end pivot value so call mas_wr_endtend_null() from within mas_wr_end_piv() to keep it all together.

---
 lib/maple_tree.c | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)
lib/maple_tree.c +15 -16
index 34eccddb0b47..adf662bc413e 100644
@@ -4197,18 +4197,6 @@ static inline bool mas_wr_slot_store(struct ma_wr_state *wr_mas)
 	return true;
 }
 
-static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas)
-{
-	while ((wr_mas->offset_end < wr_mas->node_end) &&
-	       (wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end]))
-		wr_mas->offset_end++;
-
-	if (wr_mas->offset_end < wr_mas->node_end)
-		wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end];
-	else
-		wr_mas->end_piv = wr_mas->mas->max;
-}
-
 static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
@@ -4245,6 +4233,21 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas)
 	}
 }
 
+static inline void mas_wr_end_piv(struct ma_wr_state *wr_mas)
+{
+	while ((wr_mas->offset_end < wr_mas->node_end) &&
+	       (wr_mas->mas->last > wr_mas->pivots[wr_mas->offset_end]))
+		wr_mas->offset_end++;
+
+	if (wr_mas->offset_end < wr_mas->node_end)
+		wr_mas->end_piv = wr_mas->pivots[wr_mas->offset_end];
+	else
+		wr_mas->end_piv = wr_mas->mas->max;
+
+	if (!wr_mas->entry)
+		mas_wr_extend_null(wr_mas);
+}
+
 static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas)
 {
 	struct ma_state *mas = wr_mas->mas;
@@ -4377,10 +4380,6 @@ static inline void *mas_wr_store_entry(struct ma_wr_state *wr_mas)
 
 	/* At this point, we are at the leaf node that needs to be altered. */
 	mas_wr_end_piv(wr_mas);
-
-	if (!wr_mas->entry)
-		mas_wr_extend_null(wr_mas);
-
 	/* New root for a single pointer */
 	if (unlikely(!mas->index && mas->last == ULONG_MAX)) {
 		mas_new_root(mas, wr_mas->entry);
Signature · 1 line
2.39.2
#12 lore raw

PATCH 12/14 maple_tree: Update mas_preallocate() testing

In reply to Liam R. Howlett
---
 tools/testing/radix-tree/maple.c | 27 ++++++++++++++++-----------
 1 file changed, 16 insertions(+), 11 deletions(-)
tools/testing/radix-tree/maple.c +16 -11
index cfadc4b75d51..14d89ba186ee 100644
@@ -35383,6 +35383,8 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	for (i = 0; i <= max; i++)
 		mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
 
+	/* Spanning store */
+	mas_set_range(&mas, 470, 500);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
@@ -35406,7 +35408,6 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mn = mas_pop_node(&mas);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
@@ -35420,7 +35421,6 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mn = mas_pop_node(&mas);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
@@ -35434,7 +35434,6 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mn = mas_pop_node(&mas);
 	MT_BUG_ON(mt, mas_allocated(&mas) != allocated - 1);
@@ -35448,33 +35447,37 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated == 0);
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 
+	/* Slot store does not need allocations */
+	mas_set_range(&mas, 6, 9);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
-	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated == 0);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	MT_BUG_ON(mt, allocated != 0);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+
+	mas_set_range(&mas, 6, 10);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated == 0);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	MT_BUG_ON(mt, allocated != 1);
 	mas_store_prealloc(&mas, ptr);
+	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 
+	/* Split */
+	mas_set_range(&mas, 54, 54);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
-	MT_BUG_ON(mt, allocated == 0);
-	MT_BUG_ON(mt, allocated != 1 + height * 3);
+	MT_BUG_ON(mt, allocated != 1 + height * 2);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
 	mt_set_non_kernel(1);
+	/* Spanning store */
+	mas_set_range(&mas, 1, 100);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
@@ -35482,6 +35485,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	mas_destroy(&mas);
 
 
+	/* Spanning store */
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL) != 0);
 	allocated = mas_allocated(&mas);
 	height = mas_mt_height(&mas);
@@ -35489,6 +35493,7 @@ static noinline void __init check_prealloc(struct maple_tree *mt)
 	MT_BUG_ON(mt, allocated != 1 + height * 3);
 	mas_store_prealloc(&mas, ptr);
 	MT_BUG_ON(mt, mas_allocated(&mas) != 0);
+	mas_set_range(&mas, 0, 200);
 	mt_set_non_kernel(1);
 	MT_BUG_ON(mt, mas_preallocate(&mas, ptr, GFP_KERNEL & GFP_NOWAIT) == 0);
 	allocated = mas_allocated(&mas);
Signature · 1 line
2.39.2
#13 lore raw

PATCH 13/14 maple_tree: Refine mas_preallocate() node calculations

In reply to Liam R. Howlett

Calculate the number of nodes based on the pending write action instead of assuming the worst case.

This addresses a performance regression introduced in platforms that have longer allocation timing.

---
 lib/maple_tree.c | 44 +++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 43 insertions(+), 1 deletion(-)
lib/maple_tree.c +43 -1
index adf662bc413e..5ea211c3f186 100644
@@ -5541,9 +5541,51 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
  */
 int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 {
+	MA_WR_STATE(wr_mas, mas, entry);
+	unsigned char node_size;
+	int request = 1;
 	int ret;
 
-	mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
+
+	if (unlikely(!mas->index && mas->last == ULONG_MAX))
+		goto ask_now;
+
+	mas_wr_store_setup(&wr_mas);
+	wr_mas.content = mas_start(mas);
+	/* Root expand */
+	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
+		goto ask_now;
+
+	if (unlikely(!mas_wr_walk(&wr_mas))) {
+		/* Spanning store, use worst case for now */
+		request = 1 + mas_mt_height(mas) * 3;
+		goto ask_now;
+	}
+
+	/* At this point, we are at the leaf node that needs to be altered. */
+	/* Exact fit, no nodes needed. */
+	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
+		return 0;
+
+	mas_wr_end_piv(&wr_mas);
+	node_size = mas_wr_new_end(&wr_mas);
+	if (node_size >= mt_slots[wr_mas.type]) {
+		/* Split, worst case for now. */
+		request = 1 + mas_mt_height(mas) * 2;
+		goto ask_now;
+	}
+
+	/* New root needs a singe node */
+	if (unlikely(mte_is_root(mas->node)))
+		goto ask_now;
+
+	/* Potential spanning rebalance collapsing a node, use worst-case */
+	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
+		request = mas_mt_height(mas) * 2 - 1;
+
+	/* node store, slot store needs one node */
+ask_now:
+	mas_node_count_gfp(mas, request, gfp);
 	mas->mas_flags |= MA_STATE_PREALLOC;
 	if (likely(!mas_is_err(mas)))
 		return 0;
Signature · 1 line
2.39.2
#14 lore raw

Re: [PATCH 13/14] maple_tree: Refine mas_preallocate() node calculations

Quoted 16 lines · Liam R. Howlett

Calculate the number of nodes based on the pending write action instead of assuming the worst case.

This addresses a performance regression introduced in platforms that have longer allocation timing.

---
  lib/maple_tree.c | 44 +++++++++++++++++++++++++++++++++++++++++++-
  1 file changed, 43 insertions(+), 1 deletion(-)
lib/maple_tree.c +0 -0
index adf662bc413e..5ea211c3f186 100644

lib/maple_tree.c EXPORT_SYMBOL_GPL(mas_store_prealloc); · line 5546

Quoted 6 lines
lib/maple_tree.c +3 -0
@@ -5541,9 +5541,51 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
   */
  int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
  {
+	MA_WR_STATE(wr_mas, mas, entry);
+	unsigned char node_size;
+	int request = 1;

If either mas_wr_append() or mas_wr_slot_store() succeeds, or does a simple replacement, we don't need to make any allocations.

Quoted 46 lines
lib/maple_tree.c +40 -1
  	int ret;
 
-	mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
+
+	if (unlikely(!mas->index && mas->last == ULONG_MAX))
+		goto ask_now;
+
+	mas_wr_store_setup(&wr_mas);
+	wr_mas.content = mas_start(mas);
+	/* Root expand */
+	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
+		goto ask_now;
+
+	if (unlikely(!mas_wr_walk(&wr_mas))) {
+		/* Spanning store, use worst case for now */
+		request = 1 + mas_mt_height(mas) * 3;
+		goto ask_now;
+	}
+
+	/* At this point, we are at the leaf node that needs to be altered. */
+	/* Exact fit, no nodes needed. */
+	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
+		return 0;
+
+	mas_wr_end_piv(&wr_mas);
+	node_size = mas_wr_new_end(&wr_mas);
+	if (node_size >= mt_slots[wr_mas.type]) {
+		/* Split, worst case for now. */
+		request = 1 + mas_mt_height(mas) * 2;
+		goto ask_now;
+	}
+
+	/* New root needs a singe node */
+	if (unlikely(mte_is_root(mas->node)))
+		goto ask_now;
+
+	/* Potential spanning rebalance collapsing a node, use worst-case */
+	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
+		request = mas_mt_height(mas) * 2 - 1;
+
+	/* node store, slot store needs one node */
+ask_now:
+	mas_node_count_gfp(mas, request, gfp);
  	mas->mas_flags |= MA_STATE_PREALLOC;
  	if (likely(!mas_is_err(mas)))
  		return 0;
#15 lore raw

Re: [PATCH 13/14] maple_tree: Refine mas_preallocate() node calculations

Quoted 14 lines · Peng Zhang
Quoted 11 lines · Liam R. Howlett

Calculate the number of nodes based on the pending write action instead of assuming the worst case.

This addresses a performance regression introduced in platforms that have longer allocation timing.

---
  lib/maple_tree.c | 44 +++++++++++++++++++++++++++++++++++++++++++-
  1 file changed, 43 insertions(+), 1 deletion(-)
Quoted 13 lines

lib/maple_tree.c EXPORT_SYMBOL_GPL(mas_store_prealloc); · line 5546

Quoted 11 lines
lib/maple_tree.c +3 -0
index adf662bc413e..5ea211c3f186 100644
@@ -5541,9 +5541,51 @@ EXPORT_SYMBOL_GPL(mas_store_prealloc);
   */
  int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
  {
+	MA_WR_STATE(wr_mas, mas, entry);
+	unsigned char node_size;
+	int request = 1;

If either mas_wr_append() or mas_wr_slot_store() succeeds, or does a simple replacement, we don't need to make any allocations.

Thanks for looking at this.

See below

Quoted 14 lines
Quoted 14 lines
lib/maple_tree.c +12 -1
  	int ret;
-	mas_node_count_gfp(mas, 1 + mas_mt_height(mas) * 3, gfp);
+
+	if (unlikely(!mas->index && mas->last == ULONG_MAX))
+		goto ask_now;
+
+	mas_wr_store_setup(&wr_mas);
+	wr_mas.content = mas_start(mas);
+	/* Root expand */
+	if (unlikely(mas_is_none(mas) || mas_is_ptr(mas)))
+		goto ask_now;
+
+	if (unlikely(!mas_wr_walk(&wr_mas))) {
+		/* Spanning store, use worst case for now */
Quoted 8 lines

lib/maple_tree.c EXPORT_SYMBOL_GPL(mas_store_prealloc); · line 5568

Quoted 8 lines
lib/maple_tree.c +8 -0
+		request = 1 + mas_mt_height(mas) * 3;
+		goto ask_now;
+	}
+
+	/* At this point, we are at the leaf node that needs to be altered. */
+	/* Exact fit, no nodes needed. */
+	if (wr_mas.r_min == mas->index && wr_mas.r_max == mas->last)
+		return 0;

The exact fit (simple replacement) case is covered here.

Quoted 9 lines

lib/maple_tree.c EXPORT_SYMBOL_GPL(mas_store_prealloc); · line 5576

Quoted 9 lines
lib/maple_tree.c +8 -0
+
+	mas_wr_end_piv(&wr_mas);
+	node_size = mas_wr_new_end(&wr_mas);
 
+	if (node_size >= mt_slots[wr_mas.type]) {
+		/* Split, worst case for now. */
+		request = 1 + mas_mt_height(mas) * 2;
+		goto ask_now;
+	}

I will look at adding the mas_wr_append() and mas_wr_slot_store() checks as well. I suspect it will need to live around here.

I'm debating a function that returns the type of store and saving it in mas (wr_mas does not live beyond this function). The mas store type could be cleared unless mas_store_prealloc() is used. This would avoid duplicating this work on the actual write operation.

Quoted 15 lines
Quoted 15 lines
lib/maple_tree.c +12 -0
+
+	/* New root needs a singe node */
+	if (unlikely(mte_is_root(mas->node)))
+		goto ask_now;
+
+	/* Potential spanning rebalance collapsing a node, use worst-case */
+	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
+		request = mas_mt_height(mas) * 2 - 1;
+
+	/* node store, slot store needs one node */
+ask_now:
+	mas_node_count_gfp(mas, request, gfp);
  	mas->mas_flags |= MA_STATE_PREALLOC;
  	if (likely(!mas_is_err(mas)))
  		return 0;
#16 lore raw

PATCH 14/14 mm/mmap: Change vma iteration order in do_vmi_align_munmap()

In reply to Liam R. Howlett

By delaying the setting of prev/next VMA until after the write of NULL, the probability of the prev/next VMA already being in the CPU cache is significantly increased, especially for larger munmap operations. It also means that prev/next will be loaded closer to when they are used.

This has the consequence of needing to change the for_each() to a do {} for_each() when writing to the side tree.

Since prev will be set later in the function, it is better to reverse the splitting direction of the start VMA (modify the new_below argument to __split_vma).

Using the vma_iter_prev_range() to walk back to the correct location in the tree will, on the most part, mean walking within the CPU cache. Usually, this is two steps vs a node reset and a tree re-walk.

---
 mm/mmap.c | 27 ++++++++++++---------------
 1 file changed, 12 insertions(+), 15 deletions(-)
mm/mmap.c +12 -15
index eaebcc8f60d2..429e314bd134 100644
@@ -2395,20 +2395,17 @@ do_vmi_align_munmap(struct vma_iterator *vmi, struct vm_area_struct *vma,
 		if (end < vma->vm_end && mm->map_count >= sysctl_max_map_count)
 			goto map_count_exceeded;
 
-		error = __split_vma(vmi, vma, start, 0);
+		error = __split_vma(vmi, vma, start, 1);
 		if (error)
 			goto start_split_failed;
-
-		vma = vma_iter_load(vmi);
 	}
 
-	prev = vma_prev(vmi);
-
 	/*
 	 * Detach a range of VMAs from the mm. Using next as a temp variable as
 	 * it is always overwritten.
 	 */
-	for_each_vma_range(*vmi, next, end) {
+	next = vma;
+	do {
 		/* Does it split the end? */
 		if (next->vm_end > end) {
 			error = __split_vma(vmi, next, end, 0);
@@ -2440,13 +2437,7 @@ do_vmi_align_munmap(struct vma_iterator *vmi, struct vm_area_struct *vma,
 		BUG_ON(next->vm_start < start);
 		BUG_ON(next->vm_start > end);
 #endif
-	}
-
-	if (vma_iter_end(vmi) > end)
-		next = vma_iter_load(vmi);
-
-	if (!next)
-		next = vma_next(vmi);
+	} for_each_vma_range(*vmi, next, end);
 
 #if defined(CONFIG_DEBUG_VM_MAPLE_TREE)
 	/* Make sure no VMAs are about to be lost. */
@@ -2467,12 +2458,18 @@ do_vmi_align_munmap(struct vma_iterator *vmi, struct vm_area_struct *vma,
 		BUG_ON(count != test_count);
 	}
 #endif
-	/* Point of no return */
-	vma_iter_set(vmi, start);
+	while (vma_iter_addr(vmi) > start)
+		vma_iter_prev_range(vmi);
+
 	if (vma_iter_clear_gfp(vmi, start, end, GFP_KERNEL))
 		return -ENOMEM;
 
 	mm->map_count -= count;
+	prev = vma_iter_prev_range(vmi);
+	next = vma_next(vmi);
+	if (next)
+		vma_iter_prev_range(vmi);
+
 	/*
 	 * Do not downgrade mmap_lock if we are next to VM_GROWSDOWN or
 	 * VM_GROWSUP VMA. Such VMAs can change their size under
Signature · 1 line
2.39.2
#17 lore raw
In reply to Liam R. Howlett

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down. This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating. This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree
0005: Small cleanup of do_vmi_align_munmap()
0006-0013: mas_preallocate() calculation change
0014: Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
503880
Base with this patchset:
519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
718080

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
maple_tree: Add benchmarking for mas_for_each
maple_tree: Add benchmarking for mas_prev()
mm: Move unmap_vmas() declaration to internal header
mm: Change do_vmi_align_munmap() side tree index
mm: Remove prev check from do_vmi_align_munmap()
maple_tree: Introduce __mas_set_range()
mm: Remove re-walk from mmap_region()
maple_tree: Re-introduce entry to mas_preallocate() arguments
mm: Use vma_iter_clear_gfp() in nommu
mm: Set up vma iterator for vma_iter_prealloc() calls
maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
maple_tree: Update mas_preallocate() testing
maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

 fs/exec.c                        |   1 +
 include/linux/maple_tree.h       |  23 ++++-
 include/linux/mm.h               |   4 -
 lib/maple_tree.c                 |  78 ++++++++++----
 lib/test_maple_tree.c            |  74 +++++++++++++
 mm/internal.h                    |  40 ++++++--
 mm/memory.c                      |  16 ++-
 mm/mmap.c                        | 171 ++++++++++++++++---------------
 mm/nommu.c                       |  45 ++++----
 tools/testing/radix-tree/maple.c |  59 ++++++-----
 10 files changed, 331 insertions(+), 180 deletions(-)
#18 lore raw
Quoted 36 lines · Yin, Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down. This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating. This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree
0005: Small cleanup of do_vmi_align_munmap()
0006-0013: mas_preallocate() calculation change
0014: Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
503880
Base with this patchset:
519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Thanks for retesting. I've not been able to see the regression myself. Are you running in a VM of sorts? Android and some cloud VMs seem to see this, but I do not in kvm or the server I test on.

I am still looking to reduce/reverse the regression and a reproducer on my end would help.

Quoted 36 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
maple_tree: Add benchmarking for mas_for_each
maple_tree: Add benchmarking for mas_prev()
mm: Move unmap_vmas() declaration to internal header
mm: Change do_vmi_align_munmap() side tree index
mm: Remove prev check from do_vmi_align_munmap()
maple_tree: Introduce __mas_set_range()
mm: Remove re-walk from mmap_region()
maple_tree: Re-introduce entry to mas_preallocate() arguments
mm: Use vma_iter_clear_gfp() in nommu
mm: Set up vma iterator for vma_iter_prealloc() calls
maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
maple_tree: Update mas_preallocate() testing
maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

 fs/exec.c                        |   1 +
 include/linux/maple_tree.h       |  23 ++++-
 include/linux/mm.h               |   4 -
 lib/maple_tree.c                 |  78 ++++++++++----
 lib/test_maple_tree.c            |  74 +++++++++++++
 mm/internal.h                    |  40 ++++++--
 mm/memory.c                      |  16 ++-
 mm/mmap.c                        | 171 ++++++++++++++++---------------
 mm/nommu.c                       |  45 ++++----
 tools/testing/radix-tree/maple.c |  59 ++++++-----
 10 files changed, 331 insertions(+), 180 deletions(-)
#19 lore raw

Hi Liam,

Quoted 41 lines · Liam R. Howlett
Quoted 40 lines · Yin, Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down. This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating. This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree
0005: Small cleanup of do_vmi_align_munmap()
0006-0013: mas_preallocate() calculation change
0014: Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
503880
Base with this patchset:
519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
718080

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

Quoted 7 lines
Quoted 4 lines

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Thanks for retesting. I've not been able to see the regression myself. Are you running in a VM of sorts? Android and some cloud VMs seem to

I didn't run it in VM. I run it on a native env.

Quoted 4 lines

see this, but I do not in kvm or the server I test on.

I am still looking to reduce/reverse the regression and a reproducer on my end would help.

The test is page_test of AIM9. You could get AIM9 test suite from:
http://nchc.dl.sourceforge.net/project/aimbench/aim-suite9

After build it, we could see app singleuser.

It needs a txt file named s9workfile to define the test case. The s9workfile I am using has following content:

# @(#) s9workfile:1.2 1/22/96 00:00:00
# AIM Independent Resource Benchmark - Suite IX Workfile
FILESIZE: 5M
page_test

Then you can run the testing by command:
./singleuser -nl

It will ask some configuration questions and then run the real test.

One thing need be taken care is that the create-clo.c has one line:
newbrk = sbrk(-4096 * 16);

It should be updated as:
intptr_t inc = -4096 * 16;
newbrk = sbrk(inc);

Otherwise, the -4096 * 16 will be treated as 32 bit and the line is changed to extend brk to around 4G. If we don't have enough RAM, the set_brk syscall will fail.

If you met any issue to run the test, just ping me. Thanks.

Regards
Yin, Fengwei

Quoted 37 lines
Quoted 37 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
maple_tree: Add benchmarking for mas_for_each
maple_tree: Add benchmarking for mas_prev()
mm: Move unmap_vmas() declaration to internal header
mm: Change do_vmi_align_munmap() side tree index
mm: Remove prev check from do_vmi_align_munmap()
maple_tree: Introduce __mas_set_range()
mm: Remove re-walk from mmap_region()
maple_tree: Re-introduce entry to mas_preallocate() arguments
mm: Use vma_iter_clear_gfp() in nommu
mm: Set up vma iterator for vma_iter_prealloc() calls
maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
maple_tree: Update mas_preallocate() testing
maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

 fs/exec.c                        |   1 +
 include/linux/maple_tree.h       |  23 ++++-
 include/linux/mm.h               |   4 -
 lib/maple_tree.c                 |  78 ++++++++++----
 lib/test_maple_tree.c            |  74 +++++++++++++
 mm/internal.h                    |  40 ++++++--
 mm/memory.c                      |  16 ++-
 mm/mmap.c                        | 171 ++++++++++++++++---------------
 mm/nommu.c                       |  45 ++++----
 tools/testing/radix-tree/maple.c |  59 ++++++-----
 10 files changed, 331 insertions(+), 180 deletions(-)
#20 lore raw
In reply to Yin, Fengwei
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down. This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating. This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree
0005: Small cleanup of do_vmi_align_munmap()
0006-0013: mas_preallocate() calculation change
0014: Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):

   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):

   718080
Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

Thanks,
Peng

lib/maple_tree.c +5 -4
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 		goto ask_now;
 	}
 
-	/* New root needs a singe node */
-	if (unlikely(mte_is_root(mas->node)))
-		goto ask_now;
+	if ((node_size == wr_mas.node_end + 1 &&
+	     mas->offset == wr_mas.node_end) ||
+	    (node_size == wr_mas.node_end &&
+	     wr_mas.offset_end - mas->offset == 1))
+		return 0;
 
 	/* Potential spanning rebalance collapsing a node, use worst-case */
 	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
 	if (likely(!mas_is_err(mas)))
 		return 0;
 
-	mas_set_alloc_req(mas, 0);
 	ret = xa_err(mas->node);
 	mas_reset(mas);
 	mas_destroy(mas);
Quoted 36 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
maple_tree: Add benchmarking for mas_for_each
maple_tree: Add benchmarking for mas_prev()
mm: Move unmap_vmas() declaration to internal header
mm: Change do_vmi_align_munmap() side tree index
mm: Remove prev check from do_vmi_align_munmap()
maple_tree: Introduce __mas_set_range()
mm: Remove re-walk from mmap_region()
maple_tree: Re-introduce entry to mas_preallocate() arguments
mm: Use vma_iter_clear_gfp() in nommu
mm: Set up vma iterator for vma_iter_prealloc() calls
maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
maple_tree: Update mas_preallocate() testing
maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

  fs/exec.c                        |   1 +
  include/linux/maple_tree.h       |  23 ++++-
  include/linux/mm.h               |   4 -
  lib/maple_tree.c                 |  78 ++++++++++----
  lib/test_maple_tree.c            |  74 +++++++++++++
  mm/internal.h                    |  40 ++++++--
  mm/memory.c                      |  16 ++-
  mm/mmap.c                        | 171 ++++++++++++++++---------------
  mm/nommu.c                       |  45 ++++----
  tools/testing/radix-tree/maple.c |  59 ++++++-----
  10 files changed, 331 insertions(+), 180 deletions(-)
#21 lore raw

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
   718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:
529040

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Regards
Yin, Fengwei

Quoted 69 lines

Thanks,
Peng

lib/maple_tree.c +5 -4
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
          goto ask_now;
      }
 
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;
 
      /* Potential spanning rebalance collapsing a node, use worst-case */
      if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
      if (likely(!mas_is_err(mas)))
          return 0;
 
-    mas_set_alloc_req(mas, 0);
      ret = xa_err(mas->node);
      mas_reset(mas);
      mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

  fs/exec.c                        |   1 + include/linux/maple_tree.h       |  23 ++++- include/linux/mm.h               |   4 -
  lib/maple_tree.c                 |  78 ++++++++++---- lib/test_maple_tree.c            |  74 +++++++++++++ mm/internal.h                    |  40 ++++++-- mm/memory.c                      |  16 ++-
  mm/mmap.c                        | 171 ++++++++++++++++--------------- mm/nommu.c                       |  45 ++++---- tools/testing/radix-tree/maple.c |  59 ++++++-----

  10 files changed, 331 insertions(+), 180 deletions(-)
#22 lore raw
Quoted 57 lines · Yin Fengwei

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
   718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

Quoted 6 lines

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:
529040

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Just noticed that the commit f5715584af95 make validate_mm() two implementation based on CONFIG_DEBUG_VM instead of CONFIG_DEBUG_VM_MAPPLE_TREE). I have CONFIG_DEBUG_VM but not CONFIG_DEBUG_VM_MAPPLE_TREE defined. So it's not an apple to apple.

I disable CONFIG_DEBUG_VM and re-run the test and got:
Before preallocation change (7be1c1a3c7b1):

    770100
After preallocation change (28c5609fb236):
    680000
With liam's fix:
    702100
plus Peng's fix:
    725900

Regards
Yin, Fengwei

Quoted 74 lines

Regards
Yin, Fengwei

Quoted 69 lines

Thanks,
Peng

lib/maple_tree.c +5 -4
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
          goto ask_now;
      }
 
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;
 
      /* Potential spanning rebalance collapsing a node, use worst-case */
      if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
      if (likely(!mas_is_err(mas)))
          return 0;
 
-    mas_set_alloc_req(mas, 0);
      ret = xa_err(mas->node);
      mas_reset(mas);
      mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

  fs/exec.c                        |   1 + include/linux/maple_tree.h       |  23 ++++- include/linux/mm.h               |   4 -
  lib/maple_tree.c                 |  78 ++++++++++---- lib/test_maple_tree.c            |  74 +++++++++++++ mm/internal.h                    |  40 ++++++-- mm/memory.c                      |  16 ++-
  mm/mmap.c                        | 171 ++++++++++++++++--------------- mm/nommu.c                       |  45 ++++---- tools/testing/radix-tree/maple.c |  59 ++++++-----

  10 files changed, 331 insertions(+), 180 deletions(-)
#23 lore raw
Quoted 74 lines · Fengwei
Quoted 57 lines · Yin Fengwei

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
   718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

Quoted 6 lines

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:

   529040

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Just noticed that the commit f5715584af95 make validate_mm() two implementation based on CONFIG_DEBUG_VM instead of CONFIG_DEBUG_VM_MAPPLE_TREE). I have CONFIG_DEBUG_VM but not CONFIG_DEBUG_VM_MAPPLE_TREE defined. So it's not an apple to apple.

I disable CONFIG_DEBUG_VM and re-run the test and got:
Before preallocation change (7be1c1a3c7b1):

Quoted 7 lines
     770100
After preallocation change (28c5609fb236):
     680000
With liam's fix:
     702100
plus Peng's fix:
     725900

Thank you for your test, now it seems that the performance regression is not so much.

Quoted 79 lines

Regards
Yin, Fengwei

Quoted 74 lines

Regards
Yin, Fengwei

Quoted 69 lines

Thanks,
Peng

lib/maple_tree.c +5 -4
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
          goto ask_now;
      }
 
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;
 
      /* Potential spanning rebalance collapsing a node, use worst-case */
      if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
      if (likely(!mas_is_err(mas)))
          return 0;
 
-    mas_set_alloc_req(mas, 0);
      ret = xa_err(mas->node);
      mas_reset(mas);
      mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

   fs/exec.c                        |   1 +
   include/linux/maple_tree.h       |  23 ++++-
   include/linux/mm.h               |   4 -
   lib/maple_tree.c                 |  78 ++++++++++----
   lib/test_maple_tree.c            |  74 +++++++++++++
   mm/internal.h                    |  40 ++++++--
   mm/memory.c                      |  16 ++-
   mm/mmap.c                        | 171 ++++++++++++++++---------------
   mm/nommu.c                       |  45 ++++----
   tools/testing/radix-tree/maple.c |  59 ++++++-----
   10 files changed, 331 insertions(+), 180 deletions(-)
#24 lore raw
Quoted 67 lines · Peng Zhang
Quoted 64 lines · Fengwei
Quoted 61 lines · Yin Fengwei

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
   718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:

   529040
Quoted 6 lines
Quoted 6 lines
Quoted 2 lines

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Just noticed that the commit f5715584af95 make validate_mm() two implementation based on CONFIG_DEBUG_VM instead of CONFIG_DEBUG_VM_MAPPLE_TREE). I have CONFIG_DEBUG_VM but not CONFIG_DEBUG_VM_MAPPLE_TREE defined. So it's not an apple to apple.

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Quoted 11 lines
Quoted 11 lines

I disable CONFIG_DEBUG_VM and re-run the test and got:
Before preallocation change (7be1c1a3c7b1):

     770100
After preallocation change (28c5609fb236):
     680000
With liam's fix:
     702100
plus Peng's fix:
     725900
Quoted 2 lines

Thank you for your test, now it seems that the performance regression is not so much.

We are also too strict on the reset during mas_store_prealloc() checking for a spanning write. I have a fix for this for v2 of the patch set, although I suspect it will not make a huge difference.

Quoted 22 lines
Quoted 22 lines

Regards
Yin, Fengwei

Quoted 17 lines

Regards
Yin, Fengwei

Quoted 12 lines

Thanks,
Peng

lib/maple_tree.c +0 -0
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
          goto ask_now;
      }
 
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5580

Quoted 3 lines
lib/maple_tree.c +0 -3
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;

Why did you drop this? If we are creating a new root we will only need one node.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5582

Quoted 5 lines
lib/maple_tree.c +5 -0
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;

I will add this to v2 as well, or something similar.

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5593

Quoted 8 lines
lib/maple_tree.c +0 -1
      /* Potential spanning rebalance collapsing a node, use worst-case */
      if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
      if (likely(!mas_is_err(mas)))
          return 0;
 
-    mas_set_alloc_req(mas, 0);

Why did you drop this? It seems like a worth while cleanup on failure.

Quoted 41 lines
Quoted 41 lines
Quoted 41 lines
Quoted 41 lines
lib/maple_tree.c +0 -0
      ret = xa_err(mas->node);
      mas_reset(mas);
      mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

   fs/exec.c                        |   1 +
   include/linux/maple_tree.h       |  23 ++++-
   include/linux/mm.h               |   4 -
   lib/maple_tree.c                 |  78 ++++++++++----
   lib/test_maple_tree.c            |  74 +++++++++++++
   mm/internal.h                    |  40 ++++++--
   mm/memory.c                      |  16 ++-
   mm/mmap.c                        | 171 ++++++++++++++++---------------
   mm/nommu.c                       |  45 ++++----
   tools/testing/radix-tree/maple.c |  59 ++++++-----
   10 files changed, 331 insertions(+), 180 deletions(-)
#25 lore raw
Quoted 123 lines · Liam R. Howlett
Quoted 67 lines · Peng Zhang
Quoted 64 lines · Fengwei
Quoted 61 lines · Yin Fengwei

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
   718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:

    529040
Quoted 6 lines
Quoted 6 lines
Quoted 2 lines

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Just noticed that the commit f5715584af95 make validate_mm() two implementation based on CONFIG_DEBUG_VM instead of CONFIG_DEBUG_VM_MAPPLE_TREE). I have CONFIG_DEBUG_VM but not CONFIG_DEBUG_VM_MAPPLE_TREE defined. So it's not an apple to apple.

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Quoted 11 lines
Quoted 11 lines

I disable CONFIG_DEBUG_VM and re-run the test and got:
Before preallocation change (7be1c1a3c7b1):

      770100
After preallocation change (28c5609fb236):
      680000
With liam's fix:
      702100
plus Peng's fix:
      725900
Quoted 2 lines

Thank you for your test, now it seems that the performance regression is not so much.

We are also too strict on the reset during mas_store_prealloc() checking for a spanning write. I have a fix for this for v2 of the patch set, although I suspect it will not make a huge difference.

Quoted 22 lines
Quoted 22 lines

Regards
Yin, Fengwei

Quoted 17 lines

Regards
Yin, Fengwei

Quoted 12 lines

Thanks,
Peng

lib/maple_tree.c +0 -0
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
           goto ask_now;
       }
 
Quoted 6 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5580

Quoted 3 lines
lib/maple_tree.c +0 -3
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;

Why did you drop this? If we are creating a new root we will only need one node.

The code below handles the root case perfectly,
we don't need additional checks.

	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
		request = mas_mt_height(mas) * 2 - 1;
Quoted 16 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5582

Quoted 6 lines
lib/maple_tree.c +5 -0
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;

I will add this to v2 as well, or something similar.

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
lib/maple_tree.c +0 -0
       /* Potential spanning rebalance collapsing a node, use worst-case */
       if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
       if (likely(!mas_is_err(mas)))
           return 0;
 
Quoted 3 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5593

Quoted 1 line
lib/maple_tree.c +0 -1
-    mas_set_alloc_req(mas, 0);

Why did you drop this? It seems like a worth while cleanup on failure.

Because we will clear it in mas_node_count_gfp()->mas_alloc_nodes().

Quoted 42 lines
Quoted 42 lines
Quoted 42 lines
Quoted 42 lines
Quoted 42 lines
lib/maple_tree.c +0 -0
       ret = xa_err(mas->node);
       mas_reset(mas);
       mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

    fs/exec.c                        |   1 +
    include/linux/maple_tree.h       |  23 ++++-
    include/linux/mm.h               |   4 -
    lib/maple_tree.c                 |  78 ++++++++++----
    lib/test_maple_tree.c            |  74 +++++++++++++
    mm/internal.h                    |  40 ++++++--
    mm/memory.c                      |  16 ++-
    mm/mmap.c                        | 171 ++++++++++++++++---------------
    mm/nommu.c                       |  45 ++++----
    tools/testing/radix-tree/maple.c |  59 ++++++-----
    10 files changed, 331 insertions(+), 180 deletions(-)
#26 lore raw
Quoted 132 lines · Peng Zhang
Quoted 123 lines · Liam R. Howlett
Quoted 67 lines · Peng Zhang
Quoted 64 lines · Fengwei
Quoted 61 lines · Yin Fengwei

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
   718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:

    529040
Quoted 6 lines
Quoted 6 lines
Quoted 2 lines

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Just noticed that the commit f5715584af95 make validate_mm() two implementation based on CONFIG_DEBUG_VM instead of CONFIG_DEBUG_VM_MAPPLE_TREE). I have CONFIG_DEBUG_VM but not CONFIG_DEBUG_VM_MAPPLE_TREE defined. So it's not an apple to apple.

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Quoted 11 lines
Quoted 11 lines

I disable CONFIG_DEBUG_VM and re-run the test and got:
Before preallocation change (7be1c1a3c7b1):

      770100
After preallocation change (28c5609fb236):
      680000
With liam's fix:
      702100
plus Peng's fix:
      725900
Quoted 2 lines

Thank you for your test, now it seems that the performance regression is not so much.

We are also too strict on the reset during mas_store_prealloc() checking for a spanning write. I have a fix for this for v2 of the patch set, although I suspect it will not make a huge difference.

Quoted 22 lines
Quoted 22 lines

Regards
Yin, Fengwei

Quoted 17 lines

Regards
Yin, Fengwei

Quoted 12 lines

Thanks,
Peng

lib/maple_tree.c +0 -0
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
           goto ask_now;
       }
 
Quoted 6 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5580

Quoted 3 lines
lib/maple_tree.c +0 -3
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;

Why did you drop this? If we are creating a new root we will only need one node.

Quoted 4 lines

The code below handles the root case perfectly,
we don't need additional checks.

	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
		request = mas_mt_height(mas) * 2 - 1;

Unless we have the minimum for a node, in which case we will fall through and ask for one node. This works and is rare enough so I'll drop it. Thanks.

Quoted 16 lines
Quoted 16 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5582

Quoted 6 lines
lib/maple_tree.c +5 -0
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;

I will add this to v2 as well, or something similar.

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
lib/maple_tree.c +0 -0
       /* Potential spanning rebalance collapsing a node, use worst-case */
       if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
       if (likely(!mas_is_err(mas)))
           return 0;
 
Quoted 4 lines
Quoted 3 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5593

Quoted 1 line
lib/maple_tree.c +0 -1
-    mas_set_alloc_req(mas, 0);

Why did you drop this? It seems like a worth while cleanup on failure.

Because we will clear it in mas_node_count_gfp()->mas_alloc_nodes().

On failure we set the alloc request to the remainder of what was not allocated.

Quoted 42 lines
Quoted 42 lines
Quoted 42 lines
Quoted 42 lines
Quoted 42 lines
Quoted 42 lines
lib/maple_tree.c +0 -0
       ret = xa_err(mas->node);
       mas_reset(mas);
       mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

    fs/exec.c                        |   1 +
    include/linux/maple_tree.h       |  23 ++++-
    include/linux/mm.h               |   4 -
    lib/maple_tree.c                 |  78 ++++++++++----
    lib/test_maple_tree.c            |  74 +++++++++++++
    mm/internal.h                    |  40 ++++++--
    mm/memory.c                      |  16 ++-
    mm/mmap.c                        | 171 ++++++++++++++++---------------
    mm/nommu.c                       |  45 ++++----
    tools/testing/radix-tree/maple.c |  59 ++++++-----
    10 files changed, 331 insertions(+), 180 deletions(-)
#27 lore raw
Quoted 158 lines · Liam R. Howlett
Quoted 132 lines · Peng Zhang
Quoted 123 lines · Liam R. Howlett
Quoted 67 lines · Peng Zhang
Quoted 64 lines · Fengwei
Quoted 61 lines · Yin Fengwei

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):

      503880
Base with this patchset:
      519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):

      718080
Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:

     529040
Quoted 6 lines
Quoted 6 lines
Quoted 2 lines

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Just noticed that the commit f5715584af95 make validate_mm() two implementation based on CONFIG_DEBUG_VM instead of CONFIG_DEBUG_VM_MAPPLE_TREE). I have CONFIG_DEBUG_VM but not CONFIG_DEBUG_VM_MAPPLE_TREE defined. So it's not an apple to apple.

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Quoted 11 lines
Quoted 11 lines

I disable CONFIG_DEBUG_VM and re-run the test and got:
Before preallocation change (7be1c1a3c7b1):

       770100
After preallocation change (28c5609fb236):
       680000
With liam's fix:
       702100
plus Peng's fix:
       725900
Quoted 2 lines

Thank you for your test, now it seems that the performance regression is not so much.

We are also too strict on the reset during mas_store_prealloc() checking for a spanning write. I have a fix for this for v2 of the patch set, although I suspect it will not make a huge difference.

Quoted 22 lines
Quoted 22 lines

Regards
Yin, Fengwei

Quoted 17 lines

Regards
Yin, Fengwei

Quoted 12 lines

Thanks,
Peng

lib/maple_tree.c +0 -0
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
            goto ask_now;
        }
 
Quoted 6 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5580

Quoted 3 lines
lib/maple_tree.c +0 -3
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;

Why did you drop this? If we are creating a new root we will only need one node.

Quoted 4 lines

The code below handles the root case perfectly,
we don't need additional checks.

	if (node_size  - 1 <= mt_min_slots[wr_mas.type])
		request = mas_mt_height(mas) * 2 - 1;

Unless we have the minimum for a node, in which case we will fall through and ask for one node. This works and is rare enough so I'll drop it. Thanks.

Quoted 16 lines
Quoted 16 lines
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5582

Quoted 6 lines
lib/maple_tree.c +5 -0
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;

I will add this to v2 as well, or something similar.

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
lib/maple_tree.c +0 -0
        /* Potential spanning rebalance collapsing a node, use worst-case */
        if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
        if (likely(!mas_is_err(mas)))
            return 0;
 
Quoted 7 lines
Quoted 4 lines
Quoted 3 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5593

Quoted 1 line
lib/maple_tree.c +0 -1
-    mas_set_alloc_req(mas, 0);

Why did you drop this? It seems like a worth while cleanup on failure.

Because we will clear it in mas_node_count_gfp()->mas_alloc_nodes().

On failure we set the alloc request to the remainder of what was not allocated.

Yes, you are right.

Quoted 43 lines
Quoted 43 lines
Quoted 43 lines
Quoted 43 lines
Quoted 43 lines
Quoted 43 lines
Quoted 43 lines
lib/maple_tree.c +0 -0
        ret = xa_err(mas->node);
        mas_reset(mas);
        mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

     fs/exec.c                        |   1 +
     include/linux/maple_tree.h       |  23 ++++-
     include/linux/mm.h               |   4 -
     lib/maple_tree.c                 |  78 ++++++++++----
     lib/test_maple_tree.c            |  74 +++++++++++++
     mm/internal.h                    |  40 ++++++--
     mm/memory.c                      |  16 ++-
     mm/mmap.c                        | 171 ++++++++++++++++---------------
     mm/nommu.c                       |  45 ++++----
     tools/testing/radix-tree/maple.c |  59 ++++++-----
     10 files changed, 331 insertions(+), 180 deletions(-)
#28 lore raw
In reply to Liam R. Howlett
Quoted 70 lines · Liam R. Howlett
Quoted 69 lines · Peng Zhang
Quoted 66 lines · Fengwei
Quoted 63 lines · Yin Fengwei

Hi Peng,

Quoted 47 lines · Peng Zhang
Quoted 36 lines · Fengwei

Hi Liam,

Quoted 14 lines · Liam R. Howlett

Initial work on preallocations showed no regression in performance during testing, but recently some users (both on [1] and off [android] list) have reported that preallocating the worst-case number of nodes has caused some slow down.  This patch set addresses the number of allocations in a few ways.

During munmap() most munmap() operations will remove a single VMA, so leverage the fact that the maple tree can place a single pointer at range 0 - 0 without allocating.  This is done by changing the index in the 'sidetree'.

Re-introduce the entry argument to mas_preallocate() so that a more intelligent guess of the node count can be made.

Quoted 6 lines

Patches are in the following order:
0001-0002: Testing framework for benchmarking some operations 0003-0004: Reduction of maple node allocation in sidetree 0005:      Small cleanup of do_vmi_align_munmap() 0006-0013: mas_preallocate() calculation change 0014:      Change the vma iterator order

I did run The AIM:page_test on an IceLake 48C/96T + 192G RAM platform with this patchset.

The result has a little bit improvement:
Base (next-20230602):
   503880
Base with this patchset:
   519501

But they are far from the none-regression result (commit 7be1c1a3c7b1):
   718080

Quoted 8 lines

Some other information I collected:
With Base, the mas_alloc_nodes are always hit with request: 7. With this patchset, the request are 1 or 5.

I suppose this is the reason for improvement from 503880 to 519501.

With commit 7be1c1a3c7b1, mas_store_gfp() in do_brk_flags never triggered mas_alloc_nodes() call. Thanks.

Quoted 7 lines

Hi Fengwei,

I think it may be related to the inaccurate number of nodes allocated in the pre-allocation. I slightly modified the pre-allocation in this patchset, but I don't know if it works. It would be great if you could help test it, and help pinpoint the cause. Below is the diff, which can be applied based on this pachset.

I tried the patch, it could eliminate the call of mas_alloc_nodes() during the test. But the result of benchmark got a little bit improvement:

   529040

But it's still much less than none-regression result. I will also double confirm the none-regression result.

Quoted 7 lines
Quoted 4 lines
Quoted 4 lines

Just noticed that the commit f5715584af95 make validate_mm() two implementation based on CONFIG_DEBUG_VM instead of CONFIG_DEBUG_VM_MAPPLE_TREE). I have CONFIG_DEBUG_VM but not CONFIG_DEBUG_VM_MAPPLE_TREE defined. So it's not an apple to apple.

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

Yes. The f5715584af95 was from next-20230602. I will include the subject of the patch in the future to avoid such confusion.

Quoted 5 lines

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

No worries here. The problem is in my local config. I enabled the CONFIG_DEBUG_VM to capture VM asserts/warnings. It should be disabled for performance testing. LKP does disable it for performance check.

Regards
Yin, Fengwei

Quoted 108 lines
Quoted 12 lines
Quoted 5 lines

I disable CONFIG_DEBUG_VM and re-run the test and got:
Before preallocation change (7be1c1a3c7b1):

Quoted 7 lines
     770100
After preallocation change (28c5609fb236):
     680000
With liam's fix:
     702100
plus Peng's fix:
     725900
Quoted 2 lines

Thank you for your test, now it seems that the performance regression is not so much.

We are also too strict on the reset during mas_store_prealloc() checking for a spanning write. I have a fix for this for v2 of the patch set, although I suspect it will not make a huge difference.

Quoted 22 lines
Quoted 22 lines

Regards
Yin, Fengwei

Quoted 17 lines

Regards
Yin, Fengwei

Quoted 12 lines

Thanks,
Peng

lib/maple_tree.c +0 -0
index 5ea211c3f186..e67bf2744384 100644
@@ -5575,9 +5575,11 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
          goto ask_now;
      }
 
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5580

Quoted 3 lines
lib/maple_tree.c +0 -3
-    /* New root needs a singe node */
-    if (unlikely(mte_is_root(mas->node)))
-        goto ask_now;

Why did you drop this? If we are creating a new root we will only need one node.

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5582

Quoted 5 lines
lib/maple_tree.c +5 -0
+    if ((node_size == wr_mas.node_end + 1 &&
+         mas->offset == wr_mas.node_end) ||
+        (node_size == wr_mas.node_end &&
+         wr_mas.offset_end - mas->offset == 1))
+        return 0;

I will add this to v2 as well, or something similar.

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/maple_tree.c int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp) · line 5593

Quoted 8 lines
lib/maple_tree.c +0 -1
      /* Potential spanning rebalance collapsing a node, use worst-case */
      if (node_size  - 1 <= mt_min_slots[wr_mas.type])
@@ -5590,7 +5592,6 @@ int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)
      if (likely(!mas_is_err(mas)))
          return 0;
 
-    mas_set_alloc_req(mas, 0);

Why did you drop this? It seems like a worth while cleanup on failure.

Quoted 41 lines
Quoted 41 lines
Quoted 41 lines
Quoted 41 lines
lib/maple_tree.c +0 -0
      ret = xa_err(mas->node);
      mas_reset(mas);
      mas_destroy(mas);
Quoted 38 lines

Regards
Yin, Fengwei

Quoted 31 lines

[1] https://lore.kernel.org/linux-mm/[email protected]/

Liam R. Howlett (14):
   maple_tree: Add benchmarking for mas_for_each
   maple_tree: Add benchmarking for mas_prev()
   mm: Move unmap_vmas() declaration to internal header
   mm: Change do_vmi_align_munmap() side tree index
   mm: Remove prev check from do_vmi_align_munmap()
   maple_tree: Introduce __mas_set_range()
   mm: Remove re-walk from mmap_region()
   maple_tree: Re-introduce entry to mas_preallocate() arguments
   mm: Use vma_iter_clear_gfp() in nommu
   mm: Set up vma iterator for vma_iter_prealloc() calls
   maple_tree: Move mas_wr_end_piv() below mas_wr_extend_null()
   maple_tree: Update mas_preallocate() testing
   maple_tree: Refine mas_preallocate() node calculations mm/mmap: Change vma iteration order in do_vmi_align_munmap()

   fs/exec.c                        |   1 +
   include/linux/maple_tree.h       |  23 ++++-
   include/linux/mm.h               |   4 -
   lib/maple_tree.c                 |  78 ++++++++++----
   lib/test_maple_tree.c            |  74 +++++++++++++
   mm/internal.h                    |  40 ++++++--
   mm/memory.c                      |  16 ++-
   mm/mmap.c                        | 171 ++++++++++++++++---------------
   mm/nommu.c                       |  45 ++++----
   tools/testing/radix-tree/maple.c |  59 ++++++-----
   10 files changed, 331 insertions(+), 180 deletions(-)
#29 lore raw
In reply to Liam R. Howlett
Quoted 8 lines · Liam R. Howlett

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Most CONFIG_DEBUG_VM checks are quite cheap, mostly VM_BUG_ONs for easily checked conditions. If validate_mm() is still the kind of thing it used to be, checking through every vma on every mmap operation, please don't bring that into CONFIG_DEBUG_VM - it distorts performance too much, so always used to be under a separate CONFIG_DEBUG_VM_RB instead.

Hugh

#30 lore raw

Hi Huge,

Quoted 11 lines · Hugh Dickins
Quoted 8 lines · Liam R. Howlett

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Most CONFIG_DEBUG_VM checks are quite cheap, mostly VM_BUG_ONs for

Indeed. I had CONFIG_DEBUG_VM enabled and didn't see surprise perf report.

Quoted 4 lines

easily checked conditions. If validate_mm() is still the kind of thing it used to be, checking through every vma on every mmap operation, please don't bring that into CONFIG_DEBUG_VM - it distorts performance too much, so always used to be under a separate CONFIG_DEBUG_VM_RB instead.

So does this mean CONFIG_DEBUG_VM is allowed to be enabled for performance testing? Thanks.

Regards
Yin, Fengwei

Quoted 2 lines

Hugh

#31 lore raw
Quoted 15 lines · Fengwei
Quoted 11 lines · Hugh Dickins
Quoted 8 lines · Liam R. Howlett

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Most CONFIG_DEBUG_VM checks are quite cheap, mostly VM_BUG_ONs for

Indeed. I had CONFIG_DEBUG_VM enabled and didn't see surprise perf report.

Quoted 6 lines
Quoted 4 lines

easily checked conditions. If validate_mm() is still the kind of thing it used to be, checking through every vma on every mmap operation, please don't bring that into CONFIG_DEBUG_VM - it distorts performance too much, so always used to be under a separate CONFIG_DEBUG_VM_RB instead.

So does this mean CONFIG_DEBUG_VM is allowed to be enabled for performance testing? Thanks.

I was going to say:
No, I did not mean that: I just meant that even developers not doing strict performance testing still like to keep a rough eye on performance changes; and historically CONFIG_DEBUG_VM has not distorted very much.

But then I wonder about certain distros which (wrongly or rightly) turn CONFIG_DEBUG_VM on: I expect they do performance testing on their kernels.

Hugh

#32 lore raw
Quoted 23 lines · Hugh Dickins
Quoted 15 lines · Fengwei
Quoted 11 lines · Hugh Dickins
Quoted 8 lines · Liam R. Howlett

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Most CONFIG_DEBUG_VM checks are quite cheap, mostly VM_BUG_ONs for

Indeed. I had CONFIG_DEBUG_VM enabled and didn't see surprise perf report.

Quoted 6 lines
Quoted 4 lines

easily checked conditions. If validate_mm() is still the kind of thing it used to be, checking through every vma on every mmap operation, please don't bring that into CONFIG_DEBUG_VM - it distorts performance too much, so always used to be under a separate CONFIG_DEBUG_VM_RB instead.

So does this mean CONFIG_DEBUG_VM is allowed to be enabled for performance testing? Thanks.

Quoted 7 lines

I was going to say:
No, I did not mean that: I just meant that even developers not doing strict performance testing still like to keep a rough eye on performance changes; and historically CONFIG_DEBUG_VM has not distorted very much.

But then I wonder about certain distros which (wrongly or rightly) turn CONFIG_DEBUG_VM on: I expect they do performance testing on their kernels.

Fair enough. Thanks for explanation.

Regards
Yin, Fengwei

Quoted 2 lines

Hugh

#33 lore raw
Quoted 15 lines · Yin, Fengwei
Quoted 12 lines · Hugh Dickins
Quoted 11 lines · Fengwei
Quoted 10 lines · Hugh Dickins
Quoted 8 lines · Liam R. Howlett

You mean "mm: update validate_mm() to use vma iterator" here I guess. I have it as a different commit id in my branch.

I 'restored' some of the checking because I was able to work around not having the mt_dump() definition with the vma iterator. I'm now wondering how wide spread CONFIG_DEBUG_VM is used and if I should not have added these extra checks.

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 1 line

Most CONFIG_DEBUG_VM checks are quite cheap, mostly VM_BUG_ONs for

Indeed. I had CONFIG_DEBUG_VM enabled and didn't see surprise perf report.

Quoted 4 lines

easily checked conditions. If validate_mm() is still the kind of thing it used to be, checking through every vma on every mmap operation, please don't bring that into CONFIG_DEBUG_VM - it distorts performance too much, so always used to be under a separate CONFIG_DEBUG_VM_RB instead.

Okay, I will update my patch to use CONFIG_DEBUG_VM_MAPLE_TREE for validate_mm().

Quoted 12 lines
Quoted 10 lines
Quoted 2 lines

So does this mean CONFIG_DEBUG_VM is allowed to be enabled for performance testing? Thanks.

I was going to say:
No, I did not mean that: I just meant that even developers not doing strict performance testing still like to keep a rough eye on performance changes; and historically CONFIG_DEBUG_VM has not distorted very much.

But then I wonder about certain distros which (wrongly or rightly) turn CONFIG_DEBUG_VM on: I expect they do performance testing on their kernels.

Fair enough. Thanks for explanation.

Thanks for looking at this everyone.

Regards,
Liam