On Wed, 2024-02-28 at 11:58 -0800, Andrii Nakryiko wrote:
[...]
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index cbfb235984c8..26e32555711c 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -361,6 +361,7 @@ struct bpf_jmp_history_entry {
> > u32 prev_idx : 22;
> > /* special flags, e.g., whether insn is doing register stack spill/load */
> > u32 flags : 10;
> > + u64 equal_scalars;
>
> nit: should we call this concept as a bit more generic "linked
> registers" instead of "equal scalars"?
It's a historical name for the feature and it is present in a few commit and tests.
Agree that "linked_registers" is better in current context.
A bit reluctant but can change it here.
[...]
> I'm wondering if this pop/push set of primitives is the best approach?
I kinda like it :)
> What if we had pack/unpack operations, where for various checking
> logic we'd be working with "unpacked" representation, e.g., something
> like this:
>
> struct linked_reg_set {
> int cnt;
> struct {
Will need a name here, otherwise iteration would be somewhat inconvenient.
Suppose 'struct reg_or_spill'.
> int frameno;
> union {
> int spi;
> int regno;
> };
> bool is_set;
> bool is_reg;
> } reg_set[6];
> };
>
> bt_set_equal_scalars() could accept `struct linked_reg_set*` instead
> of bitmask itself. Same for find_equal_scalars().
For clients it would be
while (equal_scalars_pop(&equal_scalars, &fr, &spi, &is_reg)) {
if ((is_reg && bt_is_frame_reg_set(bt, fr, spi)) ||
(!is_reg && bt_is_frame_slot_set(bt, fr, spi)))
...
}
--- vs ---
for (i = 0; i < equal_scalars->cnt; ++i) {
struct reg_or_spill *r = equal_scalars->reg_set[i];
if ((r->is_reg && bt_is_frame_reg_set(bt, r->frameno, r->regno)) ||
(!r->is_reg && bt_is_frame_slot_set(bt, r->frameno, r->spi)))
...
}
I'd say, no significant difference.
> I think even implementation of packing/unpacking would be more
> straightforward and we won't even need all those ES_xxx consts (or at
> least fewer of them).
>
> WDYT?
I wouldn't say it simplifies packing/unpacking much.
Below is the code using new data structure and it's like
59 lines old version vs 56 lines new version.
--- 8< ----------------------------------------------------------------
struct reg_or_spill {
int frameno;
union {
int spi;
int regno;
};
bool is_reg;
};
struct linked_reg_set {
int cnt;
struct reg_or_spill reg_set[6];
};
/* Pack one history entry for equal scalars as 10 bits in the following format:
* - 3-bits frameno
* - 6-bits spi_or_reg
* - 1-bit is_reg
*/
static u64 linked_reg_set_pack(struct linked_reg_set *s)
{
u64 val = 0;
int i;
for (i = 0; i < s->cnt; ++i) {
struct reg_or_spill *r = &s->reg_set[i];
u64 tmp = 0;
tmp |= r->frameno & ES_FRAMENO_MASK;
tmp |= (r->spi & ES_SPI_MASK) << ES_SPI_OFF;
tmp |= (r->is_reg ? 1 : 0) << ES_IS_REG_OFF;
val <<= ES_ENTRY_BITS;
val |= tmp;
}
val <<= ES_SIZE_BITS;
val |= s->cnt;
return val;
}
static void linked_reg_set_unpack(u64 val, struct linked_reg_set *s)
{
int i;
s->cnt = val & ES_SIZE_MASK;
val >>= ES_SIZE_BITS;
for (i = 0; i < s->cnt; ++i) {
struct reg_or_spill *r = &s->reg_set[i];
r->frameno = val & ES_FRAMENO_MASK;
r->spi = (val >> ES_SPI_OFF) & ES_SPI_MASK;
r->is_reg = (val >> ES_IS_REG_OFF) & 0x1;
val >>= ES_ENTRY_BITS;
}
}
---------------------------------------------------------------- >8 ---
