Skip to contentSkip to conversation

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

PATCH Superseded Daniel Bristot de Oliveira 2 participants 18 messages Apr 1, 2019 – May 2, 2019

Subsystems (2)

v5 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

v5 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:

int 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 v4:
- Renamed jump_label_can_update_check() to jump_label_can_update() (Borislav Petkov)
- Switch jump_label_can_update() return values to bool (Borislav Petkov)
- Accept the fact that some lines will be > 80 characters (Borislav Petkov)
- Local variables are now in the inverted Christmas three order (Borislav Petkov)
- Removed superfluous helpers. (Borislav Petkov)
- Renamed text_to_poke to text_patch_loc, and handler to detour (Borislav Petkov & Steven Rostedt)
- Re-applied the suggestion of not using BUG() from steven (Masami Hiramatsu)
- arch_jump_label_transform_queue() now returns 0 on success and -ENOSPC/EINVAL on errors (Masami Hiramatsu)
Changes from v3:
- Optimizations in the hot path of poke_int3_handler() (Masami Hiramatsu)
- Reduce code duplication in text_poke_bp()/text_poke_batch() (Masami Hiramatsu)
- Set NOKPROBE_SYMBOL on functions called by poke_int3_handler() (Masami Hiramatsu)
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 (7):
jump_label: Add for_each_label_entry helper
jump_label: Add a jump_label_can_update() helper x86/jump_label: Add a __jump_label_set_jump_code() helper
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        | 152 +++++++++++++++++++++------
 arch/x86/kernel/jump_label.c         | 135 ++++++++++++++++++++----
 include/linux/jump_label.h           |   6 ++
 kernel/jump_label.c                  |  79 ++++++++++++--
 6 files changed, 331 insertions(+), 58 deletions(-)
Signature · 1 line
2.20.1
#1 lore raw

PATCH v5 1/7 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 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.
Signature · 1 line
2.20.1
#5 lore raw

PATCH v5 3/7 x86/jump_label: Add a __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.

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 | 47 ++++++++++++++++++++++--------------
 1 file changed, 29 insertions(+), 18 deletions(-)
arch/x86/kernel/jump_label.c +29 -18
index f99bd26bd3f1..8aa65fbbd764 100644
@@ -35,24 +35,20 @@ static void bug_at(unsigned char *ip, int line)
 	BUG();
 }
 
