2.6.5-rc2-aa vma merging

2.6.5-rc2-aa vma merging

[Hugh Dickins]

Andrea,

Again I beg you to attend to vma merging in your anon_vma tree.
Still you have #if VMA_MERGING_FIXUP throughout mm/mprotect.c
(and much less seriously in mremap.c), and that's just masking
the real problem: that when you do enable vma merging there, your
anon_vmas will get in the way of merging in significant cases.

Try the example below, on mainline and on anonmm and on anon_vma,
even when you've done the VMA_MERGING_FIXUP: you're limited by the
MAX_MAP_COUNT of vmas, one per page.  Now, I know there's a move
afoot to have /proc/sys/vm/max_map_count tunable, but I don't
think that's the right answer for you ;)

If I remember rightly, Linus tried to do away with a lot of the
vma merging about three years ago, but some had to be reinstated.
So I assume that what's there is needed, and the example below
does looks plausible enough: add page, fill it, protect it, ...

How to fix this?  Clearly you could walk the pages, reassigning
their anon_vmas; but if you're reduced to doing that in the
common mprotect case, you're still worse off than anonmm which
only has to do it in the unusal mremap move case, while it has
to walk the pages anyway.

Until you can deal with this, I believe that the simpler
anonmm method in my anobjrmap patches does the job better:
less change, less overhead, more to the point.

Your anon_vma is good at connecting pages directly to their
vma groups in swapout, where my anonmm has to use find_vma (and
your anon_vma will fit more neatly with Andrew's vision of per-vma
spinlocks, where mine will probably need to down_read_trylock).

But the cost to vma merging seems too high.  And besides,
wasn't the point of this objrmap exercise, to move away from
the memory and processing load of pte_chains on the fast paths,
to using more cpu to solve it in the swapout paths?
anonmm does that better.

Hugh

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>

#define PAGE_SIZE	4096

