[PATCH bpf 00/12] verify callbacks as if they are called unknown number of times

[PATCH bpf 00/12] verify callbacks as if they are called unknown number of times

[Eduard Zingerman]

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 extends test_load based tests infra with __not_msg() macro;
- patch #12 adds test cases for #10 (and uses __not_msg() from #11).

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              136         219  +83 (+61.03%)
strobemeta_bpf_loop.bpf.o  on_event              113         152  +39 (+34.51%)
xdp_synproxy_kern.bpf.o    syncookie_tc          341         298  -43 (-12.61%)
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.

[0] https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@mail.gmail.com/
[1] https://lore.kernel.org/bpf/20231024000917.12153-1-eddyz87@gmail.com/
[2] git@github.com:cilium/tetragon.git

Eduard Zingerman (12):
  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: add __not_msg annotation for test_loader based tests
  selftests/bpf: check if max number of bpf_loop iterations is tracked

 include/linux/bpf_verifier.h                  |  14 +
 kernel/bpf/verifier.c                         | 381 ++++++++++++------
 .../selftests/bpf/prog_tests/cb_refs.c        |   4 +-
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/bpf_loop_bench.c      |  13 +-
 tools/testing/selftests/bpf/progs/bpf_misc.h  |   9 +
 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  | 234 +++++++++++
 .../bpf/progs/verifier_subprog_precision.c    |  22 +-
 .../selftests/bpf/progs/xdp_synproxy_kern.c   |  84 ++--
 tools/testing/selftests/bpf/test_loader.c     |  82 ++--
 13 files changed, 691 insertions(+), 235 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c

-- 
2.42.0

[PATCH bpf 01/12] selftests/bpf: track tcp payload offset as scalar in xdp_synproxy

[Eduard Zingerman]

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.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../selftests/bpf/progs/xdp_synproxy_kern.c   | 84 ++++++++++++-------
 1 file changed, 52 insertions(+), 32 deletions(-)

diff --git a/tools/testing/selftests/bpf/progs/xdp_synproxy_kern.c b/tools/testing/selftests/bpf/progs/xdp_synproxy_kern.c
index e959336c7a73..80f620602d50 100644
--- a/tools/testing/selftests/bpf/progs/xdp_synproxy_kern.c
+++ b/tools/testing/selftests/bpf/progs/xdp_synproxy_kern.c
@@ -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
-- 
2.42.0

[PATCH bpf 02/12] selftests/bpf: track string payload offset as scalar in strobemeta

[Eduard Zingerman]

This change prepares strobemeta for update in callbakcs verification
logic. To allow bpf_loop() verification converge when multiple
callback itreations 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.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../testing/selftests/bpf/progs/strobemeta.h  | 78 ++++++++++++-------
 1 file changed, 48 insertions(+), 30 deletions(-)

diff --git a/tools/testing/selftests/bpf/progs/strobemeta.h b/tools/testing/selftests/bpf/progs/strobemeta.h
index e02cfd380746..40df2cc26eaf 100644
--- a/tools/testing/selftests/bpf/progs/strobemeta.h
+++ b/tools/testing/selftests/bpf/progs/strobemeta.h
@@ -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")
-- 
2.42.0

[PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Eduard Zingerman]

The patch a few patches from this one 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 for verifier it merely represents 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

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/bpf_loop_bench.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

diff --git a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
index 4ce76eb064c4..d461746fd3c1 100644
--- a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
+++ b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
@@ -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;
 }
-- 
2.42.0

[PATCH bpf 04/12] bpf: extract __check_reg_arg() utility function

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

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9ae6eae13471..0576fc1ddc4d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3580,13 +3580,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) {
@@ -3627,6 +3625,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;
@@ -9522,7 +9529,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);
 	}
 }
 
-- 
2.42.0

[PATCH bpf 05/12] bpf: extract setup_func_entry() utility function

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

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 0576fc1ddc4d..d9513fd58c7c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9542,11 +9542,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;
 
@@ -9556,13 +9555,56 @@ 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);
+	if (err)
+		goto err_out;
+
+	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;
@@ -9632,35 +9674,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);
-	if (err)
-		goto err_out;
-
-	err = set_callee_state_cb(env, caller, callee, *insn_idx);
+	err = setup_func_entry(env, subprog, *insn_idx, set_callee_state_cb, state);
 	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;
 
@@ -9668,14 +9687,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,
-- 
2.42.0

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

[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 <awerner32@gmail.com>
Closes: https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@mail.gmail.com/
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h                  |   5 +
 kernel/bpf/verifier.c                         | 257 +++++++++++-------
 .../selftests/bpf/prog_tests/cb_refs.c        |   4 +-
 tools/testing/selftests/bpf/progs/cb_refs.c   |   1 +
 .../selftests/bpf/progs/exceptions_fail.c     |   2 +
 .../bpf/progs/verifier_subprog_precision.c    |  22 +-
 6 files changed, 183 insertions(+), 108 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 24213a99cc79..0ffb479c72d8 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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 */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d9513fd58c7c..270f7ca3c44d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -542,13 +542,12 @@ static bool is_dynptr_ref_function(enum bpf_func_id func_id)
 	return func_id == BPF_FUNC_dynptr_data;
 }
 
-static bool is_callback_calling_kfunc(u32 btf_id);
+static bool is_sync_callback_calling_kfunc(u32 btf_id);
 static bool is_bpf_throw_kfunc(struct bpf_insn *insn);
 
-static bool is_callback_calling_function(enum bpf_func_id func_id)
+static bool is_sync_callback_calling_function(enum bpf_func_id func_id)
 {
 	return func_id == BPF_FUNC_for_each_map_elem ||
-	       func_id == BPF_FUNC_timer_set_callback ||
 	       func_id == BPF_FUNC_find_vma ||
 	       func_id == BPF_FUNC_loop ||
 	       func_id == BPF_FUNC_user_ringbuf_drain;
@@ -559,6 +558,18 @@ static bool is_async_callback_calling_function(enum bpf_func_id func_id)
 	return func_id == BPF_FUNC_timer_set_callback;
 }
 
+static bool is_callback_calling_function(enum bpf_func_id func_id)
+{
+	return is_sync_callback_calling_function(func_id) ||
+	       is_async_callback_calling_function(func_id);
+}
+
+static bool is_sync_callback_calling_insn(struct bpf_insn *insn)
+{
+	return (bpf_helper_call(insn) && is_sync_callback_calling_function(insn->imm)) ||
+	       (bpf_pseudo_kfunc_call(insn) && is_sync_callback_calling_kfunc(insn->imm));
+}
+
 static bool is_storage_get_function(enum bpf_func_id func_id)
 {
 	return func_id == BPF_FUNC_sk_storage_get ||
@@ -1803,6 +1814,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
 	dst_state->first_insn_idx = src->first_insn_idx;
 	dst_state->last_insn_idx = src->last_insn_idx;
 	dst_state->dfs_depth = src->dfs_depth;
+	dst_state->callback_iter_depth = src->callback_iter_depth;
 	dst_state->used_as_loop_entry = src->used_as_loop_entry;
 	for (i = 0; i <= src->curframe; i++) {
 		dst = dst_state->frame[i];
@@ -3855,6 +3867,8 @@ static void fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask)
 	}
 }
 
