Skip to contentSkip to conversation

bpf: Support shadow stack for bpf progs

RFC PATCH Superseded Yonghong Song 3 participants 6 messages Jun 10, 2024 – Jun 18, 2024

Subsystems (4)

v1 of 12 Superseded Latest is v12 →

lore
Share & tools
lore

Yonghong Song

author reviewer
#0 lore raw

RFC PATCH 1/1 bpf: Support shadow stack for bpf progs

The main motivation for shadow stack comes from nested scheduler in sched-ext from Tejun. The basic idea is that
- each cgroup will its own associated bpf program,
- bpf program with parent cgroup will call bpf programs in immediate child cgroups.

Let us say we have the following cgroup hierarchy:
root_cg (prog0):

    cg1 (prog1):
      cg11 (prog11):
        cg111 (prog111)
        cg112 (prog112)
      cg12 (prog12):
        cg121 (prog121)
        cg122 (prog122)
    cg2 (prog2):
      cg21 (prog21)
      cg22 (prog22)
      cg23 (prog23)

In the above example, prog0 will call a kfunc which will call prog1 and prog2 to get sched info for cg1 and cg2 and then the information is summarized and sent back to prog0. Similarly, prog11 and prog12 will be invoked in the kfunc and the result will be summarized and sent back to prog1, etc.

Currently, for each thread, the x86 kernel allocate 8KB stack. The each bpf program (including its subprograms) has maximum 512B stack size to avoid potential stack overflow. And nested bpf programs increase the risk of stack overflow. To avoid potential stack overflow caused by bpf programs, this patch implemented a shadow stack so bpf program stack space is allocated dynamically when the program is jited.

But more than one instance of the same bpf program may run in the system. To make things simple, percpu shadow stack is allocated for each program, so if the same program is running on different cpus concurrently, we won't have any issue. Note that the kernel already have logic to prevent the recursion for the same bpf program on the same cpu (kprobe, fentry, etc.).

The patch implemented a percpu shadow stack based approach for x86 arch.
- The stack size will be 0.
- In the beginning of jit, r9 is used to save percpu shadow stack pointer.
- Each rbp in the bpf asm insn is replaced by r9.
- For each call, push r9 before the call and pop r9 after the call to preserve r9 value.

The following are some code example to illustrate the idea for selftest cgroup_skb_sk_lookup:

   the existing code                        the shadow-stack approach code
   endbr64                                  endbr64
   nop    DWORD PTR [rax+rax*1+0x0]         nop    DWORD PTR [rax+rax*1+0x0]
   xchg   ax,ax                             xchg   ax,ax
   push   rbp                               push   rbp
   mov    rbp,rsp                           mov    rbp,rsp
   endbr64                                  endbr64
   sub    rsp,0x68
   push   rbx                               push   rbx
   ...                                      ...
   ...                                      mov    r9d,0x8c1c860
   ...                                      add    r9,QWORD PTR gs:0x21a00
   ...                                      ...
   mov    rdx,rbp                           mov    rdx, r9
   add    rdx,0xffffffffffffffb4            rdx,0xffffffffffffffb4
   ...                                      ...
   mov    ecx,0x28                          mov    ecx,0x28
                                            push   r9
   call   0xffffffffe305e474                call   0xffffffffe305e524
                                            pop    r9
   mov    rdi,rax                           mov    rdi,rax
   ...                                      ...
   movzx  rdi,BYTE PTR [rbp-0x46]           movzx  rdi,BYTE PTR [r9-0x46]
   ...                                      ...

So the number of insns is increased by 1 + num_of_calls * 2.

There are an alternative approach is to do
mov r9d,0x8c1c860
add r9,QWORD PTR gs:0x21a00
right before each rbp usage where the rbp is replaced with r9. The number of insns is increased by num_of_rbp_usage * 2.

The current implementation is preferred since for a bpf prog using a lot of stack space, the number of calls is mostly likely much smaller than stack access.

This simple implementation passed all selftests. I marked it as RFC since several issues need to be resolved.
- The tradeoff between simplicity/more_memory/reasonable_performance vs. complex/less_memory/worse_performance.

The percpu shadow stack makes implementation much simpler. My previous approach (as discussed in lsfmmbpf2024) used
a more complex way trying to avoid excess shadow stack memory by using a few percpu pages for non-sleepable programs and runtime allocation for sleepable programs. This can save some memory but will make jit more complex and also degrade performance quite a bit esp. for sleepable programs.
- Should we introduce a flag during program load to indicate whether the program should use shadow stack or not? There are a couple of cases here:
- for xdp prog, performance is hugely critical. the current implement may still degreate performance slightly.
- for a system with huge number of cpus, e.g., 256, 1024, and only one instance of the bpf program is running. It could be quite some memory waste, esp. if there are quite some bpf progs are running on the system.

---
 arch/x86/net/bpf_jit_comp.c | 61 ++++++++++++++++++++++++++++++++++---
 include/linux/bpf.h         |  1 +
 kernel/bpf/syscall.c        |  1 +
 3 files changed, 59 insertions(+), 4 deletions(-)
arch/x86/net/bpf_jit_comp.c +57 -4
index 5159c7a22922..1af62ade0ceb 100644
@@ -19,6 +19,8 @@
 #include <asm/unwind.h>
 #include <asm/cfi.h>
 
+static const int global_enable_shadow_stack = 1;
+
 static bool all_callee_regs_used[4] = {true, true, true, true};
 
 static u8 *emit_code(u8 *ptr, u32 bytes, unsigned int len)
@@ -1311,6 +1313,21 @@ static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op)
 	*pprog = prog;
 }
 
