Skip to contentSkip to conversation

x86/jump_label: Bound IPIs sent when updating a static key

PATCH Superseded Daniel Bristot de Oliveira 4 participants 27 messages Dec 21, 2018 – Apr 19, 2019

Subsystems (3)

v3 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

v3 cover x86/jump_label: Bound IPIs sent when updating a static key

While tuning a system with CPUs isolated as much as possible, we've noticed that isolated CPUs were receiving bursts of 12 IPIs, periodically. Tracing the functions that emit IPIs, we saw chronyd - an unprivileged process - generating the IPIs when changing a static key, enabling network timestaping on sockets.

For instance, the trace pointed:

# trace-cmd record --func-stack -p function -l smp_call_function_single -e irq_vectors -f 'vector == 251'...
# trace-cmde report...
[...]
         chronyd-858   [000]   433.286406: function:             smp_call_function_single
         chronyd-858   [000]   433.286408: kernel_stack:         <stack trace>
=> smp_call_function_many (ffffffffbc10ab22)
=> smp_call_function (ffffffffbc10abaa)
=> on_each_cpu (ffffffffbc10ac0b)
=> text_poke_bp (ffffffffbc02436a)
=> arch_jump_label_transform (ffffffffbc020ec8)
=> __jump_label_update (ffffffffbc1b300f)
=> jump_label_update (ffffffffbc1b30ed)
=> static_key_slow_inc (ffffffffbc1b334d)
=> net_enable_timestamp (ffffffffbc625c44)
=> sock_enable_timestamp (ffffffffbc6127d5)
=> sock_setsockopt (ffffffffbc612d2f)
=> SyS_setsockopt (ffffffffbc60d5e6)
=> tracesys (ffffffffbc7681c5)
          <idle>-0     [001]   433.286416: call_function_single_entry: vector=251
          <idle>-0     [001]   433.286419: call_function_single_exit: vector=251

[... The IPI takes place 12 times]

The static key in case was the netstamp_needed_key. A static key change from enabled->disabled/disabled->enabled causes the code to be patched, and this is done in three steps:

-- Pseudo-code #1 - Current implementation ---
For each key to be updated:
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

As the static key netstamp_needed_key has four entries (used in for places in the code) in our kernel, 3 IPIs were generated for each entry, resulting in 12 IPIs. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling is _not_ running.

Rather than doing each updated at once, it is possible to queue all updates first, and then apply all updates at once, rewriting the pseudo-code #1 in this way:

-- Pseudo-code #2 - proposal ---
1) for each key in the queue:
add an int3 trap to the address that will be patched
sync cores (send IPI to all other CPUs)

2) for each key in the queue:
update all but the first byte of the patched range
sync cores (send IPI to all other CPUs)

3) for each key in the queue:
replace the first byte (int3) by the first byte of replacing opcode
sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - proposal ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

Currently, the jump label of a static key is transformed via the arch specific function:

void arch_jump_label_transform(struct jump_entry *entry,
enum jump_label_type type)

The new approach (batch mode) uses two arch functions, the first has the same arguments of the arch_jump_label_transform(), and is the function:

void arch_jump_label_transform_queue(struct jump_entry *entry,
enum jump_label_type type)

Rather than transforming the code, it adds the jump_entry in a queue of entries to be updated.

After queuing all jump_entries, the function:

void arch_jump_label_transform_apply(void)

Applies the changes in the queue.

One easy way to see the benefits of this patch is switching the schedstats on and off. For instance:

-------------------------- %< ---------------------------- #!/bin/bash

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
sleep 2
sysctl -w kernel.sched_schedstats=0
sleep 2
done
-------------------------- >% ----------------------------

while watching the IPI count:

-------------------------- %< ----------------------------

# watch -n1 "cat /proc/interrupts | grep Function"
-------------------------- >% ----------------------------

With the current mode, it is possible to see +- 168 IPIs each 2 seconds, while with the batch mode the number of IPIs goes to 3 each 2 seconds.

Regarding the performance impact of this patch set, I made two measurements:

The time to update a key (the task that is causing the change) The time to run the int3 handler (the side effect on a thread that
hits the code being changed)

The sched_schedstats static key was chosen as the key to being switched on and off. The reason being is that it is used in more than 56 places, in a hot path. The change in the schedstats static key will be done with the following command:

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
usleep 500000
sysctl -w kernel.sched_schedstats=0
usleep 500000
done

In this way, they key will be updated twice per second. To force the hit of the int3 handler, the system will also run a kernel compilation with two jobs per CPU. The test machine is a two nodes/24 CPUs box with an Intel Xeon processor @2.27GHz.

Regarding the update part, on average, the regular kernel takes 57 ms to update the static key, while the kernel with the batch updates takes just 1.4 ms on average. Although it seems to be too good to be true, it makes sense: the sched_schedstats key is used in 56 places, so it was expected that it would take around 56 times to update the keys with the current implementation, as the IPIs are the most expensive part of the update.

Regarding the int3 handler, the non-batch handler takes 45 ns on average, while the batch version takes around 180 ns. At first glance, it seems to be a high value. But it is not, considering that it is doing 56 updates, rather than one! It is taking four times more, only. This gain is possible because the patch uses a binary search in the vector: log2(56)=5.8. So, it was expected to have an overhead within four times.

(voice of tv propaganda) But, that is not all! As the int3 handler keeps on for a shorter period (because the update part is on for a shorter time), the number of hits in the int3 handler decreased by 10%.

The question then is: Is it worth paying the price of "135 ns" more in the int3 handler?

Considering that, in this test case, we are saving the handling of 53 IPIs, that takes more than these 135 ns, it seems to be a meager price to be paid. Moreover, the test case was forcing the hit of the int3, in practice, it does not take that often. While the IPI takes place on all CPUs, hitting the int3 handler or not!

For instance, in an isolated CPU with a process running in user-space (nohz_full use-case), the chances of hitting the int3 handler is barely zero, while there is no way to avoid the IPIs. By bounding the IPIs, we are improving this scenario a lot.

Changes from v2:
- Switch the order of patches 8 and 9 (Steven Rostedt)
- Fallback in the case of failure in the batch mode (Steven Rostedt)
- Fix a pointer in patch 7 (Steven Rostedt)
- Adjust the commit log of the patch 1 (Borislav Petkov)
- Adjust the commit log of the patch 3 (Jiri Kosina/Thomas Gleixner)
Changes from v1:
- Split the patch in jump-label/x86-jump-label/alternative (Jason Baron)
- Use bserach in the int3 handler (Steven Rostedt)
- Use a pre-allocated page to store the vector (Jason/Steven)
- Do performance tests in the int3 handler (peterz)

Daniel Bristot de Oliveira (9):
jump_label: Add for_each_label_entry helper
jump_label: Add the jump_label_can_update_check() helper x86/jump_label: Move checking code away from __jump_label_transform() x86/jump_label: Add __jump_label_set_jump_code() helper x86/alternative: Split text_poke_bp() into tree steps
jump_label: Sort entries of the same key by the code x86/alternative: Batch of patch operations
jump_label: Batch updates if arch supports it x86/jump_label: Batch jump label updates

 arch/x86/include/asm/jump_label.h    |   2 +
 arch/x86/include/asm/text-patching.h |  15 +++
 arch/x86/kernel/alternative.c        | 140 ++++++++++++++++++---
 arch/x86/kernel/jump_label.c         | 174 ++++++++++++++++++++++-----
 include/linux/jump_label.h           |   6 +
 kernel/jump_label.c                  |  73 +++++++++--
 6 files changed, 359 insertions(+), 51 deletions(-)
Signature · 1 line
2.17.1
#1 lore raw

PATCH v3 1/9 jump_label: Add for_each_label_entry helper

Add a helper macro to make jump entry iteration code more readable.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 include/linux/jump_label.h | 3 +++
 kernel/jump_label.c        | 2 +-
 2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/jump_label.h +3 -0
index 5df6a621e464..c88d903befc0 100644
@@ -231,6 +231,9 @@ extern void static_key_disable(struct static_key *key);
 extern void static_key_enable_cpuslocked(struct static_key *key);
 extern void static_key_disable_cpuslocked(struct static_key *key);
 
+#define for_each_label_entry(key, entry, stop)				  \
+	for (; (entry < stop) && (jump_entry_key(entry) == key); entry++)
+
 /*
  * We should be using ATOMIC_INIT() for initializing .enabled, but
  * the inclusion of atomic.h is problematic for inclusion of jump_label.h
kernel/jump_label.c +1 -1
index b28028b08d44..65965eb1cf05 100644
@@ -381,7 +381,7 @@ static void __jump_label_update(struct static_key *key,
 				struct jump_entry *stop,
 				bool init)
 {
-	for (; (entry < stop) && (jump_entry_key(entry) == key); entry++) {
+	for_each_label_entry(key, entry, stop) {
 		/*
 		 * An entry->code of 0 indicates an entry which has been
 		 * disabled because it was in an init text area.
Signature · 1 line
2.17.1
#3 lore raw

PATCH v3 2/9 jump_label: Add the jump_label_can_update_check() helper

In reply to Daniel Bristot de Oliveira

Move the check of if a jump_entry is valid to a specific function. No functional change.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 kernel/jump_label.c | 30 ++++++++++++++++++++----------
 1 file changed, 20 insertions(+), 10 deletions(-)
kernel/jump_label.c +20 -10
index 65965eb1cf05..26bf54251218 100644
@@ -376,22 +376,32 @@ static enum jump_label_type jump_label_type(struct jump_entry *entry)
 	return enabled ^ branch;
 }
 
+bool jump_label_can_update_check(struct jump_entry *entry, bool init)
+{
+	/*
+	 * An entry->code of 0 indicates an entry which has been
+	 * disabled because it was in an init text area.
+	 */
+	if (init || !jump_entry_is_init(entry)) {
+		if (!kernel_text_address(jump_entry_code(entry))) {
+			WARN_ONCE(1, "can't patch jump_label at %pS",
+				  (void *)jump_entry_code(entry));
+			return 0;
+		}
+		return 1;
+	}
+	return 0;
+}
+
 static void __jump_label_update(struct static_key *key,
 				struct jump_entry *entry,
 				struct jump_entry *stop,
 				bool init)
 {
 	for_each_label_entry(key, entry, stop) {
-		/*
-		 * An entry->code of 0 indicates an entry which has been
-		 * disabled because it was in an init text area.
-		 */
-		if (init || !jump_entry_is_init(entry)) {
-			if (kernel_text_address(jump_entry_code(entry)))
-				arch_jump_label_transform(entry, jump_label_type(entry));
-			else
-				WARN_ONCE(1, "can't patch jump_label at %pS",
-					  (void *)jump_entry_code(entry));
+		if (jump_label_can_update_check(entry, init)) {
+			arch_jump_label_transform(entry,
+						  jump_label_type(entry));
 		}
 	}
 }
Signature · 1 line
2.17.1
#5 lore raw

PATCH v3 3/9 x86/jump_label: Move checking code away from __jump_label_transform()

In reply to Daniel Bristot de Oliveira

Move the check of the current code, before updating an entry, to specialized functions. No changes in the method, only code relocation.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/kernel/jump_label.c | 60 +++++++++++++++++++++++++-----------
 1 file changed, 42 insertions(+), 18 deletions(-)
arch/x86/kernel/jump_label.c +42 -18
index aac0c1f7e354..7894080bd02f 100644
@@ -37,16 +37,53 @@ static void bug_at(unsigned char *ip, int line)
 	BUG();
 }
 
