[patch 0/7] Immediate Values for 2.6.23-rc6-mm1

[patch 0/7] Immediate Values for 2.6.23-rc6-mm1

[Mathieu Desnoyers]

Hi Andrew,

Here are the updated immediate values, following recent discussions. The changes
were mostly made to the documentation and to function headers.

It depends on the text edit lock patches.

It applies to 2.6.23-rc6-mm1, in the following order:

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


-- 
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/7] Immediate Values - Architecture Independent Code

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-architecture-independent-code.patch --]
[-- Type: text/plain, Size: 17446 bytes --]

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 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.

Changelog:

- section __immediate is already SHF_ALLOC
- Because of the wonders of ELF, section 0 has sh_addr and sh_size 0.  So
  the if (immediateindex) is unnecessary here.
- Remove module_mutex usage: depend on functions implemented in module.c for
  that.
- Does not update tainted module's immediate values.
- remove immediate_*_t types, add DECLARE_IMMEDIATE() and DEFINE_IMMEDIATE().
  - immediate_read(&var) becomes immediate_read(var) because of this.
- Adding a new EXPORT_IMMEDIATE_SYMBOL(_GPL).
- remove immediate_if(). Should use if (unlikely(immediate_read(var))) instead.
  - Wait until we have gcc support before we add the immediate_if macro, since
    its form may have to change.
- Document immediate_set_early(). This design is chosen over immediate_init()
  because:
    - We can mark the function __init so it is freed after boot.
    - Module code patching can also be done by the "normal" function. This is
      preferred, even if it can be slightly slower, because update performance
      does not matter.
    - immediate_init() could confuse users because we can actually "initialize"
      an immediate value to a certain value, which will be used as initial
      value. e.g.:
        static DEFINE_IMMEDIATE(int, var) = 10;

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
---
 include/asm-generic/vmlinux.lds.h |    7 ++
 include/linux/immediate.h         |  133 ++++++++++++++++++++++++++++++++++++++
 include/linux/module.h            |   17 ++++
 init/main.c                       |    2 
 kernel/Makefile                   |    1 
 kernel/immediate.c                |   92 ++++++++++++++++++++++++++
 kernel/module.c                   |   49 ++++++++++++++
 7 files changed, 301 insertions(+)

Index: linux-2.6-lttng/include/linux/immediate.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6-lttng/include/linux/immediate.h	2007-09-17 13:38:32.000000000 -0400
@@ -0,0 +1,133 @@
+#ifndef _LINUX_IMMEDIATE_H
+#define _LINUX_IMMEDIATE_H
+
+/*
+ * Immediate values, can be updated at runtime and save cache lines.
+ *
+ * (C) Copyright 2007 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
+ *
+ * This file is released under the GPLv2.
+ * See the file COPYING for more details.
+ */
+
+#ifdef CONFIG_IMMEDIATE
+
+#include <asm/immediate.h>
+
+/**
+ * immediate_set - set immediate variable (with locking)
+ * @name: immediate value name
+ * @i: required value
+ *
+ * Sets the value of @name, taking the module_mutex if required by
+ * the architecture.
+ */
+#define immediate_set(name, i)						\
+	do {								\
+		name##__immediate = (i);				\
+		core_immediate_update();				\
+		module_immediate_update();				\
+	} while (0)
+
+
+/**
+ * _immediate_set - set immediate variable (without locking)
+ * @name: immediate value name
+ * @i: required value
+ *
+ * Sets the value of @name. Must be called with module_mutex held.
+ */
+#define _immediate_set(name, i)						\
+	do {								\
+		name##__immediate = (i);				\
+		core_immediate_update();				\
+		_module_immediate_update();				\
+	} while (0)
+
+/**
+ * immediate_set_early - set immediate variable at early boot
+ * @name: immediate value name
+ * @i: required value
+ *
+ * Sets the value of @name. Should be used for updates at early boot, when only
+ * one CPU is active and interrupts are disabled.
+ */
+#define immediate_set_early(name, i)					\
+	do {								\
+		name##__immediate = (i);				\
+		immediate_update_early();				\
+	} while (0)
+
+/*
+ * Internal update functions.
+ */
+extern void core_immediate_update(void);
+extern void immediate_update_range(const struct __immediate *begin,
+	const struct __immediate *end);
+extern void immediate_update_early(void);
+
+#else
+
+/*
+ * Generic immediate values: a simple, standard, memory load.
+ */
+
+/**
+ * immediate_read - read immediate variable
+ * @name: immediate value name
+ *
+ * Reads the value of @name.
+ */
+#define immediate_read(name)		_immediate_read(name)
+
+/**
+ * immediate_set - set immediate variable (with locking)
+ * @name: immediate value name
+ * @i: required value
+ *
+ * Sets the value of @name, taking the module_mutex if required by
+ * the architecture.
+ */
+#define immediate_set(name, i)		(name##__immediate = (i))
+
+/**
+ * _immediate_set - set immediate variable (without locking)
+ * @name: immediate value name
+ * @i: required value
+ *
+ * Sets the value of @name. Must be called with module_mutex held.
+ */
+#define _immediate_set(name, i)		immediate_set(name, i)
+
+/**
+ * immediate_set_early - set immediate variable at early boot
+ * @name: immediate value name
+ * @i: required value
+ *
+ * Sets the value of @name. Should be used for early boot updates.
+ */
+#define immediate_set_early(name, i)	immediate_set(name, i)
+
+/*
+ * Internal update functions.
+ */
+static inline void immediate_update_early(void)
+{ }
+#endif
+
+#define DECLARE_IMMEDIATE(type, name) extern __typeof__(type) name##__immediate
+#define DEFINE_IMMEDIATE(type, name)  __typeof__(type) name##__immediate
+
+#define EXPORT_IMMEDIATE_SYMBOL(name) EXPORT_SYMBOL(name##__immediate)
+#define EXPORT_IMMEDIATE_SYMBOL_GPL(name) EXPORT_SYMBOL_GPL(name##__immediate)
+
+/**
+ * _immediate_read - Read immediate value with standard memory load.
+ * @name: immediate value name
+ *
+ * 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(name)		(name##__immediate)
+
+#endif
Index: linux-2.6-lttng/include/asm-generic/vmlinux.lds.h
===================================================================
--- linux-2.6-lttng.orig/include/asm-generic/vmlinux.lds.h	2007-09-17 13:25:06.000000000 -0400
+++ linux-2.6-lttng/include/asm-generic/vmlinux.lds.h	2007-09-17 13:35:50.000000000 -0400
@@ -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)					\
Index: linux-2.6-lttng/include/linux/module.h
===================================================================
--- linux-2.6-lttng.orig/include/linux/module.h	2007-09-17 13:25:06.000000000 -0400
+++ linux-2.6-lttng/include/linux/module.h	2007-09-17 13:35:50.000000000 -0400
@@ -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>
@@ -370,6 +371,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 {}
@@ -473,6 +479,9 @@ int unregister_module_notifier(struct no
 
 extern void print_modules(void);
 
+extern void _module_immediate_update(void);
+extern void module_immediate_update(void);
+
 #else /* !CONFIG_MODULES... */
 #define EXPORT_SYMBOL(sym)
 #define EXPORT_SYMBOL_GPL(sym)
@@ -572,6 +581,14 @@ static inline void print_modules(void)
 {
 }
 
+static inline void _module_immediate_update(void)
+{
+}
+
+static inline void module_immediate_update(void)
+{
+}
+
 #endif /* CONFIG_MODULES */
 
 struct device_driver;