+static void emit_percpu_shadow_frame_ptr(u8 **pprog, void *shadow_frame_ptr)
+{
+	u8 *prog = *pprog;
+
+	/* movabs r9, shadow_frame_ptr */
+	emit_mov_imm32(&prog, false, X86_REG_R9, (u32) (long) shadow_frame_ptr);
+
+	/* add <r9>, gs:[<off>] */
+	EMIT2(0x65, 0x4c);
+	EMIT3(0x03, 0x0c, 0x25);
+	EMIT((u32)(unsigned long)&this_cpu_off, 4);
+
+	*pprog = prog;
+}
+
 #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
 
 /* mov rax, qword ptr [rbp - rounded_stack_depth - 8] */
@@ -1326,13 +1343,31 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
 	int insn_cnt = bpf_prog->len;
 	bool tail_call_seen = false;
 	bool seen_exit = false;
+	void *percpu_shadow_stack_ptr, *shadow_frame_ptr = NULL;
+	bool enable_shadow_stack = global_enable_shadow_stack;
 	u8 temp[BPF_MAX_INSN_SIZE + BPF_INSN_SAFETY];
+	u32 stack_depth = bpf_prog->aux->stack_depth;
 	u64 arena_vm_start, user_vm_start;
 	int i, excnt = 0;
 	int ilen, proglen = 0;
 	u8 *prog = temp;
 	int err;
 
+	if (stack_depth && enable_shadow_stack) {
+		if (bpf_prog->percpu_shadow_stack_ptr) {
+			percpu_shadow_stack_ptr = bpf_prog->percpu_shadow_stack_ptr;
+		} else {
+			percpu_shadow_stack_ptr = __alloc_percpu_gfp(stack_depth, 8, GFP_KERNEL);
+			if (!percpu_shadow_stack_ptr)
+				return -ENOMEM;
+			bpf_prog->percpu_shadow_stack_ptr = percpu_shadow_stack_ptr;
+		}
+		shadow_frame_ptr = percpu_shadow_stack_ptr + round_up(stack_depth, 8);
+		stack_depth = 0;
+	} else {
+		enable_shadow_stack = 0;
+	}
+
 	arena_vm_start = bpf_arena_get_kern_vm_start(bpf_prog->aux->arena);
 	user_vm_start = bpf_arena_get_user_vm_start(bpf_prog->aux->arena);
 
@@ -1342,7 +1377,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
 	/* tail call's presence in current prog implies it is reachable */
 	tail_call_reachable |= tail_call_seen;
 
-	emit_prologue(&prog, bpf_prog->aux->stack_depth,
+	emit_prologue(&prog, stack_depth,
 		      bpf_prog_was_classic(bpf_prog), tail_call_reachable,
 		      bpf_is_subprog(bpf_prog), bpf_prog->aux->exception_cb);
 	/* Exception callback will clobber callee regs for its own use, and
@@ -1364,6 +1399,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
 		emit_mov_imm64(&prog, X86_REG_R12,
 			       arena_vm_start >> 32, (u32) arena_vm_start);
 
+	if (enable_shadow_stack)
+		emit_percpu_shadow_frame_ptr(&prog, shadow_frame_ptr);
+
 	ilen = prog - temp;
 	if (rw_image)
 		memcpy(rw_image + proglen, temp, ilen);
@@ -1383,6 +1421,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
 		u8 *func;
 		int nops;
 
+		if (enable_shadow_stack) {
+			if (src_reg == BPF_REG_FP)
+				src_reg = X86_REG_R9;
+
+			if (dst_reg == BPF_REG_FP)
+				dst_reg = X86_REG_R9;
+		}
+
 		switch (insn->code) {
 			/* ALU */
 		case BPF_ALU | BPF_ADD | BPF_X:
@@ -2014,6 +2060,7 @@ st:			if (is_imm8(insn->off))
 				emit_mov_reg(&prog, is64, real_src_reg, BPF_REG_0);
 				/* Restore R0 after clobbering RAX */
 				emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
+
 				break;
 			}
 
@@ -2038,14 +2085,20 @@ st:			if (is_imm8(insn->off))
 
 			func = (u8 *) __bpf_call_base + imm32;
 			if (tail_call_reachable) {
-				RESTORE_TAIL_CALL_CNT(bpf_prog->aux->stack_depth);
+				RESTORE_TAIL_CALL_CNT(stack_depth);
 				ip += 7;
 			}
 			if (!imm32)
 				return -EINVAL;
+			if (enable_shadow_stack) {
+				EMIT2(0x41, 0x51);
+				ip += 2;
+			}
 			ip += x86_call_depth_emit_accounting(&prog, func, ip);
 			if (emit_call(&prog, func, ip))
 				return -EINVAL;
+			if (enable_shadow_stack)
+				EMIT2(0x41, 0x59);
 			break;
 		}
 
@@ -2055,13 +2108,13 @@ st:			if (is_imm8(insn->off))
 							  &bpf_prog->aux->poke_tab[imm32 - 1],
 							  &prog, image + addrs[i - 1],
 							  callee_regs_used,
-							  bpf_prog->aux->stack_depth,
+							  stack_depth,
 							  ctx);
 			else
 				emit_bpf_tail_call_indirect(bpf_prog,
 							    &prog,
 							    callee_regs_used,
-							    bpf_prog->aux->stack_depth,
+							    stack_depth,
 							    image + addrs[i - 1],
 							    ctx);
 			break;
include/linux/bpf.h +1 -0
index a834f4b761bc..08014b4954f0 100644
@@ -1563,6 +1563,7 @@ struct bpf_prog {
 					    const struct bpf_insn *insn);
 	struct bpf_prog_aux	*aux;		/* Auxiliary fields */
 	struct sock_fprog_kern	*orig_prog;	/* Original BPF program */
