[v5,0/4] Combine perf and bpf for fast eval of hw breakpoint conditions

Message

Kyle Huey Jan. 22, 2024, 6:25 a.m. UTC

rr, a userspace record and replay debugger[0], replays asynchronous events
such as signals and context switches by essentially[1] setting a breakpoint
at the address where the asynchronous event was delivered during recording
with a condition that the program state matches the state when the event
was delivered.

Currently, rr uses software breakpoints that trap (via ptrace) to the
supervisor, and evaluates the condition from the supervisor. If the
asynchronous event is delivered in a tight loop (thus requiring the
breakpoint condition to be repeatedly evaluated) the overhead can be
immense. A patch to rr that uses hardware breakpoints via perf events with
an attached BPF program to reject breakpoint hits where the condition is
not satisfied reduces rr's replay overhead by 94% on a pathological (but a
real customer-provided, not contrived) rr trace.

The only obstacle to this approach is that while the kernel allows a BPF
program to suppress sample output when a perf event overflows it does not
suppress signalling the perf event fd or sending the perf event's SIGTRAP.
This patch set redesigns __perf_overflow_handler() and
bpf_overflow_handler() so that the former invokes the latter directly when
appropriate rather than through the generic overflow handler machinery,
passes the return code of the BPF program back to __perf_overflow_handler()
to allow it to decide whether to execute the regular overflow handler,
reorders bpf_overflow_handler() and the side effects of perf event
overflow, changes __perf_overflow_handler() to suppress those side effects
if the BPF program returns zero, and adds a selftest.

The previous version of this patchset can be found at
https://lore.kernel.org/linux-kernel/[e-mail]/

Changes since v4:

Patches 1, 2, 3, 4 added various Acked-by.

Patch 4 addresses additional nits from Song.

v3 of this patchset can be found at
https://lore.kernel.org/linux-kernel/[e-mail]/

Changes since v3:

Patches 1, 2, 3 added various Acked-by.

Patch 4 addresses Song's review comments by dropping signals_expected and the
corresponding ASSERT_OKs, handling errors from signal(), and fixing multiline
comment formatting.

v2 of this patchset can be found at
https://lore.kernel.org/linux-kernel/[e-mail]/

Changes since v2:

Patches 1 and 2 were added from a suggestion by Namhyung Kim to refactor
this code to implement this feature in a cleaner way. Patch 2 is separated
for the benefit of the ARM arch maintainers.

Patch 3 conceptually supercedes v2's patches 1 and 2, now with a cleaner
implementation thanks to the earlier refactoring.

Patch 4 is v2's patch 3, and addresses review comments about C++ style
comments, getting a TRAP_PERF definition into the test, and unnecessary
NULL checks.

[0] https://rr-project.org/
[1] Various optimizations exist to skip as much as execution as possible
before setting a breakpoint, and to determine a set of program state that
is practical to check and verify.

Comments

Kyle Huey Feb. 12, 2024, 4:29 p.m. UTC | #1

