1
2=============
3eBPF verifier
4=============
5
6The safety of the eBPF program is determined in two steps.
7
8First step does DAG check to disallow loops and other CFG validation.
9In particular it will detect programs that have unreachable instructions.
10(though classic BPF checker allows them)
11
12Second step starts from the first insn and descends all possible paths.
13It simulates execution of every insn and observes the state change of
14registers and stack.
15
16At the start of the program the register R1 contains a pointer to context
17and has type PTR_TO_CTX.
18If verifier sees an insn that does R2=R1, then R2 has now type
19PTR_TO_CTX as well and can be used on the right hand side of expression.
20If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=SCALAR_VALUE,
21since addition of two valid pointers makes invalid pointer.
22(In 'secure' mode verifier will reject any type of pointer arithmetic to make
23sure that kernel addresses don't leak to unprivileged users)
24
25If register was never written to, it's not readable::
26
27  bpf_mov R0 = R2
28  bpf_exit
29
30will be rejected, since R2 is unreadable at the start of the program.
31
32After kernel function call, R1-R5 are reset to unreadable and
33R0 has a return type of the function.
34
35Since R6-R9 are callee saved, their state is preserved across the call.
36
37::
38
39  bpf_mov R6 = 1
40  bpf_call foo
41  bpf_mov R0 = R6
42  bpf_exit
43
44is a correct program. If there was R1 instead of R6, it would have
45been rejected.
46
47load/store instructions are allowed only with registers of valid types, which
48are PTR_TO_CTX, PTR_TO_MAP, PTR_TO_STACK. They are bounds and alignment checked.
49For example::
50
51 bpf_mov R1 = 1
52 bpf_mov R2 = 2
53 bpf_xadd *(u32 *)(R1 + 3) += R2
54 bpf_exit
55
56will be rejected, since R1 doesn't have a valid pointer type at the time of
57execution of instruction bpf_xadd.
58
59At the start R1 type is PTR_TO_CTX (a pointer to generic ``struct bpf_context``)
60A callback is used to customize verifier to restrict eBPF program access to only
61certain fields within ctx structure with specified size and alignment.
62
63For example, the following insn::
64
65  bpf_ld R0 = *(u32 *)(R6 + 8)
66
67intends to load a word from address R6 + 8 and store it into R0
68If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
69that offset 8 of size 4 bytes can be accessed for reading, otherwise
70the verifier will reject the program.
71If R6=PTR_TO_STACK, then access should be aligned and be within
72stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
73so it will fail verification, since it's out of bounds.
74
75The verifier will allow eBPF program to read data from stack only after
76it wrote into it.
77
78Classic BPF verifier does similar check with M[0-15] memory slots.
79For example::
80
81  bpf_ld R0 = *(u32 *)(R10 - 4)
82  bpf_exit
83
84is invalid program.
85Though R10 is correct read-only register and has type PTR_TO_STACK
86and R10 - 4 is within stack bounds, there were no stores into that location.
87
88Pointer register spill/fill is tracked as well, since four (R6-R9)
89callee saved registers may not be enough for some programs.
90
91Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
92The eBPF verifier will check that registers match argument constraints.
93After the call register R0 will be set to return type of the function.
94
95Function calls is a main mechanism to extend functionality of eBPF programs.
96Socket filters may let programs to call one set of functions, whereas tracing
97filters may allow completely different set.
98
99If a function made accessible to eBPF program, it needs to be thought through
100from safety point of view. The verifier will guarantee that the function is
101called with valid arguments.
102
103seccomp vs socket filters have different security restrictions for classic BPF.
104Seccomp solves this by two stage verifier: classic BPF verifier is followed
105by seccomp verifier. In case of eBPF one configurable verifier is shared for
106all use cases.
107
108See details of eBPF verifier in kernel/bpf/verifier.c
109
110Register value tracking
111=======================
112
113In order to determine the safety of an eBPF program, the verifier must track
114the range of possible values in each register and also in each stack slot.
115This is done with ``struct bpf_reg_state``, defined in include/linux/
116bpf_verifier.h, which unifies tracking of scalar and pointer values.  Each
117register state has a type, which is either NOT_INIT (the register has not been
118written to), SCALAR_VALUE (some value which is not usable as a pointer), or a
119pointer type.  The types of pointers describe their base, as follows:
120
121
122    PTR_TO_CTX
123			Pointer to bpf_context.
124    CONST_PTR_TO_MAP
125			Pointer to struct bpf_map.  "Const" because arithmetic
126			on these pointers is forbidden.
127    PTR_TO_MAP_VALUE
128			Pointer to the value stored in a map element.
129    PTR_TO_MAP_VALUE_OR_NULL
130			Either a pointer to a map value, or NULL; map accesses
131			(see maps.rst) return this type, which becomes a
132			PTR_TO_MAP_VALUE when checked != NULL. Arithmetic on
133			these pointers is forbidden.
134    PTR_TO_STACK
135			Frame pointer.
136    PTR_TO_PACKET
137			skb->data.
138    PTR_TO_PACKET_END
139			skb->data + headlen; arithmetic forbidden.
140    PTR_TO_SOCKET
141			Pointer to struct bpf_sock_ops, implicitly refcounted.
142    PTR_TO_SOCKET_OR_NULL
143			Either a pointer to a socket, or NULL; socket lookup
144			returns this type, which becomes a PTR_TO_SOCKET when
145			checked != NULL. PTR_TO_SOCKET is reference-counted,
146			so programs must release the reference through the
147			socket release function before the end of the program.
148			Arithmetic on these pointers is forbidden.
149
150However, a pointer may be offset from this base (as a result of pointer
151arithmetic), and this is tracked in two parts: the 'fixed offset' and 'variable
152offset'.  The former is used when an exactly-known value (e.g. an immediate
153operand) is added to a pointer, while the latter is used for values which are
154not exactly known.  The variable offset is also used in SCALAR_VALUEs, to track
155the range of possible values in the register.
156
157The verifier's knowledge about the variable offset consists of:
158
159* minimum and maximum values as unsigned
160* minimum and maximum values as signed
161
162* knowledge of the values of individual bits, in the form of a 'tnum': a u64
163  'mask' and a u64 'value'.  1s in the mask represent bits whose value is unknown;
164  1s in the value represent bits known to be 1.  Bits known to be 0 have 0 in both
165  mask and value; no bit should ever be 1 in both.  For example, if a byte is read
166  into a register from memory, the register's top 56 bits are known zero, while
167  the low 8 are unknown - which is represented as the tnum (0x0; 0xff).  If we
168  then OR this with 0x40, we get (0x40; 0xbf), then if we add 1 we get (0x0;
169  0x1ff), because of potential carries.
170
171Besides arithmetic, the register state can also be updated by conditional
172branches.  For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch
173it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false'
174branch it will have a umax_value of 8.  A signed compare (with BPF_JSGT or
175BPF_JSGE) would instead update the signed minimum/maximum values.  Information
176from the signed and unsigned bounds can be combined; for instance if a value is
177first tested < 8 and then tested s> 4, the verifier will conclude that the value
178is also > 4 and s< 8, since the bounds prevent crossing the sign boundary.
179
180PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all
181pointers sharing that same variable offset.  This is important for packet range
182checks: after adding a variable to a packet pointer register A, if you then copy
183it to another register B and then add a constant 4 to A, both registers will
184share the same 'id' but the A will have a fixed offset of +4.  Then if A is
185bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is
186now known to have a safe range of at least 4 bytes.  See 'Direct packet access',
187below, for more on PTR_TO_PACKET ranges.
188
189The 'id' field is also used on PTR_TO_MAP_VALUE_OR_NULL, common to all copies of
190the pointer returned from a map lookup.  This means that when one copy is
191checked and found to be non-NULL, all copies can become PTR_TO_MAP_VALUEs.
192As well as range-checking, the tracked information is also used for enforcing
193alignment of pointer accesses.  For instance, on most systems the packet pointer
194is 2 bytes after a 4-byte alignment.  If a program adds 14 bytes to that to jump
195over the Ethernet header, then reads IHL and adds (IHL * 4), the resulting
196pointer will have a variable offset known to be 4n+2 for some n, so adding the 2
197bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through
198that pointer are safe.
199The 'id' field is also used on PTR_TO_SOCKET and PTR_TO_SOCKET_OR_NULL, common
200to all copies of the pointer returned from a socket lookup. This has similar
201behaviour to the handling for PTR_TO_MAP_VALUE_OR_NULL->PTR_TO_MAP_VALUE, but
202it also handles reference tracking for the pointer. PTR_TO_SOCKET implicitly
203represents a reference to the corresponding ``struct sock``. To ensure that the
204reference is not leaked, it is imperative to NULL-check the reference and in
205the non-NULL case, and pass the valid reference to the socket release function.
206
207Direct packet access
208====================
209
210In cls_bpf and act_bpf programs the verifier allows direct access to the packet
211data via skb->data and skb->data_end pointers.
212Ex::
213
214    1:  r4 = *(u32 *)(r1 +80)  /* load skb->data_end */
215    2:  r3 = *(u32 *)(r1 +76)  /* load skb->data */
216    3:  r5 = r3
217    4:  r5 += 14
218    5:  if r5 > r4 goto pc+16
219    R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
220    6:  r0 = *(u16 *)(r3 +12) /* access 12 and 13 bytes of the packet */
221
222this 2byte load from the packet is safe to do, since the program author
223did check ``if (skb->data + 14 > skb->data_end) goto err`` at insn #5 which
224means that in the fall-through case the register R3 (which points to skb->data)
225has at least 14 directly accessible bytes. The verifier marks it
226as R3=pkt(id=0,off=0,r=14).
227id=0 means that no additional variables were added to the register.
228off=0 means that no additional constants were added.
229r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
230Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
231to the packet data, but constant 14 was added to the register, so
232it now points to ``skb->data + 14`` and accessible range is [R5, R5 + 14 - 14)
233which is zero bytes.
234
235More complex packet access may look like::
236
237
238    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
239    6:  r0 = *(u8 *)(r3 +7) /* load 7th byte from the packet */
240    7:  r4 = *(u8 *)(r3 +12)
241    8:  r4 *= 14
242    9:  r3 = *(u32 *)(r1 +76) /* load skb->data */
243    10:  r3 += r4
244    11:  r2 = r1
245    12:  r2 <<= 48
246    13:  r2 >>= 48
247    14:  r3 += r2
248    15:  r2 = r3
249    16:  r2 += 8
250    17:  r1 = *(u32 *)(r1 +80) /* load skb->data_end */
251    18:  if r2 > r1 goto pc+2
252    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
253    19:  r1 = *(u8 *)(r3 +4)
254
255The state of the register R3 is R3=pkt(id=2,off=0,r=8)
256id=2 means that two ``r3 += rX`` instructions were seen, so r3 points to some
257offset within a packet and since the program author did
258``if (r3 + 8 > r1) goto err`` at insn #18, the safe range is [R3, R3 + 8).
259The verifier only allows 'add'/'sub' operations on packet registers. Any other
260operation will set the register state to 'SCALAR_VALUE' and it won't be
261available for direct packet access.
262
263Operation ``r3 += rX`` may overflow and become less than original skb->data,
264therefore the verifier has to prevent that.  So when it sees ``r3 += rX``
265instruction and rX is more than 16-bit value, any subsequent bounds-check of r3
266against skb->data_end will not give us 'range' information, so attempts to read
267through the pointer will give "invalid access to packet" error.
268
269Ex. after insn ``r4 = *(u8 *)(r3 +12)`` (insn #7 above) the state of r4 is
270R4=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) which means that upper 56 bits
271of the register are guaranteed to be zero, and nothing is known about the lower
2728 bits. After insn ``r4 *= 14`` the state becomes
273R4=inv(id=0,umax_value=3570,var_off=(0x0; 0xfffe)), since multiplying an 8-bit
274value by constant 14 will keep upper 52 bits as zero, also the least significant
275bit will be zero as 14 is even.  Similarly ``r2 >>= 48`` will make
276R2=inv(id=0,umax_value=65535,var_off=(0x0; 0xffff)), since the shift is not sign
277extending.  This logic is implemented in adjust_reg_min_max_vals() function,
278which calls adjust_ptr_min_max_vals() for adding pointer to scalar (or vice
279versa) and adjust_scalar_min_max_vals() for operations on two scalars.
280
281The end result is that bpf program author can access packet directly
282using normal C code as::
283
284  void *data = (void *)(long)skb->data;
285  void *data_end = (void *)(long)skb->data_end;
286  struct eth_hdr *eth = data;
287  struct iphdr *iph = data + sizeof(*eth);
288  struct udphdr *udp = data + sizeof(*eth) + sizeof(*iph);
289
290  if (data + sizeof(*eth) + sizeof(*iph) + sizeof(*udp) > data_end)
291	  return 0;
292  if (eth->h_proto != htons(ETH_P_IP))
293	  return 0;
294  if (iph->protocol != IPPROTO_UDP || iph->ihl != 5)
295	  return 0;
296  if (udp->dest == 53 || udp->source == 9)
297	  ...;
298
299which makes such programs easier to write comparing to LD_ABS insn
300and significantly faster.
301
302Pruning
303=======
304
305The verifier does not actually walk all possible paths through the program.  For
306each new branch to analyse, the verifier looks at all the states it's previously
307been in when at this instruction.  If any of them contain the current state as a
308subset, the branch is 'pruned' - that is, the fact that the previous state was
309accepted implies the current state would be as well.  For instance, if in the
310previous state, r1 held a packet-pointer, and in the current state, r1 holds a
311packet-pointer with a range as long or longer and at least as strict an
312alignment, then r1 is safe.  Similarly, if r2 was NOT_INIT before then it can't
313have been used by any path from that point, so any value in r2 (including
314another NOT_INIT) is safe.  The implementation is in the function regsafe().
315Pruning considers not only the registers but also the stack (and any spilled
316registers it may hold).  They must all be safe for the branch to be pruned.
317This is implemented in states_equal().
318
319Some technical details about state pruning implementation could be found below.
320
321Register liveness tracking
322--------------------------
323
324In order to make state pruning effective, liveness state is tracked for each
325register and stack slot. The basic idea is to track which registers and stack
326slots are actually used during subseqeuent execution of the program, until
327program exit is reached. Registers and stack slots that were never used could be
328removed from the cached state thus making more states equivalent to a cached
329state. This could be illustrated by the following program::
330
331  0: call bpf_get_prandom_u32()
332  1: r1 = 0
333  2: if r0 == 0 goto +1
334  3: r0 = 1
335  --- checkpoint ---
336  4: r0 = r1
337  5: exit
338
339Suppose that a state cache entry is created at instruction #4 (such entries are
340also called "checkpoints" in the text below). The verifier could reach the
341instruction with one of two possible register states:
342
343* r0 = 1, r1 = 0
344* r0 = 0, r1 = 0
345
346However, only the value of register ``r1`` is important to successfully finish
347verification. The goal of the liveness tracking algorithm is to spot this fact
348and figure out that both states are actually equivalent.
349
350Data structures
351~~~~~~~~~~~~~~~
352
353Liveness is tracked using the following data structures::
354
355  enum bpf_reg_liveness {
356	REG_LIVE_NONE = 0,
357	REG_LIVE_READ32 = 0x1,
358	REG_LIVE_READ64 = 0x2,
359	REG_LIVE_READ = REG_LIVE_READ32 | REG_LIVE_READ64,
360	REG_LIVE_WRITTEN = 0x4,
361	REG_LIVE_DONE = 0x8,
362  };
363
364  struct bpf_reg_state {
365 	...
366	struct bpf_reg_state *parent;
367 	...
368	enum bpf_reg_liveness live;
369 	...
370  };
371
372  struct bpf_stack_state {
373	struct bpf_reg_state spilled_ptr;
374	...
375  };
376
377  struct bpf_func_state {
378	struct bpf_reg_state regs[MAX_BPF_REG];
379        ...
380	struct bpf_stack_state *stack;
381  }
382
383  struct bpf_verifier_state {
384	struct bpf_func_state *frame[MAX_CALL_FRAMES];
385	struct bpf_verifier_state *parent;
386        ...
387  }
388
389* ``REG_LIVE_NONE`` is an initial value assigned to ``->live`` fields upon new
390  verifier state creation;
391
392* ``REG_LIVE_WRITTEN`` means that the value of the register (or stack slot) is
393  defined by some instruction verified between this verifier state's parent and
394  verifier state itself;
395
396* ``REG_LIVE_READ{32,64}`` means that the value of the register (or stack slot)
397  is read by a some child state of this verifier state;
398
399* ``REG_LIVE_DONE`` is a marker used by ``clean_verifier_state()`` to avoid
400  processing same verifier state multiple times and for some sanity checks;
401
402* ``->live`` field values are formed by combining ``enum bpf_reg_liveness``
403  values using bitwise or.
404
405Register parentage chains
406~~~~~~~~~~~~~~~~~~~~~~~~~
407
408In order to propagate information between parent and child states, a *register
409parentage chain* is established. Each register or stack slot is linked to a
410corresponding register or stack slot in its parent state via a ``->parent``
411pointer. This link is established upon state creation in ``is_state_visited()``
412and might be modified by ``set_callee_state()`` called from
413``__check_func_call()``.
414
415The rules for correspondence between registers / stack slots are as follows:
416
417* For the current stack frame, registers and stack slots of the new state are
418  linked to the registers and stack slots of the parent state with the same
419  indices.
420
421* For the outer stack frames, only caller saved registers (r6-r9) and stack
422  slots are linked to the registers and stack slots of the parent state with the
423  same indices.
424
425* When function call is processed a new ``struct bpf_func_state`` instance is
426  allocated, it encapsulates a new set of registers and stack slots. For this
427  new frame, parent links for r6-r9 and stack slots are set to nil, parent links
428  for r1-r5 are set to match caller r1-r5 parent links.
429
430This could be illustrated by the following diagram (arrows stand for
431``->parent`` pointers)::
432
433      ...                    ; Frame #0, some instructions
434  --- checkpoint #0 ---
435  1 : r6 = 42                ; Frame #0
436  --- checkpoint #1 ---
437  2 : call foo()             ; Frame #0
438      ...                    ; Frame #1, instructions from foo()
439  --- checkpoint #2 ---
440      ...                    ; Frame #1, instructions from foo()
441  --- checkpoint #3 ---
442      exit                   ; Frame #1, return from foo()
443  3 : r1 = r6                ; Frame #0  <- current state
444
445             +-------------------------------+-------------------------------+
446             |           Frame #0            |           Frame #1            |
447  Checkpoint +-------------------------------+-------------------------------+
448  #0         | r0 | r1-r5 | r6-r9 | fp-8 ... |
449             +-------------------------------+
450                ^    ^       ^       ^
451                |    |       |       |
452  Checkpoint +-------------------------------+
453  #1         | r0 | r1-r5 | r6-r9 | fp-8 ... |
454             +-------------------------------+
455                     ^       ^       ^
456                     |_______|_______|_______________
457                             |       |               |
458               nil  nil      |       |               |      nil     nil
459                |    |       |       |               |       |       |
460  Checkpoint +-------------------------------+-------------------------------+
461  #2         | r0 | r1-r5 | r6-r9 | fp-8 ... | r0 | r1-r5 | r6-r9 | fp-8 ... |
462             +-------------------------------+-------------------------------+
463                             ^       ^               ^       ^       ^
464               nil  nil      |       |               |       |       |
465                |    |       |       |               |       |       |
466  Checkpoint +-------------------------------+-------------------------------+
467  #3         | r0 | r1-r5 | r6-r9 | fp-8 ... | r0 | r1-r5 | r6-r9 | fp-8 ... |
468             +-------------------------------+-------------------------------+
469                             ^       ^
470               nil  nil      |       |
471                |    |       |       |
472  Current    +-------------------------------+
473  state      | r0 | r1-r5 | r6-r9 | fp-8 ... |
474             +-------------------------------+
475                             \
476                               r6 read mark is propagated via these links
477                               all the way up to checkpoint #1.
478                               The checkpoint #1 contains a write mark for r6
479                               because of instruction (1), thus read propagation
480                               does not reach checkpoint #0 (see section below).
481
482Liveness marks tracking
483~~~~~~~~~~~~~~~~~~~~~~~
484
485For each processed instruction, the verifier tracks read and written registers
486and stack slots. The main idea of the algorithm is that read marks propagate
487back along the state parentage chain until they hit a write mark, which 'screens
488off' earlier states from the read. The information about reads is propagated by
489function ``mark_reg_read()`` which could be summarized as follows::
490
491  mark_reg_read(struct bpf_reg_state *state, ...):
492      parent = state->parent
493      while parent:
494          if state->live & REG_LIVE_WRITTEN:
495              break
496          if parent->live & REG_LIVE_READ64:
497              break
498          parent->live |= REG_LIVE_READ64
499          state = parent
500          parent = state->parent
501
502Notes:
503
504* The read marks are applied to the **parent** state while write marks are
505  applied to the **current** state. The write mark on a register or stack slot
506  means that it is updated by some instruction in the straight-line code leading
507  from the parent state to the current state.
508
509* Details about REG_LIVE_READ32 are omitted.
510
511* Function ``propagate_liveness()`` (see section :ref:`read_marks_for_cache_hits`)
512  might override the first parent link. Please refer to the comments in the
513  ``propagate_liveness()`` and ``mark_reg_read()`` source code for further
514  details.
515
516Because stack writes could have different sizes ``REG_LIVE_WRITTEN`` marks are
517applied conservatively: stack slots are marked as written only if write size
518corresponds to the size of the register, e.g. see function ``save_register_state()``.
519
520Consider the following example::
521
522  0: (*u64)(r10 - 8) = 0   ; define 8 bytes of fp-8
523  --- checkpoint #0 ---
524  1: (*u32)(r10 - 8) = 1   ; redefine lower 4 bytes
525  2: r1 = (*u32)(r10 - 8)  ; read lower 4 bytes defined at (1)
526  3: r2 = (*u32)(r10 - 4)  ; read upper 4 bytes defined at (0)
527
528As stated above, the write at (1) does not count as ``REG_LIVE_WRITTEN``. Should
529it be otherwise, the algorithm above wouldn't be able to propagate the read mark
530from (3) to checkpoint #0.
531
532Once the ``BPF_EXIT`` instruction is reached ``update_branch_counts()`` is
533called to update the ``->branches`` counter for each verifier state in a chain
534of parent verifier states. When the ``->branches`` counter reaches zero the
535verifier state becomes a valid entry in a set of cached verifier states.
536
537Each entry of the verifier states cache is post-processed by a function
538``clean_live_states()``. This function marks all registers and stack slots
539without ``REG_LIVE_READ{32,64}`` marks as ``NOT_INIT`` or ``STACK_INVALID``.
540Registers/stack slots marked in this way are ignored in function ``stacksafe()``
541called from ``states_equal()`` when a state cache entry is considered for
542equivalence with a current state.
543
544Now it is possible to explain how the example from the beginning of the section
545works::
546
547  0: call bpf_get_prandom_u32()
548  1: r1 = 0
549  2: if r0 == 0 goto +1
550  3: r0 = 1
551  --- checkpoint[0] ---
552  4: r0 = r1
553  5: exit
554
555* At instruction #2 branching point is reached and state ``{ r0 == 0, r1 == 0, pc == 4 }``
556  is pushed to states processing queue (pc stands for program counter).
557
558* At instruction #4:
559
560  * ``checkpoint[0]`` states cache entry is created: ``{ r0 == 1, r1 == 0, pc == 4 }``;
561  * ``checkpoint[0].r0`` is marked as written;
562  * ``checkpoint[0].r1`` is marked as read;
563
564* At instruction #5 exit is reached and ``checkpoint[0]`` can now be processed
565  by ``clean_live_states()``. After this processing ``checkpoint[0].r0`` has a
566  read mark and all other registers and stack slots are marked as ``NOT_INIT``
567  or ``STACK_INVALID``
568
569* The state ``{ r0 == 0, r1 == 0, pc == 4 }`` is popped from the states queue
570  and is compared against a cached state ``{ r1 == 0, pc == 4 }``, the states
571  are considered equivalent.
572
573.. _read_marks_for_cache_hits:
574
575Read marks propagation for cache hits
576~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
577
578Another point is the handling of read marks when a previously verified state is
579found in the states cache. Upon cache hit verifier must behave in the same way
580as if the current state was verified to the program exit. This means that all
581read marks, present on registers and stack slots of the cached state, must be
582propagated over the parentage chain of the current state. Example below shows
583why this is important. Function ``propagate_liveness()`` handles this case.
584
585Consider the following state parentage chain (S is a starting state, A-E are
586derived states, -> arrows show which state is derived from which)::
587
588                   r1 read
589            <-------------                A[r1] == 0
590                                          C[r1] == 0
591      S ---> A ---> B ---> exit           E[r1] == 1
592      |
593      ` ---> C ---> D
594      |
595      ` ---> E      ^
596                    |___   suppose all these
597             ^           states are at insn #Y
598             |
599      suppose all these
600    states are at insn #X
601
602* Chain of states ``S -> A -> B -> exit`` is verified first.
603
604* While ``B -> exit`` is verified, register ``r1`` is read and this read mark is
605  propagated up to state ``A``.
606
607* When chain of states ``C -> D`` is verified the state ``D`` turns out to be
608  equivalent to state ``B``.
609
610* The read mark for ``r1`` has to be propagated to state ``C``, otherwise state
611  ``C`` might get mistakenly marked as equivalent to state ``E`` even though
612  values for register ``r1`` differ between ``C`` and ``E``.
613
614Understanding eBPF verifier messages
615====================================
616
617The following are few examples of invalid eBPF programs and verifier error
618messages as seen in the log:
619
620Program with unreachable instructions::
621
622  static struct bpf_insn prog[] = {
623  BPF_EXIT_INSN(),
624  BPF_EXIT_INSN(),
625  };
626
627Error::
628
629  unreachable insn 1
630
631Program that reads uninitialized register::
632
633  BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
634  BPF_EXIT_INSN(),
635
636Error::
637
638  0: (bf) r0 = r2
639  R2 !read_ok
640
641Program that doesn't initialize R0 before exiting::
642
643  BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
644  BPF_EXIT_INSN(),
645
646Error::
647
648  0: (bf) r2 = r1
649  1: (95) exit
650  R0 !read_ok
651
652Program that accesses stack out of bounds::
653
654    BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
655    BPF_EXIT_INSN(),
656
657Error::
658
659    0: (7a) *(u64 *)(r10 +8) = 0
660    invalid stack off=8 size=8
661
662Program that doesn't initialize stack before passing its address into function::
663
664  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
665  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
666  BPF_LD_MAP_FD(BPF_REG_1, 0),
667  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
668  BPF_EXIT_INSN(),
669
670Error::
671
672  0: (bf) r2 = r10
673  1: (07) r2 += -8
674  2: (b7) r1 = 0x0
675  3: (85) call 1
676  invalid indirect read from stack off -8+0 size 8
677
678Program that uses invalid map_fd=0 while calling to map_lookup_elem() function::
679
680  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
681  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
682  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
683  BPF_LD_MAP_FD(BPF_REG_1, 0),
684  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
685  BPF_EXIT_INSN(),
686
687Error::
688
689  0: (7a) *(u64 *)(r10 -8) = 0
690  1: (bf) r2 = r10
691  2: (07) r2 += -8
692  3: (b7) r1 = 0x0
693  4: (85) call 1
694  fd 0 is not pointing to valid bpf_map
695
696Program that doesn't check return value of map_lookup_elem() before accessing
697map element::
698
699  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
700  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
701  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
702  BPF_LD_MAP_FD(BPF_REG_1, 0),
703  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
704  BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
705  BPF_EXIT_INSN(),
706
707Error::
708
709  0: (7a) *(u64 *)(r10 -8) = 0
710  1: (bf) r2 = r10
711  2: (07) r2 += -8
712  3: (b7) r1 = 0x0
713  4: (85) call 1
714  5: (7a) *(u64 *)(r0 +0) = 0
715  R0 invalid mem access 'map_value_or_null'
716
717Program that correctly checks map_lookup_elem() returned value for NULL, but
718accesses the memory with incorrect alignment::
719
720  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
721  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
722  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
723  BPF_LD_MAP_FD(BPF_REG_1, 0),
724  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
725  BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
726  BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
727  BPF_EXIT_INSN(),
728
729Error::
730
731  0: (7a) *(u64 *)(r10 -8) = 0
732  1: (bf) r2 = r10
733  2: (07) r2 += -8
734  3: (b7) r1 = 1
735  4: (85) call 1
736  5: (15) if r0 == 0x0 goto pc+1
737   R0=map_ptr R10=fp
738  6: (7a) *(u64 *)(r0 +4) = 0
739  misaligned access off 4 size 8
740
741Program that correctly checks map_lookup_elem() returned value for NULL and
742accesses memory with correct alignment in one side of 'if' branch, but fails
743to do so in the other side of 'if' branch::
744
745  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
746  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
747  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
748  BPF_LD_MAP_FD(BPF_REG_1, 0),
749  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
750  BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
751  BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
752  BPF_EXIT_INSN(),
753  BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
754  BPF_EXIT_INSN(),
755
756Error::
757
758  0: (7a) *(u64 *)(r10 -8) = 0
759  1: (bf) r2 = r10
760  2: (07) r2 += -8
761  3: (b7) r1 = 1
762  4: (85) call 1
763  5: (15) if r0 == 0x0 goto pc+2
764   R0=map_ptr R10=fp
765  6: (7a) *(u64 *)(r0 +0) = 0
766  7: (95) exit
767
768  from 5 to 8: R0=imm0 R10=fp
769  8: (7a) *(u64 *)(r0 +0) = 1
770  R0 invalid mem access 'imm'
771
772Program that performs a socket lookup then sets the pointer to NULL without
773checking it::
774
775  BPF_MOV64_IMM(BPF_REG_2, 0),
776  BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
777  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
778  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
779  BPF_MOV64_IMM(BPF_REG_3, 4),
780  BPF_MOV64_IMM(BPF_REG_4, 0),
781  BPF_MOV64_IMM(BPF_REG_5, 0),
782  BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
783  BPF_MOV64_IMM(BPF_REG_0, 0),
784  BPF_EXIT_INSN(),
785
786Error::
787
788  0: (b7) r2 = 0
789  1: (63) *(u32 *)(r10 -8) = r2
790  2: (bf) r2 = r10
791  3: (07) r2 += -8
792  4: (b7) r3 = 4
793  5: (b7) r4 = 0
794  6: (b7) r5 = 0
795  7: (85) call bpf_sk_lookup_tcp#65
796  8: (b7) r0 = 0
797  9: (95) exit
798  Unreleased reference id=1, alloc_insn=7
799
800Program that performs a socket lookup but does not NULL-check the returned
801value::
802
803  BPF_MOV64_IMM(BPF_REG_2, 0),
804  BPF_STX_MEM(BPF_W, BPF_REG_10, BPF_REG_2, -8),
805  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
806  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
807  BPF_MOV64_IMM(BPF_REG_3, 4),
808  BPF_MOV64_IMM(BPF_REG_4, 0),
809  BPF_MOV64_IMM(BPF_REG_5, 0),
810  BPF_EMIT_CALL(BPF_FUNC_sk_lookup_tcp),
811  BPF_EXIT_INSN(),
812
813Error::
814
815  0: (b7) r2 = 0
816  1: (63) *(u32 *)(r10 -8) = r2
817  2: (bf) r2 = r10
818  3: (07) r2 += -8
819  4: (b7) r3 = 4
820  5: (b7) r4 = 0
821  6: (b7) r5 = 0
822  7: (85) call bpf_sk_lookup_tcp#65
823  8: (95) exit
824  Unreleased reference id=1, alloc_insn=7
825