Skip to contentSkip to conversation

verify callbacks as if they are called unknown number of times

PATCH Superseded Eduard Zingerman 2 participants 19 messages Nov 18, 2023 – Nov 20, 2023

Subsystems (5)
Kselftest BPF BPF selftests BPF core +1 more subsystems

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Eduard Zingerman

author maintainer
#0 lore raw

v2 cover verify callbacks as if they are called unknown number of times

This series updates verifier logic for callback functions handling. Current master simulates callback body execution exactly once, which leads to verifier not detecting unsafe programs like below:

    static int unsafe_on_zero_iter_cb(__u32 idx, struct num_context *ctx)
    {
        ctx->i = 0;
        return 0;
    }
    
    SEC("?raw_tp")
    int unsafe_on_zero_iter(void *unused)
    {
        struct num_context loop_ctx = { .i = 32 };
        __u8 choice_arr[2] = { 0, 1 };
    
        bpf_loop(100, unsafe_on_zero_iter_cb, &loop_ctx, 0);
        return choice_arr[loop_ctx.i];
    }

This was reported previously in [0].
The basic idea of the fix is to schedule callback entry state for verification in env->head until some identical, previously visited state in current DFS state traversal is found. Same logic as with open coded iterators, and builds on top recent fixes [1] for those.

The series is structured as follows:
- patches #1,2,3 update strobemeta, xdp_synproxy selftests and bpf_loop_bench benchmark to allow convergence of the bpf_loop callback states;
- patches #4,5 just shuffle the code a bit;
- patch #6 is the main part of the series;
- patch #7 adds test cases for #6;
- patch #8 extend patch #6 with same speculative scalar widening logic, as used for open coded iterators;
- patch #9 adds test cases for #8;
- patch #10 extends patch #6 to track maximal number of callback executions specifically for bpf_loop();
- patch #11 adds test cases for #10.

Veristat results comparing this series to master+patches #1,2,3 using selftests show the following difference:

File                       Program        States (A)  States (B)  States (DIFF)
-------------------------  -------------  ----------  ----------  -------------
bpf_loop_bench.bpf.o       benchmark               1           2  +1 (+100.00%)
pyperf600_bpf_loop.bpf.o   on_event              322         407  +85 (+26.40%)
strobemeta_bpf_loop.bpf.o  on_event              113         151  +38 (+33.63%)
xdp_synproxy_kern.bpf.o    syncookie_tc          341         291  -50 (-14.66%)
xdp_synproxy_kern.bpf.o    syncookie_xdp         344         301  -43 (-12.50%)

Veristat results comparing this series to master using Tetragon BPF files [2] also show some differences.
States diff varies from +2% to +15% on 23 programs out of 186, no new failures.

Changelog V1 [3] -> V2, changes suggested by Andrii:
- small changes for error handling code in __check_func_call();
- callback body processing log is now matched in relevant verifier_subprog_precision.c tests;
- R1 passed to bpf_loop() is now always marked as precise;
- log level 2 message for bpf_loop() iteration termination instead of iteration depth messages;
- __no_msg macro removed;
- bpf_loop_iter_limit_nested updated to avoid using __no_msg;
- commit message for patch #3 updated according to Alexei's request.

[0] https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@mail.gmail.com/
[1] https://lore.kernel.org/bpf/[email protected]/
[2] [email protected]:cilium/tetragon.git
[3] https://lore.kernel.org/bpf/[email protected]/T/#t

Eduard Zingerman (11):
selftests/bpf: track tcp payload offset as scalar in xdp_synproxy selftests/bpf: track string payload offset as scalar in strobemeta selftests/bpf: fix bpf_loop_bench for new callback verification scheme
bpf: extract __check_reg_arg() utility function
bpf: extract setup_func_entry() utility function
bpf: verify callbacks as if they are called unknown number of times selftests/bpf: tests for iterating callbacks
bpf: widening for callback iterators
selftests/bpf: test widening for iterating callbacks
bpf: keep track of max number of bpf_loop callback iterations selftests/bpf: check if max number of bpf_loop iterations is tracked

 include/linux/bpf_verifier.h                  |  14 +
 kernel/bpf/verifier.c                         | 395 ++++++++++++------
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/bpf_loop_bench.c      |  13 +-
 tools/testing/selftests/bpf/progs/cb_refs.c   |   1 +
 .../selftests/bpf/progs/exceptions_fail.c     |   2 +
 .../testing/selftests/bpf/progs/strobemeta.h  |  78 ++--
 .../bpf/progs/verifier_iterating_callbacks.c  | 250 +++++++++++
 .../bpf/progs/verifier_subprog_precision.c    |  80 +++-
 .../selftests/bpf/progs/xdp_synproxy_kern.c   |  84 ++--
 10 files changed, 702 insertions(+), 217 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
Signature · 1 line
2.42.1
author maintainer
#1 lore raw

PATCH v2 1/11 selftests/bpf: track tcp payload offset as scalar in xdp_synproxy

This change prepares syncookie_{tc,xdp} for update in callbakcs verification logic. To allow bpf_loop() verification converge when multiple callback itreations are considered:
- track offset inside TCP payload explicitly, not as a part of the pointer;
- make sure that offset does not exceed MAX_PACKET_OFF enforced by verifier;
- make sure that offset is tracked as unbound scalar between iterations, otherwise verifier won't be able infer that bpf_loop callback reaches identical states.

Acked-by Andrii Nakryiko <[email protected]>
Signed-off-by Eduard Zingerman <[email protected]>
---
 .../selftests/bpf/progs/xdp_synproxy_kern.c   | 84 ++++++++++++-------
 1 file changed, 52 insertions(+), 32 deletions(-)
tools/testing/selftests/bpf/progs/xdp_synproxy_kern.c +52 -32
index e959336c7a73..80f620602d50 100644
@@ -53,6 +53,8 @@
 #define DEFAULT_TTL 64
 #define MAX_ALLOWED_PORTS 8
 
+#define MAX_PACKET_OFF 0xffff
+
 #define swap(a, b) \
 	do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
 

@@ -183,63 +185,76 @@ static __always_inline __u32 tcp_clock_ms(void)
 }
 
 struct tcpopt_context {
-	__u8 *ptr;
-	__u8 *end;
+	void *data;
 	void *data_end;
 	__be32 *tsecr;
 	__u8 wscale;
 	bool option_timestamp;
 	bool option_sack;
+	__u32 off;
 };
 
-static int tscookie_tcpopt_parse(struct tcpopt_context *ctx)
+static __always_inline u8 *next(struct tcpopt_context *ctx, __u32 sz)
 {
-	__u8 opcode, opsize;
+	__u64 off = ctx->off;
+	__u8 *data;
 
-	if (ctx->ptr >= ctx->end)
-		return 1;
-	if (ctx->ptr >= ctx->data_end)
-		return 1;
+	/* Verifier forbids access to packet when offset exceeds MAX_PACKET_OFF */
+	if (off > MAX_PACKET_OFF - sz)
+		return NULL;
 
-	opcode = ctx->ptr[0];
+	data = ctx->data + off;
+	barrier_var(data);
+	if (data + sz >= ctx->data_end)
+		return NULL;
 
-	if (opcode == TCPOPT_EOL)
-		return 1;
-	if (opcode == TCPOPT_NOP) {
-		++ctx->ptr;
-		return 0;
-	}
+	ctx->off += sz;
+	return data;
+}
 
