[bpf-next,v6,01/16] bpf: implement lookup-free direct value access for maps

This generic extension to BPF maps allows for directly loading
an address residing inside a BPF map value as a single BPF
ldimm64 instruction!

The idea is similar to what BPF_PSEUDO_MAP_FD does today, which
is a special src_reg flag for ldimm64 instruction that indicates
that inside the first part of the double insns's imm field is a
file descriptor which the verifier then replaces as a full 64bit
address of the map into both imm parts. For the newly added
BPF_PSEUDO_MAP_VALUE src_reg flag, the idea is the following:
the first part of the double insns's imm field is again a file
descriptor corresponding to the map, and the second part of the
imm field is an offset into the value. The verifier will then
replace both imm parts with an address that points into the BPF
map value at the given value offset for maps that support this
operation. Currently supported is array map with single entry.
It is possible to support more than just single map element by
reusing both 16bit off fields of the insns as a map index, so
full array map lookup could be expressed that way. It hasn't
been implemented here due to lack of concrete use case, but
could easily be done so in future in a compatible way, since
both off fields right now have to be 0 and would correctly
denote a map index 0.

The BPF_PSEUDO_MAP_VALUE is a distinct flag as otherwise with
BPF_PSEUDO_MAP_FD we could not differ offset 0 between load of
map pointer versus load of map's value at offset 0, and changing
BPF_PSEUDO_MAP_FD's encoding into off by one to differ between
regular map pointer and map value pointer would add unnecessary
complexity and increases barrier for debugability thus less
suitable. Using the second part of the imm field as an offset
into the value does /not/ come with limitations since maximum
possible value size is in u32 universe anyway.

This optimization allows for efficiently retrieving an address
to a map value memory area without having to issue a helper call
which needs to prepare registers according to calling convention,
etc, without needing the extra NULL test, and without having to
add the offset in an additional instruction to the value base
pointer. The verifier then treats the destination register as
PTR_TO_MAP_VALUE with constant reg->off from the user passed
offset from the second imm field, and guarantees that this is
within bounds of the map value. Any subsequent operations are
normally treated as typical map value handling without anything
extra needed from verification side.

The two map operations for direct value access have been added to
array map for now. In future other types could be supported as
well depending on the use case. The main use case for this commit
is to allow for BPF loader support for global variables that
reside in .data/.rodata/.bss sections such that we can directly
load the address of them with minimal additional infrastructure
required. Loader support has been added in subsequent commits for
libbpf library.

Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
---
 include/linux/bpf.h               |  6 +++
 include/linux/bpf_verifier.h      |  4 ++
 include/uapi/linux/bpf.h          | 13 ++++-
 kernel/bpf/arraymap.c             | 32 ++++++++++++
 kernel/bpf/core.c                 |  3 +-
 kernel/bpf/disasm.c               |  5 +-
 kernel/bpf/syscall.c              | 28 +++++++---
 kernel/bpf/verifier.c             | 86 ++++++++++++++++++++++++-------
 tools/bpf/bpftool/xlated_dumper.c |  3 ++
 9 files changed, 149 insertions(+), 31 deletions(-)

Message ID	20190409212018.32423-2-daniel@iogearbox.net
State	Accepted
Delegated to:	BPF Maintainers
Headers	show Return-Path: <netdev-owner@vger.kernel.org> From: Daniel Borkmann <daniel@iogearbox.net> To: bpf@vger.kernel.org Cc: netdev@vger.kernel.org, ast@kernel.org, joe@wand.net.nz, yhs@fb.com, andrii.nakryiko@gmail.com, kafai@fb.com, jannh@google.com, Daniel Borkmann <daniel@iogearbox.net> Subject: [PATCH bpf-next v6 01/16] bpf: implement lookup-free direct value access for maps Date: Tue, 9 Apr 2019 23:20:03 +0200 Message-Id: <20190409212018.32423-2-daniel@iogearbox.net> In-Reply-To: <20190409212018.32423-1-daniel@iogearbox.net> References: <20190409212018.32423-1-daniel@iogearbox.net> Sender: netdev-owner@vger.kernel.org Precedence: bulk
Series	BPF support for global data \| expand [bpf-next,v6,00/16] BPF support for global data [bpf-next,v6,01/16] bpf: implement lookup-free direct value access for maps [bpf-next,v6,02/16] bpf: do not retain flags that are not tied to map lifetime [bpf-next,v6,03/16] bpf: add program side {rd, wr}only support for maps [bpf-next,v6,04/16] bpf: add syscall side map freeze support [bpf-next,v6,05/16] bpf: allow . char as part of the object name [bpf-next,v6,06/16] bpf: add specification for BTF Var and DataSec kinds [bpf-next,v6,07/16] bpf: kernel side support for BTF Var and DataSec [bpf-next,v6,08/16] bpf: allow for key-less BTF in array map [bpf-next,v6,09/16] bpf: sync {btf, bpf}.h uapi header from tools infrastructure [bpf-next,v6,10/16] bpf, libbpf: refactor relocation handling [bpf-next,v6,11/16] bpf, libbpf: support global data/bss/rodata sections [bpf-next,v6,12/16] bpf, libbpf: add support for BTF Var and DataSec [bpf-next,v6,13/16] bpf: bpftool support for dumping data/bss/rodata sections [bpf-next,v6,14/16] bpf, selftest: test {rd, wr}only flags and direct value access [bpf-next,v6,15/16] bpf, selftest: test global data/bss/rodata sections [bpf-next,v6,16/16] bpf, selftest: add test cases for BTF Var and DataSec

[bpf-next,v6,01/16] bpf: implement lookup-free direct value access for maps

Commit Message

Patch