+static inline void __jump_label_trans_check_enable(struct jump_entry *entry,
+						   enum jump_label_type type,
+						   const unsigned char *ideal_nop,
+						   int init)
+{
+	const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
+	const void *expect;
+	int line;
+
+	if (init) {
+		expect = default_nop; line = __LINE__;
+	} else {
+		expect = ideal_nop; line = __LINE__;
+	}
+
+	if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
+		bug_at((void *)jump_entry_code(entry), line);
+}
+
+static inline void __jump_label_trans_check_disable(struct jump_entry *entry,
+						    enum jump_label_type type,
+						    union jump_code_union *jmp,
+						    int init)
+{
+	const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
+	const void *expect;
+	int line;
+
+	if (init) {
+		expect = default_nop; line = __LINE__;
+	} else {
+		expect = jmp->code; line = __LINE__;
+	}
+
+	if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
+		bug_at((void *)jump_entry_code(entry), line);
+}
+
+
 static void __ref __jump_label_transform(struct jump_entry *entry,
 					 enum jump_label_type type,
 					 void *(*poker)(void *, const void *, size_t),
 					 int init)
 {
 	union jump_code_union jmp;
-	const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
 	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
-	const void *expect, *code;
-	int line;
+	const void *code;
 
 	jmp.jump = 0xe9;
 	jmp.offset = jump_entry_target(entry) -
@@ -56,26 +93,13 @@ static void __ref __jump_label_transform(struct jump_entry *entry,
 		poker = text_poke_early;
 
 	if (type == JUMP_LABEL_JMP) {
-		if (init) {
-			expect = default_nop; line = __LINE__;
-		} else {
-			expect = ideal_nop; line = __LINE__;
-		}
-
+		__jump_label_trans_check_enable(entry, type, ideal_nop, init);
 		code = &jmp.code;
 	} else {
-		if (init) {
-			expect = default_nop; line = __LINE__;
-		} else {
-			expect = &jmp.code; line = __LINE__;
-		}
-
+		__jump_label_trans_check_disable(entry, type, &jmp, init);
 		code = ideal_nop;
 	}
 
-	if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
-		bug_at((void *)jump_entry_code(entry), line);
-
 	/*
 	 * Make text_poke_bp() a default fallback poker.
 	 *
Signature · 1 line
2.17.1
#7 lore raw

PATCH v3 4/9 x86/jump_label: Add __jump_label_set_jump_code() helper

In reply to Daniel Bristot de Oliveira

Move the definition of the code to be written from __jump_label_transform() to a specialized function. No change in the method, code relocation only.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/kernel/jump_label.c | 38 +++++++++++++++++++++---------------
 1 file changed, 22 insertions(+), 16 deletions(-)
arch/x86/kernel/jump_label.c +22 -16
index 7894080bd02f..a039ac4ca5bf 100644
@@ -75,30 +75,36 @@ static inline void __jump_label_trans_check_disable(struct jump_entry *entry,
 		bug_at((void *)jump_entry_code(entry), line);
 }
 
+static void __jump_label_set_jump_code(struct jump_entry *entry,
+				       enum jump_label_type type,
+				       union jump_code_union *code,
+				       int init)
+{
+	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
+
+	code->jump = 0xe9;
+	code->offset = jump_entry_target(entry) -
+		     (jump_entry_code(entry) + JUMP_LABEL_NOP_SIZE);
+
+	if (type == JUMP_LABEL_JMP) {
+		__jump_label_trans_check_enable(entry, type, ideal_nop, init);
+	} else {
+		__jump_label_trans_check_disable(entry, type, code, init);
+		memcpy(code, ideal_nop, JUMP_LABEL_NOP_SIZE);
+	}
+}
 
 static void __ref __jump_label_transform(struct jump_entry *entry,
 					 enum jump_label_type type,
 					 void *(*poker)(void *, const void *, size_t),
 					 int init)
 {
-	union jump_code_union jmp;
-	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
-	const void *code;
-
-	jmp.jump = 0xe9;
-	jmp.offset = jump_entry_target(entry) -
-		     (jump_entry_code(entry) + JUMP_LABEL_NOP_SIZE);
+	union jump_code_union code;
 
 	if (early_boot_irqs_disabled)
 		poker = text_poke_early;
 
-	if (type == JUMP_LABEL_JMP) {
-		__jump_label_trans_check_enable(entry, type, ideal_nop, init);
-		code = &jmp.code;
-	} else {
-		__jump_label_trans_check_disable(entry, type, &jmp, init);
-		code = ideal_nop;
-	}
+	__jump_label_set_jump_code(entry, type, &code, init);
 
 	/*
 	 * Make text_poke_bp() a default fallback poker.
@@ -109,12 +115,12 @@ static void __ref __jump_label_transform(struct jump_entry *entry,
 	 *
 	 */
 	if (poker) {
-		(*poker)((void *)jump_entry_code(entry), code,
+		(*poker)((void *)jump_entry_code(entry), &code,
 			 JUMP_LABEL_NOP_SIZE);
 		return;
 	}
 
-	text_poke_bp((void *)jump_entry_code(entry), code, JUMP_LABEL_NOP_SIZE,
+	text_poke_bp((void *)jump_entry_code(entry), &code, JUMP_LABEL_NOP_SIZE,
 		     (void *)jump_entry_code(entry) + JUMP_LABEL_NOP_SIZE);
 }
 
Signature · 1 line
2.17.1
#9 lore raw

PATCH v3 5/9 x86/alternative: Split text_poke_bp() into tree steps

In reply to Daniel Bristot de Oliveira

text_poke_bp() updates instructions on live kernel on SMP in three steps:
1) add a int3 trap to the address that will be patched
2) update all but the first byte of the patched range
3) replace the first byte (int3) by the first byte of

This patch creates one function for each of these steps.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/kernel/alternative.c | 38 +++++++++++++++++++++++++----------
 1 file changed, 27 insertions(+), 11 deletions(-)
arch/x86/kernel/alternative.c +27 -11
index ebeac487a20c..6f5ad8587de0 100644
@@ -767,6 +767,29 @@ int poke_int3_handler(struct pt_regs *regs)
 
 }
 
+static void text_poke_bp_set_handler(void *addr, void *handler,
+				     unsigned char int3)
+{
+	bp_int3_handler = handler;
+	bp_int3_addr = (u8 *)addr + sizeof(int3);
+	text_poke(addr, &int3, sizeof(int3));
+}
+
+static void patch_all_but_first_byte(void *addr, const void *opcode,
+				     size_t len, unsigned char int3)
+{
+	/* patch all but the first byte */
+	text_poke((char *)addr + sizeof(int3),
+		  (const char *) opcode + sizeof(int3),
+		  len - sizeof(int3));
+}
+
+static void patch_first_byte(void *addr, const void *opcode, unsigned char int3)
+{
+	/* patch the first byte */
+	text_poke(addr, opcode, sizeof(int3));
+}
+
 /**
  * text_poke_bp() -- update instructions on live kernel on SMP
  * @addr:	address to patch
@@ -791,27 +814,21 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 {
 	unsigned char int3 = 0xcc;
 
-	bp_int3_handler = handler;
-	bp_int3_addr = (u8 *)addr + sizeof(int3);
-	bp_patching_in_progress = true;
-
 	lockdep_assert_held(&text_mutex);
 
+	bp_patching_in_progress = true;
 	/*
 	 * Corresponding read barrier in int3 notifier for making sure the
 	 * in_progress and handler are correctly ordered wrt. patching.
 	 */
 	smp_wmb();
 
-	text_poke(addr, &int3, sizeof(int3));
+	text_poke_bp_set_handler(addr, handler, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 
 	if (len - sizeof(int3) > 0) {
-		/* patch all but the first byte */
-		text_poke((char *)addr + sizeof(int3),
-			  (const char *) opcode + sizeof(int3),
-			  len - sizeof(int3));
+		patch_all_but_first_byte(addr, opcode, len, int3);
 		/*
 		 * According to Intel, this core syncing is very likely
 		 * not necessary and we'd be safe even without it. But
@@ -820,8 +837,7 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 		on_each_cpu(do_sync_core, NULL, 1);
 	}
 
-	/* patch the first byte */
-	text_poke(addr, opcode, sizeof(int3));
+	patch_first_byte(addr, opcode, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 	/*
Signature · 1 line
2.17.1
#11 lore raw

PATCH v3 6/9 jump_label: Sort entries of the same key by the code

In reply to Daniel Bristot de Oliveira

In the batching mode, entries with the same key should also be sorted by the code, enabling a bsearch() of a code/addr when updating a key.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 kernel/jump_label.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
kernel/jump_label.c +16 -0
index 26bf54251218..22093b5f57c9 100644
@@ -38,12 +38,28 @@ static int jump_label_cmp(const void *a, const void *b)
 	const struct jump_entry *jea = a;
 	const struct jump_entry *jeb = b;
 
+	/*
+	 * Entrires are sorted by key.
+	 */
 	if (jump_entry_key(jea) < jump_entry_key(jeb))
 		return -1;
 
 	if (jump_entry_key(jea) > jump_entry_key(jeb))
 		return 1;
 
+#ifdef HAVE_JUMP_LABEL_BATCH
+	/*
+	 * In the batching mode, entries should also be sorted by the code
+	 * inside the already sorted list of entries, enabling a bsearch in
+	 * the vector.
+	 */
+	if (jump_entry_code(jea) < jump_entry_code(jeb))
+		return -1;
+
+	if (jump_entry_code(jea) > jump_entry_code(jeb))
+		return 1;
+#endif
+
 	return 0;
 }
 
Signature · 1 line
2.17.1
#13 lore raw

PATCH v3 7/9 x86/alternative: Batch of patch operations

In reply to Daniel Bristot de Oliveira

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +102 -6

151 lines not on this page · raw message

Signature · 1 line
2.17.1
#21 lore raw

PATCH v3 8/9 jump_label: Batch updates if arch supports it

In reply to Daniel Bristot de Oliveira

If the architecture supports the batching of jump label updates, use it!

An easy way to see the benefits of this patch is switching the schedstats on and off. For instance:

-------------------------- %< ---------------------------- #!/bin/bash

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
sleep 2
sysctl -w kernel.sched_schedstats=0
sleep 2
done
-------------------------- >% ----------------------------

while watching the IPI count:

-------------------------- %< ----------------------------

# watch -n1 "cat /proc/interrupts | grep Function"
-------------------------- >% ----------------------------

With the current mode, it is possible to see +- 168 IPIs each 2 seconds, while with this patch the number of IPIs goes to 3 each 2 seconds.

Regarding the performance impact of this patch set, I made two measurements:

The time to update a key (the task that is causing the change) The time to run the int3 handler (the side effect on a thread that
hits the code being changed)

The schedstats static key was chosen as the key to being switched on and off. The reason being is that it is used in more than 56 places, in a hot path. The change in the schedstats static key will be done with the following command:

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
usleep 500000
sysctl -w kernel.sched_schedstats=0
usleep 500000
done

In this way, they key will be updated twice per second. To force the hit of the int3 handler, the system will also run a kernel compilation with two jobs per CPU. The test machine is a two nodes/24 CPUs box with an Intel Xeon processor @2.27GHz.

Regarding the update part, on average, the regular kernel takes 57 ms to update the schedstats key, while the kernel with the batch updates takes just 1.4 ms on average. Although it seems to be too good to be true, it makes sense: the schedstats key is used in 56 places, so it was expected that it would take around 56 times to update the keys with the current implementation, as the IPIs are the most expensive part of the update.

Regarding the int3 handler, the non-batch handler takes 45 ns on average, while the batch version takes around 180 ns. At first glance, it seems to be a high value. But it is not, considering that it is doing 56 updates, rather than one! It is taking four times more, only. This gain is possible because the patch uses a binary search in the vector: log2(56)=5.8. So, it was expected to have an overhead within four times.

(voice of tv propaganda) But, that is not all! As the int3 handler keeps on for a shorter period (because the update part is on for a shorter time), the number of hits in the int3 handler decreased by 10%.

The question then is: Is it worth paying the price of "135 ns" more in the int3 handler?

Considering that, in this test case, we are saving the handling of 53 IPIs, that takes more than these 135 ns, it seems to be a meager price to be paid. Moreover, the test case was forcing the hit of the int3, in practice, it does not take that often. While the IPI takes place on all CPUs, hitting the int3 handler or not!

For instance, in an isolated CPU with a process running in user-space (nohz_full use-case), the chances of hitting the int3 handler is barely zero, while there is no way to avoid the IPIs. By bounding the IPIs, we are improving a lot this scenario.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 include/linux/jump_label.h |  3 +++
 kernel/jump_label.c        | 29 +++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+)
include/linux/jump_label.h +3 -0
index c88d903befc0..ed51ef3e1abd 100644
@@ -219,6 +219,9 @@ extern void arch_jump_label_transform(struct jump_entry *entry,
 				      enum jump_label_type type);
 extern void arch_jump_label_transform_static(struct jump_entry *entry,
 					     enum jump_label_type type);
+extern int arch_jump_label_transform_queue(struct jump_entry *entry,
+					    enum jump_label_type type);
+extern void arch_jump_label_transform_apply(void);
 extern int jump_label_text_reserved(void *start, void *end);
 extern void static_key_slow_inc(struct static_key *key);
 extern void static_key_slow_dec(struct static_key *key);
kernel/jump_label.c +29 -0
index 22093b5f57c9..08ace142af0a 100644
@@ -409,6 +409,7 @@ bool jump_label_can_update_check(struct jump_entry *entry, bool init)
 	return 0;
 }
 
+#ifndef HAVE_JUMP_LABEL_BATCH
 static void __jump_label_update(struct static_key *key,
 				struct jump_entry *entry,
 				struct jump_entry *stop,
@@ -421,6 +422,34 @@ static void __jump_label_update(struct static_key *key,
 		}
 	}
 }