-static void __ref __jump_label_transform(struct jump_entry *entry,
-					 enum jump_label_type type,
-					 void *(*poker)(void *, const void *, size_t),
-					 int init)
+static void __jump_label_set_jump_code(struct jump_entry *entry,
+				       enum jump_label_type type,
+				       union jump_code_union *code,
+				       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;
+	const void *expect;
 	int line;
 
-	jmp.jump = 0xe9;
-	jmp.offset = jump_entry_target(entry) -
+	code->jump = 0xe9;
+	code->offset = jump_entry_target(entry) -
 		     (jump_entry_code(entry) + JUMP_LABEL_NOP_SIZE);
 
-	if (early_boot_irqs_disabled)
-		poker = text_poke_early;
-
 	if (type == JUMP_LABEL_JMP) {
 		if (init) {
 			expect = default_nop; line = __LINE__;
@@ -60,19 +56,34 @@ static void __ref __jump_label_transform(struct jump_entry *entry,
 			expect = ideal_nop; line = __LINE__;
 		}
 
-		code = &jmp.code;
+		if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
+			bug_at((void *)jump_entry_code(entry), line);
+
 	} else {
 		if (init) {
 			expect = default_nop; line = __LINE__;
 		} else {
-			expect = &jmp.code; line = __LINE__;
+			expect = code->code; line = __LINE__;
 		}
 
-		code = ideal_nop;
+		if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
+			bug_at((void *)jump_entry_code(entry), line);
+
+		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 code;
+
+	if (early_boot_irqs_disabled)
+		poker = text_poke_early;
 
-	if (memcmp((void *)jump_entry_code(entry), expect, JUMP_LABEL_NOP_SIZE))
-		bug_at((void *)jump_entry_code(entry), line);
+	__jump_label_set_jump_code(entry, type, &code, init);
 
 	/*
 	 * Make text_poke_bp() a default fallback poker.
@@ -83,12 +94,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.20.1
#6 lore raw

PATCH v5 4/7 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 e666a4d6642a..8b7bfbba4cef 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;
 }
 
Signature · 1 line
2.20.1
#9 lore raw

PATCH v5 5/7 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        | 152 +++++++++++++++++++++------
 2 files changed, 136 insertions(+), 31 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
index e85ff65c43c3..8ffa0c14c039 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_patch_loc {
+	void *detour;
+	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_patch_loc *tp, unsigned int nr_entries);
 extern int after_bootmem;
 
 #endif /* _ASM_X86_TEXT_PATCHING_H */
arch/x86/kernel/alternative.c +121 -31

223 lines not on this page · raw message

Signature · 1 line
2.20.1
#11 lore raw

PATCH v5 6/7 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/sh
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        | 37 +++++++++++++++++++++++++++++++++++++
 2 files changed, 40 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 +37 -0
index 8b7bfbba4cef..7357a2df2e8c 100644
@@ -406,6 +406,7 @@ static bool jump_label_can_update(struct jump_entry *entry, bool init)
 	return true;
 }
 
+#ifndef HAVE_JUMP_LABEL_BATCH
 static void __jump_label_update(struct static_key *key,
 				struct jump_entry *entry,
 				struct jump_entry *stop,
@@ -417,6 +418,42 @@ static void __jump_label_update(struct static_key *key,
 		}
 	}
 }
+#else
+int fallback_batch __read_mostly;
+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(entry, init))
+			continue;
+
+		if (unlikely(fallback_batch)) {
+			arch_jump_label_transform(entry, jump_label_type(entry));
+			continue;
+		}
+
+		if (!arch_jump_label_transform_queue(entry, jump_label_type(entry)))
+			continue;
+
+		/*
+		 * Queue's overflow: Apply the current queue, and then try to
+		 * queue again. If it stills fail to queue, fallback to the
+		 * non-batch mode!
+		 */
+		arch_jump_label_transform_apply();
+
+		if (arch_jump_label_transform_queue(entry, jump_label_type(entry))) {
+			WARN(1, "jump_label: batch mode failure!\n");
+			fallback_batch = 1;
+			arch_jump_label_transform(entry, jump_label_type(entry));
+		}
+	}
+	arch_jump_label_transform_apply();
+}
+#endif
 
 void __init jump_label_init(void)
 {
Signature · 1 line
2.20.1
#13 lore raw

PATCH v5 7/7 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:

int 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 0 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 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

Signature · 1 line
2.20.1
#4 lore raw

PATCH v5 2/7 jump_label: Add a jump_label_can_update() helper

In reply to Daniel Bristot de Oliveira

Move the check if a jump_entry is valid to a function.

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 | 28 ++++++++++++++++++----------
 1 file changed, 18 insertions(+), 10 deletions(-)
kernel/jump_label.c +18 -10
index 288d630da22d..e666a4d6642a 100644
@@ -374,22 +374,30 @@ static enum jump_label_type jump_label_type(struct jump_entry *entry)
 	return enabled ^ branch;
 }
 
+static bool jump_label_can_update(struct jump_entry *entry, bool init)
+{
+	/*
+	 * Cannot update code that was in an init text area.
+	 */
+	if (!init && jump_entry_is_init(entry))
+		return false;
+
+	if (!kernel_text_address(jump_entry_code(entry))) {
+		WARN_ONCE(1, "can't patch jump_label at %pS", (void *)jump_entry_code(entry));
+		return false;
+	}
+
+	return true;
+}
+
 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(entry, init)) {
+			arch_jump_label_transform(entry, jump_label_type(entry));
 		}
 	}
 }
Signature · 1 line
2.20.1
#17 lore raw
In reply to Daniel Bristot de Oliveira
Quoted 176 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:

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

Quoted 13 lines