-	if (ctx->ptr + 1 >= ctx->end)
-		return 1;
-	if (ctx->ptr + 1 >= ctx->data_end)
+static int tscookie_tcpopt_parse(struct tcpopt_context *ctx)
+{
+	__u8 *opcode, *opsize, *wscale, *tsecr;
+	__u32 off = ctx->off;
+
+	opcode = next(ctx, 1);
+	if (!opcode)
 		return 1;
-	opsize = ctx->ptr[1];
-	if (opsize < 2)
+
+	if (*opcode == TCPOPT_EOL)
 		return 1;
+	if (*opcode == TCPOPT_NOP)
+		return 0;
 
-	if (ctx->ptr + opsize > ctx->end)
+	opsize = next(ctx, 1);
+	if (!opsize || *opsize < 2)
 		return 1;
 
-	switch (opcode) {
+	switch (*opcode) {
 	case TCPOPT_WINDOW:
-		if (opsize == TCPOLEN_WINDOW && ctx->ptr + TCPOLEN_WINDOW <= ctx->data_end)
-			ctx->wscale = ctx->ptr[2] < TCP_MAX_WSCALE ? ctx->ptr[2] : TCP_MAX_WSCALE;
+		wscale = next(ctx, 1);
+		if (!wscale)
+			return 1;
+		if (*opsize == TCPOLEN_WINDOW)
+			ctx->wscale = *wscale < TCP_MAX_WSCALE ? *wscale : TCP_MAX_WSCALE;
 		break;
 	case TCPOPT_TIMESTAMP:
-		if (opsize == TCPOLEN_TIMESTAMP && ctx->ptr + TCPOLEN_TIMESTAMP <= ctx->data_end) {
+		tsecr = next(ctx, 4);
+		if (!tsecr)
+			return 1;
+		if (*opsize == TCPOLEN_TIMESTAMP) {
 			ctx->option_timestamp = true;
 			/* Client's tsval becomes our tsecr. */
-			*ctx->tsecr = get_unaligned((__be32 *)(ctx->ptr + 2));
+			*ctx->tsecr = get_unaligned((__be32 *)tsecr);
 		}
 		break;
 	case TCPOPT_SACK_PERM:
-		if (opsize == TCPOLEN_SACK_PERM)
+		if (*opsize == TCPOLEN_SACK_PERM)
 			ctx->option_sack = true;
 		break;
 	}
 
-	ctx->ptr += opsize;
+	ctx->off = off + *opsize;
 
 	return 0;
 }

@@ -256,16 +271,21 @@ static int tscookie_tcpopt_parse_batch(__u32 index, void *context)
 
 static __always_inline bool tscookie_init(struct tcphdr *tcp_header,
 					  __u16 tcp_len, __be32 *tsval,
-					  __be32 *tsecr, void *data_end)
+					  __be32 *tsecr, void *data, void *data_end)
 {
 	struct tcpopt_context loop_ctx = {
-		.ptr = (__u8 *)(tcp_header + 1),
-		.end = (__u8 *)tcp_header + tcp_len,
+		.data = data,
 		.data_end = data_end,
 		.tsecr = tsecr,
 		.wscale = TS_OPT_WSCALE_MASK,
 		.option_timestamp = false,
 		.option_sack = false,
+		/* Note: currently verifier would track .off as unbound scalar.
+		 *       In case if verifier would at some point get smarter and
+		 *       compute bounded value for this var, beware that it might
+		 *       hinder bpf_loop() convergence validation.
+		 */
+		.off = (__u8 *)(tcp_header + 1) - (__u8 *)data,
 	};
 	u32 cookie;
 

@@ -635,7 +655,7 @@ static __always_inline int syncookie_handle_syn(struct header_pointers *hdr,
 	cookie = (__u32)value;
 
 	if (tscookie_init((void *)hdr->tcp, hdr->tcp_len,
-			  &tsopt_buf[0], &tsopt_buf[1], data_end))
+			  &tsopt_buf[0], &tsopt_buf[1], data, data_end))
 		tsopt = tsopt_buf;
 
 	/* Check that there is enough space for a SYNACK. It also covers
Signature · 1 line
2.42.1
author maintainer
#2 lore raw

PATCH v2 2/11 selftests/bpf: track string payload offset as scalar in strobemeta

In reply to Eduard Zingerman

This change prepares strobemeta for update in callbacks verification logic. To allow bpf_loop() verification converge when multiple callback iterations are considered:
- track offset inside strobemeta_payload->payload directly as scalar value;
- at each iteration make sure that remaining strobemeta_payload->payload capacity is sufficient for execution of read_{map,str}_var functions;
- make sure that offset is tracked as unbound scalar between iterations, otherwise verifier won't be able infer that bpf_loop callback reaches identical states.

Acked-by Andrii Nakryiko <[email protected]>
Signed-off-by Eduard Zingerman <[email protected]>
---
 .../testing/selftests/bpf/progs/strobemeta.h  | 78 ++++++++++++-------
 1 file changed, 48 insertions(+), 30 deletions(-)
tools/testing/selftests/bpf/progs/strobemeta.h +48 -30
index e02cfd380746..40df2cc26eaf 100644
@@ -24,9 +24,11 @@ struct task_struct {};
 #define STACK_TABLE_EPOCH_SHIFT 20
 #define STROBE_MAX_STR_LEN 1
 #define STROBE_MAX_CFGS 32
+#define READ_MAP_VAR_PAYLOAD_CAP					\
+	((1 + STROBE_MAX_MAP_ENTRIES * 2) * STROBE_MAX_STR_LEN)
 #define STROBE_MAX_PAYLOAD						\
 	(STROBE_MAX_STRS * STROBE_MAX_STR_LEN +				\
-	STROBE_MAX_MAPS * (1 + STROBE_MAX_MAP_ENTRIES * 2) * STROBE_MAX_STR_LEN)
+	 STROBE_MAX_MAPS * READ_MAP_VAR_PAYLOAD_CAP)
 
 struct strobe_value_header {
 	/*

@@ -355,7 +357,7 @@ static __always_inline uint64_t read_str_var(struct strobemeta_cfg *cfg,
 					     size_t idx, void *tls_base,
 					     struct strobe_value_generic *value,
 					     struct strobemeta_payload *data,
-					     void *payload)
+					     size_t off)
 {
 	void *location;
 	uint64_t len;

@@ -366,7 +368,7 @@ static __always_inline uint64_t read_str_var(struct strobemeta_cfg *cfg,
 		return 0;
 
 	bpf_probe_read_user(value, sizeof(struct strobe_value_generic), location);
-	len = bpf_probe_read_user_str(payload, STROBE_MAX_STR_LEN, value->ptr);
+	len = bpf_probe_read_user_str(&data->payload[off], STROBE_MAX_STR_LEN, value->ptr);
 	/*
 	 * if bpf_probe_read_user_str returns error (<0), due to casting to
 	 * unsinged int, it will become big number, so next check is

@@ -378,14 +380,14 @@ static __always_inline uint64_t read_str_var(struct strobemeta_cfg *cfg,
 		return 0;
 
 	data->str_lens[idx] = len;
-	return len;
+	return off + len;
 }
 
-static __always_inline void *read_map_var(struct strobemeta_cfg *cfg,
-					  size_t idx, void *tls_base,
-					  struct strobe_value_generic *value,
-					  struct strobemeta_payload *data,
-					  void *payload)
+static __always_inline uint64_t read_map_var(struct strobemeta_cfg *cfg,
+					     size_t idx, void *tls_base,
+					     struct strobe_value_generic *value,
+					     struct strobemeta_payload *data,
+					     size_t off)
 {
 	struct strobe_map_descr* descr = &data->map_descrs[idx];
 	struct strobe_map_raw map;

@@ -397,11 +399,11 @@ static __always_inline void *read_map_var(struct strobemeta_cfg *cfg,
 
 	location = calc_location(&cfg->map_locs[idx], tls_base);
 	if (!location)
-		return payload;
+		return off;
 
 	bpf_probe_read_user(value, sizeof(struct strobe_value_generic), location);
 	if (bpf_probe_read_user(&map, sizeof(struct strobe_map_raw), value->ptr))
-		return payload;
+		return off;
 
 	descr->id = map.id;
 	descr->cnt = map.cnt;

@@ -410,10 +412,10 @@ static __always_inline void *read_map_var(struct strobemeta_cfg *cfg,
 		data->req_meta_valid = 1;
 	}
 
-	len = bpf_probe_read_user_str(payload, STROBE_MAX_STR_LEN, map.tag);
+	len = bpf_probe_read_user_str(&data->payload[off], STROBE_MAX_STR_LEN, map.tag);
 	if (len <= STROBE_MAX_STR_LEN) {
 		descr->tag_len = len;
-		payload += len;
+		off += len;
 	}
 
 #ifdef NO_UNROLL

@@ -426,22 +428,22 @@ static __always_inline void *read_map_var(struct strobemeta_cfg *cfg,
 			break;
 
 		descr->key_lens[i] = 0;
-		len = bpf_probe_read_user_str(payload, STROBE_MAX_STR_LEN,
+		len = bpf_probe_read_user_str(&data->payload[off], STROBE_MAX_STR_LEN,
 					      map.entries[i].key);
 		if (len <= STROBE_MAX_STR_LEN) {
 			descr->key_lens[i] = len;
-			payload += len;
+			off += len;
 		}
 		descr->val_lens[i] = 0;
-		len = bpf_probe_read_user_str(payload, STROBE_MAX_STR_LEN,
+		len = bpf_probe_read_user_str(&data->payload[off], STROBE_MAX_STR_LEN,
 					      map.entries[i].val);
 		if (len <= STROBE_MAX_STR_LEN) {
 			descr->val_lens[i] = len;
-			payload += len;
+			off += len;
 		}
 	}
 
-	return payload;
+	return off;
 }
 
 #ifdef USE_BPF_LOOP

@@ -455,14 +457,20 @@ struct read_var_ctx {
 	struct strobemeta_payload *data;
 	void *tls_base;
 	struct strobemeta_cfg *cfg;
-	void *payload;
+	size_t payload_off;
 	/* value gets mutated */
 	struct strobe_value_generic *value;
 	enum read_type type;
 };
 
