[PATCH] final merging patch -- significant mozilla speedup.

[PATCH] final merging patch -- significant mozilla speedup.

[Ben LaHaise]

Hello again,

This should be the final variant of the vma merging patch: it does tail
merging for mmap and runs the same code after an mprotect syscall via the
merge_anon_vmas and attempt_merge_next functions.  This also includes a
fix to the mremap merging to avoid merge attempts on non-private mappings.
All told, mozilla now uses ~220 vmas for a few quick page loads that would
previously reach ~1650 vmas or more.  This really boosts the speed of
mozilla -- give it a try!  Patch is against 2.4.9 and applies cleanly to
2.4.8-ac5 too.

		-ben

.... v2.4.9-merge-full.diff
diff -urN /md0/kernels/2.4/v2.4.9/include/linux/mm.h foo/include/linux/mm.h
--- /md0/kernels/2.4/v2.4.9/include/linux/mm.h	Tue Aug  7 17:52:06 2001
+++ foo/include/linux/mm.h	Thu Aug 16 16:59:34 2001
@@ -515,6 +515,7 @@
 extern int do_munmap(struct mm_struct *, unsigned long, size_t);

 extern unsigned long do_brk(unsigned long, unsigned long);
+extern void merge_anon_vmas(struct mm_struct *mm, unsigned long start, unsigned long end);

 struct zone_t;
 /* filemap.c */
diff -urN /md0/kernels/2.4/v2.4.9/mm/mmap.c foo/mm/mmap.c
--- /md0/kernels/2.4/v2.4.9/mm/mmap.c	Fri May 25 22:48:10 2001
+++ foo/mm/mmap.c	Thu Aug 16 16:59:35 2001
@@ -17,6 +17,8 @@
 #include <asm/uaccess.h>
 #include <asm/pgalloc.h>

+static inline void attempt_merge_next(struct mm_struct *mm, struct vm_area_struct *vma);
+
 /* description of effects of mapping type and prot in current implementation.
  * this is due to the limited x86 page protection hardware.  The expected
  * behavior is in parens:
@@ -309,7 +311,7 @@

 	/* Can we just expand an old anonymous mapping? */
 	if (addr && !file && !(vm_flags & VM_SHARED)) {
-		struct vm_area_struct * vma = find_vma(mm, addr-1);
+		vma = find_vma(mm, addr-1);
 		if (vma && vma->vm_end == addr && !vma->vm_file &&
 		    vma->vm_flags == vm_flags) {
 			vma->vm_end = addr + len;
@@ -365,12 +367,17 @@
 	if (correct_wcount)
 		atomic_inc(&file->f_dentry->d_inode->i_writecount);

-out:
+out:
 	mm->total_vm += len >> PAGE_SHIFT;
 	if (vm_flags & VM_LOCKED) {
 		mm->locked_vm += len >> PAGE_SHIFT;
 		make_pages_present(addr, addr + len);
 	}
+
+	/* Can we merge this anonymous mapping with the one following it? */
+	if (!file && !(vm_flags & VM_SHARED))
+		attempt_merge_next(mm, vma);
+
 	return addr;

 unmap_and_free_vma:
@@ -1004,4 +1011,34 @@
 	__insert_vm_struct(mm, vmp);
 	spin_unlock(&current->mm->page_table_lock);
 	unlock_vma_mappings(vmp);
+}
+
+static inline void attempt_merge_next(struct mm_struct *mm, struct vm_area_struct *vma)
+{
+	struct vm_area_struct *next = vma->vm_next;
+	if (next && vma->vm_end == next->vm_start && !next->vm_file &&
+	    vma->vm_flags == next->vm_flags) {
+		spin_lock(&mm->page_table_lock);
+		vma->vm_next = next->vm_next;
+		if (mm->mmap_avl)
+			avl_remove(next, &mm->mmap_avl);
+		vma->vm_end = next->vm_end;
+		mm->mmap_cache = vma;	/* Kill the cache. */
+		mm->map_count--;
+		spin_unlock(&mm->page_table_lock);
+
+		kmem_cache_free(vm_area_cachep, next);
+	}
+}
+
+void merge_anon_vmas(struct mm_struct *mm, unsigned long start, unsigned long end)
+{
+	struct vm_area_struct *vma;
+	if (start)
+		start--;
+
+	for (vma = find_vma(mm, start); vma && vma->vm_start <= end;
+	     vma = vma->vm_next)
+		if (!vma->vm_file && !(vma->vm_flags & VM_SHARED))
+			attempt_merge_next(mm, vma);
 }
diff -urN /md0/kernels/2.4/v2.4.9/mm/mprotect.c foo/mm/mprotect.c
--- /md0/kernels/2.4/v2.4.9/mm/mprotect.c	Thu Apr  5 11:53:46 2001
+++ foo/mm/mprotect.c	Thu Aug 16 16:59:35 2001
@@ -278,6 +278,7 @@
 			break;
 		}
 	}
