bpf: per-register parent pointers

By giving each register its own liveness chain, we elide the skip_callee() logic. Instead, each register's parent is the state it inherits from; both check_func_call() and prepare_func_exit() automatically connect reg states to the correct chain since when they copy the reg state across (r1-r5 into the callee as args, and r0 out as the return value) they also copy the parent pointer.

---
Ed,

I've started analyzing this old patch and it looks great.
I'd like to apply it, but I see the difference in insn_processed.
Several cilium tests show favorable difference towards new liveness approach.
selftests/bpf/test_xdp_noinline.o also shows the difference.
I'm struggling to see why this patch would make such difference.
Could you please help me analyze why such difference exists?
In particular if you hack test_progs.c to run only test_xdp_noinline
with verifier log_level=1 you will see this delta:
-from 237 to 273: frame2: R0=inv1 R1=pkt(id=0,off=54,r=14,imm=0) R2=fp-95,call_13 R3=fp-94,call_13 R4=pkt(id=0,off=0,r=14,imm=0) R5=pkt_end(id=0,off=0,imm=0) R6=fp-56,call_13 R10=fp0,call_44 -273: (95) exit
-returning from callee:
- frame2: R0=inv1 R1=pkt(id=0,off=54,r=14,imm=0) R2=fp-95,call_13 R3=fp-94,call_13 R4=pkt(id=0,off=0,r=14,imm=0) R5=pkt_end(id=0,off=0,imm=0) R6=fp-56,call_13 R10=fp0,call_44 -to caller at 45:
- frame1: R0=inv1 R6=pkt(id=0,off=0,r=14,imm=0) R7=inv1 R9=pkt_end(id=0,off=0,imm=0) R10=fp0,call_13 fp-8=0 fp-24=0 fp-32=0 fp-40=0 fp-48=0 fp-56=0 fp-64=0 fp-72=0 fp-80=0 fp-112=ctx -
-from 273 to 45: frame1: R0=inv1 R6=pkt(id=0,off=0,r=14,imm=0) R7=inv1 R9=pkt_end(id=0,off=0,imm=0) R10=fp0,call_13 fp-8=0 fp-24=0 fp-32=0 fp-40=0 fp-48=0 fp-56=0 fp-64=0 fp-72=0 fp-80=0 fp-112=ctx -45: (05) goto pc+9
-55: safe
+from 237 to 273: safe

-processed 2971 insns (limit 131072), stack depth 0+112+0+0+8+0+4+24+8+16+0+16+8+0+0+0+0+0+32+0+0 -test_xdp_noinline:PASS:ipv4 3292 nsec
-test_xdp_noinline:PASS:ipv6 3105 nsec
+processed 2957 insns (limit 131072), stack depth 0+112+0+0+8+0+4+24+8+16+0+16+8+0+0+0+0+0+32+0+0 +test_xdp_noinline:PASS:ipv4 2922 nsec
+test_xdp_noinline:PASS:ipv6 4296 nsec

Did we miss liveness propagation before or there is a bug in this patch? Thanks

 include/linux/bpf_verifier.h |   8 +-
 kernel/bpf/verifier.c        | 180 ++++++++---------------------------
 2 files changed, 45 insertions(+), 143 deletions(-)

index 38b04f559ad3..b42b60a83e19 100644
@@ -41,6 +41,7 @@ enum bpf_reg_liveness {
 };
 
 struct bpf_reg_state {
+	/* Ordering of fields matters.  See states_equal() */
 	enum bpf_reg_type type;
 	union {
 		/* valid when type == PTR_TO_PACKET */

@@ -59,7 +60,6 @@ struct bpf_reg_state {
 	 * came from, when one is tested for != NULL.
 	 */
 	u32 id;
-	/* Ordering of fields matters.  See states_equal() */
 	/* For scalar types (SCALAR_VALUE), this represents our knowledge of
 	 * the actual value.
 	 * For pointer types, this represents the variable part of the offset

@@ -76,15 +76,15 @@ struct bpf_reg_state {
 	s64 smax_value; /* maximum possible (s64)value */
 	u64 umin_value; /* minimum possible (u64)value */
 	u64 umax_value; /* maximum possible (u64)value */
+	/* parentage chain for liveness checking */
+	struct bpf_reg_state *parent;
 	/* Inside the callee two registers can be both PTR_TO_STACK like
 	 * R1=fp-8 and R2=fp-8, but one of them points to this function stack
 	 * while another to the caller's stack. To differentiate them 'frameno'
 	 * is used which is an index in bpf_verifier_state->frame[] array
 	 * pointing to bpf_func_state.
-	 * This field must be second to last, for states_equal() reasons.
 	 */
 	u32 frameno;
-	/* This field must be last, for states_equal() reasons. */
 	enum bpf_reg_liveness live;
 };
 

@@ -107,7 +107,6 @@ struct bpf_stack_state {
  */
 struct bpf_func_state {
 	struct bpf_reg_state regs[MAX_BPF_REG];
-	struct bpf_verifier_state *parent;
 	/* index of call instruction that called into this func */
 	int callsite;
 	/* stack frame number of this function state from pov of

@@ -129,7 +128,6 @@ struct bpf_func_state {
 struct bpf_verifier_state {
 	/* call stack tracking */
 	struct bpf_func_state *frame[MAX_CALL_FRAMES];
-	struct bpf_verifier_state *parent;
 	u32 curframe;
 };
 

2.17.1

I'm also confused by it at present, but I am looking into it. -Ed