From: Alexei Starovoitov kfunc_iter_stack_liveness matches a line of the verifier log: 6: (85) call bpf_iter_num_new#95497 ; def: fp0-24 .. " 6: (85) call bpf_iter_num_new{{.*}} ; def: fp0-24 .." The pattern has "{{.*}}" for the id and then ten spaces. The verifier pads the insn to a fixed column. An id of six digits leaves nine spaces, and the test fails. resolve_btfids sorts BTF by name. The next patches add about 11000 decl tags to vmlinux. Their names start with "bpf_fmodret_retval:", so all of them come before "bpf_iter_num_new": id of bpf_iter_num_new before this series 95497 after this series 106933 Let "{{.*}}" match the spaces too, as other tests in this file do. Signed-off-by: Alexei Starovoitov Acked-by: Anton Protopopov --- tools/testing/selftests/bpf/progs/verifier_live_stack.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/tools/testing/selftests/bpf/progs/verifier_live_stack.c b/tools/testing/selftests/bpf/progs/verifier_live_stack.c index 2d31868bcfdb..4bc4091b17a5 100644 --- a/tools/testing/selftests/bpf/progs/verifier_live_stack.c +++ b/tools/testing/selftests/bpf/progs/verifier_live_stack.c @@ -979,9 +979,9 @@ void __kfunc_btf_root(void) */ SEC("socket") __success __log_level(2) -__msg(" 6: (85) call bpf_iter_num_new{{.*}} ; def: fp0-24 may_def: fp0-24{{$}}") -__msg(" 9: (85) call bpf_iter_num_next{{.*}} ; use: fp0-24 may_def: fp0-24{{$}}") -__msg("14: (85) call bpf_iter_num_destroy{{.*}} ; use: fp0-24 may_def: fp0-24{{$}}") +__msg(" 6: (85) call bpf_iter_num_new{{.*}}; def: fp0-24 may_def: fp0-24{{$}}") +__msg(" 9: (85) call bpf_iter_num_next{{.*}}; use: fp0-24 may_def: fp0-24{{$}}") +__msg("14: (85) call bpf_iter_num_destroy{{.*}}; use: fp0-24 may_def: fp0-24{{$}}") __naked void kfunc_iter_stack_liveness(void) { asm volatile ( -- 2.55.0 From: Anton Protopopov resolve_btfids is the tool that sees vmlinux and each module after the link, with BTF at hand. A later patch lets it read the machine code of the functions, to find the errors that they return. The two kinds of files differ: vmlinux module ELF file linked image relocatable (ET_REL) address virtual address each section starts at 0 field of a jump final value 0, a relocation has the target A field is the bytes of an instruction that hold the target. In a module these are fields with a relocation: - the jump to __x86_return_thunk, which is the return of the function - the jump to the cold subfunction Add struct image. It gives both kinds of files one address space: vmlinux addr = virtual address module addr = section index << 32 | offset undefined symbol addr = 16 * symbol index (section 0) image_bytes(addr) the bytes at addr, and how many follow image_reloc(addr, len) the target of a field in the len bytes image_symbol(name) the address of a symbol image_func(name) name, section, address and size The user of struct image works in three steps: decode the instruction at addr -> len image_reloc(addr, len) -> the address of the target compare it with image_symbol("__x86_return_thunk") BTF knows a function only by its name. image_func() returns NULL if two functions have the name: nobody can tell which of them the FUNC is. Signed-off-by: Anton Protopopov Co-developed-by: Alexei Starovoitov Signed-off-by: Alexei Starovoitov --- tools/bpf/resolve_btfids/Build | 1 + tools/bpf/resolve_btfids/image.c | 222 +++++++++++++++++++++++++++++++ tools/bpf/resolve_btfids/image.h | 62 +++++++++ 3 files changed, 285 insertions(+) create mode 100644 tools/bpf/resolve_btfids/image.c create mode 100644 tools/bpf/resolve_btfids/image.h diff --git a/tools/bpf/resolve_btfids/Build b/tools/bpf/resolve_btfids/Build index 602e1508bf09..65af9dee7659 100644 --- a/tools/bpf/resolve_btfids/Build +++ b/tools/bpf/resolve_btfids/Build @@ -2,6 +2,7 @@ hostprogs := resolve_btfids resolve_btfids-y += main.o resolve_btfids-y += btf_colors.o +resolve_btfids-y += image.o resolve_btfids-y += rbtree.o resolve_btfids-y += zalloc.o resolve_btfids-y += string.o diff --git a/tools/bpf/resolve_btfids/image.c b/tools/bpf/resolve_btfids/image.c new file mode 100644 index 000000000000..7a97a49e5364 --- /dev/null +++ b/tools/bpf/resolve_btfids/image.c @@ -0,0 +1,222 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* The code of an ELF file, by address. See image.h */ + +#include +#include +#include + +#include "image.h" + +static uint64_t image_address(const struct image *img, size_t shndx, uint64_t value) +{ + return img->relocatable ? (uint64_t)shndx << 32 | value : value; +} + +static uint64_t symbol_address(const struct image *img, size_t idx, const GElf_Sym *sym) +{ + if (sym->st_shndx == SHN_UNDEF) + return img->relocatable ? idx << 4 : 0; + if (sym->st_shndx >= SHN_LORESERVE) + return 0; + return image_address(img, sym->st_shndx, sym->st_value); +} + +uint64_t image_symbol(const struct image *img, const char *name) +{ + size_t i; + + for (i = 1; i < img->nr_symbols; i++) { + const char *s; + GElf_Sym sym; + + if (!gelf_getsym(img->symbols, i, &sym) || !sym.st_name) + continue; + s = elf_strptr(img->elf, img->strndx, sym.st_name); + if (s && !strcmp(s, name)) + return symbol_address(img, i, &sym); + } + return 0; +} + +static int cmp_func(const void *va, const void *vb) +{ + const struct image_func *a = va, *b = vb; + + return strcmp(a->name, b->name); +} + +const struct image_func *image_func(const struct image *img, const char *name) +{ + const struct image_func key = { .name = name }, *end = img->funcs + img->nr_funcs, *f; + + f = bsearch(&key, img->funcs, img->nr_funcs, sizeof(*f), cmp_func); + if (!f || (f > img->funcs && !strcmp(f[-1].name, name)) || + (f + 1 < end && !strcmp(f[1].name, name))) + return NULL; + return f; +} + +const unsigned char *image_bytes(const struct image *img, uint64_t addr, size_t *avail) +{ + const struct image_section *s; + size_t i; + + for (i = img->relocatable ? addr >> 32 : 1; i < img->nr_sections; i++) { + s = &img->sections[i]; + if (addr - s->addr < s->size) { + *avail = s->size - (addr - s->addr); + return s->data + (addr - s->addr); + } + } + return NULL; +} + +const struct image_reloc *image_reloc(const struct image *img, uint64_t addr, size_t len) +{ + size_t lo = 0, hi = img->nr_relocs; + + while (lo < hi) { + size_t mid = lo + (hi - lo) / 2; + + if (img->relocs[mid].addr < addr) + lo = mid + 1; + else + hi = mid; + } + return lo < img->nr_relocs && img->relocs[lo].addr - addr < len ? &img->relocs[lo] : NULL; +} + +static int cmp_reloc(const void *va, const void *vb) +{ + const struct image_reloc *a = va, *b = vb; + + return a->addr > b->addr ? 1 : a->addr < b->addr ? -1 : 0; +} + +static int read_relocs(struct image *img, Elf_Scn *scn, const GElf_Shdr *shdr) +{ + size_t nr = shdr->sh_size / shdr->sh_entsize, i; + Elf_Data *data = elf_getdata(scn, NULL); + struct image_reloc *relocs; + + if (!data) + return -EINVAL; + relocs = realloc(img->relocs, (img->nr_relocs + nr) * sizeof(*relocs)); + if (!relocs) + return -ENOMEM; + img->relocs = relocs; + for (i = 0; i < nr; i++) { + GElf_Rela rela; + GElf_Sym sym; + uint64_t s; + + if (!gelf_getrela(data, i, &rela) || + !gelf_getsym(img->symbols, GELF_R_SYM(rela.r_info), &sym)) + return -EINVAL; + s = symbol_address(img, GELF_R_SYM(rela.r_info), &sym); + if (!s) + continue; + relocs[img->nr_relocs].addr = image_address(img, shdr->sh_info, rela.r_offset); + relocs[img->nr_relocs++].target = s + rela.r_addend; + } + return 0; +} + +static int read_funcs(struct image *img) +{ + size_t i; + + img->funcs = calloc(img->nr_symbols, sizeof(*img->funcs)); + if (!img->funcs) + return -ENOMEM; + for (i = 1; i < img->nr_symbols; i++) { + struct image_func *f = &img->funcs[img->nr_funcs]; + GElf_Sym sym; + + if (!gelf_getsym(img->symbols, i, &sym)) + return -EINVAL; + if (sym.st_shndx == SHN_UNDEF ? !img->relocatable : + GELF_ST_TYPE(sym.st_info) != STT_FUNC || sym.st_shndx >= img->nr_sections) + continue; + f->name = elf_strptr(img->elf, img->strndx, sym.st_name); + if (!f->name) + return -EINVAL; + f->section = img->sections[sym.st_shndx].name ?: ""; + f->addr = symbol_address(img, i, &sym); + f->size = sym.st_size; + img->nr_funcs++; + } + qsort(img->funcs, img->nr_funcs, sizeof(*img->funcs), cmp_func); + return 0; +} + +int image_open(struct image *img, Elf *elf) +{ + size_t i, shstrndx; + GElf_Ehdr ehdr; + GElf_Shdr shdr; + Elf_Scn *scn; + int err; + + memset(img, 0, sizeof(*img)); + if (!gelf_getehdr(elf, &ehdr) || elf_getshdrnum(elf, &img->nr_sections) || + elf_getshdrstrndx(elf, &shstrndx)) + return -EINVAL; + img->elf = elf; + img->relocatable = ehdr.e_type == ET_REL; + img->sections = calloc(img->nr_sections, sizeof(*img->sections)); + if (!img->sections) + return -ENOMEM; + + for (i = 1; i < img->nr_sections; i++) { + struct image_section *s = &img->sections[i]; + Elf_Data *data; + + scn = elf_getscn(elf, i); + if (!scn || !gelf_getshdr(scn, &shdr)) + return -EINVAL; + s->name = elf_strptr(elf, shstrndx, shdr.sh_name); + if (!s->name) + return -EINVAL; + if (shdr.sh_type == SHT_SYMTAB) { + img->symbols = elf_getdata(scn, NULL); + img->nr_symbols = shdr.sh_size / shdr.sh_entsize; + img->strndx = shdr.sh_link; + } + if (!(shdr.sh_flags & SHF_EXECINSTR) || shdr.sh_type != SHT_PROGBITS) + continue; + data = elf_getdata(scn, NULL); + if (!data || data->d_size != shdr.sh_size) + return -EINVAL; + s->data = data->d_buf; + s->addr = image_address(img, i, shdr.sh_addr); + s->size = shdr.sh_size; + } + if (!img->symbols) + return -EINVAL; + err = read_funcs(img); + if (err) + return err; + + for (i = 1; img->relocatable && i < img->nr_sections; i++) { + scn = elf_getscn(elf, i); + if (!gelf_getshdr(scn, &shdr)) + return -EINVAL; + if (shdr.sh_type != SHT_RELA || !img->sections[shdr.sh_info].size) + continue; + err = read_relocs(img, scn, &shdr); + if (err) + return err; + } + if (img->nr_relocs) + qsort(img->relocs, img->nr_relocs, sizeof(*img->relocs), cmp_reloc); + return 0; +} + +void image_close(struct image *img) +{ + free(img->sections); + free(img->relocs); + free(img->funcs); + memset(img, 0, sizeof(*img)); +} diff --git a/tools/bpf/resolve_btfids/image.h b/tools/bpf/resolve_btfids/image.h new file mode 100644 index 000000000000..5ae25f6a362b --- /dev/null +++ b/tools/bpf/resolve_btfids/image.h @@ -0,0 +1,62 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef __RESOLVE_BTFIDS_IMAGE_H +#define __RESOLVE_BTFIDS_IMAGE_H + +#include +#include +#include +#include + +/* + * The code of an ELF file, by address. + * + * In a linked image (vmlinux) an address is the virtual address and all fields + * hold their final values. A relocatable file (a module) has neither: there the + * address of a byte is the index of its section in the upper 32 bits and its + * offset in the lower ones, and what a field refers to is taken from its + * relocation. An undefined symbol lives in section 0, at 16 times its index. + */ +struct image_section { + const char *name; + /* Of a section with code */ + uint64_t addr, size; + const unsigned char *data; +}; + +struct image_reloc { + uint64_t addr; /* of the field */ + uint64_t target; /* symbol + addend */ +}; + +/* A function of the file, or an undefined symbol of a relocatable file: no section, no size */ +struct image_func { + const char *name, *section; + uint64_t addr, size; +}; + +struct image { + Elf *elf; + bool relocatable; + struct image_section *sections; + size_t nr_sections; + struct image_reloc *relocs; /* sorted by address */ + size_t nr_relocs; + struct image_func *funcs; /* sorted by name */ + size_t nr_funcs; + Elf_Data *symbols; + size_t nr_symbols, strndx; +}; + +int image_open(struct image *img, Elf *elf); +void image_close(struct image *img); + +/* Return the address of the symbol NAME, or 0 */ +uint64_t image_symbol(const struct image *img, const char *name); +/* Return the function NAME, or NULL if there is none or more than one */ +const struct image_func *image_func(const struct image *img, const char *name); +/* Return the bytes at ADDR and set AVAIL to how many follow in the section */ +const unsigned char *image_bytes(const struct image *img, uint64_t addr, size_t *avail); +/* Return the relocation of a field in the LEN bytes at ADDR, or NULL */ +const struct image_reloc *image_reloc(const struct image *img, uint64_t addr, size_t len); + +#endif -- 2.55.0 From: Alexei Starovoitov mov $0xffffffea,%eax ... does -22 reach the ret? ret The answer needs three facts about each instruction in between: its length, where it branches, each register that it writes. Implicit writes count too: mul, cmpxchg, ldp, a post-index load. After one missed write the tool says that a function returns an error that it never returns. A decoder written by hand is 300 - 800 lines per arch, for ever. LLVM's MC (machine code) layer knows the three facts for each arch: bytes | MCDisassembler length, MCInst | MCInstrAnalysis branch, call, target | MCInstrDesc explicit and implicit defs | MCRegAliasIterator eax is a part of rax | table of the arch what an opcode computes v struct text_insn kind, dst, src, imm, defs: no arch in it LLVM's C API returns only text. So text_mc.cpp is one C++ file with a C interface, like tools/perf/util/llvm-c-helpers.cpp. MC does not say what an instruction computes. The table of an arch does, by the names of opcodes and registers. The headers with the enums of a target are not installed. x86-64 arm64 patterns 13 11 opcode -> mov of an immediate, mov, sign extension, select return 1 1 RET64, RET test instructions 56 55 bytes -> expected text_insn Where the table says nothing, the tool drops an error. It adds none: - An opcode without a pattern makes an unknown value. - An opcode with hasUnmodeledSideEffects() writes all registers: hvc and vmcall have no defs. So no return value passes ud2 or brk: BUG() has no next instruction. The table says of 16 frequent opcodes that their defs are complete: lock, mrs, ldxr .. - isReturn() holds for iret and eret too. Only the opcode that the table names is a return to the caller. LLVM's API, opcode names and defs change between releases. text_arch_init() looks up all names and decodes all test instructions at each start of the tool. The build stops if one of them differs. llvm-mc.sh is the one place that runs llvm-config. A later patch lets Kconfig take its exit code. It compiles nothing: 3 ms. The Makefile takes flags and libraries from it, only if kbuild passes --fmodret_scan. Signed-off-by: Alexei Starovoitov Acked-by: Anton Protopopov --- tools/bpf/resolve_btfids/Build | 5 + tools/bpf/resolve_btfids/Makefile | 23 +- tools/bpf/resolve_btfids/llvm-mc.sh | 59 ++++ tools/bpf/resolve_btfids/text_insn.h | 71 ++++ tools/bpf/resolve_btfids/text_mc.cpp | 406 +++++++++++++++++++++++ tools/bpf/resolve_btfids/text_mc.h | 105 ++++++ tools/bpf/resolve_btfids/text_mc_arm64.c | 118 +++++++ tools/bpf/resolve_btfids/text_mc_x86.c | 118 +++++++ 8 files changed, 904 insertions(+), 1 deletion(-) create mode 100755 tools/bpf/resolve_btfids/llvm-mc.sh create mode 100644 tools/bpf/resolve_btfids/text_insn.h create mode 100644 tools/bpf/resolve_btfids/text_mc.cpp create mode 100644 tools/bpf/resolve_btfids/text_mc.h create mode 100644 tools/bpf/resolve_btfids/text_mc_arm64.c create mode 100644 tools/bpf/resolve_btfids/text_mc_x86.c diff --git a/tools/bpf/resolve_btfids/Build b/tools/bpf/resolve_btfids/Build index 65af9dee7659..b9e5bf21439f 100644 --- a/tools/bpf/resolve_btfids/Build +++ b/tools/bpf/resolve_btfids/Build @@ -3,12 +3,17 @@ hostprogs := resolve_btfids resolve_btfids-y += main.o resolve_btfids-y += btf_colors.o resolve_btfids-y += image.o +resolve_btfids-$(LLVM_MC) += text_mc.o +resolve_btfids-$(LLVM_MC) += text_mc_$(SRCARCH).o resolve_btfids-y += rbtree.o resolve_btfids-y += zalloc.o resolve_btfids-y += string.o resolve_btfids-y += ctype.o resolve_btfids-y += str_error_r.o +# LLVM's C++ API may have moved on, see Makefile +$(OUTPUT)text_mc.o: cmd_cxx_o_c += $(or_llvm_mc_help) + $(OUTPUT)%.o: ../../lib/%.c FORCE $(call rule_mkdir) $(call if_changed_dep,host_cc_o_c) diff --git a/tools/bpf/resolve_btfids/Makefile b/tools/bpf/resolve_btfids/Makefile index 6f5206ca00d4..38b7caa98776 100644 --- a/tools/bpf/resolve_btfids/Makefile +++ b/tools/bpf/resolve_btfids/Makefile @@ -79,7 +79,28 @@ HOSTCFLAGS_resolve_btfids += -g \ LIBS = $(LIBELF_LIBS) $(ZLIB_LIBS) +# text_mc.cpp reads machine code with LLVM's MC layer. Only --fmodret_scan needs +# it: don't touch LLVM unless kbuild is going to run the tool with that flag. +ifneq ($(filter --fmodret_scan,$(RESOLVE_BTFIDS_FLAGS)),) +LLVM_MC := y +HOSTCXX ?= g++ +LLVM_MC_SH := LLVM_CONFIG="$(LLVM_CONFIG)" HOSTCXX="$(HOSTCXX)" \ + $(SHELL) $(srctree)/tools/bpf/resolve_btfids/llvm-mc.sh $(SRCARCH) +# Kconfig knows from llvm-mc.sh that LLVM is installed. Whether text_mc.cpp can +# be built with it shows here. +LLVM_MC_HELP := CONFIG_BPF_FMODRET_SCAN=y needs a C++17 compiler (HOSTCXX=$(HOSTCXX)) and the \ + headers and libraries of LLVM 17 or later (LLVM_CONFIG=$(LLVM_CONFIG), packages \ + llvm-dev, llvm-devel). See above what is wrong, or switch the option off +or_llvm_mc_help := || { echo '$(LLVM_MC_HELP)' >&2; false; } +HOSTCFLAGS_resolve_btfids += -DHAVE_LLVM_MC +CXX := $(HOSTCXX) +CXXFLAGS := $(filter-out -Werror,$(HOSTCFLAGS_resolve_btfids)) -O2 \ + $(or $(shell $(LLVM_MC_SH) cxxflags),$(error $(LLVM_MC_HELP))) +LIBS += $(or $(shell $(LLVM_MC_SH) libs),$(error $(LLVM_MC_HELP))) +endif + export srctree OUTPUT HOSTCFLAGS_resolve_btfids Q HOSTCC HOSTLD HOSTAR +export CXX CXXFLAGS SRCARCH LLVM_MC or_llvm_mc_help include $(srctree)/tools/build/Makefile.include $(BINARY_IN): fixdep FORCE prepare | $(OUTPUT) @@ -87,7 +108,7 @@ $(BINARY_IN): fixdep FORCE prepare | $(OUTPUT) $(BINARY): $(BPFOBJ) $(SUBCMDOBJ) $(BINARY_IN) $(call msg,LINK,$@) - $(Q)$(HOSTCC) $(BINARY_IN) $(KBUILD_HOSTLDFLAGS) $(EXTRA_LDFLAGS) -o $@ $(BPFOBJ) $(SUBCMDOBJ) $(LIBS) + $(Q)$(HOSTCC) $(BINARY_IN) $(KBUILD_HOSTLDFLAGS) $(EXTRA_LDFLAGS) -o $@ $(BPFOBJ) $(SUBCMDOBJ) $(LIBS) $(or_llvm_mc_help) clean_objects := $(wildcard $(OUTPUT)/*.o \ $(OUTPUT)/.*.o.cmd \ diff --git a/tools/bpf/resolve_btfids/llvm-mc.sh b/tools/bpf/resolve_btfids/llvm-mc.sh new file mode 100755 index 000000000000..bc62c4e43406 --- /dev/null +++ b/tools/bpf/resolve_btfids/llvm-mc.sh @@ -0,0 +1,59 @@ +#!/bin/sh +# SPDX-License-Identifier: GPL-2.0-only +# +# usage: llvm-mc.sh SRCARCH [cxxflags | libs] +# +# text_mc.cpp reads the machine code of the kernel arch SRCARCH with LLVM's MC +# layer. Fail, and say why, if this host lacks what it takes to build it. +# CONFIG_BPF_FMODRET_SCAN depends on that. Each Kconfig run pays for it, so it is +# one run of llvm-config. Whether text_mc.cpp works with this LLVM shows when the +# tool is built, and in text_arch_init() when it starts. +# +# For the Makefile print the flags to compile text_mc.cpp, or the libraries. +# +# The host's LLVM need not be the one which compiles the kernel, if any does. + +die() +{ + echo "$0: $*" >&2 + exit 1 +} + +case "$1" in +x86) target=X86 ;; +arm64) target=AArch64 ;; +*) die "no text_mc_$1.c" ;; +esac +print=$2 + +if [ -z "$LLVM_CONFIG" ]; then + case "$LLVM" in + */) LLVM_CONFIG=${LLVM}llvm-config ;; + -*) LLVM_CONFIG=llvm-config$LLVM ;; + *) LLVM_CONFIG=llvm-config ;; + esac +fi + +command -v ${HOSTCXX:-g++} > /dev/null || die "no C++ compiler ${HOSTCXX:-g++}" +set -- $($LLVM_CONFIG --version --includedir --targets-built 2> /dev/null) +[ $# -gt 2 ] || die "cannot run $LLVM_CONFIG" +[ "${1%%.*}" -ge 17 ] || die "$LLVM_CONFIG is LLVM $1, not 17 or later" +[ -e "$2/llvm/MC/MCInstrDesc.h" ] || die "$2 lacks the headers of LLVM $1" +case " $* " in +*" $target "*) ;; +*) die "$LLVM_CONFIG, LLVM $1, lacks the target $target" ;; +esac + +case "$print" in +cxxflags) + echo "$($LLVM_CONFIG --cxxflags) -DMC_TARGET=$target" + ;; +libs) + # A static link starts faster, which counts for each module, and does not tie the + # tool, which is shipped for the build of external modules, to a shared library + set -- --ldflags --libs --system-libs ${target}Desc ${target}Disassembler ${target}Info + libs=$($LLVM_CONFIG --link-static "$@" 2> /dev/null) || + libs=$($LLVM_CONFIG --link-shared "$@") || die "no libraries of LLVM" + echo $libs -lstdc++ -lm + ;; +esac diff --git a/tools/bpf/resolve_btfids/text_insn.h b/tools/bpf/resolve_btfids/text_insn.h new file mode 100644 index 000000000000..210d749439e7 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_insn.h @@ -0,0 +1,71 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef __TEXT_INSN_H +#define __TEXT_INSN_H + +#include + +/* + * What one machine instruction does to the integer registers and to the + * control flow, in terms which do not depend on the arch. It is what a data + * flow analysis of copies needs, see text_flow.h. + * + * A decoder looks at one instruction and keeps no state. It has to get right + * the length, the kind and the registers which are written. An instruction + * which it does not know is TEXT_OTHER and writes TEXT_ALL_REGS. It may leave + * out a value which dst can get, and never names one which dst cannot get: + * "dst = src or a value which is computed" is a TEXT_SELECT of src and src. + */ +enum text_insn_kind { + TEXT_OTHER, + TEXT_MOV_IMM, /* dst = imm or imm2 */ + TEXT_MOV, /* dst = src */ + TEXT_SEXT32, /* dst = (s32)src */ + TEXT_SELECT, /* dst = src or src2 */ + TEXT_SELECT_IMM, /* dst = src or imm */ + TEXT_BRANCH, /* to imm, 0 if it is computed */ + TEXT_COND_BRANCH, /* to imm or to the next instruction */ + TEXT_CALL, /* of imm, 0 if it is computed */ + TEXT_RETURN, +}; + +/* The arch numbers its registers */ +#define TEXT_MAX_REGS 32 +#define TEXT_ALL_REGS (~0U) +#define TEXT_NO_INSN (~0U) + +struct text_insn { + u8 kind; + u8 len; + u8 dst, src, src2; + bool is32; /* It works on the low 32 bits and zero extends the result */ + /* The registers which it writes, but for dst */ + u32 defs; + u64 imm, imm2; + /* For the user of the decoder */ + u64 addr; + u32 target; /* the index of the instruction at imm */ +}; + +struct text_arch { + u8 retval; /* the register with the return value */ + u32 caller_saved; /* the registers which a call may write */ + /* A branch to this symbol is a return */ + const char *return_thunk; + /* + * Describe the instruction at ADDR, whose bytes are at CODE. At most LEN + * bytes can be read. Return a negative value if it is not an instruction. + */ + int (*decode)(const void *code, unsigned int len, u64 addr, struct text_insn *insn); +}; + +#ifdef HAVE_LLVM_MC +/* Return the arch of the ELF machine MACHINE, or NULL, after a message, if it cannot be decoded */ +const struct text_arch *text_arch_init(unsigned int machine); +#else +static inline const struct text_arch *text_arch_init(unsigned int machine) +{ + return NULL; +} +#endif + +#endif diff --git a/tools/bpf/resolve_btfids/text_mc.cpp b/tools/bpf/resolve_btfids/text_mc.cpp new file mode 100644 index 000000000000..e7166ad4b871 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_mc.cpp @@ -0,0 +1,406 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * The instructions of any arch in the terms of text_insn.h, on top of LLVM's MC + * layer. Nothing in this file depends on the arch: see text_mc.h for the rest. + * + * length, MCInst MCDisassembler::getInstruction() + * branch, call MCInstrAnalysis, which asks MCInstrDesc + * target MCInstrAnalysis::evaluateBranch() + * registers written MCInstrDesc: defs, implicit defs + * eax and rax, w0 and x0 MCRegAliasIterator + * + * Whatever MC does not describe completely writes TEXT_ALL_REGS. + */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +extern "C" { +#include "text_mc.h" +} + +#if LLVM_VERSION_MAJOR < 17 +#error "LLVM 17, the oldest one which can build the kernel, or later" +#endif + +using namespace llvm; + +namespace { + +enum { NO_REG = 0xff, ZERO_REG = 0xfe }; + +/* An LLVM register in the terms of text_insn.h */ +struct Reg { + u32 mask = 0; /* the registers which it overlaps */ + u8 nr = NO_REG; /* the register if it overlaps one, or ZERO_REG */ + u8 bits = 0; /* 64: all of it, 32: the low half, a write zero extends, 0: some part */ +}; + +/* What is known about an opcode before its operands are */ +struct Opcode { + u32 implicit_defs = 0; + unsigned int implicit_def = 0, implicit_use = 0; /* the first ones, LLVM registers */ + bool unmodeled = false, is_return = false; + std::vector patterns; +}; + +struct Decoder { + std::unique_ptr MRI; + std::unique_ptr MAI; + std::unique_ptr MII; + std::unique_ptr STI; + std::unique_ptr Ctx; + std::unique_ptr Dis; + std::unique_ptr MIA; + std::vector regs; + std::vector opcodes; + MCInst inst; +}; + +Decoder d; + +/* MC_TARGET is LLVM's name of the arch, see llvm-mc.sh */ +#define INITIALIZE_(target, what) LLVMInitialize##target##what() +#define INITIALIZE(target, what) INITIALIZE_(target, what) + +raw_ostream &error() +{ + return errs() << "text_mc: LLVM " LLVM_VERSION_STRING ": "; +} + +bool create() +{ + MCTargetOptions options; + std::string message; +#if LLVM_VERSION_MAJOR >= 22 + Triple triple(mc_arch.triple); +#else + const char *triple = mc_arch.triple; +#endif + const Target *target; + + INITIALIZE(MC_TARGET, TargetInfo); + INITIALIZE(MC_TARGET, TargetMC); + INITIALIZE(MC_TARGET, Disassembler); + target = TargetRegistry::lookupTarget(triple, message); + if (!target) { + error() << message << "\n"; + return false; + } + d.MRI.reset(target->createMCRegInfo(triple)); + d.MAI.reset(target->createMCAsmInfo(*d.MRI, triple, options)); + d.MII.reset(target->createMCInstrInfo()); + d.STI.reset(target->createMCSubtargetInfo(triple, "", mc_arch.features)); +#if LLVM_VERSION_MAJOR >= 23 + d.Ctx.reset(new MCContext(triple, *d.MAI, *d.MRI, *d.STI)); +#else + d.Ctx.reset(new MCContext(Triple(mc_arch.triple), d.MAI.get(), d.MRI.get(), d.STI.get())); +#endif + d.Dis.reset(target->createMCDisassembler(*d.STI, *d.Ctx)); + d.MIA.reset(target->createMCInstrAnalysis(d.MII.get())); + return d.Dis && d.MIA; +} + +/* Call FN(LLVM register, index) for each of the NAMES */ +template bool for_each_reg(const char *names, Fn fn) +{ + std::istringstream in(names ?: ""); + std::string name; + bool ok = true; + + for (unsigned int i = 0, r; in >> name; i++) { + for (r = 1; r < d.MRI->getNumRegs() && name != d.MRI->getName(r); r++) + ; + if (r < d.MRI->getNumRegs()) { + fn(r, i); + continue; + } + error() << "no register " << name << "\n"; + ok = false; + } + return ok; +} + +bool read_regs() +{ + bool ok; + + d.regs.resize(d.MRI->getNumRegs()); + ok = for_each_reg(mc_arch.regs, [&](unsigned int r, unsigned int nr) { + for (MCRegAliasIterator alias(r, d.MRI.get(), true); alias.isValid(); ++alias) { + Reg ® = d.regs[*alias]; + + /* The iterator may come to a register more than once */ + reg.mask |= 1U << nr; + reg.nr = reg.mask == 1U << nr ? nr : NO_REG; + reg.bits = *alias == r ? 64 : 0; + } + }); + ok &= for_each_reg(mc_arch.regs32, [&](unsigned int r, unsigned int) { d.regs[r].bits = 32; }); + ok &= for_each_reg(mc_arch.zero_regs, [&](unsigned int r, unsigned int) { d.regs[r].nr = ZERO_REG; }); + return ok; +} + +bool read_opcodes() +{ + std::unordered_map by_name; + bool ok = true; + + d.opcodes.resize(d.MII->getNumOpcodes()); + by_name.reserve(d.opcodes.size()); + for (unsigned int op = 0; op < d.opcodes.size(); op++) { + const MCInstrDesc &desc = d.MII->get(op); + Opcode &o = d.opcodes[op]; + + by_name[d.MII->getName(op)] = &o; + for (MCPhysReg r : desc.implicit_defs()) { + o.implicit_defs |= d.regs[r].mask; + if (!o.implicit_def && d.regs[r].mask) + o.implicit_def = r; + } + for (MCPhysReg r : desc.implicit_uses()) + if (!o.implicit_use && d.regs[r].mask) + o.implicit_use = r; + /* defs_of() does not look for the last two */ + o.unmodeled = desc.hasUnmodeledSideEffects() || desc.hasOptionalDef() || + desc.variadicOpsAreDefs(); + } + for (const mc_pattern *pattern = mc_arch.patterns; pattern->opcode; pattern++) { + auto it = by_name.find(pattern->opcode); + + if (it == by_name.end()) { + error() << "no opcode " << pattern->opcode << "\n"; + ok = false; + } else if (pattern->kind == TEXT_RETURN) { + it->second->is_return = true; + } else if (pattern->kind != TEXT_OTHER) { + it->second->patterns.push_back(pattern); + } else { + it->second->unmodeled = false; + it->second->implicit_defs |= pattern->defs; + } + } + return ok; +} + +const Reg ®_of(const MCInst &inst, const Opcode &o, u8 nr, bool def) +{ + static const Reg none; + + if (nr == MC_IMPLICIT) + return d.regs[def ? o.implicit_def : o.implicit_use]; + if (nr >= inst.getNumOperands() || !inst.getOperand(nr).isReg()) + return none; + return d.regs[inst.getOperand(nr).getReg()]; +} + +bool holds(const MCInst &inst, const mc_predicate &p) +{ + const MCOperand *a, *b; + + if (p.kind == MC_TRUE) + return true; + if (p.a >= inst.getNumOperands()) + return false; + a = &inst.getOperand(p.a); + switch (p.kind) { + case MC_ZERO_REG: + return a->isReg() && d.regs[a->getReg()].nr == ZERO_REG; + case MC_SAME_REG: + if ((unsigned int)p.b >= inst.getNumOperands()) + return false; + b = &inst.getOperand(p.b); + return a->isReg() && b->isReg() && a->getReg() == b->getReg(); + case MC_IMM: + return a->isImm() && a->getImm() == p.b; + } + return false; +} + +/* Describe INST as PATTERN says. Return false, and leave TI alone, if it does not match */ +bool match(const MCInst &inst, const Opcode &o, const mc_pattern &pattern, text_insn *ti) +{ + const Reg &dst = reg_of(inst, o, pattern.dst, true); + u8 kind = pattern.kind, src = 0, src2 = 0; + bool is32 = dst.bits == 32; + u64 imm = pattern.value; + + if (!holds(inst, pattern.predicates[0]) || !holds(inst, pattern.predicates[1])) + return false; + if (dst.nr >= TEXT_MAX_REGS || !dst.bits) + return false; + if (kind != TEXT_MOV && kind != TEXT_SEXT32 && kind != TEXT_SELECT) { + if (!pattern.fixed) { + if (pattern.imm >= inst.getNumOperands() || !inst.getOperand(pattern.imm).isImm()) + return false; + imm = inst.getOperand(pattern.imm).getImm(); + } + if (pattern.shift >= inst.getNumOperands()) + return false; + if (pattern.shift) + imm <<= inst.getOperand(pattern.shift).getImm(); + if (pattern.invert) + imm = ~imm; + if (is32) + imm = (u32)imm; + } + if (kind != TEXT_MOV_IMM) { + src = src2 = reg_of(inst, o, pattern.src, false).nr; + if (kind == TEXT_SELECT) + src2 = reg_of(inst, o, pattern.src2, false).nr; + /* The zero register is a constant which is not an error: only the other source counts */ + if (src == ZERO_REG) + src = src2; + if (src2 == ZERO_REG) + src2 = src; + if (src >= TEXT_MAX_REGS || src2 >= TEXT_MAX_REGS) + return false; + } + ti->kind = kind; + ti->is32 = is32; + ti->dst = dst.nr; + ti->src = src; + ti->src2 = src2; + ti->imm = imm; + ti->imm2 = pattern.or_zero ? 0 : imm; + return true; +} + +void control_flow(const MCInst &inst, const Opcode &o, u64 addr, text_insn *ti) +{ + const MCInstrDesc &desc = d.MII->get(inst.getOpcode()); + const MCInstrAnalysis &MIA = *d.MIA; + u64 target; + + if (o.is_return) + ti->kind = TEXT_RETURN; + else if (MIA.isCall(inst)) + ti->kind = TEXT_CALL; + else if (MIA.isUnconditionalBranch(inst) || (MIA.isIndirectBranch(inst) && desc.isBarrier())) + ti->kind = TEXT_BRANCH; + else if (MIA.isBranch(inst)) + ti->kind = TEXT_COND_BRANCH; + if (ti->kind >= TEXT_BRANCH && MIA.evaluateBranch(inst, addr, ti->len, target)) + ti->imm = target; + if (ti->kind == TEXT_BRANCH || ti->kind == TEXT_RETURN) + ti->defs = 0; +} + +/* Return the registers which INST writes */ +u32 defs_of(const MCInst &inst, const Opcode &o) +{ + const MCInstrDesc &desc = d.MII->get(inst.getOpcode()); + u32 defs = o.implicit_defs; + + if (o.unmodeled) + return TEXT_ALL_REGS; + /* The operands are not those of the description: which ones are the defs? */ + if (desc.getNumDefs() && inst.getNumOperands() < desc.getNumOperands()) + return TEXT_ALL_REGS; + for (unsigned int i = 0; i < desc.getNumDefs(); i++) { + if (!inst.getOperand(i).isReg()) + return TEXT_ALL_REGS; + defs |= d.regs[inst.getOperand(i).getReg()].mask; + } + return defs; +} + +int decode(const void *code, unsigned int len, u64 addr, text_insn *ti) +{ + MCInst &inst = d.inst; + uint64_t size = 0; + + inst = MCInst(); + *ti = text_insn{}; + /* After SoftFail the MCInst is valid: LLVM has it for "ldtr w8, [x8]" */ + if (d.Dis->getInstruction(inst, size, ArrayRef((const uint8_t *)code, len), addr, + nulls()) == MCDisassembler::Fail) + return -1; + ti->len = size; + + const Opcode &o = d.opcodes[inst.getOpcode()]; + + ti->defs = defs_of(inst, o); + for (const mc_pattern *pattern : o.patterns) { + if (match(inst, o, *pattern, ti)) { + ti->defs &= ~(1U << ti->dst); + return 0; + } + } + control_flow(inst, o, addr, ti); + return 0; +} + +void print(raw_ostream &os, const text_insn &ti) +{ + os << "kind " << (int)ti.kind << " is32 " << ti.is32 << " dst " << (int)ti.dst + << " src " << (int)ti.src << " src2 " << (int)ti.src2 + << " defs " << format_hex(ti.defs, 1) << " imm " << format_hex(ti.imm, 1) + << " imm2 " << format_hex(ti.imm2, 1); +} + +bool run_tests() +{ + bool ok = true; + + for (const mc_test *test = mc_arch.tests; test->code; test++) { + const text_insn &want = test->insn; + std::istringstream in(test->code); + std::vector code; + unsigned int byte; + text_insn ti; + + while (in >> std::hex >> byte) + code.push_back(byte); + if (!decode(code.data(), code.size(), MC_TEST_ADDR, &ti) && ti.len == code.size() && + ti.kind == want.kind && ti.is32 == want.is32 && ti.dst == want.dst && + ti.src == want.src && ti.src2 == want.src2 && + ti.defs == want.defs && ti.imm == want.imm && ti.imm2 == want.imm2) + continue; + print(error() << test->code << " is " << d.MII->getName(d.inst.getOpcode()) << ", length " + << (int)ti.len << ", ", ti); + print(errs() << "\n\texpected: ", want); + errs() << "\n"; + ok = false; + } + return ok; +} + +} /* namespace */ + +extern "C" const struct text_arch *text_arch_init(unsigned int machine) +{ + static text_arch arch = mc_arch.arch; + + if (machine != mc_arch.machine) { + errs() << "text_mc: built for " << mc_arch.triple << ", not for ELF machine " << machine << "\n"; + return nullptr; + } + if (!create() || !read_regs() || !read_opcodes() || !run_tests()) { + error() << "the table of the arch does not fit it. Set LLVM_CONFIG to the " + "llvm-config of another LLVM, or switch CONFIG_BPF_FMODRET_SCAN off\n"; + return nullptr; + } + arch.decode = decode; + return &arch; +} diff --git a/tools/bpf/resolve_btfids/text_mc.h b/tools/bpf/resolve_btfids/text_mc.h new file mode 100644 index 000000000000..9d39095aab20 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_mc.h @@ -0,0 +1,105 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef __TEXT_MC_H +#define __TEXT_MC_H + +#include "text_insn.h" + +/* + * What text_mc.cpp has to be told about an arch to describe its instructions + * in the terms of text_insn.h with LLVM's MC layer. + * + * MC gives the length, the MCInst, the flags of MCInstrDesc, the explicit and + * the implicit defs, the aliases of a register and the target of a branch. + * It does not say what an instruction computes: the selection patterns are not + * a part of it. And the headers with the enums of a target are not installed. + * So opcodes and registers are given by name, as MCInstrInfo::getName() and + * MCRegisterInfo::getName() return them, and looked up once. A name which this + * LLVM does not have is an error. + */ + +/* A condition on the operands of an MCInst, like an MCInstPredicate of TableGen */ +enum mc_predicate_kind { + MC_TRUE, + MC_ZERO_REG, /* operand A is the zero register */ + MC_SAME_REG, /* operands A and B are the same register */ + MC_IMM, /* operand A is the immediate B */ +}; + +struct mc_predicate { + u8 kind; + u8 a; + s32 b; +}; + +#define ZERO_REG(a) { MC_ZERO_REG, a, 0 } +#define SAME_REG(a, b) { MC_SAME_REG, a, b } +#define IMM(a, b) { MC_IMM, a, b } +#define VALUE(v) .fixed = true, .value = v + +/* Instead of the number of an operand: the first implicit def or use */ +#define MC_IMPLICIT 0xff + +/* + * What an opcode computes, if it makes or copies a value. The patterns of an + * opcode are tried in their order. The width of the operation is that of the + * register DST. + * + * A pattern of kind TEXT_OTHER is about the defs. hasUnmodeledSideEffects() is + * how LLVM says that MCInstrDesc does not tell all about an opcode: it writes + * TEXT_ALL_REGS, unless such a pattern says that it writes what MCInstrDesc + * has, and DEFS. + * + * A pattern of kind TEXT_RETURN names a return to the caller. isReturn() holds + * for a return from an exception as well, which does not hand the return value + * register to a caller. Without such a pattern it is an opcode like any other, + * and LLVM says hasUnmodeledSideEffects() of it. + * + * Without a pattern errors are lost, none is made up. So an opcode has one only + * if that brings more than a few errors in some kernel. + */ +struct mc_pattern { + const char *opcode; + u8 kind; /* enum text_insn_kind */ + u8 dst, src, src2; /* the numbers of the operands. DST is 0 unless it is given */ + u8 imm; /* the operand with the immediate */ + u8 shift; /* the operand which says how far the immediate is shifted left */ + bool invert; /* the immediate */ + bool or_zero; /* TEXT_MOV_IMM: the immediate or 0 */ + bool fixed; /* the immediate is VALUE, not an operand */ + s64 value; + u32 defs; /* of TEXT_OTHER */ + struct mc_predicate predicates[2]; +}; + +/* An instruction, in hex, and what text_arch.decode() has to say about it at MC_TEST_ADDR */ +struct mc_test { + const char *code; + struct text_insn insn; +}; + +#define MC_TEST_ADDR 0x1000 + +struct mc_arch { + struct text_arch arch; + unsigned int machine; /* of the ELF header */ + const char *triple, *features; + /* + * The names of registers 0, 1, ... of text_insn.h, separated by spaces. + * A write of a register in REGS32 zero extends. A write of any other + * alias is not a copy. + */ + const char *regs, *regs32; + const char *zero_regs; + const struct mc_pattern *patterns; + /* + * LLVM's tables and names change from release to release, and the ones + * above were written for some of them. text_arch_init() fails if one of + * these instructions is no longer described as it was. + */ + const struct mc_test *tests; +}; + +/* The arch which the tool is built for, see Build */ +extern const struct mc_arch mc_arch; + +#endif diff --git a/tools/bpf/resolve_btfids/text_mc_arm64.c b/tools/bpf/resolve_btfids/text_mc_arm64.c new file mode 100644 index 000000000000..9cc44281242b --- /dev/null +++ b/tools/bpf/resolve_btfids/text_mc_arm64.c @@ -0,0 +1,118 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* arm64 for text_mc.cpp */ + +#include +#include + +#include "text_mc.h" + +/* The W and the X form of an opcode */ +#define WX(before, after, ...) \ + { before "W" after, __VA_ARGS__ }, { before "X" after, __VA_ARGS__ } + +static const struct mc_pattern arm64_patterns[] = { + WX("MOVN", "i", TEXT_MOV_IMM, .imm = 1, .shift = 2, .invert = true), + WX("ORR", "rs", TEXT_MOV, .src = 2, .predicates = { ZERO_REG(1), IMM(3, 0) }), /* mov */ + { "SBFMXri", TEXT_SEXT32, .src = 1, .predicates = { IMM(2, 0), IMM(3, 31) } }, /* sxtw */ + WX("CSEL", "r", TEXT_SELECT, .src = 1, .src2 = 2), + { "CSINVWr", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, + .predicates = { ZERO_REG(1), ZERO_REG(2) } }, /* csetm */ + { "CSINVWr", TEXT_SELECT_IMM, .src = 1, VALUE(-1), .predicates = { ZERO_REG(2) } }, + /* rn, or a function of rm */ + { "CSINCWr", TEXT_SELECT, .src = 1, .src2 = 1 }, + /* and rd, rn, rm, asr #31: rn or 0 */ + { "ANDWrs", TEXT_SELECT, .src = 1, .src2 = 1, .predicates = { IMM(3, 2 << 6 | 31) } }, + /* HINT: nop, bti, yield, wfe ... */ + { "HINT", TEXT_OTHER }, { "AUTIASP", TEXT_OTHER }, { "PRFMui", TEXT_OTHER }, + { "DMB", TEXT_OTHER }, { "MRS", TEXT_OTHER }, { "MSR", TEXT_OTHER }, + { "STLRB", TEXT_OTHER }, { "STLRW", TEXT_OTHER }, + WX("LDXR", "", TEXT_OTHER), WX("STXR", "", TEXT_OTHER), WX("STLXR", "", TEXT_OTHER), + { "RET", TEXT_RETURN }, + {} +}; + +#define T(code, insn_kind, ...) { code, { .kind = insn_kind, __VA_ARGS__ } } +#define IMMS(a, b) .imm = a, .imm2 = b +#define SRC(reg) .src = reg, .src2 = reg + +/* Each pattern, and what must not match it */ +static const struct mc_test arm64_tests[] = { + T("a0 02 80 12", TEXT_MOV_IMM, .is32 = true, IMMS(0xffffffea, 0xffffffea)), /* mov w0, #-22 */ + T("a0 02 80 92", TEXT_MOV_IMM, IMMS(-22, -22)), /* mov x0, #-22 */ + T("20 00 a0 12", TEXT_MOV_IMM, .is32 = true, IMMS(0xfffeffff, 0xfffeffff)), /* mov w0, #-0x10001 */ + T("e0 03 13 2a", TEXT_MOV, .is32 = true, SRC(19)), /* mov w0, w19 */ + T("e0 03 13 aa", TEXT_MOV, SRC(19)), /* mov x0, x19 */ + T("20 00 02 2a", TEXT_OTHER, .defs = BIT(0)), /* orr w0, w1, w2 */ + T("20 00 02 aa", TEXT_OTHER, .defs = BIT(0)), /* orr x0, x1, x2 */ + T("e0 07 13 2a", TEXT_OTHER, .defs = BIT(0)), /* orr w0, wzr, w19, lsl #1 */ + T("60 7e 40 93", TEXT_SEXT32, SRC(19)), /* sxtw x0, w19 */ + T("60 3e 40 93", TEXT_OTHER, .defs = BIT(0)), /* sxth x0, w19 */ + T("00 01 89 1a", TEXT_SELECT, .is32 = true, .src = 8, .src2 = 9), /* csel w0, w8, w9, eq */ + T("00 01 89 9a", TEXT_SELECT, .src = 8, .src2 = 9), /* csel x0, x8, x9, eq */ + T("00 01 9f 9a", TEXT_SELECT, SRC(8)), /* csel x0, x8, xzr, eq */ + T("e0 03 9f 5a", TEXT_MOV_IMM, .is32 = true, IMMS(0xffffffff, 0)), /* csetm w0, ne */ + T("00 01 9f 5a", TEXT_SELECT_IMM, .is32 = true, SRC(8), IMMS(0xffffffff, 0xffffffff)), /* csinv w0, w8, wzr, eq */ + T("00 01 89 5a", TEXT_OTHER, .defs = BIT(0)), /* csinv w0, w8, w9, eq */ + T("00 05 89 1a", TEXT_SELECT, .is32 = true, SRC(8)), /* csinc w0, w8, w9, eq */ + T("00 7d 89 0a", TEXT_SELECT, .is32 = true, SRC(8)), /* and w0, w8, w9, asr #31 */ + T("00 01 09 0a", TEXT_OTHER, .defs = BIT(0)), /* and w0, w8, w9 */ + T("5f 24 03 d5", TEXT_OTHER), /* bti c */ + T("bf 23 03 d5", TEXT_OTHER, .defs = BIT(30)), /* autiasp */ + T("20 00 80 f9", TEXT_OTHER), /* prfm pldl1keep, [x1] */ + T("bf 3b 03 d5", TEXT_OTHER), /* dmb ish */ + /* The brk of BUG() has no next instruction. No return value passes a brk, like ud2 */ + T("00 00 21 d4", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* brk #0x800 */ + T("80 d0 38 d5", TEXT_OTHER, .defs = BIT(0)), /* mrs x0, tpidr_el1 */ + T("80 d0 18 d5", TEXT_OTHER), /* msr tpidr_el1, x0 */ + T("20 fc 9f 08", TEXT_OTHER), /* stlrb w0, [x1] */ + T("20 fc 9f 88", TEXT_OTHER), /* stlr w0, [x1] */ + T("20 7c 5f 88", TEXT_OTHER, .defs = BIT(0)), /* ldxr w0, [x1] */ + T("20 7c 5f c8", TEXT_OTHER, .defs = BIT(0)), /* ldxr x0, [x1] */ + T("41 7c 00 88", TEXT_OTHER, .defs = BIT(0)), /* stxr w0, w1, [x2] */ + T("41 7c 00 c8", TEXT_OTHER, .defs = BIT(0)), /* stxr w0, x1, [x2] */ + T("41 fc 00 88", TEXT_OTHER, .defs = BIT(0)), /* stlxr w0, w1, [x2] */ + T("41 fc 00 c8", TEXT_OTHER, .defs = BIT(0)), /* stlxr w0, x1, [x2] */ + /* hasUnmodeledSideEffects() */ + T("02 00 00 d4", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* hvc #0 */ + /* A write of these which is missed would change the errors of a function in some kernel */ + T("20 00 a0 52", TEXT_OTHER, .defs = BIT(0)), /* mov w0, #0x10000 */ + T("20 78 1d 12", TEXT_OTHER, .defs = BIT(0)), /* and w0, w1, #0xfffffffb */ + T("00 01 09 8a", TEXT_OTHER, .defs = BIT(0)), /* and x0, x8, x9 */ + T("00 01 09 6a", TEXT_OTHER, .defs = BIT(0)), /* ands w0, w8, w9 */ + T("00 01 29 0a", TEXT_OTHER, .defs = BIT(0)), /* bic w0, w8, w9 */ + T("20 00 00 32", TEXT_OTHER, .defs = BIT(0)), /* orr w0, w1, #1 */ + T("20 04 00 11", TEXT_OTHER, .defs = BIT(0)), /* add w0, w1, #1 */ + T("20 08 01 53", TEXT_OTHER, .defs = BIT(0)), /* ubfx w0, w1, #1, #2 */ + T("20 00 40 f9", TEXT_OTHER, .defs = BIT(0)), /* ldr x0, [x1] */ + T("20 00 40 b9", TEXT_OTHER, .defs = BIT(0)), /* ldr w0, [x1] */ + T("20 c0 5f b8", TEXT_OTHER, .defs = BIT(0)), /* ldur w0, [x1, #-4] */ + T("20 c0 9f b8", TEXT_OTHER, .defs = BIT(0)), /* ldursw x0, [x1, #-4] */ + T("08 09 40 b8", TEXT_OTHER, .defs = BIT(8)), /* ldtr w8, [x8] */ + /* The control flow */ + T("10 00 00 14", TEXT_BRANCH, .imm = MC_TEST_ADDR + 0x40), /* b */ + T("00 01 1f d6", TEXT_BRANCH), /* br x8 */ + T("00 02 00 b4", TEXT_COND_BRANCH, .imm = MC_TEST_ADDR + 0x40), /* cbz x0 */ + T("10 00 00 94", TEXT_CALL, .defs = BIT(30), .imm = MC_TEST_ADDR + 0x40), /* bl */ + T("00 01 3f d6", TEXT_CALL, .defs = BIT(30)), /* blr x8 */ + T("c0 03 5f d6", TEXT_RETURN), /* ret */ + T("e0 03 9f d6", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* eret */ + {} +}; + +const struct mc_arch mc_arch = { + .arch = { + .retval = 0, + /* AAPCS64: x0 to x18 and x30 */ + .caller_saved = 0x4007ffff, + }, + .machine = EM_AARCH64, + .triple = "aarch64-unknown-linux-gnu", + .features = "+all", + .regs = "X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 X15 X16 X17 X18 X19 X20 " + "X21 X22 X23 X24 X25 X26 X27 X28 FP LR", + .regs32 = "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 " + "W21 W22 W23 W24 W25 W26 W27 W28 W29 W30", + .zero_regs = "WZR XZR", + .patterns = arm64_patterns, + .tests = arm64_tests, +}; diff --git a/tools/bpf/resolve_btfids/text_mc_x86.c b/tools/bpf/resolve_btfids/text_mc_x86.c new file mode 100644 index 000000000000..11223cd1c077 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_mc_x86.c @@ -0,0 +1,118 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* x86-64 for text_mc.cpp */ + +#include +#include + +#include "text_mc.h" + +enum { RAX, RCX, RDX, RBX, RSP, RBP, RSI, RDI, R8, R9, R10, R11 }; + +#define I MC_IMPLICIT + +static const struct mc_pattern x86_patterns[] = { + /* A 64-bit immediate, MOV64ri, may be a runtime constant, which the kernel patches */ + { "MOV32ri", TEXT_MOV_IMM, .imm = 1 }, + { "MOV64ri32", TEXT_MOV_IMM, .imm = 1 }, + { "OR32ri8", TEXT_MOV_IMM, .imm = 2, .predicates = { IMM(2, -1) } }, + { "OR64ri8", TEXT_MOV_IMM, .imm = 2, .predicates = { IMM(2, -1) } }, + { "MOV32rr", TEXT_MOV, .src = 1 }, + { "MOV64rr", TEXT_MOV, .src = 1 }, + { "MOVSX64rr32", TEXT_SEXT32, .src = 1 }, + { "CDQE", TEXT_SEXT32, .dst = I, .src = I }, + { "CMOV32rr", TEXT_SELECT, .src = 2, .src2 = 1 }, + { "CMOV64rr", TEXT_SELECT, .src = 2, .src2 = 1 }, + /* All bits of the result are equal */ + { "SBB32rr", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { SAME_REG(1, 2) } }, + { "SBB64rr", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { SAME_REG(1, 2) } }, + { "SAR32ri", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { IMM(2, 31) } }, + { "LOCK_PREFIX", TEXT_OTHER }, + /* A rep prefix is not a part of the MCInst */ + { "STOSQ", TEXT_OTHER, .defs = BIT(RCX) }, + { "RET64", TEXT_RETURN }, + {} +}; + +#define T(code, insn_kind, ...) { code, { .kind = insn_kind, __VA_ARGS__ } } +#define IMMS(a, b) .imm = a, .imm2 = b +#define SRC(reg) .src = reg, .src2 = reg + +/* Each pattern, and what must not match it */ +static const struct mc_test x86_tests[] = { + T("b8 ea ff ff ff", TEXT_MOV_IMM, .is32 = true, IMMS(0xffffffea, 0xffffffea)), /* mov $-22, %eax */ + T("48 c7 c3 ea ff ff ff", TEXT_MOV_IMM, .dst = RBX, IMMS(-22, -22)), /* mov $-22, %rbx */ + T("83 c8 ff", TEXT_MOV_IMM, .is32 = true, IMMS(0xffffffff, 0xffffffff)), /* or $-1, %eax */ + T("48 83 c8 ff", TEXT_MOV_IMM, IMMS(-1, -1)), /* or $-1, %rax */ + T("83 c8 f0", TEXT_OTHER, .defs = BIT(RAX)), /* or $-16, %eax */ + T("48 83 c8 f0", TEXT_OTHER, .defs = BIT(RAX)), /* or $-16, %rax */ + T("19 c0", TEXT_MOV_IMM, .is32 = true, IMMS(0xffffffff, 0)), /* sbb %eax, %eax */ + T("48 19 c0", TEXT_MOV_IMM, IMMS(-1, 0)), /* sbb %rax, %rax */ + T("19 d8", TEXT_OTHER, .defs = BIT(RAX)), /* sbb %ebx, %eax */ + T("48 19 d8", TEXT_OTHER, .defs = BIT(RAX)), /* sbb %rbx, %rax */ + T("c1 f8 1f", TEXT_MOV_IMM, .is32 = true, IMMS(0xffffffff, 0)), /* sar $31, %eax */ + T("c1 f8 1e", TEXT_OTHER, .defs = BIT(RAX)), /* sar $30, %eax */ + T("89 d8", TEXT_MOV, .is32 = true, SRC(RBX)), /* mov %ebx, %eax */ + T("4c 89 e0", TEXT_MOV, SRC(12)), /* mov %r12, %rax */ + T("48 63 c3", TEXT_SEXT32, SRC(RBX)), /* movslq %ebx, %rax */ + T("48 98", TEXT_SEXT32, SRC(RAX)), /* cltq */ + T("0f 44 c3", TEXT_SELECT, .is32 = true, .src = RBX, .src2 = RAX), /* cmove %ebx, %eax */ + T("48 0f 44 c3", TEXT_SELECT, .src = RBX, .src2 = RAX), /* cmove %rbx, %rax */ + T("f0", TEXT_OTHER), /* lock */ + T("f3 48 ab", TEXT_OTHER, .defs = BIT(RCX) | BIT(RDI)), /* rep stosq */ + /* hasUnmodeledSideEffects() */ + T("f3 48 a5", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* rep movsq */ + T("0f 05", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* syscall */ + T("0f 0b", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* ud2 */ + /* A write of these which is missed would change the errors of a function in some kernel */ + T("31 d8", TEXT_OTHER, .defs = BIT(RAX)), /* xor %ebx, %eax */ + T("8b 03", TEXT_OTHER, .defs = BIT(RAX)), /* mov (%rbx), %eax */ + T("48 8b 03", TEXT_OTHER, .defs = BIT(RAX)), /* mov (%rbx), %rax */ + T("8d 04 1b", TEXT_OTHER, .defs = BIT(RAX)), /* lea (%rbx,%rbx), %eax */ + T("03 03", TEXT_OTHER, .defs = BIT(RAX)), /* add (%rbx), %eax */ + T("83 c0 10", TEXT_OTHER, .defs = BIT(RAX)), /* add $16, %eax */ + T("48 83 c0 10", TEXT_OTHER, .defs = BIT(RAX)), /* add $16, %rax */ + T("05 00 01 00 00", TEXT_OTHER, .defs = BIT(RAX)), /* add $256, %eax */ + T("81 c3 00 01 00 00", TEXT_OTHER, .defs = BIT(RBX)), /* add $256, %ebx */ + T("48 81 c3 00 01 00 00", TEXT_OTHER, .defs = BIT(RBX)), /* add $256, %rbx */ + T("29 d8", TEXT_OTHER, .defs = BIT(RAX)), /* sub %ebx, %eax */ + T("21 d8", TEXT_OTHER, .defs = BIT(RAX)), /* and %ebx, %eax */ + T("25 00 01 00 00", TEXT_OTHER, .defs = BIT(RAX)), /* and $256, %eax */ + T("81 e3 00 01 00 00", TEXT_OTHER, .defs = BIT(RBX)), /* and $256, %ebx */ + T("48 81 e3 00 01 00 00", TEXT_OTHER, .defs = BIT(RBX)), /* and $256, %rbx */ + T("09 d8", TEXT_OTHER, .defs = BIT(RAX)), /* or %ebx, %eax */ + T("48 63 03", TEXT_OTHER, .defs = BIT(RAX)), /* movslq (%rbx), %rax */ + T("48 c1 e8 02", TEXT_OTHER, .defs = BIT(RAX)), /* shr $2, %rax */ + T("48 c1 f8 3f", TEXT_OTHER, .defs = BIT(RAX)), /* sar $63, %rax */ + T("0f 44 0b", TEXT_OTHER, .defs = BIT(RCX)), /* cmove (%rbx), %ecx */ + T("48 0f 44 0b", TEXT_OTHER, .defs = BIT(RCX)), /* cmove (%rbx), %rcx */ + T("83 d8 00", TEXT_OTHER, .defs = BIT(RAX)), /* sbb $0, %eax */ + T("83 d0 00", TEXT_OTHER, .defs = BIT(RAX)), /* adc $0, %eax */ + T("0f bd c3", TEXT_OTHER, .defs = BIT(RAX)), /* bsr %ebx, %eax */ + T("48 0f bd c3", TEXT_OTHER, .defs = BIT(RAX)), /* bsr %rbx, %rax */ + T("80 e3 01", TEXT_OTHER, .defs = BIT(RBX)), /* and $1, %bl */ + T("48 0f c1 13", TEXT_OTHER, .defs = BIT(RDX)), /* xadd %rdx, (%rbx) */ + /* The control flow */ + T("eb 10", TEXT_BRANCH, .imm = MC_TEST_ADDR + 0x12), /* jmp */ + T("ff e0", TEXT_BRANCH), /* jmp *%rax */ + T("0f 84 00 01 00 00", TEXT_COND_BRANCH, .imm = MC_TEST_ADDR + 0x106), /* je */ + T("e8 00 01 00 00", TEXT_CALL, .imm = MC_TEST_ADDR + 0x105), /* call */ + T("c3", TEXT_RETURN), /* ret */ + T("48 cf", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* iretq */ + {} +}; + +const struct mc_arch mc_arch = { + .arch = { + .retval = RAX, + .caller_saved = BIT(RAX) | BIT(RCX) | BIT(RDX) | BIT(RSI) | BIT(RDI) | + BIT(R8) | BIT(R9) | BIT(R10) | BIT(R11), + .return_thunk = "__x86_return_thunk", + }, + .machine = EM_X86_64, + .triple = "x86_64-unknown-linux-gnu", + .features = "", + .regs = "RAX RCX RDX RBX RSP RBP RSI RDI R8 R9 R10 R11 R12 R13 R14 R15", + .regs32 = "EAX ECX EDX EBX ESP EBP ESI EDI R8D R9D R10D R11D R12D R13D R14D R15D", + .patterns = x86_patterns, + .tests = x86_tests, +}; -- 2.55.0 From: Anton Protopopov int f(struct file *file, int mode) { int ret = -EINVAL; if (mode & ~MASK) goto out; ret = g(file); out: return ret; } Which constants does f() return? A compiler loads a constant into any register. Copies, sign extensions and selects carry it to the return value register. Run a data flow analysis on the instructions of one function. It is backward and "may", like liveness. The fact at a point is the set of registers whose value may become the return value: fact before the instruction mov $0xffffffea,%ebx {} -22 is returned test $0xfffffff8,%esi {rbx} jne 1f {rbx} join: {} + {rbx} call g {} a call writes rax mov %eax,%ebx {rax} 1: mov %ebx,%eax {rbx} ret {rax} transfer functions and join return { return value register } dst = src src takes the place of dst another write the register leaves the set call the caller-saved registers leave the set join union An instruction that loads a constant into dst is a definition that reaches the return value, if dst is in the fact after it. One run answers the question for all constants of the function. It is a may analysis. Branches are not evaluated: a constant counts if a path of the control flow graph carries it. Memory is not tracked: a constant that is spilled to the stack is not found. "mov $-22,%eax" makes 0xffffffea. That is an error for a function that returns int. For a function that returns long it is a large number, unless cltq follows. So there are three sets: returned as it is, zero extended, sign extended. Nothing in the analysis depends on the arch. Signed-off-by: Anton Protopopov Co-developed-by: Alexei Starovoitov Signed-off-by: Alexei Starovoitov --- tools/bpf/resolve_btfids/Build | 4 + tools/bpf/resolve_btfids/text_flow.c | 145 +++++++++++++++++++++++++++ tools/bpf/resolve_btfids/text_flow.h | 44 ++++++++ 3 files changed, 193 insertions(+) create mode 100644 tools/bpf/resolve_btfids/text_flow.c create mode 100644 tools/bpf/resolve_btfids/text_flow.h diff --git a/tools/bpf/resolve_btfids/Build b/tools/bpf/resolve_btfids/Build index b9e5bf21439f..cd42283bb929 100644 --- a/tools/bpf/resolve_btfids/Build +++ b/tools/bpf/resolve_btfids/Build @@ -3,6 +3,7 @@ hostprogs := resolve_btfids resolve_btfids-y += main.o resolve_btfids-y += btf_colors.o resolve_btfids-y += image.o +resolve_btfids-y += text_flow.o resolve_btfids-$(LLVM_MC) += text_mc.o resolve_btfids-$(LLVM_MC) += text_mc_$(SRCARCH).o resolve_btfids-y += rbtree.o @@ -11,6 +12,9 @@ resolve_btfids-y += string.o resolve_btfids-y += ctype.o resolve_btfids-y += str_error_r.o +# The inner loops of --fmodret_scan +HOSTCFLAGS_text_flow.o += -O2 + # LLVM's C++ API may have moved on, see Makefile $(OUTPUT)text_mc.o: cmd_cxx_o_c += $(or_llvm_mc_help) diff --git a/tools/bpf/resolve_btfids/text_flow.c b/tools/bpf/resolve_btfids/text_flow.c new file mode 100644 index 000000000000..2d58ffb2e939 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_flow.c @@ -0,0 +1,145 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* Which values does a function return? See text_flow.h */ + +#include +#include + +#include "text_flow.h" + +/* Return the index of the instruction which runs after I if I does not branch */ +static u32 next_insn(const struct text_flow *flow, u32 i) +{ + const struct text_insn *insn = &flow->insns[i]; + + /* A function and its cold subfunctions are not adjacent */ + return i + 1 < flow->nr_insns && insn[1].addr == insn->addr + insn->len ? + i + 1 : TEXT_NO_INSN; +} + +static u32 insn_at(const struct text_flow *flow, u64 addr) +{ + u32 lo = 0, hi = flow->nr_insns; + + while (lo < hi) { + u32 mid = lo + (hi - lo) / 2; + + if (flow->insns[mid].addr < addr) + lo = mid + 1; + else + hi = mid; + } + return lo < flow->nr_insns && flow->insns[lo].addr == addr ? lo : TEXT_NO_INSN; +} + +static void join(struct text_facts *facts, const struct text_flow *flow, u32 i) +{ + if (i == TEXT_NO_INSN) + return; + facts->same |= flow->facts[i].same; + facts->zext |= flow->facts[i].zext; + facts->sext |= flow->facts[i].sext; +} + +static void kill(struct text_facts *facts, u32 regs) +{ + facts->same &= ~regs; + facts->zext &= ~regs; + facts->sext &= ~regs; +} + +enum cast { SAME, ZEXT, SEXT }; + +/* The facts of DST behind "dst = cast(src)" are those of SRC before it */ +static void copy(struct text_facts *in, const struct text_facts *out, u8 dst, u8 src, + enum cast cast) +{ + bool same = out->same & BIT(dst), zext = out->zext & BIT(dst), sext = out->sext & BIT(dst); + + if (same && cast == SAME) + in->same |= BIT(src); + if (zext || (same && cast == ZEXT)) + in->zext |= BIT(src); + if (sext || (same && cast == SEXT)) + in->sext |= BIT(src); +} + +/* Return the facts before instruction I */ +static struct text_facts transfer(const struct text_flow *flow, u32 i) +{ + const struct text_insn *insn = &flow->insns[i]; + struct text_facts out = {}, in; + enum cast cast; + + switch (insn->kind) { + case TEXT_RETURN: + out.same = BIT(flow->arch->retval); + return out; + case TEXT_BRANCH: + join(&out, flow, insn->target); + return out; + case TEXT_COND_BRANCH: + join(&out, flow, insn->target); + break; + } + join(&out, flow, next_insn(flow, i)); + + in = out; + kill(&in, insn->defs); + switch (insn->kind) { + case TEXT_CALL: + kill(&in, flow->arch->caller_saved); + break; + case TEXT_MOV_IMM: + kill(&in, BIT(insn->dst)); + break; + case TEXT_MOV: + case TEXT_SEXT32: + case TEXT_SELECT: + case TEXT_SELECT_IMM: + cast = insn->kind == TEXT_SEXT32 ? SEXT : insn->is32 ? ZEXT : SAME; + kill(&in, BIT(insn->dst)); + copy(&in, &out, insn->dst, insn->src, cast); + if (insn->kind == TEXT_SELECT) + copy(&in, &out, insn->dst, insn->src2, cast); + break; + } + return in; +} + +/* + * Sweep from the last instruction to the first one until nothing changes. The + * sets only grow, and one more sweep is needed only for what goes around a loop. + */ +void text_flow_solve(struct text_flow *flow) +{ + bool changed; + u32 i; + + for (i = 0; i < flow->nr_insns; i++) { + struct text_insn *insn = &flow->insns[i]; + + flow->facts[i] = (struct text_facts){}; + insn->target = TEXT_NO_INSN; + if ((insn->kind == TEXT_BRANCH || insn->kind == TEXT_COND_BRANCH) && insn->imm) + insn->target = insn_at(flow, insn->imm); + } + do { + changed = false; + for (i = flow->nr_insns; i--; ) { + struct text_facts *old = &flow->facts[i], new = transfer(flow, i); + + if (new.same == old->same && new.zext == old->zext && new.sext == old->sext) + continue; + *old = new; + changed = true; + } + } while (changed); +} + +struct text_facts text_flow_out(const struct text_flow *flow, u32 i) +{ + struct text_facts out = {}; + + join(&out, flow, next_insn(flow, i)); + return out; +} diff --git a/tools/bpf/resolve_btfids/text_flow.h b/tools/bpf/resolve_btfids/text_flow.h new file mode 100644 index 000000000000..b307c08fd163 --- /dev/null +++ b/tools/bpf/resolve_btfids/text_flow.h @@ -0,0 +1,44 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef __TEXT_FLOW_H +#define __TEXT_FLOW_H + +#include "text_insn.h" + +/* + * Which values does a function return? A backward may data flow analysis of + * the machine code of one function. + * + * The fact at a point of the code is the set of registers whose value at that + * point may become the return value: the return value register at a return, + * and before "dst = src" the register src if dst is in the set behind it. The + * join is the union. Branches are not evaluated, calls write what the ABI lets + * them write, memory is not tracked. + * + * A copy may convert the value, and only the last conversion counts. So there + * are three sets. + */ +struct text_facts { + u32 same; /* returned as it is */ + u32 zext; /* the low 32 bits are returned, zero extended */ + u32 sext; /* the low 32 bits are returned, sign extended */ +}; + +struct text_flow { + const struct text_arch *arch; + /* + * All instructions of the function in the order of their addresses, + * whether they can be reached or not: the way to a block may be a jump + * which is patched in at run time, or an exception. + */ + struct text_insn *insns; + u32 nr_insns; + /* The result: the facts before each instruction */ + struct text_facts *facts; +}; + +/* Compute the facts */ +void text_flow_solve(struct text_flow *flow); +/* Return the facts behind instruction I, which is not a branch */ +struct text_facts text_flow_out(const struct text_flow *flow, u32 i); + +#endif -- 2.55.0 From: Anton Protopopov SEC("fmod_ret/vfs_fallocate") int BPF_PROG(no_collapse, struct file *file, int mode, loff_t offset, loff_t len, int ret) { return mode & FALLOC_FL_COLLAPSE_RANGE ? -EOPNOTSUPP : 0; } This program keeps user space away from a bug in one mode of fallocate() until the fixed kernel runs. It does not load: "vfs_fallocate() is not modifiable". The declared targets are the security hooks, the error injection list (1000 syscall entries and 16 functions) and five more functions. vfs_fallocate() returns -EOPNOTSUPP itself, so its callers can get that error today. The build can find such functions, and their errors. With --fmodret_scan resolve_btfids does that for each FUNC of BTF: FUNC -> image_func() -> decode -> data flow -> constants -4095..-1 | DECL_TAG 'bpf_fmodret_retval:-95,-29,-27,-26,-22,-21,-19,-9,-1' type_id= It reads the file that pahole has just read. So it sees the code after inlining and after the link, of GCC and of clang, of vmlinux and modules. A function gets a tag only if return type BTF says: integer or enum of 4 or 8 bytes name one ELF function has the name of the FUNC and a program can attach to it parameters BTF says: at most 12 of at most 16 bytes, no "..." section it is not .init.text entry it has the nop, or "call __fentry__", that ftrace patches. A notrace function has none An error is left out of the list if 8 bytes the constant is zero extended: 0xffffffea meaning -512 and below, -EAGAIN, -EMSGSIZE, -EINPROGRESS: these tell the caller to retry, to go on, to wait -1 alone it is -1 and the only error. -1 is also "less" or "not found": the machine code cannot tell CONFIG_BPF_FMODRET_SCAN turns it on, for x86-64 and arm64. The default is off. At this patch an x86-64 build with GCC prints FMODRET 12076 of 78350 functions are tagged, 0 of the 35445 which were scanned cannot be decoded A function that cannot be decoded gets no tag. The link fails if that is more than 1 % of the scanned functions, or if vmlinux gets no tag. BTF grows by 3 %, and resolve_btfids takes 0.4 s more for vmlinux. Signed-off-by: Anton Protopopov Co-developed-by: Alexei Starovoitov Signed-off-by: Alexei Starovoitov --- kernel/bpf/Kconfig | 19 ++ scripts/Makefile.btf | 1 + tools/bpf/resolve_btfids/Build | 3 + tools/bpf/resolve_btfids/fmodret.c | 166 +++++++++++++++++ tools/bpf/resolve_btfids/fmodret.h | 12 ++ tools/bpf/resolve_btfids/fmodret_scan.c | 219 +++++++++++++++++++++++ tools/bpf/resolve_btfids/fmodret_scan.h | 22 +++ tools/bpf/resolve_btfids/main.c | 11 ++ tools/bpf/resolve_btfids/text_insn.h | 6 + tools/bpf/resolve_btfids/text_mc.cpp | 6 + tools/bpf/resolve_btfids/text_mc.h | 2 + tools/bpf/resolve_btfids/text_mc_arm64.c | 2 + tools/bpf/resolve_btfids/text_mc_x86.c | 3 + 13 files changed, 472 insertions(+) create mode 100644 tools/bpf/resolve_btfids/fmodret.c create mode 100644 tools/bpf/resolve_btfids/fmodret.h create mode 100644 tools/bpf/resolve_btfids/fmodret_scan.c create mode 100644 tools/bpf/resolve_btfids/fmodret_scan.h diff --git a/kernel/bpf/Kconfig b/kernel/bpf/Kconfig index 2b7bbb9bd5f8..d705d7b38b5f 100644 --- a/kernel/bpf/Kconfig +++ b/kernel/bpf/Kconfig @@ -110,6 +110,25 @@ config BPF_CRYPTO source "kernel/bpf/preload/Kconfig" +config BPF_FMODRET_SCAN + bool "Find the functions which fmod_ret programs can attach to" + depends on BPF_SYSCALL && DEBUG_INFO_BTF + depends on X86_64 || ARM64 + depends on DYNAMIC_FTRACE_WITH_DIRECT_CALLS + depends on $(success,$(srctree)/tools/bpf/resolve_btfids/llvm-mc.sh $(SRCARCH)) + help + Let resolve_btfids read the machine code of the kernel and of the + modules, and tag the functions which return errors in BTF. An + fmod_ret program can attach to such a function and return one of + its errors instead of running it, for example to keep user space + away from a bug until the kernel is updated. + + The build host needs a C++17 compiler and the headers and libraries + of LLVM 17 or later with the target of the kernel, whatever compiles + the kernel. tools/bpf/resolve_btfids/llvm-mc.sh tells what is missing. + It only looks whether they are installed. The build stops if + resolve_btfids cannot be built with them. + config BPF_LSM bool "Enable BPF LSM Instrumentation" depends on BPF_EVENTS diff --git a/scripts/Makefile.btf b/scripts/Makefile.btf index 98012344a81e..02ff1702e1e8 100644 --- a/scripts/Makefile.btf +++ b/scripts/Makefile.btf @@ -35,5 +35,6 @@ resolve-btfids-flags-y := resolve-btfids-flags-$(CONFIG_WERROR) += --fatal_warnings resolve-btfids-flags-$(if $(KBUILD_EXTMOD),y) += --distill_base resolve-btfids-flags-$(if $(KBUILD_VERBOSE),y) += --verbose +resolve-btfids-flags-$(CONFIG_BPF_FMODRET_SCAN) += --fmodret_scan export RESOLVE_BTFIDS_FLAGS := $(resolve-btfids-flags-y) diff --git a/tools/bpf/resolve_btfids/Build b/tools/bpf/resolve_btfids/Build index cd42283bb929..bfbde4c49dde 100644 --- a/tools/bpf/resolve_btfids/Build +++ b/tools/bpf/resolve_btfids/Build @@ -2,6 +2,8 @@ hostprogs := resolve_btfids resolve_btfids-y += main.o resolve_btfids-y += btf_colors.o +resolve_btfids-y += fmodret.o +resolve_btfids-y += fmodret_scan.o resolve_btfids-y += image.o resolve_btfids-y += text_flow.o resolve_btfids-$(LLVM_MC) += text_mc.o @@ -13,6 +15,7 @@ resolve_btfids-y += ctype.o resolve_btfids-y += str_error_r.o # The inner loops of --fmodret_scan +HOSTCFLAGS_fmodret_scan.o += -O2 HOSTCFLAGS_text_flow.o += -O2 # LLVM's C++ API may have moved on, see Makefile diff --git a/tools/bpf/resolve_btfids/fmodret.c b/tools/bpf/resolve_btfids/fmodret.c new file mode 100644 index 000000000000..8f43e92f32bf --- /dev/null +++ b/tools/bpf/resolve_btfids/fmodret.c @@ -0,0 +1,166 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Tag the functions which fmod_ret programs can attach to, because they return + * errors: "bpf_fmodret_retval:-22,-12". fmodret_scan.c finds the errors in the + * machine code. This file decides which functions it looks at, and which of the + * errors count. + * + * A function which no program can attach to gets no tag: ftrace has to find a nop + * at its entry, see scan_func(), and a BPF trampoline has to take its parameters. + */ + +#include +#include +#include +#include + +#include + +#include "fmodret.h" +#include "fmodret_scan.h" +#include "image.h" + +#define TAG "bpf_fmodret_retval:" + +/* Return the size of the integer which FUNC returns, or 0 */ +static __u32 int_return_size(const struct btf *btf, const struct btf_type *func) +{ + const struct btf_type *t = btf__type_by_id(btf, func->type); + int ret = t->type ? btf__resolve_type(btf, t->type) : -1; + + if (ret < 0) + return 0; + t = btf__type_by_id(btf, ret); + return btf_is_int(t) || btf_is_any_enum(t) ? t->size : 0; +} + +/* As btf_distill_func_proto(): at most 12 parameters of at most 16 bytes, and no "..." */ +static bool fits_trampoline(const struct btf *btf, const struct btf_type *func) +{ + const struct btf_type *t = btf__type_by_id(btf, func->type); + unsigned int i; + + for (i = 0; i < btf_vlen(t); i++) { + __u32 type = btf_params(t)[i].type; + + if (!type || btf__resolve_size(btf, type) > 16) + return false; + } + return btf_vlen(t) <= 12; +} + +/* + * The codes of include/linux/errno.h, 512 and up, never reach user space. They, + * -EAGAIN, -EMSGSIZE and -EINPROGRESS tell the caller to retry, to go on or to + * wait, not that the function failed. Their numbers are those of the kernel, in + * asm-generic/errno.h. The errno.h of the build host can have other numbers. + */ +static bool means_failure(int error) +{ + return error > -512 && error != -11 && error != -90 && error != -115; +} + +static int cmp_error(const void *va, const void *vb) +{ + return *(const int *)va - *(const int *)vb; +} + +/* + * Write the tag for a function which returns SIZE bytes, and in them one of the + * NR VALUES of the return value register. In 8 bytes an error is sign extended. + * Return false if there is nothing to tag. + * + * The machine code cannot tell the -EPERM of a permission check from the -1 of a + * comparator or of "no such index": a function whose only error is -1 has none. + */ +static bool format_tag(char *tag, const int64_t *values, size_t nr, __u32 size) +{ + size_t i, n = 0; + int errors[nr]; + + for (i = 0; i < nr; i++) { + int error = values[i]; + + if ((size == 4 || values[i] == error) && means_failure(error)) + errors[n++] = error; + } + qsort(errors, n, sizeof(*errors), cmp_error); + tag += sprintf(tag, TAG); + for (i = 0; i < n; i++) + if (!i || errors[i] != errors[i - 1]) + tag += sprintf(tag, "%s%d", i ? "," : "", errors[i]); + return n && errors[0] < -1; +} + +int fmodret_tag(Elf *elf, struct btf *btf, int verbose) +{ + size_t nr_funcs = 0, nr_scanned = 0, nr_undecodable = 0, nr_tags = 0; + const struct btf *base = btf__base_btf(btf); + __u32 id, nr_types = btf__type_cnt(btf); + struct scan *scan = NULL; + struct image img; + char counts[200]; + int err; + + err = image_open(&img, elf); + if (err) + goto out; + err = -EINVAL; + scan = scan_open(&img); + if (!scan) + goto out; + + for (id = base ? btf__type_cnt(base) : 1, err = 0; id < nr_types && err >= 0; id++) { + const struct btf_type *t = btf__type_by_id(btf, id); + const struct image_func *func; + const int64_t *values; + const char *name; + __u32 size; + + if (!btf_is_func(t)) + continue; + nr_funcs++; + size = int_return_size(btf, t); + if ((size != 4 && size != 8) || !fits_trampoline(btf, t)) + continue; + /* Init code is gone before a program can attach */ + name = btf__name_by_offset(btf, t->name_off); + func = image_func(&img, name); + if (!func || !strcmp(func->section, ".init.text")) + continue; + nr_scanned++; + err = scan_func(scan, func, &values); + if (err == -EINVAL) { + nr_undecodable++; + err = 0; + } + if (err > 0) { + char tag[sizeof(TAG) + 6 * err]; + + if (!format_tag(tag, values, err, size)) + continue; + if (verbose > 1) + fprintf(stderr, "fmodret: %s %s\n", name, tag + strlen(TAG)); + err = btf__add_decl_tag(btf, tag, id, -1); + nr_tags++; + } + } + snprintf(counts, sizeof(counts), + "%zu of %zu functions are tagged, %zu of the %zu which were scanned cannot be decoded", + nr_tags, nr_funcs, nr_undecodable, nr_scanned); + /* + * A function which cannot be decoded costs a target, not the build. But + * if the decoder is lost in the code of vmlinux, don't leave that to be + * found out by a program which does not load. + */ + if (err >= 0 && !base && (!nr_tags || nr_undecodable > nr_scanned / 100)) { + fprintf(stderr, "FAILED: --fmodret_scan: %s\n", counts); + err = -EINVAL; + } else if (!base || verbose) { + printf(" FMODRET %s\n", counts); + } +out: + scan_close(scan); + image_close(&img); + return err < 0 ? err : 0; +} diff --git a/tools/bpf/resolve_btfids/fmodret.h b/tools/bpf/resolve_btfids/fmodret.h new file mode 100644 index 000000000000..d61a9de026df --- /dev/null +++ b/tools/bpf/resolve_btfids/fmodret.h @@ -0,0 +1,12 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef __RESOLVE_BTFIDS_FMODRET_H +#define __RESOLVE_BTFIDS_FMODRET_H + +#include + +struct btf; + +/* Tag the functions of ELF which return errors in BTF */ +int fmodret_tag(Elf *elf, struct btf *btf, int verbose); + +#endif diff --git a/tools/bpf/resolve_btfids/fmodret_scan.c b/tools/bpf/resolve_btfids/fmodret_scan.c new file mode 100644 index 000000000000..6df10be92610 --- /dev/null +++ b/tools/bpf/resolve_btfids/fmodret_scan.c @@ -0,0 +1,219 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Find the errors which a function of an image returns, in the machine code: + * the constants -MAX_ERRNO..-1 which an instruction loads into a register and + * which copies may carry from there to the return value register at a return. + * + * This file brings the function into the form which the analysis in text_flow.c + * takes, and collects the results. + */ + +#include +#include +#include +#include + +#include + +#include "fmodret_scan.h" +#include "text_flow.h" + +#define MAX_ERRNO 4095 +#define MAX_SUBFUNCS 3 + +struct scan { + const struct image *img; + uint64_t return_thunk; + uint64_t entry_hook; + /* The function which is being looked at */ + struct text_flow flow; + size_t max_insns; + int64_t *values; + size_t nr_values, max_values; +}; + +/* Append the instructions of SIZE bytes at ADDR */ +static int decode(struct scan *s, uint64_t addr, uint64_t size) +{ + struct text_flow *flow = &s->flow; + const unsigned char *code; + uint64_t off; + size_t avail; + + code = image_bytes(s->img, addr, &avail); + if (!code || avail < size) + return -EINVAL; + for (off = 0; off < size; off += flow->insns[flow->nr_insns++].len) { + const struct image_reloc *reloc; + struct text_insn *insn; + + if (flow->nr_insns == s->max_insns) { + size_t max = s->max_insns ? 2 * s->max_insns : 1024; + struct text_facts *facts = realloc(flow->facts, max * sizeof(*facts)); + + if (!facts) + return -ENOMEM; + flow->facts = facts; + insn = realloc(flow->insns, max * sizeof(*insn)); + if (!insn) + return -ENOMEM; + flow->insns = insn; + s->max_insns = max; + } + insn = &flow->insns[flow->nr_insns]; + if (flow->arch->decode(code + off, size - off, addr + off, insn) < 0) + return -EINVAL; + insn->addr = addr + off; + + if (insn->kind < TEXT_BRANCH || !insn->imm) + continue; + /* The field is relative to its own address, and 0 in a relocatable file */ + reloc = image_reloc(s->img, insn->addr, insn->len); + if (reloc) + insn->imm += reloc->target - reloc->addr; + if (insn->kind == TEXT_BRANCH && insn->imm == s->return_thunk) + insn->kind = TEXT_RETURN; + /* ftrace makes it a nop when the kernel boots */ + if (insn->kind == TEXT_CALL && insn->imm == s->entry_hook) { + insn->kind = TEXT_OTHER; + insn->nop = true; + } + } + return 0; +} + +static int cmp_addr(const void *va, const void *vb) +{ + const struct image_func * const *a = va, * const *b = vb; + + return (*a)->addr > (*b)->addr ? 1 : (*a)->addr < (*b)->addr ? -1 : 0; +} + +/* + * Decode F and its cold subfunctions: compilers move unlikely blocks of F to a + * symbol of their own, F.cold or F.__part.1. By name they follow F. + */ +static int decode_func(struct scan *s, const struct image_func *f) +{ + const struct image_func *funcs[1 + MAX_SUBFUNCS] = { f }, *g; + const struct image_func *end = s->img->funcs + s->img->nr_funcs; + size_t len = strlen(f->name); + unsigned int nr = 1, i; + int err = 0; + + for (g = f + 1; g < end && !strncmp(g->name, f->name, len) && g->name[len] == '.'; g++) + if (nr <= MAX_SUBFUNCS && + (!strncmp(g->name + len, ".cold", 5) || !strncmp(g->name + len, ".__part.", 8))) + funcs[nr++] = g; + qsort(funcs, nr, sizeof(*funcs), cmp_addr); + s->flow.nr_insns = 0; + for (i = 0; !err && i < nr; i++) + err = decode(s, funcs[i]->addr, funcs[i]->size); + return err; +} + +/* + * ftrace, and with it a BPF trampoline, attaches to a function through the nop + * which the compiler leaves at ENTRY, or behind a landing pad: endbr64 and bti c + * have 4 bytes. + */ +static bool has_entry_nop(const struct text_flow *flow, uint64_t entry) +{ + u32 i; + + for (i = 0; i < flow->nr_insns; i++) + if (flow->insns[i].nop && flow->insns[i].addr - entry <= 4) + return true; + return false; +} + +/* The return value register may hold V */ +static int add_value(struct scan *s, int64_t v) +{ + size_t i; + + if ((int32_t)v < -MAX_ERRNO || (int32_t)v >= 0) + return 0; + for (i = 0; i < s->nr_values; i++) + if (s->values[i] == v) + return 0; + if (s->nr_values == s->max_values) { + size_t max = s->max_values ? 2 * s->max_values : 16; + int64_t *values = realloc(s->values, max * sizeof(*values)); + + if (!values) + return -ENOMEM; + s->values = values; + s->max_values = max; + } + s->values[s->nr_values++] = v; + return 0; +} + +int scan_func(struct scan *s, const struct image_func *f, const int64_t **values) +{ + const struct text_flow *flow = &s->flow; + int err = decode_func(s, f); + u32 i; + + if (err) + return err; + if (!has_entry_nop(flow, f->addr)) + return 0; + text_flow_solve(&s->flow); + + s->nr_values = 0; + for (i = 0; i < flow->nr_insns && !err; i++) { + const struct text_insn *insn = &flow->insns[i]; + uint64_t imm[2] = { insn->imm, insn->imm2 }; + struct text_facts out; + unsigned int n; + + if (insn->kind != TEXT_MOV_IMM && insn->kind != TEXT_SELECT_IMM) + continue; + out = text_flow_out(flow, i); + for (n = 0; n < 2 && !err; n++) { + if (out.same & BIT(insn->dst)) + err = add_value(s, imm[n]); + if (!err && out.zext & BIT(insn->dst)) + err = add_value(s, (uint32_t)imm[n]); + if (!err && out.sext & BIT(insn->dst)) + err = add_value(s, (int32_t)imm[n]); + } + } + *values = s->values; + return err ?: s->nr_values; +} + +struct scan *scan_open(const struct image *img) +{ + struct scan *s = calloc(1, sizeof(*s)); + GElf_Ehdr ehdr; + + if (!s || !gelf_getehdr(img->elf, &ehdr)) + goto err; + s->flow.arch = text_arch_init(ehdr.e_machine); + if (!s->flow.arch) { + fprintf(stderr, "FAILED: no decoder for the code of ELF machine %u\n", ehdr.e_machine); + goto err; + } + s->img = img; + if (s->flow.arch->return_thunk) + s->return_thunk = image_symbol(img, s->flow.arch->return_thunk); + if (s->flow.arch->entry_hook) + s->entry_hook = image_symbol(img, s->flow.arch->entry_hook); + return s; +err: + free(s); + return NULL; +} + +void scan_close(struct scan *s) +{ + if (!s) + return; + free(s->flow.insns); + free(s->flow.facts); + free(s->values); + free(s); +} diff --git a/tools/bpf/resolve_btfids/fmodret_scan.h b/tools/bpf/resolve_btfids/fmodret_scan.h new file mode 100644 index 000000000000..ef3b4ed4d189 --- /dev/null +++ b/tools/bpf/resolve_btfids/fmodret_scan.h @@ -0,0 +1,22 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +#ifndef __RESOLVE_BTFIDS_FMODRET_SCAN_H +#define __RESOLVE_BTFIDS_FMODRET_SCAN_H + +#include + +#include "image.h" + +struct scan; + +/* Return NULL, after a message, if the code of IMG cannot be read */ +struct scan *scan_open(const struct image *img); +void scan_close(struct scan *scan); +/* + * Find the constants which FUNC returns and whose low 32 bits are an error. Set + * VALUES to what the return value register holds then, until the next call. + * A function which ftrace cannot patch has none: no program can attach to it. + * Return how many there are, or -EINVAL if the code cannot be decoded. + */ +int scan_func(struct scan *scan, const struct image_func *func, const int64_t **values); + +#endif diff --git a/tools/bpf/resolve_btfids/main.c b/tools/bpf/resolve_btfids/main.c index c16dd93fa6d4..0ac895222a14 100644 --- a/tools/bpf/resolve_btfids/main.c +++ b/tools/bpf/resolve_btfids/main.c @@ -69,6 +69,10 @@ * - rewrites the prototype of KF_IMPLICIT_ARGS kfuncs. * * These kfunc annotations were historically produced by pahole. + * + * With --fmodret_scan it also reads the machine code, and emits a + * "bpf_fmodret_retval:" decl tag for each function which returns errors, + * see fmodret.c. */ #define _GNU_SOURCE @@ -90,6 +94,7 @@ #include #include #include "btf_colors.h" +#include "fmodret.h" #include #define BTF_IDS_SECTION ".BTF_ids" @@ -2098,6 +2103,7 @@ int main(int argc, const char **argv) struct btf_links btf_links = {}; bool fatal_warnings = false; bool resolve_btfids = true; + bool fmodret_scan = false; char out_path[PATH_MAX]; struct option btfid_options[] = { @@ -2113,6 +2119,8 @@ int main(int argc, const char **argv) "distill --btf_base and emit .BTF.base section data"), OPT_BOOLEAN(0, "inline", &obj.extract_inline, "extract location BTF into a .BTF.inline file"), + OPT_BOOLEAN(0, "fmodret_scan", &fmodret_scan, + "tag the functions which return errors as fmod_ret targets"), OPT_CALLBACK(0, "btf_link", &btf_links, "section:module:btf-file", "patch a BTF link with --patch_btfids", parse_btf_link), OPT_STRING(0, "patch_btfids", &btfids_path, "file", @@ -2174,6 +2182,9 @@ int main(int argc, const char **argv) if (btf2btf(&obj)) goto out; + if (fmodret_scan && fmodret_tag(obj.efile.elf, obj.btf, verbose)) + goto out; + if (finalize_btf(&obj)) goto out; diff --git a/tools/bpf/resolve_btfids/text_insn.h b/tools/bpf/resolve_btfids/text_insn.h index 210d749439e7..0ead445f5442 100644 --- a/tools/bpf/resolve_btfids/text_insn.h +++ b/tools/bpf/resolve_btfids/text_insn.h @@ -38,6 +38,7 @@ struct text_insn { u8 len; u8 dst, src, src2; bool is32; /* It works on the low 32 bits and zero extends the result */ + bool nop; /* It does nothing */ /* The registers which it writes, but for dst */ u32 defs; u64 imm, imm2; @@ -51,6 +52,11 @@ struct text_arch { u32 caller_saved; /* the registers which a call may write */ /* A branch to this symbol is a return */ const char *return_thunk; + /* + * The build may leave a call of this symbol where ftrace patches a nop, at + * the entry of a function. It writes no register. + */ + const char *entry_hook; /* * Describe the instruction at ADDR, whose bytes are at CODE. At most LEN * bytes can be read. Return a negative value if it is not an instruction. diff --git a/tools/bpf/resolve_btfids/text_mc.cpp b/tools/bpf/resolve_btfids/text_mc.cpp index e7166ad4b871..cb57f9db9f9d 100644 --- a/tools/bpf/resolve_btfids/text_mc.cpp +++ b/tools/bpf/resolve_btfids/text_mc.cpp @@ -61,6 +61,7 @@ struct Opcode { u32 implicit_defs = 0; unsigned int implicit_def = 0, implicit_use = 0; /* the first ones, LLVM registers */ bool unmodeled = false, is_return = false; + const mc_pattern *nop = nullptr; std::vector patterns; }; @@ -198,6 +199,8 @@ bool read_opcodes() } else { it->second->unmodeled = false; it->second->implicit_defs |= pattern->defs; + if (pattern->nop) + it->second->nop = pattern; } } return ok; @@ -340,6 +343,7 @@ int decode(const void *code, unsigned int len, u64 addr, text_insn *ti) const Opcode &o = d.opcodes[inst.getOpcode()]; + ti->nop = o.nop && holds(inst, o.nop->predicates[0]); ti->defs = defs_of(inst, o); for (const mc_pattern *pattern : o.patterns) { if (match(inst, o, *pattern, ti)) { @@ -353,6 +357,7 @@ int decode(const void *code, unsigned int len, u64 addr, text_insn *ti) void print(raw_ostream &os, const text_insn &ti) { + os << "nop " << ti.nop << " "; os << "kind " << (int)ti.kind << " is32 " << ti.is32 << " dst " << (int)ti.dst << " src " << (int)ti.src << " src2 " << (int)ti.src2 << " defs " << format_hex(ti.defs, 1) << " imm " << format_hex(ti.imm, 1) @@ -373,6 +378,7 @@ bool run_tests() while (in >> std::hex >> byte) code.push_back(byte); if (!decode(code.data(), code.size(), MC_TEST_ADDR, &ti) && ti.len == code.size() && + ti.nop == want.nop && ti.kind == want.kind && ti.is32 == want.is32 && ti.dst == want.dst && ti.src == want.src && ti.src2 == want.src2 && ti.defs == want.defs && ti.imm == want.imm && ti.imm2 == want.imm2) diff --git a/tools/bpf/resolve_btfids/text_mc.h b/tools/bpf/resolve_btfids/text_mc.h index 9d39095aab20..8eef0860aa1c 100644 --- a/tools/bpf/resolve_btfids/text_mc.h +++ b/tools/bpf/resolve_btfids/text_mc.h @@ -48,6 +48,7 @@ struct mc_predicate { * how LLVM says that MCInstrDesc does not tell all about an opcode: it writes * TEXT_ALL_REGS, unless such a pattern says that it writes what MCInstrDesc * has, and DEFS. + * With NOP the instruction is a nop if the first predicate holds. * * A pattern of kind TEXT_RETURN names a return to the caller. isReturn() holds * for a return from an exception as well, which does not hand the return value @@ -68,6 +69,7 @@ struct mc_pattern { bool fixed; /* the immediate is VALUE, not an operand */ s64 value; u32 defs; /* of TEXT_OTHER */ + bool nop; /* of TEXT_OTHER */ struct mc_predicate predicates[2]; }; diff --git a/tools/bpf/resolve_btfids/text_mc_arm64.c b/tools/bpf/resolve_btfids/text_mc_arm64.c index 9cc44281242b..546a9d319126 100644 --- a/tools/bpf/resolve_btfids/text_mc_arm64.c +++ b/tools/bpf/resolve_btfids/text_mc_arm64.c @@ -24,6 +24,7 @@ static const struct mc_pattern arm64_patterns[] = { { "ANDWrs", TEXT_SELECT, .src = 1, .src2 = 1, .predicates = { IMM(3, 2 << 6 | 31) } }, /* HINT: nop, bti, yield, wfe ... */ { "HINT", TEXT_OTHER }, { "AUTIASP", TEXT_OTHER }, { "PRFMui", TEXT_OTHER }, + { "HINT", TEXT_OTHER, .nop = true, .predicates = { IMM(0, 0) } }, /* nop */ { "DMB", TEXT_OTHER }, { "MRS", TEXT_OTHER }, { "MSR", TEXT_OTHER }, { "STLRB", TEXT_OTHER }, { "STLRW", TEXT_OTHER }, WX("LDXR", "", TEXT_OTHER), WX("STXR", "", TEXT_OTHER), WX("STLXR", "", TEXT_OTHER), @@ -56,6 +57,7 @@ static const struct mc_test arm64_tests[] = { T("00 05 89 1a", TEXT_SELECT, .is32 = true, SRC(8)), /* csinc w0, w8, w9, eq */ T("00 7d 89 0a", TEXT_SELECT, .is32 = true, SRC(8)), /* and w0, w8, w9, asr #31 */ T("00 01 09 0a", TEXT_OTHER, .defs = BIT(0)), /* and w0, w8, w9 */ + T("1f 20 03 d5", TEXT_OTHER, .nop = true), /* nop */ T("5f 24 03 d5", TEXT_OTHER), /* bti c */ T("bf 23 03 d5", TEXT_OTHER, .defs = BIT(30)), /* autiasp */ T("20 00 80 f9", TEXT_OTHER), /* prfm pldl1keep, [x1] */ diff --git a/tools/bpf/resolve_btfids/text_mc_x86.c b/tools/bpf/resolve_btfids/text_mc_x86.c index 11223cd1c077..d907fac001c8 100644 --- a/tools/bpf/resolve_btfids/text_mc_x86.c +++ b/tools/bpf/resolve_btfids/text_mc_x86.c @@ -27,6 +27,7 @@ static const struct mc_pattern x86_patterns[] = { { "SBB64rr", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { SAME_REG(1, 2) } }, { "SAR32ri", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { IMM(2, 31) } }, { "LOCK_PREFIX", TEXT_OTHER }, + { "NOOPL", TEXT_OTHER, .nop = true }, /* A rep prefix is not a part of the MCInst */ { "STOSQ", TEXT_OTHER, .defs = BIT(RCX) }, { "RET64", TEXT_RETURN }, @@ -58,6 +59,7 @@ static const struct mc_test x86_tests[] = { T("0f 44 c3", TEXT_SELECT, .is32 = true, .src = RBX, .src2 = RAX), /* cmove %ebx, %eax */ T("48 0f 44 c3", TEXT_SELECT, .src = RBX, .src2 = RAX), /* cmove %rbx, %rax */ T("f0", TEXT_OTHER), /* lock */ + T("0f 1f 44 00 00", TEXT_OTHER, .nop = true), /* nopl 0x0(%rax,%rax,1) */ T("f3 48 ab", TEXT_OTHER, .defs = BIT(RCX) | BIT(RDI)), /* rep stosq */ /* hasUnmodeledSideEffects() */ T("f3 48 a5", TEXT_OTHER, .defs = TEXT_ALL_REGS), /* rep movsq */ @@ -107,6 +109,7 @@ const struct mc_arch mc_arch = { .caller_saved = BIT(RAX) | BIT(RCX) | BIT(RDX) | BIT(RSI) | BIT(RDI) | BIT(R8) | BIT(R9) | BIT(R10) | BIT(R11), .return_thunk = "__x86_return_thunk", + .entry_hook = "__fentry__", }, .machine = EM_X86_64, .triple = "x86_64-unknown-linux-gnu", -- 2.55.0 From: Alexei Starovoitov return copy_to_user(to, from, n) ? -EFAULT : 0; GCC for x86-64 never loads -14 into a register here: neg %rax sbb %eax,%eax 0 or -1 and $0xfffffff2,%eax 0 or -14 ret So the function gets no tag. Other forms of the same select: one of two errors sbb; and; sub the condition is negated sbb; not; and The table of x86-64 describes "sbb %eax,%eax" as a definition with two constants, 0 and -1. Describe "dst = src op imm" in text_insn.h as TEXT_ALU_IMM. text_flow_fold() runs before the analysis. It computes the instruction if src still holds the constants of an earlier instruction, and the code falls through from there. The result is again a definition with two constants. Five patterns of x86-64 use it: "and" and "sub" of a short immediate, in 32 and in 64 bits, and "not". functions tagged before after x86-64 GCC 12076 12256 x86-64 clang 12994 13002 arm64 clang 11837 11837 Signed-off-by: Alexei Starovoitov Acked-by: Anton Protopopov --- tools/bpf/resolve_btfids/fmodret_scan.c | 1 + tools/bpf/resolve_btfids/text_flow.c | 49 +++++++++++++++++++++++++ tools/bpf/resolve_btfids/text_flow.h | 6 +++ tools/bpf/resolve_btfids/text_insn.h | 8 ++++ tools/bpf/resolve_btfids/text_mc.cpp | 3 ++ tools/bpf/resolve_btfids/text_mc.h | 1 + tools/bpf/resolve_btfids/text_mc_x86.c | 10 +++++ 7 files changed, 78 insertions(+) diff --git a/tools/bpf/resolve_btfids/fmodret_scan.c b/tools/bpf/resolve_btfids/fmodret_scan.c index 6df10be92610..5b5eb8cb414b 100644 --- a/tools/bpf/resolve_btfids/fmodret_scan.c +++ b/tools/bpf/resolve_btfids/fmodret_scan.c @@ -160,6 +160,7 @@ int scan_func(struct scan *s, const struct image_func *f, const int64_t **values return err; if (!has_entry_nop(flow, f->addr)) return 0; + text_flow_fold(&s->flow); text_flow_solve(&s->flow); s->nr_values = 0; diff --git a/tools/bpf/resolve_btfids/text_flow.c b/tools/bpf/resolve_btfids/text_flow.c index 2d58ffb2e939..3fe2c75eb2fc 100644 --- a/tools/bpf/resolve_btfids/text_flow.c +++ b/tools/bpf/resolve_btfids/text_flow.c @@ -16,6 +16,54 @@ static u32 next_insn(const struct text_flow *flow, u32 i) i + 1 : TEXT_NO_INSN; } +static u64 alu(const struct text_insn *insn, u64 v) +{ + switch (insn->op) { + case TEXT_AND: + v &= insn->imm; + break; + case TEXT_XOR: + v ^= insn->imm; + break; + case TEXT_SUB: + v -= insn->imm; + break; + } + return insn->is32 ? (u32)v : v; +} + +void text_flow_fold(struct text_flow *flow) +{ + /* The instruction which has left a constant in each register */ + u32 def[TEXT_MAX_REGS], i, r; + + for (i = 0; i < flow->nr_insns; i++) { + struct text_insn *insn = &flow->insns[i]; + u32 defs = insn->defs; + + /* The function or a cold subfunction begins */ + if (!i || next_insn(flow, i - 1) == TEXT_NO_INSN) + for (r = 0; r < TEXT_MAX_REGS; r++) + def[r] = TEXT_NO_INSN; + if (insn->kind == TEXT_ALU_IMM && def[insn->src] != TEXT_NO_INSN) { + insn->kind = TEXT_MOV_IMM; + insn->imm2 = alu(insn, flow->insns[def[insn->src]].imm2); + insn->imm = alu(insn, flow->insns[def[insn->src]].imm); + } + if (insn->kind == TEXT_BRANCH || insn->kind == TEXT_RETURN) + defs = TEXT_ALL_REGS; + else if (insn->kind == TEXT_CALL) + defs |= flow->arch->caller_saved; + else if (insn->kind != TEXT_OTHER && insn->kind != TEXT_COND_BRANCH) + defs |= BIT(insn->dst); + for (r = 0; defs && r < TEXT_MAX_REGS; r++) + if (defs & BIT(r)) + def[r] = TEXT_NO_INSN; + if (insn->kind == TEXT_MOV_IMM) + def[insn->dst] = i; + } +} + static u32 insn_at(const struct text_flow *flow, u64 addr) { u32 lo = 0, hi = flow->nr_insns; @@ -90,6 +138,7 @@ static struct text_facts transfer(const struct text_flow *flow, u32 i) kill(&in, flow->arch->caller_saved); break; case TEXT_MOV_IMM: + case TEXT_ALU_IMM: kill(&in, BIT(insn->dst)); break; case TEXT_MOV: diff --git a/tools/bpf/resolve_btfids/text_flow.h b/tools/bpf/resolve_btfids/text_flow.h index b307c08fd163..a266419400f9 100644 --- a/tools/bpf/resolve_btfids/text_flow.h +++ b/tools/bpf/resolve_btfids/text_flow.h @@ -36,6 +36,12 @@ struct text_flow { struct text_facts *facts; }; +/* + * Fold constants: "dst = imm or imm2" and a later "dst = src op imm" in the same + * straight line of code give "dst = imm' or imm2'". Compilers select one of two + * constants without a branch in this way. + */ +void text_flow_fold(struct text_flow *flow); /* Compute the facts */ void text_flow_solve(struct text_flow *flow); /* Return the facts behind instruction I, which is not a branch */ diff --git a/tools/bpf/resolve_btfids/text_insn.h b/tools/bpf/resolve_btfids/text_insn.h index 0ead445f5442..a79a4c9a86d5 100644 --- a/tools/bpf/resolve_btfids/text_insn.h +++ b/tools/bpf/resolve_btfids/text_insn.h @@ -18,6 +18,7 @@ enum text_insn_kind { TEXT_OTHER, TEXT_MOV_IMM, /* dst = imm or imm2 */ + TEXT_ALU_IMM, /* dst = src op imm */ TEXT_MOV, /* dst = src */ TEXT_SEXT32, /* dst = (s32)src */ TEXT_SELECT, /* dst = src or src2 */ @@ -28,6 +29,12 @@ enum text_insn_kind { TEXT_RETURN, }; +enum text_alu_op { + TEXT_AND, + TEXT_XOR, + TEXT_SUB, +}; + /* The arch numbers its registers */ #define TEXT_MAX_REGS 32 #define TEXT_ALL_REGS (~0U) @@ -37,6 +44,7 @@ struct text_insn { u8 kind; u8 len; u8 dst, src, src2; + u8 op; /* of TEXT_ALU_IMM */ bool is32; /* It works on the low 32 bits and zero extends the result */ bool nop; /* It does nothing */ /* The registers which it writes, but for dst */ diff --git a/tools/bpf/resolve_btfids/text_mc.cpp b/tools/bpf/resolve_btfids/text_mc.cpp index cb57f9db9f9d..ddf9e33ee5a0 100644 --- a/tools/bpf/resolve_btfids/text_mc.cpp +++ b/tools/bpf/resolve_btfids/text_mc.cpp @@ -284,6 +284,7 @@ bool match(const MCInst &inst, const Opcode &o, const mc_pattern &pattern, text_ ti->dst = dst.nr; ti->src = src; ti->src2 = src2; + ti->op = pattern.op; ti->imm = imm; ti->imm2 = pattern.or_zero ? 0 : imm; return true; @@ -360,6 +361,7 @@ void print(raw_ostream &os, const text_insn &ti) os << "nop " << ti.nop << " "; os << "kind " << (int)ti.kind << " is32 " << ti.is32 << " dst " << (int)ti.dst << " src " << (int)ti.src << " src2 " << (int)ti.src2 + << " op " << (int)ti.op << " defs " << format_hex(ti.defs, 1) << " imm " << format_hex(ti.imm, 1) << " imm2 " << format_hex(ti.imm2, 1); } @@ -381,6 +383,7 @@ bool run_tests() ti.nop == want.nop && ti.kind == want.kind && ti.is32 == want.is32 && ti.dst == want.dst && ti.src == want.src && ti.src2 == want.src2 && + ti.op == want.op && ti.defs == want.defs && ti.imm == want.imm && ti.imm2 == want.imm2) continue; print(error() << test->code << " is " << d.MII->getName(d.inst.getOpcode()) << ", length " diff --git a/tools/bpf/resolve_btfids/text_mc.h b/tools/bpf/resolve_btfids/text_mc.h index 8eef0860aa1c..70fe54595d60 100644 --- a/tools/bpf/resolve_btfids/text_mc.h +++ b/tools/bpf/resolve_btfids/text_mc.h @@ -64,6 +64,7 @@ struct mc_pattern { u8 dst, src, src2; /* the numbers of the operands. DST is 0 unless it is given */ u8 imm; /* the operand with the immediate */ u8 shift; /* the operand which says how far the immediate is shifted left */ + u8 op; /* of TEXT_ALU_IMM */ bool invert; /* the immediate */ bool or_zero; /* TEXT_MOV_IMM: the immediate or 0 */ bool fixed; /* the immediate is VALUE, not an operand */ diff --git a/tools/bpf/resolve_btfids/text_mc_x86.c b/tools/bpf/resolve_btfids/text_mc_x86.c index d907fac001c8..2773f35bfc12 100644 --- a/tools/bpf/resolve_btfids/text_mc_x86.c +++ b/tools/bpf/resolve_btfids/text_mc_x86.c @@ -26,6 +26,11 @@ static const struct mc_pattern x86_patterns[] = { { "SBB32rr", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { SAME_REG(1, 2) } }, { "SBB64rr", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { SAME_REG(1, 2) } }, { "SAR32ri", TEXT_MOV_IMM, VALUE(-1), .or_zero = true, .predicates = { IMM(2, 31) } }, + { "AND32ri8", TEXT_ALU_IMM, .src = 1, .imm = 2, .op = TEXT_AND }, + { "AND64ri8", TEXT_ALU_IMM, .src = 1, .imm = 2, .op = TEXT_AND }, + { "SUB32ri8", TEXT_ALU_IMM, .src = 1, .imm = 2, .op = TEXT_SUB }, + { "SUB64ri8", TEXT_ALU_IMM, .src = 1, .imm = 2, .op = TEXT_SUB }, + { "NOT32r", TEXT_ALU_IMM, .src = 1, .op = TEXT_XOR, VALUE(-1) }, { "LOCK_PREFIX", TEXT_OTHER }, { "NOOPL", TEXT_OTHER, .nop = true }, /* A rep prefix is not a part of the MCInst */ @@ -58,6 +63,11 @@ static const struct mc_test x86_tests[] = { T("48 98", TEXT_SEXT32, SRC(RAX)), /* cltq */ T("0f 44 c3", TEXT_SELECT, .is32 = true, .src = RBX, .src2 = RAX), /* cmove %ebx, %eax */ T("48 0f 44 c3", TEXT_SELECT, .src = RBX, .src2 = RAX), /* cmove %rbx, %rax */ + T("83 e3 f2", TEXT_ALU_IMM, .is32 = true, .dst = RBX, SRC(RBX), .op = TEXT_AND, IMMS(0xfffffff2, 0xfffffff2)), /* and $-14, %ebx */ + T("48 83 e3 f2", TEXT_ALU_IMM, .dst = RBX, SRC(RBX), .op = TEXT_AND, IMMS(-14, -14)), /* and $-14, %rbx */ + T("83 eb 0e", TEXT_ALU_IMM, .is32 = true, .dst = RBX, SRC(RBX), .op = TEXT_SUB, IMMS(14, 14)), /* sub $14, %ebx */ + T("48 83 eb 0e", TEXT_ALU_IMM, .dst = RBX, SRC(RBX), .op = TEXT_SUB, IMMS(14, 14)), /* sub $14, %rbx */ + T("f7 d0", TEXT_ALU_IMM, .is32 = true, .op = TEXT_XOR, IMMS(0xffffffff, 0xffffffff)), /* not %eax */ T("f0", TEXT_OTHER), /* lock */ T("0f 1f 44 00 00", TEXT_OTHER, .nop = true), /* nopl 0x0(%rax,%rax,1) */ T("f3 48 ab", TEXT_OTHER, .defs = BIT(RCX) | BIT(RDI)), /* rep stosq */ -- 2.55.0 From: Alexei Starovoitov Ebusy: spin_unlock(&files->file_lock); return -EBUSY; mov %rdi,%r13 files, the first argument ... lea 0xc0(%r13),%rdi &files->file_lock call _raw_spin_unlock mov $0xfffffff0,%eax do_dup2() unlocks an object of its caller before it returns the error. The next patch looks for that in the machine code: is the pointer in %rdi computed from an argument of do_dup2()? The decoder says which registers an instruction writes. It does not say from what. text_insn.uses the registers that the instruction reads: the operands behind the defs of MCInstrDesc, and its implicit uses text_insn.load it reads memory: MCInstrDesc::mayLoad() lea 0xc0(%r13),%rdi uses r13: a pointer into *files mov 0xc0(%r13),%rdi uses r13, load: another object An opcode with hasUnmodeledSideEffects() reads all registers, as it writes all registers. For LLVM "xor %edi,%edi" reads %edi. Compilers pass NULL in this way. The table of x86-64 gets a pattern for it: dst = 0. A test instruction says what is read only if that is its point: four for x86-64, three for arm64. No tag changes. Signed-off-by: Alexei Starovoitov Acked-by: Anton Protopopov --- tools/bpf/resolve_btfids/text_insn.h | 3 +++ tools/bpf/resolve_btfids/text_mc.cpp | 22 ++++++++++++++++++++++ tools/bpf/resolve_btfids/text_mc.h | 1 + tools/bpf/resolve_btfids/text_mc_arm64.c | 4 ++++ tools/bpf/resolve_btfids/text_mc_x86.c | 7 +++++++ 5 files changed, 37 insertions(+) diff --git a/tools/bpf/resolve_btfids/text_insn.h b/tools/bpf/resolve_btfids/text_insn.h index a79a4c9a86d5..5c3ba3a54856 100644 --- a/tools/bpf/resolve_btfids/text_insn.h +++ b/tools/bpf/resolve_btfids/text_insn.h @@ -49,6 +49,9 @@ struct text_insn { bool nop; /* It does nothing */ /* The registers which it writes, but for dst */ u32 defs; + /* The registers which it reads. TEXT_ALL_REGS if the decoder does not know it */ + u32 uses; + bool load; /* It reads memory */ u64 imm, imm2; /* For the user of the decoder */ u64 addr; diff --git a/tools/bpf/resolve_btfids/text_mc.cpp b/tools/bpf/resolve_btfids/text_mc.cpp index ddf9e33ee5a0..57f45a4bed6f 100644 --- a/tools/bpf/resolve_btfids/text_mc.cpp +++ b/tools/bpf/resolve_btfids/text_mc.cpp @@ -7,6 +7,8 @@ * branch, call MCInstrAnalysis, which asks MCInstrDesc * target MCInstrAnalysis::evaluateBranch() * registers written MCInstrDesc: defs, implicit defs + * registers read MCInstrDesc: the other operands, implicit uses + * load MCInstrDesc::mayLoad() * eax and rax, w0 and x0 MCRegAliasIterator * * Whatever MC does not describe completely writes TEXT_ALL_REGS. @@ -59,6 +61,7 @@ struct Reg { /* What is known about an opcode before its operands are */ struct Opcode { u32 implicit_defs = 0; + u32 implicit_uses = 0; unsigned int implicit_def = 0, implicit_use = 0; /* the first ones, LLVM registers */ bool unmodeled = false, is_return = false; const mc_pattern *nop = nullptr; @@ -182,6 +185,8 @@ bool read_opcodes() for (MCPhysReg r : desc.implicit_uses()) if (!o.implicit_use && d.regs[r].mask) o.implicit_use = r; + for (MCPhysReg r : desc.implicit_uses()) + o.implicit_uses |= d.regs[r].mask; /* defs_of() does not look for the last two */ o.unmodeled = desc.hasUnmodeledSideEffects() || desc.hasOptionalDef() || desc.variadicOpsAreDefs(); @@ -329,6 +334,19 @@ u32 defs_of(const MCInst &inst, const Opcode &o) return defs; } +/* Return the registers which INST reads */ +u32 uses_of(const MCInst &inst, const Opcode &o) +{ + u32 uses = o.implicit_uses; + + if (o.unmodeled) + return TEXT_ALL_REGS; + for (unsigned int i = d.MII->get(inst.getOpcode()).getNumDefs(); i < inst.getNumOperands(); i++) + if (inst.getOperand(i).isReg()) + uses |= d.regs[inst.getOperand(i).getReg()].mask; + return uses; +} + int decode(const void *code, unsigned int len, u64 addr, text_insn *ti) { MCInst &inst = d.inst; @@ -346,6 +364,8 @@ int decode(const void *code, unsigned int len, u64 addr, text_insn *ti) ti->nop = o.nop && holds(inst, o.nop->predicates[0]); ti->defs = defs_of(inst, o); + ti->uses = uses_of(inst, o); + ti->load = d.MII->get(inst.getOpcode()).mayLoad(); for (const mc_pattern *pattern : o.patterns) { if (match(inst, o, *pattern, ti)) { ti->defs &= ~(1U << ti->dst); @@ -364,6 +384,7 @@ void print(raw_ostream &os, const text_insn &ti) << " op " << (int)ti.op << " defs " << format_hex(ti.defs, 1) << " imm " << format_hex(ti.imm, 1) << " imm2 " << format_hex(ti.imm2, 1); + os << " uses " << format_hex(ti.uses, 1) << " load " << ti.load; } bool run_tests() @@ -384,6 +405,7 @@ bool run_tests() ti.kind == want.kind && ti.is32 == want.is32 && ti.dst == want.dst && ti.src == want.src && ti.src2 == want.src2 && ti.op == want.op && + (!want.uses || (ti.uses == want.uses && ti.load == want.load)) && ti.defs == want.defs && ti.imm == want.imm && ti.imm2 == want.imm2) continue; print(error() << test->code << " is " << d.MII->getName(d.inst.getOpcode()) << ", length " diff --git a/tools/bpf/resolve_btfids/text_mc.h b/tools/bpf/resolve_btfids/text_mc.h index 70fe54595d60..f2add1f45f4f 100644 --- a/tools/bpf/resolve_btfids/text_mc.h +++ b/tools/bpf/resolve_btfids/text_mc.h @@ -77,6 +77,7 @@ struct mc_pattern { /* An instruction, in hex, and what text_arch.decode() has to say about it at MC_TEST_ADDR */ struct mc_test { const char *code; + /* uses and load are compared only if uses is set */ struct text_insn insn; }; diff --git a/tools/bpf/resolve_btfids/text_mc_arm64.c b/tools/bpf/resolve_btfids/text_mc_arm64.c index 546a9d319126..c2576473773e 100644 --- a/tools/bpf/resolve_btfids/text_mc_arm64.c +++ b/tools/bpf/resolve_btfids/text_mc_arm64.c @@ -90,6 +90,10 @@ static const struct mc_test arm64_tests[] = { T("20 c0 5f b8", TEXT_OTHER, .defs = BIT(0)), /* ldur w0, [x1, #-4] */ T("20 c0 9f b8", TEXT_OTHER, .defs = BIT(0)), /* ldursw x0, [x1, #-4] */ T("08 09 40 b8", TEXT_OTHER, .defs = BIT(8)), /* ldtr w8, [x8] */ + /* What is read */ + T("20 00 01 91", TEXT_OTHER, .defs = BIT(0), .uses = BIT(1)), /* add x0, x1, #0x40 */ + T("20 20 40 f9", TEXT_OTHER, .defs = BIT(0), .uses = BIT(1), .load = true), /* ldr x0, [x1, #0x40] */ + T("20 00 00 b9", TEXT_OTHER, .uses = BIT(0) | BIT(1)), /* str w0, [x1] */ /* The control flow */ T("10 00 00 14", TEXT_BRANCH, .imm = MC_TEST_ADDR + 0x40), /* b */ T("00 01 1f d6", TEXT_BRANCH), /* br x8 */ diff --git a/tools/bpf/resolve_btfids/text_mc_x86.c b/tools/bpf/resolve_btfids/text_mc_x86.c index 2773f35bfc12..d8d48b0f68fe 100644 --- a/tools/bpf/resolve_btfids/text_mc_x86.c +++ b/tools/bpf/resolve_btfids/text_mc_x86.c @@ -16,6 +16,7 @@ static const struct mc_pattern x86_patterns[] = { { "MOV64ri32", TEXT_MOV_IMM, .imm = 1 }, { "OR32ri8", TEXT_MOV_IMM, .imm = 2, .predicates = { IMM(2, -1) } }, { "OR64ri8", TEXT_MOV_IMM, .imm = 2, .predicates = { IMM(2, -1) } }, + { "XOR32rr", TEXT_MOV_IMM, VALUE(0), .predicates = { SAME_REG(1, 2) } }, { "MOV32rr", TEXT_MOV, .src = 1 }, { "MOV64rr", TEXT_MOV, .src = 1 }, { "MOVSX64rr32", TEXT_SEXT32, .src = 1 }, @@ -51,6 +52,7 @@ static const struct mc_test x86_tests[] = { T("48 83 c8 ff", TEXT_MOV_IMM, IMMS(-1, -1)), /* or $-1, %rax */ T("83 c8 f0", TEXT_OTHER, .defs = BIT(RAX)), /* or $-16, %eax */ T("48 83 c8 f0", TEXT_OTHER, .defs = BIT(RAX)), /* or $-16, %rax */ + T("31 c0", TEXT_MOV_IMM, .is32 = true), /* xor %eax, %eax */ T("19 c0", TEXT_MOV_IMM, .is32 = true, IMMS(0xffffffff, 0)), /* sbb %eax, %eax */ T("48 19 c0", TEXT_MOV_IMM, IMMS(-1, 0)), /* sbb %rax, %rax */ T("19 d8", TEXT_OTHER, .defs = BIT(RAX)), /* sbb %ebx, %eax */ @@ -103,6 +105,11 @@ static const struct mc_test x86_tests[] = { T("48 0f bd c3", TEXT_OTHER, .defs = BIT(RAX)), /* bsr %rbx, %rax */ T("80 e3 01", TEXT_OTHER, .defs = BIT(RBX)), /* and $1, %bl */ T("48 0f c1 13", TEXT_OTHER, .defs = BIT(RDX)), /* xadd %rdx, (%rbx) */ + /* What is read */ + T("48 8d 47 40", TEXT_OTHER, .defs = BIT(RAX), .uses = BIT(RDI)), /* lea 0x40(%rdi), %rax */ + T("48 8b 47 40", TEXT_OTHER, .defs = BIT(RAX), .uses = BIT(RDI), .load = true), /* mov 0x40(%rdi), %rax */ + T("89 04 cb", TEXT_OTHER, .uses = BIT(RAX) | BIT(RBX) | BIT(RCX)), /* mov %eax, (%rbx,%rcx,8) */ + T("50", TEXT_OTHER, .defs = BIT(RSP), .uses = BIT(RAX) | BIT(RSP)), /* push %rax */ /* The control flow */ T("eb 10", TEXT_BRANCH, .imm = MC_TEST_ADDR + 0x12), /* jmp */ T("ff e0", TEXT_BRANCH), /* jmp *%rax */ -- 2.55.0 From: Alexei Starovoitov A program that returns an error skips f(). A skip of f() is not a failure of f(). ksys_dup3() takes the lock and ends with "return do_dup2(..)": static int do_dup2(..) __releases(&files->file_lock) .. Ebusy: spin_unlock(&files->file_lock); return -EBUSY; do_dup2() fails dup2() = -EBUSY, the lock is free do_dup2() is skipped dup2() = -EBUSY, the lock stays held A caller can rely on what f() does on each path to "return e". The rule: An error is not in the list if, on each path from the entry to its return, f() hands a pointer that is based on one of its pointer arguments to a callee that returns void. A callee that returns void cannot fail: what it does to the object is done when f() returns the error. Most unlock, put, free and init functions return void. BTF says so, no name is needed. A callee that returns a value may have failed. "Based on": computed without a load, as &arg->lock is. BTF gives the parameters, the code has registers. Registers are counted as in bpf_jit_place_args(): a bpfptr_t takes two. The count stops at a parameter of more than 16 bytes and at a packed struct. forward, may the registers that hold a based pointer. A call that hands one to a void callee is an effect. Does a path without an effect lead from the entry to here? backward, may the analysis that is there. It stops at an effect f() stays a target if its list keeps an error. The run takes 0.2 s more. tagged errors x86-64 GCC 12256 -> 11432 19989 -> 18293 x86-64 clang 13002 -> 12096 22112 -> 20063 arm64 clang 11837 -> 10954 20325 -> 18237 The tool does not see - an unlock that is inlined: it is a store, not a call - a callee that takes the object and returns a value, a computed callee - a void callee without BTF: f.isra.0, a name that two functions have - a pointer that was spilled to the stack, or loaded from the object - a pointer on the stack, or behind a parameter where the count stops It also leaves out - an error behind a void callee that locks arg, or only prints about it Outline KASAN and KCSAN add void callees that get a pointer, such as __asan_load8(p). Each read of *arg is an effect then: targets are lost. Signed-off-by: Alexei Starovoitov Acked-by: Anton Protopopov --- tools/bpf/resolve_btfids/fmodret.c | 88 ++++++++++++++++++++++++ tools/bpf/resolve_btfids/fmodret_scan.c | 64 +++++++++++++++++ tools/bpf/resolve_btfids/fmodret_scan.h | 9 +++ tools/bpf/resolve_btfids/text_flow.c | 69 +++++++++++++++++++ tools/bpf/resolve_btfids/text_flow.h | 27 ++++++++ tools/bpf/resolve_btfids/text_insn.h | 6 ++ tools/bpf/resolve_btfids/text_mc_arm64.c | 3 + tools/bpf/resolve_btfids/text_mc_x86.c | 4 ++ 8 files changed, 270 insertions(+) diff --git a/tools/bpf/resolve_btfids/fmodret.c b/tools/bpf/resolve_btfids/fmodret.c index 8f43e92f32bf..0751519b95d2 100644 --- a/tools/bpf/resolve_btfids/fmodret.c +++ b/tools/bpf/resolve_btfids/fmodret.c @@ -5,6 +5,10 @@ * machine code. This file decides which functions it looks at, and which of the * errors count. * + * A program skips the function. That is not a failure of the function if it + * works on an object of its caller before it returns the error: it unlocks, + * frees or initializes it. Such an error does not count, see set_protos(). + * * A function which no program can attach to gets no tag: ftrace has to find a nop * at its entry, see scan_func(), and a BPF trampoline has to take its parameters. */ @@ -19,8 +23,11 @@ #include "fmodret.h" #include "fmodret_scan.h" #include "image.h" +#include "text_insn.h" #define TAG "bpf_fmodret_retval:" +/* More than any arch has argument registers */ +#define MAX_PARAMS 16 /* Return the size of the integer which FUNC returns, or 0 */ static __u32 int_return_size(const struct btf *btf, const struct btf_type *func) @@ -92,6 +99,86 @@ static bool format_tag(char *tag, const int64_t *values, size_t nr, __u32 size) return n && errors[0] < -1; } +/* As btf_func_arg_align(): is TYPE, or a member of it, an integer of 16 bytes? */ +static bool is_align16(const struct btf *btf, __u32 type) +{ + const struct btf_type *t = btf__type_by_id(btf, btf__resolve_type(btf, type)); + unsigned int i; + + for (i = 0; btf_is_composite(t) && i < btf_vlen(t); i++) + if (is_align16(btf, btf_members(t)[i].type)) + return true; + return btf_is_array(t) ? is_align16(btf, btf_array(t)->type) : + btf_is_int(t) && t->size > 8; +} + +/* + * Count registers like bpf_jit_place_args(): a parameter of up to 16 bytes takes + * one or two of the argument registers, or the stack if they are not left. Set + * REGS[N] to the first register of parameter N of PROTO, as scan_set_proto() takes + * it, or to 0. Return for how many parameters that is known: what a bigger one + * takes depends on the arch, and x86-64 has a struct with an unaligned member on + * the stack. Nothing is known if the return value is bigger. + */ +static unsigned int place_params(const struct btf *btf, const struct btf_type *proto, + const struct text_arch *arch, unsigned int *regs) +{ + unsigned int i, reg = 0; + + if (proto->type && btf__resolve_size(btf, proto->type) > 16) + return 0; + for (i = 0; i < btf_vlen(proto) && i < MAX_PARAMS; i++) { + __u32 type = btf_params(proto)[i].type; + __s64 size = btf__resolve_size(btf, type); + unsigned int nr = (size + 7) / 8; + + /* btf__align_of() is 1 for a packed struct */ + if (size <= 0 || size > 16 || (size > 1 && btf__align_of(btf, type) == 1)) + break; + if (arch->even_reg_align && is_align16(btf, type)) + reg += reg & 1; + regs[i] = 0; + if (reg + nr <= arch->nr_args) { + regs[i] = 1U << reg; + reg += nr; + } else if (!arch->backfill_after_stack) { + reg = arch->nr_args; + } + } + return i; +} + +/* + * Tell SCAN what BTF says about the functions of IMG. A function which returns + * nothing cannot fail: what it does to an object is done when its caller returns + * an error. Unlock, put, free and init functions are of this kind. A function + * which returns a value may have failed, and that may be the reason for the error. + */ +static void set_protos(struct scan *scan, const struct image *img, const struct btf *btf) +{ + __u32 id, nr_types = btf__type_cnt(btf); + + for (id = 1; id < nr_types; id++) { + const struct btf_type *t = btf__type_by_id(btf, id); + const struct image_func *func = NULL; + unsigned int pointers = 0, regs[MAX_PARAMS], nr, i; + + if (btf_is_func(t)) + func = image_func(img, btf__name_by_offset(btf, t->name_off)); + if (!func) + continue; + t = btf__type_by_id(btf, t->type); + nr = place_params(btf, t, scan_arch(scan), regs); + for (i = 0; i < nr; i++) { + int type = btf__resolve_type(btf, btf_params(t)[i].type); + + if (type > 0 && btf_is_ptr(btf__type_by_id(btf, type))) + pointers |= regs[i]; + } + scan_set_proto(scan, func, pointers, !t->type); + } +} + int fmodret_tag(Elf *elf, struct btf *btf, int verbose) { size_t nr_funcs = 0, nr_scanned = 0, nr_undecodable = 0, nr_tags = 0; @@ -109,6 +196,7 @@ int fmodret_tag(Elf *elf, struct btf *btf, int verbose) scan = scan_open(&img); if (!scan) goto out; + set_protos(scan, &img, btf); for (id = base ? btf__type_cnt(base) : 1, err = 0; id < nr_types && err >= 0; id++) { const struct btf_type *t = btf__type_by_id(btf, id); diff --git a/tools/bpf/resolve_btfids/fmodret_scan.c b/tools/bpf/resolve_btfids/fmodret_scan.c index 5b5eb8cb414b..3753aa1e50c3 100644 --- a/tools/bpf/resolve_btfids/fmodret_scan.c +++ b/tools/bpf/resolve_btfids/fmodret_scan.c @@ -21,10 +21,18 @@ #define MAX_ERRNO 4095 #define MAX_SUBFUNCS 3 +/* The function at an address, whatever its names are. See scan_set_proto() */ +struct callee { + uint64_t addr; + u32 pointers; /* the registers */ + bool effect; +}; + struct scan { const struct image *img; uint64_t return_thunk; uint64_t entry_hook; + struct callee *callees; /* one for each of img->funcs, sorted by address */ /* The function which is being looked at */ struct text_flow flow; size_t max_insns; @@ -32,6 +40,38 @@ struct scan { size_t nr_values, max_values; }; +static int cmp_callee(const void *va, const void *vb) +{ + const struct callee *a = va, *b = vb; + + return a->addr > b->addr ? 1 : a->addr < b->addr ? -1 : 0; +} + +/* Of two names for ADDR always the same one is found */ +static struct callee *callee_at(const struct scan *s, uint64_t addr) +{ + const struct callee key = { .addr = addr }; + + return bsearch(&key, s->callees, s->img->nr_funcs, sizeof(key), cmp_callee); +} + +const struct text_arch *scan_arch(const struct scan *s) +{ + return s->flow.arch; +} + +void scan_set_proto(struct scan *s, const struct image_func *f, unsigned int pointers, bool effect) +{ + struct callee *callee = callee_at(s, f->addr); + unsigned int i; + + callee->effect = effect; + callee->pointers = 0; + for (i = 0; i < s->flow.arch->nr_args; i++) + if (pointers & BIT(i)) + callee->pointers |= BIT(s->flow.arch->args[i]); +} + /* Append the instructions of SIZE bytes at ADDR */ static int decode(struct scan *s, uint64_t addr, uint64_t size) { @@ -45,15 +85,21 @@ static int decode(struct scan *s, uint64_t addr, uint64_t size) return -EINVAL; for (off = 0; off < size; off += flow->insns[flow->nr_insns++].len) { const struct image_reloc *reloc; + const struct callee *callee; struct text_insn *insn; if (flow->nr_insns == s->max_insns) { size_t max = s->max_insns ? 2 * s->max_insns : 1024; struct text_facts *facts = realloc(flow->facts, max * sizeof(*facts)); + struct text_reach *reach; if (!facts) return -ENOMEM; flow->facts = facts; + reach = realloc(flow->reach, max * sizeof(*reach)); + if (!reach) + return -ENOMEM; + flow->reach = reach; insn = realloc(flow->insns, max * sizeof(*insn)); if (!insn) return -ENOMEM; @@ -78,6 +124,11 @@ static int decode(struct scan *s, uint64_t addr, uint64_t size) insn->kind = TEXT_OTHER; insn->nop = true; } + if (insn->kind != TEXT_CALL) + continue; + callee = callee_at(s, insn->imm); + if (callee && callee->effect) + insn->pointers = callee->pointers; } return 0; } @@ -160,6 +211,8 @@ int scan_func(struct scan *s, const struct image_func *f, const int64_t **values return err; if (!has_entry_nop(flow, f->addr)) return 0; + s->flow.entry = f->addr; + s->flow.args = callee_at(s, f->addr)->pointers; text_flow_fold(&s->flow); text_flow_solve(&s->flow); @@ -172,6 +225,8 @@ int scan_func(struct scan *s, const struct image_func *f, const int64_t **values if (insn->kind != TEXT_MOV_IMM && insn->kind != TEXT_SELECT_IMM) continue; + if (flow->reach[i].path == TEXT_EFFECT_PATH) + continue; out = text_flow_out(flow, i); for (n = 0; n < 2 && !err; n++) { if (out.same & BIT(insn->dst)) @@ -190,6 +245,7 @@ struct scan *scan_open(const struct image *img) { struct scan *s = calloc(1, sizeof(*s)); GElf_Ehdr ehdr; + size_t i; if (!s || !gelf_getehdr(img->elf, &ehdr)) goto err; @@ -203,6 +259,12 @@ struct scan *scan_open(const struct image *img) s->return_thunk = image_symbol(img, s->flow.arch->return_thunk); if (s->flow.arch->entry_hook) s->entry_hook = image_symbol(img, s->flow.arch->entry_hook); + s->callees = calloc(img->nr_funcs, sizeof(*s->callees)); + if (!s->callees) + goto err; + for (i = 0; i < img->nr_funcs; i++) + s->callees[i].addr = img->funcs[i].addr; + qsort(s->callees, img->nr_funcs, sizeof(*s->callees), cmp_callee); return s; err: free(s); @@ -215,6 +277,8 @@ void scan_close(struct scan *s) return; free(s->flow.insns); free(s->flow.facts); + free(s->flow.reach); + free(s->callees); free(s->values); free(s); } diff --git a/tools/bpf/resolve_btfids/fmodret_scan.h b/tools/bpf/resolve_btfids/fmodret_scan.h index ef3b4ed4d189..f390ab7f5956 100644 --- a/tools/bpf/resolve_btfids/fmodret_scan.h +++ b/tools/bpf/resolve_btfids/fmodret_scan.h @@ -11,9 +11,18 @@ struct scan; /* Return NULL, after a message, if the code of IMG cannot be read */ struct scan *scan_open(const struct image *img); void scan_close(struct scan *scan); +const struct text_arch *scan_arch(const struct scan *scan); +/* + * FUNC takes pointers in the argument registers POINTERS: bit N is the one with + * number N. If EFFECT, a call of it changes the objects which they point to. + */ +void scan_set_proto(struct scan *scan, const struct image_func *func, unsigned int pointers, + bool effect); /* * Find the constants which FUNC returns and whose low 32 bits are an error. Set * VALUES to what the return value register holds then, until the next call. + * Leave out a constant if each path from the entry to its return has an effect + * on an object which FUNC gets a pointer to, see text_flow.h. * A function which ftrace cannot patch has none: no program can attach to it. * Return how many there are, or -EINVAL if the code cannot be decoded. */ diff --git a/tools/bpf/resolve_btfids/text_flow.c b/tools/bpf/resolve_btfids/text_flow.c index 3fe2c75eb2fc..d7d3f9d1c6c1 100644 --- a/tools/bpf/resolve_btfids/text_flow.c +++ b/tools/bpf/resolve_btfids/text_flow.c @@ -1,6 +1,8 @@ // SPDX-License-Identifier: GPL-2.0-only /* Which values does a function return? See text_flow.h */ +#include + #include #include @@ -130,6 +132,9 @@ static struct text_facts transfer(const struct text_flow *flow, u32 i) break; } join(&out, flow, next_insn(flow, i)); + /* An effect: the paths without one end here */ + if (insn->pointers) + out = (struct text_facts){}; in = out; kill(&in, insn->defs); @@ -155,6 +160,65 @@ static struct text_facts transfer(const struct text_flow *flow, u32 i) return in; } +/* Return the registers which hold a based pointer behind INSN, if BASED do before it */ +static u32 transfer_based(const struct text_flow *flow, const struct text_insn *insn, u32 based) +{ + u32 defs = insn->defs; + + /* endbr64, the ud2 or brk of WARN(): LLVM does not say what it writes. It may be nothing */ + if (defs == TEXT_ALL_REGS) + return based; + if (insn->kind == TEXT_CALL) + return based & ~(defs | flow->arch->caller_saved); + if (insn->kind != TEXT_OTHER && insn->kind < TEXT_BRANCH) + defs |= BIT(insn->dst); + if (insn->kind == TEXT_MOV_IMM || insn->load || !(insn->uses & based)) + return based & ~defs; + /* push %rdi reads a based pointer and writes the stack pointer */ + return (based | defs) & ~flow->arch->stack_pointer; +} + +/* Join OUT into the facts before instruction I. Return true if they change */ +static bool join_reach(struct text_flow *flow, u32 i, const struct text_reach *out) +{ + struct text_reach *in, old; + + if (i == TEXT_NO_INSN) + return false; + in = &flow->reach[i]; + old = *in; + in->based |= out->based; + if (in->path < out->path) + in->path = out->path; + return memcmp(in, &old, sizeof(old)); +} + +/* Sweep from the first instruction to the last one until nothing changes */ +static void solve_forward(struct text_flow *flow) +{ + const struct text_reach entry = { flow->args, TEXT_CLEAN_PATH }; + bool changed; + u32 i; + + memset(flow->reach, 0, flow->nr_insns * sizeof(*flow->reach)); + join_reach(flow, insn_at(flow, flow->entry), &entry); + do { + changed = false; + for (i = 0; i < flow->nr_insns; i++) { + const struct text_insn *insn = &flow->insns[i]; + struct text_reach out = flow->reach[i]; + + out.based = transfer_based(flow, insn, out.based); + if (insn->pointers) + out.path = TEXT_EFFECT_PATH; + if (insn->kind == TEXT_BRANCH || insn->kind == TEXT_COND_BRANCH) + changed |= join_reach(flow, insn->target, &out); + if (insn->kind != TEXT_BRANCH && insn->kind != TEXT_RETURN) + changed |= join_reach(flow, next_insn(flow, i), &out); + } + } while (changed); +} + /* * Sweep from the last instruction to the first one until nothing changes. The * sets only grow, and one more sweep is needed only for what goes around a loop. @@ -172,6 +236,11 @@ void text_flow_solve(struct text_flow *flow) if ((insn->kind == TEXT_BRANCH || insn->kind == TEXT_COND_BRANCH) && insn->imm) insn->target = insn_at(flow, insn->imm); } + /* Where do the pointers go? A call which gets none is not an effect. Then the paths */ + solve_forward(flow); + for (i = 0; i < flow->nr_insns; i++) + flow->insns[i].pointers &= flow->reach[i].based; + solve_forward(flow); do { changed = false; for (i = flow->nr_insns; i--; ) { diff --git a/tools/bpf/resolve_btfids/text_flow.h b/tools/bpf/resolve_btfids/text_flow.h index a266419400f9..56cd13c277f3 100644 --- a/tools/bpf/resolve_btfids/text_flow.h +++ b/tools/bpf/resolve_btfids/text_flow.h @@ -23,8 +23,34 @@ struct text_facts { u32 sext; /* the low 32 bits are returned, sign extended */ }; +/* + * What has the function done to the objects of its caller when it returns a + * value? An effect is a call which hands a pointer that is based on a pointer + * argument to a callee which changes the object, see text_insn.pointers. The + * sets above stop at an effect: they are about the paths without one. A forward + * may data flow analysis finds the effects, and the paths from the entry. + */ +enum text_path { + TEXT_NO_PATH, /* None shows in the code, see text_flow.insns */ + TEXT_EFFECT_PATH, /* Each path has an effect */ + TEXT_CLEAN_PATH, +}; + +/* The facts before an instruction. The join is the union, and the better path */ +struct text_reach { + /* + * The registers which may hold a pointer that is based on a pointer argument: + * it is computed from the argument without a load, so it points into the + * same object. Memory is not tracked: a pointer which is spilled is lost. + */ + u32 based; + u32 path; /* from the entry to here */ +}; + struct text_flow { const struct text_arch *arch; + u64 entry; /* The address of the first instruction which runs ... */ + u32 args; /* ... and the registers which hold pointer arguments there */ /* * All instructions of the function in the order of their addresses, * whether they can be reached or not: the way to a block may be a jump @@ -34,6 +60,7 @@ struct text_flow { u32 nr_insns; /* The result: the facts before each instruction */ struct text_facts *facts; + struct text_reach *reach; }; /* diff --git a/tools/bpf/resolve_btfids/text_insn.h b/tools/bpf/resolve_btfids/text_insn.h index 5c3ba3a54856..e498245a5b73 100644 --- a/tools/bpf/resolve_btfids/text_insn.h +++ b/tools/bpf/resolve_btfids/text_insn.h @@ -56,11 +56,17 @@ struct text_insn { /* For the user of the decoder */ u64 addr; u32 target; /* the index of the instruction at imm */ + /* Of a TEXT_CALL: the registers with pointers to objects which the callee changes */ + u32 pointers; }; struct text_arch { u8 retval; /* the register with the return value */ + u8 args[8], nr_args; /* the registers with the arguments */ + /* How the parameters take them, as in struct bpf_jit_arg_abi */ + bool even_reg_align, backfill_after_stack; u32 caller_saved; /* the registers which a call may write */ + u32 stack_pointer; /* a mask, 0 if it is not one of the registers */ /* A branch to this symbol is a return */ const char *return_thunk; /* diff --git a/tools/bpf/resolve_btfids/text_mc_arm64.c b/tools/bpf/resolve_btfids/text_mc_arm64.c index c2576473773e..5d2fa8a23a14 100644 --- a/tools/bpf/resolve_btfids/text_mc_arm64.c +++ b/tools/bpf/resolve_btfids/text_mc_arm64.c @@ -108,6 +108,9 @@ static const struct mc_test arm64_tests[] = { const struct mc_arch mc_arch = { .arch = { .retval = 0, + .args = { 0, 1, 2, 3, 4, 5, 6, 7 }, + .nr_args = 8, + .even_reg_align = true, /* AAPCS64: x0 to x18 and x30 */ .caller_saved = 0x4007ffff, }, diff --git a/tools/bpf/resolve_btfids/text_mc_x86.c b/tools/bpf/resolve_btfids/text_mc_x86.c index d8d48b0f68fe..4f60a8f3263c 100644 --- a/tools/bpf/resolve_btfids/text_mc_x86.c +++ b/tools/bpf/resolve_btfids/text_mc_x86.c @@ -123,8 +123,12 @@ static const struct mc_test x86_tests[] = { const struct mc_arch mc_arch = { .arch = { .retval = RAX, + .args = { RDI, RSI, RDX, RCX, R8, R9 }, + .nr_args = 6, + .backfill_after_stack = true, .caller_saved = BIT(RAX) | BIT(RCX) | BIT(RDX) | BIT(RSI) | BIT(RDI) | BIT(R8) | BIT(R9) | BIT(R10) | BIT(R11), + .stack_pointer = BIT(RSP), .return_thunk = "__x86_return_thunk", .entry_hook = "__fentry__", }, -- 2.55.0 From: Anton Protopopov SEC("fmod_ret/vfs_fallocate") int BPF_PROG(no_big_files, struct file *file, int mode, loff_t offset, loff_t len, int ret) { return len > MAX_LEN ? -EFBIG : 0; } This program keeps user space away from a bug below vfs_fallocate() until the fixed kernel runs. It does not load: "vfs_fallocate() is not modifiable". The build has tagged the function with the errors that it returns, the list: "bpf_fmodret_retval:-95,-29,-27,-26,-22,-21,-19,-9,-1". Let an fmod_ret program that is not sleepable attach to a tagged function. The declared targets stay as they are: what a program returns there is not checked. A caller of a tagged function can get each error of the list from the function itself. The build knows nothing about other values: R0 at an exit the trampoline 0 calls the function an error of the list skips it, the caller gets the error another value -, the program does not load: At program exit the register R0 should be 0 or one of -95,-29,-27,.. With the BTF of a module a program can name a FUNC of vmlinux. It attaches to the function of that name in the module, and the tag of vmlinux says nothing about that one. So only the own types of the BTF object are searched. They are sorted by name: a binary search finds the first tag. The check is static: each value in the range of R0 is 0 or in the list. [-27, 0] has -25. The program above gets to the exit in two states, -27 and 0. The verifier tests R0 at the exit of the program and of an exception callback, so flow_join_makes_up() does not join ranges that leave a gap. R0 has a 64-bit and a 32-bit range. clang ends "return a && b ? -EPERM : 0" with "w0 &= 1; w0 = -w0; exit". That is [0, U32_MAX] and [-1, 0]. target returns range R0 at the exit int 32-bit w0 = -22 -22, allowed r0 = 1 << 32 rejected long 64-bit w0 = -22 4294967274, rejected The caller of an int function reads the low 32 bits. The trampoline tests all 64: 1 << 32 skips the function and the caller sees 0. So the 32-bit range decides only if the high 32 bits are 0. For the ABI see the comment. What returns to the trampoline main program, exception callback, cookie of bpf_throw() checked tail call refused extension of the main program refused by existing checks Signed-off-by: Anton Protopopov Co-developed-by: Alexei Starovoitov Signed-off-by: Alexei Starovoitov --- include/linux/bpf.h | 3 ++ include/linux/bpf_verifier.h | 2 + kernel/bpf/btf.c | 30 ++++++++++++++ kernel/bpf/flow.c | 2 + kernel/bpf/verifier.c | 80 ++++++++++++++++++++++++++++++++++++ 5 files changed, 117 insertions(+) diff --git a/include/linux/bpf.h b/include/linux/bpf.h index 520fd72e21fd..ac26bc517482 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -1542,6 +1542,8 @@ struct bpf_attach_target_info { struct module *tgt_mod; const char *tgt_name; const struct btf_type *tgt_type; + /* The errors in the "bpf_fmodret_retval:" tag, if that is what allows fmod_ret */ + const char *fmodret_retvals; }; #define BPF_DISPATCHER_MAX 48 /* Fits in 2048B */ @@ -3430,6 +3432,7 @@ int btf_check_type_match(struct bpf_verifier_log *log, const struct bpf_prog *pr struct btf *btf, const struct btf_type *t); const char *btf_find_decl_tag_value(const struct btf *btf, const struct btf_type *pt, int comp_idx, const char *tag_key); +const char *btf_find_func_tag_value(const struct btf *btf, u32 func_id, const char *tag_key); int btf_find_next_decl_tag(const struct btf *btf, const struct btf_type *pt, int comp_idx, const char *tag_key, int last_id); diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 0d039742c97a..b8567190cd0c 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -1359,6 +1359,8 @@ struct bpf_verifier_env { char tmp_arg_name[32]; struct bpf_insn insn_buf[INSN_BUF_SIZE]; struct bpf_insn epilogue_buf[INSN_BUF_SIZE]; + /* See check_fmodret_retval() */ + const char *fmodret_retvals; struct bpf_liveness *liveness; struct bpf_iarray *succ; struct bpf_iarray *gotox_tmp_buf; diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index 3b30517f56a3..242b011ba93a 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -3682,6 +3682,36 @@ const char *btf_find_decl_tag_value(const struct btf *btf, const struct btf_type return value; } +/* + * The value of the decl tag "" on a function of the kernel or of + * a module. The build sorts their BTF by name: the tags with one key are + * neighbours, and so are those with one value. + * + * Only the own types of btf are searched, not its base. With the BTF of a module + * func_id can be a FUNC of vmlinux: it stands for the function of that name in the + * module. What the build found in the code of vmlinux is not true for it. + */ +const char *btf_find_func_tag_value(const struct btf *btf, u32 func_id, const char *tag_key) +{ + int id, n = btf_nr_types(btf), len = strlen(tag_key); + const char *name = NULL; + u32 name_off = 0; + + for (id = btf_find_by_name_kind_bsearch(btf, tag_key); id < n; id++) { + const struct btf_type *t = btf_type_by_id(btf, id); + + if (t->name_off != name_off) { + name_off = t->name_off; + name = btf_name_by_offset(btf, name_off); + if (strncmp(name, tag_key, len)) + break; + } + if (t->type == func_id && btf_type_is_decl_tag(t)) + return name + len; + } + return NULL; +} + static int btf_find_graph_root(const struct btf *btf, const struct btf_type *pt, const struct btf_type *t, int comp_idx, u32 off, diff --git a/kernel/bpf/flow.c b/kernel/bpf/flow.c index 640a7c500f7c..99abcef86920 100644 --- a/kernel/bpf/flow.c +++ b/kernel/bpf/flow.c @@ -1054,6 +1054,8 @@ static int flow_compute_need_const(struct bpf_verifier_env *env, struct flow_nee if (jump) { /* the verifier compares what the prog and its callbacks return with a range */ ret[0] = BIT(BPF_REG_0); + /* no insn takes the address of this one. It's 0 if there is none */ + ret[env->exception_callback_subprog] = BIT(BPF_REG_0); for (i = 0; i < env->prog->len; i++) { if (!bpf_pseudo_func(&insns[i])) continue; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index bb1659ce7a5c..7fb41713641a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13550,6 +13550,14 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn } if (func_id == BPF_FUNC_tail_call) { + /* + * The program which a tail call jumps to returns for this one, + * and a program array does not check the values it may return. + */ + if (env->fmodret_retvals) { + verbose(env, "tail calls are not allowed in fmod_ret programs with restricted return values\n"); + return -EINVAL; + } if (env->cur_state->curframe) { struct bpf_verifier_state *branch; @@ -20225,6 +20233,66 @@ static bool program_returns_void(struct bpf_verifier_env *env) return false; } +static bool fmodret_retval_allowed(const char *list, s64 value) +{ + char *end; + + if (!value) + return true; + for (; *list; list = *end ? end + 1 : end) { + if (simple_strtoll(list, &end, 10) == value) + return true; + } + return false; +} + +/* + * The build tags the functions which return errors: "bpf_fmodret_retval:-22,-12", + * see tools/bpf/resolve_btfids/fmodret.c. An fmod_ret program can attach to such + * a function. A caller can get each of these errors today: the function returns + * them itself. So the program must return one of them, or 0 to call the function. + */ +static int check_fmodret_retval(struct bpf_verifier_env *env, int regno, + const char *exit_ctx, const char *reg_name) +{ + const struct bpf_prog_aux *aux = env->prog->aux; + struct bpf_reg_state *reg = reg_state(env, regno); + s64 smin = reg_smin(reg), smax = reg_smax(reg), v; + const struct btf_type *t; + + if (reg->type != SCALAR_VALUE) { + verbose(env, "%s the register %s is not a known value (%s)\n", + exit_ctx, reg_name, reg_type_str(env, reg->type)); + return -EINVAL; + } + + /* + * "w0 = -22" zero-extends, the caller of an int function sees -22. The + * trampoline tests all 64 bits: 1 << 32 would skip the function, and the + * caller would see 0. So the low 32 bits decide only if the high ones are 0. + * + * That is right where the ABI leaves the high 32 bits of an int in the + * return value register open: x86-64, arm64. s390x, riscv64, ppc64 and + * loongarch want it sign-extended: look here before one of them is added + * to CONFIG_BPF_FMODRET_SCAN. + */ + t = btf_type_skip_modifiers(aux->attach_btf, aux->attach_func_proto->type, NULL); + if (t->size == 4 && reg_umax(reg) <= U32_MAX) { + smin = reg_s32_min(reg); + smax = reg_s32_max(reg); + } + + /* Stops at the first value which is not in the list, however wide the range is */ + for (v = smin; v <= smax; v++) { + if (!fmodret_retval_allowed(env->fmodret_retvals, v)) { + verbose(env, "%s the register %s should be 0 or one of %s\n", + exit_ctx, reg_name, env->fmodret_retvals); + return -EINVAL; + } + } + return 0; +} + static int check_return_code(struct bpf_verifier_env *env, int regno, const char *reg_name) { const char *exit_ctx = "At program exit"; @@ -20281,6 +20349,9 @@ static int check_return_code(struct bpf_verifier_env *env, int regno, const char if (prog_type == BPF_PROG_TYPE_CGROUP_SKB && (env->prog->expected_attach_type == BPF_CGROUP_INET_EGRESS)) enforce_attach_type_range = tnum_range(2, 3); + if (env->fmodret_retvals) + return check_fmodret_retval(env, regno, exit_ctx, reg_name); + if (!return_retval_range(env, &range)) return 0; @@ -24276,6 +24347,13 @@ int bpf_check_attach_target(struct bpf_verifier_log *log, if (btf_kfunc_is_modify_return(btf, btf_id, prog) || !check_attach_modify_return(addr, tname)) ret = 0; + if (ret) { + /* Nobody declared it as a target. Has the build tagged it? */ + tgt_info->fmodret_retvals = + btf_find_func_tag_value(btf, btf_id, "bpf_fmodret_retval:"); + if (tgt_info->fmodret_retvals) + ret = 0; + } if (ret) { module_put(mod); bpf_log(log, "%s() is not modifiable\n", tname); @@ -24454,6 +24532,8 @@ static int check_attach_btf_id(struct bpf_verifier_env *env) return -EINVAL; } + env->fmodret_retvals = tgt_info.fmodret_retvals; + /* * We don't get trampoline for tracing_multi programs at this point, * it's done when tracing_multi link is created. -- 2.55.0 From: Anton Protopopov The interpreter returns unsigned int, while the trampoline passes all 64 bits of the return value register to the caller of the function. The ABI and the compiler decide what the high 32 bits hold. If they are 0 and an fmod_ret program on a tagged function which returns long is interpreted, then a valid return value like -14 reaches the caller as 4294967282. This value is not 0, so the function is skipped, and it is not an error either. Require the JIT for such programs, as for other features which the interpreter does not support. The caller of a function which returns int reads only the low 32 bits, so nothing changes for it. No kernel that has tags runs such a program in the interpreter today. CONFIG_BPF_FMODRET_SCAN is for x86-64 and arm64. There CONFIG_BPF_JIT=y forces CONFIG_BPF_JIT_ALWAYS_ON=y, so each program requires the JIT, and CONFIG_BPF_JIT=n leaves no trampoline to attach to. The rule is for the next arch that gets the option and keeps the interpreter. There net.core.bpf_jit_enable=0, or a JIT that gives up, hands the program to the interpreter. Signed-off-by: Anton Protopopov Co-developed-by: Alexei Starovoitov Signed-off-by: Alexei Starovoitov --- kernel/bpf/verifier.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 7fb41713641a..a22037ac9068 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -24533,6 +24533,9 @@ static int check_attach_btf_id(struct bpf_verifier_env *env) } env->fmodret_retvals = tgt_info.fmodret_retvals; + /* The interpreter returns only 32 bits */ + if (env->fmodret_retvals && tgt_info.fmodel.ret_size == 8) + prog->jit_required = 1; /* * We don't get trampoline for tracing_multi programs at this point, -- 2.55.0 From: Anton Protopopov bpf_testmod gets functions for the rules of the tool. Subtest "tags" compares their tags: bpf_testmod_retval_ returns tag called, long two errors, int and long both errors zero_extended, minus_one (u32)-EINVAL as u64, -1 alone none eperm -1 and -ENOENT both errors denied -EACCES, -EAGAIN, -EMSGSIZE, -13 -EINPROGRESS, -512, -529 effect, _late, _two_regs -EINVAL, an unlock, -EBUSY -22 no_effect trylock, unlock on one path all errors err_ptr PTR_ERR(), inlined helper both errors no_branch sbb + and with GCC -14 pointer, argument, init, not an integer, an argument, none notrace, variadic init code, no attach bpf_testmod.c includes the new file, so that bpf_testmod stays one object. Subtest "run": bpf_testmod_test_write() calls bpf_testmod_retval_called(). the program returns the function write() fails with 0 is called -EFBIG, its own error -EINVAL is skipped -EINVAL The other programs are only loaded, one for each rule of the check: other_error an error that is not in the list range [-27, -22]: only both ends are in the list (exception_cb_)two_paths two errors on two paths to one exit negated_bool [-1, 0] in the low 32 bits high_bits 1 << 32 zero_extended w0 = -14, the target returns long pointer R0 is not a scalar throws, exception_cb the cookie, the exit of the callback tag_of_vmlinux the tag of a vmlinux function of that name tail_call, not_a_target refused Subtest "extension": what an extension returns is not checked, and an extension of the main program returns to the trampoline. Existing checks refuse it. It must not load, with a plain ctx or __arg_ctx in either one. The config of the selftests turns the option on. Without it, or without LLVM on the build host, the test is skipped. The selftests build their own resolve_btfids, without LLVM, and pass it to kbuild for the test modules. kbuild runs it with the flags of the config of the kernel, and --fmodret_scan fails: "no decoder for the code of ELF machine 62". With the option on kbuild takes the resolve_btfids of the kernel build: flags and tool belong together. BPF CI unpacks a kernel build directory without the tool. kbuild makes it again. Signed-off-by: Anton Protopopov Co-developed-by: Alexei Starovoitov Signed-off-by: Alexei Starovoitov --- tools/testing/selftests/bpf/config | 1 + .../selftests/bpf/prog_tests/fmodret_retval.c | 155 +++++++++++++ .../selftests/bpf/progs/fmodret_retval.c | 203 ++++++++++++++++++ .../selftests/bpf/progs/fmodret_retval_ext.c | 18 ++ .../testing/selftests/bpf/test_kmods/Makefile | 16 ++ .../selftests/bpf/test_kmods/bpf_testmod.c | 4 +- .../bpf/test_kmods/bpf_testmod_retval.c | 153 +++++++++++++ 7 files changed, 549 insertions(+), 1 deletion(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/fmodret_retval.c create mode 100644 tools/testing/selftests/bpf/progs/fmodret_retval.c create mode 100644 tools/testing/selftests/bpf/progs/fmodret_retval_ext.c create mode 100644 tools/testing/selftests/bpf/test_kmods/bpf_testmod_retval.c diff --git a/tools/testing/selftests/bpf/config b/tools/testing/selftests/bpf/config index 49dfe939467c..30b744844ef5 100644 --- a/tools/testing/selftests/bpf/config +++ b/tools/testing/selftests/bpf/config @@ -3,6 +3,7 @@ CONFIG_BOOTPARAM_HARDLOCKUP_PANIC=y CONFIG_BOOTPARAM_SOFTLOCKUP_PANIC=1 CONFIG_BPF=y CONFIG_BPF_EVENTS=y +CONFIG_BPF_FMODRET_SCAN=y CONFIG_BPF_JIT=y CONFIG_BPF_KPROBE_OVERRIDE=y CONFIG_BPF_LIRC_MODE2=y diff --git a/tools/testing/selftests/bpf/prog_tests/fmodret_retval.c b/tools/testing/selftests/bpf/prog_tests/fmodret_retval.c new file mode 100644 index 000000000000..1db55d8d8d67 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/fmodret_retval.c @@ -0,0 +1,155 @@ +// SPDX-License-Identifier: GPL-2.0 +/* The functions which the build tags as fmod_ret targets, because they return errors */ +#include +#include +#include "fmodret_retval.skel.h" +#include "fmodret_retval_ext.skel.h" + +#define TAG "bpf_fmodret_retval:" + +/* The functions of test_kmods/bpf_testmod_retval.c and the errors in their tags */ +static const struct { + const char *func, *errors; +} fixtures[] = { + { "bpf_testmod_retval_called", "-27,-22" }, + { "bpf_testmod_retval_long", "-28,-14" }, + { "bpf_testmod_retval_zero_extended", "" }, + { "bpf_testmod_retval_minus_one", "" }, + { "bpf_testmod_retval_eperm", "-2,-1" }, + { "bpf_testmod_retval_denied", "-13" }, + { "bpf_testmod_retval_effect", "-22" }, + { "bpf_testmod_retval_effect_late", "-22" }, + { "bpf_testmod_retval_effect_two_regs", "-22" }, + { "bpf_testmod_retval_no_effect", "-28,-22,-16" }, + { "bpf_testmod_retval_err_ptr", "-34,-14" }, + { "bpf_testmod_retval_no_branch", "-14" }, + { "bpf_testmod_retval_pointer", "" }, + { "bpf_testmod_retval_argument", "" }, + { "bpf_testmod_retval_notrace", "" }, + { "bpf_testmod_retval_variadic", "" }, + { "bpf_testmod_retval_init", "" }, +}; + +/* Return the errors in the tag of FUNC, or NULL */ +static const char *tagged_errors(const struct btf *btf, const char *func) +{ + int id, func_id = btf__find_by_name_kind(btf, func, BTF_KIND_FUNC); + + if (!ASSERT_GT(func_id, 0, func)) + return NULL; + for (id = btf__type_cnt(btf__base_btf(btf)); id < btf__type_cnt(btf); id++) { + const struct btf_type *t = btf__type_by_id(btf, id); + const char *name = btf__name_by_offset(btf, t->name_off); + + if (btf_is_decl_tag(t) && t->type == func_id && !strncmp(name, TAG, strlen(TAG))) + return name + strlen(TAG); + } + return NULL; +} + +static int write_errno(int len) +{ + int fd = open("/sys/kernel/bpf_testmod", O_WRONLY), err; + char buf[8] = {}; + + if (!ASSERT_GE(fd, 0, "open")) + return 0; + err = write(fd, buf, len) < 0 ? -errno : 0; + close(fd); + return err; +} + +/* bpf_testmod_test_write() returns the error of the target, or -EIO */ +static void test_run(void) +{ + struct fmodret_retval *skel; + struct bpf_program *prog; + + skel = fmodret_retval__open(); + if (!ASSERT_OK_PTR(skel, "open")) + return; + bpf_object__for_each_program(prog, skel->obj) + bpf_program__set_autoload(prog, prog == skel->progs.called); + if (!ASSERT_OK(fmodret_retval__load(skel), "load")) + goto out; + skel->bss->pid = getpid(); + + ASSERT_EQ(write_errno(7), -EFBIG, "before"); + if (!ASSERT_OK(fmodret_retval__attach(skel), "attach")) + goto out; + ASSERT_EQ(write_errno(7), -EFBIG, "called"); + skel->bss->deny = true; + ASSERT_EQ(write_errno(7), -EINVAL, "skipped"); + fmodret_retval__detach(skel); + ASSERT_EQ(write_errno(7), -EFBIG, "after"); +out: + fmodret_retval__destroy(skel); +} + +/* + * What an extension returns is not checked against the tag, and an extension of + * the main program would return to the trampoline. Today none has the type of + * the main program of a tracing program. Whatever the reason is, it must not load. + */ +static void test_extension(void) +{ + struct bpf_program *prog, *main_prog, *ext_prog; + struct fmodret_retval_ext *ext; + struct fmodret_retval *skel; + int i; + + skel = fmodret_retval__open(); + if (!ASSERT_OK_PTR(skel, "open")) + return; + bpf_object__for_each_program(prog, skel->obj) + bpf_program__set_autoload(prog, prog == skel->progs.called || + prog == skel->progs.tagged_ctx); + if (!ASSERT_OK(fmodret_retval__load(skel), "load")) + goto out; + for (i = 0; i < 4; i++) { + ext = fmodret_retval_ext__open(); + if (!ASSERT_OK_PTR(ext, "open extension")) + break; + main_prog = i & 1 ? skel->progs.called : skel->progs.tagged_ctx; + ext_prog = i & 2 ? ext->progs.plain_ctx : ext->progs.arg_ctx; + bpf_object__for_each_program(prog, ext->obj) + bpf_program__set_autoload(prog, prog == ext_prog); + ASSERT_OK(bpf_program__set_attach_target(ext_prog, bpf_program__fd(main_prog), + bpf_program__name(main_prog)), + "set_attach_target"); + ASSERT_ERR(fmodret_retval_ext__load(ext), "load extension"); + fmodret_retval_ext__destroy(ext); + } +out: + fmodret_retval__destroy(skel); +} + +void test_fmodret_retval(void) +{ + struct btf *vmlinux_btf, *btf = NULL; + int i; + + vmlinux_btf = btf__load_vmlinux_btf(); + if (!ASSERT_OK_PTR(vmlinux_btf, "btf__load_vmlinux_btf")) + return; + btf = btf__load_module_btf("bpf_testmod", vmlinux_btf); + if (!ASSERT_OK_PTR(btf, "btf__load_module_btf")) + goto out; + if (!tagged_errors(btf, fixtures[0].func)) { + printf("%s:SKIP:no CONFIG_BPF_FMODRET_SCAN\n", __func__); + test__skip(); + goto out; + } + if (test__start_subtest("tags")) + for (i = 0; i < ARRAY_SIZE(fixtures); i++) + ASSERT_STREQ(tagged_errors(btf, fixtures[i].func) ?: "", fixtures[i].errors, + fixtures[i].func); + if (test__start_subtest("run")) + test_run(); + if (test__start_subtest("extension")) + test_extension(); + RUN_TESTS(fmodret_retval); +out: + btf__free(btf); + btf__free(vmlinux_btf); +} diff --git a/tools/testing/selftests/bpf/progs/fmodret_retval.c b/tools/testing/selftests/bpf/progs/fmodret_retval.c new file mode 100644 index 000000000000..1045462a4ec7 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/fmodret_retval.c @@ -0,0 +1,203 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * fmod_ret programs on functions of bpf_testmod which the build has tagged, see + * test_kmods/bpf_testmod_retval.c. They may return only 0 or the errors in the + * "bpf_fmodret_retval:" tag of their target. + */ +#include +#include +#include +#include +#include "bpf_misc.h" +#include "bpf_experimental.h" + +char _license[] SEC("license") = "GPL"; + +int pid; +bool deny; + +/* What write() to /sys/kernel/bpf_testmod returns tells whether the function was called */ +SEC("fmod_ret/bpf_testmod_retval_called") +__success +int BPF_PROG(called, size_t len, int ret) +{ + if (bpf_get_current_pid_tgid() >> 32 != pid) + return 0; + return deny ? -EINVAL : 0; +} + +/* For the extensions of fmodret_retval_ext.c: "called" has a plain ctx */ +SEC("fmod_ret/bpf_testmod_retval_called") +__success +int tagged_ctx(unsigned long long *ctx __arg_ctx) +{ + return 0; +} + +SEC("fmod_ret/bpf_testmod_retval_called") +__failure __msg("At program exit the register R0 should be 0 or one of -27,-22") +int BPF_PROG(other_error, size_t len, int ret) +{ + return -EPERM; +} + +/* Each path to the exit has an allowed value, their join has not */ +SEC("fmod_ret/bpf_testmod_retval_called") +__success +__naked void two_paths(void) +{ + asm volatile ( + "r2 = *(u64 *)(r1 + 0);" + "r0 = -27;" + "if r2 == 7 goto 1f;" + "r0 = -22;" +"1:" + "exit;" + ::: __clobber_all); +} + +/* Both ends of the range are in the list, the values between them are not */ +SEC("fmod_ret/bpf_testmod_retval_called") +__failure __msg("R0 should be 0 or one of -27,-22") +__naked void range(void) +{ + asm volatile ( + "r0 = *(u64 *)(r1 + 0);" + "if r0 s< -27 goto 1f;" + "if r0 s> -22 goto 1f;" + "exit;" +"1:" + "r0 = 0;" + "exit;" + ::: __clobber_all); +} + +/* The end of clang's "return a && b ? -EPERM : 0": [0, U32_MAX] in 64 bits, [-1, 0] in 32 */ +SEC("fmod_ret/bpf_testmod_retval_eperm") +__success +__naked void negated_bool(void) +{ + asm volatile ( + "r0 = *(u64 *)(r1 + 0);" + "w0 &= 1;" + "w0 = -w0;" + "exit;" + ::: __clobber_all); +} + +/* Not 0, so the function is not called, but the caller would see 0 */ +SEC("fmod_ret/bpf_testmod_retval_called") +__failure __msg("R0 should be 0 or one of -27,-22") +__naked void high_bits(void) +{ + asm volatile ( + "r0 = 1;" + "r0 <<= 32;" + "exit;" + ::: __clobber_all); +} + +/* The function returns long, so all 64 bits count: this is 4294967282 */ +SEC("fmod_ret/bpf_testmod_retval_long") +__failure __msg("R0 should be 0 or one of -28,-14") +__naked void zero_extended(void) +{ + asm volatile ( + "w0 = -14;" + "exit;" + ::: __clobber_all); +} + +/* A privileged program may return a pointer, but not here */ +SEC("fmod_ret/bpf_testmod_retval_called") +__failure __msg("R0 is not a known value (ctx)") +__naked void pointer(void) +{ + asm volatile ( + "r0 = r1;" + "exit;" + ::: __clobber_all); +} + +/* The default exception callback returns the cookie */ +SEC("fmod_ret/bpf_testmod_retval_denied") +__failure __msg("At program exit the register R1 should be 0 or one of -13") +int BPF_PROG(throws, int a, int b, int c, int d, int ret) +{ + if (a) + bpf_throw(7); + return 0; +} + +/* An exception callback returns for the program */ +__noinline int returns_eperm(u64 cookie) +{ + return -EPERM; +} + +SEC("fmod_ret/bpf_testmod_retval_called") +__exception_cb(returns_eperm) +__failure __msg("R0 should be 0 or one of -27,-22") +int BPF_PROG(exception_cb, size_t len, int ret) +{ + if (len) + bpf_throw(0); + return 0; +} + +/* As in two_paths, each path to the exit has an allowed value, their join has not */ +__noinline int returns_two_errors(u64 cookie) +{ + register int err asm("r0"); + + asm volatile ( + "r0 = -27;" + "if %[cookie] == 7 goto 1f;" + "r0 = -22;" +"1:" + : "=r"(err) : [cookie] "r"(cookie)); + return err; +} + +SEC("fmod_ret/bpf_testmod_retval_called") +__exception_cb(returns_two_errors) +__success +int BPF_PROG(exception_cb_two_paths, size_t len, int ret) +{ + if (len) + bpf_throw(len); + return 0; +} + +SEC("fmod_ret/bpf_testmod_retval_minus_one") +__failure __msg("bpf_testmod_retval_minus_one() is not modifiable") +int BPF_PROG(not_a_target, int value, int ret) +{ + return 0; +} + +/* + * vmlinux has a bpf_dummy_reg() of the same type, so the two share the FUNC of + * vmlinux. That one returns an error and has a tag. This one returns only 0. + */ +SEC("fmod_ret/bpf_testmod:bpf_dummy_reg") +__failure __msg("bpf_dummy_reg() is not modifiable") +int BPF_PROG(tag_of_vmlinux, void *kdata, struct bpf_link *link, int ret) +{ + return 0; +} + +struct { + __uint(type, BPF_MAP_TYPE_PROG_ARRAY); + __uint(max_entries, 1); + __uint(key_size, sizeof(__u32)); + __uint(value_size, sizeof(__u32)); +} jmp_table SEC(".maps"); + +SEC("fmod_ret/bpf_testmod_retval_called") +__failure __msg("tail calls are not allowed in fmod_ret programs with restricted return values") +int BPF_PROG(tail_call, size_t len, int ret) +{ + bpf_tail_call(ctx, &jmp_table, 0); + return 0; +} diff --git a/tools/testing/selftests/bpf/progs/fmodret_retval_ext.c b/tools/testing/selftests/bpf/progs/fmodret_retval_ext.c new file mode 100644 index 000000000000..9f640fcabdb1 --- /dev/null +++ b/tools/testing/selftests/bpf/progs/fmodret_retval_ext.c @@ -0,0 +1,18 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Extensions for the main program of an fmod_ret program, see prog_tests/fmodret_retval.c */ +#include +#include + +char _license[] SEC("license") = "GPL"; + +SEC("freplace") +int plain_ctx(unsigned long long *ctx) +{ + return 7; +} + +SEC("freplace") +int arg_ctx(unsigned long long *ctx __arg_ctx) +{ + return 7; +} diff --git a/tools/testing/selftests/bpf/test_kmods/Makefile b/tools/testing/selftests/bpf/test_kmods/Makefile index 031c7454ce65..4459a037b42b 100644 --- a/tools/testing/selftests/bpf/test_kmods/Makefile +++ b/tools/testing/selftests/bpf/test_kmods/Makefile @@ -12,6 +12,18 @@ KDIR ?= $(if $(KMOD_O_VALID),$(SRCTREE_KDIR), \ $(if $(wildcard $(SRCTREE_KDIR)/Module.symvers),$(SRCTREE_KDIR), \ /lib/modules/$(shell uname -r)/build)) +# kbuild runs resolve_btfids with the flags which the config of the kernel asks +# for, and --fmodret_scan needs a resolve_btfids which is linked with LLVM. The +# one of the kernel build is. The one of the selftests, which bpf/Makefile passes +# down, is not. A kernel build directory that comes out of an archive can lack +# the tool: kbuild makes it again, in its place: not in the OUTPUT of kselftest. +KMOD_OBJTREE := $(or $(KMOD_O_VALID),$(KDIR)) +KERNEL_RESOLVE_BTFIDS := $(KMOD_OBJTREE)/tools/bpf/resolve_btfids/resolve_btfids +ifneq ($(shell grep -sx CONFIG_BPF_FMODRET_SCAN=y $(KMOD_OBJTREE)/include/config/auto.conf),) +MAKEOVERRIDES := $(filter-out RESOLVE_BTFIDS=% OUTPUT=%,$(MAKEOVERRIDES)) +all: $(KERNEL_RESOLVE_BTFIDS) +endif + ifeq ($(V),1) Q = else @@ -38,6 +50,10 @@ else ifneq ("$(wildcard $(KDIR))", "") M=$(TEST_KMOD_DIR) modules endif +$(KERNEL_RESOLVE_BTFIDS): + $(Q)$(MAKE) -C $(KDIR) $(if $(KMOD_O_VALID),O=$(KMOD_O_VALID) KBUILD_OUTPUT=$(KMOD_O_VALID),KBUILD_OUTPUT=) \ + tools/bpf/resolve_btfids + clean: ifneq ("$(wildcard $(KDIR))", "") $(Q)$(MAKE) -C $(KDIR) $(if $(KMOD_O_VALID),O=$(KMOD_O_VALID) KBUILD_OUTPUT=$(KMOD_O_VALID),KBUILD_OUTPUT=) \ diff --git a/tools/testing/selftests/bpf/test_kmods/bpf_testmod.c b/tools/testing/selftests/bpf/test_kmods/bpf_testmod.c index 41ff36f0ca77..1f8bc0c99a71 100644 --- a/tools/testing/selftests/bpf/test_kmods/bpf_testmod.c +++ b/tools/testing/selftests/bpf/test_kmods/bpf_testmod.c @@ -879,6 +879,8 @@ static __always_inline size_t testmod_inline_len(size_t len) return len; } +#include "bpf_testmod_retval.c" + noinline ssize_t bpf_testmod_test_write(struct file *file, struct kobject *kobj, const struct bin_attribute *bin_attr, @@ -892,7 +894,7 @@ bpf_testmod_test_write(struct file *file, struct kobject *kobj, trace_bpf_testmod_test_write_bare_tp(current, &ctx); - return -EIO; /* always fail */ + return bpf_testmod_retval_called(len) ?: -EIO; /* always fail */ } EXPORT_SYMBOL(bpf_testmod_test_write); ALLOW_ERROR_INJECTION(bpf_testmod_test_write, ERRNO); diff --git a/tools/testing/selftests/bpf/test_kmods/bpf_testmod_retval.c b/tools/testing/selftests/bpf/test_kmods/bpf_testmod_retval.c new file mode 100644 index 000000000000..c6263d7e65be --- /dev/null +++ b/tools/testing/selftests/bpf/test_kmods/bpf_testmod_retval.c @@ -0,0 +1,153 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Functions for resolve_btfids --fmodret_scan, which tags the functions that + * return errors as fmod_ret targets. prog_tests/fmodret_retval.c has the tags + * which it expects. A part of bpf_testmod.c. + */ + +/* bpf_testmod_test_write() calls it and returns what it gets */ +static noinline int bpf_testmod_retval_called(size_t len) +{ + if (len == 7) + return -EFBIG; + return len ? 0 : -EINVAL; +} + +static __used noinline long bpf_testmod_retval_long(int value) +{ + return value ? -EFAULT : -ENOSPC; +} + +/* 0xffffffea is not an error in 64 bits */ +static __used noinline u64 bpf_testmod_retval_zero_extended(int value) +{ + return value ? (u32)-EINVAL : 0; +} + +/* -1 may be "less" or "none": it counts only next to another error */ +static __used noinline int bpf_testmod_retval_minus_one(int value) +{ + return value ? -1 : 0; +} + +static __used noinline int bpf_testmod_retval_eperm(int value) +{ + if (value < 0) + return -EPERM; + return value > 8 ? -ENOENT : value; +} + +/* Errors which tell the caller that something goes on are not listed */ +static __used noinline int bpf_testmod_retval_denied(int a, int b, int c, int d) +{ + if (a > 1) + return -EMSGSIZE; + if (a) + return -EACCES; + if (b) + return -EAGAIN; + if (c) + return -EINPROGRESS; + return d ? -ERESTARTSYS : -EIOCBQUEUED; +} + +/* A caller which gets -EBUSY relies on the unlock */ +static __used noinline int bpf_testmod_retval_effect(struct mutex *lock, int value) +{ + if (value < 0) + return -EINVAL; + mutex_unlock(lock); + return value > 8 ? -EBUSY : value; +} + +/* The errors are set before the unlock. The pointer moves to another register */ +static __used noinline int bpf_testmod_retval_effect_late(int value, struct mutex *lock) +{ + int err = 0; + + if (value < 0) + return -EINVAL; + if (value == 1) + err = -EBUSY; + else if (value == 2) + err = -ENOSPC; + mutex_unlock(lock); + return err; +} + +/* The lock is in the third argument register: a sockptr_t takes two */ +static __used noinline int bpf_testmod_retval_effect_two_regs(sockptr_t ptr, struct mutex *lock, + int value) +{ + if (value < 0) + return -EINVAL; + mutex_unlock(lock); + return value > 8 ? -EBUSY : value; +} + +/* The callee can fail, the pointer is loaded, a path goes around the unlock */ +static __used noinline int bpf_testmod_retval_no_effect(struct mutex *lock, struct mutex **other, + int value) +{ + if (!mutex_trylock(lock)) + return -EBUSY; + mutex_unlock(*other); + if (value < 0) + return -EINVAL; + if (value & 1) + mutex_unlock(lock); + return mutex_is_locked(lock) ? -ENOSPC : 0; +} + +/* PTR_ERR() of the ERR_PTR() of an inlined helper */ +static __always_inline int *bpf_testmod_retval_slot(int *buf, int idx) +{ + if (idx < 0) + return ERR_PTR(-ERANGE); + return idx > 8 ? ERR_PTR(-EFAULT) : &buf[idx]; +} + +static __used noinline int bpf_testmod_retval_err_ptr(int *buf, int idx) +{ + int *slot = bpf_testmod_retval_slot(buf, idx); + + if (IS_ERR(slot)) + return PTR_ERR(slot); + *slot = 1; + return 0; +} + +/* GCC for x86-64: neg, sbb, and */ +static __used noinline int bpf_testmod_retval_no_branch(unsigned long left) +{ + return left ? -EFAULT : 0; +} + +/* Not an integer, and an error which is not returned */ +static __used noinline void *bpf_testmod_retval_pointer(int value) +{ + return value ? ERR_PTR(-EINVAL) : NULL; +} + +static __used noinline int bpf_testmod_retval_argument(int value) +{ + return bpf_testmod_retval_minus_one(value ? -EINVAL : -ENOMEM) + 1; +} + +/* ftrace has no nop to patch at its entry */ +static __used noinline notrace int bpf_testmod_retval_notrace(int value) +{ + return value ? -EINVAL : -ENOMEM; +} + +/* A BPF trampoline does not take it */ +static __used noinline int bpf_testmod_retval_variadic(int value, ...) +{ + return value ? -EINVAL : -ENOMEM; +} + +/* Gone before a program can attach */ +static __used noinline __init int bpf_testmod_retval_init(int value) +{ + return value ? -EINVAL : -ENOMEM; +} -- 2.55.0