Changes from v4:
- Renamed jump_label_can_update_check() to jump_label_can_update() (Borislav Petkov)
- Switch jump_label_can_update() return values to bool (Borislav Petkov)
- Accept the fact that some lines will be > 80 characters (Borislav Petkov)
- Local variables are now in the inverted Christmas three order (Borislav Petkov)
- Removed superfluous helpers. (Borislav Petkov)
- Renamed text_to_poke to text_patch_loc, and handler to detour (Borislav Petkov & Steven Rostedt)
- Re-applied the suggestion of not using BUG() from steven (Masami Hiramatsu)
- arch_jump_label_transform_queue() now returns 0 on success and -ENOSPC/EINVAL on errors (Masami Hiramatsu)

This is a gentle ping...

Thanks!
-- Daniel

maintainer
#2 lore raw

Re: [PATCH V5 1/7] jump_label: Add for_each_label_entry helper

In reply to Daniel Bristot de Oliveira
Quoted 9 lines · Daniel Bristot de Oliveira

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

include/linux/jump_label.h +0 -0
index 3e113a1fa0f1..7e91af98bbb1 100644

include/linux/jump_label.h extern void static_key_disable(struct static_key *key); · line 232

Quoted 6 lines
include/linux/jump_label.h +3 -0
@@ -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++)
+

I don't really like this naming; most (all?) for_each_*() loops start iteration and have the iteration variable as first argument.

This should maybe be called:

for_each_jump_entry_by_key_cont(entry, stop, key)

and I realize that is a horrible name too.

maintainer
#7 lore raw

Re: [PATCH V5 4/7] jump_label: Sort entries of the same key by the code

In reply to Daniel Bristot de Oliveira
Quoted 2 lines · 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.

Might be good to explain *why*.

We can see what the code does, explaining why we do things is what we have Changelogs for.

Quoted 44 lines
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 +8 -0
index e666a4d6642a..8b7bfbba4cef 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.

kernel/jump_label.c static int jump_label_cmp(const void *a, const void *b) · line 62

Quoted 10 lines
kernel/jump_label.c +8 -0
+	 */
+	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;
 }

The secondary sort order doesn't hurt, so we could leave the #ifdef out, not sure.

#3 lore raw

Re: [PATCH V5 1/7] jump_label: Add for_each_label_entry helper

In reply to Peter Zijlstra
Quoted 11 lines · Peter Zijlstra

include/linux/jump_label.h extern void static_key_disable(struct static_key *key); · line 232

Quoted 3 lines
include/linux/jump_label.h +3 -0
+#define for_each_label_entry(key, entry, stop)				  \
+	for (; (entry < stop) && (jump_entry_key(entry) == key); entry++)
+

I don't really like this naming; most (all?) for_each_*() loops start iteration and have the iteration variable as first argument.

This should maybe be called:

for_each_jump_entry_by_key_cont(entry, stop, key)

and I realize that is a horrible name too.

Borislav did not like this helper too, so I am convinced: we do not need it. I will remove it in the next version.

-- Daniel

#8 lore raw

Re: [PATCH V5 4/7] jump_label: Sort entries of the same key by the code

In reply to Peter Zijlstra
Quoted 8 lines · Peter Zijlstra
Quoted 2 lines · 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.

Might be good to explain *why*.

We can see what the code does, explaining why we do things is what we have Changelogs for.

Ack! I will explain why,

Quoted 30 lines
Quoted 30 lines
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 +0 -0
index e666a4d6642a..8b7bfbba4cef 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;
 
Quoted 3 lines

kernel/jump_label.c static int jump_label_cmp(const void *a, const void *b) · line 41

Quoted 3 lines
kernel/jump_label.c +3 -0
+	/*
+	 * Entrires are sorted by key.
+	 */

and this the typo above (just noticed),

Quoted 16 lines
Quoted 16 lines
kernel/jump_label.c +10 -0
 	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))
Quoted 8 lines

kernel/jump_label.c static int jump_label_cmp(const void *a, const void *b) · line 62

Quoted 5 lines
kernel/jump_label.c +3 -0
+		return 1;
+#endif
+
 	return 0;
 }

The secondary sort order doesn't hurt, so we could leave the #ifdef out, not sure.

and remove the #ifdef, unless someone else things we need to keep it.