+	merge_anon_vmas(current->mm, start, end);
 out:
 	up_write(&current->mm->mmap_sem);
 	return error;
diff -urN /md0/kernels/2.4/v2.4.9/mm/mremap.c foo/mm/mremap.c
--- /md0/kernels/2.4/v2.4.9/mm/mremap.c	Thu May  3 11:22:20 2001
+++ foo/mm/mremap.c	Thu Aug 16 16:59:35 2001
@@ -128,10 +128,23 @@
 	unsigned long new_addr)
 {
 	struct vm_area_struct * new_vma;
+	int allocated_vma = 0;

-	new_vma = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
-	if (new_vma) {
-		if (!move_page_tables(current->mm, new_addr, addr, old_len)) {
+	/* First, check if we can merge a mapping. -ben */
+	new_vma = find_vma(current->mm, new_addr-1);
+	if (new_vma && !vma->vm_file && !(vma->vm_flags & VM_SHARED) &&
+	    new_vma->vm_end == new_addr && !new_vma->vm_file &&
+		new_vma->vm_flags == vma->vm_flags) {
+		new_vma->vm_end = new_addr + new_len;
+	} else {
+		new_vma = kmem_cache_alloc(vm_area_cachep, SLAB_KERNEL);
+		if (!new_vma)
+			goto no_mem;
+		allocated_vma = 1;
+	}
+
+	if (!move_page_tables(current->mm, new_addr, addr, old_len)) {
+		if (allocated_vma) {
 			*new_vma = *vma;
 			new_vma->vm_start = new_addr;
 			new_vma->vm_end = new_addr+new_len;
@@ -142,17 +155,20 @@
 			if (new_vma->vm_ops && new_vma->vm_ops->open)
 				new_vma->vm_ops->open(new_vma);
 			insert_vm_struct(current->mm, new_vma);
-			do_munmap(current->mm, addr, old_len);
-			current->mm->total_vm += new_len >> PAGE_SHIFT;
-			if (new_vma->vm_flags & VM_LOCKED) {
-				current->mm->locked_vm += new_len >> PAGE_SHIFT;
-				make_pages_present(new_vma->vm_start,
-						   new_vma->vm_end);
-			}
-			return new_addr;
 		}
-		kmem_cache_free(vm_area_cachep, new_vma);
+		do_munmap(current->mm, addr, old_len);
+		current->mm->total_vm += new_len >> PAGE_SHIFT;
+		if (new_vma->vm_flags & VM_LOCKED) {
+			current->mm->locked_vm += new_len >> PAGE_SHIFT;
+			make_pages_present(new_vma->vm_start,
+					   new_vma->vm_end);
+		}
+		return new_addr;
 	}
+	if (allocated_vma)
+		kmem_cache_free(vm_area_cachep, new_vma);
+
+no_mem:
 	return -ENOMEM;
 }


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Ben LaHaise]

It appears that whitespace was mangled.  Here's a resend of the patch,
uuencoded.

		-ben

begin 644 v2.4.9-merge-full.diff.gz
M'XL(`(<T?#L"`[57;5/;1A#^+/^*[72&,<BR+8,-,<&%IM!V$I).PO2K1DAG
MHZ*3--()0S+\]^[NG63+;Y"^>#S6Z6YO;^_9M\=A-)V"4^8?H2?#?N]>Y(F(
MB]Z@>]1[P)_NFUZ4!'$9BEX<)>5C3\KN'4S3=,-TRW&<[]!BW90"+LH9P#&X
MQ^/A8-P?P:#?=UNV;6\YPKJY*WF/.\+O>/AF?'BD]YR?@S-TAYT1V/0XAO/S
M%HA'A99`E"@(4T^6B?2S=J'R,E`@I6=&!QTHDR*:)2*$.$UF'2BBK\)3^Z<M
MJ'4T)$C;;7[?7MG6>,7=MMG[D$8A2)'/A.<G:>(]2+_88(:4*RJ@4'ZN5B=%
M$FK+S+ZO:8+&XDSO`*91+/".W0`.>JWP1==*B5\6)[CKMYV.K*6LJSR":_\)
M!D,8#,9')V.WW_3?0G3=;<.%V]QC\AK^GK#3?C1NA[=^(7NE'P2B*+IWD]65
M;.;'<1KP2LM&J%04H*LQ6(1&W%=*R$QY&OD$G;$%=#-^D)Z?"[]>0C>1$QG8
M4!1!'F4J2A-(IR"F4Q&H@H9XP2Q"MZBG3("?A)#EJ4([("CS7&#D13)#I^#(
MI]W=%L`!J+NH`/R&F`(JQ5<!<20CA3Y^/!E!YL\$Z\%#Z,0[/P_G:%L7X`9%
MQ6.&"R)D5;?BSG^(TIS4X:D9BB7%F($][+_!1+`/7=?D0PLLO,L[/X&Y@+_*
M0I$JLAEGTI@>:?(DT[*H;O43Q1%8T13:?ACFL+<'/U",\:"-@$UC?U;`'OQY
M[7WY[>+SY2_[^_"MY5C6%DQQPH<SC-,DI#1H$_RDV7$):LO:M0P6&T(B>#P^
MG`FJQW2`LS.HS:OF*S-I&^"GGF>+<4<U)H-1QFHHU/ILB$5RJK$<#3ON`,$<
M'7=<C29;$Z3HY4!Y\R`M$[5/FGR5RBCP,%C;>V2%,YEZ(?H_?W(F(4ZG(4Y%
MWCQ'?^M=E,Y.6JJQU;+I@5JD="8J57Z,.(!]1H;`9`)_7/QZB4C_?G5S:@QH
M.N'#IW?OT0GZ2J0#,^1>A+N46-*_%QZ%7.%EN2C04G9V9PD#1O\9<\%>"B#.
M*QW*:X$#\TC=<5QC=<)B@)DZI^E(<4C9;/J+H401L2&+*2KJY+1RH4HLLF0L
MET6N\EAH0V^:"T%AI+/![?>/.D=8:/J8#]@VV(4>^J,0N4(Q$Z-&>\97+O`N
M7ID0B.T]D]#.A'`EO#SEW\;"HU66UH)THF=@*-I:D\W8_4\UJF5_0Z"V")!*
M.*NCGUY/#?R\M)Y)-,WOW'W8/?54G53VYIQ:"%:9A1YD$#6$FY&S%\EGS*WU
M5/:RP;1;LG,?8HX-"P=>+F3Z(/@V'=AKR#14Z[RN->,K+]<;`C_`<&6H3BG*
MWT=QS!',"UT=MEJ<I"EQ'>>TOF`5)5NN2'+W4DA]#(=FN_(53V4=MHUM?C8!
M\]\3AYVQ0C<WL<$*&&,>\47Q;8I]IKVA1FOQ4UBIS3J"WIZ!`1M,T*P$Y'[E
MX+7B385A.<36JL/N\@#/KR1!IM<N$:%ZYD4R5$MJEI/E`$-PW?'P<'PT6B=$
M*^+;2-'@^(18$3U,M[&L6W36/9?L9UV.K=786"I1G2H(#%\T?:7,=.-9*6><
M`8607,=,115YGF))?1V"N6@22?/^(GI&CL$@,@F'A!WRR<$&,KDLO)U.#DXZ
MR$1M>@X.-7;-1$C$W*-V@=V:^N0VJD)B54H@CV.VZ2MNIA3!?>[:EI'"B:7T
M9MFU_/[RX>)G[_WEYX^7'Q!GQQ1AWFY8$R<!E3-O44)6O%H9K]MSAWB;1QU:
M%UNL6U=17J#;\<C@'E#AG"I88KJU7S7H+CBWR`:XJ"VN4"?UQB,-25LR>R/C
MVI6TN&[J@-'0[#SZ'--S%NM+;<=JS"^XG+_6=M8.6.BW><C<#HLM8%B*QI[O
M=V95P"IW<FV:I<CM$_SC*21+K$:0:VI]18?^C>,U1U\^H.*U!XM+Z0I/D\O@
MZ"J]@&==H@F?78/'Z78T($)LN\-A!W/6E*JE&&$-:5:0`U>FG$F:X0UXA[5Q
MK<X/;=0:65M#2,MB*EF+?_P-H29X6K11"I=9M[GI*FEV-MQP(PDGP:;V!A_?
MH7X3*U]S6D>+\A^<%7^9FSWSKRGH#0?SRLN,I$+4?C6@]O?C:;\23ON?H&F_
M&DQ[.Y:VQ?UV$Y+/)GV;R?<ZOE>CV[)UG1@OVJ]S^?'3]>4ULQAH_0VB:\=V
$J!,`````
`
end

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sat, Aug 18, 2001 at 02:22:12PM -0400, Ben LaHaise wrote:
> It appears that whitespace was mangled.  Here's a resend of the patch,
> uuencoded.

This below patch besides rewriting the vma lookup engine also covers the
cases addressed by your patch:

	ftp://ftp.kernel.org/pub/linux/kernel/people/andrea/patches/v2.4/2.4.9/mmap-rb-4

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Ben LaHaise]

On Sun, 19 Aug 2001, Andrea Arcangeli wrote:

> This below patch besides rewriting the vma lookup engine also covers the
> cases addressed by your patch:

Your patch performs a few odd things like:

+       vma->vm_raend = 0;
+       vma->vm_pgoff += (start - vma->vm_start) >> PAGE_SHIFT;
        lock_vma_mappings(vma);
        spin_lock(&vma->vm_mm->page_table_lock);
-       vma->vm_pgoff += (start - vma->vm_start) >> PAGE_SHIFT;

which I would argue are incorrect.  Remember that page faults rely on
page_table_lock to protect against the case where the stack is grown and
vm_start is modified.  Aside from that, your patch is a sufficiently large
change so as to be material for 2.5.  Also, have you instrumented the rb
trees to see what kind of an effect it has on performance compared to the
avl tree?

		-ben

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sat, Aug 18, 2001 at 08:10:50PM -0400, Ben LaHaise wrote:
> On Sun, 19 Aug 2001, Andrea Arcangeli wrote:
> 
> > This below patch besides rewriting the vma lookup engine also covers the
> > cases addressed by your patch:
> 
> Your patch performs a few odd things like:
> 
> +       vma->vm_raend = 0;
> +       vma->vm_pgoff += (start - vma->vm_start) >> PAGE_SHIFT;
>         lock_vma_mappings(vma);
>         spin_lock(&vma->vm_mm->page_table_lock);
> -       vma->vm_pgoff += (start - vma->vm_start) >> PAGE_SHIFT;
> 
> which I would argue are incorrect.  Remember that page faults rely on

vm_raend is obviously correct.

For the vm_pgoff I need to think more about it (quite frankly I never
thought about expand_stack(), I only thought about the swapper locking
while doing the "odd" change), if it's a bug I will release a corrected
mmap-rb-5 in a few hours.  Thanks for raising this issue.

> page_table_lock to protect against the case where the stack is grown and
> vm_start is modified.  Aside from that, your patch is a sufficiently large
> change so as to be material for 2.5.  Also, have you instrumented the rb

I'm not caring about 2.whatever here. However I will certainly try at
max to avoid any hack at this point even in 2.4 now that the rb works
apparently solid (AFIK as worse with a SMP race in vm_pgoff :).

> trees to see what kind of an effect it has on performance compared to the
> avl tree?

I posted some benchmark result a few minutes ago (the numbers says there
were no implementation bugs).

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Rik van Riel]

