[PATCH v4 bpf-next 0/9] introduce bpf_spin_lock

[PATCH v4 bpf-next 0/9] introduce bpf_spin_lock

[Alexei Starovoitov]

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

-- 
2.17.1

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

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

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 include/linux/bpf.h          |  37 ++++++++-
 include/linux/bpf_verifier.h |   1 +
 include/linux/btf.h          |   1 +
 include/uapi/linux/bpf.h     |   7 +-
 kernel/bpf/arraymap.c        |   7 +-
 kernel/bpf/btf.c             |  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(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 3851529062ec..ee0352bd728f 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -72,14 +72,15 @@ struct bpf_map {
 	u32 value_size;
 	u32 max_entries;
 	u32 map_flags;
-	u32 pages;
+	int spin_lock_off; /* >=0 valid offset, <0 error */
 	u32 id;
 	int numa_node;
 	u32 btf_key_type_id;
 	u32 btf_value_type_id;
 	struct btf *btf;
+	u32 pages;
 	bool unpriv_array;
-	/* 55 bytes hole */
+	/* 51 bytes hole */
 
 	/* The 3rd and 4th cacheline with misc members to avoid false sharing
 	 * particularly with refcounting.
@@ -91,6 +92,34 @@ struct bpf_map {
 	char name[BPF_OBJ_NAME_LEN];
 };
 
+static inline bool map_value_has_spin_lock(const struct bpf_map *map)
+{
+	return map->spin_lock_off >= 0;
+}
+
+static inline void check_and_init_map_lock(struct bpf_map *map, void *dst)
+{
+	if (likely(!map_value_has_spin_lock(map)))
+		return;
+	*(struct bpf_spin_lock *)(dst + map->spin_lock_off) =
+		(struct bpf_spin_lock){};
+}
+
+/* copy everything but bpf_spin_lock */
+static inline void copy_map_value(struct bpf_map *map, void *dst, void *src)
+{
+	if (unlikely(map_value_has_spin_lock(map))) {
+		u32 off = map->spin_lock_off;
+
+		memcpy(dst, src, off);
+		memcpy(dst + off + sizeof(struct bpf_spin_lock),
+		       src + off + sizeof(struct bpf_spin_lock),
+		       map->value_size - off - sizeof(struct bpf_spin_lock));
+	} else {
+		memcpy(dst, src, map->value_size);
+	}
+}
+
 struct bpf_offload_dev;
 struct bpf_offloaded_map;
 
@@ -162,6 +191,7 @@ enum bpf_arg_type {
 	ARG_PTR_TO_CTX,		/* pointer to context */
 	ARG_ANYTHING,		/* any (initialized) argument is ok */
 	ARG_PTR_TO_SOCKET,	/* pointer to bpf_sock */
+	ARG_PTR_TO_SPIN_LOCK,	/* pointer to bpf_spin_lock */
 };
 
 /* type of values returned from helper functions */
@@ -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. */
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 0620e418dde5..69f7a3449eda 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -148,6 +148,7 @@ struct bpf_verifier_state {
 	/* call stack tracking */
 	struct bpf_func_state *frame[MAX_CALL_FRAMES];
 	u32 curframe;
+	u32 active_spin_lock;
 	bool speculative;
 };
 
diff --git a/include/linux/btf.h b/include/linux/btf.h
index 12502e25e767..455d31b55828 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -50,6 +50,7 @@ u32 btf_id(const struct btf *btf);
 bool btf_member_is_reg_int(const struct btf *btf, const struct btf_type *s,
 			   const struct btf_member *m,
 			   u32 expected_offset, u32 expected_size);
+int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t);
 
 #ifdef CONFIG_BPF_SYSCALL
 const struct btf_type *btf_type_by_id(const struct btf *btf, u32 type_id);
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 91c43884f295..30f9dfd40f13 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -2421,7 +2421,9 @@ union bpf_attr {
 	FN(map_peek_elem),		\
 	FN(msg_push_data),		\
 	FN(msg_pop_data),		\
-	FN(rc_pointer_rel),
+	FN(rc_pointer_rel),		\
+	FN(spin_lock),			\
+	FN(spin_unlock),
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
  * function eBPF program intends to call
@@ -3054,4 +3056,7 @@ struct bpf_line_info {
 	__u32	line_col;
 };
 
+struct bpf_spin_lock {
+	__u32	val;
+};
 #endif /* _UAPI__LINUX_BPF_H__ */
diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index 25632a75d630..d6d979910a2a 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -270,9 +270,10 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
 		memcpy(this_cpu_ptr(array->pptrs[index & array->index_mask]),
 		       value, map->value_size);
 	else
-		memcpy(array->value +
-		       array->elem_size * (index & array->index_mask),
-		       value, map->value_size);
+		copy_map_value(map,
+			       array->value +
+			       array->elem_size * (index & array->index_mask),
+			       value);
 	return 0;
 }
 
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 022ef9ca1296..03b1a7a6195c 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -355,6 +355,11 @@ static bool btf_type_is_struct(const struct btf_type *t)
 	return kind == BTF_KIND_STRUCT || kind == BTF_KIND_UNION;
 }
 
+static bool __btf_type_is_struct(const struct btf_type *t)
+{
+	return BTF_INFO_KIND(t->info) == BTF_KIND_STRUCT;
+}
+
 static bool btf_type_is_array(const struct btf_type *t)
 {
 	return BTF_INFO_KIND(t->info) == BTF_KIND_ARRAY;
@@ -2045,6 +2050,43 @@ static void btf_struct_log(struct btf_verifier_env *env,
 	btf_verifier_log(env, "size=%u vlen=%u", t->size, btf_type_vlen(t));
 }
 
+/* find 'struct bpf_spin_lock' in map value.
+ * return >= 0 offset if found
+ * and < 0 in case of error
+ */
+int btf_find_spin_lock(const struct btf *btf, const struct btf_type *t)
+{
+	const struct btf_member *member;
+	u32 i, off = -ENOENT;
+
+	if (!__btf_type_is_struct(t))
+		return -EINVAL;
+
+	for_each_member(i, t, member) {
+		const struct btf_type *member_type = btf_type_by_id(btf,
+								    member->type);
+		if (!__btf_type_is_struct(member_type))
+			continue;
+		if (member_type->size != sizeof(struct bpf_spin_lock))
+			continue;
+		if (strcmp(__btf_name_by_offset(btf, member_type->name_off),
+			   "bpf_spin_lock"))
+			continue;
+		if (off != -ENOENT)
+			/* only one 'struct bpf_spin_lock' is allowed */
+			return -E2BIG;
+		off = btf_member_bit_offset(t, member);
+		if (off % 8)
+			/* valid C code cannot generate such BTF */
+			return -EINVAL;
+		off /= 8;
+		if (off % __alignof__(struct bpf_spin_lock))
+			/* valid struct bpf_spin_lock will be 4 byte aligned */
+			return -EINVAL;
+	}
+	return off;
+}
+
 static void btf_struct_seq_show(const struct btf *btf, const struct btf_type *t,
 				u32 type_id, void *data, u8 bits_offset,
 				struct seq_file *m)
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 2a81b8af3748..2b44eca22ef8 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -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;
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 4b7c76765d9d..48a41bf65e1b 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -770,6 +770,8 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 			l_new = ERR_PTR(-ENOMEM);
 			goto dec_count;
 		}
+		check_and_init_map_lock(&htab->map,
+					l_new->key + round_up(key_size, 8));
 	}
 
 	memcpy(l_new->key, key, key_size);
@@ -792,7 +794,9 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 		if (!prealloc)
 			htab_elem_set_ptr(l_new, key_size, pptr);
 	} else {
-		memcpy(l_new->key + round_up(key_size, 8), value, size);
+		copy_map_value(&htab->map,
+			       l_new->key + round_up(key_size, 8),
+			       value);
 	}
 
 	l_new->hash = hash;
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index a74972b07e74..2e98e4caf5aa 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -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;
+
+	queued_spin_unlock(qlock);
+#else
+	struct dumb_spin_lock *qlock = (void *)lock;
+
+	atomic_set(&qlock->val, 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,
+};
+
 #ifdef CONFIG_CGROUPS
 BPF_CALL_0(bpf_get_current_cgroup_id)
 {
diff --git a/kernel/bpf/map_in_map.c b/kernel/bpf/map_in_map.c
index 99d243e1ad6e..920eff1b677b 100644
--- a/kernel/bpf/map_in_map.c
+++ b/kernel/bpf/map_in_map.c
@@ -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);
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index b155cd17c1bd..ebf0a673cb83 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -463,7 +463,7 @@ int map_check_no_btf(const struct bpf_map *map,
 	return -ENOTSUPP;
 }
 
