Classic BPF vs eBPF

Classic BPF와 eBPF의 register 구성

eBPF는 instruction을 hardware instruction에 일대일로 대응시켜 JIT compile하도록 설계됐습니다. 이 구조는 GCC/LLVM compiler가 eBPF backend를 통해 native compile code에 가까운 속도의 최적화된 eBPF code를 생성할 가능성도 열어 줍니다.

classic BPF에서 eBPF format으로 바뀐 핵심 사항은 다음과 같습니다.

• register 수가 2개에서 10개로 증가합니다.
• register 폭이 32-bit에서 64-bit로 증가합니다.
• 조건 분기의 `jt/jf` target이 `jt/fall-through`로 바뀝니다.
• zero-overhead kernel function call을 위한 `bpf_call` instruction과 register passing convention이 도입됩니다.

기존 format에는 A와 X라는 두 register와 숨겨진 frame pointer가 있었습니다. 새 layout은 이를 10개의 내부 register와 read-only frame pointer로 확장합니다. 64-bit CPU는 register로 function argument를 전달하므로 eBPF program이 in-kernel function에 전달할 수 있는 argument는 5개로 제한되고, register 하나는 in-kernel function의 return value를 받는 데 사용됩니다.

native ABI에서 x86_64는 처음 6개 argument를 register로 전달하고 aarch64/sparcv9/mips64는 argument용 register가 7~8개입니다. x86_64에는 callee-saved register가 6개, aarch64/sparcv9/mips64에는 11개 이상 있습니다.

따라서 x86_64, aarch64 등의 환경에서는 모든 eBPF register를 hardware register에 일대일로 mapping할 수 있고, eBPF calling convention도 64-bit architecture의 kernel ABI에 직접 대응합니다.

32-bit architecture의 JIT는 32-bit arithmetic만 사용하는 program을 mapping하고, 더 복잡한 program은 interpreter로 실행하게 할 수 있습니다.

`R0 - R5`는 scratch register이므로 eBPF program은 call을 사이에 두고 필요하면 이들을 spill/fill해야 합니다. eBPF program은 하나의 eBPF main routine뿐이며 다른 eBPF function을 호출할 수 없고, 미리 정의된 in-kernel function만 호출할 수 있습니다.

64-bit register와 32-bit subregister

register 폭은 32-bit에서 64-bit로 증가하지만 원래 32-bit ALU operation의 semantics는 32-bit subregister를 통해 보존됩니다. 모든 eBPF register는 64-bit이고, 아래쪽 32-bit subregister에 값을 쓰면 그 값이 64-bit로 zero-extend됩니다.

이 동작은 x86_64와 arm64의 subregister 정의에 직접 대응하지만 다른 JIT의 구현은 더 어렵게 만듭니다. 32-bit architecture는 64-bit eBPF program을 interpreter로 실행합니다. 해당 JIT는 32-bit subregister만 사용하는 BPF program을 native instruction set으로 변환하고 나머지는 interpreter에 맡길 수 있습니다.

operation이 64-bit인 이유는 64-bit architecture에서 pointer도 64-bit이고 kernel function에 64-bit value를 전달하거나 돌려받아야 하기 때문입니다. 32-bit eBPF register를 사용하면 register-pair ABI를 별도로 정의해야 하므로 eBPF register와 hardware register를 직접 mapping할 수 없습니다.

그 경우 JIT는 function에 드나드는 모든 register마다 combine/split/move operation을 수행해야 하며, 이는 복잡하고 bug가 생기기 쉬우며 느립니다. atomic 64-bit counter를 사용한다는 점도 64-bit register를 채택한 또 다른 이유입니다.

Fall-through 분기와 bpf_call 호출 규약

기존의 `if (cond) jump_true; else jump_false;` 같은 conditional `jt/jf` 구조는 `if (cond) jump_true; /* else fall-through */` 형태의 `jt/fall-through` 구조로 대체됩니다.

