Re: [RFC PATCH v2 bpf-next 0/2] verifier liveness simplification

[Jiong Wang <jiong.wang@netronome.com>]

On 22/08/2018 20:00, Edward Cree wrote:
> The first patch is a simplification of register liveness tracking by using
>  a separate parentage chain for each register and stack slot, thus avoiding
>  the need for logic to handle callee-saved registers when applying read
>  marks.  In the future this idea may be extended to form use-def chains.

Interesting.

This could potentially help efficient code-gen for 32-bit architectures and I
had been thinking some implementations along this line and would like to have
a discussion.

Program description
===
It will be good if we could know one instruction is safe to operate on low
32-bit sub-register only. If this is true:
   - 32-bit arches could save some code-gen.
   - 64-bit arches could utilize 32-bit sub-register instructions.

Algorithm
===
Based on the current verifier code-path-walker, it looks to me we could get
32-bit safety information using the following algorithm:

   1. assume all instructions operate on 32-bit sub-register initially.
   2. link each insn to insns which define its use.
   3. for a register use, if it is a 64-bit write back to memory, or if it is
      a comparison-then-jump based on 64-bit value, or if it is a right shift,
      then consider the use is a 64-bit use, then all its define insns and their
      parents define insns should be marked as need full 64-bit operation.
   4. currently, register read (REG_LIVE_READ) will be propagated to parent
      state when path prune happened, and REG_LIVE_WRITTEN would screen off such
      propagation. We need to propagate 64-bit mark in similar way, but
      REG_LIVE_WRITTEN shouldn't screen off backward 64-bit mark propagation if
      the written reg also used as source reg (this has raised REG_LIVE_READ
      propagation but it is not necessarily indicating 64-bit read) in the same
      instruction.

Implementation
===
And it seems there could be an implementation based on current liveness tracking
infrastructure without dramatic change.

   1. instruction level use->def chain

      - new active_defs array for each call frame to record which insn the active
        define of one register comes from. callee copies active_defs from caller
        for argument registers only, and copies active_def of R0 to caller when
        exit.

        struct bpf_func_state {
          ...
          s16 active_defs[__MAX_BPF_REG];

      - new use->def chains for each instruction. one eBPF insn could have two
        uses at maximum. also one new boolean "full_ref_def" added to keep the
        final 32-bit safety information. it will be true if this instruction
        needs to operate on full 64-bit.

        bpf_insn_aux_data {
        ...
          struct {
            s16 def[2];
            bool full_ref_def;
          };

   2. Inside mark_reg_read, split SRC_OP to SRC0_OP/SRC1_OP/SRC_OP_64/SRC1_OP_64
      to indicate one register read if from the first or second use slot of this
      instruction, and to indicate whether the read is on full 64-bit which will
      only be true if the read is for 64-bit write back to memory, or 64-bit
      comparison-then-jump, or bit right shift means 64-bit.

      Build use->def chain for any read, but do 64-bit backward propagation
      for 64-bit read only. The propagation is to set full_ref_def to true for
      def and parent defs of the 64-bit read.

    3. Need new bpf_reg_liveness enum, REG_LIVE_READ64 to indicate there is
       64-bit access to one register in the pruned path, and need
       REG_LIVE_WRITTEN64 to indicate a write that is REG_LIVE_WRITTEN but should
       not screen backward propagate 64-bit read info.

        #define REG_LIVE_NONE          0
        #define REG_LIVE_READ          BIT(0)
        #define REG_LIVE_READ64        BIT(1)
        #define REG_LIVE_WRITTEN       BIT(2)
        #define REG_LIVE_WRITTEN64     BIT(3)

I might have missed something in above thoughts, would appreciate reviews and
suggestions. I will also send out some concrete patches later.

Regards,
Jiong