-static int map_check_btf(const struct bpf_map *map, const struct btf *btf,
+static int map_check_btf(struct bpf_map *map, const struct btf *btf,
 			 u32 btf_key_id, u32 btf_value_id)
 {
 	const struct btf_type *key_type, *value_type;
@@ -478,6 +478,21 @@ static int map_check_btf(const struct bpf_map *map, const struct btf *btf,
 	if (!value_type || value_size != map->value_size)
 		return -EINVAL;
 
+	map->spin_lock_off = btf_find_spin_lock(btf, value_type);
+
+	if (map_value_has_spin_lock(map)) {
+		if (map->map_type != BPF_MAP_TYPE_HASH &&
+		    map->map_type != BPF_MAP_TYPE_ARRAY)
+			return -ENOTSUPP;
+		if (map->spin_lock_off + sizeof(struct bpf_spin_lock) >
+		    map->value_size) {
+			WARN_ONCE(1,
+				  "verifier bug spin_lock_off %d value_size %d\n",
+				  map->spin_lock_off, map->value_size);
+			return -EFAULT;
+		}
+	}
+
 	if (map->ops->map_check_btf)
 		ret = map->ops->map_check_btf(map, btf, key_type, value_type);
 
@@ -542,6 +557,8 @@ static int map_create(union bpf_attr *attr)
 		map->btf = btf;
 		map->btf_key_type_id = attr->btf_key_type_id;
 		map->btf_value_type_id = attr->btf_value_type_id;
+	} else {
+		map->spin_lock_off = -EINVAL;
 	}
 
 	err = security_bpf_map_alloc(map);
@@ -740,7 +757,7 @@ static int map_lookup_elem(union bpf_attr *attr)
 			err = -ENOENT;
 		} else {
 			err = 0;
-			memcpy(value, ptr, value_size);
+			copy_map_value(map, value, ptr);
 		}
 		rcu_read_unlock();
 	}
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8cfe39ef770f..f372904fa691 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -213,6 +213,7 @@ struct bpf_call_arg_meta {
 	s64 msize_smax_value;
 	u64 msize_umax_value;
 	int ptr_id;
+	int func_id;
 };
 
 static DEFINE_MUTEX(bpf_verifier_lock);
@@ -351,6 +352,12 @@ static bool reg_is_refcounted(const struct bpf_reg_state *reg)
 	return type_is_refcounted(reg->type);
 }
 
+static bool reg_may_point_to_spin_lock(const struct bpf_reg_state *reg)
+{
+	return reg->type == PTR_TO_MAP_VALUE &&
+		map_value_has_spin_lock(reg->map_ptr);
+}
+
 static bool reg_is_refcounted_or_null(const struct bpf_reg_state *reg)
 {
 	return type_is_refcounted_or_null(reg->type);
@@ -712,6 +719,7 @@ static int copy_verifier_state(struct bpf_verifier_state *dst_state,
 	}
 	dst_state->speculative = src->speculative;
 	dst_state->curframe = src->curframe;
+	dst_state->active_spin_lock = src->active_spin_lock;
 	for (i = 0; i <= src->curframe; i++) {
 		dst = dst_state->frame[i];
 		if (!dst) {
@@ -1483,6 +1491,21 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno,
 	if (err)
 		verbose(env, "R%d max value is outside of the array range\n",
 			regno);
+
+	if (map_value_has_spin_lock(reg->map_ptr)) {
+		u32 lock = reg->map_ptr->spin_lock_off;
+
+		/* if any part of struct bpf_spin_lock can be touched by
+		 * load/store reject this program
+		 */
+		if ((reg->smin_value + off <= lock &&
+		     lock < reg->umax_value + off + size) ||
+		    (reg->smin_value + off < lock + sizeof(struct bpf_spin_lock) &&
+		     lock + sizeof(struct bpf_spin_lock) <= reg->umax_value + off + size)) {
+			verbose(env, "bpf_spin_lock cannot be accessed directly by load/store\n");
+			return -EACCES;
+		}
+	}
 	return err;
 }
 
@@ -2192,6 +2215,91 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
 	}
 }
 
+/* Implementation details:
+ * bpf_map_lookup returns PTR_TO_MAP_VALUE_OR_NULL
+ * Two bpf_map_lookups (even with the same key) will have different reg->id.
+ * For traditional PTR_TO_MAP_VALUE the verifier clears reg->id after
+ * value_or_null->value transition, since the verifier only cares about
+ * the range of access to valid map value pointer and doesn't care about actual
+ * address of the map element.
+ * For maps with 'struct bpf_spin_lock' inside map value the verifier keeps
+ * reg->id > 0 after value_or_null->value transition. By doing so
+ * two bpf_map_lookups will be considered two different pointers that
+ * point to different bpf_spin_locks.
+ * The verifier allows taking only one bpf_spin_lock at a time to avoid
+ * dead-locks.
+ * Since only one bpf_spin_lock is allowed the checks are simpler than
+ * reg_is_refcounted() logic. The verifier needs to remember only
+ * one spin_lock instead of array of acquired_refs.
+ * cur_state->active_spin_lock remembers which map value element got locked
+ * and clears it after bpf_spin_unlock.
+ */
+static int process_spin_lock(struct bpf_verifier_env *env, int regno,
+			     bool is_lock)
+{
+	struct bpf_reg_state *regs = cur_regs(env), *reg = &regs[regno];
+	struct bpf_verifier_state *cur = env->cur_state;
+	bool is_const = tnum_is_const(reg->var_off);
+	struct bpf_map *map = reg->map_ptr;
+	u64 val = reg->var_off.value;
+
+	if (reg->type != PTR_TO_MAP_VALUE) {
+		verbose(env, "R%d is not a pointer to map_value\n", regno);
+		return -EINVAL;
+	}
+	if (!is_const) {
+		verbose(env,
+			"R%d doesn't have constant offset. bpf_spin_lock has to be at the constant offset\n",
+			regno);
+		return -EINVAL;
+	}
+	if (!map->btf) {
+		verbose(env,
+			"map '%s' has to have BTF in order to use bpf_spin_lock\n",
+			map->name);
+		return -EINVAL;
+	}
+	if (!map_value_has_spin_lock(map)) {
+		if (map->spin_lock_off == -E2BIG)
+			verbose(env,
+				"map '%s' has more than one 'struct bpf_spin_lock'\n",
+				map->name);
+		else if (map->spin_lock_off == -ENOENT)
+			verbose(env,
+				"map '%s' doesn't have 'struct bpf_spin_lock'\n",
+				map->name);
+		else
+			verbose(env,
+				"map '%s' is not a struct type or bpf_spin_lock is mangled\n",
+				map->name);
+		return -EINVAL;
+	}
+	if (map->spin_lock_off != val + reg->off) {
+		verbose(env, "off %lld doesn't point to 'struct bpf_spin_lock'\n",
+			val + reg->off);
+		return -EINVAL;
+	}
+	if (is_lock) {
+		if (cur->active_spin_lock) {
+			verbose(env,
+				"Locking two bpf_spin_locks are not allowed\n");
+			return -EINVAL;
+		}
+		cur->active_spin_lock = reg->id;
+	} else {
+		if (!cur->active_spin_lock) {
+			verbose(env, "bpf_spin_unlock without taking a lock\n");
+			return -EINVAL;
+		}
+		if (cur->active_spin_lock != reg->id) {
+			verbose(env, "bpf_spin_unlock of different lock\n");
+			return -EINVAL;
+		}
+		cur->active_spin_lock = 0;
+	}
+	return 0;
+}
+
 static bool arg_type_is_mem_ptr(enum bpf_arg_type type)
 {
 	return type == ARG_PTR_TO_MEM ||
@@ -2268,6 +2376,17 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno,
 			return -EFAULT;
 		}
 		meta->ptr_id = reg->id;
+	} else if (arg_type == ARG_PTR_TO_SPIN_LOCK) {
+		if (meta->func_id == BPF_FUNC_spin_lock) {
+			if (process_spin_lock(env, regno, true))
+				return -EACCES;
+		} else if (meta->func_id == BPF_FUNC_spin_unlock) {
+			if (process_spin_lock(env, regno, false))
+				return -EACCES;
+		} else {
+			verbose(env, "verifier internal error\n");
+			return -EFAULT;
+		}
 	} else if (arg_type_is_mem_ptr(arg_type)) {
 		expected_type = PTR_TO_STACK;
 		/* One exception here. In case function allows for NULL to be
@@ -2887,6 +3006,7 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
 		return err;
 	}
 
+	meta.func_id = func_id;
 	/* check args */
 	err = check_func_arg(env, BPF_REG_1, fn->arg1_type, &meta);
 	if (err)
@@ -4344,7 +4464,8 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,
 		} else if (reg->type == PTR_TO_SOCKET_OR_NULL) {
 			reg->type = PTR_TO_SOCKET;
 		}
