About Kernel Documentation Linux Kernel Contact Linux Resources Linux Blog

Documentation / networking / filter.txt




Custom Search

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