eBPF는 다른 kernel function과의 zero-overhead call을 위해 `bpf_call` instruction과 register passing convention을 도입합니다. in-kernel function을 호출하기 전에 eBPF program은 calling convention에 맞춰 argument를 `R1`부터 `R5`에 둡니다. interpreter는 이 값을 register에서 꺼내 in-kernel function에 전달합니다.

주어진 architecture에서 `R1 - R5`가 argument 전달용 CPU register에 mapping돼 있다면 JIT compiler는 별도 move를 생성할 필요가 없습니다. argument는 이미 올바른 register에 있고 `BPF_CALL`은 hardware의 단일 `call` instruction으로 JIT compile됩니다. 이 convention은 일반적인 호출 상황을 performance penalty 없이 처리하도록 선택됐습니다.

in-kernel function call이 끝나면 `R1 - R5`는 읽을 수 없는 상태로 reset되고 `R0`에 function return value가 들어갑니다. `R6 - R9`는 callee-saved이므로 call 전후에 상태가 보존됩니다.

C·x86_64·eBPF 호출 연결 예제

다음 세 C function을 예로 듭니다.

u64 f1() { return (*_f2)(1); }
u64 f2(u64 a) { return f3(a + 1, a); }
u64 f3(u64 a, u64 b) { return a - b; }

GCC는 `f1`과 `f3`를 다음 x86_64 code로 compile할 수 있습니다.

f1:
    movl $1, %edi
    movq _f2(%rip), %rax
    jmp  *%rax
f3:
    movq %rdi, %rax
    subq %rsi, %rax
    ret

eBPF로 작성한 `f2`는 다음과 같은 형태가 될 수 있습니다.

f2:
    bpf_mov R2, R1
    bpf_add R1, 1
    bpf_call f3
    bpf_exit

`f2`를 JIT compile하고 그 pointer를 `_f2`에 저장하면 `f1 -> f2 -> f3` call과 return이 끊김 없이 이어집니다. JIT를 사용하지 않을 때는 `__bpf_prog_run()` interpreter로 `f2`를 호출해야 합니다.

Program argument 제한과 x86_64 register mapping

실용적인 이유로 모든 eBPF program에는 `ctx`라는 argument 하나만 있습니다. `ctx`는 `__bpf_prog_run()` 시작 시점 등의 경로에서 이미 `R1`에 놓이며, program은 최대 5개 argument를 받는 kernel function을 호출할 수 있습니다. 6개 이상 argument를 받는 call은 현재 지원하지 않지만 필요하다면 향후 제한을 완화할 수 있습니다.

64-bit architecture에서는 모든 eBPF register를 hardware register에 일대일로 mapping합니다. 예를 들어 x86_64 JIT compiler는 다음처럼 mapping할 수 있습니다.

R0 - rax
R1 - rdi
R2 - rsi
R3 - rdx
R4 - rcx
R5 - r8
R6 - rbx
R7 - r13
R8 - r14
R9 - r15
R10 - rbp

x86_64 ABI는 argument 전달에 `rdi`, `rsi`, `rdx`, `rcx`, `r8`, `r9`를 사용하고 `rbx`, `r12 - r15`를 callee-saved로 규정하므로 이 mapping이 성립합니다.

eBPF pseudo-program과 x86_64 JIT 결과

다음 eBPF pseudo-program을 생각합니다.

bpf_mov R6, R1 /* save ctx */
bpf_mov R2, 2
bpf_mov R3, 3
bpf_mov R4, 4
bpf_mov R5, 5
bpf_call foo
bpf_mov R7, R0 /* save foo() return value */
bpf_mov R1, R6 /* restore ctx for next call */
bpf_mov R2, 6
bpf_mov R3, 7
bpf_mov R4, 8
bpf_mov R5, 9
bpf_call bar
bpf_add R0, R7
bpf_exit

이를 x86_64로 JIT compile한 결과는 다음과 같은 형태가 될 수 있습니다.

