verifier.c (ab387f0af24e661fc1c2f609664ec9ae6618e3f0) verifier.c (ab3f0063c48c26c927851b6767824e35a716d878)
1/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
2 * Copyright (c) 2016 Facebook
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

--- 7 unchanged lines hidden (view full) ---

16#include <linux/bpf.h>
17#include <linux/bpf_verifier.h>
18#include <linux/filter.h>
19#include <net/netlink.h>
20#include <linux/file.h>
21#include <linux/vmalloc.h>
22#include <linux/stringify.h>
23
1/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
2 * Copyright (c) 2016 Facebook
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

--- 7 unchanged lines hidden (view full) ---

16#include <linux/bpf.h>
17#include <linux/bpf_verifier.h>
18#include <linux/filter.h>
19#include <net/netlink.h>
20#include <linux/file.h>
21#include <linux/vmalloc.h>
22#include <linux/stringify.h>
23
24#include "disasm.h"
25
26static const struct bpf_verifier_ops * const bpf_verifier_ops[] = {
27#define BPF_PROG_TYPE(_id, _name) \
28 [_id] = & _name ## _verifier_ops,
29#define BPF_MAP_TYPE(_id, _ops)
30#include <linux/bpf_types.h>
31#undef BPF_PROG_TYPE
32#undef BPF_MAP_TYPE
33};
34
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)

--- 116 unchanged lines hidden (view full) ---

148struct bpf_call_arg_meta {
149 struct bpf_map *map_ptr;
150 bool raw_mode;
151 bool pkt_access;
152 int regno;
153 int access_size;
154};
155
35/* bpf_check() is a static code analyzer that walks eBPF program
36 * instruction by instruction and updates register/stack state.
37 * All paths of conditional branches are analyzed until 'bpf_exit' insn.
38 *
39 * The first pass is depth-first-search to check that the program is a DAG.
40 * It rejects the following programs:
41 * - larger than BPF_MAXINSNS insns
42 * - if loop is present (detected via back-edge)

--- 116 unchanged lines hidden (view full) ---

159struct bpf_call_arg_meta {
160 struct bpf_map *map_ptr;
161 bool raw_mode;
162 bool pkt_access;
163 int regno;
164 int access_size;
165};
166
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 */
167static DEFINE_MUTEX(bpf_verifier_lock);
168
169/* log_level controls verbosity level of eBPF verifier.
170 * verbose() is used to dump the verification trace to the log, so the user
171 * can figure out what's wrong with the program
172 */
168static __printf(1, 2) void verbose(const char *fmt, ...)
173static __printf(2, 3) void verbose(struct bpf_verifier_env *env,
174 const char *fmt, ...)
169{
175{
176 struct bpf_verifer_log *log = &env->log;
177 unsigned int n;
170 va_list args;
171
178 va_list args;
179
172 if (log_level == 0 || log_len >= log_size - 1)
180 if (!log->level || !log->ubuf || bpf_verifier_log_full(log))
173 return;
174
175 va_start(args, fmt);
181 return;
182
183 va_start(args, fmt);
176 log_len += vscnprintf(log_buf + log_len, log_size - log_len, fmt, args);
184 n = vscnprintf(log->kbuf, BPF_VERIFIER_TMP_LOG_SIZE, fmt, args);
177 va_end(args);
185 va_end(args);
186
187 WARN_ONCE(n >= BPF_VERIFIER_TMP_LOG_SIZE - 1,
188 "verifier log line truncated - local buffer too short\n");
189
190 n = min(log->len_total - log->len_used - 1, n);
191 log->kbuf[n] = '\0';
192
193 if (!copy_to_user(log->ubuf + log->len_used, log->kbuf, n + 1))
194 log->len_used += n;
195 else
196 log->ubuf = NULL;
178}
179
197}
198
199static bool type_is_pkt_pointer(enum bpf_reg_type type)
200{
201 return type == PTR_TO_PACKET ||
202 type == PTR_TO_PACKET_META;
203}
204
180/* string representation of 'enum bpf_reg_type' */
181static const char * const reg_type_str[] = {
182 [NOT_INIT] = "?",
183 [SCALAR_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",
188 [PTR_TO_STACK] = "fp",
189 [PTR_TO_PACKET] = "pkt",
205/* string representation of 'enum bpf_reg_type' */
206static const char * const reg_type_str[] = {
207 [NOT_INIT] = "?",
208 [SCALAR_VALUE] = "inv",
209 [PTR_TO_CTX] = "ctx",
210 [CONST_PTR_TO_MAP] = "map_ptr",
211 [PTR_TO_MAP_VALUE] = "map_value",
212 [PTR_TO_MAP_VALUE_OR_NULL] = "map_value_or_null",
213 [PTR_TO_STACK] = "fp",
214 [PTR_TO_PACKET] = "pkt",
215 [PTR_TO_PACKET_META] = "pkt_meta",
190 [PTR_TO_PACKET_END] = "pkt_end",
191};
192
216 [PTR_TO_PACKET_END] = "pkt_end",
217};
218
193#define __BPF_FUNC_STR_FN(x) [BPF_FUNC_ ## x] = __stringify(bpf_ ## x)
194static const char * const func_id_str[] = {
195 __BPF_FUNC_MAPPER(__BPF_FUNC_STR_FN)
196};
197#undef __BPF_FUNC_STR_FN
198
199static const char *func_id_name(int id)
219static void print_verifier_state(struct bpf_verifier_env *env,
220 struct bpf_verifier_state *state)
200{
221{
201 BUILD_BUG_ON(ARRAY_SIZE(func_id_str) != __BPF_FUNC_MAX_ID);
202
203 if (id >= 0 && id < __BPF_FUNC_MAX_ID && func_id_str[id])
204 return func_id_str[id];
205 else
206 return "unknown";
207}
208
209static void print_verifier_state(struct bpf_verifier_state *state)
210{
211 struct bpf_reg_state *reg;
212 enum bpf_reg_type t;
213 int i;
214
215 for (i = 0; i < MAX_BPF_REG; i++) {
216 reg = &state->regs[i];
217 t = reg->type;
218 if (t == NOT_INIT)
219 continue;
222 struct bpf_reg_state *reg;
223 enum bpf_reg_type t;
224 int i;
225
226 for (i = 0; i < MAX_BPF_REG; i++) {
227 reg = &state->regs[i];
228 t = reg->type;
229 if (t == NOT_INIT)
230 continue;
220 verbose(" R%d=%s", i, reg_type_str[t]);
231 verbose(env, " R%d=%s", i, reg_type_str[t]);
221 if ((t == SCALAR_VALUE || t == PTR_TO_STACK) &&
222 tnum_is_const(reg->var_off)) {
223 /* reg->off should be 0 for SCALAR_VALUE */
232 if ((t == SCALAR_VALUE || t == PTR_TO_STACK) &&
233 tnum_is_const(reg->var_off)) {
234 /* reg->off should be 0 for SCALAR_VALUE */
224 verbose("%lld", reg->var_off.value + reg->off);
235 verbose(env, "%lld", reg->var_off.value + reg->off);
225 } else {
236 } else {
226 verbose("(id=%d", reg->id);
237 verbose(env, "(id=%d", reg->id);
227 if (t != SCALAR_VALUE)
238 if (t != SCALAR_VALUE)
228 verbose(",off=%d", reg->off);
229 if (t == PTR_TO_PACKET)
230 verbose(",r=%d", reg->range);
239 verbose(env, ",off=%d", reg->off);
240 if (type_is_pkt_pointer(t))
241 verbose(env, ",r=%d", reg->range);
231 else if (t == CONST_PTR_TO_MAP ||
232 t == PTR_TO_MAP_VALUE ||
233 t == PTR_TO_MAP_VALUE_OR_NULL)
242 else if (t == CONST_PTR_TO_MAP ||
243 t == PTR_TO_MAP_VALUE ||
244 t == PTR_TO_MAP_VALUE_OR_NULL)
234 verbose(",ks=%d,vs=%d",
245 verbose(env, ",ks=%d,vs=%d",
235 reg->map_ptr->key_size,
236 reg->map_ptr->value_size);
237 if (tnum_is_const(reg->var_off)) {
238 /* Typically an immediate SCALAR_VALUE, but
239 * could be a pointer whose offset is too big
240 * for reg->off
241 */
246 reg->map_ptr->key_size,
247 reg->map_ptr->value_size);
248 if (tnum_is_const(reg->var_off)) {
249 /* Typically an immediate SCALAR_VALUE, but
250 * could be a pointer whose offset is too big
251 * for reg->off
252 */
242 verbose(",imm=%llx", reg->var_off.value);
253 verbose(env, ",imm=%llx", reg->var_off.value);
243 } else {
244 if (reg->smin_value != reg->umin_value &&
245 reg->smin_value != S64_MIN)
254 } else {
255 if (reg->smin_value != reg->umin_value &&
256 reg->smin_value != S64_MIN)
246 verbose(",smin_value=%lld",
257 verbose(env, ",smin_value=%lld",
247 (long long)reg->smin_value);
248 if (reg->smax_value != reg->umax_value &&
249 reg->smax_value != S64_MAX)
258 (long long)reg->smin_value);
259 if (reg->smax_value != reg->umax_value &&
260 reg->smax_value != S64_MAX)
250 verbose(",smax_value=%lld",
261 verbose(env, ",smax_value=%lld",
251 (long long)reg->smax_value);
252 if (reg->umin_value != 0)
262 (long long)reg->smax_value);
263 if (reg->umin_value != 0)
253 verbose(",umin_value=%llu",
264 verbose(env, ",umin_value=%llu",
254 (unsigned long long)reg->umin_value);
255 if (reg->umax_value != U64_MAX)
265 (unsigned long long)reg->umin_value);
266 if (reg->umax_value != U64_MAX)
256 verbose(",umax_value=%llu",
267 verbose(env, ",umax_value=%llu",
257 (unsigned long long)reg->umax_value);
258 if (!tnum_is_unknown(reg->var_off)) {
259 char tn_buf[48];
260
261 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
268 (unsigned long long)reg->umax_value);
269 if (!tnum_is_unknown(reg->var_off)) {
270 char tn_buf[48];
271
272 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
262 verbose(",var_off=%s", tn_buf);
273 verbose(env, ",var_off=%s", tn_buf);
263 }
264 }
274 }
275 }
265 verbose(")");
276 verbose(env, ")");
266 }
267 }
277 }
278 }
268 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
269 if (state->stack_slot_type[i] == STACK_SPILL)
270 verbose(" fp%d=%s", -MAX_BPF_STACK + i,
271 reg_type_str[state->spilled_regs[i / BPF_REG_SIZE].type]);
279 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
280 if (state->stack[i].slot_type[0] == STACK_SPILL)
281 verbose(env, " fp%d=%s",
282 -MAX_BPF_STACK + i * BPF_REG_SIZE,
283 reg_type_str[state->stack[i].spilled_ptr.type]);
272 }
284 }
273 verbose("\n");
285 verbose(env, "\n");
274}
275
286}
287
276static const char *const bpf_class_string[] = {
277 [BPF_LD] = "ld",
278 [BPF_LDX] = "ldx",
279 [BPF_ST] = "st",
280 [BPF_STX] = "stx",
281 [BPF_ALU] = "alu",
282 [BPF_JMP] = "jmp",
283 [BPF_RET] = "BUG",
284 [BPF_ALU64] = "alu64",
285};
288static int copy_stack_state(struct bpf_verifier_state *dst,
289 const struct bpf_verifier_state *src)
290{
291 if (!src->stack)
292 return 0;
293 if (WARN_ON_ONCE(dst->allocated_stack < src->allocated_stack)) {
294 /* internal bug, make state invalid to reject the program */
295 memset(dst, 0, sizeof(*dst));
296 return -EFAULT;
297 }
298 memcpy(dst->stack, src->stack,
299 sizeof(*src->stack) * (src->allocated_stack / BPF_REG_SIZE));
300 return 0;
301}
286
302
287static const char *const bpf_alu_string[16] = {
288 [BPF_ADD >> 4] = "+=",
289 [BPF_SUB >> 4] = "-=",
290 [BPF_MUL >> 4] = "*=",
291 [BPF_DIV >> 4] = "/=",
292 [BPF_OR >> 4] = "|=",
293 [BPF_AND >> 4] = "&=",
294 [BPF_LSH >> 4] = "<<=",
295 [BPF_RSH >> 4] = ">>=",
296 [BPF_NEG >> 4] = "neg",
297 [BPF_MOD >> 4] = "%=",
298 [BPF_XOR >> 4] = "^=",
299 [BPF_MOV >> 4] = "=",
300 [BPF_ARSH >> 4] = "s>>=",
301 [BPF_END >> 4] = "endian",
302};
303
304static const char *const bpf_ldst_string[] = {
305 [BPF_W >> 3] = "u32",
306 [BPF_H >> 3] = "u16",
307 [BPF_B >> 3] = "u8",
308 [BPF_DW >> 3] = "u64",
309};
310
311static const char *const bpf_jmp_string[16] = {
312 [BPF_JA >> 4] = "jmp",
313 [BPF_JEQ >> 4] = "==",
314 [BPF_JGT >> 4] = ">",
315 [BPF_JLT >> 4] = "<",
316 [BPF_JGE >> 4] = ">=",
317 [BPF_JLE >> 4] = "<=",
318 [BPF_JSET >> 4] = "&",
319 [BPF_JNE >> 4] = "!=",
320 [BPF_JSGT >> 4] = "s>",
321 [BPF_JSLT >> 4] = "s<",
322 [BPF_JSGE >> 4] = "s>=",
323 [BPF_JSLE >> 4] = "s<=",
324 [BPF_CALL >> 4] = "call",
325 [BPF_EXIT >> 4] = "exit",
326};
327
328static void print_bpf_insn(const struct bpf_verifier_env *env,
329 const struct bpf_insn *insn)
303/* do_check() starts with zero-sized stack in struct bpf_verifier_state to
304 * make it consume minimal amount of memory. check_stack_write() access from
305 * the program calls into realloc_verifier_state() to grow the stack size.
306 * Note there is a non-zero 'parent' pointer inside bpf_verifier_state
307 * which this function copies over. It points to previous bpf_verifier_state
308 * which is never reallocated
309 */
310static int realloc_verifier_state(struct bpf_verifier_state *state, int size,
311 bool copy_old)
330{
312{
331 u8 class = BPF_CLASS(insn->code);
313 u32 old_size = state->allocated_stack;
314 struct bpf_stack_state *new_stack;
315 int slot = size / BPF_REG_SIZE;
332
316
333 if (class == BPF_ALU || class == BPF_ALU64) {
334 if (BPF_SRC(insn->code) == BPF_X)
335 verbose("(%02x) %sr%d %s %sr%d\n",
336 insn->code, class == BPF_ALU ? "(u32) " : "",
337 insn->dst_reg,
338 bpf_alu_string[BPF_OP(insn->code) >> 4],
339 class == BPF_ALU ? "(u32) " : "",
340 insn->src_reg);
341 else
342 verbose("(%02x) %sr%d %s %s%d\n",
343 insn->code, class == BPF_ALU ? "(u32) " : "",
344 insn->dst_reg,
345 bpf_alu_string[BPF_OP(insn->code) >> 4],
346 class == BPF_ALU ? "(u32) " : "",
347 insn->imm);
348 } else if (class == BPF_STX) {
349 if (BPF_MODE(insn->code) == BPF_MEM)
350 verbose("(%02x) *(%s *)(r%d %+d) = r%d\n",
351 insn->code,
352 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
353 insn->dst_reg,
354 insn->off, insn->src_reg);
355 else if (BPF_MODE(insn->code) == BPF_XADD)
356 verbose("(%02x) lock *(%s *)(r%d %+d) += r%d\n",
357 insn->code,
358 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
359 insn->dst_reg, insn->off,
360 insn->src_reg);
361 else
362 verbose("BUG_%02x\n", insn->code);
363 } else if (class == BPF_ST) {
364 if (BPF_MODE(insn->code) != BPF_MEM) {
365 verbose("BUG_st_%02x\n", insn->code);
366 return;
317 if (size <= old_size || !size) {
318 if (copy_old)
319 return 0;
320 state->allocated_stack = slot * BPF_REG_SIZE;
321 if (!size && old_size) {
322 kfree(state->stack);
323 state->stack = NULL;
367 }
324 }
368 verbose("(%02x) *(%s *)(r%d %+d) = %d\n",
369 insn->code,
370 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
371 insn->dst_reg,
372 insn->off, insn->imm);
373 } else if (class == BPF_LDX) {
374 if (BPF_MODE(insn->code) != BPF_MEM) {
375 verbose("BUG_ldx_%02x\n", insn->code);
376 return;
377 }
378 verbose("(%02x) r%d = *(%s *)(r%d %+d)\n",
379 insn->code, insn->dst_reg,
380 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
381 insn->src_reg, insn->off);
382 } else if (class == BPF_LD) {
383 if (BPF_MODE(insn->code) == BPF_ABS) {
384 verbose("(%02x) r0 = *(%s *)skb[%d]\n",
385 insn->code,
386 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
387 insn->imm);
388 } else if (BPF_MODE(insn->code) == BPF_IND) {
389 verbose("(%02x) r0 = *(%s *)skb[r%d + %d]\n",
390 insn->code,
391 bpf_ldst_string[BPF_SIZE(insn->code) >> 3],
392 insn->src_reg, insn->imm);
393 } else if (BPF_MODE(insn->code) == BPF_IMM &&
394 BPF_SIZE(insn->code) == BPF_DW) {
395 /* At this point, we already made sure that the second
396 * part of the ldimm64 insn is accessible.
397 */
398 u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm;
399 bool map_ptr = insn->src_reg == BPF_PSEUDO_MAP_FD;
325 return 0;
326 }
327 new_stack = kmalloc_array(slot, sizeof(struct bpf_stack_state),
328 GFP_KERNEL);
329 if (!new_stack)
330 return -ENOMEM;
331 if (copy_old) {
332 if (state->stack)
333 memcpy(new_stack, state->stack,
334 sizeof(*new_stack) * (old_size / BPF_REG_SIZE));
335 memset(new_stack + old_size / BPF_REG_SIZE, 0,
336 sizeof(*new_stack) * (size - old_size) / BPF_REG_SIZE);
337 }
338 state->allocated_stack = slot * BPF_REG_SIZE;
339 kfree(state->stack);
340 state->stack = new_stack;
341 return 0;
342}
400
343
401 if (map_ptr && !env->allow_ptr_leaks)
402 imm = 0;
344static void free_verifier_state(struct bpf_verifier_state *state,
345 bool free_self)
346{
347 kfree(state->stack);
348 if (free_self)
349 kfree(state);
350}
403
351
404 verbose("(%02x) r%d = 0x%llx\n", insn->code,
405 insn->dst_reg, (unsigned long long)imm);
406 } else {
407 verbose("BUG_ld_%02x\n", insn->code);
408 return;
409 }
410 } else if (class == BPF_JMP) {
411 u8 opcode = BPF_OP(insn->code);
352/* copy verifier state from src to dst growing dst stack space
353 * when necessary to accommodate larger src stack
354 */
355static int copy_verifier_state(struct bpf_verifier_state *dst,
356 const struct bpf_verifier_state *src)
357{
358 int err;
412
359
413 if (opcode == BPF_CALL) {
414 verbose("(%02x) call %s#%d\n", insn->code,
415 func_id_name(insn->imm), insn->imm);
416 } else if (insn->code == (BPF_JMP | BPF_JA)) {
417 verbose("(%02x) goto pc%+d\n",
418 insn->code, insn->off);
419 } else if (insn->code == (BPF_JMP | BPF_EXIT)) {
420 verbose("(%02x) exit\n", insn->code);
421 } else if (BPF_SRC(insn->code) == BPF_X) {
422 verbose("(%02x) if r%d %s r%d goto pc%+d\n",
423 insn->code, insn->dst_reg,
424 bpf_jmp_string[BPF_OP(insn->code) >> 4],
425 insn->src_reg, insn->off);
426 } else {
427 verbose("(%02x) if r%d %s 0x%x goto pc%+d\n",
428 insn->code, insn->dst_reg,
429 bpf_jmp_string[BPF_OP(insn->code) >> 4],
430 insn->imm, insn->off);
431 }
432 } else {
433 verbose("(%02x) %s\n", insn->code, bpf_class_string[class]);
434 }
360 err = realloc_verifier_state(dst, src->allocated_stack, false);
361 if (err)
362 return err;
363 memcpy(dst, src, offsetof(struct bpf_verifier_state, allocated_stack));
364 return copy_stack_state(dst, src);
435}
436
365}
366
437static int pop_stack(struct bpf_verifier_env *env, int *prev_insn_idx)
367static int pop_stack(struct bpf_verifier_env *env, int *prev_insn_idx,
368 int *insn_idx)
438{
369{
439 struct bpf_verifier_stack_elem *elem;
440 int insn_idx;
370 struct bpf_verifier_state *cur = env->cur_state;
371 struct bpf_verifier_stack_elem *elem, *head = env->head;
372 int err;
441
442 if (env->head == NULL)
373
374 if (env->head == NULL)
443 return -1;
375 return -ENOENT;
444
376
445 memcpy(&env->cur_state, &env->head->st, sizeof(env->cur_state));
446 insn_idx = env->head->insn_idx;
377 if (cur) {
378 err = copy_verifier_state(cur, &head->st);
379 if (err)
380 return err;
381 }
382 if (insn_idx)
383 *insn_idx = head->insn_idx;
447 if (prev_insn_idx)
384 if (prev_insn_idx)
448 *prev_insn_idx = env->head->prev_insn_idx;
449 elem = env->head->next;
450 kfree(env->head);
385 *prev_insn_idx = head->prev_insn_idx;
386 elem = head->next;
387 free_verifier_state(&head->st, false);
388 kfree(head);
451 env->head = elem;
452 env->stack_size--;
389 env->head = elem;
390 env->stack_size--;
453 return insn_idx;
391 return 0;
454}
455
456static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env,
457 int insn_idx, int prev_insn_idx)
458{
392}
393
394static struct bpf_verifier_state *push_stack(struct bpf_verifier_env *env,
395 int insn_idx, int prev_insn_idx)
396{
397 struct bpf_verifier_state *cur = env->cur_state;
459 struct bpf_verifier_stack_elem *elem;
398 struct bpf_verifier_stack_elem *elem;
399 int err;
460
400
461 elem = kmalloc(sizeof(struct bpf_verifier_stack_elem), GFP_KERNEL);
401 elem = kzalloc(sizeof(struct bpf_verifier_stack_elem), GFP_KERNEL);
462 if (!elem)
463 goto err;
464
402 if (!elem)
403 goto err;
404
465 memcpy(&elem->st, &env->cur_state, sizeof(env->cur_state));
466 elem->insn_idx = insn_idx;
467 elem->prev_insn_idx = prev_insn_idx;
468 elem->next = env->head;
469 env->head = elem;
470 env->stack_size++;
405 elem->insn_idx = insn_idx;
406 elem->prev_insn_idx = prev_insn_idx;
407 elem->next = env->head;
408 env->head = elem;
409 env->stack_size++;
410 err = copy_verifier_state(&elem->st, cur);
411 if (err)
412 goto err;
471 if (env->stack_size > BPF_COMPLEXITY_LIMIT_STACK) {
413 if (env->stack_size > BPF_COMPLEXITY_LIMIT_STACK) {
472 verbose("BPF program is too complex\n");
414 verbose(env, "BPF program is too complex\n");
473 goto err;
474 }
475 return &elem->st;
476err:
477 /* pop all elements and return */
415 goto err;
416 }
417 return &elem->st;
418err:
419 /* pop all elements and return */
478 while (pop_stack(env, NULL) >= 0);
420 while (!pop_stack(env, NULL, NULL));
479 return NULL;
480}
481
482#define CALLER_SAVED_REGS 6
483static const int caller_saved[CALLER_SAVED_REGS] = {
484 BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
485};
486

--- 15 unchanged lines hidden (view full) ---

502/* Mark the 'variable offset' part of a register as zero. This should be
503 * used only on registers holding a pointer type.
504 */
505static void __mark_reg_known_zero(struct bpf_reg_state *reg)
506{
507 __mark_reg_known(reg, 0);
508}
509
421 return NULL;
422}
423
424#define CALLER_SAVED_REGS 6
425static const int caller_saved[CALLER_SAVED_REGS] = {
426 BPF_REG_0, BPF_REG_1, BPF_REG_2, BPF_REG_3, BPF_REG_4, BPF_REG_5
427};
428

--- 15 unchanged lines hidden (view full) ---

