bpf.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Joe Burton <jevburton.kernel@gmail.com>
To: Alexei Starovoitov <ast@kernel.org>,
	Daniel Borkmann <daniel@iogearbox.net>,
	Andrii Nakryiko <andrii@kernel.org>,
	Martin KaFai Lau <kafai@fb.com>
Cc: Song Liu <songliubraving@fb.com>, Yonghong Song <yhs@fb.com>,
	John Fastabend <john.fastabend@gmail.com>,
	KP Singh <kpsingh@kernel.org>, Petar Penkov <ppenkov@google.com>,
	Stanislav Fomichev <sdf@google.com>, Hao Luo <haoluo@google.com>,
	netdev@vger.kernel.org, bpf@vger.kernel.org,
	Joe Burton <jevburton@google.com>
Subject: [RFC PATCH v2 00/13] Introduce BPF map tracing capability
Date: Wed, 29 Sep 2021 23:58:57 +0000	[thread overview]
Message-ID: <20210929235910.1765396-1-jevburton.kernel@gmail.com> (raw)

From: Joe Burton <jevburton@google.com>

This patch introduces 'map tracing': the capability to execute a
tracing program after updating a map.

Map tracing enables upgrades of stateful programs with fewer race
conditions than otherwise possible. We use a tracing program to
imbue a map with copy-on-write semantics, then use an iterator to
perform a bulk copy of data in the map. After bulk copying concludes,
updates to that map automatically propagate via the tracing
program, avoiding a class of race conditions. This use case is
demonstrated in the new 'real_world_example' selftest.

Extend BPF_PROG_TYPE_TRACING with a new attach type, BPF_TRACE_MAP,
and allow linking these programs to arbitrary maps.

Extend the verifier to invoke helper calls directly after
bpf_map_update_elem() and bpf_map_delete_elem(). The helpers have the
exact same signature as the functions they trace, and simply pass those
arguments to the list of tracing programs attached to the map.

struct bpf_map gets a single additional pointer, which points to a
structure containing lists of tracing programs. This pointer is
populated when the first tracing program is attached to a map, to
minimize memory overhead for the majority of maps which are not
traced. I use an atomic cmpxchg() to avoid the need for a mutex
when accessing the pointer. Once populated, the pointer is never
freed until the map itself is freed.

One open question is how to handle pointer-based map updates. For
example:
  int *x = bpf_map_lookup_elem(...);
  if (...) *x++;
  if (...) *x--;
We can't just call a helper function right after the
bpf_map_lookup_elem(), since the updates occur later on. We also can't
determine where the last modification to the pointer occurs, due to
branch instructions. I would therefore consider a pattern where we
'flush' pointers at the end of a BPF program:
  int *x = bpf_map_lookup_elem(...);
  ...
  /* Execute tracing programs for this cell in this map. */
  bpf_map_trace_pointer_update(x);
  return 0;
We can't necessarily do this in the verifier, since 'x' may no
longer be in a register or on the stack. Thus we might introduce a
helper to save pointers that should be flushed, then flush all
registered pointers at every exit point:
  int *x = bpf_map_lookup_elem(...);
  /*
   * Saves 'x' somewhere in kernel memory. Does nothing if no
   * corresponding tracing progs are attached to the map.
   */
  bpf_map_trace_register_pointer(x);
  ...
  /* flush all registered pointers */
  bpf_map_trace_pointer_update();
  return 0;
This should be easy to implement in the verifier.

In addition, we use the verifier to instrument certain map update
calls. This requires saving arguments onto the stack, which means that
a program using MAX_BPF_STACK bytes of stack could exceed the limit.
I don't know whether this actually causes any problems.

Linux Plumbers Conference slides on this topic:
https://linuxplumbersconf.org/event/11/contributions/942/attachments/
814/1533/joe_burton_lpc_2021_slides.pdf

