[PATCH bpf 0/4] bpf: track changes_pkt_data property for global functions

[PATCH bpf 0/4] bpf: track changes_pkt_data property for global functions

[Eduard Zingerman]

Nick Zavaritsky reported [0] a bug in verifier, where the following
unsafe program is not rejected:

    __attribute__((__noinline__))
    long skb_pull_data(struct __sk_buff *sk, __u32 len)
    {
        return bpf_skb_pull_data(sk, len);
    }

    SEC("tc")
    int test_invalidate_checks(struct __sk_buff *sk)
    {
        int *p = (void *)(long)sk->data;
        if ((void *)(p + 1) > (void *)(long)sk->data_end) return TCX_DROP;
        skb_pull_data(sk, 0);
        /* not safe, p is invalid after bpf_skb_pull_data call */
        *p = 42;
        return TCX_PASS;
    }

This happens because verifier does not track package invalidation
effect of global sub-programs.

This patch-set fixes the issue by modifying check_cfg() to compute
whether or not each sub-program calls (directly or indirectly)
helper invalidating packet pointers.

[0] https://lore.kernel.org/bpf/0498CA22-5779-4767-9C0C-A9515CEA711F@gmail.com/

Eduard Zingerman (4):
  bpf: add find_containing_subprog() utility function
  bpf: refactor bpf_helper_changes_pkt_data to use helper number
  bpf: track changes_pkt_data property for global functions
  selftests/bpf: test for changing packet data from global functions

 include/linux/bpf_verifier.h                  |  1 +
 include/linux/filter.h                        |  2 +-
 kernel/bpf/core.c                             |  2 +-
 kernel/bpf/verifier.c                         | 62 ++++++++++++++++--
 net/core/filter.c                             | 63 +++++++++----------
 .../selftests/bpf/progs/verifier_sock.c       | 28 +++++++++
 6 files changed, 115 insertions(+), 43 deletions(-)

-- 
2.47.0

[PATCH bpf 1/4] bpf: add find_containing_subprog() utility function

[Eduard Zingerman]

Add a utility function, looking for a subprogram containing a given
instruction index, rewrite find_subprog() to use this function.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 kernel/bpf/verifier.c | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 01fbef9576e0..277c1892bb9a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2597,16 +2597,36 @@ static int cmp_subprogs(const void *a, const void *b)
 	       ((struct bpf_subprog_info *)b)->start;
 }
 
+/* Find subprogram that contains instruction at 'off' */
+static struct bpf_subprog_info *find_containing_subprog(struct bpf_verifier_env *env, int off)
+{
+	struct bpf_subprog_info *vals = env->subprog_info;
+	int l, r, m;
+
+	if (off >= env->prog->len || off < 0 || env->subprog_cnt == 0)
+		return NULL;
+
+	l = 0;
+	r = env->subprog_cnt - 1;
+	while (l < r) {
+		m = l + (r - l + 1) / 2;
+		if (vals[m].start <= off)
+			l = m;
+		else
+			r = m - 1;
+	}
+	return &vals[l];
+}
+
+/* Find subprogram that starts exactly at 'off' */
 static int find_subprog(struct bpf_verifier_env *env, int off)
 {
 	struct bpf_subprog_info *p;
 
-	p = bsearch(&off, env->subprog_info, env->subprog_cnt,
-		    sizeof(env->subprog_info[0]), cmp_subprogs);
-	if (!p)
+	p = find_containing_subprog(env, off);
+	if (!p || p->start != off)
 		return -ENOENT;
 	return p - env->subprog_info;
-
 }
 
 static int add_subprog(struct bpf_verifier_env *env, int off)
-- 
2.47.0

[PATCH bpf 2/4] bpf: refactor bpf_helper_changes_pkt_data to use helper number

[Eduard Zingerman]

Use BPF helper number instead of function pointer in
bpf_helper_changes_pkt_data(). This would simplify usage of this
function in verifier.c:check_cfg() (in a follow-up patch),
where only helper number is easily available and there is no real need
to lookup helper proto.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/filter.h |  2 +-
 kernel/bpf/core.c      |  2 +-
 kernel/bpf/verifier.c  |  2 +-
 net/core/filter.c      | 63 +++++++++++++++++++-----------------------
 4 files changed, 31 insertions(+), 38 deletions(-)

diff --git a/include/linux/filter.h b/include/linux/filter.h
index 3a21947f2fd4..0477254bc2d3 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -1122,7 +1122,7 @@ bool bpf_jit_supports_insn(struct bpf_insn *insn, bool in_arena);
 bool bpf_jit_supports_private_stack(void);
 u64 bpf_arch_uaddress_limit(void);
 void arch_bpf_stack_walk(bool (*consume_fn)(void *cookie, u64 ip, u64 sp, u64 bp), void *cookie);
