Slowdown with randomize_va_space in 2.6.12.2

Slowdown with randomize_va_space in 2.6.12.2

[Paulo Marques]

Hi, all

I have a bash script that calls a small application several times 
(around 50 calls) that just send and receives data through an already 
open tcp socket to a local server through the loopback device. It also 
launches another small app several times that just reads a small file 
from disk and does some processing on it in memory.

We noticed a severe performance regression on this application under 
kernel 2.6.12.2 that we tracked down to the address space randomization 
patches:

# echo 0 > randomize_va_space
# time ./script
real    0m0.671s
user    0m0.293s
sys     0m0.325s

# echo 1 > randomize_va_space
# time ./script
real    0m3.310s
user    0m2.712s
sys     0m0.401s

Notice that the real time is 5x slower with "randomize_va_space" turned 
on. This is on a Transmeta Crusoe TM5600 at 533MHz.

What is weird is that most of the extra time is being accounted as 
user-space time, but the user-space application is exactly the same in 
both runs, only the "randomize_va_space" parameter changed.

I browsed the randomization patch code and I don't think the random 
calculations themselves could account for all that time.

Does anybody have a clue as to why this is happening or what I should do 
to debug this further?

-- 
Paulo Marques - www.grupopie.com

It is a mistake to think you can solve any major problems
just with potatoes.
Douglas Adams

Re: Slowdown with randomize_va_space in 2.6.12.2

[David S. Miller]

From: Paulo Marques <pmarques@grupopie.com>
Date: Wed, 06 Jul 2005 15:23:56 +0100

> What is weird is that most of the extra time is being accounted as 
> user-space time, but the user-space application is exactly the same in 
> both runs, only the "randomize_va_space" parameter changed.

It might be attributable to more cpu cache misses in userspace since
the virtual addresses of everything are changing each and every
invocation.

But 2 seconds more of execution time is quite a lot.

Re: Slowdown with randomize_va_space in 2.6.12.2

[Dave Jones]

On Wed, Jul 06, 2005 at 12:57:19PM -0700, David S. Miller wrote:
 > From: Paulo Marques <pmarques@grupopie.com>
 > Date: Wed, 06 Jul 2005 15:23:56 +0100
 > 
 > > What is weird is that most of the extra time is being accounted as 
 > > user-space time, but the user-space application is exactly the same in 
 > > both runs, only the "randomize_va_space" parameter changed.
 > 
 > It might be attributable to more cpu cache misses in userspace since
 > the virtual addresses of everything are changing each and every
 > invocation.

On Transmeta CPUs that probably triggers a retranslation of
x86->native bytecode, if it thinks it hasn't seen code at that
address before.

		Dave

Re: Slowdown with randomize_va_space in 2.6.12.2

[David S. Miller]

From: Dave Jones <davej@redhat.com>
Subject: Re: Slowdown with randomize_va_space in 2.6.12.2
Date: Wed, 6 Jul 2005 16:53:15 -0400

> On Wed, Jul 06, 2005 at 12:57:19PM -0700, David S. Miller wrote:
>  > It might be attributable to more cpu cache misses in userspace since
>  > the virtual addresses of everything are changing each and every
>  > invocation.
> 
> On Transmeta CPUs that probably triggers a retranslation of
> x86->native bytecode, if it thinks it hasn't seen code at that
> address before.

That sounds like a more likely cause than my theory.

Re: Slowdown with randomize_va_space in 2.6.12.2

[Andrew Morton]

Dave Jones <davej@redhat.com> wrote:
>
> On Wed, Jul 06, 2005 at 12:57:19PM -0700, David S. Miller wrote:
>  > From: Paulo Marques <pmarques@grupopie.com>
>  > Date: Wed, 06 Jul 2005 15:23:56 +0100
>  > 
>  > > What is weird is that most of the extra time is being accounted as 
>  > > user-space time, but the user-space application is exactly the same in 
>  > > both runs, only the "randomize_va_space" parameter changed.
>  > 
>  > It might be attributable to more cpu cache misses in userspace since
>  > the virtual addresses of everything are changing each and every
>  > invocation.
> 
> On Transmeta CPUs that probably triggers a retranslation of
> x86->native bytecode, if it thinks it hasn't seen code at that
> address before.
> 

ouch.   What do we do?  Default to off?  Default to off on xmeta?

Re: Slowdown with randomize_va_space in 2.6.12.2

[David S. Miller]

From: Andrew Morton <akpm@osdl.org>
Date: Wed, 6 Jul 2005 18:12:20 -0700

> ouch.   What do we do?  Default to off?  Default to off on xmeta?

Good question.  Whatever security is gained by the va randomization
stuff is definitely not worth a 0.23 --> 3.0 second performance
regression.

Re: Slowdown with randomize_va_space in 2.6.12.2

[pmarques]

Quoting "David S. Miller" <davem@davemloft.net>:

