| blob | 319e5e041f3808b3f0b77fcc4f6c511b4918144b |
1 Linux Socket Filtering aka Berkeley Packet Filter (BPF)
2 =======================================================
4 Introduction
5 ------------
7 Linux Socket Filtering (LSF) is derived from the Berkeley Packet Filter.
8 Though there are some distinct differences between the BSD and Linux
9 Kernel filtering, but when we speak of BPF or LSF in Linux context, we
10 mean the very same mechanism of filtering in the Linux kernel.
12 BPF allows a user-space program to attach a filter onto any socket and
13 allow or disallow certain types of data to come through the socket. LSF
14 follows exactly the same filter code structure as BSD's BPF, so referring
15 to the BSD bpf.4 manpage is very helpful in creating filters.
17 On Linux, BPF is much simpler than on BSD. One does not have to worry
18 about devices or anything like that. You simply create your filter code,
19 send it to the kernel via the SO_ATTACH_FILTER option and if your filter
20 code passes the kernel check on it, you then immediately begin filtering
21 data on that socket.
23 You can also detach filters from your socket via the SO_DETACH_FILTER
24 option. This will probably not be used much since when you close a socket
25 that has a filter on it the filter is automagically removed. The other
26 less common case may be adding a different filter on the same socket where
27 you had another filter that is still running: the kernel takes care of
28 removing the old one and placing your new one in its place, assuming your
29 filter has passed the checks, otherwise if it fails the old filter will
30 remain on that socket.
32 SO_LOCK_FILTER option allows to lock the filter attached to a socket. Once
33 set, a filter cannot be removed or changed. This allows one process to
34 setup a socket, attach a filter, lock it then drop privileges and be
35 assured that the filter will be kept until the socket is closed.
37 The biggest user of this construct might be libpcap. Issuing a high-level
38 filter command like `tcpdump -i em1 port 22` passes through the libpcap
39 internal compiler that generates a structure that can eventually be loaded
40 via SO_ATTACH_FILTER to the kernel. `tcpdump -i em1 port 22 -ddd`
41 displays what is being placed into this structure.
43 Although we were only speaking about sockets here, BPF in Linux is used
44 in many more places. There's xt_bpf for netfilter, cls_bpf in the kernel
45 qdisc layer, SECCOMP-BPF (SECure COMPuting [1]), and lots of other places
46 such as team driver, PTP code, etc where BPF is being used.
48 [1] Documentation/userspace-api/seccomp_filter.rst
50 Original BPF paper:
52 Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
53 architecture for user-level packet capture. In Proceedings of the
54 USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
55 Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
56 CA, USA, 2-2. [http://www.tcpdump.org/papers/bpf-usenix93.pdf]
58 Structure
59 ---------
61 User space applications include <linux/filter.h> which contains the
62 following relevant structures:
64 struct sock_filter { /* Filter block */
65 __u16 code; /* Actual filter code */
66 __u8 jt; /* Jump true */
67 __u8 jf; /* Jump false */
68 __u32 k; /* Generic multiuse field */
69 };
71 Such a structure is assembled as an array of 4-tuples, that contains
72 a code, jt, jf and k value. jt and jf are jump offsets and k a generic
73 value to be used for a provided code.
75 struct sock_fprog { /* Required for SO_ATTACH_FILTER. */
76 unsigned short len; /* Number of filter blocks */
77 struct sock_filter __user *filter;
78 };
80 For socket filtering, a pointer to this structure (as shown in
81 follow-up example) is being passed to the kernel through setsockopt(2).
83 Example
84 -------
86 #include <sys/socket.h>
87 #include <sys/types.h>
88 #include <arpa/inet.h>
89 #include <linux/if_ether.h>
90 /* ... */
92 /* From the example above: tcpdump -i em1 port 22 -dd */
93 struct sock_filter code[] = {
94 { 0x28, 0, 0, 0x0000000c },
95 { 0x15, 0, 8, 0x000086dd },
96 { 0x30, 0, 0, 0x00000014 },
97 { 0x15, 2, 0, 0x00000084 },
98 { 0x15, 1, 0, 0x00000006 },
99 { 0x15, 0, 17, 0x00000011 },
100 { 0x28, 0, 0, 0x00000036 },
101 { 0x15, 14, 0, 0x00000016 },
102 { 0x28, 0, 0, 0x00000038 },
103 { 0x15, 12, 13, 0x00000016 },
104 { 0x15, 0, 12, 0x00000800 },
105 { 0x30, 0, 0, 0x00000017 },
106 { 0x15, 2, 0, 0x00000084 },
107 { 0x15, 1, 0, 0x00000006 },
108 { 0x15, 0, 8, 0x00000011 },
109 { 0x28, 0, 0, 0x00000014 },
110 { 0x45, 6, 0, 0x00001fff },
111 { 0xb1, 0, 0, 0x0000000e },
112 { 0x48, 0, 0, 0x0000000e },
113 { 0x15, 2, 0, 0x00000016 },
114 { 0x48, 0, 0, 0x00000010 },
115 { 0x15, 0, 1, 0x00000016 },
116 { 0x06, 0, 0, 0x0000ffff },
117 { 0x06, 0, 0, 0x00000000 },
118 };
120 struct sock_fprog bpf = {
121 .len = ARRAY_SIZE(code),
122 .filter = code,
123 };
125 sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
126 if (sock < 0)
127 /* ... bail out ... */
129 ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));
130 if (ret < 0)
131 /* ... bail out ... */
133 /* ... */
134 close(sock);
136 The above example code attaches a socket filter for a PF_PACKET socket
137 in order to let all IPv4/IPv6 packets with port 22 pass. The rest will
138 be dropped for this socket.
140 The setsockopt(2) call to SO_DETACH_FILTER doesn't need any arguments
141 and SO_LOCK_FILTER for preventing the filter to be detached, takes an
142 integer value with 0 or 1.
144 Note that socket filters are not restricted to PF_PACKET sockets only,
145 but can also be used on other socket families.
147 Summary of system calls:
149 * setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &val, sizeof(val));
150 * setsockopt(sockfd, SOL_SOCKET, SO_DETACH_FILTER, &val, sizeof(val));
151 * setsockopt(sockfd, SOL_SOCKET, SO_LOCK_FILTER, &val, sizeof(val));
153 Normally, most use cases for socket filtering on packet sockets will be
154 covered by libpcap in high-level syntax, so as an application developer
155 you should stick to that. libpcap wraps its own layer around all that.
157 Unless i) using/linking to libpcap is not an option, ii) the required BPF
158 filters use Linux extensions that are not supported by libpcap's compiler,
159 iii) a filter might be more complex and not cleanly implementable with
160 libpcap's compiler, or iv) particular filter codes should be optimized
161 differently than libpcap's internal compiler does; then in such cases
162 writing such a filter "by hand" can be of an alternative. For example,
163 xt_bpf and cls_bpf users might have requirements that could result in
164 more complex filter code, or one that cannot be expressed with libpcap
165 (e.g. different return codes for various code paths). Moreover, BPF JIT
166 implementors may wish to manually write test cases and thus need low-level
167 access to BPF code as well.
169 BPF engine and instruction set
170 ------------------------------
172 Under tools/bpf/ there's a small helper tool called bpf_asm which can
173 be used to write low-level filters for example scenarios mentioned in the
174 previous section. Asm-like syntax mentioned here has been implemented in
175 bpf_asm and will be used for further explanations (instead of dealing with
176 less readable opcodes directly, principles are the same). The syntax is
177 closely modelled after Steven McCanne's and Van Jacobson's BPF paper.
179 The BPF architecture consists of the following basic elements:
181 Element Description
183 A 32 bit wide accumulator
184 X 32 bit wide X register
185 M[] 16 x 32 bit wide misc registers aka "scratch memory
186 store", addressable from 0 to 15
188 A program, that is translated by bpf_asm into "opcodes" is an array that
189 consists of the following elements (as already mentioned):
191 op:16, jt:8, jf:8, k:32
193 The element op is a 16 bit wide opcode that has a particular instruction
194 encoded. jt and jf are two 8 bit wide jump targets, one for condition
195 "jump if true", the other one "jump if false". Eventually, element k
196 contains a miscellaneous argument that can be interpreted in different
197 ways depending on the given instruction in op.
199 The instruction set consists of load, store, branch, alu, miscellaneous
200 and return instructions that are also represented in bpf_asm syntax. This
201 table lists all bpf_asm instructions available resp. what their underlying
202 opcodes as defined in linux/filter.h stand for:
204 Instruction Addressing mode Description
206 ld 1, 2, 3, 4, 12 Load word into A
207 ldi 4 Load word into A
208 ldh 1, 2 Load half-word into A
209 ldb 1, 2 Load byte into A
210 ldx 3, 4, 5, 12 Load word into X
211 ldxi 4 Load word into X
212 ldxb 5 Load byte into X
214 st 3 Store A into M[]
215 stx 3 Store X into M[]
217 jmp 6 Jump to label
218 ja 6 Jump to label
219 jeq 7, 8, 9, 10 Jump on A == <x>
220 jneq 9, 10 Jump on A != <x>
221 jne 9, 10 Jump on A != <x>
222 jlt 9, 10 Jump on A < <x>
223 jle 9, 10 Jump on A <= <x>
224 jgt 7, 8, 9, 10 Jump on A > <x>
225 jge 7, 8, 9, 10 Jump on A >= <x>
226 jset 7, 8, 9, 10 Jump on A & <x>
228 add 0, 4 A + <x>
229 sub 0, 4 A - <x>
230 mul 0, 4 A * <x>
231 div 0, 4 A / <x>
232 mod 0, 4 A % <x>
233 neg !A
234 and 0, 4 A & <x>
235 or 0, 4 A | <x>
236 xor 0, 4 A ^ <x>
237 lsh 0, 4 A << <x>
238 rsh 0, 4 A >> <x>
240 tax Copy A into X
241 txa Copy X into A
243 ret 4, 11 Return
245 The next table shows addressing formats from the 2nd column:
247 Addressing mode Syntax Description
249 0 x/%x Register X
250 1 [k] BHW at byte offset k in the packet
251 2 [x + k] BHW at the offset X + k in the packet
252 3 M[k] Word at offset k in M[]
253 4 #k Literal value stored in k
254 5 4*([k]&0xf) Lower nibble * 4 at byte offset k in the packet
255 6 L Jump label L
256 7 #k,Lt,Lf Jump to Lt if true, otherwise jump to Lf
257 8 x/%x,Lt,Lf Jump to Lt if true, otherwise jump to Lf
258 9 #k,Lt Jump to Lt if predicate is true
259 10 x/%x,Lt Jump to Lt if predicate is true
260 11 a/%a Accumulator A
261 12 extension BPF extension
263 The Linux kernel also has a couple of BPF extensions that are used along
264 with the class of load instructions by "overloading" the k argument with
265 a negative offset + a particular extension offset. The result of such BPF
266 extensions are loaded into A.
268 Possible BPF extensions are shown in the following table:
270 Extension Description
272 len skb->len
273 proto skb->protocol
274 type skb->pkt_type
275 poff Payload start offset
276 ifidx skb->dev->ifindex
277 nla Netlink attribute of type X with offset A
278 nlan Nested Netlink attribute of type X with offset A
279 mark skb->mark
280 queue skb->queue_mapping
281 hatype skb->dev->type
282 rxhash skb->hash
283 cpu raw_smp_processor_id()
284 vlan_tci skb_vlan_tag_get(skb)
285 vlan_avail skb_vlan_tag_present(skb)
286 vlan_tpid skb->vlan_proto
287 rand prandom_u32()
289 These extensions can also be prefixed with '#'.
290 Examples for low-level BPF:
292 ** ARP packets:
294 ldh [12]
295 jne #0x806, drop
296 ret #-1
297 drop: ret #0
299 ** IPv4 TCP packets:
301 ldh [12]
302 jne #0x800, drop
303 ldb [23]
304 jneq #6, drop
305 ret #-1
306 drop: ret #0
308 ** (Accelerated) VLAN w/ id 10:
310 ld vlan_tci
311 jneq #10, drop
312 ret #-1
313 drop: ret #0
315 ** icmp random packet sampling, 1 in 4
316 ldh [12]
317 jne #0x800, drop
318 ldb [23]
319 jneq #1, drop
320 # get a random uint32 number
321 ld rand
322 mod #4
323 jneq #1, drop
324 ret #-1
325 drop: ret #0
327 ** SECCOMP filter example:
329 ld [4] /* offsetof(struct seccomp_data, arch) */
330 jne #0xc000003e, bad /* AUDIT_ARCH_X86_64 */
331 ld [0] /* offsetof(struct seccomp_data, nr) */
332 jeq #15, good /* __NR_rt_sigreturn */
333 jeq #231, good /* __NR_exit_group */
334 jeq #60, good /* __NR_exit */
335 jeq #0, good /* __NR_read */
336 jeq #1, good /* __NR_write */
337 jeq #5, good /* __NR_fstat */
338 jeq #9, good /* __NR_mmap */
339 jeq #14, good /* __NR_rt_sigprocmask */
340 jeq #13, good /* __NR_rt_sigaction */
341 jeq #35, good /* __NR_nanosleep */
342 bad: ret #0 /* SECCOMP_RET_KILL_THREAD */
343 good: ret #0x7fff0000 /* SECCOMP_RET_ALLOW */
345 The above example code can be placed into a file (here called "foo"), and
346 then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf
347 and cls_bpf understands and can directly be loaded with. Example with above
348 ARP code:
350 $ ./bpf_asm foo
351 4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,
353 In copy and paste C-like output:
355 $ ./bpf_asm -c foo
356 { 0x28, 0, 0, 0x0000000c },
357 { 0x15, 0, 1, 0x00000806 },
358 { 0x06, 0, 0, 0xffffffff },
359 { 0x06, 0, 0, 0000000000 },
361 In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF
362 filters that might not be obvious at first, it's good to test filters before
363 attaching to a live system. For that purpose, there's a small tool called
364 bpf_dbg under tools/bpf/ in the kernel source directory. This debugger allows
365 for testing BPF filters against given pcap files, single stepping through the
366 BPF code on the pcap's packets and to do BPF machine register dumps.
368 Starting bpf_dbg is trivial and just requires issuing:
370 # ./bpf_dbg
372 In case input and output do not equal stdin/stdout, bpf_dbg takes an
373 alternative stdin source as a first argument, and an alternative stdout
374 sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`.
376 Other than that, a particular libreadline configuration can be set via
377 file "~/.bpf_dbg_init" and the command history is stored in the file
378 "~/.bpf_dbg_history".
380 Interaction in bpf_dbg happens through a shell that also has auto-completion
381 support (follow-up example commands starting with '>' denote bpf_dbg shell).
382 The usual workflow would be to ...
384 > 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
385 Loads a BPF filter from standard output of bpf_asm, or transformed via
386 e.g. `tcpdump -iem1 -ddd port 22 | tr '\n' ','`. Note that for JIT
387 debugging (next section), this command creates a temporary socket and
388 loads the BPF code into the kernel. Thus, this will also be useful for
389 JIT developers.
391 > load pcap foo.pcap
392 Loads standard tcpdump pcap file.
394 > run [<n>]
395 bpf passes:1 fails:9
396 Runs through all packets from a pcap to account how many passes and fails
397 the filter will generate. A limit of packets to traverse can be given.
399 > disassemble
400 l0: ldh [12]
401 l1: jeq #0x800, l2, l5
402 l2: ldb [23]
403 l3: jeq #0x1, l4, l5
404 l4: ret #0xffff
405 l5: ret #0
406 Prints out BPF code disassembly.
408 > dump
409 /* { op, jt, jf, k }, */
410 { 0x28, 0, 0, 0x0000000c },
411 { 0x15, 0, 3, 0x00000800 },
412 { 0x30, 0, 0, 0x00000017 },
413 { 0x15, 0, 1, 0x00000001 },
414 { 0x06, 0, 0, 0x0000ffff },
415 { 0x06, 0, 0, 0000000000 },
416 Prints out C-style BPF code dump.
418 > breakpoint 0
419 breakpoint at: l0: ldh [12]
420 > breakpoint 1
421 breakpoint at: l1: jeq #0x800, l2, l5
422 ...
423 Sets breakpoints at particular BPF instructions. Issuing a `run` command
424 will walk through the pcap file continuing from the current packet and
425 break when a breakpoint is being hit (another `run` will continue from
426 the currently active breakpoint executing next instructions):
428 > run
429 -- register dump --
430 pc: [0] <-- program counter
431 code: [40] jt[0] jf[0] k[12] <-- plain BPF code of current instruction
432 curr: l0: ldh [12] <-- disassembly of current instruction
433 A: [00000000][0] <-- content of A (hex, decimal)
434 X: [00000000][0] <-- content of X (hex, decimal)
435 M[0,15]: [00000000][0] <-- folded content of M (hex, decimal)
436 -- packet dump -- <-- Current packet from pcap (hex)
437 len: 42
438 0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
439 16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
440 32: 00 00 00 00 00 00 0a 3b 01 01
441 (breakpoint)
442 >
444 > breakpoint
445 breakpoints: 0 1
446 Prints currently set breakpoints.
448 > step [-<n>, +<n>]
449 Performs single stepping through the BPF program from the current pc
450 offset. Thus, on each step invocation, above register dump is issued.
451 This can go forwards and backwards in time, a plain `step` will break
452 on the next BPF instruction, thus +1. (No `run` needs to be issued here.)
454 > select <n>
455 Selects a given packet from the pcap file to continue from. Thus, on
456 the next `run` or `step`, the BPF program is being evaluated against
457 the user pre-selected packet. Numbering starts just as in Wireshark
458 with index 1.
460 > quit
461 #
462 Exits bpf_dbg.
464 JIT compiler
465 ------------
467 The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC,
468 PowerPC, ARM, ARM64, MIPS, RISC-V and s390 and can be enabled through
469 CONFIG_BPF_JIT. The JIT compiler is transparently invoked for each
470 attached filter from user space or for internal kernel users if it has
471 been previously enabled by root:
473 echo 1 > /proc/sys/net/core/bpf_jit_enable
475 For JIT developers, doing audits etc, each compile run can output the generated
476 opcode image into the kernel log via:
478 echo 2 > /proc/sys/net/core/bpf_jit_enable
480 Example output from dmesg:
482 [ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
483 [ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
484 [ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
485 [ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
486 [ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
487 [ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3
489 When CONFIG_BPF_JIT_ALWAYS_ON is enabled, bpf_jit_enable is permanently set to 1 and
490 setting any other value than that will return in failure. This is even the case for
491 setting bpf_jit_enable to 2, since dumping the final JIT image into the kernel log
492 is discouraged and introspection through bpftool (under tools/bpf/bpftool/) is the
493 generally recommended approach instead.
495 In the kernel source tree under tools/bpf/, there's bpf_jit_disasm for
496 generating disassembly out of the kernel log's hexdump:
498 # ./bpf_jit_disasm
499 70 bytes emitted from JIT compiler (pass:3, flen:6)
500 ffffffffa0069c8f + <x>:
501 0: push %rbp
502 1: mov %rsp,%rbp
503 4: sub $0x60,%rsp
504 8: mov %rbx,-0x8(%rbp)
505 c: mov 0x68(%rdi),%r9d
506 10: sub 0x6c(%rdi),%r9d
507 14: mov 0xd8(%rdi),%r8
508 1b: mov $0xc,%esi
509 20: callq 0xffffffffe0ff9442
510 25: cmp $0x800,%eax
511 2a: jne 0x0000000000000042
512 2c: mov $0x17,%esi
513 31: callq 0xffffffffe0ff945e
514 36: cmp $0x1,%eax
515 39: jne 0x0000000000000042
516 3b: mov $0xffff,%eax
517 40: jmp 0x0000000000000044
518 42: xor %eax,%eax
519 44: leaveq
520 45: retq
522 Issuing option `-o` will "annotate" opcodes to resulting assembler
523 instructions, which can be very useful for JIT developers:
525 # ./bpf_jit_disasm -o
526 70 bytes emitted from JIT compiler (pass:3, flen:6)
527 ffffffffa0069c8f + <x>:
528 0: push %rbp
529 55
530 1: mov %rsp,%rbp
531 48 89 e5
532 4: sub $0x60,%rsp
533 48 83 ec 60
534 8: mov %rbx,-0x8(%rbp)
535 48 89 5d f8
536 c: mov 0x68(%rdi),%r9d
537 44 8b 4f 68
538 10: sub 0x6c(%rdi),%r9d
539 44 2b 4f 6c
540 14: mov 0xd8(%rdi),%r8
541 4c 8b 87 d8 00 00 00
542 1b: mov $0xc,%esi
543 be 0c 00 00 00
544 20: callq 0xffffffffe0ff9442
545 e8 1d 94 ff e0
546 25: cmp $0x800,%eax
547 3d 00 08 00 00
548 2a: jne 0x0000000000000042
549 75 16
550 2c: mov $0x17,%esi
551 be 17 00 00 00
552 31: callq 0xffffffffe0ff945e
553 e8 28 94 ff e0
554 36: cmp $0x1,%eax
555 83 f8 01
556 39: jne 0x0000000000000042
557 75 07
558 3b: mov $0xffff,%eax
559 b8 ff ff 00 00
560 40: jmp 0x0000000000000044
561 eb 02
562 42: xor %eax,%eax
563 31 c0
564 44: leaveq
565 c9
566 45: retq
567 c3
569 For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful
570 toolchain for developing and testing the kernel's JIT compiler.
572 BPF kernel internals
573 --------------------
574 Internally, for the kernel interpreter, a different instruction set
575 format with similar underlying principles from BPF described in previous
576 paragraphs is being used. However, the instruction set format is modelled
577 closer to the underlying architecture to mimic native instruction sets, so
578 that a better performance can be achieved (more details later). This new
579 ISA is called 'eBPF' or 'internal BPF' interchangeably. (Note: eBPF which
580 originates from [e]xtended BPF is not the same as BPF extensions! While
581 eBPF is an ISA, BPF extensions date back to classic BPF's 'overloading'
582 of BPF_LD | BPF_{B,H,W} | BPF_ABS instruction.)
584 It is designed to be JITed with one to one mapping, which can also open up
585 the possibility for GCC/LLVM compilers to generate optimized eBPF code through
586 an eBPF backend that performs almost as fast as natively compiled code.
588 The new instruction set was originally designed with the possible goal in
589 mind to write programs in "restricted C" and compile into eBPF with a optional
590 GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with
591 minimal performance overhead over two steps, that is, C -> eBPF -> native code.
593 Currently, the new format is being used for running user BPF programs, which
594 includes seccomp BPF, classic socket filters, cls_bpf traffic classifier,
595 team driver's classifier for its load-balancing mode, netfilter's xt_bpf
596 extension, PTP dissector/classifier, and much more. They are all internally
597 converted by the kernel into the new instruction set representation and run
598 in the eBPF interpreter. For in-kernel handlers, this all works transparently
599 by using bpf_prog_create() for setting up the filter, resp.
600 bpf_prog_destroy() for destroying it. The macro
601 BPF_PROG_RUN(filter, ctx) transparently invokes eBPF interpreter or JITed
602 code to run the filter. 'filter' is a pointer to struct bpf_prog that we
603 got from bpf_prog_create(), and 'ctx' the given context (e.g.
604 skb pointer). All constraints and restrictions from bpf_check_classic() apply
605 before a conversion to the new layout is being done behind the scenes!
607 Currently, the classic BPF format is being used for JITing on most
608 32-bit architectures, whereas x86-64, aarch64, s390x, powerpc64,
609 sparc64, arm32, riscv (RV64G) perform JIT compilation from eBPF
610 instruction set.
612 Some core changes of the new internal format:
614 - Number of registers increase from 2 to 10:
616 The old format had two registers A and X, and a hidden frame pointer. The
617 new layout extends this to be 10 internal registers and a read-only frame
618 pointer. Since 64-bit CPUs are passing arguments to functions via registers
619 the number of args from eBPF program to in-kernel function is restricted
620 to 5 and one register is used to accept return value from an in-kernel
621 function. Natively, x86_64 passes first 6 arguments in registers, aarch64/
622 sparcv9/mips64 have 7 - 8 registers for arguments; x86_64 has 6 callee saved
623 registers, and aarch64/sparcv9/mips64 have 11 or more callee saved registers.
625 Therefore, eBPF calling convention is defined as:
627 * R0 - return value from in-kernel function, and exit value for eBPF program
628 * R1 - R5 - arguments from eBPF program to in-kernel function
629 * R6 - R9 - callee saved registers that in-kernel function will preserve
630 * R10 - read-only frame pointer to access stack
632 Thus, all eBPF registers map one to one to HW registers on x86_64, aarch64,
633 etc, and eBPF calling convention maps directly to ABIs used by the kernel on
634 64-bit architectures.
636 On 32-bit architectures JIT may map programs that use only 32-bit arithmetic
637 and may let more complex programs to be interpreted.
639 R0 - R5 are scratch registers and eBPF program needs spill/fill them if
640 necessary across calls. Note that there is only one eBPF program (== one
641 eBPF main routine) and it cannot call other eBPF functions, it can only
642 call predefined in-kernel functions, though.
644 - Register width increases from 32-bit to 64-bit:
646 Still, the semantics of the original 32-bit ALU operations are preserved
647 via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower
648 subregisters that zero-extend into 64-bit if they are being written to.
649 That behavior maps directly to x86_64 and arm64 subregister definition, but
650 makes other JITs more difficult.
652 32-bit architectures run 64-bit internal BPF programs via interpreter.
653 Their JITs may convert BPF programs that only use 32-bit subregisters into
654 native instruction set and let the rest being interpreted.
656 Operation is 64-bit, because on 64-bit architectures, pointers are also
657 64-bit wide, and we want to pass 64-bit values in/out of kernel functions,
658 so 32-bit eBPF registers would otherwise require to define register-pair
659 ABI, thus, there won't be able to use a direct eBPF register to HW register
660 mapping and JIT would need to do combine/split/move operations for every
661 register in and out of the function, which is complex, bug prone and slow.
662 Another reason is the use of atomic 64-bit counters.
664 - Conditional jt/jf targets replaced with jt/fall-through:
666 While the original design has constructs such as "if (cond) jump_true;
667 else jump_false;", they are being replaced into alternative constructs like
668 "if (cond) jump_true; /* else fall-through */".
670 - Introduces bpf_call insn and register passing convention for zero overhead
671 calls from/to other kernel functions:
673 Before an in-kernel function call, the internal BPF program needs to
674 place function arguments into R1 to R5 registers to satisfy calling
675 convention, then the interpreter will take them from registers and pass
676 to in-kernel function. If R1 - R5 registers are mapped to CPU registers
677 that are used for argument passing on given architecture, the JIT compiler
678 doesn't need to emit extra moves. Function arguments will be in the correct
679 registers and BPF_CALL instruction will be JITed as single 'call' HW
680 instruction. This calling convention was picked to cover common call
681 situations without performance penalty.
683 After an in-kernel function call, R1 - R5 are reset to unreadable and R0 has
684 a return value of the function. Since R6 - R9 are callee saved, their state
685 is preserved across the call.
687 For example, consider three C functions:
689 u64 f1() { return (*_f2)(1); }
690 u64 f2(u64 a) { return f3(a + 1, a); }
691 u64 f3(u64 a, u64 b) { return a - b; }
693 GCC can compile f1, f3 into x86_64:
695 f1:
696 movl $1, %edi
697 movq _f2(%rip), %rax
698 jmp *%rax
699 f3:
700 movq %rdi, %rax
701 subq %rsi, %rax
702 ret
704 Function f2 in eBPF may look like:
706 f2:
707 bpf_mov R2, R1
708 bpf_add R1, 1
709 bpf_call f3
710 bpf_exit
712 If f2 is JITed and the pointer stored to '_f2'. The calls f1 -> f2 -> f3 and
713 returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to
714 be used to call into f2.
716 For practical reasons all eBPF programs have only one argument 'ctx' which is
717 already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs
718 can call kernel functions with up to 5 arguments. Calls with 6 or more arguments
719 are currently not supported, but these restrictions can be lifted if necessary
720 in the future.
722 On 64-bit architectures all register map to HW registers one to one. For
723 example, x86_64 JIT compiler can map them as ...
725 R0 - rax
726 R1 - rdi
727 R2 - rsi
728 R3 - rdx
729 R4 - rcx
730 R5 - r8
731 R6 - rbx
732 R7 - r13
733 R8 - r14
734 R9 - r15
735 R10 - rbp
737 ... since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing
738 and rbx, r12 - r15 are callee saved.
740 Then the following internal BPF pseudo-program:
742 bpf_mov R6, R1 /* save ctx */
743 bpf_mov R2, 2
744 bpf_mov R3, 3
745 bpf_mov R4, 4
746 bpf_mov R5, 5
747 bpf_call foo
748 bpf_mov R7, R0 /* save foo() return value */
749 bpf_mov R1, R6 /* restore ctx for next call */
750 bpf_mov R2, 6
751 bpf_mov R3, 7
752 bpf_mov R4, 8
753 bpf_mov R5, 9
754 bpf_call bar
755 bpf_add R0, R7
756 bpf_exit
758 After JIT to x86_64 may look like:
760 push %rbp
761 mov %rsp,%rbp
762 sub $0x228,%rsp
763 mov %rbx,-0x228(%rbp)
764 mov %r13,-0x220(%rbp)
765 mov %rdi,%rbx
766 mov $0x2,%esi
767 mov $0x3,%edx
768 mov $0x4,%ecx
769 mov $0x5,%r8d
770 callq foo
771 mov %rax,%r13
772 mov %rbx,%rdi
773 mov $0x2,%esi
774 mov $0x3,%edx
775 mov $0x4,%ecx
776 mov $0x5,%r8d
777 callq bar
778 add %r13,%rax
779 mov -0x228(%rbp),%rbx
780 mov -0x220(%rbp),%r13
781 leaveq
782 retq
784 Which is in this example equivalent in C to:
786 u64 bpf_filter(u64 ctx)
787 {
788 return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
789 }
791 In-kernel functions foo() and bar() with prototype: u64 (*)(u64 arg1, u64
792 arg2, u64 arg3, u64 arg4, u64 arg5); will receive arguments in proper
793 registers and place their return value into '%rax' which is R0 in eBPF.
794 Prologue and epilogue are emitted by JIT and are implicit in the
795 interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve
796 them across the calls as defined by calling convention.
798 For example the following program is invalid:
800 bpf_mov R1, 1
801 bpf_call foo
802 bpf_mov R0, R1
803 bpf_exit
805 After the call the registers R1-R5 contain junk values and cannot be read.
806 An in-kernel eBPF verifier is used to validate internal BPF programs.
808 Also in the new design, eBPF is limited to 4096 insns, which means that any
809 program will terminate quickly and will only call a fixed number of kernel
810 functions. Original BPF and the new format are two operand instructions,
811 which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT.
813 The input context pointer for invoking the interpreter function is generic,
814 its content is defined by a specific use case. For seccomp register R1 points
815 to seccomp_data, for converted BPF filters R1 points to a skb.
817 A program, that is translated internally consists of the following elements:
819 op:16, jt:8, jf:8, k:32 ==> op:8, dst_reg:4, src_reg:4, off:16, imm:32
821 So far 87 internal BPF instructions were implemented. 8-bit 'op' opcode field
822 has room for new instructions. Some of them may use 16/24/32 byte encoding. New
823 instructions must be multiple of 8 bytes to preserve backward compatibility.
825 Internal BPF is a general purpose RISC instruction set. Not every register and
826 every instruction are used during translation from original BPF to new format.
827 For example, socket filters are not using 'exclusive add' instruction, but
828 tracing filters may do to maintain counters of events, for example. Register R9
829 is not used by socket filters either, but more complex filters may be running
830 out of registers and would have to resort to spill/fill to stack.
832 Internal BPF can be used as a generic assembler for last step performance
833 optimizations, socket filters and seccomp are using it as assembler. Tracing
834 filters may use it as assembler to generate code from kernel. In kernel usage
835 may not be bounded by security considerations, since generated internal BPF code
836 may be optimizing internal code path and not being exposed to the user space.
837 Safety of internal BPF can come from a verifier (TBD). In such use cases as
838 described, it may be used as safe instruction set.
840 Just like the original BPF, the new format runs within a controlled environment,
841 is deterministic and the kernel can easily prove that. The safety of the program
842 can be determined in two steps: first step does depth-first-search to disallow
843 loops and other CFG validation; second step starts from the first insn and
844 descends all possible paths. It simulates execution of every insn and observes
845 the state change of registers and stack.
847 eBPF opcode encoding
848 --------------------
850 eBPF is reusing most of the opcode encoding from classic to simplify conversion
851 of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code'
852 field is divided into three parts:
854 +----------------+--------+--------------------+
855 | 4 bits | 1 bit | 3 bits |
856 | operation code | source | instruction class |
857 +----------------+--------+--------------------+
858 (MSB) (LSB)
860 Three LSB bits store instruction class which is one of:
862 Classic BPF classes: eBPF classes:
864 BPF_LD 0x00 BPF_LD 0x00
865 BPF_LDX 0x01 BPF_LDX 0x01
866 BPF_ST 0x02 BPF_ST 0x02
867 BPF_STX 0x03 BPF_STX 0x03
868 BPF_ALU 0x04 BPF_ALU 0x04
869 BPF_JMP 0x05 BPF_JMP 0x05
870 BPF_RET 0x06 BPF_JMP32 0x06
871 BPF_MISC 0x07 BPF_ALU64 0x07
873 When BPF_CLASS(code) == BPF_ALU or BPF_JMP, 4th bit encodes source operand ...
875 BPF_K 0x00
876 BPF_X 0x08
878 * in classic BPF, this means:
880 BPF_SRC(code) == BPF_X - use register X as source operand
881 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
883 * in eBPF, this means:
885 BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand
886 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
888 ... and four MSB bits store operation code.
890 If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of:
892 BPF_ADD 0x00
893 BPF_SUB 0x10
894 BPF_MUL 0x20
895 BPF_DIV 0x30
896 BPF_OR 0x40
897 BPF_AND 0x50
898 BPF_LSH 0x60
899 BPF_RSH 0x70
900 BPF_NEG 0x80
901 BPF_MOD 0x90
902 BPF_XOR 0xa0
903 BPF_MOV 0xb0 /* eBPF only: mov reg to reg */
904 BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */
905 BPF_END 0xd0 /* eBPF only: endianness conversion */
907 If BPF_CLASS(code) == BPF_JMP or BPF_JMP32 [ in eBPF ], BPF_OP(code) is one of:
909 BPF_JA 0x00 /* BPF_JMP only */
910 BPF_JEQ 0x10
911 BPF_JGT 0x20
912 BPF_JGE 0x30
913 BPF_JSET 0x40
914 BPF_JNE 0x50 /* eBPF only: jump != */
915 BPF_JSGT 0x60 /* eBPF only: signed '>' */
916 BPF_JSGE 0x70 /* eBPF only: signed '>=' */
917 BPF_CALL 0x80 /* eBPF BPF_JMP only: function call */
918 BPF_EXIT 0x90 /* eBPF BPF_JMP only: function return */
919 BPF_JLT 0xa0 /* eBPF only: unsigned '<' */
920 BPF_JLE 0xb0 /* eBPF only: unsigned '<=' */
921 BPF_JSLT 0xc0 /* eBPF only: signed '<' */
922 BPF_JSLE 0xd0 /* eBPF only: signed '<=' */
924 So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF
925 and eBPF. There are only two registers in classic BPF, so it means A += X.
926 In eBPF it means dst_reg = (u32) dst_reg + (u32) src_reg; similarly,
927 BPF_XOR | BPF_K | BPF_ALU means A ^= imm32 in classic BPF and analogous
928 src_reg = (u32) src_reg ^ (u32) imm32 in eBPF.
930 Classic BPF is using BPF_MISC class to represent A = X and X = A moves.
931 eBPF is using BPF_MOV | BPF_X | BPF_ALU code instead. Since there are no
932 BPF_MISC operations in eBPF, the class 7 is used as BPF_ALU64 to mean
933 exactly the same operations as BPF_ALU, but with 64-bit wide operands
934 instead. So BPF_ADD | BPF_X | BPF_ALU64 means 64-bit addition, i.e.:
935 dst_reg = dst_reg + src_reg
937 Classic BPF wastes the whole BPF_RET class to represent a single 'ret'
938 operation. Classic BPF_RET | BPF_K means copy imm32 into return register
939 and perform function exit. eBPF is modeled to match CPU, so BPF_JMP | BPF_EXIT
940 in eBPF means function exit only. The eBPF program needs to store return
941 value into register R0 before doing a BPF_EXIT. Class 6 in eBPF is used as
942 BPF_JMP32 to mean exactly the same operations as BPF_JMP, but with 32-bit wide
943 operands for the comparisons instead.
945 For load and store instructions the 8-bit 'code' field is divided as:
947 +--------+--------+-------------------+
948 | 3 bits | 2 bits | 3 bits |
949 | mode | size | instruction class |
950 +--------+--------+-------------------+
951 (MSB) (LSB)
953 Size modifier is one of ...
955 BPF_W 0x00 /* word */
956 BPF_H 0x08 /* half word */
957 BPF_B 0x10 /* byte */
958 BPF_DW 0x18 /* eBPF only, double word */
960 ... which encodes size of load/store operation:
962 B - 1 byte
963 H - 2 byte
964 W - 4 byte
965 DW - 8 byte (eBPF only)
967 Mode modifier is one of:
969 BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
970 BPF_ABS 0x20
971 BPF_IND 0x40
972 BPF_MEM 0x60
973 BPF_LEN 0x80 /* classic BPF only, reserved in eBPF */
974 BPF_MSH 0xa0 /* classic BPF only, reserved in eBPF */
975 BPF_XADD 0xc0 /* eBPF only, exclusive add */
977 eBPF has two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and
978 (BPF_IND | <size> | BPF_LD) which are used to access packet data.
980 They had to be carried over from classic to have strong performance of
981 socket filters running in eBPF interpreter. These instructions can only
982 be used when interpreter context is a pointer to 'struct sk_buff' and
983 have seven implicit operands. Register R6 is an implicit input that must
984 contain pointer to sk_buff. Register R0 is an implicit output which contains
985 the data fetched from the packet. Registers R1-R5 are scratch registers
986 and must not be used to store the data across BPF_ABS | BPF_LD or
987 BPF_IND | BPF_LD instructions.
989 These instructions have implicit program exit condition as well. When
990 eBPF program is trying to access the data beyond the packet boundary,
991 the interpreter will abort the execution of the program. JIT compilers
992 therefore must preserve this property. src_reg and imm32 fields are
993 explicit inputs to these instructions.
995 For example:
997 BPF_IND | BPF_W | BPF_LD means:
999 R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))
1000 and R1 - R5 were scratched.
1002 Unlike classic BPF instruction set, eBPF has generic load/store operations:
1004 BPF_MEM | <size> | BPF_STX: *(size *) (dst_reg + off) = src_reg
1005 BPF_MEM | <size> | BPF_ST: *(size *) (dst_reg + off) = imm32
1006 BPF_MEM | <size> | BPF_LDX: dst_reg = *(size *) (src_reg + off)
1007 BPF_XADD | BPF_W | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg
1008 BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
1010 Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and
1011 2 byte atomic increments are not supported.
1013 eBPF has one 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM which consists
1014 of two consecutive 'struct bpf_insn' 8-byte blocks and interpreted as single
1015 instruction that loads 64-bit immediate value into a dst_reg.
1016 Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
1017 32-bit immediate value into a register.
1019 eBPF verifier
1020 -------------
1021 The safety of the eBPF program is determined in two steps.
1023 First step does DAG check to disallow loops and other CFG validation.
1024 In particular it will detect programs that have unreachable instructions.
1025 (though classic BPF checker allows them)
1027 Second step starts from the first insn and descends all possible paths.
1028 It simulates execution of every insn and observes the state change of
1029 registers and stack.
1031 At the start of the program the register R1 contains a pointer to context
1032 and has type PTR_TO_CTX.
1033 If verifier sees an insn that does R2=R1, then R2 has now type
1034 PTR_TO_CTX as well and can be used on the right hand side of expression.
1035 If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,
1036 since addition of two valid pointers makes invalid pointer.
1037 (In 'secure' mode verifier will reject any type of pointer arithmetic to make
1038 sure that kernel addresses don't leak to unprivileged users)
1040 If register was never written to, it's not readable:
1041 bpf_mov R0 = R2
1042 bpf_exit
1043 will be rejected, since R2 is unreadable at the start of the program.
1045 After kernel function call, R1-R5 are reset to unreadable and
1046 R0 has a return type of the function.
1048 Since R6-R9 are callee saved, their state is preserved across the call.
1049 bpf_mov R6 = 1
1050 bpf_call foo
1051 bpf_mov R0 = R6
1052 bpf_exit
1053 is a correct program. If there was R1 instead of R6, it would have
1054 been rejected.
1056 load/store instructions are allowed only with registers of valid types, which
1057 are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
1058 For example:
1059 bpf_mov R1 = 1
1060 bpf_mov R2 = 2
1061 bpf_xadd *(u32 *)(R1 + 3) += R2
1062 bpf_exit
1063 will be rejected, since R1 doesn't have a valid pointer type at the time of
1064 execution of instruction bpf_xadd.
1066 At the start R1 type is PTR_TO_CTX (a pointer to generic 'struct bpf_context')
1067 A callback is used to customize verifier to restrict eBPF program access to only
1068 certain fields within ctx structure with specified size and alignment.
1070 For example, the following insn:
1071 bpf_ld R0 = *(u32 *)(R6 + 8)
1072 intends to load a word from address R6 + 8 and store it into R0
1073 If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
1074 that offset 8 of size 4 bytes can be accessed for reading, otherwise
1075 the verifier will reject the program.
1076 If R6=PTR_TO_STACK, then access should be aligned and be within
1077 stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
1078 so it will fail verification, since it's out of bounds.
1080 The verifier will allow eBPF program to read data from stack only after
1081 it wrote into it.
1082 Classic BPF verifier does similar check with M[0-15] memory slots.
1083 For example:
1084 bpf_ld R0 = *(u32 *)(R10 - 4)
1085 bpf_exit
1086 is invalid program.
1087 Though R10 is correct read-only register and has type PTR_TO_STACK
1088 and R10 - 4 is within stack bounds, there were no stores into that location.
1090 Pointer register spill/fill is tracked as well, since four (R6-R9)
1091 callee saved registers may not be enough for some programs.
1093 Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
1094 The eBPF verifier will check that registers match argument constraints.
1095 After the call register R0 will be set to return type of the function.
1097 Function calls is a main mechanism to extend functionality of eBPF programs.
1098 Socket filters may let programs to call one set of functions, whereas tracing
1099 filters may allow completely different set.
1101 If a function made accessible to eBPF program, it needs to be thought through
1102 from safety point of view. The verifier will guarantee that the function is
1103 called with valid arguments.
1105 seccomp vs socket filters have different security restrictions for classic BPF.
1106 Seccomp solves this by two stage verifier: classic BPF verifier is followed
1107 by seccomp verifier. In case of eBPF one configurable verifier is shared for
1108 all use cases.
1110 See details of eBPF verifier in kernel/bpf/verifier.c
1112 Register value tracking
1113 -----------------------
1114 In order to determine the safety of an eBPF program, the verifier must track
1115 the range of possible values in each register and also in each stack slot.
1116 This is done with 'struct bpf_reg_state', defined in include/linux/
1117 bpf_verifier.h, which unifies tracking of scalar and pointer values. Each
1118 register state has a type, which is either NOT_INIT (the register has not been
1119 written to), SCALAR_VALUE (some value which is not usable as a pointer), or a
1120 pointer type. The types of pointers describe their base, as follows:
1121 PTR_TO_CTX Pointer to bpf_context.
1122 CONST_PTR_TO_MAP Pointer to struct bpf_map. "Const" because arithmetic
1123 on these pointers is forbidden.
1124 PTR_TO_MAP_VALUE Pointer to the value stored in a map element.
1125 PTR_TO_MAP_VALUE_OR_NULL
1126 Either a pointer to a map value, or NULL; map accesses
1127 (see section 'eBPF maps', below) return this type,
1128 which becomes a PTR_TO_MAP_VALUE when checked != NULL.
1129 Arithmetic on these pointers is forbidden.
1130 PTR_TO_STACK Frame pointer.
1131 PTR_TO_PACKET skb->data.
1132 PTR_TO_PACKET_END skb->data + headlen; arithmetic forbidden.
1133 PTR_TO_SOCKET Pointer to struct bpf_sock_ops, implicitly refcounted.
1134 PTR_TO_SOCKET_OR_NULL
1135 Either a pointer to a socket, or NULL; socket lookup
1136 returns this type, which becomes a PTR_TO_SOCKET when
1137 checked != NULL. PTR_TO_SOCKET is reference-counted,
1138 so programs must release the reference through the
1139 socket release function before the end of the program.
1140 Arithmetic on these pointers is forbidden.
1141 However, a pointer may be offset from this base (as a result of pointer
1142 arithmetic), and this is tracked in two parts: the 'fixed offset' and 'variable
1143 offset'. The former is used when an exactly-known value (e.g. an immediate
1144 operand) is added to a pointer, while the latter is used for values which are
1145 not exactly known. The variable offset is also used in SCALAR_VALUEs, to track
1146 the range of possible values in the register.
1147 The verifier's knowledge about the variable offset consists of:
1148 * minimum and maximum values as unsigned
1149 * minimum and maximum values as signed
1150 * knowledge of the values of individual bits, in the form of a 'tnum': a u64
1151 'mask' and a u64 'value'. 1s in the mask represent bits whose value is unknown;
1152 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both
1153 mask and value; no bit should ever be 1 in both. For example, if a byte is read
1154 into a register from memory, the register's top 56 bits are known zero, while
1155 the low 8 are unknown - which is represented as the tnum (0x0; 0xff). If we
1156 then OR this with 0x40, we get (0x40; 0xbf), then if we add 1 we get (0x0;
1157 0x1ff), because of potential carries.
1159 Besides arithmetic, the register state can also be updated by conditional
1160 branches. For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch
1161 it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false'
1162 branch it will have a umax_value of 8. A signed compare (with BPF_JSGT or
1163 BPF_JSGE) would instead update the signed minimum/maximum values. Information
1164 from the signed and unsigned bounds can be combined; for instance if a value is
1165 first tested < 8 and then tested s> 4, the verifier will conclude that the value
1166 is also > 4 and s< 8, since the bounds prevent crossing the sign boundary.
1168 PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all
1169 pointers sharing that same variable offset. This is important for packet range
1170 checks: after adding a variable to a packet pointer register A, if you then copy
1171 it to another register B and then add a constant 4 to A, both registers will
1172 share the same 'id' but the A will have a fixed offset of +4. Then if A is
1173 bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is
1174 now known to have a safe range of at least 4 bytes. See 'Direct packet access',
1175 below, for more on PTR_TO_PACKET ranges.
1177 The 'id' field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of
1178 the pointer returned from a map lookup. This means that when one copy is
1179 checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs.
1180 As well as range-checking, the tracked information is also used for enforcing
1181 alignment of pointer accesses. For instance, on most systems the packet pointer
1182 is 2 bytes after a 4-byte alignment. If a program adds 14 bytes to that to jump
1183 over the Ethernet header, then reads IHL and addes (IHL * 4), the resulting
1184 pointer will have a variable offset known to be 4n+2 for some n, so adding the 2
1185 bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through
1186 that pointer are safe.
1187 The 'id' field is also used on PTR_TO_SOCKET and PTR_TO_SOCKET_OR_NULL, common
1188 to all copies of the pointer returned from a socket lookup. This has similar
1189 behaviour to the handling for PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE, but
1190 it also handles reference tracking for the pointer. PTR_TO_SOCKET implicitly
1191 represents a reference to the corresponding 'struct sock'. To ensure that the
1192 reference is not leaked, it is imperative to NULL-check the reference and in
1193 the non-NULL case, and pass the valid reference to the socket release function.
1195 Direct packet access
1196 --------------------
1197 In cls_bpf and act_bpf programs the verifier allows direct access to the packet
1198 data via skb->data and skb->data_end pointers.
1199 Ex:
1200 1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */
1201 2: r3 = *(u32 *)(r1 +76) /* load skb->data */
1202 3: r5 = r3
1203 4: r5 += 14
1204 5: if r5 > r4 goto pc+16
1205 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
1206 6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */
1208 this 2byte load from the packet is safe to do, since the program author
1209 did check 'if (skb->data + 14 > skb->data_end) goto err' at insn #5 which
1210 means that in the fall-through case the register R3 (which points to skb->data)
1211 has at least 14 directly accessible bytes. The verifier marks it
1212 as R3=pkt(id=0,off=0,r=14).
1213 id=0 means that no additional variables were added to the register.
1214 off=0 means that no additional constants were added.
1215 r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
1216 Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
1217 to the packet data, but constant 14 was added to the register, so
1218 it now points to 'skb->data + 14' and accessible range is [R5, R5 + 14 - 14)
1219 which is zero bytes.
1221 More complex packet access may look like:
1222 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
1223 6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
1224 7: r4 = *(u8 *)(r3 +12)
1225 8: r4 *= 14
1226 9: r3 = *(u32 *)(r1 +76) /* load skb->data */
1227 10: r3 += r4
1228 11: r2 = r1
1229 12: r2 <<= 48
1230 13: r2 >>= 48
1231 14: r3 += r2
1232 15: r2 = r3
1233 16: r2 += 8
1234 17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */
1235 18: if r2 > r1 goto pc+2
1236 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
1237 19: r1 = *(u8 *)(r3 +4)
1238 The state of the register R3 is R3=pkt(id=2,off=0,r=8)
1239 id=2 means that two 'r3 += rX' instructions were seen, so r3 points to some
1240 offset within a packet and since the program author did
1241 'if (r3 + 8 > r1) goto err' at insn #18, the safe range is [R3, R3 + 8).
1242 The verifier only allows 'add'/'sub' operations on packet registers. Any other
1243 operation will set the register state to 'SCALAR_VALUE' and it won't be
1244 available for direct packet access.
1245 Operation 'r3 += rX' may overflow and become less than original skb->data,
1246 therefore the verifier has to prevent that. So when it sees 'r3 += rX'
1247 instruction and rX is more than 16-bit value, any subsequent bounds-check of r3
1248 against skb->data_end will not give us 'range' information, so attempts to read
1249 through the pointer will give "invalid access to packet" error.
1250 Ex. after insn 'r4 = *(u8 *)(r3 +12)' (insn #7 above) the state of r4 is
1251 R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits
1252 of the register are guaranteed to be zero, and nothing is known about the lower
1253 8 bits. After insn 'r4 *= 14' the state becomes
1254 R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit
1255 value by constant 14 will keep upper 52 bits as zero, also the least significant
1256 bit will be zero as 14 is even. Similarly 'r2 >>= 48' will make
1257 R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign
1258 extending. This logic is implemented in adjust_reg_min_max_vals() function,
1259 which calls adjust_ptr_min_max_vals() for adding pointer to scalar (or vice
1260 versa) and adjust_scalar_min_max_vals() for operations on two scalars.
1262 The end result is that bpf program author can access packet directly
1263 using normal C code as:
1264 void *data = (void *)(long)skb->data;
1265 void *data_end = (void *)(long)skb->data_end;
1266 struct eth_hdr *eth = data;
1267 struct iphdr *iph = data + sizeof(*eth);
1268 struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
1270 if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
1271 return 0;
1272 if (eth->h_proto != htons(ETH_P_IP))
1273 return 0;
1274 if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
1275 return 0;
1276 if (udp->dest == 53 || udp->source == 9)
1277 ...;
1278 which makes such programs easier to write comparing to LD_ABS insn
1279 and significantly faster.
1281 eBPF maps
1282 ---------
1283 'maps' is a generic storage of different types for sharing data between kernel
1284 and userspace.
1286 The maps are accessed from user space via BPF syscall, which has commands:
1287 - create a map with given type and attributes
1288 map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size)
1289 using attr->map_type, attr->key_size, attr->value_size, attr->max_entries
1290 returns process-local file descriptor or negative error
1292 - lookup key in a given map
1293 err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size)
1294 using attr->map_fd, attr->key, attr->value
1295 returns zero and stores found elem into value or negative error
1297 - create or update key/value pair in a given map
1298 err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size)
1299 using attr->map_fd, attr->key, attr->value
1300 returns zero or negative error
1302 - find and delete element by key in a given map
1303 err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size)
1304 using attr->map_fd, attr->key
1306 - to delete map: close(fd)
1307 Exiting process will delete maps automatically
1309 userspace programs use this syscall to create/access maps that eBPF programs
1310 are concurrently updating.
1312 maps can have different types: hash, array, bloom filter, radix-tree, etc.
1314 The map is defined by:
1315 . type
1316 . max number of elements
1317 . key size in bytes
1318 . value size in bytes
1320 Pruning
1321 -------
1322 The verifier does not actually walk all possible paths through the program. For
1323 each new branch to analyse, the verifier looks at all the states it's previously
1324 been in when at this instruction. If any of them contain the current state as a
1325 subset, the branch is 'pruned' - that is, the fact that the previous state was
1326 accepted implies the current state would be as well. For instance, if in the
1327 previous state, r1 held a packet-pointer, and in the current state, r1 holds a
1328 packet-pointer with a range as long or longer and at least as strict an
1329 alignment, then r1 is safe. Similarly, if r2 was NOT_INIT before then it can't
1330 have been used by any path from that point, so any value in r2 (including
1331 another NOT_INIT) is safe. The implementation is in the function regsafe().
1332 Pruning considers not only the registers but also the stack (and any spilled
1333 registers it may hold). They must all be safe for the branch to be pruned.
1334 This is implemented in states_equal().
1336 Understanding eBPF verifier messages
1337 ------------------------------------
1339 The following are few examples of invalid eBPF programs and verifier error
1340 messages as seen in the log:
1342 Program with unreachable instructions:
1343 static struct bpf_insn prog[] = {
1344 BPF_EXIT_INSN(),
1345 BPF_EXIT_INSN(),
1346 };
1347 Error:
1348 unreachable insn 1
1350 Program that reads uninitialized register:
1351 BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
1352 BPF_EXIT_INSN(),
1353 Error:
1354 0: (bf) r0 = r2
1355 R2 !read_ok
1357 Program that doesn't initialize R0 before exiting:
1358 BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
1359 BPF_EXIT_INSN(),
1360 Error:
1361 0: (bf) r2 = r1
1362 1: (95) exit
1363 R0 !read_ok
1365 Program that accesses stack out of bounds:
1366 BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
1367 BPF_EXIT_INSN(),
1368 Error:
1369 0: (7a) *(u64 *)(r10 +8) = 0
1370 invalid stack off=8 size=8
1372 Program that doesn't initialize stack before passing its address into function:
1373 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1374 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1375 BPF_LD_MAP_FD(BPF_REG_1, 0),
1376 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1377 BPF_EXIT_INSN(),
1378 Error:
1379 0: (bf) r2 = r10
1380 1: (07) r2 += -8
1381 2: (b7) r1 = 0x0
1382 3: (85) call 1
1383 invalid indirect read from stack off -8+0 size 8
1385 Program that uses invalid map_fd=0 while calling to map_lookup_elem() function:
1386 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1387 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1388 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1389 BPF_LD_MAP_FD(BPF_REG_1, 0),
1390 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1391 BPF_EXIT_INSN(),
1392 Error:
1393 0: (7a) *(u64 *)(r10 -8) = 0
1394 1: (bf) r2 = r10
1395 2: (07) r2 += -8
1396 3: (b7) r1 = 0x0
1397 4: (85) call 1
1398 fd 0 is not pointing to valid bpf_map
1400 Program that doesn't check return value of map_lookup_elem() before accessing
1401 map element:
1402 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1403 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1404 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1405 BPF_LD_MAP_FD(BPF_REG_1, 0),
1406 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1407 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1408 BPF_EXIT_INSN(),
1409 Error:
1410 0: (7a) *(u64 *)(r10 -8) = 0
1411 1: (bf) r2 = r10
1412 2: (07) r2 += -8
1413 3: (b7) r1 = 0x0
1414 4: (85) call 1
1415 5: (7a) *(u64 *)(r0 +0) = 0
1416 R0 invalid mem access 'map_value_or_null'
1418 Program that correctly checks map_lookup_elem() returned value for NULL, but
1419 accesses the memory with incorrect alignment:
1420 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1421 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1422 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1423 BPF_LD_MAP_FD(BPF_REG_1, 0),
1424 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1425 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
1426 BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
1427 BPF_EXIT_INSN(),
1428 Error:
1429 0: (7a) *(u64 *)(r10 -8) = 0
1430 1: (bf) r2 = r10
1431 2: (07) r2 += -8
1432 3: (b7) r1 = 1
1433 4: (85) call 1
1434 5: (15) if r0 == 0x0 goto pc+1
1435 R0=map_ptr R10=fp
1436 6: (7a) *(u64 *)(r0 +4) = 0
1437 misaligned access off 4 size 8
1439 Program that correctly checks map_lookup_elem() returned value for NULL and
1440 accesses memory with correct alignment in one side of 'if' branch, but fails
1441 to do so in the other side of 'if' branch:
1442 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1443 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1444 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1445 BPF_LD_MAP_FD(BPF_REG_1, 0),
1446 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1447 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
1448 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1449 BPF_EXIT_INSN(),
1450 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
1451 BPF_EXIT_INSN(),
1452 Error:
1453 0: (7a) *(u64 *)(r10 -8) = 0
1454 1: (bf) r2 = r10
1455 2: (07) r2 += -8
1456 3: (b7) r1 = 1
1457 4: (85) call 1
1458 5: (15) if r0 == 0x0 goto pc+2
1459 R0=map_ptr R10=fp
1460 6: (7a) *(u64 *)(r0 +0) = 0
1461 7: (95) exit
1463 from 5 to 8: R0=imm0 R10=fp
1464 8: (7a) *(u64 *)(r0 +0) = 1
1465 R0 invalid mem access 'imm'
1467 Program that performs a socket lookup then sets the pointer to NULL without
1468 checking it:
1469 value:
1470 BPF_MOV64_IMM(BPF_REG_2, 0),
1471 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
1472 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1473 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1474 BPF_MOV64_IMM(BPF_REG_3, 4),
1475 BPF_MOV64_IMM(BPF_REG_4, 0),
1476 BPF_MOV64_IMM(BPF_REG_5, 0),
1477 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
1478 BPF_MOV64_IMM(BPF_REG_0, 0),
1479 BPF_EXIT_INSN(),
1480 Error:
1481 0: (b7) r2 = 0
1482 1: (63) *(u32 *)(r10 -8) = r2
1483 2: (bf) r2 = r10
1484 3: (07) r2 += -8
1485 4: (b7) r3 = 4
1486 5: (b7) r4 = 0
1487 6: (b7) r5 = 0
1488 7: (85) call bpf_sk_lookup_tcp#65
1489 8: (b7) r0 = 0
1490 9: (95) exit
1491 Unreleased reference id=1, alloc_insn=7
1493 Program that performs a socket lookup but does not NULL-check the returned
1494 value:
1495 BPF_MOV64_IMM(BPF_REG_2, 0),
1496 BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
1497 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1498 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1499 BPF_MOV64_IMM(BPF_REG_3, 4),
1500 BPF_MOV64_IMM(BPF_REG_4, 0),
1501 BPF_MOV64_IMM(BPF_REG_5, 0),
1502 BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
1503 BPF_EXIT_INSN(),
1504 Error:
1505 0: (b7) r2 = 0
1506 1: (63) *(u32 *)(r10 -8) = r2
1507 2: (bf) r2 = r10
1508 3: (07) r2 += -8
1509 4: (b7) r3 = 4
1510 5: (b7) r4 = 0
1511 6: (b7) r5 = 0
1512 7: (85) call bpf_sk_lookup_tcp#65
1513 8: (95) exit
1514 Unreleased reference id=1, alloc_insn=7
1516 Testing
1517 -------
1519 Next to the BPF toolchain, the kernel also ships a test module that contains
1520 various test cases for classic and internal BPF that can be executed against
1521 the BPF interpreter and JIT compiler. It can be found in lib/test_bpf.c and
1522 enabled via Kconfig:
1524 CONFIG_TEST_BPF=m
1526 After the module has been built and installed, the test suite can be executed
1527 via insmod or modprobe against 'test_bpf' module. Results of the test cases
1528 including timings in nsec can be found in the kernel log (dmesg).
1530 Misc
1531 ----
1533 Also trinity, the Linux syscall fuzzer, has built-in support for BPF and
1534 SECCOMP-BPF kernel fuzzing.
1536 Written by
1537 ----------
1539 The document was written in the hope that it is found useful and in order
1540 to give potential BPF hackers or security auditors a better overview of
1541 the underlying architecture.
1543 Jay Schulist <jschlst@samba.org>
1544 Daniel Borkmann <daniel@iogearbox.net>
1545 Alexei Starovoitov <ast@kernel.org>