On Sun, 19 Aug 2001, Andrea Arcangeli wrote:
> On Sat, Aug 18, 2001 at 08:10:50PM -0400, Ben LaHaise wrote:

> > Your patch performs a few odd things like:
> >
> > +       vma->vm_raend = 0;
...
> > which I would argue are incorrect.  Remember that page faults rely on
>
> vm_raend is obviously correct.

Why ?

Rik
--
IA64: a worthy successor to i860.

http://www.surriel.com/		http://distro.conectiva.com/

Send all your spam to aardvark@nl.linux.org (spam digging piggy)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sun, Aug 19, 2001 at 02:35:48AM +0200, Andrea Arcangeli wrote:
> For the vm_pgoff I need to think more about it (quite frankly I never
> thought about expand_stack(), I only thought about the swapper locking
> while doing the "odd" change), if it's a bug I will release a corrected
> mmap-rb-5 in a few hours.  Thanks for raising this issue.

I don't think it's a bug so I don't feel the need to change it. The
expand_stack can only run with the semaphore acquired at worse in read
mode so it cannot race.

However now that you make me to think about this vm_pgoff field I'm
afraid I forgot to update it in the forward merging cases (in the new
code), luckily there are only a few forward merging cases that we have
to do (the backmerging are much more frequent) so it will be trivial to
fix it (and since I only merge anon mappings the bug seems only
theorical and this is probably why I couldn't notice it while doing the
regression testing [but I certainly agree to fix it even if it's
theorical]).

