Hi Ingo,
Here is the update to the jump patching optimization taking care of Peter's

comments about register liveliness and instruction re-use by gcc optimizations.

A good thing : it actually simplifies the code. Unfortunately, it adds 3 bytes

to the instructions in i-cache because I now have to use a 5-bytes mov

instruction so I can replace it with a 5-bytes jump. Therefore, 9 bytes are

added to rather small functions (5-bytes mov + 2-bytes test + 2 bytes

conditional branch) and 13 bytes are added to larger functions which needs a 6

bytes conditional branch at the branch site.
Instead of having to execute a sequence of nop, nop and jump, we now only have

to execute the near jump, which jumps either at the address following the

conditional branch or at the target address of the conditional branch, depending

on the immediate value variable state.
Thanks to Peter for the review.
Those two patches apply on top of sched-devel.git.
Mathieu
--

Mathieu Desnoyers

Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal

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

--

Just in case someone gets the wrong idea...
I still think this is the completely wrong approach.
I'd use stronger terms, but Al Viro would sue me for copyright infringement.
	-hpa

--

hm, can it result in a broken kernel? If yes, how? Or are your

objections more higher level?
i actually like that we end up with something rather NOP-ish, with some

mild 'ambient' impact due to the extra constraints that state value

visibility brings with it. The in-source impact of the markers is

minimal, especially with Peter Zijstra's wrappers. The scheduler markers

at least are also expected to stay pretty stable as well.
the syscall markers should be done less intrusively - and i think they

can be done less intrusively.
but we need to get past this current impasse, the optimizations that

Mathieu has done to markers are pretty impressive so far. The overhead

is not zero, but it gets quite close to it and the SystemTap and kprobes 
it would clearly fall under the Fair Use Doctrine and perhaps also under

the Doctrine of Severe Necessities, so dont be shy!
	Ingo

--

My objections are higher level, I believe the current code is (a)

painfully complex, and I'd rather not see it in the kernel, and (b) the

wrong thing anyway.
Put a 5-byte nop in as the marker, and patch it with a call instruction,

out of line, to a collector function.
	-hpa

--

the counter argument was that by specific sched.o analysis, this results

in slower code. The reason is that the "function call parameter

preparation" halo around that 5-byte patch site is larger than that

single conditional branch operation to an offline place of the current

function is.
i.e. the current optimized marker approach does roughly this:
  [ .... fastpath head ....       ]

  [ immediate value instruction   ]  --->

  [ branch instruction            ]  ---> these two get NOP-ed out

  [ .... fastpath tail ....       ]

  [ ............................. ]

  [ ... offline area ............ ]

  [ ... parameter preparation ... ]

  [ ... marker call ............. ]
your proposed 5-byte call NOP approach (which btw. was what i proposed

multiple times in the past 2 years) would do this:
  [ .... fastpath head ......     ]

  [ ... parameter preparation ... ]

  [ ....   5-byte CALL .......... ]  ---> NOP-ed out

  [ .... fastpath tail .......... ]

  [ ............................. ]
in the first case we have little "marker parameter/value preparation"

cost: it all happens in the 'offline area' _by GCC_. I.e. the fastpath

is relatively undisturbed.
in the latter case, all the 'parameter preparation' phase has to happen

at around the 5-byte CALL site, in the fastpath. This, in the specific,

assembly level analysis of sched.o, was shown by Matthieu to be a

pessimisation. We are better off by inserting that conditional and

letting gcc generate the call, than by forcing it in the middle of the

fastpath - even if we end up NOP-ing out the call.
wrt. complexity i agree with you - if the current optimization cannot be

made correctly we have to fall back to a simpler variant, even if it's

slower.
	Ingo

--

No, that's not what I'm proposing at all (and would indeed be bogus.)
What I'm proposing is:
 >   [ .... fastpath head ......     ]

 >   [ ....   5-byte CALL .......... ]  ---> NOP-ed out

 >   [ .... fastpath tail .......... ]

 >   [ ............................. ]
The call site is created with an asm() statement as opposed to a gcc

function call; it is up to the logging function to take the state and

mangle it into whatever format it wants to; the debugging information

(e.g. DWARF) should tell it all it needs to know about how the

register/memory state maps onto the C state.  This mapping can either be

