Re: [PATCH bpf 5/6] selftests/bpf: Add tests for the indirect jump edge limit

[Anton Protopopov <a.s.protopopov@gmail.com>]

On 26/09/09 10:40PM, Daniel Borkmann wrote:
> Build programs whose gotox instructions are their own jump table targets,
> which makes the edge count quadratic.
> 
>   # LDLIBS=-static PKG_CONFIG='pkg-config --static' ./vmtest.sh -- ./test_progs -t bpf_insn_array
>   [...]
>   #24/10   bpf_insn_array/too-many-gotox-edges:OK
>   #24/11   bpf_insn_array/gotox-edges-at-limit:OK
>   #24/12   bpf_insn_array/gotox-edges-across-subprogs:OK
>   #24      bpf_insn_array:OK
>   Summary: 1/12 PASSED, 0 SKIPPED, 0/0 FAILED
> 
> Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
> ---
>  .../selftests/bpf/prog_tests/bpf_insn_array.c | 266 ++++++++++++++++++
>  1 file changed, 266 insertions(+)
> 
> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> index 0222a9a5d076..c69d44cd4607 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_insn_array.c
> @@ -453,6 +453,263 @@ static void check_bpf_no_lookup(void)
>  	close(map_fd);
>  }
>  
> +#define GOTOX_CNT_AT_LIMIT	1000
> +#define GOTOX_LOG_SZ		(256 * 1024)
> +
> +static const char gotox_limit_msg[] =
> +	"number of indirect jump edges in the program exceeds";
> +
> +static int gotox_jt_create(__u32 first_gotox, __u32 gotox_cnt)
> +{
> +	/* the run of gotox itself, plus the exit block right after it */
> +	const __u32 jt_cnt = gotox_cnt + 1;
> +	struct bpf_insn_array_value val = {};
> +	int map_fd;
> +	__u32 i;
> +
> +	map_fd = map_create(BPF_MAP_TYPE_INSN_ARRAY, jt_cnt);
> +	if (!ASSERT_GE(map_fd, 0, "map_create"))
> +		return map_fd;
> +
> +	for (i = 0; i < jt_cnt; i++) {
> +		val.orig_off = first_gotox + i;
> +		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0,
> +			       "bpf_map_update_elem"))
> +			goto err;
> +	}
> +
> +	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
> +		goto err;
> +
> +	return map_fd;
> +err:
> +	close(map_fd);
> +	return -1;
> +}
> +
> +static int gotox_prog_load(struct bpf_insn *insns, __u32 insn_cnt,
> +			   int *fd_array, __u32 fd_array_cnt, char *log)
> +{
> +	LIBBPF_OPTS(bpf_prog_load_opts, opts);
> +	int prog_fd;
> +
> +	log[0] = 0;
> +	opts.fd_array = fd_array;
> +	opts.fd_array_cnt = fd_array_cnt;
> +	opts.log_buf = log;
> +	opts.log_size = GOTOX_LOG_SZ;
> +	opts.log_level = 1;
> +
> +	prog_fd = bpf_prog_load(BPF_PROG_TYPE_XDP, NULL, "GPL", insns, insn_cnt, &opts);
> +	if (prog_fd >= 0) {
> +		close(prog_fd);
> +		return 0;
> +	}
> +	return prog_fd;
> +}
> +
> +/* Fill in 'r1 = 0; gotox_cnt x gotox r1' at 'insns'. */
> +static void gotox_run_fill(struct bpf_insn *insns, __u32 gotox_cnt)
> +{
> +	__u32 i;
> +
> +	insns[0] = BPF_MOV64_IMM(BPF_REG_1, 0);
> +	for (i = 1; i <= gotox_cnt; i++)
> +		insns[i] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +}
> +
> +static void check_gotox_limit_hit(const char *log, int err)
> +{
> +	ASSERT_EQ(err, -E2BIG, "program should have been rejected");
> +	ASSERT_HAS_SUBSTR(log, gotox_limit_msg, "verifier log");
> +}
> +
> +static bool try_load_gotox_prog(__u32 gotox_cnt, char *log, int *err)
> +{
> +	const __u32 insn_cnt = gotox_cnt + 3;
> +	struct bpf_insn *insns;
> +	bool attempted = false;
> +	int map_fd;
> +
> +	insns = calloc(insn_cnt, sizeof(*insns));
> +	if (!ASSERT_OK_PTR(insns, "calloc insns"))
> +		return false;
> +
> +	gotox_run_fill(insns, gotox_cnt);
> +	insns[gotox_cnt + 1] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[gotox_cnt + 2] = BPF_EXIT_INSN();
> +
> +	map_fd = gotox_jt_create(1, gotox_cnt);
> +	if (map_fd < 0)
> +		goto free_insns;
> +
> +	*err = gotox_prog_load(insns, insn_cnt, &map_fd, 1, log);
> +	close(map_fd);
> +	attempted = true;
> +free_insns:
> +	free(insns);
> +	return attempted;
> +}
> +
> +/*
> + * The extra exit target in the jump table makes for gotox_cnt * (gotox_cnt
> + * + 1) edges, hence the program is over the limit by gotox_cnt edges.
> + */
> +static void check_too_many_gotox_edges(void)
> +{
> +	const __u32 gotox_cnt = GOTOX_CNT_AT_LIMIT;
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	if (try_load_gotox_prog(gotox_cnt, log, &err))
> +		check_gotox_limit_hit(log, err);
> +
> +	free(log);
> +}
> +
> +/*
> + * A chain of blocks, where block k loads jt[k] and jumps to it. The jump
> + * table holds the starts of the blocks that follow plus the exit block,
> + * which is gotox_cnt targets for gotox_cnt gotox, so the program sits
> + * exactly at the limit and must still load.
> + */
> +#define GOTOX_BLOCK_SZ		4
> +
> +static void gotox_chain_fill(struct bpf_insn *insns, __u32 gotox_cnt)
> +{
> +	struct bpf_insn *at;
> +	__u32 k;
> +
> +	for (k = 0; k < gotox_cnt; k++) {
> +		at = insns + k * GOTOX_BLOCK_SZ;
> +
> +		/* r1 = &jt[0], by index 0 into fd_array */
> +		at[0] = (struct bpf_insn) {
> +			.code = BPF_LD | BPF_DW | BPF_IMM,
> +			.dst_reg = BPF_REG_1,
> +			.src_reg = BPF_PSEUDO_MAP_IDX_VALUE,
> +			.imm = 0,
> +		};
> +		at[1] = (struct bpf_insn) { .imm = 0 };
> +		at[2] = BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_1, k * 8);
> +		at[3] = BPF_RAW_INSN(BPF_JMP | BPF_JA | BPF_X, BPF_REG_1, 0, 0, 0);
> +	}
> +
> +	insns[gotox_cnt * GOTOX_BLOCK_SZ] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[gotox_cnt * GOTOX_BLOCK_SZ + 1] = BPF_EXIT_INSN();
> +}
> +
> +static int gotox_chain_jt_create(__u32 gotox_cnt)
> +{
> +	struct bpf_insn_array_value val = {};
> +	int map_fd;
> +	__u32 i;
> +
> +	map_fd = map_create(BPF_MAP_TYPE_INSN_ARRAY, gotox_cnt);
> +	if (!ASSERT_GE(map_fd, 0, "map_create"))
> +		return map_fd;
> +
> +	for (i = 0; i < gotox_cnt; i++) {
> +		val.orig_off = (i + 1) * GOTOX_BLOCK_SZ;
> +		if (!ASSERT_EQ(bpf_map_update_elem(map_fd, &i, &val, 0), 0,
> +			       "bpf_map_update_elem"))
> +			goto err;
> +	}
> +
> +	if (!ASSERT_EQ(bpf_map_freeze(map_fd), 0, "bpf_map_freeze"))
> +		goto err;
> +
> +	return map_fd;
> +err:
> +	close(map_fd);
> +	return -1;
> +}
> +
> +static void check_gotox_edges_at_limit(void)
> +{
> +	const __u32 gotox_cnt = GOTOX_CNT_AT_LIMIT;
> +	const __u32 insn_cnt = gotox_cnt * GOTOX_BLOCK_SZ + 2;
> +	struct bpf_insn *insns;
> +	char *log;
> +	int map_fd, err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	insns = calloc(insn_cnt, sizeof(*insns));
> +	if (!ASSERT_OK_PTR(insns, "calloc insns"))
> +		goto free_log;
> +
> +	gotox_chain_fill(insns, gotox_cnt);
> +
> +	map_fd = gotox_chain_jt_create(gotox_cnt);
> +	if (map_fd < 0)
> +		goto free_insns;
> +
> +	err = gotox_prog_load(insns, insn_cnt, &map_fd, 1, log);
> +	close(map_fd);
> +
> +	if (!ASSERT_OK(err, "program at the edge limit should load"))
> +		fprintf(stderr, "verifier log: %s\n", log);
> +
> +free_insns:
> +	free(insns);
> +free_log:
> +	free(log);
> +}
> +
> +static void check_gotox_edges_across_subprogs(void)
> +{
> +	const __u32 gotox_cnt = GOTOX_CNT_AT_LIMIT * 3 / 4;
> +	const __u32 sub_start = gotox_cnt + 3;
> +	const __u32 insn_cnt = 2 * (gotox_cnt + 3);
> +	int map_fd[2] = { -1, -1 };
> +	struct bpf_insn *insns;
> +	char *log;
> +	int err;
> +
> +	log = calloc(1, GOTOX_LOG_SZ);
> +	if (!ASSERT_OK_PTR(log, "calloc log"))
> +		return;
> +
> +	insns = calloc(insn_cnt, sizeof(*insns));
> +	if (!ASSERT_OK_PTR(insns, "calloc insns"))
> +		goto free_log;
> +
> +	gotox_run_fill(insns, gotox_cnt);
> +	insns[gotox_cnt + 1] = BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0,
> +					    BPF_PSEUDO_CALL, 0,
> +					    sub_start - (gotox_cnt + 1) - 1);
> +	insns[gotox_cnt + 2] = BPF_EXIT_INSN();
> +
> +	gotox_run_fill(insns + sub_start, gotox_cnt);
> +	insns[sub_start + gotox_cnt + 1] = BPF_MOV64_IMM(BPF_REG_0, 0);
> +	insns[sub_start + gotox_cnt + 2] = BPF_EXIT_INSN();
> +
> +	map_fd[0] = gotox_jt_create(1, gotox_cnt);
> +	if (map_fd[0] < 0)
> +		goto free_insns;
> +	map_fd[1] = gotox_jt_create(sub_start + 1, gotox_cnt);
> +	if (map_fd[1] < 0)
> +		goto close_maps;
> +
> +	err = gotox_prog_load(insns, insn_cnt, map_fd, 2, log);
> +	check_gotox_limit_hit(log, err);
> +
> +close_maps:
> +	close(map_fd[0]);
> +	close(map_fd[1]);
> +free_insns:
> +	free(insns);
> +free_log:
> +	free(log);
> +}
> +
>  static void check_bpf_side(void)
>  {
>  	check_bpf_no_lookup();
> @@ -490,6 +747,15 @@ static void __test_bpf_insn_array(void)
>  
>  	if (test__start_subtest("bpf-side-ops"))
>  		check_bpf_side();
> +
> +	if (test__start_subtest("too-many-gotox-edges"))
> +		check_too_many_gotox_edges();
> +
> +	if (test__start_subtest("gotox-edges-at-limit"))
> +		check_gotox_edges_at_limit();
> +
> +	if (test__start_subtest("gotox-edges-across-subprogs"))
> +		check_gotox_edges_across_subprogs();
>  }
>  #else
>  static void __test_bpf_insn_array(void)
> -- 
> 2.43.0
> 

Acked-by: Anton Protopopov <a.s.protopopov@gmail.com>