-bool bpf_helper_changes_pkt_data(void *func);
+bool bpf_helper_changes_pkt_data(enum bpf_func_id func_id);
 
 static inline bool bpf_dump_raw_ok(const struct cred *cred)
 {
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index a2327c4fdc8b..6fa8041d4831 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -2936,7 +2936,7 @@ void __weak bpf_jit_compile(struct bpf_prog *prog)
 {
 }
 
-bool __weak bpf_helper_changes_pkt_data(void *func)
+bool __weak bpf_helper_changes_pkt_data(enum bpf_func_id func_id)
 {
 	return false;
 }
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 277c1892bb9a..ad3f6d28e8e4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10728,7 +10728,7 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 	}
 
 	/* With LD_ABS/IND some JITs save/restore skb from r1. */
-	changes_data = bpf_helper_changes_pkt_data(fn->func);
+	changes_data = bpf_helper_changes_pkt_data(func_id);
 	if (changes_data && fn->arg1_type != ARG_PTR_TO_CTX) {
 		verbose(env, "kernel subsystem misconfigured func %s#%d: r1 != ctx\n",
 			func_id_name(func_id), func_id);
diff --git a/net/core/filter.c b/net/core/filter.c
index 6625b3f563a4..efb75eed2e35 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -7899,42 +7899,35 @@ static const struct bpf_func_proto bpf_tcp_raw_check_syncookie_ipv6_proto = {
 
 #endif /* CONFIG_INET */
 
-bool bpf_helper_changes_pkt_data(void *func)
-{
-	if (func == bpf_skb_vlan_push ||
-	    func == bpf_skb_vlan_pop ||
-	    func == bpf_skb_store_bytes ||
-	    func == bpf_skb_change_proto ||
-	    func == bpf_skb_change_head ||
-	    func == sk_skb_change_head ||
-	    func == bpf_skb_change_tail ||
-	    func == sk_skb_change_tail ||
-	    func == bpf_skb_adjust_room ||
-	    func == sk_skb_adjust_room ||
-	    func == bpf_skb_pull_data ||
-	    func == sk_skb_pull_data ||
-	    func == bpf_clone_redirect ||
-	    func == bpf_l3_csum_replace ||
-	    func == bpf_l4_csum_replace ||
-	    func == bpf_xdp_adjust_head ||
-	    func == bpf_xdp_adjust_meta ||
-	    func == bpf_msg_pull_data ||
-	    func == bpf_msg_push_data ||
-	    func == bpf_msg_pop_data ||
-	    func == bpf_xdp_adjust_tail ||
-#if IS_ENABLED(CONFIG_IPV6_SEG6_BPF)
-	    func == bpf_lwt_seg6_store_bytes ||
-	    func == bpf_lwt_seg6_adjust_srh ||
-	    func == bpf_lwt_seg6_action ||
-#endif
-#ifdef CONFIG_INET
-	    func == bpf_sock_ops_store_hdr_opt ||
-#endif
-	    func == bpf_lwt_in_push_encap ||
-	    func == bpf_lwt_xmit_push_encap)
+bool bpf_helper_changes_pkt_data(enum bpf_func_id func_id)
+{
+	switch (func_id) {
+	case BPF_FUNC_clone_redirect:
+	case BPF_FUNC_l3_csum_replace:
+	case BPF_FUNC_l4_csum_replace:
+	case BPF_FUNC_lwt_push_encap:
+	case BPF_FUNC_lwt_seg6_action:
+	case BPF_FUNC_lwt_seg6_adjust_srh:
+	case BPF_FUNC_lwt_seg6_store_bytes:
+	case BPF_FUNC_msg_pop_data:
+	case BPF_FUNC_msg_pull_data:
+	case BPF_FUNC_msg_push_data:
+	case BPF_FUNC_skb_adjust_room:
+	case BPF_FUNC_skb_change_head:
+	case BPF_FUNC_skb_change_proto:
+	case BPF_FUNC_skb_change_tail:
+	case BPF_FUNC_skb_pull_data:
+	case BPF_FUNC_skb_store_bytes:
+	case BPF_FUNC_skb_vlan_pop:
+	case BPF_FUNC_skb_vlan_push:
+	case BPF_FUNC_store_hdr_opt:
+	case BPF_FUNC_xdp_adjust_head:
+	case BPF_FUNC_xdp_adjust_meta:
+	case BPF_FUNC_xdp_adjust_tail:
 		return true;
-
-	return false;
+	default:
+		return false;
+	}
 }
 
 const struct bpf_func_proto bpf_event_output_data_proto __weak;
-- 
2.47.0

[PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Eduard Zingerman]

When processing calls to certain helpers, verifier invalidates all
packet pointers in a current state. For example, consider the
following program:

    __attribute__((__noinline__))
    long skb_pull_data(struct __sk_buff *sk, __u32 len)
    {
        return bpf_skb_pull_data(sk, len);
    }

    SEC("tc")
    int test_invalidate_checks(struct __sk_buff *sk)
    {
        int *p = (void *)(long)sk->data;
        if ((void *)(p + 1) > (void *)(long)sk->data_end) return TCX_DROP;
        skb_pull_data(sk, 0);
        *p = 42;
        return TCX_PASS;
    }

After a call to bpf_skb_pull_data() the pointer 'p' can't be used
safely. See function filter.c:bpf_helper_changes_pkt_data() for a list
of such helpers.

At the moment verifier does packet pointers invalidation only upon
processing calls to helper functions. This means that calls to helpers
done from global sub-programs do not invalidate pointers in the caller
state. E.g. the following program above is unsafe, but is not rejected
by verifier.

This commit fixes the omission by computing field
bpf_subprog_info->changes_pkt_data for each sub-program before main
verification pass.
changes_pkt_data should be set if:
- subprogram calls helper for which bpf_helper_changes_pkt_data
  returns true;
- subprogram calls a global function,
  for which bpf_subprog_info->changes_pkt_data should be set.

The verifier.c:check_cfg() pass is modified to compute this
information. The commit relies on depth first instruction traversal
done by check_cfg() and absence of recursive function calls:
- check_cfg() would eventually visit every call to subprogram S in a
  state when S is fully explored;
- when S is fully explored:
  - every direct helper call within S is explored
    (and thus changes_pkt_data is set if needed);
  - every call to subprogram S1 called by S was visited with S1 fully
    explored (and thus S inherits changes_pkt_data from S1).

The downside of such approach is that dead code elimination is not
taken into account: if a helper call inside global function is dead
because of current configuration, verifier would conservatively assume
that the call occurs for the purpose of the changes_pkt_data
computation.

Reported-by: Nick Zavaritsky <mejedi@gmail.com>
Closes: https://lore.kernel.org/bpf/0498CA22-5779-4767-9C0C-A9515CEA711F@gmail.com/
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 32 +++++++++++++++++++++++++++++++-
 2 files changed, 32 insertions(+), 1 deletion(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index f4290c179bee..48b7b2eeb7e2 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -659,6 +659,7 @@ struct bpf_subprog_info {
 	bool args_cached: 1;
 	/* true if bpf_fastcall stack region is used by functions that can't be inlined */
 	bool keep_fastcall_stack: 1;
+	bool changes_pkt_data: 1;
 
 	enum priv_stack_mode priv_stack_mode;
 	u8 arg_cnt;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ad3f6d28e8e4..6a29b68cebd6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -10042,6 +10042,8 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 
 		verbose(env, "Func#%d ('%s') is global and assumed valid.\n",
 			subprog, sub_name);
+		if (env->subprog_info[subprog].changes_pkt_data)
+			clear_all_pkt_pointers(env);
 		/* mark global subprog for verifying after main prog */
 		subprog_aux(env, subprog)->called = true;
 		clear_caller_saved_regs(env, caller->regs);
@@ -16246,6 +16248,29 @@ static int check_return_code(struct bpf_verifier_env *env, int regno, const char
 	return 0;
 }
 
+static void mark_subprog_changes_pkt_data(struct bpf_verifier_env *env, int off)
+{
+	struct bpf_subprog_info *subprog;
+
+	subprog = find_containing_subprog(env, off);
+	subprog->changes_pkt_data = true;
+}
+
+/* 't' is an index of a call-site.
+ * 'w' is a callee entry point.
+ * Eventually this function would be called when env->cfg.insn_state[w] == EXPLORED.
+ * Rely on DFS traversal order and absence of recursive calls to guarantee that
+ * callee's change_pkt_data marks would be correct at that moment.
+ */
+static void merge_callee_effects(struct bpf_verifier_env *env, int t, int w)
+{
+	struct bpf_subprog_info *caller, *callee;
+
+	caller = find_containing_subprog(env, t);
+	callee = find_containing_subprog(env, w);
+	caller->changes_pkt_data |= callee->changes_pkt_data;
+}
+
 /* non-recursive DFS pseudo code
  * 1  procedure DFS-iterative(G,v):
  * 2      label v as discovered
@@ -16379,6 +16404,7 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,
 				bool visit_callee)
 {
 	int ret, insn_sz;
+	int w;
 
 	insn_sz = bpf_is_ldimm64(&insns[t]) ? 2 : 1;
 	ret = push_insn(t, t + insn_sz, FALLTHROUGH, env);
@@ -16390,8 +16416,10 @@ static int visit_func_call_insn(int t, struct bpf_insn *insns,
 	mark_jmp_point(env, t + insn_sz);
 
 	if (visit_callee) {
+		w = t + insns[t].imm + 1;
 		mark_prune_point(env, t);
-		ret = push_insn(t, t + insns[t].imm + 1, BRANCH, env);
+		merge_callee_effects(env, t, w);
+		ret = push_insn(t, w, BRANCH, env);
 	}
 	return ret;
 }
@@ -16708,6 +16736,8 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 			mark_prune_point(env, t);
 			mark_jmp_point(env, t);
 		}
+		if (bpf_helper_call(insn) && bpf_helper_changes_pkt_data(insn->imm))
+			mark_subprog_changes_pkt_data(env, t);
 		if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
 			struct bpf_kfunc_call_arg_meta meta;
 
-- 
2.47.0

[PATCH bpf 4/4] selftests/bpf: test for changing packet data from global functions

[Eduard Zingerman]

Check if verifier is aware of packet pointers invalidation done in
global functions. Based on a test shared by Nick Zavaritsky in [0].

[0] https://lore.kernel.org/bpf/0498CA22-5779-4767-9C0C-A9515CEA711F@gmail.com/

Suggested-by: Nick Zavaritsky <mejedi@gmail.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../selftests/bpf/progs/verifier_sock.c       | 28 +++++++++++++++++++
 1 file changed, 28 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_sock.c b/tools/testing/selftests/bpf/progs/verifier_sock.c
index d3e70e38e442..51826379a1aa 100644
--- a/tools/testing/selftests/bpf/progs/verifier_sock.c
+++ b/tools/testing/selftests/bpf/progs/verifier_sock.c
@@ -1037,4 +1037,32 @@ __naked void sock_create_read_src_port(void)
 	: __clobber_all);
 }
 
+__noinline
+long skb_pull_data2(struct __sk_buff *sk, __u32 len)
+{
+	return bpf_skb_pull_data(sk, len);
+}
+
+__noinline
+long skb_pull_data1(struct __sk_buff *sk, __u32 len)
+{
+	return skb_pull_data2(sk, len);
+}
+
+/* global function calls bpf_skb_pull_data(), which invalidates packet
+ * pointers established before global function call.
+ */
+SEC("tc")
+__failure __msg("invalid mem access")
+int invalidate_pkt_pointers_from_global_func(struct __sk_buff *sk)
+{
+	int *p = (void *)(long)sk->data;
+
+	if ((void *)(p + 1) > (void *)(long)sk->data_end)
+		return TCX_DROP;
+	skb_pull_data1(sk, 0);
+	*p = 42; /* this is unsafe */
+	return TCX_PASS;
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.47.0

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Alexei Starovoitov]

On Thu, Dec 5, 2024 at 8:03 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index f4290c179bee..48b7b2eeb7e2 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -659,6 +659,7 @@ struct bpf_subprog_info {
>         bool args_cached: 1;
>         /* true if bpf_fastcall stack region is used by functions that can't be inlined */
>         bool keep_fastcall_stack: 1;
> +       bool changes_pkt_data: 1;

since freplace was brought up in the other thread.
Let's fix it all in one patch.
I think propagating changes_pkt_data flag into prog_aux and
into map->owner should do it.
The handling will be similar to existing xdp_has_frags.

Otherwise tail_call from static subprog will have the same issue.
xdp_has_frags compatibility requires equality. All progs either
have it or don't.
changes_pkt_data flag doesn't need to be that strict:
A prog with changes_pkt_data can be freplaced by prog without
and tailcall into prog without it.
But not the other way around.

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Eduard Zingerman]

On Fri, 2024-12-06 at 12:43 -0800, Alexei Starovoitov wrote:
> On Thu, Dec 5, 2024 at 8:03 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index f4290c179bee..48b7b2eeb7e2 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -659,6 +659,7 @@ struct bpf_subprog_info {
> >         bool args_cached: 1;
> >         /* true if bpf_fastcall stack region is used by functions that can't be inlined */
> >         bool keep_fastcall_stack: 1;
> > +       bool changes_pkt_data: 1;
> 
> since freplace was brought up in the other thread.
> Let's fix it all in one patch.
> I think propagating changes_pkt_data flag into prog_aux and
> into map->owner should do it.
> The handling will be similar to existing xdp_has_frags.
> 
> Otherwise tail_call from static subprog will have the same issue.
> xdp_has_frags compatibility requires equality. All progs either
> have it or don't.
> changes_pkt_data flag doesn't need to be that strict:
> A prog with changes_pkt_data can be freplaced by prog without
> and tailcall into prog without it.
> But not the other way around.

Ack, will do.

(Note: the change Andrii suggested with change to global subprogram
       visit order looks plausible and not hard to implement,
       after I though about it a bit more).

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Eduard Zingerman]

On Fri, 2024-12-06 at 12:43 -0800, Alexei Starovoitov wrote:
> On Thu, Dec 5, 2024 at 8:03 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> >
> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index f4290c179bee..48b7b2eeb7e2 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -659,6 +659,7 @@ struct bpf_subprog_info {
> >         bool args_cached: 1;
> >         /* true if bpf_fastcall stack region is used by functions that can't be inlined */
> >         bool keep_fastcall_stack: 1;
> > +       bool changes_pkt_data: 1;
>
> since freplace was brought up in the other thread.
> Let's fix it all in one patch.
> I think propagating changes_pkt_data flag into prog_aux and
> into map->owner should do it.
> The handling will be similar to existing xdp_has_frags.
>
> Otherwise tail_call from static subprog will have the same issue.
> xdp_has_frags compatibility requires equality. All progs either
> have it or don't.
> changes_pkt_data flag doesn't need to be that strict:
> A prog with changes_pkt_data can be freplaced by prog without
> and tailcall into prog without it.
> But not the other way around.

I tried implementing this in:
https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug

The freplace part is simple and works as intended.

The tail call part won't work with check_cfg() based approach and
needs global functions traversal reordering Andrii talked about.
This is so, because of the need to inspect the value of register R1,
passed to the tail call helper, in order to check map owner's properties.

If the rules are simplified to consider each tail call such that
packet pointers are invalidated, the test case
tailcalls/tailcall_freplace fails. Here is how it looks:

    // tc_bpf2bpf.c
    __noinline                             freplace
    int subprog_tc(struct __sk_buff *skb) <--------.
    {                                              |
    	int ret = 1;                               |
                                                   |
    	__sink(skb);                               |
    	__sink(ret);                               |
    	return ret;                                |
    }                                              |
                                                   |
    SEC("tc")                                      |
    int entry_tc(struct __sk_buff *skb)            |
    {                                              |
    	return subprog_tc(skb);                    |
    }                                              |
                                                   |
    // tailcall_freplace.c                         |
    struct {                                       |
    	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);     |
    	__uint(max_entries, 1);                    |
    	__uint(key_size, sizeof(__u32));           |
    	__uint(value_size, sizeof(__u32));         |
    } jmp_table SEC(".maps");                      |
                                                   |
    int count = 0;                                 |
                                                   |
    SEC("freplace")                                |
    int entry_freplace(struct __sk_buff *skb) -----'
    {
    	count++;
    	bpf_tail_call_static(skb, &jmp_table, 0);
    	return count;
    }

Here 'entry_freplace' is assumed to invalidate packet data because of
the bpf_tail_call_static(), and thus it can't replace 'subprog_tc'.
There is an option to add a dummy call to bpf_skb_pull_data(),
but this operation is not a noop, as far as I can tell.

Same situation was discussed in the sub-thread regarding use of tags.
(Note: because of the tail calls, some form of changes_pkt_data effect
 propagation similar to one done in check_cfg() would be needed with
 tags as well. That, or tags would be needed not only for global
 sub-programs but also for BPF_MAP_TYPE_PROG_ARRAY maps).

---

I'll continue with global sub-programs traversal reordering and share
the implementation on Monday, to facilitate further discussion.

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Alexei Starovoitov]

On Sun, Dec 8, 2024 at 11:40 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2024-12-06 at 12:43 -0800, Alexei Starovoitov wrote:
> > On Thu, Dec 5, 2024 at 8:03 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > > index f4290c179bee..48b7b2eeb7e2 100644
> > > --- a/include/linux/bpf_verifier.h
> > > +++ b/include/linux/bpf_verifier.h
> > > @@ -659,6 +659,7 @@ struct bpf_subprog_info {
> > >         bool args_cached: 1;
> > >         /* true if bpf_fastcall stack region is used by functions that can't be inlined */
> > >         bool keep_fastcall_stack: 1;
> > > +       bool changes_pkt_data: 1;
> >
> > since freplace was brought up in the other thread.
> > Let's fix it all in one patch.
> > I think propagating changes_pkt_data flag into prog_aux and
> > into map->owner should do it.
> > The handling will be similar to existing xdp_has_frags.
> >
> > Otherwise tail_call from static subprog will have the same issue.
> > xdp_has_frags compatibility requires equality. All progs either
> > have it or don't.
> > changes_pkt_data flag doesn't need to be that strict:
> > A prog with changes_pkt_data can be freplaced by prog without
> > and tailcall into prog without it.
> > But not the other way around.
>
> I tried implementing this in:
> https://github.com/eddyz87/bpf/tree/skb-pull-data-global-func-bug
>
> The freplace part is simple and works as intended.
>
> The tail call part won't work with check_cfg() based approach and
> needs global functions traversal reordering Andrii talked about.
> This is so, because of the need to inspect the value of register R1,
> passed to the tail call helper, in order to check map owner's properties.
>
> If the rules are simplified to consider each tail call such that
> packet pointers are invalidated, the test case
> tailcalls/tailcall_freplace fails. Here is how it looks:
>
>     // tc_bpf2bpf.c
>     __noinline                             freplace
>     int subprog_tc(struct __sk_buff *skb) <--------.
>     {                                              |
>         int ret = 1;                               |
>                                                    |
>         __sink(skb);                               |
>         __sink(ret);                               |
>         return ret;                                |
>     }                                              |
>                                                    |
>     SEC("tc")                                      |
>     int entry_tc(struct __sk_buff *skb)            |
>     {                                              |
>         return subprog_tc(skb);                    |
>     }                                              |
>                                                    |
>     // tailcall_freplace.c                         |
>     struct {                                       |
>         __uint(type, BPF_MAP_TYPE_PROG_ARRAY);     |
>         __uint(max_entries, 1);                    |
>         __uint(key_size, sizeof(__u32));           |
>         __uint(value_size, sizeof(__u32));         |
>     } jmp_table SEC(".maps");                      |
>                                                    |
>     int count = 0;                                 |
>                                                    |
>     SEC("freplace")                                |
>     int entry_freplace(struct __sk_buff *skb) -----'
>     {
>         count++;
>         bpf_tail_call_static(skb, &jmp_table, 0);
>         return count;
>     }

hmm. none of the above changes pkt_data, so it should be allowed.
The prog doesn't read skb->data either.
So I don't quite see the problem.

> Here 'entry_freplace' is assumed to invalidate packet data because of
> the bpf_tail_call_static(), and thus it can't replace 'subprog_tc'.
> There is an option to add a dummy call to bpf_skb_pull_data(),
> but this operation is not a noop, as far as I can tell.

skb_pull is not, but there are plenty that are practically nop helpers.
bpf_helper_changes_pkt_data() lists them all.
Like bpf_xdp_adjust_meta(xdp, 0)

> Same situation was discussed in the sub-thread regarding use of tags.
> (Note: because of the tail calls, some form of changes_pkt_data effect
>  propagation similar to one done in check_cfg() would be needed with
>  tags as well. That, or tags would be needed not only for global
>  sub-programs but also for BPF_MAP_TYPE_PROG_ARRAY maps).

nack to tags approach.

>
> ---
>
> I'll continue with global sub-programs traversal reordering and share
> the implementation on Monday, to facilitate further discussion.
>

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Eduard Zingerman]

On Mon, 2024-12-09 at 08:53 -0800, Alexei Starovoitov wrote:

[...]

> > 
> >     // tc_bpf2bpf.c
> >     __noinline                             freplace
> >     int subprog_tc(struct __sk_buff *skb) <--------.
> >     {                                              |
> >         int ret = 1;                               |
> >                                                    |
> >         __sink(skb);                               |
> >         __sink(ret);                               |
> >         return ret;                                |
> >     }                                              |
> >                                                    |
> >     SEC("tc")                                      |
> >     int entry_tc(struct __sk_buff *skb)            |
> >     {                                              |
> >         return subprog_tc(skb);                    |
> >     }                                              |
> >                                                    |
> >     // tailcall_freplace.c                         |
> >     struct {                                       |
> >         __uint(type, BPF_MAP_TYPE_PROG_ARRAY);     |
> >         __uint(max_entries, 1);                    |
> >         __uint(key_size, sizeof(__u32));           |
> >         __uint(value_size, sizeof(__u32));         |
> >     } jmp_table SEC(".maps");                      |
> >                                                    |
> >     int count = 0;                                 |
> >                                                    |
> >     SEC("freplace")                                |
> >     int entry_freplace(struct __sk_buff *skb) -----'
> >     {
> >         count++;
> >         bpf_tail_call_static(skb, &jmp_table, 0);
> >         return count;
> >     }
> 
> hmm. none of the above changes pkt_data, so it should be allowed.
> The prog doesn't read skb->data either.
> So I don't quite see the problem.

The problem is when I use simplified rule: "every tail call changes packet data",
as a substitute for proper map content effects tracking.

If map content effects are tracked, there should be no problems
verifying this program. However, that can't be done in check_cfg(),
as it does not track register values, and register value is needed to
identify the map. Hence, mechanics with "in-line" global sub-program
traversal is needed (as described by Andrii):
- during a regular verification pass get to a global sub-program call:
  - if sub-program had not been visited yet, verify it completely
    and compute changes_pkt_data effect;
  - continue from the call-site using the computed effect;
- during a regular verification pass get to a tail call:
  - check the map pointed to by R1 to see whether it has
    changes_pkt_data effect.

> > Here 'entry_freplace' is assumed to invalidate packet data because of
> > the bpf_tail_call_static(), and thus it can't replace 'subprog_tc'.
> > There is an option to add a dummy call to bpf_skb_pull_data(),
> > but this operation is not a noop, as far as I can tell.
> 
> skb_pull is not, but there are plenty that are practically nop helpers.
> bpf_helper_changes_pkt_data() lists them all.
> Like bpf_xdp_adjust_meta(xdp, 0)
> 
> > Same situation was discussed in the sub-thread regarding use of tags.
> > (Note: because of the tail calls, some form of changes_pkt_data effect
> >  propagation similar to one done in check_cfg() would be needed with
> >  tags as well. That, or tags would be needed not only for global
> >  sub-programs but also for BPF_MAP_TYPE_PROG_ARRAY maps).
> 
> nack to tags approach.

Understood.

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Alexei Starovoitov]

On Mon, Dec 9, 2024 at 9:57 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-12-09 at 08:53 -0800, Alexei Starovoitov wrote:
>
> [...]
>
> > >
> > >     // tc_bpf2bpf.c
> > >     __noinline                             freplace
> > >     int subprog_tc(struct __sk_buff *skb) <--------.
> > >     {                                              |
> > >         int ret = 1;                               |
> > >                                                    |
> > >         __sink(skb);                               |
> > >         __sink(ret);                               |
> > >         return ret;                                |
> > >     }                                              |
> > >                                                    |
> > >     SEC("tc")                                      |
> > >     int entry_tc(struct __sk_buff *skb)            |
> > >     {                                              |
> > >         return subprog_tc(skb);                    |
> > >     }                                              |
> > >                                                    |
> > >     // tailcall_freplace.c                         |
> > >     struct {                                       |
> > >         __uint(type, BPF_MAP_TYPE_PROG_ARRAY);     |
> > >         __uint(max_entries, 1);                    |
> > >         __uint(key_size, sizeof(__u32));           |
> > >         __uint(value_size, sizeof(__u32));         |
> > >     } jmp_table SEC(".maps");                      |
> > >                                                    |
> > >     int count = 0;                                 |
> > >                                                    |
> > >     SEC("freplace")                                |
> > >     int entry_freplace(struct __sk_buff *skb) -----'
> > >     {
> > >         count++;
> > >         bpf_tail_call_static(skb, &jmp_table, 0);
> > >         return count;
> > >     }
> >
> > hmm. none of the above changes pkt_data, so it should be allowed.
> > The prog doesn't read skb->data either.
> > So I don't quite see the problem.
>
> The problem is when I use simplified rule: "every tail call changes packet data",
> as a substitute for proper map content effects tracking.
>
> If map content effects are tracked, there should be no problems
> verifying this program. However, that can't be done in check_cfg(),
> as it does not track register values, and register value is needed to
> identify the map.

We don't need data flow analysis and R1 tracking.

We could do the following rule:
if prog has a tail call and any prog array map in prog->aux->used_maps
calls into prog with adjust_pkt_data assume that this prog
also adjusts pkt_data.

> Hence, mechanics with "in-line" global sub-program
> traversal is needed (as described by Andrii):
> - during a regular verification pass get to a global sub-program call:
>   - if sub-program had not been visited yet, verify it completely
>     and compute changes_pkt_data effect;
>   - continue from the call-site using the computed effect;
> - during a regular verification pass get to a tail call:
>   - check the map pointed to by R1 to see whether it has
>     changes_pkt_data effect.

I don't think we should be adding all that logic when a much simpler
rule (as described above) is good enough.

Also either inline global sub-prog traversal or the simple rule above
both suffer from the following issue:
in case prog_array is empty map->changes_pkt_data will be false.
It will be set to true only when the first
prog_fd_array_get_ptr()->bpf_prog_map_compatible()
will record changes_pkt_data from the first prog inserted in prog_array.

So main prog reading skb->data after calling subprog that tail_calls
somewhere should assume that skb->data is invalidated.

That's pretty much your rule "every tail call changes packet data".

I think we can go with this simplest approach as well.
The test you mentioned have to be adjusted. Not a big deal.

Or we can do:
"if prog_array empty assume adjusts_pkt_data == true,
otherwise adj_pkt_data | = for each map in used_maps {
map->owner.adj_pkt_data }"

The fancy inline global subprog traversal would have to have the same
"simple" (or call it dumb) rule.
So at the end both inline or check_cfg are not accurate at all,
but check_cfg approach is so much simpler.

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Eduard Zingerman]

On Mon, 2024-12-09 at 16:48 -0800, Alexei Starovoitov wrote:

[...]

> Also either inline global sub-prog traversal or the simple rule above
> both suffer from the following issue:
> in case prog_array is empty map->changes_pkt_data will be false.
> It will be set to true only when the first
> prog_fd_array_get_ptr()->bpf_prog_map_compatible()
> will record changes_pkt_data from the first prog inserted in prog_array.
> 
> So main prog reading skb->data after calling subprog that tail_calls
> somewhere should assume that skb->data is invalidated.

Yes, that's what I was planning to do.

> That's pretty much your rule "every tail call changes packet data".
> 
> I think we can go with this simplest approach as well.
> The test you mentioned have to be adjusted. Not a big deal.
> 
> Or we can do:
> "if prog_array empty assume adjusts_pkt_data == true,
> otherwise adj_pkt_data | = for each map in used_maps {
> map->owner.adj_pkt_data }"
> 
> The fancy inline global subprog traversal would have to have the same
> "simple" (or call it dumb) rule.
> So at the end both inline or check_cfg are not accurate at all,
> but check_cfg approach is so much simpler.

I don't like the '|= map->owner.adj_pkt_data' thing, tbh.
I think "any tail call changes packet data" is simpler to reason about.
But then, the question is, how to modify the test?
You suggested bpf_xdp_adjust_meta(xdp, 0) for 'xdp', and it is a good fit,
as it does not do much.
For 'skb' I don't see anything better than 'bpf_skb_pull_data(sk, 0)',
it does skb_ensure_writable(), but everything else does more.
Dedicated kfunc would be cleaner, though.

Re: [PATCH bpf 3/4] bpf: track changes_pkt_data property for global functions

[Alexei Starovoitov]

On Mon, Dec 9, 2024 at 5:24 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Mon, 2024-12-09 at 16:48 -0800, Alexei Starovoitov wrote:
>
> [...]
>
> > Also either inline global sub-prog traversal or the simple rule above
> > both suffer from the following issue:
> > in case prog_array is empty map->changes_pkt_data will be false.
> > It will be set to true only when the first
> > prog_fd_array_get_ptr()->bpf_prog_map_compatible()
> > will record changes_pkt_data from the first prog inserted in prog_array.
> >
> > So main prog reading skb->data after calling subprog that tail_calls
> > somewhere should assume that skb->data is invalidated.
>
> Yes, that's what I was planning to do.
>
> > That's pretty much your rule "every tail call changes packet data".
> >
> > I think we can go with this simplest approach as well.
> > The test you mentioned have to be adjusted. Not a big deal.
> >
> > Or we can do:
> > "if prog_array empty assume adjusts_pkt_data == true,
> > otherwise adj_pkt_data | = for each map in used_maps {
> > map->owner.adj_pkt_data }"
> >
> > The fancy inline global subprog traversal would have to have the same
> > "simple" (or call it dumb) rule.
> > So at the end both inline or check_cfg are not accurate at all,
> > but check_cfg approach is so much simpler.
>
> I don't like the '|= map->owner.adj_pkt_data' thing, tbh.
> I think "any tail call changes packet data" is simpler to reason about.
> But then, the question is, how to modify the test?
> You suggested bpf_xdp_adjust_meta(xdp, 0) for 'xdp', and it is a good fit,
> as it does not do much.
> For 'skb' I don't see anything better than 'bpf_skb_pull_data(sk, 0)',
> it does skb_ensure_writable(), but everything else does more.

bpf_skb_change_proto(skb, skb->protocol, 0)
is a guaranteed success and as close to nop as possible.
Or the same with invalid flags or invalid proto.
bpf_skb_change_proto(skb, 0, 0)
Guaranteed -EINVAL.

> Dedicated kfunc would be cleaner, though.

Sorry I disagree.