jump-labels: Implement 2 and 5 byte jumps

Ingo,

A while ago I posted this series and you discovered a bug. I fixed that bug, but due to traveling and other responsibilities I'm not sure I posted the fix.

The fix is the last patch in this series.

As things have changed since the last post, there were a lot of conflicts, and I had to rebase the patch set against tip/perf/jump-labels and fix up the patches. Mostly the changes from JUMP_LABEL_* to STATIC_KEY_*.

But I got this done and retested them.

-- Steve

Please pull the latest tip/perf/jump-label-5 tree, which can be found at:

git://git.kernel.org/pub/scm/linux/kernel/git/rostedt/linux-trace.git
tip/perf/jump-label-5

Head SHA1: b0fdf8910bf8e30fd3542b05062ca9a9721cf26f

Steven Rostedt (7):
x86/jump-label: Use best default nops for inital jump label calls x86/jump-label: Do not bother updating nops if they are correct x86/jump-label: Add safety checks to jump label conversions jump labels: Add infrastructure to update jump labels at compile time x86/jump labels: Use etiher 5 byte or 2 byte jumps x86/jump lables: Show where and what was wrong on errors x86/jump labels: Handle initialization of enabled nops

----

 Makefile                          |    7 +
 arch/Kconfig                      |    6 +
 arch/x86/Kconfig                  |    1 +
 arch/x86/include/asm/jump_label.h |   14 ++-
 arch/x86/kernel/jump_label.c      |  121 ++++++++++++-
 scripts/Makefile                  |    1 +
 scripts/Makefile.build            |   15 ++-
 scripts/update_jump_label.c       |  341 +++++++++++++++++++++++++++++++++++++
 scripts/update_jump_label.h       |  208 ++++++++++++++++++++++
 9 files changed, 700 insertions(+), 14 deletions(-)

From: Steven Rostedt <[email protected]>

As specified by H. Peter Anvin, the best nops for x86 without knowing the running computer is:

32bit:
0x3e, 0x8d, 0x74, 0x26, 0x00 also known as GENERIC_NOP5_ATOMIC

64bit:
0x0f, 0x1f, 0x44, 0x00, 0x00 also known as P6_NOP5_ATOMIC

Currently the default nop that is used by jump label is:

0xe9 0x00 0x00 0x00 0x00

Which is really a 5byte jump to the next position.

It's better to use a real nop than a jmp.

---
 arch/x86/include/asm/jump_label.h |    9 +++++++--
 1 files changed, 7 insertions(+), 2 deletions(-)

index 3a16c14..64507f3 100644
@@ -3,18 +3,23 @@
 
 #ifdef __KERNEL__
 
+#include <linux/stringify.h>
 #include <linux/types.h>
 #include <asm/nops.h>
 #include <asm/asm.h>
 
 #define JUMP_LABEL_NOP_SIZE 5
 
