Skip to contentSkip to conversation

Immediate Values

PATCH In review Mathieu Desnoyers 12 participants 51 messages Jul 3, 2007 – Jul 11, 2007

Subsystems (15)
lore
Share & tools
lore
#0 lore raw

cover Immediate Values

Hi,

This is the update to the Immediate Values patch. It provides a value with a load immediate instruction instead of requiring a data load which could hurt the data cache. It aims at providing a very efficient manner to branch over compiled-in but mostly inactive code.

This release takes care of the modifications suggested in the previous round of review (thanks to all reviewers!).

It applies on 2.6.22-rc6-mm1, and depends on the text edit lock patch.

Mathieu

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

PATCH 1/10 Immediate values - Global modules list and module mutex

Remove "static" from module_mutex and the modules list so it can be used by other builtin objects in the kernel. Otherwise, every code depending on the module list would have to be put in kernel/module.c. Since the immediate values depends on the module list but can be considered as logically different, it makes sense to implement them in their own file.

---
 kernel/module.c |    4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/module.c +2 -2
Index: linux-2.6-lttng/kernel/module.c
===================================================================
@@ -65,8 +65,8 @@
 static DEFINE_SPINLOCK(modlist_lock);
 
 /* List of modules, protected by module_mutex AND modlist_lock */
-static DEFINE_MUTEX(module_mutex);
-static LIST_HEAD(modules);
+DEFINE_MUTEX(module_mutex);
+LIST_HEAD(modules);
 static DECLARE_MUTEX(notify_mutex);
 
 static BLOCKING_NOTIFIER_HEAD(module_notify_list);
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#2 lore raw

PATCH 2/10 Immediate Value - Architecture Independent Code

In reply to Mathieu Desnoyers

Immediate values (previously known as conditional calls) are used as a fast condition used in an if() statement to compile in a block meant to be dynamically enabled at runtime. When it is disabled, it has a very small
footprint: it loads an immediate value, fed to the branch. In the disabled state, the branch skips the whole block (if the block consists in a function call, it will skip the argument setup and the call itself).

It can be used to compile code in the kernel that is seldomly meant to be dynamically activated. It's the case of CPU specific workarounds, profiling, tracing, etc.

There is a generic immediate() version, which uses standard global variables, and optimized per architecture immediate() implementations, which use a load immediate to remove a data cache hit. When the immediate() 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() activation functions sits in kernel/immediate.c.

Immediate values refer to the memory address of a previously declared integer. This integer hold 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 their current implementation, immediate values should not be used to store data not meant to be either 0 or !0. The goal of the optimized implementations is to get the smallest instruction, with lowest impact on the normal function behavior and to provide a int3 handler teardown that will support preemptible code. Also, since the i386 architecture implementation depends on the 0 vs !0 variable caracteristic, it is recommended to only use these variables as a condition for a if() statement.

---
 include/asm-generic/vmlinux.lds.h |    7 +
 include/linux/immediate.h         |  116 ++++++++++++++++++++++
 include/linux/module.h            |   10 +
 kernel/Makefile                   |    1 
 kernel/immediate.c                |  197 ++++++++++++++++++++++++++++++++++++++
 kernel/module.c                   |   18 +++
 6 files changed, 349 insertions(+)
include/linux/immediate.h new file +116 -0
Index: linux-2.6-lttng/include/linux/immediate.h
===================================================================
@@ -0,0 +1,116 @@
+#ifndef _LINUX_IMMEDIATE_H
+#define _LINUX_IMMEDIATE_H
+
+/*
+ * Immediate values, can be set at runtime. Only set to 0 or 1.
+ *
+ * (C) Copyright 2007 Mathieu Desnoyers <[email protected]>
+ *
+ * This file is released under the GPLv2.
+ * See the file COPYING for more details.
+ */
+
+#ifdef __KERNEL__
+
+struct module;
+
+/* Always access this type with the provided functions. */
+typedef struct { int value; } immediate_t;
+
+struct __immediate {
+		/* Identifier variable (int *) of the immediate value */
+	immediate_t *var;
+		/*
+		 * Pointer to the memory location that holds the value (data or
+ 		 * immediate value within the load immediate instruction).
+		 */
+	void *enable;
+		/* Immediate value flags, see the list below */
+	int flags;
+};
+
+/*
+ * Immediate value flags : selects the mechanism used to set the immediate
+ * value. This is primarily used at reentrancy-unfriendly sites.
+ *
+ * On an architecture that has optimized immediate values implemented,
+ * the IF_OPTIMIZED flags distinguishes between optimized and non-optimized
+ * immediate value statements: typically, reentrancy-unfriendly sites should
+ * declare their immediate values without the IF_OPTIMIZED flag.
+ */
+#define IF_OPTIMIZED		(1 << 0) /* Use optimized immediate */
+#define IF_LOCKDEP		(1 << 1) /* Can trigger lockdep at patch site */
+#define _IF_NR			2
+
+/*
+ * In order to support embedded systems with read-only memory for the text
+ * segment, the choice to disable the "optimized" immediate values is left as a
+ * config option even if the architecture has the optimized flavor.
+ *
+ * This include scheme is used to support both the generic and optimized version
+ * at the same time : if a _immediate is declared with the IF_OPTIMIZED flags
+ * unset, it will use the generic version. This is useful when we must place
+ * immediates in locations that present specific reentrancy issues, such as
+ * some trap handlers, in the lockdep code and some of the scheduler code. The
+ * optimized version, when it uses the i386 mechanism to insure correct
+ * cross-cpu code modification, can trigger a trap, which will call into lockdep
+ * and might have other side-effects.
+ */
+
+#ifdef CONFIG_IMMEDIATE
+
+#include <asm/immediate.h>		/* optimized immediate flavor */
+
+/*
+ * Generic immediate flavor always available.
+ *
+ * Note : the empty asm volatile with read constraint is used here instead of a
+ * "used" attribute to fix a gcc 4.1.x bug.
+ * Quoting Jeremy Fitzhardinge <[email protected]> :
+ * "There's a gcc bug which ignores the attribute for local-scope static
+ * variables: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29299"
+ */
+#define immediate_generic(flags, var)					\
+	({								\
+		static const struct __immediate __immediate_info	\
+			__attribute__((section("__immediate"))) =	\
+			{ &(var), NULL, (flags) & ~IF_OPTIMIZED } ;	\
+		asm volatile ( "" : : "i" (&__immediate_info));		\
+		(var).value;						\
+	})
+
+extern void immediate_arm(immediate_t *var);
+extern void immediate_disarm(immediate_t *var);
+extern int immediate_list(void);
+extern void module_immediate_setup(struct module *mod);
+extern void __immediate_update(immediate_t *var, int value);
+#else /* !CONFIG_IMMEDIATE */
+
+#include <asm-generic/immediate.h>	/* fallback on generic immediate */
+
+#define immediate_generic(flags, var)	(unlikely((var).value))
+
+static inline void immediate_arm(immediate_t *var)
+{
+	var->value = 1;
+}
+
+static inline void immediate_disarm(immediate_t *var)
+{
+	var->value = 0;
+}
+static inline void module_immediate_setup(struct module *mod) { }
+static inline void __immediate_update(immediate_t *var, int value)
+{
+	var->value = value;
+}
+#endif /* CONFIG_IMMEDIATE */
+
+/* immediate_query : Returns 1 if enabled, 0 if disabled or not present */
+static inline int immediate_query(immediate_t *var)
+{
+	return var->value;
+}
+
+#endif /* __KERNEL__ */
+#endif
include/asm-generic/vmlinux.lds.h +7 -0
Index: linux-2.6-lttng/include/asm-generic/vmlinux.lds.h
===================================================================
@@ -122,6 +122,13 @@
 		VMLINUX_SYMBOL(__stop___kcrctab_gpl_future) = .;	\
 	}								\
 									\
