Merge branch 'etnaviv/fixes' of https://git.pengutronix.de/git/lst/linux into drm...
[sfrench/cifs-2.6.git] / Documentation / networking / filter.txt
1 Linux Socket Filtering aka Berkeley Packet Filter (BPF)
2 =======================================================
3
4 Introduction
5 ------------
6
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.
11
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.
16
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.
22
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.
31
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.
36
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.
42
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.
47
48  [1] Documentation/prctl/seccomp_filter.txt
49
50 Original BPF paper:
51
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]
57
58 Structure
59 ---------
60
61 User space applications include <linux/filter.h> which contains the
62 following relevant structures:
63
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 };
70
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.
74
75 struct sock_fprog {                     /* Required for SO_ATTACH_FILTER. */
76         unsigned short             len; /* Number of filter blocks */
77         struct sock_filter __user *filter;
78 };
79
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).
82
83 Example
84 -------
85
86 #include <sys/socket.h>
87 #include <sys/types.h>
88 #include <arpa/inet.h>
89 #include <linux/if_ether.h>
90 /* ... */
91
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 };
119
120 struct sock_fprog bpf = {
121         .len = ARRAY_SIZE(code),
122         .filter = code,
123 };
124
125 sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
126 if (sock < 0)
127         /* ... bail out ... */
128
129 ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));
130 if (ret < 0)
131         /* ... bail out ... */
132
133 /* ... */
134 close(sock);
135
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.
139
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.
143
144 Note that socket filters are not restricted to PF_PACKET sockets only,
145 but can also be used on other socket families.
146
147 Summary of system calls:
148
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));
152
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.
156
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.
168
169 BPF engine and instruction set
170 ------------------------------
171
172 Under tools/net/ 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.
178
179 The BPF architecture consists of the following basic elements:
180
181   Element          Description
182
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
187
188 A program, that is translated by bpf_asm into "opcodes" is an array that
189 consists of the following elements (as already mentioned):
190
191   op:16, jt:8, jf:8, k:32
192
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.
198
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:
203
204   Instruction      Addressing mode      Description
205
206   ld               1, 2, 3, 4, 10       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, 10          Load word into X
211   ldxi             4                    Load word into X
212   ldxb             5                    Load byte into X
213
214   st               3                    Store A into M[]
215   stx              3                    Store X into M[]
216
217   jmp              6                    Jump to label
218   ja               6                    Jump to label
219   jeq              7, 8                 Jump on A == k
220   jneq             8                    Jump on A != k
221   jne              8                    Jump on A != k
222   jlt              8                    Jump on A <  k
223   jle              8                    Jump on A <= k
224   jgt              7, 8                 Jump on A >  k
225   jge              7, 8                 Jump on A >= k
226   jset             7, 8                 Jump on A &  k
227
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>
239
240   tax                                   Copy A into X
241   txa                                   Copy X into A
242
243   ret              4, 9                 Return
244
245 The next table shows addressing formats from the 2nd column:
246
247   Addressing mode  Syntax               Description
248
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               #k,Lt                Jump to Lt if predicate is true
258    9               a/%a                 Accumulator A
259   10               extension            BPF extension
260
261 The Linux kernel also has a couple of BPF extensions that are used along
262 with the class of load instructions by "overloading" the k argument with
263 a negative offset + a particular extension offset. The result of such BPF
264 extensions are loaded into A.
265
266 Possible BPF extensions are shown in the following table:
267
268   Extension                             Description
269
270   len                                   skb->len
271   proto                                 skb->protocol
272   type                                  skb->pkt_type
273   poff                                  Payload start offset
274   ifidx                                 skb->dev->ifindex
275   nla                                   Netlink attribute of type X with offset A
276   nlan                                  Nested Netlink attribute of type X with offset A
277   mark                                  skb->mark
278   queue                                 skb->queue_mapping
279   hatype                                skb->dev->type
280   rxhash                                skb->hash
281   cpu                                   raw_smp_processor_id()
282   vlan_tci                              skb_vlan_tag_get(skb)
283   vlan_avail                            skb_vlan_tag_present(skb)
284   vlan_tpid                             skb->vlan_proto
285   rand                                  prandom_u32()
286
287 These extensions can also be prefixed with '#'.
288 Examples for low-level BPF:
289
290 ** ARP packets:
291
292   ldh [12]
293   jne #0x806, drop
294   ret #-1
295   drop: ret #0
296
297 ** IPv4 TCP packets:
298
299   ldh [12]
300   jne #0x800, drop
301   ldb [23]
302   jneq #6, drop
303   ret #-1
304   drop: ret #0
305
306 ** (Accelerated) VLAN w/ id 10:
307
308   ld vlan_tci
309   jneq #10, drop
310   ret #-1
311   drop: ret #0
312
313 ** icmp random packet sampling, 1 in 4
314   ldh [12]
315   jne #0x800, drop
316   ldb [23]
317   jneq #1, drop
318   # get a random uint32 number
319   ld rand
320   mod #4
321   jneq #1, drop
322   ret #-1
323   drop: ret #0
324
325 ** SECCOMP filter example:
326
327   ld [4]                  /* offsetof(struct seccomp_data, arch) */
328   jne #0xc000003e, bad    /* AUDIT_ARCH_X86_64 */
329   ld [0]                  /* offsetof(struct seccomp_data, nr) */
330   jeq #15, good           /* __NR_rt_sigreturn */
331   jeq #231, good          /* __NR_exit_group */
332   jeq #60, good           /* __NR_exit */
333   jeq #0, good            /* __NR_read */
334   jeq #1, good            /* __NR_write */
335   jeq #5, good            /* __NR_fstat */
336   jeq #9, good            /* __NR_mmap */
337   jeq #14, good           /* __NR_rt_sigprocmask */
338   jeq #13, good           /* __NR_rt_sigaction */
339   jeq #35, good           /* __NR_nanosleep */
340   bad: ret #0             /* SECCOMP_RET_KILL */
341   good: ret #0x7fff0000   /* SECCOMP_RET_ALLOW */
342
343 The above example code can be placed into a file (here called "foo"), and
344 then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf
345 and cls_bpf understands and can directly be loaded with. Example with above
346 ARP code:
347
348 $ ./bpf_asm foo
349 4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,
350
351 In copy and paste C-like output:
352
353 $ ./bpf_asm -c foo
354 { 0x28,  0,  0, 0x0000000c },
355 { 0x15,  0,  1, 0x00000806 },
356 { 0x06,  0,  0, 0xffffffff },
357 { 0x06,  0,  0, 0000000000 },
358
359 In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF
360 filters that might not be obvious at first, it's good to test filters before
361 attaching to a live system. For that purpose, there's a small tool called
362 bpf_dbg under tools/net/ in the kernel source directory. This debugger allows
363 for testing BPF filters against given pcap files, single stepping through the
364 BPF code on the pcap's packets and to do BPF machine register dumps.
365
366 Starting bpf_dbg is trivial and just requires issuing:
367
368 # ./bpf_dbg
369
370 In case input and output do not equal stdin/stdout, bpf_dbg takes an
371 alternative stdin source as a first argument, and an alternative stdout
372 sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`.
373
374 Other than that, a particular libreadline configuration can be set via
375 file "~/.bpf_dbg_init" and the command history is stored in the file
376 "~/.bpf_dbg_history".
377
378 Interaction in bpf_dbg happens through a shell that also has auto-completion
379 support (follow-up example commands starting with '>' denote bpf_dbg shell).
380 The usual workflow would be to ...
381
382 > 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
383   Loads a BPF filter from standard output of bpf_asm, or transformed via
384   e.g. `tcpdump -iem1 -ddd port 22 | tr '\n' ','`. Note that for JIT
385   debugging (next section), this command creates a temporary socket and
386   loads the BPF code into the kernel. Thus, this will also be useful for
387   JIT developers.
388
389 > load pcap foo.pcap
390   Loads standard tcpdump pcap file.
391
392 > run [<n>]
393 bpf passes:1 fails:9
394   Runs through all packets from a pcap to account how many passes and fails
395   the filter will generate. A limit of packets to traverse can be given.
396
397 > disassemble
398 l0:     ldh [12]
399 l1:     jeq #0x800, l2, l5
400 l2:     ldb [23]
401 l3:     jeq #0x1, l4, l5
402 l4:     ret #0xffff
403 l5:     ret #0
404   Prints out BPF code disassembly.
405
406 > dump
407 /* { op, jt, jf, k }, */
408 { 0x28,  0,  0, 0x0000000c },
409 { 0x15,  0,  3, 0x00000800 },
410 { 0x30,  0,  0, 0x00000017 },
411 { 0x15,  0,  1, 0x00000001 },
412 { 0x06,  0,  0, 0x0000ffff },
413 { 0x06,  0,  0, 0000000000 },
414   Prints out C-style BPF code dump.
415
416 > breakpoint 0
417 breakpoint at: l0:      ldh [12]
418 > breakpoint 1
419 breakpoint at: l1:      jeq #0x800, l2, l5
420   ...
421   Sets breakpoints at particular BPF instructions. Issuing a `run` command
422   will walk through the pcap file continuing from the current packet and
423   break when a breakpoint is being hit (another `run` will continue from
424   the currently active breakpoint executing next instructions):
425
426   > run
427   -- register dump --
428   pc:       [0]                       <-- program counter
429   code:     [40] jt[0] jf[0] k[12]    <-- plain BPF code of current instruction
430   curr:     l0: ldh [12]              <-- disassembly of current instruction
431   A:        [00000000][0]             <-- content of A (hex, decimal)
432   X:        [00000000][0]             <-- content of X (hex, decimal)
433   M[0,15]:  [00000000][0]             <-- folded content of M (hex, decimal)
434   -- packet dump --                   <-- Current packet from pcap (hex)
435   len: 42
436     0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
437    16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
438    32: 00 00 00 00 00 00 0a 3b 01 01
439   (breakpoint)
440   >
441
442 > breakpoint
443 breakpoints: 0 1
444   Prints currently set breakpoints.
445
446 > step [-<n>, +<n>]
447   Performs single stepping through the BPF program from the current pc
448   offset. Thus, on each step invocation, above register dump is issued.
449   This can go forwards and backwards in time, a plain `step` will break
450   on the next BPF instruction, thus +1. (No `run` needs to be issued here.)
451
452 > select <n>
453   Selects a given packet from the pcap file to continue from. Thus, on
454   the next `run` or `step`, the BPF program is being evaluated against
455   the user pre-selected packet. Numbering starts just as in Wireshark
456   with index 1.
457
458 > quit
459 #
460   Exits bpf_dbg.
461
462 JIT compiler
463 ------------
464
465 The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC, PowerPC,
466 ARM, ARM64, MIPS and s390 and can be enabled through CONFIG_BPF_JIT. The JIT
467 compiler is transparently invoked for each attached filter from user space
468 or for internal kernel users if it has been previously enabled by root:
469
470   echo 1 > /proc/sys/net/core/bpf_jit_enable
471
472 For JIT developers, doing audits etc, each compile run can output the generated
473 opcode image into the kernel log via:
474
475   echo 2 > /proc/sys/net/core/bpf_jit_enable
476
477 Example output from dmesg:
478
479 [ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
480 [ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
481 [ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
482 [ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
483 [ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
484 [ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3
485
486 In the kernel source tree under tools/net/, there's bpf_jit_disasm for
487 generating disassembly out of the kernel log's hexdump:
488
489 # ./bpf_jit_disasm
490 70 bytes emitted from JIT compiler (pass:3, flen:6)
491 ffffffffa0069c8f + <x>:
492    0:   push   %rbp
493    1:   mov    %rsp,%rbp
494    4:   sub    $0x60,%rsp
495    8:   mov    %rbx,-0x8(%rbp)
496    c:   mov    0x68(%rdi),%r9d
497   10:   sub    0x6c(%rdi),%r9d
498   14:   mov    0xd8(%rdi),%r8
499   1b:   mov    $0xc,%esi
500   20:   callq  0xffffffffe0ff9442
501   25:   cmp    $0x800,%eax
502   2a:   jne    0x0000000000000042
503   2c:   mov    $0x17,%esi
504   31:   callq  0xffffffffe0ff945e
505   36:   cmp    $0x1,%eax
506   39:   jne    0x0000000000000042
507   3b:   mov    $0xffff,%eax
508   40:   jmp    0x0000000000000044
509   42:   xor    %eax,%eax
510   44:   leaveq
511   45:   retq
512
513 Issuing option `-o` will "annotate" opcodes to resulting assembler
514 instructions, which can be very useful for JIT developers:
515
516 # ./bpf_jit_disasm -o
517 70 bytes emitted from JIT compiler (pass:3, flen:6)
518 ffffffffa0069c8f + <x>:
519    0:   push   %rbp
520         55
521    1:   mov    %rsp,%rbp
522         48 89 e5
523    4:   sub    $0x60,%rsp
524         48 83 ec 60
525    8:   mov    %rbx,-0x8(%rbp)
526         48 89 5d f8
527    c:   mov    0x68(%rdi),%r9d
528         44 8b 4f 68
529   10:   sub    0x6c(%rdi),%r9d
530         44 2b 4f 6c
531   14:   mov    0xd8(%rdi),%r8
532         4c 8b 87 d8 00 00 00
533   1b:   mov    $0xc,%esi
534         be 0c 00 00 00
535   20:   callq  0xffffffffe0ff9442
536         e8 1d 94 ff e0
537   25:   cmp    $0x800,%eax
538         3d 00 08 00 00
539   2a:   jne    0x0000000000000042
540         75 16
541   2c:   mov    $0x17,%esi
542         be 17 00 00 00
543   31:   callq  0xffffffffe0ff945e
544         e8 28 94 ff e0
545   36:   cmp    $0x1,%eax
546         83 f8 01
547   39:   jne    0x0000000000000042
548         75 07
549   3b:   mov    $0xffff,%eax
550         b8 ff ff 00 00
551   40:   jmp    0x0000000000000044
552         eb 02
553   42:   xor    %eax,%eax
554         31 c0
555   44:   leaveq
556         c9
557   45:   retq
558         c3
559
560 For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful
561 toolchain for developing and testing the kernel's JIT compiler.
562
563 BPF kernel internals
564 --------------------
565 Internally, for the kernel interpreter, a different instruction set
566 format with similar underlying principles from BPF described in previous
567 paragraphs is being used. However, the instruction set format is modelled
568 closer to the underlying architecture to mimic native instruction sets, so
569 that a better performance can be achieved (more details later). This new
570 ISA is called 'eBPF' or 'internal BPF' interchangeably. (Note: eBPF which
571 originates from [e]xtended BPF is not the same as BPF extensions! While
572 eBPF is an ISA, BPF extensions date back to classic BPF's 'overloading'
573 of BPF_LD | BPF_{B,H,W} | BPF_ABS instruction.)
574
575 It is designed to be JITed with one to one mapping, which can also open up
576 the possibility for GCC/LLVM compilers to generate optimized eBPF code through
577 an eBPF backend that performs almost as fast as natively compiled code.
578
579 The new instruction set was originally designed with the possible goal in
580 mind to write programs in "restricted C" and compile into eBPF with a optional
581 GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with
582 minimal performance overhead over two steps, that is, C -> eBPF -> native code.
583
584 Currently, the new format is being used for running user BPF programs, which
585 includes seccomp BPF, classic socket filters, cls_bpf traffic classifier,
586 team driver's classifier for its load-balancing mode, netfilter's xt_bpf
587 extension, PTP dissector/classifier, and much more. They are all internally
588 converted by the kernel into the new instruction set representation and run
589 in the eBPF interpreter. For in-kernel handlers, this all works transparently
590 by using bpf_prog_create() for setting up the filter, resp.
591 bpf_prog_destroy() for destroying it. The macro
592 BPF_PROG_RUN(filter, ctx) transparently invokes eBPF interpreter or JITed
593 code to run the filter. 'filter' is a pointer to struct bpf_prog that we
594 got from bpf_prog_create(), and 'ctx' the given context (e.g.
595 skb pointer). All constraints and restrictions from bpf_check_classic() apply
596 before a conversion to the new layout is being done behind the scenes!
597
598 Currently, the classic BPF format is being used for JITing on most 32-bit
599 architectures, whereas x86-64, aarch64, s390x, powerpc64, sparc64 perform JIT
600 compilation from eBPF instruction set.
601
602 Some core changes of the new internal format:
603
604 - Number of registers increase from 2 to 10:
605
606   The old format had two registers A and X, and a hidden frame pointer. The
607   new layout extends this to be 10 internal registers and a read-only frame
608   pointer. Since 64-bit CPUs are passing arguments to functions via registers
609   the number of args from eBPF program to in-kernel function is restricted
610   to 5 and one register is used to accept return value from an in-kernel
611   function. Natively, x86_64 passes first 6 arguments in registers, aarch64/
612   sparcv9/mips64 have 7 - 8 registers for arguments; x86_64 has 6 callee saved
613   registers, and aarch64/sparcv9/mips64 have 11 or more callee saved registers.
614
615   Therefore, eBPF calling convention is defined as:
616
617     * R0        - return value from in-kernel function, and exit value for eBPF program
618     * R1 - R5   - arguments from eBPF program to in-kernel function
619     * R6 - R9   - callee saved registers that in-kernel function will preserve
620     * R10       - read-only frame pointer to access stack
621
622   Thus, all eBPF registers map one to one to HW registers on x86_64, aarch64,
623   etc, and eBPF calling convention maps directly to ABIs used by the kernel on
624   64-bit architectures.
625
626   On 32-bit architectures JIT may map programs that use only 32-bit arithmetic
627   and may let more complex programs to be interpreted.
628
629   R0 - R5 are scratch registers and eBPF program needs spill/fill them if
630   necessary across calls. Note that there is only one eBPF program (== one
631   eBPF main routine) and it cannot call other eBPF functions, it can only
632   call predefined in-kernel functions, though.
633
634 - Register width increases from 32-bit to 64-bit:
635
636   Still, the semantics of the original 32-bit ALU operations are preserved
637   via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower
638   subregisters that zero-extend into 64-bit if they are being written to.
639   That behavior maps directly to x86_64 and arm64 subregister definition, but
640   makes other JITs more difficult.
641
642   32-bit architectures run 64-bit internal BPF programs via interpreter.
643   Their JITs may convert BPF programs that only use 32-bit subregisters into
644   native instruction set and let the rest being interpreted.
645
646   Operation is 64-bit, because on 64-bit architectures, pointers are also
647   64-bit wide, and we want to pass 64-bit values in/out of kernel functions,
648   so 32-bit eBPF registers would otherwise require to define register-pair
649   ABI, thus, there won't be able to use a direct eBPF register to HW register
650   mapping and JIT would need to do combine/split/move operations for every
651   register in and out of the function, which is complex, bug prone and slow.
652   Another reason is the use of atomic 64-bit counters.
653
654 - Conditional jt/jf targets replaced with jt/fall-through:
655
656   While the original design has constructs such as "if (cond) jump_true;
657   else jump_false;", they are being replaced into alternative constructs like
658   "if (cond) jump_true; /* else fall-through */".
659
660 - Introduces bpf_call insn and register passing convention for zero overhead
661   calls from/to other kernel functions:
662
663   Before an in-kernel function call, the internal BPF program needs to
664   place function arguments into R1 to R5 registers to satisfy calling
665   convention, then the interpreter will take them from registers and pass
666   to in-kernel function. If R1 - R5 registers are mapped to CPU registers
667   that are used for argument passing on given architecture, the JIT compiler
668   doesn't need to emit extra moves. Function arguments will be in the correct
669   registers and BPF_CALL instruction will be JITed as single 'call' HW
670   instruction. This calling convention was picked to cover common call
671   situations without performance penalty.
672
673   After an in-kernel function call, R1 - R5 are reset to unreadable and R0 has
674   a return value of the function. Since R6 - R9 are callee saved, their state
675   is preserved across the call.
676
677   For example, consider three C functions:
678
679   u64 f1() { return (*_f2)(1); }
680   u64 f2(u64 a) { return f3(a + 1, a); }
681   u64 f3(u64 a, u64 b) { return a - b; }
682
683   GCC can compile f1, f3 into x86_64:
684
685   f1:
686     movl $1, %edi
687     movq _f2(%rip), %rax
688     jmp  *%rax
689   f3:
690     movq %rdi, %rax
691     subq %rsi, %rax
692     ret
693
694   Function f2 in eBPF may look like:
695
696   f2:
697     bpf_mov R2, R1
698     bpf_add R1, 1
699     bpf_call f3
700     bpf_exit
701
702   If f2 is JITed and the pointer stored to '_f2'. The calls f1 -> f2 -> f3 and
703   returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to
704   be used to call into f2.
705
706   For practical reasons all eBPF programs have only one argument 'ctx' which is
707   already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs
708   can call kernel functions with up to 5 arguments. Calls with 6 or more arguments
709   are currently not supported, but these restrictions can be lifted if necessary
710   in the future.
711
712   On 64-bit architectures all register map to HW registers one to one. For
713   example, x86_64 JIT compiler can map them as ...
714
715     R0 - rax
716     R1 - rdi
717     R2 - rsi
718     R3 - rdx
719     R4 - rcx
720     R5 - r8
721     R6 - rbx
722     R7 - r13
723     R8 - r14
724     R9 - r15
725     R10 - rbp
726
727   ... since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing
728   and rbx, r12 - r15 are callee saved.
729
730   Then the following internal BPF pseudo-program:
731
732     bpf_mov R6, R1 /* save ctx */
733     bpf_mov R2, 2
734     bpf_mov R3, 3
735     bpf_mov R4, 4
736     bpf_mov R5, 5
737     bpf_call foo
738     bpf_mov R7, R0 /* save foo() return value */
739     bpf_mov R1, R6 /* restore ctx for next call */
740     bpf_mov R2, 6
741     bpf_mov R3, 7
742     bpf_mov R4, 8
743     bpf_mov R5, 9
744     bpf_call bar
745     bpf_add R0, R7
746     bpf_exit
747
748   After JIT to x86_64 may look like:
749
750     push %rbp
751     mov %rsp,%rbp
752     sub $0x228,%rsp
753     mov %rbx,-0x228(%rbp)
754     mov %r13,-0x220(%rbp)
755     mov %rdi,%rbx
756     mov $0x2,%esi
757     mov $0x3,%edx
758     mov $0x4,%ecx
759     mov $0x5,%r8d
760     callq foo
761     mov %rax,%r13
762     mov %rbx,%rdi
763     mov $0x2,%esi
764     mov $0x3,%edx
765     mov $0x4,%ecx
766     mov $0x5,%r8d
767     callq bar
768     add %r13,%rax
769     mov -0x228(%rbp),%rbx
770     mov -0x220(%rbp),%r13
771     leaveq
772     retq
773
774   Which is in this example equivalent in C to:
775
776     u64 bpf_filter(u64 ctx)
777     {
778         return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
779     }
780
781   In-kernel functions foo() and bar() with prototype: u64 (*)(u64 arg1, u64
782   arg2, u64 arg3, u64 arg4, u64 arg5); will receive arguments in proper
783   registers and place their return value into '%rax' which is R0 in eBPF.
784   Prologue and epilogue are emitted by JIT and are implicit in the
785   interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve
786   them across the calls as defined by calling convention.
787
788   For example the following program is invalid:
789
790     bpf_mov R1, 1
791     bpf_call foo
792     bpf_mov R0, R1
793     bpf_exit
794
795   After the call the registers R1-R5 contain junk values and cannot be read.
796   In the future an eBPF verifier can be used to validate internal BPF programs.
797
798 Also in the new design, eBPF is limited to 4096 insns, which means that any
799 program will terminate quickly and will only call a fixed number of kernel
800 functions. Original BPF and the new format are two operand instructions,
801 which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT.
802
803 The input context pointer for invoking the interpreter function is generic,
804 its content is defined by a specific use case. For seccomp register R1 points
805 to seccomp_data, for converted BPF filters R1 points to a skb.
806
807 A program, that is translated internally consists of the following elements:
808
809   op:16, jt:8, jf:8, k:32    ==>    op:8, dst_reg:4, src_reg:4, off:16, imm:32
810
811 So far 87 internal BPF instructions were implemented. 8-bit 'op' opcode field
812 has room for new instructions. Some of them may use 16/24/32 byte encoding. New
813 instructions must be multiple of 8 bytes to preserve backward compatibility.
814
815 Internal BPF is a general purpose RISC instruction set. Not every register and
816 every instruction are used during translation from original BPF to new format.
817 For example, socket filters are not using 'exclusive add' instruction, but
818 tracing filters may do to maintain counters of events, for example. Register R9
819 is not used by socket filters either, but more complex filters may be running
820 out of registers and would have to resort to spill/fill to stack.
821
822 Internal BPF can used as generic assembler for last step performance
823 optimizations, socket filters and seccomp are using it as assembler. Tracing
824 filters may use it as assembler to generate code from kernel. In kernel usage
825 may not be bounded by security considerations, since generated internal BPF code
826 may be optimizing internal code path and not being exposed to the user space.
827 Safety of internal BPF can come from a verifier (TBD). In such use cases as
828 described, it may be used as safe instruction set.
829
830 Just like the original BPF, the new format runs within a controlled environment,
831 is deterministic and the kernel can easily prove that. The safety of the program
832 can be determined in two steps: first step does depth-first-search to disallow
833 loops and other CFG validation; second step starts from the first insn and
834 descends all possible paths. It simulates execution of every insn and observes
835 the state change of registers and stack.
836
837 eBPF opcode encoding
838 --------------------
839
840 eBPF is reusing most of the opcode encoding from classic to simplify conversion
841 of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code'
842 field is divided into three parts:
843
844   +----------------+--------+--------------------+
845   |   4 bits       |  1 bit |   3 bits           |
846   | operation code | source | instruction class  |
847   +----------------+--------+--------------------+
848   (MSB)                                      (LSB)
849
850 Three LSB bits store instruction class which is one of:
851
852   Classic BPF classes:    eBPF classes:
853
854   BPF_LD    0x00          BPF_LD    0x00
855   BPF_LDX   0x01          BPF_LDX   0x01
856   BPF_ST    0x02          BPF_ST    0x02
857   BPF_STX   0x03          BPF_STX   0x03
858   BPF_ALU   0x04          BPF_ALU   0x04
859   BPF_JMP   0x05          BPF_JMP   0x05
860   BPF_RET   0x06          [ class 6 unused, for future if needed ]
861   BPF_MISC  0x07          BPF_ALU64 0x07
862
863 When BPF_CLASS(code) == BPF_ALU or BPF_JMP, 4th bit encodes source operand ...
864
865   BPF_K     0x00
866   BPF_X     0x08
867
868  * in classic BPF, this means:
869
870   BPF_SRC(code) == BPF_X - use register X as source operand
871   BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
872
873  * in eBPF, this means:
874
875   BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand
876   BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
877
878 ... and four MSB bits store operation code.
879
880 If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of:
881
882   BPF_ADD   0x00
883   BPF_SUB   0x10
884   BPF_MUL   0x20
885   BPF_DIV   0x30
886   BPF_OR    0x40
887   BPF_AND   0x50
888   BPF_LSH   0x60
889   BPF_RSH   0x70
890   BPF_NEG   0x80
891   BPF_MOD   0x90
892   BPF_XOR   0xa0
893   BPF_MOV   0xb0  /* eBPF only: mov reg to reg */
894   BPF_ARSH  0xc0  /* eBPF only: sign extending shift right */
895   BPF_END   0xd0  /* eBPF only: endianness conversion */
896
897 If BPF_CLASS(code) == BPF_JMP, BPF_OP(code) is one of:
898
899   BPF_JA    0x00
900   BPF_JEQ   0x10
901   BPF_JGT   0x20
902   BPF_JGE   0x30
903   BPF_JSET  0x40
904   BPF_JNE   0x50  /* eBPF only: jump != */
905   BPF_JSGT  0x60  /* eBPF only: signed '>' */
906   BPF_JSGE  0x70  /* eBPF only: signed '>=' */
907   BPF_CALL  0x80  /* eBPF only: function call */
908   BPF_EXIT  0x90  /* eBPF only: function return */
909
910 So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF
911 and eBPF. There are only two registers in classic BPF, so it means A += X.
912 In eBPF it means dst_reg = (u32) dst_reg + (u32) src_reg; similarly,
913 BPF_XOR | BPF_K | BPF_ALU means A ^= imm32 in classic BPF and analogous
914 src_reg = (u32) src_reg ^ (u32) imm32 in eBPF.
915
916 Classic BPF is using BPF_MISC class to represent A = X and X = A moves.
917 eBPF is using BPF_MOV | BPF_X | BPF_ALU code instead. Since there are no
918 BPF_MISC operations in eBPF, the class 7 is used as BPF_ALU64 to mean
919 exactly the same operations as BPF_ALU, but with 64-bit wide operands
920 instead. So BPF_ADD | BPF_X | BPF_ALU64 means 64-bit addition, i.e.:
921 dst_reg = dst_reg + src_reg
922
923 Classic BPF wastes the whole BPF_RET class to represent a single 'ret'
924 operation. Classic BPF_RET | BPF_K means copy imm32 into return register
925 and perform function exit. eBPF is modeled to match CPU, so BPF_JMP | BPF_EXIT
926 in eBPF means function exit only. The eBPF program needs to store return
927 value into register R0 before doing a BPF_EXIT. Class 6 in eBPF is currently
928 unused and reserved for future use.
929
930 For load and store instructions the 8-bit 'code' field is divided as:
931
932   +--------+--------+-------------------+
933   | 3 bits | 2 bits |   3 bits          |
934   |  mode  |  size  | instruction class |
935   +--------+--------+-------------------+
936   (MSB)                             (LSB)
937
938 Size modifier is one of ...
939
940   BPF_W   0x00    /* word */
941   BPF_H   0x08    /* half word */
942   BPF_B   0x10    /* byte */
943   BPF_DW  0x18    /* eBPF only, double word */
944
945 ... which encodes size of load/store operation:
946
947  B  - 1 byte
948  H  - 2 byte
949  W  - 4 byte
950  DW - 8 byte (eBPF only)
951
952 Mode modifier is one of:
953
954   BPF_IMM  0x00  /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
955   BPF_ABS  0x20
956   BPF_IND  0x40
957   BPF_MEM  0x60
958   BPF_LEN  0x80  /* classic BPF only, reserved in eBPF */
959   BPF_MSH  0xa0  /* classic BPF only, reserved in eBPF */
960   BPF_XADD 0xc0  /* eBPF only, exclusive add */
961
962 eBPF has two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and
963 (BPF_IND | <size> | BPF_LD) which are used to access packet data.
964
965 They had to be carried over from classic to have strong performance of
966 socket filters running in eBPF interpreter. These instructions can only
967 be used when interpreter context is a pointer to 'struct sk_buff' and
968 have seven implicit operands. Register R6 is an implicit input that must
969 contain pointer to sk_buff. Register R0 is an implicit output which contains
970 the data fetched from the packet. Registers R1-R5 are scratch registers
971 and must not be used to store the data across BPF_ABS | BPF_LD or
972 BPF_IND | BPF_LD instructions.
973
974 These instructions have implicit program exit condition as well. When
975 eBPF program is trying to access the data beyond the packet boundary,
976 the interpreter will abort the execution of the program. JIT compilers
977 therefore must preserve this property. src_reg and imm32 fields are
978 explicit inputs to these instructions.
979
980 For example:
981
982   BPF_IND | BPF_W | BPF_LD means:
983
984     R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32))
985     and R1 - R5 were scratched.
986
987 Unlike classic BPF instruction set, eBPF has generic load/store operations:
988
989 BPF_MEM | <size> | BPF_STX:  *(size *) (dst_reg + off) = src_reg
990 BPF_MEM | <size> | BPF_ST:   *(size *) (dst_reg + off) = imm32
991 BPF_MEM | <size> | BPF_LDX:  dst_reg = *(size *) (src_reg + off)
992 BPF_XADD | BPF_W  | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg
993 BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
994
995 Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and
996 2 byte atomic increments are not supported.
997
998 eBPF has one 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM which consists
999 of two consecutive 'struct bpf_insn' 8-byte blocks and interpreted as single
1000 instruction that loads 64-bit immediate value into a dst_reg.
1001 Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
1002 32-bit immediate value into a register.
1003
1004 eBPF verifier
1005 -------------
1006 The safety of the eBPF program is determined in two steps.
1007
1008 First step does DAG check to disallow loops and other CFG validation.
1009 In particular it will detect programs that have unreachable instructions.
1010 (though classic BPF checker allows them)
1011
1012 Second step starts from the first insn and descends all possible paths.
1013 It simulates execution of every insn and observes the state change of
1014 registers and stack.
1015
1016 At the start of the program the register R1 contains a pointer to context
1017 and has type PTR_TO_CTX.
1018 If verifier sees an insn that does R2=R1, then R2 has now type
1019 PTR_TO_CTX as well and can be used on the right hand side of expression.
1020 If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=UNKNOWN_VALUE,
1021 since addition of two valid pointers makes invalid pointer.
1022 (In 'secure' mode verifier will reject any type of pointer arithmetic to make
1023 sure that kernel addresses don't leak to unprivileged users)
1024
1025 If register was never written to, it's not readable:
1026   bpf_mov R0 = R2
1027   bpf_exit
1028 will be rejected, since R2 is unreadable at the start of the program.
1029
1030 After kernel function call, R1-R5 are reset to unreadable and
1031 R0 has a return type of the function.
1032
1033 Since R6-R9 are callee saved, their state is preserved across the call.
1034   bpf_mov R6 = 1
1035   bpf_call foo
1036   bpf_mov R0 = R6
1037   bpf_exit
1038 is a correct program. If there was R1 instead of R6, it would have
1039 been rejected.
1040
1041 load/store instructions are allowed only with registers of valid types, which
1042 are PTR_TO_CTX, PTR_TO_MAP, FRAME_PTR. They are bounds and alignment checked.
1043 For example:
1044  bpf_mov R1 = 1
1045  bpf_mov R2 = 2
1046  bpf_xadd *(u32 *)(R1 + 3) += R2
1047  bpf_exit
1048 will be rejected, since R1 doesn't have a valid pointer type at the time of
1049 execution of instruction bpf_xadd.
1050
1051 At the start R1 type is PTR_TO_CTX (a pointer to generic 'struct bpf_context')
1052 A callback is used to customize verifier to restrict eBPF program access to only
1053 certain fields within ctx structure with specified size and alignment.
1054
1055 For example, the following insn:
1056   bpf_ld R0 = *(u32 *)(R6 + 8)
1057 intends to load a word from address R6 + 8 and store it into R0
1058 If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
1059 that offset 8 of size 4 bytes can be accessed for reading, otherwise
1060 the verifier will reject the program.
1061 If R6=FRAME_PTR, then access should be aligned and be within
1062 stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
1063 so it will fail verification, since it's out of bounds.
1064
1065 The verifier will allow eBPF program to read data from stack only after
1066 it wrote into it.
1067 Classic BPF verifier does similar check with M[0-15] memory slots.
1068 For example:
1069   bpf_ld R0 = *(u32 *)(R10 - 4)
1070   bpf_exit
1071 is invalid program.
1072 Though R10 is correct read-only register and has type FRAME_PTR
1073 and R10 - 4 is within stack bounds, there were no stores into that location.
1074
1075 Pointer register spill/fill is tracked as well, since four (R6-R9)
1076 callee saved registers may not be enough for some programs.
1077
1078 Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
1079 The eBPF verifier will check that registers match argument constraints.
1080 After the call register R0 will be set to return type of the function.
1081
1082 Function calls is a main mechanism to extend functionality of eBPF programs.
1083 Socket filters may let programs to call one set of functions, whereas tracing
1084 filters may allow completely different set.
1085
1086 If a function made accessible to eBPF program, it needs to be thought through
1087 from safety point of view. The verifier will guarantee that the function is
1088 called with valid arguments.
1089
1090 seccomp vs socket filters have different security restrictions for classic BPF.
1091 Seccomp solves this by two stage verifier: classic BPF verifier is followed
1092 by seccomp verifier. In case of eBPF one configurable verifier is shared for
1093 all use cases.
1094
1095 See details of eBPF verifier in kernel/bpf/verifier.c
1096
1097 Direct packet access
1098 --------------------
1099 In cls_bpf and act_bpf programs the verifier allows direct access to the packet
1100 data via skb->data and skb->data_end pointers.
1101 Ex:
1102 1:  r4 = *(u32 *)(r1 +80)  /* load skb->data_end */
1103 2:  r3 = *(u32 *)(r1 +76)  /* load skb->data */
1104 3:  r5 = r3
1105 4:  r5 += 14
1106 5:  if r5 > r4 goto pc+16
1107 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
1108 6:  r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */
1109
1110 this 2byte load from the packet is safe to do, since the program author
1111 did check 'if (skb->data + 14 > skb->data_end) goto err' at insn #5 which
1112 means that in the fall-through case the register R3 (which points to skb->data)
1113 has at least 14 directly accessible bytes. The verifier marks it
1114 as R3=pkt(id=0,off=0,r=14).
1115 id=0 means that no additional variables were added to the register.
1116 off=0 means that no additional constants were added.
1117 r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
1118 Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
1119 to the packet data, but constant 14 was added to the register, so
1120 it now points to 'skb->data + 14' and accessible range is [R5, R5 + 14 - 14)
1121 which is zero bytes.
1122
1123 More complex packet access may look like:
1124  R0=imm1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
1125  6:  r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
1126  7:  r4 = *(u8 *)(r3 +12)
1127  8:  r4 *= 14
1128  9:  r3 = *(u32 *)(r1 +76) /* load skb->data */
1129 10:  r3 += r4
1130 11:  r2 = r1
1131 12:  r2 <<= 48
1132 13:  r2 >>= 48
1133 14:  r3 += r2
1134 15:  r2 = r3
1135 16:  r2 += 8
1136 17:  r1 = *(u32 *)(r1 +80) /* load skb->data_end */
1137 18:  if r2 > r1 goto pc+2
1138  R0=inv56 R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv52 R5=pkt(id=0,off=14,r=14) R10=fp
1139 19:  r1 = *(u8 *)(r3 +4)
1140 The state of the register R3 is R3=pkt(id=2,off=0,r=8)
1141 id=2 means that two 'r3 += rX' instructions were seen, so r3 points to some
1142 offset within a packet and since the program author did
1143 'if (r3 + 8 > r1) goto err' at insn #18, the safe range is [R3, R3 + 8).
1144 The verifier only allows 'add' operation on packet registers. Any other
1145 operation will set the register state to 'unknown_value' and it won't be
1146 available for direct packet access.
1147 Operation 'r3 += rX' may overflow and become less than original skb->data,
1148 therefore the verifier has to prevent that. So it tracks the number of
1149 upper zero bits in all 'uknown_value' registers, so when it sees
1150 'r3 += rX' instruction and rX is more than 16-bit value, it will error as:
1151 "cannot add integer value with N upper zero bits to ptr_to_packet"
1152 Ex. after insn 'r4 = *(u8 *)(r3 +12)' (insn #7 above) the state of r4 is
1153 R4=inv56 which means that upper 56 bits on the register are guaranteed
1154 to be zero. After insn 'r4 *= 14' the state becomes R4=inv52, since
1155 multiplying 8-bit value by constant 14 will keep upper 52 bits as zero.
1156 Similarly 'r2 >>= 48' will make R2=inv48, since the shift is not sign
1157 extending. This logic is implemented in evaluate_reg_alu() function.
1158
1159 The end result is that bpf program author can access packet directly
1160 using normal C code as:
1161   void *data = (void *)(long)skb->data;
1162   void *data_end = (void *)(long)skb->data_end;
1163   struct eth_hdr *eth = data;
1164   struct iphdr *iph = data + sizeof(*eth);
1165   struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
1166
1167   if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
1168           return 0;
1169   if (eth->h_proto != htons(ETH_P_IP))
1170           return 0;
1171   if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
1172           return 0;
1173   if (udp->dest == 53 || udp->source == 9)
1174           ...;
1175 which makes such programs easier to write comparing to LD_ABS insn
1176 and significantly faster.
1177
1178 eBPF maps
1179 ---------
1180 'maps' is a generic storage of different types for sharing data between kernel
1181 and userspace.
1182
1183 The maps are accessed from user space via BPF syscall, which has commands:
1184 - create a map with given type and attributes
1185   map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size)
1186   using attr->map_type, attr->key_size, attr->value_size, attr->max_entries
1187   returns process-local file descriptor or negative error
1188
1189 - lookup key in a given map
1190   err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size)
1191   using attr->map_fd, attr->key, attr->value
1192   returns zero and stores found elem into value or negative error
1193
1194 - create or update key/value pair in a given map
1195   err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size)
1196   using attr->map_fd, attr->key, attr->value
1197   returns zero or negative error
1198
1199 - find and delete element by key in a given map
1200   err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size)
1201   using attr->map_fd, attr->key
1202
1203 - to delete map: close(fd)
1204   Exiting process will delete maps automatically
1205
1206 userspace programs use this syscall to create/access maps that eBPF programs
1207 are concurrently updating.
1208
1209 maps can have different types: hash, array, bloom filter, radix-tree, etc.
1210
1211 The map is defined by:
1212   . type
1213   . max number of elements
1214   . key size in bytes
1215   . value size in bytes
1216
1217 Understanding eBPF verifier messages
1218 ------------------------------------
1219
1220 The following are few examples of invalid eBPF programs and verifier error
1221 messages as seen in the log:
1222
1223 Program with unreachable instructions:
1224 static struct bpf_insn prog[] = {
1225   BPF_EXIT_INSN(),
1226   BPF_EXIT_INSN(),
1227 };
1228 Error:
1229   unreachable insn 1
1230
1231 Program that reads uninitialized register:
1232   BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
1233   BPF_EXIT_INSN(),
1234 Error:
1235   0: (bf) r0 = r2
1236   R2 !read_ok
1237
1238 Program that doesn't initialize R0 before exiting:
1239   BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
1240   BPF_EXIT_INSN(),
1241 Error:
1242   0: (bf) r2 = r1
1243   1: (95) exit
1244   R0 !read_ok
1245
1246 Program that accesses stack out of bounds:
1247   BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
1248   BPF_EXIT_INSN(),
1249 Error:
1250   0: (7a) *(u64 *)(r10 +8) = 0
1251   invalid stack off=8 size=8
1252
1253 Program that doesn't initialize stack before passing its address into function:
1254   BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1255   BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1256   BPF_LD_MAP_FD(BPF_REG_1, 0),
1257   BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1258   BPF_EXIT_INSN(),
1259 Error:
1260   0: (bf) r2 = r10
1261   1: (07) r2 += -8
1262   2: (b7) r1 = 0x0
1263   3: (85) call 1
1264   invalid indirect read from stack off -8+0 size 8
1265
1266 Program that uses invalid map_fd=0 while calling to map_lookup_elem() function:
1267   BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1268   BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1269   BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1270   BPF_LD_MAP_FD(BPF_REG_1, 0),
1271   BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1272   BPF_EXIT_INSN(),
1273 Error:
1274   0: (7a) *(u64 *)(r10 -8) = 0
1275   1: (bf) r2 = r10
1276   2: (07) r2 += -8
1277   3: (b7) r1 = 0x0
1278   4: (85) call 1
1279   fd 0 is not pointing to valid bpf_map
1280
1281 Program that doesn't check return value of map_lookup_elem() before accessing
1282 map element:
1283   BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1284   BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1285   BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1286   BPF_LD_MAP_FD(BPF_REG_1, 0),
1287   BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1288   BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1289   BPF_EXIT_INSN(),
1290 Error:
1291   0: (7a) *(u64 *)(r10 -8) = 0
1292   1: (bf) r2 = r10
1293   2: (07) r2 += -8
1294   3: (b7) r1 = 0x0
1295   4: (85) call 1
1296   5: (7a) *(u64 *)(r0 +0) = 0
1297   R0 invalid mem access 'map_value_or_null'
1298
1299 Program that correctly checks map_lookup_elem() returned value for NULL, but
1300 accesses the memory with incorrect alignment:
1301   BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1302   BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1303   BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1304   BPF_LD_MAP_FD(BPF_REG_1, 0),
1305   BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1306   BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
1307   BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
1308   BPF_EXIT_INSN(),
1309 Error:
1310   0: (7a) *(u64 *)(r10 -8) = 0
1311   1: (bf) r2 = r10
1312   2: (07) r2 += -8
1313   3: (b7) r1 = 1
1314   4: (85) call 1
1315   5: (15) if r0 == 0x0 goto pc+1
1316    R0=map_ptr R10=fp
1317   6: (7a) *(u64 *)(r0 +4) = 0
1318   misaligned access off 4 size 8
1319
1320 Program that correctly checks map_lookup_elem() returned value for NULL and
1321 accesses memory with correct alignment in one side of 'if' branch, but fails
1322 to do so in the other side of 'if' branch:
1323   BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
1324   BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
1325   BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
1326   BPF_LD_MAP_FD(BPF_REG_1, 0),
1327   BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
1328   BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
1329   BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
1330   BPF_EXIT_INSN(),
1331   BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
1332   BPF_EXIT_INSN(),
1333 Error:
1334   0: (7a) *(u64 *)(r10 -8) = 0
1335   1: (bf) r2 = r10
1336   2: (07) r2 += -8
1337   3: (b7) r1 = 1
1338   4: (85) call 1
1339   5: (15) if r0 == 0x0 goto pc+2
1340    R0=map_ptr R10=fp
1341   6: (7a) *(u64 *)(r0 +0) = 0
1342   7: (95) exit
1343
1344   from 5 to 8: R0=imm0 R10=fp
1345   8: (7a) *(u64 *)(r0 +0) = 1
1346   R0 invalid mem access 'imm'
1347
1348 Testing
1349 -------
1350
1351 Next to the BPF toolchain, the kernel also ships a test module that contains
1352 various test cases for classic and internal BPF that can be executed against
1353 the BPF interpreter and JIT compiler. It can be found in lib/test_bpf.c and
1354 enabled via Kconfig:
1355
1356   CONFIG_TEST_BPF=m
1357
1358 After the module has been built and installed, the test suite can be executed
1359 via insmod or modprobe against 'test_bpf' module. Results of the test cases
1360 including timings in nsec can be found in the kernel log (dmesg).
1361
1362 Misc
1363 ----
1364
1365 Also trinity, the Linux syscall fuzzer, has built-in support for BPF and
1366 SECCOMP-BPF kernel fuzzing.
1367
1368 Written by
1369 ----------
1370
1371 The document was written in the hope that it is found useful and in order
1372 to give potential BPF hackers or security auditors a better overview of
1373 the underlying architecture.
1374
1375 Jay Schulist <jschlst@samba.org>
1376 Daniel Borkmann <daniel@iogearbox.net>
1377 Alexei Starovoitov <ast@kernel.org>