Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Wed, 21 Apr 2021 12:23:48 +0000
Message-Id: <20210421122348.547922-1-jackmanb@google.com>
Mime-Version: 1.0
Subject: Help with verifier failure
From:   Brendan Jackman <jackmanb@google.com>
To:     bpf@vger.kernel.org
Cc:     ast@kernel.org, daniel@iogearbox.net, andrii@kernel.org,
        linux-kernel@vger.kernel.org, Brendan Jackman <jackmanb@google.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

Hi,

Recently when our internal Clang build was updated to 0e92cbd6a652 we start=
ed
hitting a verifier issue that I can't see an easy fix for. I've narrowed it=
 down
to a minimal reproducer - this email is a patch to add that repro as a prog
test (./test_progs -t example).

Here's the BPF code I get from the attached source:

0000000000000000 <exec>:
; int BPF_PROG(exec, struct linux_binprm *bprm) {
       0:       79 11 00 00 00 00 00 00 r1 =3D *(u64 *)(r1 + 0)
       1:       7b 1a e8 ff 00 00 00 00 *(u64 *)(r10 - 24) =3D r1
;   uint64_t args_size =3D bprm->argc & 0xFFFFFFF;
       2:       61 17 58 00 00 00 00 00 r7 =3D *(u32 *)(r1 + 88)
       3:       b4 01 00 00 00 00 00 00 w1 =3D 0
;   int map_key =3D 0;
       4:       63 1a fc ff 00 00 00 00 *(u32 *)(r10 - 4) =3D r1
       5:       bf a2 00 00 00 00 00 00 r2 =3D r10
       6:       07 02 00 00 fc ff ff ff r2 +=3D -4
;   void *buf =3D bpf_map_lookup_elem(&buf_map, &map_key);
       7:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 =3D 0 ll
       9:       85 00 00 00 01 00 00 00 call 1
      10:       7b 0a f0 ff 00 00 00 00 *(u64 *)(r10 - 16) =3D r0
      11:       57 07 00 00 ff ff ff 0f r7 &=3D 268435455
      12:       bf 76 00 00 00 00 00 00 r6 =3D r7
;   if (!buf)
      13:       16 07 12 00 00 00 00 00 if w7 =3D=3D 0 goto +18 <LBB0_7>
      14:       79 a1 f0 ff 00 00 00 00 r1 =3D *(u64 *)(r10 - 16)
      15:       15 01 10 00 00 00 00 00 if r1 =3D=3D 0 goto +16 <LBB0_7>
      16:       b4 09 00 00 00 00 00 00 w9 =3D 0
      17:       b7 01 00 00 00 10 00 00 r1 =3D 4096
      18:       bf 68 00 00 00 00 00 00 r8 =3D r6
      19:       05 00 0e 00 00 00 00 00 goto +14 <LBB0_3>

00000000000000a0 <LBB0_5>:
;     void *src =3D (void *)(char *)bprm->p + offset;
      20:       79 a1 e8 ff 00 00 00 00 r1 =3D *(u64 *)(r10 - 24)
      21:       79 13 18 00 00 00 00 00 r3 =3D *(u64 *)(r1 + 24)
;     uint64_t read_size =3D args_size - offset;
      22:       0f 73 00 00 00 00 00 00 r3 +=3D r7
      23:       07 03 00 00 00 f0 ff ff r3 +=3D -4096
;     (void) bpf_probe_read_user(buf, read_size, src);
      24:       79 a1 f0 ff 00 00 00 00 r1 =3D *(u64 *)(r10 - 16)
      25:       85 00 00 00 70 00 00 00 call 112
;   for (int i =3D 0; i < 512 && offset < args_size; i++) {
      26:       26 09 05 00 fe 01 00 00 if w9 > 510 goto +5 <LBB0_7>
      27:       07 08 00 00 00 f0 ff ff r8 +=3D -4096
      28:       bf 71 00 00 00 00 00 00 r1 =3D r7
      29:       07 01 00 00 00 10 00 00 r1 +=3D 4096
      30:       04 09 00 00 01 00 00 00 w9 +=3D 1
;   for (int i =3D 0; i < 512 && offset < args_size; i++) {
      31:       ad 67 02 00 00 00 00 00 if r7 < r6 goto +2 <LBB0_3>

0000000000000100 <LBB0_7>:
; int BPF_PROG(exec, struct linux_binprm *bprm) {
      32:       b4 00 00 00 00 00 00 00 w0 =3D 0
      33:       95 00 00 00 00 00 00 00 exit

0000000000000110 <LBB0_3>:
      34:       bf 17 00 00 00 00 00 00 r7 =3D r1
;     (void) bpf_probe_read_user(buf, read_size, src);
      35:       bc 82 00 00 00 00 00 00 w2 =3D w8
      36:       a5 08 ef ff 00 10 00 00 if r8 < 4096 goto -17 <LBB0_5>
      37:       b4 02 00 00 00 10 00 00 w2 =3D 4096
      38:       05 00 ed ff 00 00 00 00 goto -19 <LBB0_5>


The full log I get is at
https://gist.githubusercontent.com/bjackman/2928c4ff4cc89545f3993bddd9d5edb=
2/raw/feda6d7c165d24be3ea72c3cf7045c50246abd83/gistfile1.txt,
but basically the verifier runs through the loop a large number of times, g=
oing
down the true path of the `if (read_size > CHUNK_LEN)` every time. Then
eventually it takes the false path.

In the disassembly this is basically instructions 35-37 - pseudocode:
  w2 =3D w8
  if (r8 < 4096) {
    w2 =3D 4096
  }

w2 can't exceed 4096 but the verifier doesn't seem to "backpropagate" those
bounds from r8 (note the umax_value for R8 goes to 4095 after the branch fr=
om 36
to 20, but R2's umax_value is still 266342399)

from 31 to 34: R0_w=3Dinv(id=3D0) R1_w=3Dinv2097152 R6=3Dinv(id=3D2,umin_va=
lue=3D2093057,umax_value=3D268435455,var_off=3D(0x0; 0xfffffff)) R7_w=3Dinv=
2093056 R8_w=3Dinv(id=3D0,umax_value=3D266342399,var_off=3D(0x0; 0xfffffff)=
) R9_w=3DinvP511 R10=3Dfp0 fp-8=3Dmmmm???? fp-16=3Dmap_value fp-24=3Dptr_
; int BPF_PROG(exec, struct linux_binprm *bprm) {
34: (bf) r7 =3D r1
; (void) bpf_probe_read_user(buf, read_size, src);
35: (bc) w2 =3D w8
36: (a5) if r8 < 0x1000 goto pc-17

from 36 to 20: R0_w=3Dinv(id=3D0) R1_w=3Dinv2097152 R2_w=3Dinv(id=3D0,umax_=
value=3D266342399,var_off=3D(0x0; 0xfffffff)) R6=3Dinv(id=3D2,umin_value=3D=
2093057,umax_value=3D268435455,var_off=3D(0x0; 0xfffffff)) R7_w=3Dinv209715=
2 R8_w=3Dinv(id=3D0,umax_value=3D4095,var_off=3D(0x0; 0xfff)) R9_w=3DinvP51=
1 R10=3Dfp0 fp-8=3Dmmmm???? fp-16=3Dmap_value fp-24=3Dptr_
; void *src =3D (void *)(char *)bprm->p + offset;
20: (79) r1 =3D *(u64 *)(r10 -24)
21: (79) r3 =3D *(u64 *)(r1 +24)
; uint64_t read_size =3D args_size - offset;
22: (0f) r3 +=3D r7
23: (07) r3 +=3D -4096
; (void) bpf_probe_read_user(buf, read_size, src);
24: (79) r1 =3D *(u64 *)(r10 -16)
25: (85) call bpf_probe_read_user#112
 R0_w=3Dinv(id=3D0) R1_w=3Dmap_value(id=3D0,off=3D0,ks=3D4,vs=3D4096,imm=3D=
0) R2_w=3Dinv(id=3D0,umax_value=3D266342399,var_off=3D(0x0; 0xfffffff)) R3_=
w=3Dinv(id=3D0) R6=3Dinv(id=3D2,umin_value=3D2093057,umax_value=3D268435455=
,var_off=3D(0x0; 0xfffffff)) R7_w=3Dinv2097152 R8_w=3Dinv(id=3D0,umax_value=
=3D4095,var_off=3D(0x0; 0xfff)) R9_w=3DinvP511 R10=3Dfp0 fp-8=3Dmmmm???? fp=
-16=3Dmap_value fp-24=3Dptr_
 R0_w=3Dinv(id=3D0) R1_w=3Dmap_value(id=3D0,off=3D0,ks=3D4,vs=3D4096,imm=3D=
0) R2_w=3Dinv(id=3D0,umax_value=3D266342399,var_off=3D(0x0; 0xfffffff)) R3_=
w=3Dinv(id=3D0) R6=3Dinv(id=3D2,umin_value=3D2093057,umax_value=3D268435455=
,var_off=3D(0x0; 0xfffffff)) R7_w=3Dinv2097152 R8_w=3Dinv(id=3D0,umax_value=
=3D4095,var_off=3D(0x0; 0xfff)) R9_w=3DinvP511 R10=3Dfp0 fp-8=3Dmmmm???? fp=
-16=3Dmap_value fp-24=3Dptr_
invalid access to map value, value_size=3D4096 off=3D0 size=3D266342399
R1 min value is outside of the allowed memory range
processed 9239 insns (limit 1000000) max_states_per_insn 4 total_states 133=
 peak_states 133 mark_read 2

This seems like it must be a common pitfall, any idea what we can do to fix=
 it
and avoid it in future? Am I misunderstanding the issue?

Cheers,
Brendan

---
 .../selftests/bpf/prog_tests/example.c        | 17 ++++++++
 tools/testing/selftests/bpf/progs/example.c   | 42 +++++++++++++++++++
 2 files changed, 59 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/example.c
 create mode 100644 tools/testing/selftests/bpf/progs/example.c

diff --git a/tools/testing/selftests/bpf/prog_tests/example.c b/tools/testi=
ng/selftests/bpf/prog_tests/example.c
new file mode 100644
index 000000000000..9c36858019b3
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/example.c
@@ -0,0 +1,17 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <test_progs.h>
+
+#include "example.skel.h"
+
+void test_example(void)
+{
+	struct example *skel;
+	__u32 duration =3D 0;
+
+	skel =3D example__open_and_load();
+	if (CHECK(!skel, "skel_load", "couldn't load program\n"))
+		return;
+
+	example__destroy(skel);
+}
diff --git a/tools/testing/selftests/bpf/progs/example.c b/tools/testing/se=
lftests/bpf/progs/example.c
new file mode 100644
index 000000000000..6c90060e92e0
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/example.c
@@ -0,1 +1,42 @@
+#include "vmlinux.h"
+
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+
+char _license[] SEC("license") =3D "GPL";
+
+#define CHUNK_LEN (uint64_t)4096
+struct {
+  __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
+  __uint(key_size, sizeof(int));
+  __uint(value_size, CHUNK_LEN);
+  __uint(max_entries, 1);
+} buf_map SEC(".maps");
+
+SEC("lsm/bprm_committed_creds")
+int BPF_PROG(exec, struct linux_binprm *bprm) {
+  /* Actual value doesn't make sense here, just picking something unknown =
to the
+   * verifier that produces simple disassembly
+   */
+  uint64_t args_size =3D bprm->argc & 0xFFFFFFF;
+  int map_key =3D 0;
+  void *buf =3D bpf_map_lookup_elem(&buf_map, &map_key);
+  uint64_t offset =3D 0;
+  if (!buf)
+    return 0;
+
+  for (int i =3D 0; i < 512 && offset < args_size; i++) {
+    void *src =3D (void *)(char *)bprm->p + offset;
+    uint64_t read_size =3D args_size - offset;
+
+    if (read_size > CHUNK_LEN) {
+      read_size =3D CHUNK_LEN;
+    }
+
+    (void) bpf_probe_read_user(buf, read_size, src);
+
+    offset +=3D CHUNK_LEN;
+  }
+
+  return 0;
+}
--
2.31.1.368.gbe11c130af-goog