+	/* Immediate values: pointers */				\
+	__immediate : AT(ADDR(__immediate) - LOAD_OFFSET) {		\
+		VMLINUX_SYMBOL(__start___immediate) = .;		\
+		*(__immediate)						\
+		VMLINUX_SYMBOL(__stop___immediate) = .;			\
+	}								\
+									\
 	/* Kernel symbol table: strings */				\
         __ksymtab_strings : AT(ADDR(__ksymtab_strings) - LOAD_OFFSET) {	\
 		*(__ksymtab_strings)					\
include/linux/module.h +10 -0
Index: linux-2.6-lttng/include/linux/module.h
===================================================================
@@ -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>
@@ -67,6 +68,10 @@
 /* Archs provide a method of finding the correct exception table. */
 struct exception_table_entry;
 
+/* Protects the list of modules. */
+extern struct mutex module_mutex;
+extern struct list_head modules;
+
 const struct exception_table_entry *
 search_extable(const struct exception_table_entry *first,
 	       const struct exception_table_entry *last,
@@ -370,6 +375,11 @@
 	/* The command line arguments (may be mangled).  People like
 	   keeping pointers to this stuff */
 	char *args;
+
+#ifdef CONFIG_IMMEDIATE
+	const struct __immediate *immediates;
+	unsigned int num_immediates;
+#endif
 };
 #ifndef MODULE_ARCH_INIT
 #define MODULE_ARCH_INIT {}
kernel/module.c +18 -0
Index: linux-2.6-lttng/kernel/module.c
===================================================================
@@ -32,6 +32,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>
@@ -1623,6 +1624,9 @@
 	unsigned int unusedcrcindex;
 	unsigned int unusedgplindex;
 	unsigned int unusedgplcrcindex;
+	unsigned int immediateindex = 0;
+	unsigned int markersindex = 0;
+	unsigned int markersstringsindex = 0;
 	struct module *mod;
 	long err = 0;
 	void *percpu = NULL, *ptr = NULL; /* Stops spurious gcc warning */
@@ -1719,6 +1723,9 @@
 #ifdef ARCH_UNWIND_SECTION_NAME
 	unwindex = find_sec(hdr, sechdrs, secstrings, ARCH_UNWIND_SECTION_NAME);
 #endif
+#ifdef CONFIG_IMMEDIATE
+	immediateindex = find_sec(hdr, sechdrs, secstrings, "__immediate");
+#endif
 
 	/* Don't keep modinfo section */
 	sechdrs[infoindex].sh_flags &= ~(unsigned long)SHF_ALLOC;
@@ -1729,6 +1736,8 @@
 #endif
 	if (unwindex)
 		sechdrs[unwindex].sh_flags |= SHF_ALLOC;
+	if (immediateindex)
+		sechdrs[immediateindex].sh_flags |= SHF_ALLOC;
 
 	/* Check module struct version now, before we try to use module. */
 	if (!check_modstruct_version(sechdrs, versindex, mod)) {
@@ -1869,6 +1878,13 @@
 	mod->gpl_future_syms = (void *)sechdrs[gplfutureindex].sh_addr;
 	if (gplfuturecrcindex)
 		mod->gpl_future_crcs = (void *)sechdrs[gplfuturecrcindex].sh_addr;
+#ifdef CONFIG_IMMEDIATE
+	if (immediateindex) {
+		mod->immediates = (void *)sechdrs[immediateindex].sh_addr;
+		mod->num_immediates =
+			sechdrs[immediateindex].sh_size / sizeof(*mod->immediates);
+	}
+#endif
 
 	mod->unused_syms = (void *)sechdrs[unusedindex].sh_addr;
 	if (unusedcrcindex)
@@ -1934,6 +1950,8 @@
         }
 #endif
 
+	module_immediate_setup(mod);
+
 	err = module_finalize(hdr, sechdrs, mod);
 	if (err < 0)
 		goto cleanup;
kernel/Makefile +1 -0
Index: linux-2.6-lttng/kernel/Makefile
===================================================================
@@ -58,6 +58,7 @@
 obj-$(CONFIG_SYSCTL) += utsname_sysctl.o
 obj-$(CONFIG_TASK_DELAY_ACCT) += delayacct.o
 obj-$(CONFIG_TASKSTATS) += taskstats.o tsacct.o
+obj-$(CONFIG_IMMEDIATE) += immediate.o
 
 ifneq ($(CONFIG_SCHED_NO_NO_OMIT_FRAME_POINTER),y)
 # According to Alan Modra <[email protected]>, the -fno-omit-frame-pointer is
kernel/immediate.c new file +197 -0

197 lines not on this page · raw message

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

PATCH 3/10 Immediate Values - Non Optimized Architectures

In reply to Mathieu Desnoyers

Architecture agnostic, generic, version of the immediate values. It uses a global variable to mimic the immediate values.

---
 include/asm-alpha/immediate.h     |    1 +
 include/asm-arm/immediate.h       |    1 +
 include/asm-arm26/immediate.h     |    1 +
 include/asm-cris/immediate.h      |    1 +
 include/asm-frv/immediate.h       |    1 +
 include/asm-generic/immediate.h   |   14 ++++++++++++++
 include/asm-h8300/immediate.h     |    1 +
 include/asm-i386/immediate.h      |    1 +
 include/asm-ia64/immediate.h      |    1 +
 include/asm-m32r/immediate.h      |    1 +
 include/asm-m68k/immediate.h      |    1 +
 include/asm-m68knommu/immediate.h |    1 +
 include/asm-mips/immediate.h      |    1 +
 include/asm-parisc/immediate.h    |    1 +
 include/asm-powerpc/immediate.h   |    1 +
 include/asm-ppc/immediate.h       |    1 +
 include/asm-s390/immediate.h      |    1 +
 include/asm-sh/immediate.h        |    1 +
 include/asm-sh64/immediate.h      |    1 +
 include/asm-sparc/immediate.h     |    1 +
 include/asm-sparc64/immediate.h   |    1 +
 include/asm-um/immediate.h        |    1 +
 include/asm-v850/immediate.h      |    1 +
 include/asm-x86_64/immediate.h    |    1 +
 include/asm-xtensa/immediate.h    |    1 +
 25 files changed, 38 insertions(+)
include/asm-generic/immediate.h new file +14 -0
Index: linux-2.6-lttng/include/asm-generic/immediate.h
===================================================================
@@ -0,0 +1,14 @@
+#ifndef _ASM_GENERIC_IMMEDIATE_H
+#define _ASM_GENERIC_IMMEDIATE_H
+
+/* Default flags, used by _immediate() */
+#define IF_DEFAULT			0
+
+/* Fallback on the generic immediate, since no optimized version is available */
+#define immediate_optimized		immediate_generic
+#define _immediate(flags, var)		immediate_generic(flags, var)
+
+/* immediate with default behavior */
+#define immediate(var)		_immediate(IF_DEFAULT, var)
+
+#endif /* _ASM_GENERIC_IMMEDIATE_H */
include/asm-alpha/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-alpha/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-arm/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-arm/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-arm26/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-arm26/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-cris/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-cris/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-frv/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-frv/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-h8300/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-h8300/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-ia64/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-ia64/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-m32r/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-m32r/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-m68k/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-m68k/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-m68knommu/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-m68knommu/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-mips/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-mips/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-parisc/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-parisc/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-ppc/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-ppc/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-s390/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-s390/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-sh/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-sh/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-sh64/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-sh64/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-sparc/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-sparc/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-sparc64/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-sparc64/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-um/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-um/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-v850/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-v850/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-x86_64/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-x86_64/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-xtensa/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-xtensa/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-i386/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-i386/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
include/asm-powerpc/immediate.h new file +1 -0
Index: linux-2.6-lttng/include/asm-powerpc/immediate.h
===================================================================
@@ -0,0 +1 @@
+#include <asm-generic/immediate.h>
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#4 lore raw

PATCH 4/10 Immediate Value - Add kconfig menus

In reply to Mathieu Desnoyers

Immediate values provide a way to compile in kernels features that can be enabled dynamically, with a very small footprint when disabled.

This patch:

Add Kconfig menus for the marker code.

---

 arch/alpha/Kconfig       |    6 ++++++
 arch/arm/Kconfig         |    6 ++++++
 arch/arm26/Kconfig       |    6 ++++++
 arch/avr32/Kconfig.debug |    7 +++++++
 arch/cris/Kconfig        |    6 ++++++
 arch/frv/Kconfig         |    6 ++++++
 arch/h8300/Kconfig       |    6 ++++++
 arch/i386/Kconfig        |    2 ++
 arch/ia64/Kconfig        |    3 +++
 arch/m32r/Kconfig        |    6 ++++++
 arch/m68k/Kconfig        |    6 ++++++
 arch/m68knommu/Kconfig   |    6 ++++++
 arch/mips/Kconfig        |    6 ++++++
 arch/parisc/Kconfig      |    6 ++++++
 arch/powerpc/Kconfig     |    3 +++
 arch/ppc/Kconfig         |    6 ++++++
 arch/s390/Kconfig        |    2 ++
 arch/sh/Kconfig          |    6 ++++++
 arch/sh64/Kconfig        |    6 ++++++
 arch/sparc/Kconfig       |    2 ++
 arch/sparc64/Kconfig     |    3 +++
 arch/um/Kconfig          |    6 ++++++
 arch/v850/Kconfig        |    6 ++++++
 arch/x86_64/Kconfig      |    3 +++
 arch/xtensa/Kconfig      |    6 ++++++
 kernel/Kconfig.immediate |    9 +++++++++
 26 files changed, 136 insertions(+)
arch/alpha/Kconfig +6 -0
Index: linux-2.6-lttng/arch/alpha/Kconfig
===================================================================
@@ -653,6 +653,12 @@
 
 source "arch/alpha/oprofile/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/alpha/Kconfig.debug"
 
 # DUMMY_CONSOLE may be defined in drivers/video/console/Kconfig
arch/arm/Kconfig +6 -0
Index: linux-2.6-lttng/arch/arm/Kconfig
===================================================================
@@ -1046,6 +1046,12 @@
 
 source "arch/arm/oprofile/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/arm/Kconfig.debug"
 
 source "security/Kconfig"
arch/arm26/Kconfig +6 -0
Index: linux-2.6-lttng/arch/arm26/Kconfig
===================================================================
@@ -244,6 +244,12 @@
 
 source "drivers/usb/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/arm26/Kconfig.debug"
 
 source "security/Kconfig"
arch/cris/Kconfig +6 -0
Index: linux-2.6-lttng/arch/cris/Kconfig
===================================================================
@@ -198,6 +198,12 @@
 
 source "drivers/usb/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/cris/Kconfig.debug"
 
 source "security/Kconfig"
arch/frv/Kconfig +6 -0
Index: linux-2.6-lttng/arch/frv/Kconfig
===================================================================
@@ -375,6 +375,12 @@
 
 source "fs/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/frv/Kconfig.debug"
 
 source "security/Kconfig"
arch/h8300/Kconfig +6 -0
Index: linux-2.6-lttng/arch/h8300/Kconfig
===================================================================
@@ -223,6 +223,12 @@
 
 source "fs/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/h8300/Kconfig.debug"
 
 source "security/Kconfig"
arch/i386/Kconfig +2 -0
Index: linux-2.6-lttng/arch/i386/Kconfig
===================================================================
@@ -1235,6 +1235,8 @@
 	  for kernel debugging, non-intrusive instrumentation and testing.
 	  If in doubt, say "N".
 
+source "kernel/Kconfig.immediate"
+
 endif # INSTRUMENTATION
 
 source "arch/i386/Kconfig.debug"
arch/ia64/Kconfig +3 -0
Index: linux-2.6-lttng/arch/ia64/Kconfig
===================================================================
@@ -593,6 +593,9 @@
 	  a probepoint and specifies the callback.  Kprobes is useful
 	  for kernel debugging, non-intrusive instrumentation and testing.
 	  If in doubt, say "N".
+
+source "kernel/Kconfig.immediate"
+
 endmenu
 
 source "arch/ia64/Kconfig.debug"
arch/m32r/Kconfig +6 -0
Index: linux-2.6-lttng/arch/m32r/Kconfig
===================================================================
@@ -408,6 +408,12 @@
 
 source "arch/m32r/oprofile/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/m32r/Kconfig.debug"
 
 source "security/Kconfig"
arch/m68k/Kconfig +6 -0
Index: linux-2.6-lttng/arch/m68k/Kconfig
===================================================================
@@ -679,6 +679,12 @@
 
 source "fs/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/m68k/Kconfig.debug"
 
 source "security/Kconfig"
arch/m68knommu/Kconfig +6 -0
Index: linux-2.6-lttng/arch/m68knommu/Kconfig
===================================================================
@@ -668,6 +668,12 @@
 
 source "fs/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/m68knommu/Kconfig.debug"
 
 source "security/Kconfig"
arch/mips/Kconfig +6 -0
Index: linux-2.6-lttng/arch/mips/Kconfig
===================================================================
@@ -1957,6 +1957,12 @@
 
 source "arch/mips/oprofile/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/mips/Kconfig.debug"
 
 source "security/Kconfig"
arch/parisc/Kconfig +6 -0
Index: linux-2.6-lttng/arch/parisc/Kconfig
===================================================================
@@ -269,6 +269,12 @@
 
 source "arch/parisc/oprofile/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/parisc/Kconfig.debug"
 
 source "security/Kconfig"
arch/powerpc/Kconfig +3 -0
Index: linux-2.6-lttng/arch/powerpc/Kconfig
===================================================================
@@ -905,6 +905,9 @@
 	  a probepoint and specifies the callback.  Kprobes is useful
 	  for kernel debugging, non-intrusive instrumentation and testing.
 	  If in doubt, say "N".
+
+source "kernel/Kconfig.immediate"
+
 endmenu
 
 source "arch/powerpc/Kconfig.debug"
arch/ppc/Kconfig +6 -0
Index: linux-2.6-lttng/arch/ppc/Kconfig
===================================================================
@@ -1451,8 +1451,14 @@
 
 source "lib/Kconfig"
 
+menu "Instrumentation Support"
+
 source "arch/powerpc/oprofile/Kconfig"
 
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/ppc/Kconfig.debug"
 
 source "security/Kconfig"
arch/s390/Kconfig +2 -0
Index: linux-2.6-lttng/arch/s390/Kconfig
===================================================================
@@ -547,6 +547,8 @@
 	  for kernel debugging, non-intrusive instrumentation and testing.
 	  If in doubt, say "N".
 
+source "kernel/Kconfig.immediate"
+
 endmenu
 
 source "arch/s390/Kconfig.debug"
arch/sh/Kconfig +6 -0
Index: linux-2.6-lttng/arch/sh/Kconfig
===================================================================
@@ -721,6 +721,12 @@
 
 source "arch/sh/oprofile/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/sh/Kconfig.debug"
 
 source "security/Kconfig"
arch/sh64/Kconfig +6 -0
Index: linux-2.6-lttng/arch/sh64/Kconfig
===================================================================
@@ -284,6 +284,12 @@
 
 source "arch/sh64/oprofile/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/sh64/Kconfig.debug"
 
 source "security/Kconfig"
arch/sparc/Kconfig +2 -0
Index: linux-2.6-lttng/arch/sparc/Kconfig
===================================================================
@@ -313,6 +313,8 @@
 
 source "arch/sparc/oprofile/Kconfig"
 
+source "kernel/Kconfig.immediate"
+
 endmenu
 
 source "arch/sparc/Kconfig.debug"
arch/sparc64/Kconfig +3 -0
Index: linux-2.6-lttng/arch/sparc64/Kconfig
===================================================================
@@ -438,6 +438,9 @@
 	  a probepoint and specifies the callback.  Kprobes is useful
 	  for kernel debugging, non-intrusive instrumentation and testing.
 	  If in doubt, say "N".
+
+source "kernel/Kconfig.immediate"
+
 endmenu
 
 source "arch/sparc64/Kconfig.debug"
arch/um/Kconfig +6 -0
Index: linux-2.6-lttng/arch/um/Kconfig
===================================================================
@@ -335,4 +335,10 @@
 	bool
 	default n
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/um/Kconfig.debug"
arch/v850/Kconfig +6 -0
Index: linux-2.6-lttng/arch/v850/Kconfig
===================================================================
@@ -331,6 +331,12 @@
 
 source "drivers/usb/Kconfig"
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/v850/Kconfig.debug"
 
 source "security/Kconfig"
arch/x86_64/Kconfig +3 -0
Index: linux-2.6-lttng/arch/x86_64/Kconfig
===================================================================
@@ -792,6 +792,9 @@
 	  a probepoint and specifies the callback.  Kprobes is useful
 	  for kernel debugging, non-intrusive instrumentation and testing.
 	  If in doubt, say "N".
+
+source "kernel/Kconfig.immediate"
+
 endmenu
 
 source "arch/x86_64/Kconfig.debug"
arch/xtensa/Kconfig +6 -0
Index: linux-2.6-lttng/arch/xtensa/Kconfig
===================================================================
@@ -251,6 +251,12 @@
 	  provide one yourself.
 endmenu
 
+menu "Instrumentation Support"
+
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 source "arch/xtensa/Kconfig.debug"
 
 source "security/Kconfig"
kernel/Kconfig.immediate new file +9 -0
Index: linux-2.6-lttng/kernel/Kconfig.immediate
===================================================================
@@ -0,0 +1,9 @@
+# Immediate values configuration
+
+config IMMEDIATE
+	bool "Use self-modifying code to provide fast immediate values"
+	help
+	  Provides a way to use immediate values acting as global values to
+	  dynamically enable kernel features while having a very small
+	  footprint when disabled. You may want to disable this feature if you
+	  run your kernel code on a read-only rom/flash.
arch/avr32/Kconfig.debug +7 -0
Index: linux-2.6-lttng/arch/avr32/Kconfig.debug
===================================================================
@@ -6,6 +6,9 @@
 
 source "lib/Kconfig.debug"
 
+menu "Instrumentation Support"
+	depends on EXPERIMENTAL
+
 config KPROBES
 	bool "Kprobes"
 	depends on DEBUG_KERNEL
@@ -16,4 +19,8 @@
           for kernel debugging, non-intrusive instrumentation and testing.
           If in doubt, say "N".
 
+source "kernel/Kconfig.immediate"
+
+endmenu
+
 endmenu
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#5 lore raw

PATCH 5/10 Immediate Values - kprobe header fix

In reply to Mathieu Desnoyers

Since the immediate values depend on the same int3 handler as kprobes implements for i386, we have to get architecture specific defines available for the kprobes trap handler (especially restore_interrupts()) wven when CONFIG_KPROBES is not selected.

That kind of ifdef around a whole header does not make sense in the first place anyway.

---
 include/linux/kprobes.h |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
include/linux/kprobes.h +1 -1
Index: linux-2.6-lttng/include/linux/kprobes.h
===================================================================
@@ -37,9 +37,9 @@
 #include <linux/rcupdate.h>
 #include <linux/mutex.h>
 
-#ifdef CONFIG_KPROBES
 #include <asm/kprobes.h>
 
+#ifdef CONFIG_KPROBES
 /* kprobe_status settings */
 #define KPROBE_HIT_ACTIVE	0x00000001
 #define KPROBE_HIT_SS		0x00000002
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#6 lore raw

PATCH 6/10 Immediate Value - i386 Optimization

In reply to Mathieu Desnoyers

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

---
 arch/i386/kernel/Makefile    |    1 
 arch/i386/kernel/immediate.c |  171 +++++++++++++++++++++++++++++++++++++++++++
 arch/i386/kernel/traps.c     |    8 +-
 include/asm-i386/immediate.h |   72 +++++++++++++++++-
 4 files changed, 247 insertions(+), 5 deletions(-)
include/asm-i386/immediate.h +71 -1
Index: linux-2.6-lttng/include/asm-i386/immediate.h
===================================================================
@@ -1 +1,71 @@
-#include <asm-generic/immediate.h>
+#ifndef _ASM_I386_IMMEDIATE_H
+#define _ASM_I386_IMMEDIATE_H
+
+/*
+ * Immediate values. i386 architecture optimizations.
+ *
+ * (C) Copyright 2006 Mathieu Desnoyers <[email protected]>
+ *
+ * This file is released under the GPLv2.
+ * See the file COPYING for more details.
+ */
+
+#define IF_DEFAULT (IF_OPTIMIZED | IF_LOCKDEP)
+
+/*
+ * Optimized version of the immediate. Passing the flags as a pointer to
+ * the inline assembly to trick it into putting the flags value as third
+ * parameter in the structure.
+ */
+#define immediate_optimized(flags, var)					\
+	({								\
+		int condition;						\
+		asm (	".section __immediate, \"a\", @progbits;\n\t"	\
+					".long %1, 0f, %2;\n\t"		\
+					".previous;\n\t"		\
+					"0:\n\t"			\
+					"movl %3,%0;\n\t"		\
+				: "=r" (condition)			\
+				: "m" (var),				\
+				  "m" (*(char*)flags),			\
+				  "i" (0));				\
+		condition;						\
+	})
+
+/*
+ * immediate macro selecting the generic or optimized version of immediate,
+ * depending on the flags specified. It is a macro because we need to pass the
+ * name to immediate_optimized() and immediate_generic() so they can declare a
+ * static variable with it.
+ */
+#define _immediate(flags, var)						\
+({									\
+	(((flags) & IF_LOCKDEP) && ((flags) & IF_OPTIMIZED)) ?		\
+		immediate_optimized(flags, var) :			\
+		immediate_generic(flags, var);				\
+})
+
+/* immediate with default behavior */
+#define immediate(var)	_immediate(IF_DEFAULT, var)
+
+/*
+ * Architecture dependant immediate information, used internally for immediate
+ * activation.
+ */
+
+/*
+ * Offset of the immediate value from the start of the movl instruction, in
+ * bytes. We point to the first lower byte of the 4 bytes immediate value. Only
+ * changing one byte makes sure we do an atomic memory write, independently of
+ * the alignment of the 4 bytes in the load immediate instruction.
+ */
+#define IMMEDIATE_OPTIMIZED_ENABLE_IMMEDIATE_OFFSET 1
+#define IMMEDIATE_OPTIMIZED_ENABLE_TYPE unsigned char
+/* Dereference enable as lvalue from a pointer to its instruction */
+#define IMMEDIATE_OPTIMIZED_ENABLE(a)					\
+	(*(IMMEDIATE_OPTIMIZED_ENABLE_TYPE*)				\
+		((char*)(a)+IMMEDIATE_OPTIMIZED_ENABLE_IMMEDIATE_OFFSET))
+
+extern int immediate_optimized_set_enable(void *address, char enable);
+
+#endif /* _ASM_I386_IMMEDIATE_H */
arch/i386/kernel/Makefile +1 -0
Index: linux-2.6-lttng/arch/i386/kernel/Makefile
===================================================================
@@ -35,6 +35,7 @@
 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_SERIAL_8250)	+= legacy_serial.o
 obj-$(CONFIG_VM86)		+= vm86.o
