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