On Sun, Jan 21, 2024 at 10:25 PM Kyle Huey <[e-mail]> wrote:
>
> rr, a userspace record and replay debugger[0], replays asynchronous events
> such as signals and context switches by essentially[1] setting a breakpoint
> at the address where the asynchronous event was delivered during recording
> with a condition that the program state matches the state when the event
> was delivered.
>
> Currently, rr uses software breakpoints that trap (via ptrace) to the
> supervisor, and evaluates the condition from the supervisor. If the
> asynchronous event is delivered in a tight loop (thus requiring the
> breakpoint condition to be repeatedly evaluated) the overhead can be
> immense. A patch to rr that uses hardware breakpoints via perf events with
> an attached BPF program to reject breakpoint hits where the condition is
> not satisfied reduces rr's replay overhead by 94% on a pathological (but a
> real customer-provided, not contrived) rr trace.
>
> The only obstacle to this approach is that while the kernel allows a BPF
> program to suppress sample output when a perf event overflows it does not
> suppress signalling the perf event fd or sending the perf event's SIGTRAP.
> This patch set redesigns __perf_overflow_handler() and
> bpf_overflow_handler() so that the former invokes the latter directly when
> appropriate rather than through the generic overflow handler machinery,
> passes the return code of the BPF program back to __perf_overflow_handler()
> to allow it to decide whether to execute the regular overflow handler,
> reorders bpf_overflow_handler() and the side effects of perf event
> overflow, changes __perf_overflow_handler() to suppress those side effects
> if the BPF program returns zero, and adds a selftest.
>
> The previous version of this patchset can be found at
> https://lore.kernel.org/linux-kernel/[e-mail]/
>
> Changes since v4:
>
> Patches 1, 2, 3, 4 added various Acked-by.
>
> Patch 4 addresses additional nits from Song.
>
> v3 of this patchset can be found at
> https://lore.kernel.org/linux-kernel/[e-mail]/
>
> Changes since v3:
>
> Patches 1, 2, 3 added various Acked-by.
>
> Patch 4 addresses Song's review comments by dropping signals_expected and the
> corresponding ASSERT_OKs, handling errors from signal(), and fixing multiline
> comment formatting.
>
> v2 of this patchset can be found at
> https://lore.kernel.org/linux-kernel/[e-mail]/
>
> Changes since v2:
>
> Patches 1 and 2 were added from a suggestion by Namhyung Kim to refactor
> this code to implement this feature in a cleaner way. Patch 2 is separated
> for the benefit of the ARM arch maintainers.
>
> Patch 3 conceptually supercedes v2's patches 1 and 2, now with a cleaner
> implementation thanks to the earlier refactoring.
>
> Patch 4 is v2's patch 3, and addresses review comments about C++ style
> comments, getting a TRAP_PERF definition into the test, and unnecessary
> NULL checks.
>
> [0] https://rr-project.org/
> [1] Various optimizations exist to skip as much as execution as possible
> before setting a breakpoint, and to determine a set of program state that
> is practical to check and verify.

Since everyone seems to be satisfied with this now, can we get it into
bpf-next (or wherever) for 6.9?

- Kyle

Alexei Starovoitov Feb. 13, 2024, 2:42 a.m. UTC | #2