arch/i386/kernel/immediate.c new file +171 -0

171 lines not on this page · raw message

arch/i386/kernel/traps.c +4 -4
Index: linux-2.6-lttng/arch/i386/kernel/traps.c
===================================================================
@@ -628,7 +628,7 @@
 }
 
 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)
@@ -848,14 +848,14 @@
 	nmi_exit();
 }
 
-#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 valueswants
+	 * interrupts disabled. Normal trap handlers don't. */
 	restore_interrupts(regs);
 	do_trap(3, SIGTRAP, "int3", 1, regs, error_code, NULL);
 }
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#7 lore raw

Re: [patch 06/10] Immediate Value - i386 Optimization

What is not clear to me is the exact code that is generated by these macros. Nor can I find it anywhere in the documentation.

Could you please describe this in some detail? In particular, it seems that the uses of these are largely as branch targets, where the extra indirection over modifying the jump target directly seems wasted.

-hpa

#8 lore raw

Re: [patch 06/10] Immediate Value - i386 Optimization

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

What is not clear to me is the exact code that is generated by these macros. Nor can I find it anywhere in the documentation.

Could you please describe this in some detail? In particular, it seems that the uses of these are largely as branch targets, where the extra indirection over modifying the jump target directly seems wasted.

Hi Peter,

I understand your concern. If you find a way to let the code be compiled by gcc, put at the end of the functions (never being a branch target) and then, dynamically, get the address of the branch instruction and patch it, all that in cooperation with gcc, I would be glad to hear from it. What I found is that gcc lets us do anything that touches variables/registers in an inline assembly, but does not permit to place branch instructions ourselves; it does not expect the execution flow to be changed in inline asms.

Here is an objdump of the interesting bits on an immediate value placed in scheddule (inline schedule_debug).

00000000 <schedule>:

   0:   55                      push   %ebp
   1:   89 e5                   mov    %esp,%ebp
   3:   57                      push   %edi
   4:   56                      push   %esi
   5:   53                      push   %ebx
   6:   83 ec 40                sub    $0x40,%esp
   9:   b8 01 00 00 00          mov    $0x1,%eax
   e:   e8 fc ff ff ff          call   f <schedule+0xf>
  13:   e8 fc ff ff ff          call   14 <schedule+0x14>
  18:   89 45 dc                mov    %eax,0xffffffdc(%ebp)
  1b:   b8 00 00 00 00          mov    $0x0,%eax
  20:   8b 4d dc                mov    0xffffffdc(%ebp),%ecx
  23:   8b 14 8d 00 00 00 00    mov    0x0(,%ecx,4),%edx
  2a:   01 d0                   add    %edx,%eax
  2c:   89 45 d0                mov    %eax,0xffffffd0(%ebp)
  2f:   b8 00 00 00 00          mov    $0x0,%eax
  34:   c7 44 02 04 01 00 00    movl   $0x1,0x4(%edx,%eax,1)
  3b:   00
  3c:   8b 5d d0                mov    0xffffffd0(%ebp),%ebx
  3f:   8b 9b f0 03 00 00       mov    0x3f0(%ebx),%ebx
  45:   89 5d c8                mov    %ebx,0xffffffc8(%ebp)
  48:   81 c3 94 01 00 00       add    $0x194,%ebx
  4e:   89 5d cc                mov    %ebx,0xffffffcc(%ebp)
  51:   8b 45 c8                mov    0xffffffc8(%ebp),%eax
  54:   8b 40 14                mov    0x14(%eax),%eax
  57:   85 c0                   test   %eax,%eax
  59:   0f 89 30 03 00 00       jns    38f <schedule+0x38f>
  5f:   89 e0                   mov    %esp,%eax
  61:   25 00 e0 ff ff          and    $0xffffe000,%eax
  66:   8b 40 14                mov    0x14(%eax),%eax
  69:   25 ff ff ff ef          and    $0xefffffff,%eax
  6e:   83 e8 01                sub    $0x1,%eax
  71:   0f 85 fb 02 00 00       jne    372 <schedule+0x372>
<branch site>
  77:   b8 00 00 00 00          mov    $0x0,%eax
  7c:   85 c0                   test   %eax,%eax
  7e:   0f 85 16 03 00 00       jne    39a <schedule+0x39a>

here, we just loaded 0 in eax (movl used to make sure we populate the whole register so we do not stall the pipeline)a
When we activate the site,
line 77 becomes: b8 01 00 00 00 mov $0x1,%eax
</branch site>

  84:   8b 45 d0                mov    0xffffffd0(%ebp),%eax
  87:   e8 fc ff ff ff          call   88 <schedule+0x88>
  8c:   8b 4d c8                mov    0xffffffc8(%ebp),%ecx
  8f:   8b 41 04                mov    0x4(%ecx),%eax
  92:   f0 0f ba 70 08 02       lock btrl $0x2,0x8(%eax)

...

<profile_hit inline function>

 39a:   8b 55 04                mov    0x4(%ebp),%edx
 39d:   b9 01 00 00 00          mov    $0x1,%ecx
 3a2:   b8 02 00 00 00          mov    $0x2,%eax
 3a7:   e8 fc ff ff ff          call   3a8 <schedule+0x3a8>
 3ac:   e9 d3 fc ff ff          jmp    84 <schedule+0x84>

</profile_hit inline function>

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

Re: [patch 06/10] Immediate Value - i386 Optimization

Quoted 12 lines · Mathieu Desnoyers

Hi Peter,

I understand your concern. If you find a way to let the code be compiled by gcc, put at the end of the functions (never being a branch target) and then, dynamically, get the address of the branch instruction and patch it, all that in cooperation with gcc, I would be glad to hear from it. What I found is that gcc lets us do anything that touches variables/registers in an inline assembly, but does not permit to place branch instructions ourselves; it does not expect the execution flow to be changed in inline asms.

I believe this is correct. It probably would require requesting a gcc builtin, which might be worthwhile to do if we

Quoted 9 lines

<branch site>

  77:   b8 00 00 00 00          mov    $0x0,%eax
  7c:   85 c0                   test   %eax,%eax
  7e:   0f 85 16 03 00 00       jne    39a <schedule+0x39a>

here, we just loaded 0 in eax (movl used to make sure we populate the whole register so we do not stall the pipeline)a
When we activate the site,
line 77 becomes: b8 01 00 00 00 mov $0x1,%eax
</branch site>

One could, though, use an indirect jump to achieve, if not as good, at least most of the effect:

	movl	$<patchable>,<reg>
	jmp	*<reg>

Some x86 cores will be able to detect the movl...jmp forwarding, and collapse it into a known branch target; however, on the ones that can't, it might be worse, since one would have to rely on the indirect branch predictor.

This would, however, provide infrastructure that could be combined with a future gcc builtin.

-hpa

#10 lore raw

Re: [patch 06/10] Immediate Value - i386 Optimization

Quoted 7 lines · H. Peter Anvin

One could, though, use an indirect jump to achieve, if not as good, at least most of the effect:

	movl	$<patchable>,<reg>
	jmp	*<reg>

Yeah, but there's this GCC bug:

	http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22448

You can't even dereference labels in an ASM statement.

#11 lore raw

Re: [patch 06/10] Immediate Value - i386 Optimization

Quoted 8 lines · Chuck Ebbert
Quoted 6 lines · H. Peter Anvin

One could, though, use an indirect jump to achieve, if not as good, at least most of the effect:

	movl	$<patchable>,<reg>
	jmp	*<reg>
Quoted 5 lines

Yeah, but there's this GCC bug:

	http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22448

You can't even dereference labels in an ASM statement.

I wouldn't to that, though, for the existing compiler. Instead, I
would do:

	void (*func)(void);	/* or what's appropriate */
	asm(<magic movl> : "=rm" (func));
	func();

	-hpa
#12 lore raw

Re: [patch 06/10] Immediate Value - i386 Optimization

In reply to Chuck Ebbert
Quoted 10 lines · Chuck Ebbert
Quoted 7 lines · H. Peter Anvin

One could, though, use an indirect jump to achieve, if not as good, at least most of the effect:

	movl	$<patchable>,<reg>
	jmp	*<reg>
Quoted 5 lines

Yeah, but there's this GCC bug:

	http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22448

You can't even dereference labels in an ASM statement.

I was told in absolute terms that any use of &&label other than to pass it to goto was not supported, and would not be supported.

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29305

