| Message ID | 20190116050830.1881316-2-ast@kernel.org |
|---|---|
| State | Changes Requested |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | introduce bpf_spin_lock | expand |
On 01/16/2019 06:08 AM, Alexei Starovoitov wrote: > Introduce 'struct bpf_spin_lock' and bpf_spin_lock/unlock() helpers to let > bpf program serialize access to other variables. > > Example: > struct hash_elem { > int cnt; > struct bpf_spin_lock lock; > }; > struct hash_elem * val = bpf_map_lookup_elem(&hash_map, &key); > if (val) { > bpf_spin_lock(&val->lock); > val->cnt++; > bpf_spin_unlock(&val->lock); > } > > Restrictions and safety checks: > - bpf_spin_lock is only allowed inside HASH and ARRAY maps. > - BTF description of the map is mandatory for safety analysis. > - bpf program can take one bpf_spin_lock at a time, since two or more can > cause dead locks. > - only one 'struct bpf_spin_lock' is allowed per map element. > It drastically simplifies implementation yet allows bpf program to use > any number of bpf_spin_locks. > - when bpf_spin_lock is taken the calls (either bpf2bpf or helpers) are not allowed. > - bpf program must bpf_spin_unlock() before return. > - bpf program can access 'struct bpf_spin_lock' only via > bpf_spin_lock()/bpf_spin_unlock() helpers. > - load/store into 'struct bpf_spin_lock lock;' field is not allowed. > - to use bpf_spin_lock() helper the BTF description of map value must be > a struct and have 'struct bpf_spin_lock anyname;' field at the top level. > Nested lock inside another struct is not allowed. > - syscall map_lookup doesn't copy bpf_spin_lock field to user space. > - syscall map_update and program map_update do not update bpf_spin_lock field. > - bpf_spin_lock cannot be on the stack or inside networking packet. > bpf_spin_lock can only be inside HASH or ARRAY map value. > - bpf_spin_lock is available to root only and to all program types. > > Implementation details: > - on !SMP bpf_spin_lock() becomes nop > - presence of bpf_spin_lock inside map value could have been indicated via > extra flag during map_create, but specifying it via BTF is cleaner. > It provides introspection for map key/value and reduces user coding mistakes. > > Next steps: > - allow bpf_spin_lock in other map types (like cgroup local storage) > - introduce BPF_F_LOCK flag for bpf_map_update() syscall and helper > to request kernel to grab bpf_spin_lock before rewriting the value. > That will serialize access to map elements. > > Signed-off-by: Alexei Starovoitov <ast@kernel.org> [...] > diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c > index a74972b07e74..591fdedae7bf 100644 > --- a/kernel/bpf/helpers.c > +++ b/kernel/bpf/helpers.c > @@ -221,6 +221,41 @@ const struct bpf_func_proto bpf_get_current_comm_proto = { > .arg2_type = ARG_CONST_SIZE, > }; > > +BPF_CALL_1(bpf_spin_lock, struct bpf_spin_lock *, lock) > +{ > +#if defined(CONFIG_SMP) > + struct qspinlock *qlock = (void *)lock; > + > + BUILD_BUG_ON(sizeof(*qlock) != sizeof(*lock)); > + queued_spin_lock(qlock); > +#endif > + return 0; > +} > + > +const struct bpf_func_proto bpf_spin_lock_proto = { > + .func = bpf_spin_lock, > + .gpl_only = false, > + .ret_type = RET_VOID, > + .arg1_type = ARG_PTR_TO_SPIN_LOCK, > +}; > + > +BPF_CALL_1(bpf_spin_unlock, struct bpf_spin_lock *, lock) > +{ > +#if defined(CONFIG_SMP) > + struct qspinlock *qlock = (void *)lock; > + > + queued_spin_unlock(qlock); > +#endif > + return 0; > +} > + > +const struct bpf_func_proto bpf_spin_unlock_proto = { > + .func = bpf_spin_unlock, > + .gpl_only = false, > + .ret_type = RET_VOID, > + .arg1_type = ARG_PTR_TO_SPIN_LOCK, > +}; > + > #ifdef CONFIG_CGROUPS > BPF_CALL_0(bpf_get_current_cgroup_id) > { > diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c > index b155cd17c1bd..ebf0a673cb83 100644 > --- a/kernel/bpf/syscall.c > +++ b/kernel/bpf/syscall.c > @@ -463,7 +463,7 @@ int map_check_no_btf(const struct bpf_map *map, > return -ENOTSUPP; > } > > -static int map_check_btf(const struct bpf_map *map, const struct btf *btf, > +static int map_check_btf(struct bpf_map *map, const struct btf *btf, > u32 btf_key_id, u32 btf_value_id) > { > const struct btf_type *key_type, *value_type; > @@ -478,6 +478,21 @@ static int map_check_btf(const struct bpf_map *map, const struct btf *btf, > if (!value_type || value_size != map->value_size) > return -EINVAL; > > + map->spin_lock_off = btf_find_spin_lock(btf, value_type); > + > + if (map_value_has_spin_lock(map)) { > + if (map->map_type != BPF_MAP_TYPE_HASH && > + map->map_type != BPF_MAP_TYPE_ARRAY) > + return -ENOTSUPP; > + if (map->spin_lock_off + sizeof(struct bpf_spin_lock) > > + map->value_size) { > + WARN_ONCE(1, > + "verifier bug spin_lock_off %d value_size %d\n", > + map->spin_lock_off, map->value_size); > + return -EFAULT; > + } > + } > + > if (map->ops->map_check_btf) > ret = map->ops->map_check_btf(map, btf, key_type, value_type); > > @@ -542,6 +557,8 @@ static int map_create(union bpf_attr *attr) > map->btf = btf; > map->btf_key_type_id = attr->btf_key_type_id; > map->btf_value_type_id = attr->btf_value_type_id; > + } else { > + map->spin_lock_off = -EINVAL; > } > > err = security_bpf_map_alloc(map); > @@ -740,7 +757,7 @@ static int map_lookup_elem(union bpf_attr *attr) > err = -ENOENT; > } else { > err = 0; > - memcpy(value, ptr, value_size); > + copy_map_value(map, value, ptr); > } > rcu_read_unlock(); > } > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c > index 56674a7c3778..0f3d1fb30d7a 100644 > --- a/kernel/bpf/verifier.c > +++ b/kernel/bpf/verifier.c > @@ -213,6 +213,7 @@ struct bpf_call_arg_meta { > s64 msize_smax_value; > u64 msize_umax_value; > int ptr_id; > + int func_id; > }; > > static DEFINE_MUTEX(bpf_verifier_lock); > @@ -351,6 +352,12 @@ static bool reg_is_refcounted(const struct bpf_reg_state *reg) > return type_is_refcounted(reg->type); > } > > +static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg) > +{ > + return reg->type == PTR_TO_MAP_VALUE && > + map_value_has_spin_lock(reg->map_ptr); > +} > + > static bool reg_is_refcounted_or_null(const struct bpf_reg_state *reg) > { > return type_is_refcounted_or_null(reg->type); > @@ -712,6 +719,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state, > } > dst_state->speculative = src->speculative; > dst_state->curframe = src->curframe; > + dst_state->active_spin_lock = src->active_spin_lock; > for (i = 0; i <= src->curframe; i++) { > dst = dst_state->frame[i]; > if (!dst) { > @@ -1483,6 +1491,21 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno, > if (err) > verbose(env, "R%d max value is outside of the array range\n", > regno); > + > + if (map_value_has_spin_lock(reg->map_ptr)) { > + u32 lock = reg->map_ptr->spin_lock_off; > + > + /* if any part of struct bpf_spin_lock can be touched by > + * load/store reject this program > + */ > + if ((reg->smin_value + off <= lock && > + lock < reg->umax_value + off + size) || > + (reg->smin_value + off < lock + sizeof(struct bpf_spin_lock) && > + lock + sizeof(struct bpf_spin_lock) <= reg->umax_value + off + size)) { > + verbose(env, "bpf_spin_lock cannot be accessed directly by load/store\n"); > + return -EACCES; > + } > + } > return err; > } > > @@ -2192,6 +2215,91 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, > } > } > > +/* Implementation details: > + * bpf_map_lookup returns PTR_TO_MAP_VALUE_OR_NULL > + * Two bpf_map_lookups (even with the same key) will have different reg->id. > + * For traditional PTR_TO_MAP_VALUE the verifier clears reg->id after > + * value_or_null->value transition, since the verifier only cares about > + * the range of access to valid map value pointer and doesn't care about actual > + * address of the map element. > + * For maps with 'struct bpf_spin_lock' inside map value the verifier keeps > + * reg->id > 0 after value_or_null->value transition. By doing so > + * two bpf_map_lookups will be considered two different pointers that > + * point to different bpf_spin_locks. > + * The verifier allows taking only one bpf_spin_lock at a time to avoid > + * dead-locks. > + * Since only one bpf_spin_lock is allowed the checks are simpler than > + * reg_is_refcounted() logic. The verifier needs to remember only > + * one spin_lock instead of array of acquired_refs. > + * cur_state->active_spin_lock remembers which map value element got locked > + * and clears it after bpf_spin_unlock. > + */ > +static int process_spin_lock(struct bpf_verifier_env *env, int regno, > + bool is_lock) > +{ > + struct bpf_reg_state *regs = cur_regs(env), *reg = ®s[regno]; > + struct bpf_verifier_state *cur = env->cur_state; > + bool is_const = tnum_is_const(reg->var_off); > + struct bpf_map *map = reg->map_ptr; > + u64 val = reg->var_off.value; > + > + if (reg->type != PTR_TO_MAP_VALUE) { > + verbose(env, "R%d is not a pointer to map_value\n", regno); > + return -EINVAL; > + } > + if (!is_const) { > + verbose(env, > + "R%d doesn't have constant offset. bpf_spin_lock has to be at the constant offset\n", > + regno); > + return -EINVAL; > + } > + if (!map->btf) { > + verbose(env, > + "map '%s' has to have BTF in order to use bpf_spin_lock\n", > + map->name); > + return -EINVAL; > + } > + if (!map_value_has_spin_lock(map)) { > + if (map->spin_lock_off == -E2BIG) > + verbose(env, > + "map '%s' has more than one 'struct bpf_spin_lock'\n", > + map->name); > + else if (map->spin_lock_off == -ENOENT) > + verbose(env, > + "map '%s' doesn't have 'struct bpf_spin_lock'\n", > + map->name); > + else > + verbose(env, > + "map '%s' is not a struct type or bpf_spin_lock is mangled\n", > + map->name); > + return -EINVAL; > + } > + if (map->spin_lock_off != val + reg->off) { > + verbose(env, "off %lld doesn't point to 'struct bpf_spin_lock'\n", > + val + reg->off); > + return -EINVAL; > + } > + if (is_lock) { > + if (cur->active_spin_lock) { > + verbose(env, > + "Locking two bpf_spin_locks are not allowed\n"); > + return -EINVAL; > + } > + cur->active_spin_lock = reg->id; > + } else { > + if (!cur->active_spin_lock) { > + verbose(env, "bpf_spin_unlock without taking a lock\n"); > + return -EINVAL; > + } > + if (cur->active_spin_lock != reg->id) { > + verbose(env, "bpf_spin_unlock of different lock\n"); > + return -EINVAL; > + } > + cur->active_spin_lock = 0; > + } > + return 0; > +} > + > static bool arg_type_is_mem_ptr(enum bpf_arg_type type) > { > return type == ARG_PTR_TO_MEM || > @@ -2268,6 +2376,17 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno, > return -EFAULT; > } > meta->ptr_id = reg->id; > + } else if (arg_type == ARG_PTR_TO_SPIN_LOCK) { > + if (meta->func_id == BPF_FUNC_spin_lock) { > + if (process_spin_lock(env, regno, true)) > + return -EACCES; > + } else if (meta->func_id == BPF_FUNC_spin_unlock) { > + if (process_spin_lock(env, regno, false)) > + return -EACCES; > + } else { > + verbose(env, "verifier internal error\n"); > + return -EFAULT; > + } > } else if (arg_type_is_mem_ptr(arg_type)) { > expected_type = PTR_TO_STACK; > /* One exception here. In case function allows for NULL to be > @@ -2887,6 +3006,7 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn > return err; > } > > + meta.func_id = func_id; > /* check args */ > err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta); > if (err) > @@ -4344,7 +4464,8 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state, > } else if (reg->type == PTR_TO_SOCKET_OR_NULL) { > reg->type = PTR_TO_SOCKET; > } > - if (is_null || !reg_is_refcounted(reg)) { > + if (is_null || !(reg_is_refcounted(reg) || > + reg_may_point_to_spin_lock(reg))) { > /* We don't need id from this point onwards anymore, > * thus we should better reset it, so that state > * pruning has chances to take effect. > @@ -5651,6 +5772,9 @@ static bool states_equal(struct bpf_verifier_env *env, > if (old->speculative && !cur->speculative) > return false; > > + if (old->active_spin_lock != cur->active_spin_lock) > + return false; > + > /* for states to be equal callsites have to be the same > * and all frame states need to be equivalent > */ > @@ -6068,6 +6192,12 @@ static int do_check(struct bpf_verifier_env *env) > return -EINVAL; > } > > + if (env->cur_state->active_spin_lock && > + (insn->src_reg == BPF_PSEUDO_CALL || > + insn->imm != BPF_FUNC_spin_unlock)) { > + verbose(env, "function calls are not allowed while holding a lock\n"); > + return -EINVAL; > + } > if (insn->src_reg == BPF_PSEUDO_CALL) > err = check_func_call(env, insn, &env->insn_idx); > else > @@ -6096,6 +6226,11 @@ static int do_check(struct bpf_verifier_env *env) > return -EINVAL; > } > > + if (env->cur_state->active_spin_lock) { > + verbose(env, "bpf_spin_unlock is missing\n"); > + return -EINVAL; > + } > + > if (state->curframe) { > /* exit from nested function */ > env->prev_insn_idx = env->insn_idx; I think if I'm not mistaken there should still be a possibility for causing a deadlock, namely if in the middle of the critical section I'm using an LD_ABS or LD_IND instruction with oob index such that I cause an implicit return 0 while lock is held. At least I don't see this being caught, probably also for such case a test_verifier snippet would be good. Wouldn't we also need to mark queued spinlock functions as notrace such that e.g. from kprobe one cannot attach to these causing a deadlock?
On 01/16/2019 11:48 PM, Daniel Borkmann wrote: > On 01/16/2019 06:08 AM, Alexei Starovoitov wrote: [...] >> @@ -6096,6 +6226,11 @@ static int do_check(struct bpf_verifier_env *env) >> return -EINVAL; >> } >> >> + if (env->cur_state->active_spin_lock) { >> + verbose(env, "bpf_spin_unlock is missing\n"); >> + return -EINVAL; >> + } >> + >> if (state->curframe) { >> /* exit from nested function */ >> env->prev_insn_idx = env->insn_idx; > > I think if I'm not mistaken there should still be a possibility for causing a > deadlock, namely if in the middle of the critical section I'm using an LD_ABS > or LD_IND instruction with oob index such that I cause an implicit return 0 > while lock is held. At least I don't see this being caught, probably also for > such case a test_verifier snippet would be good. > > Wouldn't we also need to mark queued spinlock functions as notrace such that > e.g. from kprobe one cannot attach to these causing a deadlock? I think there may be another problem: haven't verified, but it might be possible at least from reading the code that I have two programs which share a common array/hash with spin_lock in BTF provided. Program A is properly using spin_lock as in one of your examples. Program B is using map in map with inner map being that same map using spin_lock. When we return that fake inner_map_meta as reg->map_ptr then we can bypass any read/write restrictions into spin_lock area which is normally prevented by verifier. Meaning, map in map needs to be made aware of spin_lock case as well. Thanks, Daniel
On Wed, Jan 16, 2019 at 11:48:15PM +0100, Daniel Borkmann wrote: > > I think if I'm not mistaken there should still be a possibility for causing a > deadlock, namely if in the middle of the critical section I'm using an LD_ABS > or LD_IND instruction with oob index such that I cause an implicit return 0 > while lock is held. At least I don't see this being caught, probably also for > such case a test_verifier snippet would be good. good catch. My earlier implementation was reusing check_reference_leak() that is called for both bpf_exit and bpf_ld_abs, but then I realized we cannot call bpf_exit from callee when lock is held and moved that check before prepare_func_exit() forgetting about ldabs. argh. Will fix. > Wouldn't we also need to mark queued spinlock functions as notrace such that > e.g. from kprobe one cannot attach to these causing a deadlock? there is recursion check already, so I'm not sure that is necessary, but will add it since it doesn't hurt and safer indeed.
On Thu, Jan 17, 2019 at 12:16:44AM +0100, Daniel Borkmann wrote: > On 01/16/2019 11:48 PM, Daniel Borkmann wrote: > > On 01/16/2019 06:08 AM, Alexei Starovoitov wrote: > [...] > >> @@ -6096,6 +6226,11 @@ static int do_check(struct bpf_verifier_env *env) > >> return -EINVAL; > >> } > >> > >> + if (env->cur_state->active_spin_lock) { > >> + verbose(env, "bpf_spin_unlock is missing\n"); > >> + return -EINVAL; > >> + } > >> + > >> if (state->curframe) { > >> /* exit from nested function */ > >> env->prev_insn_idx = env->insn_idx; > > > > I think if I'm not mistaken there should still be a possibility for causing a > > deadlock, namely if in the middle of the critical section I'm using an LD_ABS > > or LD_IND instruction with oob index such that I cause an implicit return 0 > > while lock is held. At least I don't see this being caught, probably also for > > such case a test_verifier snippet would be good. > > > > Wouldn't we also need to mark queued spinlock functions as notrace such that > > e.g. from kprobe one cannot attach to these causing a deadlock? > > I think there may be another problem: haven't verified, but it might be possible > at least from reading the code that I have two programs which share a common > array/hash with spin_lock in BTF provided. Program A is properly using spin_lock > as in one of your examples. Program B is using map in map with inner map being > that same map using spin_lock. When we return that fake inner_map_meta as > reg->map_ptr then we can bypass any read/write restrictions into spin_lock area > which is normally prevented by verifier. Meaning, map in map needs to be made > aware of spin_lock case as well. 2nd great catch. thanks! Indeed inner_map_meta doesn't preserve all the fields from struct bpf_map. It seems long term we'll be able to support spin_lock in inner map too, but for now I'll disable it.
On Tue, Jan 15, 2019 at 09:08:22PM -0800, Alexei Starovoitov wrote: [ ... ] > +/* copy everything but bpf_spin_lock */ > +static inline void copy_map_value(struct bpf_map *map, void *dst, void *src) > +{ > + if (unlikely(map_value_has_spin_lock(map))) { > + u32 off = map->spin_lock_off; > + > + memcpy(dst, src, off); > + memcpy(dst + off + sizeof(struct bpf_spin_lock), > + src + off + sizeof(struct bpf_spin_lock), > + map->value_size - off - sizeof(struct bpf_spin_lock)); > + } else { > + memcpy(dst, src, map->value_size); > + } > +} > + [ ... ] > +int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t) > +{ > + const struct btf_member *member; > + u32 i, off = -ENOENT; > + > + if (BTF_INFO_KIND(t->info) != BTF_KIND_STRUCT) > + return -EINVAL; > + > + for_each_member(i, t, member) { > + const struct btf_type *member_type = btf_type_by_id(btf, > + member->type); > + if (!btf_type_is_struct(member_type)) may be using "BTF_INFO_KIND(t->info) != BTF_KIND_STRUCT" here also. > + continue; > + if (member_type->size != sizeof(struct bpf_spin_lock)) > + continue; > + if (strcmp(__btf_name_by_offset(btf, member_type->name_off), > + "bpf_spin_lock")) > + continue; > + if (off != -ENOENT) > + /* only one 'struct bpf_spin_lock' is allowed */ > + return -E2BIG; > + off = btf_member_bit_offset(t, member); > + if (off % 8) > + /* valid C code cannot generate such BTF */ > + return -EINVAL; > + off /= 8; > + if (off % __alignof__(struct bpf_spin_lock)) > + /* valid struct bpf_spin_lock will be 4 byte aligned */ > + return -EINVAL; > + } > + return off; > +} > + [ ... ] > diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c > index b155cd17c1bd..ebf0a673cb83 100644 > --- a/kernel/bpf/syscall.c > +++ b/kernel/bpf/syscall.c [ ... ] > err = security_bpf_map_alloc(map); > @@ -740,7 +757,7 @@ static int map_lookup_elem(union bpf_attr *attr) > err = -ENOENT; > } else { > err = 0; > - memcpy(value, ptr, value_size); > + copy_map_value(map, value, ptr); copy_map_value() skips the bpf_spin_lock and "value" has not been zero-ed. "value" is then copied to the "__user *uvalue". May be init the bpf_spin_lock part of the "uvalue" to 0? btw, somehow patch 6 and 7 are missing: https://patchwork.ozlabs.org/cover/1025640/
On 01/17/2019 12:30 AM, Alexei Starovoitov wrote: > On Thu, Jan 17, 2019 at 12:16:44AM +0100, Daniel Borkmann wrote: >> On 01/16/2019 11:48 PM, Daniel Borkmann wrote: >>> On 01/16/2019 06:08 AM, Alexei Starovoitov wrote: >> [...] >>>> @@ -6096,6 +6226,11 @@ static int do_check(struct bpf_verifier_env *env) >>>> return -EINVAL; >>>> } >>>> >>>> + if (env->cur_state->active_spin_lock) { >>>> + verbose(env, "bpf_spin_unlock is missing\n"); >>>> + return -EINVAL; >>>> + } >>>> + >>>> if (state->curframe) { >>>> /* exit from nested function */ >>>> env->prev_insn_idx = env->insn_idx; >>> >>> I think if I'm not mistaken there should still be a possibility for causing a >>> deadlock, namely if in the middle of the critical section I'm using an LD_ABS >>> or LD_IND instruction with oob index such that I cause an implicit return 0 >>> while lock is held. At least I don't see this being caught, probably also for >>> such case a test_verifier snippet would be good. >>> >>> Wouldn't we also need to mark queued spinlock functions as notrace such that >>> e.g. from kprobe one cannot attach to these causing a deadlock? >> >> I think there may be another problem: haven't verified, but it might be possible >> at least from reading the code that I have two programs which share a common >> array/hash with spin_lock in BTF provided. Program A is properly using spin_lock >> as in one of your examples. Program B is using map in map with inner map being >> that same map using spin_lock. When we return that fake inner_map_meta as >> reg->map_ptr then we can bypass any read/write restrictions into spin_lock area >> which is normally prevented by verifier. Meaning, map in map needs to be made >> aware of spin_lock case as well. > > 2nd great catch. thanks! > Indeed inner_map_meta doesn't preserve all the fields from struct bpf_map. > It seems long term we'll be able to support spin_lock in inner map too, > but for now I'll disable it. There's also one more potential issue in pruning I _think_. In regsafe() we make the basic assumption that for PTR_TO_MAP_VALUE id has been zeroed which is true up to here, and as such we prune state not taking id into account. The only other case we have is PTR_TO_SOCKET{,_OR_NULL} which only allows for exact matches. Potentially there could be a case where you have two map pointers from different branches but with same basic map properties read/ writing map data, and in first run for PTR_TO_MAP_VALUE w/o spin_lock path it was considered safe such that we would get a match in regsafe() as well and could potentially prune the access? I guess definitely worth adding such test case to test_verifier to make sure.
On Thu, Jan 17, 2019 at 12:16:18AM +0000, Martin Lau wrote: > On Tue, Jan 15, 2019 at 09:08:22PM -0800, Alexei Starovoitov wrote: > [ ... ] > > > +/* copy everything but bpf_spin_lock */ > > +static inline void copy_map_value(struct bpf_map *map, void *dst, void *src) > > +{ > > + if (unlikely(map_value_has_spin_lock(map))) { > > + u32 off = map->spin_lock_off; > > + > > + memcpy(dst, src, off); > > + memcpy(dst + off + sizeof(struct bpf_spin_lock), > > + src + off + sizeof(struct bpf_spin_lock), > > + map->value_size - off - sizeof(struct bpf_spin_lock)); > > + } else { > > + memcpy(dst, src, map->value_size); > > + } > > +} > > + > [ ... ] > > > +int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t) > > +{ > > + const struct btf_member *member; > > + u32 i, off = -ENOENT; > > + > > + if (BTF_INFO_KIND(t->info) != BTF_KIND_STRUCT) > > + return -EINVAL; > > + > > + for_each_member(i, t, member) { > > + const struct btf_type *member_type = btf_type_by_id(btf, > > + member->type); > > + if (!btf_type_is_struct(member_type)) > may be using "BTF_INFO_KIND(t->info) != BTF_KIND_STRUCT" here also. good point. will do. > > + continue; > > + if (member_type->size != sizeof(struct bpf_spin_lock)) > > + continue; > > + if (strcmp(__btf_name_by_offset(btf, member_type->name_off), > > + "bpf_spin_lock")) > > + continue; > > + if (off != -ENOENT) > > + /* only one 'struct bpf_spin_lock' is allowed */ > > + return -E2BIG; > > + off = btf_member_bit_offset(t, member); > > + if (off % 8) > > + /* valid C code cannot generate such BTF */ > > + return -EINVAL; > > + off /= 8; > > + if (off % __alignof__(struct bpf_spin_lock)) > > + /* valid struct bpf_spin_lock will be 4 byte aligned */ > > + return -EINVAL; > > + } > > + return off; > > +} > > + > [ ... ] > > > > diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c > > index b155cd17c1bd..ebf0a673cb83 100644 > > --- a/kernel/bpf/syscall.c > > +++ b/kernel/bpf/syscall.c > [ ... ] > > > err = security_bpf_map_alloc(map); > > @@ -740,7 +757,7 @@ static int map_lookup_elem(union bpf_attr *attr) > > err = -ENOENT; > > } else { > > err = 0; > > - memcpy(value, ptr, value_size); > > + copy_map_value(map, value, ptr); > copy_map_value() skips the bpf_spin_lock and "value" has not been zero-ed. > "value" is then copied to the "__user *uvalue". > May be init the bpf_spin_lock part of the "uvalue" to 0? I guess something went wrong with my scripts. The patch on my side has this: if (attr->flags & BPF_F_LOCK) { /* lock 'ptr' elem and copy * everything but the lock */ copy_map_value_locked(map, value, ptr, true); /* mask lock, since value was kmalloced */ check_and_init_map_lock(map, value); } else { copy_map_value(map, value, ptr); } and lock is inited to zero before copying to user space. But I don't see the same in patchworks, so you're absolutely right to point it out as a bug. > btw, somehow patch 6 and 7 are missing: > https://patchwork.ozlabs.org/cover/1025640/ Indeed and I cannot explain why. Hopefully v2 won't have this weirdness.
On Thu, Jan 17, 2019 at 01:21:32AM +0100, Daniel Borkmann wrote: > On 01/17/2019 12:30 AM, Alexei Starovoitov wrote: > > On Thu, Jan 17, 2019 at 12:16:44AM +0100, Daniel Borkmann wrote: > >> On 01/16/2019 11:48 PM, Daniel Borkmann wrote: > >>> On 01/16/2019 06:08 AM, Alexei Starovoitov wrote: > >> [...] > >>>> @@ -6096,6 +6226,11 @@ static int do_check(struct bpf_verifier_env *env) > >>>> return -EINVAL; > >>>> } > >>>> > >>>> + if (env->cur_state->active_spin_lock) { > >>>> + verbose(env, "bpf_spin_unlock is missing\n"); > >>>> + return -EINVAL; > >>>> + } > >>>> + > >>>> if (state->curframe) { > >>>> /* exit from nested function */ > >>>> env->prev_insn_idx = env->insn_idx; > >>> > >>> I think if I'm not mistaken there should still be a possibility for causing a > >>> deadlock, namely if in the middle of the critical section I'm using an LD_ABS > >>> or LD_IND instruction with oob index such that I cause an implicit return 0 > >>> while lock is held. At least I don't see this being caught, probably also for > >>> such case a test_verifier snippet would be good. > >>> > >>> Wouldn't we also need to mark queued spinlock functions as notrace such that > >>> e.g. from kprobe one cannot attach to these causing a deadlock? > >> > >> I think there may be another problem: haven't verified, but it might be possible > >> at least from reading the code that I have two programs which share a common > >> array/hash with spin_lock in BTF provided. Program A is properly using spin_lock > >> as in one of your examples. Program B is using map in map with inner map being > >> that same map using spin_lock. When we return that fake inner_map_meta as > >> reg->map_ptr then we can bypass any read/write restrictions into spin_lock area > >> which is normally prevented by verifier. Meaning, map in map needs to be made > >> aware of spin_lock case as well. > > > > 2nd great catch. thanks! > > Indeed inner_map_meta doesn't preserve all the fields from struct bpf_map. > > It seems long term we'll be able to support spin_lock in inner map too, > > but for now I'll disable it. > > There's also one more potential issue in pruning I _think_. In regsafe() we > make the basic assumption that for PTR_TO_MAP_VALUE id has been zeroed which > is true up to here, and as such we prune state not taking id into account. > The only other case we have is PTR_TO_SOCKET{,_OR_NULL} which only allows > for exact matches. Potentially there could be a case where you have two map > pointers from different branches but with same basic map properties read/ > writing map data, and in first run for PTR_TO_MAP_VALUE w/o spin_lock path > it was considered safe such that we would get a match in regsafe() as well > and could potentially prune the access? I guess definitely worth adding such > test case to test_verifier to make sure. Hmm. Something to think about for sure. I belive if (old->active_spin_lock != cur->active_spin_lock) check protects from all cases where spin_lock-ed paths are mixed with non-spin. Like going through non-locked ld/st of map_value in the first pass through the prog and then jumping half way into that pass after taking spin_lock to trigger regsafe(). I cannot quite see how to construct such test without triggering old->active_spin_lock != cur->active_spin_lock before reaching regsafe(). But I will keep thinking. If you have more concrete description for the test please suggest.
On 01/17/2019 02:16 AM, Alexei Starovoitov wrote: > On Thu, Jan 17, 2019 at 01:21:32AM +0100, Daniel Borkmann wrote: >> On 01/17/2019 12:30 AM, Alexei Starovoitov wrote: >>> On Thu, Jan 17, 2019 at 12:16:44AM +0100, Daniel Borkmann wrote: >>>> On 01/16/2019 11:48 PM, Daniel Borkmann wrote: >>>>> On 01/16/2019 06:08 AM, Alexei Starovoitov wrote: >>>> [...] >>>>>> @@ -6096,6 +6226,11 @@ static int do_check(struct bpf_verifier_env *env) >>>>>> return -EINVAL; >>>>>> } >>>>>> >>>>>> + if (env->cur_state->active_spin_lock) { >>>>>> + verbose(env, "bpf_spin_unlock is missing\n"); >>>>>> + return -EINVAL; >>>>>> + } >>>>>> + >>>>>> if (state->curframe) { >>>>>> /* exit from nested function */ >>>>>> env->prev_insn_idx = env->insn_idx; >>>>> >>>>> I think if I'm not mistaken there should still be a possibility for causing a >>>>> deadlock, namely if in the middle of the critical section I'm using an LD_ABS >>>>> or LD_IND instruction with oob index such that I cause an implicit return 0 >>>>> while lock is held. At least I don't see this being caught, probably also for >>>>> such case a test_verifier snippet would be good. >>>>> >>>>> Wouldn't we also need to mark queued spinlock functions as notrace such that >>>>> e.g. from kprobe one cannot attach to these causing a deadlock? >>>> >>>> I think there may be another problem: haven't verified, but it might be possible >>>> at least from reading the code that I have two programs which share a common >>>> array/hash with spin_lock in BTF provided. Program A is properly using spin_lock >>>> as in one of your examples. Program B is using map in map with inner map being >>>> that same map using spin_lock. When we return that fake inner_map_meta as >>>> reg->map_ptr then we can bypass any read/write restrictions into spin_lock area >>>> which is normally prevented by verifier. Meaning, map in map needs to be made >>>> aware of spin_lock case as well. >>> >>> 2nd great catch. thanks! >>> Indeed inner_map_meta doesn't preserve all the fields from struct bpf_map. >>> It seems long term we'll be able to support spin_lock in inner map too, >>> but for now I'll disable it. >> >> There's also one more potential issue in pruning I _think_. In regsafe() we >> make the basic assumption that for PTR_TO_MAP_VALUE id has been zeroed which >> is true up to here, and as such we prune state not taking id into account. >> The only other case we have is PTR_TO_SOCKET{,_OR_NULL} which only allows >> for exact matches. Potentially there could be a case where you have two map >> pointers from different branches but with same basic map properties read/ >> writing map data, and in first run for PTR_TO_MAP_VALUE w/o spin_lock path >> it was considered safe such that we would get a match in regsafe() as well >> and could potentially prune the access? I guess definitely worth adding such >> test case to test_verifier to make sure. > > Hmm. Something to think about for sure. > I belive if (old->active_spin_lock != cur->active_spin_lock) check > protects from all cases where spin_lock-ed paths are mixed with non-spin. > Like going through non-locked ld/st of map_value in the first pass through > the prog and then jumping half way into that pass after taking spin_lock > to trigger regsafe(). > I cannot quite see how to construct such test without triggering > old->active_spin_lock != cur->active_spin_lock > before reaching regsafe(). > But I will keep thinking. > If you have more concrete description for the test please suggest. Was thinking something like this, in very rough pseudo code: Prog A (normal spin lock use of mapA): val = bpf_map_lookup_elem(&mapA, &key); if (val) { bpf_spin_lock(&val->lock); [...] bpf_spin_unlock(&val->lock); } Prog B: if (non_const_condition_A) { map_ptr = &mapB; // mapB is normal array map with same // properties as mapA, but no BTF and // thus no spinlock use. } else { map_ptr = &mapA; } val = bpf_map_lookup_elem(&map_ptr, &key); map_ptr = 0; // clear map reg to match for // both verification paths if (val) { // turning val into PTR_TO_MAP_VALUE if (non_const_condition_B) { // write into memory area of spin_lock; // first path with mapB is considered // safe (since map with no spin_lock so // write into this area allowed); // now when verifier is checking the // non_const_condition_A's else path // with mapA, then non_const_condition_B // has pruning checkpoint and is going // to compare reg with PTR_TO_MAP_VALUE; // since id is not considered I /think/ // verifier would find it (wrongly) safe // as well. } } Wdyt? Thanks, Daniel
On Thu, Jan 17, 2019 at 12:27:55PM +0100, Daniel Borkmann wrote: > > Was thinking something like this, in very rough pseudo code: > > Prog A (normal spin lock use of mapA): > > val = bpf_map_lookup_elem(&mapA, &key); > if (val) { > bpf_spin_lock(&val->lock); > [...] > bpf_spin_unlock(&val->lock); > } > > Prog B: > > if (non_const_condition_A) { > map_ptr = &mapB; // mapB is normal array map with same > // properties as mapA, but no BTF and > // thus no spinlock use. > } else { > map_ptr = &mapA; > } > val = bpf_map_lookup_elem(&map_ptr, &key); > map_ptr = 0; // clear map reg to match for > // both verification paths > if (val) { > // turning val into PTR_TO_MAP_VALUE > if (non_const_condition_B) { > // write into memory area of spin_lock; > // first path with mapB is considered > // safe (since map with no spin_lock so > // write into this area allowed); > // now when verifier is checking the > // non_const_condition_A's else path > // with mapA, then non_const_condition_B > // has pruning checkpoint and is going > // to compare reg with PTR_TO_MAP_VALUE; > // since id is not considered I /think/ > // verifier would find it (wrongly) safe > // as well. > } > } > > Wdyt? I've implemented it and it was rejected. regsafe() is doing: memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)); 'map_ptr' is before 'id' in bpf_reg_state. lookups from different maps will have different register states as expected. I still felt that we need to compare id, so I tried if (random) val = bpf_map_lookup_elem(&hash_map, &key1); else val = bpf_map_lookup_elem(&hash_map, &key2); to force pruning of two states that point to the same map. The val->spin_lock addresses will be different and intuitively it may feel that we need to compare id, but it's unnecessary. If the rest of the program is valid with val for key1 it's a good thing to prune verification for key2 to avoid spending more cycles in the verifier. All map elements have spin_locks. If bpf code is valid for one element it's valid for all elements. Then I tried to trick the verifier with the following: int flag = 0; if (random) { val = bpf_map_lookup_elem(&hash_map, &key1); } else { flag = 1; val = bpf_map_lookup_elem(&hash_map, &key2); } if (!val) goto err; bpf_spin_lock(&val->lock); bpf_spin_unlock(&val->lock); if (flag == 1) // access spin_lock with ld/st the first pass of the verifier will correctly avoid exploring 'flag == 1' condition (because the verifier is smart enough to know that the flag is 0 there), but the second pass with different reg->id for 'val' will not be pruned, since the register (or stack) where 'flag' is stored is different and the verifier will proceed and will catch ld/st into spin_lock field and the prog will be rejected. So I believe the verifier should not compare 'id' in regsafe() for PTR_TO_MAP_VALUE to have better pruning. I'll add a comment there explaining this.
diff --git a/include/linux/bpf.h b/include/linux/bpf.h index e734f163bd0b..5ffa32ea7673 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -72,14 +72,15 @@ struct bpf_map { u32 value_size; u32 max_entries; u32 map_flags; - u32 pages; + int spin_lock_off; /* >=0 valid offset, <0 error */ u32 id; int numa_node; u32 btf_key_type_id; u32 btf_value_type_id; struct btf *btf; + u32 pages; bool unpriv_array; - /* 55 bytes hole */ + /* 51 bytes hole */ /* The 3rd and 4th cacheline with misc members to avoid false sharing * particularly with refcounting. @@ -91,6 +92,34 @@ struct bpf_map { char name[BPF_OBJ_NAME_LEN]; }; +static inline bool map_value_has_spin_lock(const struct bpf_map *map) +{ + return map->spin_lock_off >= 0; +} + +static inline void check_and_init_map_lock(struct bpf_map *map, void *dst) +{ + if (likely(!map_value_has_spin_lock(map))) + return; + *(struct bpf_spin_lock *)(dst + map->spin_lock_off) = + (struct bpf_spin_lock){}; +} + +/* copy everything but bpf_spin_lock */ +static inline void copy_map_value(struct bpf_map *map, void *dst, void *src) +{ + if (unlikely(map_value_has_spin_lock(map))) { + u32 off = map->spin_lock_off; + + memcpy(dst, src, off); + memcpy(dst + off + sizeof(struct bpf_spin_lock), + src + off + sizeof(struct bpf_spin_lock), + map->value_size - off - sizeof(struct bpf_spin_lock)); + } else { + memcpy(dst, src, map->value_size); + } +} + struct bpf_offload_dev; struct bpf_offloaded_map; @@ -162,6 +191,7 @@ enum bpf_arg_type { ARG_PTR_TO_CTX, /* pointer to context */ ARG_ANYTHING, /* any (initialized) argument is ok */ ARG_PTR_TO_SOCKET, /* pointer to bpf_sock */ + ARG_PTR_TO_SPIN_LOCK, /* pointer to bpf_spin_lock */ }; /* type of values returned from helper functions */ @@ -869,7 +899,8 @@ extern const struct bpf_func_proto bpf_msg_redirect_hash_proto; extern const struct bpf_func_proto bpf_msg_redirect_map_proto; extern const struct bpf_func_proto bpf_sk_redirect_hash_proto; extern const struct bpf_func_proto bpf_sk_redirect_map_proto; - +extern const struct bpf_func_proto bpf_spin_lock_proto; +extern const struct bpf_func_proto bpf_spin_unlock_proto; extern const struct bpf_func_proto bpf_get_local_storage_proto; /* Shared helpers among cBPF and eBPF. */ diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 573cca00a0e6..ff2ff2d9e810 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -148,6 +148,7 @@ struct bpf_verifier_state { /* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES]; u32 curframe; + u32 active_spin_lock; bool speculative; }; diff --git a/include/linux/btf.h b/include/linux/btf.h index 12502e25e767..455d31b55828 100644 --- a/include/linux/btf.h +++ b/include/linux/btf.h @@ -50,6 +50,7 @@ u32 btf_id(const struct btf *btf); bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s, const struct btf_member *m, u32 expected_offset, u32 expected_size); +int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t); #ifdef CONFIG_BPF_SYSCALL const struct btf_type *btf_type_by_id(const struct btf *btf, u32 type_id); diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h index 91c43884f295..30f9dfd40f13 100644 --- a/include/uapi/linux/bpf.h +++ b/include/uapi/linux/bpf.h @@ -2421,7 +2421,9 @@ union bpf_attr { FN(map_peek_elem), \ FN(msg_push_data), \ FN(msg_pop_data), \ - FN(rc_pointer_rel), + FN(rc_pointer_rel), \ + FN(spin_lock), \ + FN(spin_unlock), /* integer value in 'imm' field of BPF_CALL instruction selects which helper * function eBPF program intends to call @@ -3054,4 +3056,7 @@ struct bpf_line_info { __u32 line_col; }; +struct bpf_spin_lock { + __u32 val; +}; #endif /* _UAPI__LINUX_BPF_H__ */ diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c index 25632a75d630..d6d979910a2a 100644 --- a/kernel/bpf/arraymap.c +++ b/kernel/bpf/arraymap.c @@ -270,9 +270,10 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value, memcpy(this_cpu_ptr(array->pptrs[index & array->index_mask]), value, map->value_size); else - memcpy(array->value + - array->elem_size * (index & array->index_mask), - value, map->value_size); + copy_map_value(map, + array->value + + array->elem_size * (index & array->index_mask), + value); return 0; } diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index a2f53642592b..ed5ae2b1f035 100644 --- a/kernel/bpf/btf.c +++ b/kernel/bpf/btf.c @@ -1979,6 +1979,43 @@ static void btf_struct_log(struct btf_verifier_env *env, btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t)); } +/* find 'struct bpf_spin_lock' in map value. + * return >= 0 offset if found + * and < 0 in case of error + */ +int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t) +{ + const struct btf_member *member; + u32 i, off = -ENOENT; + + if (BTF_INFO_KIND(t->info) != BTF_KIND_STRUCT) + return -EINVAL; + + for_each_member(i, t, member) { + const struct btf_type *member_type = btf_type_by_id(btf, + member->type); + if (!btf_type_is_struct(member_type)) + continue; + if (member_type->size != sizeof(struct bpf_spin_lock)) + continue; + if (strcmp(__btf_name_by_offset(btf, member_type->name_off), + "bpf_spin_lock")) + continue; + if (off != -ENOENT) + /* only one 'struct bpf_spin_lock' is allowed */ + return -E2BIG; + off = btf_member_bit_offset(t, member); + if (off % 8) + /* valid C code cannot generate such BTF */ + return -EINVAL; + off /= 8; + if (off % __alignof__(struct bpf_spin_lock)) + /* valid struct bpf_spin_lock will be 4 byte aligned */ + return -EINVAL; + } + return off; +} + static void btf_struct_seq_show(const struct btf *btf, const struct btf_type *t, u32 type_id, void *data, u8 bits_offset, struct seq_file *m) diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c index f908b9356025..497d0c4c123c 100644 --- a/kernel/bpf/core.c +++ b/kernel/bpf/core.c @@ -2036,6 +2036,8 @@ const struct bpf_func_proto bpf_map_delete_elem_proto __weak; const struct bpf_func_proto bpf_map_push_elem_proto __weak; const struct bpf_func_proto bpf_map_pop_elem_proto __weak; const struct bpf_func_proto bpf_map_peek_elem_proto __weak; +const struct bpf_func_proto bpf_spin_lock_proto __weak; +const struct bpf_func_proto bpf_spin_unlock_proto __weak; const struct bpf_func_proto bpf_get_prandom_u32_proto __weak; const struct bpf_func_proto bpf_get_smp_processor_id_proto __weak; diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c index 4b7c76765d9d..48a41bf65e1b 100644 --- a/kernel/bpf/hashtab.c +++ b/kernel/bpf/hashtab.c @@ -770,6 +770,8 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, l_new = ERR_PTR(-ENOMEM); goto dec_count; } + check_and_init_map_lock(&htab->map, + l_new->key + round_up(key_size, 8)); } memcpy(l_new->key, key, key_size); @@ -792,7 +794,9 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, if (!prealloc) htab_elem_set_ptr(l_new, key_size, pptr); } else { - memcpy(l_new->key + round_up(key_size, 8), value, size); + copy_map_value(&htab->map, + l_new->key + round_up(key_size, 8), + value); } l_new->hash = hash; diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index a74972b07e74..591fdedae7bf 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -221,6 +221,41 @@ const struct bpf_func_proto bpf_get_current_comm_proto = { .arg2_type = ARG_CONST_SIZE, }; +BPF_CALL_1(bpf_spin_lock, struct bpf_spin_lock *, lock) +{ +#if defined(CONFIG_SMP) + struct qspinlock *qlock = (void *)lock; + + BUILD_BUG_ON(sizeof(*qlock) != sizeof(*lock)); + queued_spin_lock(qlock); +#endif + return 0; +} + +const struct bpf_func_proto bpf_spin_lock_proto = { + .func = bpf_spin_lock, + .gpl_only = false, + .ret_type = RET_VOID, + .arg1_type = ARG_PTR_TO_SPIN_LOCK, +}; + +BPF_CALL_1(bpf_spin_unlock, struct bpf_spin_lock *, lock) +{ +#if defined(CONFIG_SMP) + struct qspinlock *qlock = (void *)lock; + + queued_spin_unlock(qlock); +#endif + return 0; +} + +const struct bpf_func_proto bpf_spin_unlock_proto = { + .func = bpf_spin_unlock, + .gpl_only = false, + .ret_type = RET_VOID, + .arg1_type = ARG_PTR_TO_SPIN_LOCK, +}; + #ifdef CONFIG_CGROUPS BPF_CALL_0(bpf_get_current_cgroup_id) { diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c index b155cd17c1bd..ebf0a673cb83 100644 --- a/kernel/bpf/syscall.c +++ b/kernel/bpf/syscall.c @@ -463,7 +463,7 @@ int map_check_no_btf(const struct bpf_map *map, return -ENOTSUPP; } -static int map_check_btf(const struct bpf_map *map, const struct btf *btf, +static int map_check_btf(struct bpf_map *map, const struct btf *btf, u32 btf_key_id, u32 btf_value_id) { const struct btf_type *key_type, *value_type; @@ -478,6 +478,21 @@ static int map_check_btf(const struct bpf_map *map, const struct btf *btf, if (!value_type || value_size != map->value_size) return -EINVAL; + map->spin_lock_off = btf_find_spin_lock(btf, value_type); + + if (map_value_has_spin_lock(map)) { + if (map->map_type != BPF_MAP_TYPE_HASH && + map->map_type != BPF_MAP_TYPE_ARRAY) + return -ENOTSUPP; + if (map->spin_lock_off + sizeof(struct bpf_spin_lock) > + map->value_size) { + WARN_ONCE(1, + "verifier bug spin_lock_off %d value_size %d\n", + map->spin_lock_off, map->value_size); + return -EFAULT; + } + } + if (map->ops->map_check_btf) ret = map->ops->map_check_btf(map, btf, key_type, value_type); @@ -542,6 +557,8 @@ static int map_create(union bpf_attr *attr) map->btf = btf; map->btf_key_type_id = attr->btf_key_type_id; map->btf_value_type_id = attr->btf_value_type_id; + } else { + map->spin_lock_off = -EINVAL; } err = security_bpf_map_alloc(map); @@ -740,7 +757,7 @@ static int map_lookup_elem(union bpf_attr *attr) err = -ENOENT; } else { err = 0; - memcpy(value, ptr, value_size); + copy_map_value(map, value, ptr); } rcu_read_unlock(); } diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 56674a7c3778..0f3d1fb30d7a 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -213,6 +213,7 @@ struct bpf_call_arg_meta { s64 msize_smax_value; u64 msize_umax_value; int ptr_id; + int func_id; }; static DEFINE_MUTEX(bpf_verifier_lock); @@ -351,6 +352,12 @@ static bool reg_is_refcounted(const struct bpf_reg_state *reg) return type_is_refcounted(reg->type); } +static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg) +{ + return reg->type == PTR_TO_MAP_VALUE && + map_value_has_spin_lock(reg->map_ptr); +} + static bool reg_is_refcounted_or_null(const struct bpf_reg_state *reg) { return type_is_refcounted_or_null(reg->type); @@ -712,6 +719,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state, } dst_state->speculative = src->speculative; dst_state->curframe = src->curframe; + dst_state->active_spin_lock = src->active_spin_lock; for (i = 0; i <= src->curframe; i++) { dst = dst_state->frame[i]; if (!dst) { @@ -1483,6 +1491,21 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno, if (err) verbose(env, "R%d max value is outside of the array range\n", regno); + + if (map_value_has_spin_lock(reg->map_ptr)) { + u32 lock = reg->map_ptr->spin_lock_off; + + /* if any part of struct bpf_spin_lock can be touched by + * load/store reject this program + */ + if ((reg->smin_value + off <= lock && + lock < reg->umax_value + off + size) || + (reg->smin_value + off < lock + sizeof(struct bpf_spin_lock) && + lock + sizeof(struct bpf_spin_lock) <= reg->umax_value + off + size)) { + verbose(env, "bpf_spin_lock cannot be accessed directly by load/store\n"); + return -EACCES; + } + } return err; } @@ -2192,6 +2215,91 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno, } } +/* Implementation details: + * bpf_map_lookup returns PTR_TO_MAP_VALUE_OR_NULL + * Two bpf_map_lookups (even with the same key) will have different reg->id. + * For traditional PTR_TO_MAP_VALUE the verifier clears reg->id after + * value_or_null->value transition, since the verifier only cares about + * the range of access to valid map value pointer and doesn't care about actual + * address of the map element. + * For maps with 'struct bpf_spin_lock' inside map value the verifier keeps + * reg->id > 0 after value_or_null->value transition. By doing so + * two bpf_map_lookups will be considered two different pointers that + * point to different bpf_spin_locks. + * The verifier allows taking only one bpf_spin_lock at a time to avoid + * dead-locks. + * Since only one bpf_spin_lock is allowed the checks are simpler than + * reg_is_refcounted() logic. The verifier needs to remember only + * one spin_lock instead of array of acquired_refs. + * cur_state->active_spin_lock remembers which map value element got locked + * and clears it after bpf_spin_unlock. + */ +static int process_spin_lock(struct bpf_verifier_env *env, int regno, + bool is_lock) +{ + struct bpf_reg_state *regs = cur_regs(env), *reg = ®s[regno]; + struct bpf_verifier_state *cur = env->cur_state; + bool is_const = tnum_is_const(reg->var_off); + struct bpf_map *map = reg->map_ptr; + u64 val = reg->var_off.value; + + if (reg->type != PTR_TO_MAP_VALUE) { + verbose(env, "R%d is not a pointer to map_value\n", regno); + return -EINVAL; + } + if (!is_const) { + verbose(env, + "R%d doesn't have constant offset. bpf_spin_lock has to be at the constant offset\n", + regno); + return -EINVAL; + } + if (!map->btf) { + verbose(env, + "map '%s' has to have BTF in order to use bpf_spin_lock\n", + map->name); + return -EINVAL; + } + if (!map_value_has_spin_lock(map)) { + if (map->spin_lock_off == -E2BIG) + verbose(env, + "map '%s' has more than one 'struct bpf_spin_lock'\n", + map->name); + else if (map->spin_lock_off == -ENOENT) + verbose(env, + "map '%s' doesn't have 'struct bpf_spin_lock'\n", + map->name); + else + verbose(env, + "map '%s' is not a struct type or bpf_spin_lock is mangled\n", + map->name); + return -EINVAL; + } + if (map->spin_lock_off != val + reg->off) { + verbose(env, "off %lld doesn't point to 'struct bpf_spin_lock'\n", + val + reg->off); + return -EINVAL; + } + if (is_lock) { + if (cur->active_spin_lock) { + verbose(env, + "Locking two bpf_spin_locks are not allowed\n"); + return -EINVAL; + } + cur->active_spin_lock = reg->id; + } else { + if (!cur->active_spin_lock) { + verbose(env, "bpf_spin_unlock without taking a lock\n"); + return -EINVAL; + } + if (cur->active_spin_lock != reg->id) { + verbose(env, "bpf_spin_unlock of different lock\n"); + return -EINVAL; + } + cur->active_spin_lock = 0; + } + return 0; +} + static bool arg_type_is_mem_ptr(enum bpf_arg_type type) { return type == ARG_PTR_TO_MEM || @@ -2268,6 +2376,17 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno, return -EFAULT; } meta->ptr_id = reg->id; + } else if (arg_type == ARG_PTR_TO_SPIN_LOCK) { + if (meta->func_id == BPF_FUNC_spin_lock) { + if (process_spin_lock(env, regno, true)) + return -EACCES; + } else if (meta->func_id == BPF_FUNC_spin_unlock) { + if (process_spin_lock(env, regno, false)) + return -EACCES; + } else { + verbose(env, "verifier internal error\n"); + return -EFAULT; + } } else if (arg_type_is_mem_ptr(arg_type)) { expected_type = PTR_TO_STACK; /* One exception here. In case function allows for NULL to be @@ -2887,6 +3006,7 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn return err; } + meta.func_id = func_id; /* check args */ err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta); if (err) @@ -4344,7 +4464,8 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state, } else if (reg->type == PTR_TO_SOCKET_OR_NULL) { reg->type = PTR_TO_SOCKET; } - if (is_null || !reg_is_refcounted(reg)) { + if (is_null || !(reg_is_refcounted(reg) || + reg_may_point_to_spin_lock(reg))) { /* We don't need id from this point onwards anymore, * thus we should better reset it, so that state * pruning has chances to take effect. @@ -5651,6 +5772,9 @@ static bool states_equal(struct bpf_verifier_env *env, if (old->speculative && !cur->speculative) return false; + if (old->active_spin_lock != cur->active_spin_lock) + return false; + /* for states to be equal callsites have to be the same * and all frame states need to be equivalent */ @@ -6068,6 +6192,12 @@ static int do_check(struct bpf_verifier_env *env) return -EINVAL; } + if (env->cur_state->active_spin_lock && + (insn->src_reg == BPF_PSEUDO_CALL || + insn->imm != BPF_FUNC_spin_unlock)) { + verbose(env, "function calls are not allowed while holding a lock\n"); + return -EINVAL; + } if (insn->src_reg == BPF_PSEUDO_CALL) err = check_func_call(env, insn, &env->insn_idx); else @@ -6096,6 +6226,11 @@ static int do_check(struct bpf_verifier_env *env) return -EINVAL; } + if (env->cur_state->active_spin_lock) { + verbose(env, "bpf_spin_unlock is missing\n"); + return -EINVAL; + } + if (state->curframe) { /* exit from nested function */ env->prev_insn_idx = env->insn_idx; diff --git a/net/core/filter.c b/net/core/filter.c index 2b3b436ef545..24a5d874d156 100644 --- a/net/core/filter.c +++ b/net/core/filter.c @@ -5306,10 +5306,20 @@ bpf_base_func_proto(enum bpf_func_id func_id) return &bpf_tail_call_proto; case BPF_FUNC_ktime_get_ns: return &bpf_ktime_get_ns_proto; + default: + break; + } + + if (!capable(CAP_SYS_ADMIN)) + return NULL; + + switch (func_id) { + case BPF_FUNC_spin_lock: + return &bpf_spin_lock_proto; + case BPF_FUNC_spin_unlock: + return &bpf_spin_unlock_proto; case BPF_FUNC_trace_printk: - if (capable(CAP_SYS_ADMIN)) - return bpf_get_trace_printk_proto(); - /* else: fall through */ + return bpf_get_trace_printk_proto(); default: return NULL; }
Introduce 'struct bpf_spin_lock' and bpf_spin_lock/unlock() helpers to let bpf program serialize access to other variables. Example: struct hash_elem { int cnt; struct bpf_spin_lock lock; }; struct hash_elem * val = bpf_map_lookup_elem(&hash_map, &key); if (val) { bpf_spin_lock(&val->lock); val->cnt++; bpf_spin_unlock(&val->lock); } Restrictions and safety checks: - bpf_spin_lock is only allowed inside HASH and ARRAY maps. - BTF description of the map is mandatory for safety analysis. - bpf program can take one bpf_spin_lock at a time, since two or more can cause dead locks. - only one 'struct bpf_spin_lock' is allowed per map element. It drastically simplifies implementation yet allows bpf program to use any number of bpf_spin_locks. - when bpf_spin_lock is taken the calls (either bpf2bpf or helpers) are not allowed. - bpf program must bpf_spin_unlock() before return. - bpf program can access 'struct bpf_spin_lock' only via bpf_spin_lock()/bpf_spin_unlock() helpers. - load/store into 'struct bpf_spin_lock lock;' field is not allowed. - to use bpf_spin_lock() helper the BTF description of map value must be a struct and have 'struct bpf_spin_lock anyname;' field at the top level. Nested lock inside another struct is not allowed. - syscall map_lookup doesn't copy bpf_spin_lock field to user space. - syscall map_update and program map_update do not update bpf_spin_lock field. - bpf_spin_lock cannot be on the stack or inside networking packet. bpf_spin_lock can only be inside HASH or ARRAY map value. - bpf_spin_lock is available to root only and to all program types. Implementation details: - on !SMP bpf_spin_lock() becomes nop - presence of bpf_spin_lock inside map value could have been indicated via extra flag during map_create, but specifying it via BTF is cleaner. It provides introspection for map key/value and reduces user coding mistakes. Next steps: - allow bpf_spin_lock in other map types (like cgroup local storage) - introduce BPF_F_LOCK flag for bpf_map_update() syscall and helper to request kernel to grab bpf_spin_lock before rewriting the value. That will serialize access to map elements. Signed-off-by: Alexei Starovoitov <ast@kernel.org> --- include/linux/bpf.h | 37 +++++++++- include/linux/bpf_verifier.h | 1 + include/linux/btf.h | 1 + include/uapi/linux/bpf.h | 7 +- kernel/bpf/arraymap.c | 7 +- kernel/bpf/btf.c | 37 ++++++++++ kernel/bpf/core.c | 2 + kernel/bpf/hashtab.c | 6 +- kernel/bpf/helpers.c | 35 +++++++++ kernel/bpf/syscall.c | 21 +++++- kernel/bpf/verifier.c | 137 ++++++++++++++++++++++++++++++++++- net/core/filter.c | 16 +++- 12 files changed, 293 insertions(+), 14 deletions(-)