Documentation/bpf/verifier.rst

16 At the start of the program the register R1 contains a pointer to context
33 R0 has a return type of the function.
44 is a correct program. If there was R1 instead of R6, it would have
56 will be rejected, since R1 doesn't have a valid pointer type at the time of
59 At the start R1 type is PTR_TO_CTX (a pointer to generic ``struct bpf_context``)
60 A callback is used to customize verifier to restrict eBPF program access to only
67 intends to load a word from address R6 + 8 and store it into R0
95 Function calls is a main mechanism to extend functionality of eBPF programs.
99 If a function made accessible to eBPF program, it needs to be thought through
117 register state has a type, which is either NOT_INIT (the register has not been
118 written to), SCALAR_VALUE (some value which is not usable as a pointer), or a
128 			Pointer to the value stored in a map element.
130 			Either a pointer to a map value, or NULL; map accesses
131 			(see maps.rst) return this type, which becomes a
143 			Either a pointer to a socket, or NULL; socket lookup
144 			returns this type, which becomes a PTR_TO_SOCKET when
150 However, a pointer may be offset from this base (as a result of pointer
153 operand) is added to a pointer, while the latter is used for values which are
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;
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
172 branches.  For instance, if a SCALAR_VALUE is compared > 8, in the 'true' branch
173 it will have a umin_value (unsigned minimum value) of 9, whereas in the 'false'
174 branch it will have a umax_value of 8.  A signed compare (with BPF_JSGT or
176 from the signed and unsigned bounds can be combined; for instance if a value is
180 PTR_TO_PACKETs with a variable offset part have an 'id', which is common to all
182 checks: after adding a variable to a packet pointer register A, if you then copy
183 it to another register B and then add a constant 4 to A, both registers will
184 share the same 'id' but the A will have a fixed offset of +4.  Then if A is
185 bounds-checked and found to be less than a PTR_TO_PACKET_END, the register B is
186 now known to have a safe range of at least 4 bytes.  See 'Direct packet access',
190 the pointer returned from a map lookup.  This means that when one copy is
194 is 2 bytes after a 4-byte alignment.  If a program adds 14 bytes to that to jump
196 pointer will have a variable offset known to be 4n+2 for some n, so adding the 2
197 bytes (NET_IP_ALIGN) gives a 4-byte alignment and so word-sized accesses through
200 to all copies of the pointer returned from a socket lookup. This has similar
203 represents a reference to the corresponding ``struct sock``. To ensure that the
217     4:  r5 += 14
219     R1=ctx R3=pkt(id=0,off=0,r=14) R4=pkt_end R5=pkt(id=0,off=14,r=14) R10=fp
223 did check ``if (skb->data + 14 > skb->data_end) goto err`` at insn #5 which
225 has at least 14 directly accessible bytes. The verifier marks it
226 as R3=pkt(id=0,off=0,r=14).
229 r=14 is the range of safe access which means that bytes [R3, R3 + 14) are ok.
230 Note that R5 is marked as R5=pkt(id=0,off=14,r=14). It also points
231 to the packet data, but constant 14 was added to the register, so
232 it now points to ``skb->data + 14`` and accessible range is [R5, R5 + 14 - 14)
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
241     8:  r4 *= 14
247     14:  r3 += r2
252 …(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
257 offset within a packet and since the program author did
272 8 bits. After insn ``r4 *= 14`` the state becomes
274 value by constant 14 will keep upper 52 bits as zero, also the least significant
275 bit will be zero as 14 is even.  Similarly ``r2 >>= 48`` will make
307 been in when at this instruction.  If any of them contain the current state as a
310 previous state, r1 held a packet-pointer, and in the current state, r1 holds a
311 packet-pointer with a range as long or longer and at least as strict an
328 removed from the cached state thus making more states equivalent to a cached
339 Suppose that a state cache entry is created at instruction #4 (such entries are
397   is read by a some child state of this verifier state;
399 * ``REG_LIVE_DONE`` is a marker used by ``clean_verifier_state()`` to avoid
408 In order to propagate information between parent and child states, a *register
409 parentage chain* is established. Each register or stack slot is linked to a
410 corresponding register or stack slot in its parent state via a ``->parent``
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
478                                The checkpoint #1 contains a write mark for r6
487 back along the state parentage chain until they hit a write mark, which 'screens
505   applied to the **current** state. The write mark on a register or stack slot
533 called to update the ``->branches`` counter for each verifier state in a chain
535 verifier state becomes a valid entry in a set of cached verifier states.
537 Each entry of the verifier states cache is post-processed by a function
541 called from ``states_equal()`` when a state cache entry is considered for
542 equivalence with a current state.
565   by ``clean_live_states()``. After this processing ``checkpoint[0].r1`` has a
570   and is compared against a cached state ``{ r1 == 0, pc == 4 }``, the states
578 Another point is the handling of read marks when a previously verified state is
585 Consider the following state parentage chain (S is a starting state, A-E are
589             <-------------                A[r1] == 0
591       S ---> A ---> B ---> exit           E[r1] == 1
602 * Chain of states ``S -> A -> B -> exit`` is verified first.
605   propagated up to state ``A``.
659     0: (7a) *(u64 *)(r10 +8) = 0
689   0: (7a) *(u64 *)(r10 -8) = 0
709   0: (7a) *(u64 *)(r10 -8) = 0
714   5: (7a) *(u64 *)(r0 +0) = 0
731   0: (7a) *(u64 *)(r10 -8) = 0
738   6: (7a) *(u64 *)(r0 +4) = 0
758   0: (7a) *(u64 *)(r10 -8) = 0
765   6: (7a) *(u64 *)(r0 +0) = 0
769   8: (7a) *(u64 *)(r0 +0) = 1
772 Program that performs a socket lookup then sets the pointer to NULL without
800 Program that performs a socket lookup but does not NULL-check the returned