ftrace: to kill a daemon

This patch enables the loading of the __mcount_section of modules and changing all the callers of mcount into nops.

The modification is done before the init_module function is called, so again, we do not need to use kstop_machine to make these changes.

Quoted 5 lines · On Friday 08 August 2008 04:20:16 Steven Rostedt wrote:

This patch enables the loading of the __mcount_section of modules and changing all the callers of mcount into nops.

The modification is done before the init_module function is called, so again, we do not need to use kstop_machine to make these changes.

Importantly, before parameter parsing too (which can use module functions before the module's init()).

One of the things that bothered me about the latest ftrace code was this annoying daemon that would wake up once a second to see if it had work to do. If it did not, it would go to sleep, otherwise it would do its work and then go to sleep.

You see, the reason for this is that for ftrace to maintain performance when configured in but disabled, it would need to change all the locations that called "mcount" (enabled with the gcc -pg option) into nops. The "-pg" option in gcc sets up a function profiler to call this function called "mcount". If you simply have "mcount" return, it will still add 15 to 18% overhead in performance. Changing all the calls to nops moved the overhead into noise.

To get rid of this, I had the mcount code record the location that called it. Later, the "ftraced" daemon would wake up and look to see if any new functions were recorded. If so, it would call kstop_machine and convert the calls to "nops". We needed kstop_machine because bad things happen on SMP if you modify code that happens to be in the instruction cache of another CPU.

This "ftraced" kernel thread would be a happy little worker, but it caused some pains. One, is that it woke up once a second, and Ted Tso got mad at me because it would show up on PowerTop. I could easily make the default 5 seconds, and even have it runtime configurable, with a trivial patch. I have not got around to doing that yet.

The other annoying thing, and this one bothers me the most, is that we can not have this enabled on a production -rt kernel. The latency caused by the kstop_machine when doing work is lost in the noise on a non-rt kernel, but it can be up to 800 microseconds, and that would kill the -rt kernel. The reason this bothered me the most, is that -rt is where it came from, and ftraced was not treating its motherland very well.

Along came Gregory Haskins, who was bickering about having ftrace enabled on a production -rt kernel. I told him the reasons that this would be bad and then he started thinking out loud, and suggesting wild ideas, like patching gcc!

Since I have recently seen "The Dark Knight", Gregory's comments put me into an "evil" mood. I then thought of the idea about using the relocation entries of the mcount call sites, in a prelinked object file, and create a separate section with a list of these sites. On boot up, record them and change them into nops.

That's it! No kstop_machine for turning them into nops. We would only need stop_machine to enable or disable tracing, but a user not tracing will not have to deal with this annoying "ftraced" kernel thread waking up every second or ever running kstop_machine.

What's more, this means we can enable it on a production -rt kernel!

Now, this was no easy task. We needed to add a section to every object file with a list of pointers to the call sites to mcount. The idea I came up with was to make a tmp.s file for every object just after it is compiled. This tmp.s would then be compiled and relinked into the original object. The tmp.s file would have something like:

.section __mcount_loc,"a",@progbits
.quad location_of_mcount1
.quad location_of_mcount2
(etc)

By running objdump on the object file we can find the offsets into the sections that the functions are called.

For example, looking at hrtimer.o:

Disassembly of section .text:

0000000000000000 <hrtimer_init_sleeper>:

       0:       55                      push   %rbp
       1:       48 89 e5                mov    %rsp,%rbp
       4:       e8 00 00 00 00          callq  9 <hrtimer_init_sleeper+0x9>
                        5: R_X86_64_PC32        mcount+0xfffffffffffffffc

[...]

the '5' in the '5: R_X86_64_PC32' is the offset that the mcount relocation is to be done for the call site. This offset is from the .text section, and not necessarily, from the function. If we look further we see:

000000000000001e <ktime_add_safe>:

      1e:       55                      push   %rbp
      1f:       48 89 e5                mov    %rsp,%rbp
      22:       e8 00 00 00 00          callq  27 <ktime_add_safe+0x9>
                        23: R_X86_64_PC32       mcount+0xfffffffffffffffc

This mcount call site is 0x23 from the .text section, and obviously not from the ktime_add_safe.

If we make a tmp.s that has the following:

.section __mcount_loc,"a",@progbits
.quad hrtimer_init_sleeper + 0x5
.quad hrtimer_init_sleeper + 0x23

We have a section with the locations of these two call sites. After the final linking, they will point to the actual address used.

All that would need to be done is:

gcc -c tmp.s -o tmp.o
ld -r tmp.o hrtimer.o -o tmp_hrtime.o
mv tmp_hrtimer.o hrtimer.o

Easy as that! Not quite. What happens if that first function in the section is a static function? That is, the symbol for the function is local to the object. If for some reason hrtimer_init_sleeper is static, the tmp_hrtimer.o would have two symbols for hrtimer_init_sleeper. One local and one global.

But we can be even more evil with this idea. We can do crazy things with objcopy to solve it for us.

  objcopy --globalize-symbol hrtimer_init_sleeper hrtimer.o tmp_hrtimer.o

Now the hrtimer_init_sleeper would be global for linking.

ld -r tmp_hrtimer.o tmp.o -o tmp2_hrtimer.o

Now the tmp.o could use the same global hrtimer_init_sleeper symbol. But we have tmp2_hritmer.o that has the tmp.o and tmp_hrtimer.o symbols, but we cant just blindly convert local symbols to globals.

The solution is simply put it back to local.

  objcopy --localize-symbol hrtimer_init_sleeper tmp2_hrtimer.o hrtimer.o

Now our hrtimer.o file has our __mcount_loc section and the reference to hrtimer_init_sleeper will be resolved.

This is a bit complex to do in shell scripting and Makefiles, so I wrote a well documented recordmcount.pl perl script, that will do the above all in one place.

With this new update, we can work to kill that kernel thread "ftraced"!

This patch set ports to x86_64 and i386, the other archs will still use the daemon until they are converted over.

I tested this on both x86_64 and i386 with and without CONFIG_RELOCATE set.

Hi Steven,

If you really want to stop using stop_machine, I think you should have a look at my immediate values infrastructure :

see:
http://git.kernel.org/?p=linux/kernel/git/compudj/linux-2.6-lttng.git;a=blob;f=arch/x86/kernel/immediate.c;h=0958c02b49eed3bbc00bdc5aceeee17a6d0c7ab4;hb=HEAD

particularly replace_instruction_safe(), which uses a temporary breakpoint to safely replace an instruction on a live SMP system without using stop_machine. Feel free to try it in ftrace. :)

You may need to tweak the imv_notifier(), which is responsible for executing the breakpoint. The only special thing this handler has to know is the non-relocatable instructions you might want to insert (it only cares about the new instructions, not the old ones being replaced). The current code deals with 5-bytes jumps. Note that the instruction is executed in the breakpoint handler with preemption disabled, which might not be well suited for a call instruction.

I would recommend to patch in a 5-bytes jmp with 0 offset (e9 00 00 00 00) when disabled (this makes a single 5-bytes instruction and thus makes sure no instruction pointer can iret in the middle).

When enabling the site, you could patch-in the original call, but you should tweak the imv_notifier() so that it uses the jmp offset 0 in the bypass instead of the function call, because preemption would otherwise be disabled around the call when executed in the breakpoint bypass.

Therefore, simply statically forcing the bypass code to e9 00 00 00 00 in all the cases (a nop) would do the job for your needs.

Quoted 30 lines · Mathieu Desnoyers

Hi Steven,

If you really want to stop using stop_machine, I think you should have a look at my immediate values infrastructure :

see:
http://git.kernel.org/?p=linux/kernel/git/compudj/linux-2.6-lttng.git;a=blob;f=arch/x86/kernel/immediate.c;h=0958c02b49eed3bbc00bdc5aceeee17a6d0c7ab4;hb=HEAD

particularly replace_instruction_safe(), which uses a temporary breakpoint to safely replace an instruction on a live SMP system without using stop_machine. Feel free to try it in ftrace. :)

You may need to tweak the imv_notifier(), which is responsible for executing the breakpoint. The only special thing this handler has to know is the non-relocatable instructions you might want to insert (it only cares about the new instructions, not the old ones being replaced). The current code deals with 5-bytes jumps. Note that the instruction is executed in the breakpoint handler with preemption disabled, which might not be well suited for a call instruction.

I would recommend to patch in a 5-bytes jmp with 0 offset (e9 00 00 00 00) when disabled (this makes a single 5-bytes instruction and thus makes sure no instruction pointer can iret in the middle).

When enabling the site, you could patch-in the original call, but you should tweak the imv_notifier() so that it uses the jmp offset 0 in the bypass instead of the function call, because preemption would otherwise be disabled around the call when executed in the breakpoint bypass.

Quoted 2 lines

Therefore, simply statically forcing the bypass code to e9 00 00 00 00 in all the cases (a nop) would do the job for your needs.

I originally used jumps instead of nops, but unfortunately, they actually hurt performance more than adding nops. Ingo told me it was probably due to using up the jump predictions of the CPU.

-- Steve

Quoted 5 lines · * Steven Rostedt ([email protected]) wrote:

I originally used jumps instead of nops, but unfortunately, they actually hurt performance more than adding nops. Ingo told me it was probably due to using up the jump predictions of the CPU.

Hrm, are you sure you use a single 5-bytes nop instruction then, or do you use a mix of various nop sizes (add_nops) on some architectures ?

You can consume the branch prediction buffers for conditional branches, but I doubt static jumps have this impact ? I don't see what "jump predictions" you are referring to here exactly.

Quoted 7 lines · Mathieu Desnoyers

Quoted 5 lines · * Steven Rostedt ([email protected]) wrote:

I originally used jumps instead of nops, but unfortunately, they actually hurt performance more than adding nops. Ingo told me it was probably due to using up the jump predictions of the CPU.

Quoted 2 lines

Hrm, are you sure you use a single 5-bytes nop instruction then, or do you use a mix of various nop sizes (add_nops) on some architectures ?

I use (for x86) what is in include/asm-x86/nops.h depending on what the cpuid gives us.

Quoted 4 lines

You can consume the branch prediction buffers for conditional branches, but I doubt static jumps have this impact ? I don't see what "jump predictions" you are referring to here exactly.

I don't know the details, but we definitely saw a drop in preformance between using nops and static jumps.

-- Steve

Quoted 9 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 5 lines · * Steven Rostedt ([email protected]) wrote:

I originally used jumps instead of nops, but unfortunately, they actually hurt performance more than adding nops. Ingo told me it was probably due to using up the jump predictions of the CPU.

Quoted 6 lines

Quoted 2 lines

Hrm, are you sure you use a single 5-bytes nop instruction then, or do you use a mix of various nop sizes (add_nops) on some architectures ?

