Received-SPF: pass (google.com: domain of linux-kernel+bounces-441-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1;
Precedence: bulk
MIME-Version: 1.0
References: <CACkBjsbj4y4EhqpV-ZVt645UtERJRTxfEab21jXD1ahPyzH4_g@mail.gmail.com>
 <CAEf4BzZ0xidVCqB47XnkXcNhkPWF6_nTV7yt+_Lf0kcFEut2Mg@mail.gmail.com>
 <CACkBjsaEQxCaZ0ERRnBXduBqdw3MXB5r7naJx_anqxi0Wa-M_Q@mail.gmail.com>
 <480a5cfefc23446f7c82c5b87eef6306364132b9.camel@gmail.com>
 <917DAD9F-8697-45B8-8890-D33393F6CDF1@gmail.com> <9dee19c7d39795242c15b2f7aa56fb4a6c3ebffa.camel@gmail.com>
 <73d021e3f77161668aae833e478b210ed5cd2f4d.camel@gmail.com>
 <CAEf4BzYuV3odyj8A77ZW8H9jyx_YLhAkSiM+1hkvtH=OYcHL3w@mail.gmail.com>
 <526d4ac8f6788d3323d29fdbad0e0e5d09a534db.camel@gmail.com>
 <2b49b96de9f8a1cd6d78cc5aebe7c35776cd2c19.camel@gmail.com>
 <CAADnVQ+RVT1pO1hTzMawdkfc9B0xAxas2XmSk6+_EiqX9Xy9Ug@mail.gmail.com> <66b2a6c45045c207d8452ad3b5786a9dc0082d79.camel@gmail.com>
In-Reply-To: <66b2a6c45045c207d8452ad3b5786a9dc0082d79.camel@gmail.com>
From: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Date: Thu, 14 Dec 2023 21:20:43 -0800
Message-ID: <CAEf4BzaTTv7oP2vcfVYXjUnA958MqohkRDJ9J7qOCtGfpijROw@mail.gmail.com>
Subject: Re: [Bug Report] bpf: incorrectly pruning runtime execution path
To: Eduard Zingerman <eddyz87@gmail.com>
Cc: Alexei Starovoitov <alexei.starovoitov@gmail.com>, Hao Sun <sunhao.th@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-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Thu, Dec 14, 2023 at 6:28=E2=80=AFPM Eduard Zingerman <eddyz87@gmail.com=
> wrote:
>
> On Thu, 2023-12-14 at 18:16 -0800, Alexei Starovoitov wrote:
> [...]
> > > E.g. for the test-case at hand:
> > >
> > >   0: (85) call bpf_get_prandom_u32#7    ; R0=3Dscalar()
> > >   1: (bf) r7 =3D r0                       ; R0=3Dscalar(id=3D1) R7_w=
=3Dscalar(id=3D1)
> > >   2: (bf) r8 =3D r0                       ; R0=3Dscalar(id=3D1) R8_w=
=3Dscalar(id=3D1)
> > >   3: (85) call bpf_get_prandom_u32#7    ; R0=3Dscalar()
> > >   --- checkpoint #1 r7.id =3D 1, r8.id =3D 1 ---
> > >   4: (25) if r0 > 0x1 goto pc+0         ; R0=3Dscalar(smin=3Dsmin32=
=3D0,smax=3Dumax=3Dsmax32=3Dumax32=3D1,...)
> > >   --- checkpoint #2 r7.id =3D 1, r8.id =3D 1 ---
> > >   5: (3d) if r8 >=3D r0 goto pc+3         ; R0=3D1 R8=3D0 | record r8=
.id=3D1 in jump history
> > >   6: (0f) r8 +=3D r8                      ; R8=3D0
> >
> > can we detect that any register link is broken and force checkpoint her=
e?
>
> Should be possible. I'll try this in the morning and check veristat resul=
ts.
>
> By the way, I added some stats collection for find_equal_scalars() and se=
e
> the following results when run on ./test_progs:
> - maximal number of registers with same id per call: 3
> - average number of registers with same id per call: 1.4


What if we keep 8 extra bytes in jump/instruction history and encode
up to 8 linked registers/slots:

1. 1 bit to mark whether it's a src_reg set, or dst_reg set
2. 1 bit to mark whether it's a stack slot or register
3. 6 bits (0..63 values) to record register or slot number

If we ever need more than 8 linked registers, we can just forcefully
some "links" by resetting some IDs?

BTW, is it only conditional jumps that need to record this linked
register sets? Did we previously discuss why we don't need this for
any other operation?