On Thu, 2023-06-08 at 15:37 -0700, Andrii Nakryiko wrote:
> On Thu, Jun 8, 2023 at 1:58 PM Eduard Zingerman <eddyz87@xxxxxxxxx> wrote:
> >
> > On Thu, 2023-06-08 at 22:05 +0300, Eduard Zingerman wrote:
> > [...]
> > > > Hm.. It's clever and pretty minimal, I like it. We are basically
> > > > allocating virtual ID for SCALAR that doesn't have id, just to make
> > > > sure we get a conflict if the SCALAR with ID cannot be mapped into two
> > > > different SCALARs, right?
> > > >
> > > > The only question would be if it's safe to do that for case when
> > > > old_reg->id != 0 and cur_reg->id == 0? E.g., if in old (verified)
> > > > state we have r6.id = r7.id = 123, and in new state we have r6.id = 0
> > > > and r7.id = 0, then your implementation above will say that states are
> > > > equivalent. But are they, given there is a link between r6 and r7 that
> > > > might be required for correctness. Which we don't have in current
> > > > state.
> > >
> > > You mean the other way around, rold.id == 0, rcur.id != 0, right?
> > > (below 0/2 means: original value 0, replaced by new id 2).
>
> no, I actually meant what I wrote, but I didn't realize that
> check_ids() is kind of broken... Because it shouldn't allow the same
> ID from cur state to be mapped to two different IDs in old state,
> should it?
IDs are used for several things, and it looks like the answer might vary.
For example, I looked at mark_ptr_or_null_regs():
- it is called when conditional of form (ptr == NULL) is checked;
- it marks every register with pointer having same ID as ptr as
null/non-null;
- when register is marked not null ID is removed (not for locks but
ignore it for now).
Assume r6 and r7 are both PTR_MAYBE_NULL and ID assignments look as
follows:
old cur
r6.id 1 3
r7.id 2 3
'old' is safe, which means the following:
- either r6 was not accessed or it was guarded by (r6 == NULL)
- either r7 was not accessed or it was guarded by (r7 == NULL)
In both cases it should be ok, if r6 and r7 are in fact the same
pointer. It would be checked to be not NULL two times but that's fine.
So, I'd say that 'cur' is a special case of 'old' and check_ids() is
correct for it. But this is the same argument I used for scalars and
you were not convinced :)
Need to examine each use case carefully.
> > > (1) old cur
> > > r6.id 0/2 1
> > > r7.id 0/3 1 check_ids returns true
>
> I think this should be rejected.
That's what we agreed upon when decided not to do !rold->id, so yes.
> > > (2) old cur
> > > r6.id 1 0/2
> > > r7.id 1 0/3 check_ids returns false
>
> And this should be rejected.
For sure.
> > > Also, (1) is no different from (3):
> > >
> > > (3) old cur
> > > r6.id 1 3
> > > r7.id 2 3 check_ids returns true
>
> And this definitely should be rejected.
Same as (1).
> The only situation that might not be rejected would be:
>
> old cur
> r6.id 0/1 3
> r7.id. 0/2 4
>
> And perhaps this one is ok as well?
>
> old cur
> r6.id 3 0/1
> r7.id. 4 0/2
I think these two should be accepted.
[...]
> > +static bool check_scalar_ids(struct bpf_verifier_env *env, u32 old_id, u32 cur_id,
> > + struct bpf_id_pair *idmap)
> > +{
> > + unsigned int i;
> > +
> > + old_id = old_id ? old_id : env->id_gen++;
> > + cur_id = cur_id ? cur_id : env->id_gen++;
> > +
> > + for (i = 0; i < BPF_ID_MAP_SIZE; i++) {
> > + if (!idmap[i].old) {
> > + /* Reached an empty slot; haven't seen this id before */
> > + idmap[i].old = old_id;
> > + idmap[i].cur = cur_id;
> > + return true;
> > + }
> > + if (idmap[i].old == old_id)
> > + return idmap[i].cur == cur_id;
> > + if (idmap[i].cur == cur_id)
> > + return false;
>
> I think this should just be added to existing check_ids(), I think
> it's a bug that we don't check this condition today in check_ids().
>
> But I'd say let's land fixes you have right now. And then work on
> fixing and optimizing scala ID checks separately. We are doing too
> many things at the same time :(
Ok, will post V4 with these changes and examine other cases later.
Thanks again for the discussion.
[...]