-static int read_var_callback(__u32 index, struct read_var_ctx *ctx)
+static int read_var_callback(__u64 index, struct read_var_ctx *ctx)
 {
+	/* lose precision info for ctx->payload_off, verifier won't track
+	 * double xor, barrier_var() is needed to force clang keep both xors.
+	 */
+	ctx->payload_off ^= index;
+	barrier_var(ctx->payload_off);
+	ctx->payload_off ^= index;
 	switch (ctx->type) {
 	case READ_INT_VAR:
 		if (index >= STROBE_MAX_INTS)

@@ -472,14 +480,18 @@ static int read_var_callback(__u32 index, struct read_var_ctx *ctx)
 	case READ_MAP_VAR:
 		if (index >= STROBE_MAX_MAPS)
 			return 1;
-		ctx->payload = read_map_var(ctx->cfg, index, ctx->tls_base,
-					    ctx->value, ctx->data, ctx->payload);
+		if (ctx->payload_off > sizeof(ctx->data->payload) - READ_MAP_VAR_PAYLOAD_CAP)
+			return 1;
+		ctx->payload_off = read_map_var(ctx->cfg, index, ctx->tls_base,
+						ctx->value, ctx->data, ctx->payload_off);
 		break;
 	case READ_STR_VAR:
 		if (index >= STROBE_MAX_STRS)
 			return 1;
-		ctx->payload += read_str_var(ctx->cfg, index, ctx->tls_base,
-					     ctx->value, ctx->data, ctx->payload);
+		if (ctx->payload_off > sizeof(ctx->data->payload) - STROBE_MAX_STR_LEN)
+			return 1;
+		ctx->payload_off = read_str_var(ctx->cfg, index, ctx->tls_base,
+						ctx->value, ctx->data, ctx->payload_off);
 		break;
 	}
 	return 0;

@@ -501,7 +513,8 @@ static void *read_strobe_meta(struct task_struct *task,
 	pid_t pid = bpf_get_current_pid_tgid() >> 32;
 	struct strobe_value_generic value = {0};
 	struct strobemeta_cfg *cfg;
-	void *tls_base, *payload;
+	size_t payload_off;
+	void *tls_base;
 
 	cfg = bpf_map_lookup_elem(&strobemeta_cfgs, &pid);
 	if (!cfg)

@@ -509,7 +522,7 @@ static void *read_strobe_meta(struct task_struct *task,
 
 	data->int_vals_set_mask = 0;
 	data->req_meta_valid = 0;
-	payload = data->payload;
+	payload_off = 0;
 	/*
 	 * we don't have struct task_struct definition, it should be:
 	 * tls_base = (void *)task->thread.fsbase;

@@ -522,7 +535,7 @@ static void *read_strobe_meta(struct task_struct *task,
 		.tls_base = tls_base,
 		.value = &value,
 		.data = data,
-		.payload = payload,
+		.payload_off = 0,
 	};
 	int err;
 

@@ -540,6 +553,11 @@ static void *read_strobe_meta(struct task_struct *task,
 	err = bpf_loop(STROBE_MAX_MAPS, read_var_callback, &ctx, 0);
 	if (err != STROBE_MAX_MAPS)
 		return NULL;
+
+	payload_off = ctx.payload_off;
+	/* this should not really happen, here only to satisfy verifer */
+	if (payload_off > sizeof(data->payload))
+		payload_off = sizeof(data->payload);
 #else
 #ifdef NO_UNROLL
 #pragma clang loop unroll(disable)

@@ -555,7 +573,7 @@ static void *read_strobe_meta(struct task_struct *task,
 #pragma unroll
 #endif /* NO_UNROLL */
 	for (int i = 0; i < STROBE_MAX_STRS; ++i) {
-		payload += read_str_var(cfg, i, tls_base, &value, data, payload);
+		payload_off = read_str_var(cfg, i, tls_base, &value, data, payload_off);
 	}
 #ifdef NO_UNROLL
 #pragma clang loop unroll(disable)

@@ -563,7 +581,7 @@ static void *read_strobe_meta(struct task_struct *task,
 #pragma unroll
 #endif /* NO_UNROLL */
 	for (int i = 0; i < STROBE_MAX_MAPS; ++i) {
-		payload = read_map_var(cfg, i, tls_base, &value, data, payload);
+		payload_off = read_map_var(cfg, i, tls_base, &value, data, payload_off);
 	}
 #endif /* USE_BPF_LOOP */
 

@@ -571,7 +589,7 @@ static void *read_strobe_meta(struct task_struct *task,
 	 * return pointer right after end of payload, so it's possible to
 	 * calculate exact amount of useful data that needs to be sent
 	 */
-	return payload;
+	return &data->payload[payload_off];
 }
 
 SEC("raw_tracepoint/kfree_skb")
Signature · 1 line
2.42.1
author maintainer
#3 lore raw

PATCH v2 3/11 selftests/bpf: fix bpf_loop_bench for new callback verification scheme

In reply to Eduard Zingerman

This is a preparatory change. A follow-up patch "bpf: verify callbacks as if they are called unknown number of times" changes logic for callbacks handling. While previously callbacks were verified as a single function call, new scheme takes into account that callbacks could be executed unknown number of times.

This has dire implications for bpf_loop_bench:

    SEC("fentry/" SYS_PREFIX "sys_getpgid")
    int benchmark(void *ctx)
    {
            for (int i = 0; i < 1000; i++) {
                    bpf_loop(nr_loops, empty_callback, NULL, 0);
                    __sync_add_and_fetch(&hits, nr_loops);
            }
            return 0;
    }

W/o callbacks change verifier sees it as a 1000 calls to empty_callback(). However, with callbacks change things become exponential:
- i=0: state exploring empty_callback is scheduled with i=0 (a);
- i=1: state exploring empty_callback is scheduled with i=1;
...
- i=999: state exploring empty_callback is scheduled with i=999;
- state (a) is popped from stack;
- i=1: state exploring empty_callback is scheduled with i=1;
...

Avoid this issue by rewriting outer loop as bpf_loop(). Unfortunately, this adds a function call to a loop at runtime, which negatively affects performance:

throughput latency
before: 149.919 ± 0.168 M ops/s, 6.670 ns/op
after : 137.040 ± 0.187 M ops/s, 7.297 ns/op

Acked-by Andrii Nakryiko <[email protected]>
Signed-off-by Eduard Zingerman <[email protected]>
---
 tools/testing/selftests/bpf/progs/bpf_loop_bench.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/progs/bpf_loop_bench.c +8 -5
index 4ce76eb064c4..d461746fd3c1 100644
@@ -15,13 +15,16 @@ static int empty_callback(__u32 index, void *data)
 	return 0;
 }
 
+static int outer_loop(__u32 index, void *data)
+{
+	bpf_loop(nr_loops, empty_callback, NULL, 0);
+	__sync_add_and_fetch(&hits, nr_loops);
+	return 0;
+}
+
 SEC("fentry/" SYS_PREFIX "sys_getpgid")
 int benchmark(void *ctx)
 {
-	for (int i = 0; i < 1000; i++) {
-		bpf_loop(nr_loops, empty_callback, NULL, 0);
-
-		__sync_add_and_fetch(&hits, nr_loops);
-	}
+	bpf_loop(1000, outer_loop, NULL, 0);
 	return 0;
 }
Signature · 1 line
2.42.1
author maintainer
#4 lore raw

PATCH v2 4/11 bpf: extract __check_reg_arg() utility function

In reply to Eduard Zingerman

Split check_reg_arg() into two utility functions:
- check_reg_arg() operating on registers from current verifier state;
- __check_reg_arg() operating on a specific set of registers passed as a parameter;

The __check_reg_arg() function would be used by a follow-up change for callbacks handling.

Acked-by Andrii Nakryiko <[email protected]>
Signed-off-by Eduard Zingerman <[email protected]>
---
 kernel/bpf/verifier.c | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)
kernel/bpf/verifier.c +13 -6
index 7c3461b89513..ca54f738cfae 100644
@@ -3586,13 +3586,11 @@ static void mark_insn_zext(struct bpf_verifier_env *env,
 	reg->subreg_def = DEF_NOT_SUBREG;
 }
 
-static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
-			 enum reg_arg_type t)
+static int __check_reg_arg(struct bpf_verifier_env *env, struct bpf_reg_state *regs, u32 regno,
+			   enum reg_arg_type t)
 {
-	struct bpf_verifier_state *vstate = env->cur_state;
-	struct bpf_func_state *state = vstate->frame[vstate->curframe];
 	struct bpf_insn *insn = env->prog->insnsi + env->insn_idx;
-	struct bpf_reg_state *reg, *regs = state->regs;
+	struct bpf_reg_state *reg;
 	bool rw64;
 
 	if (regno >= MAX_BPF_REG) {

@@ -3633,6 +3631,15 @@ static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
 	return 0;
 }
 
+static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
+			 enum reg_arg_type t)
+{
+	struct bpf_verifier_state *vstate = env->cur_state;
+	struct bpf_func_state *state = vstate->frame[vstate->curframe];
+
+	return __check_reg_arg(env, state->regs, regno, t);
+}
+
 static void mark_jmp_point(struct bpf_verifier_env *env, int idx)
 {
 	env->insn_aux_data[idx].jmp_point = true;

@@ -9528,7 +9535,7 @@ static void clear_caller_saved_regs(struct bpf_verifier_env *env,
 	/* after the call registers r0 - r5 were scratched */
 	for (i = 0; i < CALLER_SAVED_REGS; i++) {
 		mark_reg_not_init(env, regs, caller_saved[i]);
-		check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
+		__check_reg_arg(env, regs, caller_saved[i], DST_OP_NO_MARK);
 	}
 }
Signature · 1 line
2.42.1
author maintainer
#5 lore raw

PATCH v2 5/11 bpf: extract setup_func_entry() utility function

In reply to Eduard Zingerman

Move code for simulated stack frame creation to a separate utility function. This function would be used in the follow-up change for callbacks handling.

Acked-by Andrii Nakryiko <[email protected]>
Signed-off-by Eduard Zingerman <[email protected]>
---
 kernel/bpf/verifier.c | 84 ++++++++++++++++++++++++-------------------
 1 file changed, 48 insertions(+), 36 deletions(-)
kernel/bpf/verifier.c +48 -36
index ca54f738cfae..0b695014da3b 100644
@@ -9548,11 +9548,10 @@ static int set_callee_state(struct bpf_verifier_env *env,
 			    struct bpf_func_state *caller,
 			    struct bpf_func_state *callee, int insn_idx);
 
-static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
-			     int *insn_idx, int subprog,
-			     set_callee_state_fn set_callee_state_cb)
+static int setup_func_entry(struct bpf_verifier_env *env, int subprog, int callsite,
+			    set_callee_state_fn set_callee_state_cb,
+			    struct bpf_verifier_state *state)
 {
-	struct bpf_verifier_state *state = env->cur_state;
 	struct bpf_func_state *caller, *callee;
 	int err;
 

@@ -9562,13 +9561,53 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		return -E2BIG;
 	}
 
-	caller = state->frame[state->curframe];
 	if (state->frame[state->curframe + 1]) {
 		verbose(env, "verifier bug. Frame %d already allocated\n",
 			state->curframe + 1);
 		return -EFAULT;
 	}
 
+	caller = state->frame[state->curframe];
+	callee = kzalloc(sizeof(*callee), GFP_KERNEL);
+	if (!callee)
+		return -ENOMEM;
+	state->frame[state->curframe + 1] = callee;
+
+	/* callee cannot access r0, r6 - r9 for reading and has to write
+	 * into its own stack before reading from it.
+	 * callee can read/write into caller's stack
+	 */
+	init_func_state(env, callee,
+			/* remember the callsite, it will be used by bpf_exit */
+			callsite,
+			state->curframe + 1 /* frameno within this callchain */,
+			subprog /* subprog number within this prog */);
+	/* Transfer references to the callee */
+	err = copy_reference_state(callee, caller);
+	err = err ?: set_callee_state_cb(env, caller, callee, callsite);
+	if (err)
+		goto err_out;
+
+	/* only increment it after check_reg_arg() finished */
+	state->curframe++;
+
+	return 0;
+
+err_out:
+	free_func_state(callee);
+	state->frame[state->curframe + 1] = NULL;
+	return err;
+}
+
+static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			     int *insn_idx, int subprog,
+			     set_callee_state_fn set_callee_state_cb)
+{
+	struct bpf_verifier_state *state = env->cur_state;
+	struct bpf_func_state *caller, *callee;
+	int err;
+
+	caller = state->frame[state->curframe];
 	err = btf_check_subprog_call(env, subprog, caller->regs);
 	if (err == -EFAULT)
 		return err;

@@ -9638,35 +9677,12 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		return 0;
 	}
 