-#define STATIC_KEY_INITIAL_NOP ".byte 0xe9 \n\t .long 0\n\t"
+#ifdef CONFIG_X86_64
+# define STATIC_KEY_INIT_NOP P6_NOP5_ATOMIC
+#else
+# define STATIC_KEY_INIT_NOP GENERIC_NOP5_ATOMIC
+#endif
 
 static __always_inline bool arch_static_branch(struct static_key *key)
 {
 	asm goto("1:"
-		STATIC_KEY_INITIAL_NOP
+		".byte " __stringify(STATIC_KEY_INIT_NOP) "\n\t"
 		".pushsection __jump_table,  \"aw\" \n\t"
 		_ASM_ALIGN "\n\t"
 		_ASM_PTR "1b, %l[l_yes], %c0 \n\t"

1.7.8.3

From: Steven Rostedt <[email protected]>

On boot up, the jump label init function scans all the jump label locations and converts them to the best nop for the machine. If the nop is already the ideal nop, do not bother with changing it.

---
 arch/x86/kernel/jump_label.c |   20 +++++++++++++++++++-
 1 files changed, 19 insertions(+), 1 deletions(-)

index 2889b3d..11cc4da 100644
@@ -53,7 +53,25 @@ void arch_jump_label_transform(struct jump_entry *entry,
 __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry,
 				      enum jump_label_type type)
 {
-	__jump_label_transform(entry, type, text_poke_early);
+	static int once;
+	static int update;
+
+	/*
+	 * This function is called at boot up and when modules are
+	 * first loaded. Check if the default nop, the one that is
+	 * inserted at compile time, is the ideal nop. If it is, then
+	 * we do not need to update the nop, and we can leave it as is.
+	 * If it is not, then we need to update the nop to the ideal nop.
+	 */
+	if (!once) {
+		const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
+		const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
+		once++;
+		if (memcmp(ideal_nop, default_nop, 5) != 0)
+			update = 1;
+	}
+	if (update)
+		__jump_label_transform(entry, type, text_poke_early);
 }
 
 #endif

1.7.8.3

From: Steven Rostedt <[email protected]>

As with all modifying of kernel text, we need to be very paranoid.

When converting the jump label locations to and from nops to jumps a check has been added to make sure what we are replacing is what we expect, otherwise we bug.

---
 arch/x86/kernel/jump_label.c |   32 ++++++++++++++++++++++++++++----
 1 files changed, 28 insertions(+), 4 deletions(-)

index 11cc4da..aaf88c9 100644
@@ -26,16 +26,40 @@ union jump_code_union {
 
 static void __jump_label_transform(struct jump_entry *entry,
 				   enum jump_label_type type,
-				   void *(*poker)(void *, const void *, size_t))
+				   void *(*poker)(void *, const void *, size_t),
+				   int init)
 {
 	union jump_code_union code;
+	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
 
 	if (type == JUMP_LABEL_ENABLE) {
+		/*
+		 * We are enabling this jump label. If it is not a nop
+		 * then something must have gone wrong.
+		 */
+		BUG_ON(memcmp((void *)entry->code, ideal_nop, 5) != 0);
+
 		code.jump = 0xe9;
 		code.offset = entry->target -
 				(entry->code + JUMP_LABEL_NOP_SIZE);
-	} else
+	} else {
+		/*
+		 * We are disabling this jump label. If it is not what
+		 * we think it is, then something must have gone wrong.
+		 * If this is the first initialization call, then we
+		 * are converting the default nop to the ideal nop.
+		 */
+		if (init) {
+			const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
+			BUG_ON(memcmp((void *)entry->code, default_nop, 5) != 0);
+		} else {
+			code.jump = 0xe9;
+			code.offset = entry->target -
+				(entry->code + JUMP_LABEL_NOP_SIZE);
+			BUG_ON(memcmp((void *)entry->code, &code, 5) != 0);
+		}
 		memcpy(&code, ideal_nops[NOP_ATOMIC5], JUMP_LABEL_NOP_SIZE);
+	}
 
 	(*poker)((void *)entry->code, &code, JUMP_LABEL_NOP_SIZE);
 }

@@ -45,7 +69,7 @@ void arch_jump_label_transform(struct jump_entry *entry,
 {
 	get_online_cpus();
 	mutex_lock(&text_mutex);
-	__jump_label_transform(entry, type, text_poke_smp);
+	__jump_label_transform(entry, type, text_poke_smp, 0);
 	mutex_unlock(&text_mutex);
 	put_online_cpus();
 }

@@ -71,7 +95,7 @@ __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry,
 			update = 1;
 	}
 	if (update)
-		__jump_label_transform(entry, type, text_poke_early);
+		__jump_label_transform(entry, type, text_poke_early, 1);
 }
 
 #endif

1.7.8.3

From: Steven Rostedt <[email protected]>

Add the infrastructure to allow architectures to modify the jump label locations at compile time. This is mainly for x86, where the jmps may be either 2 bytes or 5 bytes. Instead of wasting 5 bytes for all jump labels, this code will let x86 put in a jmp instead of a 5 byte nop. Then the assembler will make either a 2 byte or 5 byte jmp depending on where the target is.

At compile time, this code will replace the jmps with either a 2 byte or 5 byte nop depending on the size of the jmp that was added.

---
 Makefile                    |    7 +
 arch/Kconfig                |    6 +
 scripts/Makefile            |    1 +
 scripts/Makefile.build      |   15 ++-
 scripts/update_jump_label.c |  341 +++++++++++++++++++++++++++++++++++++++++++
 scripts/update_jump_label.h |  208 ++++++++++++++++++++++++++
 6 files changed, 576 insertions(+), 2 deletions(-)
 create mode 100644 scripts/update_jump_label.c
 create mode 100644 scripts/update_jump_label.h

index e3b23e8..52b0a91 100644
@@ -611,6 +611,13 @@ ifdef CONFIG_DYNAMIC_FTRACE
 endif
 endif
 