+static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx);
+
 /* For given verifier state backtrack_insn() is called from the last insn to
  * the first insn. Its purpose is to compute a bitmask of registers and
  * stack slots that needs precision in the parent verifier state.
@@ -4030,10 +4044,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
 					return -EFAULT;
 				return 0;
 			}
-		} else if ((bpf_helper_call(insn) &&
-			    is_callback_calling_function(insn->imm) &&
-			    !is_async_callback_calling_function(insn->imm)) ||
-			   (bpf_pseudo_kfunc_call(insn) && is_callback_calling_kfunc(insn->imm))) {
+		} else if (is_sync_callback_calling_insn(insn) && idx != subseq_idx - 1) {
 			/* callback-calling helper or kfunc call, which means
 			 * we are exiting from subprog, but unlike the subprog
 			 * call handling above, we shouldn't propagate
@@ -4074,10 +4085,18 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
 		} else if (opcode == BPF_EXIT) {
 			bool r0_precise;
 
+			/* Backtracking to a nested function call, 'idx' is a part of
+			 * the inner frame 'subseq_idx' is a part of the outer frame.
+			 * In case of a regular function call, instructions giving
+			 * precision to registers R1-R5 should have been found already.
+			 * In case of a callback, it is ok to have R1-R5 marked for
+			 * backtracking, as these registers are set by the function
+			 * invoking callback.
+			 */
+			if (subseq_idx >= 0 && is_callback_iter_next(env, subseq_idx))
+				for (i = BPF_REG_1; i <= BPF_REG_5; i++)
+					bt_clear_reg(bt, i);
 			if (bt_reg_mask(bt) & BPF_REGMASK_ARGS) {
-				/* if backtracing was looking for registers R1-R5
-				 * they should have been found already.
-				 */
 				verbose(env, "BUG regs %x\n", bt_reg_mask(bt));
 				WARN_ONCE(1, "verifier backtracking bug");
 				return -EFAULT;
@@ -9596,11 +9615,11 @@ static int setup_func_entry(struct bpf_verifier_env *env, int subprog, int calls
 	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)
+static int push_callback_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_verifier_state *state = env->cur_state, *callback_state;
 	struct bpf_func_state *caller, *callee;
 	int err;
 
@@ -9608,44 +9627,22 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 	err = btf_check_subprog_call(env, subprog, caller->regs);
 	if (err == -EFAULT)
 		return err;
-	if (subprog_is_global(env, subprog)) {
-		if (err) {
-			verbose(env, "Caller passes invalid args into func#%d\n",
-				subprog);
-			return err;
-		} else {
-			if (env->log.level & BPF_LOG_LEVEL)
-				verbose(env,
-					"Func#%d is global and valid. Skipping.\n",
-					subprog);
-			clear_caller_saved_regs(env, caller->regs);
-
-			/* All global functions return a 64-bit SCALAR_VALUE */
-			mark_reg_unknown(env, caller->regs, BPF_REG_0);
-			caller->regs[BPF_REG_0].subreg_def = DEF_NOT_SUBREG;
-
-			/* continue with next insn after call */
-			return 0;
-		}
-	}
 
 	/* set_callee_state is used for direct subprog calls, but we are
 	 * interested in validating only BPF helpers that can call subprogs as
 	 * callbacks
 	 */
-	if (set_callee_state_cb != set_callee_state) {
-		env->subprog_info[subprog].is_cb = true;
-		if (bpf_pseudo_kfunc_call(insn) &&
-		    !is_callback_calling_kfunc(insn->imm)) {
-			verbose(env, "verifier bug: kfunc %s#%d not marked as callback-calling\n",
-				func_id_name(insn->imm), insn->imm);
-			return -EFAULT;
-		} else if (!bpf_pseudo_kfunc_call(insn) &&
-			   !is_callback_calling_function(insn->imm)) { /* helper */
-			verbose(env, "verifier bug: helper %s#%d not marked as callback-calling\n",
-				func_id_name(insn->imm), insn->imm);
-			return -EFAULT;
-		}
+	env->subprog_info[subprog].is_cb = true;
+	if (bpf_pseudo_kfunc_call(insn) &&
+	    !is_sync_callback_calling_kfunc(insn->imm)) {
+		verbose(env, "verifier bug: kfunc %s#%d not marked as callback-calling\n",
+			func_id_name(insn->imm), insn->imm);
+		return -EFAULT;
+	} else if (!bpf_pseudo_kfunc_call(insn) &&
+		   !is_callback_calling_function(insn->imm)) { /* helper */
+		verbose(env, "verifier bug: helper %s#%d not marked as callback-calling\n",
+			func_id_name(insn->imm), insn->imm);
+		return -EFAULT;
 	}
 
 	if (insn->code == (BPF_JMP | BPF_CALL) &&
@@ -9656,25 +9653,76 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		/* there is no real recursion here. timer callbacks are async */
 		env->subprog_info[subprog].is_async_cb = true;
 		async_cb = push_async_cb(env, env->subprog_info[subprog].start,
-					 *insn_idx, subprog);
+					 insn_idx, subprog);
 		if (!async_cb)
 			return -EFAULT;
 		callee = async_cb->frame[0];
 		callee->async_entry_cnt = caller->async_entry_cnt + 1;
 
 		/* Convert bpf_timer_set_callback() args into timer callback args */
-		err = set_callee_state_cb(env, caller, callee, *insn_idx);
+		err = set_callee_state_cb(env, caller, callee, insn_idx);
 		if (err)
 			return err;
 
+		return 0;
+	}
+
+	/* for callback functions enqueue entry to callback and
+	 * proceed with next instruction within current frame.
+	 */
+	callback_state = push_stack(env, env->subprog_info[subprog].start, insn_idx, false);
+	if (!callback_state)
+		return -ENOMEM;
+
+	err = setup_func_entry(env, subprog, insn_idx, set_callee_state_cb,
+			       callback_state);
+	if (err)
+		return err;
+
+	callback_state->callback_iter_depth++;
+	return 0;
+}
+
+static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			   int *insn_idx)
+{
+	struct bpf_verifier_state *state = env->cur_state;
+	struct bpf_func_state *caller;
+	int err, subprog, target_insn;
+
+	target_insn = *insn_idx + insn->imm + 1;
+	subprog = find_subprog(env, target_insn);
+	if (subprog < 0) {
+		verbose(env, "verifier bug. No program starts at insn %d\n", target_insn);
+		return -EFAULT;
+	}
+
+	caller = state->frame[state->curframe];
+	err = btf_check_subprog_call(env, subprog, caller->regs);
+	if (err == -EFAULT)
+		return err;
+	if (subprog_is_global(env, subprog)) {
+		if (err) {
+			verbose(env, "Caller passes invalid args into func#%d\n", subprog);
+			return err;
+		}
+
+		if (env->log.level & BPF_LOG_LEVEL)
+			verbose(env, "Func#%d is global and valid. Skipping.\n", subprog);
 		clear_caller_saved_regs(env, caller->regs);
+
+		/* All global functions return a 64-bit SCALAR_VALUE */
 		mark_reg_unknown(env, caller->regs, BPF_REG_0);
 		caller->regs[BPF_REG_0].subreg_def = DEF_NOT_SUBREG;
+
 		/* continue with next insn after call */
 		return 0;
 	}
 
-	err = setup_func_entry(env, subprog, *insn_idx, set_callee_state_cb, state);
+	/* for regular function entry setup new frame and continue
+	 * from that frame.
+	 */
+	err = setup_func_entry(env, subprog, *insn_idx, set_callee_state, state);
 	if (err)
 		return err;
 
@@ -9734,22 +9782,6 @@ static int set_callee_state(struct bpf_verifier_env *env,
 	return 0;
 }
 
-static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
-			   int *insn_idx)
-{
-	int subprog, target_insn;
-
-	target_insn = *insn_idx + insn->imm + 1;
-	subprog = find_subprog(env, target_insn);
-	if (subprog < 0) {
-		verbose(env, "verifier bug. No program starts at insn %d\n",
-			target_insn);
-		return -EFAULT;
-	}
-
-	return __check_func_call(env, insn, insn_idx, subprog, set_callee_state);
-}
-
 static int set_map_elem_callback_state(struct bpf_verifier_env *env,
 				       struct bpf_func_state *caller,
 				       struct bpf_func_state *callee,
@@ -9990,7 +10022,15 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 			return err;
 	}
 
-	*insn_idx = callee->callsite + 1;
+	/* for callbacks like bpf_loop or bpf_for_each_map_elem go back to callsite,
+	 * 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))
+		*insn_idx = callee->callsite;
+	else
+		*insn_idx = callee->callsite + 1;
+
 	if (env->log.level & BPF_LOG_LEVEL) {
 		verbose(env, "returning from callee:\n");
 		print_verifier_state(env, callee, true);
@@ -10403,24 +10443,24 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		}
 		break;
 	case BPF_FUNC_for_each_map_elem:
-		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
-					set_map_elem_callback_state);
+		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+					 set_map_elem_callback_state);
 		break;
 	case BPF_FUNC_timer_set_callback:
-		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
-					set_timer_callback_state);
+		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+					 set_timer_callback_state);
 		break;
 	case BPF_FUNC_find_vma:
-		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
-					set_find_vma_callback_state);
+		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+					 set_find_vma_callback_state);
 		break;
 	case BPF_FUNC_snprintf:
 		err = check_bpf_snprintf_call(env, regs);
 		break;
 	case BPF_FUNC_loop:
 		update_loop_inline_state(env, meta.subprogno);
-		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
-					set_loop_callback_state);
+		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+					 set_loop_callback_state);
 		break;
 	case BPF_FUNC_dynptr_from_mem:
 		if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
@@ -10516,8 +10556,8 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 		break;
 	}
 	case BPF_FUNC_user_ringbuf_drain:
-		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
-					set_user_ringbuf_callback_state);
+		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+					 set_user_ringbuf_callback_state);
 		break;
 	}
 
@@ -11414,7 +11454,7 @@ static bool is_bpf_graph_api_kfunc(u32 btf_id)
 	       btf_id == special_kfunc_list[KF_bpf_refcount_acquire_impl];
 }
 
-static bool is_callback_calling_kfunc(u32 btf_id)
+static bool is_sync_callback_calling_kfunc(u32 btf_id)
 {
 	return btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl];
 }
@@ -12176,6 +12216,21 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		return -EACCES;
 	}
 
+	/* Check the arguments */
+	err = check_kfunc_args(env, &meta, insn_idx);
+	if (err < 0)
+		return err;
+
+	if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {
+		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
+					 set_rbtree_add_callback_state);
+		if (err) {
+			verbose(env, "kfunc %s#%d failed callback verification\n",
+				func_name, meta.func_id);
+			return err;
+		}
+	}
+
 	rcu_lock = is_kfunc_bpf_rcu_read_lock(&meta);
 	rcu_unlock = is_kfunc_bpf_rcu_read_unlock(&meta);
 
@@ -12211,10 +12266,6 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		return -EINVAL;
 	}
 
-	/* Check the arguments */
-	err = check_kfunc_args(env, &meta, insn_idx);
-	if (err < 0)
-		return err;
 	/* In case of release function, we get register number of refcounted
 	 * PTR_TO_BTF_ID in bpf_kfunc_arg_meta, do the release now.
 	 */
@@ -12248,16 +12299,6 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		}
 	}
 