> From: Andrew Morton <akpm@osdl.org>
> Date: Wed, 6 Jul 2005 18:12:20 -0700
> 
> > ouch.   What do we do?  Default to off?  Default to off on xmeta?
> 
> Good question.  Whatever security is gained by the va randomization
> stuff is definitely not worth a 0.23 --> 3.0 second performance
> regression.

Well, I tested the exact same script on my P4 2.8GHz and didn't notice a
significant regression. So maybe this is really Transmeta specific.

Also, this workload probably represents the worst scenario to trigger this: the
script does more than 100 fork / execs with each exec'ed program doing very
little work and exiting.

I can do some more tests (tomorrow) to see if different workloads are also
significantly affected, but I suspect that simply running one "normal" process
(or a few) will not show this problem.

Anyway, I still find this to be a little weird. My understanding of the Linux
memory management is still limited, so correct me if I'm wrong:

 - once we exec one program for the first time, the executable file is mmap'ed
in memory and pages are faulted in as they are executed (modulo prefaulting,
read-ahead, etc.).

 - these same pages are kept as pagecache even after the process exits(*)

 - on the next execution, these pages are already in memory as pagecache, and
are simply mapped to the process address space. The virtual address is
different because of randomization, but the physical addresses are the same.

 - why does the Transmeta interpreter "re-compiles" the code that is on the same
physical address? Interpreter bug?

I'm just pointing this out, because the machine I'm working on isn't exactly
"new", and it might have an old version of the interpreter. This can possibly
mean that newer Transmetas might not show this problem at all.

This is the cpuinfo of the machine in question:

processor       : 0
vendor_id       : GenuineTMx86
cpu family      : 6
model           : 4
model name      : Transmeta(tm) Crusoe(tm) Processor TM5600
stepping        : 3
cpu MHz         : 530.696
cache size      : 512 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr cx8 sep cmov mmx longrun lrti
bogomips        : 1028.09

and the relevant part of the dmesg output:

CPU: L1 I Cache: 64K (64 bytes/line), D cache 64K (32 bytes/line)
CPU: L2 Cache: 512K (128 bytes/line)
CPU: Processor revision 1.3.1.2, 533 MHz
CPU: Code Morphing Software revision 4.2.7-8-278
CPU: 20011004 02:04 official release 4.2.7#7
CPU serial number disabled.
CPU: After all inits, caps: 0080893f 0081813f 0000000e 00000000 00000000
00000000 00000000
CPU: Transmeta(tm) Crusoe(tm) Processor TM5600 stepping 03

So, if there is someone out there with newer Transmetas available that also want
to test this to see if there is a regression, I can build a small testcase to
see how it goes.

--
Paulo Marques - www.grupopie.com

(*) by the way, during the tests the machine always had more than 70Mb of free
memory, so I see no reason for it to dump pagecache

Re: Slowdown with randomize_va_space in 2.6.12.2

[Arjan van de Ven]

On Wed, 2005-07-06 at 18:12 -0700, Andrew Morton wrote:
> Dave Jones <davej@redhat.com> wrote:
> >
> > On Wed, Jul 06, 2005 at 12:57:19PM -0700, David S. Miller wrote:
> >  > From: Paulo Marques <pmarques@grupopie.com>
> >  > Date: Wed, 06 Jul 2005 15:23:56 +0100
> >  > 
> >  > > What is weird is that most of the extra time is being accounted as 
> >  > > user-space time, but the user-space application is exactly the same in 
> >  > > both runs, only the "randomize_va_space" parameter changed.
> >  > 
> >  > It might be attributable to more cpu cache misses in userspace since
> >  > the virtual addresses of everything are changing each and every
> >  > invocation.
> > 
> > On Transmeta CPUs that probably triggers a retranslation of
> > x86->native bytecode, if it thinks it hasn't seen code at that
> > address before.
> > 
> 
> ouch.   What do we do?  Default to off?  Default to off on xmeta?

off-on-xmeta would be my preference; I'll cook up a patch for that.

Re: Slowdown with randomize_va_space in 2.6.12.2

[Andrew Morton]

Arjan van de Ven <arjan@infradead.org> wrote:
>
> > > On Transmeta CPUs that probably triggers a retranslation of
>  > > x86->native bytecode, if it thinks it hasn't seen code at that
>  > > address before.
>  > > 
>  > 
>  > ouch.   What do we do?  Default to off?  Default to off on xmeta?
> 
>  off-on-xmeta would be my preference; I'll cook up a patch for that.

Well we seem to have several people reporting problems of various sorts
with that patch?

Re: Slowdown with randomize_va_space in 2.6.12.2

[Arjan van de Ven]

On Wed, 2005-07-06 at 23:41 -0700, Andrew Morton wrote:
> Arjan van de Ven <arjan@infradead.org> wrote:
> >
> > > > On Transmeta CPUs that probably triggers a retranslation of
> >  > > x86->native bytecode, if it thinks it hasn't seen code at that
> >  > > address before.
> >  > > 
> >  > 
> >  > ouch.   What do we do?  Default to off?  Default to off on xmeta?
> > 
> >  off-on-xmeta would be my preference; I'll cook up a patch for that.
> 
> Well we seem to have several people reporting problems of various sorts
> with that patch?