+ifdef CONFIG_JUMP_LABEL
+	ifdef CONFIG_HAVE_BUILD_TIME_JUMP_LABEL
+		BUILD_UPDATE_JUMP_LABEL := y
+		export BUILD_UPDATE_JUMP_LABEL
+	endif
+endif
+
 # We trigger additional mismatches with less inlining
 ifdef CONFIG_DEBUG_SECTION_MISMATCH
 KBUILD_CFLAGS += $(call cc-option, -fno-inline-functions-called-once)

index 5b448a7..0af2dc4 100644
@@ -184,6 +184,12 @@ config HAVE_PERF_EVENTS_NMI
 	  subsystem.  Also has support for calculating CPU cycle events
 	  to determine how many clock cycles in a given period.
 
+config HAVE_BUILD_TIME_JUMP_LABEL
+       bool
+       help
+	If an arch uses scripts/update_jump_label to patch in jump nops
+	at build time, then it must enable this option.
+
 config HAVE_ARCH_JUMP_LABEL
 	bool
 

index df7678f..738b65c 100644
@@ -13,6 +13,7 @@ hostprogs-$(CONFIG_LOGO)         += pnmtologo
 hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(CONFIG_IKCONFIG)     += bin2c
 hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount
+hostprogs-$(BUILD_UPDATE_JUMP_LABEL) += update_jump_label
 
 always		:= $(hostprogs-y) $(hostprogs-m)
 

index d2b366c..8a84b80 100644
@@ -258,6 +258,15 @@ cmd_modversions =								\
 	fi;
 endif
 
+ifdef BUILD_UPDATE_JUMP_LABEL
+update_jump_label_source := $(srctree)/scripts/update_jump_label.c \
+			$(srctree)/scripts/update_jump_label.h
+cmd_update_jump_label =						\
+	if [ $(@) != "scripts/mod/empty.o" ]; then		\
+		$(objtree)/scripts/update_jump_label "$(@)";	\
+	fi;
+endif
+
 ifdef CONFIG_FTRACE_MCOUNT_RECORD
 ifdef BUILD_C_RECORDMCOUNT
 ifeq ("$(origin RECORDMCOUNT_WARN)", "command line")

@@ -294,6 +303,7 @@ define rule_cc_o_c
 	$(cmd_modversions)						  \
 	$(call echo-cmd,record_mcount)					  \
 	$(cmd_record_mcount)						  \
+	$(cmd_update_jump_label)					  \
 	scripts/basic/fixdep $(depfile) $@ '$(call make-cmd,cc_o_c)' >    \
 	                                              $(dot-target).tmp;  \
 	rm -f $(depfile);						  \

@@ -301,13 +311,14 @@ define rule_cc_o_c
 endef
 
 # Built-in and composite module parts
-$(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
+$(obj)/%.o: $(src)/%.c $(recordmcount_source) $(update_jump_label_source) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 
 # Single-part modules are special since we need to mark them in $(MODVERDIR)
 
-$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
+$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) \
+		  $(update_jump_label_source) FORCE
 	$(call cmd,force_checksrc)
 	$(call if_changed_rule,cc_o_c)
 	@{ echo $(@:.o=.ko); echo $@; } > $(MODVERDIR)/$(@F:.o=.mod)

1.7.8.3

From: Steven Rostedt <[email protected]>

Have the jump labels add a "jmp" in the assembly instead of a default nop. This will cause the assembler to put in either a 2 byte or 5 byte jmp depending on where the target lable is.

Then at compile time, the update_jump_label code will replace the jmps with either 2 or 5 byte nops.

On boot up, the code can be examined to see if the jump label uses either a 2 or 5 byte nop and replace it.

By allowing the jump labels to be 2 bytes, it speeds up the nops, not only 2 byte nops are faster than 5 byte nops, but also because it saves on cache foot print.

text data bss dec hex filename
13403667 3666856 2998272 20068795 13239bb ../nobackup/mxtest/vmlinux-old 13398536 3666856 2998272 20063664 13225b0 ../nobackup/mxtest/vmlinux-new

Converting the current v3.2 trace points saved 5,131 bytes. As more places use jump labels, this will have a bigger savings.

---
 arch/x86/Kconfig                  |    1 +
 arch/x86/include/asm/jump_label.h |    7 +++-
 arch/x86/kernel/jump_label.c      |   85 ++++++++++++++++++++++++++++--------
 3 files changed, 73 insertions(+), 20 deletions(-)

