About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / networking / filter.txt




Custom Search

Based on kernel version 4.16.1. Page generated on 2018-04-09 11:53 EST.

1	Linux Socket Filtering aka Berkeley Packet Filter (BPF)
2	=======================================================
3	
4	Introduction
5	------------
6	
7	Linux Socket Filtering (LSF) is derived from the Berkeley Packet Filter.
8	Though there are some distinct differences between the BSD and Linux
9	Kernel filtering, but when we speak of BPF or LSF in Linux context, we
10	mean the very same mechanism of filtering in the Linux kernel.
11	
12	BPF allows a user-space program to attach a filter onto any socket and
13	allow or disallow certain types of data to come through the socket. LSF
14	follows exactly the same filter code structure as BSD's BPF, so referring
15	to the BSD bpf.4 manpage is very helpful in creating filters.
16	
17	On Linux, BPF is much simpler than on BSD. One does not have to worry
18	about devices or anything like that. You simply create your filter code,
19	send it to the kernel via the SO_ATTACH_FILTER option and if your filter
20	code passes the kernel check on it, you then immediately begin filtering
21	data on that socket.
22	
23	You can also detach filters from your socket via the SO_DETACH_FILTER
24	option. This will probably not be used much since when you close a socket
25	that has a filter on it the filter is automagically removed. The other
26	less common case may be adding a different filter on the same socket where
27	you had another filter that is still running: the kernel takes care of
28	removing the old one and placing your new one in its place, assuming your
29	filter has passed the checks, otherwise if it fails the old filter will
30	remain on that socket.
31	
32	SO_LOCK_FILTER option allows to lock the filter attached to a socket. Once
33	set, a filter cannot be removed or changed. This allows one process to
34	setup a socket, attach a filter, lock it then drop privileges and be
35	assured that the filter will be kept until the socket is closed.
36	
37	The biggest user of this construct might be libpcap. Issuing a high-level
38	filter command like `tcpdump -i em1 port 22` passes through the libpcap
39	internal compiler that generates a structure that can eventually be loaded
40	via SO_ATTACH_FILTER to the kernel. `tcpdump -i em1 port 22 -ddd`
41	displays what is being placed into this structure.
42	
43	Although we were only speaking about sockets here, BPF in Linux is used
44	in many more places. There's xt_bpf for netfilter, cls_bpf in the kernel
45	qdisc layer, SECCOMP-BPF (SECure COMPuting [1]), and lots of other places
46	such as team driver, PTP code, etc where BPF is being used.
47	
48	 [1] Documentation/userspace-api/seccomp_filter.rst
49	
50	Original BPF paper:
51	
52	Steven McCanne and Van Jacobson. 1993. The BSD packet filter: a new
53	architecture for user-level packet capture. In Proceedings of the
54	USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993
55	Conference Proceedings (USENIX'93). USENIX Association, Berkeley,
56	CA, USA, 2-2. [http://www.tcpdump.org/papers/bpf-usenix93.pdf]
57	
58	Structure
59	---------
60	
61	User space applications include <linux/filter.h> which contains the
62	following relevant structures:
63	
64	struct sock_filter {	/* Filter block */
65		__u16	code;   /* Actual filter code */
66		__u8	jt;	/* Jump true */
67		__u8	jf;	/* Jump false */
68		__u32	k;      /* Generic multiuse field */
69	};
70	
71	Such a structure is assembled as an array of 4-tuples, that contains
72	a code, jt, jf and k value. jt and jf are jump offsets and k a generic
73	value to be used for a provided code.
74	
75	struct sock_fprog {			/* Required for SO_ATTACH_FILTER. */
76		unsigned short		   len;	/* Number of filter blocks */
77		struct sock_filter __user *filter;
78	};
79	
80	For socket filtering, a pointer to this structure (as shown in
81	follow-up example) is being passed to the kernel through setsockopt(2).
82	
83	Example
84	-------
85	
86	#include <sys/socket.h>
87	#include <sys/types.h>
88	#include <arpa/inet.h>
89	#include <linux/if_ether.h>
90	/* ... */
91	
92	/* From the example above: tcpdump -i em1 port 22 -dd */
93	struct sock_filter code[] = {
94		{ 0x28,  0,  0, 0x0000000c },
95		{ 0x15,  0,  8, 0x000086dd },
96		{ 0x30,  0,  0, 0x00000014 },
97		{ 0x15,  2,  0, 0x00000084 },
98		{ 0x15,  1,  0, 0x00000006 },
99		{ 0x15,  0, 17, 0x00000011 },
100		{ 0x28,  0,  0, 0x00000036 },
101		{ 0x15, 14,  0, 0x00000016 },
102		{ 0x28,  0,  0, 0x00000038 },
103		{ 0x15, 12, 13, 0x00000016 },
104		{ 0x15,  0, 12, 0x00000800 },
105		{ 0x30,  0,  0, 0x00000017 },
106		{ 0x15,  2,  0, 0x00000084 },
107		{ 0x15,  1,  0, 0x00000006 },
108		{ 0x15,  0,  8, 0x00000011 },
109		{ 0x28,  0,  0, 0x00000014 },
110		{ 0x45,  6,  0, 0x00001fff },
111		{ 0xb1,  0,  0, 0x0000000e },
112		{ 0x48,  0,  0, 0x0000000e },
113		{ 0x15,  2,  0, 0x00000016 },
114		{ 0x48,  0,  0, 0x00000010 },
115		{ 0x15,  0,  1, 0x00000016 },
116		{ 0x06,  0,  0, 0x0000ffff },
117		{ 0x06,  0,  0, 0x00000000 },
118	};
119	
120	struct sock_fprog bpf = {
121		.len = ARRAY_SIZE(code),
122		.filter = code,
123	};
124	
125	sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
126	if (sock < 0)
127		/* ... bail out ... */
128	
129	ret = setsockopt(sock, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf));
130	if (ret < 0)
131		/* ... bail out ... */
132	
133	/* ... */
134	close(sock);
135	
136	The above example code attaches a socket filter for a PF_PACKET socket
137	in order to let all IPv4/IPv6 packets with port 22 pass. The rest will
138	be dropped for this socket.
139	
140	The setsockopt(2) call to SO_DETACH_FILTER doesn't need any arguments
141	and SO_LOCK_FILTER for preventing the filter to be detached, takes an
142	integer value with 0 or 1.
143	
144	Note that socket filters are not restricted to PF_PACKET sockets only,
145	but can also be used on other socket families.
146	
147	Summary of system calls:
148	
149	 * setsockopt(sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &val, sizeof(val));
150	 * setsockopt(sockfd, SOL_SOCKET, SO_DETACH_FILTER, &val, sizeof(val));
151	 * setsockopt(sockfd, SOL_SOCKET, SO_LOCK_FILTER,   &val, sizeof(val));
152	
153	Normally, most use cases for socket filtering on packet sockets will be
154	covered by libpcap in high-level syntax, so as an application developer
155	you should stick to that. libpcap wraps its own layer around all that.
156	
157	Unless i) using/linking to libpcap is not an option, ii) the required BPF
158	filters use Linux extensions that are not supported by libpcap's compiler,
159	iii) a filter might be more complex and not cleanly implementable with
160	libpcap's compiler, or iv) particular filter codes should be optimized
161	differently than libpcap's internal compiler does; then in such cases
162	writing such a filter "by hand" can be of an alternative. For example,
163	xt_bpf and cls_bpf users might have requirements that could result in
164	more complex filter code, or one that cannot be expressed with libpcap
165	(e.g. different return codes for various code paths). Moreover, BPF JIT
166	implementors may wish to manually write test cases and thus need low-level
167	access to BPF code as well.
168	
169	BPF engine and instruction set
170	------------------------------
171	
172	Under tools/net/ there's a small helper tool called bpf_asm which can
173	be used to write low-level filters for example scenarios mentioned in the
174	previous section. Asm-like syntax mentioned here has been implemented in
175	bpf_asm and will be used for further explanations (instead of dealing with
176	less readable opcodes directly, principles are the same). The syntax is
177	closely modelled after Steven McCanne's and Van Jacobson's BPF paper.
178	
179	The BPF architecture consists of the following basic elements:
180	
181	  Element          Description
182	
183	  A                32 bit wide accumulator
184	  X                32 bit wide X register
185	  M[]              16 x 32 bit wide misc registers aka "scratch memory
186	                   store", addressable from 0 to 15
187	
188	A program, that is translated by bpf_asm into "opcodes" is an array that
189	consists of the following elements (as already mentioned):
190	
191	  op:16, jt:8, jf:8, k:32
192	
193	The element op is a 16 bit wide opcode that has a particular instruction
194	encoded. jt and jf are two 8 bit wide jump targets, one for condition
195	"jump if true", the other one "jump if false". Eventually, element k
196	contains a miscellaneous argument that can be interpreted in different
197	ways depending on the given instruction in op.
198	
199	The instruction set consists of load, store, branch, alu, miscellaneous
200	and return instructions that are also represented in bpf_asm syntax. This
201	table lists all bpf_asm instructions available resp. what their underlying
202	opcodes as defined in linux/filter.h stand for:
203	
204	  Instruction      Addressing mode      Description
205	
206	  ld               1, 2, 3, 4, 10       Load word into A
207	  ldi              4                    Load word into A
208	  ldh              1, 2                 Load half-word into A
209	  ldb              1, 2                 Load byte into A
210	  ldx              3, 4, 5, 10          Load word into X
211	  ldxi             4                    Load word into X
212	  ldxb             5                    Load byte into X
213	
214	  st               3                    Store A into M[]
215	  stx              3                    Store X into M[]
216	
217	  jmp              6                    Jump to label
218	  ja               6                    Jump to label
219	  jeq              7, 8                 Jump on A == k
220	  jneq             8                    Jump on A != k
221	  jne              8                    Jump on A != k
222	  jlt              8                    Jump on A <  k
223	  jle              8                    Jump on A <= k
224	  jgt              7, 8                 Jump on A >  k
225	  jge              7, 8                 Jump on A >= k
226	  jset             7, 8                 Jump on A &  k
227	
228	  add              0, 4                 A + <x>
229	  sub              0, 4                 A - <x>
230	  mul              0, 4                 A * <x>
231	  div              0, 4                 A / <x>
232	  mod              0, 4                 A % <x>
233	  neg                                   !A
234	  and              0, 4                 A & <x>
235	  or               0, 4                 A | <x>
236	  xor              0, 4                 A ^ <x>
237	  lsh              0, 4                 A << <x>
238	  rsh              0, 4                 A >> <x>
239	
240	  tax                                   Copy A into X
241	  txa                                   Copy X into A
242	
243	  ret              4, 9                 Return
244	
245	The next table shows addressing formats from the 2nd column:
246	
247	  Addressing mode  Syntax               Description
248	
249	   0               x/%x                 Register X
250	   1               [k]                  BHW at byte offset k in the packet
251	   2               [x + k]              BHW at the offset X + k in the packet
252	   3               M[k]                 Word at offset k in M[]
253	   4               #k                   Literal value stored in k
254	   5               4*([k]&0xf)          Lower nibble * 4 at byte offset k in the packet
255	   6               L                    Jump label L
256	   7               #k,Lt,Lf             Jump to Lt if true, otherwise jump to Lf
257	   8               #k,Lt                Jump to Lt if predicate is true
258	   9               a/%a                 Accumulator A
259	  10               extension            BPF extension
260	
261	The Linux kernel also has a couple of BPF extensions that are used along
262	with the class of load instructions by "overloading" the k argument with
263	a negative offset + a particular extension offset. The result of such BPF
264	extensions are loaded into A.
265	
266	Possible BPF extensions are shown in the following table:
267	
268	  Extension                             Description
269	
270	  len                                   skb->len
271	  proto                                 skb->protocol
272	  type                                  skb->pkt_type
273	  poff                                  Payload start offset
274	  ifidx                                 skb->dev->ifindex
275	  nla                                   Netlink attribute of type X with offset A
276	  nlan                                  Nested Netlink attribute of type X with offset A
277	  mark                                  skb->mark
278	  queue                                 skb->queue_mapping
279	  hatype                                skb->dev->type
280	  rxhash                                skb->hash
281	  cpu                                   raw_smp_processor_id()
282	  vlan_tci                              skb_vlan_tag_get(skb)
283	  vlan_avail                            skb_vlan_tag_present(skb)
284	  vlan_tpid                             skb->vlan_proto
285	  rand                                  prandom_u32()
286	
287	These extensions can also be prefixed with '#'.
288	Examples for low-level BPF:
289	
290	** ARP packets:
291	
292	  ldh [12]
293	  jne #0x806, drop
294	  ret #-1
295	  drop: ret #0
296	
297	** IPv4 TCP packets:
298	
299	  ldh [12]
300	  jne #0x800, drop
301	  ldb [23]
302	  jneq #6, drop
303	  ret #-1
304	  drop: ret #0
305	
306	** (Accelerated) VLAN w/ id 10:
307	
308	  ld vlan_tci
309	  jneq #10, drop
310	  ret #-1
311	  drop: ret #0
312	
313	** icmp random packet sampling, 1 in 4
314	  ldh [12]
315	  jne #0x800, drop
316	  ldb [23]
317	  jneq #1, drop
318	  # get a random uint32 number
319	  ld rand
320	  mod #4
321	  jneq #1, drop
322	  ret #-1
323	  drop: ret #0
324	
325	** SECCOMP filter example:
326	
327	  ld [4]                  /* offsetof(struct seccomp_data, arch) */
328	  jne #0xc000003e, bad    /* AUDIT_ARCH_X86_64 */
329	  ld [0]                  /* offsetof(struct seccomp_data, nr) */
330	  jeq #15, good           /* __NR_rt_sigreturn */
331	  jeq #231, good          /* __NR_exit_group */
332	  jeq #60, good           /* __NR_exit */
333	  jeq #0, good            /* __NR_read */
334	  jeq #1, good            /* __NR_write */
335	  jeq #5, good            /* __NR_fstat */
336	  jeq #9, good            /* __NR_mmap */
337	  jeq #14, good           /* __NR_rt_sigprocmask */
338	  jeq #13, good           /* __NR_rt_sigaction */
339	  jeq #35, good           /* __NR_nanosleep */
340	  bad: ret #0             /* SECCOMP_RET_KILL_THREAD */
341	  good: ret #0x7fff0000   /* SECCOMP_RET_ALLOW */
342	
343	The above example code can be placed into a file (here called "foo"), and
344	then be passed to the bpf_asm tool for generating opcodes, output that xt_bpf
345	and cls_bpf understands and can directly be loaded with. Example with above
346	ARP code:
347	
348	$ ./bpf_asm foo
349	4,40 0 0 12,21 0 1 2054,6 0 0 4294967295,6 0 0 0,
350	
351	In copy and paste C-like output:
352	
353	$ ./bpf_asm -c foo
354	{ 0x28,  0,  0, 0x0000000c },
355	{ 0x15,  0,  1, 0x00000806 },
356	{ 0x06,  0,  0, 0xffffffff },
357	{ 0x06,  0,  0, 0000000000 },
358	
359	In particular, as usage with xt_bpf or cls_bpf can result in more complex BPF
360	filters that might not be obvious at first, it's good to test filters before
361	attaching to a live system. For that purpose, there's a small tool called
362	bpf_dbg under tools/net/ in the kernel source directory. This debugger allows
363	for testing BPF filters against given pcap files, single stepping through the
364	BPF code on the pcap's packets and to do BPF machine register dumps.
365	
366	Starting bpf_dbg is trivial and just requires issuing:
367	
368	# ./bpf_dbg
369	
370	In case input and output do not equal stdin/stdout, bpf_dbg takes an
371	alternative stdin source as a first argument, and an alternative stdout
372	sink as a second one, e.g. `./bpf_dbg test_in.txt test_out.txt`.
373	
374	Other than that, a particular libreadline configuration can be set via
375	file "~/.bpf_dbg_init" and the command history is stored in the file
376	"~/.bpf_dbg_history".
377	
378	Interaction in bpf_dbg happens through a shell that also has auto-completion
379	support (follow-up example commands starting with '>' denote bpf_dbg shell).
380	The usual workflow would be to ...
381	
382	> load bpf 6,40 0 0 12,21 0 3 2048,48 0 0 23,21 0 1 1,6 0 0 65535,6 0 0 0
383	  Loads a BPF filter from standard output of bpf_asm, or transformed via
384	  e.g. `tcpdump -iem1 -ddd port 22 | tr '\n' ','`. Note that for JIT
385	  debugging (next section), this command creates a temporary socket and
386	  loads the BPF code into the kernel. Thus, this will also be useful for
387	  JIT developers.
388	
389	> load pcap foo.pcap
390	  Loads standard tcpdump pcap file.
391	
392	> run [<n>]
393	bpf passes:1 fails:9
394	  Runs through all packets from a pcap to account how many passes and fails
395	  the filter will generate. A limit of packets to traverse can be given.
396	
397	> disassemble
398	l0:	ldh [12]
399	l1:	jeq #0x800, l2, l5
400	l2:	ldb [23]
401	l3:	jeq #0x1, l4, l5
402	l4:	ret #0xffff
403	l5:	ret #0
404	  Prints out BPF code disassembly.
405	
406	> dump
407	/* { op, jt, jf, k }, */
408	{ 0x28,  0,  0, 0x0000000c },
409	{ 0x15,  0,  3, 0x00000800 },
410	{ 0x30,  0,  0, 0x00000017 },
411	{ 0x15,  0,  1, 0x00000001 },
412	{ 0x06,  0,  0, 0x0000ffff },
413	{ 0x06,  0,  0, 0000000000 },
414	  Prints out C-style BPF code dump.
415	
416	> breakpoint 0
417	breakpoint at: l0:	ldh [12]
418	> breakpoint 1
419	breakpoint at: l1:	jeq #0x800, l2, l5
420	  ...
421	  Sets breakpoints at particular BPF instructions. Issuing a `run` command
422	  will walk through the pcap file continuing from the current packet and
423	  break when a breakpoint is being hit (another `run` will continue from
424	  the currently active breakpoint executing next instructions):
425	
426	  > run
427	  -- register dump --
428	  pc:       [0]                       <-- program counter
429	  code:     [40] jt[0] jf[0] k[12]    <-- plain BPF code of current instruction
430	  curr:     l0:	ldh [12]              <-- disassembly of current instruction
431	  A:        [00000000][0]             <-- content of A (hex, decimal)
432	  X:        [00000000][0]             <-- content of X (hex, decimal)
433	  M[0,15]:  [00000000][0]             <-- folded content of M (hex, decimal)
434	  -- packet dump --                   <-- Current packet from pcap (hex)
435	  len: 42
436	    0: 00 19 cb 55 55 a4 00 14 a4 43 78 69 08 06 00 01
437	   16: 08 00 06 04 00 01 00 14 a4 43 78 69 0a 3b 01 26
438	   32: 00 00 00 00 00 00 0a 3b 01 01
439	  (breakpoint)
440	  >
441	
442	> breakpoint
443	breakpoints: 0 1
444	  Prints currently set breakpoints.
445	
446	> step [-<n>, +<n>]
447	  Performs single stepping through the BPF program from the current pc
448	  offset. Thus, on each step invocation, above register dump is issued.
449	  This can go forwards and backwards in time, a plain `step` will break
450	  on the next BPF instruction, thus +1. (No `run` needs to be issued here.)
451	
452	> select <n>
453	  Selects a given packet from the pcap file to continue from. Thus, on
454	  the next `run` or `step`, the BPF program is being evaluated against
455	  the user pre-selected packet. Numbering starts just as in Wireshark
456	  with index 1.
457	
458	> quit
459	#
460	  Exits bpf_dbg.
461	
462	JIT compiler
463	------------
464	
465	The Linux kernel has a built-in BPF JIT compiler for x86_64, SPARC, PowerPC,
466	ARM, ARM64, MIPS and s390 and can be enabled through CONFIG_BPF_JIT. The JIT
467	compiler is transparently invoked for each attached filter from user space
468	or for internal kernel users if it has been previously enabled by root:
469	
470	  echo 1 > /proc/sys/net/core/bpf_jit_enable
471	
472	For JIT developers, doing audits etc, each compile run can output the generated
473	opcode image into the kernel log via:
474	
475	  echo 2 > /proc/sys/net/core/bpf_jit_enable
476	
477	Example output from dmesg:
478	
479	[ 3389.935842] flen=6 proglen=70 pass=3 image=ffffffffa0069c8f
480	[ 3389.935847] JIT code: 00000000: 55 48 89 e5 48 83 ec 60 48 89 5d f8 44 8b 4f 68
481	[ 3389.935849] JIT code: 00000010: 44 2b 4f 6c 4c 8b 87 d8 00 00 00 be 0c 00 00 00
482	[ 3389.935850] JIT code: 00000020: e8 1d 94 ff e0 3d 00 08 00 00 75 16 be 17 00 00
483	[ 3389.935851] JIT code: 00000030: 00 e8 28 94 ff e0 83 f8 01 75 07 b8 ff ff 00 00
484	[ 3389.935852] JIT code: 00000040: eb 02 31 c0 c9 c3
485	
486	In the kernel source tree under tools/net/, there's bpf_jit_disasm for
487	generating disassembly out of the kernel log's hexdump:
488	
489	# ./bpf_jit_disasm
490	70 bytes emitted from JIT compiler (pass:3, flen:6)
491	ffffffffa0069c8f + <x>:
492	   0:	push   %rbp
493	   1:	mov    %rsp,%rbp
494	   4:	sub    $0x60,%rsp
495	   8:	mov    %rbx,-0x8(%rbp)
496	   c:	mov    0x68(%rdi),%r9d
497	  10:	sub    0x6c(%rdi),%r9d
498	  14:	mov    0xd8(%rdi),%r8
499	  1b:	mov    $0xc,%esi
500	  20:	callq  0xffffffffe0ff9442
501	  25:	cmp    $0x800,%eax
502	  2a:	jne    0x0000000000000042
503	  2c:	mov    $0x17,%esi
504	  31:	callq  0xffffffffe0ff945e
505	  36:	cmp    $0x1,%eax
506	  39:	jne    0x0000000000000042
507	  3b:	mov    $0xffff,%eax
508	  40:	jmp    0x0000000000000044
509	  42:	xor    %eax,%eax
510	  44:	leaveq
511	  45:	retq
512	
513	Issuing option `-o` will "annotate" opcodes to resulting assembler
514	instructions, which can be very useful for JIT developers:
515	
516	# ./bpf_jit_disasm -o
517	70 bytes emitted from JIT compiler (pass:3, flen:6)
518	ffffffffa0069c8f + <x>:
519	   0:	push   %rbp
520		55
521	   1:	mov    %rsp,%rbp
522		48 89 e5
523	   4:	sub    $0x60,%rsp
524		48 83 ec 60
525	   8:	mov    %rbx,-0x8(%rbp)
526		48 89 5d f8
527	   c:	mov    0x68(%rdi),%r9d
528		44 8b 4f 68
529	  10:	sub    0x6c(%rdi),%r9d
530		44 2b 4f 6c
531	  14:	mov    0xd8(%rdi),%r8
532		4c 8b 87 d8 00 00 00
533	  1b:	mov    $0xc,%esi
534		be 0c 00 00 00
535	  20:	callq  0xffffffffe0ff9442
536		e8 1d 94 ff e0
537	  25:	cmp    $0x800,%eax
538		3d 00 08 00 00
539	  2a:	jne    0x0000000000000042
540		75 16
541	  2c:	mov    $0x17,%esi
542		be 17 00 00 00
543	  31:	callq  0xffffffffe0ff945e
544		e8 28 94 ff e0
545	  36:	cmp    $0x1,%eax
546		83 f8 01
547	  39:	jne    0x0000000000000042
548		75 07
549	  3b:	mov    $0xffff,%eax
550		b8 ff ff 00 00
551	  40:	jmp    0x0000000000000044
552		eb 02
553	  42:	xor    %eax,%eax
554		31 c0
555	  44:	leaveq
556		c9
557	  45:	retq
558		c3
559	
560	For BPF JIT developers, bpf_jit_disasm, bpf_asm and bpf_dbg provides a useful
561	toolchain for developing and testing the kernel's JIT compiler.
562	
563	BPF kernel internals
564	--------------------
565	Internally, for the kernel interpreter, a different instruction set
566	format with similar underlying principles from BPF described in previous
567	paragraphs is being used. However, the instruction set format is modelled
568	closer to the underlying architecture to mimic native instruction sets, so
569	that a better performance can be achieved (more details later). This new
570	ISA is called 'eBPF' or 'internal BPF' interchangeably. (Note: eBPF which
571	originates from [e]xtended BPF is not the same as BPF extensions! While
572	eBPF is an ISA, BPF extensions date back to classic BPF's 'overloading'
573	of BPF_LD | BPF_{B,H,W} | BPF_ABS instruction.)
574	
575	It is designed to be JITed with one to one mapping, which can also open up
576	the possibility for GCC/LLVM compilers to generate optimized eBPF code through
577	an eBPF backend that performs almost as fast as natively compiled code.
578	
579	The new instruction set was originally designed with the possible goal in
580	mind to write programs in "restricted C" and compile into eBPF with a optional
581	GCC/LLVM backend, so that it can just-in-time map to modern 64-bit CPUs with
582	minimal performance overhead over two steps, that is, C -> eBPF -> native code.
583	
584	Currently, the new format is being used for running user BPF programs, which
585	includes seccomp BPF, classic socket filters, cls_bpf traffic classifier,
586	team driver's classifier for its load-balancing mode, netfilter's xt_bpf
587	extension, PTP dissector/classifier, and much more. They are all internally
588	converted by the kernel into the new instruction set representation and run
589	in the eBPF interpreter. For in-kernel handlers, this all works transparently
590	by using bpf_prog_create() for setting up the filter, resp.
591	bpf_prog_destroy() for destroying it. The macro
592	BPF_PROG_RUN(filter, ctx) transparently invokes eBPF interpreter or JITed
593	code to run the filter. 'filter' is a pointer to struct bpf_prog that we
594	got from bpf_prog_create(), and 'ctx' the given context (e.g.
595	skb pointer). All constraints and restrictions from bpf_check_classic() apply
596	before a conversion to the new layout is being done behind the scenes!
597	
598	Currently, the classic BPF format is being used for JITing on most 32-bit
599	architectures, whereas x86-64, aarch64, s390x, powerpc64, sparc64, arm32 perform
600	JIT compilation from eBPF instruction set.
601	
602	Some core changes of the new internal format:
603	
604	- Number of registers increase from 2 to 10:
605	
606	  The old format had two registers A and X, and a hidden frame pointer. The
607	  new layout extends this to be 10 internal registers and a read-only frame
608	  pointer. Since 64-bit CPUs are passing arguments to functions via registers
609	  the number of args from eBPF program to in-kernel function is restricted
610	  to 5 and one register is used to accept return value from an in-kernel
611	  function. Natively, x86_64 passes first 6 arguments in registers, aarch64/
612	  sparcv9/mips64 have 7 - 8 registers for arguments; x86_64 has 6 callee saved
613	  registers, and aarch64/sparcv9/mips64 have 11 or more callee saved registers.
614	
615	  Therefore, eBPF calling convention is defined as:
616	
617	    * R0	- return value from in-kernel function, and exit value for eBPF program
618	    * R1 - R5	- arguments from eBPF program to in-kernel function
619	    * R6 - R9	- callee saved registers that in-kernel function will preserve
620	    * R10	- read-only frame pointer to access stack
621	
622	  Thus, all eBPF registers map one to one to HW registers on x86_64, aarch64,
623	  etc, and eBPF calling convention maps directly to ABIs used by the kernel on
624	  64-bit architectures.
625	
626	  On 32-bit architectures JIT may map programs that use only 32-bit arithmetic
627	  and may let more complex programs to be interpreted.
628	
629	  R0 - R5 are scratch registers and eBPF program needs spill/fill them if
630	  necessary across calls. Note that there is only one eBPF program (== one
631	  eBPF main routine) and it cannot call other eBPF functions, it can only
632	  call predefined in-kernel functions, though.
633	
634	- Register width increases from 32-bit to 64-bit:
635	
636	  Still, the semantics of the original 32-bit ALU operations are preserved
637	  via 32-bit subregisters. All eBPF registers are 64-bit with 32-bit lower
638	  subregisters that zero-extend into 64-bit if they are being written to.
639	  That behavior maps directly to x86_64 and arm64 subregister definition, but
640	  makes other JITs more difficult.
641	
642	  32-bit architectures run 64-bit internal BPF programs via interpreter.
643	  Their JITs may convert BPF programs that only use 32-bit subregisters into
644	  native instruction set and let the rest being interpreted.
645	
646	  Operation is 64-bit, because on 64-bit architectures, pointers are also
647	  64-bit wide, and we want to pass 64-bit values in/out of kernel functions,
648	  so 32-bit eBPF registers would otherwise require to define register-pair
649	  ABI, thus, there won't be able to use a direct eBPF register to HW register
650	  mapping and JIT would need to do combine/split/move operations for every
651	  register in and out of the function, which is complex, bug prone and slow.
652	  Another reason is the use of atomic 64-bit counters.
653	
654	- Conditional jt/jf targets replaced with jt/fall-through:
655	
656	  While the original design has constructs such as "if (cond) jump_true;
657	  else jump_false;", they are being replaced into alternative constructs like
658	  "if (cond) jump_true; /* else fall-through */".
659	
660	- Introduces bpf_call insn and register passing convention for zero overhead
661	  calls from/to other kernel functions:
662	
663	  Before an in-kernel function call, the internal BPF program needs to
664	  place function arguments into R1 to R5 registers to satisfy calling
665	  convention, then the interpreter will take them from registers and pass
666	  to in-kernel function. If R1 - R5 registers are mapped to CPU registers
667	  that are used for argument passing on given architecture, the JIT compiler
668	  doesn't need to emit extra moves. Function arguments will be in the correct
669	  registers and BPF_CALL instruction will be JITed as single 'call' HW
670	  instruction. This calling convention was picked to cover common call
671	  situations without performance penalty.
672	
673	  After an in-kernel function call, R1 - R5 are reset to unreadable and R0 has
674	  a return value of the function. Since R6 - R9 are callee saved, their state
675	  is preserved across the call.
676	
677	  For example, consider three C functions:
678	
679	  u64 f1() { return (*_f2)(1); }
680	  u64 f2(u64 a) { return f3(a + 1, a); }
681	  u64 f3(u64 a, u64 b) { return a - b; }
682	
683	  GCC can compile f1, f3 into x86_64:
684	
685	  f1:
686	    movl $1, %edi
687	    movq _f2(%rip), %rax
688	    jmp  *%rax
689	  f3:
690	    movq %rdi, %rax
691	    subq %rsi, %rax
692	    ret
693	
694	  Function f2 in eBPF may look like:
695	
696	  f2:
697	    bpf_mov R2, R1
698	    bpf_add R1, 1
699	    bpf_call f3
700	    bpf_exit
701	
702	  If f2 is JITed and the pointer stored to '_f2'. The calls f1 -> f2 -> f3 and
703	  returns will be seamless. Without JIT, __bpf_prog_run() interpreter needs to
704	  be used to call into f2.
705	
706	  For practical reasons all eBPF programs have only one argument 'ctx' which is
707	  already placed into R1 (e.g. on __bpf_prog_run() startup) and the programs
708	  can call kernel functions with up to 5 arguments. Calls with 6 or more arguments
709	  are currently not supported, but these restrictions can be lifted if necessary
710	  in the future.
711	
712	  On 64-bit architectures all register map to HW registers one to one. For
713	  example, x86_64 JIT compiler can map them as ...
714	
715	    R0 - rax
716	    R1 - rdi
717	    R2 - rsi
718	    R3 - rdx
719	    R4 - rcx
720	    R5 - r8
721	    R6 - rbx
722	    R7 - r13
723	    R8 - r14
724	    R9 - r15
725	    R10 - rbp
726	
727	  ... since x86_64 ABI mandates rdi, rsi, rdx, rcx, r8, r9 for argument passing
728	  and rbx, r12 - r15 are callee saved.
729	
730	  Then the following internal BPF pseudo-program:
731	
732	    bpf_mov R6, R1 /* save ctx */
733	    bpf_mov R2, 2
734	    bpf_mov R3, 3
735	    bpf_mov R4, 4
736	    bpf_mov R5, 5
737	    bpf_call foo
738	    bpf_mov R7, R0 /* save foo() return value */
739	    bpf_mov R1, R6 /* restore ctx for next call */
740	    bpf_mov R2, 6
741	    bpf_mov R3, 7
742	    bpf_mov R4, 8
743	    bpf_mov R5, 9
744	    bpf_call bar
745	    bpf_add R0, R7
746	    bpf_exit
747	
748	  After JIT to x86_64 may look like:
749	
750	    push %rbp
751	    mov %rsp,%rbp
752	    sub $0x228,%rsp
753	    mov %rbx,-0x228(%rbp)
754	    mov %r13,-0x220(%rbp)
755	    mov %rdi,%rbx
756	    mov $0x2,%esi
757	    mov $0x3,%edx
758	    mov $0x4,%ecx
759	    mov $0x5,%r8d
760	    callq foo
761	    mov %rax,%r13
762	    mov %rbx,%rdi
763	    mov $0x2,%esi
764	    mov $0x3,%edx
765	    mov $0x4,%ecx
766	    mov $0x5,%r8d
767	    callq bar
768	    add %r13,%rax
769	    mov -0x228(%rbp),%rbx
770	    mov -0x220(%rbp),%r13
771	    leaveq
772	    retq
773	
774	  Which is in this example equivalent in C to:
775	
776	    u64 bpf_filter(u64 ctx)
777	    {
778	        return foo(ctx, 2, 3, 4, 5) + bar(ctx, 6, 7, 8, 9);
779	    }
780	
781	  In-kernel functions foo() and bar() with prototype: u64 (*)(u64 arg1, u64
782	  arg2, u64 arg3, u64 arg4, u64 arg5); will receive arguments in proper
783	  registers and place their return value into '%rax' which is R0 in eBPF.
784	  Prologue and epilogue are emitted by JIT and are implicit in the
785	  interpreter. R0-R5 are scratch registers, so eBPF program needs to preserve
786	  them across the calls as defined by calling convention.
787	
788	  For example the following program is invalid:
789	
790	    bpf_mov R1, 1
791	    bpf_call foo
792	    bpf_mov R0, R1
793	    bpf_exit
794	
795	  After the call the registers R1-R5 contain junk values and cannot be read.
796	  An in-kernel eBPF verifier is used to validate internal BPF programs.
797	
798	Also in the new design, eBPF is limited to 4096 insns, which means that any
799	program will terminate quickly and will only call a fixed number of kernel
800	functions. Original BPF and the new format are two operand instructions,
801	which helps to do one-to-one mapping between eBPF insn and x86 insn during JIT.
802	
803	The input context pointer for invoking the interpreter function is generic,
804	its content is defined by a specific use case. For seccomp register R1 points
805	to seccomp_data, for converted BPF filters R1 points to a skb.
806	
807	A program, that is translated internally consists of the following elements:
808	
809	  op:16, jt:8, jf:8, k:32    ==>    op:8, dst_reg:4, src_reg:4, off:16, imm:32
810	
811	So far 87 internal BPF instructions were implemented. 8-bit 'op' opcode field
812	has room for new instructions. Some of them may use 16/24/32 byte encoding. New
813	instructions must be multiple of 8 bytes to preserve backward compatibility.
814	
815	Internal BPF is a general purpose RISC instruction set. Not every register and
816	every instruction are used during translation from original BPF to new format.
817	For example, socket filters are not using 'exclusive add' instruction, but
818	tracing filters may do to maintain counters of events, for example. Register R9
819	is not used by socket filters either, but more complex filters may be running
820	out of registers and would have to resort to spill/fill to stack.
821	
822	Internal BPF can used as generic assembler for last step performance
823	optimizations, socket filters and seccomp are using it as assembler. Tracing
824	filters may use it as assembler to generate code from kernel. In kernel usage
825	may not be bounded by security considerations, since generated internal BPF code
826	may be optimizing internal code path and not being exposed to the user space.
827	Safety of internal BPF can come from a verifier (TBD). In such use cases as
828	described, it may be used as safe instruction set.
829	
830	Just like the original BPF, the new format runs within a controlled environment,
831	is deterministic and the kernel can easily prove that. The safety of the program
832	can be determined in two steps: first step does depth-first-search to disallow
833	loops and other CFG validation; second step starts from the first insn and
834	descends all possible paths. It simulates execution of every insn and observes
835	the state change of registers and stack.
836	
837	eBPF opcode encoding
838	--------------------
839	
840	eBPF is reusing most of the opcode encoding from classic to simplify conversion
841	of classic BPF to eBPF. For arithmetic and jump instructions the 8-bit 'code'
842	field is divided into three parts:
843	
844	  +----------------+--------+--------------------+
845	  |   4 bits       |  1 bit |   3 bits           |
846	  | operation code | source | instruction class  |
847	  +----------------+--------+--------------------+
848	  (MSB)                                      (LSB)
849	
850	Three LSB bits store instruction class which is one of:
851	
852	  Classic BPF classes:    eBPF classes:
853	
854	  BPF_LD    0x00          BPF_LD    0x00
855	  BPF_LDX   0x01          BPF_LDX   0x01
856	  BPF_ST    0x02          BPF_ST    0x02
857	  BPF_STX   0x03          BPF_STX   0x03
858	  BPF_ALU   0x04          BPF_ALU   0x04
859	  BPF_JMP   0x05          BPF_JMP   0x05
860	  BPF_RET   0x06          [ class 6 unused, for future if needed ]
861	  BPF_MISC  0x07          BPF_ALU64 0x07
862	
863	When BPF_CLASS(code) == BPF_ALU or BPF_JMP, 4th bit encodes source operand ...
864	
865	  BPF_K     0x00
866	  BPF_X     0x08
867	
868	 * in classic BPF, this means:
869	
870	  BPF_SRC(code) == BPF_X - use register X as source operand
871	  BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
872	
873	 * in eBPF, this means:
874	
875	  BPF_SRC(code) == BPF_X - use 'src_reg' register as source operand
876	  BPF_SRC(code) == BPF_K - use 32-bit immediate as source operand
877	
878	... and four MSB bits store operation code.
879	
880	If BPF_CLASS(code) == BPF_ALU or BPF_ALU64 [ in eBPF ], BPF_OP(code) is one of:
881	
882	  BPF_ADD   0x00
883	  BPF_SUB   0x10
884	  BPF_MUL   0x20
885	  BPF_DIV   0x30
886	  BPF_OR    0x40
887	  BPF_AND   0x50
888	  BPF_LSH   0x60
889	  BPF_RSH   0x70
890	  BPF_NEG   0x80
891	  BPF_MOD   0x90
892	  BPF_XOR   0xa0
893	  BPF_MOV   0xb0  /* eBPF only: mov reg to reg */
894	  BPF_ARSH  0xc0  /* eBPF only: sign extending shift right */
895	  BPF_END   0xd0  /* eBPF only: endianness conversion */
896	
897	If BPF_CLASS(code) == BPF_JMP, BPF_OP(code) is one of:
898	
899	  BPF_JA    0x00
900	  BPF_JEQ   0x10
901	  BPF_JGT   0x20
902	  BPF_JGE   0x30
903	  BPF_JSET  0x40
904	  BPF_JNE   0x50  /* eBPF only: jump != */
905	  BPF_JSGT  0x60  /* eBPF only: signed '>' */
906	  BPF_JSGE  0x70  /* eBPF only: signed '>=' */
907	  BPF_CALL  0x80  /* eBPF only: function call */
908	  BPF_EXIT  0x90  /* eBPF only: function return */
909	  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 '<=' */
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	
958	  BPF_IMM  0x00  /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
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	
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	
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.
1024	If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,
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
1046	are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
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.
1065	If R6=PTR_TO_STACK, then access should be aligned and be within
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.
1076	Though R10 is correct read-only register and has type PTR_TO_STACK
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	
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; 0xbf), 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	
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:
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
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
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
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).
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
1215	available for direct packet access.
1216	Operation 'r3 += rX' may overflow and become less than original skb->data,
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.
1221	Ex. after insn 'r4 = *(u8 *)(r3 +12)' (insn #7 above) the state of r4 is
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.
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	
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	
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	
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	
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	
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>
1466	Daniel Borkmann <daniel@iogearbox.net>
1467	Alexei Starovoitov <ast@kernel.org>
Hide Line Numbers
About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Information is copyright its respective author. All material is available from the Linux Kernel Source distributed under a GPL License. This page is provided as a free service by mjmwired.net.