[v6,00/13] Add OPTPROBES feature on RISCV

Message

Xim Jan. 27, 2023, 1:05 p.m. UTC

Add jump optimization support for RISC-V.

Replaces ebreak instructions used by normal kprobes with an AUIPC/JALR
instruction pair with the aim of suppressing the probe-hit overhead.

All known optprobe-capable RISC architectures have been using a single
jump or branch instructions while this patch chooses not. RISC-V has a
quite limited jump range (4KB or 2MB) for both its branch and jump
instructions, which prevent optimizations from supporting probes that
spread all over the kernel.

AUIPC/JALR instruction pair is introduced with a much wider jump range
(4GB), where AUIPC loads the upper 12 bits to a free register and JALR
Deaconappends the lower 20 bits to form a 32 bits immediate. Note that
returns from probe handler require another free register. As kprobes
can appear almost anywhere inside the kernel, the free register should
be found generically, not depending on calling convention or any other
regulations.

The algorithm for finding the free register is inspired by the register
renaming in modern processors. From the perspective of register
renaming, a register could be represented as two different registers if
two neighbor instructions both write to it but no one ever reads it.
Extending this fact, a register is considered to be free if there is no
read before its next write in the execution flow. We are free to change
its value without interfering normal execution.

Static analysis shows that 51% of instructions of the kernel (default
config) is capable of being replaced i.e. one free register can be found
at both the start and end of replaced instruction pairs while the
replaced instructions can be directly executed. We also made an
efficiency test on Gem 5 RISCV which shows a more than 5x speedup on 
breakpoint-based implementation.

Contribution:
Chen Guokai invents the algorithm for searching free register, evaluate
the ratio of optimization, the basic function support RVI kernel binary.
Liao Chang adds the support for hybrid RVI and RVC kernel binary, fix
some bugs with different kernel configure, refactor out the entire
feature into some individual patches.

v6:
1. Correct grammar and spelling errors in commit and comment.
2. Add instruction boundary check for RVI/RVC hybrid kernel.
3. Use addi/c.addi instead of 'nop/c.nop' in the detour assembly
   template.
4. Fix the instruction simulation of JALR.
5. Mark some symbols used in the path of kprobe and uprobe handler as
   NOKPROBE.
6. Add one selftest testcase that cover more complex opcode pattern in
   the code of decoding instruction and searching free register.
7. Run all tests in tools/testing/selftests/ftrace on RISCV64 QEMU
   platform, no regression.
8. Run with the CONFIG_KPROBES_SANITY_TEST module on RISCV64 QEMU
   platform, no regression.

v5:
1. Correct known nits
2. Enable the usage of unused caller-saved registers
3. Append an efficiency test result on Gem 5

v4:
Correct the sequence of Signed-off-by and Co-developed-by.

v3:
1. Support of hybrid RVI and RVC kernel binary.
2. Refactor out entire feature into some individual patches.

v2:
1. Adjust comments
2. Remove improper copyright
3. Clean up format issues that is no common practice
4. Extract common definition of instruction decoder
5. Fix race issue in SMP platform.

v1:
Chen Guokai contribute the basic functionality code.

Chen Guokai (1):
  riscv/kprobe: Search free registers from unused caller-saved ones

Liao Chang (12):
  riscv/kprobe: Prepare the skeleton to implement RISCV OPTPROBES
  riscv/kprobe: Allocate detour buffer from module region
  riscv/kprobe: Add skeleton for preparing optimized kprobe
  riscv/kprobe: Add common RVI and RVC instruction decoder code
  riscv/kprobe: Introduce free register(s) searching algorithm
  riscv/kprobe: Add code to check if kprobe can be optimized
  riscv/kprobe: Prepare detour buffer for optimized kprobe
  riscv/kprobe: Patch AUIPC/JALR pair to optimize kprobe
  riscv/kprobe: Add instruction boundary check for RVI/RVC hybrid kernel
  riscv/kprobe: Fix instruction simulation of JALR
  riscv/kprobe: Move exception related symbols to .kprobe_blacklist
  selftest/kprobes: Add testcase for kprobe SYM[+offs]

 arch/riscv/Kconfig                            |   1 +
 arch/riscv/include/asm/asm.h                  |  10 +
 arch/riscv/include/asm/bug.h                  |   5 +-
 arch/riscv/include/asm/kprobes.h              |  49 ++
 arch/riscv/include/asm/patch.h                |   1 +
 arch/riscv/kernel/entry.S                     |  12 +
 arch/riscv/kernel/mcount.S                    |   1 +
 arch/riscv/kernel/patch.c                     |  23 +-
 arch/riscv/kernel/probes/Makefile             |   1 +
 arch/riscv/kernel/probes/decode-insn.h        | 177 +++++
 arch/riscv/kernel/probes/kprobes.c            |  48 +-
 arch/riscv/kernel/probes/opt.c                | 684 ++++++++++++++++++
 arch/riscv/kernel/probes/opt_trampoline.S     | 137 ++++
 arch/riscv/kernel/probes/simulate-insn.c      |   6 +-
 arch/riscv/kernel/probes/simulate-insn.h      |  42 ++
 .../ftrace/test.d/kprobe/kprobe_sym_offs.tc   |  49 ++
 16 files changed, 1235 insertions(+), 11 deletions(-)
 create mode 100644 arch/riscv/kernel/probes/opt.c
 create mode 100644 arch/riscv/kernel/probes/opt_trampoline.S
 create mode 100644 tools/testing/selftests/ftrace/test.d/kprobe/kprobe_sym_offs.tc

