summaryrefslogtreecommitdiffstats
path: root/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
blob: 99e561f18f9b67aa44af233c8941cb1e37776248 (plain)
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
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
// SPDX-License-Identifier: GPL-2.0
#include "bpf_misc.h"
#include "bpf_experimental.h"

struct {
	__uint(type, BPF_MAP_TYPE_ARRAY);
	__uint(max_entries, 8);
	__type(key, __u32);
	__type(value, __u64);
} map SEC(".maps");

struct {
	__uint(type, BPF_MAP_TYPE_USER_RINGBUF);
	__uint(max_entries, 8);
} ringbuf SEC(".maps");

struct vm_area_struct;
struct bpf_map;

struct buf_context {
	char *buf;
};

struct num_context {
	__u64 i;
	__u64 j;
};

__u8 choice_arr[2] = { 0, 1 };

static int unsafe_on_2nd_iter_cb(__u32 idx, struct buf_context *ctx)
{
	if (idx == 0) {
		ctx->buf = (char *)(0xDEAD);
		return 0;
	}

	if (bpf_probe_read_user(ctx->buf, 8, (void *)(0xBADC0FFEE)))
		return 1;

	return 0;
}

SEC("?raw_tp")
__failure __msg("R1 type=scalar expected=fp")
int unsafe_on_2nd_iter(void *unused)
{
	char buf[4];
	struct buf_context loop_ctx = { .buf = buf };

	bpf_loop(100, unsafe_on_2nd_iter_cb, &loop_ctx, 0);
	return 0;
}

static int unsafe_on_zero_iter_cb(__u32 idx, struct num_context *ctx)
{
	ctx->i = 0;
	return 0;
}

SEC("?raw_tp")
__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
int unsafe_on_zero_iter(void *unused)
{
	struct num_context loop_ctx = { .i = 32 };

	bpf_loop(100, unsafe_on_zero_iter_cb, &loop_ctx, 0);
	return choice_arr[loop_ctx.i];
}

static int widening_cb(__u32 idx, struct num_context *ctx)
{
	++ctx->i;
	return 0;
}

SEC("?raw_tp")
__success
int widening(void *unused)
{
	struct num_context loop_ctx = { .i = 0, .j = 1 };

	bpf_loop(100, widening_cb, &loop_ctx, 0);
	/* loop_ctx.j is not changed during callback iteration,
	 * verifier should not apply widening to it.
	 */
	return choice_arr[loop_ctx.j];
}

static int loop_detection_cb(__u32 idx, struct num_context *ctx)
{
	for (;;) {}
	return 0;
}

SEC("?raw_tp")
__failure __msg("infinite loop detected")
int loop_detection(void *unused)
{
	struct num_context loop_ctx = { .i = 0 };

	bpf_loop(100, loop_detection_cb, &loop_ctx, 0);
	return 0;
}

static __always_inline __u64 oob_state_machine(struct num_context *ctx)
{
	switch (ctx->i) {
	case 0:
		ctx->i = 1;
		break;
	case 1:
		ctx->i = 32;
		break;
	}
	return 0;
}

static __u64 for_each_map_elem_cb(struct bpf_map *map, __u32 *key, __u64 *val, void *data)
{
	return oob_state_machine(data);
}

SEC("?raw_tp")
__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
int unsafe_for_each_map_elem(void *unused)
{
	struct num_context loop_ctx = { .i = 0 };

	bpf_for_each_map_elem(&map, for_each_map_elem_cb, &loop_ctx, 0);
	return choice_arr[loop_ctx.i];
}

static __u64 ringbuf_drain_cb(struct bpf_dynptr *dynptr, void *data)
{
	return oob_state_machine(data);
}

SEC("?raw_tp")
__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
int unsafe_ringbuf_drain(void *unused)
{
	struct num_context loop_ctx = { .i = 0 };

	bpf_user_ringbuf_drain(&ringbuf, ringbuf_drain_cb, &loop_ctx, 0);
	return choice_arr[loop_ctx.i];
}

static __u64 find_vma_cb(struct task_struct *task, struct vm_area_struct *vma, void *data)
{
	return oob_state_machine(data);
}

SEC("?raw_tp")
__failure __msg("invalid access to map value, value_size=2 off=32 size=1")
int unsafe_find_vma(void *unused)
{
	struct task_struct *task = bpf_get_current_task_btf();
	struct num_context loop_ctx = { .i = 0 };

	bpf_find_vma(task, 0, find_vma_cb, &loop_ctx, 0);
	return choice_arr[loop_ctx.i];
}

static int iter_limit_cb(__u32 idx, struct num_context *ctx)
{
	ctx->i++;
	return 0;
}

SEC("?raw_tp")
__success
int bpf_loop_iter_limit_ok(void *unused)
{
	struct num_context ctx = { .i = 0 };

	bpf_loop(1, iter_limit_cb, &ctx, 0);
	return choice_arr[ctx.i];
}

SEC("?raw_tp")
__failure __msg("invalid access to map value, value_size=2 off=2 size=1")
int bpf_loop_iter_limit_overflow(void *unused)
{
	struct num_context ctx = { .i = 0 };

	bpf_loop(2, iter_limit_cb, &ctx, 0);
	return choice_arr[ctx.i];
}

static int iter_limit_level2a_cb(__u32 idx, struct num_context *ctx)
{
	ctx->i += 100;
	return 0;
}

static int iter_limit_level2b_cb(__u32 idx, struct num_context *ctx)
{
	ctx->i += 10;
	return 0;
}

