Skip to contentSkip to conversation

introduce bpf_spin_lock

PATCH Superseded Alexei Starovoitov 8 participants 62 messages Jan 24, 2019 – Feb 1, 2019

Subsystems (8)

v4 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
author maintainer
#59 lore raw

PATCH v4 5/9 selftests/bpf: add bpf_spin_lock C test

In reply to Alexei Starovoitov

add 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
index 70229de510f5..fcfda51406f9 100644
@@ -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
index 6c77cf7bedce..6a0ce0f055c5 100644
@@ -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
author maintainer
#57 lore raw

PATCH v4 3/9 tools/bpf: sync include/uapi/linux/bpf.h

In reply to Alexei Starovoitov

sync bpf.h

---
 tools/include/uapi/linux/bpf.h | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
tools/include/uapi/linux/bpf.h +6 -1
index 91c43884f295..30f9dfd40f13 100644
@@ -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
author maintainer
#61 lore raw

PATCH v4 7/9 tools/bpf: sync uapi/bpf.h

In reply to Alexei Starovoitov

add 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
index 30f9dfd40f13..c23eaa284a45 100644
@@ -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
author maintainer
#1 lore raw

PATCH v4 1/9 bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov

Introduce 'struct bpf_spin_lock' and bpf_spin_lock/unlock() helpers to let bpf program serialize access to other variables.

Example:

struct hash_elem {
    int cnt;
    struct bpf_spin_lock lock;
};
struct hash_elem * val = bpf_map_lookup_elem(&hash_map, &key);
if (val) {
    bpf_spin_lock(&val->lock);
    val->cnt++;
    bpf_spin_unlock(&val->lock);
}

Restrictions and safety checks:
- bpf_spin_lock is only allowed inside HASH and ARRAY maps.
- BTF description of the map is mandatory for safety analysis.
- bpf program can take one bpf_spin_lock at a time, since two or more can cause dead locks.
- only one 'struct bpf_spin_lock' is allowed per map element.
It drastically simplifies implementation yet allows bpf program to use any number of bpf_spin_locks.
- when bpf_spin_lock is taken the calls (either bpf2bpf or helpers) are not allowed.
- bpf program must bpf_spin_unlock() before return.
- bpf program can access 'struct bpf_spin_lock' only via bpf_spin_lock()/bpf_spin_unlock() helpers.
- load/store into 'struct bpf_spin_lock lock;' field is not allowed.
- to use bpf_spin_lock() helper the BTF description of map value must be a struct and have 'struct bpf_spin_lock anyname;' field at the top level. Nested lock inside another struct is not allowed.
- syscall map_lookup doesn't copy bpf_spin_lock field to user space.
- syscall map_update and program map_update do not update bpf_spin_lock field.
- bpf_spin_lock cannot be on the stack or inside networking packet. bpf_spin_lock can only be inside HASH or ARRAY map value.
- bpf_spin_lock is available to root only and to all program types.
- 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
index 3851529062ec..ee0352bd728f 100644
@@ -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
index 0620e418dde5..69f7a3449eda 100644
@@ -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
index 12502e25e767..455d31b55828 100644
@@ -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
index 91c43884f295..30f9dfd40f13 100644
@@ -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
index 25632a75d630..d6d979910a2a 100644
@@ -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
index 2a81b8af3748..2b44eca22ef8 100644
@@ -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
index 4b7c76765d9d..48a41bf65e1b 100644
@@ -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
index 99d243e1ad6e..920eff1b677b 100644
@@ -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
index b155cd17c1bd..ebf0a673cb83 100644
@@ -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
index 2b3b436ef545..24a5d874d156 100644
@@ -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
author maintainer
#56 lore raw

PATCH v4 2/9 bpf: add support for bpf_spin_lock to cgroup local storage

In reply to Alexei Starovoitov

Allow '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
index 07a34ef562a0..0295427f06e2 100644
@@ -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
index ebf0a673cb83..b29e6dc44650 100644
@@ -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
index f372904fa691..bfd6bebca911 100644
@@ -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
author maintainer
#60 lore raw

PATCH v4 6/9 bpf: introduce BPF_F_LOCK flag

In reply to Alexei Starovoitov

Introduce 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
index ee0352bd728f..34a517137b63 100644
@@ -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
index 30f9dfd40f13..c23eaa284a45 100644
@@ -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
index d6d979910a2a..c72e0d8e1e65 100644
@@ -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
index 2e98e4caf5aa..60e475bcb708 100644
@@ -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
index 0295427f06e2..6b572e2de7fb 100644
@@ -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
index b29e6dc44650..0834958f1dc4 100644
@@ -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 flags
 
 static 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

author maintainer
#0 lore raw

v4 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
author maintainer
#58 lore raw

PATCH 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
index 4f67afeec8d9..4b29dba7ffff 100644
@@ -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
maintainer
#2 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov

Thanks for having kernel/locking people on Cc...

Quoted 2 lines · Alexei Starovoitov

Implementation details:
- on !SMP bpf_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_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).

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:
- 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.

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
index a74972b07e74..2e98e4caf5aa 100644
@@ -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,
+};
maintainer
#3 lore raw

Re: [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 !SMP bpf_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_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).

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:
- 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.

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?

#4 lore raw

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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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_UNLOCKED is for.

I get the sizeof(__u32) thing, but why not key off of that?

Quoted 5 lines

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.

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?

#19 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
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 !SMP bpf_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.

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_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).

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?

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:
- 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.

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
index a74972b07e74..2e98e4caf5aa 100644
@@ -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.

#5 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Paul E. McKenney
Quoted 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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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.