-	if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {
-		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
-					set_rbtree_add_callback_state);
-		if (err) {
-			verbose(env, "kfunc %s#%d failed callback verification\n",
-				func_name, meta.func_id);
-			return err;
-		}
-	}
-
 	if (meta.func_id == special_kfunc_list[KF_bpf_throw]) {
 		if (!bpf_jit_supports_exceptions()) {
 			verbose(env, "JIT does not support calling kfunc %s#%d\n",
@@ -15504,6 +15545,15 @@ static bool is_force_checkpoint(struct bpf_verifier_env *env, int insn_idx)
 	return env->insn_aux_data[insn_idx].force_checkpoint;
 }
 
+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;
+}
 
 enum {
 	DONE_EXPLORING = 0,
@@ -15620,6 +15670,21 @@ static int visit_insn(int t, struct bpf_verifier_env *env)
 			 * async state will be pushed for further exploration.
 			 */
 			mark_prune_point(env, t);
+		/* For functions that invoke callbacks it is not known how many times
+		 * callback would be called. Verifier models callback calling functions
+		 * by repeatedly visiting callback bodies and returning to origin call
+		 * instruction.
+		 * In order to stop such iteration verifier needs to identify when a
+		 * state identical some state from a previous iteration is reached.
+		 * Check below forces creation of checkpoint before callback calling
+		 * instruction to allow search for such identical states.
+		 */
+		if (is_sync_callback_calling_insn(insn)) {
+			mark_callback_iter_next(env, t);
+			mark_force_checkpoint(env, t);
+			mark_prune_point(env, t);
+			mark_jmp_point(env, t);
+		}
 		if (insn->src_reg == BPF_PSEUDO_KFUNC_CALL) {
 			struct bpf_kfunc_call_arg_meta meta;
 
@@ -17080,10 +17145,16 @@ static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 				}
 				goto skip_inf_loop_check;
 			}
+			if (is_callback_iter_next(env, insn_idx)) {
+				if (states_equal(env, &sl->state, cur, true))
+					goto hit;
+				goto skip_inf_loop_check;
+			}
 			/* attempt to detect infinite loop to avoid unnecessary doomed work */
 			if (states_maybe_looping(&sl->state, cur) &&
 			    states_equal(env, &sl->state, cur, false) &&
-			    !iter_active_depths_differ(&sl->state, cur)) {
+			    !iter_active_depths_differ(&sl->state, cur) &&
+			    sl->state.callback_iter_depth == cur->callback_iter_depth) {
 				verbose_linfo(env, insn_idx, "; ");
 				verbose(env, "infinite loop detected at insn %d\n", insn_idx);
 				verbose(env, "cur state:");
diff --git a/tools/testing/selftests/bpf/prog_tests/cb_refs.c b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
index 3bff680de16c..b5aa168889c1 100644
--- a/tools/testing/selftests/bpf/prog_tests/cb_refs.c
+++ b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
@@ -21,12 +21,14 @@ void test_cb_refs(void)
 {
 	LIBBPF_OPTS(bpf_object_open_opts, opts, .kernel_log_buf = log_buf,
 						.kernel_log_size = sizeof(log_buf),
-						.kernel_log_level = 1);
+						.kernel_log_level = 1 | 2 | 4);
 	struct bpf_program *prog;
 	struct cb_refs *skel;
 	int i;
 
 	for (i = 0; i < ARRAY_SIZE(cb_refs_tests); i++) {
+		if (!test__start_subtest(cb_refs_tests[i].prog_name))
+			continue;
 		LIBBPF_OPTS(bpf_test_run_opts, run_opts,
 			.data_in = &pkt_v4,
 			.data_size_in = sizeof(pkt_v4),
diff --git a/tools/testing/selftests/bpf/progs/cb_refs.c b/tools/testing/selftests/bpf/progs/cb_refs.c
index 76d661b20e87..56c764df8196 100644
--- a/tools/testing/selftests/bpf/progs/cb_refs.c
+++ b/tools/testing/selftests/bpf/progs/cb_refs.c
@@ -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;
 }
 
diff --git a/tools/testing/selftests/bpf/progs/exceptions_fail.c b/tools/testing/selftests/bpf/progs/exceptions_fail.c
index 4c39e920dac2..8c0ef2742208 100644
--- a/tools/testing/selftests/bpf/progs/exceptions_fail.c
+++ b/tools/testing/selftests/bpf/progs/exceptions_fail.c
@@ -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;
 }
 
diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
index db6b3143338b..ead358679fe2 100644
--- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
+++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
@@ -120,14 +120,12 @@ __naked int global_subprog_result_precise(void)
 SEC("?raw_tp")
 __success __log_level(2)
 __msg("14: (0f) r1 += r6")
-__msg("mark_precise: frame0: last_idx 14 first_idx 10")
+__msg("mark_precise: frame0: last_idx 14 first_idx 9")
 __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
 __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
 __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
 __msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")
-__msg("mark_precise: frame0: parent state regs=r0 stack=:")
-__msg("mark_precise: frame0: last_idx 18 first_idx 0")
-__msg("mark_precise: frame0: regs=r0 stack= before 18: (95) exit")
+__msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")
 __naked int callback_result_precise(void)
 {
 	asm volatile (
@@ -234,14 +232,12 @@ __naked int parent_callee_saved_reg_precise_global(void)
 SEC("?raw_tp")
 __success __log_level(2)
 __msg("12: (0f) r1 += r6")
-__msg("mark_precise: frame0: last_idx 12 first_idx 10")
+__msg("mark_precise: frame0: last_idx 12 first_idx 9")
 __msg("mark_precise: frame0: regs=r6 stack= before 11: (bf) r1 = r7")
 __msg("mark_precise: frame0: regs=r6 stack= before 10: (27) r6 *= 4")
+__msg("mark_precise: frame0: regs=r6 stack= before 9: (85) call bpf_loop")
 __msg("mark_precise: frame0: parent state regs=r6 stack=:")
-__msg("mark_precise: frame0: last_idx 16 first_idx 0")
-__msg("mark_precise: frame0: regs=r6 stack= before 16: (95) exit")
-__msg("mark_precise: frame1: regs= stack= before 15: (b7) r0 = 0")
-__msg("mark_precise: frame1: regs= stack= before 9: (85) call bpf_loop#181")
+__msg("mark_precise: frame0: last_idx 8 first_idx 0 subseq_idx 9")
 __msg("mark_precise: frame0: regs=r6 stack= before 8: (b7) r4 = 0")
 __msg("mark_precise: frame0: regs=r6 stack= before 7: (b7) r3 = 0")
 __msg("mark_precise: frame0: regs=r6 stack= before 6: (bf) r2 = r8")
@@ -374,15 +370,13 @@ __naked int parent_stack_slot_precise_global(void)
 SEC("?raw_tp")
 __success __log_level(2)
 __msg("14: (0f) r1 += r6")
-__msg("mark_precise: frame0: last_idx 14 first_idx 11")
+__msg("mark_precise: frame0: last_idx 14 first_idx 10")
 __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
 __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
 __msg("mark_precise: frame0: regs=r6 stack= before 11: (79) r6 = *(u64 *)(r10 -8)")
+__msg("mark_precise: frame0: regs= stack=-8 before 10: (85) call bpf_loop")
 __msg("mark_precise: frame0: parent state regs= stack=-8:")
-__msg("mark_precise: frame0: last_idx 18 first_idx 0")
-__msg("mark_precise: frame0: regs= stack=-8 before 18: (95) exit")
-__msg("mark_precise: frame1: regs= stack= before 17: (b7) r0 = 0")
-__msg("mark_precise: frame1: regs= stack= before 10: (85) call bpf_loop#181")
+__msg("mark_precise: frame0: last_idx 9 first_idx 0 subseq_idx 10")
 __msg("mark_precise: frame0: regs= stack=-8 before 9: (b7) r4 = 0")
 __msg("mark_precise: frame0: regs= stack=-8 before 8: (b7) r3 = 0")
 __msg("mark_precise: frame0: regs= stack=-8 before 7: (bf) r2 = r8")
-- 
2.42.0

[PATCH bpf 07/12] selftests/bpf: tests for iterating callbacks

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

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../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

diff --git a/tools/testing/selftests/bpf/prog_tests/verifier.c b/tools/testing/selftests/bpf/prog_tests/verifier.c
index e5c61aa6604a..5cfa7a6316b6 100644
--- a/tools/testing/selftests/bpf/prog_tests/verifier.c
+++ b/tools/testing/selftests/bpf/prog_tests/verifier.c
@@ -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); }
diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
new file mode 100644
index 000000000000..fa9429f77a81
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -0,0 +1,147 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 8);
+	__type(key, __u32);
+	__type(value, __u64);
+} map SEC(".maps");
+
+struct {
+	__uint(type, BPF_MAP_TYPE_USER_RINGBUF);
+	__uint(max_entries, 8);
+} ringbuf SEC(".maps");
+
+struct vm_area_struct;
+struct bpf_map;
+
+struct buf_context {
+	char *buf;
+};
+
+struct num_context {
+	__u64 i;
+};
+
+__u8 choice_arr[2] = { 0, 1 };
+
+static int unsafe_on_2nd_iter_cb(__u32 idx, struct buf_context *ctx)
+{
+	if (idx == 0) {
+		ctx->buf = (char *)(0xDEAD);
+		return 0;
+	}
+
+	if (bpf_probe_read_user(ctx->buf, 8, (void *)(0xBADC0FFEE)))
+		return 1;
+
+	return 0;
+}
+
+SEC("?raw_tp")
+__failure __msg("R1 type=scalar expected=fp")
+int unsafe_on_2nd_iter(void *unused)
+{
+	char buf[4];
+	struct buf_context loop_ctx = { .buf = buf };
+
+	bpf_loop(100, unsafe_on_2nd_iter_cb, &loop_ctx, 0);
+	return 0;
+}
+
+static int unsafe_on_zero_iter_cb(__u32 idx, struct num_context *ctx)
+{
+	ctx->i = 0;
+	return 0;
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
+int unsafe_on_zero_iter(void *unused)
+{
+	struct num_context loop_ctx = { .i = 32 };
+
+	bpf_loop(100, unsafe_on_zero_iter_cb, &loop_ctx, 0);
+	return choice_arr[loop_ctx.i];
+}
+
+static int loop_detection_cb(__u32 idx, struct num_context *ctx)
+{
+	for (;;) {}
+	return 0;
+}
+
+SEC("?raw_tp")
+__failure __msg("infinite loop detected")
+int loop_detection(void *unused)
+{
+	struct num_context loop_ctx = { .i = 0 };
+
+	bpf_loop(100, loop_detection_cb, &loop_ctx, 0);
+	return 0;
+}
+
+static __always_inline __u64 oob_state_machine(struct num_context *ctx)
+{
+	switch (ctx->i) {
+	case 0:
+		ctx->i = 1;
+		break;
+	case 1:
+		ctx->i = 32;
+		break;
+	}
+	return 0;
+}
+
+static __u64 for_each_map_elem_cb(struct bpf_map *map, __u32 *key, __u64 *val, void *data)
+{
+	return oob_state_machine(data);
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
+int unsafe_for_each_map_elem(void *unused)
+{
+	struct num_context loop_ctx = { .i = 0 };
+
+	bpf_for_each_map_elem(&map, for_each_map_elem_cb, &loop_ctx, 0);
+	return choice_arr[loop_ctx.i];
+}
+
+static __u64 ringbuf_drain_cb(struct bpf_dynptr *dynptr, void *data)
+{
+	return oob_state_machine(data);
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
+int unsafe_ringbuf_drain(void *unused)
+{
+	struct num_context loop_ctx = { .i = 0 };
+
+	bpf_user_ringbuf_drain(&ringbuf, ringbuf_drain_cb, &loop_ctx, 0);
+	return choice_arr[loop_ctx.i];
+}
+
+static __u64 find_vma_cb(struct task_struct *task, struct vm_area_struct *vma, void *data)
+{
+	return oob_state_machine(data);
+}
+
+SEC("?raw_tp")
+__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
+int unsafe_find_vma(void *unused)
+{
+	struct task_struct *task = bpf_get_current_task_btf();
+	struct num_context loop_ctx = { .i = 0 };
+
+	bpf_find_vma(task, 0, find_vma_cb, &loop_ctx, 0);
+	return choice_arr[loop_ctx.i];
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.42.0

[PATCH bpf 08/12] bpf: widening for callback iterators

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

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

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 270f7ca3c44d..5b8c0ebcb4f6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9974,9 +9974,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];
@@ -10026,7 +10027,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;
@@ -10041,6 +10043,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;
 }
 
-- 
2.42.0

[PATCH bpf 09/12] selftests/bpf: test widening for iterating callbacks

[Eduard Zingerman]

A test case to verify that imprecise scalars widening is applied to
callback bodies on repetative iteration.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 .../bpf/progs/verifier_iterating_callbacks.c  | 20 +++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index fa9429f77a81..598c1e984b26 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -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 (;;) {}
-- 
2.42.0

[PATCH bpf 10/12] bpf: keep track of max number of bpf_loop callback iterations

[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 <eddyz87@gmail.com>
---
 include/linux/bpf_verifier.h |  9 +++++++++
 kernel/bpf/verifier.c        | 12 ++++++++++--
 2 files changed, 19 insertions(+), 2 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 0ffb479c72d8..302f9c310de7 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 5b8c0ebcb4f6..474af277ea54 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9680,6 +9680,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;
 }
 
@@ -10479,8 +10481,14 @@ 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);
+		if (env->log.level & BPF_LOG_LEVEL2)
+			verbose(env, "frame%d callback_depth=%u\n",
+				env->cur_state->curframe, cur_func(env)->callback_depth);
+		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;
 		break;
 	case BPF_FUNC_dynptr_from_mem:
 		if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
-- 
2.42.0

[PATCH bpf 11/12] selftests/bpf: add __not_msg annotation for test_loader based tests

[Eduard Zingerman]

Add an ability to specify messages that should not be found in the
test verifier log. Similar to LLVM's FileCheck tool for the following
test specification:

    __success
    __msg("a")
    __not_msg("b")
    __msg("c")
    void foo(...) { ... }

- message "a" is expected to be in the log;
- message "b" is not expected after message "a"
  (but could be present before "a");
- message "c" is expected to be in the log after message "a".

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/bpf_misc.h |  9 +++
 tools/testing/selftests/bpf/test_loader.c    | 82 ++++++++++++++------
 2 files changed, 68 insertions(+), 23 deletions(-)

diff --git a/tools/testing/selftests/bpf/progs/bpf_misc.h b/tools/testing/selftests/bpf/progs/bpf_misc.h
index 799fff4995d8..f24fcda6fc0b 100644
--- a/tools/testing/selftests/bpf/progs/bpf_misc.h
+++ b/tools/testing/selftests/bpf/progs/bpf_misc.h
@@ -22,7 +22,13 @@
  *
  * __msg             Message expected to be found in the verifier log.
  *                   Multiple __msg attributes could be specified.
+ *                   When multiple messages are specified they are
+ *                   matched one after another.
+ * __not_msg	     Message not expected to be found in the verifier log.
+ *                   Matched from the end of the last checked __msg or
+ *                   from log start, if no __msg had been matched yet.
  * __msg_unpriv      Same as __msg but for unprivileged mode.
+ * __not_msg_unpriv  Same as __not_msg but for unprivileged mode.
  *
  * __success         Expect program load success in privileged mode.
  * __success_unpriv  Expect program load success in unprivileged mode.
@@ -59,10 +65,13 @@
  * __auxiliary_unpriv  Same, but load program in unprivileged mode.
  */
 #define __msg(msg)		__attribute__((btf_decl_tag("comment:test_expect_msg=" msg)))
+#define __not_msg(msg)		__attribute__((btf_decl_tag("comment:test_dont_expect_msg=" msg)))
 #define __failure		__attribute__((btf_decl_tag("comment:test_expect_failure")))
 #define __success		__attribute__((btf_decl_tag("comment:test_expect_success")))
 #define __description(desc)	__attribute__((btf_decl_tag("comment:test_description=" desc)))
 #define __msg_unpriv(msg)	__attribute__((btf_decl_tag("comment:test_expect_msg_unpriv=" msg)))
+#define __not_msg_unpriv(msg)						\
+	__attribute__((btf_decl_tag("comment:test_dont_expect_msg_unpriv=" msg)))
 #define __failure_unpriv	__attribute__((btf_decl_tag("comment:test_expect_failure_unpriv")))
 #define __success_unpriv	__attribute__((btf_decl_tag("comment:test_expect_success_unpriv")))
 #define __log_level(lvl)	__attribute__((btf_decl_tag("comment:test_log_level="#lvl)))
diff --git a/tools/testing/selftests/bpf/test_loader.c b/tools/testing/selftests/bpf/test_loader.c
index 37ffa57f28a1..def16d9aeae2 100644
--- a/tools/testing/selftests/bpf/test_loader.c
+++ b/tools/testing/selftests/bpf/test_loader.c
@@ -17,9 +17,11 @@
 #define TEST_TAG_EXPECT_FAILURE "comment:test_expect_failure"
 #define TEST_TAG_EXPECT_SUCCESS "comment:test_expect_success"
 #define TEST_TAG_EXPECT_MSG_PFX "comment:test_expect_msg="
+#define TEST_TAG_DONT_EXPECT_MSG_PFX "comment:test_dont_expect_msg="
 #define TEST_TAG_EXPECT_FAILURE_UNPRIV "comment:test_expect_failure_unpriv"
 #define TEST_TAG_EXPECT_SUCCESS_UNPRIV "comment:test_expect_success_unpriv"
 #define TEST_TAG_EXPECT_MSG_PFX_UNPRIV "comment:test_expect_msg_unpriv="
+#define TEST_TAG_DONT_EXPECT_MSG_PFX_UNPRIV "comment:test_dont_expect_msg_unpriv="
 #define TEST_TAG_LOG_LEVEL_PFX "comment:test_log_level="
 #define TEST_TAG_PROG_FLAGS_PFX "comment:test_prog_flags="
 #define TEST_TAG_DESCRIPTION_PFX "comment:test_description="
@@ -45,10 +47,15 @@ enum mode {
 	UNPRIV = 2
 };
 
+struct pattern {
+	const char *str;
+	bool expected;
+};
+
 struct test_subspec {
 	char *name;
 	bool expect_failure;
-	const char **expect_msgs;
+	struct pattern *expect_msgs;
 	size_t expect_msg_cnt;
 	int retval;
 	bool execute;
@@ -98,17 +105,21 @@ static void free_test_spec(struct test_spec *spec)
 	spec->unpriv.expect_msgs = NULL;
 }
 
-static int push_msg(const char *msg, struct test_subspec *subspec)
+static int push_msg(const char *msg, struct test_subspec *subspec, bool expected)
 {
+	size_t cnt = subspec->expect_msg_cnt;
 	void *tmp;
 
-	tmp = realloc(subspec->expect_msgs, (1 + subspec->expect_msg_cnt) * sizeof(void *));
+	tmp = realloc(subspec->expect_msgs,
+		      (1 + subspec->expect_msg_cnt) * sizeof(*subspec->expect_msgs));
 	if (!tmp) {
 		ASSERT_FAIL("failed to realloc memory for messages\n");
 		return -ENOMEM;
 	}
 	subspec->expect_msgs = tmp;
-	subspec->expect_msgs[subspec->expect_msg_cnt++] = msg;
+	subspec->expect_msgs[cnt].str = msg;
+	subspec->expect_msgs[cnt].expected = expected;
+	subspec->expect_msg_cnt++;
 
 	return 0;
 }
@@ -221,13 +232,25 @@ static int parse_test_spec(struct test_loader *tester,
 			spec->mode_mask |= UNPRIV;
 		} else if (str_has_pfx(s, TEST_TAG_EXPECT_MSG_PFX)) {
 			msg = s + sizeof(TEST_TAG_EXPECT_MSG_PFX) - 1;
-			err = push_msg(msg, &spec->priv);
+			err = push_msg(msg, &spec->priv, true);
 			if (err)
 				goto cleanup;
 			spec->mode_mask |= PRIV;
 		} else if (str_has_pfx(s, TEST_TAG_EXPECT_MSG_PFX_UNPRIV)) {
 			msg = s + sizeof(TEST_TAG_EXPECT_MSG_PFX_UNPRIV) - 1;
-			err = push_msg(msg, &spec->unpriv);
+			err = push_msg(msg, &spec->unpriv, true);
+			if (err)
+				goto cleanup;
+			spec->mode_mask |= UNPRIV;
+		} else if (str_has_pfx(s, TEST_TAG_DONT_EXPECT_MSG_PFX)) {
+			msg = s + sizeof(TEST_TAG_DONT_EXPECT_MSG_PFX) - 1;
+			err = push_msg(msg, &spec->priv, false);
+			if (err)
+				goto cleanup;
+			spec->mode_mask |= PRIV;
+		} else if (str_has_pfx(s, TEST_TAG_DONT_EXPECT_MSG_PFX_UNPRIV)) {
+			msg = s + sizeof(TEST_TAG_DONT_EXPECT_MSG_PFX_UNPRIV) - 1;
+			err = push_msg(msg, &spec->unpriv, false);
 			if (err)
 				goto cleanup;
 			spec->mode_mask |= UNPRIV;
@@ -316,7 +339,7 @@ static int parse_test_spec(struct test_loader *tester,
 		}
 
 		if (!spec->unpriv.expect_msgs) {
-			size_t sz = spec->priv.expect_msg_cnt * sizeof(void *);
+			size_t sz = spec->priv.expect_msg_cnt * sizeof(*spec->priv.expect_msgs);
 
 			spec->unpriv.expect_msgs = malloc(sz);
 			if (!spec->unpriv.expect_msgs) {
@@ -375,33 +398,46 @@ static void emit_verifier_log(const char *log_buf, bool force)
 	fprintf(stdout, "VERIFIER LOG:\n=============\n%s=============\n", log_buf);
 }
 
+static void show_log_and_msgs(struct test_loader *tester, struct test_subspec *subspec, int n)
+{
+	struct pattern *pat;
+	int i;
+
+	if (env.verbosity == VERBOSE_NONE)
+		emit_verifier_log(tester->log_buf, true /*force*/);
+	for (i = 0; i < n; i++) {
+		pat = &subspec->expect_msgs[i];
+		fprintf(stderr, "   MATCHED MSG: %s'%s'\n", pat->expected ? "" : "!", pat->str);
+	}
+}
+
 static void validate_case(struct test_loader *tester,
 			  struct test_subspec *subspec,
 			  struct bpf_object *obj,
 			  struct bpf_program *prog,
 			  int load_err)
 {
-	int i, j;
+	int i;
 
 	for (i = 0; i < subspec->expect_msg_cnt; i++) {
+		struct pattern *pat = &subspec->expect_msgs[i];
 		char *match;
-		const char *expect_msg;
-
-		expect_msg = subspec->expect_msgs[i];
-
-		match = strstr(tester->log_buf + tester->next_match_pos, expect_msg);
-		if (!ASSERT_OK_PTR(match, "expect_msg")) {
-			/* if we are in verbose mode, we've already emitted log */
-			if (env.verbosity == VERBOSE_NONE)
-				emit_verifier_log(tester->log_buf, true /*force*/);
-			for (j = 0; j < i; j++)
-				fprintf(stderr,
-					"MATCHED  MSG: '%s'\n", subspec->expect_msgs[j]);
-			fprintf(stderr, "EXPECTED MSG: '%s'\n", expect_msg);
+
+		match = strstr(tester->log_buf + tester->next_match_pos, pat->str);
+		if (pat->expected && !match) {
+			PRINT_FAIL("Expected log message not found\n");
+			show_log_and_msgs(tester, subspec, i);
+			fprintf(stderr, "  EXPECTED MSG: '%s'\n", pat->str);
 			return;
 		}
-
-		tester->next_match_pos = match - tester->log_buf + strlen(expect_msg);
+		if (!pat->expected && match) {
+			PRINT_FAIL("Unexpected log message found\n");
+			show_log_and_msgs(tester, subspec, i);
+			fprintf(stderr, "UNEXPECTED MSG: '%s'\n", pat->str);
+			return;
+		}
+		if (pat->expected)
+			tester->next_match_pos = match - tester->log_buf + strlen(pat->str);
 	}
 }
 
-- 
2.42.0

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

[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 <eddyz87@gmail.com>
---
 .../bpf/progs/verifier_iterating_callbacks.c  | 67 +++++++++++++++++++
 1 file changed, 67 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
index 598c1e984b26..da10ce57da5e 100644
--- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
+++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
@@ -164,4 +164,71 @@ 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 last verified exit from the program visited each
+ * callback expected number of times: one visit per callback for each
+ * top level bpf_loop call.
+ */
+__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
+/* Ensure that read above is the last one by checking that there are
+ * no more reads for ctx.i.
+ */
+__not_msg("r1 = *(u64 *)(r10 -16)	; R1_w=")
+int bpf_loop_iter_limit_nested(void *unused)
+{
+	struct num_context ctx = { .i = 0 };
+
+	bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
+	ctx.i *= 1000;
+	bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
+	return choice_arr[ctx.i % 2];
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.42.0

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

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h |  9 +++++++++
>  kernel/bpf/verifier.c        | 12 ++++++++++--
>  2 files changed, 19 insertions(+), 2 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 0ffb479c72d8..302f9c310de7 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -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;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5b8c0ebcb4f6..474af277ea54 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9680,6 +9680,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;
>  }
>
> @@ -10479,8 +10481,14 @@ 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);
> +               if (env->log.level & BPF_LOG_LEVEL2)
> +                       verbose(env, "frame%d callback_depth=%u\n",
> +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> +               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)

I haven't had time to look at the patch set properly yet and I'm not
sure if I'll have time today. But one thing that I randomly realized
is that if you are taking umax_value into account then this BPF_REG_1
has to be precise, so please make sure to mark_chain_precision() on it
first.

> +                       err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> +                                                set_loop_callback_state);
> +               else
> +                       cur_func(env)->callback_depth = 0;
>                 break;
>         case BPF_FUNC_dynptr_from_mem:
>                 if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
> --
> 2.42.0
>

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

[Eduard Zingerman]

On Thu, 2023-11-16 at 09:08 -0500, Andrii Nakryiko wrote:
[...]
> > @@ -10479,8 +10481,14 @@ 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);
> > +               if (env->log.level & BPF_LOG_LEVEL2)
> > +                       verbose(env, "frame%d callback_depth=%u\n",
> > +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> > +               if (cur_func(env)->callback_depth < regs[BPF_REG_1].umax_value)
> 
> I haven't had time to look at the patch set properly yet and I'm not
> sure if I'll have time today. But one thing that I randomly realized
> is that if you are taking umax_value into account then this BPF_REG_1
> has to be precise, so please make sure to mark_chain_precision() on it
> first.

Yes, makes sense, thank you for spotting this.
Will update in v2, waiting for some more feedback before resending.

Re: [PATCH bpf 11/12] selftests/bpf: add __not_msg annotation for test_loader based tests

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> Add an ability to specify messages that should not be found in the
> test verifier log. Similar to LLVM's FileCheck tool for the following
> test specification:
>
>     __success
>     __msg("a")
>     __not_msg("b")
>     __msg("c")
>     void foo(...) { ... }
>
> - message "a" is expected to be in the log;
> - message "b" is not expected after message "a"
>   (but could be present before "a");
> - message "c" is expected to be in the log after message "a".

I think this implementation has an undesired surprising behavior.
Imagine you have a log like this:

A
C
D
B


And you specify

__msg("A")
__nomsg("B")
__msg("C")
__msg("D")
__msg("B")

Log matches the spec, right? But your implementation will eagerly reject it.

I think you can implement more coherent behavior if you only strstr()
__msg() specs, skipping __nomsg() first. But on each __msg one, if
successful, you go back and validate that there are no matches for all
__nomsg() specs that you skipped, taking into account matched
positions for current __msg() and last __msg() (or the start of the
log, of course).

Not sure if I explained clearly, but the idea is to postpone __nomsg()
until we anchor ourselves between two __msg()s. And beginning/end of
verifier log are two other anchoring positions.

>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  tools/testing/selftests/bpf/progs/bpf_misc.h |  9 +++
>  tools/testing/selftests/bpf/test_loader.c    | 82 ++++++++++++++------
>  2 files changed, 68 insertions(+), 23 deletions(-)
>
> diff --git a/tools/testing/selftests/bpf/progs/bpf_misc.h b/tools/testing/selftests/bpf/progs/bpf_misc.h
> index 799fff4995d8..f24fcda6fc0b 100644
> --- a/tools/testing/selftests/bpf/progs/bpf_misc.h
> +++ b/tools/testing/selftests/bpf/progs/bpf_misc.h
> @@ -22,7 +22,13 @@
>   *
>   * __msg             Message expected to be found in the verifier log.
>   *                   Multiple __msg attributes could be specified.
> + *                   When multiple messages are specified they are
> + *                   matched one after another.
> + * __not_msg        Message not expected to be found in the verifier log.
> + *                   Matched from the end of the last checked __msg or
> + *                   from log start, if no __msg had been matched yet.
>   * __msg_unpriv      Same as __msg but for unprivileged mode.
> + * __not_msg_unpriv  Same as __not_msg but for unprivileged mode.

ok, it's bikeshedding, but __nomsg and __nomsg_unpriv seems a bit
nicer names for this (very subjective, of course)

>   *
>   * __success         Expect program load success in privileged mode.
>   * __success_unpriv  Expect program load success in unprivileged mode.
> @@ -59,10 +65,13 @@
>   * __auxiliary_unpriv  Same, but load program in unprivileged mode.
>   */
>  #define __msg(msg)             __attribute__((btf_decl_tag("comment:test_expect_msg=" msg)))
> +#define __not_msg(msg)         __attribute__((btf_decl_tag("comment:test_dont_expect_msg=" msg)))
>  #define __failure              __attribute__((btf_decl_tag("comment:test_expect_failure")))
>  #define __success              __attribute__((btf_decl_tag("comment:test_expect_success")))
>  #define __description(desc)    __attribute__((btf_decl_tag("comment:test_description=" desc)))
>  #define __msg_unpriv(msg)      __attribute__((btf_decl_tag("comment:test_expect_msg_unpriv=" msg)))
> +#define __not_msg_unpriv(msg)                                          \
> +       __attribute__((btf_decl_tag("comment:test_dont_expect_msg_unpriv=" msg)))

test_expect_no_msg ?

>  #define __failure_unpriv       __attribute__((btf_decl_tag("comment:test_expect_failure_unpriv")))
>  #define __success_unpriv       __attribute__((btf_decl_tag("comment:test_expect_success_unpriv")))
>  #define __log_level(lvl)       __attribute__((btf_decl_tag("comment:test_log_level="#lvl)))
> diff --git a/tools/testing/selftests/bpf/test_loader.c b/tools/testing/selftests/bpf/test_loader.c
> index 37ffa57f28a1..def16d9aeae2 100644
> --- a/tools/testing/selftests/bpf/test_loader.c
> +++ b/tools/testing/selftests/bpf/test_loader.c

[...]

> -static int push_msg(const char *msg, struct test_subspec *subspec)
> +static int push_msg(const char *msg, struct test_subspec *subspec, bool expected)
>  {
> +       size_t cnt = subspec->expect_msg_cnt;
>         void *tmp;
>
> -       tmp = realloc(subspec->expect_msgs, (1 + subspec->expect_msg_cnt) * sizeof(void *));
> +       tmp = realloc(subspec->expect_msgs,
> +                     (1 + subspec->expect_msg_cnt) * sizeof(*subspec->expect_msgs));

nit: 1 + cnt ?

>         if (!tmp) {
>                 ASSERT_FAIL("failed to realloc memory for messages\n");
>                 return -ENOMEM;
>         }
>         subspec->expect_msgs = tmp;
> -       subspec->expect_msgs[subspec->expect_msg_cnt++] = msg;
> +       subspec->expect_msgs[cnt].str = msg;
> +       subspec->expect_msgs[cnt].expected = expected;
> +       subspec->expect_msg_cnt++;
>
>         return 0;
>  }

[...]

Re: [PATCH bpf 01/12] selftests/bpf: track tcp payload offset as scalar in xdp_synproxy

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  .../selftests/bpf/progs/xdp_synproxy_kern.c   | 84 ++++++++++++-------
>  1 file changed, 52 insertions(+), 32 deletions(-)
>

LGTM.

Acked-by: Andrii Nakryiko <andrii@kernel.org>

[...]

Re: [PATCH bpf 02/12] selftests/bpf: track string payload offset as scalar in strobemeta

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> This change prepares strobemeta for update in callbakcs verification

typo: callbacks

> logic. To allow bpf_loop() verification converge when multiple
> callback itreations are considered:

typo: iterations

> - 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.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  .../testing/selftests/bpf/progs/strobemeta.h  | 78 ++++++++++++-------
>  1 file changed, 48 insertions(+), 30 deletions(-)
>

Acked-by: Andrii Nakryiko <andrii@kernel.org>

Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> The patch a few patches from this one 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 for verifier it merely represents 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;
>   ...

would this still happen if you use an obfuscated zero initializer for i?

int zero = 0; /* global var */

...


for (i = zero; i < 1000; i++) {
     ...
}

>
> 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
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  tools/testing/selftests/bpf/progs/bpf_loop_bench.c | 13 ++++++++-----
>  1 file changed, 8 insertions(+), 5 deletions(-)
>

Either way, it doesn't seem like a big deal to me.

Acked-by: Andrii Nakryiko <andrii@kernel.org>



> diff --git a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
> index 4ce76eb064c4..d461746fd3c1 100644
> --- a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
> +++ b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
> @@ -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;
>  }
> --
> 2.42.0
>

Re: [PATCH bpf 04/12] bpf: extract __check_reg_arg() utility function

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 19 +++++++++++++------
>  1 file changed, 13 insertions(+), 6 deletions(-)
>

Acked-by: Andrii Nakryiko <andrii@kernel.org>

[...]

Re: [PATCH bpf 05/12] bpf: extract setup_func_entry() utility function

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 87 +++++++++++++++++++++++++------------------
>  1 file changed, 51 insertions(+), 36 deletions(-)
>

LGTM, minor nit below.

Acked-by: Andrii Nakryiko <andrii@kernel.org>

> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 0576fc1ddc4d..d9513fd58c7c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9542,11 +9542,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;
>
> @@ -9556,13 +9555,56 @@ 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);
> +       if (err)
> +               goto err_out;
> +
> +       err = set_callee_state_cb(env, caller, callee, callsite);
> +       if (err)
> +               goto err_out;

given we are touching and moving this code, it might make sense to
make it a bit more succinct with this pattern:

err = copy_reference_state(...);
err = err ?: set_callee_state_cb();
if (err)
    goto err_out;


Error handling is a bit less distracting this way.

> +
> +       /* 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;
> +}
> +

[...]

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

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <awerner32@gmail.com>
> Closes: https://lore.kernel.org/bpf/CA+vRuzPChFNXmouzGG+wsy=6eMcfr1mFG0F3g7rbg-sedGKW3w@mail.gmail.com/
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h                  |   5 +
>  kernel/bpf/verifier.c                         | 257 +++++++++++-------
>  .../selftests/bpf/prog_tests/cb_refs.c        |   4 +-
>  tools/testing/selftests/bpf/progs/cb_refs.c   |   1 +
>  .../selftests/bpf/progs/exceptions_fail.c     |   2 +
>  .../bpf/progs/verifier_subprog_precision.c    |  22 +-
>  6 files changed, 183 insertions(+), 108 deletions(-)
>

Overall makes sense, but I left few questions below to try to
understand everything better. Thanks!

[...]

> +static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx);
> +
>  /* For given verifier state backtrack_insn() is called from the last insn to
>   * the first insn. Its purpose is to compute a bitmask of registers and
>   * stack slots that needs precision in the parent verifier state.
> @@ -4030,10 +4044,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
>                                         return -EFAULT;
>                                 return 0;
>                         }
> -               } else if ((bpf_helper_call(insn) &&
> -                           is_callback_calling_function(insn->imm) &&
> -                           !is_async_callback_calling_function(insn->imm)) ||
> -                          (bpf_pseudo_kfunc_call(insn) && is_callback_calling_kfunc(insn->imm))) {
> +               } else if (is_sync_callback_calling_insn(insn) && idx != subseq_idx - 1) {

can you leave a comment why we need idx != subseq_idx - 1 check?

>                         /* callback-calling helper or kfunc call, which means
>                          * we are exiting from subprog, but unlike the subprog
>                          * call handling above, we shouldn't propagate

[...]

> @@ -12176,6 +12216,21 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
>                 return -EACCES;
>         }
>
> +       /* Check the arguments */
> +       err = check_kfunc_args(env, &meta, insn_idx);
> +       if (err < 0)
> +               return err;
> +
> +       if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {

can't we use is_sync_callback_calling_kfunc() here?

> +               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> +                                        set_rbtree_add_callback_state);
> +               if (err) {
> +                       verbose(env, "kfunc %s#%d failed callback verification\n",
> +                               func_name, meta.func_id);
> +                       return err;
> +               }
> +       }
> +