-	callee = kzalloc(sizeof(*callee), GFP_KERNEL);
-	if (!callee)
-		return -ENOMEM;
-	state->frame[state->curframe + 1] = callee;
-
-	/* callee cannot access r0, r6 - r9 for reading and has to write
-	 * into its own stack before reading from it.
-	 * callee can read/write into caller's stack
-	 */
-	init_func_state(env, callee,
-			/* remember the callsite, it will be used by bpf_exit */
-			*insn_idx /* callsite */,
-			state->curframe + 1 /* frameno within this callchain */,
-			subprog /* subprog number within this prog */);
-
-	/* Transfer references to the callee */
-	err = copy_reference_state(callee, caller);
+	err = setup_func_entry(env, subprog, *insn_idx, set_callee_state_cb, state);
 	if (err)
-		goto err_out;
-
-	err = set_callee_state_cb(env, caller, callee, *insn_idx);
-	if (err)
-		goto err_out;
+		return err;
 
 	clear_caller_saved_regs(env, caller->regs);
 
-	/* only increment it after check_reg_arg() finished */
-	state->curframe++;
-
 	/* and go analyze first insn of the callee */
 	*insn_idx = env->subprog_info[subprog].start - 1;
 

@@ -9674,14 +9690,10 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		verbose(env, "caller:\n");
 		print_verifier_state(env, caller, true);
 		verbose(env, "callee:\n");