+#else
+static void __jump_label_update(struct static_key *key,
+				struct jump_entry *entry,
+				struct jump_entry *stop,
+				bool init)
+{
+	for_each_label_entry(key, entry, stop) {
+
+		if (!jump_label_can_update_check(entry, init))
+			continue;
+
+		if (arch_jump_label_transform_queue(entry,
+						    jump_label_type(entry)))
+			continue;
+
+		/*
+		 * Queue's overflow: Apply the current queue, and then
+		 * queue again. If it stills not possible to queue, BUG!
+		 */
+		arch_jump_label_transform_apply();
+		if (!arch_jump_label_transform_queue(entry,
+						     jump_label_type(entry))) {
+			BUG();
+		}
+	}
+	arch_jump_label_transform_apply();
+}
+#endif
 
 void __init jump_label_init(void)
 {
Signature · 1 line
2.17.1
#23 lore raw

PATCH v3 9/9 x86/jump_label: Batch jump label updates

In reply to Daniel Bristot de Oliveira

Currently, the jump label of a static key is transformed via the arch specific function:

void arch_jump_label_transform(struct jump_entry *entry,
enum jump_label_type type)

The new approach (batch mode) uses two arch functions, the first has the same arguments of the arch_jump_label_transform(), and is the function:

void arch_jump_label_transform_queue(struct jump_entry *entry,
enum jump_label_type type)

Rather than transforming the code, it adds the jump_entry in a queue of entries to be updated. This functions returns 1 in the case of a successful enqueue of an entry. If it returns 0, the caller must to apply the queue and then try to queue again, for instance, because the queue is full.

This function expects the caller to sort the entries by the address before enqueueuing then. This is already done by the arch independent code, though.

After queuing all jump_entries, the function:

void arch_jump_label_transform_apply(void)

Applies the changes in the queue.

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/jump_label.h |  2 +
 arch/x86/kernel/jump_label.c      | 88 +++++++++++++++++++++++++++++++
 2 files changed, 90 insertions(+)
arch/x86/include/asm/jump_label.h +2 -0
index a5fb34fe56a4..39f908e8c0d1 100644
@@ -2,6 +2,8 @@
 #ifndef _ASM_X86_JUMP_LABEL_H
 #define _ASM_X86_JUMP_LABEL_H
 
+#define HAVE_JUMP_LABEL_BATCH
+
 #define JUMP_LABEL_NOP_SIZE 5
 
 #ifdef CONFIG_X86_64
arch/x86/kernel/jump_label.c +88 -0

100 lines not on this page · raw message

Signature · 1 line
2.17.1
#25 lore raw
In reply to Daniel Bristot de Oliveira
Quoted 199 lines · Daniel Bristot de Oliveira

While tuning a system with CPUs isolated as much as possible, we've noticed that isolated CPUs were receiving bursts of 12 IPIs, periodically. Tracing the functions that emit IPIs, we saw chronyd - an unprivileged process - generating the IPIs when changing a static key, enabling network timestaping on sockets.

For instance, the trace pointed:

# trace-cmd record --func-stack -p function -l smp_call_function_single -e irq_vectors -f 'vector == 251'...
# trace-cmde report...
[...]
         chronyd-858   [000]   433.286406: function:             smp_call_function_single
         chronyd-858   [000]   433.286408: kernel_stack:         <stack trace>
=> smp_call_function_many (ffffffffbc10ab22)
=> smp_call_function (ffffffffbc10abaa)
=> on_each_cpu (ffffffffbc10ac0b)
=> text_poke_bp (ffffffffbc02436a)
=> arch_jump_label_transform (ffffffffbc020ec8)
=> __jump_label_update (ffffffffbc1b300f)
=> jump_label_update (ffffffffbc1b30ed)
=> static_key_slow_inc (ffffffffbc1b334d)
=> net_enable_timestamp (ffffffffbc625c44)
=> sock_enable_timestamp (ffffffffbc6127d5)
=> sock_setsockopt (ffffffffbc612d2f)
=> SyS_setsockopt (ffffffffbc60d5e6)
=> tracesys (ffffffffbc7681c5)
          <idle>-0     [001]   433.286416: call_function_single_entry: vector=251
          <idle>-0     [001]   433.286419: call_function_single_exit: vector=251

[... The IPI takes place 12 times]

The static key in case was the netstamp_needed_key. A static key change from enabled->disabled/disabled->enabled causes the code to be patched, and this is done in three steps:

-- Pseudo-code #1 - Current implementation ---
For each key to be updated:
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

As the static key netstamp_needed_key has four entries (used in for places in the code) in our kernel, 3 IPIs were generated for each entry, resulting in 12 IPIs. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling is _not_ running.

Rather than doing each updated at once, it is possible to queue all updates first, and then apply all updates at once, rewriting the pseudo-code #1 in this way:

-- Pseudo-code #2 - proposal ---
1) for each key in the queue:
add an int3 trap to the address that will be patched
sync cores (send IPI to all other CPUs)

2) for each key in the queue:
update all but the first byte of the patched range
sync cores (send IPI to all other CPUs)

3) for each key in the queue:
replace the first byte (int3) by the first byte of replacing opcode
sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - proposal ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

Currently, the jump label of a static key is transformed via the arch specific function:

void arch_jump_label_transform(struct jump_entry *entry,
enum jump_label_type type)

The new approach (batch mode) uses two arch functions, the first has the same arguments of the arch_jump_label_transform(), and is the function:

void arch_jump_label_transform_queue(struct jump_entry *entry,
enum jump_label_type type)

Rather than transforming the code, it adds the jump_entry in a queue of entries to be updated.

After queuing all jump_entries, the function:

void arch_jump_label_transform_apply(void)

Applies the changes in the queue.

One easy way to see the benefits of this patch is switching the schedstats on and off. For instance:

-------------------------- %< ---------------------------- #!/bin/bash

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
sleep 2
sysctl -w kernel.sched_schedstats=0
sleep 2
done
-------------------------- >% ----------------------------

while watching the IPI count:

-------------------------- %< ----------------------------

# watch -n1 "cat /proc/interrupts | grep Function"
-------------------------- >% ----------------------------

With the current mode, it is possible to see +- 168 IPIs each 2 seconds, while with the batch mode the number of IPIs goes to 3 each 2 seconds.

Regarding the performance impact of this patch set, I made two measurements:

The time to update a key (the task that is causing the change) The time to run the int3 handler (the side effect on a thread that
hits the code being changed)

The sched_schedstats static key was chosen as the key to being switched on and off. The reason being is that it is used in more than 56 places, in a hot path. The change in the schedstats static key will be done with the following command:

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
usleep 500000
sysctl -w kernel.sched_schedstats=0
usleep 500000
done

In this way, they key will be updated twice per second. To force the hit of the int3 handler, the system will also run a kernel compilation with two jobs per CPU. The test machine is a two nodes/24 CPUs box with an Intel Xeon processor @2.27GHz.

Regarding the update part, on average, the regular kernel takes 57 ms to update the static key, while the kernel with the batch updates takes just 1.4 ms on average. Although it seems to be too good to be true, it makes sense: the sched_schedstats key is used in 56 places, so it was expected that it would take around 56 times to update the keys with the current implementation, as the IPIs are the most expensive part of the update.

Regarding the int3 handler, the non-batch handler takes 45 ns on average, while the batch version takes around 180 ns. At first glance, it seems to be a high value. But it is not, considering that it is doing 56 updates, rather than one! It is taking four times more, only. This gain is possible because the patch uses a binary search in the vector: log2(56)=5.8. So, it was expected to have an overhead within four times.

(voice of tv propaganda) But, that is not all! As the int3 handler keeps on for a shorter period (because the update part is on for a shorter time), the number of hits in the int3 handler decreased by 10%.

The question then is: Is it worth paying the price of "135 ns" more in the int3 handler?

Considering that, in this test case, we are saving the handling of 53 IPIs, that takes more than these 135 ns, it seems to be a meager price to be paid. Moreover, the test case was forcing the hit of the int3, in practice, it does not take that often. While the IPI takes place on all CPUs, hitting the int3 handler or not!

For instance, in an isolated CPU with a process running in user-space (nohz_full use-case), the chances of hitting the int3 handler is barely zero, while there is no way to avoid the IPIs. By bounding the IPIs, we are improving this scenario a lot.

Changes from v2:
- Switch the order of patches 8 and 9 (Steven Rostedt)
- Fallback in the case of failure in the batch mode (Steven Rostedt)
- Fix a pointer in patch 7 (Steven Rostedt)
- Adjust the commit log of the patch 1 (Borislav Petkov)
- Adjust the commit log of the patch 3 (Jiri Kosina/Thomas Gleixner)
Changes from v1:
- Split the patch in jump-label/x86-jump-label/alternative (Jason Baron)
- Use bserach in the int3 handler (Steven Rostedt)
- Use a pre-allocated page to store the vector (Jason/Steven)
- Do performance tests in the int3 handler (peterz)

Daniel Bristot de Oliveira (9):
jump_label: Add for_each_label_entry helper
jump_label: Add the jump_label_can_update_check() helper x86/jump_label: Move checking code away from __jump_label_transform() x86/jump_label: Add __jump_label_set_jump_code() helper x86/alternative: Split text_poke_bp() into tree steps
jump_label: Sort entries of the same key by the code x86/alternative: Batch of patch operations
jump_label: Batch updates if arch supports it x86/jump_label: Batch jump label updates

Quoted 8 lines
 arch/x86/include/asm/jump_label.h    |   2 +
 arch/x86/include/asm/text-patching.h |  15 +++
 arch/x86/kernel/alternative.c        | 140 ++++++++++++++++++---
 arch/x86/kernel/jump_label.c         | 174 ++++++++++++++++++++++-----
 include/linux/jump_label.h           |   6 +
 kernel/jump_label.c                  |  73 +++++++++--
 6 files changed, 359 insertions(+), 51 deletions(-)

Hi,

This is just a gentle ping... Any thoughts about this patch series?

Thanks!
-- Daniel

#14 lore raw

Re: [PATCH V3 7/9] x86/alternative: Batch of patch operations

In reply to Daniel Bristot de Oliveira

Hi Daniel,

Quoted 157 lines · On Fri, 21 Dec 2018 11:27:32 +0100 Daniel Bristot de Oliveira…

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +23 -0
index 6f5ad8587de0..8fa47e5ec709 100644
@@ -21,6 +21,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +739,32 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
+/*
+ * Single poke.
+ */
 static void *bp_int3_handler, *bp_int3_addr;
+/*
+ * Batching poke.
+ */
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +780,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 788

Quoted 10 lines
arch/x86/kernel/alternative.c +4 -3
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	/*
+	 * Single poke first.
+	 */

I wonder why would you separate single poke and batch poke? It seems a single poke is just a case that bp_int3_tpv_nr == 1. If so, you can remove bp_int3_addr and this block.

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 800

Quoted 13 lines
arch/x86/kernel/alternative.c +11 -1
+	if (bp_int3_addr) {
+		if (regs->ip == (unsigned long) bp_int3_addr) {
+			regs->ip = (unsigned long) bp_int3_handler;
+			return 1;
+		}
+		return 0;
+	}
 
-	return 1;
+	/*
+	 * Batch mode.
+	 */
+	if (bp_int3_tpv_nr) {

if (unlikely(bp_int3_tpv_nr))

Sorry about interrupting, but this is a "hot-path" when we use kprobes.

Also, could you add NOKPROBE_SYMBOL(); for all symbols involved in this process?
Recently I found I missed it for poke_int3_handler and sent a fix. ( https://www.mail-archive.com/[email protected]/msg1898241.html ) If this increase the function-call-chain from poke_int3_handler, those must be marked as NOKPROBE_SYMBOL().

But basically this series looks good to me.

Thank you,

Quoted 92 lines
arch/x86/kernel/alternative.c +64 -2
+		ip = (void *) regs->ip - sizeof(unsigned char);
+		tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
+			     sizeof(struct text_to_poke),
+			     text_bp_batch_bsearch);
+		if (tp) {
+			/* set up the specified breakpoint handler */
+			regs->ip = (unsigned long) tp->handler;
+			return 1;
+		}
+	}
 
+	return 0;
 }
 
 static void text_poke_bp_set_handler(void *addr, void *handler,
 				     unsigned char int3)
 {
-	bp_int3_handler = handler;
-	bp_int3_addr = (u8 *)addr + sizeof(int3);
 	text_poke(addr, &int3, sizeof(int3));
 }
 
@@ -816,6 +859,9 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 
 	lockdep_assert_held(&text_mutex);
 
+	bp_int3_handler = handler;
+	bp_int3_addr = (u8 *)addr + sizeof(int3);
+
 	bp_patching_in_progress = true;
 	/*
 	 * Corresponding read barrier in int3 notifier for making sure the
@@ -846,6 +892,56 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 	 */
 	bp_patching_in_progress = false;
 
+	bp_int3_handler = bp_int3_addr = 0;
 	return addr;
 }
 
+void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries)
+{
+	unsigned int i;
+	unsigned char int3 = 0xcc;
+	int patched_all_but_first = 0;
+
+	bp_int3_tpv = tp;
+	bp_int3_tpv_nr = nr_entries;
+	bp_patching_in_progress = true;
+	/*
+	 * Corresponding read barrier in int3 notifier for making sure the
+	 * in_progress and handler are correctly ordered wrt. patching.
+	 */
+	smp_wmb();
+
+	for (i = 0; i < nr_entries; i++)
+		text_poke_bp_set_handler(tp[i].addr, tp[i].handler, int3);
+
+	on_each_cpu(do_sync_core, NULL, 1);
+
+	for (i = 0; i < nr_entries; i++) {
+		if (tp[i].len - sizeof(int3) > 0) {
+			patch_all_but_first_byte(tp[i].addr, tp[i].opcode,
+						 tp[i].len, int3);
+			patched_all_but_first++;
+		}
+	}
+
+	if (patched_all_but_first) {
+		/*
+		 * According to Intel, this core syncing is very likely
+		 * not necessary and we'd be safe even without it. But
+		 * better safe than sorry (plus there's not only Intel).
+		 */
+		on_each_cpu(do_sync_core, NULL, 1);
+	}
+
+	for (i = 0; i < nr_entries; i++)
+		patch_first_byte(tp[i].addr, tp[i].opcode, int3);
+
+	on_each_cpu(do_sync_core, NULL, 1);
+	/*
+	 * sync_core() implies an smp_mb() and orders this store against
+	 * the writing of the new instruction.
+	 */
+	bp_int3_tpv_nr = 0;
+	bp_int3_tpv = NULL;
+	bp_patching_in_progress = false;
+}
Signature · 1 line
2.17.1
Signature · 1 line
Masami Hiramatsu <[email protected]>
#15 lore raw

Re: [PATCH V3 7/9] x86/alternative: Batch of patch operations

Quoted 167 lines · Masami Hiramatsu

Hi Daniel,