-		if (is_null || !reg_is_refcounted(reg)) {
+		if (is_null || !(reg_is_refcounted(reg) ||
+				 reg_may_point_to_spin_lock(reg))) {
 			/* We don't need id from this point onwards anymore,
 			 * thus we should better reset it, so that state
 			 * pruning has chances to take effect.
@@ -4713,6 +4834,11 @@ static int check_ld_abs(struct bpf_verifier_env *env, struct bpf_insn *insn)
 		return err;
 	}
 
+	if (env->cur_state->active_spin_lock) {
+		verbose(env, "BPF_LD_[ABS|IND] cannot be used inside bpf_spin_lock-ed region\n");
+		return -EINVAL;
+	}
+
 	if (regs[BPF_REG_6].type != PTR_TO_CTX) {
 		verbose(env,
 			"at the time of BPF_LD_ABS|IND R6 != pointer to skb\n");
@@ -5448,8 +5574,11 @@ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
 	case PTR_TO_MAP_VALUE:
 		/* If the new min/max/var_off satisfy the old ones and
 		 * everything else matches, we are OK.
-		 * We don't care about the 'id' value, because nothing
-		 * uses it for PTR_TO_MAP_VALUE (only for ..._OR_NULL)
+		 * 'id' is not compared, since it's only used for maps with
+		 * bpf_spin_lock inside map element and in such cases if
+		 * the rest of the prog is valid for one map element then
+		 * it's valid for all map elements regardless of the key
+		 * used in bpf_map_lookup()
 		 */
 		return memcmp(rold, rcur, offsetof(struct bpf_reg_state, id)) == 0 &&
 		       range_within(rold, rcur) &&
@@ -5652,6 +5781,9 @@ static bool states_equal(struct bpf_verifier_env *env,
 	if (old->speculative && !cur->speculative)
 		return false;
 
+	if (old->active_spin_lock != cur->active_spin_lock)
+		return false;
+
 	/* for states to be equal callsites have to be the same
 	 * and all frame states need to be equivalent
 	 */
@@ -6069,6 +6201,12 @@ static int do_check(struct bpf_verifier_env *env)
 					return -EINVAL;
 				}
 
+				if (env->cur_state->active_spin_lock &&
+				    (insn->src_reg == BPF_PSEUDO_CALL ||
+				     insn->imm != BPF_FUNC_spin_unlock)) {
+					verbose(env, "function calls are not allowed while holding a lock\n");
+					return -EINVAL;
+				}
 				if (insn->src_reg == BPF_PSEUDO_CALL)
 					err = check_func_call(env, insn, &env->insn_idx);
 				else
@@ -6097,6 +6235,11 @@ static int do_check(struct bpf_verifier_env *env)
 					return -EINVAL;
 				}
 
+				if (env->cur_state->active_spin_lock) {
+					verbose(env, "bpf_spin_unlock is missing\n");
+					return -EINVAL;
+				}
+
 				if (state->curframe) {
 					/* exit from nested function */
 					env->prev_insn_idx = env->insn_idx;
diff --git a/net/core/filter.c b/net/core/filter.c
index 2b3b436ef545..24a5d874d156 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -5306,10 +5306,20 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 		return &bpf_tail_call_proto;
 	case BPF_FUNC_ktime_get_ns:
 		return &bpf_ktime_get_ns_proto;
+	default:
+		break;
+	}
+
+	if (!capable(CAP_SYS_ADMIN))
+		return NULL;
+
+	switch (func_id) {
+	case BPF_FUNC_spin_lock:
+		return &bpf_spin_lock_proto;
+	case BPF_FUNC_spin_unlock:
+		return &bpf_spin_unlock_proto;
 	case BPF_FUNC_trace_printk:
-		if (capable(CAP_SYS_ADMIN))
-			return bpf_get_trace_printk_proto();
-		/* else: fall through */
+		return bpf_get_trace_printk_proto();
 	default:
 		return NULL;
 	}
-- 
2.17.1

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

[Peter Zijlstra]

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

On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:

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

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

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


> diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> index a74972b07e74..2e98e4caf5aa 100644
> --- a/kernel/bpf/helpers.c
> +++ b/kernel/bpf/helpers.c
> @@ -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;
> +
> +	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 :-)

> +#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,
> +};

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

[Peter Zijlstra]

On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> 
> Thanks for having kernel/locking people on Cc...
> 
> On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> 
> > 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.
> 
> > - 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?
> 
> > 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?
> 

Also; what about BPF running from NMI context and using locks?

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

[Paul E. McKenney]

On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > 
> > Thanks for having kernel/locking people on Cc...
> > 
> > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > 
> > > 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.
> > 
> > > - 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

> > 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?
> > 
> > > 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?
> 
> Also; what about BPF running from NMI context and using locks?
> 

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

[Alexei Starovoitov]

On Thu, Jan 24, 2019 at 03:42:32PM -0800, Paul E. McKenney wrote:
> On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > 
> > > Thanks for having kernel/locking people on Cc...
> > > 
> > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > 
> > > > 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.
> > > 
> > > > - 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.

Let's keep "srcu in bpf" discussion separate from bpf_spin_lock discussion.
bpf is not switching to srcu any time soon.
If/when it happens it will be only for certain prog+map types
like bpf syscall probes that need to be able to do copy_from_user
from bpf prog.

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

[Paul E. McKenney]

On Thu, Jan 24, 2019 at 04:05:16PM -0800, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 03:42:32PM -0800, Paul E. McKenney wrote:
> > On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > > 
> > > > Thanks for having kernel/locking people on Cc...
> > > > 
> > > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > > 
> > > > > 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.
> > > > 
> > > > > - 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.
> 
> 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

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

[Jann Horn]

On Fri, Jan 25, 2019 at 2:22 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote:
> On Thu, Jan 24, 2019 at 04:05:16PM -0800, Alexei Starovoitov wrote:
> > On Thu, Jan 24, 2019 at 03:42:32PM -0800, Paul E. McKenney wrote:
> > > On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> > > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > > >
> > > > > Thanks for having kernel/locking people on Cc...
> > > > >
> > > > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > > >
> > > > > > 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.
> > > > >
> > > > > > - 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.
> >
> > 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.

The BPF verifier prevents loops; this is in push_insn() in
kernel/bpf/verifier.c, which errors out with -EINVAL when a back edge
is encountered. For non-root programs, that limits the maximum number
of instructions per eBPF engine execution to
BPF_MAXINSNS*MAX_TAIL_CALL_CNT==4096*32==131072 (but that includes
call instructions, which can cause relatively expensive operations
like hash table lookups). For programs created with CAP_SYS_ADMIN,
things get more tricky because you can create your own functions and
call them repeatedly; I'm not sure whether the pessimal runtime there
becomes exponential, or whether there is some check that catches this.

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

[Alexei Starovoitov]

On Fri, Jan 25, 2019 at 02:46:55AM +0100, Jann Horn wrote:
> On Fri, Jan 25, 2019 at 2:22 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote:
> > On Thu, Jan 24, 2019 at 04:05:16PM -0800, Alexei Starovoitov wrote:
> > > On Thu, Jan 24, 2019 at 03:42:32PM -0800, Paul E. McKenney wrote:
> > > > On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> > > > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > > > >
> > > > > > Thanks for having kernel/locking people on Cc...
> > > > > >
> > > > > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > > > >
> > > > > > > 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.
> > > > > >
> > > > > > > - 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.
> > >
> > > 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.
> 
> 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.

> For programs created with CAP_SYS_ADMIN,
> things get more tricky because you can create your own functions and
> call them repeatedly; I'm not sure whether the pessimal runtime there
> becomes exponential, or whether there is some check that catches this.

I think you're referring to bpf-to-bpf calls.
The limit it still the same. 4k per program including all calls.
tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.

Note that classic bpf has the same 4k limit and it can call
expensive functions too via SKF_AD extensions.

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

[Alexei Starovoitov]

On 1/24/19 6:38 PM, Alexei Starovoitov wrote:
>> For programs created with CAP_SYS_ADMIN,
>> things get more tricky because you can create your own functions and
>> call them repeatedly; I'm not sure whether the pessimal runtime there
>> becomes exponential, or whether there is some check that catches this.
> I think you're referring to bpf-to-bpf calls.
> The limit it still the same. 4k per program including all calls.
> tail calls are not allowed when bpf-to-bpf is used. So no 32 multiplier.

Jann,

I think you meant
main:
call A
call A
call A
exit
A:
call B
call B
call B
exit
B:
call C
...

