Skip to contentSkip to conversation

bpf: track changes_pkt_data property for global functions

PATCH Applied Eduard Zingerman 4 participants 17 messages Dec 10, 2024

Subsystems (6)
lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

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

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/[email protected]/
[1] https://lore.kernel.org/bpf/[email protected]/

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

PATCH v2 1/8 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 v2 2/8 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 v2 3/8 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 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.

---
 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
#4 lore raw

PATCH v2 4/8 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
author maintainer
#5 lore raw

PATCH v2 5/8 bpf: check changes_pkt_data property for extension programs

In reply to Eduard Zingerman

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.

---
 include/linux/bpf.h   |  1 +
 kernel/bpf/verifier.c | 16 ++++++++++++----
 2 files changed, 13 insertions(+), 4 deletions(-)
include/linux/bpf.h +1 -0
index eaee2a819f4c..fe392d074973 100644
@@ -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;
kernel/bpf/verifier.c +12 -4
index 6a29b68cebd6..c2e5d0e6e3d0 100644
@@ -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;
Signature · 1 line
2.47.0
author maintainer
#6 lore raw

PATCH v2 6/8 selftests/bpf: freplace tests for tracking of changes_packet_data

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

---
 .../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
tools/testing/selftests/bpf/prog_tests/changes_pkt_data.c new file +76 -0
new file mode 100644
index 000000000000..c0c7202f6c5c
@@ -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);
+}
tools/testing/selftests/bpf/progs/changes_pkt_data.c new file +26 -0
new file mode 100644
index 000000000000..f87da8e9d6b3
@@ -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";
tools/testing/selftests/bpf/progs/changes_pkt_data_freplace.c new file +18 -0
new file mode 100644
index 000000000000..0e525beb8603
@@ -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";
Signature · 1 line
2.47.0
author maintainer
#7 lore raw

PATCH v2 7/8 bpf: consider that tail calls invalidate packet pointers

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

---
 net/core/filter.c                              | 2 ++
 tools/testing/selftests/bpf/progs/tc_bpf2bpf.c | 2 ++
 2 files changed, 4 insertions(+)
net/core/filter.c +2 -0
index efb75eed2e35..21131ec25f24 100644
@@ -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;
tools/testing/selftests/bpf/progs/tc_bpf2bpf.c +2 -0
index d1a57f7d09bd..fe6249d99b31 100644
@@ -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;
 }
 
Signature · 1 line
2.47.0
#8 lore raw

Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers

Quoted 4 lines

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

Quoted 60 lines

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.

---
net/core/filter.c | 2 ++
tools/testing/selftests/bpf/progs/tc_bpf2bpf.c | 2 ++

2 files changed, 4 insertions(+)
net/core/filter.c +0 -0
index efb75eed2e35..21131ec25f24 100644
@@ -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;

tools/testing/selftests/bpf/progs/tc_bpf2bpf.c +2 -0
index d1a57f7d09bd..fe6249d99b31 100644
@@ -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;
 }
 
Signature · 1 line
2.47.0
#9 lore raw

Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers

Quoted 6 lines · Nick Zavaritsky
Quoted 5 lines

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

Quoted 7 lines

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.

Quoted 5 lines

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.

Quoted 6 lines

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.

author maintainer
#10 lore raw

Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers

Quoted 11 lines · Alexei Starovoitov
Quoted 10 lines · Nick Zavaritsky
Quoted 5 lines

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.

Quoted 7 lines
Quoted 3 lines

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.

Quoted 7 lines
Quoted 5 lines

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

[...]

#11 lore raw

Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers

Quoted 31 lines · Eduard Zingerman
Quoted 11 lines · Alexei Starovoitov
Quoted 10 lines · Nick Zavaritsky
Quoted 5 lines

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.

Quoted 7 lines
Quoted 3 lines

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.

Quoted 6 lines
Quoted 5 lines

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.

Quoted 6 lines
Quoted 1 line

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.

author maintainer
#12 lore raw

Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers

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

[...]

Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Quoted 5 lines

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.

Quoted 7 lines
Quoted 4 lines

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?

#13 lore raw

Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers

Quoted 18 lines · Eduard Zingerman

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

[...]

Quoted 13 lines
Quoted 12 lines
Quoted 7 lines
Quoted 5 lines

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

Quoted 6 lines
Quoted 2 lines

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.

author maintainer
#14 lore raw

Re: [PATCH bpf v2 7/8] bpf: consider that tail calls invalidate packet pointers

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

[...]

Quoted 4 lines

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.

author maintainer
#15 lore raw

PATCH v2 8/8 selftests/bpf: validate that tail call invalidates packet pointers

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

---
 .../selftests/bpf/progs/verifier_sock.c       | 28 +++++++++++++++++++
 1 file changed, 28 insertions(+)
tools/testing/selftests/bpf/progs/verifier_sock.c +28 -0
index 51826379a1aa..0d5e56dffabb 100644
@@ -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";
Signature · 1 line
2.47.0
#16 lore raw
In reply to Eduard Zingerman
This series was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:

Quoted 10 lines · 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!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html