push %rbp
mov %rsp,%rbp
sub $0x228,%rsp
mov %rbx,-0x228(%rbp)
mov %r13,-0x220(%rbp)
mov %rdi,%rbx
mov $0x2,%esi
mov $0x3,%edx
mov $0x4,%ecx
mov $0x5,%r8d
callq foo
mov %rax,%r13
mov %rbx,%rdi
mov $0x6,%esi
mov $0x7,%edx
mov $0x8,%ecx
mov $0x9,%r8d
callq bar
add %r13,%rax
mov -0x228(%rbp),%rbx
mov -0x220(%rbp),%r13
leaveq
retq

이 예제는 C로 표현하면 다음과 같습니다.

u64 bpf_filter(u64 ctx)
{
    return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
}

`u64 (*)(u64 arg1, u64 arg2, u64 arg3, u64 arg4, u64 arg5)` prototype을 가진 in-kernel function `foo()`와 `bar()`는 올바른 register에서 argument를 받고, return value를 eBPF의 `R0`에 해당하는 `%rax`에 둡니다.

prologue와 epilogue는 JIT가 생성하며 interpreter에서는 암시적으로 처리됩니다. `R0-R5`는 scratch register이므로 eBPF program은 calling convention에 정의된 대로 call 사이에서 필요한 값을 보존해야 합니다.

Call 이후 register 상태와 program context

예를 들어 다음 program은 유효하지 않습니다.

bpf_mov R1, 1
bpf_call foo
bpf_mov R0, R1
bpf_exit

call 이후 `R1-R5`에는 의미 없는 값이 들어 있으므로 읽을 수 없습니다. in-kernel `verifier.rst`가 eBPF program을 검증합니다.

새 설계에서 eBPF program은 4096 insns로 제한됩니다. 따라서 모든 program은 빠르게 종료하며 고정된 횟수만큼만 kernel function을 호출합니다. Original BPF와 eBPF는 모두 two-operand instruction이므로 JIT 과정에서 eBPF instruction과 x86 instruction을 일대일로 mapping하기 쉽습니다.

interpreter function을 호출할 때 전달하는 input context pointer는 generic pointer이며 내용은 use case에 따라 정해집니다. seccomp에서는 `R1`이 `seccomp_data`를 가리키고, 변환된 BPF filter에서는 `R1`이 `skb`를 가리킵니다.

Instruction format과 일반 목적 RISC 특성

내부에서 변환되는 program element의 format은 다음과 같습니다.

op:16, jt:8, jf:8, k:32    ==>    op:8, dst_reg:4, src_reg:4, off:16, imm:32

현재까지 eBPF instruction은 87개가 구현됐습니다. 8-bit `op` opcode field에는 새 instruction을 추가할 여유가 있습니다. 일부 새 instruction은 16/24/32-byte encoding을 사용할 수 있지만 backward compatibility를 보존하려면 길이가 8 bytes의 배수여야 합니다.

eBPF는 general-purpose RISC instruction set입니다. original BPF에서 eBPF로 변환할 때 모든 register와 instruction을 사용하는 것은 아닙니다. 예를 들어 socket filter는 event counter를 유지하는 tracing filter와 달리 `exclusive add` instruction을 사용하지 않습니다.

socket filter는 `R9`도 사용하지 않지만 더 복잡한 filter는 register가 부족해 stack으로 spill/fill해야 할 수 있습니다.

eBPF는 마지막 단계의 performance optimization을 위한 generic assembler로 사용할 수 있습니다. socket filter와 seccomp는 eBPF를 assembler로 사용하고, tracing filter는 kernel에서 code를 생성하는 assembler로 사용할 수 있습니다.

kernel 내부에서 생성한 eBPF code가 userspace에 노출되지 않고 내부 code path를 최적화한다면 security consideration으로 제한할 필요가 없을 수 있습니다. eBPF의 safety는 `verifier.rst`에서 얻을 수 있으며, 이런 use case에서는 safe instruction set으로 활용할 수 있습니다.

Controlled execution과 verifier의 두 단계 검증

