Re: [PATCH RFC net-next 08/14] bpf: add eBPF verifier

+/* types of values:
+ * - stored in an eBPF register
+ * - passed into helper functions as an argument
+ * - returned from helper functions
+ */
+enum bpf_reg_type {
+	INVALID_PTR,			/* reg doesn't contain a valid pointer */

+	PTR_TO_CTX,			/* reg points to bpf_context */
+	PTR_TO_MAP,			/* reg points to map element value */
+	PTR_TO_MAP_CONDITIONAL,		/* points to map element value or NULL */
+	PTR_TO_STACK,			/* reg == frame_pointer */
+	PTR_TO_STACK_IMM,		/* reg == frame_pointer + imm */
+	PTR_TO_STACK_IMM_MAP_KEY,	/* pointer to stack used as map key */
+	PTR_TO_STACK_IMM_MAP_VALUE,	/* pointer to stack used as map elem */

+	RET_INTEGER,			/* function returns integer */
+	RET_VOID,			/* function returns void */
+	CONST_ARG,			/* function expects integer constant argument */
+	CONST_ARG_MAP_ID,		/* int const argument that is used as map_id */

+	/* int const argument indicating number of bytes accessed from stack
+	 * previous function argument must be ptr_to_stack_imm
+	 */
+	CONST_ARG_STACK_IMM_SIZE,
+};

+
+/* check read/write into map element returned by bpf_table_lookup() */
+static int check_table_access(struct verifier_env *env, int regno, int off,
+			      int size)

+{
+	struct bpf_map *map;
+	int map_id = env->cur_state.regs[regno].imm;
+
+	_(get_map_info(env, map_id, &map));
+
+	if (off < 0 || off + size > map->value_size) {
+		verbose("invalid access to map_id=%d leaf_size=%d off=%d size=%d\n",
+			map_id, map->value_size, off, size);
+		return -EACCES;
+	}
+	return 0;
+}

+static int check_mem_access(struct verifier_env *env, int regno, int off,
+			    int bpf_size, enum bpf_access_type t,
+			    int value_regno)
+{
+	struct verifier_state *state = &env->cur_state;
+	int size;
+
+	_(size = bpf_size_to_bytes(bpf_size));
+
+	if (off % size != 0) {
+		verbose("misaligned access off %d size %d\n", off, size);
+		return -EACCES;
+	}
+
+	if (state->regs[regno].ptr == PTR_TO_MAP) {
+		_(check_table_access(env, regno, off, size));
+		if (t == BPF_READ)
+			mark_reg_no_ptr(state->regs, value_regno);
+	} else if (state->regs[regno].ptr == PTR_TO_CTX) {
+		_(check_ctx_access(env, off, size, t));
+		if (t == BPF_READ)
+			mark_reg_no_ptr(state->regs, value_regno);
+	} else if (state->regs[regno].ptr == PTR_TO_STACK) {
+		if (off >= 0 || off < -MAX_BPF_STACK) {
+			verbose("invalid stack off=%d size=%d\n", off, size);
+			return -EACCES;
+		}

+		if (t == BPF_WRITE)
+			_(check_stack_write(state, off, size, value_regno));
+		else
+			_(check_stack_read(state, off, size, value_regno));
+	} else {
+		verbose("R%d invalid mem access '%s'\n",
+			regno, reg_type_str[state->regs[regno].ptr]);
+		return -EACCES;
+	}
+	return 0;
+}

+static int check_call(struct verifier_env *env, int func_id)
+{
+	struct verifier_state *state = &env->cur_state;
+	const struct bpf_func_proto *fn = NULL;
+	struct reg_state *regs = state->regs;
+	struct bpf_map *map = NULL;
+	struct reg_state *reg;
+	int map_id = -1;
+	int i;
+
+	/* find function prototype */
+	if (func_id <= 0 || func_id >= __BPF_FUNC_MAX_ID) {
+		verbose("invalid func %d\n", func_id);
+		return -EINVAL;
+	}
+
+	if (env->prog->info->ops->get_func_proto)
+		fn = env->prog->info->ops->get_func_proto(func_id);
+
+	if (!fn || (fn->ret_type != RET_INTEGER &&
+		    fn->ret_type != PTR_TO_MAP_CONDITIONAL &&
+		    fn->ret_type != RET_VOID)) {
+		verbose("unknown func %d\n", func_id);
+		return -EINVAL;
+	}
+
+	/* check args */
+	_(check_func_arg(env, BPF_REG_1, fn->arg1_type, &map_id, &map));
+	_(check_func_arg(env, BPF_REG_2, fn->arg2_type, &map_id, &map));
+	_(check_func_arg(env, BPF_REG_3, fn->arg3_type, &map_id, &map));
+	_(check_func_arg(env, BPF_REG_4, fn->arg4_type, &map_id, &map));

+
+	/* reset caller saved regs */
+	for (i = 0; i < CALLER_SAVED_REGS; i++) {
+		reg = regs + caller_saved[i];
+		reg->read_ok = false;
+		reg->ptr = INVALID_PTR;
+		reg->imm = 0xbadbad;
+	}
+
+	/* update return register */
+	reg = regs + BPF_REG_0;
+	if (fn->ret_type == RET_INTEGER) {
+		reg->read_ok = true;
+		reg->ptr = INVALID_PTR;
+	} else if (fn->ret_type != RET_VOID) {
+		reg->read_ok = true;
+		reg->ptr = fn->ret_type;
+		if (fn->ret_type == PTR_TO_MAP_CONDITIONAL)
+			/*
+			 * remember map_id, so that check_table_access()
+			 * can check 'value_size' boundary of memory access
+			 * to map element returned from bpf_table_lookup()
+			 */
+			reg->imm = map_id;
+	}
+	return 0;
+}

+	({ \
+		int _ret; \
+		if (cur_stack == 0) \
+			_ret = -1; \
+		else \
+			_ret = stack[cur_stack - 1]; \
+		_ret; \
+	 })
+
+#define POP_INT() \
+	({ \
+		int _ret; \
+		if (cur_stack == 0) \
+			_ret = -1; \
+		else \
+			_ret = stack[--cur_stack]; \
+		_ret; \
+	 })