Index: linux-2.6-lttng/kernel/module.c
===================================================================
--- linux-2.6-lttng.orig/kernel/module.c	2007-09-17 13:25:06.000000000 -0400
+++ linux-2.6-lttng/kernel/module.c	2007-09-17 13:35:51.000000000 -0400
@@ -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>
@@ -1717,6 +1718,7 @@ static struct module *load_module(void _
 	unsigned int unusedcrcindex;
 	unsigned int unusedgplindex;
 	unsigned int unusedgplcrcindex;
+	unsigned int immediateindex;
 	struct module *mod;
 	long err = 0;
 	void *percpu = NULL, *ptr = NULL; /* Stops spurious gcc warning */
@@ -1813,6 +1815,7 @@ static struct module *load_module(void _
 #ifdef ARCH_UNWIND_SECTION_NAME
 	unwindex = find_sec(hdr, sechdrs, secstrings, ARCH_UNWIND_SECTION_NAME);
 #endif
+	immediateindex = find_sec(hdr, sechdrs, secstrings, "__immediate");
 
 	/* Don't keep modinfo section */
 	sechdrs[infoindex].sh_flags &= ~(unsigned long)SHF_ALLOC;
@@ -1963,6 +1966,11 @@ 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
+	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)
@@ -2028,6 +2036,12 @@ static struct module *load_module(void _
 		 goto nomodsectinfo;
 #endif
 
+#ifdef CONFIG_IMMEDIATE
+	if (!mod->taints)
+		immediate_update_range(mod->immediate,
+			mod->immediate + mod->num_immediate);
+#endif
+
 	err = module_finalize(hdr, sechdrs, mod);
 	if (err < 0)
 		goto cleanup;
@@ -2629,3 +2643,38 @@ EXPORT_SYMBOL(module_remove_driver);
 void struct_module(struct module *mod) { return; }
 EXPORT_SYMBOL(struct_module);
 #endif
+
+#ifdef CONFIG_IMMEDIATE
+/**
+ * _module_immediate_update - update all immediate values in the kernel
+ *
+ * Iterate on the kernel core and modules to update the immediate values.
+ * Module_mutex must be held be the caller.
+ */
+void _module_immediate_update(void)
+{
+	struct module *mod;
+
+	list_for_each_entry(mod, &modules, list) {
+		if (mod->taints)
+			continue;
+		immediate_update_range(mod->immediate,
+			mod->immediate + mod->num_immediate);
+	}
+}
+EXPORT_SYMBOL_GPL(_module_immediate_update);
+
+/**
+ * module_immediate_update - update all immediate values in the kernel
+ *
+ * Iterate on the kernel core and modules to update the immediate values.
+ * Takes module_mutex.
+ */
+void module_immediate_update(void)
+{
+	mutex_lock(&module_mutex);
+	_module_immediate_update();
+	mutex_unlock(&module_mutex);
+}
+EXPORT_SYMBOL_GPL(module_immediate_update);
+#endif
Index: linux-2.6-lttng/kernel/immediate.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6-lttng/kernel/immediate.c	2007-09-17 13:25:22.000000000 -0400
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2007 Mathieu Desnoyers
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+#include <linux/module.h>
+#include <linux/mutex.h>
+#include <linux/immediate.h>
+#include <linux/memory.h>
+
+extern const struct __immediate __start___immediate[];
+extern const struct __immediate __stop___immediate[];
+
+/*
+ * immediate_mutex nests inside module_mutex. immediate_mutex protects builtin
+ * immediates and module immediates.
+ */
+static DEFINE_MUTEX(immediate_mutex);
+
+/**
+ * immediate_update_range - Update immediate values in a range
+ * @begin: pointer to the beginning of the range
+ * @end: pointer to the end of the range
+ *
+ * Sets a range of immediates to a enabled state : set the enable bit.
+ */
+void immediate_update_range(const struct __immediate *begin,
+		const struct __immediate *end)
+{
+	const struct __immediate *iter;
+	int ret;
+
+	for (iter = begin; iter < end; iter++) {
+		mutex_lock(&immediate_mutex);
+		kernel_text_lock();
+		ret = arch_immediate_update(iter);
+		kernel_text_unlock();
+		if (ret)
+			printk(KERN_WARNING "Invalid immediate value. "
+					    "Variable at %p, "
+					    "instruction at %p, size %lu\n",
+					    (void*)iter->immediate,
+					    (void*)iter->var, iter->size);
+		mutex_unlock(&immediate_mutex);
+	}
+}
+EXPORT_SYMBOL_GPL(immediate_update_range);
+
+/**
+ * immediate_update - update all immediate values in the kernel
+ * @lock: should a module_mutex be taken ?
+ *
+ * Iterate on the kernel core and modules to update the immediate values.
+ */
+void core_immediate_update(void)
+{
+	/* Core kernel immediates */
+	immediate_update_range(__start___immediate, __stop___immediate);
+}
+EXPORT_SYMBOL_GPL(core_immediate_update);
+
+static void __init immediate_update_early_range(const struct __immediate *begin,
+		const struct __immediate *end)
+{
+	const struct __immediate *iter;
+
+	for (iter = begin; iter < end; iter++)
+		arch_immediate_update_early(iter);
+}
+
+/**
+ * immediate_update_early - Update immediate values at boot time
+ *
+ * Update the immediate values to the state of the variables they refer to. It
+ * is done before SMP is active, at the very beginning of start_kernel().
+ */
+void __init immediate_update_early(void)
+{
+	immediate_update_early_range(__start___immediate, __stop___immediate);
+}
Index: linux-2.6-lttng/init/main.c
===================================================================
--- linux-2.6-lttng.orig/init/main.c	2007-09-17 13:25:06.000000000 -0400
+++ linux-2.6-lttng/init/main.c	2007-09-17 13:25:22.000000000 -0400
@@ -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>
@@ -525,6 +526,7 @@ asmlinkage void __init start_kernel(void
 	unwind_init();
 	lockdep_init();
 	container_init_early();
+	immediate_update_early();
 
 	local_irq_disable();
 	early_boot_irqs_off();
Index: linux-2.6-lttng/kernel/Makefile
===================================================================
--- linux-2.6-lttng.orig/kernel/Makefile	2007-09-17 13:25:06.000000000 -0400
+++ linux-2.6-lttng/kernel/Makefile	2007-09-17 13:35:50.000000000 -0400
@@ -61,6 +61,7 @@ obj-$(CONFIG_SYSCTL) += utsname_sysctl.o
 obj-$(CONFIG_TASK_DELAY_ACCT) += delayacct.o
 obj-$(CONFIG_TASKSTATS) += taskstats.o tsacct.o
 obj-$(CONFIG_RESOURCE_COUNTERS) += res_counter.o
+obj-$(CONFIG_IMMEDIATE) += immediate.o
 
 ifneq ($(CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <alan@linuxcare.com.au>, the -fno-omit-frame-pointer is

-- 
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/7] Immediate Values - Kconfig menu in EMBEDDED

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-kconfig-embedded.patch --]
[-- Type: text/plain, Size: 2652 bytes --]

Immediate 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.

Note: Since I think that I really should let embedded systems developers using
RO memory the option to disable the immediate values, I choose to leave this
menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes
sense because we want to compile out all the immediate code when we decide not
to use optimized immediate values at all (it removes otherwise unused code).

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
CC: Adrian Bunk <bunk@stusta.de>
CC: Andi Kleen <andi@firstfloor.org>
CC: Alexey Dobriyan <adobriyan@gmail.com>
CC: Christoph Hellwig <hch@infradead.org>
---
 init/Kconfig |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

Index: linux-2.6-lttng/init/Kconfig
===================================================================
--- linux-2.6-lttng.orig/init/Kconfig	2007-09-18 10:09:40.000000000 -0400
+++ linux-2.6-lttng/init/Kconfig	2007-09-18 13:14:58.000000000 -0400
@@ -407,6 +407,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. They can be
+	  disabled through the EMBEDDED menu.
+
 menuconfig EMBEDDED
 	bool "Configure standard kernel features (for small systems)"
 	help
@@ -646,6 +657,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

-- 
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/7] Immediate Values - Kconfig menu in EMBEDDED

[Randy Dunlap]

On Tue, 18 Sep 2007 17:07:49 -0400 Mathieu Desnoyers wrote:

> Immediate 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.
> 
> Note: Since I think that I really should let embedded systems developers using
> RO memory the option to disable the immediate values, I choose to leave this
> menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes
> sense because we want to compile out all the immediate code when we decide not
> to use optimized immediate values at all (it removes otherwise unused code).
> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
> CC: Adrian Bunk <bunk@stusta.de>
> CC: Andi Kleen <andi@firstfloor.org>
> CC: Alexey Dobriyan <adobriyan@gmail.com>
> CC: Christoph Hellwig <hch@infradead.org>
> ---
>  init/Kconfig |   21 +++++++++++++++++++++
>  1 file changed, 21 insertions(+)
> 
> Index: linux-2.6-lttng/init/Kconfig
> ===================================================================
> --- linux-2.6-lttng.orig/init/Kconfig	2007-09-18 10:09:40.000000000 -0400
> +++ linux-2.6-lttng/init/Kconfig	2007-09-18 13:14:58.000000000 -0400
> @@ -407,6 +407,17 @@ config CC_OPTIMIZE_FOR_SIZE
>  config SYSCTL
>  	bool
>  
> +config IMMEDIATE
> +	default y if !DISABLE_IMMEDIATE

So DISABLE_IMMEDIATE is just an intermediate symbol to make this option
be displayed in the EMBEDDED menu instead of in the General Setup menu ?


> +	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. They can be
> +	  disabled through the EMBEDDED menu.
> +
>  menuconfig EMBEDDED
>  	bool "Configure standard kernel features (for small systems)"
>  	help
> @@ -646,6 +657,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

---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***

Re: [patch 2/7] Immediate Values - Kconfig menu in EMBEDDED

[Mathieu Desnoyers]

* Randy Dunlap (randy.dunlap@oracle.com) wrote:
> On Tue, 18 Sep 2007 17:07:49 -0400 Mathieu Desnoyers wrote:
> 
> > Immediate 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.
> > 
> > Note: Since I think that I really should let embedded systems developers using
> > RO memory the option to disable the immediate values, I choose to leave this
> > menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes
> > sense because we want to compile out all the immediate code when we decide not
> > to use optimized immediate values at all (it removes otherwise unused code).
> > 
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
> > CC: Adrian Bunk <bunk@stusta.de>
> > CC: Andi Kleen <andi@firstfloor.org>
> > CC: Alexey Dobriyan <adobriyan@gmail.com>
> > CC: Christoph Hellwig <hch@infradead.org>
> > ---
> >  init/Kconfig |   21 +++++++++++++++++++++
> >  1 file changed, 21 insertions(+)
> > 
> > Index: linux-2.6-lttng/init/Kconfig
> > ===================================================================
> > --- linux-2.6-lttng.orig/init/Kconfig	2007-09-18 10:09:40.000000000 -0400
> > +++ linux-2.6-lttng/init/Kconfig	2007-09-18 13:14:58.000000000 -0400
> > @@ -407,6 +407,17 @@ config CC_OPTIMIZE_FOR_SIZE
> >  config SYSCTL
> >  	bool
> >  
> > +config IMMEDIATE
> > +	default y if !DISABLE_IMMEDIATE
> 
> So DISABLE_IMMEDIATE is just an intermediate symbol to make this option
> be displayed in the EMBEDDED menu instead of in the General Setup menu ?
> 

I simply prefer to use a positive logic (CONFIG_IMMEDIATE) rather than
the opposite. It makes makefiles and ifdefs much cleaner. Actually, the
IMMEDIATE config option is not shown in any menu at all; it is totally
controlled by DISABLE_IMMEDIATE. And yes, DISABLE_IMMEDIATE appears in
the embedded menu.

> 
> > +	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. They can be
> > +	  disabled through the EMBEDDED menu.
> > +
> >  menuconfig EMBEDDED
> >  	bool "Configure standard kernel features (for small systems)"
> >  	help
> > @@ -646,6 +657,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
> 
> ---
> ~Randy
> *** Remember to use Documentation/SubmitChecklist when testing your code ***

-- 
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/7] Immediate Values - Move Kprobes i386 restore_interrupt to kdebug.h

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-move-kprobes-i386-restore-interrupt-to-kdebug-h.patch --]
[-- Type: text/plain, Size: 2329 bytes --]

Since 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.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
Acked-by: Ananth N Mavinakayanahalli <ananth@in.ibm.com>
CC: Christoph Hellwig <hch@infradead.org>
CC: prasanna@in.ibm.com
CC: anil.s.keshavamurthy@intel.com
CC: davem@davemloft.net
---
 include/asm-i386/kdebug.h  |   12 ++++++++++++
 include/asm-i386/kprobes.h |    9 ---------
 2 files changed, 12 insertions(+), 9 deletions(-)

Index: linux-2.6-lttng/include/asm-i386/kdebug.h
===================================================================
--- linux-2.6-lttng.orig/include/asm-i386/kdebug.h	2007-09-04 11:52:37.000000000 -0400
+++ linux-2.6-lttng/include/asm-i386/kdebug.h	2007-09-04 12:12:06.000000000 -0400
@@ -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
Index: linux-2.6-lttng/include/asm-i386/kprobes.h
===================================================================
--- linux-2.6-lttng.orig/include/asm-i386/kprobes.h	2007-09-04 11:53:26.000000000 -0400
+++ linux-2.6-lttng/include/asm-i386/kprobes.h	2007-09-04 12:12:06.000000000 -0400
@@ -79,15 +79,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);

-- 
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/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-i386-optimization.patch --]
[-- Type: text/plain, Size: 16431 bytes --]

i386 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.

Changelog:
- Use text_poke_early with cr0 WP save/restore to patch the bypass. We are doing
  non atomic writes to a code region only touched by us (nobody can execute it
  since we are protected by the immediate_mutex).
- Put immediate_set and _immediate_set in the architecture independent header.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
CC: Andi Kleen <ak@muc.de>
CC: "H. Peter Anvin" <hpa@zytor.com>
CC: Chuck Ebbert <cebbert@redhat.com>
CC: Christoph Hellwig <hch@infradead.org>
---
 arch/i386/kernel/Makefile    |    1 
 arch/i386/kernel/immediate.c |  307 +++++++++++++++++++++++++++++++++++++++++++
 arch/i386/kernel/traps.c     |    8 -
 include/asm-i386/immediate.h |   82 +++++++++++
 4 files changed, 394 insertions(+), 4 deletions(-)

