1Linux Socket Filtering aka Berkeley Packet Filter (BPF) 2======================================================= 3 4Introduction 5------------ 6 7Linux Socket Filtering (LSF) is derived from the Berkeley Packet Filter. 8Though there are some distinct differences between the BSD and Linux 9Kernel filtering, but when we speak of BPF or LSF in Linux context, we 10mean the very same mechanism of filtering in the Linux kernel. 11 12BPF allows a user-space program to attach a filter onto any socket and 13allow or disallow certain types of data to come through the socket. LSF 14follows exactly the same filter code structure as BSD's BPF, so referring 15to the BSD bpf.4 manpage is very helpful in creating filters. 16 17On Linux, BPF is much simpler than on BSD. One does not have to worry 18about devices or anything like that. You simply create your filter code, 19send it to the kernel via the SO_ATTACH_FILTER option and if your filter 20code passes the kernel check on it, you then immediately begin filtering 21data on that socket. 22 23You can also detach filters from your socket via the SO_DETACH_FILTER 24option. This will probably not be used much since when you close a socket 25that has a filter on it the filter is automagically removed. The other 26less common case may be adding a different filter on the same socket where 27you had another filter that is still running: the kernel takes care of 28removing the old one and placing your new one in its place, assuming your 29filter has passed the checks, otherwise if it fails the old filter will 30remain on that socket. 31 32SO_LOCK_FILTER option allows to lock the filter attached to a socket. Once 33set, a filter cannot be removed or changed. This allows one process to 34setup a socket, attach a filter, lock it then drop privileges and be 35assured that the filter will be kept until the socket is closed. 36 37The biggest user of this construct might be libpcap. Issuing a high-level 38filter command like `tcpdump -i em1 port 22` passes through the libpcap 39internal compiler that generates a structure that can eventually be loaded 40via SO_ATTACH_FILTER to the kernel. `tcpdump -i em1 port 22 -ddd` 41displays what is being placed into this structure. 42 43Although we were only speaking about sockets here, BPF in Linux is used 44in many more places. There's xt_bpf for netfilter, cls_bpf in the kernel 45qdisc layer, SECCOMP-BPF (SECure COMPuting [1]), and lots of other places 46such as team driver, PTP code, etc where BPF is being used. 47 48 [1] Documentation/prctl/seccomp_filter.txt 49 50Original BPF paper: 51 52Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new 53architecture for user-level packet capture. In Proceedings of the 54USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993 55Conference Proceedings (USENIX'93). USENIX Association, Berkeley, 56CA, USA, 2-2. [http://www.tcpdump.org/papers/bpf-usenix93.pdf] 57 58Structure 59--------- 60 61User space applications include <linux/filter.h> which contains the 62following relevant structures: 63 64struct 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 71Such a structure is assembled as an array of 4-tuples, that contains 72a code, jt, jf and k value. jt and jf are jump offsets and k a generic 73value to be used for a provided code. 74 75struct sock_fprog { /* Required for SO_ATTACH_FILTER. */ 76 unsigned short len; /* Number of filter blocks */ 77 struct sock_filter __user *filter; 78}; 79 80For socket filtering, a pointer to this structure (as shown in 81follow-up example) is being passed to the kernel through setsockopt(2). 82 83Example 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 */ 93struct 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 120struct sock_fprog bpf = { 121 .len = ARRAY_SIZE(code), 122 .filter = code, 123}; 124 125sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL)); 126if (sock < 0) 127 /* ... bail out ... */ 128 129ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf)); 130if (ret < 0) 131 /* ... bail out ... */ 132 133/* ... */ 134close(sock); 135 136The above example code attaches a socket filter for a PF_PACKET socket 137in order to let all IPv4/IPv6 packets with port 22 pass. The rest will 138be dropped for this socket. 139 140The setsockopt(2) call to SO_DETACH_FILTER doesn't need any arguments 141and SO_LOCK_FILTER for preventing the filter to be detached, takes an 142integer value with 0 or 1. 143 144Note that socket filters are not restricted to PF_PACKET sockets only, 145but can also be used on other socket families. 146 147Summary 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 153Normally, most use cases for socket filtering on packet sockets will be 154covered by libpcap in high-level syntax, so as an application developer 155you should stick to that. libpcap wraps its own layer around all that. 156 157Unless i) using/linking to libpcap is not an option, ii) the required BPF 158filters use Linux extensions that are not supported by libpcap's compiler, 159iii) a filter might be more complex and not cleanly implementable with 160libpcap's compiler, or iv) particular filter codes should be optimized 161differently than libpcap's internal compiler does; then in such cases 162writing such a filter "by hand" can be of an alternative. For example, 163xt_bpf and cls_bpf users might have requirements that could result in 164more complex filter code, or one that cannot be expressed with libpcap 165(e.g. different return codes for various code paths). Moreover, BPF JIT 166implementors may wish to manually write test cases and thus need low-level 167access to BPF code as well. 168 169BPF engine and instruction set 170------------------------------ 171 172Under tools/net/ there's a small helper tool called bpf_asm which can 173be used to write low-level filters for example scenarios mentioned in the 174previous section. Asm-like syntax mentioned here has been implemented in 175bpf_asm and will be used for further explanations (instead of dealing with 176less readable opcodes directly, principles are the same). The syntax is 177closely modelled after Steven McCanne's and Van Jacobson's BPF paper. 178 179The 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 188A program, that is translated by bpf_asm into "opcodes" is an array that 189consists of the following elements (as already mentioned): 190 191 op:16, jt:8, jf:8, k:32 192 193The element op is a 16 bit wide opcode that has a particular instruction 194encoded. 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 196contains a miscellaneous argument that can be interpreted in different 197ways depending on the given instruction in op. 198 199The instruction set consists of load, store, branch, alu, miscellaneous 200and return instructions that are also represented in bpf_asm syntax. This 201table lists all bpf_asm instructions available resp. what their underlying 202opcodes 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 k == A 220 jneq 8 Jump on k != A 221 jne 8 Jump on k != A 222 jlt 8 Jump on k < A 223 jle 8 Jump on k <= A 224 jgt 7, 8 Jump on k > A 225 jge 7, 8 Jump on k >= A 226 jset 7, 8 Jump on k & A 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 0, 4 !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 245The 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 261The Linux kernel also has a couple of BPF extensions that are used along 262with the class of load instructions by "overloading" the k argument with 263a negative offset + a particular extension offset. The result of such BPF 264extensions are loaded into A. 265 266Possible 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 287These extensions can also be prefixed with '#'. 288Examples 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 343The above example code can be placed into a file (here called "foo"), and 344then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf 345and cls_bpf understands and can directly be loaded with. Example with above 346ARP code: 347 348$ ./bpf_asm foo 3494,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0, 350 351In 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 359In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF 360filters that might not be obvious at first, it's good to test filters before 361attaching to a live system. For that purpose, there's a small tool called 362bpf_dbg under tools/net/ in the kernel source directory. This debugger allows 363for testing BPF filters against given pcap files, single stepping through the 364BPF code on the pcap's packets and to do BPF machine register dumps. 365 366Starting bpf_dbg is trivial and just requires issuing: 367 368# ./bpf_dbg 369 370In case input and output do not equal stdin/stdout, bpf_dbg takes an 371alternative stdin source as a first argument, and an alternative stdout 372sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`. 373 374Other than that, a particular libreadline configuration can be set via 375file "~/.bpf_dbg_init" and the command history is stored in the file 376"~/.bpf_dbg_history". 377 378Interaction in bpf_dbg happens through a shell that also has auto-completion 379support (follow-up example commands starting with '>' denote bpf_dbg shell). 380The 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>] 393bpf 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 398l0: ldh [12] 399l1: jeq #0x800, l2, l5 400l2: ldb [23] 401l3: jeq #0x1, l4, l5 402l4: ret #0xffff 403l5: 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 417breakpoint at: l0: ldh [12] 418> breakpoint 1 419breakpoint 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 443breakpoints: 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 462JIT compiler 463------------ 464 465The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC, PowerPC, 466ARM, ARM64, MIPS and s390 and can be enabled through CONFIG_BPF_JIT. The JIT 467compiler is transparently invoked for each attached filter from user space 468or for internal kernel users if it has been previously enabled by root: 469 470 echo 1 > /proc/sys/net/core/bpf_jit_enable 471 472For JIT developers, doing audits etc, each compile run can output the generated 473opcode image into the kernel log via: 474 475 echo 2 > /proc/sys/net/core/bpf_jit_enable 476 477Example 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 486In the kernel source tree under tools/net/, there's bpf_jit_disasm for 487generating disassembly out of the kernel log's hexdump: 488 489# ./bpf_jit_disasm 49070 bytes emitted from JIT compiler (pass:3, flen:6) 491ffffffffa0069c8f + <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 513Issuing option `-o` will "annotate" opcodes to resulting assembler 514instructions, which can be very useful for JIT developers: 515 516# ./bpf_jit_disasm -o 51770 bytes emitted from JIT compiler (pass:3, flen:6) 518ffffffffa0069c8f + <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 560For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful 561toolchain for developing and testing the kernel's JIT compiler. 562 563BPF kernel internals 564-------------------- 565Internally, for the kernel interpreter, a different instruction set 566format with similar underlying principles from BPF described in previous 567paragraphs is being used. However, the instruction set format is modelled 568closer to the underlying architecture to mimic native instruction sets, so 569that a better performance can be achieved (more details later). This new 570ISA is called 'eBPF' or 'internal BPF' interchangeably. (Note: eBPF which 571originates from [e]xtended BPF is not the same as BPF extensions! While 572eBPF is an ISA, BPF extensions date back to classic BPF's 'overloading' 573of BPF_LD | BPF_{B,H,W} | BPF_ABS instruction.) 574 575It is designed to be JITed with one to one mapping, which can also open up 576the possibility for GCC/LLVM compilers to generate optimized eBPF code through 577an eBPF backend that performs almost as fast as natively compiled code. 578 579The new instruction set was originally designed with the possible goal in 580mind to write programs in "restricted C" and compile into eBPF with a optional 581GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with 582minimal performance overhead over two steps, that is, C -> eBPF -> native code. 583 584Currently, the new format is being used for running user BPF programs, which 585includes seccomp BPF, classic socket filters, cls_bpf traffic classifier, 586team driver's classifier for its load-balancing mode, netfilter's xt_bpf 587extension, PTP dissector/classifier, and much more. They are all internally 588converted by the kernel into the new instruction set representation and run 589in the eBPF interpreter. For in-kernel handlers, this all works transparently 590by using bpf_prog_create() for setting up the filter, resp. 591bpf_prog_destroy() for destroying it. The macro 592BPF_PROG_RUN(filter, ctx) transparently invokes eBPF interpreter or JITed 593code to run the filter. 'filter' is a pointer to struct bpf_prog that we 594got from bpf_prog_create(), and 'ctx' the given context (e.g. 595skb pointer). All constraints and restrictions from bpf_check_classic() apply 596before a conversion to the new layout is being done behind the scenes! 597 598Currently, the classic BPF format is being used for JITing on most of the 599architectures. x86-64, aarch64 and s390x perform JIT compilation from eBPF 600instruction set, however, future work will migrate other JIT compilers as well, 601so that they will profit from the very same benefits. 602 603Some core changes of the new internal format: 604 605- Number of registers increase from 2 to 10: 606 607 The old format had two registers A and X, and a hidden frame pointer. The 608 new layout extends this to be 10 internal registers and a read-only frame 609 pointer. Since 64-bit CPUs are passing arguments to functions via registers 610 the number of args from eBPF program to in-kernel function is restricted 611 to 5 and one register is used to accept return value from an in-kernel 612 function. Natively, x86_64 passes first 6 arguments in registers, aarch64/ 613 sparcv9/mips64 have 7 - 8 registers for arguments; x86_64 has 6 callee saved 614 registers, and aarch64/sparcv9/mips64 have 11 or more callee saved registers. 615 616 Therefore, eBPF calling convention is defined as: 617 618 * R0 - return value from in-kernel function, and exit value for eBPF program 619 * R1 - R5 - arguments from eBPF program to in-kernel function 620 * R6 - R9 - callee saved registers that in-kernel function will preserve 621 * R10 - read-only frame pointer to access stack 622 623 Thus, all eBPF registers map one to one to HW registers on x86_64, aarch64, 624 etc, and eBPF calling convention maps directly to ABIs used by the kernel on 625 64-bit architectures. 626 627 On 32-bit architectures JIT may map programs that use only 32-bit arithmetic 628 and may let more complex programs to be interpreted. 629 630 R0 - R5 are scratch registers and eBPF program needs spill/fill them if 631 necessary across calls. Note that there is only one eBPF program (== one 632 eBPF main routine) and it cannot call other eBPF functions, it can only 633 call predefined in-kernel functions, though. 634 635- Register width increases from 32-bit to 64-bit: 636 637 Still, the semantics of the original 32-bit ALU operations are preserved 638 via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower 639 subregisters that zero-extend into 64-bit if they are being written to. 640 That behavior maps directly to x86_64 and arm64 subregister definition, but 641 makes other JITs more difficult. 642 643 32-bit architectures run 64-bit internal BPF programs via interpreter. 644 Their JITs may convert BPF programs that only use 32-bit subregisters into 645 native instruction set and let the rest being interpreted. 646 647 Operation is 64-bit, because on 64-bit architectures, pointers are also 648 64-bit wide, and we want to pass 64-bit values in/out of kernel functions, 649 so 32-bit eBPF registers would otherwise require to define register-pair 650 ABI, thus, there won't be able to use a direct eBPF register to HW register 651 mapping and JIT would need to do combine/split/move operations for every 652 register in and out of the function, which is complex, bug prone and slow. 653 Another reason is the use of atomic 64-bit counters. 654 655- Conditional jt/jf targets replaced with jt/fall-through: 656 657 While the original design has constructs such as "if (cond) jump_true; 658 else jump_false;", they are being replaced into alternative constructs like 659 "if (cond) jump_true; /* else fall-through */". 660 661- Introduces bpf_call insn and register passing convention for zero overhead 662 calls from/to other kernel functions: 663 664 Before an in-kernel function call, the internal BPF program needs to 665 place function arguments into R1 to R5 registers to satisfy calling 666 convention, then the interpreter will take them from registers and pass 667 to in-kernel function. If R1 - R5 registers are mapped to CPU registers 668 that are used for argument passing on given architecture, the JIT compiler 669 doesn't need to emit extra moves. Function arguments will be in the correct 670 registers and BPF_CALL instruction will be JITed as single 'call' HW 671 instruction. This calling convention was picked to cover common call 672 situations without performance penalty. 673 674 After an in-kernel function call, R1 - R5 are reset to unreadable and R0 has 675 a return value of the function. Since R6 - R9 are callee saved, their state 676 is preserved across the call. 677 678 For example, consider three C functions: 679 680 u64 f1() { return (*_f2)(1); } 681 u64 f2(u64 a) { return f3(a + 1, a); } 682 u64 f3(u64 a, u64 b) { return a - b; } 683 684 GCC can compile f1, f3 into x86_64: 685 686 f1: 687 movl $1, %edi 688 movq _f2(%rip), %rax 689 jmp *%rax 690 f3: 691 movq %rdi, %rax 692 subq %rsi, %rax 693 ret 694 695 Function f2 in eBPF may look like: 696 697 f2: 698 bpf_mov R2, R1 699 bpf_add R1, 1 700 bpf_call f3 701 bpf_exit 702 703 If f2 is JITed and the pointer stored to '_f2'. The calls f1 -> f2 -> f3 and 704 returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to 705 be used to call into f2. 706 707 For practical reasons all eBPF programs have only one argument 'ctx' which is 708 already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs 709 can call kernel functions with up to 5 arguments. Calls with 6 or more arguments 710 are currently not supported, but these restrictions can be lifted if necessary 711 in the future. 712 713 On 64-bit architectures all register map to HW registers one to one. For 714 example, x86_64 JIT compiler can map them as ... 715 716 R0 - rax 717 R1 - rdi 718 R2 - rsi 719 R3 - rdx 720 R4 - rcx 721 R5 - r8 722 R6 - rbx 723 R7 - r13 724 R8 - r14 725 R9 - r15 726 R10 - rbp 727 728 ... since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing 729 and rbx, r12 - r15 are callee saved. 730 731 Then the following internal BPF pseudo-program: 732 733 bpf_mov R6, R1 /* save ctx */ 734 bpf_mov R2, 2 735 bpf_mov R3, 3 736 bpf_mov R4, 4 737 bpf_mov R5, 5 738 bpf_call foo 739 bpf_mov R7, R0 /* save foo() return value */ 740 bpf_mov R1, R6 /* restore ctx for next call */ 741 bpf_mov R2, 6 742 bpf_mov R3, 7 743 bpf_mov R4, 8 744 bpf_mov R5, 9 745 bpf_call bar 746 bpf_add R0, R7 747 bpf_exit 748 749 After JIT to x86_64 may look like: 750 751 push %rbp 752 mov %rsp,%rbp 753 sub $0x228,%rsp 754 mov %rbx,-0x228(%rbp) 755 mov %r13,-0x220(%rbp) 756 mov %rdi,%rbx 757 mov $0x2,%esi 758 mov $0x3,%edx 759 mov $0x4,%ecx 760 mov $0x5,%r8d 761 callq foo 762 mov %rax,%r13 763 mov %rbx,%rdi 764 mov $0x2,%esi 765 mov $0x3,%edx 766 mov $0x4,%ecx 767 mov $0x5,%r8d 768 callq bar 769 add %r13,%rax 770 mov -0x228(%rbp),%rbx 771 mov -0x220(%rbp),%r13 772 leaveq 773 retq 774 775 Which is in this example equivalent in C to: 776 777 u64 bpf_filter(u64 ctx) 778 { 779 return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9); 780 } 781 782 In-kernel functions foo() and bar() with prototype: u64 (*)(u64 arg1, u64 783 arg2, u64 arg3, u64 arg4, u64 arg5); will receive arguments in proper 784 registers and place their return value into '%rax' which is R0 in eBPF. 785 Prologue and epilogue are emitted by JIT and are implicit in the 786 interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve 787 them across the calls as defined by calling convention. 788 789 For example the following program is invalid: 790 791 bpf_mov R1, 1 792 bpf_call foo 793 bpf_mov R0, R1 794 bpf_exit 795 796 After the call the registers R1-R5 contain junk values and cannot be read. 797 In the future an eBPF verifier can be used to validate internal BPF programs. 798 799Also in the new design, eBPF is limited to 4096 insns, which means that any 800program will terminate quickly and will only call a fixed number of kernel 801functions. Original BPF and the new format are two operand instructions, 802which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT. 803 804The input context pointer for invoking the interpreter function is generic, 805its content is defined by a specific use case. For seccomp register R1 points 806to seccomp_data, for converted BPF filters R1 points to a skb. 807 808A program, that is translated internally consists of the following elements: 809 810 op:16, jt:8, jf:8, k:32 ==> op:8, dst_reg:4, src_reg:4, off:16, imm:32 811 812So far 87 internal BPF instructions were implemented. 8-bit 'op' opcode field 813has room for new instructions. Some of them may use 16/24/32 byte encoding. New 814instructions must be multiple of 8 bytes to preserve backward compatibility. 815 816Internal BPF is a general purpose RISC instruction set. Not every register and 817every instruction are used during translation from original BPF to new format. 818For example, socket filters are not using 'exclusive add' instruction, but 819tracing filters may do to maintain counters of events, for example. Register R9 820is not used by socket filters either, but more complex filters may be running 821out of registers and would have to resort to spill/fill to stack. 822 823Internal BPF can used as generic assembler for last step performance 824optimizations, socket filters and seccomp are using it as assembler. Tracing 825filters may use it as assembler to generate code from kernel. In kernel usage 826may not be bounded by security considerations, since generated internal BPF code 827may be optimizing internal code path and not being exposed to the user space. 828Safety of internal BPF can come from a verifier (TBD). In such use cases as 829described, it may be used as safe instruction set. 830 831Just like the original BPF, the new format runs within a controlled environment, 832is deterministic and the kernel can easily prove that. The safety of the program 833can be determined in two steps: first step does depth-first-search to disallow 834loops and other CFG validation; second step starts from the first insn and 835descends all possible paths. It simulates execution of every insn and observes 836the state change of registers and stack. 837 838eBPF opcode encoding 839-------------------- 840 841eBPF is reusing most of the opcode encoding from classic to simplify conversion 842of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code' 843field is divided into three parts: 844 845 +----------------+--------+--------------------+ 846 | 4 bits | 1 bit | 3 bits | 847 | operation code | source | instruction class | 848 +----------------+--------+--------------------+ 849 (MSB) (LSB) 850 851Three LSB bits store instruction class which is one of: 852 853 Classic BPF classes: eBPF classes: 854 855 BPF_LD 0x00 BPF_LD 0x00 856 BPF_LDX 0x01 BPF_LDX 0x01 857 BPF_ST 0x02 BPF_ST 0x02 858 BPF_STX 0x03 BPF_STX 0x03 859 BPF_ALU 0x04 BPF_ALU 0x04 860 BPF_JMP 0x05 BPF_JMP 0x05 861 BPF_RET 0x06 [ class 6 unused, for future if needed ] 862 BPF_MISC 0x07 BPF_ALU64 0x07 863 864When BPF_CLASS(code) == BPF_ALU or BPF_JMP, 4th bit encodes source operand ... 865 866 BPF_K 0x00 867 BPF_X 0x08 868 869 * in classic BPF, this means: 870 871 BPF_SRC(code) == BPF_X - use register X as source operand 872 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand 873 874 * in eBPF, this means: 875 876 BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand 877 BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand 878 879... and four MSB bits store operation code. 880 881If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of: 882 883 BPF_ADD 0x00 884 BPF_SUB 0x10 885 BPF_MUL 0x20 886 BPF_DIV 0x30 887 BPF_OR 0x40 888 BPF_AND 0x50 889 BPF_LSH 0x60 890 BPF_RSH 0x70 891 BPF_NEG 0x80 892 BPF_MOD 0x90 893 BPF_XOR 0xa0 894 BPF_MOV 0xb0 /* eBPF only: mov reg to reg */ 895 BPF_ARSH 0xc0 /* eBPF only: sign extending shift right */ 896 BPF_END 0xd0 /* eBPF only: endianness conversion */ 897 898If BPF_CLASS(code) == BPF_JMP, BPF_OP(code) is one of: 899 900 BPF_JA 0x00 901 BPF_JEQ 0x10 902 BPF_JGT 0x20 903 BPF_JGE 0x30 904 BPF_JSET 0x40 905 BPF_JNE 0x50 /* eBPF only: jump != */ 906 BPF_JSGT 0x60 /* eBPF only: signed '>' */ 907 BPF_JSGE 0x70 /* eBPF only: signed '>=' */ 908 BPF_CALL 0x80 /* eBPF only: function call */ 909 BPF_EXIT 0x90 /* eBPF only: function return */ 910 911So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF 912and eBPF. There are only two registers in classic BPF, so it means A += X. 913In eBPF it means dst_reg = (u32) dst_reg + (u32) src_reg; similarly, 914BPF_XOR | BPF_K | BPF_ALU means A ^= imm32 in classic BPF and analogous 915src_reg = (u32) src_reg ^ (u32) imm32 in eBPF. 916 917Classic BPF is using BPF_MISC class to represent A = X and X = A moves. 918eBPF is using BPF_MOV | BPF_X | BPF_ALU code instead. Since there are no 919BPF_MISC operations in eBPF, the class 7 is used as BPF_ALU64 to mean 920exactly the same operations as BPF_ALU, but with 64-bit wide operands 921instead. So BPF_ADD | BPF_X | BPF_ALU64 means 64-bit addition, i.e.: 922dst_reg = dst_reg + src_reg 923 924Classic BPF wastes the whole BPF_RET class to represent a single 'ret' 925operation. Classic BPF_RET | BPF_K means copy imm32 into return register 926and perform function exit. eBPF is modeled to match CPU, so BPF_JMP | BPF_EXIT 927in eBPF means function exit only. The eBPF program needs to store return 928value into register R0 before doing a BPF_EXIT. Class 6 in eBPF is currently 929unused and reserved for future use. 930 931For load and store instructions the 8-bit 'code' field is divided as: 932 933 +--------+--------+-------------------+ 934 | 3 bits | 2 bits | 3 bits | 935 | mode | size | instruction class | 936 +--------+--------+-------------------+ 937 (MSB) (LSB) 938 939Size modifier is one of ... 940 941 BPF_W 0x00 /* word */ 942 BPF_H 0x08 /* half word */ 943 BPF_B 0x10 /* byte */ 944 BPF_DW 0x18 /* eBPF only, double word */ 945 946... which encodes size of load/store operation: 947 948 B - 1 byte 949 H - 2 byte 950 W - 4 byte 951 DW - 8 byte (eBPF only) 952 953Mode modifier is one of: 954 955 BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */ 956 BPF_ABS 0x20 957 BPF_IND 0x40 958 BPF_MEM 0x60 959 BPF_LEN 0x80 /* classic BPF only, reserved in eBPF */ 960 BPF_MSH 0xa0 /* classic BPF only, reserved in eBPF */ 961 BPF_XADD 0xc0 /* eBPF only, exclusive add */ 962 963eBPF has two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and 964(BPF_IND | <size> | BPF_LD) which are used to access packet data. 965 966They had to be carried over from classic to have strong performance of 967socket filters running in eBPF interpreter. These instructions can only 968be used when interpreter context is a pointer to 'struct sk_buff' and 969have seven implicit operands. Register R6 is an implicit input that must 970contain pointer to sk_buff. Register R0 is an implicit output which contains 971the data fetched from the packet. Registers R1-R5 are scratch registers 972and must not be used to store the data across BPF_ABS | BPF_LD or 973BPF_IND | BPF_LD instructions. 974 975These instructions have implicit program exit condition as well. When 976eBPF program is trying to access the data beyond the packet boundary, 977the interpreter will abort the execution of the program. JIT compilers 978therefore must preserve this property. src_reg and imm32 fields are 979explicit inputs to these instructions. 980 981For example: 982 983 BPF_IND | BPF_W | BPF_LD means: 984 985 R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32)) 986 and R1 - R5 were scratched. 987 988Unlike classic BPF instruction set, eBPF has generic load/store operations: 989 990BPF_MEM | <size> | BPF_STX: *(size *) (dst_reg + off) = src_reg 991BPF_MEM | <size> | BPF_ST: *(size *) (dst_reg + off) = imm32 992BPF_MEM | <size> | BPF_LDX: dst_reg = *(size *) (src_reg + off) 993BPF_XADD | BPF_W | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg 994BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg 995 996Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and 9972 byte atomic increments are not supported. 998 999eBPF has one 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM which consists 1000of two consecutive 'struct bpf_insn' 8-byte blocks and interpreted as single 1001instruction that loads 64-bit immediate value into a dst_reg. 1002Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads 100332-bit immediate value into a register. 1004 1005eBPF verifier 1006------------- 1007The safety of the eBPF program is determined in two steps. 1008 1009First step does DAG check to disallow loops and other CFG validation. 1010In particular it will detect programs that have unreachable instructions. 1011(though classic BPF checker allows them) 1012 1013Second step starts from the first insn and descends all possible paths. 1014It simulates execution of every insn and observes the state change of 1015registers and stack. 1016 1017At the start of the program the register R1 contains a pointer to context 1018and has type PTR_TO_CTX. 1019If verifier sees an insn that does R2=R1, then R2 has now type 1020PTR_TO_CTX as well and can be used on the right hand side of expression. 1021If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=UNKNOWN_VALUE, 1022since addition of two valid pointers makes invalid pointer. 1023(In 'secure' mode verifier will reject any type of pointer arithmetic to make 1024sure that kernel addresses don't leak to unprivileged users) 1025 1026If register was never written to, it's not readable: 1027 bpf_mov R0 = R2 1028 bpf_exit 1029will be rejected, since R2 is unreadable at the start of the program. 1030 1031After kernel function call, R1-R5 are reset to unreadable and 1032R0 has a return type of the function. 1033 1034Since R6-R9 are callee saved, their state is preserved across the call. 1035 bpf_mov R6 = 1 1036 bpf_call foo 1037 bpf_mov R0 = R6 1038 bpf_exit 1039is a correct program. If there was R1 instead of R6, it would have 1040been rejected. 1041 1042load/store instructions are allowed only with registers of valid types, which 1043are PTR_TO_CTX, PTR_TO_MAP, FRAME_PTR. They are bounds and alignment checked. 1044For example: 1045 bpf_mov R1 = 1 1046 bpf_mov R2 = 2 1047 bpf_xadd *(u32 *)(R1 + 3) += R2 1048 bpf_exit 1049will be rejected, since R1 doesn't have a valid pointer type at the time of 1050execution of instruction bpf_xadd. 1051 1052At the start R1 type is PTR_TO_CTX (a pointer to generic 'struct bpf_context') 1053A callback is used to customize verifier to restrict eBPF program access to only 1054certain fields within ctx structure with specified size and alignment. 1055 1056For example, the following insn: 1057 bpf_ld R0 = *(u32 *)(R6 + 8) 1058intends to load a word from address R6 + 8 and store it into R0 1059If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know 1060that offset 8 of size 4 bytes can be accessed for reading, otherwise 1061the verifier will reject the program. 1062If R6=FRAME_PTR, then access should be aligned and be within 1063stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8, 1064so it will fail verification, since it's out of bounds. 1065 1066The verifier will allow eBPF program to read data from stack only after 1067it wrote into it. 1068Classic BPF verifier does similar check with M[0-15] memory slots. 1069For example: 1070 bpf_ld R0 = *(u32 *)(R10 - 4) 1071 bpf_exit 1072is invalid program. 1073Though R10 is correct read-only register and has type FRAME_PTR 1074and R10 - 4 is within stack bounds, there were no stores into that location. 1075 1076Pointer register spill/fill is tracked as well, since four (R6-R9) 1077callee saved registers may not be enough for some programs. 1078 1079Allowed function calls are customized with bpf_verifier_ops->get_func_proto() 1080The eBPF verifier will check that registers match argument constraints. 1081After the call register R0 will be set to return type of the function. 1082 1083Function calls is a main mechanism to extend functionality of eBPF programs. 1084Socket filters may let programs to call one set of functions, whereas tracing 1085filters may allow completely different set. 1086 1087If a function made accessible to eBPF program, it needs to be thought through 1088from safety point of view. The verifier will guarantee that the function is 1089called with valid arguments. 1090 1091seccomp vs socket filters have different security restrictions for classic BPF. 1092Seccomp solves this by two stage verifier: classic BPF verifier is followed 1093by seccomp verifier. In case of eBPF one configurable verifier is shared for 1094all use cases. 1095 1096See details of eBPF verifier in kernel/bpf/verifier.c 1097 1098eBPF maps 1099--------- 1100'maps' is a generic storage of different types for sharing data between kernel 1101and userspace. 1102 1103The maps are accessed from user space via BPF syscall, which has commands: 1104- create a map with given type and attributes 1105 map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) 1106 using attr->map_type, attr->key_size, attr->value_size, attr->max_entries 1107 returns process-local file descriptor or negative error 1108 1109- lookup key in a given map 1110 err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) 1111 using attr->map_fd, attr->key, attr->value 1112 returns zero and stores found elem into value or negative error 1113 1114- create or update key/value pair in a given map 1115 err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) 1116 using attr->map_fd, attr->key, attr->value 1117 returns zero or negative error 1118 1119- find and delete element by key in a given map 1120 err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) 1121 using attr->map_fd, attr->key 1122 1123- to delete map: close(fd) 1124 Exiting process will delete maps automatically 1125 1126userspace programs use this syscall to create/access maps that eBPF programs 1127are concurrently updating. 1128 1129maps can have different types: hash, array, bloom filter, radix-tree, etc. 1130 1131The map is defined by: 1132 . type 1133 . max number of elements 1134 . key size in bytes 1135 . value size in bytes 1136 1137Understanding eBPF verifier messages 1138------------------------------------ 1139 1140The following are few examples of invalid eBPF programs and verifier error 1141messages as seen in the log: 1142 1143Program with unreachable instructions: 1144static struct bpf_insn prog[] = { 1145 BPF_EXIT_INSN(), 1146 BPF_EXIT_INSN(), 1147}; 1148Error: 1149 unreachable insn 1 1150 1151Program that reads uninitialized register: 1152 BPF_MOV64_REG(BPF_REG_0, BPF_REG_2), 1153 BPF_EXIT_INSN(), 1154Error: 1155 0: (bf) r0 = r2 1156 R2 !read_ok 1157 1158Program that doesn't initialize R0 before exiting: 1159 BPF_MOV64_REG(BPF_REG_2, BPF_REG_1), 1160 BPF_EXIT_INSN(), 1161Error: 1162 0: (bf) r2 = r1 1163 1: (95) exit 1164 R0 !read_ok 1165 1166Program that accesses stack out of bounds: 1167 BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0), 1168 BPF_EXIT_INSN(), 1169Error: 1170 0: (7a) *(u64 *)(r10 +8) = 0 1171 invalid stack off=8 size=8 1172 1173Program that doesn't initialize stack before passing its address into function: 1174 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), 1175 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), 1176 BPF_LD_MAP_FD(BPF_REG_1, 0), 1177 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), 1178 BPF_EXIT_INSN(), 1179Error: 1180 0: (bf) r2 = r10 1181 1: (07) r2 += -8 1182 2: (b7) r1 = 0x0 1183 3: (85) call 1 1184 invalid indirect read from stack off -8+0 size 8 1185 1186Program that uses invalid map_fd=0 while calling to map_lookup_elem() function: 1187 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), 1188 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), 1189 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), 1190 BPF_LD_MAP_FD(BPF_REG_1, 0), 1191 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), 1192 BPF_EXIT_INSN(), 1193Error: 1194 0: (7a) *(u64 *)(r10 -8) = 0 1195 1: (bf) r2 = r10 1196 2: (07) r2 += -8 1197 3: (b7) r1 = 0x0 1198 4: (85) call 1 1199 fd 0 is not pointing to valid bpf_map 1200 1201Program that doesn't check return value of map_lookup_elem() before accessing 1202map element: 1203 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), 1204 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), 1205 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), 1206 BPF_LD_MAP_FD(BPF_REG_1, 0), 1207 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), 1208 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0), 1209 BPF_EXIT_INSN(), 1210Error: 1211 0: (7a) *(u64 *)(r10 -8) = 0 1212 1: (bf) r2 = r10 1213 2: (07) r2 += -8 1214 3: (b7) r1 = 0x0 1215 4: (85) call 1 1216 5: (7a) *(u64 *)(r0 +0) = 0 1217 R0 invalid mem access 'map_value_or_null' 1218 1219Program that correctly checks map_lookup_elem() returned value for NULL, but 1220accesses the memory with incorrect alignment: 1221 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), 1222 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), 1223 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), 1224 BPF_LD_MAP_FD(BPF_REG_1, 0), 1225 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), 1226 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1), 1227 BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0), 1228 BPF_EXIT_INSN(), 1229Error: 1230 0: (7a) *(u64 *)(r10 -8) = 0 1231 1: (bf) r2 = r10 1232 2: (07) r2 += -8 1233 3: (b7) r1 = 1 1234 4: (85) call 1 1235 5: (15) if r0 == 0x0 goto pc+1 1236 R0=map_ptr R10=fp 1237 6: (7a) *(u64 *)(r0 +4) = 0 1238 misaligned access off 4 size 8 1239 1240Program that correctly checks map_lookup_elem() returned value for NULL and 1241accesses memory with correct alignment in one side of 'if' branch, but fails 1242to do so in the other side of 'if' branch: 1243 BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), 1244 BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), 1245 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), 1246 BPF_LD_MAP_FD(BPF_REG_1, 0), 1247 BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), 1248 BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), 1249 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0), 1250 BPF_EXIT_INSN(), 1251 BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1), 1252 BPF_EXIT_INSN(), 1253Error: 1254 0: (7a) *(u64 *)(r10 -8) = 0 1255 1: (bf) r2 = r10 1256 2: (07) r2 += -8 1257 3: (b7) r1 = 1 1258 4: (85) call 1 1259 5: (15) if r0 == 0x0 goto pc+2 1260 R0=map_ptr R10=fp 1261 6: (7a) *(u64 *)(r0 +0) = 0 1262 7: (95) exit 1263 1264 from 5 to 8: R0=imm0 R10=fp 1265 8: (7a) *(u64 *)(r0 +0) = 1 1266 R0 invalid mem access 'imm' 1267 1268Testing 1269------- 1270 1271Next to the BPF toolchain, the kernel also ships a test module that contains 1272various test cases for classic and internal BPF that can be executed against 1273the BPF interpreter and JIT compiler. It can be found in lib/test_bpf.c and 1274enabled via Kconfig: 1275 1276 CONFIG_TEST_BPF=m 1277 1278After the module has been built and installed, the test suite can be executed 1279via insmod or modprobe against 'test_bpf' module. Results of the test cases 1280including timings in nsec can be found in the kernel log (dmesg). 1281 1282Misc 1283---- 1284 1285Also trinity, the Linux syscall fuzzer, has built-in support for BPF and 1286SECCOMP-BPF kernel fuzzing. 1287 1288Written by 1289---------- 1290 1291The document was written in the hope that it is found useful and in order 1292to give potential BPF hackers or security auditors a better overview of 1293the underlying architecture. 1294 1295Jay Schulist <jschlst@samba.org> 1296Daniel Borkmann <dborkman@redhat.com> 1297Alexei Starovoitov <ast@plumgrid.com> 1298