reduce BPF_ID_MAP_SIZE to fit only valid programs
Subsystems (4)
Eduard Zingerman
maintainercover reduce BPF_ID_MAP_SIZE to fit only valid programs
This is a follow-up for threads [1] and [2]:
- The size of the bpf_verifier_state->idmap_scratch array is reduced but remains sufficient for any valid BPF program.
- selftests/bpf test_loader is updated to allow specifying that program requires BPF_F_TEST_STATE_FREQ flag.
- Test case for the verifier.c:check_ids() update uses test_loader and is meant as an example of using it for test_verifier-kind tests.
The combination of test_loader and naked functions (see [3]) with inline assembly allows to write verifier tests easier than it is done currently with BPF_RAW_INSN-series macros.
One can follow the steps below to add new tests of such kind:
- add a topic file under bpf/progs/ directory;
- define test programs using naked functions and inline assembly:
#include <linux/bpf.h>
#include "bpf_misc.h"
SEC(...)
__naked int foo_test(void)
{
asm volatile(
"r0 = 0;"
"exit;"
::: __clobber_all);
} - add skeleton and runner functions in prog_tests/verifier.c:
#include "topic.skel.h" TEST_SET(topic)
After these steps the test_progs binary would include the topic tests. Topic tests could be selectively executed using the following command:
$ ./test_progs -vvv -a topic
These changes are suggested by Andrii Nakryiko.
[1] https://lore.kernel.org/bpf/CAEf4BzYN1JmY9t03pnCHc4actob80wkBz2vk90ihJCBzi8CT9w@mail.gmail.com/
[2] https://lore.kernel.org/bpf/CAEf4BzYPsDWdRgx+ND1wiKAB62P=WwoLhr2uWkbVpQfbHqi1oA@mail.gmail.com/
[3] https://gcc.gnu.org/onlinedocs/gcc/Basic-Asm.html#Basic-Asm
Eduard Zingerman (4):
selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader selftests/bpf: convenience macro for use with 'asm volatile' blocks
bpf: reduce BPF_ID_MAP_SIZE to fit only valid programs selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids
include/linux/bpf_verifier.h | 4 +- kernel/bpf/verifier.c | 6 +- .../selftests/bpf/prog_tests/verifier.c | 12 +++ tools/testing/selftests/bpf/progs/bpf_misc.h | 7 ++ .../selftests/bpf/progs/check_ids_limits.c | 77 +++++++++++++++++++ tools/testing/selftests/bpf/test_loader.c | 10 +++ 6 files changed, 112 insertions(+), 4 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c
Signature · 1 line
2.38.2
Eduard Zingerman
maintainerPATCH 1/4 selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader
Adds a macro __test_state_freq, the macro expands as a btf_decl_tag of a special form that instructs test_loader that the flag BPF_F_TEST_STATE_FREQ has to be passed to BPF verifier when program is loaded.
--- tools/testing/selftests/bpf/progs/bpf_misc.h | 1 + tools/testing/selftests/bpf/test_loader.c | 10 ++++++++++ 2 files changed, 11 insertions(+)
tools/testing/selftests/bpf/progs/bpf_misc.h +1 -0
@@ -6,6 +6,7 @@#define __failure __attribute__((btf_decl_tag("comment:test_expect_failure")))#define __success __attribute__((btf_decl_tag("comment:test_expect_success")))#define __log_level (lvl) __attribute__((btf_decl_tag("comment:test_log_level="#lvl))) +#define __test_state_freq __attribute__((btf_decl_tag("comment:test_state_freq")))#if defined(__TARGET_ARCH_x86)#define SYSCALL_WRAPPER 1
tools/testing/selftests/bpf/test_loader.c +10 -0
@@ -11,6 +11,7 @@#define TEST_TAG_EXPECT_FAILURE "comment:test_expect_failure"#define TEST_TAG_EXPECT_SUCCESS "comment:test_expect_success" +#define TEST_TAG_TEST_STATE_FREQ "comment:test_state_freq"#define TEST_TAG_EXPECT_MSG_PFX "comment:test_expect_msg="#define TEST_TAG_LOG_LEVEL_PFX "comment:test_log_level="
@@ -19,6 +20,7 @@ struct test_spec {bool expect_failure;const char *expect_msg;int log_level; +bool test_state_freq; };static int tester_init (struct test_loader *tester)
@@ -81,6 +83,8 @@ static int parse_test_spec(struct test_loader *tester, spec->expect_failure = true; }else if (strcmp (s,TEST_TAG_EXPECT_SUCCESS ) ==0 ) { spec->expect_failure = false; + }else if (strcmp (s,TEST_TAG_TEST_STATE_FREQ ) ==0 ) { + spec->test_state_freq = true; }else if (str_has_pfx (s,TEST_TAG_EXPECT_MSG_PFX )) { spec->expect_msg = s +sizeof (TEST_TAG_EXPECT_MSG_PFX ) -1 ; }else if (str_has_pfx (s,TEST_TAG_LOG_LEVEL_PFX )) {
@@ -102,6 +106,7 @@ static void prepare_case(struct test_loader *tester, struct bpf_program *prog) {int min_log_level =0 ; +__u32 flags =0 ;if (env.verbosity >VERBOSE_NONE ) min_log_level =1 ;
@@ -120,6 +125,11 @@ static void prepare_case(struct test_loader *tester,bpf_program__set_log_level (prog, spec->log_level); tester->log_buf[0 ] ='\0' ; + +if (spec->test_state_freq) + flags |=BPF_F_TEST_STATE_FREQ ; + +bpf_program__set_flags (prog, flags); }static void emit_verifier_log (const char *log_buf,bool force)
Signature · 1 line
2.38.2
Eduard Zingerman
maintainerPATCH 2/4 selftests/bpf: convenience macro for use with 'asm volatile' blocks
In reply to Eduard ZingermanA set of macros useful for writing naked BPF functions using inline assembly. E.g. as follows:
struct map_struct {
...
} map SEC(".maps");SEC(...)__naked int foo_test(void)
{
asm volatile(
"r0 = 0;"
"*(u64*)(r10 - 8) = r0;"
"r1 = %[map] ll;"
"r2 = r10;"
"r2 += -8;"
"call %[bpf_map_lookup_elem];"
"r0 = 0;"
"exit;"
:
: __imm(bpf_map_lookup_elem),
__imm_addr(map)
: __clobber_all);
}--- tools/testing/selftests/bpf/progs/bpf_misc.h | 6 ++++++ 1 file changed, 6 insertions(+)
tools/testing/selftests/bpf/progs/bpf_misc.h +6 -0
@@ -8,6 +8,12 @@#define __log_level (lvl) __attribute__((btf_decl_tag("comment:test_log_level="#lvl)))#define __test_state_freq __attribute__((btf_decl_tag("comment:test_state_freq"))) +/* Convenience macro for use with 'asm volatile' blocks */ +#define __naked __attribute__((naked)) +#define __clobber_all "r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9", "memory" +#define __imm (name) [name]"i"(name) +#define __imm_addr (name) [name]"i"(&name) +#if defined(__TARGET_ARCH_x86)#define SYSCALL_WRAPPER 1#define SYS_PREFIX "__x64_"
Signature · 1 line
2.38.2
Eduard Zingerman
maintainerPATCH 3/4 bpf: reduce BPF_ID_MAP_SIZE to fit only valid programs
In reply to Eduard ZingermanBPF limits stack usage by MAX_BPF_STACK bytes across all call frames, however this is enforced by function check_max_stack_depth() which is executed after do_check_{subprogs,main}().
This means that when check_ids() is executed the maximal stack depth is not yet verified, thus in theory the number of stack spills might be MAX_CALL_FRAMES * MAX_BPF_STACK / BPF_REG_SIZE.
However, any program with stack usage deeper than MAX_BPF_STACK / BPF_REG_SIZE would be rejected by verifier.
Hence save some memory by reducing the BPF_ID_MAP_SIZE.
This is a follow up for
https://lore.kernel.org/bpf/CAEf4BzYN1JmY9t03pnCHc4actob80wkBz2vk90ihJCBzi8CT9w@mail.gmail.com/
--- include/linux/bpf_verifier.h | 4 ++-- kernel/bpf/verifier.c | 6 ++++-- 2 files changed, 6 insertions(+), 4 deletions(-)
include/linux/bpf_verifier.h +2 -2
@@ -274,8 +274,8 @@ struct bpf_id_pair { };#define MAX_CALL_FRAMES 8 -/* Maximum number of register states that can exist at once */ -#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES) +/* Maximum number of register states that can exist at once in a valid program */ +#define BPF_ID_MAP_SIZE (MAX_BPF_REG * MAX_CALL_FRAMES + MAX_BPF_STACK / BPF_REG_SIZE)struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];
kernel/bpf/verifier.c +4 -2
@@ -12951,8 +12951,10 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)if (idmap[i].old == old_id)return idmap[i].cur == cur_id; } -/* We ran out of idmap slots, which should be impossible */ -WARN_ON_ONCE (1 ); +/* Run out of slots in idmap, conservatively return false, cached +* state will not be reused. The BPF_ID_MAP_SIZE is sufficiently +* large to fit all valid programs. +*/ return false; }
Signature · 1 line
2.38.2
Eduard Zingerman
maintainerPATCH 4/4 selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids
In reply to Eduard ZingermanA simple program that allocates a bunch of unique register ids than branches. The goal is to confirm that idmap used in verifier.c:check_ids() has sufficient capacity to verify that branches converge to a same state.
--- .../selftests/bpf/prog_tests/verifier.c | 12 +++ .../selftests/bpf/progs/check_ids_limits.c | 77 +++++++++++++++++++ 2 files changed, 89 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c
tools/testing/selftests/bpf/prog_tests/verifier.c new file +12 -0
@@ -0,0 +1,12 @@ +// SPDX-License-Identifier: GPL-2.0-only +#include <test_progs.h> + +#include "check_ids_limits.skel.h" + +#define TEST_SET (skel) \ + void test_##skel(void) \ + { \ + RUN_TESTS(skel); \ + } + +TEST_SET (check_ids_limits)
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +77 -0
77 lines not on this page · raw message
Signature · 1 line
2.38.2
Re: [PATCH bpf-next 1/4] selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader
In reply to Eduard ZingermanQuoted 5 lines · Eduard Zingerman
Adds a macro
__test_state_freq, the macro expands as abtf_decl_tagof a special form that instructstest_loaderthat the flagBPF_F_TEST_STATE_FREQhas to be passed to BPF verifier when program is loaded.Signed-off-by Eduard Zingerman <[email protected]>
Re: [PATCH bpf-next 2/4] selftests/bpf: convenience macro for use with 'asm volatile' blocks
In reply to Eduard ZingermanQuoted 25 lines · Eduard Zingerman
A set of macros useful for writing naked BPF functions using inline assembly. E.g. as follows:
struct map_struct { ... } map SEC(".maps");SEC(...)
__nakedintfoo_test(void){ asm volatile( "r0 = 0;" "*(u64*)(r10 - 8) = r0;" "r1 = %[map] ll;" "r2 = r10;" "r2 += -8;" "call %[bpf_map_lookup_elem];" "r0 = 0;" "exit;" : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); }
Quoted 1 line
Signed-off-by Eduard Zingerman <[email protected]>
Re: [PATCH bpf-next 3/4] bpf: reduce BPF_ID_MAP_SIZE to fit only valid programs
In reply to Eduard ZingermanQuoted 11 lines · Eduard Zingerman
BPF limits stack usage by
MAX_BPF_STACKbytes across all call frames, however this is enforced by functioncheck_max_stack_depth()which is executed after do_check_{subprogs,main}().This means that when
check_ids()is executed the maximal stack depth is not yet verified, thus in theory the number of stack spills might beMAX_CALL_FRAMES*MAX_BPF_STACK/BPF_REG_SIZE.However, any program with stack usage deeper than
MAX_BPF_STACK/BPF_REG_SIZEwould be rejected by verifier.
Quoted 7 lines
Hence save some memory by reducing the
BPF_ID_MAP_SIZE.This is a follow up for
https://lore.kernel.org/bpf/CAEf4BzYN1JmY9t03pnCHc4actob80wkBz2vk90ihJCBzi8CT9w@mail.gmail.com/Signed-off-by Eduard Zingerman <[email protected]>Suggested-by Andrii Nakryiko <[email protected]>
Re: [PATCH bpf-next 4/4] selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids
In reply to Eduard ZingermanQuoted 5 lines · Eduard Zingerman
A simple program that allocates a bunch of unique register ids than branches. The goal is to confirm that idmap used in verifier.c:check_ids() has sufficient capacity to verify that branches converge to a same state.
Signed-off-by Eduard Zingerman <[email protected]>
Re: [PATCH bpf-next 1/4] selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader
In reply to Eduard ZingermanQuoted 5 lines · Eduard Zingerman
Adds a macro
__test_state_freq, the macro expands as abtf_decl_tagof a special form that instructstest_loaderthat the flagBPF_F_TEST_STATE_FREQhas to be passed to BPF verifier when program is loaded.
I needed similar capabilities locally, but I went a slightly different direction. Instead of defining custom macros and logic, I define just __flags(X) macro and then parse flags either by their symbolic name (or just integer value, which might be useful sometimes for development purposes). I've also added support for matching multiple messages sequentially which locally is in the same commit. Feel free to ignore that part, but I think it's useful as well. So WDYT about the below?
commit 936bb5d21d717d54c85e74047e082ca3216a7a40
Author: Andrii Nakryiko <[email protected]> Date: Mon Dec 19 15:57:26 2022 -0800
selftests/bpf: support custom per-test flags and multiple expected messages
(quoted diff) +0 -0
b/tools/testing/selftests/bpf/test_loader.c
index 679efb3aa785..b0dab5dee38c 100644
tools/testing/selftests/bpf/test_loader.c +10 -3
@@ -13,12 +13,15 @@#define TEST_TAG_EXPECT_SUCCESS "comment:test_expect_success"#define TEST_TAG_EXPECT_MSG_PFX "comment:test_expect_msg="#define TEST_TAG_LOG_LEVEL_PFX "comment:test_log_level=" +#define TEST_TAG_PROG_FLAGS_PFX "comment:test_prog_flags="struct test_spec {const char *name;bool expect_failure; -const char *expect_msg; +const char **expect_msgs; +size_t expect_msg_cnt;int log_level; +int prog_flags; };static int tester_init (struct test_loader *tester)
@@ -67,7 +70,8 @@ static int parse_test_spec(struct test_loader *tester,for (i =1 ; i <btf__type_cnt (btf); i++) {const struct btf_type *t; -const char *s; +const char *s, *val; +char *e; t =btf__type_by_id (btf, i);if (!btf_is_decl_tag (t))
@@ -82,14 +86,47 @@ static int parse_test_spec(struct test_loader *tester, }else if (strcmp (s,TEST_TAG_EXPECT_SUCCESS ) ==0 ) { spec->expect_failure = false; }else if (str_has_pfx (s,TEST_TAG_EXPECT_MSG_PFX )) { - spec->expect_msg = s +sizeof (TEST_TAG_EXPECT_MSG_PFX ) -1 ; +void *tmp; +const char **msg; + + tmp = realloc(spec->expect_msgs, (1 +
spec->expect_msg_cnt) * sizeof(void *));
+ if (!tmp) {
+ ASSERT_FAIL("failed to realloc memory for messages\n");
+ return -ENOMEM;
+ }
+ spec->expect_msgs = tmp;
+ msg = &spec->expect_msgs[spec->expect_msg_cnt++];
+ *msg = s + sizeof(TEST_TAG_EXPECT_MSG_PFX) - 1;
} else if (str_has_pfx(s, TEST_TAG_LOG_LEVEL_PFX)) {
+ val = s + sizeof(TEST_TAG_LOG_LEVEL_PFX) - 1;
errno = 0;
- spec->log_level = strtol(s +
sizeof(TEST_TAG_LOG_LEVEL_PFX) - 1, NULL, 0);
- if (errno) {
+ spec->log_level = strtol(val, &e, 0);
+ if (errno || e[0] != '\0') {
ASSERT_FAIL("failed to parse test log level from '%s'", s);
return -EINVAL;
}+ } else if (str_has_pfx(s, TEST_TAG_PROG_FLAGS_PFX)) {
+ val = s + sizeof(TEST_TAG_PROG_FLAGS_PFX) - 1;
+ if (strcmp(val, "BPF_F_STRICT_ALIGNMENT") == 0) {
+ spec->prog_flags |= BPF_F_STRICT_ALIGNMENT;
+ } else if (strcmp(val, "BPF_F_ANY_ALIGNMENT") == 0) {
+ spec->prog_flags |= BPF_F_ANY_ALIGNMENT;
+ } else if (strcmp(val, "BPF_F_TEST_RND_HI32") == 0) {
+ spec->prog_flags |= BPF_F_TEST_RND_HI32;
+ } else if (strcmp(val, "BPF_F_TEST_STATE_FREQ") == 0) {
+ spec->prog_flags |= BPF_F_TEST_STATE_FREQ;
+ } else if (strcmp(val, "BPF_F_SLEEPABLE") == 0) {
+ spec->prog_flags |= BPF_F_SLEEPABLE;
+ } else if (strcmp(val, "BPF_F_XDP_HAS_FRAGS") == 0) {
+ spec->prog_flags |= BPF_F_XDP_HAS_FRAGS;
+ } else /* assume numeric value */ {
+ errno = 0;
+ spec->prog_flags |= strtol(val, &e, 0);
+ if (errno || e[0] != '\0') {+ ASSERT_FAIL("failed to parse test prog flags from
'%s'", s);
+ return -EINVAL;
+ }
+ }
}
}@@ -101,7 +138,7 @@ static void prepare_case(struct test_loader *tester,
struct bpf_object *obj,
struct bpf_program *prog)
{
- int min_log_level = 0;
+ int min_log_level = 0, prog_flags;
if (env.verbosity > VERBOSE_NONE)
min_log_level = 1;
@@ -119,7 +156,11 @@ static void prepare_case(struct test_loader *tester,
else
bpf_program__set_log_level(prog, spec->log_level);+ prog_flags = bpf_program__flags(prog);
+ bpf_program__set_flags(prog, prog_flags | spec->prog_flags);
+
tester->log_buf[0] = '\0';
+ tester->next_match_pos = 0;
}
static void emit_verifier_log(const char *log_buf, bool force)
@@ -135,17 +176,26 @@ static void validate_case(struct test_loader *tester,
struct bpf_program *prog,
int load_err)
{
- if (spec->expect_msg) {
+ int i, j;
+
+ for (i = 0; i < spec->expect_msg_cnt; i++) {
char *match;+ const char *expect_msg;
+
+ expect_msg = spec->expect_msgs[i];
- match = strstr(tester->log_buf, spec->expect_msg);
+ 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*/);
- fprintf(stderr, "EXPECTED MSG: '%s'\n", spec->expect_msg);
+ for (j = 0; j < i; j++)
+ fprintf(stderr, "MATCHED MSG: '%s'\n", spec->expect_msgs[j]);
+ fprintf(stderr, "EXPECTED MSG: '%s'\n", expect_msg);
return;
}
+
+ tester->next_match_pos = match - tester->log_buf + strlen(expect_msg);
}}
(quoted diff) +0 -0
b/tools/testing/selftests/bpf/test_progs.h
index 3f058dfadbaf..9af80704f20a 100644
tools/testing/selftests/bpf/test_progs.h +1 -0
@@ -410,6 +410,7 @@ int write_sysctl(const char *sysctl, const char *value);struct test_loader {char *log_buf;size_t log_buf_sz; +size_t next_match_pos;struct bpf_object *obj; };
Quoted 56 lines
Signed-off-by Eduard Zingerman <[email protected]>--- tools/testing/selftests/bpf/progs/bpf_misc.h | 1 + tools/testing/selftests/bpf/test_loader.c | 10 ++++++++++ 2 files changed, 11 insertions(+)tools/testing/selftests/bpf/progs/bpf_misc.h +1
-0@@ -6,6 +6,7 @@#define __failure __attribute__((btf_decl_tag("comment:test_expect_failure")))#define __success __attribute__((btf_decl_tag("comment:test_expect_success")))#define __log_level (lvl) __attribute__((btf_decl_tag("comment:test_log_level="#lvl))) +#define __test_state_freq __attribute__((btf_decl_tag("comment:test_state_freq")))#if defined(__TARGET_ARCH_x86)#define SYSCALL_WRAPPER 1tools/testing/selftests/bpf/test_loader.c +5
-0@@ -11,6 +11,7 @@#define TEST_TAG_EXPECT_FAILURE "comment:test_expect_failure"#define TEST_TAG_EXPECT_SUCCESS "comment:test_expect_success" +#define TEST_TAG_TEST_STATE_FREQ "comment:test_state_freq"#define TEST_TAG_EXPECT_MSG_PFX "comment:test_expect_msg="#define TEST_TAG_LOG_LEVEL_PFX "comment:test_log_level="@@ -19,6 +20,7 @@ struct test_spec {bool expect_failure;const char *expect_msg;int log_level; +bool test_state_freq; };static int tester_init (struct test_loader *tester)@@ -81,6 +83,8 @@ static int parse_test_spec(struct test_loader *tester, spec->expect_failure = true; }else if (strcmp (s,TEST_TAG_EXPECT_SUCCESS ) ==0 ) { spec->expect_failure = false; + }else if (strcmp (s,TEST_TAG_TEST_STATE_FREQ ) ==0 ) { + spec->test_state_freq = true; }else if (str_has_pfx (s,TEST_TAG_EXPECT_MSG_PFX )) { spec->expect_msg = s +sizeof (TEST_TAG_EXPECT_MSG_PFX ) -1 ; }else if (str_has_pfx (s,TEST_TAG_LOG_LEVEL_PFX )) {@@ -102,6 +106,7 @@ static void prepare_case(struct test_loader *tester, struct bpf_program *prog) {int min_log_level =0 ; +__u32 flags =0 ;if (env.verbosity >VERBOSE_NONE ) min_log_level =1 ;
tools/testing/selftests/bpf/test_loader.c static void prepare_case(struct test_loader *tester, · line 132
Quoted 8 lines
tools/testing/selftests/bpf/test_loader.c +5
-0@@ -120,6 +125,11 @@ static void prepare_case(struct test_loader *tester,bpf_program__set_log_level (prog, spec->log_level); tester->log_buf[0 ] ='\0' ; + +if (spec->test_state_freq) + flags |=BPF_F_TEST_STATE_FREQ ; + +bpf_program__set_flags (prog, flags);
see my example above, it's safer to fetch current prog flags to not override stuff like BPF_F_SLEEPABLE
Quoted 6 lines
tools/testing/selftests/bpf/test_loader.c +0
-1}static void emit_verifier_log (const char *log_buf,bool force) --2.38.2
Re: [PATCH bpf-next 2/4] selftests/bpf: convenience macro for use with 'asm volatile' blocks
In reply to Eduard ZingermanQuoted 36 lines · Eduard Zingerman
A set of macros useful for writing naked BPF functions using inline assembly. E.g. as follows:
struct map_struct { ... } map SEC(".maps");SEC(...)
__nakedintfoo_test(void){ asm volatile( "r0 = 0;" "*(u64*)(r10 - 8) = r0;" "r1 = %[map] ll;" "r2 = r10;" "r2 += -8;" "call %[bpf_map_lookup_elem];" "r0 = 0;" "exit;" : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); }Signed-off-by Eduard Zingerman <[email protected]>--- tools/testing/selftests/bpf/progs/bpf_misc.h | 6 ++++++ 1 file changed, 6 insertions(+)tools/testing/selftests/bpf/progs/bpf_misc.h +0
-0
tools/testing/selftests/bpf/progs/bpf_misc.h line 13
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +3
-0@@ -8,6 +8,12 @@#define __log_level (lvl) __attribute__((btf_decl_tag("comment:test_log_level="#lvl)))#define __test_state_freq __attribute__((btf_decl_tag("comment:test_state_freq"))) +/* Convenience macro for use with 'asm volatile' blocks */ +#define __naked __attribute__((naked)) +#define __clobber_all "r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9", "memory"
I found that this one doesn't work well when passing some inputs as registers (e.g., for address of a variable on stack). Compiler complains that it couldn't find any free registers to use. So I ended up using
#define __asm_common_clobbers "r0", "r1", "r2", "r3", "r4", "r5", "memory"
and adding "r6", "r7", etc manually, depending on the test.
So maybe let's add it upfront as __clobber_common as well?
But changes look good to me:
Quoted 9 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +3
-1+#define __imm (name) [name]"i"(name) +#define __imm_addr (name) [name]"i"(&name) +#if defined(__TARGET_ARCH_x86)#define SYSCALL_WRAPPER 1#define SYS_PREFIX "__x64_" --2.38.2
Re: [PATCH bpf-next 3/4] bpf: reduce BPF_ID_MAP_SIZE to fit only valid programs
In reply to Eduard ZingermanQuoted 12 lines · Eduard Zingerman
BPF limits stack usage by
MAX_BPF_STACKbytes across all call frames, however this is enforced by functioncheck_max_stack_depth()which is executed after do_check_{subprogs,main}().This means that when
check_ids()is executed the maximal stack depth is not yet verified, thus in theory the number of stack spills might beMAX_CALL_FRAMES*MAX_BPF_STACK/BPF_REG_SIZE.However, any program with stack usage deeper than
MAX_BPF_STACK/BPF_REG_SIZEwould be rejected by verifier.
Quoted 8 lines
Hence save some memory by reducing the
BPF_ID_MAP_SIZE.This is a follow up for
https://lore.kernel.org/bpf/CAEf4BzYN1JmY9t03pnCHc4actob80wkBz2vk90ihJCBzi8CT9w@mail.gmail.com/Signed-off-by Eduard Zingerman <[email protected]>Suggested-by Andrii Nakryiko <[email protected]>---
LGTM, thanks.
Quoted 39 lines
include/linux/bpf_verifier.h | 4 ++-- kernel/bpf/verifier.c | 6 ++++-- 2 files changed, 6 insertions(+), 4 deletions(-)include/linux/bpf_verifier.h +2
-2@@ -274,8 +274,8 @@ struct bpf_id_pair { };#define MAX_CALL_FRAMES 8 -/* Maximum number of register states that can exist at once */ -#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE) * MAX_CALL_FRAMES) +/* Maximum number of register states that can exist at once in a valid program */ +#define BPF_ID_MAP_SIZE (MAX_BPF_REG * MAX_CALL_FRAMES + MAX_BPF_STACK / BPF_REG_SIZE)struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];kernel/bpf/verifier.c +4
-3@@ -12951,8 +12951,10 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_id_pair *idmap)if (idmap[i].old == old_id)return idmap[i].cur == cur_id; } -/* We ran out of idmap slots, which should be impossible */ -WARN_ON_ONCE (1 ); +/* Run out of slots in idmap, conservatively return false, cached +* state will not be reused. The BPF_ID_MAP_SIZE is sufficiently +* large to fit all valid programs. +*/ return false; } --2.38.2
Re: [PATCH bpf-next 4/4] selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids
In reply to Eduard ZingermanQuoted 19 lines · Eduard Zingerman
A simple program that allocates a bunch of unique register ids than branches. The goal is to confirm that idmap used in verifier.c:check_ids() has sufficient capacity to verify that branches converge to a same state.
Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/prog_tests/verifier.c | 12 +++ .../selftests/bpf/progs/check_ids_limits.c | 77 +++++++++++++++++++ 2 files changed, 89 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.ctools/testing/selftests/bpf/prog_tests/verifier.c new file +0
-0
tools/testing/selftests/bpf/prog_tests/verifier.c line 10
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/verifier.c new file +10
-0@@ -0,0 +1,12 @@ +// SPDX-License-Identifier: GPL-2.0-only +#include <test_progs.h> + +#include "check_ids_limits.skel.h" + +#define TEST_SET (skel) \ + void test_##skel(void) \ + { \ + RUN_TESTS(skel); \ + }
Let's not use such trivial macros, please. It makes grepping for tests much harder and saves 1 line of code only. Let's define funcs explicitly?
I'm also surprised it works at all (it does, right?), because Makefile is grepping explicitly for void (serial_)test_xxx pattern when generating a list of tests. So this shouldn't have worked, unless I'm missing something.
Quoted 16 lines
tools/testing/selftests/bpf/prog_tests/verifier.c new file +2
-0+ +TEST_SET (check_ids_limits)tools/testing/selftests/bpf/progs/check_ids_limits.c new file +8
-0@@ -0,0 +1,77 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +struct map_struct { + __uint(type, BPF_MAP_TYPE_ARRAY);
tools/testing/selftests/bpf/progs/check_ids_limits.c line 18
Quoted 10 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +10
-0+__uint (max_entries,1 ); +__type (key, int); +__type (value, int); +} map SEC(".maps"); + +/* Make sure that verifier.c:check_ids() can handle (almost) maximal +* number of ids. +*/ +SEC("?raw_tp") +__naked __test_state_freq __log_level(2) __msg("43 to 45: safe")
it's not clear what's special about 43 -> 45 jump?
can we also validate that id=69 was somewhere in verifier output? which would require multiple __msg support, of course.
Quoted 30 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +30
-0+int allocate_many_ids (void ) +{ +/* Use bpf_map_lookup_elem() as a way to get a bunch of values +* with unique ids. +*/ +#define __lookup (dst) \ + "r1 = %[map] ll;" \ + "r2 = r10;" \ + "r2 += -8;" \ + "call %[bpf_map_lookup_elem];" \ + dst " = r0;" + asmvolatile ( +"r0 = 0;" +"*(u64*)(r10 - 8) = r0;" +"r7 = r10;" +"r8 = 0;" +/* Spill 64 bpf_map_lookup_elem() results to stack, +* each lookup gets its own unique id. +*/ +"write_loop:" +"r7 += -8;" +"r8 += -8;" + __lookup("*(u64*)(r7 + 0)") +"if r8 != -512 goto write_loop;" +/* No way to source unique ids for r1-r5 as these +* would be clobbered by bpf_map_lookup_elem call, +* so make do with 64+5 unique ids. +*/ + __lookup("r6") +__lookup ("r7" )
tools/testing/selftests/bpf/progs/check_ids_limits.c line 58
Quoted 10 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +10
-0+ __lookup("r8") + __lookup("r9") +__lookup ("r0" ) +/* Create a branching point for states comparison. */ +/* 43: */ "if r0 != 0 goto skip_one;" +/* Read all registers and stack spills to make these +* persist in the checkpoint state. +*/ +"r0 = r0;" +"skip_one:"
where you trying to just create a checkpoint here? given __test_state_freq the simplest way would be just
goto +0;
no?
Quoted 22 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +19
-1+/* 45: */ "r0 = r6;" +"r0 = r7;" +"r0 = r8;" +"r0 = r9;" +"r0 = r10;" +"r1 = 0;" +"read_loop:" +"r0 += -8;" +"r1 += -8;" +"r2 = *(u64*)(r0 + 0);" +"if r1 != -512 goto read_loop;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_map_lookup_elem), +__imm_addr (map) + : __clobber_all); +#undef __lookup +} --2.38.2
Quoted 9 lines · Eduard Zingerman
This is a follow-up for threads [1] and [2]:
- The size of thebpf_verifier_state->idmap_scratcharray is reduced but remains sufficient for any valid BPF program.
- selftests/bpftest_loaderis updated to allow specifying that program requiresBPF_F_TEST_STATE_FREQflag.
- Test case for the verifier.c:check_ids() update usestest_loaderand is meant as an example of using it for test_verifier-kind tests.
Quoted 7 lines
The combination of
test_loaderand naked functions (see [3]) with inline assembly allows to write verifier tests easier than it is done currently with BPF_RAW_INSN-series macros.One can follow the steps below to add new tests of such kind:
- add a topic file under bpf/progs/ directory;
- define test programs using naked functions and inline assembly:
it's better, you don't *have* to use __naked functions, you can mix and match. E.g., I have local tests that rely on the C compiler to do stack allocation for local variables (%[dynptr]) and global variables (%[zero]) and pass an address (fp-X) register to asm parts to work with it.
+int zero;
+
+SEC("?raw_tp")
+__failure
+__flags(BPF_F_TEST_STATE_FREQ)
+__msg("invalid size of register fill")
+int stacksafe_should_not_conflate_stack_spill_and_dynptr(void *ctx) +{
+ struct bpf_dynptr dynptr;
+
+ asm volatile (
+ /* Create a fork in logic, with general setup as follows:
+ * - fallthrough (first) path is valid; + * - branch (second) path is invalid. + * Then depending on what we do in fallthrough vs branch path, + * we try to detect bugs in func_states_equal(), regsafe(), + * refsafe(), stack_safe(), and similar by tricking verifier + * into believing that branch state is a valid subset of + * a fallthrough state. Verifier should reject overall + * validation, unless there is a bug somewhere in verifier + * logic. + */ + "call %[bpf_get_prandom_u32];" + "r6 = r0;" + "call %[bpf_get_prandom_u32];" + "r7 = r0;" + "if r6 > r7 goto bad;" /* fork */ + + /* spill r6 into stack slot of bpf_dynptr var */ + "*(u64 *)(%[dynptr] + 0) = r6;" + "*(u64 *)(%[dynptr] + 8) = r6;" + + "goto skip_bad;" + "bad:" + /* create dynptr in the same stack slot */ + "r1 = %[zero];" + "r2 = 4;" + "r3 = 0;" + "r4 = %[dynptr];" + "call %[bpf_dynptr_from_mem];"
+
+ /* here, if stacksafe() doesn't distinguish STACK_DYNPTR from
+ * STACK_MISC, verifier will assume safety at checkpoint below
+ */
+ "skip_bad:"
+ "goto +0;" /* force checkpoint */
+
+ /* leak dynptr state */ + "r0 = *(u64 *)(%[dynptr] + 8);" + "if r0 > 0 goto +1;" + "exit;" + : + : __asm_ptr(dynptr), __asm_ptr(zero),
+ __asm_imm(bpf_get_prandom_u32),
+ __asm_imm(bpf_dynptr_from_mem)
+ : __asm_common_clobbers, "r6", "r7"
+ );
+
+ return 0;
+}
Quoted 48 lines
#include <linux/bpf.h> #include "bpf_misc.h" SEC(...) __naked int foo_test(void) { asm volatile( "r0 = 0;" "exit;" ::: __clobber_all); }- add skeleton and runner functions in
prog_tests/verifier.c:#include "topic.skel.h" TEST_SET(topic)After these steps the
test_progsbinary would include the topic tests. Topic tests could be selectively executed using the following command:$ ./test_progs -vvv -a topicThese changes are suggested by Andrii Nakryiko.
[1] https://lore.kernel.org/bpf/CAEf4BzYN1JmY9t03pnCHc4actob80wkBz2vk90ihJCBzi8CT9w@mail.gmail.com/
[2] https://lore.kernel.org/bpf/CAEf4BzYPsDWdRgx+ND1wiKAB62P=WwoLhr2uWkbVpQfbHqi1oA@mail.gmail.com/
[3] https://gcc.gnu.org/onlinedocs/gcc/Basic-Asm.html#Basic-AsmEduard Zingerman (4):
selftests/bpf: support forBPF_F_TEST_STATE_FREQintest_loaderselftests/bpf: convenience macro for use with 'asm volatile' blocks
bpf: reduceBPF_ID_MAP_SIZEto fit only valid programs selftests/bpf: check if verifier.c:check_ids() handles 64+5 idsinclude/linux/bpf_verifier.h | 4 +- kernel/bpf/verifier.c | 6 +- .../selftests/bpf/prog_tests/verifier.c | 12 +++ tools/testing/selftests/bpf/progs/bpf_misc.h | 7 ++ .../selftests/bpf/progs/check_ids_limits.c | 77 +++++++++++++++++++ tools/testing/selftests/bpf/test_loader.c | 10 +++ 6 files changed, 112 insertions(+), 4 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.c--
2.38.2
Eduard Zingerman
maintainerRe: [PATCH bpf-next 1/4] selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader
In reply to Andrii NakryikoQuoted 7 lines · Andrii Nakryiko
Quoted 5 lines · Eduard Zingerman
Adds a macro
__test_state_freq, the macro expands as abtf_decl_tagof a special form that instructstest_loaderthat the flagBPF_F_TEST_STATE_FREQhas to be passed to BPF verifier when program is loaded.
Quoted 8 lines
I needed similar capabilities locally, but I went a slightly different direction. Instead of defining custom macros and logic, I define just
__flags(X)macro and then parse flags either by their symbolic name (or just integer value, which might be useful sometimes for development purposes). I've also added support for matching multiple messages sequentially which locally is in the same commit. Feel free to ignore that part, but I think it's useful as well. So WDYT about the below?
Makes total sense. I can replace my patch with your patch in the patchset, or just wait until your changes land.
Quoted 238 lines
commit
936bb5d21d717d54c85e74047e082ca3216a7a40Author: Andrii Nakryiko <[email protected]> Date: Mon Dec 19 15:57:26 2022 -0800selftests/bpf: support custom per-test flags and multiple expected messages
Signed-off-by Andrii Nakryiko <[email protected]>tools/testing/selftests/bpf/test_loader.c +42
-5@@ -13,12 +13,15 @@#define TEST_TAG_EXPECT_SUCCESS "comment:test_expect_success"#define TEST_TAG_EXPECT_MSG_PFX "comment:test_expect_msg="#define TEST_TAG_LOG_LEVEL_PFX "comment:test_log_level=" +#define TEST_TAG_PROG_FLAGS_PFX "comment:test_prog_flags="struct test_spec {const char *name;bool expect_failure; -const char *expect_msg; +const char **expect_msgs; +size_t expect_msg_cnt;int log_level; +int prog_flags; };static int tester_init (struct test_loader *tester)@@ -67,7 +70,8 @@ static int parse_test_spec(struct test_loader *tester,for (i =1 ; i <btf__type_cnt (btf); i++) {const struct btf_type *t; -const char *s; +const char *s, *val; +char *e; t =btf__type_by_id (btf, i);if (!btf_is_decl_tag (t))@@ -82,14 +86,47 @@ static int parse_test_spec(struct test_loader *tester, }else if (strcmp (s,TEST_TAG_EXPECT_SUCCESS ) ==0 ) { spec->expect_failure = false; }else if (str_has_pfx (s,TEST_TAG_EXPECT_MSG_PFX )) { - spec->expect_msg = s +sizeof (TEST_TAG_EXPECT_MSG_PFX ) -1 ; +void *tmp; +const char **msg; + + tmp =realloc (spec->expect_msgs, (1 + spec->expect_msg_cnt) *sizeof (void *)); +if (!tmp) { +ASSERT_FAIL ("failed to realloc memory for messages\n" ); +return -ENOMEM ; + } + spec->expect_msgs = tmp; + msg = &spec->expect_msgs[spec->expect_msg_cnt++]; + *msg = s +sizeof (TEST_TAG_EXPECT_MSG_PFX ) -1 ; }else if (str_has_pfx (s,TEST_TAG_LOG_LEVEL_PFX )) { + val = s +sizeof (TEST_TAG_LOG_LEVEL_PFX ) -1 ; errno =0 ; - spec->log_level =strtol (s + sizeof(TEST_TAG_LOG_LEVEL_PFX) - 1, NULL, 0); -if (errno) { + spec->log_level =strtol (val, &e,0 ); +if (errno || e[0 ] !='\0' ) {ASSERT_FAIL ("failed to parse test log level from '%s'" , s);return -EINVAL ; } + }else if (str_has_pfx (s,TEST_TAG_PROG_FLAGS_PFX )) { + val = s +sizeof (TEST_TAG_PROG_FLAGS_PFX ) -1 ; +if (strcmp (val,"BPF_F_STRICT_ALIGNMENT" ) ==0 ) { + spec->prog_flags |=BPF_F_STRICT_ALIGNMENT ; + }else if (strcmp (val,"BPF_F_ANY_ALIGNMENT" ) ==0 ) { + spec->prog_flags |=BPF_F_ANY_ALIGNMENT ; + }else if (strcmp (val,"BPF_F_TEST_RND_HI32" ) ==0 ) { + spec->prog_flags |=BPF_F_TEST_RND_HI32 ; + }else if (strcmp (val,"BPF_F_TEST_STATE_FREQ" ) ==0 ) { + spec->prog_flags |=BPF_F_TEST_STATE_FREQ ; + }else if (strcmp (val,"BPF_F_SLEEPABLE" ) ==0 ) { + spec->prog_flags |=BPF_F_SLEEPABLE ; + }else if (strcmp (val,"BPF_F_XDP_HAS_FRAGS" ) ==0 ) { + spec->prog_flags |=BPF_F_XDP_HAS_FRAGS ; + }else /* assume numeric value */ { + errno =0 ; + spec->prog_flags |=strtol (val, &e,0 ); +if (errno || e[0 ] !='\0' ) { + ASSERT_FAIL("failed to parse test prog flags from '%s'", s); +return -EINVAL ; + } + }} }tools/testing/selftests/bpf/test_loader.c +17
-4@@ -101,7 +138,7 @@ static void prepare_case(struct test_loader *tester,struct bpf_object *obj, struct bpf_program *prog) { - int min_log_level = 0; + int min_log_level = 0, prog_flags;if (env.verbosity >VERBOSE_NONE ) min_log_level =1 ;@@ -119,7 +156,11 @@ static void prepare_case(struct test_loader *tester,else bpf_program__set_log_level (prog, spec->log_level); + prog_flags =bpf_program__flags (prog); +bpf_program__set_flags (prog, prog_flags | spec->prog_flags); + tester->log_buf[0 ] ='\0' ; + tester->next_match_pos =0 ; }static void emit_verifier_log (const char *log_buf,bool force)@@ -135,17 +176,26 @@ static void validate_case(struct test_loader *tester,struct bpf_program *prog, int load_err) { -if (spec->expect_msg) { + int i, j; + +for (i =0 ; i < spec->expect_msg_cnt; i++) {char *match; +const char *expect_msg; + + expect_msg = spec->expect_msgs[i]; - match =strstr (tester->log_buf, spec->expect_msg); + 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*/ ); -fprintf (stderr,"EXPECTED MSG: '%s'\n" , spec->expect_msg); +for (j =0 ; j < i; j++) +fprintf (stderr,"MATCHED MSG: '%s'\n" , spec->expect_msgs[j]); +fprintf (stderr,"EXPECTED MSG: '%s'\n" , expect_msg);return ; } + + tester->next_match_pos = match - tester->log_buf +strlen (expect_msg); } }tools/testing/selftests/bpf/test_progs.h +1
-0@@ -410,6 +410,7 @@ int write_sysctl(const char *sysctl, const char *value);struct test_loader {char *log_buf;size_t log_buf_sz; +size_t next_match_pos;struct bpf_object *obj; };Quoted 60 lines
Signed-off-by Eduard Zingerman <[email protected]>--- tools/testing/selftests/bpf/progs/bpf_misc.h | 1 + tools/testing/selftests/bpf/test_loader.c | 10 ++++++++++ 2 files changed, 11 insertions(+)tools/testing/selftests/bpf/progs/bpf_misc.h +1
-0@@ -6,6 +6,7 @@#define __failure __attribute__((btf_decl_tag("comment:test_expect_failure")))#define __success __attribute__((btf_decl_tag("comment:test_expect_success")))#define __log_level (lvl) __attribute__((btf_decl_tag("comment:test_log_level="#lvl))) +#define __test_state_freq __attribute__((btf_decl_tag("comment:test_state_freq")))#if defined(__TARGET_ARCH_x86)#define SYSCALL_WRAPPER 1tools/testing/selftests/bpf/test_loader.c +5
-0@@ -11,6 +11,7 @@#define TEST_TAG_EXPECT_FAILURE "comment:test_expect_failure"#define TEST_TAG_EXPECT_SUCCESS "comment:test_expect_success" +#define TEST_TAG_TEST_STATE_FREQ "comment:test_state_freq"#define TEST_TAG_EXPECT_MSG_PFX "comment:test_expect_msg="#define TEST_TAG_LOG_LEVEL_PFX "comment:test_log_level="@@ -19,6 +20,7 @@ struct test_spec {bool expect_failure;const char *expect_msg;int log_level; +bool test_state_freq; };static int tester_init (struct test_loader *tester)@@ -81,6 +83,8 @@ static int parse_test_spec(struct test_loader *tester, spec->expect_failure = true; }else if (strcmp (s,TEST_TAG_EXPECT_SUCCESS ) ==0 ) { spec->expect_failure = false; + }else if (strcmp (s,TEST_TAG_TEST_STATE_FREQ ) ==0 ) { + spec->test_state_freq = true; }else if (str_has_pfx (s,TEST_TAG_EXPECT_MSG_PFX )) { spec->expect_msg = s +sizeof (TEST_TAG_EXPECT_MSG_PFX ) -1 ; }else if (str_has_pfx (s,TEST_TAG_LOG_LEVEL_PFX )) {@@ -102,6 +106,7 @@ static void prepare_case(struct test_loader *tester, struct bpf_program *prog) {int min_log_level =0 ; +__u32 flags =0 ;if (env.verbosity >VERBOSE_NONE ) min_log_level =1 ;tools/testing/selftests/bpf/test_loader.c static void prepare_case(struct test_loader *tester, · line 132
Quoted 8 lines
tools/testing/selftests/bpf/test_loader.c +5
-0@@ -120,6 +125,11 @@ static void prepare_case(struct test_loader *tester,bpf_program__set_log_level (prog, spec->log_level); tester->log_buf[0 ] ='\0' ; + +if (spec->test_state_freq) + flags |=BPF_F_TEST_STATE_FREQ ; + +bpf_program__set_flags (prog, flags);see my example above, it's safer to fetch current prog flags to not override stuff like
BPF_F_SLEEPABLEQuoted 6 lines
tools/testing/selftests/bpf/test_loader.c +0
-1}static void emit_verifier_log (const char *log_buf,bool force) --2.38.2
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/4] selftests/bpf: convenience macro for use with 'asm volatile' blocks
In reply to Andrii NakryikoQuoted 49 lines · Andrii Nakryiko
Quoted 36 lines · Eduard Zingerman
A set of macros useful for writing naked BPF functions using inline assembly. E.g. as follows:
struct map_struct { ... } map SEC(".maps");SEC(...)
__nakedintfoo_test(void){ asm volatile( "r0 = 0;" "*(u64*)(r10 - 8) = r0;" "r1 = %[map] ll;" "r2 = r10;" "r2 += -8;" "call %[bpf_map_lookup_elem];" "r0 = 0;" "exit;" : : __imm(bpf_map_lookup_elem), __imm_addr(map) : __clobber_all); }Signed-off-by Eduard Zingerman <[email protected]>--- tools/testing/selftests/bpf/progs/bpf_misc.h | 6 ++++++ 1 file changed, 6 insertions(+)tools/testing/selftests/bpf/progs/bpf_misc.h +0
-0tools/testing/selftests/bpf/progs/bpf_misc.h line 13
Quoted 6 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +3
-0@@ -8,6 +8,12 @@#define __log_level (lvl) __attribute__((btf_decl_tag("comment:test_log_level="#lvl)))#define __test_state_freq __attribute__((btf_decl_tag("comment:test_state_freq"))) +/* Convenience macro for use with 'asm volatile' blocks */ +#define __naked __attribute__((naked)) +#define __clobber_all "r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9", "memory"I found that this one doesn't work well when passing some inputs as registers (e.g., for address of a variable on stack). Compiler complains that it couldn't find any free registers to use. So I ended up using
Quoted 5 lines
#define
__asm_common_clobbers"r0", "r1", "r2", "r3", "r4", "r5", "memory"and adding "r6", "r7", etc manually, depending on the test.
So maybe let's add it upfront as
__clobber_commonas well?
Will do.
Quoted 14 lines
But changes look good to me:
Acked-by Andrii Nakryiko <[email protected]>Quoted 9 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +3
-1+#define __imm (name) [name]"i"(name) +#define __imm_addr (name) [name]"i"(&name) +#if defined(__TARGET_ARCH_x86)#define SYSCALL_WRAPPER 1#define SYS_PREFIX "__x64_" --2.38.2
Eduard Zingerman
maintainerRe: [PATCH bpf-next 4/4] selftests/bpf: check if verifier.c:check_ids() handles 64+5 ids
In reply to Andrii NakryikoQuoted 35 lines · Andrii Nakryiko
Quoted 19 lines · Eduard Zingerman
A simple program that allocates a bunch of unique register ids than branches. The goal is to confirm that idmap used in verifier.c:check_ids() has sufficient capacity to verify that branches converge to a same state.
Signed-off-by Eduard Zingerman <[email protected]>--- .../selftests/bpf/prog_tests/verifier.c | 12 +++ .../selftests/bpf/progs/check_ids_limits.c | 77 +++++++++++++++++++ 2 files changed, 89 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/verifier.c create mode 100644 tools/testing/selftests/bpf/progs/check_ids_limits.ctools/testing/selftests/bpf/prog_tests/verifier.c new file +0
-0tools/testing/selftests/bpf/prog_tests/verifier.c line 10
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/verifier.c new file +10
-0@@ -0,0 +1,12 @@ +// SPDX-License-Identifier: GPL-2.0-only +#include <test_progs.h> + +#include "check_ids_limits.skel.h" + +#define TEST_SET (skel) \ + void test_##skel(void) \ + { \ + RUN_TESTS(skel); \ + }Let's not use such trivial macros, please. It makes grepping for tests much harder and saves 1 line of code only. Let's define funcs explicitly?
Quoted 1 line
I'm also surprised it works at all (it does, right?), because
Makefile
Nope, it doesn't work and it is embarrassing. I've tested w/o this macro and only added it before final tests run. And didn't check the log. Thank you for catching it. Will remove this macro.
Quoted 106 lines
is grepping explicitly for
void (serial_)test_xxxpattern when generating a list of tests. So this shouldn't have worked, unless I'm missing something.Quoted 16 lines
tools/testing/selftests/bpf/prog_tests/verifier.c new file +2
-0+ +TEST_SET (check_ids_limits)tools/testing/selftests/bpf/progs/check_ids_limits.c new file +8
-0@@ -0,0 +1,77 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <linux/bpf.h> +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +struct map_struct { + __uint(type, BPF_MAP_TYPE_ARRAY);tools/testing/selftests/bpf/progs/check_ids_limits.c line 18
Quoted 10 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +10
-0+__uint (max_entries,1 ); +__type (key, int); +__type (value, int); +} map SEC(".maps"); + +/* Make sure that verifier.c:check_ids() can handle (almost) maximal +* number of ids. +*/ +SEC("?raw_tp") +__naked __test_state_freq __log_level(2) __msg("43 to 45: safe")it's not clear what's special about 43 -> 45 jump?
can we also validate that id=69 was somewhere in verifier output? which would require multiple
__msgsupport, of course.Quoted 30 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +30
-0+int allocate_many_ids (void ) +{ +/* Use bpf_map_lookup_elem() as a way to get a bunch of values +* with unique ids. +*/ +#define __lookup (dst) \ + "r1 = %[map] ll;" \ + "r2 = r10;" \ + "r2 += -8;" \ + "call %[bpf_map_lookup_elem];" \ + dst " = r0;" + asmvolatile ( +"r0 = 0;" +"*(u64*)(r10 - 8) = r0;" +"r7 = r10;" +"r8 = 0;" +/* Spill 64 bpf_map_lookup_elem() results to stack, +* each lookup gets its own unique id. +*/ +"write_loop:" +"r7 += -8;" +"r8 += -8;" + __lookup("*(u64*)(r7 + 0)") +"if r8 != -512 goto write_loop;" +/* No way to source unique ids for r1-r5 as these +* would be clobbered by bpf_map_lookup_elem call, +* so make do with 64+5 unique ids. +*/ + __lookup("r6") +__lookup ("r7" )tools/testing/selftests/bpf/progs/check_ids_limits.c line 58
Quoted 10 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +10
-0+ __lookup("r8") + __lookup("r9") +__lookup ("r0" ) +/* Create a branching point for states comparison. */ +/* 43: */ "if r0 != 0 goto skip_one;" +/* Read all registers and stack spills to make these +* persist in the checkpoint state. +*/ +"r0 = r0;" +"skip_one:" where you trying to just create a checkpoint here? given
__test_state_freqthe simplest way would be justgoto +0;
no?
Quoted 22 lines
tools/testing/selftests/bpf/progs/check_ids_limits.c new file +19
-1+/* 45: */ "r0 = r6;" +"r0 = r7;" +"r0 = r8;" +"r0 = r9;" +"r0 = r10;" +"r1 = 0;" +"read_loop:" +"r0 += -8;" +"r1 += -8;" +"r2 = *(u64*)(r0 + 0);" +"if r1 != -512 goto read_loop;" +"r0 = 0;" +"exit;" + : + : __imm(bpf_map_lookup_elem), +__imm_addr (map) + : __clobber_all); +#undef __lookup +} --2.38.2
Re: [PATCH bpf-next 1/4] selftests/bpf: support for BPF_F_TEST_STATE_FREQ in test_loader
In reply to Eduard ZingermanQuoted 18 lines · Eduard Zingerman
Quoted 7 lines · Andrii Nakryiko
Quoted 5 lines · Eduard Zingerman
Adds a macro
__test_state_freq, the macro expands as abtf_decl_tagof a special form that instructstest_loaderthat the flagBPF_F_TEST_STATE_FREQhas to be passed to BPF verifier when program is loaded.Quoted 8 lines
I needed similar capabilities locally, but I went a slightly different direction. Instead of defining custom macros and logic, I define just
__flags(X)macro and then parse flags either by their symbolic name (or just integer value, which might be useful sometimes for development purposes). I've also added support for matching multiple messages sequentially which locally is in the same commit. Feel free to ignore that part, but I think it's useful as well. So WDYT about the below?
Quoted 2 lines
Makes total sense. I can replace my patch with your patch in the patchset, or just wait until your changes land.
Mine will take a bit more time and will be stuck in discussions anyways, so the more prerequisites land before it the better. Please go ahead and add it to your patch set.
Quoted 3 lines
Quoted 3 lines