1 // SPDX-License-Identifier: GPL-2.0
2 /* Converted from tools/testing/selftests/bpf/verifier/loops1.c */
3
4 #include <linux/bpf.h>
5 #include <bpf/bpf_helpers.h>
6 #include "bpf_misc.h"
7
8 SEC("xdp")
9 __description("bounded loop, count to 4")
10 __success __retval(4)
bounded_loop_count_to_4(void)11 __naked void bounded_loop_count_to_4(void)
12 {
13 asm volatile (" \
14 r0 = 0; \
15 l0_%=: r0 += 1; \
16 if r0 < 4 goto l0_%=; \
17 exit; \
18 " ::: __clobber_all);
19 }
20
21 SEC("tracepoint")
22 __description("bounded loop, count to 20")
23 __success
bounded_loop_count_to_20(void)24 __naked void bounded_loop_count_to_20(void)
25 {
26 asm volatile (" \
27 r0 = 0; \
28 l0_%=: r0 += 3; \
29 if r0 < 20 goto l0_%=; \
30 exit; \
31 " ::: __clobber_all);
32 }
33
34 SEC("tracepoint")
35 __description("bounded loop, count from positive unknown to 4")
36 __success
from_positive_unknown_to_4(void)37 __naked void from_positive_unknown_to_4(void)
38 {
39 asm volatile (" \
40 call %[bpf_get_prandom_u32]; \
41 if r0 s< 0 goto l0_%=; \
42 l1_%=: r0 += 1; \
43 if r0 < 4 goto l1_%=; \
44 l0_%=: exit; \
45 " :
46 : __imm(bpf_get_prandom_u32)
47 : __clobber_all);
48 }
49
50 SEC("tracepoint")
51 __description("bounded loop, count from totally unknown to 4")
52 __success
from_totally_unknown_to_4(void)53 __naked void from_totally_unknown_to_4(void)
54 {
55 asm volatile (" \
56 call %[bpf_get_prandom_u32]; \
57 l0_%=: r0 += 1; \
58 if r0 < 4 goto l0_%=; \
59 exit; \
60 " :
61 : __imm(bpf_get_prandom_u32)
62 : __clobber_all);
63 }
64
65 SEC("tracepoint")
66 __description("bounded loop, count to 4 with equality")
67 __success
count_to_4_with_equality(void)68 __naked void count_to_4_with_equality(void)
69 {
70 asm volatile (" \
71 r0 = 0; \
72 l0_%=: r0 += 1; \
73 if r0 != 4 goto l0_%=; \
74 exit; \
75 " ::: __clobber_all);
76 }
77
78 SEC("socket")
79 __description("bounded loop, start in the middle")
80 __success
81 __failure_unpriv __msg_unpriv("back-edge")
loop_start_in_the_middle(void)82 __naked void loop_start_in_the_middle(void)
83 {
84 asm volatile (" \
85 r0 = 0; \
86 goto l0_%=; \
87 l1_%=: r0 += 1; \
88 l0_%=: if r0 < 4 goto l1_%=; \
89 exit; \
90 " ::: __clobber_all);
91 }
92
93 SEC("xdp")
94 __description("bounded loop containing a forward jump")
95 __success __retval(4)
loop_containing_a_forward_jump(void)96 __naked void loop_containing_a_forward_jump(void)
97 {
98 asm volatile (" \
99 r0 = 0; \
100 l1_%=: r0 += 1; \
101 if r0 == r0 goto l0_%=; \
102 l0_%=: if r0 < 4 goto l1_%=; \
103 exit; \
104 " ::: __clobber_all);
105 }
106
107 SEC("tracepoint")
108 __description("bounded loop that jumps out rather than in")
109 __success
jumps_out_rather_than_in(void)110 __naked void jumps_out_rather_than_in(void)
111 {
112 asm volatile (" \
113 r6 = 0; \
114 l1_%=: r6 += 1; \
115 if r6 > 10000 goto l0_%=; \
116 call %[bpf_get_prandom_u32]; \
117 goto l1_%=; \
118 l0_%=: exit; \
119 " :
120 : __imm(bpf_get_prandom_u32)
121 : __clobber_all);
122 }
123
124 SEC("tracepoint")
125 __description("infinite loop after a conditional jump")
126 __failure __msg("program is too large")
loop_after_a_conditional_jump(void)127 __naked void loop_after_a_conditional_jump(void)
128 {
129 asm volatile (" \
130 r0 = 5; \
131 if r0 < 4 goto l0_%=; \
132 l1_%=: r0 += 1; \
133 goto l1_%=; \
134 l0_%=: exit; \
135 " ::: __clobber_all);
136 }
137
138 SEC("tracepoint")
139 __description("bounded recursion")
140 __failure
141 __msg("recursive call from")
bounded_recursion(void)142 __naked void bounded_recursion(void)
143 {
144 asm volatile (" \
145 r1 = 0; \
146 call bounded_recursion__1; \
147 exit; \
148 " ::: __clobber_all);
149 }
150
151 static __naked __noinline __attribute__((used))
bounded_recursion__1(void)152 void bounded_recursion__1(void)
153 {
154 asm volatile (" \
155 r1 += 1; \
156 r0 = r1; \
157 if r1 < 4 goto l0_%=; \
158 exit; \
159 l0_%=: call bounded_recursion__1; \
160 exit; \
161 " ::: __clobber_all);
162 }
163
164 SEC("tracepoint")
165 __description("infinite loop in two jumps")
166 __failure __msg("loop detected")
infinite_loop_in_two_jumps(void)167 __naked void infinite_loop_in_two_jumps(void)
168 {
169 asm volatile (" \
170 r0 = 0; \
171 l1_%=: goto l0_%=; \
172 l0_%=: if r0 < 4 goto l1_%=; \
173 exit; \
174 " ::: __clobber_all);
175 }
176
177 SEC("tracepoint")
178 __description("infinite loop: three-jump trick")
179 __failure __msg("loop detected")
infinite_loop_three_jump_trick(void)180 __naked void infinite_loop_three_jump_trick(void)
181 {
182 asm volatile (" \
183 r0 = 0; \
184 l2_%=: r0 += 1; \
185 r0 &= 1; \
186 if r0 < 2 goto l0_%=; \
187 exit; \
188 l0_%=: r0 += 1; \
189 r0 &= 1; \
190 if r0 < 2 goto l1_%=; \
191 exit; \
192 l1_%=: r0 += 1; \
193 r0 &= 1; \
194 if r0 < 2 goto l2_%=; \
195 exit; \
196 " ::: __clobber_all);
197 }
198
199 SEC("xdp")
200 __description("not-taken loop with back jump to 1st insn")
201 __success __retval(123)
back_jump_to_1st_insn_1(void)202 __naked void back_jump_to_1st_insn_1(void)
203 {
204 asm volatile (" \
205 l0_%=: r0 = 123; \
206 if r0 == 4 goto l0_%=; \
207 exit; \
208 " ::: __clobber_all);
209 }
210
211 SEC("xdp")
212 __description("taken loop with back jump to 1st insn")
213 __success __retval(55)
back_jump_to_1st_insn_2(void)214 __naked void back_jump_to_1st_insn_2(void)
215 {
216 asm volatile (" \
217 r1 = 10; \
218 r2 = 0; \
219 call back_jump_to_1st_insn_2__1; \
220 exit; \
221 " ::: __clobber_all);
222 }
223
224 static __naked __noinline __attribute__((used))
back_jump_to_1st_insn_2__1(void)225 void back_jump_to_1st_insn_2__1(void)
226 {
227 asm volatile (" \
228 l0_%=: r2 += r1; \
229 r1 -= 1; \
230 if r1 != 0 goto l0_%=; \
231 r0 = r2; \
232 exit; \
233 " ::: __clobber_all);
234 }
235
236 SEC("xdp")
237 __description("taken loop with back jump to 1st insn, 2")
238 __success __retval(55)
jump_to_1st_insn_2(void)239 __naked void jump_to_1st_insn_2(void)
240 {
241 asm volatile (" \
242 r1 = 10; \
243 r2 = 0; \
244 call jump_to_1st_insn_2__1; \
245 exit; \
246 " ::: __clobber_all);
247 }
248
249 static __naked __noinline __attribute__((used))
jump_to_1st_insn_2__1(void)250 void jump_to_1st_insn_2__1(void)
251 {
252 asm volatile (" \
253 l0_%=: r2 += r1; \
254 r1 -= 1; \
255 if w1 != 0 goto l0_%=; \
256 r0 = r2; \
257 exit; \
258 " ::: __clobber_all);
259 }
260
261 SEC("xdp")
262 __success
not_an_inifinite_loop(void)263 __naked void not_an_inifinite_loop(void)
264 {
265 asm volatile (" \
266 call %[bpf_get_prandom_u32]; \
267 r0 &= 0xff; \
268 *(u64 *)(r10 - 8) = r0; \
269 r0 = 0; \
270 loop_%=: \
271 r0 = *(u64 *)(r10 - 8); \
272 if r0 > 10 goto exit_%=; \
273 r0 += 1; \
274 *(u64 *)(r10 - 8) = r0; \
275 r0 = 0; \
276 goto loop_%=; \
277 exit_%=: \
278 r0 = 0; \
279 exit; \
280 " :
281 : __imm(bpf_get_prandom_u32)
282 : __clobber_all);
283 }
284
285 /*
286 * This test case triggered a bug in verifier.c:maybe_exit_scc().
287 * Speculative execution path reaches stack access instruction,
288 * stops and triggers maybe_exit_scc() w/o accompanying maybe_enter_scc() call.
289 */
290 SEC("socket")
291 __arch_x86_64
__caps_unpriv(CAP_BPF)292 __caps_unpriv(CAP_BPF)
293 __naked void maybe_exit_scc_bug1(void)
294 {
295 asm volatile (
296 "r0 = 100;"
297 "1:"
298 /* Speculative execution path reaches and stops here. */
299 "*(u64 *)(r10 - 512) = r0;"
300 /* Condition is always false, but verifier speculatively executes the true branch. */
301 "if r0 <= 0x0 goto 1b;"
302 "exit;"
303 ::: __clobber_all);
304 }
305
306 /*
307 * The loop reads zero from the caller's stack on its first iteration and
308 * one from the callee's stack on its second iteration. At the loop header,
309 * only the frame number of the pointer in r1 changes.
310 */
311 static __naked __noinline __used
loop_stack_frames_reg(void)312 void loop_stack_frames_reg(void)
313 {
314 asm volatile (
315 "*(u64 *)(r10 - 8) = 1;"
316 "1:"
317 "r0 = *(u64 *)(r1 + 0);"
318 "if r0 != 0 goto 2f;"
319 "r1 = r10;"
320 "r1 += -8;"
321 "goto 1b;"
322 "2:"
323 "exit;"
324 ::: __clobber_all);
325 }
326
327 SEC("xdp")
328 __description("bounded loop changing stack frame in a register")
329 __success __retval(1)
__flag(BPF_F_TEST_STATE_FREQ)330 __flag(BPF_F_TEST_STATE_FREQ)
331 __naked void bounded_loop_stack_frames_reg(void)
332 {
333 asm volatile (
334 "*(u64 *)(r10 - 8) = 0;"
335 "r1 = r10;"
336 "r1 += -8;"
337 "call loop_stack_frames_reg;"
338 "exit;"
339 ::: __clobber_all);
340 }
341
342 char _license[] SEC("license") = "GPL";
343