Skip to contentSkip to conversation

Segmented Stacks for BPF Programs

LSF/MM/BPF TOPIC Yonghong Song 3 participants 5 messages Feb 14, 2024 – Feb 19, 2024 BPF

lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

For each active kernel thread, the thread stack size is 2*PAGE_SIZE ([1]). Each bpf program has a maximum stack size 512 bytes to avoid overflowing the thread stack. But nested bpf programs may post a challenge to avoid stack overflow.

For example, currently we already allow nested bpf programs esp in tracing, i.e.,
  Prog_A
    -> Call Helper_B
      -> Call Func_C
        -> fentry program is called due to Func_C.
          -> Call Helper_D and then Func_E
            -> fentry due to Func_E
              -> ...
If we have too many bpf programs in the chain and each bpf program has close to 512 byte stack size, it could overflow the kernel thread stack.

Another more practical potential use case is from a discussion between Alexei and Tejun. It is possible for a complex scheduler like sched-ext, we could have BPF prog hierarchy like below:
                       Prog_1 (at system level)
          Prog_Numa_1    Prog_Numa_2 ...  Prog_Numa_4 Prog_LLC_1 Prog_LLC_2 ...
     Prog_CPU_1 ...

Basically, the top bpf program (Prog_1) will call Prog_Numa_* programs

through a kfunc to collect information from programs in each numa node. Each Prog_Numa_* program will call Prog_LLC_* programs to collect information from programs in each llc domain in that particular numa node, etc. The same for Prog_LLC_* vs. Prog_CPU_*.
Now we have four level nested bpf programs.

The proposed approach is to allocate stack from heap for each bpf program. That way, we do not need to worry about kernel stack overflow. Such an approach is called segmented stacks ([2]) in clang/gcc/go etc.

Obviously there are some drawbacks for segmented stack approach:
 - some performance degradation, so this approach may not for everyone.
 - stack backtracking,  kernel changes are necessary.

  [1] https://www.kernel.org/doc/html/next/x86/kernel-stacks.html
  [2] https://releases.llvm.org/3.0/docs/SegmentedStacks.html

#1 lore raw
Quoted 35 lines · Yonghong Song

For each active kernel thread, the thread stack size is 2*PAGE_SIZE ([1]). Each bpf program has a maximum stack size 512 bytes to avoid overflowing the thread stack. But nested bpf programs may post a challenge to avoid stack overflow.

For example, currently we already allow nested bpf programs esp in tracing, i.e.,
Prog_A

     -> Call Helper_B
       -> Call Func_C
         -> fentry program is called due to Func_C.
           -> Call Helper_D and then Func_E
             -> fentry due to Func_E
               -> ...

If we have too many bpf programs in the chain and each bpf program has close to 512 byte stack size, it could overflow the kernel thread stack.

Another more practical potential use case is from a discussion between Alexei and Tejun. It is possible for a complex scheduler like sched-ext, we could have BPF prog hierarchy like below:

                        Prog_1 (at system level)
           Prog_Numa_1    Prog_Numa_2 ...  Prog_Numa_4
        Prog_LLC_1 Prog_LLC_2 ...
      Prog_CPU_1 ...

Basically, the top bpf program (Prog_1) will call Prog_Numa_* programs

through a kfunc to collect information from programs in each numa node. Each Prog_Numa_* program will call Prog_LLC_* programs to collect information from programs in each llc domain in that particular numa node, etc. The same for Prog_LLC_* vs. Prog_CPU_*.
Now we have four level nested bpf programs.

Quoted 8 lines

The proposed approach is to allocate stack from heap for each bpf program. That way, we do not need to worry about kernel stack overflow. Such an approach is called segmented stacks ([2]) in clang/gcc/go etc.

Obviously there are some drawbacks for segmented stack approach:
- some performance degradation, so this approach may not for everyone.
- stack backtracking, kernel changes are necessary.

I suspect segmented stacks the way compilers do them are not suitable for bpf progs, since they break backtraces and backtrace is a crucial feature that must work even when there are kernel bugs.
How about we keep call/ret, save/restore of callee saved regs in the normal stack, but use a parallel memory (per-cpu or some other) for bpf prog needs. What bpf prog thinks of stack will be in that memory while the call chain will remain correct.
From bpf prog pov the stack is where bpf_reg_r10 points to. It doesn't have to be in the kernel stack. Shadow memory will work.

Let's also call it something else than "segmented stack" to avoid confusion.

author reviewer
#2 lore raw
Quoted 43 lines · Alexei Starovoitov
Quoted 34 lines · Yonghong Song

For each active kernel thread, the thread stack size is 2*PAGE_SIZE ([1]). Each bpf program has a maximum stack size 512 bytes to avoid overflowing the thread stack. But nested bpf programs may post a challenge to avoid stack overflow.