Quoted 162 lines · On Fri, 21 Dec 2018 11:27:32 +0100 Daniel Bristot de Oliveira…

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +24 -1
index 6f5ad8587de0..8fa47e5ec709 100644
@@ -21,6 +21,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +739,32 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
+/*
+ * Single poke.
+ */
 static void *bp_int3_handler, *bp_int3_addr;
+/*
+ * Batching poke.
+ */
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +780,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
Quoted 8 lines

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 788

Quoted 5 lines
arch/x86/kernel/alternative.c +3 -2
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	/*
+	 * Single poke first.
+	 */

I wonder why would you separate single poke and batch poke? It seems a single poke is just a case that bp_int3_tpv_nr == 1.

Hi Masami!

The single poke is used only at the boot time, before the system is able to allocate memory. After that, the batch mode becomes the default.

I was thinking to make one function to each method, but then I would have to change the do_int3() and manage how to switch between one and the other without further overhead. I was planing to do this in a second round of improvements.

Quoted 18 lines

If so, you can remove bp_int3_addr and this block.

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 800

Quoted 13 lines
arch/x86/kernel/alternative.c +11 -1
+	if (bp_int3_addr) {
+		if (regs->ip == (unsigned long) bp_int3_addr) {
+			regs->ip = (unsigned long) bp_int3_handler;
+			return 1;
+		}
+		return 0;
+	}
 
-	return 1;
+	/*
+	 * Batch mode.
+	 */
+	if (bp_int3_tpv_nr) {

if (unlikely(bp_int3_tpv_nr))

Quoted 1 line

Sorry about interrupting, but this is a "hot-path" when we use kprobes.

No problem at all! :-)

I will change this function to better deal with the hot-path (the default mode after the system boots up).

how about something like this:
------------------ %< ------------------
int poke_int3_handler(struct pt_regs *regs)

{
        void *ip;
        struct text_to_poke *tp;

        /*
         * Having observed our INT3 instruction, we now must observe
         * bp_patching_in_progress.
         *
         *      in_progress = TRUE              INT3
         *      WMB                             RMB
         *      write INT3                      if (in_progress)
         *
         * Idem for bp_int3_handler.
         */
        smp_rmb();

        if (likely(!bp_patching_in_progress))
                return 0;

        if (user_mode(regs))
                return 0;

        /*
         * Single poke is only used at the boot.
         */
        if (unlikely(!bp_int3_tpv))
                goto single_poke;

        ip = (void *) regs->ip - sizeof(unsigned char);
        tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
                     sizeof(struct text_to_poke),
                     text_bp_batch_bsearch);
        if (tp) {
                /* set up the specified breakpoint handler */
                regs->ip = (unsigned long) tp->handler;
                return 1;
        }

        return 0;

single_poke:

        if (regs->ip == (unsigned long) bp_int3_addr) {
                regs->ip = (unsigned long) bp_int3_handler;
                return 1;
        }

        return 0;
}

------------- >% ----------

In this way the default code is up, and the only 'if' I am using is a var of the batch mode (that will be used later). If are are still at the boot, we are jumping to the end of the function.

look better?

Quoted 7 lines

Also, could you add NOKPROBE_SYMBOL(); for all symbols involved in this process?
Recently I found I missed it for poke_int3_handler and sent a fix. ( https://www.mail-archive.com/[email protected]/msg1898241.html ) If this increase the function-call-chain from poke_int3_handler, those must be marked as NOKPROBE_SYMBOL().

Ack! Doing that!

Thanks!

#16 lore raw

Re: [PATCH V3 7/9] x86/alternative: Batch of patch operations

Quoted 177 lines · On Sat, 26 Jan 2019 12:52:15 +0100 Daniel Bristot de Oliveira…
Quoted 167 lines · Masami Hiramatsu

Hi Daniel,

Quoted 162 lines · On Fri, 21 Dec 2018 11:27:32 +0100 Daniel Bristot de Oliveira…

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +24 -1
index 6f5ad8587de0..8fa47e5ec709 100644
@@ -21,6 +21,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +739,32 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
+/*
+ * Single poke.
+ */
 static void *bp_int3_handler, *bp_int3_addr;
+/*
+ * Batching poke.
+ */
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +780,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
Quoted 8 lines

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 788

Quoted 5 lines
arch/x86/kernel/alternative.c +3 -2
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	/*
+	 * Single poke first.
+	 */

I wonder why would you separate single poke and batch poke? It seems a single poke is just a case that bp_int3_tpv_nr == 1.

Quoted 4 lines

Hi Masami!

The single poke is used only at the boot time, before the system is able to allocate memory. After that, the batch mode becomes the default.

Hmm, what's the difference from text_poke_early()?

Quoted 4 lines

I was thinking to make one function to each method, but then I would have to change the do_int3() and manage how to switch between one and the other without further overhead. I was planing to do this in a second round of improvements.

I didn't think such big change.
I just thought we could allocate single entry array on stack, something like

text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)

{
	struct text_to_poke tp = {.handler = handler, .addr = addr, .len = len};
	if (len > POKE_MAX_OPCODE_SIZE)
		return -E2BIG;
	memcpy(tp.opcode, opcode, len);
	return text_poke_bp_batch(&tp, 1);
}
Quoted 19 lines
Quoted 19 lines

If so, you can remove bp_int3_addr and this block.

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 800

Quoted 13 lines
arch/x86/kernel/alternative.c +11 -1
+	if (bp_int3_addr) {
+		if (regs->ip == (unsigned long) bp_int3_addr) {
+			regs->ip = (unsigned long) bp_int3_handler;
+			return 1;
+		}
+		return 0;
+	}
 
-	return 1;
+	/*
+	 * Batch mode.
+	 */
+	if (bp_int3_tpv_nr) {

if (unlikely(bp_int3_tpv_nr))

Quoted 3 lines
Quoted 1 line

Sorry about interrupting, but this is a "hot-path" when we use kprobes.

No problem at all! :-)

Thanks! :-)

Quoted 55 lines

I will change this function to better deal with the hot-path (the default mode after the system boots up).

how about something like this:
------------------ %< ------------------
int poke_int3_handler(struct pt_regs *regs)

{
        void *ip;
        struct text_to_poke *tp;

        /*
         * Having observed our INT3 instruction, we now must observe
         * bp_patching_in_progress.
         *
         *      in_progress = TRUE              INT3
         *      WMB                             RMB
         *      write INT3                      if (in_progress)
         *
         * Idem for bp_int3_handler.
         */
        smp_rmb();

        if (likely(!bp_patching_in_progress))
                return 0;

        if (user_mode(regs))
                return 0;

        /*
         * Single poke is only used at the boot.
         */
        if (unlikely(!bp_int3_tpv))
                goto single_poke;

        ip = (void *) regs->ip - sizeof(unsigned char);
        tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
                     sizeof(struct text_to_poke),
                     text_bp_batch_bsearch);
        if (tp) {
                /* set up the specified breakpoint handler */
                regs->ip = (unsigned long) tp->handler;
                return 1;
        }

        return 0;

single_poke:

        if (regs->ip == (unsigned long) bp_int3_addr) {
                regs->ip = (unsigned long) bp_int3_handler;
                return 1;
        }

        return 0;
}
Quoted 7 lines

------------- >% ----------

In this way the default code is up, and the only 'if' I am using is a var of the batch mode (that will be used later). If are are still at the boot, we are jumping to the end of the function.

look better?

yeah, it looks much better. But I just wonder why don't you consolidate both by just because reducing code.

Quoted 10 lines
Quoted 8 lines

Also, could you add NOKPROBE_SYMBOL(); for all symbols involved in this process?
Recently I found I missed it for poke_int3_handler and sent a fix. ( https://www.mail-archive.com/[email protected]/msg1898241.html ) If this increase the function-call-chain from poke_int3_handler, those must be marked as NOKPROBE_SYMBOL().

Ack! Doing that!

Thank you!

Quoted 2 lines

Thanks!

Signature · 1 line
Masami Hiramatsu <[email protected]>
#17 lore raw

Re: [PATCH V3 7/9] x86/alternative: Batch of patch operations

Quoted 180 lines · Masami Hiramatsu
Quoted 177 lines · On Sat, 26 Jan 2019 12:52:15 +0100 Daniel Bristot de Oliveira…
Quoted 175 lines · Masami Hiramatsu

Hi Daniel,

Quoted 157 lines · On Fri, 21 Dec 2018 11:27:32 +0100 Daniel Bristot de Oliveira…

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +23 -0
index 6f5ad8587de0..8fa47e5ec709 100644
@@ -21,6 +21,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +739,32 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
+/*
+ * Single poke.
+ */
 static void *bp_int3_handler, *bp_int3_addr;
+/*
+ * Batching poke.
+ */
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +780,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 788

Quoted 10 lines
arch/x86/kernel/alternative.c +4 -3
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	/*
+	 * Single poke first.
+	 */

I wonder why would you separate single poke and batch poke? It seems a single poke is just a case that bp_int3_tpv_nr == 1.

Quoted 6 lines
Quoted 4 lines

Hi Masami!

The single poke is used only at the boot time, before the system is able to allocate memory. After that, the batch mode becomes the default.

Hmm, what's the difference from text_poke_early()?

text_poke_early(): before enabling interrupts at boot.

text_poke_bp(): after enabling interrupts, before being able to allocate memory, or in the error handling with batch mode.

task_poke_batch(): After enabling interrupts and being able to allocate memory.

Quoted 7 lines
Quoted 4 lines

I was thinking to make one function to each method, but then I would have to change the do_int3() and manage how to switch between one and the other without further overhead. I was planing to do this in a second round of improvements.

I didn't think such big change.
I just thought we could allocate single entry array on stack, something like

Ah!

Quoted 8 lines

text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)

{
	struct text_to_poke tp = {.handler = handler, .addr = addr, .len = len};
	if (len > POKE_MAX_OPCODE_SIZE)
		return -E2BIG;
	memcpy(tp.opcode, opcode, len);
	return text_poke_bp_batch(&tp, 1);
}

Good idea!

Quoted 82 lines
Quoted 19 lines
Quoted 19 lines

If so, you can remove bp_int3_addr and this block.

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 800

Quoted 13 lines
arch/x86/kernel/alternative.c +11 -1
+	if (bp_int3_addr) {
+		if (regs->ip == (unsigned long) bp_int3_addr) {
+			regs->ip = (unsigned long) bp_int3_handler;
+			return 1;
+		}
+		return 0;
+	}
 
-	return 1;
+	/*
+	 * Batch mode.
+	 */
+	if (bp_int3_tpv_nr) {

if (unlikely(bp_int3_tpv_nr))

Quoted 3 lines
Quoted 1 line

Sorry about interrupting, but this is a "hot-path" when we use kprobes.

No problem at all! :-)

Thanks! :-)

Quoted 57 lines

I will change this function to better deal with the hot-path (the default mode after the system boots up).

how about something like this:
------------------ %< ------------------
int poke_int3_handler(struct pt_regs *regs)

{
        void *ip;
        struct text_to_poke *tp;

        /*
         * Having observed our INT3 instruction, we now must observe
         * bp_patching_in_progress.
         *
         *      in_progress = TRUE              INT3
         *      WMB                             RMB
         *      write INT3                      if (in_progress)
         *
         * Idem for bp_int3_handler.
         */
        smp_rmb();

        if (likely(!bp_patching_in_progress))
                return 0;

        if (user_mode(regs))
                return 0;

        /*
         * Single poke is only used at the boot.
         */
        if (unlikely(!bp_int3_tpv))
                goto single_poke;

        ip = (void *) regs->ip - sizeof(unsigned char);
        tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
                     sizeof(struct text_to_poke),
                     text_bp_batch_bsearch);
        if (tp) {
                /* set up the specified breakpoint handler */
                regs->ip = (unsigned long) tp->handler;
                return 1;
        }

        return 0;

single_poke:

        if (regs->ip == (unsigned long) bp_int3_addr) {
                regs->ip = (unsigned long) bp_int3_handler;
                return 1;
        }

        return 0;
}

------------- >% ----------

Quoted 9 lines
Quoted 5 lines

In this way the default code is up, and the only 'if' I am using is a var of the batch mode (that will be used later). If are are still at the boot, we are jumping to the end of the function.

look better?

yeah, it looks much better. But I just wonder why don't you consolidate both by just because reducing code.

and so I did. How about something like this?
---------- %< ---------

---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 118 +++++++++++++++++++--------
 lib/bsearch.c                        |   2 +
 3 files changed, 100 insertions(+), 35 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +83 -35

185 lines not on this page · raw message

lib/bsearch.c +2 -0
index 18b445b010c3..82512fe7b33c 100644
@@ -11,6 +11,7 @@
 
 #include <linux/export.h>
 #include <linux/bsearch.h>
+#include <linux/kprobes.h>
 
 /*
  * bsearch - binary search an array of elements
@@ -53,3 +54,4 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	return NULL;
 }
 EXPORT_SYMBOL(bsearch);
+NOKPROBE_SYMBOL(bsearch);
Signature · 5 lines
If so, I will send a v4 with this ideia.

Thanks!

-- Daniel
Reviewed-by
#18 lore raw

Re: [PATCH V3 7/9] x86/alternative: Batch of patch operations

Hi Daniel,

Quoted 186 lines · On Fri, 1 Feb 2019 13:49:32 +0100 Daniel Bristot de Oliveira…
Quoted 185 lines · Masami Hiramatsu
Quoted 181 lines · On Sat, 26 Jan 2019 12:52:15 +0100 Daniel Bristot de Oliveira…
Quoted 167 lines · Masami Hiramatsu

Hi Daniel,

Quoted 162 lines · On Fri, 21 Dec 2018 11:27:32 +0100 Daniel Bristot de Oliveira…

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +24 -1
index 6f5ad8587de0..8fa47e5ec709 100644
@@ -21,6 +21,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +739,32 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
+/*
+ * Single poke.
+ */
 static void *bp_int3_handler, *bp_int3_addr;