int main(int argc, char *argv[])
{
	unsigned long *ptr;
	unsigned long pageno = 0;

	while (1) {
		ptr = mmap(NULL, PAGE_SIZE, PROT_READ|PROT_WRITE,
				MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
		if (ptr == MAP_FAILED) {
			fflush(stdout);
			perror("mmap");
			printf("Type <Return> to exit ");
			getchar();
			exit(1);
		}
		*ptr = pageno++;
		if (mprotect(ptr, PAGE_SIZE, PROT_READ) == -1) {
			fflush(stdout);
			perror("mprotect");
			printf("Type <Return> to exit ");
			getchar();
			exit(1);
		}
		printf("%7lu kB\n", (PAGE_SIZE/1024) * pageno);
	}
}

Re: 2.6.5-rc2-aa vma merging

[Hugh Dickins]

Sorry to be boring, Andrea, but 2.6.5-rc3-aa2 is now out, and you
have still not fixed the vma merging issue: I don't believe you can.

I realize you're very busy doing lots else, but you seem oddly
unaware that anon_vma is broken in this plausible scenario -
you've traded some common cases of anon vma merging for an
admirable solution to the mremap move shared anon issue;
but the latter is much too rare to justify that trade.

If I'm wrong, please show us all.  Take out the "*ptr = pageno++;"
below and, yes, I'm sure it's just a trivial matter of adding a
little code to mprotect.c and removing the #if VMA_MERGING_FIXUPs;
but actually writing data into the pages before protecting them
readonly (a reasonable thing to do) spoils it all - each page
gets its own vma with its own anon_vma preventing merge.

Whole mail from before repeated.  Yes, I read your reply: thank
you for giving us anon vma merging in 2.4.10 (so it's important?);
but checking Red Hat 2.4.9 variants (merge_anon_vmas) shows they
also needed it: so I don't think you can now take back what you gave.

Hugh

On Mon, 29 Mar 2004, Hugh Dickins wrote:

> Andrea,
> 
> Again I beg you to attend to vma merging in your anon_vma tree.
> Still you have #if VMA_MERGING_FIXUP throughout mm/mprotect.c
> (and much less seriously in mremap.c), and that's just masking
> the real problem: that when you do enable vma merging there, your
> anon_vmas will get in the way of merging in significant cases.
> 
> Try the example below, on mainline and on anonmm and on anon_vma,
> even when you've done the VMA_MERGING_FIXUP: you're limited by the
> MAX_MAP_COUNT of vmas, one per page.  Now, I know there's a move
> afoot to have /proc/sys/vm/max_map_count tunable, but I don't
> think that's the right answer for you ;)
> 
> If I remember rightly, Linus tried to do away with a lot of the
> vma merging about three years ago, but some had to be reinstated.
> So I assume that what's there is needed, and the example below
> does looks plausible enough: add page, fill it, protect it, ...
> 
> How to fix this?  Clearly you could walk the pages, reassigning
> their anon_vmas; but if you're reduced to doing that in the
> common mprotect case, you're still worse off than anonmm which
> only has to do it in the unusal mremap move case, while it has
> to walk the pages anyway.
> 
> Until you can deal with this, I believe that the simpler
> anonmm method in my anobjrmap patches does the job better:
> less change, less overhead, more to the point.
> 
> Your anon_vma is good at connecting pages directly to their
> vma groups in swapout, where my anonmm has to use find_vma (and
> your anon_vma will fit more neatly with Andrew's vision of per-vma
> spinlocks, where mine will probably need to down_read_trylock).
> 
> But the cost to vma merging seems too high.  And besides,
> wasn't the point of this objrmap exercise, to move away from
> the memory and processing load of pte_chains on the fast paths,
> to using more cpu to solve it in the swapout paths?
> anonmm does that better.
> 
> Hugh

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>

#define PAGE_SIZE	4096

int main(int argc, char *argv[])
{
	unsigned long *ptr;
	unsigned long pageno = 0;

	while (1) {
		ptr = mmap(NULL, PAGE_SIZE, PROT_READ|PROT_WRITE,
				MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
		if (ptr == MAP_FAILED) {
			fflush(stdout);
			perror("mmap");
			printf("Type <Return> to exit ");
			getchar();
			exit(1);
		}
		*ptr = pageno++;
		if (mprotect(ptr, PAGE_SIZE, PROT_READ) == -1) {
			fflush(stdout);
			perror("mprotect");
			printf("Type <Return> to exit ");
			getchar();
			exit(1);
		}
		printf("%7lu kB\n", (PAGE_SIZE/1024) * pageno);
	}
}

Re: 2.6.5-rc2-aa vma merging

[Andrea Arcangeli]

On Fri, Apr 02, 2004 at 12:34:29PM +0100, Hugh Dickins wrote:
> Sorry to be boring, Andrea, but 2.6.5-rc3-aa2 is now out, and you
> have still not fixed the vma merging issue: I don't believe you can.

Hugh, it will get fixed perfectly, so please give me the time to fix
swap suspend, then I can care about minor issues.

Swap suspend now works, swap resume is still broken and I cannot yet
care about mprotect, after I fixed swapsuspend (and swap resume) I will
be allowed to spend time on non-blocker bugs. I promise mprotect will
merge perfectly your testcase without any problem a few days after swap
suspend and swap resume works.

anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrea Arcangeli]

On Fri, Apr 02, 2004 at 05:35:22PM +0200, Andrea Arcangeli wrote:
> On Fri, Apr 02, 2004 at 12:34:29PM +0100, Hugh Dickins wrote:
> > Sorry to be boring, Andrea, but 2.6.5-rc3-aa2 is now out, and you
> > have still not fixed the vma merging issue: I don't believe you can.
> 
> Hugh, it will get fixed perfectly, so please give me the time to fix
> swap suspend, then I can care about minor issues.

here we go with the mprotect merging, try this on top of 2.6.5-rc3-aa2.

Your testcase output:

[..]
 981140 kB
 981144 kB
 981148 kB
 981152 kB
 981156 kB
 981160 kB
 981164 kB
 981168 kB
 981172 kB
 981176 kB
 981180 kB
 981184 kB
 981188 kB
 981192 kB
 981196 kB

hanging now in a oom condition (it's 1G box) because I had no swap
(looks like the VM is totally broken w/o swap, nothing gets killed in a
obvious oom scenario that would be resolved by the 2.4 vm in a second [I
mean, without swap!], anyways I could break it with C^c after waiting
half a minute with some faith in the vm not being completely locked up
w/o swap).

Now I did mkswap /dev/sda1 and swapon -a, so I'll try again now with
swap (it didn't get swap because a previous swap-restore crashed).

2095720 kB
2095724 kB
2095728 kB
2095732 kB
2095736 kB
2095740 kB
2095744 kB
2095748 kB
2095752 kB
2095756 kB
2095760 kB
2095764 kB
2095768 kB
2095772 kB
2095776 kB
2095780 kB
2095784 kB
2095788 kB
2095792 kB
2095796 kB
2095800 kB
2095804 kB
2095808 kB
2095812 kB
mmap: Cannot allocate memory
Type <Return> to exit
xeon:~ # 

it worked better this time after some swap, the oom was because the
address space was finished.

I run it another time stopping it in the middle to verify the number of
mappings and the merging:

[..]
 1315 pts/0    T      0:03 ./mprotect-merge
 1316 pts/0    R      0:00 ps x
xeon:~ # cat /proc/1315/maps 
08048000-08049000 r-xp 00000000 08:02 611014     /root/mprotect-merge
08049000-0804a000 rw-p 00000000 08:02 611014     /root/mprotect-merge
40000000-40014000 r-xp 00000000 08:02 443256     /lib/ld-2.3.2.so
40014000-40015000 rw-p 00014000 08:02 443256     /lib/ld-2.3.2.so
40015000-40016000 r--p 40015000 00:00 0 
40016000-40017000 rw-p 40016000 00:00 0 
40017000-40028000 r--p 40017000 00:00 0 
40028000-40157000 r-xp 00000000 08:02 443262     /lib/libc.so.6
40157000-4015b000 rw-p 0012f000 08:02 443262     /lib/libc.so.6
4015b000-4015e000 rw-p 4015b000 00:00 0 
4015e000-6f80d000 r--p 4015e000 00:00 0 
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1 vma for all
bfffd000-c0000000 rwxp bfffd000 00:00 0 
ffffe000-fffff000 ---p 00000000 00:00 0 
xeon:~ # 

here the last seconds of swapout before I press the key to exit after
the address space is finished:

 1  3 1101252   9860    740   5280    0 33224     0 33228 2231  2193  3  8  8 80
 4  1 1120564   4360    744   5368  340 18960   476 19164 1730  3866  2  8 44 45
 0  0 1143692   6220    588   4544   88 23912   156 23912 2820  2160  1  5 54 41
 0  0 1143692   6296    588   4544    0    0     0     0 1064    23  0  0 100  0
 0  0 1143692   6296    596   4536    0    0     0    32 1008    37  0  0 100  0
 0  0 1143692   6296    596   4536    0    0     0     0 1004    27  0  0 100  0
 0  0 1143692   6308    596   4536    0    0     0     0 1005    29  0  0 100  0
 0  0 1143692   6308    596   4536    0    0     0     0 1004    31  0  0 100  0
 0  0 1143692   6308    596   4536    0    0     0     0 1005    29  0  0 100  0
 0  0 1143692   6308    596   4536    0    0     0     0 1004    31  0  0 100  0
 0  0 1143692   6388    596   4536    0    0     0     0 1005    33  0  0 100  0
 0  0 1143692   6388    596   4536    0    0     0     0 1004    29  0  0 100  0
 0  0  13268 998296    596   4476  132    0   152     0 1023    59  0  7 92  1
 0  0  13268 998296    596   4476    0    0     0     0 1004    25  0  0 100  0
 0  0  13268 998336    612   4444   16    0    56     0 1013    51  0  0 99  1


Ok now that the basic testing is over and it's all running successful on the
test box I'll load the thing on my desktop. Note: I will keep this at the very
end of my patchset (if you see it's also incremental with prio-tree) because
this is an add-on and it had zero testing yet, kernel is perfectly
stable even without this (partly new for file mappings) merging-feature.
I encountered no bugs while writing this. However I did some cleanup
in the process of creating some better helper API to use in common with
mmap.c.

Most important: now file mappings gets merged perfectly through mprotect
too (still untested though, but if anon-vma merging works file merging
will most certainly too), that has never been possible in any linux yet
(I believe this is more useful than the anon-vma merging infact, I know
some big app using mprotect on filebacked mappings).

The spinlocking is cleaned up as well, compared to mainline, now only
the mmap_sem semaphore (in write mode) protects the vma merging, no need
of page_table_lock spinlock anymore except while walking the pagetables.

--- x/include/linux/mm.h.~1~	2004-04-02 20:37:14.000000000 +0200
+++ x/include/linux/mm.h	2004-04-03 03:02:07.362304072 +0200
@@ -751,6 +751,7 @@ extern int do_munmap(struct mm_struct *,
 
 extern unsigned long do_brk(unsigned long, unsigned long);
 
+/* vma merging helpers */
 static inline void
 __vma_unlink(struct mm_struct *mm, struct vm_area_struct *vma,
 		struct vm_area_struct *prev)
@@ -761,14 +762,48 @@ __vma_unlink(struct mm_struct *mm, struc
 		mm->mmap_cache = prev;
 }
 
-static inline int
-can_vma_merge(struct vm_area_struct *vma, unsigned long vm_flags)
+extern void __remove_shared_vm_struct(struct vm_area_struct *, struct inode *,
+				      struct address_space *);
+
+/*
+ * If the vma has a ->close operation then the driver probably needs to release
+ * per-vma resources, so we don't attempt to merge those.
+ */
+#define VM_SPECIAL (VM_IO | VM_DONTCOPY | VM_DONTEXPAND | VM_RESERVED)
+
+static inline int is_mergeable_vma(struct vm_area_struct *vma,
+				   struct file *file,
+				   unsigned long vm_flags,
+				   unsigned long pgoff,
+				   anon_vma_t ** anon_vma_cache)
 {
-#ifdef CONFIG_MMU
-	if (!vma->vm_file && vma->vm_flags == vm_flags)
-		return 1;
-#endif
-	return 0;
+	if (vma->vm_ops && vma->vm_ops->close)
+		return 0;
+	if (vma->vm_file != file)
+		return 0;
+	if (vma->vm_pgoff != pgoff)
+		return 0;
+	if (vma->vm_private_data)
+		return 0;
+	if (vma->vm_flags != vm_flags) {
+		/*
+		 * If the only difference between two adiacent
+		 * vmas is the page protection we try to
+		 * share the same anon_vma to maximize the
+		 * merging in mprotect.
+		 */
+		if (anon_vma_cache && !*anon_vma_cache)
+			*anon_vma_cache = vma->anon_vma;
+		return 0;
+	}
+	return 1;
+}
+
+static inline int is_mergeable_anon_vma(struct vm_area_struct *prev,
+					struct vm_area_struct *next)
+{
+	return ((!next->anon_vma || !prev->anon_vma) ||
+		(next->anon_vma == prev->anon_vma));
 }
 
 /* filemap.c */
--- x/mm/mmap.c.~1~	2004-04-02 20:37:14.000000000 +0200
+++ x/mm/mmap.c	2004-04-03 02:59:15.959361280 +0200
@@ -74,7 +74,7 @@ EXPORT_SYMBOL(vm_committed_space);
 /*
  * Requires inode->i_mapping->i_shared_sem
  */
-static void
+void
 __remove_shared_vm_struct(struct vm_area_struct *vma, struct inode *inode,
 			  struct address_space * mapping)
 {
@@ -343,26 +343,6 @@ __insert_vm_struct(struct mm_struct * mm
 }
 
 /*
- * If the vma has a ->close operation then the driver probably needs to release
- * per-vma resources, so we don't attempt to merge those.
- */
-#define VM_SPECIAL (VM_IO | VM_DONTCOPY | VM_DONTEXPAND | VM_RESERVED)
-
-static inline int is_mergeable_vma(struct vm_area_struct *vma,
-			struct file *file, unsigned long vm_flags)
-{
-	if (vma->vm_ops && vma->vm_ops->close)
-		return 0;
-	if (vma->vm_file != file)
-		return 0;
-	if (vma->vm_flags != vm_flags)
-		return 0;
-	if (vma->vm_private_data)
-		return 0;
-	return 1;
-}
-
-/*
  * Return true if we can merge this (vm_flags,file,vm_pgoff,size)
  * in front of (at a lower virtual address and file offset than) the vma.
  *
@@ -373,26 +353,25 @@ static inline int is_mergeable_vma(struc
 static int
 can_vma_merge_before(struct vm_area_struct *prev,
 		     struct vm_area_struct *vma, unsigned long vm_flags,
-		     struct file *file, unsigned long vm_pgoff, unsigned long size)
+		     struct file *file, unsigned long vm_pgoff,
+		     anon_vma_t ** anon_vma_cache)
 {
-	if (is_mergeable_vma(vma, file, vm_flags))
-		if (vma->vm_pgoff == vm_pgoff + size) {
-			if (prev) {
-				/*
-				 * We can fill an hole only if the two
-				 * anonymous mappings are queued in the same
-				 * anon_vma, or if one of them is "direct"
-				 * and it can be queued in the existing
-				 * anon_vma.
-				 *
-				 * Must check this even if file != NULL
-				 * for MAP_PRIVATE mappings.
-				 */
-				return ((!vma->anon_vma || !prev->anon_vma) ||
-					(vma->anon_vma == prev->anon_vma));
-			}
-			return 1;
+	if (is_mergeable_vma(vma, file, vm_flags, vm_pgoff, anon_vma_cache)) {
+		if (prev) {
+			/*
+			 * We can fill an hole only if the two
+			 * anonymous mappings are queued in the same
+			 * anon_vma, or if one of them is "direct"
+			 * and it can be queued in the existing
+			 * anon_vma.
+			 *
+			 * Must check this even if file != NULL
+			 * for MAP_PRIVATE mappings.
+			 */
+			return is_mergeable_anon_vma(prev, vma);
 		}
+		return 1;
+	}
 	return 0;
 }
 
@@ -402,16 +381,11 @@ can_vma_merge_before(struct vm_area_stru
  */
 static int
 can_vma_merge_after(struct vm_area_struct *vma, unsigned long vm_flags,
-	struct file *file, unsigned long vm_pgoff)
+		    struct file *file, unsigned long vm_pgoff,
+		    anon_vma_t ** anon_vma_cache)
 {
-	if (is_mergeable_vma(vma, file, vm_flags)) {
-		unsigned long vma_size;
-
-		vma_size = (vma->vm_end - vma->vm_start) >> PAGE_SHIFT;
-		if (vma->vm_pgoff + vma_size == vm_pgoff)
-			return 1;
-	}
-	return 0;
+	unsigned long vma_size = (vma->vm_end - vma->vm_start) >> PAGE_SHIFT;
+	return is_mergeable_vma(vma, file, vm_flags, vm_pgoff - vma_size, anon_vma_cache);
 }
 
 /*
@@ -420,14 +394,15 @@ can_vma_merge_after(struct vm_area_struc
  * both (it neatly fills a hole).
  */
 static int vma_merge(struct mm_struct *mm, struct vm_area_struct *prev,
-			struct rb_node *rb_parent, unsigned long addr, 
-			unsigned long end, unsigned long vm_flags,
-			struct file *file, unsigned long pgoff)
+		     struct rb_node *rb_parent, unsigned long addr, 
+		     unsigned long end, unsigned long vm_flags,
+		     struct file *file, unsigned long pgoff,
+		     anon_vma_t ** anon_vma_cache)
 {
-	struct inode *inode = file ? file->f_dentry->d_inode : NULL;
-	struct address_space *mapping = file ? file->f_mapping : NULL;
+	struct inode *inode;
+	struct address_space *mapping;
 	struct semaphore *i_shared_sem;
-	struct prio_tree_root *root = NULL;
+	struct prio_tree_root *root;
 
 	/*
 	 * We later require that vma->vm_flags == vm_flags, so this tests
@@ -436,14 +411,24 @@ static int vma_merge(struct mm_struct *m
 	if (vm_flags & VM_SPECIAL)
 		return 0;
 
-	i_shared_sem = file ? &file->f_mapping->i_shared_sem : NULL;
+	/*
+	 * Only "root" and "inode" have to be NULL too if "file" is null,
+	 * however mapping and i_shared_sem would cause gcc to warn about
+	 * uninitialized usage so we set them to NULL too.
+	 */
+	inode = NULL;
+	root = NULL;
+	i_shared_sem = NULL;
+	mapping = NULL;
+	if (file) {
+		inode = file->f_dentry->d_inode;
+		mapping = file->f_mapping;
+		i_shared_sem = &mapping->i_shared_sem;
 
-	if (mapping) {
 		if (vm_flags & VM_SHARED) {
 			if (likely(!(vm_flags & VM_NONLINEAR)))
 				root = &mapping->i_mmap_shared;
-		}
-		else
+		} else
 			root = &mapping->i_mmap;
 	}
 
@@ -456,7 +441,7 @@ static int vma_merge(struct mm_struct *m
 	 * Can it merge with the predecessor?
 	 */
 	if (prev->vm_end == addr &&
-			can_vma_merge_after(prev, vm_flags, file, pgoff)) {
+	    can_vma_merge_after(prev, vm_flags, file, pgoff, anon_vma_cache)) {
 		struct vm_area_struct *next;
 
 		/*
@@ -465,8 +450,9 @@ static int vma_merge(struct mm_struct *m
 		next = prev->vm_next;
 		/* next cannot change under us, it's serialized by the mmap_sem */
 		if (next && end == next->vm_start &&
-				can_vma_merge_before(prev, next, vm_flags, file,
-					pgoff, (end - addr) >> PAGE_SHIFT)) {
+		    can_vma_merge_before(prev, next, vm_flags, file,
+					 pgoff + ((end - addr) >> PAGE_SHIFT),
+					 anon_vma_cache)) {
 			/* serialized by the mmap_sem */
 			__vma_unlink(mm, next, prev);
 
@@ -516,10 +502,10 @@ static int vma_merge(struct mm_struct *m
 	prev = prev->vm_next;
 	if (prev) {
  merge_next:
-		if (!can_vma_merge_before(NULL, prev, vm_flags, file,
-				pgoff, (end - addr) >> PAGE_SHIFT))
-			return 0;
-		if (end == prev->vm_start) {
+		if (end == prev->vm_start &&
+		    can_vma_merge_before(NULL, prev, vm_flags, file,
+					 pgoff + ((end - addr) >> PAGE_SHIFT),
+					 anon_vma_cache)) {
 			if (file)
 				down(i_shared_sem);
 			anon_vma_lock(prev);
@@ -551,6 +537,7 @@ unsigned long do_mmap_pgoff(struct file 
 	int error;
 	struct rb_node ** rb_link, * rb_parent;
 	unsigned long charged = 0;
+	anon_vma_t * anon_vma_cache;
 
 	if (file) {
 		if (!file->f_op || !file->f_op->mmap)
@@ -686,9 +673,10 @@ munmap_back:
 	}
 
 	/* Can we just expand an old anonymous mapping? */
+	anon_vma_cache = NULL;
 	if (!file && !(vm_flags & VM_SHARED) && rb_parent)
 		if (vma_merge(mm, prev, rb_parent, addr, addr + len,
-					vm_flags, NULL, pgoff))
+					vm_flags, NULL, pgoff, &anon_vma_cache))
 			goto out;
 
 	/*
@@ -712,7 +700,6 @@ munmap_back:
 	vma->vm_private_data = NULL;
 	vma->vm_next = NULL;
 	INIT_VMA_SHARED(vma);
-	vma->anon_vma = NULL;
 
 	if (file) {
 		error = -EINVAL;
@@ -751,7 +738,9 @@ munmap_back:
 	addr = vma->vm_start;
 
 	if (!file || !rb_parent || !vma_merge(mm, prev, rb_parent, addr,
-				addr + len, vma->vm_flags, file, pgoff)) {
+					      addr + len, vma->vm_flags, file, pgoff,
+					      &anon_vma_cache)) {
+		vma->anon_vma = anon_vma_cache;
 		vma_link(mm, vma, prev, rb_link, rb_parent);
 		if (correct_wcount)
 			atomic_inc(&inode->i_writecount);
@@ -1409,6 +1398,7 @@ unsigned long do_brk(unsigned long addr,
 	unsigned long flags;
 	struct rb_node ** rb_link, * rb_parent;
 	unsigned long pgoff;
+	anon_vma_t * anon_vma_cache;
 
 	len = PAGE_ALIGN(len);
 	if (!len)
@@ -1454,8 +1444,9 @@ unsigned long do_brk(unsigned long addr,
 	pgoff = addr >> PAGE_SHIFT;
 
 	/* Can we just expand an old anonymous mapping? */
+	anon_vma_cache = NULL;
 	if (rb_parent && vma_merge(mm, prev, rb_parent, addr, addr + len,
-					flags, NULL, pgoff))
+				   flags, NULL, pgoff, &anon_vma_cache))
 		goto out;
 
 	/*
@@ -1477,7 +1468,7 @@ unsigned long do_brk(unsigned long addr,
 	vma->vm_file = NULL;
 	vma->vm_private_data = NULL;
 	INIT_VMA_SHARED(vma);
-	vma->anon_vma = NULL;
+	vma->anon_vma = anon_vma_cache;
 
 	vma_link(mm, vma, prev, rb_link, rb_parent);
 
--- x/mm/fremap.c.~1~	2004-04-02 20:37:14.000000000 +0200
+++ x/mm/fremap.c	2004-04-02 20:51:11.873652616 +0200
@@ -61,9 +61,8 @@ int install_page(struct mm_struct *mm, s
 	pmd_t *pmd;
 	pte_t pte_val;
 
-	spin_lock(&mm->page_table_lock);
 	pgd = pgd_offset(mm, addr);
-
+	spin_lock(&mm->page_table_lock);
 	pmd = pmd_alloc(mm, pgd, addr);
 	if (!pmd)
 		goto err_unlock;
@@ -103,9 +102,8 @@ int install_file_pte(struct mm_struct *m
 	pmd_t *pmd;
 	pte_t pte_val;
 
-	spin_lock(&mm->page_table_lock);
 	pgd = pgd_offset(mm, addr);
-
+	spin_lock(&mm->page_table_lock);
 	pmd = pmd_alloc(mm, pgd, addr);
 	if (!pmd)
 		goto err_unlock;
--- x/mm/mprotect.c.~1~	2004-04-02 20:37:13.928039712 +0200
+++ x/mm/mprotect.c	2004-04-03 01:46:44.987809496 +0200
@@ -16,6 +16,8 @@
 #include <linux/fs.h>
 #include <linux/highmem.h>
 #include <linux/security.h>
+#include <linux/objrmap.h>
+#include <linux/file.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgalloc.h>
@@ -107,7 +109,6 @@ change_protection(struct vm_area_struct 
 	return;
 }
 
-#if VMA_MERGING_FIXUP
 /*
  * Try to merge a vma with the previous flag, return 1 if successful or 0 if it
  * was impossible.
@@ -116,42 +117,174 @@ static int
 mprotect_attempt_merge(struct vm_area_struct *vma, struct vm_area_struct *prev,
 		unsigned long end, int newflags)
 {
-	struct mm_struct * mm = vma->vm_mm;
+	unsigned long prev_pgoff;
+	struct file *file;
+	struct inode *inode;
+	struct address_space *mapping;
+	struct semaphore *i_shared_sem;
+	struct prio_tree_root *root;
 
-	if (!prev || !vma)
+	if (newflags & VM_SPECIAL)
+		return 0;
+	if (!prev)
 		return 0;
 	if (prev->vm_end != vma->vm_start)
 		return 0;
-	if (!can_vma_merge(prev, newflags))
+
+	prev_pgoff = vma->vm_pgoff - ((prev->vm_end - prev->vm_start) >> PAGE_SHIFT);
+	file = vma->vm_file;
+	if (!is_mergeable_vma(prev, file, newflags, prev_pgoff, NULL))
 		return 0;
-	if (vma->vm_file || (vma->vm_flags & VM_SHARED))
+	if (!is_mergeable_anon_vma(prev, vma))
 		return 0;
 
 	/*
+	 * Only "root" and "inode" have to be NULL too if "file" is null,
+	 * however mapping and i_shared_sem would cause gcc to warn about
+	 * uninitialized usage so we set them to NULL too.
+	 */
+	inode = NULL;
+	root = NULL;
+	i_shared_sem = NULL;
+	mapping = NULL;
+	if (file) {
+		inode = file->f_dentry->d_inode;
+		mapping = file->f_mapping;
+		i_shared_sem = &mapping->i_shared_sem;
+
+		if (vma->vm_flags & VM_SHARED) {
+			if (likely(!(vma->vm_flags & VM_NONLINEAR)))
+				root = &mapping->i_mmap_shared;
+		} else
+			root = &mapping->i_mmap;
+	}
+
+	/*
 	 * If the whole area changes to the protection of the previous one
 	 * we can just get rid of it.
 	 */
 	if (end == vma->vm_end) {
-		spin_lock(&mm->page_table_lock);
-		prev->vm_end = end;
+		struct mm_struct * mm = vma->vm_mm;
+
+		/* serialized by the mmap_sem */
 		__vma_unlink(mm, vma, prev);
-		spin_unlock(&mm->page_table_lock);
 
-		kmem_cache_free(vm_area_cachep, vma);
+		if (file)
+			down(i_shared_sem);
+		__vma_modify(root, prev, prev->vm_start,
+			     end, prev->vm_pgoff);
+
+		__remove_shared_vm_struct(vma, inode, mapping);
+		if (file)
+			up(i_shared_sem);
+
+		/*
+		 * The anon_vma_lock is taken inside and
+		 * we can race with the vm_end move on the right,
+		 * that will not be a problem, moves on the right
+		 * of vm_end are controlled races.
+		 */
+		anon_vma_merge(prev, vma);
+
+		if (file)
+			fput(file);
+
 		mm->map_count--;
+		kmem_cache_free(vm_area_cachep, vma);
 		return 1;
 	} 
 
 	/*
 	 * Otherwise extend it.
 	 */
-	spin_lock(&mm->page_table_lock);
-	prev->vm_end = end;
-	vma->vm_start = end;
-	spin_unlock(&mm->page_table_lock);
+	if (file)
+		down(i_shared_sem);
+	__vma_modify(root, prev, prev->vm_start, end, prev->vm_pgoff);
+	__vma_modify(root, vma, end, vma->vm_end,
+		     vma->vm_pgoff + ((end - vma->vm_start) >> PAGE_SHIFT));
+	if (file)
+		up(i_shared_sem);
 	return 1;
 }
-#endif
+
+static void
+mprotect_attempt_merge_final(struct vm_area_struct *prev,
+			     struct vm_area_struct *next)
+{
+	unsigned long next_pgoff;
+	struct file * file;
+	struct inode *inode;
+	struct address_space *mapping;
+	struct semaphore *i_shared_sem;
+	struct prio_tree_root *root;
+	struct mm_struct * mm;
+	unsigned int newflags;
+
+	if (!next)
+		return;
+	if (prev->vm_end != next->vm_start)
+		return;
+	newflags = prev->vm_flags;
+	if (newflags & VM_SPECIAL)
+		return;
+
+	next_pgoff = prev->vm_pgoff + ((prev->vm_end - prev->vm_start) >> PAGE_SHIFT);
+	file = prev->vm_file;
+	if (!is_mergeable_vma(next, file, newflags, next_pgoff, NULL))
+		return;
+	if (!is_mergeable_anon_vma(prev, next))
+		return;
+
+
+	/*
+	 * Only "root" and "inode" have to be NULL too if "file" is null,
+	 * however mapping and i_shared_sem would cause gcc to warn about
+	 * uninitialized usage so we set them to NULL too.
+	 */
+	inode = NULL;
+	root = NULL;
+	i_shared_sem = NULL;
+	mapping = NULL;
+	if (file) {
+		inode = file->f_dentry->d_inode;
+		mapping = file->f_mapping;
+		i_shared_sem = &mapping->i_shared_sem;
+
+		if (next->vm_flags & VM_SHARED) {
+			if (likely(!(next->vm_flags & VM_NONLINEAR)))
+				root = &mapping->i_mmap_shared;
+		} else
+			root = &mapping->i_mmap;
+	}
+
+	mm = next->vm_mm;
+
+	/* serialized by the mmap_sem */
+	__vma_unlink(mm, next, prev);
+
+	if (file)
+		down(i_shared_sem);
+	__vma_modify(root, prev, prev->vm_start,
+		     next->vm_end, prev->vm_pgoff);
+
+	__remove_shared_vm_struct(next, inode, mapping);
+	if (file)
+		up(i_shared_sem);
+
+	/*
+	 * The anon_vma_lock is taken inside and
+	 * we can race with the vm_end move on the right,
+	 * that will not be a problem, moves on the right
+	 * of vm_end are controlled races.
+	 */
+	anon_vma_merge(prev, next);
+
+	if (file)
+		fput(file);
+
+	mm->map_count--;
+	kmem_cache_free(vm_area_cachep, next);
+}
 
 static int
 mprotect_fixup(struct vm_area_struct *vma, struct vm_area_struct **pprev,
@@ -187,7 +320,6 @@ mprotect_fixup(struct vm_area_struct *vm
 	newprot = protection_map[newflags & 0xf];
 
 	if (start == vma->vm_start) {
-#if VMA_MERGING_FIXUP
 		/*
 		 * Try to merge with the previous vma.
 		 */
@@ -195,7 +327,6 @@ mprotect_fixup(struct vm_area_struct *vm
 			vma = *pprev;
 			goto success;
 		}
-#endif
 	} else {
 		error = split_vma(mm, vma, start, 1);
 		if (error)
@@ -213,13 +344,13 @@ mprotect_fixup(struct vm_area_struct *vm
 			goto fail;
 	}
 
-	spin_lock(&mm->page_table_lock);
+	/*
+	 * vm_flags and vm_page_prot are protected by the mmap_sem
+	 * hold in write mode.
+	 */
 	vma->vm_flags = newflags;
 	vma->vm_page_prot = newprot;
-	spin_unlock(&mm->page_table_lock);
-#if VMA_MERGING_FIXUP
 success:
-#endif
 	change_protection(vma, start, end, newprot);
 	return 0;
 
@@ -321,19 +452,7 @@ sys_mprotect(unsigned long start, size_t
 		}
 	}
 
-#if VMA_MERGING_FIXUP
-	if (next && prev->vm_end == next->vm_start &&
-			can_vma_merge(next, prev->vm_flags) &&
-			!prev->vm_file && !(prev->vm_flags & VM_SHARED)) {
-		spin_lock(&prev->vm_mm->page_table_lock);
-		prev->vm_end = next->vm_end;
-		__vma_unlink(prev->vm_mm, next, prev);
-		spin_unlock(&prev->vm_mm->page_table_lock);
-
-		kmem_cache_free(vm_area_cachep, next);
-		prev->vm_mm->map_count--;
-	}
-#endif
+	mprotect_attempt_merge_final(prev, next);
 out:
 	up_write(&current->mm->mmap_sem);
 	return error;

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Hugh Dickins]

On Sat, 3 Apr 2004, Andrea Arcangeli wrote:
> On Fri, Apr 02, 2004 at 12:34:29PM +0100, Hugh Dickins wrote:
> > Sorry to be boring, Andrea, but 2.6.5-rc3-aa2 is now out, and you
> > have still not fixed the vma merging issue: I don't believe you can.
> 
> here we go with the mprotect merging, try this on top of 2.6.5-rc3-aa2.

Thank you!  It works.  You've surprised me again.  Forgive me.

It's a bit erratic, test program below you'd expect to end up with one
vma of 4 pages at 0x80000000, whereas it ends up with one of 1 and one
of 3 (where mainline ends up with two of 2); but that's just an
implementation detail which obviously can be smoothed away later.
Presumably it should be looking to merge, or propagating anon_vma
to/from adjacent vma, somewhere else too.

It does look more complicated than I'd hoped, a lot of that coming from
the file-backed merging: which I like, but, we could have done it at
any point over the last couple of years if someone had a need for it.
Fair enough, you've discovered a need, at the same time that you have
to attend to vm_pgoff for anons, so it makes sense to do them together.

Do you realize that you could allocate just a single anon_vma to
the mm at fork time, for all the pure anon vmas created in it later?
And then no need for propagating anon_vma from adjacent vma, they'd
all have the right one already and be mergeable anyway.  But I think
you'll reject that on two grounds: you want to merge the file-backed
vmas as much as is reasonable, so you need the code anyway for them;
and you'd prefer your anon_vma lists to be as short as possible, to
minimize searching at page_referenced/try_to_unmap time.

Clearly there's a tension between keeping the anon_vma lists short,
and leaving the vmas mergable: it's natural that we should differ on
where to strike that balance, having come to it from opposite ends.

I still prefer my simpler anonmm solution (will post the prio tree
patch on top of it later this evening), but I don't see any good
reason now to oppose your anon_vma solution.  Let others decide.

Hugh

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>

#define PAGE_SIZE	4096
#define MAP_AREA	((void *) 0x80000000)

int main(int argc, char *argv[])
{
	unsigned long pageno = 0;
	unsigned long *ptr;
	char buf[40];

	ptr = mmap(MAP_AREA, 2*PAGE_SIZE, PROT_READ,
			MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
	if (ptr == MAP_FAILED)
		exit(1);
	ptr = mmap(MAP_AREA + 2*PAGE_SIZE, 2*PAGE_SIZE, PROT_READ|PROT_WRITE,
			MAP_PRIVATE|MAP_ANONYMOUS|MAP_FIXED, -1, 0);
	if (ptr == MAP_FAILED)
		exit(1);
	ptr = MAP_AREA;
	while (pageno < 4) {
		if (mprotect(ptr, PAGE_SIZE, PROT_READ|PROT_WRITE) == -1)
			exit(1);
		*ptr = pageno++;
		if (mprotect(ptr, PAGE_SIZE, PROT_READ) == -1)
			exit(1);
		ptr += PAGE_SIZE / sizeof(unsigned long);
	}
	sprintf(buf, "cat /proc/%d/maps", getpid());
	system(buf);
	exit(0);
}

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrea Arcangeli]

On Sat, Apr 03, 2004 at 06:06:49PM +0100, Hugh Dickins wrote:
> It does look more complicated than I'd hoped, a lot of that coming from
> the file-backed merging: which I like, but, we could have done it at
> any point over the last couple of years if someone had a need for it.
> Fair enough, you've discovered a need, at the same time that you have
> to attend to vm_pgoff for anons, so it makes sense to do them together.

the point is that *nobody* has a need for it, nor for the anonymous, nor
for the filebacked mappings. It's just an "optimization", not a real
need.

You're right it's not trivial, but as you can see 95% of the complexity
comes from the filebacked merging, the anon-vma merging adds up to 5% of
the complexity (i.e. calling is_mergeable_anon_vma before proceeding and
then calling anon_vma_merge while nuking the superflous vma).

> Do you realize that you could allocate just a single anon_vma to
> the mm at fork time, for all the pure anon vmas created in it later?
> And then no need for propagating anon_vma from adjacent vma, they'd
> all have the right one already and be mergeable anyway.  But I think
> you'll reject that on two grounds: you want to merge the file-backed
> vmas as much as is reasonable, so you need the code anyway for them;
> and you'd prefer your anon_vma lists to be as short as possible, to
> minimize searching at page_referenced/try_to_unmap time.
> 
> Clearly there's a tension between keeping the anon_vma lists short,
> and leaving the vmas mergable: it's natural that we should differ on
> where to strike that balance, having come to it from opposite ends.

exactly. the cost of the anonvmas is absolutely non measurable, so while
it makes sense to share the sane anon_vma for adiancent mappings that
differs only for the page protection flags, I don't want to share
anything else to boost the reverse lookup performance. I want it as
finegrined as possible, not just to have few vmas, but also to track
_only_ the interesting MM in the group, something anonmm will never be
able to do, except when the page has mapcount == 1. Sharing the same
anon_vma for everything would just slowdown the lookup, in practice
there would be no more merging at all. I believe being as finegrined as
possible will payoff, maybe one day we may even be ok to pay for some
more byte in the vma for a prio_tree on top of the anon_vma, to speedup
the lookup as much as possible (today it would only waste ram IMO). Plus
I love being able to handle mremap trasparently by-design. The ugliness
of doing a swapin + copy and calling handle_mm_fault in mremap is pretty
bad IMO. some more byte per-vma is not a problem and it'll never be
noticeable, just like not merging non adiacent mappings will never be
noticeable. So I believe the few bytes per vma are worth it, plus now it
does filebacked mprotect merging too.

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrea Arcangeli]

On Sat, Apr 03, 2004 at 07:24:26PM +0200, Andrea Arcangeli wrote:
> exactly. the cost of the anonvmas is absolutely non measurable, so while
> it makes sense to share the sane anon_vma for adiancent mappings that
> differs only for the page protection flags, I don't want to share
> anything else to boost the reverse lookup performance. I want it as
> finegrined as possible, not just to have few vmas, but also to track
> _only_ the interesting MM in the group, something anonmm will never be
> able to do, except when the page has mapcount == 1. Sharing the same
> anon_vma for everything would just slowdown the lookup, in practice
> there would be no more merging at all. I believe being as finegrined as
> possible will payoff, maybe one day we may even be ok to pay for some
> more byte in the vma for a prio_tree on top of the anon_vma, to speedup
> the lookup as much as possible (today it would only waste ram IMO). Plus
> I love being able to handle mremap trasparently by-design. The ugliness
> of doing a swapin + copy and calling handle_mm_fault in mremap is pretty
> bad IMO. some more byte per-vma is not a problem and it'll never be
> noticeable, just like not merging non adiacent mappings will never be
> noticeable. So I believe the few bytes per vma are worth it, plus now it
> does filebacked mprotect merging too.

another relevant advantage of anon-vma compared to anonmm, is the smp
locking scalability and simplicity. With anonmm you're either forced to
keep the mm-wide page_table_lock during vma merging and in general
during all vma modifications (so you can lookup the rbtree from
try_to_unmap by trylocking on the page_table_lock). While with anon-vma
the page_table_lock goes away completely from the vma merging and all
vma manipulations. page_table_lock remains but only for accessing the
pagetables.

btw, it's good I was thinking now at the locking since I noticed I
missed an anon_vma_lock here:

 	/*
 	 * Otherwise extend it.
 	 */
-	spin_lock(&mm->page_table_lock);
-	prev->vm_end = end;
-	vma->vm_start = end;
-	spin_unlock(&mm->page_table_lock);
+	if (file)
+		down(i_shared_sem);
+	__vma_modify(root, prev, prev->vm_start, end, prev->vm_pgoff);
+	__vma_modify(root, vma, end, vma->vm_end,
+		     vma->vm_pgoff + ((end - vma->vm_start) >>
PAGE_SHIFT));
+	if (file)
+		up(i_shared_sem);


it's really needed only for the "start" moves, the "end" moves can go
lockless, but adding an anon_vma_lock/unlock(vma) after the if (file)
down is simpler. The other modifications don't need it because they're
all extensions at the end (not at the start), so the smp race is controlled.

I'll recheck and fix it in next -aa tomorrow (it's unlikely anybody can
trigger it in the meantime ;)

About the ppc page->mapping stuff I don't think the ppc fixes in
anobjrmap are really going to fix anything, though that tlb.c code is
very confusing to me, not sure how can it work without it, but OTOH then
even mainline shouldn't work if that's needed. ppc help?

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Hugh Dickins]

On Sat, 3 Apr 2004, Andrea Arcangeli wrote:
> 
> another relevant advantage of anon-vma compared to anonmm, is the smp
> locking scalability and simplicity. With anonmm you're either forced to
> keep the mm-wide page_table_lock during vma merging and in general
> during all vma modifications (so you can lookup the rbtree from
> try_to_unmap by trylocking on the page_table_lock). While with anon-vma
> the page_table_lock goes away completely from the vma merging and all
> vma manipulations. page_table_lock remains but only for accessing the
> pagetables.

I liked Andrew's vma->page_table_lock suggestion, was imagining we
should migrate in that direction (as you said at the time, needn't
be right now), if only as a discipline to force us away from the
page_table_lock or mmap_sem muddle in (not your version of) mmap.c.

So I had been expecting to shift anonmm in that direction,
needing to do a down_read_trylock around its anon find_vma.

By the way, your and my page_referenced_one do need to take
page_table_lock, but the need for it is very very slender: Dave
took it out a year ago, I persuaded him it had to go back in,
but there's probably some way we can avoid it later on.

> About the ppc page->mapping stuff I don't think the ppc fixes in
> anobjrmap are really going to fix anything, though that tlb.c code is
> very confusing to me, not sure how can it work without it, but OTOH then
> even mainline shouldn't work if that's needed. ppc help?

I just translated what was there before: I thought I could understand
why it did that on user page tables, but I couldn't understand why it
did it to all the kernel page tables too.

I believe it's related to the fact that page_referenced_one does not
flush TLB after ptep_test_and_clear_referenced: so MMU may not notice
that we have cleared it, and not set it again even though referenced;
so pages referenced very frequently may be treated as unreferenced.
We ought to flush TLB there, but I presume it's been thought
to waste more time than its worth (particularly across cpus).
Probably depends rather on architecture, hence the ppc code.

Hugh

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrea Arcangeli]

On Sat, Apr 03, 2004 at 08:29:15PM +0100, Hugh Dickins wrote:
> I liked Andrew's vma->page_table_lock suggestion, was imagining we

vma->page_table_lock cannot help you with anonmm, the rbtree is global,
for that you still need a mm-wide lock with anonmm. I serialize
read/write the rbtree only with the mmap_sem, you cannot.

vma->page_table_lock helps _only_ in the pagetable scanning: so only
_after_ nuking the global page_table_lock like I can do thanks to
anon_vma. you cannot drop the mm-wide page_table_lock with anonmm.
vma->page_table_lock is a natural optimization for the anon-vma logic
instead (after fixing the mremap/truncate race ;).

To drop the page_table_lock during vma manipulations in anonmm (and so
to give a real sense to a vma->page_table_lock in anonmm) you could use
a down_read_trylock on the mm->mmap_sem, but that is not going to work
well: the mmap_sem can be taken during extended period of times
involving I/O, and you may never get it. BTW, now that the lookup on the
prio-tree is immediate the i_shared_sem has no reason anymore to be a
semaphore either, it should go back to a spinlock like in 2.4, like the
anon_vma is also protected by a spinlock.

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrew Morton]

Andrea Arcangeli <andrea@suse.de> wrote:
>
> BTW, now that the lookup on the
>  prio-tree is immediate the i_shared_sem has no reason anymore to be a
>  semaphore either, it should go back to a spinlock like in 2.4, like the
>  anon_vma is also protected by a spinlock.

That change was made for scheduling latency reasons, mainly due to huge
pagetable walks in zap_page_range():

    i_shared_lock is held for a very long time during vmtruncate() and
    causes high scheduling latencies when truncating a file which is
    mmapped.  I've seen 100 milliseconds.

    So turn it into a semaphore.  It nests inside mmap_sem.  This
    change is also needed by the shared pagetable patch, which needs to
    unshare pte's on the vmtruncate path - lots of pagetable pages need to
    be allocated and they are using __GFP_WAIT.

If we no longer hold that lock during pte takedown then sure, it would
be better if we had a spinlock in there.

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrea Arcangeli]

On Sat, Apr 03, 2004 at 05:13:58PM -0800, Andrew Morton wrote:
> That change was made for scheduling latency reasons, mainly due to huge
> pagetable walks in zap_page_range():
> 
>     i_shared_lock is held for a very long time during vmtruncate() and
>     causes high scheduling latencies when truncating a file which is
>     mmapped.  I've seen 100 milliseconds.
> 
>     So turn it into a semaphore.  It nests inside mmap_sem.  This
>     change is also needed by the shared pagetable patch, which needs to
>     unshare pte's on the vmtruncate path - lots of pagetable pages need to
>     be allocated and they are using __GFP_WAIT.
> 
> If we no longer hold that lock during pte takedown then sure, it would
> be better if we had a spinlock in there.

agreed, vmtruncate may still be very costly due the pte scan, so
I was probably wrong about not needing the semaphore anymore with
prio-tree (I was too objrmap centric, and after all objrmap with the
trylocks threats it like a spinlock anyways), though the semaphore
cannot help the latency of the non-contention case (I mean with preempt
disabled), that seem to have room for improvements with a cond_sched()
before returning from invalidate_mmap_range_list not present yet.

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrew Morton]

Andrea Arcangeli <andrea@suse.de> wrote:
>
> On Sat, Apr 03, 2004 at 05:13:58PM -0800, Andrew Morton wrote:
> > That change was made for scheduling latency reasons, mainly due to huge
> > pagetable walks in zap_page_range():
> > 
> >     i_shared_lock is held for a very long time during vmtruncate() and
> >     causes high scheduling latencies when truncating a file which is
> >     mmapped.  I've seen 100 milliseconds.
> > 
> >     So turn it into a semaphore.  It nests inside mmap_sem.  This
> >     change is also needed by the shared pagetable patch, which needs to
> >     unshare pte's on the vmtruncate path - lots of pagetable pages need to
> >     be allocated and they are using __GFP_WAIT.
> > 
> > If we no longer hold that lock during pte takedown then sure, it would
> > be better if we had a spinlock in there.
> 
> agreed, vmtruncate may still be very costly due the pte scan, so
> I was probably wrong about not needing the semaphore anymore with
> prio-tree (I was too objrmap centric, and after all objrmap with the
> trylocks threats it like a spinlock anyways), though the semaphore
> cannot help the latency of the non-contention case (I mean with preempt
> disabled), that seem to have room for improvements with a cond_sched()
> before returning from invalidate_mmap_range_list not present yet.

<looks>

Actually I was a bit harsh to the !CONFIG_PREEMPT case in unmap_vmas():

/* No preempt: go for the best straight-line efficiency */
#if !defined(CONFIG_PREEMPT)
#define ZAP_BLOCK_SIZE	(~(0UL))
#endif

We should probably make that 1024*PAGE_SIZE or something like that.

truncate_inode_pages() does a cond_resched() every 16 pages irrespective of
CONFIG_PREEMPT.

Re: anon-vma (and now filebacked-mappings too) mprotect vma merging [Re: 2.6.5-rc2-aa vma merging]

[Andrea Arcangeli]

On Sat, Apr 03, 2004 at 05:43:12PM -0800, Andrew Morton wrote:
> Andrea Arcangeli <andrea@suse.de> wrote:
> >
> > On Sat, Apr 03, 2004 at 05:13:58PM -0800, Andrew Morton wrote:
> > > That change was made for scheduling latency reasons, mainly due to huge
> > > pagetable walks in zap_page_range():
> > > 
> > >     i_shared_lock is held for a very long time during vmtruncate() and
> > >     causes high scheduling latencies when truncating a file which is
> > >     mmapped.  I've seen 100 milliseconds.
> > > 
> > >     So turn it into a semaphore.  It nests inside mmap_sem.  This
> > >     change is also needed by the shared pagetable patch, which needs to
> > >     unshare pte's on the vmtruncate path - lots of pagetable pages need to
> > >     be allocated and they are using __GFP_WAIT.
> > > 
> > > If we no longer hold that lock during pte takedown then sure, it would
> > > be better if we had a spinlock in there.
> > 
> > agreed, vmtruncate may still be very costly due the pte scan, so
> > I was probably wrong about not needing the semaphore anymore with
> > prio-tree (I was too objrmap centric, and after all objrmap with the
> > trylocks threats it like a spinlock anyways), though the semaphore
> > cannot help the latency of the non-contention case (I mean with preempt
> > disabled), that seem to have room for improvements with a cond_sched()
> > before returning from invalidate_mmap_range_list not present yet.
> 
> <looks>

ok so it's implemented already, actually w/o prio-tree you'd waste some
cpu w/o schedule points if all vmas are out of range, with prio-tree
that's fixed.

> 
> Actually I was a bit harsh to the !CONFIG_PREEMPT case in unmap_vmas():
> 
> /* No preempt: go for the best straight-line efficiency */
> #if !defined(CONFIG_PREEMPT)
> #define ZAP_BLOCK_SIZE	(~(0UL))
> #endif
> 
> We should probably make that 1024*PAGE_SIZE or something like that.

agreed, more specifically we shouldn't differentiate the preempt from
non-preempt case, I'd suggest removing those CONFIG_PREEMPT there, it's
a misconception to think people disabling preempt cares about worst case
latencies less than people enabling preempt, infact the people disabling
preempt _only_ cares about the worst case latency ;)