If I'm missing something let me know of course, thanks,

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Rik van Riel]

On Sun, 19 Aug 2001, Andrea Arcangeli wrote:
> On Sat, Aug 18, 2001 at 08:10:50PM -0400, Ben LaHaise wrote:

> > trees to see what kind of an effect it has on performance compared to the
> > avl tree?
>
> I posted some benchmark result a few minutes ago (the numbers says
> there were no implementation bugs).

Oh, and now that I think about this ... ;)

Your numbers show better insert/removal behaviour, but
isn't LOOKUP the common thing done with the VMAs in the
tree ?

Doesn't an rb tree give longer lookup paths or is this
something which should balance out in the real world?

regards,

Rik
--
IA64: a worthy successor to i860.

http://www.surriel.com/		http://distro.conectiva.com/

Send all your spam to aardvark@nl.linux.org (spam digging piggy)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sat, Aug 18, 2001 at 09:50:04PM -0300, Rik van Riel wrote:
> On Sun, 19 Aug 2001, Andrea Arcangeli wrote:
> > On Sat, Aug 18, 2001 at 08:10:50PM -0400, Ben LaHaise wrote:
> 
> > > Your patch performs a few odd things like:
> > >
> > > +       vma->vm_raend = 0;
> ...
> > > which I would argue are incorrect.  Remember that page faults rely on
> >
> > vm_raend is obviously correct.
> 
> Why ?