+/*
+ * Batching poke.
+ */
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +780,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
Quoted 8 lines

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 785

Quoted 5 lines
arch/x86/kernel/alternative.c +3 -2
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	/*
+	 * Single poke first.
+	 */

I wonder why would you separate single poke and batch poke? It seems a single poke is just a case that bp_int3_tpv_nr == 1.

Hi Masami!

The single poke is used only at the boot time, before the system is able to allocate memory. After that, the batch mode becomes the default.

Quoted 8 lines
Quoted 1 line

Hmm, what's the difference from text_poke_early()?

text_poke_early(): before enabling interrupts at boot.

text_poke_bp(): after enabling interrupts, before being able to allocate memory, or in the error handling with batch mode.

task_poke_batch(): After enabling interrupts and being able to allocate memory.

OK, I got it. Maybe we should document this for future users.

Quoted 106 lines
Quoted 6 lines
Quoted 3 lines

I was thinking to make one function to each method, but then I would have to change the do_int3() and manage how to switch between one and the other without further overhead. I was planing to do this in a second round of improvements.

I didn't think such big change.
I just thought we could allocate single entry array on stack, something like

Ah!

Quoted 8 lines

text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)

{
	struct text_to_poke tp = {.handler = handler, .addr = addr, .len = len};
	if (len > POKE_MAX_OPCODE_SIZE)
		return -E2BIG;
	memcpy(tp.opcode, opcode, len);
	return text_poke_bp_batch(&tp, 1);
}

Good idea!

Quoted 86 lines
Quoted 19 lines
Quoted 19 lines

If so, you can remove bp_int3_addr and this block.

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 800

Quoted 13 lines
arch/x86/kernel/alternative.c +11 -1
+	if (bp_int3_addr) {
+		if (regs->ip == (unsigned long) bp_int3_addr) {
+			regs->ip = (unsigned long) bp_int3_handler;
+			return 1;
+		}
+		return 0;
+	}
 
-	return 1;
+	/*
+	 * Batch mode.
+	 */
+	if (bp_int3_tpv_nr) {

if (unlikely(bp_int3_tpv_nr))

Quoted 3 lines
Quoted 1 line

Sorry about interrupting, but this is a "hot-path" when we use kprobes.

No problem at all! :-)

Thanks! :-)

Quoted 61 lines

I will change this function to better deal with the hot-path (the default mode after the system boots up).

how about something like this:
------------------ %< ------------------
int poke_int3_handler(struct pt_regs *regs)

{
        void *ip;
        struct text_to_poke *tp;

        /*
         * Having observed our INT3 instruction, we now must observe
         * bp_patching_in_progress.
         *
         *      in_progress = TRUE              INT3
         *      WMB                             RMB
         *      write INT3                      if (in_progress)
         *
         * Idem for bp_int3_handler.
         */
        smp_rmb();

        if (likely(!bp_patching_in_progress))
                return 0;

        if (user_mode(regs))
                return 0;

        /*
         * Single poke is only used at the boot.
         */
        if (unlikely(!bp_int3_tpv))
                goto single_poke;

        ip = (void *) regs->ip - sizeof(unsigned char);
        tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
                     sizeof(struct text_to_poke),
                     text_bp_batch_bsearch);
        if (tp) {
                /* set up the specified breakpoint handler */
                regs->ip = (unsigned long) tp->handler;
                return 1;
        }

        return 0;

single_poke:

        if (regs->ip == (unsigned long) bp_int3_addr) {
                regs->ip = (unsigned long) bp_int3_handler;
                return 1;
        }

        return 0;
}

------------- >% ----------

In this way the default code is up, and the only 'if' I am using is a var of the batch mode (that will be used later). If are are still at the boot, we are jumping to the end of the function.

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

look better?

yeah, it looks much better. But I just wonder why don't you consolidate both by just because reducing code.

and so I did. How about something like this?

OK, I just have a nitpick comment, but this version looks good to me.

Quoted 117 lines

---------- %< ---------

---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 118 +++++++++++++++++++--------
 lib/bsearch.c                        |   2 +
 3 files changed, 100 insertions(+), 35 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +37 -5
index 202af29c43c0..2196bb8bb924 100644
@@ -11,6 +11,7 @@
 #include <linux/stop_machine.h>
 #include <linux/slab.h>
 #include <linux/kdebug.h>
+#include <linux/kprobes.h>
 #include <asm/text-patching.h>
 #include <asm/alternative.h>
 #include <asm/sections.h>
@@ -21,6 +22,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +740,26 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
-static void *bp_int3_handler, *bp_int3_addr;
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
+NOKPROBE_SYMBOL(text_bp_batch_bsearch);
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +775,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	ip = (void *) regs->ip - sizeof(unsigned char);
 
-	return 1;
+	/*
+	 * Skip the binary search if there is a single member in the vector.
+	 */
+	if (unlikely(bp_int3_tpv_nr == 1))
+		goto single_poke;
+
+	tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
+		     sizeof(struct text_to_poke),
+		     text_bp_batch_bsearch);
+	if (tp) {
+		/* set up the specified breakpoint handler */
+		regs->ip = (unsigned long) tp->handler;
+		return 1;
+	}
+
+	return 0;

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 808

Quoted 10 lines
arch/x86/kernel/alternative.c +8 -0
+
+single_poke:
+	if (ip == (unsigned long) bp_int3_tpv->addr) {
+		regs->ip = (unsigned long) bp_int3_tpv->handler;
+		return 1;
+	}
 
+	return 0;
 }
+NOKPROBE_SYMBOL(poke_int3_handler);

Ah, this will be covered by a series which currently I'm pinging Ingo.

https://lkml.org/lkml/2019/1/11/1480

Quoted 85 lines
arch/x86/kernel/alternative.c +19 -29
 static void text_poke_bp_set_handler(void *addr, void *handler,
 				     unsigned char int3)
 {
-	bp_int3_handler = handler;
-	bp_int3_addr = (u8 *)addr + sizeof(int3);
 	text_poke(addr, &int3, sizeof(int3));
 }
 
@@ -790,32 +828,14 @@ static void patch_first_byte(void *addr, const void *opcode, unsigned char int3)
 	text_poke(addr, opcode, sizeof(int3));
 }
 
-/**
- * text_poke_bp() -- update instructions on live kernel on SMP
- * @addr:	address to patch
- * @opcode:	opcode of new instruction
- * @len:	length to copy
- * @handler:	address to jump to when the temporary breakpoint is hit
- *
- * Modify multi-byte instruction by using int3 breakpoint on SMP.
- * We completely avoid stop_machine() here, and achieve the
- * synchronization using int3 breakpoint.
- *
- * The way it is done:
- *	- add a int3 trap to the address that will be patched
- *	- sync cores
- *	- update all but the first byte of the patched range
- *	- sync cores
- *	- replace the first byte (int3) by the first byte of
- *	  replacing opcode
- *	- sync cores
- */
-void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
+void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries)
 {
+	unsigned int i;
 	unsigned char int3 = 0xcc;
+	int patched_all_but_first = 0;
 
-	lockdep_assert_held(&text_mutex);
-
+	bp_int3_tpv = tp;
+	bp_int3_tpv_nr = nr_entries;
 	bp_patching_in_progress = true;
 	/*
 	 * Corresponding read barrier in int3 notifier for making sure the
@@ -823,12 +843,20 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 	 */
 	smp_wmb();
 
-	text_poke_bp_set_handler(addr, handler, int3);
+	for (i = 0; i < nr_entries; i++)
+		text_poke_bp_set_handler(tp[i].addr, tp[i].handler, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 
-	if (len - sizeof(int3) > 0) {
-		patch_all_but_first_byte(addr, opcode, len, int3);
+	for (i = 0; i < nr_entries; i++) {
+		if (tp[i].len - sizeof(int3) > 0) {
+			patch_all_but_first_byte(tp[i].addr, tp[i].opcode,
+						 tp[i].len, int3);
+			patched_all_but_first++;
+		}
+	}
+
+	if (patched_all_but_first) {
 		/*
 		 * According to Intel, this core syncing is very likely
 		 * not necessary and we'd be safe even without it. But
@@ -837,15 +865,35 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 		on_each_cpu(do_sync_core, NULL, 1);
 	}
 
-	patch_first_byte(addr, opcode, int3);
+	for (i = 0; i < nr_entries; i++)
+		patch_first_byte(tp[i].addr, tp[i].opcode, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 	/*
 	 * sync_core() implies an smp_mb() and orders this store against
 	 * the writing of the new instruction.
 	 */
+	bp_int3_tpv_nr = 0;

arch/x86/kernel/alternative.c void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler) · line 886

Quoted 10 lines
arch/x86/kernel/alternative.c +9 -0
+	bp_int3_tpv = NULL;
 	bp_patching_in_progress = false;
+}
+ XXX: paste the old comment here... I forgot.
+void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
+{
+	struct text_to_poke tp = {
+		.handler = handler,
+		.addr = addr,
+		.len = len

even the last field assignment, you'd better add "," here.

Quoted 28 lines
arch/x86/kernel/alternative.c +10 -1
+	};
+
+	if (len > POKE_MAX_OPCODE_SIZE) {
+		WARN_ONCE(1, "len is larger than %d\n", POKE_MAX_OPCODE_SIZE);
+		return NULL;
+	}
+
+	memcpy((void *)tp.opcode, opcode, len);
+
+	text_poke_bp_batch(&tp, 1);
 
 	return addr;
 }
-
lib/bsearch.c +1 -0
index 18b445b010c3..82512fe7b33c 100644
@@ -11,6 +11,7 @@
 
 #include <linux/export.h>
 #include <linux/bsearch.h>
+#include <linux/kprobes.h>
 
 /*
  * bsearch - binary search an array of elements

lib/bsearch.c void *bsearch(const void *key, const void *base, size_t num, size_t size, · line 57

Quoted 4 lines
lib/bsearch.c +1 -0
@@ -53,3 +54,4 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	return NULL;
 }
 EXPORT_SYMBOL(bsearch);
+NOKPROBE_SYMBOL(bsearch);

Actually, this part is already pointed by Andrea Righi, since ftrace is using bsearch, see below.

https://lkml.org/lkml/2019/1/12/70

It depends on which patch series are merged first, but I would like to separate NOKPROBE_SYMBOL() patch since it fixes (or prevents) a bug.

Anyway, this looks good to me.

Thank you,

Quoted 7 lines
Signature · 5 lines
If so, I will send a v4 with this ideia.

Thanks!

-- Daniel
Signature · 1 line
Masami Hiramatsu <[email protected]>
#19 lore raw

Re: [PATCH V3 7/9] x86/alternative: Batch of patch operations

Hi Masami!

Quoted 541 lines · Masami Hiramatsu

Hi Daniel,

Quoted 186 lines · On Fri, 1 Feb 2019 13:49:32 +0100 Daniel Bristot de Oliveira…
Quoted 185 lines · Masami Hiramatsu
Quoted 181 lines · On Sat, 26 Jan 2019 12:52:15 +0100 Daniel Bristot de Oliveira…
Quoted 167 lines · Masami Hiramatsu

Hi Daniel,

Quoted 162 lines · On Fri, 21 Dec 2018 11:27:32 +0100 Daniel Bristot de Oliveira…

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc "Steven Rostedt (VMware)" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc "Peter Zijlstra (Intel)" <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Jason Baron <[email protected]>
Cc Scott Wood <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Clark Williams <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +24 -1
index 6f5ad8587de0..8fa47e5ec709 100644
@@ -21,6 +21,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +739,32 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
+/*
+ * Single poke.
+ */
 static void *bp_int3_handler, *bp_int3_addr;
+/*
+ * Batching poke.
+ */
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +780,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
Quoted 8 lines

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 785

Quoted 5 lines
arch/x86/kernel/alternative.c +3 -2
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	/*
+	 * Single poke first.
+	 */

I wonder why would you separate single poke and batch poke? It seems a single poke is just a case that bp_int3_tpv_nr == 1.

Hi Masami!

The single poke is used only at the boot time, before the system is able to allocate memory. After that, the batch mode becomes the default.

Quoted 8 lines
Quoted 1 line

Hmm, what's the difference from text_poke_early()?

text_poke_early(): before enabling interrupts at boot.

text_poke_bp(): after enabling interrupts, before being able to allocate memory, or in the error handling with batch mode.

task_poke_batch(): After enabling interrupts and being able to allocate memory.

OK, I got it. Maybe we should document this for future users.

Quoted 106 lines
Quoted 6 lines
Quoted 3 lines

I was thinking to make one function to each method, but then I would have to change the do_int3() and manage how to switch between one and the other without further overhead. I was planing to do this in a second round of improvements.

I didn't think such big change.
I just thought we could allocate single entry array on stack, something like

Ah!

Quoted 8 lines

text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)

{
	struct text_to_poke tp = {.handler = handler, .addr = addr, .len = len};
	if (len > POKE_MAX_OPCODE_SIZE)
		return -E2BIG;
	memcpy(tp.opcode, opcode, len);
	return text_poke_bp_batch(&tp, 1);
}

Good idea!

Quoted 86 lines
Quoted 19 lines
Quoted 19 lines

If so, you can remove bp_int3_addr and this block.

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 800

Quoted 13 lines
arch/x86/kernel/alternative.c +11 -1
+	if (bp_int3_addr) {
+		if (regs->ip == (unsigned long) bp_int3_addr) {
+			regs->ip = (unsigned long) bp_int3_handler;
+			return 1;
+		}
+		return 0;
+	}
 
-	return 1;
+	/*
+	 * Batch mode.
+	 */
+	if (bp_int3_tpv_nr) {

if (unlikely(bp_int3_tpv_nr))

Quoted 3 lines
Quoted 1 line

Sorry about interrupting, but this is a "hot-path" when we use kprobes.

No problem at all! :-)

Thanks! :-)