-		print_verifier_state(env, callee, true);
+		print_verifier_state(env, state->frame[state->curframe], true);
 	}
-	return 0;
 
-err_out:
-	free_func_state(callee);
-	state->frame[state->curframe + 1] = NULL;
-	return err;
+	return 0;
 }
 
 int map_set_for_each_callback_args(struct bpf_verifier_env *env,
Signature · 1 line
2.42.1
author maintainer
#6 lore raw

PATCH v2 6/11 bpf: verify callbacks as if they are called unknown number of times

In reply to Eduard Zingerman

Prior to this patch callbacks were handled as regular function calls, execution of callback body was modeled exactly once.
This patch updates callbacks handling logic as follows:
- introduces a function push_callback_call() that schedules callback body verification in env->head stack;
- updates prepare_func_exit() to reschedule callback body verification upon BPF_EXIT;
- as calls to bpf_*_iter_next(), calls to callback invoking functions are marked as checkpoints;
- is_state_visited() is updated to stop callback based iteration when some identical parent state is found.

Paths with callback function invoked zero times are now verified first, which leads to necessity to modify some selftests:
- the following negative tests required adding release/unlock/drop calls to avoid previously masked unrelated error reports:
- cb_refs.c:underflow_prog
- exceptions_fail.c:reject_rbtree_add_throw
- exceptions_fail.c:reject_with_cp_reference
- the following precision tracking selftests needed change in expected log trace:
- verifier_subprog_precision.c:callback_result_precise
(note: r0 precision is no longer propagated inside callback and
I think this is a correct behavior)
- verifier_subprog_precision.c:parent_callee_saved_reg_precise_with_callback
- verifier_subprog_precision.c:parent_stack_slot_precise_with_callback

Reported-by Andrew Werner <[email protected]>
Closes https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@mail.gmail.com/ open here
Signed-off-by Eduard Zingerman <[email protected]>
---
 include/linux/bpf_verifier.h                  |   5 +
 kernel/bpf/verifier.c                         | 269 +++++++++++-------
 tools/testing/selftests/bpf/progs/cb_refs.c   |   1 +
 .../selftests/bpf/progs/exceptions_fail.c     |   2 +
 .../bpf/progs/verifier_subprog_precision.c    |  65 ++++-
 5 files changed, 229 insertions(+), 113 deletions(-)
include/linux/bpf_verifier.h +5 -0
index 52a4012b8255..7def320aceef 100644
@@ -400,6 +400,7 @@ struct bpf_verifier_state {
 	struct bpf_idx_pair *jmp_history;
 	u32 jmp_history_cnt;
 	u32 dfs_depth;
+	u32 callback_iter_depth;
 };
 
 #define bpf_get_spilled_reg(slot, frame, mask)				\

@@ -511,6 +512,10 @@ struct bpf_insn_aux_data {
 	 * this instruction, regardless of any heuristics
 	 */
 	bool force_checkpoint;
+	/* true if instruction is a call to a helper function that
+	 * accepts callback function as a parameter.
+	 */
+	bool callback_iter;
 };
 
 #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */
kernel/bpf/verifier.c +170 -99

429 lines not on this page · raw message

tools/testing/selftests/bpf/progs/cb_refs.c +1 -0
index 76d661b20e87..56c764df8196 100644
@@ -33,6 +33,7 @@ int underflow_prog(void *ctx)
 	if (!p)
 		return 0;
 	bpf_for_each_map_elem(&array_map, cb1, &p, 0);
+	bpf_kfunc_call_test_release(p);
 	return 0;
 }
tools/testing/selftests/bpf/progs/exceptions_fail.c +2 -0
index 4c39e920dac2..8c0ef2742208 100644
@@ -171,6 +171,7 @@ int reject_with_rbtree_add_throw(void *ctx)
 		return 0;
 	bpf_spin_lock(&lock);
 	bpf_rbtree_add(&rbtree, &f->node, rbless);
+	bpf_spin_unlock(&lock);
 	return 0;
 }
 

@@ -214,6 +215,7 @@ int reject_with_cb_reference(void *ctx)
 	if (!f)
 		return 0;
 	bpf_loop(5, subprog_cb_ref, NULL, 0);
+	bpf_obj_drop(f);
 	return 0;
 }
tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +51 -14

108 lines not on this page · raw message

Signature · 1 line
2.42.1
#7 lore raw

Re: [PATCH bpf v2 06/11] bpf: verify callbacks as if they are called unknown number of times

Quoted 3 lines · Eduard Zingerman

- as calls to bpf_*_iter_next(), calls to callback invoking functions are marked as checkpoints;

...

kernel/bpf/verifier.c static bool is_force_checkpoint(struct bpf_verifier_env *env, int insn_idx) · line 15577

Quoted 9 lines
kernel/bpf/verifier.c +9 -0
+static void mark_callback_iter_next(struct bpf_verifier_env *env, int idx)
+{
+       env->insn_aux_data[idx].callback_iter = true;
+}
+
+static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx)
+{
+       return env->insn_aux_data[insn_idx].callback_iter;
+}

I think you're trying to make it similar to is_iter_next_kfunc(), but in this context the _iter_next is confusing. Especially _next suffix. Maybe
s/bool callback_iter/bool calls_callback/ ? s/is_callback_iter_next/calls_callback/ ? s/mark_callback_iter_next/mark_calls_callback/ ?

callback_iter_depth isn't quite accurate either.
Maybe callback_nest_level ?

author maintainer
#8 lore raw

Re: [PATCH bpf v2 06/11] bpf: verify callbacks as if they are called unknown number of times

On Sun, 2023-11-19 at 17:41 -0800, Alexei Starovoitov wrote:
[...]

Quoted 9 lines

I think you're trying to make it similar to is_iter_next_kfunc(), but in this context the _iter_next is confusing. Especially _next suffix. Maybe
s/bool callback_iter/bool calls_callback/ ? s/is_callback_iter_next/calls_callback/ ? s/mark_callback_iter_next/mark_calls_callback/ ?

callback_iter_depth isn't quite accurate either.
Maybe callback_nest_level ?

Makes sense, will update naming scheme.

author maintainer
#9 lore raw

PATCH v2 7/11 selftests/bpf: tests for iterating callbacks

In reply to Eduard Zingerman

A set of test cases to check behavior of callback handling logic, check if verifier catches the following situations:
- program not safe on second callback iteration;
- program not safe on zero callback iterations;
- infinite loop inside a callback.

Verify that callback logic works for bpf_loop, bpf_for_each_map_elem, bpf_user_ringbuf_drain, bpf_find_vma.

Acked-by Andrii Nakryiko <[email protected]>
Signed-off-by Eduard Zingerman <[email protected]>
---
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../bpf/progs/verifier_iterating_callbacks.c  | 147 ++++++++++++++++++
 2 files changed, 149 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index e5c61aa6604a..5cfa7a6316b6 100644
@@ -31,6 +31,7 @@
 #include "verifier_helper_restricted.skel.h"
 #include "verifier_helper_value_access.skel.h"
 #include "verifier_int_ptr.skel.h"
+#include "verifier_iterating_callbacks.skel.h"
 #include "verifier_jeq_infer_not_null.skel.h"
 #include "verifier_ld_ind.skel.h"
 #include "verifier_ldsx.skel.h"