original BPF와 마찬가지로 eBPF는 controlled environment에서 deterministic하게 실행되므로 kernel이 그 특성을 쉽게 증명할 수 있습니다.

program safety는 두 단계로 판정합니다. 첫 단계는 depth-first-search를 수행해 loop를 금지하고 기타 CFG validation을 수행합니다. 두 번째 단계는 첫 instruction에서 시작해 가능한 모든 path를 내려가며 각 instruction의 실행을 simulate하고 register와 stack의 상태 변화를 관찰합니다.

Arithmetic·jump opcode encoding

eBPF는 classic BPF에서 eBPF로 쉽게 변환할 수 있도록 classic opcode encoding의 대부분을 재사용합니다.

arithmetic와 jump instruction의 8-bit `code` field는 operation code 4 bits, source 1 bit, instruction class 3 bits로 나뉩니다.

Classic BPF와 eBPF instruction class

하위 3 bits에는 다음 instruction class 중 하나를 저장합니다.

Source operand bit

4번째 bit는 source operand를 다음처럼 encode합니다.

BPF_K     0x00
BPF_X     0x08

classic BPF에서 의미는 다음과 같습니다.

BPF_SRC(code) == BPF_X - use register X as source operand
BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand

eBPF에서 의미는 다음과 같습니다.

BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand
BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand

상위 4 bits에는 operation code를 저장합니다.

BPF_ALU와 BPF_ALU64 operation code

`BPF_CLASS(code) == BPF_ALU`이거나 eBPF에서 `BPF_ALU64`이면 `BPF_OP(code)`는 다음 중 하나입니다.

BPF_JMP와 BPF_JMP32 operation code

`BPF_CLASS(code) == BPF_JMP`이거나 eBPF에서 `BPF_JMP32`이면 `BPF_OP(code)`는 다음 중 하나입니다.

32-bit·64-bit ALU와 return semantics

`BPF_ADD | BPF_X | BPF_ALU`는 classic BPF와 eBPF 모두에서 32-bit addition을 뜻합니다. register가 A와 X 둘뿐인 classic BPF에서는 `A += X`이고, eBPF에서는 `dst_reg = (u32) dst_reg + (u32) src_reg`입니다.

마찬가지로 `BPF_XOR | BPF_K | BPF_ALU`는 classic BPF에서 `A ^= imm32`이고 eBPF에서는 이에 대응하는 `src_reg = (u32) src_reg ^ (u32) imm32`입니다.

classic BPF는 `A = X`와 `X = A` move를 표현하는 데 `BPF_MISC` class를 사용합니다. eBPF는 대신 `BPF_MOV | BPF_X | BPF_ALU` code를 사용합니다.

eBPF에는 `BPF_MISC` operation이 없으므로 class 7을 `BPF_ALU64`로 사용합니다. operation 자체는 `BPF_ALU`와 같지만 operand 폭이 64-bit입니다. 따라서 `BPF_ADD | BPF_X | BPF_ALU64`는 64-bit addition, 즉 `dst_reg = dst_reg + src_reg`를 뜻합니다.

classic BPF는 단일 `ret` operation을 표현하기 위해 `BPF_RET` class 전체를 사용합니다. classic `BPF_RET | BPF_K`는 `imm32`를 return register에 복사하고 function을 종료합니다.

eBPF는 CPU 동작에 맞춰 설계됐으므로 `BPF_JMP | BPF_EXIT`는 function exit만 의미합니다. eBPF program은 `BPF_EXIT` 전에 return value를 `R0`에 저장해야 합니다. eBPF의 class 6은 `BPF_JMP32`이며, `BPF_JMP`와 같은 비교 operation을 32-bit operand 폭으로 수행합니다.

Load/store code의 mode와 size encoding

load와 store instruction의 8-bit `code` field는 mode 3 bits, size 2 bits, instruction class 3 bits로 나뉩니다.

size modifier는 다음 중 하나입니다.

각 modifier가 encode하는 load/store operation size는 다음과 같습니다.

mode modifier는 다음 중 하나입니다.