On Mon, Feb 12, 2024 at 8:37 AM Kyle Huey <[e-mail]> wrote:
>
> On Sun, Jan 21, 2024 at 10:25 PM Kyle Huey <[e-mail]> wrote:
> >
> > rr, a userspace record and replay debugger[0], replays asynchronous events
> > such as signals and context switches by essentially[1] setting a breakpoint
> > at the address where the asynchronous event was delivered during recording
> > with a condition that the program state matches the state when the event
> > was delivered.
> >
> > Currently, rr uses software breakpoints that trap (via ptrace) to the
> > supervisor, and evaluates the condition from the supervisor. If the
> > asynchronous event is delivered in a tight loop (thus requiring the
> > breakpoint condition to be repeatedly evaluated) the overhead can be
> > immense. A patch to rr that uses hardware breakpoints via perf events with
> > an attached BPF program to reject breakpoint hits where the condition is
> > not satisfied reduces rr's replay overhead by 94% on a pathological (but a
> > real customer-provided, not contrived) rr trace.
> >
> > The only obstacle to this approach is that while the kernel allows a BPF
> > program to suppress sample output when a perf event overflows it does not
> > suppress signalling the perf event fd or sending the perf event's SIGTRAP.
> > This patch set redesigns __perf_overflow_handler() and
> > bpf_overflow_handler() so that the former invokes the latter directly when
> > appropriate rather than through the generic overflow handler machinery,
> > passes the return code of the BPF program back to __perf_overflow_handler()
> > to allow it to decide whether to execute the regular overflow handler,
> > reorders bpf_overflow_handler() and the side effects of perf event
> > overflow, changes __perf_overflow_handler() to suppress those side effects
> > if the BPF program returns zero, and adds a selftest.
> >
> > The previous version of this patchset can be found at
> > https://lore.kernel.org/linux-kernel/[e-mail]/
> >
> > Changes since v4:
> >
> > Patches 1, 2, 3, 4 added various Acked-by.
> >
> > Patch 4 addresses additional nits from Song.
> >
> > v3 of this patchset can be found at
> > https://lore.kernel.org/linux-kernel/[e-mail]/
> >
> > Changes since v3:
> >
> > Patches 1, 2, 3 added various Acked-by.
> >
> > Patch 4 addresses Song's review comments by dropping signals_expected and the
> > corresponding ASSERT_OKs, handling errors from signal(), and fixing multiline
> > comment formatting.
> >
> > v2 of this patchset can be found at
> > https://lore.kernel.org/linux-kernel/[e-mail]/
> >
> > Changes since v2:
> >
> > Patches 1 and 2 were added from a suggestion by Namhyung Kim to refactor
> > this code to implement this feature in a cleaner way. Patch 2 is separated
> > for the benefit of the ARM arch maintainers.
> >
> > Patch 3 conceptually supercedes v2's patches 1 and 2, now with a cleaner
> > implementation thanks to the earlier refactoring.
> >
> > Patch 4 is v2's patch 3, and addresses review comments about C++ style
> > comments, getting a TRAP_PERF definition into the test, and unnecessary
> > NULL checks.
> >
> > [0] https://rr-project.org/
> > [1] Various optimizations exist to skip as much as execution as possible
> > before setting a breakpoint, and to determine a set of program state that
> > is practical to check and verify.
>
> Since everyone seems to be satisfied with this now, can we get it into
> bpf-next (or wherever) for 6.9?

The changes look fine, but since they change perf side we need
perf maintainer's ack-s before we can land the patches.
And none of them were cc-ed.
So please resend the whole set and cc
PERFORMANCE EVENTS SUBSYSTEM
M:      Peter Zijlstra <[e-mail]>
M:      Ingo Molnar <[e-mail]>
M:      Arnaldo Carvalho de Melo <[e-mail]>
M:      Namhyung Kim <[e-mail]>

Kyle Huey Feb. 13, 2024, 3:57 a.m. UTC | #3

