| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Tue, 3 Mar 2020 08:48:04 +0100
From: Björn Töpel <bjorn.topel@...il.com>
To: Luke Nelson <lukenels@...washington.edu>
Cc: bpf <bpf@...r.kernel.org>, Luke Nelson <luke.r.nels@...il.com>,
Jonathan Corbet <corbet@....net>,
Alexei Starovoitov <ast@...nel.org>,
Daniel Borkmann <daniel@...earbox.net>,
Martin KaFai Lau <kafai@...com>,
Song Liu <songliubraving@...com>, Yonghong Song <yhs@...com>,
Andrii Nakryiko <andriin@...com>,
"David S. Miller" <davem@...emloft.net>,
Jakub Kicinski <kuba@...nel.org>,
Paul Walmsley <paul.walmsley@...ive.com>,
Palmer Dabbelt <palmer@...belt.com>,
Albert Ou <aou@...s.berkeley.edu>, Xi Wang <xi.wang@...il.com>,
Mauro Carvalho Chehab <mchehab+samsung@...nel.org>,
Stephen Hemminger <stephen@...workplumber.org>,
Rob Herring <robh@...nel.org>,
Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
Jonathan Cameron <Jonathan.Cameron@...wei.com>,
Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
linux-doc@...r.kernel.org, LKML <linux-kernel@...r.kernel.org>,
Netdev <netdev@...r.kernel.org>, linux-riscv@...ts.infradead.org
Subject: Re: [PATCH bpf-next v4 2/4] riscv, bpf: add RV32G eBPF JIT
On Tue, 3 Mar 2020 at 01:50, Luke Nelson <lukenels@...washington.edu> wrote:
>
> This is an eBPF JIT for RV32G, adapted from the JIT for RV64G and
> the 32-bit ARM JIT.
>
> There are two main changes required for this to work compared to
> the RV64 JIT.
>
> First, eBPF registers are 64-bit, while RV32G registers are 32-bit.
> BPF registers either map directly to 2 RISC-V registers, or reside
> in stack scratch space and are saved and restored when used.
>
> Second, many 64-bit ALU operations do not trivially map to 32-bit
> operations. Operations that move bits between high and low words,
> such as ADD, LSH, MUL, and others must emulate the 64-bit behavior
> in terms of 32-bit instructions.
>
> Supported features:
>
> The RV32 JIT supports the same features and instructions as the
> RV64 JIT, with the following exceptions:
>
> - ALU64 DIV/MOD: Requires loops to implement on 32-bit hardware.
>
> - BPF_XADD | BPF_DW: There's no 8-byte atomic instruction in RV32.
>
> These features are also unsupported on other BPF JITs for 32-bit
> architectures.
>
> Testing:
>
> - lib/test_bpf.c
> test_bpf: Summary: 378 PASSED, 0 FAILED, [349/366 JIT'ed]
Which are the tests that fail to JIT, and is that due to div/mod +
xadd?
> test_bpf: test_skb_segment: Summary: 2 PASSED, 0 FAILED
>
> - tools/testing/selftests/bpf/test_verifier.c
> Summary: 1415 PASSED, 122 SKIPPED, 43 FAILED
>
> Tested both with and without BPF JIT hardening.
>
> This is the same set of tests that pass using the BPF interpreter
> with the JIT disabled.
>
> Verification and synthesis:
>
> We developed the RV32 JIT using our automated verification tool,
> Serval. We have used Serval in the past to verify patches to the
> RV64 JIT. We also used Serval to superoptimize the resulting code
> through program synthesis.
>
> You can find the tool and a guide to the approach and results here:
> https://github.com/uw-unsat/serval-bpf/tree/rv32-jit-v4
>
Very interesting work!
> Co-developed-by: Xi Wang <xi.wang@...il.com>
> Signed-off-by: Xi Wang <xi.wang@...il.com>
> Signed-off-by: Luke Nelson <luke.r.nels@...il.com>
> ---
> arch/riscv/Kconfig | 2 +-
> arch/riscv/net/Makefile | 7 +-
> arch/riscv/net/bpf_jit_comp32.c | 1466 +++++++++++++++++++++++++++++++
> 3 files changed, 1473 insertions(+), 2 deletions(-)
> create mode 100644 arch/riscv/net/bpf_jit_comp32.c
[...]
> +
> +static const s8 *rv32_bpf_get_reg64(const s8 *reg, const s8 *tmp,
> + struct rv_jit_context *ctx)
Really a nit, but you're using rv32 as prefix, and also as part of
many of the functions (e.g. emit_rv32). Everything is this file is
just for RV32, so maybe remove that implicit information from the
function name? Just a thought! :-)
> +{
> + if (is_stacked(hi(reg))) {
> + emit(rv_lw(hi(tmp), hi(reg), RV_REG_FP), ctx);
> + emit(rv_lw(lo(tmp), lo(reg), RV_REG_FP), ctx);
> + reg = tmp;
> + }
> + return reg;
> +}
> +
> +static void rv32_bpf_put_reg64(const s8 *reg, const s8 *src,
> + struct rv_jit_context *ctx)
> +{
> + if (is_stacked(hi(reg))) {
> + emit(rv_sw(RV_REG_FP, hi(reg), hi(src)), ctx);
> + emit(rv_sw(RV_REG_FP, lo(reg), lo(src)), ctx);
> + }
> +}
> +
> +static const s8 *rv32_bpf_get_reg32(const s8 *reg, const s8 *tmp,
> + struct rv_jit_context *ctx)
> +{
> + if (is_stacked(lo(reg))) {
> + emit(rv_lw(lo(tmp), lo(reg), RV_REG_FP), ctx);
> + reg = tmp;
> + }
> + return reg;
> +}
> +
> +static void rv32_bpf_put_reg32(const s8 *reg, const s8 *src,
> + struct rv_jit_context *ctx)
> +{
> + if (is_stacked(lo(reg))) {
> + emit(rv_sw(RV_REG_FP, lo(reg), lo(src)), ctx);
> + if (!ctx->prog->aux->verifier_zext)
> + emit(rv_sw(RV_REG_FP, hi(reg), RV_REG_ZERO), ctx);
> + } else if (!ctx->prog->aux->verifier_zext) {
> + emit(rv_addi(hi(reg), RV_REG_ZERO, 0), ctx);
> + }
> +}
> +
> +static void emit_jump_and_link(u8 rd, s32 rvoff, bool force_jalr,
> + struct rv_jit_context *ctx)
> +{
> + s32 upper, lower;
> +
> + if (rvoff && is_21b_int(rvoff) && !force_jalr) {
> + emit(rv_jal(rd, rvoff >> 1), ctx);
> + return;
> + }
> +
> + upper = (rvoff + (1 << 11)) >> 12;
> + lower = rvoff & 0xfff;
> + emit(rv_auipc(RV_REG_T1, upper), ctx);
> + emit(rv_jalr(rd, RV_REG_T1, lower), ctx);
> +}
> +
> +static void emit_rv32_alu_i64(const s8 *dst, s32 imm,
> + struct rv_jit_context *ctx, const u8 op)
> +{
> + const s8 *tmp1 = bpf2rv32[TMP_REG_1];
> + const s8 *rd = rv32_bpf_get_reg64(dst, tmp1, ctx);
> +
> + switch (op) {
> + case BPF_MOV:
> + emit_imm32(rd, imm, ctx);
> + break;
> + case BPF_AND:
> + if (is_12b_int(imm)) {
> + emit(rv_andi(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_and(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + if (imm >= 0)
> + emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
> + break;
> + case BPF_OR:
> + if (is_12b_int(imm)) {
> + emit(rv_ori(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_or(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + if (imm < 0)
> + emit(rv_ori(hi(rd), RV_REG_ZERO, -1), ctx);
> + break;
> + case BPF_XOR:
> + if (is_12b_int(imm)) {
> + emit(rv_xori(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_xor(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + if (imm < 0)
> + emit(rv_xori(hi(rd), hi(rd), -1), ctx);
> + break;
> + case BPF_LSH:
> + if (imm >= 32) {
> + emit(rv_slli(hi(rd), lo(rd), imm - 32), ctx);
> + emit(rv_addi(lo(rd), RV_REG_ZERO, 0), ctx);
> + } else if (imm == 0) {
> + /* nop */
Can we get rid of this, and just do if/else if?
> + } else {
> + emit(rv_srli(RV_REG_T0, lo(rd), 32 - imm), ctx);
> + emit(rv_slli(hi(rd), hi(rd), imm), ctx);
> + emit(rv_or(hi(rd), RV_REG_T0, hi(rd)), ctx);
> + emit(rv_slli(lo(rd), lo(rd), imm), ctx);
> + }
> + break;
> + case BPF_RSH:
> + if (imm >= 32) {
> + emit(rv_srli(lo(rd), hi(rd), imm - 32), ctx);
> + emit(rv_addi(hi(rd), RV_REG_ZERO, 0), ctx);
> + } else if (imm == 0) {
> + /* nop */
Dito.
> + } else {
> + emit(rv_slli(RV_REG_T0, hi(rd), 32 - imm), ctx);
> + emit(rv_srli(lo(rd), lo(rd), imm), ctx);
> + emit(rv_or(lo(rd), RV_REG_T0, lo(rd)), ctx);
> + emit(rv_srli(hi(rd), hi(rd), imm), ctx);
> + }
> + break;
> + case BPF_ARSH:
> + if (imm >= 32) {
> + emit(rv_srai(lo(rd), hi(rd), imm - 32), ctx);
> + emit(rv_srai(hi(rd), hi(rd), 31), ctx);
> + } else if (imm == 0) {
> + /* nop */
Dito.
> + } else {
> + emit(rv_slli(RV_REG_T0, hi(rd), 32 - imm), ctx);
> + emit(rv_srli(lo(rd), lo(rd), imm), ctx);
> + emit(rv_or(lo(rd), RV_REG_T0, lo(rd)), ctx);
> + emit(rv_srai(hi(rd), hi(rd), imm), ctx);
> + }
> + break;
> + }
> +
> + rv32_bpf_put_reg64(dst, rd, ctx);
> +}
> +
> +static void emit_rv32_alu_i32(const s8 *dst, s32 imm,
> + struct rv_jit_context *ctx, const u8 op)
> +{
> + const s8 *tmp1 = bpf2rv32[TMP_REG_1];
> + const s8 *rd = rv32_bpf_get_reg32(dst, tmp1, ctx);
> +
> + switch (op) {
> + case BPF_MOV:
> + emit_imm(lo(rd), imm, ctx);
> + break;
> + case BPF_ADD:
> + if (is_12b_int(imm)) {
> + emit(rv_addi(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_add(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
> + case BPF_SUB:
> + if (is_12b_int(-imm)) {
> + emit(rv_addi(lo(rd), lo(rd), -imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_sub(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
> + case BPF_AND:
> + if (is_12b_int(imm)) {
> + emit(rv_andi(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_and(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
> + case BPF_OR:
> + if (is_12b_int(imm)) {
> + emit(rv_ori(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_or(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
> + case BPF_XOR:
> + if (is_12b_int(imm)) {
> + emit(rv_xori(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_xor(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
> + case BPF_LSH:
> + if (is_12b_int(imm)) {
> + emit(rv_slli(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_sll(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
> + case BPF_RSH:
> + if (is_12b_int(imm)) {
> + emit(rv_srli(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_srl(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
> + case BPF_ARSH:
> + if (is_12b_int(imm)) {
> + emit(rv_srai(lo(rd), lo(rd), imm), ctx);
> + } else {
> + emit_imm(RV_REG_T0, imm, ctx);
> + emit(rv_sra(lo(rd), lo(rd), RV_REG_T0), ctx);
> + }
> + break;
Again nit; I like "early exit" code if possible. Instead of:
if (bleh) {
foo();
} else {
bar();
}
do:
if (bleh) {
foo()
return/break;
}
bar();
I find the latter easier to read -- but really a nit, and a matter of
style. There are number of places where that could be applied in the
file.
> + }
[...]
> +
> +static int build_body(struct rv_jit_context *ctx, bool extra_pass, int *offset)
> +{
> + const struct bpf_prog *prog = ctx->prog;
> + int i;
> +
> + for (i = 0; i < prog->len; i++) {
> + const struct bpf_insn *insn = &prog->insnsi[i];
> + int ret;
> +
> + ret = emit_insn(insn, ctx, extra_pass);
> + if (ret > 0)
> + /*
> + * BPF_LD | BPF_IMM | BPF_DW:
> + * Skip the next instruction.
> + */
> + i++;
> + if (offset)
> + offset[i] = ctx->ninsns;
> + if (ret < 0)
> + return ret;
> + }
> + return 0;
> +}
> +
> +bool bpf_jit_needs_zext(void)
> +{
> + return true;
> +}
> +
> +struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
> +{
> + bool tmp_blinded = false, extra_pass = false;
> + struct bpf_prog *tmp, *orig_prog = prog;
> + int pass = 0, prev_ninsns = 0, i;
> + struct rv_jit_data *jit_data;
> + struct rv_jit_context *ctx;
> + unsigned int image_size = 0;
> +
> + if (!prog->jit_requested)
> + return orig_prog;
> +
> + tmp = bpf_jit_blind_constants(prog);
> + if (IS_ERR(tmp))
> + return orig_prog;
> + if (tmp != prog) {
> + tmp_blinded = true;
> + prog = tmp;
> + }
> +
> + jit_data = prog->aux->jit_data;
> + if (!jit_data) {
> + jit_data = kzalloc(sizeof(*jit_data), GFP_KERNEL);
> + if (!jit_data) {
> + prog = orig_prog;
> + goto out;
> + }
> + prog->aux->jit_data = jit_data;
> + }
> +
> + ctx = &jit_data->ctx;
> +
> + if (ctx->offset) {
> + extra_pass = true;
> + image_size = sizeof(u32) * ctx->ninsns;
> + goto skip_init_ctx;
> + }
> +
> + ctx->prog = prog;
> + ctx->offset = kcalloc(prog->len, sizeof(int), GFP_KERNEL);
> + if (!ctx->offset) {
> + prog = orig_prog;
> + goto out_offset;
> + }
> + for (i = 0; i < prog->len; i++) {
> + prev_ninsns += 32;
> + ctx->offset[i] = prev_ninsns;
> + }
> +
> + for (i = 0; i < NR_JIT_ITERATIONS; i++) {
> + pass++;
> + ctx->ninsns = 0;
> + if (build_body(ctx, extra_pass, ctx->offset)) {
> + prog = orig_prog;
> + goto out_offset;
> + }
> + build_prologue(ctx);
> + ctx->epilogue_offset = ctx->ninsns;
> + build_epilogue(ctx);
> +
> + if (ctx->ninsns == prev_ninsns) {
> + if (jit_data->header)
> + break;
> +
> + image_size = sizeof(u32) * ctx->ninsns;
> + jit_data->header =
> + bpf_jit_binary_alloc(image_size,
> + &jit_data->image,
> + sizeof(u32),
> + bpf_fill_ill_insns);
> + if (!jit_data->header) {
> + prog = orig_prog;
> + goto out_offset;
> + }
> +
> + ctx->insns = (u32 *)jit_data->image;
> + }
> + prev_ninsns = ctx->ninsns;
> + }
> +
> + if (i == NR_JIT_ITERATIONS) {
> + pr_err("bpf-jit: image did not converge in <%d passes!\n", i);
> + bpf_jit_binary_free(jit_data->header);
> + prog = orig_prog;
> + goto out_offset;
> + }
> +
> +skip_init_ctx:
> + pass++;
> + ctx->ninsns = 0;
> +
> + build_prologue(ctx);
> + if (build_body(ctx, extra_pass, NULL)) {
> + bpf_jit_binary_free(jit_data->header);
> + prog = orig_prog;
> + goto out_offset;
> + }
> + build_epilogue(ctx);
> +
> + if (bpf_jit_enable > 1)
> + bpf_jit_dump(prog->len, image_size, 2, ctx->insns);
> +
> + prog->bpf_func = (void *)ctx->insns;
> + prog->jited = 1;
> + prog->jited_len = image_size;
> +
> + bpf_flush_icache(jit_data->header, ctx->insns + ctx->ninsns);
> +
> + if (!prog->is_func || extra_pass) {
> +out_offset:
> + kfree(ctx->offset);
> + kfree(jit_data);
> + prog->aux->jit_data = NULL;
> + }
> +out:
> +
> + if (tmp_blinded)
> + bpf_jit_prog_release_other(prog, prog == orig_prog ?
> + tmp : orig_prog);
> + return prog;
> +}
At this point of the series, let's introduce the shared code .c-file
containing implementation for bpf_int_jit_compile() (with build_body
part of that)and bpf_jit_needs_zext(). That will make it easier to
catch bugs in both JITs and to avoid code duplication! Also, when
adding the stronger invariant suggested by Palmer [1], we only need to
do it in one place.
The pull out refactoring can be a separate commit.
Thanks!
Björn
[1] https://lore.kernel.org/bpf/mhng-6be38b2a-78df-4016-aaea-f35aa0acd7e0@palmerdabbelt-glaptop/
Powered by blists - more mailing lists