actually we have several people reporting problems that started around
the time the patch got merged. There's very few cases that actually go
away when disabling this. (there's the weird kernel build one and we're
waiting on a good maps on that one)

Re: Slowdown with randomize_va_space in 2.6.12.2

[Eric Lammerts]

On Thu, 7 Jul 2005, Arjan van de Ven wrote:
> On Wed, 2005-07-06 at 18:12 -0700, Andrew Morton wrote:
> > Dave Jones <davej@redhat.com> wrote:
> > > On Transmeta CPUs that probably triggers a retranslation of
> > > x86->native bytecode, if it thinks it hasn't seen code at that
> > > address before.
> >
> > ouch.   What do we do?  Default to off?  Default to off on xmeta?
>
> off-on-xmeta would be my preference; I'll cook up a patch for that.

It would be nice if a fix for this could get in before 2.6.13 comes
out. What about this patch?

cheers,
Eric

--- linux-2.6.13-rc4/arch/i386/kernel/cpu/transmeta.c.orig	2005-06-17 15:48:29.000000000 -0400
+++ linux-2.6.13-rc4/arch/i386/kernel/cpu/transmeta.c	2005-07-29 20:46:54.000000000 -0400
@@ -76,6 +76,10 @@
 #define USER686 (X86_FEATURE_TSC|X86_FEATURE_CX8|X86_FEATURE_CMOV)
         if ( c->x86 == 5 && (c->x86_capability[0] & USER686) == USER686 )
 		c->x86 = 6;
+
+	/* randomize_va_space slows us down enormously;
+	   it probably triggers retranslation of x86->native bytecode */
+	randomize_va_space = 0;
 }

 static void transmeta_identify(struct cpuinfo_x86 * c)

Re: Slowdown with randomize_va_space in 2.6.12.2

[Andrew Morton]

Eric Lammerts <eric@lammerts.org> wrote:
>
> 
> On Thu, 7 Jul 2005, Arjan van de Ven wrote:
> > On Wed, 2005-07-06 at 18:12 -0700, Andrew Morton wrote:
> > > Dave Jones <davej@redhat.com> wrote:
> > > > On Transmeta CPUs that probably triggers a retranslation of
> > > > x86->native bytecode, if it thinks it hasn't seen code at that
> > > > address before.
> > >
> > > ouch.   What do we do?  Default to off?  Default to off on xmeta?
> >
> > off-on-xmeta would be my preference; I'll cook up a patch for that.
> 
> It would be nice if a fix for this could get in before 2.6.13 comes
> out.

I agree.

> What about this patch?
> 

It has the virtue of simplicity.  Arjan, were you planning on anything
fancier?

> 
> --- linux-2.6.13-rc4/arch/i386/kernel/cpu/transmeta.c.orig	2005-06-17 15:48:29.000000000 -0400
> +++ linux-2.6.13-rc4/arch/i386/kernel/cpu/transmeta.c	2005-07-29 20:46:54.000000000 -0400
> @@ -76,6 +76,10 @@
>  #define USER686 (X86_FEATURE_TSC|X86_FEATURE_CX8|X86_FEATURE_CMOV)
>          if ( c->x86 == 5 && (c->x86_capability[0] & USER686) == USER686 )
>  		c->x86 = 6;
> +
> +	/* randomize_va_space slows us down enormously;
> +	   it probably triggers retranslation of x86->native bytecode */
> +	randomize_va_space = 0;
>  }
> 
>  static void transmeta_identify(struct cpuinfo_x86 * c)

Re: Slowdown with randomize_va_space in 2.6.12.2

[Arjan van de Ven]

> 
> It has the virtue of simplicity.  Arjan, were you planning on anything
> fancier?

short term: no. (eg 2.6.13).
Long term I wanted to turn this into a bitmask so that you can control
the randomisations individual (eg keep the stack one disable the library
one only)

Re: Slowdown with randomize_va_space in 2.6.12.2

[Arjan van de Ven]

[-- Attachment #1: Type: text/plain, Size: 210 bytes --]


> It has the virtue of simplicity.  Arjan, were you planning on anything
> fancier?

not for 2.6.13; this was the plan
for later I was going to turn it into a bitmask for the individual
randomisations 

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Slowdown with randomize_va_space in 2.6.12.2

[Arjan van de Ven]

On Wed, 2005-07-06 at 12:57 -0700, David S. Miller wrote:
> From: Paulo Marques <pmarques@grupopie.com>
> Date: Wed, 06 Jul 2005 15:23:56 +0100
> 
> > What is weird is that most of the extra time is being accounted as 
> > user-space time, but the user-space application is exactly the same in 
> > both runs, only the "randomize_va_space" parameter changed.
> 
> It might be attributable to more cpu cache misses in userspace since
> the virtual addresses of everything are changing each and every
> invocation.

also x86 technically is pipt so virtual addresses shouldn't matter...