[...]

> diff --git a/tools/testing/selftests/bpf/prog_tests/cb_refs.c b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> index 3bff680de16c..b5aa168889c1 100644
> --- a/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> +++ b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> @@ -21,12 +21,14 @@ void test_cb_refs(void)
>  {
>         LIBBPF_OPTS(bpf_object_open_opts, opts, .kernel_log_buf = log_buf,
>                                                 .kernel_log_size = sizeof(log_buf),
> -                                               .kernel_log_level = 1);
> +                                               .kernel_log_level = 1 | 2 | 4);

nit: 1 is redundant if 2 is specified, so just `2 | 4` ?

>         struct bpf_program *prog;
>         struct cb_refs *skel;
>         int i;
>
>         for (i = 0; i < ARRAY_SIZE(cb_refs_tests); i++) {
> +               if (!test__start_subtest(cb_refs_tests[i].prog_name))
> +                       continue;
>                 LIBBPF_OPTS(bpf_test_run_opts, run_opts,
>                         .data_in = &pkt_v4,
>                         .data_size_in = sizeof(pkt_v4),

[...]

> diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> index db6b3143338b..ead358679fe2 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> @@ -120,14 +120,12 @@ __naked int global_subprog_result_precise(void)
>  SEC("?raw_tp")
>  __success __log_level(2)
>  __msg("14: (0f) r1 += r6")
> -__msg("mark_precise: frame0: last_idx 14 first_idx 10")
> +__msg("mark_precise: frame0: last_idx 14 first_idx 9")
>  __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
>  __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
>  __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
>  __msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")
> -__msg("mark_precise: frame0: parent state regs=r0 stack=:")
> -__msg("mark_precise: frame0: last_idx 18 first_idx 0")
> -__msg("mark_precise: frame0: regs=r0 stack= before 18: (95) exit")
> +__msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")

you are right that r0 returned from bpf_loop is not r0 returned from
bpf_loop's callback, but we still have to go through callback
instructions, right? so you removed few __msg() from subprog
instruction history because it was too long a history or what? I'd
actually keep those but update that in subprog we don't need r0 to be
precise, that will make this test even clearer

>  __naked int callback_result_precise(void)
>  {
>         asm volatile (

[...]

Re: [PATCH bpf 07/12] selftests/bpf: tests for iterating callbacks

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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.
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  .../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
>

Great!

Acked-by: Andrii Nakryiko <andrii@kernel.org>

[...]

Re: [PATCH bpf 08/12] bpf: widening for callback iterators

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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);
>   ...
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  kernel/bpf/verifier.c | 24 ++++++++++++++++++++++--
>  1 file changed, 22 insertions(+), 2 deletions(-)
>

Acked-by: Andrii Nakryiko <andrii@kernel.org>

[...]

Re: [PATCH bpf 09/12] selftests/bpf: test widening for iterating callbacks

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> A test case to verify that imprecise scalars widening is applied to
> callback bodies on repetative iteration.

typo: repetitive? repeating? successive? subsequent?

>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  .../bpf/progs/verifier_iterating_callbacks.c  | 20 +++++++++++++++++++
>  1 file changed, 20 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> index fa9429f77a81..598c1e984b26 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> @@ -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];

would the test be a bit more interesting if you use loop_ctx.i here?
`return choice_arr[loop_ctx.i & 1];` ?



> +}
> +
>  static int loop_detection_cb(__u32 idx, struct num_context *ctx)
>  {
>         for (;;) {}
> --
> 2.42.0
>

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

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <eddyz87@gmail.com>
> ---
>  include/linux/bpf_verifier.h |  9 +++++++++
>  kernel/bpf/verifier.c        | 12 ++++++++++--
>  2 files changed, 19 insertions(+), 2 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 0ffb479c72d8..302f9c310de7 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -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;
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 5b8c0ebcb4f6..474af277ea54 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9680,6 +9680,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;
>  }
>
> @@ -10479,8 +10481,14 @@ 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);
> +               if (env->log.level & BPF_LOG_LEVEL2)
> +                       verbose(env, "frame%d callback_depth=%u\n",
> +                               env->cur_state->curframe, cur_func(env)->callback_depth);

