BPF: Indirect Jumps
Anton Propototov
Contents
● BPF Static Keys (in a Nutshell)
● Instruction Set Maps
● Indirect Branches in BPF
BPF Static Keys
BPF Static Keys: branch is unlikely, key is off
BPF Static Keys: branch is unlikely, key is off
Static Keys vs. Relocations
call 0x76
goto +0
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
call 0x76
goto +38
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
Key off
Key on
Static Keys vs. Relocations
call 0x76
goto +0
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
call 0x76
goto +38
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
Key off
Key on
Static Keys vs. Relocations
call 0x76
…
…
18000000beef1011
00000000ffffffff
r0 = *(u64 *)r0
bpf_patch_insn_data()
call 0x76
goto +0
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
call 0x76
goto +38
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
Key off
Key on
ldimm64
goto +0
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-44
r2 = 42
…
…
goto +38
r0 = 0
exit
…
…
Key off
Key on
Imm >> 32
r0 = *r0
ldimm64
r1 = map
call 0x6
goto pc-42
r2 = 42
…
Imm >> 32
r0 = *r0
Load, verify, relocate
This jump becomes
invalid, we need to
relocate it the same way
the normal jumps are
relocated
A new BPF map: Instruction Set
r0 = 17
goto +0
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
BPF Program
1
42
INSN_SET map
33
INSN_SET map
Load, verify, relocate
r0 = 17
goto +0
r0 = 0
exit
r1 = map
…
call 0x6
goto pc-42
r2 = 42
…
…
BPF Program
3
47
INSN_SET map
35
INSN_SET map
…
…
…
…
…
…
Instruction Set Map Properties
Before program load
● A map is populated with instructions offsets
On program load:
● The map becomes read-only to userspace
(it’s always read-only on the BPF side)
● Every instruction in this map is properly relocated
Why new map: Instruction Set
● Jump offsets can be stored in 16-byte jumps (we’re adding new
instructions in any case)
● However, this is more useful to have an object which groups to
simplify static keys API
● What is even more important is that instruction sets can also be
used for other purposes, e.g., to implement Indirect Branches
Indirect Jumps
● The goal is to add a new instruction (or multiple)
goto Rx
goto *Rx
(or so, see later)
Indirect Jumps: possible with Instruction Set Maps
…
goto Rx
…
insn j
…
j
i
j
Program P
Map M
…
…insn i
…
i
k …
…
insn k
…
k
A `goto rx` instruction must point to an instruction set map. Then
during verification we can check that 1) Every jump from `goto rX`
is valid 2) Rx is actually loaded from M
Indirect Jumps: new instructions
This looks reasonable to add the following instructions:
● BPF_JMP|BPF_JA|BPF_X, src=index, dst=0, imm=map
○ Translated by the verifier to the second form
● BPF_JMP|BPF_JA|BPF_X, src=map_value, dst=1, imm=map
○ Jitted to, e.g., `jmpq *(%rsi)`
● BPF_JMP|BPF_JA|BPF_X, src=ip, dst=2, imm=map
○ Jitted to, e.g., `jmpq *%rsi`
○ (This one looks like an optional + requires more verification)
Indirect Jumps: check_cfg & visit_insn
F
Vertex state:
● Old orthodox state
● + A new Counter inside insn_state
1
2
3
…
…
…
i
j
Map M
…
…
k …
Entering goto rx instruction:
Pushing the next insns to stack:
Indirect Jumps: Verification (do_check)
* Only DST=0 version of instruction is supported ATM. For DST=1 it must be checked
that src_reg was loaded from the map
Indirect Jumps: prepare to JIT: DST=0 -> DST=1
Indirect Jumps: prepare to JIT: DST=0 -> DST=1
Indirect Jumps: JIT
● The only change to [x86] Jit is to add the following case
Code example 1
Code example 1
0: r1 = 0
1: goto r1
2: r0 = 2
3: exit
Create an instruction set map
of size 1 with one value: M={2}
Put the map file descriptor
inside the instruction. Now
program is ready to load.
Code example 1
Code example 2
C jump tables
C jump tables
C jump tables
C jump tables
JMP|JA|X, .src=r1, .imm=map(x)
libbpf
llvm optimizer
C Switches
● All the switches are now replaced with if-else-...
● Larger switches can benefit from using an indirect jump
● Yonghong said:
○ First support for jump tables
○ Then support for switches
Next Steps
● Start pushing the patch set: insn set map, then static keys
● Indirect branches:
1. LLVM code generation + libbpf support (jump_tables)
2. Refactor the kernel side accordingly
3. may_goto 1
● C Switches => indirect jumps
Questions?