scenario when everything fits into 4k?
Would be great if you can construct such test while we're fixing
the rest of the issues brought up in this thread.
It will definitely be no more than BPF_COMPLEXITY_LIMIT_INSNS
which is 128k, but I wonder what will be the actual number of
executed insns.
I think such clever constructed sequence can actually
hit 128k executed too.
It would be awesome test to add to test_verifier.c
We have some of such pushing-the-boundary tests in lib/test_bpf.c
that are generated in assembler.
The longest takes 23853 nanoseconds, but clever bpf2bpf call hack
like above with map_update call in the leaf function should
certainly take much longer.
I accept Paul's challenge to try to get such fancy bpf prog
to take 100 millseconds :)

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

[Paul E. McKenney]

On Fri, Jan 25, 2019 at 04:27:02AM +0000, Alexei Starovoitov wrote:
> On 1/24/19 6:38 PM, Alexei Starovoitov wrote:
> >> 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 :)

Fair enough!  But once you meet my challenge, the RCU CPU stall warning
code will challenge you to hit 21 seconds (or only three seconds given
an appropriately configured kernel).  ;-)

							Thanx, Paul

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

[Alexei Starovoitov]

On 1/24/19 8:31 PM, Paul E. McKenney wrote:
> On Fri, Jan 25, 2019 at 04:27:02AM +0000, Alexei Starovoitov wrote:
>> On 1/24/19 6:38 PM, Alexei Starovoitov wrote:
>>>> 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 :)
> 
> 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.

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

[Paul E. McKenney]

On Fri, Jan 25, 2019 at 04:47:20AM +0000, Alexei Starovoitov wrote:
> On 1/24/19 8:31 PM, Paul E. McKenney wrote:
> > On Fri, Jan 25, 2019 at 04:27:02AM +0000, Alexei Starovoitov wrote:
> >> On 1/24/19 6:38 PM, Alexei Starovoitov wrote:
> >>>> 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 :)
> > 
> > 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 !

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.

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

> Other folks proposed to get rid of 4k limit when prog
> is preemptable and executing in user context.
> That's when srcu will come into play.

OK, please let me know when you get to this point so that I can get
the lightweight variant of SRCU moving forward.

							Thanx, Paul

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

[Paul E. McKenney]

On Fri, Jan 25, 2019 at 02:46:55AM +0100, Jann Horn wrote:
> On Fri, Jan 25, 2019 at 2:22 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote:
> > On Thu, Jan 24, 2019 at 04:05:16PM -0800, Alexei Starovoitov wrote:
> > > On Thu, Jan 24, 2019 at 03:42:32PM -0800, Paul E. McKenney wrote:
> > > > On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> > > > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > > > >
> > > > > > Thanks for having kernel/locking people on Cc...
> > > > > >
> > > > > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > > > >
> > > > > > > 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.
> > > > > >
> > > > > > > - 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.
> > >
> > > 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.
> 
> 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

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

[Jann Horn]

On Fri, Jan 25, 2019 at 5:12 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote:
> On Fri, Jan 25, 2019 at 02:46:55AM +0100, Jann Horn wrote:
> > On Fri, Jan 25, 2019 at 2:22 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote:
> > > On Thu, Jan 24, 2019 at 04:05:16PM -0800, Alexei Starovoitov wrote:
> > > > On Thu, Jan 24, 2019 at 03:42:32PM -0800, Paul E. McKenney wrote:
> > > > > On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> > > > > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > > > > >
> > > > > > > Thanks for having kernel/locking people on Cc...
> > > > > > >
> > > > > > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > > > > >
> > > > > > > > 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.
> > > > > > >
> > > > > > > > - 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.
> > > >
> > > > 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.
> >
> > 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?

Depends on RLIMIT_MEMLOCK and on how hard userspace is trying to make
things slow, I guess - if userspace manages to create a hashtable,
with a few dozen megabytes in size, with worst-case assignment of
elements to buckets (everything in a single bucket), every lookup call
on that bucket becomes a linked list traversal through a list that
must be stored in main memory because it's too big for the CPU caches.
I don't know into how much time that translates.

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

[Paul E. McKenney]

On Fri, Jan 25, 2019 at 05:18:12PM +0100, Jann Horn wrote:
> On Fri, Jan 25, 2019 at 5:12 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote:
> > On Fri, Jan 25, 2019 at 02:46:55AM +0100, Jann Horn wrote:
> > > On Fri, Jan 25, 2019 at 2:22 AM Paul E. McKenney <paulmck@linux.ibm.com> wrote:
> > > > On Thu, Jan 24, 2019 at 04:05:16PM -0800, Alexei Starovoitov wrote:
> > > > > On Thu, Jan 24, 2019 at 03:42:32PM -0800, Paul E. McKenney wrote:
> > > > > > On Thu, Jan 24, 2019 at 07:56:52PM +0100, Peter Zijlstra wrote:
> > > > > > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > > > > > >
> > > > > > > > Thanks for having kernel/locking people on Cc...
> > > > > > > >
> > > > > > > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > > > > > >
> > > > > > > > > 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.
> > > > > > > >
> > > > > > > > > - 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.
> > > > >
> > > > > 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.
> > >
> > > 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?
> 
> 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

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

[Alexei Starovoitov]

On Fri, Jan 25, 2019 at 02:51:12PM -0800, Paul E. McKenney wrote:
> > >
> > > 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.
> 
> 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.

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

[Jann Horn]

On Sat, Jan 26, 2019 at 12:44 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Jan 25, 2019 at 02:51:12PM -0800, Paul E. McKenney wrote:
> > > >
> > > > 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.
> >
> > 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

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

[Jann Horn]

On Sat, Jan 26, 2019 at 1:43 AM Jann Horn <jannh@google.com> wrote:
> On Sat, Jan 26, 2019 at 12:44 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, Jan 25, 2019 at 02:51:12PM -0800, Paul E. McKenney wrote:
> > > > >
> > > > > 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.
> > >
> > > 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

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?

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

[Alexei Starovoitov]

On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> 
> Thanks for having kernel/locking people on Cc...
> 
> On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> 
> > 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.

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

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

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

> > diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
> > index a74972b07e74..2e98e4caf5aa 100644
> > --- a/kernel/bpf/helpers.c
> > +++ b/kernel/bpf/helpers.c
> > @@ -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;
> > +
> > +	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.

> And this would again be the moment where I go pester you about the BPF
> memory model :-)

hehe :)
How do you propose to define it in a way that it applies to all archs
and yet doesn't penalize x86 ?
"Assume minimum execution ordering model" the way kernel does
unfortunately is not usable, since bpf doesn't have a luxury
of using nice #defines that convert into nops on x86.

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

[Jann Horn]

On Fri, Jan 25, 2019 at 12:59 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > Thanks for having kernel/locking people on Cc...
> >
> > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> >
> > > 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.

Hmm? What about
unix_dgram_sendmsg->sk_filter->sk_filter_trim_cap->bpf_prog_run_save_cb->BPF_PROG_RUN?
That just holds rcu_read_lock(), as far as I can tell...

In general, for tricky rules about locks that must be held or contexts
that code can run in, it makes sense to use some check that yells when
that rule is being violated, at least in debug builds. Otherwise it's
too easy for bugs to creep in...

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

[Alexei Starovoitov]

On Fri, Jan 25, 2019 at 01:18:04AM +0100, Jann Horn wrote:
> On Fri, Jan 25, 2019 at 12:59 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > Thanks for having kernel/locking people on Cc...
> > >
> > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > >
> > > > 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.
> 
> 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.

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

[Eric Dumazet]

On 01/24/2019 03:58 PM, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:

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

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

[Alexei Starovoitov]

On Thu, Jan 24, 2019 at 06:29:55PM -0800, Eric Dumazet wrote:
> 
> 
> On 01/24/2019 03:58 PM, Alexei Starovoitov wrote:
> > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> 
> >> 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

it's a known false positive.
https://lkml.org/lkml/2018/7/25/756
and the same answer as before:
we're not going to penalize performance to shut up false positive.

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

[Eric Dumazet]

On 01/24/2019 06:34 PM, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 06:29:55PM -0800, Eric Dumazet wrote:
>>
>>
>> On 01/24/2019 03:58 PM, Alexei Starovoitov wrote:
>>> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
>>
>>>> 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
> 
> 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.

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

[Alexei Starovoitov]

On Thu, Jan 24, 2019 at 06:44:20PM -0800, Eric Dumazet wrote:
> 
> 
> On 01/24/2019 06:34 PM, Alexei Starovoitov wrote:
> > On Thu, Jan 24, 2019 at 06:29:55PM -0800, Eric Dumazet wrote:
> >>
> >>
> >> On 01/24/2019 03:58 PM, Alexei Starovoitov wrote:
> >>> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> >>
> >>>> 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
> > 
> > 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 ?

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.

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

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

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

