Skip to contentSkip to conversation

RFC: jump label - (tracepoint optimizations)

PATCH In review Jason Baron 6 participants 12 messages Sep 3, 2009 – Sep 10, 2009

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

cover RFC: jump label - (tracepoint optimizations)

hi,

Problem:

Currenly, tracepoints are implemented using a conditional. The conditional check requires checking a global variable for each tracepoint. Although, the overhead of this check is small, it increases under memory pressure. As we increase the number of tracepoints in the kernel this may become more of an issue. In addition, tracepoints are often dormant (disabled), and provide no direct kernel functionality. Thus, it is highly desirable to reduce their impact as much as possible. Mathieu Desnoyers has already suggested a number of requirements for a solution to this issue.

Solution:

In discussing this problem with Roland McGrath and Richard Henderson, we came up with a new 'asm goto' statement that allows branching to a label. Thus, this patch set introdues a 'STATIC_JUMP_IF()' macro as follows:

#ifdef HAVE_STATIC_JUMP

#define STATIC_JUMP_IF(tag, label, cond)                               \
       asm goto ("1:"   /* 5-byte insn */                              \
          P6_NOP5                                                      \
               ".pushsection __jump_table,  \"a\" \n\t"                \
               _ASM_PTR "1b, %l[" #label "], %c0 \n\t"                 \
               ".popsection \n\t"                                      \
               : :  "i" (__sjstrtab_##tag) :  : label)

#else

#define STATIC_JUMP_IF(tag, label, cond)        \
        if (unlikely(cond))                     \
                goto label;

#endif /* !HAVE_STATIC_JUMP */

which can be used as:

        STATIC_JUMP_IF(trace, trace_label, jump_enabled);
        printk("not doing tracing\n");
if (0) {
trace_label:
        printk("doing tracing: %d\n", file);
}

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

Thus, if 'HAVE_STATIC_JUMP' is defined (which will depend ultimately on the existence of 'asm goto' in the compiler version), we simply have a no-op followed by a jump around the dormant (disabled) tracing code. The 'STATIC_JUMP_IF()' macro, produces a 'jump_table' which has the following format:

[instruction address] [jump target] [tracepoint name]

Thus, to enable a tracepoint, we simply patch the 'instruction address' with a jump to the 'jump target'. The current implementation is using ftrace infrastructure to accomplish the patching, which uses 'stop_machine'. In subsequent versions, we will update the mechanism to use more efficient code patching techniques.

I've tested the performance of this using 'get_cycles()' calls around the tracepoint call sites. For an Intel Core 2 Quad cpu (in cycles, averages):

		idle		after tbench run
		----		----------------

old code 32 88
new code 2 4

The performance improvement can be reproduced very reliably (using patch 4 in this series) on both Intel and AMD hardware.

In terms of code analysis the current code for the disabled case is a 'cmpl' followed by a 'je' around the tracepoint code. so:

cmpl - 83 3d 0e 77 87 00 00 - 7 bytes
je - 74 3e - 2 bytes

total of 9 instruction bytes.

The new code is a 'nopl' followed by a 'jmp'. Thus:

nopl - 0f 1f 44 00 00 - 5 bytes
jmp - eb 3e - 2 bytes

total of 7 instruction bytes.

So, the new code also accounts for 2 less bytes in the instruction cache per tracepoint.

here's a link to the gcc thread introducing this feature:

http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html

Todo:

-convert the patching to a more optimal implementation (not using stop machine) -expand infrastructure for modules
-other use cases?
-mark the trace_label section with 'cold' attributes
-add module support
-add support for other arches (besides x86)

thanks,

-Jason

 arch/x86/kernel/ftrace.c          |   36 +++++
 arch/x86/kernel/test_nx.c         |    3 +
 include/asm-generic/vmlinux.lds.h |   11 ++
 include/linux/ftrace.h            |    3 +
 include/linux/jump_label.h        |   45 ++++++
 include/linux/tracepoint.h        |   50 +++++---
 kernel/Makefile                   |    2 +-
 kernel/jump_label.c               |  271 +++++++++++++++++++++++++++++++++++++
 kernel/trace/trace_workqueue.c    |    2 +
 kernel/tracepoint.c               |  134 ++++++++++++++++++
 10 files changed, 540 insertions(+), 17 deletions(-)
 create mode 100644 include/linux/jump_label.h
 create mode 100644 kernel/jump_label.c
#1 lore raw

PATCH 1/4 RFC: basic jump label implementation

introduce basic infrastructure for jump patching:

-STATIC_JUMP_IF() macro
-jump table infrastructure
-jump/nop patching in the ftrace layer

---
 arch/x86/kernel/ftrace.c          |   36 ++++++++++
 include/asm-generic/vmlinux.lds.h |   11 +++
 include/linux/ftrace.h            |    3 +
 include/linux/jump_label.h        |   45 ++++++++++++
 kernel/Makefile                   |    2 +-
 kernel/jump_label.c               |  138 +++++++++++++++++++++++++++++++++++++
 6 files changed, 234 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/jump_label.h
 create mode 100644 kernel/jump_label.c
arch/x86/kernel/ftrace.c +36 -0
index 9dbb527..0907b8c 100644
@@ -67,6 +67,20 @@ static unsigned char *ftrace_call_replace(unsigned long ip, unsigned long addr)
 	return calc.code;
 }
 
+static unsigned char *ftrace_jump_replace(unsigned long ip, unsigned long addr)
+{
+	static union ftrace_code_union calc;
+
+	calc.e8		= 0xe9;
+	calc.offset	= ftrace_calc_offset(ip + MCOUNT_INSN_SIZE, addr);
+
+	/*
+	 * No locking needed, this must be called via kstop_machine
+	 * which in essence is like running on a uniprocessor machine.
+	 */
+	return calc.code;
+}
+
 /*
  * Modifying code must take extra care. On an SMP machine, if
  * the code being modified is also being executed on another CPU
@@ -278,6 +292,28 @@ int ftrace_make_call(struct dyn_ftrace *rec, unsigned long addr)
 	return ftrace_modify_code(rec->ip, old, new);
 }
 
+int ftrace_make_jump(struct dyn_ftrace *rec, unsigned long addr)
+{
+	unsigned char *new, *old;
+	unsigned long ip = rec->ip;
+
+	old = ftrace_nop_replace();
+	new = ftrace_jump_replace(ip, addr);
+
+	return ftrace_modify_code(rec->ip, old, new);
+}
+
+int ftrace_make_jump_nop(struct dyn_ftrace *rec, unsigned long addr)
+{
+	unsigned char *new, *old;
+	unsigned long ip = rec->ip;
+
+	old = ftrace_jump_replace(ip, addr);
+	new = ftrace_nop_replace();
+
+	return ftrace_modify_code(rec->ip, old, new);
+}
+
 int ftrace_update_ftrace_func(ftrace_func_t func)
 {
 	unsigned long ip = (unsigned long)(&ftrace_call);
include/asm-generic/vmlinux.lds.h +11 -0
index a549465..d789646 100644
@@ -212,6 +212,7 @@
 		*(__vermagic)		/* Kernel version magic */	\
 		*(__markers_strings)	/* Markers: strings */		\
 		*(__tracepoints_strings)/* Tracepoints: strings */	\
+		*(__jump_strings)/* Jump: strings */	\
 	}								\
 									\
 	.rodata1          : AT(ADDR(.rodata1) - LOAD_OFFSET) {		\
@@ -219,6 +220,8 @@
 	}								\
 									\
 	BUG_TABLE							\
