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