[Peter Zijlstra]

On Thu, Jan 24, 2019 at 06:57:00PM -0800, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 06:44:20PM -0800, Eric Dumazet wrote:
> > 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.

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

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

[Peter Zijlstra]

On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > 
> > Thanks for having kernel/locking people on Cc...
> > 
> > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > 
> > > 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.

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

diff --git a/include/linux/filter.h b/include/linux/filter.h
index d531d4250bff..4ab51e78da36 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -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
 
diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index 8f0e68e250a7..f4cea3260a28 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -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
 
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index ee7763641348..799c285f4e0f 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -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

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

[Alexei Starovoitov]

On Fri, Jan 25, 2019 at 10:10:57AM +0100, Peter Zijlstra wrote:
> On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > 
> > > Thanks for having kernel/locking people on Cc...
> > > 
> > > On Wed, Jan 23, 2019 at 08:13:55PM -0800, Alexei Starovoitov wrote:
> > > 
> > > > 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.
> 
> 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(-)
> 
> diff --git a/include/linux/filter.h b/include/linux/filter.h
> index d531d4250bff..4ab51e78da36 100644
> --- a/include/linux/filter.h
> +++ b/include/linux/filter.h
> @@ -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.

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

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

BPF_PROG_RUN macro is used as a template for another macro:
ret = BPF_PROG_RUN_ARRAY(&bpf_prog_array, ctx, BPF_PROG_RUN);
see kernel/trace/bpf_trace.c
Doing bpf_prog_active for every prog in array is too expensive.

But your issue above is valid.
We don't use bpf_prog_active for networking progs, since we allow
for one level of nesting due to the classic SKF_AD_PAY_OFFSET legacy.
Also we allow tracing progs to nest with networking progs.
People using this actively.
Typically it's not an issue, since in networking there is no
arbitrary nesting (unlike kprobe/nmi in tracing),
but for bpf_spin_lock it can be, since the same map can be shared
by networking and tracing progs and above deadlock would be possible:
(first BPF_PROG_RUN will be from networking prog, then kprobe+bpf's
BPF_PROG_RUN accessing the same map with bpf_spin_lock)

So for now I'm going to allow bpf_spin_lock in networking progs only,
since there is no arbitrary nesting there.
And once we figure out the safety concerns for kprobe/tracepoint progs
we can enable bpf_spin_lock there too.
NMI bpf progs will never have bpf_spin_lock.

re: memory model.. will reply in the other thread.

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

[Peter Zijlstra]

On Fri, Jan 25, 2019 at 03:42:43PM -0800, Alexei Starovoitov wrote:
> On Fri, Jan 25, 2019 at 10:10:57AM +0100, Peter Zijlstra wrote:

> > 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(-)
> > 
> > diff --git a/include/linux/filter.h b/include/linux/filter.h
> > index d531d4250bff..4ab51e78da36 100644
> > --- a/include/linux/filter.h
> > +++ b/include/linux/filter.h
> > @@ -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 ?

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

Suggested-by: Jann Horn <jannh@google.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>

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

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

[Peter Zijlstra]

On Fri, Jan 25, 2019 at 03:42:43PM -0800, Alexei Starovoitov wrote:
> On Fri, Jan 25, 2019 at 10:10:57AM +0100, Peter Zijlstra wrote:
> > On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:

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

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

[Peter Zijlstra]

On Mon, Jan 28, 2019 at 09:31:23AM +0100, Peter Zijlstra wrote:
> On Fri, Jan 25, 2019 at 03:42:43PM -0800, Alexei Starovoitov wrote:
> > On Fri, Jan 25, 2019 at 10:10:57AM +0100, Peter Zijlstra wrote:
> > > On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> 
> > >  > 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.

Ooh, later you say:

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

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

[Alexei Starovoitov]

On Mon, Jan 28, 2019 at 09:35:08AM +0100, Peter Zijlstra wrote:
> On Mon, Jan 28, 2019 at 09:31:23AM +0100, Peter Zijlstra wrote:
> > On Fri, Jan 25, 2019 at 03:42:43PM -0800, Alexei Starovoitov wrote:
> > > On Fri, Jan 25, 2019 at 10:10:57AM +0100, Peter Zijlstra wrote:
> > > > On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> > 
> > > >  > 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.
> 
> Ooh, later you say:
> 
> > Also we allow tracing progs to nest with networking progs.
> 
> Which seems to suggest BPF itself can suppord (limited) nesting.

well I'm not sure where is the boundary between bpf and the kernel :)
By non-reentrant I meant pieces of the kernel that bpf maps
or bpf helpers may use.
For example kmalloc-style bpf map is using rcu and map update/delete
do call_rcu() from inside bpf program.
If kprobe or tracepoint bpf prog is called from inner bits of
__call_rcu_core and the prog is doing map update we get into
recursive __call_rcu_core and things go bad.
Hence we disallow such situations when possible.
If bpf had its own infrastructure for everything then it would be
easy enough to allow proper recursion using mechanism similar
to what perf does with get_recursion_context.

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

[Peter Zijlstra]

On Fri, Jan 25, 2019 at 03:42:43PM -0800, Alexei Starovoitov wrote:
> On Fri, Jan 25, 2019 at 10:10:57AM +0100, Peter Zijlstra wrote:

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

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

Isn't that still broken? AFAIU networking progs can happen in task
context (TX) and SoftIRQ context (RX), which can nest.

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

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

[Alexei Starovoitov]

On Mon, Jan 28, 2019 at 09:43:10AM +0100, Peter Zijlstra wrote:
> On Fri, Jan 25, 2019 at 03:42:43PM -0800, Alexei Starovoitov wrote:
> > On Fri, Jan 25, 2019 at 10:10:57AM +0100, Peter Zijlstra wrote:
> 
> > > 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).
> 
> > 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.
> 
> 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.

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

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

[Peter Zijlstra]

On Mon, Jan 28, 2019 at 01:37:12PM -0800, Alexei Starovoitov wrote:
> On Mon, Jan 28, 2019 at 09:43:10AM +0100, Peter Zijlstra wrote:

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

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

[Alexei Starovoitov]

On Tue, Jan 29, 2019 at 09:59:03AM +0100, Peter Zijlstra wrote:
> On Mon, Jan 28, 2019 at 01:37:12PM -0800, Alexei Starovoitov wrote:
> > On Mon, Jan 28, 2019 at 09:43:10AM +0100, Peter Zijlstra wrote:
> 
> > > 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.

right. excellent point. Since bh is not disabled nesting of the sender side
socket filter is possible with receive side socket filter.
Theoretically the same socket filter prog can be nested.
I believe it's fine with the current state of things including
parrallel access to bpf maps
(my patch to add preempt_disable around socket filter is still needed).
But this point regarding local_bh_disable changes the plans for bpf_spin_lock.
We'd need local_bh_disable around socket filters and around syscall access
to map with 'struct bpf_spin_lock' or two new helpers bpf_spin_lock_irqsave
and corresponding verifier support.
I guess we'll argue about best option when that time comes.
For now there will be no bpf_spin_lock in socket filters and I need to
add local_bh_disable for syscall access to maps with bpf_spin_lock
to avoid deadlock.
I'll send a set of fixes for lockdep false positives and
respin bpf_spin_lock set.

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

[Peter Zijlstra]

On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:

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

PowerPC has 8 bytes for some config options IIRC.

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

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

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

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

[Peter Zijlstra]

On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:

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

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

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

[Peter Zijlstra]

On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:

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

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

[Alexei Starovoitov]

On Fri, Jan 25, 2019 at 11:23:12AM +0100, Peter Zijlstra wrote:
> On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> 
> > > 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.

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.

> Similarly; could something like this not also help with the spinlock
> thing? Use that generic test-and-set thing for the interpreter, but
> provide a better implementation in the JIT?

May be eventually. We can add cmpxchg insn, but the verifier still
doesn't support loops. We made a lot of progress in bounded loop research
over the last 2 years, but loops in bpf are still a year away.
We considered adding 'bpf_spin_lock' as a new instruction instead of helper call,
but that approach has a lot of negatives, so we went with the helper.

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

[Peter Zijlstra]

On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> On Fri, Jan 25, 2019 at 11:23:12AM +0100, Peter Zijlstra wrote:
> > On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > 
> > > > 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.
> 
> 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.

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.

> > Similarly; could something like this not also help with the spinlock
> > thing? Use that generic test-and-set thing for the interpreter, but
> > provide a better implementation in the JIT?
> 
> May be eventually. We can add cmpxchg insn, but the verifier still
> doesn't support loops. We made a lot of progress in bounded loop research
> over the last 2 years, but loops in bpf are still a year away.
> We considered adding 'bpf_spin_lock' as a new instruction instead of helper call,
> but that approach has a lot of negatives, so we went with the helper.