#20 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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 !SMP bpf_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 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 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.

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...

#6 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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_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.

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

#7 lore raw

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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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_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.

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.

#22 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 7 lines · Alexei Starovoitov
Quoted 1 line · Peter Zijlstra

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.

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 79000
#23 lore raw

Re: [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_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.

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

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.

#8 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Jann Horn
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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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_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.

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() 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).

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.

#24 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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_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 9 lines
Quoted 3 lines

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

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.

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.

#21 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Jann Horn
Quoted 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 !SMP bpf_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 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 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 3 lines

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...

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.

#25 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Eric Dumazet
Quoted 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_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 9 lines
Quoted 3 lines

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

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.

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 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

argh. lookup cmd is missing __this_cpu_inc(bpf_prog_active); like update/delete do. Will fix.

Quoted 2 lines

It seems pcpu_freelist_pop and pcpu_freelist_push are not NMI safe, so what prevents bad things to happen ?

nmi checks for bpf_prog_active==0. See bpf_overflow_handler.

#13 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Jann Horn
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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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_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.

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() 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.

Whew!!! ;-)

So no more than (say) 100 milliseconds?

Thanx, Paul

#9 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to 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
...

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 :)

#10 lore raw

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 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 :)

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

#11 lore raw

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 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 :)

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.

maintainer
#26 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 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 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

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 calls bpf_stackmap_copy which can call pcpu_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_pop and pcpu_freelist_push are 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.

maintainer
#27 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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 !SMP bpf_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 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 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.

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
index d531d4250bff..4ab51e78da36 100644
@@ -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
index 8f0e68e250a7..f4cea3260a28 100644
@@ -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
index ee7763641348..799c285f4e0f 100644
@@ -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
maintainer
#37 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 12 lines · Alexei Starovoitov
Quoted 10 lines · Peter Zijlstra
Quoted 3 lines

- 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).

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.

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 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).

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 and dumb_spin_lock on archs that dont.

Another option is use to arch_spinlock_t when its sizeof==4

That's what I meant.

Quoted 5 lines

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.

Quoted 11 lines

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.

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..

maintainer
#38 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 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_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.

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).

maintainer
#39 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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.

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?

#12 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 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 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 :)

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

#14 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Paul E. McKenney
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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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_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.

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() 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.

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.

#15 lore raw

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 !SMP bpf_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 6 lines
Quoted 6 lines
Quoted 3 lines

- 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).

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_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.

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() 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.

Quoted 3 lines

Whew!!! ;-)

So no more than (say) 100 milliseconds?

Quoted 7 lines

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.

So perhaps you have a candidate BPF program for the RCU CPU stall warning challenge, then. ;-)

Thanx, Paul

#28 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
Quoted 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 !SMP bpf_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 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 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.

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
index d531d4250bff..4ab51e78da36 100644

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 COUNT
queued_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_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>
Quoted 3 lines

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).

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.

#16 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Paul E. McKenney
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines
Quoted 2 lines

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.

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.

#40 lore raw

bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
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 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.

#17 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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_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.

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 through
BPF_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

#18 lore raw

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_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.

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 through
BPF_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.

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?

maintainer
#29 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 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
index d531d4250bff..4ab51e78da36 100644
@@ -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_dissector calls 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.

maintainer
#30 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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_active is 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.

maintainer
#31 lore raw

Re: [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_active is 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()

maintainer
#33 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 33 lines · Alexei Starovoitov
Quoted 14 lines · Peter Zijlstra

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>
Quoted 3 lines

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).

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)

Quoted 2 lines

So for now I'm going to allow bpf_spin_lock in 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_lock there too.
NMI bpf progs will never have bpf_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'.

maintainer
#41 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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 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.

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 with smp_rmb instructions, 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?

#32 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
Quoted 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_active is 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.

#34 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
Quoted 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_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>
Quoted 3 lines

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).

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)

Quoted 5 lines
Quoted 2 lines

So for now I'm going to allow bpf_spin_lock in 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_lock there too.
NMI bpf progs will never have bpf_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.

#42 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
Quoted 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 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.

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 with smp_rmb instructions, 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_LOCK instruction, 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.

maintainer
#35 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
Quoted 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.

maintainer
#43 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov
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_LOCK instruction, 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. 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.

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?

#36 lore raw

Re: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
Quoted 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.

#44 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
Quoted 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_LOCK instruction, 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. 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.

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_lock directly 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?

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.

maintainer
#45 lore raw

Re: 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_LOCK instruction, 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. 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.

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_t where 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.

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_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.

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.

#47 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Alexei Starovoitov

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 with smp_rmb instructions, 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

#48 lore raw

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 with smp_rmb instructions, 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_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

#46 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Peter Zijlstra
Quoted 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_LOCK instruction, 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. 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.

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_t where 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.

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_t is _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.

#55 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Will Deacon
Quoted 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.

#49 lore raw

Re: bpf memory model. Was: [PATCH v4 bpf-next 1/9] bpf: introduce bpf_spin_lock

In reply to Paul E. McKenney
Quoted 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 with smp_rmb instructions, 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.

#50 lore raw

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 with smp_rmb instructions, 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

#51 lore raw

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 with smp_rmb instructions, 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.

Quoted 7 lines

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?

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 ?

#52 lore raw

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 with smp_rmb instructions, 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.

Quoted 7 lines

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?

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 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 ?

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

#53 lore raw

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 with smp_rmb instructions, 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.

Quoted 7 lines

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?

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 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 ?

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

#54 lore raw

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 with smp_rmb instructions, 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.

Quoted 7 lines

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?

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 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 ?

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