introduce bpf_spin_lock
Subsystems (8)
Alexei Starovoitov
maintainerPATCH v4 5/9 selftests/bpf: add bpf_spin_lock C test
In reply to Alexei Starovoitovadd bpf_spin_lock C based test that requires latest llvm with BTF support
--- tools/testing/selftests/bpf/Makefile | 2 +- tools/testing/selftests/bpf/bpf_helpers.h | 4 + tools/testing/selftests/bpf/test_progs.c | 43 +++++++- tools/testing/selftests/bpf/test_spin_lock.c | 108 +++++++++++++++++++ 4 files changed, 155 insertions(+), 2 deletions(-) create mode 100644 tools/testing/selftests/bpf/test_spin_lock.c
tools/testing/selftests/bpf/Makefile +1 -1
@@ -39,7 +39,7 @@ TEST_GEN_FILES = test_pkt_access.o test_xdp.o test_l4lb.o test_tcp_estats.o test get_cgroup_id_kern.o socket_cookie_prog.o test_select_reuseport_kern.o \ test_skb_cgroup_id_kern.o bpf_flow.o netcnt_prog.o \ test_sk_lookup_kern.o test_xdp_vlan.o test_queue_map.o test_stack_map.o \ - xdp_dummy.o test_map_in_map.o + xdp_dummy.o test_map_in_map.o test_spin_lock.o # Order correspond to 'make run_tests' order TEST_PROGS := test_kmod.sh \
tools/testing/selftests/bpf/bpf_helpers.h +4 -0
@@ -172,6 +172,10 @@ static int (*bpf_skb_vlan_pop)(void *ctx) = (void *) BPF_FUNC_skb_vlan_pop;static int (*bpf_rc_pointer_rel)(void *ctx,int rel_x,int rel_y) = (void *) BPF_FUNC_rc_pointer_rel; +static void (*bpf_spin_lock)(struct bpf_spin_lock *lock) = + (void *) BPF_FUNC_spin_lock; +static void (*bpf_spin_unlock)(struct bpf_spin_lock *lock) = + (void *) BPF_FUNC_spin_unlock;/* llvm builtin functions that eBPF C program may use to * emit BPF_LD_ABS and BPF_LD_IND instructions
tools/testing/selftests/bpf/test_progs.c +42 -1
61 lines not on this page · raw message
tools/testing/selftests/bpf/test_spin_lock.c new file +108 -0
108 lines not on this page · raw message
Signature · 1 line
2.17.1
Alexei Starovoitov
maintainerPATCH v4 3/9 tools/bpf: sync include/uapi/linux/bpf.h
In reply to Alexei Starovoitovsync bpf.h
--- tools/include/uapi/linux/bpf.h | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-)
tools/include/uapi/linux/bpf.h +6 -1
@@ -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__ */
Signature · 1 line
2.17.1
Alexei Starovoitov
maintainerPATCH v4 7/9 tools/bpf: sync uapi/bpf.h
In reply to Alexei Starovoitovadd BPF_F_LOCK definition to tools/include/uapi/linux/bpf.h
--- tools/include/uapi/linux/bpf.h | 1 + 1 file changed, 1 insertion(+)
tools/include/uapi/linux/bpf.h +1 -0
@@ -266,6 +266,7 @@ enum bpf_attach_type {#define BPF_ANY 0/* create new element or update existing */ #define BPF_NOEXIST 1/* create new element if it didn't exist */ #define BPF_EXIST 2/* update existing element */ +#define BPF_F_LOCK 4/* spin_lock-ed map_lookup/map_update */ /* flags for BPF_MAP_CREATE command */ #define BPF_F_NO_PREALLOC (1U << 0)
Signature · 1 line
2.17.1
Alexei Starovoitov
maintainerPATCH v4 1/9 bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovIntroduce '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.
- bpf_spin_lock is not allowed in inner maps of map-in-map.
- ld_abs is not allowed inside spin_lock-ed region.
Implementation details:
- on !SMP bpf_spin_lock() becomes nop
- on architectures that don't support queued_spin_lock trivial lock is used. Note that arch_spin_lock cannot be used, since not all archs agree that zero == unlocked and sizeof(arch_spinlock_t) != sizeof(__u32).
- 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.
--- 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 | 42 ++++++++++ kernel/bpf/core.c | 2 + kernel/bpf/hashtab.c | 6 +- kernel/bpf/helpers.c | 57 ++++++++++++++ kernel/bpf/map_in_map.c | 5 ++ kernel/bpf/syscall.c | 21 ++++- kernel/bpf/verifier.c | 149 ++++++++++++++++++++++++++++++++++- net/core/filter.c | 16 +++- 13 files changed, 335 insertions(+), 16 deletions(-)
include/linux/bpf.h +34 -3
@@ -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 */
@@ -876,7 +906,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. */
include/linux/bpf_verifier.h +1 -0
@@ -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; };
include/linux/btf.h +1 -0
@@ -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);
include/uapi/linux/bpf.h +6 -1
@@ -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__ */
kernel/bpf/arraymap.c +4 -3
@@ -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 ; }
kernel/bpf/btf.c +42 -0
54 lines not on this page · raw message
kernel/bpf/core.c +2 -0
@@ -2050,6 +2050,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 ;
kernel/bpf/hashtab.c +5 -1
@@ -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;
kernel/bpf/helpers.c +57 -0
63 lines not on this page · raw message
kernel/bpf/map_in_map.c +5 -0
@@ -36,6 +36,11 @@ struct bpf_map *bpf_map_meta_alloc(int inner_map_ufd)return ERR_PTR (-EINVAL ); } +if (map_value_has_spin_lock (inner_map)) { +fdput (f); +return ERR_PTR (-ENOTSUPP ); + } + inner_map_meta =kzalloc (sizeof (*inner_map_meta),GFP_USER );if (!inner_map_meta) {fdput (f);
kernel/bpf/syscall.c +19 -2
@@ -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 (); }
kernel/bpf/verifier.c +146 -3
227 lines not on this page · raw message
net/core/filter.c +13 -3
@@ -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 ; }
Signature · 1 line
2.17.1
Alexei Starovoitov
maintainerPATCH v4 2/9 bpf: add support for bpf_spin_lock to cgroup local storage
In reply to Alexei StarovoitovAllow 'struct bpf_spin_lock' to reside inside cgroup local storage.
--- kernel/bpf/local_storage.c | 2 ++ kernel/bpf/syscall.c | 3 ++- kernel/bpf/verifier.c | 2 ++ 3 files changed, 6 insertions(+), 1 deletion(-)
kernel/bpf/local_storage.c +2 -0
@@ -147,6 +147,7 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,return -ENOMEM ;memcpy (&new->data[0 ], value, map->value_size); +check_and_init_map_lock (map, new->data); new =xchg (&storage->buf, new);kfree_rcu (new, rcu);
@@ -483,6 +484,7 @@ struct bpf_cgroup_storage *bpf_cgroup_storage_alloc(struct bpf_prog *prog, storage->buf =kmalloc_node (size, flags, map->numa_node);if (!storage->buf) goto enomem; +check_and_init_map_lock (map, storage->buf->data); }else { storage->percpu_buf =__alloc_percpu_gfp (size,8 , flags);if (!storage->percpu_buf)
kernel/bpf/syscall.c +2 -1
@@ -482,7 +482,8 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,if (map_value_has_spin_lock (map)) {if (map->map_type !=BPF_MAP_TYPE_HASH && - map->map_type !=BPF_MAP_TYPE_ARRAY ) + map->map_type !=BPF_MAP_TYPE_ARRAY && + map->map_type !=BPF_MAP_TYPE_CGROUP_STORAGE )return -ENOTSUPP ;if (map->spin_lock_off +sizeof (struct bpf_spin_lock ) > map->value_size) {
kernel/bpf/verifier.c +2 -0
@@ -3089,6 +3089,8 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn regs[BPF_REG_0 ].map_ptr = meta.map_ptr;if (fn->ret_type ==RET_PTR_TO_MAP_VALUE ) { regs[BPF_REG_0 ].type =PTR_TO_MAP_VALUE ; +if (map_value_has_spin_lock (meta.map_ptr)) + regs[BPF_REG_0 ].id = ++env->id_gen; }else { regs[BPF_REG_0 ].type =PTR_TO_MAP_VALUE_OR_NULL ; regs[BPF_REG_0 ].id = ++env->id_gen;
Signature · 1 line
2.17.1
Alexei Starovoitov
maintainerPATCH v4 6/9 bpf: introduce BPF_F_LOCK flag
In reply to Alexei StarovoitovIntroduce BPF_F_LOCK flag for map_lookup and map_update syscall commands and for map_update() helper function.
In all these cases take a lock of existing element (which was provided in BTF description) before copying (in or out) the rest of map value.
Implementation details that are part of uapi:
Array:
The array map takes the element lock for lookup/update.
Hash:
hash map also takes the lock for lookup/update and tries to avoid the bucket lock. If old element exists it takes the element lock and updates the element in place. If element doesn't exist it allocates new one and inserts into hash table while holding the bucket lock.
In rare case the hashmap has to take both the bucket lock and the element lock to update old value in place.
Cgroup local storage:
It is similar to array. update in place and lookup are done with lock taken.
--- include/linux/bpf.h | 2 ++ include/uapi/linux/bpf.h | 1 + kernel/bpf/arraymap.c | 24 ++++++++++++++-------- kernel/bpf/hashtab.c | 42 +++++++++++++++++++++++++++++++++++--- kernel/bpf/helpers.c | 14 +++++++++++++ kernel/bpf/local_storage.c | 14 ++++++++++++- kernel/bpf/syscall.c | 25 +++++++++++++++++++++-- 7 files changed, 108 insertions(+), 14 deletions(-)
include/linux/bpf.h +2 -0
@@ -119,6 +119,8 @@ static inline void copy_map_value(struct bpf_map *map, void *dst, void *src)memcpy (dst, src, map->value_size); } } +void copy_map_value_locked (struct bpf_map *map,void *dst,void *src, +bool lock_src);struct bpf_offload_dev ;struct bpf_offloaded_map ;
include/uapi/linux/bpf.h +1 -0
@@ -266,6 +266,7 @@ enum bpf_attach_type {#define BPF_ANY 0/* create new element or update existing */ #define BPF_NOEXIST 1/* create new element if it didn't exist */ #define BPF_EXIST 2/* update existing element */ +#define BPF_F_LOCK 4/* spin_lock-ed map_lookup/map_update */ /* flags for BPF_MAP_CREATE command */ #define BPF_F_NO_PREALLOC (1U << 0)
kernel/bpf/arraymap.c +16 -8
@@ -253,8 +253,9 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value, { struct bpf_array *array = container_of(map, struct bpf_array, map);u32 index = *(u32 *)key; +char *val; -if (unlikely (map_flags >BPF_EXIST )) +if (unlikely ((map_flags & ~BPF_F_LOCK ) >BPF_EXIST ))/* unknown flags */ return -EINVAL ;
@@ -262,18 +263,25 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,/* all elements were pre-allocated, cannot insert a new one */ return -E2BIG ; -if (unlikely (map_flags ==BPF_NOEXIST )) +if (unlikely (map_flags &BPF_NOEXIST ))/* all elements already exist */ return -EEXIST ; -if (array->map.map_type ==BPF_MAP_TYPE_PERCPU_ARRAY ) +if (unlikely ((map_flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map))) +return -EINVAL ; + +if (array->map.map_type ==BPF_MAP_TYPE_PERCPU_ARRAY ) {memcpy (this_cpu_ptr (array->pptrs[index & array->index_mask]), value, map->value_size); -else -copy_map_value (map, - array->value + - array->elem_size * (index & array->index_mask), - value); + }else { + val = array->value + + array->elem_size * (index & array->index_mask); +if (map_flags &BPF_F_LOCK ) +copy_map_value_locked (map, val, value, false); +else +copy_map_value (map, val, value); + }return 0 ; }
kernel/bpf/hashtab.c +39 -3
69 lines not on this page · raw message
kernel/bpf/helpers.c +14 -0
@@ -278,6 +278,20 @@ const struct bpf_func_proto bpf_spin_unlock_proto = { .arg1_type = ARG_PTR_TO_SPIN_LOCK, }; +void copy_map_value_locked (struct bpf_map *map,void *dst,void *src, +bool lock_src) +{ +struct bpf_spin_lock *lock; + +if (lock_src) + lock = src + map->spin_lock_off; +else + lock = dst + map->spin_lock_off; +____bpf_spin_lock (lock); +copy_map_value (map, dst, src); +____bpf_spin_unlock (lock); +} +#ifdef CONFIG_CGROUPS BPF_CALL_0 (bpf_get_current_cgroup_id) {
kernel/bpf/local_storage.c +13 -1
@@ -131,7 +131,14 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,struct bpf_cgroup_storage *storage;struct bpf_storage_buffer *new; -if (flags !=BPF_ANY && flags !=BPF_EXIST ) +if (unlikely (flags & ~(BPF_F_LOCK |BPF_EXIST |BPF_NOEXIST ))) +return -EINVAL ; + +if (unlikely (flags &BPF_NOEXIST )) +return -EINVAL ; + +if (unlikely ((flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)))return -EINVAL ; storage = cgroup_storage_lookup((struct bpf_cgroup_storage_map *)map,
@@ -139,6 +146,11 @@ static int cgroup_storage_update_elem(struct bpf_map *map, void *_key,if (!storage)return -ENOENT ; +if (flags &BPF_F_LOCK ) { +copy_map_value_locked (map, storage->buf->data, value, false); +return 0 ; + } + new = kmalloc_node(sizeof(struct bpf_storage_buffer) + map->value_size, __GFP_ZERO | GFP_ATOMIC | __GFP_NOWARN,
kernel/bpf/syscall.c +23 -2
@@ -682,7 +682,7 @@ static void *__bpf_copy_key(void __user *ukey, u64 key_size) }/* last field in 'union bpf_attr' used by this command */ -#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD value +#define BPF_MAP_LOOKUP_ELEM_LAST_FIELD flagsstatic int map_lookup_elem (union bpf_attr *attr) {
@@ -698,6 +698,9 @@ static int map_lookup_elem(union bpf_attr *attr)if (CHECK_ATTR (BPF_MAP_LOOKUP_ELEM ))return -EINVAL ; +if (attr->flags & ~BPF_F_LOCK ) +return -EINVAL ; + f =fdget (ufd); map =__bpf_map_get (f);if (IS_ERR (map))
@@ -708,6 +711,12 @@ static int map_lookup_elem(union bpf_attr *attr) goto err_put; } +if ((attr->flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)) { + err = -EINVAL ; + goto err_put; + } + key =__bpf_copy_key (ukey, map->key_size);if (IS_ERR (key)) { err =PTR_ERR (key);
@@ -758,7 +767,13 @@ static int map_lookup_elem(union bpf_attr *attr) err = -ENOENT ; }else { err =0 ; -copy_map_value (map, value, ptr); +if (attr->flags &BPF_F_LOCK ) +/* lock 'ptr' and copy everything but lock */ +copy_map_value_locked (map, value, ptr, true); +else +copy_map_value (map, value, ptr); +/* mask lock, since value wasn't zero inited */ +check_and_init_map_lock (map, value); }rcu_read_unlock (); }
@@ -818,6 +833,12 @@ static int map_update_elem(union bpf_attr *attr) goto err_put; } +if ((attr->flags &BPF_F_LOCK ) && + !map_value_has_spin_lock (map)) { + err = -EINVAL ; + goto err_put; + } + key =__bpf_copy_key (ukey, map->key_size);if (IS_ERR (key)) { err =PTR_ERR (key);
Signature · 1 line
2.17.1
Alexei Starovoitov
maintainerv4 cover introduce bpf_spin_lock
Many algorithms need to read and modify several variables atomically. Until now it was hard to impossible to implement such algorithms in BPF. Hence introduce support for bpf_spin_lock.
The api consists of 'struct bpf_spin_lock' that should be placed inside hash/array/cgroup_local_storage element
and bpf_spin_lock/unlock() helper function.
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);
}and BPF_F_LOCK flag for lookup/update bpf syscall commands that allows user space to read/write map elements under lock.
Together these primitives allow race free access to map elements from bpf programs and from user space.
Key restriction: root only.
Key requirement: maps must be annotated with BTF.
This concept was discussed at Linux Plumbers Conference 2018. Thank you everyone who participated and helped to iron out details of api and implementation.
Patch 1: bpf_spin_lock support in the verifier, BTF, hash, array. Patch 2: bpf_spin_lock in cgroup local storage.
Patches 3,4,5: tests
Patch 6: BPF_F_LOCK flag to lookup/update
Patches 7,8,9: tests
v3->v4:
- fix BPF_EXIST | BPF_NOEXIST check patch 6. Spotted by Jakub. Thanks!
- rebase
v2->v3:
- fixed build on ia64 and archs where qspinlock is not supported
- fixed missing lock init during lookup w/o BPF_F_LOCK. Spotted by Martin
v1->v2:
- addressed several issues spotted by Daniel and Martin in patch 1
- added test11 to patch 4 as suggested by Daniel
Alexei Starovoitov (9):
bpf: introduce bpf_spin_lock
bpf: add support for bpf_spin_lock to cgroup local storage tools/bpf: sync include/uapi/linux/bpf.h selftests/bpf: add bpf_spin_lock tests selftests/bpf: add bpf_spin_lock C test
bpf: introduce BPF_F_LOCK flag
tools/bpf: sync uapi/bpf.h
libbpf: introduce bpf_map_lookup_elem_flags() selftests/bpf: test for BPF_F_LOCK
include/linux/bpf.h | 39 +- include/linux/bpf_verifier.h | 1 + include/linux/btf.h | 1 + include/uapi/linux/bpf.h | 8 +- kernel/bpf/arraymap.c | 23 +- kernel/bpf/btf.c | 42 ++ kernel/bpf/core.c | 2 + kernel/bpf/hashtab.c | 48 +- kernel/bpf/helpers.c | 71 +++ kernel/bpf/local_storage.c | 16 +- kernel/bpf/map_in_map.c | 5 + kernel/bpf/syscall.c | 45 +- kernel/bpf/verifier.c | 151 +++++- net/core/filter.c | 16 +- tools/include/uapi/linux/bpf.h | 8 +- tools/lib/bpf/bpf.c | 13 + tools/lib/bpf/bpf.h | 2 + tools/lib/bpf/libbpf.map | 1 + tools/testing/selftests/bpf/Makefile | 2 +- tools/testing/selftests/bpf/bpf_helpers.h | 4 + tools/testing/selftests/bpf/test_map_lock.c | 66 +++ tools/testing/selftests/bpf/test_progs.c | 117 ++++- tools/testing/selftests/bpf/test_spin_lock.c | 108 +++++ tools/testing/selftests/bpf/test_verifier.c | 459 ++++++++++++++++++- 24 files changed, 1219 insertions(+), 29 deletions(-) create mode 100644 tools/testing/selftests/bpf/test_map_lock.c create mode 100644 tools/testing/selftests/bpf/test_spin_lock.c
Signature · 1 line
2.17.1
Alexei Starovoitov
maintainerPATCH v4 4/9 selftests/bpf: add bpf_spin_lock tests
add bpf_spin_lock tests to test_verifier.c that don't require latest llvm with BTF support
--- tools/testing/selftests/bpf/test_verifier.c | 459 +++++++++++++++++++- 1 file changed, 458 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/test_verifier.c +458 -1
@@ -32,6 +32,7 @@#include <linux/bpf_perf_event.h> #include <linux/bpf.h> #include <linux/if_ether.h> +#include <linux/btf.h> #include <bpf/bpf.h>
@@ -49,7 +50,7 @@#define MAX_INSNS BPF_MAXINSNS#define MAX_FIXUPS 8 -#define MAX_NR_MAPS 13 +#define MAX_NR_MAPS 14#define MAX_TEST_RUNS 8#define POINTER_VALUE 0xcafe4all#define TEST_DATA_LEN 64
@@ -76,6 +77,7 @@ struct bpf_test {int fixup_map_in_map[MAX_FIXUPS ];int fixup_cgroup_storage[MAX_FIXUPS ];int fixup_percpu_cgroup_storage[MAX_FIXUPS ]; +int fixup_map_spin_lock[MAX_FIXUPS ];const char *errstr;const char *errstr_unpriv;uint32_t retval, retval_unpriv, insn_processed;
@@ -15759,6 +15761,361 @@ static struct bpf_test tests[] = { .result = ACCEPT, .retval = 2, }, + { + "spin_lock: test1 success", + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_6 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = ACCEPT, + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test2 direct ld/st" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "cannot be accessed directly", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test3 direct ld/st" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_6 ,1 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "cannot be accessed directly", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test4 direct ld/st" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_LDX_MEM (BPF_H ,BPF_REG_0 ,BPF_REG_6 ,3 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "cannot be accessed directly", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test5 call within a locked region" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_get_prandom_u32), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "calls are not allowed", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test6 missing unlock" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_6 ,0 ), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "unlock is missing", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test7 unlock without lock" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_1 ,0 ,1 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_6 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "without taking a lock", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test8 double lock" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_6 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "calls are not allowed", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test9 different lock" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_7 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3, 11 }, + .result = REJECT, + .errstr = "unlock of different lock", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test10 lock in subprog without unlock" , + .insns = { +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,1 ,0 ,5 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_6 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), +BPF_EXIT_INSN (), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 3 }, + .result = REJECT, + .errstr = "unlock is missing", + .result_unpriv = REJECT, + .errstr_unpriv = "", + .prog_type = BPF_PROG_TYPE_CGROUP_SKB, + }, + { +"spin_lock: test11 ld_abs under lock" , + .insns = { +BPF_MOV64_REG (BPF_REG_6 ,BPF_REG_1 ), +BPF_ST_MEM (BPF_W ,BPF_REG_10 ,-4 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-4 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JNE ,BPF_REG_0 ,0 ,1 ), +BPF_EXIT_INSN (), +BPF_MOV64_REG (BPF_REG_7 ,BPF_REG_0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_lock), +BPF_LD_ABS (BPF_B ,0 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_7 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_1 ,4 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , + BPF_FUNC_spin_unlock), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_spin_lock = { 4 }, + .result = REJECT, + .errstr = "inside bpf_spin_lock", + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + }, };static int probe_filter_length (const struct bpf_insn *fp)
@@ -15889,6 +16246,98 @@ static int create_cgroup_storage(bool percpu)return fd; } +#define BTF_INFO_ENC (kind, kind_flag, vlen) \ + ((!!(kind_flag) << 31) | ((kind) << 24) | ((vlen) & BTF_MAX_VLEN)) +#define BTF_TYPE_ENC (name, info, size_or_type) \ + (name), (info), (size_or_type) +#define BTF_INT_ENC (encoding, bits_offset, nr_bits) \ + ((encoding) << 24 | (bits_offset) << 16 | (nr_bits)) +#define BTF_TYPE_INT_ENC (name, encoding, bits_offset, bits, sz) \ + BTF_TYPE_ENC(name, BTF_INFO_ENC(BTF_KIND_INT, 0, 0), sz), \ + BTF_INT_ENC(encoding, bits_offset, bits) +#define BTF_MEMBER_ENC (name, type, bits_offset) \ + (name), (type), (bits_offset) + +struct btf_raw_data { +__u32 raw_types[64 ]; +const char *str_sec; +__u32 str_sec_size; +}; + +/* struct bpf_spin_lock { +* int val; +* }; +* struct val { +* int cnt; +* struct bpf_spin_lock l; +* }; +*/ +static const char btf_str_sec[] ="\0bpf_spin_lock\0val\0cnt\0l" ; +static __u32 btf_raw_types[] = { +/* int */ +BTF_TYPE_INT_ENC (0 ,BTF_INT_SIGNED ,0 ,32 ,4 ),/* [1] */ +/* struct bpf_spin_lock */ /* [2] */ +BTF_TYPE_ENC (1 ,BTF_INFO_ENC (BTF_KIND_STRUCT ,0 ,1 ),4 ), +BTF_MEMBER_ENC (15 ,1 ,0 ),/* int val; */ +/* struct val */ /* [3] */ +BTF_TYPE_ENC (15 ,BTF_INFO_ENC (BTF_KIND_STRUCT ,0 ,2 ),8 ), +BTF_MEMBER_ENC (19 ,1 ,0 ),/* int cnt; */ +BTF_MEMBER_ENC (23 ,2 ,32 ),/* struct bpf_spin_lock l; */ +}; + +static int load_btf (void ) +{ +struct btf_header hdr = { + .magic =BTF_MAGIC , + .version =BTF_VERSION , + .hdr_len =sizeof (struct btf_header ), + .type_len =sizeof (btf_raw_types), + .str_off =sizeof (btf_raw_types), + .str_len =sizeof (btf_str_sec), + }; +void *ptr, *raw_btf; +int btf_fd; + + ptr = raw_btf =malloc (sizeof (hdr) +sizeof (btf_raw_types) + +sizeof (btf_str_sec)); + +memcpy (ptr, &hdr,sizeof (hdr)); + ptr +=sizeof (hdr); +memcpy (ptr, btf_raw_types, hdr.type_len); + ptr += hdr.type_len; +memcpy (ptr, btf_str_sec, hdr.str_len); + ptr += hdr.str_len; + + btf_fd =bpf_load_btf (raw_btf, ptr - raw_btf,0 ,0 ,0 ); +free (raw_btf); +if (btf_fd <0 ) +return -1 ; +return btf_fd; +} + +static int create_map_spin_lock (void ) +{ +struct bpf_create_map_attr attr = { + .name ="test_map" , + .map_type =BPF_MAP_TYPE_ARRAY , + .key_size =4 , + .value_size =8 , + .max_entries =1 , + .btf_key_type_id =1 , + .btf_value_type_id =3 , + }; +int fd, btf_fd; + + btf_fd =load_btf (); +if (btf_fd <0 ) +return -1 ; + attr.btf_fd = btf_fd; + fd =bpf_create_map_xattr (&attr); +if (fd <0 ) +printf ("Failed to create map with spin_lock\n" ); +return fd; +} +static char bpf_vlog[UINT_MAX >>8 ]; static void do_test_fixup(struct bpf_test *test, enum bpf_prog_type prog_type,
@@ -15907,6 +16356,7 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_prog_type prog_type,int *fixup_map_in_map = test->fixup_map_in_map;int *fixup_cgroup_storage = test->fixup_cgroup_storage;int *fixup_percpu_cgroup_storage = test->fixup_percpu_cgroup_storage; +int *fixup_map_spin_lock = test->fixup_map_spin_lock;if (test->fill_helper) test->fill_helper (test);
@@ -16023,6 +16473,13 @@ static void do_test_fixup(struct bpf_test *test, enum bpf_prog_type prog_type, fixup_map_stacktrace++; }while (*fixup_map_stacktrace); } +if (*fixup_map_spin_lock) { + map_fds[13 ] =create_map_spin_lock (); +do { + prog[*fixup_map_spin_lock].imm = map_fds[13 ]; + fixup_map_spin_lock++; + }while (*fixup_map_spin_lock); + } }static int set_admin (bool admin)
Signature · 1 line
2.17.1
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovThanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nop
Because no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the BPF_RUN_PROG things are under rcu_read_lock() only, which is not sufficient.
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).
I really don't much like direct usage of qspinlock; esp. not as a surprise.
Why does it matter if 0 means unlocked; that's what __ARCH_SPIN_LOCK_UNLOCKED is for.
I get the sizeof(__u32) thing, but why not key off of that?
Quoted 5 lines
Next steps:
- allowbpf_spin_lockin other map types (like cgroup local storage)
- introduceBPF_F_LOCKflag forbpf_map_update()syscall and helper to request kernel to grabbpf_spin_lockbefore rewriting the value. That will serialize access to map elements.
So clearly this map stuff is shared between bpf proglets, otherwise there would not be a need for locking. But what happens if one is from task context and another from IRQ context?
I don't see a local_irq_save()/restore() anywhere. What avoids the trivial lock inversion?
Quoted 43 lines
kernel/bpf/helpers.c +35
-0@@ -221,6 +221,63 @@ const struct bpf_func_proto bpf_get_current_comm_proto = { .arg2_type = ARG_CONST_SIZE, }; +#ifndef CONFIG_QUEUED_SPINLOCKS +struct dumb_spin_lock { +atomic_t val; +}; +#endif + +notrace BPF_CALL_1 (bpf_spin_lock ,struct bpf_spin_lock *,lock ) +{ +#if defined(CONFIG_SMP ) +#ifdef CONFIG_QUEUED_SPINLOCKS +struct qspinlock *qlock = (void *)lock; + +BUILD_BUG_ON (sizeof (*qlock) !=sizeof (*lock)); +queued_spin_lock (qlock); +#else +struct dumb_spin_lock *qlock = (void *)lock; + +BUILD_BUG_ON (sizeof (*qlock) !=sizeof (*lock)); +do { +while (atomic_read (&qlock->val) !=0 ) +cpu_relax (); + }while (atomic_cmpxchg (&qlock->val,0 ,1 ) !=0 ); +#endif +#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 , +}; + +notrace BPF_CALL_1 (bpf_spin_unlock ,struct bpf_spin_lock *,lock )
kernel/bpf/helpers.c const struct bpf_func_proto bpf_get_current_comm_proto = { · line 268
Quoted 10 lines
kernel/bpf/helpers.c +10
-0+{ +#if defined(CONFIG_SMP ) +#ifdef CONFIG_QUEUED_SPINLOCKS +struct qspinlock *qlock = (void *)lock; + +queued_spin_unlock (qlock); +#else +struct dumb_spin_lock *qlock = (void *)lock; + +atomic_set (&qlock->val,0 );
And this is broken... That should've been atomic_set_release() at the very least.
And this would again be the moment where I go pester you about the BPF memory model :-)
Quoted 11 lines
kernel/bpf/helpers.c +11
-0+#endif +#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 , +};
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 32 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Why does it matter if 0 means unlocked; that's what
__ARCH_SPIN_LOCK_UNLOCKEDis for.I get the
sizeof(__u32)thing, but why not key off of that?Quoted 5 lines
Next steps:
- allowbpf_spin_lockin other map types (like cgroup local storage)
- introduceBPF_F_LOCKflag forbpf_map_update()syscall and helper to request kernel to grabbpf_spin_lockbefore rewriting the value. That will serialize access to map elements.
Quoted 7 lines
So clearly this map stuff is shared between bpf proglets, otherwise there would not be a need for locking. But what happens if one is from task context and another from IRQ context?
I don't see a local_irq_save()/restore() anywhere. What avoids the trivial lock inversion?
Also; what about BPF running from NMI context and using locks?
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.
Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.
One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Thanx, Paul
Quoted 20 lines
Quoted 11 lines
Why does it matter if 0 means unlocked; that's what
__ARCH_SPIN_LOCK_UNLOCKEDis for.I get the
sizeof(__u32)thing, but why not key off of that?Quoted 5 lines
Next steps:
- allowbpf_spin_lockin other map types (like cgroup local storage)
- introduceBPF_F_LOCKflag forbpf_map_update()syscall and helper to request kernel to grabbpf_spin_lockbefore rewriting the value. That will serialize access to map elements.Quoted 6 lines
So clearly this map stuff is shared between bpf proglets, otherwise there would not be a need for locking. But what happens if one is from task context and another from IRQ context?
I don't see a local_irq_save()/restore() anywhere. What avoids the trivial lock inversion?
Also; what about BPF running from NMI context and using locks?
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 5 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
Quoted 8 lines
Quoted 2 lines
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.
nope. all bpf prog types disable preemption. That is must have for all sorts of things to work properly.
If there is a prog type that doing rcu_read_lock only it's a serious bug. About a year or so ago we audited everything specifically to make sure everything disables preemption before calling bpf progs. I'm pretty sure nothing crept in in the mean time.
Quoted 11 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Why does it matter if 0 means unlocked; that's what
__ARCH_SPIN_LOCK_UNLOCKEDis for.I get the
sizeof(__u32)thing, but why not key off of that?
what do you mean by 'key off of that' ?
to use arch_spinlock_t instead of qspinlock ?
That was my first attempt, but then I painfully found that its size on parisc is 16 bytes and we're not going to penalize bpf to waste that much space because of single architecture. sizeof(arch_spinlock_t) can be 1 byte too (on sparc). That would fit in __u32, but I figured it's cleaner to use qspinlock on all archs that support it and dumb_spin_lock on archs that dont.
Another option is use to arch_spinlock_t when its sizeof==4 and use dumb_spin_lock otherwise.
It's doable, but imo still less clean than using qspinlock due to zero init. Since zero init is a lot less map work that zero inits all elements already.
If arch_spinlock_t is used than at map init time we would need to walk all elements and do __ARCH_SPIN_LOCK_UNLOCKED assignment (and maps can have millions of elements).
Not horrible, but 100% waste of cycles for x86/arm64 where qspinlock is used. Such waste can be workaround further by doing ugly #idef __ARCH_SPIN_LOCK_UNLOCKED == 0 -> don't do init loop. And then add another #ifdef for archs with sizeof(arch_spinlock_t)!=4 to keep zero init for all map types that support bpf_spin_lock via dumb_spin_lock.
Clearly at that point we're getting into ugliness everywhere. Hence I've used qspinlock directly.
Quoted 6 lines
Quoted 5 lines
Next steps:
- allowbpf_spin_lockin other map types (like cgroup local storage)
- introduceBPF_F_LOCKflag forbpf_map_update()syscall and helper to request kernel to grabbpf_spin_lockbefore rewriting the value. That will serialize access to map elements.
Quoted 8 lines
So clearly this map stuff is shared between bpf proglets, otherwise there would not be a need for locking. But what happens if one is from task context and another from IRQ context?
I don't see a local_irq_save()/restore() anywhere. What avoids the trivial lock inversion?
and from NMI ...
progs are not preemptable and map syscall accessors have bpf_prog_active counters. So nmi/kprobe progs will not be running when syscall is running. Hence dead lock is not possible and irq_save is not needed.
Quoted 48 lines
Quoted 48 lines
kernel/bpf/helpers.c +40
-0@@ -221,6 +221,63 @@ const struct bpf_func_proto bpf_get_current_comm_proto = { .arg2_type = ARG_CONST_SIZE, }; +#ifndef CONFIG_QUEUED_SPINLOCKS +struct dumb_spin_lock { +atomic_t val; +}; +#endif + +notrace BPF_CALL_1 (bpf_spin_lock ,struct bpf_spin_lock *,lock ) +{ +#if defined(CONFIG_SMP ) +#ifdef CONFIG_QUEUED_SPINLOCKS +struct qspinlock *qlock = (void *)lock; + +BUILD_BUG_ON (sizeof (*qlock) !=sizeof (*lock)); +queued_spin_lock (qlock); +#else +struct dumb_spin_lock *qlock = (void *)lock; + +BUILD_BUG_ON (sizeof (*qlock) !=sizeof (*lock)); +do { +while (atomic_read (&qlock->val) !=0 ) +cpu_relax (); + }while (atomic_cmpxchg (&qlock->val,0 ,1 ) !=0 ); +#endif +#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 , +}; + +notrace BPF_CALL_1 (bpf_spin_unlock ,struct bpf_spin_lock *,lock ) +{ +#if defined(CONFIG_SMP ) +#ifdef CONFIG_QUEUED_SPINLOCKS +struct qspinlock *qlock = (void *)lock; +
Quoted 8 lines
kernel/bpf/helpers.c const struct bpf_func_proto bpf_get_current_comm_proto = { · line 268
Quoted 5 lines
kernel/bpf/helpers.c +5
-0+queued_spin_unlock (qlock); +#else +struct dumb_spin_lock *qlock = (void *)lock; + +atomic_set (&qlock->val,0 );And this is broken... That should've been
atomic_set_release()at the very least.
right. good catch.
Quoted 2 lines
And this would again be the moment where I go pester you about the BPF memory model :-)
hehe :)
How do you propose to define it in a way that it applies to all archs and yet doesn't penalize x86 ?
"Assume minimum execution ordering model" the way kernel does unfortunately is not usable, since bpf doesn't have a luxury of using nice #defines that convert into nops on x86.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Paul E. McKenneyQuoted 27 lines · Paul E. McKenney
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
Quoted 5 lines
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Let's keep "srcu in bpf" discussion separate from bpf_spin_lock discussion. bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types like bpf syscall probes that need to be able to do copy_from_user from bpf prog.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 14 lines · Alexei Starovoitov
Quoted 4 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
Quoted 8 lines
Quoted 2 lines
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.
Quoted 6 lines
nope. all bpf prog types disable preemption. That is must have for all sorts of things to work properly.
If there is a prog type that doingrcu_read_lockonly it's a serious bug. About a year or so ago we audited everything specifically to make sure everything disables preemption before calling bpf progs. I'm pretty sure nothing crept in in the mean time.
Hmm? What about unix_dgram_sendmsg->sk_filter->sk_filter_trim_cap->bpf_prog_run_save_cb->BPF_PROG_RUN? That just holds rcu_read_lock(), as far as I can tell...
In general, for tricky rules about locks that must be held or contexts that code can run in, it makes sense to use some check that yells when that rule is being violated, at least in debug builds. Otherwise it's too easy for bugs to creep in...
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 31 lines · Alexei Starovoitov
Quoted 30 lines · Paul E. McKenney
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.
Quoted 8 lines
Quoted 2 lines
One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Let's keep "srcu in bpf" discussion separate from
bpf_spin_lockdiscussion. bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types like bpf syscall probes that need to be able to docopy_from_userfrom bpf prog.
Hmmm... What prevents BPF programs from looping infinitely within an RCU reader, and as you noted, preemption disabled?
If BPF programs are in fact allowed to loop infinitely, it would be very good for the health of the kernel to have preemption enabled. And to be within an SRCU read-side critical section instead of an RCU read-side critical section.
Thanx, Paul
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 41 lines · Paul E. McKenney
Quoted 31 lines · Alexei Starovoitov
Quoted 30 lines · Paul E. McKenney
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.Quoted 8 lines
Quoted 2 lines
One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Let's keep "srcu in bpf" discussion separate from
bpf_spin_lockdiscussion. bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types like bpf syscall probes that need to be able to docopy_from_userfrom bpf prog.
Quoted 7 lines
Hmmm... What prevents BPF programs from looping infinitely within an RCU reader, and as you noted, preemption disabled?
If BPF programs are in fact allowed to loop infinitely, it would be very good for the health of the kernel to have preemption enabled. And to be within an SRCU read-side critical section instead of an RCU read-side critical section.
The BPF verifier prevents loops; this is in push_insn() in kernel/bpf/verifier.c, which errors out with -EINVAL when a back edge is encountered. For non-root programs, that limits the maximum number of instructions per eBPF engine execution to BPF_MAXINSNS*MAX_TAIL_CALL_CNT==4096*32==131072 (but that includes call instructions, which can cause relatively expensive operations like hash table lookups). For programs created with CAP_SYS_ADMIN, things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 7 lines · Alexei Starovoitov
Quoted 1 line · Peter Zijlstra
and from NMI ...
progs are not preemptable and map syscall accessors have
bpf_prog_activecounters. So nmi/kprobe progs will not be running when syscall is running. Hence dead lock is not possible andirq_saveis not needed.
Speaking of NMI, how pcpu_freelist_push() and pop() can actually work ?
It seems bpf_get_stackid() can be called from NMI, and lockdep seems to complain loudly
lpaa5:/export/hda3/google/edumazet# ./test_progs test_pkt_access:PASS:ipv4 48 nsec test_pkt_access:PASS:ipv6 49 nsec test_prog_run_xattr:PASS:load 0 nsec test_prog_run_xattr:PASS:run 316 nsec test_prog_run_xattr:PASS:data_size_out 316 nsec test_prog_run_xattr:PASS:overflow 316 nsec test_prog_run_xattr:PASS:run_no_output 431 nsec test_prog_run_xattr:PASS:run_wrong_size_out 431 nsec test_xdp:PASS:ipv4 1397 nsec test_xdp:PASS:ipv6 523 nsec test_xdp_adjust_tail:PASS:ipv4 382 nsec test_xdp_adjust_tail:PASS:ipv6 210 nsec test_l4lb:PASS:ipv4 143 nsec test_l4lb:PASS:ipv6 164 nsec libbpf: incorrect bpf_call opcode libbpf: incorrect bpf_call opcode test_tcp_estats:PASS: 0 nsec test_bpf_obj_id:PASS:get-fd-by-notexist-prog-id 0 nsec test_bpf_obj_id:PASS:get-fd-by-notexist-map-id 0 nsec test_bpf_obj_id:PASS:get-map-info(fd) 0 nsec test_bpf_obj_id:PASS:get-prog-info(fd) 0 nsec test_bpf_obj_id:PASS:get-map-info(fd) 0 nsec test_bpf_obj_id:PASS:get-prog-info(fd) 0 nsec test_bpf_obj_id:PASS:get-prog-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-prog-fd-bad-nr-map-ids 0 nsec test_bpf_obj_id:PASS:get-prog-info(next_id->fd) 0 nsec test_bpf_obj_id:PASS:get-prog-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-prog-fd-bad-nr-map-ids 0 nsec test_bpf_obj_id:PASS:get-prog-info(next_id->fd) 0 nsec test_bpf_obj_id:PASS:check total prog id found by get_next_id 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:check get-map-info(next_id->fd) 0 nsec test_bpf_obj_id:PASS:get-map-fd(next_id) 0 nsec test_bpf_obj_id:PASS:check get-map-info(next_id->fd) 0 nsec test_bpf_obj_id:PASS:check total map id found by get_next_id 0 nsec test_pkt_md_access:PASS: 76 nsec test_obj_name:PASS:check-bpf-prog-name 0 nsec test_obj_name:PASS:check-bpf-map-name 0 nsec test_obj_name:PASS:check-bpf-prog-name 0 nsec test_obj_name:PASS:check-bpf-map-name 0 nsec test_obj_name:PASS:check-bpf-prog-name 0 nsec test_obj_name:PASS:check-bpf-map-name 0 nsec test_obj_name:PASS:check-bpf-prog-name 0 nsec test_obj_name:PASS:check-bpf-map-name 0 nsec test_tp_attach_query:PASS:open 0 nsec test_tp_attach_query:PASS:read 0 nsec test_tp_attach_query:PASS:prog_load 0 nsec test_tp_attach_query:PASS:bpf_obj_get_info_by_fd 0 nsec test_tp_attach_query:PASS:perf_event_open 0 nsec test_tp_attach_query:PASS:perf_event_ioc_enable 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_set_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:prog_load 0 nsec test_tp_attach_query:PASS:bpf_obj_get_info_by_fd 0 nsec test_tp_attach_query:PASS:perf_event_open 0 nsec test_tp_attach_query:PASS:perf_event_ioc_enable 0 nsec test_tp_attach_query:PASS:perf_event_ioc_set_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:prog_load 0 nsec test_tp_attach_query:PASS:bpf_obj_get_info_by_fd 0 nsec test_tp_attach_query:PASS:perf_event_open 0 nsec test_tp_attach_query:PASS:perf_event_ioc_enable 0 nsec test_tp_attach_query:PASS:perf_event_ioc_set_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_tp_attach_query:PASS:perf_event_ioc_query_bpf 0 nsec test_stacktrace_map:PASS:prog_load 0 nsec test_stacktrace_map:PASS:open 0 nsec test_stacktrace_map:PASS:perf_event_open 0 nsec test_stacktrace_map:PASS:compare_map_keys stackid_hmap vs. stackmap 0 nsec test_stacktrace_map:PASS:compare_map_keys stackmap vs. stackid_hmap 0 nsec test_stacktrace_map:PASS:compare_stack_ips stackmap vs. stack_amap 0 nsec test_stacktrace_build_id:PASS:prog_load 0 nsec test_stacktrace_build_id:PASS:open 0 nsec test_stacktrace_build_id:PASS:read 0 nsec test_stacktrace_build_id:PASS:perf_event_open 0 nsec test_stacktrace_build_id:PASS:perf_event_ioc_enable 0 nsec test_stacktrace_build_id:PASS:perf_event_ioc_set_bpf 0 nsec test_stacktrace_build_id:PASS:bpf_find_map control_map 0 nsec test_stacktrace_build_id:PASS:bpf_find_map stackid_hmap 0 nsec test_stacktrace_build_id:PASS:bpf_find_map stackmap 0 nsec test_stacktrace_build_id:PASS:bpf_find_map stack_amap 0 nsec test_stacktrace_build_id:PASS:compare_map_keys stackid_hmap vs. stackmap 0 nsec test_stacktrace_build_id:PASS:compare_map_keys stackmap vs. stackid_hmap 0 nsec test_stacktrace_build_id:PASS:get build_id with readelf 0 nsec test_stacktrace_build_id:PASS:get_next_key from stackmap 0 nsec test_stacktrace_build_id:PASS:lookup_elem from stackmap 0 nsec test_stacktrace_build_id:PASS:lookup_elem from stackmap 0 nsec test_stacktrace_build_id:PASS:build id match 0 nsec test_stacktrace_build_id:PASS:compare_stack_ips stackmap vs. stack_amap 0 nsec test_stacktrace_build_id_nmi:PASS:prog_load 0 nsec test_stacktrace_build_id_nmi:PASS:perf_event_open 0 nsec test_stacktrace_build_id_nmi:PASS:perf_event_ioc_enable 0 nsec test_stacktrace_build_id_nmi:PASS:perf_event_ioc_set_bpf 0 nsec test_stacktrace_build_id_nmi:PASS:bpf_find_map control_map 0 nsec test_stacktrace_build_id_nmi:PASS:bpf_find_map stackid_hmap 0 nsec test_stacktrace_build_id_nmi:PASS:bpf_find_map stackmap 0 nsec test_stacktrace_build_id_nmi:PASS:bpf_find_map stack_amap 0 nsec test_stacktrace_build_id_nmi:PASS:compare_map_keys stackid_hmap vs. stackmap 0 nsec test_stacktrace_build_id_nmi:PASS:compare_map_keys stackmap vs. stackid_hmap 0 nsec test_stacktrace_build_id_nmi:PASS:get build_id with readelf 0 nsec test_stacktrace_build_id_nmi:PASS:get_next_key from stackmap 0 nsec test_stacktrace_build_id_nmi:PASS:lookup_elem from stackmap 0 nsec test_stacktrace_build_id_nmi:PASS:lookup_elem from stackmap 0 nsec test_stacktrace_build_id_nmi:PASS:lookup_elem from stackmap 0 nsec test_stacktrace_build_id_nmi:PASS:lookup_elem from stackmap 0 nsec test_stacktrace_build_id_nmi:PASS:build id match 0 nsec test_stacktrace_map_raw_tp:PASS:prog_load raw tp 0 nsec test_stacktrace_map_raw_tp:PASS:raw_tp_open 0 nsec test_stacktrace_map_raw_tp:PASS:compare_map_keys stackid_hmap vs. stackmap 0 nsec test_stacktrace_map_raw_tp:PASS:compare_map_keys stackmap vs. stackid_hmap 0 nsec test_get_stack_raw_tp:PASS:prog_load raw tp 0 nsec test_get_stack_raw_tp:PASS:raw_tp_open 0 nsec test_get_stack_raw_tp:PASS:bpf_find_map 0 nsec test_get_stack_raw_tp:PASS:load_kallsyms 0 nsec test_get_stack_raw_tp:PASS:perf_event_open 0 nsec test_get_stack_raw_tp:PASS:bpf_map_update_elem 0 nsec test_get_stack_raw_tp:PASS:ioctl PERF_EVENT_IOC_ENABLE 0 nsec test_get_stack_raw_tp:PASS:perf_event_mmap 0 nsec test_get_stack_raw_tp:PASS:perf_event_poller 0 nsec test_task_fd_query_rawtp:PASS:prog_load raw tp 0 nsec test_task_fd_query_rawtp:PASS:raw_tp_open 0 nsec test_task_fd_query_rawtp:PASS:bpf_task_fd_query 0 nsec test_task_fd_query_rawtp:PASS:check_results 0 nsec test_task_fd_query_rawtp:PASS:bpf_task_fd_query (len = 0) 0 nsec test_task_fd_query_rawtp:PASS:check_results 0 nsec test_task_fd_query_rawtp:PASS:bpf_task_fd_query (buf = 0) 0 nsec test_task_fd_query_rawtp:PASS:check_results 0 nsec test_task_fd_query_rawtp:PASS:bpf_task_fd_query (len = 3) 0 nsec test_task_fd_query_rawtp:PASS:check_results 0 nsec test_task_fd_query_tp_core:PASS:bpf_prog_load 0 nsec test_task_fd_query_tp_core:PASS:open 0 nsec test_task_fd_query_tp_core:PASS:read 0 nsec test_task_fd_query_tp_core:PASS:perf_event_open 0 nsec test_task_fd_query_tp_core:PASS:perf_event_ioc_enable 0 nsec test_task_fd_query_tp_core:PASS:perf_event_ioc_set_bpf 0 nsec test_task_fd_query_tp_core:PASS:bpf_task_fd_query 0 nsec test_task_fd_query_tp_core:PASS:check_results 0 nsec test_task_fd_query_tp_core:PASS:bpf_prog_load 0 nsec test_task_fd_query_tp_core:PASS:open 0 nsec test_task_fd_query_tp_core:PASS:read 0 nsec test_task_fd_query_tp_core:PASS:perf_event_open 0 nsec test_task_fd_query_tp_core:PASS:perf_event_ioc_enable 0 nsec test_task_fd_query_tp_core:PASS:perf_event_ioc_set_bpf 0 nsec test_task_fd_query_tp_core:PASS:bpf_task_fd_query 0 nsec test_task_fd_query_tp_core:PASS:check_results 0 nsec test_reference_tracking:PASS:sk_lookup_success 0 nsec test_reference_tracking:PASS:sk_lookup_success_simple 0 nsec test_reference_tracking:PASS:fail_use_after_free 0 nsec test_reference_tracking:PASS:fail_modify_sk_pointer 0 nsec test_reference_tracking:PASS:fail_modify_sk_or_null_pointer 0 nsec test_reference_tracking:PASS:fail_no_release 0 nsec test_reference_tracking:PASS:fail_release_twice 0 nsec test_reference_tracking:PASS:fail_release_unchecked 0 nsec test_reference_tracking:PASS:fail_no_release_subcall 0 nsec test_queue_stack_map:PASS:bpf_map_pop_elem 342 nsec test_queue_stack_map:PASS:check-queue-stack-map-empty 323 nsec test_queue_stack_map:PASS:bpf_map_push_elem 323 nsec test_queue_stack_map:PASS:bpf_map_pop_elem 325 nsec test_queue_stack_map:PASS:check-queue-stack-map-empty 311 nsec test_queue_stack_map:PASS:bpf_map_push_elem 311 nsec Summary: 175 PASSED, 2 FAILED
[ 429.727565] ========================================================
[ 429.733916] WARNING: possible irq lock inversion dependency detected
[ 429.740282] 5.0.0-dbg-DEV #550 Not tainted
[ 429.744381] --------------------------------------------------------
[ 429.750743] dd/16374 just changed the state of lock:
[ 429.755751] 0000000062c2321f (&head->lock){+...}, at: pcpu_freelist_push+0x28/0x50
[ 429.763348] but this lock was taken by another, HARDIRQ-safe lock in the past:
[ 429.770609] (&rq->lock){-.-.}
[ 429.770610] and interrupts could create inverse lock ordering between them.
[ 429.785089]
other info that might help us debug this:
[ 429.791630] Possible interrupt unsafe locking scenario:[ 429.798432] CPU0 CPU1
[ 429.802964] ---- ----
[ 429.807513] lock(&head->lock);
[ 429.810746] local_irq_disable();
[ 429.816700] lock(&rq->lock);
[ 429.822322] lock(&head->lock);
[ 429.828094] <Interrupt>
[ 429.830724] lock(&rq->lock);
[ 429.833977]
*** DEADLOCK ***[ 429.839929] 1 lock held by dd/16374:
[ 429.843526] #0: 00000000a4c09748 (rcu_read_lock){....}, at: trace_call_bpf+0x38/0x1f0
[ 429.851498]
the shortest dependencies between 2nd lock and 1st lock:
[ 429.859348] -> (&rq->lock){-.-.} {
[ 429.862847] IN-HARDIRQ-W at:
[ 429.866091] lock_acquire+0xa7/0x190
[ 429.871531] _raw_spin_lock+0x2f/0x40
[ 429.877051] scheduler_tick+0x51/0x100
[ 429.882621] update_process_times+0x6f/0x90
[ 429.888660] tick_periodic+0x2b/0xc0
[ 429.894065] tick_handle_periodic+0x25/0x70
[ 429.900096] timer_interrupt+0x15/0x20
[ 429.905729] __handle_irq_event_percpu+0x44/0x2b0
[ 429.912265] handle_irq_event+0x60/0xc0
[ 429.917924] handle_edge_irq+0x8b/0x220
[ 429.923570] handle_irq+0x21/0x30
[ 429.928724] do_IRQ+0x64/0x120
[ 429.933613] ret_from_intr+0x0/0x1d
[ 429.938935] timer_irq_works+0x5b/0xfd
[ 429.944528] setup_IO_APIC+0x378/0x82b
[ 429.950101] apic_intr_mode_init+0x16d/0x172
[ 429.956202] x86_late_time_init+0x15/0x1c
[ 429.962049] start_kernel+0x44b/0x4fe
[ 429.967532] x86_64_start_reservations+0x24/0x26
[ 429.973988] x86_64_start_kernel+0x6f/0x72
[ 429.979942] secondary_startup_64+0xa4/0xb0
[ 429.985960] IN-SOFTIRQ-W at:
[ 429.989183] lock_acquire+0xa7/0x190
[ 429.994582] _raw_spin_lock+0x2f/0x40
[ 430.000067] try_to_wake_up+0x1ef/0x610
[ 430.005740] wake_up_process+0x15/0x20
[ 430.011314] swake_up_one+0x36/0x70
[ 430.016648] rcu_gp_kthread_wake+0x3c/0x40
[ 430.022591] rcu_accelerate_cbs_unlocked+0x8c/0xd0
[ 430.029219] rcu_process_callbacks+0xdd/0xc50
[ 430.035434] __do_softirq+0x105/0x465
[ 430.040952] irq_exit+0xc8/0xd0
[ 430.045932] smp_apic_timer_interrupt+0xa5/0x230
[ 430.052387] apic_timer_interrupt+0xf/0x20
[ 430.058331] clear_page_erms+0x7/0x10
[ 430.063825] __alloc_pages_nodemask+0x165/0x390
[ 430.070201] dsalloc_pages+0x65/0x90
[ 430.075657] reserve_ds_buffers+0x136/0x500
[ 430.081679] x86_reserve_hardware+0x16d/0x180
[ 430.087874] x86_pmu_event_init+0x4b/0x210
[ 430.093828] perf_try_init_event+0x8f/0xb0
[ 430.099744] perf_event_alloc+0xa1d/0xc90
[ 430.105576] perf_event_create_kernel_counter+0x24/0x150
[ 430.112721] hardlockup_detector_event_create+0x41/0x90
[ 430.119785] hardlockup_detector_perf_enable+0xe/0x40
[ 430.126653] watchdog_nmi_enable+0xe/0x20
[ 430.132501] watchdog_enable+0xb8/0xd0
[ 430.138097] softlockup_start_fn+0x15/0x20
[ 430.144015] smp_call_on_cpu_callback+0x2a/0x60
[ 430.150393] process_one_work+0x1f4/0x580
[ 430.156231] worker_thread+0x6f/0x430
[ 430.161708] kthread+0x132/0x170
[ 430.166791] ret_from_fork+0x24/0x30
[ 430.172180] INITIAL USE at:
[ 430.175334] lock_acquire+0xa7/0x190
[ 430.180656] _raw_spin_lock_irqsave+0x3a/0x50
[ 430.186763] rq_attach_root+0x1d/0xd0
[ 430.192153] sched_init+0x30b/0x40d
[ 430.197409] start_kernel+0x283/0x4fe
[ 430.202825] x86_64_start_reservations+0x24/0x26
[ 430.209181] x86_64_start_kernel+0x6f/0x72
[ 430.215032] secondary_startup_64+0xa4/0xb0
[ 430.220964] }
[ 430.222724] ... key at: [<ffffffff88f7dc28>] __key.71964+0x0/0x8
[ 430.229345] ... acquired at:
[ 430.232404] _raw_spin_lock+0x2f/0x40
[ 430.236260] pcpu_freelist_pop+0x77/0xf0
[ 430.240349] bpf_get_stackid+0x1c4/0x440
[ 430.244465] bpf_get_stackid_tp+0x11/0x20[ 430.250156] -> (&head->lock){+...} {
[ 430.253742] HARDIRQ-ON-W at:
[ 430.256878] lock_acquire+0xa7/0x190
[ 430.262095] _raw_spin_lock+0x2f/0x40
[ 430.267397] pcpu_freelist_push+0x28/0x50
[ 430.273088] bpf_get_stackid+0x41e/0x440
[ 430.278677] bpf_get_stackid_tp+0x11/0x20
[ 430.284350] INITIAL USE at:
[ 430.287411] lock_acquire+0xa7/0x190
[ 430.292591] _raw_spin_lock+0x2f/0x40
[ 430.297833] pcpu_freelist_populate+0xc3/0x120
[ 430.303840] htab_map_alloc+0x41e/0x550
[ 430.309245] __do_sys_bpf+0x27e/0x1b50
[ 430.314591] __x64_sys_bpf+0x1a/0x20
[ 430.319738] do_syscall_64+0x5a/0x460
[ 430.324962] entry_SYSCALL_64_after_hwframe+0x49/0xbe
[ 430.331598] }
[ 430.333274] ... key at: [<ffffffff89bfce48>] __key.13162+0x0/0x8
[ 430.339821] ... acquired at:
[ 430.342795] mark_lock+0x3c4/0x630
[ 430.346371] __lock_acquire+0x3b2/0x1850
[ 430.350493] lock_acquire+0xa7/0x190
[ 430.354282] _raw_spin_lock+0x2f/0x40
[ 430.358129] pcpu_freelist_push+0x28/0x50
[ 430.362331] bpf_get_stackid+0x41e/0x440
[ 430.366438] bpf_get_stackid_tp+0x11/0x20[ 430.372128]
stack backtrace:
[ 430.376479] CPU: 29 PID: 16374 Comm: dd Not tainted 5.0.0-dbg-DEV #550
[ 430.383008] Hardware name: Intel RML,PCH/Iota_QC_19, BIOS 2.54.0 06/07/2018
[ 430.389967] Call Trace:
[ 430.392433] dump_stack+0x67/0x95
[ 430.395756] print_irq_inversion_bug.part.38+0x1b8/0x1c4
[ 430.401066] check_usage_backwards+0x156/0x160
[ 430.405523] mark_lock+0x3c4/0x630
[ 430.408925] ? mark_lock+0x3c4/0x630
[ 430.412496] ? print_shortest_lock_dependencies+0x1b0/0x1b0
[ 430.418092] __lock_acquire+0x3b2/0x1850
[ 430.422018] ? find_get_entry+0x1b1/0x320
[ 430.426050] ? find_get_entry+0x1d0/0x320
[ 430.430063] lock_acquire+0xa7/0x190
[ 430.433667] ? lock_acquire+0xa7/0x190
[ 430.437433] ? pcpu_freelist_push+0x28/0x50
[ 430.441635] _raw_spin_lock+0x2f/0x40
[ 430.445317] ? pcpu_freelist_push+0x28/0x50
[ 430.449494] pcpu_freelist_push+0x28/0x50
[ 430.453513] bpf_get_stackid+0x41e/0x440
[ 430.457446] bpf_get_stackid_tp+0x11/0x20
[ 430.461450] ? trace_call_bpf+0xe4/0x1f0
[ 430.465365] ? perf_trace_run_bpf_submit+0x42/0xb0
[ 430.470155] ? perf_trace_urandom_read+0xbf/0x100
[ 430.474851] ? urandom_read+0x20f/0x350
[ 430.478685] ? vfs_read+0xb8/0x190
[ 430.482096] ? __x64_sys_read+0x61/0xd0
[ 430.485949] ? do_syscall_64+0x21/0x460
[ 430.489797] ? do_syscall_64+0x5a/0x460
[ 430.493635] ? entry_SYSCALL_64_after_hwframe+0x49/0xbe
[ 451.715758] perf: interrupt took too long (2516 > 2500), lowering kernel.perf_event_max_sample_rate to 79000Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 7 lines · Eric Dumazet
Quoted 4 lines · Alexei Starovoitov
Quoted 1 line · Peter Zijlstra
and from NMI ...
Quoted 8 lines
Quoted 3 lines
progs are not preemptable and map syscall accessors have
bpf_prog_activecounters. So nmi/kprobe progs will not be running when syscall is running. Hence dead lock is not possible andirq_saveis not needed.Speaking of NMI, how
pcpu_freelist_push()andpop()can actually work ?It seems
bpf_get_stackid()can be called from NMI, and lockdep seems to complain loudly
it's a known false positive.
https://lkml.org/lkml/2018/7/25/756
and the same answer as before:
we're not going to penalize performance to shut up false positive.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Jann HornQuoted 50 lines · Jann Horn
Quoted 41 lines · Paul E. McKenney
Quoted 31 lines · Alexei Starovoitov
Quoted 30 lines · Paul E. McKenney
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.Quoted 8 lines
Quoted 2 lines
One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Let's keep "srcu in bpf" discussion separate from
bpf_spin_lockdiscussion. bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types like bpf syscall probes that need to be able to docopy_from_userfrom bpf prog.Quoted 7 lines
Hmmm... What prevents BPF programs from looping infinitely within an RCU reader, and as you noted, preemption disabled?
If BPF programs are in fact allowed to loop infinitely, it would be very good for the health of the kernel to have preemption enabled. And to be within an SRCU read-side critical section instead of an RCU read-side critical section.
Quoted 7 lines
The BPF verifier prevents loops; this is in
push_insn()inkernel/bpf/verifier.c, which errors out with-EINVALwhen a back edge is encountered. For non-root programs, that limits the maximum number of instructions per eBPF engine execution to BPF_MAXINSNS*MAX_TAIL_CALL_CNT==4096*32==131072 (but that includes call instructions, which can cause relatively expensive operations like hash table lookups).
correct.
Quoted 4 lines
For programs created with
CAP_SYS_ADMIN,
things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.
I think you're referring to bpf-to-bpf calls.
The limit it still the same. 4k per program including all calls. tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.
Note that classic bpf has the same 4k limit and it can call expensive functions too via SKF_AD extensions.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 13 lines · Alexei Starovoitov
Quoted 12 lines · Eric Dumazet
Quoted 7 lines · Alexei Starovoitov
Quoted 1 line · Peter Zijlstra
and from NMI ...
progs are not preemptable and map syscall accessors have
bpf_prog_activecounters. So nmi/kprobe progs will not be running when syscall is running. Hence dead lock is not possible andirq_saveis not needed.
Quoted 9 lines
Quoted 3 lines
Speaking of NMI, how
pcpu_freelist_push()andpop()can actually work ?It seems
bpf_get_stackid()can be called from NMI, and lockdep seems to complain loudlyit's a known false positive.
https://lkml.org/lkml/2018/7/25/756
and the same answer as before:
we're not going to penalize performance to shut up false positive.
As far as lockdep is concerned, I do not believe we care about performance.
How can we remove this false positive, so that lockdep stays alive even after running bpf test_progs ?
Let see if we understood this well.
1. create perf event PERF_TYPE_HARDWARE:PERF_COUNT_HW_CPU_CYCLES
2. attach bpf probram to this event
3. since that's a hw event, the bpf program is executed in NMI context
4. the bpf program calls bpf_get_stackid to record the trace in a bpf map
5. bpf_get_stackid calls pcpu_freelist_pop and pcpu_freelist_push from NMI
6. userspace calls sys_bpf(bpf_map_lookup_elem) which calls bpf_stackmap_copy which can call pcpu_freelist_push
It seems pcpu_freelist_pop and pcpu_freelist_push are not NMI safe, so what prevents bad things to happen ?
Thanks.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Jann HornQuoted 23 lines · Jann Horn
Quoted 14 lines · Alexei Starovoitov
Quoted 4 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
Quoted 8 lines
Quoted 2 lines
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
nope. all bpf prog types disable preemption. That is must have for all sorts of things to work properly.
If there is a prog type that doingrcu_read_lockonly it's a serious bug. About a year or so ago we audited everything specifically to make sure everything disables preemption before calling bpf progs. I'm pretty sure nothing crept in in the mean time.
Quoted 3 lines
Hmm? What about
unix_dgram_sendmsg->sk_filter->sk_filter_trim_cap->bpf_prog_run_save_cb->BPF_PROG_RUN? That just holdsrcu_read_lock(), as far as I can tell...
Looking into it.
First reaction is per-cpu maps and bpf_get_smp_processor_id/numa_id will return bogus values for sender attached socket socket filters in CONFIG_PREEMPT kernels. Receive side is in bh.
Not a security issue, but something we have to fix.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Eric DumazetQuoted 26 lines · Eric Dumazet
Quoted 13 lines · Alexei Starovoitov
Quoted 12 lines · Eric Dumazet
Quoted 7 lines · Alexei Starovoitov
Quoted 1 line · Peter Zijlstra
and from NMI ...
progs are not preemptable and map syscall accessors have
bpf_prog_activecounters. So nmi/kprobe progs will not be running when syscall is running. Hence dead lock is not possible andirq_saveis not needed.Quoted 9 lines
Quoted 3 lines
Speaking of NMI, how
pcpu_freelist_push()andpop()can actually work ?It seems
bpf_get_stackid()can be called from NMI, and lockdep seems to complain loudlyit's a known false positive.
https://lkml.org/lkml/2018/7/25/756
and the same answer as before:
we're not going to penalize performance to shut up false positive.
Quoted 3 lines
As far as lockdep is concerned, I do not believe we care about performance.
How can we remove this false positive, so that lockdep stays alive even after running bpf
test_progs?
Like do irq_save version when lockdep is on?
Sure. Let's do that.
That splat was bugging me for very long time.
I see it every single day when I run this test before applying patches.
Quoted 8 lines
Let see if we understood this well.
1. create perf event PERF_TYPE_HARDWARE:PERF_COUNT_HW_CPU_CYCLES
2. attach bpf probram to this event
3. since that's a hw event, the bpf program is executed in NMI context
4. the bpf program callsbpf_get_stackidto record the trace in a bpf map
5.bpf_get_stackidcallspcpu_freelist_popandpcpu_freelist_pushfrom NMI
6. userspace callssys_bpf(bpf_map_lookup_elem)which callsbpf_stackmap_copywhich can callpcpu_freelist_push
argh. lookup cmd is missing __this_cpu_inc(bpf_prog_active); like update/delete do. Will fix.
Quoted 2 lines
It seems
pcpu_freelist_popandpcpu_freelist_pushare not NMI safe, so what prevents bad things to happen ?
nmi checks for bpf_prog_active==0. See bpf_overflow_handler.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Jann HornQuoted 50 lines · Jann Horn
Quoted 41 lines · Paul E. McKenney
Quoted 31 lines · Alexei Starovoitov
Quoted 30 lines · Paul E. McKenney
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.Quoted 8 lines
Quoted 2 lines
One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Let's keep "srcu in bpf" discussion separate from
bpf_spin_lockdiscussion. bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types like bpf syscall probes that need to be able to docopy_from_userfrom bpf prog.Quoted 7 lines
Hmmm... What prevents BPF programs from looping infinitely within an RCU reader, and as you noted, preemption disabled?
If BPF programs are in fact allowed to loop infinitely, it would be very good for the health of the kernel to have preemption enabled. And to be within an SRCU read-side critical section instead of an RCU read-side critical section.
Quoted 10 lines
The BPF verifier prevents loops; this is in
push_insn()inkernel/bpf/verifier.c, which errors out with-EINVALwhen a back edge is encountered. For non-root programs, that limits the maximum number of instructions per eBPF engine execution to BPF_MAXINSNS*MAX_TAIL_CALL_CNT==4096*32==131072 (but that includes call instructions, which can cause relatively expensive operations like hash table lookups). For programs created withCAP_SYS_ADMIN, things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.
Whew!!! ;-)
So no more than (say) 100 milliseconds?
Thanx, Paul
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 7 lines · Alexei Starovoitov
Quoted 4 lines
For programs created with
CAP_SYS_ADMIN,
things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.I think you're referring to bpf-to-bpf calls.
The limit it still the same. 4k per program including all calls. tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.
Jann,
I think you meant
main:
call A
call A
call A
exit
A:
call B
call B
call B
exit
B:
call C
...
scenario when everything fits into 4k?
Would be great if you can construct such test while we're fixing the rest of the issues brought up in this thread.
It will definitely be no more than BPF_COMPLEXITY_LIMIT_INSNS which is 128k, but I wonder what will be the actual number of executed insns.
I think such clever constructed sequence can actually hit 128k executed too.
It would be awesome test to add to test_verifier.c
We have some of such pushing-the-boundary tests in lib/test_bpf.c that are generated in assembler.
The longest takes 23853 nanoseconds, but clever bpf2bpf call hack like above with map_update call in the leaf function should certainly take much longer.
I accept Paul's challenge to try to get such fancy bpf prog to take 100 millseconds :)
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 26 lines · Alexei Starovoitov
Quoted 7 lines · Alexei Starovoitov
Quoted 4 lines
For programs created with
CAP_SYS_ADMIN,
things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.I think you're referring to bpf-to-bpf calls.
The limit it still the same. 4k per program including all calls. tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.Jann,
I think you meant
main:
call A
call A
call A
exit
A:
call B
call B
call B
exit
B:
call C
...
Quoted 16 lines
scenario when everything fits into 4k?
Would be great if you can construct such test while we're fixing the rest of the issues brought up in this thread.
It will definitely be no more thanBPF_COMPLEXITY_LIMIT_INSNSwhich is 128k, but I wonder what will be the actual number of executed insns.
I think such clever constructed sequence can actually hit 128k executed too.
It would be awesome test to add totest_verifier.c
We have some of such pushing-the-boundary tests inlib/test_bpf.cthat are generated in assembler.
The longest takes 23853 nanoseconds, but clever bpf2bpf call hack like above withmap_updatecall in the leaf function should certainly take much longer.
I accept Paul's challenge to try to get such fancy bpf prog to take 100 millseconds :)
Fair enough! But once you meet my challenge, the RCU CPU stall warning code will challenge you to hit 21 seconds (or only three seconds given an appropriately configured kernel). ;-)
Thanx, Paul
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 44 lines · Paul E. McKenney
Quoted 26 lines · Alexei Starovoitov
Quoted 7 lines · Alexei Starovoitov
Quoted 4 lines
For programs created with
CAP_SYS_ADMIN,
things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.I think you're referring to bpf-to-bpf calls.
The limit it still the same. 4k per program including all calls. tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.Jann,
I think you meant
main:
call A
call A
call A
exit
A:
call B
call B
call B
exit
B:
call C
...Quoted 16 lines
scenario when everything fits into 4k?
Would be great if you can construct such test while we're fixing the rest of the issues brought up in this thread.
It will definitely be no more thanBPF_COMPLEXITY_LIMIT_INSNSwhich is 128k, but I wonder what will be the actual number of executed insns.
I think such clever constructed sequence can actually hit 128k executed too.
It would be awesome test to add totest_verifier.c
We have some of such pushing-the-boundary tests inlib/test_bpf.cthat are generated in assembler.
The longest takes 23853 nanoseconds, but clever bpf2bpf call hack like above withmap_updatecall in the leaf function should certainly take much longer.
I accept Paul's challenge to try to get such fancy bpf prog to take 100 millseconds :)
Quoted 3 lines
Fair enough! But once you meet my challenge, the RCU CPU stall warning code will challenge you to hit 21 seconds (or only three seconds given an appropriately configured kernel). ;-)
if (till_stall_check < 3) {
WRITE_ONCE(rcu_cpu_stall_timeout, 3);
till_stall_check = 3;let's change that limit to 1 !
Seriously though folks have proposed to teach bpf verifier to sprinkle cond_resched() automatically into bpf program when critical path through the program reaches certain insn limit. The verifier can easily be taught to compute the longest path. Other folks proposed to get rid of 4k limit when prog is preemptable and executing in user context.
That's when srcu will come into play.
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 8 lines · Alexei Starovoitov
Quoted 7 lines · Eric Dumazet
Let see if we understood this well.
1. create perf event PERF_TYPE_HARDWARE:PERF_COUNT_HW_CPU_CYCLES
2. attach bpf probram to this event
3. since that's a hw event, the bpf program is executed in NMI context
4. the bpf program callsbpf_get_stackidto record the trace in a bpf map
5.bpf_get_stackidcallspcpu_freelist_popandpcpu_freelist_pushfrom NMI
How is this not a straight up bug? NMI code should not ever call code that uses spinlocks.
Quoted 9 lines
Quoted 1 line
6. userspace calls
sys_bpf(bpf_map_lookup_elem)which callsbpf_stackmap_copywhich can callpcpu_freelist_pushargh. lookup cmd is missing
__this_cpu_inc(bpf_prog_active); like update/delete do. Will fix.Quoted 2 lines
It seems
pcpu_freelist_popandpcpu_freelist_pushare not NMI safe, so what prevents bad things to happen ?nmi checks for bpf_prog_active==0. See
bpf_overflow_handler.
yuck yuck yuck.. That's horrific :-( That means the whole BPF crud is unreliable and events can go randomly missing.
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 15 lines · Alexei Starovoitov
Quoted 5 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
Quoted 8 lines
Quoted 2 lines
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.
Quoted 6 lines
nope. all bpf prog types disable preemption. That is must have for all sorts of things to work properly.
If there is a prog type that doingrcu_read_lockonly it's a serious bug. About a year or so ago we audited everything specifically to make sure everything disables preemption before calling bpf progs. I'm pretty sure nothing crept in in the mean time.
Do we want something like (the completely untested) below to avoid having to manually audit this over and over?
--- include/linux/filter.h | 2 +- include/linux/kernel.h | 9 +++++++-- kernel/sched/core.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 36 insertions(+), 3 deletions(-)
include/linux/filter.h +1 -1
@@ -513,7 +513,7 @@ struct sk_filter {struct bpf_prog *prog; }; -#define BPF_PROG_RUN (filter, ctx) (*(filter)->bpf_func)(ctx, (filter)->insnsi) +#define BPF_PROG_RUN (filter, ctx) ({ cant_sleep(); (*(filter)->bpf_func)(ctx, (filter)->insnsi); })#define BPF_SKB_CB_LEN QDISC_CB_PRIV_LEN
include/linux/kernel.h +7 -2
@@ -245,8 +245,10 @@ extern int _cond_resched(void);#endif #ifdef CONFIG_DEBUG_ATOMIC_SLEEP -void ___might_sleep (const char *file,int line,int preempt_offset); -void __might_sleep (const char *file,int line,int preempt_offset); +extern void ___might_sleep (const char *file,int line,int preempt_offset); +extern void __might_sleep (const char *file,int line,int preempt_offset); +extern void __cant_sleep (const char *file,int line,int preempt_offset); +/** * might_sleep - annotation for functions that can sleep *
@@ -259,6 +261,8 @@ extern int _cond_resched(void);*/ # define might_sleep () \ do { __might_sleep(__FILE__, __LINE__, 0); might_resched(); } while (0) +# define cant_sleep () \ + do { __cant_sleep(__FILE__, __LINE__, 0); } while (0)# define sched_annotate_sleep () (current->task_state_change = 0)#else static inline void ___might_sleep(const char *file, int line,
@@ -266,6 +270,7 @@ extern int _cond_resched(void);static inline void __might_sleep (const char *file,int line,int preempt_offset) { }# define might_sleep () do { might_resched(); } while (0) +# define cant_sleep () do { } while (0)# define sched_annotate_sleep () do { } while (0)#endif
kernel/sched/core.c +28 -0
@@ -6162,6 +6162,34 @@ void ___might_sleep(const char *file, int line, int preempt_offset)add_taint (TAINT_WARN ,LOCKDEP_STILL_OK ); }EXPORT_SYMBOL (___might_sleep); + +void __cant_sleep (const char *file,int line,int preempt_offset) +{ +static unsigned long prev_jiffy; + +if (irqs_disabled ()) +return ; + +if (!IS_ENABLED (CONFIG_PREEMPT_COUNT )) +return ; + +if (preempt_count () > preempt_offset) +return ; + +if (time_before (jiffies, prev_jiffy +HZ ) && prev_jiffy) +return ; + prev_jiffy = jiffies; + +printk (KERN_ERR "BUG: assuming atomic context at %s:%d\n" , file, line); +printk (KERN_ERR "in_atomic(): %d, irqs_disabled(): %d, pid: %d, name: %s\n" , +in_atomic (),irqs_disabled (), + current->pid, current->comm); + +debug_show_held_locks (current); +dump_stack (); +add_taint (TAINT_WARN ,LOCKDEP_STILL_OK ); +} +EXPORT_SYMBOL_GPL (__cant_sleep);#endif #ifdef CONFIG_MAGIC_SYSRQ
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 12 lines · Alexei Starovoitov
Quoted 10 lines · Peter Zijlstra
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Why does it matter if 0 means unlocked; that's what
__ARCH_SPIN_LOCK_UNLOCKEDis for.
Quoted 8 lines
Quoted 1 line
I get the
sizeof(__u32)thing, but why not key off of that?what do you mean by 'key off of that' ?
to usearch_spinlock_tinstead of qspinlock ?
That was my first attempt, but then I painfully found that its size on parisc is 16 bytes and we're not going to penalize bpf to waste that much space because of single architecture.sizeof(arch_spinlock_t)can be 1 byte too (on sparc).
PowerPC has 8 bytes for some config options IIRC.
Quoted 4 lines
That would fit in
__u32, but I figured it's cleaner to use qspinlock on all archs that support it anddumb_spin_lockon archs that dont.Another option is use to
arch_spinlock_twhen its sizeof==4
That's what I meant.
Quoted 5 lines
and use
dumb_spin_lockotherwise.
It's doable, but imo still less clean than using qspinlock due to zero init. Since zero init is a lot less map work that zero inits all elements already.
Quoted 11 lines
If
arch_spinlock_tis used than at map init time we would need to walk all elements and do__ARCH_SPIN_LOCK_UNLOCKEDassignment (and maps can have millions of elements).
Not horrible, but 100% waste of cycles for x86/arm64 where qspinlock is used. Such waste can be workaround further by doing ugly #idef__ARCH_SPIN_LOCK_UNLOCKED== 0 -> don't do init loop. And then add another #ifdef for archs with sizeof(arch_spinlock_t)!=4 to keep zero init for all map types that supportbpf_spin_lockviadumb_spin_lock.
Clearly at that point we're getting into ugliness everywhere. Hence I've used qspinlock directly.
OK; I see.. but do these locks really have enough contention to run into trouble with the simple test-and-set lock?
[ I tried to propose a simple ticket lock, but then realized the virt
archs (s390,powerpc,etc.) would hate that and deleted everything again
]
Argh, what a mess..
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 6 lines · Alexei Starovoitov
Quoted 4 lines · Peter Zijlstra
So clearly this map stuff is shared between bpf proglets, otherwise there would not be a need for locking. But what happens if one is from task context and another from IRQ context?
Quoted 8 lines
Quoted 4 lines
I don't see a local_irq_save()/restore() anywhere. What avoids the trivial lock inversion?
and from NMI ...
progs are not preemptable and map syscall accessors have
bpf_prog_activecounters. So nmi/kprobe progs will not be running when syscall is running. Hence dead lock is not possible andirq_saveis not needed.
What about the progs that run from SoftIRQ ? Since that bpf_prog_active thing isn't inside BPF_PROG_RUN() what is to stop say:
reuseport_select_sock()
...
BPF_PROG_RUN()
bpf_spin_lock()
<IRQ>
...
BPF_PROG_RUN()
bpf_spin_lock() // forever more
</IRQ>Unless you stick that bpf_prog_active stuff inside BPF_PROG_RUN itself, I don't see how you can fundamentally avoid this happening (now or in the future).
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 11 lines · Alexei Starovoitov
Quoted 2 lines · Peter Zijlstra
And this would again be the moment where I go pester you about the BPF memory model :-)
hehe :)
How do you propose to define it in a way that it applies to all archs and yet doesn't penalize x86 ?
"Assume minimum execution ordering model" the way kernel does unfortunately is not usable, since bpf doesn't have a luxury of using nice #defines that convert into nops on x86.
Why not? Surely the JIT can fix it up? That is, suppose you were to have smp_rmb() as a eBPF instruction then the JIT (which knows what architecture it is targeting) can simply avoid emitting instructions for it.
Similarly; could something like this not also help with the spinlock thing? Use that generic test-and-set thing for the interpreter, but provide a better implementation in the JIT?
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 49 lines · Alexei Starovoitov
Quoted 44 lines · Paul E. McKenney
Quoted 26 lines · Alexei Starovoitov
Quoted 7 lines · Alexei Starovoitov
Quoted 4 lines
For programs created with
CAP_SYS_ADMIN,
things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.I think you're referring to bpf-to-bpf calls.
The limit it still the same. 4k per program including all calls. tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.Jann,
I think you meant
main:
call A
call A
call A
exit
A:
call B
call B
call B
exit
B:
call C
...Quoted 16 lines
scenario when everything fits into 4k?
Would be great if you can construct such test while we're fixing the rest of the issues brought up in this thread.
It will definitely be no more thanBPF_COMPLEXITY_LIMIT_INSNSwhich is 128k, but I wonder what will be the actual number of executed insns.
I think such clever constructed sequence can actually hit 128k executed too.
It would be awesome test to add totest_verifier.c
We have some of such pushing-the-boundary tests inlib/test_bpf.cthat are generated in assembler.
The longest takes 23853 nanoseconds, but clever bpf2bpf call hack like above withmap_updatecall in the leaf function should certainly take much longer.
I accept Paul's challenge to try to get such fancy bpf prog to take 100 millseconds :)Quoted 3 lines
Fair enough! But once you meet my challenge, the RCU CPU stall warning code will challenge you to hit 21 seconds (or only three seconds given an appropriately configured kernel). ;-)
Quoted 5 lines
if (till_stall_check < 3) { WRITE_ONCE(rcu_cpu_stall_timeout, 3); till_stall_check = 3;let's change that limit to 1 !
Heh! It was 1.5 seconds back in DYNIX/ptx. However, taking it below 3 seconds would require some other adjustments. Something about there being a lot more moving parts in the Linux kernel.
Quoted 4 lines
Seriously though folks have proposed to teach bpf verifier to sprinkle
cond_resched()automatically into bpf program when critical path through the program reaches certain insn limit. The verifier can easily be taught to compute the longest path.
Good point, for PREEMPT=n, cond_resched() will help.
Quoted 3 lines
Other folks proposed to get rid of 4k limit when prog is preemptable and executing in user context. That's when srcu will come into play.
OK, please let me know when you get to this point so that I can get the lightweight variant of SRCU moving forward.
Thanx, Paul
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Paul E. McKenneyQuoted 62 lines · Paul E. McKenney
Quoted 50 lines · Jann Horn
Quoted 41 lines · Paul E. McKenney
Quoted 31 lines · Alexei Starovoitov
Quoted 30 lines · Paul E. McKenney
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.Quoted 8 lines
Quoted 2 lines
One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Let's keep "srcu in bpf" discussion separate from
bpf_spin_lockdiscussion. bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types like bpf syscall probes that need to be able to docopy_from_userfrom bpf prog.Quoted 7 lines
Hmmm... What prevents BPF programs from looping infinitely within an RCU reader, and as you noted, preemption disabled?
If BPF programs are in fact allowed to loop infinitely, it would be very good for the health of the kernel to have preemption enabled. And to be within an SRCU read-side critical section instead of an RCU read-side critical section.
Quoted 10 lines
The BPF verifier prevents loops; this is in
push_insn()inkernel/bpf/verifier.c, which errors out with-EINVALwhen a back edge is encountered. For non-root programs, that limits the maximum number of instructions per eBPF engine execution to BPF_MAXINSNS*MAX_TAIL_CALL_CNT==4096*32==131072 (but that includes call instructions, which can cause relatively expensive operations like hash table lookups). For programs created withCAP_SYS_ADMIN, things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.
Quoted 3 lines
Whew!!! ;-)
So no more than (say) 100 milliseconds?
Depends on RLIMIT_MEMLOCK and on how hard userspace is trying to make things slow, I guess - if userspace manages to create a hashtable, with a few dozen megabytes in size, with worst-case assignment of elements to buckets (everything in a single bucket), every lookup call on that bucket becomes a linked list traversal through a list that must be stored in main memory because it's too big for the CPU caches. I don't know into how much time that translates.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 67 lines · Jann Horn
Quoted 62 lines · Paul E. McKenney
Quoted 50 lines · Jann Horn
Quoted 41 lines · Paul E. McKenney
Quoted 31 lines · Alexei Starovoitov
Quoted 30 lines · Paul E. McKenney
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
Quoted 2 lines · Alexei Starovoitov
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
Quoted 6 lines
Quoted 3 lines
- on architectures that don't support
queued_spin_locktrivial lock is used. Note thatarch_spin_lockcannot be used, since not all archs agree that zero == unlocked andsizeof(arch_spinlock_t)!=sizeof(__u32).I really don't much like direct usage of qspinlock; esp. not as a surprise.
Substituting the lightweight-reader SRCU as discussed earlier would allow use of a more generic locking primitive, for example, one that allowed blocking, at least in cases were the context allowed this.
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/linux-rcu.git
branch srcu-lr.2019.01.16a.Quoted 8 lines
Quoted 2 lines
One advantage of a more generic locking primitive would be keeping BPF programs independent of internal changes to spinlock primitives.
Let's keep "srcu in bpf" discussion separate from
bpf_spin_lockdiscussion. bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types like bpf syscall probes that need to be able to docopy_from_userfrom bpf prog.Quoted 7 lines
Hmmm... What prevents BPF programs from looping infinitely within an RCU reader, and as you noted, preemption disabled?
If BPF programs are in fact allowed to loop infinitely, it would be very good for the health of the kernel to have preemption enabled. And to be within an SRCU read-side critical section instead of an RCU read-side critical section.
Quoted 10 lines
The BPF verifier prevents loops; this is in
push_insn()inkernel/bpf/verifier.c, which errors out with-EINVALwhen a back edge is encountered. For non-root programs, that limits the maximum number of instructions per eBPF engine execution to BPF_MAXINSNS*MAX_TAIL_CALL_CNT==4096*32==131072 (but that includes call instructions, which can cause relatively expensive operations like hash table lookups). For programs created withCAP_SYS_ADMIN, things get more tricky because you can create your own functions and call them repeatedly; I'm not sure whether the pessimal runtime there becomes exponential, or whether there is some check that catches this.Quoted 3 lines
Whew!!! ;-)
So no more than (say) 100 milliseconds?
Quoted 7 lines
Depends on
RLIMIT_MEMLOCKand on how hard userspace is trying to make things slow, I guess - if userspace manages to create a hashtable, with a few dozen megabytes in size, with worst-case assignment of elements to buckets (everything in a single bucket), every lookup call on that bucket becomes a linked list traversal through a list that must be stored in main memory because it's too big for the CPU caches. I don't know into how much time that translates.
So perhaps you have a candidate BPF program for the RCU CPU stall warning challenge, then. ;-)
Thanx, Paul
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 37 lines · Peter Zijlstra
Quoted 15 lines · Alexei Starovoitov
Quoted 5 lines · Peter Zijlstra
Thanks for having kernel/locking people on Cc...
On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
Quoted 8 lines
Quoted 2 lines
Implementation details:
- on !SMPbpf_spin_lock()becomes nopBecause no BPF program is preemptible? I don't see any assertions or even a comment that says this code is non-preemptible.
AFAICT some of the
BPF_RUN_PROGthings are underrcu_read_lock()only, which is not sufficient.Quoted 6 lines
nope. all bpf prog types disable preemption. That is must have for all sorts of things to work properly.
If there is a prog type that doingrcu_read_lockonly it's a serious bug. About a year or so ago we audited everything specifically to make sure everything disables preemption before calling bpf progs. I'm pretty sure nothing crept in in the mean time.Do we want something like (the completely untested) below to avoid having to manually audit this over and over?
--- include/linux/filter.h | 2 +- include/linux/kernel.h | 9 +++++++-- kernel/sched/core.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 36 insertions(+), 3 deletions(-)include/linux/filter.h +0
-0
include/linux/filter.h struct sk_filter { · line 516
Quoted 5 lines
include/linux/filter.h +1
-1@@ -513,7 +513,7 @@ struct sk_filter {struct bpf_prog *prog; }; -#define BPF_PROG_RUN (filter, ctx) (*(filter)->bpf_func)(ctx, (filter)->insnsi) +#define BPF_PROG_RUN (filter, ctx) ({ cant_sleep(); (*(filter)->bpf_func)(ctx, (filter)->insnsi); })
That looks reasonable and I intent to apply this patch to bpf-next after testing. Can you pls reply with a sob ?
With Daniel we did a bit of git archaeology how we came to this missing preempt_disable in send side of socket filters...
The main reason is that classic BPF was preemptable from the beginning and it has SKF_AD_CPU feature for the 10+ years.
Meaning that classic BPF programs can read current cpu as a hint though they are preemptable.raw_smp_processor_id was used to avoid triggering false warning. When eBPF came along we kept it as-is during classic->extended conversion. Back then there were no per-cpu maps.
When per-cpu maps were introduced we missed preemptable sendmsg case. This cant_sleep() check should help us in the future.
The easiest fix is to add preempt_disable/enable for socket filters. There is a concern that such fix will make classic bpf non-preemptable and classic bpf can be quite cpu expensive.
For example it's allowed to have 4k classic instructions that do 'load SKF_AD_PAY_OFFSET' which will call heavy flow_dissector 4k times.
We can do preempt_disable for extended only. Then BPF_PROG_RUN macro and cant_sleep would need to be adjusted accordingly.
My preference would be to do preempt_disable for both classic and extended. Since classic is only legacy uapi at this point. Nothing on the kernel side makes it special and I'd like to keep it such.
Also on the receive side classic runs in bh, so 4k flow_dissector calls in classic has to be dealt with anyway.
Quoted 3 lines
include/linux/filter.h +0
-0> nmi checks for bpf_prog_active==0. See bpf_overflow_handler.yuck yuck yuck.. That's horrific :-( That means the whole BPF crud is unreliable and events can go randomly missing.
bpf_prog_active is the mechanism to workaround non-reentrant pieces of the kernel. Before that we couldn't do this:
sudo funccount.py *spin_lock*
Tracing 5 functions for "*spin_lock*"... Hit Ctrl-C to end.
^C
FUNC COUNTqueued_spin_lock_slowpath 682_raw_spin_lock_bh 997_raw_spin_lock_irq 10586_raw_spin_lock_irqsave 90666_raw_spin_lock 318300
Detaching...
Now we can.
This power comes with the 'horrific' caveat that two tracing progs cannot execute on the same cpu at the same time. It's not a pretty fix for the reentrancy issue.
If anyone has better ideas, I'm all ears.
Quoted 14 lines
What about the progs that run from SoftIRQ ? Since that
bpf_prog_activething isn't insideBPF_PROG_RUN()what is to stop say:reuseport_select_sock() ... BPF_PROG_RUN() bpf_spin_lock() <IRQ> ... BPF_PROG_RUN() bpf_spin_lock() // forever more </IRQ>
Quoted 3 lines
Unless you stick that
bpf_prog_activestuff insideBPF_PROG_RUNitself, I don't see how you can fundamentally avoid this happening (now or in the future).
BPF_PROG_RUN macro is used as a template for another macro:
ret = BPF_PROG_RUN_ARRAY(&bpf_prog_array, ctx, BPF_PROG_RUN); see kernel/trace/bpf_trace.c
Doing bpf_prog_active for every prog in array is too expensive.
But your issue above is valid.
We don't use bpf_prog_active for networking progs, since we allow for one level of nesting due to the classic SKF_AD_PAY_OFFSET legacy. Also we allow tracing progs to nest with networking progs. People using this actively.
Typically it's not an issue, since in networking there is no arbitrary nesting (unlike kprobe/nmi in tracing),
but for bpf_spin_lock it can be, since the same map can be shared by networking and tracing progs and above deadlock would be possible:
(first BPF_PROG_RUN will be from networking prog, then kprobe+bpf's BPF_PROG_RUN accessing the same map with bpf_spin_lock)
So for now I'm going to allow bpf_spin_lock in networking progs only, since there is no arbitrary nesting there.
And once we figure out the safety concerns for kprobe/tracepoint progs we can enable bpf_spin_lock there too.
NMI bpf progs will never have bpf_spin_lock.
re: memory model.. will reply in the other thread.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Paul E. McKenneyQuoted 11 lines · Paul E. McKenney
Quoted 10 lines
Quoted 2 lines
So no more than (say) 100 milliseconds?
Depends on
RLIMIT_MEMLOCKand on how hard userspace is trying to make things slow, I guess - if userspace manages to create a hashtable, with a few dozen megabytes in size, with worst-case assignment of elements to buckets (everything in a single bucket), every lookup call on that bucket becomes a linked list traversal through a list that must be stored in main memory because it's too big for the CPU caches. I don't know into how much time that translates.
Quoted 2 lines
So perhaps you have a candidate BPF program for the RCU CPU stall warning challenge, then. ;-)
I'd like to see one that can defeat jhash + random seed.
bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 13 lines · Peter Zijlstra
Quoted 11 lines · Alexei Starovoitov
Quoted 2 lines · Peter Zijlstra
And this would again be the moment where I go pester you about the BPF memory model :-)
hehe :)
How do you propose to define it in a way that it applies to all archs and yet doesn't penalize x86 ?
"Assume minimum execution ordering model" the way kernel does unfortunately is not usable, since bpf doesn't have a luxury of using nice #defines that convert into nops on x86.
Quoted 4 lines
Why not? Surely the JIT can fix it up? That is, suppose you were to have
smp_rmb()as a eBPF instruction then the JIT (which knows what architecture it is targeting) can simply avoid emitting instructions for it.
I'm all for adding new instructions that solve real use cases. imo bpf_spin_lock() is the first step in helping with concurrency. At plumbers conference we agreed to add new sync_fetch_and_add() and xchg() instructions. That's a second step. smp_rmb/wmb/mb should be added as well.
JITs will patch them depending on architecture.
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable with smp_rmb instructions, but we must not force weak execution on the developer.
Quoted 3 lines
Similarly; could something like this not also help with the spinlock thing? Use that generic test-and-set thing for the interpreter, but provide a better implementation in the JIT?
May be eventually. We can add cmpxchg insn, but the verifier still doesn't support loops. We made a lot of progress in bounded loop research over the last 2 years, but loops in bpf are still a year away.
We considered adding 'bpf_spin_lock' as a new instruction instead of helper call, but that approach has a lot of negatives, so we went with the helper.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 13 lines · Alexei Starovoitov
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines
Quoted 2 lines
So no more than (say) 100 milliseconds?
Depends on
RLIMIT_MEMLOCKand on how hard userspace is trying to make things slow, I guess - if userspace manages to create a hashtable, with a few dozen megabytes in size, with worst-case assignment of elements to buckets (everything in a single bucket), every lookup call on that bucket becomes a linked list traversal through a list that must be stored in main memory because it's too big for the CPU caches. I don't know into how much time that translates.
Quoted 4 lines
Quoted 2 lines
So perhaps you have a candidate BPF program for the RCU CPU stall warning challenge, then. ;-)
I'd like to see one that can defeat jhash + random seed.
Assuming that the map isn't created by root with BPF_F_ZERO_SEED:
The dumb approach would be to put things into the map, try to measure via timing/sidechannel whether you got collisions, and then keep trying different keys, and keep them if the timing indicates a collision. That'd probably be pretty slow and annoying though. Two years ago, I implemented something similar to leak information about virtual addresses from Firefox by measuring hash bucket collisions from JavaScript (but to be fair, it was easier there because you can resize the hash table):
https://thejh.net/misc/firefox-cve-2016-9904-and-cve-2017-5378-bugreport
But I think there's an easier way, too: The jhash seed is just 32 bits, and AFAICS the BPF API leaks information about that seed throughBPF_MAP_GET_NEXT_KEY: Stuff two random keys into the hash table, run BPF_MAP_GET_NEXT_KEY with attr->key==NULL, and see which key is returned. Do that around 32 times, and you should have roughly enough information to bruteforce the jhash seed? Recovering the seed should then be relatively quick, 2^32 iterations of a fast hash don't take terribly long.
That said, I don't think this is interesting enough to spend the time necessary to implement it. :P
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 41 lines · Jann Horn
Quoted 13 lines · Alexei Starovoitov
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines
Quoted 2 lines
So no more than (say) 100 milliseconds?
Depends on
RLIMIT_MEMLOCKand on how hard userspace is trying to make things slow, I guess - if userspace manages to create a hashtable, with a few dozen megabytes in size, with worst-case assignment of elements to buckets (everything in a single bucket), every lookup call on that bucket becomes a linked list traversal through a list that must be stored in main memory because it's too big for the CPU caches. I don't know into how much time that translates.Quoted 4 lines
Quoted 2 lines
So perhaps you have a candidate BPF program for the RCU CPU stall warning challenge, then. ;-)
I'd like to see one that can defeat jhash + random seed.
Assuming that the map isn't created by root with
BPF_F_ZERO_SEED:The dumb approach would be to put things into the map, try to measure via timing/sidechannel whether you got collisions, and then keep trying different keys, and keep them if the timing indicates a collision. That'd probably be pretty slow and annoying though. Two years ago, I implemented something similar to leak information about virtual addresses from Firefox by measuring hash bucket collisions from JavaScript (but to be fair, it was easier there because you can resize the hash table):
https://thejh.net/misc/firefox-cve-2016-9904-and-cve-2017-5378-bugreportBut I think there's an easier way, too: The jhash seed is just 32 bits, and AFAICS the BPF API leaks information about that seed through
BPF_MAP_GET_NEXT_KEY: Stuff two random keys into the hash table, runBPF_MAP_GET_NEXT_KEYwith attr->key==NULL, and see which key is returned. Do that around 32 times, and you should have roughly enough information to bruteforce the jhash seed? Recovering the seed should then be relatively quick, 2^32 iterations of a fast hash don't take terribly long.
Quoted 2 lines
That said, I don't think this is interesting enough to spend the time necessary to implement it. :P
Oh, and actually, you can probably also detect a collision in a simpler way:
- insert A
- insert B
- query BPF_MAP_GET_NEXT_KEY
- delete A
- delete B
- insert B
- insert A
- query BPF_MAP_GET_NEXT_KEY
- delete A
- delete B
If the two BPF_MAP_GET_NEXT_KEY queries return the same result, A and B are in different buckets; if they return different results, A and B are in the same bucket, I think?
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 19 lines · Alexei Starovoitov
Quoted 17 lines · Peter Zijlstra
Do we want something like (the completely untested) below to avoid having to manually audit this over and over?
--- include/linux/filter.h | 2 +- include/linux/kernel.h | 9 +++++++-- kernel/sched/core.c | 28 ++++++++++++++++++++++++++++ 3 files changed, 36 insertions(+), 3 deletions(-)include/linux/filter.h +0
-0@@ -513,7 +513,7 @@ struct sk_filter {struct bpf_prog *prog; };
Quoted 5 lines
include/linux/filter.h struct sk_filter { · line 516
Quoted 2 lines
include/linux/filter.h +1
-1-#define BPF_PROG_RUN (filter, ctx) (*(filter)->bpf_func)(ctx, (filter)->insnsi) +#define BPF_PROG_RUN (filter, ctx) ({ cant_sleep(); (*(filter)->bpf_func)(ctx, (filter)->insnsi); })That looks reasonable and I intent to apply this patch to bpf-next after testing. Can you pls reply with a sob ?
Sure; with the caveat that I didn't even hold it near a compiler, and it probably should grow a comment to explain the interface (similar to might_sleep):
Quoted 6 lines
The easiest fix is to add preempt_disable/enable for socket filters. There is a concern that such fix will make classic bpf non-preemptable and classic bpf can be quite cpu expensive.
Also on the receive side classic runs in bh, so 4k
flow_dissectorcalls in classic has to be dealt with anyway.
Right and agreed; per that argument the worst case (legacy) BPF was already present under non-preempt and thus making it consistently so should not affect the worst case.
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 9 lines · Alexei Starovoitov
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Alexei Starovoitov
nmi checks for bpf_prog_active==0. See
bpf_overflow_handler.yuck yuck yuck.. That's horrific :-( That means the whole BPF crud is unreliable and events can go randomly missing.
bpf_prog_activeis the mechanism to workaround non-reentrant pieces of the kernel.
'the kernel' or 'bpf' ?
perf has a recursion counter per context (task,softirq,hardirq,nmi) and that ensures that perf doesn't recurse in on itself while allowing the nesting of these contexts.
But if BPF itself is not able to deal with such nesting that won't work of course.
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 11 lines · Peter Zijlstra
Quoted 9 lines · Alexei Starovoitov
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Alexei Starovoitov
nmi checks for bpf_prog_active==0. See
bpf_overflow_handler.yuck yuck yuck.. That's horrific :-( That means the whole BPF crud is unreliable and events can go randomly missing.
bpf_prog_activeis the mechanism to workaround non-reentrant pieces of the kernel.
Quoted 8 lines
'the kernel' or 'bpf' ?
perf has a recursion counter per context (task,softirq,hardirq,nmi) and that ensures that perf doesn't recurse in on itself while allowing the nesting of these contexts.
But if BPF itself is not able to deal with such nesting that won't work of course.
Ooh, later you say:
Quoted 1 line
Also we allow tracing progs to nest with networking progs.
Which seems to suggest BPF itself can suppord (limited) nesting.
See: kernel/events/internal.h:get_recursion_context()
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 33 lines · Alexei Starovoitov
Quoted 14 lines · Peter Zijlstra
What about the progs that run from SoftIRQ ? Since that
bpf_prog_activething isn't insideBPF_PROG_RUN()what is to stop say:reuseport_select_sock() ... BPF_PROG_RUN() bpf_spin_lock() <IRQ> ... BPF_PROG_RUN() bpf_spin_lock() // forever more </IRQ>Quoted 3 lines
Unless you stick that
bpf_prog_activestuff insideBPF_PROG_RUNitself, I don't see how you can fundamentally avoid this happening (now or in the future).But your issue above is valid.
We don't use
bpf_prog_activefor networking progs, since we allow for one level of nesting due to the classicSKF_AD_PAY_OFFSETlegacy. Also we allow tracing progs to nest with networking progs. People using this actively.
Typically it's not an issue, since in networking there is no arbitrary nesting (unlike kprobe/nmi in tracing),
but forbpf_spin_lockit can be, since the same map can be shared by networking and tracing progs and above deadlock would be possible:
(firstBPF_PROG_RUNwill be from networking prog, then kprobe+bpf'sBPF_PROG_RUNaccessing the same map withbpf_spin_lock)
Quoted 2 lines
So for now I'm going to allow
bpf_spin_lockin networking progs only, since there is no arbitrary nesting there.
Isn't that still broken? AFAIU networking progs can happen in task context (TX) and SoftIRQ context (RX), which can nest.
Quoted 3 lines
And once we figure out the safety concerns for kprobe/tracepoint progs we can enable
bpf_spin_lockthere too.
NMI bpf progs will never havebpf_spin_lock.
kprobe is like NMI, since it pokes an INT3 instruction which can trigger in the middle of IRQ-disabled or even in NMIs. Similar arguments can be made for tracepoints, they can happen 'anywhere'.
Peter Zijlstra
maintainerRe: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 26 lines · Alexei Starovoitov
Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Alexei Starovoitov
Quoted 2 lines · Peter Zijlstra
And this would again be the moment where I go pester you about the BPF memory model :-)
hehe :)
How do you propose to define it in a way that it applies to all archs and yet doesn't penalize x86 ?
"Assume minimum execution ordering model" the way kernel does unfortunately is not usable, since bpf doesn't have a luxury of using nice #defines that convert into nops on x86.Quoted 4 lines
Why not? Surely the JIT can fix it up? That is, suppose you were to have
smp_rmb()as a eBPF instruction then the JIT (which knows what architecture it is targeting) can simply avoid emitting instructions for it.I'm all for adding new instructions that solve real use cases. imo
bpf_spin_lock()is the first step in helping with concurrency. At plumbers conference we agreed to add newsync_fetch_and_add()andxchg()instructions. That's a second step. smp_rmb/wmb/mb should be added as well.
JITs will patch them depending on architecture.
Quoted 7 lines
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.
Well, I agree with only introducing bits you actually need, and my smp_rmb() example might have been poorly chosen, smp_load_acquire() / smp_store_release() might have been a far more useful example.
But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
Quoted 9 lines
Quoted 3 lines
Similarly; could something like this not also help with the spinlock thing? Use that generic test-and-set thing for the interpreter, but provide a better implementation in the JIT?
May be eventually. We can add cmpxchg insn, but the verifier still doesn't support loops. We made a lot of progress in bounded loop research over the last 2 years, but loops in bpf are still a year away.
We considered adding 'bpf_spin_lock' as a new instruction instead of helper call, but that approach has a lot of negatives, so we went with the helper.
Ah, but the loop won't be in the BPF program itself. The BPF program would only have had the BPF_SPIN_LOCK instruction, the JIT them emits code similar to queued_spin_lock()/queued_spin_unlock() (or calls to out-of-line versions of them).
There isn't anything that mandates the JIT uses the exact same locking routines the interpreter does, is there?
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 18 lines · Peter Zijlstra
Quoted 17 lines · Peter Zijlstra
Quoted 9 lines · Alexei Starovoitov
Quoted 6 lines · Peter Zijlstra
Quoted 1 line · Alexei Starovoitov
nmi checks for bpf_prog_active==0. See
bpf_overflow_handler.yuck yuck yuck.. That's horrific :-( That means the whole BPF crud is unreliable and events can go randomly missing.
bpf_prog_activeis the mechanism to workaround non-reentrant pieces of the kernel.'the kernel' or 'bpf' ?
perf has a recursion counter per context (task,softirq,hardirq,nmi) and that ensures that perf doesn't recurse in on itself while allowing the nesting of these contexts.
Quoted 8 lines
Quoted 2 lines
But if BPF itself is not able to deal with such nesting that won't work of course.
Ooh, later you say:
Quoted 1 line
Also we allow tracing progs to nest with networking progs.
Which seems to suggest BPF itself can suppord (limited) nesting.
well I'm not sure where is the boundary between bpf and the kernel :) By non-reentrant I meant pieces of the kernel that bpf maps or bpf helpers may use.
For example kmalloc-style bpf map is using rcu and map update/delete do call_rcu() from inside bpf program.
If kprobe or tracepoint bpf prog is called from inner bits of __call_rcu_core and the prog is doing map update we get into recursive __call_rcu_core and things go bad.
Hence we disallow such situations when possible.
If bpf had its own infrastructure for everything then it would be easy enough to allow proper recursion using mechanism similar to what perf does with get_recursion_context.
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 34 lines · Peter Zijlstra
Quoted 33 lines · Alexei Starovoitov
Quoted 14 lines · Peter Zijlstra
What about the progs that run from SoftIRQ ? Since that
bpf_prog_activething isn't insideBPF_PROG_RUN()what is to stop say:reuseport_select_sock() ... BPF_PROG_RUN() bpf_spin_lock() <IRQ> ... BPF_PROG_RUN() bpf_spin_lock() // forever more </IRQ>Quoted 3 lines
Unless you stick that
bpf_prog_activestuff insideBPF_PROG_RUNitself, I don't see how you can fundamentally avoid this happening (now or in the future).But your issue above is valid.
We don't use
bpf_prog_activefor networking progs, since we allow for one level of nesting due to the classicSKF_AD_PAY_OFFSETlegacy. Also we allow tracing progs to nest with networking progs. People using this actively.
Typically it's not an issue, since in networking there is no arbitrary nesting (unlike kprobe/nmi in tracing),
but forbpf_spin_lockit can be, since the same map can be shared by networking and tracing progs and above deadlock would be possible:
(firstBPF_PROG_RUNwill be from networking prog, then kprobe+bpf'sBPF_PROG_RUNaccessing the same map withbpf_spin_lock)
Quoted 5 lines
Quoted 2 lines
So for now I'm going to allow
bpf_spin_lockin networking progs only, since there is no arbitrary nesting there.Isn't that still broken? AFAIU networking progs can happen in task context (TX) and SoftIRQ context (RX), which can nest.
Sure. sendmsg side of networking can be interrupted by napi receive. Both can have bpf progs attached at different points, but napi won't run when bpf prog is running, because bpf prog disables preemption.
More so the whole networking stack can be recursive and there is xmit_recursion counter to check for bad cases.
When bpf progs interact with networking they don't add to that recursion. All of *redirect*() helpers do so outside of bpf preempt disabled context. Also there is no nesting of the same networking prog type.
Like xdp/tc/lwt/cgroup bpf progs cannot be called recursively by design. There are no arbitrary entry points unlike kprobe/tracepoint.
The only nesting is when socket filter _classic_ bpf prog is calling SKF_AD_PAY_OFFSET legacy. That calls flow dissector which may call flow dissector bpf prog. Classic bpf doesn't use bpf maps, so no deadlock issues.
Quoted 7 lines
Quoted 3 lines
And once we figure out the safety concerns for kprobe/tracepoint progs we can enable
bpf_spin_lockthere too.
NMI bpf progs will never havebpf_spin_lock.kprobe is like NMI, since it pokes an INT3 instruction which can trigger in the middle of IRQ-disabled or even in NMIs. Similar arguments can be made for tracepoints, they can happen 'anywhere'.
exactly. that's why there is bpf_prog_active to protect the kernel in general for tracing bpf progs.
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 39 lines · Peter Zijlstra
Quoted 26 lines · Alexei Starovoitov
Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Alexei Starovoitov
Quoted 2 lines · Peter Zijlstra
And this would again be the moment where I go pester you about the BPF memory model :-)
hehe :)
How do you propose to define it in a way that it applies to all archs and yet doesn't penalize x86 ?
"Assume minimum execution ordering model" the way kernel does unfortunately is not usable, since bpf doesn't have a luxury of using nice #defines that convert into nops on x86.Quoted 4 lines
Why not? Surely the JIT can fix it up? That is, suppose you were to have
smp_rmb()as a eBPF instruction then the JIT (which knows what architecture it is targeting) can simply avoid emitting instructions for it.I'm all for adding new instructions that solve real use cases. imo
bpf_spin_lock()is the first step in helping with concurrency. At plumbers conference we agreed to add newsync_fetch_and_add()andxchg()instructions. That's a second step. smp_rmb/wmb/mb should be added as well.
JITs will patch them depending on architecture.Quoted 7 lines
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.
Quoted 7 lines
But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
Memory model is CPU HW design decision. BPF ISA cannot dictate HW design. We're not saying today that BPF is strongly ordered.
BPF load/stores are behaving differently on x86 vs arm64.
We can add new instructions, but we cannot 'define' how load/stores behave from memory model perspective.
For example, take atomicity of single byte load/store.
Not all archs have them atomic, but we cannot say to bpf programmers to always assume non-atomic byte loads.
Quoted 10 lines
Quoted 9 lines
Quoted 3 lines
Similarly; could something like this not also help with the spinlock thing? Use that generic test-and-set thing for the interpreter, but provide a better implementation in the JIT?
May be eventually. We can add cmpxchg insn, but the verifier still doesn't support loops. We made a lot of progress in bounded loop research over the last 2 years, but loops in bpf are still a year away.
We considered adding 'bpf_spin_lock' as a new instruction instead of helper call, but that approach has a lot of negatives, so we went with the helper.
Quoted 4 lines
Ah, but the loop won't be in the BPF program itself. The BPF program would only have had the
BPF_SPIN_LOCKinstruction, the JIT them emits code similar to queued_spin_lock()/queued_spin_unlock() (or calls to out-of-line versions of them).
As I said we considered exactly that and such approach has a lot of downsides comparing with the helper approach.
Pretty much every time new feature is added we're evaluating whether it should be new instruction or new helper. 99% of the time we go with new helper.
Quoted 2 lines
There isn't anything that mandates the JIT uses the exact same locking routines the interpreter does, is there?
sure. This bpf_spin_lock() helper can be optimized whichever way the kernel wants. Like bpf_map_lookup_elem() call is _inlined_ by the verifier for certain map types. JITs don't even need to do anything. It looks like function call from bpf prog point of view, but in JITed code it is a sequence of native instructions.
Say tomorrow we find out that bpf_prog->bpf_spin_lock()->queued_spin_lock() takes too much time then we can inline fast path of queued_spin_lock directly into bpf prog and save function call cost.
Peter Zijlstra
maintainerRe: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 8 lines · Alexei Starovoitov
Quoted 2 lines · Peter Zijlstra
Isn't that still broken? AFAIU networking progs can happen in task context (TX) and SoftIRQ context (RX), which can nest.
Sure. sendmsg side of networking can be interrupted by napi receive. Both can have bpf progs attached at different points, but napi won't run when bpf prog is running, because bpf prog disables preemption.
Disabling preemption is not sufficient, it needs to have done local_bh_disable(), which isn't unlikely given this is all networking code.
Anyway, if you're sure that's all good, I'll trust you on that. It's been a very _very_ long time since I looked at the networking code.
Peter Zijlstra
maintainerRe: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovQuoted 11 lines · Alexei Starovoitov
Quoted 4 lines · Peter Zijlstra
Ah, but the loop won't be in the BPF program itself. The BPF program would only have had the
BPF_SPIN_LOCKinstruction, the JIT them emits code similar to queued_spin_lock()/queued_spin_unlock() (or calls to out-of-line versions of them).As I said we considered exactly that and such approach has a lot of downsides comparing with the helper approach.
Pretty much every time new feature is added we're evaluating whether it should be new instruction or new helper. 99% of the time we go with new helper.
Ah; it seems I'm confused on helper vs instruction. As in, I've no idea what a helper is.
Quoted 11 lines
Quoted 2 lines
There isn't anything that mandates the JIT uses the exact same locking routines the interpreter does, is there?
sure. This
bpf_spin_lock()helper can be optimized whichever way the kernel wants. Likebpf_map_lookup_elem()call is _inlined_ by the verifier for certain map types. JITs don't even need to do anything. It looks like function call from bpf prog point of view, but in JITed code it is a sequence of native instructions.Say tomorrow we find out that bpf_prog->bpf_spin_lock()->queued_spin_lock() takes too much time then we can inline fast path of
queued_spin_lockdirectly into bpf prog and save function call cost.
OK, so then the JIT can optimize helpers. Would it not make sense to have the simple test-and-set spinlock in the generic code and have the JITs use arch_spinlock_t where appropriate?
Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
Quoted 5 lines · Alexei Starovoitov
Quoted 2 lines · Peter Zijlstra
Isn't that still broken? AFAIU networking progs can happen in task context (TX) and SoftIRQ context (RX), which can nest.
Quoted 7 lines
Quoted 3 lines
Sure. sendmsg side of networking can be interrupted by napi receive. Both can have bpf progs attached at different points, but napi won't run when bpf prog is running, because bpf prog disables preemption.
Disabling preemption is not sufficient, it needs to have done
local_bh_disable(), which isn't unlikely given this is all networking code.
right. excellent point. Since bh is not disabled nesting of the sender side socket filter is possible with receive side socket filter. Theoretically the same socket filter prog can be nested.
I believe it's fine with the current state of things including parrallel access to bpf maps
(my patch to add preempt_disable around socket filter is still needed). But this point regarding local_bh_disable changes the plans for bpf_spin_lock. We'd need local_bh_disable around socket filters and around syscall access to map with 'struct bpf_spin_lock' or two new helpers bpf_spin_lock_irqsave and corresponding verifier support.
I guess we'll argue about best option when that time comes.
For now there will be no bpf_spin_lock in socket filters and I need to add local_bh_disable for syscall access to maps with bpf_spin_lock to avoid deadlock.
I'll send a set of fixes for lockdep false positives and
respin bpf_spin_lock set.
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 8 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
Quoted 4 lines · Peter Zijlstra
Ah, but the loop won't be in the BPF program itself. The BPF program would only have had the
BPF_SPIN_LOCKinstruction, the JIT them emits code similar to queued_spin_lock()/queued_spin_unlock() (or calls to out-of-line versions of them).
Quoted 7 lines
Quoted 4 lines
As I said we considered exactly that and such approach has a lot of downsides comparing with the helper approach.
Pretty much every time new feature is added we're evaluating whether it should be new instruction or new helper. 99% of the time we go with new helper.Ah; it seems I'm confused on helper vs instruction. As in, I've no idea what a helper is.
bpf helper is a normal kernel function that can be called from bpf program. In assembler it's a direct function call.
Quoted 8 lines
Quoted 8 lines
Quoted 2 lines
There isn't anything that mandates the JIT uses the exact same locking routines the interpreter does, is there?
sure. This
bpf_spin_lock()helper can be optimized whichever way the kernel wants. Likebpf_map_lookup_elem()call is _inlined_ by the verifier for certain map types. JITs don't even need to do anything. It looks like function call from bpf prog point of view, but in JITed code it is a sequence of native instructions.
Quoted 7 lines
Quoted 3 lines
Say tomorrow we find out that bpf_prog->bpf_spin_lock()->queued_spin_lock() takes too much time then we can inline fast path of
queued_spin_lockdirectly into bpf prog and save function call cost.OK, so then the JIT can optimize helpers. Would it not make sense to have the simple test-and-set spinlock in the generic code and have the JITs use
arch_spinlock_twhere appropriate?
I think that pretty much the same as what I have with qspinlock. Instead of taking a risk how JIT writers implement bpf_spin_lock optimization I'm using qspinlock on architectures that are known to support it. So instead of starting with dumb test-and-set there will be faster qspinlock from the start on x86, arm64 and few others archs. Those are the archs we care about the most anyway. Other archs can take time to optimize it (if optimizations are necessary at all).
In general hacking JITs is much harder and more error prone than changing core and adding helpers. Hence we avoid touching JITs
as much as possible.
Like map_lookup inlining optimization we do only when JIT is on. And we do it purely in the generic core. See array_map_gen_lookup(). We generate bpf instructions only to feed them into JITs so they can replace them with native asm. That is much easier to implement correctly than if we were doing inlining in every JIT independently.
Peter Zijlstra
maintainerRe: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 14 lines · Alexei Starovoitov
Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Alexei Starovoitov
Quoted 4 lines · Peter Zijlstra
Ah, but the loop won't be in the BPF program itself. The BPF program would only have had the
BPF_SPIN_LOCKinstruction, the JIT them emits code similar to queued_spin_lock()/queued_spin_unlock() (or calls to out-of-line versions of them).As I said we considered exactly that and such approach has a lot of downsides comparing with the helper approach.
Pretty much every time new feature is added we're evaluating whether it should be new instruction or new helper. 99% of the time we go with new helper.
Quoted 5 lines
Quoted 2 lines
Ah; it seems I'm confused on helper vs instruction. As in, I've no idea what a helper is.
bpf helper is a normal kernel function that can be called from bpf program. In assembler it's a direct function call.
Ah, it is what is otherwise known as a standard library,
Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
Quoted 2 lines
There isn't anything that mandates the JIT uses the exact same locking routines the interpreter does, is there?
sure. This
bpf_spin_lock()helper can be optimized whichever way the kernel wants. Likebpf_map_lookup_elem()call is _inlined_ by the verifier for certain map types. JITs don't even need to do anything. It looks like function call from bpf prog point of view, but in JITed code it is a sequence of native instructions.Say tomorrow we find out that bpf_prog->bpf_spin_lock()->queued_spin_lock() takes too much time then we can inline fast path of
queued_spin_lockdirectly into bpf prog and save function call cost.
Quoted 7 lines
Quoted 3 lines
OK, so then the JIT can optimize helpers. Would it not make sense to have the simple test-and-set spinlock in the generic code and have the JITs use
arch_spinlock_twhere appropriate?I think that pretty much the same as what I have with qspinlock. Instead of taking a risk how JIT writers implement
bpf_spin_lockoptimization I'm using qspinlock on architectures that are known to support it.
I see the argument for it...
Quoted 7 lines
So instead of starting with dumb test-and-set there will be faster qspinlock from the start on x86, arm64 and few others archs. Those are the archs we care about the most anyway. Other archs can take time to optimize it (if optimizations are necessary at all). In general hacking JITs is much harder and more error prone than changing core and adding helpers. Hence we avoid touching JITs as much as possible.
So archs/JITs are not trivially able to override those helper functions? Because for example ARM (32bit) doesn't do qspinlock but it's arch_spinlock_t is _much_ better than a TAS lock.
Quoted 5 lines
Like
map_lookupinlining optimization we do only when JIT is on. And we do it purely in the generic core. Seearray_map_gen_lookup(). We generate bpf instructions only to feed them into JITs so they can replace them with native asm. That is much easier to implement correctly than if we were doing inlining in every JIT independently.
That seems prudent and fairly painful at the same time. I see why you would want to share as much of it as possible, but being restricted to BPF instructions seems very limiting.
Anyway, I'll not press the issue; but I do think that arch specific helpers would make sense here.
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Alexei StarovoitovHi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
Quoted 8 lines
Memory model is CPU HW design decision. BPF ISA cannot dictate HW design. We're not saying today that BPF is strongly ordered.
BPF load/stores are behaving differently on x86 vs arm64.
We can add new instructions, but we cannot 'define' how load/stores behave from memory model perspective.
For example, take atomicity of single byte load/store.
Not all archs have them atomic, but we cannot say to bpf programmers to always assume non-atomic byte loads.
Hmm, I don't think this is a good approach to take for the future of eBPF. Assuming that a desirable property of an eBPF program is portability between CPU architectures, then you're effectively forcing the programmer to "assume the worst", where the worst is almost certainly unusable for practical purposes.
One easy thing you could consider would be to allow tagging of an eBPF program with its supported target architectures (the JIT will refuse to accept it for other architectures). This would at least prevent remove the illusion of portability and force the programmer to be explicit.
However, I think we'd much better off if we defined some basic ordering primitives such as relaxed and RCpc-style acquire/release operations (including atomic RmW), single-copy atomic memory accesses up to the native machine size and a full-fence instruction. If your program uses something that the underlying arch doesn't support, then it is rejected (e.g. 64-bit READ_ONCE on a 32-bit arch)
That should map straightforwardly to all modern architectures and allow for efficient codegen on x86 and arm64. It would probably require a bunch of new BPF instructions that would be defined to be atomic (you already have XADD as a relaxed atomic add).
Apologies if this sounds patronising, but I'm keen to help figure out the semantics *now* so that we don't end up having to infer them later on, which is the usual painful case for memory models. I suspect Peter and Paul would also prefer to attack it that way around. I appreciate that the temptation is to avoid the problem by deferring to the underlying hardware memory model, but I think that will create more problems than it solves and we're here to help you get this right.
Will
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 29 lines · Will Deacon
Hi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
Quoted 6 lines
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
To reinforce this point, the Linux-kernel memory model (tools/memory-model) is that abstraction for the Linux kernel. Why not just use that for BPF?
Thanx, Paul
Quoted 42 lines
Quoted 8 lines
Memory model is CPU HW design decision. BPF ISA cannot dictate HW design. We're not saying today that BPF is strongly ordered.
BPF load/stores are behaving differently on x86 vs arm64.
We can add new instructions, but we cannot 'define' how load/stores behave from memory model perspective.
For example, take atomicity of single byte load/store.
Not all archs have them atomic, but we cannot say to bpf programmers to always assume non-atomic byte loads.Hmm, I don't think this is a good approach to take for the future of eBPF. Assuming that a desirable property of an eBPF program is portability between CPU architectures, then you're effectively forcing the programmer to "assume the worst", where the worst is almost certainly unusable for practical purposes.
One easy thing you could consider would be to allow tagging of an eBPF program with its supported target architectures (the JIT will refuse to accept it for other architectures). This would at least prevent remove the illusion of portability and force the programmer to be explicit.
However, I think we'd much better off if we defined some basic ordering primitives such as relaxed and RCpc-style acquire/release operations (including atomic RmW), single-copy atomic memory accesses up to the native machine size and a full-fence instruction. If your program uses something that the underlying arch doesn't support, then it is rejected (e.g. 64-bit
READ_ONCEon a 32-bit arch)That should map straightforwardly to all modern architectures and allow for efficient codegen on x86 and arm64. It would probably require a bunch of new BPF instructions that would be defined to be atomic (you already have XADD as a relaxed atomic add).
Apologies if this sounds patronising, but I'm keen to help figure out the semantics *now* so that we don't end up having to infer them later on, which is the usual painful case for memory models. I suspect Peter and Paul would also prefer to attack it that way around. I appreciate that the temptation is to avoid the problem by deferring to the underlying hardware memory model, but I think that will create more problems than it solves and we're here to help you get this right.
Will
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Peter ZijlstraQuoted 53 lines · Peter Zijlstra
Quoted 14 lines · Alexei Starovoitov
Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Alexei Starovoitov
Quoted 4 lines · Peter Zijlstra
Ah, but the loop won't be in the BPF program itself. The BPF program would only have had the
BPF_SPIN_LOCKinstruction, the JIT them emits code similar to queued_spin_lock()/queued_spin_unlock() (or calls to out-of-line versions of them).As I said we considered exactly that and such approach has a lot of downsides comparing with the helper approach.
Pretty much every time new feature is added we're evaluating whether it should be new instruction or new helper. 99% of the time we go with new helper.Quoted 5 lines
Quoted 2 lines
Ah; it seems I'm confused on helper vs instruction. As in, I've no idea what a helper is.
bpf helper is a normal kernel function that can be called from bpf program. In assembler it's a direct function call.
Ah, it is what is otherwise known as a standard library,
Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
Quoted 2 lines
There isn't anything that mandates the JIT uses the exact same locking routines the interpreter does, is there?
sure. This
bpf_spin_lock()helper can be optimized whichever way the kernel wants. Likebpf_map_lookup_elem()call is _inlined_ by the verifier for certain map types. JITs don't even need to do anything. It looks like function call from bpf prog point of view, but in JITed code it is a sequence of native instructions.Say tomorrow we find out that bpf_prog->bpf_spin_lock()->queued_spin_lock() takes too much time then we can inline fast path of
queued_spin_lockdirectly into bpf prog and save function call cost.Quoted 7 lines
Quoted 3 lines
OK, so then the JIT can optimize helpers. Would it not make sense to have the simple test-and-set spinlock in the generic code and have the JITs use
arch_spinlock_twhere appropriate?I think that pretty much the same as what I have with qspinlock. Instead of taking a risk how JIT writers implement
bpf_spin_lockoptimization I'm using qspinlock on architectures that are known to support it.I see the argument for it...
Quoted 7 lines
So instead of starting with dumb test-and-set there will be faster qspinlock from the start on x86, arm64 and few others archs. Those are the archs we care about the most anyway. Other archs can take time to optimize it (if optimizations are necessary at all). In general hacking JITs is much harder and more error prone than changing core and adding helpers. Hence we avoid touching JITs as much as possible.
Quoted 3 lines
So archs/JITs are not trivially able to override those helper functions? Because for example ARM (32bit) doesn't do qspinlock but it's
arch_spinlock_tis _much_ better than a TAS lock.
JITs can override. There is no 'ready to use' facility for all types of helpers to do that, but it's easy enough to add. Having said that I'm going to reject arm32 JIT patches that are trying to use arch_spinlock instead of generic bpf_spin_lock. The last thing arm32 jit needs is this type of optimization. Other JITs is a different story.
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Will DeaconQuoted 2 lines · Will Deacon
Assuming that a desirable property of an eBPF program is portability between CPU architectures, then you're effectively forcing the programmer to "assume
that is fundamental misunderstanding that being thrown in this thread. bpf is not fixated on portability.
All projects that tried to come up with universal byte code miserably failed. bpf program compiled for big endian won't load on little.
bpf program designed to be used on x86 will work horribly slow on nfp. It will work, but will be innefficient. Hence we have alu32 mode in llvm. More so maps don't map one to one to all archs either.
per-cpu map doesn't exist on nfp. we're still figuring out
an equivalent for it for nfp.
So, no, programs are not portable across architectures.
The programmer cannot assume that.
They could be portable in some cases and we're trying to keep portability as much as possible, but it's not a "desirable property" that we're going to sacrifice performance and usability for it.
If it helps look at bpf as a safe kernel module.
Does given kernel module work on all archs? No. Sometimes users only need to recompile it and sometimes do heavy changes. smp_mb and load acquire are the list things to worry about when folks trying to make
such 'safe kernel module' work on different archs.
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
In reply to Paul E. McKenneyQuoted 37 lines · Paul E. McKenney
Quoted 29 lines · Will Deacon
Hi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
Quoted 6 lines
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
Quoted 2 lines
To reinforce this point, the Linux-kernel memory model (
tools/memory-model) is that abstraction for the Linux kernel. Why not just use that for BPF?
I already answered this earlier in the thread.
tldr: not going to sacrifice performance.
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 38 lines · Alexei Starovoitov
Quoted 37 lines · Paul E. McKenney
Quoted 35 lines · Will Deacon
Hi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
Quoted 5 lines
Quoted 2 lines
To reinforce this point, the Linux-kernel memory model (
tools/memory-model) is that abstraction for the Linux kernel. Why not just use that for BPF?I already answered this earlier in the thread.
tldr: not going to sacrifice performance.
Understood.
But can we at least say that where there are no performance consequences, BPF should follow LKMM? You already mentioned smp_load_acquire() and smp_store_release(), but the void atomics (e.g., atomic_inc()) should also work because they don't provide any ordering guarantees. The _relaxed(), _release(), and _acquire() variants of the value-returning atomics should be just fine as well.
The other value-returning atomics have strong ordering, which is fine on many systems, but potentially suboptimal for the weakly ordered ones. Though you have to have pretty good locality of reference to be able to see the difference, because otherwise cache-miss overhead dominates.
Things like cmpxchg() don't seem to fit BPF because they are normally used in spin loops, though there are some non-spinning use cases.
You correctly pointed out that READ_ONCE() and WRITE_ONCE() are suboptimal on systems that don't support all sizes of loads, but I bet that there are some sizes for which they are just fine across systems, for example, pointer size and int size.
Does that help? Or am I missing additional cases where performance could be degraded?
Thanx, Paul
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 62 lines · Paul E. McKenney
Quoted 38 lines · Alexei Starovoitov
Quoted 37 lines · Paul E. McKenney
Quoted 35 lines · Will Deacon
Hi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
Quoted 5 lines
Quoted 2 lines
To reinforce this point, the Linux-kernel memory model (
tools/memory-model) is that abstraction for the Linux kernel. Why not just use that for BPF?I already answered this earlier in the thread.
tldr: not going to sacrifice performance.Understood.
But can we at least say that where there are no performance consequences, BPF should follow LKMM? You already mentioned
smp_load_acquire()andsmp_store_release(), but the void atomics (e.g.,atomic_inc()) should also work because they don't provide any ordering guarantees. The_relaxed(),_release(), and_acquire()variants of the value-returning atomics should be just fine as well.The other value-returning atomics have strong ordering, which is fine on many systems, but potentially suboptimal for the weakly ordered ones. Though you have to have pretty good locality of reference to be able to see the difference, because otherwise cache-miss overhead dominates.
Things like
cmpxchg()don't seem to fit BPF because they are normally used in spin loops, though there are some non-spinning use cases.
Quoted 7 lines
You correctly pointed out that
READ_ONCE()andWRITE_ONCE()are suboptimal on systems that don't support all sizes of loads, but I bet that there are some sizes for which they are just fine across systems, for example, pointer size and int size.Does that help? Or am I missing additional cases where performance could be degraded?
bpf doesn't have smp_load_acquire, atomic_fetch_add, xchg, fence instructions. They can be added step by step. That's easy.
I believe folks already started working on adding atomic_fetch_add. What I have problem with is making a statement today that bpf's end goal is LKMM. Even after adding all sorts of instructions it may not be practical.
Only when real use case requires adding new instruction we do it. Do you have a bpf program that needs smp_load_acquire ?
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 71 lines · Alexei Starovoitov
Quoted 62 lines · Paul E. McKenney
Quoted 38 lines · Alexei Starovoitov
Quoted 37 lines · Paul E. McKenney
Quoted 35 lines · Will Deacon
Hi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
Quoted 5 lines
Quoted 2 lines
To reinforce this point, the Linux-kernel memory model (
tools/memory-model) is that abstraction for the Linux kernel. Why not just use that for BPF?I already answered this earlier in the thread.
tldr: not going to sacrifice performance.Understood.
But can we at least say that where there are no performance consequences, BPF should follow LKMM? You already mentioned
smp_load_acquire()andsmp_store_release(), but the void atomics (e.g.,atomic_inc()) should also work because they don't provide any ordering guarantees. The_relaxed(),_release(), and_acquire()variants of the value-returning atomics should be just fine as well.The other value-returning atomics have strong ordering, which is fine on many systems, but potentially suboptimal for the weakly ordered ones. Though you have to have pretty good locality of reference to be able to see the difference, because otherwise cache-miss overhead dominates.
Things like
cmpxchg()don't seem to fit BPF because they are normally used in spin loops, though there are some non-spinning use cases.Quoted 7 lines
You correctly pointed out that
READ_ONCE()andWRITE_ONCE()are suboptimal on systems that don't support all sizes of loads, but I bet that there are some sizes for which they are just fine across systems, for example, pointer size and int size.Does that help? Or am I missing additional cases where performance could be degraded?
Quoted 8 lines
bpf doesn't have
smp_load_acquire,atomic_fetch_add, xchg, fence instructions. They can be added step by step. That's easy.
I believe folks already started working on addingatomic_fetch_add. What I have problem with is making a statement today that bpf's end goal is LKMM. Even after adding all sorts of instructions it may not be practical.
Only when real use case requires adding new instruction we do it. Do you have a bpf program that needssmp_load_acquire?
We seem to be talking past each other. Let me try again...
I believe that if BPF adds a given concurrency feature, it should follow LKMM unless there is some specific problem with its doing so.
My paragraphs in my previous email list the concurrency features BPF could follow LKMM without penalty, should BPF choose to add them.
Does that help?
Thanx, Paul
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 83 lines · Paul E. McKenney
Quoted 71 lines · Alexei Starovoitov
Quoted 62 lines · Paul E. McKenney
Quoted 38 lines · Alexei Starovoitov
Quoted 37 lines · Paul E. McKenney
Quoted 35 lines · Will Deacon
Hi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
Quoted 5 lines
Quoted 2 lines
To reinforce this point, the Linux-kernel memory model (
tools/memory-model) is that abstraction for the Linux kernel. Why not just use that for BPF?I already answered this earlier in the thread.
tldr: not going to sacrifice performance.Understood.
But can we at least say that where there are no performance consequences, BPF should follow LKMM? You already mentioned
smp_load_acquire()andsmp_store_release(), but the void atomics (e.g.,atomic_inc()) should also work because they don't provide any ordering guarantees. The_relaxed(),_release(), and_acquire()variants of the value-returning atomics should be just fine as well.The other value-returning atomics have strong ordering, which is fine on many systems, but potentially suboptimal for the weakly ordered ones. Though you have to have pretty good locality of reference to be able to see the difference, because otherwise cache-miss overhead dominates.
Things like
cmpxchg()don't seem to fit BPF because they are normally used in spin loops, though there are some non-spinning use cases.Quoted 7 lines
You correctly pointed out that
READ_ONCE()andWRITE_ONCE()are suboptimal on systems that don't support all sizes of loads, but I bet that there are some sizes for which they are just fine across systems, for example, pointer size and int size.Does that help? Or am I missing additional cases where performance could be degraded?
Quoted 8 lines
bpf doesn't have
smp_load_acquire,atomic_fetch_add, xchg, fence instructions. They can be added step by step. That's easy.
I believe folks already started working on addingatomic_fetch_add. What I have problem with is making a statement today that bpf's end goal is LKMM. Even after adding all sorts of instructions it may not be practical.
Only when real use case requires adding new instruction we do it. Do you have a bpf program that needssmp_load_acquire?We seem to be talking past each other. Let me try again...
Quoted 7 lines
I believe that if BPF adds a given concurrency feature, it should follow LKMM unless there is some specific problem with its doing so.
My paragraphs in my previous email list the concurrency features BPF could follow LKMM without penalty, should BPF choose to add them.
Does that help?
yeah. we're talking past each other indeed.
Doesn't look like that more emails will help.
Let's resolve it either f2f during next conference or join our bi-weekly bpf bluejeans call Wed 11am pacific.
Reminders and links are on this list
https://lists.iovisor.org/g/iovisor-dev/messages?p=created,0,,20,2,0,0
Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock
Quoted 90 lines · Alexei Starovoitov
Quoted 89 lines · Paul E. McKenney
Quoted 71 lines · Alexei Starovoitov
Quoted 62 lines · Paul E. McKenney
Quoted 38 lines · Alexei Starovoitov
Quoted 37 lines · Paul E. McKenney
Quoted 35 lines · Will Deacon
Hi Alexei,
Quoted 17 lines · Alexei Starovoitov
Quoted 16 lines · Peter Zijlstra
Quoted 7 lines · Alexei Starovoitov
What I want to avoid is to define the whole execution ordering model upfront. We cannot say that BPF ISA is weakly ordered like alpha.
Most of the bpf progs are written and running on x86. We shouldn't twist bpf developer's arm by artificially relaxing memory model. BPF memory model is equal to memory model of underlying architecture. What we can do is to make it bpf progs a bit more portable withsmp_rmbinstructions, but we must not force weak execution on the developer.Well, I agree with only introducing bits you actually need, and my
smp_rmb()example might have been poorly chosen,smp_load_acquire()/smp_store_release()might have been a far more useful example.But I disagree with the last part; we have to pick a model now; otherwise you'll pain yourself into a corner.
Quoted 8 lines
Quoted 4 lines
Also; Alpha isn't very relevant these days; however ARM64 does seem to be gaining a lot of attention and that is very much a weak architecture. Adding strongly ordered assumptions to BPF now, will penalize them in the long run.
arm64 is gaining attention just like riscV is gaining it too. BPF jit for arm64 is very solid, while BPF jit for riscV is being worked on. BPF is not picking sides in CPU HW and ISA battles.
It's not about picking a side, it's about providing an abstraction of the various CPU architectures out there so that the programmer doesn't need to worry about where their program may run. Hell, even if you just said "eBPF follows x86 semantics" that would be better than saying nothing (and then we could have a discussion about whether x86 semantics are really what you want).
Quoted 5 lines
Quoted 2 lines
To reinforce this point, the Linux-kernel memory model (
tools/memory-model) is that abstraction for the Linux kernel. Why not just use that for BPF?I already answered this earlier in the thread.
tldr: not going to sacrifice performance.Understood.
But can we at least say that where there are no performance consequences, BPF should follow LKMM? You already mentioned
smp_load_acquire()andsmp_store_release(), but the void atomics (e.g.,atomic_inc()) should also work because they don't provide any ordering guarantees. The_relaxed(),_release(), and_acquire()variants of the value-returning atomics should be just fine as well.The other value-returning atomics have strong ordering, which is fine on many systems, but potentially suboptimal for the weakly ordered ones. Though you have to have pretty good locality of reference to be able to see the difference, because otherwise cache-miss overhead dominates.
Things like
cmpxchg()don't seem to fit BPF because they are normally used in spin loops, though there are some non-spinning use cases.Quoted 7 lines
You correctly pointed out that
READ_ONCE()andWRITE_ONCE()are suboptimal on systems that don't support all sizes of loads, but I bet that there are some sizes for which they are just fine across systems, for example, pointer size and int size.Does that help? Or am I missing additional cases where performance could be degraded?
Quoted 8 lines
bpf doesn't have
smp_load_acquire,atomic_fetch_add, xchg, fence instructions. They can be added step by step. That's easy.
I believe folks already started working on addingatomic_fetch_add. What I have problem with is making a statement today that bpf's end goal is LKMM. Even after adding all sorts of instructions it may not be practical.
Only when real use case requires adding new instruction we do it. Do you have a bpf program that needssmp_load_acquire?We seem to be talking past each other. Let me try again...
I believe that if BPF adds a given concurrency feature, it should follow LKMM unless there is some specific problem with its doing so.
My paragraphs in my previous email list the concurrency features BPF could follow LKMM without penalty, should BPF choose to add them.
Quoted 8 lines
Quoted 1 line
Does that help?
yeah. we're talking past each other indeed.
Doesn't look like that more emails will help.
Let's resolve it either f2f during next conference or join our bi-weekly bpf bluejeans call Wed 11am pacific.
Reminders and links are on this list
https://lists.iovisor.org/g/iovisor-dev/messages?p=created,0,,20,2,0,0
There is an instance of this meeting next week, correct?
If so, I could make the instance on Feb 27th, assuming that I have access to bluejeans.
Thanx, Paul