btw, is this a debugging leftover or intentional? If the latter, why
is it done only for bpf_loop()? Maybe push_callback_call() be a better
place for it?

> +               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;

I guess it's actually a bit more interesting to know that we stopped
iterating because umax is reached. But I'm actually not sure whether
we should be adding these logs at all, though I don't have a strong
preference.



>                 break;
>         case BPF_FUNC_dynptr_from_mem:
>                 if (regs[BPF_REG_1].type != PTR_TO_MAP_VALUE) {
> --
> 2.42.0
>

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

[Andrii Nakryiko]

On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> 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 <eddyz87@gmail.com>
> ---
>  .../bpf/progs/verifier_iterating_callbacks.c  | 67 +++++++++++++++++++
>  1 file changed, 67 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> index 598c1e984b26..da10ce57da5e 100644
> --- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> +++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> @@ -164,4 +164,71 @@ 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 last verified exit from the program visited each
> + * callback expected number of times: one visit per callback for each
> + * top level bpf_loop call.
> + */
> +__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
> +/* Ensure that read above is the last one by checking that there are
> + * no more reads for ctx.i.
> + */
> +__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")

can't you enforce that we don't go above 111111 just by making sure to
use r1 - 111111 + 1 as an index into choice_arr()?

We can then simplify the patch set by dropping __not_msg() parts (and
can add them separately).


> +int bpf_loop_iter_limit_nested(void *unused)
> +{
> +       struct num_context ctx = { .i = 0 };
> +
> +       bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
> +       ctx.i *= 1000;
> +       bpf_loop(1, iter_limit_level1_cb, &ctx, 0);
> +       return choice_arr[ctx.i % 2];
> +}
> +
>  char _license[] SEC("license") = "GPL";
> --
> 2.42.0
>

Re: [PATCH bpf 02/12] selftests/bpf: track string payload offset as scalar in strobemeta

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:46 -0500, Andrii Nakryiko wrote:
> On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > This change prepares strobemeta for update in callbakcs verification
> 
> typo: callbacks
> 
> > logic. To allow bpf_loop() verification converge when multiple
> > callback itreations are considered:
> 
> typo: iterations

[:facepalm:], I'll fix it.

Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:46 -0500, Andrii Nakryiko wrote:
[...]
> > 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 for verifier it merely represents 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;
> >   ...
> 
> would this still happen if you use an obfuscated zero initializer for i?
> 
> int zero = 0; /* global var */
> 
> ...
> 
> 
> for (i = zero; i < 1000; i++) {
>      ...
> }

In that case it fails with jump limit.
Mechanism for states explosion is similar, as far as I understand.

Re: [PATCH bpf 05/12] bpf: extract setup_func_entry() utility function

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:46 -0500, Andrii Nakryiko wrote:
[...]
> > +       /* Transfer references to the callee */
> > +       err = copy_reference_state(callee, caller);
> > +       if (err)
> > +               goto err_out;
> > +
> > +       err = set_callee_state_cb(env, caller, callee, callsite);
> > +       if (err)
> > +               goto err_out;
> 
> given we are touching and moving this code, it might make sense to
> make it a bit more succinct with this pattern:
> 
> err = copy_reference_state(...);
> err = err ?: set_callee_state_cb();
> if (err)
>     goto err_out;
> 
> 
> Error handling is a bit less distracting this way.

Will do.

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

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:46 -0500, Andrii Nakryiko wrote:
[...]
> > +static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx);
> > +
> >  /* For given verifier state backtrack_insn() is called from the last insn to
> >   * the first insn. Its purpose is to compute a bitmask of registers and
> >   * stack slots that needs precision in the parent verifier state.
> > @@ -4030,10 +4044,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> >                                         return -EFAULT;
> >                                 return 0;
> >                         }
> > -               } else if ((bpf_helper_call(insn) &&
> > -                           is_callback_calling_function(insn->imm) &&
> > -                           !is_async_callback_calling_function(insn->imm)) ||
> > -                          (bpf_pseudo_kfunc_call(insn) && is_callback_calling_kfunc(insn->imm))) {
> > +               } else if (is_sync_callback_calling_insn(insn) && idx != subseq_idx - 1) {
> 
> can you leave a comment why we need idx != subseq_idx - 1 check?

This check is needed to make sure that we on the arc from callback
return to callback calling function, I'll extend the comment below.

> >                         /* callback-calling helper or kfunc call, which means
> >                          * we are exiting from subprog, but unlike the subprog
> >                          * call handling above, we shouldn't propagate
> 
> [...]
> 
> > @@ -12176,6 +12216,21 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
> >                 return -EACCES;
> >         }
> > 
> > +       /* Check the arguments */
> > +       err = check_kfunc_args(env, &meta, insn_idx);
> > +       if (err < 0)
> > +               return err;
> > +
> > +       if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {
> 
> can't we use is_sync_callback_calling_kfunc() here?

No, because it uses 'set_rbtree_add_callback_state' as a parameter,
specific to rbtree_add, not just any kfunc.

> > +               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> > +                                        set_rbtree_add_callback_state);
> > +               if (err) {
> > +                       verbose(env, "kfunc %s#%d failed callback verification\n",
> > +                               func_name, meta.func_id);
> > +                       return err;
> > +               }
> > +       }
> > +

