1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
|
// SPDX-License-Identifier: GPL-2.0
/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
#include <linux/bpf.h>
#include <bpf/bpf_helpers.h>
#include "bpf_misc.h"
/*
* kernel/bpf/loops.c:compute_loops_in_subprog() distinguishes between
* the following cases:
* - B: backedge -> simple loop
* - C: cross edge to non-loop node -> no-op
* - D: edge to node whose header is in DFS path -> nested loop
* - E: edge to node whose header is NOT in DFS path -> irreducible
*
* Below test cases cover the above branches in various combinations.
*/
/* Case B: single bounded loop. */
SEC("socket")
__success
__log_level(2)
__msg("loop at 1{{$}}")
__msg("Program dump")
__msg(" -1 0: {{.*}} (b7) r0 = 0")
__msg(" 1 0 1: {{.*}} (07) r0 += 1")
__msg(" 1 1 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2")
__msg(" 2 3: {{.*}} (95) exit")
__naked void loop_single(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
if r0 < 10 goto 1b; \
exit; \
" ::: __clobber_all);
}
/* Case B: two independent loops at the same nesting level. */
SEC("socket")
__success
__log_level(2)
__msg("loop at 1{{$}}")
__msg("loop at 4{{$}}")
__msg("Program dump")
__msg(" -1 0: {{.*}} (b7) r0 = 0")
__msg(" 2 0 1: {{.*}} (07) r0 += 1")
__msg(" 2 1 1 2: {{.*}} (a5) if r0 < 0xa goto pc-2")
__msg(" 2 3: {{.*}} (b7) r1 = 0")
__msg(" 1 3 4: {{.*}} (07) r1 += 1")
__msg(" 1 4 4 5: {{.*}} (a5) if r1 < 0xa goto pc-2")
__msg(" 5 6: {{.*}} (95) exit")
__naked void loop_two_independent(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
if r0 < 10 goto 1b; \
r1 = 0; \
2: r1 += 1; \
if r1 < 10 goto 2b; \
exit; \
" ::: __clobber_all);
}
/* Case B + D: nested loops. */
SEC("socket")
__success
__log_level(2)
__msg("loop at 1{{$}}")
__msg("loop at 3, nested in 1")
__msg("Program dump")
__msg(" -1 0: {{.*}} (b7) r0 = 0")
__msg(" 1 0 1: {{.*}} (07) r0 += 1") /* outer loop header */
__msg(" 1 1 1 2: {{.*}} (b7) r1 = 0") /* outer loop insn */
__msg(" 1 1 2 3: {{.*}} (07) r1 += 1") /* inner loop header */
__msg(" 1 3 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2") /* inner loop insn */
__msg(" 1 1 4 5: {{.*}} (a5) if r0 < 0xa goto pc-5") /* outer loop insn */
__msg(" 5 6: {{.*}} (95) exit")
__naked void loop_nested(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
r1 = 0; \
2: r1 += 1; \
if r1 < 5 goto 2b; \
if r0 < 10 goto 1b; \
exit; \
" ::: __clobber_all);
}
/* Case C: forward edges, no loops. */
SEC("socket")
__success
__log_level(2)
__msg("Program dump")
__msg(" -1 0: {{.*}} (85) call bpf_get_prandom_u32")
__msg(" 0 1: {{.*}} (25) if r0 > 0x0 goto pc+2")
__msg(" 1 2: {{.*}} (b7) r0 = 2")
__msg(" 2 3: {{.*}} (05) goto pc+1")
__msg(" 1 4: {{.*}} (b7) r0 = 3")
__msg(" 1 5: {{.*}} (95) exit")
__naked void fwd_edges_no_loop(void)
{
asm volatile (" \
call %[bpf_get_prandom_u32]; \
if r0 > 0 goto 1f; \
r0 = 2; \
goto 2f; \
1: r0 = 3; \
2: exit; \
" :
: __imm(bpf_get_prandom_u32)
: __clobber_all);
}
/* Case B + D: two sibling inner loops within one outer loop. */
SEC("socket")
__success
__log_level(2)
__msg("loop at 1{{$}}")
__msg("loop at 3, nested in 1")
__msg("loop at 6, nested in 1")
__msg("Program dump")
__msg(" -1 0: {{.*}} (b7) r0 = 0")
__msg(" 1 0 1: {{.*}} (07) r0 += 1")
__msg(" 1 1 1 2: {{.*}} (b7) r1 = 0")
__msg(" 1 1 2 3: {{.*}} (07) r1 += 1")
__msg(" 1 3 3 4: {{.*}} (a5) if r1 < 0x5 goto pc-2")
__msg(" 1 1 4 5: {{.*}} (b7) r2 = 0")
__msg(" 1 1 5 6: {{.*}} (07) r2 += 1")
__msg(" 1 6 6 7: {{.*}} (a5) if r2 < 0x5 goto pc-2")
__msg(" 1 1 7 8: {{.*}} (a5) if r0 < 0xa goto pc-8")
__msg(" 8 9: {{.*}} (95) exit")
__naked void loop_nested_siblings(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
r1 = 0; \
2: r1 += 1; \
if r1 < 5 goto 2b; \
r2 = 0; \
3: r2 += 1; \
if r2 < 5 goto 3b; \
if r0 < 10 goto 1b; \
exit; \
" ::: __clobber_all);
}
/* Three levels of nesting. */
SEC("socket")
__success
__log_level(2)
__msg("loop at 1{{$}}")
__msg("loop at 3, nested in 1")
__msg("loop at 5, nested in 3")
__msg("Program dump")
__msg(" -1 0: {{.*}} (b7) r0 = 0")
__msg(" 1 0 1: {{.*}} (07) r0 += 1")
__msg(" 1 1 1 2: {{.*}} (b7) r1 = 0")
__msg(" 1 1 2 3: {{.*}} (07) r1 += 1")
__msg(" 1 3 3 4: {{.*}} (b7) r2 = 0")
__msg(" 1 3 4 5: {{.*}} (07) r2 += 1")
__msg(" 1 5 5 6: {{.*}} (a5) if r2 < 0x3 goto pc-2")
__msg(" 1 3 6 7: {{.*}} (a5) if r1 < 0x5 goto pc-5")
__msg(" 1 1 7 8: {{.*}} (a5) if r0 < 0xa goto pc-8")
__msg(" 8 9: {{.*}} (95) exit")
__naked void loop_three_levels(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
r1 = 0; \
2: r1 += 1; \
r2 = 0; \
3: r2 += 1; \
if r2 < 3 goto 3b; \
if r1 < 5 goto 2b; \
if r0 < 10 goto 1b; \
exit; \
" ::: __clobber_all);
}
/* Loop with an if-else body (forward branch inside loop, Case D). */
SEC("socket")
__success
__log_level(2)
__msg("loop at 1")
__msg("Program dump")
__msg(" -1 0: {{.*}} (b7) r0 = 0")
__msg(" 1 0 1: {{.*}} (07) r0 += 1")
__msg(" 1 1 1 2: {{.*}} (bf) r1 = r0")
__msg(" 1 1 2 3: {{.*}} (25) if r1 > 0x5 goto pc+1")
__msg(" 1 1 3 4: {{.*}} (b7) r1 = 1")
__msg(" 1 1 3 5: {{.*}} (0f) r0 += r1")
__msg(" 1 1 5 6: {{.*}} (a5) if r0 < 0x64 goto pc-6")
__msg(" 6 7: {{.*}} (95) exit")
__naked void loop_with_if_else(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
r1 = r0; \
if r1 > 5 goto 2f; \
r1 = 1; \
2: r0 += r1; \
if r0 < 100 goto 1b; \
exit; \
" ::: __clobber_all);
}
/* Case E: irreducible loop. */
SEC("socket")
__success
__log_level(2)
__msg("loop at 3, irreducible")
__msg("Program dump")
__msg(" -1 0: {{.*}} (85) call bpf_get_prandom_u32#7")
__msg(" 0 1: {{.*}} (b7) r1 = 0")
__msg(" 1 2: {{.*}} (25) if r0 > 0x5 goto pc+2")
__msg(" 1 2 3: {{.*}} (b7) r1 = 1")
__msg(" 1 3 3 4: {{.*}} (05) goto pc+1")
__msg(" 2 5: {{.*}} (b7) r1 = 2")
__msg(" 1 3 2 6: {{.*}} (0f) r0 += r1")
__msg(" 1 3 6 7: {{.*}} (a5) if r0 < 0x10 goto pc-5")
__msg(" 7 8: {{.*}} (95) exit")
__naked void loop_irreducible(void)
{
asm volatile (" \
call %[bpf_get_prandom_u32]; \
r1 = 0; \
if r0 > 5 goto 2f; \
1: r1 = 1; \
goto 3f; \
2: r1 = 2; \
3: r0 += r1; \
if r0 < 16 goto 1b; \
exit; \
" :
: __imm(bpf_get_prandom_u32)
: __clobber_all);
}
SEC("socket")
__failure
__log_level(2)
__msg("loop at 1")
__msg("infinite loop detected at insn 1")
__naked void loop_self(void)
{
asm volatile (" \
call %[bpf_get_prandom_u32]; \
1: if r0 < 10 goto 1b; \
exit; \
" :
: __imm(bpf_get_prandom_u32)
: __clobber_all);
}
/*
* Loops at 5 and 7 are nested inside loops at 3 and 1.
* The edge 6 -> 7 exits loop at 5 and enters loop at 7.
* Check that it is logged only as an exit from loop at 5.
*
* 0: r0 = 0;
* do {
* 1: r0++;
* 2: r1 = 0;
* do {
* 3: r1++;
* 4: r2 = 0;
* do {
* 5: r2++;
* 6: } while (r2 < 3);
* do {
* 7: r2--;
* 8: } while (r2 != 0);
* 9: } while (r1 < 4);
* 10: } while (r0 < 5);
* 11: return r0;
*/
SEC("socket")
__success
__log_level(2)
__msg("loop at 1{{$}}")
__msg_next(" backedge from 10, latch at 10")
__msg_next(" exit from 10 to 11")
__msg_next("loop at 3, nested in 1")
__msg_next(" backedge from 9, latch at 9")
__msg_next(" exit from 9 to 10")
__msg_next("loop at 5, nested in 3")
__msg_next(" backedge from 6, latch at 6")
__msg_next(" exit from 6 to 7")
__msg_next("loop at 7, nested in 3")
__msg_next(" backedge from 8, latch at 8")
__msg_next(" exit from 8 to 9")
__naked void loop_nested_siblings_common_ancestors(void)
{
asm volatile (" \
r0 = 0; \
1: r0 += 1; \
r1 = 0; \
2: r1 += 1; \
r2 = 0; \
3: r2 += 1; \
if r2 < 3 goto 3b; \
4: r2 += -1; \
if r2 != 0 goto 4b; \
if r1 < 4 goto 2b; \
if r0 < 5 goto 1b; \
exit; \
" ::: __clobber_all);
}
/*
* The outer loop backedge (4 -> 2) originates in an inner loop.
* For now, latch should not be identified in such cases.
*/
SEC("socket")
__success
__log_level(2)
__msg("loop at 2{{$}}")
__msg_next(" backedge from 4{{$}}")
__msg_next(" exit from 5 to 7")
__msg_next("loop at 3, nested in 2")
__msg_next(" backedge from 6, latch at 5")
__msg_next(" exit from 4 to 2")
__msg_next(" exit from 5 to 7")
__naked void loop_outer_backedge_from_inner(void)
{
asm volatile (" \
r6 = 99; \
r2 = 2; \
2: r6 += 1; /* loop at 2 */ \
3: r2 += 1; /* loop at 3 */ \
4: if r2 == 3 goto 2b; \
5: if r6 > 100 goto 7f; \
goto 3b; \
7: r0 = 0; \
exit; \
" ::: __clobber_all);
}
char _license[] SEC("license") = "GPL";
|