444/* Mark the 'variable offset' part of a register as zero. This should be
445 * used only on registers holding a pointer type.
446 */
447static void __mark_reg_known_zero(struct bpf_reg_state *reg)
448{
449 __mark_reg_known(reg, 0);
450}
451
510static void mark_reg_known_zero(struct bpf_reg_state *regs, u32 regno)
452static void mark_reg_known_zero(struct bpf_verifier_env *env,
453 struct bpf_reg_state *regs, u32 regno)
511{
512 if (WARN_ON(regno >= MAX_BPF_REG)) {
454{
455 if (WARN_ON(regno >= MAX_BPF_REG)) {
513 verbose("mark_reg_known_zero(regs, %u)\n", regno);
456 verbose(env, "mark_reg_known_zero(regs, %u)\n", regno);
514 /* Something bad happened, let's kill all regs */
515 for (regno = 0; regno < MAX_BPF_REG; regno++)
516 __mark_reg_not_init(regs + regno);
517 return;
518 }
519 __mark_reg_known_zero(regs + regno);
520}
521
457 /* Something bad happened, let's kill all regs */
458 for (regno = 0; regno < MAX_BPF_REG; regno++)
459 __mark_reg_not_init(regs + regno);
460 return;
461 }
462 __mark_reg_known_zero(regs + regno);
463}
464
465static bool reg_is_pkt_pointer(const struct bpf_reg_state *reg)
466{
467 return type_is_pkt_pointer(reg->type);
468}
469
470static bool reg_is_pkt_pointer_any(const struct bpf_reg_state *reg)
471{
472 return reg_is_pkt_pointer(reg) ||
473 reg->type == PTR_TO_PACKET_END;
474}
475
476/* Unmodified PTR_TO_PACKET[_META,_END] register from ctx access. */
477static bool reg_is_init_pkt_pointer(const struct bpf_reg_state *reg,
478 enum bpf_reg_type which)
479{
480 /* The register can already have a range from prior markings.
481 * This is fine as long as it hasn't been advanced from its
482 * origin.
483 */
484 return reg->type == which &&
485 reg->id == 0 &&
486 reg->off == 0 &&
487 tnum_equals_const(reg->var_off, 0);
488}
489
522/* Attempts to improve min/max values based on var_off information */
523static void __update_reg_bounds(struct bpf_reg_state *reg)
524{
525 /* min signed is max(sign bit) | min(other bits) */
526 reg->smin_value = max_t(s64, reg->smin_value,
527 reg->var_off.value | (reg->var_off.mask & S64_MIN));
528 /* max signed is min(sign bit) | max(other bits) */
529 reg->smax_value = min_t(s64, reg->smax_value,

--- 60 unchanged lines hidden (view full) ---

590{
591 reg->type = SCALAR_VALUE;
592 reg->id = 0;
593 reg->off = 0;
594 reg->var_off = tnum_unknown;
595 __mark_reg_unbounded(reg);
596}
597
490/* Attempts to improve min/max values based on var_off information */
491static void __update_reg_bounds(struct bpf_reg_state *reg)
492{
493 /* min signed is max(sign bit) | min(other bits) */
494 reg->smin_value = max_t(s64, reg->smin_value,
495 reg->var_off.value | (reg->var_off.mask & S64_MIN));
496 /* max signed is min(sign bit) | max(other bits) */
497 reg->smax_value = min_t(s64, reg->smax_value,

--- 60 unchanged lines hidden (view full) ---

558{
559 reg->type = SCALAR_VALUE;
560 reg->id = 0;
561 reg->off = 0;
562 reg->var_off = tnum_unknown;
563 __mark_reg_unbounded(reg);
564}
565
598static void mark_reg_unknown(struct bpf_reg_state *regs, u32 regno)
566static void mark_reg_unknown(struct bpf_verifier_env *env,
567 struct bpf_reg_state *regs, u32 regno)
599{
600 if (WARN_ON(regno >= MAX_BPF_REG)) {
568{
569 if (WARN_ON(regno >= MAX_BPF_REG)) {
601 verbose("mark_reg_unknown(regs, %u)\n", regno);
570 verbose(env, "mark_reg_unknown(regs, %u)\n", regno);
602 /* Something bad happened, let's kill all regs */
603 for (regno = 0; regno < MAX_BPF_REG; regno++)
604 __mark_reg_not_init(regs + regno);
605 return;
606 }
607 __mark_reg_unknown(regs + regno);
608}
609
610static void __mark_reg_not_init(struct bpf_reg_state *reg)
611{
612 __mark_reg_unknown(reg);
613 reg->type = NOT_INIT;
614}
615
571 /* Something bad happened, let's kill all regs */
572 for (regno = 0; regno < MAX_BPF_REG; regno++)
573 __mark_reg_not_init(regs + regno);
574 return;
575 }
576 __mark_reg_unknown(regs + regno);
577}
578
579static void __mark_reg_not_init(struct bpf_reg_state *reg)
580{
581 __mark_reg_unknown(reg);
582 reg->type = NOT_INIT;
583}
584
616static void mark_reg_not_init(struct bpf_reg_state *regs, u32 regno)
585static void mark_reg_not_init(struct bpf_verifier_env *env,
586 struct bpf_reg_state *regs, u32 regno)
617{
618 if (WARN_ON(regno >= MAX_BPF_REG)) {
587{
588 if (WARN_ON(regno >= MAX_BPF_REG)) {
619 verbose("mark_reg_not_init(regs, %u)\n", regno);
589 verbose(env, "mark_reg_not_init(regs, %u)\n", regno);
620 /* Something bad happened, let's kill all regs */
621 for (regno = 0; regno < MAX_BPF_REG; regno++)
622 __mark_reg_not_init(regs + regno);
623 return;
624 }
625 __mark_reg_not_init(regs + regno);
626}
627
590 /* Something bad happened, let's kill all regs */
591 for (regno = 0; regno < MAX_BPF_REG; regno++)
592 __mark_reg_not_init(regs + regno);
593 return;
594 }
595 __mark_reg_not_init(regs + regno);
596}
597
628static void init_reg_state(struct bpf_reg_state *regs)
598static void init_reg_state(struct bpf_verifier_env *env,
599 struct bpf_reg_state *regs)
629{
630 int i;
631
632 for (i = 0; i < MAX_BPF_REG; i++) {
600{
601 int i;
602
603 for (i = 0; i < MAX_BPF_REG; i++) {
633 mark_reg_not_init(regs, i);
604 mark_reg_not_init(env, regs, i);
634 regs[i].live = REG_LIVE_NONE;
635 }
636
637 /* frame pointer */
638 regs[BPF_REG_FP].type = PTR_TO_STACK;
605 regs[i].live = REG_LIVE_NONE;
606 }
607
608 /* frame pointer */
609 regs[BPF_REG_FP].type = PTR_TO_STACK;
639 mark_reg_known_zero(regs, BPF_REG_FP);
610 mark_reg_known_zero(env, regs, BPF_REG_FP);
640
641 /* 1st arg to a function */
642 regs[BPF_REG_1].type = PTR_TO_CTX;
611
612 /* 1st arg to a function */
613 regs[BPF_REG_1].type = PTR_TO_CTX;
643 mark_reg_known_zero(regs, BPF_REG_1);
614 mark_reg_known_zero(env, regs, BPF_REG_1);
644}
645
646enum reg_arg_type {
647 SRC_OP, /* register is used as source operand */
648 DST_OP, /* register is used as destination operand */
649 DST_OP_NO_MARK /* same as above, check only, don't mark */
650};
651
652static void mark_reg_read(const struct bpf_verifier_state *state, u32 regno)
653{
654 struct bpf_verifier_state *parent = state->parent;
655
615}
616
617enum reg_arg_type {
618 SRC_OP, /* register is used as source operand */
619 DST_OP, /* register is used as destination operand */
620 DST_OP_NO_MARK /* same as above, check only, don't mark */
621};
622
623static void mark_reg_read(const struct bpf_verifier_state *state, u32 regno)
624{
625 struct bpf_verifier_state *parent = state->parent;
626
627 if (regno == BPF_REG_FP)
628 /* We don't need to worry about FP liveness because it's read-only */
629 return;
630
656 while (parent) {
657 /* if read wasn't screened by an earlier write ... */
658 if (state->regs[regno].live & REG_LIVE_WRITTEN)
659 break;
660 /* ... then we depend on parent's value */
661 parent->regs[regno].live |= REG_LIVE_READ;
662 state = parent;
663 parent = state->parent;
664 }
665}
666
667static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
668 enum reg_arg_type t)
669{
631 while (parent) {
632 /* if read wasn't screened by an earlier write ... */
633 if (state->regs[regno].live & REG_LIVE_WRITTEN)
634 break;
635 /* ... then we depend on parent's value */
636 parent->regs[regno].live |= REG_LIVE_READ;
637 state = parent;
638 parent = state->parent;
639 }
640}
641
642static int check_reg_arg(struct bpf_verifier_env *env, u32 regno,
643 enum reg_arg_type t)
644{
670 struct bpf_reg_state *regs = env->cur_state.regs;
645 struct bpf_reg_state *regs = env->cur_state->regs;
671
672 if (regno >= MAX_BPF_REG) {
646
647 if (regno >= MAX_BPF_REG) {
673 verbose("R%d is invalid\n", regno);
648 verbose(env, "R%d is invalid\n", regno);
674 return -EINVAL;
675 }
676
677 if (t == SRC_OP) {
678 /* check whether register used as source operand can be read */
679 if (regs[regno].type == NOT_INIT) {
649 return -EINVAL;
650 }
651
652 if (t == SRC_OP) {
653 /* check whether register used as source operand can be read */
654 if (regs[regno].type == NOT_INIT) {
680 verbose("R%d !read_ok\n", regno);
655 verbose(env, "R%d !read_ok\n", regno);
681 return -EACCES;
682 }
656 return -EACCES;
657 }
683 mark_reg_read(&env->cur_state, regno);
658 mark_reg_read(env->cur_state, regno);
684 } else {
685 /* check whether register used as dest operand can be written to */
686 if (regno == BPF_REG_FP) {
659 } else {
660 /* check whether register used as dest operand can be written to */
661 if (regno == BPF_REG_FP) {
687 verbose("frame pointer is read only\n");
662 verbose(env, "frame pointer is read only\n");
688 return -EACCES;
689 }
690 regs[regno].live |= REG_LIVE_WRITTEN;
691 if (t == DST_OP)
663 return -EACCES;
664 }
665 regs[regno].live |= REG_LIVE_WRITTEN;
666 if (t == DST_OP)
692 mark_reg_unknown(regs, regno);
667 mark_reg_unknown(env, regs, regno);
693 }
694 return 0;
695}
696
697static bool is_spillable_regtype(enum bpf_reg_type type)
698{
699 switch (type) {
700 case PTR_TO_MAP_VALUE:
701 case PTR_TO_MAP_VALUE_OR_NULL:
702 case PTR_TO_STACK:
703 case PTR_TO_CTX:
704 case PTR_TO_PACKET:
668 }
669 return 0;
670}
671
672static bool is_spillable_regtype(enum bpf_reg_type type)
673{
674 switch (type) {
675 case PTR_TO_MAP_VALUE:
676 case PTR_TO_MAP_VALUE_OR_NULL:
677 case PTR_TO_STACK:
678 case PTR_TO_CTX:
679 case PTR_TO_PACKET:
680 case PTR_TO_PACKET_META:
705 case PTR_TO_PACKET_END:
706 case CONST_PTR_TO_MAP:
707 return true;
708 default:
709 return false;
710 }
711}
712
713/* check_stack_read/write functions track spill/fill of registers,
714 * stack boundary and alignment are checked in check_mem_access()
715 */
681 case PTR_TO_PACKET_END:
682 case CONST_PTR_TO_MAP:
683 return true;
684 default:
685 return false;
686 }
687}
688
689/* check_stack_read/write functions track spill/fill of registers,
690 * stack boundary and alignment are checked in check_mem_access()
691 */
716static int check_stack_write(struct bpf_verifier_state *state, int off,
692static int check_stack_write(struct bpf_verifier_env *env,
693 struct bpf_verifier_state *state, int off,
717 int size, int value_regno)
718{
694 int size, int value_regno)
695{
719 int i, spi = (MAX_BPF_STACK + off) / BPF_REG_SIZE;
696 int i, slot = -off - 1, spi = slot / BPF_REG_SIZE, err;
697
698 err = realloc_verifier_state(state, round_up(slot + 1, BPF_REG_SIZE),
699 true);
700 if (err)
701 return err;
720 /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
721 * so it's aligned access and [off, off + size) are within stack limits
722 */
702 /* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
703 * so it's aligned access and [off, off + size) are within stack limits
704 */
705 if (!env->allow_ptr_leaks &&
706 state->stack[spi].slot_type[0] == STACK_SPILL &&
707 size != BPF_REG_SIZE) {
708 verbose(env, "attempt to corrupt spilled pointer on stack\n");
709 return -EACCES;
710 }
723
724 if (value_regno >= 0 &&
725 is_spillable_regtype(state->regs[value_regno].type)) {
726
727 /* register containing pointer is being spilled into stack */
728 if (size != BPF_REG_SIZE) {
711
712 if (value_regno >= 0 &&
713 is_spillable_regtype(state->regs[value_regno].type)) {
714
715 /* register containing pointer is being spilled into stack */
716 if (size != BPF_REG_SIZE) {
729 verbose("invalid size of register spill\n");
717 verbose(env, "invalid size of register spill\n");
730 return -EACCES;
731 }
732
733 /* save register state */
718 return -EACCES;
719 }
720
721 /* save register state */
734 state->spilled_regs[spi] = state->regs[value_regno];
735 state->spilled_regs[spi].live |= REG_LIVE_WRITTEN;
722 state->stack[spi].spilled_ptr = state->regs[value_regno];
723 state->stack[spi].spilled_ptr.live |= REG_LIVE_WRITTEN;
736
737 for (i = 0; i < BPF_REG_SIZE; i++)
724
725 for (i = 0; i < BPF_REG_SIZE; i++)
738 state->stack_slot_type[MAX_BPF_STACK + off + i] = STACK_SPILL;
726 state->stack[spi].slot_type[i] = STACK_SPILL;
739 } else {
740 /* regular write of data into stack */
727 } else {
728 /* regular write of data into stack */
741 state->spilled_regs[spi] = (struct bpf_reg_state) {};
729 state->stack[spi].spilled_ptr = (struct bpf_reg_state) {};
742
743 for (i = 0; i < size; i++)
730
731 for (i = 0; i < size; i++)
744 state->stack_slot_type[MAX_BPF_STACK + off + i] = STACK_MISC;
732 state->stack[spi].slot_type[(slot - i) % BPF_REG_SIZE] =
733 STACK_MISC;
745 }
746 return 0;
747}
748
749static void mark_stack_slot_read(const struct bpf_verifier_state *state, int slot)
750{
751 struct bpf_verifier_state *parent = state->parent;
752
753 while (parent) {
754 /* if read wasn't screened by an earlier write ... */
734 }
735 return 0;
736}
737
738static void mark_stack_slot_read(const struct bpf_verifier_state *state, int slot)
739{
740 struct bpf_verifier_state *parent = state->parent;
741
742 while (parent) {
743 /* if read wasn't screened by an earlier write ... */
755 if (state->spilled_regs[slot].live & REG_LIVE_WRITTEN)
744 if (state->stack[slot].spilled_ptr.live & REG_LIVE_WRITTEN)
756 break;
757 /* ... then we depend on parent's value */
745 break;
746 /* ... then we depend on parent's value */
758 parent->spilled_regs[slot].live |= REG_LIVE_READ;
747 parent->stack[slot].spilled_ptr.live |= REG_LIVE_READ;
759 state = parent;
760 parent = state->parent;
761 }
762}
763
748 state = parent;
749 parent = state->parent;
750 }
751}
752
764static int check_stack_read(struct bpf_verifier_state *state, int off, int size,
753static int check_stack_read(struct bpf_verifier_env *env,
754 struct bpf_verifier_state *state, int off, int size,
765 int value_regno)
766{
755 int value_regno)
756{
767 u8 *slot_type;
768 int i, spi;
757 int i, slot = -off - 1, spi = slot / BPF_REG_SIZE;
758 u8 *stype;
769
759
770 slot_type = &state->stack_slot_type[MAX_BPF_STACK + off];
760 if (state->allocated_stack <= slot) {
761 verbose(env, "invalid read from stack off %d+0 size %d\n",
762 off, size);
763 return -EACCES;
764 }
765 stype = state->stack[spi].slot_type;
771
766
772 if (slot_type[0] == STACK_SPILL) {
767 if (stype[0] == STACK_SPILL) {
773 if (size != BPF_REG_SIZE) {
768 if (size != BPF_REG_SIZE) {
774 verbose("invalid size of register spill\n");
769 verbose(env, "invalid size of register spill\n");
775 return -EACCES;
776 }
777 for (i = 1; i < BPF_REG_SIZE; i++) {
770 return -EACCES;
771 }
772 for (i = 1; i < BPF_REG_SIZE; i++) {
778 if (slot_type[i] != STACK_SPILL) {
779 verbose("corrupted spill memory\n");
773 if (stype[(slot - i) % BPF_REG_SIZE] != STACK_SPILL) {
774 verbose(env, "corrupted spill memory\n");
780 return -EACCES;
781 }
782 }
783
775 return -EACCES;
776 }
777 }
778
784 spi = (MAX_BPF_STACK + off) / BPF_REG_SIZE;
785
786 if (value_regno >= 0) {
787 /* restore register state from stack */
779 if (value_regno >= 0) {
780 /* restore register state from stack */
788 state->regs[value_regno] = state->spilled_regs[spi];
781 state->regs[value_regno] = state->stack[spi].spilled_ptr;
789 mark_stack_slot_read(state, spi);
790 }
791 return 0;
792 } else {
793 for (i = 0; i < size; i++) {
782 mark_stack_slot_read(state, spi);
783 }
784 return 0;
785 } else {
786 for (i = 0; i < size; i++) {
794 if (slot_type[i] != STACK_MISC) {
795 verbose("invalid read from stack off %d+%d size %d\n",
787 if (stype[(slot - i) % BPF_REG_SIZE] != STACK_MISC) {
788 verbose(env, "invalid read from stack off %d+%d size %d\n",
796 off, i, size);
797 return -EACCES;
798 }
799 }
800 if (value_regno >= 0)
801 /* have read misc data from the stack */
789 off, i, size);
790 return -EACCES;
791 }
792 }
793 if (value_regno >= 0)
794 /* have read misc data from the stack */
802 mark_reg_unknown(state->regs, value_regno);
795 mark_reg_unknown(env, state->regs, value_regno);
803 return 0;
804 }
805}
806
807/* check read/write into map element returned by bpf_map_lookup_elem() */
808static int __check_map_access(struct bpf_verifier_env *env, u32 regno, int off,
809 int size)
810{
796 return 0;
797 }
798}
799
800/* check read/write into map element returned by bpf_map_lookup_elem() */
801static int __check_map_access(struct bpf_verifier_env *env, u32 regno, int off,
802 int size)
803{
811 struct bpf_map *map = env->cur_state.regs[regno].map_ptr;
804 struct bpf_reg_state *regs = cur_regs(env);
805 struct bpf_map *map = regs[regno].map_ptr;
812
813 if (off < 0 || size <= 0 || off + size > map->value_size) {
806
807 if (off < 0 || size <= 0 || off + size > map->value_size) {
814 verbose("invalid access to map value, value_size=%d off=%d size=%d\n",
808 verbose(env, "invalid access to map value, value_size=%d off=%d size=%d\n",
815 map->value_size, off, size);
816 return -EACCES;
817 }
818 return 0;
819}
820
821/* check read/write into a map element with possible variable offset */
822static int check_map_access(struct bpf_verifier_env *env, u32 regno,
809 map->value_size, off, size);
810 return -EACCES;
811 }
812 return 0;
813}
814
815/* check read/write into a map element with possible variable offset */
816static int check_map_access(struct bpf_verifier_env *env, u32 regno,
823 int off, int size)
817 int off, int size)
824{
818{
825 struct bpf_verifier_state *state = &env->cur_state;
819 struct bpf_verifier_state *state = env->cur_state;
826 struct bpf_reg_state *reg = &state->regs[regno];
827 int err;
828
829 /* We may have adjusted the register to this map value, so we
830 * need to try adding each of min_value and max_value to off
831 * to make sure our theoretical access will be safe.
832 */
820 struct bpf_reg_state *reg = &state->regs[regno];
821 int err;
822
823 /* We may have adjusted the register to this map value, so we
824 * need to try adding each of min_value and max_value to off
825 * to make sure our theoretical access will be safe.
826 */
833 if (log_level)
834 print_verifier_state(state);
827 if (env->log.level)
828 print_verifier_state(env, state);
835 /* The minimum value is only important with signed
836 * comparisons where we can't assume the floor of a
837 * value is 0. If we are using signed variables for our
838 * index'es we need to make sure that whatever we use
839 * will have a set floor within our range.
840 */
841 if (reg->smin_value < 0) {
829 /* The minimum value is only important with signed
830 * comparisons where we can't assume the floor of a
831 * value is 0. If we are using signed variables for our
832 * index'es we need to make sure that whatever we use
833 * will have a set floor within our range.
834 */
835 if (reg->smin_value < 0) {
842 verbose("R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
836 verbose(env, "R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
843 regno);
844 return -EACCES;
845 }
846 err = __check_map_access(env, regno, reg->smin_value + off, size);
847 if (err) {
837 regno);
838 return -EACCES;
839 }
840 err = __check_map_access(env, regno, reg->smin_value + off, size);
841 if (err) {
848 verbose("R%d min value is outside of the array range\n", regno);
842 verbose(env, "R%d min value is outside of the array range\n",
843 regno);
849 return err;
850 }
851
852 /* If we haven't set a max value then we need to bail since we can't be
853 * sure we won't do bad things.
854 * If reg->umax_value + off could overflow, treat that as unbounded too.
855 */
856 if (reg->umax_value >= BPF_MAX_VAR_OFF) {
844 return err;
845 }
846
847 /* If we haven't set a max value then we need to bail since we can't be
848 * sure we won't do bad things.
849 * If reg->umax_value + off could overflow, treat that as unbounded too.
850 */
851 if (reg->umax_value >= BPF_MAX_VAR_OFF) {
857 verbose("R%d unbounded memory access, make sure to bounds check any array access into a map\n",
852 verbose(env, "R%d unbounded memory access, make sure to bounds check any array access into a map\n",
858 regno);
859 return -EACCES;
860 }
861 err = __check_map_access(env, regno, reg->umax_value + off, size);
862 if (err)
853 regno);
854 return -EACCES;
855 }
856 err = __check_map_access(env, regno, reg->umax_value + off, size);
857 if (err)
863 verbose("R%d max value is outside of the array range\n", regno);
858 verbose(env, "R%d max value is outside of the array range\n",
859 regno);
864 return err;
865}
866
867#define MAX_PACKET_OFF 0xffff
868
869static bool may_access_direct_pkt_data(struct bpf_verifier_env *env,
870 const struct bpf_call_arg_meta *meta,
871 enum bpf_access_type t)

--- 18 unchanged lines hidden (view full) ---

890 default:
891 return false;
892 }
893}
894
895static int __check_packet_access(struct bpf_verifier_env *env, u32 regno,
896 int off, int size)
897{
860 return err;
861}
862
863#define MAX_PACKET_OFF 0xffff
864
865static bool may_access_direct_pkt_data(struct bpf_verifier_env *env,
866 const struct bpf_call_arg_meta *meta,
867 enum bpf_access_type t)

--- 18 unchanged lines hidden (view full) ---

886 default:
887 return false;
888 }
889}
890
891static int __check_packet_access(struct bpf_verifier_env *env, u32 regno,
892 int off, int size)
893{
898 struct bpf_reg_state *regs = env->cur_state.regs;
894 struct bpf_reg_state *regs = cur_regs(env);
899 struct bpf_reg_state *reg = &regs[regno];
900
901 if (off < 0 || size <= 0 || (u64)off + size > reg->range) {
895 struct bpf_reg_state *reg = &regs[regno];
896
897 if (off < 0 || size <= 0 || (u64)off + size > reg->range) {
902 verbose("invalid access to packet, off=%d size=%d, R%d(id=%d,off=%d,r=%d)\n",
898 verbose(env, "invalid access to packet, off=%d size=%d, R%d(id=%d,off=%d,r=%d)\n",
903 off, size, regno, reg->id, reg->off, reg->range);
904 return -EACCES;
905 }
906 return 0;
907}
908
909static int check_packet_access(struct bpf_verifier_env *env, u32 regno, int off,
910 int size)
911{
899 off, size, regno, reg->id, reg->off, reg->range);
900 return -EACCES;
901 }
902 return 0;
903}
904
905static int check_packet_access(struct bpf_verifier_env *env, u32 regno, int off,
906 int size)
907{
912 struct bpf_reg_state *regs = env->cur_state.regs;
908 struct bpf_reg_state *regs = cur_regs(env);
913 struct bpf_reg_state *reg = &regs[regno];
914 int err;
915
916 /* We may have added a variable offset to the packet pointer; but any
917 * reg->range we have comes after that. We are only checking the fixed
918 * offset.
919 */
920
921 /* We don't allow negative numbers, because we aren't tracking enough
922 * detail to prove they're safe.
923 */
924 if (reg->smin_value < 0) {
909 struct bpf_reg_state *reg = &regs[regno];
910 int err;
911
912 /* We may have added a variable offset to the packet pointer; but any
913 * reg->range we have comes after that. We are only checking the fixed
914 * offset.
915 */
916
917 /* We don't allow negative numbers, because we aren't tracking enough
918 * detail to prove they're safe.
919 */
920 if (reg->smin_value < 0) {
925 verbose("R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
921 verbose(env, "R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n",
926 regno);
927 return -EACCES;
928 }
929 err = __check_packet_access(env, regno, off, size);
930 if (err) {
922 regno);
923 return -EACCES;
924 }
925 err = __check_packet_access(env, regno, off, size);
926 if (err) {
931 verbose("R%d offset is outside of the packet\n", regno);
927 verbose(env, "R%d offset is outside of the packet\n", regno);
932 return err;
933 }
934 return err;
935}
936
937/* check access to 'struct bpf_context' fields. Supports fixed offsets only */
938static int check_ctx_access(struct bpf_verifier_env *env, int insn_idx, int off, int size,
939 enum bpf_access_type t, enum bpf_reg_type *reg_type)
940{
941 struct bpf_insn_access_aux info = {
942 .reg_type = *reg_type,
943 };
944
928 return err;
929 }
930 return err;
931}
932
933/* check access to 'struct bpf_context' fields. Supports fixed offsets only */
934static int check_ctx_access(struct bpf_verifier_env *env, int insn_idx, int off, int size,
935 enum bpf_access_type t, enum bpf_reg_type *reg_type)
936{
937 struct bpf_insn_access_aux info = {
938 .reg_type = *reg_type,
939 };
940
945 /* for analyzer ctx accesses are already validated and converted */
946 if (env->analyzer_ops)
947 return 0;
948
949 if (env->prog->aux->ops->is_valid_access &&
950 env->prog->aux->ops->is_valid_access(off, size, t, &info)) {
941 if (env->ops->is_valid_access &&
942 env->ops->is_valid_access(off, size, t, &info)) {
951 /* A non zero info.ctx_field_size indicates that this field is a
952 * candidate for later verifier transformation to load the whole
953 * field and then apply a mask when accessed with a narrower
954 * access than actual ctx access size. A zero info.ctx_field_size
955 * will only allow for whole field access and rejects any other
956 * type of narrower access.
957 */
943 /* A non zero info.ctx_field_size indicates that this field is a
944 * candidate for later verifier transformation to load the whole
945 * field and then apply a mask when accessed with a narrower
946 * access than actual ctx access size. A zero info.ctx_field_size
947 * will only allow for whole field access and rejects any other
948 * type of narrower access.
949 */
958 env->insn_aux_data[insn_idx].ctx_field_size = info.ctx_field_size;
959 *reg_type = info.reg_type;
960
950 *reg_type = info.reg_type;
951
952 if (env->analyzer_ops)
953 return 0;
954
955 env->insn_aux_data[insn_idx].ctx_field_size = info.ctx_field_size;
961 /* remember the offset of last byte accessed in ctx */
962 if (env->prog->aux->max_ctx_offset < off + size)
963 env->prog->aux->max_ctx_offset = off + size;
964 return 0;
965 }
966
956 /* remember the offset of last byte accessed in ctx */
957 if (env->prog->aux->max_ctx_offset < off + size)
958 env->prog->aux->max_ctx_offset = off + size;
959 return 0;
960 }
961
967 verbose("invalid bpf_context access off=%d size=%d\n", off, size);
962 verbose(env, "invalid bpf_context access off=%d size=%d\n", off, size);
968 return -EACCES;
969}
970
971static bool __is_pointer_value(bool allow_ptr_leaks,
972 const struct bpf_reg_state *reg)
973{
974 if (allow_ptr_leaks)
975 return false;
976
977 return reg->type != SCALAR_VALUE;
978}
979
980static bool is_pointer_value(struct bpf_verifier_env *env, int regno)
981{
963 return -EACCES;
964}
965
966static bool __is_pointer_value(bool allow_ptr_leaks,
967 const struct bpf_reg_state *reg)
968{
969 if (allow_ptr_leaks)
970 return false;
971
972 return reg->type != SCALAR_VALUE;
973}
974
975static bool is_pointer_value(struct bpf_verifier_env *env, int regno)
976{
982 return __is_pointer_value(env->allow_ptr_leaks, &env->cur_state.regs[regno]);
977 return __is_pointer_value(env->allow_ptr_leaks, cur_regs(env) + regno);
983}
984
978}
979
985static int check_pkt_ptr_alignment(const struct bpf_reg_state *reg,
980static int check_pkt_ptr_alignment(struct bpf_verifier_env *env,
981 const struct bpf_reg_state *reg,
986 int off, int size, bool strict)
987{
988 struct tnum reg_off;
989 int ip_align;
990
991 /* Byte size accesses are always allowed. */
992 if (!strict || size == 1)
993 return 0;

--- 8 unchanged lines hidden (view full) ---

1002 */
1003 ip_align = 2;
1004
1005 reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
1006 if (!tnum_is_aligned(reg_off, size)) {
1007 char tn_buf[48];
1008
1009 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
982 int off, int size, bool strict)
983{
984 struct tnum reg_off;
985 int ip_align;
986
987 /* Byte size accesses are always allowed. */
988 if (!strict || size == 1)
989 return 0;

--- 8 unchanged lines hidden (view full) ---

998 */
999 ip_align = 2;
1000
1001 reg_off = tnum_add(reg->var_off, tnum_const(ip_align + reg->off + off));
1002 if (!tnum_is_aligned(reg_off, size)) {
1003 char tn_buf[48];
1004
1005 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1010 verbose("misaligned packet access off %d+%s+%d+%d size %d\n",
1006 verbose(env,
1007 "misaligned packet access off %d+%s+%d+%d size %d\n",
1011 ip_align, tn_buf, reg->off, off, size);
1012 return -EACCES;
1013 }
1014
1015 return 0;
1016}
1017
1008 ip_align, tn_buf, reg->off, off, size);
1009 return -EACCES;
1010 }
1011
1012 return 0;
1013}
1014
1018static int check_generic_ptr_alignment(const struct bpf_reg_state *reg,
1015static int check_generic_ptr_alignment(struct bpf_verifier_env *env,
1016 const struct bpf_reg_state *reg,
1019 const char *pointer_desc,
1020 int off, int size, bool strict)
1021{
1022 struct tnum reg_off;
1023
1024 /* Byte size accesses are always allowed. */
1025 if (!strict || size == 1)
1026 return 0;
1027
1028 reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
1029 if (!tnum_is_aligned(reg_off, size)) {
1030 char tn_buf[48];
1031
1032 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1017 const char *pointer_desc,
1018 int off, int size, bool strict)
1019{
1020 struct tnum reg_off;
1021
1022 /* Byte size accesses are always allowed. */
1023 if (!strict || size == 1)
1024 return 0;
1025
1026 reg_off = tnum_add(reg->var_off, tnum_const(reg->off + off));
1027 if (!tnum_is_aligned(reg_off, size)) {
1028 char tn_buf[48];
1029
1030 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1033 verbose("misaligned %saccess off %s+%d+%d size %d\n",
1031 verbose(env, "misaligned %saccess off %s+%d+%d size %d\n",
1034 pointer_desc, tn_buf, reg->off, off, size);
1035 return -EACCES;
1036 }
1037
1038 return 0;
1039}
1040
1041static int check_ptr_alignment(struct bpf_verifier_env *env,
1042 const struct bpf_reg_state *reg,
1043 int off, int size)
1044{
1045 bool strict = env->strict_alignment;
1046 const char *pointer_desc = "";
1047
1048 switch (reg->type) {
1049 case PTR_TO_PACKET:
1032 pointer_desc, tn_buf, reg->off, off, size);
1033 return -EACCES;
1034 }
1035
1036 return 0;
1037}
1038
1039static int check_ptr_alignment(struct bpf_verifier_env *env,
1040 const struct bpf_reg_state *reg,
1041 int off, int size)
1042{
1043 bool strict = env->strict_alignment;
1044 const char *pointer_desc = "";
1045
1046 switch (reg->type) {
1047 case PTR_TO_PACKET:
1050 /* special case, because of NET_IP_ALIGN */
1051 return check_pkt_ptr_alignment(reg, off, size, strict);
1048 case PTR_TO_PACKET_META:
1049 /* Special case, because of NET_IP_ALIGN. Given metadata sits
1050 * right in front, treat it the very same way.
1051 */
1052 return check_pkt_ptr_alignment(env, reg, off, size, strict);
1052 case PTR_TO_MAP_VALUE:
1053 pointer_desc = "value ";
1054 break;
1055 case PTR_TO_CTX:
1056 pointer_desc = "context ";
1057 break;
1058 case PTR_TO_STACK:
1059 pointer_desc = "stack ";
1060 break;
1061 default:
1062 break;
1063 }
1053 case PTR_TO_MAP_VALUE:
1054 pointer_desc = "value ";
1055 break;
1056 case PTR_TO_CTX:
1057 pointer_desc = "context ";
1058 break;
1059 case PTR_TO_STACK:
1060 pointer_desc = "stack ";
1061 break;
1062 default:
1063 break;
1064 }
1064 return check_generic_ptr_alignment(reg, pointer_desc, off, size, strict);
1065 return check_generic_ptr_alignment(env, reg, pointer_desc, off, size,
1066 strict);
1065}
1066
1067/* check whether memory at (regno + off) is accessible for t = (read | write)
1068 * if t==write, value_regno is a register which value is stored into memory
1069 * if t==read, value_regno is a register which will receive the value from memory
1070 * if t==write && value_regno==-1, some unknown value is stored into memory
1071 * if t==read && value_regno==-1, don't care what we read from memory
1072 */
1073static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno, int off,
1074 int bpf_size, enum bpf_access_type t,
1075 int value_regno)
1076{
1067}
1068
1069/* check whether memory at (regno + off) is accessible for t = (read | write)
1070 * if t==write, value_regno is a register which value is stored into memory
1071 * if t==read, value_regno is a register which will receive the value from memory
1072 * if t==write && value_regno==-1, some unknown value is stored into memory
1073 * if t==read && value_regno==-1, don't care what we read from memory
1074 */
1075static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regno, int off,
1076 int bpf_size, enum bpf_access_type t,
1077 int value_regno)
1078{
1077 struct bpf_verifier_state *state = &env->cur_state;
1078 struct bpf_reg_state *reg = &state->regs[regno];
1079 struct bpf_verifier_state *state = env->cur_state;
1080 struct bpf_reg_state *regs = cur_regs(env);
1081 struct bpf_reg_state *reg = regs + regno;
1079 int size, err = 0;
1080
1081 size = bpf_size_to_bytes(bpf_size);
1082 if (size < 0)
1083 return size;
1084
1085 /* alignment checks will add in reg->off themselves */
1086 err = check_ptr_alignment(env, reg, off, size);
1087 if (err)
1088 return err;
1089
1090 /* for access checks, reg->off is just part of off */
1091 off += reg->off;
1092
1093 if (reg->type == PTR_TO_MAP_VALUE) {
1094 if (t == BPF_WRITE && value_regno >= 0 &&
1095 is_pointer_value(env, value_regno)) {
1082 int size, err = 0;
1083
1084 size = bpf_size_to_bytes(bpf_size);
1085 if (size < 0)
1086 return size;
1087
1088 /* alignment checks will add in reg->off themselves */
1089 err = check_ptr_alignment(env, reg, off, size);
1090 if (err)
1091 return err;
1092
1093 /* for access checks, reg->off is just part of off */
1094 off += reg->off;
1095
1096 if (reg->type == PTR_TO_MAP_VALUE) {
1097 if (t == BPF_WRITE && value_regno >= 0 &&
1098 is_pointer_value(env, value_regno)) {
1096 verbose("R%d leaks addr into map\n", value_regno);
1099 verbose(env, "R%d leaks addr into map\n", value_regno);
1097 return -EACCES;
1098 }
1099
1100 err = check_map_access(env, regno, off, size);
1101 if (!err && t == BPF_READ && value_regno >= 0)
1100 return -EACCES;
1101 }
1102
1103 err = check_map_access(env, regno, off, size);
1104 if (!err && t == BPF_READ && value_regno >= 0)
1102 mark_reg_unknown(state->regs, value_regno);
1105 mark_reg_unknown(env, regs, value_regno);
1103
1104 } else if (reg->type == PTR_TO_CTX) {
1105 enum bpf_reg_type reg_type = SCALAR_VALUE;
1106
1107 if (t == BPF_WRITE && value_regno >= 0 &&
1108 is_pointer_value(env, value_regno)) {
1106
1107 } else if (reg->type == PTR_TO_CTX) {
1108 enum bpf_reg_type reg_type = SCALAR_VALUE;
1109
1110 if (t == BPF_WRITE && value_regno >= 0 &&
1111 is_pointer_value(env, value_regno)) {
1109 verbose("R%d leaks addr into ctx\n", value_regno);
1112 verbose(env, "R%d leaks addr into ctx\n", value_regno);
1110 return -EACCES;
1111 }
1112 /* ctx accesses must be at a fixed offset, so that we can
1113 * determine what type of data were returned.
1114 */
1113 return -EACCES;
1114 }
1115 /* ctx accesses must be at a fixed offset, so that we can
1116 * determine what type of data were returned.
1117 */
1115 if (!tnum_is_const(reg->var_off)) {
1118 if (reg->off) {
1119 verbose(env,
1120 "dereference of modified ctx ptr R%d off=%d+%d, ctx+const is allowed, ctx+const+const is not\n",
1121 regno, reg->off, off - reg->off);
1122 return -EACCES;
1123 }
1124 if (!tnum_is_const(reg->var_off) || reg->var_off.value) {
1116 char tn_buf[48];
1117
1118 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1125 char tn_buf[48];
1126
1127 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1119 verbose("variable ctx access var_off=%s off=%d size=%d",
1128 verbose(env,
1129 "variable ctx access var_off=%s off=%d size=%d",
1120 tn_buf, off, size);
1121 return -EACCES;
1122 }
1130 tn_buf, off, size);
1131 return -EACCES;
1132 }
1123 off += reg->var_off.value;
1124 err = check_ctx_access(env, insn_idx, off, size, t, &reg_type);
1125 if (!err && t == BPF_READ && value_regno >= 0) {
1126 /* ctx access returns either a scalar, or a
1133 err = check_ctx_access(env, insn_idx, off, size, t, &reg_type);
1134 if (!err && t == BPF_READ && value_regno >= 0) {
1135 /* ctx access returns either a scalar, or a
1127 * PTR_TO_PACKET[_END]. In the latter case, we know
1128 * the offset is zero.
1136 * PTR_TO_PACKET[_META,_END]. In the latter
1137 * case, we know the offset is zero.
1129 */
1130 if (reg_type == SCALAR_VALUE)
1138 */
1139 if (reg_type == SCALAR_VALUE)
1131 mark_reg_unknown(state->regs, value_regno);
1140 mark_reg_unknown(env, regs, value_regno);
1132 else
1141 else
1133 mark_reg_known_zero(state->regs, value_regno);
1134 state->regs[value_regno].id = 0;
1135 state->regs[value_regno].off = 0;
1136 state->regs[value_regno].range = 0;
1137 state->regs[value_regno].type = reg_type;
1142 mark_reg_known_zero(env, regs,
1143 value_regno);
1144 regs[value_regno].id = 0;
1145 regs[value_regno].off = 0;
1146 regs[value_regno].range = 0;
1147 regs[value_regno].type = reg_type;
1138 }
1139
1140 } else if (reg->type == PTR_TO_STACK) {
1141 /* stack accesses must be at a fixed offset, so that we can
1142 * determine what type of data were returned.
1143 * See check_stack_read().
1144 */
1145 if (!tnum_is_const(reg->var_off)) {
1146 char tn_buf[48];
1147
1148 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1148 }
1149
1150 } else if (reg->type == PTR_TO_STACK) {
1151 /* stack accesses must be at a fixed offset, so that we can
1152 * determine what type of data were returned.
1153 * See check_stack_read().
1154 */
1155 if (!tnum_is_const(reg->var_off)) {
1156 char tn_buf[48];
1157
1158 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
1149 verbose("variable stack access var_off=%s off=%d size=%d",
1159 verbose(env, "variable stack access var_off=%s off=%d size=%d",
1150 tn_buf, off, size);
1151 return -EACCES;
1152 }
1153 off += reg->var_off.value;
1154 if (off >= 0 || off < -MAX_BPF_STACK) {
1160 tn_buf, off, size);
1161 return -EACCES;
1162 }
1163 off += reg->var_off.value;
1164 if (off >= 0 || off < -MAX_BPF_STACK) {
1155 verbose("invalid stack off=%d size=%d\n", off, size);
1165 verbose(env, "invalid stack off=%d size=%d\n", off,
1166 size);
1156 return -EACCES;
1157 }
1158
1159 if (env->prog->aux->stack_depth < -off)
1160 env->prog->aux->stack_depth = -off;
1161
1167 return -EACCES;
1168 }
1169
1170 if (env->prog->aux->stack_depth < -off)
1171 env->prog->aux->stack_depth = -off;
1172
1162 if (t == BPF_WRITE) {
1163 if (!env->allow_ptr_leaks &&
1164 state->stack_slot_type[MAX_BPF_STACK + off] == STACK_SPILL &&
1165 size != BPF_REG_SIZE) {
1166 verbose("attempt to corrupt spilled pointer on stack\n");
1167 return -EACCES;
1168 }
1169 err = check_stack_write(state, off, size, value_regno);
1170 } else {
1171 err = check_stack_read(state, off, size, value_regno);
1172 }
1173 } else if (reg->type == PTR_TO_PACKET) {
1173 if (t == BPF_WRITE)
1174 err = check_stack_write(env, state, off, size,
1175 value_regno);
1176 else
1177 err = check_stack_read(env, state, off, size,
1178 value_regno);
1179 } else if (reg_is_pkt_pointer(reg)) {
1174 if (t == BPF_WRITE && !may_access_direct_pkt_data(env, NULL, t)) {
1180 if (t == BPF_WRITE && !may_access_direct_pkt_data(env, NULL, t)) {
1175 verbose("cannot write into packet\n");
1181 verbose(env, "cannot write into packet\n");
1176 return -EACCES;
1177 }
1178 if (t == BPF_WRITE && value_regno >= 0 &&
1179 is_pointer_value(env, value_regno)) {
1182 return -EACCES;
1183 }
1184 if (t == BPF_WRITE && value_regno >= 0 &&
1185 is_pointer_value(env, value_regno)) {
1180 verbose("R%d leaks addr into packet\n", value_regno);
1186 verbose(env, "R%d leaks addr into packet\n",
1187 value_regno);
1181 return -EACCES;
1182 }
1183 err = check_packet_access(env, regno, off, size);
1184 if (!err && t == BPF_READ && value_regno >= 0)
1188 return -EACCES;
1189 }
1190 err = check_packet_access(env, regno, off, size);
1191 if (!err && t == BPF_READ && value_regno >= 0)
1185 mark_reg_unknown(state->regs, value_regno);
1192 mark_reg_unknown(env, regs, value_regno);
1186 } else {
1193 } else {
1187 verbose("R%d invalid mem access '%s'\n",
1188 regno, reg_type_str[reg->type]);
1194 verbose(env, "R%d invalid mem access '%s'\n", regno,
1195 reg_type_str[reg->type]);
1189 return -EACCES;
1190 }
1191
1192 if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
1196 return -EACCES;
1197 }
1198
1199 if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
1193 state->regs[value_regno].type == SCALAR_VALUE) {
1200 regs[value_regno].type == SCALAR_VALUE) {
1194 /* b/h/w load zero-extends, mark upper bits as known 0 */
1201 /* b/h/w load zero-extends, mark upper bits as known 0 */
1195 state->regs[value_regno].var_off = tnum_cast(
1196 state->regs[value_regno].var_off, size);
1197 __update_reg_bounds(&state->regs[value_regno]);
1202 regs[value_regno].var_off =
1203 tnum_cast(regs[value_regno].var_off, size);
1204 __update_reg_bounds(&regs[value_regno]);
1198 }
1199 return err;
1200}
1201
1202static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn)
1203{
1204 int err;
1205
1206 if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
1207 insn->imm != 0) {
1205 }
1206 return err;
1207}
1208
1209static int check_xadd(struct bpf_verifier_env *env, int insn_idx, struct bpf_insn *insn)
1210{
1211 int err;
1212
1213 if ((BPF_SIZE(insn->code) != BPF_W && BPF_SIZE(insn->code) != BPF_DW) ||
1214 insn->imm != 0) {
1208 verbose("BPF_XADD uses reserved fields\n");
1215 verbose(env, "BPF_XADD uses reserved fields\n");
1209 return -EINVAL;
1210 }
1211
1212 /* check src1 operand */
1213 err = check_reg_arg(env, insn->src_reg, SRC_OP);
1214 if (err)
1215 return err;
1216
1217 /* check src2 operand */
1218 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
1219 if (err)
1220 return err;
1221
1222 if (is_pointer_value(env, insn->src_reg)) {
1216 return -EINVAL;
1217 }
1218
1219 /* check src1 operand */
1220 err = check_reg_arg(env, insn->src_reg, SRC_OP);
1221 if (err)
1222 return err;
1223
1224 /* check src2 operand */
1225 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
1226 if (err)
1227 return err;
1228
1229 if (is_pointer_value(env, insn->src_reg)) {
1223 verbose("R%d leaks addr into mem\n", insn->src_reg);
1230 verbose(env, "R%d leaks addr into mem\n", insn->src_reg);
1224 return -EACCES;
1225 }
1226
1227 /* check whether atomic_add can read the memory */
1228 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
1229 BPF_SIZE(insn->code), BPF_READ, -1);
1230 if (err)
1231 return err;