On Mon, Feb 12, 2024 at 6:42 PM Alexei Starovoitov
<[e-mail]> wrote:
>
> On Mon, Feb 12, 2024 at 8:37 AM Kyle Huey <[e-mail]> wrote:
> >
> > On Sun, Jan 21, 2024 at 10:25 PM Kyle Huey <[e-mail]> wrote:
> > >
> > > rr, a userspace record and replay debugger[0], replays asynchronous events
> > > such as signals and context switches by essentially[1] setting a breakpoint
> > > at the address where the asynchronous event was delivered during recording
> > > with a condition that the program state matches the state when the event
> > > was delivered.
> > >
> > > Currently, rr uses software breakpoints that trap (via ptrace) to the
> > > supervisor, and evaluates the condition from the supervisor. If the
> > > asynchronous event is delivered in a tight loop (thus requiring the
> > > breakpoint condition to be repeatedly evaluated) the overhead can be
> > > immense. A patch to rr that uses hardware breakpoints via perf events with
> > > an attached BPF program to reject breakpoint hits where the condition is
> > > not satisfied reduces rr's replay overhead by 94% on a pathological (but a
> > > real customer-provided, not contrived) rr trace.
> > >
> > > The only obstacle to this approach is that while the kernel allows a BPF
> > > program to suppress sample output when a perf event overflows it does not
> > > suppress signalling the perf event fd or sending the perf event's SIGTRAP.
> > > This patch set redesigns __perf_overflow_handler() and
> > > bpf_overflow_handler() so that the former invokes the latter directly when
> > > appropriate rather than through the generic overflow handler machinery,
> > > passes the return code of the BPF program back to __perf_overflow_handler()
> > > to allow it to decide whether to execute the regular overflow handler,
> > > reorders bpf_overflow_handler() and the side effects of perf event
> > > overflow, changes __perf_overflow_handler() to suppress those side effects
> > > if the BPF program returns zero, and adds a selftest.
> > >
> > > The previous version of this patchset can be found at
> > > https://lore.kernel.org/linux-kernel/[e-mail]/
> > >
> > > Changes since v4:
> > >
> > > Patches 1, 2, 3, 4 added various Acked-by.
> > >
> > > Patch 4 addresses additional nits from Song.
> > >
> > > v3 of this patchset can be found at
> > > https://lore.kernel.org/linux-kernel/[e-mail]/
> > >
> > > Changes since v3:
> > >
> > > Patches 1, 2, 3 added various Acked-by.
> > >
> > > Patch 4 addresses Song's review comments by dropping signals_expected and the
> > > corresponding ASSERT_OKs, handling errors from signal(), and fixing multiline
> > > comment formatting.
> > >
> > > v2 of this patchset can be found at
> > > https://lore.kernel.org/linux-kernel/[e-mail]/
> > >
> > > Changes since v2:
> > >
> > > Patches 1 and 2 were added from a suggestion by Namhyung Kim to refactor
> > > this code to implement this feature in a cleaner way. Patch 2 is separated
> > > for the benefit of the ARM arch maintainers.
> > >
> > > Patch 3 conceptually supercedes v2's patches 1 and 2, now with a cleaner
> > > implementation thanks to the earlier refactoring.
> > >
> > > Patch 4 is v2's patch 3, and addresses review comments about C++ style
> > > comments, getting a TRAP_PERF definition into the test, and unnecessary
> > > NULL checks.
> > >
> > > [0] https://rr-project.org/
> > > [1] Various optimizations exist to skip as much as execution as possible
> > > before setting a breakpoint, and to determine a set of program state that
> > > is practical to check and verify.
> >
> > Since everyone seems to be satisfied with this now, can we get it into
> > bpf-next (or wherever) for 6.9?
>
> The changes look fine, but since they change perf side we need
> perf maintainer's ack-s before we can land the patches.
> And none of them were cc-ed.
> So please resend the whole set and cc
> PERFORMANCE EVENTS SUBSYSTEM
> M:      Peter Zijlstra <[e-mail]>
> M:      Ingo Molnar <[e-mail]>
> M:      Arnaldo Carvalho de Melo <[e-mail]>
> M:      Namhyung Kim <[e-mail]>

They're all CCd to the three non-test patches in this set, Namhyung
Kim is CCd to all of them and this cover email, and he both suggested
the first patch and acked the third.

- Kyle

Namhyung Kim Feb. 13, 2024, 5:35 p.m. UTC | #4

Hello,