[...]

> > diff --git a/tools/testing/selftests/bpf/prog_tests/cb_refs.c b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> > index 3bff680de16c..b5aa168889c1 100644
> > --- a/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> > +++ b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> > @@ -21,12 +21,14 @@ void test_cb_refs(void)
> >  {
> >         LIBBPF_OPTS(bpf_object_open_opts, opts, .kernel_log_buf = log_buf,
> >                                                 .kernel_log_size = sizeof(log_buf),
> > -                                               .kernel_log_level = 1);
> > +                                               .kernel_log_level = 1 | 2 | 4);
> 
> nit: 1 is redundant if 2 is specified, so just `2 | 4` ?

This is a leftover, sorry, I'll remove changes to cb_refs.c.

[...]

> > diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> > index db6b3143338b..ead358679fe2 100644
> > --- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> > +++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> > @@ -120,14 +120,12 @@ __naked int global_subprog_result_precise(void)
> >  SEC("?raw_tp")
> >  __success __log_level(2)
> >  __msg("14: (0f) r1 += r6")
> > -__msg("mark_precise: frame0: last_idx 14 first_idx 10")
> > +__msg("mark_precise: frame0: last_idx 14 first_idx 9")
> >  __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
> >  __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
> >  __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
> >  __msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")
> > -__msg("mark_precise: frame0: parent state regs=r0 stack=:")
> > -__msg("mark_precise: frame0: last_idx 18 first_idx 0")
> > -__msg("mark_precise: frame0: regs=r0 stack= before 18: (95) exit")
> > +__msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")
> 
> you are right that r0 returned from bpf_loop is not r0 returned from
> bpf_loop's callback, but we still have to go through callback
> instructions, right?

Should we? We are looking to make r0 precise, but what are the rules
for propagating that across callback boundary?
For bpf_loop() and for bpf_for_each_map_elem() that would be marking
r0 inside callback as precise, but in general that is callback specific.