--- 14 unchanged lines hidden (view full) ---

1246 * and all elements of stack are initialized.
1247 * Unlike most pointer bounds-checking functions, this one doesn't take an
1248 * 'off' argument, so it has to add in reg->off itself.
1249 */
1250static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
1251 int access_size, bool zero_size_allowed,
1252 struct bpf_call_arg_meta *meta)
1253{
1231 return -EACCES;
1232 }
1233
1234 /* check whether atomic_add can read the memory */
1235 err = check_mem_access(env, insn_idx, insn->dst_reg, insn->off,
1236 BPF_SIZE(insn->code), BPF_READ, -1);
1237 if (err)
1238 return err;

--- 14 unchanged lines hidden (view full) ---

1253 * and all elements of stack are initialized.
1254 * Unlike most pointer bounds-checking functions, this one doesn't take an
1255 * 'off' argument, so it has to add in reg->off itself.
1256 */
1257static int check_stack_boundary(struct bpf_verifier_env *env, int regno,
1258 int access_size, bool zero_size_allowed,
1259 struct bpf_call_arg_meta *meta)
1260{
1254 struct bpf_verifier_state *state = &env->cur_state;
1261 struct bpf_verifier_state *state = env->cur_state;
1255 struct bpf_reg_state *regs = state->regs;
1262 struct bpf_reg_state *regs = state->regs;
1256 int off, i;
1263 int off, i, slot, spi;
1257
1258 if (regs[regno].type != PTR_TO_STACK) {
1259 /* Allow zero-byte read from NULL, regardless of pointer type */
1260 if (zero_size_allowed && access_size == 0 &&
1261 register_is_null(regs[regno]))
1262 return 0;
1263
1264
1265 if (regs[regno].type != PTR_TO_STACK) {
1266 /* Allow zero-byte read from NULL, regardless of pointer type */
1267 if (zero_size_allowed && access_size == 0 &&
1268 register_is_null(regs[regno]))
1269 return 0;
1270
1264 verbose("R%d type=%s expected=%s\n", regno,
1271 verbose(env, "R%d type=%s expected=%s\n", regno,
1265 reg_type_str[regs[regno].type],
1266 reg_type_str[PTR_TO_STACK]);
1267 return -EACCES;
1268 }
1269
1270 /* Only allow fixed-offset stack reads */
1271 if (!tnum_is_const(regs[regno].var_off)) {
1272 char tn_buf[48];
1273
1274 tnum_strn(tn_buf, sizeof(tn_buf), regs[regno].var_off);
1272 reg_type_str[regs[regno].type],
1273 reg_type_str[PTR_TO_STACK]);
1274 return -EACCES;
1275 }
1276
1277 /* Only allow fixed-offset stack reads */
1278 if (!tnum_is_const(regs[regno].var_off)) {
1279 char tn_buf[48];
1280
1281 tnum_strn(tn_buf, sizeof(tn_buf), regs[regno].var_off);
1275 verbose("invalid variable stack read R%d var_off=%s\n",
1282 verbose(env, "invalid variable stack read R%d var_off=%s\n",
1276 regno, tn_buf);
1277 }
1278 off = regs[regno].off + regs[regno].var_off.value;
1279 if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
1280 access_size <= 0) {
1283 regno, tn_buf);
1284 }
1285 off = regs[regno].off + regs[regno].var_off.value;
1286 if (off >= 0 || off < -MAX_BPF_STACK || off + access_size > 0 ||
1287 access_size <= 0) {
1281 verbose("invalid stack type R%d off=%d access_size=%d\n",
1288 verbose(env, "invalid stack type R%d off=%d access_size=%d\n",
1282 regno, off, access_size);
1283 return -EACCES;
1284 }
1285
1286 if (env->prog->aux->stack_depth < -off)
1287 env->prog->aux->stack_depth = -off;
1288
1289 if (meta && meta->raw_mode) {
1290 meta->access_size = access_size;
1291 meta->regno = regno;
1292 return 0;
1293 }
1294
1295 for (i = 0; i < access_size; i++) {
1289 regno, off, access_size);
1290 return -EACCES;
1291 }
1292
1293 if (env->prog->aux->stack_depth < -off)
1294 env->prog->aux->stack_depth = -off;
1295
1296 if (meta && meta->raw_mode) {
1297 meta->access_size = access_size;
1298 meta->regno = regno;
1299 return 0;
1300 }
1301
1302 for (i = 0; i < access_size; i++) {
1296 if (state->stack_slot_type[MAX_BPF_STACK + off + i] != STACK_MISC) {
1297 verbose("invalid indirect read from stack off %d+%d size %d\n",
1303 slot = -(off + i) - 1;
1304 spi = slot / BPF_REG_SIZE;
1305 if (state->allocated_stack <= slot ||
1306 state->stack[spi].slot_type[slot % BPF_REG_SIZE] !=
1307 STACK_MISC) {
1308 verbose(env, "invalid indirect read from stack off %d+%d size %d\n",
1298 off, i, access_size);
1299 return -EACCES;
1300 }
1301 }
1302 return 0;
1303}
1304
1305static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
1306 int access_size, bool zero_size_allowed,
1307 struct bpf_call_arg_meta *meta)
1308{
1309 off, i, access_size);
1310 return -EACCES;
1311 }
1312 }
1313 return 0;
1314}
1315
1316static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
1317 int access_size, bool zero_size_allowed,
1318 struct bpf_call_arg_meta *meta)
1319{
1309 struct bpf_reg_state *regs = env->cur_state.regs, *reg = &regs[regno];
1320 struct bpf_reg_state *regs = cur_regs(env), *reg = &regs[regno];
1310
1311 switch (reg->type) {
1312 case PTR_TO_PACKET:
1321
1322 switch (reg->type) {
1323 case PTR_TO_PACKET:
1324 case PTR_TO_PACKET_META:
1313 return check_packet_access(env, regno, reg->off, access_size);
1314 case PTR_TO_MAP_VALUE:
1315 return check_map_access(env, regno, reg->off, access_size);
1316 default: /* scalar_value|ptr_to_stack or invalid ptr */
1317 return check_stack_boundary(env, regno, access_size,
1318 zero_size_allowed, meta);
1319 }
1320}
1321
1322static int check_func_arg(struct bpf_verifier_env *env, u32 regno,
1323 enum bpf_arg_type arg_type,
1324 struct bpf_call_arg_meta *meta)
1325{
1325 return check_packet_access(env, regno, reg->off, access_size);
1326 case PTR_TO_MAP_VALUE:
1327 return check_map_access(env, regno, reg->off, access_size);
1328 default: /* scalar_value|ptr_to_stack or invalid ptr */
1329 return check_stack_boundary(env, regno, access_size,
1330 zero_size_allowed, meta);
1331 }
1332}
1333
1334static int check_func_arg(struct bpf_verifier_env *env, u32 regno,
1335 enum bpf_arg_type arg_type,
1336 struct bpf_call_arg_meta *meta)
1337{
1326 struct bpf_reg_state *regs = env->cur_state.regs, *reg = &regs[regno];
1338 struct bpf_reg_state *regs = cur_regs(env), *reg = &regs[regno];
1327 enum bpf_reg_type expected_type, type = reg->type;
1328 int err = 0;
1329
1330 if (arg_type == ARG_DONTCARE)
1331 return 0;
1332
1333 err = check_reg_arg(env, regno, SRC_OP);
1334 if (err)
1335 return err;
1336
1337 if (arg_type == ARG_ANYTHING) {
1338 if (is_pointer_value(env, regno)) {
1339 enum bpf_reg_type expected_type, type = reg->type;
1340 int err = 0;
1341
1342 if (arg_type == ARG_DONTCARE)
1343 return 0;
1344
1345 err = check_reg_arg(env, regno, SRC_OP);
1346 if (err)
1347 return err;
1348
1349 if (arg_type == ARG_ANYTHING) {
1350 if (is_pointer_value(env, regno)) {
1339 verbose("R%d leaks addr into helper function\n", regno);
1351 verbose(env, "R%d leaks addr into helper function\n",
1352 regno);
1340 return -EACCES;
1341 }
1342 return 0;
1343 }
1344
1353 return -EACCES;
1354 }
1355 return 0;
1356 }
1357
1345 if (type == PTR_TO_PACKET &&
1358 if (type_is_pkt_pointer(type) &&
1346 !may_access_direct_pkt_data(env, meta, BPF_READ)) {
1359 !may_access_direct_pkt_data(env, meta, BPF_READ)) {
1347 verbose("helper access to the packet is not allowed\n");
1360 verbose(env, "helper access to the packet is not allowed\n");
1348 return -EACCES;
1349 }
1350
1351 if (arg_type == ARG_PTR_TO_MAP_KEY ||
1352 arg_type == ARG_PTR_TO_MAP_VALUE) {
1353 expected_type = PTR_TO_STACK;
1361 return -EACCES;
1362 }
1363
1364 if (arg_type == ARG_PTR_TO_MAP_KEY ||
1365 arg_type == ARG_PTR_TO_MAP_VALUE) {
1366 expected_type = PTR_TO_STACK;
1354 if (type != PTR_TO_PACKET && type != expected_type)
1367 if (!type_is_pkt_pointer(type) &&
1368 type != expected_type)
1355 goto err_type;
1356 } else if (arg_type == ARG_CONST_SIZE ||
1357 arg_type == ARG_CONST_SIZE_OR_ZERO) {
1358 expected_type = SCALAR_VALUE;
1359 if (type != expected_type)
1360 goto err_type;
1361 } else if (arg_type == ARG_CONST_MAP_PTR) {
1362 expected_type = CONST_PTR_TO_MAP;

--- 7 unchanged lines hidden (view full) ---

1370 arg_type == ARG_PTR_TO_UNINIT_MEM) {
1371 expected_type = PTR_TO_STACK;
1372 /* One exception here. In case function allows for NULL to be
1373 * passed in as argument, it's a SCALAR_VALUE type. Final test
1374 * happens during stack boundary checking.
1375 */
1376 if (register_is_null(*reg))
1377 /* final test in check_stack_boundary() */;
1369 goto err_type;
1370 } else if (arg_type == ARG_CONST_SIZE ||
1371 arg_type == ARG_CONST_SIZE_OR_ZERO) {
1372 expected_type = SCALAR_VALUE;
1373 if (type != expected_type)
1374 goto err_type;
1375 } else if (arg_type == ARG_CONST_MAP_PTR) {
1376 expected_type = CONST_PTR_TO_MAP;

--- 7 unchanged lines hidden (view full) ---

1384 arg_type == ARG_PTR_TO_UNINIT_MEM) {
1385 expected_type = PTR_TO_STACK;
1386 /* One exception here. In case function allows for NULL to be
1387 * passed in as argument, it's a SCALAR_VALUE type. Final test
1388 * happens during stack boundary checking.
1389 */
1390 if (register_is_null(*reg))
1391 /* final test in check_stack_boundary() */;
1378 else if (type != PTR_TO_PACKET && type != PTR_TO_MAP_VALUE &&
1392 else if (!type_is_pkt_pointer(type) &&
1393 type != PTR_TO_MAP_VALUE &&
1379 type != expected_type)
1380 goto err_type;
1381 meta->raw_mode = arg_type == ARG_PTR_TO_UNINIT_MEM;
1382 } else {
1394 type != expected_type)
1395 goto err_type;
1396 meta->raw_mode = arg_type == ARG_PTR_TO_UNINIT_MEM;
1397 } else {
1383 verbose("unsupported arg_type %d\n", arg_type);
1398 verbose(env, "unsupported arg_type %d\n", arg_type);
1384 return -EFAULT;
1385 }
1386
1387 if (arg_type == ARG_CONST_MAP_PTR) {
1388 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
1389 meta->map_ptr = reg->map_ptr;
1390 } else if (arg_type == ARG_PTR_TO_MAP_KEY) {
1391 /* bpf_map_xxx(..., map_ptr, ..., key) call:
1392 * check that [key, key + map->key_size) are within
1393 * stack limits and initialized
1394 */
1395 if (!meta->map_ptr) {
1396 /* in function declaration map_ptr must come before
1397 * map_key, so that it's verified and known before
1398 * we have to check map_key here. Otherwise it means
1399 * that kernel subsystem misconfigured verifier
1400 */
1399 return -EFAULT;
1400 }
1401
1402 if (arg_type == ARG_CONST_MAP_PTR) {
1403 /* bpf_map_xxx(map_ptr) call: remember that map_ptr */
1404 meta->map_ptr = reg->map_ptr;
1405 } else if (arg_type == ARG_PTR_TO_MAP_KEY) {
1406 /* bpf_map_xxx(..., map_ptr, ..., key) call:
1407 * check that [key, key + map->key_size) are within
1408 * stack limits and initialized
1409 */
1410 if (!meta->map_ptr) {
1411 /* in function declaration map_ptr must come before
1412 * map_key, so that it's verified and known before
1413 * we have to check map_key here. Otherwise it means
1414 * that kernel subsystem misconfigured verifier
1415 */
1401 verbose("invalid map_ptr to access map->key\n");
1416 verbose(env, "invalid map_ptr to access map->key\n");
1402 return -EACCES;
1403 }
1417 return -EACCES;
1418 }
1404 if (type == PTR_TO_PACKET)
1419 if (type_is_pkt_pointer(type))
1405 err = check_packet_access(env, regno, reg->off,
1406 meta->map_ptr->key_size);
1407 else
1408 err = check_stack_boundary(env, regno,
1409 meta->map_ptr->key_size,
1410 false, NULL);
1411 } else if (arg_type == ARG_PTR_TO_MAP_VALUE) {
1412 /* bpf_map_xxx(..., map_ptr, ..., value) call:
1413 * check [value, value + map->value_size) validity
1414 */
1415 if (!meta->map_ptr) {
1416 /* kernel subsystem misconfigured verifier */
1420 err = check_packet_access(env, regno, reg->off,
1421 meta->map_ptr->key_size);
1422 else
1423 err = check_stack_boundary(env, regno,
1424 meta->map_ptr->key_size,
1425 false, NULL);
1426 } else if (arg_type == ARG_PTR_TO_MAP_VALUE) {
1427 /* bpf_map_xxx(..., map_ptr, ..., value) call:
1428 * check [value, value + map->value_size) validity
1429 */
1430 if (!meta->map_ptr) {
1431 /* kernel subsystem misconfigured verifier */
1417 verbose("invalid map_ptr to access map->value\n");
1432 verbose(env, "invalid map_ptr to access map->value\n");
1418 return -EACCES;
1419 }
1433 return -EACCES;
1434 }
1420 if (type == PTR_TO_PACKET)
1435 if (type_is_pkt_pointer(type))
1421 err = check_packet_access(env, regno, reg->off,
1422 meta->map_ptr->value_size);
1423 else
1424 err = check_stack_boundary(env, regno,
1425 meta->map_ptr->value_size,
1426 false, NULL);
1427 } else if (arg_type == ARG_CONST_SIZE ||
1428 arg_type == ARG_CONST_SIZE_OR_ZERO) {
1429 bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO);
1430
1431 /* bpf_xxx(..., buf, len) call will access 'len' bytes
1432 * from stack pointer 'buf'. Check it
1433 * note: regno == len, regno - 1 == buf
1434 */
1435 if (regno == 0) {
1436 /* kernel subsystem misconfigured verifier */
1436 err = check_packet_access(env, regno, reg->off,
1437 meta->map_ptr->value_size);
1438 else
1439 err = check_stack_boundary(env, regno,
1440 meta->map_ptr->value_size,
1441 false, NULL);
1442 } else if (arg_type == ARG_CONST_SIZE ||
1443 arg_type == ARG_CONST_SIZE_OR_ZERO) {
1444 bool zero_size_allowed = (arg_type == ARG_CONST_SIZE_OR_ZERO);
1445
1446 /* bpf_xxx(..., buf, len) call will access 'len' bytes
1447 * from stack pointer 'buf'. Check it
1448 * note: regno == len, regno - 1 == buf
1449 */
1450 if (regno == 0) {
1451 /* kernel subsystem misconfigured verifier */
1437 verbose("ARG_CONST_SIZE cannot be first argument\n");
1452 verbose(env,
1453 "ARG_CONST_SIZE cannot be first argument\n");
1438 return -EACCES;
1439 }
1440
1441 /* The register is SCALAR_VALUE; the access check
1442 * happens using its boundaries.
1443 */
1444
1445 if (!tnum_is_const(reg->var_off))
1446 /* For unprivileged variable accesses, disable raw
1447 * mode so that the program is required to
1448 * initialize all the memory that the helper could
1449 * just partially fill up.
1450 */
1451 meta = NULL;
1452
1453 if (reg->smin_value < 0) {
1454 return -EACCES;
1455 }
1456
1457 /* The register is SCALAR_VALUE; the access check
1458 * happens using its boundaries.
1459 */
1460
1461 if (!tnum_is_const(reg->var_off))
1462 /* For unprivileged variable accesses, disable raw
1463 * mode so that the program is required to
1464 * initialize all the memory that the helper could
1465 * just partially fill up.
1466 */
1467 meta = NULL;
1468
1469 if (reg->smin_value < 0) {
1454 verbose("R%d min value is negative, either use unsigned or 'var &= const'\n",
1470 verbose(env, "R%d min value is negative, either use unsigned or 'var &= const'\n",
1455 regno);
1456 return -EACCES;
1457 }
1458
1459 if (reg->umin_value == 0) {
1460 err = check_helper_mem_access(env, regno - 1, 0,
1461 zero_size_allowed,
1462 meta);
1463 if (err)
1464 return err;
1465 }
1466
1467 if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
1471 regno);
1472 return -EACCES;
1473 }
1474
1475 if (reg->umin_value == 0) {
1476 err = check_helper_mem_access(env, regno - 1, 0,
1477 zero_size_allowed,
1478 meta);
1479 if (err)
1480 return err;
1481 }
1482
1483 if (reg->umax_value >= BPF_MAX_VAR_SIZ) {
1468 verbose("R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n",
1484 verbose(env, "R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n",
1469 regno);
1470 return -EACCES;
1471 }
1472 err = check_helper_mem_access(env, regno - 1,
1473 reg->umax_value,
1474 zero_size_allowed, meta);
1475 }
1476
1477 return err;
1478err_type:
1485 regno);
1486 return -EACCES;
1487 }
1488 err = check_helper_mem_access(env, regno - 1,
1489 reg->umax_value,
1490 zero_size_allowed, meta);
1491 }
1492
1493 return err;
1494err_type:
1479 verbose("R%d type=%s expected=%s\n", regno,
1495 verbose(env, "R%d type=%s expected=%s\n", regno,
1480 reg_type_str[type], reg_type_str[expected_type]);
1481 return -EACCES;
1482}
1483
1496 reg_type_str[type], reg_type_str[expected_type]);
1497 return -EACCES;
1498}
1499
1484static int check_map_func_compatibility(struct bpf_map *map, int func_id)
1500static int check_map_func_compatibility(struct bpf_verifier_env *env,
1501 struct bpf_map *map, int func_id)
1485{
1486 if (!map)
1487 return 0;
1488
1489 /* We need a two way check, first is from map perspective ... */
1490 switch (map->map_type) {
1491 case BPF_MAP_TYPE_PROG_ARRAY:
1492 if (func_id != BPF_FUNC_tail_call)
1493 goto error;
1494 break;
1495 case BPF_MAP_TYPE_PERF_EVENT_ARRAY:
1496 if (func_id != BPF_FUNC_perf_event_read &&
1502{
1503 if (!map)
1504 return 0;
1505
1506 /* We need a two way check, first is from map perspective ... */
1507 switch (map->map_type) {
1508 case BPF_MAP_TYPE_PROG_ARRAY:
1509 if (func_id != BPF_FUNC_tail_call)
1510 goto error;
1511 break;
1512 case BPF_MAP_TYPE_PERF_EVENT_ARRAY:
1513 if (func_id != BPF_FUNC_perf_event_read &&
1497 func_id != BPF_FUNC_perf_event_output)
1514 func_id != BPF_FUNC_perf_event_output &&
1515 func_id != BPF_FUNC_perf_event_read_value)
1498 goto error;
1499 break;
1500 case BPF_MAP_TYPE_STACK_TRACE:
1501 if (func_id != BPF_FUNC_get_stackid)
1502 goto error;
1503 break;
1504 case BPF_MAP_TYPE_CGROUP_ARRAY:
1505 if (func_id != BPF_FUNC_skb_under_cgroup &&
1506 func_id != BPF_FUNC_current_task_under_cgroup)
1507 goto error;
1508 break;
1509 /* devmap returns a pointer to a live net_device ifindex that we cannot
1510 * allow to be modified from bpf side. So do not allow lookup elements
1511 * for now.
1512 */
1513 case BPF_MAP_TYPE_DEVMAP:
1514 if (func_id != BPF_FUNC_redirect_map)
1515 goto error;
1516 break;
1516 goto error;
1517 break;
1518 case BPF_MAP_TYPE_STACK_TRACE:
1519 if (func_id != BPF_FUNC_get_stackid)
1520 goto error;
1521 break;
1522 case BPF_MAP_TYPE_CGROUP_ARRAY:
1523 if (func_id != BPF_FUNC_skb_under_cgroup &&
1524 func_id != BPF_FUNC_current_task_under_cgroup)
1525 goto error;
1526 break;
1527 /* devmap returns a pointer to a live net_device ifindex that we cannot
1528 * allow to be modified from bpf side. So do not allow lookup elements
1529 * for now.
1530 */
1531 case BPF_MAP_TYPE_DEVMAP:
1532 if (func_id != BPF_FUNC_redirect_map)
1533 goto error;
1534 break;
1535 /* Restrict bpf side of cpumap, open when use-cases appear */
1536 case BPF_MAP_TYPE_CPUMAP:
1537 if (func_id != BPF_FUNC_redirect_map)
1538 goto error;
1539 break;
1517 case BPF_MAP_TYPE_ARRAY_OF_MAPS:
1518 case BPF_MAP_TYPE_HASH_OF_MAPS:
1519 if (func_id != BPF_FUNC_map_lookup_elem)
1520 goto error;
1521 break;
1522 case BPF_MAP_TYPE_SOCKMAP:
1523 if (func_id != BPF_FUNC_sk_redirect_map &&
1524 func_id != BPF_FUNC_sock_map_update &&

--- 7 unchanged lines hidden (view full) ---

1532 /* ... and second from the function itself. */
1533 switch (func_id) {
1534 case BPF_FUNC_tail_call:
1535 if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
1536 goto error;
1537 break;
1538 case BPF_FUNC_perf_event_read:
1539 case BPF_FUNC_perf_event_output:
1540 case BPF_MAP_TYPE_ARRAY_OF_MAPS:
1541 case BPF_MAP_TYPE_HASH_OF_MAPS:
1542 if (func_id != BPF_FUNC_map_lookup_elem)
1543 goto error;
1544 break;
1545 case BPF_MAP_TYPE_SOCKMAP:
1546 if (func_id != BPF_FUNC_sk_redirect_map &&
1547 func_id != BPF_FUNC_sock_map_update &&

--- 7 unchanged lines hidden (view full) ---

1555 /* ... and second from the function itself. */
1556 switch (func_id) {
1557 case BPF_FUNC_tail_call:
1558 if (map->map_type != BPF_MAP_TYPE_PROG_ARRAY)
1559 goto error;
1560 break;
1561 case BPF_FUNC_perf_event_read:
1562 case BPF_FUNC_perf_event_output:
1563 case BPF_FUNC_perf_event_read_value:
1540 if (map->map_type != BPF_MAP_TYPE_PERF_EVENT_ARRAY)
1541 goto error;
1542 break;
1543 case BPF_FUNC_get_stackid:
1544 if (map->map_type != BPF_MAP_TYPE_STACK_TRACE)
1545 goto error;
1546 break;
1547 case BPF_FUNC_current_task_under_cgroup:
1548 case BPF_FUNC_skb_under_cgroup:
1549 if (map->map_type != BPF_MAP_TYPE_CGROUP_ARRAY)
1550 goto error;
1551 break;
1552 case BPF_FUNC_redirect_map:
1564 if (map->map_type != BPF_MAP_TYPE_PERF_EVENT_ARRAY)
1565 goto error;
1566 break;
1567 case BPF_FUNC_get_stackid:
1568 if (map->map_type != BPF_MAP_TYPE_STACK_TRACE)
1569 goto error;
1570 break;
1571 case BPF_FUNC_current_task_under_cgroup:
1572 case BPF_FUNC_skb_under_cgroup:
1573 if (map->map_type != BPF_MAP_TYPE_CGROUP_ARRAY)
1574 goto error;
1575 break;
1576 case BPF_FUNC_redirect_map:
1553 if (map->map_type != BPF_MAP_TYPE_DEVMAP)
1577 if (map->map_type != BPF_MAP_TYPE_DEVMAP &&
1578 map->map_type != BPF_MAP_TYPE_CPUMAP)
1554 goto error;
1555 break;
1556 case BPF_FUNC_sk_redirect_map:
1557 if (map->map_type != BPF_MAP_TYPE_SOCKMAP)
1558 goto error;
1559 break;
1560 case BPF_FUNC_sock_map_update:
1561 if (map->map_type != BPF_MAP_TYPE_SOCKMAP)
1562 goto error;
1563 break;
1564 default:
1565 break;
1566 }
1567
1568 return 0;
1569error:
1579 goto error;
1580 break;
1581 case BPF_FUNC_sk_redirect_map:
1582 if (map->map_type != BPF_MAP_TYPE_SOCKMAP)
1583 goto error;
1584 break;
1585 case BPF_FUNC_sock_map_update:
1586 if (map->map_type != BPF_MAP_TYPE_SOCKMAP)
1587 goto error;
1588 break;
1589 default:
1590 break;
1591 }
1592
1593 return 0;
1594error:
1570 verbose("cannot pass map_type %d into func %s#%d\n",
1595 verbose(env, "cannot pass map_type %d into func %s#%d\n",
1571 map->map_type, func_id_name(func_id), func_id);
1572 return -EINVAL;
1573}
1574
1575static int check_raw_mode(const struct bpf_func_proto *fn)
1576{
1577 int count = 0;
1578

--- 6 unchanged lines hidden (view full) ---

1585 if (fn->arg4_type == ARG_PTR_TO_UNINIT_MEM)
1586 count++;
1587 if (fn->arg5_type == ARG_PTR_TO_UNINIT_MEM)
1588 count++;
1589
1590 return count > 1 ? -EINVAL : 0;
1591}
1592
1596 map->map_type, func_id_name(func_id), func_id);
1597 return -EINVAL;
1598}
1599
1600static int check_raw_mode(const struct bpf_func_proto *fn)
1601{
1602 int count = 0;
1603

--- 6 unchanged lines hidden (view full) ---

1610 if (fn->arg4_type == ARG_PTR_TO_UNINIT_MEM)
1611 count++;
1612 if (fn->arg5_type == ARG_PTR_TO_UNINIT_MEM)
1613 count++;
1614
1615 return count > 1 ? -EINVAL : 0;
1616}
1617
1593/* Packet data might have moved, any old PTR_TO_PACKET[_END] are now invalid,
1594 * so turn them into unknown SCALAR_VALUE.
1618/* Packet data might have moved, any old PTR_TO_PACKET[_META,_END]
1619 * are now invalid, so turn them into unknown SCALAR_VALUE.
1595 */
1596static void clear_all_pkt_pointers(struct bpf_verifier_env *env)
1597{
1620 */
1621static void clear_all_pkt_pointers(struct bpf_verifier_env *env)
1622{
1598 struct bpf_verifier_state *state = &env->cur_state;
1623 struct bpf_verifier_state *state = env->cur_state;
1599 struct bpf_reg_state *regs = state->regs, *reg;
1600 int i;
1601
1602 for (i = 0; i < MAX_BPF_REG; i++)
1624 struct bpf_reg_state *regs = state->regs, *reg;
1625 int i;
1626
1627 for (i = 0; i < MAX_BPF_REG; i++)
1603 if (regs[i].type == PTR_TO_PACKET ||
1604 regs[i].type == PTR_TO_PACKET_END)
1605 mark_reg_unknown(regs, i);
1628 if (reg_is_pkt_pointer_any(&regs[i]))
1629 mark_reg_unknown(env, regs, i);
1606
1630
1607 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
1608 if (state->stack_slot_type[i] != STACK_SPILL)
1631 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
1632 if (state->stack[i].slot_type[0] != STACK_SPILL)
1609 continue;
1633 continue;
1610 reg = &state->spilled_regs[i / BPF_REG_SIZE];
1611 if (reg->type != PTR_TO_PACKET &&
1612 reg->type != PTR_TO_PACKET_END)
1613 continue;
1614 __mark_reg_unknown(reg);
1634 reg = &state->stack[i].spilled_ptr;
1635 if (reg_is_pkt_pointer_any(reg))
1636 __mark_reg_unknown(reg);
1615 }
1616}
1617
1618static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
1619{
1637 }
1638}
1639
1640static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
1641{
1620 struct bpf_verifier_state *state = &env->cur_state;
1621 const struct bpf_func_proto *fn = NULL;
1642 const struct bpf_func_proto *fn = NULL;
1622 struct bpf_reg_state *regs = state->regs;
1643 struct bpf_reg_state *regs;
1623 struct bpf_call_arg_meta meta;
1624 bool changes_data;
1625 int i, err;
1626
1627 /* find function prototype */
1628 if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
1644 struct bpf_call_arg_meta meta;
1645 bool changes_data;
1646 int i, err;
1647
1648 /* find function prototype */
1649 if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
1629 verbose("invalid func %s#%d\n", func_id_name(func_id), func_id);
1650 verbose(env, "invalid func %s#%d\n", func_id_name(func_id),
1651 func_id);
1630 return -EINVAL;
1631 }
1632
1652 return -EINVAL;
1653 }
1654
1633 if (env->prog->aux->ops->get_func_proto)
1634 fn = env->prog->aux->ops->get_func_proto(func_id);
1655 if (env->ops->get_func_proto)
1656 fn = env->ops->get_func_proto(func_id);
1635
1636 if (!fn) {
1657
1658 if (!fn) {
1637 verbose("unknown func %s#%d\n", func_id_name(func_id), func_id);
1659 verbose(env, "unknown func %s#%d\n", func_id_name(func_id),
1660 func_id);
1638 return -EINVAL;
1639 }
1640
1641 /* eBPF programs must be GPL compatible to use GPL-ed functions */
1642 if (!env->prog->gpl_compatible && fn->gpl_only) {
1661 return -EINVAL;
1662 }
1663
1664 /* eBPF programs must be GPL compatible to use GPL-ed functions */
1665 if (!env->prog->gpl_compatible && fn->gpl_only) {
1643 verbose("cannot call GPL only function from proprietary program\n");
1666 verbose(env, "cannot call GPL only function from proprietary program\n");
1644 return -EINVAL;
1645 }
1646
1647 changes_data = bpf_helper_changes_pkt_data(fn->func);
1648
1649 memset(&meta, 0, sizeof(meta));
1650 meta.pkt_access = fn->pkt_access;
1651
1652 /* We only support one arg being in raw mode at the moment, which
1653 * is sufficient for the helper functions we have right now.
1654 */
1655 err = check_raw_mode(fn);
1656 if (err) {
1667 return -EINVAL;
1668 }
1669
1670 changes_data = bpf_helper_changes_pkt_data(fn->func);
1671
1672 memset(&meta, 0, sizeof(meta));
1673 meta.pkt_access = fn->pkt_access;
1674
1675 /* We only support one arg being in raw mode at the moment, which
1676 * is sufficient for the helper functions we have right now.
1677 */
1678 err = check_raw_mode(fn);
1679 if (err) {
1657 verbose("kernel subsystem misconfigured func %s#%d\n",
1680 verbose(env, "kernel subsystem misconfigured func %s#%d\n",
1658 func_id_name(func_id), func_id);
1659 return err;
1660 }
1661
1662 /* check args */
1663 err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta);
1664 if (err)
1665 return err;

--- 14 unchanged lines hidden (view full) ---

1680 * is inferred from register state.
1681 */
1682 for (i = 0; i < meta.access_size; i++) {
1683 err = check_mem_access(env, insn_idx, meta.regno, i, BPF_B, BPF_WRITE, -1);
1684 if (err)
1685 return err;
1686 }
1687
1681 func_id_name(func_id), func_id);
1682 return err;
1683 }
1684
1685 /* check args */
1686 err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta);
1687 if (err)
1688 return err;

