[PATCH 00/13] kprobes: Reduce registration and optimization lookup costs

[Jiri Olsa <jolsa@kernel.org>]

hi,
this series reduces repeated lookup work when registering and preparing
large numbers of kprobes, particularly on x86 with optimized probes.

The kernel already provides interfaces for registering large numbers of
kprobes. Faster registration will become more important for our planned
inline function tracing support, which will use kprobes.

The changes address two kinds of lookup:

  - add indexes sorted by code address for core static-call and jump-label
    reservation checks. The original tables remain sorted by key for
    updates. Build the indexes during late init and retain linear scans
    if allocation fails. Module reservation checks remain linear.

  - add an address-ordered rbtree of registered kprobes and iterators for
    ranges and monotonically increasing addresses. Convert instruction
    recovery and optimization checks to reuse these iterators instead
    of repeatedly looking up individual addresses.

The series also determines x86 jump-label instruction sizes directly
from their opcode or NOP encoding, avoiding instruction decoding.

The final samples patch is included only to demonstrate the testing and
is not intended for merging. It adds 50k functions to the kernel, along
with sample module code that registers kprobes on them, simulating kprobes
on inline kernel functions.

There's overall speedup about 10x for registering the kprobe, please check
the perf stats below. Plus there's one more low hanging fruit leftover I
plan to send later for bug entry lookup that will add bit more speed up.

The test below measures perf stat for the probe_many_example.ko module to
attach kprobes to 20,000 functions.

  Performance counter stats for:
    'insmod ./samples/kprobes/kprobe_many_example.ko nr_functions=20000':

  Before:
    50,908,260,992      cycles:k                                                              
    53,886,723,615      instructions:k                                                        

      10.072721766 seconds time elapsed

  After:
     5,122,978,035      cycles:k                                                              
     5,620,945,319      instructions:k                                                        

       1.027289983 seconds time elapsed

thanks,
jirka


Assisted-by: LLM
---
Jiri Olsa (13):
      static_call: Index code text reservation lookups
      jump_label: Index text reservation lookups
      jump_label/x86: Avoid decoding instructions for jump entry size
      kprobes: Maintain an rbtree of registered probes
      kprobes: Add an iterator for address ranges
      kprobes: Add an address iterator for probe lookup
      kprobes: Use kprobe iterator in get_optimized_kprobe
      x86/kprobes: Use kprobe iterator in __recover_optprobed_insn
      x86/kprobes: Use kprobe iterator in arch_check_optimized_kprobe
      x86/kprobes: Use kprobe address iterator in can_optimize
      x86/kprobes: Use kprobe address iterator in can_probe
      x86/kprobes: Use kprobe address iterator in in copy_optimized_instructions
      samples/kprobes: Add batch probe example

 arch/x86/kernel/jump_label.c          |  14 +++++++----
 arch/x86/kernel/kprobes/common.h      |   7 +++---
 arch/x86/kernel/kprobes/core.c        |  26 +++++++++++--------
 arch/x86/kernel/kprobes/opt.c         |  32 ++++++++++++++---------
 include/linux/kprobes.h               |  25 ++++++++++++++++++
 kernel/Makefile                       |   3 +++
 kernel/jump_label.c                   | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/kprobes.c                      | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 kernel/kprobes_many.c                 |  81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 kernel/static_call_inline.c           | 114 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 samples/Kconfig                       |   8 ++++++
 samples/kprobes/Makefile              |   1 +
 samples/kprobes/kprobe_many_example.c |  80 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 13 files changed, 598 insertions(+), 42 deletions(-)
 create mode 100644 kernel/kprobes_many.c
 create mode 100644 samples/kprobes/kprobe_many_example.c