BPF List
 help / color / mirror / Atom feed
* [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions
@ 2024-12-10  4:10 Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 1/8] bpf: add find_containing_subprog() utility function Eduard Zingerman
                   ` (8 more replies)
  0 siblings, 9 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	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.

As global functions could be replaced with extension programs,
a new field 'changes_pkt_data' is added to struct bpf_prog_aux.
Verifier only allows replacing functions that do not change packet
data with functions that do not change packet data.

In case if there is a need to a have a global function that does not
change packet data, but allow replacing it with function that does,
the recommendation is to add a noop call to a helper, e.g.:
- for skb do 'bpf_skb_change_proto(skb, 0, 0)';
- for xdp do 'bpf_xdp_adjust_meta(xdp, 0)'.

Functions also can do tail calls. Effects of the tail call cannot be
analyzed before-hand, thus verifier assumes that tail calls always
change packet data.

Changes v1 [1] -> v2:
- added handling of extension programs and tail calls
  (thanks, Alexei, for all the input).

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

Eduard Zingerman (8):
  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
  bpf: check changes_pkt_data property for extension programs
  selftests/bpf: freplace tests for tracking of changes_packet_data
  bpf: consider that tail calls invalidate packet pointers
  selftests/bpf: validate that tail call invalidates packet pointers

 include/linux/bpf.h                           |  1 +
 include/linux/bpf_verifier.h                  |  1 +
 include/linux/filter.h                        |  2 +-
 kernel/bpf/core.c                             |  2 +-
 kernel/bpf/verifier.c                         | 78 ++++++++++++++++---
 net/core/filter.c                             | 65 +++++++---------
 .../bpf/prog_tests/changes_pkt_data.c         | 76 ++++++++++++++++++
 .../selftests/bpf/progs/changes_pkt_data.c    | 26 +++++++
 .../bpf/progs/changes_pkt_data_freplace.c     | 18 +++++
 .../testing/selftests/bpf/progs/tc_bpf2bpf.c  |  2 +
 .../selftests/bpf/progs/verifier_sock.c       | 56 +++++++++++++
 11 files changed, 280 insertions(+), 47 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/changes_pkt_data.c
 create mode 100644 tools/testing/selftests/bpf/progs/changes_pkt_data.c
 create mode 100644 tools/testing/selftests/bpf/progs/changes_pkt_data_freplace.c

-- 
2.47.0


^ permalink raw reply	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 1/8] bpf: add find_containing_subprog() utility function
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
@ 2024-12-10  4:10 ` Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 2/8] bpf: refactor bpf_helper_changes_pkt_data to use helper number Eduard Zingerman
                   ` (7 subsequent siblings)
  8 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	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


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 2/8] bpf: refactor bpf_helper_changes_pkt_data to use helper number
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 1/8] bpf: add find_containing_subprog() utility function Eduard Zingerman
@ 2024-12-10  4:10 ` Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 3/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
                   ` (6 subsequent siblings)
  8 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	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


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 3/8] bpf: track changes_pkt_data property for global functions
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 1/8] bpf: add find_containing_subprog() utility function Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 2/8] bpf: refactor bpf_helper_changes_pkt_data to use helper number Eduard Zingerman
@ 2024-12-10  4:10 ` Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 4/8] selftests/bpf: test for changing packet data from " Eduard Zingerman
                   ` (5 subsequent siblings)
  8 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	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 invalidates packet pointers when processing
helper function calls, and does not traverse global sub-programs when
processing calls to global sub-programs. This means that calls to
helpers done from global sub-programs do not invalidate pointers in
the caller state. E.g. the 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


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 4/8] selftests/bpf: test for changing packet data from global functions
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
                   ` (2 preceding siblings ...)
  2024-12-10  4:10 ` [PATCH bpf v2 3/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
@ 2024-12-10  4:10 ` Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 5/8] bpf: check changes_pkt_data property for extension programs Eduard Zingerman
                   ` (4 subsequent siblings)
  8 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	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


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 5/8] bpf: check changes_pkt_data property for extension programs
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
                   ` (3 preceding siblings ...)
  2024-12-10  4:10 ` [PATCH bpf v2 4/8] selftests/bpf: test for changing packet data from " Eduard Zingerman
@ 2024-12-10  4:10 ` Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 6/8] selftests/bpf: freplace tests for tracking of changes_packet_data Eduard Zingerman
                   ` (3 subsequent siblings)
  8 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	Eduard Zingerman, Alexei Starovoitov

When processing calls to global sub-programs, verifier decides whether
to invalidate all packet pointers in current state depending on the
changes_pkt_data property of the global sub-program.

Because of this, an extension program replacing a global sub-program
must be compatible with changes_pkt_data property of the sub-program
being replaced.

This commit:
- adds changes_pkt_data flag to struct bpf_prog_aux:
  - this flag is set in check_cfg() for main sub-program;
  - in jit_subprogs() for other sub-programs;
- modifies bpf_check_attach_btf_id() to check changes_pkt_data flag;
- moves call to check_attach_btf_id() after the call to check_cfg(),
  because it needs changes_pkt_data flag to be set:

    bpf_check:
      ...                             ...
    - check_attach_btf_id             resolve_pseudo_ldimm64
      resolve_pseudo_ldimm64   -->    bpf_prog_is_offloaded
      bpf_prog_is_offloaded           check_cfg
      check_cfg                     + check_attach_btf_id
      ...                             ...

The following fields are set by check_attach_btf_id():
- env->ops
- prog->aux->attach_btf_trace
- prog->aux->attach_func_name
- prog->aux->attach_func_proto
- prog->aux->dst_trampoline
- prog->aux->mod
- prog->aux->saved_dst_attach_type
- prog->aux->saved_dst_prog_type
- prog->expected_attach_type

Neither of these fields are used by resolve_pseudo_ldimm64() or
bpf_prog_offload_verifier_prep() (for netronome and netdevsim
drivers), so the reordering is safe.

Suggested-by: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf.h   |  1 +
 kernel/bpf/verifier.c | 16 ++++++++++++----
 2 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index eaee2a819f4c..fe392d074973 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1527,6 +1527,7 @@ struct bpf_prog_aux {
 	bool is_extended; /* true if extended by freplace program */
 	bool jits_use_priv_stack;
 	bool priv_stack_requested;
+	bool changes_pkt_data;
 	u64 prog_array_member_cnt; /* counts how many times as member of prog_array */
 	struct mutex ext_mutex; /* mutex for is_extended and prog_array_member_cnt */
 	struct bpf_arena *arena;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 6a29b68cebd6..c2e5d0e6e3d0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -16872,6 +16872,7 @@ static int check_cfg(struct bpf_verifier_env *env)
 		}
 	}
 	ret = 0; /* cfg looks good */
+	env->prog->aux->changes_pkt_data = env->subprog_info[0].changes_pkt_data;
 
 err_free:
 	kvfree(insn_state);
@@ -20361,6 +20362,7 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		func[i]->aux->num_exentries = num_exentries;
 		func[i]->aux->tail_call_reachable = env->subprog_info[i].tail_call_reachable;
 		func[i]->aux->exception_cb = env->subprog_info[i].is_exception_cb;
+		func[i]->aux->changes_pkt_data = env->subprog_info[i].changes_pkt_data;
 		if (!i)
 			func[i]->aux->exception_boundary = env->seen_exception;
 		func[i] = bpf_int_jit_compile(func[i]);
@@ -22225,6 +22227,12 @@ int bpf_check_attach_target(struct bpf_verifier_log *log,
 					"Extension programs should be JITed\n");
 				return -EINVAL;
 			}
+			if (prog->aux->changes_pkt_data &&
+			    !aux->func[subprog]->aux->changes_pkt_data) {
+				bpf_log(log,
+					"Extension program changes packet data, while original does not\n");
+				return -EINVAL;
+			}
 		}
 		if (!tgt_prog->jited) {
 			bpf_log(log, "Can attach to only JITed progs\n");
@@ -22690,10 +22698,6 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 	if (ret < 0)
 		goto skip_full_check;
 
-	ret = check_attach_btf_id(env);
-	if (ret)
-		goto skip_full_check;
-
 	ret = resolve_pseudo_ldimm64(env);
 	if (ret < 0)
 		goto skip_full_check;
@@ -22708,6 +22712,10 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, __u3
 	if (ret < 0)
 		goto skip_full_check;
 
+	ret = check_attach_btf_id(env);
+	if (ret)
+		goto skip_full_check;
+
 	ret = mark_fastcall_patterns(env);
 	if (ret < 0)
 		goto skip_full_check;
-- 
2.47.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 6/8] selftests/bpf: freplace tests for tracking of changes_packet_data
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
                   ` (4 preceding siblings ...)
  2024-12-10  4:10 ` [PATCH bpf v2 5/8] bpf: check changes_pkt_data property for extension programs Eduard Zingerman
@ 2024-12-10  4:10 ` Eduard Zingerman
  2024-12-10  4:10 ` [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers Eduard Zingerman
                   ` (2 subsequent siblings)
  8 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	Eduard Zingerman