Ah, but the loop won't be in the BPF program itself. The BPF program
would only have had the BPF_SPIN_LOCK instruction, the JIT them emits
code similar to queued_spin_lock()/queued_spin_unlock() (or calls to
out-of-line versions of them).

There isn't anything that mandates the JIT uses the exact same locking
routines the interpreter does, is there?

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

[Alexei Starovoitov]

On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > On Fri, Jan 25, 2019 at 11:23:12AM +0100, Peter Zijlstra wrote:
> > > On Thu, Jan 24, 2019 at 03:58:59PM -0800, Alexei Starovoitov wrote:
> > > > On Thu, Jan 24, 2019 at 07:01:09PM +0100, Peter Zijlstra wrote:
> > > 
> > > > > 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.
> > 
> > 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.
> 
> 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.

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.

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

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.

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

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

[Peter Zijlstra]

On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:

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

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

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

[Alexei Starovoitov]

On Tue, Jan 29, 2019 at 10:16:54AM +0100, Peter Zijlstra wrote:
> On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> 
> > > 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.

bpf helper is a normal kernel function that can be called from bpf program.
In assembler it's a direct function call.

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

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.

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

[Peter Zijlstra]

On Tue, Jan 29, 2019 at 06:32:13PM -0800, Alexei Starovoitov wrote:
> On Tue, Jan 29, 2019 at 10:16:54AM +0100, Peter Zijlstra wrote:
> > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > 
> > > > 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.
> 
> 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,

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

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

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

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

[Alexei Starovoitov]

On Wed, Jan 30, 2019 at 09:58:50AM +0100, Peter Zijlstra wrote:
> On Tue, Jan 29, 2019 at 06:32:13PM -0800, Alexei Starovoitov wrote:
> > On Tue, Jan 29, 2019 at 10:16:54AM +0100, Peter Zijlstra wrote:
> > > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > 
> > > > > 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.
> > 
> > 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,
> 
> > > > > 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?
> > 
> > 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...
> 
> > 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.

JITs can override. There is no 'ready to use' facility for all types
of helpers to do that, but it's easy enough to add.
Having said that I'm going to reject arm32 JIT patches that
are trying to use arch_spinlock instead of generic bpf_spin_lock.
The last thing arm32 jit needs is this type of optimization.
Other JITs is a different story.

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

[Will Deacon]

Hi Alexei,

On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > 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.
> 
> 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).

> Memory model is CPU HW design decision. BPF ISA cannot dictate HW design.
> We're not saying today that BPF is strongly ordered.
> BPF load/stores are behaving differently on x86 vs arm64.
> We can add new instructions, but we cannot 'define' how load/stores behave
> from memory model perspective.
> For example, take atomicity of single byte load/store.
> Not all archs have them atomic, but we cannot say to bpf programmers
> to always assume non-atomic byte loads.

Hmm, I don't think this is a good approach to take for the future of eBPF.
Assuming that a desirable property of an eBPF program is portability between
CPU architectures, then you're effectively forcing the programmer to "assume
the worst", where the worst is almost certainly unusable for practical
purposes.

One easy thing you could consider would be to allow tagging of an eBPF
program with its supported target architectures (the JIT will refuse to
accept it for other architectures). This would at least prevent remove the
illusion of portability and force the programmer to be explicit.

However, I think we'd much better off if we defined some basic ordering
primitives such as relaxed and RCpc-style acquire/release operations
(including atomic RmW), single-copy atomic memory accesses up to the native
machine size and a full-fence instruction. If your program uses something
that the underlying arch doesn't support, then it is rejected (e.g. 64-bit
READ_ONCE on a 32-bit arch)

That should map straightforwardly to all modern architectures and allow for
efficient codegen on x86 and arm64. It would probably require a bunch of new
BPF instructions that would be defined to be atomic (you already have XADD
as a relaxed atomic add).

Apologies if this sounds patronising, but I'm keen to help figure out the
semantics *now* so that we don't end up having to infer them later on, which
is the usual painful case for memory models. I suspect Peter and Paul would
also prefer to attack it that way around. I appreciate that the temptation
is to avoid the problem by deferring to the underlying hardware memory
model, but I think that will create more problems than it solves and we're
here to help you get this right.

Will

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

[Paul E. McKenney]

On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> Hi Alexei,
> 
> On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > > 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.
> > 
> > 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).

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

> > Memory model is CPU HW design decision. BPF ISA cannot dictate HW design.
> > We're not saying today that BPF is strongly ordered.
> > BPF load/stores are behaving differently on x86 vs arm64.
> > We can add new instructions, but we cannot 'define' how load/stores behave
> > from memory model perspective.
> > For example, take atomicity of single byte load/store.
> > Not all archs have them atomic, but we cannot say to bpf programmers
> > to always assume non-atomic byte loads.
> 
> Hmm, I don't think this is a good approach to take for the future of eBPF.
> Assuming that a desirable property of an eBPF program is portability between
> CPU architectures, then you're effectively forcing the programmer to "assume
> the worst", where the worst is almost certainly unusable for practical
> purposes.
> 
> One easy thing you could consider would be to allow tagging of an eBPF
> program with its supported target architectures (the JIT will refuse to
> accept it for other architectures). This would at least prevent remove the
> illusion of portability and force the programmer to be explicit.
> 
> However, I think we'd much better off if we defined some basic ordering
> primitives such as relaxed and RCpc-style acquire/release operations
> (including atomic RmW), single-copy atomic memory accesses up to the native
> machine size and a full-fence instruction. If your program uses something
> that the underlying arch doesn't support, then it is rejected (e.g. 64-bit
> READ_ONCE on a 32-bit arch)
> 
> That should map straightforwardly to all modern architectures and allow for
> efficient codegen on x86 and arm64. It would probably require a bunch of new
> BPF instructions that would be defined to be atomic (you already have XADD
> as a relaxed atomic add).
> 
> Apologies if this sounds patronising, but I'm keen to help figure out the
> semantics *now* so that we don't end up having to infer them later on, which
> is the usual painful case for memory models. I suspect Peter and Paul would
> also prefer to attack it that way around. I appreciate that the temptation
> is to avoid the problem by deferring to the underlying hardware memory
> model, but I think that will create more problems than it solves and we're
> here to help you get this right.
> 
> Will
> 

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

[Alexei Starovoitov]

On Wed, Jan 30, 2019 at 10:36:18AM -0800, Paul E. McKenney wrote:
> On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> > Hi Alexei,
> > 
> > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > > > 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.
> > > 
> > > 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).
> 
> To reinforce this point, the Linux-kernel memory model (tools/memory-model)
> is that abstraction for the Linux kernel.  Why not just use that for BPF?

I already answered this earlier in the thread.
tldr: not going to sacrifice performance.

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

[Paul E. McKenney]

On Wed, Jan 30, 2019 at 11:51:14AM -0800, Alexei Starovoitov wrote:
> On Wed, Jan 30, 2019 at 10:36:18AM -0800, Paul E. McKenney wrote:
> > On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> > > Hi Alexei,
> > > 
> > > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > > > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > > > > 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.
> > > > 
> > > > 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).
> > 
> > To reinforce this point, the Linux-kernel memory model (tools/memory-model)
> > is that abstraction for the Linux kernel.  Why not just use that for BPF?
> 
> I already answered this earlier in the thread.
> tldr: not going to sacrifice performance.

Understood.

But can we at least say that where there are no performance consequences,
BPF should follow LKMM?  You already mentioned smp_load_acquire()
and smp_store_release(), but the void atomics (e.g., atomic_inc())
should also work because they don't provide any ordering guarantees.
The _relaxed(), _release(), and _acquire() variants of the value-returning
atomics should be just fine as well.

The other value-returning atomics have strong ordering, which is fine
on many systems, but potentially suboptimal for the weakly ordered ones.
Though you have to have pretty good locality of reference to be able to
see the difference, because otherwise cache-miss overhead dominates.

Things like cmpxchg() don't seem to fit BPF because they are normally
used in spin loops, though there are some non-spinning use cases.

You correctly pointed out that READ_ONCE() and WRITE_ONCE() are suboptimal
on systems that don't support all sizes of loads, but I bet that there
are some sizes for which they are just fine across systems, for example,
pointer size and int size.

Does that help?  Or am I missing additional cases where performance
could be degraded?

							Thanx, Paul

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

[Alexei Starovoitov]

On Wed, Jan 30, 2019 at 01:05:36PM -0800, Paul E. McKenney wrote:
> On Wed, Jan 30, 2019 at 11:51:14AM -0800, Alexei Starovoitov wrote:
> > On Wed, Jan 30, 2019 at 10:36:18AM -0800, Paul E. McKenney wrote:
> > > On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> > > > Hi Alexei,
> > > > 
> > > > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > > > > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > > > > > 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.
> > > > > 
> > > > > 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).
> > > 
> > > 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?