I use (for x86) what is in include/asm-x86/nops.h depending on what the cpuid gives us.

That's bad :

#define GENERIC_NOP5 GENERIC_NOP1 GENERIC_NOP4

#define K8_NOP5 K8_NOP3 K8_NOP2

#define K7_NOP5 K7_NOP4 ASM_NOP1

So, when you try, later, to replace these instructions with a single 5-bytes instruction, a preempted thread could iret in the middle of your 5-bytes insn and cause an illegal instruction ?

Quoted 7 lines

Quoted 6 lines

You can consume the branch prediction buffers for conditional branches, but I doubt static jumps have this impact ? I don't see what "jump predictions" you are referring to here exactly.

Quoted 3 lines

I don't know the details, but we definitely saw a drop in preformance between using nops and static jumps.

Generated by replacing all the call by 5-bytes jumps e9 00 00 00 00 instead of the 5-bytes add_nops ? On which architectures ?

Quoted 21 lines · Mathieu Desnoyers

Quoted 9 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 5 lines · * Steven Rostedt ([email protected]) wrote:

I originally used jumps instead of nops, but unfortunately, they actually hurt performance more than adding nops. Ingo told me it was probably due to using up the jump predictions of the CPU.

Quoted 6 lines

Quoted 2 lines

Hrm, are you sure you use a single 5-bytes nop instruction then, or do you use a mix of various nop sizes (add_nops) on some architectures ?

I use (for x86) what is in include/asm-x86/nops.h depending on what the cpuid gives us.

That's bad :

#define GENERIC_NOP5 GENERIC_NOP1 GENERIC_NOP4

Quoted 7 lines

#define K8_NOP5 K8_NOP3 K8_NOP2

#define K7_NOP5 K7_NOP4 ASM_NOP1

So, when you try, later, to replace these instructions with a single 5-bytes instruction, a preempted thread could iret in the middle of your 5-bytes insn and cause an illegal instruction ?

That's why I use kstop_machine.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

You can consume the branch prediction buffers for conditional branches, but I doubt static jumps have this impact ? I don't see what "jump predictions" you are referring to here exactly.

Quoted 7 lines

Quoted 3 lines

I don't know the details, but we definitely saw a drop in preformance between using nops and static jumps.

Generated by replacing all the call by 5-bytes jumps e9 00 00 00 00 instead of the 5-bytes add_nops ? On which architectures ?

I ran this on my Dell (intel Xeon), which IIRC did show the performance degration. I unfortunately don't have the time to redo those tests, but you are welcome to.

Just look at arch/x86/kernel/ftrace.c and replace the nop with the jump. In fact, the comments in that file still say it is a jmp. Remember, my first go was to use the jmp.

Quoted 23 lines · Mathieu Desnoyers

Quoted 9 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 7 lines · Mathieu Desnoyers

Quoted 5 lines · * Steven Rostedt ([email protected]) wrote:

I originally used jumps instead of nops, but unfortunately, they actually hurt performance more than adding nops. Ingo told me it was probably due to using up the jump predictions of the CPU.

Quoted 6 lines

Quoted 2 lines

Hrm, are you sure you use a single 5-bytes nop instruction then, or do you use a mix of various nop sizes (add_nops) on some architectures ?

I use (for x86) what is in include/asm-x86/nops.h depending on what the cpuid gives us.

That's bad :

#define GENERIC_NOP5 GENERIC_NOP1 GENERIC_NOP4

#define K8_NOP5 K8_NOP3 K8_NOP2

Quoted 5 lines

#define K7_NOP5 K7_NOP4 ASM_NOP1

So, when you try, later, to replace these instructions with a single 5-bytes instruction, a preempted thread could iret in the middle of your 5-bytes insn and cause an illegal instruction ?

That's why I use kstop_machine.

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

You can consume the branch prediction buffers for conditional branches, but I doubt static jumps have this impact ? I don't see what "jump predictions" you are referring to here exactly.

Quoted 7 lines

Quoted 3 lines

I don't know the details, but we definitely saw a drop in preformance between using nops and static jumps.

Generated by replacing all the call by 5-bytes jumps e9 00 00 00 00 instead of the 5-bytes add_nops ? On which architectures ?

I ran this on my Dell (intel Xeon), which IIRC did show the performance degration. I unfortunately don't have the time to redo those tests, but you are welcome to.

Just look at arch/x86/kernel/ftrace.c and replace the nop with the jump. In fact, the comments in that file still say it is a jmp. Remember, my first go was to use the jmp.

-- Steve

Quoted 8 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 8 lines

Quoted 1 line

That's bad :

#define GENERIC_NOP5 GENERIC_NOP1 GENERIC_NOP4

#define K8_NOP5 K8_NOP3 K8_NOP2

Quoted 8 lines

Quoted 5 lines

#define K7_NOP5 K7_NOP4 ASM_NOP1

So, when you try, later, to replace these instructions with a single 5-bytes instruction, a preempted thread could iret in the middle of your 5-bytes insn and cause an illegal instruction ?

That's why I use kstop_machine.

kstop_machine does not guarantee that you won't have _any_ thread preempted with IP pointing exactly in the middle of your instructions _before_ the modification scheduled back in _after_ the modification and thus causing an illegal instruction.

Still buggy. :/

Quoted 23 lines · Mathieu Desnoyers

Quoted 8 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 8 lines

Quoted 1 line

That's bad :

#define GENERIC_NOP5 GENERIC_NOP1 GENERIC_NOP4

#define K8_NOP5 K8_NOP3 K8_NOP2

Quoted 8 lines

Quoted 5 lines

#define K7_NOP5 K7_NOP4 ASM_NOP1

So, when you try, later, to replace these instructions with a single 5-bytes instruction, a preempted thread could iret in the middle of your 5-bytes insn and cause an illegal instruction ?

That's why I use kstop_machine.

kstop_machine does not guarantee that you won't have _any_ thread preempted with IP pointing exactly in the middle of your instructions _before_ the modification scheduled back in _after_ the modification and thus causing an illegal instruction.

Quoted 1 line

Still buggy. :/

Hmm, good point. Unless...

Can a processor be preempted in a middle of nops? What do nops do for a processor? Can it skip them nicely in one shot?

This means I'll have to do the benchmarks again, and see what the performance difference of a jmp and a nop is significant. I'm thinking that if the processor can safely skip nops without any type of processing, this may be the reason that nops are better than a jmp. A jmp causes the processor to do a little more work.

I might even run a test to see if I can force a processor that uses the three-two nops to preempt between them.

I can add a test in x86 ftrace.c to check to see which nop was used, and use the jmp if the arch does not have a 5 byte nop.

I'm assuming that jmp is more expensive than the nops because otherwise a jmp 0 would have been used as a 5 byte nop.

-- Steve

Quoted 8 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 8 lines

Quoted 2 lines

That's why I use kstop_machine.

kstop_machine does not guarantee that you won't have _any_ thread preempted with IP pointing exactly in the middle of your instructions _before_ the modification scheduled back in _after_ the modification and thus causing an illegal instruction.

Quoted 7 lines

Quoted 1 line

Still buggy. :/

Hmm, good point. Unless...

Can a processor be preempted in a middle of nops? What do nops do for a processor? Can it skip them nicely in one shot?

Given that those are multiple instructions, I think a processor has all the rights to preempt in the middle of them. And even if some specific architecture, for any obscure reason, happens to merge them, I don't think this will be portable across Intel, AMD, ...

Quoted 9 lines

This means I'll have to do the benchmarks again, and see what the performance difference of a jmp and a nop is significant. I'm thinking that if the processor can safely skip nops without any type of processing, this may be the reason that nops are better than a jmp. A jmp causes the processor to do a little more work.

I might even run a test to see if I can force a processor that uses the three-two nops to preempt between them.

Yup, although one architecture not triggering this doesn't say much about the various x86 flavors out there. In any case
- if you trigger the problem, we have to fix it.
- if you do not succeed to trigger the problem, we will have to test it on a wider architecture range and maybe end up fixit it anyway to play safe with the specs.

So, in every case, we end up fixing the issue.

Quoted 3 lines

I can add a test in x86 ftrace.c to check to see which nop was used, and use the jmp if the arch does not have a 5 byte nop.

I would propose the following alternative :

Create new macros in include/asm-x86/nops.h :

/* short jump, offset 3 bytes : skips total of 5 bytes */ #define GENERIC_ATOMIC_NOP5 ".byte 0xeb,0x03,0x00,0x00,0x00\n"

#if defined(CONFIG_MK7)
#define ATOMIC_NOP5 GENERIC_ATOMIC_NOP5
#elif defined(CONFIG_X86_P6_NOP)
#define ATOMIC_NOP5 P6_NOP5
#elif defined(CONFIG_X86_64)
#define ATOMIC_NOP5 GENERIC_ATOMIC_NOP5
#else
#define ATOMIC_NOP5 GENERIC_ATOMIC_NOP5
#endif

And then optimize if necessary. You will probably find plenty of knowledgeable people who will know better 5-bytes nop instruction more efficient than this "generic" short jump offset 0x3.

Then you can use the (buggy) 3nops/2nops as a performance baseline and see the performance hit on each architecture.

First get it right, then make it fast....

I'm stubborn, I want to get it right _and_ keep it fast.

Quoted 1 line · Steven Rostedt

I'm stubborn, I want to get it right _and_ keep it fast.

For me it would seem better to just not use two part 5 byte nops instead of adding such hacks. I doubt there are that many of them anyways. I bet you won't be able to measure any difference between the different nop types in any macro benchmark.

I wish we had a true 5 byte nop.

Quoted 1 line · Steven Rostedt

I wish we had a true 5 byte nop.

0x66 0x66 0x66 0x66 0x90

Unfortunately, aside from P6_NOP5, none of the standard asm/nops.h nops are suitable. Something like "0x66, 0x66, 0x66, 0x66, 0x90" would work everywhere, but its possible putting more than 3 prefixes on the instruction will kick the decoder into a slow path, which may have a noticable effect.

Quoted 1 line · Steven Rostedt

I wish we had a true 5 byte nop.

0x66 0x66 0x66 0x66 0x90

Quoted 2 lines · Jeremy Fitzhardinge

Steven Rostedt wrote:

Quoted 3 lines

Quoted 1 line

I wish we had a true 5 byte nop.

0x66 0x66 0x66 0x66 0x90

I don't think so. Multiple redundant prefixes can be really expensive on some uarchs.

A no-op that isn't cheap isn't a no-op at all, it's a slow-op.

Quoted 9 lines · Linus Torvalds

Quoted 5 lines · Jeremy Fitzhardinge

Quoted 1 line · Steven Rostedt

I wish we had a true 5 byte nop.

0x66 0x66 0x66 0x66 0x90

Quoted 4 lines

I don't think so. Multiple redundant prefixes can be really expensive on some uarchs.