In a separate discussion with you and Alexei you mentioned that you
are going to send a patch-set that would force all r0 precise on exit,
which would cover current situation. Imo, it would make sense to wait
for that patch-set, as it would be simpler than changes in
backtrack_insn(), wdyt?

> so you removed few __msg() from subprog
> instruction history because it was too long a history or what? I'd
> actually keep those but update that in subprog we don't need r0 to be
> precise, that will make this test even clearer
> 
> >  __naked int callback_result_precise(void)

Here is relevant log fragment:

14: (0f) r1 += r6
mark_precise: frame0: last_idx 14 first_idx 9 subseq_idx -1 
mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7
mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4
mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4
mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0
mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop#181
15: R1_w=map_value(off=0,ks=4,vs=16,smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))
    R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))
15: (61) r0 = *(u32 *)(r1 +0)         ; R0_w=scalar(smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
                                        R1_w=map_value(off=0,ks=4,vs=16,smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))
16: (95) exit

Re: [PATCH bpf 09/12] selftests/bpf: test widening for iterating callbacks

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
> On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > A test case to verify that imprecise scalars widening is applied to
> > callback bodies on repetative iteration.
> 
> typo: repetitive? repeating? successive? subsequent?

I'll configure spell-checking, I promise.

[...]
> > +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];
> 
> would the test be a bit more interesting if you use loop_ctx.i here?
> `return choice_arr[loop_ctx.i & 1];` ? 

It would force precision for 'loop_ctx.i', precise values are not widened.

> 
> > +}
> > +

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

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
[...]
> > @@ -10479,8 +10481,14 @@ 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);
> > +               if (env->log.level & BPF_LOG_LEVEL2)
> > +                       verbose(env, "frame%d callback_depth=%u\n",
> > +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> 
> btw, is this a debugging leftover or intentional? If the latter, why
> is it done only for bpf_loop()? Maybe push_callback_call() be a better
> place for it?

Intentional...

> 
> > +               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;
> 
> I guess it's actually a bit more interesting to know that we stopped
> iterating because umax is reached. But I'm actually not sure whether
> we should be adding these logs at all, though I don't have a strong
> preference.

... it is not obvious to infer current depth looking at the log, so I
think something should be printed. Note about stopped iteration sounds
good, and it could be placed here, not in the push_callback_call(), e.g.:

               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, "bpf_loop iteration limit reached\n");
               }

wdyt?

Re: [PATCH bpf 11/12] selftests/bpf: add __not_msg annotation for test_loader based tests

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:45 -0500, Andrii Nakryiko wrote:
[...]
> I think this implementation has an undesired surprising behavior.
> Imagine you have a log like this:
> 
> A
> C
> D
> B
> 
> 
> And you specify
> 
> __msg("A")
> __nomsg("B")
> __msg("C")
> __msg("D")
> __msg("B")
> 
> Log matches the spec, right? But your implementation will eagerly reject it.
> 
> I think you can implement more coherent behavior if you only strstr()
> __msg() specs, skipping __nomsg() first. But on each __msg one, if
> successful, you go back and validate that there are no matches for all
> __nomsg() specs that you skipped, taking into account matched
> positions for current __msg() and last __msg() (or the start of the
> log, of course).
> 
> Not sure if I explained clearly, but the idea is to postpone __nomsg()
> until we anchor ourselves between two __msg()s. And beginning/end of
> verifier log are two other anchoring positions.

Yes, makes total sense, thank you for spotting it. I can fix this and
submit this patch as an unrelated change or just drop it, what would
you prefer?

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

[Eduard Zingerman]

On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
[...]
> > +SEC("?raw_tp")
> > +__success __log_level(2)
> > +/* Check that last verified exit from the program visited each
> > + * callback expected number of times: one visit per callback for each
> > + * top level bpf_loop call.
> > + */
> > +__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
> > +/* Ensure that read above is the last one by checking that there are
> > + * no more reads for ctx.i.
> > + */
> > +__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")
> 
> can't you enforce that we don't go above 111111 just by making sure to
> use r1 - 111111 + 1 as an index into choice_arr()?
> 
> We can then simplify the patch set by dropping __not_msg() parts (and
> can add them separately).

Well, r1 could be 0 as well, so idx would be out of bounds.
But I like the idea, it is possible to check that r1 is either 00000,
100000, ..., 111111 and do something unsafe otherwise.
Thank you. I'll drop __not_msg() then.

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

[Andrii Nakryiko]

On Fri, Nov 17, 2023 at 1:52 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 11:46 -0500, Andrii Nakryiko wrote:
> [...]
> > > +static bool is_callback_iter_next(struct bpf_verifier_env *env, int insn_idx);
> > > +
> > >  /* For given verifier state backtrack_insn() is called from the last insn to
> > >   * the first insn. Its purpose is to compute a bitmask of registers and
> > >   * stack slots that needs precision in the parent verifier state.
> > > @@ -4030,10 +4044,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
> > >                                         return -EFAULT;
> > >                                 return 0;
> > >                         }
> > > -               } else if ((bpf_helper_call(insn) &&
> > > -                           is_callback_calling_function(insn->imm) &&
> > > -                           !is_async_callback_calling_function(insn->imm)) ||
> > > -                          (bpf_pseudo_kfunc_call(insn) && is_callback_calling_kfunc(insn->imm))) {
> > > +               } else if (is_sync_callback_calling_insn(insn) && idx != subseq_idx - 1) {
> >
> > can you leave a comment why we need idx != subseq_idx - 1 check?
>
> This check is needed to make sure that we on the arc from callback
> return to callback calling function, I'll extend the comment below.

great, thanks

>
> > >                         /* callback-calling helper or kfunc call, which means
> > >                          * we are exiting from subprog, but unlike the subprog
> > >                          * call handling above, we shouldn't propagate
> >
> > [...]
> >
> > > @@ -12176,6 +12216,21 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
> > >                 return -EACCES;
> > >         }
> > >
> > > +       /* Check the arguments */
> > > +       err = check_kfunc_args(env, &meta, insn_idx);
> > > +       if (err < 0)
> > > +               return err;
> > > +
> > > +       if (meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {
> >
> > can't we use is_sync_callback_calling_kfunc() here?
>
> No, because it uses 'set_rbtree_add_callback_state' as a parameter,
> specific to rbtree_add, not just any kfunc.
>

ah, ok, never mind then

> > > +               err = push_callback_call(env, insn, insn_idx, meta.subprogno,
> > > +                                        set_rbtree_add_callback_state);
> > > +               if (err) {
> > > +                       verbose(env, "kfunc %s#%d failed callback verification\n",
> > > +                               func_name, meta.func_id);
> > > +                       return err;
> > > +               }
> > > +       }
> > > +
>
> [...]
>
> > > diff --git a/tools/testing/selftests/bpf/prog_tests/cb_refs.c b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> > > index 3bff680de16c..b5aa168889c1 100644
> > > --- a/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> > > +++ b/tools/testing/selftests/bpf/prog_tests/cb_refs.c
> > > @@ -21,12 +21,14 @@ void test_cb_refs(void)
> > >  {
> > >         LIBBPF_OPTS(bpf_object_open_opts, opts, .kernel_log_buf = log_buf,
> > >                                                 .kernel_log_size = sizeof(log_buf),
> > > -                                               .kernel_log_level = 1);
> > > +                                               .kernel_log_level = 1 | 2 | 4);
> >
> > nit: 1 is redundant if 2 is specified, so just `2 | 4` ?
>
> This is a leftover, sorry, I'll remove changes to cb_refs.c.
>
> [...]
>
> > > diff --git a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> > > index db6b3143338b..ead358679fe2 100644
> > > --- a/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> > > +++ b/tools/testing/selftests/bpf/progs/verifier_subprog_precision.c
> > > @@ -120,14 +120,12 @@ __naked int global_subprog_result_precise(void)
> > >  SEC("?raw_tp")
> > >  __success __log_level(2)
> > >  __msg("14: (0f) r1 += r6")
> > > -__msg("mark_precise: frame0: last_idx 14 first_idx 10")
> > > +__msg("mark_precise: frame0: last_idx 14 first_idx 9")
> > >  __msg("mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7")
> > >  __msg("mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4")
> > >  __msg("mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4")
> > >  __msg("mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0")
> > > -__msg("mark_precise: frame0: parent state regs=r0 stack=:")
> > > -__msg("mark_precise: frame0: last_idx 18 first_idx 0")
> > > -__msg("mark_precise: frame0: regs=r0 stack= before 18: (95) exit")
> > > +__msg("mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop")
> >
> > you are right that r0 returned from bpf_loop is not r0 returned from
> > bpf_loop's callback, but we still have to go through callback
> > instructions, right?
>
> Should we? We are looking to make r0 precise, but what are the rules
> for propagating that across callback boundary?

rules are that r0 in parent frame stays marked as precise, then when
we go into child (subprog) frame, we clear r0 *for that frame*, but we
still need to process callback instruction validation history to
eventually get back to caller instructions again

> For bpf_loop() and for bpf_for_each_map_elem() that would be marking
> r0 inside callback as precise, but in general that is callback specific.
>
> In a separate discussion with you and Alexei you mentioned that you
> are going to send a patch-set that would force all r0 precise on exit,
> which would cover current situation. Imo, it would make sense to wait
> for that patch-set, as it would be simpler than changes in
> backtrack_insn(), wdyt?

this is a completely different issue

>
> > so you removed few __msg() from subprog
> > instruction history because it was too long a history or what? I'd
> > actually keep those but update that in subprog we don't need r0 to be
> > precise, that will make this test even clearer
> >
> > >  __naked int callback_result_precise(void)
>
> Here is relevant log fragment:
>
> 14: (0f) r1 += r6
> mark_precise: frame0: last_idx 14 first_idx 9 subseq_idx -1
> mark_precise: frame0: regs=r6 stack= before 13: (bf) r1 = r7
> mark_precise: frame0: regs=r6 stack= before 12: (27) r6 *= 4
> mark_precise: frame0: regs=r6 stack= before 11: (25) if r6 > 0x3 goto pc+4
> mark_precise: frame0: regs=r6 stack= before 10: (bf) r6 = r0
> mark_precise: frame0: regs=r0 stack= before 9: (85) call bpf_loop#181
> 15: R1_w=map_value(off=0,ks=4,vs=16,smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))
>     R6_w=scalar(smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))
> 15: (61) r0 = *(u32 *)(r1 +0)         ; R0_w=scalar(smin=0,smax=umax=4294967295,var_off=(0x0; 0xffffffff))
>                                         R1_w=map_value(off=0,ks=4,vs=16,smin=smin32=0,smax=umax=smax32=umax32=12,var_off=(0x0; 0xc))
> 16: (95) exit
>

So I assume this is the case where bpf_loop callback is not executed
at all, right? What I'm asking is to keep log expectation where
callback *is* executed once, so that we can validate that r0 in the
caller is not propagated to callback through callback_calling helpers
(like bpf_loop).

Re: [PATCH bpf 09/12] selftests/bpf: test widening for iterating callbacks

[Andrii Nakryiko]