bpf doesn't have smp_load_acquire, atomic_fetch_add, xchg, fence instructions.
They can be added step by step. That's easy.
I believe folks already started working on adding atomic_fetch_add.
What I have problem with is making a statement today that bpf's end
goal is LKMM. Even after adding all sorts of instructions it may
not be practical.
Only when real use case requires adding new instruction we do it.
Do you have a bpf program that needs smp_load_acquire ?

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

[Paul E. McKenney]

On Wed, Jan 30, 2019 at 02:57:43PM -0800, Alexei Starovoitov wrote:
> On Wed, Jan 30, 2019 at 01:05:36PM -0800, Paul E. McKenney wrote:
> > On Wed, Jan 30, 2019 at 11:51:14AM -0800, Alexei Starovoitov wrote:
> > > On Wed, Jan 30, 2019 at 10:36:18AM -0800, Paul E. McKenney wrote:
> > > > On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> > > > > Hi Alexei,
> > > > > 
> > > > > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > > > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > > > > > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > > > > > > 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.
> > > > > > 
> > > > > > 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).
> > > > 
> > > > 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?
> 
> 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

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

[Alexei Starovoitov]

On Thu, Jan 31, 2019 at 06:01:56AM -0800, Paul E. McKenney wrote:
> On Wed, Jan 30, 2019 at 02:57:43PM -0800, Alexei Starovoitov wrote:
> > On Wed, Jan 30, 2019 at 01:05:36PM -0800, Paul E. McKenney wrote:
> > > On Wed, Jan 30, 2019 at 11:51:14AM -0800, Alexei Starovoitov wrote:
> > > > On Wed, Jan 30, 2019 at 10:36:18AM -0800, Paul E. McKenney wrote:
> > > > > On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> > > > > > Hi Alexei,
> > > > > > 
> > > > > > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > > > > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > > > > > > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > > > > > > > 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.
> > > > > > > 
> > > > > > > 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).
> > > > > 
> > > > > 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?
> > 
> > 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?

yeah. we're talking past each other indeed.
Doesn't look like that more emails will help.
Let's resolve it either f2f during next conference or join our bi-weekly
bpf bluejeans call Wed 11am pacific.
Reminders and links are on this list
https://lists.iovisor.org/g/iovisor-dev/messages?p=created,0,,20,2,0,0

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

[Paul E. McKenney]

On Thu, Jan 31, 2019 at 10:47:50AM -0800, Alexei Starovoitov wrote:
> On Thu, Jan 31, 2019 at 06:01:56AM -0800, Paul E. McKenney wrote:
> > On Wed, Jan 30, 2019 at 02:57:43PM -0800, Alexei Starovoitov wrote:
> > > On Wed, Jan 30, 2019 at 01:05:36PM -0800, Paul E. McKenney wrote:
> > > > On Wed, Jan 30, 2019 at 11:51:14AM -0800, Alexei Starovoitov wrote:
> > > > > On Wed, Jan 30, 2019 at 10:36:18AM -0800, Paul E. McKenney wrote:
> > > > > > On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> > > > > > > Hi Alexei,
> > > > > > > 
> > > > > > > On Mon, Jan 28, 2019 at 01:56:24PM -0800, Alexei Starovoitov wrote:
> > > > > > > > On Mon, Jan 28, 2019 at 10:24:08AM +0100, Peter Zijlstra wrote:
> > > > > > > > > On Fri, Jan 25, 2019 at 04:17:26PM -0800, Alexei Starovoitov wrote:
> > > > > > > > > > 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.
> > > > > > > > 
> > > > > > > > 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).
> > > > > > 
> > > > > > 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?
> > > 
> > > 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?
> 
> 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

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

[Alexei Starovoitov]

On Wed, Jan 30, 2019 at 06:11:00PM +0000, Will Deacon wrote:
> 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.

[PATCH v4 bpf-next 2/9] bpf: add support for bpf_spin_lock to cgroup local storage

[Alexei Starovoitov]

Allow 'struct bpf_spin_lock' to reside inside cgroup local storage.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/local_storage.c | 2 ++
 kernel/bpf/syscall.c       | 3 ++-
 kernel/bpf/verifier.c      | 2 ++
 3 files changed, 6 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/local_storage.c b/kernel/bpf/local_storage.c
index 07a34ef562a0..0295427f06e2 100644
--- a/kernel/bpf/local_storage.c
+++ b/kernel/bpf/local_storage.c
@@ -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)
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index ebf0a673cb83..b29e6dc44650 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -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) {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f372904fa691..bfd6bebca911 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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;
-- 
2.17.1

[PATCH v4 bpf-next 3/9] tools/bpf: sync include/uapi/linux/bpf.h

[Alexei Starovoitov]

sync bpf.h

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/include/uapi/linux/bpf.h | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index 91c43884f295..30f9dfd40f13 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -2421,7 +2421,9 @@ union bpf_attr {
 	FN(map_peek_elem),		\
 	FN(msg_push_data),		\
 	FN(msg_pop_data),		\
-	FN(rc_pointer_rel),
+	FN(rc_pointer_rel),		\
+	FN(spin_lock),			\
+	FN(spin_unlock),
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
  * function eBPF program intends to call
@@ -3054,4 +3056,7 @@ struct bpf_line_info {
 	__u32	line_col;
 };
 
+struct bpf_spin_lock {
+	__u32	val;
+};
 #endif /* _UAPI__LINUX_BPF_H__ */
-- 
2.17.1

[PATCH v4 bpf-next 4/9] selftests/bpf: add bpf_spin_lock tests

[Alexei Starovoitov]

add bpf_spin_lock tests to test_verifier.c that don't require
latest llvm with BTF support

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/testing/selftests/bpf/test_verifier.c | 459 +++++++++++++++++++-
 1 file changed, 458 insertions(+), 1 deletion(-)

diff --git a/tools/testing/selftests/bpf/test_verifier.c b/tools/testing/selftests/bpf/test_verifier.c
index 4f67afeec8d9..4b29dba7ffff 100644
--- a/tools/testing/selftests/bpf/test_verifier.c
+++ b/tools/testing/selftests/bpf/test_verifier.c
@@ -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)
-- 
2.17.1

[PATCH v4 bpf-next 5/9] selftests/bpf: add bpf_spin_lock C test

[Alexei Starovoitov]

add bpf_spin_lock C based test that requires latest llvm with BTF support

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 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

diff --git a/tools/testing/selftests/bpf/Makefile b/tools/testing/selftests/bpf/Makefile
index 70229de510f5..fcfda51406f9 100644
--- a/tools/testing/selftests/bpf/Makefile
+++ b/tools/testing/selftests/bpf/Makefile
@@ -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 \
diff --git a/tools/testing/selftests/bpf/bpf_helpers.h b/tools/testing/selftests/bpf/bpf_helpers.h
index 6c77cf7bedce..6a0ce0f055c5 100644
--- a/tools/testing/selftests/bpf/bpf_helpers.h
+++ b/tools/testing/selftests/bpf/bpf_helpers.h
@@ -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
diff --git a/tools/testing/selftests/bpf/test_progs.c b/tools/testing/selftests/bpf/test_progs.c
index 126fc624290d..6425e95c3f16 100644
--- a/tools/testing/selftests/bpf/test_progs.c
+++ b/tools/testing/selftests/bpf/test_progs.c
@@ -28,7 +28,7 @@ typedef __u16 __sum16;
 #include <sys/wait.h>
 #include <sys/types.h>
 #include <fcntl.h>
-
+#include <pthread.h>
 #include <linux/bpf.h>
 #include <linux/err.h>
 #include <bpf/bpf.h>
@@ -1882,6 +1882,46 @@ static void test_queue_stack_map(int type)
 	bpf_object__close(obj);
 }
 
