[PATCH bpf-next v1 00/29] Exceptions - Resource Cleanup - Redux

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

Currently bpf_throw() can only be called while the program holds no
resources. A throw unwinds to the exception callback of the main program
and discards every frame in between. Any reference, lock, saved IRQ flags,
or RCU or preemption disabled section held by those frames would leak, so
the verifier rejects the throw. This makes assertions unusable in most
places where a program wants one: in a loop over an iterator, under a
lock, or in an RCU section.

This series allows the main program and its subprogs, static and global,
to throw while holding resources. The unwinder releases the resources of
every frame it discards.

To release a resource the unwinder needs its handle: a pointer to an
object, a ringbuf record or a lock, or the address of an iterator or of
saved IRQ flags on the stack. The verifier tells the unwinder where to
find each handle, in one of two ways.

 1. In the location where the program already keeps it. A frame can only
    be unwound at a call it has not returned from: bpf_throw(), or a call
    to a subprog that may throw. Such a call is a site. On every visit to
    a site the verifier records where the frame keeps each handle: the
    stack slot of an iterator or of saved IRQ flags, the stack slot or
    register that holds a pointer to a referenced object, and the address
    of a lock or a pointer to the object that contains it. It also records
    how many RCU and preemption disabled sections the frame is in. When
    every visit finds a resource held, with its handle in the same
    location, that location goes into a descriptor for the site. The
    program pays nothing for this at runtime.

 2. In a hidden stack slot. When the visits to a site do not agree, the
    verifier reserves a hidden stack slot in the frame for the instruction
    that acquires the resource. Instructions inserted around the acquiring
    call store the handle in the slot, and instructions inserted before
    the releasing call clear it. Sections are counted the same way, in one
    hidden slot per kind.

A resource that is never held at a site needs neither. That is the case
for every resource that is released before the next call that may throw.

A callee may release a resource that its caller holds. If it is a
reference passed in an argument register, the call transfers it: the
callee owns the reference from its entry and tracks it in either of the
two ways above. Any other resource, such as a lock, stays with the caller.
The caller's sites then describe it, or the caller clears its hidden slot
before the call. A callx is handled the same way, for every subprog it
may call.

At runtime the unwinder walks the frames once per phase: locks and IRQ
flags first, then objects whose destructor needs RCU protection, then RCU
and preemption sections, then all remaining objects. This way no
destructor runs under a lock or with IRQs disabled, a destructor that may
sleep runs after every section has been left, and an RCU protected
iterator is destroyed before its RCU section ends. For each frame the
unwinder releases the resources in the frame's hidden slots and those
listed in the descriptor of the frame's site. It finds the site from the
frame's return address, in a table that the JIT fills.

To read handles from registers, bpf_throw() gets a native entry point
that captures the registers of the throw site before any C code runs.
R6-R9 are callee-saved, so the unwinder recovers them for each outer
frame from the locations where the inner frames saved them in their
prologues, which the JIT records. R0-R5 are known only for the frame that
calls bpf_throw(). That is still useful: bpf_throw() does not return, so
a compiler leaves a reference in whichever register it was in.

The unwinder restores the callee-saved registers of the program's caller
from the same saved locations. The main program of a program that throws
therefore no longer saves all of them in its prologue for the exception
callback to restore, and uses a normal prologue.

Programs that cannot throw are not affected.

Limits on program patterns:

 - A throw inside a callback stays rejected. This will be lifted in a
   follow up version or set, along with support for normal unwinding.
   Link: https://lore.kernel.org/bpf/cover.1793147364.git.memxor@gmail.com

 - A hidden slot belongs to the frame that acquired the resource. Some
   resources end up held by another frame: a lock that a subprog takes
   and returns with, an iterator or saved IRQ flags that a callee creates
   on its caller's stack, or an RCU or preemption section that a callee
   enters or leaves for its caller. These are accepted when the site
   descriptors describe the resource, or when no throw can happen while
   it is held. They are rejected when a hidden slot would be needed. This
   does not need to be fixed: the usual wrappers load, and only a site
   that is reached both with and without such a resource is rejected.

 - A hidden slot holds one handle. When a frame holds two resources
   acquired by the same instruction, for example in a loop, the program
   is accepted only if no throw can happen while both are held. This can
   be lifted in a follow up for resources that a site can describe.

 - The instructions that maintain a hidden slot are emitted once per
   call. A resource that needs a hidden slot is rejected if its call
   acquires it only on some paths or in different ways on different
   paths, if its handle is not in a register at the acquiring or at a
   releasing call, or if the acquiring call may itself unwind. In
   well-behaved programs using RAII, this pattern is unlikely to appear.
   The last case is expected to go away with support for normal
   unwinding. The others do not need to be fixed.

 - A callee cannot access a hidden slot of its caller. When the caller
   keeps a resource in a hidden slot, the program is rejected if:

    - a callee that was not handed the resource may throw before it
      releases it, or releases it only on some paths;
    - a callee that was handed the resource returns without releasing
      it on some paths;
    - a callx may call one subprog that releases the resource and
      another that does not;
    - a callback releases the resource.

   Likewise, a subprog that keeps a reference it was handed in a hidden
   slot of its own is rejected if another call passes it something else
   in that argument.

   Only the second case is expected in practice: a callee that consumes
   a reference on some paths and leaves it to its caller on others. It
   loads today if the callee returns the pointer instead, and can be
   lifted in a follow up. The others do not need to be fixed.

 - A throw is rejected while the program holds a reference that the
   unwinder cannot release: its type has no cleanup destructor, the
   program is not allowed to call its release kfunc, or the object has
   NMI unsafe fields and the program is a tracing program. The first
   case is fixed by registering a destructor for the type. In the other
   two the program could not release the reference itself either, so
   they do not need to be fixed.

 - A program that throws must not overwrite an iterator or saved IRQ
   flags on its stack, release an object while it holds the lock inside
   that object, or keep an RCU protected iterator beyond its RCU section.
   Such programs are rejected without a throw as well, so this does not
   need to be fixed.

Other limits:

 - A register or stack slot that points to a held resource stays in the
   verifier state after the program has read it for the last time, so
   that a site can describe it. Two states are equivalent only if these
   locations match, which can reduce pruning. Liveness is unchanged. This
   does not need to be fixed: it only matters when two states keep a
   held resource in different locations.

 - Hidden slots count towards the stack depth limit. This does not need
   to be fixed: a slot is eight bytes, and only a resource that no site
   can describe takes one.

 - Only x86-64 and arm64 are supported. Other architectures keep the
   existing behavior, and can be added in follow ups.

Kumar Kartikeya Dwivedi (29):
  bpf: Record where JITs save callee-saved registers
  bpf: Add bpf_throw_unwind() and an arch entry hook
  bpf, x86: Capture registers in a native bpf_throw() entry
  bpf, arm64: Capture registers in a native bpf_throw() entry
  bpf: Restore callee-saved registers from unwound frames
  bpf: Keep last insn's aux data in add_hidden_subprog()
  bpf: Add one allocator for hidden stack slots
  bpf: Add flags and release kfuncs to the dtor registry
  bpf: Register cleanup destructors for more types
  bpf: Record where JITed frames keep the BPF stack
  bpf: Give every reference an owner frame
  bpf: Release resources in hidden slots on bpf_throw()
  bpf: Track held resources in hidden stack slots
  bpf: Describe held resources at throw sites
  bpf: Describe handles in registers at throw sites
  bpf: Describe locks at throw sites
  bpf: Apply hidden slot limits only when a slot is needed
  bpf: Allow a callee to leave resources with its caller
  bpf: Allow a callee to release its caller's resources
  bpf: Transfer a reference to the callee that releases it
  bpf: Support callx when a callee releases resources
  selftests/bpf: Test rejected throws that hold resources
  selftests/bpf: Test resource cleanup on bpf_throw()
  selftests/bpf: Test cleanup of handles on the stack
  selftests/bpf: Test cleanup of handles in registers
  selftests/bpf: Test callees releasing caller resources
  selftests/bpf: Test resources a callee leaves with its caller
  selftests/bpf: Test cleanup of locks described at sites
  selftests/bpf: Test callee releases through callx

 arch/arm64/net/Makefile                       |    1 +
 arch/arm64/net/bpf_jit_comp.c                 |  168 +-
 arch/arm64/net/bpf_throw.S                    |   33 +
 arch/x86/net/Makefile                         |    1 +
 arch/x86/net/bpf_jit_comp.c                   |  158 +-
 arch/x86/net/bpf_throw.S                      |   45 +
 drivers/base/power/wakeup.c                   |   25 +-
 drivers/hid/bpf/hid_bpf_dispatch.c            |   23 +
 drivers/hid/bpf/hid_bpf_dispatch.h            |    1 +
 fs/bpf_fs_kfuncs.c                            |   27 +-
 include/linux/bpf.h                           |  206 +-
 include/linux/bpf_throw.h                     |   71 +
 include/linux/bpf_verifier.h                  |  255 ++
 include/linux/btf.h                           |   23 +-
 include/linux/filter.h                        |    1 +
 include/net/netfilter/nf_conntrack_bpf.h      |    1 +
 include/net/xfrm.h                            |    1 +
 kernel/bpf/Makefile                           |    2 +-
 kernel/bpf/bpf_iter.c                         |    6 +
 kernel/bpf/btf.c                              |  101 +-
 kernel/bpf/cfg.c                              |   23 +-
 kernel/bpf/cgroup_iter.c                      |    6 +
 kernel/bpf/core.c                             |   21 +
 kernel/bpf/cpumask.c                          |    7 +-
 kernel/bpf/crypto.c                           |    7 +-
 kernel/bpf/dmabuf_iter.c                      |    6 +
 kernel/bpf/fixups.c                           |  293 ++-
 kernel/bpf/frame_desc.c                       | 2143 +++++++++++++++++
 kernel/bpf/helpers.c                          |  135 +-
 kernel/bpf/join.c                             |   26 +-
 kernel/bpf/kmem_cache_iter.c                  |    6 +
 kernel/bpf/states.c                           |   43 +-
 kernel/bpf/task_iter.c                        |   18 +
 kernel/bpf/unwind.c                           |  346 +++
 kernel/bpf/verifier.c                         |  378 ++-
 kernel/sched/ext/ext.c                        |   41 +
 mm/bpf_memcontrol.c                           |   28 +-
 net/bpf/test_run.c                            |   14 +-
 net/core/bpf_ksock.c                          |    3 +
 net/core/filter.c                             |    2 +-
 net/netfilter/nf_conntrack_bpf.c              |   38 +
 net/sched/bpf_qdisc.c                         |   10 +-
 net/xfrm/xfrm_state_bpf.c                     |   26 +-
 .../bpf/prog_tests/exceptions_cleanup.c       |  323 +++
 .../selftests/bpf/prog_tests/verifier.c       |    2 +
 .../selftests/bpf/progs/exceptions_cleanup.c  | 1997 +++++++++++++++
 .../selftests/bpf/progs/exceptions_fail.c     |  300 ++-
 .../selftests/bpf/progs/verifier_frame_desc.c | 1121 +++++++++
 .../bpf/progs/verifier_private_stack.c        |   12 +-
 .../selftests/bpf/test_kmods/bpf_testmod.c    |   43 +-
 50 files changed, 8224 insertions(+), 343 deletions(-)
 create mode 100644 arch/arm64/net/bpf_throw.S
 create mode 100644 arch/x86/net/bpf_throw.S
 create mode 100644 include/linux/bpf_throw.h
 create mode 100644 kernel/bpf/frame_desc.c
 create mode 100644 kernel/bpf/unwind.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/exceptions_cleanup.c
 create mode 100644 tools/testing/selftests/bpf/progs/exceptions_cleanup.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_frame_desc.c


base-commit: 0fb18ce8a2e9de830433923cf65838933d615359
-- 
2.53.0