Seems that passing to an asm() falls into the same class of problem I had. I think the underlying problem is that if the code containing the label is in an inlined function or unrolled loop, the reference can't be resolved properly anyway.

J

#13 lore raw

Re: [patch 06/10] Immediate Value - i386 Optimization

In reply to H. Peter Anvin
Quoted 27 lines · * H. Peter Anvin ([email protected]) wrote:
Quoted 12 lines · Mathieu Desnoyers

Hi Peter,

I understand your concern. If you find a way to let the code be compiled by gcc, put at the end of the functions (never being a branch target) and then, dynamically, get the address of the branch instruction and patch it, all that in cooperation with gcc, I would be glad to hear from it. What I found is that gcc lets us do anything that touches variables/registers in an inline assembly, but does not permit to place branch instructions ourselves; it does not expect the execution flow to be changed in inline asms.

I believe this is correct. It probably would require requesting a gcc builtin, which might be worthwhile to do if we

Quoted 9 lines

<branch site>

  77:   b8 00 00 00 00          mov    $0x0,%eax
  7c:   85 c0                   test   %eax,%eax
  7e:   0f 85 16 03 00 00       jne    39a <schedule+0x39a>

here, we just loaded 0 in eax (movl used to make sure we populate the whole register so we do not stall the pipeline)
When we activate the site,
line 77 becomes: b8 01 00 00 00 mov $0x1,%eax
</branch site>

Quoted 6 lines

One could, though, use an indirect jump to achieve, if not as good, at least most of the effect:

	movl	$<patchable>,<reg>
	jmp	*<reg>

Using a jmp *<reg> will instruct gcc not to inline inline functions and restrict loop unrolling (but the latter is not used in the linux kernel). We would have to compute different $<patchable> for every site generated by putting an immediate in an inline function.

Quoted 8 lines

Some x86 cores will be able to detect the movl...jmp forwarding, and collapse it into a known branch target; however, on the ones that can't, it might be worse, since one would have to rely on the indirect branch predictor.

This would, however, provide infrastructure that could be combined with a future gcc builtin.

If we can change the compiler, here is what we could do:

Tell GCC to put NOPs that could be altered by a branch alternative to some specified code. We should be able to get the instruction pointers (think of inlines) to these nop/branch instructions so we can change them dynamically.

Something like:

immediate_t myfunc_cond;

inline myfunction(void) {
static void *insn; /* pointer to nops/branch instruction */
static void *target_inactive, *target_active;

  __builtin_polymorphic_if(&insn, &myfunc_cond) {
    /* Do something */
  } else {
    ...

}
}

I could then save all the insns into my immediate value section and later activate them by looking up all of those who refer to myfunc_cond.

The default behavior would be to branch to the target_inactive, and we could change insn to jump to target_active dynamically.

Note that we should align the jump instruction so the address could be changed atomically in the general case (on x86 and x86_64, we have to use an int3 bypass anyway, so we don't really care).

Also, we should fine a way to let gcc tell us what type of jump it had to use depending on how far the target of the branch is.

I suspect this would be inherently tricky. If someone is ready to do this and tells me "yes, it will be there in 1 month", I am more than ready to switch my markers to this and help, but since the core of my work is kernel tracing, I don't have the time nor the ressources to tackle this problem.

In the event that someone answers "we'll do this in the following 3 years", I might consider to change the if (immediate(var)) into an immediate_if (var) so we can later proceed to the change with simple ifdefs without rewriting all the kernel code that would use it.

Mathieu

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

Re: [patch 06/10] Immediate Value - i386 Optimization

Quoted 8 lines · Mathieu Desnoyers

If we can change the compiler, here is what we could do:

Tell GCC to put NOPs that could be altered by a branch alternative to some specified code. We should be able to get the instruction pointers (think of inlines) to these nop/branch instructions so we can change them dynamically.

Changing the compiler should be perfectly feasible, *BUT* I think we need a transitional solution that works on existing compilers.

Quoted 10 lines

I suspect this would be inherently tricky. If someone is ready to do this and tells me "yes, it will be there in 1 month", I am more than ready to switch my markers to this and help, but since the core of my work is kernel tracing, I don't have the time nor the ressources to tackle this problem.

In the event that someone answers "we'll do this in the following 3 years", I might consider to change the if (immediate(var)) into an immediate_if (var) so we can later proceed to the change with simple ifdefs without rewriting all the kernel code that would use it.

This is much more of "we'll do that in the following 1-2 years", since we have to deal with a full gcc development cycle. However, I really want to see this being implemented in a way that would let us DTRT in the long run.

-hpa

#15 lore raw

PATCH 7/10 Immediate Value - PowerPC Optimization

In reply to Mathieu Desnoyers

PowerPC optimization of the immediate values which uses a li instruction, patched with an immediate value 0 or 1 to set the immediate value.

---
 arch/powerpc/kernel/Makefile    |    1 
 arch/powerpc/kernel/immediate.c |   29 ++++++++++++++++
 include/asm-powerpc/immediate.h |   69 +++++++++++++++++++++++++++++++++++++++-
 3 files changed, 98 insertions(+), 1 deletion(-)
include/asm-powerpc/immediate.h +68 -1
Index: linux-2.6-lttng/include/asm-powerpc/immediate.h
===================================================================
@@ -1 +1,68 @@
-#include <asm-generic/immediate.h>
+#ifndef _ASM_POWERPC_IMMEDIATE_H
+#define _ASM_POWERPC_IMMEDIATE_H
+
+/*
+ * Immediate values. PowerPC architecture optimizations.
+ *
+ * (C) Copyright 2006 Mathieu Desnoyers <[email protected]>
+ *
+ * This file is released under the GPLv2.
+ * See the file COPYING for more details.
+ */
+
+#include <asm/asm-compat.h>
+
+#define IF_DEFAULT (IF_OPTIMIZED | IF_LOCKDEP)
+
+/* Optimized version of the immediate */
+#define immediate_optimized(flags, var)					\
+	({								\
+		char condition;						\
+		asm (	".section __immediate, \"a\", @progbits;\n\t"	\
+					PPC_LONG "%1, 0f, %2;\n\t"	\
+					".previous;\n\t"		\
+					".align 4\n\t"			\
+					"0:\n\t"			\
+					"li %0,%3;\n\t"			\
+				: "=r" (condition)			\
+				: "i" (&var),				\
+				  "i" (flags),				\
+				  "i" (0));				\
+		condition;						\
+	})
+
+/*
+ * immediate macro selecting the generic or optimized version of immediate,
+ * depending on the flags specified. It is a macro because we need to pass the
+ * name to immediate_optimized() and immediate_generic() so they can declare a
+ * static variable with it.
+ */
+#define _immediate(flags, var)						\
+({									\
+	((flags) & IF_OPTIMIZED) ?					\
+		immediate_optimized(flags, var) :			\
+		immediate_generic(flags, var);				\
+})
+
+/* immediate with default behavior */
+#define immediate(var)	 _immediate(IF_DEFAULT, var)
+
+/*
+ * Architecture dependant immediate information, used internally for immediate
+ * activation.
+ */
+
+/*
+ * Offset of the immediate value from the start of the addi instruction (result
+ * of the li mnemonic), in bytes.
+ */
+#define IMMEDIATE_OPTIMIZED_ENABLE_IMMEDIATE_OFFSET 2
+#define IMMEDIATE_OPTIMIZED_ENABLE_TYPE unsigned short
+/* Dereference enable as lvalue from a pointer to its instruction */
+#define IMMEDIATE_OPTIMIZED_ENABLE(a)					\
+	(*(IMMEDIATE_OPTIMIZED_ENABLE_TYPE*)				\
+		((char*)(a)+IMMEDIATE_OPTIMIZED_ENABLE_IMMEDIATE_OFFSET))
+
+extern int immediate_optimized_set_enable(void *address, char enable);
+
+#endif /* _ASM_POWERPC_IMMEDIATE_H */
arch/powerpc/kernel/Makefile +1 -0
Index: linux-2.6-lttng/arch/powerpc/kernel/Makefile
===================================================================
@@ -96,3 +96,4 @@
 
 extra-$(CONFIG_PPC_FPU)		+= fpu.o
 extra-$(CONFIG_PPC64)		+= entry_64.o
+obj-$(CONFIG_IMMEDIATE)		+= immediate.o
arch/powerpc/kernel/immediate.c new file +29 -0
Index: linux-2.6-lttng/arch/powerpc/kernel/immediate.c
===================================================================
@@ -0,0 +1,29 @@
+/*
+ * Powerpc optimized immediate values enabling/disabling.
+ *
+ * Mathieu Desnoyers <[email protected]>
+ */
+
+#include <linux/module.h>
+#include <linux/immediate.h>
+#include <linux/string.h>
+#include <asm/cacheflush.h>
+#include <asm/page.h>
+
+/*
+ * The address is aligned on 4 bytes boundary: the 4 bytes instruction we are
+ * changing fits within one page.
+ */
+int immediate_optimized_set_enable(void *address, char enable)
+{
+	char newi[IMMEDIATE_OPTIMIZED_ENABLE_IMMEDIATE_OFFSET+1];
+	int size = IMMEDIATE_OPTIMIZED_ENABLE_IMMEDIATE_OFFSET
+			+ sizeof(IMMEDIATE_OPTIMIZED_ENABLE_TYPE);
+
+	memcpy(newi, address, size);
+	IMMEDIATE_OPTIMIZED_ENABLE(&newi[0]) = enable;
+	memcpy(address, newi, size);
+	flush_icache_range((unsigned long)address, size);
+	return 0;
+}
+EXPORT_SYMBOL_GPL(immediate_optimized_set_enable);
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#16 lore raw

PATCH 8/10 Immediate Value - Documentation

In reply to Mathieu Desnoyers
---
 Documentation/immediate.txt |  103 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 103 insertions(+)
Documentation/immediate.txt new file +103 -0
Index: linux-2.6-lttng/Documentation/immediate.txt
===================================================================
@@ -0,0 +1,103 @@
+		        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 a branch that is disabled
+at compile-time that has almost no measurable performance impact on the kernel.
+Then, at runtime, it can be enabled dynamically.
+
+It can be used to compile code in the kernel that is seldomly meant to be
+dynamically activated. It's the case of CPU specific workarounds, profiling,
+tracing, etc.
+
+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.
+
+
+* Usage
+
+In order to use the macro immediate, you should include linux/immediate.h.
+
+#include <linux/immediate.h>
+
+immediate_t __read_mostly this_immediate;
+EXPORT_SYMBOL(this_immediate);
+
+
+Add, in your code :
+
+if (unlikely(immediate(this_immediate))) {
+	some code...
+}
+
+And then, use:
+
+Use immediate_arm(&this_immediate) to activate the immediate value.
+
+Use immediate_disarm(&this_immediate) to deactivate the immediate value.
+
+Use immediate_query(&this_immediate) to query the immediate value state.
+
+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.
+
+
+* Optimization for a given architecture
+
+One can implement optimized immediate values for a given architecture by
+replacing asm-$ARCH/immediate.h.
+
+The IF_* flags can be used to control the type of immediate value. See the
+include/linux/immediate.h header for the list of flags. They can be specified as
+the first parameter of the _immediate() macro, as in the following example,
+which uses flags to declare a immediate that always uses the generic version of
+the immediates. It can be useful to use this when immediates are placed in
+kernel code presenting particular reentrancy challenges.
+
+if (unlikely(_immediate(IF_DEFAULT & ~IF_OPTIMIZED, this_immediate))) {
+	some code...
+}
+
+
+* Performance improvement
+
+Result of a small test comparing:
+
+1 - Branch depending on a cache miss (has to fetch in memory, caused by a 128
+    bytes stride)). This is the test that is likely to look like what
+    side-effect the original profile_hit code was causing, under the
+    assumption that the kernel is already using L1 and L2 caches at
+    their full capacity and that a supplementary data load would cause
+    cache trashing.
+2 - Branch depending on L1 cache hit. Just for comparison.
+3 - Branch depending on a load immediate in the instruction stream.
+
+It has been compiled with gcc -O2. Tests done on a 3GHz P4.
+
+In the first test series, the branch is not taken:
+
+number of tests : 1000
+number of branches per test : 81920
+memory hit cycles per iteration (mean) : 48.252
+L1 cache hit cycles per iteration (mean) : 16.1693
+instruction stream based test, cycles per iteration (mean) : 16.0432
+
+
+In the second test series, the branch is taken and an integer is
+incremented within the block:
+
+number of tests : 1000
+number of branches per test : 81920
+memory hit cycles per iteration (mean) : 48.2691
+L1 cache hit cycles per iteration (mean) : 16.396
+instruction stream based test, cycles per iteration (mean) : 16.0441
+
+Therefore, the memory fetch based test seems to be 200% slower than the
+load immediate based test.
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#17 lore raw

PATCH 9/10 F00F bug fixup for i386 - use immediate values

In reply to Mathieu Desnoyers

Use the faster immediate values for F00F bug handling in do_page_fault.

---
 arch/i386/kernel/traps.c     |    4 ++++
 arch/i386/mm/fault.c         |    3 ++-
 include/asm-i386/processor.h |    3 +++
 3 files changed, 9 insertions(+), 1 deletion(-)
