Skip to contentSkip to conversation

Introducing the Maple Tree

PATCH In review Liam Howlett 14 participants 114 messages Apr 26, 2022 – Jun 30, 2022 Page 2 of 2

Subsystems (49)
lore
Share & tools
lore
#80 lore raw

PATCH v8 54/70 mm/ksm: use vma iterators instead of vma linked list

In reply to Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

Remove the use of the linked list for eventual removal.

---
 mm/ksm.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
mm/ksm.c +11 -7
index 8d5369425c62..fcdceb28d072 100644
@@ -975,11 +975,13 @@ static int unmerge_and_remove_all_rmap_items(void)
 						struct mm_slot, mm_list);
 	spin_unlock(&ksm_mmlist_lock);
 
-	for (mm_slot = ksm_scan.mm_slot;
-			mm_slot != &ksm_mm_head; mm_slot = ksm_scan.mm_slot) {
+	for (mm_slot = ksm_scan.mm_slot; mm_slot != &ksm_mm_head;
+	     mm_slot = ksm_scan.mm_slot) {
+		VMA_ITERATOR(vmi, mm_slot->mm, 0);
+
 		mm = mm_slot->mm;
 		mmap_read_lock(mm);
-		for (vma = mm->mmap; vma; vma = vma->vm_next) {
+		for_each_vma(vmi, vma) {
 			if (ksm_test_exit(mm))
 				break;
 			if (!(vma->vm_flags & VM_MERGEABLE) || !vma->anon_vma)
@@ -2224,6 +2226,7 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	struct mm_slot *slot;
 	struct vm_area_struct *vma;
 	struct rmap_item *rmap_item;
+	struct vma_iterator vmi;
 	int nid;
 
 	if (list_empty(&ksm_mm_head.mm_list))
@@ -2282,13 +2285,13 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	}
 
 	mm = slot->mm;
+	vma_iter_init(&vmi, mm, ksm_scan.address);
+
 	mmap_read_lock(mm);
 	if (ksm_test_exit(mm))
-		vma = NULL;
-	else
-		vma = find_vma(mm, ksm_scan.address);
+		goto no_vmas;
 
-	for (; vma; vma = vma->vm_next) {
+	for_each_vma(vmi, vma) {
 		if (!(vma->vm_flags & VM_MERGEABLE))
 			continue;
 		if (ksm_scan.address < vma->vm_start)
@@ -2326,6 +2329,7 @@ static struct rmap_item *scan_get_next_rmap_item(struct page **page)
 	}
 
 	if (ksm_test_exit(mm)) {
+no_vmas:
 		ksm_scan.address = 0;
 		ksm_scan.rmap_list = &slot->rmap_list;
 	}
Signature · 1 line
2.35.1
#81 lore raw

PATCH v8 55/70 mm/madvise: use vma_find() instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

madvise_walk_vmas() no longer uses linked list.

---
 mm/madvise.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/madvise.c +1 -1
index ec03a76244b7..1c943a7ddcb2 100644
@@ -1232,7 +1232,7 @@ int madvise_walk_vmas(struct mm_struct *mm, unsigned long start,
 		if (start >= end)
 			break;
 		if (prev)
-			vma = prev->vm_next;
+			vma = find_vma(mm, prev->vm_end);
 		else	/* madvise_remove dropped mmap_lock */
 			vma = find_vma(mm, start);
 	}
Signature · 1 line
2.35.1
#82 lore raw

PATCH v8 56/70 mm/memcontrol: stop using mm->highest_vm_end

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Pass through ULONG_MAX instead.

---
 mm/memcontrol.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
mm/memcontrol.c +2 -4
index 7924c77d213f..27567b047f2d 100644
@@ -5760,7 +5760,7 @@ static unsigned long mem_cgroup_count_precharge(struct mm_struct *mm)
 	unsigned long precharge;
 
 	mmap_read_lock(mm);
-	walk_page_range(mm, 0, mm->highest_vm_end, &precharge_walk_ops, NULL);
+	walk_page_range(mm, 0, ULONG_MAX, &precharge_walk_ops, NULL);
 	mmap_read_unlock(mm);
 
 	precharge = mc.precharge;
@@ -6058,9 +6058,7 @@ static void mem_cgroup_move_charge(void)
 	 * When we have consumed all precharges and failed in doing
 	 * additional charge, the page walk just aborts.
 	 */
-	walk_page_range(mc.mm, 0, mc.mm->highest_vm_end, &charge_walk_ops,
-			NULL);
-
+	walk_page_range(mc.mm, 0, ULONG_MAX, &charge_walk_ops, NULL);
 	mmap_read_unlock(mc.mm);
 	atomic_dec(&mc.from->moving_account);
 }
Signature · 1 line
2.35.1
#83 lore raw

PATCH v8 57/70 mm/mempolicy: use vma iterator & maple state instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Reworked the way mbind_range() finds the first VMA to reuse the maple state and limit the number of tree walks needed.

Note, this drops the VM_BUG_ON(!vma) call, which would catch a start address higher than the last VMA. The code was written in a way that allowed no VMA updates to occur and still return success. There should be no functional change to this scenario with the new code.

---
 mm/mempolicy.c | 56 ++++++++++++++++++++++++++++----------------------
 1 file changed, 32 insertions(+), 24 deletions(-)
mm/mempolicy.c +32 -24
index 75a8b247f631..78d706196d4a 100644
@@ -381,9 +381,10 @@ void mpol_rebind_task(struct task_struct *tsk, const nodemask_t *new)
 void mpol_rebind_mm(struct mm_struct *mm, nodemask_t *new)
 {
 	struct vm_area_struct *vma;
+	VMA_ITERATOR(vmi, mm, 0);
 
 	mmap_write_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next)
+	for_each_vma(vmi, vma)
 		mpol_rebind_policy(vma->vm_policy, new);
 	mmap_write_unlock(mm);
 }
@@ -662,7 +663,7 @@ static unsigned long change_prot_numa(struct vm_area_struct *vma,
 static int queue_pages_test_walk(unsigned long start, unsigned long end,
 				struct mm_walk *walk)
 {
-	struct vm_area_struct *vma = walk->vma;
+	struct vm_area_struct *next, *vma = walk->vma;
 	struct queue_pages *qp = walk->private;
 	unsigned long endvma = vma->vm_end;
 	unsigned long flags = qp->flags;
@@ -677,9 +678,10 @@ static int queue_pages_test_walk(unsigned long start, unsigned long end,
 			/* hole at head side of range */
 			return -EFAULT;
 	}
+	next = find_vma(vma->vm_mm, vma->vm_end);
 	if (!(flags & MPOL_MF_DISCONTIG_OK) &&
 		((vma->vm_end < qp->end) &&
-		(!vma->vm_next || vma->vm_end < vma->vm_next->vm_start)))
+		(!next || vma->vm_end < next->vm_start)))
 		/* hole at middle or tail of range */
 		return -EFAULT;
 
@@ -793,26 +795,24 @@ static int vma_replace_policy(struct vm_area_struct *vma,
 static int mbind_range(struct mm_struct *mm, unsigned long start,
 		       unsigned long end, struct mempolicy *new_pol)
 {
+	MA_STATE(mas, &mm->mm_mt, start - 1, start - 1);
 	struct vm_area_struct *prev;
 	struct vm_area_struct *vma;
 	int err = 0;
 	pgoff_t pgoff;
-	unsigned long vmstart;
-	unsigned long vmend;
-
-	vma = find_vma(mm, start);
-	VM_BUG_ON(!vma);
 
-	prev = vma->vm_prev;
-	if (start > vma->vm_start)
-		prev = vma;
+	prev = mas_find_rev(&mas, 0);
+	if (prev && (start < prev->vm_end))
+		vma = prev;
+	else
+		vma = mas_next(&mas, end - 1);
 
-	for (; vma && vma->vm_start < end; prev = vma, vma = vma->vm_next) {
-		vmstart = max(start, vma->vm_start);
-		vmend   = min(end, vma->vm_end);
+	for (; vma; vma = mas_next(&mas, end - 1)) {
+		unsigned long vmstart = max(start, vma->vm_start);
+		unsigned long vmend = min(end, vma->vm_end);
 
 		if (mpol_equal(vma_policy(vma), new_pol))
-			continue;
+			goto next;
 
 		pgoff = vma->vm_pgoff +
 			((vmstart - vma->vm_start) >> PAGE_SHIFT);
@@ -821,6 +821,8 @@ static int mbind_range(struct mm_struct *mm, unsigned long start,
 				 new_pol, vma->vm_userfaultfd_ctx,
 				 anon_vma_name(vma));
 		if (prev) {
+			/* vma_merge() invalidated the mas */
+			mas_pause(&mas);
 			vma = prev;
 			goto replace;
 		}
@@ -828,19 +830,25 @@ static int mbind_range(struct mm_struct *mm, unsigned long start,
 			err = split_vma(vma->vm_mm, vma, vmstart, 1);
 			if (err)
 				goto out;
+			/* split_vma() invalidated the mas */
+			mas_pause(&mas);
 		}
 		if (vma->vm_end != vmend) {
 			err = split_vma(vma->vm_mm, vma, vmend, 0);
 			if (err)
 				goto out;
+			/* split_vma() invalidated the mas */
+			mas_pause(&mas);
 		}
- replace:
+replace:
 		err = vma_replace_policy(vma, new_pol);
 		if (err)
 			goto out;
+next:
+		prev = vma;
 	}
 
- out:
+out:
 	return err;
 }
 
@@ -1055,6 +1063,7 @@ static int migrate_to_node(struct mm_struct *mm, int source, int dest,
 			   int flags)
 {
 	nodemask_t nmask;
+	struct vm_area_struct *vma;
 	LIST_HEAD(pagelist);
 	int err = 0;
 	struct migration_target_control mtc = {
@@ -1070,8 +1079,9 @@ static int migrate_to_node(struct mm_struct *mm, int source, int dest,
 	 * need migration.  Between passing in the full user address
 	 * space range and MPOL_MF_DISCONTIG_OK, this call can not fail.
 	 */
+	vma = find_vma(mm, 0);
 	VM_BUG_ON(!(flags & (MPOL_MF_MOVE | MPOL_MF_MOVE_ALL)));
-	queue_pages_range(mm, mm->mmap->vm_start, mm->task_size, &nmask,
+	queue_pages_range(mm, vma->vm_start, mm->task_size, &nmask,
 			flags | MPOL_MF_DISCONTIG_OK, &pagelist);
 
 	if (!list_empty(&pagelist)) {
@@ -1201,14 +1211,13 @@ static struct page *new_page(struct page *page, unsigned long start)
 	struct folio *dst, *src = page_folio(page);
 	struct vm_area_struct *vma;
 	unsigned long address;
+	VMA_ITERATOR(vmi, current->mm, start);
 	gfp_t gfp = GFP_HIGHUSER_MOVABLE | __GFP_RETRY_MAYFAIL;
 
-	vma = find_vma(current->mm, start);
-	while (vma) {
+	for_each_vma(vmi, vma) {
 		address = page_address_in_vma(page, vma);
 		if (address != -EFAULT)
 			break;
-		vma = vma->vm_next;
 	}
 
 	if (folio_test_hugetlb(src))
@@ -1486,6 +1495,7 @@ SYSCALL_DEFINE4(set_mempolicy_home_node, unsigned long, start, unsigned long, le
 	unsigned long vmend;
 	unsigned long end;
 	int err = -ENOENT;
+	VMA_ITERATOR(vmi, mm, start);
 
 	start = untagged_addr(start);
 	if (start & ~PAGE_MASK)
@@ -1511,9 +1521,7 @@ SYSCALL_DEFINE4(set_mempolicy_home_node, unsigned long, start, unsigned long, le
 	if (end == start)
 		return 0;
 	mmap_write_lock(mm);
-	vma = find_vma(mm, start);
-	for (; vma && vma->vm_start < end;  vma = vma->vm_next) {
-
+	for_each_vma_range(vmi, vma, end) {
 		vmstart = max(start, vma->vm_start);
 		vmend   = min(end, vma->vm_end);
 		new = mpol_dup(vma_policy(vma));
Signature · 1 line
2.35.1
#84 lore raw

PATCH v8 58/70 mm/mlock: use vma iterator and instead of vma linked list

In reply to Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

Handle overflow checking in count_mm_mlocked_page_nr() differently.

---
 mm/mlock.c | 34 ++++++++++++++++++----------------
 1 file changed, 18 insertions(+), 16 deletions(-)
mm/mlock.c +18 -16
index 716caf851043..d8549b3dcb59 100644
@@ -471,6 +471,7 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 	unsigned long nstart, end, tmp;
 	struct vm_area_struct *vma, *prev;
 	int error;
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
 	VM_BUG_ON(offset_in_page(start));
 	VM_BUG_ON(len != PAGE_ALIGN(len));
@@ -479,13 +480,14 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 		return -EINVAL;
 	if (end == start)
 		return 0;
-	vma = find_vma(current->mm, start);
-	if (!vma || vma->vm_start > start)
+	vma = mas_walk(&mas);
+	if (!vma)
 		return -ENOMEM;
 
-	prev = vma->vm_prev;
 	if (start > vma->vm_start)
 		prev = vma;
+	else
+		prev = mas_prev(&mas, 0);
 
 	for (nstart = start ; ; ) {
 		vm_flags_t newflags = vma->vm_flags & VM_LOCKED_CLEAR_MASK;
@@ -505,7 +507,7 @@ static int apply_vma_lock_flags(unsigned long start, size_t len,
 		if (nstart >= end)
 			break;
 
-		vma = prev->vm_next;
+		vma = find_vma(prev->vm_mm, prev->vm_end);
 		if (!vma || vma->vm_start != nstart) {
 			error = -ENOMEM;
 			break;
@@ -526,24 +528,23 @@ static unsigned long count_mm_mlocked_page_nr(struct mm_struct *mm,
 {
 	struct vm_area_struct *vma;
 	unsigned long count = 0;
+	unsigned long end;
+	VMA_ITERATOR(vmi, mm, start);
 
 	if (mm == NULL)
 		mm = current->mm;
 
-	vma = find_vma(mm, start);
-	if (vma == NULL)
-		return 0;
-
-	for (; vma ; vma = vma->vm_next) {
-		if (start >= vma->vm_end)
-			continue;
-		if (start + len <=  vma->vm_start)
-			break;
+	/* Don't overflow past ULONG_MAX */
+	if (unlikely(ULONG_MAX - len < start))
+		end = ULONG_MAX;
+	else
+		end = start + len;
+	for_each_vma_range(vmi, vma, end) {
 		if (vma->vm_flags & VM_LOCKED) {
 			if (start > vma->vm_start)
 				count -= (start - vma->vm_start);
-			if (start + len < vma->vm_end) {
-				count += start + len - vma->vm_start;
+			if (end < vma->vm_end) {
+				count += end - vma->vm_start;
 				break;
 			}
 			count += vma->vm_end - vma->vm_start;
@@ -659,6 +660,7 @@ SYSCALL_DEFINE2(munlock, unsigned long, start, size_t, len)
  */
 static int apply_mlockall_flags(int flags)
 {
+	VMA_ITERATOR(vmi, current->mm, 0);
 	struct vm_area_struct *vma, *prev = NULL;
 	vm_flags_t to_add = 0;
 
@@ -679,7 +681,7 @@ static int apply_mlockall_flags(int flags)
 			to_add |= VM_LOCKONFAULT;
 	}
 
-	for (vma = current->mm->mmap; vma ; vma = prev->vm_next) {
+	for_each_vma(vmi, vma) {
 		vm_flags_t newflags;
 
 		newflags = vma->vm_flags & VM_LOCKED_CLEAR_MASK;
Signature · 1 line
2.35.1
#85 lore raw

PATCH v8 59/70 mm/mprotect: use maple tree navigation instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/mprotect.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
mm/mprotect.c +4 -3
index 20a46f21cca8..fbb248caf8aa 100644
@@ -550,6 +550,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 	const bool rier = (current->personality & READ_IMPLIES_EXEC) &&
 				(prot & PROT_READ);
 	struct mmu_gather tlb;
+	MA_STATE(mas, &current->mm->mm_mt, start, start);
 
 	start = untagged_addr(start);
 
@@ -581,7 +582,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 	if ((pkey != -1) && !mm_pkey_is_allocated(current->mm, pkey))
 		goto out;
 
-	vma = find_vma(current->mm, start);
+	vma = mas_find(&mas, ULONG_MAX);
 	error = -ENOMEM;
 	if (!vma)
 		goto out;
@@ -607,7 +608,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 	if (start > vma->vm_start)
 		prev = vma;
 	else
-		prev = vma->vm_prev;
+		prev = mas_prev(&mas, 0);
 
 	tlb_gather_mmu(&tlb, current->mm);
 	for (nstart = start ; ; ) {
@@ -670,7 +671,7 @@ static int do_mprotect_pkey(unsigned long start, size_t len,
 		if (nstart >= end)
 			break;
 
-		vma = prev->vm_next;
+		vma = find_vma(current->mm, prev->vm_end);
 		if (!vma || vma->vm_start != nstart) {
 			error = -ENOMEM;
 			break;
Signature · 1 line
2.35.1
#86 lore raw

PATCH v8 60/70 mm/mremap: use vma_find_intersection() instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/mremap.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
mm/mremap.c +3 -2
index 4495f69eccbe..c0d32330d435 100644
@@ -716,7 +716,7 @@ static unsigned long move_vma(struct vm_area_struct *vma,
 	if (excess) {
 		vma->vm_flags |= VM_ACCOUNT;
 		if (split)
-			vma->vm_next->vm_flags |= VM_ACCOUNT;
+			find_vma(mm, vma->vm_end)->vm_flags |= VM_ACCOUNT;
 	}
 
 	return new_addr;
@@ -866,9 +866,10 @@ static unsigned long mremap_to(unsigned long addr, unsigned long old_len,
 static int vma_expandable(struct vm_area_struct *vma, unsigned long delta)
 {
 	unsigned long end = vma->vm_end + delta;
+
 	if (end < vma->vm_end) /* overflow */
 		return 0;
-	if (vma->vm_next && vma->vm_next->vm_start < end) /* intersection */
+	if (find_vma_intersection(vma->vm_mm, vma->vm_end, end))
 		return 0;
 	if (get_unmapped_area(NULL, vma->vm_start, end - vma->vm_start,
 			      0, MAP_FIXED) & ~PAGE_MASK)
Signature · 1 line
2.35.1
#87 lore raw

PATCH v8 61/70 mm/msync: use vma_find() instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/msync.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/msync.c +1 -1
index 137d1c104f3e..ac4c9bfea2e7 100644
@@ -104,7 +104,7 @@ SYSCALL_DEFINE3(msync, unsigned long, start, size_t, len, int, flags)
 				error = 0;
 				goto out_unlock;
 			}
-			vma = vma->vm_next;
+			vma = find_vma(mm, vma->vm_end);
 		}
 	}
 out_unlock:
Signature · 1 line
2.35.1
#88 lore raw

PATCH v8 62/70 mm/oom_kill: use maple tree iterators instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

---
 mm/oom_kill.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
mm/oom_kill.c +2 -1
index 7ec38194f8e1..cc25bd430b68 100644
@@ -513,6 +513,7 @@ bool __oom_reap_task_mm(struct mm_struct *mm)
 {
 	struct vm_area_struct *vma;
 	bool ret = true;
+	VMA_ITERATOR(vmi, mm, 0);
 
 	/*
 	 * Tell all users of get_user/copy_from_user etc... that the content
@@ -522,7 +523,7 @@ bool __oom_reap_task_mm(struct mm_struct *mm)
 	 */
 	set_bit(MMF_UNSTABLE, &mm->flags);
 
-	for (vma = mm->mmap ; vma; vma = vma->vm_next) {
+	for_each_vma(vmi, vma) {
 		if (vma->vm_flags & (VM_HUGETLB|VM_PFNMAP))
 			continue;
 
Signature · 1 line
2.35.1
#89 lore raw

PATCH v8 63/70 mm/pagewalk: use vma_find() instead of vma linked list

In reply to Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

walk_page_range() no longer uses the one vma linked list reference.

---
 mm/pagewalk.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
mm/pagewalk.c +1 -1
index 9b3db11a4d1d..53e5c145fcce 100644
@@ -456,7 +456,7 @@ int walk_page_range(struct mm_struct *mm, unsigned long start,
 		} else { /* inside vma */
 			walk.vma = vma;
 			next = min(end, vma->vm_end);
-			vma = vma->vm_next;
+			vma = find_vma(mm, vma->vm_end);
 
 			err = walk_page_test(start, next, &walk);
 			if (err > 0) {
Signature · 1 line
2.35.1
#90 lore raw

PATCH v8 64/70 mm/swapfile: use vma iterator instead of vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

unuse_mm() no longer needs to reference the linked list.

---
 mm/swapfile.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)
mm/swapfile.c +3 -1
index 9398e915b36b..3007031c0f5f 100644
@@ -1984,14 +1984,16 @@ static int unuse_mm(struct mm_struct *mm, unsigned int type)
 {
 	struct vm_area_struct *vma;
 	int ret = 0;
+	VMA_ITERATOR(vmi, mm, 0);
 
 	mmap_read_lock(mm);
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	for_each_vma(vmi, vma) {
 		if (vma->anon_vma) {
 			ret = unuse_vma(vma, type);
 			if (ret)
 				break;
 		}
+
 		cond_resched();
 	}
 	mmap_read_unlock(mm);
Signature · 1 line
2.35.1
#91 lore raw

PATCH v8 65/70 i915: use the VMA iterator

In reply to Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

Replace the linked list in probe_range() with the VMA iterator.

---
 drivers/gpu/drm/i915/gem/i915_gem_userptr.c | 14 +++++---------
 1 file changed, 5 insertions(+), 9 deletions(-)
drivers/gpu/drm/i915/gem/i915_gem_userptr.c +5 -9
index 6d1a71d6404c..e20ee4b611fd 100644
@@ -426,12 +426,11 @@ static const struct drm_i915_gem_object_ops i915_gem_userptr_ops = {
 static int
 probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len)
 {
-	const unsigned long end = addr + len;
+	VMA_ITERATOR(vmi, mm, addr);
 	struct vm_area_struct *vma;
-	int ret = -EFAULT;
 
 	mmap_read_lock(mm);
-	for (vma = find_vma(mm, addr); vma; vma = vma->vm_next) {
+	for_each_vma_range(vmi, vma, addr + len) {
 		/* Check for holes, note that we also update the addr below */
 		if (vma->vm_start > addr)
 			break;
@@ -439,16 +438,13 @@ probe_range(struct mm_struct *mm, unsigned long addr, unsigned long len)
 		if (vma->vm_flags & (VM_PFNMAP | VM_MIXEDMAP))
 			break;
 
-		if (vma->vm_end >= end) {
-			ret = 0;
-			break;
-		}
-
 		addr = vma->vm_end;
 	}
 	mmap_read_unlock(mm);
 
-	return ret;
+	if (vma)
+		return -EFAULT;
+	return 0;
 }
 
 /*
Signature · 1 line
2.35.1
#92 lore raw

PATCH v8 66/70 nommu: remove uses of VMA linked list

In reply to Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

Use the maple tree or VMA iterator instead. This is faster and will allow us to shrink the VMA.

---
 mm/nommu.c | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)
mm/nommu.c +11 -4
index 26a9056e508f..645d11d3a8ab 100644
@@ -1381,6 +1381,7 @@ static int shrink_vma(struct mm_struct *mm,
  */
 int do_munmap(struct mm_struct *mm, unsigned long start, size_t len, struct list_head *uf)
 {
+	MA_STATE(mas, &mm->mm_mt, start, start);
 	struct vm_area_struct *vma;
 	unsigned long end;
 	int ret;
@@ -1392,7 +1393,7 @@ int do_munmap(struct mm_struct *mm, unsigned long start, size_t len, struct list
 	end = start + len;
 
 	/* find the first potentially overlapping VMA */
-	vma = find_vma(mm, start);
+	vma = mas_find(&mas, end - 1);
 	if (!vma) {
 		static int limit;
 		if (limit < 5) {
@@ -1411,7 +1412,7 @@ int do_munmap(struct mm_struct *mm, unsigned long start, size_t len, struct list
 				return -EINVAL;
 			if (end == vma->vm_end)
 				goto erase_whole_vma;
-			vma = vma->vm_next;
+			vma = mas_next(&mas, end - 1);
 		} while (vma);
 		return -EINVAL;
 	} else {
@@ -1460,6 +1461,7 @@ SYSCALL_DEFINE2(munmap, unsigned long, addr, size_t, len)
  */
 void exit_mmap(struct mm_struct *mm)
 {
+	VMA_ITERATOR(vmi, mm, 0);
 	struct vm_area_struct *vma;
 
 	if (!mm)
@@ -1467,12 +1469,17 @@ void exit_mmap(struct mm_struct *mm)
 
 	mm->total_vm = 0;
 
-	while ((vma = mm->mmap)) {
-		mm->mmap = vma->vm_next;
+	/*
+	 * Lock the mm to avoid assert complaining even though this is the only
+	 * user of the mm
+	 */
+	mmap_write_lock(mm);
+	for_each_vma(vmi, vma) {
 		delete_vma_from_mm(vma);
 		delete_vma(mm, vma);
 		cond_resched();
 	}
+	mmap_write_unlock(mm);
 	__mt_destroy(&mm->mm_mt);
 }
 
Signature · 1 line
2.35.1
#93 lore raw

Re: [PATCH v8 66/70] nommu: remove uses of VMA linked list

Quoted 8 lines · Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

Use the maple tree or VMA iterator instead. This is faster and will allow us to shrink the VMA.

This patch crashes my xtensa nommu (kc705-nommu) boot test. Crash and bisect logs attached. I can not revert the patch for cross checks because that results in a compile failure.

Note that mps2-an385 boot tests also fail but I was not able to bisect.

Guenter

---

[   19.394659] Unable to handle kernel paging request at virtual address 00000048
[   19.394659]  pc = 600d7039, ra = a00d7ed4
[   19.394840] Oops: sig: 11 [#1] PREEMPT
[   19.394930] CPU: 0 PID: 142 Comm: mount Not tainted 5.18.0-rc4-next-20220428 #1
[   19.394980] a00: a00d7ed4 6253be00 6b6b6b6b ffffffff 00000001 6254ada0 00000000 6253be20
[   19.395091] a08: a03b91a8 00000000 6b6b6b6b ffffff00 6b6b6b6b 6235c400 6253be40 6b6b6b6b
[   19.395198] pc: 600d7039, ps: 00060710, depc: 0000001c, excvaddr: 00000048
[   19.395225] lbeg: 6056536c, lend: 60565377 lcount: ffffffff, sar: 00000009
[   19.395275] Stack:
[   19.395320]  6b6b6b6b 6235c400 0000001f 6b6b6b6b a0009585 6253be40 6234e020 6235a2e0
[   19.395349]  00000000 6254ada0 00000000 6253be20 a000e789 6253be80 6234e020 60731424
[   19.395375]  6234e020 6b6b6b6c 6b6b6b6b 6235c40c 00000000 ffffffff 00000000 00000200
[   19.395401]  60748f3c 6234e090 00000001 6253be50 a000eee0 6253bea0 6234e020 6254a8a0
[   19.395426]  00000000 6234e020 6254a8a0 00000000 60005e8c 6253bf00 00000000 6270d6d4
[   19.395452]  60005e8c 6253bef0 00000000 00000000 6254aca0 00000000 fffff000 00000000
[   19.395478]  6254b3a0 619a0780 627aff95 627aff9a 60005c19 6253bf00 6253bf00 3fffffff
[   19.395503]  6234e090 00000000 00000000 00000000 60005ba9 6253bf20 6253bf30 00000000
[   19.395519] Call Trace:
[   19.395577] Disabling lock debugging due to kernel taint
[   19.395714] Fixing recursive fault but reboot is needed!
[   19.395826] BUG: scheduling while atomic: mount/142/0x00000000
[   19.395871] INFO: lockdep is turned off.
[   19.395904] Modules linked in:
[   19.396000] Preemption disabled at:
[   19.396019] [<00000000>] 0x0
[   19.396256] CPU: 0 PID: 142 Comm: mount Tainted: G      D           5.18.0-rc4-next-20220428 #1
[   19.396284] Stack:
[   19.396311]  00000100 00000000 6253bbf0 6253bbd0 6074b97c 0000008e 6095915c a057531a
[   19.396339]  a00287ab 6253bc10 00000010 60734364 00000000 00000004 6253bbf0 6253bbd0
[   19.396365]  a0578975 6253bc30 00000000 00000000 00000000 00000000 60730cbc 6253bda4
[   19.396392]  a002b770 6253bc50 00000000 6254a8a0 40000000 00000000 00000000 6253bc30
[   19.396418]  a000eece 6253bca0 0000810c 00008000 00000000 00000000 00000001 60915040
[   19.396444]  00000000 60915020 6253a000 60915040 a000eece 6253bca0 00000000 0000050c
[   19.396471]  608011c0 608015c0 6253a000 6253bc50 a0007f39 6253bcc0 00000003 00000001
[   19.396497]  0000008e 00060003 00000000 6253bca0 a0008675 6253bce0 00000000 0000ff00
[   19.396509] Call Trace:
[   19.396520]  [<6057535d>] dump_stack+0x9/0x18
[   19.396556]  [<600287ab>] __schedule_bug+0x7f/0xc0
[   19.396584]  [<60578975>] __schedule+0x59/0x764
[   19.396609]  [<6002b770>] do_task_dead+0x4c/0x74
[   19.396633]  [<6000eece>] make_task_dead+0xaa/0xb0
[   19.396657]  [<60007f39>] die+0x9d/0xb4
[   19.396681]  [<60008675>] bad_page_fault+0x61/0xc4
[   19.396705]  [<60008875>] do_page_fault+0x19d/0x1ec
[   19.396729]  [<60005ba9>] common_exception+0x7f/0x7f
[   19.396752]  [<600d7ed4>] exit_mmap+0x44/0xa8
[   19.396778]  [<60009585>] mmput+0x55/0xec
[   19.396802]  [<6000e789>] do_exit+0x279/0x914
[   19.396825]  [<6000eee0>] sys_exit+0xc/0xc
[   19.396849]  [<60005e8c>] system_call+0x48/0x60
[   19.396872]  [<60005ba9>] common_exception+0x7f/0x7f

---
# bad: [bdc61aad77faf67187525028f1f355eff3849f22] Add linux-next specific files for 20220428
# good: [af2d861d4cd2a4da5137f795ee3509e6f944a25b] Linux 5.18-rc4
git bisect start 'HEAD' 'v5.18-rc4'
# good: [a6ffa4aa7e81a54632f3370f4c93fce603160192] Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git
git bisect good a6ffa4aa7e81a54632f3370f4c93fce603160192
# good: [cd63f17e3bb63006f9f88bf7f5947b8e1601bcd9] Merge branch 'edac-for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/ras/ras.git
git bisect good cd63f17e3bb63006f9f88bf7f5947b8e1601bcd9
# good: [cee7bbed3e5cc089b5c364ac8ad4a186c2a28bb6] Merge branch 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/vkoul/dmaengine.git
git bisect good cee7bbed3e5cc089b5c364ac8ad4a186c2a28bb6
# good: [d5a23156ea99f10b584221893a6a7d6f6554cde8] Merge branch 'for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/vbabka/slab.git
git bisect good d5a23156ea99f10b584221893a6a7d6f6554cde8
# good: [2f1fde90d983bc404503100c9c4bbbf1e191bcf4] selftests: cgroup: fix alloc_anon_noexit() instantly freeing memory
git bisect good 2f1fde90d983bc404503100c9c4bbbf1e191bcf4
# good: [fca1db6ff251278c532231552e840c7dc36dfa76] Merge branch 'bitmap-for-next' of https://github.com/norov/linux.git
git bisect good fca1db6ff251278c532231552e840c7dc36dfa76
# good: [40b39116fe8e6fb66e3166ea40138eec506dfd91] perf: use VMA iterator
git bisect good 40b39116fe8e6fb66e3166ea40138eec506dfd91
# bad: [33ef257872566922df2b6bcfdb5330b2388aef53] Docs/{ABI,admin-guide}/damon: update for fixed virtual address ranges monitoring git bisect bad 33ef257872566922df2b6bcfdb5330b2388aef53
# good: [2d8640f244c1ea6c40acde911d339dabc2ac765d] mm/oom_kill: use maple tree iterators instead of vma linked list
git bisect good 2d8640f244c1ea6c40acde911d339dabc2ac765d
# bad: [49d281fa016f2906346f1707e5059b6f7674a948] mm/mmap.c: pass in mapping to __vma_link_file()
git bisect bad 49d281fa016f2906346f1707e5059b6f7674a948
# bad: [487c2c6d922605aebe6f470e1a458eb1425548db] nommu: remove uses of VMA linked list
git bisect bad 487c2c6d922605aebe6f470e1a458eb1425548db
# good: [dc4a1ab575a32e454be953f7b1b0222dcd3d47fa] mm/swapfile: use vma iterator instead of vma linked list
git bisect good dc4a1ab575a32e454be953f7b1b0222dcd3d47fa
# good: [7fffbdd08665ddeeb38768309269fa5b32388c3d] i915: use the VMA iterator
git bisect good 7fffbdd08665ddeeb38768309269fa5b32388c3d

# first bad commit: [487c2c6d922605aebe6f470e1a458eb1425548db] nommu: remove uses of VMA linked list
#94 lore raw

Re: [PATCH v8 66/70] nommu: remove uses of VMA linked list

In reply to Liam Howlett
Quoted 8 lines · Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

Use the maple tree or VMA iterator instead. This is faster and will allow us to shrink the VMA.

This patch also results in boot failures for m68k:mcf5208evb qemu emulations. Backtrace and bisect log attached.

Guenter

---
# bad: [bdc61aad77faf67187525028f1f355eff3849f22] Add linux-next specific files for 20220428
# good: [af2d861d4cd2a4da5137f795ee3509e6f944a25b] Linux 5.18-rc4
git bisect start 'HEAD' 'v5.18-rc4'
# good: [a6ffa4aa7e81a54632f3370f4c93fce603160192] Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git
git bisect good a6ffa4aa7e81a54632f3370f4c93fce603160192
# good: [cd63f17e3bb63006f9f88bf7f5947b8e1601bcd9] Merge branch 'edac-for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/ras/ras.git
git bisect good cd63f17e3bb63006f9f88bf7f5947b8e1601bcd9
# good: [cee7bbed3e5cc089b5c364ac8ad4a186c2a28bb6] Merge branch 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/vkoul/dmaengine.git
git bisect good cee7bbed3e5cc089b5c364ac8ad4a186c2a28bb6
# good: [d5a23156ea99f10b584221893a6a7d6f6554cde8] Merge branch 'for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/vbabka/slab.git
git bisect good d5a23156ea99f10b584221893a6a7d6f6554cde8
# good: [2f1fde90d983bc404503100c9c4bbbf1e191bcf4] selftests: cgroup: fix alloc_anon_noexit() instantly freeing memory
git bisect good 2f1fde90d983bc404503100c9c4bbbf1e191bcf4
# good: [fca1db6ff251278c532231552e840c7dc36dfa76] Merge branch 'bitmap-for-next' of https://github.com/norov/linux.git
git bisect good fca1db6ff251278c532231552e840c7dc36dfa76
# good: [40b39116fe8e6fb66e3166ea40138eec506dfd91] perf: use VMA iterator
git bisect good 40b39116fe8e6fb66e3166ea40138eec506dfd91
# bad: [33ef257872566922df2b6bcfdb5330b2388aef53] Docs/{ABI,admin-guide}/damon: update for fixed virtual address ranges monitoring git bisect bad 33ef257872566922df2b6bcfdb5330b2388aef53
# good: [2d8640f244c1ea6c40acde911d339dabc2ac765d] mm/oom_kill: use maple tree iterators instead of vma linked list
git bisect good 2d8640f244c1ea6c40acde911d339dabc2ac765d
# bad: [49d281fa016f2906346f1707e5059b6f7674a948] mm/mmap.c: pass in mapping to __vma_link_file()
git bisect bad 49d281fa016f2906346f1707e5059b6f7674a948
# bad: [487c2c6d922605aebe6f470e1a458eb1425548db] nommu: remove uses of VMA linked list
git bisect bad 487c2c6d922605aebe6f470e1a458eb1425548db
# good: [dc4a1ab575a32e454be953f7b1b0222dcd3d47fa] mm/swapfile: use vma iterator instead of vma linked list
git bisect good dc4a1ab575a32e454be953f7b1b0222dcd3d47fa
# good: [7fffbdd08665ddeeb38768309269fa5b32388c3d] i915: use the VMA iterator
git bisect good 7fffbdd08665ddeeb38768309269fa5b32388c3d

# first bad commit: [487c2c6d922605aebe6f470e1a458eb1425548db] nommu: remove uses of VMA linked list

---

...
page allocation failure: order:7, mode:0xcc0(GFP_KERNEL), nodemask=(null)

CPU: 0 PID: 62 Comm: echo Not tainted 5.18.0-rc4-next-20220428 #1
Stack from 405d9d14:
        405d9d14 40335f43 40335f43 00000000 00000000 402da566 40335f43 400926f6
        00000cc0 00000000 00000000 00000000 405d8000 40906ee0 405d9d6c 40335402
        405d9d4c 405d9df8 40093158 00000cc0 00000000 40335402 00000007 00000007
        000d8000 00000cc0 00000001 00000077 0000006c 00000000 40906ee0 409049a0
        00000000 00000000 00000001 00000000 00000400 41cdad88 00000000 001008c0
        00000000 409830d2 405d4037 283a0000 00004037 283a0000 00000000 00010000
Call Trace: [<402da566>] dump_stack+0xc/0x10
 [<400926f6>] warn_alloc+0xd0/0x1ce
 [<40093158>] __alloc_pages+0x8c6/0xb7e
 [<40046f82>] check_preempt_wakeup+0xce/0x178
 [<400965da>] kmem_cache_alloc+0x22/0x17e
 [<40093ca2>] alloc_pages_exact+0x86/0x14e
 [<4008ddca>] do_mmap+0x3d8/0xa8a
 [<40085ece>] vm_mmap_pgoff+0x5c/0x84
 [<400a486c>] begin_new_exec+0x45e/0x852
 [<400f1ea0>] load_flat_binary+0x5e8/0x878
 [<4009bf94>] kernel_read+0x0/0x98
 [<402d4308>] memset+0x0/0x70
 [<4009e842>] fput+0x0/0x18
 [<400a3638>] bprm_execve+0x188/0x3bc
 [<400a3ab6>] copy_string_kernel+0x0/0x146
 [<400a30ca>] copy_strings+0x0/0x1b4
 [<400a3dce>] do_execveat_common+0x14c/0x220
 [<403768f4>] do_name+0x27a/0x296
 [<403765ec>] do_header+0x1c6/0x21c
 [<403768f4>] do_name+0x27a/0x296
 [<400a4c86>] sys_execve+0x26/0x30
 [<403768f4>] do_name+0x27a/0x296
 [<403765ec>] do_header+0x1c6/0x21c
 [<400a4c60>] sys_execve+0x0/0x30
 [<40022154>] system_call+0x48/0x94
 [<403768f4>] do_name+0x27a/0x296
 [<403765ec>] do_header+0x1c6/0x21c

Mem-Info:
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:152
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1071 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:216kB pagetables:0kB all_unreclaimable? no DMA free:8568kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 1*8kB (U) 1*16kB (U) 9*32kB (U) 7*64kB (U) 21*128kB (U) 8*256kB (U) 6*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 8568kB
613 total pagecache pages
4096 pages RAM
0 pages HighMem/MovableOnly
476 pages reserved
nommu: Allocation of length 884736 from process 62 (echo) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:152
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1071 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:216kB pagetables:0kB all_unreclaimable? no DMA free:8568kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 1*8kB (U) 1*16kB (U) 9*32kB (U) 7*64kB (U) 21*128kB (U) 8*256kB (U) 6*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 8568kB
613 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 63 (echo) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1409 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:176kB pagetables:0kB all_unreclaimable? no DMA free:11272kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 5*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11272kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 64 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1409 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:176kB pagetables:0kB all_unreclaimable? no DMA free:11272kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 5*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11272kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 65 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 66 (S20urandom) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 67 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 68 (S40network) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 69 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 70 (S55runtest) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12

#95 lore raw

Re: [PATCH v8 66/70] nommu: remove uses of VMA linked list

Quoted 6 lines · Guenter Roeck
Quoted 5 lines · Liam Howlett

From: "Matthew Wilcox (Oracle)" <[email protected]>

Use the maple tree or VMA iterator instead. This is faster and will allow us to shrink the VMA.

Quoted 6 lines
Quoted 3 lines

This patch also results in boot failures for m68k:mcf5208evb qemu emulations. Backtrace and bisect log attached.

Thanks, I have tried my branch and was able to get buildroot to boot and log in. At least maple tree worked on this platform at one point.

Quoted 216 lines

Guenter

---
# bad: [bdc61aad77faf67187525028f1f355eff3849f22] Add linux-next specific files for 20220428
# good: [af2d861d4cd2a4da5137f795ee3509e6f944a25b] Linux 5.18-rc4
git bisect start 'HEAD' 'v5.18-rc4'
# good: [a6ffa4aa7e81a54632f3370f4c93fce603160192] Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/herbert/cryptodev-2.6.git
git bisect good a6ffa4aa7e81a54632f3370f4c93fce603160192
# good: [cd63f17e3bb63006f9f88bf7f5947b8e1601bcd9] Merge branch 'edac-for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/ras/ras.git
git bisect good cd63f17e3bb63006f9f88bf7f5947b8e1601bcd9
# good: [cee7bbed3e5cc089b5c364ac8ad4a186c2a28bb6] Merge branch 'next' of git://git.kernel.org/pub/scm/linux/kernel/git/vkoul/dmaengine.git
git bisect good cee7bbed3e5cc089b5c364ac8ad4a186c2a28bb6
# good: [d5a23156ea99f10b584221893a6a7d6f6554cde8] Merge branch 'for-next' of git://git.kernel.org/pub/scm/linux/kernel/git/vbabka/slab.git
git bisect good d5a23156ea99f10b584221893a6a7d6f6554cde8
# good: [2f1fde90d983bc404503100c9c4bbbf1e191bcf4] selftests: cgroup: fix alloc_anon_noexit() instantly freeing memory
git bisect good 2f1fde90d983bc404503100c9c4bbbf1e191bcf4
# good: [fca1db6ff251278c532231552e840c7dc36dfa76] Merge branch 'bitmap-for-next' of https://github.com/norov/linux.git
git bisect good fca1db6ff251278c532231552e840c7dc36dfa76
# good: [40b39116fe8e6fb66e3166ea40138eec506dfd91] perf: use VMA iterator
git bisect good 40b39116fe8e6fb66e3166ea40138eec506dfd91
# bad: [33ef257872566922df2b6bcfdb5330b2388aef53] Docs/{ABI,admin-guide}/damon: update for fixed virtual address ranges monitoring git bisect bad 33ef257872566922df2b6bcfdb5330b2388aef53
# good: [2d8640f244c1ea6c40acde911d339dabc2ac765d] mm/oom_kill: use maple tree iterators instead of vma linked list
git bisect good 2d8640f244c1ea6c40acde911d339dabc2ac765d
# bad: [49d281fa016f2906346f1707e5059b6f7674a948] mm/mmap.c: pass in mapping to __vma_link_file()
git bisect bad 49d281fa016f2906346f1707e5059b6f7674a948
# bad: [487c2c6d922605aebe6f470e1a458eb1425548db] nommu: remove uses of VMA linked list
git bisect bad 487c2c6d922605aebe6f470e1a458eb1425548db
# good: [dc4a1ab575a32e454be953f7b1b0222dcd3d47fa] mm/swapfile: use vma iterator instead of vma linked list
git bisect good dc4a1ab575a32e454be953f7b1b0222dcd3d47fa
# good: [7fffbdd08665ddeeb38768309269fa5b32388c3d] i915: use the VMA iterator
git bisect good 7fffbdd08665ddeeb38768309269fa5b32388c3d

# first bad commit: [487c2c6d922605aebe6f470e1a458eb1425548db] nommu: remove uses of VMA linked list

---

...
page allocation failure: order:7, mode:0xcc0(GFP_KERNEL), nodemask=(null)

CPU: 0 PID: 62 Comm: echo Not tainted 5.18.0-rc4-next-20220428 #1
Stack from 405d9d14:
        405d9d14 40335f43 40335f43 00000000 00000000 402da566 40335f43 400926f6
        00000cc0 00000000 00000000 00000000 405d8000 40906ee0 405d9d6c 40335402
        405d9d4c 405d9df8 40093158 00000cc0 00000000 40335402 00000007 00000007
        000d8000 00000cc0 00000001 00000077 0000006c 00000000 40906ee0 409049a0
        00000000 00000000 00000001 00000000 00000400 41cdad88 00000000 001008c0
        00000000 409830d2 405d4037 283a0000 00004037 283a0000 00000000 00010000
Call Trace: [<402da566>] dump_stack+0xc/0x10
 [<400926f6>] warn_alloc+0xd0/0x1ce
 [<40093158>] __alloc_pages+0x8c6/0xb7e
 [<40046f82>] check_preempt_wakeup+0xce/0x178
 [<400965da>] kmem_cache_alloc+0x22/0x17e
 [<40093ca2>] alloc_pages_exact+0x86/0x14e
 [<4008ddca>] do_mmap+0x3d8/0xa8a
 [<40085ece>] vm_mmap_pgoff+0x5c/0x84
 [<400a486c>] begin_new_exec+0x45e/0x852
 [<400f1ea0>] load_flat_binary+0x5e8/0x878
 [<4009bf94>] kernel_read+0x0/0x98
 [<402d4308>] memset+0x0/0x70
 [<4009e842>] fput+0x0/0x18
 [<400a3638>] bprm_execve+0x188/0x3bc
 [<400a3ab6>] copy_string_kernel+0x0/0x146
 [<400a30ca>] copy_strings+0x0/0x1b4
 [<400a3dce>] do_execveat_common+0x14c/0x220
 [<403768f4>] do_name+0x27a/0x296
 [<403765ec>] do_header+0x1c6/0x21c
 [<403768f4>] do_name+0x27a/0x296
 [<400a4c86>] sys_execve+0x26/0x30
 [<403768f4>] do_name+0x27a/0x296
 [<403765ec>] do_header+0x1c6/0x21c
 [<400a4c60>] sys_execve+0x0/0x30
 [<40022154>] system_call+0x48/0x94
 [<403768f4>] do_name+0x27a/0x296
 [<403765ec>] do_header+0x1c6/0x21c

Mem-Info:
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:152
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1071 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:216kB pagetables:0kB all_unreclaimable? no DMA free:8568kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 1*8kB (U) 1*16kB (U) 9*32kB (U) 7*64kB (U) 21*128kB (U) 8*256kB (U) 6*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 8568kB
613 total pagecache pages
4096 pages RAM
0 pages HighMem/MovableOnly
476 pages reserved
nommu: Allocation of length 884736 from process 62 (echo) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:152
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1071 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:216kB pagetables:0kB all_unreclaimable? no DMA free:8568kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 1*8kB (U) 1*16kB (U) 9*32kB (U) 7*64kB (U) 21*128kB (U) 8*256kB (U) 6*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 8568kB
613 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 63 (echo) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1409 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:176kB pagetables:0kB all_unreclaimable? no DMA free:11272kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 5*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11272kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 64 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1409 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:176kB pagetables:0kB all_unreclaimable? no DMA free:11272kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 5*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11272kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 65 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 66 (S20urandom) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 67 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 68 (S40network) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 69 ([) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12
nommu: Allocation of length 884736 from process 70 (S55runtest) failed
active_anon:0 inactive_anon:0 isolated_anon:0
active_file:0 inactive_file:0 isolated_file:0
unevictable:606 dirty:0 writeback:0
slab_reclaimable:62 slab_unreclaimable:153
mapped:0 shmem:0 pagetables:0 bounce:0
kernel_misc_reclaimable:0
free:1415 free_pcp:0 free_cma:0
Node 0 active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB isolated(anon):0kB isolated(file):0kB mapped:0kB dirty:0kB writeback:0kB shmem:0kB writeback_tmp:0kB kernel_stack:168kB pagetables:0kB all_unreclaimable? no DMA free:11320kB boost:0kB min:664kB low:824kB high:984kB reserved_highatomic:0KB active_anon:0kB inactive_anon:0kB active_file:0kB inactive_file:0kB unevictable:4848kB writepending:0kB present:32768kB managed:28960kB mlocked:0kB bounce:0kB free_pcp:0kB local_pcp:0kB free_cma:0kB lowmem_reserve[]: 0 0 0
DMA: 11*8kB (U) 6*16kB (U) 12*32kB (U) 10*64kB (U) 21*128kB (U) 11*256kB (U) 9*512kB (U) 0*1024kB 0*2048kB 0*4096kB 0*8192kB = 11320kB
614 total pagecache pages
binfmt_flat: Unable to allocate RAM for process text/data, errno -12

#96 lore raw

PATCH v8 67/70 riscv: use vma iterator for vdso

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Remove the linked list use in favour of the vma iterator.

---
 arch/riscv/kernel/vdso.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
arch/riscv/kernel/vdso.c +2 -1
index a9436a65161a..20e2ae135fb9 100644
@@ -116,10 +116,11 @@ int vdso_join_timens(struct task_struct *task, struct time_namespace *ns)
 {
 	struct mm_struct *mm = task->mm;
 	struct vm_area_struct *vma;
+	VMA_ITERATOR(vmi, mm, 0);
 
 	mmap_read_lock(mm);
 
-	for (vma = mm->mmap; vma; vma = vma->vm_next) {
+	for_each_vma(vmi, vma) {
 		unsigned long size = vma->vm_end - vma->vm_start;
 
 		if (vma_is_special_mapping(vma, vdso_info.dm))
Signature · 1 line
2.35.1
#97 lore raw

PATCH v8 68/70 mm: remove the vma linked list

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Replace any vm_next use with vma_find().

Update free_pgtables(), unmap_vmas(), and zap_page_range() to use the maple tree.

Use the new free_pgtables() and unmap_vmas() in do_mas_align_munmap(). At the same time, alter the loop to be more compact.

Now that free_pgtables() and unmap_vmas() take a maple tree as an argument, rearrange do_mas_align_munmap() to use the new tree to hold the vmas to remove.

Remove __vma_link_list() and __vma_unlink_list() as they are exclusively used to update the linked list

Drop linked list update from __insert_vm_struct().

Rework validation of tree as it was depending on the linked list.

---
 include/linux/mm.h       |   5 +-
 include/linux/mm_types.h |   4 -
 kernel/fork.c            |  15 +-
 mm/debug.c               |  14 +-
 mm/internal.h            |   8 +-
 mm/memory.c              |  33 ++-
 mm/mmap.c                | 433 ++++++++++++++++-----------------------
 mm/nommu.c               |   5 -
 mm/util.c                |  40 ----
 9 files changed, 218 insertions(+), 339 deletions(-)
include/linux/mm.h +3 -2
index 110587299681..3200c954c385 100644
@@ -1868,8 +1868,9 @@ void zap_vma_ptes(struct vm_area_struct *vma, unsigned long address,
 		  unsigned long size);
 void zap_page_range(struct vm_area_struct *vma, unsigned long address,
 		    unsigned long size);
-void unmap_vmas(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
-		unsigned long start, unsigned long end);
+void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
+		struct vm_area_struct *start_vma, unsigned long start,
+		unsigned long end);
 
 struct mmu_notifier_range;
 
include/linux/mm_types.h +0 -4
index ca47e66d1b14..b724cbe933e6 100644
@@ -392,8 +392,6 @@ struct vm_area_struct {
 	unsigned long vm_end;		/* The first byte after our end address
 					   within vm_mm. */
 
-	/* linked list of VM areas per task, sorted by address */
-	struct vm_area_struct *vm_next, *vm_prev;
 	struct mm_struct *vm_mm;	/* The address space we belong to. */
 
 	/*
@@ -457,7 +455,6 @@ struct vm_area_struct {
 struct kioctx_table;
 struct mm_struct {
 	struct {
-		struct vm_area_struct *mmap;		/* list of VMAs */
 		struct maple_tree mm_mt;
 #ifdef CONFIG_MMU
 		unsigned long (*get_unmapped_area) (struct file *filp,
@@ -472,7 +469,6 @@ struct mm_struct {
 		unsigned long mmap_compat_legacy_base;
 #endif
 		unsigned long task_size;	/* size of task vm space */
-		unsigned long highest_vm_end;	/* highest vma end address */
 		pgd_t * pgd;
 
 #ifdef CONFIG_MEMBARRIER
kernel/fork.c +1 -14
index fa0ec0783784..0b032f02c658 100644
@@ -474,7 +474,6 @@ struct vm_area_struct *vm_area_dup(struct vm_area_struct *orig)
 		 */
 		*new = data_race(*orig);
 		INIT_LIST_HEAD(&new->anon_vma_chain);
-		new->vm_next = new->vm_prev = NULL;
 		dup_anon_vma_name(orig, new);
 	}
 	return new;
@@ -579,7 +578,7 @@ static void dup_mm_exe_file(struct mm_struct *mm, struct mm_struct *oldmm)
 static __latent_entropy int dup_mmap(struct mm_struct *mm,
 					struct mm_struct *oldmm)
 {
-	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
+	struct vm_area_struct *mpnt, *tmp;
 	int retval;
 	unsigned long charge = 0;
 	MA_STATE(old_mas, &oldmm->mm_mt, 0, 0);
@@ -606,7 +605,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	mm->exec_vm = oldmm->exec_vm;
 	mm->stack_vm = oldmm->stack_vm;
 
-	pprev = &mm->mmap;
 	retval = ksm_fork(mm, oldmm);
 	if (retval)
 		goto out;
@@ -614,8 +612,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 	if (retval)
 		goto out;
 
-	prev = NULL;
-
 	retval = mas_expected_entries(&mas, oldmm->map_count);
 	if (retval)
 		goto out;
@@ -687,14 +683,6 @@ static __latent_entropy int dup_mmap(struct mm_struct *mm,
 		if (is_vm_hugetlb_page(tmp))
 			reset_vma_resv_huge_pages(tmp);
 
-		/*
-		 * Link in the new vma and copy the page table entries.
-		 */
-		*pprev = tmp;
-		pprev = &tmp->vm_next;
-		tmp->vm_prev = prev;
-		prev = tmp;
-
 		/* Link the vma into the MT */
 		mas.index = tmp->vm_start;
 		mas.last = tmp->vm_end - 1;
@@ -1112,7 +1100,6 @@ static void mm_init_uprobes_state(struct mm_struct *mm)
 static struct mm_struct *mm_init(struct mm_struct *mm, struct task_struct *p,
 	struct user_namespace *user_ns)
 {
-	mm->mmap = NULL;
 	mt_init_flags(&mm->mm_mt, MM_MT_FLAGS);
 	mt_set_external_lock(&mm->mm_mt, &mm->mmap_lock);
 	atomic_set(&mm->mm_users, 1);
mm/debug.c +6 -8
index 2d625ca0e326..0fd15ba70d16 100644
@@ -139,13 +139,11 @@ EXPORT_SYMBOL(dump_page);
 
 void dump_vma(const struct vm_area_struct *vma)
 {
-	pr_emerg("vma %px start %px end %px\n"
-		"next %px prev %px mm %px\n"
+	pr_emerg("vma %px start %px end %px mm %px\n"
 		"prot %lx anon_vma %px vm_ops %px\n"
 		"pgoff %lx file %px private_data %px\n"
 		"flags: %#lx(%pGv)\n",
-		vma, (void *)vma->vm_start, (void *)vma->vm_end, vma->vm_next,
-		vma->vm_prev, vma->vm_mm,
+		vma, (void *)vma->vm_start, (void *)vma->vm_end, vma->vm_mm,
 		(unsigned long)pgprot_val(vma->vm_page_prot),
 		vma->anon_vma, vma->vm_ops, vma->vm_pgoff,
 		vma->vm_file, vma->vm_private_data,
@@ -155,11 +153,11 @@ EXPORT_SYMBOL(dump_vma);
 
 void dump_mm(const struct mm_struct *mm)
 {
-	pr_emerg("mm %px mmap %px task_size %lu\n"
+	pr_emerg("mm %px task_size %lu\n"
 #ifdef CONFIG_MMU
 		"get_unmapped_area %px\n"
 #endif
-		"mmap_base %lu mmap_legacy_base %lu highest_vm_end %lu\n"
+		"mmap_base %lu mmap_legacy_base %lu\n"
 		"pgd %px mm_users %d mm_count %d pgtables_bytes %lu map_count %d\n"
 		"hiwater_rss %lx hiwater_vm %lx total_vm %lx locked_vm %lx\n"
 		"pinned_vm %llx data_vm %lx exec_vm %lx stack_vm %lx\n"
@@ -183,11 +181,11 @@ void dump_mm(const struct mm_struct *mm)
 		"tlb_flush_pending %d\n"
 		"def_flags: %#lx(%pGv)\n",
 
-		mm, mm->mmap, mm->task_size,
+		mm, mm->task_size,
 #ifdef CONFIG_MMU
 		mm->get_unmapped_area,
 #endif
-		mm->mmap_base, mm->mmap_legacy_base, mm->highest_vm_end,
+		mm->mmap_base, mm->mmap_legacy_base,
 		mm->pgd, atomic_read(&mm->mm_users),
 		atomic_read(&mm->mm_count),
 		mm_pgtables_bytes(mm),
mm/internal.h +3 -5
index 92734fc9b90d..65f1294f0335 100644
@@ -69,8 +69,9 @@ void folio_rotate_reclaimable(struct folio *folio);
 bool __folio_end_writeback(struct folio *folio);
 void deactivate_file_folio(struct folio *folio);
 
-void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *start_vma,
-		unsigned long floor, unsigned long ceiling);
+void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
+		   struct vm_area_struct *start_vma, unsigned long floor,
+		   unsigned long ceiling);
 void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte);
 
 struct zap_details;
@@ -492,9 +493,6 @@ static inline void vma_mas_remove(struct vm_area_struct *vma, struct ma_state *m
 }
 
 /* mm/util.c */
-void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
-		struct vm_area_struct *prev);
-void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma);
 struct anon_vma *folio_anon_vma(struct folio *folio);
 
 #ifdef CONFIG_MMU
mm/memory.c +24 -9
index 5513d049e7e0..77753da71cd1 100644
@@ -400,12 +400,21 @@ void free_pgd_range(struct mmu_gather *tlb,
 	} while (pgd++, addr = next, addr != end);
 }
 
-void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
-		unsigned long floor, unsigned long ceiling)
+void free_pgtables(struct mmu_gather *tlb, struct maple_tree *mt,
+		   struct vm_area_struct *vma, unsigned long floor,
+		   unsigned long ceiling)
 {
-	while (vma) {
-		struct vm_area_struct *next = vma->vm_next;
+	MA_STATE(mas, mt, vma->vm_end, vma->vm_end);
+
+	do {
 		unsigned long addr = vma->vm_start;
+		struct vm_area_struct *next;
+
+		/*
+		 * 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);
 
 		/*
 		 * Hide vma from rmap and truncate_pagecache before freeing
@@ -424,7 +433,7 @@ void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
 			while (next && next->vm_start <= vma->vm_end + PMD_SIZE
 			       && !is_vm_hugetlb_page(next)) {
 				vma = next;
-				next = vma->vm_next;
+				next = mas_find(&mas, ceiling - 1);
 				unlink_anon_vmas(vma);
 				unlink_file_vma(vma);
 			}
@@ -432,7 +441,7 @@ void free_pgtables(struct mmu_gather *tlb, struct vm_area_struct *vma,
 				floor, next ? next->vm_start : ceiling);
 		}
 		vma = next;
-	}
+	} while (vma);
 }
 
 void pmd_install(struct mm_struct *mm, pmd_t *pmd, pgtable_t *pte)
@@ -1628,17 +1637,19 @@ 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,
+void unmap_vmas(struct mmu_gather *tlb, struct maple_tree *mt,
 		struct vm_area_struct *vma, unsigned long start_addr,
 		unsigned long end_addr)
 {
 	struct mmu_notifier_range range;
+	MA_STATE(mas, mt, vma->vm_end, vma->vm_end);
 
 	mmu_notifier_range_init(&range, MMU_NOTIFY_UNMAP, 0, vma, vma->vm_mm,
 				start_addr, end_addr);
 	mmu_notifier_invalidate_range_start(&range);
-	for ( ; vma && vma->vm_start < end_addr; vma = vma->vm_next)
+	do {
 		unmap_single_vma(tlb, vma, start_addr, end_addr, NULL);
+	} while ((vma = mas_find(&mas, end_addr - 1)) != NULL);
 	mmu_notifier_invalidate_range_end(&range);
 }
 
@@ -1653,8 +1664,11 @@ void unmap_vmas(struct mmu_gather *tlb,
 void zap_page_range(struct vm_area_struct *vma, unsigned long start,
 		unsigned long size)
 {
+	struct maple_tree *mt = &vma->vm_mm->mm_mt;
+	unsigned long end = start + size;
 	struct mmu_notifier_range range;
 	struct mmu_gather tlb;
+	MA_STATE(mas, mt, vma->vm_end, vma->vm_end);
 
 	lru_add_drain();
 	mmu_notifier_range_init(&range, MMU_NOTIFY_CLEAR, 0, vma, vma->vm_mm,
@@ -1662,8 +1676,9 @@ void zap_page_range(struct vm_area_struct *vma, unsigned long start,
 	tlb_gather_mmu(&tlb, vma->vm_mm);
 	update_hiwater_rss(vma->vm_mm);
 	mmu_notifier_invalidate_range_start(&range);
-	for ( ; vma && vma->vm_start < range.end; vma = vma->vm_next)
+	do {
 		unmap_single_vma(&tlb, vma, start, range.end, NULL);
+	} while ((vma = mas_find(&mas, end - 1)) != NULL);
 	mmu_notifier_invalidate_range_end(&range);
 	tlb_finish_mmu(&tlb);
 }
mm/mmap.c +181 -252

878 lines not on this page · raw message

mm/nommu.c +0 -5
index 645d11d3a8ab..8b801f5c9ef9 100644
@@ -551,7 +551,6 @@ static void put_nommu_region(struct vm_region *region)
 static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 {
 	struct address_space *mapping;
-	struct vm_area_struct *prev;
 	MA_STATE(mas, &mm->mm_mt, vma->vm_start, vma->vm_end);
 
 	BUG_ON(!vma->vm_region);
@@ -570,11 +569,8 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 		i_mmap_unlock_write(mapping);
 	}
 
-	prev = mas_prev(&mas, 0);
-	mas_reset(&mas);
 	/* add the VMA to the tree */
 	vma_mas_store(vma, &mas);
-	__vma_link_list(mm, vma, prev);
 }
 
 /*
@@ -599,7 +595,6 @@ static void delete_vma_from_mm(struct vm_area_struct *vma)
 
 	/* remove from the MM's tree and list */
 	vma_mas_remove(vma, &mas);
-	__vma_unlink_list(vma->vm_mm, vma);
 }
 
 /*
mm/util.c +0 -40
index 486cb132a887..1a5856f469e1 100644
@@ -272,46 +272,6 @@ void *memdup_user_nul(const void __user *src, size_t len)
 }
 EXPORT_SYMBOL(memdup_user_nul);
 
-void __vma_link_list(struct mm_struct *mm, struct vm_area_struct *vma,
-		struct vm_area_struct *prev)
-{
-	struct vm_area_struct *next;
-
-	vma->vm_prev = prev;
-	if (prev) {
-		next = prev->vm_next;
-		prev->vm_next = vma;
-	} else {
-		next = mm->mmap;
-		mm->mmap = vma;
-	}
-	vma->vm_next = next;
-	if (next)
-		next->vm_prev = vma;
-	else
-		mm->highest_vm_end = vm_end_gap(vma);
-}
-
-void __vma_unlink_list(struct mm_struct *mm, struct vm_area_struct *vma)
-{
-	struct vm_area_struct *prev, *next;
-
-	next = vma->vm_next;
-	prev = vma->vm_prev;
-	if (prev)
-		prev->vm_next = next;
-	else
-		mm->mmap = next;
-	if (next) {
-		next->vm_prev = prev;
-	} else {
-		if (prev)
-			mm->highest_vm_end = vm_end_gap(prev);
-		else
-			mm->highest_vm_end = 0;
-	}
-}
-
 /* Check if the vma is being used as a stack by this task */
 int vma_is_stack_for_current(struct vm_area_struct *vma)
 {
Signature · 1 line
2.35.1
#98 lore raw

PATCH v8 69/70 mm/mmap: drop range_has_overlap() function

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

Since there is no longer a linked list, the range_has_overlap() function is identical to the find_vma_intersection() function.

---
 mm/mmap.c | 28 +---------------------------
 1 file changed, 1 insertion(+), 27 deletions(-)
mm/mmap.c +1 -27
index 50b616449c87..01985a0d664e 100644
@@ -440,30 +440,6 @@ anon_vma_interval_tree_post_update_vma(struct vm_area_struct *vma)
 		anon_vma_interval_tree_insert(avc, &avc->anon_vma->rb_root);
 }
 
-/*
- * range_has_overlap() - Check the @start - @end range for overlapping VMAs and
- * sets up a pointer to the previous VMA
- * @mm: the mm struct
- * @start: the start address of the range
- * @end: the end address of the range
- * @pprev: the pointer to the pointer of the previous VMA
- *
- * Returns: True if there is an overlapping VMA, false otherwise
- */
-static inline
-bool range_has_overlap(struct mm_struct *mm, unsigned long start,
-		       unsigned long end, struct vm_area_struct **pprev)
-{
-	struct vm_area_struct *existing;
-
-	MA_STATE(mas, &mm->mm_mt, start, start);
-	rcu_read_lock();
-	existing = mas_find(&mas, end - 1);
-	*pprev = mas_prev(&mas, 0);
-	rcu_read_unlock();
-	return existing ? true : false;
-}
-
 static unsigned long count_vma_pages_range(struct mm_struct *mm,
 		unsigned long addr, unsigned long end)
 {
@@ -3210,9 +3186,7 @@ void exit_mmap(struct mm_struct *mm)
  */
 int insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
 {
-	struct vm_area_struct *prev;
-
-	if (range_has_overlap(mm, vma->vm_start, vma->vm_end, &prev))
+	if (find_vma_intersection(mm, vma->vm_start, vma->vm_end))
 		return -ENOMEM;
 
 	if ((vma->vm_flags & VM_ACCOUNT) &&
Signature · 1 line
2.35.1
#99 lore raw

PATCH v8 70/70 mm/mmap.c: pass in mapping to __vma_link_file()

In reply to Liam Howlett

From: "Liam R. Howlett" <[email protected]>

__vma_link_file() resolves the mapping from the file, if there is one. Pass through the mapping and check the vm_file externally since most places already have the required information and check of vm_file.

---
 mm/mmap.c | 33 ++++++++++++++-------------------
 1 file changed, 14 insertions(+), 19 deletions(-)
mm/mmap.c +14 -19
index 01985a0d664e..6a37f5d2e496 100644
@@ -249,6 +249,7 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
 	if (brk < min_brk)
 		goto out;
 
+
 	/*
 	 * Check against rlimit here. If this check is done later after the test
 	 * of oldbrk with newbrk then it can escape the test and let the data
@@ -325,7 +326,6 @@ SYSCALL_DEFINE1(brk, unsigned long, brk)
 	if (populate)
 		mm_populate(oldbrk, newbrk - oldbrk);
 	return brk;
-
 out:
 	mmap_write_unlock(mm);
 	return origbrk;
@@ -457,21 +457,15 @@ static unsigned long count_vma_pages_range(struct mm_struct *mm,
 	return nr_pages;
 }
 
-static void __vma_link_file(struct vm_area_struct *vma)
+static void __vma_link_file(struct vm_area_struct *vma,
+			    struct address_space *mapping)
 {
-	struct file *file;
-
-	file = vma->vm_file;
-	if (file) {
-		struct address_space *mapping = file->f_mapping;
-
-		if (vma->vm_flags & VM_SHARED)
-			mapping_allow_writable(mapping);
+	if (vma->vm_flags & VM_SHARED)
+		mapping_allow_writable(mapping);
 
-		flush_dcache_mmap_lock(mapping);
-		vma_interval_tree_insert(vma, &mapping->i_mmap);
-		flush_dcache_mmap_unlock(mapping);
-	}
+	flush_dcache_mmap_lock(mapping);
+	vma_interval_tree_insert(vma, &mapping->i_mmap);
+	flush_dcache_mmap_unlock(mapping);
 }
 
 /*
@@ -518,10 +512,11 @@ static int vma_link(struct mm_struct *mm, struct vm_area_struct *vma)
 	}
 
 	vma_mas_store(vma, &mas);
-	__vma_link_file(vma);
 
-	if (mapping)
+	if (mapping) {
+		__vma_link_file(vma, mapping);
 		i_mmap_unlock_write(mapping);
+	}
 
 	mm->map_count++;
 	validate_mm(mm);
@@ -762,14 +757,14 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
 			uprobe_munmap(next, next->vm_start, next->vm_end);
 
 		i_mmap_lock_write(mapping);
-		if (insert) {
+		if (insert && insert->vm_file) {
 			/*
 			 * Put into interval tree now, so instantiated pages
 			 * are visible to arm/parisc __flush_dcache_page
 			 * throughout; but we cannot insert into address
 			 * space until vma start or end is updated.
 			 */
-			__vma_link_file(insert);
+			__vma_link_file(insert, insert->vm_file->f_mapping);
 		}
 	}
 
@@ -2982,7 +2977,6 @@ static int do_brk_flags(struct ma_state *mas, struct vm_area_struct *vma,
 	struct mm_struct *mm = current->mm;
 	validate_mm_mt(mm);
 
-
 	/*
 	 * Check against address space limits by the changed size
 	 * Note: This happens *after* clearing old mappings in some code paths.
@@ -3037,6 +3031,7 @@ static int do_brk_flags(struct ma_state *mas, struct vm_area_struct *vma,
 	mas_set_range(mas, vma->vm_start, addr + len - 1);
 	mas_store_gfp(mas, vma, GFP_KERNEL);
 	mm->map_count++;
+
 out:
 	perf_event_mmap(vma);
 	mm->total_vm += len >> PAGE_SHIFT;
Signature · 1 line
2.35.1
maintainer
#100 lore raw
In reply to Liam Howlett
Quoted 4 lines · On Tue, 26 Apr 2022 15:06:19 +0000 Liam Howlett <[email protected]> wrote:

Please replace the patches in your mglru-maple branch with this set. It should be a drop in replacement for my patch range with the fixes into these patches. Adding the preallocation to work around the fs-reclaim LOCKDEP issue caused enough changes to the patches to warrant a respin.

OK, thanks. I'll give these a bit of testing locally with a view to having a run in -next soon.

It's all not looking very reviewed. Any thoughts on who we could attempt to presuade to hep out here?

Quoted 3 lines

The last patch on the branch is still needed to fix vmscan after mglru is applied. ee4b1fc24f30 "mm/vmscan: Use VMA_ITERATOR in get_next_vma()"

OK, someone please send that at me when the next rev of mglru surfaces?

maintainer
#101 lore raw
In reply to Liam Howlett
Quoted 2 lines · On Tue, 26 Apr 2022 15:06:19 +0000 Liam Howlett <[email protected]> wrote:

The maple tree is an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel

I think it would be helpful to expand on "a number of places". Specifically which places?

Quoted 6 lines

that a non-overlapping range-based tree would be beneficial, especially one with a simple interface. The first user that is covered in this patch set is the vm_area_struct, where three data structures are replaced by the maple tree: the augmented rbtree, the vma cache, and the linked list of VMAs in the mm_struct. The long term goal is to reduce or remove the mmap_sem contention.

"mmap_lock" ;)

Quoted 6 lines

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly shorter than the rbtree so it has fewer cache misses. The removal of the linked list between subsequent entries also reduces the cache misses and the need to pull in the previous and next VMA during many tree alterations.

Do we have any quantitative testing results?

What's the plan on utilizing this to further reduce mmap_lock contention?

maintainer
#102 lore raw
Quoted 6 lines · Andrew Morton
Quoted 2 lines · On Tue, 26 Apr 2022 15:06:19 +0000 Liam Howlett <[email protected]> wrote:

The maple tree is an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel

I think it would be helpful to expand on "a number of places". Specifically which places?

The page cache would be a good place to use it once it has a few more features to bring it up to par with the radix tree. I can go into more detail if you want.

In general, anywhere that's using the IDR/Radix Tree/XArray would benefit. The radix tree has some pretty poor space consumption properties, particularly for anyone using the cyclic variants.

Many users of the rbtree would have better performance if converted to the maple tree.

Ultimately, it's going to be incumbent on people who know their own chunk of the kernel to say "Oh, yes, I can use that data structure", rather than on Liam to go around converting everybody's code for them.

#103 lore raw
In reply to Andrew Morton
Quoted 7 lines · Andrew Morton
Quoted 2 lines · On Tue, 26 Apr 2022 15:06:19 +0000 Liam Howlett <[email protected]> wrote:

The maple tree is an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel

I think it would be helpful to expand on "a number of places". Specifically which places?

Matthew answered this, but if you look for users of the interval tree you will come across many users that do not have overlapping ranges. The interval tree is being (ab)used because it is easier than the other options even though it is not necessarily the best choice for the data being stored. I don't want to be negative about the other options, they are all really valuable and have their uses. I think where the maple tree excels is the ease of use and the cache efficiency.

Quoted 9 lines
Quoted 7 lines

that a non-overlapping range-based tree would be beneficial, especially one with a simple interface. The first user that is covered in this patch set is the vm_area_struct, where three data structures are replaced by the maple tree: the augmented rbtree, the vma cache, and the linked list of VMAs in the mm_struct. The long term goal is to reduce or remove the mmap_sem contention.

"mmap_lock" ;)

Ah, right. Thanks.

Quoted 9 lines
Quoted 7 lines

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly shorter than the rbtree so it has fewer cache misses. The removal of the linked list between subsequent entries also reduces the cache misses and the need to pull in the previous and next VMA during many tree alterations.

Do we have any quantitative testing results?

I was waiting for the mmtests sweep to complete before sending them but I didn't want to hold up Yu Zhao's testing of the combined tree as it has proved useful already. Please don't include the results in the first commit as it wouldn't make much sense. If you intend to put them in a commit message, please put them in the patch introducing the maple tree. The benchmarks are around the same as they have always been.

kernbench

                               rb5.18-rc2             mt5.18-rc2
Amean     user-2        862.24 (   0.00%)      861.45 *   0.09%*
Amean     syst-2        136.65 (   0.00%)      141.58 *  -3.61%*
Amean     elsp-2        505.38 (   0.00%)      507.99 *  -0.52%*
Amean     user-4        890.24 (   0.00%)      888.34 *   0.21%*
Amean     syst-4        140.64 (   0.00%)      145.32 *  -3.33%*
Amean     elsp-4        264.34 (   0.00%)      265.76 *  -0.54%*
Amean     user-8        952.30 (   0.00%)      947.57 *   0.50%*
Amean     syst-8        145.52 (   0.00%)      147.79 *  -1.56%*
Amean     elsp-8        145.02 (   0.00%)      145.38 *  -0.24%*
Amean     user-16       920.83 (   0.00%)      918.95 *   0.20%*
Amean     syst-16       135.37 (   0.00%)      138.99 *  -2.67%*
Amean     elsp-16        75.03 (   0.00%)       75.25 *  -0.29%*
Amean     user-32       970.98 (   0.00%)      969.01 *   0.20%*
Amean     syst-32       144.75 (   0.00%)      148.58 *  -2.64%*
Amean     elsp-32        44.10 (   0.00%)       44.64 *  -1.24%*
Amean     user-64      1062.19 (   0.00%)     1060.30 *   0.18%*
Amean     syst-64       154.24 (   0.00%)      157.58 *  -2.17%*
Amean     elsp-64        28.88 (   0.00%)       29.10 *  -0.76%*
Amean     user-128     1609.09 (   0.00%)     1612.19 *  -0.19%*
Amean     syst-128      210.05 (   0.00%)      215.09 *  -2.40%*
Amean     elsp-128       25.22 (   0.00%)       25.45 *  -0.94%*
Amean     user-256     1767.37 (   0.00%)     1766.86 *   0.03%*
Amean     syst-256      215.99 (   0.00%)      221.56 *  -2.58%*
Amean     elsp-256       25.20 (   0.00%)       25.33 *  -0.54%*
Amean     user-288     1772.73 (   0.00%)     1772.35 *   0.02%*
Amean     syst-288      216.08 (   0.00%)      221.39 *  -2.45%*
Amean     elsp-288       25.16 (   0.00%)       25.44 *  -1.13%*

Increase in performance in the following micro-benchmarks in Hmean:
- context_switch1-processes +14.74% to 2.22%

Mixed results in the following micro-benchmarks in Hmean:
- malloc1-threads +34.95% to -30.06%
- malloc1-processes +2.73% to -23.65%
- page_fault3-threads +19.84% to -11.55%
- pthread_mutex1-threads +42.50% to -11.76%

Decrease in performance in the following micro-benchmarks in Hmean:
- brk1-processes -35.35% to -42.69%

brk1-processes decrease is due to the test itself. Since the VMA cannot be expanded, the test is actually inserting a new VMA.

Quoted 2 lines

What's the plan on utilizing this to further reduce mmap_lock contention?

The plan is to get to the point where we use the maple tree in RCU mode. Readers will not block for writers. A single write operation will be allowed at a time. A reader re-walks if stale data is encountered. VMAs would be RCU enabled and this mode would be entered once multiple tasks are using the mm_struct. I can go into more details if you want.

maintainer
#104 lore raw
Quoted 7 lines · On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <[email protected]> wrote:
Quoted 7 lines
Quoted 6 lines

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly shorter than the rbtree so it has fewer cache misses. The removal of the linked list between subsequent entries also reduces the cache misses and the need to pull in the previous and next VMA during many tree alterations.

Quoted 7 lines
Quoted 1 line

Do we have any quantitative testing results?

I was waiting for the mmtests sweep to complete before sending them but I didn't want to hold up Yu Zhao's testing of the combined tree as it has proved useful already. Please don't include the results in the first commit as it wouldn't make much sense. If you intend to put them in a commit message, please put them in the patch introducing the maple tree.

I did that.

Quoted 1 line

The benchmarks are around the same as they have always been.

So it's presently a wash.

That makes "the plan" (below) really critical, otherwise there seems little point in merging this code at this time?

Please send me many very soothing words about how confident we should be that the plan will be implemented and that it shall be good?

Quoted 8 lines
Quoted 2 lines

What's the plan on utilizing this to further reduce mmap_lock contention?

The plan is to get to the point where we use the maple tree in RCU mode. Readers will not block for writers. A single write operation will be allowed at a time. A reader re-walks if stale data is encountered. VMAs would be RCU enabled and this mode would be entered once multiple tasks are using the mm_struct. I can go into more details if you want.

Uh, that's very important information. It's really the whole point
of the patchset! I added this to the [0/n] changelog.

maintainer
#105 lore raw
Quoted 10 lines · Andrew Morton
Quoted 1 line · On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <[email protected]> wrote:

The benchmarks are around the same as they have always been.

So it's presently a wash.

That makes "the plan" (below) really critical, otherwise there seems little point in merging this code at this time?

Please send me many very soothing words about how confident we should be that the plan will be implemented and that it shall be good?

Yes, performance-wise it's a wash. However, Davidlohr was very impressed that it was a wash because we're actually getting rid of three data structures here; the linked list, the rbtree and the vmacache. His opinion was that we should push the maple tree in now, in advance of the future RCU uses.

We also have other users waiting in the wings. Dave Howells has something he's working on that uses the maple tree directly. I have a couple of XArray users that are using it inappropriately that I want to convert ... I just didn't want to do that work before all this lands.

The current LSFMM schedule has very many words about the Maple tree scheduled for 13:30-15:00 on Monday. Hopefully we'll have a better idea after that how confident we are that RCU VMA walking is going to work.

#106 lore raw
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Andrew Morton
Quoted 1 line · On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <[email protected]> wrote:

The benchmarks are around the same as they have always been.

So it's presently a wash.

That makes "the plan" (below) really critical, otherwise there seems little point in merging this code at this time?

Quoted 8 lines
Quoted 2 lines

Please send me many very soothing words about how confident we should be that the plan will be implemented and that it shall be good?

Yes, performance-wise it's a wash. However, Davidlohr was very impressed that it was a wash because we're actually getting rid of three data structures here; the linked list, the rbtree and the vmacache. His opinion was that we should push the maple tree in now, in advance of the future RCU uses.

Yes I like the maple tree, and at this stage I don't think we can ask for more from this series wrt the MM - albeit there seems to still be some folks reporting breakage. Fundamentally I see Liam's work to (re)move complexity out of the MM (not to say that the actual maple tree is not complex) by consolidating the three complimentary data structures very much worth it considering performance does not take a hit. This was very much a turn off with the range locking approach, which worst case scenario incurred in prohibitive overhead. Also as Liam and Matthew have mentioned, RCU opens up a lot of nice performance opportunities, and in addition academia[1] has shown outstanding scalability of address spaces with the foundation of replacing the locked rbtree with RCU aware trees.

[1] https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf

Thanks,
Davidlohr

maintainer
#107 lore raw
Quoted 20 lines · On Sun, 1 May 2022 13:26:34 -0700 Davidlohr Bueso <[email protected]> wrote:
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Andrew Morton
Quoted 1 line · On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <[email protected]> wrote:

The benchmarks are around the same as they have always been.

So it's presently a wash.

That makes "the plan" (below) really critical, otherwise there seems little point in merging this code at this time?

Quoted 8 lines
Quoted 2 lines

Please send me many very soothing words about how confident we should be that the plan will be implemented and that it shall be good?

Yes, performance-wise it's a wash. However, Davidlohr was very impressed that it was a wash because we're actually getting rid of three data structures here; the linked list, the rbtree and the vmacache. His opinion was that we should push the maple tree in now, in advance of the future RCU uses.

Quoted 12 lines

Yes I like the maple tree, and at this stage I don't think we can ask for more from this series wrt the MM - albeit there seems to still be some folks reporting breakage. Fundamentally I see Liam's work to (re)move complexity out of the MM (not to say that the actual maple tree is not complex) by consolidating the three complimentary data structures very much worth it considering performance does not take a hit. This was very much a turn off with the range locking approach, which worst case scenario incurred in prohibitive overhead. Also as Liam and Matthew have mentioned, RCU opens up a lot of nice performance opportunities, and in addition academia[1] has shown outstanding scalability of address spaces with the foundation of replacing the locked rbtree with RCU aware trees.

Thanks. That sounded like a wordy acked-by to me? :)

Liam, I think the above is useful background for the [0/N].

Quoted 1 line

[1] https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf

As is that. The paper seems shockingly relevant. Do we know the authors or is it a cosmic coincidence?

#108 lore raw
Quoted 35 lines · Andrew Morton
Quoted 20 lines · On Sun, 1 May 2022 13:26:34 -0700 Davidlohr Bueso <[email protected]> wrote:
Quoted 9 lines · Matthew Wilcox
Quoted 8 lines · Andrew Morton
Quoted 1 line · On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <[email protected]> wrote:

The benchmarks are around the same as they have always been.

So it's presently a wash.

That makes "the plan" (below) really critical, otherwise there seems little point in merging this code at this time?

Quoted 8 lines
Quoted 2 lines

Please send me many very soothing words about how confident we should be that the plan will be implemented and that it shall be good?

Yes, performance-wise it's a wash. However, Davidlohr was very impressed that it was a wash because we're actually getting rid of three data structures here; the linked list, the rbtree and the vmacache. His opinion was that we should push the maple tree in now, in advance of the future RCU uses.

Quoted 12 lines

Yes I like the maple tree, and at this stage I don't think we can ask for more from this series wrt the MM - albeit there seems to still be some folks reporting breakage. Fundamentally I see Liam's work to (re)move complexity out of the MM (not to say that the actual maple tree is not complex) by consolidating the three complimentary data structures very much worth it considering performance does not take a hit. This was very much a turn off with the range locking approach, which worst case scenario incurred in prohibitive overhead. Also as Liam and Matthew have mentioned, RCU opens up a lot of nice performance opportunities, and in addition academia[1] has shown outstanding scalability of address spaces with the foundation of replacing the locked rbtree with RCU aware trees.

Quoted 9 lines

Thanks. That sounded like a wordy acked-by to me? :)

Liam, I think the above is useful background for the [0/N].

Quoted 1 line

[1] https://pdos.csail.mit.edu/papers/rcuvm:asplos12.pdf

As is that. The paper seems shockingly relevant. Do we know the authors or is it a cosmic coincidence?

Cosmic coincidence. We designed our tree with the intention of solving the hardest problem first. Upon settling on a b-tree variant and a rough outline, we researched ranged based b-trees and RCU b-trees and did find that article. So it was nice to find reassurances that we were on the right path, but our design choice of using ranges made that paper unusable for us.

Thanks,
Liam

#109 lore raw
In reply to Andrew Morton
Quoted 17 lines · Andrew Morton
Quoted 7 lines · On Wed, 27 Apr 2022 14:08:39 +0000 Liam Howlett <[email protected]> wrote:
Quoted 7 lines
Quoted 6 lines

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly shorter than the rbtree so it has fewer cache misses. The removal of the linked list between subsequent entries also reduces the cache misses and the need to pull in the previous and next VMA during many tree alterations.

Quoted 7 lines
Quoted 1 line

Do we have any quantitative testing results?

I was waiting for the mmtests sweep to complete before sending them but I didn't want to hold up Yu Zhao's testing of the combined tree as it has proved useful already. Please don't include the results in the first commit as it wouldn't make much sense. If you intend to put them in a commit message, please put them in the patch introducing the maple tree.

Quoted 8 lines

I did that.

Quoted 1 line

The benchmarks are around the same as they have always been.

So it's presently a wash.

That makes "the plan" (below) really critical, otherwise there seems little point in merging this code at this time?

There are a number of reasons to merge at this time. First, as Matthew said, we have more than one user so having the tree upstream would obviously help them out. Second, we can make sure this much (maple tree
+ vma tracking) works for everyone before we enable VMA RCU and play even more with the locking scenarios. The third reason is to get more community input into "the plan" to ensure the maple tree is beneficial in the most common execution paths and capture corner cases.

Quoted 3 lines

Please send me many very soothing words about how confident we should be that the plan will be implemented and that it shall be good?

Tea, warmth, fresh bread.

As we know, VMAs are rarely written and mostly read. This plan removes the majority of the slow down on readers. The only slow down is when a reader conflicts with a writer. We are actually slower on writes - we allocate nodes for the tree vs having it embedded in the VMA itself and we do more work in calculating the gaps, but we are actually fast enough to hide that on the read side. Once the writers stop blocking the readers it shall be good. We need this step to get to using the maple tree in RCU mode to make this happen.

Quoted 4 lines
Quoted 4 lines
Quoted 3 lines

What's the plan on utilizing this to further reduce mmap_lock contention?

Quoted 8 lines
Quoted 5 lines

The plan is to get to the point where we use the maple tree in RCU mode. Readers will not block for writers. A single write operation will be allowed at a time. A reader re-walks if stale data is encountered. VMAs would be RCU enabled and this mode would be entered once multiple tasks are using the mm_struct. I can go into more details if you want.

Uh, that's very important information. It's really the whole point
of the patchset! I added this to the [0/n] changelog.

Yes, but that's not what the patch set does today. I didn't want to include The Plan until it exists. I'd like to think that what we have here is worth while on its own and a good start - but a start to something big. It's hard enough to get people to look at 70 patches, doubly so for an RFC of 70. The interest from others in using a tree with an easy interface seems like a win as well.

I also have some side goals such as the removal of __vma_adjust() for code readability.

Thanks,
Liam

#110 lore raw
In reply to Liam Howlett
Quoted 35 lines · Liam Howlett

Andrew,

Please replace the patches in your mglru-maple branch with this set. It should be a drop in replacement for my patch range with the fixes into these patches. Adding the preallocation to work around the fs-reclaim LOCKDEP issue caused enough changes to the patches to warrant a respin.

The last patch on the branch is still needed to fix vmscan after mglru is applied. ee4b1fc24f30 "mm/vmscan: Use VMA_ITERATOR in get_next_vma()"

Here is the pretty cover letter you requested last time.

------------------------------------

The maple tree is an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel that a non-overlapping range-based tree would be beneficial, especially one with a simple interface. The first user that is covered in this patch set is the vm_area_struct, where three data structures are replaced by the maple tree: the augmented rbtree, the vma cache, and the linked list of VMAs in the mm_struct. The long term goal is to reduce or remove the mmap_sem contention.

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly shorter than the rbtree so it has fewer cache misses. The removal of the linked list between subsequent entries also reduces the cache misses and the need to pull in the previous and next VMA during many tree alterations.

This patch set is based on v5.18-rc2

git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220426

Quoted 11 lines

v8 changes:
- Added preallocations before any potential edits to the tree when holding the
i_mmap_lock to avoid fs-reclaim issues on extreme memory pressure.
- Fixed issue in mempolicy mas_for_each() loop.
- Moved static definitions inside ifdef for DEBUG_MAPLE
- Fixed compile warnings reported by build bots
- Moved mas_dfs_preorder() to testing code
- Changed __vma_adjust() to record the highest vma in case 6 instead of
finding it twice.
- Fixed locking issue in exit_mmap()
- Fixed up from/s-o-b ordering

Running some syscall fuzzer would trigger a crash.

 BUG: KASAN: use-after-free in mas_find
 ma_dead_node at lib/maple_tree.c:532
 (inlined by) mas_next_entry at lib/maple_tree.c:4637
 (inlined by) mas_find at lib/maple_tree.c:5869
 Read of size 8 at addr ffff88811c5e9c00 by task trinity-c0/1351

 CPU: 5 PID: 1351 Comm: trinity-c0 Not tainted 5.18.0-rc4-next-20220427 #3
 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-5.fc35 04/01/2014
 Call Trace:
  <TASK>
  dump_stack_lvl
  print_address_description.constprop.0.cold
  print_report.cold
  kasan_report
  mas_find
  apply_mlockall_flags
  __do_sys_munlockall
  do_syscall_64
  entry_SYSCALL_64_after_hwframe
 RIP: 0033:0x7f3105611a3d
 Code: 5b 41 5c c3 66 0f 1f 84 00 00 00 00 00 f3 0f 1e fa 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 738
 RSP: 002b:00007ffeefae7c68 EFLAGS: 00000246 ORIG_RAX: 0000000000000098
 RAX: ffffffffffffffda RBX: 0000000000000002 RCX: 00007f3105611a3d
 RDX: 00000000ffff0000 RSI: ffffffffffffafff RDI: 0000009357075a39
 RBP: 00007f3103f94000 R08: 00000000fffffff7 R09: 000000000000006b
 R10: fffffffffffffffd R11: 0000000000000246 R12: 0000000000000098
 R13: 00007f31054f06c0 R14: 00007f3103f94058 R15: 00007f3103f94000
  </TASK>

 Allocated by task 1351:
  kasan_save_stack
  __kasan_slab_alloc
  kmem_cache_alloc_bulk
  mas_alloc_nodes
  mas_preallocate
  __vma_adjust
  __split_vma
  do_mas_align_munmap.constprop.0
  __vm_munmap
  __x64_sys_munmap
  do_syscall_64
  entry_SYSCALL_64_after_hwframe

 Freed by task 1351:
  kasan_save_stack
  kasan_set_track
  kasan_set_free_info
  ____kasan_slab_free
  slab_free_freelist_hook
  kmem_cache_free_bulk.part.0
  mas_destroy
  mas_store_prealloc
  __vma_adjust
  vma_merge
  mlock_fixup
  apply_mlockall_flags
  __do_sys_munlockall
  do_syscall_64
  entry_SYSCALL_64_after_hwframe

 The buggy address belongs to the object at ffff88811c5e9c00
  which belongs to the cache maple_node of size 256
 The buggy address is located 0 bytes inside of
  256-byte region [ffff88811c5e9c00, ffff88811c5e9d00)

 The buggy address belongs to the physical page:
 page:ffffea0004717a00 refcount:1 mapcount:0 mapping:0000000000000000 index:0x0 pfn:0x11c5e8
 head:ffffea0004717a00 order:2 compound_mapcount:0 compound_pincount:0
 flags: 0x200000000010200(slab|head|node=0|zone=2)
 raw: 0200000000010200 ffffea0004f8da08 ffffea0004676a08 ffff888100050940
 raw: 0000000000000000 0000000000150015 00000001ffffffff 0000000000000000
 page dumped because: kasan: bad access detected

 Memory state around the buggy address:
  ffff88811c5e9b00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
  ffff88811c5e9b80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
 >ffff88811c5e9c00: fa fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
                    ^
  ffff88811c5e9c80: fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb fb
  ffff88811c5e9d00: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
 ==================================================================
 Disabling lock debugging due to kernel taint
 general protection fault, probably for non-canonical address 0xdffffc0000000001: 0000 [#1] PREEMPT SMP KASAN PTI
 KASAN: null-ptr-deref in range [0x0000000000000008-0x000000000000000f]
 CPU: 5 PID: 1351 Comm: trinity-c0 Tainted: G    B             5.18.0-rc4-next-20220427 #3
 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-5.fc35 04/01/2014
 RIP: 0010:mas_ascend
 Code: cb 18 41 89 d3 48 83 cb 04 41 83 f3 01 40 84 ed 40 0f 95 c7 41 20 fb 74 26 83 ee 01 48 63 f6 48 8d 14 f1 48 89 d6 48 c1 ee 03 <42> 80 3c 3e 00 0f 854
 RSP: 0018:ffffc9000279fc78 EFLAGS: 00010202
 RAX: 0000000000000000 RBX: ffff888106dc3504 RCX: 0000000000000000
 RDX: 0000000000000008 RSI: 0000000000000001 RDI: ffff88811d42e201
 RBP: 0000000000000002 R08: 0000000000000000 R09: ffff88810f723300
 R10: ffffffffffffffff R11: 0000000000000001 R12: ffffc9000279fe78
 R13: 0000000000000000 R14: ffff888106dc3500 R15: dffffc0000000000
 FS:  00007f31054f0740(0000) GS:ffff8882d2e80000(0000) knlGS:0000000000000000
 CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
 CR2: 00007f3104db847c CR3: 0000000127e80002 CR4: 0000000000370ee0
 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
 Call Trace:
  <TASK>
  mas_next_node
  mas_find
  apply_mlockall_flags
  __do_sys_munlockall
  do_syscall_64
  entry_SYSCALL_64_after_hwframe
 RIP: 0033:0x7f3105611a3d
 Code: 5b 41 5c c3 66 0f 1f 84 00 00 00 00 00 f3 0f 1e fa 48 89 f8 48 89 f7 48 89 d6 48 89 ca 4d 89 c2 4d 89 c8 4c 8b 4c 24 08 0f 05 <48> 3d 01 f0 ff ff 738
 RSP: 002b:00007ffeefae7c68 EFLAGS: 00000246 ORIG_RAX: 0000000000000098
 RAX: ffffffffffffffda RBX: 0000000000000002 RCX: 00007f3105611a3d
 RDX: 00000000ffff0000 RSI: ffffffffffffafff RDI: 0000009357075a39
 RBP: 00007f3103f94000 R08: 00000000fffffff7 R09: 000000000000006b
 R10: fffffffffffffffd R11: 0000000000000246 R12: 0000000000000098
 R13: 00007f31054f06c0 R14: 00007f3103f94058 R15: 00007f3103f94000
  </TASK>
 Modules linked in:
 ---[ end trace 0000000000000000 ]---
 RIP: 0010:mas_ascend
 Code: cb 18 41 89 d3 48 83 cb 04 41 83 f3 01 40 84 ed 40 0f 95 c7 41 20 fb 74 26 83 ee 01 48 63 f6 48 8d 14 f1 48 89 d6 48 c1 ee 03 <42> 80 3c 3e 00 0f 854
 RSP: 0018:ffffc9000279fc78 EFLAGS: 00010202
 RAX: 0000000000000000 RBX: ffff888106dc3504 RCX: 0000000000000000
 RDX: 0000000000000008 RSI: 0000000000000001 RDI: ffff88811d42e201
 RBP: 0000000000000002 R08: 0000000000000000 R09: ffff88810f723300
 R10: ffffffffffffffff R11: 0000000000000001 R12: ffffc9000279fe78
 R13: 0000000000000000 R14: ffff888106dc3500 R15: dffffc0000000000
 FS:  00007f31054f0740(0000) GS:ffff8882d2e80000(0000) knlGS:0000000000000000
 CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
 CR2: 00007f3104db847c CR3: 0000000127e80002 CR4: 0000000000370ee0
 DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
 DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
 Kernel panic - not syncing: Fatal exception
 Kernel Offset: 0x15400000 from 0xffffffff81000000 (relocation range: 0xffffffff80000000-0xffffffffbfffffff)
#111 lore raw
Quoted 50 lines · Qian Cai
Quoted 35 lines · Liam Howlett

Andrew,

Please replace the patches in your mglru-maple branch with this set. It should be a drop in replacement for my patch range with the fixes into these patches. Adding the preallocation to work around the fs-reclaim LOCKDEP issue caused enough changes to the patches to warrant a respin.

The last patch on the branch is still needed to fix vmscan after mglru is applied. ee4b1fc24f30 "mm/vmscan: Use VMA_ITERATOR in get_next_vma()"

Here is the pretty cover letter you requested last time.

------------------------------------

The maple tree is an RCU-safe range based B-tree designed to use modern processor cache efficiently. There are a number of places in the kernel that a non-overlapping range-based tree would be beneficial, especially one with a simple interface. The first user that is covered in this patch set is the vm_area_struct, where three data structures are replaced by the maple tree: the augmented rbtree, the vma cache, and the linked list of VMAs in the mm_struct. The long term goal is to reduce or remove the mmap_sem contention.

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf nodes. With the increased branching factor, it is significantly shorter than the rbtree so it has fewer cache misses. The removal of the linked list between subsequent entries also reduces the cache misses and the need to pull in the previous and next VMA during many tree alterations.

This patch set is based on v5.18-rc2

git: https://github.com/oracle/linux-uek/tree/howlett/maple/20220426

Quoted 11 lines

v8 changes:
- Added preallocations before any potential edits to the tree when holding the
i_mmap_lock to avoid fs-reclaim issues on extreme memory pressure.
- Fixed issue in mempolicy mas_for_each() loop.
- Moved static definitions inside ifdef for DEBUG_MAPLE
- Fixed compile warnings reported by build bots
- Moved mas_dfs_preorder() to testing code
- Changed __vma_adjust() to record the highest vma in case 6 instead of
finding it twice.
- Fixed locking issue in exit_mmap()
- Fixed up from/s-o-b ordering

Running some syscall fuzzer would trigger a crash.

Quoted 16 lines
 BUG: KASAN: use-after-free in mas_find
 ma_dead_node at lib/maple_tree.c:532
 (inlined by) mas_next_entry at lib/maple_tree.c:4637
 (inlined by) mas_find at lib/maple_tree.c:5869
 Read of size 8 at addr ffff88811c5e9c00 by task trinity-c0/1351

 CPU: 5 PID: 1351 Comm: trinity-c0 Not tainted 5.18.0-rc4-next-20220427 #3
 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-5.fc35 04/01/2014
 Call Trace:
  <TASK>
  dump_stack_lvl
  print_address_description.constprop.0.cold
  print_report.cold
  kasan_report
  mas_find
  apply_mlockall_flags

Thanks. This is indeed an issue with 0d43186b36c1 (mm/mlock: use vma iterator and instead of vma linked list)

Andrew, Please include this patch as a fix.

Thanks,
Liam

From 62c50b9683d10ccaa0b689459efaa41794db129b Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <[email protected]>
Date: Wed, 27 Apr 2022 12:46:04 -0400
Subject: [PATCH] mm/mlock: Use maple state in apply_mlockall_flags()

The vma iterator is for simple cases. Since mlock_fixup() can cause the tree to change and thus requires the maple state to be reset, apply_mlockall_flags() is not a simple case. Use a maple state and call mas_pause() instead.

Fixes 0d43186b36c1 (mm/mlock: use vma iterator and instead of vma

linked list)

---
 mm/mlock.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
mm/mlock.c +3 -2
index d8549b3dcb59..c41604ba5197 100644
@@ -660,7 +660,7 @@ SYSCALL_DEFINE2(munlock, unsigned long, start, size_t, len)
  */
 static int apply_mlockall_flags(int flags)
 {
-	VMA_ITERATOR(vmi, current->mm, 0);
+	MA_STATE(mas, &current->mm->mm_mt, 0, 0);
 	struct vm_area_struct *vma, *prev = NULL;
 	vm_flags_t to_add = 0;
 
@@ -681,7 +681,7 @@ static int apply_mlockall_flags(int flags)
 			to_add |= VM_LOCKONFAULT;
 	}
 
-	for_each_vma(vmi, vma) {
+	mas_for_each(&mas, vma, ULONG_MAX) {
 		vm_flags_t newflags;
 
 		newflags = vma->vm_flags & VM_LOCKED_CLEAR_MASK;
@@ -689,6 +689,7 @@ static int apply_mlockall_flags(int flags)
 
 		/* Ignore errors */
 		mlock_fixup(vma, &prev, vma->vm_start, vma->vm_end, newflags);
+		mas_pause(&mas);
 		cond_resched();
 	}
 out:
Signature · 1 line
2.35.1
#112 lore raw
Quoted 4 lines · Liam Howlett

Thanks. This is indeed an issue with 0d43186b36c1 (mm/mlock: use vma iterator and instead of vma linked list)

Andrew, Please include this patch as a fix.

Even with the patch applied, there are still thousands of memory leaks reports from kmemleak after booting.

unreferenced object 0xffff400259bd6d00 (size 256):
comm "multipathd", pid 2577, jiffies 4294915929 (age 2370.384s) hex dump (first 32 bytes):

    00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
    00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

backtrace:
slab_post_alloc_hook
kmem_cache_alloc_bulk
mas_alloc_nodes
mt_alloc_bulk at lib/maple_tree.c:151 (inlined by) mas_alloc_nodes at lib/maple_tree.c:1244 mas_preallocate
__vma_adjust
shift_arg_pages
setup_arg_pages
load_elf_binary
search_binary_handler
exec_binprm
bprm_execve
do_execveat_common.isra.0
__arm64_sys_execve
invoke_syscall
el0_svc_common.constprop.0
do_el0_svc

#113 lore raw
Quoted 8 lines · Qian Cai
Quoted 4 lines · Liam Howlett

Thanks. This is indeed an issue with 0d43186b36c1 (mm/mlock: use vma iterator and instead of vma linked list)

Andrew, Please include this patch as a fix.

Even with the patch applied, there are still thousands of memory leaks reports from kmemleak after booting.

Thank you for finding this.

Quoted 17 lines

unreferenced object 0xffff400259bd6d00 (size 256):
comm "multipathd", pid 2577, jiffies 4294915929 (age 2370.384s) hex dump (first 32 bytes):

    00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
    00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................

backtrace:
slab_post_alloc_hook
kmem_cache_alloc_bulk
mas_alloc_nodes
mt_alloc_bulk at lib/maple_tree.c:151 (inlined by) mas_alloc_nodes at lib/maple_tree.c:1244 mas_preallocate
__vma_adjust
shift_arg_pages
setup_arg_pages
load_elf_binary

Quoted 8 lines

search_binary_handler
exec_binprm
bprm_execve
do_execveat_common.isra.0
__arm64_sys_execve
invoke_syscall
el0_svc_common.constprop.0
do_el0_svc

__vma_adjust is way too complicated. This patch should fix the leak.

Andrew, please add this patch to "mm: start tracking VMAs with maple tree"

Thanks,
Liam

From 74f551227d44b351d56f4ec0a36542d871f337d5 Mon Sep 17 00:00:00 2001
From: "Liam R. Howlett" <[email protected]>
Date: Wed, 27 Apr 2022 18:40:00 -0400
Subject: [PATCH] mm/mmap: Fix __vma_adjust() memory leak.

When shifting the arg pages, the maple state may be left with allocated memory. Free the memory by calling mas_destroy() unconditionally at the end of the function.

Fixes bd6a1fd58daf (mm: start tracking VMAs with maple tree)
---
 mm/mmap.c | 1 +
 1 file changed, 1 insertion(+)
mm/mmap.c +1 -0
index 6a37f5d2e496..f52bbf9aa024 100644
@@ -904,6 +904,7 @@ int __vma_adjust(struct vm_area_struct *vma, unsigned long start,
 		uprobe_mmap(insert);
 	}
 
+	mas_destroy(&mas);
 	validate_mm(mm);
 
 	return 0;
Signature · 1 line
2.35.1