Quoted 61 lines

I will change this function to better deal with the hot-path (the default mode after the system boots up).

how about something like this:
------------------ %< ------------------
int poke_int3_handler(struct pt_regs *regs)

{
        void *ip;
        struct text_to_poke *tp;

        /*
         * Having observed our INT3 instruction, we now must observe
         * bp_patching_in_progress.
         *
         *      in_progress = TRUE              INT3
         *      WMB                             RMB
         *      write INT3                      if (in_progress)
         *
         * Idem for bp_int3_handler.
         */
        smp_rmb();

        if (likely(!bp_patching_in_progress))
                return 0;

        if (user_mode(regs))
                return 0;

        /*
         * Single poke is only used at the boot.
         */
        if (unlikely(!bp_int3_tpv))
                goto single_poke;

        ip = (void *) regs->ip - sizeof(unsigned char);
        tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
                     sizeof(struct text_to_poke),
                     text_bp_batch_bsearch);
        if (tp) {
                /* set up the specified breakpoint handler */
                regs->ip = (unsigned long) tp->handler;
                return 1;
        }

        return 0;

single_poke:

        if (regs->ip == (unsigned long) bp_int3_addr) {
                regs->ip = (unsigned long) bp_int3_handler;
                return 1;
        }

        return 0;
}

------------- >% ----------

In this way the default code is up, and the only 'if' I am using is a var of the batch mode (that will be used later). If are are still at the boot, we are jumping to the end of the function.

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

look better?

yeah, it looks much better. But I just wonder why don't you consolidate both by just because reducing code.

and so I did. How about something like this?

OK, I just have a nitpick comment, but this version looks good to me.

Quoted 117 lines

---------- %< ---------

---
 arch/x86/include/asm/text-patching.h |  15 ++++
 arch/x86/kernel/alternative.c        | 118 +++++++++++++++++++--------
 lib/bsearch.c                        |   2 +
 3 files changed, 100 insertions(+), 35 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +37 -5
index 202af29c43c0..2196bb8bb924 100644
@@ -11,6 +11,7 @@
 #include <linux/stop_machine.h>
 #include <linux/slab.h>
 #include <linux/kdebug.h>
+#include <linux/kprobes.h>
 #include <asm/text-patching.h>
 #include <asm/alternative.h>
 #include <asm/sections.h>
@@ -21,6 +22,7 @@
 #include <asm/tlbflush.h>
 #include <asm/io.h>
 #include <asm/fixmap.h>
+#include <linux/bsearch.h>
 
 int __read_mostly alternatives_patched;
 
@@ -738,10 +740,26 @@ static void do_sync_core(void *info)
 }
 
 static bool bp_patching_in_progress;
-static void *bp_int3_handler, *bp_int3_addr;
+static struct text_to_poke *bp_int3_tpv;
+static unsigned int bp_int3_tpv_nr;
+
+static int text_bp_batch_bsearch(const void *key, const void *elt)
+{
+	struct text_to_poke *tp = (struct text_to_poke *) elt;
+
+	if (key < tp->addr)
+		return -1;
+	if (key > tp->addr)
+		return 1;
+	return 0;
+}
+NOKPROBE_SYMBOL(text_bp_batch_bsearch);
 
 int poke_int3_handler(struct pt_regs *regs)
 {
+	void *ip;
+	struct text_to_poke *tp;
+
 	/*
 	 * Having observed our INT3 instruction, we now must observe
 	 * bp_patching_in_progress.
@@ -757,21 +775,41 @@ int poke_int3_handler(struct pt_regs *regs)
 	if (likely(!bp_patching_in_progress))
 		return 0;
 
-	if (user_mode(regs) || regs->ip != (unsigned long)bp_int3_addr)
+	if (user_mode(regs))
 		return 0;
 
-	/* set up the specified breakpoint handler */
-	regs->ip = (unsigned long) bp_int3_handler;
+	ip = (void *) regs->ip - sizeof(unsigned char);
 
-	return 1;
+	/*
+	 * Skip the binary search if there is a single member in the vector.
+	 */
+	if (unlikely(bp_int3_tpv_nr == 1))
+		goto single_poke;
+
+	tp = bsearch(ip, bp_int3_tpv, bp_int3_tpv_nr,
+		     sizeof(struct text_to_poke),
+		     text_bp_batch_bsearch);
+	if (tp) {
+		/* set up the specified breakpoint handler */
+		regs->ip = (unsigned long) tp->handler;
+		return 1;
+	}
+
+	return 0;

arch/x86/kernel/alternative.c int poke_int3_handler(struct pt_regs *regs) · line 808

Quoted 10 lines
arch/x86/kernel/alternative.c +8 -0
+
+single_poke:
+	if (ip == (unsigned long) bp_int3_tpv->addr) {
+		regs->ip = (unsigned long) bp_int3_tpv->handler;
+		return 1;
+	}
 
+	return 0;
 }
+NOKPROBE_SYMBOL(poke_int3_handler);

Ah, this will be covered by a series which currently I'm pinging Ingo.

https://lkml.org/lkml/2019/1/11/1480

Quoted 89 lines
arch/x86/kernel/alternative.c +22 -29
 static void text_poke_bp_set_handler(void *addr, void *handler,
 				     unsigned char int3)
 {
-	bp_int3_handler = handler;
-	bp_int3_addr = (u8 *)addr + sizeof(int3);
 	text_poke(addr, &int3, sizeof(int3));
 }
 
@@ -790,32 +828,14 @@ static void patch_first_byte(void *addr, const void *opcode, unsigned char int3)
 	text_poke(addr, opcode, sizeof(int3));
 }
 