+	JUMP_TABLE							\
+									\
 									\
 	/* PCI quirks */						\
 	.pci_fixup        : AT(ADDR(.pci_fixup) - LOAD_OFFSET) {	\
@@ -563,6 +566,14 @@
 #define BUG_TABLE
 #endif
 
+#define JUMP_TABLE							\
+	. = ALIGN(8);							\
+	__jump_table : AT(ADDR(__jump_table) - LOAD_OFFSET) {		\
+		VMLINUX_SYMBOL(__start___jump_table) = .;		\
+		*(__jump_table)						\
+		VMLINUX_SYMBOL(__stop___jump_table) = .;			\
+	}
+
 #ifdef CONFIG_PM_TRACE
 #define TRACEDATA							\
 	. = ALIGN(4);							\
include/linux/ftrace.h +3 -0
index dc3b132..cf3d995 100644
@@ -227,6 +227,9 @@ extern int ftrace_make_nop(struct module *mod,
  * Any other value will be considered a failure.
  */
 extern int ftrace_make_call(struct dyn_ftrace *rec, unsigned long addr);
+extern int ftrace_make_jump(struct dyn_ftrace *rec, unsigned long addr);
+extern int ftrace_make_jump_nop(struct dyn_ftrace *rec, unsigned long addr);
+
 
 /* May be defined in arch */
 extern int ftrace_arch_read_dyn_info(char *buf, int size);
include/linux/jump_label.h new file +45 -0

45 lines not on this page · raw message

kernel/Makefile +1 -1
index ef1011b..d29ae98 100644
@@ -10,7 +10,7 @@ obj-y     = sched.o fork.o exec_domain.o panic.o printk.o \
 	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \
 	    hrtimer.o rwsem.o nsproxy.o srcu.o semaphore.o \
 	    notifier.o ksysfs.o pm_qos_params.o sched_clock.o cred.o \
-	    async.o
+	    async.o jump_label.o
 obj-y += groups.o
 
 ifdef CONFIG_FUNCTION_TRACER
kernel/jump_label.c new file +138 -0

138 lines not on this page · raw message

Signature · 1 line
1.6.2.5
#2 lore raw

PATCH 2/4 RFC: jump label example usage

In reply to Jason Baron

Example cases to see how jump patching can be used:

echo a '1' into <debugfs>/jump/enabled to see a 'doing tracing' printk echo a '0' into <debugfs>/jump/enabled to see a 'not doing tracing' printk

The codepaths are updated using code patching.

---
 kernel/jump_label.c |  133 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 133 insertions(+), 0 deletions(-)
kernel/jump_label.c +133 -0
index f6be1eb..0bc0b2d 100644
@@ -120,10 +120,143 @@ int run_make_nop(char *name)
 
 #endif
 
+static ssize_t read_enabled_file_jump(struct file *file,
+		char __user *user_buf, size_t count, loff_t *ppos)
+{
+	char buf[3];
+	ssize_t val;
+
+	if (jump_enabled)
+		buf[0] = '1';
+	else
+		buf[0] = '0';
+	buf[1] = '\n';
+	buf[2] = 0x00;
+
+	val = simple_read_from_buffer(user_buf, count, ppos, buf, 2);
+	JUMP_LABEL_IF(trace, trace_label, jump_enabled);
+	printk("not doing tracing\n");
+if (0) {
+trace_label:
+	printk("doing tracing: %d\n", file);
+}
+	printk("val is: %d\n", val);
+	return val;
+}
+
+static ssize_t read_enabled_file_jump2(struct file *file,
+               char __user *user_buf, size_t count, loff_t *ppos)
+{
+	char buf[3];
+	ssize_t val;
+
+	if (jump_enabled2)
+		buf[0] = '1';
+	else
+		buf[0] = '0';
+	buf[1] = '\n';
+	buf[2] = 0x00;
+
+	val = simple_read_from_buffer(user_buf, count, ppos, buf, 2);
+	JUMP_LABEL_IF(trace2, trace_label, jump_enabled2);
+	printk("not doing tracing 2\n");
+if (0) {
+trace_label:
+	printk("doing tracing 2: %d\n", file);
+}
+	printk("val is: %d\n", val);
+	return val;
+}
+
+static ssize_t write_enabled_file_jump(struct file *file,
+	const char __user *user_buf, size_t count, loff_t *ppos)
+{
+	char buf[32];
+	int buf_size;
+
+	buf_size = min(count, (sizeof(buf)-1));
+	if (copy_from_user(buf, user_buf, buf_size))
+		return -EFAULT;
+
+	switch (buf[0]) {
+	case 'y':
+	case 'Y':
+	case '1':
+		jump_enabled = 1;
+		run_make_jump("trace");
+		break;
+	case 'n':
+	case 'N':
+	case '0':
+		jump_enabled = 0;
+		run_make_nop("trace");
+		break;
+	}
+
+	return count;
+}
+
+static ssize_t write_enabled_file_jump2(struct file *file,
+		const char __user *user_buf, size_t count, loff_t *ppos)
+{
+	char buf[32];
+	int buf_size;
+
+	buf_size = min(count, (sizeof(buf)-1));
+	if (copy_from_user(buf, user_buf, buf_size))
+		return -EFAULT;
+
+	switch (buf[0]) {
+	case 'y':
+	case 'Y':
+	case '1':
+		jump_enabled2 = 1;
+		run_make_jump("trace2");
+		break;
+	case 'n':
+	case 'N':
+	case '0':
+		jump_enabled2 = 0;
+		run_make_nop("trace2");
+		break;
+	}
+
+	return count;
+}
+
+static struct file_operations fops_jump = {
+	.read =         read_enabled_file_jump,
+	.write =        write_enabled_file_jump,
+};
+
+static struct file_operations fops_jump2 = {
+	.read =         read_enabled_file_jump2,
+	.write =        write_enabled_file_jump2,
+};
+
 static int __jump_label_init(void)
 {
+	struct dentry *dir, *file;
+	unsigned int value = 1;
 	struct jump_entry *iter;
 
+	dir = debugfs_create_dir("jump", NULL);
+	if (!dir)
+		return -ENOMEM;
+
+	file = debugfs_create_file("enabled", 0600, dir,
+					&value, &fops_jump);
+	if (!file) {
+		debugfs_remove(dir);
+		return -ENOMEM;
+	}
+
+	file = debugfs_create_file("enabled2", 0600, dir,
+					&value, &fops_jump2);
+	if (!file) {
+		debugfs_remove(dir);
+		return -ENOMEM;
+	}
 
 #ifdef HAVE_STATIC_JUMP
 	printk("__start___jump_table is: %p\n", __start___jump_table);
Signature · 1 line
1.6.2.5
#3 lore raw

PATCH 3/4 RFC: implement tracepoints on top of jump patching

In reply to Jason Baron

Convert tracepoints to use the new jump patching infrastructure. See how easy it is!

Also, notice there is a patch to comment out the workqueue tracepoints. Without this patch I had some panic when doing the code patching. I think this is probably due to an iteraction b/w stop_machine() using workqueues to do the actual patching and the workqueue code itself.

---
 arch/x86/kernel/test_nx.c      |    3 +++
 include/linux/tracepoint.h     |   38 ++++++++++++++++++++++----------------
 kernel/trace/trace_workqueue.c |    2 ++
 kernel/tracepoint.c            |    9 +++++++++
 4 files changed, 36 insertions(+), 16 deletions(-)
arch/x86/kernel/test_nx.c +3 -0
index 787a5e4..3dab463 100644
@@ -15,6 +15,9 @@
 
 #include <asm/uaccess.h>
 #include <asm/asm.h>
+#include <linux/jump_label.h>
+
+JUMP_LABEL_NAME(kmalloc);
 
 extern int rodata_test_data;
 
include/linux/tracepoint.h +22 -16
index 63a3f7a..fdd2d8b 100644
@@ -16,6 +16,7 @@
 
 #include <linux/types.h>
 #include <linux/rcupdate.h>
+#include <linux/jump_label.h>
 
 struct module;
 struct tracepoint;
@@ -63,21 +64,25 @@ struct tracepoint {
  * not add unwanted padding between the beginning of the section and the
  * structure. Force alignment to the same alignment as the section start.
  */
-#define DECLARE_TRACE(name, proto, args)				\
-	extern struct tracepoint __tracepoint_##name;			\
-	static inline void trace_##name(proto)				\
-	{								\
-		if (unlikely(__tracepoint_##name.state))		\
-			__DO_TRACE(&__tracepoint_##name,		\
-				TP_PROTO(proto), TP_ARGS(args));	\
-	}								\
-	static inline int register_trace_##name(void (*probe)(proto))	\
-	{								\
-		return tracepoint_probe_register(#name, (void *)probe);	\
-	}								\
-	static inline int unregister_trace_##name(void (*probe)(proto))	\
-	{								\
-		return tracepoint_probe_unregister(#name, (void *)probe);\
+#define DECLARE_TRACE(name, proto, args)				     \
+	extern struct tracepoint __tracepoint_##name;			     \
+	extern const char __sjstrtab_##name[];				     \
+	static inline void trace_##name(proto)				     \
+	{								     \
+		JUMP_LABEL_IF(name, trace_label, __tracepoint_##name.state); \
+		if (0) {						     \
+trace_label:								     \
+			__DO_TRACE(&__tracepoint_##name,		     \
+				TP_PROTO(proto), TP_ARGS(args));	     \
+		}							     \
+	}								     \
+	static inline int register_trace_##name(void (*probe)(proto))	     \
+	{								     \
+		return tracepoint_probe_register(#name, (void *)probe);	     \
+	}								     \
+	static inline int unregister_trace_##name(void (*probe)(proto))	     \
+	{								     \
+		return tracepoint_probe_unregister(#name, (void *)probe);    \
 	}
 
 
@@ -86,7 +91,8 @@ struct tracepoint {
 	__attribute__((section("__tracepoints_strings"))) = #name;	\
 	struct tracepoint __tracepoint_##name				\
 	__attribute__((section("__tracepoints"), aligned(32))) =	\
-		{ __tpstrtab_##name, 0, reg, unreg, NULL }
+		{ __tpstrtab_##name, 0, reg, unreg, NULL };		\
+	JUMP_LABEL_NAME(name);
 
 #define DEFINE_TRACE(name)						\
 	DEFINE_TRACE_FN(name, NULL, NULL);
kernel/trace/trace_workqueue.c +2 -0
index 40cafb0..bc38428 100644
@@ -258,6 +258,7 @@ int __init trace_workqueue_early_init(void)
 {
 	int ret, cpu;
 
+	/*
 	ret = register_trace_workqueue_insertion(probe_workqueue_insertion);
 	if (ret)
 		goto out;
@@ -273,6 +274,7 @@ int __init trace_workqueue_early_init(void)
 	ret = register_trace_workqueue_destruction(probe_workqueue_destruction);
 	if (ret)
 		goto no_creation;
+	*/
 
 	for_each_possible_cpu(cpu) {
 		spin_lock_init(&workqueue_cpu_stat(cpu)->lock);
kernel/tracepoint.c +9 -0
index 9489a0a..1b4acc0 100644
@@ -25,6 +25,7 @@
 #include <linux/err.h>
 #include <linux/slab.h>
 #include <linux/sched.h>
+#include <linux/jump_label.h>
 
 extern struct tracepoint __start___tracepoints[];
 extern struct tracepoint __stop___tracepoints[];
@@ -256,6 +257,11 @@ static void set_tracepoint(struct tracepoint_entry **entry,
 	 * is used.
 	 */
 	rcu_assign_pointer(elem->funcs, (*entry)->funcs);
+	if (!elem->state && active) {
+		printk("set_tracepoint: call run_make_jump: %s\n", elem->name);
+		run_make_jump(elem->name);
+	} else if (elem->state && !active)
+		run_make_nop(elem->name);
 	elem->state = active;
 }
 
@@ -270,6 +276,9 @@ static void disable_tracepoint(struct tracepoint *elem)
 	if (elem->unregfunc && elem->state)
 		elem->unregfunc();
 
+	if (elem->state)
+		run_make_nop(elem->name);
+
 	elem->state = 0;
 	rcu_assign_pointer(elem->funcs, NULL);
 }
Signature · 1 line
1.6.2.5
#4 lore raw

PATCH 4/4 RFC: performance testing harness

In reply to Jason Baron

Not intended to be merged just a harness for micro-testing tracepoint performance.

---
 include/linux/tracepoint.h |   12 ++++
 kernel/tracepoint.c        |  125 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 137 insertions(+), 0 deletions(-)
include/linux/tracepoint.h +12 -0
index fdd2d8b..da657bf 100644
@@ -27,6 +27,8 @@ struct tracepoint {
 	void (*regfunc)(void);
 	void (*unregfunc)(void);
 	void **funcs;
+	unsigned long cycle_total;
+	unsigned long count;
 } __attribute__((aligned(32)));		/*
 					 * Aligned on 32 bytes because it is
 					 * globally visible and gcc happily
@@ -69,12 +71,22 @@ struct tracepoint {
 	extern const char __sjstrtab_##name[];				     \
 	static inline void trace_##name(proto)				     \
 	{								     \
+		unsigned long profile_flags;				     \
+		u64 t1, t2;						     \
+		local_irq_save(profile_flags);				     \
+		preempt_disable();					     \
+		t1 = get_cycles();					     \
 		JUMP_LABEL_IF(name, trace_label, __tracepoint_##name.state); \
 		if (0) {						     \
 trace_label:								     \
 			__DO_TRACE(&__tracepoint_##name,		     \
 				TP_PROTO(proto), TP_ARGS(args));	     \
 		}							     \
+		t2 = get_cycles();					     \
+		local_irq_restore(profile_flags);			     \
+		preempt_enable();					     \
+		__tracepoint_##name.count += 1;				     \
+		__tracepoint_##name.cycle_total += (t2 - t1);		     \
 	}								     \
 	static inline int register_trace_##name(void (*probe)(proto))	     \
 	{								     \
kernel/tracepoint.c +125 -0

148 lines not on this page · raw message

Signature · 1 line
1.6.2.5
#5 lore raw
In reply to Jason Baron
Quoted 4 lines · Jason Baron

hi,

Problem:

Quoted 8 lines

Currenly, tracepoints are implemented using a conditional. The conditional check requires checking a global variable for each tracepoint. Although, the overhead of this check is small, it increases under memory pressure. As we increase the number of tracepoints in the kernel this may become more of an issue. In addition, tracepoints are often dormant (disabled), and provide no direct kernel functionality. Thus, it is highly desirable to reduce their impact as much as possible. Mathieu Desnoyers has already suggested a number of requirements for a solution to this issue.

Could you run your patches though scripts/checkpatch.pl and clean up any errors.. It looks like you have some style issues in a few of the patches.

Daniel

#6 lore raw
In reply to Jason Baron
Quoted 93 lines · Jason Baron

hi,

Problem:

Currenly, tracepoints are implemented using a conditional. The conditional check requires checking a global variable for each tracepoint. Although, the overhead of this check is small, it increases under memory pressure. As we increase the number of tracepoints in the kernel this may become more of an issue. In addition, tracepoints are often dormant (disabled), and provide no direct kernel functionality. Thus, it is highly desirable to reduce their impact as much as possible. Mathieu Desnoyers has already suggested a number of requirements for a solution to this issue.

Solution:

In discussing this problem with Roland McGrath and Richard Henderson, we came up with a new 'asm goto' statement that allows branching to a label. Thus, this patch set introdues a 'STATIC_JUMP_IF()' macro as follows:

#ifdef HAVE_STATIC_JUMP

#define STATIC_JUMP_IF(tag, label, cond)                               \
       asm goto ("1:"   /* 5-byte insn */                              \
          P6_NOP5                                                      \
               ".pushsection __jump_table,  \"a\" \n\t"                \
               _ASM_PTR "1b, %l[" #label "], %c0 \n\t"                 \
               ".popsection \n\t"                                      \
               : :  "i" (__sjstrtab_##tag) :  : label)

#else

#define STATIC_JUMP_IF(tag, label, cond)        \
        if (unlikely(cond))                     \
                goto label;

#endif /* !HAVE_STATIC_JUMP */

which can be used as:

        STATIC_JUMP_IF(trace, trace_label, jump_enabled);
        printk("not doing tracing\n");
if (0) {
trace_label:
        printk("doing tracing: %d\n", file);
}

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

Thus, if 'HAVE_STATIC_JUMP' is defined (which will depend ultimately on the existence of 'asm goto' in the compiler version), we simply have a no-op followed by a jump around the dormant (disabled) tracing code. The 'STATIC_JUMP_IF()' macro, produces a 'jump_table' which has the following format:

[instruction address] [jump target] [tracepoint name]

Thus, to enable a tracepoint, we simply patch the 'instruction address' with a jump to the 'jump target'. The current implementation is using ftrace infrastructure to accomplish the patching, which uses 'stop_machine'. In subsequent versions, we will update the mechanism to use more efficient code patching techniques.

I've tested the performance of this using 'get_cycles()' calls around the tracepoint call sites. For an Intel Core 2 Quad cpu (in cycles, averages):

		idle		after tbench run
		----		----------------

old code 32 88
new code 2 4

The performance improvement can be reproduced very reliably (using patch 4 in this series) on both Intel and AMD hardware.

In terms of code analysis the current code for the disabled case is a 'cmpl' followed by a 'je' around the tracepoint code. so:

cmpl - 83 3d 0e 77 87 00 00 - 7 bytes
je - 74 3e - 2 bytes

total of 9 instruction bytes.

The new code is a 'nopl' followed by a 'jmp'. Thus:

nopl - 0f 1f 44 00 00 - 5 bytes
jmp - eb 3e - 2 bytes

Quoted 8 lines

total of 7 instruction bytes.

So, the new code also accounts for 2 less bytes in the instruction cache per tracepoint.

here's a link to the gcc thread introducing this feature:

http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html

This looks really interesting and desired. Once GCC adds this (or an equivalent) feature, i'd love to have your optimization in the kernel.

Quoted 5 lines

Todo:

- convert the patching to a more optimal implementation (not using stop machine)
- expand infrastructure for modules
- other use cases?

[...]

Other usecases might be kernel features that are turned on/off via some slowpath. For example SLAB statistics could be patched in/out using this method. Or scheduler statistics.

Basically everything that is optional and touches some very hot codepath would be eligible - not just tracepoints.

Ingo

#7 lore raw
Quoted 3 lines

This looks really interesting and desired. Once GCC adds this (or an equivalent) feature, i'd love to have your optimization in the kernel.

We expect it will be in gcc 4.5 and backported to Fedora's 4.4 pretty soon. But it's not finalized yet, so we are only doing proof-of-concept so far.

Quoted 2 lines

Basically everything that is optional and touches some very hot codepath would be eligible - not just tracepoints.

Sure. Any place you have a load+conditional-jump where that is too costly, we can make it a nop that costs a only cycle or so. We probably want to think a little harder about the nicest macro setup we can do to make employing this trivial in the source.

Thanks,
Roland

#8 lore raw
In reply to Jason Baron
Quoted 4 lines · * Jason Baron ([email protected]) wrote:

hi,

Problem:

Quoted 9 lines

Currenly, tracepoints are implemented using a conditional. The conditional check requires checking a global variable for each tracepoint. Although, the overhead of this check is small, it increases under memory pressure. As we increase the number of tracepoints in the kernel this may become more of an issue. In addition, tracepoints are often dormant (disabled), and provide no direct kernel functionality. Thus, it is highly desirable to reduce their impact as much as possible. Mathieu Desnoyers has already suggested a number of requirements for a solution to this issue.

Hi Jason,

Thanks for working on this. It's a useful idea that's just been sitting there for too long now. Please see comments below,

Quoted 11 lines

Solution:

In discussing this problem with Roland McGrath and Richard Henderson, we came up with a new 'asm goto' statement that allows branching to a label. Thus, this patch set introdues a 'STATIC_JUMP_IF()' macro as follows:

#ifdef HAVE_STATIC_JUMP

#define STATIC_JUMP_IF(tag, label, cond)                               \
       asm goto ("1:"   /* 5-byte insn */                              \
          P6_NOP5                                                      \

Hrm, be careful there. P6_NOP5 is not always a single instruction. If you are preempted in the middle of it, bad things could happen, even with stop_machine, if you iret in the middle the of the new jump instruction. It could cause an illegal instruction fault. You should use an atomic nop5. I think the function tracer already does, since I told Steven about this exact issue.

Quoted 5 lines
               ".pushsection __jump_table,  \"a\" \n\t"                \
               _ASM_PTR "1b, %l[" #label "], %c0 \n\t"                 \
               ".popsection \n\t"                                      \
               : :  "i" (__sjstrtab_##tag) :  : label)

Supporting multiple labels to create a real jump table would be a nice-to-have as future enhancement too. This could be called STATIC_JUMP_TABLE(). Actually, the STATIC_JUMP_IF could probably be implemented in terms of STATIC_JUMP_TABLE.

Quoted 6 lines

#else

#define STATIC_JUMP_IF(tag, label, cond)        \
        if (unlikely(cond))                     \
                goto label;

Hrm, however, it's not clear to me how the STATIC_JUMP_TABLE() fallback would look like. In the case of STATIC_JUMP_IF, it's a simple if (), which makes support of compilers lacking static jump support easy. We could probably use a switch statement to replace the STATIC_JUMP_TABLE though.

Quoted 12 lines

#endif /* !HAVE_STATIC_JUMP */

which can be used as:

        STATIC_JUMP_IF(trace, trace_label, jump_enabled);
        printk("not doing tracing\n");
if (0) {
trace_label:
        printk("doing tracing: %d\n", file);
}

Hrm. Is there any way to make this a bit prettier ? Given modifications are made to gcc anyway...

Maybe:

static_jump_if (trace, jump_enabled) {
...

} else {
...
}

And for the jump table:

static_jump_table (trace, jump_select) {
case 0: ...

          break;
  case 1: ...
          break;
  default:
          ...
}
Quoted 5 lines

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

Thus, if 'HAVE_STATIC_JUMP' is defined (which will depend ultimately on the existence of 'asm goto' in the compiler version), we simply have a no-op followed by a jump around the dormant (disabled) tracing code.

Hrm, why don't we collapse that into a single 5-bytes jump instruction instead ?

Quoted 32 lines

The
'STATIC_JUMP_IF()' macro, produces a 'jump_table' which has the following format:

[instruction address] [jump target] [tracepoint name]

Thus, to enable a tracepoint, we simply patch the 'instruction address' with a jump to the 'jump target'. The current implementation is using ftrace infrastructure to accomplish the patching, which uses 'stop_machine'. In subsequent versions, we will update the mechanism to use more efficient code patching techniques.

I've tested the performance of this using 'get_cycles()' calls around the tracepoint call sites. For an Intel Core 2 Quad cpu (in cycles, averages):

		idle		after tbench run
		----		----------------

old code 32 88
new code 2 4

The performance improvement can be reproduced very reliably (using patch 4 in this series) on both Intel and AMD hardware.

In terms of code analysis the current code for the disabled case is a 'cmpl' followed by a 'je' around the tracepoint code. so:

cmpl - 83 3d 0e 77 87 00 00 - 7 bytes
je - 74 3e - 2 bytes

total of 9 instruction bytes.

Quoted 9 lines

The new code is a 'nopl' followed by a 'jmp'. Thus:

nopl - 0f 1f 44 00 00 - 5 bytes
jmp - eb 3e - 2 bytes

total of 7 instruction bytes.

So, the new code also accounts for 2 less bytes in the instruction cache per tracepoint.

With a single 5-bytes jump, this would account for a 5 bytes total, which is 4 bytes less.

Thanks,

Mathieu

Quoted 31 lines

here's a link to the gcc thread introducing this feature:

http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html

Todo:

(quoted diff) +0 -6
-convert the patching to a more optimal implementation (not using stop machine)
-expand infrastructure for modules
-other use cases?
-mark the trace_label section with 'cold' attributes
-add module support
-add support for other arches (besides x86)

thanks,

-Jason

 arch/x86/kernel/ftrace.c          |   36 +++++
 arch/x86/kernel/test_nx.c         |    3 +
 include/asm-generic/vmlinux.lds.h |   11 ++
 include/linux/ftrace.h            |    3 +
 include/linux/jump_label.h        |   45 ++++++
 include/linux/tracepoint.h        |   50 +++++---
 kernel/Makefile                   |    2 +-
 kernel/jump_label.c               |  271 +++++++++++++++++++++++++++++++++++++
 kernel/trace/trace_workqueue.c    |    2 +
 kernel/tracepoint.c               |  134 ++++++++++++++++++
 10 files changed, 540 insertions(+), 17 deletions(-)
 create mode 100644 include/linux/jump_label.h
 create mode 100644 kernel/jump_label.c
Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#9 lore raw
Quoted 1 line · * Mathieu Desnoyers ([email protected]) wrote:

* Jason Baron ([email protected]) wrote:

[...]

Quoted 12 lines
Quoted 11 lines

Solution:

In discussing this problem with Roland McGrath and Richard Henderson, we came up with a new 'asm goto' statement that allows branching to a label. Thus, this patch set introdues a 'STATIC_JUMP_IF()' macro as follows:

#ifdef HAVE_STATIC_JUMP

#define STATIC_JUMP_IF(tag, label, cond)                               \
       asm goto ("1:"   /* 5-byte insn */                              \
          P6_NOP5                                                      \
Quoted 7 lines

Hrm, be careful there. P6_NOP5 is not always a single instruction. If you are preempted in the middle of it, bad things could happen, even with stop_machine, if you iret in the middle the of the new jump instruction. It could cause an illegal instruction fault. You should use an atomic nop5. I think the function tracer already does, since I told Steven about this exact issue.

Just to clarify this statement:

P6_NOP5 happens to be an atomic nop, but nothing states this requirement in arch/x86/include/asm/nops.h. Other 5-bytes nops are defined as multiple instructions (e.g. 2 bytes + 3 bytes nops). So I recommend to create a family of ATOMIC_P6_NOP5 (and other ATOMIC_*_NOP5 defines) to document this atomicity requirement.

Ftrace could probably handle this more gracefully than it does at the moment. It basically assumes that P6_NOP5 is atomic, and falls back on a 5-bytes jmp if it detects that P6_NOP5 faults.

That's coherent with the
"TODO: check the cpuid to determine the best nop."

present in x86 ftrace.c.

So, at the very least, if we rely on nops.h having a single-instruction P6_NOP5 5 bytes nop, a comment to that effect should be added to nops.h.

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
maintainer
#10 lore raw
Quoted 23 lines · Mathieu Desnoyers
Quoted 1 line · * Mathieu Desnoyers ([email protected]) wrote:

* Jason Baron ([email protected]) wrote:

[...]

Quoted 12 lines
Quoted 11 lines

Solution:

In discussing this problem with Roland McGrath and Richard Henderson, we came up with a new 'asm goto' statement that allows branching to a label. Thus, this patch set introdues a 'STATIC_JUMP_IF()' macro as follows:

#ifdef HAVE_STATIC_JUMP

#define STATIC_JUMP_IF(tag, label, cond)                               \
       asm goto ("1:"   /* 5-byte insn */                              \
          P6_NOP5                                                      \
Quoted 7 lines

Hrm, be careful there. P6_NOP5 is not always a single instruction. If you are preempted in the middle of it, bad things could happen, even with stop_machine, if you iret in the middle the of the new jump instruction. It could cause an illegal instruction fault. You should use an atomic nop5. I think the function tracer already does, since I told Steven about this exact issue.

Quoted 7 lines

Just to clarify this statement:

P6_NOP5 happens to be an atomic nop, but nothing states this requirement in arch/x86/include/asm/nops.h. Other 5-bytes nops are defined as multiple instructions (e.g. 2 bytes + 3 bytes nops). So I recommend to create a family of ATOMIC_P6_NOP5 (and other ATOMIC_*_NOP5 defines) to document this atomicity requirement.

Although I agree that we probably should place a comment in that file, I highly doubt anyone will change that. But who knows?

Quoted 5 lines

Ftrace could probably handle this more gracefully than it does at the moment. It basically assumes that P6_NOP5 is atomic, and falls back on a 5-bytes jmp if it detects that P6_NOP5 faults.

Quoted 7 lines

That's coherent with the
"TODO: check the cpuid to determine the best nop."

present in x86 ftrace.c.

So, at the very least, if we rely on nops.h having a single-instruction P6_NOP5 5 bytes nop, a comment to that effect should be added to nops.h.

I might as well go add one.

-- Steve

#11 lore raw
In reply to Mathieu Desnoyers
Quoted 18 lines · Mathieu Desnoyers
Quoted 5 lines
               ".pushsection __jump_table,  \"a\" \n\t"                \
               _ASM_PTR "1b, %l[" #label "], %c0 \n\t"                 \
               ".popsection \n\t"                                      \
               : :  "i" (__sjstrtab_##tag) :  : label)

Supporting multiple labels to create a real jump table would be a nice-to-have as future enhancement too. This could be called STATIC_JUMP_TABLE(). Actually, the STATIC_JUMP_IF could probably be implemented in terms of STATIC_JUMP_TABLE.

Quoted 6 lines

#else

#define STATIC_JUMP_IF(tag, label, cond)        \
        if (unlikely(cond))                     \
                goto label;
Quoted 6 lines

Hrm, however, it's not clear to me how the STATIC_JUMP_TABLE() fallback would look like. In the case of STATIC_JUMP_IF, it's a simple if (), which makes support of compilers lacking static jump support easy. We could probably use a switch statement to replace the STATIC_JUMP_TABLE though.

right - if we have more labels passed into STATIC_JUMP_TABLE(), we can probably do a case statement with a 'goto' to the correct label.

Quoted 27 lines
Quoted 12 lines

#endif /* !HAVE_STATIC_JUMP */

which can be used as:

        STATIC_JUMP_IF(trace, trace_label, jump_enabled);
        printk("not doing tracing\n");
if (0) {
trace_label:
        printk("doing tracing: %d\n", file);
}

Hrm. Is there any way to make this a bit prettier ? Given modifications are made to gcc anyway...

Maybe:

static_jump_if (trace, jump_enabled) {
...

} else {
...
}

And for the jump table:

Quoted 9 lines

static_jump_table (trace, jump_select) {
case 0: ...

          break;
  case 1: ...
          break;
  default:
          ...
}

hmmm...yes, I agree it would be nice if the code looked a little prettier. However, short of additional gcc changes i'm not sure how to do that. perhaps, somebody has some better ideas? Note also, that the 'STATIC_JUMP_IF()' as defined implements both:

if () { }

and:

if () { } else { }

I'm not sure the code is that hideous as proposed. However, I definitely would be interested it other opinions? Also, in this case note that the STATIC_JUMP_IF() is only added to 1 place in the code, and doesn't affect any of the normal tracepoint API.

Quoted 9 lines
Quoted 6 lines

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

Thus, if 'HAVE_STATIC_JUMP' is defined (which will depend ultimately on the existence of 'asm goto' in the compiler version), we simply have a no-op followed by a jump around the dormant (disabled) tracing code.

Hrm, why don't we collapse that into a single 5-bytes jump instruction instead ?

that might be nice, but would require more complex compiler support. I'm not sure if the extra complexity is worth the 2-byte i-cache savings? That is, I think we're getting the majority of the savings with the proposed solution.

thanks,

-Jason