+	void			*percpu_shadow_stack_ptr;
 	/* Instructions for interpreter */
 	union {
 		DECLARE_FLEX_ARRAY(struct sock_filter, insns);
kernel/bpf/syscall.c +1 -0
index 5070fa20d05c..7b9093cc3671 100644
@@ -2244,6 +2244,7 @@ static void __bpf_prog_put_rcu(struct rcu_head *rcu)
 
 	kvfree(aux->func_info);
 	kfree(aux->func_info_aux);
+	free_percpu(aux->prog->percpu_shadow_stack_ptr);
 	free_uid(aux->user);
 	security_bpf_prog_free(aux->prog);
 	bpf_prog_free(aux->prog);
Signature · 1 line
2.43.0
#1 lore raw
Quoted 1 line · Yonghong Song

I think "shadow stack" already has at least two different meanings in the kernel.
Let's avoid adding 3rd.
How about "divided stack" ?

arch/x86/net/bpf_jit_comp.c static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op) · line 1326

Quoted 11 lines
arch/x86/net/bpf_jit_comp.c +11 -0
+static void emit_percpu_shadow_frame_ptr(u8 **pprog, void *shadow_frame_ptr)
+{
+       u8 *prog = *pprog;
+
+       /* movabs r9, shadow_frame_ptr */
+       emit_mov_imm32(&prog, false, X86_REG_R9, (u32) (long) shadow_frame_ptr);
+
+       /* add <r9>, gs:[<off>] */
+       EMIT2(0x65, 0x4c);
+       EMIT3(0x03, 0x0c, 0x25);
+       EMIT((u32)(unsigned long)&this_cpu_off, 4);

I think this can be one insn:
lea r9, gs:[(u32)shadow_frame_ptr]

Quoted 1 line

+ if (stack_depth && enable_shadow_stack) {

I think enabling it for progs with small stack usage
is unnecessary.
The definition of "small" is complicated.
I feel stack_depth <= 64 can stay as-is and
all networking progs don't have to use it either,
since they're called from known places.
While tracing progs can be anywhere, so I'd enable
divided stack for
stack_depth > 64 && prog_type == kprobe, tp, raw_tp, tracing, perf_event.

Quoted 37 lines
arch/x86/net/bpf_jit_comp.c +18 -1
+               if (bpf_prog->percpu_shadow_stack_ptr) {
+                       percpu_shadow_stack_ptr = bpf_prog->percpu_shadow_stack_ptr;
+               } else {
+                       percpu_shadow_stack_ptr = __alloc_percpu_gfp(stack_depth, 8, GFP_KERNEL);
+                       if (!percpu_shadow_stack_ptr)
+                               return -ENOMEM;
+                       bpf_prog->percpu_shadow_stack_ptr = percpu_shadow_stack_ptr;
+               }
+               shadow_frame_ptr = percpu_shadow_stack_ptr + round_up(stack_depth, 8);
+               stack_depth = 0;
+       } else {
+               enable_shadow_stack = 0;
+       }
+
        arena_vm_start = bpf_arena_get_kern_vm_start(bpf_prog->aux->arena);
        user_vm_start = bpf_arena_get_user_vm_start(bpf_prog->aux->arena);
@@ -1342,7 +1377,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
        /* tail call's presence in current prog implies it is reachable */
        tail_call_reachable |= tail_call_seen;
 
-       emit_prologue(&prog, bpf_prog->aux->stack_depth,
+       emit_prologue(&prog, stack_depth,
                      bpf_prog_was_classic(bpf_prog), tail_call_reachable,
                      bpf_is_subprog(bpf_prog), bpf_prog->aux->exception_cb);
        /* Exception callback will clobber callee regs for its own use, and
@@ -1364,6 +1399,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                emit_mov_imm64(&prog, X86_REG_R12,
                               arena_vm_start >> 32, (u32) arena_vm_start);
 
+       if (enable_shadow_stack)
+               emit_percpu_shadow_frame_ptr(&prog, shadow_frame_ptr);
+
        ilen = prog - temp;
        if (rw_image)
                memcpy(rw_image + proglen, temp, ilen);

arch/x86/net/bpf_jit_comp.c static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image · line 1429

Quoted 9 lines
arch/x86/net/bpf_jit_comp.c +6 -0
@@ -1383,6 +1421,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                u8 *func;
                int nops;
 
+               if (enable_shadow_stack) {
+                       if (src_reg == BPF_REG_FP)
+                               src_reg = X86_REG_R9;
+
+                       if (dst_reg == BPF_REG_FP)
+                               dst_reg = X86_REG_R9;

the verifier will reject a prog that attempts to write into R10. So the above shouldn't be necessary.

Quoted 22 lines
arch/x86/net/bpf_jit_comp.c +4 -1
+               }
+
                switch (insn->code) {
                        /* ALU */
                case BPF_ALU | BPF_ADD | BPF_X:
@@ -2014,6 +2060,7 @@ st:                       if (is_imm8(insn->off))
                                emit_mov_reg(&prog, is64, real_src_reg, BPF_REG_0);
                                /* Restore R0 after clobbering RAX */
                                emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
+
                                break;
                        }
 
@@ -2038,14 +2085,20 @@ st:                     if (is_imm8(insn->off))
 
                        func = (u8 *) __bpf_call_base + imm32;
                        if (tail_call_reachable) {
-                               RESTORE_TAIL_CALL_CNT(bpf_prog->aux->stack_depth);
+                               RESTORE_TAIL_CALL_CNT(stack_depth);
                                ip += 7;
                        }
                        if (!imm32)

arch/x86/net/bpf_jit_comp.c st: if (is_imm8(insn->off)) · line 2101

Quoted 10 lines
arch/x86/net/bpf_jit_comp.c +6 -0
                                return -EINVAL;
+                       if (enable_shadow_stack) {
+                               EMIT2(0x41, 0x51);
+                               ip += 2;
+                       }
                        ip += x86_call_depth_emit_accounting(&prog, func, ip);
                        if (emit_call(&prog, func, ip))
                                return -EINVAL;
+                       if (enable_shadow_stack)
+                               EMIT2(0x41, 0x59);

push/pop around calls are load/store plus math on %rsp. I think it's cheaper to reload r9 after the call with a single insn.
The reload of r9 is effectively gs+const. There is no memory access. So it should be faster.

Technically we can replace all uses of R10==rbp with 'gs:' based instructions.
Like:
r1 = r10
can be jitted into
lea rdi, gs + (u32)shadow_frame_ptr

and r0 = *(u32 *)(r10 - 64)
can be jitted into:
mov rax, dword ptr gs:[(u32)shadow_frame_ptr - 64]

but that is probably a bunch of jit changes.
So I'd start with a simple reload of r9 after each call.

We need to micro-benchmark it to make sure there is no perf overhead.

author reviewer
#2 lore raw
Quoted 5 lines · Alexei Starovoitov

On Sun, Jun 9, 2024 at 10:18 PM Yonghong Song <[email protected]> wrote:
I think "shadow stack" already has at least two different meanings in the kernel.
Let's avoid adding 3rd.
How about "divided stack" ?

Naming is hard. Maybe "private stack" which suggests the stack is private to that program?

Quoted 14 lines

arch/x86/net/bpf_jit_comp.c static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op) · line 1326