arch/i386/kernel/traps.c +4 -0
Index: linux-2.6-lttng/arch/i386/kernel/traps.c
===================================================================
@@ -31,6 +31,7 @@
 #include <linux/uaccess.h>
 #include <linux/nmi.h>
 #include <linux/bug.h>
+#include <linux/immediate.h>
 
 #ifdef CONFIG_EISA
 #include <linux/ioport.h>
@@ -1149,6 +1150,8 @@
 #endif /* CONFIG_MATH_EMULATION */
 
 #ifdef CONFIG_X86_F00F_BUG
+immediate_t __read_mostly f00f_bug_fix;
+
 void __init trap_init_f00f_bug(void)
 {
 	__set_fixmap(FIX_F00F_IDT, __pa(&idt_table), PAGE_KERNEL_RO);
@@ -1159,6 +1162,7 @@
 	 */
 	idt_descr.address = fix_to_virt(FIX_F00F_IDT);
 	load_idt(&idt_descr);
+	immediate_arm(&f00f_bug_fix);
 }
 #endif
 
arch/i386/mm/fault.c +2 -1
Index: linux-2.6-lttng/arch/i386/mm/fault.c
===================================================================
@@ -25,6 +25,7 @@
 #include <linux/kprobes.h>
 #include <linux/uaccess.h>
 #include <linux/kdebug.h>
+#include <linux/immediate.h>
 
 #include <asm/system.h>
 #include <asm/desc.h>
@@ -477,7 +478,7 @@
 	/*
 	 * Pentium F0 0F C7 C8 bug workaround.
 	 */