-/**
- * text_poke_bp() -- update instructions on live kernel on SMP
- * @addr:	address to patch
- * @opcode:	opcode of new instruction
- * @len:	length to copy
- * @handler:	address to jump to when the temporary breakpoint is hit
- *
- * Modify multi-byte instruction by using int3 breakpoint on SMP.
- * We completely avoid stop_machine() here, and achieve the
- * synchronization using int3 breakpoint.
- *
- * The way it is done:
- *	- add a int3 trap to the address that will be patched
- *	- sync cores
- *	- update all but the first byte of the patched range
- *	- sync cores
- *	- replace the first byte (int3) by the first byte of
- *	  replacing opcode
- *	- sync cores
- */
-void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
+void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries)
 {
+	unsigned int i;
 	unsigned char int3 = 0xcc;
+	int patched_all_but_first = 0;
 
-	lockdep_assert_held(&text_mutex);
-
+	bp_int3_tpv = tp;
+	bp_int3_tpv_nr = nr_entries;
 	bp_patching_in_progress = true;
 	/*
 	 * Corresponding read barrier in int3 notifier for making sure the
@@ -823,12 +843,20 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 	 */
 	smp_wmb();
 
-	text_poke_bp_set_handler(addr, handler, int3);
+	for (i = 0; i < nr_entries; i++)
+		text_poke_bp_set_handler(tp[i].addr, tp[i].handler, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 
-	if (len - sizeof(int3) > 0) {
-		patch_all_but_first_byte(addr, opcode, len, int3);
+	for (i = 0; i < nr_entries; i++) {
+		if (tp[i].len - sizeof(int3) > 0) {
+			patch_all_but_first_byte(tp[i].addr, tp[i].opcode,
+						 tp[i].len, int3);
+			patched_all_but_first++;
+		}
+	}
+
+	if (patched_all_but_first) {
 		/*
 		 * According to Intel, this core syncing is very likely
 		 * not necessary and we'd be safe even without it. But
@@ -837,15 +865,35 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 		on_each_cpu(do_sync_core, NULL, 1);
 	}
 
-	patch_first_byte(addr, opcode, int3);
+	for (i = 0; i < nr_entries; i++)
+		patch_first_byte(tp[i].addr, tp[i].opcode, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 	/*
 	 * sync_core() implies an smp_mb() and orders this store against
 	 * the writing of the new instruction.
 	 */
+	bp_int3_tpv_nr = 0;
+	bp_int3_tpv = NULL;
 	bp_patching_in_progress = false;
+}
+ XXX: paste the old comment here... I forgot.
Quoted 8 lines

arch/x86/kernel/alternative.c void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler) · line 886

Quoted 6 lines
arch/x86/kernel/alternative.c +6 -0
+void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
+{
+	struct text_to_poke tp = {
+		.handler = handler,
+		.addr = addr,
+		.len = len

even the last field assignment, you'd better add "," here.

ack!

Doing the changes, testing and submitting again.

Thank you very much for your comments.

-- Daniel

Quoted 57 lines
Quoted 29 lines
arch/x86/kernel/alternative.c +10 -1
+	};
+
+	if (len > POKE_MAX_OPCODE_SIZE) {
+		WARN_ONCE(1, "len is larger than %d\n", POKE_MAX_OPCODE_SIZE);
+		return NULL;
+	}
+
+	memcpy((void *)tp.opcode, opcode, len);
+
+	text_poke_bp_batch(&tp, 1);
 
 	return addr;
 }
-
lib/bsearch.c +1 -0
index 18b445b010c3..82512fe7b33c 100644
@@ -11,6 +11,7 @@
 
 #include <linux/export.h>
 #include <linux/bsearch.h>
+#include <linux/kprobes.h>
 
 /*
  * bsearch - binary search an array of elements

lib/bsearch.c void *bsearch(const void *key, const void *base, size_t num, size_t size, · line 57

Quoted 4 lines
lib/bsearch.c +1 -0
@@ -53,3 +54,4 @@ void *bsearch(const void *key, const void *base, size_t num, size_t size,
 	return NULL;
 }
 EXPORT_SYMBOL(bsearch);
+NOKPROBE_SYMBOL(bsearch);

Actually, this part is already pointed by Andrea Righi, since ftrace is using bsearch, see below.

https://lkml.org/lkml/2019/1/12/70

It depends on which patch series are merged first, but I would like to separate NOKPROBE_SYMBOL() patch since it fixes (or prevents) a bug.

Anyway, this looks good to me.

Thank you,

Quoted 7 lines
Signature · 5 lines
If so, I will send a v4 with this ideia.

Thanks!

-- Daniel
#2 lore raw

[tip:x86/alternatives] jump_label: Add for_each_label_entry helper

In reply to Daniel Bristot de Oliveira
jump_label: Add for_each_label_entry helper
Commit-ID:  b1b944f7230f4101b5a293d5ac3b7a9627ed5e6f
Gitweb:     https://git.kernel.org/tip/b1b944f7230f4101b5a293d5ac3b7a9627ed5e6f
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:26 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:34 +0200

jump_label: Add for_each_label_entry helper

Add a helper macro to make jump entry iteration code more readable.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 include/linux/jump_label.h | 3 +++
 kernel/jump_label.c        | 2 +-
 2 files changed, 4 insertions(+), 1 deletion(-)
include/linux/jump_label.h +3 -0
index 3e113a1fa0f1..7e91af98bbb1 100644
@@ -227,6 +227,9 @@ extern void static_key_disable(struct static_key *key);
 extern void static_key_enable_cpuslocked(struct static_key *key);
 extern void static_key_disable_cpuslocked(struct static_key *key);
 
+#define for_each_label_entry(key, entry, stop)				  \
+	for (; (entry < stop) && (jump_entry_key(entry) == key); entry++)
+
 /*
  * We should be using ATOMIC_INIT() for initializing .enabled, but
  * the inclusion of atomic.h is problematic for inclusion of jump_label.h
kernel/jump_label.c +1 -1
index bad96b476eb6..288d630da22d 100644
@@ -379,7 +379,7 @@ static void __jump_label_update(struct static_key *key,
 				struct jump_entry *stop,
 				bool init)
 {
-	for (; (entry < stop) && (jump_entry_key(entry) == key); entry++) {
+	for_each_label_entry(key, entry, stop) {
 		/*
 		 * An entry->code of 0 indicates an entry which has been
 		 * disabled because it was in an init text area.
#4 lore raw

[tip:x86/alternatives] jump_label: Add the jump_label_can_update_check() helper

In reply to Daniel Bristot de Oliveira
jump_label: Add the jump_label_can_update_check() helper
Commit-ID:  41bef31d0abe29b5888b33b526cacc8a30795318
Gitweb:     https://git.kernel.org/tip/41bef31d0abe29b5888b33b526cacc8a30795318
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:27 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:34 +0200

jump_label: Add the jump_label_can_update_check() helper

Move the check of if a jump_entry is valid to a specific function. No functional change.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 kernel/jump_label.c | 30 ++++++++++++++++++++----------
 1 file changed, 20 insertions(+), 10 deletions(-)
kernel/jump_label.c +20 -10
index 288d630da22d..456c0d7cbb5b 100644
@@ -374,22 +374,32 @@ static enum jump_label_type jump_label_type(struct jump_entry *entry)
 	return enabled ^ branch;
 }
 
+bool jump_label_can_update_check(struct jump_entry *entry, bool init)
+{
+	/*
+	 * An entry->code of 0 indicates an entry which has been
+	 * disabled because it was in an init text area.
+	 */
+	if (init || !jump_entry_is_init(entry)) {
+		if (!kernel_text_address(jump_entry_code(entry))) {
+			WARN_ONCE(1, "can't patch jump_label at %pS",
+				  (void *)jump_entry_code(entry));
+			return 0;
+		}
+		return 1;
+	}
+	return 0;
+}
+
 static void __jump_label_update(struct static_key *key,
 				struct jump_entry *entry,
 				struct jump_entry *stop,
 				bool init)
 {
 	for_each_label_entry(key, entry, stop) {
-		/*
-		 * An entry->code of 0 indicates an entry which has been
-		 * disabled because it was in an init text area.
-		 */
-		if (init || !jump_entry_is_init(entry)) {
-			if (kernel_text_address(jump_entry_code(entry)))
-				arch_jump_label_transform(entry, jump_label_type(entry));
-			else
-				WARN_ONCE(1, "can't patch jump_label at %pS",
-					  (void *)jump_entry_code(entry));
+		if (jump_label_can_update_check(entry, init)) {
+			arch_jump_label_transform(entry,
+						  jump_label_type(entry));
 		}
 	}
 }
#6 lore raw

[tip:x86/alternatives] x86/jump_label: Move checking code away from __jump_label_transform()

In reply to Daniel Bristot de Oliveira
x86/jump_label: Move checking code away from __jump_label_transform()
Commit-ID:  ddbefdc167f3d492036e6b0babd11a350c3bd3e3
Gitweb:     https://git.kernel.org/tip/ddbefdc167f3d492036e6b0babd11a350c3bd3e3
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:28 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:34 +0200

x86/jump_label: Move checking code away from __jump_label_transform()

Move the check of the current code, before updating an entry, to specialized functions. No changes in the method, only code relocation.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 arch/x86/kernel/jump_label.c | 60 +++++++++++++++++++++++++++++++-------------
 1 file changed, 42 insertions(+), 18 deletions(-)
arch/x86/kernel/jump_label.c +42 -18
index f99bd26bd3f1..e443c43478eb 100644
@@ -35,16 +35,53 @@ static void bug_at(unsigned char *ip, int line)
 	BUG();
 }
 
+static inline void __jump_label_trans_check_enable(struct jump_entry *entry,
+						   enum jump_label_type type,
+						   const unsigned char *ideal_nop,
+						   int init)
+{
+	const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
+	const void *expect;
+	int line;
+
+	if (init) {
+		expect = default_nop; line = __LINE__;
+	} else {
+		expect = ideal_nop; line = __LINE__;
+	}
+
+	if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
+		bug_at((void *)jump_entry_code(entry), line);
+}
+
+static inline void __jump_label_trans_check_disable(struct jump_entry *entry,
+						    enum jump_label_type type,
+						    union jump_code_union *jmp,
+						    int init)
+{
+	const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
+	const void *expect;
+	int line;
+
+	if (init) {
+		expect = default_nop; line = __LINE__;
+	} else {
+		expect = jmp->code; line = __LINE__;
+	}
+
+	if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
+		bug_at((void *)jump_entry_code(entry), line);
+}
+
+
 static void __ref __jump_label_transform(struct jump_entry *entry,
 					 enum jump_label_type type,
 					 void *(*poker)(void *, const void *, size_t),
 					 int init)
 {
 	union jump_code_union jmp;
-	const unsigned char default_nop[] = { STATIC_KEY_INIT_NOP };
 	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
-	const void *expect, *code;
-	int line;
+	const void *code;
 
 	jmp.jump = 0xe9;
 	jmp.offset = jump_entry_target(entry) -
@@ -54,26 +91,13 @@ static void __ref __jump_label_transform(struct jump_entry *entry,
 		poker = text_poke_early;
 
 	if (type == JUMP_LABEL_JMP) {
-		if (init) {
-			expect = default_nop; line = __LINE__;
-		} else {
-			expect = ideal_nop; line = __LINE__;
-		}
-
+		__jump_label_trans_check_enable(entry, type, ideal_nop, init);
 		code = &jmp.code;
 	} else {
-		if (init) {
-			expect = default_nop; line = __LINE__;
-		} else {
-			expect = &jmp.code; line = __LINE__;
-		}
-
+		__jump_label_trans_check_disable(entry, type, &jmp, init);
 		code = ideal_nop;
 	}
 
-	if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
-		bug_at((void *)jump_entry_code(entry), line);
-
 	/*
 	 * Make text_poke_bp() a default fallback poker.
 	 *
#10 lore raw

[tip:x86/alternatives] x86/alternative: Split text_poke_bp() into tree steps

In reply to Daniel Bristot de Oliveira
x86/alternative: Split text_poke_bp() into tree steps
Commit-ID:  6d2b0054d9a448d384264e003474219497e70bb9
Gitweb:     https://git.kernel.org/tip/6d2b0054d9a448d384264e003474219497e70bb9
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:30 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:34 +0200

x86/alternative: Split text_poke_bp() into tree steps

text_poke_bp() updates instructions on live kernel on SMP in three steps:
1) add a int3 trap to the address that will be patched
2) update all but the first byte of the patched range
3) replace the first byte (int3) by the first byte of

This patch creates one function for each of these steps.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 arch/x86/kernel/alternative.c | 38 +++++++++++++++++++++++++++-----------
 1 file changed, 27 insertions(+), 11 deletions(-)
arch/x86/kernel/alternative.c +27 -11
index 9a79c7808f9c..7fce844017f1 100644
@@ -768,6 +768,29 @@ int poke_int3_handler(struct pt_regs *regs)
 }
 NOKPROBE_SYMBOL(poke_int3_handler);
 
+static void text_poke_bp_set_handler(void *addr, void *handler,
+				     unsigned char int3)
+{
+	bp_int3_handler = handler;
+	bp_int3_addr = (u8 *)addr + sizeof(int3);
+	text_poke(addr, &int3, sizeof(int3));
+}
+
+static void patch_all_but_first_byte(void *addr, const void *opcode,
+				     size_t len, unsigned char int3)
+{
+	/* patch all but the first byte */
+	text_poke((char *)addr + sizeof(int3),
+		  (const char *) opcode + sizeof(int3),
+		  len - sizeof(int3));
+}
+
+static void patch_first_byte(void *addr, const void *opcode, unsigned char int3)
+{
+	/* patch the first byte */
+	text_poke(addr, opcode, sizeof(int3));
+}
+
 /**
  * text_poke_bp() -- update instructions on live kernel on SMP
  * @addr:	address to patch
@@ -792,27 +815,21 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 {
 	unsigned char int3 = 0xcc;
 
-	bp_int3_handler = handler;
-	bp_int3_addr = (u8 *)addr + sizeof(int3);
-	bp_patching_in_progress = true;
-
 	lockdep_assert_held(&text_mutex);
 
+	bp_patching_in_progress = true;
 	/*
 	 * Corresponding read barrier in int3 notifier for making sure the
 	 * in_progress and handler are correctly ordered wrt. patching.
 	 */
 	smp_wmb();
 
-	text_poke(addr, &int3, sizeof(int3));
+	text_poke_bp_set_handler(addr, handler, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 
 	if (len - sizeof(int3) > 0) {
-		/* patch all but the first byte */
-		text_poke((char *)addr + sizeof(int3),
-			  (const char *) opcode + sizeof(int3),
-			  len - sizeof(int3));
+		patch_all_but_first_byte(addr, opcode, len, int3);
 		/*
 		 * According to Intel, this core syncing is very likely
 		 * not necessary and we'd be safe even without it. But
@@ -821,8 +838,7 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 		on_each_cpu(do_sync_core, NULL, 1);
 	}
 
-	/* patch the first byte */
-	text_poke(addr, opcode, sizeof(int3));
+	patch_first_byte(addr, opcode, int3);
 
 	on_each_cpu(do_sync_core, NULL, 1);
 	/*
#8 lore raw

[tip:x86/alternatives] x86/jump_label: Add __jump_label_set_jump_code() helper

In reply to Daniel Bristot de Oliveira
x86/jump_label: Add __jump_label_set_jump_code() helper
Commit-ID:  369670e583390ce7324ba3db988de09a7fceca93
Gitweb:     https://git.kernel.org/tip/369670e583390ce7324ba3db988de09a7fceca93
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:29 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:34 +0200

x86/jump_label: Add __jump_label_set_jump_code() helper

Move the definition of the code to be written from __jump_label_transform() to a specialized function. No change in the method, code relocation only.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 arch/x86/kernel/jump_label.c | 38 ++++++++++++++++++++++----------------
 1 file changed, 22 insertions(+), 16 deletions(-)
arch/x86/kernel/jump_label.c +22 -16
index e443c43478eb..2ef687db5a87 100644
@@ -73,30 +73,36 @@ static inline void __jump_label_trans_check_disable(struct jump_entry *entry,
 		bug_at((void *)jump_entry_code(entry), line);
 }
 
+static void __jump_label_set_jump_code(struct jump_entry *entry,
+				       enum jump_label_type type,
+				       union jump_code_union *code,
+				       int init)
+{
+	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
+
+	code->jump = 0xe9;
+	code->offset = jump_entry_target(entry) -
+		     (jump_entry_code(entry) + JUMP_LABEL_NOP_SIZE);
+
+	if (type == JUMP_LABEL_JMP) {
+		__jump_label_trans_check_enable(entry, type, ideal_nop, init);
+	} else {
+		__jump_label_trans_check_disable(entry, type, code, init);
+		memcpy(code, ideal_nop, JUMP_LABEL_NOP_SIZE);
+	}
+}
 
 static void __ref __jump_label_transform(struct jump_entry *entry,
 					 enum jump_label_type type,
 					 void *(*poker)(void *, const void *, size_t),
 					 int init)
 {
-	union jump_code_union jmp;
-	const unsigned char *ideal_nop = ideal_nops[NOP_ATOMIC5];
-	const void *code;
-
-	jmp.jump = 0xe9;
-	jmp.offset = jump_entry_target(entry) -
-		     (jump_entry_code(entry) + JUMP_LABEL_NOP_SIZE);
+	union jump_code_union code;
 
 	if (early_boot_irqs_disabled)
 		poker = text_poke_early;
 
-	if (type == JUMP_LABEL_JMP) {
-		__jump_label_trans_check_enable(entry, type, ideal_nop, init);
-		code = &jmp.code;
-	} else {
-		__jump_label_trans_check_disable(entry, type, &jmp, init);
-		code = ideal_nop;
-	}
+	__jump_label_set_jump_code(entry, type, &code, init);
 
 	/*
 	 * Make text_poke_bp() a default fallback poker.
@@ -107,12 +113,12 @@ static void __ref __jump_label_transform(struct jump_entry *entry,
 	 *
 	 */
 	if (poker) {
-		(*poker)((void *)jump_entry_code(entry), code,
+		(*poker)((void *)jump_entry_code(entry), &code,
 			 JUMP_LABEL_NOP_SIZE);
 		return;
 	}
 
-	text_poke_bp((void *)jump_entry_code(entry), code, JUMP_LABEL_NOP_SIZE,
+	text_poke_bp((void *)jump_entry_code(entry), &code, JUMP_LABEL_NOP_SIZE,
 		     (void *)jump_entry_code(entry) + JUMP_LABEL_NOP_SIZE);
 }
 
#12 lore raw

[tip:x86/alternatives] jump_label: Sort entries of the same key by the code

In reply to Daniel Bristot de Oliveira
jump_label: Sort entries of the same key by the code
Commit-ID:  1ca3398278341e1db3568f2d9c015ee4f5ad0b56
Gitweb:     https://git.kernel.org/tip/1ca3398278341e1db3568f2d9c015ee4f5ad0b56
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:31 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:34 +0200

jump_label: Sort entries of the same key by the code

In the batching mode, entries with the same key should also be sorted by the code, enabling a bsearch() of a code/addr when updating a key.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 kernel/jump_label.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
kernel/jump_label.c +16 -0
index 456c0d7cbb5b..53b7c85c0b09 100644
@@ -36,12 +36,28 @@ static int jump_label_cmp(const void *a, const void *b)
 	const struct jump_entry *jea = a;
 	const struct jump_entry *jeb = b;
 
+	/*
+	 * Entrires are sorted by key.
+	 */
 	if (jump_entry_key(jea) < jump_entry_key(jeb))
 		return -1;
 
 	if (jump_entry_key(jea) > jump_entry_key(jeb))
 		return 1;
 
+#ifdef HAVE_JUMP_LABEL_BATCH
+	/*
+	 * In the batching mode, entries should also be sorted by the code
+	 * inside the already sorted list of entries, enabling a bsearch in
+	 * the vector.
+	 */
+	if (jump_entry_code(jea) < jump_entry_code(jeb))
+		return -1;
+
+	if (jump_entry_code(jea) > jump_entry_code(jeb))
+		return 1;
+#endif
+
 	return 0;
 }
 
#20 lore raw

[tip:x86/alternatives] x86/alternative: Batch of patch operations

In reply to Daniel Bristot de Oliveira
x86/alternative: Batch of patch operations
Commit-ID:  76ec759ad71c1fa0c4b327367e82b2650109a22f
Gitweb:     https://git.kernel.org/tip/76ec759ad71c1fa0c4b327367e82b2650109a22f
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:32 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:35 +0200

x86/alternative: Batch of patch operations

Currently, the patch of an address is done in three steps:

-- Pseudo-code #1 - Current implementation ---
1) add an int3 trap to the address that will be patched sync cores (send IPI to all other CPUs)
2) update all but the first byte of the patched range sync cores (send IPI to all other CPUs)
3) replace the first byte (int3) by the first byte of replacing opcode sync cores (send IPI to all other CPUs)
-- Pseudo-code #1 ---

When a static key has more than one entry, these steps are called once for each entry. The number of IPIs then is linear with regard to the number 'n' of entries of a key: O(n*3), which is O(n).

This algorithm works fine for the update of a single key. But we think it is possible to optimize the case in which a static key has more than one entry. For instance, the sched_schedstats jump label has 56 entries in my (updated) fedora kernel, resulting in 168 IPIs for each CPU in which the thread that is enabling the key is _not_ running.

With this patch, rather than receiving a single patch to be processed, a vector of patches is passed, enabling the rewrite of the pseudo-code #1 in this way:

-- Pseudo-code #2 - This patch ---
1) for each patch in the vector:
add an int3 trap to the address that will be patched