--- 14 unchanged lines hidden (view full) ---

1703 * is inferred from register state.
1704 */
1705 for (i = 0; i < meta.access_size; i++) {
1706 err = check_mem_access(env, insn_idx, meta.regno, i, BPF_B, BPF_WRITE, -1);
1707 if (err)
1708 return err;
1709 }
1710
1711 regs = cur_regs(env);
1688 /* reset caller saved regs */
1689 for (i = 0; i < CALLER_SAVED_REGS; i++) {
1712 /* reset caller saved regs */
1713 for (i = 0; i < CALLER_SAVED_REGS; i++) {
1690 mark_reg_not_init(regs, caller_saved[i]);
1714 mark_reg_not_init(env, regs, caller_saved[i]);
1691 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
1692 }
1693
1694 /* update return register (already marked as written above) */
1695 if (fn->ret_type == RET_INTEGER) {
1696 /* sets type to SCALAR_VALUE */
1715 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
1716 }
1717
1718 /* update return register (already marked as written above) */
1719 if (fn->ret_type == RET_INTEGER) {
1720 /* sets type to SCALAR_VALUE */
1697 mark_reg_unknown(regs, BPF_REG_0);
1721 mark_reg_unknown(env, regs, BPF_REG_0);
1698 } else if (fn->ret_type == RET_VOID) {
1699 regs[BPF_REG_0].type = NOT_INIT;
1700 } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) {
1701 struct bpf_insn_aux_data *insn_aux;
1702
1703 regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL;
1704 /* There is no offset yet applied, variable or fixed */
1722 } else if (fn->ret_type == RET_VOID) {
1723 regs[BPF_REG_0].type = NOT_INIT;
1724 } else if (fn->ret_type == RET_PTR_TO_MAP_VALUE_OR_NULL) {
1725 struct bpf_insn_aux_data *insn_aux;
1726
1727 regs[BPF_REG_0].type = PTR_TO_MAP_VALUE_OR_NULL;
1728 /* There is no offset yet applied, variable or fixed */
1705 mark_reg_known_zero(regs, BPF_REG_0);
1729 mark_reg_known_zero(env, regs, BPF_REG_0);
1706 regs[BPF_REG_0].off = 0;
1707 /* remember map_ptr, so that check_map_access()
1708 * can check 'value_size' boundary of memory access
1709 * to map element returned from bpf_map_lookup_elem()
1710 */
1711 if (meta.map_ptr == NULL) {
1730 regs[BPF_REG_0].off = 0;
1731 /* remember map_ptr, so that check_map_access()
1732 * can check 'value_size' boundary of memory access
1733 * to map element returned from bpf_map_lookup_elem()
1734 */
1735 if (meta.map_ptr == NULL) {
1712 verbose("kernel subsystem misconfigured verifier\n");
1736 verbose(env,
1737 "kernel subsystem misconfigured verifier\n");
1713 return -EINVAL;
1714 }
1715 regs[BPF_REG_0].map_ptr = meta.map_ptr;
1716 regs[BPF_REG_0].id = ++env->id_gen;
1717 insn_aux = &env->insn_aux_data[insn_idx];
1718 if (!insn_aux->map_ptr)
1719 insn_aux->map_ptr = meta.map_ptr;
1720 else if (insn_aux->map_ptr != meta.map_ptr)
1721 insn_aux->map_ptr = BPF_MAP_PTR_POISON;
1722 } else {
1738 return -EINVAL;
1739 }
1740 regs[BPF_REG_0].map_ptr = meta.map_ptr;
1741 regs[BPF_REG_0].id = ++env->id_gen;
1742 insn_aux = &env->insn_aux_data[insn_idx];
1743 if (!insn_aux->map_ptr)
1744 insn_aux->map_ptr = meta.map_ptr;
1745 else if (insn_aux->map_ptr != meta.map_ptr)
1746 insn_aux->map_ptr = BPF_MAP_PTR_POISON;
1747 } else {
1723 verbose("unknown return type %d of func %s#%d\n",
1748 verbose(env, "unknown return type %d of func %s#%d\n",
1724 fn->ret_type, func_id_name(func_id), func_id);
1725 return -EINVAL;
1726 }
1727
1749 fn->ret_type, func_id_name(func_id), func_id);
1750 return -EINVAL;
1751 }
1752
1728 err = check_map_func_compatibility(meta.map_ptr, func_id);
1753 err = check_map_func_compatibility(env, meta.map_ptr, func_id);
1729 if (err)
1730 return err;
1731
1732 if (changes_data)
1733 clear_all_pkt_pointers(env);
1734 return 0;
1735}
1736

--- 30 unchanged lines hidden (view full) ---

1767 * If we return -EACCES, caller may want to try again treating pointer as a
1768 * scalar. So we only emit a diagnostic if !env->allow_ptr_leaks.
1769 */
1770static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
1771 struct bpf_insn *insn,
1772 const struct bpf_reg_state *ptr_reg,
1773 const struct bpf_reg_state *off_reg)
1774{
1754 if (err)
1755 return err;
1756
1757 if (changes_data)
1758 clear_all_pkt_pointers(env);
1759 return 0;
1760}
1761

--- 30 unchanged lines hidden (view full) ---

1792 * If we return -EACCES, caller may want to try again treating pointer as a
1793 * scalar. So we only emit a diagnostic if !env->allow_ptr_leaks.
1794 */
1795static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
1796 struct bpf_insn *insn,
1797 const struct bpf_reg_state *ptr_reg,
1798 const struct bpf_reg_state *off_reg)
1799{
1775 struct bpf_reg_state *regs = env->cur_state.regs, *dst_reg;
1800 struct bpf_reg_state *regs = cur_regs(env), *dst_reg;
1776 bool known = tnum_is_const(off_reg->var_off);
1777 s64 smin_val = off_reg->smin_value, smax_val = off_reg->smax_value,
1778 smin_ptr = ptr_reg->smin_value, smax_ptr = ptr_reg->smax_value;
1779 u64 umin_val = off_reg->umin_value, umax_val = off_reg->umax_value,
1780 umin_ptr = ptr_reg->umin_value, umax_ptr = ptr_reg->umax_value;
1781 u8 opcode = BPF_OP(insn->code);
1782 u32 dst = insn->dst_reg;
1783
1784 dst_reg = &regs[dst];
1785
1786 if (WARN_ON_ONCE(known && (smin_val != smax_val))) {
1801 bool known = tnum_is_const(off_reg->var_off);
1802 s64 smin_val = off_reg->smin_value, smax_val = off_reg->smax_value,
1803 smin_ptr = ptr_reg->smin_value, smax_ptr = ptr_reg->smax_value;
1804 u64 umin_val = off_reg->umin_value, umax_val = off_reg->umax_value,
1805 umin_ptr = ptr_reg->umin_value, umax_ptr = ptr_reg->umax_value;
1806 u8 opcode = BPF_OP(insn->code);
1807 u32 dst = insn->dst_reg;
1808
1809 dst_reg = &regs[dst];
1810
1811 if (WARN_ON_ONCE(known && (smin_val != smax_val))) {
1787 print_verifier_state(&env->cur_state);
1788 verbose("verifier internal error: known but bad sbounds\n");
1812 print_verifier_state(env, env->cur_state);
1813 verbose(env,
1814 "verifier internal error: known but bad sbounds\n");
1789 return -EINVAL;
1790 }
1791 if (WARN_ON_ONCE(known && (umin_val != umax_val))) {
1815 return -EINVAL;
1816 }
1817 if (WARN_ON_ONCE(known && (umin_val != umax_val))) {
1792 print_verifier_state(&env->cur_state);
1793 verbose("verifier internal error: known but bad ubounds\n");
1818 print_verifier_state(env, env->cur_state);
1819 verbose(env,
1820 "verifier internal error: known but bad ubounds\n");
1794 return -EINVAL;
1795 }
1796
1797 if (BPF_CLASS(insn->code) != BPF_ALU64) {
1798 /* 32-bit ALU ops on pointers produce (meaningless) scalars */
1799 if (!env->allow_ptr_leaks)
1821 return -EINVAL;
1822 }
1823
1824 if (BPF_CLASS(insn->code) != BPF_ALU64) {
1825 /* 32-bit ALU ops on pointers produce (meaningless) scalars */
1826 if (!env->allow_ptr_leaks)
1800 verbose("R%d 32-bit pointer arithmetic prohibited\n",
1827 verbose(env,
1828 "R%d 32-bit pointer arithmetic prohibited\n",
1801 dst);
1802 return -EACCES;
1803 }
1804
1805 if (ptr_reg->type == PTR_TO_MAP_VALUE_OR_NULL) {
1806 if (!env->allow_ptr_leaks)
1829 dst);
1830 return -EACCES;
1831 }
1832
1833 if (ptr_reg->type == PTR_TO_MAP_VALUE_OR_NULL) {
1834 if (!env->allow_ptr_leaks)
1807 verbose("R%d pointer arithmetic on PTR_TO_MAP_VALUE_OR_NULL prohibited, null-check it first\n",
1835 verbose(env, "R%d pointer arithmetic on PTR_TO_MAP_VALUE_OR_NULL prohibited, null-check it first\n",
1808 dst);
1809 return -EACCES;
1810 }
1811 if (ptr_reg->type == CONST_PTR_TO_MAP) {
1812 if (!env->allow_ptr_leaks)
1836 dst);
1837 return -EACCES;
1838 }
1839 if (ptr_reg->type == CONST_PTR_TO_MAP) {
1840 if (!env->allow_ptr_leaks)
1813 verbose("R%d pointer arithmetic on CONST_PTR_TO_MAP prohibited\n",
1841 verbose(env, "R%d pointer arithmetic on CONST_PTR_TO_MAP prohibited\n",
1814 dst);
1815 return -EACCES;
1816 }
1817 if (ptr_reg->type == PTR_TO_PACKET_END) {
1818 if (!env->allow_ptr_leaks)
1842 dst);
1843 return -EACCES;
1844 }
1845 if (ptr_reg->type == PTR_TO_PACKET_END) {
1846 if (!env->allow_ptr_leaks)
1819 verbose("R%d pointer arithmetic on PTR_TO_PACKET_END prohibited\n",
1847 verbose(env, "R%d pointer arithmetic on PTR_TO_PACKET_END prohibited\n",
1820 dst);
1821 return -EACCES;
1822 }
1823
1824 /* In case of 'scalar += pointer', dst_reg inherits pointer type and id.
1825 * The id may be overwritten later if we create a new variable offset.
1826 */
1827 dst_reg->type = ptr_reg->type;

--- 38 unchanged lines hidden (view full) ---

1866 dst_reg->umin_value = 0;
1867 dst_reg->umax_value = U64_MAX;
1868 } else {
1869 dst_reg->umin_value = umin_ptr + umin_val;
1870 dst_reg->umax_value = umax_ptr + umax_val;
1871 }
1872 dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
1873 dst_reg->off = ptr_reg->off;
1848 dst);
1849 return -EACCES;
1850 }
1851
1852 /* In case of 'scalar += pointer', dst_reg inherits pointer type and id.
1853 * The id may be overwritten later if we create a new variable offset.
1854 */
1855 dst_reg->type = ptr_reg->type;

--- 38 unchanged lines hidden (view full) ---

1894 dst_reg->umin_value = 0;
1895 dst_reg->umax_value = U64_MAX;
1896 } else {
1897 dst_reg->umin_value = umin_ptr + umin_val;
1898 dst_reg->umax_value = umax_ptr + umax_val;
1899 }
1900 dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off);
1901 dst_reg->off = ptr_reg->off;
1874 if (ptr_reg->type == PTR_TO_PACKET) {
1902 if (reg_is_pkt_pointer(ptr_reg)) {
1875 dst_reg->id = ++env->id_gen;
1876 /* something was added to pkt_ptr, set range to zero */
1877 dst_reg->range = 0;
1878 }
1879 break;
1880 case BPF_SUB:
1881 if (dst_reg == off_reg) {
1882 /* scalar -= pointer. Creates an unknown scalar */
1883 if (!env->allow_ptr_leaks)
1903 dst_reg->id = ++env->id_gen;
1904 /* something was added to pkt_ptr, set range to zero */
1905 dst_reg->range = 0;
1906 }
1907 break;
1908 case BPF_SUB:
1909 if (dst_reg == off_reg) {
1910 /* scalar -= pointer. Creates an unknown scalar */
1911 if (!env->allow_ptr_leaks)
1884 verbose("R%d tried to subtract pointer from scalar\n",
1912 verbose(env, "R%d tried to subtract pointer from scalar\n",
1885 dst);
1886 return -EACCES;
1887 }
1888 /* We don't allow subtraction from FP, because (according to
1889 * test_verifier.c test "invalid fp arithmetic", JITs might not
1890 * be able to deal with it.
1891 */
1892 if (ptr_reg->type == PTR_TO_STACK) {
1893 if (!env->allow_ptr_leaks)
1913 dst);
1914 return -EACCES;
1915 }
1916 /* We don't allow subtraction from FP, because (according to
1917 * test_verifier.c test "invalid fp arithmetic", JITs might not
1918 * be able to deal with it.
1919 */
1920 if (ptr_reg->type == PTR_TO_STACK) {
1921 if (!env->allow_ptr_leaks)
1894 verbose("R%d subtraction from stack pointer prohibited\n",
1922 verbose(env, "R%d subtraction from stack pointer prohibited\n",
1895 dst);
1896 return -EACCES;
1897 }
1898 if (known && (ptr_reg->off - smin_val ==
1899 (s64)(s32)(ptr_reg->off - smin_val))) {
1900 /* pointer -= K. Subtract it from fixed offset */
1901 dst_reg->smin_value = smin_ptr;
1902 dst_reg->smax_value = smax_ptr;

--- 23 unchanged lines hidden (view full) ---

1926 dst_reg->umax_value = U64_MAX;
1927 } else {
1928 /* Cannot overflow (as long as bounds are consistent) */
1929 dst_reg->umin_value = umin_ptr - umax_val;
1930 dst_reg->umax_value = umax_ptr - umin_val;
1931 }
1932 dst_reg->var_off = tnum_sub(ptr_reg->var_off, off_reg->var_off);
1933 dst_reg->off = ptr_reg->off;
1923 dst);
1924 return -EACCES;
1925 }
1926 if (known && (ptr_reg->off - smin_val ==
1927 (s64)(s32)(ptr_reg->off - smin_val))) {
1928 /* pointer -= K. Subtract it from fixed offset */
1929 dst_reg->smin_value = smin_ptr;
1930 dst_reg->smax_value = smax_ptr;

--- 23 unchanged lines hidden (view full) ---

1954 dst_reg->umax_value = U64_MAX;
1955 } else {
1956 /* Cannot overflow (as long as bounds are consistent) */
1957 dst_reg->umin_value = umin_ptr - umax_val;
1958 dst_reg->umax_value = umax_ptr - umin_val;
1959 }
1960 dst_reg->var_off = tnum_sub(ptr_reg->var_off, off_reg->var_off);
1961 dst_reg->off = ptr_reg->off;
1934 if (ptr_reg->type == PTR_TO_PACKET) {
1962 if (reg_is_pkt_pointer(ptr_reg)) {
1935 dst_reg->id = ++env->id_gen;
1936 /* something was added to pkt_ptr, set range to zero */
1937 if (smin_val < 0)
1938 dst_reg->range = 0;
1939 }
1940 break;
1941 case BPF_AND:
1942 case BPF_OR:
1943 case BPF_XOR:
1944 /* bitwise ops on pointers are troublesome, prohibit for now.
1945 * (However, in principle we could allow some cases, e.g.
1946 * ptr &= ~3 which would reduce min_value by 3.)
1947 */
1948 if (!env->allow_ptr_leaks)
1963 dst_reg->id = ++env->id_gen;
1964 /* something was added to pkt_ptr, set range to zero */
1965 if (smin_val < 0)
1966 dst_reg->range = 0;
1967 }
1968 break;
1969 case BPF_AND:
1970 case BPF_OR:
1971 case BPF_XOR:
1972 /* bitwise ops on pointers are troublesome, prohibit for now.
1973 * (However, in principle we could allow some cases, e.g.
1974 * ptr &= ~3 which would reduce min_value by 3.)
1975 */
1976 if (!env->allow_ptr_leaks)
1949 verbose("R%d bitwise operator %s on pointer prohibited\n",
1977 verbose(env, "R%d bitwise operator %s on pointer prohibited\n",
1950 dst, bpf_alu_string[opcode >> 4]);
1951 return -EACCES;
1952 default:
1953 /* other operators (e.g. MUL,LSH) produce non-pointer results */
1954 if (!env->allow_ptr_leaks)
1978 dst, bpf_alu_string[opcode >> 4]);
1979 return -EACCES;
1980 default:
1981 /* other operators (e.g. MUL,LSH) produce non-pointer results */
1982 if (!env->allow_ptr_leaks)
1955 verbose("R%d pointer arithmetic with %s operator prohibited\n",
1983 verbose(env, "R%d pointer arithmetic with %s operator prohibited\n",
1956 dst, bpf_alu_string[opcode >> 4]);
1957 return -EACCES;
1958 }
1959
1960 __update_reg_bounds(dst_reg);
1961 __reg_deduce_bounds(dst_reg);
1962 __reg_bound_offset(dst_reg);
1963 return 0;
1964}
1965
1966static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
1967 struct bpf_insn *insn,
1968 struct bpf_reg_state *dst_reg,
1969 struct bpf_reg_state src_reg)
1970{
1984 dst, bpf_alu_string[opcode >> 4]);
1985 return -EACCES;
1986 }
1987
1988 __update_reg_bounds(dst_reg);
1989 __reg_deduce_bounds(dst_reg);
1990 __reg_bound_offset(dst_reg);
1991 return 0;
1992}
1993
1994static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
1995 struct bpf_insn *insn,
1996 struct bpf_reg_state *dst_reg,
1997 struct bpf_reg_state src_reg)
1998{
1971 struct bpf_reg_state *regs = env->cur_state.regs;
1999 struct bpf_reg_state *regs = cur_regs(env);
1972 u8 opcode = BPF_OP(insn->code);
1973 bool src_known, dst_known;
1974 s64 smin_val, smax_val;
1975 u64 umin_val, umax_val;
1976
1977 if (BPF_CLASS(insn->code) != BPF_ALU64) {
1978 /* 32-bit ALU ops are (32,32)->64 */
1979 coerce_reg_to_32(dst_reg);

--- 133 unchanged lines hidden (view full) ---

2113 /* We may learn something more from the var_off */
2114 __update_reg_bounds(dst_reg);
2115 break;
2116 case BPF_LSH:
2117 if (umax_val > 63) {
2118 /* Shifts greater than 63 are undefined. This includes
2119 * shifts by a negative number.
2120 */
2000 u8 opcode = BPF_OP(insn->code);
2001 bool src_known, dst_known;
2002 s64 smin_val, smax_val;
2003 u64 umin_val, umax_val;
2004
2005 if (BPF_CLASS(insn->code) != BPF_ALU64) {
2006 /* 32-bit ALU ops are (32,32)->64 */
2007 coerce_reg_to_32(dst_reg);

--- 133 unchanged lines hidden (view full) ---

2141 /* We may learn something more from the var_off */
2142 __update_reg_bounds(dst_reg);
2143 break;
2144 case BPF_LSH:
2145 if (umax_val > 63) {
2146 /* Shifts greater than 63 are undefined. This includes
2147 * shifts by a negative number.
2148 */
2121 mark_reg_unknown(regs, insn->dst_reg);
2149 mark_reg_unknown(env, regs, insn->dst_reg);
2122 break;
2123 }
2124 /* We lose all sign bit information (except what we can pick
2125 * up from var_off)
2126 */
2127 dst_reg->smin_value = S64_MIN;
2128 dst_reg->smax_value = S64_MAX;
2129 /* If we might shift our top bit out, then we know nothing */

--- 11 unchanged lines hidden (view full) ---

2141 /* We may learn something more from the var_off */
2142 __update_reg_bounds(dst_reg);
2143 break;
2144 case BPF_RSH:
2145 if (umax_val > 63) {
2146 /* Shifts greater than 63 are undefined. This includes
2147 * shifts by a negative number.
2148 */
2150 break;
2151 }
2152 /* We lose all sign bit information (except what we can pick
2153 * up from var_off)
2154 */
2155 dst_reg->smin_value = S64_MIN;
2156 dst_reg->smax_value = S64_MAX;
2157 /* If we might shift our top bit out, then we know nothing */

--- 11 unchanged lines hidden (view full) ---

2169 /* We may learn something more from the var_off */
2170 __update_reg_bounds(dst_reg);
2171 break;
2172 case BPF_RSH:
2173 if (umax_val > 63) {
2174 /* Shifts greater than 63 are undefined. This includes
2175 * shifts by a negative number.
2176 */
2149 mark_reg_unknown(regs, insn->dst_reg);
2177 mark_reg_unknown(env, regs, insn->dst_reg);
2150 break;
2151 }
2152 /* BPF_RSH is an unsigned shift, so make the appropriate casts */
2153 if (dst_reg->smin_value < 0) {
2154 if (umin_val) {
2155 /* Sign bit will be cleared */
2156 dst_reg->smin_value = 0;
2157 } else {

--- 11 unchanged lines hidden (view full) ---

2169 else
2170 dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val);
2171 dst_reg->umin_value >>= umax_val;
2172 dst_reg->umax_value >>= umin_val;
2173 /* We may learn something more from the var_off */
2174 __update_reg_bounds(dst_reg);
2175 break;
2176 default:
2178 break;
2179 }
2180 /* BPF_RSH is an unsigned shift, so make the appropriate casts */
2181 if (dst_reg->smin_value < 0) {
2182 if (umin_val) {
2183 /* Sign bit will be cleared */
2184 dst_reg->smin_value = 0;
2185 } else {

--- 11 unchanged lines hidden (view full) ---

2197 else
2198 dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val);
2199 dst_reg->umin_value >>= umax_val;
2200 dst_reg->umax_value >>= umin_val;
2201 /* We may learn something more from the var_off */
2202 __update_reg_bounds(dst_reg);
2203 break;
2204 default:
2177 mark_reg_unknown(regs, insn->dst_reg);
2205 mark_reg_unknown(env, regs, insn->dst_reg);
2178 break;
2179 }
2180
2181 __reg_deduce_bounds(dst_reg);
2182 __reg_bound_offset(dst_reg);
2183 return 0;
2184}
2185
2186/* Handles ALU ops other than BPF_END, BPF_NEG and BPF_MOV: computes new min/max
2187 * and var_off.
2188 */
2189static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
2190 struct bpf_insn *insn)
2191{
2206 break;
2207 }
2208
2209 __reg_deduce_bounds(dst_reg);
2210 __reg_bound_offset(dst_reg);
2211 return 0;
2212}
2213
2214/* Handles ALU ops other than BPF_END, BPF_NEG and BPF_MOV: computes new min/max
2215 * and var_off.
2216 */
2217static int adjust_reg_min_max_vals(struct bpf_verifier_env *env,
2218 struct bpf_insn *insn)
2219{
2192 struct bpf_reg_state *regs = env->cur_state.regs, *dst_reg, *src_reg;
2220 struct bpf_reg_state *regs = cur_regs(env), *dst_reg, *src_reg;
2193 struct bpf_reg_state *ptr_reg = NULL, off_reg = {0};
2194 u8 opcode = BPF_OP(insn->code);
2195 int rc;
2196
2197 dst_reg = &regs[insn->dst_reg];
2198 src_reg = NULL;
2199 if (dst_reg->type != SCALAR_VALUE)
2200 ptr_reg = dst_reg;
2201 if (BPF_SRC(insn->code) == BPF_X) {
2202 src_reg = &regs[insn->src_reg];
2203 if (src_reg->type != SCALAR_VALUE) {
2204 if (dst_reg->type != SCALAR_VALUE) {
2205 /* Combining two pointers by any ALU op yields
2206 * an arbitrary scalar.
2207 */
2208 if (!env->allow_ptr_leaks) {
2221 struct bpf_reg_state *ptr_reg = NULL, off_reg = {0};
2222 u8 opcode = BPF_OP(insn->code);
2223 int rc;
2224
2225 dst_reg = &regs[insn->dst_reg];
2226 src_reg = NULL;
2227 if (dst_reg->type != SCALAR_VALUE)
2228 ptr_reg = dst_reg;
2229 if (BPF_SRC(insn->code) == BPF_X) {
2230 src_reg = &regs[insn->src_reg];
2231 if (src_reg->type != SCALAR_VALUE) {
2232 if (dst_reg->type != SCALAR_VALUE) {
2233 /* Combining two pointers by any ALU op yields
2234 * an arbitrary scalar.
2235 */
2236 if (!env->allow_ptr_leaks) {
2209 verbose("R%d pointer %s pointer prohibited\n",
2237 verbose(env, "R%d pointer %s pointer prohibited\n",
2210 insn->dst_reg,
2211 bpf_alu_string[opcode >> 4]);
2212 return -EACCES;
2213 }
2238 insn->dst_reg,
2239 bpf_alu_string[opcode >> 4]);
2240 return -EACCES;
2241 }
2214 mark_reg_unknown(regs, insn->dst_reg);
2242 mark_reg_unknown(env, regs, insn->dst_reg);
2215 return 0;
2216 } else {
2217 /* scalar += pointer
2218 * This is legal, but we have to reverse our
2219 * src/dest handling in computing the range
2220 */
2221 rc = adjust_ptr_min_max_vals(env, insn,
2222 src_reg, dst_reg);

--- 35 unchanged lines hidden (view full) ---

2258 env, insn, dst_reg, off_reg);
2259 }
2260 return rc;
2261 }
2262 }
2263
2264 /* Got here implies adding two SCALAR_VALUEs */
2265 if (WARN_ON_ONCE(ptr_reg)) {
2243 return 0;
2244 } else {
2245 /* scalar += pointer
2246 * This is legal, but we have to reverse our
2247 * src/dest handling in computing the range
2248 */
2249 rc = adjust_ptr_min_max_vals(env, insn,
2250 src_reg, dst_reg);

--- 35 unchanged lines hidden (view full) ---

2286 env, insn, dst_reg, off_reg);
2287 }
2288 return rc;
2289 }
2290 }
2291
2292 /* Got here implies adding two SCALAR_VALUEs */
2293 if (WARN_ON_ONCE(ptr_reg)) {
2266 print_verifier_state(&env->cur_state);
2267 verbose("verifier internal error: unexpected ptr_reg\n");
2294 print_verifier_state(env, env->cur_state);
2295 verbose(env, "verifier internal error: unexpected ptr_reg\n");
2268 return -EINVAL;
2269 }
2270 if (WARN_ON(!src_reg)) {
2296 return -EINVAL;
2297 }
2298 if (WARN_ON(!src_reg)) {
2271 print_verifier_state(&env->cur_state);
2272 verbose("verifier internal error: no src_reg\n");
2299 print_verifier_state(env, env->cur_state);
2300 verbose(env, "verifier internal error: no src_reg\n");
2273 return -EINVAL;
2274 }
2275 return adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
2276}
2277
2278/* check validity of 32-bit and 64-bit arithmetic operations */
2279static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
2280{
2301 return -EINVAL;
2302 }
2303 return adjust_scalar_min_max_vals(env, insn, dst_reg, *src_reg);
2304}
2305
2306/* check validity of 32-bit and 64-bit arithmetic operations */
2307static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
2308{
2281 struct bpf_reg_state *regs = env->cur_state.regs;
2309 struct bpf_reg_state *regs = cur_regs(env);
2282 u8 opcode = BPF_OP(insn->code);
2283 int err;
2284
2285 if (opcode == BPF_END || opcode == BPF_NEG) {
2286 if (opcode == BPF_NEG) {
2287 if (BPF_SRC(insn->code) != 0 ||
2288 insn->src_reg != BPF_REG_0 ||
2289 insn->off != 0 || insn->imm != 0) {
2310 u8 opcode = BPF_OP(insn->code);
2311 int err;
2312
2313 if (opcode == BPF_END || opcode == BPF_NEG) {
2314 if (opcode == BPF_NEG) {
2315 if (BPF_SRC(insn->code) != 0 ||
2316 insn->src_reg != BPF_REG_0 ||
2317 insn->off != 0 || insn->imm != 0) {
2290 verbose("BPF_NEG uses reserved fields\n");
2318 verbose(env, "BPF_NEG uses reserved fields\n");
2291 return -EINVAL;
2292 }
2293 } else {
2294 if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
2295 (insn->imm != 16 && insn->imm != 32 && insn->imm != 64) ||
2296 BPF_CLASS(insn->code) == BPF_ALU64) {
2319 return -EINVAL;
2320 }
2321 } else {
2322 if (insn->src_reg != BPF_REG_0 || insn->off != 0 ||
2323 (insn->imm != 16 && insn->imm != 32 && insn->imm != 64) ||
2324 BPF_CLASS(insn->code) == BPF_ALU64) {
2297 verbose("BPF_END uses reserved fields\n");
2325 verbose(env, "BPF_END uses reserved fields\n");
2298 return -EINVAL;
2299 }
2300 }
2301
2302 /* check src operand */
2303 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
2304 if (err)
2305 return err;
2306
2307 if (is_pointer_value(env, insn->dst_reg)) {
2326 return -EINVAL;
2327 }
2328 }
2329
2330 /* check src operand */
2331 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
2332 if (err)
2333 return err;
2334
2335 if (is_pointer_value(env, insn->dst_reg)) {
2308 verbose("R%d pointer arithmetic prohibited\n",
2336 verbose(env, "R%d pointer arithmetic prohibited\n",
2309 insn->dst_reg);
2310 return -EACCES;
2311 }
2312
2313 /* check dest operand */
2314 err = check_reg_arg(env, insn->dst_reg, DST_OP);
2315 if (err)
2316 return err;
2317
2318 } else if (opcode == BPF_MOV) {
2319
2320 if (BPF_SRC(insn->code) == BPF_X) {
2321 if (insn->imm != 0 || insn->off != 0) {
2337 insn->dst_reg);
2338 return -EACCES;
2339 }
2340
2341 /* check dest operand */
2342 err = check_reg_arg(env, insn->dst_reg, DST_OP);
2343 if (err)
2344 return err;
2345
2346 } else if (opcode == BPF_MOV) {
2347
2348 if (BPF_SRC(insn->code) == BPF_X) {
2349 if (insn->imm != 0 || insn->off != 0) {
2322 verbose("BPF_MOV uses reserved fields\n");
2350 verbose(env, "BPF_MOV uses reserved fields\n");
2323 return -EINVAL;
2324 }
2325
2326 /* check src operand */
2327 err = check_reg_arg(env, insn->src_reg, SRC_OP);
2328 if (err)
2329 return err;
2330 } else {
2331 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
2351 return -EINVAL;
2352 }
2353
2354 /* check src operand */
2355 err = check_reg_arg(env, insn->src_reg, SRC_OP);
2356 if (err)
2357 return err;
2358 } else {
2359 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
2332 verbose("BPF_MOV uses reserved fields\n");
2360 verbose(env, "BPF_MOV uses reserved fields\n");
2333 return -EINVAL;
2334 }
2335 }
2336
2337 /* check dest operand */
2338 err = check_reg_arg(env, insn->dst_reg, DST_OP);
2339 if (err)
2340 return err;
2341
2342 if (BPF_SRC(insn->code) == BPF_X) {
2343 if (BPF_CLASS(insn->code) == BPF_ALU64) {
2344 /* case: R1 = R2
2345 * copy register state to dest reg
2346 */
2347 regs[insn->dst_reg] = regs[insn->src_reg];
2361 return -EINVAL;
2362 }
2363 }
2364
2365 /* check dest operand */
2366 err = check_reg_arg(env, insn->dst_reg, DST_OP);
2367 if (err)
2368 return err;
2369
2370 if (BPF_SRC(insn->code) == BPF_X) {
2371 if (BPF_CLASS(insn->code) == BPF_ALU64) {
2372 /* case: R1 = R2
2373 * copy register state to dest reg
2374 */
2375 regs[insn->dst_reg] = regs[insn->src_reg];
2376 regs[insn->dst_reg].live |= REG_LIVE_WRITTEN;
2348 } else {
2349 /* R1 = (u32) R2 */
2350 if (is_pointer_value(env, insn->src_reg)) {
2377 } else {
2378 /* R1 = (u32) R2 */
2379 if (is_pointer_value(env, insn->src_reg)) {
2351 verbose("R%d partial copy of pointer\n",
2380 verbose(env,
2381 "R%d partial copy of pointer\n",
2352 insn->src_reg);
2353 return -EACCES;
2354 }
2382 insn->src_reg);
2383 return -EACCES;
2384 }
2355 mark_reg_unknown(regs, insn->dst_reg);
2385 mark_reg_unknown(env, regs, insn->dst_reg);
2356 /* high 32 bits are known zero. */
2357 regs[insn->dst_reg].var_off = tnum_cast(
2358 regs[insn->dst_reg].var_off, 4);
2359 __update_reg_bounds(&regs[insn->dst_reg]);
2360 }
2361 } else {
2362 /* case: R = imm
2363 * remember the value we stored into this reg
2364 */
2365 regs[insn->dst_reg].type = SCALAR_VALUE;
2366 __mark_reg_known(regs + insn->dst_reg, insn->imm);
2367 }
2368
2369 } else if (opcode > BPF_END) {
2386 /* high 32 bits are known zero. */
2387 regs[insn->dst_reg].var_off = tnum_cast(
2388 regs[insn->dst_reg].var_off, 4);
2389 __update_reg_bounds(&regs[insn->dst_reg]);
2390 }
2391 } else {
2392 /* case: R = imm
2393 * remember the value we stored into this reg
2394 */
2395 regs[insn->dst_reg].type = SCALAR_VALUE;
2396 __mark_reg_known(regs + insn->dst_reg, insn->imm);
2397 }
2398
2399 } else if (opcode > BPF_END) {
2370 verbose("invalid BPF_ALU opcode %x\n", opcode);
2400 verbose(env, "invalid BPF_ALU opcode %x\n", opcode);
2371 return -EINVAL;
2372
2373 } else { /* all other ALU ops: and, sub, xor, add, ... */
2374
2375 if (BPF_SRC(insn->code) == BPF_X) {
2376 if (insn->imm != 0 || insn->off != 0) {
2401 return -EINVAL;
2402
2403 } else { /* all other ALU ops: and, sub, xor, add, ... */
2404
2405 if (BPF_SRC(insn->code) == BPF_X) {
2406 if (insn->imm != 0 || insn->off != 0) {
2377 verbose("BPF_ALU uses reserved fields\n");
2407 verbose(env, "BPF_ALU uses reserved fields\n");
2378 return -EINVAL;
2379 }
2380 /* check src1 operand */
2381 err = check_reg_arg(env, insn->src_reg, SRC_OP);
2382 if (err)
2383 return err;
2384 } else {
2385 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
2408 return -EINVAL;
2409 }
2410 /* check src1 operand */
2411 err = check_reg_arg(env, insn->src_reg, SRC_OP);
2412 if (err)
2413 return err;
2414 } else {
2415 if (insn->src_reg != BPF_REG_0 || insn->off != 0) {
2386 verbose("BPF_ALU uses reserved fields\n");
2416 verbose(env, "BPF_ALU uses reserved fields\n");
2387 return -EINVAL;
2388 }
2389 }
2390
2391 /* check src2 operand */
2392 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
2393 if (err)
2394 return err;
2395
2396 if ((opcode == BPF_MOD || opcode == BPF_DIV) &&
2397 BPF_SRC(insn->code) == BPF_K && insn->imm == 0) {
2417 return -EINVAL;
2418 }
2419 }
2420
2421 /* check src2 operand */
2422 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
2423 if (err)
2424 return err;
2425
2426 if ((opcode == BPF_MOD || opcode == BPF_DIV) &&
2427 BPF_SRC(insn->code) == BPF_K && insn->imm == 0) {
2398 verbose("div by zero\n");
2428 verbose(env, "div by zero\n");
2399 return -EINVAL;
2400 }
2401
2402 if ((opcode == BPF_LSH || opcode == BPF_RSH ||
2403 opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
2404 int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
2405
2406 if (insn->imm < 0 || insn->imm >= size) {
2429 return -EINVAL;
2430 }
2431
2432 if ((opcode == BPF_LSH || opcode == BPF_RSH ||
2433 opcode == BPF_ARSH) && BPF_SRC(insn->code) == BPF_K) {
2434 int size = BPF_CLASS(insn->code) == BPF_ALU64 ? 64 : 32;
2435
2436 if (insn->imm < 0 || insn->imm >= size) {
2407 verbose("invalid shift %d\n", insn->imm);
2437 verbose(env, "invalid shift %d\n", insn->imm);
2408 return -EINVAL;
2409 }
2410 }
2411
2412 /* check dest operand */
2413 err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
2414 if (err)
2415 return err;
2416
2417 return adjust_reg_min_max_vals(env, insn);
2418 }
2419
2420 return 0;
2421}
2422
2423static void find_good_pkt_pointers(struct bpf_verifier_state *state,
2438 return -EINVAL;
2439 }
2440 }
2441
2442 /* check dest operand */
2443 err = check_reg_arg(env, insn->dst_reg, DST_OP_NO_MARK);
2444 if (err)
2445 return err;
2446
2447 return adjust_reg_min_max_vals(env, insn);
2448 }
2449
2450 return 0;
2451}
2452
2453static void find_good_pkt_pointers(struct bpf_verifier_state *state,
2424 struct bpf_reg_state *dst_reg)
2454 struct bpf_reg_state *dst_reg,
2455 enum bpf_reg_type type,
2456 bool range_right_open)
2425{
2426 struct bpf_reg_state *regs = state->regs, *reg;
2457{
2458 struct bpf_reg_state *regs = state->regs, *reg;
2459 u16 new_range;
2427 int i;
2428
2460 int i;
2461
2429 if (dst_reg->off < 0)
2462 if (dst_reg->off < 0 ||
2463 (dst_reg->off == 0 && range_right_open))
2430 /* This doesn't give us any range */
2431 return;
2432
2433 if (dst_reg->umax_value > MAX_PACKET_OFF ||
2434 dst_reg->umax_value + dst_reg->off > MAX_PACKET_OFF)
2435 /* Risk of overflow. For instance, ptr + (1<<63) may be less
2436 * than pkt_end, but that's because it's also less than pkt.
2437 */
2438 return;
2439
2464 /* This doesn't give us any range */
2465 return;
2466
2467 if (dst_reg->umax_value > MAX_PACKET_OFF ||
2468 dst_reg->umax_value + dst_reg->off > MAX_PACKET_OFF)
2469 /* Risk of overflow. For instance, ptr + (1<<63) may be less
2470 * than pkt_end, but that's because it's also less than pkt.
2471 */
2472 return;
2473
2440 /* LLVM can generate four kind of checks:
2474 new_range = dst_reg->off;
2475 if (range_right_open)
2476 new_range--;
2477
2478 /* Examples for register markings:
2441 *
2479 *
2442 * Type 1/2:
2480 * pkt_data in dst register:
2443 *
2444 * r2 = r3;
2445 * r2 += 8;
2446 * if (r2 > pkt_end) goto <handle exception>
2447 * <access okay>
2448 *
2449 * r2 = r3;
2450 * r2 += 8;
2451 * if (r2 < pkt_end) goto <access okay>
2452 * <handle exception>
2453 *
2454 * Where:
2455 * r2 == dst_reg, pkt_end == src_reg
2456 * r2=pkt(id=n,off=8,r=0)
2457 * r3=pkt(id=n,off=0,r=0)
2458 *
2481 *
2482 * r2 = r3;
2483 * r2 += 8;
2484 * if (r2 > pkt_end) goto <handle exception>
2485 * <access okay>
2486 *
2487 * r2 = r3;
2488 * r2 += 8;
2489 * if (r2 < pkt_end) goto <access okay>
2490 * <handle exception>
2491 *
2492 * Where:
2493 * r2 == dst_reg, pkt_end == src_reg
2494 * r2=pkt(id=n,off=8,r=0)
2495 * r3=pkt(id=n,off=0,r=0)
2496 *
2459 * Type 3/4:
2497 * pkt_data in src register:
2460 *
2461 * r2 = r3;
2462 * r2 += 8;
2463 * if (pkt_end >= r2) goto <access okay>
2464 * <handle exception>
2465 *
2466 * r2 = r3;
2467 * r2 += 8;
2468 * if (pkt_end <= r2) goto <handle exception>
2469 * <access okay>
2470 *
2471 * Where:
2472 * pkt_end == dst_reg, r2 == src_reg
2473 * r2=pkt(id=n,off=8,r=0)
2474 * r3=pkt(id=n,off=0,r=0)
2475 *
2476 * Find register r3 and mark its range as r3=pkt(id=n,off=0,r=8)
2498 *
2499 * r2 = r3;
2500 * r2 += 8;
2501 * if (pkt_end >= r2) goto <access okay>
2502 * <handle exception>
2503 *
2504 * r2 = r3;
2505 * r2 += 8;
2506 * if (pkt_end <= r2) goto <handle exception>
2507 * <access okay>
2508 *
2509 * Where:
2510 * pkt_end == dst_reg, r2 == src_reg
2511 * r2=pkt(id=n,off=8,r=0)
2512 * r3=pkt(id=n,off=0,r=0)
2513 *
2514 * Find register r3 and mark its range as r3=pkt(id=n,off=0,r=8)
2477 * so that range of bytes [r3, r3 + 8) is safe to access.
2515 * or r3=pkt(id=n,off=0,r=8-1), so that range of bytes [r3, r3 + 8)
2516 * and [r3, r3 + 8-1) respectively is safe to access depending on
2517 * the check.
2478 */
2479
2480 /* If our ids match, then we must have the same max_value. And we
2481 * don't care about the other reg's fixed offset, since if it's too big
2482 * the range won't allow anything.
2483 * dst_reg->off is known < MAX_PACKET_OFF, therefore it fits in a u16.
2484 */
2485 for (i = 0; i < MAX_BPF_REG; i++)
2518 */
2519
2520 /* If our ids match, then we must have the same max_value. And we
2521 * don't care about the other reg's fixed offset, since if it's too big
2522 * the range won't allow anything.
2523 * dst_reg->off is known < MAX_PACKET_OFF, therefore it fits in a u16.
2524 */
2525 for (i = 0; i < MAX_BPF_REG; i++)
2486 if (regs[i].type == PTR_TO_PACKET && regs[i].id == dst_reg->id)
2526 if (regs[i].type == type && regs[i].id == dst_reg->id)
2487 /* keep the maximum range already checked */
2527 /* keep the maximum range already checked */
2488 regs[i].range = max_t(u16, regs[i].range, dst_reg->off);
2528 regs[i].range = max(regs[i].range, new_range);
2489
2529
2490 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
2491 if (state->stack_slot_type[i] != STACK_SPILL)
2530 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
2531 if (state->stack[i].slot_type[0] != STACK_SPILL)
2492 continue;
2532 continue;
2493 reg = &state->spilled_regs[i / BPF_REG_SIZE];
2494 if (reg->type == PTR_TO_PACKET && reg->id == dst_reg->id)
2495 reg->range = max_t(u16, reg->range, dst_reg->off);
2533 reg = &state->stack[i].spilled_ptr;
2534 if (reg->type == type && reg->id == dst_reg->id)
2535 reg->range = max(reg->range, new_range);
2496 }
2497}
2498
2499/* Adjusts the register min/max values in the case that the dst_reg is the
2500 * variable register that we are working on, and src_reg is a constant or we're
2501 * simply doing a BPF_K check.
2502 * In JEQ/JNE cases we also adjust the var_off values.
2503 */