A no-op that isn't cheap isn't a no-op at all, it's a slow-op.

A quick meaningless benchmark showed a slight perfomance hit.

Here's 10 runs of "hackbench 50" using the two part 5 byte nop:

run 1
Time: 4.501
run 2
Time: 4.855
run 3
Time: 4.198
run 4
Time: 4.587
run 5
Time: 5.016
run 6
Time: 4.757
run 7
Time: 4.477
run 8
Time: 4.693
run 9
Time: 4.710
run 10
Time: 4.715
avg = 4.6509

And 10 runs using the above 5 byte nop:

run 1
Time: 4.832
run 2
Time: 5.319
run 3
Time: 5.213
run 4
Time: 4.830
run 5
Time: 4.363
run 6
Time: 4.391
run 7
Time: 4.772
run 8
Time: 4.992
run 9
Time: 4.727
run 10
Time: 4.825
avg = 4.8264

# cat /proc/cpuinfo
processor	: 0
vendor_id	: AuthenticAMD
cpu family	: 15
model		: 65
model name	: Dual-Core AMD Opteron(tm) Processor 2220
stepping	: 3
cpu MHz		: 2799.992
cache size	: 1024 KB
physical id	: 0
siblings	: 2
core id		: 0
cpu cores	: 2
apicid		: 0
initial apicid	: 0
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 pae mce cx8 apic sep mtrr pge mca 
cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt 
rdtscp lm 3dnowext 3dnow pni cx16 lahf_lm cmp_legacy svm extapic 
cr8_legacy
bogomips	: 5599.98
clflush size	: 64
power management: ts fid vid ttp tm stc

There's 4 of these.

Just to make sure, I ran the above nop test again:

[ this is reverse from the above runs ]

run 1
Time: 4.723
run 2
Time: 5.080
run 3
Time: 4.521
run 4
Time: 4.841
run 5
Time: 4.696
run 6
Time: 4.946
run 7
Time: 4.754
run 8
Time: 4.717
run 9
Time: 4.905
run 10
Time: 4.814
avg = 4.7997

And again the two part nop:

run 1
Time: 4.434
run 2
Time: 4.496
run 3
Time: 4.801
run 4
Time: 4.714
run 5
Time: 4.631
run 6
Time: 5.178
run 7
Time: 4.728
run 8
Time: 4.920
run 9
Time: 4.898
run 10
Time: 4.770
avg = 4.757

This time it was close, but still seems to have some difference.

heh, perhaps it's just noise.

-- Steve

Quoted 11 lines · * Steven Rostedt ([email protected]) wrote:

Quoted 9 lines · Linus Torvalds

Quoted 5 lines · Jeremy Fitzhardinge

Quoted 1 line · Steven Rostedt

I wish we had a true 5 byte nop.

0x66 0x66 0x66 0x66 0x90

Quoted 8 lines

Quoted 4 lines

I don't think so. Multiple redundant prefixes can be really expensive on some uarchs.

A no-op that isn't cheap isn't a no-op at all, it's a slow-op.

A quick meaningless benchmark showed a slight perfomance hit.

Hi Steven,

I tried to run my own tests to see if I could get to know if these numbers are actually meaningful at all. My results seems to show that there is not any significant difference between the various configurations, and actually that the only one tendency I see is that the 2-bytes jump offset 0x03 would be slightly faster than the 3/2 nop on Intel Xeon. But we would have to run these a bit more often to confirm that I guess.

I am just trying to get a sense of whether we are really trying hard to optimize something worthless in practice, and to me it looks like it. But it could be the architecture I am using that brings these results.

Mathieu

Intel Xeon dual quad-core
Intel(R) Xeon(R) CPU E5405 @ 2.00GHz

3/2 nop used :
K8_NOP3 K8_NOP2
#define K8_NOP2 ".byte 0x66,0x90\n"
#define K8_NOP3 ".byte 0x66,0x66,0x90\n"

** Summary **

Test A : make -j20 2.6.27-rc2 kernel (real time)

                                          Avg.      std.dev
Case 1 : ftrace not compiled-in.          1m9.76s   0.41s
Case 2 : 3/2 nops                         1m9.95s   0.36s
Case 3 : 2-bytes jump, offset 0x03        1m9.10s   0.40s
Case 4 : 5-bytes jump, offset 0x00        1m9.25s   0.34s

Test B : hackbench 15

Case 1 : ftrace not compiled-in. 0.349s 0.007s
Case 2 : 3/2 nops 0.351s 0.014s
Case 3 : 2-bytes jump, offset 0x03 0.350s 0.007s
Case 4 : 5-bytes jump, offset 0x00 0.351s 0.010s

** Detail **

* Test A

benchmark : make -j20 2.6.27-rc2 kernel
make clean; make -j20; make clean done before the tests to prime caches. Same .config used.

Case 1 : ftrace not compiled-in.

real 1m9.980s
user 7m27.664s
sys 0m48.771s

real 1m9.330s
user 7m27.244s
sys 0m50.567s

real 1m9.393s
user 7m27.408s
sys 0m50.511s

real 1m9.674s
user 7m28.088s
sys 0m50.327s

real 1m10.441s
user 7m27.736s
sys 0m49.687s

real time
average : 1m9.76s
std. dev. : 0.41s

after a reboot with the same kernel :

real 1m8.758s
user 7m26.012s
sys 0m48.835s

real 1m11.035s
user 7m26.432s
sys 0m49.171s

real 1m9.834s
user 7m25.768s
sys 0m49.167s

Case 2 : 3/2 nops

real 1m9.713s
user 7m27.524s
sys 0m48.315s

real 1m9.481s
user 7m27.144s
sys 0m48.587s

real 1m10.565s
user 7m27.048s
sys 0m48.715s

real 1m10.008s
user 7m26.436s
sys 0m49.295s

real 1m9.982s
user 7m27.160s
sys 0m48.667s

real time
avg : 1m9.95s
std. dev. : 0.36s

Case 3 : 2-bytes jump, offset 0x03

real 1m9.158s
user 7m27.108s
sys 0m48.775s

real 1m9.159s
user 7m27.320s
sys 0m48.659s

real 1m8.390s
user 7m27.976s
sys 0m48.359s

real 1m9.143s
user 7m26.624s
sys 0m48.719s

real 1m9.642s
user 7m26.228s
sys 0m49.483s

real time
avg : 1m9.10s
std. dev. : 0.40s

one extra after reboot with same kernel :

real 1m8.855s
user 7m27.372s
sys 0m48.543s

Case 4 : 5-bytes jump, offset 0x00

real 1m9.173s
user 7m27.228s
sys 0m48.151s

real 1m9.735s
user 7m26.852s
sys 0m48.499s

real 1m9.502s
user 7m27.148s
sys 0m48.107s

real 1m8.727s
user 7m27.416s
sys 0m48.071s

real 1m9.115s
user 7m26.932s
sys 0m48.727s

real time
avg : 1m9.25s
std. dev. : 0.34s

* Test B

Hackbench

Case 1 : ftrace not compiled-in.

./hackbench 15
Time: 0.358
./hackbench 15
Time: 0.342
./hackbench 15
Time: 0.354
./hackbench 15
Time: 0.338
./hackbench 15
Time: 0.347

Average : 0.349
std. dev. : 0.007

Case 2 : 3/2 nops

./hackbench 15
Time: 0.328
./hackbench 15
Time: 0.368
./hackbench 15
Time: 0.351
./hackbench 15
Time: 0.343
./hackbench 15
Time: 0.366

Average : 0.351
std. dev. : 0.014

Case 3 : jmp 2 bytes

./hackbench 15
Time: 0.346
./hackbench 15
Time: 0.359
./hackbench 15
Time: 0.356
./hackbench 15
Time: 0.350
./hackbench 15
Time: 0.340

Average : 0.350
std. dev. : 0.007

Case 3 : jmp 5 bytes

./hackbench 15
Time: 0.346
./hackbench 15
Time: 0.346
./hackbench 15
Time: 0.364
./hackbench 15
Time: 0.362
./hackbench 15
Time: 0.338

Average : 0.351
std. dev. : 0.010

Hardware used :

processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Intel(R) Xeon(R) CPU E5405 @ 2.00GHz
stepping : 6
cpu MHz : 2000.114
cache size : 6144 KB
physical id : 0
siblings : 4
core id : 0
cpu cores : 4
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov
pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni monitor ds_cpl vmx tm2 ssse3 cx16 xtpr dca sse4_1 lahf_lm
bogomips : 4000.22
clflush size : 64
cache_alignment : 64
address sizes : 38 bits physical, 48 bits virtual
power management:

(7 other similar cpus)

Quoted 139 lines

Here's 10 runs of "hackbench 50" using the two part 5 byte nop:

run 1
Time: 4.501
run 2
Time: 4.855
run 3
Time: 4.198
run 4
Time: 4.587
run 5
Time: 5.016
run 6
Time: 4.757
run 7
Time: 4.477
run 8
Time: 4.693
run 9
Time: 4.710
run 10
Time: 4.715
avg = 4.6509

And 10 runs using the above 5 byte nop:

run 1
Time: 4.832
run 2
Time: 5.319
run 3
Time: 5.213
run 4
Time: 4.830
run 5
Time: 4.363
run 6
Time: 4.391
run 7
Time: 4.772
run 8
Time: 4.992
run 9
Time: 4.727
run 10
Time: 4.825
avg = 4.8264

# cat /proc/cpuinfo
processor	: 0
vendor_id	: AuthenticAMD
cpu family	: 15
model		: 65
model name	: Dual-Core AMD Opteron(tm) Processor 2220
stepping	: 3
cpu MHz		: 2799.992
cache size	: 1024 KB
physical id	: 0
siblings	: 2
core id		: 0
cpu cores	: 2
apicid		: 0
initial apicid	: 0
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 pae mce cx8 apic sep mtrr pge mca 
cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt 
rdtscp lm 3dnowext 3dnow pni cx16 lahf_lm cmp_legacy svm extapic 
cr8_legacy
bogomips	: 5599.98
clflush size	: 64
power management: ts fid vid ttp tm stc

There's 4 of these.

Just to make sure, I ran the above nop test again:

[ this is reverse from the above runs ]

run 1
Time: 4.723
run 2
Time: 5.080
run 3
Time: 4.521
run 4
Time: 4.841
run 5
Time: 4.696
run 6
Time: 4.946
run 7
Time: 4.754
run 8
Time: 4.717
run 9
Time: 4.905
run 10
Time: 4.814
avg = 4.7997

And again the two part nop:

run 1
Time: 4.434
run 2
Time: 4.496
run 3
Time: 4.801
run 4
Time: 4.714
run 5
Time: 4.631
run 6
Time: 5.178
run 7
Time: 4.728
run 8
Time: 4.920
run 9
Time: 4.898
run 10
Time: 4.770
avg = 4.757