Index: linux-2.6-lttng/include/asm-i386/immediate.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6-lttng/include/asm-i386/immediate.h	2007-09-18 13:15:02.000000000 -0400
@@ -0,0 +1,82 @@
+#ifndef _ASM_I386_IMMEDIATE_H
+#define _ASM_I386_IMMEDIATE_H
+
+/*
+ * Immediate values. i386 architecture optimizations.
+ *
+ * (C) Copyright 2006 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
+ *
+ * This file is released under the GPLv2.
+ * See the file COPYING for more details.
+ */
+
+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
+ * @name: immediate value name
+ *
+ * Reads the value of @name.
+ * 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(name)						\
+	({								\
+		__typeof__(name##__immediate) 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" (name##__immediate),		\
+				  "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" (name##__immediate),		\
+				  "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" (name##__immediate),		\
+				  "i" (0));				\
+			break;						\
+		default:value = name##__immediate;			\
+			break;						\
+		};							\
+		value;							\
+	})
+
+extern int arch_immediate_update(const struct __immediate *immediate);
+extern void arch_immediate_update_early(const struct __immediate *immediate);
+
+#endif /* _ASM_I386_IMMEDIATE_H */
Index: linux-2.6-lttng/arch/i386/kernel/Makefile
===================================================================
--- linux-2.6-lttng.orig/arch/i386/kernel/Makefile	2007-09-18 10:08:33.000000000 -0400
+++ linux-2.6-lttng/arch/i386/kernel/Makefile	2007-09-18 13:15:02.000000000 -0400
@@ -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
Index: linux-2.6-lttng/arch/i386/kernel/immediate.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6-lttng/arch/i386/kernel/immediate.c	2007-09-18 13:15:02.000000000 -0400
@@ -0,0 +1,307 @@
+/*
+ * Immediate Value - i386 architecture specific code.
+ *
+ * Rationale
+ *
+ * Required because of :
+ * - 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 immediate value modification 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."
+ *
+ * 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.
+ *
+ * Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
+ */
+
+#include <linux/notifier.h>
+#include <linux/preempt.h>
+#include <linux/smp.h>
+#include <linux/notifier.h>
+#include <linux/module.h>
+#include <linux/immediate.h>
+#include <linux/kdebug.h>
+#include <linux/rcupdate.h>
+#include <linux/kprobes.h>
+
+#include <asm/cacheflush.h>
+
+#define BREAKPOINT_INSTRUCTION  0xcc
+#define BREAKPOINT_INS_LEN	1
+#define NR_NOPS			8
+
+static long target_after_int3;		/* EIP of the target after the int3 */
+static long bypass_eip;			/* EIP of the bypass. */
+static long bypass_after_int3;		/* EIP after the end-of-bypass int3 */
+static long after_immediate;		/*
+					 * EIP where to resume after the
+					 * single-stepping.
+					 */
+
+/*
+ * Size of the movl instruction (without the immediate value) in bytes.
+ * The 2 bytes load immediate has a 66H prefix, which makes the opcode 2 bytes
+ * wide.
+ */
+static inline size_t _immediate_get_insn_size(long size)
+{
+	switch (size) {
+		case 1: return 1;
+		case 2: return 2;
+		case 4: return 1;
+		default: BUG();
+	};
+}
+
+/*
+ * Internal bypass used during value update. The bypass is skipped by the
+ * function in which it is inserted.
+ * No need to be aligned because we exclude readers from the site during
+ * update.
+ * Layout is:
+ * nop nop nop nop nop nop nop nop int3
+ * The nops are the target replaced by the instruction to single-step.
+ */
+static inline void _immediate_bypass(long *bypassaddr, long *breaknextaddr)
+{
+		asm volatile (	"jmp 2f;\n\t"
+				"0:\n\t"
+				".space 8, 0x90;\n\t"
+				"1:\n\t"
+				"int3;\n\t"
+				"2:\n\t"
+				"movl $(0b),%0;\n\t"
+				"movl $((1b)+1),%1;\n\t"
+				: "=r" (*bypassaddr),
+				  "=r" (*breaknextaddr) : );
+}
+
+static void immediate_synchronize_core(void *info)
+{
+	sync_core();	/* use cpuid to stop speculative execution */
+}
+
+/*
+ * The eip value points right after the breakpoint instruction, in the second
+ * byte of the movl.
+ * Disable preemption in the bypass to make sure no thread will be preempted in
+ * it. We can then use synchronize_sched() to make sure every bypass users have
+ * ended.
+ */
+static int immediate_notifier(struct notifier_block *nb,
+	unsigned long val, void *data)
+{
+	enum die_val die_val = (enum die_val) val;
+	struct die_args *args = data;
+
+	if (!args->regs || user_mode_vm(args->regs))
+		return NOTIFY_DONE;
+
+	if (die_val == DIE_INT3) {
+		if (args->regs->eip == target_after_int3) {
+			preempt_disable();
+			args->regs->eip = bypass_eip;
+			return NOTIFY_STOP;
+		} else if (args->regs->eip == bypass_after_int3) {
+			args->regs->eip = after_immediate;
+			preempt_enable();
+			return NOTIFY_STOP;
+		}
+	}
+	return NOTIFY_DONE;
+}
+
+static struct notifier_block immediate_notify = {
+	.notifier_call = immediate_notifier,
+	.priority = 0x7fffffff,	/* we need to be notified first */
+};
+
+
+/**
+ * arch_immediate_update - update one immediate value
+ * @immediate: pointer of type const struct __immediate to update
+ *
+ * Update one immediate value. Must be called with immediate_mutex held.
+ */
+__kprobes int arch_immediate_update(const struct __immediate *immediate)
+{
+	int ret;
+	size_t insn_size = _immediate_get_insn_size(immediate->size);
+	long insn = immediate->immediate - insn_size;
+	long len;
+	unsigned long cr0;
+
+#ifdef CONFIG_KPROBES
+	/*
+	 * Fail if a kprobe has been set on this instruction.
+	 * (TODO: we could eventually do better and modify all the (possibly
+	 * nested) kprobes for this site if kprobes had an API for this.
+	 */
+	if (unlikely(*(unsigned char*)insn == BREAKPOINT_INSTRUCTION)) {
+		printk(KERN_WARNING "Immediate value in conflict with kprobe. "
+				    "Variable at %p, "
+				    "instruction at %p, size %lu\n",
+				    (void*)immediate->immediate,
+				    (void*)immediate->var, immediate->size);
+		return -EBUSY;
+	}
+#endif
+
+	/*
+	 * If the variable and the instruction have the same value, there is
+	 * nothing to do.
+	 */
+	switch (immediate->size) {
+		case 1:	if (*(uint8_t*)immediate->immediate
+					== *(uint8_t*)immediate->var)
+				return 0;
+			break;
+		case 2:	if (*(uint16_t*)immediate->immediate
+					== *(uint16_t*)immediate->var)
+				return 0;
+			break;
+		case 4:	if (*(uint32_t*)immediate->immediate
+					== *(uint32_t*)immediate->var)
+				return 0;
+			break;
+		default:return -EINVAL;
+	}
+
+	_immediate_bypass(&bypass_eip, &bypass_after_int3);
+
+	after_immediate = immediate->immediate + immediate->size;
+
+	/*
+	 * Using the _early variants because nobody is executing the
+	 * bypass code while we patch it. It is protected by the
+	 * immediate_mutex. Since we modify the instructions non atomically (for
+	 * nops), we have to use the _early variant.
+	 * We must however deal with the WP flag in cr0 by ourself.
+	 */
+	kernel_wp_save(cr0);
+	text_poke_early((void*)bypass_eip, (void*)insn,
+			insn_size + immediate->size);
+	/*
+	 * Fill the rest with nops.
+	 */
+	len = NR_NOPS - immediate->size - insn_size;
+	add_nops((void*)(bypass_eip + insn_size + immediate->size), len);
+	kernel_wp_restore(cr0);
+
+	target_after_int3 = insn + BREAKPOINT_INS_LEN;
+	/* register_die_notifier has memory barriers */
+	register_die_notifier(&immediate_notify);
+	/* The breakpoint will single-step the bypass */
+	text_poke((void*)insn,
+		INIT_ARRAY(unsigned char, BREAKPOINT_INSTRUCTION, 1), 1);
+	wmb();
+	/*
+	 * Execute serializing instruction on each CPU.
+	 * Acts as a memory barrier.
+	 */
+	ret = on_each_cpu(immediate_synchronize_core, NULL, 1, 1);
+	BUG_ON(ret != 0);
+
+	text_poke((void*)(insn + insn_size), (void*)immediate->var,
+			immediate->size);
+	wmb();
+	text_poke((void*)insn, (unsigned char*)bypass_eip, 1);
+		/*
+		 * 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.
+		 * synchronize_sched has memory barriers.
+		 */
+	synchronize_sched();
+	unregister_die_notifier(&immediate_notify);
+	/* unregister_die_notifier has memory barriers */
+	return 0;
+}
+
+/**
+ * arch_immediate_update_early - update one immediate value at boot time
+ * @immediate: pointer of type const struct __immediate to update
+ *
+ * Update one immediate value at boot time.
+ */
+void __init arch_immediate_update_early(const struct __immediate *immediate)
+{
+	/*
+	 * If the variable and the instruction have the same value, there is
+	 * nothing to do.
+	 */
+	switch (immediate->size) {
+		case 1:	if (*(uint8_t*)immediate->immediate
+					== *(uint8_t*)immediate->var)
+				return;
+			break;
+		case 2:	if (*(uint16_t*)immediate->immediate
+					== *(uint16_t*)immediate->var)
+				return;
+			break;
+		case 4:	if (*(uint32_t*)immediate->immediate
+					== *(uint32_t*)immediate->var)
+				return;
+			break;
+		default:return;
+	}
+	memcpy((void*)immediate->immediate, (void*)immediate->var,
+			immediate->size);
+}
Index: linux-2.6-lttng/arch/i386/kernel/traps.c
===================================================================
--- linux-2.6-lttng.orig/arch/i386/kernel/traps.c	2007-09-18 10:09:57.000000000 -0400
+++ linux-2.6-lttng/arch/i386/kernel/traps.c	2007-09-18 13:15:02.000000000 -0400
@@ -637,7 +637,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)
@@ -879,14 +879,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);
 }

-- 
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 4/7] Immediate Values - i386 Optimization

[Jeremy Fitzhardinge]

Mathieu Desnoyers wrote:

