Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.38 as permitted sender) client-ip=23.128.96.38;
MIME-Version: 1.0
References: <CACkBjsY3vMLVVO0zHd+CRcQPdykDhXv8-f2oD82+Jk5KJpq_8w@mail.gmail.com>
In-Reply-To: <CACkBjsY3vMLVVO0zHd+CRcQPdykDhXv8-f2oD82+Jk5KJpq_8w@mail.gmail.com>
From:   Andrii Nakryiko <andrii.nakryiko@gmail.com>
Date:   Wed, 1 Nov 2023 13:57:33 -0700
Message-ID: <CAEf4BzbDK15myKbN4sM+cxFvfWCNjthJuFZf81k6OEBpaC124g@mail.gmail.com>
Subject: Re: bpf: incorrectly reject program with `back-edge insn from 7 to 8`
To:     Hao Sun <sunhao.th@gmail.com>
Cc:     Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        John Fastabend <john.fastabend@gmail.com>,
        Andrii Nakryiko <andrii@kernel.org>,
        Martin KaFai Lau <martin.lau@linux.dev>,
        Song Liu <song@kernel.org>,
        Yonghong Song <yonghong.song@linux.dev>,
        KP Singh <kpsingh@kernel.org>,
        Stanislav Fomichev <sdf@google.com>,
        Hao Luo <haoluo@google.com>, Jiri Olsa <jolsa@kernel.org>,
        Mykola Lysenko <mykolal@fb.com>, Shuah Khan <shuah@kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        bpf <bpf@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Wed, Nov 1, 2023 at 6:56=E2=80=AFAM Hao Sun <sunhao.th@gmail.com> wrote:
>
> Hi,
>
> The verifier incorrectly rejects the following prog in check_cfg() when
> loading with root with confusing log `back-edge insn from 7 to 8`:
>   /* 0: r9 =3D 2
>    * 1: r3 =3D 0x20
>    * 2: r4 =3D 0x35
>    * 3: r8 =3D r4
>    * 4: goto+3
>    * 5: r9 -=3D r3
>    * 6: r9 -=3D r4
>    * 7: r9 -=3D r8
>    * 8: r8 +=3D r4
>    * 9: if r8 < 0x64 goto-5
>    * 10: r0 =3D r9
>    * 11: exit
>    * */
>   BPF_MOV64_IMM(BPF_REG_9, 2),
>   BPF_MOV64_IMM(BPF_REG_3, 0x20),
>   BPF_MOV64_IMM(BPF_REG_4, 0x35),
>   BPF_MOV64_REG(BPF_REG_8, BPF_REG_4),
>   BPF_JMP_IMM(BPF_JA, 0, 0, 3),
>   BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_3),
>   BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_4),
>   BPF_ALU64_REG(BPF_SUB, BPF_REG_9, BPF_REG_8),
>   BPF_ALU64_REG(BPF_ADD, BPF_REG_8, BPF_REG_4),
>   BPF_JMP32_IMM(BPF_JLT, BPF_REG_8, 0x68, -5),
>   BPF_MOV64_REG(BPF_REG_0, BPF_REG_9),
>   BPF_EXIT_INSN()
>
> -------- Verifier Log --------
> func#0 @0
> back-edge from insn 7 to 8
> processed 0 insns (limit 1000000) max_states_per_insn 0 total_states 0
> peak_states 0 mark_read 0
>
> This is not intentionally rejected, right?

The way you wrote it, with goto +3, yes, it's intentional. Note that
you'll get different results in privileged and unprivileged modes.
Privileged mode allows "bounded loops" logic, so it doesn't
immediately reject this program, and then later sees that r8 is always
< 0x64, so program is correct.

But in unprivileged mode the rules are different, and this conditional
back edge is not allowed, which is probably what you are getting.

It's actually confusing and your "back-edge from insn 7 to 8" is out
of date and doesn't correspond to your program, you should see
"back-edge from insn 11 to 7", please double check.

Anyways, while I was looking into this, I realized that ldimm64 isn't
handled exactly correctly in check_cfg(), so I just sent a fix. It
also adds a nicer detection of jumping into the middle of the ldimm64
instruction, which I believe is something you were advocating for.

>
> Best
> Hao