+static void *parallel_bpf_prog_test_run(void *arg)
+{
+	__u32 duration, retval;
+	int err, prog_fd = *(u32 *) arg;
+
+	err = bpf_prog_test_run(prog_fd, 10000, &pkt_v4, sizeof(pkt_v4),
+				NULL, NULL, &retval, &duration);
+	CHECK(err || retval, "",
+	      "err %d errno %d retval %d duration %d\n",
+	      err, errno, retval, duration);
+	pthread_exit(arg);
+}
+
+static void test_spin_lock(void)
+{
+	const char *file = "./test_spin_lock.o";
+	pthread_t thread_id[4];
+	struct bpf_object *obj;
+	int prog_fd;
+	int err = 0, i;
+	void *ret;
+
+	err = bpf_prog_load(file, BPF_PROG_TYPE_CGROUP_SKB, &obj, &prog_fd);
+	if (err) {
+		printf("test_spin_lock:bpf_prog_load errno %d\n", errno);
+		goto close_prog;
+	}
+	for (i = 0; i < 4; i++)
+		assert(pthread_create(&thread_id[i], NULL,
+				      &parallel_bpf_prog_test_run, &prog_fd) == 0);
+	for (i = 0; i < 4; i++)
+		assert(pthread_join(thread_id[i], &ret) == 0 &&
+		       ret == (void *)&prog_fd);
+	goto close_prog_noerr;
+close_prog:
+	error_cnt++;
+close_prog_noerr:
+	bpf_object__close(obj);
+}
+
 int main(void)
 {
 	srand(time(NULL));
@@ -1909,6 +1949,7 @@ int main(void)
 	test_reference_tracking();
 	test_queue_stack_map(QUEUE);
 	test_queue_stack_map(STACK);
+	test_spin_lock();
 
 	printf("Summary: %d PASSED, %d FAILED\n", pass_cnt, error_cnt);
 	return error_cnt ? EXIT_FAILURE : EXIT_SUCCESS;
diff --git a/tools/testing/selftests/bpf/test_spin_lock.c b/tools/testing/selftests/bpf/test_spin_lock.c
new file mode 100644
index 000000000000..40f904312090
--- /dev/null
+++ b/tools/testing/selftests/bpf/test_spin_lock.c
@@ -0,0 +1,108 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2019 Facebook
+#include <linux/bpf.h>
+#include <linux/version.h>
+#include "bpf_helpers.h"
+
+struct hmap_elem {
+	volatile int cnt;
+	struct bpf_spin_lock lock;
+	int test_padding;
+};
+
+struct bpf_map_def SEC("maps") hmap = {
+	.type = BPF_MAP_TYPE_HASH,
+	.key_size = sizeof(int),
+	.value_size = sizeof(struct hmap_elem),
+	.max_entries = 1,
+};
+
+BPF_ANNOTATE_KV_PAIR(hmap, int, struct hmap_elem);
+
+
+struct cls_elem {
+	struct bpf_spin_lock lock;
+	volatile int cnt;
+};
+
+struct bpf_map_def SEC("maps") cls_map = {
+	.type = BPF_MAP_TYPE_CGROUP_STORAGE,
+	.key_size = sizeof(struct bpf_cgroup_storage_key),
+	.value_size = sizeof(struct cls_elem),
+};
+
+BPF_ANNOTATE_KV_PAIR(cls_map, struct bpf_cgroup_storage_key,
+		     struct cls_elem);
+
+struct bpf_vqueue {
+	struct bpf_spin_lock lock;
+	/* 4 byte hole */
+	unsigned long long lasttime;
+	int credit;
+	unsigned int rate;
+};
+
+struct bpf_map_def SEC("maps") vqueue = {
+	.type = BPF_MAP_TYPE_ARRAY,
+	.key_size = sizeof(int),
+	.value_size = sizeof(struct bpf_vqueue),
+	.max_entries = 1,
+};
+
+BPF_ANNOTATE_KV_PAIR(vqueue, int, struct bpf_vqueue);
+#define CREDIT_PER_NS(delta, rate) (((delta) * rate) >> 20)
+
+SEC("spin_lock_demo")
+int bpf_sping_lock_test(struct __sk_buff *skb)
+{
+	volatile int credit = 0, max_credit = 100, pkt_len = 64;
+	struct hmap_elem zero = {}, *val;
+	unsigned long long curtime;
+	struct bpf_vqueue *q;
+	struct cls_elem *cls;
+	int key = 0;
+	int err = 0;
+
+	val = bpf_map_lookup_elem(&hmap, &key);
+	if (!val) {
+		bpf_map_update_elem(&hmap, &key, &zero, 0);
+		val = bpf_map_lookup_elem(&hmap, &key);
+		if (!val) {
+			err = 1;
+			goto err;
+		}
+	}
+	/* spin_lock in hash map run time test */
+	bpf_spin_lock(&val->lock);
+	if (val->cnt)
+		val->cnt--;
+	else
+		val->cnt++;
+	if (val->cnt != 0 && val->cnt != 1)
+		err = 1;
+	bpf_spin_unlock(&val->lock);
+
+	/* spin_lock in array. virtual queue demo */
+	q = bpf_map_lookup_elem(&vqueue, &key);
+	if (!q)
+		goto err;
+	curtime = bpf_ktime_get_ns();
+	bpf_spin_lock(&q->lock);
+	q->credit += CREDIT_PER_NS(curtime - q->lasttime, q->rate);
+	q->lasttime = curtime;
+	if (q->credit > max_credit)
+		q->credit = max_credit;
+	q->credit -= pkt_len;
+	credit = q->credit;
+	bpf_spin_unlock(&q->lock);
+
+	/* spin_lock in cgroup local storage */
+	cls = bpf_get_local_storage(&cls_map, 0);
+	bpf_spin_lock(&cls->lock);
+	cls->cnt++;
+	bpf_spin_unlock(&cls->lock);
+
+err:
+	return err;
+}
+char _license[] SEC("license") = "GPL";
-- 
2.17.1

[PATCH v4 bpf-next 6/9] bpf: introduce BPF_F_LOCK flag

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

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 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(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index ee0352bd728f..34a517137b63 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -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;
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 30f9dfd40f13..c23eaa284a45 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -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)
diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index d6d979910a2a..c72e0d8e1e65 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -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;
 }
 
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 48a41bf65e1b..27b986c19c63 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -809,11 +809,11 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old,
 		       u64 map_flags)
 {
-	if (l_old && map_flags == BPF_NOEXIST)
+	if (l_old && (map_flags & ~BPF_F_LOCK) == BPF_NOEXIST)
 		/* elem already exists */
 		return -EEXIST;
 
-	if (!l_old && map_flags == BPF_EXIST)
+	if (!l_old && (map_flags & ~BPF_F_LOCK) == BPF_EXIST)
 		/* elem doesn't exist, cannot update it */
 		return -ENOENT;
 
@@ -832,7 +832,7 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 	u32 key_size, hash;
 	int ret;
 
-	if (unlikely(map_flags > BPF_EXIST))
+	if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST))
 		/* unknown flags */
 		return -EINVAL;
 
@@ -845,6 +845,28 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 	b = __select_bucket(htab, hash);
 	head = &b->head;
 
+	if (unlikely(map_flags & BPF_F_LOCK)) {
+		if (unlikely(!map_value_has_spin_lock(map)))
+			return -EINVAL;
+		/* find an element without taking the bucket lock */
+		l_old = lookup_nulls_elem_raw(head, hash, key, key_size,
+					      htab->n_buckets);
+		ret = check_flags(htab, l_old, map_flags);
+		if (ret)
+			return ret;
+		if (l_old) {
+			/* grab the element lock and update value in place */
+			copy_map_value_locked(map,
+					      l_old->key + round_up(key_size, 8),
+					      value, false);
+			return 0;
+		}
+		/* fall through, grab the bucket lock and lookup again.
+		 * 99.9% chance that the element won't be found,
+		 * but second lookup under lock has to be done.
+		 */
+	}
+
 	/* bpf_map_update_elem() can be called in_irq() */
 	raw_spin_lock_irqsave(&b->lock, flags);
 
@@ -854,6 +876,20 @@ static int htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 	if (ret)
 		goto err;
 
+	if (unlikely(l_old && (map_flags & BPF_F_LOCK))) {
+		/* first lookup without the bucket lock didn't find the element,
+		 * but second lookup with the bucket lock found it.
+		 * This case is highly unlikely, but has to be dealt with:
+		 * grab the element lock in addition to the bucket lock
+		 * and update element in place
+		 */
+		copy_map_value_locked(map,
+				      l_old->key + round_up(key_size, 8),
+				      value, false);
+		ret = 0;
+		goto err;
+	}
+
 	l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false,
 				l_old);
 	if (IS_ERR(l_new)) {
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 2e98e4caf5aa..60e475bcb708 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -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)
 {
diff --git a/kernel/bpf/local_storage.c b/kernel/bpf/local_storage.c
index 0295427f06e2..6b572e2de7fb 100644
--- a/kernel/bpf/local_storage.c
+++ b/kernel/bpf/local_storage.c
@@ -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,
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index b29e6dc44650..0834958f1dc4 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -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);
-- 
2.17.1

[PATCH v4 bpf-next 7/9] tools/bpf: sync uapi/bpf.h

[Alexei Starovoitov]

add BPF_F_LOCK definition to tools/include/uapi/linux/bpf.h

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 tools/include/uapi/linux/bpf.h | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index 30f9dfd40f13..c23eaa284a45 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -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)
-- 
2.17.1