[RFC PATCH bpf-next v2 05/11] bpf: Preserve reg->id of pointer objects after null-check

[Amery Hung <ameryhung@gmail.com>]

Preserve reg->id of pointer objects after null-checking the register so
that children objects derived from it can still refer to it in the new
object relationship tracking mechanism introduced in a later patch. This
change incurs a slight increase in the number of states in one selftest
bpf object, rbtree_search.bpf.o. For Meta bpf objects, the increase of
states is also negligible.

Selftest BPF objects with insns_diff > 0

Insns (A)  Insns (B)  Insns  (DIFF)  States (A)  States (B)  States (DIFF)
---------  ---------  -------------  ----------  ----------  -------------
     7309       7814  +505 (+6.91%)         394         413   +19 (+4.82%)

Meta BPF objects with insns_diff > 0

Insns (A)  Insns (B)  Insns   (DIFF)  States (A)  States (B)  States (DIFF)
---------  ---------  --------------  ----------  ----------  -------------
       52         57     +5 (+9.62%)           5           6   +1 (+20.00%)
       52         57     +5 (+9.62%)           5           6   +1 (+20.00%)
      676        679     +3 (+0.44%)          54          54    +0 (+0.00%)
      289        292     +3 (+1.04%)          20          20    +0 (+0.00%)
       78         82     +4 (+5.13%)           8           8    +0 (+0.00%)
      252        320   +68 (+26.98%)          21          27   +6 (+28.57%)
      252        320   +68 (+26.98%)          21          27   +6 (+28.57%)
      119        126     +7 (+5.88%)           6           7   +1 (+16.67%)
     1119       1128     +9 (+0.80%)          95          96    +1 (+1.05%)
     1128       1137     +9 (+0.80%)          95          96    +1 (+1.05%)
     4380       4465    +85 (+1.94%)         114         118    +4 (+3.51%)
     3093       3170    +77 (+2.49%)          83          88    +5 (+6.02%)
    30181      31224  +1043 (+3.46%)         832         863   +31 (+3.73%)
   237608     237619    +11 (+0.00%)       11670       11671    +1 (+0.01%)
    94832      94836     +4 (+0.00%)        4787        4788    +1 (+0.02%)
   237387     237407    +20 (+0.01%)       11651       11652    +1 (+0.01%)
    94832      94836     +4 (+0.00%)        4787        4788    +1 (+0.02%)
     8103       8108     +5 (+0.06%)         459         459    +0 (+0.00%)
     8076       8079     +3 (+0.04%)         457         457    +0 (+0.00%)
     8177       8197    +20 (+0.24%)         459         460    +1 (+0.22%)
     8083       8086     +3 (+0.04%)         458         458    +0 (+0.00%)
   237608     237619    +11 (+0.00%)       11670       11671    +1 (+0.01%)
    94832      94836     +4 (+0.00%)        4787        4788    +1 (+0.02%)
   237387     237407    +20 (+0.01%)       11651       11652    +1 (+0.01%)
    94832      94836     +4 (+0.00%)        4787        4788    +1 (+0.02%)
     8103       8108     +5 (+0.06%)         459         459    +0 (+0.00%)
     8076       8079     +3 (+0.04%)         457         457    +0 (+0.00%)
     8177       8197    +20 (+0.24%)         459         460    +1 (+0.22%)
     8083       8086     +3 (+0.04%)         458         458    +0 (+0.00%)

Looking into rbtree_search, the reason for such increase is that the
verifier has to explore the main loop shown below for one more iteration
until state pruning decides the current state is safe.

long rbtree_search(void *ctx)
{
	...
	bpf_spin_lock(&glock0);
	rb_n = bpf_rbtree_root(&groot0);
	while (can_loop) {
		if (!rb_n) {
			bpf_spin_unlock(&glock0);
			return __LINE__;
		}

		n = rb_entry(rb_n, struct node_data, r0);
		if (lookup_key == n->key0)
			break;
		if (nr_gc < NR_NODES)
			gc_ns[nr_gc++] = rb_n;
		if (lookup_key < n->key0)
			rb_n = bpf_rbtree_left(&groot0, rb_n);
		else
			rb_n = bpf_rbtree_right(&groot0, rb_n);
	}
	...
}

Below is what the verifier sees at the start of each iteration
(65: may_goto) after preserving id of rb_n. Without id of rb_n, the
verifier stops exploring the loop at iter 16.

           rb_n  gc_ns[15]
iter 15    257   257

iter 16    290   257    rb_n: idmap add 257->290
                        gc_ns[15]: check 257 != 290 --> state not equal

iter 17    325   257    rb_n: idmap add 290->325
                        gc_ns[15]: idmap add 257->257 --> state safe

Signed-off-by: Amery Hung <ameryhung@gmail.com>
---
 kernel/bpf/verifier.c | 13 ++++---------
 1 file changed, 4 insertions(+), 9 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ea10dd611df2..8f9e28901bc4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17014,15 +17014,10 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,
 
 		mark_ptr_not_null_reg(reg);
 
-		if (!reg_may_point_to_spin_lock(reg)) {
-			/* For not-NULL ptr, reg->ref_obj_id will be reset
-			 * in release_reference().
-			 *
-			 * reg->id is still used by spin_lock ptr. Other
-			 * than spin_lock ptr type, reg->id can be reset.
-			 */
-			reg->id = 0;
-		}
+		/*
+		 * reg->id is preserved for object relationship tracking
+		 * and spin_lock lock state tracking
+		 */
 	}
 }
 
-- 
2.47.3