For example, currently we already allow nested bpf programs esp in tracing, i.e.,

    Prog_A
      -> Call Helper_B
        -> Call Func_C
          -> fentry program is called due to Func_C.
            -> Call Helper_D and then Func_E
              -> fentry due to Func_E
                -> ...

If we have too many bpf programs in the chain and each bpf program has close to 512 byte stack size, it could overflow the kernel thread stack.

Another more practical potential use case is from a discussion between Alexei and Tejun. It is possible for a complex scheduler like sched-ext, we could have BPF prog hierarchy like below:

                         Prog_1 (at system level)
            Prog_Numa_1    Prog_Numa_2 ...  Prog_Numa_4
         Prog_LLC_1 Prog_LLC_2 ...
       Prog_CPU_1 ...

Basically, the top bpf program (Prog_1) will call Prog_Numa_* programs

through a kfunc to collect information from programs in each numa node. Each Prog_Numa_* program will call Prog_LLC_* programs to collect information from programs in each llc domain in that particular numa node, etc. The same for Prog_LLC_* vs. Prog_CPU_*.
Now we have four level nested bpf programs.

Quoted 8 lines

The proposed approach is to allocate stack from heap for each bpf program. That way, we do not need to worry about kernel stack overflow. Such an approach is called segmented stacks ([2]) in clang/gcc/go etc.

Obviously there are some drawbacks for segmented stack approach:
- some performance degradation, so this approach may not for everyone.
- stack backtracking, kernel changes are necessary.

Quoted 9 lines

I suspect segmented stacks the way compilers do them are not suitable for bpf progs, since they break backtraces and backtrace is a crucial feature that must work even when there are kernel bugs.
How about we keep call/ret, save/restore of callee saved regs in the normal stack, but use a parallel memory (per-cpu or some other) for bpf prog needs. What bpf prog thinks of stack will be in that memory while the call chain will remain correct.
From bpf prog pov the stack is where bpf_reg_r10 points to.
It doesn't have to be in the kernel stack. Shadow memory will work.

Thanks for suggestions. Make sense. This will resolve backtrace issue. Let me experiment with this approach.

Quoted 3 lines

Let's also call it something else than "segmented stack" to avoid confusion.

Indeed, "segmented stack" terminoloty is not appropriate any more since the original stack is backtracable. Will think of a different one.

#3 lore raw
In reply to Yonghong Song

Hi Yonghong,

Quoted 5 lines · Yonghong Song

For each active kernel thread, the thread stack size is 2*PAGE_SIZE ([1]). Each bpf program has a maximum stack size 512 bytes to avoid overflowing the thread stack. But nested bpf programs may post a challenge to avoid stack overflow.

Quoted 12 lines

For example, currently we already allow nested bpf programs esp in tracing, i.e.,
  Prog_A
    -> Call Helper_B
      -> Call Func_C
        -> fentry program is called due to Func_C.
          -> Call Helper_D and then Func_E
            -> fentry due to Func_E
              -> ...
If we have too many bpf programs in the chain and each bpf program has close to 512 byte stack size, it could overflow the kernel thread stack.

Just curious - overflowing the thread stack would cause some kind of panic right? And also, segmented/split stacks for bpf just reduces likelihood of stack overflow due to BPF prog stack requirements. In theory, a deep call stack due to fentry probes could still occur, right?

[...]

Thanks,
Daniel

author reviewer
#4 lore raw
Quoted 20 lines · Daniel Xu

Hi Yonghong,

Quoted 5 lines · Yonghong Song

For each active kernel thread, the thread stack size is 2*PAGE_SIZE ([1]). Each bpf program has a maximum stack size 512 bytes to avoid overflowing the thread stack. But nested bpf programs may post a challenge to avoid stack overflow.

Quoted 12 lines

For example, currently we already allow nested bpf programs esp in tracing, i.e.,
  Prog_A
    -> Call Helper_B
      -> Call Func_C
        -> fentry program is called due to Func_C.
          -> Call Helper_D and then Func_E
            -> fentry due to Func_E
              -> ...
If we have too many bpf programs in the chain and each bpf program has close to 512 byte stack size, it could overflow the kernel thread stack.

Quoted 2 lines

Just curious - overflowing the thread stack would cause some kind of panic right? And also, segmented/split stacks for bpf just reduces

Yes. immediately after normal thread stack, there is a guard page. If there is a load/store to that guard page, kernel will panic.

Quoted 1 line

likelihood of stack overflow due to BPF prog stack requirements. In

This is the intention as bpf prog will use a separate stack for all its local variables.

Quoted 1 line

theory, a deep call stack due to fentry probes could still occur, right?

Yes, although currently I did not see a lot of use cases for this, but still it is possible.

Quoted 5 lines

[...]

Thanks,
Daniel