static int iter_limit_level1_cb(__u32 idx, struct num_context *ctx)
{
	ctx->i += 1;
	bpf_loop(1, iter_limit_level2a_cb, ctx, 0);
	bpf_loop(1, iter_limit_level2b_cb, ctx, 0);
	return 0;
}

/* Check that path visiting every callback function once had been
 * reached by verifier. Variables 'ctx{1,2}i' below serve as flags,
 * with each decimal digit corresponding to a callback visit marker.
 */
SEC("socket")
__success __retval(111111)
int bpf_loop_iter_limit_nested(void *unused)
{
	struct num_context ctx1 = { .i = 0 };
	struct num_context ctx2 = { .i = 0 };
	__u64 a, b, c;

	bpf_loop(1, iter_limit_level1_cb, &ctx1, 0);
	bpf_loop(1, iter_limit_level1_cb, &ctx2, 0);
	a = ctx1.i;
	b = ctx2.i;
	/* Force 'ctx1.i' and 'ctx2.i' precise. */
	c = choice_arr[(a + b) % 2];
	/* This makes 'c' zero, but neither clang nor verifier know it. */
	c /= 10;
	/* Make sure that verifier does not visit 'impossible' states:
	 * enumerate all possible callback visit masks.
	 */
	if (a != 0 && a != 1 && a != 11 && a != 101 && a != 111 &&
	    b != 0 && b != 1 && b != 11 && b != 101 && b != 111)
		asm volatile ("r0 /= 0;" ::: "r0");
	return 1000 * a + b + c;
}

struct iter_limit_bug_ctx {
	__u64 a;
	__u64 b;
	__u64 c;
};

static __naked void iter_limit_bug_cb(void)
{
	/* This is the same as C code below, but written
	 * in assembly to control which branches are fall-through.
	 *
	 *   switch (bpf_get_prandom_u32()) {
	 *   case 1:  ctx->a = 42; break;
	 *   case 2:  ctx->b = 42; break;
	 *   default: ctx->c = 42; break;
	 *   }
	 */
	asm volatile (
	"r9 = r2;"
	"call %[bpf_get_prandom_u32];"
	"r1 = r0;"
	"r2 = 42;"
	"r0 = 0;"
	"if r1 == 0x1 goto 1f;"
	"if r1 == 0x2 goto 2f;"
	"*(u64 *)(r9 + 16) = r2;"
	"exit;"
	"1: *(u64 *)(r9 + 0) = r2;"
	"exit;"
	"2: *(u64 *)(r9 + 8) = r2;"
	"exit;"
	:
	: __imm(bpf_get_prandom_u32)
	: __clobber_all
	);
}

SEC("tc")
__failure
__flag(BPF_F_TEST_STATE_FREQ)
int iter_limit_bug(struct __sk_buff *skb)
{
	struct iter_limit_bug_ctx ctx = { 7, 7, 7 };

	bpf_loop(2, iter_limit_bug_cb, &ctx, 0);

	/* This is the same as C code below,
	 * written in assembly to guarantee checks order.
	 *
	 *   if (ctx.a == 42 && ctx.b == 42 && ctx.c == 7)
	 *     asm volatile("r1 /= 0;":::"r1");
	 */
	asm volatile (
	"r1 = *(u64 *)%[ctx_a];"
	"if r1 != 42 goto 1f;"
	"r1 = *(u64 *)%[ctx_b];"
	"if r1 != 42 goto 1f;"
	"r1 = *(u64 *)%[ctx_c];"
	"if r1 != 7 goto 1f;"
	"r1 /= 0;"
	"1:"
	:
	: [ctx_a]"m"(ctx.a),
	  [ctx_b]"m"(ctx.b),
	  [ctx_c]"m"(ctx.c)
	: "r1"
	);
	return 0;
}

#define ARR_SZ 1000000
int zero;
char arr[ARR_SZ];

SEC("socket")
__success __retval(0xd495cdc0)
int cond_break1(const void *ctx)
{
	unsigned long i;
	unsigned int sum = 0;

	for (i = zero; i < ARR_SZ; cond_break, i++)
		sum += i;
	for (i = zero; i < ARR_SZ; i++) {
		barrier_var(i);
		sum += i + arr[i];
		cond_break;
	}

	return sum;
}

SEC("socket")
__success __retval(999000000)
int cond_break2(const void *ctx)
{
	int i, j;
	int sum = 0;

	for (i = zero; i < 1000; cond_break, i++)
		for (j = zero; j < 1000; j++) {
			sum += i + j;
			cond_break;
		}

	return sum;
}

static __noinline int loop(void)
{
	int i, sum = 0;

	for (i = zero; i <= 1000000; i++, cond_break)
		sum += i;

	return sum;
}

SEC("socket")
__success __retval(0x6a5a2920)
int cond_break3(const void *ctx)
{
	return loop();
}

SEC("socket")
__success __retval(1)
int cond_break4(const void *ctx)
{
	int cnt = zero;

	for (;;) {
		/* should eventually break out of the loop */
		cond_break;
		cnt++;
	}
	/* if we looped a bit, it's a success */
	return cnt > 1 ? 1 : 0;
}

static __noinline int static_subprog(void)
{
	int cnt = zero;

	for (;;) {
		cond_break;
		cnt++;
	}

	return cnt;
}

SEC("socket")
__success __retval(1)
int cond_break5(const void *ctx)
{
	int cnt1 = zero, cnt2;

	for (;;) {
		cond_break;
		cnt1++;
	}

	cnt2 = static_subprog();

	/* main and subprog have to loop a bit */
	return cnt1 > 1 && cnt2 > 1 ? 1 : 0;
}

char _license[] SEC("license") = "GPL";