Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) client-ip=2620:137:e000::3:4;
Content-Type: text/plain;
        charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3774.200.91.1.1\))
Subject: Re: [Bug Report] bpf: incorrectly pruning runtime execution path
From:   Hao Sun <sunhao.th@gmail.com>
In-Reply-To: <480a5cfefc23446f7c82c5b87eef6306364132b9.camel@gmail.com>
Date:   Thu, 14 Dec 2023 10:38:01 +0100
Cc:     Andrii Nakryiko <andrii.nakryiko@gmail.com>,
        Alexei Starovoitov <ast@kernel.org>,
        Andrii Nakryiko <andrii@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        bpf <bpf@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Content-Transfer-Encoding: quoted-printable
Message-Id: <917DAD9F-8697-45B8-8890-D33393F6CDF1@gmail.com>
References: <CACkBjsbj4y4EhqpV-ZVt645UtERJRTxfEab21jXD1ahPyzH4_g@mail.gmail.com>
 <CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com>
 <CACkBjsaEQxCaZ0ERRnBXduBqdw3MXB5r7naJx_anqxi0Wa-M_Q@mail.gmail.com>
 <480a5cfefc23446f7c82c5b87eef6306364132b9.camel@gmail.com>
To:     Eduard Zingerman <eddyz87@gmail.com>
Precedence: bulk


> On 14 Dec 2023, at 12:35=E2=80=AFAM, Eduard Zingerman =
<eddyz87@gmail.com> wrote:
>=20
> On Wed, 2023-12-13 at 11:25 +0100, Hao Sun wrote:
> [...]
>=20
>> I tried to convert the repro to a valid test case in inline asm, but =
seems
>> JSET (if r0 & 0xfffffffe goto pc+3) is currently not supported in =
clang-17.
>> Will try after clang-18 is released.
>>=20
>> #30 is expected to be executed, see below where everything after ";" =
is
>> the runtime value:
>>   ...
>>   6: (36) if w8 >=3D 0x69 goto pc+1    ; w8 =3D 0xbe, always taken
>>   ...
>>  11: (45) if r0 & 0xfffffffe goto pc+3  ; r0 =3D 0x616, taken
>>  ...
>>  18: (56) if w8 !=3D 0xf goto pc+3     ; w8 not touched, taken
>>  ...
>>  23: (bf) r5 =3D r8     ; w5 =3D 0xbe
>>  24: (18) r2 =3D 0x4
>>  26: (7e) if w8 s>=3D w0 goto pc+5    ; non-taken
>>  27: (4f) r8 |=3D r8
>>  28: (0f) r8 +=3D r8
>>  29: (d6) if w5 s<=3D 0x1d goto pc+2  ; non-taken
>>  30: (18) r0 =3D 0x4      ; executed
>>=20
>> Since the verifier prunes at #26, #30 is dead and eliminated. So, #30
>> is executed after manually commenting out the dead code rewrite pass.
>>=20
>> =46rom my understanding, I think r0 should be marked as precise when
>> first backtrack from #29, because r5 range at this point depends on =
w0
>> as r8 and r5 share the same id at #26.
>=20
> Hi Hao, Andrii,
>=20
> I converted program in question to a runnable test, here is a link to
> the patch adding it and disabling dead code removal:
> https://gist.github.com/eddyz87/e888ad70c947f28f94146a47e33cd378
>=20
> Run the test as follows:
>  ./test_progs -vvv -a verifier_and/pruning_test
>=20
> And inspect the retval:
>  do_prog_test_run:PASS:bpf_prog_test_run 0 nsec
>  run_subtest:FAIL:647 Unexpected retval: 1353935089 !=3D 4
>=20

Thanks for the runnable test!=20

The reason why retval checks fails is that the way you disable dead
code removal pass is not complete. Disable opt_remove_dead_code()
just prevent the instruction #30 from being removed, but also note
opt_hard_wire_dead_code_branches(), which convert conditional jump
into unconditional one, so #30 is still skipped.


> Note that I tried this test with two functions:
> - bpf_get_current_cgroup_id, with this function I get retval 2, not 4 =
:)
> - bpf_get_prandom_u32, with this function I get a random retval each =
time.
>=20
> What is the expectation when 'bpf_get_current_cgroup_id' is used?
> That it is some known (to us) number, but verifier treats it as =
unknown scalar?
>=20

Either one would work, but to make #30 always taken, r0 should be
non-zero.=