Try different combinations of global functions replacement:
- replace function that changes packet data with one that doesn't;
- replace function that changes packet data with one that does;
- replace function that doesn't change packet data with one that does;
- replace function that doesn't change packet data with one that doesn't;

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../bpf/prog_tests/changes_pkt_data.c         | 76 +++++++++++++++++++
 .../selftests/bpf/progs/changes_pkt_data.c    | 26 +++++++
 .../bpf/progs/changes_pkt_data_freplace.c     | 18 +++++
 3 files changed, 120 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/changes_pkt_data.c
 create mode 100644 tools/testing/selftests/bpf/progs/changes_pkt_data.c
 create mode 100644 tools/testing/selftests/bpf/progs/changes_pkt_data_freplace.c

diff --git a/tools/testing/selftests/bpf/prog_tests/changes_pkt_data.c b/tools/testing/selftests/bpf/prog_tests/changes_pkt_data.c
new file mode 100644
index 000000000000..c0c7202f6c5c
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/changes_pkt_data.c
@@ -0,0 +1,76 @@
+// SPDX-License-Identifier: GPL-2.0
+#include "bpf/libbpf.h"
+#include "changes_pkt_data_freplace.skel.h"
+#include "changes_pkt_data.skel.h"
+#include <test_progs.h>
+
+static void print_verifier_log(const char *log)
+{
+	if (env.verbosity >= VERBOSE_VERY)
+		fprintf(stdout, "VERIFIER LOG:\n=============\n%s=============\n", log);
+}
+
+static void test_aux(const char *main_prog_name, const char *freplace_prog_name, bool expect_load)
+{
+	struct changes_pkt_data_freplace *freplace = NULL;
+	struct bpf_program *freplace_prog = NULL;
+	LIBBPF_OPTS(bpf_object_open_opts, opts);
+	struct changes_pkt_data *main = NULL;
+	char log[16*1024];
+	int err;
+
+	opts.kernel_log_buf = log;
+	opts.kernel_log_size = sizeof(log);
+	if (env.verbosity >= VERBOSE_SUPER)
+		opts.kernel_log_level = 1 | 2 | 4;
+	main = changes_pkt_data__open_opts(&opts);
+	if (!ASSERT_OK_PTR(main, "changes_pkt_data__open"))
+		goto out;
+	err = changes_pkt_data__load(main);
+	print_verifier_log(log);
+	if (!ASSERT_OK(err, "changes_pkt_data__load"))
+		goto out;
+	freplace = changes_pkt_data_freplace__open_opts(&opts);
+	if (!ASSERT_OK_PTR(freplace, "changes_pkt_data_freplace__open"))
+		goto out;
+	freplace_prog = bpf_object__find_program_by_name(freplace->obj, freplace_prog_name);
+	if (!ASSERT_OK_PTR(freplace_prog, "freplace_prog"))
+		goto out;
+	bpf_program__set_autoload(freplace_prog, true);
+	bpf_program__set_autoattach(freplace_prog, true);
+	bpf_program__set_attach_target(freplace_prog,
+				       bpf_program__fd(main->progs.dummy),
+				       main_prog_name);
+	err = changes_pkt_data_freplace__load(freplace);
+	print_verifier_log(log);
+	if (expect_load) {
+		ASSERT_OK(err, "changes_pkt_data_freplace__load");
+	} else {
+		ASSERT_ERR(err, "changes_pkt_data_freplace__load");
+		ASSERT_HAS_SUBSTR(log, "Extension program changes packet data", "error log");
+	}
+
+out:
+	changes_pkt_data_freplace__destroy(freplace);
+	changes_pkt_data__destroy(main);
+}
+
+/* There are two global subprograms in both changes_pkt_data.skel.h:
+ * - one changes packet data;
+ * - another does not.
+ * It is ok to freplace subprograms that change packet data with those
+ * that either do or do not. It is only ok to freplace subprograms
+ * that do not change packet data with those that do not as well.
+ * The below tests check outcomes for each combination of such freplace.
+ */
+void test_changes_pkt_data_freplace(void)
+{
+	if (test__start_subtest("changes_with_changes"))
+		test_aux("changes_pkt_data", "changes_pkt_data", true);
+	if (test__start_subtest("changes_with_doesnt_change"))
+		test_aux("changes_pkt_data", "does_not_change_pkt_data", true);
+	if (test__start_subtest("doesnt_change_with_changes"))
+		test_aux("does_not_change_pkt_data", "changes_pkt_data", false);
+	if (test__start_subtest("doesnt_change_with_doesnt_change"))
+		test_aux("does_not_change_pkt_data", "does_not_change_pkt_data", true);
+}
diff --git a/tools/testing/selftests/bpf/progs/changes_pkt_data.c b/tools/testing/selftests/bpf/progs/changes_pkt_data.c
new file mode 100644
index 000000000000..f87da8e9d6b3
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/changes_pkt_data.c
@@ -0,0 +1,26 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+
+__noinline
+long changes_pkt_data(struct __sk_buff *sk, __u32 len)
+{
+	return bpf_skb_pull_data(sk, len);
+}
+
+__noinline __weak
+long does_not_change_pkt_data(struct __sk_buff *sk, __u32 len)
+{
+	return 0;
+}
+
+SEC("tc")
+int dummy(struct __sk_buff *sk)
+{
+	changes_pkt_data(sk, 0);
+	does_not_change_pkt_data(sk, 0);
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
diff --git a/tools/testing/selftests/bpf/progs/changes_pkt_data_freplace.c b/tools/testing/selftests/bpf/progs/changes_pkt_data_freplace.c
new file mode 100644
index 000000000000..0e525beb8603
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/changes_pkt_data_freplace.c
@@ -0,0 +1,18 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+
+SEC("?freplace")
+long changes_pkt_data(struct __sk_buff *sk, __u32 len)
+{
+	return bpf_skb_pull_data(sk, len);
+}
+
+SEC("?freplace")
+long does_not_change_pkt_data(struct __sk_buff *sk, __u32 len)
+{
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.47.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
                   ` (5 preceding siblings ...)
  2024-12-10  4:10 ` [PATCH bpf v2 6/8] selftests/bpf: freplace tests for tracking of changes_packet_data Eduard Zingerman
@ 2024-12-10  4:10 ` Eduard Zingerman
  2024-12-10 10:35   ` Nick Zavaritsky
  2024-12-10  4:11 ` [PATCH bpf v2 8/8] selftests/bpf: validate that tail call invalidates " Eduard Zingerman
  2024-12-10 18:40 ` [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions patchwork-bot+netdevbpf
  8 siblings, 1 reply; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:10 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	Eduard Zingerman

Tail-called programs could execute any of the helpers that invalidate
packet pointers. Hence, conservatively assume that each tail call
invalidates packet pointers.

Making the change in bpf_helper_changes_pkt_data() automatically makes
use of check_cfg() logic that computes 'changes_pkt_data' effect for
global sub-programs, such that the following program could be
rejected:

    int tail_call(struct __sk_buff *sk)
    {
    	bpf_tail_call_static(sk, &jmp_table, 0);
    	return 0;
    }

    SEC("tc")
    int not_safe(struct __sk_buff *sk)
    {
    	int *p = (void *)(long)sk->data;
    	... make p valid ...
    	tail_call(sk);
    	*p = 42; /* this is unsafe */
    	...
    }

The tc_bpf2bpf.c:subprog_tc() needs change: mark it as a function that
can invalidate packet pointers. Otherwise, it can't be freplaced with
tailcall_freplace.c:entry_freplace() that does a tail call.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 net/core/filter.c                              | 2 ++
 tools/testing/selftests/bpf/progs/tc_bpf2bpf.c | 2 ++
 2 files changed, 4 insertions(+)

diff --git a/net/core/filter.c b/net/core/filter.c
index efb75eed2e35..21131ec25f24 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -7924,6 +7924,8 @@ bool bpf_helper_changes_pkt_data(enum bpf_func_id func_id)
 	case BPF_FUNC_xdp_adjust_head:
 	case BPF_FUNC_xdp_adjust_meta:
 	case BPF_FUNC_xdp_adjust_tail:
+	/* tail-called program could call any of the above */
+	case BPF_FUNC_tail_call:
 		return true;
 	default:
 		return false;
diff --git a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
index d1a57f7d09bd..fe6249d99b31 100644
--- a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
+++ b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
@@ -11,6 +11,8 @@ int subprog_tc(struct __sk_buff *skb)
 
 	__sink(skb);
 	__sink(ret);
+	/* let verifier know that 'subprog_tc' can change pointers to skb->data */
+	bpf_skb_change_proto(skb, 0, 0);
 	return ret;
 }
 
-- 
2.47.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* [PATCH bpf v2 8/8] selftests/bpf: validate that tail call invalidates packet pointers
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
                   ` (6 preceding siblings ...)
  2024-12-10  4:10 ` [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers Eduard Zingerman
@ 2024-12-10  4:11 ` Eduard Zingerman
  2024-12-10 18:40 ` [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions patchwork-bot+netdevbpf
  8 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10  4:11 UTC (permalink / raw)
  To: bpf, ast
  Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song, mejedi,
	Eduard Zingerman

Add a test case with a tail call done from a global sub-program. Such
tails calls should be considered as invalidating packet pointers.

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 51826379a1aa..0d5e56dffabb 100644
--- a/tools/testing/selftests/bpf/progs/verifier_sock.c
+++ b/tools/testing/selftests/bpf/progs/verifier_sock.c
@@ -50,6 +50,13 @@ struct {
 	__uint(map_flags, BPF_F_NO_PREALLOC);
 } sk_storage_map SEC(".maps");
 
+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");
+
 SEC("cgroup/skb")
 __description("skb->sk: no NULL check")
 __failure __msg("invalid mem access 'sock_common_or_null'")
@@ -1065,4 +1072,25 @@ int invalidate_pkt_pointers_from_global_func(struct __sk_buff *sk)
 	return TCX_PASS;
 }
 
+__noinline
+int tail_call(struct __sk_buff *sk)
+{
+	bpf_tail_call_static(sk, &jmp_table, 0);
+	return 0;
+}
+
+/* Tail calls invalidate packet pointers. */
+SEC("tc")
+__failure __msg("invalid mem access")
+int invalidate_pkt_pointers_by_tail_call(struct __sk_buff *sk)
+{
+	int *p = (void *)(long)sk->data;
+
+	if ((void *)(p + 1) > (void *)(long)sk->data_end)
+		return TCX_DROP;
+	tail_call(sk);
+	*p = 42; /* this is unsafe */
+	return TCX_PASS;
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.47.0


^ permalink raw reply related	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10  4:10 ` [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers Eduard Zingerman
@ 2024-12-10 10:35   ` Nick Zavaritsky
  2024-12-10 18:23     ` Alexei Starovoitov
  0 siblings, 1 reply; 17+ messages in thread
From: Nick Zavaritsky @ 2024-12-10 10:35 UTC (permalink / raw)
  To: Eduard Zingerman
  Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song


> Tail-called programs could execute any of the helpers that invalidate
> packet pointers. Hence, conservatively assume that each tail call
> invalidates packet pointers.

Tail calls look like a clear limitation of "auto-infer packet
invalidation effect" approach. Correct solution requires propagating
effects in the dynamic callee-caller graph, unlikely to ever happen.

I'm curious if assuming that every call to a global sub program
invalidates packet pointers might be an option. Does it break too many
programs in the wild?

From an end-user perspective, the presented solution makes debugging
verifier errors harder. An error message doesn't tell which call
invalidated pointers. Whether verifier considers a particular sub
program as pointer-invalidating is not revealed. I foresee exciting
debugging sessions.

It probably doesn't matter, but I don't like bpf_xdp_adjust_meta(xdp, 0)
hack to mark a program as pointer-invalidating either.

I would've preferred a simple static rule "calls to global sub programs
invalidate packet pointers" with an optional decl tag to mark a sub
program as non-invalidating, in line with "arg:nonnull".

> Making the change in bpf_helper_changes_pkt_data() automatically makes
> use of check_cfg() logic that computes 'changes_pkt_data' effect for
> global sub-programs, such that the following program could be
> rejected:
> 
>    int tail_call(struct __sk_buff *sk)
>    {
>     bpf_tail_call_static(sk, &jmp_table, 0);
>     return 0;
>    }
> 
>    SEC("tc")
>    int not_safe(struct __sk_buff *sk)
>    {
>     int *p = (void *)(long)sk->data;
>     ... make p valid ...
>     tail_call(sk);
>     *p = 42; /* this is unsafe */
>     ...
>    }
> 
> The tc_bpf2bpf.c:subprog_tc() needs change: mark it as a function that
> can invalidate packet pointers. Otherwise, it can't be freplaced with
> tailcall_freplace.c:entry_freplace() that does a tail call.
> 
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
> net/core/filter.c                              | 2 ++
> tools/testing/selftests/bpf/progs/tc_bpf2bpf.c | 2 ++
> 2 files changed, 4 insertions(+)
> 
> diff --git a/net/core/filter.c b/net/core/filter.c
> index efb75eed2e35..21131ec25f24 100644
> --- a/net/core/filter.c
> +++ b/net/core/filter.c
> @@ -7924,6 +7924,8 @@ bool bpf_helper_changes_pkt_data(enum bpf_func_id func_id)
> case BPF_FUNC_xdp_adjust_head:
> case BPF_FUNC_xdp_adjust_meta:
> case BPF_FUNC_xdp_adjust_tail:
> + /* tail-called program could call any of the above */
> + case BPF_FUNC_tail_call:
> return true;
> default:
> return false;
> diff --git a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
> index d1a57f7d09bd..fe6249d99b31 100644
> --- a/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
> +++ b/tools/testing/selftests/bpf/progs/tc_bpf2bpf.c
> @@ -11,6 +11,8 @@ int subprog_tc(struct __sk_buff *skb)
> 
> __sink(skb);
> __sink(ret);
> + /* let verifier know that 'subprog_tc' can change pointers to skb->data */
> + bpf_skb_change_proto(skb, 0, 0);
> return ret;
> }
> 
> -- 
> 2.47.0
> 


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10 10:35   ` Nick Zavaritsky
@ 2024-12-10 18:23     ` Alexei Starovoitov
  2024-12-10 18:29       ` Eduard Zingerman
  0 siblings, 1 reply; 17+ messages in thread
From: Alexei Starovoitov @ 2024-12-10 18:23 UTC (permalink / raw)
  To: Nick Zavaritsky
  Cc: Eduard Zingerman, bpf, Alexei Starovoitov, Andrii Nakryiko,
	Daniel Borkmann, Martin KaFai Lau, Kernel Team, Yonghong Song

On Tue, Dec 10, 2024 at 2:35 AM Nick Zavaritsky <mejedi@gmail.com> wrote:
>
>
> > Tail-called programs could execute any of the helpers that invalidate
> > packet pointers. Hence, conservatively assume that each tail call
> > invalidates packet pointers.
>
> Tail calls look like a clear limitation of "auto-infer packet
> invalidation effect" approach. Correct solution requires propagating
> effects in the dynamic callee-caller graph, unlikely to ever happen.
>
> I'm curious if assuming that every call to a global sub program
> invalidates packet pointers might be an option. Does it break too many
> programs in the wild?

It might. Assuming every global prog changes pkt data is too risky,
also it would diverge global vs static verification even further,
which is a bad user experience.

> From an end-user perspective, the presented solution makes debugging
> verifier errors harder. An error message doesn't tell which call
> invalidated pointers. Whether verifier considers a particular sub
> program as pointer-invalidating is not revealed. I foresee exciting
> debugging sessions.

There is such a risk.

> It probably doesn't matter, but I don't like bpf_xdp_adjust_meta(xdp, 0)
> hack to mark a program as pointer-invalidating either.
>
> I would've preferred a simple static rule "calls to global sub programs
> invalidate packet pointers" with an optional decl tag to mark a sub
> program as non-invalidating, in line with "arg:nonnull".

That's not an option.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10 18:23     ` Alexei Starovoitov
@ 2024-12-10 18:29       ` Eduard Zingerman
  2024-12-10 18:31         ` Alexei Starovoitov
  0 siblings, 1 reply; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10 18:29 UTC (permalink / raw)
  To: Alexei Starovoitov, Nick Zavaritsky
  Cc: bpf, Alexei Starovoitov, Andrii Nakryiko, Daniel Borkmann,
	Martin KaFai Lau, Kernel Team, Yonghong Song

On Tue, 2024-12-10 at 10:23 -0800, Alexei Starovoitov wrote:
> On Tue, Dec 10, 2024 at 2:35 AM Nick Zavaritsky <mejedi@gmail.com> wrote:
> > 
> > 
> > > Tail-called programs could execute any of the helpers that invalidate
> > > packet pointers. Hence, conservatively assume that each tail call
> > > invalidates packet pointers.
> > 
> > Tail calls look like a clear limitation of "auto-infer packet
> > invalidation effect" approach. Correct solution requires propagating
> > effects in the dynamic callee-caller graph, unlikely to ever happen.
> > 
> > I'm curious if assuming that every call to a global sub program
> > invalidates packet pointers might be an option. Does it break too many
> > programs in the wild?
> 
> It might. Assuming every global prog changes pkt data is too risky,
> also it would diverge global vs static verification even further,
> which is a bad user experience.

I assume that freplace and tail calls are used much less often than
global calls. If so, I think that some degree of inference, even with
limitations, would be convenient more often than not.

> > From an end-user perspective, the presented solution makes debugging
> > verifier errors harder. An error message doesn't tell which call
> > invalidated pointers. Whether verifier considers a particular sub
> > program as pointer-invalidating is not revealed. I foresee exciting
> > debugging sessions.
> 
> There is such a risk.

I can do a v4 and add a line in the log each time the packet pointers
are invalidated. Such lines would be presented in verification failure
logs. (Can also print every register/stack slot where packet pointer
is invalidated, but this may be too verbose).

[...]


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10 18:29       ` Eduard Zingerman
@ 2024-12-10 18:31         ` Alexei Starovoitov
  2024-12-10 18:52           ` Eduard Zingerman
  0 siblings, 1 reply; 17+ messages in thread
From: Alexei Starovoitov @ 2024-12-10 18:31 UTC (permalink / raw)
  To: Eduard Zingerman
  Cc: Nick Zavaritsky, bpf, Alexei Starovoitov, Andrii Nakryiko,
	Daniel Borkmann, Martin KaFai Lau, Kernel Team, Yonghong Song

On Tue, Dec 10, 2024 at 10:29 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2024-12-10 at 10:23 -0800, Alexei Starovoitov wrote:
> > On Tue, Dec 10, 2024 at 2:35 AM Nick Zavaritsky <mejedi@gmail.com> wrote:
> > >
> > >
> > > > Tail-called programs could execute any of the helpers that invalidate
> > > > packet pointers. Hence, conservatively assume that each tail call
> > > > invalidates packet pointers.
> > >
> > > Tail calls look like a clear limitation of "auto-infer packet
> > > invalidation effect" approach. Correct solution requires propagating
> > > effects in the dynamic callee-caller graph, unlikely to ever happen.
> > >
> > > I'm curious if assuming that every call to a global sub program
> > > invalidates packet pointers might be an option. Does it break too many
> > > programs in the wild?
> >
> > It might. Assuming every global prog changes pkt data is too risky,
> > also it would diverge global vs static verification even further,
> > which is a bad user experience.
>
> I assume that freplace and tail calls are used much less often than
> global calls. If so, I think that some degree of inference, even with
> limitations, would be convenient more often than not.
>
> > > From an end-user perspective, the presented solution makes debugging
> > > verifier errors harder. An error message doesn't tell which call
> > > invalidated pointers. Whether verifier considers a particular sub
> > > program as pointer-invalidating is not revealed. I foresee exciting
> > > debugging sessions.
> >
> > There is such a risk.
>
> I can do a v4 and add a line in the log each time the packet pointers
> are invalidated. Such lines would be presented in verification failure
> logs. (Can also print every register/stack slot where packet pointer
> is invalidated, but this may be too verbose).

This is something to consider for bpf-next.
For bpf we need a minimal fix. So I applied as-is.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions
  2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
                   ` (7 preceding siblings ...)
  2024-12-10  4:11 ` [PATCH bpf v2 8/8] selftests/bpf: validate that tail call invalidates " Eduard Zingerman
@ 2024-12-10 18:40 ` patchwork-bot+netdevbpf
  8 siblings, 0 replies; 17+ messages in thread
From: patchwork-bot+netdevbpf @ 2024-12-10 18:40 UTC (permalink / raw)
  To: Eduard Zingerman
  Cc: bpf, ast, andrii, daniel, martin.lau, kernel-team, yonghong.song,
	mejedi

Hello:

This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Mon,  9 Dec 2024 20:10:52 -0800 you wrote:
> 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);
>     }
> 
> [...]

Here is the summary with links:
  - [bpf,v2,1/8] bpf: add find_containing_subprog() utility function
    https://git.kernel.org/bpf/bpf/c/27e88bc4df1d
  - [bpf,v2,2/8] bpf: refactor bpf_helper_changes_pkt_data to use helper number
    https://git.kernel.org/bpf/bpf/c/b238e187b4a2
  - [bpf,v2,3/8] bpf: track changes_pkt_data property for global functions
    https://git.kernel.org/bpf/bpf/c/51081a3f25c7
  - [bpf,v2,4/8] selftests/bpf: test for changing packet data from global functions
    https://git.kernel.org/bpf/bpf/c/3f23ee5590d9
  - [bpf,v2,5/8] bpf: check changes_pkt_data property for extension programs
    https://git.kernel.org/bpf/bpf/c/81f6d0530ba0
  - [bpf,v2,6/8] selftests/bpf: freplace tests for tracking of changes_packet_data
    https://git.kernel.org/bpf/bpf/c/89ff40890d8f
  - [bpf,v2,7/8] bpf: consider that tail calls invalidate packet pointers
    https://git.kernel.org/bpf/bpf/c/1a4607ffba35
  - [bpf,v2,8/8] selftests/bpf: validate that tail call invalidates packet pointers
    https://git.kernel.org/bpf/bpf/c/d9706b56e13b

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html



^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10 18:31         ` Alexei Starovoitov
@ 2024-12-10 18:52           ` Eduard Zingerman
  2024-12-10 19:00             ` Alexei Starovoitov
  0 siblings, 1 reply; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10 18:52 UTC (permalink / raw)
  To: Alexei Starovoitov
  Cc: Nick Zavaritsky, bpf, Alexei Starovoitov, Andrii Nakryiko,
	Daniel Borkmann, Martin KaFai Lau, Kernel Team, Yonghong Song

On Tue, 2024-12-10 at 10:31 -0800, Alexei Starovoitov wrote:

[...]

> > > > From an end-user perspective, the presented solution makes debugging
> > > > verifier errors harder. An error message doesn't tell which call
> > > > invalidated pointers. Whether verifier considers a particular sub
> > > > program as pointer-invalidating is not revealed. I foresee exciting
> > > > debugging sessions.
> > > 
> > > There is such a risk.
> > 
> > I can do a v4 and add a line in the log each time the packet pointers
> > are invalidated. Such lines would be presented in verification failure
> > logs. (Can also print every register/stack slot where packet pointer
> > is invalidated, but this may be too verbose).
> 
> This is something to consider for bpf-next.
> For bpf we need a minimal fix. So I applied as-is.

I must admit, I'm not familiar with the way bpf/bpf-next interact.
Should I wait for certain merges to happen before posting a patch
to bpf-next?


^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10 18:52           ` Eduard Zingerman
@ 2024-12-10 19:00             ` Alexei Starovoitov
  2024-12-10 19:06               ` Eduard Zingerman
  0 siblings, 1 reply; 17+ messages in thread
From: Alexei Starovoitov @ 2024-12-10 19:00 UTC (permalink / raw)
  To: Eduard Zingerman
  Cc: Nick Zavaritsky, bpf, Alexei Starovoitov, Andrii Nakryiko,
	Daniel Borkmann, Martin KaFai Lau, Kernel Team, Yonghong Song

On Tue, Dec 10, 2024 at 10:52 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Tue, 2024-12-10 at 10:31 -0800, Alexei Starovoitov wrote:
>
> [...]
>
> > > > > From an end-user perspective, the presented solution makes debugging
> > > > > verifier errors harder. An error message doesn't tell which call
> > > > > invalidated pointers. Whether verifier considers a particular sub
> > > > > program as pointer-invalidating is not revealed. I foresee exciting
> > > > > debugging sessions.
> > > >
> > > > There is such a risk.
> > >
> > > I can do a v4 and add a line in the log each time the packet pointers
> > > are invalidated. Such lines would be presented in verification failure
> > > logs. (Can also print every register/stack slot where packet pointer
> > > is invalidated, but this may be too verbose).
> >
> > This is something to consider for bpf-next.
> > For bpf we need a minimal fix. So I applied as-is.
>
> I must admit, I'm not familiar with the way bpf/bpf-next interact.
> Should I wait for certain merges to happen before posting a patch
> to bpf-next?

bpf tree is for fixes only.
We typically send PR every week.
Once it lands in Linus's tree we merge the fixes into bpf-next.
At that time follows up can be send targeting bpf-next.

^ permalink raw reply	[flat|nested] 17+ messages in thread

* Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers
  2024-12-10 19:00             ` Alexei Starovoitov
@ 2024-12-10 19:06               ` Eduard Zingerman
  0 siblings, 0 replies; 17+ messages in thread
From: Eduard Zingerman @ 2024-12-10 19:06 UTC (permalink / raw)
  To: Alexei Starovoitov
  Cc: Nick Zavaritsky, bpf, Alexei Starovoitov, Andrii Nakryiko,
	Daniel Borkmann, Martin KaFai Lau, Kernel Team, Yonghong Song

On Tue, 2024-12-10 at 11:00 -0800, Alexei Starovoitov wrote:

[...]

> bpf tree is for fixes only.
> We typically send PR every week.
> Once it lands in Linus's tree we merge the fixes into bpf-next.
> At that time follows up can be send targeting bpf-next.

Will send next week, then.
Thank you.


^ permalink raw reply	[flat|nested] 17+ messages in thread

end of thread, other threads:[~2024-12-10 19:06 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-12-10  4:10 [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
2024-12-10  4:10 ` [PATCH bpf v2 1/8] bpf: add find_containing_subprog() utility function Eduard Zingerman
2024-12-10  4:10 ` [PATCH bpf v2 2/8] bpf: refactor bpf_helper_changes_pkt_data to use helper number Eduard Zingerman
2024-12-10  4:10 ` [PATCH bpf v2 3/8] bpf: track changes_pkt_data property for global functions Eduard Zingerman
2024-12-10  4:10 ` [PATCH bpf v2 4/8] selftests/bpf: test for changing packet data from " Eduard Zingerman
2024-12-10  4:10 ` [PATCH bpf v2 5/8] bpf: check changes_pkt_data property for extension programs Eduard Zingerman
2024-12-10  4:10 ` [PATCH bpf v2 6/8] selftests/bpf: freplace tests for tracking of changes_packet_data Eduard Zingerman
2024-12-10  4:10 ` [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers Eduard Zingerman
2024-12-10 10:35   ` Nick Zavaritsky
2024-12-10 18:23     ` Alexei Starovoitov
2024-12-10 18:29       ` Eduard Zingerman
2024-12-10 18:31         ` Alexei Starovoitov
2024-12-10 18:52           ` Eduard Zingerman
2024-12-10 19:00             ` Alexei Starovoitov
2024-12-10 19:06               ` Eduard Zingerman
2024-12-10  4:11 ` [PATCH bpf v2 8/8] selftests/bpf: validate that tail call invalidates " Eduard Zingerman
2024-12-10 18:40 ` [PATCH bpf v2 0/8] bpf: track changes_pkt_data property for global functions patchwork-bot+netdevbpf

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox