projects / linux-block.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
bpf: extend bpf_trace_printk to support %i
[linux-block.git] / kernel / bpf / verifier.c
CommitLineData
51580e79 1/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
969bf05e 2 * Copyright (c) 2016 Facebook
51580e79
AS		 3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of version 2 of the GNU General Public
6 * License as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful, but
9 * WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 */
13#include <linux/kernel.h>
14#include <linux/types.h>
15#include <linux/slab.h>
16#include <linux/bpf.h>
58e2af8b 17#include <linux/bpf_verifier.h>
51580e79
AS		 18#include <linux/filter.h>
19#include <net/netlink.h>
20#include <linux/file.h>
21#include <linux/vmalloc.h>
ebb676da 22#include <linux/stringify.h>
51580e79
AS		 23
24/* bpf_check() is a static code analyzer that walks eBPF program
25 * instruction by instruction and updates register/stack state.
26 * All paths of conditional branches are analyzed until 'bpf_exit' insn.
27 *
28 * The first pass is depth-first-search to check that the program is a DAG.
29 * It rejects the following programs:
30 * - larger than BPF_MAXINSNS insns
31 * - if loop is present (detected via back-edge)
32 * - unreachable insns exist (shouldn't be a forest. program = one function)
33 * - out of bounds or malformed jumps
34 * The second pass is all possible path descent from the 1st insn.
35 * Since it's analyzing all pathes through the program, the length of the
eba38a96 36 * analysis is limited to 64k insn, which may be hit even if total number of
51580e79
AS		 37 * insn is less then 4K, but there are too many branches that change stack/regs.
38 * Number of 'branches to be analyzed' is limited to 1k
39 *
40 * On entry to each instruction, each register has a type, and the instruction
41 * changes the types of the registers depending on instruction semantics.
42 * If instruction is BPF_MOV64_REG(BPF_REG_1, BPF_REG_5), then type of R5 is
43 * copied to R1.
44 *
45 * All registers are 64-bit.
46 * R0 - return register
47 * R1-R5 argument passing registers
48 * R6-R9 callee saved registers
49 * R10 - frame pointer read-only
50 *
51 * At the start of BPF program the register R1 contains a pointer to bpf_context
52 * and has type PTR_TO_CTX.
53 *
54 * Verifier tracks arithmetic operations on pointers in case:
55 * BPF_MOV64_REG(BPF_REG_1, BPF_REG_10),
56 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, -20),
57 * 1st insn copies R10 (which has FRAME_PTR) type into R1
58 * and 2nd arithmetic instruction is pattern matched to recognize
59 * that it wants to construct a pointer to some element within stack.
60 * So after 2nd insn, the register R1 has type PTR_TO_STACK
61 * (and -20 constant is saved for further stack bounds checking).
62 * Meaning that this reg is a pointer to stack plus known immediate constant.
63 *
64 * Most of the time the registers have UNKNOWN_VALUE type, which
65 * means the register has some value, but it's not a valid pointer.
66 * (like pointer plus pointer becomes UNKNOWN_VALUE type)
67 *
68 * When verifier sees load or store instructions the type of base register
69 * can be: PTR_TO_MAP_VALUE, PTR_TO_CTX, FRAME_PTR. These are three pointer
70 * types recognized by check_mem_access() function.
71 *
72 * PTR_TO_MAP_VALUE means that this register is pointing to 'map element value'
73 * and the range of [ptr, ptr + map's value_size) is accessible.
74 *
75 * registers used to pass values to function calls are checked against
76 * function argument constraints.
77 *
78 * ARG_PTR_TO_MAP_KEY is one of such argument constraints.
79 * It means that the register type passed to this function must be
80 * PTR_TO_STACK and it will be used inside the function as
81 * 'pointer to map element key'
82 *
83 * For example the argument constraints for bpf_map_lookup_elem():
84 * .ret_type = RET_PTR_TO_MAP_VALUE_OR_NULL,
85 * .arg1_type = ARG_CONST_MAP_PTR,
86 * .arg2_type = ARG_PTR_TO_MAP_KEY,
87 *
88 * ret_type says that this function returns 'pointer to map elem value or null'
89 * function expects 1st argument to be a const pointer to 'struct bpf_map' and
90 * 2nd argument should be a pointer to stack, which will be used inside
91 * the helper function as a pointer to map element key.
92 *
93 * On the kernel side the helper function looks like:
94 * u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
95 * {
96 * struct bpf_map *map = (struct bpf_map *) (unsigned long) r1;
97 * void *key = (void *) (unsigned long) r2;
98 * void *value;
99 *
100 * here kernel can access 'key' and 'map' pointers safely, knowing that
101 * [key, key + map->key_size) bytes are valid and were initialized on
102 * the stack of eBPF program.
103 * }
104 *
105 * Corresponding eBPF program may look like:
106 * BPF_MOV64_REG(BPF_REG_2, BPF_REG_10), // after this insn R2 type is FRAME_PTR
107 * BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -4), // after this insn R2 type is PTR_TO_STACK
108 * BPF_LD_MAP_FD(BPF_REG_1, map_fd), // after this insn R1 type is CONST_PTR_TO_MAP
109 * BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
110 * here verifier looks at prototype of map_lookup_elem() and sees:
111 * .arg1_type == ARG_CONST_MAP_PTR and R1->type == CONST_PTR_TO_MAP, which is ok,
112 * Now verifier knows that this map has key of R1->map_ptr->key_size bytes
113 *
114 * Then .arg2_type == ARG_PTR_TO_MAP_KEY and R2->type == PTR_TO_STACK, ok so far,
115 * Now verifier checks that [R2, R2 + map's key_size) are within stack limits
116 * and were initialized prior to this call.
117 * If it's ok, then verifier allows this BPF_CALL insn and looks at
118 * .ret_type which is RET_PTR_TO_MAP_VALUE_OR_NULL, so it sets
119 * R0->type = PTR_TO_MAP_VALUE_OR_NULL which means bpf_map_lookup_elem() function
120 * returns ether pointer to map value or NULL.
121 *
122 * When type PTR_TO_MAP_VALUE_OR_NULL passes through 'if (reg != 0) goto +off'
123 * insn, the register holding that pointer in the true branch changes state to
124 * PTR_TO_MAP_VALUE and the same register changes state to CONST_IMM in the false
125 * branch. See check_cond_jmp_op().
126 *
127 * After the call R0 is set to return type of the function and registers R1-R5
128 * are set to NOT_INIT to indicate that they are no longer readable.
129 */
130
17a52670 131/* verifier_state + insn_idx are pushed to stack when branch is encountered */
58e2af8b 132struct bpf_verifier_stack_elem {
17a52670
AS		 133 /* verifer state is 'st'
134 * before processing instruction 'insn_idx'
135 * and after processing instruction 'prev_insn_idx'
136 */
58e2af8b 137 struct bpf_verifier_state st;
17a52670
AS		 138 int insn_idx;
139 int prev_insn_idx;
58e2af8b 140 struct bpf_verifier_stack_elem *next;
cbd35700
AS		 141};
142
3c2ce60b 143#define BPF_COMPLEXITY_LIMIT_INSNS 98304
07016151
DB		 144#define BPF_COMPLEXITY_LIMIT_STACK 1024
145
fad73a1a
MKL		 146#define BPF_MAP_PTR_POISON ((void *)0xeB9F + POISON_POINTER_DELTA)
147
33ff9823
DB		 148struct bpf_call_arg_meta {
149 struct bpf_map *map_ptr;
435faee1 150 bool raw_mode;
36bbef52 151 bool pkt_access;
435faee1
DB		 152 int regno;
153 int access_size;
33ff9823
DB		 154};
155
cbd35700
AS		 156/* verbose verifier prints what it's seeing
157 * bpf_check() is called under lock, so no race to access these global vars
158 */
159static u32 log_level, log_size, log_len;
160static char *log_buf;
161
162static DEFINE_MUTEX(bpf_verifier_lock);
163
164/* log_level controls verbosity level of eBPF verifier.
165 * verbose() is used to dump the verification trace to the log, so the user
166 * can figure out what's wrong with the program
167 */
1d056d9c 168static __printf(1, 2) void verbose(const char *fmt, ...)
cbd35700
AS		 169{
170 va_list args;
171
172 if (log_level == 0 || log_len >= log_size - 1)
173 return;
174
175 va_start(args, fmt);
176 log_len += vscnprintf(log_buf + log_len, log_size - log_len, fmt, args);
177 va_end(args);
178}
179
17a52670
AS		 180/* string representation of 'enum bpf_reg_type' */
181static const char * const reg_type_str[] = {
182 [NOT_INIT] = "?",
183 [UNKNOWN_VALUE] = "inv",
184 [PTR_TO_CTX] = "ctx",
185 [CONST_PTR_TO_MAP] = "map_ptr",
186 [PTR_TO_MAP_VALUE] = "map_value",
187 [PTR_TO_MAP_VALUE_OR_NULL] = "map_value_or_null",
48461135 188 [PTR_TO_MAP_VALUE_ADJ] = "map_value_adj",
17a52670
AS		 189 [FRAME_PTR] = "fp",
190 [PTR_TO_STACK] = "fp",
191 [CONST_IMM] = "imm",
969bf05e
AS		 192 [PTR_TO_PACKET] = "pkt",
193 [PTR_TO_PACKET_END] = "pkt_end",
17a52670
AS		 194};
195
ebb676da
TG		 196#define __BPF_FUNC_STR_FN(x) [BPF_FUNC_ ## x] = __stringify(bpf_ ## x)
197static const char * const func_id_str[] = {
198 __BPF_FUNC_MAPPER(__BPF_FUNC_STR_FN)
199};
200#undef __BPF_FUNC_STR_FN
201
202static const char *func_id_name(int id)
203{
204 BUILD_BUG_ON(ARRAY_SIZE(func_id_str) != __BPF_FUNC_MAX_ID);
205
206 if (id >= 0 && id < __BPF_FUNC_MAX_ID && func_id_str[id])
207 return func_id_str[id];
208 else
209 return "unknown";
210}
211
58e2af8b 212static void print_verifier_state(struct bpf_verifier_state *state)
17a52670 213{
58e2af8b 214 struct bpf_reg_state *reg;
17a52670
AS		 215 enum bpf_reg_type t;
216 int i;
217
218 for (i = 0; i < MAX_BPF_REG; i++) {
1a0dc1ac
AS		 219 reg = &state->regs[i];
220 t = reg->type;
17a52670
AS		 221 if (t == NOT_INIT)
222 continue;
223 verbose(" R%d=%s", i, reg_type_str[t]);
224 if (t == CONST_IMM || t == PTR_TO_STACK)
969bf05e
AS		 225 verbose("%lld", reg->imm);
226 else if (t == PTR_TO_PACKET)
227 verbose("(id=%d,off=%d,r=%d)",
228 reg->id, reg->off, reg->range);
229 else if (t == UNKNOWN_VALUE && reg->imm)
230 verbose("%lld", reg->imm);
17a52670 231 else if (t == CONST_PTR_TO_MAP || t == PTR_TO_MAP_VALUE ||
48461135
JB		 232 t == PTR_TO_MAP_VALUE_OR_NULL ||
233 t == PTR_TO_MAP_VALUE_ADJ)
57a09bf0 234 verbose("(ks=%d,vs=%d,id=%u)",
1a0dc1ac 235 reg->map_ptr->key_size,
57a09bf0
TG		 236 reg->map_ptr->value_size,
237 reg->id);
48461135 238 if (reg->min_value != BPF_REGISTER_MIN_RANGE)
f23cc643
JB		 239 verbose(",min_value=%lld",
240 (long long)reg->min_value);
48461135
JB		 241 if (reg->max_value != BPF_REGISTER_MAX_RANGE)
242 verbose(",max_value=%llu",
243 (unsigned long long)reg->max_value);
d1174416
DM		 244 if (reg->min_align)
245 verbose(",min_align=%u", reg->min_align);
246 if (reg->aux_off)
247 verbose(",aux_off=%u", reg->aux_off);
248 if (reg->aux_off_align)
249 verbose(",aux_off_align=%u", reg->aux_off_align);
17a52670 250 }
9c399760 251 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
1a0dc1ac 252 if (state->stack_slot_type[i] == STACK_SPILL)
17a52670 253 verbose(" fp%d=%s", -MAX_BPF_STACK + i,
1a0dc1ac 254 reg_type_str[state->spilled_regs[i / BPF_REG_SIZE].type]);
17a52670
AS		 255 }
256 verbose("\n");
257}
258
cbd35700
AS		 259static const char *const bpf_class_string[] = {
260 [BPF_LD] = "ld",
261 [BPF_LDX] = "ldx",
262 [BPF_ST] = "st",
263 [BPF_STX] = "stx",
264 [BPF_ALU] = "alu",
265 [BPF_JMP] = "jmp",
266 [BPF_RET] = "BUG",
267 [BPF_ALU64] = "alu64",
268};
269
687f0715 270static const char *const bpf_alu_string[16] = {
cbd35700
AS		 271 [BPF_ADD >> 4] = "+=",
272 [BPF_SUB >> 4] = "-=",
273 [BPF_MUL >> 4] = "*=",
274 [BPF_DIV >> 4] = "/=",
275 [BPF_OR >> 4] = "|=",
276 [BPF_AND >> 4] = "&=",
277 [BPF_LSH >> 4] = "<<=",
278 [BPF_RSH >> 4] = ">>=",
279 [BPF_NEG >> 4] = "neg",
280 [BPF_MOD >> 4] = "%=",
281 [BPF_XOR >> 4] = "^=",
282 [BPF_MOV >> 4] = "=",
283 [BPF_ARSH >> 4] = "s>>=",
284 [BPF_END >> 4] = "endian",
285};
286
287static const char *const bpf_ldst_string[] = {
288 [BPF_W >> 3] = "u32",
289 [BPF_H >> 3] = "u16",
290 [BPF_B >> 3] = "u8",
291 [BPF_DW >> 3] = "u64",
292};
293
687f0715 294static const char *const bpf_jmp_string[16] = {
cbd35700
AS		 295 [BPF_JA >> 4] = "jmp",
296 [BPF_JEQ >> 4] = "==",
297 [BPF_JGT >> 4] = ">",
298 [BPF_JGE >> 4] = ">=",
299 [BPF_JSET >> 4] = "&",
300 [BPF_JNE >> 4] = "!=",
301 [BPF_JSGT >> 4] = "s>",
302 [BPF_JSGE >> 4] = "s>=",
303 [BPF_CALL >> 4] = "call",
304 [BPF_EXIT >> 4] = "exit",
305};
306
0d0e5769
DB		 307static void print_bpf_insn(const struct bpf_verifier_env *env,
308 const struct bpf_insn *insn)
cbd35700
AS		 309{
310 u8 class = BPF_CLASS(insn->code);
311
312 if (class == BPF_ALU || class == BPF_ALU64) {
313 if (BPF_SRC(insn->code) == BPF_X)
314 verbose("(%02x) %sr%d %s %sr%d\n",
315 insn->code, class == BPF_ALU ? "(u32) " : "",
316 insn->dst_reg,
317 bpf_alu_string[BPF_OP(insn->code) >> 4],
318 class == BPF_ALU ? "(u32) " : "",
319 insn->src_reg);
320 else
321 verbose("(%02x) %sr%d %s %s%d\n",
322 insn->code, class == BPF_ALU ? "(u32) " : "",
323 insn->dst_reg,
324 bpf_alu_string[BPF_OP(insn->code) >> 4],
325 class == BPF_ALU ? "(u32) " : "",
326 insn->imm);
327 } else if (class == BPF_STX) {
328 if (BPF_MODE(insn->code) == BPF_MEM)
329 verbose("(%02x) *(%s *)(r%d %+d) = r%d\n",
330 insn->code,
331 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
332 insn->dst_reg,
333 insn->off, insn->src_reg);
334 else if (BPF_MODE(insn->code) == BPF_XADD)
335 verbose("(%02x) lock *(%s *)(r%d %+d) += r%d\n",
336 insn->code,
337 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
338 insn->dst_reg, insn->off,
339 insn->src_reg);
340 else
341 verbose("BUG_%02x\n", insn->code);
342 } else if (class == BPF_ST) {
343 if (BPF_MODE(insn->code) != BPF_MEM) {
344 verbose("BUG_st_%02x\n", insn->code);
345 return;
346 }
347 verbose("(%02x) *(%s *)(r%d %+d) = %d\n",
348 insn->code,
349 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
350 insn->dst_reg,
351 insn->off, insn->imm);
352 } else if (class == BPF_LDX) {
353 if (BPF_MODE(insn->code) != BPF_MEM) {
354 verbose("BUG_ldx_%02x\n", insn->code);
355 return;
356 }
357 verbose("(%02x) r%d = *(%s *)(r%d %+d)\n",
358 insn->code, insn->dst_reg,
359 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
360 insn->src_reg, insn->off);
361 } else if (class == BPF_LD) {
362 if (BPF_MODE(insn->code) == BPF_ABS) {
363 verbose("(%02x) r0 = *(%s *)skb[%d]\n",
364 insn->code,
365 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
366 insn->imm);
367 } else if (BPF_MODE(insn->code) == BPF_IND) {
368 verbose("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
369 insn->code,
370 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
371 insn->src_reg, insn->imm);
0d0e5769
DB		 372 } else if (BPF_MODE(insn->code) == BPF_IMM &&
373 BPF_SIZE(insn->code) == BPF_DW) {
374 /* At this point, we already made sure that the second
375 * part of the ldimm64 insn is accessible.
376 */
377 u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm;
378 bool map_ptr = insn->src_reg == BPF_PSEUDO_MAP_FD;
379
380 if (map_ptr && !env->allow_ptr_leaks)
381 imm = 0;
382
383 verbose("(%02x) r%d = 0x%llx\n", insn->code,
384 insn->dst_reg, (unsigned long long)imm);
cbd35700
AS		 385 } else {
386 verbose("BUG_ld_%02x\n", insn->code);
387 return;
388 }
389 } else if (class == BPF_JMP) {
390 u8 opcode = BPF_OP(insn->code);
391
392 if (opcode == BPF_CALL) {
ebb676da
TG		 393 verbose("(%02x) call %s#%d\n", insn->code,
394 func_id_name(insn->imm), insn->imm);
cbd35700
AS		 395 } else if (insn->code == (BPF_JMP | BPF_JA)) {
396 verbose("(%02x) goto pc%+d\n",
397 insn->code, insn->off);
398 } else if (insn->code == (BPF_JMP | BPF_EXIT)) {
399 verbose("(%02x) exit\n", insn->code);
400 } else if (BPF_SRC(insn->code) == BPF_X) {
401 verbose("(%02x) if r%d %s r%d goto pc%+d\n",
402 insn->code, insn->dst_reg,
403 bpf_jmp_string[BPF_OP(insn->code) >> 4],
404 insn->src_reg, insn->off);
405 } else {
406 verbose("(%02x) if r%d %s 0x%x goto pc%+d\n",
407 insn->code, insn->dst_reg,
408 bpf_jmp_string[BPF_OP(insn->code) >> 4],
409 insn->imm, insn->off);
410 }
411 } else {
412 verbose("(%02x) %s\n", insn->code, bpf_class_string[class]);
413 }
414}
415
58e2af8b 416static int pop_stack(struct bpf_verifier_env *env, int *prev_insn_idx)
17a52670 417{
58e2af8b 418 struct bpf_verifier_stack_elem *elem;
17a52670
AS		 419 int insn_idx;
420
421 if (env->head == NULL)
422 return -1;
423
424 memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));
425 insn_idx = env->head->insn_idx;
426 if (prev_insn_idx)
427 *prev_insn_idx = env->head->prev_insn_idx;
428 elem = env->head->next;
429 kfree(env->head);
430 env->head = elem;
431 env->stack_size--;
432 return insn_idx;
433}
434
58e2af8b
JK		 435static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env,
436 int insn_idx, int prev_insn_idx)
17a52670 437{
58e2af8b 438 struct bpf_verifier_stack_elem *elem;
17a52670 439
58e2af8b 440 elem = kmalloc(sizeof(struct bpf_verifier_stack_elem), GFP_KERNEL);
17a52670
AS		 441 if (!elem)
442 goto err;
443
444 memcpy(&elem->st, &env->cur_state, sizeof(env->cur_state));
445 elem->insn_idx = insn_idx;
446 elem->prev_insn_idx = prev_insn_idx;
447 elem->next = env->head;
448 env->head = elem;
449 env->stack_size++;
07016151 450 if (env->stack_size > BPF_COMPLEXITY_LIMIT_STACK) {
17a52670
AS		 451 verbose("BPF program is too complex\n");
452 goto err;
453 }
454 return &elem->st;
455err:
456 /* pop all elements and return */
457 while (pop_stack(env, NULL) >= 0);
458 return NULL;
459}
460
461#define CALLER_SAVED_REGS 6
462static const int caller_saved[CALLER_SAVED_REGS] = {
463 BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
464};
465
a9789ef9
DB		 466static void mark_reg_not_init(struct bpf_reg_state *regs, u32 regno)
467{
468 BUG_ON(regno >= MAX_BPF_REG);
469
470 memset(&regs[regno], 0, sizeof(regs[regno]));
471 regs[regno].type = NOT_INIT;
472 regs[regno].min_value = BPF_REGISTER_MIN_RANGE;
473 regs[regno].max_value = BPF_REGISTER_MAX_RANGE;
474}
475
58e2af8b 476static void init_reg_state(struct bpf_reg_state *regs)
17a52670
AS		 477{
478 int i;
479
a9789ef9
DB		 480 for (i = 0; i < MAX_BPF_REG; i++)
481 mark_reg_not_init(regs, i);
17a52670
AS		 482
483 /* frame pointer */
484 regs[BPF_REG_FP].type = FRAME_PTR;
485
486 /* 1st arg to a function */
487 regs[BPF_REG_1].type = PTR_TO_CTX;
488}
489
6760bf2d 490static void __mark_reg_unknown_value(struct bpf_reg_state *regs, u32 regno)
17a52670 491{
17a52670 492 regs[regno].type = UNKNOWN_VALUE;
57a09bf0 493 regs[regno].id = 0;
17a52670 494 regs[regno].imm = 0;
17a52670
AS		 495}
496
6760bf2d
DB		 497static void mark_reg_unknown_value(struct bpf_reg_state *regs, u32 regno)
498{
499 BUG_ON(regno >= MAX_BPF_REG);
500 __mark_reg_unknown_value(regs, regno);
501}
502
48461135
JB		 503static void reset_reg_range_values(struct bpf_reg_state *regs, u32 regno)
504{
505 regs[regno].min_value = BPF_REGISTER_MIN_RANGE;
506 regs[regno].max_value = BPF_REGISTER_MAX_RANGE;
d1174416 507 regs[regno].min_align = 0;
48461135
JB		 508}
509
f0318d01
GB		 510static void mark_reg_unknown_value_and_range(struct bpf_reg_state *regs,
511 u32 regno)
512{
513 mark_reg_unknown_value(regs, regno);
514 reset_reg_range_values(regs, regno);
515}
516
17a52670
AS		 517enum reg_arg_type {
518 SRC_OP, /* register is used as source operand */
519 DST_OP, /* register is used as destination operand */
520 DST_OP_NO_MARK /* same as above, check only, don't mark */
521};
522
58e2af8b 523static int check_reg_arg(struct bpf_reg_state *regs, u32 regno,
17a52670
AS		 524 enum reg_arg_type t)
525{
526 if (regno >= MAX_BPF_REG) {
527 verbose("R%d is invalid\n", regno);
528 return -EINVAL;
529 }
530
531 if (t == SRC_OP) {
532 /* check whether register used as source operand can be read */
533 if (regs[regno].type == NOT_INIT) {
534 verbose("R%d !read_ok\n", regno);
535 return -EACCES;
536 }
537 } else {
538 /* check whether register used as dest operand can be written to */
539 if (regno == BPF_REG_FP) {
540 verbose("frame pointer is read only\n");
541 return -EACCES;
542 }
543 if (t == DST_OP)
544 mark_reg_unknown_value(regs, regno);
545 }
546 return 0;
547}
548
1be7f75d
AS		 549static bool is_spillable_regtype(enum bpf_reg_type type)
550{
551 switch (type) {
552 case PTR_TO_MAP_VALUE:
553 case PTR_TO_MAP_VALUE_OR_NULL:
f0318d01 554 case PTR_TO_MAP_VALUE_ADJ:
1be7f75d
AS		 555 case PTR_TO_STACK:
556 case PTR_TO_CTX:
969bf05e
AS		 557 case PTR_TO_PACKET:
558 case PTR_TO_PACKET_END:
1be7f75d
AS		 559 case FRAME_PTR:
560 case CONST_PTR_TO_MAP:
561 return true;
562 default:
563 return false;
564 }
565}
566
17a52670
AS		 567/* check_stack_read/write functions track spill/fill of registers,
568 * stack boundary and alignment are checked in check_mem_access()
569 */
58e2af8b
JK		 570static int check_stack_write(struct bpf_verifier_state *state, int off,
571 int size, int value_regno)
17a52670 572{
17a52670 573 int i;
9c399760
AS		 574 /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
575 * so it's aligned access and [off, off + size) are within stack limits
576 */
17a52670
AS		 577
578 if (value_regno >= 0 &&
1be7f75d 579 is_spillable_regtype(state->regs[value_regno].type)) {
17a52670
AS		 580
581 /* register containing pointer is being spilled into stack */
9c399760 582 if (size != BPF_REG_SIZE) {
17a52670
AS		 583 verbose("invalid size of register spill\n");
584 return -EACCES;
585 }
586
17a52670 587 /* save register state */
9c399760
AS		 588 state->spilled_regs[(MAX_BPF_STACK + off) / BPF_REG_SIZE] =
589 state->regs[value_regno];
17a52670 590
9c399760
AS		 591 for (i = 0; i < BPF_REG_SIZE; i++)
592 state->stack_slot_type[MAX_BPF_STACK + off + i] = STACK_SPILL;
593 } else {
17a52670 594 /* regular write of data into stack */
9c399760 595 state->spilled_regs[(MAX_BPF_STACK + off) / BPF_REG_SIZE] =
58e2af8b 596 (struct bpf_reg_state) {};
9c399760
AS		 597
598 for (i = 0; i < size; i++)
599 state->stack_slot_type[MAX_BPF_STACK + off + i] = STACK_MISC;
17a52670
AS		 600 }
601 return 0;
602}
603
58e2af8b 604static int check_stack_read(struct bpf_verifier_state *state, int off, int size,
17a52670
AS		 605 int value_regno)
606{
9c399760 607 u8 *slot_type;
17a52670 608 int i;
17a52670 609
9c399760 610 slot_type = &state->stack_slot_type[MAX_BPF_STACK + off];
17a52670 611
9c399760
AS		 612 if (slot_type[0] == STACK_SPILL) {
613 if (size != BPF_REG_SIZE) {
17a52670
AS		 614 verbose("invalid size of register spill\n");
615 return -EACCES;
616 }
9c399760
AS		 617 for (i = 1; i < BPF_REG_SIZE; i++) {
618 if (slot_type[i] != STACK_SPILL) {
17a52670
AS		 619 verbose("corrupted spill memory\n");
620 return -EACCES;
621 }
622 }
623
624 if (value_regno >= 0)
625 /* restore register state from stack */
9c399760
AS		 626 state->regs[value_regno] =
627 state->spilled_regs[(MAX_BPF_STACK + off) / BPF_REG_SIZE];
17a52670
AS		 628 return 0;
629 } else {
630 for (i = 0; i < size; i++) {
9c399760 631 if (slot_type[i] != STACK_MISC) {
17a52670
AS		 632 verbose("invalid read from stack off %d+%d size %d\n",
633 off, i, size);
634 return -EACCES;
635 }
636 }
637 if (value_regno >= 0)
638 /* have read misc data from the stack */
f0318d01
GB		 639 mark_reg_unknown_value_and_range(state->regs,
640 value_regno);
17a52670
AS		 641 return 0;
642 }
643}
644
645/* check read/write into map element returned by bpf_map_lookup_elem() */
58e2af8b 646static int check_map_access(struct bpf_verifier_env *env, u32 regno, int off,
17a52670
AS		 647 int size)
648{
649 struct bpf_map *map = env->cur_state.regs[regno].map_ptr;
650
5722569b 651 if (off < 0 || size <= 0 || off + size > map->value_size) {
17a52670
AS		 652 verbose("invalid access to map value, value_size=%d off=%d size=%d\n",
653 map->value_size, off, size);
654 return -EACCES;
655 }
656 return 0;
657}
658
dbcfe5f7
GB		 659/* check read/write into an adjusted map element */
660static int check_map_access_adj(struct bpf_verifier_env *env, u32 regno,
661 int off, int size)
662{
663 struct bpf_verifier_state *state = &env->cur_state;
664 struct bpf_reg_state *reg = &state->regs[regno];
665 int err;
666
667 /* We adjusted the register to this map value, so we
668 * need to change off and size to min_value and max_value
669 * respectively to make sure our theoretical access will be
670 * safe.
671 */
672 if (log_level)
673 print_verifier_state(state);
674 env->varlen_map_value_access = true;
675 /* The minimum value is only important with signed
676 * comparisons where we can't assume the floor of a
677 * value is 0. If we are using signed variables for our
678 * index'es we need to make sure that whatever we use
679 * will have a set floor within our range.
680 */
681 if (reg->min_value < 0) {
682 verbose("R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
683 regno);
684 return -EACCES;
685 }
686 err = check_map_access(env, regno, reg->min_value + off, size);
687 if (err) {
688 verbose("R%d min value is outside of the array range\n",
689 regno);
690 return err;
691 }
692
693 /* If we haven't set a max value then we need to bail
694 * since we can't be sure we won't do bad things.
695 */
696 if (reg->max_value == BPF_REGISTER_MAX_RANGE) {
697 verbose("R%d unbounded memory access, make sure to bounds check any array access into a map\n",
698 regno);
699 return -EACCES;
700 }
701 return check_map_access(env, regno, reg->max_value + off, size);
702}
703
969bf05e
AS		 704#define MAX_PACKET_OFF 0xffff
705
58e2af8b 706static bool may_access_direct_pkt_data(struct bpf_verifier_env *env,
3a0af8fd
TG		 707 const struct bpf_call_arg_meta *meta,
708 enum bpf_access_type t)
4acf6c0b 709{
36bbef52 710 switch (env->prog->type) {
3a0af8fd
TG		 711 case BPF_PROG_TYPE_LWT_IN:
712 case BPF_PROG_TYPE_LWT_OUT:
713 /* dst_input() and dst_output() can't write for now */
714 if (t == BPF_WRITE)
715 return false;
7e57fbb2 716 /* fallthrough */
36bbef52
DB		 717 case BPF_PROG_TYPE_SCHED_CLS:
718 case BPF_PROG_TYPE_SCHED_ACT:
4acf6c0b 719 case BPF_PROG_TYPE_XDP:
3a0af8fd 720 case BPF_PROG_TYPE_LWT_XMIT:
36bbef52
DB		 721 if (meta)
722 return meta->pkt_access;
723
724 env->seen_direct_write = true;
4acf6c0b
BB		 725 return true;
726 default:
727 return false;
728 }
729}
730
58e2af8b 731static int check_packet_access(struct bpf_verifier_env *env, u32 regno, int off,
969bf05e
AS		 732 int size)
733{
58e2af8b
JK		 734 struct bpf_reg_state *regs = env->cur_state.regs;
735 struct bpf_reg_state *reg = &regs[regno];
969bf05e 736
d91b28ed 737 off += reg->off;
b399cf64 738 if (off < 0 || size <= 0 || off + size > reg->range) {
d91b28ed
AS		 739 verbose("invalid access to packet, off=%d size=%d, R%d(id=%d,off=%d,r=%d)\n",
740 off, size, regno, reg->id, reg->off, reg->range);
969bf05e
AS		 741 return -EACCES;
742 }
743 return 0;
744}
745
17a52670 746/* check access to 'struct bpf_context' fields */
31fd8581 747static int check_ctx_access(struct bpf_verifier_env *env, int insn_idx, int off, int size,
19de99f7 748 enum bpf_access_type t, enum bpf_reg_type *reg_type)
17a52670 749{
f96da094
DB		 750 struct bpf_insn_access_aux info = {
751 .reg_type = *reg_type,
752 };
31fd8581 753
13a27dfc
JK		 754 /* for analyzer ctx accesses are already validated and converted */
755 if (env->analyzer_ops)
756 return 0;
757
17a52670 758 if (env->prog->aux->ops->is_valid_access &&
23994631 759 env->prog->aux->ops->is_valid_access(off, size, t, &info)) {
f96da094
DB		 760 /* A non zero info.ctx_field_size indicates that this field is a
761 * candidate for later verifier transformation to load the whole
762 * field and then apply a mask when accessed with a narrower
763 * access than actual ctx access size. A zero info.ctx_field_size
764 * will only allow for whole field access and rejects any other
765 * type of narrower access.
31fd8581 766 */
f96da094 767 env->insn_aux_data[insn_idx].ctx_field_size = info.ctx_field_size;
23994631 768 *reg_type = info.reg_type;
31fd8581 769
32bbe007
AS		 770 /* remember the offset of last byte accessed in ctx */
771 if (env->prog->aux->max_ctx_offset < off + size)
772 env->prog->aux->max_ctx_offset = off + size;
17a52670 773 return 0;
32bbe007 774 }
17a52670
AS		 775
776 verbose("invalid bpf_context access off=%d size=%d\n", off, size);
777 return -EACCES;
778}
779
58e2af8b 780static bool is_pointer_value(struct bpf_verifier_env *env, int regno)
1be7f75d
AS		 781{
782 if (env->allow_ptr_leaks)
783 return false;
784
785 switch (env->cur_state.regs[regno].type) {
786 case UNKNOWN_VALUE:
787 case CONST_IMM:
788 return false;
789 default:
790 return true;
791 }
792}
793
79adffcd 794static int check_pkt_ptr_alignment(const struct bpf_reg_state *reg,
d1174416 795 int off, int size, bool strict)
969bf05e 796{
e07b98d9 797 int ip_align;
d1174416
DM		 798 int reg_off;
799
800 /* Byte size accesses are always allowed. */
801 if (!strict || size == 1)
802 return 0;
803
804 reg_off = reg->off;
805 if (reg->id) {
806 if (reg->aux_off_align % size) {
807 verbose("Packet access is only %u byte aligned, %d byte access not allowed\n",
808 reg->aux_off_align, size);
809 return -EACCES;
810 }
811 reg_off += reg->aux_off;
969bf05e
AS		 812 }
813
e4eda884
DM		 814 /* For platforms that do not have a Kconfig enabling
815 * CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS the value of
816 * NET_IP_ALIGN is universally set to '2'. And on platforms
817 * that do set CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS, we get
818 * to this code only in strict mode where we want to emulate
819 * the NET_IP_ALIGN==2 checking. Therefore use an
820 * unconditional IP align value of '2'.
e07b98d9 821 */
e4eda884 822 ip_align = 2;
e07b98d9 823 if ((ip_align + reg_off + off) % size != 0) {
969bf05e 824 verbose("misaligned packet access off %d+%d+%d size %d\n",
e07b98d9 825 ip_align, reg_off, off, size);
969bf05e
AS		 826 return -EACCES;
827 }
79adffcd 828
969bf05e
AS		 829 return 0;
830}
831
79adffcd 832static int check_val_ptr_alignment(const struct bpf_reg_state *reg,
d1174416 833 int size, bool strict)
79adffcd 834{
d1174416 835 if (strict && size != 1) {
79adffcd
DB		 836 verbose("Unknown alignment. Only byte-sized access allowed in value access.\n");
837 return -EACCES;
838 }
839
969bf05e
AS		 840 return 0;
841}
842
e07b98d9
DM		 843static int check_ptr_alignment(struct bpf_verifier_env *env,
844 const struct bpf_reg_state *reg,
79adffcd
DB		 845 int off, int size)
846{
e07b98d9 847 bool strict = env->strict_alignment;
d1174416 848
79adffcd
DB		 849 switch (reg->type) {
850 case PTR_TO_PACKET:
d1174416 851 return check_pkt_ptr_alignment(reg, off, size, strict);
79adffcd 852 case PTR_TO_MAP_VALUE_ADJ:
d1174416 853 return check_val_ptr_alignment(reg, size, strict);
79adffcd
DB		 854 default:
855 if (off % size != 0) {
856 verbose("misaligned access off %d size %d\n",
857 off, size);
858 return -EACCES;
859 }
860
861 return 0;
862 }
863}
864
17a52670
AS		 865/* check whether memory at (regno + off) is accessible for t = (read | write)
866 * if t==write, value_regno is a register which value is stored into memory
867 * if t==read, value_regno is a register which will receive the value from memory
868 * if t==write && value_regno==-1, some unknown value is stored into memory
869 * if t==read && value_regno==-1, don't care what we read from memory
870 */
31fd8581 871static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno, int off,
17a52670
AS		 872 int bpf_size, enum bpf_access_type t,
873 int value_regno)
874{
58e2af8b
JK		 875 struct bpf_verifier_state *state = &env->cur_state;
876 struct bpf_reg_state *reg = &state->regs[regno];
17a52670
AS		 877 int size, err = 0;
878
1a0dc1ac
AS		 879 if (reg->type == PTR_TO_STACK)
880 off += reg->imm;
24b4d2ab 881
17a52670
AS		 882 size = bpf_size_to_bytes(bpf_size);
883 if (size < 0)
884 return size;
885
e07b98d9 886 err = check_ptr_alignment(env, reg, off, size);
969bf05e
AS		 887 if (err)
888 return err;
17a52670 889
48461135
JB		 890 if (reg->type == PTR_TO_MAP_VALUE ||
891 reg->type == PTR_TO_MAP_VALUE_ADJ) {
1be7f75d
AS		 892 if (t == BPF_WRITE && value_regno >= 0 &&
893 is_pointer_value(env, value_regno)) {
894 verbose("R%d leaks addr into map\n", value_regno);
895 return -EACCES;
896 }
48461135 897
dbcfe5f7
GB		 898 if (reg->type == PTR_TO_MAP_VALUE_ADJ)
899 err = check_map_access_adj(env, regno, off, size);
900 else
901 err = check_map_access(env, regno, off, size);
17a52670 902 if (!err && t == BPF_READ && value_regno >= 0)
f0318d01
GB		 903 mark_reg_unknown_value_and_range(state->regs,
904 value_regno);
17a52670 905
1a0dc1ac 906 } else if (reg->type == PTR_TO_CTX) {
19de99f7
AS		 907 enum bpf_reg_type reg_type = UNKNOWN_VALUE;
908
1be7f75d
AS		 909 if (t == BPF_WRITE && value_regno >= 0 &&
910 is_pointer_value(env, value_regno)) {
911 verbose("R%d leaks addr into ctx\n", value_regno);
912 return -EACCES;
913 }
31fd8581 914 err = check_ctx_access(env, insn_idx, off, size, t, &reg_type);
969bf05e 915 if (!err && t == BPF_READ && value_regno >= 0) {
f0318d01
GB		 916 mark_reg_unknown_value_and_range(state->regs,
917 value_regno);
1955351d
MS		 918 /* note that reg.[id|off|range] == 0 */
919 state->regs[value_regno].type = reg_type;
d1174416
DM		 920 state->regs[value_regno].aux_off = 0;
921 state->regs[value_regno].aux_off_align = 0;
969bf05e 922 }
17a52670 923
1a0dc1ac 924 } else if (reg->type == FRAME_PTR || reg->type == PTR_TO_STACK) {
17a52670
AS		 925 if (off >= 0 || off < -MAX_BPF_STACK) {
926 verbose("invalid stack off=%d size=%d\n", off, size);
927 return -EACCES;
928 }
8726679a
AS		 929
930 if (env->prog->aux->stack_depth < -off)
931 env->prog->aux->stack_depth = -off;
932
1be7f75d
AS		 933 if (t == BPF_WRITE) {
934 if (!env->allow_ptr_leaks &&
935 state->stack_slot_type[MAX_BPF_STACK + off] == STACK_SPILL &&
936 size != BPF_REG_SIZE) {
937 verbose("attempt to corrupt spilled pointer on stack\n");
938 return -EACCES;
939 }
17a52670 940 err = check_stack_write(state, off, size, value_regno);
1be7f75d 941 } else {
17a52670 942 err = check_stack_read(state, off, size, value_regno);
1be7f75d 943 }
969bf05e 944 } else if (state->regs[regno].type == PTR_TO_PACKET) {
3a0af8fd 945 if (t == BPF_WRITE && !may_access_direct_pkt_data(env, NULL, t)) {
969bf05e
AS		 946 verbose("cannot write into packet\n");
947 return -EACCES;
948 }
4acf6c0b
BB		 949 if (t == BPF_WRITE && value_regno >= 0 &&
950 is_pointer_value(env, value_regno)) {
951 verbose("R%d leaks addr into packet\n", value_regno);
952 return -EACCES;
953 }
969bf05e
AS		 954 err = check_packet_access(env, regno, off, size);
955 if (!err && t == BPF_READ && value_regno >= 0)
f0318d01
GB		 956 mark_reg_unknown_value_and_range(state->regs,
957 value_regno);
17a52670
AS		 958 } else {
959 verbose("R%d invalid mem access '%s'\n",
1a0dc1ac 960 regno, reg_type_str[reg->type]);
17a52670
AS		 961 return -EACCES;
962 }
969bf05e
AS		 963
964 if (!err && size <= 2 && value_regno >= 0 && env->allow_ptr_leaks &&
965 state->regs[value_regno].type == UNKNOWN_VALUE) {
966 /* 1 or 2 byte load zero-extends, determine the number of
967 * zero upper bits. Not doing it fo 4 byte load, since
968 * such values cannot be added to ptr_to_packet anyway.
969 */
970 state->regs[value_regno].imm = 64 - size * 8;
971 }
17a52670
AS		 972 return err;
973}
974
31fd8581 975static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn)
17a52670 976{
58e2af8b 977 struct bpf_reg_state *regs = env->cur_state.regs;
17a52670
AS		 978 int err;
979
980 if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
981 insn->imm != 0) {
982 verbose("BPF_XADD uses reserved fields\n");
983 return -EINVAL;
984 }
985
986 /* check src1 operand */
987 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
988 if (err)
989 return err;
990
991 /* check src2 operand */
992 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
993 if (err)
994 return err;
995
6bdf6abc
DB		 996 if (is_pointer_value(env, insn->src_reg)) {
997 verbose("R%d leaks addr into mem\n", insn->src_reg);
998 return -EACCES;
999 }
1000
17a52670 1001 /* check whether atomic_add can read the memory */
31fd8581 1002 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
17a52670
AS		 1003 BPF_SIZE(insn->code), BPF_READ, -1);
1004 if (err)
1005 return err;
1006
1007 /* check whether atomic_add can write into the same memory */
31fd8581 1008 return check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
17a52670
AS		 1009 BPF_SIZE(insn->code), BPF_WRITE, -1);
1010}
1011
1012/* when register 'regno' is passed into function that will read 'access_size'
1013 * bytes from that pointer, make sure that it's within stack boundary
1014 * and all elements of stack are initialized
1015 */
58e2af8b 1016static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
435faee1
DB		 1017 int access_size, bool zero_size_allowed,
1018 struct bpf_call_arg_meta *meta)
17a52670 1019{
58e2af8b
JK		 1020 struct bpf_verifier_state *state = &env->cur_state;
1021 struct bpf_reg_state *regs = state->regs;
17a52670
AS		 1022 int off, i;
1023
8e2fe1d9
DB		 1024 if (regs[regno].type != PTR_TO_STACK) {
1025 if (zero_size_allowed && access_size == 0 &&
1026 regs[regno].type == CONST_IMM &&
1027 regs[regno].imm == 0)
1028 return 0;
1029
1030 verbose("R%d type=%s expected=%s\n", regno,
1031 reg_type_str[regs[regno].type],
1032 reg_type_str[PTR_TO_STACK]);
17a52670 1033 return -EACCES;
8e2fe1d9 1034 }
17a52670
AS		 1035
1036 off = regs[regno].imm;
1037 if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
1038 access_size <= 0) {
1039 verbose("invalid stack type R%d off=%d access_size=%d\n",
1040 regno, off, access_size);
1041 return -EACCES;
1042 }
1043
8726679a
AS		 1044 if (env->prog->aux->stack_depth < -off)
1045 env->prog->aux->stack_depth = -off;
1046
435faee1
DB		 1047 if (meta && meta->raw_mode) {
1048 meta->access_size = access_size;
1049 meta->regno = regno;
1050 return 0;
1051 }
1052
17a52670 1053 for (i = 0; i < access_size; i++) {
9c399760 1054 if (state->stack_slot_type[MAX_BPF_STACK + off + i] != STACK_MISC) {
17a52670
AS		 1055 verbose("invalid indirect read from stack off %d+%d size %d\n",
1056 off, i, access_size);
1057 return -EACCES;
1058 }
1059 }
1060 return 0;
1061}
1062
06c1c049
GB		 1063static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
1064 int access_size, bool zero_size_allowed,
1065 struct bpf_call_arg_meta *meta)
1066{
1067 struct bpf_reg_state *regs = env->cur_state.regs;
1068
1069 switch (regs[regno].type) {
1070 case PTR_TO_PACKET:
1071 return check_packet_access(env, regno, 0, access_size);
1072 case PTR_TO_MAP_VALUE:
1073 return check_map_access(env, regno, 0, access_size);
1074 case PTR_TO_MAP_VALUE_ADJ:
1075 return check_map_access_adj(env, regno, 0, access_size);
1076 default: /* const_imm|ptr_to_stack or invalid ptr */
1077 return check_stack_boundary(env, regno, access_size,
1078 zero_size_allowed, meta);
1079 }
1080}
1081
58e2af8b 1082static int check_func_arg(struct bpf_verifier_env *env, u32 regno,
33ff9823
DB		 1083 enum bpf_arg_type arg_type,
1084 struct bpf_call_arg_meta *meta)
17a52670 1085{
58e2af8b 1086 struct bpf_reg_state *regs = env->cur_state.regs, *reg = &regs[regno];
6841de8b 1087 enum bpf_reg_type expected_type, type = reg->type;
17a52670
AS		 1088 int err = 0;
1089
80f1d68c 1090 if (arg_type == ARG_DONTCARE)
17a52670
AS		 1091 return 0;
1092
6841de8b 1093 if (type == NOT_INIT) {
17a52670
AS		 1094 verbose("R%d !read_ok\n", regno);
1095 return -EACCES;
1096 }
1097
1be7f75d
AS		 1098 if (arg_type == ARG_ANYTHING) {
1099 if (is_pointer_value(env, regno)) {
1100 verbose("R%d leaks addr into helper function\n", regno);
1101 return -EACCES;
1102 }
80f1d68c 1103 return 0;
1be7f75d 1104 }
80f1d68c 1105
3a0af8fd
TG		 1106 if (type == PTR_TO_PACKET &&
1107 !may_access_direct_pkt_data(env, meta, BPF_READ)) {
36bbef52 1108 verbose("helper access to the packet is not allowed\n");
6841de8b
AS		 1109 return -EACCES;
1110 }
1111
8e2fe1d9 1112 if (arg_type == ARG_PTR_TO_MAP_KEY ||
17a52670
AS		 1113 arg_type == ARG_PTR_TO_MAP_VALUE) {
1114 expected_type = PTR_TO_STACK;
6841de8b
AS		 1115 if (type != PTR_TO_PACKET && type != expected_type)
1116 goto err_type;
39f19ebb
AS		 1117 } else if (arg_type == ARG_CONST_SIZE ||
1118 arg_type == ARG_CONST_SIZE_OR_ZERO) {
17a52670 1119 expected_type = CONST_IMM;
06c1c049
GB		 1120 /* One exception. Allow UNKNOWN_VALUE registers when the
1121 * boundaries are known and don't cause unsafe memory accesses
1122 */
1123 if (type != UNKNOWN_VALUE && type != expected_type)
6841de8b 1124 goto err_type;
17a52670
AS		 1125 } else if (arg_type == ARG_CONST_MAP_PTR) {
1126 expected_type = CONST_PTR_TO_MAP;
6841de8b
AS		 1127 if (type != expected_type)
1128 goto err_type;
608cd71a
AS		 1129 } else if (arg_type == ARG_PTR_TO_CTX) {
1130 expected_type = PTR_TO_CTX;
6841de8b
AS		 1131 if (type != expected_type)
1132 goto err_type;
39f19ebb
AS		 1133 } else if (arg_type == ARG_PTR_TO_MEM ||
1134 arg_type == ARG_PTR_TO_UNINIT_MEM) {
8e2fe1d9
DB		 1135 expected_type = PTR_TO_STACK;
1136 /* One exception here. In case function allows for NULL to be
1137 * passed in as argument, it's a CONST_IMM type. Final test
1138 * happens during stack boundary checking.
1139 */
6841de8b
AS		 1140 if (type == CONST_IMM && reg->imm == 0)
1141 /* final test in check_stack_boundary() */;
5722569b
GB		 1142 else if (type != PTR_TO_PACKET && type != PTR_TO_MAP_VALUE &&
1143 type != PTR_TO_MAP_VALUE_ADJ && type != expected_type)
6841de8b 1144 goto err_type;
39f19ebb 1145 meta->raw_mode = arg_type == ARG_PTR_TO_UNINIT_MEM;
17a52670
AS		 1146 } else {
1147 verbose("unsupported arg_type %d\n", arg_type);
1148 return -EFAULT;
1149 }
1150
17a52670
AS		 1151 if (arg_type == ARG_CONST_MAP_PTR) {
1152 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
33ff9823 1153 meta->map_ptr = reg->map_ptr;
17a52670
AS		 1154 } else if (arg_type == ARG_PTR_TO_MAP_KEY) {
1155 /* bpf_map_xxx(..., map_ptr, ..., key) call:
1156 * check that [key, key + map->key_size) are within
1157 * stack limits and initialized
1158 */
33ff9823 1159 if (!meta->map_ptr) {
17a52670
AS		 1160 /* in function declaration map_ptr must come before
1161 * map_key, so that it's verified and known before
1162 * we have to check map_key here. Otherwise it means
1163 * that kernel subsystem misconfigured verifier
1164 */
1165 verbose("invalid map_ptr to access map->key\n");
1166 return -EACCES;
1167 }
6841de8b
AS		 1168 if (type == PTR_TO_PACKET)
1169 err = check_packet_access(env, regno, 0,
1170 meta->map_ptr->key_size);
1171 else
1172 err = check_stack_boundary(env, regno,
1173 meta->map_ptr->key_size,
1174 false, NULL);
17a52670
AS		 1175 } else if (arg_type == ARG_PTR_TO_MAP_VALUE) {
1176 /* bpf_map_xxx(..., map_ptr, ..., value) call:
1177 * check [value, value + map->value_size) validity
1178 */
33ff9823 1179 if (!meta->map_ptr) {
17a52670
AS		 1180 /* kernel subsystem misconfigured verifier */
1181 verbose("invalid map_ptr to access map->value\n");
1182 return -EACCES;
1183 }
6841de8b
AS		 1184 if (type == PTR_TO_PACKET)
1185 err = check_packet_access(env, regno, 0,
1186 meta->map_ptr->value_size);
1187 else
1188 err = check_stack_boundary(env, regno,
1189 meta->map_ptr->value_size,
1190 false, NULL);
39f19ebb
AS		 1191 } else if (arg_type == ARG_CONST_SIZE ||
1192 arg_type == ARG_CONST_SIZE_OR_ZERO) {
1193 bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO);
17a52670 1194
17a52670
AS		 1195 /* bpf_xxx(..., buf, len) call will access 'len' bytes
1196 * from stack pointer 'buf'. Check it
1197 * note: regno == len, regno - 1 == buf
1198 */
1199 if (regno == 0) {
1200 /* kernel subsystem misconfigured verifier */
39f19ebb 1201 verbose("ARG_CONST_SIZE cannot be first argument\n");
17a52670
AS		 1202 return -EACCES;
1203 }
06c1c049
GB		 1204
1205 /* If the register is UNKNOWN_VALUE, the access check happens
1206 * using its boundaries. Otherwise, just use its imm
1207 */
1208 if (type == UNKNOWN_VALUE) {
1209 /* For unprivileged variable accesses, disable raw
1210 * mode so that the program is required to
1211 * initialize all the memory that the helper could
1212 * just partially fill up.
1213 */
1214 meta = NULL;
1215
1216 if (reg->min_value < 0) {
1217 verbose("R%d min value is negative, either use unsigned or 'var &= const'\n",
1218 regno);
1219 return -EACCES;
1220 }
1221
1222 if (reg->min_value == 0) {
1223 err = check_helper_mem_access(env, regno - 1, 0,
1224 zero_size_allowed,
1225 meta);
1226 if (err)
1227 return err;
1228 }
1229
1230 if (reg->max_value == BPF_REGISTER_MAX_RANGE) {
1231 verbose("R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n",
1232 regno);
1233 return -EACCES;
1234 }
1235 err = check_helper_mem_access(env, regno - 1,
1236 reg->max_value,
1237 zero_size_allowed, meta);
1238 if (err)
1239 return err;
1240 } else {
1241 /* register is CONST_IMM */
1242 err = check_helper_mem_access(env, regno - 1, reg->imm,
1243 zero_size_allowed, meta);
1244 }
17a52670
AS		 1245 }
1246
1247 return err;
6841de8b
AS		 1248err_type:
1249 verbose("R%d type=%s expected=%s\n", regno,
1250 reg_type_str[type], reg_type_str[expected_type]);
1251 return -EACCES;
17a52670
AS		 1252}
1253
35578d79
KX		 1254static int check_map_func_compatibility(struct bpf_map *map, int func_id)
1255{
35578d79
KX		 1256 if (!map)
1257 return 0;
1258
6aff67c8
AS		 1259 /* We need a two way check, first is from map perspective ... */
1260 switch (map->map_type) {
1261 case BPF_MAP_TYPE_PROG_ARRAY:
1262 if (func_id != BPF_FUNC_tail_call)
1263 goto error;
1264 break;
1265 case BPF_MAP_TYPE_PERF_EVENT_ARRAY:
1266 if (func_id != BPF_FUNC_perf_event_read &&
1267 func_id != BPF_FUNC_perf_event_output)
1268 goto error;
1269 break;
1270 case BPF_MAP_TYPE_STACK_TRACE:
1271 if (func_id != BPF_FUNC_get_stackid)
1272 goto error;
1273 break;
4ed8ec52 1274 case BPF_MAP_TYPE_CGROUP_ARRAY:
60747ef4 1275 if (func_id != BPF_FUNC_skb_under_cgroup &&
60d20f91 1276 func_id != BPF_FUNC_current_task_under_cgroup)
4a482f34
MKL		 1277 goto error;
1278 break;
56f668df 1279 case BPF_MAP_TYPE_ARRAY_OF_MAPS:
bcc6b1b7 1280 case BPF_MAP_TYPE_HASH_OF_MAPS:
56f668df
MKL		 1281 if (func_id != BPF_FUNC_map_lookup_elem)
1282 goto error;
6aff67c8
AS		 1283 default:
1284 break;
1285 }
1286
1287 /* ... and second from the function itself. */
1288 switch (func_id) {
1289 case BPF_FUNC_tail_call:
1290 if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
1291 goto error;
1292 break;
1293 case BPF_FUNC_perf_event_read:
1294 case BPF_FUNC_perf_event_output:
1295 if (map->map_type != BPF_MAP_TYPE_PERF_EVENT_ARRAY)
1296 goto error;
1297 break;
1298 case BPF_FUNC_get_stackid:
1299 if (map->map_type != BPF_MAP_TYPE_STACK_TRACE)
1300 goto error;
1301 break;
60d20f91 1302 case BPF_FUNC_current_task_under_cgroup:
747ea55e 1303 case BPF_FUNC_skb_under_cgroup:
4a482f34
MKL		 1304 if (map->map_type != BPF_MAP_TYPE_CGROUP_ARRAY)
1305 goto error;
1306 break;
6aff67c8
AS		 1307 default:
1308 break;
35578d79
KX		 1309 }
1310
1311 return 0;
6aff67c8 1312error:
ebb676da
TG		 1313 verbose("cannot pass map_type %d into func %s#%d\n",
1314 map->map_type, func_id_name(func_id), func_id);
6aff67c8 1315 return -EINVAL;
35578d79
KX		 1316}
1317
435faee1
DB		 1318static int check_raw_mode(const struct bpf_func_proto *fn)
1319{
1320 int count = 0;
1321
39f19ebb 1322 if (fn->arg1_type == ARG_PTR_TO_UNINIT_MEM)
435faee1 1323 count++;
39f19ebb 1324 if (fn->arg2_type == ARG_PTR_TO_UNINIT_MEM)
435faee1 1325 count++;
39f19ebb 1326 if (fn->arg3_type == ARG_PTR_TO_UNINIT_MEM)
435faee1 1327 count++;
39f19ebb 1328 if (fn->arg4_type == ARG_PTR_TO_UNINIT_MEM)
435faee1 1329 count++;
39f19ebb 1330 if (fn->arg5_type == ARG_PTR_TO_UNINIT_MEM)
435faee1
DB		 1331 count++;
1332
1333 return count > 1 ? -EINVAL : 0;
1334}
1335
58e2af8b 1336static void clear_all_pkt_pointers(struct bpf_verifier_env *env)
969bf05e 1337{
58e2af8b
JK		 1338 struct bpf_verifier_state *state = &env->cur_state;
1339 struct bpf_reg_state *regs = state->regs, *reg;
969bf05e
AS		 1340 int i;
1341
1342 for (i = 0; i < MAX_BPF_REG; i++)
1343 if (regs[i].type == PTR_TO_PACKET ||
1344 regs[i].type == PTR_TO_PACKET_END)
1345 mark_reg_unknown_value(regs, i);
1346
1347 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
1348 if (state->stack_slot_type[i] != STACK_SPILL)
1349 continue;
1350 reg = &state->spilled_regs[i / BPF_REG_SIZE];
1351 if (reg->type != PTR_TO_PACKET &&
1352 reg->type != PTR_TO_PACKET_END)
1353 continue;
36e24c00
DB		 1354 __mark_reg_unknown_value(state->spilled_regs,
1355 i / BPF_REG_SIZE);
969bf05e
AS		 1356 }
1357}
1358
81ed18ab 1359static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
17a52670 1360{
58e2af8b 1361 struct bpf_verifier_state *state = &env->cur_state;
17a52670 1362 const struct bpf_func_proto *fn = NULL;
58e2af8b 1363 struct bpf_reg_state *regs = state->regs;
33ff9823 1364 struct bpf_call_arg_meta meta;
969bf05e 1365 bool changes_data;
17a52670
AS		 1366 int i, err;
1367
1368 /* find function prototype */
1369 if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
ebb676da 1370 verbose("invalid func %s#%d\n", func_id_name(func_id), func_id);
17a52670
AS		 1371 return -EINVAL;
1372 }
1373
1374 if (env->prog->aux->ops->get_func_proto)
1375 fn = env->prog->aux->ops->get_func_proto(func_id);
1376
1377 if (!fn) {
ebb676da 1378 verbose("unknown func %s#%d\n", func_id_name(func_id), func_id);
17a52670
AS		 1379 return -EINVAL;
1380 }
1381
1382 /* eBPF programs must be GPL compatible to use GPL-ed functions */
24701ece 1383 if (!env->prog->gpl_compatible && fn->gpl_only) {
17a52670
AS		 1384 verbose("cannot call GPL only function from proprietary program\n");
1385 return -EINVAL;
1386 }
1387
17bedab2 1388 changes_data = bpf_helper_changes_pkt_data(fn->func);
969bf05e 1389
33ff9823 1390 memset(&meta, 0, sizeof(meta));
36bbef52 1391 meta.pkt_access = fn->pkt_access;
33ff9823 1392
435faee1
DB		 1393 /* We only support one arg being in raw mode at the moment, which
1394 * is sufficient for the helper functions we have right now.
1395 */
1396 err = check_raw_mode(fn);
1397 if (err) {
ebb676da
TG		 1398 verbose("kernel subsystem misconfigured func %s#%d\n",
1399 func_id_name(func_id), func_id);
435faee1
DB		 1400 return err;
1401 }
1402
17a52670 1403 /* check args */
33ff9823 1404 err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta);
17a52670
AS		 1405 if (err)
1406 return err;
33ff9823 1407 err = check_func_arg(env, BPF_REG_2, fn->arg2_type, &meta);
17a52670
AS		 1408 if (err)
1409 return err;
33ff9823 1410 err = check_func_arg(env, BPF_REG_3, fn->arg3_type, &meta);
17a52670
AS		 1411 if (err)
1412 return err;
33ff9823 1413 err = check_func_arg(env, BPF_REG_4, fn->arg4_type, &meta);
17a52670
AS		 1414 if (err)
1415 return err;
33ff9823 1416 err = check_func_arg(env, BPF_REG_5, fn->arg5_type, &meta);
17a52670
AS		 1417 if (err)
1418 return err;
1419
435faee1
DB		 1420 /* Mark slots with STACK_MISC in case of raw mode, stack offset
1421 * is inferred from register state.
1422 */
1423 for (i = 0; i < meta.access_size; i++) {
31fd8581 1424 err = check_mem_access(env, insn_idx, meta.regno, i, BPF_B, BPF_WRITE, -1);
435faee1
DB		 1425 if (err)
1426 return err;
1427 }
1428
17a52670 1429 /* reset caller saved regs */
a9789ef9
DB		 1430 for (i = 0; i < CALLER_SAVED_REGS; i++)
1431 mark_reg_not_init(regs, caller_saved[i]);
17a52670
AS		 1432
1433 /* update return register */
1434 if (fn->ret_type == RET_INTEGER) {
1435 regs[BPF_REG_0].type = UNKNOWN_VALUE;
1436 } else if (fn->ret_type == RET_VOID) {
1437 regs[BPF_REG_0].type = NOT_INIT;
1438 } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) {
fad73a1a
MKL		 1439 struct bpf_insn_aux_data *insn_aux;
1440
17a52670 1441 regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL;
48461135 1442 regs[BPF_REG_0].max_value = regs[BPF_REG_0].min_value = 0;
17a52670
AS		 1443 /* remember map_ptr, so that check_map_access()
1444 * can check 'value_size' boundary of memory access
1445 * to map element returned from bpf_map_lookup_elem()
1446 */
33ff9823 1447 if (meta.map_ptr == NULL) {
17a52670
AS		 1448 verbose("kernel subsystem misconfigured verifier\n");
1449 return -EINVAL;
1450 }
33ff9823 1451 regs[BPF_REG_0].map_ptr = meta.map_ptr;
57a09bf0 1452 regs[BPF_REG_0].id = ++env->id_gen;
fad73a1a
MKL		 1453 insn_aux = &env->insn_aux_data[insn_idx];
1454 if (!insn_aux->map_ptr)
1455 insn_aux->map_ptr = meta.map_ptr;
1456 else if (insn_aux->map_ptr != meta.map_ptr)
1457 insn_aux->map_ptr = BPF_MAP_PTR_POISON;
17a52670 1458 } else {
ebb676da
TG		 1459 verbose("unknown return type %d of func %s#%d\n",
1460 fn->ret_type, func_id_name(func_id), func_id);
17a52670
AS		 1461 return -EINVAL;
1462 }
04fd61ab 1463
33ff9823 1464 err = check_map_func_compatibility(meta.map_ptr, func_id);
35578d79
KX		 1465 if (err)
1466 return err;
04fd61ab 1467
969bf05e
AS		 1468 if (changes_data)
1469 clear_all_pkt_pointers(env);
1470 return 0;
1471}
1472
58e2af8b
JK		 1473static int check_packet_ptr_add(struct bpf_verifier_env *env,
1474 struct bpf_insn *insn)
969bf05e 1475{
58e2af8b
JK		 1476 struct bpf_reg_state *regs = env->cur_state.regs;
1477 struct bpf_reg_state *dst_reg = &regs[insn->dst_reg];
1478 struct bpf_reg_state *src_reg = &regs[insn->src_reg];
1479 struct bpf_reg_state tmp_reg;
969bf05e
AS		 1480 s32 imm;
1481
1482 if (BPF_SRC(insn->code) == BPF_K) {
1483 /* pkt_ptr += imm */
1484 imm = insn->imm;
1485
1486add_imm:
63dfef75 1487 if (imm < 0) {
969bf05e
AS		 1488 verbose("addition of negative constant to packet pointer is not allowed\n");
1489 return -EACCES;
1490 }
1491 if (imm >= MAX_PACKET_OFF ||
1492 imm + dst_reg->off >= MAX_PACKET_OFF) {
1493 verbose("constant %d is too large to add to packet pointer\n",
1494 imm);
1495 return -EACCES;
1496 }
1497 /* a constant was added to pkt_ptr.
1498 * Remember it while keeping the same 'id'
1499 */
1500 dst_reg->off += imm;
1501 } else {
d1174416
DM		 1502 bool had_id;
1503
1b9b69ec
AS		 1504 if (src_reg->type == PTR_TO_PACKET) {
1505 /* R6=pkt(id=0,off=0,r=62) R7=imm22; r7 += r6 */
1506 tmp_reg = *dst_reg; /* save r7 state */
1507 *dst_reg = *src_reg; /* copy pkt_ptr state r6 into r7 */
1508 src_reg = &tmp_reg; /* pretend it's src_reg state */
1509 /* if the checks below reject it, the copy won't matter,
1510 * since we're rejecting the whole program. If all ok,
1511 * then imm22 state will be added to r7
1512 * and r7 will be pkt(id=0,off=22,r=62) while
1513 * r6 will stay as pkt(id=0,off=0,r=62)
1514 */
1515 }
1516
969bf05e
AS		 1517 if (src_reg->type == CONST_IMM) {
1518 /* pkt_ptr += reg where reg is known constant */
1519 imm = src_reg->imm;
1520 goto add_imm;
1521 }
1522 /* disallow pkt_ptr += reg
1523 * if reg is not uknown_value with guaranteed zero upper bits
1524 * otherwise pkt_ptr may overflow and addition will become
1525 * subtraction which is not allowed
1526 */
1527 if (src_reg->type != UNKNOWN_VALUE) {
1528 verbose("cannot add '%s' to ptr_to_packet\n",
1529 reg_type_str[src_reg->type]);
1530 return -EACCES;
1531 }
1532 if (src_reg->imm < 48) {
1533 verbose("cannot add integer value with %lld upper zero bits to ptr_to_packet\n",
1534 src_reg->imm);
1535 return -EACCES;
1536 }
d1174416
DM		 1537
1538 had_id = (dst_reg->id != 0);
1539
969bf05e
AS		 1540 /* dst_reg stays as pkt_ptr type and since some positive
1541 * integer value was added to the pointer, increment its 'id'
1542 */
1f415a74 1543 dst_reg->id = ++env->id_gen;
969bf05e 1544
d1174416 1545 /* something was added to pkt_ptr, set range to zero */
6832a333 1546 dst_reg->aux_off += dst_reg->off;
969bf05e
AS		 1547 dst_reg->off = 0;
1548 dst_reg->range = 0;
d1174416
DM		 1549 if (had_id)
1550 dst_reg->aux_off_align = min(dst_reg->aux_off_align,
1551 src_reg->min_align);
1552 else
1553 dst_reg->aux_off_align = src_reg->min_align;
969bf05e
AS		 1554 }
1555 return 0;
1556}
1557
58e2af8b 1558static int evaluate_reg_alu(struct bpf_verifier_env *env, struct bpf_insn *insn)
969bf05e 1559{
58e2af8b
JK		 1560 struct bpf_reg_state *regs = env->cur_state.regs;
1561 struct bpf_reg_state *dst_reg = &regs[insn->dst_reg];
969bf05e
AS		 1562 u8 opcode = BPF_OP(insn->code);
1563 s64 imm_log2;
1564
1565 /* for type == UNKNOWN_VALUE:
1566 * imm > 0 -> number of zero upper bits
1567 * imm == 0 -> don't track which is the same as all bits can be non-zero
1568 */
1569
1570 if (BPF_SRC(insn->code) == BPF_X) {
58e2af8b 1571 struct bpf_reg_state *src_reg = &regs[insn->src_reg];
969bf05e
AS		 1572
1573 if (src_reg->type == UNKNOWN_VALUE && src_reg->imm > 0 &&
1574 dst_reg->imm && opcode == BPF_ADD) {
1575 /* dreg += sreg
1576 * where both have zero upper bits. Adding them
1577 * can only result making one more bit non-zero
1578 * in the larger value.
1579 * Ex. 0xffff (imm=48) + 1 (imm=63) = 0x10000 (imm=47)
1580 * 0xffff (imm=48) + 0xffff = 0x1fffe (imm=47)
1581 */
1582 dst_reg->imm = min(dst_reg->imm, src_reg->imm);
1583 dst_reg->imm--;
1584 return 0;
1585 }
1586 if (src_reg->type == CONST_IMM && src_reg->imm > 0 &&
1587 dst_reg->imm && opcode == BPF_ADD) {
1588 /* dreg += sreg
1589 * where dreg has zero upper bits and sreg is const.
1590 * Adding them can only result making one more bit
1591 * non-zero in the larger value.
1592 */
1593 imm_log2 = __ilog2_u64((long long)src_reg->imm);
1594 dst_reg->imm = min(dst_reg->imm, 63 - imm_log2);
1595 dst_reg->imm--;
1596 return 0;
1597 }
1598 /* all other cases non supported yet, just mark dst_reg */
1599 dst_reg->imm = 0;
1600 return 0;
1601 }
1602
1603 /* sign extend 32-bit imm into 64-bit to make sure that
1604 * negative values occupy bit 63. Note ilog2() would have
1605 * been incorrect, since sizeof(insn->imm) == 4
1606 */
1607 imm_log2 = __ilog2_u64((long long)insn->imm);
1608
1609 if (dst_reg->imm && opcode == BPF_LSH) {
1610 /* reg <<= imm
1611 * if reg was a result of 2 byte load, then its imm == 48
1612 * which means that upper 48 bits are zero and shifting this reg
1613 * left by 4 would mean that upper 44 bits are still zero
1614 */
1615 dst_reg->imm -= insn->imm;
1616 } else if (dst_reg->imm && opcode == BPF_MUL) {
1617 /* reg *= imm
1618 * if multiplying by 14 subtract 4
1619 * This is conservative calculation of upper zero bits.
1620 * It's not trying to special case insn->imm == 1 or 0 cases
1621 */
1622 dst_reg->imm -= imm_log2 + 1;
1623 } else if (opcode == BPF_AND) {
1624 /* reg &= imm */
1625 dst_reg->imm = 63 - imm_log2;
1626 } else if (dst_reg->imm && opcode == BPF_ADD) {
1627 /* reg += imm */
1628 dst_reg->imm = min(dst_reg->imm, 63 - imm_log2);
1629 dst_reg->imm--;
1630 } else if (opcode == BPF_RSH) {
1631 /* reg >>= imm
1632 * which means that after right shift, upper bits will be zero
1633 * note that verifier already checked that
1634 * 0 <= imm < 64 for shift insn
1635 */
1636 dst_reg->imm += insn->imm;
1637 if (unlikely(dst_reg->imm > 64))
1638 /* some dumb code did:
1639 * r2 = *(u32 *)mem;
1640 * r2 >>= 32;
1641 * and all bits are zero now */
1642 dst_reg->imm = 64;
1643 } else {
1644 /* all other alu ops, means that we don't know what will
1645 * happen to the value, mark it with unknown number of zero bits
1646 */
1647 dst_reg->imm = 0;
1648 }
1649
1650 if (dst_reg->imm < 0) {
1651 /* all 64 bits of the register can contain non-zero bits
1652 * and such value cannot be added to ptr_to_packet, since it
1653 * may overflow, mark it as unknown to avoid further eval
1654 */
1655 dst_reg->imm = 0;
1656 }
1657 return 0;
1658}
1659
58e2af8b
JK		 1660static int evaluate_reg_imm_alu(struct bpf_verifier_env *env,
1661 struct bpf_insn *insn)
969bf05e 1662{
58e2af8b
JK		 1663 struct bpf_reg_state *regs = env->cur_state.regs;
1664 struct bpf_reg_state *dst_reg = &regs[insn->dst_reg];
1665 struct bpf_reg_state *src_reg = &regs[insn->src_reg];
969bf05e 1666 u8 opcode = BPF_OP(insn->code);
3fadc801 1667 u64 dst_imm = dst_reg->imm;
969bf05e 1668
3fadc801
DB		 1669 /* dst_reg->type == CONST_IMM here. Simulate execution of insns
1670 * containing ALU ops. Don't care about overflow or negative
1671 * values, just add/sub/... them; registers are in u64.
969bf05e 1672 */
3fadc801
DB		 1673 if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_K) {
1674 dst_imm += insn->imm;
1675 } else if (opcode == BPF_ADD && BPF_SRC(insn->code) == BPF_X &&
1676 src_reg->type == CONST_IMM) {
1677 dst_imm += src_reg->imm;
1678 } else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_K) {
1679 dst_imm -= insn->imm;
1680 } else if (opcode == BPF_SUB && BPF_SRC(insn->code) == BPF_X &&
1681 src_reg->type == CONST_IMM) {
1682 dst_imm -= src_reg->imm;
1683 } else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_K) {
1684 dst_imm *= insn->imm;
1685 } else if (opcode == BPF_MUL && BPF_SRC(insn->code) == BPF_X &&
1686 src_reg->type == CONST_IMM) {
1687 dst_imm *= src_reg->imm;
1688 } else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_K) {
1689 dst_imm |= insn->imm;
1690 } else if (opcode == BPF_OR && BPF_SRC(insn->code) == BPF_X &&
1691 src_reg->type == CONST_IMM) {
1692 dst_imm |= src_reg->imm;
1693 } else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_K) {
1694 dst_imm &= insn->imm;
1695 } else if (opcode == BPF_AND && BPF_SRC(insn->code) == BPF_X &&
1696 src_reg->type == CONST_IMM) {
1697 dst_imm &= src_reg->imm;
1698 } else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_K) {
1699 dst_imm >>= insn->imm;
1700 } else if (opcode == BPF_RSH && BPF_SRC(insn->code) == BPF_X &&
1701 src_reg->type == CONST_IMM) {
1702 dst_imm >>= src_reg->imm;
1703 } else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_K) {
1704 dst_imm <<= insn->imm;
1705 } else if (opcode == BPF_LSH && BPF_SRC(insn->code) == BPF_X &&
1706 src_reg->type == CONST_IMM) {
1707 dst_imm <<= src_reg->imm;
1708 } else {
969bf05e 1709 mark_reg_unknown_value(regs, insn->dst_reg);
3fadc801
DB		 1710 goto out;
1711 }
1712
1713 dst_reg->imm = dst_imm;
1714out:
17a52670
AS		 1715 return 0;
1716}
1717
48461135
JB		 1718static void check_reg_overflow(struct bpf_reg_state *reg)
1719{
1720 if (reg->max_value > BPF_REGISTER_MAX_RANGE)
1721 reg->max_value = BPF_REGISTER_MAX_RANGE;
f23cc643
JB		 1722 if (reg->min_value < BPF_REGISTER_MIN_RANGE ||
1723 reg->min_value > BPF_REGISTER_MAX_RANGE)
48461135
JB		 1724 reg->min_value = BPF_REGISTER_MIN_RANGE;
1725}
1726
d1174416
DM		 1727static u32 calc_align(u32 imm)
1728{
1729 if (!imm)
1730 return 1U << 31;
1731 return imm - ((imm - 1) & imm);
1732}
1733
48461135
JB		 1734static void adjust_reg_min_max_vals(struct bpf_verifier_env *env,
1735 struct bpf_insn *insn)
1736{
1737 struct bpf_reg_state *regs = env->cur_state.regs, *dst_reg;
f23cc643
JB		 1738 s64 min_val = BPF_REGISTER_MIN_RANGE;
1739 u64 max_val = BPF_REGISTER_MAX_RANGE;
48461135 1740 u8 opcode = BPF_OP(insn->code);
d1174416 1741 u32 dst_align, src_align;
48461135
JB		 1742
1743 dst_reg = &regs[insn->dst_reg];
d1174416 1744 src_align = 0;
48461135
JB		 1745 if (BPF_SRC(insn->code) == BPF_X) {
1746 check_reg_overflow(&regs[insn->src_reg]);
1747 min_val = regs[insn->src_reg].min_value;
1748 max_val = regs[insn->src_reg].max_value;
1749
1750 /* If the source register is a random pointer then the
1751 * min_value/max_value values represent the range of the known
1752 * accesses into that value, not the actual min/max value of the
1753 * register itself. In this case we have to reset the reg range
1754 * values so we know it is not safe to look at.
1755 */
1756 if (regs[insn->src_reg].type != CONST_IMM &&
1757 regs[insn->src_reg].type != UNKNOWN_VALUE) {
1758 min_val = BPF_REGISTER_MIN_RANGE;
1759 max_val = BPF_REGISTER_MAX_RANGE;
d1174416
DM		 1760 src_align = 0;
1761 } else {
1762 src_align = regs[insn->src_reg].min_align;
48461135
JB		 1763 }
1764 } else if (insn->imm < BPF_REGISTER_MAX_RANGE &&
1765 (s64)insn->imm > BPF_REGISTER_MIN_RANGE) {
1766 min_val = max_val = insn->imm;
d1174416 1767 src_align = calc_align(insn->imm);
48461135
JB		 1768 }
1769
d1174416
DM		 1770 dst_align = dst_reg->min_align;
1771
48461135
JB		 1772 /* We don't know anything about what was done to this register, mark it
1773 * as unknown.
1774 */
1775 if (min_val == BPF_REGISTER_MIN_RANGE &&
1776 max_val == BPF_REGISTER_MAX_RANGE) {
1777 reset_reg_range_values(regs, insn->dst_reg);
1778 return;
1779 }
1780
f23cc643
JB		 1781 /* If one of our values was at the end of our ranges then we can't just
1782 * do our normal operations to the register, we need to set the values
1783 * to the min/max since they are undefined.
1784 */
1785 if (min_val == BPF_REGISTER_MIN_RANGE)
1786 dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
1787 if (max_val == BPF_REGISTER_MAX_RANGE)
1788 dst_reg->max_value = BPF_REGISTER_MAX_RANGE;
1789
48461135
JB		 1790 switch (opcode) {
1791 case BPF_ADD:
f23cc643
JB		 1792 if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
1793 dst_reg->min_value += min_val;
1794 if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
1795 dst_reg->max_value += max_val;
d1174416 1796 dst_reg->min_align = min(src_align, dst_align);
48461135
JB		 1797 break;
1798 case BPF_SUB:
f23cc643
JB		 1799 if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
1800 dst_reg->min_value -= min_val;
1801 if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
1802 dst_reg->max_value -= max_val;
d1174416 1803 dst_reg->min_align = min(src_align, dst_align);
48461135
JB		 1804 break;
1805 case BPF_MUL:
f23cc643
JB		 1806 if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
1807 dst_reg->min_value *= min_val;
1808 if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
1809 dst_reg->max_value *= max_val;
d1174416 1810 dst_reg->min_align = max(src_align, dst_align);
48461135
JB		 1811 break;
1812 case BPF_AND:
f23cc643
JB		 1813 /* Disallow AND'ing of negative numbers, ain't nobody got time
1814 * for that. Otherwise the minimum is 0 and the max is the max
1815 * value we could AND against.
1816 */
1817 if (min_val < 0)
1818 dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
1819 else
1820 dst_reg->min_value = 0;
48461135 1821 dst_reg->max_value = max_val;
d1174416 1822 dst_reg->min_align = max(src_align, dst_align);
48461135
JB		 1823 break;
1824 case BPF_LSH:
1825 /* Gotta have special overflow logic here, if we're shifting
1826 * more than MAX_RANGE then just assume we have an invalid
1827 * range.
1828 */
d1174416 1829 if (min_val > ilog2(BPF_REGISTER_MAX_RANGE)) {
48461135 1830 dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
d1174416
DM		 1831 dst_reg->min_align = 1;
1832 } else {
1833 if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE)
1834 dst_reg->min_value <<= min_val;
1835 if (!dst_reg->min_align)
1836 dst_reg->min_align = 1;
1837 dst_reg->min_align <<= min_val;
1838 }
48461135
JB		 1839 if (max_val > ilog2(BPF_REGISTER_MAX_RANGE))
1840 dst_reg->max_value = BPF_REGISTER_MAX_RANGE;
f23cc643 1841 else if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
48461135
JB		 1842 dst_reg->max_value <<= max_val;
1843 break;
1844 case BPF_RSH:
f23cc643
JB		 1845 /* RSH by a negative number is undefined, and the BPF_RSH is an
1846 * unsigned shift, so make the appropriate casts.
48461135 1847 */
d1174416 1848 if (min_val < 0 || dst_reg->min_value < 0) {
f23cc643 1849 dst_reg->min_value = BPF_REGISTER_MIN_RANGE;
d1174416 1850 } else {
f23cc643
JB		 1851 dst_reg->min_value =
1852 (u64)(dst_reg->min_value) >> min_val;
d1174416
DM		 1853 }
1854 if (min_val < 0) {
1855 dst_reg->min_align = 1;
1856 } else {
1857 dst_reg->min_align >>= (u64) min_val;
1858 if (!dst_reg->min_align)
1859 dst_reg->min_align = 1;
1860 }
f23cc643
JB		 1861 if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE)
1862 dst_reg->max_value >>= max_val;
48461135
JB		 1863 break;
1864 default:
1865 reset_reg_range_values(regs, insn->dst_reg);
1866 break;
1867 }
1868
1869 check_reg_overflow(dst_reg);
1870}
1871
17a52670 1872/* check validity of 32-bit and 64-bit arithmetic operations */
58e2af8b 1873static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
17a52670 1874{
58e2af8b 1875 struct bpf_reg_state *regs = env->cur_state.regs, *dst_reg;
17a52670
AS		 1876 u8 opcode = BPF_OP(insn->code);
1877 int err;
1878
1879 if (opcode == BPF_END || opcode == BPF_NEG) {
1880 if (opcode == BPF_NEG) {
1881 if (BPF_SRC(insn->code) != 0 ||
1882 insn->src_reg != BPF_REG_0 ||
1883 insn->off != 0 || insn->imm != 0) {
1884 verbose("BPF_NEG uses reserved fields\n");
1885 return -EINVAL;
1886 }
1887 } else {
1888 if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
1889 (insn->imm != 16 && insn->imm != 32 && insn->imm != 64)) {
1890 verbose("BPF_END uses reserved fields\n");
1891 return -EINVAL;
1892 }
1893 }
1894
1895 /* check src operand */
1896 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1897 if (err)
1898 return err;
1899
1be7f75d
AS		 1900 if (is_pointer_value(env, insn->dst_reg)) {
1901 verbose("R%d pointer arithmetic prohibited\n",
1902 insn->dst_reg);
1903 return -EACCES;
1904 }
1905
17a52670
AS		 1906 /* check dest operand */
1907 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1908 if (err)
1909 return err;
1910
1911 } else if (opcode == BPF_MOV) {
1912
1913 if (BPF_SRC(insn->code) == BPF_X) {
1914 if (insn->imm != 0 || insn->off != 0) {
1915 verbose("BPF_MOV uses reserved fields\n");
1916 return -EINVAL;
1917 }
1918
1919 /* check src operand */
1920 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1921 if (err)
1922 return err;
1923 } else {
1924 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
1925 verbose("BPF_MOV uses reserved fields\n");
1926 return -EINVAL;
1927 }
1928 }
1929
1930 /* check dest operand */
1931 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
1932 if (err)
1933 return err;
1934
48461135
JB		 1935 /* we are setting our register to something new, we need to
1936 * reset its range values.
1937 */
1938 reset_reg_range_values(regs, insn->dst_reg);
1939
17a52670
AS		 1940 if (BPF_SRC(insn->code) == BPF_X) {
1941 if (BPF_CLASS(insn->code) == BPF_ALU64) {
1942 /* case: R1 = R2
1943 * copy register state to dest reg
1944 */
1945 regs[insn->dst_reg] = regs[insn->src_reg];
1946 } else {
1be7f75d
AS		 1947 if (is_pointer_value(env, insn->src_reg)) {
1948 verbose("R%d partial copy of pointer\n",
1949 insn->src_reg);
1950 return -EACCES;
1951 }
57a09bf0 1952 mark_reg_unknown_value(regs, insn->dst_reg);
17a52670
AS		 1953 }
1954 } else {
1955 /* case: R = imm
1956 * remember the value we stored into this reg
1957 */
1958 regs[insn->dst_reg].type = CONST_IMM;
1959 regs[insn->dst_reg].imm = insn->imm;
4a2ff55a 1960 regs[insn->dst_reg].id = 0;
48461135
JB		 1961 regs[insn->dst_reg].max_value = insn->imm;
1962 regs[insn->dst_reg].min_value = insn->imm;
d1174416 1963 regs[insn->dst_reg].min_align = calc_align(insn->imm);
17a52670
AS		 1964 }
1965
1966 } else if (opcode > BPF_END) {
1967 verbose("invalid BPF_ALU opcode %x\n", opcode);
1968 return -EINVAL;
1969
1970 } else { /* all other ALU ops: and, sub, xor, add, ... */
1971
17a52670
AS		 1972 if (BPF_SRC(insn->code) == BPF_X) {
1973 if (insn->imm != 0 || insn->off != 0) {
1974 verbose("BPF_ALU uses reserved fields\n");
1975 return -EINVAL;
1976 }
1977 /* check src1 operand */
1978 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
1979 if (err)
1980 return err;
1981 } else {
1982 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
1983 verbose("BPF_ALU uses reserved fields\n");
1984 return -EINVAL;
1985 }
1986 }
1987
1988 /* check src2 operand */
1989 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
1990 if (err)
1991 return err;
1992
1993 if ((opcode == BPF_MOD || opcode == BPF_DIV) &&
1994 BPF_SRC(insn->code) == BPF_K && insn->imm == 0) {
1995 verbose("div by zero\n");
1996 return -EINVAL;
1997 }
1998
229394e8
RV		 1999 if ((opcode == BPF_LSH || opcode == BPF_RSH ||
2000 opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
2001 int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
2002
2003 if (insn->imm < 0 || insn->imm >= size) {
2004 verbose("invalid shift %d\n", insn->imm);
2005 return -EINVAL;
2006 }
2007 }
2008
1a0dc1ac
AS		 2009 /* check dest operand */
2010 err = check_reg_arg(regs, insn->dst_reg, DST_OP_NO_MARK);
2011 if (err)
2012 return err;
2013
2014 dst_reg = &regs[insn->dst_reg];
2015
48461135
JB		 2016 /* first we want to adjust our ranges. */
2017 adjust_reg_min_max_vals(env, insn);
2018
17a52670
AS		 2019 /* pattern match 'bpf_add Rx, imm' instruction */
2020 if (opcode == BPF_ADD && BPF_CLASS(insn->code) == BPF_ALU64 &&
1a0dc1ac
AS		 2021 dst_reg->type == FRAME_PTR && BPF_SRC(insn->code) == BPF_K) {
2022 dst_reg->type = PTR_TO_STACK;
2023 dst_reg->imm = insn->imm;
2024 return 0;
332270fd
YS		 2025 } else if (opcode == BPF_ADD &&
2026 BPF_CLASS(insn->code) == BPF_ALU64 &&
2027 dst_reg->type == PTR_TO_STACK &&
2028 ((BPF_SRC(insn->code) == BPF_X &&
2029 regs[insn->src_reg].type == CONST_IMM) ||
2030 BPF_SRC(insn->code) == BPF_K)) {
2031 if (BPF_SRC(insn->code) == BPF_X)
2032 dst_reg->imm += regs[insn->src_reg].imm;
2033 else
2034 dst_reg->imm += insn->imm;
2035 return 0;
969bf05e
AS		 2036 } else if (opcode == BPF_ADD &&
2037 BPF_CLASS(insn->code) == BPF_ALU64 &&
1b9b69ec
AS		 2038 (dst_reg->type == PTR_TO_PACKET ||
2039 (BPF_SRC(insn->code) == BPF_X &&
2040 regs[insn->src_reg].type == PTR_TO_PACKET))) {
969bf05e
AS		 2041 /* ptr_to_packet += K|X */
2042 return check_packet_ptr_add(env, insn);
2043 } else if (BPF_CLASS(insn->code) == BPF_ALU64 &&
2044 dst_reg->type == UNKNOWN_VALUE &&
2045 env->allow_ptr_leaks) {
2046 /* unknown += K|X */
2047 return evaluate_reg_alu(env, insn);
2048 } else if (BPF_CLASS(insn->code) == BPF_ALU64 &&
2049 dst_reg->type == CONST_IMM &&
2050 env->allow_ptr_leaks) {
2051 /* reg_imm += K|X */
2052 return evaluate_reg_imm_alu(env, insn);
1be7f75d
AS		 2053 } else if (is_pointer_value(env, insn->dst_reg)) {
2054 verbose("R%d pointer arithmetic prohibited\n",
2055 insn->dst_reg);
2056 return -EACCES;
2057 } else if (BPF_SRC(insn->code) == BPF_X &&
2058 is_pointer_value(env, insn->src_reg)) {
2059 verbose("R%d pointer arithmetic prohibited\n",
2060 insn->src_reg);
2061 return -EACCES;
2062 }
17a52670 2063
48461135
JB		 2064 /* If we did pointer math on a map value then just set it to our
2065 * PTR_TO_MAP_VALUE_ADJ type so we can deal with any stores or
2066 * loads to this register appropriately, otherwise just mark the
2067 * register as unknown.
2068 */
2069 if (env->allow_ptr_leaks &&
fce366a9 2070 BPF_CLASS(insn->code) == BPF_ALU64 && opcode == BPF_ADD &&
48461135
JB		 2071 (dst_reg->type == PTR_TO_MAP_VALUE ||
2072 dst_reg->type == PTR_TO_MAP_VALUE_ADJ))
2073 dst_reg->type = PTR_TO_MAP_VALUE_ADJ;
2074 else
2075 mark_reg_unknown_value(regs, insn->dst_reg);
17a52670
AS		 2076 }
2077
2078 return 0;
2079}
2080
58e2af8b
JK		 2081static void find_good_pkt_pointers(struct bpf_verifier_state *state,
2082 struct bpf_reg_state *dst_reg)
969bf05e 2083{
58e2af8b 2084 struct bpf_reg_state *regs = state->regs, *reg;
969bf05e 2085 int i;
2d2be8ca
DB		 2086
2087 /* LLVM can generate two kind of checks:
2088 *
2089 * Type 1:
2090 *
2091 * r2 = r3;
2092 * r2 += 8;
2093 * if (r2 > pkt_end) goto <handle exception>
2094 * <access okay>
2095 *
2096 * Where:
2097 * r2 == dst_reg, pkt_end == src_reg
2098 * r2=pkt(id=n,off=8,r=0)
2099 * r3=pkt(id=n,off=0,r=0)
2100 *
2101 * Type 2:
2102 *
2103 * r2 = r3;
2104 * r2 += 8;
2105 * if (pkt_end >= r2) goto <access okay>
2106 * <handle exception>
2107 *
2108 * Where:
2109 * pkt_end == dst_reg, r2 == src_reg
2110 * r2=pkt(id=n,off=8,r=0)
2111 * r3=pkt(id=n,off=0,r=0)
2112 *
2113 * Find register r3 and mark its range as r3=pkt(id=n,off=0,r=8)
2114 * so that range of bytes [r3, r3 + 8) is safe to access.
969bf05e 2115 */
2d2be8ca 2116
969bf05e
AS		 2117 for (i = 0; i < MAX_BPF_REG; i++)
2118 if (regs[i].type == PTR_TO_PACKET && regs[i].id == dst_reg->id)
b1977682
AS		 2119 /* keep the maximum range already checked */
2120 regs[i].range = max(regs[i].range, dst_reg->off);
969bf05e
AS		 2121
2122 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
2123 if (state->stack_slot_type[i] != STACK_SPILL)
2124 continue;
2125 reg = &state->spilled_regs[i / BPF_REG_SIZE];
2126 if (reg->type == PTR_TO_PACKET && reg->id == dst_reg->id)
b1977682 2127 reg->range = max(reg->range, dst_reg->off);
969bf05e
AS		 2128 }
2129}
2130
48461135
JB		 2131/* Adjusts the register min/max values in the case that the dst_reg is the
2132 * variable register that we are working on, and src_reg is a constant or we're
2133 * simply doing a BPF_K check.
2134 */
2135static void reg_set_min_max(struct bpf_reg_state *true_reg,
2136 struct bpf_reg_state *false_reg, u64 val,
2137 u8 opcode)
2138{
2139 switch (opcode) {
2140 case BPF_JEQ:
2141 /* If this is false then we know nothing Jon Snow, but if it is
2142 * true then we know for sure.
2143 */
2144 true_reg->max_value = true_reg->min_value = val;
2145 break;
2146 case BPF_JNE:
2147 /* If this is true we know nothing Jon Snow, but if it is false
2148 * we know the value for sure;
2149 */
2150 false_reg->max_value = false_reg->min_value = val;
2151 break;
2152 case BPF_JGT:
2153 /* Unsigned comparison, the minimum value is 0. */
2154 false_reg->min_value = 0;
7e57fbb2 2155 /* fallthrough */
48461135
JB		 2156 case BPF_JSGT:
2157 /* If this is false then we know the maximum val is val,
2158 * otherwise we know the min val is val+1.
2159 */
2160 false_reg->max_value = val;
2161 true_reg->min_value = val + 1;
2162 break;
2163 case BPF_JGE:
2164 /* Unsigned comparison, the minimum value is 0. */
2165 false_reg->min_value = 0;
7e57fbb2 2166 /* fallthrough */
48461135
JB		 2167 case BPF_JSGE:
2168 /* If this is false then we know the maximum value is val - 1,
2169 * otherwise we know the mimimum value is val.
2170 */
2171 false_reg->max_value = val - 1;
2172 true_reg->min_value = val;
2173 break;
2174 default:
2175 break;
2176 }
2177
2178 check_reg_overflow(false_reg);
2179 check_reg_overflow(true_reg);
2180}
2181
2182/* Same as above, but for the case that dst_reg is a CONST_IMM reg and src_reg
2183 * is the variable reg.
2184 */
2185static void reg_set_min_max_inv(struct bpf_reg_state *true_reg,
2186 struct bpf_reg_state *false_reg, u64 val,
2187 u8 opcode)
2188{
2189 switch (opcode) {
2190 case BPF_JEQ:
2191 /* If this is false then we know nothing Jon Snow, but if it is
2192 * true then we know for sure.
2193 */
2194 true_reg->max_value = true_reg->min_value = val;
2195 break;
2196 case BPF_JNE:
2197 /* If this is true we know nothing Jon Snow, but if it is false
2198 * we know the value for sure;
2199 */
2200 false_reg->max_value = false_reg->min_value = val;
2201 break;
2202 case BPF_JGT:
2203 /* Unsigned comparison, the minimum value is 0. */
2204 true_reg->min_value = 0;
7e57fbb2 2205 /* fallthrough */
48461135
JB		 2206 case BPF_JSGT:
2207 /*
2208 * If this is false, then the val is <= the register, if it is
2209 * true the register <= to the val.
2210 */
2211 false_reg->min_value = val;
2212 true_reg->max_value = val - 1;
2213 break;
2214 case BPF_JGE:
2215 /* Unsigned comparison, the minimum value is 0. */
2216 true_reg->min_value = 0;
7e57fbb2 2217 /* fallthrough */
48461135
JB		 2218 case BPF_JSGE:
2219 /* If this is false then constant < register, if it is true then
2220 * the register < constant.
2221 */
2222 false_reg->min_value = val + 1;
2223 true_reg->max_value = val;
2224 break;
2225 default:
2226 break;
2227 }
2228
2229 check_reg_overflow(false_reg);
2230 check_reg_overflow(true_reg);
2231}
2232
57a09bf0
TG		 2233static void mark_map_reg(struct bpf_reg_state *regs, u32 regno, u32 id,
2234 enum bpf_reg_type type)
2235{
2236 struct bpf_reg_state *reg = &regs[regno];
2237
2238 if (reg->type == PTR_TO_MAP_VALUE_OR_NULL && reg->id == id) {
56f668df
MKL		 2239 if (type == UNKNOWN_VALUE) {
2240 __mark_reg_unknown_value(regs, regno);
2241 } else if (reg->map_ptr->inner_map_meta) {
2242 reg->type = CONST_PTR_TO_MAP;
2243 reg->map_ptr = reg->map_ptr->inner_map_meta;
2244 } else {
2245 reg->type = type;
2246 }
a08dd0da
DB		 2247 /* We don't need id from this point onwards anymore, thus we
2248 * should better reset it, so that state pruning has chances
2249 * to take effect.
2250 */
2251 reg->id = 0;
57a09bf0
TG		 2252 }
2253}
2254
2255/* The logic is similar to find_good_pkt_pointers(), both could eventually
2256 * be folded together at some point.
2257 */
2258static void mark_map_regs(struct bpf_verifier_state *state, u32 regno,
2259 enum bpf_reg_type type)
2260{
2261 struct bpf_reg_state *regs = state->regs;
a08dd0da 2262 u32 id = regs[regno].id;
57a09bf0
TG		 2263 int i;
2264
2265 for (i = 0; i < MAX_BPF_REG; i++)
a08dd0da 2266 mark_map_reg(regs, i, id, type);
57a09bf0
TG		 2267
2268 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
2269 if (state->stack_slot_type[i] != STACK_SPILL)
2270 continue;
a08dd0da 2271 mark_map_reg(state->spilled_regs, i / BPF_REG_SIZE, id, type);
57a09bf0
TG		 2272 }
2273}
2274
58e2af8b 2275static int check_cond_jmp_op(struct bpf_verifier_env *env,
17a52670
AS		 2276 struct bpf_insn *insn, int *insn_idx)
2277{
58e2af8b
JK		 2278 struct bpf_verifier_state *other_branch, *this_branch = &env->cur_state;
2279 struct bpf_reg_state *regs = this_branch->regs, *dst_reg;
17a52670
AS		 2280 u8 opcode = BPF_OP(insn->code);
2281 int err;
2282
2283 if (opcode > BPF_EXIT) {
2284 verbose("invalid BPF_JMP opcode %x\n", opcode);
2285 return -EINVAL;
2286 }
2287
2288 if (BPF_SRC(insn->code) == BPF_X) {
2289 if (insn->imm != 0) {
2290 verbose("BPF_JMP uses reserved fields\n");
2291 return -EINVAL;
2292 }
2293
2294 /* check src1 operand */
2295 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
2296 if (err)
2297 return err;
1be7f75d
AS		 2298
2299 if (is_pointer_value(env, insn->src_reg)) {
2300 verbose("R%d pointer comparison prohibited\n",
2301 insn->src_reg);
2302 return -EACCES;
2303 }
17a52670
AS		 2304 } else {
2305 if (insn->src_reg != BPF_REG_0) {
2306 verbose("BPF_JMP uses reserved fields\n");
2307 return -EINVAL;
2308 }
2309 }
2310
2311 /* check src2 operand */
2312 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
2313 if (err)
2314 return err;
2315
1a0dc1ac
AS		 2316 dst_reg = &regs[insn->dst_reg];
2317
17a52670
AS		 2318 /* detect if R == 0 where R was initialized to zero earlier */
2319 if (BPF_SRC(insn->code) == BPF_K &&
2320 (opcode == BPF_JEQ || opcode == BPF_JNE) &&
1a0dc1ac 2321 dst_reg->type == CONST_IMM && dst_reg->imm == insn->imm) {
17a52670
AS		 2322 if (opcode == BPF_JEQ) {
2323 /* if (imm == imm) goto pc+off;
2324 * only follow the goto, ignore fall-through
2325 */
2326 *insn_idx += insn->off;
2327 return 0;
2328 } else {
2329 /* if (imm != imm) goto pc+off;
2330 * only follow fall-through branch, since
2331 * that's where the program will go
2332 */
2333 return 0;
2334 }
2335 }
2336
2337 other_branch = push_stack(env, *insn_idx + insn->off + 1, *insn_idx);
2338 if (!other_branch)
2339 return -EFAULT;
2340
48461135
JB		 2341 /* detect if we are comparing against a constant value so we can adjust
2342 * our min/max values for our dst register.
2343 */
2344 if (BPF_SRC(insn->code) == BPF_X) {
2345 if (regs[insn->src_reg].type == CONST_IMM)
2346 reg_set_min_max(&other_branch->regs[insn->dst_reg],
2347 dst_reg, regs[insn->src_reg].imm,
2348 opcode);
2349 else if (dst_reg->type == CONST_IMM)
2350 reg_set_min_max_inv(&other_branch->regs[insn->src_reg],
2351 &regs[insn->src_reg], dst_reg->imm,
2352 opcode);
2353 } else {
2354 reg_set_min_max(&other_branch->regs[insn->dst_reg],
2355 dst_reg, insn->imm, opcode);
2356 }
2357
58e2af8b 2358 /* detect if R == 0 where R is returned from bpf_map_lookup_elem() */
17a52670 2359 if (BPF_SRC(insn->code) == BPF_K &&
1a0dc1ac
AS		 2360 insn->imm == 0 && (opcode == BPF_JEQ || opcode == BPF_JNE) &&
2361 dst_reg->type == PTR_TO_MAP_VALUE_OR_NULL) {
57a09bf0
TG		 2362 /* Mark all identical map registers in each branch as either
2363 * safe or unknown depending R == 0 or R != 0 conditional.
2364 */
2365 mark_map_regs(this_branch, insn->dst_reg,
2366 opcode == BPF_JEQ ? PTR_TO_MAP_VALUE : UNKNOWN_VALUE);
2367 mark_map_regs(other_branch, insn->dst_reg,
2368 opcode == BPF_JEQ ? UNKNOWN_VALUE : PTR_TO_MAP_VALUE);
969bf05e
AS		 2369 } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JGT &&
2370 dst_reg->type == PTR_TO_PACKET &&
2371 regs[insn->src_reg].type == PTR_TO_PACKET_END) {
2d2be8ca
DB		 2372 find_good_pkt_pointers(this_branch, dst_reg);
2373 } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JGE &&
2374 dst_reg->type == PTR_TO_PACKET_END &&
2375 regs[insn->src_reg].type == PTR_TO_PACKET) {
2376 find_good_pkt_pointers(other_branch, &regs[insn->src_reg]);
1be7f75d
AS		 2377 } else if (is_pointer_value(env, insn->dst_reg)) {
2378 verbose("R%d pointer comparison prohibited\n", insn->dst_reg);
2379 return -EACCES;
17a52670
AS		 2380 }
2381 if (log_level)
2d2be8ca 2382 print_verifier_state(this_branch);
17a52670
AS		 2383 return 0;
2384}
2385
0246e64d
AS		 2386/* return the map pointer stored inside BPF_LD_IMM64 instruction */
2387static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
2388{
2389 u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32;
2390
2391 return (struct bpf_map *) (unsigned long) imm64;
2392}
2393
17a52670 2394/* verify BPF_LD_IMM64 instruction */
58e2af8b 2395static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
17a52670 2396{
58e2af8b 2397 struct bpf_reg_state *regs = env->cur_state.regs;
17a52670
AS		 2398 int err;
2399
2400 if (BPF_SIZE(insn->code) != BPF_DW) {
2401 verbose("invalid BPF_LD_IMM insn\n");
2402 return -EINVAL;
2403 }
2404 if (insn->off != 0) {
2405 verbose("BPF_LD_IMM64 uses reserved fields\n");
2406 return -EINVAL;
2407 }
2408
2409 err = check_reg_arg(regs, insn->dst_reg, DST_OP);
2410 if (err)
2411 return err;
2412
6b173873 2413 if (insn->src_reg == 0) {
6b173873
JK		 2414 u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm;
2415
6b173873
JK		 2416 regs[insn->dst_reg].type = CONST_IMM;
2417 regs[insn->dst_reg].imm = imm;
4a2ff55a 2418 regs[insn->dst_reg].id = 0;
17a52670 2419 return 0;
6b173873 2420 }
17a52670
AS		 2421
2422 /* replace_map_fd_with_map_ptr() should have caught bad ld_imm64 */
2423 BUG_ON(insn->src_reg != BPF_PSEUDO_MAP_FD);
2424
2425 regs[insn->dst_reg].type = CONST_PTR_TO_MAP;
2426 regs[insn->dst_reg].map_ptr = ld_imm64_to_map_ptr(insn);
2427 return 0;
2428}
2429
96be4325
DB		 2430static bool may_access_skb(enum bpf_prog_type type)
2431{
2432 switch (type) {
2433 case BPF_PROG_TYPE_SOCKET_FILTER:
2434 case BPF_PROG_TYPE_SCHED_CLS:
94caee8c 2435 case BPF_PROG_TYPE_SCHED_ACT:
96be4325
DB		 2436 return true;
2437 default:
2438 return false;
2439 }
2440}
2441
ddd872bc
AS		 2442/* verify safety of LD_ABS|LD_IND instructions:
2443 * - they can only appear in the programs where ctx == skb
2444 * - since they are wrappers of function calls, they scratch R1-R5 registers,
2445 * preserve R6-R9, and store return value into R0
2446 *
2447 * Implicit input:
2448 * ctx == skb == R6 == CTX
2449 *
2450 * Explicit input:
2451 * SRC == any register
2452 * IMM == 32-bit immediate
2453 *
2454 * Output:
2455 * R0 - 8/16/32-bit skb data converted to cpu endianness
2456 */
58e2af8b 2457static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
ddd872bc 2458{
58e2af8b 2459 struct bpf_reg_state *regs = env->cur_state.regs;
ddd872bc 2460 u8 mode = BPF_MODE(insn->code);
ddd872bc
AS		 2461 int i, err;
2462
24701ece 2463 if (!may_access_skb(env->prog->type)) {
1a0dc1ac 2464 verbose("BPF_LD_[ABS|IND] instructions not allowed for this program type\n");
ddd872bc
AS		 2465 return -EINVAL;
2466 }
2467
2468 if (insn->dst_reg != BPF_REG_0 || insn->off != 0 ||
d82bccc6 2469 BPF_SIZE(insn->code) == BPF_DW ||
ddd872bc 2470 (mode == BPF_ABS && insn->src_reg != BPF_REG_0)) {
1a0dc1ac 2471 verbose("BPF_LD_[ABS|IND] uses reserved fields\n");
ddd872bc
AS		 2472 return -EINVAL;
2473 }
2474
2475 /* check whether implicit source operand (register R6) is readable */
2476 err = check_reg_arg(regs, BPF_REG_6, SRC_OP);
2477 if (err)
2478 return err;
2479
2480 if (regs[BPF_REG_6].type != PTR_TO_CTX) {
2481 verbose("at the time of BPF_LD_ABS|IND R6 != pointer to skb\n");
2482 return -EINVAL;
2483 }
2484
2485 if (mode == BPF_IND) {
2486 /* check explicit source operand */
2487 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
2488 if (err)
2489 return err;
2490 }
2491
2492 /* reset caller saved regs to unreadable */
a9789ef9
DB		 2493 for (i = 0; i < CALLER_SAVED_REGS; i++)
2494 mark_reg_not_init(regs, caller_saved[i]);
ddd872bc
AS		 2495
2496 /* mark destination R0 register as readable, since it contains
2497 * the value fetched from the packet
2498 */
2499 regs[BPF_REG_0].type = UNKNOWN_VALUE;
2500 return 0;
2501}
2502
475fb78f
AS		 2503/* non-recursive DFS pseudo code
2504 * 1 procedure DFS-iterative(G,v):
2505 * 2 label v as discovered
2506 * 3 let S be a stack
2507 * 4 S.push(v)
2508 * 5 while S is not empty
2509 * 6 t <- S.pop()
2510 * 7 if t is what we're looking for:
2511 * 8 return t
2512 * 9 for all edges e in G.adjacentEdges(t) do
2513 * 10 if edge e is already labelled
2514 * 11 continue with the next edge
2515 * 12 w <- G.adjacentVertex(t,e)
2516 * 13 if vertex w is not discovered and not explored
2517 * 14 label e as tree-edge
2518 * 15 label w as discovered
2519 * 16 S.push(w)
2520 * 17 continue at 5
2521 * 18 else if vertex w is discovered
2522 * 19 label e as back-edge
2523 * 20 else
2524 * 21 // vertex w is explored
2525 * 22 label e as forward- or cross-edge
2526 * 23 label t as explored
2527 * 24 S.pop()
2528 *
2529 * convention:
2530 * 0x10 - discovered
2531 * 0x11 - discovered and fall-through edge labelled
2532 * 0x12 - discovered and fall-through and branch edges labelled
2533 * 0x20 - explored
2534 */
2535
2536enum {
2537 DISCOVERED = 0x10,
2538 EXPLORED = 0x20,
2539 FALLTHROUGH = 1,
2540 BRANCH = 2,
2541};
2542
58e2af8b 2543#define STATE_LIST_MARK ((struct bpf_verifier_state_list *) -1L)
f1bca824 2544
475fb78f
AS		 2545static int *insn_stack; /* stack of insns to process */
2546static int cur_stack; /* current stack index */
2547static int *insn_state;
2548
2549/* t, w, e - match pseudo-code above:
2550 * t - index of current instruction
2551 * w - next instruction
2552 * e - edge
2553 */
58e2af8b 2554static int push_insn(int t, int w, int e, struct bpf_verifier_env *env)
475fb78f
AS		 2555{
2556 if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
2557 return 0;
2558
2559 if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
2560 return 0;
2561
2562 if (w < 0 || w >= env->prog->len) {
2563 verbose("jump out of range from insn %d to %d\n", t, w);
2564 return -EINVAL;
2565 }
2566
f1bca824
AS		 2567 if (e == BRANCH)
2568 /* mark branch target for state pruning */
2569 env->explored_states[w] = STATE_LIST_MARK;
2570
475fb78f
AS		 2571 if (insn_state[w] == 0) {
2572 /* tree-edge */
2573 insn_state[t] = DISCOVERED | e;
2574 insn_state[w] = DISCOVERED;
2575 if (cur_stack >= env->prog->len)
2576 return -E2BIG;
2577 insn_stack[cur_stack++] = w;
2578 return 1;
2579 } else if ((insn_state[w] & 0xF0) == DISCOVERED) {
2580 verbose("back-edge from insn %d to %d\n", t, w);
2581 return -EINVAL;
2582 } else if (insn_state[w] == EXPLORED) {
2583 /* forward- or cross-edge */
2584 insn_state[t] = DISCOVERED | e;
2585 } else {
2586 verbose("insn state internal bug\n");
2587 return -EFAULT;
2588 }
2589 return 0;
2590}
2591
2592/* non-recursive depth-first-search to detect loops in BPF program
2593 * loop == back-edge in directed graph
2594 */
58e2af8b 2595static int check_cfg(struct bpf_verifier_env *env)
475fb78f
AS		 2596{
2597 struct bpf_insn *insns = env->prog->insnsi;
2598 int insn_cnt = env->prog->len;
2599 int ret = 0;
2600 int i, t;
2601
2602 insn_state = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
2603 if (!insn_state)
2604 return -ENOMEM;
2605
2606 insn_stack = kcalloc(insn_cnt, sizeof(int), GFP_KERNEL);
2607 if (!insn_stack) {
2608 kfree(insn_state);
2609 return -ENOMEM;
2610 }
2611
2612 insn_state[0] = DISCOVERED; /* mark 1st insn as discovered */
2613 insn_stack[0] = 0; /* 0 is the first instruction */
2614 cur_stack = 1;
2615
2616peek_stack:
2617 if (cur_stack == 0)
2618 goto check_state;
2619 t = insn_stack[cur_stack - 1];
2620
2621 if (BPF_CLASS(insns[t].code) == BPF_JMP) {
2622 u8 opcode = BPF_OP(insns[t].code);
2623
2624 if (opcode == BPF_EXIT) {
2625 goto mark_explored;
2626 } else if (opcode == BPF_CALL) {
2627 ret = push_insn(t, t + 1, FALLTHROUGH, env);
2628 if (ret == 1)
2629 goto peek_stack;
2630 else if (ret < 0)
2631 goto err_free;
07016151
DB		 2632 if (t + 1 < insn_cnt)
2633 env->explored_states[t + 1] = STATE_LIST_MARK;
475fb78f
AS		 2634 } else if (opcode == BPF_JA) {
2635 if (BPF_SRC(insns[t].code) != BPF_K) {
2636 ret = -EINVAL;
2637 goto err_free;
2638 }
2639 /* unconditional jump with single edge */
2640 ret = push_insn(t, t + insns[t].off + 1,
2641 FALLTHROUGH, env);
2642 if (ret == 1)
2643 goto peek_stack;
2644 else if (ret < 0)
2645 goto err_free;
f1bca824
AS		 2646 /* tell verifier to check for equivalent states
2647 * after every call and jump
2648 */
c3de6317
AS		 2649 if (t + 1 < insn_cnt)
2650 env->explored_states[t + 1] = STATE_LIST_MARK;
475fb78f
AS		 2651 } else {
2652 /* conditional jump with two edges */
3c2ce60b 2653 env->explored_states[t] = STATE_LIST_MARK;
475fb78f
AS		 2654 ret = push_insn(t, t + 1, FALLTHROUGH, env);
2655 if (ret == 1)
2656 goto peek_stack;
2657 else if (ret < 0)
2658 goto err_free;
2659
2660 ret = push_insn(t, t + insns[t].off + 1, BRANCH, env);
2661 if (ret == 1)
2662 goto peek_stack;
2663 else if (ret < 0)
2664 goto err_free;
2665 }
2666 } else {
2667 /* all other non-branch instructions with single
2668 * fall-through edge
2669 */
2670 ret = push_insn(t, t + 1, FALLTHROUGH, env);
2671 if (ret == 1)
2672 goto peek_stack;
2673 else if (ret < 0)
2674 goto err_free;
2675 }
2676
2677mark_explored:
2678 insn_state[t] = EXPLORED;
2679 if (cur_stack-- <= 0) {
2680 verbose("pop stack internal bug\n");
2681 ret = -EFAULT;
2682 goto err_free;
2683 }
2684 goto peek_stack;
2685
2686check_state:
2687 for (i = 0; i < insn_cnt; i++) {
2688 if (insn_state[i] != EXPLORED) {
2689 verbose("unreachable insn %d\n", i);
2690 ret = -EINVAL;
2691 goto err_free;
2692 }
2693 }
2694 ret = 0; /* cfg looks good */
2695
2696err_free:
2697 kfree(insn_state);
2698 kfree(insn_stack);
2699 return ret;
2700}
2701
969bf05e
AS		 2702/* the following conditions reduce the number of explored insns
2703 * from ~140k to ~80k for ultra large programs that use a lot of ptr_to_packet
2704 */
1ad2f583
DB		 2705static bool compare_ptrs_to_packet(struct bpf_verifier_env *env,
2706 struct bpf_reg_state *old,
58e2af8b 2707 struct bpf_reg_state *cur)
969bf05e
AS		 2708{
2709 if (old->id != cur->id)
2710 return false;
2711
2712 /* old ptr_to_packet is more conservative, since it allows smaller
2713 * range. Ex:
2714 * old(off=0,r=10) is equal to cur(off=0,r=20), because
2715 * old(off=0,r=10) means that with range=10 the verifier proceeded
2716 * further and found no issues with the program. Now we're in the same
2717 * spot with cur(off=0,r=20), so we're safe too, since anything further
2718 * will only be looking at most 10 bytes after this pointer.
2719 */
2720 if (old->off == cur->off && old->range < cur->range)
2721 return true;
2722
2723 /* old(off=20,r=10) is equal to cur(off=22,re=22 or 5 or 0)
2724 * since both cannot be used for packet access and safe(old)
2725 * pointer has smaller off that could be used for further
2726 * 'if (ptr > data_end)' check
2727 * Ex:
2728 * old(off=20,r=10) and cur(off=22,r=22) and cur(off=22,r=0) mean
2729 * that we cannot access the packet.
2730 * The safe range is:
2731 * [ptr, ptr + range - off)
2732 * so whenever off >=range, it means no safe bytes from this pointer.
2733 * When comparing old->off <= cur->off, it means that older code
2734 * went with smaller offset and that offset was later
2735 * used to figure out the safe range after 'if (ptr > data_end)' check
2736 * Say, 'old' state was explored like:
2737 * ... R3(off=0, r=0)
2738 * R4 = R3 + 20
2739 * ... now R4(off=20,r=0) <-- here
2740 * if (R4 > data_end)
2741 * ... R4(off=20,r=20), R3(off=0,r=20) and R3 can be used to access.
2742 * ... the code further went all the way to bpf_exit.
2743 * Now the 'cur' state at the mark 'here' has R4(off=30,r=0).
2744 * old_R4(off=20,r=0) equal to cur_R4(off=30,r=0), since if the verifier
2745 * goes further, such cur_R4 will give larger safe packet range after
2746 * 'if (R4 > data_end)' and all further insn were already good with r=20,
2747 * so they will be good with r=30 and we can prune the search.
2748 */
1ad2f583 2749 if (!env->strict_alignment && old->off <= cur->off &&
969bf05e
AS		 2750 old->off >= old->range && cur->off >= cur->range)
2751 return true;
2752
2753 return false;
2754}
2755
f1bca824
AS		 2756/* compare two verifier states
2757 *
2758 * all states stored in state_list are known to be valid, since
2759 * verifier reached 'bpf_exit' instruction through them
2760 *
2761 * this function is called when verifier exploring different branches of
2762 * execution popped from the state stack. If it sees an old state that has
2763 * more strict register state and more strict stack state then this execution
2764 * branch doesn't need to be explored further, since verifier already
2765 * concluded that more strict state leads to valid finish.
2766 *
2767 * Therefore two states are equivalent if register state is more conservative
2768 * and explored stack state is more conservative than the current one.
2769 * Example:
2770 * explored current
2771 * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC)
2772 * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC)
2773 *
2774 * In other words if current stack state (one being explored) has more
2775 * valid slots than old one that already passed validation, it means
2776 * the verifier can stop exploring and conclude that current state is valid too
2777 *
2778 * Similarly with registers. If explored state has register type as invalid
2779 * whereas register type in current state is meaningful, it means that
2780 * the current state will reach 'bpf_exit' instruction safely
2781 */
48461135
JB		 2782static bool states_equal(struct bpf_verifier_env *env,
2783 struct bpf_verifier_state *old,
58e2af8b 2784 struct bpf_verifier_state *cur)
f1bca824 2785{
e2d2afe1 2786 bool varlen_map_access = env->varlen_map_value_access;
58e2af8b 2787 struct bpf_reg_state *rold, *rcur;
f1bca824
AS		 2788 int i;
2789
2790 for (i = 0; i < MAX_BPF_REG; i++) {
1a0dc1ac
AS		 2791 rold = &old->regs[i];
2792 rcur = &cur->regs[i];
2793
2794 if (memcmp(rold, rcur, sizeof(*rold)) == 0)
2795 continue;
2796
48461135
JB		 2797 /* If the ranges were not the same, but everything else was and
2798 * we didn't do a variable access into a map then we are a-ok.
2799 */
e2d2afe1 2800 if (!varlen_map_access &&
d2a4dd37 2801 memcmp(rold, rcur, offsetofend(struct bpf_reg_state, id)) == 0)
48461135
JB		 2802 continue;
2803
e2d2afe1
JB		 2804 /* If we didn't map access then again we don't care about the
2805 * mismatched range values and it's ok if our old type was
2806 * UNKNOWN and we didn't go to a NOT_INIT'ed reg.
2807 */
1a0dc1ac 2808 if (rold->type == NOT_INIT ||
e2d2afe1
JB		 2809 (!varlen_map_access && rold->type == UNKNOWN_VALUE &&
2810 rcur->type != NOT_INIT))
1a0dc1ac
AS		 2811 continue;
2812
3c2ce60b
DB		 2813 /* Don't care about the reg->id in this case. */
2814 if (rold->type == PTR_TO_MAP_VALUE_OR_NULL &&
2815 rcur->type == PTR_TO_MAP_VALUE_OR_NULL &&
2816 rold->map_ptr == rcur->map_ptr)
2817 continue;
2818
969bf05e 2819 if (rold->type == PTR_TO_PACKET && rcur->type == PTR_TO_PACKET &&
1ad2f583 2820 compare_ptrs_to_packet(env, rold, rcur))
969bf05e
AS		 2821 continue;
2822
1a0dc1ac 2823 return false;
f1bca824
AS		 2824 }
2825
2826 for (i = 0; i < MAX_BPF_STACK; i++) {
9c399760
AS		 2827 if (old->stack_slot_type[i] == STACK_INVALID)
2828 continue;
2829 if (old->stack_slot_type[i] != cur->stack_slot_type[i])
2830 /* Ex: old explored (safe) state has STACK_SPILL in
2831 * this stack slot, but current has has STACK_MISC ->
2832 * this verifier states are not equivalent,
2833 * return false to continue verification of this path
2834 */
f1bca824 2835 return false;
9c399760
AS		 2836 if (i % BPF_REG_SIZE)
2837 continue;
d25da6ca
DB		 2838 if (old->stack_slot_type[i] != STACK_SPILL)
2839 continue;
9c399760
AS		 2840 if (memcmp(&old->spilled_regs[i / BPF_REG_SIZE],
2841 &cur->spilled_regs[i / BPF_REG_SIZE],
2842 sizeof(old->spilled_regs[0])))
2843 /* when explored and current stack slot types are
2844 * the same, check that stored pointers types
2845 * are the same as well.
2846 * Ex: explored safe path could have stored
58e2af8b 2847 * (bpf_reg_state) {.type = PTR_TO_STACK, .imm = -8}
9c399760 2848 * but current path has stored:
58e2af8b 2849 * (bpf_reg_state) {.type = PTR_TO_STACK, .imm = -16}
9c399760
AS		 2850 * such verifier states are not equivalent.
2851 * return false to continue verification of this path
2852 */
2853 return false;
2854 else
2855 continue;
f1bca824
AS		 2856 }
2857 return true;
2858}
2859
58e2af8b 2860static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
f1bca824 2861{
58e2af8b
JK		 2862 struct bpf_verifier_state_list *new_sl;
2863 struct bpf_verifier_state_list *sl;
f1bca824
AS		 2864
2865 sl = env->explored_states[insn_idx];
2866 if (!sl)
2867 /* this 'insn_idx' instruction wasn't marked, so we will not
2868 * be doing state search here
2869 */
2870 return 0;
2871
2872 while (sl != STATE_LIST_MARK) {
48461135 2873 if (states_equal(env, &sl->state, &env->cur_state))
f1bca824
AS		 2874 /* reached equivalent register/stack state,
2875 * prune the search
2876 */
2877 return 1;
2878 sl = sl->next;
2879 }
2880
2881 /* there were no equivalent states, remember current one.
2882 * technically the current state is not proven to be safe yet,
2883 * but it will either reach bpf_exit (which means it's safe) or
2884 * it will be rejected. Since there are no loops, we won't be
2885 * seeing this 'insn_idx' instruction again on the way to bpf_exit
2886 */
58e2af8b 2887 new_sl = kmalloc(sizeof(struct bpf_verifier_state_list), GFP_USER);
f1bca824
AS		 2888 if (!new_sl)
2889 return -ENOMEM;
2890
2891 /* add new state to the head of linked list */
2892 memcpy(&new_sl->state, &env->cur_state, sizeof(env->cur_state));
2893 new_sl->next = env->explored_states[insn_idx];
2894 env->explored_states[insn_idx] = new_sl;
2895 return 0;
2896}
2897
13a27dfc
JK		 2898static int ext_analyzer_insn_hook(struct bpf_verifier_env *env,
2899 int insn_idx, int prev_insn_idx)
2900{
2901 if (!env->analyzer_ops || !env->analyzer_ops->insn_hook)
2902 return 0;
2903
2904 return env->analyzer_ops->insn_hook(env, insn_idx, prev_insn_idx);
2905}
2906
58e2af8b 2907static int do_check(struct bpf_verifier_env *env)
17a52670 2908{
58e2af8b 2909 struct bpf_verifier_state *state = &env->cur_state;
17a52670 2910 struct bpf_insn *insns = env->prog->insnsi;
58e2af8b 2911 struct bpf_reg_state *regs = state->regs;
17a52670
AS		 2912 int insn_cnt = env->prog->len;
2913 int insn_idx, prev_insn_idx = 0;
2914 int insn_processed = 0;
2915 bool do_print_state = false;
2916
2917 init_reg_state(regs);
2918 insn_idx = 0;
48461135 2919 env->varlen_map_value_access = false;
17a52670
AS		 2920 for (;;) {
2921 struct bpf_insn *insn;
2922 u8 class;
2923 int err;
2924
2925 if (insn_idx >= insn_cnt) {
2926 verbose("invalid insn idx %d insn_cnt %d\n",
2927 insn_idx, insn_cnt);
2928 return -EFAULT;
2929 }
2930
2931 insn = &insns[insn_idx];
2932 class = BPF_CLASS(insn->code);
2933
07016151 2934 if (++insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) {
bc1750f3 2935 verbose("BPF program is too large. Processed %d insn\n",
17a52670
AS		 2936 insn_processed);
2937 return -E2BIG;
2938 }
2939
f1bca824
AS		 2940 err = is_state_visited(env, insn_idx);
2941 if (err < 0)
2942 return err;
2943 if (err == 1) {
2944 /* found equivalent state, can prune the search */
2945 if (log_level) {
2946 if (do_print_state)
2947 verbose("\nfrom %d to %d: safe\n",
2948 prev_insn_idx, insn_idx);
2949 else
2950 verbose("%d: safe\n", insn_idx);
2951 }
2952 goto process_bpf_exit;
2953 }
2954
3c2ce60b
DB		 2955 if (need_resched())
2956 cond_resched();
2957
c5fc9692
DM		 2958 if (log_level > 1 || (log_level && do_print_state)) {
2959 if (log_level > 1)
2960 verbose("%d:", insn_idx);
2961 else
2962 verbose("\nfrom %d to %d:",
2963 prev_insn_idx, insn_idx);
1a0dc1ac 2964 print_verifier_state(&env->cur_state);
17a52670
AS		 2965 do_print_state = false;
2966 }
2967
2968 if (log_level) {
2969 verbose("%d: ", insn_idx);
0d0e5769 2970 print_bpf_insn(env, insn);
17a52670
AS		 2971 }
2972
13a27dfc
JK		 2973 err = ext_analyzer_insn_hook(env, insn_idx, prev_insn_idx);
2974 if (err)
2975 return err;
2976
17a52670 2977 if (class == BPF_ALU || class == BPF_ALU64) {
1be7f75d 2978 err = check_alu_op(env, insn);
17a52670
AS		 2979 if (err)
2980 return err;
2981
2982 } else if (class == BPF_LDX) {
3df126f3 2983 enum bpf_reg_type *prev_src_type, src_reg_type;
9bac3d6d
AS		 2984
2985 /* check for reserved fields is already done */
2986
17a52670
AS		 2987 /* check src operand */
2988 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
2989 if (err)
2990 return err;
2991
2992 err = check_reg_arg(regs, insn->dst_reg, DST_OP_NO_MARK);
2993 if (err)
2994 return err;
2995
725f9dcd
AS		 2996 src_reg_type = regs[insn->src_reg].type;
2997
17a52670
AS		 2998 /* check that memory (src_reg + off) is readable,
2999 * the state of dst_reg will be updated by this func
3000 */
31fd8581 3001 err = check_mem_access(env, insn_idx, insn->src_reg, insn->off,
17a52670
AS		 3002 BPF_SIZE(insn->code), BPF_READ,
3003 insn->dst_reg);
3004 if (err)
3005 return err;
3006
3df126f3
JK		 3007 prev_src_type = &env->insn_aux_data[insn_idx].ptr_type;
3008
3009 if (*prev_src_type == NOT_INIT) {
9bac3d6d
AS		 3010 /* saw a valid insn
3011 * dst_reg = *(u32 *)(src_reg + off)
3df126f3 3012 * save type to validate intersecting paths
9bac3d6d 3013 */
3df126f3 3014 *prev_src_type = src_reg_type;
9bac3d6d 3015
3df126f3 3016 } else if (src_reg_type != *prev_src_type &&
9bac3d6d 3017 (src_reg_type == PTR_TO_CTX ||
3df126f3 3018 *prev_src_type == PTR_TO_CTX)) {
9bac3d6d
AS		 3019 /* ABuser program is trying to use the same insn
3020 * dst_reg = *(u32*) (src_reg + off)
3021 * with different pointer types:
3022 * src_reg == ctx in one branch and
3023 * src_reg == stack|map in some other branch.
3024 * Reject it.
3025 */
3026 verbose("same insn cannot be used with different pointers\n");
3027 return -EINVAL;
3028 }
3029
17a52670 3030 } else if (class == BPF_STX) {
3df126f3 3031 enum bpf_reg_type *prev_dst_type, dst_reg_type;
d691f9e8 3032
17a52670 3033 if (BPF_MODE(insn->code) == BPF_XADD) {
31fd8581 3034 err = check_xadd(env, insn_idx, insn);
17a52670
AS		 3035 if (err)
3036 return err;
3037 insn_idx++;
3038 continue;
3039 }
3040
17a52670
AS		 3041 /* check src1 operand */
3042 err = check_reg_arg(regs, insn->src_reg, SRC_OP);
3043 if (err)
3044 return err;
3045 /* check src2 operand */
3046 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
3047 if (err)
3048 return err;
3049
d691f9e8
AS		 3050 dst_reg_type = regs[insn->dst_reg].type;
3051
17a52670 3052 /* check that memory (dst_reg + off) is writeable */
31fd8581 3053 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
17a52670
AS		 3054 BPF_SIZE(insn->code), BPF_WRITE,
3055 insn->src_reg);
3056 if (err)
3057 return err;
3058
3df126f3
JK		 3059 prev_dst_type = &env->insn_aux_data[insn_idx].ptr_type;
3060
3061 if (*prev_dst_type == NOT_INIT) {
3062 *prev_dst_type = dst_reg_type;
3063 } else if (dst_reg_type != *prev_dst_type &&
d691f9e8 3064 (dst_reg_type == PTR_TO_CTX ||
3df126f3 3065 *prev_dst_type == PTR_TO_CTX)) {
d691f9e8
AS		 3066 verbose("same insn cannot be used with different pointers\n");
3067 return -EINVAL;
3068 }
3069
17a52670
AS		 3070 } else if (class == BPF_ST) {
3071 if (BPF_MODE(insn->code) != BPF_MEM ||
3072 insn->src_reg != BPF_REG_0) {
3073 verbose("BPF_ST uses reserved fields\n");
3074 return -EINVAL;
3075 }
3076 /* check src operand */
3077 err = check_reg_arg(regs, insn->dst_reg, SRC_OP);
3078 if (err)
3079 return err;
3080
3081 /* check that memory (dst_reg + off) is writeable */
31fd8581 3082 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
17a52670
AS		 3083 BPF_SIZE(insn->code), BPF_WRITE,
3084 -1);
3085 if (err)
3086 return err;
3087
3088 } else if (class == BPF_JMP) {
3089 u8 opcode = BPF_OP(insn->code);
3090
3091 if (opcode == BPF_CALL) {
3092 if (BPF_SRC(insn->code) != BPF_K ||
3093 insn->off != 0 ||
3094 insn->src_reg != BPF_REG_0 ||
3095 insn->dst_reg != BPF_REG_0) {
3096 verbose("BPF_CALL uses reserved fields\n");
3097 return -EINVAL;
3098 }
3099
81ed18ab 3100 err = check_call(env, insn->imm, insn_idx);
17a52670
AS		 3101 if (err)
3102 return err;
3103
3104 } else if (opcode == BPF_JA) {
3105 if (BPF_SRC(insn->code) != BPF_K ||
3106 insn->imm != 0 ||
3107 insn->src_reg != BPF_REG_0 ||
3108 insn->dst_reg != BPF_REG_0) {
3109 verbose("BPF_JA uses reserved fields\n");
3110 return -EINVAL;
3111 }
3112
3113 insn_idx += insn->off + 1;
3114 continue;
3115
3116 } else if (opcode == BPF_EXIT) {
3117 if (BPF_SRC(insn->code) != BPF_K ||
3118 insn->imm != 0 ||
3119 insn->src_reg != BPF_REG_0 ||
3120 insn->dst_reg != BPF_REG_0) {
3121 verbose("BPF_EXIT uses reserved fields\n");
3122 return -EINVAL;
3123 }
3124
3125 /* eBPF calling convetion is such that R0 is used
3126 * to return the value from eBPF program.
3127 * Make sure that it's readable at this time
3128 * of bpf_exit, which means that program wrote
3129 * something into it earlier
3130 */
3131 err = check_reg_arg(regs, BPF_REG_0, SRC_OP);
3132 if (err)
3133 return err;
3134
1be7f75d
AS		 3135 if (is_pointer_value(env, BPF_REG_0)) {
3136 verbose("R0 leaks addr as return value\n");
3137 return -EACCES;
3138 }
3139
f1bca824 3140process_bpf_exit:
17a52670
AS		 3141 insn_idx = pop_stack(env, &prev_insn_idx);
3142 if (insn_idx < 0) {
3143 break;
3144 } else {
3145 do_print_state = true;
3146 continue;
3147 }
3148 } else {
3149 err = check_cond_jmp_op(env, insn, &insn_idx);
3150 if (err)
3151 return err;
3152 }
3153 } else if (class == BPF_LD) {
3154 u8 mode = BPF_MODE(insn->code);
3155
3156 if (mode == BPF_ABS || mode == BPF_IND) {
ddd872bc
AS		 3157 err = check_ld_abs(env, insn);
3158 if (err)
3159 return err;
3160
17a52670
AS		 3161 } else if (mode == BPF_IMM) {
3162 err = check_ld_imm(env, insn);
3163 if (err)
3164 return err;
3165
3166 insn_idx++;
3167 } else {
3168 verbose("invalid BPF_LD mode\n");
3169 return -EINVAL;
3170 }
48461135 3171 reset_reg_range_values(regs, insn->dst_reg);
17a52670
AS		 3172 } else {
3173 verbose("unknown insn class %d\n", class);
3174 return -EINVAL;
3175 }
3176
3177 insn_idx++;
3178 }
3179
8726679a
AS		 3180 verbose("processed %d insns, stack depth %d\n",
3181 insn_processed, env->prog->aux->stack_depth);
17a52670
AS		 3182 return 0;
3183}
3184
56f668df
MKL		 3185static int check_map_prealloc(struct bpf_map *map)
3186{
3187 return (map->map_type != BPF_MAP_TYPE_HASH &&
bcc6b1b7
MKL		 3188 map->map_type != BPF_MAP_TYPE_PERCPU_HASH &&
3189 map->map_type != BPF_MAP_TYPE_HASH_OF_MAPS) ||
56f668df
MKL		 3190 !(map->map_flags & BPF_F_NO_PREALLOC);
3191}
3192
fdc15d38
AS		 3193static int check_map_prog_compatibility(struct bpf_map *map,
3194 struct bpf_prog *prog)
3195
3196{
56f668df
MKL		 3197 /* Make sure that BPF_PROG_TYPE_PERF_EVENT programs only use
3198 * preallocated hash maps, since doing memory allocation
3199 * in overflow_handler can crash depending on where nmi got
3200 * triggered.
3201 */
3202 if (prog->type == BPF_PROG_TYPE_PERF_EVENT) {
3203 if (!check_map_prealloc(map)) {
3204 verbose("perf_event programs can only use preallocated hash map\n");
3205 return -EINVAL;
3206 }
3207 if (map->inner_map_meta &&
3208 !check_map_prealloc(map->inner_map_meta)) {
3209 verbose("perf_event programs can only use preallocated inner hash map\n");
3210 return -EINVAL;
3211 }
fdc15d38
AS		 3212 }
3213 return 0;
3214}
3215
0246e64d
AS		 3216/* look for pseudo eBPF instructions that access map FDs and
3217 * replace them with actual map pointers
3218 */
58e2af8b 3219static int replace_map_fd_with_map_ptr(struct bpf_verifier_env *env)
0246e64d
AS		 3220{
3221 struct bpf_insn *insn = env->prog->insnsi;
3222 int insn_cnt = env->prog->len;
fdc15d38 3223 int i, j, err;
0246e64d 3224
f1f7714e 3225 err = bpf_prog_calc_tag(env->prog);
aafe6ae9
DB		 3226 if (err)
3227 return err;
3228
0246e64d 3229 for (i = 0; i < insn_cnt; i++, insn++) {
9bac3d6d 3230 if (BPF_CLASS(insn->code) == BPF_LDX &&
d691f9e8 3231 (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0)) {
9bac3d6d
AS		 3232 verbose("BPF_LDX uses reserved fields\n");
3233 return -EINVAL;
3234 }
3235
d691f9e8
AS		 3236 if (BPF_CLASS(insn->code) == BPF_STX &&
3237 ((BPF_MODE(insn->code) != BPF_MEM &&
3238 BPF_MODE(insn->code) != BPF_XADD) || insn->imm != 0)) {
3239 verbose("BPF_STX uses reserved fields\n");
3240 return -EINVAL;
3241 }
3242
0246e64d
AS		 3243 if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {
3244 struct bpf_map *map;
3245 struct fd f;
3246
3247 if (i == insn_cnt - 1 || insn[1].code != 0 ||
3248 insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
3249 insn[1].off != 0) {
3250 verbose("invalid bpf_ld_imm64 insn\n");
3251 return -EINVAL;
3252 }
3253
3254 if (insn->src_reg == 0)
3255 /* valid generic load 64-bit imm */
3256 goto next_insn;
3257
3258 if (insn->src_reg != BPF_PSEUDO_MAP_FD) {
3259 verbose("unrecognized bpf_ld_imm64 insn\n");
3260 return -EINVAL;
3261 }
3262
3263 f = fdget(insn->imm);
c2101297 3264 map = __bpf_map_get(f);
0246e64d
AS		 3265 if (IS_ERR(map)) {
3266 verbose("fd %d is not pointing to valid bpf_map\n",
3267 insn->imm);
0246e64d
AS		 3268 return PTR_ERR(map);
3269 }
3270
fdc15d38
AS		 3271 err = check_map_prog_compatibility(map, env->prog);
3272 if (err) {
3273 fdput(f);
3274 return err;
3275 }
3276
0246e64d
AS		 3277 /* store map pointer inside BPF_LD_IMM64 instruction */
3278 insn[0].imm = (u32) (unsigned long) map;
3279 insn[1].imm = ((u64) (unsigned long) map) >> 32;
3280
3281 /* check whether we recorded this map already */
3282 for (j = 0; j < env->used_map_cnt; j++)
3283 if (env->used_maps[j] == map) {
3284 fdput(f);
3285 goto next_insn;
3286 }
3287
3288 if (env->used_map_cnt >= MAX_USED_MAPS) {
3289 fdput(f);
3290 return -E2BIG;
3291 }
3292
0246e64d
AS		 3293 /* hold the map. If the program is rejected by verifier,
3294 * the map will be released by release_maps() or it
3295 * will be used by the valid program until it's unloaded
3296 * and all maps are released in free_bpf_prog_info()
3297 */
92117d84
AS		 3298 map = bpf_map_inc(map, false);
3299 if (IS_ERR(map)) {
3300 fdput(f);
3301 return PTR_ERR(map);
3302 }
3303 env->used_maps[env->used_map_cnt++] = map;
3304
0246e64d
AS		 3305 fdput(f);
3306next_insn:
3307 insn++;
3308 i++;
3309 }
3310 }
3311
3312 /* now all pseudo BPF_LD_IMM64 instructions load valid
3313 * 'struct bpf_map *' into a register instead of user map_fd.
3314 * These pointers will be used later by verifier to validate map access.
3315 */
3316 return 0;
3317}
3318
3319/* drop refcnt of maps used by the rejected program */
58e2af8b 3320static void release_maps(struct bpf_verifier_env *env)
0246e64d
AS		 3321{
3322 int i;
3323
3324 for (i = 0; i < env->used_map_cnt; i++)
3325 bpf_map_put(env->used_maps[i]);
3326}
3327
3328/* convert pseudo BPF_LD_IMM64 into generic BPF_LD_IMM64 */
58e2af8b 3329static void convert_pseudo_ld_imm64(struct bpf_verifier_env *env)
0246e64d
AS		 3330{
3331 struct bpf_insn *insn = env->prog->insnsi;
3332 int insn_cnt = env->prog->len;
3333 int i;
3334
3335 for (i = 0; i < insn_cnt; i++, insn++)
3336 if (insn->code == (BPF_LD | BPF_IMM | BPF_DW))
3337 insn->src_reg = 0;
3338}
3339
8041902d
AS		 3340/* single env->prog->insni[off] instruction was replaced with the range
3341 * insni[off, off + cnt). Adjust corresponding insn_aux_data by copying
3342 * [0, off) and [off, end) to new locations, so the patched range stays zero
3343 */
3344static int adjust_insn_aux_data(struct bpf_verifier_env *env, u32 prog_len,
3345 u32 off, u32 cnt)
3346{
3347 struct bpf_insn_aux_data *new_data, *old_data = env->insn_aux_data;
3348
3349 if (cnt == 1)
3350 return 0;
3351 new_data = vzalloc(sizeof(struct bpf_insn_aux_data) * prog_len);
3352 if (!new_data)
3353 return -ENOMEM;
3354 memcpy(new_data, old_data, sizeof(struct bpf_insn_aux_data) * off);
3355 memcpy(new_data + off + cnt - 1, old_data + off,
3356 sizeof(struct bpf_insn_aux_data) * (prog_len - off - cnt + 1));
3357 env->insn_aux_data = new_data;
3358 vfree(old_data);
3359 return 0;
3360}
3361
3362static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 off,
3363 const struct bpf_insn *patch, u32 len)
3364{
3365 struct bpf_prog *new_prog;
3366
3367 new_prog = bpf_patch_insn_single(env->prog, off, patch, len);
3368 if (!new_prog)
3369 return NULL;
3370 if (adjust_insn_aux_data(env, new_prog->len, off, len))
3371 return NULL;
3372 return new_prog;
3373}
3374
9bac3d6d
AS		 3375/* convert load instructions that access fields of 'struct __sk_buff'
3376 * into sequence of instructions that access fields of 'struct sk_buff'
3377 */
58e2af8b 3378static int convert_ctx_accesses(struct bpf_verifier_env *env)
9bac3d6d 3379{
36bbef52 3380 const struct bpf_verifier_ops *ops = env->prog->aux->ops;
f96da094 3381 int i, cnt, size, ctx_field_size, delta = 0;
3df126f3 3382 const int insn_cnt = env->prog->len;
36bbef52 3383 struct bpf_insn insn_buf[16], *insn;
9bac3d6d 3384 struct bpf_prog *new_prog;
d691f9e8 3385 enum bpf_access_type type;
f96da094
DB		 3386 bool is_narrower_load;
3387 u32 target_size;
9bac3d6d 3388
36bbef52
DB		 3389 if (ops->gen_prologue) {
3390 cnt = ops->gen_prologue(insn_buf, env->seen_direct_write,
3391 env->prog);
3392 if (cnt >= ARRAY_SIZE(insn_buf)) {
3393 verbose("bpf verifier is misconfigured\n");
3394 return -EINVAL;
3395 } else if (cnt) {
8041902d 3396 new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
36bbef52
DB		 3397 if (!new_prog)
3398 return -ENOMEM;
8041902d 3399
36bbef52 3400 env->prog = new_prog;
3df126f3 3401 delta += cnt - 1;
36bbef52
DB		 3402 }
3403 }
3404
3405 if (!ops->convert_ctx_access)
9bac3d6d
AS		 3406 return 0;
3407
3df126f3 3408 insn = env->prog->insnsi + delta;
36bbef52 3409
9bac3d6d 3410 for (i = 0; i < insn_cnt; i++, insn++) {
62c7989b
DB		 3411 if (insn->code == (BPF_LDX | BPF_MEM | BPF_B) ||
3412 insn->code == (BPF_LDX | BPF_MEM | BPF_H) ||
3413 insn->code == (BPF_LDX | BPF_MEM | BPF_W) ||
ea2e7ce5 3414 insn->code == (BPF_LDX | BPF_MEM | BPF_DW))
d691f9e8 3415 type = BPF_READ;
62c7989b
DB		 3416 else if (insn->code == (BPF_STX | BPF_MEM | BPF_B) ||
3417 insn->code == (BPF_STX | BPF_MEM | BPF_H) ||
3418 insn->code == (BPF_STX | BPF_MEM | BPF_W) ||
ea2e7ce5 3419 insn->code == (BPF_STX | BPF_MEM | BPF_DW))
d691f9e8
AS		 3420 type = BPF_WRITE;
3421 else
9bac3d6d
AS		 3422 continue;
3423
8041902d 3424 if (env->insn_aux_data[i + delta].ptr_type != PTR_TO_CTX)
9bac3d6d 3425 continue;
9bac3d6d 3426
31fd8581 3427 ctx_field_size = env->insn_aux_data[i + delta].ctx_field_size;
f96da094 3428 size = BPF_LDST_BYTES(insn);
31fd8581
YS		 3429
3430 /* If the read access is a narrower load of the field,
3431 * convert to a 4/8-byte load, to minimum program type specific
3432 * convert_ctx_access changes. If conversion is successful,
3433 * we will apply proper mask to the result.
3434 */
f96da094 3435 is_narrower_load = size < ctx_field_size;
31fd8581 3436 if (is_narrower_load) {
f96da094
DB		 3437 u32 off = insn->off;
3438 u8 size_code;
3439
3440 if (type == BPF_WRITE) {
3441 verbose("bpf verifier narrow ctx access misconfigured\n");
3442 return -EINVAL;
3443 }
31fd8581 3444
f96da094 3445 size_code = BPF_H;
31fd8581
YS		 3446 if (ctx_field_size == 4)
3447 size_code = BPF_W;
3448 else if (ctx_field_size == 8)
3449 size_code = BPF_DW;
f96da094 3450
31fd8581
YS		 3451 insn->off = off & ~(ctx_field_size - 1);
3452 insn->code = BPF_LDX | BPF_MEM | size_code;
3453 }
f96da094
DB		 3454
3455 target_size = 0;
3456 cnt = ops->convert_ctx_access(type, insn, insn_buf, env->prog,
3457 &target_size);
3458 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf) ||
3459 (ctx_field_size && !target_size)) {
9bac3d6d
AS		 3460 verbose("bpf verifier is misconfigured\n");
3461 return -EINVAL;
3462 }
f96da094
DB		 3463
3464 if (is_narrower_load && size < target_size) {
31fd8581
YS		 3465 if (ctx_field_size <= 4)
3466 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg,
f96da094 3467 (1 << size * 8) - 1);
31fd8581
YS		 3468 else
3469 insn_buf[cnt++] = BPF_ALU64_IMM(BPF_AND, insn->dst_reg,
f96da094 3470 (1 << size * 8) - 1);
31fd8581 3471 }
9bac3d6d 3472
8041902d 3473 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
9bac3d6d
AS		 3474 if (!new_prog)
3475 return -ENOMEM;
3476
3df126f3 3477 delta += cnt - 1;
9bac3d6d
AS		 3478
3479 /* keep walking new program and skip insns we just inserted */
3480 env->prog = new_prog;
3df126f3 3481 insn = new_prog->insnsi + i + delta;
9bac3d6d
AS		 3482 }
3483
3484 return 0;
3485}
3486
79741b3b 3487/* fixup insn->imm field of bpf_call instructions
81ed18ab 3488 * and inline eligible helpers as explicit sequence of BPF instructions
e245c5c6
AS		 3489 *
3490 * this function is called after eBPF program passed verification
3491 */
79741b3b 3492static int fixup_bpf_calls(struct bpf_verifier_env *env)
e245c5c6 3493{
79741b3b
AS		 3494 struct bpf_prog *prog = env->prog;
3495 struct bpf_insn *insn = prog->insnsi;
e245c5c6 3496 const struct bpf_func_proto *fn;
79741b3b 3497 const int insn_cnt = prog->len;
81ed18ab
AS		 3498 struct bpf_insn insn_buf[16];
3499 struct bpf_prog *new_prog;
3500 struct bpf_map *map_ptr;
3501 int i, cnt, delta = 0;
e245c5c6 3502
79741b3b
AS		 3503 for (i = 0; i < insn_cnt; i++, insn++) {
3504 if (insn->code != (BPF_JMP | BPF_CALL))
3505 continue;
e245c5c6 3506
79741b3b
AS		 3507 if (insn->imm == BPF_FUNC_get_route_realm)
3508 prog->dst_needed = 1;
3509 if (insn->imm == BPF_FUNC_get_prandom_u32)
3510 bpf_user_rnd_init_once();
79741b3b 3511 if (insn->imm == BPF_FUNC_tail_call) {
7b9f6da1
DM		 3512 /* If we tail call into other programs, we
3513 * cannot make any assumptions since they can
3514 * be replaced dynamically during runtime in
3515 * the program array.
3516 */
3517 prog->cb_access = 1;
80a58d02 3518 env->prog->aux->stack_depth = MAX_BPF_STACK;
7b9f6da1 3519
79741b3b
AS		 3520 /* mark bpf_tail_call as different opcode to avoid
3521 * conditional branch in the interpeter for every normal
3522 * call and to prevent accidental JITing by JIT compiler
3523 * that doesn't support bpf_tail_call yet
e245c5c6 3524 */
79741b3b 3525 insn->imm = 0;
71189fa9 3526 insn->code = BPF_JMP | BPF_TAIL_CALL;
79741b3b
AS		 3527 continue;
3528 }
e245c5c6 3529
81ed18ab
AS		 3530 if (ebpf_jit_enabled() && insn->imm == BPF_FUNC_map_lookup_elem) {
3531 map_ptr = env->insn_aux_data[i + delta].map_ptr;
fad73a1a
MKL		 3532 if (map_ptr == BPF_MAP_PTR_POISON ||
3533 !map_ptr->ops->map_gen_lookup)
81ed18ab
AS		 3534 goto patch_call_imm;
3535
3536 cnt = map_ptr->ops->map_gen_lookup(map_ptr, insn_buf);
3537 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) {
3538 verbose("bpf verifier is misconfigured\n");
3539 return -EINVAL;
3540 }
3541
3542 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf,
3543 cnt);
3544 if (!new_prog)
3545 return -ENOMEM;
3546
3547 delta += cnt - 1;
3548
3549 /* keep walking new program and skip insns we just inserted */
3550 env->prog = prog = new_prog;
3551 insn = new_prog->insnsi + i + delta;
3552 continue;
3553 }
3554
3555patch_call_imm:
79741b3b
AS		 3556 fn = prog->aux->ops->get_func_proto(insn->imm);
3557 /* all functions that have prototype and verifier allowed
3558 * programs to call them, must be real in-kernel functions
3559 */
3560 if (!fn->func) {
3561 verbose("kernel subsystem misconfigured func %s#%d\n",
3562 func_id_name(insn->imm), insn->imm);
3563 return -EFAULT;
e245c5c6 3564 }
79741b3b 3565 insn->imm = fn->func - __bpf_call_base;
e245c5c6 3566 }
e245c5c6 3567
79741b3b
AS		 3568 return 0;
3569}
e245c5c6 3570
58e2af8b 3571static void free_states(struct bpf_verifier_env *env)
f1bca824 3572{
58e2af8b 3573 struct bpf_verifier_state_list *sl, *sln;
f1bca824
AS		 3574 int i;
3575
3576 if (!env->explored_states)
3577 return;
3578
3579 for (i = 0; i < env->prog->len; i++) {
3580 sl = env->explored_states[i];
3581
3582 if (sl)
3583 while (sl != STATE_LIST_MARK) {
3584 sln = sl->next;
3585 kfree(sl);
3586 sl = sln;
3587 }
3588 }
3589
3590 kfree(env->explored_states);
3591}
3592
9bac3d6d 3593int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
51580e79 3594{
cbd35700 3595 char __user *log_ubuf = NULL;
58e2af8b 3596 struct bpf_verifier_env *env;
51580e79
AS		 3597 int ret = -EINVAL;
3598
58e2af8b 3599 /* 'struct bpf_verifier_env' can be global, but since it's not small,
cbd35700
AS		 3600 * allocate/free it every time bpf_check() is called
3601 */
58e2af8b 3602 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL);
cbd35700
AS		 3603 if (!env)
3604 return -ENOMEM;
3605
3df126f3
JK		 3606 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) *
3607 (*prog)->len);
3608 ret = -ENOMEM;
3609 if (!env->insn_aux_data)
3610 goto err_free_env;
9bac3d6d 3611 env->prog = *prog;
0246e64d 3612
cbd35700
AS		 3613 /* grab the mutex to protect few globals used by verifier */
3614 mutex_lock(&bpf_verifier_lock);
3615
3616 if (attr->log_level || attr->log_buf || attr->log_size) {
3617 /* user requested verbose verifier output
3618 * and supplied buffer to store the verification trace
3619 */
3620 log_level = attr->log_level;
3621 log_ubuf = (char __user *) (unsigned long) attr->log_buf;
3622 log_size = attr->log_size;
3623 log_len = 0;
3624
3625 ret = -EINVAL;
3626 /* log_* values have to be sane */
3627 if (log_size < 128 || log_size > UINT_MAX >> 8 ||
3628 log_level == 0 || log_ubuf == NULL)
3df126f3 3629 goto err_unlock;
cbd35700
AS		 3630
3631 ret = -ENOMEM;
3632 log_buf = vmalloc(log_size);
3633 if (!log_buf)
3df126f3 3634 goto err_unlock;
cbd35700
AS		 3635 } else {
3636 log_level = 0;
3637 }
1ad2f583
DB		 3638
3639 env->strict_alignment = !!(attr->prog_flags & BPF_F_STRICT_ALIGNMENT);
3640 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
e07b98d9 3641 env->strict_alignment = true;
cbd35700 3642
0246e64d
AS		 3643 ret = replace_map_fd_with_map_ptr(env);
3644 if (ret < 0)
3645 goto skip_full_check;
3646
9bac3d6d 3647 env->explored_states = kcalloc(env->prog->len,
58e2af8b 3648 sizeof(struct bpf_verifier_state_list *),
f1bca824
AS		 3649 GFP_USER);
3650 ret = -ENOMEM;
3651 if (!env->explored_states)
3652 goto skip_full_check;
3653
475fb78f
AS		 3654 ret = check_cfg(env);
3655 if (ret < 0)
3656 goto skip_full_check;
3657
1be7f75d
AS		 3658 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
3659
17a52670 3660 ret = do_check(env);
cbd35700 3661
0246e64d 3662skip_full_check:
17a52670 3663 while (pop_stack(env, NULL) >= 0);
f1bca824 3664 free_states(env);
0246e64d 3665
9bac3d6d
AS		 3666 if (ret == 0)
3667 /* program is valid, convert *(u32*)(ctx + off) accesses */
3668 ret = convert_ctx_accesses(env);
3669
e245c5c6 3670 if (ret == 0)
79741b3b 3671 ret = fixup_bpf_calls(env);
e245c5c6 3672
cbd35700
AS		 3673 if (log_level && log_len >= log_size - 1) {
3674 BUG_ON(log_len >= log_size);
3675 /* verifier log exceeded user supplied buffer */
3676 ret = -ENOSPC;
3677 /* fall through to return what was recorded */
3678 }
3679
3680 /* copy verifier log back to user space including trailing zero */
3681 if (log_level && copy_to_user(log_ubuf, log_buf, log_len + 1) != 0) {
3682 ret = -EFAULT;
3683 goto free_log_buf;
3684 }
3685
0246e64d
AS		 3686 if (ret == 0 && env->used_map_cnt) {
3687 /* if program passed verifier, update used_maps in bpf_prog_info */
9bac3d6d
AS		 3688 env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt,
3689 sizeof(env->used_maps[0]),
3690 GFP_KERNEL);
0246e64d 3691
9bac3d6d 3692 if (!env->prog->aux->used_maps) {
0246e64d
AS		 3693 ret = -ENOMEM;
3694 goto free_log_buf;
3695 }
3696
9bac3d6d 3697 memcpy(env->prog->aux->used_maps, env->used_maps,
0246e64d 3698 sizeof(env->used_maps[0]) * env->used_map_cnt);
9bac3d6d 3699 env->prog->aux->used_map_cnt = env->used_map_cnt;
0246e64d
AS		 3700
3701 /* program is valid. Convert pseudo bpf_ld_imm64 into generic
3702 * bpf_ld_imm64 instructions
3703 */
3704 convert_pseudo_ld_imm64(env);
3705 }
cbd35700
AS		 3706
3707free_log_buf:
3708 if (log_level)
3709 vfree(log_buf);
9bac3d6d 3710 if (!env->prog->aux->used_maps)
0246e64d
AS		 3711 /* if we didn't copy map pointers into bpf_prog_info, release
3712 * them now. Otherwise free_bpf_prog_info() will release them.
3713 */
3714 release_maps(env);
9bac3d6d 3715 *prog = env->prog;
3df126f3 3716err_unlock:
cbd35700 3717 mutex_unlock(&bpf_verifier_lock);
3df126f3
JK		 3718 vfree(env->insn_aux_data);
3719err_free_env:
3720 kfree(env);
51580e79
AS		 3721 return ret;
3722}
13a27dfc
JK		 3723
3724int bpf_analyzer(struct bpf_prog *prog, const struct bpf_ext_analyzer_ops *ops,
3725 void *priv)
3726{
3727 struct bpf_verifier_env *env;
3728 int ret;
3729
3730 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL);
3731 if (!env)
3732 return -ENOMEM;
3733
3734 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) *
3735 prog->len);
3736 ret = -ENOMEM;
3737 if (!env->insn_aux_data)
3738 goto err_free_env;
3739 env->prog = prog;
3740 env->analyzer_ops = ops;
3741 env->analyzer_priv = priv;
3742
3743 /* grab the mutex to protect few globals used by verifier */
3744 mutex_lock(&bpf_verifier_lock);
3745
3746 log_level = 0;
1ad2f583 3747
e07b98d9 3748 env->strict_alignment = false;
1ad2f583
DB		 3749 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
3750 env->strict_alignment = true;
13a27dfc
JK		 3751
3752 env->explored_states = kcalloc(env->prog->len,
3753 sizeof(struct bpf_verifier_state_list *),
3754 GFP_KERNEL);
3755 ret = -ENOMEM;
3756 if (!env->explored_states)
3757 goto skip_full_check;
3758
3759 ret = check_cfg(env);
3760 if (ret < 0)
3761 goto skip_full_check;
3762
3763 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
3764
3765 ret = do_check(env);
3766
3767skip_full_check:
3768 while (pop_stack(env, NULL) >= 0);
3769 free_states(env);
3770
3771 mutex_unlock(&bpf_verifier_lock);
3772 vfree(env->insn_aux_data);
3773err_free_env:
3774 kfree(env);
3775 return ret;
3776}
3777EXPORT_SYMBOL_GPL(bpf_analyzer);
Linux 6.x block layer and io_uring tree(s)