> On 11 Apr 2019, at 03:52, Jakub Kicinski <jakub.kicinski@xxxxxxxxxxxxx> wrote:
>
> On Wed, 10 Apr 2019 20:50:19 +0100, Jiong Wang wrote:
>> Register liveness infrastructure doesn't track register read width at the
>> moment, while the width information will be needed for the later 32-bit
>> safety analysis pass.
>>
>> This patch take the first step to split read liveness into REG_LIVE_READ64
>> and REG_LIVE_READ32.
>>
>> Liveness propagation code are updated accordingly. They are taught to
>> understand how to propagate REG_LIVE_READ64 and REG_LIVE_READ32 at the same
>> propagation iteration. For example, "mark_reg_read" now propagate "flags"
>> which could be multiple read bits instead of the single REG_LIVE_READ64.
>>
>> A write still screen off all width of reads.
>>
>> Signed-off-by: Jiong Wang <jiong.wang@xxxxxxxxxxxxx>
>> ---
>> include/linux/bpf_verifier.h | 8 +--
>> kernel/bpf/verifier.c | 119 +++++++++++++++++++++++++++++++++++++++----
>> 2 files changed, 113 insertions(+), 14 deletions(-)
>>
>> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
>> index b3ab61f..fba0ebb 100644
>> --- a/include/linux/bpf_verifier.h
>> +++ b/include/linux/bpf_verifier.h
>> @@ -36,9 +36,11 @@
>> */
>> enum bpf_reg_liveness {
>> REG_LIVE_NONE = 0, /* reg hasn't been read or written this branch */
>> - REG_LIVE_READ, /* reg was read, so we're sensitive to initial value */
>> - REG_LIVE_WRITTEN, /* reg was written first, screening off later reads */
>> - REG_LIVE_DONE = 4, /* liveness won't be updating this register anymore */
>> + REG_LIVE_READ32 = 0x1, /* reg was read, so we're sensitive to initial value */
>> + REG_LIVE_READ64 = 0x2, /* likewise, but full 64-bit content matters */
>> + REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,
>> + REG_LIVE_WRITTEN = 0x4, /* reg was written first, screening off later reads */
>> + REG_LIVE_DONE = 0x8, /* liveness won't be updating this register anymore */
>> };
>>
>> struct bpf_reg_state {
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index bd30a65..44e4278 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -1135,7 +1135,7 @@ static int check_subprogs(struct bpf_verifier_env *env)
>> */
>> static int mark_reg_read(struct bpf_verifier_env *env,
>> const struct bpf_reg_state *state,
>> - struct bpf_reg_state *parent)
>> + struct bpf_reg_state *parent, u8 flags)
>> {
>> bool writes = parent == state->parent; /* Observe write marks */
>> int cnt = 0;
>> @@ -1150,17 +1150,17 @@ static int mark_reg_read(struct bpf_verifier_env *env,
>> parent->var_off.value, parent->off);
>> return -EFAULT;
>> }
>> - if (parent->live & REG_LIVE_READ)
>> + if ((parent->live & REG_LIVE_READ) == flags)
>> /* The parentage chain never changes and
>> - * this parent was already marked as LIVE_READ.
>> + * this parent was already marked with all read bits.
>
> Do we have to propagate all read bits? Read64 is strictly stronger
> than read32, as long as read64 is set on the parent we should be good?
We should be good, but I doubt there is value to differentiate on this in this
kind of HOT function.
>
>> * There is no need to keep walking the chain again and
>> - * keep re-marking all parents as LIVE_READ.
>> + * keep re-marking all parents with reads bits in flags.
>> * This case happens when the same register is read
>> * multiple times without writes into it in-between.
>> */
>> break;
>> /* ... then we depend on parent's value */
>> - parent->live |= REG_LIVE_READ;
>> + parent->live |= flags;
>> state = parent;
>> parent = state->parent;
>> writes = true;
>
>> @@ -6196,12 +6286,19 @@ static int propagate_liveness_reg(struct bpf_verifier_env *env,
>> struct bpf_reg_state *reg,
>> struct bpf_reg_state *parent_reg)
>> {
>> + u8 parent_bits = parent_reg->live & REG_LIVE_READ;
>> + u8 bits = reg->live & REG_LIVE_READ;
>> + u8 bits_diff = parent_bits ^ bits;
>> + u8 bits_prop = bits_diff & bits;
>> int err;
>>
>> - if (parent_reg->live & REG_LIVE_READ || !(reg->live & REG_LIVE_READ))
>> + /* "reg" and "parent_reg" has the same read bits, or the bit doesn't
>> + * belong to "reg".
>> + */
>> + if (!bits_diff || !bits_prop)
>
> bits_prop is a subset of bits_diff, no? !bits_prop is always true
> if !bits_diff is true, no need to check both.
Bits_prop is a subset of bits_diff WHEN it comes from “reg", we don’t want to
do the propagation when the diff comes from “parent_reg”, so, we need to check
both.
Regards,
Jiong
>
>> return 0;
>>
>> - err = mark_reg_read(env, reg, parent_reg);
>> + err = mark_reg_read(env, reg, parent_reg, bits_prop);
>> if (err)
>> return err;
