Immediate Values
Subsystems (4)
cover Immediate Values
Hi Andrew,
Here is the latest version of immediate values. It applies on 2.6.23-rc2-mm2 in this order:
immediate-values-global-modules-list-and-mutex.patch immediate-values-architecture-independent-code.patch immediate-values-kconfig-embedded.patch immediate-values-move-kprobes-i386-restore-interrupt-to-kdebug-h.patch immediate-values-i386-optimization.patch immediate-values-powerpc-optimization.patch immediate-values-documentation.patch
#
profiling-use-immediate-values.patch
Mathieu
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 1/8 Immediate Values - Global Modules List and Module Mutex
Remove "static" from module_mutex and the modules list so it can be used by other builtin objects in the kernel. Otherwise, every code depending on the module list would have to be put in kernel/module.c. Since the immediate values depends on the module list but can be considered as logically different, it makes sense to implement them in their own file.
The alternative to this would be to disable preemption in code path that need such synchronization, so they can be protected against module unload by stop_machine(), but not being able to sleep within while needing such synchronization is limiting.
--- include/linux/module.h | 4 ++++ kernel/module.c | 4 ++-- 2 files changed, 6 insertions(+), 2 deletions(-)
kernel/module.c +2 -2
@@ -64,8 +64,8 @@ extern int module_sysfs_initialized;/* List of modules, protected by module_mutex or preempt_disable * (add/delete uses stop_machine). */ -static DEFINE_MUTEX (module_mutex); -static LIST_HEAD (modules); +DEFINE_MUTEX (module_mutex); +LIST_HEAD (modules);static DECLARE_MUTEX (notify_mutex);static BLOCKING_NOTIFIER_HEAD (module_notify_list);
include/linux/module.h +4 -0
@@ -60,6 +60,10 @@ struct module_kobjectstruct kobject *drivers_dir; }; +/* Protects the list of modules. */ +extern struct mutex module_mutex; +extern struct list_head modules; +/* These are either module local, or the kernel's dummy ones. */ extern int init_module (void );extern void cleanup_module (void );
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 2/8 Immediate Values - Architecture Independent Code
In reply to Mathieu DesnoyersImmediate values are used as read mostly variables that are rarely updated. They use code patching to modify the values inscribed in the instruction stream. It provides a way to save precious cache lines that would otherwise have to be used by these variables.
There is a generic _immediate_read() version, which uses standard global variables, and optimized per architecture immediate_read() implementations, which use a load immediate to remove a data cache hit. When the immediate values functionnality is disabled in the kernel, it falls back to global variables.
It adds a new rodata section "__immediate" to place the pointers to the enable value. Immediate values activation functions sits in kernel/immediate.c.
Immediate values refer to the memory address of a previously declared integer. This integer holds the information about the state of the immediate values associated, and must be accessed through the API found in linux/immediate.h.
At module load time, each immediate value is checked to see if it must be enabled. It would be the case if the variable they refer to is exported from another module and already enabled.
In the early stages of start_kernel(), the immediate values are updated to reflect the state of the variable they refer to.
* Why should this be merged *
It improves performances on heavy memory I/O workloads.
An interesting result shows the potential this infrastructure has by showing the slowdown a simple system call such as getppid() suffers when it is used under heavy user-space cache trashing:
Random walk L1 and L2 trashing surrounding a getppid() call:
(note: in this test, do_syscal_trace was taken at each system call, see Documentation/immediate.txt in these patches for details)
- No memory pressure : getppid() takes 1573 cycles
- With memory pressure : getppid() takes 15589 cycles
We therefore have a slowdown of 10 times just to get the kernel variables from memory. Another test on the same architecture (Intel P4) measured the memory latency to be 559 cycles. Therefore, each cache line removed from the hot path would improve the syscall time of 3.5% in these conditions.
--- include/asm-generic/vmlinux.lds.h | 7 ++ include/linux/immediate.h | 119 +++++++++++++++++++++++++++++++++++ include/linux/module.h | 6 + init/main.c | 2 kernel/Makefile | 1 kernel/immediate.c | 128 ++++++++++++++++++++++++++++++++++++++ kernel/module.c | 16 ++++ 7 files changed, 279 insertions(+)
include/linux/immediate.h new file +119 -0
@@ -0,0 +1,119 @@ +#ifndef _LINUX_IMMEDIATE_H +#define _LINUX_IMMEDIATE_H + +/* +* Immediate values, can be updated at runtime and save cache lines. +* +* (C) Copyright 2007 Mathieu Desnoyers <[email protected]> +* +* This file is released under the GPLv2. +* See the file COPYING for more details. +*/ + +#ifdef CONFIG_IMMEDIATE +#include <asm/immediate.h> +#else +/* +* Generic immediate values: a simple, standard, memory load. +*/ + +struct module ; + +/** +* immediate_read - read immediate variable +* @var: pointer of type immediate_*_t +* +* Reads the value of @var. +*/ +#define immediate_read (var) _immediate_read(var) + +/** +* immediate_set - set immediate variable (with locking) +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var, taking the module_mutex if required by +* the architecture. +*/ +#define immediate_set (var, i) ((var)->value = (i)) + +/** +* _immediate_set - set immediate variable (without locking) +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var. Must be called with module_mutex held. +*/ +#define _immediate_set (var, i) immediate_set(var, i) + +/** +* immediate_set_early - set immediate variable at early boot +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var. Should be used for early boot updates. +*/ +#define immediate_set_early (var, i) immediate_set(var, i) + +/** +* immediate_if - if () statement depending on an immediate value +* @var: pointer of type immediate_*_t +* +* Use as an if () statement depending on an immediate value. +*/ +#define immediate_if (var) if (immediate_read(var)) + +/* +* Internal update functions. +*/ +static inline void module_immediate_setup (struct module *mod) { } +static inline void immediate_update_early (void ) { } +#endif + +/** +* DEFINE_IMMEDIATE_TYPE - Define an immediate type +* @type: type that the immediate should hold +* @name: name of the immediate type +* +* Define new immediate types. Naming scheme is immediate_*_t. +* Always access these types with the provided functions. +*/ +#define DEFINE_IMMEDIATE_TYPE (type, name) \ + typedef struct { type value; } name + +/* +* Standard pre-defined immediate types. +*/ +DEFINE_IMMEDIATE_TYPE (char, immediate_char_t); +DEFINE_IMMEDIATE_TYPE (short, immediate_short_t); +DEFINE_IMMEDIATE_TYPE (int, immediate_int_t); +DEFINE_IMMEDIATE_TYPE (long, immediate_long_t); +DEFINE_IMMEDIATE_TYPE(void*, immediate_void_ptr_t); + +/** +* IMMEDIATE_INIT - Static initialization of an immediate variable +* @i: required value +* +* Use this macro to initialize an immediate value to an initial static +* value. +*/ +#define IMMEDIATE_INIT (i) { (i) } + +/** +* _immediate_read - Read immediate value with standard memory load. +* @var: pointer of type immediate_*_t +* +* Force a data read of the immediate value instead of the immediate value +* based mechanism. Useful for __init and __exit section data read. +*/ +#define _immediate_read (var) (var)->value + +/* +* _immediate_if - if () statement depending on immediate value (memory load) +* @var: pointer of type immediate_*_t +* +* Force the use of a normal if () statement depending on an immediate value. +*/ +#define _immediate_if (var) if (_immediate_read(var)) + +#endif
include/asm-generic/vmlinux.lds.h +7 -0
@@ -122,6 +122,13 @@ VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .; \ } \ \ +/* Immediate values: pointers */ \ + __immediate : AT(ADDR(__immediate) - LOAD_OFFSET) { \ + VMLINUX_SYMBOL(__start___immediate) = .; \ + *(__immediate ) \ + VMLINUX_SYMBOL(__stop___immediate) = .; \ + } \ + \/* Kernel symbol table: strings */ \ __ksymtab_strings : AT(ADDR(__ksymtab_strings) - LOAD_OFFSET) { \ *(__ksymtab_strings) \
include/linux/module.h +6 -0
@@ -15,6 +15,7 @@#include <linux/stringify.h> #include <linux/kobject.h> #include <linux/moduleparam.h> +#include <linux/immediate.h> #include <asm/local.h> #include <asm/module.h>
@@ -374,6 +375,11 @@ struct module/* The command line arguments (may be mangled). People like keeping pointers to this stuff */ char *args; + +#ifdef CONFIG_IMMEDIATE +const struct __immediate *immediate; +unsigned int num_immediate; +#endif };#ifndef MODULE_ARCH_INIT #define MODULE_ARCH_INIT {}
kernel/module.c +16 -0
@@ -33,6 +33,7 @@#include <linux/cpu.h> #include <linux/moduleparam.h> #include <linux/errno.h> +#include <linux/immediate.h> #include <linux/err.h> #include <linux/vermagic.h> #include <linux/notifier.h>
@@ -1719,6 +1720,7 @@ static struct module *load_module(void _unsigned int unusedcrcindex;unsigned int unusedgplindex;unsigned int unusedgplcrcindex; +unsigned int immediateindex =0 ;struct module *mod;long err =0 ;void *percpu =NULL , *ptr =NULL ;/* Stops spurious gcc warning */
@@ -1815,6 +1817,9 @@ static struct module *load_module(void _#ifdef ARCH_UNWIND_SECTION_NAME unwindex =find_sec (hdr, sechdrs, secstrings,ARCH_UNWIND_SECTION_NAME );#endif +#ifdef CONFIG_IMMEDIATE + immediateindex =find_sec (hdr, sechdrs, secstrings,"__immediate" ); +#endif /* Don't keep modinfo section */ sechdrs[infoindex].sh_flags &= ~(unsigned long )SHF_ALLOC ;
@@ -1825,6 +1830,8 @@ static struct module *load_module(void _#endif if (unwindex) sechdrs[unwindex].sh_flags |=SHF_ALLOC ; +if (immediateindex) + sechdrs[immediateindex].sh_flags |=SHF_ALLOC ;/* Check module struct version now, before we try to use module. */ if (!check_modstruct_version (sechdrs, versindex, mod)) {
@@ -1965,6 +1972,13 @@ static struct module *load_module(void _ mod->gpl_future_syms = (void *)sechdrs[gplfutureindex].sh_addr;if (gplfuturecrcindex) mod->gpl_future_crcs = (void *)sechdrs[gplfuturecrcindex].sh_addr; +#ifdef CONFIG_IMMEDIATE +if (immediateindex) { + mod->immediate = (void *)sechdrs[immediateindex].sh_addr; + mod->num_immediate = + sechdrs[immediateindex].sh_size /sizeof (*mod->immediate); + } +#endif mod->unused_syms = (void *)sechdrs[unusedindex].sh_addr;if (unusedcrcindex)
@@ -2031,6 +2045,8 @@ static struct module *load_module(void _ }#endif +module_immediate_setup (mod); + err =module_finalize (hdr, sechdrs, mod);if (err <0 ) goto cleanup;
kernel/Makefile +1 -0
@@ -57,6 +57,7 @@ obj-$(CONFIG_RELAY) += relay.o obj-$(CONFIG_SYSCTL) += utsname_sysctl.o obj-$(CONFIG_TASK_DELAY_ACCT) += delayacct.o obj-$(CONFIG_TASKSTATS) += taskstats.o tsacct.o +obj-$(CONFIG_IMMEDIATE) += immediate.o ifneq ($(CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER),y) # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is
kernel/immediate.c new file +128 -0
128 lines not on this page · raw message
init/main.c +2 -0
@@ -56,6 +56,7 @@#include <linux/pid_namespace.h> #include <linux/device.h> #include <linux/kthread.h> +#include <linux/immediate.h> #include <asm/io.h> #include <asm/bugs.h>
@@ -521,6 +522,7 @@ asmlinkage void __init start_kernel(voidunwind_init ();lockdep_init ();container_init_early (); +immediate_update_early ();local_irq_disable ();early_boot_irqs_off ();
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
Re: [patch 2/8] Immediate Values - Architecture Independent Code
Quoted 38 lines · Mathieu Desnoyers
Immediate values are used as read mostly variables that are rarely updated. They use code patching to modify the values inscribed in the instruction stream. It provides a way to save precious cache lines that would otherwise have to be used by these variables.
There is a generic
_immediate_read()version, which uses standard global variables, and optimized per architectureimmediate_read()implementations, which use a load immediate to remove a data cache hit. When the immediate values functionnality is disabled in the kernel, it falls back to global variables.It adds a new rodata section "
__immediate" to place the pointers to the enable value. Immediate values activation functions sits inkernel/immediate.c.Immediate values refer to the memory address of a previously declared integer. This integer holds the information about the state of the immediate values associated, and must be accessed through the API found in
linux/immediate.h.At module load time, each immediate value is checked to see if it must be enabled. It would be the case if the variable they refer to is exported from another module and already enabled.
In the early stages of
start_kernel(), the immediate values are updated to reflect the state of the variable they refer to.* Why should this be merged *
It improves performances on heavy memory I/O workloads.
An interesting result shows the potential this infrastructure has by showing the slowdown a simple system call such as
getppid()suffers when it is used under heavy user-space cache trashing:Random walk L1 and L2 trashing surrounding a
getppid()call:
(note: in this test,do_syscal_tracewas taken at each system call, seeDocumentation/immediate.txtin these patches for details)
- No memory pressure :getppid()takes 1573 cycles
- With memory pressure :getppid()takes 15589 cycles
Quoted 4 lines
We therefore have a slowdown of 10 times just to get the kernel variables from memory. Another test on the same architecture (Intel P4) measured the memory latency to be 559 cycles. Therefore, each cache line removed from the hot path would improve the syscall time of 3.5% in these conditions.
I still think this is bad idea:
1) already existing CPU erratas against popular models. As I learned yesterday -- SILENT reboot (often) or hang (rare).
2) new type pretending to be standard and idiomatic -- immediate_t
3) new almost-C-keyword -- immediate_if. What does it mean? You'll never guess just by looking at it.
4) numbers! it's very entertaining to look at numbers with 4 digits after comma and without any attempts to do error estimates.
5) examples!
DEFINE_IMMEDIATE_TYPE(struct task_struct*, immediate_task_struct_ptr_t); immediate_task_struct_ptr_t myptr;
this is close to hungarian notation, and threats were made to use immediate stuff everywhere.
6) hundreds lines of new code playing with dynamic modifying
For what you ask?
For 1 (one) cacheline saving in schedule() which
unlike getpid/getppid is non-trivial function, so all rosy numbers about speed savings aren't really applicable. And nobody measured how big it is on macro benchmark.
So, this stuff should be put into CoolHacks case and put aside. It just not worth it!
A side note, folks at KS can discuss barrier for merging speed improvements. My feelings are around 1%.
Re: [patch 2/8] Immediate Values - Architecture Independent Code
Quoted 39 lines · * Alexey Dobriyan ([email protected]) wrote:
Quoted 38 lines · Mathieu Desnoyers
Immediate values are used as read mostly variables that are rarely updated. They use code patching to modify the values inscribed in the instruction stream. It provides a way to save precious cache lines that would otherwise have to be used by these variables.
There is a generic
_immediate_read()version, which uses standard global variables, and optimized per architectureimmediate_read()implementations, which use a load immediate to remove a data cache hit. When the immediate values functionnality is disabled in the kernel, it falls back to global variables.It adds a new rodata section "
__immediate" to place the pointers to the enable value. Immediate values activation functions sits inkernel/immediate.c.Immediate values refer to the memory address of a previously declared integer. This integer holds the information about the state of the immediate values associated, and must be accessed through the API found in
linux/immediate.h.At module load time, each immediate value is checked to see if it must be enabled. It would be the case if the variable they refer to is exported from another module and already enabled.
In the early stages of
start_kernel(), the immediate values are updated to reflect the state of the variable they refer to.* Why should this be merged *
It improves performances on heavy memory I/O workloads.
An interesting result shows the potential this infrastructure has by showing the slowdown a simple system call such as
getppid()suffers when it is used under heavy user-space cache trashing:Random walk L1 and L2 trashing surrounding a
getppid()call:
(note: in this test,do_syscal_tracewas taken at each system call, seeDocumentation/immediate.txtin these patches for details)
- No memory pressure :getppid()takes 1573 cycles
- With memory pressure :getppid()takes 15589 cycles
Quoted 8 lines
Quoted 4 lines
We therefore have a slowdown of 10 times just to get the kernel variables from memory. Another test on the same architecture (Intel P4) measured the memory latency to be 559 cycles. Therefore, each cache line removed from the hot path would improve the syscall time of 3.5% in these conditions.
I still think this is bad idea:
1) already existing CPU erratas against popular models. As I learned yesterday -- SILENT reboot (often) or hang (rare).
I understand your fears. Actually, I had the same reaction when I heard about the djprobes project. What I am doing with the immediate values are a quite simpler version of live code patching which limits what has to be patched to a very simple subset of instructions which layout (alignment, etc) can be controlled.
I have taken the said erratas into consideration and developed the algorithms that makes sure they won't be triggered. I would suggest that you present test cases that proves your fear right, or if you could cite documentation of the specific CPU models upon which you base your comment.
Reproducing the errata both on PIII and Intel Core2 duo seems very hard to achieve. If anyone out there have a "known" test case to trigger the fault, I would gladly do some more testing to show the behavior without my algorithm (non working) vs with my algorithm in the same conditions.
Quoted 1 line
2) new type pretending to be standard and idiomatic --
immediate_t
Representing the data referred to by immediate_reads seems important to me, because not doing so would result in people updating the variable directly without using immediate_set, which, of course, would not update all the references to the variable. If you have better suggestions, I am open to them.
Quoted 2 lines
3) new almost-C-keyword --
immediate_if. What does it mean? You'll never guess just by looking at it.
It's a special if() statement that uses its argument (an immediate value) as a condition for a branch. The reason why it's not under the form if (immediate_read(var)) is because I want to leave room from improvement if gcc guys ever want to implement nop/jmp based branches that could be patchable at runtime.
Quoted 2 lines
4) numbers! it's very entertaining to look at numbers with 4 digits after comma and without any attempts to do error estimates.
Here are the test redone with error estimates :
10 runs of 100 iterations each: (I don't have more time to do the 10000 iterations I've done the first time, sorry, stats will take care of showing the errors appropriately). Tests done on a 3GHz P4. Here I run getppid with syscall trace inactive, comparing memory pressure and w/o memory pressure. (sorry, my system is not setup to execute syscall_trace this time, but it will make the point anyway).
No memory pressure
Reading timestamps: 150.92 cycles, std dev. 1.01 cycles getppid: 1462.09 cycles, std dev. 18.87 cycles
With memory pressure
Reading timestamps: 578.22 cycles, std dev. 269.51 cycles getppid: 17113.33 cycles, std dev. 1655.92 cycles
Now for memory read timing: (10 runs, branches per test: 100000) Memory read based branch:
644.09 cycles, std dev. 11.39 cycles
L1 cache hit based branch:
88.16 cycles, std dev. 1.35 cyclesSo, now that we have the raw results, let's calculate:
Memory read:
644.09±11.39 - 88.16±1.35 = 555.93±11.46 cycles
Getppid without memory pressure:
1462.09±18.87 - 150.92±1.01 = 1311.17±18.90 cycles
Getppid with memory pressure:
17113.33±1655.92 - 578.22±269.51 = 16535.11±1677.71 cycles
Therefore, if we add 2 markers not based on immediate values to the getppid code, which would add 2 memory reads, we would add
2 * 555.93±12.74 = 1111.86±25.48 cycles
Therefore,
1111.86±25.48 / 16535.11±1677.71 = 0.0672
relative error: sqrt(((25.48/1111.86)^2)+((1677.71/16535.11)^2))
= 0.1040
absolute error: 0.1040 * 0.0672 = 0.0070
Therefore: 0.0672±0.0070 * 100% = 6.72±0.70 %
We can therefore affirm that adding 2 markers to getppid, on a system with high memory pressure, would have a performance hit of at least 6.0 % on the system call time, all within the uncertainty limits of these tests. The same applies to other kernel code paths. The smaller those code paths are, the highest the impact ratio will be.
Quoted 7 lines
5) examples!
DEFINE_IMMEDIATE_TYPE(struct task_struct*, immediate_task_struct_ptr_t); immediate_task_struct_ptr_t myptr;this is close to hungarian notation, and threats were made to use immediate stuff everywhere.
Same reason as 2). Note that the standard case is immediate_int_t, immediate_long_t... and is not as bad as having to express the whole pointer type in the type name. That's the best tradeoff between restricting direct update of these pointers and code readability I have seen. I am open to better solutions...
Quoted 6 lines
6) hundreds lines of new code playing with dynamic modifying
For what you ask?
Quoted 9 lines
For 1 (one) cacheline saving in
schedule()which
unlike getpid/getppid is non-trivial function, so all rosy numbers about speed savings aren't really applicable. And nobody measured how big it is on macro benchmark.So, this stuff should be put into CoolHacks case and put aside. It just not worth it!
I think you are missing the whole point there. The scheduler profiling patch is only an example of how immediate values can be used. Timer stats would perfectly fit too, blktrace, .... actually, any feature that is very useful to have in a distro, but where the choice much be made at compile time can now be temporarily activated at runtime when needed.
"unlike getpid/getppid is non-trivial function" : I am instrumenting a *lot* of kernel paths with LTTng, including do_syscall_entry and do_syscall_exit, which happen to be executed upon *all* system calls when tracing is active. I used getppid (tracing inactive, but do_syscal_trace forced) to exemplify the performance difference of a simple system call, but you must note that it applies to _every_ system call in the kernel. I've seen people complain when impact of a dormant tracer on the select() system call is noticeable _at all_, so, yes, a 3.5% impact on getppid is meaningful.
Quoted 3 lines
A side note, folks at KS can discuss barrier for merging speed improvements. My feelings are around 1%.
Should they discuss what performance deterioration is acceptable for new infrastructures such as tracer too ? In the end, they may decide that "it can be compiled away anyway", but distros will not ship kernels with features that slows down the kernel and people will still complain that Linux does not ship with a tracing alternative comparable to Dtrace.
The question that arises when selecting a new feature is not "what is the average performance improvement of this", but rather "what is the worse case performance hit". This is exactly what I address.
Mathieu
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 3/8 Immediate Values - Kconfig menu in EMBEDDED
In reply to Mathieu DesnoyersImmediate values provide a way to use dynamic code patching to update variables sitting within the instruction stream. It saves caches lines normally used by static read mostly variables. Enable it by default, but let users disable it through the EMBEDDED menu with the "Disable immediate values" submenu entry.
--- init/Kconfig | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+)
init/Kconfig +21 -0
@@ -411,6 +411,17 @@ config CC_OPTIMIZE_FOR_SIZE config SYSCTL bool +config IMMEDIATE + default y if !DISABLE_IMMEDIATE + depends on X86_32 || PPC || PPC64 + bool + help + Immediate values are used as read mostly variables that are rarely + updated. They use code patching to modify the values inscribed in the + instruction stream. It provides a way to save precious cache lines + that would otherwise have to be used by these variables. Can be + disabled through the EMBEDDED menu. + menuconfig EMBEDDED bool "Configure standard kernel features (for small systems)" help
@@ -649,6 +660,16 @@ config PROC_KPAGEMAP information on page-level memory usage. Disabling this interface will reduce the size of the kernel by around 600 bytes. +config DISABLE_IMMEDIATE + default y if EMBEDDED + bool "Disable immediate values" if EMBEDDED + depends on X86_32 || PPC || PPC64 + help + Disable code patching based immediate values for embedded systems. It + consumes slightly more memory and requires to modify the instruction + stream each time a variable is updated. Should really be disabled for + embedded systems with read-only text. + endmenu # General setup config RT_MUTEXES
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 4/8 Immediate Values - Move Kprobes i386 restore_interrupt to kdebug.h
In reply to Mathieu DesnoyersSince the breakpoint handler is useful both to kprobes and immediate values, it makes sense to make the required restore_interrupt() available through asm-i386/kdebug.h.
--- include/asm-i386/kdebug.h | 12 ++++++++++++ include/asm-i386/kprobes.h | 9 --------- 2 files changed, 12 insertions(+), 9 deletions(-)
include/asm-i386/kdebug.h +12 -0
@@ -6,6 +6,9 @@* from x86_64 architecture. */ +#include <asm/ptrace.h> +#include <asm/system.h> +struct pt_regs ;/* Grossly misnamed. */
@@ -25,4 +28,13 @@ enum die_val { DIE_PAGE_FAULT_NO_CONTEXT, }; +/* trap3/1 are intr gates for kprobes. So, restore the status of IF, +* if necessary, before executing the original int3/1 (trap) handler. +*/ +static inline void restore_interrupts (struct pt_regs *regs) +{ +if (regs->eflags &IF_MASK ) +local_irq_enable (); +} +#endif
include/asm-i386/kprobes.h +0 -9
@@ -77,15 +77,6 @@ struct kprobe_ctlblk {struct prev_kprobe prev_kprobe; }; -/* trap3/1 are intr gates for kprobes. So, restore the status of IF, -* if necessary, before executing the original int3/1 (trap) handler. -*/ -static inline void restore_interrupts (struct pt_regs *regs) -{ -if (regs->eflags &IF_MASK ) -local_irq_enable (); -} -extern int kprobe_exceptions_notify (struct notifier_block *self,unsigned long val,void *data);extern int kprobe_fault_handler (struct pt_regs *regs,int trapnr);
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 5/8 Immediate Values - i386 Optimization
In reply to Mathieu Desnoyersi386 optimization of the immediate values which uses a movl with code patching to set/unset the value used to populate the register used as variable source.
--- arch/i386/kernel/Makefile | 1 arch/i386/kernel/immediate.c | 301 +++++++++++++++++++++++++++++++++++++++++++ arch/i386/kernel/traps.c | 8 - include/asm-i386/immediate.h | 137 +++++++++++++++++++ 4 files changed, 443 insertions(+), 4 deletions(-)
include/asm-i386/immediate.h new file +137 -0
@@ -0,0 +1,137 @@ +#ifndef _ASM_I386_IMMEDIATE_H +#define _ASM_I386_IMMEDIATE_H + +/* +* Immediate values. i386 architecture optimizations. +* +* (C) Copyright 2006 Mathieu Desnoyers <[email protected]> +* +* This file is released under the GPLv2. +* See the file COPYING for more details. +*/ + +struct module ; + +struct __immediate { +long var;/* Pointer to the identifier variable of the +* immediate value +*/ +long immediate;/* +* Pointer to the memory location of the +* immediate value within the instruction. +*/ +long size;/* Type size. */ +}; + +/** +* immediate_read - read immediate variable +* @var: pointer of type immediate_*_t +* +* Reads the value of @var. +* Optimized version of the immediate. +* Do not use in __init and __exit functions. Use _immediate_read() instead. +* Makes sure the 2 and 4 bytes update will be atomic by aligning the immediate +* value. 2 bytes (short) uses a 66H prefix. If size is bigger than 4 bytes, +* fall back on a memory read. +*/ +#define immediate_read (var) \ + ({ \ + __typeof__((var)->value) value; \ + switch (sizeof(value)) { \ + case 1: \ + asm ( ".section __immediate, \"a\", @progbits;\n\t" \ + ".long %1, (0f)+1, 1;\n\t" \ + ".previous;\n\t" \ + "0:\n\t" \ + "mov %2,%0;\n\t" \ + : "=r" (value) \ + : "m" ((var)->value), \ + "i" (0)); \ + break; \ + case 2: \ + asm ( ".section __immediate, \"a\", @progbits;\n\t" \ + ".long %1, (0f)+2, 2;\n\t" \ + ".previous;\n\t" \ + "1:\n\t" \ + ".align 2;\n\t" \ + "0:\n\t" \ + "mov %2,%0;\n\t" \ + : "=r" (value) \ + : "m" ((var)->value), \ + "i" (0)); \ + break; \ + case 4: \ + asm ( ".section __immediate, \"a\", @progbits;\n\t" \ + ".long %1, (0f)+1, 4;\n\t" \ + ".previous;\n\t" \ + "1:\n\t" \ + ".org (1b)+(3-((1b)%%4)), 0x90;\n\t" \ + "0:\n\t" \ + "mov %2,%0;\n\t" \ + : "=r" (value) \ + : "m" ((var)->value), \ + "i" (0)); \ + break; \ + default:value = (var)->value; \ + break; \ + }; \ + value; \ + }) + + +/** +* immediate_set - set immediate variable (with locking) +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var, taking the module_mutex if required by +* the architecture. +*/ +#define immediate_set (var, i) \ + (var)->value = (i); \ + immediate_update(1); + +/** +* _immediate_set - set immediate variable (without locking) +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var. Must be called with module_mutex held. +*/ +#define _immediate_set (var, i) \ + (var)->value = (i); \ + immediate_update(0); + +/** +* immediate_set_early - set immediate variable at early boot +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var. Should be used for early boot updates. +*/ +#define immediate_set_early (var, i) \ + (var)->value = (i); \ + immediate_update_early(); + +/** +* immediate_if - if () statement depending on an immediate value +* @var: pointer of type immediate_*_t +* +* Use as an if () statement depending on an immediate value. +* Do not use in __init and __exit functions. Use _immediate_if() instead. +* Branch depending on an immediate value. Could eventually be optimized further +* by improving gcc to give the ability to patch a jump instruction instead of +* the value it depends on. +*/ +#define immediate_if (var) if (unlikely(immediate_read(var))) + +/* +* Internal update functions. +*/ +extern void immediate_update (int lock); +extern void module_immediate_setup (struct module *mod); +extern void immediate_update_early (void ); +extern int arch_immediate_update (const struct __immediate *immediate); +extern void arch_immediate_update_early (const struct __immediate *immediate); + +#endif /* _ASM_I386_IMMEDIATE_H */
arch/i386/kernel/Makefile +1 -0
@@ -36,6 +36,7 @@ obj-$(CONFIG_MODULES) += module.o obj-y += sysenter.o vsyscall.o obj-$(CONFIG_ACPI_SRAT) += srat.o obj-$(CONFIG_EFI) += efi.o efi_stub.o +obj-$(CONFIG_IMMEDIATE) += immediate.o obj-$(CONFIG_DOUBLEFAULT) += doublefault.o obj-$(CONFIG_KGDB) += kgdb.o kgdb-jmp.o obj-$(CONFIG_VM86) += vm86.o
arch/i386/kernel/immediate.c new file +301 -0
301 lines not on this page · raw message
arch/i386/kernel/traps.c +4 -4
@@ -564,7 +564,7 @@ fastcall void do_##name(struct pt_regs * } DO_VM86_ERROR_INFO( 0, SIGFPE, "divide error", divide_error, FPE_INTDIV, regs->eip) -#ifndef CONFIG_KPROBES +#if !defined(CONFIG_KPROBES ) && !defined(CONFIG_IMMEDIATE ) DO_VM86_ERROR( 3, SIGTRAP, "int3", int3)#endif DO_VM86_ERROR (4 ,SIGSEGV ,"overflow" , overflow)
@@ -799,14 +799,14 @@ void restart_nmi(void)acpi_nmi_enable (); } -#ifdef CONFIG_KPROBES +#if defined(CONFIG_KPROBES ) || defined(CONFIG_IMMEDIATE ) fastcall void __kprobes do_int3(struct pt_regs *regs, long error_code) {if (notify_die (DIE_INT3 ,"int3" , regs, error_code,3 ,SIGTRAP ) ==NOTIFY_STOP )return ; -/* This is an interrupt gate, because kprobes wants interrupts -disabled. Normal trap handlers don't. */ +/* This is an interrupt gate, because kprobes and immediate values wants +* interrupts disabled. Normal trap handlers don't. */ restore_interrupts (regs);do_trap (3 ,SIGTRAP ,"int3" ,1 , regs, error_code,NULL ); }
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 1/1 Immediate Values - i386 Optimization - fix warnings
Immediate Values - i386 optimization - fix warnings
2 warnings creps in caused by my recent work with text lock edit.
arch/i386/kernel/immediate.c: In function 'arch_immediate_update':arch/i386/kernel/immediate.c:228: warning: passing argument 1 of '__constant_memcpy' makes pointer from integer without a cast arch/i386/kernel/immediate.c:228: warning: passing argument 1 of '__memcpy' makes pointer from integer without a cast arch/i386/kernel/immediate.c:185: warning: unused variable 'bypass_immediate'
This trivial patch fixes this issue.
--- arch/i386/kernel/immediate.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
arch/i386/kernel/immediate.c +1 -2
@@ -182,7 +182,6 @@ __kprobes int arch_immediate_update(consint ret;size_t insn_size =_immediate_get_insn_size (immediate->size);long insn = immediate->immediate - insn_size; -long bypass_immediate;#ifdef CONFIG_KPROBES /*
@@ -225,7 +224,7 @@ __kprobes int arch_immediate_update(cons after_immediate = immediate->immediate + immediate->size;kernel_text_mark_rw ((unsigned long )bypass_eip,NR_NOPS ); -memcpy (bypass_eip, (void *)insn, insn_size + immediate->size); +memcpy ((void *)bypass_eip, (void *)insn, insn_size + immediate->size);/* * Fill the rest with nops. */
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 6/8 Immediate Values - Powerpc Optimization
In reply to Mathieu DesnoyersPowerPC optimization of the immediate values which uses a li instruction, patched with an immediate value.
--- arch/powerpc/kernel/Makefile | 1 arch/powerpc/kernel/immediate.c | 103 ++++++++++++++++++++++++++++++++ include/asm-powerpc/immediate.h | 127 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 231 insertions(+)
include/asm-powerpc/immediate.h new file +127 -0
@@ -0,0 +1,127 @@ +#ifndef _ASM_POWERPC_IMMEDIATE_H +#define _ASM_POWERPC_IMMEDIATE_H + +/* +* Immediate values. PowerPC architecture optimizations. +* +* (C) Copyright 2006 Mathieu Desnoyers <[email protected]> +* +* This file is released under the GPLv2. +* See the file COPYING for more details. +*/ + +#include <asm/asm-compat.h> + +struct module ; + +struct __immediate { +long var;/* Identifier variable of the immediate value */ +long immediate;/* +* Pointer to the memory location that holds +* the immediate value within the load immediate +* instruction. +*/ +long size;/* Type size. */ +}; + +/** +* immediate_read - read immediate variable +* @var: pointer of type immediate_*_t +* +* Reads the value of @var. +* Optimized version of the immediate. +* Do not use in __init and __exit functions. Use _immediate_read() instead. +* Makes sure the 2 bytes update will be atomic by aligning the immediate +* value. Use a normal memory read for the 4 bytes immediate because there is no +* way to atomically update it without using a seqlock read side, which would +* cost more in term of total i-cache and d-cache space than a simple memory +* read. +*/ +#define immediate_read (var) \ + ({ \ + __typeof__((var)->value) value; \ + switch (sizeof(value)) { \ + case 1: \ + asm ( ".section __immediate, \"a\", @progbits;\n\t" \ + PPC_LONG "%1, ((0f)+3), 1;\n\t" \ + ".previous;\n\t" \ + "0:\n\t" \ + "li %0,%2;\n\t" \ + : "=r" (value) \ + : "i" (&(var)->value), \ + "i" (0)); \ + break; \ + case 2: \ + asm ( ".section __immediate, \"a\", @progbits;\n\t" \ + PPC_LONG "%1, ((0f)+2), 2;\n\t" \ + ".previous;\n\t" \ + ".align 2\n\t" \ + "0:\n\t" \ + "li %0,%2;\n\t" \ + : "=r" (value) \ + : "i" (&(var)->value), \ + "i" (0)); \ + break; \ + default: \ + value = (var)->value; \ + break; \ + }; \ + value; \ + }) + +/** +* immediate_set - set immediate variable (with locking) +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var, taking the module_mutex if required by +* the architecture. +*/ +#define immediate_set (var, i) \ + (var)->value = (i); \ + immediate_update(1); + +/** +* _immediate_set - set immediate variable (without locking) +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var. Must be called with module_mutex held. +*/ +#define _immediate_set (var, i) \ + (var)->value = (i); \ + immediate_update(0); + +/** +* immediate_set_early - set immediate variable at early boot +* @var: pointer of type immediate_*_t +* @i: required value +* +* Sets the value of @var. Should be used for early boot updates. +*/ +#define immediate_set_early (var, i) \ + (var)->value = (i); \ + immediate_update_early(); + +/** +* immediate_if - if () statement depending on an immediate value +* @var: pointer of type immediate_*_t +* +* Use as an if () statement depending on an immediate value. +* Do not use in __init and __exit functions. Use _immediate_if() instead. +* Branch depending on an immediate value. Could eventually be optimized further +* by improving gcc to give the ability to patch a jump instruction instead of +* the value it depends on. +*/ +#define immediate_if (var) if (unlikely(immediate_read(var))) + +/* +* Internal update functions. +*/ +extern void immediate_update (int lock); +extern void module_immediate_setup (struct module *mod); +extern void immediate_update_early (void ); +extern int arch_immediate_update (const struct __immediate *immediate); +extern void arch_immediate_update_early (const struct __immediate *immediate); + +#endif /* _ASM_POWERPC_IMMEDIATE_H */
arch/powerpc/kernel/Makefile +1 -0
@@ -103,3 +103,4 @@ obj-$(CONFIG_PPC64) += $(obj64-y) extra-$(CONFIG_PPC_FPU) += fpu.o extra-$(CONFIG_PPC64) += entry_64.o +obj-$(CONFIG_IMMEDIATE) += immediate.o
arch/powerpc/kernel/immediate.c new file +103 -0
103 lines not on this page · raw message
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 7/8 Immediate Values - Documentation
In reply to Mathieu Desnoyers--- Documentation/immediate.txt | 180 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 180 insertions(+)
Documentation/immediate.txt new file +180 -0
@@ -0,0 +1,180 @@ + Using the Immediate Values + + Mathieu Desnoyers + + +This document introduces Immediate Values and their use. + +* Purpose of immediate values + +An immediate value is used to compile into the kernel variables that sits within +the instruction stream. They are meant to be rarely updated but read often. +Using immediate values for these variables will save cache lines. + +This infrastructure is specialized in supporting dynamic patching of the values +in the instruction stream when multiple CPUs are running without disturbing the +normal system behavior. + +Compiling code meant to be rarely enabled at runtime can be done using +immediate_if() as condition surrounding the code. + +* Usage + +In order to use the macro immediate, you should include linux/immediate.h. + +#include <linux/immediate.h> + +immediate_char_t this_immediate; +EXPORT_SYMBOL(this_immediate); + + +Add, in your code : + +Use immediate_set(&this_immediate) to set the immediate value. + +Use immediate_read(&this_immediate) to read the immediate value. + +The immediate mechanism supports inserting multiple instances of the same +immediate. Immediate values can be put in inline functions, inlined static +functions, and unrolled loops. + +If you have to read the immediate values from a function declared as __init or +__exit, you should explicitly use _immediate_read(), which will fall back on a +global variable read. Failing to do so will leave a reference to the __init +section after it is freed (it would generate a modpost warning). + +The prefered idiom to dynamically enable compiled-in code is to use +immediate_if (&this_immediate), which may eventually use gcc improvements to +provide a jump instruction patching based condition instead of a immediate value +feeding a conditional jump. You should use _immediate_if () instead of +immediate_if () in functions marked __init or __exit. + +immediate_set_early() should be used only at early kernel boot time, before SMP +is activated. + +If you need to declare your own immediate types (for instance, a pointer to +struct task_struct), use: + +DEFINE_IMMEDIATE_TYPE(struct task_struct*, immediate_task_struct_ptr_t); + +and declare your variable with: +immediate_task_struct_ptr_t myptr; + +You can choose to set an initial static value to the immediate by using, for +instance: + +immediate_task_struct_ptr_t myptr = IMMEDIATE_INIT(10); + + +* Optimization for a given architecture + +One can implement optimized immediate values for a given architecture by +replacing asm-$ARCH/immediate.h. + +* Performance improvement + +* Memory hit for a data-based branch + +Here are the results on a 3GHz Pentium 4: + +number of tests : 100 +number of branches per test : 100000 +memory hit cycles per iteration (mean) : 636.611 +L1 cache hit cycles per iteration (mean) : 89.6413 +instruction stream based test, cycles per iteration (mean) : 85.3438 +Just getting the pointer from a modulo on a pseudo-random value, doing + noting with it, cycles per iteration (mean) : 77.5044 + +So: +Base case: 77.50 cycles +instruction stream based test: +7.8394 cycles +L1 cache hit based test: +12.1369 cycles +Memory load based test: +559.1066 cycles + +So let's say we have a ping flood coming at +(14014 packets transmitted, 14014 received, 0% packet loss, time 1826ms) +7674 packets per second. If we put 2 markers for irq entry/exit, it +brings us to 15348 markers sites executed per second. + +(15348 exec/s) * (559 cycles/exec) / (3G cycles/s) = 0.0029 +We therefore have a 0.29% slowdown just on this case. + +Compared to this, the instruction stream based test will cause a +slowdown of: + +(15348 exec/s) * (7.84 cycles/exec) / (3G cycles/s) = 0.00004 +For a 0.004% slowdown. + +If we plan to use this for memory allocation, spinlock, and all sort of +very high event rate tracing, we can assume it will execute 10 to 100 +times more sites per second, which brings us to 0.4% slowdown with the +instruction stream based test compared to 29% slowdown with the memory +load based test on a system with high memory pressure. + + + +* Markers impact under heavy memory load + +Running a kernel with my LTTng instrumentation set, in a test that +generates memory pressure (from userspace) by trashing L1 and L2 caches +between calls to getppid() (note: syscall_trace is active and calls +a marker upon syscall entry and syscall exit; markers are disarmed). +This test is done in user-space, so there are some delays due to IRQs +coming and to the scheduler. (UP 2.6.22-rc6-mm1 kernel, task with -20 +nice level) + +My first set of results : Linear cache trashing, turned out not to be +very interesting, because it seems like the linearity of the memset on a +full array is somehow detected and it does not "really" trash the +caches. + +Now the most interesting result : Random walk L1 and L2 trashing +surrounding a getppid() call. + +- Markers compiled out (but syscall_trace execution forced) +number of tests : 10000 +No memory pressure +Reading timestamps takes 108.033 cycles +getppid : 1681.4 cycles +With memory pressure +Reading timestamps takes 102.938 cycles +getppid : 15691.6 cycles + + +- With the immediate values based markers: +number of tests : 10000 +No memory pressure +Reading timestamps takes 108.006 cycles +getppid : 1681.84 cycles +With memory pressure +Reading timestamps takes 100.291 cycles +getppid : 11793 cycles + + +- With global variables based markers: +number of tests : 10000 +No memory pressure +Reading timestamps takes 107.999 cycles +getppid : 1669.06 cycles +With memory pressure +Reading timestamps takes 102.839 cycles +getppid : 12535 cycles + + +The result is quite interesting in that the kernel is slower without +markers than with markers. I explain it by the fact that the data +accessed is not layed out in the same manner in the cache lines when the +markers are compiled in or out. It seems that it aligns the function's +data better to compile-in the markers in this case. + +But since the interesting comparison is between the immediate values and +global variables based markers, and because they share the same memory +layout, except for the movl being replaced by a movz, we see that the +global variable based markers (2 markers) adds 742 cycles to each system +call (syscall entry and exit are traced and memory locations for both +global variables lie on the same cache line). + +Therefore, not only is it interesting to use the immediate values to +dynamically activate dormant code such as the markers, but I think it +should also be considered as a replacement for many of the "read mostly" +static variables.
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
PATCH 8/8 Scheduler Profiling - Use Immediate Values
In reply to Mathieu DesnoyersUse immediate values with lower d-cache hit in optimized version as a condition for scheduler profiling call.
--- drivers/kvm/svm.c | 2 +- drivers/kvm/vmx.c | 2 +- include/linux/profile.h | 10 ++++------ kernel/profile.c | 38 ++++++++++++++++++++++++++------------ kernel/sched.c | 3 ++- 5 files changed, 34 insertions(+), 21 deletions(-)
kernel/profile.c +26 -12
@@ -42,9 +42,6 @@static atomic_t *prof_buffer;static unsigned long prof_len, prof_shift; -int prof_on__read_mostly ; -EXPORT_SYMBOL_GPL (prof_on); -static cpumask_t prof_cpu_mask =CPU_MASK_ALL ;#ifdef CONFIG_SMP static DEFINE_PER_CPU(struct profile_hit *[2], cpu_profile_hits);
@@ -52,6 +49,14 @@static DEFINE_MUTEX (profile_flip_mutex);#endif /* CONFIG_SMP */ +/* Immediate values */ +immediate_char_t sleep_profiling__read_mostly , + sched_profiling__read_mostly , + kvm_profiling__read_mostly , + cpu_profiling__read_mostly ; +EXPORT_SYMBOL_GPL (kvm_profiling); +EXPORT_SYMBOL_GPL (cpu_profiling); +static int __init profile_setup (char * str) {static char __initdata schedstr[] ="schedule" ;
@@ -60,7 +65,7 @@int par;if (!strncmp (str, sleepstr,strlen (sleepstr))) { - prof_on =SLEEP_PROFILING ; +immediate_set_early (&sleep_profiling,1 );if (str[strlen (sleepstr)] ==',' ) str +=strlen (sleepstr) +1 ;if (get_option (&str, &par))
@@ -69,7 +74,7 @@"kernel sleep profiling enabled (shift: %ld)\n" , prof_shift); }else if (!strncmp (str, schedstr,strlen (schedstr))) { - prof_on =SCHED_PROFILING ; +immediate_set_early (&sched_profiling,1 );if (str[strlen (schedstr)] ==',' ) str +=strlen (schedstr) +1 ;if (get_option (&str, &par))
@@ -78,7 +83,7 @@"kernel schedule profiling enabled (shift: %ld)\n" , prof_shift); }else if (!strncmp (str, kvmstr,strlen (kvmstr))) { - prof_on =KVM_PROFILING ; +immediate_set_early (&kvm_profiling,1 );if (str[strlen (kvmstr)] ==',' ) str +=strlen (kvmstr) +1 ;if (get_option (&str, &par))
@@ -88,7 +93,7 @@ prof_shift); }else if (get_option (&str, &par)) { prof_shift = par; - prof_on =CPU_PROFILING ; +immediate_set_early (&cpu_profiling,1 );printk (KERN_INFO "kernel profiling enabled (shift: %ld)\n" , prof_shift); }
@@ -99,7 +104,10 @@void __init profile_init (void ) { -if (!prof_on) +if (!_immediate_read (&sleep_profiling) && + !_immediate_read (&sched_profiling) && + !_immediate_read (&kvm_profiling) && + !_immediate_read (&cpu_profiling))return ;/* only text is profiled */
@@ -288,7 +296,7 @@int i, j, cpu;struct profile_hit *hits; -if (prof_on != type || !prof_buffer) +if (!prof_buffer)return ; pc =min ((pc - (unsigned long )_stext) >> prof_shift, prof_len -1 ); i = primary = (pc & (NR_PROFILE_GRP -1 )) <<PROFILE_GRPSHIFT ;
@@ -398,7 +406,7 @@ {unsigned long pc; -if (prof_on != type || !prof_buffer) +if (!prof_buffer)return ; pc = ((unsigned long )__pc - (unsigned long )_stext) >> prof_shift;atomic_add (nr_hits, &prof_buffer[min (pc, prof_len -1 )]);
@@ -555,7 +563,10 @@ }return 0 ; out_cleanup: - prof_on =0 ; +immediate_set_early (&sleep_profiling,0 ); +immediate_set_early (&sched_profiling,0 ); +immediate_set_early (&kvm_profiling,0 ); +immediate_set_early (&cpu_profiling,0 );smp_mb ();on_each_cpu (profile_nop,NULL ,0 ,1 );for_each_online_cpu (cpu) {
@@ -582,7 +593,10 @@ {struct proc_dir_entry *entry; -if (!prof_on) +if (!_immediate_read (&sleep_profiling) && + !_immediate_read (&sched_profiling) && + !_immediate_read (&kvm_profiling) && + !_immediate_read (&cpu_profiling))return 0 ;if (create_hash_tables ())return -1 ;
include/linux/profile.h +4 -6
@@ -7,10 +7,12 @@#include <linux/init.h> #include <linux/cpumask.h> #include <linux/cache.h> +#include <linux/immediate.h> #include <asm/errno.h> -extern int prof_on__read_mostly ; +extern immediate_char_t sleep_profiling, sched_profiling, kvm_profiling, + cpu_profiling;#define CPU_PROFILING 1#define SCHED_PROFILING 2
@@ -35,11 +37,7 @@*/ static inline void profile_hit (int type,void *ip) { -/* -* Speedup for the common (no profiling enabled) case: -*/ -if (unlikely (prof_on == type)) -profile_hits (type, ip,1 ); +profile_hits (type, ip,1 ); }#ifdef CONFIG_PROC_FS
kernel/sched.c +2 -1
@@ -3241,7 +3241,8 @@if (unlikely (in_atomic_preempt_off ()) &&unlikely (!prev->exit_state))__schedule_bug (prev); -profile_hit (SCHED_PROFILING ,__builtin_return_address (0 )); + immediate_if (&sched_profiling) +profile_hit (SCHED_PROFILING ,__builtin_return_address (0 ));schedstat_inc (this_rq (), sched_cnt); }
drivers/kvm/svm.c +1 -1
@@ -1654,7 +1654,7 @@/* * Profile KVM exit RIPs: */ -if (unlikely (prof_on ==KVM_PROFILING )) + immediate_if (&kvm_profiling)profile_hit (KVM_PROFILING , (void *)(unsigned long )vcpu->svm->vmcb->save.rip);
drivers/kvm/vmx.c +1 -1
@@ -2156,7 +2156,7 @@/* * Profile KVM exit RIPs: */ -if (unlikely (prof_on ==KVM_PROFILING )) + immediate_if (&kvm_profiling)profile_hit (KVM_PROFILING , (void *)vmcs_readl (GUEST_RIP )); vcpu->launched =1 ;
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
Quoted 4 lines · Mathieu Desnoyers
Hi Andrew,
Here is the latest version of immediate values. It applies on 2.6.23-rc2-mm2 in this order:
I have a concern; you seem to be patching potentially "live" code....
there are basically two options
1) you run the risk of triple faulting (patching an instruction while some other core/cpu may be decoding it may cause a triple fault)
2) you do an IPI to all other cpus and prevent them from executing any code except a small loop during the patching... this is expensive.
To be honest, neither sound very attractive to me ;(
Quoted 10 lines · * Arjan van de Ven ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
Hi Andrew,
Here is the latest version of immediate values. It applies on 2.6.23-rc2-mm2 in this order:
I have a concern; you seem to be patching potentially "live" code....
Quoted 8 lines
there are basically two options
1) you run the risk of triple faulting (patching an instruction while some other core/cpu may be decoding it may cause a triple fault)
2) you do an IPI to all other cpus and prevent them from executing any code except a small loop during the patching... this is expensive.To be honest, neither sound very attractive to me ;(
Yup, the concern is appropriate. That's why I dealt with it in the "Immediate Values - i386 Optimization" patch. (I guess your concern is specific to i386, x86_64 and ia64).
I have currently only implemented the i386 optimization, but x86_64 and ia64 should be similar.
The triple fault in question is discussed in Intel's errata under the title "Centrino Duo Processor Technology Specification Update, AH33. Unsynchronized Cross-Modifying Code Operations Can Cause Unexpected Instruction Execution Results." (if you refer to something else, please tell me).
I discuss thoroughly the algorithm I use in the patch comments, which is none of the two options you point out.
Quoting the patch:
"Overall design
The algorithm proposed by Intel applies not so well in kernel context: it would imply disabling interrupts and looping on every CPUs while modifying the code and would not support instrumentation of code called from interrupt sources that cannot be disabled.
Therefore, we use a different algorithm to respect Intel's erratum (see the quoted discussion above). We make sure that no CPU sees an out-of-date copy of a pre-fetched instruction by 1 - using a breakpoint, which skips the instruction that is going to be modified, 2 - issuing an IPI to every CPU to execute a sync_core(), to make sure that even when the breakpoint is removed, no cpu could possibly still have the out-of-date copy of the instruction, modify the now unused 2nd byte of the instruction, and then put back the original 1st byte of the instruction.
It has exactly the same intent as the algorithm proposed by Intel, but it has less side-effects, scales better and supports NMI, SMI and MCE."
Moreover, just to be cautious, I arrange the alignment of instructions to modify so their updates will be atomic. Therefore, a 5 bytes movl will always be aligned on 4 bytes boundaries - 1, so the immediate value that follows the 1 byte opcode will be itself aligned on 4 bytes boundaries.
Mathieu
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68
Quoted 9 lines
Quoted 9 lines
I have a concern; you seem to be patching potentially "live" code....
there are basically two options
1) you run the risk of triple faulting (patching an instruction while some other core/cpu may be decoding it may cause a triple fault)
2) you do an IPI to all other cpus and prevent them from executing any code except a small loop during the patching... this is expensive.
Quoted 6 lines
Quoted 2 lines
To be honest, neither sound very attractive to me ;(
Yup, the concern is appropriate. That's why I dealt with it in the "Immediate Values - i386 Optimization" patch. (I guess your concern is specific to i386,
x86_64and ia64).
it's specific to all smp architectures I suppose
Quoted 9 lines
I have currently only implemented the i386 optimization, but
x86_64and ia64 should be similar.The triple fault in question is discussed in Intel's errata under the title "Centrino Duo Processor Technology Specification Update, AH33. Unsynchronized Cross-Modifying Code Operations Can Cause Unexpected Instruction Execution Results." (if you refer to something else, please tell me).
Core2DUO is only one generation of Intel processors; however I know that several other (if not all of them) have issues with this kind of thing in ring 0; all subtly different ;(
All other alternatives are ok right now (they all run in UP mode), but... I'm just very nervous about the amount of CPU errata in this kind of scenario. And I'm not just talking Intel, I wouldn't be surprised if the other x86 CPU vendors also have issues with this; I don't know how well they specify their errata though..
Signature · 2 lines
if you want to mail me at work (you don't), use arjan (at) linux.intel.com Test the interaction between Linux and your BIOS via http://www.linuxfirmwarekit.org
Quoted 9 lines · * Arjan van de Ven ([email protected]) wrote:
Quoted 9 lines
Quoted 9 lines
I have a concern; you seem to be patching potentially "live" code....
there are basically two options
1) you run the risk of triple faulting (patching an instruction while some other core/cpu may be decoding it may cause a triple fault)
2) you do an IPI to all other cpus and prevent them from executing any code except a small loop during the patching... this is expensive.
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
To be honest, neither sound very attractive to me ;(
Yup, the concern is appropriate. That's why I dealt with it in the "Immediate Values - i386 Optimization" patch. (I guess your concern is specific to i386,
x86_64and ia64).it's specific to all smp architectures I suppose
I would wait to see the references before doing such presumptions.. AFAIK, powerpc does not suffer from such problems. I have also seen nothing of this kind about AMD processors, so it seems to be Intel specific.
Quoted 10 lines
Quoted 9 lines
I have currently only implemented the i386 optimization, but
x86_64and ia64 should be similar.The triple fault in question is discussed in Intel's errata under the title "Centrino Duo Processor Technology Specification Update, AH33. Unsynchronized Cross-Modifying Code Operations Can Cause Unexpected Instruction Execution Results." (if you refer to something else, please tell me).
Quoted 4 lines
Core2DUO is only one generation of Intel processors; however I know that several other (if not all of them) have issues with this kind of thing in ring 0; all subtly different ;(
Yes, this errata can be found starting at the Pentium III (as explained in my patch). Can you elaborate a little more on the differences ? From what I have seem, the basic problem is always the same from PIII to core2 Duo: instruction prefetch.
Quoted 7 lines
All other alternatives are ok right now (they all run in UP mode), but... I'm just very nervous about the amount of CPU errata in this kind of scenario. And I'm not just talking Intel, I wouldn't be surprised if the other x86 CPU vendors also have issues with this; I don't know how well they specify their errata though..
You seem to be pointing out to a lot of erratas, when there is, from what I reckon, only one (basically the same) from PIII to Core 2 Duo, which is Intel specific. I have looked around and ia64 also seems to be affected by this. Can you point us out to other documentation sources please ?
Mathieu
Signature · 3 lines
Mathieu Desnoyers Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68