This time it was close, but still seems to have some difference.

heh, perhaps it's just noise.

-- Steve

Signature · 2 lines

Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Quoted 9 lines · Linus Torvalds

Quoted 5 lines · Jeremy Fitzhardinge

Quoted 1 line · Steven Rostedt

I wish we had a true 5 byte nop.

0x66 0x66 0x66 0x66 0x90

Quoted 4 lines

I don't think so. Multiple redundant prefixes can be really expensive on some uarchs.

A no-op that isn't cheap isn't a no-op at all, it's a slow-op.

A quick meaningless benchmark showed a slight perfomance hit.

Here's 10 runs of "hackbench 50" using the two part 5 byte nop:

run 1
Time: 4.501
run 2
Time: 4.855
run 3
Time: 4.198
run 4
Time: 4.587
run 5
Time: 5.016
run 6
Time: 4.757
run 7
Time: 4.477
run 8
Time: 4.693
run 9
Time: 4.710
run 10
Time: 4.715
avg = 4.6509

And 10 runs using the above 5 byte nop:

run 1
Time: 4.832
run 2
Time: 5.319
run 3
Time: 5.213
run 4
Time: 4.830
run 5
Time: 4.363
run 6
Time: 4.391
run 7
Time: 4.772
run 8
Time: 4.992
run 9
Time: 4.727
run 10
Time: 4.825
avg = 4.8264

# cat /proc/cpuinfo
processor	: 0
vendor_id	: AuthenticAMD
cpu family	: 15
model		: 65
model name	: Dual-Core AMD Opteron(tm) Processor 2220
stepping	: 3
cpu MHz		: 2799.992
cache size	: 1024 KB
physical id	: 0
siblings	: 2
core id		: 0
cpu cores	: 2
apicid		: 0
initial apicid	: 0
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 pae mce cx8 apic sep mtrr pge mca 
cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt 
rdtscp lm 3dnowext 3dnow pni cx16 lahf_lm cmp_legacy svm extapic 
cr8_legacy
bogomips	: 5599.98
clflush size	: 64
power management: ts fid vid ttp tm stc

There's 4 of these.

Just to make sure, I ran the above nop test again:

[ this is reverse from the above runs ]

run 1
Time: 4.723
run 2
Time: 5.080
run 3
Time: 4.521
run 4
Time: 4.841
run 5
Time: 4.696
run 6
Time: 4.946
run 7
Time: 4.754
run 8
Time: 4.717
run 9
Time: 4.905
run 10
Time: 4.814
avg = 4.7997

And again the two part nop:

run 1
Time: 4.434
run 2
Time: 4.496
run 3
Time: 4.801
run 4
Time: 4.714
run 5
Time: 4.631
run 6
Time: 5.178
run 7
Time: 4.728
run 8
Time: 4.920
run 9
Time: 4.898
run 10
Time: 4.770
avg = 4.757

This time it was close, but still seems to have some difference.

heh, perhaps it's just noise.

-- Steve

I also did some microbenchmarks on my Intel Xeon 64 bits, AMD64 and Intel Pentium 4 boxes to compare a baseline

So microbenchmarking this way will probably make some things look unrealistically good.

So for me the best strategy would be to get rid of the frame pointer
and ignore the nops. This unfortunately would require going away
from -pg and instead post process gcc output to insert "call mcount"
manually. But the nice advantage of that is that you could actually set up a custom table of callers built in a ELF section and with that you don't actually need the runtime patching (which is only
done currently because there's no global table of mcount calls),
but could do everything in stop_machine(). Without
runtime patching you also don't need single part nops.

I think that would be the best option. I especially like it because it would prevent forcing frame pointer which seems to be costlier than any kinds of nosp.

How would you deal with inlines? Using debug information?

Quoted 2 lines

How would you deal with inlines? Using debug information?

-pg already ignores inlines, so they aren't even traced today.

It pretty much has to, assume an inline gets spread out by the global optimizer over the rest of the function, where would the mcount calls be inserted?

Quoted 2 lines

So microbenchmarking this way will probably make some things look unrealistically good.

Must be careful to miss the big picture here.

We have two assumptions here in this thread:

- Normal alternative() nops are relatively infrequent, typically in points with enough pipeline bubbles anyways, and it likely doesn't matter how they are encode. And also they don't have an issue with mult part instructions anyways because they're not patched at runtime, so always the best known can be used.

- The one case where nops are very frequent and matter and multipart is a problem is with ftrace noping out the call to mcount at runtime because that happens on every function entry.
Even there the overhead is not that big, but at least measurable in kernel builds.

Now the numbers have shown that just by not using frame pointer ( -pg right now implies frame pointer) you can get more benefit than what you lose from using non optimal nops.

So for me the best strategy would be to get rid of the frame pointer and ignore the nops. This unfortunately would require going away from -pg and instead post process gcc output to insert "call mcount" manually. But the nice advantage of that is that you could actually set up a custom table of callers built in a ELF section and with that you don't actually need the runtime patching (which is only done currently because there's no global table of mcount calls), but could do everything in stop_machine(). Without runtime patching you also don't need single part nops.

I think that would be the best option. I especially like it because it would prevent forcing frame pointer which seems to be costlier than any kinds of nosp.

-Andi

Sorry to ask, I feel I must be missing something, but I'm trying to figure out where you propose to add the "call mcount" ? In the caller or in the callee ?

Or is it a different scheme I don't see ? I am trying to figure out how you happen to do all that without dynamic code modification and manage not to hurt performance.

Quoted 3 lines

Sorry to ask, I feel I must be missing something, but I'm trying to figure out where you propose to add the "call mcount" ? In the caller or in the callee ?

callee like gcc. caller would be likely more bloated because there are more calls than functions. Also if it was at the callee more code would be needed because the function currently executed couldn't be gotten from stack directly.

Quoted 3 lines

Or is it a different scheme I don't see ? I am trying to figure out how you happen to do all that without dynamic code modification and manage not to hurt performance.

The dynamic code modification is only needed because there is no global table of the mcount call sites. So instead it discovers them at runtime, but that requires runtime save patching

With a custom call scheme one could just build up a table of call sites at link time using an ELF section and then when tracing is enabled/disabled always patch them all in one go in a stop_machine(). Then you wouldn't need parallel execution safe patching anymore and it doesn't matter what the nops look like.

The other advantage is that it would allow getting rid of the frame pointer.

-Andi

If a kernel thread is preempted in single-cpu mode right after the NOP (nop about to be turned into a lock prefix), then we CPU hotplug a CPU, and then the thread is scheduled back again, a SMP-unsafe atomic operation will be used on shared SMP variables, leading to corruption. No corruption would happen in the reverse case : going from SMP to UP is ok because we split a bit instruction into tiny pieces, which does not present this condition.

Changing the 0x90 (single-byte nop) currently used into a 0x3E DS segment override prefix should fix this issue. Since the default of the atomic instructions is to use the DS segment anyway, it should not affect the behavior.

Quoted 7 lines · Mathieu Desnoyers

If a kernel thread is preempted in single-cpu mode right after the NOP (nop
about to be turned into a lock prefix), then we CPU hotplug a CPU, and then the
thread is scheduled back again, a SMP-unsafe atomic operation will be used on
shared SMP variables, leading to corruption. No corruption would happen in

Quoted 8 lines

the
reverse case : going from SMP to UP is ok because we split a bit instruction
into tiny pieces, which does not present this condition. Changing the 0x90 (single-byte nop) currently used into a 0x3E DS segment override prefix should fix this issue. Since the default of the atomic instructions is to use the DS segment anyway, it should not affect the behavior.

I believe this should be okay. In 32-bit mode some of the security and hypervisor frameworks want to set segment limits, but I don't believe they ever would set DS and SS inconsistently, or that we'd handle a #GP versus an #SS differently (segment violations on the stack segment are #SS, not #GP.) To be 100% sure we'd have to pick apart the modr/m byte to figure out what the base register is but I think that's total overkill.

I have a vague notion that DS: prefixes came with a penalty on older CPUs, so we may want to do this only when CPU hotplug is enabled, to avoid penalizing older embedded systems.

-hpa

I believe this should be okay. In 32-bit mode some of the security and hypervisor frameworks want to set segment limits, but I don't believe they ever would set DS and SS inconsistently, or that we'd handle a #GP versus an #SS differently (segment violations on the stack segment are #SS, not #GP.) To be 100% sure we'd have to pick apart the modr/m byte to figure out what the base register is but I think that's total overkill.

That said, I wonder how useful it is to do the SMP->UP code transition. How often does a kernel go from being SMP to UP in a situation where we really care about the performance? And that won't be shortly be becoming SMP again anyway?

Quoted 6 lines · H. Peter Anvin

I believe this should be okay. In 32-bit mode some of the security and hypervisor frameworks want to set segment limits, but I don't believe they ever would set DS and SS inconsistently, or that we'd handle a #GP versus an #SS differently (segment violations on the stack segment are #SS, not #GP.) To be 100% sure we'd have to pick apart the modr/m byte to figure out what the base register is but I think that's total overkill.

The kernel sets ds and ss to the same selector, so they're always going to have the same underlying descriptor.

My only concern is whether there are any locked instructions which are explicitly using a cs: override for those odd corners of the kernel. I don't think so.

That said, I wonder how useful it is to do the SMP->UP code transition. How often does a kernel go from being SMP to UP in a situation where we really care about the performance? And that won't be shortly be becoming SMP again anyway?

J

A virtualized guest kernel could use that to limit its use of the overall machine CPU resources in different time periods. Policies can determine how many physical CPU a virtual machine can be tied to, and that may change depending on e.g. the workload or time of day. Having the ability to efficiently switch to UP for a long period of time seems important in this use-case.

Quoted 6 lines · Mathieu Desnoyers

A virtualized guest kernel could use that to limit its use of the overall machine CPU resources in different time periods. Policies can determine how many physical CPU a virtual machine can be tied to, and that may change depending on e.g. the workload or time of day. Having the ability to efficiently switch to UP for a long period of time seems important in this use-case.

Not very convinced. Unplugging cpus is a pretty coarse way to control resource use. There are lots of other mechanisms. And it's not like an uncontended lock is all that expensive these days...

J

I can't argue about the benefit of using VM CPU pinning to manage resources because I don't use it myself, but I ran some tests out of curiosity to find if uncontended locks were that cheap, and it turns out they aren't.

I can't argue about the benefit of using VM CPU pinning to manage resources because I don't use it myself, but I ran some tests out of curiosity to find if uncontended locks were that cheap, and it turns out they aren't. Here are the results :

Xeon 2.0GHz

Summary

make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %

1 CPU, replace smp lock prefixes with DS segment selector prefixes 1 CPU, noreplace-smp