sync cores (send IPI to all other CPUs)

2) for each patch in the vector:
update all but the first byte of the patched range

sync cores (send IPI to all other CPUs)

3) for each patch in the vector:
replace the first byte (int3) by the first byte of replacing opcode

sync cores (send IPI to all other CPUs)
-- Pseudo-code #2 - This patch ---

Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).

The batch mode is done with the function text_poke_bp_batch(), that receives two arguments: a vector of "struct text_to_poke", and the number of entries in the vector.

The vector must be sorted by the addr field of the text_to_poke structure, enabling the binary search of a handler in the poke_int3_handler function (a fast path).

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 arch/x86/include/asm/text-patching.h |  15 +++++
 arch/x86/kernel/alternative.c        | 108 +++++++++++++++++++++++++++++++++--
 2 files changed, 117 insertions(+), 6 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..42ea7846df33 100644
@@ -18,6 +18,20 @@ static inline void apply_paravirt(struct paravirt_patch_site *start,
 #define __parainstructions_end	NULL
 #endif
 
+/*
+ * Currently, the max observed size in the kernel code is
+ * JUMP_LABEL_NOP_SIZE/RELATIVEJUMP_SIZE, which are 5.
+ * Raise it if needed.
+ */
+#define POKE_MAX_OPCODE_SIZE	5
+
+struct text_to_poke {
+	void *handler;
+	void *addr;
+	size_t len;
+	const char opcode[POKE_MAX_OPCODE_SIZE];
+};
+
 extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 
 /*
@@ -37,6 +51,7 @@ extern void *text_poke_early(void *addr, const void *opcode, size_t len);
 extern void *text_poke(void *addr, const void *opcode, size_t len);
 extern int poke_int3_handler(struct pt_regs *regs);
 extern void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler);
+extern void text_poke_bp_batch(struct text_to_poke *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +102 -6

151 lines not on this page · raw message

#22 lore raw

[tip:x86/alternatives] jump_label: Batch updates if arch supports it

In reply to Daniel Bristot de Oliveira
jump_label: Batch updates if arch supports it
Commit-ID:  9f4a3121e69d4e93cde30d1a274bd877f58e6b0a
Gitweb:     https://git.kernel.org/tip/9f4a3121e69d4e93cde30d1a274bd877f58e6b0a
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:33 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:35 +0200

jump_label: Batch updates if arch supports it

If the architecture supports the batching of jump label updates, use it!

An easy way to see the benefits of this patch is switching the schedstats on and off. For instance:

-------------------------- %< ----------------------------

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
sleep 2
sysctl -w kernel.sched_schedstats=0
sleep 2
done
-------------------------- >% ----------------------------

while watching the IPI count:

-------------------------- %< ---------------------------- -------------------------- >% ----------------------------

With the current mode, it is possible to see +- 168 IPIs each 2 seconds, while with this patch the number of IPIs goes to 3 each 2 seconds.

Regarding the performance impact of this patch set, I made two measurements:

The time to update a key (the task that is causing the change) The time to run the int3 handler (the side effect on a thread that
hits the code being changed)

The schedstats static key was chosen as the key to being switched on and off. The reason being is that it is used in more than 56 places, in a hot path. The change in the schedstats static key will be done with the following command:

while [ true ]; do
sysctl -w kernel.sched_schedstats=1
usleep 500000
sysctl -w kernel.sched_schedstats=0
usleep 500000
done

In this way, they key will be updated twice per second. To force the hit of the int3 handler, the system will also run a kernel compilation with two jobs per CPU. The test machine is a two nodes/24 CPUs box with an Intel Xeon processor @2.27GHz.

Regarding the update part, on average, the regular kernel takes 57 ms to update the schedstats key, while the kernel with the batch updates takes just 1.4 ms on average. Although it seems to be too good to be true, it makes sense: the schedstats key is used in 56 places, so it was expected that it would take around 56 times to update the keys with the current implementation, as the IPIs are the most expensive part of the update.

Regarding the int3 handler, the non-batch handler takes 45 ns on average, while the batch version takes around 180 ns. At first glance, it seems to be a high value. But it is not, considering that it is doing 56 updates, rather than one! It is taking four times more, only. This gain is possible because the patch uses a binary search in the vector: log2(56)=5.8. So, it was expected to have an overhead within four times.

(voice of tv propaganda) But, that is not all! As the int3 handler keeps on for a shorter period (because the update part is on for a shorter time), the number of hits in the int3 handler decreased by 10%.

The question then is: Is it worth paying the price of "135 ns" more in the int3 handler?

Considering that, in this test case, we are saving the handling of 53 IPIs, that takes more than these 135 ns, it seems to be a meager price to be paid. Moreover, the test case was forcing the hit of the int3, in practice, it does not take that often. While the IPI takes place on all CPUs, hitting the int3 handler or not!

For instance, in an isolated CPU with a process running in user-space (nohz_full use-case), the chances of hitting the int3 handler is barely zero, while there is no way to avoid the IPIs. By bounding the IPIs, we are improving a lot this scenario.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 include/linux/jump_label.h |  3 +++
 kernel/jump_label.c        | 29 +++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+)
include/linux/jump_label.h +3 -0
index 7e91af98bbb1..b3dfce98edb7 100644
@@ -215,6 +215,9 @@ extern void arch_jump_label_transform(struct jump_entry *entry,
 				      enum jump_label_type type);
 extern void arch_jump_label_transform_static(struct jump_entry *entry,
 					     enum jump_label_type type);
+extern int arch_jump_label_transform_queue(struct jump_entry *entry,
+					    enum jump_label_type type);
+extern void arch_jump_label_transform_apply(void);
 extern int jump_label_text_reserved(void *start, void *end);
 extern void static_key_slow_inc(struct static_key *key);
 extern void static_key_slow_dec(struct static_key *key);
kernel/jump_label.c +29 -0
index 53b7c85c0b09..944c75a0b09b 100644
@@ -407,6 +407,7 @@ bool jump_label_can_update_check(struct jump_entry *entry, bool init)
 	return 0;
 }
 
+#ifndef HAVE_JUMP_LABEL_BATCH
 static void __jump_label_update(struct static_key *key,
 				struct jump_entry *entry,
 				struct jump_entry *stop,
@@ -419,6 +420,34 @@ static void __jump_label_update(struct static_key *key,
 		}
 	}
 }
+#else
+static void __jump_label_update(struct static_key *key,
+				struct jump_entry *entry,
+				struct jump_entry *stop,
+				bool init)
+{
+	for_each_label_entry(key, entry, stop) {
+
+		if (!jump_label_can_update_check(entry, init))
+			continue;
+
+		if (arch_jump_label_transform_queue(entry,
+						    jump_label_type(entry)))
+			continue;
+
+		/*
+		 * Queue's overflow: Apply the current queue, and then
+		 * queue again. If it stills not possible to queue, BUG!
+		 */
+		arch_jump_label_transform_apply();
+		if (!arch_jump_label_transform_queue(entry,
+						     jump_label_type(entry))) {
+			BUG();
+		}
+	}
+	arch_jump_label_transform_apply();
+}
+#endif
 
 void __init jump_label_init(void)
 {
#24 lore raw

[tip:x86/alternatives] x86/jump_label: Batch jump label updates

In reply to Daniel Bristot de Oliveira
x86/jump_label: Batch jump label updates
Commit-ID:  1f30946b1a01baf22df6faf74c0a1e602bb6cac7
Gitweb:     https://git.kernel.org/tip/1f30946b1a01baf22df6faf74c0a1e602bb6cac7
Author:     Daniel Bristot de Oliveira <[email protected]>
AuthorDate: Fri, 21 Dec 2018 11:27:34 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Apr 2019 19:37:35 +0200

x86/jump_label: Batch jump label updates

Currently, the jump label of a static key is transformed via the arch specific function:

void arch_jump_label_transform(struct jump_entry *entry,
enum jump_label_type type)

The new approach (batch mode) uses two arch functions, the first has the same arguments of the arch_jump_label_transform(), and is the function:

void arch_jump_label_transform_queue(struct jump_entry *entry,
enum jump_label_type type)

Rather than transforming the code, it adds the jump_entry in a queue of entries to be updated. This functions returns 1 in the case of a successful enqueue of an entry. If it returns 0, the caller must to apply the queue and then try to queue again, for instance, because the queue is full.

This function expects the caller to sort the entries by the address before enqueueuing then. This is already done by the arch independent code, though.

After queuing all jump_entries, the function:

void arch_jump_label_transform_apply(void)

Applies the changes in the queue.

Cc Alexander Shishkin <[email protected]>
Cc Andy Lutomirski <[email protected]>
Cc Arnaldo Carvalho de Melo <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc Brian Gerst <[email protected]>
Cc Chris von Recklinghausen <[email protected]>
Cc Clark Williams <[email protected]>
Cc Denys Vlasenko <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Jason Baron <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc Jiri Olsa <[email protected]>
Cc Josh Poimboeuf <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Marcelo Tosatti <[email protected]>
Cc Masami Hiramatsu <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Scott Wood <[email protected]>
Cc Steven Rostedt (VMware) <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 arch/x86/include/asm/jump_label.h |  2 +
 arch/x86/kernel/jump_label.c      | 88 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 90 insertions(+)
arch/x86/include/asm/jump_label.h +2 -0
index 65191ce8e1cf..06c3cc22a058 100644
@@ -2,6 +2,8 @@
 #ifndef _ASM_X86_JUMP_LABEL_H
 #define _ASM_X86_JUMP_LABEL_H
 
+#define HAVE_JUMP_LABEL_BATCH
+
 #define JUMP_LABEL_NOP_SIZE 5
 
 #ifdef CONFIG_X86_64
arch/x86/kernel/jump_label.c +88 -0

100 lines not on this page · raw message

#26 lore raw
In reply to Daniel Bristot de Oliveira
Quoted 34 lines · Daniel Bristot de Oliveira

Considering that, in this test case, we are saving the handling of 53 IPIs, that takes more than these 135 ns, it seems to be a meager price to be paid. Moreover, the test case was forcing the hit of the int3, in practice, it does not take that often. While the IPI takes place on all CPUs, hitting the int3 handler or not!

For instance, in an isolated CPU with a process running in user-space (nohz_full use-case), the chances of hitting the int3 handler is barely zero, while there is no way to avoid the IPIs. By bounding the IPIs, we are improving this scenario a lot.

Changes from v2:
- Switch the order of patches 8 and 9 (Steven Rostedt)
- Fallback in the case of failure in the batch mode (Steven Rostedt)
- Fix a pointer in patch 7 (Steven Rostedt)
- Adjust the commit log of the patch 1 (Borislav Petkov)
- Adjust the commit log of the patch 3 (Jiri Kosina/Thomas Gleixner)
Changes from v1:
- Split the patch in jump-label/x86-jump-label/alternative (Jason Baron)
- Use bserach in the int3 handler (Steven Rostedt)
- Use a pre-allocated page to store the vector (Jason/Steven)
- Do performance tests in the int3 handler (peterz)

Daniel Bristot de Oliveira (9):
jump_label: Add for_each_label_entry helper
jump_label: Add the jump_label_can_update_check() helper x86/jump_label: Move checking code away from __jump_label_transform() x86/jump_label: Add __jump_label_set_jump_code() helper x86/alternative: Split text_poke_bp() into tree steps
jump_label: Sort entries of the same key by the code x86/alternative: Batch of patch operations
jump_label: Batch updates if arch supports it x86/jump_label: Batch jump label updates

Quoted 7 lines
 arch/x86/include/asm/jump_label.h    |   2 +
 arch/x86/include/asm/text-patching.h |  15 +++
 arch/x86/kernel/alternative.c        | 140 ++++++++++++++++++---
 arch/x86/kernel/jump_label.c         | 174 ++++++++++++++++++++++-----
 include/linux/jump_label.h           |   6 +
 kernel/jump_label.c                  |  73 +++++++++--
 6 files changed, 359 insertions(+), 51 deletions(-)

Note that I've applied these to tip:WIP.x86/alternatives to help move it along and help with testing, but before this can go upstream review feedback from PeterZ needs to be addressed.

Please send the latest series (v3, v4, etc.) with full patches to make it easy to review from scratch to everyone - I'll reshuffle the WIP branch accordingly. These are not stable SHA1's yet.

Thanks,

Ingo