Skip to contentSkip to conversation

bpf: track changes_pkt_data property for global functions

PATCH Superseded Eduard Zingerman 2 participants 13 messages Dec 6, 2024 – Dec 10, 2024

Subsystems (6)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

cover bpf: track changes_pkt_data property for global functions

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/[email protected]/

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(-)
Signature · 1 line
2.47.0
author maintainer
#1 lore raw

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

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

---
 kernel/bpf/verifier.c | 28 ++++++++++++++++++++++++----
 1 file changed, 24 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +24 -4
index 01fbef9576e0..277c1892bb9a 100644
@@ -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)
Signature · 1 line
2.47.0
author maintainer
#2 lore raw

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

In reply to 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.

---
 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(-)
include/linux/filter.h +1 -1
index 3a21947f2fd4..0477254bc2d3 100644
@@ -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)
 {
kernel/bpf/core.c +1 -1
index a2327c4fdc8b..6fa8041d4831 100644
@@ -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;
 }
kernel/bpf/verifier.c +1 -1
index 277c1892bb9a..ad3f6d28e8e4 100644
@@ -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);
net/core/filter.c +28 -35

70 lines not on this page · raw message

Signature · 1 line
2.47.0
author maintainer
#3 lore raw

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

In reply to 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.

---
 include/linux/bpf_verifier.h |  1 +
 kernel/bpf/verifier.c        | 32 +++++++++++++++++++++++++++++++-
 2 files changed, 32 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +1 -0
index f4290c179bee..48b7b2eeb7e2 100644
@@ -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;
kernel/bpf/verifier.c +31 -1
index ad3f6d28e8e4..6a29b68cebd6 100644
@@ -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;
 
Signature · 1 line
2.47.0
author maintainer
#12 lore raw

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

In reply to 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/[email protected]/

---
 .../selftests/bpf/progs/verifier_sock.c       | 28 +++++++++++++++++++
 1 file changed, 28 insertions(+)
tools/testing/selftests/bpf/progs/verifier_sock.c +28 -0
index d3e70e38e442..51826379a1aa 100644
@@ -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";
Signature · 1 line
2.47.0
#4 lore raw
In reply to Eduard Zingerman

include/linux/bpf_verifier.h struct bpf_subprog_info { · line 662

Quoted 10 lines · Eduard Zingerman
include/linux/bpf_verifier.h +1 -0
index f4290c179bee..48b7b2eeb7e2 100644
@@ -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.

author maintainer
#5 lore raw
Quoted 18 lines · Alexei Starovoitov

include/linux/bpf_verifier.h struct bpf_subprog_info { · line 662

Quoted 10 lines · Eduard Zingerman
include/linux/bpf_verifier.h +1 -0
index f4290c179bee..48b7b2eeb7e2 100644
@@ -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.

Quoted 7 lines

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).

author maintainer
#6 lore raw
In reply to Alexei Starovoitov
Quoted 18 lines · Alexei Starovoitov

include/linux/bpf_verifier.h struct bpf_subprog_info { · line 662

Quoted 10 lines · Eduard Zingerman
include/linux/bpf_verifier.h +1 -0
index f4290c179bee..48b7b2eeb7e2 100644
@@ -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.

Quoted 7 lines

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.

#7 lore raw
Quoted 68 lines · Eduard Zingerman
Quoted 18 lines · Alexei Starovoitov

include/linux/bpf_verifier.h struct bpf_subprog_info { · line 662

Quoted 10 lines · Eduard Zingerman
include/linux/bpf_verifier.h +1 -0
index f4290c179bee..48b7b2eeb7e2 100644
@@ -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.

Quoted 7 lines

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;                                 |
Quoted 8 lines
                                                   |
    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.

Quoted 4 lines

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)

Quoted 5 lines

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.

Quoted 6 lines

---

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

author maintainer
#8 lore raw

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

[...]

Quoted 36 lines
Quoted 27 lines
    // 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;                                 |
Quoted 8 lines
                                                   |
    SEC("freplace")                                |
    int entry_freplace(struct __sk_buff *skb) -----'
    {
        count++;
        bpf_tail_call_static(skb, &jmp_table, 0);
        return count;
    }
Quoted 3 lines

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.

Quoted 9 lines
Quoted 4 lines

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)

Quoted 7 lines
Quoted 5 lines

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.

#9 lore raw
Quoted 45 lines · Eduard Zingerman

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

[...]

Quoted 36 lines
Quoted 27 lines
    // 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;                                 |
Quoted 8 lines
                                                   |
    SEC("freplace")                                |
    int entry_freplace(struct __sk_buff *skb) -----'
    {
        count++;
        bpf_tail_call_static(skb, &jmp_table, 0);
        return count;
    }
Quoted 3 lines

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.

Quoted 7 lines

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.

Quoted 9 lines

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.

author maintainer
#10 lore raw

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

[...]

Quoted 9 lines

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.

Quoted 10 lines

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 }"

Quoted 4 lines

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.

#11 lore raw
Quoted 32 lines · Eduard Zingerman

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

[...]

Quoted 9 lines

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.

Quoted 10 lines

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 }"

Quoted 4 lines

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.

Quoted 7 lines

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.

Quoted 1 line

Dedicated kfunc would be cleaner, though.

Sorry I disagree.