-	if (boot_cpu_data.f00f_bug) {
+	if (unlikely(immediate(f00f_bug_fix))) {
 		unsigned long nr;
 		
 		nr = (address - idt_descr.address) >> 3;
include/asm-i386/processor.h +3 -0
Index: linux-2.6-lttng/include/asm-i386/processor.h
===================================================================
@@ -21,6 +21,7 @@
 #include <asm/percpu.h>
 #include <linux/cpumask.h>
 #include <linux/init.h>
+#include <linux/immediate.h>
 #include <asm/processor-flags.h>
 
 /* flag for disabling the tsc */
@@ -102,6 +103,8 @@
 extern struct tss_struct doublefault_tss;
 DECLARE_PER_CPU(struct tss_struct, init_tss);
 
+extern immediate_t __read_mostly f00f_bug_fix;
+
 #ifdef CONFIG_SMP
 extern struct cpuinfo_x86 cpu_data[];
 #define current_cpu_data cpu_data[smp_processor_id()]
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#18 lore raw

Re: [patch 09/10] F00F bug fixup for i386 - use immediate values

Quoted 13 lines · Mathieu Desnoyers

Use the faster immediate values for F00F bug handling in do_page_fault.

arch/i386/mm/fault.c +1 -0
@@ -25,6 +25,7 @@
 #include <linux/kprobes.h>
 #include <linux/uaccess.h>
 #include <linux/kdebug.h>
+#include <linux/immediate.h>
 
 #include <asm/system.h>
 #include <asm/desc.h>

arch/i386/mm/fault.c line 481

Quoted 5 lines
arch/i386/mm/fault.c +1 -1
@@ -477,7 +478,7 @@
 	/*
 	 * Pentium F0 0F C7 C8 bug workaround.
 	 */
-	if (boot_cpu_data.f00f_bug) {
+	if (unlikely(immediate(f00f_bug_fix))) {

As I understand it, this never triggers in normal valid and invalid pagefaults, because even invalid userspace pagefaults take branch slightly earlier where catch SIGSEGV. Nobody cares about performance if you reach this branch.

#19 lore raw

PATCH 10/10 Scheduler profiling - Use immediate values

In reply to Mathieu Desnoyers

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

---
 drivers/kvm/svm.c       |    2 +-
 drivers/kvm/vmx.c       |    2 +-
 include/linux/profile.h |    9 +++------
 kernel/profile.c        |   37 +++++++++++++++++++++++++------------
 kernel/sched.c          |    3 ++-
 5 files changed, 32 insertions(+), 21 deletions(-)
kernel/profile.c +25 -12
Index: linux-2.6-lttng/kernel/profile.c
===================================================================
@@ -23,6 +23,7 @@
 #include <linux/profile.h>
 #include <linux/highmem.h>
 #include <linux/mutex.h>
+#include <linux/immediate.h>
 #include <asm/sections.h>
 #include <asm/semaphore.h>
 #include <asm/irq_regs.h>
@@ -42,9 +43,6 @@
 static atomic_t *prof_buffer;
 static unsigned long prof_len, prof_shift;
 
-int prof_on __read_mostly;
-EXPORT_SYMBOL_GPL(prof_on);
-
 static cpumask_t prof_cpu_mask = CPU_MASK_ALL;
 #ifdef CONFIG_SMP
 static DEFINE_PER_CPU(struct profile_hit *[2], cpu_profile_hits);
@@ -52,6 +50,12 @@
 static DEFINE_MUTEX(profile_flip_mutex);
 #endif /* CONFIG_SMP */
 
+/* Immediate values */
+immediate_t __read_mostly sleep_profiling, sched_profiling, kvm_profiling,
+	cpu_profiling;
+EXPORT_SYMBOL_GPL(kvm_profiling);
+EXPORT_SYMBOL_GPL(cpu_profiling);
+
 static int __init profile_setup(char * str)
 {
 	static char __initdata schedstr[] = "schedule";
@@ -60,7 +64,7 @@
 	int par;
 
 	if (!strncmp(str, sleepstr, strlen(sleepstr))) {
-		prof_on = SLEEP_PROFILING;
+		immediate_arm(&sleep_profiling);
 		if (str[strlen(sleepstr)] == ',')
 			str += strlen(sleepstr) + 1;
 		if (get_option(&str, &par))
@@ -69,7 +73,7 @@
 			"kernel sleep profiling enabled (shift: %ld)\n",
 			prof_shift);
 	} else if (!strncmp(str, schedstr, strlen(schedstr))) {
-		prof_on = SCHED_PROFILING;
+		immediate_arm(&sched_profiling);
 		if (str[strlen(schedstr)] == ',')
 			str += strlen(schedstr) + 1;
 		if (get_option(&str, &par))
@@ -78,7 +82,7 @@
 			"kernel schedule profiling enabled (shift: %ld)\n",
 			prof_shift);
 	} else if (!strncmp(str, kvmstr, strlen(kvmstr))) {
-		prof_on = KVM_PROFILING;
+		immediate_arm(&kvm_profiling);
 		if (str[strlen(kvmstr)] == ',')
 			str += strlen(kvmstr) + 1;
 		if (get_option(&str, &par))
@@ -88,7 +92,7 @@
 			prof_shift);
 	} else if (get_option(&str, &par)) {
 		prof_shift = par;
-		prof_on = CPU_PROFILING;
+		immediate_arm(&cpu_profiling);
 		printk(KERN_INFO "kernel profiling enabled (shift: %ld)\n",
 			prof_shift);
 	}
@@ -99,7 +103,10 @@
 
 void __init profile_init(void)
 {
-	if (!prof_on) 
+	if (!immediate_query(&sleep_profiling) &&
+		!immediate_query(&sched_profiling) &&
+		!immediate_query(&kvm_profiling) &&
+		!immediate_query(&cpu_profiling))
 		return;
  
 	/* only text is profiled */
@@ -288,7 +295,7 @@
 	int i, j, cpu;
 	struct profile_hit *hits;
 
-	if (prof_on != type || !prof_buffer)
+	if (!prof_buffer)
 		return;
 	pc = min((pc - (unsigned long)_stext) >> prof_shift, prof_len - 1);
 	i = primary = (pc & (NR_PROFILE_GRP - 1)) << PROFILE_GRPSHIFT;
@@ -398,7 +405,7 @@
 {
 	unsigned long pc;
 
-	if (prof_on != type || !prof_buffer)
+	if (!prof_buffer)
 		return;
 	pc = ((unsigned long)__pc - (unsigned long)_stext) >> prof_shift;
 	atomic_add(nr_hits, &prof_buffer[min(pc, prof_len - 1)]);
@@ -555,7 +562,10 @@
 	}
 	return 0;
 out_cleanup:
-	prof_on = 0;
+	immediate_disarm(&sleep_profiling);
+	immediate_disarm(&sched_profiling);
+	immediate_disarm(&kvm_profiling);
+	immediate_disarm(&cpu_profiling);
 	smp_mb();
 	on_each_cpu(profile_nop, NULL, 0, 1);
 	for_each_online_cpu(cpu) {
@@ -582,7 +592,10 @@
 {
 	struct proc_dir_entry *entry;
 
-	if (!prof_on)
+	if (!immediate_query(&sleep_profiling) &&
+		!immediate_query(&sched_profiling) &&
+		!immediate_query(&kvm_profiling) &&
+		!immediate_query(&cpu_profiling))
 		return 0;
 	if (create_hash_tables())
 		return -1;
include/linux/profile.h +3 -6
Index: linux-2.6-lttng/include/linux/profile.h
===================================================================
@@ -10,7 +10,8 @@
 
 #include <asm/errno.h>
 
-extern int prof_on __read_mostly;
+extern immediate_t __read_mostly sleep_profiling, sched_profiling, kvm_profiling,
+		cpu_profiling;
 
 #define CPU_PROFILING	1
 #define SCHED_PROFILING	2
@@ -35,11 +36,7 @@
  */
 static inline void profile_hit(int type, void *ip)
 {
-	/*
-	 * Speedup for the common (no profiling enabled) case:
-	 */
-	if (unlikely(prof_on == type))
-		profile_hits(type, ip, 1);
+	profile_hits(type, ip, 1);
 }
 
 #ifdef CONFIG_PROC_FS
kernel/sched.c +2 -1
Index: linux-2.6-lttng/kernel/sched.c
===================================================================
@@ -3241,7 +3241,8 @@
 	if (unlikely(in_atomic_preempt_off()) && unlikely(!prev->exit_state))
 		__schedule_bug(prev);
 
-	profile_hit(SCHED_PROFILING, __builtin_return_address(0));
+	if (unlikely(immediate(sched_profiling)))
+		profile_hit(SCHED_PROFILING, __builtin_return_address(0));
 
 	schedstat_inc(this_rq(), sched_cnt);
 }
drivers/kvm/svm.c +1 -1
Index: linux-2.6-lttng/drivers/kvm/svm.c
===================================================================
@@ -1654,7 +1654,7 @@
 	/*
 	 * Profile KVM exit RIPs:
 	 */
-	if (unlikely(prof_on == KVM_PROFILING))
+	if (unlikely(immediate(kvm_profiling)))
 		profile_hit(KVM_PROFILING,
 			(void *)(unsigned long)vcpu->svm->vmcb->save.rip);
 
drivers/kvm/vmx.c +1 -1
Index: linux-2.6-lttng/drivers/kvm/vmx.c
===================================================================
@@ -2156,7 +2156,7 @@
 	/*
 	 * Profile KVM exit RIPs:
 	 */
-	if (unlikely(prof_on == KVM_PROFILING))
+	if (unlikely(immediate(kvm_profiling)))
 		profile_hit(KVM_PROFILING, (void *)vmcs_readl(GUEST_RIP));
 
 	vcpu->launched = 1;
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#20 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 2 lines · Mathieu Desnoyers

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

How much difference in performance do you see?

#21 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 6 lines · * Alexey Dobriyan ([email protected]) wrote:
Quoted 2 lines · Mathieu Desnoyers

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

How much difference in performance do you see?

Hi Alexey,

Please have a look at Documentation/immediate.txt for that information. Also note that the main advantage of the load immediate is to free a cache line. Therefore, I guess the best way to quantify the improvement it brings at one single site is not in terms of cycles, but in terms of number of cache lines used by the scheduler code. Since memory bandwidth seems to be an increasing bottleneck (CPU frequency increases faster than the available memory bandwidth), it makes sense to free as much cache lines as we can.

Measuring the overall impact on the system of this single modification results in the difference brought by one site within the standard deviation of the normal samples. It will become significant when the number of immediate values used instead of global variables at hot kernel paths (need to ponder with the frequency at which the data is accessed) will start to be significant compared to the L1 data cache size. We could characterize this in memory to L1 cache transfers per seconds.

On 3GHz P4:

memory read: ~48 cycles

So we can definitely say that 48*HZ (approximation of the frequency at which the scheduler is called) won't make much difference, but as it grows, it will.

On a 1000HZ system, it results in:

48000 cycles/second, or 16µs/second, or 0.000016% speedup.

However, if we place this in code called much more often, such as do_page_fault, we get, with an hypotetical scenario of approximation of 100000 page faults per second:

4800000 cycles/s, 1.6ms/second or 0.0016% speedup.

So as the number of immediate values used increase, the overall memory bandwidth required by the kernel will go down.

Mathieu

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 40 lines · Mathieu Desnoyers
Quoted 6 lines · * Alexey Dobriyan ([email protected]) wrote:
Quoted 2 lines · Mathieu Desnoyers

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

How much difference in performance do you see?

Hi Alexey,

Please have a look at Documentation/immediate.txt for that information. Also note that the main advantage of the load immediate is to free a cache line. Therefore, I guess the best way to quantify the improvement it brings at one single site is not in terms of cycles, but in terms of number of cache lines used by the scheduler code. Since memory bandwidth seems to be an increasing bottleneck (CPU frequency increases faster than the available memory bandwidth), it makes sense to free as much cache lines as we can.

Measuring the overall impact on the system of this single modification results in the difference brought by one site within the standard deviation of the normal samples. It will become significant when the number of immediate values used instead of global variables at hot kernel paths (need to ponder with the frequency at which the data is accessed) will start to be significant compared to the L1 data cache size. We could characterize this in memory to L1 cache transfers per seconds.

On 3GHz P4:

memory read: ~48 cycles

So we can definitely say that 48*HZ (approximation of the frequency at which the scheduler is called) won't make much difference, but as it grows, it will.

On a 1000HZ system, it results in:

48000 cycles/second, or 16µs/second, or 0.000016% speedup.

Quoted 8 lines

However, if we place this in code called much more often, such as do_page_fault, we get, with an hypotetical scenario of approximation of 100000 page faults per second:

4800000 cycles/s, 1.6ms/second or 0.0016% speedup.

So as the number of immediate values used increase, the overall memory bandwidth required by the kernel will go down.

Might make a nice scientific paper, but even according to your own optimistic numbers it's not realistic that you will ever achieve any visible improvement even if you'd find 100 places in hotpaths you could mark this way.

And a better direction for hotpaths seems to be Andi's __cold/COLD in -mm without adding an own framework for doing such things.

Quoted 1 line

Mathieu

cu
Adrian

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

In reply to Mathieu Desnoyers
Quoted 19 lines · Mathieu Desnoyers
Quoted 6 lines · * Alexey Dobriyan ([email protected]) wrote:
Quoted 2 lines · Mathieu Desnoyers

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

How much difference in performance do you see?

Hi Alexey,

Please have a look at Documentation/immediate.txt for that information. Also note that the main advantage of the load immediate is to free a cache line. Therefore, I guess the best way to quantify the improvement it brings at one single site is not in terms of cycles, but in terms of number of cache lines used by the scheduler code. Since memory bandwidth seems to be an increasing bottleneck (CPU frequency increases faster than the available memory bandwidth), it makes sense to free as much cache lines as we can.

Quoted 7 lines

Measuring the overall impact on the system of this single modification results in the difference brought by one site within the standard deviation of the normal samples. It will become significant when the number of immediate values used instead of global variables at hot kernel paths (need to ponder with the frequency at which the data is accessed) will start to be significant compared to the L1 data cache size.

L1 cache is 8K here. Just how many such variables should exist? On hot paths!

Quoted 15 lines

We could characterize this in memory to L1 cache transfers per seconds.

On 3GHz P4:

memory read: ~48 cycles

So we can definitely say that 48*HZ (approximation of the frequency at which the scheduler is called) won't make much difference, but as it grows, it will.

On a 1000HZ system, it results in:

48000 cycles/second, or 16µs/second, or 0.000016% speedup.

Quoted 8 lines

However, if we place this in code called much more often, such as do_page_fault, we get, with an hypotetical scenario of approximation of 100000 page faults per second:

4800000 cycles/s, 1.6ms/second or 0.0016% speedup.

So as the number of immediate values used increase, the overall memory bandwidth required by the kernel will go down.

Adding so many infrastructure for something that you can't even measure is totally unjustified.

There are already too many places where unlikely() and __read_mostly are used just because they can be used, so adding yet another such very specific, let's call it annotation, seems wrong to me.

#24 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

In reply to Mathieu Desnoyers
Quoted 21 lines · On Tue, 3 Jul 2007 14:57:48 -0400 Mathieu Desnoyers…

Measuring the overall impact on the system of this single modification results in the difference brought by one site within the standard deviation of the normal samples. It will become significant when the number of immediate values used instead of global variables at hot kernel paths (need to ponder with the frequency at which the data is accessed) will start to be significant compared to the L1 data cache size. We could characterize this in memory to L1 cache transfers per seconds.

On 3GHz P4:

memory read: ~48 cycles

So we can definitely say that 48*HZ (approximation of the frequency at which the scheduler is called) won't make much difference, but as it grows, it will.

On a 1000HZ system, it results in:

48000 cycles/second, or 16__s/second, or 0.000016% speedup.

Quoted 8 lines

However, if we place this in code called much more often, such as do_page_fault, we get, with an hypotetical scenario of approximation of 100000 page faults per second:

4800000 cycles/s, 1.6ms/second or 0.0016% speedup.

So as the number of immediate values used increase, the overall memory bandwidth required by the kernel will go down.

Is that 48 cycles measured when the target of the read is in L1 cache, as it would be in any situation which we actually care about? I guess so...

Boy, this is a tiny optimisation and boy, you added a pile of tricky new code to obtain it.

Frankly, I'm thinking that life would be simpler if we just added static markers and stopped trying to add lots of tricksy maintenance-load-increasing things like this.

Ho hum. Need more convincing, please.

Also: a while back (maybe as much as a year) we had an extensive discussion regarding whether we want static markers at all in the kernel. The eventual outcome was, I believe, "yes".

But our reasons for making that decision appear to have been lost. So if I were to send the markers patches to Linus and he were to ask me "why are you sending these", I'd be forced to answer "I don't know". This is not a good situation.

Please prepare and maintain a short document which describes the justification for making all these changes to the kernel. The changelog for the main markers patch wold be an appropriate place for this. The target audience would be kernel developers and it should capture the pro- and con- arguments which were raised during that discussion.

Bascially: tell us why we should merge _any_ of this stuff, because I for one have forgotten. Thanks.

#25 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 2 lines · On Thu, 5 Jul 2007 13:21:20 -0700 Andrew Morton <[email protected]>…

Please prepare and maintain a short document which describes the justification for making all these changes to the kernel.

oh, you did. It's there in the add-kconfig-stuff patch.

#26 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 7 lines · * Andrew Morton ([email protected]) wrote:
Quoted 2 lines · On Thu, 5 Jul 2007 13:21:20 -0700 Andrew Morton <[email protected]>…

Please prepare and maintain a short document which describes the justification for making all these changes to the kernel.

oh, you did. It's there in the add-kconfig-stuff patch.

Yes, if you feel it should be put in a different patch header, I'll move it.

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

In reply to Andrew Morton
Quoted 2 lines · Andrew Morton

Is that 48 cycles measured when the target of the read is in L1 cache, as it would be in any situation which we actually care about? I guess so...

The normal situation is big database or other bloated software runs; clears all the dcaches, then enters kernel. Kernel has a cache miss on all its data. But icache access is faster because the CPU prefetches.

We've had cases like this -- e.g. the additional dcache line accesses that were added by the new time code in vgettimeofday() were visible in macro benchmarks.

Also cache misses in this situation tend to be much more than 48 cycles (even an K8 with integrated memory controller with fastest DIMMs is slower than that) Mathieu probably measured an L2 miss, not a load from RAM. Load from RAM can be hundreds of ns in the worst case.

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

-Andi

#28 lore raw

RE: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 1 line

Also cache misses in this situation tend to be much more than 48

cycles

Quoted 2 lines

(even an K8 with integrated memory controller with fastest DIMMs is slower than that) Mathieu probably measured an L2 miss, not a load

from

Quoted 3 lines

RAM.
Load from RAM can be hundreds of ns in the worst case.

The 48 cycles sounds to me like a memory load in an unloaded system, but it is quite low. I wonder how it was measured...

tong

#29 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 4 lines · Tong N
Quoted 1 line

Also cache misses in this situation tend to be much more than 48

cycles

Quoted 2 lines

(even an K8 with integrated memory controller with fastest DIMMs is slower than that) Mathieu probably measured an L2 miss, not a load

                                                    ^^^^^^^

I meant L2 cache hit of course

Quoted 7 lines

from

Quoted 3 lines

RAM.
Load from RAM can be hundreds of ns in the worst case.

The 48 cycles sounds to me like a memory load in an unloaded system, but it is quite low. I wonder how it was measured...

I found that memory latency is difficult to measure in modern x86 CPUs because they have very clever prefetchers that can often outwit benchmarks.

Another trap on P4 is that RDTSC is actually quite slow and synchronizes the CPU; that can add large measurement errors.

-Andi

#30 lore raw

RE: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 3 lines

I found that memory latency is difficult to measure in modern x86 CPUs because they have very clever prefetchers that can often outwit benchmarks.

A pointer-chasing program that accesses a random sequence of addresses usually can produce a good estimate on memory latency. Also, prefetching can be turned off in BIOS or by modifying the MSRs.

Quoted 1 line

Another trap on P4 is that RDTSC is actually quite slow and

synchronizes

Quoted 3 lines

the CPU; that can add large measurement errors.

-Andi

The cost can be amortized if the portion of memory accesses is long enough.

tong

#31 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 10 lines · * Li, Tong N ([email protected]) wrote:
Quoted 3 lines

I found that memory latency is difficult to measure in modern x86 CPUs because they have very clever prefetchers that can often outwit benchmarks.

A pointer-chasing program that accesses a random sequence of addresses usually can produce a good estimate on memory latency. Also, prefetching can be turned off in BIOS or by modifying the MSRs.

Quoted 1 line

Another trap on P4 is that RDTSC is actually quite slow and

synchronizes

Quoted 9 lines
Quoted 3 lines

the CPU; that can add large measurement errors.

-Andi

The cost can be amortized if the portion of memory accesses is long enough.

tong

That's what I am currently doing.. the results are coming in a few moments... :)

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

Re: [patch 10/10] *Tests* Scheduler profiling - Use immediate values

In reply to Li, Tong N
Quoted 5 lines · * Li, Tong N ([email protected]) wrote:
Quoted 1 line

Also cache misses in this situation tend to be much more than 48

cycles

Quoted 2 lines

(even an K8 with integrated memory controller with fastest DIMMs is slower than that) Mathieu probably measured an L2 miss, not a load

from

Quoted 9 lines
Quoted 3 lines

RAM.
Load from RAM can be hundreds of ns in the worst case.

The 48 cycles sounds to me like a memory load in an unloaded system, but it is quite low. I wonder how it was measured...

tong

Ah, excellent point.

I just re-read through my test case, and I modified it so it initializes the memory first, instead of using the zero page, and now does a pseudo-random walk instead of going through the L2 cache lines sequentially... that will help. Especially since the memory is dual channel and the cpu does some prefetching. The code follows this email for easier review and test.

I also did a test that characterize the speed impact of my LTTng marker set in both scenarios with a memory I/O hungry program, also provided below.

* Memory hit for a data-based branch

Here are the results now, on my 3GHz Pentium 4:

number of tests : 100
number of branches per test : 100000
memory hit cycles per iteration (mean) : 636.611
L1 cache hit cycles per iteration (mean) : 89.6413 instruction stream based test, cycles per iteration (mean) : 85.3438 Just getting the pointer from a modulo on a pseudo-random value, doing
noting with it, cycles per iteration (mean) : 77.5044

So:

Base case:                      77.50 cycles
instruction stream based test:  +7.8394 cycles
L1 cache hit based test:        +12.1369 cycles
Memory load based test:         +559.1066 cycles

So let's say we have a ping flood coming at
(14014 packets transmitted, 14014 received, 0% packet loss, time 1826ms) 7674 packets per second. If we put 2 markers for irq entry/exit, it brings us to 15348 markers sites executed per second.

(15348 exec/s) * (559 cycles/exec) / (3G cycles/s) = 0.0029 We therefore have a 0.29% slowdown just on this case.

Compared to this, the instruction stream based test will cause a slowdown of:

(15348 exec/s) * (7.84 cycles/exec) / (3G cycles/s) = 0.00004 For a 0.004% slowdown.

If we plan to use this for memory allocation, spinlock, and all sort of very high event rate tracing, we can assume it will execute 10 to 100 times more sites per second, which brings us to 0.4% slowdown with the instruction stream based test compared to 29% slowdown with the memory load based test on a system with high memory pressure.

* Markers impact under heavy memory load

Running a kernel with my LTTng instrumentation set, in a test that generates memory pressure (from userspace) by trashing L1 and L2 caches between calls to getppid() (note: syscall_trace is active and calls a marker upon syscall entry and syscall exit; markers are disarmed). This test is done in user-space, so there are some delays due to IRQs coming and to the scheduler. (UP 2.6.22-rc6-mm1 kernel, task with -20 nice level)

My first set of results : Linear cache trashing, turned out not to be very interesting, because it seems like the linearity of the memset on a full array is somehow detected and it does not "really" trash the caches.

Now the most interesting result : Random walk L1 and L2 trashing surrounding a getppid() call.

- Markers compiled out (but syscall_trace execution forced) number of tests : 10000
No memory pressure
Reading timestamps takes 108.033 cycles
getppid : 1681.4 cycles
With memory pressure
Reading timestamps takes 102.938 cycles
getppid : 15691.6 cycles

- With the immediate values based markers:
number of tests : 10000
No memory pressure
Reading timestamps takes 108.006 cycles
getppid : 1681.84 cycles
With memory pressure
Reading timestamps takes 100.291 cycles
getppid : 11793 cycles

- With global variables based markers:
number of tests : 10000
No memory pressure
Reading timestamps takes 107.999 cycles
getppid : 1669.06 cycles
With memory pressure
Reading timestamps takes 102.839 cycles
getppid : 12535 cycles

The result is quite interesting in that the kernel is slower without markers than with markers. I explain it by the fact that the data accessed is not layed out in the same manner in the cache lines when the markers are compiled in or out. It seems that it aligns the function's data better to compile-in the markers in this case.

But since the interesting comparison is between the immediate values and global variables based markers, and because they share the same memory layout, except for the movl being replaced by a movz, we see that the global variable based markers (2 markers) adds 742 cycles to each system call (syscall entry and exit are traced and memory locations for both global variables lie on the same cache line).

Therefore, not only is it interesting to use the immediate values to dynamically activate dormant code such as the markers, but I think it should also be considered as a replacement for many of the "read mostly" static variables.

Mathieu

Testing memory timings, in user-space:
----------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long cycles_t;

#define barrier() __asm__ __volatile__("": : :"memory")

#define rdtsc(low,high) \
     __asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high))
#define rdtscl(low) \
     __asm__ __volatile__("rdtsc" : "=a" (low) : : "edx")
#define rdtscll(val) \
     __asm__ __volatile__("rdtsc" : "=A" (val))

static inline cycles_t get_cycles(void)

{
	unsigned long long ret = 0;

	barrier();
	rdtscll(ret);
	barrier();
	return ret;
}

#define L1_CACHELINE_SIZE 64
#define L2_CACHELINE_SIZE 128
#define ARRAY_SIZE 524288000

#define NR_TESTS 100
#define NR_ITER 100000

char array[ARRAY_SIZE];
unsigned int glob = 0;

int main(int argc, char **argv)

{
	char *testval;
	cycles_t time1, time2;
	double cycles_per_iter;
	unsigned int i, j;

	srandom(get_cycles());

	printf("number of tests : %lu\n", NR_TESTS);
	printf("number of branches per test : %lu\n", NR_ITER);

	memset(array, 0, ARRAY_SIZE);

	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		time1 = get_cycles();
		for (j = 0; j < NR_ITER; j++) {
			testval = &array[random() % ARRAY_SIZE];
			if (*testval)
				glob++;
		}
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1)/(double)NR_ITER;
	}
	cycles_per_iter /= (double)NR_TESTS;
	printf("memory hit cycles per iteration (mean) : %g\n", cycles_per_iter);

	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		testval = &array[random() % L1_CACHELINE_SIZE];
		if (*testval)
			glob++;
		time1 = get_cycles();
		for (j = 0; j < NR_ITER; j++) {
			testval = &array[random() % L1_CACHELINE_SIZE];
			if (*testval)
				glob++;
		}
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1)/(double)NR_ITER;
	}
	cycles_per_iter /= (double)NR_TESTS;
	printf("L1 cache hit cycles per iteration (mean) : %g\n", cycles_per_iter);

	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		time1 = get_cycles();
		for (j = 0; j < NR_ITER; j++) {
			char condition;
			asm (			".align 2\n\t"
						"0:\n\t"
						"movb %1,%0;\n\t"
					: "=r" (condition)
					: "i" (0));
				testval = &array[random() % ARRAY_SIZE];
				if (condition)
					glob++;
		}
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1)/(double)NR_ITER;
	}
	cycles_per_iter /= (double)NR_TESTS;
	printf("instruction stream based test, cycles per iteration (mean) : %g\n", cycles_per_iter);

	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		time1 = get_cycles();
		for (j = 0; j < NR_ITER; j++) {
			testval = &array[random() % ARRAY_SIZE];
		}
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1)/(double)NR_ITER;
	}
	cycles_per_iter /= (double)NR_TESTS;
	printf("Just getting the pointer, doing noting with it, cycles per iteration (mean) : %g\n", cycles_per_iter);

	return 0;
}