> +#define immediate_read(name)						\
> +	({								\
> +		__typeof__(name##__immediate) 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"		\

Given that you're relying on the exact instruction that this mov
generates, it might be better to explicitly put the opcodes in with
.byte.  That way you're protected from the assembler deciding to
generate some other form of the instruction (for whatever reason).  I
guess substituting in different registers would be a pain.

Aside from that,  is there any reason not to just put $0 in there rather
than use %2?


> +					".long %1, (0f)+1, 4;\n\t"	\
> +					".previous;\n\t"		\
> +					"1:\n\t"			\
> +					".org (1b)+(3-((1b)%%4)), 0x90;\n\t" \
>   
Seems a little complex, but I couldn't come up with anything much better:

	.org . + 3 - (. & 3), 0x90

You can use . rather than needing to define 1:, it doesn't need quite so
many parens, and using &3 avoids the %% wart. 

It's a pity that gas seems to generate plain 0x90 nops rather than
long-nop forms here.  I thought it could do that.

    J

Re: [patch 4/7] Immediate Values - i386 Optimization

[H. Peter Anvin]

Jeremy Fitzhardinge wrote:
> Mathieu Desnoyers wrote:
> 
>> +#define immediate_read(name)						\
>> +	({								\
>> +		__typeof__(name##__immediate) 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"		\
> 
> Given that you're relying on the exact instruction that this mov
> generates, it might be better to explicitly put the opcodes in with
> .byte.  That way you're protected from the assembler deciding to
> generate some other form of the instruction (for whatever reason).  I
> guess substituting in different registers would be a pain.

Allowing different registers should be doable, but if so, one would have
to put 0: at the *end* of the instruction and use (0f)-4 instead, since
the non-%eax forms are one byte longer.

This also seems "safer", since an imm32 is always the last thing in the
instruction.

	-hpa

Re: [patch 4/7] Immediate Values - i386 Optimization

[Jeremy Fitzhardinge]

H. Peter Anvin wrote:
> Allowing different registers should be doable, but if so, one would have
> to put 0: at the *end* of the instruction and use (0f)-4 instead, since
> the non-%eax forms are one byte longer.
>   

OK, that's already a problem since its using "=r" as the constraint.

> This also seems "safer", since an imm32 is always the last thing in the
> instruction.

Good idea.  If gas/gcc generates entirely the wrong addressing mode,
then we've got bigger problems.

    J

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* Jeremy Fitzhardinge (jeremy@goop.org) wrote:
> H. Peter Anvin wrote:
> > Allowing different registers should be doable, but if so, one would have
> > to put 0: at the *end* of the instruction and use (0f)-4 instead, since
> > the non-%eax forms are one byte longer.
> >   
> 
> OK, that's already a problem since its using "=r" as the constraint.
> 
> > This also seems "safer", since an imm32 is always the last thing in the
> > instruction.
> 
> Good idea.  If gas/gcc generates entirely the wrong addressing mode,
> then we've got bigger problems.
> 

Ok, let's have a good look at what we want:

1 - get a pointer to the beginning of the immediate value within the
    instruction.
2 - make sure that the immediate value, within the instruction, is
    written to atomically wrt all CPUs, even on older architectures
    where non aligned writes are not atomic.

Effectively, placing a label at the end of the instruction, and then
offsetting backward from there, will give us (1).

Then, for the alignment, we have to give a good look at the instruction
set reference, mov instruction, to see what the variants of mov
immediate value to register are on i386.

First, let's look at the possible prefixes:
- Lock and repeat prefixes : no
- Segment override prefixes: no memory reference there, so doesn't
  apply.
- Branch hints : no, it's a mov instruction
- Operand-size override prefix: *yes*, can be used for 2 bytes mov
- Address-size override prefix: no address in there, only immediate
  value and register.

(looking at the Compat/Leg Mode)

3 cases:

* 1 byte
B0 + rb         MOV r8, imm8     (1 byte opcode)
REX + B0 + rb   MOV r8, imm8     (only on 64 bits archs, never generated)
C6 /0           MOV r/m8, imm8   (2 bytes opcode)
(this one doesn't require alignment at all, since we do a 1 byte write)

* 2 bytes
B8 + rw         MOV r16, imm16   (1 byte opcode)
66 B8 + rd      MOV r16, imm16   (2 bytes opcode) (with 66H prefix)
C7 /0           MOV r/m16, imm16 (2 bytes opcode)
(Alignment on 4 bytes boundaries would be required because of the
possible 1 byte opcode ? Or is the 66H prefix mandatory there ? If it
is, then we can safely align on 2 bytes boundaries.)

* 4 bytes
B8 + rd         MOV r32, imm32   (1 byte opcode)
C7 /0           MOV r/m32, imm32 (2 bytes opcode)
(the 2 bytes opcode can be a problem)

I have missed anything ?

Mathieu

-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* Mathieu Desnoyers (mathieu.desnoyers@polymtl.ca) wrote:
> * Jeremy Fitzhardinge (jeremy@goop.org) wrote:
> > H. Peter Anvin wrote:
> > > Allowing different registers should be doable, but if so, one would have
> > > to put 0: at the *end* of the instruction and use (0f)-4 instead, since
> > > the non-%eax forms are one byte longer.
> > >   
> > 
> > OK, that's already a problem since its using "=r" as the constraint.
> > 
> > > This also seems "safer", since an imm32 is always the last thing in the
> > > instruction.
> > 
> > Good idea.  If gas/gcc generates entirely the wrong addressing mode,
> > then we've got bigger problems.
> > 
> 
> Ok, let's have a good look at what we want:
> 
> 1 - get a pointer to the beginning of the immediate value within the
>     instruction.
> 2 - make sure that the immediate value, within the instruction, is
>     written to atomically wrt all CPUs, even on older architectures
>     where non aligned writes are not atomic.
> 
> Effectively, placing a label at the end of the instruction, and then
> offsetting backward from there, will give us (1).
> 
> Then, for the alignment, we have to give a good look at the instruction
> set reference, mov instruction, to see what the variants of mov
> immediate value to register are on i386.
> 
> First, let's look at the possible prefixes:
> - Lock and repeat prefixes : no
> - Segment override prefixes: no memory reference there, so doesn't
>   apply.
> - Branch hints : no, it's a mov instruction
> - Operand-size override prefix: *yes*, can be used for 2 bytes mov
> - Address-size override prefix: no address in there, only immediate
>   value and register.
> 
> (looking at the Compat/Leg Mode)
> 
> 3 cases:
> 
> * 1 byte
> B0 + rb         MOV r8, imm8     (1 byte opcode)
> REX + B0 + rb   MOV r8, imm8     (only on 64 bits archs, never generated)
> C6 /0           MOV r/m8, imm8   (2 bytes opcode)
> (this one doesn't require alignment at all, since we do a 1 byte write)
> 
> * 2 bytes
> B8 + rw         MOV r16, imm16   (1 byte opcode)
> 66 B8 + rd      MOV r16, imm16   (2 bytes opcode) (with 66H prefix)
> C7 /0           MOV r/m16, imm16 (2 bytes opcode)
> (Alignment on 4 bytes boundaries would be required because of the
> possible 1 byte opcode ? Or is the 66H prefix mandatory there ? If it
> is, then we can safely align on 2 bytes boundaries.)
> 
> * 4 bytes
> B8 + rd         MOV r32, imm32   (1 byte opcode)
> C7 /0           MOV r/m32, imm32 (2 bytes opcode)
> (the 2 bytes opcode can be a problem)
> 
> I have missed anything ?
> 

This is not a problem in practice because we place a breakpoint and use
a bypass when we are updating immediate values that can be used
concurrently. So let's not bother about that too much. It just means
that the breakpoint approach might have to be used for more
architectures in the future to address that kind of issue.

Mathieu


-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Re: [patch 4/7] Immediate Values - i386 Optimization

[H. Peter Anvin]

Mathieu Desnoyers wrote:
> 
> Ok, let's have a good look at what we want:
> 
> 1 - get a pointer to the beginning of the immediate value within the
>     instruction.
> 2 - make sure that the immediate value, within the instruction, is
>     written to atomically wrt all CPUs, even on older architectures
>     where non aligned writes are not atomic.
> 

I think you'll find that even on modern architectures cross-cacheline
writes aren't atomic.

Anyway, disregard the bit I mentioned about one byte longer; I've been
staring myself too blind at instruction variants lately (lots of
arguments about how to generate various instructions using NASM syntax).

> 
> * 4 bytes
> B8 + rd         MOV r32, imm32   (1 byte opcode)
> C7 /0           MOV r/m32, imm32 (2 bytes opcode)
> (the 2 bytes opcode can be a problem)
> 

If gas generates the C7 opcodes by default, then that's a bug, nothing less.

	-hpa

Re: [patch 4/7] Immediate Values - i386 Optimization

[Jeremy Fitzhardinge]

H. Peter Anvin wrote:
> Mathieu Desnoyers wrote:
>   
>> Ok, let's have a good look at what we want:
>>
>> 1 - get a pointer to the beginning of the immediate value within the
>>     instruction.
>> 2 - make sure that the immediate value, within the instruction, is
>>     written to atomically wrt all CPUs, even on older architectures
>>     where non aligned writes are not atomic.
>>
>>     
>
> I think you'll find that even on modern architectures cross-cacheline
> writes aren't atomic.
>   

Cross-cache-line, sure.  But what about just not sizeof aligned?  If its
enough to avoid cross-cache-line, then that's simpler.

Which is something I was going to comment on: Mathieu, you try to align
the constant itself, but you don't prevent the instruction overall from
crossing a cache line.  Given how delicate all this stuff is, it seems
like a good idea to do that.


>> * 4 bytes
>> B8 + rd         MOV r32, imm32   (1 byte opcode)
>> C7 /0           MOV r/m32, imm32 (2 bytes opcode)
>> (the 2 bytes opcode can be a problem)
>>
>>     
>
> If gas generates the C7 opcodes by default, then that's a bug, nothing less.
>   

Well, in this case, it might be preferred if it brings the constant into
alignment without explicit padding :)

    J

Re: [patch 4/7] Immediate Values - i386 Optimization

[H. Peter Anvin]

Jeremy Fitzhardinge wrote:
> 
> Cross-cache-line, sure.  But what about just not sizeof aligned?  If its
> enough to avoid cross-cache-line, then that's simpler.
> 

Not really.  It pretty much comes down to the same problem.

> Which is something I was going to comment on: Mathieu, you try to align
> the constant itself, but you don't prevent the instruction overall from
> crossing a cache line.  Given how delicate all this stuff is, it seems
> like a good idea to do that.

Given how delicate all his stuff is, it would be interesting to know the
magnitude of the expected payoff, which I personally don't remember seeing.

	-hpa

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* H. Peter Anvin (hpa@zytor.com) wrote:
> Jeremy Fitzhardinge wrote:
> > 
> > Cross-cache-line, sure.  But what about just not sizeof aligned?  If its
> > enough to avoid cross-cache-line, then that's simpler.
> > 
> 
> Not really.  It pretty much comes down to the same problem.
> 
> > Which is something I was going to comment on: Mathieu, you try to align
> > the constant itself, but you don't prevent the instruction overall from
> > crossing a cache line.  Given how delicate all this stuff is, it seems
> > like a good idea to do that.
> 
> Given how delicate all his stuff is, it would be interesting to know the
> magnitude of the expected payoff, which I personally don't remember seeing.
> 

Please have a look at the patch header at:
http://lkml.org/lkml/2007/9/18/346

And at the documentation:
http://lkml.org/lkml/2007/9/18/375

Where I provide speedups experienced with this patch. Please note that
my primary goal is to provide non intrusive instrumentation with the
Linux Kernel Markers, and the immediate values are the underlying
mechanism that help enabling/disabling dynamically instrumentation sites
with the smallest effect possible (and still get the local variables
in the middle of a function compiled with -O2...).

Mathieu

-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* Jeremy Fitzhardinge (jeremy@goop.org) wrote:
> H. Peter Anvin wrote:
> > Mathieu Desnoyers wrote:
> >   
> >> Ok, let's have a good look at what we want:
> >>
> >> 1 - get a pointer to the beginning of the immediate value within the
> >>     instruction.
> >> 2 - make sure that the immediate value, within the instruction, is
> >>     written to atomically wrt all CPUs, even on older architectures
> >>     where non aligned writes are not atomic.
> >>
> >>     
> >
> > I think you'll find that even on modern architectures cross-cacheline
> > writes aren't atomic.
> >   
> 
> Cross-cache-line, sure.  But what about just not sizeof aligned?  If its
> enough to avoid cross-cache-line, then that's simpler.
> 

Being sizeof aligned on a cache-line (e.g. 32 bytes boundaries) is a
superset of being aligned on sizeof multiples (e.g. 4 bytes). Therefore,
if we declare data of a certain size not aligned on the sizeof
boundaries, we won't be aligned on cache-lines neither. (unless I am
utterly wrong..) :)

> Which is something I was going to comment on: Mathieu, you try to align
> the constant itself, but you don't prevent the instruction overall from
> crossing a cache line.  Given how delicate all this stuff is, it seems
> like a good idea to do that.
> 

We just can't, for movl is 5 bytes in total : 1 byte for opcode, 4
bytes for the immediate value. But since we do not modify the opcode at
all, CPUs will either see the old or new immediate value (each of those
will be coherent because of the atomic update) and, in every case, they
will use it with the same opcode that haven't been touched.

> 
> >> * 4 bytes
> >> B8 + rd         MOV r32, imm32   (1 byte opcode)
> >> C7 /0           MOV r/m32, imm32 (2 bytes opcode)
> >> (the 2 bytes opcode can be a problem)
> >>
> >>     
> >
> > If gas generates the C7 opcodes by default, then that's a bug, nothing less.
> >   
> 
> Well, in this case, it might be preferred if it brings the constant into
> alignment without explicit padding :)
> 

It will need explicit padding too. We would have to align the 4 bytes
immediate value on 4 bytes multiples. Therefore, this 2 bytes opcode
followed by 4 bytes immediate value would have to be aligned on
(4 bytes - 2) boundaries.

Mathieu

-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* Jeremy Fitzhardinge (jeremy@goop.org) wrote:
> H. Peter Anvin wrote:
> > Allowing different registers should be doable, but if so, one would have
> > to put 0: at the *end* of the instruction and use (0f)-4 instead, since
> > the non-%eax forms are one byte longer.
> >   
> 
> OK, that's already a problem since its using "=r" as the constraint.
> 

Hi Jeremy,

I have tried generating asm-to-"register" c variables for char, short
and int on i386 and I do not see this happening. The char opcode is
always 1 byte, short 2 bytes and int 1 byte. Result:

gcc version 4.1.3 20070812 (prerelease) (Debian 4.1.2-15)

   8:   b3 02                   mov    $0x2,%bl
   a:   b1 03                   mov    $0x3,%cl
   c:   b2 04                   mov    $0x4,%dl
   e:   b0 05                   mov    $0x5,%al

  4f:   66 be 06 00             mov    $0x6,%si
  53:   66 bb 07 00             mov    $0x7,%bx
  57:   66 b9 08 00             mov    $0x8,%cx
  5b:   66 ba 09 00             mov    $0x9,%dx
  5f:   66 b8 0a 00             mov    $0xa,%ax

  9f:   bb 0b 00 00 00          mov    $0xb,%ebx
  a4:   be 0c 00 00 00          mov    $0xc,%esi
  a9:   b9 0d 00 00 00          mov    $0xd,%ecx
  ae:   ba 0e 00 00 00          mov    $0xe,%edx
  b3:   b8 0f 00 00 00          mov    $0xf,%eax


I notice that having a "=r" inline assembly that outputs to the first
"register char" variable seems to be problematic. It fails with the
following error:

/tmp/ccy35Hq1.s: Assembler messages:
/tmp/ccy35Hq1.s:15: Error: bad register name `%sil'

But it seems to be specific to "register" variables, which I do not use
in my immediate values.


> > This also seems "safer", since an imm32 is always the last thing in the
> > instruction.
> 
> Good idea.  If gas/gcc generates entirely the wrong addressing mode,
> then we've got bigger problems.
> 

I am still trying to figure out if we must assume that gas will produce
different length opcodes for mov instructions. The choice is:

- Either I use a "r" constraint and let gcc produce the instructions,
  that I need to assume to have correct size so I can align their
  immediate values (therefore, taking the offset from the end of the
  instruction will not help). Here, if gas changes its behavior
  dramatically for a given immediate value size, it will break.

- Second choice is to stick to a particular register, choosing the one
  with the less side-effect, and encoding the instruction ourselves. I
  start to think that this second solution might be safer, even though
  we wouldn't let the compiler select the register which has the less
  impact by itself.

Any comments about this ?

-- 
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 4/7] Immediate Values - i386 Optimization

[H. Peter Anvin]

Mathieu Desnoyers wrote:
> 
> I have tried generating asm-to-"register" c variables for char, short
> and int on i386 and I do not see this happening. The char opcode is
> always 1 byte, short 2 bytes and int 1 byte. Result:
> 

The comment was referring to x86-64, but I incorrectly remembered that 
applying to "movq $imm,%reg" as opposed to loading from an absolute 
address.  gas actually has a special opcode (movabs) for the 64-bit 
version of the latter variant, which is only available with %rax and its 
subregisters.

Nevermind, in other words.  It's still true, though, that the immediate 
will always be the last thing in the instruction -- that's a fixture of 
the instruction format.

> gcc version 4.1.3 20070812 (prerelease) (Debian 4.1.2-15)
> 
>    8:   b3 02                   mov    $0x2,%bl
>    a:   b1 03                   mov    $0x3,%cl
>    c:   b2 04                   mov    $0x4,%dl
>    e:   b0 05                   mov    $0x5,%al
> 
>   4f:   66 be 06 00             mov    $0x6,%si
>   53:   66 bb 07 00             mov    $0x7,%bx
>   57:   66 b9 08 00             mov    $0x8,%cx
>   5b:   66 ba 09 00             mov    $0x9,%dx
>   5f:   66 b8 0a 00             mov    $0xa,%ax
> 
>   9f:   bb 0b 00 00 00          mov    $0xb,%ebx
>   a4:   be 0c 00 00 00          mov    $0xc,%esi
>   a9:   b9 0d 00 00 00          mov    $0xd,%ecx
>   ae:   ba 0e 00 00 00          mov    $0xe,%edx
>   b3:   b8 0f 00 00 00          mov    $0xf,%eax
> 
> 
> I notice that having a "=r" inline assembly that outputs to the first
> "register char" variable seems to be problematic. It fails with the
> following error:
> 
> /tmp/ccy35Hq1.s: Assembler messages:
> /tmp/ccy35Hq1.s:15: Error: bad register name `%sil'

'r' is wrong for 8-bit variables on i386.  It needs to be 'q'.

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* H. Peter Anvin (hpa@zytor.com) wrote:
> Mathieu Desnoyers wrote:
> >
> >I have tried generating asm-to-"register" c variables for char, short
> >and int on i386 and I do not see this happening. The char opcode is
> >always 1 byte, short 2 bytes and int 1 byte. Result:
> >
> 
> The comment was referring to x86-64, but I incorrectly remembered that 
> applying to "movq $imm,%reg" as opposed to loading from an absolute 
> address.  gas actually has a special opcode (movabs) for the 64-bit 
> version of the latter variant, which is only available with %rax and its 
> subregisters.
> 
> Nevermind, in other words.  It's still true, though, that the immediate 
> will always be the last thing in the instruction -- that's a fixture of 
> the instruction format.
> 

Hrm, some basic testing shows me that, on x86_64:

        register long var, var2, var3, var4, var5;
        asm ("movq $0xFFFFFFFF,%0;\n\t" : "=r" (var) :);
        asm ("movq $0x100000000,%0;\n\t" : "=r" (var2) :);
        asm ("movq $0,%0;\n\t" : "=r" (var3) :);
        asm ("movq $0xFFFFFFFFFFFFFFFF,%0;\n\t" : "=r" (var4) :);
        asm ("movq $0xFEFEFEFE01010101,%0;\n\t" : "=r" (var5) :);

generates:

  ae:   48 be ff ff ff ff 00    mov    $0xffffffff,%rsi
  b5:   00 00 00 
  b8:   48 bf 00 00 00 00 01    mov    $0x100000000,%rdi
  bf:   00 00 00 
  c2:   48 c7 c1 00 00 00 00    mov    $0x0,%rcx
  c9:   48 c7 c2 ff ff ff ff    mov    $0xffffffffffffffff,%rdx
  d0:   48 b8 01 01 01 01 fe    mov    $0xfefefefe01010101,%rax
  d7:   fe fe fe 

So we have to deal with the fact that gas produces opcodes of
different size (2 and 3 bytes) and with different immediate value sizes
for 8 bytes load immediates, depending on the immediate value to load.
There even seems to be an implicit duplication of the value when the
lower and higher 32 bits of the immediate value are the same (the
0xFFFFFFFFFFFFFFFF case).

Therefore, I propose the following. We should use the

asm ("movq $0xFEFEFEFE01010101,%0;\n\t" : "=r" (var5) :);

to make sure we always deal with the same instruction and have a 8 bytes
immediate value. We don't really care about the static value given
because we always update it dynamically before the first time it is
executed.

> >gcc version 4.1.3 20070812 (prerelease) (Debian 4.1.2-15)
> >
> >   8:   b3 02                   mov    $0x2,%bl
> >   a:   b1 03                   mov    $0x3,%cl
> >   c:   b2 04                   mov    $0x4,%dl
> >   e:   b0 05                   mov    $0x5,%al
> >
> >  4f:   66 be 06 00             mov    $0x6,%si
> >  53:   66 bb 07 00             mov    $0x7,%bx
> >  57:   66 b9 08 00             mov    $0x8,%cx
> >  5b:   66 ba 09 00             mov    $0x9,%dx
> >  5f:   66 b8 0a 00             mov    $0xa,%ax
> >
> >  9f:   bb 0b 00 00 00          mov    $0xb,%ebx
> >  a4:   be 0c 00 00 00          mov    $0xc,%esi
> >  a9:   b9 0d 00 00 00          mov    $0xd,%ecx
> >  ae:   ba 0e 00 00 00          mov    $0xe,%edx
> >  b3:   b8 0f 00 00 00          mov    $0xf,%eax
> >
> >
> >I notice that having a "=r" inline assembly that outputs to the first
> >"register char" variable seems to be problematic. It fails with the
> >following error:
> >
> >/tmp/ccy35Hq1.s: Assembler messages:
> >/tmp/ccy35Hq1.s:15: Error: bad register name `%sil'
> 
> 'r' is wrong for 8-bit variables on i386.  It needs to be 'q'.
> 

Will fix. I noticed that it was because I had too much "register" char
variables declared and used at the same time. Putting a "g" constraint
gave the same result.

Mathieu

-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

Re: [patch 4/7] Immediate Values - i386 Optimization

[H. Peter Anvin]

Mathieu Desnoyers wrote:
> 
> Will fix. I noticed that it was because I had too much "register" char
> variables declared and used at the same time. Putting a "g" constraint
> gave the same result.
> 

"g" is the same as "rmi", which is probably *NOT* what you want.

Don't use "register" variables.  That's a poor workaround for using the 
proper constraints.

	-hpa

Re: [patch 4/7] Immediate Values - i386 Optimization

[Andi Kleen]

> - Either I use a "r" constraint and let gcc produce the instructions,
>   that I need to assume to have correct size so I can align their
>   immediate values (therefore, taking the offset from the end of the
>   instruction will not help). Here, if gas changes its behavior
>   dramatically for a given immediate value size, it will break.

I wouldn't expect it to do that, but you could perhaps add a self
test somewhere to check for it.

> 
> - Second choice is to stick to a particular register, choosing the one
>   with the less side-effect, and encoding the instruction ourselves. I
>   start to think that this second solution might be safer, even though
>   we wouldn't let the compiler select the register which has the less
>   impact by itself.

Such effects caused occassional bugs in the alternative() implementation
which requires a maximum size for the replacement.

But in this case it should be safe enough to trust gas stability.

-Andi

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* H. Peter Anvin (hpa@zytor.com) wrote:
> Jeremy Fitzhardinge wrote:
> > Mathieu Desnoyers wrote:
> > 
> >> +#define immediate_read(name)						\
> >> +	({								\
> >> +		__typeof__(name##__immediate) 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"		\
> > 
> > Given that you're relying on the exact instruction that this mov
> > generates, it might be better to explicitly put the opcodes in with
> > .byte.  That way you're protected from the assembler deciding to
> > generate some other form of the instruction (for whatever reason).  I
> > guess substituting in different registers would be a pain.
> 
> Allowing different registers should be doable, but if so, one would have
> to put 0: at the *end* of the instruction and use (0f)-4 instead, since
> the non-%eax forms are one byte longer.
> 
> This also seems "safer", since an imm32 is always the last thing in the
> instruction.
> 

The idea is very interesting, but then, if I can't be sure of the size
of my instruction, how can I align the immediate value properly ?

> 	-hpa
> 

-- 
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 4/7] Immediate Values - i386 Optimization

[Andi Kleen]

Jeremy Fitzhardinge <jeremy@goop.org> writes:
> 
> It's a pity that gas seems to generate plain 0x90 nops rather than
> long-nop forms here.  I thought it could do that.

.p2align does it.

-Andi

Re: [patch 4/7] Immediate Values - i386 Optimization

[Jeremy Fitzhardinge]

Andi Kleen wrote:
> Jeremy Fitzhardinge <jeremy@goop.org> writes:
>   
>> It's a pity that gas seems to generate plain 0x90 nops rather than
>> long-nop forms here.  I thought it could do that.
>>     
>
> .p2align does it

Just .p2align?  Not align, balign, org or skip?  Seems... strange.

    J

Re: [patch 4/7] Immediate Values - i386 Optimization

[H. Peter Anvin]

Jeremy Fitzhardinge wrote:
> Andi Kleen wrote:
>> Jeremy Fitzhardinge <jeremy@goop.org> writes:
>>   
>>> It's a pity that gas seems to generate plain 0x90 nops rather than
>>> long-nop forms here.  I thought it could do that.
>>>     
>> .p2align does it
> 
> Just .p2align?  Not align, balign, org or skip?  Seems... strange.
> 

Probably it works for .align and .balign too, but not .org.

	-hpa

Re: [patch 4/7] Immediate Values - i386 Optimization

[Andi Kleen]

On Tue, Sep 18, 2007 at 03:29:50PM -0700, Jeremy Fitzhardinge wrote:
> Andi Kleen wrote:
> > Jeremy Fitzhardinge <jeremy@goop.org> writes:
> >   
> >> It's a pity that gas seems to generate plain 0x90 nops rather than
> >> long-nop forms here.  I thought it could do that.
> >>     
> >
> > .p2align does it
> 
> Just .p2align?  Not align, balign, org or skip?  Seems... strange.

The problem is that you cannot always safely jump into the middle of the 
longer form nops. So I suppose they didn't risk breakage on older
code relying on this.

-Andi

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* Andi Kleen (andi@firstfloor.org) wrote:
> Jeremy Fitzhardinge <jeremy@goop.org> writes:
> > 
> > It's a pity that gas seems to generate plain 0x90 nops rather than
> > long-nop forms here.  I thought it could do that.
> 
> .p2align does it.
> 

Sadly, p2align does not apply well to my context. I have to align on 4
bytes boundaries - 1 for the 4 bytes mov, so, if I would use p2align, I
would end up aligning on 4 bytes with p2align and then add 3 bytes
(worse case: adding 3 + 3 = 6 bytes of nops).

However, with the .org arithmetic, I can simply add then quantity of
nops needed to make my alignment on 4 bytes - 1, so the worse case
becomes adding 3 bytes.

The example is:

originally: address & 3 = 1
* p2align
p2align adds 3 bytes to align on 4 bytes boundaries
we add 3 bytes to align on the next 4 bytes - 1, so the immediate value
within the instruction is aligned on 4 bytes boundaries

* org
we add 2 bytes to be aligned on the next 4 bytes - 1.

And yes, it's a pity there is no way to produce the long-nops there. :(

Mathieu

> -Andi

-- 
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 4/7] Immediate Values - i386 Optimization

[Andi Kleen]

> And yes, it's a pity there is no way to produce the long-nops there. :(

To be honest I consider it extremly unlikely you would be able
to measure a difference.

-Andi

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* Jeremy Fitzhardinge (jeremy@goop.org) wrote:
> Mathieu Desnoyers wrote:
> 
> > +#define immediate_read(name)						\
> > +	({								\
> > +		__typeof__(name##__immediate) 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"		\
> 
> Given that you're relying on the exact instruction that this mov
> generates, it might be better to explicitly put the opcodes in with
> .byte.  That way you're protected from the assembler deciding to
> generate some other form of the instruction (for whatever reason).  I
> guess substituting in different registers would be a pain.
> 

Good point. I thought it might come up, especially for 16 bits mov that
can be expressed under different forms, one of which has a prefix. I
would like to go for Peter's suggestion: putting the label _after_ the
instruction, since we know that we will be right after the immediate
value, but it has a drawback: we cannot insure correct alignment of the
immediate value in that case. But that would help not having to force
the register.

> Aside from that,  is there any reason not to just put $0 in there rather
> than use %2?
> 

Actually, no, since the initial value is written to the immediate value
references at early boot and at module load time. I originally thought
passing the referenced variable to it, but, as I recall, it brought
linker issues when the symbol was defined in another module. So yes,
just $0 is ok, I'll change that.

> 
> > +					".long %1, (0f)+1, 4;\n\t"	\
> > +					".previous;\n\t"		\
> > +					"1:\n\t"			\
> > +					".org (1b)+(3-((1b)%%4)), 0x90;\n\t" \
> >   
> Seems a little complex, but I couldn't come up with anything much better:
> 
> 	.org . + 3 - (. & 3), 0x90
> 
> You can use . rather than needing to define 1:, it doesn't need quite so
> many parens, and using &3 avoids the %% wart. 
> 

Yes, this one is tricky.. trying to align efficiently something on a 4
bytes address - 1 is not what gas is used to help doing.

> It's a pity that gas seems to generate plain 0x90 nops rather than
> long-nop forms here.  I thought it could do that.
> 

At least we will have at most 3 nops there.

Mathieu

>     J

-- 
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 4/7] Immediate Values - i386 Optimization

[Denys Vlasenko]

On Tuesday 18 September 2007 22:07, Mathieu Desnoyers wrote:
> i386 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.
> 
> Changelog:
> - Use text_poke_early with cr0 WP save/restore to patch the bypass. We are doing
>   non atomic writes to a code region only touched by us (nobody can execute it
>   since we are protected by the immediate_mutex).
> - Put immediate_set and _immediate_set in the architecture independent header.

> +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. */
> +};


> +		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" (name##__immediate),		\
> +				  "i" (0));				\

Instead of letting gcc use whatever instruction it sees fit best
for accessing the variable (like add/cmp/test...)
now we force it to use mov imm,reg first. Maybe with preceding nop
due to "align 2".

And then we use 12 more bytes in __immediate section
*for each* place where you read the variable.

Do you plan to use the same approach on x86_64?
I mean, longs there are twice as long.

Can this be made conditional, on CONFIG_CC_OPTIMIZE_FOR_SIZE perhaps?
--
vda

Re: [patch 4/7] Immediate Values - i386 Optimization

[Mathieu Desnoyers]

* Denys Vlasenko (vda.linux@googlemail.com) wrote:
> On Tuesday 18 September 2007 22:07, Mathieu Desnoyers wrote:
> > i386 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.
> > 
> > Changelog:
> > - Use text_poke_early with cr0 WP save/restore to patch the bypass. We are doing
> >   non atomic writes to a code region only touched by us (nobody can execute it
> >   since we are protected by the immediate_mutex).
> > - Put immediate_set and _immediate_set in the architecture independent header.
> 
> > +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. */
> > +};
> 
> 
> > +		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" (name##__immediate),		\
> > +				  "i" (0));				\
> 
> Instead of letting gcc use whatever instruction it sees fit best
> for accessing the variable (like add/cmp/test...)
> now we force it to use mov imm,reg first. Maybe with preceding nop
> due to "align 2".
> 

Yes, this is true. So, the following branch:

char x;

void testb(void)
{
        if (x > 5)
                testa();
}

Would turn into:
  56:   b0 00                   mov    $0x0,%al
  58:   3c 05                   cmp    $0x5,%al
  5a:   7e 05                   jle    61 <testb+0x11>


Rather than:

  56:   80 3d 00 00 00 00 05    cmpb   $0x5,0x0
  5d:   7e 05                   jle    64 <testb+0x14>

> And then we use 12 more bytes in __immediate section
> *for each* place where you read the variable.
> 

Yes. You must consider the this section is only used when updating the
variable. It is never used by the read-side and therefore does not
consume data cache on hot paths.

> Do you plan to use the same approach on x86_64?
> I mean, longs there are twice as long.
> 

Yup. It's a memory footprint vs active cacheline footprints tradeoff.
When GCC optimizes for size and we see kernel speedups, it is not so
because it "consumes" less memory, but rather that there is less junk
polluting the cachelines. So unless you worry about a few K of data and
are an embedded system developer, I really don't see why you worry about
this. Oh, and by the way, I provide the ability to disable immediate
values in the EMBEDDED menu.

> Can this be made conditional, on CONFIG_CC_OPTIMIZE_FOR_SIZE perhaps?

No. As I just stated, only embedded developers would have an interest in
disabling this features because they would have so few memory available
on their architecture. The memory consumed by the immediate values table
is out of the hot path cachelines and therefore does not impact overall
performance.

> --
> vda

-- 
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/7] Immediate Values - Powerpc Optimization

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-powerpc-optimization.patch --]
[-- Type: text/plain, Size: 6946 bytes --]

PowerPC optimization of the immediate values which uses a li instruction,
patched with an immediate value.

Changelog:
- Put immediate_set and _immediate_set in the architecture independent header.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
CC: Christoph Hellwig <hch@infradead.org>
---
 arch/powerpc/kernel/Makefile    |    1 
 arch/powerpc/kernel/immediate.c |  103 ++++++++++++++++++++++++++++++++++++++++
 include/asm-powerpc/immediate.h |   73 ++++++++++++++++++++++++++++
 3 files changed, 177 insertions(+)

Index: linux-2.6-lttng/include/asm-powerpc/immediate.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6-lttng/include/asm-powerpc/immediate.h	2007-09-17 13:39:02.000000000 -0400
@@ -0,0 +1,73 @@
+#ifndef _ASM_POWERPC_IMMEDIATE_H
+#define _ASM_POWERPC_IMMEDIATE_H
+
+/*
+ * Immediate values. PowerPC architecture optimizations.
+ *
+ * (C) Copyright 2006 Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
+ *
+ * This file is released under the GPLv2.
+ * See the file COPYING for more details.
+ */
+
+#include <asm/asm-compat.h>
+
+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
+ * @name: immediate value name
+ *
+ * Reads the value of @name.
+ * 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(name)						\
+	({								\
+		__typeof__(name##__immediate) 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" (&name##__immediate),		\
+				  "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" (&name##__immediate),		\
+				  "i" (0));				\
+			break;						\
+		default:						\
+			value = name##__immediate;			\
+			break;						\
+		};							\
+		value;							\
+	})
+
+extern int arch_immediate_update(const struct __immediate *immediate);
+extern void arch_immediate_update_early(const struct __immediate *immediate);
+
+#endif /* _ASM_POWERPC_IMMEDIATE_H */
Index: linux-2.6-lttng/arch/powerpc/kernel/Makefile
===================================================================
--- linux-2.6-lttng.orig/arch/powerpc/kernel/Makefile	2007-09-17 13:37:03.000000000 -0400
+++ linux-2.6-lttng/arch/powerpc/kernel/Makefile	2007-09-17 13:38:54.000000000 -0400
@@ -97,3 +97,4 @@ obj-$(CONFIG_PPC64)		+= $(obj64-y)
 
 extra-$(CONFIG_PPC_FPU)		+= fpu.o
 extra-$(CONFIG_PPC64)		+= entry_64.o
+obj-$(CONFIG_IMMEDIATE)		+= immediate.o
Index: linux-2.6-lttng/arch/powerpc/kernel/immediate.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6-lttng/arch/powerpc/kernel/immediate.c	2007-09-17 13:38:54.000000000 -0400
@@ -0,0 +1,103 @@
+/*
+ * Powerpc optimized immediate values enabling/disabling.
+ *
+ * Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
+ */
+
+#include <linux/module.h>
+#include <linux/immediate.h>
+#include <linux/string.h>
+#include <linux/kprobes.h>
+#include <asm/cacheflush.h>
+#include <asm/page.h>
+
+#define LI_OPCODE_LEN	2
+
+/**
+ * arch_immediate_update - update one immediate value
+ * @immediate: pointer of type const struct __immediate to update
+ *
+ * Update one immediate value. Must be called with immediate_mutex held.
+ */
+int arch_immediate_update(const struct __immediate *immediate)
+{
+#ifdef CONFIG_KPROBES
+	kprobe_opcode_t *insn;
+	/*
+	 * Fail if a kprobe has been set on this instruction.
+	 * (TODO: we could eventually do better and modify all the (possibly
+	 * nested) kprobes for this site if kprobes had an API for this.
+	 */
+	switch (immediate->size) {
+		case 1:	/* The uint8_t points to the 3rd byte of the
+			 * instruction */
+			insn = (void*)(immediate->immediate - 1 - LI_OPCODE_LEN);
+			break;
+		case 2:	insn = (void*)(immediate->immediate - LI_OPCODE_LEN);
+			break;
+		default:
+		return -EINVAL;
+	}
+
+	if (unlikely(*insn == BREAKPOINT_INSTRUCTION)) {
+		printk(KERN_WARNING "Immediate value in conflict with kprobe. "
+				    "Variable at %p, "
+				    "instruction at %p, size %lu\n",
+				    (void*)immediate->immediate,
+				    (void*)immediate->var, immediate->size);
+		return -EBUSY;
+	}
+#endif
+
+	/*
+	 * If the variable and the instruction have the same value, there is
+	 * nothing to do.
+	 */
+	switch (immediate->size) {
+		case 1:	if (*(uint8_t*)immediate->immediate
+					== *(uint8_t*)immediate->var)
+				return 0;
+			break;
+		case 2:	if (*(uint16_t*)immediate->immediate
+					== *(uint16_t*)immediate->var)
+				return 0;
+			break;
+		default:return -EINVAL;
+	}
+	memcpy((void*)immediate->immediate, (void*)immediate->var,
+			immediate->size);
+	flush_icache_range((unsigned long)immediate->immediate,
+		(unsigned long)immediate->immediate + immediate->size);
+	return 0;
+}
+
+/**
+ * arch_immediate_update_early - update one immediate value at boot time
+ * @immediate: pointer of type const struct __immediate to update
+ *
+ * Update one immediate value at boot time.
+ * We can use flush_icache_range, since the cpu identification has been done in
+ * the early_init stage.
+ */
+void __init arch_immediate_update_early(const struct __immediate *immediate)
+{
+	/*
+	 * If the variable and the instruction have the same value, there is
+	 * nothing to do.
+	 */
+	switch (immediate->size) {
+		case 1:	if (*(uint8_t*)immediate->immediate
+					== *(uint8_t*)immediate->var)
+				return;
+			break;
+		case 2:	if (*(uint16_t*)immediate->immediate
+					== *(uint16_t*)immediate->var)
+				return;
+			break;
+		default:return;
+	}
+	memcpy((void*)immediate->immediate, (void*)immediate->var,
+			immediate->size);
+	flush_icache_range((unsigned long)immediate->immediate,
+		(unsigned long)immediate->immediate + immediate->size);
+}

-- 
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/7] Immediate Values - Documentation

[Mathieu Desnoyers]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: immediate-values-documentation.patch --]
[-- Type: text/plain, Size: 9211 bytes --]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
---
 Documentation/immediate.txt |  228 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 228 insertions(+)

Index: linux-2.6-lttng/Documentation/immediate.txt
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6-lttng/Documentation/immediate.txt	2007-09-18 09:12:01.000000000 -0400
@@ -0,0 +1,228 @@
+		        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 sit 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
+if (unlikely(immediate_read(var))) as condition surrounding the code. The
+smallest data type required for the test (an 8 bits char) is preferred, since
+some architectures, such as powerpc, only allow up to 16 bits immediate values.
+
+
+* Usage
+
+In order to use the "immediate" macros, you should include linux/immediate.h.
+
+#include <linux/immediate.h>
+
+DEFINE_IMMEDIATE(char, this_immediate);
+EXPORT_IMMEDIATE_SYMBOL(this_immediate);
+
+
+And use, in the body of a function:
+
+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).
+
+immediate_set_early() should be used only at early kernel boot time, before SMP
+is activated. It provides no locking, does not clear the write-protection bits
+when touching executable pages and does not take into account SMP errata on the
+i386 and x86_64 architectures. By not doing so, it can update the immediate
+values very early at kernel boot time and require only the minimalistic
+infrastructure available at that point.
+
+You can choose to set an initial static value to the immediate by using, for
+instance:
+
+DEFINE_IMMEDIATE(long, myptr) = 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
+  nothing 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 sorts 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 laid 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).
+
+
+- Test redone with less iterations, but with error estimates
+
+10 runs of 100 iterations each: Tests done on a 3GHz P4. Here I run getppid with
+syscall trace inactive, comparing the case with memory pressure and without
+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 cycles
+
+
+So, 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.
+
+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.

-- 
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/7] Scheduler Profiling - Use Immediate Values

[Mathieu Desnoyers]

[-- Attachment #1: profiling-use-immediate-values.patch --]
[-- Type: text/plain, Size: 5025 bytes --]

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

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
---
 drivers/kvm/kvm_main.c  |    3 ++-
 include/linux/profile.h |    5 +++--
 kernel/profile.c        |   22 +++++++++++-----------
 3 files changed, 16 insertions(+), 14 deletions(-)

Index: linux-2.6-lttng/kernel/profile.c
===================================================================
--- linux-2.6-lttng.orig/kernel/profile.c	2007-09-18 10:09:12.000000000 -0400
+++ linux-2.6-lttng/kernel/profile.c	2007-09-18 13:15:15.000000000 -0400
@@ -42,8 +42,8 @@ static int (*timer_hook)(struct pt_regs 
 static atomic_t *prof_buffer;
 static unsigned long prof_len, prof_shift;
 
-int prof_on __read_mostly;
-EXPORT_SYMBOL_GPL(prof_on);
+DEFINE_IMMEDIATE(char, prof_on) __read_mostly;
+EXPORT_IMMEDIATE_SYMBOL_GPL(prof_on);
 
 static cpumask_t prof_cpu_mask = CPU_MASK_ALL;
 #ifdef CONFIG_SMP
@@ -60,7 +60,7 @@ static int __init profile_setup(char * s
 	int par;
 
 	if (!strncmp(str, sleepstr, strlen(sleepstr))) {
-		prof_on = SLEEP_PROFILING;
+		immediate_set_early(prof_on, SLEEP_PROFILING);
 		if (str[strlen(sleepstr)] == ',')
 			str += strlen(sleepstr) + 1;
 		if (get_option(&str, &par))
@@ -69,7 +69,7 @@ static int __init profile_setup(char * s
 			"kernel sleep profiling enabled (shift: %ld)\n",
 			prof_shift);
 	} else if (!strncmp(str, schedstr, strlen(schedstr))) {
-		prof_on = SCHED_PROFILING;
+		immediate_set_early(prof_on, SCHED_PROFILING);
 		if (str[strlen(schedstr)] == ',')
 			str += strlen(schedstr) + 1;
 		if (get_option(&str, &par))
@@ -78,7 +78,7 @@ static int __init profile_setup(char * s
 			"kernel schedule profiling enabled (shift: %ld)\n",
 			prof_shift);
 	} else if (!strncmp(str, kvmstr, strlen(kvmstr))) {
-		prof_on = KVM_PROFILING;
+		immediate_set_early(prof_on, KVM_PROFILING);
 		if (str[strlen(kvmstr)] == ',')
 			str += strlen(kvmstr) + 1;
 		if (get_option(&str, &par))
@@ -88,7 +88,7 @@ static int __init profile_setup(char * s
 			prof_shift);
 	} else if (get_option(&str, &par)) {
 		prof_shift = par;
-		prof_on = CPU_PROFILING;
+		immediate_set_early(prof_on, CPU_PROFILING);
 		printk(KERN_INFO "kernel profiling enabled (shift: %ld)\n",
 			prof_shift);
 	}
@@ -99,7 +99,7 @@ __setup("profile=", profile_setup);
 
 void __init profile_init(void)
 {
-	if (!prof_on) 
+	if (!_immediate_read(prof_on))
 		return;
  
 	/* only text is profiled */
@@ -288,7 +288,7 @@ void profile_hits(int type, void *__pc, 
 	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 +398,7 @@ void profile_hits(int type, void *__pc, 
 {
 	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 +555,7 @@ static int __init create_hash_tables(voi
 	}
 	return 0;
 out_cleanup:
-	prof_on = 0;
+	immediate_set_early(prof_on, 0);
 	smp_mb();
 	on_each_cpu(profile_nop, NULL, 0, 1);
 	for_each_online_cpu(cpu) {
@@ -582,7 +582,7 @@ static int __init create_proc_profile(vo
 {
 	struct proc_dir_entry *entry;
 
-	if (!prof_on)
+	if (!_immediate_read(prof_on))
 		return 0;
 	if (create_hash_tables())
 		return -1;
Index: linux-2.6-lttng/include/linux/profile.h
===================================================================
--- linux-2.6-lttng.orig/include/linux/profile.h	2007-09-18 10:09:12.000000000 -0400
+++ linux-2.6-lttng/include/linux/profile.h	2007-09-18 13:15:15.000000000 -0400
@@ -7,10 +7,11 @@
 #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;
+DECLARE_IMMEDIATE(char, prof_on) __read_mostly;
 
 #define CPU_PROFILING	1
 #define SCHED_PROFILING	2
@@ -38,7 +39,7 @@ static inline void profile_hit(int type,
 	/*
 	 * Speedup for the common (no profiling enabled) case:
 	 */
-	if (unlikely(prof_on == type))
+	if (unlikely(immediate_read(prof_on) == type))
 		profile_hits(type, ip, 1);
 }
 
Index: linux-2.6-lttng/drivers/kvm/kvm_main.c
===================================================================
--- linux-2.6-lttng.orig/drivers/kvm/kvm_main.c	2007-09-18 13:16:26.000000000 -0400
+++ linux-2.6-lttng/drivers/kvm/kvm_main.c	2007-09-18 13:18:04.000000000 -0400
@@ -2063,7 +2063,8 @@ again:
 	/*
 	 * Profile KVM exit RIPs:
 	 */
-	if (unlikely(prof_on == KVM_PROFILING)) {
+
+	if (unlikely(immediate_read(prof_on) == KVM_PROFILING)) {
 		kvm_x86_ops->cache_regs(vcpu);
 		profile_hit(KVM_PROFILING, (void *)vcpu->rip);
 	}

-- 
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 0/7] Immediate Values

[Mathieu Desnoyers]

Hi Andrew,

Here are the updated immediate values for 2.6.24-git12.

Dependencies :

# instrumentation menu removal #merged in kbuild.git
fix-arm-to-play-nicely-with-generic-instrumentation-menu.patch
create-arch-kconfig.patch
add-have-oprofile.patch
add-have-kprobes.patch
move-kconfiginstrumentation-to-arch-kconfig-and-init-kconfig.patch
#
#Kprobes mutex cleanup
kprobes-use-mutex-for-insn-pages.patch
kprobes-dont-use-kprobes-mutex-in-arch-code.patch
kprobes-declare-kprobes-mutex-static.patch
#Enhance DEBUG_RODATA support
x86-enhance-debug-rodata-support-alternatives.patch
x86-enhance-debug-rodata-support-for-hotplug-and-kprobes.patch
#Text Edit Lock (depends on Enhance DEBUG_RODATA and kprobes mutex cleanup)
text-edit-lock-architecture-independent-code.patch
text-edit-lock-kprobes-architecture-independent-support.patch

The patchset applies in the following order :

#Immediate Values
immediate-values-architecture-independent-code.patch
immediate-values-kconfig-menu-in-embedded.patch
immediate-values-x86-optimization.patch
add-text-poke-and-sync-core-to-powerpc.patch
immediate-values-powerpc-optimization.patch
immediate-values-documentation.patch
#
scheduler-profiling-use-immediate-values.patch
#

Mathieu


-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

[patch 2/7] Immediate Values - Kconfig menu in EMBEDDED

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-kconfig-menu-in-embedded.patch --]
[-- Type: text/plain, Size: 2661 bytes --]

Immediate 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.

Note: Since I think that I really should let embedded systems developers using
RO memory the option to disable the immediate values, I choose to leave this
menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes
sense because we want to compile out all the immediate code when we decide not
to use optimized immediate values at all (it removes otherwise unused code).

Changelog:
- Change ARCH_SUPPORTS_IMMEDIATE for ARCH_HAS_IMMEDIATE

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
CC: Rusty Russell <rusty@rustcorp.com.au>
CC: Adrian Bunk <bunk@stusta.de>
CC: Andi Kleen <andi@firstfloor.org>
CC: Alexey Dobriyan <adobriyan@gmail.com>
CC: Christoph Hellwig <hch@infradead.org>
---
 init/Kconfig |   24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

Index: linux-2.6-lttng/init/Kconfig
===================================================================
--- linux-2.6-lttng.orig/init/Kconfig	2008-01-29 15:26:54.000000000 -0500
+++ linux-2.6-lttng/init/Kconfig	2008-01-29 15:27:17.000000000 -0500
@@ -444,6 +444,20 @@ config CC_OPTIMIZE_FOR_SIZE
 config SYSCTL
 	bool
 
+config IMMEDIATE
+	default y if !DISABLE_IMMEDIATE
+	depends on HAVE_IMMEDIATE
+	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. They can be
+	  disabled through the EMBEDDED menu.
+
+config HAVE_IMMEDIATE
+	def_bool n
+
 menuconfig EMBEDDED
 	bool "Configure standard kernel features (for small systems)"
 	help
@@ -679,6 +693,16 @@ config MARKERS
 
 source "arch/Kconfig"
 
+config DISABLE_IMMEDIATE
+	default y if EMBEDDED
+	bool "Disable immediate values" if EMBEDDED
+	depends on HAVE_IMMEDIATE
+	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 SLABINFO

-- 
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 0/7] Immediate Values (redux) for 2.6.24-rc4-git3

[Mathieu Desnoyers]

Hi,

Here are the redux version of immediate values. It currently supports x86_32,
x86_64 and powerpc. The other architectures use a generic fallback (a simple
variable).

It depends on the text edit lock patches. It diminishes the impact of dormant
markers by providing a fast branch over a function call with a "load immediate"
instruction. It minimizes the d-cache hit.

This redux version it not reentrant wrt NMIs and MCEs. One must be cautious not
to use it in code paths reached by such execution contexts.

It could be interesting to queue this for 2.6.25.

Mathieu

-- 
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68

[patch 2/7] Immediate Values - Kconfig menu in EMBEDDED

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-kconfig-embedded.patch --]
[-- Type: text/plain, Size: 2663 bytes --]

Immediate 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.

Note: Since I think that I really should let embedded systems developers using
RO memory the option to disable the immediate values, I choose to leave this
menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes
sense because we want to compile out all the immediate code when we decide not
to use optimized immediate values at all (it removes otherwise unused code).

Changelog:
- Change ARCH_SUPPORTS_IMMEDIATE for ARCH_HAS_IMMEDIATE

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
CC: Rusty Russell <rusty@rustcorp.com.au>
CC: Adrian Bunk <bunk@stusta.de>
CC: Andi Kleen <andi@firstfloor.org>
CC: Alexey Dobriyan <adobriyan@gmail.com>
CC: Christoph Hellwig <hch@infradead.org>
---
 init/Kconfig |   24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

Index: linux-2.6-lttng/init/Kconfig
===================================================================
--- linux-2.6-lttng.orig/init/Kconfig	2007-12-05 20:53:19.000000000 -0500
+++ linux-2.6-lttng/init/Kconfig	2007-12-05 20:53:35.000000000 -0500
@@ -435,6 +435,20 @@ config CC_OPTIMIZE_FOR_SIZE
 config SYSCTL
 	bool
 
+config IMMEDIATE
+	default y if !DISABLE_IMMEDIATE
+	depends on HAVE_IMMEDIATE
+	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. They can be
+	  disabled through the EMBEDDED menu.
+
+config HAVE_IMMEDIATE
+	def_bool n
+
 menuconfig EMBEDDED
 	bool "Configure standard kernel features (for small systems)"
 	help
@@ -670,6 +684,16 @@ config MARKERS
 
 source "arch/Kconfig"
 
+config DISABLE_IMMEDIATE
+	default y if EMBEDDED
+	bool "Disable immediate values" if EMBEDDED
+	depends on HAVE_IMMEDIATE
+	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

-- 
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 0/7] Immediate Values

[Mathieu Desnoyers]

Hi Andrew,

Here are the updated immediate values, following recent discussions.

It depends on the text edit lock patches.

It applies to 2.6.23-rc4-mm1, in the following order:

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

-- 
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/7] Immediate Values - Kconfig menu in EMBEDDED

[Mathieu Desnoyers]

[-- Attachment #1: immediate-values-kconfig-embedded.patch --]
[-- Type: text/plain, Size: 2647 bytes --]

Immediate 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.

Note: Since I think that I really should let embedded systems developers using
RO memory the option to disable the immediate values, I choose to leave this
menu option there, in the EMBEDDED menu. Also, the "CONFIG_IMMEDIATE" makes
sense because we want to compile out all the immediate code when we decide not
to use optimized immediate values at all (it removes otherwise unused code).

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
CC: Adrian Bunk <bunk@stusta.de>
CC: Andi Kleen <andi@firstfloor.org>
CC: Alexey Dobriyan <adobriyan@gmail.com>
CC: Christoph Hellwig <hch@infradead.org>
---
 init/Kconfig |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

Index: linux-2.6-lttng/init/Kconfig
===================================================================
--- linux-2.6-lttng.orig/init/Kconfig	2007-09-04 11:53:59.000000000 -0400
+++ linux-2.6-lttng/init/Kconfig	2007-09-04 12:12:03.000000000 -0400
@@ -407,6 +407,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
@@ -645,6 +656,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

-- 
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/7] Immediate Values - Kconfig menu in EMBEDDED

[Randy Dunlap]

On Mon, 17 Sep 2007 14:42:26 -0400 Mathieu Desnoyers wrote:

>  init/Kconfig |   21 +++++++++++++++++++++
>  1 file changed, 21 insertions(+)
> 
> Index: linux-2.6-lttng/init/Kconfig
> ===================================================================
> --- linux-2.6-lttng.orig/init/Kconfig	2007-09-04 11:53:59.000000000 -0400
> +++ linux-2.6-lttng/init/Kconfig	2007-09-04 12:12:03.000000000 -0400
> @@ -407,6 +407,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

                                       read-mostly

> +	  updated. They use code patching to modify the values inscribed in the
> +	  instruction stream. It provides a way to save precious cache lines

They .... (then) It ...
so choose one of the other.  I think I prefer "They".

> +	  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

---
~Randy
*** Remember to use Documentation/SubmitChecklist when testing your code ***