Quoted 10 lines · Mathieu Desnoyers

I can't argue about the benefit of using VM CPU pinning to manage resources because I don't use it myself, but I ran some tests out of curiosity to find if uncontended locks were that cheap, and it turns out they aren't. Here are the results :
Xeon 2.0GHz
Summary
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %
1 CPU, replace smp lock prefixes with DS segment selector prefixes 1 CPU, noreplace-smp

For reference, could you also compare replace smp lock with NOPs?

-hpa

Quoted 13 lines · * H. Peter Anvin ([email protected]) wrote:

Quoted 11 lines · Mathieu Desnoyers

I can't argue about the benefit of using VM CPU pinning to manage resources because I don't use it myself, but I ran some tests out of curiosity to find if uncontended locks were that cheap, and it turns out they aren't. Here are the results :
Xeon 2.0GHz
Summary
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %
1 CPU, replace smp lock prefixes with DS segment selector prefixes 1 CPU, noreplace-smp

Quoted 4 lines

For reference, could you also compare replace smp lock with NOPs?

-hpa

Sure, here are the updated tables. Basically, they show no significant difference between the NOP and the DS segment selector prefix approaches.

Quoted 15 lines · Mathieu Desnoyers

Quoted 13 lines · * H. Peter Anvin ([email protected]) wrote:

Quoted 11 lines · Mathieu Desnoyers

I can't argue about the benefit of using VM CPU pinning to manage resources because I don't use it myself, but I ran some tests out of curiosity to find if uncontended locks were that cheap, and it turns out they aren't. Here are the results :
Xeon 2.0GHz
Summary
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %
1 CPU, replace smp lock prefixes with DS segment selector prefixes 1 CPU, noreplace-smp

Quoted 9 lines

Quoted 4 lines

For reference, could you also compare replace smp lock with NOPs?

-hpa

Sure, here are the updated tables. Basically, they show no significant difference between the NOP and the DS segment selector prefix approaches.

BTW, are you changing the initial prefix to DS too? Ie, are you doing a nop->lock->ds transition, or ds->lock->ds?

J

Quoted 25 lines · * Jeremy Fitzhardinge ([email protected]) wrote:

Quoted 23 lines · Mathieu Desnoyers

Quoted 20 lines · * H. Peter Anvin ([email protected]) wrote:

Quoted 12 lines · Mathieu Desnoyers

I can't argue about the benefit of using VM CPU pinning to manage resources because I don't use it myself, but I ran some tests out of curiosity to find if uncontended locks were that cheap, and it turns out they aren't. Here are the results :
Xeon 2.0GHz
Summary
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %
1 CPU, replace smp lock prefixes with DS segment selector prefixes 1 CPU, noreplace-smp

For reference, could you also compare replace smp lock with NOPs?

-hpa

Quoted 9 lines

Quoted 5 lines

Sure, here are the updated tables. Basically, they show no significant difference between the NOP and the DS segment selector prefix approaches.

BTW, are you changing the initial prefix to DS too? Ie, are you doing a nop->lock->ds transition, or ds->lock->ds?

J

Yeah, I thought about this case yesterday, good thing you ask.

include/asm-x86/alternative.h defines LOCK_PREFIX as :

#define LOCK_PREFIX \
                ".section .smp_locks,\"a\"\n"   \
                _ASM_ALIGN "\n"                 \
                _ASM_PTR "661f\n" /* address */ \
                ".previous\n"                   \
                "661:\n\tlock; "

So we have the locked instructions built into the kernel, not the nop'd one. Therefore, the only transition I am doing for my benchmarks is :

lock->ds

but I tried to switch back to SMP and it worked fine.

Ah, OK. I'd thought we started unlocked, but given that I've just been disassembling the kernel and looking at the lock prefixes, that's a bit of a braino on my part.

BTW, using the ds prefix allows us to undo the hack of dealing with locked instructions with exception handlers. There was a bug where if we do lock->nop, then the address of a faulting instruction changes, so we need exception records for both the locked and unlocked forms. Using ds means the instruction size doesn't change, so we only need one exception record. I don't remember off hand where that happens.

Quoted 9 lines · Jeremy Fitzhardinge

Ah, OK. I'd thought we started unlocked, but given that I've just been disassembling the kernel and looking at the lock prefixes, that's a bit of a braino on my part.
BTW, using the ds prefix allows us to undo the hack of dealing with locked instructions with exception handlers. There was a bug where if we do lock->nop, then the address of a faulting instruction changes, so we need exception records for both the locked and unlocked forms. Using ds means the instruction size doesn't change, so we only need one exception record.
I don't remember off hand where that happens.

Using %ds: rather than nop really seems to solve a whole lot of problems, and might even be faster to boot. It really sounds like a no-brainer.

-hpa

So should I wait a bit for more comments or straightforwardly submit this as a patch rather than RFC ?

Quoted 3 lines · Mathieu Desnoyers

So should I wait a bit for more comments or straightforwardly submit this as a patch rather than RFC ?

Looks like all the relevant people have reviewed it now, so I don't think there's much more to say.

J

I'm just worried about this comment from Harvey Harrison :

arch/x86/mm/fault.c : is_prefetch()

* Values 0x26,0x2E,0x36,0x3E are valid x86 prefixes.
* In X86_64 long mode, the CPU will signal invalid
* opcode if some of these prefixes are present so
* X86_64 will never get here anyway
*/

This comment refers to :

0x26 : ES segment override prefix
0x2E : CS segment override prefix
0x36 : SS segment override prefix
0x3E : DS segment override prefix

AMD documentation seems to indicate that these prefix will be null, not that the cpu would signal "invalid opcodes" :

"AMD 64-Bit Technology" A.7
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/x86-64_overview.pdf

"In 64-bit mode, the DS, ES, SS and CS segment-override prefixes have no effect. These four prefixes are no longer treated as segment-override prefixes in the context of multipleprefix rules. Instead, they are treated as null prefixes."

Intel does not seem to state anything particular about these prefixes for the 64-bit mode.

So, is this comment misleading, or is it using the term "invalid opcode" in a way that does not imply generating a fault ?

I'm just worried about this comment from Harvey Harrison :

arch/x86/mm/fault.c : is_prefetch()

* Values 0x26,0x2E,0x36,0x3E are valid x86 prefixes.
* In X86_64 long mode, the CPU will signal invalid
* opcode if some of these prefixes are present so
* X86_64 will never get here anyway

Quoted 4 lines · Mathieu Desnoyers

I'm just worried about this comment from Harvey Harrison :

arch/x86/mm/fault.c : is_prefetch()

Quoted 8 lines

* Values 0x26,0x2E,0x36,0x3E are valid x86
prefixes.
* In X86_64 long mode, the CPU will signal
invalid
* opcode if some of these prefixes are
present so
* X86_64 will never get here anyway

I would say that comment is wrong. But we'd never put a lock prefix on a prefetch, so you won't be added a ds prefix either.

Sure, here are the updated tables. Basically, they show no significant difference between the NOP and the DS segment selector prefix approaches.

Quoted 3 lines · Mathieu Desnoyers

Sure, here are the updated tables. Basically, they show no significant difference between the NOP and the DS segment selector prefix approaches.

Actually, unless I have blown my T-test completely, they show with a 80% and 74% confidence (respective for the two benchmarks) that the DS case is slightly *better* (0.26% and 0.20% better, respective), which makes it a no-brainer. Doing around 10 runs of each is likely to confirm this conclusion by pushing it into the 90+% interval.

Note that since the difference is so small, and so can also be due to some kind of systematic error (lower ambient temperature during the DS run making the disk drive slightly faster, what have you.)

-hpa

Quoted 3 lines · Mathieu Desnoyers

Sure, here are the updated tables. Basically, they show no significant difference between the NOP and the DS segment selector prefix approaches.

Actually, unless I have blown my T-test completely, they show with a 80% and 74% confidence (respective for the two benchmarks) that the DS case is slightly *better* (0.26% and 0.20% better, respective), which makes it a no-brainer. Doing around 10 runs of each is likely to confirm this conclusion by pushing it into the 90+% interval.

Note that since the difference is so small, and so can also be due to some kind of systematic error (lower ambient temperature during the DS run making the disk drive slightly faster, what have you.)

-hpa

I can't argue about the benefit of using VM CPU pinning to manage resources because I don't use it myself, but I ran some tests out of curiosity to find if uncontended locks were that cheap, and it turns out they aren't. Here are the results :

Xeon 2.0GHz

Summary

no lock prefix (s) with lock prefix (s) Speedup
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %

Quoted 4 lines

Xeon 2.0GHz

Quoted 6 lines

Summary

no lock prefix (s) with lock prefix (s) Speedup
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %

Yeah, that's more severe than I would have expected. Perhaps I have AMD numbers in my head.

Quoted 11 lines · Jeremy Fitzhardinge

Quoted 10 lines

Xeon 2.0GHz

Summary

no lock prefix (s) with lock prefix (s) Speedup
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %

Quoted 2 lines

Yeah, that's more severe than I would have expected. Perhaps I have AMD numbers in my head.

He doesn't specify what kind of Xeon it is (there are three completely different CPUs under the Xeon brand name: P3 Xeon, P4 Xeon, and Core 2 Xeon), but I think it's a P4 Xeon.

Netburst sucked in so many ways, and this is one of them.

Xeon cpuinfo :

processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Intel(R) Xeon(R) CPU E5405 @ 2.00GHz
stepping : 6
cpu MHz : 2000.126
cache size : 6144 KB
physical id : 0
siblings : 4
core id : 0
cpu cores : 4
apicid : 0
initial apicid : 0
fpu : yes
fpu_exception : yes

cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx lm constant_tsc arch_perfmon pebs bts rep_good pni monitor ds_cpl vmx tm2 ssse3 cx16 xtpr dca sse4_1 lahf_lm
bogomips : 4000.25
clflush size : 64
cache_alignment : 64
address sizes : 38 bits physical, 48 bits virtual
power management:

Quoted 4 lines

He doesn't specify what kind of Xeon it is (there are three completely different CPUs under the Xeon brand name: P3 Xeon, P4 Xeon, and Core 2 Xeon), but I think it's a P4 Xeon.

Netburst sucked in so many ways, and this is one of them.

I presume it's this one:

Quoted 2 lines

Xeon cpuinfo :

Quoted 5 lines

processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Intel(R) Xeon(R) CPU E5405 @ 2.00GHz

I've given up trying to remember what "E5405" might mean, but that feature list suggests a relatively modern microarchitecture.

Quoted 9 lines · Jeremy Fitzhardinge

Quoted 9 lines

Xeon 2.0GHz

Summary

no lock prefix (s) with lock prefix (s) Speedup
make -j1 kernel/ 33.94 +/- 0.07 34.91 +/- 0.27 2.8 %
hackbench 50 2.99 +/- 0.01 3.74 +/- 0.01 25.1 %