--- 231 unchanged lines hidden (view full) ---

2735{
2736 struct bpf_reg_state *regs = state->regs;
2737 u32 id = regs[regno].id;
2738 int i;
2739
2740 for (i = 0; i < MAX_BPF_REG; i++)
2741 mark_map_reg(regs, i, id, is_null);
2742
2536 }
2537}
2538
2539/* Adjusts the register min/max values in the case that the dst_reg is the
2540 * variable register that we are working on, and src_reg is a constant or we're
2541 * simply doing a BPF_K check.
2542 * In JEQ/JNE cases we also adjust the var_off values.
2543 */

--- 231 unchanged lines hidden (view full) ---

2775{
2776 struct bpf_reg_state *regs = state->regs;
2777 u32 id = regs[regno].id;
2778 int i;
2779
2780 for (i = 0; i < MAX_BPF_REG; i++)
2781 mark_map_reg(regs, i, id, is_null);
2782
2743 for (i = 0; i < MAX_BPF_STACK; i += BPF_REG_SIZE) {
2744 if (state->stack_slot_type[i] != STACK_SPILL)
2783 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
2784 if (state->stack[i].slot_type[0] != STACK_SPILL)
2745 continue;
2785 continue;
2746 mark_map_reg(state->spilled_regs, i / BPF_REG_SIZE, id, is_null);
2786 mark_map_reg(&state->stack[i].spilled_ptr, 0, id, is_null);
2747 }
2748}
2749
2787 }
2788}
2789
2790static bool try_match_pkt_pointers(const struct bpf_insn *insn,
2791 struct bpf_reg_state *dst_reg,
2792 struct bpf_reg_state *src_reg,
2793 struct bpf_verifier_state *this_branch,
2794 struct bpf_verifier_state *other_branch)
2795{
2796 if (BPF_SRC(insn->code) != BPF_X)
2797 return false;
2798
2799 switch (BPF_OP(insn->code)) {
2800 case BPF_JGT:
2801 if ((dst_reg->type == PTR_TO_PACKET &&
2802 src_reg->type == PTR_TO_PACKET_END) ||
2803 (dst_reg->type == PTR_TO_PACKET_META &&
2804 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
2805 /* pkt_data' > pkt_end, pkt_meta' > pkt_data */
2806 find_good_pkt_pointers(this_branch, dst_reg,
2807 dst_reg->type, false);
2808 } else if ((dst_reg->type == PTR_TO_PACKET_END &&
2809 src_reg->type == PTR_TO_PACKET) ||
2810 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
2811 src_reg->type == PTR_TO_PACKET_META)) {
2812 /* pkt_end > pkt_data', pkt_data > pkt_meta' */
2813 find_good_pkt_pointers(other_branch, src_reg,
2814 src_reg->type, true);
2815 } else {
2816 return false;
2817 }
2818 break;
2819 case BPF_JLT:
2820 if ((dst_reg->type == PTR_TO_PACKET &&
2821 src_reg->type == PTR_TO_PACKET_END) ||
2822 (dst_reg->type == PTR_TO_PACKET_META &&
2823 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
2824 /* pkt_data' < pkt_end, pkt_meta' < pkt_data */
2825 find_good_pkt_pointers(other_branch, dst_reg,
2826 dst_reg->type, true);
2827 } else if ((dst_reg->type == PTR_TO_PACKET_END &&
2828 src_reg->type == PTR_TO_PACKET) ||
2829 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
2830 src_reg->type == PTR_TO_PACKET_META)) {
2831 /* pkt_end < pkt_data', pkt_data > pkt_meta' */
2832 find_good_pkt_pointers(this_branch, src_reg,
2833 src_reg->type, false);
2834 } else {
2835 return false;
2836 }
2837 break;
2838 case BPF_JGE:
2839 if ((dst_reg->type == PTR_TO_PACKET &&
2840 src_reg->type == PTR_TO_PACKET_END) ||
2841 (dst_reg->type == PTR_TO_PACKET_META &&
2842 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
2843 /* pkt_data' >= pkt_end, pkt_meta' >= pkt_data */
2844 find_good_pkt_pointers(this_branch, dst_reg,
2845 dst_reg->type, true);
2846 } else if ((dst_reg->type == PTR_TO_PACKET_END &&
2847 src_reg->type == PTR_TO_PACKET) ||
2848 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
2849 src_reg->type == PTR_TO_PACKET_META)) {
2850 /* pkt_end >= pkt_data', pkt_data >= pkt_meta' */
2851 find_good_pkt_pointers(other_branch, src_reg,
2852 src_reg->type, false);
2853 } else {
2854 return false;
2855 }
2856 break;
2857 case BPF_JLE:
2858 if ((dst_reg->type == PTR_TO_PACKET &&
2859 src_reg->type == PTR_TO_PACKET_END) ||
2860 (dst_reg->type == PTR_TO_PACKET_META &&
2861 reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET))) {
2862 /* pkt_data' <= pkt_end, pkt_meta' <= pkt_data */
2863 find_good_pkt_pointers(other_branch, dst_reg,
2864 dst_reg->type, false);
2865 } else if ((dst_reg->type == PTR_TO_PACKET_END &&
2866 src_reg->type == PTR_TO_PACKET) ||
2867 (reg_is_init_pkt_pointer(dst_reg, PTR_TO_PACKET) &&
2868 src_reg->type == PTR_TO_PACKET_META)) {
2869 /* pkt_end <= pkt_data', pkt_data <= pkt_meta' */
2870 find_good_pkt_pointers(this_branch, src_reg,
2871 src_reg->type, true);
2872 } else {
2873 return false;
2874 }
2875 break;
2876 default:
2877 return false;
2878 }
2879
2880 return true;
2881}
2882
2750static int check_cond_jmp_op(struct bpf_verifier_env *env,
2751 struct bpf_insn *insn, int *insn_idx)
2752{
2883static int check_cond_jmp_op(struct bpf_verifier_env *env,
2884 struct bpf_insn *insn, int *insn_idx)
2885{
2753 struct bpf_verifier_state *other_branch, *this_branch = &env->cur_state;
2886 struct bpf_verifier_state *other_branch, *this_branch = env->cur_state;
2754 struct bpf_reg_state *regs = this_branch->regs, *dst_reg;
2755 u8 opcode = BPF_OP(insn->code);
2756 int err;
2757
2758 if (opcode > BPF_JSLE) {
2887 struct bpf_reg_state *regs = this_branch->regs, *dst_reg;
2888 u8 opcode = BPF_OP(insn->code);
2889 int err;
2890
2891 if (opcode > BPF_JSLE) {
2759 verbose("invalid BPF_JMP opcode %x\n", opcode);
2892 verbose(env, "invalid BPF_JMP opcode %x\n", opcode);
2760 return -EINVAL;
2761 }
2762
2763 if (BPF_SRC(insn->code) == BPF_X) {
2764 if (insn->imm != 0) {
2893 return -EINVAL;
2894 }
2895
2896 if (BPF_SRC(insn->code) == BPF_X) {
2897 if (insn->imm != 0) {
2765 verbose("BPF_JMP uses reserved fields\n");
2898 verbose(env, "BPF_JMP uses reserved fields\n");
2766 return -EINVAL;
2767 }
2768
2769 /* check src1 operand */
2770 err = check_reg_arg(env, insn->src_reg, SRC_OP);
2771 if (err)
2772 return err;
2773
2774 if (is_pointer_value(env, insn->src_reg)) {
2899 return -EINVAL;
2900 }
2901
2902 /* check src1 operand */
2903 err = check_reg_arg(env, insn->src_reg, SRC_OP);
2904 if (err)
2905 return err;
2906
2907 if (is_pointer_value(env, insn->src_reg)) {
2775 verbose("R%d pointer comparison prohibited\n",
2908 verbose(env, "R%d pointer comparison prohibited\n",
2776 insn->src_reg);
2777 return -EACCES;
2778 }
2779 } else {
2780 if (insn->src_reg != BPF_REG_0) {
2909 insn->src_reg);
2910 return -EACCES;
2911 }
2912 } else {
2913 if (insn->src_reg != BPF_REG_0) {
2781 verbose("BPF_JMP uses reserved fields\n");
2914 verbose(env, "BPF_JMP uses reserved fields\n");
2782 return -EINVAL;
2783 }
2784 }
2785
2786 /* check src2 operand */
2787 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
2788 if (err)
2789 return err;

--- 58 unchanged lines hidden (view full) ---

2848 if (BPF_SRC(insn->code) == BPF_K &&
2849 insn->imm == 0 && (opcode == BPF_JEQ || opcode == BPF_JNE) &&
2850 dst_reg->type == PTR_TO_MAP_VALUE_OR_NULL) {
2851 /* Mark all identical map registers in each branch as either
2852 * safe or unknown depending R == 0 or R != 0 conditional.
2853 */
2854 mark_map_regs(this_branch, insn->dst_reg, opcode == BPF_JNE);
2855 mark_map_regs(other_branch, insn->dst_reg, opcode == BPF_JEQ);
2915 return -EINVAL;
2916 }
2917 }
2918
2919 /* check src2 operand */
2920 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
2921 if (err)
2922 return err;

--- 58 unchanged lines hidden (view full) ---

2981 if (BPF_SRC(insn->code) == BPF_K &&
2982 insn->imm == 0 && (opcode == BPF_JEQ || opcode == BPF_JNE) &&
2983 dst_reg->type == PTR_TO_MAP_VALUE_OR_NULL) {
2984 /* Mark all identical map registers in each branch as either
2985 * safe or unknown depending R == 0 or R != 0 conditional.
2986 */
2987 mark_map_regs(this_branch, insn->dst_reg, opcode == BPF_JNE);
2988 mark_map_regs(other_branch, insn->dst_reg, opcode == BPF_JEQ);
2856 } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JGT &&
2857 dst_reg->type == PTR_TO_PACKET &&
2858 regs[insn->src_reg].type == PTR_TO_PACKET_END) {
2859 find_good_pkt_pointers(this_branch, dst_reg);
2860 } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JLT &&
2861 dst_reg->type == PTR_TO_PACKET &&
2862 regs[insn->src_reg].type == PTR_TO_PACKET_END) {
2863 find_good_pkt_pointers(other_branch, dst_reg);
2864 } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JGE &&
2865 dst_reg->type == PTR_TO_PACKET_END &&
2866 regs[insn->src_reg].type == PTR_TO_PACKET) {
2867 find_good_pkt_pointers(other_branch, &regs[insn->src_reg]);
2868 } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JLE &&
2869 dst_reg->type == PTR_TO_PACKET_END &&
2870 regs[insn->src_reg].type == PTR_TO_PACKET) {
2871 find_good_pkt_pointers(this_branch, &regs[insn->src_reg]);
2872 } else if (is_pointer_value(env, insn->dst_reg)) {
2873 verbose("R%d pointer comparison prohibited\n", insn->dst_reg);
2989 } else if (!try_match_pkt_pointers(insn, dst_reg, &regs[insn->src_reg],
2990 this_branch, other_branch) &&
2991 is_pointer_value(env, insn->dst_reg)) {
2992 verbose(env, "R%d pointer comparison prohibited\n",
2993 insn->dst_reg);
2874 return -EACCES;
2875 }
2994 return -EACCES;
2995 }
2876 if (log_level)
2877 print_verifier_state(this_branch);
2996 if (env->log.level)
2997 print_verifier_state(env, this_branch);
2878 return 0;
2879}
2880
2881/* return the map pointer stored inside BPF_LD_IMM64 instruction */
2882static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
2883{
2884 u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32;
2885
2886 return (struct bpf_map *) (unsigned long) imm64;
2887}
2888
2889/* verify BPF_LD_IMM64 instruction */
2890static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
2891{
2998 return 0;
2999}
3000
3001/* return the map pointer stored inside BPF_LD_IMM64 instruction */
3002static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
3003{
3004 u64 imm64 = ((u64) (u32) insn[0].imm) | ((u64) (u32) insn[1].imm) << 32;
3005
3006 return (struct bpf_map *) (unsigned long) imm64;
3007}
3008
3009/* verify BPF_LD_IMM64 instruction */
3010static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
3011{
2892 struct bpf_reg_state *regs = env->cur_state.regs;
3012 struct bpf_reg_state *regs = cur_regs(env);
2893 int err;
2894
2895 if (BPF_SIZE(insn->code) != BPF_DW) {
3013 int err;
3014
3015 if (BPF_SIZE(insn->code) != BPF_DW) {
2896 verbose("invalid BPF_LD_IMM insn\n");
3016 verbose(env, "invalid BPF_LD_IMM insn\n");
2897 return -EINVAL;
2898 }
2899 if (insn->off != 0) {
3017 return -EINVAL;
3018 }
3019 if (insn->off != 0) {
2900 verbose("BPF_LD_IMM64 uses reserved fields\n");
3020 verbose(env, "BPF_LD_IMM64 uses reserved fields\n");
2901 return -EINVAL;
2902 }
2903
2904 err = check_reg_arg(env, insn->dst_reg, DST_OP);
2905 if (err)
2906 return err;
2907
2908 if (insn->src_reg == 0) {

--- 36 unchanged lines hidden (view full) ---

2945 * SRC == any register
2946 * IMM == 32-bit immediate
2947 *
2948 * Output:
2949 * R0 - 8/16/32-bit skb data converted to cpu endianness
2950 */
2951static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
2952{
3021 return -EINVAL;
3022 }
3023
3024 err = check_reg_arg(env, insn->dst_reg, DST_OP);
3025 if (err)
3026 return err;
3027
3028 if (insn->src_reg == 0) {

--- 36 unchanged lines hidden (view full) ---

3065 * SRC == any register
3066 * IMM == 32-bit immediate
3067 *
3068 * Output:
3069 * R0 - 8/16/32-bit skb data converted to cpu endianness
3070 */
3071static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
3072{
2953 struct bpf_reg_state *regs = env->cur_state.regs;
3073 struct bpf_reg_state *regs = cur_regs(env);
2954 u8 mode = BPF_MODE(insn->code);
2955 int i, err;
2956
2957 if (!may_access_skb(env->prog->type)) {
3074 u8 mode = BPF_MODE(insn->code);
3075 int i, err;
3076
3077 if (!may_access_skb(env->prog->type)) {
2958 verbose("BPF_LD_[ABS|IND] instructions not allowed for this program type\n");
3078 verbose(env, "BPF_LD_[ABS|IND] instructions not allowed for this program type\n");
2959 return -EINVAL;
2960 }
2961
2962 if (insn->dst_reg != BPF_REG_0 || insn->off != 0 ||
2963 BPF_SIZE(insn->code) == BPF_DW ||
2964 (mode == BPF_ABS && insn->src_reg != BPF_REG_0)) {
3079 return -EINVAL;
3080 }
3081
3082 if (insn->dst_reg != BPF_REG_0 || insn->off != 0 ||
3083 BPF_SIZE(insn->code) == BPF_DW ||
3084 (mode == BPF_ABS && insn->src_reg != BPF_REG_0)) {
2965 verbose("BPF_LD_[ABS|IND] uses reserved fields\n");
3085 verbose(env, "BPF_LD_[ABS|IND] uses reserved fields\n");
2966 return -EINVAL;
2967 }
2968
2969 /* check whether implicit source operand (register R6) is readable */
2970 err = check_reg_arg(env, BPF_REG_6, SRC_OP);
2971 if (err)
2972 return err;
2973
2974 if (regs[BPF_REG_6].type != PTR_TO_CTX) {
3086 return -EINVAL;
3087 }
3088
3089 /* check whether implicit source operand (register R6) is readable */
3090 err = check_reg_arg(env, BPF_REG_6, SRC_OP);
3091 if (err)
3092 return err;
3093
3094 if (regs[BPF_REG_6].type != PTR_TO_CTX) {
2975 verbose("at the time of BPF_LD_ABS|IND R6 != pointer to skb\n");
3095 verbose(env,
3096 "at the time of BPF_LD_ABS|IND R6 != pointer to skb\n");
2976 return -EINVAL;
2977 }
2978
2979 if (mode == BPF_IND) {
2980 /* check explicit source operand */
2981 err = check_reg_arg(env, insn->src_reg, SRC_OP);
2982 if (err)
2983 return err;
2984 }
2985
2986 /* reset caller saved regs to unreadable */
2987 for (i = 0; i < CALLER_SAVED_REGS; i++) {
3097 return -EINVAL;
3098 }
3099
3100 if (mode == BPF_IND) {
3101 /* check explicit source operand */
3102 err = check_reg_arg(env, insn->src_reg, SRC_OP);
3103 if (err)
3104 return err;
3105 }
3106
3107 /* reset caller saved regs to unreadable */
3108 for (i = 0; i < CALLER_SAVED_REGS; i++) {
2988 mark_reg_not_init(regs, caller_saved[i]);
3109 mark_reg_not_init(env, regs, caller_saved[i]);
2989 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
2990 }
2991
2992 /* mark destination R0 register as readable, since it contains
2993 * the value fetched from the packet.
2994 * Already marked as written above.
2995 */
3110 check_reg_arg(env, caller_saved[i], DST_OP_NO_MARK);
3111 }
3112
3113 /* mark destination R0 register as readable, since it contains
3114 * the value fetched from the packet.
3115 * Already marked as written above.
3116 */
2996 mark_reg_unknown(regs, BPF_REG_0);
3117 mark_reg_unknown(env, regs, BPF_REG_0);
2997 return 0;
2998}
2999
3118 return 0;
3119}
3120
3121static int check_return_code(struct bpf_verifier_env *env)
3122{
3123 struct bpf_reg_state *reg;
3124 struct tnum range = tnum_range(0, 1);
3125
3126 switch (env->prog->type) {
3127 case BPF_PROG_TYPE_CGROUP_SKB:
3128 case BPF_PROG_TYPE_CGROUP_SOCK:
3129 case BPF_PROG_TYPE_SOCK_OPS:
3130 break;
3131 default:
3132 return 0;
3133 }
3134
3135 reg = cur_regs(env) + BPF_REG_0;
3136 if (reg->type != SCALAR_VALUE) {
3137 verbose(env, "At program exit the register R0 is not a known value (%s)\n",
3138 reg_type_str[reg->type]);
3139 return -EINVAL;
3140 }
3141
3142 if (!tnum_in(range, reg->var_off)) {
3143 verbose(env, "At program exit the register R0 ");
3144 if (!tnum_is_unknown(reg->var_off)) {
3145 char tn_buf[48];
3146
3147 tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
3148 verbose(env, "has value %s", tn_buf);
3149 } else {
3150 verbose(env, "has unknown scalar value");
3151 }
3152 verbose(env, " should have been 0 or 1\n");
3153 return -EINVAL;
3154 }
3155 return 0;
3156}
3157
3000/* non-recursive DFS pseudo code
3001 * 1 procedure DFS-iterative(G,v):
3002 * 2 label v as discovered
3003 * 3 let S be a stack
3004 * 4 S.push(v)
3005 * 5 while S is not empty
3006 * 6 t <- S.pop()
3007 * 7 if t is what we're looking for:

--- 44 unchanged lines hidden (view full) ---

3052{
3053 if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
3054 return 0;
3055
3056 if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
3057 return 0;
3058
3059 if (w < 0 || w >= env->prog->len) {
3158/* non-recursive DFS pseudo code
3159 * 1 procedure DFS-iterative(G,v):
3160 * 2 label v as discovered
3161 * 3 let S be a stack
3162 * 4 S.push(v)
3163 * 5 while S is not empty
3164 * 6 t <- S.pop()
3165 * 7 if t is what we're looking for:

--- 44 unchanged lines hidden (view full) ---

3210{
3211 if (e == FALLTHROUGH && insn_state[t] >= (DISCOVERED | FALLTHROUGH))
3212 return 0;
3213
3214 if (e == BRANCH && insn_state[t] >= (DISCOVERED | BRANCH))
3215 return 0;
3216
3217 if (w < 0 || w >= env->prog->len) {
3060 verbose("jump out of range from insn %d to %d\n", t, w);
3218 verbose(env, "jump out of range from insn %d to %d\n", t, w);
3061 return -EINVAL;
3062 }
3063
3064 if (e == BRANCH)
3065 /* mark branch target for state pruning */
3066 env->explored_states[w] = STATE_LIST_MARK;
3067
3068 if (insn_state[w] == 0) {
3069 /* tree-edge */
3070 insn_state[t] = DISCOVERED | e;
3071 insn_state[w] = DISCOVERED;
3072 if (cur_stack >= env->prog->len)
3073 return -E2BIG;
3074 insn_stack[cur_stack++] = w;
3075 return 1;
3076 } else if ((insn_state[w] & 0xF0) == DISCOVERED) {
3219 return -EINVAL;
3220 }
3221
3222 if (e == BRANCH)
3223 /* mark branch target for state pruning */
3224 env->explored_states[w] = STATE_LIST_MARK;
3225
3226 if (insn_state[w] == 0) {
3227 /* tree-edge */
3228 insn_state[t] = DISCOVERED | e;
3229 insn_state[w] = DISCOVERED;
3230 if (cur_stack >= env->prog->len)
3231 return -E2BIG;
3232 insn_stack[cur_stack++] = w;
3233 return 1;
3234 } else if ((insn_state[w] & 0xF0) == DISCOVERED) {
3077 verbose("back-edge from insn %d to %d\n", t, w);
3235 verbose(env, "back-edge from insn %d to %d\n", t, w);
3078 return -EINVAL;
3079 } else if (insn_state[w] == EXPLORED) {
3080 /* forward- or cross-edge */
3081 insn_state[t] = DISCOVERED | e;
3082 } else {
3236 return -EINVAL;
3237 } else if (insn_state[w] == EXPLORED) {
3238 /* forward- or cross-edge */
3239 insn_state[t] = DISCOVERED | e;
3240 } else {
3083 verbose("insn state internal bug\n");
3241 verbose(env, "insn state internal bug\n");
3084 return -EFAULT;
3085 }
3086 return 0;
3087}
3088
3089/* non-recursive depth-first-search to detect loops in BPF program
3090 * loop == back-edge in directed graph
3091 */

--- 77 unchanged lines hidden (view full) ---

3169 goto peek_stack;
3170 else if (ret < 0)
3171 goto err_free;
3172 }
3173
3174mark_explored:
3175 insn_state[t] = EXPLORED;
3176 if (cur_stack-- <= 0) {
3242 return -EFAULT;
3243 }
3244 return 0;
3245}
3246
3247/* non-recursive depth-first-search to detect loops in BPF program
3248 * loop == back-edge in directed graph
3249 */

--- 77 unchanged lines hidden (view full) ---

3327 goto peek_stack;
3328 else if (ret < 0)
3329 goto err_free;
3330 }
3331
3332mark_explored:
3333 insn_state[t] = EXPLORED;
3334 if (cur_stack-- <= 0) {
3177 verbose("pop stack internal bug\n");
3335 verbose(env, "pop stack internal bug\n");
3178 ret = -EFAULT;
3179 goto err_free;
3180 }
3181 goto peek_stack;
3182
3183check_state:
3184 for (i = 0; i < insn_cnt; i++) {
3185 if (insn_state[i] != EXPLORED) {
3336 ret = -EFAULT;
3337 goto err_free;
3338 }
3339 goto peek_stack;
3340
3341check_state:
3342 for (i = 0; i < insn_cnt; i++) {
3343 if (insn_state[i] != EXPLORED) {
3186 verbose("unreachable insn %d\n", i);
3344 verbose(env, "unreachable insn %d\n", i);
3187 ret = -EINVAL;
3188 goto err_free;
3189 }
3190 }
3191 ret = 0; /* cfg looks good */
3192
3193err_free:
3194 kfree(insn_state);

--- 98 unchanged lines hidden (view full) ---

3293 * we converted to a PTR_TO_MAP_VALUE.
3294 */
3295 if (rcur->type != PTR_TO_MAP_VALUE_OR_NULL)
3296 return false;
3297 if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)))
3298 return false;
3299 /* Check our ids match any regs they're supposed to */
3300 return check_ids(rold->id, rcur->id, idmap);
3345 ret = -EINVAL;
3346 goto err_free;
3347 }
3348 }
3349 ret = 0; /* cfg looks good */
3350
3351err_free:
3352 kfree(insn_state);

--- 98 unchanged lines hidden (view full) ---

3451 * we converted to a PTR_TO_MAP_VALUE.
3452 */
3453 if (rcur->type != PTR_TO_MAP_VALUE_OR_NULL)
3454 return false;
3455 if (memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)))
3456 return false;
3457 /* Check our ids match any regs they're supposed to */
3458 return check_ids(rold->id, rcur->id, idmap);
3459 case PTR_TO_PACKET_META:
3301 case PTR_TO_PACKET:
3460 case PTR_TO_PACKET:
3302 if (rcur->type != PTR_TO_PACKET)
3461 if (rcur->type != rold->type)
3303 return false;
3304 /* We must have at least as much range as the old ptr
3305 * did, so that any accesses which were safe before are
3306 * still safe. This is true even if old range < old off,
3307 * since someone could have accessed through (ptr - k), or
3308 * even done ptr -= k in a register, to get a safe access.
3309 */
3310 if (rold->range > rcur->range)

--- 21 unchanged lines hidden (view full) ---

3332 return false;
3333 }
3334
3335 /* Shouldn't get here; if we do, say it's not safe */
3336 WARN_ON_ONCE(1);
3337 return false;
3338}
3339
3462 return false;
3463 /* We must have at least as much range as the old ptr
3464 * did, so that any accesses which were safe before are
3465 * still safe. This is true even if old range < old off,
3466 * since someone could have accessed through (ptr - k), or
3467 * even done ptr -= k in a register, to get a safe access.
3468 */
3469 if (rold->range > rcur->range)

--- 21 unchanged lines hidden (view full) ---

3491 return false;
3492 }
3493
3494 /* Shouldn't get here; if we do, say it's not safe */
3495 WARN_ON_ONCE(1);
3496 return false;
3497}
3498
3499static bool stacksafe(struct bpf_verifier_state *old,
3500 struct bpf_verifier_state *cur,
3501 struct idpair *idmap)
3502{
3503 int i, spi;
3504
3505 /* if explored stack has more populated slots than current stack
3506 * such stacks are not equivalent
3507 */
3508 if (old->allocated_stack > cur->allocated_stack)
3509 return false;
3510
3511 /* walk slots of the explored stack and ignore any additional
3512 * slots in the current stack, since explored(safe) state
3513 * didn't use them
3514 */
3515 for (i = 0; i < old->allocated_stack; i++) {
3516 spi = i / BPF_REG_SIZE;
3517
3518 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] == STACK_INVALID)
3519 continue;
3520 if (old->stack[spi].slot_type[i % BPF_REG_SIZE] !=
3521 cur->stack[spi].slot_type[i % BPF_REG_SIZE])
3522 /* Ex: old explored (safe) state has STACK_SPILL in
3523 * this stack slot, but current has has STACK_MISC ->
3524 * this verifier states are not equivalent,
3525 * return false to continue verification of this path
3526 */
3527 return false;
3528 if (i % BPF_REG_SIZE)
3529 continue;
3530 if (old->stack[spi].slot_type[0] != STACK_SPILL)
3531 continue;
3532 if (!regsafe(&old->stack[spi].spilled_ptr,
3533 &cur->stack[spi].spilled_ptr,
3534 idmap))
3535 /* when explored and current stack slot are both storing
3536 * spilled registers, check that stored pointers types
3537 * are the same as well.
3538 * Ex: explored safe path could have stored
3539 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -8}
3540 * but current path has stored:
3541 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -16}
3542 * such verifier states are not equivalent.
3543 * return false to continue verification of this path
3544 */
3545 return false;
3546 }
3547 return true;
3548}
3549
3340/* compare two verifier states
3341 *
3342 * all states stored in state_list are known to be valid, since
3343 * verifier reached 'bpf_exit' instruction through them
3344 *
3345 * this function is called when verifier exploring different branches of
3346 * execution popped from the state stack. If it sees an old state that has
3347 * more strict register state and more strict stack state then this execution

--- 28 unchanged lines hidden (view full) ---

3376 if (!idmap)
3377 return false;
3378
3379 for (i = 0; i < MAX_BPF_REG; i++) {
3380 if (!regsafe(&old->regs[i], &cur->regs[i], idmap))
3381 goto out_free;
3382 }
3383
3550/* compare two verifier states
3551 *
3552 * all states stored in state_list are known to be valid, since
3553 * verifier reached 'bpf_exit' instruction through them
3554 *
3555 * this function is called when verifier exploring different branches of
3556 * execution popped from the state stack. If it sees an old state that has
3557 * more strict register state and more strict stack state then this execution

--- 28 unchanged lines hidden (view full) ---

3586 if (!idmap)
3587 return false;
3588
3589 for (i = 0; i < MAX_BPF_REG; i++) {
3590 if (!regsafe(&old->regs[i], &cur->regs[i], idmap))
3591 goto out_free;
3592 }
3593
3384 for (i = 0; i < MAX_BPF_STACK; i++) {
3385 if (old->stack_slot_type[i] == STACK_INVALID)
3386 continue;
3387 if (old->stack_slot_type[i] != cur->stack_slot_type[i])
3388 /* Ex: old explored (safe) state has STACK_SPILL in
3389 * this stack slot, but current has has STACK_MISC ->
3390 * this verifier states are not equivalent,
3391 * return false to continue verification of this path
3392 */
3393 goto out_free;
3394 if (i % BPF_REG_SIZE)
3395 continue;
3396 if (old->stack_slot_type[i] != STACK_SPILL)
3397 continue;
3398 if (!regsafe(&old->spilled_regs[i / BPF_REG_SIZE],
3399 &cur->spilled_regs[i / BPF_REG_SIZE],
3400 idmap))
3401 /* when explored and current stack slot are both storing
3402 * spilled registers, check that stored pointers types
3403 * are the same as well.
3404 * Ex: explored safe path could have stored
3405 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -8}
3406 * but current path has stored:
3407 * (bpf_reg_state) {.type = PTR_TO_STACK, .off = -16}
3408 * such verifier states are not equivalent.
3409 * return false to continue verification of this path
3410 */
3411 goto out_free;
3412 else
3413 continue;
3414 }
3594 if (!stacksafe(old, cur, idmap))
3595 goto out_free;
3415 ret = true;
3416out_free:
3417 kfree(idmap);
3418 return ret;
3419}
3420
3421/* A write screens off any subsequent reads; but write marks come from the
3422 * straight-line code between a state and its parent. When we arrive at a

--- 19 unchanged lines hidden (view full) ---

3442 if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
3443 continue;
3444 if (state->regs[i].live & REG_LIVE_READ) {
3445 parent->regs[i].live |= REG_LIVE_READ;
3446 touched = true;
3447 }
3448 }
3449 /* ... and stack slots */
3596 ret = true;
3597out_free:
3598 kfree(idmap);
3599 return ret;
3600}
3601
3602/* A write screens off any subsequent reads; but write marks come from the
3603 * straight-line code between a state and its parent. When we arrive at a

--- 19 unchanged lines hidden (view full) ---

3623 if (writes && (state->regs[i].live & REG_LIVE_WRITTEN))
3624 continue;
3625 if (state->regs[i].live & REG_LIVE_READ) {
3626 parent->regs[i].live |= REG_LIVE_READ;
3627 touched = true;
3628 }
3629 }
3630 /* ... and stack slots */
3450 for (i = 0; i < MAX_BPF_STACK / BPF_REG_SIZE; i++) {
3451 if (parent->stack_slot_type[i * BPF_REG_SIZE] != STACK_SPILL)
3631 for (i = 0; i < state->allocated_stack / BPF_REG_SIZE &&
3632 i < parent->allocated_stack / BPF_REG_SIZE; i++) {
3633 if (parent->stack[i].slot_type[0] != STACK_SPILL)
3452 continue;
3634 continue;
3453 if (state->stack_slot_type[i * BPF_REG_SIZE] != STACK_SPILL)
3635 if (state->stack[i].slot_type[0] != STACK_SPILL)
3454 continue;
3636 continue;
3455 if (parent->spilled_regs[i].live & REG_LIVE_READ)
3637 if (parent->stack[i].spilled_ptr.live & REG_LIVE_READ)
3456 continue;
3638 continue;
3457 if (writes && (state->spilled_regs[i].live & REG_LIVE_WRITTEN))
3639 if (writes &&
3640 (state->stack[i].spilled_ptr.live & REG_LIVE_WRITTEN))
3458 continue;
3641 continue;
3459 if (state->spilled_regs[i].live & REG_LIVE_READ) {
3460 parent->spilled_regs[i].live |= REG_LIVE_READ;
3642 if (state->stack[i].spilled_ptr.live & REG_LIVE_READ) {
3643 parent->stack[i].spilled_ptr.live |= REG_LIVE_READ;
3461 touched = true;
3462 }
3463 }
3464 return touched;
3465}
3466
3467/* "parent" is "a state from which we reach the current state", but initially
3468 * it is not the state->parent (i.e. "the state whose straight-line code leads

--- 13 unchanged lines hidden (view full) ---

3482 parent = state->parent;
3483 }
3484}
3485
3486static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
3487{
3488 struct bpf_verifier_state_list *new_sl;
3489 struct bpf_verifier_state_list *sl;
3644 touched = true;
3645 }
3646 }
3647 return touched;
3648}
3649
3650/* "parent" is "a state from which we reach the current state", but initially
3651 * it is not the state->parent (i.e. "the state whose straight-line code leads

--- 13 unchanged lines hidden (view full) ---

3665 parent = state->parent;
3666 }
3667}
3668
3669static int is_state_visited(struct bpf_verifier_env *env, int insn_idx)
3670{
3671 struct bpf_verifier_state_list *new_sl;
3672 struct bpf_verifier_state_list *sl;
3490 int i;
3673 struct bpf_verifier_state *cur = env->cur_state;
3674 int i, err;
3491
3492 sl = env->explored_states[insn_idx];
3493 if (!sl)
3494 /* this 'insn_idx' instruction wasn't marked, so we will not
3495 * be doing state search here
3496 */
3497 return 0;
3498
3499 while (sl != STATE_LIST_MARK) {
3675
3676 sl = env->explored_states[insn_idx];
3677 if (!sl)
3678 /* this 'insn_idx' instruction wasn't marked, so we will not
3679 * be doing state search here
3680 */
3681 return 0;
3682
3683 while (sl != STATE_LIST_MARK) {
3500 if (states_equal(env, &sl->state, &env->cur_state)) {
3684 if (states_equal(env, &sl->state, cur)) {
3501 /* reached equivalent register/stack state,
3502 * prune the search.
3503 * Registers read by the continuation are read by us.
3504 * If we have any write marks in env->cur_state, they
3505 * will prevent corresponding reads in the continuation
3506 * from reaching our parent (an explored_state). Our
3507 * own state will get the read marks recorded, but
3508 * they'll be immediately forgotten as we're pruning
3509 * this state and will pop a new one.
3510 */
3685 /* reached equivalent register/stack state,
3686 * prune the search.
3687 * Registers read by the continuation are read by us.
3688 * If we have any write marks in env->cur_state, they
3689 * will prevent corresponding reads in the continuation
3690 * from reaching our parent (an explored_state). Our
3691 * own state will get the read marks recorded, but
3692 * they'll be immediately forgotten as we're pruning
3693 * this state and will pop a new one.
3694 */
3511 propagate_liveness(&sl->state, &env->cur_state);
3695 propagate_liveness(&sl->state, cur);
3512 return 1;
3513 }
3514 sl = sl->next;
3515 }
3516
3517 /* there were no equivalent states, remember current one.
3518 * technically the current state is not proven to be safe yet,
3519 * but it will either reach bpf_exit (which means it's safe) or
3520 * it will be rejected. Since there are no loops, we won't be
3521 * seeing this 'insn_idx' instruction again on the way to bpf_exit
3522 */
3696 return 1;
3697 }
3698 sl = sl->next;
3699 }
3700
3701 /* there were no equivalent states, remember current one.
3702 * technically the current state is not proven to be safe yet,
3703 * but it will either reach bpf_exit (which means it's safe) or
3704 * it will be rejected. Since there are no loops, we won't be
3705 * seeing this 'insn_idx' instruction again on the way to bpf_exit
3706 */
3523 new_sl = kmalloc(sizeof(struct bpf_verifier_state_list), GFP_USER);
3707 new_sl = kzalloc(sizeof(struct bpf_verifier_state_list), GFP_KERNEL);
3524 if (!new_sl)
3525 return -ENOMEM;
3526
3527 /* add new state to the head of linked list */
3708 if (!new_sl)
3709 return -ENOMEM;
3710
3711 /* add new state to the head of linked list */
3528 memcpy(&new_sl->state, &env->cur_state, sizeof(env->cur_state));
3712 err = copy_verifier_state(&new_sl->state, cur);
3713 if (err) {
3714 free_verifier_state(&new_sl->state, false);
3715 kfree(new_sl);
3716 return err;
3717 }
3529 new_sl->next = env->explored_states[insn_idx];
3530 env->explored_states[insn_idx] = new_sl;
3531 /* connect new state to parentage chain */
3718 new_sl->next = env->explored_states[insn_idx];
3719 env->explored_states[insn_idx] = new_sl;
3720 /* connect new state to parentage chain */
3532 env->cur_state.parent = &new_sl->state;
3721 cur->parent = &new_sl->state;
3533 /* clear write marks in current state: the writes we did are not writes
3534 * our child did, so they don't screen off its reads from us.
3535 * (There are no read marks in current state, because reads always mark
3536 * their parent and current state never has children yet. Only
3537 * explored_states can get read marks.)
3538 */
3539 for (i = 0; i < BPF_REG_FP; i++)
3722 /* clear write marks in current state: the writes we did are not writes
3723 * our child did, so they don't screen off its reads from us.
3724 * (There are no read marks in current state, because reads always mark
3725 * their parent and current state never has children yet. Only
3726 * explored_states can get read marks.)
3727 */
3728 for (i = 0; i < BPF_REG_FP; i++)
3540 env->cur_state.regs[i].live = REG_LIVE_NONE;
3541 for (i = 0; i < MAX_BPF_STACK / BPF_REG_SIZE; i++)
3542 if (env->cur_state.stack_slot_type[i * BPF_REG_SIZE] == STACK_SPILL)
3543 env->cur_state.spilled_regs[i].live = REG_LIVE_NONE;
3729 cur->regs[i].live = REG_LIVE_NONE;
3730 for (i = 0; i < cur->allocated_stack / BPF_REG_SIZE; i++)
3731 if (cur->stack[i].slot_type[0] == STACK_SPILL)
3732 cur->stack[i].spilled_ptr.live = REG_LIVE_NONE;
3544 return 0;
3545}
3546
3547static int ext_analyzer_insn_hook(struct bpf_verifier_env *env,
3548 int insn_idx, int prev_insn_idx)
3549{
3733 return 0;
3734}
3735
3736static int ext_analyzer_insn_hook(struct bpf_verifier_env *env,
3737 int insn_idx, int prev_insn_idx)
3738{
3550 if (!env->analyzer_ops || !env->analyzer_ops->insn_hook)
3551 return 0;
3739 if (env->analyzer_ops && env->analyzer_ops->insn_hook)
3740 return env->analyzer_ops->insn_hook(env, insn_idx,
3741 prev_insn_idx);
3742 if (env->dev_ops && env->dev_ops->insn_hook)
3743 return env->dev_ops->insn_hook(env, insn_idx, prev_insn_idx);
3552
3744
3553 return env->analyzer_ops->insn_hook(env, insn_idx, prev_insn_idx);
3745 return 0;
3554}
3555
3556static int do_check(struct bpf_verifier_env *env)
3557{
3746}
3747
3748static int do_check(struct bpf_verifier_env *env)
3749{
3558 struct bpf_verifier_state *state = &env->cur_state;
3750 struct bpf_verifier_state *state;
3559 struct bpf_insn *insns = env->prog->insnsi;
3751 struct bpf_insn *insns = env->prog->insnsi;
3560 struct bpf_reg_state *regs = state->regs;
3752 struct bpf_reg_state *regs;
3561 int insn_cnt = env->prog->len;
3562 int insn_idx, prev_insn_idx = 0;
3563 int insn_processed = 0;
3564 bool do_print_state = false;
3565
3753 int insn_cnt = env->prog->len;
3754 int insn_idx, prev_insn_idx = 0;
3755 int insn_processed = 0;
3756 bool do_print_state = false;
3757
3566 init_reg_state(regs);
3758 state = kzalloc(sizeof(struct bpf_verifier_state), GFP_KERNEL);
3759 if (!state)
3760 return -ENOMEM;
3761 env->cur_state = state;
3762 init_reg_state(env, state->regs);
3567 state->parent = NULL;
3568 insn_idx = 0;
3569 for (;;) {
3570 struct bpf_insn *insn;
3571 u8 class;
3572 int err;
3573
3574 if (insn_idx >= insn_cnt) {
3763 state->parent = NULL;
3764 insn_idx = 0;
3765 for (;;) {
3766 struct bpf_insn *insn;
3767 u8 class;
3768 int err;
3769
3770 if (insn_idx >= insn_cnt) {
3575 verbose("invalid insn idx %d insn_cnt %d\n",
3771 verbose(env, "invalid insn idx %d insn_cnt %d\n",
3576 insn_idx, insn_cnt);
3577 return -EFAULT;
3578 }
3579
3580 insn = &insns[insn_idx];
3581 class = BPF_CLASS(insn->code);
3582
3583 if (++insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) {
3772 insn_idx, insn_cnt);
3773 return -EFAULT;
3774 }
3775
3776 insn = &insns[insn_idx];
3777 class = BPF_CLASS(insn->code);
3778
3779 if (++insn_processed > BPF_COMPLEXITY_LIMIT_INSNS) {
3584 verbose("BPF program is too large. Processed %d insn\n",
3780 verbose(env,
3781 "BPF program is too large. Processed %d insn\n",
3585 insn_processed);
3586 return -E2BIG;
3587 }
3588
3589 err = is_state_visited(env, insn_idx);
3590 if (err < 0)
3591 return err;
3592 if (err == 1) {
3593 /* found equivalent state, can prune the search */
3782 insn_processed);
3783 return -E2BIG;
3784 }
3785
3786 err = is_state_visited(env, insn_idx);
3787 if (err < 0)
3788 return err;
3789 if (err == 1) {
3790 /* found equivalent state, can prune the search */
3594 if (log_level) {
3791 if (env->log.level) {
3595 if (do_print_state)
3792 if (do_print_state)
3596 verbose("\nfrom %d to %d: safe\n",
3793 verbose(env, "\nfrom %d to %d: safe\n",
3597 prev_insn_idx, insn_idx);
3598 else
3794 prev_insn_idx, insn_idx);
3795 else
3599 verbose("%d: safe\n", insn_idx);
3796 verbose(env, "%d: safe\n", insn_idx);
3600 }
3601 goto process_bpf_exit;
3602 }
3603
3604 if (need_resched())
3605 cond_resched();
3606
3797 }
3798 goto process_bpf_exit;
3799 }
3800
3801 if (need_resched())
3802 cond_resched();
3803
3607 if (log_level > 1 || (log_level && do_print_state)) {
3608 if (log_level > 1)
3609 verbose("%d:", insn_idx);
3804 if (env->log.level > 1 || (env->log.level && do_print_state)) {
3805 if (env->log.level > 1)
3806 verbose(env, "%d:", insn_idx);
3610 else
3807 else
3611 verbose("\nfrom %d to %d:",
3808 verbose(env, "\nfrom %d to %d:",
3612 prev_insn_idx, insn_idx);
3809 prev_insn_idx, insn_idx);
3613 print_verifier_state(&env->cur_state);
3810 print_verifier_state(env, state);
3614 do_print_state = false;
3615 }
3616
3811 do_print_state = false;
3812 }
3813
3617 if (log_level) {
3618 verbose("%d: ", insn_idx);
3619 print_bpf_insn(env, insn);
3814 if (env->log.level) {
3815 verbose(env, "%d: ", insn_idx);
3816 print_bpf_insn(verbose, env, insn,
3817 env->allow_ptr_leaks);
3620 }
3621
3622 err = ext_analyzer_insn_hook(env, insn_idx, prev_insn_idx);
3623 if (err)
3624 return err;
3625
3818 }
3819
3820 err = ext_analyzer_insn_hook(env, insn_idx, prev_insn_idx);
3821 if (err)
3822 return err;
3823
3824 regs = cur_regs(env);
3626 if (class == BPF_ALU || class == BPF_ALU64) {
3627 err = check_alu_op(env, insn);
3628 if (err)
3629 return err;
3630
3631 } else if (class == BPF_LDX) {
3632 enum bpf_reg_type *prev_src_type, src_reg_type;
3633

--- 33 unchanged lines hidden (view full) ---

3667 *prev_src_type == PTR_TO_CTX)) {
3668 /* ABuser program is trying to use the same insn
3669 * dst_reg = *(u32*) (src_reg + off)
3670 * with different pointer types:
3671 * src_reg == ctx in one branch and
3672 * src_reg == stack|map in some other branch.
3673 * Reject it.
3674 */
3825 if (class == BPF_ALU || class == BPF_ALU64) {
3826 err = check_alu_op(env, insn);
3827 if (err)
3828 return err;
3829
3830 } else if (class == BPF_LDX) {
3831 enum bpf_reg_type *prev_src_type, src_reg_type;
3832

--- 33 unchanged lines hidden (view full) ---

3866 *prev_src_type == PTR_TO_CTX)) {
3867 /* ABuser program is trying to use the same insn
3868 * dst_reg = *(u32*) (src_reg + off)
3869 * with different pointer types:
3870 * src_reg == ctx in one branch and
3871 * src_reg == stack|map in some other branch.
3872 * Reject it.
3873 */
3675 verbose("same insn cannot be used with different pointers\n");
3874 verbose(env, "same insn cannot be used with different pointers\n");
3676 return -EINVAL;
3677 }
3678
3679 } else if (class == BPF_STX) {
3680 enum bpf_reg_type *prev_dst_type, dst_reg_type;
3681
3682 if (BPF_MODE(insn->code) == BPF_XADD) {
3683 err = check_xadd(env, insn_idx, insn);

--- 23 unchanged lines hidden (view full) ---

3707
3708 prev_dst_type = &env->insn_aux_data[insn_idx].ptr_type;
3709
3710 if (*prev_dst_type == NOT_INIT) {
3711 *prev_dst_type = dst_reg_type;
3712 } else if (dst_reg_type != *prev_dst_type &&
3713 (dst_reg_type == PTR_TO_CTX ||
3714 *prev_dst_type == PTR_TO_CTX)) {
3875 return -EINVAL;
3876 }
3877
3878 } else if (class == BPF_STX) {
3879 enum bpf_reg_type *prev_dst_type, dst_reg_type;
3880
3881 if (BPF_MODE(insn->code) == BPF_XADD) {
3882 err = check_xadd(env, insn_idx, insn);

--- 23 unchanged lines hidden (view full) ---

3906
3907 prev_dst_type = &env->insn_aux_data[insn_idx].ptr_type;
3908
3909 if (*prev_dst_type == NOT_INIT) {
3910 *prev_dst_type = dst_reg_type;
3911 } else if (dst_reg_type != *prev_dst_type &&
3912 (dst_reg_type == PTR_TO_CTX ||
3913 *prev_dst_type == PTR_TO_CTX)) {
3715 verbose("same insn cannot be used with different pointers\n");
3914 verbose(env, "same insn cannot be used with different pointers\n");
3716 return -EINVAL;
3717 }
3718
3719 } else if (class == BPF_ST) {
3720 if (BPF_MODE(insn->code) != BPF_MEM ||
3721 insn->src_reg != BPF_REG_0) {
3915 return -EINVAL;
3916 }
3917
3918 } else if (class == BPF_ST) {
3919 if (BPF_MODE(insn->code) != BPF_MEM ||
3920 insn->src_reg != BPF_REG_0) {
3722 verbose("BPF_ST uses reserved fields\n");
3921 verbose(env, "BPF_ST uses reserved fields\n");
3723 return -EINVAL;
3724 }
3725 /* check src operand */
3726 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
3727 if (err)
3728 return err;
3729
3730 /* check that memory (dst_reg + off) is writeable */

--- 6 unchanged lines hidden (view full) ---

3737 } else if (class == BPF_JMP) {
3738 u8 opcode = BPF_OP(insn->code);
3739
3740 if (opcode == BPF_CALL) {
3741 if (BPF_SRC(insn->code) != BPF_K ||
3742 insn->off != 0 ||
3743 insn->src_reg != BPF_REG_0 ||
3744 insn->dst_reg != BPF_REG_0) {
3922 return -EINVAL;
3923 }
3924 /* check src operand */
3925 err = check_reg_arg(env, insn->dst_reg, SRC_OP);
3926 if (err)
3927 return err;
3928
3929 /* check that memory (dst_reg + off) is writeable */

--- 6 unchanged lines hidden (view full) ---

3936 } else if (class == BPF_JMP) {
3937 u8 opcode = BPF_OP(insn->code);
3938
3939 if (opcode == BPF_CALL) {
3940 if (BPF_SRC(insn->code) != BPF_K ||
3941 insn->off != 0 ||
3942 insn->src_reg != BPF_REG_0 ||
3943 insn->dst_reg != BPF_REG_0) {
3745 verbose("BPF_CALL uses reserved fields\n");
3944 verbose(env, "BPF_CALL uses reserved fields\n");
3746 return -EINVAL;
3747 }
3748
3749 err = check_call(env, insn->imm, insn_idx);
3750 if (err)
3751 return err;
3752
3753 } else if (opcode == BPF_JA) {
3754 if (BPF_SRC(insn->code) != BPF_K ||
3755 insn->imm != 0 ||
3756 insn->src_reg != BPF_REG_0 ||
3757 insn->dst_reg != BPF_REG_0) {
3945 return -EINVAL;
3946 }
3947
3948 err = check_call(env, insn->imm, insn_idx);
3949 if (err)
3950 return err;
3951
3952 } else if (opcode == BPF_JA) {
3953 if (BPF_SRC(insn->code) != BPF_K ||
3954 insn->imm != 0 ||
3955 insn->src_reg != BPF_REG_0 ||
3956 insn->dst_reg != BPF_REG_0) {
3758 verbose("BPF_JA uses reserved fields\n");
3957 verbose(env, "BPF_JA uses reserved fields\n");
3759 return -EINVAL;
3760 }
3761
3762 insn_idx += insn->off + 1;
3763 continue;
3764
3765 } else if (opcode == BPF_EXIT) {
3766 if (BPF_SRC(insn->code) != BPF_K ||
3767 insn->imm != 0 ||
3768 insn->src_reg != BPF_REG_0 ||
3769 insn->dst_reg != BPF_REG_0) {
3958 return -EINVAL;
3959 }
3960
3961 insn_idx += insn->off + 1;
3962 continue;
3963
3964 } else if (opcode == BPF_EXIT) {
3965 if (BPF_SRC(insn->code) != BPF_K ||
3966 insn->imm != 0 ||
3967 insn->src_reg != BPF_REG_0 ||
3968 insn->dst_reg != BPF_REG_0) {
3770 verbose("BPF_EXIT uses reserved fields\n");
3969 verbose(env, "BPF_EXIT uses reserved fields\n");
3771 return -EINVAL;
3772 }
3773
3774 /* eBPF calling convetion is such that R0 is used
3775 * to return the value from eBPF program.
3776 * Make sure that it's readable at this time
3777 * of bpf_exit, which means that program wrote
3778 * something into it earlier
3779 */
3780 err = check_reg_arg(env, BPF_REG_0, SRC_OP);
3781 if (err)
3782 return err;
3783
3784 if (is_pointer_value(env, BPF_REG_0)) {
3970 return -EINVAL;
3971 }
3972
3973 /* eBPF calling convetion is such that R0 is used
3974 * to return the value from eBPF program.
3975 * Make sure that it's readable at this time
3976 * of bpf_exit, which means that program wrote
3977 * something into it earlier
3978 */
3979 err = check_reg_arg(env, BPF_REG_0, SRC_OP);
3980 if (err)
3981 return err;
3982
3983 if (is_pointer_value(env, BPF_REG_0)) {
3785 verbose("R0 leaks addr as return value\n");
3984 verbose(env, "R0 leaks addr as return value\n");
3786 return -EACCES;
3787 }
3788
3985 return -EACCES;
3986 }
3987
3988 err = check_return_code(env);
3989 if (err)
3990 return err;
3789process_bpf_exit:
3991process_bpf_exit:
3790 insn_idx = pop_stack(env, &prev_insn_idx);
3791 if (insn_idx < 0) {
3992 err = pop_stack(env, &prev_insn_idx, &insn_idx);
3993 if (err < 0) {
3994 if (err != -ENOENT)
3995 return err;
3792 break;
3793 } else {
3794 do_print_state = true;
3795 continue;
3796 }
3797 } else {
3798 err = check_cond_jmp_op(env, insn, &insn_idx);
3799 if (err)

--- 9 unchanged lines hidden (view full) ---

3809
3810 } else if (mode == BPF_IMM) {
3811 err = check_ld_imm(env, insn);
3812 if (err)
3813 return err;
3814
3815 insn_idx++;
3816 } else {
3996 break;
3997 } else {
3998 do_print_state = true;
3999 continue;
4000 }
4001 } else {
4002 err = check_cond_jmp_op(env, insn, &insn_idx);
4003 if (err)

--- 9 unchanged lines hidden (view full) ---

4013
4014 } else if (mode == BPF_IMM) {
4015 err = check_ld_imm(env, insn);
4016 if (err)
4017 return err;
4018
4019 insn_idx++;
4020 } else {
3817 verbose("invalid BPF_LD mode\n");
4021 verbose(env, "invalid BPF_LD mode\n");
3818 return -EINVAL;
3819 }
3820 } else {
4022 return -EINVAL;
4023 }
4024 } else {
3821 verbose("unknown insn class %d\n", class);
4025 verbose(env, "unknown insn class %d\n", class);
3822 return -EINVAL;
3823 }
3824
3825 insn_idx++;
3826 }
3827
4026 return -EINVAL;
4027 }
4028
4029 insn_idx++;
4030 }
4031
3828 verbose("processed %d insns, stack depth %d\n",
3829 insn_processed, env->prog->aux->stack_depth);
4032 verbose(env, "processed %d insns, stack depth %d\n", insn_processed,
4033 env->prog->aux->stack_depth);
3830 return 0;
3831}
3832
3833static int check_map_prealloc(struct bpf_map *map)
3834{
3835 return (map->map_type != BPF_MAP_TYPE_HASH &&
3836 map->map_type != BPF_MAP_TYPE_PERCPU_HASH &&
3837 map->map_type != BPF_MAP_TYPE_HASH_OF_MAPS) ||
3838 !(map->map_flags & BPF_F_NO_PREALLOC);
3839}
3840
4034 return 0;
4035}
4036
4037static int check_map_prealloc(struct bpf_map *map)
4038{
4039 return (map->map_type != BPF_MAP_TYPE_HASH &&
4040 map->map_type != BPF_MAP_TYPE_PERCPU_HASH &&
4041 map->map_type != BPF_MAP_TYPE_HASH_OF_MAPS) ||
4042 !(map->map_flags & BPF_F_NO_PREALLOC);
4043}
4044
3841static int check_map_prog_compatibility(struct bpf_map *map,
4045static int check_map_prog_compatibility(struct bpf_verifier_env *env,
4046 struct bpf_map *map,
3842 struct bpf_prog *prog)
3843
3844{
3845 /* Make sure that BPF_PROG_TYPE_PERF_EVENT programs only use
3846 * preallocated hash maps, since doing memory allocation
3847 * in overflow_handler can crash depending on where nmi got
3848 * triggered.
3849 */
3850 if (prog->type == BPF_PROG_TYPE_PERF_EVENT) {
3851 if (!check_map_prealloc(map)) {
4047 struct bpf_prog *prog)
4048
4049{
4050 /* Make sure that BPF_PROG_TYPE_PERF_EVENT programs only use
4051 * preallocated hash maps, since doing memory allocation
4052 * in overflow_handler can crash depending on where nmi got
4053 * triggered.
4054 */
4055 if (prog->type == BPF_PROG_TYPE_PERF_EVENT) {
4056 if (!check_map_prealloc(map)) {
3852 verbose("perf_event programs can only use preallocated hash map\n");
4057 verbose(env, "perf_event programs can only use preallocated hash map\n");
3853 return -EINVAL;
3854 }
3855 if (map->inner_map_meta &&
3856 !check_map_prealloc(map->inner_map_meta)) {
4058 return -EINVAL;
4059 }
4060 if (map->inner_map_meta &&
4061 !check_map_prealloc(map->inner_map_meta)) {
3857 verbose("perf_event programs can only use preallocated inner hash map\n");
4062 verbose(env, "perf_event programs can only use preallocated inner hash map\n");
3858 return -EINVAL;
3859 }
3860 }
3861 return 0;
3862}
3863
3864/* look for pseudo eBPF instructions that access map FDs and
3865 * replace them with actual map pointers

--- 6 unchanged lines hidden (view full) ---

3872
3873 err = bpf_prog_calc_tag(env->prog);
3874 if (err)
3875 return err;
3876
3877 for (i = 0; i < insn_cnt; i++, insn++) {
3878 if (BPF_CLASS(insn->code) == BPF_LDX &&
3879 (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0)) {
4063 return -EINVAL;
4064 }
4065 }
4066 return 0;
4067}
4068
4069/* look for pseudo eBPF instructions that access map FDs and
4070 * replace them with actual map pointers

--- 6 unchanged lines hidden (view full) ---

4077
4078 err = bpf_prog_calc_tag(env->prog);
4079 if (err)
4080 return err;
4081
4082 for (i = 0; i < insn_cnt; i++, insn++) {
4083 if (BPF_CLASS(insn->code) == BPF_LDX &&
4084 (BPF_MODE(insn->code) != BPF_MEM || insn->imm != 0)) {
3880 verbose("BPF_LDX uses reserved fields\n");
4085 verbose(env, "BPF_LDX uses reserved fields\n");
3881 return -EINVAL;
3882 }
3883
3884 if (BPF_CLASS(insn->code) == BPF_STX &&
3885 ((BPF_MODE(insn->code) != BPF_MEM &&
3886 BPF_MODE(insn->code) != BPF_XADD) || insn->imm != 0)) {
4086 return -EINVAL;
4087 }
4088
4089 if (BPF_CLASS(insn->code) == BPF_STX &&
4090 ((BPF_MODE(insn->code) != BPF_MEM &&
4091 BPF_MODE(insn->code) != BPF_XADD) || insn->imm != 0)) {
3887 verbose("BPF_STX uses reserved fields\n");
4092 verbose(env, "BPF_STX uses reserved fields\n");
3888 return -EINVAL;
3889 }
3890
3891 if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {
3892 struct bpf_map *map;
3893 struct fd f;
3894
3895 if (i == insn_cnt - 1 || insn[1].code != 0 ||
3896 insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
3897 insn[1].off != 0) {
4093 return -EINVAL;
4094 }
4095
4096 if (insn[0].code == (BPF_LD | BPF_IMM | BPF_DW)) {
4097 struct bpf_map *map;
4098 struct fd f;
4099
4100 if (i == insn_cnt - 1 || insn[1].code != 0 ||
4101 insn[1].dst_reg != 0 || insn[1].src_reg != 0 ||
4102 insn[1].off != 0) {
3898 verbose("invalid bpf_ld_imm64 insn\n");
4103 verbose(env, "invalid bpf_ld_imm64 insn\n");
3899 return -EINVAL;
3900 }
3901
3902 if (insn->src_reg == 0)
3903 /* valid generic load 64-bit imm */
3904 goto next_insn;
3905
3906 if (insn->src_reg != BPF_PSEUDO_MAP_FD) {
4104 return -EINVAL;
4105 }
4106
4107 if (insn->src_reg == 0)
4108 /* valid generic load 64-bit imm */
4109 goto next_insn;
4110
4111 if (insn->src_reg != BPF_PSEUDO_MAP_FD) {
3907 verbose("unrecognized bpf_ld_imm64 insn\n");
4112 verbose(env,
4113 "unrecognized bpf_ld_imm64 insn\n");
3908 return -EINVAL;
3909 }
3910
3911 f = fdget(insn->imm);
3912 map = __bpf_map_get(f);
3913 if (IS_ERR(map)) {
4114 return -EINVAL;
4115 }
4116
4117 f = fdget(insn->imm);
4118 map = __bpf_map_get(f);
4119 if (IS_ERR(map)) {
3914 verbose("fd %d is not pointing to valid bpf_map\n",
4120 verbose(env, "fd %d is not pointing to valid bpf_map\n",
3915 insn->imm);
3916 return PTR_ERR(map);
3917 }
3918
4121 insn->imm);
4122 return PTR_ERR(map);
4123 }
4124
3919 err = check_map_prog_compatibility(map, env->prog);
4125 err = check_map_prog_compatibility(env, map, env->prog);
3920 if (err) {
3921 fdput(f);
3922 return err;
3923 }
3924
3925 /* store map pointer inside BPF_LD_IMM64 instruction */
3926 insn[0].imm = (u32) (unsigned long) map;
3927 insn[1].imm = ((u64) (unsigned long) map) >> 32;

--- 92 unchanged lines hidden (view full) ---

4020 return new_prog;
4021}
4022
4023/* convert load instructions that access fields of 'struct __sk_buff'
4024 * into sequence of instructions that access fields of 'struct sk_buff'
4025 */
4026static int convert_ctx_accesses(struct bpf_verifier_env *env)
4027{
4126 if (err) {
4127 fdput(f);
4128 return err;
4129 }
4130
4131 /* store map pointer inside BPF_LD_IMM64 instruction */
4132 insn[0].imm = (u32) (unsigned long) map;
4133 insn[1].imm = ((u64) (unsigned long) map) >> 32;

--- 92 unchanged lines hidden (view full) ---

4226 return new_prog;
4227}
4228
4229/* convert load instructions that access fields of 'struct __sk_buff'
4230 * into sequence of instructions that access fields of 'struct sk_buff'
4231 */
4232static int convert_ctx_accesses(struct bpf_verifier_env *env)
4233{
4028 const struct bpf_verifier_ops *ops = env->prog->aux->ops;
4234 const struct bpf_verifier_ops *ops = env->ops;
4029 int i, cnt, size, ctx_field_size, delta = 0;
4030 const int insn_cnt = env->prog->len;
4031 struct bpf_insn insn_buf[16], *insn;
4032 struct bpf_prog *new_prog;
4033 enum bpf_access_type type;
4034 bool is_narrower_load;
4035 u32 target_size;
4036
4037 if (ops->gen_prologue) {
4038 cnt = ops->gen_prologue(insn_buf, env->seen_direct_write,
4039 env->prog);
4040 if (cnt >= ARRAY_SIZE(insn_buf)) {
4235 int i, cnt, size, ctx_field_size, delta = 0;
4236 const int insn_cnt = env->prog->len;
4237 struct bpf_insn insn_buf[16], *insn;
4238 struct bpf_prog *new_prog;
4239 enum bpf_access_type type;
4240 bool is_narrower_load;
4241 u32 target_size;
4242
4243 if (ops->gen_prologue) {
4244 cnt = ops->gen_prologue(insn_buf, env->seen_direct_write,
4245 env->prog);
4246 if (cnt >= ARRAY_SIZE(insn_buf)) {
4041 verbose("bpf verifier is misconfigured\n");
4247 verbose(env, "bpf verifier is misconfigured\n");
4042 return -EINVAL;
4043 } else if (cnt) {
4044 new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
4045 if (!new_prog)
4046 return -ENOMEM;
4047
4048 env->prog = new_prog;
4049 delta += cnt - 1;

--- 31 unchanged lines hidden (view full) ---

4081 * we will apply proper mask to the result.
4082 */
4083 is_narrower_load = size < ctx_field_size;
4084 if (is_narrower_load) {
4085 u32 off = insn->off;
4086 u8 size_code;
4087
4088 if (type == BPF_WRITE) {
4248 return -EINVAL;
4249 } else if (cnt) {
4250 new_prog = bpf_patch_insn_data(env, 0, insn_buf, cnt);
4251 if (!new_prog)
4252 return -ENOMEM;
4253
4254 env->prog = new_prog;
4255 delta += cnt - 1;

--- 31 unchanged lines hidden (view full) ---

4287 * we will apply proper mask to the result.
4288 */
4289 is_narrower_load = size < ctx_field_size;
4290 if (is_narrower_load) {
4291 u32 off = insn->off;
4292 u8 size_code;
4293
4294 if (type == BPF_WRITE) {
4089 verbose("bpf verifier narrow ctx access misconfigured\n");
4295 verbose(env, "bpf verifier narrow ctx access misconfigured\n");
4090 return -EINVAL;
4091 }
4092
4093 size_code = BPF_H;
4094 if (ctx_field_size == 4)
4095 size_code = BPF_W;
4096 else if (ctx_field_size == 8)
4097 size_code = BPF_DW;
4098
4099 insn->off = off & ~(ctx_field_size - 1);
4100 insn->code = BPF_LDX | BPF_MEM | size_code;
4101 }
4102
4103 target_size = 0;
4104 cnt = ops->convert_ctx_access(type, insn, insn_buf, env->prog,
4105 &target_size);
4106 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf) ||
4107 (ctx_field_size && !target_size)) {
4296 return -EINVAL;
4297 }
4298
4299 size_code = BPF_H;
4300 if (ctx_field_size == 4)
4301 size_code = BPF_W;
4302 else if (ctx_field_size == 8)
4303 size_code = BPF_DW;
4304
4305 insn->off = off & ~(ctx_field_size - 1);
4306 insn->code = BPF_LDX | BPF_MEM | size_code;
4307 }
4308
4309 target_size = 0;
4310 cnt = ops->convert_ctx_access(type, insn, insn_buf, env->prog,
4311 &target_size);
4312 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf) ||
4313 (ctx_field_size && !target_size)) {
4108 verbose("bpf verifier is misconfigured\n");
4314 verbose(env, "bpf verifier is misconfigured\n");
4109 return -EINVAL;
4110 }
4111
4112 if (is_narrower_load && size < target_size) {
4113 if (ctx_field_size <= 4)
4114 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg,
4115 (1 << size * 8) - 1);
4116 else

--- 65 unchanged lines hidden (view full) ---

4182 insn->imm == BPF_FUNC_map_lookup_elem) {
4183 map_ptr = env->insn_aux_data[i + delta].map_ptr;
4184 if (map_ptr == BPF_MAP_PTR_POISON ||
4185 !map_ptr->ops->map_gen_lookup)
4186 goto patch_call_imm;
4187
4188 cnt = map_ptr->ops->map_gen_lookup(map_ptr, insn_buf);
4189 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) {
4315 return -EINVAL;
4316 }
4317
4318 if (is_narrower_load && size < target_size) {
4319 if (ctx_field_size <= 4)
4320 insn_buf[cnt++] = BPF_ALU32_IMM(BPF_AND, insn->dst_reg,
4321 (1 << size * 8) - 1);
4322 else

--- 65 unchanged lines hidden (view full) ---

4388 insn->imm == BPF_FUNC_map_lookup_elem) {
4389 map_ptr = env->insn_aux_data[i + delta].map_ptr;
4390 if (map_ptr == BPF_MAP_PTR_POISON ||
4391 !map_ptr->ops->map_gen_lookup)
4392 goto patch_call_imm;
4393
4394 cnt = map_ptr->ops->map_gen_lookup(map_ptr, insn_buf);
4395 if (cnt == 0 || cnt >= ARRAY_SIZE(insn_buf)) {
4190 verbose("bpf verifier is misconfigured\n");
4396 verbose(env, "bpf verifier is misconfigured\n");
4191 return -EINVAL;
4192 }
4193
4194 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf,
4195 cnt);
4196 if (!new_prog)
4197 return -ENOMEM;
4198

--- 22 unchanged lines hidden (view full) ---

4221 if (!new_prog)
4222 return -ENOMEM;
4223
4224 delta += cnt - 1;
4225 env->prog = prog = new_prog;
4226 insn = new_prog->insnsi + i + delta;
4227 }
4228patch_call_imm:
4397 return -EINVAL;
4398 }
4399
4400 new_prog = bpf_patch_insn_data(env, i + delta, insn_buf,
4401 cnt);
4402 if (!new_prog)
4403 return -ENOMEM;
4404

--- 22 unchanged lines hidden (view full) ---

4427 if (!new_prog)
4428 return -ENOMEM;
4429
4430 delta += cnt - 1;
4431 env->prog = prog = new_prog;
4432 insn = new_prog->insnsi + i + delta;
4433 }
4434patch_call_imm:
4229 fn = prog->aux->ops->get_func_proto(insn->imm);
4435 fn = env->ops->get_func_proto(insn->imm);
4230 /* all functions that have prototype and verifier allowed
4231 * programs to call them, must be real in-kernel functions
4232 */
4233 if (!fn->func) {
4436 /* all functions that have prototype and verifier allowed
4437 * programs to call them, must be real in-kernel functions
4438 */
4439 if (!fn->func) {
4234 verbose("kernel subsystem misconfigured func %s#%d\n",
4440 verbose(env,
4441 "kernel subsystem misconfigured func %s#%d\n",
4235 func_id_name(insn->imm), insn->imm);
4236 return -EFAULT;
4237 }
4238 insn->imm = fn->func - __bpf_call_base;
4239 }
4240
4241 return 0;
4242}

--- 7 unchanged lines hidden (view full) ---

4250 return;
4251
4252 for (i = 0; i < env->prog->len; i++) {
4253 sl = env->explored_states[i];
4254
4255 if (sl)
4256 while (sl != STATE_LIST_MARK) {
4257 sln = sl->next;
4442 func_id_name(insn->imm), insn->imm);
4443 return -EFAULT;
4444 }
4445 insn->imm = fn->func - __bpf_call_base;
4446 }
4447
4448 return 0;
4449}

--- 7 unchanged lines hidden (view full) ---

4457 return;
4458
4459 for (i = 0; i < env->prog->len; i++) {
4460 sl = env->explored_states[i];
4461
4462 if (sl)
4463 while (sl != STATE_LIST_MARK) {
4464 sln = sl->next;
4465 free_verifier_state(&sl->state, false);
4258 kfree(sl);
4259 sl = sln;
4260 }
4261 }
4262
4263 kfree(env->explored_states);
4264}
4265
4266int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
4267{
4466 kfree(sl);
4467 sl = sln;
4468 }
4469 }
4470
4471 kfree(env->explored_states);
4472}
4473
4474int bpf_check(struct bpf_prog **prog, union bpf_attr *attr)
4475{
4268 char __user *log_ubuf = NULL;
4269 struct bpf_verifier_env *env;
4476 struct bpf_verifier_env *env;
4477 struct bpf_verifer_log *log;
4270 int ret = -EINVAL;
4271
4478 int ret = -EINVAL;
4479
4480 /* no program is valid */
4481 if (ARRAY_SIZE(bpf_verifier_ops) == 0)
4482 return -EINVAL;
4483
4272 /* 'struct bpf_verifier_env' can be global, but since it's not small,
4273 * allocate/free it every time bpf_check() is called
4274 */
4275 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL);
4276 if (!env)
4277 return -ENOMEM;
4484 /* 'struct bpf_verifier_env' can be global, but since it's not small,
4485 * allocate/free it every time bpf_check() is called
4486 */
4487 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL);
4488 if (!env)
4489 return -ENOMEM;
4490 log = &env->log;
4278
4279 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) *
4280 (*prog)->len);
4281 ret = -ENOMEM;
4282 if (!env->insn_aux_data)
4283 goto err_free_env;
4284 env->prog = *prog;
4491
4492 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) *
4493 (*prog)->len);
4494 ret = -ENOMEM;
4495 if (!env->insn_aux_data)
4496 goto err_free_env;
4497 env->prog = *prog;
4498 env->ops = bpf_verifier_ops[env->prog->type];
4285
4286 /* grab the mutex to protect few globals used by verifier */
4287 mutex_lock(&bpf_verifier_lock);
4288
4289 if (attr->log_level || attr->log_buf || attr->log_size) {
4290 /* user requested verbose verifier output
4291 * and supplied buffer to store the verification trace
4292 */
4499
4500 /* grab the mutex to protect few globals used by verifier */
4501 mutex_lock(&bpf_verifier_lock);
4502
4503 if (attr->log_level || attr->log_buf || attr->log_size) {
4504 /* user requested verbose verifier output
4505 * and supplied buffer to store the verification trace
4506 */
4293 log_level = attr->log_level;
4294 log_ubuf = (char __user *) (unsigned long) attr->log_buf;
4295 log_size = attr->log_size;
4296 log_len = 0;
4507 log->level = attr->log_level;
4508 log->ubuf = (char __user *) (unsigned long) attr->log_buf;
4509 log->len_total = attr->log_size;
4297
4298 ret = -EINVAL;
4510
4511 ret = -EINVAL;
4299 /* log_* values have to be sane */
4300 if (log_size < 128 || log_size > UINT_MAX >> 8 ||
4301 log_level == 0 || log_ubuf == NULL)
4512 /* log attributes have to be sane */
4513 if (log->len_total < 128 || log->len_total > UINT_MAX >> 8 ||
4514 !log->level || !log->ubuf)
4302 goto err_unlock;
4515 goto err_unlock;
4303
4304 ret = -ENOMEM;
4305 log_buf = vmalloc(log_size);
4306 if (!log_buf)
4307 goto err_unlock;
4308 } else {
4309 log_level = 0;
4310 }
4311
4312 env->strict_alignment = !!(attr->prog_flags & BPF_F_STRICT_ALIGNMENT);
4313 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
4314 env->strict_alignment = true;
4315
4516 }
4517
4518 env->strict_alignment = !!(attr->prog_flags & BPF_F_STRICT_ALIGNMENT);
4519 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
4520 env->strict_alignment = true;
4521
4522 if (env->prog->aux->offload) {
4523 ret = bpf_prog_offload_verifier_prep(env);
4524 if (ret)
4525 goto err_unlock;
4526 }
4527
4316 ret = replace_map_fd_with_map_ptr(env);
4317 if (ret < 0)
4318 goto skip_full_check;
4319
4320 env->explored_states = kcalloc(env->prog->len,
4321 sizeof(struct bpf_verifier_state_list *),
4322 GFP_USER);
4323 ret = -ENOMEM;
4324 if (!env->explored_states)
4325 goto skip_full_check;
4326
4327 ret = check_cfg(env);
4328 if (ret < 0)
4329 goto skip_full_check;
4330
4331 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
4332
4333 ret = do_check(env);
4528 ret = replace_map_fd_with_map_ptr(env);
4529 if (ret < 0)
4530 goto skip_full_check;
4531
4532 env->explored_states = kcalloc(env->prog->len,
4533 sizeof(struct bpf_verifier_state_list *),
4534 GFP_USER);
4535 ret = -ENOMEM;
4536 if (!env->explored_states)
4537 goto skip_full_check;
4538
4539 ret = check_cfg(env);
4540 if (ret < 0)
4541 goto skip_full_check;
4542
4543 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
4544
4545 ret = do_check(env);
4546 if (env->cur_state) {
4547 free_verifier_state(env->cur_state, true);
4548 env->cur_state = NULL;
4549 }
4334
4335skip_full_check:
4550
4551skip_full_check:
4336 while (pop_stack(env, NULL) >= 0);
4552 while (!pop_stack(env, NULL, NULL));
4337 free_states(env);
4338
4339 if (ret == 0)
4340 /* program is valid, convert *(u32*)(ctx + off) accesses */
4341 ret = convert_ctx_accesses(env);
4342
4343 if (ret == 0)
4344 ret = fixup_bpf_calls(env);
4345
4553 free_states(env);
4554
4555 if (ret == 0)
4556 /* program is valid, convert *(u32*)(ctx + off) accesses */
4557 ret = convert_ctx_accesses(env);
4558
4559 if (ret == 0)
4560 ret = fixup_bpf_calls(env);
4561
4346 if (log_level && log_len >= log_size - 1) {
4347 BUG_ON(log_len >= log_size);
4348 /* verifier log exceeded user supplied buffer */
4562 if (log->level && bpf_verifier_log_full(log))
4349 ret = -ENOSPC;
4563 ret = -ENOSPC;
4350 /* fall through to return what was recorded */
4351 }
4352
4353 /* copy verifier log back to user space including trailing zero */
4354 if (log_level && copy_to_user(log_ubuf, log_buf, log_len + 1) != 0) {
4564 if (log->level && !log->ubuf) {
4355 ret = -EFAULT;
4565 ret = -EFAULT;
4356 goto free_log_buf;
4566 goto err_release_maps;
4357 }
4358
4359 if (ret == 0 && env->used_map_cnt) {
4360 /* if program passed verifier, update used_maps in bpf_prog_info */
4361 env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt,
4362 sizeof(env->used_maps[0]),
4363 GFP_KERNEL);
4364
4365 if (!env->prog->aux->used_maps) {
4366 ret = -ENOMEM;
4567 }
4568
4569 if (ret == 0 && env->used_map_cnt) {
4570 /* if program passed verifier, update used_maps in bpf_prog_info */
4571 env->prog->aux->used_maps = kmalloc_array(env->used_map_cnt,
4572 sizeof(env->used_maps[0]),
4573 GFP_KERNEL);
4574
4575 if (!env->prog->aux->used_maps) {
4576 ret = -ENOMEM;
4367 goto free_log_buf;
4577 goto err_release_maps;
4368 }
4369
4370 memcpy(env->prog->aux->used_maps, env->used_maps,
4371 sizeof(env->used_maps[0]) * env->used_map_cnt);
4372 env->prog->aux->used_map_cnt = env->used_map_cnt;
4373
4374 /* program is valid. Convert pseudo bpf_ld_imm64 into generic
4375 * bpf_ld_imm64 instructions
4376 */
4377 convert_pseudo_ld_imm64(env);
4378 }
4379
4578 }
4579
4580 memcpy(env->prog->aux->used_maps, env->used_maps,
4581 sizeof(env->used_maps[0]) * env->used_map_cnt);
4582 env->prog->aux->used_map_cnt = env->used_map_cnt;
4583
4584 /* program is valid. Convert pseudo bpf_ld_imm64 into generic
4585 * bpf_ld_imm64 instructions
4586 */
4587 convert_pseudo_ld_imm64(env);
4588 }
4589
4380free_log_buf:
4381 if (log_level)
4382 vfree(log_buf);
4590err_release_maps:
4383 if (!env->prog->aux->used_maps)
4384 /* if we didn't copy map pointers into bpf_prog_info, release
4385 * them now. Otherwise free_bpf_prog_info() will release them.
4386 */
4387 release_maps(env);
4388 *prog = env->prog;
4389err_unlock:
4390 mutex_unlock(&bpf_verifier_lock);
4391 vfree(env->insn_aux_data);
4392err_free_env:
4393 kfree(env);
4394 return ret;
4395}
4396
4591 if (!env->prog->aux->used_maps)
4592 /* if we didn't copy map pointers into bpf_prog_info, release
4593 * them now. Otherwise free_bpf_prog_info() will release them.
4594 */
4595 release_maps(env);
4596 *prog = env->prog;
4597err_unlock:
4598 mutex_unlock(&bpf_verifier_lock);
4599 vfree(env->insn_aux_data);
4600err_free_env:
4601 kfree(env);
4602 return ret;
4603}
4604
4605static const struct bpf_verifier_ops * const bpf_analyzer_ops[] = {
4606#ifdef CONFIG_NET
4607 [BPF_PROG_TYPE_XDP] = &xdp_analyzer_ops,
4608 [BPF_PROG_TYPE_SCHED_CLS] = &tc_cls_act_analyzer_ops,
4609#endif
4610};
4611
4397int bpf_analyzer(struct bpf_prog *prog, const struct bpf_ext_analyzer_ops *ops,
4398 void *priv)
4399{
4400 struct bpf_verifier_env *env;
4401 int ret;
4402
4612int bpf_analyzer(struct bpf_prog *prog, const struct bpf_ext_analyzer_ops *ops,
4613 void *priv)
4614{
4615 struct bpf_verifier_env *env;
4616 int ret;
4617
4618 if (prog->type >= ARRAY_SIZE(bpf_analyzer_ops) ||
4619 !bpf_analyzer_ops[prog->type])
4620 return -EOPNOTSUPP;
4621
4403 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL);
4404 if (!env)
4405 return -ENOMEM;
4406
4407 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) *
4408 prog->len);
4409 ret = -ENOMEM;
4410 if (!env->insn_aux_data)
4411 goto err_free_env;
4412 env->prog = prog;
4622 env = kzalloc(sizeof(struct bpf_verifier_env), GFP_KERNEL);
4623 if (!env)
4624 return -ENOMEM;
4625
4626 env->insn_aux_data = vzalloc(sizeof(struct bpf_insn_aux_data) *
4627 prog->len);
4628 ret = -ENOMEM;
4629 if (!env->insn_aux_data)
4630 goto err_free_env;
4631 env->prog = prog;
4632 env->ops = bpf_analyzer_ops[env->prog->type];
4413 env->analyzer_ops = ops;
4414 env->analyzer_priv = priv;
4415
4416 /* grab the mutex to protect few globals used by verifier */
4417 mutex_lock(&bpf_verifier_lock);
4418
4633 env->analyzer_ops = ops;
4634 env->analyzer_priv = priv;
4635
4636 /* grab the mutex to protect few globals used by verifier */
4637 mutex_lock(&bpf_verifier_lock);
4638
4419 log_level = 0;
4420
4421 env->strict_alignment = false;
4422 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
4423 env->strict_alignment = true;
4424
4425 env->explored_states = kcalloc(env->prog->len,
4426 sizeof(struct bpf_verifier_state_list *),
4427 GFP_KERNEL);
4428 ret = -ENOMEM;
4429 if (!env->explored_states)
4430 goto skip_full_check;
4431
4432 ret = check_cfg(env);
4433 if (ret < 0)
4434 goto skip_full_check;
4435
4436 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
4437
4438 ret = do_check(env);
4639 env->strict_alignment = false;
4640 if (!IS_ENABLED(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS))
4641 env->strict_alignment = true;
4642
4643 env->explored_states = kcalloc(env->prog->len,
4644 sizeof(struct bpf_verifier_state_list *),
4645 GFP_KERNEL);
4646 ret = -ENOMEM;
4647 if (!env->explored_states)
4648 goto skip_full_check;
4649
4650 ret = check_cfg(env);
4651 if (ret < 0)
4652 goto skip_full_check;
4653
4654 env->allow_ptr_leaks = capable(CAP_SYS_ADMIN);
4655
4656 ret = do_check(env);
4657 if (env->cur_state) {
4658 free_verifier_state(env->cur_state, true);
4659 env->cur_state = NULL;
4660 }
4439
4440skip_full_check:
4661
4662skip_full_check:
4441 while (pop_stack(env, NULL) >= 0);
4663 while (!pop_stack(env, NULL, NULL));
4442 free_states(env);
4443
4444 mutex_unlock(&bpf_verifier_lock);
4445 vfree(env->insn_aux_data);
4446err_free_env:
4447 kfree(env);
4448 return ret;
4449}
4450EXPORT_SYMBOL_GPL(bpf_analyzer);
4664 free_states(env);
4665
4666 mutex_unlock(&bpf_verifier_lock);
4667 vfree(env->insn_aux_data);
4668err_free_env:
4669 kfree(env);
4670 return ret;
4671}
4672EXPORT_SYMBOL_GPL(bpf_analyzer);