-- Daniel

maintainer
#10 lore raw

Re: [PATCH V5 5/7] x86/alternative: Batch of patch operations

In reply to Daniel Bristot de Oliveira

arch/x86/kernel/alternative.c static void do_sync_core(void *info) · line 783

Quoted 1 line · Daniel Bristot de Oliveira
arch/x86/kernel/alternative.c +1 -0
+	ip = (void *) regs->ip - sizeof(unsigned char);

That one confused me mightily. Does that want to be:

	ip = (void *)regs->ip - LEN_INT3;

or something? Even just a naked 1 would've been less confusing.

Quoted 13 lines
arch/x86/kernel/alternative.c +12 -0
+	/*
+	 * Skip the binary search if there is a single member in the vector.
+	 */
+	if (unlikely(bp_patching.nr_entries == 1))
+		goto single_poke;
+
+	tp = bsearch(ip, bp_patching.vec, bp_patching.nr_entries,
+		     sizeof(struct text_patch_loc),
+		     patch_cmp);
+	if (!tp)
+		return 0;
+

arch/x86/kernel/alternative.c static void do_sync_core(void *info) · line 806

Quoted 10 lines
arch/x86/kernel/alternative.c +9 -0
+	/* set up the specified breakpoint detour */
+	regs->ip = (unsigned long) tp->detour;
 	return 1;
+single_poke:
+	if (ip == bp_patching.vec->addr) {
+		regs->ip = (unsigned long) bp_patching.vec->detour;
+		return 1;
+	}
+
+	return 0;
	if (bp_patching.nr_entries > 1) {
		tp = bsearch(ip, bp_patching.vec, bp_patching.nr_entries,
			     sizeof(struct text_patch_loc), patch_cmp);
		if (!tp)
			return 0;
	} else {
		tp = bp_patching.vec;
		if (tp->addr != ip)
			return 0;
	}

	regs->ip = (unsigned long)tp->detour;
	return 1;
Quoted 64 lines

}
NOKPROBE_SYMBOL(poke_int3_handler);