Quoted 12 lines
arch/x86/net/bpf_jit_comp.c +11 -0
+static void emit_percpu_shadow_frame_ptr(u8 **pprog, void *shadow_frame_ptr)
+{
+       u8 *prog = *pprog;
+
+       /* movabs r9, shadow_frame_ptr */
+       emit_mov_imm32(&prog, false, X86_REG_R9, (u32) (long) shadow_frame_ptr);
+
+       /* add <r9>, gs:[<off>] */
+       EMIT2(0x65, 0x4c);
+       EMIT3(0x03, 0x0c, 0x25);
+       EMIT((u32)(unsigned long)&this_cpu_off, 4);

I think this can be one insn:
lea r9, gs:[(u32)shadow_frame_ptr]

Apparently, __alloc_percpu_gfp() may return a pointer which is beyond 32bit. That is why my RFC patch failed CI. I later tried to use

+ /* movabs r9, shadow_frame_ptr */
+ emit_mov_imm64(&prog, X86_REG_R9, (long) shadow_frame_ptr >> 32,
+ (u32) (long) shadow_frame_ptr);

and CI is successful. I did some on-demand test (https://github.com/kernel-patches/bpf/pull/7179)
and it succeeded with CI.

If __alloc_percpu_gfp() returns a pointer beyond 32bit, I am not sure whether we could get r9 with a single insn.

Quoted 11 lines
Quoted 2 lines

+ if (stack_depth && enable_shadow_stack) {

I think enabling it for progs with small stack usage
is unnecessary.
The definition of "small" is complicated.
I feel stack_depth <= 64 can stay as-is and
all networking progs don't have to use it either,
since they're called from known places.
While tracing progs can be anywhere, so I'd enable
divided stack for
stack_depth > 64 && prog_type == kprobe, tp, raw_tp, tracing, perf_event.

This does make sense. It partially aligns what I think for prog type side. We only need to enable 'divided stack' for certain prog types.

Quoted 41 lines
Quoted 41 lines
arch/x86/net/bpf_jit_comp.c +18 -1
+               if (bpf_prog->percpu_shadow_stack_ptr) {
+                       percpu_shadow_stack_ptr = bpf_prog->percpu_shadow_stack_ptr;
+               } else {
+                       percpu_shadow_stack_ptr = __alloc_percpu_gfp(stack_depth, 8, GFP_KERNEL);
+                       if (!percpu_shadow_stack_ptr)
+                               return -ENOMEM;
+                       bpf_prog->percpu_shadow_stack_ptr = percpu_shadow_stack_ptr;
+               }
+               shadow_frame_ptr = percpu_shadow_stack_ptr + round_up(stack_depth, 8);
+               stack_depth = 0;
+       } else {
+               enable_shadow_stack = 0;
+       }
+
         arena_vm_start = bpf_arena_get_kern_vm_start(bpf_prog->aux->arena);
         user_vm_start = bpf_arena_get_user_vm_start(bpf_prog->aux->arena);
@@ -1342,7 +1377,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
         /* tail call's presence in current prog implies it is reachable */
         tail_call_reachable |= tail_call_seen;
 
-       emit_prologue(&prog, bpf_prog->aux->stack_depth,
+       emit_prologue(&prog, stack_depth,
                       bpf_prog_was_classic(bpf_prog), tail_call_reachable,
                       bpf_is_subprog(bpf_prog), bpf_prog->aux->exception_cb);
         /* Exception callback will clobber callee regs for its own use, and
@@ -1364,6 +1399,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                 emit_mov_imm64(&prog, X86_REG_R12,
                                arena_vm_start >> 32, (u32) arena_vm_start);
 
+       if (enable_shadow_stack)
+               emit_percpu_shadow_frame_ptr(&prog, shadow_frame_ptr);
+
         ilen = prog - temp;
         if (rw_image)
                 memcpy(rw_image + proglen, temp, ilen);
@@ -1383,6 +1421,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                 u8 *func;
                 int nops;
 
Quoted 8 lines

arch/x86/net/bpf_jit_comp.c static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image · line 1429

Quoted 6 lines
arch/x86/net/bpf_jit_comp.c +6 -0
+               if (enable_shadow_stack) {
+                       if (src_reg == BPF_REG_FP)
+                               src_reg = X86_REG_R9;
+
+                       if (dst_reg == BPF_REG_FP)
+                               dst_reg = X86_REG_R9;

the verifier will reject a prog that attempts to write into R10. So the above shouldn't be necessary.

Actually there is at least one exception, e.g.,
if r10 > r5 goto +5
where dst is r10 and src r5.

For some insn where dst is intended to write with r10 like r10 = 10, and verifier will reject the program before jit, as you mentioned in the above.

Quoted 30 lines
Quoted 30 lines
arch/x86/net/bpf_jit_comp.c +8 -1
+               }
+
                 switch (insn->code) {
                         /* ALU */
                 case BPF_ALU | BPF_ADD | BPF_X:
@@ -2014,6 +2060,7 @@ st:                       if (is_imm8(insn->off))
                                 emit_mov_reg(&prog, is64, real_src_reg, BPF_REG_0);
                                 /* Restore R0 after clobbering RAX */
                                 emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
+
                                 break;
                         }
 
@@ -2038,14 +2085,20 @@ st:                     if (is_imm8(insn->off))
 
                         func = (u8 *) __bpf_call_base + imm32;
                         if (tail_call_reachable) {
-                               RESTORE_TAIL_CALL_CNT(bpf_prog->aux->stack_depth);
+                               RESTORE_TAIL_CALL_CNT(stack_depth);
                                 ip += 7;
                         }
                         if (!imm32)
                                 return -EINVAL;
+                       if (enable_shadow_stack) {
+                               EMIT2(0x41, 0x51);
+                               ip += 2;
+                       }
                         ip += x86_call_depth_emit_accounting(&prog, func, ip);
                         if (emit_call(&prog, func, ip))
Quoted 8 lines

arch/x86/net/bpf_jit_comp.c st: if (is_imm8(insn->off)) · line 2101

Quoted 3 lines
arch/x86/net/bpf_jit_comp.c +2 -0
                                 return -EINVAL;
+                       if (enable_shadow_stack)
+                               EMIT2(0x41, 0x59);

push/pop around calls are load/store plus math on %rsp. I think it's cheaper to reload r9 after the call with a single insn.
The reload of r9 is effectively gs+const. There is no memory access. So it should be faster.

Two insn may be necessary since __alloc_percpu_gfp() may return a pointer beyond 32 bits.

Quoted 8 lines

Technically we can replace all uses of R10==rbp with 'gs:' based instructions.
Like:
r1 = r10
can be jitted into
lea rdi, gs + (u32)shadow_frame_ptr

Quoted 6 lines

and r0 = *(u32 *)(r10 - 64)
can be jitted into:
mov rax, dword ptr gs:[(u32)shadow_frame_ptr - 64]

but that is probably a bunch of jit changes.
So I'd start with a simple reload of r9 after each call.

This is a good idea. We might need this so we only have one extra insn per call.

Quoted 2 lines

We need to micro-benchmark it to make sure there is no perf overhead.

Sure. Will do!

#3 lore raw
Quoted 11 lines · Yonghong Song
Quoted 5 lines · Alexei Starovoitov

On Sun, Jun 9, 2024 at 10:18 PM Yonghong Song <[email protected]> wrote:
I think "shadow stack" already has at least two different meanings in the kernel.
Let's avoid adding 3rd.
How about "divided stack" ?

Naming is hard. Maybe "private stack" which suggests the stack is private to that program?

I like it. "private stack" fits the best.

Quoted 22 lines
Quoted 14 lines

arch/x86/net/bpf_jit_comp.c static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op) · line 1326

Quoted 12 lines
arch/x86/net/bpf_jit_comp.c +11 -0
+static void emit_percpu_shadow_frame_ptr(u8 **pprog, void *shadow_frame_ptr)
+{
+       u8 *prog = *pprog;
+
+       /* movabs r9, shadow_frame_ptr */
+       emit_mov_imm32(&prog, false, X86_REG_R9, (u32) (long) shadow_frame_ptr);
+
+       /* add <r9>, gs:[<off>] */
+       EMIT2(0x65, 0x4c);
+       EMIT3(0x03, 0x0c, 0x25);
+       EMIT((u32)(unsigned long)&this_cpu_off, 4);

I think this can be one insn:
lea r9, gs:[(u32)shadow_frame_ptr]

Apparently, __alloc_percpu_gfp() may return a pointer which is beyond 32bit. That is why my RFC patch failed CI. I later tried to use

(quoted diff) +3 -0
+       /* movabs r9, shadow_frame_ptr */
+       emit_mov_imm64(&prog, X86_REG_R9, (long) shadow_frame_ptr >> 32,
+                      (u32) (long) shadow_frame_ptr);
Quoted 5 lines

and CI is successful. I did some on-demand test (https://github.com/kernel-patches/bpf/pull/7179)
and it succeeded with CI.

If __alloc_percpu_gfp() returns a pointer beyond 32bit, I am not sure whether we could get r9 with a single insn.

I see. Ok. Let's keep two insns sequence.

Quoted 66 lines
Quoted 12 lines
Quoted 3 lines

+ if (stack_depth && enable_shadow_stack) {

I think enabling it for progs with small stack usage
is unnecessary.
The definition of "small" is complicated.
I feel stack_depth <= 64 can stay as-is and
all networking progs don't have to use it either,
since they're called from known places.
While tracing progs can be anywhere, so I'd enable
divided stack for
stack_depth > 64 && prog_type == kprobe, tp, raw_tp, tracing, perf_event.

This does make sense. It partially aligns what I think for prog type side. We only need to enable 'divided stack' for certain prog types.

Quoted 41 lines
Quoted 41 lines
arch/x86/net/bpf_jit_comp.c +18 -1
+               if (bpf_prog->percpu_shadow_stack_ptr) {
+                       percpu_shadow_stack_ptr = bpf_prog->percpu_shadow_stack_ptr;
+               } else {
+                       percpu_shadow_stack_ptr = __alloc_percpu_gfp(stack_depth, 8, GFP_KERNEL);
+                       if (!percpu_shadow_stack_ptr)
+                               return -ENOMEM;
+                       bpf_prog->percpu_shadow_stack_ptr = percpu_shadow_stack_ptr;
+               }
+               shadow_frame_ptr = percpu_shadow_stack_ptr + round_up(stack_depth, 8);
+               stack_depth = 0;
+       } else {
+               enable_shadow_stack = 0;
+       }
+
         arena_vm_start = bpf_arena_get_kern_vm_start(bpf_prog->aux->arena);
         user_vm_start = bpf_arena_get_user_vm_start(bpf_prog->aux->arena);
@@ -1342,7 +1377,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
         /* tail call's presence in current prog implies it is reachable */
         tail_call_reachable |= tail_call_seen;
 
-       emit_prologue(&prog, bpf_prog->aux->stack_depth,
+       emit_prologue(&prog, stack_depth,
                       bpf_prog_was_classic(bpf_prog), tail_call_reachable,
                       bpf_is_subprog(bpf_prog), bpf_prog->aux->exception_cb);
         /* Exception callback will clobber callee regs for its own use, and
@@ -1364,6 +1399,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                 emit_mov_imm64(&prog, X86_REG_R12,
                                arena_vm_start >> 32, (u32) arena_vm_start);
 
+       if (enable_shadow_stack)
+               emit_percpu_shadow_frame_ptr(&prog, shadow_frame_ptr);
+
         ilen = prog - temp;
         if (rw_image)
                 memcpy(rw_image + proglen, temp, ilen);
@@ -1383,6 +1421,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                 u8 *func;
                 int nops;
 
Quoted 8 lines

arch/x86/net/bpf_jit_comp.c static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image · line 1429

Quoted 6 lines
arch/x86/net/bpf_jit_comp.c +6 -0
+               if (enable_shadow_stack) {
+                       if (src_reg == BPF_REG_FP)
+                               src_reg = X86_REG_R9;
+
+                       if (dst_reg == BPF_REG_FP)
+                               dst_reg = X86_REG_R9;

the verifier will reject a prog that attempts to write into R10. So the above shouldn't be necessary.

Quoted 3 lines

Actually there is at least one exception, e.g.,
if r10 > r5 goto +5
where dst is r10 and src r5.

Good point. We even have such a selftest to make sure it's rejected in unpriv.

SEC("socket")
__description("unpriv: cmp of frame pointer")
__success __failure_unpriv __msg_unpriv("R10 pointer comparison") __retval(0)
__naked void unpriv_cmp_of_frame_pointer(void)

{
        asm volatile ("                                 \
        if r10 == 0 goto l0_%=;                         \
Quoted 54 lines
Quoted 30 lines
Quoted 30 lines
arch/x86/net/bpf_jit_comp.c +8 -1
+               }
+
                 switch (insn->code) {
                         /* ALU */
                 case BPF_ALU | BPF_ADD | BPF_X:
@@ -2014,6 +2060,7 @@ st:                       if (is_imm8(insn->off))
                                 emit_mov_reg(&prog, is64, real_src_reg, BPF_REG_0);
                                 /* Restore R0 after clobbering RAX */
                                 emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
+
                                 break;
                         }
 
@@ -2038,14 +2085,20 @@ st:                     if (is_imm8(insn->off))
 
                         func = (u8 *) __bpf_call_base + imm32;
                         if (tail_call_reachable) {
-                               RESTORE_TAIL_CALL_CNT(bpf_prog->aux->stack_depth);
+                               RESTORE_TAIL_CALL_CNT(stack_depth);
                                 ip += 7;
                         }
                         if (!imm32)
                                 return -EINVAL;
+                       if (enable_shadow_stack) {
+                               EMIT2(0x41, 0x51);
+                               ip += 2;
+                       }
                         ip += x86_call_depth_emit_accounting(&prog, func, ip);
                         if (emit_call(&prog, func, ip))
Quoted 8 lines

arch/x86/net/bpf_jit_comp.c st: if (is_imm8(insn->off)) · line 2101

Quoted 3 lines
arch/x86/net/bpf_jit_comp.c +2 -0
                                 return -EINVAL;
+                       if (enable_shadow_stack)
+                               EMIT2(0x41, 0x59);

push/pop around calls are load/store plus math on %rsp. I think it's cheaper to reload r9 after the call with a single insn.
The reload of r9 is effectively gs+const. There is no memory access. So it should be faster.

Two insn may be necessary since __alloc_percpu_gfp() may return a pointer beyond 32 bits.

Quoted 12 lines

Technically we can replace all uses of R10==rbp with 'gs:' based instructions.
Like:
r1 = r10
can be jitted into
lea rdi, gs + (u32)shadow_frame_ptr

and r0 = *(u32 *)(r10 - 64)
can be jitted into:
mov rax, dword ptr gs:[(u32)shadow_frame_ptr - 64]

Quoted 5 lines
Quoted 2 lines

but that is probably a bunch of jit changes.
So I'd start with a simple reload of r9 after each call.

This is a good idea. We might need this so we only have one extra insn per call.

Since reload of r9 is a two insn sequence of 64-bit mov immediate, and load from gs:this_cpu_off, I suspect, push/pop r9 might be faster. So I'd stick to what you have already.

Interesting though that static per-cpu vars have 32-bit pointers, but dynamic per-cpu alloc returns full 64-bit? hmm.

author reviewer
#4 lore raw
Quoted 167 lines · Alexei Starovoitov
Quoted 9 lines · Yonghong Song
Quoted 5 lines · Alexei Starovoitov

On Sun, Jun 9, 2024 at 10:18 PM Yonghong Song <[email protected]> wrote:
I think "shadow stack" already has at least two different meanings in the kernel.
Let's avoid adding 3rd.
How about "divided stack" ?

Naming is hard. Maybe "private stack" which suggests the stack is private to that program?

I like it. "private stack" fits the best.

Quoted 20 lines
Quoted 5 lines
Quoted 5 lines
arch/x86/net/bpf_jit_comp.c +5 -0
+static void emit_percpu_shadow_frame_ptr(u8 **pprog, void *shadow_frame_ptr)
+{
+       u8 *prog = *pprog;
+
+       /* movabs r9, shadow_frame_ptr */
Quoted 8 lines

arch/x86/net/bpf_jit_comp.c static void emit_shiftx(u8 **pprog, u32 dst_reg, u8 src_reg, bool is64, u8 op) · line 1326

Quoted 6 lines
arch/x86/net/bpf_jit_comp.c +6 -0
+       emit_mov_imm32(&prog, false, X86_REG_R9, (u32) (long) shadow_frame_ptr);
+
+       /* add <r9>, gs:[<off>] */
+       EMIT2(0x65, 0x4c);
+       EMIT3(0x03, 0x0c, 0x25);
+       EMIT((u32)(unsigned long)&this_cpu_off, 4);

I think this can be one insn:
lea r9, gs:[(u32)shadow_frame_ptr]

Apparently, __alloc_percpu_gfp() may return a pointer which is beyond 32bit. That is why my RFC patch failed CI. I later tried to use

(quoted diff) +3 -0
+       /* movabs r9, shadow_frame_ptr */
+       emit_mov_imm64(&prog, X86_REG_R9, (long) shadow_frame_ptr >> 32,
+                      (u32) (long) shadow_frame_ptr);
Quoted 5 lines

and CI is successful. I did some on-demand test (https://github.com/kernel-patches/bpf/pull/7179)
and it succeeded with CI.

If __alloc_percpu_gfp() returns a pointer beyond 32bit, I am not sure whether we could get r9 with a single insn.

I see. Ok. Let's keep two insns sequence.

Quoted 61 lines
Quoted 10 lines
Quoted 1 line

+ if (stack_depth && enable_shadow_stack) {

I think enabling it for progs with small stack usage
is unnecessary.
The definition of "small" is complicated.
I feel stack_depth <= 64 can stay as-is and
all networking progs don't have to use it either,
since they're called from known places.
While tracing progs can be anywhere, so I'd enable
divided stack for
stack_depth > 64 && prog_type == kprobe, tp, raw_tp, tracing, perf_event.

This does make sense. It partially aligns what I think for prog type side. We only need to enable 'divided stack' for certain prog types.

Quoted 40 lines
Quoted 40 lines
arch/x86/net/bpf_jit_comp.c +18 -1
+               if (bpf_prog->percpu_shadow_stack_ptr) {
+                       percpu_shadow_stack_ptr = bpf_prog->percpu_shadow_stack_ptr;
+               } else {
+                       percpu_shadow_stack_ptr = __alloc_percpu_gfp(stack_depth, 8, GFP_KERNEL);
+                       if (!percpu_shadow_stack_ptr)
+                               return -ENOMEM;
+                       bpf_prog->percpu_shadow_stack_ptr = percpu_shadow_stack_ptr;
+               }
+               shadow_frame_ptr = percpu_shadow_stack_ptr + round_up(stack_depth, 8);
+               stack_depth = 0;
+       } else {
+               enable_shadow_stack = 0;
+       }
+
          arena_vm_start = bpf_arena_get_kern_vm_start(bpf_prog->aux->arena);
          user_vm_start = bpf_arena_get_user_vm_start(bpf_prog->aux->arena);
@@ -1342,7 +1377,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
          /* tail call's presence in current prog implies it is reachable */
          tail_call_reachable |= tail_call_seen;
 
-       emit_prologue(&prog, bpf_prog->aux->stack_depth,
+       emit_prologue(&prog, stack_depth,
                        bpf_prog_was_classic(bpf_prog), tail_call_reachable,
                        bpf_is_subprog(bpf_prog), bpf_prog->aux->exception_cb);
          /* Exception callback will clobber callee regs for its own use, and
@@ -1364,6 +1399,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                  emit_mov_imm64(&prog, X86_REG_R12,
                                 arena_vm_start >> 32, (u32) arena_vm_start);
 
+       if (enable_shadow_stack)
+               emit_percpu_shadow_frame_ptr(&prog, shadow_frame_ptr);
+
          ilen = prog - temp;
          if (rw_image)
                  memcpy(rw_image + proglen, temp, ilen);
@@ -1383,6 +1421,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
                  u8 *func;
                  int nops;
 
Quoted 8 lines

arch/x86/net/bpf_jit_comp.c static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image · line 1429

Quoted 6 lines
arch/x86/net/bpf_jit_comp.c +6 -0
+               if (enable_shadow_stack) {
+                       if (src_reg == BPF_REG_FP)
+                               src_reg = X86_REG_R9;
+
+                       if (dst_reg == BPF_REG_FP)
+                               dst_reg = X86_REG_R9;

the verifier will reject a prog that attempts to write into R10. So the above shouldn't be necessary.

Quoted 3 lines

Actually there is at least one exception, e.g.,

    if r10 > r5 goto +5

where dst is r10 and src r5.

Good point. We even have such a selftest to make sure it's rejected in unpriv.

SEC("socket")
__description("unpriv: cmp of frame pointer")
__success __failure_unpriv __msg_unpriv("R10 pointer comparison") __retval(0)
__naked void unpriv_cmp_of_frame_pointer(void)

{
         asm volatile ("                                 \
         if r10 == 0 goto l0_%=;                         \
Quoted 53 lines
Quoted 29 lines
Quoted 29 lines
arch/x86/net/bpf_jit_comp.c +8 -1
+               }
+
                  switch (insn->code) {
                          /* ALU */
                  case BPF_ALU | BPF_ADD | BPF_X:
@@ -2014,6 +2060,7 @@ st:                       if (is_imm8(insn->off))
                                  emit_mov_reg(&prog, is64, real_src_reg, BPF_REG_0);
                                  /* Restore R0 after clobbering RAX */
                                  emit_mov_reg(&prog, true, BPF_REG_0, BPF_REG_AX);
+
                                  break;
                          }
 
@@ -2038,14 +2085,20 @@ st:                     if (is_imm8(insn->off))
 
                          func = (u8 *) __bpf_call_base + imm32;
                          if (tail_call_reachable) {
-                               RESTORE_TAIL_CALL_CNT(bpf_prog->aux->stack_depth);
+                               RESTORE_TAIL_CALL_CNT(stack_depth);
                                  ip += 7;
                          }
                          if (!imm32)
                                  return -EINVAL;
+                       if (enable_shadow_stack) {
+                               EMIT2(0x41, 0x51);
+                               ip += 2;
+                       }
                          ip += x86_call_depth_emit_accounting(&prog, func, ip);
                          if (emit_call(&prog, func, ip))
Quoted 8 lines

arch/x86/net/bpf_jit_comp.c st: if (is_imm8(insn->off)) · line 2101

Quoted 3 lines
arch/x86/net/bpf_jit_comp.c +2 -0
                                  return -EINVAL;
+                       if (enable_shadow_stack)
+                               EMIT2(0x41, 0x59);

push/pop around calls are load/store plus math on %rsp. I think it's cheaper to reload r9 after the call with a single insn.
The reload of r9 is effectively gs+const. There is no memory access. So it should be faster.

Two insn may be necessary since __alloc_percpu_gfp() may return a pointer beyond 32 bits.

Quoted 13 lines

Technically we can replace all uses of R10==rbp with 'gs:' based instructions.
Like:
r1 = r10
can be jitted into
lea rdi, gs + (u32)shadow_frame_ptr

and r0 = *(u32 *)(r10 - 64)
can be jitted into:
mov rax, dword ptr gs:[(u32)shadow_frame_ptr - 64]

but that is probably a bunch of jit changes.
So I'd start with a simple reload of r9 after each call.

Quoted 8 lines
Quoted 2 lines

This is a good idea. We might need this so we only have one extra insn per call.

Since reload of r9 is a two insn sequence of 64-bit mov immediate, and load from gs:this_cpu_off, I suspect, push/pop r9 might be faster. So I'd stick to what you have already.

Interesting though that static per-cpu vars have 32-bit pointers, but dynamic per-cpu alloc returns full 64-bit? hmm.

Not always. This RFC works in my local qemu run as dynamic per-cpu allocation returns 32-bit. But CI failed since in CI 64-bit ptr val is returned. Later on, with different code based, my local qemu can also return 64-bit per-cpu ptr. In the next revision, I will use 64-bit value to hold shadow_frame_ptr (to be named private_frame_ptr).

#5 lore raw
In reply to Yonghong Song
kernel test robot noticed the following build warnings:

Hi Yonghong,

[This is a private test report for your RFC patch.] kernel test robot noticed the following build warnings:

[auto build test WARNING on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Yonghong-Song/bpf-Support-shadow-stack-for-bpf-progs/20240610-132108
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20240610051839.1296086-1-yonghong.song%40linux.dev
patch subject: [RFC PATCH bpf-next] bpf: Support shadow stack for bpf progs
config: x86_64-randconfig-123-20240614 (https://download.01.org/0day-ci/archive/20240614/[email protected]/config)
compiler: clang version 18.1.5 (https://github.com/llvm/llvm-project 617a15a9eac96088ae5e9134248d8236e34b91b1)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240614/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

sparse warnings: (new ones prefixed by >>)

>> kernel/bpf/syscall.c:2247:30: sparse: sparse: incorrect type in argument 1 (different address spaces) @@     expected void [noderef] __percpu *__pdata @@     got void *percpu_shadow_stack_ptr @@

kernel/bpf/syscall.c:2247:30: sparse: expected void [noderef] __percpu *__pdata
kernel/bpf/syscall.c:2247:30: sparse: got void *percpu_shadow_stack_ptr

vim +2247 kernel/bpf/syscall.c

2240
2241 static void __bpf_prog_put_rcu(struct rcu_head *rcu)
2242 {
2243 struct bpf_prog_aux *aux = container_of(rcu, struct bpf_prog_aux, rcu);
2244
2245 kvfree(aux->func_info);
2246 kfree(aux->func_info_aux);

> 2247		free_percpu(aux->prog->percpu_shadow_stack_ptr);

2248 free_uid(aux->user);
2249 security_bpf_prog_free(aux->prog);
2250 bpf_prog_free(aux->prog);
2251 }
2252

Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki