[v4,bpf-next,1/9] bpf: introduce bpf_spin_lock

Introduce 'struct bpf_spin_lock' and bpf_spin_lock/unlock() helpers to let
bpf program serialize access to other variables.

Example:
struct hash_elem {
    int cnt;
    struct bpf_spin_lock lock;
};
struct hash_elem * val = bpf_map_lookup_elem(&hash_map, &key);
if (val) {
    bpf_spin_lock(&val->lock);
    val->cnt++;
    bpf_spin_unlock(&val->lock);
}

Restrictions and safety checks:
- bpf_spin_lock is only allowed inside HASH and ARRAY maps.
- BTF description of the map is mandatory for safety analysis.
- bpf program can take one bpf_spin_lock at a time, since two or more can
  cause dead locks.
- only one 'struct bpf_spin_lock' is allowed per map element.
  It drastically simplifies implementation yet allows bpf program to use
  any number of bpf_spin_locks.
- when bpf_spin_lock is taken the calls (either bpf2bpf or helpers) are not allowed.
- bpf program must bpf_spin_unlock() before return.
- bpf program can access 'struct bpf_spin_lock' only via
  bpf_spin_lock()/bpf_spin_unlock() helpers.
- load/store into 'struct bpf_spin_lock lock;' field is not allowed.
- to use bpf_spin_lock() helper the BTF description of map value must be
  a struct and have 'struct bpf_spin_lock anyname;' field at the top level.
  Nested lock inside another struct is not allowed.
- syscall map_lookup doesn't copy bpf_spin_lock field to user space.
- syscall map_update and program map_update do not update bpf_spin_lock field.
- bpf_spin_lock cannot be on the stack or inside networking packet.
  bpf_spin_lock can only be inside HASH or ARRAY map value.
- bpf_spin_lock is available to root only and to all program types.
- bpf_spin_lock is not allowed in inner maps of map-in-map.
- ld_abs is not allowed inside spin_lock-ed region.

Implementation details:
- on !SMP bpf_spin_lock() becomes nop
- on architectures that don't support queued_spin_lock trivial lock is used.
  Note that arch_spin_lock cannot be used, since not all archs agree that
  zero == unlocked and sizeof(arch_spinlock_t) != sizeof(__u32).
- presence of bpf_spin_lock inside map value could have been indicated via
  extra flag during map_create, but specifying it via BTF is cleaner.
  It provides introspection for map key/value and reduces user coding mistakes.

Next steps:
- allow bpf_spin_lock in other map types (like cgroup local storage)
- introduce BPF_F_LOCK flag for bpf_map_update() syscall and helper
  to request kernel to grab bpf_spin_lock before rewriting the value.
  That will serialize access to map elements.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf.h          |  37 ++++++++-
 include/linux/bpf_verifier.h |   1 +
 include/linux/btf.h          |   1 +
 include/uapi/linux/bpf.h     |   7 +-
 kernel/bpf/arraymap.c        |   7 +-
 kernel/bpf/btf.c             |  42 ++++++++++
 kernel/bpf/core.c            |   2 +
 kernel/bpf/hashtab.c         |   6 +-
 kernel/bpf/helpers.c         |  57 ++++++++++++++
 kernel/bpf/map_in_map.c      |   5 ++
 kernel/bpf/syscall.c         |  21 ++++-
 kernel/bpf/verifier.c        | 149 ++++++++++++++++++++++++++++++++++-
 net/core/filter.c            |  16 +++-
 13 files changed, 335 insertions(+), 16 deletions(-)

Message ID	20190124041403.2100609-2-ast@kernel.org
State	Changes Requested
Delegated to:	BPF Maintainers
Headers	show Return-Path: <netdev-owner@vger.kernel.org> Smtp-Origin-Hostprefix: devbig From: Alexei Starovoitov <ast@kernel.org> Smtp-Origin-Hostname: devbig007.ftw2.facebook.com To: <davem@davemloft.net> CC: <daniel@iogearbox.net>, <jakub.kicinski@netronome.com>, <netdev@vger.kernel.org>, <kernel-team@fb.com> Smtp-Origin-Cluster: ftw2c04 Subject: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock Date: Wed, 23 Jan 2019 20:13:55 -0800 Message-ID: <20190124041403.2100609-2-ast@kernel.org> In-Reply-To: <20190124041403.2100609-1-ast@kernel.org> References: <20190124041403.2100609-1-ast@kernel.org> MIME-Version: 1.0 Content-Type: text/plain Sender: netdev-owner@vger.kernel.org Precedence: bulk
Series	introduce bpf_spin_lock \| expand [v4,bpf-next,0/9] introduce bpf_spin_lock [v4,bpf-next,1/9] bpf: introduce bpf_spin_lock [v4,bpf-next,2/9] bpf: add support for bpf_spin_lock to cgroup local storage [v4,bpf-next,3/9] tools/bpf: sync include/uapi/linux/bpf.h [v4,bpf-next,4/9] selftests/bpf: add bpf_spin_lock tests [v4,bpf-next,5/9] selftests/bpf: add bpf_spin_lock C test [v4,bpf-next,6/9] bpf: introduce BPF_F_LOCK flag [v4,bpf-next,7/9] tools/bpf: sync uapi/bpf.h

[v4,bpf-next,1/9] bpf: introduce bpf_spin_lock

Commit Message

Comments

Patch