Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 1 | Linux Socket Filtering aka Berkeley Packet Filter (BPF) |
| 2 | ======================================================= |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 3 | |
| 4 | Introduction |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 5 | ------------ |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 6 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 11 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 16 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 22 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 31 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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. |
Vincent Bernat | d59577b | 2013-01-16 22:55:49 +0100 | [diff] [blame] | 36 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 42 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 47 | |
Pavel Machek | 2130c02 | 2017-09-16 16:28:02 +0200 | [diff] [blame] | 48 | [1] Documentation/userspace-api/seccomp_filter.rst |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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 |
Daniel Borkmann | 9295c03 | 2016-05-16 23:06:53 +0200 | [diff] [blame] | 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 |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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> |
Dave Anderson | 83d26b6 | 2016-03-28 14:56:47 -0700 | [diff] [blame] | 233 | neg !A |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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 |
Tobias Klauser | b0db5cd | 2014-05-20 13:52:13 +0200 | [diff] [blame] | 280 | rxhash skb->hash |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 281 | cpu raw_smp_processor_id() |
Jiri Pirko | df8a39de | 2015-01-13 17:13:44 +0100 | [diff] [blame] | 282 | vlan_tci skb_vlan_tag_get(skb) |
Michal Sekletar | 27cd545 | 2015-03-24 14:48:41 +0100 | [diff] [blame] | 283 | vlan_avail skb_vlan_tag_present(skb) |
| 284 | vlan_tpid skb->vlan_proto |
Chema Gonzalez | 4cd3675 | 2014-04-21 09:21:24 -0700 | [diff] [blame] | 285 | rand prandom_u32() |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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 | |
Chema Gonzalez | 4cd3675 | 2014-04-21 09:21:24 -0700 | [diff] [blame] | 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 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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 */ |
Kees Cook | fd76875 | 2017-08-11 12:53:18 -0700 | [diff] [blame] | 340 | bad: ret #0 /* SECCOMP_RET_KILL_THREAD */ |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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, |
Linus Torvalds | 6325e94 | 2014-10-08 05:34:24 -0400 | [diff] [blame] | 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: |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 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 | |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 563 | BPF kernel internals |
| 564 | -------------------- |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 565 | Internally, for the kernel interpreter, a different instruction set |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 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.) |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 574 | |
| 575 | It is designed to be JITed with one to one mapping, which can also open up |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 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. |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 578 | |
| 579 | The new instruction set was originally designed with the possible goal in |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 580 | mind to write programs in "restricted C" and compile into eBPF with a optional |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 581 | GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 582 | minimal performance overhead over two steps, that is, C -> eBPF -> native code. |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 589 | in the eBPF interpreter. For in-kernel handlers, this all works transparently |
Alexei Starovoitov | 7ae457c | 2014-07-30 20:34:16 -0700 | [diff] [blame] | 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. |
Alexei Starovoitov | 4df95ff | 2014-07-30 20:34:14 -0700 | [diff] [blame] | 595 | skb pointer). All constraints and restrictions from bpf_check_classic() apply |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 596 | before a conversion to the new layout is being done behind the scenes! |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 597 | |
Alexei Starovoitov | e2989ee | 2017-04-23 09:01:00 -0700 | [diff] [blame] | 598 | Currently, the classic BPF format is being used for JITing on most 32-bit |
Shubham Bansal | d2aaa3d | 2017-08-23 21:29:10 +0530 | [diff] [blame] | 599 | architectures, whereas x86-64, aarch64, s390x, powerpc64, sparc64, arm32 perform |
| 600 | JIT compilation from eBPF instruction set. |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 609 | the number of args from eBPF program to in-kernel function is restricted |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 | |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 615 | Therefore, eBPF calling convention is defined as: |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 616 | |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 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 |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 619 | * R6 - R9 - callee saved registers that in-kernel function will preserve |
| 620 | * R10 - read-only frame pointer to access stack |
| 621 | |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 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 |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 | |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 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. |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 637 | via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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, |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 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 |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 | |
Alexei Starovoitov | dfee07c | 2014-05-01 08:16:03 -0700 | [diff] [blame] | 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 | |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 694 | Function f2 in eBPF may look like: |
Alexei Starovoitov | dfee07c | 2014-05-01 08:16:03 -0700 | [diff] [blame] | 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 |
Li RongQing | 1a9525f | 2014-10-10 11:36:54 +0800 | [diff] [blame] | 703 | returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to |
Alexei Starovoitov | dfee07c | 2014-05-01 08:16:03 -0700 | [diff] [blame] | 704 | be used to call into f2. |
| 705 | |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 706 | For practical reasons all eBPF programs have only one argument 'ctx' which is |
Li RongQing | 1a9525f | 2014-10-10 11:36:54 +0800 | [diff] [blame] | 707 | already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs |
Alexei Starovoitov | dfee07c | 2014-05-01 08:16:03 -0700 | [diff] [blame] | 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 |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 783 | registers and place their return value into '%rax' which is R0 in eBPF. |
Alexei Starovoitov | dfee07c | 2014-05-01 08:16:03 -0700 | [diff] [blame] | 784 | Prologue and epilogue are emitted by JIT and are implicit in the |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 785 | interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve |
Alexei Starovoitov | dfee07c | 2014-05-01 08:16:03 -0700 | [diff] [blame] | 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. |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 796 | An in-kernel eBPF verifier is used to validate internal BPF programs. |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 797 | |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 798 | Also in the new design, eBPF is limited to 4096 insns, which means that any |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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, |
Alexei Starovoitov | e4ad403 | 2014-06-10 17:44:06 +0200 | [diff] [blame] | 801 | which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT. |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 | |
Alexei Starovoitov | e430f34 | 2014-06-06 14:46:06 -0700 | [diff] [blame] | 809 | op:16, jt:8, jf:8, k:32 ==> op:8, dst_reg:4, src_reg:4, off:16, imm:32 |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 810 | |
Alexei Starovoitov | dfee07c | 2014-05-01 08:16:03 -0700 | [diff] [blame] | 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 | |
Alexei Starovoitov | 9a985cd | 2014-03-28 18:58:26 +0100 | [diff] [blame] | 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 | |
Alexei Starovoitov | 783e327b | 2014-06-10 17:44:07 +0200 | [diff] [blame] | 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 */ |
Daniel Borkmann | 92b31a9 | 2017-08-10 01:39:55 +0200 | [diff] [blame] | 909 | BPF_JLT 0xa0 /* eBPF only: unsigned '<' */ |
| 910 | BPF_JLE 0xb0 /* eBPF only: unsigned '<=' */ |
| 911 | BPF_JSLT 0xc0 /* eBPF only: signed '<' */ |
| 912 | BPF_JSLE 0xd0 /* eBPF only: signed '<=' */ |
Alexei Starovoitov | 783e327b | 2014-06-10 17:44:07 +0200 | [diff] [blame] | 913 | |
| 914 | So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF |
| 915 | and eBPF. There are only two registers in classic BPF, so it means A += X. |
| 916 | In eBPF it means dst_reg = (u32) dst_reg + (u32) src_reg; similarly, |
| 917 | BPF_XOR | BPF_K | BPF_ALU means A ^= imm32 in classic BPF and analogous |
| 918 | src_reg = (u32) src_reg ^ (u32) imm32 in eBPF. |
| 919 | |
| 920 | Classic BPF is using BPF_MISC class to represent A = X and X = A moves. |
| 921 | eBPF is using BPF_MOV | BPF_X | BPF_ALU code instead. Since there are no |
| 922 | BPF_MISC operations in eBPF, the class 7 is used as BPF_ALU64 to mean |
| 923 | exactly the same operations as BPF_ALU, but with 64-bit wide operands |
| 924 | instead. So BPF_ADD | BPF_X | BPF_ALU64 means 64-bit addition, i.e.: |
| 925 | dst_reg = dst_reg + src_reg |
| 926 | |
| 927 | Classic BPF wastes the whole BPF_RET class to represent a single 'ret' |
| 928 | operation. Classic BPF_RET | BPF_K means copy imm32 into return register |
| 929 | and perform function exit. eBPF is modeled to match CPU, so BPF_JMP | BPF_EXIT |
| 930 | in eBPF means function exit only. The eBPF program needs to store return |
| 931 | value into register R0 before doing a BPF_EXIT. Class 6 in eBPF is currently |
| 932 | unused and reserved for future use. |
| 933 | |
| 934 | For load and store instructions the 8-bit 'code' field is divided as: |
| 935 | |
| 936 | +--------+--------+-------------------+ |
| 937 | | 3 bits | 2 bits | 3 bits | |
| 938 | | mode | size | instruction class | |
| 939 | +--------+--------+-------------------+ |
| 940 | (MSB) (LSB) |
| 941 | |
| 942 | Size modifier is one of ... |
| 943 | |
| 944 | BPF_W 0x00 /* word */ |
| 945 | BPF_H 0x08 /* half word */ |
| 946 | BPF_B 0x10 /* byte */ |
| 947 | BPF_DW 0x18 /* eBPF only, double word */ |
| 948 | |
| 949 | ... which encodes size of load/store operation: |
| 950 | |
| 951 | B - 1 byte |
| 952 | H - 2 byte |
| 953 | W - 4 byte |
| 954 | DW - 8 byte (eBPF only) |
| 955 | |
| 956 | Mode modifier is one of: |
| 957 | |
Alexei Starovoitov | 02ab695 | 2014-09-04 22:17:17 -0700 | [diff] [blame] | 958 | BPF_IMM 0x00 /* used for 32-bit mov in classic BPF and 64-bit in eBPF */ |
Alexei Starovoitov | 783e327b | 2014-06-10 17:44:07 +0200 | [diff] [blame] | 959 | BPF_ABS 0x20 |
| 960 | BPF_IND 0x40 |
| 961 | BPF_MEM 0x60 |
| 962 | BPF_LEN 0x80 /* classic BPF only, reserved in eBPF */ |
| 963 | BPF_MSH 0xa0 /* classic BPF only, reserved in eBPF */ |
| 964 | BPF_XADD 0xc0 /* eBPF only, exclusive add */ |
| 965 | |
| 966 | eBPF has two non-generic instructions: (BPF_ABS | <size> | BPF_LD) and |
| 967 | (BPF_IND | <size> | BPF_LD) which are used to access packet data. |
| 968 | |
| 969 | They had to be carried over from classic to have strong performance of |
| 970 | socket filters running in eBPF interpreter. These instructions can only |
| 971 | be used when interpreter context is a pointer to 'struct sk_buff' and |
| 972 | have seven implicit operands. Register R6 is an implicit input that must |
| 973 | contain pointer to sk_buff. Register R0 is an implicit output which contains |
| 974 | the data fetched from the packet. Registers R1-R5 are scratch registers |
| 975 | and must not be used to store the data across BPF_ABS | BPF_LD or |
| 976 | BPF_IND | BPF_LD instructions. |
| 977 | |
| 978 | These instructions have implicit program exit condition as well. When |
| 979 | eBPF program is trying to access the data beyond the packet boundary, |
| 980 | the interpreter will abort the execution of the program. JIT compilers |
| 981 | therefore must preserve this property. src_reg and imm32 fields are |
| 982 | explicit inputs to these instructions. |
| 983 | |
| 984 | For example: |
| 985 | |
| 986 | BPF_IND | BPF_W | BPF_LD means: |
| 987 | |
| 988 | R0 = ntohl(*(u32 *) (((struct sk_buff *) R6)->data + src_reg + imm32)) |
| 989 | and R1 - R5 were scratched. |
| 990 | |
| 991 | Unlike classic BPF instruction set, eBPF has generic load/store operations: |
| 992 | |
| 993 | BPF_MEM | <size> | BPF_STX: *(size *) (dst_reg + off) = src_reg |
| 994 | BPF_MEM | <size> | BPF_ST: *(size *) (dst_reg + off) = imm32 |
| 995 | BPF_MEM | <size> | BPF_LDX: dst_reg = *(size *) (src_reg + off) |
| 996 | BPF_XADD | BPF_W | BPF_STX: lock xadd *(u32 *)(dst_reg + off16) += src_reg |
| 997 | BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg |
| 998 | |
| 999 | Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and |
| 1000 | 2 byte atomic increments are not supported. |
| 1001 | |
Alexei Starovoitov | 02ab695 | 2014-09-04 22:17:17 -0700 | [diff] [blame] | 1002 | eBPF has one 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM which consists |
| 1003 | of two consecutive 'struct bpf_insn' 8-byte blocks and interpreted as single |
| 1004 | instruction that loads 64-bit immediate value into a dst_reg. |
| 1005 | Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads |
| 1006 | 32-bit immediate value into a register. |
| 1007 | |
Alexei Starovoitov | 51580e7 | 2014-09-26 00:17:02 -0700 | [diff] [blame] | 1008 | eBPF verifier |
| 1009 | ------------- |
| 1010 | The safety of the eBPF program is determined in two steps. |
| 1011 | |
| 1012 | First step does DAG check to disallow loops and other CFG validation. |
| 1013 | In particular it will detect programs that have unreachable instructions. |
| 1014 | (though classic BPF checker allows them) |
| 1015 | |
| 1016 | Second step starts from the first insn and descends all possible paths. |
| 1017 | It simulates execution of every insn and observes the state change of |
| 1018 | registers and stack. |
| 1019 | |
| 1020 | At the start of the program the register R1 contains a pointer to context |
| 1021 | and has type PTR_TO_CTX. |
| 1022 | If verifier sees an insn that does R2=R1, then R2 has now type |
| 1023 | PTR_TO_CTX as well and can be used on the right hand side of expression. |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1024 | If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE, |
Alexei Starovoitov | 51580e7 | 2014-09-26 00:17:02 -0700 | [diff] [blame] | 1025 | since addition of two valid pointers makes invalid pointer. |
| 1026 | (In 'secure' mode verifier will reject any type of pointer arithmetic to make |
| 1027 | sure that kernel addresses don't leak to unprivileged users) |
| 1028 | |
| 1029 | If register was never written to, it's not readable: |
| 1030 | bpf_mov R0 = R2 |
| 1031 | bpf_exit |
| 1032 | will be rejected, since R2 is unreadable at the start of the program. |
| 1033 | |
| 1034 | After kernel function call, R1-R5 are reset to unreadable and |
| 1035 | R0 has a return type of the function. |
| 1036 | |
| 1037 | Since R6-R9 are callee saved, their state is preserved across the call. |
| 1038 | bpf_mov R6 = 1 |
| 1039 | bpf_call foo |
| 1040 | bpf_mov R0 = R6 |
| 1041 | bpf_exit |
| 1042 | is a correct program. If there was R1 instead of R6, it would have |
| 1043 | been rejected. |
| 1044 | |
| 1045 | load/store instructions are allowed only with registers of valid types, which |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1046 | are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked. |
Alexei Starovoitov | 51580e7 | 2014-09-26 00:17:02 -0700 | [diff] [blame] | 1047 | For example: |
| 1048 | bpf_mov R1 = 1 |
| 1049 | bpf_mov R2 = 2 |
| 1050 | bpf_xadd *(u32 *)(R1 + 3) += R2 |
| 1051 | bpf_exit |
| 1052 | will be rejected, since R1 doesn't have a valid pointer type at the time of |
| 1053 | execution of instruction bpf_xadd. |
| 1054 | |
| 1055 | At the start R1 type is PTR_TO_CTX (a pointer to generic 'struct bpf_context') |
| 1056 | A callback is used to customize verifier to restrict eBPF program access to only |
| 1057 | certain fields within ctx structure with specified size and alignment. |
| 1058 | |
| 1059 | For example, the following insn: |
| 1060 | bpf_ld R0 = *(u32 *)(R6 + 8) |
| 1061 | intends to load a word from address R6 + 8 and store it into R0 |
| 1062 | If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know |
| 1063 | that offset 8 of size 4 bytes can be accessed for reading, otherwise |
| 1064 | the verifier will reject the program. |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1065 | If R6=PTR_TO_STACK, then access should be aligned and be within |
Alexei Starovoitov | 51580e7 | 2014-09-26 00:17:02 -0700 | [diff] [blame] | 1066 | stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8, |
| 1067 | so it will fail verification, since it's out of bounds. |
| 1068 | |
| 1069 | The verifier will allow eBPF program to read data from stack only after |
| 1070 | it wrote into it. |
| 1071 | Classic BPF verifier does similar check with M[0-15] memory slots. |
| 1072 | For example: |
| 1073 | bpf_ld R0 = *(u32 *)(R10 - 4) |
| 1074 | bpf_exit |
| 1075 | is invalid program. |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1076 | Though R10 is correct read-only register and has type PTR_TO_STACK |
Alexei Starovoitov | 51580e7 | 2014-09-26 00:17:02 -0700 | [diff] [blame] | 1077 | and R10 - 4 is within stack bounds, there were no stores into that location. |
| 1078 | |
| 1079 | Pointer register spill/fill is tracked as well, since four (R6-R9) |
| 1080 | callee saved registers may not be enough for some programs. |
| 1081 | |
| 1082 | Allowed function calls are customized with bpf_verifier_ops->get_func_proto() |
| 1083 | The eBPF verifier will check that registers match argument constraints. |
| 1084 | After the call register R0 will be set to return type of the function. |
| 1085 | |
| 1086 | Function calls is a main mechanism to extend functionality of eBPF programs. |
| 1087 | Socket filters may let programs to call one set of functions, whereas tracing |
| 1088 | filters may allow completely different set. |
| 1089 | |
| 1090 | If a function made accessible to eBPF program, it needs to be thought through |
| 1091 | from safety point of view. The verifier will guarantee that the function is |
| 1092 | called with valid arguments. |
| 1093 | |
| 1094 | seccomp vs socket filters have different security restrictions for classic BPF. |
| 1095 | Seccomp solves this by two stage verifier: classic BPF verifier is followed |
| 1096 | by seccomp verifier. In case of eBPF one configurable verifier is shared for |
| 1097 | all use cases. |
| 1098 | |
| 1099 | See details of eBPF verifier in kernel/bpf/verifier.c |
| 1100 | |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1101 | Register value tracking |
| 1102 | ----------------------- |
| 1103 | In order to determine the safety of an eBPF program, the verifier must track |
| 1104 | the range of possible values in each register and also in each stack slot. |
| 1105 | This is done with 'struct bpf_reg_state', defined in include/linux/ |
| 1106 | bpf_verifier.h, which unifies tracking of scalar and pointer values. Each |
| 1107 | register state has a type, which is either NOT_INIT (the register has not been |
| 1108 | written to), SCALAR_VALUE (some value which is not usable as a pointer), or a |
| 1109 | pointer type. The types of pointers describe their base, as follows: |
| 1110 | PTR_TO_CTX Pointer to bpf_context. |
| 1111 | CONST_PTR_TO_MAP Pointer to struct bpf_map. "Const" because arithmetic |
| 1112 | on these pointers is forbidden. |
| 1113 | PTR_TO_MAP_VALUE Pointer to the value stored in a map element. |
| 1114 | PTR_TO_MAP_VALUE_OR_NULL |
| 1115 | Either a pointer to a map value, or NULL; map accesses |
| 1116 | (see section 'eBPF maps', below) return this type, |
| 1117 | which becomes a PTR_TO_MAP_VALUE when checked != NULL. |
| 1118 | Arithmetic on these pointers is forbidden. |
| 1119 | PTR_TO_STACK Frame pointer. |
| 1120 | PTR_TO_PACKET skb->data. |
| 1121 | PTR_TO_PACKET_END skb->data + headlen; arithmetic forbidden. |
| 1122 | However, a pointer may be offset from this base (as a result of pointer |
| 1123 | arithmetic), and this is tracked in two parts: the 'fixed offset' and 'variable |
| 1124 | offset'. The former is used when an exactly-known value (e.g. an immediate |
| 1125 | operand) is added to a pointer, while the latter is used for values which are |
| 1126 | not exactly known. The variable offset is also used in SCALAR_VALUEs, to track |
| 1127 | the range of possible values in the register. |
| 1128 | The verifier's knowledge about the variable offset consists of: |
| 1129 | * minimum and maximum values as unsigned |
| 1130 | * minimum and maximum values as signed |
| 1131 | * knowledge of the values of individual bits, in the form of a 'tnum': a u64 |
| 1132 | 'mask' and a u64 'value'. 1s in the mask represent bits whose value is unknown; |
| 1133 | 1s in the value represent bits known to be 1. Bits known to be 0 have 0 in both |
| 1134 | mask and value; no bit should ever be 1 in both. For example, if a byte is read |
| 1135 | into a register from memory, the register's top 56 bits are known zero, while |
| 1136 | the low 8 are unknown - which is represented as the tnum (0x0; 0xff). If we |
| 1137 | then OR this with 0x40, we get (0x40; 0xcf), then if we add 1 we get (0x0; |
| 1138 | 0x1ff), because of potential carries. |
| 1139 | Besides arithmetic, the register state can also be updated by conditional |
| 1140 | branches. For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch |
| 1141 | it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false' |
| 1142 | branch it will have a umax_value of 8. A signed compare (with BPF_JSGT or |
| 1143 | BPF_JSGE) would instead update the signed minimum/maximum values. Information |
| 1144 | from the signed and unsigned bounds can be combined; for instance if a value is |
| 1145 | first tested < 8 and then tested s> 4, the verifier will conclude that the value |
| 1146 | is also > 4 and s< 8, since the bounds prevent crossing the sign boundary. |
| 1147 | PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all |
| 1148 | pointers sharing that same variable offset. This is important for packet range |
| 1149 | checks: after adding some variable to a packet pointer, if you then copy it to |
| 1150 | another register and (say) add a constant 4, both registers will share the same |
| 1151 | 'id' but one will have a fixed offset of +4. Then if it is bounds-checked and |
| 1152 | found to be less than a PTR_TO_PACKET_END, the other register is now known to |
| 1153 | have a safe range of at least 4 bytes. See 'Direct packet access', below, for |
| 1154 | more on PTR_TO_PACKET ranges. |
| 1155 | The 'id' field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of |
| 1156 | the pointer returned from a map lookup. This means that when one copy is |
| 1157 | checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs. |
| 1158 | As well as range-checking, the tracked information is also used for enforcing |
| 1159 | alignment of pointer accesses. For instance, on most systems the packet pointer |
| 1160 | is 2 bytes after a 4-byte alignment. If a program adds 14 bytes to that to jump |
| 1161 | over the Ethernet header, then reads IHL and addes (IHL * 4), the resulting |
| 1162 | pointer will have a variable offset known to be 4n+2 for some n, so adding the 2 |
| 1163 | bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through |
| 1164 | that pointer are safe. |
| 1165 | |
Alexei Starovoitov | f9c8d19 | 2016-05-05 19:49:13 -0700 | [diff] [blame] | 1166 | Direct packet access |
| 1167 | -------------------- |
| 1168 | In cls_bpf and act_bpf programs the verifier allows direct access to the packet |
| 1169 | data via skb->data and skb->data_end pointers. |
| 1170 | Ex: |
| 1171 | 1: r4 = *(u32 *)(r1 +80) /* load skb->data_end */ |
| 1172 | 2: r3 = *(u32 *)(r1 +76) /* load skb->data */ |
| 1173 | 3: r5 = r3 |
| 1174 | 4: r5 += 14 |
| 1175 | 5: if r5 > r4 goto pc+16 |
| 1176 | R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp |
| 1177 | 6: r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */ |
| 1178 | |
| 1179 | this 2byte load from the packet is safe to do, since the program author |
| 1180 | did check 'if (skb->data + 14 > skb->data_end) goto err' at insn #5 which |
| 1181 | means that in the fall-through case the register R3 (which points to skb->data) |
| 1182 | has at least 14 directly accessible bytes. The verifier marks it |
| 1183 | as R3=pkt(id=0,off=0,r=14). |
| 1184 | id=0 means that no additional variables were added to the register. |
| 1185 | off=0 means that no additional constants were added. |
| 1186 | r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok. |
| 1187 | Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points |
| 1188 | to the packet data, but constant 14 was added to the register, so |
| 1189 | it now points to 'skb->data + 14' and accessible range is [R5, R5 + 14 - 14) |
| 1190 | which is zero bytes. |
| 1191 | |
| 1192 | More complex packet access may look like: |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1193 | R0=inv1 R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp |
Alexei Starovoitov | f9c8d19 | 2016-05-05 19:49:13 -0700 | [diff] [blame] | 1194 | 6: r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */ |
| 1195 | 7: r4 = *(u8 *)(r3 +12) |
| 1196 | 8: r4 *= 14 |
| 1197 | 9: r3 = *(u32 *)(r1 +76) /* load skb->data */ |
| 1198 | 10: r3 += r4 |
| 1199 | 11: r2 = r1 |
| 1200 | 12: r2 <<= 48 |
| 1201 | 13: r2 >>= 48 |
| 1202 | 14: r3 += r2 |
| 1203 | 15: r2 = r3 |
| 1204 | 16: r2 += 8 |
| 1205 | 17: r1 = *(u32 *)(r1 +80) /* load skb->data_end */ |
| 1206 | 18: if r2 > r1 goto pc+2 |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1207 | R0=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R1=pkt_end R2=pkt(id=2,off=8,r=8) R3=pkt(id=2,off=0,r=8) R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)) R5=pkt(id=0,off=14,r=14) R10=fp |
Alexei Starovoitov | f9c8d19 | 2016-05-05 19:49:13 -0700 | [diff] [blame] | 1208 | 19: r1 = *(u8 *)(r3 +4) |
| 1209 | The state of the register R3 is R3=pkt(id=2,off=0,r=8) |
| 1210 | id=2 means that two 'r3 += rX' instructions were seen, so r3 points to some |
| 1211 | offset within a packet and since the program author did |
| 1212 | 'if (r3 + 8 > r1) goto err' at insn #18, the safe range is [R3, R3 + 8). |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1213 | The verifier only allows 'add'/'sub' operations on packet registers. Any other |
| 1214 | operation will set the register state to 'SCALAR_VALUE' and it won't be |
Alexei Starovoitov | f9c8d19 | 2016-05-05 19:49:13 -0700 | [diff] [blame] | 1215 | available for direct packet access. |
| 1216 | Operation 'r3 += rX' may overflow and become less than original skb->data, |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1217 | therefore the verifier has to prevent that. So when it sees 'r3 += rX' |
| 1218 | instruction and rX is more than 16-bit value, any subsequent bounds-check of r3 |
| 1219 | against skb->data_end will not give us 'range' information, so attempts to read |
| 1220 | through the pointer will give "invalid access to packet" error. |
Alexei Starovoitov | f9c8d19 | 2016-05-05 19:49:13 -0700 | [diff] [blame] | 1221 | Ex. after insn 'r4 = *(u8 *)(r3 +12)' (insn #7 above) the state of r4 is |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1222 | R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits |
| 1223 | of the register are guaranteed to be zero, and nothing is known about the lower |
| 1224 | 8 bits. After insn 'r4 *= 14' the state becomes |
| 1225 | R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit |
| 1226 | value by constant 14 will keep upper 52 bits as zero, also the least significant |
| 1227 | bit will be zero as 14 is even. Similarly 'r2 >>= 48' will make |
| 1228 | R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign |
| 1229 | extending. This logic is implemented in adjust_reg_min_max_vals() function, |
| 1230 | which calls adjust_ptr_min_max_vals() for adding pointer to scalar (or vice |
| 1231 | versa) and adjust_scalar_min_max_vals() for operations on two scalars. |
Alexei Starovoitov | f9c8d19 | 2016-05-05 19:49:13 -0700 | [diff] [blame] | 1232 | |
| 1233 | The end result is that bpf program author can access packet directly |
| 1234 | using normal C code as: |
| 1235 | void *data = (void *)(long)skb->data; |
| 1236 | void *data_end = (void *)(long)skb->data_end; |
| 1237 | struct eth_hdr *eth = data; |
| 1238 | struct iphdr *iph = data + sizeof(*eth); |
| 1239 | struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph); |
| 1240 | |
| 1241 | if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end) |
| 1242 | return 0; |
| 1243 | if (eth->h_proto != htons(ETH_P_IP)) |
| 1244 | return 0; |
| 1245 | if (iph->protocol != IPPROTO_UDP || iph->ihl != 5) |
| 1246 | return 0; |
| 1247 | if (udp->dest == 53 || udp->source == 9) |
| 1248 | ...; |
| 1249 | which makes such programs easier to write comparing to LD_ABS insn |
| 1250 | and significantly faster. |
| 1251 | |
Alexei Starovoitov | 99c55f7 | 2014-09-26 00:16:57 -0700 | [diff] [blame] | 1252 | eBPF maps |
| 1253 | --------- |
| 1254 | 'maps' is a generic storage of different types for sharing data between kernel |
| 1255 | and userspace. |
| 1256 | |
| 1257 | The maps are accessed from user space via BPF syscall, which has commands: |
| 1258 | - create a map with given type and attributes |
| 1259 | map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) |
| 1260 | using attr->map_type, attr->key_size, attr->value_size, attr->max_entries |
| 1261 | returns process-local file descriptor or negative error |
| 1262 | |
| 1263 | - lookup key in a given map |
| 1264 | err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) |
| 1265 | using attr->map_fd, attr->key, attr->value |
| 1266 | returns zero and stores found elem into value or negative error |
| 1267 | |
| 1268 | - create or update key/value pair in a given map |
| 1269 | err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) |
| 1270 | using attr->map_fd, attr->key, attr->value |
| 1271 | returns zero or negative error |
| 1272 | |
| 1273 | - find and delete element by key in a given map |
| 1274 | err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) |
| 1275 | using attr->map_fd, attr->key |
| 1276 | |
| 1277 | - to delete map: close(fd) |
| 1278 | Exiting process will delete maps automatically |
| 1279 | |
| 1280 | userspace programs use this syscall to create/access maps that eBPF programs |
| 1281 | are concurrently updating. |
| 1282 | |
| 1283 | maps can have different types: hash, array, bloom filter, radix-tree, etc. |
| 1284 | |
| 1285 | The map is defined by: |
| 1286 | . type |
| 1287 | . max number of elements |
| 1288 | . key size in bytes |
| 1289 | . value size in bytes |
| 1290 | |
Edward Cree | 0cbf474 | 2017-08-07 15:30:09 +0100 | [diff] [blame] | 1291 | Pruning |
| 1292 | ------- |
| 1293 | The verifier does not actually walk all possible paths through the program. For |
| 1294 | each new branch to analyse, the verifier looks at all the states it's previously |
| 1295 | been in when at this instruction. If any of them contain the current state as a |
| 1296 | subset, the branch is 'pruned' - that is, the fact that the previous state was |
| 1297 | accepted implies the current state would be as well. For instance, if in the |
| 1298 | previous state, r1 held a packet-pointer, and in the current state, r1 holds a |
| 1299 | packet-pointer with a range as long or longer and at least as strict an |
| 1300 | alignment, then r1 is safe. Similarly, if r2 was NOT_INIT before then it can't |
| 1301 | have been used by any path from that point, so any value in r2 (including |
| 1302 | another NOT_INIT) is safe. The implementation is in the function regsafe(). |
| 1303 | Pruning considers not only the registers but also the stack (and any spilled |
| 1304 | registers it may hold). They must all be safe for the branch to be pruned. |
| 1305 | This is implemented in states_equal(). |
| 1306 | |
Alexei Starovoitov | 51580e7 | 2014-09-26 00:17:02 -0700 | [diff] [blame] | 1307 | Understanding eBPF verifier messages |
| 1308 | ------------------------------------ |
| 1309 | |
| 1310 | The following are few examples of invalid eBPF programs and verifier error |
| 1311 | messages as seen in the log: |
| 1312 | |
| 1313 | Program with unreachable instructions: |
| 1314 | static struct bpf_insn prog[] = { |
| 1315 | BPF_EXIT_INSN(), |
| 1316 | BPF_EXIT_INSN(), |
| 1317 | }; |
| 1318 | Error: |
| 1319 | unreachable insn 1 |
| 1320 | |
| 1321 | Program that reads uninitialized register: |
| 1322 | BPF_MOV64_REG(BPF_REG_0, BPF_REG_2), |
| 1323 | BPF_EXIT_INSN(), |
| 1324 | Error: |
| 1325 | 0: (bf) r0 = r2 |
| 1326 | R2 !read_ok |
| 1327 | |
| 1328 | Program that doesn't initialize R0 before exiting: |
| 1329 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_1), |
| 1330 | BPF_EXIT_INSN(), |
| 1331 | Error: |
| 1332 | 0: (bf) r2 = r1 |
| 1333 | 1: (95) exit |
| 1334 | R0 !read_ok |
| 1335 | |
| 1336 | Program that accesses stack out of bounds: |
| 1337 | BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0), |
| 1338 | BPF_EXIT_INSN(), |
| 1339 | Error: |
| 1340 | 0: (7a) *(u64 *)(r10 +8) = 0 |
| 1341 | invalid stack off=8 size=8 |
| 1342 | |
| 1343 | Program that doesn't initialize stack before passing its address into function: |
| 1344 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), |
| 1345 | BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), |
| 1346 | BPF_LD_MAP_FD(BPF_REG_1, 0), |
| 1347 | BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), |
| 1348 | BPF_EXIT_INSN(), |
| 1349 | Error: |
| 1350 | 0: (bf) r2 = r10 |
| 1351 | 1: (07) r2 += -8 |
| 1352 | 2: (b7) r1 = 0x0 |
| 1353 | 3: (85) call 1 |
| 1354 | invalid indirect read from stack off -8+0 size 8 |
| 1355 | |
| 1356 | Program that uses invalid map_fd=0 while calling to map_lookup_elem() function: |
| 1357 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
| 1358 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), |
| 1359 | BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), |
| 1360 | BPF_LD_MAP_FD(BPF_REG_1, 0), |
| 1361 | BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), |
| 1362 | BPF_EXIT_INSN(), |
| 1363 | Error: |
| 1364 | 0: (7a) *(u64 *)(r10 -8) = 0 |
| 1365 | 1: (bf) r2 = r10 |
| 1366 | 2: (07) r2 += -8 |
| 1367 | 3: (b7) r1 = 0x0 |
| 1368 | 4: (85) call 1 |
| 1369 | fd 0 is not pointing to valid bpf_map |
| 1370 | |
| 1371 | Program that doesn't check return value of map_lookup_elem() before accessing |
| 1372 | map element: |
| 1373 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
| 1374 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), |
| 1375 | BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), |
| 1376 | BPF_LD_MAP_FD(BPF_REG_1, 0), |
| 1377 | BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), |
| 1378 | BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0), |
| 1379 | BPF_EXIT_INSN(), |
| 1380 | Error: |
| 1381 | 0: (7a) *(u64 *)(r10 -8) = 0 |
| 1382 | 1: (bf) r2 = r10 |
| 1383 | 2: (07) r2 += -8 |
| 1384 | 3: (b7) r1 = 0x0 |
| 1385 | 4: (85) call 1 |
| 1386 | 5: (7a) *(u64 *)(r0 +0) = 0 |
| 1387 | R0 invalid mem access 'map_value_or_null' |
| 1388 | |
| 1389 | Program that correctly checks map_lookup_elem() returned value for NULL, but |
| 1390 | accesses the memory with incorrect alignment: |
| 1391 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
| 1392 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), |
| 1393 | BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), |
| 1394 | BPF_LD_MAP_FD(BPF_REG_1, 0), |
| 1395 | BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), |
| 1396 | BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1), |
| 1397 | BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0), |
| 1398 | BPF_EXIT_INSN(), |
| 1399 | Error: |
| 1400 | 0: (7a) *(u64 *)(r10 -8) = 0 |
| 1401 | 1: (bf) r2 = r10 |
| 1402 | 2: (07) r2 += -8 |
| 1403 | 3: (b7) r1 = 1 |
| 1404 | 4: (85) call 1 |
| 1405 | 5: (15) if r0 == 0x0 goto pc+1 |
| 1406 | R0=map_ptr R10=fp |
| 1407 | 6: (7a) *(u64 *)(r0 +4) = 0 |
| 1408 | misaligned access off 4 size 8 |
| 1409 | |
| 1410 | Program that correctly checks map_lookup_elem() returned value for NULL and |
| 1411 | accesses memory with correct alignment in one side of 'if' branch, but fails |
| 1412 | to do so in the other side of 'if' branch: |
| 1413 | BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0), |
| 1414 | BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), |
| 1415 | BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), |
| 1416 | BPF_LD_MAP_FD(BPF_REG_1, 0), |
| 1417 | BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), |
| 1418 | BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2), |
| 1419 | BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0), |
| 1420 | BPF_EXIT_INSN(), |
| 1421 | BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1), |
| 1422 | BPF_EXIT_INSN(), |
| 1423 | Error: |
| 1424 | 0: (7a) *(u64 *)(r10 -8) = 0 |
| 1425 | 1: (bf) r2 = r10 |
| 1426 | 2: (07) r2 += -8 |
| 1427 | 3: (b7) r1 = 1 |
| 1428 | 4: (85) call 1 |
| 1429 | 5: (15) if r0 == 0x0 goto pc+2 |
| 1430 | R0=map_ptr R10=fp |
| 1431 | 6: (7a) *(u64 *)(r0 +0) = 0 |
| 1432 | 7: (95) exit |
| 1433 | |
| 1434 | from 5 to 8: R0=imm0 R10=fp |
| 1435 | 8: (7a) *(u64 *)(r0 +0) = 1 |
| 1436 | R0 invalid mem access 'imm' |
| 1437 | |
Daniel Borkmann | 04caa48 | 2014-05-23 18:43:59 +0200 | [diff] [blame] | 1438 | Testing |
| 1439 | ------- |
| 1440 | |
| 1441 | Next to the BPF toolchain, the kernel also ships a test module that contains |
| 1442 | various test cases for classic and internal BPF that can be executed against |
| 1443 | the BPF interpreter and JIT compiler. It can be found in lib/test_bpf.c and |
| 1444 | enabled via Kconfig: |
| 1445 | |
| 1446 | CONFIG_TEST_BPF=m |
| 1447 | |
| 1448 | After the module has been built and installed, the test suite can be executed |
| 1449 | via insmod or modprobe against 'test_bpf' module. Results of the test cases |
| 1450 | including timings in nsec can be found in the kernel log (dmesg). |
| 1451 | |
Daniel Borkmann | 7924cd5 | 2013-12-11 23:43:45 +0100 | [diff] [blame] | 1452 | Misc |
| 1453 | ---- |
| 1454 | |
| 1455 | Also trinity, the Linux syscall fuzzer, has built-in support for BPF and |
| 1456 | SECCOMP-BPF kernel fuzzing. |
| 1457 | |
| 1458 | Written by |
| 1459 | ---------- |
| 1460 | |
| 1461 | The document was written in the hope that it is found useful and in order |
| 1462 | to give potential BPF hackers or security auditors a better overview of |
| 1463 | the underlying architecture. |
| 1464 | |
| 1465 | Jay Schulist <jschlst@samba.org> |
Alexei Starovoitov | f9c8d19 | 2016-05-05 19:49:13 -0700 | [diff] [blame] | 1466 | Daniel Borkmann <daniel@iogearbox.net> |
| 1467 | Alexei Starovoitov <ast@kernel.org> |