@@ -139,6 +140,7 @@ void test_verifier_helper_packet_access(void) { RUN(verifier_helper_packet_acces
 void test_verifier_helper_restricted(void)    { RUN(verifier_helper_restricted); }
 void test_verifier_helper_value_access(void)  { RUN(verifier_helper_value_access); }
 void test_verifier_int_ptr(void)              { RUN(verifier_int_ptr); }
+void test_verifier_iterating_callbacks(void)  { RUN(verifier_iterating_callbacks); }
 void test_verifier_jeq_infer_not_null(void)   { RUN(verifier_jeq_infer_not_null); }
 void test_verifier_ld_ind(void)               { RUN(verifier_ld_ind); }
 void test_verifier_ldsx(void)                  { RUN(verifier_ldsx); }
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c new file +147 -0

147 lines not on this page · raw message

Signature · 1 line
2.42.1
author maintainer
#10 lore raw

PATCH v2 8/11 bpf: widening for callback iterators

In reply to Eduard Zingerman

Callbacks are similar to open coded iterators, so add imprecise widening logic for callback body processing. This makes callback based loops behave identically to open coded iterators, e.g. allowing to verify programs like below:

  struct ctx { u32 i; };
  int cb(u32 idx, struct ctx* ctx)
  {
          ++ctx->i;
          return 0;
  }
  ...
  struct ctx ctx = { .i = 0 };
  bpf_loop(100, cb, &ctx, 0);
  ...
Acked-by Andrii Nakryiko <[email protected]>
Signed-off-by Eduard Zingerman <[email protected]>
---
 kernel/bpf/verifier.c | 24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +22 -2
index 35e137c5f29a..b9e3067890b7 100644
@@ -9977,9 +9977,10 @@ static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
 
 static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 {
-	struct bpf_verifier_state *state = env->cur_state;
+	struct bpf_verifier_state *state = env->cur_state, *prev_st;
 	struct bpf_func_state *caller, *callee;
 	struct bpf_reg_state *r0;
+	bool callback_iter;
 	int err;
 
 	callee = state->frame[state->curframe];

@@ -10029,7 +10030,8 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 	 * there function call logic would reschedule callback visit. If iteration
 	 * converges is_state_visited() would prune that visit eventually.
 	 */
-	if (callee->in_callback_fn && is_callback_iter_next(env, callee->callsite))
+	callback_iter = callee->in_callback_fn && is_callback_iter_next(env, callee->callsite);
+	if (callback_iter)
 		*insn_idx = callee->callsite;
 	else
 		*insn_idx = callee->callsite + 1;

@@ -10044,6 +10046,24 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 	 * bpf_throw, this will be done by copy_verifier_state for extra frames. */
 	free_func_state(callee);
 	state->frame[state->curframe--] = NULL;
+
+	/* for callbacks widen imprecise scalars to make programs like below verify:
+	 *
+	 *   struct ctx { int i; }
+	 *   void cb(int idx, struct ctx *ctx) { ctx->i++; ... }
+	 *   ...
+	 *   struct ctx = { .i = 0; }
+	 *   bpf_loop(100, cb, &ctx, 0);
+	 *
+	 * This is similar to what is done in process_iter_next_call() for open
+	 * coded iterators.
+	 */
+	prev_st = callback_iter ? find_prev_entry(env, state, *insn_idx) : NULL;
+	if (prev_st) {
+		err = widen_imprecise_scalars(env, prev_st, state);
+		if (err)
+			return err;
+	}
 	return 0;
 }
Signature · 1 line
2.42.1
author maintainer
#11 lore raw

PATCH v2 9/11 selftests/bpf: test widening for iterating callbacks

In reply to Eduard Zingerman

A test case to verify that imprecise scalars widening is applied to callback entering state, when callback call is simulated repeatedly.

Signed-off-by Eduard Zingerman <[email protected]>
---
 .../bpf/progs/verifier_iterating_callbacks.c  | 20 +++++++++++++++++++
 1 file changed, 20 insertions(+)
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +20 -0
index fa9429f77a81..598c1e984b26 100644
@@ -25,6 +25,7 @@ struct buf_context {
 
 struct num_context {
 	__u64 i;
+	__u64 j;
 };
 
 __u8 choice_arr[2] = { 0, 1 };

@@ -69,6 +70,25 @@ int unsafe_on_zero_iter(void *unused)
 	return choice_arr[loop_ctx.i];
 }
 
+static int widening_cb(__u32 idx, struct num_context *ctx)
+{
+	++ctx->i;
+	return 0;
+}
+
+SEC("?raw_tp")
+__success
+int widening(void *unused)
+{
+	struct num_context loop_ctx = { .i = 0, .j = 1 };
+
+	bpf_loop(100, widening_cb, &loop_ctx, 0);
+	/* loop_ctx.j is not changed during callback iteration,
+	 * verifier should not apply widening to it.
+	 */
+	return choice_arr[loop_ctx.j];
+}
+
 static int loop_detection_cb(__u32 idx, struct num_context *ctx)
 {
 	for (;;) {}
Signature · 1 line
2.42.1
author maintainer
#12 lore raw

PATCH v2 10/11 bpf: keep track of max number of bpf_loop callback iterations

In reply to Eduard Zingerman

In some cases verifier can't infer convergence of the bpf_loop() iteration. E.g. for the following program:

    static int cb(__u32 idx, struct num_context* ctx)
    {
        ctx->i++;
        return 0;
    }

    SEC("?raw_tp")
    int prog(void *_)
    {
        struct num_context ctx = { .i = 0 };
        __u8 choice_arr[2] = { 0, 1 };

        bpf_loop(2, cb, &ctx, 0);
        return choice_arr[ctx.i];
    }

Each 'cb' simulation would eventually return to 'prog' and reach 'return choice_arr[ctx.i]' statement. At which point ctx.i would be marked precise, thus forcing verifier to track multitude of separate states with {.i=0}, {.i=1}, ... at bpf_loop() callback entry.

This commit allows "brute force" handling for such cases by limiting number of callback body simulations using 'umax' value of the first bpf_loop() parameter.

For this, extend bpf_func_state with 'callback_depth' field. Increment this field when callback visiting state is pushed to states traversal stack. For frame #N it's 'callback_depth' field counts how many times callback with frame depth N+1 had been executed. Use bpf_func_state specifically to allow independent tracking of callback depths when multiple nested bpf_loop() calls are present.

Signed-off-by Eduard Zingerman <[email protected]>
---
 include/linux/bpf_verifier.h                  |  9 ++++++
 kernel/bpf/verifier.c                         | 17 +++++++++--
 .../bpf/progs/verifier_subprog_precision.c    | 29 ++++++++++++++-----
 3 files changed, 46 insertions(+), 9 deletions(-)
include/linux/bpf_verifier.h +9 -0
index 7def320aceef..71b7c7c39cea 100644
@@ -301,6 +301,15 @@ struct bpf_func_state {
 	struct tnum callback_ret_range;
 	bool in_async_callback_fn;
 	bool in_exception_callback_fn;
+	/* For callback calling functions that limit number of possible
+	 * callback executions (e.g. bpf_loop) keeps track of current
+	 * simulated iteration number. When non-zero either:
+	 * - current frame has a child frame, in such case it's callsite points
+	 *   to callback calling function;
+	 * - current frame is a topmost frame, in such case callback has just
+	 *   returned and env->insn_idx points to callback calling function.
+	 */
+	u32 callback_depth;
 
 	/* The following fields should be last. See copy_func_state() */
 	int acquired_refs;
kernel/bpf/verifier.c +15 -2
index b9e3067890b7..843d1d3be63e 100644
@@ -9683,6 +9683,8 @@ static int push_callback_call(struct bpf_verifier_env *env, struct bpf_insn *ins
 		return err;
 
 	callback_state->callback_iter_depth++;
+	callback_state->frame[callback_state->curframe - 1]->callback_depth++;
+	caller->callback_depth = 0;
 	return 0;
 }
 

@@ -10485,8 +10487,19 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		break;
 	case BPF_FUNC_loop:
 		update_loop_inline_state(env, meta.subprogno);
-		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
-					 set_loop_callback_state);
+		/* Verifier relies on R1 value to determine if bpf_loop() iteration
+		 * is finished, thus mark it precise.
+		 */
+		mark_chain_precision(env, BPF_REG_1);
+		if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value) {
+			err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+						 set_loop_callback_state);
+		} else {
+			cur_func(env)->callback_depth = 0;
+			if (env->log.level & BPF_LOG_LEVEL2)
+				verbose(env, "frame%d bpf_loop iteration limit reached\n",
+					env->cur_state->curframe);
+		}
 		break;
 	case BPF_FUNC_dynptr_from_mem:
 		if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +22 -7
index ec4cd596b8c6..e753fb52dcdd 100644
@@ -119,7 +119,23 @@ __naked int global_subprog_result_precise(void)
 
 SEC("?raw_tp")
 __success __log_level(2)
-/* First simulated path does not include callback body */
+/* First simulated path does not include callback body,
+ * r1 and r4 are always precise for bpf_loop() calls.
+ */
+__msg("9: (85) call bpf_loop#181")
+__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
+__msg("mark_precise: frame0: parent state regs=r4 stack=:")
+__msg("mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx 9")
+__msg("mark_precise: frame0: regs=r4 stack= before 8: (b7) r4 = 0")
+__msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
+__msg("mark_precise: frame0: parent state regs=r1 stack=:")
+__msg("mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx 9")
+__msg("mark_precise: frame0: regs=r1 stack= before 8: (b7) r4 = 0")
+__msg("mark_precise: frame0: regs=r1 stack= before 7: (b7) r3 = 0")
+__msg("mark_precise: frame0: regs=r1 stack= before 6: (bf) r2 = r8")
+__msg("mark_precise: frame0: regs=r1 stack= before 5: (bf) r1 = r6")
+__msg("mark_precise: frame0: regs=r6 stack= before 4: (b7) r6 = 3")
+/* r6 precision propagation */
 __msg("14: (0f) r1 += r6")
 __msg("mark_precise: frame0: last_idx 14 first_idx 9")
 __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")

@@ -134,8 +150,7 @@ __msg("17: (b7) r0 = 0")
 __msg("18: (95) exit")
 __msg("returning from callee:")
 __msg("to caller at 9:")
-/* r4 (flags) is always precise for bpf_loop() */
-__msg("frame 0: propagating r4")
+__msg("frame 0: propagating r1,r4")
 __msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
 __msg("mark_precise: frame0: parent state regs= stack=:")
 __msg("from 18 to 9: safe")

@@ -264,10 +279,10 @@ __msg("15: (b7) r0 = 0")
 __msg("16: (95) exit")
 __msg("returning from callee:")
 __msg("to caller at 9:")
-/* r4 (flags) is always precise for bpf_loop(),
+/* r1, r4 are always precise for bpf_loop(),
  * r6 was marked before backtracking to callback body.
  */
-__msg("frame 0: propagating r4,r6")
+__msg("frame 0: propagating r1,r4,r6")
 __msg("mark_precise: frame0: last_idx 9 first_idx 9 subseq_idx -1")
 __msg("mark_precise: frame0: parent state regs= stack=:")
 __msg("from 16 to 9: safe")

@@ -419,10 +434,10 @@ __msg("17: (b7) r0 = 0")
 __msg("18: (95) exit")
 __msg("returning from callee:")
 __msg("to caller at 10:")
-/* r4 (flags) is always precise for bpf_loop(),
+/* r1, r4 are always precise for bpf_loop(),
  * fp-8 was marked before backtracking to callback body.
  */
-__msg("frame 0: propagating r4,fp-8")
+__msg("frame 0: propagating r1,r4,fp-8")
 __msg("mark_precise: frame0: last_idx 10 first_idx 10 subseq_idx -1")
 __msg("mark_precise: frame0: parent state regs= stack=:")
 __msg("from 18 to 10: safe")
Signature · 1 line
2.42.1
#13 lore raw

Re: [PATCH bpf v2 10/11] bpf: keep track of max number of bpf_loop callback iterations

Quoted 8 lines · Eduard Zingerman
include/linux/bpf_verifier.h +0 -0
index 7def320aceef..71b7c7c39cea 100644
@@ -301,6 +301,15 @@ struct bpf_func_state {
        struct tnum callback_ret_range;
        bool in_async_callback_fn;

include/linux/bpf_verifier.h struct bpf_func_state { · line 312

Quoted 10 lines
include/linux/bpf_verifier.h +9 -0
        bool in_exception_callback_fn;
+       /* For callback calling functions that limit number of possible
+        * callback executions (e.g. bpf_loop) keeps track of current
+        * simulated iteration number. When non-zero either:
+        * - current frame has a child frame, in such case it's callsite points
+        *   to callback calling function;
+        * - current frame is a topmost frame, in such case callback has just
+        *   returned and env->insn_idx points to callback calling function.
+        */
+       u32 callback_depth;

The first part of the comment makes sense, but the second... What are you trying to explain with the second part ? How does the knowledge of insn_idx help here ? or helps to understand the rest of the patch?

author maintainer
#14 lore raw

Re: [PATCH bpf v2 10/11] bpf: keep track of max number of bpf_loop callback iterations

Quoted 16 lines · Alexei Starovoitov
Quoted 15 lines · Eduard Zingerman
include/linux/bpf_verifier.h +6 -0
index 7def320aceef..71b7c7c39cea 100644
@@ -301,6 +301,15 @@ struct bpf_func_state {
        struct tnum callback_ret_range;
        bool in_async_callback_fn;
        bool in_exception_callback_fn;
+       /* For callback calling functions that limit number of possible
+        * callback executions (e.g. bpf_loop) keeps track of current
+        * simulated iteration number. When non-zero either:
+        * - current frame has a child frame, in such case it's callsite points
+        *   to callback calling function;
+        * - current frame is a topmost frame, in such case callback has just
Quoted 8 lines

include/linux/bpf_verifier.h struct bpf_func_state { · line 312

Quoted 3 lines
include/linux/bpf_verifier.h +3 -0
+        *   returned and env->insn_idx points to callback calling function.
+        */
+       u32 callback_depth;

The first part of the comment makes sense, but the second... What are you trying to explain with the second part ? How does the knowledge of insn_idx help here ? or helps to understand the rest of the patch?

The intent was to explain that 'callback_depth' in frame N refers to number of times callback with frame N+1 was simulated, e.g.:

  bpf_loop(..., fn, ...); | suppose current frame is N
                          | fn would be simulated in frame N+1
                          | number of simulations is tracked in frame N
#15 lore raw

Re: [PATCH bpf v2 10/11] bpf: keep track of max number of bpf_loop callback iterations

Quoted 27 lines · Eduard Zingerman
Quoted 16 lines · Alexei Starovoitov
Quoted 15 lines · Eduard Zingerman
include/linux/bpf_verifier.h +6 -0
index 7def320aceef..71b7c7c39cea 100644
@@ -301,6 +301,15 @@ struct bpf_func_state {
        struct tnum callback_ret_range;
        bool in_async_callback_fn;
        bool in_exception_callback_fn;
+       /* For callback calling functions that limit number of possible
+        * callback executions (e.g. bpf_loop) keeps track of current
+        * simulated iteration number. When non-zero either:
+        * - current frame has a child frame, in such case it's callsite points
+        *   to callback calling function;
+        * - current frame is a topmost frame, in such case callback has just
Quoted 8 lines

include/linux/bpf_verifier.h struct bpf_func_state { · line 312

Quoted 3 lines
include/linux/bpf_verifier.h +3 -0
+        *   returned and env->insn_idx points to callback calling function.
+        */
+       u32 callback_depth;

The first part of the comment makes sense, but the second... What are you trying to explain with the second part ? How does the knowledge of insn_idx help here ? or helps to understand the rest of the patch?

Quoted 6 lines

The intent was to explain that 'callback_depth' in frame N refers to number of times callback with frame N+1 was simulated, e.g.:

  bpf_loop(..., fn, ...); | suppose current frame is N
                          | fn would be simulated in frame N+1
                          | number of simulations is tracked in frame N

I see. Pls use this instead. Much clearer :)

author maintainer
#16 lore raw

PATCH v2 11/11 selftests/bpf: check if max number of bpf_loop iterations is tracked

In reply to Eduard Zingerman

Check that even if bpf_loop() callback simulation does not converge to a specific state, verification could proceed via "brute force" simulation of maximal number of callback calls.

Signed-off-by Eduard Zingerman <[email protected]>
---
 .../bpf/progs/verifier_iterating_callbacks.c  | 83 +++++++++++++++++++
 1 file changed, 83 insertions(+)
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +83 -0
index 598c1e984b26..fe0ce06de55f 100644
@@ -164,4 +164,87 @@ int unsafe_find_vma(void *unused)
 	return choice_arr[loop_ctx.i];
 }
 
+static int iter_limit_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i++;
+	return 0;
+}
+
+SEC("?raw_tp")
+__success
+int bpf_loop_iter_limit_ok(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(1, iter_limit_cb, &ctx, 0);
+	return choice_arr[ctx.i];
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=2 size=1")
+int bpf_loop_iter_limit_overflow(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(2, iter_limit_cb, &ctx, 0);
+	return choice_arr[ctx.i];
+}
+
+static int iter_limit_level2a_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 100;
+	return 0;
+}
+
+static int iter_limit_level2b_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 10;
+	return 0;
+}
+
+static int iter_limit_level1_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i += 1;
+	bpf_loop(1, iter_limit_level2a_cb, ctx, 0);
+	bpf_loop(1, iter_limit_level2b_cb, ctx, 0);
+	return 0;
+}
+
+SEC("?raw_tp")
+__success __log_level(2)
+/* Check that path visiting every callback function once had been
+ * reached by verifier. Variable 'i' below (stored as r2) serves
+ * as a flag, with each decimal digit corresponding to a callback
+ * visit marker.
+ */
+__msg("(73) *(u8 *)(r1 +0) = r2          ; R1_w=map_value(off=0,ks=4,vs=2,imm=0) R2_w=111111")
+int bpf_loop_iter_limit_nested(void *unused)
+{
+	struct num_context ctx1 = { .i = 0 };
+	struct num_context ctx2 = { .i = 0 };
+	/* Set registers for 'i' and 'p' to get guaranteed asm
+	 * instruction shape for __msg matching.
+	 */
+	register unsigned i asm("r2");
+	register __u8 *p asm("r1");
+	unsigned a, b;
+
+	bpf_loop(1, iter_limit_level1_cb, &ctx1, 0);
+	bpf_loop(1, iter_limit_level1_cb, &ctx2, 0);
+	a = ctx1.i;
+	b = ctx2.i;
+	i = a * 1000 + b;
+	/* Force 'ctx1.i' and 'ctx2.i' precise. */
+	p = &choice_arr[(a % 2 + b % 2) % 2];
+	/* Make sure that verifier does not visit 'impossible' states:
+	 * enumerate all possible callback visit masks.
+	 */
+	if (a != 0 && a != 1 && a != 11 && a != 101 && a != 111 &&
+	    b != 0 && b != 1 && b != 11 && b != 101 && b != 111)
+		asm volatile ("r0 /= 0;" ::: "r0");
+	/* Instruction for match in __msg spec. */
+	asm volatile ("*(u8 *)(r1 + 0) = r2;" :: "r"(p), "r"(i) : "memory");
+	return 0;
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.42.1
#17 lore raw

Re: [PATCH bpf v2 11/11] selftests/bpf: check if max number of bpf_loop iterations is tracked

Quoted 8 lines · Eduard Zingerman
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +8 -0
+
+SEC("?raw_tp")
+__success __log_level(2)
+/* Check that path visiting every callback function once had been
+ * reached by verifier. Variable 'i' below (stored as r2) serves
+ * as a flag, with each decimal digit corresponding to a callback
+ * visit marker.
+ */

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_find_vma(void *unused) · line 229

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +10 -0
+__msg("(73) *(u8 *)(r1 +0) = r2          ; R1_w=map_value(off=0,ks=4,vs=2,imm=0) R2_w=111111")
+int bpf_loop_iter_limit_nested(void *unused)
+{
+       struct num_context ctx1 = { .i = 0 };
+       struct num_context ctx2 = { .i = 0 };
+       /* Set registers for 'i' and 'p' to get guaranteed asm
+        * instruction shape for __msg matching.
+        */
+       register unsigned i asm("r2");
+       register __u8 *p asm("r1");

I suspect this is fragile.
The compiler will use r2 for 'i' if 'i' is actually there, but if it can optimize 'i' and 'p' away the r1 and r2 may be used for something else.
The "register" keyword is not mandatory. Unlike "volatile".

Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +7 -0
+       unsigned a, b;
+
+       bpf_loop(1, iter_limit_level1_cb, &ctx1, 0);
+       bpf_loop(1, iter_limit_level1_cb, &ctx2, 0);
+       a = ctx1.i;
+       b = ctx2.i;
+       i = a * 1000 + b;

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_find_vma(void *unused) · line 246

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +10 -0
+       /* Force 'ctx1.i' and 'ctx2.i' precise. */
+       p = &choice_arr[(a % 2 + b % 2) % 2];
+       /* Make sure that verifier does not visit 'impossible' states:
+        * enumerate all possible callback visit masks.
+        */
+       if (a != 0 && a != 1 && a != 11 && a != 101 && a != 111 &&
+           b != 0 && b != 1 && b != 11 && b != 101 && b != 111)
+               asm volatile ("r0 /= 0;" ::: "r0");
+       /* Instruction for match in __msg spec. */
+       asm volatile ("*(u8 *)(r1 + 0) = r2;" :: "r"(p), "r"(i) : "memory");

Feels even more fragile. Not sure what gcc will do.
Can 'i' be checked as run-time value ?
If it passes the verifier and after bpf_prog_run the 'i' is equal to expected value we're good, no?

author maintainer
#18 lore raw

Re: [PATCH bpf v2 11/11] selftests/bpf: check if max number of bpf_loop iterations is tracked

On Sun, 2023-11-19 at 18:09 -0800, Alexei Starovoitov wrote:
[...]

Quoted 8 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_find_vma(void *unused) · line 229

Quoted 2 lines
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +2 -0
+       register unsigned i asm("r2");
+       register __u8 *p asm("r1");

I suspect this is fragile.
The compiler will use r2 for 'i' if 'i' is actually there, but if it can optimize 'i' and 'p' away the r1 and r2 may be used for something else.
The "register" keyword is not mandatory. Unlike "volatile".

[...]

Quoted 10 lines

tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c int unsafe_find_vma(void *unused) · line 246

Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c +5 -0
+       if (a != 0 && a != 1 && a != 11 && a != 101 && a != 111 &&
+           b != 0 && b != 1 && b != 11 && b != 101 && b != 111)
+               asm volatile ("r0 /= 0;" ::: "r0");
+       /* Instruction for match in __msg spec. */
+       asm volatile ("*(u8 *)(r1 + 0) = r2;" :: "r"(p), "r"(i) : "memory");

Feels even more fragile. Not sure what gcc will do.
Can 'i' be checked as run-time value ?
If it passes the verifier and after bpf_prog_run the 'i' is equal to expected value we're good, no?

Runtime check should work, thank you for this suggestion. I'll remove unnecessary 'asm' blocks and use __retval instead ('r0 /= 0' will remain).