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
8SEC("xdp")
9__description("bounded loop, count to 4")
10__success __retval(4)
11__naked void bounded_loop_count_to_4(void)
12{
13	asm volatile ("					\
14	r0 = 0;						\
15l0_%=:	r0 += 1;					\
16	if r0 < 4 goto l0_%=;				\
17	exit;						\
18"	::: __clobber_all);
19}
20
21SEC("tracepoint")
22__description("bounded loop, count to 20")
23__success
24__naked void bounded_loop_count_to_20(void)
25{
26	asm volatile ("					\
27	r0 = 0;						\
28l0_%=:	r0 += 3;					\
29	if r0 < 20 goto l0_%=;				\
30	exit;						\
31"	::: __clobber_all);
32}
33
34SEC("tracepoint")
35__description("bounded loop, count from positive unknown to 4")
36__success
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_%=;				\
42l1_%=:	r0 += 1;					\
43	if r0 < 4 goto l1_%=;				\
44l0_%=:	exit;						\
45"	:
46	: __imm(bpf_get_prandom_u32)
47	: __clobber_all);
48}
49
50SEC("tracepoint")
51__description("bounded loop, count from totally unknown to 4")
52__success
53__naked void from_totally_unknown_to_4(void)
54{
55	asm volatile ("					\
56	call %[bpf_get_prandom_u32];			\
57l0_%=:	r0 += 1;					\
58	if r0 < 4 goto l0_%=;				\
59	exit;						\
60"	:
61	: __imm(bpf_get_prandom_u32)
62	: __clobber_all);
63}
64
65SEC("tracepoint")
66__description("bounded loop, count to 4 with equality")
67__success
68__naked void count_to_4_with_equality(void)
69{
70	asm volatile ("					\
71	r0 = 0;						\
72l0_%=:	r0 += 1;					\
73	if r0 != 4 goto l0_%=;				\
74	exit;						\
75"	::: __clobber_all);
76}
77
78SEC("socket")
79__description("bounded loop, start in the middle")
80__success
81__failure_unpriv __msg_unpriv("back-edge")
82__naked void loop_start_in_the_middle(void)
83{
84	asm volatile ("					\
85	r0 = 0;						\
86	goto l0_%=;					\
87l1_%=:	r0 += 1;					\
88l0_%=:	if r0 < 4 goto l1_%=;				\
89	exit;						\
90"	::: __clobber_all);
91}
92
93SEC("xdp")
94__description("bounded loop containing a forward jump")
95__success __retval(4)
96__naked void loop_containing_a_forward_jump(void)
97{
98	asm volatile ("					\
99	r0 = 0;						\
100l1_%=:	r0 += 1;					\
101	if r0 == r0 goto l0_%=;				\
102l0_%=:	if r0 < 4 goto l1_%=;				\
103	exit;						\
104"	::: __clobber_all);
105}
106
107SEC("tracepoint")
108__description("bounded loop that jumps out rather than in")
109__success
110__naked void jumps_out_rather_than_in(void)
111{
112	asm volatile ("					\
113	r6 = 0;						\
114l1_%=:	r6 += 1;					\
115	if r6 > 10000 goto l0_%=;			\
116	call %[bpf_get_prandom_u32];			\
117	goto l1_%=;					\
118l0_%=:	exit;						\
119"	:
120	: __imm(bpf_get_prandom_u32)
121	: __clobber_all);
122}
123
124SEC("tracepoint")
125__description("infinite loop after a conditional jump")
126__failure __msg("program is too large")
127__naked void loop_after_a_conditional_jump(void)
128{
129	asm volatile ("					\
130	r0 = 5;						\
131	if r0 < 4 goto l0_%=;				\
132l1_%=:	r0 += 1;					\
133	goto l1_%=;					\
134l0_%=:	exit;						\
135"	::: __clobber_all);
136}
137
138SEC("tracepoint")
139__description("bounded recursion")
140__failure
141/* verifier limitation in detecting max stack depth */
142__msg("the call stack of 8 frames is too deep !")
143__naked void bounded_recursion(void)
144{
145	asm volatile ("					\
146	r1 = 0;						\
147	call bounded_recursion__1;			\
148	exit;						\
149"	::: __clobber_all);
150}
151
152static __naked __noinline __attribute__((used))
153void bounded_recursion__1(void)
154{
155	asm volatile ("					\
156	r1 += 1;					\
157	r0 = r1;					\
158	if r1 < 4 goto l0_%=;				\
159	exit;						\
160l0_%=:	call bounded_recursion__1;			\
161	exit;						\
162"	::: __clobber_all);
163}
164
165SEC("tracepoint")
166__description("infinite loop in two jumps")
167__failure __msg("loop detected")
168__naked void infinite_loop_in_two_jumps(void)
169{
170	asm volatile ("					\
171	r0 = 0;						\
172l1_%=:	goto l0_%=;					\
173l0_%=:	if r0 < 4 goto l1_%=;				\
174	exit;						\
175"	::: __clobber_all);
176}
177
178SEC("tracepoint")
179__description("infinite loop: three-jump trick")
180__failure __msg("loop detected")
181__naked void infinite_loop_three_jump_trick(void)
182{
183	asm volatile ("					\
184	r0 = 0;						\
185l2_%=:	r0 += 1;					\
186	r0 &= 1;					\
187	if r0 < 2 goto l0_%=;				\
188	exit;						\
189l0_%=:	r0 += 1;					\
190	r0 &= 1;					\
191	if r0 < 2 goto l1_%=;				\
192	exit;						\
193l1_%=:	r0 += 1;					\
194	r0 &= 1;					\
195	if r0 < 2 goto l2_%=;				\
196	exit;						\
197"	::: __clobber_all);
198}
199
200SEC("xdp")
201__description("not-taken loop with back jump to 1st insn")
202__success __retval(123)
203__naked void back_jump_to_1st_insn_1(void)
204{
205	asm volatile ("					\
206l0_%=:	r0 = 123;					\
207	if r0 == 4 goto l0_%=;				\
208	exit;						\
209"	::: __clobber_all);
210}
211
212SEC("xdp")
213__description("taken loop with back jump to 1st insn")
214__success __retval(55)
215__naked void back_jump_to_1st_insn_2(void)
216{
217	asm volatile ("					\
218	r1 = 10;					\
219	r2 = 0;						\
220	call back_jump_to_1st_insn_2__1;		\
221	exit;						\
222"	::: __clobber_all);
223}
224
225static __naked __noinline __attribute__((used))
226void back_jump_to_1st_insn_2__1(void)
227{
228	asm volatile ("					\
229l0_%=:	r2 += r1;					\
230	r1 -= 1;					\
231	if r1 != 0 goto l0_%=;				\
232	r0 = r2;					\
233	exit;						\
234"	::: __clobber_all);
235}
236
237SEC("xdp")
238__description("taken loop with back jump to 1st insn, 2")
239__success __retval(55)
240__naked void jump_to_1st_insn_2(void)
241{
242	asm volatile ("					\
243	r1 = 10;					\
244	r2 = 0;						\
245	call jump_to_1st_insn_2__1;			\
246	exit;						\
247"	::: __clobber_all);
248}
249
250static __naked __noinline __attribute__((used))
251void jump_to_1st_insn_2__1(void)
252{
253	asm volatile ("					\
254l0_%=:	r2 += r1;					\
255	r1 -= 1;					\
256	if w1 != 0 goto l0_%=;				\
257	r0 = r2;					\
258	exit;						\
259"	::: __clobber_all);
260}
261
262SEC("xdp")
263__success
264__naked void not_an_inifinite_loop(void)
265{
266	asm volatile ("					\
267	call %[bpf_get_prandom_u32];			\
268	r0 &= 0xff;					\
269	*(u64 *)(r10 - 8) = r0;				\
270	r0 = 0;						\
271loop_%=:						\
272	r0 = *(u64 *)(r10 - 8);				\
273	if r0 > 10 goto exit_%=;			\
274	r0 += 1;					\
275	*(u64 *)(r10 - 8) = r0;				\
276	r0 = 0;						\
277	goto loop_%=;					\
278exit_%=:						\
279	r0 = 0;						\
280	exit;						\
281"	:
282	: __imm(bpf_get_prandom_u32)
283	: __clobber_all);
284}
285
286char _license[] SEC("license") = "GPL";
287