Quoted 2 lines

Yeah, that's more severe than I would have expected. Perhaps I have AMD numbers in my head.

He doesn't specify what kind of Xeon it is (there are three completely different CPUs under the Xeon brand name: P3 Xeon, P4 Xeon, and Core 2 Xeon), but I think it's a P4 Xeon.

Netburst sucked in so many ways, and this is one of them.

-hpa

Here are the specs. It's a brand new 64bits dual quad-core (Christmas in August) :-) None of the specs seems to talk about neither Core2 or Pentium 4 though. Those appellations seems to hold for desktop processors, not server processors...

Quoted 5 lines · Mathieu Desnoyers

Here are the specs. It's a brand new 64bits dual quad-core (Christmas in August) :-) None of the specs seems to talk about neither Core2 or Pentium 4 though. Those appellations seems to hold for desktop processors, not server processors...

Is it a Dell thingy? Turns out my main test box has exactly the same processor.

J

Quoted 10 lines · * Jeremy Fitzhardinge ([email protected]) wrote:

Quoted 6 lines · Mathieu Desnoyers

Here are the specs. It's a brand new 64bits dual quad-core (Christmas in August) :-) None of the specs seems to talk about neither Core2 or Pentium 4 though. Those appellations seems to hold for desktop processors, not server processors...

Is it a Dell thingy? Turns out my main test box has exactly the same processor.

Quoted 2 lines

J

Nope, it's a custom-made machine from a company in the Montreal area. It has a Supermicro X7DAL-E motherboard and, well, I got 16GB of ram in it. Pretty useful to take large traces.

Mathieu

Quoted 3 lines

Sorry to ask, I feel I must be missing something, but I'm trying to figure out where you propose to add the "call mcount" ? In the caller or in the callee ?

callee like gcc. caller would be likely more bloated because there are more calls than functions. Also if it was at the callee more code would be needed because the function currently executed couldn't be gotten from stack directly.

Quoted 3 lines

Or is it a different scheme I don't see ? I am trying to figure out how you happen to do all that without dynamic code modification and manage not to hurt performance.

The dynamic code modification is only needed because there is no global table of the mcount call sites. So instead it discovers them at runtime, but that requires runtime save patching

With a custom call scheme one could just build up a table of call sites at link time using an ELF section and then when tracing is enabled/disabled always patch them all in one go in a stop_machine(). Then you wouldn't need parallel execution safe patching anymore and it doesn't matter what the nops look like.

The other advantage is that it would allow getting rid of the frame pointer.

Quoted 2 lines

The other advantage is that it would allow getting rid of the frame pointer.

This is the only advantage that you have.

Quoted 3 lines · Mathieu Desnoyers

I also did some microbenchmarks on my Intel Xeon 64 bits, AMD64 and Intel Pentium 4 boxes to compare a baseline

Note that the biggest problems of a jump-based nop are likely to happen when there are I$ misses and/or when there are other jumps involved. Ie a some microarchitectures tend to have issues with jumps to jumps, or when there are multiple control changes in the same (possibly partial) cacheline because the instruction stream prediction may be predecoded in the L1 I$, and multiple branches in the same cacheline - or in the same execution cycle - can pollute that kind of thing.

So microbenchmarking this way will probably make some things look unrealistically good.

On the P4, the trace cache makes things even more interesting, since it's another level of I$ entirely, with very different behavior for the hit case vs the miss case.

And I$ misses for the kernel are actually fairly high. Not in microbenchmarks that tend to have very repetive behavior and a small I$ footprint, but in a lot of real-life loads the *bulk* of all action is in user space, and then the kernel side is often invoced with few loops (the kernel has very few loops indeed) and a cold I$.

So your numbers are interesting, but it would be really good to also get some info from Intel/AMD who may know about microarchitectural issues for the cases that don't show up in the hot-I$-cache environment.

Linus

Are we sure there aren't some good available 5-byte nops?

e.g. for 64-bit maybe 3e 48 8d 76 00

     for 32-bit maybe 3e 8d 74 26 00

Have the chip folks confirmed that exactly the set we have in asm-x86/nops.h are the only optimal ones?

I wish we had a true 5 byte nop. The alternative is a jmp 0, which is measurable. This is replacing mcount from a kernel compile with the -pg

Quoted 2 lines

I wish we had a true 5 byte nop. The alternative is a jmp 0, which is measurable. This is replacing mcount from a kernel compile with the -pg

Scary usage. How much is the difference?

BTW a good way to get most of that back would be to not use frame pointers if you have them enabled ;-) Unfortunately recently the "select FRAME_POINTER"s keep creeping all over so far too many kernels suffer from this slow mode now :-/

Funny, CONFIG_FTRACE happens to select that. Now the question is, would mcount work without it?

Quoted 2 lines

Funny, CONFIG_FTRACE happens to select that. Now the question is, would mcount work without it?

Not without fixing gcc first. It would work if gcc always called mcount the first thing before setting up the stack frame. Not sure why it doesn't do that.

Still do a benchmark of frame pointer vs no frame pointer kernel and you'll see, especially on a older CPUs without special hardware to avoid stack stalls (e.g. not Core2)

Quoted 3 lines · Andi Kleen

Quoted 2 lines

Funny, CONFIG_FTRACE happens to select that. Now the question is, would mcount work without it?

Quoted 3 lines

Not without fixing gcc first. It would work if gcc always called mcount the first thing before setting up the stack frame. Not sure why it doesn't do that.

I could take out the frame pointer option and pass in zero for the parent in such that case. But the parent is quite useful. But if it helps with performance, it may be worth doing this.

Quoted 2 lines

I wish we had a true 5 byte nop. The alternative is a jmp 0, which is measurable. This is replacing mcount from a kernel compile with the -pg

Scary usage. How much is the difference?

BTW a good way to get most of that back would be to not use frame pointers if you have them enabled ;-) Unfortunately recently the "select FRAME_POINTER"s keep creeping all over so far too many kernels suffer from this slow mode now :-/

The do_something_silly had an mcount pointer to it. I put in printks in the ftrace enabled code to see where this was preempted. It was preempted several times before and after the nops, but never at either nop.

Maybe I didn't run it enough (almost 2 hours), but perhaps it is very unlikely to be preempted at a nop if there's something coming up next.

Yes a string of nops may be preempted, but perhaps only two nops followed by an actual command might be skipped quickly.

I'll write some hacks to look at where it is preempted in the scheduler itself, and see if I see it preempting at the second nop ever.

Index: linux-tip.git/arch/x86/kernel/ftrace.c
===================================================================

arch/x86/kernel/ftrace.c +7 -0

@@ -127,6 +127,46 @@ notrace int ftrace_mcount_set(unsigned l
 	return 0;
 }
 