Joe Burton (13):
  bpf: Add machinery to register map tracing hooks
  bpf: Allow loading BPF_TRACE_MAP programs
  bpf: Add list of tracing programs to struct bpf_map
  bpf: Define a few bpf_link_ops for BPF_TRACE_MAP
  bpf: Enable creation of BPF_LINK_TYPE_MAP_TRACE
  bpf: Add APIs to invoke tracing programs
  bpf: Register BPF_MAP_TRACE_{UPDATE,DELETE}_ELEM hooks
  libbpf: Support BPF_TRACE_MAP
  bpf: Add infinite loop check on map tracers
  Add bpf_map_trace_{update,delete}_elem() helper functions
  bpf: verifier inserts map tracing helper call
  bpf: Add selftests for map tracing
  bpf: Add real world example for map tracing

 include/linux/bpf.h                           |  48 ++-
 include/linux/bpf_types.h                     |   1 +
 include/uapi/linux/bpf.h                      |  22 +
 kernel/bpf/Makefile                           |   1 +
 kernel/bpf/helpers.c                          |  29 ++
 kernel/bpf/map_trace.c                        | 406 ++++++++++++++++++
 kernel/bpf/syscall.c                          |   7 +
 kernel/bpf/verifier.c                         |  81 +++-
 tools/include/uapi/linux/bpf.h                |  22 +
 tools/lib/bpf/bpf.c                           |  13 +-
 tools/lib/bpf/bpf.h                           |   4 +-
 tools/lib/bpf/libbpf.c                        | 118 +++++
 tools/lib/bpf/libbpf.h                        |  11 +
 tools/lib/bpf/libbpf.map                      |   1 +
 .../selftests/bpf/prog_tests/bpf_map_trace.c  | 401 +++++++++++++++++
 .../bpf/progs/bpf_map_trace_delete_elem.c     |  49 +++
 .../selftests/bpf/progs/bpf_map_trace_loop0.c |  26 ++
 .../selftests/bpf/progs/bpf_map_trace_loop1.c |  43 ++
 .../progs/bpf_map_trace_real_world_common.h   | 125 ++++++
 .../bpf_map_trace_real_world_migration.c      |  96 +++++
 .../bpf/progs/bpf_map_trace_real_world_new.c  |   4 +
 .../bpf/progs/bpf_map_trace_real_world_old.c  |   5 +
 .../bpf/progs/bpf_map_trace_update_elem.c     |  51 +++
 .../selftests/bpf/verifier/map_trace.c        |  40 ++
 24 files changed, 1592 insertions(+), 12 deletions(-)
 create mode 100644 kernel/bpf/map_trace.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_map_trace.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_delete_elem.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_loop0.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_loop1.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_real_world_common.h
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_real_world_migration.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_real_world_new.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_real_world_old.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_map_trace_update_elem.c
 create mode 100644 tools/testing/selftests/bpf/verifier/map_trace.c

-- 
2.33.0.685.g46640cef36-goog


             reply	other threads:[~2021-09-29 23:59 UTC|newest]

Thread overview: 21+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-09-29 23:58 Joe Burton [this message]
2021-09-29 23:58 ` [RFC PATCH v2 01/13] bpf: Add machinery to register map tracing hooks Joe Burton
2021-09-29 23:58 ` [RFC PATCH v2 02/13] bpf: Allow loading BPF_TRACE_MAP programs Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 03/13] bpf: Add list of tracing programs to struct bpf_map Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 04/13] bpf: Define a few bpf_link_ops for BPF_TRACE_MAP Joe Burton
2021-09-30  0:26   ` Eric Dumazet
2021-09-30  1:09     ` Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 05/13] bpf: Enable creation of BPF_LINK_TYPE_MAP_TRACE Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 06/13] bpf: Add APIs to invoke tracing programs Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 07/13] bpf: Register BPF_MAP_TRACE_{UPDATE,DELETE}_ELEM hooks Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 08/13] libbpf: Support BPF_TRACE_MAP Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 09/13] bpf: Add infinite loop check on map tracers Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 10/13] Add bpf_map_trace_{update,delete}_elem() helper functions Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 11/13] bpf: verifier inserts map tracing helper call Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 12/13] bpf: Add selftests for map tracing Joe Burton
2021-09-29 23:59 ` [RFC PATCH v2 13/13] bpf: Add real world example " Joe Burton
2021-10-05  5:13 ` [RFC PATCH v2 00/13] Introduce BPF map tracing capability Alexei Starovoitov
2021-10-05 21:47   ` Joe Burton
2021-10-06 16:41     ` Alexei Starovoitov
2021-10-06 21:05       ` Joe Burton
2021-10-18 23:15         ` Alexei Starovoitov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20210929235910.1765396-1-jevburton.kernel@gmail.com \
    --to=jevburton.kernel@gmail.com \
    --cc=andrii@kernel.org \
    --cc=ast@kernel.org \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=haoluo@google.com \
    --cc=jevburton@google.com \
    --cc=john.fastabend@gmail.com \
    --cc=kafai@fb.com \
    --cc=kpsingh@kernel.org \
    --cc=netdev@vger.kernel.org \
    --cc=ppenkov@google.com \
    --cc=sdf@google.com \
    --cc=songliubraving@fb.com \
    --cc=yhs@fb.com \
    --subject='Re: [RFC PATCH v2 00/13] Introduce BPF map tracing capability' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).