Do you know of any piece of code that touches vm_raend without the the
mmap_sem acquired? If yes you will change my mind about it otherwise you
will know why.

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sat, Aug 18, 2001 at 09:54:21PM -0300, Rik van Riel wrote:
> On Sun, 19 Aug 2001, Andrea Arcangeli wrote:
> > On Sat, Aug 18, 2001 at 08:10:50PM -0400, Ben LaHaise wrote:
> 
> > > trees to see what kind of an effect it has on performance compared to the
> > > avl tree?
> >
> > I posted some benchmark result a few minutes ago (the numbers says
> > there were no implementation bugs).
> 
> Oh, and now that I think about this ... ;)
> 
> Your numbers show better insert/removal behaviour, but
> isn't LOOKUP the common thing done with the VMAs in the
> tree ?

Every single mmap is doing 1 lookups (and 1 inserction). So it's doing a
flood of lookups as well.

> Doesn't an rb tree give longer lookup paths or is this
> something which should balance out in the real world?

The math complexity of the lookup remains O(lon(N)) and that is the only
thing that matters in the real world as far I can tell.

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sun, Aug 19, 2001 at 02:53:14AM +0200, Andrea Arcangeli wrote:
> I don't think it's a bug so I don't feel the need to change it. The
> expand_stack can only run with the semaphore acquired at worse in read
> mode so it cannot race.