+static const unsigned char *second_nop;
+
+void arch_ftrace_pre_enable(void)
+{
+	struct task_struct *g, *p;
+	unsigned long **ip;
+

[ updated patch ]

Quoted 6 lines · Steven Rostedt

The do_something_silly had an mcount pointer to it. I put in printks in the ftrace enabled code to see where this was preempted. It was preempted several times before and after the nops, but never at either nop.

Quoted 8 lines

Maybe I didn't run it enough (almost 2 hours), but perhaps it is very unlikely to be preempted at a nop if there's something coming up next.

Yes a string of nops may be preempted, but perhaps only two nops followed by an actual command might be skipped quickly.

I'll write some hacks to look at where it is preempted in the scheduler itself, and see if I see it preempting at the second nop ever.

I put that code in the scheduler and it does indeed preempt in the nops! It also uncovered a nasty bug I had in my code:

[...]

Quoted 15 lines

Index: linux-tip.git/arch/x86/kernel/ftrace.c
===================================================================

arch/x86/kernel/ftrace.c +7 -0

@@ -127,6 +127,46 @@ notrace int ftrace_mcount_set(unsigned l
 	return 0;
 }
 
+static const unsigned char *second_nop;
+
+void arch_ftrace_pre_enable(void)
+{
+	struct task_struct *g, *p;
+	unsigned long **ip;
+

[...]

arch/x86/kernel/ftrace.c notrace int ftrace_mcount_set(unsigned l · line 164

Quoted 6 lines

arch/x86/kernel/ftrace.c +6 -0

+		ip = task_thread_info(p)->ip;
+		if (!ip)
+			continue;
+		if (memcmp(*ip, second_nop, x86_nop5_part2) == 0)
+			/* Match, move the ip forward */
+			*ip += x86_nop5_part2;

Notice the bug? Hint, *ip is of type unsigned long *.

Here's the updated fix:

Signed-off-by Steven Rostedt <[email protected]>

---
 arch/x86/kernel/alternative.c    |   29 ++++++++++++++++++++-------
 arch/x86/kernel/asm-offsets_32.c |    1 
 arch/x86/kernel/asm-offsets_64.c |    1 
 arch/x86/kernel/entry_32.S       |    4 +++
 arch/x86/kernel/entry_64.S       |    4 +++
 arch/x86/kernel/ftrace.c         |   41 +++++++++++++++++++++++++++++++++++++++
 include/asm-x86/ftrace.h         |    5 ++++
 include/asm-x86/thread_info.h    |    4 +++
 kernel/trace/ftrace.c            |   12 +++++++++++
 9 files changed, 94 insertions(+), 7 deletions(-)

Index: linux-tip.git/arch/x86/kernel/alternative.c
===================================================================

arch/x86/kernel/alternative.c +22 -7

@@ -140,13 +140,26 @@ static const unsigned char *const p6_nop
 };
 #endif
 
+/*
+ * Some versions of x86 CPUs have a two part NOP5. This
+ * can break ftrace if a process is preempted between
+ * the two. ftrace needs to know what the second nop
+ * is to handle this case.
+ */
+int x86_nop5_part2;
+
 #ifdef CONFIG_X86_64
 
 extern char __vsyscall_0;
 const unsigned char *const *find_nop_table(void)
 {
-	return boot_cpu_data.x86_vendor != X86_VENDOR_INTEL ||
-	       boot_cpu_data.x86 < 6 ? k8_nops : p6_nops;
+	if (boot_cpu_data.x86_vendor != X86_VENDOR_INTEL ||
+	    boot_cpu_data.x86 < 6) {
+		x86_nop5_part2 = 2; /* K8_NOP2 */
+		return k8_nops;
+	} else
+		/* keep k86_nop5_part2 NULL */
+		return p6_nops;
 }
 
 #else /* CONFIG_X86_64 */

@@ -154,12 +167,13 @@ const unsigned char *const *find_nop_tab
 static const struct nop {
 	int cpuid;
 	const unsigned char *const *noptable;
+	int nop5_part2;
 } noptypes[] = {
-	{ X86_FEATURE_K8, k8_nops },
-	{ X86_FEATURE_K7, k7_nops },
-	{ X86_FEATURE_P4, p6_nops },
-	{ X86_FEATURE_P3, p6_nops },
-	{ -1, NULL }
+	{ X86_FEATURE_K8, k8_nops, 2},
+	{ X86_FEATURE_K7, k7_nops, 1 },
+	{ X86_FEATURE_P4, p6_nops, 0 },
+	{ X86_FEATURE_P3, p6_nops, 0 },
+	{ -1, NULL, 0 }
 };
 
 const unsigned char *const *find_nop_table(void)

@@ -170,6 +184,7 @@ const unsigned char *const *find_nop_tab
 	for (i = 0; noptypes[i].cpuid >= 0; i++) {
 		if (boot_cpu_has(noptypes[i].cpuid)) {
 			noptable = noptypes[i].noptable;
+			x86_nop5_part2 = noptypes[i].nop5_part2;
 			break;
 		}
 	}

Index: linux-tip.git/arch/x86/kernel/asm-offsets_32.c
===================================================================

arch/x86/kernel/asm-offsets_32.c +1 -0

@@ -59,6 +59,7 @@ void foo(void)
 	OFFSET(TI_restart_block, thread_info, restart_block);
 	OFFSET(TI_sysenter_return, thread_info, sysenter_return);
 	OFFSET(TI_cpu, thread_info, cpu);
+	OFFSET(TI_ip, thread_info, ip);
 	BLANK();
 
 	OFFSET(GDS_size, desc_ptr, size);

Index: linux-tip.git/arch/x86/kernel/asm-offsets_64.c
===================================================================

arch/x86/kernel/asm-offsets_64.c +1 -0

@@ -41,6 +41,7 @@ int main(void)
 	ENTRY(addr_limit);
 	ENTRY(preempt_count);
 	ENTRY(status);
+	ENTRY(ip);
 #ifdef CONFIG_IA32_EMULATION
 	ENTRY(sysenter_return);
 #endif

Index: linux-tip.git/arch/x86/kernel/entry_32.S
===================================================================

arch/x86/kernel/entry_32.S +4 -0

@@ -304,7 +304,11 @@ need_resched:
 	jz restore_all
 	testl $X86_EFLAGS_IF,PT_EFLAGS(%esp)	# interrupts off (exception path) ?
 	jz restore_all
+	lea PT_EIP(%esp), %eax
+	movl %eax, TI_ip(%ebp)
 	call preempt_schedule_irq
+	GET_THREAD_INFO(%ebp)
+	movl $0, TI_ip(%ebp)
 	jmp need_resched
 END(resume_kernel)
 #endif

Index: linux-tip.git/arch/x86/kernel/entry_64.S
===================================================================

arch/x86/kernel/entry_64.S +4 -0

@@ -837,7 +837,11 @@ ENTRY(retint_kernel)
 	jnc  retint_restore_args
 	bt   $9,EFLAGS-ARGOFFSET(%rsp)	/* interrupts off? */
 	jnc  retint_restore_args
+	leaq RIP-ARGOFFSET(%rsp), %rax
+	movq %rax, TI_ip(%rcx)
 	call preempt_schedule_irq
+	GET_THREAD_INFO(%rcx)
+	movq $0, TI_ip(%rcx)
 	jmp exit_intr
 #endif	
 

Index: linux-tip.git/arch/x86/kernel/ftrace.c
===================================================================

arch/x86/kernel/ftrace.c +41 -0

@@ -127,6 +127,44 @@ notrace int ftrace_mcount_set(unsigned l
 	return 0;
 }
 
+static const unsigned char *second_nop;
+
+void arch_ftrace_pre_enable(void)
+{
+	struct task_struct *g, *p;
+	void **ip;
+
+	if (!second_nop)
+		return;
+
+	/*
+	 * x86 has a two part nop to handle 5 byte instructions.
+	 * If a task was preempted after the first nop, and has
+	 * not ran the second nop, if we modify the code, we can
+	 * crash the system. Thus, we will look at all the tasks
+	 * and if any of them was preempted and will run the
+	 * second nop next, we simply move their ip pointer past
+	 * the second nop.
+	 */
+
+	/*
+	 * Don't need to grab the task list lock, we are running
+	 * in kstop_machine
+	 */
+	do_each_thread(g, p) {
+		/*
+		 * In entry.S we save the ip when a task is preempted
+		 * and reset it when it is back running.
+		 */
+		ip = (void **)task_thread_info(p)->ip;
+		if (!ip)
+			continue;
+		if (memcmp(*ip, second_nop, x86_nop5_part2) == 0)
+			/* Match, move the ip forward */
+			*ip += x86_nop5_part2;
+	} while_each_thread(g, p);
+}
+
 int __init ftrace_dyn_arch_init(void *data)
 {
 	const unsigned char *const *noptable = find_nop_table();

@@ -137,5 +175,8 @@ int __init ftrace_dyn_arch_init(void *da
 
 	ftrace_nop = (unsigned long *)noptable[MCOUNT_INSN_SIZE];
 
+	if (x86_nop5_part2)
+		second_nop = noptable[x86_nop5_part2];
+
 	return 0;
 }

Index: linux-tip.git/include/asm-x86/ftrace.h
===================================================================

include/asm-x86/ftrace.h +5 -0

@@ -17,6 +17,11 @@ static inline unsigned long ftrace_call_
 	 */
 	return addr - 1;
 }
+
+extern int x86_nop5_part2;
+extern void arch_ftrace_pre_enable(void);
+#define ftrace_pre_enable arch_ftrace_pre_enable
+
 #endif
 
 #endif /* CONFIG_FTRACE */

Index: linux-tip.git/include/asm-x86/thread_info.h
===================================================================

include/asm-x86/thread_info.h +4 -0

@@ -29,6 +29,9 @@ struct thread_info {
 	__u32			cpu;		/* current CPU */
 	int			preempt_count;	/* 0 => preemptable,
 						   <0 => BUG */
+	unsigned long		**ip;		/* pointer to ip on stackwhen
+						   preempted
+						*/
 	mm_segment_t		addr_limit;
 	struct restart_block    restart_block;
 	void __user		*sysenter_return;

@@ -47,6 +50,7 @@ struct thread_info {
 	.flags		= 0,			\
 	.cpu		= 0,			\
 	.preempt_count	= 1,			\
+	.ip		= NULL,			\
 	.addr_limit	= KERNEL_DS,		\
 	.restart_block = {			\
 		.fn = do_no_restart_syscall,	\

Index: linux-tip.git/kernel/trace/ftrace.c
===================================================================

kernel/trace/ftrace.c +12 -0

@@ -32,6 +32,10 @@
 
 #include "trace.h"
 
+#ifndef ftrace_pre_enable
+# define ftrace_pre_enable() do { } while (0)
+#endif
+
 /* ftrace_enabled is a method to turn ftrace on or off */
 int ftrace_enabled __read_mostly;
 static int last_ftrace_enabled;

@@ -500,6 +504,14 @@ static void ftrace_replace_code(int enab
 	else
 		new = ftrace_nop_replace();
 
+	/*
+	 * Some archs *cough*x86*cough* have more than one nop to cover
+	 * the call to mcount. In these cases, special care must be taken
+	 * before we start converting nops into calls.
+	 */
+	if (enable)
+		ftrace_pre_enable();
+
 	for (pg = ftrace_pages_start; pg; pg = pg->next) {
 		for (i = 0; i < pg->index; i++) {
 			rec = &pg->records[i];

Hi Steven,

I'm actually a bit worried about this scheduler-centric approach. The problem is that any trap that could be generated in the middle of the 3/2 nops (think of performance counters if the APIC is set as a trap gate) which would stack an interruptible trap handler on top of those instructions would lead to having a return IP pointing in the wrong spot, but because the scheduler would interrupt the trap handler and not the trapped code, it would not detect this.

I am not sure wheter we do actually have the possibility to have these interruptible trap handlers considering the way the kernel sets up the gates, but I think the "let's figure out where the IP stopped" approach is a bit complex and fragile.

Trying to find a fast atomic 5-bytes nop, involving the microarchitecture guys, seems like a better approach to me.

Can a processor be preempted in a middle of nops?

What do nops do for a processor?

Can it skip them nicely in one shot?

I'm assuming that jmp is more expensive than the nops because otherwise a jmp 0 would have been used as a 5 byte nop.

Hmm, good point. Unless...

Can a processor be preempted in a middle of nops? What do nops do for a processor? Can it skip them nicely in one shot?

This means I'll have to do the benchmarks again, and see what the performance difference of a jmp and a nop is significant. I'm thinking that if the processor can safely skip nops without any type of processing, this may be the reason that nops are better than a jmp. A jmp causes the processor to do a little more work.

Quoted 6 lines · Mathieu Desnoyers

kstop_machine does not guarantee that you won't have _any_ thread preempted with IP pointing exactly in the middle of your instructions _before_ the modification scheduled back in _after_ the modification and thus causing an illegal instruction.

Still buggy. :/

Hmm, good point. Unless...

Quoted 6 lines · On Saturday 09 August 2008 04:41:06 Steven Rostedt wrote:

Quoted 5 lines · Mathieu Desnoyers

kstop_machine does not guarantee that you won't have _any_ thread preempted with IP pointing exactly in the middle of your instructions _before_ the modification scheduled back in _after_ the modification and thus causing an illegal instruction.

Quoted 3 lines

Quoted 1 line

Still buggy. :/

Hmm, good point. Unless...

You can walk the task list and fix them up, if you have to. Of course, this could be extremely slow with a million threads. Maybe just walking the runqueues would be sufficient?

Now, this was no easy task. We needed to add a section to every object file with a list of pointers to the call sites to mcount. The idea I came up with was to make a tmp.s file for every object just after it is compiled. This tmp.s would then be compiled and relinked into the original object. The tmp.s file would have something like:

.section __mcount_loc,"a",@progbits
.quad location_of_mcount1
.quad location_of_mcount2
(etc)

By running objdump on the object file we can find the offsets into the sections that the functions are called.

For example, looking at hrtimer.o:

Disassembly of section .text:

0000000000000000 <hrtimer_init_sleeper>:

       0:       55                      push   %rbp
       1:       48 89 e5                mov    %rsp,%rbp
       4:       e8 00 00 00 00          callq  9 <hrtimer_init_sleeper+0x9>
                        5: R_X86_64_PC32        mcount+0xfffffffffffffffc

[...]

the '5' in the '5: R_X86_64_PC32' is the offset that the mcount relocation is to be done for the call site. This offset is from the .text section, and not necessarily, from the function. If we look further we see:

000000000000001e <ktime_add_safe>:

      1e:       55                      push   %rbp
      1f:       48 89 e5                mov    %rsp,%rbp
      22:       e8 00 00 00 00          callq  27 <ktime_add_safe+0x9>
                        23: R_X86_64_PC32       mcount+0xfffffffffffffffc

This mcount call site is 0x23 from the .text section, and obviously not from the ktime_add_safe.

If we make a tmp.s that has the following:

.section __mcount_loc,"a",@progbits
.quad hrtimer_init_sleeper + 0x5
.quad hrtimer_init_sleeper + 0x23

We have a section with the locations of these two call sites. After the final linking, they will point to the actual address used.

All that would need to be done is:

gcc -c tmp.s -o tmp.o
ld -r tmp.o hrtimer.o -o tmp_hrtime.o
mv tmp_hrtimer.o hrtimer.o

Easy as that! Not quite. What happens if that first function in the section is a static function? That is, the symbol for the function is local to the object. If for some reason hrtimer_init_sleeper is static, the tmp_hrtimer.o would have two symbols for hrtimer_init_sleeper. One local and one global.

But we can be even more evil with this idea. We can do crazy things with objcopy to solve it for us.

  objcopy --globalize-symbol hrtimer_init_sleeper hrtimer.o tmp_hrtimer.o

Now the hrtimer_init_sleeper would be global for linking.

ld -r tmp_hrtimer.o tmp.o -o tmp2_hrtimer.o

Now the tmp.o could use the same global hrtimer_init_sleeper symbol. But we have tmp2_hritmer.o that has the tmp.o and tmp_hrtimer.o symbols, but we cant just blindly convert local symbols to globals.

The solution is simply put it back to local.

  objcopy --localize-symbol hrtimer_init_sleeper tmp2_hrtimer.o hrtimer.o

Now our hrtimer.o file has our __mcount_loc section and the reference to hrtimer_init_sleeper will be resolved.

This is a bit complex to do in shell scripting and Makefiles, so I wrote a well documented recordmcount.pl perl script, that will do the above all in one place.

With this new update, we can work to kill that kernel thread "ftraced"!

This patch set ports to x86_64 and i386, the other archs will still use the daemon until they are converted over.

I tested this on both x86_64 and i386 with and without CONFIG_RELOCATE set.

Quoted 11 lines · Steven Rostedt

Now, this was no easy task. We needed to add a section to every object file with a list of pointers to the call sites to mcount. The idea I came up with was to make a tmp.s file for every object just after it is compiled. This tmp.s would then be compiled and relinked into the original object. The tmp.s file would have something like:

.section __mcount_loc,"a",@progbits
.quad location_of_mcount1
.quad location_of_mcount2
(etc)

I have a few concerns about this scheme:

One is that you assume that all text is in a .text section, and that the offsets you compute on a per-section basis are going to be valid in the final kernel image. At the very least you should make each offset relative to its own function rather than inter-function.

But it seems pretty fragile overall. Things like -ffunction-sections and section gc will invalidate the table you build up.

It seems to me that you can acheive the same effect by:

1. link vmlinux with "ld -q", which will leave the relocation information intact in the final object
2. use "readelf -r" to extract the relocation info, find the references to mcount and build a table
3. link that table into the kernel image
4. repeat to get a stable result

Note that steps 2-4 are identical to kallsyms, both in intent and detail. The only difference is the precise table you build and the command you use to extract the info from the kernel. From a quick peek at the way Makefile implements kallsyms, it looks to me like it would be fairly easy to generalize so that you can do the mcount reloc processing in the same relink passes as kallsyms with minimal overhead on the kernel build time.

It just seems incredibly fiddly to be doing all this per-object.

This doesn't seem any less complex than what I did. With this, I would have to come up with another way to handle modules. This will make things a lot more complex.

Quoted 3 lines

This doesn't seem any less complex than what I did. With this, I would have to come up with another way to handle modules. This will make things a lot more complex.

The scheme you've implemented can apply fine to a .ko file after it's made. They are just .o's really. It is presumably faster to do one step per final .ko rather than many tiny ones (per source file).

That might be a benefit to doing it all at the end for vmlinux too. I think the best way would be to have a vmlinux.o that we actually use in the link, rather than just analyzing and discarding. Then you can just do your existing hack on vmlinux.o before it's linked into vmlinux.

Quoted 9 lines · Roland McGrath

The scheme you've implemented can apply fine to a .ko file after it's made. They are just .o's really. It is presumably faster to do one step per final .ko rather than many tiny ones (per source file).

That might be a benefit to doing it all at the end for vmlinux too. I think the best way would be to have a vmlinux.o that we actually use in the link, rather than just analyzing and discarding. Then you can just do your existing hack on vmlinux.o before it's linked into vmlinux.

OK, I am playing with this. And you are right, it does work with vmlinux.o file. It adds almost another minute to the build anytime something is changed. Where the per-object way may take longer doing a full build, but does not add that extra minute ever build.

Which would people prefer? I little longer full build and do the modification on every object, or have a shorter full build, but every build will take that extra minute to do?

Note, if you have DYNMAIC_FTRACE disabled, this is a nop, and will _not_ affect you.

Quoted 4 lines · Roland McGrath

Quoted 3 lines

This doesn't seem any less complex than what I did. With this, I would have to come up with another way to handle modules. This will make things a lot more complex.

Quoted 8 lines

The scheme you've implemented can apply fine to a .ko file after it's made. They are just .o's really. It is presumably faster to do one step per final .ko rather than many tiny ones (per source file).

That might be a benefit to doing it all at the end for vmlinux too. I think the best way would be to have a vmlinux.o that we actually use in the link, rather than just analyzing and discarding. Then you can just do your existing hack on vmlinux.o before it's linked into vmlinux.

OK, I am playing with this. And you are right, it does work with vmlinux.o file. It adds almost another minute to the build anytime something is changed. Where the per-object way may take longer doing a full build, but does not add that extra minute ever build.

Which would people prefer? I little longer full build and do the modification on every object, or have a shorter full build, but every build will take that extra minute to do?

Quoted 3 lines · Steven Rostedt

Which would people prefer? I little longer full build and do the modification on every object, or have a shorter full build, but every build will take that extra minute to do?

I have a very strong preference to do it per obj rather than at the end, that way it can be distributed and make these fancy smp boxen useful.

Bonus points if you can make distcc dig it.

The vmlinux link path is the thing that is killing build performance, anything to shorten that is golden, anything increasing it needs _very_ good justification.

Quoted 3 lines

This doesn't seem any less complex than what I did. With this, I would have to come up with another way to handle modules. This will make things a lot more complex.

The scheme you've implemented can apply fine to a .ko file after it's made. They are just .o's really. It is presumably faster to do one step per final .ko rather than many tiny ones (per source file).

That might be a benefit to doing it all at the end for vmlinux too. I think the best way would be to have a vmlinux.o that we actually use in the link, rather than just analyzing and discarding. Then you can just do your existing hack on vmlinux.o before it's linked into vmlinux.

You see, the reason for this is that for ftrace to maintain performance when configured in but disabled, it would need to change all the locations that called "mcount" (enabled with the gcc -pg option) into nops. The "-pg" option in gcc sets up a function profiler to call this function called "mcount". If you simply have "mcount" return, it will still add 15 to 18% overhead in performance. Changing all the calls to nops moved the overhead into noise.

To get rid of this, I had the mcount code record the location that called it. Later, the "ftraced" daemon would wake up and look to see if any new functions were recorded. If so, it would call kstop_machine and convert the calls to "nops". We needed kstop_machine because bad things happen on SMP if you modify code that happens to be in the instruction cache of another CPU.

Quoted 8 lines · Steven Rostedt

You see, the reason for this is that for ftrace to maintain performance when configured in but disabled, it would need to change all the locations that called "mcount" (enabled with the gcc -pg option) into nops. The "-pg" option in gcc sets up a function profiler to call this function called "mcount". If you simply have "mcount" return, it will still add 15 to 18% overhead in performance. Changing all the calls to nops moved the overhead into noise.

Quoted 6 lines

To get rid of this, I had the mcount code record the location that called it. Later, the "ftraced" daemon would wake up and look to see if any new functions were recorded. If so, it would call kstop_machine and convert the calls to "nops". We needed kstop_machine because bad things happen on SMP if you modify code that happens to be in the instruction cache of another CPU.

Is this new framework needed for x86 specific reasons only? From what I gathered here, ftraced defers mcount patching simply because there's no way to update a 5-byte nop atomically. If so, why can't mcount site patching be left to arch specific ftrace code? For !SMP or archs which generate word sized mcount branch calls (e.g, ARM) is there really no way to patch mcount sites synchronously from inside ftrace_record_ip by disabling interrupts?

Dynamically modifying text that might be in the pipeline on another CPU may or may not be dangerous on all archs.

The fix here is to convert the mcount calls to nops at boot up. This is really ideal on all archs. This means we know ever mcount call, and we get rid of the requirement that we need to run the code once before we can trace it.

The kstop_machine is now only left at the start and stop of tracing.

Quoted 2 lines · Steven Rostedt

Dynamically modifying text that might be in the pipeline on another CPU may or may not be dangerous on all archs.

Kprobes leaves this mess for individual archs to handle (see arch_arm_kprobe). What would be nice to have is an explanation as to which archs are safe from this and under what conditions. Also, for !SMP, this boot-time patching approach and the associated build time paraphernalia would simply be a bloat. There we can simply have a daemonless ftrace which patches mcount sites synchronously. Why not let each arch have this hinge on CONFIG_SMP?

Quoted 5 lines

The fix here is to convert the mcount calls to nops at boot up. This is really ideal on all archs. This means we know ever mcount call, and we get rid of the requirement that we need to run the code once before we can trace it.

This solution indeed would fit all archs well but for some it may be an overkill (or is it?...I'd like to know that :-\ ).

Oh and as you pointed out, it would mean that we have to no longer run the code before starting to trace it. But why don't we do that now? How about calling the tracer from ftrace_record_ip? All we need to do is pass along the parent_ip from mcount.

Quoted 2 lines

The kstop_machine is now only left at the start and stop of tracing.

This a nice fix. I'm just looking to find out what the self modifying code problem here translates to on different archs for my own understanding :-)

One of the things I tried to do was to make ftrace port easily to all archs. David Miller ported it to Sparc64 in 20 minutes and that was mostly compiling. Doing a kprobe fix would require much more knowledge to each arch and more prone to errors.

Quoted 2 lines

This solution indeed would fit all archs well but for some it may be an overkill (or is it?...I'd like to know that :-\ ).

It is not an issue at all. The mcount list is discarded with the init section, and the change to nops is relatively fast. We do make a list of all entries anyway, so that we can pick and choose which functions we want to enable tracing on.

I want ftrace_record_ip to be as fast as possible, and also having it call the registered function means we need to test if it was set in the filter too. This is too much for what record_ip does. And as I said, doing it all on boot up would be best.