On Fri, Nov 17, 2023 at 1:53 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
> > On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > A test case to verify that imprecise scalars widening is applied to
> > > callback bodies on repetative iteration.
> >
> > typo: repetitive? repeating? successive? subsequent?
>
> I'll configure spell-checking, I promise.

no worries, I only notice it because gmail highlights it. I was rather
wondering if "repetitive iteration" is the right way to explain this.

>
> [...]
> > > +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];
> >
> > would the test be a bit more interesting if you use loop_ctx.i here?
> > `return choice_arr[loop_ctx.i & 1];` ?
>
> It would force precision for 'loop_ctx.i', precise values are not widened.

ah, right, ok

>
> >
> > > +}
> > > +
>
>

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

[Andrii Nakryiko]

On Fri, Nov 17, 2023 at 1:53 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
> [...]
> > > @@ -10479,8 +10481,14 @@ 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);
> > > +               if (env->log.level & BPF_LOG_LEVEL2)
> > > +                       verbose(env, "frame%d callback_depth=%u\n",
> > > +                               env->cur_state->curframe, cur_func(env)->callback_depth);
> >
> > btw, is this a debugging leftover or intentional? If the latter, why
> > is it done only for bpf_loop()? Maybe push_callback_call() be a better
> > place for it?
>
> Intentional...
>
> >
> > > +               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;
> >
> > I guess it's actually a bit more interesting to know that we stopped
> > iterating because umax is reached. But I'm actually not sure whether
> > we should be adding these logs at all, though I don't have a strong
> > preference.
>
> ... it is not obvious to infer current depth looking at the log, so I
> think something should be printed. Note about stopped iteration sounds
> good, and it could be placed here, not in the push_callback_call(), e.g.:
>
>                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, "bpf_loop iteration limit reached\n");
>                }
>
> wdyt?
>
>

Sure, I don't mind.

Re: [PATCH bpf 11/12] selftests/bpf: add __not_msg annotation for test_loader based tests

[Andrii Nakryiko]

On Fri, Nov 17, 2023 at 1:53 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 11:45 -0500, Andrii Nakryiko wrote:
> [...]
> > I think this implementation has an undesired surprising behavior.
> > Imagine you have a log like this:
> >
> > A
> > C
> > D
> > B
> >
> >
> > And you specify
> >
> > __msg("A")
> > __nomsg("B")
> > __msg("C")
> > __msg("D")
> > __msg("B")
> >
> > Log matches the spec, right? But your implementation will eagerly reject it.
> >
> > I think you can implement more coherent behavior if you only strstr()
> > __msg() specs, skipping __nomsg() first. But on each __msg one, if
> > successful, you go back and validate that there are no matches for all
> > __nomsg() specs that you skipped, taking into account matched
> > positions for current __msg() and last __msg() (or the start of the
> > log, of course).
> >
> > Not sure if I explained clearly, but the idea is to postpone __nomsg()
> > until we anchor ourselves between two __msg()s. And beginning/end of
> > verifier log are two other anchoring positions.
>
> Yes, makes total sense, thank you for spotting it. I can fix this and
> submit this patch as an unrelated change or just drop it, what would
> you prefer?
>
>

I think it's useful in general, I believe I had few cases where this
would be helpful. So submitting separately makes sense. But I think
this patch set doesn't need it if we can validate logic in last patch
without relying on this feature.

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

[Andrii Nakryiko]

On Fri, Nov 17, 2023 at 1:53 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 11:47 -0500, Andrii Nakryiko wrote:
> [...]
> > > +SEC("?raw_tp")
> > > +__success __log_level(2)
> > > +/* Check that last verified exit from the program visited each
> > > + * callback expected number of times: one visit per callback for each
> > > + * top level bpf_loop call.
> > > + */
> > > +__msg("r1 = *(u64 *)(r10 -16)       ; R1_w=111111 R10=fp0 fp-16=111111")
> > > +/* Ensure that read above is the last one by checking that there are
> > > + * no more reads for ctx.i.
> > > + */
> > > +__not_msg("r1 = *(u64 *)(r10 -16)      ; R1_w=")
> >
> > can't you enforce that we don't go above 111111 just by making sure to
> > use r1 - 111111 + 1 as an index into choice_arr()?
> >
> > We can then simplify the patch set by dropping __not_msg() parts (and
> > can add them separately).
>
> Well, r1 could be 0 as well, so idx would be out of bounds.
> But I like the idea, it is possible to check that r1 is either 00000,
> 100000, ..., 111111 and do something unsafe otherwise.

then why not `return choice_arr[r <= 111111 ? (r & 1) : -1];` or
something along those lines?

> Thank you. I'll drop __not_msg() then.

yep, thanks

>
>

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

[Eduard Zingerman]

On Fri, 2023-11-17 at 15:27 -0500, Andrii Nakryiko wrote:
[...]
> > > you are right that r0 returned from bpf_loop is not r0 returned from
> > > bpf_loop's callback, but we still have to go through callback
> > > instructions, right?
> > 
> > Should we? We are looking to make r0 precise, but what are the rules
> > for propagating that across callback boundary?
> 
> rules are that r0 in parent frame stays marked as precise, then when
> we go into child (subprog) frame, we clear r0 *for that frame*,
[...]
> So I assume this is the case where bpf_loop callback is not executed
> at all, right? What I'm asking is to keep log expectation where
> callback *is* executed once, so that we can validate that r0 in the
> caller is not propagated to callback through callback_calling helpers
> (like bpf_loop).

I see, I'll extend the __msg matching sequence.

I'll also extend matching in the following two tests:
- parent_callee_saved_reg_precise_with_callback
- parent_stack_slot_precise_with_callback

To check that r6-r9 and fp[*] precision is propagated through callback body.
 

Re: [PATCH bpf 11/12] selftests/bpf: add __not_msg annotation for test_loader based tests

[Eduard Zingerman]

On Fri, 2023-11-17 at 15:31 -0500, Andrii Nakryiko wrote:
[...]
> > > I think this implementation has an undesired surprising behavior.
> > > Imagine you have a log like this:
> > > 
> > > A
> > > C
> > > D
> > > B
> > > 
> > > And you specify
> > > 
> > > __msg("A")
> > > __nomsg("B")
> > > __msg("C")
> > > __msg("D")
> > > __msg("B")
[...]
> I think it's useful in general, I believe I had few cases where this
> would be helpful. So submitting separately makes sense. But I think
> this patch set doesn't need it if we can validate logic in last patch
> without relying on this feature.

Ok, will do it separately. While at it can also add two more features:
- __msg_next, again mimicking FileCheck [0], which would require match to
  be on a line subsequent to previous match;
- __msg_re, with support for regular expressions (using [1]).

[0] https://llvm.org/docs/CommandGuide/FileCheck.html
[1] https://www.gnu.org/software/libc/manual/html_node/Regular-Expressions.html

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

[Eduard Zingerman]

On Fri, 2023-11-17 at 15:32 -0500, Andrii Nakryiko wrote:
[...]
> > Well, r1 could be 0 as well, so idx would be out of bounds.
> > But I like the idea, it is possible to check that r1 is either 00000,
> > 100000, ..., 111111 and do something unsafe otherwise.
> 
> then why not `return choice_arr[r <= 111111 ? (r & 1) : -1];` or
> something along those lines?

In theory, invalid value might be 100002 or something similar.
I'll try writing down something more precise, if that would look too
ugly would resort to the comparison that you suggest.

Re: [PATCH bpf 11/12] selftests/bpf: add __not_msg annotation for test_loader based tests

[Alexei Starovoitov]

On Fri, Nov 17, 2023 at 1:10 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 15:31 -0500, Andrii Nakryiko wrote:
> [...]
> > > > I think this implementation has an undesired surprising behavior.
> > > > Imagine you have a log like this:
> > > >
> > > > A
> > > > C
> > > > D
> > > > B
> > > >
> > > > And you specify
> > > >
> > > > __msg("A")
> > > > __nomsg("B")
> > > > __msg("C")
> > > > __msg("D")
> > > > __msg("B")
> [...]
> > I think it's useful in general, I believe I had few cases where this
> > would be helpful. So submitting separately makes sense. But I think
> > this patch set doesn't need it if we can validate logic in last patch
> > without relying on this feature.
>
> Ok, will do it separately. While at it can also add two more features:
> - __msg_next, again mimicking FileCheck [0], which would require match to
>   be on a line subsequent to previous match;
> - __msg_re, with support for regular expressions (using [1]).
>
> [0] https://llvm.org/docs/CommandGuide/FileCheck.html
> [1] https://www.gnu.org/software/libc/manual/html_node/Regular-Expressions.html

So far this patch set didn't have conflicts with bpf-next and
we need to land it in the bpf tree and backport later,
so pls minimize the changes.
_nomsg, _msg* extensions are certainly useful, but let's add them
later via bpf-next when trees converge.

Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Alexei Starovoitov]

On Wed, Nov 15, 2023 at 6:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> The patch a few patches from this one changes logic for callbacks
> handling.

That's a wordsmith level 10. I'm far below this level.
Could you please rephrase it? 'The next patch changes ...' or something?

Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Eduard Zingerman]

On Fri, 2023-11-17 at 13:38 -0800, Alexei Starovoitov wrote:
> On Wed, Nov 15, 2023 at 6:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > The patch a few patches from this one changes logic for callbacks
> > handling.
> 
> That's a wordsmith level 10. I'm far below this level.
> Could you please rephrase it? 'The next patch changes ...' or something?

This is patch #3, and actual changes are in patch #6, I can change it to:

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

Would that work?

Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Alexei Starovoitov]

On Fri, Nov 17, 2023 at 1:43 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 13:38 -0800, Alexei Starovoitov wrote:
> > On Wed, Nov 15, 2023 at 6:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > The patch a few patches from this one changes logic for callbacks
> > > handling.
> >
> > That's a wordsmith level 10. I'm far below this level.
> > Could you please rephrase it? 'The next patch changes ...' or something?
>
> This is patch #3, and actual changes are in patch #6, I can change it to:
>
>   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.
>   ...
>
> Would that work?

... or just drop it. The commit log typically describes only what's
happening in this commit or links to prior commits.
Future commit references are unusual.

Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Eduard Zingerman]

On Fri, 2023-11-17 at 13:47 -0800, Alexei Starovoitov wrote:
[...]
> > This is patch #3, and actual changes are in patch #6, I can change it to:
> > 
> >   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.
> >   ...
> > 
> > Would that work?
> 
> ... or just drop it. The commit log typically describes only what's
> happening in this commit or links to prior commits.
> Future commit references are unusual.

But there needs to be some justification.
Since this is not a test, maybe move it after patch #6 and refer to a
changes from a previous commit?

Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Alexei Starovoitov]

On Fri, Nov 17, 2023 at 1:50 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 13:47 -0800, Alexei Starovoitov wrote:
> [...]
> > > This is patch #3, and actual changes are in patch #6, I can change it to:
> > >
> > >   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.
> > >   ...
> > >
> > > Would that work?
> >
> > ... or just drop it. The commit log typically describes only what's
> > happening in this commit or links to prior commits.
> > Future commit references are unusual.
>
> But there needs to be some justification.
> Since this is not a test, maybe move it after patch #6 and refer to a
> changes from a previous commit?

Better to keep it here to avoid breaking this test.
Use the above wording then.