Actually the locking is a bit subtle so I think it needs a further
explanation, everybody but expand_stack is playing with the vm_pgoff
with the write semaphore acquired.

The only ones playing with vm_pgoff with only the read semaphore
acquired is expand_stack and it serialize against itself with the
spinlock.

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sun, Aug 19, 2001 at 02:55:32AM +0200, Andrea Arcangeli wrote:
> On Sat, Aug 18, 2001 at 09:50:04PM -0300, Rik van Riel wrote:
> > On Sun, 19 Aug 2001, Andrea Arcangeli wrote:
> > > On Sat, Aug 18, 2001 at 08:10:50PM -0400, Ben LaHaise wrote:
> > 
> > > > Your patch performs a few odd things like:
> > > >
> > > > +       vma->vm_raend = 0;
> > ...
> > > > which I would argue are incorrect.  Remember that page faults rely on
> > >
> > > vm_raend is obviously correct.
> > 
> > Why ?
> 
> Do you know of any piece of code that touches vm_raend without the the
> mmap_sem acquired? If yes you will change my mind about it otherwise you
> will know why.

btw, while my change to madvise is obviously correct (madvise holds the
write sem), I noticed now that the other code changing vm_raend is racy
(but this is totally unrelated to my changes): the nopage callback
during the page fault updates the vm_raend with only the read semaphore
acquired so multiple threads could get confused, however it seems a
controlled race that cannot harm.

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sun, Aug 19, 2001 at 02:53:14AM +0200, Andrea Arcangeli wrote:
> theorical and this is probably why I couldn't notice it while doing the
> regression testing [but I certainly agree to fix it even if it's
> theorical]).

I changed idea, I think it doesn't make sense to try to do anything with
the vm_pgoff field with anon mappings so I won't change anything. the
vm_pgoff just doesn't make any sense and it can be just random for any
anon mapping.

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

