From patchwork Wed Jun 19 01:18:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexei Starovoitov X-Patchwork-Id: 13703305 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 78577AD24 for ; Wed, 19 Jun 2024 01:19:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718759945; cv=none; b=mUYrj+zw+7WNAGLMrTZ0EaAZpu5d5jPlwSLmQaewkyY4XHiSpDbHS3YVCGQsQKtZjp4N7nYaxC+vTB7BgSVEo4Cd1tUxKQPXSeO4PmLrpSZRXueGepCiYeFhACuN/+bCpg5vqcqoJR17oodajFSjGDvtbuD4tTlynsb6ACQhjf8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718759945; c=relaxed/simple; bh=e77DLA6028b5BFSlWHf0akYiSkNdRn8Vh/5Kd5rGLHk=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=OqLf+SLhRbXnbpxyKG6yNRwUzNV/d2V6PgY9flNdYC5ztzxErwbBUe9RShI2DEncfzzFUFhulxV1O9xcsC1FrZX7i4EQWuewc+UQadEEcb6CUzSz22jDQNoEqgorEbmCfXdeVbULbYiNBI5wyXey3NHzr7sTyAruryqi+6wJIbQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=GTSsK88r; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="GTSsK88r" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-1f70131063cso48273245ad.2 for ; Tue, 18 Jun 2024 18:19:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1718759943; x=1719364743; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=QZ9KPcIDP6RbgStz4eZd0IPK1X0gzFYWhtvhEBA6rSs=; b=GTSsK88r5dfidz7VbSqcxJWRHJ99jYR3Z/+MqUn5XZ4kCe6WBD/r+b1S0F70I2pm7/ o5lC1YR3kgAEdK676arnDJFgR1IOAz+2BsSEY1i6qqRj/qLjaJCgd2Q28knlud7Iittp ljP6K6Wbp33JfsuMDqsuif88oFaH6lIGPY+SDfiNfiBVkiKJSa+e9xQxYSNXxu1fb7km rUNTAMlhpGcHlWJeP27KWgs8dgzxa04h+veDLAf7VQBH9NVrJmkeGWHKK/FXTwvA7rpw tMFn1waszI7ggd9yzYDAPCuIuZOTH6ZQcosDxQr9MMpZGo/JSeyVFsC8Q5b8iVO1xJxH FWbw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1718759943; x=1719364743; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=QZ9KPcIDP6RbgStz4eZd0IPK1X0gzFYWhtvhEBA6rSs=; b=njcPnwjo23OhUuChWi7HMlIaLs/0JxODGzP/JQ+maR1D80rvi8RRKKHO9kVav1CoBO FQqEhOSpUEYiVb14rFXI8m/Mngz10f04UASytmAY+gmDr29Reym9F//D2LET9yLAOvRA qdR9Kkon6Z5u93S2oSQyoxhFPf+GE9B/tcxEArXZG2azNcvEXafcalo2NuebxzHQDkLC r23OOA8GkEq+MtgrWJx/dm3/sH5qYZo6Lv1D+/+Z+7METRXNkq+FsSc7W5AZyQuQPiY6 Jdafhq9jtY6vQVpF6Oy3567QNegP0lIsCaPvRvt2yd/rjA0oLuBAA9LOBZ3cBYUyLSO2 LoGA== X-Gm-Message-State: AOJu0Yzf0Ng/PiWNJY1rNpvsioGkh21joXMmTaXLDh72MyKmOgAVt6f2 cO2M+P85Z5eIdr/QJ5clndmP/+eK4/X4kEnKsjnUv/o7U454bJgVCA1OSg== X-Google-Smtp-Source: AGHT+IGJvYPOhPbT8Qo+SEdTUmgD+I5iku4UE3wraugyMT3fi/GzmbSK3mx0LVQg3QZC/lW/T3DF6g== X-Received: by 2002:a17:902:d4c7:b0:1f7:17c2:118b with SMTP id d9443c01a7336-1f9aa3e9e49mr12391995ad.27.1718759942846; Tue, 18 Jun 2024 18:19:02 -0700 (PDT) Received: from localhost.localdomain ([2620:10d:c090:400::5:fc92]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-1f99d3fb36dsm16955985ad.186.2024.06.18.18.19.01 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 18 Jun 2024 18:19:02 -0700 (PDT) From: Alexei Starovoitov To: bpf@vger.kernel.org Cc: daniel@iogearbox.net, andrii@kernel.org, martin.lau@kernel.org, memxor@gmail.com, eddyz87@gmail.com, zacecob@protonmail.com, kernel-team@fb.com Subject: [PATCH v2 bpf 1/2] bpf: Fix the corner case with may_goto and jump to the 1st insn. Date: Tue, 18 Jun 2024 18:18:58 -0700 Message-Id: <20240619011859.79334-1-alexei.starovoitov@gmail.com> X-Mailer: git-send-email 2.39.3 (Apple Git-146) Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net From: Alexei Starovoitov When the following program is processed by the verifier: L1: may_goto L2 goto L1 L2: w0 = 0 exit the may_goto insn is first converted to: L1: r11 = *(u64 *)(r10 -8) if r11 == 0x0 goto L2 r11 -= 1 *(u64 *)(r10 -8) = r11 goto L1 L2: w0 = 0 exit then later as the last step the verifier inserts: *(u64 *)(r10 -8) = BPF_MAX_LOOPS as the first insn of the program to initialize loop count. When the first insn happens to be a branch target of some jmp the bpf_patch_insn_data() logic will produce: L1: *(u64 *)(r10 -8) = BPF_MAX_LOOPS r11 = *(u64 *)(r10 -8) if r11 == 0x0 goto L2 r11 -= 1 *(u64 *)(r10 -8) = r11 goto L1 L2: w0 = 0 exit because instruction patching adjusts all jmps and calls, but for this particular corner case it's incorrect and the L1 label should be one instruction down, like: *(u64 *)(r10 -8) = BPF_MAX_LOOPS L1: r11 = *(u64 *)(r10 -8) if r11 == 0x0 goto L2 r11 -= 1 *(u64 *)(r10 -8) = r11 goto L1 L2: w0 = 0 exit and that's what this patch is fixing. After bpf_patch_insn_data() call adjust_jmp_off() to adjust all jmps that point to newly insert BPF_ST insn to point to insn after. Note that bpf_patch_insn_data() cannot easily be changed to accommodate this logic, since jumps that point before or after a sequence of patched instructions have to be adjusted with the full length of the patch. Conceptually it's somewhat similar to "insert" of instructions between other instructions with weird semantics. Like "insert" before 1st insn would require adjustment of CALL insns to point to newly inserted 1st insn, but not an adjustment JMP insns that point to 1st, yet still adjusting JMP insns that cross over 1st insn (point to insn before or insn after), hence use simple adjust_jmp_off() logic to fix this corner case. Ideally bpf_patch_insn_data() would have an auxiliary info to say where 'the start of newly inserted patch is', but it would be too complex for backport. Reported-by: Zac Ecob Closes: https://lore.kernel.org/bpf/CAADnVQJ_WWx8w4b=6Gc2EpzAjgv+6A0ridnMz2TvS2egj4r3Gw@mail.gmail.com/ Fixes: 011832b97b31 ("bpf: Introduce may_goto instruction") Acked-by: Eduard Zingerman Signed-off-by: Alexei Starovoitov --- kernel/bpf/verifier.c | 50 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 50 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index e0a398a97d32..5586a571bf55 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -12721,6 +12721,16 @@ static bool signed_add32_overflows(s32 a, s32 b) return res < a; } +static bool signed_add16_overflows(s16 a, s16 b) +{ + /* Do the add in u16, where overflow is well-defined */ + s16 res = (s16)((u16)a + (u16)b); + + if (b < 0) + return res > a; + return res < a; +} + static bool signed_sub_overflows(s64 a, s64 b) { /* Do the sub in u64, where overflow is well-defined */ @@ -18732,6 +18742,39 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of return new_prog; } +/* + * For all jmp insns in a given 'prog' that point to 'tgt_idx' insn adjust the + * jump offset by 'delta'. + */ +static int adjust_jmp_off(struct bpf_prog *prog, u32 tgt_idx, u32 delta) +{ + struct bpf_insn *insn = prog->insnsi; + u32 insn_cnt = prog->len, i; + + for (i = 0; i < insn_cnt; i++, insn++) { + u8 code = insn->code; + + if ((BPF_CLASS(code) != BPF_JMP && BPF_CLASS(code) != BPF_JMP32) || + BPF_OP(code) == BPF_CALL || BPF_OP(code) == BPF_EXIT) + continue; + + if (insn->code == (BPF_JMP32 | BPF_JA)) { + if (i + 1 + insn->imm != tgt_idx) + continue; + if (signed_add32_overflows(insn->imm, delta)) + return -ERANGE; + insn->imm += delta; + } else { + if (i + 1 + insn->off != tgt_idx) + continue; + if (signed_add16_overflows(insn->imm, delta)) + return -ERANGE; + insn->off += delta; + } + } + return 0; +} + static int adjust_subprog_starts_after_remove(struct bpf_verifier_env *env, u32 off, u32 cnt) { @@ -20548,6 +20591,13 @@ static int do_misc_fixups(struct bpf_verifier_env *env) if (!new_prog) return -ENOMEM; env->prog = prog = new_prog; + /* + * If may_goto is a first insn of a prog there could be a jmp + * insn that points to it, hence adjust all such jmps to point + * to insn after BPF_ST that inits may_goto count. + * Adjustment will succeed because bpf_patch_insn_data() didn't fail. + */ + WARN_ON(adjust_jmp_off(env->prog, subprog_start, 1)); } /* Since poke tab is now finalized, publish aux to tracker. */ From patchwork Wed Jun 19 01:18:59 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexei Starovoitov X-Patchwork-Id: 13703306 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pg1-f181.google.com (mail-pg1-f181.google.com [209.85.215.181]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 57DEE6FB8 for ; Wed, 19 Jun 2024 01:19:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718759949; cv=none; b=jtgBURLQYC1Rj+kCvhqAgUzz1xMFWt6XTQOCtMihmE/3kn25+ntICsnBbJ/yH0TiXgQd2SnZ0oEIaAyOunOPeDjCFLFPDEdGxMN8JQerA9xAxsGQE8QIb1+XloJkQ0VfxMwRnKvwnWN4u4GigCVFv3gTWXAWv/oQXu9IAs4Nm+k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1718759949; c=relaxed/simple; bh=b06cm/BNX4LeTHSmI513hw72QGfmUM0Jn61LXF74cD4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GAvrTICwdxoqI/LRrFBdSuSwNKk9mS3MhtD8Z/NADRihwN3TEAPWFo853EwfX8xedHqlqLNEFI+iBRhXmgIeIpplBONRsrQDBLyANqiwXblRBN+8NcSTVo/thg5k9AZ0A0+cfGV0hb8IIPJxOPU6zLa3TSGfvFbY/OG6ov+gWWU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=d+0kfBfU; arc=none smtp.client-ip=209.85.215.181 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="d+0kfBfU" Received: by mail-pg1-f181.google.com with SMTP id 41be03b00d2f7-6c5bcb8e8edso4859592a12.2 for ; Tue, 18 Jun 2024 18:19:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1718759947; x=1719364747; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=kOrMjixFcXovuBhfL6+XKJXigbxc8mG3H5zc4ZTAQBQ=; b=d+0kfBfUaJ3ra39rsyDsZtFHAjAXnv+/EqKqe78xbaV6E5o94cZfjHJLeqUXbmwQil 0ut9I6scuer6VOCiCxq5/XPDbjhnbTrsQehGLrVA3k4z8lWsdAiJhwfWwoHbyT5+c3O6 r9KzBMLm5mkRWblg72vSUkaULxnS+YqfsGCRk3m3ui4uGwZuppibor7nRYxc6y3CH1Tk kcLT/3IJJLCSf/OHttNCabkh7iT7iOnmk7FcIF0zCbzvkSCVeWsYNO/ySlQ7pojCqo1K eBQktuvPP/9LuUYa6DB2hWZMZFwqnPqLOg6q2EgACK/GF64vUom5bBpVpiBq9cPFar3b AmCg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1718759947; x=1719364747; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=kOrMjixFcXovuBhfL6+XKJXigbxc8mG3H5zc4ZTAQBQ=; b=dnmfP71dF9GVc0L1yv9cm9UFSxuzLOAFRs5DF6Rn3KGZOYc7MgJQvyBRal1YvY60ot 3GWwtlVE78XtmkMZC0D1LzESwx23DBhd/XquoKnaDPyPwf9REY6GkvFCcy/4feUcsTMj Lw5udpIKYuaN3ejBhKP5ZIRib02Z/qqsnyT5StBVg48cM5kaRbm+ropv/3g1DM3fudgE ys6uPtJ8b5FTIJuHiyrnvgTggl3yUUbRRqf0PVasu/eO7VjmoI/9iO38+1hUkwiQ1TE5 en0f4mIzkaAfknqWv9kaxZ1XM8H1faLt/TFlpFX84T70iBr9Be1J7Kf0HI84IE4Ec5Ma tnRw== X-Gm-Message-State: AOJu0Yyp5KF412EZr5MJQzrI7waU9NK6DNviTIi7sP83lR5znBQudgET iwoHtI5DVn0UaQY4mKtN70Eqv/OfPxUCD3TugeY0urWVPv8QRk0+NYTlKA== X-Google-Smtp-Source: AGHT+IFYRjxbqz2Vq+zwQ0crGN5ZLryPNagA8h7CgOQ+S+9whQhoaQH3+4De/5VMD9s7zoTMZSVqQw== X-Received: by 2002:a05:6a20:2da9:b0:1b5:2c97:a88f with SMTP id adf61e73a8af0-1bcbb409a8emr1131608637.20.1718759946740; Tue, 18 Jun 2024 18:19:06 -0700 (PDT) Received: from localhost.localdomain ([2620:10d:c090:400::5:fc92]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-705ccb770c3sm9525153b3a.182.2024.06.18.18.19.05 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Tue, 18 Jun 2024 18:19:06 -0700 (PDT) From: Alexei Starovoitov To: bpf@vger.kernel.org Cc: daniel@iogearbox.net, andrii@kernel.org, martin.lau@kernel.org, memxor@gmail.com, eddyz87@gmail.com, zacecob@protonmail.com, kernel-team@fb.com Subject: [PATCH v2 bpf 2/2] selftests/bpf: Tests with may_goto and jumps to the 1st insn Date: Tue, 18 Jun 2024 18:18:59 -0700 Message-Id: <20240619011859.79334-2-alexei.starovoitov@gmail.com> X-Mailer: git-send-email 2.39.3 (Apple Git-146) In-Reply-To: <20240619011859.79334-1-alexei.starovoitov@gmail.com> References: <20240619011859.79334-1-alexei.starovoitov@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net From: Alexei Starovoitov Add few tests with may_goto and jumps to the 1st insn. Acked-by: Eduard Zingerman Signed-off-by: Alexei Starovoitov --- .../bpf/progs/verifier_iterating_callbacks.c | 94 +++++++++++++++++++ 1 file changed, 94 insertions(+) diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c index bd676d7e615f..8885e5239d6b 100644 --- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c @@ -307,6 +307,100 @@ int iter_limit_bug(struct __sk_buff *skb) return 0; } +SEC("socket") +__success __retval(0) +__naked void ja_and_may_goto(void) +{ + asm volatile (" \ +l0_%=: .byte 0xe5; /* may_goto */ \ + .byte 0; /* regs */ \ + .short 1; /* off 1 */ \ + .long 0; /* imm */ \ + goto l0_%=; \ + r0 = 0; \ + exit; \ +" ::: __clobber_common); +} + +SEC("socket") +__success __retval(0) +__naked void ja_and_may_goto2(void) +{ + asm volatile (" \ +l0_%=: r0 = 0; \ + .byte 0xe5; /* may_goto */ \ + .byte 0; /* regs */ \ + .short 1; /* off 1 */ \ + .long 0; /* imm */ \ + goto l0_%=; \ + r0 = 0; \ + exit; \ +" ::: __clobber_common); +} + +SEC("socket") +__success __retval(0) +__naked void jlt_and_may_goto(void) +{ + asm volatile (" \ +l0_%=: call %[bpf_jiffies64]; \ + .byte 0xe5; /* may_goto */ \ + .byte 0; /* regs */ \ + .short 1; /* off 1 */ \ + .long 0; /* imm */ \ + if r0 < 10 goto l0_%=; \ + r0 = 0; \ + exit; \ +" :: __imm(bpf_jiffies64) + : __clobber_all); +} + +#if (defined(__TARGET_ARCH_arm64) || defined(__TARGET_ARCH_x86) || \ + (defined(__TARGET_ARCH_riscv) && __riscv_xlen == 64) || \ + defined(__TARGET_ARCH_arm) || defined(__TARGET_ARCH_s390) || \ + defined(__TARGET_ARCH_loongarch)) && \ + __clang_major__ >= 18 +SEC("socket") +__success __retval(0) +__naked void gotol_and_may_goto(void) +{ + asm volatile (" \ +l0_%=: r0 = 0; \ + .byte 0xe5; /* may_goto */ \ + .byte 0; /* regs */ \ + .short 1; /* off 1 */ \ + .long 0; /* imm */ \ + gotol l0_%=; \ + r0 = 0; \ + exit; \ +" ::: __clobber_common); +} +#endif + +SEC("socket") +__success __retval(0) +__naked void ja_and_may_goto_subprog(void) +{ + asm volatile (" \ + call subprog_with_may_goto; \ + exit; \ +" ::: __clobber_all); +} + +static __naked __noinline __used +void subprog_with_may_goto(void) +{ + asm volatile (" \ +l0_%=: .byte 0xe5; /* may_goto */ \ + .byte 0; /* regs */ \ + .short 1; /* off 1 */ \ + .long 0; /* imm */ \ + goto l0_%=; \ + r0 = 0; \ + exit; \ +" ::: __clobber_all); +} + #define ARR_SZ 1000000 int zero; char arr[ARR_SZ];