Re: [PATCH bpf-next v2 5/8] bpf: Add bpf_rcu_read_lock() verifier support

[Yonghong Song <yhs@meta.com>]

On 11/8/22 9:04 AM, Kumar Kartikeya Dwivedi wrote:
> On Tue, Nov 08, 2022 at 01:11:14PM IST, Yonghong Song wrote:
>> To simplify the design and support the common practice, no
>> nested bpf_rcu_read_lock() is allowed. During verification,
>> each paired bpf_rcu_read_lock()/unlock() has a unique
>> region id, starting from 1. Each rcu ptr register also
>> remembers the region id when the ptr reg is initialized.
>> The following is a simple example to illustrate the
>> rcu lock regions and usage of rcu ptr's.
>>
>>       ...                    <=== rcu lock region 0
>>       bpf_rcu_read_lock()    <=== rcu lock region 1
>>       rcu_ptr1 = ...         <=== rcu_ptr1 with region 1
>>       ... using rcu_ptr1 ...
>>       bpf_rcu_read_unlock()
>>       ...                    <=== rcu lock region -1
>>       bpf_rcu_read_lock()    <=== rcu lock region 2
>>       rcu_ptr2 = ...         <=== rcu_ptr2 with region 2
>>       ... using rcu_ptr2 ...
>>       ... using rcu_ptr1 ... <=== wrong, region 1 rcu_ptr in region 2
>>       bpf_rcu_read_unlock()
>>
>> Outside the rcu lock region, the rcu lock region id is 0 or negative of
>> previous valid rcu lock region id, so the next valid rcu lock region
>> id can be easily computed.
>>
>> Note that rcu protection is not needed for non-sleepable program. But
>> it is supported to make cross-sleepable/nonsleepable development easier.
>> For non-sleepable program, the following insns can be inside the rcu
>> lock region:
>>    - any non call insns except BPF_ABS/BPF_IND
>>    - non sleepable helpers or kfuncs
>> Also, bpf_*_storage_get() helper's 5th hidden argument (for memory
>> allocation flag) should be GFP_ATOMIC.
>>
>> If a pointer (PTR_TO_BTF_ID) is marked as rcu, then any use of
>> this pointer and the load which gets this pointer needs to be
>> protected by bpf_rcu_read_lock(). The following shows a couple
>> of examples:
>>    struct task_struct {
>>          ...
>>          struct task_struct __rcu        *real_parent;
>>          struct css_set __rcu            *cgroups;
>>          ...
>>    };
>>    struct css_set {
>>          ...
>>          struct cgroup *dfl_cgrp;
>>          ...
>>    }
>>    ...
>>    task = bpf_get_current_task_btf();
>>    cgroups = task->cgroups;
>>    dfl_cgroup = cgroups->dfl_cgrp;
>>    ... using dfl_cgroup ...
>>
>> The bpf_rcu_read_lock/unlock() should be added like below to
>> avoid verification failures.
>>    task = bpf_get_current_task_btf();
>>    bpf_rcu_read_lock();
>>    cgroups = task->cgroups;
>>    dfl_cgroup = cgroups->dfl_cgrp;
>>    bpf_rcu_read_unlock();
>>    ... using dfl_cgroup ...
>>
>> The following is another example for task->real_parent.
>>    task = bpf_get_current_task_btf();
>>    bpf_rcu_read_lock();
>>    real_parent = task->real_parent;
>>    ... bpf_task_storage_get(&map, real_parent, 0, 0);
>>    bpf_rcu_read_unlock();
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>>   include/linux/bpf.h          |  1 +
>>   include/linux/bpf_verifier.h |  7 +++
>>   kernel/bpf/btf.c             | 32 ++++++++++++-
>>   kernel/bpf/verifier.c        | 92 +++++++++++++++++++++++++++++++-----
>>   4 files changed, 120 insertions(+), 12 deletions(-)
>>
>> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
>> index b4bbcafd1c9b..98af0c9ec721 100644
>> --- a/include/linux/bpf.h
>> +++ b/include/linux/bpf.h
>> @@ -761,6 +761,7 @@ struct bpf_prog_ops {
>>   struct btf_struct_access_info {
>>   	u32 next_btf_id;
>>   	enum bpf_type_flag flag;
>> +	bool is_rcu;
>>   };
>>
>>   struct bpf_verifier_ops {
>> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
>> index 1a32baa78ce2..5d703637bb12 100644
>> --- a/include/linux/bpf_verifier.h
>> +++ b/include/linux/bpf_verifier.h
>> @@ -179,6 +179,10 @@ struct bpf_reg_state {
>>   	 */
>>   	s32 subreg_def;
>>   	enum bpf_reg_liveness live;
>> +	/* 0: not rcu ptr; > 0: rcu ptr, id of the rcu read lock region where
>> +	 * the rcu ptr reg is initialized.
>> +	 */
>> +	int active_rcu_lock;
>>   	/* if (!precise && SCALAR_VALUE) min/max/tnum don't affect safety */
>>   	bool precise;
>>   };
>> @@ -324,6 +328,8 @@ struct bpf_verifier_state {
>>   	u32 insn_idx;
>>   	u32 curframe;
>>   	u32 active_spin_lock;
>> +	/* <= 0: not in rcu read lock region; > 0: the rcu lock region id */
>> +	int active_rcu_lock;
>>   	bool speculative;
>>
>>   	/* first and last insn idx of this verifier state */
>> @@ -424,6 +430,7 @@ struct bpf_insn_aux_data {
>>   	u32 seen; /* this insn was processed by the verifier at env->pass_cnt */
>>   	bool sanitize_stack_spill; /* subject to Spectre v4 sanitation */
>>   	bool zext_dst; /* this insn zero extends dst reg */
>> +	bool storage_get_func_atomic; /* bpf_*_storage_get() with atomic memory alloc */
>>   	u8 alu_state; /* used in combination with alu_limit */
>>
>>   	/* below fields are initialized once */
>> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
>> index d2ee1669a2f3..c5a9569f2ae0 100644
>> --- a/kernel/bpf/btf.c
>> +++ b/kernel/bpf/btf.c
>> @@ -5831,6 +5831,7 @@ static int btf_struct_walk(struct bpf_verifier_log *log, const struct btf *btf,
>>   		if (btf_type_is_ptr(mtype)) {
>>   			const struct btf_type *stype, *t;
>>   			enum bpf_type_flag tmp_flag = 0;
>> +			bool is_rcu = false;
>>   			u32 id;
>>
>>   			if (msize != size || off != moff) {
>> @@ -5850,12 +5851,16 @@ static int btf_struct_walk(struct bpf_verifier_log *log, const struct btf *btf,
>>   				/* check __percpu tag */
>>   				if (strcmp(tag_value, "percpu") == 0)
>>   					tmp_flag = MEM_PERCPU;
>> +				/* check __rcu tag */
>> +				if (strcmp(tag_value, "rcu") == 0)
>> +					is_rcu = true;
>>   			}
>>
>>   			stype = btf_type_skip_modifiers(btf, mtype->type, &id);
>>   			if (btf_type_is_struct(stype)) {
>>   				info->next_btf_id = id;
>>   				info->flag = tmp_flag;
>> +				info->is_rcu = is_rcu;
>>   				return WALK_PTR;
>>   			}
>>   		}
>> @@ -6317,7 +6322,7 @@ static int btf_check_func_arg_match(struct bpf_verifier_env *env,
>>   {
>>   	enum bpf_prog_type prog_type = resolve_prog_type(env->prog);
>>   	bool rel = false, kptr_get = false, trusted_args = false;
>> -	bool sleepable = false;
>> +	bool sleepable = false, rcu_lock = false, rcu_unlock = false;
>>   	struct bpf_verifier_log *log = &env->log;
>>   	u32 i, nargs, ref_id, ref_obj_id = 0;
>>   	bool is_kfunc = btf_is_kernel(btf);
>> @@ -6356,6 +6361,31 @@ static int btf_check_func_arg_match(struct bpf_verifier_env *env,
>>   		kptr_get = kfunc_meta->flags & KF_KPTR_GET;
>>   		trusted_args = kfunc_meta->flags & KF_TRUSTED_ARGS;
>>   		sleepable = kfunc_meta->flags & KF_SLEEPABLE;
>> +		rcu_lock = kfunc_meta->flags & KF_RCU_LOCK;
>> +		rcu_unlock = kfunc_meta->flags & KF_RCU_UNLOCK;
>> +	}
>> +
>> +	/* checking rcu read lock/unlock */
>> +	if (env->cur_state->active_rcu_lock > 0) {
>> +		if (rcu_lock) {
>> +			bpf_log(log, "nested rcu read lock (kernel function %s)\n", func_name);
>> +			return -EINVAL;
>> +		} else if (rcu_unlock) {
>> +			/* change active_rcu_lock to its corresponding negative value to
>> +			 * preserve the previous lock region id.
>> +			 */
>> +			env->cur_state->active_rcu_lock = -env->cur_state->active_rcu_lock;
>> +		} else if (sleepable) {
>> +			bpf_log(log, "kernel func %s is sleepable within rcu_read_lock region\n",
>> +				func_name);
>> +			return -EINVAL;
>> +		}
>> +	} else if (rcu_lock) {
>> +		/* a new lock region started, increase the region id. */
>> +		env->cur_state->active_rcu_lock = (-env->cur_state->active_rcu_lock) + 1;
>> +	} else if (rcu_unlock) {
>> +		bpf_log(log, "unmatched rcu read unlock (kernel function %s)\n", func_name);
>> +		return -EINVAL;
>>   	}
>>
> 
> Can you provide more context on why having ids is better than simply
> invalidating the registers when the section ends, and making active_rcu_lock a
> boolean instead? You can use bpf_for_each_reg_in_vstate to find every reg having
> MEM_RCU and mark it unknown.

I think we also need to invalidate rcu-ptr related states as well in spills.

I also tried to support cases like:
	bpf_rcu_read_lock();
	rcu_ptr = ...
	   ... rcu_ptr ...
	bpf_rcu_read_unlock();
	... rcu_ptr ... /* no load, just use the rcu_ptr somehow */

In the above case, outside the rcu read lock region, there is no
load with rcu_ptr but it can still be used for other purposes
with a property of a pointer.

But for a second thought, it should be okay to invalidate
rcu_ptr during bpf_rcu_read_unlock() as a scalar. This should
satisfy almost all (if not all) cases.

> 
> You won't have to match the id in btf_struct_access as such registers won't ever
> reach that function (if marked unknown on invalidation, they become scalars).
> The reg state won't need another active_rcu_lock member either, it is simply
> part of reg->type.

Right, if I don't maintain region id's, no need to have 
reg->active_rcu_lock and using MEM_RCU should be enough.

> 
> It seems to that simply invalidating registers when rcu_read_unlock is called is
> both less code to write and simpler to understand.

invalidating rcu_ptr in registers and spills.

Let me try to implement this and compare to my current approach. I guess
MEM_RCU + invalidation at bpf_rcu_read_unlock() should be simpler as you
suggested.

> 
> Having ids also makes the pruning algorithm unecessarily conservative.
> Later in states_equal, the check is:
> 
>> +	if (old->active_rcu_lock != cur->active_rcu_lock)
>> +		return false;
> 
> which means even though the current state just holding the RCU read lock would
> be enough to prune search, it would be rejected now due to distinct IDs (e.g. if
> the current path didn't make exactly the same number of rcu_read_lock calls
> compared to the old state).

That is true. We should also check old/new verifier state. If both
verifier state are not in rcu read lock region. The above check can
be ignored. But agree this becomes a little bit more complicated.