hmm I noticed a superflous change I did, in unmap_fixup the 'area' isn't
visible to the readers (it was just out of the tree), so we can fixup
outside the spinlock, we need to spinlock only before making it visible
again:

	if (end == area->vm_end) {
		lock_vma_mappings(area);
		spin_lock(&mm->page_table_lock);
		area->vm_end = addr;

so in short I can put the area->vm_end = addr back before the
lock_vma...

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

Ok, at the light of this thread I did these changes:

diff -urN mmap-rb-ref/include/linux/mm.h mmap-rb-5/include/linux/mm.h
--- mmap-rb-ref/include/linux/mm.h	Sun Aug 19 04:51:13 2001
+++ mmap-rb-5/include/linux/mm.h	Sun Aug 19 04:56:07 2001
@@ -578,6 +578,10 @@
 {
 	unsigned long grow;
 
+	/*
+	 * vma->vm_start/vm_end cannot change under us because the caller is required
+	 * to hold the mmap_sem at least in read mode.
+	 */
 	address &= PAGE_MASK;
 	if (prev_vma && prev_vma->vm_end + (heap_stack_gap << PAGE_SHIFT) > address)
 		return -ENOMEM;
@@ -587,7 +591,21 @@
 		return -ENOMEM;
 	spin_lock(&vma->vm_mm->page_table_lock);
 	vma->vm_start = address;
+
+	/*
+	 * vm_pgoff locking is a bit subtle: everybody but expand_stack is
+	 * playing with the vm_pgoff with the write semaphore acquired. The
+	 * only one playing with vm_pgoff with only the read semaphore
+	 * acquired is expand_stack and it serializes against itself with the
+	 * spinlock.
+	 *
+	 * More in general this means that it is not enough to grab the mmap_sem
+	 * in read mode to avoid vm_pgoff to change under you. You either
+	 * need the write semaphore acquired, or the read semaphore plus
+	 * the spinlock.
+	 */
 	vma->vm_pgoff -= grow;
+
 	vma->vm_mm->total_vm += grow;
 	if (vma->vm_flags & VM_LOCKED)
 		vma->vm_mm->locked_vm += grow;
diff -urN mmap-rb-ref/mm/mmap.c mmap-rb-5/mm/mmap.c
--- mmap-rb-ref/mm/mmap.c	Sun Aug 19 04:49:51 2001
+++ mmap-rb-5/mm/mmap.c	Sun Aug 19 04:52:05 2001
@@ -785,14 +785,19 @@
 
 	/* Work out to one of the ends. */
 	if (end == area->vm_end) {
+		/*
+		 * here area isn't visible to the semaphore-less readers
+		 * so we don't need to update it under the spinlock.
+		 */
+		area->vm_end = addr;
 		lock_vma_mappings(area);
 		spin_lock(&mm->page_table_lock);
-		area->vm_end = addr;
 	} else if (addr == area->vm_start) {
 		area->vm_pgoff += (end - area->vm_start) >> PAGE_SHIFT;
+		/* same locking considerations of the above case */
+		area->vm_start = end;
 		lock_vma_mappings(area);
 		spin_lock(&mm->page_table_lock);
-		area->vm_start = end;
 	} else {
 	/* Unmapping a hole: area->vm_start < addr <= end < area->vm_end */
 		/* Add end mapping -- leave beginning for below */

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sun, Aug 19, 2001 at 04:59:06AM +0200, Andrea Arcangeli wrote:
> @@ -587,7 +591,21 @@
>  		return -ENOMEM;
>  	spin_lock(&vma->vm_mm->page_table_lock);
>  	vma->vm_start = address;
> +
> +	/*
> +	 * vm_pgoff locking is a bit subtle: everybody but expand_stack is
> +	 * playing with the vm_pgoff with the write semaphore acquired. The
> +	 * only one playing with vm_pgoff with only the read semaphore
> +	 * acquired is expand_stack and it serializes against itself with the
> +	 * spinlock.
> +	 *
> +	 * More in general this means that it is not enough to grab the mmap_sem
> +	 * in read mode to avoid vm_pgoff to change under you. You either
> +	 * need the write semaphore acquired, or the read semaphore plus
> +	 * the spinlock.
> +	 */
>  	vma->vm_pgoff -= grow;
> +
>  	vma->vm_mm->total_vm += grow;
>  	if (vma->vm_flags & VM_LOCKED)
>  		vma->vm_mm->locked_vm += grow;

unfortunately I was way too optimistic about this and I also misread
part of the code while writing the above. Looking more closely
expand_stack is a race condition in itself.

Nobody is allowed to change vm_pgoff or vm_start without holding _both_
the mm sem in _write_ mode _and_ the spinlock.

expand_stack holds the mm sem in _read_ mode and the spinlock so it is
totally broken.

All the readers thinks that only holding only the read semaphore is
enough to get coherent data but expand_stack is breaking this rule and
so all the readers can race.

To fix this problem we simply need to convert all the callers of
expand_stack to hold the write semaphore instead of the read semaphore
(this will have to be propagated to all architectures). I just checked
all the callers and they're all convertible without any real pain (we
just need to do a second lookup after upgrading the lock because we
don't have a primitive to upgrade the lock from "read" to "write"
atomically without having to release it for some time in the middle, but
expand_stack is a slow path so it's not a showstopper).

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: resend Re: [PATCH] final merging patch -- significant mozilla speedup.

[Andrea Arcangeli]

On Sun, Aug 19, 2001 at 05:53:11AM +0200, Andrea Arcangeli wrote:
> just need to do a second lookup after upgrading the lock because we
> don't have a primitive to upgrade the lock from "read" to "write"

I attempted to write such a primitive but it's impossible without a fail
path (think two readers trying to upgrade the lock at the same time, it
either deadlocks or one of the two will have to fail the atomic
upgrade and accept that something has changed under it), so it could
only improve performance saving a lookup sometime in case we are the
only readers out there, but we would still need to implement the ugly
slow path case (and avoiding the ugliness of such code was the only
reason I attempted to write such a primitive so...)

Andrea
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/