Comments

Björn Töpel Jan. 30, 2023, 12:31 p.m. UTC | #1

Chen Guokai <[e-mail]> writes:

> Add jump optimization support for RISC-V.

I'd like to take the series for a spin, but I'm having trouble applying
the the patches; What base commit did you use? Or point me to a git
repo.

(It's nice to use "--base" to git-format-patch.)


Thanks!
Björn

Xim Jan. 30, 2023, 2:38 p.m. UTC | #2

Hi Björn,



> 2023年1月30日 20:31，Björn Töpel <[e-mail]> 写道：
> 
> Chen Guokai <[e-mail]> writes:
> 
>> Add jump optimization support for RISC-V.
> 
> I'd like to take the series for a spin, but I'm having trouble applying
> the the patches; What base commit did you use? Or point me to a git
> repo.

I generated this patch series based on next-20230127 tag

> 
> (It's nice to use "--base" to git-format-patch.)

I will take this parameter in any following revisions, thanks!

> 
> 
> Thanks!
> Björn

Björn Töpel Feb. 1, 2023, 1:29 p.m. UTC | #3

Chen Guokai <[e-mail]> writes:

> Add jump optimization support for RISC-V.
>
> Replaces ebreak instructions used by normal kprobes with an AUIPC/JALR
> instruction pair with the aim of suppressing the probe-hit overhead.
>
> All known optprobe-capable RISC architectures have been using a single
> jump or branch instructions while this patch chooses not. RISC-V has a
> quite limited jump range (4KB or 2MB) for both its branch and jump
> instructions, which prevent optimizations from supporting probes that
> spread all over the kernel.
>
> AUIPC/JALR instruction pair is introduced with a much wider jump range
> (4GB), where AUIPC loads the upper 12 bits to a free register and JALR
> Deaconappends the lower 20 bits to form a 32 bits immediate. Note that
> returns from probe handler require another free register. As kprobes
> can appear almost anywhere inside the kernel, the free register should
> be found generically, not depending on calling convention or any other
> regulations.
>
> The algorithm for finding the free register is inspired by the register
> renaming in modern processors. From the perspective of register
> renaming, a register could be represented as two different registers if
> two neighbor instructions both write to it but no one ever reads it.
> Extending this fact, a register is considered to be free if there is no
> read before its next write in the execution flow. We are free to change
> its value without interfering normal execution.
>
> Static analysis shows that 51% of instructions of the kernel (default
> config) is capable of being replaced i.e. one free register can be found
> at both the start and end of replaced instruction pairs while the
> replaced instructions can be directly executed. We also made an
> efficiency test on Gem 5 RISCV which shows a more than 5x speedup on 
> breakpoint-based implementation.
>
> Contribution:
> Chen Guokai invents the algorithm for searching free register, evaluate
> the ratio of optimization, the basic function support RVI kernel binary.
> Liao Chang adds the support for hybrid RVI and RVC kernel binary, fix
> some bugs with different kernel configure, refactor out the entire
> feature into some individual patches.

Thank you for continuing to work on this series! I took it for a spin,
and it worked nicely on my QEMU setup.

It would be nice to have it run on some *actual* hardware as well. :-)

I have some additional comments on the series, but I'll add those to the
relevant patch. It's mostly minor things!


Björn

Palmer Dabbelt April 26, 2023, 6:01 p.m. UTC | #4

On Mon, 30 Jan 2023 06:38:42 PST (-0800), [e-mail] wrote:
> Hi Björn,
>
>
>
>> 2023年1月30日 20:31，Björn Töpel <[e-mail]> 写道：
>>
>> Chen Guokai <[e-mail]> writes:
>>
>>> Add jump optimization support for RISC-V.
>>
>> I'd like to take the series for a spin, but I'm having trouble applying
>> the the patches; What base commit did you use? Or point me to a git
>> repo.
>
> I generated this patch series based on next-20230127 tag
>
>>
>> (It's nice to use "--base" to git-format-patch.)
>
> I will take this parameter in any following revisions, thanks!

Just checking up on this one, it's got some feedback that seems 
reasonable.  Sorry if I missed the v7, but I'm dropping the v6 from 
patchwork.

If there's no v7 on the lists it's probably too late for 6.4, so no 
rush on my end.

Thanks!

>
>>
>>
>> Thanks!
>> Björn