| Message ID | 20200731000324.2253-1-maciej.fijalkowski@intel.com |
|---|---|
| Headers | show |
| Series | bpf: tailcalls in BPF subprograms | expand |
On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: > v5->v6: > - propagate only those poke descriptors that individual subprogram is > actually using (Daniel) > - drop the cumbersome check if poke desc got filled in map_poke_run() > - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 > to patch 3 to provide bisectability (Daniel) I did a basic test with Cilium on K8s with this set, spawning a few Pods and checking connectivity & whether we're not crashing since it has bit more elaborate tail call use. So far so good. I was inclined to push the series out, but there is one more issue I noticed and didn't notice earlier when reviewing, and that is overall stack size: What happens when you create a single program that has nested BPF to BPF calls e.g. either up to the maximum nesting or one call that is using up the max stack size which is then doing another BPF to BPF call that contains the tail call. In the tail call map, you have the same program in there. This means we create a worst case stack from BPF size of max_stack_size * max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 we have a stack of arch/x86/include/asm/page_64_types.h: #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) So we end up with 16k in a typical case. And this will cause kernel stack overflow; I'm at least not seeing where we handle this situation in the set. Hm, need to think more, but maybe this needs tracking of max stack across tail calls to force an upper limit.. Thanks, Daniel
On Sat, Aug 01, 2020 at 03:03:19AM +0200, Daniel Borkmann wrote: > On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: > > v5->v6: > > - propagate only those poke descriptors that individual subprogram is > > actually using (Daniel) > > - drop the cumbersome check if poke desc got filled in map_poke_run() > > - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 > > to patch 3 to provide bisectability (Daniel) > > I did a basic test with Cilium on K8s with this set, spawning a few Pods > and checking connectivity & whether we're not crashing since it has bit more > elaborate tail call use. So far so good. I was inclined to push the series > out, but there is one more issue I noticed and didn't notice earlier when > reviewing, and that is overall stack size: > > What happens when you create a single program that has nested BPF to BPF > calls e.g. either up to the maximum nesting or one call that is using up > the max stack size which is then doing another BPF to BPF call that contains > the tail call. In the tail call map, you have the same program in there. > This means we create a worst case stack from BPF size of max_stack_size * > max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 > we have a stack of arch/x86/include/asm/page_64_types.h: > > #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) > #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) > > So we end up with 16k in a typical case. And this will cause kernel stack > overflow; I'm at least not seeing where we handle this situation in the > set. Hm, need to think more, but maybe this needs tracking of max stack > across tail calls to force an upper limit.. My knee jerk reaction would be to decrement the allowed max tail calls, but not sure if it's an option and if it would help. Otherwise I'm not sure how to pass around the stack size just like we're doing it in this set with tail call counter that sits in %rax. > > Thanks, > Daniel
On Sat, Aug 01, 2020 at 09:13:57AM +0200, Maciej Fijalkowski wrote: > On Sat, Aug 01, 2020 at 03:03:19AM +0200, Daniel Borkmann wrote: > > On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: > > > v5->v6: > > > - propagate only those poke descriptors that individual subprogram is > > > actually using (Daniel) > > > - drop the cumbersome check if poke desc got filled in map_poke_run() > > > - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 > > > to patch 3 to provide bisectability (Daniel) > > > > I did a basic test with Cilium on K8s with this set, spawning a few Pods > > and checking connectivity & whether we're not crashing since it has bit more > > elaborate tail call use. So far so good. I was inclined to push the series > > out, but there is one more issue I noticed and didn't notice earlier when > > reviewing, and that is overall stack size: > > > > What happens when you create a single program that has nested BPF to BPF > > calls e.g. either up to the maximum nesting or one call that is using up > > the max stack size which is then doing another BPF to BPF call that contains > > the tail call. In the tail call map, you have the same program in there. > > This means we create a worst case stack from BPF size of max_stack_size * > > max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 > > we have a stack of arch/x86/include/asm/page_64_types.h: > > > > #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) > > #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) > > > > So we end up with 16k in a typical case. And this will cause kernel stack > > overflow; I'm at least not seeing where we handle this situation in the Not quite. The subprog is always 32 byte stack (from safety pov). The real stack (when JITed) can be lower or zero. So the max stack is (512 - 32) * 32 = 15360. So there is no overflow, but may be a bit too close to comfort. Imo the room is ok to land the set and the better enforcement can be done as a follow up later, like below idea... > > set. Hm, need to think more, but maybe this needs tracking of max stack > > across tail calls to force an upper limit.. > > My knee jerk reaction would be to decrement the allowed max tail calls, > but not sure if it's an option and if it would help. How about make the verifier use a lower bound for a function with a tail call ? Something like 64 would work. subprog_info[idx].stack_depth with tail_call will be >= 64. Then the main function will be automatically limited to 512-64 and the worst case stack = 14kbyte. When the sub prog with tail call is not an empty body (malicious stack abuser) then the lower bound won't affect anything. A bit annoying that stack_depth will be used by JIT to actually allocate that much. Some of it will not be used potentially, but I think it's fine. It's much simpler solution than to keep two variables to track stack size. Or may be check_max_stack_depth() can be a bit smarter and it can detect that subprog is using tail_call without actually hacking stack_depth variable. Essentially I'm proposing to tweak this formula: depth += round_up(max_t(u32, subprog[idx].stack_depth, 1), 32); and replace 1 with 64 for subprogs with tail_call.
On 8/2/20 5:07 AM, Alexei Starovoitov wrote: > On Sat, Aug 01, 2020 at 09:13:57AM +0200, Maciej Fijalkowski wrote: >> On Sat, Aug 01, 2020 at 03:03:19AM +0200, Daniel Borkmann wrote: >>> On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: >>>> v5->v6: >>>> - propagate only those poke descriptors that individual subprogram is >>>> actually using (Daniel) >>>> - drop the cumbersome check if poke desc got filled in map_poke_run() >>>> - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 >>>> to patch 3 to provide bisectability (Daniel) >>> >>> I did a basic test with Cilium on K8s with this set, spawning a few Pods >>> and checking connectivity & whether we're not crashing since it has bit more >>> elaborate tail call use. So far so good. I was inclined to push the series >>> out, but there is one more issue I noticed and didn't notice earlier when >>> reviewing, and that is overall stack size: >>> >>> What happens when you create a single program that has nested BPF to BPF >>> calls e.g. either up to the maximum nesting or one call that is using up >>> the max stack size which is then doing another BPF to BPF call that contains >>> the tail call. In the tail call map, you have the same program in there. >>> This means we create a worst case stack from BPF size of max_stack_size * >>> max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 >>> we have a stack of arch/x86/include/asm/page_64_types.h: >>> >>> #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) >>> #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) >>> >>> So we end up with 16k in a typical case. And this will cause kernel stack >>> overflow; I'm at least not seeing where we handle this situation in the > > Not quite. The subprog is always 32 byte stack (from safety pov). > The real stack (when JITed) can be lower or zero. > So the max stack is (512 - 32) * 32 = 15360. > So there is no overflow, but may be a bit too close to comfort. I did a check with adding `stack_not_used(current)` to various points which provides some useful data under CONFIG_DEBUG_STACK_USAGE. From tc ingress side I'm getting roughly 13k free stack space which is definitely less than 15k even at tc layer. I also checked on sk_filter_trim_cap() on ingress and worst case I saw is very close to 12k, so a malicious or by accident a buggy program would be able to cause a stack overflow as-is. > Imo the room is ok to land the set and the better enforcement can > be done as a follow up later, like below idea... > >>> set. Hm, need to think more, but maybe this needs tracking of max stack >>> across tail calls to force an upper limit.. >> >> My knee jerk reaction would be to decrement the allowed max tail calls, >> but not sure if it's an option and if it would help. > > How about make the verifier use a lower bound for a function with a tail call ? > Something like 64 would work. > subprog_info[idx].stack_depth with tail_call will be >= 64. > Then the main function will be automatically limited to 512-64 and the worst > case stack = 14kbyte. Even 14k is way too close, see above. Some archs that are supported by the kernel run under 8k total stack size. In the long run if more archs would support tail calls with bpf-to-bpf calls, we might need a per-arch upper cap, but I think in this context here an upper total cap on x86 that is 4k should be reasonable, it sounds broken to me if more is indeed needed for the vast majority of use cases. > When the sub prog with tail call is not an empty body (malicious stack > abuser) then the lower bound won't affect anything. > A bit annoying that stack_depth will be used by JIT to actually allocate > that much. Some of it will not be used potentially, but I think it's fine. > It's much simpler solution than to keep two variables to track stack size. > Or may be check_max_stack_depth() can be a bit smarter and it can detect > that subprog is using tail_call without actually hacking stack_depth variable. +1, I think that would be better, maybe we could have a different cost function for the tail call counter itself depending in which call-depth we are, but that also requires two vars for tracking (tail call counter, call depth counter), so more JIT changes & emitted insns required. :/ Otoh, what if tail call counter is limited to 4k and we subtract stack usage instead with a min cost (e.g. 128) if progs use less than that? Though the user experience will be really bad in this case given these semantics feel less deterministic / hard to debug from user PoV. > Essentially I'm proposing to tweak this formula: > depth += round_up(max_t(u32, subprog[idx].stack_depth, 1), 32); > and replace 1 with 64 for subprogs with tail_call. >
On Mon, Aug 03, 2020 at 04:00:10PM +0200, Daniel Borkmann wrote: > On 8/2/20 5:07 AM, Alexei Starovoitov wrote: > > On Sat, Aug 01, 2020 at 09:13:57AM +0200, Maciej Fijalkowski wrote: > > > On Sat, Aug 01, 2020 at 03:03:19AM +0200, Daniel Borkmann wrote: > > > > On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: > > > > > v5->v6: > > > > > - propagate only those poke descriptors that individual subprogram is > > > > > actually using (Daniel) > > > > > - drop the cumbersome check if poke desc got filled in map_poke_run() > > > > > - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 > > > > > to patch 3 to provide bisectability (Daniel) > > > > > > > > I did a basic test with Cilium on K8s with this set, spawning a few Pods > > > > and checking connectivity & whether we're not crashing since it has bit more > > > > elaborate tail call use. So far so good. I was inclined to push the series > > > > out, but there is one more issue I noticed and didn't notice earlier when > > > > reviewing, and that is overall stack size: > > > > > > > > What happens when you create a single program that has nested BPF to BPF > > > > calls e.g. either up to the maximum nesting or one call that is using up > > > > the max stack size which is then doing another BPF to BPF call that contains > > > > the tail call. In the tail call map, you have the same program in there. > > > > This means we create a worst case stack from BPF size of max_stack_size * > > > > max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 > > > > we have a stack of arch/x86/include/asm/page_64_types.h: > > > > > > > > #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) > > > > #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) > > > > > > > > So we end up with 16k in a typical case. And this will cause kernel stack > > > > overflow; I'm at least not seeing where we handle this situation in the > > > > Not quite. The subprog is always 32 byte stack (from safety pov). > > The real stack (when JITed) can be lower or zero. > > So the max stack is (512 - 32) * 32 = 15360. > > So there is no overflow, but may be a bit too close to comfort. > > I did a check with adding `stack_not_used(current)` to various points which > provides some useful data under CONFIG_DEBUG_STACK_USAGE. From tc ingress side > I'm getting roughly 13k free stack space which is definitely less than 15k even > at tc layer. I also checked on sk_filter_trim_cap() on ingress and worst case I > saw is very close to 12k, so a malicious or by accident a buggy program would be > able to cause a stack overflow as-is. > > > Imo the room is ok to land the set and the better enforcement can > > be done as a follow up later, like below idea... > > > > > > set. Hm, need to think more, but maybe this needs tracking of max stack > > > > across tail calls to force an upper limit.. > > > > > > My knee jerk reaction would be to decrement the allowed max tail calls, > > > but not sure if it's an option and if it would help. > > > > How about make the verifier use a lower bound for a function with a tail call ? > > Something like 64 would work. > > subprog_info[idx].stack_depth with tail_call will be >= 64. > > Then the main function will be automatically limited to 512-64 and the worst > > case stack = 14kbyte. > > Even 14k is way too close, see above. Some archs that are supported by the kernel > run under 8k total stack size. In the long run if more archs would support tail > calls with bpf-to-bpf calls, we might need a per-arch upper cap, but I think in > this context here an upper total cap on x86 that is 4k should be reasonable, it > sounds broken to me if more is indeed needed for the vast majority of use cases. > > > When the sub prog with tail call is not an empty body (malicious stack > > abuser) then the lower bound won't affect anything. > > A bit annoying that stack_depth will be used by JIT to actually allocate > > that much. Some of it will not be used potentially, but I think it's fine. > > It's much simpler solution than to keep two variables to track stack size. > > Or may be check_max_stack_depth() can be a bit smarter and it can detect > > that subprog is using tail_call without actually hacking stack_depth variable. > > +1, I think that would be better, maybe we could have a different cost function > for the tail call counter itself depending in which call-depth we are, but that > also requires two vars for tracking (tail call counter, call depth counter), so > more JIT changes & emitted insns required. :/ Otoh, what if tail call counter > is limited to 4k and we subtract stack usage instead with a min cost (e.g. 128) > if progs use less than that? Though the user experience will be really bad in > this case given these semantics feel less deterministic / hard to debug from > user PoV. Let's get this rolling again. I like this approach, but from the opposite way - instead of decrementing from 4k, let's start with 0 like we did before and add up the max(stack_size, 128) on each tailcall as you suggested. Reason for that is no need for changes in prologue, we can keep the xor eax,eax insn which occupies 2 bytes whereas mov eax, 4096 needs 5 bytes from what I see. cmp eax, 4096 also needs more bytes than what cmp eax, MAX_TAIL_CALL_CNT needed, but that's something we need as well as change mentioned below. One last change is add eax, 1 becomes the add eax, max(stack_size, 128) and it is also encoded differently. Let me know if you're fine with that and if i can post v7. Dirty patch below that I will squash onto patch 5 if it's fine. From 01d2494eed07284ea56134f40c6a304b109090ab Mon Sep 17 00:00:00 2001 From: Maciej Fijalkowski <maciej.fijalkowski@intel.com> Date: Fri, 21 Aug 2020 14:04:27 +0200 Subject: [PATCH] bpf: track stack size in tailcall WIP Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com> --- arch/x86/net/bpf_jit_comp.c | 37 ++++++++++++++++++++----------------- include/linux/bpf.h | 1 + 2 files changed, 21 insertions(+), 17 deletions(-) diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c index 880f283adb66..56b38536b1dd 100644 --- a/arch/x86/net/bpf_jit_comp.c +++ b/arch/x86/net/bpf_jit_comp.c @@ -393,7 +393,7 @@ static int get_pop_bytes(bool *callee_regs_used) * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ... * if (index >= array->map.max_entries) * goto out; - * if (++tail_call_cnt > MAX_TAIL_CALL_CNT) + * if (tail_call_stack_depth + stack_depth > MAX_TAIL_CALL_STACK_DEPTH) * goto out; * prog = array->ptrs[index]; * if (prog == NULL) @@ -404,11 +404,12 @@ static int get_pop_bytes(bool *callee_regs_used) static void emit_bpf_tail_call_indirect(u8 **pprog, bool *callee_regs_used, u32 stack_depth) { - int tcc_off = -4 - round_up(stack_depth, 8); + u16 sd = max_t(u16, round_up(stack_depth, 8), 128); + int tcsd_off = -4 - round_up(stack_depth, 8); u8 *prog = *pprog; int pop_bytes = 0; - int off1 = 49; - int off2 = 38; + int off1 = 49 + 4; + int off2 = 38 + 2; int off3 = 16; int cnt = 0; @@ -438,15 +439,16 @@ static void emit_bpf_tail_call_indirect(u8 **pprog, bool *callee_regs_used, EMIT2(X86_JBE, OFFSET1); /* jbe out */ /* - * if (tail_call_cnt > MAX_TAIL_CALL_CNT) + * if (tail_call_stack_depth > MAX_TAIL_CALL_STACK_DEPTH) * goto out; */ - EMIT2_off32(0x8B, 0x85, tcc_off); /* mov eax, dword ptr [rbp - tcc_off] */ - EMIT3(0x83, 0xF8, MAX_TAIL_CALL_CNT); /* cmp eax, MAX_TAIL_CALL_CNT */ + EMIT2_off32(0x8B, 0x85, tcsd_off); /* mov eax, dword ptr [rbp - tcsd_off] */ + EMIT1_off32(0x3D, /* cmp eax, MAX_TAIL_CALL_STACK_DEPTH */ + MAX_TAIL_CALL_STACK_DEPTH); #define OFFSET2 (off2 + RETPOLINE_RCX_BPF_JIT_SIZE) EMIT2(X86_JA, OFFSET2); /* ja out */ - EMIT3(0x83, 0xC0, 0x01); /* add eax, 1 */ - EMIT2_off32(0x89, 0x85, tcc_off); /* mov dword ptr [rbp - tcc_off], eax */ + EMIT1_off32(0x05, sd); /* add eax, stack_depth */ + EMIT2_off32(0x89, 0x85, tcsd_off); /* mov dword ptr [rbp - tcsd_off], eax */ /* prog = array->ptrs[index]; */ EMIT4_off32(0x48, 0x8B, 0x8C, 0xD6, /* mov rcx, [rsi + rdx * 8 + offsetof(...)] */ @@ -488,10 +490,11 @@ static void emit_bpf_tail_call_direct(struct bpf_jit_poke_descriptor *poke, u8 **pprog, int addr, u8 *image, bool *callee_regs_used, u32 stack_depth) { - int tcc_off = -4 - round_up(stack_depth, 8); + u16 sd = max_t(u16, round_up(stack_depth, 8), 128); + int tcsd_off = -4 - round_up(stack_depth, 8); u8 *prog = *pprog; int pop_bytes = 0; - int off1 = 27; + int off1 = 27 + 2; int poke_off; int cnt = 0; @@ -512,14 +515,14 @@ static void emit_bpf_tail_call_direct(struct bpf_jit_poke_descriptor *poke, poke_off = X86_PATCH_SIZE + pop_bytes + 7 + 1; /* - * if (tail_call_cnt > MAX_TAIL_CALL_CNT) + * if (tail_call_stack_depth > MAX_TAIL_CALL_STACK_DEPTH) * goto out; */ - EMIT2_off32(0x8B, 0x85, tcc_off); /* mov eax, dword ptr [rbp - tcc_off] */ - EMIT3(0x83, 0xF8, MAX_TAIL_CALL_CNT); /* cmp eax, MAX_TAIL_CALL_CNT */ + EMIT2_off32(0x8B, 0x85, tcsd_off); /* mov eax, dword ptr [rbp - tcsd_off] */ + EMIT1_off32(0x3D, MAX_TAIL_CALL_STACK_DEPTH); /* cmp eax, MAX_TAIL_CALL_STACK_DEPTH */ EMIT2(X86_JA, off1); /* ja out */ - EMIT3(0x83, 0xC0, 0x01); /* add eax, 1 */ - EMIT2_off32(0x89, 0x85, tcc_off); /* mov dword ptr [rbp - tcc_off], eax */ + EMIT1_off32(0x05, sd); /* add eax, stack_size */ + EMIT2_off32(0x89, 0x85, tcsd_off); /* mov dword ptr [rbp - tcsd_off], eax */ poke->tailcall_bypass = image + (addr - poke_off - X86_PATCH_SIZE); poke->adj_off = X86_TAIL_CALL_OFFSET; @@ -1430,7 +1433,7 @@ xadd: if (is_imm8(insn->off)) ctx->cleanup_addr = proglen; pop_callee_regs(&prog, callee_regs_used); if (!bpf_prog_was_classic(bpf_prog) && tail_call_seen) - EMIT1(0x59); /* pop rcx, get rid of tail_call_cnt */ + EMIT1(0x59); /* pop rcx, get rid of tail_call_stack_depth */ EMIT1(0xC9); /* leave */ EMIT1(0xC3); /* ret */ break; diff --git a/include/linux/bpf.h b/include/linux/bpf.h index c9c460a437ed..5600dfd2217a 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -895,6 +895,7 @@ struct bpf_array { #define BPF_COMPLEXITY_LIMIT_INSNS 1000000 /* yes. 1M insns */ #define MAX_TAIL_CALL_CNT 32 +#define MAX_TAIL_CALL_STACK_DEPTH 4096 #define BPF_F_ACCESS_MASK (BPF_F_RDONLY | \ BPF_F_RDONLY_PROG | \
On Fri, Aug 21, 2020 at 07:38:15PM +0200, Maciej Fijalkowski wrote: > On Mon, Aug 03, 2020 at 04:00:10PM +0200, Daniel Borkmann wrote: > > On 8/2/20 5:07 AM, Alexei Starovoitov wrote: > > > On Sat, Aug 01, 2020 at 09:13:57AM +0200, Maciej Fijalkowski wrote: > > > > On Sat, Aug 01, 2020 at 03:03:19AM +0200, Daniel Borkmann wrote: > > > > > On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: > > > > > > v5->v6: > > > > > > - propagate only those poke descriptors that individual subprogram is > > > > > > actually using (Daniel) > > > > > > - drop the cumbersome check if poke desc got filled in map_poke_run() > > > > > > - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 > > > > > > to patch 3 to provide bisectability (Daniel) > > > > > > > > > > I did a basic test with Cilium on K8s with this set, spawning a few Pods > > > > > and checking connectivity & whether we're not crashing since it has bit more > > > > > elaborate tail call use. So far so good. I was inclined to push the series > > > > > out, but there is one more issue I noticed and didn't notice earlier when > > > > > reviewing, and that is overall stack size: > > > > > > > > > > What happens when you create a single program that has nested BPF to BPF > > > > > calls e.g. either up to the maximum nesting or one call that is using up > > > > > the max stack size which is then doing another BPF to BPF call that contains > > > > > the tail call. In the tail call map, you have the same program in there. > > > > > This means we create a worst case stack from BPF size of max_stack_size * > > > > > max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 > > > > > we have a stack of arch/x86/include/asm/page_64_types.h: > > > > > > > > > > #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) > > > > > #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) > > > > > > > > > > So we end up with 16k in a typical case. And this will cause kernel stack > > > > > overflow; I'm at least not seeing where we handle this situation in the > > > > > > Not quite. The subprog is always 32 byte stack (from safety pov). > > > The real stack (when JITed) can be lower or zero. > > > So the max stack is (512 - 32) * 32 = 15360. > > > So there is no overflow, but may be a bit too close to comfort. > > > > I did a check with adding `stack_not_used(current)` to various points which > > provides some useful data under CONFIG_DEBUG_STACK_USAGE. From tc ingress side > > I'm getting roughly 13k free stack space which is definitely less than 15k even > > at tc layer. I also checked on sk_filter_trim_cap() on ingress and worst case I > > saw is very close to 12k, so a malicious or by accident a buggy program would be > > able to cause a stack overflow as-is. > > > > > Imo the room is ok to land the set and the better enforcement can > > > be done as a follow up later, like below idea... > > > > > > > > set. Hm, need to think more, but maybe this needs tracking of max stack > > > > > across tail calls to force an upper limit.. > > > > > > > > My knee jerk reaction would be to decrement the allowed max tail calls, > > > > but not sure if it's an option and if it would help. > > > > > > How about make the verifier use a lower bound for a function with a tail call ? > > > Something like 64 would work. > > > subprog_info[idx].stack_depth with tail_call will be >= 64. > > > Then the main function will be automatically limited to 512-64 and the worst > > > case stack = 14kbyte. > > > > Even 14k is way too close, see above. Some archs that are supported by the kernel > > run under 8k total stack size. In the long run if more archs would support tail > > calls with bpf-to-bpf calls, we might need a per-arch upper cap, but I think in > > this context here an upper total cap on x86 that is 4k should be reasonable, it > > sounds broken to me if more is indeed needed for the vast majority of use cases. > > > > > When the sub prog with tail call is not an empty body (malicious stack > > > abuser) then the lower bound won't affect anything. > > > A bit annoying that stack_depth will be used by JIT to actually allocate > > > that much. Some of it will not be used potentially, but I think it's fine. > > > It's much simpler solution than to keep two variables to track stack size. > > > Or may be check_max_stack_depth() can be a bit smarter and it can detect > > > that subprog is using tail_call without actually hacking stack_depth variable. > > > > +1, I think that would be better, maybe we could have a different cost function > > for the tail call counter itself depending in which call-depth we are, but that > > also requires two vars for tracking (tail call counter, call depth counter), so > > more JIT changes & emitted insns required. :/ Otoh, what if tail call counter > > is limited to 4k and we subtract stack usage instead with a min cost (e.g. 128) > > if progs use less than that? Though the user experience will be really bad in > > this case given these semantics feel less deterministic / hard to debug from > > user PoV. > > Let's get this rolling again. > I like this approach, but from the opposite way - instead of decrementing > from 4k, let's start with 0 like we did before and add up the > max(stack_size, 128) on each tailcall as you suggested. > > Reason for that is no need for changes in prologue, we can keep the xor > eax,eax insn which occupies 2 bytes whereas mov eax, 4096 needs 5 bytes > from what I see. > > cmp eax, 4096 also needs more bytes than what cmp eax, MAX_TAIL_CALL_CNT > needed, but that's something we need as well as change mentioned below. > > One last change is add eax, 1 becomes the add eax, max(stack_size, 128) > and it is also encoded differently. > > Let me know if you're fine with that and if i can post v7. > Dirty patch below that I will squash onto patch 5 if it's fine. > > From 01d2494eed07284ea56134f40c6a304b109090ab Mon Sep 17 00:00:00 2001 > From: Maciej Fijalkowski <maciej.fijalkowski@intel.com> > Date: Fri, 21 Aug 2020 14:04:27 +0200 > Subject: [PATCH] bpf: track stack size in tailcall > > WIP > > Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com> > --- > arch/x86/net/bpf_jit_comp.c | 37 ++++++++++++++++++++----------------- > include/linux/bpf.h | 1 + > 2 files changed, 21 insertions(+), 17 deletions(-) > > diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c > index 880f283adb66..56b38536b1dd 100644 > --- a/arch/x86/net/bpf_jit_comp.c > +++ b/arch/x86/net/bpf_jit_comp.c > @@ -393,7 +393,7 @@ static int get_pop_bytes(bool *callee_regs_used) > * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ... > * if (index >= array->map.max_entries) > * goto out; > - * if (++tail_call_cnt > MAX_TAIL_CALL_CNT) > + * if (tail_call_stack_depth + stack_depth > MAX_TAIL_CALL_STACK_DEPTH) > * goto out; I don't think we cannot use this approach because it's not correct. Adding the stack_depth of the current function doesn't count stack space accurately. The bpf_tail_call will unwind the current stack. It's the caller's stack (in case of bpf2bpf) that matters from stack overflow pov. But this callee (that does tail_call eventually) can be called from multiple callsites in the caller and potentially from different callers, so the callee cannot know the stack value to subtract without additional verifier help. We can try to keep the maximum depth of stack (including all call frames) in the verfier that leads to that callee with bpf_tail_call() and then pass it into JITs to do this stack accounting. It's reasonable additional complexity in the verifier, but it's painful to add the interpreter support. We would need to hack BPF_TAIL_CALL insn. Like we can store max_stack_of_all_callsites into insn->off when we do fixup_bpf_calls(). Then interpreter will do: iff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index ed0b3578867c..9a8b54c1adb6 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -1532,10 +1532,10 @@ static u64 __no_fgcse ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u6 if (unlikely(index >= array->map.max_entries)) goto out; - if (unlikely(tail_call_cnt > MAX_TAIL_CALL_CNT)) + if (unlikely(tail_call_stack > MAX_TAIL_CALL_STACK /* 4096 */)) goto out; - tail_call_cnt++; + tail_call_stack += insn->off; and similar thing JITs would have to do. That includes modifying all existing JITs. When bpf_tail_call() is called from top frame (instead of bpf-to-bpf subprog) we can init 'off' with 128, so the old 32 call limit will be preserved. But if we go with such massive user visible change I'd rather init 'off' with 32. Then the tail call cnt limit will be 4096/32 = 128 invocations. At least it will address a complain from folks that were hitting 32 limit. Another approach is to use what I've suggested earlier. Adjust the math in check_max_stack_depth(): diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 8a097a85d01b..9c6c909a1ab9 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2982,6 +2982,11 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) int ret_prog[MAX_CALL_FRAMES]; process_func: + if (idx && subprog[idx].has_tail_call && depth >= 256) { + verbose(env, "Cannot do bpf_tail_call when call stack of previous frames is %d bytes. Too large\n", + depth); + return -EACCES; + } Then the worst case stack will be 256 * 32 = 8k while tail_call_cnt of 32 will stay as-is. And no need to change interpreter or JITs. I'm still thinking which way is better long term. Thoughts?
On Wed, Aug 26, 2020 at 02:35:25PM -0700, Alexei Starovoitov wrote: > On Fri, Aug 21, 2020 at 07:38:15PM +0200, Maciej Fijalkowski wrote: > > On Mon, Aug 03, 2020 at 04:00:10PM +0200, Daniel Borkmann wrote: > > > On 8/2/20 5:07 AM, Alexei Starovoitov wrote: > > > > On Sat, Aug 01, 2020 at 09:13:57AM +0200, Maciej Fijalkowski wrote: > > > > > On Sat, Aug 01, 2020 at 03:03:19AM +0200, Daniel Borkmann wrote: > > > > > > On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: > > > > > > > v5->v6: > > > > > > > - propagate only those poke descriptors that individual subprogram is > > > > > > > actually using (Daniel) > > > > > > > - drop the cumbersome check if poke desc got filled in map_poke_run() > > > > > > > - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 > > > > > > > to patch 3 to provide bisectability (Daniel) > > > > > > > > > > > > I did a basic test with Cilium on K8s with this set, spawning a few Pods > > > > > > and checking connectivity & whether we're not crashing since it has bit more > > > > > > elaborate tail call use. So far so good. I was inclined to push the series > > > > > > out, but there is one more issue I noticed and didn't notice earlier when > > > > > > reviewing, and that is overall stack size: > > > > > > > > > > > > What happens when you create a single program that has nested BPF to BPF > > > > > > calls e.g. either up to the maximum nesting or one call that is using up > > > > > > the max stack size which is then doing another BPF to BPF call that contains > > > > > > the tail call. In the tail call map, you have the same program in there. > > > > > > This means we create a worst case stack from BPF size of max_stack_size * > > > > > > max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 > > > > > > we have a stack of arch/x86/include/asm/page_64_types.h: > > > > > > > > > > > > #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) > > > > > > #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) > > > > > > > > > > > > So we end up with 16k in a typical case. And this will cause kernel stack > > > > > > overflow; I'm at least not seeing where we handle this situation in the > > > > > > > > Not quite. The subprog is always 32 byte stack (from safety pov). > > > > The real stack (when JITed) can be lower or zero. > > > > So the max stack is (512 - 32) * 32 = 15360. > > > > So there is no overflow, but may be a bit too close to comfort. > > > > > > I did a check with adding `stack_not_used(current)` to various points which > > > provides some useful data under CONFIG_DEBUG_STACK_USAGE. From tc ingress side > > > I'm getting roughly 13k free stack space which is definitely less than 15k even > > > at tc layer. I also checked on sk_filter_trim_cap() on ingress and worst case I > > > saw is very close to 12k, so a malicious or by accident a buggy program would be > > > able to cause a stack overflow as-is. > > > > > > > Imo the room is ok to land the set and the better enforcement can > > > > be done as a follow up later, like below idea... > > > > > > > > > > set. Hm, need to think more, but maybe this needs tracking of max stack > > > > > > across tail calls to force an upper limit.. > > > > > > > > > > My knee jerk reaction would be to decrement the allowed max tail calls, > > > > > but not sure if it's an option and if it would help. > > > > > > > > How about make the verifier use a lower bound for a function with a tail call ? > > > > Something like 64 would work. > > > > subprog_info[idx].stack_depth with tail_call will be >= 64. > > > > Then the main function will be automatically limited to 512-64 and the worst > > > > case stack = 14kbyte. > > > > > > Even 14k is way too close, see above. Some archs that are supported by the kernel > > > run under 8k total stack size. In the long run if more archs would support tail > > > calls with bpf-to-bpf calls, we might need a per-arch upper cap, but I think in > > > this context here an upper total cap on x86 that is 4k should be reasonable, it > > > sounds broken to me if more is indeed needed for the vast majority of use cases. > > > > > > > When the sub prog with tail call is not an empty body (malicious stack > > > > abuser) then the lower bound won't affect anything. > > > > A bit annoying that stack_depth will be used by JIT to actually allocate > > > > that much. Some of it will not be used potentially, but I think it's fine. > > > > It's much simpler solution than to keep two variables to track stack size. > > > > Or may be check_max_stack_depth() can be a bit smarter and it can detect > > > > that subprog is using tail_call without actually hacking stack_depth variable. > > > > > > +1, I think that would be better, maybe we could have a different cost function > > > for the tail call counter itself depending in which call-depth we are, but that > > > also requires two vars for tracking (tail call counter, call depth counter), so > > > more JIT changes & emitted insns required. :/ Otoh, what if tail call counter > > > is limited to 4k and we subtract stack usage instead with a min cost (e.g. 128) > > > if progs use less than that? Though the user experience will be really bad in > > > this case given these semantics feel less deterministic / hard to debug from > > > user PoV. > > > > Let's get this rolling again. > > I like this approach, but from the opposite way - instead of decrementing > > from 4k, let's start with 0 like we did before and add up the > > max(stack_size, 128) on each tailcall as you suggested. > > > > Reason for that is no need for changes in prologue, we can keep the xor > > eax,eax insn which occupies 2 bytes whereas mov eax, 4096 needs 5 bytes > > from what I see. > > > > cmp eax, 4096 also needs more bytes than what cmp eax, MAX_TAIL_CALL_CNT > > needed, but that's something we need as well as change mentioned below. > > > > One last change is add eax, 1 becomes the add eax, max(stack_size, 128) > > and it is also encoded differently. > > > > Let me know if you're fine with that and if i can post v7. > > Dirty patch below that I will squash onto patch 5 if it's fine. > > > > From 01d2494eed07284ea56134f40c6a304b109090ab Mon Sep 17 00:00:00 2001 > > From: Maciej Fijalkowski <maciej.fijalkowski@intel.com> > > Date: Fri, 21 Aug 2020 14:04:27 +0200 > > Subject: [PATCH] bpf: track stack size in tailcall > > > > WIP > > > > Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com> > > --- > > arch/x86/net/bpf_jit_comp.c | 37 ++++++++++++++++++++----------------- > > include/linux/bpf.h | 1 + > > 2 files changed, 21 insertions(+), 17 deletions(-) > > > > diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c > > index 880f283adb66..56b38536b1dd 100644 > > --- a/arch/x86/net/bpf_jit_comp.c > > +++ b/arch/x86/net/bpf_jit_comp.c > > @@ -393,7 +393,7 @@ static int get_pop_bytes(bool *callee_regs_used) > > * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ... > > * if (index >= array->map.max_entries) > > * goto out; > > - * if (++tail_call_cnt > MAX_TAIL_CALL_CNT) > > + * if (tail_call_stack_depth + stack_depth > MAX_TAIL_CALL_STACK_DEPTH) > > * goto out; > > I don't think we cannot use this approach because it's not correct. Adding the > stack_depth of the current function doesn't count stack space accurately. > The bpf_tail_call will unwind the current stack. It's the caller's stack > (in case of bpf2bpf) that matters from stack overflow pov. I must admit I was puzzled when I came back to this stuff after a break, because as you're saying before the actual tailcall we will unwind the stack frame of tailcall's caller (or the current stack frame in simpler terms). So, to visualize a bit and so that I'm sure I follow: func1 -> sub rsp, 128 subfunc1 -> sub rsp, 256 tailcall1 -> add rsp, 256 func2 -> sub rsp, 256 (total stack size = 128 + 256 = 384) subfunc2 -> sub rsp, 64 subfunc22 -> sub rsp, 128 tailcall2 -> add rsp, 128 func3 -> sub rsp, 256 (total stack size 128 + 256 + 64 + 256 = 704) and so on. And this is what we have to address. If that's it, then thanks for making it explicit that it's about the subprog caller's stack. > But this callee (that does tail_call eventually) can be called from multiple > callsites in the caller and potentially from different callers, so > the callee cannot know the stack value to subtract without additional verifier help. > We can try to keep the maximum depth of stack (including all call frames) in > the verfier that leads to that callee with bpf_tail_call() and then pass it > into JITs to do this stack accounting. It's reasonable additional complexity in > the verifier, but it's painful to add the interpreter support. Not sure if we're on the same page - we allow this set only for x64 arch. Why do you mention the interpreter and other JITs? We could introduce one of your suggestions to verifier and surround it with proper ifdefs like patch 5/6 is doing it. > We would need to hack BPF_TAIL_CALL insn. Like we can store > max_stack_of_all_callsites into insn->off when we do fixup_bpf_calls(). > Then interpreter will do: > iff --git a/kernel/bpf/core.c b/kernel/bpf/core.c > index ed0b3578867c..9a8b54c1adb6 100644 > --- a/kernel/bpf/core.c > +++ b/kernel/bpf/core.c > @@ -1532,10 +1532,10 @@ static u64 __no_fgcse ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u6 > > if (unlikely(index >= array->map.max_entries)) > goto out; > - if (unlikely(tail_call_cnt > MAX_TAIL_CALL_CNT)) > + if (unlikely(tail_call_stack > MAX_TAIL_CALL_STACK /* 4096 */)) > goto out; > > - tail_call_cnt++; > + tail_call_stack += insn->off; > > and similar thing JITs would have to do. That includes modifying all existing JITs. Again, I don't get why we would have to address everything else besides x64 JIT. > > When bpf_tail_call() is called from top frame (instead of bpf-to-bpf subprog) > we can init 'off' with 128, so the old 32 call limit will be preserved. > But if we go with such massive user visible change I'd rather init 'off' with 32. > Then the tail call cnt limit will be 4096/32 = 128 invocations. > At least it will address a complain from folks that were hitting 32 limit. > > Another approach is to use what I've suggested earlier. > Adjust the math in check_max_stack_depth(): > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 8a097a85d01b..9c6c909a1ab9 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -2982,6 +2982,11 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) > int ret_prog[MAX_CALL_FRAMES]; > > process_func: > + if (idx && subprog[idx].has_tail_call && depth >= 256) { > + verbose(env, "Cannot do bpf_tail_call when call stack of previous frames is %d bytes. Too large\n", > + depth); > + return -EACCES; > + } > Then the worst case stack will be 256 * 32 = 8k while tail_call_cnt of 32 will stay as-is. > And no need to change interpreter or JITs. I tend to lean towards simpler solutions as this work is already complex. Let's hear Daniel's opinion though. > > I'm still thinking which way is better long term. > Thoughts?
On Sun, Aug 30, 2020 at 01:19:25AM +0200, Maciej Fijalkowski wrote: > On Wed, Aug 26, 2020 at 02:35:25PM -0700, Alexei Starovoitov wrote: > > On Fri, Aug 21, 2020 at 07:38:15PM +0200, Maciej Fijalkowski wrote: > > > On Mon, Aug 03, 2020 at 04:00:10PM +0200, Daniel Borkmann wrote: > > > > On 8/2/20 5:07 AM, Alexei Starovoitov wrote: > > > > > On Sat, Aug 01, 2020 at 09:13:57AM +0200, Maciej Fijalkowski wrote: > > > > > > On Sat, Aug 01, 2020 at 03:03:19AM +0200, Daniel Borkmann wrote: > > > > > > > On 7/31/20 2:03 AM, Maciej Fijalkowski wrote: > > > > > > > > v5->v6: > > > > > > > > - propagate only those poke descriptors that individual subprogram is > > > > > > > > actually using (Daniel) > > > > > > > > - drop the cumbersome check if poke desc got filled in map_poke_run() > > > > > > > > - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 > > > > > > > > to patch 3 to provide bisectability (Daniel) > > > > > > > > > > > > > > I did a basic test with Cilium on K8s with this set, spawning a few Pods > > > > > > > and checking connectivity & whether we're not crashing since it has bit more > > > > > > > elaborate tail call use. So far so good. I was inclined to push the series > > > > > > > out, but there is one more issue I noticed and didn't notice earlier when > > > > > > > reviewing, and that is overall stack size: > > > > > > > > > > > > > > What happens when you create a single program that has nested BPF to BPF > > > > > > > calls e.g. either up to the maximum nesting or one call that is using up > > > > > > > the max stack size which is then doing another BPF to BPF call that contains > > > > > > > the tail call. In the tail call map, you have the same program in there. > > > > > > > This means we create a worst case stack from BPF size of max_stack_size * > > > > > > > max_tail_call_size, that is, 512*32. So that adds 16k worst case. For x86 > > > > > > > we have a stack of arch/x86/include/asm/page_64_types.h: > > > > > > > > > > > > > > #define THREAD_SIZE_ORDER (2 + KASAN_STACK_ORDER) > > > > > > > #define THREAD_SIZE (PAGE_SIZE << THREAD_SIZE_ORDER) > > > > > > > > > > > > > > So we end up with 16k in a typical case. And this will cause kernel stack > > > > > > > overflow; I'm at least not seeing where we handle this situation in the > > > > > > > > > > Not quite. The subprog is always 32 byte stack (from safety pov). > > > > > The real stack (when JITed) can be lower or zero. > > > > > So the max stack is (512 - 32) * 32 = 15360. > > > > > So there is no overflow, but may be a bit too close to comfort. > > > > > > > > I did a check with adding `stack_not_used(current)` to various points which > > > > provides some useful data under CONFIG_DEBUG_STACK_USAGE. From tc ingress side > > > > I'm getting roughly 13k free stack space which is definitely less than 15k even > > > > at tc layer. I also checked on sk_filter_trim_cap() on ingress and worst case I > > > > saw is very close to 12k, so a malicious or by accident a buggy program would be > > > > able to cause a stack overflow as-is. > > > > > > > > > Imo the room is ok to land the set and the better enforcement can > > > > > be done as a follow up later, like below idea... > > > > > > > > > > > > set. Hm, need to think more, but maybe this needs tracking of max stack > > > > > > > across tail calls to force an upper limit.. > > > > > > > > > > > > My knee jerk reaction would be to decrement the allowed max tail calls, > > > > > > but not sure if it's an option and if it would help. > > > > > > > > > > How about make the verifier use a lower bound for a function with a tail call ? > > > > > Something like 64 would work. > > > > > subprog_info[idx].stack_depth with tail_call will be >= 64. > > > > > Then the main function will be automatically limited to 512-64 and the worst > > > > > case stack = 14kbyte. > > > > > > > > Even 14k is way too close, see above. Some archs that are supported by the kernel > > > > run under 8k total stack size. In the long run if more archs would support tail > > > > calls with bpf-to-bpf calls, we might need a per-arch upper cap, but I think in > > > > this context here an upper total cap on x86 that is 4k should be reasonable, it > > > > sounds broken to me if more is indeed needed for the vast majority of use cases. > > > > > > > > > When the sub prog with tail call is not an empty body (malicious stack > > > > > abuser) then the lower bound won't affect anything. > > > > > A bit annoying that stack_depth will be used by JIT to actually allocate > > > > > that much. Some of it will not be used potentially, but I think it's fine. > > > > > It's much simpler solution than to keep two variables to track stack size. > > > > > Or may be check_max_stack_depth() can be a bit smarter and it can detect > > > > > that subprog is using tail_call without actually hacking stack_depth variable. > > > > > > > > +1, I think that would be better, maybe we could have a different cost function > > > > for the tail call counter itself depending in which call-depth we are, but that > > > > also requires two vars for tracking (tail call counter, call depth counter), so > > > > more JIT changes & emitted insns required. :/ Otoh, what if tail call counter > > > > is limited to 4k and we subtract stack usage instead with a min cost (e.g. 128) > > > > if progs use less than that? Though the user experience will be really bad in > > > > this case given these semantics feel less deterministic / hard to debug from > > > > user PoV. > > > > > > Let's get this rolling again. > > > I like this approach, but from the opposite way - instead of decrementing > > > from 4k, let's start with 0 like we did before and add up the > > > max(stack_size, 128) on each tailcall as you suggested. > > > > > > Reason for that is no need for changes in prologue, we can keep the xor > > > eax,eax insn which occupies 2 bytes whereas mov eax, 4096 needs 5 bytes > > > from what I see. > > > > > > cmp eax, 4096 also needs more bytes than what cmp eax, MAX_TAIL_CALL_CNT > > > needed, but that's something we need as well as change mentioned below. > > > > > > One last change is add eax, 1 becomes the add eax, max(stack_size, 128) > > > and it is also encoded differently. > > > > > > Let me know if you're fine with that and if i can post v7. > > > Dirty patch below that I will squash onto patch 5 if it's fine. > > > > > > From 01d2494eed07284ea56134f40c6a304b109090ab Mon Sep 17 00:00:00 2001 > > > From: Maciej Fijalkowski <maciej.fijalkowski@intel.com> > > > Date: Fri, 21 Aug 2020 14:04:27 +0200 > > > Subject: [PATCH] bpf: track stack size in tailcall > > > > > > WIP > > > > > > Signed-off-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com> > > > --- > > > arch/x86/net/bpf_jit_comp.c | 37 ++++++++++++++++++++----------------- > > > include/linux/bpf.h | 1 + > > > 2 files changed, 21 insertions(+), 17 deletions(-) > > > > > > diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c > > > index 880f283adb66..56b38536b1dd 100644 > > > --- a/arch/x86/net/bpf_jit_comp.c > > > +++ b/arch/x86/net/bpf_jit_comp.c > > > @@ -393,7 +393,7 @@ static int get_pop_bytes(bool *callee_regs_used) > > > * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ... > > > * if (index >= array->map.max_entries) > > > * goto out; > > > - * if (++tail_call_cnt > MAX_TAIL_CALL_CNT) > > > + * if (tail_call_stack_depth + stack_depth > MAX_TAIL_CALL_STACK_DEPTH) > > > * goto out; > > > > I don't think we cannot use this approach because it's not correct. Adding the > > stack_depth of the current function doesn't count stack space accurately. > > The bpf_tail_call will unwind the current stack. It's the caller's stack > > (in case of bpf2bpf) that matters from stack overflow pov. > > I must admit I was puzzled when I came back to this stuff after a break, > because as you're saying before the actual tailcall we will unwind the > stack frame of tailcall's caller (or the current stack frame in simpler > terms). > > So, to visualize a bit and so that I'm sure I follow: > > func1 -> sub rsp, 128 > subfunc1 -> sub rsp, 256 > tailcall1 -> add rsp, 256 > func2 -> sub rsp, 256 (total stack size = 128 + 256 = 384) > subfunc2 -> sub rsp, 64 > subfunc22 -> sub rsp, 128 > tailcall2 -> add rsp, 128 > func3 -> sub rsp, 256 (total stack size 128 + 256 + 64 + 256 = 704) > > and so on. And this is what we have to address. If that's it, then thanks > for making it explicit that it's about the subprog caller's stack. Right. The above is correct. Could you add it to the code as a comment? Please replace second and third use of 256 with a different constant to make it easier to see that 'sub rsp, X' in func1, func2, and func3 can be different. > > But this callee (that does tail_call eventually) can be called from multiple > > callsites in the caller and potentially from different callers, so > > the callee cannot know the stack value to subtract without additional verifier help. > > We can try to keep the maximum depth of stack (including all call frames) in > > the verfier that leads to that callee with bpf_tail_call() and then pass it > > into JITs to do this stack accounting. It's reasonable additional complexity in > > the verifier, but it's painful to add the interpreter support. > > Not sure if we're on the same page - we allow this set only for x64 arch. > Why do you mention the interpreter and other JITs? It's not 100% mandatory to make the interpreter compatible with JIT, but we should always try to keep the parity when possible. Like when I was working on BPF trampoline I've considered to support JITed code only, since generation of trampoline itself requires Just-In-Time code generation. But I took the extra effort to make sure invoke_bpf_prog() in arch/x86/net/bpf_jit_comp.c supports interpreter as well. There could be bugs in the interpreter or JIT. Having two ways to execute the program is useful for many reasons. In this case the new tail_call handling in x86 JIT will unwind the current stack, so existing interpreter handling of tail_call won't quite work. Take a look at bpf_patch_call_args(), JMP_CALL_ARGS:, and JMP_TAIL_CALL:. The JMP_TAIL_CALL will sort-of unwind the current stack, but the size of the stack will be reused for tail_call target function. Illustrating on your example: func1 -> sub rsp, 128 subfunc1 -> sub rsp, 256 tailcall1 -> add rsp, 256 func2 -> sub rsp, 192 (total stack size = 128 + 192 = 320) subfunc2 -> sub rsp, 64 subfunc22 -> sub rsp, 128 tailcall2 -> add rsp, 128 func3 -> sub rsp, 224 (total stack size 128 + 192 + 64 + 224 = 608) The interpreter will call into subfunc1 with 256 bytes of the interpreter stack and will reuse it for tail_call into func2. If func2 needs 192, it's going to work fine, but if it needs more than 256 there will be stack overflow. We can disable mixing bpf2bpf calls and tail_calls when interpreter is used for now, but it would be good to support it somehow. > We could introduce one of your suggestions to verifier and surround it with > proper ifdefs like patch 5/6 is doing it. If we use the approach of changing JMP_TAIL_CALL pseudo insn to do: - tail_call_cnt++; + tail_call_stack += insn->off; then we have to update other JITs to do the same. Other JITs do NOT need to support bpf2bpf calls with tail_calls. they do NOT need to do current stack unwinding, but they have to match the new behavior of JMP_TAIL_CALL otherwise such interpreter vs JIT discrepancy will create plenty of unhappy users. > > We would need to hack BPF_TAIL_CALL insn. Like we can store > > max_stack_of_all_callsites into insn->off when we do fixup_bpf_calls(). > > Then interpreter will do: > > iff --git a/kernel/bpf/core.c b/kernel/bpf/core.c > > index ed0b3578867c..9a8b54c1adb6 100644 > > --- a/kernel/bpf/core.c > > +++ b/kernel/bpf/core.c > > @@ -1532,10 +1532,10 @@ static u64 __no_fgcse ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u6 > > > > if (unlikely(index >= array->map.max_entries)) > > goto out; > > - if (unlikely(tail_call_cnt > MAX_TAIL_CALL_CNT)) > > + if (unlikely(tail_call_stack > MAX_TAIL_CALL_STACK /* 4096 */)) > > goto out; > > > > - tail_call_cnt++; > > + tail_call_stack += insn->off; > > > > and similar thing JITs would have to do. That includes modifying all existing JITs. > > Again, I don't get why we would have to address everything else besides > x64 JIT. > > > > > When bpf_tail_call() is called from top frame (instead of bpf-to-bpf subprog) > > we can init 'off' with 128, so the old 32 call limit will be preserved. > > But if we go with such massive user visible change I'd rather init 'off' with 32. > > Then the tail call cnt limit will be 4096/32 = 128 invocations. > > At least it will address a complain from folks that were hitting 32 limit. > > > > Another approach is to use what I've suggested earlier. > > Adjust the math in check_max_stack_depth(): > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > index 8a097a85d01b..9c6c909a1ab9 100644 > > --- a/kernel/bpf/verifier.c > > +++ b/kernel/bpf/verifier.c > > @@ -2982,6 +2982,11 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) > > int ret_prog[MAX_CALL_FRAMES]; > > > > process_func: > > + if (idx && subprog[idx].has_tail_call && depth >= 256) { > > + verbose(env, "Cannot do bpf_tail_call when call stack of previous frames is %d bytes. Too large\n", > > + depth); > > + return -EACCES; > > + } > > Then the worst case stack will be 256 * 32 = 8k while tail_call_cnt of 32 will stay as-is. > > And no need to change interpreter or JITs. > > I tend to lean towards simpler solutions as this work is already complex. > Let's hear Daniel's opinion though. Let's go with this simpler solution. We can add fancier stack accounting later.
On Tue, Sep 01, 2020 at 09:24:12AM -0700, Alexei Starovoitov wrote: [...] > > > > diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c > > > > index 880f283adb66..56b38536b1dd 100644 > > > > --- a/arch/x86/net/bpf_jit_comp.c > > > > +++ b/arch/x86/net/bpf_jit_comp.c > > > > @@ -393,7 +393,7 @@ static int get_pop_bytes(bool *callee_regs_used) > > > > * ... bpf_tail_call(void *ctx, struct bpf_array *array, u64 index) ... > > > > * if (index >= array->map.max_entries) > > > > * goto out; > > > > - * if (++tail_call_cnt > MAX_TAIL_CALL_CNT) > > > > + * if (tail_call_stack_depth + stack_depth > MAX_TAIL_CALL_STACK_DEPTH) > > > > * goto out; > > > > > > I don't think we cannot use this approach because it's not correct. Adding the > > > stack_depth of the current function doesn't count stack space accurately. > > > The bpf_tail_call will unwind the current stack. It's the caller's stack > > > (in case of bpf2bpf) that matters from stack overflow pov. > > > > I must admit I was puzzled when I came back to this stuff after a break, > > because as you're saying before the actual tailcall we will unwind the > > stack frame of tailcall's caller (or the current stack frame in simpler > > terms). > > > > So, to visualize a bit and so that I'm sure I follow: > > > > func1 -> sub rsp, 128 > > subfunc1 -> sub rsp, 256 > > tailcall1 -> add rsp, 256 > > func2 -> sub rsp, 256 (total stack size = 128 + 256 = 384) > > subfunc2 -> sub rsp, 64 > > subfunc22 -> sub rsp, 128 > > tailcall2 -> add rsp, 128 > > func3 -> sub rsp, 256 (total stack size 128 + 256 + 64 + 256 = 704) > > > > and so on. And this is what we have to address. If that's it, then thanks > > for making it explicit that it's about the subprog caller's stack. > > Right. The above is correct. Could you add it to the code as a comment? > Please replace second and third use of 256 with a different constant to > make it easier to see that 'sub rsp, X' in func1, func2, and func3 can > be different. Good stuff. I played with your suggestion to limit caller's stack depth down to 256 when there is tailcall in subprogram by creating buffers on stack among subprogs and use it in some stupid way so that verifier wouldn't prune it and it seems that it is doing its job. For a moment I was a bit confused if everything is all right since I saw that I hit the stack depth of 480, but it was due to the fact that tailcall was in last subprog AND previous stacks summarized were not above 256. IOW that last stack will get unwinded before the tailcall as mentioned already multiple times. Thanks for all of the explanations below, that is pretty educational, but I'm glad that I don't have to get my hands dirty with interpreter...yet :) I wrapped the code you suggested with ifdefs same as the patch that allows for having tailcalls in BPF subprogs. Sending v7. > > > > But this callee (that does tail_call eventually) can be called from multiple > > > callsites in the caller and potentially from different callers, so > > > the callee cannot know the stack value to subtract without additional verifier help. > > > We can try to keep the maximum depth of stack (including all call frames) in > > > the verfier that leads to that callee with bpf_tail_call() and then pass it > > > into JITs to do this stack accounting. It's reasonable additional complexity in > > > the verifier, but it's painful to add the interpreter support. > > > > Not sure if we're on the same page - we allow this set only for x64 arch. > > Why do you mention the interpreter and other JITs? > > It's not 100% mandatory to make the interpreter compatible with JIT, > but we should always try to keep the parity when possible. > Like when I was working on BPF trampoline I've considered to support JITed code > only, since generation of trampoline itself requires Just-In-Time code > generation. But I took the extra effort to make sure invoke_bpf_prog() in > arch/x86/net/bpf_jit_comp.c supports interpreter as well. There could be bugs > in the interpreter or JIT. Having two ways to execute the program is useful for > many reasons. > > In this case the new tail_call handling in x86 JIT will unwind the current stack, > so existing interpreter handling of tail_call won't quite work. > Take a look at bpf_patch_call_args(), JMP_CALL_ARGS:, and JMP_TAIL_CALL:. > The JMP_TAIL_CALL will sort-of unwind the current stack, but the size of the stack > will be reused for tail_call target function. > Illustrating on your example: > func1 -> sub rsp, 128 > subfunc1 -> sub rsp, 256 > tailcall1 -> add rsp, 256 > func2 -> sub rsp, 192 (total stack size = 128 + 192 = 320) > subfunc2 -> sub rsp, 64 > subfunc22 -> sub rsp, 128 > tailcall2 -> add rsp, 128 > func3 -> sub rsp, 224 (total stack size 128 + 192 + 64 + 224 = 608) > > The interpreter will call into subfunc1 with 256 bytes of the interpreter stack > and will reuse it for tail_call into func2. > If func2 needs 192, it's going to work fine, but if it needs more than 256 > there will be stack overflow. > > We can disable mixing bpf2bpf calls and tail_calls when interpreter is used > for now, but it would be good to support it somehow. > > > We could introduce one of your suggestions to verifier and surround it with > > proper ifdefs like patch 5/6 is doing it. > > If we use the approach of changing JMP_TAIL_CALL pseudo insn to do: > - tail_call_cnt++; > + tail_call_stack += insn->off; > then we have to update other JITs to do the same. > Other JITs do NOT need to support bpf2bpf calls with tail_calls. > they do NOT need to do current stack unwinding, but they have to match > the new behavior of JMP_TAIL_CALL otherwise such interpreter vs JIT > discrepancy will create plenty of unhappy users. > > > > We would need to hack BPF_TAIL_CALL insn. Like we can store > > > max_stack_of_all_callsites into insn->off when we do fixup_bpf_calls(). > > > Then interpreter will do: > > > iff --git a/kernel/bpf/core.c b/kernel/bpf/core.c > > > index ed0b3578867c..9a8b54c1adb6 100644 > > > --- a/kernel/bpf/core.c > > > +++ b/kernel/bpf/core.c > > > @@ -1532,10 +1532,10 @@ static u64 __no_fgcse ___bpf_prog_run(u64 *regs, const struct bpf_insn *insn, u6 > > > > > > if (unlikely(index >= array->map.max_entries)) > > > goto out; > > > - if (unlikely(tail_call_cnt > MAX_TAIL_CALL_CNT)) > > > + if (unlikely(tail_call_stack > MAX_TAIL_CALL_STACK /* 4096 */)) > > > goto out; > > > > > > - tail_call_cnt++; > > > + tail_call_stack += insn->off; > > > > > > and similar thing JITs would have to do. That includes modifying all existing JITs. > > > > Again, I don't get why we would have to address everything else besides > > x64 JIT. > > > > > > > > When bpf_tail_call() is called from top frame (instead of bpf-to-bpf subprog) > > > we can init 'off' with 128, so the old 32 call limit will be preserved. > > > But if we go with such massive user visible change I'd rather init 'off' with 32. > > > Then the tail call cnt limit will be 4096/32 = 128 invocations. > > > At least it will address a complain from folks that were hitting 32 limit. > > > > > > Another approach is to use what I've suggested earlier. > > > Adjust the math in check_max_stack_depth(): > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > > > index 8a097a85d01b..9c6c909a1ab9 100644 > > > --- a/kernel/bpf/verifier.c > > > +++ b/kernel/bpf/verifier.c > > > @@ -2982,6 +2982,11 @@ static int check_max_stack_depth(struct bpf_verifier_env *env) > > > int ret_prog[MAX_CALL_FRAMES]; > > > > > > process_func: > > > + if (idx && subprog[idx].has_tail_call && depth >= 256) { > > > + verbose(env, "Cannot do bpf_tail_call when call stack of previous frames is %d bytes. Too large\n", > > > + depth); > > > + return -EACCES; > > > + } > > > Then the worst case stack will be 256 * 32 = 8k while tail_call_cnt of 32 will stay as-is. > > > And no need to change interpreter or JITs. > > > > I tend to lean towards simpler solutions as this work is already complex. > > Let's hear Daniel's opinion though. > > Let's go with this simpler solution. We can add fancier stack > accounting later.
v5->v6: - propagate only those poke descriptors that individual subprogram is actually using (Daniel) - drop the cumbersome check if poke desc got filled in map_poke_run() - move poke->ip renaming in bpf_jit_add_poke_descriptor() from patch 4 to patch 3 to provide bisectability (Daniel) v4->v5: - simplify the fix from v3/v4 (Daniel) v3->v4: - be more careful around the fix from v3 v2->v3: - call map_poke_untrack() on each previously registered subprog's aux struct to prog array if adding poke descriptor or tracking the aux struct failed (Daniel) v1->v2: - include the rax->rcx conversion in first patch, target prog needs to be placed in rcx in the tailcall indirect routine (Daniel) - add error checks to routines that add poke descriptors to subprograms (Daniel) - don't allow this optimization when arch is different than x64 and when JIT is disabled (Daniel) - pull out the rename of poke desc members onto a separate patch (Daniel) - add a new poke member to store the bypass address so that calculation of it won't be necessary - avoid the special casing when old and new is null in map_poke_run (Daniel) - do not sync RCU when bypass target was not patched (Daniel) - do not introduce nop2 instruction to prologue for cBPF programs (Daniel) RFC->v1: - rename poke->ip/poke->ip_aux pair to poke->tailcall_target/poke->tailcall_bypass (Alexei) - get rid of x86-specific code in prog_array_map_poke_run (Alexei) - use synchronize_rcu in prog_array_map_poke_run so that other CPUs in the middle of execution will finish running the program and will not stumble upon the incorrect state (Alexei) - update performance reports - rebase Hello, today bpf2bpf calls and tailcalls exclude each other. This set makes them work together. To give you an overview how this work started, previously I posted RFC that was targetted at getting rid of push/pop instructions for callee saved registers in x86-64 JIT that are not used by the BPF program. Alexei saw a potential that that work could be lifted a bit and tailcalls could work with BPF subprograms. More on that in [1], [2]. For previous discussions on RFC version, see [3]. For v1, see [4]. v2 is in [5], v3 can be ignored. v5 - [6]. In [1], Alexei says: "The prologue will look like: nop5 xor eax,eax // two new bytes if bpf_tail_call() is used in this function push rbp mov rbp, rsp sub rsp, rounded_stack_depth push rax // zero init tail_call counter variable number of push rbx,r13,r14,r15 Then bpf_tail_call will pop variable number rbx,.. and final 'pop rax' Then 'add rsp, size_of_current_stack_frame' jmp to next function and skip over 'nop5; xor eax,eax; push rpb; mov rbp, rsp' This way new function will set its own stack size and will init tail call counter with whatever value the parent had. If next function doesn't use bpf_tail_call it won't have 'xor eax,eax'. Instead it would need to have 'nop2' in there." So basically I gave a shot at that suggestion. Patch 4 has a description of implementation. Quick overview of patches: Patch 1 changes BPF retpoline to use %rcx instead of %rax to store address of BPF tailcall target program Patch 2 propagates poke descriptors from main program to each subprogram Patch 3 renames poke->ip to poke->tailcall_target Patch 4 is the main dish in this set. It implements new prologue layout that was suggested by Alexei and reworks tailcall handling. Patch 5 relaxes verifier's restrictions about tailcalls being used with BPF subprograms for x64 JIT Patch 6 is the new selftest that proves tailcalls can be used from within BPF subprogram. ------------------------------------------------------------------- prog_array_map_poke_run changes: Before the tailcall and with the new prologue layout, stack need to be unwinded and callee saved registers need to be popped. Instructions responsible for that are generated, but they should not be executed if target program is not present. To address that, new poke target 'tailcall_bypass' is introduced to poke descriptor that will be used for skipping these instructions. This means there are two poke targets for handling direct tailcalls. Simplified flow can be presented as three sections: 1. skip call or nop (poke->tailcall_bypass) 2. stack unwind 3. call tail or nop (poke->tailcall_target) It would be possible under specific circumstances that one of CPU might be in point 2 and point 3 is not yet updated (nop), which would lead to problems mentioned in patch 4 commit message, IOW unwind section should not be executed if there is no target program. We can define the following state matrix for that (courtesy of Bjorn): A nop, unwind, nop B nop, unwind, tail C skip, unwind, nop D skip, unwind, tail A is forbidden (lead to incorrectness). The state transitions between tailcall install/update/remove will work as follows: First install tail call f: C->D->B(f) * poke the tailcall, after that get rid of the skip Update tail call f to f': B(f)->B(f') * poke the tailcall (poke->tailcall_target) and do NOT touch the poke->tailcall_bypass Remove tail call: B(f')->C(f') * poke->tailcall_bypass is poked back to jump, then we wait the RCU grace period so that other programs will finish its execution and after that we are safe to remove the poke->tailcall_target Install new tail call (f''): C(f')->D(f'')->B(f''). * same as first step This way CPU can never be exposed to "unwind, tail" state. ------------------------------------------------------------------- Performance impact: All of this work, as stated in [2], started as a way to speed up AF-XDP by dropping the push/pop of unused callee saved registers in prologue and epilogue. Impact is positive, 15% of performance gain. However, it is obvious that it will have a negative impact on BPF programs that utilize tailcalls, but we think its volume is acceptable for the feature that this set contains. Below are te numbers from 'perf stat' for two scenarios. First scenario is the output of command: $ sudo perf stat -ddd -r 1024 ./test_progs -t tailcalls tailcalls kselftest was modified in a following way: - only tailcall1 subtest is enabled - each of the bpf_prog_test_run() calls got set 'repeat' argument to 1000000 Numbers without this set: Performance counter stats for './test_progs -t tailcalls' (1024 runs): 261.68 msec task-clock # 0.998 CPUs utilized ( +- 0.12% ) 5 context-switches # 0.017 K/sec ( +- 0.54% ) 0 cpu-migrations # 0.000 K/sec ( +- 23.37% ) 113 page-faults # 0.433 K/sec ( +- 0.03% ) 877,156,850 cycles # 3.352 GHz ( +- 0.11% ) (30.31%) 1,379,322,515 instructions # 1.57 insn per cycle ( +- 0.02% ) (38.17%) 218,869,567 branches # 836.395 M/sec ( +- 0.01% ) (38.46%) 11,954,183 branch-misses # 5.46% of all branches ( +- 0.01% ) (38.74%) 283,350,418 L1-dcache-loads # 1082.805 M/sec ( +- 0.01% ) (39.00%) 156,323 L1-dcache-load-misses # 0.06% of all L1-dcache hits ( +- 0.74% ) (39.05%) 37,309 LLC-loads # 0.143 M/sec ( +- 1.02% ) (31.08%) 15,263 LLC-load-misses # 40.91% of all LL-cache hits ( +- 0.90% ) (30.95%) <not supported> L1-icache-loads 130,427 L1-icache-load-misses ( +- 0.45% ) (30.80%) 285,369,370 dTLB-loads # 1090.520 M/sec ( +- 0.01% ) (30.64%) 1,154 dTLB-load-misses # 0.00% of all dTLB cache hits ( +- 1.26% ) (30.46%) 2,015 iTLB-loads # 0.008 M/sec ( +- 1.12% ) (30.31%) 551 iTLB-load-misses # 27.34% of all iTLB cache hits ( +- 1.29% ) (30.20%) <not supported> L1-dcache-prefetches <not supported> L1-dcache-prefetch-misses 0.262276 +- 0.000316 seconds time elapsed ( +- 0.12% ) With: Performance counter stats for './test_progs -t tailcalls' (1024 runs): 362.37 msec task-clock # 0.671 CPUs utilized ( +- 0.11% ) 28 context-switches # 0.077 K/sec ( +- 0.15% ) 0 cpu-migrations # 0.001 K/sec ( +- 4.46% ) 113 page-faults # 0.313 K/sec ( +- 0.03% ) 895,804,416 cycles # 2.472 GHz ( +- 0.08% ) (30.50%) 1,339,401,398 instructions # 1.50 insn per cycle ( +- 0.04% ) (38.29%) 302,718,849 branches # 835.385 M/sec ( +- 0.04% ) (38.39%) 11,962,089 branch-misses # 3.95% of all branches ( +- 0.05% ) (38.56%) 248,044,443 L1-dcache-loads # 684.505 M/sec ( +- 0.03% ) (38.70%) 239,882 L1-dcache-load-misses # 0.10% of all L1-dcache hits ( +- 0.49% ) (38.69%) 76,904 LLC-loads # 0.212 M/sec ( +- 0.96% ) (30.88%) 23,472 LLC-load-misses # 30.52% of all LL-cache hits ( +- 0.98% ) (30.85%) <not supported> L1-icache-loads 193,803 L1-icache-load-misses ( +- 0.53% ) (30.81%) 249,775,412 dTLB-loads # 689.282 M/sec ( +- 0.04% ) (30.81%) 2,176 dTLB-load-misses # 0.00% of all dTLB cache hits ( +- 1.53% ) (30.73%) 2,914 iTLB-loads # 0.008 M/sec ( +- 1.23% ) (30.59%) 978 iTLB-load-misses # 33.57% of all iTLB cache hits ( +- 1.29% ) (30.48%) <not supported> L1-dcache-prefetches <not supported> L1-dcache-prefetch-misses 0.540236 +- 0.000454 seconds time elapsed ( +- 0.08% ) Second conducted measurement was on BPF kselftest flow_dissector that is using the progs/bpf_flow.c with 'repeat' argument on bpf_prog_test_run_xattr set also to 1000000. Without: Performance counter stats for './test_progs -t flow_dissector' (1024 runs): 1,355.18 msec task-clock # 0.989 CPUs utilized ( +- 0.11% ) 28 context-switches # 0.021 K/sec ( +- 0.49% ) 0 cpu-migrations # 0.000 K/sec ( +- 7.86% ) 125 page-faults # 0.093 K/sec ( +- 0.03% ) 4,609,228,676 cycles # 3.401 GHz ( +- 0.03% ) (30.70%) 6,735,946,489 instructions # 1.46 insn per cycle ( +- 0.01% ) (38.42%) 1,130,187,926 branches # 833.979 M/sec ( +- 0.01% ) (38.47%) 29,150,986 branch-misses # 2.58% of all branches ( +- 0.01% ) (38.51%) 1,737,548,851 L1-dcache-loads # 1282.158 M/sec ( +- 0.01% ) (38.56%) 659,851 L1-dcache-load-misses # 0.04% of all L1-dcache hits ( +- 0.78% ) (38.56%) 71,196 LLC-loads # 0.053 M/sec ( +- 0.97% ) (30.81%) 22,218 LLC-load-misses # 31.21% of all LL-cache hits ( +- 0.83% ) (30.79%) <not supported> L1-icache-loads 770,586 L1-icache-load-misses ( +- 0.67% ) (30.77%) 1,742,104,224 dTLB-loads # 1285.520 M/sec ( +- 0.01% ) (30.74%) 7,060 dTLB-load-misses # 0.00% of all dTLB cache hits ( +- 2.08% ) (30.72%) 4,282 iTLB-loads # 0.003 M/sec ( +- 16.98% ) (30.70%) 1,261 iTLB-load-misses # 29.46% of all iTLB cache hits ( +- 7.14% ) (30.68%) <not supported> L1-dcache-prefetches <not supported> L1-dcache-prefetch-misses 1.37087 +- 0.00145 seconds time elapsed ( +- 0.11% ) With: Performance counter stats for './test_progs -t flow_dissector' (1024 runs): 1,385.56 msec task-clock # 0.989 CPUs utilized ( +- 0.06% ) 28 context-switches # 0.020 K/sec ( +- 0.48% ) 0 cpu-migrations # 0.000 K/sec ( +- 7.20% ) 125 page-faults # 0.091 K/sec ( +- 0.03% ) 4,642,599,630 cycles # 3.351 GHz ( +- 0.03% ) (30.69%) 6,901,261,616 instructions # 1.49 insn per cycle ( +- 0.01% ) (38.41%) 1,130,623,950 branches # 816.006 M/sec ( +- 0.01% ) (38.45%) 29,161,215 branch-misses # 2.58% of all branches ( +- 0.01% ) (38.50%) 1,796,850,740 L1-dcache-loads # 1296.842 M/sec ( +- 0.01% ) (38.55%) 673,908 L1-dcache-load-misses # 0.04% of all L1-dcache hits ( +- 0.89% ) (38.56%) 70,394 LLC-loads # 0.051 M/sec ( +- 1.08% ) (30.82%) 24,575 LLC-load-misses # 34.91% of all LL-cache hits ( +- 0.66% ) (30.80%) <not supported> L1-icache-loads 729,421 L1-icache-load-misses ( +- 0.85% ) (30.77%) 1,800,871,042 dTLB-loads # 1299.743 M/sec ( +- 0.01% ) (30.75%) 6,133 dTLB-load-misses # 0.00% of all dTLB cache hits ( +- 2.55% ) (30.73%) 1,998 iTLB-loads # 0.001 M/sec ( +- 9.36% ) (30.70%) 1,152 iTLB-load-misses # 57.66% of all iTLB cache hits ( +- 3.02% ) (30.68%) <not supported> L1-dcache-prefetches <not supported> L1-dcache-prefetch-misses 1.400577 +- 0.000780 seconds time elapsed ( +- 0.06% ) Interesting fact is that I observed the huge iTLB-load-misses counts on clean kernel as well: flow_dissector test: 2,613 iTLB-loads # 0.002 M/sec ( +- 21.90% ) (30.70%) 16,483 iTLB-load-misses # 630.78% of all iTLB cache hits ( +- 79.63% ) (30.68%) tailcalls test: 1,996 iTLB-loads # 0.008 M/sec ( +- 1.08% ) (30.33%) 7,272 iTLB-load-misses # 364.24% of all iTLB cache hits ( +- 92.01% ) (30.21%) So probably Alexei's suspicion about get_random_int() doing strange things was right. ------------------------------------------------------------------- Thank you, Maciej [1]: https://lore.kernel.org/bpf/20200517043227.2gpq22ifoq37ogst@ast-mbp.dhcp.thefacebook.com/ [2]: https://lore.kernel.org/bpf/20200511143912.34086-1-maciej.fijalkowski@intel.com/ [3]: https://lore.kernel.org/bpf/20200702134930.4717-1-maciej.fijalkowski@intel.com/ [4]: https://lore.kernel.org/bpf/20200715233634.3868-1-maciej.fijalkowski@intel.com/ [5]: https://lore.kernel.org/netdev/20200721115321.3099-1-maciej.fijalkowski@intel.com/ [6]: https://lore.kernel.org/netdev/20200724173557.5764-1-maciej.fijalkowski@intel.com/ Maciej Fijalkowski (6): bpf, x64: use %rcx instead of %rax for tail call retpolines bpf: propagate poke descriptors to subprograms bpf: rename poke descriptor's 'ip' member to 'tailcall_target' bpf, x64: rework pro/epilogue and tailcall handling in JIT bpf: allow for tailcalls in BPF subprograms for x64 JIT selftests: bpf: add dummy prog for bpf2bpf with tailcall arch/x86/include/asm/nospec-branch.h | 16 +- arch/x86/net/bpf_jit_comp.c | 249 +++++++++++++----- include/linux/bpf.h | 7 +- kernel/bpf/arraymap.c | 55 +++- kernel/bpf/core.c | 3 +- kernel/bpf/verifier.c | 57 +++- .../selftests/bpf/prog_tests/tailcalls.c | 85 ++++++ tools/testing/selftests/bpf/progs/tailcall6.c | 38 +++ 8 files changed, 424 insertions(+), 86 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/tailcall6.c