Date:   Mon, 14 May 2018 20:04:17 -0700
From:   Alexei Starovoitov <alexei.starovoitov@...il.com>
To:     Joe Stringer <joe@...d.net.nz>
Cc:     daniel@...earbox.net, netdev@...r.kernel.org, ast@...nel.org,
        john.fastabend@...il.com, kafai@...com
Subject: Re: [RFC bpf-next 06/11] bpf: Add reference tracking to verifier

On Wed, May 09, 2018 at 02:07:04PM -0700, Joe Stringer wrote:
> Allow helper functions to acquire a reference and return it into a
> register. Specific pointer types such as the PTR_TO_SOCKET will
> implicitly represent such a reference. The verifier must ensure that
> these references are released exactly once in each path through the
> program.
> 
> To achieve this, this commit assigns an id to the pointer and tracks it
> in the 'bpf_func_state', then when the function or program exits,
> verifies that all of the acquired references have been freed. When the
> pointer is passed to a function that frees the reference, it is removed
> from the 'bpf_func_state` and all existing copies of the pointer in
> registers are marked invalid.
> 
> Signed-off-by: Joe Stringer <joe@...d.net.nz>
> ---
>  include/linux/bpf_verifier.h |  18 ++-
>  kernel/bpf/verifier.c        | 295 ++++++++++++++++++++++++++++++++++++++++---
>  2 files changed, 292 insertions(+), 21 deletions(-)
> 
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 9dcd87f1d322..8dbee360b3ec 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -104,6 +104,11 @@ struct bpf_stack_state {
>  	u8 slot_type[BPF_REG_SIZE];
>  };
>  
> +struct bpf_reference_state {
> +	int id;
> +	int insn_idx; /* allocation insn */

the insn_idx is for more verbose messages, right?
It doesn't seem to affect the safety of algorithm.
Please add a comment to clarify that.

> +};
> +
>  /* state of the program:
>   * type of all registers and stack info
>   */
> @@ -122,7 +127,9 @@ struct bpf_func_state {
>  	 */
>  	u32 subprogno;
>  
> -	/* should be second to last. See copy_func_state() */
> +	/* The following fields should be last. See copy_func_state() */
> +	int acquired_refs;
> +	struct bpf_reference_state *refs;
>  	int allocated_stack;
>  	struct bpf_stack_state *stack;
>  };
> @@ -218,11 +225,16 @@ void bpf_verifier_vlog(struct bpf_verifier_log *log, const char *fmt,
>  __printf(2, 3) void bpf_verifier_log_write(struct bpf_verifier_env *env,
>  					   const char *fmt, ...);
>  
> -static inline struct bpf_reg_state *cur_regs(struct bpf_verifier_env *env)
> +static inline struct bpf_func_state *cur_func(struct bpf_verifier_env *env)
>  {
>  	struct bpf_verifier_state *cur = env->cur_state;
>  
> -	return cur->frame[cur->curframe]->regs;
> +	return cur->frame[cur->curframe];
> +}
> +
> +static inline struct bpf_reg_state *cur_regs(struct bpf_verifier_env *env)
> +{
> +	return cur_func(env)->regs;
>  }
>  
>  int bpf_prog_offload_verifier_prep(struct bpf_verifier_env *env);
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index f426ebf2b6bf..92b9a5dc465a 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1,5 +1,6 @@
>  /* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
>   * Copyright (c) 2016 Facebook
> + * Copyright (c) 2018 Covalent IO, Inc. http://covalent.io
>   *
>   * This program is free software; you can redistribute it and/or
>   * modify it under the terms of version 2 of the GNU General Public
> @@ -140,6 +141,18 @@ static const struct bpf_verifier_ops * const bpf_verifier_ops[] = {
>   *
>   * After the call R0 is set to return type of the function and registers R1-R5
>   * are set to NOT_INIT to indicate that they are no longer readable.
> + *
> + * The following reference types represent a potential reference to a kernel
> + * resource which, after first being allocated, must be checked and freed by
> + * the BPF program:
> + * - PTR_TO_SOCKET_OR_NULL, PTR_TO_SOCKET
> + *
> + * When the verifier sees a helper call return a reference type, it allocates a
> + * pointer id for the reference and stores it in the current function state.
> + * Similar to the way that PTR_TO_MAP_VALUE_OR_NULL is converted into
> + * PTR_TO_MAP_VALUE, PTR_TO_SOCKET_OR_NULL becomes PTR_TO_SOCKET when the type
> + * passes through a NULL-check conditional. For the branch wherein the state is
> + * changed to CONST_IMM, the verifier releases the reference.
>   */
>  
>  /* verifier_state + insn_idx are pushed to stack when branch is encountered */
> @@ -229,7 +242,42 @@ static bool type_is_pkt_pointer(enum bpf_reg_type type)
>  
>  static bool reg_type_may_be_null(enum bpf_reg_type type)
>  {
> -	return type == PTR_TO_MAP_VALUE_OR_NULL;
> +	return type == PTR_TO_MAP_VALUE_OR_NULL ||
> +	       type == PTR_TO_SOCKET_OR_NULL;
> +}
> +
> +static bool type_is_refcounted(enum bpf_reg_type type)
> +{
> +	return type == PTR_TO_SOCKET;
> +}
> +
> +static bool type_is_refcounted_or_null(enum bpf_reg_type type)
> +{
> +	return type == PTR_TO_SOCKET || type == PTR_TO_SOCKET_OR_NULL;
> +}
> +
> +static bool reg_is_refcounted(const struct bpf_reg_state *reg)
> +{
> +	return type_is_refcounted(reg->type);
> +}
> +
> +static bool reg_is_refcounted_or_null(const struct bpf_reg_state *reg)
> +{
> +	return type_is_refcounted_or_null(reg->type);
> +}
> +
> +static bool arg_type_is_refcounted(enum bpf_arg_type type)
> +{
> +	return type == ARG_PTR_TO_SOCKET;
> +}
> +
> +/* Determine whether the function releases some resources allocated by another
> + * function call. The first reference type argument will be assumed to be
> + * released by release_reference().
> + */
> +static bool is_release_function(enum bpf_func_id func_id)
> +{
> +	return false;
>  }
>  
>  /* string representation of 'enum bpf_reg_type' */
> @@ -344,6 +392,12 @@ static void print_verifier_state(struct bpf_verifier_env *env,
>  		if (state->stack[i].slot_type[0] == STACK_ZERO)
>  			verbose(env, " fp%d=0", (-i - 1) * BPF_REG_SIZE);
>  	}
> +	if (state->acquired_refs && state->refs[0].id) {
> +		verbose(env, " refs=%d", state->refs[0].id);
> +		for (i = 1; i < state->acquired_refs; i++)
> +			if (state->refs[i].id)
> +				verbose(env, ",%d", state->refs[i].id);
> +	}
>  	verbose(env, "\n");
>  }
>  
> @@ -362,6 +416,8 @@ static int copy_##NAME##_state(struct bpf_func_state *dst,		\
>  	       sizeof(*src->FIELD) * (src->COUNT / SIZE));		\
>  	return 0;							\
>  }
> +/* copy_reference_state() */
> +COPY_STATE_FN(reference, acquired_refs, refs, 1)
>  /* copy_stack_state() */
>  COPY_STATE_FN(stack, allocated_stack, stack, BPF_REG_SIZE)
>  #undef COPY_STATE_FN
> @@ -400,6 +456,8 @@ static int realloc_##NAME##_state(struct bpf_func_state *state, int size, \
>  	state->FIELD = new_##FIELD;					\
>  	return 0;							\
>  }
> +/* realloc_reference_state() */
> +REALLOC_STATE_FN(reference, acquired_refs, refs, 1)
>  /* realloc_stack_state() */
>  REALLOC_STATE_FN(stack, allocated_stack, stack, BPF_REG_SIZE)
>  #undef REALLOC_STATE_FN
> @@ -411,16 +469,89 @@ REALLOC_STATE_FN(stack, allocated_stack, stack, BPF_REG_SIZE)
>   * which realloc_stack_state() copies over. It points to previous
>   * bpf_verifier_state which is never reallocated.
>   */
> -static int realloc_func_state(struct bpf_func_state *state, int size,
> -			      bool copy_old)
> +static int realloc_func_state(struct bpf_func_state *state, int stack_size,
> +			      int refs_size, bool copy_old)
>  {
> -	return realloc_stack_state(state, size, copy_old);
> +	int err = realloc_reference_state(state, refs_size, copy_old);
> +	if (err)
> +		return err;
> +	return realloc_stack_state(state, stack_size, copy_old);
> +}
> +
> +/* Acquire a pointer id from the env and update the state->refs to include
> + * this new pointer reference.
> + * On success, returns a valid pointer id to associate with the register
> + * On failure, returns a negative errno.
> + */
> +static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx)
> +{
> +	struct bpf_func_state *state = cur_func(env);
> +	int new_ofs = state->acquired_refs;
> +	int id, err;
> +
> +	err = realloc_reference_state(state, state->acquired_refs + 1, true);
> +	if (err)
> +		return err;
> +	id = ++env->id_gen;
> +	state->refs[new_ofs].id = id;
> +	state->refs[new_ofs].insn_idx = insn_idx;

I thought that we may avoid this extra 'ref_state' array if we store
'id' into 'aux' array which is one to one to array of instructions
and avoid this expensive reallocs, but then I realized we can go
through the same instruction that returns a pointer to socket
multiple times and every time it needs to be different 'id' and
tracked indepdently, so yeah. All that infra is necessary.
Would be good to document the algorithm a bit more.

> +
> +	return id;
> +}
> +
> +/* release function corresponding to acquire_reference_state(). Idempotent. */
> +static int __release_reference_state(struct bpf_func_state *state, int ptr_id)
> +{
> +	int i, last_idx;
> +
> +	if (!ptr_id)
> +		return 0;
> +
> +	last_idx = state->acquired_refs - 1;
> +	for (i = 0; i < state->acquired_refs; i++) {
> +		if (state->refs[i].id == ptr_id) {
> +			if (last_idx && i != last_idx)
> +				memcpy(&state->refs[i], &state->refs[last_idx],
> +				       sizeof(*state->refs));
> +			memset(&state->refs[last_idx], 0, sizeof(*state->refs));
> +			state->acquired_refs--;
> +			return 0;
> +		}
> +	}
> +	return -EFAULT;
> +}
> +
> +/* variation on the above for cases where we expect that there must be an
> + * outstanding reference for the specified ptr_id.
> + */
> +static int release_reference_state(struct bpf_verifier_env *env, int ptr_id)
> +{
> +	struct bpf_func_state *state = cur_func(env);
> +	int err;
> +
> +	err = __release_reference_state(state, ptr_id);
> +	if (WARN_ON_ONCE(err != 0))
> +		verbose(env, "verifier internal error: can't release reference\n");
> +	return err;
> +}
> +
> +static int transfer_reference_state(struct bpf_func_state *dst,
> +				    struct bpf_func_state *src)
> +{
> +	int err = realloc_reference_state(dst, src->acquired_refs, false);
> +	if (err)
> +		return err;
> +	err = copy_reference_state(dst, src);
> +	if (err)
> +		return err;
> +	return 0;
>  }
>  
>  static void free_func_state(struct bpf_func_state *state)
>  {
>  	if (!state)
>  		return;
> +	kfree(state->refs);
>  	kfree(state->stack);
>  	kfree(state);
>  }
> @@ -446,10 +577,14 @@ static int copy_func_state(struct bpf_func_state *dst,
>  {
>  	int err;
>  
> -	err = realloc_func_state(dst, src->allocated_stack, false);
> +	err = realloc_func_state(dst, src->allocated_stack, src->acquired_refs,
> +				 false);
> +	if (err)
> +		return err;
> +	memcpy(dst, src, offsetof(struct bpf_func_state, acquired_refs));
> +	err = copy_reference_state(dst, src);
>  	if (err)
>  		return err;
> -	memcpy(dst, src, offsetof(struct bpf_func_state, allocated_stack));
>  	return copy_stack_state(dst, src);
>  }
>  
> @@ -1019,7 +1154,7 @@ static int check_stack_write(struct bpf_verifier_env *env,
>  	enum bpf_reg_type type;
>  
>  	err = realloc_func_state(state, round_up(slot + 1, BPF_REG_SIZE),
> -				 true);
> +				 state->acquired_refs, true);
>  	if (err)
>  		return err;
>  	/* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
> @@ -2259,10 +2394,32 @@ static bool check_arg_pair_ok(const struct bpf_func_proto *fn)
>  	return true;
>  }
>  
> +static bool check_refcount_ok(const struct bpf_func_proto *fn)
> +{
> +	int count = 0;
> +
> +	if (arg_type_is_refcounted(fn->arg1_type))
> +		count++;
> +	if (arg_type_is_refcounted(fn->arg2_type))
> +		count++;
> +	if (arg_type_is_refcounted(fn->arg3_type))
> +		count++;
> +	if (arg_type_is_refcounted(fn->arg4_type))
> +		count++;
> +	if (arg_type_is_refcounted(fn->arg5_type))
> +		count++;
> +
> +	/* We only support one arg being unreferenced at the moment,
> +	 * which is sufficient for the helper functions we have right now.
> +	 */
> +	return count <= 1;
> +}
> +
>  static int check_func_proto(const struct bpf_func_proto *fn)
>  {
>  	return check_raw_mode_ok(fn) &&
> -	       check_arg_pair_ok(fn) ? 0 : -EINVAL;
> +	       check_arg_pair_ok(fn) &&
> +	       check_refcount_ok(fn) ? 0 : -EINVAL;
>  }
>  
>  /* Packet data might have moved, any old PTR_TO_PACKET[_META,_END]
> @@ -2295,12 +2452,57 @@ static void clear_all_pkt_pointers(struct bpf_verifier_env *env)
>  		__clear_all_pkt_pointers(env, vstate->frame[i]);
>  }
>  
> +static void release_reg_references(struct bpf_verifier_env *env,
> +				   struct bpf_func_state *state, int id)
> +{
> +	struct bpf_reg_state *regs = state->regs, *reg;
> +	int i;
> +
> +	for (i = 0; i < MAX_BPF_REG; i++)
> +		if (regs[i].id == id)
> +			mark_reg_unknown(env, regs, i);
> +
> +	for_each_spilled_reg(i, state, reg) {
> +		if (!reg)
> +			continue;
> +		if (reg_is_refcounted(reg) && reg->id == id)
> +			__mark_reg_unknown(reg);
> +	}
> +}
> +
> +/* The pointer with the specified id has released its reference to kernel
> + * resources. Identify all copies of the same pointer and clear the reference.
> + */
> +static int release_reference(struct bpf_verifier_env *env)
> +{
> +	struct bpf_verifier_state *vstate = env->cur_state;
> +	struct bpf_reg_state *regs = cur_regs(env);
> +	int i, ptr_id = 0;
> +
> +	for (i = BPF_REG_1; i < BPF_REG_6; i++) {
> +		if (reg_is_refcounted(&regs[i])) {
> +			ptr_id = regs[i].id;
> +			break;
> +		}
> +	}
> +	if (WARN_ON_ONCE(!ptr_id)) {
> +		/* references must be special pointer types that are checked
> +		 * against argument requirements for the release function. */
> +		verbose(env, "verifier internal error: can't locate refcounted arg\n");
> +		return -EFAULT;
> +	}
> +	for (i = 0; i <= vstate->curframe; i++)
> +		release_reg_references(env, vstate->frame[i], ptr_id);
> +
> +	return release_reference_state(env, ptr_id);
> +}
> +
>  static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
>  			   int *insn_idx)
>  {
>  	struct bpf_verifier_state *state = env->cur_state;
>  	struct bpf_func_state *caller, *callee;
> -	int i, subprog, target_insn;
> +	int i, err, subprog, target_insn;
>  
>  	if (state->curframe + 1 >= MAX_CALL_FRAMES) {
>  		verbose(env, "the call stack of %d frames is too deep\n",
> @@ -2338,6 +2540,11 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
>  			state->curframe + 1 /* frameno within this callchain */,
>  			subprog /* subprog number within this prog */);
>  
> +	/* Transfer references to the callee */
> +	err = transfer_reference_state(callee, caller);
> +	if (err)
> +		return err;
> +
>  	/* copy r1 - r5 args that callee can access */
>  	for (i = BPF_REG_1; i <= BPF_REG_5; i++)
>  		callee->regs[i] = caller->regs[i];
> @@ -2368,6 +2575,7 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
>  	struct bpf_verifier_state *state = env->cur_state;
>  	struct bpf_func_state *caller, *callee;
>  	struct bpf_reg_state *r0;
> +	int err;
>  
>  	callee = state->frame[state->curframe];
>  	r0 = &callee->regs[BPF_REG_0];
> @@ -2387,6 +2595,11 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
>  	/* return to the caller whatever r0 had in the callee */
>  	caller->regs[BPF_REG_0] = *r0;
>  
> +	/* Transfer references to the caller */
> +	err = transfer_reference_state(caller, callee);
> +	if (err)
> +		return err;
> +
>  	*insn_idx = callee->callsite + 1;
>  	if (env->log.level) {
>  		verbose(env, "returning from callee:\n");
> @@ -2498,6 +2711,15 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
>  			return err;
>  	}
>  
> +	/* If the function is a release() function, mark all copies of the same
> +	 * pointer as "freed" in all registers and in the stack.
> +	 */
> +	if (is_release_function(func_id)) {
> +		err = release_reference(env);

I think this can be improved if check_func_arg() stores ptr_id into meta.
Then this loop
 for (i = BPF_REG_1; i < BPF_REG_6; i++) {
       if (reg_is_refcounted(&regs[i])) {
in release_reference() won't be needed.

Also the macros from the previous patch look ugly, but considering this patch
I guess it's justified. At least I don't see a better way of doing it.

Powered by blists - more mailing lists