selftests/bpf: two scale tests
Subsystems (5)
Alexei Starovoitov
maintainerPATCH 1/1 selftests/bpf: two scale tests
Add two tests to check that sequence of 1024 jumps is verifiable.
--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++ 2 files changed, 88 insertions(+) create mode 100644 tools/testing/selftests/bpf/verifier/scale.c
tools/testing/selftests/bpf/test_verifier.c +70 -0
@@ -208,6 +208,76 @@ static void bpf_fill_rand_ld_dw(struct bpf_test *self) self->retval = (uint32_t )res; } +/* test the sequence of 1k jumps */ +static void bpf_fill_scale1 (struct bpf_test *self) +{ +struct bpf_insn *insn = self->fill_insns; +int i =0 , k =0 ; + + insn[i++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); +/* test to check that the sequence of 1024 jumps is acceptable */ +while (k++ <1024 ) { + insn[i++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_get_prandom_u32); + insn[i++] =BPF_JMP_IMM (BPF_JGT ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); + insn[i++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ); + insn[i++] =BPF_STX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_6 , +-8 * (k %64 +1 )); + } +/* every jump adds 1024 steps to insn_processed, so to stay exactly +* within 1m limit add MAX_TEST_INSNS - 1025 MOVs and 1 EXIT +*/ +while (i <MAX_TEST_INSNS -1025 ) + insn[i++] =BPF_ALU32_IMM (BPF_MOV ,BPF_REG_0 ,42 ); + insn[i] =BPF_EXIT_INSN (); + self->prog_len = i +1 ; + self->retval =42 ; +} + +/* test the sequence of 1k jumps in inner most function (function depth 8)*/ +static void bpf_fill_scale2 (struct bpf_test *self) +{ +struct bpf_insn *insn = self->fill_insns; +int i =0 , k =0 ; + +#define FUNC_NEST 7 +for (k =0 ; k <FUNC_NEST ; k++) { + insn[i++] =BPF_CALL_REL (1 ); + insn[i++] =BPF_EXIT_INSN (); + } + insn[i++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); +/* test to check that the sequence of 1024 jumps is acceptable */ +while (k++ <1024 ) { + insn[i++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_get_prandom_u32); + insn[i++] =BPF_JMP_IMM (BPF_JGT ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); + insn[i++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ); + insn[i++] =BPF_STX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_6 , +-8 * (k % (64 -4 *FUNC_NEST ) +1 )); + } +/* every jump adds 1024 steps to insn_processed, so to stay exactly +* within 1m limit add MAX_TEST_INSNS - 1025 MOVs and 1 EXIT +*/ +while (i <MAX_TEST_INSNS -1025 ) + insn[i++] =BPF_ALU32_IMM (BPF_MOV ,BPF_REG_0 ,42 ); + insn[i] =BPF_EXIT_INSN (); + self->prog_len = i +1 ; + self->retval =42 ; +} + +static void bpf_fill_scale (struct bpf_test *self) +{ +switch (self->retval) { +case 1 : +return bpf_fill_scale1 (self); +case 2 : +return bpf_fill_scale2 (self); +default : + self->prog_len =0 ; +break ; + } +} +/* BPF_SK_LOOKUP contains 13 instructions, if you need to fix up maps */ #define BPF_SK_LOOKUP (func) \/* struct bpf_sock_tuple tuple = {} */ \
tools/testing/selftests/bpf/verifier/scale.c new file +18 -0
@@ -0,0 +1,18 @@ +{ + "scale: scale test 1", + .insns = { }, + .data = { }, + .fill_helper = bpf_fill_scale, + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .result = ACCEPT, + .retval =1 , +}, +{ +"scale: scale test 2" , + .insns = { }, + .data = { }, + .fill_helper = bpf_fill_scale, + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .result = ACCEPT, + .retval = 2, +},
Signature · 1 line
2.20.0
Quoted 4 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>
Shall we add a test that go beyond the 1M limit?
Quoted 114 lines
--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++ 2 files changed, 88 insertions(+) create mode 100644 tools/testing/selftests/bpf/verifier/scale.ctools/testing/selftests/bpf/test_verifier.c +70
-0@@ -208,6 +208,76 @@ static void bpf_fill_rand_ld_dw(struct bpf_test *self) self->retval = (uint32_t )res; } +/* test the sequence of 1k jumps */ +static void bpf_fill_scale1 (struct bpf_test *self) +{ +struct bpf_insn *insn = self->fill_insns; +int i =0 , k =0 ; + + insn[i++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); +/* test to check that the sequence of 1024 jumps is acceptable */ +while (k++ <1024 ) { + insn[i++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_get_prandom_u32); + insn[i++] =BPF_JMP_IMM (BPF_JGT ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); + insn[i++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ); + insn[i++] =BPF_STX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_6 , +-8 * (k %64 +1 )); + } +/* every jump adds 1024 steps to insn_processed, so to stay exactly +* within 1m limit add MAX_TEST_INSNS - 1025 MOVs and 1 EXIT +*/ +while (i <MAX_TEST_INSNS -1025 ) + insn[i++] =BPF_ALU32_IMM (BPF_MOV ,BPF_REG_0 ,42 ); + insn[i] =BPF_EXIT_INSN (); + self->prog_len = i +1 ; + self->retval =42 ; +} + +/* test the sequence of 1k jumps in inner most function (function depth 8)*/ +static void bpf_fill_scale2 (struct bpf_test *self) +{ +struct bpf_insn *insn = self->fill_insns; +int i =0 , k =0 ; + +#define FUNC_NEST 7 +for (k =0 ; k <FUNC_NEST ; k++) { + insn[i++] =BPF_CALL_REL (1 ); + insn[i++] =BPF_EXIT_INSN (); + } + insn[i++] =BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ); +/* test to check that the sequence of 1024 jumps is acceptable */ +while (k++ <1024 ) { + insn[i++] =BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_get_prandom_u32); + insn[i++] =BPF_JMP_IMM (BPF_JGT ,BPF_REG_0 ,bpf_semi_rand_get (),2 ); + insn[i++] =BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_10 ); + insn[i++] =BPF_STX_MEM (BPF_DW ,BPF_REG_1 ,BPF_REG_6 , +-8 * (k % (64 -4 *FUNC_NEST ) +1 )); + } +/* every jump adds 1024 steps to insn_processed, so to stay exactly +* within 1m limit add MAX_TEST_INSNS - 1025 MOVs and 1 EXIT +*/ +while (i <MAX_TEST_INSNS -1025 ) + insn[i++] =BPF_ALU32_IMM (BPF_MOV ,BPF_REG_0 ,42 ); + insn[i] =BPF_EXIT_INSN (); + self->prog_len = i +1 ; + self->retval =42 ; +} + +static void bpf_fill_scale (struct bpf_test *self) +{ +switch (self->retval) { +case 1 : +return bpf_fill_scale1 (self); +case 2 : +return bpf_fill_scale2 (self); +default : + self->prog_len =0 ; +break ; + } +} +/* BPF_SK_LOOKUP contains 13 instructions, if you need to fix up maps */ #define BPF_SK_LOOKUP (func) \/* struct bpf_sock_tuple tuple = {} */ \tools/testing/selftests/bpf/verifier/scale.c new file +18
-1@@ -0,0 +1,18 @@ +{ + "scale: scale test 1", + .insns = { }, + .data = { }, + .fill_helper = bpf_fill_scale, + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .result = ACCEPT, + .retval =1 , +}, +{ +"scale: scale test 2" , + .insns = { }, + .data = { }, + .fill_helper = bpf_fill_scale, + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .result = ACCEPT, + .retval = 2, +}, --2.20.0
Quoted 9 lines · Song Liu
Quoted 4 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>Acked-by Song Liu <[email protected]>Shall we add a test that go beyond the 1M limit?
1m is not uapi limit. I'm working on the doc patch to stress that point. Adding a test to check that it fails at 1m would kinda imply that it is uapi and I very much want to avoid that.
The purpose of these tests is to stress the verifier to its internal limits, but not more.
In particular in these two tests 1024, 8, 512, and another 1M are limits too.
Quoted 12 lines · Alexei Starovoitov
Quoted 9 lines · Song Liu
Quoted 4 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>Acked-by Song Liu <[email protected]>Shall we add a test that go beyond the 1M limit?
Quoted 9 lines
1m is not uapi limit. I'm working on the doc patch to stress that point. Adding a test to check that it fails at 1m would kinda imply that it is uapi and I very much want to avoid that.
The purpose of these tests is to stress the verifier to its internal limits, but not more.
In particular in these two tests 1024, 8, 512, and another 1M are limits too.
Yeah, this makes sense. Thanks for the explanation.
Song
Quoted 3 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>
Applied, thanks!
32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
In reply to Alexei StarovoitovQuoted 6 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++
I am rebasing 32-bit opt pass on top of latest bpf-next and found these new tests take more than 20 minutes to run and had not finished after that.
The reason the following insn filling insde bpf_fill_scale1 is generating nearly 1M insn whose results are recognized as safe to be poisoned.
bpf_fill_scale1:
while (i < MAX_TEST_INSNS - 1025)
insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);For each hi32 poisoning, there will be one call to "bpf_patch_insn_data" which actually is not cheap (adjust jump insns, insn aux info etc). Now, 1M call to it has exhausted server resources as described, 20minutes running still not finished.
For real world applications, we don't do hi32 poisoning, and there isn't much lo32 zext. Benchmarking those bpf programs inside Cilium shows the final zext pass adds about 8% ~ 15% verification time.
The zext pass based on top of "bpf_patch_insn_data" looks more and more is not the best approach to utilize the read32 analysis results.
Previously, in v1 cover letter, I listed some of my other thoughts on how to utilize the liveness analysis results:
1 Minor change on back-end JIT hook, also pass aux_insn information to
back-ends so they could have per insn information and they could do zero extension for the marked insn themselves using the most efficient native insn.
2 Introduce zero extension insn for eBPF. Then verifier could insert
the new zext insn instead of lshift + rshift. zext could be JITed more efficiently.
3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
and turn them into native zext.
More thinking on this, perhaps we should just go with approach 1 which actually doesn't require much change I guess.
There actually is no need to change back-end JIT hook. After we finished liveness analysis, just copy insn zext info from env->aux_insn_data.zext_dst to new dynamic allocated storage inside something like "bpf_prog->aux->insn_zext_dst" (a bool * pointer, with 1 * prog_len storage). Such optimization information then is available to JIT back-end automatically, because the currect JIT hook is
struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
After bpf_int_jit_compile finished, the dynamic allocated storage could be freed, no need to keep it along with bpf_prog's life time.
Backends also have finer control on how to do zero extension so concerns like
https://www.spinics.net/lists/netdev/msg564489.html could be addressed naturally and no need to introduce new BPF zero-extension instruction.
I am intended to send out the updated version using approach 1 so we could see how it looks like, comments?
Regards,
Jiong
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 40 lines · Jiong Wang
Quoted 6 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++I am rebasing 32-bit opt pass on top of latest bpf-next and found these new tests take more than 20 minutes to run and had not finished after that.
The reason the following insn filling insde
bpf_fill_scale1is generating nearly 1M insn whose results are recognized as safe to be poisoned.bpf_fill_scale1: while (i < MAX_TEST_INSNS - 1025) insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);For each hi32 poisoning, there will be one call to "
bpf_patch_insn_data" which actually is not cheap (adjust jump insns, insn aux info etc). Now, 1M call to it has exhausted server resources as described, 20minutes running still not finished.For real world applications, we don't do hi32 poisoning, and there isn't much lo32 zext. Benchmarking those bpf programs inside Cilium shows the final zext pass adds about 8% ~ 15% verification time.
The zext pass based on top of "
bpf_patch_insn_data" looks more and more is not the best approach to utilize the read32 analysis results.Previously, in v1 cover letter, I listed some of my other thoughts on how to utilize the liveness analysis results:
1 Minor change on back-end JIT hook, also pass
aux_insninformation to
back-ends so they could have per insn information and they could do zero extension for the marked insn themselves using the most efficient native insn.
Quoted 6 lines
2 Introduce zero extension insn for eBPF. Then verifier could insert
the new zext insn instead of lshift + rshift. zext could be JITed more efficiently.3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
and turn them into native zext.
all options sounds like hacks to workaround inefficient bpf_patch_insn_data(). Especially option 2 will work only because single insn is replaced with another insn ?
Let's fix the algo of bpf_patch_insn_data() instead, so that 1 insn -> 2+ insn is also fast.
The main point of bumping the internal limits to 1M and these tests was to expose such algorithmic inefficiencies.
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 45 lines · Alexei Starovoitov
Quoted 44 lines · Jiong Wang
Quoted 6 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++I am rebasing 32-bit opt pass on top of latest bpf-next and found these new tests take more than 20 minutes to run and had not finished after that.
The reason the following insn filling insde
bpf_fill_scale1is generating nearly 1M insn whose results are recognized as safe to be poisoned.bpf_fill_scale1: while (i < MAX_TEST_INSNS - 1025) insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);For each hi32 poisoning, there will be one call to "
bpf_patch_insn_data" which actually is not cheap (adjust jump insns, insn aux info etc). Now, 1M call to it has exhausted server resources as described, 20minutes running still not finished.For real world applications, we don't do hi32 poisoning, and there isn't much lo32 zext. Benchmarking those bpf programs inside Cilium shows the final zext pass adds about 8% ~ 15% verification time.
The zext pass based on top of "
bpf_patch_insn_data" looks more and more is not the best approach to utilize the read32 analysis results.Previously, in v1 cover letter, I listed some of my other thoughts on how to utilize the liveness analysis results:
1 Minor change on back-end JIT hook, also pass
aux_insninformation to
back-ends so they could have per insn information and they could do zero extension for the marked insn themselves using the most efficient native insn.2 Introduce zero extension insn for eBPF. Then verifier could insert
the new zext insn instead of lshift + rshift. zext could be JITed more efficiently.
Quoted 6 lines
Quoted 2 lines
3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
and turn them into native zext.all options sounds like hacks to workaround inefficient
bpf_patch_insn_data(). Especially option 2 will work only because single insn is replaced with another insn ?
Option 1 should be a generic solution. It is passing verifier analysis results generated by insn walk down to JIT back-ends. The information passed down could be any analysis result useful for JIT code-gen.
Quoted 2 lines
Let's fix the algo of
bpf_patch_insn_data()instead, so that 1 insn -> 2+ insn is also fast.
The issue with 1 insn -> 2+ insn should be calling of bpf_adj_branches which is doing another for_each_insn_in_prog traversal, so the zext insertion becomes something like:
for_each_insn_in_prog
...
if (zext)
...
for_each_insn_in_progwhich is quadratic. One solution is we chain all branch insns during previous insn traversal in for example cfg check, and keep the information somewhere info bpf_prog (env->insn_aux_data is a good place to keep such information, but insn patch helpers are supposed to work with bpf_prog) then bpf_adj_branches could traversal this chain instead of iterating through all insns.
Regards,
Jiong
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 69 lines · Jiong Wang
Quoted 45 lines · Alexei Starovoitov
Quoted 44 lines · Jiong Wang
Quoted 6 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>---
tools/testing/selftests/bpf/test_verifier.c| 70 ++++++++++++++++++++tools/testing/selftests/bpf/verifier/scale.c| 18 +++++I am rebasing 32-bit opt pass on top of latest bpf-next and found these new tests take more than 20 minutes to run and had not finished after that.
The reason the following insn filling insde
bpf_fill_scale1is generating nearly 1M insn whose results are recognized as safe to be poisoned.
bpf_fill_scale1:while (i < MAX_TEST_INSNS - 1025) insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);For each hi32 poisoning, there will be one call to "
bpf_patch_insn_data" which actually is not cheap (adjust jump insns, insn aux info etc). Now, 1M call to it has exhausted server resources as described, 20minutes running still not finished.For real world applications, we don't do hi32 poisoning, and there isn't much lo32 zext. Benchmarking those bpf programs inside Cilium shows the final zext pass adds about 8% ~ 15% verification time.
The zext pass based on top of "
bpf_patch_insn_data" looks more and more is not the best approach to utilize the read32 analysis results.Previously, in v1 cover letter, I listed some of my other thoughts on how to utilize the liveness analysis results:
1 Minor change on back-end JIT hook, also pass
aux_insninformation to
back-ends so they could have per insn information and they could do zero extension for the marked insn themselves using the most efficient native insn.2 Introduce zero extension insn for eBPF. Then verifier could insert
the new zext insn instead of lshift + rshift. zext could be JITed more efficiently.Quoted 6 lines
Quoted 2 lines
3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
and turn them into native zext.all options sounds like hacks to workaround inefficient
bpf_patch_insn_data(). Especially option 2 will work only because single insn is replaced with another insn ?Option 1 should be a generic solution. It is passing verifier analysis results generated by insn walk down to JIT back-ends. The information passed down could be any analysis result useful for JIT code-gen.
Quoted 2 lines
Let's fix the algo of
bpf_patch_insn_data()instead, so that 1 insn -> 2+ insn is also fast.The issue with 1 insn -> 2+ insn should be calling of
bpf_adj_brancheswhich is doing anotherfor_each_insn_in_progtraversal, so the zext insertion becomes something like:
Quoted 7 lines
for_each_insn_in_prog
...if (zext) ... for_each_insn_in_progwhich is quadratic. One solution
s/solution/mitigation/
Quoted 9 lines
is we chain all branch insns during
previous insn traversal in for example cfg check, and keep the information somewhere infobpf_prog(env->insn_aux_datais a good place to keep such information, but insn patch helpers are supposed to work withbpf_prog) thenbpf_adj_branchescould traversal this chain instead of iterating through all insns.Regards,
Jiong
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
In reply to Jiong WangQuoted 72 lines · Jiong Wang
Quoted 45 lines · Alexei Starovoitov
Quoted 44 lines · Jiong Wang
Quoted 6 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++I am rebasing 32-bit opt pass on top of latest bpf-next and found these new tests take more than 20 minutes to run and had not finished after that.
The reason the following insn filling insde
bpf_fill_scale1is generating nearly 1M insn whose results are recognized as safe to be poisoned.bpf_fill_scale1: while (i < MAX_TEST_INSNS - 1025) insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);For each hi32 poisoning, there will be one call to "
bpf_patch_insn_data" which actually is not cheap (adjust jump insns, insn aux info etc). Now, 1M call to it has exhausted server resources as described, 20minutes running still not finished.For real world applications, we don't do hi32 poisoning, and there isn't much lo32 zext. Benchmarking those bpf programs inside Cilium shows the final zext pass adds about 8% ~ 15% verification time.
The zext pass based on top of "
bpf_patch_insn_data" looks more and more is not the best approach to utilize the read32 analysis results.Previously, in v1 cover letter, I listed some of my other thoughts on how to utilize the liveness analysis results:
1 Minor change on back-end JIT hook, also pass
aux_insninformation to
back-ends so they could have per insn information and they could do zero extension for the marked insn themselves using the most efficient native insn.2 Introduce zero extension insn for eBPF. Then verifier could insert
the new zext insn instead of lshift + rshift. zext could be JITed more efficiently.Quoted 6 lines
Quoted 2 lines
3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
and turn them into native zext.all options sounds like hacks to workaround inefficient
bpf_patch_insn_data(). Especially option 2 will work only because single insn is replaced with another insn ?Option 1 should be a generic solution. It is passing verifier analysis results generated by insn walk down to JIT back-ends. The information passed down could be any analysis result useful for JIT code-gen.
Quoted 2 lines
Let's fix the algo of
bpf_patch_insn_data()instead, so that 1 insn -> 2+ insn is also fast.The issue with 1 insn -> 2+ insn should be calling of
bpf_adj_brancheswhich is doing anotherfor_each_insn_in_progtraversal, so the zext insertion becomes something like:
for_each_insn_in_prog
...if (zext) ... for_each_insn_in_prog
Quoted 6 lines
which is quadratic. One solution is we chain all branch insns during previous insn traversal in for example cfg check, and keep the information somewhere info
bpf_prog(env->insn_aux_datais a good place to keep such information, but insn patch helpers are supposed to work withbpf_prog) thenbpf_adj_branchescould traversal this chain instead of iterating through all insns.
I don't think it will make it much faster. There could be just as many jumps as there are instructions.
Note that bpf_patch_insn_single() is calling bpf_adj_branches() twice too. And dead_code + convert_ctx + fixup_bpf_calls are calling bpf_patch_insn_single() a lot.
How about before dead_code pass we convert the program into basic-block format, patch it all, and then convert from bb back to offsets. Patching will become very cheap, since no loop over program will be necessary. A jump from bb-N to bb-M will stay as-is regardless of amount of patching was done inside each bb.
The loops inside these patching passes will be converted from:
for (i = 0; i < insn_cnt; i++, insn++)
into:
for each bb
for each insn in bb
As far as option 1 "also pass aux_insn information to JITs"...
in theory it's fine, but looks like big refactoring to existing code.
So if you want to make this bb conversion as step 2 and unblock the current patch set faster I suggest to go with option 2 "Introduce zero extension insn".
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 73 lines · Alexei Starovoitov
Quoted 72 lines · Jiong Wang
Quoted 45 lines · Alexei Starovoitov
Quoted 44 lines · Jiong Wang
Quoted 6 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++I am rebasing 32-bit opt pass on top of latest bpf-next and found these new tests take more than 20 minutes to run and had not finished after that.
The reason the following insn filling insde
bpf_fill_scale1is generating nearly 1M insn whose results are recognized as safe to be poisoned.bpf_fill_scale1: while (i < MAX_TEST_INSNS - 1025) insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);For each hi32 poisoning, there will be one call to "
bpf_patch_insn_data" which actually is not cheap (adjust jump insns, insn aux info etc). Now, 1M call to it has exhausted server resources as described, 20minutes running still not finished.For real world applications, we don't do hi32 poisoning, and there isn't much lo32 zext. Benchmarking those bpf programs inside Cilium shows the final zext pass adds about 8% ~ 15% verification time.
The zext pass based on top of "
bpf_patch_insn_data" looks more and more is not the best approach to utilize the read32 analysis results.Previously, in v1 cover letter, I listed some of my other thoughts on how to utilize the liveness analysis results:
1 Minor change on back-end JIT hook, also pass
aux_insninformation to
back-ends so they could have per insn information and they could do zero extension for the marked insn themselves using the most efficient native insn.2 Introduce zero extension insn for eBPF. Then verifier could insert
the new zext insn instead of lshift + rshift. zext could be JITed more efficiently.Quoted 6 lines
Quoted 2 lines
3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
and turn them into native zext.all options sounds like hacks to workaround inefficient
bpf_patch_insn_data(). Especially option 2 will work only because single insn is replaced with another insn ?Option 1 should be a generic solution. It is passing verifier analysis results generated by insn walk down to JIT back-ends. The information passed down could be any analysis result useful for JIT code-gen.
Quoted 2 lines
Let's fix the algo of
bpf_patch_insn_data()instead, so that 1 insn -> 2+ insn is also fast.The issue with 1 insn -> 2+ insn should be calling of
bpf_adj_brancheswhich is doing anotherfor_each_insn_in_progtraversal, so the zext insertion becomes something like:
for_each_insn_in_prog
...if (zext) ... for_each_insn_in_prog
Quoted 6 lines
Quoted 6 lines
which is quadratic. One solution is we chain all branch insns during previous insn traversal in for example cfg check, and keep the information somewhere info
bpf_prog(env->insn_aux_datais a good place to keep such information, but insn patch helpers are supposed to work withbpf_prog) thenbpf_adj_branchescould traversal this chain instead of iterating through all insns.
Thanks very much for the feedbacks.
Quoted 2 lines
I don't think it will make it much faster. There could be just as many jumps as there are instructions.
Benchmarked a basic implemention on a couple of bpf programs in Cilium repo (the impl is a relocation list kept in a array built as by-product of check_subprogs. during patch, walk this relocation list instead of all insns. Then calculate time by 10 times run and take average)
- The time spent on zero-extension pass is ~30% less
- The time spent on convert_ctx_accesses + fixup_bpf_call + fixup_call_args is ~15% less
- The time spent on dead code elim pass is not changed which makes sense as dead code is rare so patch infra is not triggered much.
So, looks like could help a little bit on daily program, but agree no fundamental improvements, it is still N(insn_needs_patch) * N(branch), and both N could go very big.
Quoted 5 lines
Note that
bpf_patch_insn_single()is callingbpf_adj_branches()twice too. Anddead_code+convert_ctx+fixup_bpf_callsare callingbpf_patch_insn_single()a lot.
How about beforedead_codepass we convert the program into basic-block format, patch it all, and then convert from bb back to offsets.
Quoted 8 lines
Patching will become very cheap, since no loop over program will be necessary. A jump from bb-N to bb-M will stay as-is regardless of amount of patching was done inside each bb.
The loops inside these patching passes will be converted from:
for (i = 0; i <insn_cnt; i++, insn++)
into:
for each bb
for each insn in bb
Interesting. If I am understanding correctly, BB then needs to support dynamic insn buffer resize. And after all insn patching finished, all BBs are finalized, we then linearized BBs (in a best order) to generate the final bpf image.
Quoted 2 lines
As far as option 1 "also pass
aux_insninformation to JITs"... in theory it's fine, but looks like big refactoring to existing code.
Will do quick explore, might turn out to be small change.
Quoted 3 lines
So if you want to make this bb conversion as step 2 and unblock the current patch set faster I suggest to go with option 2 "Introduce zero extension insn".
A second think, even zero extension insn introduced, it is inserted after the sub-register write insn, so we are still doing insert *not* replacement, insn_delta inside bpf_patch_insn_single will be 1, so the slow path will always be taken (memmove + bpf_prog_realloc + 2 x bpf_adj_branches).
For the 1M-scale test, bpf_patch_insn_single is triggered because of hi32 poisoning, not lo32 zext. So we just need to change MOV32 to MOV64 in the testcase which doesn't break the initial testing purpose of this testcase from my understanding. This then could avoid 1M call to bpf_patch_insn_single and pass the test after 32-bit opt patch set applied.
Without this change and with hi32 randomization enabled, scale tests will still hang before insn patch infra improved.
@@ -228,7 +228,7 @@ static void bpf_fill_scale1(struct bpf_test *self)
- insn[i++] = BPF_ALU32_IMM(BPF_MOV, BPF_REG_0, 42);
+ insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);
This is change is not to paperover the underlying issue. We now know the existing insn patch infra doesn't scale to million level, so could work on improving it in the next step.
At the same time the issue exposed from hi32 poisoning does raise alarm that there could be the same issue for lo32 zext, therefore this patch set doesn't scale if there are lots of insns to be zero extended, even though this may not happen in real world bpf prog.
IMHO, avoid using insn patching when possible might always be better. So, if option 1 turns out to also generate clean patch set and introduce small changes, I am going to follow it in the update version.
Please let me know if you have different opinion.
Regards,
Jiong
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 14 lines · Jiong Wang
Quoted 5 lines · Alexei Starovoitov
Note that
bpf_patch_insn_single()is callingbpf_adj_branches()twice too. Anddead_code+convert_ctx+fixup_bpf_callsare callingbpf_patch_insn_single()a lot.
How about beforedead_codepass we convert the program into basic-block format, patch it all, and then convert from bb back to offsets.Quoted 8 lines
Patching will become very cheap, since no loop over program will be necessary. A jump from bb-N to bb-M will stay as-is regardless of amount of patching was done inside each bb.
The loops inside these patching passes will be converted from:
for (i = 0; i <insn_cnt; i++, insn++)
into:
for each bb
for each insn in bb
Quoted 4 lines
Interesting. If I am understanding correctly, BB then needs to support dynamic insn buffer resize. And after all insn patching finished, all BBs are finalized, we then linearized BBs (in a best order) to generate the final bpf image.
Does any verifier metadata ever take the index of an insn that was added by patching? If not, then we could have, instead of an array of insns, an array of list_heads, each of which is a list of insns (plus aux data etc.). At entry the original program is converted into an array of 1-element lists. On patching we edit the list, which doesn't change the index of any insn. Then after all insn patching finishes, we linearise as above.
Just a thought,
-Ed
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 19 lines · Edward Cree
Quoted 14 lines · Jiong Wang
Quoted 5 lines · Alexei Starovoitov
Note that
bpf_patch_insn_single()is callingbpf_adj_branches()twice too. Anddead_code+convert_ctx+fixup_bpf_callsare callingbpf_patch_insn_single()a lot.
How about beforedead_codepass we convert the program into basic-block format, patch it all, and then convert from bb back to offsets.Quoted 8 lines
Patching will become very cheap, since no loop over program will be necessary. A jump from bb-N to bb-M will stay as-is regardless of amount of patching was done inside each bb.
The loops inside these patching passes will be converted from:
for (i = 0; i <insn_cnt; i++, insn++)
into:
for each bb
for each insn in bbQuoted 4 lines
Interesting. If I am understanding correctly, BB then needs to support dynamic insn buffer resize. And after all insn patching finished, all BBs are finalized, we then linearized BBs (in a best order) to generate the final bpf image.
Quoted 6 lines
Does any verifier metadata ever take the index of an insn that was added by patching? If not, then we could have, instead of an array of insns, an array of
list_heads, each of which is a list of insns (plus aux data etc.). At entry the original program is converted into an array of 1-element lists. On patching we edit the list, which doesn't change the index of any insn. Then after all insn patching finishes, we linearise as above.
Interesting idea. It can be optimized further:
instead of converting all insns into lists of 1 before all patching it can be done on demand:
convert from insn to list only when patching is needed. Patched insn becomes a pointer to a block of new insns. We have reserved opcodes to recognize such situation. The question is how to linearise it once at the end?
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 3 lines · Alexei Starovoitov
instead of converting all insns into lists of 1 before all patching it can be done on demand:
convert from insn to list only when patching is needed.
Makes sense.
Quoted 2 lines
Patched insn becomes a pointer to a block of new insns. We have reserved opcodes to recognize such situation.
It's not clear to me where you can fit everything though. The pointer is 64 bits, which is the same as struct bpf_insn. Are you suggesting relying on kernel pointers always starting 0xff?
Quoted 1 line
The question is how to linearise it once at the end?
Walk the old prog once to calculate out_insn_idx for each in_insn (since we will only ever be jumping to the first insn of a list (or to a non-list insn), that's all we need), as well as out_len. Allocate enough pages for out_len (let's not try to do any of this in-place, that would be painful), then walk the old prog to copy it insn-by-insn into the new one, recalculating any jump offsets by looking up the dest insn's out_insn_idx and subtracting our own out_insn_idx (plus an offset if we're not the first insn in the list of course). While we're at it we can also fix up e.g. linfo[].insn_off: if in_insn_idx matches linfo[li_idx].insn_off, then set linfo[li_idx++].insn_off = out_insn_idx. If we still need aux_data at this point we can copy that across too. Runtime O(out_len), and gets rid of all the adjusts on patch_insn_single — branches, linfo, subprog_starts, aux_data. Have I missed anything? If I have time I'll put together an RFC patch in the next few days.
-Ed
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
In reply to Jiong WangQuoted 117 lines · Jiong Wang
Quoted 73 lines · Alexei Starovoitov
Quoted 72 lines · Jiong Wang
Quoted 45 lines · Alexei Starovoitov
Quoted 44 lines · Jiong Wang
Quoted 6 lines · Alexei Starovoitov
Add two tests to check that sequence of 1024 jumps is verifiable.
Signed-off-by Alexei Starovoitov <[email protected]>--- tools/testing/selftests/bpf/test_verifier.c | 70 ++++++++++++++++++++ tools/testing/selftests/bpf/verifier/scale.c | 18 +++++I am rebasing 32-bit opt pass on top of latest bpf-next and found these new tests take more than 20 minutes to run and had not finished after that.
The reason the following insn filling insde
bpf_fill_scale1is generating nearly 1M insn whose results are recognized as safe to be poisoned.bpf_fill_scale1: while (i < MAX_TEST_INSNS - 1025) insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);For each hi32 poisoning, there will be one call to "
bpf_patch_insn_data" which actually is not cheap (adjust jump insns, insn aux info etc). Now, 1M call to it has exhausted server resources as described, 20minutes running still not finished.For real world applications, we don't do hi32 poisoning, and there isn't much lo32 zext. Benchmarking those bpf programs inside Cilium shows the final zext pass adds about 8% ~ 15% verification time.
The zext pass based on top of "
bpf_patch_insn_data" looks more and more is not the best approach to utilize the read32 analysis results.Previously, in v1 cover letter, I listed some of my other thoughts on how to utilize the liveness analysis results:
1 Minor change on back-end JIT hook, also pass
aux_insninformation to
back-ends so they could have per insn information and they could do zero extension for the marked insn themselves using the most efficient native insn.2 Introduce zero extension insn for eBPF. Then verifier could insert
the new zext insn instead of lshift + rshift. zext could be JITed more efficiently.Quoted 6 lines
Quoted 2 lines
3 Otherwise JIT back-ends need to do peephole to catch lshift + rshift
and turn them into native zext.all options sounds like hacks to workaround inefficient
bpf_patch_insn_data(). Especially option 2 will work only because single insn is replaced with another insn ?Option 1 should be a generic solution. It is passing verifier analysis results generated by insn walk down to JIT back-ends. The information passed down could be any analysis result useful for JIT code-gen.
Quoted 2 lines
Let's fix the algo of
bpf_patch_insn_data()instead, so that 1 insn -> 2+ insn is also fast.The issue with 1 insn -> 2+ insn should be calling of
bpf_adj_brancheswhich is doing anotherfor_each_insn_in_progtraversal, so the zext insertion becomes something like:
for_each_insn_in_prog
...if (zext) ... for_each_insn_in_progQuoted 6 lines
Quoted 6 lines
which is quadratic. One solution is we chain all branch insns during previous insn traversal in for example cfg check, and keep the information somewhere info
bpf_prog(env->insn_aux_datais a good place to keep such information, but insn patch helpers are supposed to work withbpf_prog) thenbpf_adj_branchescould traversal this chain instead of iterating through all insns.Thanks very much for the feedbacks.
Quoted 2 lines
I don't think it will make it much faster. There could be just as many jumps as there are instructions.
Benchmarked a basic implemention on a couple of bpf programs in Cilium repo (the impl is a relocation list kept in a array built as by-product of
check_subprogs. during patch, walk this relocation list instead of all insns. Then calculate time by 10 times run and take average)- The time spent on zero-extension pass is ~30% less
- The time spent onconvert_ctx_accesses+fixup_bpf_call+fixup_call_argsis ~15% less
- The time spent on dead code elim pass is not changed which makes sense as dead code is rare so patch infra is not triggered much.So, looks like could help a little bit on daily program, but agree no fundamental improvements, it is still
N(insn_needs_patch)* N(branch), and both N could go very big.Quoted 5 lines
Note that
bpf_patch_insn_single()is callingbpf_adj_branches()twice too. Anddead_code+convert_ctx+fixup_bpf_callsare callingbpf_patch_insn_single()a lot.
How about beforedead_codepass we convert the program into basic-block format, patch it all, and then convert from bb back to offsets.Quoted 8 lines
Patching will become very cheap, since no loop over program will be necessary. A jump from bb-N to bb-M will stay as-is regardless of amount of patching was done inside each bb.
The loops inside these patching passes will be converted from:
for (i = 0; i <insn_cnt; i++, insn++)
into:
for each bb
for each insn in bb
Quoted 4 lines
Interesting. If I am understanding correctly, BB then needs to support dynamic insn buffer resize. And after all insn patching finished, all BBs are finalized, we then linearized BBs (in a best order) to generate the final bpf image.
dynamic BB resize could be done similar to existing prog resize. It grows in page increments.
Quoted 9 lines
Quoted 2 lines
As far as option 1 "also pass
aux_insninformation to JITs"... in theory it's fine, but looks like big refactoring to existing code.Will do quick explore, might turn out to be small change.
Quoted 3 lines
So if you want to make this bb conversion as step 2 and unblock the current patch set faster I suggest to go with option 2 "Introduce zero extension insn".
Quoted 5 lines
A second think, even zero extension insn introduced, it is inserted after the sub-register write insn, so we are still doing insert *not* replacement,
insn_deltainsidebpf_patch_insn_singlewill be 1, so the slow path will always be taken (memmove +bpf_prog_realloc+ 2 xbpf_adj_branches).
ahh. right.
Quoted 13 lines
For the 1M-scale test,
bpf_patch_insn_singleis triggered because of hi32 poisoning, not lo32 zext. So we just need to change MOV32 to MOV64 in the testcase which doesn't break the initial testing purpose of this testcase from my understanding. This then could avoid 1M call tobpf_patch_insn_singleand pass the test after 32-bit opt patch set applied.Without this change and with hi32 randomization enabled, scale tests will still hang before insn patch infra improved.
(quoted diff) +1
-1@@ -228,7 +228,7 @@ static void bpf_fill_scale1(struct bpf_test *self) - insn[i++] = BPF_ALU32_IMM(BPF_MOV, BPF_REG_0, 42); + insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);
Quoted 3 lines
This is change is not to paperover the underlying issue. We now know the existing insn patch infra doesn't scale to million level, so could work on improving it in the next step.
I'm hesitant to step back.
Do you see a program that can hit this patch_insn issue already? (I mean without your hi32/lo32 zext changes).
Quoted 10 lines
At the same time the issue exposed from hi32 poisoning does raise alarm that there could be the same issue for lo32 zext, therefore this patch set doesn't scale if there are lots of insns to be zero extended, even though this may not happen in real world bpf prog.
IMHO, avoid using insn patching when possible might always be better. So, if option 1 turns out to also generate clean patch set and introduce small changes, I am going to follow it in the update version.
Please let me know if you have different opinion.
if you can craft a test that shows patch_insn issue before your set, then it's ok to hack bpf_fill_scale1 to use alu64.
I would also prefer to go with option 2 (new zext insn) for JITs. I still don't have good feeling about option 1.
Exposing all of aux_data to JITs may become a headache
in the verifier development. It needs to be done carefully.
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 4 lines · Alexei Starovoitov
On Fri, Apr 26, 2019 at 02:06:33PM +0100, Jiong Wang wrote:
<snip>
Quoted 53 lines
Quoted 15 lines
Quoted 14 lines
Note that
bpf_patch_insn_single()is callingbpf_adj_branches()twice too. Anddead_code+convert_ctx+fixup_bpf_callsare callingbpf_patch_insn_single()a lot.
How about beforedead_codepass we convert the program into basic-block format, patch it all, and then convert from bb back to offsets. Patching will become very cheap, since no loop over program will be necessary. A jump from bb-N to bb-M will stay as-is regardless of amount of patching was done inside each bb.
The loops inside these patching passes will be converted from:
for (i = 0; i <insn_cnt; i++, insn++)
into:
for each bb
for each insn in bbQuoted 4 lines
Interesting. If I am understanding correctly, BB then needs to support dynamic insn buffer resize. And after all insn patching finished, all BBs are finalized, we then linearized BBs (in a best order) to generate the final bpf image.
dynamic BB resize could be done similar to existing prog resize. It grows in page increments.
Quoted 9 lines
Quoted 2 lines
As far as option 1 "also pass
aux_insninformation to JITs"... in theory it's fine, but looks like big refactoring to existing code.Will do quick explore, might turn out to be small change.
Quoted 3 lines
So if you want to make this bb conversion as step 2 and unblock the current patch set faster I suggest to go with option 2 "Introduce zero extension insn".
Quoted 5 lines
A second think, even zero extension insn introduced, it is inserted after the sub-register write insn, so we are still doing insert *not* replacement,
insn_deltainsidebpf_patch_insn_singlewill be 1, so the slow path will always be taken (memmove +bpf_prog_realloc+ 2 xbpf_adj_branches).ahh. right.
Quoted 13 lines
For the 1M-scale test,
bpf_patch_insn_singleis triggered because of hi32 poisoning, not lo32 zext. So we just need to change MOV32 to MOV64 in the testcase which doesn't break the initial testing purpose of this testcase from my understanding. This then could avoid 1M call tobpf_patch_insn_singleand pass the test after 32-bit opt patch set applied.Without this change and with hi32 randomization enabled, scale tests will still hang before insn patch infra improved.
(quoted diff) +1
-1@@ -228,7 +228,7 @@ static void bpf_fill_scale1(struct bpf_test *self) - insn[i++] = BPF_ALU32_IMM(BPF_MOV, BPF_REG_0, 42); + insn[i++] = BPF_ALU64_IMM(BPF_MOV, BPF_REG_0, 42);
Quoted 7 lines
Quoted 3 lines
This is change is not to paperover the underlying issue. We now know the existing insn patch infra doesn't scale to million level, so could work on improving it in the next step.
I'm hesitant to step back.
Do you see a program that can hit thispatch_insnissue already? (I mean without your hi32/lo32 zext changes).
No really on real world program which I feel won't do that much insn patching.
But on test_verifier, could be reproduced through enabling jit blinding, because the "scale" test contains imm insn.
For example, on bpf-next master, just run:
sysctl net/core/bpf_jit_enable=1
sysctl net/core/bpf_jit_harden=2
test_verifier 732 (732 is the test number for “scale: scale test1” on my env)
This enables constant blinding which also needs insn patching. test 732 contains nearly 1M BPF_MOV_IMM to be blinded, so could have similar effect as hi32 poisoning.
And benchmarking shows, once insn patch helper is called over 15000 times, then the user could fell the load delay, and when it is called around 50000 times, it will take about half minutes to finish verification.
15000 : 3s
45000 : 29s
95000 : 125s
195000: 712s
Quoted 6 lines
Quoted 6 lines
At the same time the issue exposed from hi32 poisoning does raise alarm that there could be the same issue for lo32 zext, therefore this patch set doesn't scale if there are lots of insns to be zero extended, even though this may not happen in real world bpf prog.
Quoted 8 lines
Quoted 5 lines
IMHO, avoid using insn patching when possible might always be better. So, if option 1 turns out to also generate clean patch set and introduce small changes, I am going to follow it in the update version.
Please let me know if you have different opinion.
if you can craft a test that shows
patch_insnissue before your set, then it's ok to hackbpf_fill_scale1to use alu64.
As described above, does the test_verifier 732 + jit blinding looks convincing?
Quoted 1 line
I would also prefer to go with option 2 (new zext insn) for JITs.
Got it.
Quoted 3 lines
I still don't have good feeling about option 1. Exposing all of
aux_datato JITs may become a headache in the verifier development. It needs to be done carefully.
OK, understood.
Just for clarification, I thought to just add a field, something like "bool *zext_dst" inside bpf_prog_aux. Then only copy "env->insn_aux_data[*].zext_dst" to bpf_prog->aux->zext_dst, not copy all aux_data generated by verifier. The field in bpf_prog could latter be extended to a structure contains those analysis info verifier want to push down to JIT back-ends, and JIT back-end must free them as soon as JIT compilation is done.
Re: 32-bit zext time complexity (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 8 lines
Quoted 2 lines
if you can craft a test that shows
patch_insnissue before your set, then it's ok to hackbpf_fill_scale1to use alu64.As described above, does the
test_verifier732 + jit blinding looks convincing?Quoted 1 line
I would also prefer to go with option 2 (new zext insn) for JITs.
Got it.
I followed option 2 and have sent out v5 with latests changes/fixes:
The major changes are:
- introduced BPF_ZEXT, even though it doesn't resolve insn patch in-efficient, but could let JIT back-ends do optimal code-gen, and the change is small, so perhap just better to support it in this set.
- while look insn patch code, I feel patched-insn need to be conservatiely marked if any insn inside patch buffer define sub-register.
- Also fixed helper function return value handling bug. I am thinking helper function should have accurate return value type description, otherwise there could be bug. For example arm32 back-end just executes the native helper functions and doesn't do anything special on the return value. So a function returns u32 would only set native reg r0, not r1 in the pair. Then if the outside eBPF insn is casting it into u64, there needs to be zext.
- adjusted test_verifier to make sure it could pass on hosts w and w/o hw zext.
For more info, please see the cover letter and patch description at v5.
Thanks.
Regards,
Jiong
Re: 32-bit zext JIT efficiency (Was Re: [PATCH bpf-next] selftests/bpf: two scale tests)
Quoted 10 lines · Jiong Wang
Quoted 8 lines
Quoted 2 lines
if you can craft a test that shows
patch_insnissue before your set, then it's ok to hackbpf_fill_scale1to use alu64.As described above, does the
test_verifier732 + jit blinding looks convincing?Quoted 1 line
I would also prefer to go with option 2 (new zext insn) for JITs.
Got it.
I followed option 2 and have sent out v5 with latests changes/fixes:
Had done second look at various back-ends, now noticed one new issue, some arches are not consistent on implicit zext. For example, for s390, alu32 move could be JITed using single instruction "llgfr" which will do implicit zext, but alu32 move on PowerPC needs explicit zext. Then for riscv, all BPF_ALU | BPF_K needs zext but not for some of BPF_ALU | BPF_X. So, while these arches are generally better off after verifier zext insertion enabled, but there do have unnecessary zext inserted by verifier for them case by case.
Also, for 64-bit arches like PowerPC, S390 etc, they normally has zero extended load, so narrowed load doesn't need extra zext insn, but for 32-bit arches like arm, narrowed load always need explicit zext.
All these differences are because of BPF_ALU32 or BPF_LDX + B | H | W will be eventually mapped to diversified back-ends which do not have consistent ISA semantics.
Given all these, looks like pass down the analysis info to back-ends and let them do the decision become the choice again?
Regards,
Jiong
Quoted 21 lines
The major changes are:
- introducedBPF_ZEXT, even though it doesn't resolve insn patch in-efficient, but could let JIT back-ends do optimal code-gen, and the change is small, so perhap just better to support it in this set.
- while look insn patch code, I feel patched-insn need to be conservatiely marked if any insn inside patch buffer define sub-register.
- Also fixed helper function return value handling bug. I am thinking helper function should have accurate return value type description, otherwise there could be bug. For example arm32 back-end just executes the native helper functions and doesn't do anything special on the return value. So a function returns u32 would only set native reg r0, not r1 in the pair. Then if the outside eBPF insn is casting it into u64, there needs to be zext.
- adjustedtest_verifierto make sure it could pass on hosts w and w/o hw zext.For more info, please see the cover letter and patch description at v5.
Thanks.
Regards,
Jiong