On Mon, Feb 12, 2024 at 7:57 PM Kyle Huey <[e-mail]> wrote:
>
> On Mon, Feb 12, 2024 at 6:42 PM Alexei Starovoitov
> <[e-mail]> wrote:
> >
> > On Mon, Feb 12, 2024 at 8:37 AM Kyle Huey <[e-mail]> wrote:
> > >
> > > On Sun, Jan 21, 2024 at 10:25 PM Kyle Huey <[e-mail]> wrote:
> > > >
> > > > rr, a userspace record and replay debugger[0], replays asynchronous events
> > > > such as signals and context switches by essentially[1] setting a breakpoint
> > > > at the address where the asynchronous event was delivered during recording
> > > > with a condition that the program state matches the state when the event
> > > > was delivered.
> > > >
> > > > Currently, rr uses software breakpoints that trap (via ptrace) to the
> > > > supervisor, and evaluates the condition from the supervisor. If the
> > > > asynchronous event is delivered in a tight loop (thus requiring the
> > > > breakpoint condition to be repeatedly evaluated) the overhead can be
> > > > immense. A patch to rr that uses hardware breakpoints via perf events with
> > > > an attached BPF program to reject breakpoint hits where the condition is
> > > > not satisfied reduces rr's replay overhead by 94% on a pathological (but a
> > > > real customer-provided, not contrived) rr trace.
> > > >
> > > > The only obstacle to this approach is that while the kernel allows a BPF
> > > > program to suppress sample output when a perf event overflows it does not
> > > > suppress signalling the perf event fd or sending the perf event's SIGTRAP.
> > > > This patch set redesigns __perf_overflow_handler() and
> > > > bpf_overflow_handler() so that the former invokes the latter directly when
> > > > appropriate rather than through the generic overflow handler machinery,
> > > > passes the return code of the BPF program back to __perf_overflow_handler()
> > > > to allow it to decide whether to execute the regular overflow handler,
> > > > reorders bpf_overflow_handler() and the side effects of perf event
> > > > overflow, changes __perf_overflow_handler() to suppress those side effects
> > > > if the BPF program returns zero, and adds a selftest.
> > > >
> > > > The previous version of this patchset can be found at
> > > > https://lore.kernel.org/linux-kernel/[e-mail]/
> > > >
> > > > Changes since v4:
> > > >
> > > > Patches 1, 2, 3, 4 added various Acked-by.
> > > >
> > > > Patch 4 addresses additional nits from Song.
> > > >
> > > > v3 of this patchset can be found at
> > > > https://lore.kernel.org/linux-kernel/[e-mail]/
> > > >
> > > > Changes since v3:
> > > >
> > > > Patches 1, 2, 3 added various Acked-by.
> > > >
> > > > Patch 4 addresses Song's review comments by dropping signals_expected and the
> > > > corresponding ASSERT_OKs, handling errors from signal(), and fixing multiline
> > > > comment formatting.
> > > >
> > > > v2 of this patchset can be found at
> > > > https://lore.kernel.org/linux-kernel/[e-mail]/
> > > >
> > > > Changes since v2:
> > > >
> > > > Patches 1 and 2 were added from a suggestion by Namhyung Kim to refactor
> > > > this code to implement this feature in a cleaner way. Patch 2 is separated
> > > > for the benefit of the ARM arch maintainers.
> > > >
> > > > Patch 3 conceptually supercedes v2's patches 1 and 2, now with a cleaner
> > > > implementation thanks to the earlier refactoring.
> > > >
> > > > Patch 4 is v2's patch 3, and addresses review comments about C++ style
> > > > comments, getting a TRAP_PERF definition into the test, and unnecessary
> > > > NULL checks.
> > > >
> > > > [0] https://rr-project.org/
> > > > [1] Various optimizations exist to skip as much as execution as possible
> > > > before setting a breakpoint, and to determine a set of program state that
> > > > is practical to check and verify.
> > >
> > > Since everyone seems to be satisfied with this now, can we get it into
> > > bpf-next (or wherever) for 6.9?
> >
> > The changes look fine, but since they change perf side we need
> > perf maintainer's ack-s before we can land the patches.
> > And none of them were cc-ed.
> > So please resend the whole set and cc
> > PERFORMANCE EVENTS SUBSYSTEM
> > M:      Peter Zijlstra <[e-mail]>
> > M:      Ingo Molnar <[e-mail]>
> > M:      Arnaldo Carvalho de Melo <[e-mail]>
> > M:      Namhyung Kim <[e-mail]>
>
> They're all CCd to the three non-test patches in this set, Namhyung
> Kim is CCd to all of them and this cover email, and he both suggested
> the first patch and acked the third.

I think we need to wait for Peter or Ingo for the kernel part.

Thanks,
Namhyung