Conditional Calls - for 2.6.22-rc2-mm1

Conditional calls are used to compile in code that is meant to be dynamically enabled at runtime. When code is disabled, it has a very small footprint.

It has a generic cond_call version and optimized per architecture cond_calls. The optimized cond_call uses a load immediate to remove a data cache hit.

It adds a new rodata section "__cond_call" to place the pointers to the enable value.

cond_call activation functions sits in module.c.

---
 include/asm-generic/vmlinux.lds.h |   16 +-
 include/linux/condcall.h          |   91 +++++++++++++
 include/linux/module.h            |    4 
 kernel/module.c                   |  248 ++++++++++++++++++++++++++++++++++++++
 4 files changed, 356 insertions(+), 3 deletions(-)

Index: linux-2.6-lttng/include/linux/condcall.h
===================================================================

include/linux/condcall.h new file +9 -0

@@ -0,0 +1,91 @@
+#ifndef _LINUX_CONDCALL_H
+#define _LINUX_CONDCALL_H
+
+/*
+ * Conditional function calls. Cheap when disabled, enabled at runtime.
+ *
+ * (C) Copyright 2007 Mathieu Desnoyers <[email protected]>
+ *
+ * This file is released under the GPLv2.

include/linux/condcall.h new file +11 -0

+#define COND_CALL_MAX_FORMAT_LEN	1024
+
+extern int cond_call_arm(const char *name);
+extern int cond_call_disarm(const char *name);
+
+/* cond_call_query : Returns 1 if enabled, 0 if disabled or not present */
+extern int cond_call_query(const char *name);
+extern int cond_call_list(const char *name);
+
+#endif /* __KERNEL__ */
+#endif

Index: linux-2.6-lttng/include/asm-generic/vmlinux.lds.h
===================================================================

include/asm-generic/vmlinux.lds.h +3 -1

@@ -116,11 +116,22 @@
 		*(__kcrctab_gpl_future)					\
 		VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .;	\
 	}								\