----------------------------------------------------------------------------

And here is the syscall timing under heavy memory I/O load: (gcc -O2)
----------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>

typedef unsigned long long cycles_t;

#define barrier() __asm__ __volatile__("": : :"memory")

#define rdtsc(low,high) \
     __asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high))
#define rdtscl(low) \
     __asm__ __volatile__("rdtsc" : "=a" (low) : : "edx")
#define rdtscll(val) \
     __asm__ __volatile__("rdtsc" : "=A" (val))

static inline cycles_t get_cycles(void)

{
	unsigned long long ret = 0;

	barrier();
	rdtscll(ret);
	barrier();
	return ret;
}

#define L1_CACHELINE_SIZE 64
#define L2_CACHELINE_SIZE 128
#define ARRAY_SIZE 1048576 /* 1 MB, size of L2 cache */

char array[ARRAY_SIZE];

#define NR_TESTS 10000

int main(int argc, char **argv)

{
	cycles_t time1, time2;
	double cycles_per_iter;
	unsigned int i, j;
	pid_t pid;

	printf("number of tests : %lu\n", NR_TESTS);

	srandom(get_cycles());

	printf("No memory pressure\n");
	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		time1 = get_cycles();
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1);
	}
	cycles_per_iter /= (double)NR_TESTS;

	printf("Reading timestamps takes %g cycles\n", cycles_per_iter);

	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		time1 = get_cycles();
		pid = getppid();
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1);
	}
	cycles_per_iter /= (double)NR_TESTS;

	printf("getppid : %g cycles\n", cycles_per_iter);

	printf("With memory pressure\n");

	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		//memset(array, 1, ARRAY_SIZE);
		for (j=0; j<ARRAY_SIZE*3; j++)
			array[random() % ARRAY_SIZE] = 1;
		time1 = get_cycles();
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1);
	}
	cycles_per_iter /= (double)NR_TESTS;

	printf("Reading timestamps takes %g cycles\n", cycles_per_iter);

	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		//memset(array, 1, ARRAY_SIZE);
		for (j=0; j<ARRAY_SIZE*3; j++)
			array[random() % ARRAY_SIZE] = 1;
		time1 = get_cycles();
		pid = getppid();
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1);
	}
	cycles_per_iter /= (double)NR_TESTS;

	printf("getppid : %g cycles\n", cycles_per_iter);

	return 0;
}

----------------------------------------------------------------------------

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

RE: [patch 10/10] *Tests* Scheduler profiling - Use immediate values

Mathieu,

