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 **icmp random packet sampling, 1 in 4**::
329 # get a random uint32 number
336 **SECCOMP filter example**::
338 ld [4] /* offsetof(struct seccomp_data, arch) */
339 jne #0xc000003e, bad /* AUDIT_ARCH_X86_64 */
340 ld [0] /* offsetof(struct seccomp_data, nr) */
341 jeq #15, good /* __NR_rt_sigreturn */
342 jeq #231, good /* __NR_exit_group */
343 jeq #60, good /* __NR_exit */
344 jeq #0, good /* __NR_read */
345 jeq #1, good /* __NR_write */
346 jeq #5, good /* __NR_fstat */
347 jeq #9, good /* __NR_mmap */
348 jeq #14, good /* __NR_rt_sigprocmask */
349 jeq #13, good /* __NR_rt_sigaction */
350 jeq #35, good /* __NR_nanosleep */
351 bad: ret #0 /* SECCOMP_RET_KILL_THREAD */
352 good: ret #0x7fff0000 /* SECCOMP_RET_ALLOW */
354 Examples for low-level BPF extension:
356 **Packet for interface index 13**::
363 **(Accelerated) VLAN w/ id 10**::
370 The above example code can be placed into a file (here called "foo"), and
371 then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf
372 and cls_bpf understands and can directly be loaded with. Example with above
376 4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,
378 In copy and paste C-like output::
381 { 0x28, 0, 0, 0x0000000c },
382 { 0x15, 0, 1, 0x00000806 },
383 { 0x06, 0, 0, 0xffffffff },
384 { 0x06, 0, 0, 0000000000 },
386 In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF
387 filters that might not be obvious at first, it's good to test filters before
388 attaching to a live system. For that purpose, there's a small tool called
389 bpf_dbg under tools/bpf/ in the kernel source directory. This debugger allows
390 for testing BPF filters against given pcap files, single stepping through the
391 BPF code on the pcap's packets and to do BPF machine register dumps.
393 Starting bpf_dbg is trivial and just requires issuing::
397 In case input and output do not equal stdin/stdout, bpf_dbg takes an
398 alternative stdin source as a first argument, and an alternative stdout
399 sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`.
401 Other than that, a particular libreadline configuration can be set via
402 file "~/.bpf_dbg_init" and the command history is stored in the file
403 "~/.bpf_dbg_history".
405 Interaction in bpf_dbg happens through a shell that also has auto-completion
406 support (follow-up example commands starting with '>' denote bpf_dbg shell).
407 The usual workflow would be to ...
409 * 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
410 Loads a BPF filter from standard output of bpf_asm, or transformed via
411 e.g. ``tcpdump -iem1 -ddd port 22 | tr '\n' ','``. Note that for JIT
412 debugging (next section), this command creates a temporary socket and
413 loads the BPF code into the kernel. Thus, this will also be useful for
418 Loads standard tcpdump pcap file.
423 Runs through all packets from a pcap to account how many passes and fails
424 the filter will generate. A limit of packets to traverse can be given.
429 l1: jeq #0x800, l2, l5
435 Prints out BPF code disassembly.
439 /* { op, jt, jf, k }, */
440 { 0x28, 0, 0, 0x0000000c },
441 { 0x15, 0, 3, 0x00000800 },
442 { 0x30, 0, 0, 0x00000017 },
443 { 0x15, 0, 1, 0x00000001 },
444 { 0x06, 0, 0, 0x0000ffff },
445 { 0x06, 0, 0, 0000000000 },
447 Prints out C-style BPF code dump.
451 breakpoint at: l0: ldh [12]
455 breakpoint at: l1: jeq #0x800, l2, l5
459 Sets breakpoints at particular BPF instructions. Issuing a `run` command
460 will walk through the pcap file continuing from the current packet and
461 break when a breakpoint is being hit (another `run` will continue from
462 the currently active breakpoint executing next instructions):
467 pc: [0] <-- program counter
468 code: [40] jt[0] jf[0] k[12] <-- plain BPF code of current instruction
469 curr: l0: ldh [12] <-- disassembly of current instruction
470 A: [00000000][0] <-- content of A (hex, decimal)
471 X: [00000000][0] <-- content of X (hex, decimal)
472 M[0,15]: [00000000][0] <-- folded content of M (hex, decimal)
473 -- packet dump -- <-- Current packet from pcap (hex)
475 0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
476 16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
477 32: 00 00 00 00 00 00 0a 3b 01 01
485 Prints currently set breakpoints.
489 Performs single stepping through the BPF program from the current pc
490 offset. Thus, on each step invocation, above register dump is issued.
491 This can go forwards and backwards in time, a plain `step` will break
492 on the next BPF instruction, thus +1. (No `run` needs to be issued here.)
496 Selects a given packet from the pcap file to continue from. Thus, on
497 the next `run` or `step`, the BPF program is being evaluated against
498 the user pre-selected packet. Numbering starts just as in Wireshark
508 The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC,
509 PowerPC, ARM, ARM64, MIPS, RISC-V and s390 and can be enabled through
510 CONFIG_BPF_JIT. The JIT compiler is transparently invoked for each
511 attached filter from user space or for internal kernel users if it has
512 been previously enabled by root::
514 echo 1 > /proc/sys/net/core/bpf_jit_enable
516 For JIT developers, doing audits etc, each compile run can output the generated
517 opcode image into the kernel log via::
519 echo 2 > /proc/sys/net/core/bpf_jit_enable
521 Example output from dmesg::
523 [ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
524 [ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
525 [ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
526 [ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
527 [ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
528 [ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3
530 When CONFIG_BPF_JIT_ALWAYS_ON is enabled, bpf_jit_enable is permanently set to 1 and
531 setting any other value than that will return in failure. This is even the case for
532 setting bpf_jit_enable to 2, since dumping the final JIT image into the kernel log
533 is discouraged and introspection through bpftool (under tools/bpf/bpftool/) is the
534 generally recommended approach instead.
536 In the kernel source tree under tools/bpf/, there's bpf_jit_disasm for
537 generating disassembly out of the kernel log's hexdump::
540 70 bytes emitted from JIT compiler (pass:3, flen:6)
541 ffffffffa0069c8f + <x>:
545 8: mov %rbx,-0x8(%rbp)
546 c: mov 0x68(%rdi),%r9d
547 10: sub 0x6c(%rdi),%r9d
548 14: mov 0xd8(%rdi),%r8
550 20: callq 0xffffffffe0ff9442
552 2a: jne 0x0000000000000042
554 31: callq 0xffffffffe0ff945e
556 39: jne 0x0000000000000042
558 40: jmp 0x0000000000000044
563 Issuing option `-o` will "annotate" opcodes to resulting assembler
564 instructions, which can be very useful for JIT developers:
566 # ./bpf_jit_disasm -o
567 70 bytes emitted from JIT compiler (pass:3, flen:6)
568 ffffffffa0069c8f + <x>:
575 8: mov %rbx,-0x8(%rbp)
577 c: mov 0x68(%rdi),%r9d
579 10: sub 0x6c(%rdi),%r9d
581 14: mov 0xd8(%rdi),%r8
585 20: callq 0xffffffffe0ff9442
589 2a: jne 0x0000000000000042
593 31: callq 0xffffffffe0ff945e
597 39: jne 0x0000000000000042
601 40: jmp 0x0000000000000044
610 For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful
611 toolchain for developing and testing the kernel's JIT compiler.
615 Internally, for the kernel interpreter, a different instruction set
616 format with similar underlying principles from BPF described in previous
617 paragraphs is being used. However, the instruction set format is modelled
618 closer to the underlying architecture to mimic native instruction sets, so
619 that a better performance can be achieved (more details later). This new
620 ISA is called 'eBPF' or 'internal BPF' interchangeably. (Note: eBPF which
621 originates from [e]xtended BPF is not the same as BPF extensions! While
622 eBPF is an ISA, BPF extensions date back to classic BPF's 'overloading'
623 of BPF_LD | BPF_{B,H,W} | BPF_ABS instruction.)
625 It is designed to be JITed with one to one mapping, which can also open up
626 the possibility for GCC/LLVM compilers to generate optimized eBPF code through
627 an eBPF backend that performs almost as fast as natively compiled code.
629 The new instruction set was originally designed with the possible goal in
630 mind to write programs in "restricted C" and compile into eBPF with a optional
631 GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with
632 minimal performance overhead over two steps, that is, C -> eBPF -> native code.
634 Currently, the new format is being used for running user BPF programs, which
635 includes seccomp BPF, classic socket filters, cls_bpf traffic classifier,
636 team driver's classifier for its load-balancing mode, netfilter's xt_bpf
637 extension, PTP dissector/classifier, and much more. They are all internally
638 converted by the kernel into the new instruction set representation and run
639 in the eBPF interpreter. For in-kernel handlers, this all works transparently
640 by using bpf_prog_create() for setting up the filter, resp.
641 bpf_prog_destroy() for destroying it. The function
642 bpf_prog_run(filter, ctx) transparently invokes eBPF interpreter or JITed
643 code to run the filter. 'filter' is a pointer to struct bpf_prog that we
644 got from bpf_prog_create(), and 'ctx' the given context (e.g.
645 skb pointer). All constraints and restrictions from bpf_check_classic() apply
646 before a conversion to the new layout is being done behind the scenes!
648 Currently, the classic BPF format is being used for JITing on most
649 32-bit architectures, whereas x86-64, aarch64, s390x, powerpc64,
650 sparc64, arm32, riscv64, riscv32 perform JIT compilation from eBPF
653 Some core changes of the new internal format:
655 - Number of registers increase from 2 to 10:
657 The old format had two registers A and X, and a hidden frame pointer. The
658 new layout extends this to be 10 internal registers and a read-only frame
659 pointer. Since 64-bit CPUs are passing arguments to functions via registers
660 the number of args from eBPF program to in-kernel function is restricted
661 to 5 and one register is used to accept return value from an in-kernel
662 function. Natively, x86_64 passes first 6 arguments in registers, aarch64/
663 sparcv9/mips64 have 7 - 8 registers for arguments; x86_64 has 6 callee saved
664 registers, and aarch64/sparcv9/mips64 have 11 or more callee saved registers.
666 Therefore, eBPF calling convention is defined as:
668 * R0 - return value from in-kernel function, and exit value for eBPF program
669 * R1 - R5 - arguments from eBPF program to in-kernel function
670 * R6 - R9 - callee saved registers that in-kernel function will preserve
671 * R10 - read-only frame pointer to access stack
673 Thus, all eBPF registers map one to one to HW registers on x86_64, aarch64,
674 etc, and eBPF calling convention maps directly to ABIs used by the kernel on
675 64-bit architectures.
677 On 32-bit architectures JIT may map programs that use only 32-bit arithmetic
678 and may let more complex programs to be interpreted.
680 R0 - R5 are scratch registers and eBPF program needs spill/fill them if
681 necessary across calls. Note that there is only one eBPF program (== one
682 eBPF main routine) and it cannot call other eBPF functions, it can only
683 call predefined in-kernel functions, though.
685 - Register width increases from 32-bit to 64-bit:
687 Still, the semantics of the original 32-bit ALU operations are preserved
688 via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower
689 subregisters that zero-extend into 64-bit if they are being written to.
690 That behavior maps directly to x86_64 and arm64 subregister definition, but
691 makes other JITs more difficult.
693 32-bit architectures run 64-bit internal BPF programs via interpreter.
694 Their JITs may convert BPF programs that only use 32-bit subregisters into
695 native instruction set and let the rest being interpreted.
697 Operation is 64-bit, because on 64-bit architectures, pointers are also
698 64-bit wide, and we want to pass 64-bit values in/out of kernel functions,
699 so 32-bit eBPF registers would otherwise require to define register-pair
700 ABI, thus, there won't be able to use a direct eBPF register to HW register
701 mapping and JIT would need to do combine/split/move operations for every
702 register in and out of the function, which is complex, bug prone and slow.
703 Another reason is the use of atomic 64-bit counters.
705 - Conditional jt/jf targets replaced with jt/fall-through:
707 While the original design has constructs such as ``if (cond) jump_true;
708 else jump_false;``, they are being replaced into alternative constructs like
709 ``if (cond) jump_true; /* else fall-through */``.
711 - Introduces bpf_call insn and register passing convention for zero overhead
712 calls from/to other kernel functions:
714 Before an in-kernel function call, the internal BPF program needs to
715 place function arguments into R1 to R5 registers to satisfy calling
716 convention, then the interpreter will take them from registers and pass
717 to in-kernel function. If R1 - R5 registers are mapped to CPU registers
718 that are used for argument passing on given architecture, the JIT compiler
719 doesn't need to emit extra moves. Function arguments will be in the correct
720 registers and BPF_CALL instruction will be JITed as single 'call' HW
721 instruction. This calling convention was picked to cover common call
722 situations without performance penalty.
724 After an in-kernel function call, R1 - R5 are reset to unreadable and R0 has
725 a return value of the function. Since R6 - R9 are callee saved, their state
726 is preserved across the call.
728 For example, consider three C functions::
730 u64 f1() { return (*_f2)(1); }
731 u64 f2(u64 a) { return f3(a + 1, a); }
732 u64 f3(u64 a, u64 b) { return a - b; }
734 GCC can compile f1, f3 into x86_64::
745 Function f2 in eBPF may look like::
753 If f2 is JITed and the pointer stored to ``_f2``. The calls f1 -> f2 -> f3 and
754 returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to
755 be used to call into f2.
757 For practical reasons all eBPF programs have only one argument 'ctx' which is
758 already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs
759 can call kernel functions with up to 5 arguments. Calls with 6 or more arguments
760 are currently not supported, but these restrictions can be lifted if necessary
763 On 64-bit architectures all register map to HW registers one to one. For
764 example, x86_64 JIT compiler can map them as ...
780 ... since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing
781 and rbx, r12 - r15 are callee saved.
783 Then the following internal BPF pseudo-program::
785 bpf_mov R6, R1 /* save ctx */
791 bpf_mov R7, R0 /* save foo() return value */
792 bpf_mov R1, R6 /* restore ctx for next call */
801 After JIT to x86_64 may look like::
806 mov %rbx,-0x228(%rbp)
807 mov %r13,-0x220(%rbp)
822 mov -0x228(%rbp),%rbx
823 mov -0x220(%rbp),%r13
827 Which is in this example equivalent in C to::
829 u64 bpf_filter(u64 ctx)
831 return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
834 In-kernel functions foo() and bar() with prototype: u64 (*)(u64 arg1, u64
835 arg2, u64 arg3, u64 arg4, u64 arg5); will receive arguments in proper
836 registers and place their return value into ``%rax`` which is R0 in eBPF.
837 Prologue and epilogue are emitted by JIT and are implicit in the
838 interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve
839 them across the calls as defined by calling convention.
841 For example the following program is invalid::
848 After the call the registers R1-R5 contain junk values and cannot be read.
849 An in-kernel eBPF verifier is used to validate internal BPF programs.
851 Also in the new design, eBPF is limited to 4096 insns, which means that any
852 program will terminate quickly and will only call a fixed number of kernel
853 functions. Original BPF and the new format are two operand instructions,
854 which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT.
856 The input context pointer for invoking the interpreter function is generic,
857 its content is defined by a specific use case. For seccomp register R1 points
858 to seccomp_data, for converted BPF filters R1 points to a skb.
860 A program, that is translated internally consists of the following elements::
862 op:16, jt:8, jf:8, k:32 ==> op:8, dst_reg:4, src_reg:4, off:16, imm:32
864 So far 87 internal BPF instructions were implemented. 8-bit 'op' opcode field
865 has room for new instructions. Some of them may use 16/24/32 byte encoding. New
866 instructions must be multiple of 8 bytes to preserve backward compatibility.
868 Internal BPF is a general purpose RISC instruction set. Not every register and
869 every instruction are used during translation from original BPF to new format.
870 For example, socket filters are not using ``exclusive add`` instruction, but
871 tracing filters may do to maintain counters of events, for example. Register R9
872 is not used by socket filters either, but more complex filters may be running
873 out of registers and would have to resort to spill/fill to stack.
875 Internal BPF can be used as a generic assembler for last step performance
876 optimizations, socket filters and seccomp are using it as assembler. Tracing
877 filters may use it as assembler to generate code from kernel. In kernel usage
878 may not be bounded by security considerations, since generated internal BPF code
879 may be optimizing internal code path and not being exposed to the user space.
880 Safety of internal BPF can come from a verifier (TBD). In such use cases as
881 described, it may be used as safe instruction set.
883 Just like the original BPF, the new format runs within a controlled environment,
884 is deterministic and the kernel can easily prove that. The safety of the program
885 can be determined in two steps: first step does depth-first-search to disallow
886 loops and other CFG validation; second step starts from the first insn and
887 descends all possible paths. It simulates execution of every insn and observes
888 the state change of registers and stack.
893 eBPF is reusing most of the opcode encoding from classic to simplify conversion
894 of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code'
895 field is divided into three parts::
897 +----------------+--------+--------------------+
898 | 4 bits | 1 bit | 3 bits |
899 | operation code | source | instruction class |
900 +----------------+--------+--------------------+
903 Three LSB bits store instruction class which is one of:
905 =================== ===============
906 Classic BPF classes eBPF classes
907 =================== ===============
908 BPF_LD 0x00 BPF_LD 0x00
909 BPF_LDX 0x01 BPF_LDX 0x01
910 BPF_ST 0x02 BPF_ST 0x02
911 BPF_STX 0x03 BPF_STX 0x03
912 BPF_ALU 0x04 BPF_ALU 0x04
913 BPF_JMP 0x05 BPF_JMP 0x05
914 BPF_RET 0x06 BPF_JMP32 0x06
915 BPF_MISC 0x07 BPF_ALU64 0x07
916 =================== ===============
918 When BPF_CLASS(code) == BPF_ALU or BPF_JMP, 4th bit encodes source operand ...
925 * in classic BPF, this means::
927 BPF_SRC(code) == BPF_X - use register X as source operand
928 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
930 * in eBPF, this means::
932 BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand
933 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
935 ... and four MSB bits store operation code.
937 If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of::
950 BPF_MOV 0xb0 /* eBPF only: mov reg to reg */
951 BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */
952 BPF_END 0xd0 /* eBPF only: endianness conversion */
954 If BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ], BPF_OP(code) is one of::
956 BPF_JA 0x00 /* BPF_JMP only */
961 BPF_JNE 0x50 /* eBPF only: jump != */
962 BPF_JSGT 0x60 /* eBPF only: signed '>' */
963 BPF_JSGE 0x70 /* eBPF only: signed '>=' */
964 BPF_CALL 0x80 /* eBPF BPF_JMP only: function call */
965 BPF_EXIT 0x90 /* eBPF BPF_JMP only: function return */
966 BPF_JLT 0xa0 /* eBPF only: unsigned '<' */
967 BPF_JLE 0xb0 /* eBPF only: unsigned '<=' */
968 BPF_JSLT 0xc0 /* eBPF only: signed '<' */
969 BPF_JSLE 0xd0 /* eBPF only: signed '<=' */
971 So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF
972 and eBPF. There are only two registers in classic BPF, so it means A += X.
973 In eBPF it means dst_reg = (u32) dst_reg + (u32) src_reg; similarly,
974 BPF_XOR | BPF_K | BPF_ALU means A ^= imm32 in classic BPF and analogous
975 src_reg = (u32) src_reg ^ (u32) imm32 in eBPF.
977 Classic BPF is using BPF_MISC class to represent A = X and X = A moves.
978 eBPF is using BPF_MOV | BPF_X | BPF_ALU code instead. Since there are no
979 BPF_MISC operations in eBPF, the class 7 is used as BPF_ALU64 to mean
980 exactly the same operations as BPF_ALU, but with 64-bit wide operands
981 instead. So BPF_ADD | BPF_X | BPF_ALU64 means 64-bit addition, i.e.:
982 dst_reg = dst_reg + src_reg
984 Classic BPF wastes the whole BPF_RET class to represent a single ``ret``
985 operation. Classic BPF_RET | BPF_K means copy imm32 into return register
986 and perform function exit. eBPF is modeled to match CPU, so BPF_JMP | BPF_EXIT
987 in eBPF means function exit only. The eBPF program needs to store return
988 value into register R0 before doing a BPF_EXIT. Class 6 in eBPF is used as
989 BPF_JMP32 to mean exactly the same operations as BPF_JMP, but with 32-bit wide
990 operands for the comparisons instead.
992 For load and store instructions the 8-bit 'code' field is divided as::
994 +--------+--------+-------------------+
995 | 3 bits | 2 bits | 3 bits |
996 | mode | size | instruction class |
997 +--------+--------+-------------------+
1000 Size modifier is one of ...
1004 BPF_W 0x00 /* word */
1005 BPF_H 0x08 /* half word */
1006 BPF_B 0x10 /* byte */
1007 BPF_DW 0x18 /* eBPF only, double word */
1009 ... which encodes size of load/store operation::
1014 DW - 8 byte (eBPF only)
1016 Mode modifier is one of::
1018 BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
1022 BPF_LEN 0x80 /* classic BPF only, reserved in eBPF */
1023 BPF_MSH 0xa0 /* classic BPF only, reserved in eBPF */
1024 BPF_ATOMIC 0xc0 /* eBPF only, atomic operations */
1026 eBPF has two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and
1027 (BPF_IND | <size> | BPF_LD) which are used to access packet data.
1029 They had to be carried over from classic to have strong performance of
1030 socket filters running in eBPF interpreter. These instructions can only
1031 be used when interpreter context is a pointer to ``struct sk_buff`` and
1032 have seven implicit operands. Register R6 is an implicit input that must
1033 contain pointer to sk_buff. Register R0 is an implicit output which contains
1034 the data fetched from the packet. Registers R1-R5 are scratch registers
1035 and must not be used to store the data across BPF_ABS | BPF_LD or
1036 BPF_IND | BPF_LD instructions.
1038 These instructions have implicit program exit condition as well. When
1039 eBPF program is trying to access the data beyond the packet boundary,
1040 the interpreter will abort the execution of the program. JIT compilers
1041 therefore must preserve this property. src_reg and imm32 fields are
1042 explicit inputs to these instructions.
1046 BPF_IND | BPF_W | BPF_LD means:
1048 R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))
1049 and R1 - R5 were scratched.
1051 Unlike classic BPF instruction set, eBPF has generic load/store operations::
1053 BPF_MEM | <size> | BPF_STX: *(size *) (dst_reg + off) = src_reg
1054 BPF_MEM | <size> | BPF_ST: *(size *) (dst_reg + off) = imm32
1055 BPF_MEM | <size> | BPF_LDX: dst_reg = *(size *) (src_reg + off)
1057 Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW.
1059 It also includes atomic operations, which use the immediate field for extra
1062 .imm = BPF_ADD, .code = BPF_ATOMIC | BPF_W | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg
1063 .imm = BPF_ADD, .code = BPF_ATOMIC | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
1065 The basic atomic operations supported are::
1072 Each having equivalent semantics with the ``BPF_ADD`` example, that is: the
1073 memory location addresed by ``dst_reg + off`` is atomically modified, with
1074 ``src_reg`` as the other operand. If the ``BPF_FETCH`` flag is set in the
1075 immediate, then these operations also overwrite ``src_reg`` with the
1076 value that was in memory before it was modified.
1078 The more special operations are::
1082 This atomically exchanges ``src_reg`` with the value addressed by ``dst_reg +
1087 This atomically compares the value addressed by ``dst_reg + off`` with
1088 ``R0``. If they match it is replaced with ``src_reg``. In either case, the
1089 value that was there before is zero-extended and loaded back to ``R0``.
1091 Note that 1 and 2 byte atomic operations are not supported.
1093 Clang can generate atomic instructions by default when ``-mcpu=v3`` is
1094 enabled. If a lower version for ``-mcpu`` is set, the only atomic instruction
1095 Clang can generate is ``BPF_ADD`` *without* ``BPF_FETCH``. If you need to enable
1096 the atomics features, while keeping a lower ``-mcpu`` version, you can use
1097 ``-Xclang -target-feature -Xclang +alu32``.
1099 You may encounter ``BPF_XADD`` - this is a legacy name for ``BPF_ATOMIC``,
1100 referring to the exclusive-add operation encoded when the immediate field is
1103 eBPF has one 16-byte instruction: ``BPF_LD | BPF_DW | BPF_IMM`` which consists
1104 of two consecutive ``struct bpf_insn`` 8-byte blocks and interpreted as single
1105 instruction that loads 64-bit immediate value into a dst_reg.
1106 Classic BPF has similar instruction: ``BPF_LD | BPF_W | BPF_IMM`` which loads
1107 32-bit immediate value into a register.
1111 The safety of the eBPF program is determined in two steps.
1113 First step does DAG check to disallow loops and other CFG validation.
1114 In particular it will detect programs that have unreachable instructions.
1115 (though classic BPF checker allows them)
1117 Second step starts from the first insn and descends all possible paths.
1118 It simulates execution of every insn and observes the state change of
1119 registers and stack.
1121 At the start of the program the register R1 contains a pointer to context
1122 and has type PTR_TO_CTX.
1123 If verifier sees an insn that does R2=R1, then R2 has now type
1124 PTR_TO_CTX as well and can be used on the right hand side of expression.
1125 If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,
1126 since addition of two valid pointers makes invalid pointer.
1127 (In 'secure' mode verifier will reject any type of pointer arithmetic to make
1128 sure that kernel addresses don't leak to unprivileged users)
1130 If register was never written to, it's not readable::
1135 will be rejected, since R2 is unreadable at the start of the program.
1137 After kernel function call, R1-R5 are reset to unreadable and
1138 R0 has a return type of the function.
1140 Since R6-R9 are callee saved, their state is preserved across the call.
1149 is a correct program. If there was R1 instead of R6, it would have
1152 load/store instructions are allowed only with registers of valid types, which
1153 are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
1158 bpf_xadd *(u32 *)(R1 + 3) += R2
1161 will be rejected, since R1 doesn't have a valid pointer type at the time of
1162 execution of instruction bpf_xadd.
1164 At the start R1 type is PTR_TO_CTX (a pointer to generic ``struct bpf_context``)
1165 A callback is used to customize verifier to restrict eBPF program access to only
1166 certain fields within ctx structure with specified size and alignment.
1168 For example, the following insn::
1170 bpf_ld R0 = *(u32 *)(R6 + 8)
1172 intends to load a word from address R6 + 8 and store it into R0
1173 If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
1174 that offset 8 of size 4 bytes can be accessed for reading, otherwise
1175 the verifier will reject the program.
1176 If R6=PTR_TO_STACK, then access should be aligned and be within
1177 stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
1178 so it will fail verification, since it's out of bounds.
1180 The verifier will allow eBPF program to read data from stack only after
1183 Classic BPF verifier does similar check with M[0-15] memory slots.
1186 bpf_ld R0 = *(u32 *)(R10 - 4)
1190 Though R10 is correct read-only register and has type PTR_TO_STACK
1191 and R10 - 4 is within stack bounds, there were no stores into that location.
1193 Pointer register spill/fill is tracked as well, since four (R6-R9)
1194 callee saved registers may not be enough for some programs.
1196 Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
1197 The eBPF verifier will check that registers match argument constraints.
1198 After the call register R0 will be set to return type of the function.
1200 Function calls is a main mechanism to extend functionality of eBPF programs.
1201 Socket filters may let programs to call one set of functions, whereas tracing
1202 filters may allow completely different set.
1204 If a function made accessible to eBPF program, it needs to be thought through
1205 from safety point of view. The verifier will guarantee that the function is
1206 called with valid arguments.
1208 seccomp vs socket filters have different security restrictions for classic BPF.
1209 Seccomp solves this by two stage verifier: classic BPF verifier is followed
1210 by seccomp verifier. In case of eBPF one configurable verifier is shared for
1213 See details of eBPF verifier in kernel/bpf/verifier.c
1215 Register value tracking
1216 -----------------------
1217 In order to determine the safety of an eBPF program, the verifier must track
1218 the range of possible values in each register and also in each stack slot.
1219 This is done with ``struct bpf_reg_state``, defined in include/linux/
1220 bpf_verifier.h, which unifies tracking of scalar and pointer values. Each
1221 register state has a type, which is either NOT_INIT (the register has not been
1222 written to), SCALAR_VALUE (some value which is not usable as a pointer), or a
1223 pointer type. The types of pointers describe their base, as follows:
1227 Pointer to bpf_context.
1229 Pointer to struct bpf_map. "Const" because arithmetic
1230 on these pointers is forbidden.
1232 Pointer to the value stored in a map element.
1233 PTR_TO_MAP_VALUE_OR_NULL
1234 Either a pointer to a map value, or NULL; map accesses
1235 (see section 'eBPF maps', below) return this type,
1236 which becomes a PTR_TO_MAP_VALUE when checked != NULL.
1237 Arithmetic on these pointers is forbidden.
1243 skb->data + headlen; arithmetic forbidden.
1245 Pointer to struct bpf_sock_ops, implicitly refcounted.
1246 PTR_TO_SOCKET_OR_NULL
1247 Either a pointer to a socket, or NULL; socket lookup
1248 returns this type, which becomes a PTR_TO_SOCKET when
1249 checked != NULL. PTR_TO_SOCKET is reference-counted,
1250 so programs must release the reference through the
1251 socket release function before the end of the program.
1252 Arithmetic on these pointers is forbidden.
1254 However, a pointer may be offset from this base (as a result of pointer
1255 arithmetic), and this is tracked in two parts: the 'fixed offset' and 'variable
1256 offset'. The former is used when an exactly-known value (e.g. an immediate
1257 operand) is added to a pointer, while the latter is used for values which are
1258 not exactly known. The variable offset is also used in SCALAR_VALUEs, to track
1259 the range of possible values in the register.
1261 The verifier's knowledge about the variable offset consists of:
1263 * minimum and maximum values as unsigned
1264 * minimum and maximum values as signed
1266 * knowledge of the values of individual bits, in the form of a 'tnum': a u64
1267 'mask' and a u64 'value'. 1s in the mask represent bits whose value is unknown;
1268 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both
1269 mask and value; no bit should ever be 1 in both. For example, if a byte is read
1270 into a register from memory, the register's top 56 bits are known zero, while
1271 the low 8 are unknown - which is represented as the tnum (0x0; 0xff). If we
1272 then OR this with 0x40, we get (0x40; 0xbf), then if we add 1 we get (0x0;
1273 0x1ff), because of potential carries.
1275 Besides arithmetic, the register state can also be updated by conditional
1276 branches. For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch
1277 it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false'
1278 branch it will have a umax_value of 8. A signed compare (with BPF_JSGT or
1279 BPF_JSGE) would instead update the signed minimum/maximum values. Information
1280 from the signed and unsigned bounds can be combined; for instance if a value is
1281 first tested < 8 and then tested s> 4, the verifier will conclude that the value
1282 is also > 4 and s< 8, since the bounds prevent crossing the sign boundary.
1284 PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all
1285 pointers sharing that same variable offset. This is important for packet range
1286 checks: after adding a variable to a packet pointer register A, if you then copy
1287 it to another register B and then add a constant 4 to A, both registers will
1288 share the same 'id' but the A will have a fixed offset of +4. Then if A is
1289 bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is
1290 now known to have a safe range of at least 4 bytes. See 'Direct packet access',
1291 below, for more on PTR_TO_PACKET ranges.
1293 The 'id' field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of
1294 the pointer returned from a map lookup. This means that when one copy is
1295 checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs.
1296 As well as range-checking, the tracked information is also used for enforcing
1297 alignment of pointer accesses. For instance, on most systems the packet pointer
1298 is 2 bytes after a 4-byte alignment. If a program adds 14 bytes to that to jump
1299 over the Ethernet header, then reads IHL and addes (IHL * 4), the resulting
1300 pointer will have a variable offset known to be 4n+2 for some n, so adding the 2
1301 bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through
1302 that pointer are safe.
1303 The 'id' field is also used on PTR_TO_SOCKET and PTR_TO_SOCKET_OR_NULL, common
1304 to all copies of the pointer returned from a socket lookup. This has similar
1305 behaviour to the handling for PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE, but
1306 it also handles reference tracking for the pointer. PTR_TO_SOCKET implicitly
1307 represents a reference to the corresponding ``struct sock``. To ensure that the
1308 reference is not leaked, it is imperative to NULL-check the reference and in
1309 the non-NULL case, and pass the valid reference to the socket release function.
1311 Direct packet access
1312 --------------------
1313 In cls_bpf and act_bpf programs the verifier allows direct access to the packet
1314 data via skb->data and skb->data_end pointers.
1317 1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */
1318 2: r3 = *(u32 *)(r1 +76) /* load skb->data */
1321 5: if r5 > r4 goto pc+16
1322 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
1323 6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */
1325 this 2byte load from the packet is safe to do, since the program author
1326 did check ``if (skb->data + 14 > skb->data_end) goto err`` at insn #5 which
1327 means that in the fall-through case the register R3 (which points to skb->data)
1328 has at least 14 directly accessible bytes. The verifier marks it
1329 as R3=pkt(id=0,off=0,r=14).
1330 id=0 means that no additional variables were added to the register.
1331 off=0 means that no additional constants were added.
1332 r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
1333 Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
1334 to the packet data, but constant 14 was added to the register, so
1335 it now points to ``skb->data + 14`` and accessible range is [R5, R5 + 14 - 14)
1336 which is zero bytes.
1338 More complex packet access may look like::
1341 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
1342 6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
1343 7: r4 = *(u8 *)(r3 +12)
1345 9: r3 = *(u32 *)(r1 +76) /* load skb->data */
1353 17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */
1354 18: if r2 > r1 goto pc+2
1355 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
1356 19: r1 = *(u8 *)(r3 +4)
1358 The state of the register R3 is R3=pkt(id=2,off=0,r=8)
1359 id=2 means that two ``r3 += rX`` instructions were seen, so r3 points to some
1360 offset within a packet and since the program author did
1361 ``if (r3 + 8 > r1) goto err`` at insn #18, the safe range is [R3, R3 + 8).
1362 The verifier only allows 'add'/'sub' operations on packet registers. Any other
1363 operation will set the register state to 'SCALAR_VALUE' and it won't be
1364 available for direct packet access.
1366 Operation ``r3 += rX`` may overflow and become less than original skb->data,
1367 therefore the verifier has to prevent that. So when it sees ``r3 += rX``
1368 instruction and rX is more than 16-bit value, any subsequent bounds-check of r3
1369 against skb->data_end will not give us 'range' information, so attempts to read
1370 through the pointer will give "invalid access to packet" error.
1372 Ex. after insn ``r4 = *(u8 *)(r3 +12)`` (insn #7 above) the state of r4 is
1373 R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits
1374 of the register are guaranteed to be zero, and nothing is known about the lower
1375 8 bits. After insn ``r4 *= 14`` the state becomes
1376 R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit
1377 value by constant 14 will keep upper 52 bits as zero, also the least significant
1378 bit will be zero as 14 is even. Similarly ``r2 >>= 48`` will make
1379 R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign
1380 extending. This logic is implemented in adjust_reg_min_max_vals() function,
1381 which calls adjust_ptr_min_max_vals() for adding pointer to scalar (or vice
1382 versa) and adjust_scalar_min_max_vals() for operations on two scalars.
1384 The end result is that bpf program author can access packet directly
1385 using normal C code as::
1387 void *data = (void *)(long)skb->data;
1388 void *data_end = (void *)(long)skb->data_end;
1389 struct eth_hdr *eth = data;
1390 struct iphdr *iph = data + sizeof(*eth);
1391 struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
1393 if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
1395 if (eth->h_proto != htons(ETH_P_IP))
1397 if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
1399 if (udp->dest == 53 || udp->source == 9)
1402 which makes such programs easier to write comparing to LD_ABS insn
1403 and significantly faster.
1407 'maps' is a generic storage of different types for sharing data between kernel
1410 The maps are accessed from user space via BPF syscall, which has commands:
1412 - create a map with given type and attributes
1413 ``map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size)``
1414 using attr->map_type, attr->key_size, attr->value_size, attr->max_entries
1415 returns process-local file descriptor or negative error
1417 - lookup key in a given map
1418 ``err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size)``
1419 using attr->map_fd, attr->key, attr->value
1420 returns zero and stores found elem into value or negative error
1422 - create or update key/value pair in a given map
1423 ``err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size)``
1424 using attr->map_fd, attr->key, attr->value
1425 returns zero or negative error
1427 - find and delete element by key in a given map
1428 ``err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size)``
1429 using attr->map_fd, attr->key
1431 - to delete map: close(fd)
1432 Exiting process will delete maps automatically
1434 userspace programs use this syscall to create/access maps that eBPF programs
1435 are concurrently updating.
1437 maps can have different types: hash, array, bloom filter, radix-tree, etc.
1439 The map is defined by:
1442 - max number of elements
1444 - value size in bytes
1448 The verifier does not actually walk all possible paths through the program. For
1449 each new branch to analyse, the verifier looks at all the states it's previously
1450 been in when at this instruction. If any of them contain the current state as a
1451 subset, the branch is 'pruned' - that is, the fact that the previous state was
1452 accepted implies the current state would be as well. For instance, if in the
1453 previous state, r1 held a packet-pointer, and in the current state, r1 holds a
1454 packet-pointer with a range as long or longer and at least as strict an
1455 alignment, then r1 is safe. Similarly, if r2 was NOT_INIT before then it can't
1456 have been used by any path from that point, so any value in r2 (including
1457 another NOT_INIT) is safe. The implementation is in the function regsafe().
1458 Pruning considers not only the registers but also the stack (and any spilled
1459 registers it may hold). They must all be safe for the branch to be pruned.
1460 This is implemented in states_equal().
1462 Understanding eBPF verifier messages
1463 ------------------------------------
1465 The following are few examples of invalid eBPF programs and verifier error
1466 messages as seen in the log:
1468 Program with unreachable instructions::
1470 static struct bpf_insn prog[] = {
1479 Program that reads uninitialized register::
1481 BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
1489 Program that doesn't initialize R0 before exiting::
1491 BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
1500 Program that accesses stack out of bounds::
1502 BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
1507 0: (7a) *(u64 *)(r10 +8) = 0
1508 invalid stack off=8 size=8
1510 Program that doesn't initialize stack before passing its address into function::
1512 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1513 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1514 BPF_LD_MAP_FD(BPF_REG_1, 0),
1515 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1524 invalid indirect read from stack off -8+0 size 8
1526 Program that uses invalid map_fd=0 while calling to map_lookup_elem() function::
1528 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1529 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1530 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1531 BPF_LD_MAP_FD(BPF_REG_1, 0),
1532 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1537 0: (7a) *(u64 *)(r10 -8) = 0
1542 fd 0 is not pointing to valid bpf_map
1544 Program that doesn't check return value of map_lookup_elem() before accessing
1547 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1548 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1549 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1550 BPF_LD_MAP_FD(BPF_REG_1, 0),
1551 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1552 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1557 0: (7a) *(u64 *)(r10 -8) = 0
1562 5: (7a) *(u64 *)(r0 +0) = 0
1563 R0 invalid mem access 'map_value_or_null'
1565 Program that correctly checks map_lookup_elem() returned value for NULL, but
1566 accesses the memory with incorrect alignment::
1568 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1569 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1570 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1571 BPF_LD_MAP_FD(BPF_REG_1, 0),
1572 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1573 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
1574 BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
1579 0: (7a) *(u64 *)(r10 -8) = 0
1584 5: (15) if r0 == 0x0 goto pc+1
1586 6: (7a) *(u64 *)(r0 +4) = 0
1587 misaligned access off 4 size 8
1589 Program that correctly checks map_lookup_elem() returned value for NULL and
1590 accesses memory with correct alignment in one side of 'if' branch, but fails
1591 to do so in the other side of 'if' branch::
1593 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1594 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1595 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1596 BPF_LD_MAP_FD(BPF_REG_1, 0),
1597 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1598 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
1599 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1601 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
1606 0: (7a) *(u64 *)(r10 -8) = 0
1611 5: (15) if r0 == 0x0 goto pc+2
1613 6: (7a) *(u64 *)(r0 +0) = 0
1616 from 5 to 8: R0=imm0 R10=fp
1617 8: (7a) *(u64 *)(r0 +0) = 1
1618 R0 invalid mem access 'imm'
1620 Program that performs a socket lookup then sets the pointer to NULL without
1623 BPF_MOV64_IMM(BPF_REG_2, 0),
1624 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
1625 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1626 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1627 BPF_MOV64_IMM(BPF_REG_3, 4),
1628 BPF_MOV64_IMM(BPF_REG_4, 0),
1629 BPF_MOV64_IMM(BPF_REG_5, 0),
1630 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
1631 BPF_MOV64_IMM(BPF_REG_0, 0),
1637 1: (63) *(u32 *)(r10 -8) = r2
1643 7: (85) call bpf_sk_lookup_tcp#65
1646 Unreleased reference id=1, alloc_insn=7
1648 Program that performs a socket lookup but does not NULL-check the returned
1651 BPF_MOV64_IMM(BPF_REG_2, 0),
1652 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
1653 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1654 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1655 BPF_MOV64_IMM(BPF_REG_3, 4),
1656 BPF_MOV64_IMM(BPF_REG_4, 0),
1657 BPF_MOV64_IMM(BPF_REG_5, 0),
1658 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
1664 1: (63) *(u32 *)(r10 -8) = r2
1670 7: (85) call bpf_sk_lookup_tcp#65
1672 Unreleased reference id=1, alloc_insn=7
1677 Next to the BPF toolchain, the kernel also ships a test module that contains
1678 various test cases for classic and internal BPF that can be executed against
1679 the BPF interpreter and JIT compiler. It can be found in lib/test_bpf.c and
1680 enabled via Kconfig::
1684 After the module has been built and installed, the test suite can be executed
1685 via insmod or modprobe against 'test_bpf' module. Results of the test cases
1686 including timings in nsec can be found in the kernel log (dmesg).
1691 Also trinity, the Linux syscall fuzzer, has built-in support for BPF and
1692 SECCOMP-BPF kernel fuzzing.
1697 The document was written in the hope that it is found useful and in order
1698 to give potential BPF hackers or security auditors a better overview of
1699 the underlying architecture.
1701 - Jay Schulist <jschlst@samba.org>
1702 - Daniel Borkmann <daniel@iogearbox.net>
1703 - Alexei Starovoitov <ast@kernel.org>