-									\
+	/* Conditional calls: pointers */				\
+	__cond_call : AT(ADDR(__cond_call) - LOAD_OFFSET) {		\
+		VMLINUX_SYMBOL(__start___cond_call) = .;		\

include/linux/condcall.h line 79

Quoted 5 lines

include/linux/condcall.h new file +5 -0

+#ifdef CONFIG_COND_CALL_ENABLE_OPTIMIZATION
+#include <asm/condcall.h>		/* optimized cond_call flavor */
+#else
+#include <asm-generic/condcall.h>	/* fallback on generic cond_call */
+#endif

The preferred way to do this is to give every architecture an asm/condcall.h and from within that, include asm-generic/condcall.h. Your [patch 3/9] does most of that, but it didn't remove the above ifdef, and I don't think it removed the should-be-unneeded CONFIG_COND_CALL_ENABLE_OPTIMIZATION either?

+struct __cond_call_struct {

include/linux/condcall.h new file +6 -0

+#define cond_call_generic(flags, name, func) \
+	({ \
+		static const char __cstrtab_name_##name[] \
+		__attribute__((section("__cond_call_strings"))) = #name; \
+		static char __cond_call_enable_##name = \
+			(flags) & CF_STATIC_ENABLE; \

Quoted 1 line · Mathieu Desnoyers

+struct __cond_call_struct {

Calling structs *_struct is severly deprecated and will cause some people to make fun of your code.

include/linux/condcall.h line 19

Quoted 5 lines

include/linux/condcall.h new file +4 -0

+	const char *name;
+	void *enable;
+	int flags;
+} __attribute__((packed));

The packed doesn't seem to be needed. There will be padding at the end anyways because the next one needs to be aligned.

include/linux/condcall.h line 28

Quoted 9 lines

include/linux/condcall.h new file +9 -0

+
+
+/* Cond call flags : selects the mechanism used to enable the conditional calls
+ * and prescribe what can be executed within their function. This is primarily
+ * used at reentrancy-unfriendly sites. */
+#define CF_OPTIMIZED		(1 << 0) /* Use optimized cond_call */
+#define CF_LOCKDEP		(1 << 1) /* Can call lockdep */
+#define CF_PRINTK		(1 << 2) /* Probe can call vprintk */
+#define CF_STATIC_ENABLE	(1 << 3) /* Enable cond_call statically */

Why is that all needed? Condcall shouldn't really need to know anything about all this. They're just a fancy conditional anyways -- and you don't tell if() that it may need to printk.

Please consider eliminating.

Quoted 3 lines

+#define _CF_NR 4

include/linux/condcall.h line 35

Quoted 6 lines

include/linux/condcall.h new file +6 -0

+
+#ifdef CONFIG_COND_CALL
+
+/* Generic cond_call flavor always available.
+ * Note : the empty asm volatile with read constraint is used here instead of a
+ * "used" attribute to fix a gcc 4.1.x bug. */

What gcc 4.1 bug?

Conditional calls are used to compile in code that is meant to be dynamically enabled at runtime. When code is disabled, it has a very small footprint.

It has a generic cond_call version and optimized per architecture cond_calls. The optimized cond_call uses a load immediate to remove a data cache hit.

It adds a new rodata section "__cond_call" to place the pointers to the enable value.
...

I have two questions for getting the bigger picture:

1. How much code will be changed?
Looking at the F00F bug fixup example, it seems we'll have to make several functions in every single driver conditional in the kernel for getting the best performance.
How many functions to you plan to make conditional this way?

2. What is the real-life performance improvement?
That micro benchmarks comparing cache hits with cache misses give great looking numbers is obvious.
But what will be the performance improvement in real workloads after the functions you plan to make conditional according to question 1 have been made conditional?

TIA
Adrian

Signature · 4 lines

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Hi Adrian,

...

Quoted 6 lines

2. What is the real-life performance improvement?
That micro benchmarks comparing cache hits with cache misses give great looking numbers is obvious.
But what will be the performance improvement in real workloads after the functions you plan to make conditional according to question 1 have been made conditional?

Hrm, I am trying to get interesting numbers out of lmbench: I just ran a test on a kernel sprinkled with about 50 markers at important sites (LTTng markers: system call entry/exit, traps, interrupt handlers, ...). The markers are compiled-in, but in "disabled state". Since the markers re-use the cond_call infrastructure, each marker has its own cond_call.
...
The results are that we really cannot tell that one is faster/slower than the other; the standard deviation is much higher than the difference between the two situations.

Note that lmbench is a workload that will not trigger much L1 cache stress, since it repeats the same tests many times. Do you have any suggestion of a test that would be more representative of a real diversified (in term of in-kernel locality of reference) workload ?

Thanks,

Mathieu

Quoted 1 line · Mathieu Desnoyers

Hi Adrian,

Hi Mathieu,

Quoted 18 lines

...

Quoted 6 lines

2. What is the real-life performance improvement?
That micro benchmarks comparing cache hits with cache misses give great looking numbers is obvious.
But what will be the performance improvement in real workloads after the functions you plan to make conditional according to question 1 have been made conditional?

Hrm, I am trying to get interesting numbers out of lmbench: I just ran a test on a kernel sprinkled with about 50 markers at important sites (LTTng markers: system call entry/exit, traps, interrupt handlers, ...). The markers are compiled-in, but in "disabled state". Since the markers re-use the cond_call infrastructure, each marker has its own cond_call.
...
The results are that we really cannot tell that one is faster/slower than the other; the standard deviation is much higher than the difference between the two situations.

Quoted 4 lines

Note that lmbench is a workload that will not trigger much L1 cache stress, since it repeats the same tests many times. Do you have any suggestion of a test that would be more representative of a real diversified (in term of in-kernel locality of reference) workload ?

Please correct me if I'm wrong, but I think 50 markers couldn't ever result in a visible change:

You need a change that is big enough that it has a measurable influence on the cache hit ratio.

I don't think you could get any measurable influence unless you get into areas where > 10% of all code are conditional. And that's a percentage I wouldn't consider being realistically.

And one big disadvantage of your implementation is the dependency on MODULES. If you build all driver statically into the kernel, switching from CONFIG_MODULES=y to CONFIG_MODULES=n already gives you for free a functionally equivalent kernel that is smaller by at about 8% (depending on the .config).

My impression is that your patches would add an infrastructure for a nice sounding idea that will never have any real life effect.

Quoted 3 lines

Thanks,

Mathieu

cu
Adrian

Signature · 4 lines

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

...
Well, we must take into account where these markers are added and how often the marked code is run. Since I mark very highly used code paths (interrupt handlers, page faults, lockdep code) and also plan to mark other code paths like the VM subsystem, adding cycles to these code

paths seems like a no-go solution for standard distribution kernels.
...
People can get really picky when they have to decide wether or not they compile-in a profiling or tracing infrastructure in a distribution kernel. If the impact is detectable when they are not doing any tracing nor profiling, their reflex will be to compile it out so they can have the "maximum performance". This is why I am going through the trouble of making the markers impact as small as possible.

Mathieu

Quoted 5 lines · Mathieu Desnoyers

...
Well, we must take into account where these markers are added and how often the marked code is run. Since I mark very highly used code paths (interrupt handlers, page faults, lockdep code) and also plan to mark other code paths like the VM subsystem, adding cycles to these code

Quoted 8 lines

paths seems like a no-go solution for standard distribution kernels.
...
People can get really picky when they have to decide wether or not they compile-in a profiling or tracing infrastructure in a distribution kernel. If the impact is detectable when they are not doing any tracing nor profiling, their reflex will be to compile it out so they can have the "maximum performance". This is why I am going through the trouble of making the markers impact as small as possible.

Now that we finally hear what this code is required for, can we discuss on this basis whether this is wanted and required?

Including the question which abuse possibilities such an infrastructure offers, and whether this is wanted in distribution kernels.

Quoted 15 lines · * Adrian Bunk ([email protected]) wrote:

Quoted 13 lines · Mathieu Desnoyers

...
Well, we must take into account where these markers are added and how often the marked code is run. Since I mark very highly used code paths (interrupt handlers, page faults, lockdep code) and also plan to mark other code paths like the VM subsystem, adding cycles to these code paths seems like a no-go solution for standard distribution kernels.
...
People can get really picky when they have to decide wether or not they compile-in a profiling or tracing infrastructure in a distribution kernel. If the impact is detectable when they are not doing any tracing nor profiling, their reflex will be to compile it out so they can have the "maximum performance". This is why I am going through the trouble of making the markers impact as small as possible.

Quoted 5 lines

Now that we finally hear what this code is required for, can we discuss on this basis whether this is wanted and required?

Including the question which abuse possibilities such an infrastructure offers, and whether this is wanted in distribution kernels.

Hi Adrian,

The purpose of this infrastructure has never been a secret; it is a piece taken from the Linux Kernel Markers. I proposed the first implementation of markers in December 2006.

Please use the following link as a starting point to the thorough discussion that has already been held on this matter.

First, a huge discussion thread back in November 2006, where the need for a marker infrastructure has been recognized:
http://lwn.net/Articles/200059/

A good summary of my recent previous post on kerneltrap:
http://kerneltrap.org/node/8186

If you have new specific concerns to bring forward, I will be glad to discuss them with you.

Regards,

Mathieu

Quoted 16 lines · Mathieu Desnoyers

Quoted 15 lines · * Adrian Bunk ([email protected]) wrote:

Quoted 13 lines · Mathieu Desnoyers

...
Well, we must take into account where these markers are added and how often the marked code is run. Since I mark very highly used code paths (interrupt handlers, page faults, lockdep code) and also plan to mark other code paths like the VM subsystem, adding cycles to these code paths seems like a no-go solution for standard distribution kernels.
...
People can get really picky when they have to decide wether or not they compile-in a profiling or tracing infrastructure in a distribution kernel. If the impact is detectable when they are not doing any tracing nor profiling, their reflex will be to compile it out so they can have the "maximum performance". This is why I am going through the trouble of making the markers impact as small as possible.

Quoted 7 lines

Quoted 5 lines

Now that we finally hear what this code is required for, can we discuss on this basis whether this is wanted and required?

Including the question which abuse possibilities such an infrastructure offers, and whether this is wanted in distribution kernels.

Hi Adrian,

Hi Mathieu,

Quoted 11 lines

The purpose of this infrastructure has never been a secret; it is a piece taken from the Linux Kernel Markers. I proposed the first implementation of markers in December 2006.

Please use the following link as a starting point to the thorough discussion that has already been held on this matter.

First, a huge discussion thread back in November 2006, where the need for a marker infrastructure has been recognized:
http://lwn.net/Articles/200059/

Quoted 5 lines

A good summary of my recent previous post on kerneltrap:
http://kerneltrap.org/node/8186

If you have new specific concerns to bring forward, I will be glad to discuss them with you.

sorry if I was a bit harsh, but at least for me it wasn't clear that the main (and perhaps only) reasonable use case for your conditional calls was to get markers enabled in distribution kernels.

Please correct me, but my understanding is:
- conditional calls aim at getting markers enabled in distribution kernels

- markers are a valuable debugging tool

- you don't need markers during normal operation

- markers allow normal modules doing things they shouldn't be doing, implying that markers should _not_ be enabled in normal distribution kernels

Quoted 3 lines

Regards,

Mathieu

cu
Adrian

Signature · 4 lines

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

Reimplementation of the cond calls which uses a hash table to hold the active cond_calls. It permits to first arm a cond_call and then load supplementary modules that contain this cond_call.

Without this, the order of loading a module containing a cond_call and arming a cond_call matters and there is no symbol dependency to check this.

At module load time, each cond_call checks if it is enabled in the hash table and is set accordingly.

Index: linux-2.6-lttng/kernel/module.c
===================================================================

kernel/module.c +5 -0

@@ -33,6 +33,8 @@
 #include <linux/moduleparam.h>
 #include <linux/errno.h>
 #include <linux/condcall.h>
+#include <linux/jhash.h>
+#include <linux/list.h>
 #include <linux/err.h>
 #include <linux/vermagic.h>
 #include <linux/notifier.h>

@@ -71,6 +73,20 @@
 
 static BLOCKING_NOTIFIER_HEAD(module_notify_list);
 
+#ifdef CONFIG_COND_CALL
+/* Conditional call hash table, containing the active cond_calls.
+ * Protected by module_mutex. */

kernel/module.c +7 -0

+/* Remove the cond_call from the hash table. Must be called with mutex_lock
+ * held. */
+static void hash_remove_cond_call(const char *name)
+{
+	struct hlist_head *head;
+	struct hlist_node *node;
+	struct cond_call_entry *e;

kernel/module.c +5 -1

+	if (found) {
+		hlist_del(&e->hlist);
+		kfree(e);
+	}
+}
 
 /* Set the enable bit of the cond_call, choosing the generic or architecture
  * specific functions depending on the cond_call's flags.

@@ -317,59 +395,53 @@
 		return cond_call_generic_set_enable(address, enable);
 }
 
-/* Query the state of a cond_calls range. */

Reimplementation of the cond calls which uses a hash table to hold the active cond_calls. It permits to first arm a cond_call and then load supplementary modules that contain this cond_call.

Quoted 3 lines · Mathieu Desnoyers

Reimplementation of the cond calls which uses a hash table to hold the active cond_calls. It permits to first arm a cond_call and then load supplementary modules that contain this cond_call.

Hash table is probably overkill. This is a very very slow path operation. Can you simplify the code? Just a linked list of all the condcall segments should be enough and then walk it.

Quoted 9 lines · Andi Kleen

Quoted 3 lines · Mathieu Desnoyers

Reimplementation of the cond calls which uses a hash table to hold the active cond_calls. It permits to first arm a cond_call and then load supplementary modules that contain this cond_call.

Hash table is probably overkill. This is a very very slow path operation. Can you simplify the code? Just a linked list of all the condcall segments should be enough and then walk it.

I think it could be greatly simplified by using symbols instead of strings.

That is, doing cond_call(foo, func()) rather than cond_call("foo", func()). Here foo is a structure or type holding the relevant info to deal with the cond_call infrastructure. For unoptimized architectures, it can simply be a bool, which will be faster.

This has the added advantage that the compiler will automatically pick up any misspellings of these things. And it saves the space we'd use on the hash table too.

Quoted 14 lines · * Matt Mackall ([email protected]) wrote:

Quoted 9 lines · Andi Kleen

Quoted 3 lines · Mathieu Desnoyers

Reimplementation of the cond calls which uses a hash table to hold the active cond_calls. It permits to first arm a cond_call and then load supplementary modules that contain this cond_call.

Hash table is probably overkill. This is a very very slow path operation. Can you simplify the code? Just a linked list of all the condcall segments should be enough and then walk it.

I think it could be greatly simplified by using symbols instead of strings.

Quoted 9 lines

That is, doing cond_call(foo, func()) rather than cond_call("foo", func()). Here foo is a structure or type holding the relevant info to deal with the cond_call infrastructure. For unoptimized architectures, it can simply be a bool, which will be faster.

This has the added advantage that the compiler will automatically pick up any misspellings of these things. And it saves the space we'd use on the hash table too.

The idea is interesting, but does not fit the problem: AFAIK, it will not be possible to do multiple declarations of the same symbol, which is needed whenever we want to declare a cond_call() more than once or to embed it in an inline function.

It's not clear to me why either of those things are necessary. An example please?

Quoted 2 lines

It's not clear to me why either of those things are necessary. An example please?

It's certainly possible that a global flag would need to be tested more than once.

I guess it would work if a symbol is associated with a single definition. e.g. if there is a DEFINE_COND_CALL() somewhere and the individual cond calls reference it.

Quoted 6 lines · * Andi Kleen ([email protected]) wrote:

Quoted 2 lines

It's not clear to me why either of those things are necessary. An example please?

It's certainly possible that a global flag would need to be tested more than once.

Quoted 3 lines

I guess it would work if a symbol is associated with a single definition. e.g. if there is a DEFINE_COND_CALL() somewhere and the individual cond calls reference it.

Yes, but as you have probably understood, I want to have everything embedded at the cond_call() site rather than polluting the rest of the code with declarations.

Also, if we have the same cond_calls in different modules, in which module shall it be defined ?

Yes, but as you have probably understood, I want to have everything embedded at the cond_call() site rather than polluting the rest of the code with declarations.

Also, if we have the same cond_calls in different modules, in which module shall it be defined ?

Quoted 3 lines

Yes, but as you have probably understood, I want to have everything embedded at the cond_call() site rather than polluting the rest of the code with declarations.

A cond call is essentially a fancy variable. And the Linux kernel is written in C and in C you declare variables before you use them. Also it would allow compile time checking against typos and allow removing some nasty hash table code. The proposal sounds like a clear winner to me.

Quoted 2 lines

Also, if we have the same cond_calls in different modules, in which module shall it be defined ?

In one of them. Like all other variables in C.

Quoted 10 lines · * Andi Kleen ([email protected]) wrote:

Quoted 3 lines

Yes, but as you have probably understood, I want to have everything embedded at the cond_call() site rather than polluting the rest of the code with declarations.

A cond call is essentially a fancy variable. And the Linux kernel is written in C and in C you declare variables before you use them. Also it would allow compile time checking against typos and allow removing some nasty hash table code. The proposal sounds like a clear winner to me.

You could not declare in advance a structure that would contain pointers to every load immediate instruction of the optimized cond_calls. Unless

I understand that if we limit ourselves to applications like the two toy examples I proposed (enabling profiling and bug fixups), it could make sense to try to declare a variable somewhere and later use it in the body of functions (except the fact that it cannot work, due to incapacity to declare pointers to each load immediate instruction, as

stated above). Even if it would work, the main purpose here is to support the Linux Kernel Markers, where the goal is to provide the ability to declare a marker within the body of a function without requiring more hassle than a printk, but with less performance impact than the latter. Also, we would not want the whole kernel to recompile simply because someone chose to add one or two marker in his own driver to extract some more information and had to add them to some globally included header file.

Quoted 12 lines · Mathieu Desnoyers

Quoted 10 lines · * Andi Kleen ([email protected]) wrote:

Quoted 3 lines

Yes, but as you have probably understood, I want to have everything embedded at the cond_call() site rather than polluting the rest of the code with declarations.

A cond call is essentially a fancy variable. And the Linux kernel is written in C and in C you declare variables before you use them. Also it would allow compile time checking against typos and allow removing some nasty hash table code. The proposal sounds like a clear winner to me.

Quoted 2 lines

You could not declare in advance a structure that would contain pointers to every load immediate instruction of the optimized cond_calls. Unless

To find them you just walk the sections. Changing cond call is a slow path operation. That is similar to how the smp lock switching works today.

Quoted 5 lines

I understand that if we limit ourselves to applications like the two toy examples I proposed (enabling profiling and bug fixups), it could make sense to try to declare a variable somewhere and later use it in the body of functions (except the fact that it cannot work, due to incapacity to declare pointers to each load immediate instruction, as

Quoted 8 lines

stated above). Even if it would work, the main purpose here is to support the Linux Kernel Markers, where the goal is to provide the ability to declare a marker within the body of a function without requiring more hassle than a printk, but with less performance impact than the latter. Also, we would not want the whole kernel to recompile simply because someone chose to add one or two marker in his own driver to extract some more information and had to add them to some globally included header file.

Sounds similar to config.h then when Kconfig keeps track of those dependencies for the CONFIG_*s and only recompiles what is needed. Perhaps this infrastructure could be reused.

Quoted 25 lines · Mathieu Desnoyers

Quoted 23 lines · * Matt Mackall ([email protected]) wrote:

Quoted 9 lines · Andi Kleen

Quoted 3 lines · Mathieu Desnoyers

Reimplementation of the cond calls which uses a hash table to hold the active cond_calls. It permits to first arm a cond_call and then load supplementary modules that contain this cond_call.

Hash table is probably overkill. This is a very very slow path operation. Can you simplify the code? Just a linked list of all the condcall segments should be enough and then walk it.

I think it could be greatly simplified by using symbols instead of strings.

That is, doing cond_call(foo, func()) rather than cond_call("foo", func()). Here foo is a structure or type holding the relevant info to deal with the cond_call infrastructure. For unoptimized architectures, it can simply be a bool, which will be faster.

This has the added advantage that the compiler will automatically pick up any misspellings of these things. And it saves the space we'd use on the hash table too.

Quoted 4 lines

The idea is interesting, but does not fit the problem: AFAIK, it will not be possible to do multiple declarations of the same symbol, which is needed whenever we want to declare a cond_call() more than once or to embed it in an inline function.

It's not clear to me why either of those things are necessary. An example please?

i386 optimization of the cond_calls which uses a movb with code patching to set/unset the value used to populate the register used for the branch test.

include/asm-i386/condcall.h +26 -0

+/*
+ * Conditional function calls. i386 architecture optimizations.
+ *
+ * (C) Copyright 2006 Mathieu Desnoyers <[email protected]>
+ *
+ * This file is released under the GPLv2.
+ * See the file COPYING for more details.
+ */
+
+
+#ifdef CONFIG_COND_CALL
+
+#define CF_DEFAULT (CF_OPTIMIZED | CF_LOCKDEP | CF_PRINTK)
+
+/* Optimized version of the cond_call. Passing the flags as a pointer to
+ * the inline assembly to trick it into putting the flags value as third
+ * parameter in the structure. */
+#define cond_call_optimized(flags, name, func) \
+	({ \
+		static const char __cstrtab_name_##name[] \
+		__attribute__((section("__cond_call_strings"))) = #name; \
+		char condition; \
+		asm (	".section __cond_call, \"a\", @progbits;\n\t" \
+					".long %1, 0f, %2;\n\t" \
+					".previous;\n\t" \
+					".align 2\n\t" \

include/asm-i386/condcall.h +4 -0

+extern int cond_call_optimized_set_enable(void *address, char enable);
+
+#endif
+#endif //_ASM_I386_CONDCALL_H

arch/i386/kernel/condcall.c new file +52 -0

@@ -0,0 +1,140 @@
+/* condcall.c
+ *
+ * - Erratum 49 fix for Intel PIII.
+ * - Still present on newer processors : Intel Core 2 Duo Processor for Intel
+ *   Centrino Duo Processor Technology Specification Update, AH33.
+ *   Unsynchronized Cross-Modifying Code Operations Can Cause Unexpected
+ *   Instruction Execution Results.
+ *
+ * Permits cond_call activation by XMC with correct serialization.
+ *
+ * Reentrant for NMI and trap handler instrumentation. Permits XMC to a
+ * location that has preemption enabled because it involves no temporary or
+ * reused data structure.
+ *
+ * Quoting Richard J Moore, source of the information motivating this
+ * implementation which differs from the one proposed by Intel which is not
+ * suitable for kernel context (does not support NMI and would require disabling
+ * interrupts on every CPU for a long period) :
+ *
+ * "There is another issue to consider when looking into using probes other
+ * then int3:
+ *
+ * Intel erratum 54 - Unsynchronized Cross-modifying code - refers to the
+ * practice of modifying code on one processor where another has prefetched
+ * the unmodified version of the code. Intel states that unpredictable general
+ * protection faults may result if a synchronizing instruction (iret, int,
+ * int3, cpuid, etc ) is not executed on the second processor before it
+ * executes the pre-fetched out-of-date copy of the instruction.
+ *
+ * When we became aware of this I had a long discussion with Intel's
+ * microarchitecture guys. It turns out that the reason for this erratum
+ * (which incidentally Intel does not intend to fix) is because the trace
+ * cache - the stream of micorops resulting from instruction interpretation -
+ * cannot guaranteed to be valid. Reading between the lines I assume this
+ * issue arises because of optimization done in the trace cache, where it is
+ * no longer possible to identify the original instruction boundaries. If the
+ * CPU discoverers that the trace cache has been invalidated because of
+ * unsynchronized cross-modification then instruction execution will be
+ * aborted with a GPF. Further discussion with Intel revealed that replacing
+ * the first opcode byte with an int3 would not be subject to this erratum.
+ *
+ * So, is cmpxchg reliable? One has to guarantee more than mere atomicity."
+ *
+ * Mathieu Desnoyers <[email protected]>
+ */
+
+#include <linux/notifier.h>
+#include <linux/mutex.h>
+#include <linux/preempt.h>
+#include <linux/smp.h>
+#include <linux/notifier.h>
+#include <linux/module.h>

arch/i386/kernel/condcall.c new file +3 -0

 in the second
+ * byte of the movb. Incrementing it of 1 byte makes the code resume right after
+ * the movb instruction, effectively skipping this instruction.
+ *

arch/i386/kernel/condcall.c new file +47 -0

+	if (!args->regs || user_mode_vm(args->regs))
+		return NOTIFY_DONE;
+
+	if (die_val == DIE_INT3	&& args->regs->eip == target_eip) {
+		args->regs->eip += 1; /* Skip the next byte of load immediate */
+		return NOTIFY_STOP;
+	}
+	return NOTIFY_DONE;
+}
+
+static struct notifier_block cond_call_notify = {
+	.notifier_call = cond_call_notifier,
+	.priority = 0x7fffffff,	/* we need to be notified first */
+};
+
+int cond_call_optimized_set_enable(void *address, char enable)
+{
+	char saved_byte;
+	int ret;
+	char *dest = address;
+
+	mutex_lock(&cond_call_mutex);
+
+	if (!(enable ^ dest[1])) /* Must be a state change 0<->1 to execute */
+		goto end;
+
+	target_eip = (long)address + BREAKPOINT_INS_LEN;
+	/* register_die_notifier has memory barriers */
+	register_die_notifier(&cond_call_notify);
+	saved_byte = *dest;
+	*dest = BREAKPOINT_INSTRUCTION;
+	wmb();
+	/* Execute serializing instruction on each CPU.
+	 * Acts as a memory barrier. */
+	ret = on_each_cpu(cond_call_synchronize_core, NULL, 1, 1);
+	BUG_ON(ret != 0);
+
+	dest[1] = enable;
+	wmb();
+	*dest = saved_byte;
+		/* Wait for all int3 handlers to end
+		   (interrupts are disabled in int3).
+		   This CPU is clearly not in a int3 handler,
+		   because int3 handler is not preemptible and
+		   there cannot be any more int3 handler called
+		   for this site, because we placed the original
+		   instruction back.

include/asm-i386/condcall.h +5 -0

+#define cond_call_optimized(flags, name, func) \
+	({ \
+		static const char __cstrtab_name_##name[] \
+		__attribute__((section("__cond_call_strings"))) = #name; \
+		char condition; \

Quoted 5 lines · Mathieu Desnoyers

include/asm-i386/condcall.h +5 -0

+#define cond_call_optimized(flags, name, func) \
+	({ \
+		static const char __cstrtab_name_##name[] \
+		__attribute__((section("__cond_call_strings"))) = #name; \
+		char condition; \

include/asm-i386/condcall.h line 35

Quoted 10 lines

include/asm-i386/condcall.h +10 -0

+		asm (	".section __cond_call, \"a\", @progbits;\n\t" \
+					".long %1, 0f, %2;\n\t" \
+					".previous;\n\t" \
+					".align 2\n\t" \
+					"0:\n\t" \
+					"movb %3,%0;\n\t" \
+				: "=r" (condition) \
+				: "m" (*__cstrtab_name_##name), \
+				  "m" (*(char*)flags), \
+				  "i" ((flags) & CF_STATIC_ENABLE)); \

Remind me what we need the flags again for?

I would prefer to just eliminate them and always require arming.

include/asm-i386/condcall.h line 45

Quoted 11 lines

include/asm-i386/condcall.h +10 -0

+		(likely(!condition)) ? \
+			(__typeof__(func))0 : \
+			(func); \
+	})
+
+/* cond_call macro selecting the generic or optimized version of cond_call,
+ * depending on the flags specified. */
+#define _cond_call(flags, name, func) \
+({ \
+	(((flags) & CF_LOCKDEP) && ((flags) & CF_OPTIMIZED)) ? \

Similar here? unoptimized condcalls don't make much sense. I also don't understand what the LOCKDEP flag is good for.

Quoted 7 lines

Index: linux-2.6-lttng/arch/i386/kernel/condcall.c
===================================================================

arch/i386/kernel/condcall.c new file +2 -0

@@ -0,0 +1,140 @@
+/* condcall.c
+ *

arch/i386/kernel/condcall.c line 7

Quoted 5 lines

arch/i386/kernel/condcall.c new file +5 -0

+ * - Erratum 49 fix for Intel PIII.
+ * - Still present on newer processors : Intel Core 2 Duo Processor for Intel
+ *   Centrino Duo Processor Technology Specification Update, AH33.
+ *   Unsynchronized Cross-Modifying Code Operations Can Cause Unexpected
+ *   Instruction Execution Results.

Can you please define a generic utility function to do self modifying code? There are other places that do it too.

arch/i386/kernel/condcall.c line 61

Quoted 1 line

arch/i386/kernel/condcall.c new file +1 -0

+static DEFINE_MUTEX(cond_call_mutex);

All locks need a comment describing what they protect and the hierarchy if any.

Use the faster conditional calls for F00F bug handling in do_page_fault.

(quoted diff) +0 -0

 }
 #endif
 

Index: linux-2.6-lttng/arch/i386/mm/fault.c
===================================================================

arch/i386/mm/fault.c +20 -5

@@ -25,6 +25,7 @@
 #include <linux/kprobes.h>
 #include <linux/uaccess.h>
 #include <linux/kdebug.h>
+#include <linux/condcall.h>
 
 #include <asm/system.h>
 #include <asm/desc.h>

@@ -221,6 +222,25 @@
 
 fastcall void do_invalid_op(struct pt_regs *, unsigned long);
 
+#ifdef CONFIG_X86_F00F_BUG
+/*
+ * Pentium F0 0F C7 C8 bug workaround.
+ */
+static inline int do_f00f_workaround(struct pt_regs *regs,
+		unsigned long address)
+{
+	unsigned long nr;
+
+	nr = (address - idt_descr.address) >> 3;
+
+	if (nr == 6) {
+		do_invalid_op(regs, 0);
+		return 1;
+	}
+	return 0;
+}
+#endif
+
 static inline pmd_t *vmalloc_sync_one(pgd_t *pgd, unsigned long address)
 {
 	unsigned index = pgd_index(address);

@@ -474,19 +494,8 @@
 	}
 
 #ifdef CONFIG_X86_F00F_BUG
-	/*
-	 * Pentium F0 0F C7 C8 bug workaround.
-	 */
-	if (boot_cpu_data.f00f_bug) {
-		unsigned long nr;

Quoted 2 lines

Use the faster conditional calls for F00F bug handling in do_page_fault.

I guess this means that CONDCALL will be enabled on pretty much all i386, in which case making the whole feature Kconfigurable is starting to look marginal.

Perhaps a better approach would have to made this change dependent upon CONDCALL, rather than forcing it on.

arch/i386/mm/fault.c line 498

Quoted 2 lines

arch/i386/mm/fault.c +2 -0

+	if (cond_call(fix_f00f, do_f00f_workaround(regs, address)))
+		return;

We do a cond_call() to an inlined function? That's a bit weird, isn't it?

Quoted 7 lines · * Andrew Morton ([email protected]) wrote:

Quoted 2 lines

Use the faster conditional calls for F00F bug handling in do_page_fault.

I guess this means that CONDCALL will be enabled on pretty much all i386, in which case making the whole feature Kconfigurable is starting to look marginal.

Quoted 3 lines

Perhaps a better approach would have to made this change dependent upon CONDCALL, rather than forcing it on.

Do you mean making X86_F00F_BUG depend on COND_CALL instead of selecting it ?

Quoted 5 lines

arch/i386/mm/fault.c line 498

Quoted 2 lines

arch/i386/mm/fault.c +2 -0

+	if (cond_call(fix_f00f, do_f00f_workaround(regs, address)))
+		return;

We do a cond_call() to an inlined function? That's a bit weird, isn't it?

Yes, but it works :) I will add this information to the documentation.

Quoted 9 lines · On Thu, 31 May 2007 17:07:55 -0400 Mathieu Desnoyers…

Quoted 7 lines · * Andrew Morton ([email protected]) wrote:

Quoted 2 lines

Use the faster conditional calls for F00F bug handling in do_page_fault.

I guess this means that CONDCALL will be enabled on pretty much all i386, in which case making the whole feature Kconfigurable is starting to look marginal.

Quoted 6 lines

Quoted 3 lines

Perhaps a better approach would have to made this change dependent upon CONDCALL, rather than forcing it on.

Do you mean making X86_F00F_BUG depend on COND_CALL instead of selecting it ?

yup

Quoted 6 lines

Quoted 5 lines

arch/i386/mm/fault.c line 498

Quoted 2 lines

arch/i386/mm/fault.c +2 -0

+	if (cond_call(fix_f00f, do_f00f_workaround(regs, address)))
+		return;

We do a cond_call() to an inlined function? That's a bit weird, isn't it?

Quoted 1 line

Yes, but it works :) I will add this information to the documentation.

But why does it work? Did the compiler generate an out-of-line copy of the function? If so, we'll end up with multiple copies of the function if there are other callers. If not, the `inline' was pointless.

kernel/sched.c line 2996

Quoted 8 lines · On Wed, 30 May 2007 10:00:34 -0400 Mathieu Desnoyers…

kernel/sched.c +2 -1

@@ -2990,7 +2991,8 @@
 			print_irqtrace_events(prev);
 		dump_stack();
 	}
-	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
+	cond_call(profile_on,
+		profile_hit(SCHED_PROFILING, __builtin_return_address(0)));
 

That's looking pretty neat. Do you have any before-and-after performance figures for i386 and for a non-optimised architecture?

Quoted 14 lines · * Andrew Morton ([email protected]) wrote:

kernel/sched.c line 2996

Quoted 8 lines · On Wed, 30 May 2007 10:00:34 -0400 Mathieu Desnoyers…

kernel/sched.c +2 -1

@@ -2990,7 +2991,8 @@
 			print_irqtrace_events(prev);
 		dump_stack();
 	}
-	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
+	cond_call(profile_on,
+		profile_hit(SCHED_PROFILING, __builtin_return_address(0)));
 

That's looking pretty neat. Do you have any before-and-after performance figures for i386 and for a non-optimised architecture?

Sure, here is the result of a small test comparing:
1 - Branch depending on a cache miss (has to fetch in memory, caused by a 128
bytes stride)). This is the test that is likely to look like what side-effect the original profile_hit code was causing, under the assumption that the kernel is already using L1 and L2 caches at their full capacity and that a supplementary data load would cause cache trashing.
2 - Branch depending on L1 cache hit. Just for comparison.
3 - Branch depending on a load immediate in the instruction stream.

It has been compiled with gcc -O2. Tests done on a 3GHz P4.

In the first test series, the branch is not taken:

number of tests : 1000
number of branches per test : 81920
memory hit cycles per iteration (mean) : 48.252
L1 cache hit cycles per iteration (mean) : 16.1693 instruction stream based test, cycles per iteration (mean) : 16.0432

In the second test series, the branch is taken and an integer is incremented within the block:

number of tests : 1000
number of branches per test : 81920
memory hit cycles per iteration (mean) : 48.2691
L1 cache hit cycles per iteration (mean) : 16.396 instruction stream based test, cycles per iteration (mean) : 16.0441

Therefore, the memory fetch based test seems to be 200% slower than the load immediate based test.

(I am adding these results to the documentation)

Quoted 46 lines · On Fri, 1 Jun 2007 11:54:13 -0400 Mathieu Desnoyers…

Quoted 14 lines · * Andrew Morton ([email protected]) wrote:

kernel/sched.c line 2996

Quoted 8 lines · On Wed, 30 May 2007 10:00:34 -0400 Mathieu Desnoyers…

kernel/sched.c +2 -1

@@ -2990,7 +2991,8 @@
 			print_irqtrace_events(prev);
 		dump_stack();
 	}
-	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
+	cond_call(profile_on,
+		profile_hit(SCHED_PROFILING, __builtin_return_address(0)));
 

That's looking pretty neat. Do you have any before-and-after performance figures for i386 and for a non-optimised architecture?

Sure, here is the result of a small test comparing:
1 - Branch depending on a cache miss (has to fetch in memory, caused by a 128
bytes stride)). This is the test that is likely to look like what side-effect the original profile_hit code was causing, under the assumption that the kernel is already using L1 and L2 caches at their full capacity and that a supplementary data load would cause cache trashing.
2 - Branch depending on L1 cache hit. Just for comparison.
3 - Branch depending on a load immediate in the instruction stream.

It has been compiled with gcc -O2. Tests done on a 3GHz P4.

In the first test series, the branch is not taken:

number of tests : 1000
number of branches per test : 81920
memory hit cycles per iteration (mean) : 48.252
L1 cache hit cycles per iteration (mean) : 16.1693 instruction stream based test, cycles per iteration (mean) : 16.0432

In the second test series, the branch is taken and an integer is incremented within the block:

number of tests : 1000
number of branches per test : 81920
memory hit cycles per iteration (mean) : 48.2691
L1 cache hit cycles per iteration (mean) : 16.396 instruction stream based test, cycles per iteration (mean) : 16.0441

Quoted 2 lines

Therefore, the memory fetch based test seems to be 200% slower than the load immediate based test.

Confused. From what did you calculate that 200%?

Quoted 1 line

(I am adding these results to the documentation)

Good, thanks.

Use conditional calls with lower d-cache hit in optimized version as a condition for scheduler profiling call.

Quoted 2 lines · Mathieu Desnoyers

Use conditional calls with lower d-cache hit in optimized version as a condition for scheduler profiling call.

[...]

kernel/profile.c line 97

Quoted 2 lines

kernel/profile.c +2 -0

+	if (prof_on)
+		BUG_ON(cond_call_arm("profile_on"));

What's the point of this BUG_ON()? The condition is a priori impossible.

Quoted 2 lines

Quoted 2 lines

kernel/profile.c +2 -0

+	if (prof_on)
+		BUG_ON(cond_call_arm("profile_on"));

Quoted 1 line

What's the point of this BUG_ON()? The condition is a priori impossible.

Not impossible: hash_add_cond_call() can return -ENOMEM if kmalloc lacks memory.

Quoted 2 lines · Mathieu Desnoyers

Quoted 2 lines

Quoted 2 lines

kernel/profile.c +2 -0

+	if (prof_on)
+		BUG_ON(cond_call_arm("profile_on"));

Quoted 1 line · * William Lee Irwin III ([email protected]) wrote:

Quoted 1 line

What's the point of this BUG_ON()? The condition is a priori impossible.

On Thu, May 31, 2007 at 05:12:58PM -0400, Mathieu Desnoyers wrote:

Quoted 2 lines

Not impossible: hash_add_cond_call() can return -ENOMEM if kmalloc lacks memory.

Shouldn't it just propagate the errors like anything else instead of going BUG(), then? One can easily live without profiling if the profile buffers should fail to be allocated e.g. due to memory fragmentation.

These things all have to handle errors for hotplugging anyway AIUI.

Use conditional calls with lower d-cache hit in optimized version as a condition for scheduler profiling call.

Signed-off-by Mathieu Desnoyers <[email protected]>

---
 kernel/profile.c |    4 ++++
 kernel/sched.c   |    4 +++-
 2 files changed, 7 insertions(+), 1 deletion(-)

Index: linux-2.6-lttng/kernel/profile.c
===================================================================

kernel/profile.c +4 -0

@@ -23,6 +23,7 @@
 #include <linux/profile.h>
 #include <linux/highmem.h>
 #include <linux/mutex.h>
+#include <linux/condcall.h>
 #include <asm/sections.h>
 #include <asm/semaphore.h>
 #include <asm/irq_regs.h>

@@ -92,6 +93,8 @@
 		printk(KERN_INFO "kernel profiling enabled (shift: %ld)\n",
 			prof_shift);
 	}
+	if (prof_on)
+		BUG_ON(cond_call_arm("profile_on"));
 	return 1;
 }
 __setup("profile=", profile_setup);

@@ -556,6 +559,7 @@
 	return 0;
 out_cleanup:
 	prof_on = 0;
+	cond_call_disarm("profile_on");
 	smp_mb();
 	on_each_cpu(profile_nop, NULL, 0, 1);
 	for_each_online_cpu(cpu) {

Index: linux-2.6-lttng/kernel/sched.c
===================================================================

kernel/sched.c +1 -0

@@ -59,6 +59,7 @@
 #include <linux/kprobes.h>
 #include <linux/delayacct.h>
 #include <linux/reciprocal_div.h>
+#include <linux/condcall.h>
 
 #include <asm/tlb.h>
 #include <asm/unistd.h>

kernel/sched.c line 2995

Quoted 3 lines

kernel/sched.c +2 -1

-	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
+	cond_call(profile_on,
+		profile_hit(SCHED_PROFILING, __builtin_return_address(0)));

I think we could do better here pretty trivially. profile hit still has an if (unlikely(prof_on == TYPE)). Shouldn't we just have a cond_call type for "sched_profiling" and cond_call profile_hits(type, ip, 1) directly?

kernel/sched.c line 2995

Quoted 4 lines · Mathieu Desnoyers

kernel/sched.c +2 -1

 	}
-	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
+	cond_call(profile_on,
+		profile_hit(SCHED_PROFILING, __builtin_return_address(0)));

Would it be possible to use a syntax like

        if (unlikely_cond_call(variable)) {     (or better name) 
                ...
        } 

instead? I think that would be much nicer to read than having code in a macro argument

I see your point, but there is a level of control on the branch I would lack by doing so: the ability to put the call in either the if or else branch. It is an optimization on i386.

Also, I live in the expectation that, someday, the gcc guys will be nice enough to add some kind of support for a nop-based jump that would require code patching to put a jump instead. If it ever happens, my macro could evolve into this for newer compiler versions, which I could not do with the if() statement you are proposing.

Quoted 3 lines

I see your point, but there is a level of control on the branch I would lack by doing so: the ability to put the call in either the if or else branch. It is an optimization on i386.

What does it optimize exactly?

Quoted 5 lines

Also, I live in the expectation that, someday, the gcc guys will be nice enough to add some kind of support for a nop-based jump that would require code patching to put a jump instead. If it ever happens, my macro could evolve into this for newer compiler versions, which I could not do with the if() statement you are proposing.

If that ever happens we couldn't use it anyways because Linux still has to support old compilers for a long time. And when those are dropped the code could be updated.