done online, with a small piece of dynamic code, or offline (although

offline makes it tricky to know what memory tems to gather.)
For pieces of data which would be dead at the call site, one can add "g"

annotations to the asm() statement to force it to be live without

forcing it to be present in any particular location.
	-hpa

--

that would be rather impractical as we'd force DEBUG_INFO builds on

anyone (it's HUGE) just to do some trivial tracing. Look at the ftrace

plugin usage model - it wants to be widely available and easy to use.
	Ingo

--

Otherwise you're forcing everyone to take the cost of additional cache

footprint, plus optimizer interference, just because they might want to

possibly do some trivial tracing.  DEBUG_INFO is The Right Thing for

this, as it carries all the information you may want in a well-defined

format.  You don't necessarily have to keep all this information around,

of course; you can distill out the information for the trace sites at

compile time and keep a tracer information file, after which you can

strip the information.
There is actually yet another alternative, though, which is to build the

tracer at compile time.  The tricky part of this is that it almost

requires inserting a preprocessor before the assembler, and use really

ugly asm() macros to extract the very information that the debug format

is designed explicitly to extract!
Personally, I think requiring DEBUG_INFO is a helluva lot less ugly than

these branch hacks.
	-hpa

--

Peter, do you have something like the following code in mind ?
I think the main differences between the code snippet down here and the

markers is that markers rely on the compiler to generate the stack

setup, and have this code a little bit closer to the function than what

I propose here, where I put the stack setup code in a "farfaraway"

section.  Moreover, markers are much simpler than what I show here.

And actually, markers can be deployed portably, with

architecture-specific optimizations refined later. This has to be

implemented all up front for any traced architecture. In addition,

dealing with weird types like unsigned long long can become a pain.

Also, due to fact that we are asking the compiler to put keep some

variables live in registers, I would be tempted to embed this in a block

controlled by an if() statement (conditional branch, like I use for the

markers) so we don't have to pay the penality of populating the

registers when not required if there are not live at the marker site.
Here is the toy program :
#include <stdio.h>
#define SAVE_REGS   \

	"pushl %%eax\n\t" \

	"pushl %%ebp\n\t" \

	"pushl %%edi\n\t" \

	"pushl %%esi\n\t" \

	"pushl %%edx\n\t" \

	"pushl %%ecx\n\t" \

	"pushl %%ebx\n\t"
#define RESTORE_REGS \

	"popl %%ebx\n\t"	\

	"popl %%ecx\n\t"	\

	"popl %%edx\n\t"	\

	"popl %%esi\n\t"	\

	"popl %%edi\n\t"	\

	"popl %%ebp\n\t"	\

	"popl %%eax\n\t"
#define asmlinkage __attribute__((regparm(0)))

#define _ASM_PTR ".long "
struct marker_info {

	const char *name;

	const char *fields;

	unsigned char nr_args;

	unsigned char type_sizes[];

};
#define trace_mark3(name, fields, arg1, arg2, arg3)			\

	do {								\

		static struct marker_info info = {			\

			#name,						\

			fields,						\

			3, { sizeof(arg1), sizeof(arg2), sizeof(arg3) } }; \

		asm (".section __marker_info, \"a\",@progbits\n\t"	\

			_ASM_PTR "%c0, 1f, 2f\n\t"			\

			".previous\n\t"					\

			".section __farfarawaycode,\"ax\",@progbits\n\t"\

			"1:\n\t"					\

			SAVE_REGS...
[ message continues ]

Basically, although I was suggesting using a per-site dynamic piece of 
We're requesting to keep them *alive*, but not necessarily in registers

(that would be an "r" constraint.)
	-hpa

--

Interesting. Actually, I use the "g" constraint in the code I showed

you, so it might be more acceptable to put in the fast path without

requiring registers to be populated. The only cases that would generate

additional code would probably be arguments like :
/* multiple pointer dereference */

trace_mark(evname, "argname", ptr->stuff[index]->...);
/*

 * having to do some work to prepare the variable (calling a macro or

 * inline function which does more than just a pointer deref.

 */

trace_mark(evname, "argname", get_real_valueof(variable));
/* constants */

trace_mark(evname, "argname", 10000);
Those cases won't add code to the critial path with my current markers,

but it would with the inline assembly "g" constraint approach. Looking

at the "mm" instrumentation, where page_to_pfn, swp_offset and

get_swap_info_struct are used makes me think it would not be such a rare

case.
I would also like to point out that maintaining a _separated_ piece of

code for each instrumentation site which would heavily depend on the

inner kernel data structures seems like a maintenance nightmare. This is

why I am trying to get the instrumented site to export the meaningful

data, self-described, in a standardized way. We can then simply hook on

all the instrumented sites to either perform some in-kernel analysis on

the data (ftrace) or to export that to a userspace trace analyzer

(LTTV analyzing LTTng traces).
I would be happy with a solution that doesn't depend on this gigantic

DWARF information and can be included in the kernel build process. See,

I think tracing is, primarily, a facility that the kernel should provide

to users so they can tune and find problems in their own applications.

From this POV, it would make sense to consider tracing as part of the

kernel code itself, not as a separated, kernel debugging oriented piece

of code. If you require per-site dynamic pieces of code, you are only

adding to the complexity of such a tracer. Actually, an active tracer

would trash the...
[ message continues ]

That's funny, given that's exactly what you have now.
DWARF information is the way you get this stuff out of the compiler.

That is what it's *there for*.  If you don't want to keep it around you

can distill out the information you need and then remove it.  However,

as I have said about six times now:
THE RIGHT WAY TO DO THIS IS WITH COMPILER SUPPORT.
All these problems is because you're trying to do something behind the 
This is somewhat nice in theory; I've found that gcc tends to interlace

them pretty heavily and so the cache interference even of gcc "out of

line" code is sizable.  Furthermore, modern CPUs often speculatively

fetch *both* branches of a conditional.
Nice theory.  Doesn't work in practice as long as you rely on gcc unlikey().
	-hpa

--

The per-site pieces of code are only there to do the stack setup. I
About DWARF : I agree with Ingo that we might not want to depend on this

kind of information normally expected to be correct for debug uses in a

part of infrastructure that is not limited to debugging situation.

Continous performance monitoring is one of the use cases I have in mind.
Moreover, depending on DWARF info requires us to do

architecture-specific code from the beginning. The markers are designed

in such a way that any given new architecture can use the "architecture

agnostic" version of the markers, and then later implement the

optimizations. With about 27 architectures supported by the Linux

kernel, I think this approach makes sense. Looking at the number of

years it took to port something as "simple" as kprobes to 8 out of 27
We totally agree on this about the jump-patching optimization. If the

jump-patching approach I proposed is too far-fetched, and if reading a

variable from memory at each tracing site is too expensive, I would

propose to use the standard "immediate values" flavor until gcc gives us
Using the compiler for the markers (I am not talking about immediate

values, which is an optimization) is what gives us the ability to do an

architecture-agnostic version. The 19 architectures which still lacks
Following your own suggestion, why don't we fix gcc and make it
Agreed. I'd like to find some info about which microarchitectures you
Let's fix gcc ! ;)
Cheers,
Mathieu
--

Mathieu Desnoyers

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

--

Doing this with compiler support is definitely The Right Thing, so I 
Not sure about Core 2, although Core 2 definitely can track down the 
Sounds great :)
	-hpa
--

Hi -
This would require either that DWARF processing be done far after

kernel build, and thus the kernel cannot be self-sufficient /

introspective without user-space assistance (like firmware); or that

the DWARF data extraction (and systemtap-like $context-variable code

generation) be part of the kernel build itself.  It *might* be

workable.
At least one complication though is that in the case of markers,

tracing parameter evaluation is itself conditional (and placed out of

the hot path due to -freorder-blocks).  With your suggested kind of

assembly ("g" constraints for all the expressions), those expressions

would be evaluated unconditionally, just to make them live somewhere.

That unconditional evaluation can easily entail memory reads and

dependent arithmetic, which could swamp the savings of eliminating the

marker-style conditional branch.
- FChE

--

DWARF processing done after the kernel build isn't really a problem,

although it requires a large vmlinux(.gz) file to be kept around.
As part of the kernel build is probably better, at least in the case of 
Well, it depends a bit on what kind of expressions you put in there.

You don't really want to put *expressions* in there as much as you want

to put *data* references in there, although, of course, if your have

something like "foo->bar[baz]->quux" then it's easy to trip upon.
One advantage of using the debugging information in this manner is that

you can write the actual markers long after the kernel has compiled, as

long as the data happens to be available at the call site.
Once again, the *proper* way to do this is with compiler support.  That

way we can do patched branches and out-of-line everything with impunity.
	-hpa
--

and that's exactly what was tripped upon in sched.o and analyzed.
Furthermore, the suggestion of doing this exclusively within the DWARF2

space - besides the not particularly minor complication of it not being

implemented yet - is:
 - quite substantially complex on its own
 - would make Linux instrumentation dependent on all sorts of DWARF2

   details which we had our 'fun' with before. (I proffer that that's

   more fragile than any code patching can ever be.)
 - if done self-sufficiently (i.e. if a kernel image can be used to

   trace things, which i believe any usable kernel tracer must offer),

   it would, with the current debug info format, enlargen the kernel RAM

   image with quite a substantial amount of unswappable kernel memory. 
But i would not mind such a scheme at all (it is in essence SystemTap

integrated into the core kernel) - in fact if your scheme gets

implemented then the current marker facilities could be ported to that

scheme transparently.
So i dont see how it can be a loss to stick with the current markers for

the time being. If the super-optimized runtime patching in this thread

is deemed too fragile we simply wont do that and live with the (small)

runtime overhead that current markers have.
This is a sane plan IMO, basically all the instrumentation folks agree

with it (SystemTap, LTTNG, kprobes, ftrace), the scheduler folks agree

with it as well and we'd like to move on.
	Ingo

--

I am not sure self-sufficiency is  good goal here.
If tracing becomes part of kernel-user ABI, we are in big trouble...
--

(english) http://www.livejournal.com/~pavelmachek

(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

--

thanks Mathieu, i've queued them up for more testing. Your previous

queue already looked good here so i pushed it out into sched-devel.git

as you probably noticed.
Sidenote, without trying to bikeshed paint this issue too much: are we

absolutely sure that (on modern CPU architectures) such a short jump is

better than just 2-3 NOPs in a sequence? It's a minor (sub-cycle) detail

in any case.
	Ingo

--

Let's see :
Paraphrasing the

"Intel® 64 and IA-32 Architectures Optimization Reference Manual" :

http://www.intel.com/design/processor/manuals/248966.pdf
3.5.1.8 Using NOPs
The 1-byte nop, xchg %eax,%eax, is treated specially by the cpu. It

takes only one µop and does not have register dependencies. However,

what we would need here is likely a 5-bytes nop.
The generic 5-bytes nop found in asm-x86/nops.h is :
#define GENERIC_NOP1 ".byte 0x90\n"

#define GENERIC_NOP4 ".byte 0x8d,0x74,0x26,0x00\n"

#define GENERIC_NOP5 GENERIC_NOP1 GENERIC_NOP4
In Intel's guide, they propose a single instruction :

NOP DWORD PTR [EAX + EAX*1 + 0] (8-bit displacement)
(0F 1F 44 00 00H)
Which would be required for correct code patching, since we cannot

safely turn a 1+4 bytes sequence of instruction into a single 5-bytes

call without suffering from possible preempted threads returning in the

middle of the instruction. Since the 5-bytes nop does not seem to be

available on architectures below P6, I think this would be a backward

compatibility problem.
K8 NOP 5 also uses a combination of K8_NOP3 K8_NOP2, so this is not only

backward compatibility, but also a concern for current AMD

compatibility. (same issue for K7 5-bytes nop).
However, if we forget about this issue and take for granted that we can

use a single nop instruction that would only take a single µop and have

no external effect (that would be the ideal P6 and + world), the

closest comparison with the jmp instruction I found is the jcc

(conditional branch) instruction in the same manual, Appendix C, where

they list jcc as having 0 latency when not taken and to have a bandwidth

of 0.5, compared to a latency of 1 and bandwidth of 0.33 to 0.5 for nop.
So, just there, a single jmp instruction would seem to have a lower

latency than the nop. (0 cycle vs 1 cycle)
Another interested reading in this document is about conditional

branches :
3.4.1 Optimizing the Front End
Some interesting guide lines :

- Eliminate bran...
[ message continues ]