x86/jump_label: Bound IPIs sent when updating a static key
Subsystems (2)
v6 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:
bool 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 v5:
- Remove "Add for_each_label_entry helper" patch (Peter Zijlstra & Borislav Petkov)
- Adjust the changelog of "jump_label: Sort entries of the same key by the code" (Peter Zijlstra)
- Optimize poke_int3_handler() (Peter Zijlstra)
- Optimize __jump_label_update() (Peter Zijlstra)
- Remove "in_progress" var, use "nr_entries" instead (Peter Zijlstra)
- Use static allocated memory rather than dynamic (Peter Zijlstra)
- Remove all the control/fallback required by dynamic allocated memory.
- Undo the substitution of BUG() to WARN() - Running with inconsistent code is a BUG (Peter Zijlstra)
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 (6):
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 | 154 +++++++++++++++++++++------ arch/x86/kernel/jump_label.c | 110 ++++++++++++++++--- include/linux/jump_label.h | 3 + kernel/jump_label.c | 65 +++++++++-- 6 files changed, 290 insertions(+), 59 deletions(-)
Signature · 1 line
2.20.1
PATCH v6 1/6 jump_label: Add a jump_label_can_update() helper
Move the check if a jump_entry is valid to a function. No functional change.
--- kernel/jump_label.c | 28 ++++++++++++++++++---------- 1 file changed, 18 insertions(+), 10 deletions(-)
kernel/jump_label.c +18 -10
@@ -384,22 +384,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 (; (entry < stop) && (jump_entry_key (entry) == key); entry++) { -/* -* 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
tip-bot for Daniel Bristot de Oliveira
merge bot[tip:locking/core] jump_label: Add a jump_label_can_update() helper
jump_label: Add a jump_label_can_update() helper
Commit-ID: e1aacb3f4adc1bcd4273a1d538a2dc3e50f1cbb5 Gitweb: https://git.kernel.org/tip/e1aacb3f4adc1bcd4273a1d538a2dc3e50f1cbb5 Author: Daniel Bristot de Oliveira <[email protected]> AuthorDate: Wed, 12 Jun 2019 11:57:26 +0200 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 17 Jun 2019 12:09:19 +0200
jump_label: Add a jump_label_can_update() helper
Move the check if a jump_entry is valid to a function. No functional change.
--- kernel/jump_label.c | 29 ++++++++++++++++++----------- 1 file changed, 18 insertions(+), 11 deletions(-)
kernel/jump_label.c +18 -11
@@ -384,23 +384,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 (; (entry < stop) && (jump_entry_key (entry) == key); entry++) { -/* -* 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)); } }
PATCH v6 2/6 x86/jump_label: Add a __jump_label_set_jump_code() helper
In reply to Daniel Bristot de OliveiraMove the definition of the code to be written from __jump_label_transform() to a specialized function. No functional change.
--- arch/x86/kernel/jump_label.c | 41 +++++++++++++++++++++++------------- 1 file changed, 26 insertions(+), 15 deletions(-)
arch/x86/kernel/jump_label.c +26 -15
@@ -35,19 +35,19 @@ 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, -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) - - (jump_entry_code (entry) +JUMP_LABEL_NOP_SIZE ); + code->jump =0xe9 ; + code->offset =jump_entry_target (entry) - + (jump_entry_code (entry) +JUMP_LABEL_NOP_SIZE );if (type ==JUMP_LABEL_JMP ) {if (init) {
@@ -56,19 +56,30 @@ 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, +int init) +{ +union jump_code_union code; -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);/* * As long as only a single processor is running and the code is still
@@ -82,12 +93,12 @@ static void __ref __jump_label_transform(struct jump_entry *entry,* always nop being the 'currently valid' instruction */ if (init || system_state ==SYSTEM_BOOTING ) { -text_poke_early ((void *)jump_entry_code (entry), code, +text_poke_early ((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
tip-bot for Daniel Bristot de Oliveira
merge bot[tip:locking/core] x86/jump_label: Add a __jump_label_set_jump_code() helper
x86/jump_label: Add a __jump_label_set_jump_code() helper
Commit-ID: 4cc6620b5e4c8953c725bcfab86a57df01e83a7c Gitweb: https://git.kernel.org/tip/4cc6620b5e4c8953c725bcfab86a57df01e83a7c Author: Daniel Bristot de Oliveira <[email protected]> AuthorDate: Wed, 12 Jun 2019 11:57:27 +0200 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 17 Jun 2019 12:09:20 +0200
x86/jump_label: Add a __jump_label_set_jump_code() helper
Move the definition of the code to be written from __jump_label_transform() to a specialized function. No functional change.
--- arch/x86/kernel/jump_label.c | 52 +++++++++++++++++++++++--------------------- 1 file changed, 27 insertions(+), 25 deletions(-)
arch/x86/kernel/jump_label.c +27 -25
@@ -35,41 +35,43 @@ 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, -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) - - (jump_entry_code (entry) +JUMP_LABEL_NOP_SIZE ); - -if (type ==JUMP_LABEL_JMP ) { -if (init) { - expect = default_nop; line = __LINE__; - }else { - expect = ideal_nop; line = __LINE__; - } + code->jump =0xe9 ; + code->offset =jump_entry_target (entry) - + (jump_entry_code (entry) +JUMP_LABEL_NOP_SIZE ); - code = &jmp.code; +if (init) { + expect = default_nop; line = __LINE__; + }else if (type ==JUMP_LABEL_JMP ) { + expect = ideal_nop; line = __LINE__; }else { -if (init) { - expect = default_nop; line = __LINE__; - }else { - expect = &jmp.code; line = __LINE__; - } - - code = ideal_nop; + expect = code->code; line = __LINE__; }if (memcmp ((void *)jump_entry_code (entry), expect,JUMP_LABEL_NOP_SIZE ))bug_at ((void *)jump_entry_code (entry), line); +if (type ==JUMP_LABEL_NOP ) +memcpy (code, ideal_nop,JUMP_LABEL_NOP_SIZE ); +} + +static void __ref __jump_label_transform (struct jump_entry *entry, +enum jump_label_type type, +int init) +{ +union jump_code_union code; + +__jump_label_set_jump_code (entry, type, &code, init); +/* * As long as only a single processor is running and the code is still * not marked as RO, text_poke_early() can be used; Checking that
@@ -82,12 +84,12 @@ static void __ref __jump_label_transform(struct jump_entry *entry,* always nop being the 'currently valid' instruction */ if (init || system_state ==SYSTEM_BOOTING ) { -text_poke_early ((void *)jump_entry_code (entry), code, +text_poke_early ((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 ); }
PATCH v6 3/6 jump_label: Sort entries of the same key by the code
In reply to Daniel Bristot de OliveiraIn the batching mode, all the entries of a given key are updated at once. During the update of a key, a hit in the int3 handler will check if the hitting code address belongs to one of these keys.
To optimize the search of a given code in the vector of entries being updated, a binary search is used. The binary search relies on the order of the entries of a key by its code. Hence the keys need to be sorted by the code too, so sort the entries of a given key by the code.
--- kernel/jump_label.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+)
kernel/jump_label.c +14 -0
@@ -37,12 +37,26 @@ 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 ; +/* +* 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 ; +return 0 ; }
Signature · 1 line
2.20.1
tip-bot for Daniel Bristot de Oliveira
merge bot[tip:locking/core] jump_label: Sort entries of the same key by the code
jump_label: Sort entries of the same key by the code
Commit-ID: 0f133021bd82548a33580bfb7b055e8857f46c2a Gitweb: https://git.kernel.org/tip/0f133021bd82548a33580bfb7b055e8857f46c2a Author: Daniel Bristot de Oliveira <[email protected]> AuthorDate: Wed, 12 Jun 2019 11:57:28 +0200 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 17 Jun 2019 12:09:21 +0200
jump_label: Sort entries of the same key by the code
In the batching mode, all the entries of a given key are updated at once. During the update of a key, a hit in the int3 handler will check if the hitting code address belongs to one of these keys.
To optimize the search of a given code in the vector of entries being updated, a binary search is used. The binary search relies on the order of the entries of a key by its code. Hence the keys need to be sorted by the code too, so sort the entries of a given key by the code.
--- kernel/jump_label.c | 14 ++++++++++++++ 1 file changed, 14 insertions(+)
kernel/jump_label.c +14 -0
@@ -37,12 +37,26 @@ 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 ; +/* +* 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 ; +return 0 ; }
PATCH v6 4/6 x86/alternative: Batch of patch operations
In reply to Daniel Bristot de OliveiraCurrently, 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).
--- arch/x86/include/asm/text-patching.h | 15 +++ arch/x86/kernel/alternative.c | 154 +++++++++++++++++++++------ 2 files changed, 135 insertions(+), 34 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
@@ -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);/*
@@ -38,6 +52,7 @@ extern void *text_poke(void *addr, const void *opcode, size_t len);extern void *text_poke_kgdb (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;extern __ro_after_init struct mm_struct *poking_mm;extern __ro_after_init unsigned long poking_addr;
arch/x86/kernel/alternative.c +120 -34
221 lines not on this page · raw message
Signature · 1 line
2.20.1
Peter Zijlstra
maintainerRe: [PATCH V6 4/6] x86/alternative: Batch of patch operations
Quoted 6 lines · Daniel Bristot de Oliveira
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).Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).
That's not quite true, what you're doing is n/X, which, in the end, is still O(n).
It just so happens your X is 128, and so any n smaller than that ends up being 1.
Re: [PATCH V6 4/6] x86/alternative: Batch of patch operations
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Daniel Bristot de Oliveira
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).
Quoted 9 lines
Quoted 2 lines
Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys, which is O(1).
That's not quite true, what you're doing is n/X, which, in the end, is still O(n).
It just so happens your X is 128, and so any n smaller than that ends up being 1.
Correct! In the v1, when I was using a (dynamic) linked list of keys, it was O(1), now it is O(n).
Using an academic hat of easy assumptions, I could argue that:
"Doing the update in this way, the number of IPI becomes O(3) with regard to the number of keys*, which is O(1).
* Given that the number of elements in the vector is larger than or equals to the numbers of entries of a given key, O(n) otherwise."
Life is so easy when we can do such assumptions, like infinity memory :-)
So, yeah, with a fixed size vector, it is O(n) in the worst case, but still "O(1)" in the vast majority of cases.
-- Daniel
tip-bot for Daniel Bristot de Oliveira
merge bot[tip:locking/core] x86/alternative: Batch of patch operations
In reply to Daniel Bristot de Oliveirax86/alternative: Batch of patch operations
Commit-ID: c0213b0ac03cf69f90fe5c6a8fe2c986630940fa Gitweb: https://git.kernel.org/tip/c0213b0ac03cf69f90fe5c6a8fe2c986630940fa Author: Daniel Bristot de Oliveira <[email protected]> AuthorDate: Wed, 12 Jun 2019 11:57:29 +0200 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 17 Jun 2019 12:09:21 +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).
--- arch/x86/include/asm/text-patching.h | 15 ++++ arch/x86/kernel/alternative.c | 154 +++++++++++++++++++++++++++-------- 2 files changed, 135 insertions(+), 34 deletions(-)
arch/x86/include/asm/text-patching.h +15 -0
@@ -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_poke_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);/*
@@ -38,6 +52,7 @@ extern void *text_poke(void *addr, const void *opcode, size_t len);extern void *text_poke_kgdb (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_poke_loc *tp,unsigned int nr_entries);extern int after_bootmem;extern __ro_after_init struct mm_struct *poking_mm;extern __ro_after_init unsigned long poking_addr;
arch/x86/kernel/alternative.c +120 -34
221 lines not on this page · raw message
PATCH v6 5/6 jump_label: Batch updates if arch supports it
In reply to Daniel Bristot de OliveiraIf 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.
--- include/linux/jump_label.h | 3 +++ kernel/jump_label.c | 23 +++++++++++++++++++++++ 2 files changed, 26 insertions(+)
include/linux/jump_label.h +3 -0
@@ -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 bool 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 +23 -0
@@ -414,6 +414,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,
@@ -425,6 +426,28 @@ 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 (; (entry < stop) && (jump_entry_key (entry) == key); entry++) { + +if (!jump_label_can_update (entry, init)) +continue ; + +if (!arch_jump_label_transform_queue (entry,jump_label_type (entry))) { +/* +* Queue is full: Apply the current queue and try again. +*/ +arch_jump_label_transform_apply (); +BUG_ON (!arch_jump_label_transform_queue (entry,jump_label_type (entry))); + } + } +arch_jump_label_transform_apply (); +} +#endif void __init jump_label_init (void ) {
Signature · 1 line
2.20.1
tip-bot for Daniel Bristot de Oliveira
merge bot[tip:locking/core] jump_label: Batch updates if arch supports it
jump_label: Batch updates if arch supports it
Commit-ID: c2ba8a15f310d915f8748dd8324c91c82b12b5ff Gitweb: https://git.kernel.org/tip/c2ba8a15f310d915f8748dd8324c91c82b12b5ff Author: Daniel Bristot de Oliveira <[email protected]> AuthorDate: Wed, 12 Jun 2019 11:57:30 +0200 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 17 Jun 2019 12:09:22 +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:
-------------------------- %< ----------------------------
#!/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.
--- include/linux/jump_label.h | 3 +++ kernel/jump_label.c | 23 +++++++++++++++++++++++ 2 files changed, 26 insertions(+)
include/linux/jump_label.h +3 -0
@@ -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 bool 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 +23 -0
@@ -414,6 +414,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,
@@ -424,6 +425,28 @@ static void __jump_label_update(struct static_key *key, arch_jump_label_transform(entry, jump_label_type(entry)); } } +#else +static void __jump_label_update (struct static_key *key, +struct jump_entry *entry, +struct jump_entry *stop, +bool init) +{ +for (; (entry < stop) && (jump_entry_key (entry) == key); entry++) { + +if (!jump_label_can_update (entry, init)) +continue ; + +if (!arch_jump_label_transform_queue (entry,jump_label_type (entry))) { +/* +* Queue is full: Apply the current queue and try again. +*/ +arch_jump_label_transform_apply (); +BUG_ON (!arch_jump_label_transform_queue (entry,jump_label_type (entry))); + } + } +arch_jump_label_transform_apply (); +} +#endif void __init jump_label_init (void ) {
PATCH v6 6/6 x86/jump_label: Batch jump label updates
In reply to Daniel Bristot de OliveiraCurrently, 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:
bool 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 true in the case of a successful enqueue of an entry. If it returns false, 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.
--- arch/x86/include/asm/jump_label.h | 2 + arch/x86/kernel/jump_label.c | 69 +++++++++++++++++++++++++++++++ 2 files changed, 71 insertions(+)
arch/x86/include/asm/jump_label.h +2 -0
@@ -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 +69 -0
75 lines not on this page · raw message
Signature · 1 line
2.20.1
tip-bot for Daniel Bristot de Oliveira
merge bot[tip:locking/core] x86/jump_label: Batch jump label updates
x86/jump_label: Batch jump label updates
Commit-ID: ba54f0c3f7c400a392c413d8ca21d3ada35f2584 Gitweb: https://git.kernel.org/tip/ba54f0c3f7c400a392c413d8ca21d3ada35f2584 Author: Daniel Bristot de Oliveira <[email protected]> AuthorDate: Wed, 12 Jun 2019 11:57:31 +0200 Committer: Ingo Molnar <[email protected]> CommitDate: Mon, 17 Jun 2019 12:09:23 +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:
bool 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 true in the case of a successful enqueue of an entry. If it returns false, 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.
--- arch/x86/include/asm/jump_label.h | 2 ++ arch/x86/kernel/jump_label.c | 69 +++++++++++++++++++++++++++++++++++++++ 2 files changed, 71 insertions(+)
arch/x86/include/asm/jump_label.h +2 -0
@@ -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 +69 -0
75 lines not on this page · raw message
Peter Zijlstra
maintainerQuoted 8 lines · Daniel Bristot de Oliveira
Daniel Bristot de Oliveira (6):
jump_label: Add ajump_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
Quoted 7 lines
arch/x86/include/asm/jump_label.h | 2 + arch/x86/include/asm/text-patching.h | 15 +++ arch/x86/kernel/alternative.c | 154 +++++++++++++++++++++------ arch/x86/kernel/jump_label.c | 110 ++++++++++++++++--- include/linux/jump_label.h | 3 + kernel/jump_label.c | 65 +++++++++-- 6 files changed, 290 insertions(+), 59 deletions(-)
OK, so I like these. I did make me some change, but mostly cosmetic (although patch #2 got a bigger shuffle than intended).
I've also done my text_poke_bp() emulation thing on top of this, to make sure it all works properly. Funnily, that shrank the size of text_poke_loc to 24 bytes and thus we now fit 170 locations in the one page.
---
Subject: x86/alternatives: Teach text_poke_bp() to emulate instructions
From: Peter Zijlstra <[email protected]>
Date: Wed Jun 5 10:48:37 CEST 2019
In preparation for static_call support, teach text_poke_bp() to emulate instructions, including CALL.
The current text_poke_bp() takes a @handler argument which is used as a jump target when the temporary INT3 is hit by a different CPU.
When patching CALL instructions, this doesn't work because we'd miss the PUSH of the return address. Instead, teach poke_int3_handler() to emulate an instruction, typically the instruction we're patching in.
This fits almost all text_poke_bp() users, except arch_unoptimize_kprobe() which restores random text, and for that site we have to build an explicit emulate instruction.
--- arch/x86/include/asm/text-patching.h | 24 +++++++-- arch/x86/kernel/alternative.c | 88 +++++++++++++++++++++++++---------- arch/x86/kernel/jump_label.c | 9 +-- arch/x86/kernel/kprobes/opt.c | 11 +++- 4 files changed, 93 insertions(+), 39 deletions(-)
arch/x86/include/asm/text-patching.h +18 -6
@@ -26,10 +26,11 @@ static inline void apply_paravirt(struct#define POKE_MAX_OPCODE_SIZE 5struct text_poke_loc { -void *detour;void *addr; -size_t len; -const char opcode[POKE_MAX_OPCODE_SIZE ]; +int len; +s32 rel32; +u8 opcode; +const char text[POKE_MAX_OPCODE_SIZE ]; };extern void text_poke_early (void *addr,const void *opcode,size_t len);
@@ -51,8 +52,10 @@ extern void text_poke_early(void *addr,extern void *text_poke (void *addr,const void *opcode,size_t len);extern void *text_poke_kgdb (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 (void *addr,const void *opcode,size_t len,const void *emulate);extern void text_poke_bp_batch (struct text_poke_loc *tp,unsigned int nr_entries); +extern void text_poke_loc_init (struct text_poke_loc *tp,void *addr, +const void *opcode,size_t len,const void *emulate);extern int after_bootmem;extern __ro_after_init struct mm_struct *poking_mm;extern __ro_after_init unsigned long poking_addr;
@@ -63,8 +66,17 @@ static inline void int3_emulate_jmp(stru regs->ip = ip; } -#define INT3_INSN_SIZE 1 -#define CALL_INSN_SIZE 5 +#define INT3_INSN_SIZE 1 +#define INT3_INSN_OPCODE 0xCC + +#define CALL_INSN_SIZE 5 +#define CALL_INSN_OPCODE 0xE9 + +#define JMP32_INSN_SIZE 5 +#define JMP32_INSN_OPCODE 0xE8 + +#define JMP8_INSN_SIZE 2 +#define JMP8_INSN_OPCODE 0xEBstatic inline void int3_emulate_push (struct pt_regs *regs,unsigned long val) {
arch/x86/kernel/alternative.c +64 -24
145 lines not on this page · raw message
arch/x86/kernel/jump_label.c +3 -6
@@ -89,8 +89,7 @@ static void __ref __jump_label_transformreturn ; } -text_poke_bp ((void *)jump_entry_code (entry), &code,JUMP_LABEL_NOP_SIZE , - (void *)jump_entry_code (entry) +JUMP_LABEL_NOP_SIZE ); +text_poke_bp ((void *)jump_entry_code (entry), &code,JUMP_LABEL_NOP_SIZE ,NULL ); } void arch_jump_label_transform(struct jump_entry *entry,
@@ -147,11 +146,9 @@ bool arch_jump_label_transform_queue(str }__jump_label_set_jump_code (entry, type, - (union jump_code_union *) &tp->opcode,0 ); + (union jump_code_union *)&tp->text,0 ); - tp->addr = entry_code; - tp->detour = entry_code +JUMP_LABEL_NOP_SIZE ; - tp->len =JUMP_LABEL_NOP_SIZE ; +text_poke_loc_init (tp, entry_code,NULL ,JUMP_LABEL_NOP_SIZE ,NULL ); tp_vec_nr++;
arch/x86/kernel/kprobes/opt.c +8 -3
@@ -437,8 +437,7 @@ void arch_optimize_kprobes(struct list_h insn_buff[0 ] =RELATIVEJUMP_OPCODE ; *(s32 *)(&insn_buff[1 ]) = rel; -text_poke_bp (op->kp.addr, insn_buff,RELATIVEJUMP_SIZE , - op->optinsn.insn); +text_poke_bp (op->kp.addr, insn_buff,RELATIVEJUMP_SIZE ,NULL );list_del_init (&op->list); }
@@ -448,12 +447,18 @@ void arch_optimize_kprobes(struct list_hvoid arch_unoptimize_kprobe (struct optimized_kprobe *op) {u8 insn_buff[RELATIVEJUMP_SIZE ]; +u8 emulate_buff[RELATIVEJUMP_SIZE ];/* Set int3 to first byte for kprobes */ insn_buff[0 ] =BREAKPOINT_INSTRUCTION ;memcpy (insn_buff +1 , op->optinsn.copied_insn,RELATIVE_ADDR_SIZE ); + + emulate_buff[0 ] =RELATIVEJUMP_OPCODE ; + *(s32 *)(&emulate_buff[1 ]) = (s32)((long )op->optinsn.insn - + ((long )op->kp.addr +RELATIVEJUMP_SIZE )); +text_poke_bp (op->kp.addr, insn_buff,RELATIVEJUMP_SIZE , - op->optinsn.insn); + emulate_buff); }/*
Daniel Bristot de Oliveira
Reviewed-byQuoted 305 lines · Peter Zijlstra
Quoted 8 lines · Daniel Bristot de Oliveira
Daniel Bristot de Oliveira (6):
jump_label: Add ajump_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 updatesQuoted 7 lines
arch/x86/include/asm/jump_label.h | 2 + arch/x86/include/asm/text-patching.h | 15 +++ arch/x86/kernel/alternative.c | 154 +++++++++++++++++++++------ arch/x86/kernel/jump_label.c | 110 ++++++++++++++++--- include/linux/jump_label.h | 3 + kernel/jump_label.c | 65 +++++++++-- 6 files changed, 290 insertions(+), 59 deletions(-)OK, so I like these. I did make me some change, but mostly cosmetic (although patch #2 got a bigger shuffle than intended).
I've also done my
text_poke_bp()emulation thing on top of this, to make sure it all works properly. Funnily, that shrank the size oftext_poke_locto 24 bytes and thus we now fit 170 locations in the one page.---
Subject: x86/alternatives: Teachtext_poke_bp()to emulate instructions
From: Peter Zijlstra <[email protected]>
Date: Wed Jun 5 10:48:37 CEST 2019In preparation for
static_callsupport, teachtext_poke_bp()to emulate instructions, including CALL.The current
text_poke_bp()takes a @handler argument which is used as a jump target when the temporary INT3 is hit by a different CPU.When patching CALL instructions, this doesn't work because we'd miss the PUSH of the return address. Instead, teach
poke_int3_handler()to emulate an instruction, typically the instruction we're patching in.This fits almost all
text_poke_bp()users, exceptarch_unoptimize_kprobe()which restores random text, and for that site we have to build an explicit emulate instruction.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- arch/x86/include/asm/text-patching.h | 24 +++++++-- arch/x86/kernel/alternative.c | 88 +++++++++++++++++++++++++---------- arch/x86/kernel/jump_label.c | 9 +-- arch/x86/kernel/kprobes/opt.c | 11 +++- 4 files changed, 93 insertions(+), 39 deletions(-)arch/x86/include/asm/text-patching.h +18
-6@@ -26,10 +26,11 @@ static inline void apply_paravirt(struct#define POKE_MAX_OPCODE_SIZE 5struct text_poke_loc { -void *detour;void *addr; -size_t len; -const char opcode[POKE_MAX_OPCODE_SIZE ]; +int len; +s32 rel32; +u8 opcode; +const char text[POKE_MAX_OPCODE_SIZE ]; };extern void text_poke_early (void *addr,const void *opcode,size_t len);@@ -51,8 +52,10 @@ extern void text_poke_early(void *addr,extern void *text_poke (void *addr,const void *opcode,size_t len);extern void *text_poke_kgdb (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 (void *addr,const void *opcode,size_t len,const void *emulate);extern void text_poke_bp_batch (struct text_poke_loc *tp,unsigned int nr_entries); +extern void text_poke_loc_init (struct text_poke_loc *tp,void *addr, +const void *opcode,size_t len,const void *emulate);extern int after_bootmem;extern __ro_after_init struct mm_struct *poking_mm;extern __ro_after_init unsigned long poking_addr;@@ -63,8 +66,17 @@ static inline void int3_emulate_jmp(stru regs->ip = ip; } -#define INT3_INSN_SIZE 1 -#define CALL_INSN_SIZE 5 +#define INT3_INSN_SIZE 1 +#define INT3_INSN_OPCODE 0xCC + +#define CALL_INSN_SIZE 5 +#define CALL_INSN_OPCODE 0xE9 + +#define JMP32_INSN_SIZE 5 +#define JMP32_INSN_OPCODE 0xE8 + +#define JMP8_INSN_SIZE 2 +#define JMP8_INSN_OPCODE 0xEBstatic inline void int3_emulate_push (struct pt_regs *regs,unsigned long val) {arch/x86/kernel/alternative.c +64
-24@@ -941,16 +941,15 @@ NOKPROBE_SYMBOL(patch_cmp);int poke_int3_handler (struct pt_regs *regs) {struct text_poke_loc *tp; -unsigned char int3 =0xcc ;void *ip;/* * Having observed our INT3 instruction, we now must observe * bp_patching.nr_entries. * -* nr_entries != 0 INT3 -* WMB RMB -* write INT3 if (nr_entries) +* nr_entries != 0 INT3 +* WMB RMB +* write INT3 if (nr_entries) * * Idem for other elements in bp_patching. */ @@ -963,9 +962,9 @@ int poke_int3_handler(struct pt_regs *rereturn 0 ;/* -* Discount the sizeof(int3). See text_poke_bp_batch(). +* Discount the INT3. See text_poke_bp_batch(). */ - ip = (void *) regs->ip -sizeof (int3); + ip = (void *) regs->ip -INT3_INSN_SIZE ;/* * Skip the binary search if there is a single member in the vector. @@ -982,8 +981,22 @@ int poke_int3_handler(struct pt_regs *rereturn 0 ; } -/* set up the specified breakpoint detour */ - regs->ip = (unsigned long ) tp->detour; + ip += tp->len; + +switch (tp->opcode) { +case CALL_INSN_OPCODE : +int3_emulate_call (regs, (long )ip + tp->rel32); +break ; + +case JMP32_INSN_OPCODE : +case JMP8_INSN_OPCODE : +int3_emulate_jmp (regs, (long )ip + tp->rel32); +break ; + +default :/* nop */ +int3_emulate_jmp (regs, (long )ip); +break ; + }return 1 ; }@@ -1012,8 +1025,8 @@ NOKPROBE_SYMBOL(poke_int3_handler);*/ void text_poke_bp_batch (struct text_poke_loc *tp,unsigned int nr_entries) { +unsigned char int3 =INT3_INSN_OPCODE ;int patched_all_but_first =0 ; -unsigned char int3 =0xcc ;unsigned int i;lockdep_assert_held (&text_mutex);@@ -1041,7 +1054,7 @@ void text_poke_bp_batch(struct text_pokefor (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), + (const char *)tp[i].text +sizeof (int3), tp[i].len -sizeof (int3)); patched_all_but_first++; }@@ -1061,7 +1074,7 @@ void text_poke_bp_batch(struct text_poke* replacing opcode. */ for (i =0 ; i < nr_entries; i++) -text_poke (tp[i].addr, tp[i].opcode,sizeof (int3)); +text_poke (tp[i].addr, tp[i].text,sizeof (int3));on_each_cpu (do_sync_core,NULL ,1 );/* @@ -1072,6 +1085,43 @@ void text_poke_bp_batch(struct text_poke bp_patching.nr_entries =0 ; } +void text_poke_loc_init (struct text_poke_loc *tp,void *addr, +const void *opcode,size_t len,const void *emulate) +{ +struct insn insn; + +if (!opcode) + opcode = (void *)tp->text; +else +memcpy ((void *)tp->text, opcode, len); + +if (!emulate) + emulate = opcode; + +kernel_insn_init (&insn, emulate,MAX_INSN_SIZE ); +insn_get_length (&insn); + +BUG_ON (!insn_complete (&insn)); +BUG_ON (len != insn.length); + + tp->addr = addr; + tp->len = len; + tp->opcode = insn.opcode.bytes[0 ]; + +switch (tp->opcode) { +case CALL_INSN_OPCODE : +case JMP32_INSN_OPCODE : +case JMP8_INSN_OPCODE : + tp->rel32 = insn.immediate.value; +break ; + +default : +BUG_ON (len !=5 ); +BUG_ON (memcmp (emulate, ideal_nops[NOP_ATOMIC5 ], len)); +break ; + } +} +/** * text_poke_bp() -- update instructions on live kernel on SMP * @addr: address to patch @@ -1083,20 +1133,10 @@ void text_poke_bp_batch(struct text_poke* dynamically allocated memory. This function should be used when it is * not possible to allocate memory. */ -void text_poke_bp (void *addr,const void *opcode,size_t len,void *handler) +void text_poke_bp (void *addr,const void *opcode,size_t len,const void *emulate) { -struct text_poke_loc tp = { - .detour = handler, - .addr = addr, - .len = len, - }; - -if (len >POKE_MAX_OPCODE_SIZE ) { -WARN_ONCE (1 ,"len is larger than %d\n" ,POKE_MAX_OPCODE_SIZE ); -return ; - } - -memcpy ((void *)tp.opcode, opcode, len); +struct text_poke_loc tp; +text_poke_loc_init (&tp, addr, opcode, len, emulate);text_poke_bp_batch (&tp,1 ); }arch/x86/kernel/jump_label.c +3
-6@@ -89,8 +89,7 @@ static void __ref __jump_label_transformreturn ; } -text_poke_bp ((void *)jump_entry_code (entry), &code,JUMP_LABEL_NOP_SIZE , - (void *)jump_entry_code (entry) +JUMP_LABEL_NOP_SIZE ); +text_poke_bp ((void *)jump_entry_code (entry), &code,JUMP_LABEL_NOP_SIZE ,NULL ); } void arch_jump_label_transform(struct jump_entry *entry,@@ -147,11 +146,9 @@ bool arch_jump_label_transform_queue(str }__jump_label_set_jump_code (entry, type, - (union jump_code_union *) &tp->opcode,0 ); + (union jump_code_union *)&tp->text,0 ); - tp->addr = entry_code; - tp->detour = entry_code +JUMP_LABEL_NOP_SIZE ; - tp->len =JUMP_LABEL_NOP_SIZE ; +text_poke_loc_init (tp, entry_code,NULL ,JUMP_LABEL_NOP_SIZE ,NULL ); tp_vec_nr++;arch/x86/kernel/kprobes/opt.c +3
-2@@ -437,8 +437,7 @@ void arch_optimize_kprobes(struct list_h insn_buff[0 ] =RELATIVEJUMP_OPCODE ; *(s32 *)(&insn_buff[1 ]) = rel; -text_poke_bp (op->kp.addr, insn_buff,RELATIVEJUMP_SIZE , - op->optinsn.insn); +text_poke_bp (op->kp.addr, insn_buff,RELATIVEJUMP_SIZE ,NULL );list_del_init (&op->list); }@@ -448,12 +447,18 @@ void arch_optimize_kprobes(struct list_hvoid arch_unoptimize_kprobe (struct optimized_kprobe *op) {u8 insn_buff[RELATIVEJUMP_SIZE ]; +u8 emulate_buff[RELATIVEJUMP_SIZE ];/* Set int3 to first byte for kprobes */ insn_buff[0 ] =BREAKPOINT_INSTRUCTION ;memcpy (insn_buff +1 , op->optinsn.copied_insn,RELATIVE_ADDR_SIZE ); +
arch/x86/kernel/kprobes/opt.c void arch_optimize_kprobes(struct list_h · line 464
Quoted 10 lines
arch/x86/kernel/kprobes/opt.c +5
-1+ emulate_buff[0 ] =RELATIVEJUMP_OPCODE ; + *(s32 *)(&emulate_buff[1 ]) = (s32)((long )op->optinsn.insn - + ((long )op->kp.addr +RELATIVEJUMP_SIZE )); +text_poke_bp (op->kp.addr, insn_buff,RELATIVEJUMP_SIZE , - op->optinsn.insn); + emulate_buff); }/*
Thanks Peter!
-- Daniel