Quoted 11 lines
	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		time1 = get_cycles();
		for (j = 0; j < NR_ITER; j++) {
			testval = &array[random() % ARRAY_SIZE];
		}
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1)/(double)NR_ITER;
	}
	cycles_per_iter /= (double)NR_TESTS;
	printf("Just getting the pointer, doing noting with it, cycles

per

Quoted 2 lines

iteration (mean) : %g\n", cycles_per_iter);

Some comments on the code:

1. random() is counted in cycle_per_iter, which can skew the results. You could pre-compute the random addresses and store them in an array. Then, during the actual timing, walk the array:

index = 0;
for (i = 0; i < ARRAY_SIZE; i++)

      index = *(int *)(array + index * CACHE_LINE_SIZE);

2. You may want to flush the cache before the timing starts.

3. You want to access memory at the cache-line granularity to avoid addresses falling into the same line (and thus unwanted hits).

If you do these, I expect you'll get a higher memory latency.

tong

#34 lore raw

Re: [patch 10/10] *Tests* Scheduler profiling - Use immediate values

Hi,

Quoted 23 lines · * Li, Tong N ([email protected]) wrote:

Mathieu,

Quoted 11 lines
	cycles_per_iter = 0.0;
	for (i=0; i<NR_TESTS; i++) {
		time1 = get_cycles();
		for (j = 0; j < NR_ITER; j++) {
			testval = &array[random() % ARRAY_SIZE];
		}
		time2 = get_cycles();
		cycles_per_iter += (time2 - time1)/(double)NR_ITER;
	}
	cycles_per_iter /= (double)NR_TESTS;
	printf("Just getting the pointer, doing noting with it, cycles

per

Quoted 2 lines

iteration (mean) : %g\n", cycles_per_iter);

Some comments on the code:

1. random() is counted in cycle_per_iter, which can skew the results. You could pre-compute the random addresses and store them in an array. Then, during the actual timing, walk the array:

Quoted 9 lines

index = 0;
for (i = 0; i < ARRAY_SIZE; i++)

      index = *(int *)(array + index * CACHE_LINE_SIZE);

2. You may want to flush the cache before the timing starts.

3. You want to access memory at the cache-line granularity to avoid addresses falling into the same line (and thus unwanted hits).

This is true, my test code was not perfect. Thanks for the hints. The improvements you propose will clearly accelerate my test program quite a bit, but I doubt that it will cause even higher memory latencies. Although using a random() at each memory access is slow, it should give a good enough dispersion. And since do 3 cache trashing passes in my code, I make sure that each and every cache lines are trashed. In fact, since I do multiple accesses to each cache line (as you noted in point 3), it takes more time, but makes it more certain that I hit all of them at least once.

Quoted 2 lines

If you do these, I expect you'll get a higher memory latency.

I will use these comments in my next tests, thanks. :) However, I still feel confident that the numbers I got from my run still hold.

Mathieu

Quoted 2 lines

tong

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

In reply to Andi Kleen
Quoted 4 lines · Andi Kleen

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

Another thing to consider is that there might be hundreds of these probes/tracepoints active in an instrumented kernel. The overhead adds up fast, so the gain may be worth all the pain.

#36 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 8 lines · Chuck Ebbert
Quoted 3 lines · Andi Kleen

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

Another thing to consider is that there might be hundreds of these probes/tracepoints active in an instrumented kernel. The overhead adds up fast, so the gain may be worth all the pain.

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

cu
Adrian

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 5 lines · Adrian Bunk

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

I think you're mixing up profiling and debugging. The former is
extremely valuable under production systems.

Dave

Signature · 1 line
http://www.codemonkey.org.uk
#38 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 10 lines · Dave Jones
Quoted 5 lines · Adrian Bunk

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

I think you're mixing up profiling and debugging. The former is
extremely valuable under production systems.

profiling = debugging of performance problems

My words were perhaps a bit sloppy, but profiling isn't part of normal operation and if people use a separate kernel for such purposes we don't need infrastructure for reducing performance penalties of enabled debug options.

Quoted 1 line

Dave

cu
Adrian

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 2 lines · Adrian Bunk

[...]
profiling = debugging of performance problems

Indeed.

Quoted 4 lines

My words were perhaps a bit sloppy, but profiling isn't part of normal operation and if people use a separate kernel for such purposes we don't need infrastructure for reducing performance penalties of enabled debug options.

Things are not so simple. One might not know that one has a performance problem until one tries some analysis tools. Rebooting into different kernels just to investigate does not work generally:
the erroneous phenomenon may have been short lived; the debug kernel, being "only" for debugging, may not be well tested => sufficiently trustworthy.

Your question asking for an actual performance impact of dormant hooks is OTOH entirely legitimate. It clearly depends on the placement of those hooks and thus their encounter rate, more so than their underlying technology (markers with whatever optimizations). If the cost is small enough, you will likely find that people will be willing to pay a small fraction of average performance, in order to eke out large gains when finding occasional e.g. algorithmic bugs.

- FChE

#40 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 12 lines · Frank Ch. Eigler
Quoted 2 lines · Adrian Bunk

[...]
profiling = debugging of performance problems

Indeed.

Quoted 4 lines

My words were perhaps a bit sloppy, but profiling isn't part of normal operation and if people use a separate kernel for such purposes we don't need infrastructure for reducing performance penalties of enabled debug options.

Quoted 6 lines

Things are not so simple. One might not know that one has a performance problem until one tries some analysis tools. Rebooting into different kernels just to investigate does not work generally:
the erroneous phenomenon may have been short lived; the debug kernel, being "only" for debugging, may not be well tested => sufficiently trustworthy.

I'm not getting this:

You'll only start looking into an analysis tool if you have a performance problem, IOW if you are not satisfied with the performance.

And the debug code will not have been tested on this machine no matter whether it's enabled through a compile option or at runtime.

Quoted 7 lines

Your question asking for an actual performance impact of dormant hooks is OTOH entirely legitimate. It clearly depends on the placement of those hooks and thus their encounter rate, more so than their underlying technology (markers with whatever optimizations). If the cost is small enough, you will likely find that people will be willing to pay a small fraction of average performance, in order to eke out large gains when finding occasional e.g. algorithmic bugs.

If you might be able to get a big part of tracing and other debug code enabled with a performance penalty of a few percent of _kernel_ performance, then you might get much debugging aid without any effective impact on application performance.

You always have to decide between some debug code and some small bit of performance. There's a reason why options to disable things like BUG() or printk() are in the kernel config menus hidden behind CONFIG_EMBEDDED although they obviously have some performance impact.

Quoted 1 line

- FChE

cu
Adrian

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 20 lines · Adrian Bunk
Quoted 12 lines · Frank Ch. Eigler
Quoted 2 lines · Adrian Bunk

[...]
profiling = debugging of performance problems

Indeed.

Quoted 4 lines

My words were perhaps a bit sloppy, but profiling isn't part of normal operation and if people use a separate kernel for such purposes we don't need infrastructure for reducing performance penalties of enabled debug options.

Quoted 6 lines

Things are not so simple. One might not know that one has a performance problem until one tries some analysis tools. Rebooting into different kernels just to investigate does not work generally:
the erroneous phenomenon may have been short lived; the debug kernel, being "only" for debugging, may not be well tested => sufficiently trustworthy.

Quoted 7 lines

I'm not getting this:

You'll only start looking into an analysis tool if you have a performance problem, IOW if you are not satisfied with the performance.

And the debug code will not have been tested on this machine no matter whether it's enabled through a compile option or at runtime.

At least all the rest of the code will be untouched and you will not have to reboot the machine. If you reboot to another kernel, nothing ensures that you will have the same code sequences (in fact, gcc will reorder some parts of code such as loops just because of an additional 'if'). So you know that the non-debug code you run will remain untouched. *This* is important, because the debug code is not there to debug itself, but to debug the rest.

Quoted 8 lines
Quoted 7 lines

Your question asking for an actual performance impact of dormant hooks is OTOH entirely legitimate. It clearly depends on the placement of those hooks and thus their encounter rate, more so than their underlying technology (markers with whatever optimizations). If the cost is small enough, you will likely find that people will be willing to pay a small fraction of average performance, in order to eke out large gains when finding occasional e.g. algorithmic bugs.

Quoted 4 lines

If you might be able to get a big part of tracing and other debug code enabled with a performance penalty of a few percent of _kernel_ performance, then you might get much debugging aid without any effective impact on application performance.

it largely depends on the application. Applications which require a lot of system calls will be more sensible to kernel debugging. Common sense also implies that such applications will be the ones for which kernel debugging will be relevant.

Quoted 4 lines

You always have to decide between some debug code and some small bit of performance. There's a reason why options to disable things like BUG() or printk() are in the kernel config menus hidden behind CONFIG_EMBEDDED although they obviously have some performance impact.

It is not for the CPU performance they can be disabled, but for the code size which is a real problem on embedded system. While you often have mem/cpu_mhz ratios around 1GB/1GHz on servers and desktops, you more often have ratios like 16MB/500MHz which is 1:32 of the former. That's why you optimize for size at the expense of speed on such systems.

Quoted 5 lines
Quoted 2 lines

- FChE

cu
Adrian

Regards,
Willy

#42 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 8 lines · Willy Tarreau
Quoted 1 line · Adrian Bunk

On Sat, Jul 07, 2007 at 11:45:20AM -0400, Frank Ch. Eigler wrote:

...

Quoted 4 lines

You always have to decide between some debug code and some small bit of performance. There's a reason why options to disable things like BUG() or printk() are in the kernel config menus hidden behind CONFIG_EMBEDDED although they obviously have some performance impact.

Quoted 5 lines

It is not for the CPU performance they can be disabled, but for the code size which is a real problem on embedded system. While you often have mem/cpu_mhz ratios around 1GB/1GHz on servers and desktops, you more often have ratios like 16MB/500MHz which is 1:32 of the former. That's why you optimize for size at the expense of speed on such systems.

The latter is not true for my two examples.

CONFIG_PRINTK=n, CONFIG_BUG=n will obviously make the kernel both smaller and faster. [1]

Quoted 2 lines

Regards,
Willy

cu
Adrian

[1] faster due to less code to execute and positive cache effects due to the smaller code [2]
[2] whether the "faster" is big enough that it is in any way measurable is a different question

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

In reply to Adrian Bunk

Hi, Adrian -

Quoted 10 lines · Adrian Bunk

[...]

Quoted 3 lines

Things are not so simple. One might not know that one has a performance problem until one tries some analysis tools. Rebooting into different kernels just to investigate does not work generally [...]

I'm not getting this:

You'll only start looking into an analysis tool if you have a performance problem, IOW if you are not satisfied with the performance.

There may be people whose jobs entail continually suspecting performance problems. Or one may run instrumentation code on a long-term basis specifically to locate performance spikes.

Quoted 2 lines

And the debug code will not have been tested on this machine no matter whether it's enabled through a compile option or at runtime.

There is a big difference in favour of the former. The additional instrumentation code may be small enough to inspect carefully. The rest of the kernel would be unaffected.

Quoted 4 lines

[...] If you might be able to get a big part of tracing and other debug code enabled with a performance penalty of a few percent of _kernel_ performance, then you might get much debugging aid without any effective impact on application performance.

Agreed.

- FChE

#44 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

In reply to Adrian Bunk
Quoted 10 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 8 lines · Chuck Ebbert
Quoted 3 lines · Andi Kleen

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

Another thing to consider is that there might be hundreds of these probes/tracepoints active in an instrumented kernel. The overhead adds up fast, so the gain may be worth all the pain.

Quoted 6 lines

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

Adrian,

Please have a look at my markers posts, especially:

http://www.ussg.iu.edu/hypermail/linux/kernel/0707.0/0669.html

And also look into OLS 2007 proceedings for Martin Bligh's paper on Debugging Google sized clusters. It basically makes the case for adding functionnality to debug _user space_ problems on production systems that can be turned on dynamically.

Mathieu

Quoted 10 lines

cu
Adrian

Signature · 4 lines
       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed
Signature · 3 lines
Mathieu Desnoyers
Computer Engineering Ph.D. Student, Ecole Polytechnique de Montreal
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#45 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 20 lines · Mathieu Desnoyers
Quoted 10 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 8 lines · Chuck Ebbert
Quoted 3 lines · Andi Kleen

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

Another thing to consider is that there might be hundreds of these probes/tracepoints active in an instrumented kernel. The overhead adds up fast, so the gain may be worth all the pain.

Quoted 6 lines

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

Adrian,

Quoted 8 lines

Please have a look at my markers posts, especially:

http://www.ussg.iu.edu/hypermail/linux/kernel/0707.0/0669.html

And also look into OLS 2007 proceedings for Martin Bligh's paper on Debugging Google sized clusters. It basically makes the case for adding functionnality to debug _user space_ problems on production systems that can be turned on dynamically.

Using a different kernel for tracing still fulfills all the requirements listed in section 5 of your paper...

Quoted 1 line

Mathieu

cu
Adrian

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 25 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 24 lines · Mathieu Desnoyers
Quoted 10 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 8 lines · Chuck Ebbert
Quoted 3 lines · Andi Kleen

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

Another thing to consider is that there might be hundreds of these probes/tracepoints active in an instrumented kernel. The overhead adds up fast, so the gain may be worth all the pain.

Quoted 6 lines

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

Adrian,

Please have a look at my markers posts, especially:

http://www.ussg.iu.edu/hypermail/linux/kernel/0707.0/0669.html

Quoted 8 lines
Quoted 4 lines

And also look into OLS 2007 proceedings for Martin Bligh's paper on Debugging Google sized clusters. It basically makes the case for adding functionnality to debug _user space_ problems on production systems that can be turned on dynamically.

Using a different kernel for tracing still fulfills all the requirements listed in section 5 of your paper...

Not exactly. I assume you understand that rebooting 1000 live production servers to find the source of a rare bug or the cause of a performance issue is out of question.

Moreover, strategies like enabling flight recorder traces on a few nodes on demand to detect performance problems can only be deployed in production environment if they are part of the standard production kernel.

Also, managing two different kernels is often out of question. Not only is it a maintainance burden, but just switching to the "debug" kernel can impact the system's behavior so badly that it could make the problem disappear.

Mathieu

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 44 lines · Mathieu Desnoyers
Quoted 25 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 24 lines · Mathieu Desnoyers
Quoted 10 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 8 lines · Chuck Ebbert
Quoted 3 lines · Andi Kleen

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

Another thing to consider is that there might be hundreds of these probes/tracepoints active in an instrumented kernel. The overhead adds up fast, so the gain may be worth all the pain.

Quoted 6 lines

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

Adrian,

Please have a look at my markers posts, especially:

http://www.ussg.iu.edu/hypermail/linux/kernel/0707.0/0669.html

Quoted 8 lines
Quoted 4 lines

And also look into OLS 2007 proceedings for Martin Bligh's paper on Debugging Google sized clusters. It basically makes the case for adding functionnality to debug _user space_ problems on production systems that can be turned on dynamically.

Using a different kernel for tracing still fulfills all the requirements listed in section 5 of your paper...

Not exactly. I assume you understand that rebooting 1000 live production servers to find the source of a rare bug or the cause of a performance issue is out of question.

Moreover, strategies like enabling flight recorder traces on a few nodes on demand to detect performance problems can only be deployed in production environment if they are part of the standard production kernel.

Quoted 4 lines

Also, managing two different kernels is often out of question. Not only is it a maintainance burden, but just switching to the "debug" kernel can impact the system's behavior so badly that it could make the problem disappear.

As can turning tracing on at runtime.

And you can always define requirements in a way that your solution is the only one...

Let's go to a different point:

Your paper says "When not running, must have zero effective impact."

How big is the measured impact of your markers when not used without any immediate voodoo?

You have sent many numbers about micro-benchmarks and theoretical numbers, but if you have sent the interesting numbers comparing
1. MARKERS=n
2. MARKERS=y, IMMEDIATE=n
3. MARKERS=y, IMMEDIATE=y
in actual benchmark testing I must have missed it.

Does 3. have a measurable and effective advantage over 2. or are you optimizing for some 0.01% or 1% performance difference without any effective impact and therefore not requred for the goals outlined in your paper?

Quoted 1 line

Mathieu

cu
Adrian

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

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 50 lines · Adrian Bunk
Quoted 44 lines · Mathieu Desnoyers
Quoted 25 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 24 lines · Mathieu Desnoyers
Quoted 10 lines · * Adrian Bunk ([email protected]) wrote:
Quoted 8 lines · Chuck Ebbert
Quoted 3 lines · Andi Kleen

I think the optimization is a good idea, although i dislike it that it is complicated for the dynamic markers. If it was just static it would be much simpler.

Another thing to consider is that there might be hundreds of these probes/tracepoints active in an instrumented kernel. The overhead adds up fast, so the gain may be worth all the pain.

Quoted 6 lines

Only if you want to squeeze the last bit of performance out of _debugging_ functionality.

You avoid all the pain if you simply don't use debugging functionality on production systems.

Adrian,

Please have a look at my markers posts, especially:

http://www.ussg.iu.edu/hypermail/linux/kernel/0707.0/0669.html

Quoted 8 lines
Quoted 4 lines

And also look into OLS 2007 proceedings for Martin Bligh's paper on Debugging Google sized clusters. It basically makes the case for adding functionnality to debug _user space_ problems on production systems that can be turned on dynamically.

Using a different kernel for tracing still fulfills all the requirements listed in section 5 of your paper...

Not exactly. I assume you understand that rebooting 1000 live production servers to find the source of a rare bug or the cause of a performance issue is out of question.

Moreover, strategies like enabling flight recorder traces on a few nodes on demand to detect performance problems can only be deployed in production environment if they are part of the standard production kernel.

Quoted 4 lines

Also, managing two different kernels is often out of question. Not only is it a maintainance burden, but just switching to the "debug" kernel can impact the system's behavior so badly that it could make the problem disappear.

Quoted 4 lines

As can turning tracing on at runtime.

And you can always define requirements in a way that your solution is the only one...

On large production environments, you always lose a certain percentage of machines at each reboot. Most often, it's the CR2032 lithium battery which is dead and which causes all or parts of the CMOS settings to vanish, hanging the system at boot. Then you play with the ON/OFF switch and a small percentage of the power supplies refuse to restart and some disks refuse to spin up.

Fortunately this does not happen with all machines, but if you have such problems with 1% of your machines, you lose 10 machines when you reboot 1000 of them. Those problems require a lot of man power, which explains why such systems are rarely updated.

Causing that much trouble just to enable debugging is clearly unacceptable, and your debug kernel will simply never be used. Not to mention the fact that people will never trust it because it's almost never used !

Regards,
Willy

#49 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

In reply to Mathieu Desnoyers
Quoted 2 lines · Mathieu Desnoyers

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

I think it's better to put profile.c under CONFIG_PROFILING as _expected_, so CONFIG_PROFILING=n users won't get any overhead, immediate or not. That's what I'm going to do after test-booting bunch of kernels.

Thus, enabling CONFIG_PROFILING option will buy you some overhead, again, as _expected_.

#50 lore raw

Re: [patch 10/10] Scheduler profiling - Use immediate values

Quoted 7 lines · Alexey Dobriyan
Quoted 2 lines · Mathieu Desnoyers

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

I think it's better to put profile.c under CONFIG_PROFILING as _expected_, so CONFIG_PROFILING=n users won't get any overhead, immediate or not. That's what I'm going to do after test-booting bunch of kernels.

No, it's better to handle this efficiently at runtime e.g. for distribution kernels. Mathieu's patch is good

-Andi