1
2
3
4
5
6
7
8
9
10
11
12#include <linux/kernel.h>
13#include <linux/types.h>
14#include <linux/slab.h>
15#include <linux/bpf.h>
16#include <linux/filter.h>
17#include <net/netlink.h>
18#include <linux/file.h>
19#include <linux/vmalloc.h>
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
129enum bpf_reg_type {
130 NOT_INIT = 0,
131 UNKNOWN_VALUE,
132 PTR_TO_CTX,
133 CONST_PTR_TO_MAP,
134 PTR_TO_MAP_VALUE,
135 PTR_TO_MAP_VALUE_OR_NULL,
136 FRAME_PTR,
137 PTR_TO_STACK,
138 CONST_IMM,
139};
140
141struct reg_state {
142 enum bpf_reg_type type;
143 union {
144
145 int imm;
146
147
148
149
150 struct bpf_map *map_ptr;
151 };
152};
153
154enum bpf_stack_slot_type {
155 STACK_INVALID,
156 STACK_SPILL,
157 STACK_MISC
158};
159
160#define BPF_REG_SIZE 8
161
162
163
164
165struct verifier_state {
166 struct reg_state regs[MAX_BPF_REG];
167 u8 stack_slot_type[MAX_BPF_STACK];
168 struct reg_state spilled_regs[MAX_BPF_STACK / BPF_REG_SIZE];
169};
170
171
172struct verifier_state_list {
173 struct verifier_state state;
174 struct verifier_state_list *next;
175};
176
177
178struct verifier_stack_elem {
179
180
181
182
183 struct verifier_state st;
184 int insn_idx;
185 int prev_insn_idx;
186 struct verifier_stack_elem *next;
187};
188
189#define MAX_USED_MAPS 64
190
191
192
193
194struct verifier_env {
195 struct bpf_prog *prog;
196 struct verifier_stack_elem *head;
197 int stack_size;
198 struct verifier_state cur_state;
199 struct verifier_state_list **explored_states;
200 struct bpf_map *used_maps[MAX_USED_MAPS];
201 u32 used_map_cnt;
202 bool allow_ptr_leaks;
203};
204
205
206
207
208static u32 log_level, log_size, log_len;
209static char *log_buf;
210
211static DEFINE_MUTEX(bpf_verifier_lock);
212
213
214
215
216
217static __printf(1, 2) void verbose(const char *fmt, ...)
218{
219 va_list args;
220
221 if (log_level == 0 || log_len >= log_size - 1)
222 return;
223
224 va_start(args, fmt);
225 log_len += vscnprintf(log_buf + log_len, log_size - log_len, fmt, args);
226 va_end(args);
227}
228
229
230static const char * const reg_type_str[] = {
231 [NOT_INIT] = "?",
232 [UNKNOWN_VALUE] = "inv",
233 [PTR_TO_CTX] = "ctx",
234 [CONST_PTR_TO_MAP] = "map_ptr",
235 [PTR_TO_MAP_VALUE] = "map_value",
236 [PTR_TO_MAP_VALUE_OR_NULL] = "map_value_or_null",
237 [FRAME_PTR] = "fp",
238 [PTR_TO_STACK] = "fp",
239 [CONST_IMM] = "imm",
240};
241
242static void print_verifier_state(struct verifier_env *env)
243{
244 enum bpf_reg_type t;
245 int i;
246
247 for (i = 0; i < MAX_BPF_REG; i++) {
248 t = env->cur_state.regs[i].type;
249 if (t == NOT_INIT)
250 continue;
251 verbose(" R%d=%s", i, reg_type_str[t]);
252 if (t == CONST_IMM || t == PTR_TO_STACK)
253 verbose("%d", env->cur_state.regs[i].imm);
254 else if (t == CONST_PTR_TO_MAP || t == PTR_TO_MAP_VALUE ||
255 t == PTR_TO_MAP_VALUE_OR_NULL)
256 verbose("(ks=%d,vs=%d)",
257 env->cur_state.regs[i].map_ptr->key_size,
258 env->cur_state.regs[i].map_ptr->value_size);
259 }
260 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
261 if (env->cur_state.stack_slot_type[i] == STACK_SPILL)
262 verbose(" fp%d=%s", -MAX_BPF_STACK + i,
263 reg_type_str[env->cur_state.spilled_regs[i / BPF_REG_SIZE].type]);
264 }
265 verbose("\n");
266}
267
268static const char *const bpf_class_string[] = {
269 [BPF_LD] = "ld",
270 [BPF_LDX] = "ldx",
271 [BPF_ST] = "st",
272 [BPF_STX] = "stx",
273 [BPF_ALU] = "alu",
274 [BPF_JMP] = "jmp",
275 [BPF_RET] = "BUG",
276 [BPF_ALU64] = "alu64",
277};
278
279static const char *const bpf_alu_string[16] = {
280 [BPF_ADD >> 4] = "+=",
281 [BPF_SUB >> 4] = "-=",
282 [BPF_MUL >> 4] = "*=",
283 [BPF_DIV >> 4] = "/=",
284 [BPF_OR >> 4] = "|=",
285 [BPF_AND >> 4] = "&=",
286 [BPF_LSH >> 4] = "<<=",
287 [BPF_RSH >> 4] = ">>=",
288 [BPF_NEG >> 4] = "neg",
289 [BPF_MOD >> 4] = "%=",
290 [BPF_XOR >> 4] = "^=",
291 [BPF_MOV >> 4] = "=",
292 [BPF_ARSH >> 4] = "s>>=",
293 [BPF_END >> 4] = "endian",
294};
295
296static const char *const bpf_ldst_string[] = {
297 [BPF_W >> 3] = "u32",
298 [BPF_H >> 3] = "u16",
299 [BPF_B >> 3] = "u8",
300 [BPF_DW >> 3] = "u64",
301};
302
303static const char *const bpf_jmp_string[16] = {
304 [BPF_JA >> 4] = "jmp",
305 [BPF_JEQ >> 4] = "==",
306 [BPF_JGT >> 4] = ">",
307 [BPF_JGE >> 4] = ">=",
308 [BPF_JSET >> 4] = "&",
309 [BPF_JNE >> 4] = "!=",
310 [BPF_JSGT >> 4] = "s>",
311 [BPF_JSGE >> 4] = "s>=",
312 [BPF_CALL >> 4] = "call",
313 [BPF_EXIT >> 4] = "exit",
314};
315
316static void print_bpf_insn(struct bpf_insn *insn)
317{
318 u8 class = BPF_CLASS(insn->code);
319
320 if (class == BPF_ALU || class == BPF_ALU64) {
321 if (BPF_SRC(insn->code) == BPF_X)
322 verbose("(%02x) %sr%d %s %sr%d\n",
323 insn->code, class == BPF_ALU ? "(u32) " : "",
324 insn->dst_reg,
325 bpf_alu_string[BPF_OP(insn->code) >> 4],
326 class == BPF_ALU ? "(u32) " : "",
327 insn->src_reg);
328 else
329 verbose("(%02x) %sr%d %s %s%d\n",
330 insn->code, class == BPF_ALU ? "(u32) " : "",
331 insn->dst_reg,
332 bpf_alu_string[BPF_OP(insn->code) >> 4],
333 class == BPF_ALU ? "(u32) " : "",
334 insn->imm);
335 } else if (class == BPF_STX) {
336 if (BPF_MODE(insn->code) == BPF_MEM)
337 verbose("(%02x) *(%s *)(r%d %+d) = r%d\n",
338 insn->code,
339 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
340 insn->dst_reg,
341 insn->off, insn->src_reg);
342 else if (BPF_MODE(insn->code) == BPF_XADD)
343 verbose("(%02x) lock *(%s *)(r%d %+d) += r%d\n",
344 insn->code,
345 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
346 insn->dst_reg, insn->off,
347 insn->src_reg);
348 else
349 verbose("BUG_%02x\n", insn->code);
350 } else if (class == BPF_ST) {
351 if (BPF_MODE(insn->code) != BPF_MEM) {
352 verbose("BUG_st_%02x\n", insn->code);
353 return;
354 }
355 verbose("(%02x) *(%s *)(r%d %+d) = %d\n",
356 insn->code,
357 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
358 insn->dst_reg,
359 insn->off, insn->imm);
360 } else if (class == BPF_LDX) {
361 if (BPF_MODE(insn->code) != BPF_MEM) {
362 verbose("BUG_ldx_%02x\n", insn->code);
363 return;
364 }
365 verbose("(%02x) r%d = *(%s *)(r%d %+d)\n",
366 insn->code, insn->dst_reg,
367 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
368 insn->src_reg, insn->off);
369 } else if (class == BPF_LD) {
370 if (BPF_MODE(insn->code) == BPF_ABS) {
371 verbose("(%02x) r0 = *(%s *)skb[%d]\n",
372 insn->code,
373 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
374 insn->imm);
375 } else if (BPF_MODE(insn->code) == BPF_IND) {
376 verbose("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
377 insn->code,
378 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
379 insn->src_reg, insn->imm);
380 } else if (BPF_MODE(insn->code) == BPF_IMM) {
381 verbose("(%02x) r%d = 0x%x\n",
382 insn->code, insn->dst_reg, insn->imm);
383 } else {
384 verbose("BUG_ld_%02x\n", insn->code);
385 return;
386 }
387 } else if (class == BPF_JMP) {
388 u8 opcode = BPF_OP(insn->code);
389
390 if (opcode == BPF_CALL) {
391 verbose("(%02x) call %d\n", insn->code, insn->imm);
392 } else if (insn->code == (BPF_JMP | BPF_JA)) {
393 verbose("(%02x) goto pc%+d\n",
394 insn->code, insn->off);
395 } else if (insn->code == (BPF_JMP | BPF_EXIT)) {
396 verbose("(%02x) exit\n", insn->code);
397 } else if (BPF_SRC(insn->code) == BPF_X) {
398 verbose("(%02x) if r%d %s r%d goto pc%+d\n",
399 insn->code, insn->dst_reg,
400 bpf_jmp_string[BPF_OP(insn->code) >> 4],
401 insn->src_reg, insn->off);
402 } else {
403 verbose("(%02x) if r%d %s 0x%x goto pc%+d\n",
404 insn->code, insn->dst_reg,
405 bpf_jmp_string[BPF_OP(insn->code) >> 4],
406 insn->imm, insn->off);
407 }
408 } else {
409 verbose("(%02x) %s\n", insn->code, bpf_class_string[class]);
410 }
411}
412
413static int pop_stack(struct verifier_env *env, int *prev_insn_idx)
414{
415 struct verifier_stack_elem *elem;
416 int insn_idx;
417
418 if (env->head == NULL)
419 return -1;
420
421 memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));
422 insn_idx = env->head->insn_idx;
423 if (prev_insn_idx)
424 *prev_insn_idx = env->head->prev_insn_idx;
425 elem = env->head->next;
426 kfree(env->head);
427 env->head = elem;
428 env->stack_size--;
429 return insn_idx;
430}
431
432static struct verifier_state *push_stack(struct verifier_env *env, int insn_idx,
433 int prev_insn_idx)
434{
435 struct verifier_stack_elem *elem;
436
437 elem = kmalloc(sizeof(struct verifier_stack_elem), GFP_KERNEL);
438 if (!elem)
439 goto err;
440
441 memcpy(&elem->st, &env->cur_state, sizeof(env->cur_state));
442 elem->insn_idx = insn_idx;
443 elem->prev_insn_idx = prev_insn_idx;
444 elem->next = env->head;
445 env->head = elem;
446 env->stack_size++;
447 if (env->stack_size > 1024) {
448 verbose("BPF program is too complex\n");
449 goto err;
450 }
451 return &elem->st;
452err:
453
454 while (pop_stack(env, NULL) >= 0);
455 return NULL;
456}
457
458#define CALLER_SAVED_REGS 6
459static const int caller_saved[CALLER_SAVED_REGS] = {
460 BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
461};
462
463static void init_reg_state(struct reg_state *regs)
464{
465 int i;
466
467 for (i = 0; i < MAX_BPF_REG; i++) {
468 regs[i].type = NOT_INIT;
469 regs[i].imm = 0;
470 regs[i].map_ptr = NULL;
471 }
472
473
474 regs[BPF_REG_FP].type = FRAME_PTR;
475
476
477 regs[BPF_REG_1].type = PTR_TO_CTX;
478}
479
480static void mark_reg_unknown_value(struct reg_state *regs, u32 regno)
481{
482 BUG_ON(regno >= MAX_BPF_REG);
483 regs[regno].type = UNKNOWN_VALUE;
484 regs[regno].imm = 0;
485 regs[regno].map_ptr = NULL;
486}
487
488enum reg_arg_type {
489 SRC_OP,
490 DST_OP,
491 DST_OP_NO_MARK
492};
493
494static int check_reg_arg(struct reg_state *regs, u32 regno,
495 enum reg_arg_type t)
496{
497 if (regno >= MAX_BPF_REG) {
498 verbose("R%d is invalid\n", regno);
499 return -EINVAL;
500 }
501
502 if (t == SRC_OP) {
503
504 if (regs[regno].type == NOT_INIT) {
505 verbose("R%d !read_ok\n", regno);
506 return -EACCES;
507 }
508 } else {
509
510 if (regno == BPF_REG_FP) {
511 verbose("frame pointer is read only\n");
512 return -EACCES;
513 }
514 if (t == DST_OP)
515 mark_reg_unknown_value(regs, regno);
516 }
517 return 0;
518}
519
520static int bpf_size_to_bytes(int bpf_size)
521{
522 if (bpf_size == BPF_W)
523 return 4;
524 else if (bpf_size == BPF_H)
525 return 2;
526 else if (bpf_size == BPF_B)
527 return 1;
528 else if (bpf_size == BPF_DW)
529 return 8;
530 else
531 return -EINVAL;
532}
533
534static bool is_spillable_regtype(enum bpf_reg_type type)
535{
536 switch (type) {
537 case PTR_TO_MAP_VALUE:
538 case PTR_TO_MAP_VALUE_OR_NULL:
539 case PTR_TO_STACK:
540 case PTR_TO_CTX:
541 case FRAME_PTR:
542 case CONST_PTR_TO_MAP:
543 return true;
544 default:
545 return false;
546 }
547}
548
549
550
551
552static int check_stack_write(struct verifier_state *state, int off, int size,
553 int value_regno)
554{
555 int i;
556
557
558
559
560 if (value_regno >= 0 &&
561 is_spillable_regtype(state->regs[value_regno].type)) {
562
563
564 if (size != BPF_REG_SIZE) {
565 verbose("invalid size of register spill\n");
566 return -EACCES;
567 }
568
569
570 state->spilled_regs[(MAX_BPF_STACK + off) / BPF_REG_SIZE] =
571 state->regs[value_regno];
572
573 for (i = 0; i < BPF_REG_SIZE; i++)
574 state->stack_slot_type[MAX_BPF_STACK + off + i] = STACK_SPILL;
575 } else {
576
577 state->spilled_regs[(MAX_BPF_STACK + off) / BPF_REG_SIZE] =
578 (struct reg_state) {};
579
580 for (i = 0; i < size; i++)
581 state->stack_slot_type[MAX_BPF_STACK + off + i] = STACK_MISC;
582 }
583 return 0;
584}
585
586static int check_stack_read(struct verifier_state *state, int off, int size,
587 int value_regno)
588{
589 u8 *slot_type;
590 int i;
591
592 slot_type = &state->stack_slot_type[MAX_BPF_STACK + off];
593
594 if (slot_type[0] == STACK_SPILL) {
595 if (size != BPF_REG_SIZE) {
596 verbose("invalid size of register spill\n");
597 return -EACCES;
598 }
599 for (i = 1; i < BPF_REG_SIZE; i++) {
600 if (slot_type[i] != STACK_SPILL) {
601 verbose("corrupted spill memory\n");
602 return -EACCES;
603 }
604 }
605
606 if (value_regno >= 0)
607
608 state->regs[value_regno] =
609 state->spilled_regs[(MAX_BPF_STACK + off) / BPF_REG_SIZE];
610 return 0;
611 } else {
612 for (i = 0; i < size; i++) {
613 if (slot_type[i] != STACK_MISC) {
614 verbose("invalid read from stack off %d+%d size %d\n",
615 off, i, size);
616 return -EACCES;
617 }
618 }
619 if (value_regno >= 0)
620
621 mark_reg_unknown_value(state->regs, value_regno);
622 return 0;
623 }
624}
625
626
627static int check_map_access(struct verifier_env *env, u32 regno, int off,
628 int size)
629{
630 struct bpf_map *map = env->cur_state.regs[regno].map_ptr;
631
632 if (off < 0 || off + size > map->value_size) {
633 verbose("invalid access to map value, value_size=%d off=%d size=%d\n",
634 map->value_size, off, size);
635 return -EACCES;
636 }
637 return 0;
638}
639
640
641static int check_ctx_access(struct verifier_env *env, int off, int size,
642 enum bpf_access_type t)
643{
644 if (env->prog->aux->ops->is_valid_access &&
645 env->prog->aux->ops->is_valid_access(off, size, t))
646 return 0;
647
648 verbose("invalid bpf_context access off=%d size=%d\n", off, size);
649 return -EACCES;
650}
651
652static bool is_pointer_value(struct verifier_env *env, int regno)
653{
654 if (env->allow_ptr_leaks)
655 return false;
656
657 switch (env->cur_state.regs[regno].type) {
658 case UNKNOWN_VALUE:
659 case CONST_IMM:
660 return false;
661 default:
662 return true;
663 }
664}
665
666
667
668
669
670
671
672static int check_mem_access(struct verifier_env *env, u32 regno, int off,
673 int bpf_size, enum bpf_access_type t,
674 int value_regno)
675{
676 struct verifier_state *state = &env->cur_state;
677 int size, err = 0;
678
679 if (state->regs[regno].type == PTR_TO_STACK)
680 off += state->regs[regno].imm;
681
682 size = bpf_size_to_bytes(bpf_size);
683 if (size < 0)
684 return size;
685
686 if (off % size != 0) {
687 verbose("misaligned access off %d size %d\n", off, size);
688 return -EACCES;
689 }
690
691 if (state->regs[regno].type == PTR_TO_MAP_VALUE) {
692 if (t == BPF_WRITE && value_regno >= 0 &&
693 is_pointer_value(env, value_regno)) {
694 verbose("R%d leaks addr into map\n", value_regno);
695 return -EACCES;
696 }
697 err = check_map_access(env, regno, off, size);
698 if (!err && t == BPF_READ && value_regno >= 0)
699 mark_reg_unknown_value(state->regs, value_regno);
700
701 } else if (state->regs[regno].type == PTR_TO_CTX) {
702 if (t == BPF_WRITE && value_regno >= 0 &&
703 is_pointer_value(env, value_regno)) {
704 verbose("R%d leaks addr into ctx\n", value_regno);
705 return -EACCES;
706 }
707 err = check_ctx_access(env, off, size, t);
708 if (!err && t == BPF_READ && value_regno >= 0)
709 mark_reg_unknown_value(state->regs, value_regno);
710
711 } else if (state->regs[regno].type == FRAME_PTR ||
712 state->regs[regno].type == PTR_TO_STACK) {
713 if (off >= 0 || off < -MAX_BPF_STACK) {
714 verbose("invalid stack off=%d size=%d\n", off, size);
715 return -EACCES;
716 }
717 if (t == BPF_WRITE) {
718 if (!env->allow_ptr_leaks &&
719 state->stack_slot_type[MAX_BPF_STACK + off] == STACK_SPILL &&
720 size != BPF_REG_SIZE) {
721 verbose("attempt to corrupt spilled pointer on stack\n");
722 return -EACCES;
723 }
724 err = check_stack_write(state, off, size, value_regno);
725 } else {
726 err = check_stack_read(state, off, size, value_regno);
727 }
728 } else {
729 verbose("R%d invalid mem access '%s'\n",
730 regno, reg_type_str[state->regs[regno].type]);
731 return -EACCES;
732 }
733 return err;
734}
735
736static int check_xadd(struct verifier_env *env, struct bpf_insn *insn)
737{
738 struct reg_state *regs = env->cur_state.regs;
739 int err;
740
741 if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
742 insn->imm != 0) {
743 verbose("BPF_XADD uses reserved fields\n");
744 return -EINVAL;
745 }
746
747
748 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
749 if (err)
750 return err;
751
752
753 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
754 if (err)
755 return err;
756
757
758 err = check_mem_access(env, insn->dst_reg, insn->off,
759 BPF_SIZE(insn->code), BPF_READ, -1);
760 if (err)
761 return err;
762
763
764 return check_mem_access(env, insn->dst_reg, insn->off,
765 BPF_SIZE(insn->code), BPF_WRITE, -1);
766}
767
768
769
770
771
772static int check_stack_boundary(struct verifier_env *env, int regno,
773 int access_size, bool zero_size_allowed)
774{
775 struct verifier_state *state = &env->cur_state;
776 struct reg_state *regs = state->regs;
777 int off, i;
778
779 if (regs[regno].type != PTR_TO_STACK) {
780 if (zero_size_allowed && access_size == 0 &&
781 regs[regno].type == CONST_IMM &&
782 regs[regno].imm == 0)
783 return 0;
784
785 verbose("R%d type=%s expected=%s\n", regno,
786 reg_type_str[regs[regno].type],
787 reg_type_str[PTR_TO_STACK]);
788 return -EACCES;
789 }
790
791 off = regs[regno].imm;
792 if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
793 access_size <= 0) {
794 verbose("invalid stack type R%d off=%d access_size=%d\n",
795 regno, off, access_size);
796 return -EACCES;
797 }
798
799 for (i = 0; i < access_size; i++) {
800 if (state->stack_slot_type[MAX_BPF_STACK + off + i] != STACK_MISC) {
801 verbose("invalid indirect read from stack off %d+%d size %d\n",
802 off, i, access_size);
803 return -EACCES;
804 }
805 }
806 return 0;
807}
808
809static int check_func_arg(struct verifier_env *env, u32 regno,
810 enum bpf_arg_type arg_type, struct bpf_map **mapp)
811{
812 struct reg_state *reg = env->cur_state.regs + regno;
813 enum bpf_reg_type expected_type;
814 int err = 0;
815
816 if (arg_type == ARG_DONTCARE)
817 return 0;
818
819 if (reg->type == NOT_INIT) {
820 verbose("R%d !read_ok\n", regno);
821 return -EACCES;
822 }
823
824 if (arg_type == ARG_ANYTHING) {
825 if (is_pointer_value(env, regno)) {
826 verbose("R%d leaks addr into helper function\n", regno);
827 return -EACCES;
828 }
829 return 0;
830 }
831
832 if (arg_type == ARG_PTR_TO_MAP_KEY ||
833 arg_type == ARG_PTR_TO_MAP_VALUE) {
834 expected_type = PTR_TO_STACK;
835 } else if (arg_type == ARG_CONST_STACK_SIZE ||
836 arg_type == ARG_CONST_STACK_SIZE_OR_ZERO) {
837 expected_type = CONST_IMM;
838 } else if (arg_type == ARG_CONST_MAP_PTR) {
839 expected_type = CONST_PTR_TO_MAP;
840 } else if (arg_type == ARG_PTR_TO_CTX) {
841 expected_type = PTR_TO_CTX;
842 } else if (arg_type == ARG_PTR_TO_STACK) {
843 expected_type = PTR_TO_STACK;
844
845
846
847
848 if (reg->type == CONST_IMM && reg->imm == 0)
849 expected_type = CONST_IMM;
850 } else {
851 verbose("unsupported arg_type %d\n", arg_type);
852 return -EFAULT;
853 }
854
855 if (reg->type != expected_type) {
856 verbose("R%d type=%s expected=%s\n", regno,
857 reg_type_str[reg->type], reg_type_str[expected_type]);
858 return -EACCES;
859 }
860
861 if (arg_type == ARG_CONST_MAP_PTR) {
862
863 *mapp = reg->map_ptr;
864
865 } else if (arg_type == ARG_PTR_TO_MAP_KEY) {
866
867
868
869
870 if (!*mapp) {
871
872
873
874
875
876 verbose("invalid map_ptr to access map->key\n");
877 return -EACCES;
878 }
879 err = check_stack_boundary(env, regno, (*mapp)->key_size,
880 false);
881 } else if (arg_type == ARG_PTR_TO_MAP_VALUE) {
882
883
884
885 if (!*mapp) {
886
887 verbose("invalid map_ptr to access map->value\n");
888 return -EACCES;
889 }
890 err = check_stack_boundary(env, regno, (*mapp)->value_size,
891 false);
892 } else if (arg_type == ARG_CONST_STACK_SIZE ||
893 arg_type == ARG_CONST_STACK_SIZE_OR_ZERO) {
894 bool zero_size_allowed = (arg_type == ARG_CONST_STACK_SIZE_OR_ZERO);
895
896
897
898
899
900 if (regno == 0) {
901
902 verbose("ARG_CONST_STACK_SIZE cannot be first argument\n");
903 return -EACCES;
904 }
905 err = check_stack_boundary(env, regno - 1, reg->imm,
906 zero_size_allowed);
907 }
908
909 return err;
910}
911
912static int check_map_func_compatibility(struct bpf_map *map, int func_id)
913{
914 if (!map)
915 return 0;
916
917
918 switch (map->map_type) {
919 case BPF_MAP_TYPE_PROG_ARRAY:
920 if (func_id != BPF_FUNC_tail_call)
921 goto error;
922 break;
923 case BPF_MAP_TYPE_PERF_EVENT_ARRAY:
924 if (func_id != BPF_FUNC_perf_event_read &&
925 func_id != BPF_FUNC_perf_event_output)
926 goto error;
927 break;
928 case BPF_MAP_TYPE_STACK_TRACE:
929 if (func_id != BPF_FUNC_get_stackid)
930 goto error;
931 break;
932 default:
933 break;
934 }
935
936
937 switch (func_id) {
938 case BPF_FUNC_tail_call:
939 if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
940 goto error;
941 break;
942 case BPF_FUNC_perf_event_read:
943 case BPF_FUNC_perf_event_output:
944 if (map->map_type != BPF_MAP_TYPE_PERF_EVENT_ARRAY)
945 goto error;
946 break;
947 case BPF_FUNC_get_stackid:
948 if (map->map_type != BPF_MAP_TYPE_STACK_TRACE)
949 goto error;
950 break;
951 default:
952 break;
953 }
954
955 return 0;
956error:
957 verbose("cannot pass map_type %d into func %d\n",
958 map->map_type, func_id);
959 return -EINVAL;
960}
961
962static int check_call(struct verifier_env *env, int func_id)
963{
964 struct verifier_state *state = &env->cur_state;
965 const struct bpf_func_proto *fn = NULL;
966 struct reg_state *regs = state->regs;
967 struct bpf_map *map = NULL;
968 struct reg_state *reg;
969 int i, err;
970
971
972 if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
973 verbose("invalid func %d\n", func_id);
974 return -EINVAL;
975 }
976
977 if (env->prog->aux->ops->get_func_proto)
978 fn = env->prog->aux->ops->get_func_proto(func_id);
979
980 if (!fn) {
981 verbose("unknown func %d\n", func_id);
982 return -EINVAL;
983 }
984
985
986 if (!env->prog->gpl_compatible && fn->gpl_only) {
987 verbose("cannot call GPL only function from proprietary program\n");
988 return -EINVAL;
989 }
990
991
992 err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &map);
993 if (err)
994 return err;
995 err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &map);
996 if (err)
997 return err;
998 err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &map);
999 if (err)
1000 return err;
1001 err = check_func_arg(env, BPF_REG_4, fn->arg4_type, &map);
1002 if (err)
1003 return err;
1004 err = check_func_arg(env, BPF_REG_5, fn->arg5_type, &map);
1005 if (err)
1006 return err;
1007
1008
1009 for (i = 0; i < CALLER_SAVED_REGS; i++) {
1010 reg = regs + caller_saved[i];
1011 reg->type = NOT_INIT;
1012 reg->imm = 0;
1013 }
1014
1015
1016 if (fn->ret_type == RET_INTEGER) {
1017 regs[BPF_REG_0].type = UNKNOWN_VALUE;
1018 } else if (fn->ret_type == RET_VOID) {
1019 regs[BPF_REG_0].type = NOT_INIT;
1020 } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) {
1021 regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL;
1022
1023
1024
1025
1026 if (map == NULL) {
1027 verbose("kernel subsystem misconfigured verifier\n");
1028 return -EINVAL;
1029 }
1030 regs[BPF_REG_0].map_ptr = map;
1031 } else {
1032 verbose("unknown return type %d of func %d\n",
1033 fn->ret_type, func_id);
1034 return -EINVAL;
1035 }
1036
1037 err = check_map_func_compatibility(map, func_id);
1038 if (err)
1039 return err;
1040
1041 return 0;
1042}
1043
1044
1045static int check_alu_op(struct verifier_env *env, struct bpf_insn *insn)
1046{
1047 struct reg_state *regs = env->cur_state.regs;
1048 u8 opcode = BPF_OP(insn->code);
1049 int err;
1050
1051 if (opcode == BPF_END || opcode == BPF_NEG) {
1052 if (opcode == BPF_NEG) {
1053 if (BPF_SRC(insn->code) != 0 ||
1054 insn->src_reg != BPF_REG_0 ||
1055 insn->off != 0 || insn->imm != 0) {
1056 verbose("BPF_NEG uses reserved fields\n");
1057 return -EINVAL;
1058 }
1059 } else {
1060 if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
1061 (insn->imm != 16 && insn->imm != 32 && insn->imm != 64)) {
1062 verbose("BPF_END uses reserved fields\n");
1063 return -EINVAL;
1064 }
1065 }
1066
1067
1068 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1069 if (err)
1070 return err;
1071
1072 if (is_pointer_value(env, insn->dst_reg)) {
1073 verbose("R%d pointer arithmetic prohibited\n",
1074 insn->dst_reg);
1075 return -EACCES;
1076 }
1077
1078
1079 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1080 if (err)
1081 return err;
1082
1083 } else if (opcode == BPF_MOV) {
1084
1085 if (BPF_SRC(insn->code) == BPF_X) {
1086 if (insn->imm != 0 || insn->off != 0) {
1087 verbose("BPF_MOV uses reserved fields\n");
1088 return -EINVAL;
1089 }
1090
1091
1092 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1093 if (err)
1094 return err;
1095 } else {
1096 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
1097 verbose("BPF_MOV uses reserved fields\n");
1098 return -EINVAL;
1099 }
1100 }
1101
1102
1103 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1104 if (err)
1105 return err;
1106
1107 if (BPF_SRC(insn->code) == BPF_X) {
1108 if (BPF_CLASS(insn->code) == BPF_ALU64) {
1109
1110
1111
1112 regs[insn->dst_reg] = regs[insn->src_reg];
1113 } else {
1114 if (is_pointer_value(env, insn->src_reg)) {
1115 verbose("R%d partial copy of pointer\n",
1116 insn->src_reg);
1117 return -EACCES;
1118 }
1119 regs[insn->dst_reg].type = UNKNOWN_VALUE;
1120 regs[insn->dst_reg].map_ptr = NULL;
1121 }
1122 } else {
1123
1124
1125
1126 regs[insn->dst_reg].type = CONST_IMM;
1127 regs[insn->dst_reg].imm = insn->imm;
1128 }
1129
1130 } else if (opcode > BPF_END) {
1131 verbose("invalid BPF_ALU opcode %x\n", opcode);
1132 return -EINVAL;
1133
1134 } else {
1135
1136 bool stack_relative = false;
1137
1138 if (BPF_SRC(insn->code) == BPF_X) {
1139 if (insn->imm != 0 || insn->off != 0) {
1140 verbose("BPF_ALU uses reserved fields\n");
1141 return -EINVAL;
1142 }
1143
1144 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1145 if (err)
1146 return err;
1147 } else {
1148 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
1149 verbose("BPF_ALU uses reserved fields\n");
1150 return -EINVAL;
1151 }
1152 }
1153
1154
1155 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1156 if (err)
1157 return err;
1158
1159 if ((opcode == BPF_MOD || opcode == BPF_DIV) &&
1160 BPF_SRC(insn->code) == BPF_K && insn->imm == 0) {
1161 verbose("div by zero\n");
1162 return -EINVAL;
1163 }
1164
1165 if ((opcode == BPF_LSH || opcode == BPF_RSH ||
1166 opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
1167 int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
1168
1169 if (insn->imm < 0 || insn->imm >= size) {
1170 verbose("invalid shift %d\n", insn->imm);
1171 return -EINVAL;
1172 }
1173 }
1174
1175
1176 if (opcode == BPF_ADD && BPF_CLASS(insn->code) == BPF_ALU64 &&
1177 regs[insn->dst_reg].type == FRAME_PTR &&
1178 BPF_SRC(insn->code) == BPF_K) {
1179 stack_relative = true;
1180 } else if (is_pointer_value(env, insn->dst_reg)) {
1181 verbose("R%d pointer arithmetic prohibited\n",
1182 insn->dst_reg);
1183 return -EACCES;
1184 } else if (BPF_SRC(insn->code) == BPF_X &&
1185 is_pointer_value(env, insn->src_reg)) {
1186 verbose("R%d pointer arithmetic prohibited\n",
1187 insn->src_reg);
1188 return -EACCES;
1189 }
1190
1191
1192 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1193 if (err)
1194 return err;
1195
1196 if (stack_relative) {
1197 regs[insn->dst_reg].type = PTR_TO_STACK;
1198 regs[insn->dst_reg].imm = insn->imm;
1199 }
1200 }
1201
1202 return 0;
1203}
1204
1205static int check_cond_jmp_op(struct verifier_env *env,
1206 struct bpf_insn *insn, int *insn_idx)
1207{
1208 struct reg_state *regs = env->cur_state.regs;
1209 struct verifier_state *other_branch;
1210 u8 opcode = BPF_OP(insn->code);
1211 int err;
1212
1213 if (opcode > BPF_EXIT) {
1214 verbose("invalid BPF_JMP opcode %x\n", opcode);
1215 return -EINVAL;
1216 }
1217
1218 if (BPF_SRC(insn->code) == BPF_X) {
1219 if (insn->imm != 0) {
1220 verbose("BPF_JMP uses reserved fields\n");
1221 return -EINVAL;
1222 }
1223
1224
1225 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1226 if (err)
1227 return err;
1228
1229 if (is_pointer_value(env, insn->src_reg)) {
1230 verbose("R%d pointer comparison prohibited\n",
1231 insn->src_reg);
1232 return -EACCES;
1233 }
1234 } else {
1235 if (insn->src_reg != BPF_REG_0) {
1236 verbose("BPF_JMP uses reserved fields\n");
1237 return -EINVAL;
1238 }
1239 }
1240
1241
1242 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1243 if (err)
1244 return err;
1245
1246
1247 if (BPF_SRC(insn->code) == BPF_K &&
1248 (opcode == BPF_JEQ || opcode == BPF_JNE) &&
1249 regs[insn->dst_reg].type == CONST_IMM &&
1250 regs[insn->dst_reg].imm == insn->imm) {
1251 if (opcode == BPF_JEQ) {
1252
1253
1254
1255 *insn_idx += insn->off;
1256 return 0;
1257 } else {
1258
1259
1260
1261
1262 return 0;
1263 }
1264 }
1265
1266 other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx);
1267 if (!other_branch)
1268 return -EFAULT;
1269
1270
1271 if (BPF_SRC(insn->code) == BPF_K &&
1272 insn->imm == 0 && (opcode == BPF_JEQ ||
1273 opcode == BPF_JNE) &&
1274 regs[insn->dst_reg].type == PTR_TO_MAP_VALUE_OR_NULL) {
1275 if (opcode == BPF_JEQ) {
1276
1277
1278
1279 regs[insn->dst_reg].type = PTR_TO_MAP_VALUE;
1280
1281 other_branch->regs[insn->dst_reg].type = CONST_IMM;
1282 other_branch->regs[insn->dst_reg].imm = 0;
1283 } else {
1284 other_branch->regs[insn->dst_reg].type = PTR_TO_MAP_VALUE;
1285 regs[insn->dst_reg].type = CONST_IMM;
1286 regs[insn->dst_reg].imm = 0;
1287 }
1288 } else if (is_pointer_value(env, insn->dst_reg)) {
1289 verbose("R%d pointer comparison prohibited\n", insn->dst_reg);
1290 return -EACCES;
1291 } else if (BPF_SRC(insn->code) == BPF_K &&
1292 (opcode == BPF_JEQ || opcode == BPF_JNE)) {
1293
1294 if (opcode == BPF_JEQ) {
1295
1296
1297
1298 other_branch->regs[insn->dst_reg].type = CONST_IMM;
1299 other_branch->regs[insn->dst_reg].imm = insn->imm;
1300 } else {
1301
1302
1303
1304 regs[insn->dst_reg].type = CONST_IMM;
1305 regs[insn->dst_reg].imm = insn->imm;
1306 }
1307 }
1308 if (log_level)
1309 print_verifier_state(env);
1310 return 0;
1311}
1312
1313
1314static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
1315{
1316 u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32;
1317
1318 return (struct bpf_map *) (unsigned long) imm64;
1319}
1320
1321
1322static int check_ld_imm(struct verifier_env *env, struct bpf_insn *insn)
1323{
1324 struct reg_state *regs = env->cur_state.regs;
1325 int err;
1326
1327 if (BPF_SIZE(insn->code) != BPF_DW) {
1328 verbose("invalid BPF_LD_IMM insn\n");
1329 return -EINVAL;
1330 }
1331 if (insn->off != 0) {
1332 verbose("BPF_LD_IMM64 uses reserved fields\n");
1333 return -EINVAL;
1334 }
1335
1336 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1337 if (err)
1338 return err;
1339
1340 if (insn->src_reg == 0)
1341
1342 return 0;
1343
1344
1345 BUG_ON(insn->src_reg != BPF_PSEUDO_MAP_FD);
1346
1347 regs[insn->dst_reg].type = CONST_PTR_TO_MAP;
1348 regs[insn->dst_reg].map_ptr = ld_imm64_to_map_ptr(insn);
1349 return 0;
1350}
1351
1352static bool may_access_skb(enum bpf_prog_type type)
1353{
1354 switch (type) {
1355 case BPF_PROG_TYPE_SOCKET_FILTER:
1356 case BPF_PROG_TYPE_SCHED_CLS:
1357 case BPF_PROG_TYPE_SCHED_ACT:
1358 return true;
1359 default:
1360 return false;
1361 }
1362}
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379static int check_ld_abs(struct verifier_env *env, struct bpf_insn *insn)
1380{
1381 struct reg_state *regs = env->cur_state.regs;
1382 u8 mode = BPF_MODE(insn->code);
1383 struct reg_state *reg;
1384 int i, err;
1385
1386 if (!may_access_skb(env->prog->type)) {
1387 verbose("BPF_LD_ABS|IND instructions not allowed for this program type\n");
1388 return -EINVAL;
1389 }
1390
1391 if (insn->dst_reg != BPF_REG_0 || insn->off != 0 ||
1392 BPF_SIZE(insn->code) == BPF_DW ||
1393 (mode == BPF_ABS && insn->src_reg != BPF_REG_0)) {
1394 verbose("BPF_LD_ABS uses reserved fields\n");
1395 return -EINVAL;
1396 }
1397
1398
1399 err = check_reg_arg(regs, BPF_REG_6, SRC_OP);
1400 if (err)
1401 return err;
1402
1403 if (regs[BPF_REG_6].type != PTR_TO_CTX) {
1404 verbose("at the time of BPF_LD_ABS|IND R6 != pointer to skb\n");
1405 return -EINVAL;
1406 }
1407
1408 if (mode == BPF_IND) {
1409
1410 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1411 if (err)
1412 return err;
1413 }
1414
1415
1416 for (i = 0; i < CALLER_SAVED_REGS; i++) {
1417 reg = regs + caller_saved[i];
1418 reg->type = NOT_INIT;
1419 reg->imm = 0;
1420 }
1421
1422
1423
1424
1425 regs[BPF_REG_0].type = UNKNOWN_VALUE;
1426 return 0;
1427}
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462enum {
1463 DISCOVERED = 0x10,
1464 EXPLORED = 0x20,
1465 FALLTHROUGH = 1,
1466 BRANCH = 2,
1467};
1468
1469#define STATE_LIST_MARK ((struct verifier_state_list *) -1L)
1470
1471static int *insn_stack;
1472static int cur_stack;
1473static int *insn_state;
1474
1475
1476
1477
1478
1479
1480static int push_insn(int t, int w, int e, struct verifier_env *env)
1481{
1482 if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
1483 return 0;
1484
1485 if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
1486 return 0;
1487
1488 if (w < 0 || w >= env->prog->len) {
1489 verbose("jump out of range from insn %d to %d\n", t, w);
1490 return -EINVAL;
1491 }
1492
1493 if (e == BRANCH)
1494
1495 env->explored_states[w] = STATE_LIST_MARK;
1496
1497 if (insn_state[w] == 0) {
1498
1499 insn_state[t] = DISCOVERED | e;
1500 insn_state[w] = DISCOVERED;
1501 if (cur_stack >= env->prog->len)
1502 return -E2BIG;
1503 insn_stack[cur_stack++] = w;
1504 return 1;
1505 } else if ((insn_state[w] & 0xF0) == DISCOVERED) {
1506 verbose("back-edge from insn %d to %d\n", t, w);
1507 return -EINVAL;
1508 } else if (insn_state[w] == EXPLORED) {
1509
1510 insn_state[t] = DISCOVERED | e;
1511 } else {
1512 verbose("insn state internal bug\n");
1513 return -EFAULT;
1514 }
1515 return 0;
1516}
1517
1518
1519
1520
1521static int check_cfg(struct verifier_env *env)
1522{
1523 struct bpf_insn *insns = env->prog->insnsi;
1524 int insn_cnt = env->prog->len;
1525 int ret = 0;
1526 int i, t;
1527
1528 insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
1529 if (!insn_state)
1530 return -ENOMEM;
1531
1532 insn_stack = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
1533 if (!insn_stack) {
1534 kfree(insn_state);
1535 return -ENOMEM;
1536 }
1537
1538 insn_state[0] = DISCOVERED;
1539 insn_stack[0] = 0;
1540 cur_stack = 1;
1541
1542peek_stack:
1543 if (cur_stack == 0)
1544 goto check_state;
1545 t = insn_stack[cur_stack - 1];
1546
1547 if (BPF_CLASS(insns[t].code) == BPF_JMP) {
1548 u8 opcode = BPF_OP(insns[t].code);
1549
1550 if (opcode == BPF_EXIT) {
1551 goto mark_explored;
1552 } else if (opcode == BPF_CALL) {
1553 ret = push_insn(t, t + 1, FALLTHROUGH, env);
1554 if (ret == 1)
1555 goto peek_stack;
1556 else if (ret < 0)
1557 goto err_free;
1558 } else if (opcode == BPF_JA) {
1559 if (BPF_SRC(insns[t].code) != BPF_K) {
1560 ret = -EINVAL;
1561 goto err_free;
1562 }
1563
1564 ret = push_insn(t, t + insns[t].off + 1,
1565 FALLTHROUGH, env);
1566 if (ret == 1)
1567 goto peek_stack;
1568 else if (ret < 0)
1569 goto err_free;
1570
1571
1572
1573 if (t + 1 < insn_cnt)
1574 env->explored_states[t + 1] = STATE_LIST_MARK;
1575 } else {
1576
1577 ret = push_insn(t, t + 1, FALLTHROUGH, env);
1578 if (ret == 1)
1579 goto peek_stack;
1580 else if (ret < 0)
1581 goto err_free;
1582
1583 ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
1584 if (ret == 1)
1585 goto peek_stack;
1586 else if (ret < 0)
1587 goto err_free;
1588 }
1589 } else {
1590
1591
1592
1593 ret = push_insn(t, t + 1, FALLTHROUGH, env);
1594 if (ret == 1)
1595 goto peek_stack;
1596 else if (ret < 0)
1597 goto err_free;
1598 }
1599
1600mark_explored:
1601 insn_state[t] = EXPLORED;
1602 if (cur_stack-- <= 0) {
1603 verbose("pop stack internal bug\n");
1604 ret = -EFAULT;
1605 goto err_free;
1606 }
1607 goto peek_stack;
1608
1609check_state:
1610 for (i = 0; i < insn_cnt; i++) {
1611 if (insn_state[i] != EXPLORED) {
1612 verbose("unreachable insn %d\n", i);
1613 ret = -EINVAL;
1614 goto err_free;
1615 }
1616 }
1617 ret = 0;
1618
1619err_free:
1620 kfree(insn_state);
1621 kfree(insn_stack);
1622 return ret;
1623}
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651static bool states_equal(struct verifier_state *old, struct verifier_state *cur)
1652{
1653 int i;
1654
1655 for (i = 0; i < MAX_BPF_REG; i++) {
1656 if (memcmp(&old->regs[i], &cur->regs[i],
1657 sizeof(old->regs[0])) != 0) {
1658 if (old->regs[i].type == NOT_INIT ||
1659 (old->regs[i].type == UNKNOWN_VALUE &&
1660 cur->regs[i].type != NOT_INIT))
1661 continue;
1662 return false;
1663 }
1664 }
1665
1666 for (i = 0; i < MAX_BPF_STACK; i++) {
1667 if (old->stack_slot_type[i] == STACK_INVALID)
1668 continue;
1669 if (old->stack_slot_type[i] != cur->stack_slot_type[i])
1670
1671
1672
1673
1674
1675 return false;
1676 if (i % BPF_REG_SIZE)
1677 continue;
1678 if (memcmp(&old->spilled_regs[i / BPF_REG_SIZE],
1679 &cur->spilled_regs[i / BPF_REG_SIZE],
1680 sizeof(old->spilled_regs[0])))
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691 return false;
1692 else
1693 continue;
1694 }
1695 return true;
1696}
1697
1698static int is_state_visited(struct verifier_env *env, int insn_idx)
1699{
1700 struct verifier_state_list *new_sl;
1701 struct verifier_state_list *sl;
1702
1703 sl = env->explored_states[insn_idx];
1704 if (!sl)
1705
1706
1707
1708 return 0;
1709
1710 while (sl != STATE_LIST_MARK) {
1711 if (states_equal(&sl->state, &env->cur_state))
1712
1713
1714
1715 return 1;
1716 sl = sl->next;
1717 }
1718
1719
1720
1721
1722
1723
1724
1725 new_sl = kmalloc(sizeof(struct verifier_state_list), GFP_USER);
1726 if (!new_sl)
1727 return -ENOMEM;
1728
1729
1730 memcpy(&new_sl->state, &env->cur_state, sizeof(env->cur_state));
1731 new_sl->next = env->explored_states[insn_idx];
1732 env->explored_states[insn_idx] = new_sl;
1733 return 0;
1734}
1735
1736static int do_check(struct verifier_env *env)
1737{
1738 struct verifier_state *state = &env->cur_state;
1739 struct bpf_insn *insns = env->prog->insnsi;
1740 struct reg_state *regs = state->regs;
1741 int insn_cnt = env->prog->len;
1742 int insn_idx, prev_insn_idx = 0;
1743 int insn_processed = 0;
1744 bool do_print_state = false;
1745
1746 init_reg_state(regs);
1747 insn_idx = 0;
1748 for (;;) {
1749 struct bpf_insn *insn;
1750 u8 class;
1751 int err;
1752
1753 if (insn_idx >= insn_cnt) {
1754 verbose("invalid insn idx %d insn_cnt %d\n",
1755 insn_idx, insn_cnt);
1756 return -EFAULT;
1757 }
1758
1759 insn = &insns[insn_idx];
1760 class = BPF_CLASS(insn->code);
1761
1762 if (++insn_processed > 32768) {
1763 verbose("BPF program is too large. Proccessed %d insn\n",
1764 insn_processed);
1765 return -E2BIG;
1766 }
1767
1768 err = is_state_visited(env, insn_idx);
1769 if (err < 0)
1770 return err;
1771 if (err == 1) {
1772
1773 if (log_level) {
1774 if (do_print_state)
1775 verbose("\nfrom %d to %d: safe\n",
1776 prev_insn_idx, insn_idx);
1777 else
1778 verbose("%d: safe\n", insn_idx);
1779 }
1780 goto process_bpf_exit;
1781 }
1782
1783 if (log_level && do_print_state) {
1784 verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);
1785 print_verifier_state(env);
1786 do_print_state = false;
1787 }
1788
1789 if (log_level) {
1790 verbose("%d: ", insn_idx);
1791 print_bpf_insn(insn);
1792 }
1793
1794 if (class == BPF_ALU || class == BPF_ALU64) {
1795 err = check_alu_op(env, insn);
1796 if (err)
1797 return err;
1798
1799 } else if (class == BPF_LDX) {
1800 enum bpf_reg_type src_reg_type;
1801
1802
1803
1804
1805 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1806 if (err)
1807 return err;
1808
1809 err = check_reg_arg(regs, insn->dst_reg, DST_OP_NO_MARK);
1810 if (err)
1811 return err;
1812
1813 src_reg_type = regs[insn->src_reg].type;
1814
1815
1816
1817
1818 err = check_mem_access(env, insn->src_reg, insn->off,
1819 BPF_SIZE(insn->code), BPF_READ,
1820 insn->dst_reg);
1821 if (err)
1822 return err;
1823
1824 if (BPF_SIZE(insn->code) != BPF_W) {
1825 insn_idx++;
1826 continue;
1827 }
1828
1829 if (insn->imm == 0) {
1830
1831
1832
1833
1834 insn->imm = src_reg_type;
1835
1836 } else if (src_reg_type != insn->imm &&
1837 (src_reg_type == PTR_TO_CTX ||
1838 insn->imm == PTR_TO_CTX)) {
1839
1840
1841
1842
1843
1844
1845
1846 verbose("same insn cannot be used with different pointers\n");
1847 return -EINVAL;
1848 }
1849
1850 } else if (class == BPF_STX) {
1851 enum bpf_reg_type dst_reg_type;
1852
1853 if (BPF_MODE(insn->code) == BPF_XADD) {
1854 err = check_xadd(env, insn);
1855 if (err)
1856 return err;
1857 insn_idx++;
1858 continue;
1859 }
1860
1861
1862 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1863 if (err)
1864 return err;
1865
1866 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1867 if (err)
1868 return err;
1869
1870 dst_reg_type = regs[insn->dst_reg].type;
1871
1872
1873 err = check_mem_access(env, insn->dst_reg, insn->off,
1874 BPF_SIZE(insn->code), BPF_WRITE,
1875 insn->src_reg);
1876 if (err)
1877 return err;
1878
1879 if (insn->imm == 0) {
1880 insn->imm = dst_reg_type;
1881 } else if (dst_reg_type != insn->imm &&
1882 (dst_reg_type == PTR_TO_CTX ||
1883 insn->imm == PTR_TO_CTX)) {
1884 verbose("same insn cannot be used with different pointers\n");
1885 return -EINVAL;
1886 }
1887
1888 } else if (class == BPF_ST) {
1889 if (BPF_MODE(insn->code) != BPF_MEM ||
1890 insn->src_reg != BPF_REG_0) {
1891 verbose("BPF_ST uses reserved fields\n");
1892 return -EINVAL;
1893 }
1894
1895 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1896 if (err)
1897 return err;
1898
1899
1900 err = check_mem_access(env, insn->dst_reg, insn->off,
1901 BPF_SIZE(insn->code), BPF_WRITE,
1902 -1);
1903 if (err)
1904 return err;
1905
1906 } else if (class == BPF_JMP) {
1907 u8 opcode = BPF_OP(insn->code);
1908
1909 if (opcode == BPF_CALL) {
1910 if (BPF_SRC(insn->code) != BPF_K ||
1911 insn->off != 0 ||
1912 insn->src_reg != BPF_REG_0 ||
1913 insn->dst_reg != BPF_REG_0) {
1914 verbose("BPF_CALL uses reserved fields\n");
1915 return -EINVAL;
1916 }
1917
1918 err = check_call(env, insn->imm);
1919 if (err)
1920 return err;
1921
1922 } else if (opcode == BPF_JA) {
1923 if (BPF_SRC(insn->code) != BPF_K ||
1924 insn->imm != 0 ||
1925 insn->src_reg != BPF_REG_0 ||
1926 insn->dst_reg != BPF_REG_0) {
1927 verbose("BPF_JA uses reserved fields\n");
1928 return -EINVAL;
1929 }
1930
1931 insn_idx += insn->off + 1;
1932 continue;
1933
1934 } else if (opcode == BPF_EXIT) {
1935 if (BPF_SRC(insn->code) != BPF_K ||
1936 insn->imm != 0 ||
1937 insn->src_reg != BPF_REG_0 ||
1938 insn->dst_reg != BPF_REG_0) {
1939 verbose("BPF_EXIT uses reserved fields\n");
1940 return -EINVAL;
1941 }
1942
1943
1944
1945
1946
1947
1948
1949 err = check_reg_arg(regs, BPF_REG_0, SRC_OP);
1950 if (err)
1951 return err;
1952
1953 if (is_pointer_value(env, BPF_REG_0)) {
1954 verbose("R0 leaks addr as return value\n");
1955 return -EACCES;
1956 }
1957
1958process_bpf_exit:
1959 insn_idx = pop_stack(env, &prev_insn_idx);
1960 if (insn_idx < 0) {
1961 break;
1962 } else {
1963 do_print_state = true;
1964 continue;
1965 }
1966 } else {
1967 err = check_cond_jmp_op(env, insn, &insn_idx);
1968 if (err)
1969 return err;
1970 }
1971 } else if (class == BPF_LD) {
1972 u8 mode = BPF_MODE(insn->code);
1973
1974 if (mode == BPF_ABS || mode == BPF_IND) {
1975 err = check_ld_abs(env, insn);
1976 if (err)
1977 return err;
1978
1979 } else if (mode == BPF_IMM) {
1980 err = check_ld_imm(env, insn);
1981 if (err)
1982 return err;
1983
1984 insn_idx++;
1985 } else {
1986 verbose("invalid BPF_LD mode\n");
1987 return -EINVAL;
1988 }
1989 } else {
1990 verbose("unknown insn class %d\n", class);
1991 return -EINVAL;
1992 }
1993
1994 insn_idx++;
1995 }
1996
1997 return 0;
1998}
1999
2000
2001
2002
2003static int replace_map_fd_with_map_ptr(struct verifier_env *env)
2004{
2005 struct bpf_insn *insn = env->prog->insnsi;
2006 int insn_cnt = env->prog->len;
2007 int i, j;
2008
2009 for (i = 0; i < insn_cnt; i++, insn++) {
2010 if (BPF_CLASS(insn->code) == BPF_LDX &&
2011 (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0)) {
2012 verbose("BPF_LDX uses reserved fields\n");
2013 return -EINVAL;
2014 }
2015
2016 if (BPF_CLASS(insn->code) == BPF_STX &&
2017 ((BPF_MODE(insn->code) != BPF_MEM &&
2018 BPF_MODE(insn->code) != BPF_XADD) || insn->imm != 0)) {
2019 verbose("BPF_STX uses reserved fields\n");
2020 return -EINVAL;
2021 }
2022
2023 if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {
2024 struct bpf_map *map;
2025 struct fd f;
2026
2027 if (i == insn_cnt - 1 || insn[1].code != 0 ||
2028 insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
2029 insn[1].off != 0) {
2030 verbose("invalid bpf_ld_imm64 insn\n");
2031 return -EINVAL;
2032 }
2033
2034 if (insn->src_reg == 0)
2035
2036 goto next_insn;
2037
2038 if (insn->src_reg != BPF_PSEUDO_MAP_FD) {
2039 verbose("unrecognized bpf_ld_imm64 insn\n");
2040 return -EINVAL;
2041 }
2042
2043 f = fdget(insn->imm);
2044 map = __bpf_map_get(f);
2045 if (IS_ERR(map)) {
2046 verbose("fd %d is not pointing to valid bpf_map\n",
2047 insn->imm);
2048 return PTR_ERR(map);
2049 }
2050
2051
2052 insn[0].imm = (u32) (unsigned long) map;
2053 insn[1].imm = ((u64) (unsigned long) map) >> 32;
2054
2055
2056 for (j = 0; j < env->used_map_cnt; j++)
2057 if (env->used_maps[j] == map) {
2058 fdput(f);
2059 goto next_insn;
2060 }
2061
2062 if (env->used_map_cnt >= MAX_USED_MAPS) {
2063 fdput(f);
2064 return -E2BIG;
2065 }
2066
2067
2068
2069
2070
2071
2072 map = bpf_map_inc(map, false);
2073 if (IS_ERR(map)) {
2074 fdput(f);
2075 return PTR_ERR(map);
2076 }
2077 env->used_maps[env->used_map_cnt++] = map;
2078
2079 fdput(f);
2080next_insn:
2081 insn++;
2082 i++;
2083 }
2084 }
2085
2086
2087
2088
2089
2090 return 0;
2091}
2092
2093
2094static void release_maps(struct verifier_env *env)
2095{
2096 int i;
2097
2098 for (i = 0; i < env->used_map_cnt; i++)
2099 bpf_map_put(env->used_maps[i]);
2100}
2101
2102
2103static void convert_pseudo_ld_imm64(struct verifier_env *env)
2104{
2105 struct bpf_insn *insn = env->prog->insnsi;
2106 int insn_cnt = env->prog->len;
2107 int i;
2108
2109 for (i = 0; i < insn_cnt; i++, insn++)
2110 if (insn->code == (BPF_LD | BPF_IMM | BPF_DW))
2111 insn->src_reg = 0;
2112}
2113
2114static void adjust_branches(struct bpf_prog *prog, int pos, int delta)
2115{
2116 struct bpf_insn *insn = prog->insnsi;
2117 int insn_cnt = prog->len;
2118 int i;
2119
2120 for (i = 0; i < insn_cnt; i++, insn++) {
2121 if (BPF_CLASS(insn->code) != BPF_JMP ||
2122 BPF_OP(insn->code) == BPF_CALL ||
2123 BPF_OP(insn->code) == BPF_EXIT)
2124 continue;
2125
2126
2127 if (i < pos && i + insn->off + 1 > pos)
2128 insn->off += delta;
2129 else if (i > pos + delta && i + insn->off + 1 <= pos + delta)
2130 insn->off -= delta;
2131 }
2132}
2133
2134
2135
2136
2137static int convert_ctx_accesses(struct verifier_env *env)
2138{
2139 struct bpf_insn *insn = env->prog->insnsi;
2140 int insn_cnt = env->prog->len;
2141 struct bpf_insn insn_buf[16];
2142 struct bpf_prog *new_prog;
2143 u32 cnt;
2144 int i;
2145 enum bpf_access_type type;
2146
2147 if (!env->prog->aux->ops->convert_ctx_access)
2148 return 0;
2149
2150 for (i = 0; i < insn_cnt; i++, insn++) {
2151 if (insn->code == (BPF_LDX | BPF_MEM | BPF_W))
2152 type = BPF_READ;
2153 else if (insn->code == (BPF_STX | BPF_MEM | BPF_W))
2154 type = BPF_WRITE;
2155 else
2156 continue;
2157
2158 if (insn->imm != PTR_TO_CTX) {
2159
2160 insn->imm = 0;
2161 continue;
2162 }
2163
2164 cnt = env->prog->aux->ops->
2165 convert_ctx_access(type, insn->dst_reg, insn->src_reg,
2166 insn->off, insn_buf, env->prog);
2167 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) {
2168 verbose("bpf verifier is misconfigured\n");
2169 return -EINVAL;
2170 }
2171
2172 if (cnt == 1) {
2173 memcpy(insn, insn_buf, sizeof(*insn));
2174 continue;
2175 }
2176
2177
2178 insn_cnt += cnt - 1;
2179 new_prog = bpf_prog_realloc(env->prog,
2180 bpf_prog_size(insn_cnt),
2181 GFP_USER);
2182 if (!new_prog)
2183 return -ENOMEM;
2184
2185 new_prog->len = insn_cnt;
2186
2187 memmove(new_prog->insnsi + i + cnt, new_prog->insns + i + 1,
2188 sizeof(*insn) * (insn_cnt - i - cnt));
2189
2190
2191 memcpy(new_prog->insnsi + i, insn_buf, sizeof(*insn) * cnt);
2192
2193
2194 adjust_branches(new_prog, i, cnt - 1);
2195
2196
2197 env->prog = new_prog;
2198 insn = new_prog->insnsi + i + cnt - 1;
2199 i += cnt - 1;
2200 }
2201
2202 return 0;
2203}
2204
2205static void free_states(struct verifier_env *env)
2206{
2207 struct verifier_state_list *sl, *sln;
2208 int i;
2209
2210 if (!env->explored_states)
2211 return;
2212
2213 for (i = 0; i < env->prog->len; i++) {
2214 sl = env->explored_states[i];
2215
2216 if (sl)
2217 while (sl != STATE_LIST_MARK) {
2218 sln = sl->next;
2219 kfree(sl);
2220 sl = sln;
2221 }
2222 }
2223
2224 kfree(env->explored_states);
2225}
2226
2227int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
2228{
2229 char __user *log_ubuf = NULL;
2230 struct verifier_env *env;
2231 int ret = -EINVAL;
2232
2233 if ((*prog)->len <= 0 || (*prog)->len > BPF_MAXINSNS)
2234 return -E2BIG;
2235
2236
2237
2238
2239 env = kzalloc(sizeof(struct verifier_env), GFP_KERNEL);
2240 if (!env)
2241 return -ENOMEM;
2242
2243 env->prog = *prog;
2244
2245
2246 mutex_lock(&bpf_verifier_lock);
2247
2248 if (attr->log_level || attr->log_buf || attr->log_size) {
2249
2250
2251
2252 log_level = attr->log_level;
2253 log_ubuf = (char __user *) (unsigned long) attr->log_buf;
2254 log_size = attr->log_size;
2255 log_len = 0;
2256
2257 ret = -EINVAL;
2258
2259 if (log_size < 128 || log_size > UINT_MAX >> 8 ||
2260 log_level == 0 || log_ubuf == NULL)
2261 goto free_env;
2262
2263 ret = -ENOMEM;
2264 log_buf = vmalloc(log_size);
2265 if (!log_buf)
2266 goto free_env;
2267 } else {
2268 log_level = 0;
2269 }
2270
2271 ret = replace_map_fd_with_map_ptr(env);
2272 if (ret < 0)
2273 goto skip_full_check;
2274
2275 env->explored_states = kcalloc(env->prog->len,
2276 sizeof(struct verifier_state_list *),
2277 GFP_USER);
2278 ret = -ENOMEM;
2279 if (!env->explored_states)
2280 goto skip_full_check;
2281
2282 ret = check_cfg(env);
2283 if (ret < 0)
2284 goto skip_full_check;
2285
2286 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
2287
2288 ret = do_check(env);
2289
2290skip_full_check:
2291 while (pop_stack(env, NULL) >= 0);
2292 free_states(env);
2293
2294 if (ret == 0)
2295
2296 ret = convert_ctx_accesses(env);
2297
2298 if (log_level && log_len >= log_size - 1) {
2299 BUG_ON(log_len >= log_size);
2300
2301 ret = -ENOSPC;
2302
2303 }
2304
2305
2306 if (log_level && copy_to_user(log_ubuf, log_buf, log_len + 1) != 0) {
2307 ret = -EFAULT;
2308 goto free_log_buf;
2309 }
2310
2311 if (ret == 0 && env->used_map_cnt) {
2312
2313 env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt,
2314 sizeof(env->used_maps[0]),
2315 GFP_KERNEL);
2316
2317 if (!env->prog->aux->used_maps) {
2318 ret = -ENOMEM;
2319 goto free_log_buf;
2320 }
2321
2322 memcpy(env->prog->aux->used_maps, env->used_maps,
2323 sizeof(env->used_maps[0]) * env->used_map_cnt);
2324 env->prog->aux->used_map_cnt = env->used_map_cnt;
2325
2326
2327
2328
2329 convert_pseudo_ld_imm64(env);
2330 }
2331
2332free_log_buf:
2333 if (log_level)
2334 vfree(log_buf);
2335free_env:
2336 if (!env->prog->aux->used_maps)
2337
2338
2339
2340 release_maps(env);
2341 *prog = env->prog;
2342 kfree(env);
2343 mutex_unlock(&bpf_verifier_lock);
2344 return ret;
2345}
2346