1 .. SPDX-License-Identifier: GPL-2.0
5 =======================================================
6 Linux Socket Filtering aka Berkeley Packet Filter (BPF)
7 =======================================================
12 Linux Socket Filtering (LSF) is derived from the Berkeley Packet Filter.
13 Though there are some distinct differences between the BSD and Linux
14 Kernel filtering, but when we speak of BPF or LSF in Linux context, we
15 mean the very same mechanism of filtering in the Linux kernel.
17 BPF allows a user-space program to attach a filter onto any socket and
18 allow or disallow certain types of data to come through the socket. LSF
19 follows exactly the same filter code structure as BSD's BPF, so referring
20 to the BSD bpf.4 manpage is very helpful in creating filters.
22 On Linux, BPF is much simpler than on BSD. One does not have to worry
23 about devices or anything like that. You simply create your filter code,
24 send it to the kernel via the SO_ATTACH_FILTER option and if your filter
25 code passes the kernel check on it, you then immediately begin filtering
28 You can also detach filters from your socket via the SO_DETACH_FILTER
29 option. This will probably not be used much since when you close a socket
30 that has a filter on it the filter is automagically removed. The other
31 less common case may be adding a different filter on the same socket where
32 you had another filter that is still running: the kernel takes care of
33 removing the old one and placing your new one in its place, assuming your
34 filter has passed the checks, otherwise if it fails the old filter will
35 remain on that socket.
37 SO_LOCK_FILTER option allows to lock the filter attached to a socket. Once
38 set, a filter cannot be removed or changed. This allows one process to
39 setup a socket, attach a filter, lock it then drop privileges and be
40 assured that the filter will be kept until the socket is closed.
42 The biggest user of this construct might be libpcap. Issuing a high-level
43 filter command like `tcpdump -i em1 port 22` passes through the libpcap
44 internal compiler that generates a structure that can eventually be loaded
45 via SO_ATTACH_FILTER to the kernel. `tcpdump -i em1 port 22 -ddd`
46 displays what is being placed into this structure.
48 Although we were only speaking about sockets here, BPF in Linux is used
49 in many more places. There's xt_bpf for netfilter, cls_bpf in the kernel
50 qdisc layer, SECCOMP-BPF (SECure COMPuting [1]_), and lots of other places
51 such as team driver, PTP code, etc where BPF is being used.
53 .. [1] Documentation/userspace-api/seccomp_filter.rst
57 Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
58 architecture for user-level packet capture. In Proceedings of the
59 USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
60 Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
61 CA, USA, 2-2. [http://www.tcpdump.org/papers/bpf-usenix93.pdf]
66 User space applications include <linux/filter.h> which contains the
67 following relevant structures::
69 struct sock_filter { /* Filter block */
70 __u16 code; /* Actual filter code */
71 __u8 jt; /* Jump true */
72 __u8 jf; /* Jump false */
73 __u32 k; /* Generic multiuse field */
76 Such a structure is assembled as an array of 4-tuples, that contains
77 a code, jt, jf and k value. jt and jf are jump offsets and k a generic
78 value to be used for a provided code::
80 struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
81 unsigned short len; /* Number of filter blocks */
82 struct sock_filter __user *filter;
85 For socket filtering, a pointer to this structure (as shown in
86 follow-up example) is being passed to the kernel through setsockopt(2).
93 #include <sys/socket.h>
94 #include <sys/types.h>
95 #include <arpa/inet.h>
96 #include <linux/if_ether.h>
99 /* From the example above: tcpdump -i em1 port 22 -dd */
100 struct sock_filter code[] = {
101 { 0x28, 0, 0, 0x0000000c },
102 { 0x15, 0, 8, 0x000086dd },
103 { 0x30, 0, 0, 0x00000014 },
104 { 0x15, 2, 0, 0x00000084 },
105 { 0x15, 1, 0, 0x00000006 },
106 { 0x15, 0, 17, 0x00000011 },
107 { 0x28, 0, 0, 0x00000036 },
108 { 0x15, 14, 0, 0x00000016 },
109 { 0x28, 0, 0, 0x00000038 },
110 { 0x15, 12, 13, 0x00000016 },
111 { 0x15, 0, 12, 0x00000800 },
112 { 0x30, 0, 0, 0x00000017 },
113 { 0x15, 2, 0, 0x00000084 },
114 { 0x15, 1, 0, 0x00000006 },
115 { 0x15, 0, 8, 0x00000011 },
116 { 0x28, 0, 0, 0x00000014 },
117 { 0x45, 6, 0, 0x00001fff },
118 { 0xb1, 0, 0, 0x0000000e },
119 { 0x48, 0, 0, 0x0000000e },
120 { 0x15, 2, 0, 0x00000016 },
121 { 0x48, 0, 0, 0x00000010 },
122 { 0x15, 0, 1, 0x00000016 },
123 { 0x06, 0, 0, 0x0000ffff },
124 { 0x06, 0, 0, 0x00000000 },
127 struct sock_fprog bpf = {
128 .len = ARRAY_SIZE(code),
132 sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
134 /* ... bail out ... */
136 ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));
138 /* ... bail out ... */
143 The above example code attaches a socket filter for a PF_PACKET socket
144 in order to let all IPv4/IPv6 packets with port 22 pass. The rest will
145 be dropped for this socket.
147 The setsockopt(2) call to SO_DETACH_FILTER doesn't need any arguments
148 and SO_LOCK_FILTER for preventing the filter to be detached, takes an
149 integer value with 0 or 1.
151 Note that socket filters are not restricted to PF_PACKET sockets only,
152 but can also be used on other socket families.
154 Summary of system calls:
156 * setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &val, sizeof(val));
157 * setsockopt(sockfd, SOL_SOCKET, SO_DETACH_FILTER, &val, sizeof(val));
158 * setsockopt(sockfd, SOL_SOCKET, SO_LOCK_FILTER, &val, sizeof(val));
160 Normally, most use cases for socket filtering on packet sockets will be
161 covered by libpcap in high-level syntax, so as an application developer
162 you should stick to that. libpcap wraps its own layer around all that.
164 Unless i) using/linking to libpcap is not an option, ii) the required BPF
165 filters use Linux extensions that are not supported by libpcap's compiler,
166 iii) a filter might be more complex and not cleanly implementable with
167 libpcap's compiler, or iv) particular filter codes should be optimized
168 differently than libpcap's internal compiler does; then in such cases
169 writing such a filter "by hand" can be of an alternative. For example,
170 xt_bpf and cls_bpf users might have requirements that could result in
171 more complex filter code, or one that cannot be expressed with libpcap
172 (e.g. different return codes for various code paths). Moreover, BPF JIT
173 implementors may wish to manually write test cases and thus need low-level
174 access to BPF code as well.
176 BPF engine and instruction set
177 ------------------------------
179 Under tools/bpf/ there's a small helper tool called bpf_asm which can
180 be used to write low-level filters for example scenarios mentioned in the
181 previous section. Asm-like syntax mentioned here has been implemented in
182 bpf_asm and will be used for further explanations (instead of dealing with
183 less readable opcodes directly, principles are the same). The syntax is
184 closely modelled after Steven McCanne's and Van Jacobson's BPF paper.
186 The BPF architecture consists of the following basic elements:
188 ======= ====================================================
190 ======= ====================================================
191 A 32 bit wide accumulator
192 X 32 bit wide X register
193 M[] 16 x 32 bit wide misc registers aka "scratch memory
194 store", addressable from 0 to 15
195 ======= ====================================================
197 A program, that is translated by bpf_asm into "opcodes" is an array that
198 consists of the following elements (as already mentioned)::
200 op:16, jt:8, jf:8, k:32
202 The element op is a 16 bit wide opcode that has a particular instruction
203 encoded. jt and jf are two 8 bit wide jump targets, one for condition
204 "jump if true", the other one "jump if false". Eventually, element k
205 contains a miscellaneous argument that can be interpreted in different
206 ways depending on the given instruction in op.
208 The instruction set consists of load, store, branch, alu, miscellaneous
209 and return instructions that are also represented in bpf_asm syntax. This
210 table lists all bpf_asm instructions available resp. what their underlying
211 opcodes as defined in linux/filter.h stand for:
213 =========== =================== =====================
214 Instruction Addressing mode Description
215 =========== =================== =====================
216 ld 1, 2, 3, 4, 12 Load word into A
217 ldi 4 Load word into A
218 ldh 1, 2 Load half-word into A
219 ldb 1, 2 Load byte into A
220 ldx 3, 4, 5, 12 Load word into X
221 ldxi 4 Load word into X
222 ldxb 5 Load byte into X
224 st 3 Store A into M[]
225 stx 3 Store X into M[]
229 jeq 7, 8, 9, 10 Jump on A == <x>
230 jneq 9, 10 Jump on A != <x>
231 jne 9, 10 Jump on A != <x>
232 jlt 9, 10 Jump on A < <x>
233 jle 9, 10 Jump on A <= <x>
234 jgt 7, 8, 9, 10 Jump on A > <x>
235 jge 7, 8, 9, 10 Jump on A >= <x>
236 jset 7, 8, 9, 10 Jump on A & <x>
254 =========== =================== =====================
256 The next table shows addressing formats from the 2nd column:
258 =============== =================== ===============================================
259 Addressing mode Syntax Description
260 =============== =================== ===============================================
262 1 [k] BHW at byte offset k in the packet
263 2 [x + k] BHW at the offset X + k in the packet
264 3 M[k] Word at offset k in M[]
265 4 #k Literal value stored in k
266 5 4*([k]&0xf) Lower nibble * 4 at byte offset k in the packet
268 7 #k,Lt,Lf Jump to Lt if true, otherwise jump to Lf
269 8 x/%x,Lt,Lf Jump to Lt if true, otherwise jump to Lf
270 9 #k,Lt Jump to Lt if predicate is true
271 10 x/%x,Lt Jump to Lt if predicate is true
272 11 a/%a Accumulator A
273 12 extension BPF extension
274 =============== =================== ===============================================
276 The Linux kernel also has a couple of BPF extensions that are used along
277 with the class of load instructions by "overloading" the k argument with
278 a negative offset + a particular extension offset. The result of such BPF
279 extensions are loaded into A.
281 Possible BPF extensions are shown in the following table:
283 =================================== =================================================
284 Extension Description
285 =================================== =================================================
289 poff Payload start offset
290 ifidx skb->dev->ifindex
291 nla Netlink attribute of type X with offset A
292 nlan Nested Netlink attribute of type X with offset A
294 queue skb->queue_mapping
295 hatype skb->dev->type
297 cpu raw_smp_processor_id()
298 vlan_tci skb_vlan_tag_get(skb)
299 vlan_avail skb_vlan_tag_present(skb)
300 vlan_tpid skb->vlan_proto
302 =================================== =================================================
304 These extensions can also be prefixed with '#'.
305 Examples for low-level BPF:
314 **IPv4 TCP packets**::
323 **(Accelerated) VLAN w/ id 10**::
330 **icmp random packet sampling, 1 in 4**::
336 # get a random uint32 number
343 **SECCOMP filter example**::
345 ld [4] /* offsetof(struct seccomp_data, arch) */
346 jne #0xc000003e, bad /* AUDIT_ARCH_X86_64 */
347 ld [0] /* offsetof(struct seccomp_data, nr) */
348 jeq #15, good /* __NR_rt_sigreturn */
349 jeq #231, good /* __NR_exit_group */
350 jeq #60, good /* __NR_exit */
351 jeq #0, good /* __NR_read */
352 jeq #1, good /* __NR_write */
353 jeq #5, good /* __NR_fstat */
354 jeq #9, good /* __NR_mmap */
355 jeq #14, good /* __NR_rt_sigprocmask */
356 jeq #13, good /* __NR_rt_sigaction */
357 jeq #35, good /* __NR_nanosleep */
358 bad: ret #0 /* SECCOMP_RET_KILL_THREAD */
359 good: ret #0x7fff0000 /* SECCOMP_RET_ALLOW */
361 The above example code can be placed into a file (here called "foo"), and
362 then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf
363 and cls_bpf understands and can directly be loaded with. Example with above
367 4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,
369 In copy and paste C-like output::
372 { 0x28, 0, 0, 0x0000000c },
373 { 0x15, 0, 1, 0x00000806 },
374 { 0x06, 0, 0, 0xffffffff },
375 { 0x06, 0, 0, 0000000000 },
377 In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF
378 filters that might not be obvious at first, it's good to test filters before
379 attaching to a live system. For that purpose, there's a small tool called
380 bpf_dbg under tools/bpf/ in the kernel source directory. This debugger allows
381 for testing BPF filters against given pcap files, single stepping through the
382 BPF code on the pcap's packets and to do BPF machine register dumps.
384 Starting bpf_dbg is trivial and just requires issuing::
388 In case input and output do not equal stdin/stdout, bpf_dbg takes an
389 alternative stdin source as a first argument, and an alternative stdout
390 sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`.
392 Other than that, a particular libreadline configuration can be set via
393 file "~/.bpf_dbg_init" and the command history is stored in the file
394 "~/.bpf_dbg_history".
396 Interaction in bpf_dbg happens through a shell that also has auto-completion
397 support (follow-up example commands starting with '>' denote bpf_dbg shell).
398 The usual workflow would be to ...
400 * load bpf 6,40 0 0 12,21 0 3 2048,48 0 0 23,21 0 1 1,6 0 0 65535,6 0 0 0
401 Loads a BPF filter from standard output of bpf_asm, or transformed via
402 e.g. ``tcpdump -iem1 -ddd port 22 | tr '\n' ','``. Note that for JIT
403 debugging (next section), this command creates a temporary socket and
404 loads the BPF code into the kernel. Thus, this will also be useful for
409 Loads standard tcpdump pcap file.
414 Runs through all packets from a pcap to account how many passes and fails
415 the filter will generate. A limit of packets to traverse can be given.
420 l1: jeq #0x800, l2, l5
426 Prints out BPF code disassembly.
430 /* { op, jt, jf, k }, */
431 { 0x28, 0, 0, 0x0000000c },
432 { 0x15, 0, 3, 0x00000800 },
433 { 0x30, 0, 0, 0x00000017 },
434 { 0x15, 0, 1, 0x00000001 },
435 { 0x06, 0, 0, 0x0000ffff },
436 { 0x06, 0, 0, 0000000000 },
438 Prints out C-style BPF code dump.
442 breakpoint at: l0: ldh [12]
446 breakpoint at: l1: jeq #0x800, l2, l5
450 Sets breakpoints at particular BPF instructions. Issuing a `run` command
451 will walk through the pcap file continuing from the current packet and
452 break when a breakpoint is being hit (another `run` will continue from
453 the currently active breakpoint executing next instructions):
458 pc: [0] <-- program counter
459 code: [40] jt[0] jf[0] k[12] <-- plain BPF code of current instruction
460 curr: l0: ldh [12] <-- disassembly of current instruction
461 A: [00000000][0] <-- content of A (hex, decimal)
462 X: [00000000][0] <-- content of X (hex, decimal)
463 M[0,15]: [00000000][0] <-- folded content of M (hex, decimal)
464 -- packet dump -- <-- Current packet from pcap (hex)
466 0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
467 16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
468 32: 00 00 00 00 00 00 0a 3b 01 01
476 Prints currently set breakpoints.
480 Performs single stepping through the BPF program from the current pc
481 offset. Thus, on each step invocation, above register dump is issued.
482 This can go forwards and backwards in time, a plain `step` will break
483 on the next BPF instruction, thus +1. (No `run` needs to be issued here.)
487 Selects a given packet from the pcap file to continue from. Thus, on
488 the next `run` or `step`, the BPF program is being evaluated against
489 the user pre-selected packet. Numbering starts just as in Wireshark
499 The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC,
500 PowerPC, ARM, ARM64, MIPS, RISC-V and s390 and can be enabled through
501 CONFIG_BPF_JIT. The JIT compiler is transparently invoked for each
502 attached filter from user space or for internal kernel users if it has
503 been previously enabled by root::
505 echo 1 > /proc/sys/net/core/bpf_jit_enable
507 For JIT developers, doing audits etc, each compile run can output the generated
508 opcode image into the kernel log via::
510 echo 2 > /proc/sys/net/core/bpf_jit_enable
512 Example output from dmesg::
514 [ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
515 [ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
516 [ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
517 [ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
518 [ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
519 [ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3
521 When CONFIG_BPF_JIT_ALWAYS_ON is enabled, bpf_jit_enable is permanently set to 1 and
522 setting any other value than that will return in failure. This is even the case for
523 setting bpf_jit_enable to 2, since dumping the final JIT image into the kernel log
524 is discouraged and introspection through bpftool (under tools/bpf/bpftool/) is the
525 generally recommended approach instead.
527 In the kernel source tree under tools/bpf/, there's bpf_jit_disasm for
528 generating disassembly out of the kernel log's hexdump::
531 70 bytes emitted from JIT compiler (pass:3, flen:6)
532 ffffffffa0069c8f + <x>:
536 8: mov %rbx,-0x8(%rbp)
537 c: mov 0x68(%rdi),%r9d
538 10: sub 0x6c(%rdi),%r9d
539 14: mov 0xd8(%rdi),%r8
541 20: callq 0xffffffffe0ff9442
543 2a: jne 0x0000000000000042
545 31: callq 0xffffffffe0ff945e
547 39: jne 0x0000000000000042
549 40: jmp 0x0000000000000044
554 Issuing option `-o` will "annotate" opcodes to resulting assembler
555 instructions, which can be very useful for JIT developers:
557 # ./bpf_jit_disasm -o
558 70 bytes emitted from JIT compiler (pass:3, flen:6)
559 ffffffffa0069c8f + <x>:
566 8: mov %rbx,-0x8(%rbp)
568 c: mov 0x68(%rdi),%r9d
570 10: sub 0x6c(%rdi),%r9d
572 14: mov 0xd8(%rdi),%r8
576 20: callq 0xffffffffe0ff9442
580 2a: jne 0x0000000000000042
584 31: callq 0xffffffffe0ff945e
588 39: jne 0x0000000000000042
592 40: jmp 0x0000000000000044
601 For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful
602 toolchain for developing and testing the kernel's JIT compiler.
606 Internally, for the kernel interpreter, a different instruction set
607 format with similar underlying principles from BPF described in previous
608 paragraphs is being used. However, the instruction set format is modelled
609 closer to the underlying architecture to mimic native instruction sets, so
610 that a better performance can be achieved (more details later). This new
611 ISA is called 'eBPF' or 'internal BPF' interchangeably. (Note: eBPF which
612 originates from [e]xtended BPF is not the same as BPF extensions! While
613 eBPF is an ISA, BPF extensions date back to classic BPF's 'overloading'
614 of BPF_LD | BPF_{B,H,W} | BPF_ABS instruction.)
616 It is designed to be JITed with one to one mapping, which can also open up
617 the possibility for GCC/LLVM compilers to generate optimized eBPF code through
618 an eBPF backend that performs almost as fast as natively compiled code.
620 The new instruction set was originally designed with the possible goal in
621 mind to write programs in "restricted C" and compile into eBPF with a optional
622 GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with
623 minimal performance overhead over two steps, that is, C -> eBPF -> native code.
625 Currently, the new format is being used for running user BPF programs, which
626 includes seccomp BPF, classic socket filters, cls_bpf traffic classifier,
627 team driver's classifier for its load-balancing mode, netfilter's xt_bpf
628 extension, PTP dissector/classifier, and much more. They are all internally
629 converted by the kernel into the new instruction set representation and run
630 in the eBPF interpreter. For in-kernel handlers, this all works transparently
631 by using bpf_prog_create() for setting up the filter, resp.
632 bpf_prog_destroy() for destroying it. The macro
633 BPF_PROG_RUN(filter, ctx) transparently invokes eBPF interpreter or JITed
634 code to run the filter. 'filter' is a pointer to struct bpf_prog that we
635 got from bpf_prog_create(), and 'ctx' the given context (e.g.
636 skb pointer). All constraints and restrictions from bpf_check_classic() apply
637 before a conversion to the new layout is being done behind the scenes!
639 Currently, the classic BPF format is being used for JITing on most
640 32-bit architectures, whereas x86-64, aarch64, s390x, powerpc64,
641 sparc64, arm32, riscv64, riscv32 perform JIT compilation from eBPF
644 Some core changes of the new internal format:
646 - Number of registers increase from 2 to 10:
648 The old format had two registers A and X, and a hidden frame pointer. The
649 new layout extends this to be 10 internal registers and a read-only frame
650 pointer. Since 64-bit CPUs are passing arguments to functions via registers
651 the number of args from eBPF program to in-kernel function is restricted
652 to 5 and one register is used to accept return value from an in-kernel
653 function. Natively, x86_64 passes first 6 arguments in registers, aarch64/
654 sparcv9/mips64 have 7 - 8 registers for arguments; x86_64 has 6 callee saved
655 registers, and aarch64/sparcv9/mips64 have 11 or more callee saved registers.
657 Therefore, eBPF calling convention is defined as:
659 * R0 - return value from in-kernel function, and exit value for eBPF program
660 * R1 - R5 - arguments from eBPF program to in-kernel function
661 * R6 - R9 - callee saved registers that in-kernel function will preserve
662 * R10 - read-only frame pointer to access stack
664 Thus, all eBPF registers map one to one to HW registers on x86_64, aarch64,
665 etc, and eBPF calling convention maps directly to ABIs used by the kernel on
666 64-bit architectures.
668 On 32-bit architectures JIT may map programs that use only 32-bit arithmetic
669 and may let more complex programs to be interpreted.
671 R0 - R5 are scratch registers and eBPF program needs spill/fill them if
672 necessary across calls. Note that there is only one eBPF program (== one
673 eBPF main routine) and it cannot call other eBPF functions, it can only
674 call predefined in-kernel functions, though.
676 - Register width increases from 32-bit to 64-bit:
678 Still, the semantics of the original 32-bit ALU operations are preserved
679 via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower
680 subregisters that zero-extend into 64-bit if they are being written to.
681 That behavior maps directly to x86_64 and arm64 subregister definition, but
682 makes other JITs more difficult.
684 32-bit architectures run 64-bit internal BPF programs via interpreter.
685 Their JITs may convert BPF programs that only use 32-bit subregisters into
686 native instruction set and let the rest being interpreted.
688 Operation is 64-bit, because on 64-bit architectures, pointers are also
689 64-bit wide, and we want to pass 64-bit values in/out of kernel functions,
690 so 32-bit eBPF registers would otherwise require to define register-pair
691 ABI, thus, there won't be able to use a direct eBPF register to HW register
692 mapping and JIT would need to do combine/split/move operations for every
693 register in and out of the function, which is complex, bug prone and slow.
694 Another reason is the use of atomic 64-bit counters.
696 - Conditional jt/jf targets replaced with jt/fall-through:
698 While the original design has constructs such as ``if (cond) jump_true;
699 else jump_false;``, they are being replaced into alternative constructs like
700 ``if (cond) jump_true; /* else fall-through */``.
702 - Introduces bpf_call insn and register passing convention for zero overhead
703 calls from/to other kernel functions:
705 Before an in-kernel function call, the internal BPF program needs to
706 place function arguments into R1 to R5 registers to satisfy calling
707 convention, then the interpreter will take them from registers and pass
708 to in-kernel function. If R1 - R5 registers are mapped to CPU registers
709 that are used for argument passing on given architecture, the JIT compiler
710 doesn't need to emit extra moves. Function arguments will be in the correct
711 registers and BPF_CALL instruction will be JITed as single 'call' HW
712 instruction. This calling convention was picked to cover common call
713 situations without performance penalty.
715 After an in-kernel function call, R1 - R5 are reset to unreadable and R0 has
716 a return value of the function. Since R6 - R9 are callee saved, their state
717 is preserved across the call.
719 For example, consider three C functions::
721 u64 f1() { return (*_f2)(1); }
722 u64 f2(u64 a) { return f3(a + 1, a); }
723 u64 f3(u64 a, u64 b) { return a - b; }
725 GCC can compile f1, f3 into x86_64::
736 Function f2 in eBPF may look like::
744 If f2 is JITed and the pointer stored to ``_f2``. The calls f1 -> f2 -> f3 and
745 returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to
746 be used to call into f2.
748 For practical reasons all eBPF programs have only one argument 'ctx' which is
749 already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs
750 can call kernel functions with up to 5 arguments. Calls with 6 or more arguments
751 are currently not supported, but these restrictions can be lifted if necessary
754 On 64-bit architectures all register map to HW registers one to one. For
755 example, x86_64 JIT compiler can map them as ...
771 ... since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing
772 and rbx, r12 - r15 are callee saved.
774 Then the following internal BPF pseudo-program::
776 bpf_mov R6, R1 /* save ctx */
782 bpf_mov R7, R0 /* save foo() return value */
783 bpf_mov R1, R6 /* restore ctx for next call */
792 After JIT to x86_64 may look like::
797 mov %rbx,-0x228(%rbp)
798 mov %r13,-0x220(%rbp)
813 mov -0x228(%rbp),%rbx
814 mov -0x220(%rbp),%r13
818 Which is in this example equivalent in C to::
820 u64 bpf_filter(u64 ctx)
822 return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
825 In-kernel functions foo() and bar() with prototype: u64 (*)(u64 arg1, u64
826 arg2, u64 arg3, u64 arg4, u64 arg5); will receive arguments in proper
827 registers and place their return value into ``%rax`` which is R0 in eBPF.
828 Prologue and epilogue are emitted by JIT and are implicit in the
829 interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve
830 them across the calls as defined by calling convention.
832 For example the following program is invalid::
839 After the call the registers R1-R5 contain junk values and cannot be read.
840 An in-kernel eBPF verifier is used to validate internal BPF programs.
842 Also in the new design, eBPF is limited to 4096 insns, which means that any
843 program will terminate quickly and will only call a fixed number of kernel
844 functions. Original BPF and the new format are two operand instructions,
845 which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT.
847 The input context pointer for invoking the interpreter function is generic,
848 its content is defined by a specific use case. For seccomp register R1 points
849 to seccomp_data, for converted BPF filters R1 points to a skb.
851 A program, that is translated internally consists of the following elements::
853 op:16, jt:8, jf:8, k:32 ==> op:8, dst_reg:4, src_reg:4, off:16, imm:32
855 So far 87 internal BPF instructions were implemented. 8-bit 'op' opcode field
856 has room for new instructions. Some of them may use 16/24/32 byte encoding. New
857 instructions must be multiple of 8 bytes to preserve backward compatibility.
859 Internal BPF is a general purpose RISC instruction set. Not every register and
860 every instruction are used during translation from original BPF to new format.
861 For example, socket filters are not using ``exclusive add`` instruction, but
862 tracing filters may do to maintain counters of events, for example. Register R9
863 is not used by socket filters either, but more complex filters may be running
864 out of registers and would have to resort to spill/fill to stack.
866 Internal BPF can be used as a generic assembler for last step performance
867 optimizations, socket filters and seccomp are using it as assembler. Tracing
868 filters may use it as assembler to generate code from kernel. In kernel usage
869 may not be bounded by security considerations, since generated internal BPF code
870 may be optimizing internal code path and not being exposed to the user space.
871 Safety of internal BPF can come from a verifier (TBD). In such use cases as
872 described, it may be used as safe instruction set.
874 Just like the original BPF, the new format runs within a controlled environment,
875 is deterministic and the kernel can easily prove that. The safety of the program
876 can be determined in two steps: first step does depth-first-search to disallow
877 loops and other CFG validation; second step starts from the first insn and
878 descends all possible paths. It simulates execution of every insn and observes
879 the state change of registers and stack.
884 eBPF is reusing most of the opcode encoding from classic to simplify conversion
885 of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code'
886 field is divided into three parts::
888 +----------------+--------+--------------------+
889 | 4 bits | 1 bit | 3 bits |
890 | operation code | source | instruction class |
891 +----------------+--------+--------------------+
894 Three LSB bits store instruction class which is one of:
896 =================== ===============
897 Classic BPF classes eBPF classes
898 =================== ===============
899 BPF_LD 0x00 BPF_LD 0x00
900 BPF_LDX 0x01 BPF_LDX 0x01
901 BPF_ST 0x02 BPF_ST 0x02
902 BPF_STX 0x03 BPF_STX 0x03
903 BPF_ALU 0x04 BPF_ALU 0x04
904 BPF_JMP 0x05 BPF_JMP 0x05
905 BPF_RET 0x06 BPF_JMP32 0x06
906 BPF_MISC 0x07 BPF_ALU64 0x07
907 =================== ===============
909 When BPF_CLASS(code) == BPF_ALU or BPF_JMP, 4th bit encodes source operand ...
916 * in classic BPF, this means::
918 BPF_SRC(code) == BPF_X - use register X as source operand
919 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
921 * in eBPF, this means::
923 BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand
924 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
926 ... and four MSB bits store operation code.
928 If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of::
941 BPF_MOV 0xb0 /* eBPF only: mov reg to reg */
942 BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */
943 BPF_END 0xd0 /* eBPF only: endianness conversion */
945 If BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ], BPF_OP(code) is one of::
947 BPF_JA 0x00 /* BPF_JMP only */
952 BPF_JNE 0x50 /* eBPF only: jump != */
953 BPF_JSGT 0x60 /* eBPF only: signed '>' */
954 BPF_JSGE 0x70 /* eBPF only: signed '>=' */
955 BPF_CALL 0x80 /* eBPF BPF_JMP only: function call */
956 BPF_EXIT 0x90 /* eBPF BPF_JMP only: function return */
957 BPF_JLT 0xa0 /* eBPF only: unsigned '<' */
958 BPF_JLE 0xb0 /* eBPF only: unsigned '<=' */
959 BPF_JSLT 0xc0 /* eBPF only: signed '<' */
960 BPF_JSLE 0xd0 /* eBPF only: signed '<=' */
962 So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF
963 and eBPF. There are only two registers in classic BPF, so it means A += X.
964 In eBPF it means dst_reg = (u32) dst_reg + (u32) src_reg; similarly,
965 BPF_XOR | BPF_K | BPF_ALU means A ^= imm32 in classic BPF and analogous
966 src_reg = (u32) src_reg ^ (u32) imm32 in eBPF.
968 Classic BPF is using BPF_MISC class to represent A = X and X = A moves.
969 eBPF is using BPF_MOV | BPF_X | BPF_ALU code instead. Since there are no
970 BPF_MISC operations in eBPF, the class 7 is used as BPF_ALU64 to mean
971 exactly the same operations as BPF_ALU, but with 64-bit wide operands
972 instead. So BPF_ADD | BPF_X | BPF_ALU64 means 64-bit addition, i.e.:
973 dst_reg = dst_reg + src_reg
975 Classic BPF wastes the whole BPF_RET class to represent a single ``ret``
976 operation. Classic BPF_RET | BPF_K means copy imm32 into return register
977 and perform function exit. eBPF is modeled to match CPU, so BPF_JMP | BPF_EXIT
978 in eBPF means function exit only. The eBPF program needs to store return
979 value into register R0 before doing a BPF_EXIT. Class 6 in eBPF is used as
980 BPF_JMP32 to mean exactly the same operations as BPF_JMP, but with 32-bit wide
981 operands for the comparisons instead.
983 For load and store instructions the 8-bit 'code' field is divided as::
985 +--------+--------+-------------------+
986 | 3 bits | 2 bits | 3 bits |
987 | mode | size | instruction class |
988 +--------+--------+-------------------+
991 Size modifier is one of ...
995 BPF_W 0x00 /* word */
996 BPF_H 0x08 /* half word */
997 BPF_B 0x10 /* byte */
998 BPF_DW 0x18 /* eBPF only, double word */
1000 ... which encodes size of load/store operation::
1005 DW - 8 byte (eBPF only)
1007 Mode modifier is one of::
1009 BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
1013 BPF_LEN 0x80 /* classic BPF only, reserved in eBPF */
1014 BPF_MSH 0xa0 /* classic BPF only, reserved in eBPF */
1015 BPF_ATOMIC 0xc0 /* eBPF only, atomic operations */
1017 eBPF has two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and
1018 (BPF_IND | <size> | BPF_LD) which are used to access packet data.
1020 They had to be carried over from classic to have strong performance of
1021 socket filters running in eBPF interpreter. These instructions can only
1022 be used when interpreter context is a pointer to ``struct sk_buff`` and
1023 have seven implicit operands. Register R6 is an implicit input that must
1024 contain pointer to sk_buff. Register R0 is an implicit output which contains
1025 the data fetched from the packet. Registers R1-R5 are scratch registers
1026 and must not be used to store the data across BPF_ABS | BPF_LD or
1027 BPF_IND | BPF_LD instructions.
1029 These instructions have implicit program exit condition as well. When
1030 eBPF program is trying to access the data beyond the packet boundary,
1031 the interpreter will abort the execution of the program. JIT compilers
1032 therefore must preserve this property. src_reg and imm32 fields are
1033 explicit inputs to these instructions.
1037 BPF_IND | BPF_W | BPF_LD means:
1039 R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))
1040 and R1 - R5 were scratched.
1042 Unlike classic BPF instruction set, eBPF has generic load/store operations::
1044 BPF_MEM | <size> | BPF_STX: *(size *) (dst_reg + off) = src_reg
1045 BPF_MEM | <size> | BPF_ST: *(size *) (dst_reg + off) = imm32
1046 BPF_MEM | <size> | BPF_LDX: dst_reg = *(size *) (src_reg + off)
1048 Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW.
1050 It also includes atomic operations, which use the immediate field for extra
1053 .imm = BPF_ADD, .code = BPF_ATOMIC | BPF_W | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg
1054 .imm = BPF_ADD, .code = BPF_ATOMIC | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
1056 The basic atomic operations supported are::
1063 Each having equivalent semantics with the ``BPF_ADD`` example, that is: the
1064 memory location addresed by ``dst_reg + off`` is atomically modified, with
1065 ``src_reg`` as the other operand. If the ``BPF_FETCH`` flag is set in the
1066 immediate, then these operations also overwrite ``src_reg`` with the
1067 value that was in memory before it was modified.
1069 The more special operations are::
1073 This atomically exchanges ``src_reg`` with the value addressed by ``dst_reg +
1078 This atomically compares the value addressed by ``dst_reg + off`` with
1079 ``R0``. If they match it is replaced with ``src_reg``. In either case, the
1080 value that was there before is zero-extended and loaded back to ``R0``.
1082 Note that 1 and 2 byte atomic operations are not supported.
1084 Clang can generate atomic instructions by default when ``-mcpu=v3`` is
1085 enabled. If a lower version for ``-mcpu`` is set, the only atomic instruction
1086 Clang can generate is ``BPF_ADD`` *without* ``BPF_FETCH``. If you need to enable
1087 the atomics features, while keeping a lower ``-mcpu`` version, you can use
1088 ``-Xclang -target-feature -Xclang +alu32``.
1090 You may encounter ``BPF_XADD`` - this is a legacy name for ``BPF_ATOMIC``,
1091 referring to the exclusive-add operation encoded when the immediate field is
1094 eBPF has one 16-byte instruction: ``BPF_LD | BPF_DW | BPF_IMM`` which consists
1095 of two consecutive ``struct bpf_insn`` 8-byte blocks and interpreted as single
1096 instruction that loads 64-bit immediate value into a dst_reg.
1097 Classic BPF has similar instruction: ``BPF_LD | BPF_W | BPF_IMM`` which loads
1098 32-bit immediate value into a register.
1102 The safety of the eBPF program is determined in two steps.
1104 First step does DAG check to disallow loops and other CFG validation.
1105 In particular it will detect programs that have unreachable instructions.
1106 (though classic BPF checker allows them)
1108 Second step starts from the first insn and descends all possible paths.
1109 It simulates execution of every insn and observes the state change of
1110 registers and stack.
1112 At the start of the program the register R1 contains a pointer to context
1113 and has type PTR_TO_CTX.
1114 If verifier sees an insn that does R2=R1, then R2 has now type
1115 PTR_TO_CTX as well and can be used on the right hand side of expression.
1116 If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,
1117 since addition of two valid pointers makes invalid pointer.
1118 (In 'secure' mode verifier will reject any type of pointer arithmetic to make
1119 sure that kernel addresses don't leak to unprivileged users)
1121 If register was never written to, it's not readable::
1126 will be rejected, since R2 is unreadable at the start of the program.
1128 After kernel function call, R1-R5 are reset to unreadable and
1129 R0 has a return type of the function.
1131 Since R6-R9 are callee saved, their state is preserved across the call.
1140 is a correct program. If there was R1 instead of R6, it would have
1143 load/store instructions are allowed only with registers of valid types, which
1144 are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
1149 bpf_xadd *(u32 *)(R1 + 3) += R2
1152 will be rejected, since R1 doesn't have a valid pointer type at the time of
1153 execution of instruction bpf_xadd.
1155 At the start R1 type is PTR_TO_CTX (a pointer to generic ``struct bpf_context``)
1156 A callback is used to customize verifier to restrict eBPF program access to only
1157 certain fields within ctx structure with specified size and alignment.
1159 For example, the following insn::
1161 bpf_ld R0 = *(u32 *)(R6 + 8)
1163 intends to load a word from address R6 + 8 and store it into R0
1164 If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
1165 that offset 8 of size 4 bytes can be accessed for reading, otherwise
1166 the verifier will reject the program.
1167 If R6=PTR_TO_STACK, then access should be aligned and be within
1168 stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
1169 so it will fail verification, since it's out of bounds.
1171 The verifier will allow eBPF program to read data from stack only after
1174 Classic BPF verifier does similar check with M[0-15] memory slots.
1177 bpf_ld R0 = *(u32 *)(R10 - 4)
1181 Though R10 is correct read-only register and has type PTR_TO_STACK
1182 and R10 - 4 is within stack bounds, there were no stores into that location.
1184 Pointer register spill/fill is tracked as well, since four (R6-R9)
1185 callee saved registers may not be enough for some programs.
1187 Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
1188 The eBPF verifier will check that registers match argument constraints.
1189 After the call register R0 will be set to return type of the function.
1191 Function calls is a main mechanism to extend functionality of eBPF programs.
1192 Socket filters may let programs to call one set of functions, whereas tracing
1193 filters may allow completely different set.
1195 If a function made accessible to eBPF program, it needs to be thought through
1196 from safety point of view. The verifier will guarantee that the function is
1197 called with valid arguments.
1199 seccomp vs socket filters have different security restrictions for classic BPF.
1200 Seccomp solves this by two stage verifier: classic BPF verifier is followed
1201 by seccomp verifier. In case of eBPF one configurable verifier is shared for
1204 See details of eBPF verifier in kernel/bpf/verifier.c
1206 Register value tracking
1207 -----------------------
1208 In order to determine the safety of an eBPF program, the verifier must track
1209 the range of possible values in each register and also in each stack slot.
1210 This is done with ``struct bpf_reg_state``, defined in include/linux/
1211 bpf_verifier.h, which unifies tracking of scalar and pointer values. Each
1212 register state has a type, which is either NOT_INIT (the register has not been
1213 written to), SCALAR_VALUE (some value which is not usable as a pointer), or a
1214 pointer type. The types of pointers describe their base, as follows:
1218 Pointer to bpf_context.
1220 Pointer to struct bpf_map. "Const" because arithmetic
1221 on these pointers is forbidden.
1223 Pointer to the value stored in a map element.
1224 PTR_TO_MAP_VALUE_OR_NULL
1225 Either a pointer to a map value, or NULL; map accesses
1226 (see section 'eBPF maps', below) return this type,
1227 which becomes a PTR_TO_MAP_VALUE when checked != NULL.
1228 Arithmetic on these pointers is forbidden.
1234 skb->data + headlen; arithmetic forbidden.
1236 Pointer to struct bpf_sock_ops, implicitly refcounted.
1237 PTR_TO_SOCKET_OR_NULL
1238 Either a pointer to a socket, or NULL; socket lookup
1239 returns this type, which becomes a PTR_TO_SOCKET when
1240 checked != NULL. PTR_TO_SOCKET is reference-counted,
1241 so programs must release the reference through the
1242 socket release function before the end of the program.
1243 Arithmetic on these pointers is forbidden.
1245 However, a pointer may be offset from this base (as a result of pointer
1246 arithmetic), and this is tracked in two parts: the 'fixed offset' and 'variable
1247 offset'. The former is used when an exactly-known value (e.g. an immediate
1248 operand) is added to a pointer, while the latter is used for values which are
1249 not exactly known. The variable offset is also used in SCALAR_VALUEs, to track
1250 the range of possible values in the register.
1252 The verifier's knowledge about the variable offset consists of:
1254 * minimum and maximum values as unsigned
1255 * minimum and maximum values as signed
1257 * knowledge of the values of individual bits, in the form of a 'tnum': a u64
1258 'mask' and a u64 'value'. 1s in the mask represent bits whose value is unknown;
1259 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both
1260 mask and value; no bit should ever be 1 in both. For example, if a byte is read
1261 into a register from memory, the register's top 56 bits are known zero, while
1262 the low 8 are unknown - which is represented as the tnum (0x0; 0xff). If we
1263 then OR this with 0x40, we get (0x40; 0xbf), then if we add 1 we get (0x0;
1264 0x1ff), because of potential carries.
1266 Besides arithmetic, the register state can also be updated by conditional
1267 branches. For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch
1268 it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false'
1269 branch it will have a umax_value of 8. A signed compare (with BPF_JSGT or
1270 BPF_JSGE) would instead update the signed minimum/maximum values. Information
1271 from the signed and unsigned bounds can be combined; for instance if a value is
1272 first tested < 8 and then tested s> 4, the verifier will conclude that the value
1273 is also > 4 and s< 8, since the bounds prevent crossing the sign boundary.
1275 PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all
1276 pointers sharing that same variable offset. This is important for packet range
1277 checks: after adding a variable to a packet pointer register A, if you then copy
1278 it to another register B and then add a constant 4 to A, both registers will
1279 share the same 'id' but the A will have a fixed offset of +4. Then if A is
1280 bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is
1281 now known to have a safe range of at least 4 bytes. See 'Direct packet access',
1282 below, for more on PTR_TO_PACKET ranges.
1284 The 'id' field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of
1285 the pointer returned from a map lookup. This means that when one copy is
1286 checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs.
1287 As well as range-checking, the tracked information is also used for enforcing
1288 alignment of pointer accesses. For instance, on most systems the packet pointer
1289 is 2 bytes after a 4-byte alignment. If a program adds 14 bytes to that to jump
1290 over the Ethernet header, then reads IHL and addes (IHL * 4), the resulting
1291 pointer will have a variable offset known to be 4n+2 for some n, so adding the 2
1292 bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through
1293 that pointer are safe.
1294 The 'id' field is also used on PTR_TO_SOCKET and PTR_TO_SOCKET_OR_NULL, common
1295 to all copies of the pointer returned from a socket lookup. This has similar
1296 behaviour to the handling for PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE, but
1297 it also handles reference tracking for the pointer. PTR_TO_SOCKET implicitly
1298 represents a reference to the corresponding ``struct sock``. To ensure that the
1299 reference is not leaked, it is imperative to NULL-check the reference and in
1300 the non-NULL case, and pass the valid reference to the socket release function.
1302 Direct packet access
1303 --------------------
1304 In cls_bpf and act_bpf programs the verifier allows direct access to the packet
1305 data via skb->data and skb->data_end pointers.
1308 1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */
1309 2: r3 = *(u32 *)(r1 +76) /* load skb->data */
1312 5: if r5 > r4 goto pc+16
1313 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
1314 6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */
1316 this 2byte load from the packet is safe to do, since the program author
1317 did check ``if (skb->data + 14 > skb->data_end) goto err`` at insn #5 which
1318 means that in the fall-through case the register R3 (which points to skb->data)
1319 has at least 14 directly accessible bytes. The verifier marks it
1320 as R3=pkt(id=0,off=0,r=14).
1321 id=0 means that no additional variables were added to the register.
1322 off=0 means that no additional constants were added.
1323 r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
1324 Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
1325 to the packet data, but constant 14 was added to the register, so
1326 it now points to ``skb->data + 14`` and accessible range is [R5, R5 + 14 - 14)
1327 which is zero bytes.
1329 More complex packet access may look like::
1332 R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
1333 6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
1334 7: r4 = *(u8 *)(r3 +12)
1336 9: r3 = *(u32 *)(r1 +76) /* load skb->data */
1344 17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */
1345 18: if r2 > r1 goto pc+2
1346 R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp
1347 19: r1 = *(u8 *)(r3 +4)
1349 The state of the register R3 is R3=pkt(id=2,off=0,r=8)
1350 id=2 means that two ``r3 += rX`` instructions were seen, so r3 points to some
1351 offset within a packet and since the program author did
1352 ``if (r3 + 8 > r1) goto err`` at insn #18, the safe range is [R3, R3 + 8).
1353 The verifier only allows 'add'/'sub' operations on packet registers. Any other
1354 operation will set the register state to 'SCALAR_VALUE' and it won't be
1355 available for direct packet access.
1357 Operation ``r3 += rX`` may overflow and become less than original skb->data,
1358 therefore the verifier has to prevent that. So when it sees ``r3 += rX``
1359 instruction and rX is more than 16-bit value, any subsequent bounds-check of r3
1360 against skb->data_end will not give us 'range' information, so attempts to read
1361 through the pointer will give "invalid access to packet" error.
1363 Ex. after insn ``r4 = *(u8 *)(r3 +12)`` (insn #7 above) the state of r4 is
1364 R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits
1365 of the register are guaranteed to be zero, and nothing is known about the lower
1366 8 bits. After insn ``r4 *= 14`` the state becomes
1367 R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit
1368 value by constant 14 will keep upper 52 bits as zero, also the least significant
1369 bit will be zero as 14 is even. Similarly ``r2 >>= 48`` will make
1370 R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign
1371 extending. This logic is implemented in adjust_reg_min_max_vals() function,
1372 which calls adjust_ptr_min_max_vals() for adding pointer to scalar (or vice
1373 versa) and adjust_scalar_min_max_vals() for operations on two scalars.
1375 The end result is that bpf program author can access packet directly
1376 using normal C code as::
1378 void *data = (void *)(long)skb->data;
1379 void *data_end = (void *)(long)skb->data_end;
1380 struct eth_hdr *eth = data;
1381 struct iphdr *iph = data + sizeof(*eth);
1382 struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
1384 if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
1386 if (eth->h_proto != htons(ETH_P_IP))
1388 if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
1390 if (udp->dest == 53 || udp->source == 9)
1393 which makes such programs easier to write comparing to LD_ABS insn
1394 and significantly faster.
1398 'maps' is a generic storage of different types for sharing data between kernel
1401 The maps are accessed from user space via BPF syscall, which has commands:
1403 - create a map with given type and attributes
1404 ``map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size)``
1405 using attr->map_type, attr->key_size, attr->value_size, attr->max_entries
1406 returns process-local file descriptor or negative error
1408 - lookup key in a given map
1409 ``err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size)``
1410 using attr->map_fd, attr->key, attr->value
1411 returns zero and stores found elem into value or negative error
1413 - create or update key/value pair in a given map
1414 ``err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size)``
1415 using attr->map_fd, attr->key, attr->value
1416 returns zero or negative error
1418 - find and delete element by key in a given map
1419 ``err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size)``
1420 using attr->map_fd, attr->key
1422 - to delete map: close(fd)
1423 Exiting process will delete maps automatically
1425 userspace programs use this syscall to create/access maps that eBPF programs
1426 are concurrently updating.
1428 maps can have different types: hash, array, bloom filter, radix-tree, etc.
1430 The map is defined by:
1433 - max number of elements
1435 - value size in bytes
1439 The verifier does not actually walk all possible paths through the program. For
1440 each new branch to analyse, the verifier looks at all the states it's previously
1441 been in when at this instruction. If any of them contain the current state as a
1442 subset, the branch is 'pruned' - that is, the fact that the previous state was
1443 accepted implies the current state would be as well. For instance, if in the
1444 previous state, r1 held a packet-pointer, and in the current state, r1 holds a
1445 packet-pointer with a range as long or longer and at least as strict an
1446 alignment, then r1 is safe. Similarly, if r2 was NOT_INIT before then it can't
1447 have been used by any path from that point, so any value in r2 (including
1448 another NOT_INIT) is safe. The implementation is in the function regsafe().
1449 Pruning considers not only the registers but also the stack (and any spilled
1450 registers it may hold). They must all be safe for the branch to be pruned.
1451 This is implemented in states_equal().
1453 Understanding eBPF verifier messages
1454 ------------------------------------
1456 The following are few examples of invalid eBPF programs and verifier error
1457 messages as seen in the log:
1459 Program with unreachable instructions::
1461 static struct bpf_insn prog[] = {
1470 Program that reads uninitialized register::
1472 BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
1480 Program that doesn't initialize R0 before exiting::
1482 BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
1491 Program that accesses stack out of bounds::
1493 BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
1498 0: (7a) *(u64 *)(r10 +8) = 0
1499 invalid stack off=8 size=8
1501 Program that doesn't initialize stack before passing its address into function::
1503 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1504 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1505 BPF_LD_MAP_FD(BPF_REG_1, 0),
1506 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1515 invalid indirect read from stack off -8+0 size 8
1517 Program that uses invalid map_fd=0 while calling to map_lookup_elem() function::
1519 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1520 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1521 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1522 BPF_LD_MAP_FD(BPF_REG_1, 0),
1523 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1528 0: (7a) *(u64 *)(r10 -8) = 0
1533 fd 0 is not pointing to valid bpf_map
1535 Program that doesn't check return value of map_lookup_elem() before accessing
1538 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1539 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1540 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1541 BPF_LD_MAP_FD(BPF_REG_1, 0),
1542 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1543 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1548 0: (7a) *(u64 *)(r10 -8) = 0
1553 5: (7a) *(u64 *)(r0 +0) = 0
1554 R0 invalid mem access 'map_value_or_null'
1556 Program that correctly checks map_lookup_elem() returned value for NULL, but
1557 accesses the memory with incorrect alignment::
1559 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1560 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1561 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1562 BPF_LD_MAP_FD(BPF_REG_1, 0),
1563 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1564 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
1565 BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
1570 0: (7a) *(u64 *)(r10 -8) = 0
1575 5: (15) if r0 == 0x0 goto pc+1
1577 6: (7a) *(u64 *)(r0 +4) = 0
1578 misaligned access off 4 size 8
1580 Program that correctly checks map_lookup_elem() returned value for NULL and
1581 accesses memory with correct alignment in one side of 'if' branch, but fails
1582 to do so in the other side of 'if' branch::
1584 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1585 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1586 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1587 BPF_LD_MAP_FD(BPF_REG_1, 0),
1588 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1589 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
1590 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1592 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
1597 0: (7a) *(u64 *)(r10 -8) = 0
1602 5: (15) if r0 == 0x0 goto pc+2
1604 6: (7a) *(u64 *)(r0 +0) = 0
1607 from 5 to 8: R0=imm0 R10=fp
1608 8: (7a) *(u64 *)(r0 +0) = 1
1609 R0 invalid mem access 'imm'
1611 Program that performs a socket lookup then sets the pointer to NULL without
1614 BPF_MOV64_IMM(BPF_REG_2, 0),
1615 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
1616 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1617 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1618 BPF_MOV64_IMM(BPF_REG_3, 4),
1619 BPF_MOV64_IMM(BPF_REG_4, 0),
1620 BPF_MOV64_IMM(BPF_REG_5, 0),
1621 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
1622 BPF_MOV64_IMM(BPF_REG_0, 0),
1628 1: (63) *(u32 *)(r10 -8) = r2
1634 7: (85) call bpf_sk_lookup_tcp#65
1637 Unreleased reference id=1, alloc_insn=7
1639 Program that performs a socket lookup but does not NULL-check the returned
1642 BPF_MOV64_IMM(BPF_REG_2, 0),
1643 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
1644 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1645 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1646 BPF_MOV64_IMM(BPF_REG_3, 4),
1647 BPF_MOV64_IMM(BPF_REG_4, 0),
1648 BPF_MOV64_IMM(BPF_REG_5, 0),
1649 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
1655 1: (63) *(u32 *)(r10 -8) = r2
1661 7: (85) call bpf_sk_lookup_tcp#65
1663 Unreleased reference id=1, alloc_insn=7
1668 Next to the BPF toolchain, the kernel also ships a test module that contains
1669 various test cases for classic and internal BPF that can be executed against
1670 the BPF interpreter and JIT compiler. It can be found in lib/test_bpf.c and
1671 enabled via Kconfig::
1675 After the module has been built and installed, the test suite can be executed
1676 via insmod or modprobe against 'test_bpf' module. Results of the test cases
1677 including timings in nsec can be found in the kernel log (dmesg).
1682 Also trinity, the Linux syscall fuzzer, has built-in support for BPF and
1683 SECCOMP-BPF kernel fuzzing.
1688 The document was written in the hope that it is found useful and in order
1689 to give potential BPF hackers or security auditors a better overview of
1690 the underlying architecture.
1692 - Jay Schulist <jschlst@samba.org>
1693 - Daniel Borkmann <daniel@iogearbox.net>
1694 - Alexei Starovoitov <ast@kernel.org>