index 5bed94e..5ad80a2 100644
@@ -67,6 +67,7 @@ config X86
 	select HAVE_USER_RETURN_NOTIFIER
 	select ARCH_BINFMT_ELF_RANDOMIZE_PIE
 	select HAVE_ARCH_JUMP_LABEL
+	select HAVE_BUILD_TIME_JUMP_LABEL
 	select HAVE_TEXT_POKE_SMP
 	select HAVE_GENERIC_HARDIRQS
 	select HAVE_SPARSE_IRQ

index 64507f3..615adb4 100644
@@ -10,6 +10,11 @@
 
 #define JUMP_LABEL_NOP_SIZE 5
 
+/*
+ * The STATIC_KEY_INIT_NOP must match the nops used in
+ * scripts/update_jump_label.c. Otherwise the boot time checks
+ * will fail and trigger a BUG() on boot up.
+ */
 #ifdef CONFIG_X86_64
 # define STATIC_KEY_INIT_NOP P6_NOP5_ATOMIC
 #else

@@ -19,7 +24,7 @@
 static __always_inline bool arch_static_branch(struct static_key *key)
 {
 	asm goto("1:"
-		".byte " __stringify(STATIC_KEY_INIT_NOP) "\n\t"
+		"jmp %l[l_yes]\n"
 		".pushsection __jump_table,  \"aw\" \n\t"
 		_ASM_ALIGN "\n\t"
 		_ASM_PTR "1b, %l[l_yes], %c0 \n\t"

1.7.8.3

Hi Steven,

Strange. I'm not seeing the text size savings with this patch, relative to the 'old' jump label compiled code. Is your comparison against jump labels disabled?

Here's the size without your patch 'CONFIG_JUMP_LABEL' set:

text data bss dec hex filename
10809465 1023976 1159168 12992609 c64061 vmlinux

And with your patches and 'CONFIG_JUMP_LABEL' set:

text data bss dec hex filename
10812613 1023976 1163264 12999853 c65cad vmlinux

So an increase in text of 3148. Which is not completely explained by the increase in arch/x86/kernel/jump_label.o:

without your patch 'CONFIG_JUMP_LABEL' set:

text data bss dec hex filename
229 0 0 229 e5 arch/x86/kernel/jump_label.o

with your patch 'CONFIG_JUMP_LABEL' set:

   text    data     bss     dec     hex filename
    943       0       8     951     3b7 arch/x86/kernel/jump_label.o

So jump_label.o is 714 bytes larger, which is not enough to explain the 3148 byte increase.

I'm using gcc (GCC) 4.6.2 20111027 (Red Hat 4.6.2-1).

Can you please double check the savings.

Thanks,

-Jason

Note, the code went through several changes since I first pushed these. I did not redo the size tests in my rebase.

Interesting that your test had a 3k increase?? but the jump label code increased by only 720bytes. This looks very fishy. And yes, I did have jump label enabled for my changes. I didn't change the config in the two checks. IIRC, I did a localyesconfig so that I would get the updates of the modules that would be used it my code, against a distro config.

Right this looks strange.

I'm still using 4.6.0.

I'll check again.

-- Steve

Here's my numbers from the latest changes. They are not as big, perhaps I had debug enabled too. I took a debian 3.0 config, enabled jump labels and some tracing, did a make localyesconfig (something broke it as the config still had modules that I had to manual convert to =y). Here's the results:

gcc 4.6.0

text data bss dec hex filename
14355064 1810272 5722112 21887448 14df9d8 vmlinux
14354490 1810400 5722112 21887002 14df81a vmlinux-patched

It's only a 574 byte savings. That's not much. I wish I had the config I used the first time. I may have had debug on that gave it a bigger impact.

Attached is the config:

-- Steve

At least you got a decrease! Using your .config I got the same 574 byte savings:

14310698        1810160 5722112 21842970        14d4c1a vmlinux-orig
14310124        1810288 5722112 21842524        14d4a5c vmlinux-new

I'm attaching my .config which is basically a defconfig with a few extra configs for my h/w + kvm + ext4.

Thanks,

-Jason

From: Steven Rostedt <[email protected]>

When modifying text sections for jump labels, a paranoid check is performed. If the check fails, the system "bugs". But why it failed is not shown.

The BUG_ON()s in the jump label update code is replaced with bug_at(ip). This is a function that will show what pointer failed, and what was at the location of the failure that made jump label panic.

---
 arch/x86/kernel/jump_label.c |   31 +++++++++++++++++++++----------
 1 files changed, 21 insertions(+), 10 deletions(-)

index d426da6..9bae2c9 100644
@@ -32,6 +32,18 @@ union jump_code_union {
 	} __packed;
 };
 
+static void bug_at(unsigned char *ip, int line)
+{
+	/*
+	 * The location is not an op that we were expecting.
+	 * Something went wrong. Crash the box, as something could be
+	 * corrupting the kernel.
+	 */
+	printk("Unexpected op at %pS [%p] (%02x %02x %02x %02x %02x) %s:%d\n",
+	       ip, ip, ip[0], ip[1], ip[2], ip[3], ip[4], __FILE__, line);
+	BUG();
+}
+
 static void __jump_label_transform(struct jump_entry *entry,
 				   enum jump_label_type type,
 				   void *(*poker)(void *, const void *, size_t),

@@ -59,12 +71,7 @@ static void __jump_label_transform(struct jump_entry *entry,
 			code.jump = 0xe9;
 			code.offset = entry->target - (entry->code + size);
 		} else
-			/*
-			 * The location is not a nop that we were expecting,
-			 * something went wrong. Crash the box, as something could be
-			 * corrupting the kernel.
-			 */
-			BUG();
+			bug_at(ip, __LINE__);
 	} else {
 		/*
 		 * We are disabling this jump label. If it is not what

@@ -78,7 +85,8 @@ static void __jump_label_transform(struct jump_entry *entry,
 				return;
 
 			/* We are initializing from the default nop */
-			BUG_ON(memcmp(ip, default_nop, 5) != 0);
+			if (unlikely(memcmp(ip, default_nop, 5) != 0))
+				bug_at(ip, __LINE__);
 
 			/* Set to the ideal nop */
 			size = JUMP_LABEL_NOP_SIZE;

@@ -91,7 +99,9 @@ static void __jump_label_transform(struct jump_entry *entry,
 			code.jump = 0xe9;
 			code.offset = entry->target -
 				(entry->code + JUMP_LABEL_NOP_SIZE);
-			BUG_ON(memcmp(ip, &code, 5) != 0);
+
+			if (unlikely(memcmp(ip, &code, 5) != 0))
+				bug_at(ip, __LINE__);
 
 			size = JUMP_LABEL_NOP_SIZE;
 			memcpy(&code, ideal_nops[NOP_ATOMIC5], size);

@@ -101,13 +111,14 @@ static void __jump_label_transform(struct jump_entry *entry,
 			/* Had better be a 2 byte jmp */
 			code.jump_short = 0xeb;
 			code.offset = entry->target - (entry->code + 2);
-			BUG_ON(memcmp(ip, &code, 2) != 0);
+			if (unlikely(memcmp(ip, &code, 2) != 0))
+				bug_at(ip, __LINE__);
 
 			size = 2;
 			memcpy(&code, nop_short, size);
 		} else
 			/* The code was not what we expected!  */
-			BUG();
+			bug_at(ip, __LINE__);
 	}
 
 	(*poker)(ip, &code, size);

1.7.8.3

From: Steven Rostedt <[email protected]>

When jump labels are initialized at boot up, they are compared to the default_nop before switching to the ideal nop.

But if a jump label is enabled by default on start up, the enabled code does not test against the default nop, only the ideal nop. But as this jump label has not been converted to the ideal nop, it fails the check, and will crash the box.

The enabled path needs to be aware of initialization too.

---
 arch/x86/kernel/jump_label.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

index 9bae2c9..c3ae7c3 100644
@@ -66,7 +66,8 @@ static void __jump_label_transform(struct jump_entry *entry,
 			code.jump_short = 0xeb;
 			code.offset = entry->target - (entry->code + 2);
 			/* Check for overflow ? */
-		} else if (memcmp(ip, ideal_nop, 5) == 0) {
+		} else if ((!init && memcmp(ip, ideal_nop, 5) == 0) ||
+			   (init && memcmp(ip, default_nop, 5) == 0)) {
 			size = JUMP_LABEL_NOP_SIZE;
 			code.jump = 0xe9;
 			code.offset = entry->target - (entry->code + size);

1.7.8.3