arch/x86/kernel/alternative.c +34 -0
+void text_poke_bp_batch(struct text_patch_loc *tp, unsigned int nr_entries)
 {
+	int patched_all_but_first = 0;
 	unsigned char int3 = 0xcc;
+	unsigned int i;
 
 	lockdep_assert_held(&text_mutex);
 
+	bp_patching.vec = tp;
+	bp_patching.nr_entries = 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();
 
+	/*
+	 * First step: add a int3 trap to the address that will be patched.
+	 */
+	for (i = 0; i < nr_entries; i++)
+		text_poke(tp[i].addr, &int3, sizeof(int3));
 
 	on_each_cpu(do_sync_core, NULL, 1);
 
+	/*
+	 * Second step: update all but the first byte of the patched range.
+	 */
+	for (i = 0; i < nr_entries; i++) {
+		if (tp[i].len - sizeof(int3) > 0) {
+			text_poke((char *)tp[i].addr + sizeof(int3),
+				  (const char *)tp[i].opcode + sizeof(int3),
+				  tp[i].len - sizeof(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
@@ -821,15 +874,52 @@ void *text_poke_bp(void *addr, const void *opcode, size_t len, void *handler)
 		on_each_cpu(do_sync_core, NULL, 1);
 	}
 
+	/*
+	 * Third step: replace the first byte (int3) by the first byte of
+	 * replacing opcode.
+	 */
+	for (i = 0; i < nr_entries; i++)
+		text_poke(tp[i].addr, tp[i].opcode, sizeof(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_patching.vec = NULL;
+	bp_patching.nr_entries = 0;
+	bp_patching.in_progress = false;
+}
maintainer
#12 lore raw

Re: [PATCH V5 6/7] jump_label: Batch updates if arch supports it

In reply to Daniel Bristot de Oliveira
Quoted 8 lines · Daniel Bristot de Oliveira
kernel/jump_label.c +8 -0
+int fallback_batch __read_mostly;
+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) {
+

kernel/jump_label.c static void __jump_label_update(struct static_key *key, · line 439

Quoted 10 lines
kernel/jump_label.c +10 -0
+		if (!jump_label_can_update(entry, init))
+			continue;
+
+		if (unlikely(fallback_batch)) {
+			arch_jump_label_transform(entry, jump_label_type(entry));
+			continue;
+		}
+
+		if (!arch_jump_label_transform_queue(entry, jump_label_type(entry)))
+			continue;

That reads wrong; 'if we cannot queue, continue'

Quoted 6 lines
kernel/jump_label.c +6 -0
+
+		/*
+		 * Queue's overflow: Apply the current queue, and then try to
+		 * queue again. If it stills fail to queue, fallback to the
+		 * non-batch mode!
+		 */

kernel/jump_label.c static void __jump_label_update(struct static_key *key, · line 455

Quoted 10 lines
kernel/jump_label.c +10 -0
+		arch_jump_label_transform_apply();
+
+		if (arch_jump_label_transform_queue(entry, jump_label_type(entry))) {
+			WARN(1, "jump_label: batch mode failure!\n");
+			fallback_batch = 1;
+			arch_jump_label_transform(entry, jump_label_type(entry));
+		}
+	}
+	arch_jump_label_transform_apply();
+}

Hurmph...

	for_each_whatever(entry, stop, key) {
		if (!jump_label_can_update(entry, init))
			continue;

		if (!arch_jump_label_transform_queue(entry)) {
			/* queue full, flush */
			arch_jump_label_transform_apply();
			BUG_ON(!arch_jump_label_transform_queue(entry));
		}
	}
	arch_jump_label_transform_apply();

Also, see next patch.

maintainer
#14 lore raw

Re: [PATCH V5 7/7] x86/jump_label: Batch jump label updates

In reply to Daniel Bristot de Oliveira
Quoted 33 lines · Daniel Bristot de Oliveira
arch/x86/kernel/jump_label.c +18 -0
index 8aa65fbbd764..ab75b222a7e2 100644
@@ -15,6 +15,7 @@
 #include <asm/kprobes.h>
 #include <asm/alternative.h>
 #include <asm/text-patching.h>
+#include <linux/slab.h>
 
 union jump_code_union {
 	char code[JUMP_LABEL_NOP_SIZE];
@@ -111,6 +112,93 @@ void arch_jump_label_transform(struct jump_entry *entry,
 	mutex_unlock(&text_mutex);
 }
 
+unsigned int entry_vector_max_elem __read_mostly;
+struct text_patch_loc *entry_vector;
+unsigned int entry_vector_nr_elem;
+
+void arch_jump_label_init(void)
+{
+	entry_vector = (void *) __get_free_page(GFP_KERNEL);
+
+	if (WARN_ON_ONCE(!entry_vector))
+		return;
+
+	entry_vector_max_elem = PAGE_SIZE / sizeof(struct text_patch_loc);
+	return;
+}
+
+int arch_jump_label_transform_queue(struct jump_entry *entry,
+				     enum jump_label_type type)

arch/x86/kernel/jump_label.c void arch_jump_label_transform(struct jump_entry *entry, · line 141

Quoted 10 lines
arch/x86/kernel/jump_label.c +10 -0
+{
+	struct text_patch_loc *tp;
+	void *entry_code;
+
+	/*
+	 * Batch mode disabled before being able to allocate memory:
+	 * Fallback to the non-batching mode.
+	 */
+	if (unlikely(!entry_vector_max_elem)) {
+		if (!slab_is_available() || early_boot_irqs_disabled)

See, the thing is, you never use slab, so that slab check is completely wrong.

Quoted 37 lines
arch/x86/kernel/jump_label.c +37 -0
+			goto fallback;
+
+		arch_jump_label_init();
+	}
+
+	/*
+	 * No more space in the vector, tell upper layer to apply
+	 * the queue before continuing.
+	 */
+	if (entry_vector_nr_elem == entry_vector_max_elem)
+		return -ENOSPC;
+
+	tp = &entry_vector[entry_vector_nr_elem];
+
+	entry_code = (void *)jump_entry_code(entry);
+
+	/*
+	 * The int3 handler will do a bsearch in the queue, so we need entries
+	 * to be sorted. We can survive an unsorted list by rejecting the entry,
+	 * forcing the generic jump_label code to apply the queue. Warning once,
+	 * to raise the attention to the case of an unsorted entry that is
+	 * better not happen, because, in the worst case we will perform in the
+	 * same way as we do without batching - with some more overhead.
+	 */
+	if (entry_vector_nr_elem > 0) {
+		int prev_idx = entry_vector_nr_elem - 1;
+		struct text_patch_loc *prev_tp = &entry_vector[prev_idx];
+
+		if (WARN_ON_ONCE(prev_tp->addr > entry_code))
+			return -EINVAL;
+	}
+
+	__jump_label_set_jump_code(entry, type,
+				   (union jump_code_union *) &tp->opcode, 0);
+
+	tp->addr = entry_code;
+	tp->detour = entry_code + JUMP_LABEL_NOP_SIZE;

arch/x86/kernel/jump_label.c void arch_jump_label_transform(struct jump_entry *entry, · line 188

Quoted 10 lines
arch/x86/kernel/jump_label.c +10 -0
+	tp->len = JUMP_LABEL_NOP_SIZE;
+
+	entry_vector_nr_elem++;
+
+	return 0;
+
+fallback:
+	arch_jump_label_transform(entry, type);
+	return 0;
+}

So how about we do something like:

+static struct bp_patching_desc {
+ int nr_entries;
+ struct text_patch_loc vec[PAGE_SIZE / sizeof(struct text_patch_loc)];
+} bp_patching;

and call it a day?

Then we have static storage, no allocation, no fail paths.

Also note that I removed that whole in_progress thing, as that is completely redudant vs !!nr_entries.

#15 lore raw

Re: [PATCH V5 7/7] x86/jump_label: Batch jump label updates

Quoted 8 lines · Peter Zijlstra

So how about we do something like:

(quoted diff) +4 -0
+static struct bp_patching_desc {
+       int nr_entries;
+       struct text_patch_loc vec[PAGE_SIZE / sizeof(struct text_patch_loc)];
+} bp_patching;

and call it a day?

Sure!

Actually, I used something like that in my first poc patches (for my own), but I thought people would complain...

If nobody else complains, I will use it in the next version.

-- Daniel

#16 lore raw

Re: [PATCH V5 7/7] x86/jump_label: Batch jump label updates

In reply to Peter Zijlstra
Quoted 7 lines · Peter Zijlstra

So how about we do something like:

(quoted diff) +4 -0
+static struct bp_patching_desc {
+       int nr_entries;
+       struct text_patch_loc vec[PAGE_SIZE / sizeof(struct text_patch_loc)];
+} bp_patching;
Quoted 6 lines

and call it a day?

Then we have static storage, no allocation, no fail paths.

Also note that I removed that whole in_progress thing, as that is completely redudant vs !!nr_entries.

Hi Peter,

I am finishing the next version, but now I am in a dilemma.

If I use:

static struct bp_patching_desc {
	int nr_entries;
	struct text_patch_loc vec[PAGE_SIZE / sizeof(struct text_patch_loc)];
} bp_patching;

The in_progress is still needed because nr_entries will increase while queuing... and so we would enter in the int3 before we actually need.

It will also need a new function on alternative.c to queue each entry into the vector and change the text_poke_bp_batch() to a text_poke_bp_apply() without arguments, +- replicating the arch_jump_label_transform_queue() and arch_jump_label_transform_apply().

[ and probably also take the text_mutex while queuing... and release in the apply ]

OR

I can declare a vector and a counter in arch/x86/jump_label.c, like this:

#define TP_VEC_MAX (PAGE_SIZE / sizeof(struct text_patch_loc)) static struct text_patch_loc tp_vec[TP_VEC_MAX];
int tp_nr_entries = 0;

and use the arch_jump_label_transform_batch() as it is now, i.e:

void text_poke_bp_batch(struct text_patch_loc *tp, unsigned int nr_entries)

In this case, we do not need the in_progress because the bp_patching_desc.nr_entries is filled only when in progress.

so, which path should I take?

Thanks
-- Daniel