BPF Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH bpf-next v2 01/11] bpf: factor out visit_func_call_insn() in check_cfg()
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 02/11] bpf: factor out verbose_invalid_scalar() Yonghong Song
                   ` (10 subsequent siblings)
  11 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

During verifier check_cfg(), all instructions are
visited to ensure verifier can handle program control flows.
This patch factored out function visit_func_call_insn()
so it can be reused in later patch to visit callback function
calls. There is no functionality change for this patch.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/verifier.c | 35 +++++++++++++++++++++++------------
 1 file changed, 23 insertions(+), 12 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 11a242932a2c..e3149239b346 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8591,6 +8591,27 @@ static int push_insn(int t, int w, int e, struct bpf_verifier_env *env,
 	return DONE_EXPLORING;
 }
 
+static int visit_func_call_insn(int t, int insn_cnt,
+				struct bpf_insn *insns,
+				struct bpf_verifier_env *env,
+				bool visit_callee)
+{
+	int ret;
+
+	ret = push_insn(t, t + 1, FALLTHROUGH, env, false);
+	if (ret)
+		return ret;
+
+	if (t + 1 < insn_cnt)
+		init_explored_state(env, t + 1);
+	if (visit_callee) {
+		init_explored_state(env, t);
+		ret = push_insn(t, t + insns[t].imm + 1, BRANCH,
+				env, false);
+	}
+	return ret;
+}
+
 /* Visits the instruction at index t and returns one of the following:
  *  < 0 - an error occurred
  *  DONE_EXPLORING - the instruction was fully explored
@@ -8611,18 +8632,8 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
 		return DONE_EXPLORING;
 
 	case BPF_CALL:
-		ret = push_insn(t, t + 1, FALLTHROUGH, env, false);
-		if (ret)
-			return ret;
-
-		if (t + 1 < insn_cnt)
-			init_explored_state(env, t + 1);
-		if (insns[t].src_reg == BPF_PSEUDO_CALL) {
-			init_explored_state(env, t);
-			ret = push_insn(t, t + insns[t].imm + 1, BRANCH,
-					env, false);
-		}
-		return ret;
+		return visit_func_call_insn(t, insn_cnt, insns, env,
+					    insns[t].src_reg == BPF_PSEUDO_CALL);
 
 	case BPF_JA:
 		if (BPF_SRC(insns[t].code) != BPF_K)
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper
@ 2021-02-17 18:18 Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 01/11] bpf: factor out visit_func_call_insn() in check_cfg() Yonghong Song
                   ` (11 more replies)
  0 siblings, 12 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

This patch set introduced bpf_for_each_map_elem() helper.
The helper permits bpf program iterates through all elements
for a particular map.

The work originally inspired by an internal discussion where
firewall rules are kept in a map and bpf prog wants to
check packet 5 tuples against all rules in the map.
A bounded loop can be used but it has a few drawbacks.
As the loop iteration goes up, verification time goes up too.
For really large maps, verification may fail.
A helper which abstracts out the loop itself will not have
verification time issue.

A recent discussion in [1] involves to iterate all hash map
elements in bpf program. Currently iterating all hashmap elements
in bpf program is not easy if key space is really big.
Having a helper to abstract out the loop itself is even more
meaningful.

The proposed helper signature looks like:
  long bpf_for_each_map_elem(map, callback_fn, callback_ctx, flags)
where callback_fn is a static function and callback_ctx is
a piece of data allocated on the caller stack which can be
accessed by the callback_fn. The callback_fn signature might be
different for different maps. For example, for hash/array maps,
the signature is
  long callback_fn(map, key, val, callback_ctx)

In the rest of series, Patches 1/2/3 did some refactoring. Patch 4
implemented core kernel support for the helper. Patches 5 and 6
added hashmap and arraymap support. Patches 7/8 added libbpf
support. Patch 9 added bpftool support. Patches 10 and 11 added
selftests for hashmap and arraymap.

[1]: https://lore.kernel.org/bpf/20210122205415.113822-1-xiyou.wangcong@gmail.com/

Yonghong Song (11):
  bpf: factor out visit_func_call_insn() in check_cfg()
  bpf: factor out verbose_invalid_scalar()
  bpf: refactor check_func_call() to allow callback function
  bpf: add bpf_for_each_map_elem() helper
  bpf: add hashtab support for bpf_for_each_map_elem() helper
  bpf: add arraymap support for bpf_for_each_map_elem() helper
  libbpf: move function is_ldimm64() earlier in libbpf.c
  libbpf: support local function pointer relocation
  bpftool: print local function pointer properly
  selftests/bpf: add hashmap test for bpf_for_each_map_elem() helper
  selftests/bpf: add arraymap test for bpf_for_each_map_elem() helper

 include/linux/bpf.h                           |  17 +
 include/linux/bpf_verifier.h                  |   3 +
 include/uapi/linux/bpf.h                      |  29 +-
 kernel/bpf/arraymap.c                         |  39 ++
 kernel/bpf/bpf_iter.c                         |  16 +
 kernel/bpf/hashtab.c                          |  63 ++++
 kernel/bpf/helpers.c                          |   2 +
 kernel/bpf/verifier.c                         | 346 +++++++++++++++---
 kernel/trace/bpf_trace.c                      |   2 +
 tools/bpf/bpftool/xlated_dumper.c             |   3 +
 tools/include/uapi/linux/bpf.h                |  29 +-
 tools/lib/bpf/libbpf.c                        |  52 ++-
 .../selftests/bpf/prog_tests/for_each.c       | 132 +++++++
 .../bpf/progs/for_each_array_map_elem.c       |  61 +++
 .../bpf/progs/for_each_hash_map_elem.c        |  95 +++++
 15 files changed, 829 insertions(+), 60 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/for_each.c
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_array_map_elem.c
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_hash_map_elem.c

-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 02/11] bpf: factor out verbose_invalid_scalar()
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 01/11] bpf: factor out visit_func_call_insn() in check_cfg() Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 03/11] bpf: refactor check_func_call() to allow callback function Yonghong Song
                   ` (9 subsequent siblings)
  11 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

Factor out the function verbose_invalid_scalar() to verbose
print if a scalar is not in a tnum range. There is no
functionality change and the function will be used by
later patch which introduced bpf_for_each_map_elem().

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/verifier.c | 31 ++++++++++++++++++++-----------
 1 file changed, 20 insertions(+), 11 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e3149239b346..d224cd7c3a5d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -390,6 +390,25 @@ __printf(3, 4) static void verbose_linfo(struct bpf_verifier_env *env,
 	env->prev_linfo = linfo;
 }
 
+static void verbose_invalid_scalar(struct bpf_verifier_env *env,
+				   struct bpf_reg_state *reg,
+				   struct tnum *range, const char *ctx,
+				   const char *reg_name)
+{
+	char tn_buf[48];
+
+	verbose(env, "At %s the register %s ", ctx, reg_name);
+	if (!tnum_is_unknown(reg->var_off)) {
+		tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
+		verbose(env, "has value %s", tn_buf);
+	} else {
+		verbose(env, "has unknown scalar value");
+	}
+	tnum_strn(tn_buf, sizeof(tn_buf), *range);
+	verbose(env, " should have been in %s\n", tn_buf);
+}
+
+
 static bool type_is_pkt_pointer(enum bpf_reg_type type)
 {
 	return type == PTR_TO_PACKET ||
@@ -8454,17 +8473,7 @@ static int check_return_code(struct bpf_verifier_env *env)
 	}
 
 	if (!tnum_in(range, reg->var_off)) {
-		char tn_buf[48];
-
-		verbose(env, "At program exit the register R0 ");
-		if (!tnum_is_unknown(reg->var_off)) {
-			tnum_strn(tn_buf, sizeof(tn_buf), reg->var_off);
-			verbose(env, "has value %s", tn_buf);
-		} else {
-			verbose(env, "has unknown scalar value");
-		}
-		tnum_strn(tn_buf, sizeof(tn_buf), range);
-		verbose(env, " should have been in %s\n", tn_buf);
+		verbose_invalid_scalar(env, reg, &range, "program exit", "R0");
 		return -EINVAL;
 	}
 
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 03/11] bpf: refactor check_func_call() to allow callback function
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 01/11] bpf: factor out visit_func_call_insn() in check_cfg() Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 02/11] bpf: factor out verbose_invalid_scalar() Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (8 subsequent siblings)
  11 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

Later proposed bpf_for_each_map_elem() helper has callback
function as one of its arguments. This patch refactored
check_func_call() to permit callback function which sets
callee state. Different callback functions may have
different callee states.

There is no functionality change for this patch except
it added a case to handle where subprog number is known
and there is no need to do find_subprog(). This case
is used later by implementing bpf_for_each_map() helper.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/verifier.c | 54 ++++++++++++++++++++++++++++++++-----------
 1 file changed, 41 insertions(+), 13 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d224cd7c3a5d..fcc1a2db32c9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5250,13 +5250,19 @@ static void clear_caller_saved_regs(struct bpf_verifier_env *env,
 	}
 }
 
-static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
-			   int *insn_idx)
+typedef int (*set_callee_state_fn)(struct bpf_verifier_env *env,
+				   struct bpf_func_state *caller,
+				   struct bpf_func_state *callee,
+				   int insn_idx);
+
+static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			     int *insn_idx, int subprog,
+			     set_callee_state_fn set_callee_st)
 {
 	struct bpf_verifier_state *state = env->cur_state;
 	struct bpf_func_info_aux *func_info_aux;
 	struct bpf_func_state *caller, *callee;
-	int i, err, subprog, target_insn;
+	int err, target_insn;
 	bool is_global = false;
 
 	if (state->curframe + 1 >= MAX_CALL_FRAMES) {
@@ -5265,12 +5271,16 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		return -E2BIG;
 	}
 
-	target_insn = *insn_idx + insn->imm;
-	subprog = find_subprog(env, target_insn + 1);
 	if (subprog < 0) {
-		verbose(env, "verifier bug. No program starts at insn %d\n",
-			target_insn + 1);
-		return -EFAULT;
+		target_insn = *insn_idx + insn->imm;
+		subprog = find_subprog(env, target_insn + 1);
+		if (subprog < 0) {
+			verbose(env, "verifier bug. No program starts at insn %d\n",
+				target_insn + 1);
+			return -EFAULT;
+		}
+	} else {
+		target_insn = env->subprog_info[subprog].start - 1;
 	}
 
 	caller = state->frame[state->curframe];
@@ -5326,11 +5336,9 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	if (err)
 		return err;
 
-	/* copy r1 - r5 args that callee can access.  The copy includes parent
-	 * pointers, which connects us up to the liveness chain
-	 */
-	for (i = BPF_REG_1; i <= BPF_REG_5; i++)
-		callee->regs[i] = caller->regs[i];
+	err = set_callee_st(env, caller, callee, *insn_idx);
+	if (err)
+		return err;
 
 	clear_caller_saved_regs(env, caller->regs);
 
@@ -5349,6 +5357,26 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	return 0;
 }
 
+static int set_callee_state(struct bpf_verifier_env *env,
+			    struct bpf_func_state *caller,
+			    struct bpf_func_state *callee, int insn_idx)
+{
+	int i;
+
+	/* copy r1 - r5 args that callee can access.  The copy includes parent
+	 * pointers, which connects us up to the liveness chain
+	 */
+	for (i = BPF_REG_1; i <= BPF_REG_5; i++)
+		callee->regs[i] = caller->regs[i];
+	return 0;
+}
+
+static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			   int *insn_idx)
+{
+	return __check_func_call(env, insn, insn_idx, -1, set_callee_state);
+}
+
 static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 {
 	struct bpf_verifier_state *state = env->cur_state;
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (2 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 03/11] bpf: refactor check_func_call() to allow callback function Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-22 20:59   ` Alexei Starovoitov
  2021-02-17 18:18 ` [PATCH bpf-next v2 05/11] bpf: add hashtab support for " Yonghong Song
                   ` (7 subsequent siblings)
  11 siblings, 1 reply; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

The bpf_for_each_map_elem() helper is introduced which
iterates all map elements with a callback function. The
helper signature looks like
  long bpf_for_each_map_elem(map, callback_fn, callback_ctx, flags)
and for each map element, the callback_fn will be called. For example,
like hashmap, the callback signature may look like
  long callback_fn(map, key, val, callback_ctx)

There are two known use cases for this. One is from upstream ([1]) where
a for_each_map_elem helper may help implement a timeout mechanism
in a more generic way. Another is from our internal discussion
for a firewall use case where a map contains all the rules. The packet
data can be compared to all these rules to decide allow or deny
the packet.

For array maps, users can already use a bounded loop to traverse
elements. Using this helper can avoid using bounded loop. For other
type of maps (e.g., hash maps) where bounded loop is hard or
impossible to use, this helper provides a convenient way to
operate on all elements.

For callback_fn, besides map and map element, a callback_ctx,
allocated on caller stack, is also passed to the callback
function. This callback_ctx argument can provide additional
input and allow to write to caller stack for output.

If the callback_fn returns 0, the helper will iterate through next
element if available. If the callback_fn returns 1, the helper
will stop iterating and returns to the bpf program. Other return
values are not used for now.

Currently, this helper is only available with jit. It is possible
to make it work with interpreter with so effort but I leave it
as the future work.

[1]: https://lore.kernel.org/bpf/20210122205415.113822-1-xiyou.wangcong@gmail.com/

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 include/linux/bpf.h            |  13 +++
 include/linux/bpf_verifier.h   |   3 +
 include/uapi/linux/bpf.h       |  29 ++++-
 kernel/bpf/bpf_iter.c          |  16 +++
 kernel/bpf/helpers.c           |   2 +
 kernel/bpf/verifier.c          | 199 ++++++++++++++++++++++++++++++---
 kernel/trace/bpf_trace.c       |   2 +
 tools/include/uapi/linux/bpf.h |  29 ++++-
 8 files changed, 278 insertions(+), 15 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index cccaef1088ea..40f41a9b40f9 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -39,6 +39,7 @@ struct bpf_local_storage;
 struct bpf_local_storage_map;
 struct kobject;
 struct mem_cgroup;
+struct bpf_func_state;
 
 extern struct idr btf_idr;
 extern spinlock_t btf_idr_lock;
@@ -129,6 +130,13 @@ struct bpf_map_ops {
 	bool (*map_meta_equal)(const struct bpf_map *meta0,
 			       const struct bpf_map *meta1);
 
+
+	int (*map_set_for_each_callback_args)(struct bpf_verifier_env *env,
+					      struct bpf_func_state *caller,
+					      struct bpf_func_state *callee);
+	int (*map_for_each_callback)(struct bpf_map *map, void *callback_fn,
+				     void *callback_ctx, u64 flags);
+
 	/* BTF name and id of struct allocated by map_alloc */
 	const char * const map_btf_name;
 	int *map_btf_id;
@@ -295,6 +303,8 @@ enum bpf_arg_type {
 	ARG_CONST_ALLOC_SIZE_OR_ZERO,	/* number of allocated bytes requested */
 	ARG_PTR_TO_BTF_ID_SOCK_COMMON,	/* pointer to in-kernel sock_common or bpf-mirrored bpf_sock */
 	ARG_PTR_TO_PERCPU_BTF_ID,	/* pointer to in-kernel percpu type */
+	ARG_PTR_TO_FUNC,	/* pointer to a bpf program function */
+	ARG_PTR_TO_STACK_OR_NULL,	/* pointer to stack or NULL */
 	__BPF_ARG_TYPE_MAX,
 };
 
@@ -411,6 +421,8 @@ enum bpf_reg_type {
 	PTR_TO_RDWR_BUF,	 /* reg points to a read/write buffer */
 	PTR_TO_RDWR_BUF_OR_NULL, /* reg points to a read/write buffer or NULL */
 	PTR_TO_PERCPU_BTF_ID,	 /* reg points to a percpu kernel variable */
+	PTR_TO_FUNC,		 /* reg points to a bpf program function */
+	PTR_TO_MAP_KEY,		 /* reg points to a map element key */
 };
 
 /* The information passed from prog-specific *_is_valid_access
@@ -1886,6 +1898,7 @@ extern const struct bpf_func_proto bpf_this_cpu_ptr_proto;
 extern const struct bpf_func_proto bpf_ktime_get_coarse_ns_proto;
 extern const struct bpf_func_proto bpf_sock_from_file_proto;
 extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;
+extern const struct bpf_func_proto bpf_for_each_map_elem_proto;
 
 const struct bpf_func_proto *bpf_tracing_func_proto(
 	enum bpf_func_id func_id, const struct bpf_prog *prog);
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 971b33aca13d..51c2ffa3d901 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -68,6 +68,8 @@ struct bpf_reg_state {
 			unsigned long raw1;
 			unsigned long raw2;
 		} raw;
+
+		u32 subprogno; /* for PTR_TO_FUNC */
 	};
 	/* For PTR_TO_PACKET, used to find other pointers with the same variable
 	 * offset, so they can share range knowledge.
@@ -204,6 +206,7 @@ struct bpf_func_state {
 	int acquired_refs;
 	struct bpf_reference_state *refs;
 	int allocated_stack;
+	bool in_callback_fn;
 	struct bpf_stack_state *stack;
 };
 
diff --git a/include/uapi/linux/bpf.h b/include/uapi/linux/bpf.h
index 4c24daa43bac..0ed65fd87732 100644
--- a/include/uapi/linux/bpf.h
+++ b/include/uapi/linux/bpf.h
@@ -393,6 +393,15 @@ enum bpf_link_type {
  *                   is struct/union.
  */
 #define BPF_PSEUDO_BTF_ID	3
+/* insn[0].src_reg:  BPF_PSEUDO_FUNC
+ * insn[0].imm:      insn offset to the func
+ * insn[1].imm:      0
+ * insn[0].off:      0
+ * insn[1].off:      0
+ * ldimm64 rewrite:  address of the function
+ * verifier type:    PTR_TO_FUNC.
+ */
+#define BPF_PSEUDO_FUNC		4
 
 /* when bpf_call->src_reg == BPF_PSEUDO_CALL, bpf_call->imm == pc-relative
  * offset to another bpf function
@@ -3850,7 +3859,6 @@ union bpf_attr {
  *
  * long bpf_check_mtu(void *ctx, u32 ifindex, u32 *mtu_len, s32 len_diff, u64 flags)
  *	Description
-
  *		Check ctx packet size against exceeding MTU of net device (based
  *		on *ifindex*).  This helper will likely be used in combination
  *		with helpers that adjust/change the packet size.
@@ -3910,6 +3918,24 @@ union bpf_attr {
  *		* **BPF_MTU_CHK_RET_FRAG_NEEDED**
  *		* **BPF_MTU_CHK_RET_SEGS_TOOBIG**
  *
+ * long bpf_for_each_map_elem(struct bpf_map *map, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For each element in **map**, call **callback_fn** function with
+ *		**map**, **callback_ctx** and other map-specific parameters.
+ *		For example, for hash and array maps, the callback signature can
+ *		be `long callback_fn(map, map_key, map_value, callback_ctx)`.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.
+ *		Currently, the **flags** must be 0. For per_cpu maps,
+ *		the map_value is the value on the cpu where the bpf_prog is running.
+ *
+ *		If **callback_fn** return 0, the helper will continue to the next
+ *		element. If return value is 1, the helper will skip the rest of
+ *		elements and return. Other return values are not used now.
+ *	Return
+ *		The number of traversed map elements for success, **-EINVAL** for
+ *		invalid **flags** or unsupported **callback_fn** return value.
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -4076,6 +4102,7 @@ union bpf_attr {
 	FN(ima_inode_hash),		\
 	FN(sock_from_file),		\
 	FN(check_mtu),			\
+	FN(for_each_map_elem),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
diff --git a/kernel/bpf/bpf_iter.c b/kernel/bpf/bpf_iter.c
index a0d9eade9c80..931870f9cf56 100644
--- a/kernel/bpf/bpf_iter.c
+++ b/kernel/bpf/bpf_iter.c
@@ -675,3 +675,19 @@ int bpf_iter_run_prog(struct bpf_prog *prog, void *ctx)
 	 */
 	return ret == 0 ? 0 : -EAGAIN;
 }
+
+BPF_CALL_4(bpf_for_each_map_elem, struct bpf_map *, map, void *, callback_fn,
+	   void *, callback_ctx, u64, flags)
+{
+	return map->ops->map_for_each_callback(map, callback_fn, callback_ctx, flags);
+}
+
+const struct bpf_func_proto bpf_for_each_map_elem_proto = {
+	.func		= bpf_for_each_map_elem,
+	.gpl_only	= false,
+	.ret_type	= RET_INTEGER,
+	.arg1_type	= ARG_CONST_MAP_PTR,
+	.arg2_type	= ARG_PTR_TO_FUNC,
+	.arg3_type	= ARG_PTR_TO_STACK_OR_NULL,
+	.arg4_type	= ARG_ANYTHING,
+};
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 308427fe03a3..074800226327 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -708,6 +708,8 @@ bpf_base_func_proto(enum bpf_func_id func_id)
 		return &bpf_ringbuf_discard_proto;
 	case BPF_FUNC_ringbuf_query:
 		return &bpf_ringbuf_query_proto;
+	case BPF_FUNC_for_each_map_elem:
+		return &bpf_for_each_map_elem_proto;
 	default:
 		break;
 	}
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fcc1a2db32c9..f80386d094b7 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -234,6 +234,12 @@ static bool bpf_pseudo_call(const struct bpf_insn *insn)
 	       insn->src_reg == BPF_PSEUDO_CALL;
 }
 
+static bool bpf_pseudo_func(const struct bpf_insn *insn)
+{
+	return insn->code == (BPF_LD | BPF_IMM | BPF_DW) &&
+	       insn->src_reg == BPF_PSEUDO_FUNC;
+}
+
 struct bpf_call_arg_meta {
 	struct bpf_map *map_ptr;
 	bool raw_mode;
@@ -248,6 +254,7 @@ struct bpf_call_arg_meta {
 	u32 btf_id;
 	struct btf *ret_btf;
 	u32 ret_btf_id;
+	u32 subprogno;
 };
 
 struct btf *btf_vmlinux;
@@ -428,6 +435,7 @@ static bool reg_type_not_null(enum bpf_reg_type type)
 	return type == PTR_TO_SOCKET ||
 		type == PTR_TO_TCP_SOCK ||
 		type == PTR_TO_MAP_VALUE ||
+		type == PTR_TO_MAP_KEY ||
 		type == PTR_TO_SOCK_COMMON;
 }
 
@@ -470,7 +478,8 @@ static bool arg_type_may_be_null(enum bpf_arg_type type)
 	       type == ARG_PTR_TO_MEM_OR_NULL ||
 	       type == ARG_PTR_TO_CTX_OR_NULL ||
 	       type == ARG_PTR_TO_SOCKET_OR_NULL ||
-	       type == ARG_PTR_TO_ALLOC_MEM_OR_NULL;
+	       type == ARG_PTR_TO_ALLOC_MEM_OR_NULL ||
+	       type == ARG_PTR_TO_STACK_OR_NULL;
 }
 
 /* Determine whether the function releases some resources allocated by another
@@ -553,6 +562,8 @@ static const char * const reg_type_str[] = {
 	[PTR_TO_RDONLY_BUF_OR_NULL] = "rdonly_buf_or_null",
 	[PTR_TO_RDWR_BUF]	= "rdwr_buf",
 	[PTR_TO_RDWR_BUF_OR_NULL] = "rdwr_buf_or_null",
+	[PTR_TO_FUNC]		= "func",
+	[PTR_TO_MAP_KEY]	= "map_key",
 };
 
 static char slot_type_char[] = {
@@ -624,6 +635,7 @@ static void print_verifier_state(struct bpf_verifier_env *env,
 			if (type_is_pkt_pointer(t))
 				verbose(env, ",r=%d", reg->range);
 			else if (t == CONST_PTR_TO_MAP ||
+				 t == PTR_TO_MAP_KEY ||
 				 t == PTR_TO_MAP_VALUE ||
 				 t == PTR_TO_MAP_VALUE_OR_NULL)
 				verbose(env, ",ks=%d,vs=%d",
@@ -1556,6 +1568,19 @@ static int check_subprogs(struct bpf_verifier_env *env)
 
 	/* determine subprog starts. The end is one before the next starts */
 	for (i = 0; i < insn_cnt; i++) {
+		if (bpf_pseudo_func(insn + i)) {
+			if (!env->bpf_capable) {
+				verbose(env,
+					"function pointers are allowed for CAP_BPF and CAP_SYS_ADMIN\n");
+				return -EPERM;
+			}
+			ret = add_subprog(env, i + insn[i].imm + 1);
+			if (ret < 0)
+				return ret;
+			/* remember subprog */
+			insn[i + 1].imm = find_subprog(env, i + insn[i].imm + 1);
+			continue;
+		}
 		if (!bpf_pseudo_call(insn + i))
 			continue;
 		if (!env->bpf_capable) {
@@ -2287,6 +2312,8 @@ static bool is_spillable_regtype(enum bpf_reg_type type)
 	case PTR_TO_PERCPU_BTF_ID:
 	case PTR_TO_MEM:
 	case PTR_TO_MEM_OR_NULL:
+	case PTR_TO_FUNC:
+	case PTR_TO_MAP_KEY:
 		return true;
 	default:
 		return false;
@@ -2891,6 +2918,10 @@ static int __check_mem_access(struct bpf_verifier_env *env, int regno,
 
 	reg = &cur_regs(env)[regno];
 	switch (reg->type) {
+	case PTR_TO_MAP_KEY:
+		verbose(env, "invalid access to map key, key_size=%d off=%d size=%d\n",
+			mem_size, off, size);
+		break;
 	case PTR_TO_MAP_VALUE:
 		verbose(env, "invalid access to map value, value_size=%d off=%d size=%d\n",
 			mem_size, off, size);
@@ -3296,6 +3327,9 @@ static int check_ptr_alignment(struct bpf_verifier_env *env,
 	case PTR_TO_FLOW_KEYS:
 		pointer_desc = "flow keys ";
 		break;
+	case PTR_TO_MAP_KEY:
+		pointer_desc = "key ";
+		break;
 	case PTR_TO_MAP_VALUE:
 		pointer_desc = "value ";
 		break;
@@ -3397,7 +3431,7 @@ static int check_max_stack_depth(struct bpf_verifier_env *env)
 continue_func:
 	subprog_end = subprog[idx + 1].start;
 	for (; i < subprog_end; i++) {
-		if (!bpf_pseudo_call(insn + i))
+		if (!bpf_pseudo_call(insn + i) && !bpf_pseudo_func(insn + i))
 			continue;
 		/* remember insn and function to return to */
 		ret_insn[frame] = i + 1;
@@ -3834,7 +3868,19 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
 	/* for access checks, reg->off is just part of off */
 	off += reg->off;
 
-	if (reg->type == PTR_TO_MAP_VALUE) {
+	if (reg->type == PTR_TO_MAP_KEY) {
+		if (t == BPF_WRITE) {
+			verbose(env, "write to change key R%d not allowed\n", regno);
+			return -EACCES;
+		}
+
+		err = check_mem_region_access(env, regno, off, size,
+					      reg->map_ptr->key_size, false);
+		if (err)
+			return err;
+		if (value_regno >= 0)
+			mark_reg_unknown(env, regs, value_regno);
+	} else if (reg->type == PTR_TO_MAP_VALUE) {
 		if (t == BPF_WRITE && value_regno >= 0 &&
 		    is_pointer_value(env, value_regno)) {
 			verbose(env, "R%d leaks addr into map\n", value_regno);
@@ -4250,6 +4296,9 @@ static int check_helper_mem_access(struct bpf_verifier_env *env, int regno,
 	case PTR_TO_PACKET_META:
 		return check_packet_access(env, regno, reg->off, access_size,
 					   zero_size_allowed);
+	case PTR_TO_MAP_KEY:
+		return check_mem_region_access(env, regno, reg->off, access_size,
+					       reg->map_ptr->key_size, false);
 	case PTR_TO_MAP_VALUE:
 		if (check_map_access_type(env, regno, reg->off, access_size,
 					  meta && meta->raw_mode ? BPF_WRITE :
@@ -4466,6 +4515,7 @@ static const struct bpf_reg_types map_key_value_types = {
 		PTR_TO_STACK,
 		PTR_TO_PACKET,
 		PTR_TO_PACKET_META,
+		PTR_TO_MAP_KEY,
 		PTR_TO_MAP_VALUE,
 	},
 };
@@ -4497,6 +4547,7 @@ static const struct bpf_reg_types mem_types = {
 		PTR_TO_STACK,
 		PTR_TO_PACKET,
 		PTR_TO_PACKET_META,
+		PTR_TO_MAP_KEY,
 		PTR_TO_MAP_VALUE,
 		PTR_TO_MEM,
 		PTR_TO_RDONLY_BUF,
@@ -4509,6 +4560,7 @@ static const struct bpf_reg_types int_ptr_types = {
 		PTR_TO_STACK,
 		PTR_TO_PACKET,
 		PTR_TO_PACKET_META,
+		PTR_TO_MAP_KEY,
 		PTR_TO_MAP_VALUE,
 	},
 };
@@ -4521,6 +4573,8 @@ static const struct bpf_reg_types const_map_ptr_types = { .types = { CONST_PTR_T
 static const struct bpf_reg_types btf_ptr_types = { .types = { PTR_TO_BTF_ID } };
 static const struct bpf_reg_types spin_lock_types = { .types = { PTR_TO_MAP_VALUE } };
 static const struct bpf_reg_types percpu_btf_ptr_types = { .types = { PTR_TO_PERCPU_BTF_ID } };
+static const struct bpf_reg_types func_ptr_types = { .types = { PTR_TO_FUNC } };
+static const struct bpf_reg_types stack_ptr_types = { .types = { PTR_TO_STACK } };
 
 static const struct bpf_reg_types *compatible_reg_types[__BPF_ARG_TYPE_MAX] = {
 	[ARG_PTR_TO_MAP_KEY]		= &map_key_value_types,
@@ -4549,6 +4603,8 @@ static const struct bpf_reg_types *compatible_reg_types[__BPF_ARG_TYPE_MAX] = {
 	[ARG_PTR_TO_INT]		= &int_ptr_types,
 	[ARG_PTR_TO_LONG]		= &int_ptr_types,
 	[ARG_PTR_TO_PERCPU_BTF_ID]	= &percpu_btf_ptr_types,
+	[ARG_PTR_TO_FUNC]		= &func_ptr_types,
+	[ARG_PTR_TO_STACK_OR_NULL]	= &stack_ptr_types,
 };
 
 static int check_reg_type(struct bpf_verifier_env *env, u32 regno,
@@ -4730,6 +4786,8 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
 			verbose(env, "verifier internal error\n");
 			return -EFAULT;
 		}
+	} else if (arg_type == ARG_PTR_TO_FUNC) {
+		meta->subprogno = reg->subprogno;
 	} else if (arg_type_is_mem_ptr(arg_type)) {
 		/* The access to this pointer is only checked when we hit the
 		 * next is_mem_size argument below.
@@ -5377,6 +5435,34 @@ static int check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	return __check_func_call(env, insn, insn_idx, -1, set_callee_state);
 }
 
+static int set_map_elem_callback_state(struct bpf_verifier_env *env,
+				       struct bpf_func_state *caller,
+				       struct bpf_func_state *callee,
+				       int insn_idx)
+{
+	struct bpf_insn_aux_data *insn_aux = &env->insn_aux_data[insn_idx];
+	struct bpf_map *map;
+	int err;
+
+	if (bpf_map_ptr_poisoned(insn_aux)) {
+		verbose(env, "tail_call abusing map_ptr\n");
+		return -EINVAL;
+	}
+
+	map = BPF_MAP_PTR(insn_aux->map_ptr_state);
+	if (!map->ops->map_set_for_each_callback_args ||
+	    !map->ops->map_for_each_callback) {
+		verbose(env, "callback function not allowed for map\n");
+		return -ENOTSUPP;
+	}
+
+	err = map->ops->map_set_for_each_callback_args(env, caller, callee);
+	if (err)
+		return err;
+
+	return 0;
+}
+
 static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 {
 	struct bpf_verifier_state *state = env->cur_state;
@@ -5399,8 +5485,22 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)
 
 	state->curframe--;
 	caller = state->frame[state->curframe];
-	/* return to the caller whatever r0 had in the callee */
-	caller->regs[BPF_REG_0] = *r0;
+	if (!callee->in_callback_fn) {
+		/* return to the caller whatever r0 had in the callee */
+		caller->regs[BPF_REG_0] = *r0;
+	} else {
+		/* enforce R0 return value range [0, 1]. */
+		struct tnum range = tnum_range(0, 1);
+
+		if (r0->type != SCALAR_VALUE) {
+			verbose(env, "R0 not a scalar value\n");
+			return -EACCES;
+		}
+		if (!tnum_in(range, r0->var_off)) {
+			verbose_invalid_scalar(env, r0, &range, "callback return", "R0");
+			return -EINVAL;
+		}
+	}
 
 	/* Transfer references to the caller */
 	err = transfer_reference_state(caller, callee);
@@ -5455,7 +5555,8 @@ record_func_map(struct bpf_verifier_env *env, struct bpf_call_arg_meta *meta,
 	    func_id != BPF_FUNC_map_delete_elem &&
 	    func_id != BPF_FUNC_map_push_elem &&
 	    func_id != BPF_FUNC_map_pop_elem &&
-	    func_id != BPF_FUNC_map_peek_elem)
+	    func_id != BPF_FUNC_map_peek_elem &&
+	    func_id != BPF_FUNC_for_each_map_elem)
 		return 0;
 
 	if (map == NULL) {
@@ -5536,15 +5637,18 @@ static int check_reference_leak(struct bpf_verifier_env *env)
 	return state->acquired_refs ? -EINVAL : 0;
 }
 
-static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn_idx)
+static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
+			     int *insn_idx_p)
 {
 	const struct bpf_func_proto *fn = NULL;
 	struct bpf_reg_state *regs;
 	struct bpf_call_arg_meta meta;
+	int insn_idx = *insn_idx_p;
 	bool changes_data;
-	int i, err;
+	int i, err, func_id;
 
 	/* find function prototype */
+	func_id = insn->imm;
 	if (func_id < 0 || func_id >= __BPF_FUNC_MAX_ID) {
 		verbose(env, "invalid func %s#%d\n", func_id_name(func_id),
 			func_id);
@@ -5640,6 +5744,13 @@ static int check_helper_call(struct bpf_verifier_env *env, int func_id, int insn
 		return -EINVAL;
 	}
 
+	if (func_id == BPF_FUNC_for_each_map_elem) {
+		err = __check_func_call(env, insn, insn_idx_p, meta.subprogno,
+					set_map_elem_callback_state);
+		if (err < 0)
+			return -EINVAL;
+	}
+
 	/* reset caller saved regs */
 	for (i = 0; i < CALLER_SAVED_REGS; i++) {
 		mark_reg_not_init(env, regs, caller_saved[i]);
@@ -5893,6 +6004,14 @@ static int retrieve_ptr_limit(const struct bpf_reg_state *ptr_reg,
 		else
 			*ptr_limit = -off;
 		return 0;
+	case PTR_TO_MAP_KEY:
+		if (mask_to_left) {
+			*ptr_limit = ptr_reg->umax_value + ptr_reg->off;
+		} else {
+			off = ptr_reg->smin_value + ptr_reg->off;
+			*ptr_limit = ptr_reg->map_ptr->key_size - off;
+		}
+		return 0;
 	case PTR_TO_MAP_VALUE:
 		if (mask_to_left) {
 			*ptr_limit = ptr_reg->umax_value + ptr_reg->off;
@@ -6094,6 +6213,7 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
 		verbose(env, "R%d pointer arithmetic on %s prohibited\n",
 			dst, reg_type_str[ptr_reg->type]);
 		return -EACCES;
+	case PTR_TO_MAP_KEY:
 	case PTR_TO_MAP_VALUE:
 		if (!env->allow_ptr_leaks && !known && (smin_val < 0) != (smax_val < 0)) {
 			verbose(env, "R%d has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root\n",
@@ -8273,6 +8393,21 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
 		return 0;
 	}
 
+	if (insn->src_reg == BPF_PSEUDO_FUNC) {
+		struct bpf_prog_aux *aux = env->prog->aux;
+		u32 subprogno = insn[1].imm;
+
+		if (aux->func_info &&
+		    aux->func_info_aux[subprogno].linkage != BTF_FUNC_STATIC) {
+			verbose(env, "callback function not static\n");
+			return -EINVAL;
+		}
+
+		dst_reg->type = PTR_TO_FUNC;
+		dst_reg->subprogno = subprogno;
+		return 0;
+	}
+
 	map = env->used_maps[aux->map_index];
 	mark_reg_known_zero(env, regs, insn->dst_reg);
 	dst_reg->map_ptr = map;
@@ -8659,6 +8794,9 @@ static int visit_insn(int t, int insn_cnt, struct bpf_verifier_env *env)
 	struct bpf_insn *insns = env->prog->insnsi;
 	int ret;
 
+	if (bpf_pseudo_func(insns + t))
+		return visit_func_call_insn(t, insn_cnt, insns, env, true);
+
 	/* All non-branch instructions have a single fall-through edge. */
 	if (BPF_CLASS(insns[t].code) != BPF_JMP &&
 	    BPF_CLASS(insns[t].code) != BPF_JMP32)
@@ -9275,6 +9413,7 @@ static bool regsafe(struct bpf_reg_state *rold, struct bpf_reg_state *rcur,
 			 */
 			return false;
 		}
+	case PTR_TO_MAP_KEY:
 	case PTR_TO_MAP_VALUE:
 		/* If the new min/max/var_off satisfy the old ones and
 		 * everything else matches, we are OK.
@@ -10121,10 +10260,9 @@ static int do_check(struct bpf_verifier_env *env)
 				if (insn->src_reg == BPF_PSEUDO_CALL)
 					err = check_func_call(env, insn, &env->insn_idx);
 				else
-					err = check_helper_call(env, insn->imm, env->insn_idx);
+					err = check_helper_call(env, insn, &env->insn_idx);
 				if (err)
 					return err;
-
 			} else if (opcode == BPF_JA) {
 				if (BPF_SRC(insn->code) != BPF_K ||
 				    insn->imm != 0 ||
@@ -10553,6 +10691,12 @@ static int resolve_pseudo_ldimm64(struct bpf_verifier_env *env)
 				goto next_insn;
 			}
 
+			if (insn[0].src_reg == BPF_PSEUDO_FUNC) {
+				aux = &env->insn_aux_data[i];
+				aux->ptr_type = PTR_TO_FUNC;
+				goto next_insn;
+			}
+
 			/* In final convert_pseudo_ld_imm64() step, this is
 			 * converted into regular 64-bit imm load insn.
 			 */
@@ -10685,9 +10829,13 @@ static void convert_pseudo_ld_imm64(struct bpf_verifier_env *env)
 	int insn_cnt = env->prog->len;
 	int i;
 
-	for (i = 0; i < insn_cnt; i++, insn++)
-		if (insn->code == (BPF_LD | BPF_IMM | BPF_DW))
-			insn->src_reg = 0;
+	for (i = 0; i < insn_cnt; i++, insn++) {
+		if (insn->code != (BPF_LD | BPF_IMM | BPF_DW))
+			continue;
+		if (insn->src_reg == BPF_PSEUDO_FUNC)
+			continue;
+		insn->src_reg = 0;
+	}
 }
 
 /* single env->prog->insni[off] instruction was replaced with the range
@@ -11328,6 +11476,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 		return 0;
 
 	for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
+		if (bpf_pseudo_func(insn)) {
+			env->insn_aux_data[i].call_imm = insn->imm;
+			/* subprog is encoded in insn[1].imm */
+			continue;
+		}
+
 		if (!bpf_pseudo_call(insn))
 			continue;
 		/* Upon error here we cannot fall back to interpreter but
@@ -11457,6 +11611,12 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	for (i = 0; i < env->subprog_cnt; i++) {
 		insn = func[i]->insnsi;
 		for (j = 0; j < func[i]->len; j++, insn++) {
+			if (bpf_pseudo_func(insn)) {
+				subprog = insn[1].imm;
+				insn[0].imm = (u32)(long)func[subprog]->bpf_func;
+				insn[1].imm = ((u64)(long)func[subprog]->bpf_func) >> 32;
+				continue;
+			}
 			if (!bpf_pseudo_call(insn))
 				continue;
 			subprog = insn->off;
@@ -11502,6 +11662,11 @@ static int jit_subprogs(struct bpf_verifier_env *env)
 	 * later look the same as if they were interpreted only.
 	 */
 	for (i = 0, insn = prog->insnsi; i < prog->len; i++, insn++) {
+		if (bpf_pseudo_func(insn)) {
+			insn[0].imm = env->insn_aux_data[i].call_imm;
+			insn[1].imm = find_subprog(env, i + insn[0].imm + 1);
+			continue;
+		}
 		if (!bpf_pseudo_call(insn))
 			continue;
 		insn->off = env->insn_aux_data[i].call_imm;
@@ -11566,6 +11731,14 @@ static int fixup_call_args(struct bpf_verifier_env *env)
 		return -EINVAL;
 	}
 	for (i = 0; i < prog->len; i++, insn++) {
+		if (bpf_pseudo_func(insn)) {
+			/* When JIT fails the progs with callback calls
+			 * have to be rejected, since interpreter doesn't support them yet.
+			 */
+			verbose(env, "callbacks are not allowed in non-JITed programs\n");
+			return -EINVAL;
+		}
+
 		if (!bpf_pseudo_call(insn))
 			continue;
 		depth = get_callee_stack_depth(env, insn, i);
diff --git a/kernel/trace/bpf_trace.c b/kernel/trace/bpf_trace.c
index 0b9e4fd9c61b..e95eeea8f7d8 100644
--- a/kernel/trace/bpf_trace.c
+++ b/kernel/trace/bpf_trace.c
@@ -1370,6 +1370,8 @@ bpf_tracing_func_proto(enum bpf_func_id func_id, const struct bpf_prog *prog)
 		return &bpf_per_cpu_ptr_proto;
 	case BPF_FUNC_this_cpu_ptr:
 		return &bpf_this_cpu_ptr_proto;
+	case BPF_FUNC_for_each_map_elem:
+		return &bpf_for_each_map_elem_proto;
 	default:
 		return NULL;
 	}
diff --git a/tools/include/uapi/linux/bpf.h b/tools/include/uapi/linux/bpf.h
index 4c24daa43bac..0ed65fd87732 100644
--- a/tools/include/uapi/linux/bpf.h
+++ b/tools/include/uapi/linux/bpf.h
@@ -393,6 +393,15 @@ enum bpf_link_type {
  *                   is struct/union.
  */
 #define BPF_PSEUDO_BTF_ID	3
+/* insn[0].src_reg:  BPF_PSEUDO_FUNC
+ * insn[0].imm:      insn offset to the func
+ * insn[1].imm:      0
+ * insn[0].off:      0
+ * insn[1].off:      0
+ * ldimm64 rewrite:  address of the function
+ * verifier type:    PTR_TO_FUNC.
+ */
+#define BPF_PSEUDO_FUNC		4
 
 /* when bpf_call->src_reg == BPF_PSEUDO_CALL, bpf_call->imm == pc-relative
  * offset to another bpf function
@@ -3850,7 +3859,6 @@ union bpf_attr {
  *
  * long bpf_check_mtu(void *ctx, u32 ifindex, u32 *mtu_len, s32 len_diff, u64 flags)
  *	Description
-
  *		Check ctx packet size against exceeding MTU of net device (based
  *		on *ifindex*).  This helper will likely be used in combination
  *		with helpers that adjust/change the packet size.
@@ -3910,6 +3918,24 @@ union bpf_attr {
  *		* **BPF_MTU_CHK_RET_FRAG_NEEDED**
  *		* **BPF_MTU_CHK_RET_SEGS_TOOBIG**
  *
+ * long bpf_for_each_map_elem(struct bpf_map *map, void *callback_fn, void *callback_ctx, u64 flags)
+ *	Description
+ *		For each element in **map**, call **callback_fn** function with
+ *		**map**, **callback_ctx** and other map-specific parameters.
+ *		For example, for hash and array maps, the callback signature can
+ *		be `long callback_fn(map, map_key, map_value, callback_ctx)`.
+ *		The **callback_fn** should be a static function and
+ *		the **callback_ctx** should be a pointer to the stack.
+ *		The **flags** is used to control certain aspects of the helper.
+ *		Currently, the **flags** must be 0. For per_cpu maps,
+ *		the map_value is the value on the cpu where the bpf_prog is running.
+ *
+ *		If **callback_fn** return 0, the helper will continue to the next
+ *		element. If return value is 1, the helper will skip the rest of
+ *		elements and return. Other return values are not used now.
+ *	Return
+ *		The number of traversed map elements for success, **-EINVAL** for
+ *		invalid **flags** or unsupported **callback_fn** return value.
  */
 #define __BPF_FUNC_MAPPER(FN)		\
 	FN(unspec),			\
@@ -4076,6 +4102,7 @@ union bpf_attr {
 	FN(ima_inode_hash),		\
 	FN(sock_from_file),		\
 	FN(check_mtu),			\
+	FN(for_each_map_elem),		\
 	/* */
 
 /* integer value in 'imm' field of BPF_CALL instruction selects which helper
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 05/11] bpf: add hashtab support for bpf_for_each_map_elem() helper
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (3 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-22 22:56   ` Alexei Starovoitov
  2021-02-17 18:18 ` [PATCH bpf-next v2 06/11] bpf: add arraymap " Yonghong Song
                   ` (6 subsequent siblings)
  11 siblings, 1 reply; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

This patch added support for hashmap, percpu hashmap,
lru hashmap and percpu lru hashmap.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 include/linux/bpf.h   |  4 +++
 kernel/bpf/hashtab.c  | 63 +++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c | 27 +++++++++++++++++++
 3 files changed, 94 insertions(+)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 40f41a9b40f9..34277ab1eda5 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -1392,6 +1392,10 @@ void bpf_iter_map_show_fdinfo(const struct bpf_iter_aux_info *aux,
 int bpf_iter_map_fill_link_info(const struct bpf_iter_aux_info *aux,
 				struct bpf_link_info *info);
 
+int map_set_for_each_callback_args(struct bpf_verifier_env *env,
+				   struct bpf_func_state *caller,
+				   struct bpf_func_state *callee);
+
 int bpf_percpu_hash_copy(struct bpf_map *map, void *key, void *value);
 int bpf_percpu_array_copy(struct bpf_map *map, void *key, void *value);
 int bpf_percpu_hash_update(struct bpf_map *map, void *key, void *value,
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index d63912e73ad9..f652b92ca79f 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -1869,6 +1869,61 @@ static const struct bpf_iter_seq_info iter_seq_info = {
 	.seq_priv_size		= sizeof(struct bpf_iter_seq_hash_map_info),
 };
 
+static int bpf_for_each_hash_elem(struct bpf_map *map, void *callback_fn,
+				  void *callback_ctx, u64 flags)
+{
+	struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
+	struct hlist_nulls_head *head;
+	long ret = 0, num_calls = 0;
+	struct hlist_nulls_node *n;
+	struct htab_elem *elem;
+	u32 roundup_key_size;
+	void __percpu *pptr;
+	struct bucket *b;
+	void *key, *val;
+	bool is_percpu;
+	int i;
+
+	if (flags != 0)
+		return -EINVAL;
+
+	is_percpu = htab_is_percpu(htab);
+
+	roundup_key_size = round_up(map->key_size, 8);
+	/* disable migration so percpu value prepared here will be the
+	 * same as the one seen by the bpf program with bpf_map_lookup_elem().
+	 */
+	migrate_disable();
+	for (i = 0; i < htab->n_buckets; i++) {
+		b = &htab->buckets[i];
+		rcu_read_lock();
+		head = &b->head;
+		hlist_nulls_for_each_entry_rcu(elem, n, head, hash_node) {
+			key = elem->key;
+			if (!is_percpu) {
+				val = elem->key + roundup_key_size;
+			} else {
+				/* current cpu value for percpu map */
+				pptr = htab_elem_get_ptr(elem, map->key_size);
+				val = this_cpu_ptr(pptr);
+			}
+			num_calls++;
+			ret = BPF_CAST_CALL(callback_fn)((u64)(long)map,
+					(u64)(long)key, (u64)(long)val,
+					(u64)(long)callback_ctx, 0);
+			if (ret) {
+				rcu_read_unlock();
+				ret = (ret == 1) ? 0 : -EINVAL;
+				goto out;
+			}
+		}
+		rcu_read_unlock();
+	}
+out:
+	migrate_enable();
+	return ret ?: num_calls;
+}
+
 static int htab_map_btf_id;
 const struct bpf_map_ops htab_map_ops = {
 	.map_meta_equal = bpf_map_meta_equal,
@@ -1881,6 +1936,8 @@ const struct bpf_map_ops htab_map_ops = {
 	.map_delete_elem = htab_map_delete_elem,
 	.map_gen_lookup = htab_map_gen_lookup,
 	.map_seq_show_elem = htab_map_seq_show_elem,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_for_each_hash_elem,
 	BATCH_OPS(htab),
 	.map_btf_name = "bpf_htab",
 	.map_btf_id = &htab_map_btf_id,
@@ -1900,6 +1957,8 @@ const struct bpf_map_ops htab_lru_map_ops = {
 	.map_delete_elem = htab_lru_map_delete_elem,
 	.map_gen_lookup = htab_lru_map_gen_lookup,
 	.map_seq_show_elem = htab_map_seq_show_elem,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_for_each_hash_elem,
 	BATCH_OPS(htab_lru),
 	.map_btf_name = "bpf_htab",
 	.map_btf_id = &htab_lru_map_btf_id,
@@ -2019,6 +2078,8 @@ const struct bpf_map_ops htab_percpu_map_ops = {
 	.map_update_elem = htab_percpu_map_update_elem,
 	.map_delete_elem = htab_map_delete_elem,
 	.map_seq_show_elem = htab_percpu_map_seq_show_elem,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_for_each_hash_elem,
 	BATCH_OPS(htab_percpu),
 	.map_btf_name = "bpf_htab",
 	.map_btf_id = &htab_percpu_map_btf_id,
@@ -2036,6 +2097,8 @@ const struct bpf_map_ops htab_lru_percpu_map_ops = {
 	.map_update_elem = htab_lru_percpu_map_update_elem,
 	.map_delete_elem = htab_lru_map_delete_elem,
 	.map_seq_show_elem = htab_percpu_map_seq_show_elem,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_for_each_hash_elem,
 	BATCH_OPS(htab_lru_percpu),
 	.map_btf_name = "bpf_htab",
 	.map_btf_id = &htab_lru_percpu_map_btf_id,
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index f80386d094b7..2ce8ed8aca70 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5415,6 +5415,33 @@ static int __check_func_call(struct bpf_verifier_env *env, struct bpf_insn *insn
 	return 0;
 }
 
+int map_set_for_each_callback_args(struct bpf_verifier_env *env,
+				   struct bpf_func_state *caller,
+				   struct bpf_func_state *callee)
+{
+	/* bpf_for_each_map_elem(struct bpf_map *map, void *callback_fn,
+	 *      void *callback_ctx, u64 flags);
+	 * callback_fn(struct bpf_map *map, void *key, void *value,
+	 *      void *callback_ctx);
+	 */
+	callee->regs[BPF_REG_1] = caller->regs[BPF_REG_1];
+
+	callee->regs[BPF_REG_2].type = PTR_TO_MAP_KEY;
+	__mark_reg_known_zero(&callee->regs[BPF_REG_2]);
+	callee->regs[BPF_REG_2].map_ptr = caller->regs[BPF_REG_1].map_ptr;
+
+	callee->regs[BPF_REG_3].type = PTR_TO_MAP_VALUE;
+	__mark_reg_known_zero(&callee->regs[BPF_REG_3]);
+	callee->regs[BPF_REG_3].map_ptr = caller->regs[BPF_REG_1].map_ptr;
+
+	/* pointer to stack or null */
+	callee->regs[BPF_REG_4] = caller->regs[BPF_REG_3];
+
+	/* unused */
+	__mark_reg_not_init(env, &callee->regs[BPF_REG_5]);
+	return 0;
+}
+
 static int set_callee_state(struct bpf_verifier_env *env,
 			    struct bpf_func_state *caller,
 			    struct bpf_func_state *callee, int insn_idx)
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 06/11] bpf: add arraymap support for bpf_for_each_map_elem() helper
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (4 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 05/11] bpf: add hashtab support for " Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 07/11] libbpf: move function is_ldimm64() earlier in libbpf.c Yonghong Song
                   ` (5 subsequent siblings)
  11 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

This patch added support for arraymap and percpu arraymap.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/arraymap.c | 39 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 39 insertions(+)

diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index 1f8453343bf2..4edd47114fe2 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -625,6 +625,41 @@ static const struct bpf_iter_seq_info iter_seq_info = {
 	.seq_priv_size		= sizeof(struct bpf_iter_seq_array_map_info),
 };
 
+static int bpf_for_each_array_elem(struct bpf_map *map, void *callback_fn,
+				   void *callback_ctx, u64 flags)
+{
+	long ret = 0, num_calls = 0;
+	struct bpf_array *array;
+	bool is_percpu;
+	u32 i, index;
+	void *val;
+
+	if (flags != 0)
+		return -EINVAL;
+
+	is_percpu = map->map_type == BPF_MAP_TYPE_PERCPU_ARRAY;
+	array = container_of(map, struct bpf_array, map);
+	migrate_disable();
+	for (i = 0; i < map->max_entries; i++) {
+		index = i & array->index_mask;
+		if (is_percpu)
+			val = this_cpu_ptr(array->pptrs[i]);
+		else
+			val = array->value + array->elem_size * i;
+		num_calls++;
+		ret = BPF_CAST_CALL(callback_fn)((u64)(long)map,
+					(u64)(long)&index, (u64)(long)val,
+					(u64)(long)callback_ctx, 0);
+		if (ret) {
+			ret = (ret == 1) ? 0 : -EINVAL;
+			break;
+		}
+	}
+
+	migrate_enable();
+	return ret ?: num_calls;
+}
+
 static int array_map_btf_id;
 const struct bpf_map_ops array_map_ops = {
 	.map_meta_equal = array_map_meta_equal,
@@ -643,6 +678,8 @@ const struct bpf_map_ops array_map_ops = {
 	.map_check_btf = array_map_check_btf,
 	.map_lookup_batch = generic_map_lookup_batch,
 	.map_update_batch = generic_map_update_batch,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_for_each_array_elem,
 	.map_btf_name = "bpf_array",
 	.map_btf_id = &array_map_btf_id,
 	.iter_seq_info = &iter_seq_info,
@@ -660,6 +697,8 @@ const struct bpf_map_ops percpu_array_map_ops = {
 	.map_delete_elem = array_map_delete_elem,
 	.map_seq_show_elem = percpu_array_map_seq_show_elem,
 	.map_check_btf = array_map_check_btf,
+	.map_set_for_each_callback_args = map_set_for_each_callback_args,
+	.map_for_each_callback = bpf_for_each_array_elem,
 	.map_btf_name = "bpf_array",
 	.map_btf_id = &percpu_array_map_btf_id,
 	.iter_seq_info = &iter_seq_info,
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 07/11] libbpf: move function is_ldimm64() earlier in libbpf.c
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (5 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 06/11] bpf: add arraymap " Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-23  8:06   ` Andrii Nakryiko
  2021-02-17 18:18 ` [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation Yonghong Song
                   ` (4 subsequent siblings)
  11 siblings, 1 reply; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

Move function is_ldimm64() close to the beginning of libbpf.c,
so it can be reused by later code and the next patch as well.
There is no functionality change.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 tools/lib/bpf/libbpf.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
index d43cc3f29dae..21a3eedf070d 100644
--- a/tools/lib/bpf/libbpf.c
+++ b/tools/lib/bpf/libbpf.c
@@ -574,6 +574,11 @@ static bool insn_is_subprog_call(const struct bpf_insn *insn)
 	       insn->off == 0;
 }
 
+static bool is_ldimm64(struct bpf_insn *insn)
+{
+	return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
+}
+
 static int
 bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
 		      const char *name, size_t sec_idx, const char *sec_name,
@@ -3395,7 +3400,7 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
 		return 0;
 	}
 
-	if (insn->code != (BPF_LD | BPF_IMM | BPF_DW)) {
+	if (!is_ldimm64(insn)) {
 		pr_warn("prog '%s': invalid relo against '%s' for insns[%d].code 0x%x\n",
 			prog->name, sym_name, insn_idx, insn->code);
 		return -LIBBPF_ERRNO__RELOC;
@@ -5566,11 +5571,6 @@ static void bpf_core_poison_insn(struct bpf_program *prog, int relo_idx,
 	insn->imm = 195896080; /* => 0xbad2310 => "bad relo" */
 }
 
-static bool is_ldimm64(struct bpf_insn *insn)
-{
-	return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
-}
-
 static int insn_bpf_size_to_bytes(struct bpf_insn *insn)
 {
 	switch (BPF_SIZE(insn->code)) {
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (6 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 07/11] libbpf: move function is_ldimm64() earlier in libbpf.c Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-23  8:03   ` Andrii Nakryiko
  2021-02-17 18:18 ` [PATCH bpf-next v2 09/11] bpftool: print local function pointer properly Yonghong Song
                   ` (3 subsequent siblings)
  11 siblings, 1 reply; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

A new relocation RELO_SUBPROG_ADDR is added to capture
local (static) function pointers loaded with ld_imm64
insns. Such ld_imm64 insns are marked with
BPF_PSEUDO_FUNC and will be passed to kernel so
kernel can replace them with proper actual jited
func addresses.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 tools/lib/bpf/libbpf.c | 40 +++++++++++++++++++++++++++++++++++++---
 1 file changed, 37 insertions(+), 3 deletions(-)

diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
index 21a3eedf070d..772c7455f1a2 100644
--- a/tools/lib/bpf/libbpf.c
+++ b/tools/lib/bpf/libbpf.c
@@ -188,6 +188,7 @@ enum reloc_type {
 	RELO_CALL,
 	RELO_DATA,
 	RELO_EXTERN,
+	RELO_SUBPROG_ADDR,
 };
 
 struct reloc_desc {
@@ -579,6 +580,11 @@ static bool is_ldimm64(struct bpf_insn *insn)
 	return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
 }
 
+static bool insn_is_pseudo_func(struct bpf_insn *insn)
+{
+	return is_ldimm64(insn) && insn->src_reg == BPF_PSEUDO_FUNC;
+}
+
 static int
 bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
 		      const char *name, size_t sec_idx, const char *sec_name,
@@ -3406,6 +3412,16 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
 		return -LIBBPF_ERRNO__RELOC;
 	}
 
+	if (GELF_ST_BIND(sym->st_info) == STB_LOCAL &&
+	    GELF_ST_TYPE(sym->st_info) == STT_SECTION &&
+	    (!shdr_idx || shdr_idx == obj->efile.text_shndx) &&
+	    !(sym->st_value % BPF_INSN_SZ)) {
+		reloc_desc->type = RELO_SUBPROG_ADDR;
+		reloc_desc->insn_idx = insn_idx;
+		reloc_desc->sym_off = sym->st_value;
+		return 0;
+	}
+
 	if (sym_is_extern(sym)) {
 		int sym_idx = GELF_R_SYM(rel->r_info);
 		int i, n = obj->nr_extern;
@@ -6172,6 +6188,10 @@ bpf_object__relocate_data(struct bpf_object *obj, struct bpf_program *prog)
 			}
 			relo->processed = true;
 			break;
+		case RELO_SUBPROG_ADDR:
+			insn[0].src_reg = BPF_PSEUDO_FUNC;
+			/* will be handled as a follow up pass */
+			break;
 		case RELO_CALL:
 			/* will be handled as a follow up pass */
 			break;
@@ -6358,11 +6378,11 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
 
 	for (insn_idx = 0; insn_idx < prog->sec_insn_cnt; insn_idx++) {
 		insn = &main_prog->insns[prog->sub_insn_off + insn_idx];
-		if (!insn_is_subprog_call(insn))
+		if (!insn_is_subprog_call(insn) && !insn_is_pseudo_func(insn))
 			continue;
 
 		relo = find_prog_insn_relo(prog, insn_idx);
-		if (relo && relo->type != RELO_CALL) {
+		if (relo && relo->type != RELO_CALL && relo->type != RELO_SUBPROG_ADDR) {
 			pr_warn("prog '%s': unexpected relo for insn #%zu, type %d\n",
 				prog->name, insn_idx, relo->type);
 			return -LIBBPF_ERRNO__RELOC;
@@ -6374,8 +6394,22 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
 			 * call always has imm = -1, but for static functions
 			 * relocation is against STT_SECTION and insn->imm
 			 * points to a start of a static function
+			 *
+			 * for local func relocation, the imm field encodes
+			 * the byte offset in the corresponding section.
+			 */
+			if (relo->type == RELO_CALL)
+				sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
+			else
+				sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm / BPF_INSN_SZ + 1;
+		} else if (insn_is_pseudo_func(insn)) {
+			/*
+			 * RELO_SUBPROG_ADDR relo is always emitted even if both
+			 * functions are in the same section, so it shouldn't reach here.
 			 */
-			sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
+			pr_warn("prog '%s': missing relo for insn #%zu, type %d\n",
+				prog->name, insn_idx, relo->type);
+			return -LIBBPF_ERRNO__RELOC;
 		} else {
 			/* if subprogram call is to a static function within
 			 * the same ELF section, there won't be any relocation
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 09/11] bpftool: print local function pointer properly
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (7 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-23  8:06   ` Andrii Nakryiko
  2021-02-17 18:18 ` [PATCH bpf-next v2 10/11] selftests/bpf: add hashmap test for bpf_for_each_map_elem() helper Yonghong Song
                   ` (2 subsequent siblings)
  11 siblings, 1 reply; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

With later hashmap example, using bpftool xlated output may
look like:
  int dump_task(struct bpf_iter__task * ctx):
  ; struct task_struct *task = ctx->task;
     0: (79) r2 = *(u64 *)(r1 +8)
  ; if (task == (void *)0 || called > 0)
  ...
    19: (18) r2 = subprog[+18]
    30: (18) r2 = subprog[+26]
  ...
  36: (95) exit
  __u64 check_hash_elem(struct bpf_map * map, __u32 * key, __u64 * val,
                        struct callback_ctx * data):
  ; struct bpf_iter__task *ctx = data->ctx;
    37: (79) r5 = *(u64 *)(r4 +0)
  ...
    55: (95) exit
  __u64 check_percpu_elem(struct bpf_map * map, __u32 * key,
                          __u64 * val, void * unused):
  ; check_percpu_elem(struct bpf_map *map, __u32 *key, __u64 *val, void *unused)
    56: (bf) r6 = r3
  ...
    83: (18) r2 = subprog[-46]

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 tools/bpf/bpftool/xlated_dumper.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/tools/bpf/bpftool/xlated_dumper.c b/tools/bpf/bpftool/xlated_dumper.c
index 8608cd68cdd0..b87caae2e7da 100644
--- a/tools/bpf/bpftool/xlated_dumper.c
+++ b/tools/bpf/bpftool/xlated_dumper.c
@@ -196,6 +196,9 @@ static const char *print_imm(void *private_data,
 	else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE)
 		snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
 			 "map[id:%u][0]+%u", insn->imm, (insn + 1)->imm);
+	else if (insn->src_reg == BPF_PSEUDO_FUNC)
+		snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
+			 "subprog[%+d]", insn->imm + 1);
 	else
 		snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
 			 "0x%llx", (unsigned long long)full_imm);
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 10/11] selftests/bpf: add hashmap test for bpf_for_each_map_elem() helper
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (8 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 09/11] bpftool: print local function pointer properly Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-17 18:18 ` [PATCH bpf-next v2 11/11] selftests/bpf: add arraymap " Yonghong Song
  2021-02-17 18:29 ` [PATCH bpf-next v2 00/11] bpf: add " Yonghong Song
  11 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

A test case is added for hashmap and percpu hashmap. The test
also exercises nested bpf_for_each_map_elem() calls like
    bpf_prog:
      bpf_for_each_map_elem(func1)
    func1:
      bpf_for_each_map_elem(func2)
    func2:

  $ ./test_progs -n 44
  #44/1 hash_map:OK
  #44 for_each:OK
  Summary: 1/1 PASSED, 0 SKIPPED, 0 FAILED

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 .../selftests/bpf/prog_tests/for_each.c       | 74 +++++++++++++++
 .../bpf/progs/for_each_hash_map_elem.c        | 95 +++++++++++++++++++
 2 files changed, 169 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/for_each.c
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_hash_map_elem.c

diff --git a/tools/testing/selftests/bpf/prog_tests/for_each.c b/tools/testing/selftests/bpf/prog_tests/for_each.c
new file mode 100644
index 000000000000..aa0c23e83ab8
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/for_each.c
@@ -0,0 +1,74 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2021 Facebook */
+#include <test_progs.h>
+#include <network_helpers.h>
+#include "for_each_hash_map_elem.skel.h"
+
+static unsigned int duration;
+
+static void test_hash_map(void)
+{
+	int i, err, hashmap_fd, max_entries, percpu_map_fd;
+	struct for_each_hash_map_elem *skel;
+	__u64 *percpu_valbuf = NULL;
+	__u32 key, num_cpus, retval;
+	__u64 val;
+
+	skel = for_each_hash_map_elem__open_and_load();
+	if (CHECK(!skel, "for_each_hash_map_elem__open_and_load",
+		  "skeleton open_and_load failed\n"))
+		return;
+
+	hashmap_fd = bpf_map__fd(skel->maps.hashmap);
+	max_entries = bpf_map__max_entries(skel->maps.hashmap);
+	for (i = 0; i < max_entries; i++) {
+		key = i;
+		val = i + 1;
+		err = bpf_map_update_elem(hashmap_fd, &key, &val, BPF_ANY);
+		if (CHECK(err, "map_update", "map_update failed\n"))
+			goto out;
+	}
+
+	num_cpus = bpf_num_possible_cpus();
+	percpu_map_fd = bpf_map__fd(skel->maps.percpu_map);
+	percpu_valbuf = malloc(sizeof(__u64) * num_cpus);
+	if (!ASSERT_OK_PTR(percpu_valbuf, "percpu_valbuf"))
+		goto out;
+
+	key = 1;
+	for (i = 0; i < num_cpus; i++)
+		percpu_valbuf[i] = i + 1;
+	err = bpf_map_update_elem(percpu_map_fd, &key, percpu_valbuf, BPF_ANY);
+	if (CHECK(err, "percpu_map_update", "map_update failed\n"))
+		goto out;
+
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_pkt_access),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+	if (CHECK(err || retval, "ipv4", "err %d errno %d retval %d\n",
+		  err, errno, retval))
+		goto out;
+
+	ASSERT_EQ(skel->bss->hashmap_output, 4, "hashmap_output");
+	ASSERT_EQ(skel->bss->hashmap_elems, max_entries, "hashmap_elems");
+
+	key = 1;
+	err = bpf_map_lookup_elem(hashmap_fd, &key, &val);
+	ASSERT_ERR(err, "hashmap_lookup");
+
+	ASSERT_EQ(skel->bss->percpu_called, 1, "percpu_called");
+	ASSERT_EQ(skel->bss->cpu < num_cpus, 1, "num_cpus");
+	ASSERT_EQ(skel->bss->percpu_map_elems, 1, "percpu_map_elems");
+	ASSERT_EQ(skel->bss->percpu_key, 1, "percpu_key");
+	ASSERT_EQ(skel->bss->percpu_val, skel->bss->cpu + 1, "percpu_val");
+	ASSERT_EQ(skel->bss->percpu_output, 100, "percpu_output");
+out:
+	free(percpu_valbuf);
+	for_each_hash_map_elem__destroy(skel);
+}
+
+void test_for_each(void)
+{
+	if (test__start_subtest("hash_map"))
+		test_hash_map();
+}
diff --git a/tools/testing/selftests/bpf/progs/for_each_hash_map_elem.c b/tools/testing/selftests/bpf/progs/for_each_hash_map_elem.c
new file mode 100644
index 000000000000..e47e68d7a769
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/for_each_hash_map_elem.c
@@ -0,0 +1,95 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2021 Facebook */
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+
+char _license[] SEC("license") = "GPL";
+
+struct {
+	__uint(type, BPF_MAP_TYPE_HASH);
+	__uint(max_entries, 3);
+	__type(key, __u32);
+	__type(value, __u64);
+} hashmap SEC(".maps");
+
+struct {
+	__uint(type, BPF_MAP_TYPE_PERCPU_HASH);
+	__uint(max_entries, 1);
+	__type(key, __u32);
+	__type(value, __u64);
+} percpu_map SEC(".maps");
+
+struct callback_ctx {
+	struct __sk_buff *ctx;
+	int input;
+	int output;
+};
+
+static __u64
+check_hash_elem(struct bpf_map *map, __u32 *key, __u64 *val,
+		struct callback_ctx *data)
+{
+	struct __sk_buff *skb = data->ctx;
+	__u32 k;
+	__u64 v;
+
+	if (skb) {
+		k = *key;
+		v = *val;
+		if (skb->len == 10000 && k == 10 && v == 10)
+			data->output = 3; /* impossible path */
+		else
+			data->output = 4;
+	} else {
+		data->output = data->input;
+		bpf_map_delete_elem(map, key);
+	}
+
+	return 0;
+}
+
+__u32 cpu = 0;
+__u32 percpu_called = 0;
+__u32 percpu_key = 0;
+__u64 percpu_val = 0;
+int percpu_output = 0;
+
+static __u64
+check_percpu_elem(struct bpf_map *map, __u32 *key, __u64 *val,
+		  struct callback_ctx *unused)
+{
+	struct callback_ctx data;
+
+	percpu_called++;
+	cpu = bpf_get_smp_processor_id();
+	percpu_key = *key;
+	percpu_val = *val;
+
+	data.ctx = 0;
+	data.input = 100;
+	data.output = 0;
+	bpf_for_each_map_elem(&hashmap, check_hash_elem, &data, 0);
+	percpu_output = data.output;
+
+	return 0;
+}
+
+int hashmap_output = 0;
+int hashmap_elems = 0;
+int percpu_map_elems = 0;
+
+SEC("classifier/")
+int test_pkt_access(struct __sk_buff *skb)
+{
+	struct callback_ctx data;
+
+	data.ctx = skb;
+	data.input = 10;
+	data.output = 0;
+	hashmap_elems = bpf_for_each_map_elem(&hashmap, check_hash_elem, &data, 0);
+	hashmap_output = data.output;
+
+	percpu_map_elems = bpf_for_each_map_elem(&percpu_map, check_percpu_elem,
+						 (void *)0, 0);
+	return 0;
+}
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* [PATCH bpf-next v2 11/11] selftests/bpf: add arraymap test for bpf_for_each_map_elem() helper
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (9 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 10/11] selftests/bpf: add hashmap test for bpf_for_each_map_elem() helper Yonghong Song
@ 2021-02-17 18:18 ` Yonghong Song
  2021-02-17 18:29 ` [PATCH bpf-next v2 00/11] bpf: add " Yonghong Song
  11 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:18 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

A test is added for arraymap and percpu arraymap. The test also
exercises the early return for the helper which does not
traverse all elements.
    $ ./test_progs -n 44
    #44/1 hash_map:OK
    #44/2 array_map:OK
    #44 for_each:OK
    Summary: 1/2 PASSED, 0 SKIPPED, 0 FAILED

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 .../selftests/bpf/prog_tests/for_each.c       | 58 ++++++++++++++++++
 .../bpf/progs/for_each_array_map_elem.c       | 61 +++++++++++++++++++
 2 files changed, 119 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_array_map_elem.c

diff --git a/tools/testing/selftests/bpf/prog_tests/for_each.c b/tools/testing/selftests/bpf/prog_tests/for_each.c
index aa0c23e83ab8..157abc721cab 100644
--- a/tools/testing/selftests/bpf/prog_tests/for_each.c
+++ b/tools/testing/selftests/bpf/prog_tests/for_each.c
@@ -3,6 +3,7 @@
 #include <test_progs.h>
 #include <network_helpers.h>
 #include "for_each_hash_map_elem.skel.h"
+#include "for_each_array_map_elem.skel.h"
 
 static unsigned int duration;
 
@@ -67,8 +68,65 @@ static void test_hash_map(void)
 	for_each_hash_map_elem__destroy(skel);
 }
 
+static void test_array_map(void)
+{
+	__u32 key, num_cpus, max_entries, retval;
+	int i, arraymap_fd, percpu_map_fd, err;
+	struct for_each_array_map_elem *skel;
+	__u64 *percpu_valbuf = NULL;
+	__u64 val, expected_total;
+
+	skel = for_each_array_map_elem__open_and_load();
+	if (CHECK(!skel, "for_each_array_map_elem__open_and_load",
+		  "skeleton open_and_load failed\n"))
+		return;
+
+	arraymap_fd = bpf_map__fd(skel->maps.arraymap);
+	expected_total = 0;
+	max_entries = bpf_map__max_entries(skel->maps.arraymap);
+	for (i = 0; i < max_entries; i++) {
+		key = i;
+		val = i + 1;
+		/* skip the last iteration for expected total */
+		if (i != max_entries - 1)
+			expected_total += val;
+		err = bpf_map_update_elem(arraymap_fd, &key, &val, BPF_ANY);
+		if (CHECK(err, "map_update", "map_update failed\n"))
+			goto out;
+	}
+
+	num_cpus = bpf_num_possible_cpus();
+	percpu_map_fd = bpf_map__fd(skel->maps.percpu_map);
+	percpu_valbuf = malloc(sizeof(__u64) * num_cpus);
+	if (!ASSERT_OK_PTR(percpu_valbuf, "percpu_valbuf"))
+		goto out;
+
+	key = 0;
+	for (i = 0; i < num_cpus; i++)
+		percpu_valbuf[i] = i + 1;
+	err = bpf_map_update_elem(percpu_map_fd, &key, percpu_valbuf, BPF_ANY);
+	if (CHECK(err, "percpu_map_update", "map_update failed\n"))
+		goto out;
+
+	err = bpf_prog_test_run(bpf_program__fd(skel->progs.test_pkt_access),
+				1, &pkt_v4, sizeof(pkt_v4), NULL, NULL,
+				&retval, &duration);
+	if (CHECK(err || retval, "ipv4", "err %d errno %d retval %d\n",
+		  err, errno, retval))
+		goto out;
+
+	ASSERT_EQ(skel->bss->arraymap_output, expected_total, "array_output");
+	ASSERT_EQ(skel->bss->cpu + 1, skel->bss->percpu_val, "percpu_val");
+
+out:
+	free(percpu_valbuf);
+	for_each_array_map_elem__destroy(skel);
+}
+
 void test_for_each(void)
 {
 	if (test__start_subtest("hash_map"))
 		test_hash_map();
+	if (test__start_subtest("array_map"))
+		test_array_map();
 }
diff --git a/tools/testing/selftests/bpf/progs/for_each_array_map_elem.c b/tools/testing/selftests/bpf/progs/for_each_array_map_elem.c
new file mode 100644
index 000000000000..1488bc50468f
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/for_each_array_map_elem.c
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2021 Facebook */
+#include "vmlinux.h"
+#include <bpf/bpf_helpers.h>
+
+char _license[] SEC("license") = "GPL";
+
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 3);
+	__type(key, __u32);
+	__type(value, __u64);
+} arraymap SEC(".maps");
+
+struct {
+	__uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
+	__uint(max_entries, 1);
+	__type(key, __u32);
+	__type(value, __u64);
+} percpu_map SEC(".maps");
+
+struct callback_ctx {
+	int output;
+};
+
+static __u64
+check_array_elem(struct bpf_map *map, __u32 *key, __u64 *val,
+		 struct callback_ctx *data)
+{
+	data->output += *val;
+	if (*key == 1)
+		return 1; /* stop the iteration */
+	return 0;
+}
+
+__u32 cpu = 0;
+__u64 percpu_val = 0;
+
+static __u64
+check_percpu_elem(struct bpf_map *map, __u32 *key, __u64 *val,
+		  struct callback_ctx *data)
+{
+	cpu = bpf_get_smp_processor_id();
+	percpu_val = *val;
+	return 0;
+}
+
+u32 arraymap_output = 0;
+
+SEC("classifier/")
+int test_pkt_access(struct __sk_buff *skb)
+{
+	struct callback_ctx data;
+
+	data.output = 0;
+	bpf_for_each_map_elem(&arraymap, check_array_elem, &data, 0);
+	arraymap_output = data.output;
+
+	bpf_for_each_map_elem(&percpu_map, check_percpu_elem, (void *)0, 0);
+	return 0;
+}
-- 
2.24.1


^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper
  2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
                   ` (10 preceding siblings ...)
  2021-02-17 18:18 ` [PATCH bpf-next v2 11/11] selftests/bpf: add arraymap " Yonghong Song
@ 2021-02-17 18:29 ` Yonghong Song
  11 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-17 18:29 UTC (permalink / raw)
  To: bpf; +Cc: Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team



On 2/17/21 10:18 AM, Yonghong Song wrote:
> This patch set introduced bpf_for_each_map_elem() helper.
> The helper permits bpf program iterates through all elements
> for a particular map.
> 
> The work originally inspired by an internal discussion where
> firewall rules are kept in a map and bpf prog wants to
> check packet 5 tuples against all rules in the map.
> A bounded loop can be used but it has a few drawbacks.
> As the loop iteration goes up, verification time goes up too.
> For really large maps, verification may fail.
> A helper which abstracts out the loop itself will not have
> verification time issue.
> 
> A recent discussion in [1] involves to iterate all hash map
> elements in bpf program. Currently iterating all hashmap elements
> in bpf program is not easy if key space is really big.
> Having a helper to abstract out the loop itself is even more
> meaningful.
> 
> The proposed helper signature looks like:
>    long bpf_for_each_map_elem(map, callback_fn, callback_ctx, flags)
> where callback_fn is a static function and callback_ctx is
> a piece of data allocated on the caller stack which can be
> accessed by the callback_fn. The callback_fn signature might be
> different for different maps. For example, for hash/array maps,
> the signature is
>    long callback_fn(map, key, val, callback_ctx)
> 
> In the rest of series, Patches 1/2/3 did some refactoring. Patch 4
> implemented core kernel support for the helper. Patches 5 and 6
> added hashmap and arraymap support. Patches 7/8 added libbpf
> support. Patch 9 added bpftool support. Patches 10 and 11 added
> selftests for hashmap and arraymap.
> 
> [1]: https://lore.kernel.org/bpf/20210122205415.113822-1-xiyou.wangcong@gmail.com/

I missed changelog from v1 to v2 and here it is.

Changelogs:
   v1 -> v2:
     - setup callee frame in check_helper_call() and then proceed to verify
       helper return value as normal (Alexei)
     - use meta data to keep track of map/func pointer to avoid hard coding
       the register number (Alexei)
     - verify callback_fn return value range [0, 1]. (Alexei)
     - add migrate_{disable, enable} to ensure percpu value is the one
       bpf program expects to see. (Alexei)
     - change bpf_for_each_map_elem() return value to the number of iterated
       elements. (Andrii)
     - Change libbpf pseudo_func relo name to RELO_SUBPROG_ADDR and use
       more rigid checking for the relocation. (Andrii)
     - Better format to print out subprog address with bpftool. (Andrii)
     - Use bpf_prog_test_run to trigger bpf run, instead of bpf_iter. 
(Andrii)
     - Other misc changes.

> 
> Yonghong Song (11):
>    bpf: factor out visit_func_call_insn() in check_cfg()
>    bpf: factor out verbose_invalid_scalar()
>    bpf: refactor check_func_call() to allow callback function
>    bpf: add bpf_for_each_map_elem() helper
>    bpf: add hashtab support for bpf_for_each_map_elem() helper
>    bpf: add arraymap support for bpf_for_each_map_elem() helper
>    libbpf: move function is_ldimm64() earlier in libbpf.c
>    libbpf: support local function pointer relocation
>    bpftool: print local function pointer properly
>    selftests/bpf: add hashmap test for bpf_for_each_map_elem() helper
>    selftests/bpf: add arraymap test for bpf_for_each_map_elem() helper
> 
>   include/linux/bpf.h                           |  17 +
>   include/linux/bpf_verifier.h                  |   3 +
>   include/uapi/linux/bpf.h                      |  29 +-
>   kernel/bpf/arraymap.c                         |  39 ++
>   kernel/bpf/bpf_iter.c                         |  16 +
>   kernel/bpf/hashtab.c                          |  63 ++++
>   kernel/bpf/helpers.c                          |   2 +
>   kernel/bpf/verifier.c                         | 346 +++++++++++++++---
>   kernel/trace/bpf_trace.c                      |   2 +
>   tools/bpf/bpftool/xlated_dumper.c             |   3 +
>   tools/include/uapi/linux/bpf.h                |  29 +-
>   tools/lib/bpf/libbpf.c                        |  52 ++-
>   .../selftests/bpf/prog_tests/for_each.c       | 132 +++++++
>   .../bpf/progs/for_each_array_map_elem.c       |  61 +++
>   .../bpf/progs/for_each_hash_map_elem.c        |  95 +++++
>   15 files changed, 829 insertions(+), 60 deletions(-)
>   create mode 100644 tools/testing/selftests/bpf/prog_tests/for_each.c
>   create mode 100644 tools/testing/selftests/bpf/progs/for_each_array_map_elem.c
>   create mode 100644 tools/testing/selftests/bpf/progs/for_each_hash_map_elem.c
> 

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper
  2021-02-17 18:18 ` [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
@ 2021-02-22 20:59   ` Alexei Starovoitov
  2021-02-23 18:39     ` Yonghong Song
  0 siblings, 1 reply; 29+ messages in thread
From: Alexei Starovoitov @ 2021-02-22 20:59 UTC (permalink / raw)
  To: Yonghong Song
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

On Wed, Feb 17, 2021 at 10:18:07AM -0800, Yonghong Song wrote:
> @@ -5893,6 +6004,14 @@ static int retrieve_ptr_limit(const struct bpf_reg_state *ptr_reg,
>  		else
>  			*ptr_limit = -off;
>  		return 0;
> +	case PTR_TO_MAP_KEY:
> +		if (mask_to_left) {
> +			*ptr_limit = ptr_reg->umax_value + ptr_reg->off;
> +		} else {
> +			off = ptr_reg->smin_value + ptr_reg->off;
> +			*ptr_limit = ptr_reg->map_ptr->key_size - off;
> +		}
> +		return 0;

This part cannot be exercised because for_each will require cap_bpf.
Eventually we might relax this requirement and above code will be necessary.
Could you manually test it that it's working as expected by forcing
sanitize_ptr_alu() to act on it?

>  	case PTR_TO_MAP_VALUE:
>  		if (mask_to_left) {
>  			*ptr_limit = ptr_reg->umax_value + ptr_reg->off;
> @@ -6094,6 +6213,7 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
>  		verbose(env, "R%d pointer arithmetic on %s prohibited\n",
>  			dst, reg_type_str[ptr_reg->type]);
>  		return -EACCES;
> +	case PTR_TO_MAP_KEY:
>  	case PTR_TO_MAP_VALUE:
>  		if (!env->allow_ptr_leaks && !known && (smin_val < 0) != (smax_val < 0)) {
>  			verbose(env, "R%d has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root\n",
> @@ -8273,6 +8393,21 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
>  		return 0;
>  	}
>  
> +	if (insn->src_reg == BPF_PSEUDO_FUNC) {
> +		struct bpf_prog_aux *aux = env->prog->aux;
> +		u32 subprogno = insn[1].imm;
> +
> +		if (aux->func_info &&
> +		    aux->func_info_aux[subprogno].linkage != BTF_FUNC_STATIC) {

Could you change above to "!aux->func_info || aux..." ?
That will force for_each to be available only when funcs are annotated.
The subprogs without annotations were added only to be able to manually
craft asm test cases for subprogs in test_verifier.
The for_each selftests in patches 10 and 11 are strong enough.
The asm test would not add any value.
So I would like to avoid supporting something that has no real use.

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 05/11] bpf: add hashtab support for bpf_for_each_map_elem() helper
  2021-02-17 18:18 ` [PATCH bpf-next v2 05/11] bpf: add hashtab support for " Yonghong Song
@ 2021-02-22 22:56   ` Alexei Starovoitov
  2021-02-23 18:41     ` Yonghong Song
  0 siblings, 1 reply; 29+ messages in thread
From: Alexei Starovoitov @ 2021-02-22 22:56 UTC (permalink / raw)
  To: Yonghong Song
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

On Wed, Feb 17, 2021 at 10:18:08AM -0800, Yonghong Song wrote:
> +			ret = BPF_CAST_CALL(callback_fn)((u64)(long)map,
> +					(u64)(long)key, (u64)(long)val,
> +					(u64)(long)callback_ctx, 0);
> +			if (ret) {
> +				rcu_read_unlock();
> +				ret = (ret == 1) ? 0 : -EINVAL;
> +				goto out;

There is a tnum(0,1) check in patch 4.
I'm missing the purpose of this additional check.

> +			}
> +		}
> +		rcu_read_unlock();
> +	}
> +out:
> +	migrate_enable();
> +	return ret ?: num_calls;
> +}

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-17 18:18 ` [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation Yonghong Song
@ 2021-02-23  8:03   ` Andrii Nakryiko
  2021-02-23 18:55     ` Yonghong Song
  0 siblings, 1 reply; 29+ messages in thread
From: Andrii Nakryiko @ 2021-02-23  8:03 UTC (permalink / raw)
  To: Yonghong Song
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team

On Wed, Feb 17, 2021 at 12:56 PM Yonghong Song <yhs@fb.com> wrote:
>
> A new relocation RELO_SUBPROG_ADDR is added to capture
> local (static) function pointers loaded with ld_imm64
> insns. Such ld_imm64 insns are marked with
> BPF_PSEUDO_FUNC and will be passed to kernel so
> kernel can replace them with proper actual jited
> func addresses.
>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---
>  tools/lib/bpf/libbpf.c | 40 +++++++++++++++++++++++++++++++++++++---
>  1 file changed, 37 insertions(+), 3 deletions(-)
>
> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
> index 21a3eedf070d..772c7455f1a2 100644
> --- a/tools/lib/bpf/libbpf.c
> +++ b/tools/lib/bpf/libbpf.c
> @@ -188,6 +188,7 @@ enum reloc_type {
>         RELO_CALL,
>         RELO_DATA,
>         RELO_EXTERN,
> +       RELO_SUBPROG_ADDR,
>  };
>
>  struct reloc_desc {
> @@ -579,6 +580,11 @@ static bool is_ldimm64(struct bpf_insn *insn)
>         return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
>  }
>
> +static bool insn_is_pseudo_func(struct bpf_insn *insn)
> +{
> +       return is_ldimm64(insn) && insn->src_reg == BPF_PSEUDO_FUNC;
> +}
> +
>  static int
>  bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
>                       const char *name, size_t sec_idx, const char *sec_name,
> @@ -3406,6 +3412,16 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
>                 return -LIBBPF_ERRNO__RELOC;
>         }
>
> +       if (GELF_ST_BIND(sym->st_info) == STB_LOCAL &&
> +           GELF_ST_TYPE(sym->st_info) == STT_SECTION &&

STB_LOCAL + STT_SECTION is a section symbol. But STT_FUNC symbol could
be referenced as well, no? So this is too strict.

> +           (!shdr_idx || shdr_idx == obj->efile.text_shndx) &&

this doesn't look right, shdr_idx == 0 is a bad condition and should
be rejected, not accepted.

> +           !(sym->st_value % BPF_INSN_SZ)) {
> +               reloc_desc->type = RELO_SUBPROG_ADDR;
> +               reloc_desc->insn_idx = insn_idx;
> +               reloc_desc->sym_off = sym->st_value;
> +               return 0;
> +       }
> +

So see code right after sym_is_extern(sym) check. It checks for valid
shrd_idx, which is good and would be good to use that. After that we
can assume shdr_idx is valid and we can make a simple
obj->efile.text_shndx check then and use that as a signal that this is
SUBPROG_ADDR relocation (instead of deducing that from STT_SECTION).

And !(sym->st_value % BPF_INSN_SZ) should be reported as an error, not
silently skipped. Again, just how BPF_JMP | BPF_CALL does it. That way
it's more user-friendly, if something goes wrong. So it will look like
this:

if (shdr_idx == obj->efile.text_shndx) {
    /* check sym->st_value, pr_warn(), return error */

    reloc_desc->type = RELO_SUBPROG_ADDR;
    ...
    return 0;
}

>         if (sym_is_extern(sym)) {
>                 int sym_idx = GELF_R_SYM(rel->r_info);
>                 int i, n = obj->nr_extern;
> @@ -6172,6 +6188,10 @@ bpf_object__relocate_data(struct bpf_object *obj, struct bpf_program *prog)
>                         }
>                         relo->processed = true;
>                         break;
> +               case RELO_SUBPROG_ADDR:
> +                       insn[0].src_reg = BPF_PSEUDO_FUNC;

BTW, doesn't Clang emit instruction with BPF_PSEUDO_FUNC set properly
already? If not, why not?

> +                       /* will be handled as a follow up pass */
> +                       break;
>                 case RELO_CALL:
>                         /* will be handled as a follow up pass */
>                         break;
> @@ -6358,11 +6378,11 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
>
>         for (insn_idx = 0; insn_idx < prog->sec_insn_cnt; insn_idx++) {
>                 insn = &main_prog->insns[prog->sub_insn_off + insn_idx];
> -               if (!insn_is_subprog_call(insn))
> +               if (!insn_is_subprog_call(insn) && !insn_is_pseudo_func(insn))
>                         continue;
>
>                 relo = find_prog_insn_relo(prog, insn_idx);
> -               if (relo && relo->type != RELO_CALL) {
> +               if (relo && relo->type != RELO_CALL && relo->type != RELO_SUBPROG_ADDR) {
>                         pr_warn("prog '%s': unexpected relo for insn #%zu, type %d\n",
>                                 prog->name, insn_idx, relo->type);
>                         return -LIBBPF_ERRNO__RELOC;
> @@ -6374,8 +6394,22 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
>                          * call always has imm = -1, but for static functions
>                          * relocation is against STT_SECTION and insn->imm
>                          * points to a start of a static function
> +                        *
> +                        * for local func relocation, the imm field encodes
> +                        * the byte offset in the corresponding section.
> +                        */
> +                       if (relo->type == RELO_CALL)
> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
> +                       else
> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm / BPF_INSN_SZ + 1;
> +               } else if (insn_is_pseudo_func(insn)) {
> +                       /*
> +                        * RELO_SUBPROG_ADDR relo is always emitted even if both
> +                        * functions are in the same section, so it shouldn't reach here.
>                          */
> -                       sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
> +                       pr_warn("prog '%s': missing relo for insn #%zu, type %d\n",

nit: "missing subprog addr relo" to make it clearer?

> +                               prog->name, insn_idx, relo->type);
> +                       return -LIBBPF_ERRNO__RELOC;
>                 } else {
>                         /* if subprogram call is to a static function within
>                          * the same ELF section, there won't be any relocation
> --
> 2.24.1
>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 09/11] bpftool: print local function pointer properly
  2021-02-17 18:18 ` [PATCH bpf-next v2 09/11] bpftool: print local function pointer properly Yonghong Song
@ 2021-02-23  8:06   ` Andrii Nakryiko
  2021-02-23 19:00     ` Yonghong Song
  0 siblings, 1 reply; 29+ messages in thread
From: Andrii Nakryiko @ 2021-02-23  8:06 UTC (permalink / raw)
  To: Yonghong Song
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team

On Wed, Feb 17, 2021 at 12:56 PM Yonghong Song <yhs@fb.com> wrote:
>
> With later hashmap example, using bpftool xlated output may
> look like:
>   int dump_task(struct bpf_iter__task * ctx):
>   ; struct task_struct *task = ctx->task;
>      0: (79) r2 = *(u64 *)(r1 +8)
>   ; if (task == (void *)0 || called > 0)
>   ...
>     19: (18) r2 = subprog[+18]
>     30: (18) r2 = subprog[+26]
>   ...
>   36: (95) exit
>   __u64 check_hash_elem(struct bpf_map * map, __u32 * key, __u64 * val,
>                         struct callback_ctx * data):
>   ; struct bpf_iter__task *ctx = data->ctx;
>     37: (79) r5 = *(u64 *)(r4 +0)
>   ...
>     55: (95) exit
>   __u64 check_percpu_elem(struct bpf_map * map, __u32 * key,
>                           __u64 * val, void * unused):
>   ; check_percpu_elem(struct bpf_map *map, __u32 *key, __u64 *val, void *unused)
>     56: (bf) r6 = r3
>   ...
>     83: (18) r2 = subprog[-46]
>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---
>  tools/bpf/bpftool/xlated_dumper.c | 3 +++
>  1 file changed, 3 insertions(+)
>
> diff --git a/tools/bpf/bpftool/xlated_dumper.c b/tools/bpf/bpftool/xlated_dumper.c
> index 8608cd68cdd0..b87caae2e7da 100644
> --- a/tools/bpf/bpftool/xlated_dumper.c
> +++ b/tools/bpf/bpftool/xlated_dumper.c
> @@ -196,6 +196,9 @@ static const char *print_imm(void *private_data,
>         else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE)
>                 snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
>                          "map[id:%u][0]+%u", insn->imm, (insn + 1)->imm);
> +       else if (insn->src_reg == BPF_PSEUDO_FUNC)
> +               snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
> +                        "subprog[%+d]", insn->imm + 1);

print_call_pcrel() doesn't do +1 adjustment, why is it needed here?

>         else
>                 snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
>                          "0x%llx", (unsigned long long)full_imm);
> --
> 2.24.1
>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 07/11] libbpf: move function is_ldimm64() earlier in libbpf.c
  2021-02-17 18:18 ` [PATCH bpf-next v2 07/11] libbpf: move function is_ldimm64() earlier in libbpf.c Yonghong Song
@ 2021-02-23  8:06   ` Andrii Nakryiko
  0 siblings, 0 replies; 29+ messages in thread
From: Andrii Nakryiko @ 2021-02-23  8:06 UTC (permalink / raw)
  To: Yonghong Song
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team

On Wed, Feb 17, 2021 at 12:55 PM Yonghong Song <yhs@fb.com> wrote:
>
> Move function is_ldimm64() close to the beginning of libbpf.c,
> so it can be reused by later code and the next patch as well.
> There is no functionality change.
>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---

Thanks!

Acked-by: Andrii Nakryiko <andrii@kernel.org>

>  tools/lib/bpf/libbpf.c | 12 ++++++------
>  1 file changed, 6 insertions(+), 6 deletions(-)
>
> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
> index d43cc3f29dae..21a3eedf070d 100644
> --- a/tools/lib/bpf/libbpf.c
> +++ b/tools/lib/bpf/libbpf.c
> @@ -574,6 +574,11 @@ static bool insn_is_subprog_call(const struct bpf_insn *insn)
>                insn->off == 0;
>  }
>
> +static bool is_ldimm64(struct bpf_insn *insn)
> +{
> +       return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
> +}
> +
>  static int
>  bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
>                       const char *name, size_t sec_idx, const char *sec_name,
> @@ -3395,7 +3400,7 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
>                 return 0;
>         }
>
> -       if (insn->code != (BPF_LD | BPF_IMM | BPF_DW)) {
> +       if (!is_ldimm64(insn)) {
>                 pr_warn("prog '%s': invalid relo against '%s' for insns[%d].code 0x%x\n",
>                         prog->name, sym_name, insn_idx, insn->code);
>                 return -LIBBPF_ERRNO__RELOC;
> @@ -5566,11 +5571,6 @@ static void bpf_core_poison_insn(struct bpf_program *prog, int relo_idx,
>         insn->imm = 195896080; /* => 0xbad2310 => "bad relo" */
>  }
>
> -static bool is_ldimm64(struct bpf_insn *insn)
> -{
> -       return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
> -}
> -
>  static int insn_bpf_size_to_bytes(struct bpf_insn *insn)
>  {
>         switch (BPF_SIZE(insn->code)) {
> --
> 2.24.1
>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper
  2021-02-22 20:59   ` Alexei Starovoitov
@ 2021-02-23 18:39     ` Yonghong Song
  2021-02-23 18:46       ` Alexei Starovoitov
  0 siblings, 1 reply; 29+ messages in thread
From: Yonghong Song @ 2021-02-23 18:39 UTC (permalink / raw)
  To: Alexei Starovoitov
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team



On 2/22/21 12:59 PM, Alexei Starovoitov wrote:
> On Wed, Feb 17, 2021 at 10:18:07AM -0800, Yonghong Song wrote:
>> @@ -5893,6 +6004,14 @@ static int retrieve_ptr_limit(const struct bpf_reg_state *ptr_reg,
>>   		else
>>   			*ptr_limit = -off;
>>   		return 0;
>> +	case PTR_TO_MAP_KEY:
>> +		if (mask_to_left) {
>> +			*ptr_limit = ptr_reg->umax_value + ptr_reg->off;
>> +		} else {
>> +			off = ptr_reg->smin_value + ptr_reg->off;
>> +			*ptr_limit = ptr_reg->map_ptr->key_size - off;
>> +		}
>> +		return 0;
> 
> This part cannot be exercised because for_each will require cap_bpf.
> Eventually we might relax this requirement and above code will be necessary.
> Could you manually test it that it's working as expected by forcing
> sanitize_ptr_alu() to act on it?

I did some manual test and hacking the verifier to make this code 
executed and it looks fine and verifier succeeded.

But since this code won't execute with current implementation
with bpf_capable(). It probably makes sense to remove this code
for now and will add it back later once bpf_pseudo_func is permitted for
unprivileged user.

> 
>>   	case PTR_TO_MAP_VALUE:
>>   		if (mask_to_left) {
>>   			*ptr_limit = ptr_reg->umax_value + ptr_reg->off;
>> @@ -6094,6 +6213,7 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env,
>>   		verbose(env, "R%d pointer arithmetic on %s prohibited\n",
>>   			dst, reg_type_str[ptr_reg->type]);
>>   		return -EACCES;
>> +	case PTR_TO_MAP_KEY:
>>   	case PTR_TO_MAP_VALUE:
>>   		if (!env->allow_ptr_leaks && !known && (smin_val < 0) != (smax_val < 0)) {
>>   			verbose(env, "R%d has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root\n",
>> @@ -8273,6 +8393,21 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn)
>>   		return 0;
>>   	}
>>   
>> +	if (insn->src_reg == BPF_PSEUDO_FUNC) {
>> +		struct bpf_prog_aux *aux = env->prog->aux;
>> +		u32 subprogno = insn[1].imm;
>> +
>> +		if (aux->func_info &&
>> +		    aux->func_info_aux[subprogno].linkage != BTF_FUNC_STATIC) {
> 
> Could you change above to "!aux->func_info || aux..." ?
> That will force for_each to be available only when funcs are annotated.
> The subprogs without annotations were added only to be able to manually
> craft asm test cases for subprogs in test_verifier.
> The for_each selftests in patches 10 and 11 are strong enough.
> The asm test would not add any value.
> So I would like to avoid supporting something that has no real use.

Will do.

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 05/11] bpf: add hashtab support for bpf_for_each_map_elem() helper
  2021-02-22 22:56   ` Alexei Starovoitov
@ 2021-02-23 18:41     ` Yonghong Song
  0 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-23 18:41 UTC (permalink / raw)
  To: Alexei Starovoitov
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team



On 2/22/21 2:56 PM, Alexei Starovoitov wrote:
> On Wed, Feb 17, 2021 at 10:18:08AM -0800, Yonghong Song wrote:
>> +			ret = BPF_CAST_CALL(callback_fn)((u64)(long)map,
>> +					(u64)(long)key, (u64)(long)val,
>> +					(u64)(long)callback_ctx, 0);
>> +			if (ret) {
>> +				rcu_read_unlock();
>> +				ret = (ret == 1) ? 0 : -EINVAL;
>> +				goto out;
> 
> There is a tnum(0,1) check in patch 4.
> I'm missing the purpose of this additional check.

I missed this one after I added tnum(0, 1) checking. Will fix in the 
next revision.

> 
>> +			}
>> +		}
>> +		rcu_read_unlock();
>> +	}
>> +out:
>> +	migrate_enable();
>> +	return ret ?: num_calls;
>> +}

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper
  2021-02-23 18:39     ` Yonghong Song
@ 2021-02-23 18:46       ` Alexei Starovoitov
  2021-02-23 19:37         ` Yonghong Song
  0 siblings, 1 reply; 29+ messages in thread
From: Alexei Starovoitov @ 2021-02-23 18:46 UTC (permalink / raw)
  To: Yonghong Song, Alexei Starovoitov
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team

On 2/23/21 10:39 AM, Yonghong Song wrote:
> 
> 
> On 2/22/21 12:59 PM, Alexei Starovoitov wrote:
>> On Wed, Feb 17, 2021 at 10:18:07AM -0800, Yonghong Song wrote:
>>> @@ -5893,6 +6004,14 @@ static int retrieve_ptr_limit(const struct 
>>> bpf_reg_state *ptr_reg,
>>>           else
>>>               *ptr_limit = -off;
>>>           return 0;
>>> +    case PTR_TO_MAP_KEY:
>>> +        if (mask_to_left) {
>>> +            *ptr_limit = ptr_reg->umax_value + ptr_reg->off;
>>> +        } else {
>>> +            off = ptr_reg->smin_value + ptr_reg->off;
>>> +            *ptr_limit = ptr_reg->map_ptr->key_size - off;
>>> +        }
>>> +        return 0;
>>
>> This part cannot be exercised because for_each will require cap_bpf.
>> Eventually we might relax this requirement and above code will be 
>> necessary.
>> Could you manually test it that it's working as expected by forcing
>> sanitize_ptr_alu() to act on it?
> 
> I did some manual test and hacking the verifier to make this code 
> executed and it looks fine and verifier succeeded.
> 
> But since this code won't execute with current implementation
> with bpf_capable(). It probably makes sense to remove this code
> for now and will add it back later once bpf_pseudo_func is permitted for
> unprivileged user.

I think we might forget it later.
I would leave the code here and maybe add the comment that it's tested
for future use, but not needed yet.

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-23  8:03   ` Andrii Nakryiko
@ 2021-02-23 18:55     ` Yonghong Song
  2021-02-23 19:07       ` Alexei Starovoitov
  2021-02-23 19:19       ` Andrii Nakryiko
  0 siblings, 2 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-23 18:55 UTC (permalink / raw)
  To: Andrii Nakryiko
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team



On 2/23/21 12:03 AM, Andrii Nakryiko wrote:
> On Wed, Feb 17, 2021 at 12:56 PM Yonghong Song <yhs@fb.com> wrote:
>>
>> A new relocation RELO_SUBPROG_ADDR is added to capture
>> local (static) function pointers loaded with ld_imm64
>> insns. Such ld_imm64 insns are marked with
>> BPF_PSEUDO_FUNC and will be passed to kernel so
>> kernel can replace them with proper actual jited
>> func addresses.
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>>   tools/lib/bpf/libbpf.c | 40 +++++++++++++++++++++++++++++++++++++---
>>   1 file changed, 37 insertions(+), 3 deletions(-)
>>
>> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
>> index 21a3eedf070d..772c7455f1a2 100644
>> --- a/tools/lib/bpf/libbpf.c
>> +++ b/tools/lib/bpf/libbpf.c
>> @@ -188,6 +188,7 @@ enum reloc_type {
>>          RELO_CALL,
>>          RELO_DATA,
>>          RELO_EXTERN,
>> +       RELO_SUBPROG_ADDR,
>>   };
>>
>>   struct reloc_desc {
>> @@ -579,6 +580,11 @@ static bool is_ldimm64(struct bpf_insn *insn)
>>          return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
>>   }
>>
>> +static bool insn_is_pseudo_func(struct bpf_insn *insn)
>> +{
>> +       return is_ldimm64(insn) && insn->src_reg == BPF_PSEUDO_FUNC;
>> +}
>> +
>>   static int
>>   bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
>>                        const char *name, size_t sec_idx, const char *sec_name,
>> @@ -3406,6 +3412,16 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
>>                  return -LIBBPF_ERRNO__RELOC;
>>          }
>>
>> +       if (GELF_ST_BIND(sym->st_info) == STB_LOCAL &&
>> +           GELF_ST_TYPE(sym->st_info) == STT_SECTION &&
> 
> STB_LOCAL + STT_SECTION is a section symbol. But STT_FUNC symbol could
> be referenced as well, no? So this is too strict.

Yes, STT_FUNC symbol could be referenced but we do not have use
case yet. If we encode STT_FUNC (global), the kernel will reject
it. We can extend libbpf to support STT_FUNC once we got a use
case.

> 
>> +           (!shdr_idx || shdr_idx == obj->efile.text_shndx) &&
> 
> this doesn't look right, shdr_idx == 0 is a bad condition and should
> be rejected, not accepted.

it is my fault. Will fix in the next revision.

> 
>> +           !(sym->st_value % BPF_INSN_SZ)) {
>> +               reloc_desc->type = RELO_SUBPROG_ADDR;
>> +               reloc_desc->insn_idx = insn_idx;
>> +               reloc_desc->sym_off = sym->st_value;
>> +               return 0;
>> +       }
>> +
> 
> So see code right after sym_is_extern(sym) check. It checks for valid
> shrd_idx, which is good and would be good to use that. After that we
> can assume shdr_idx is valid and we can make a simple
> obj->efile.text_shndx check then and use that as a signal that this is
> SUBPROG_ADDR relocation (instead of deducing that from STT_SECTION).
> 
> And !(sym->st_value % BPF_INSN_SZ) should be reported as an error, not
> silently skipped. Again, just how BPF_JMP | BPF_CALL does it. That way
> it's more user-friendly, if something goes wrong. So it will look like
> this:
> 
> if (shdr_idx == obj->efile.text_shndx) {
>      /* check sym->st_value, pr_warn(), return error */
> 
>      reloc_desc->type = RELO_SUBPROG_ADDR;
>      ...
>      return 0;
> }

Okay. Will do similar checking to insn->code == (BPF_JMP | BPF_CALL)
in the next revision.

> 
>>          if (sym_is_extern(sym)) {
>>                  int sym_idx = GELF_R_SYM(rel->r_info);
>>                  int i, n = obj->nr_extern;
>> @@ -6172,6 +6188,10 @@ bpf_object__relocate_data(struct bpf_object *obj, struct bpf_program *prog)
>>                          }
>>                          relo->processed = true;
>>                          break;
>> +               case RELO_SUBPROG_ADDR:
>> +                       insn[0].src_reg = BPF_PSEUDO_FUNC;
> 
> BTW, doesn't Clang emit instruction with BPF_PSEUDO_FUNC set properly
> already? If not, why not?

This is really a contract between libbpf and kernel, similar to
BPF_PSEUDO_MAP_FD/BPF_PSEUDO_MAP_VALUE/BPF_PSEUDO_BTF_ID.
Adding encoding in clang is not needed as this is simply a load
of function address as far as clang concerned.

> 
>> +                       /* will be handled as a follow up pass */
>> +                       break;
>>                  case RELO_CALL:
>>                          /* will be handled as a follow up pass */
>>                          break;
>> @@ -6358,11 +6378,11 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
>>
>>          for (insn_idx = 0; insn_idx < prog->sec_insn_cnt; insn_idx++) {
>>                  insn = &main_prog->insns[prog->sub_insn_off + insn_idx];
>> -               if (!insn_is_subprog_call(insn))
>> +               if (!insn_is_subprog_call(insn) && !insn_is_pseudo_func(insn))
>>                          continue;
>>
>>                  relo = find_prog_insn_relo(prog, insn_idx);
>> -               if (relo && relo->type != RELO_CALL) {
>> +               if (relo && relo->type != RELO_CALL && relo->type != RELO_SUBPROG_ADDR) {
>>                          pr_warn("prog '%s': unexpected relo for insn #%zu, type %d\n",
>>                                  prog->name, insn_idx, relo->type);
>>                          return -LIBBPF_ERRNO__RELOC;
>> @@ -6374,8 +6394,22 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
>>                           * call always has imm = -1, but for static functions
>>                           * relocation is against STT_SECTION and insn->imm
>>                           * points to a start of a static function
>> +                        *
>> +                        * for local func relocation, the imm field encodes
>> +                        * the byte offset in the corresponding section.
>> +                        */
>> +                       if (relo->type == RELO_CALL)
>> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
>> +                       else
>> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm / BPF_INSN_SZ + 1;
>> +               } else if (insn_is_pseudo_func(insn)) {
>> +                       /*
>> +                        * RELO_SUBPROG_ADDR relo is always emitted even if both
>> +                        * functions are in the same section, so it shouldn't reach here.
>>                           */
>> -                       sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
>> +                       pr_warn("prog '%s': missing relo for insn #%zu, type %d\n",
> 
> nit: "missing subprog addr relo" to make it clearer?

sure. will do.

> 
>> +                               prog->name, insn_idx, relo->type);
>> +                       return -LIBBPF_ERRNO__RELOC;
>>                  } else {
>>                          /* if subprogram call is to a static function within
>>                           * the same ELF section, there won't be any relocation
>> --
>> 2.24.1
>>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 09/11] bpftool: print local function pointer properly
  2021-02-23  8:06   ` Andrii Nakryiko
@ 2021-02-23 19:00     ` Yonghong Song
  0 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-23 19:00 UTC (permalink / raw)
  To: Andrii Nakryiko
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team



On 2/23/21 12:06 AM, Andrii Nakryiko wrote:
> On Wed, Feb 17, 2021 at 12:56 PM Yonghong Song <yhs@fb.com> wrote:
>>
>> With later hashmap example, using bpftool xlated output may
>> look like:
>>    int dump_task(struct bpf_iter__task * ctx):
>>    ; struct task_struct *task = ctx->task;
>>       0: (79) r2 = *(u64 *)(r1 +8)
>>    ; if (task == (void *)0 || called > 0)
>>    ...
>>      19: (18) r2 = subprog[+18]
>>      30: (18) r2 = subprog[+26]
>>    ...
>>    36: (95) exit
>>    __u64 check_hash_elem(struct bpf_map * map, __u32 * key, __u64 * val,
>>                          struct callback_ctx * data):
>>    ; struct bpf_iter__task *ctx = data->ctx;
>>      37: (79) r5 = *(u64 *)(r4 +0)
>>    ...
>>      55: (95) exit
>>    __u64 check_percpu_elem(struct bpf_map * map, __u32 * key,
>>                            __u64 * val, void * unused):
>>    ; check_percpu_elem(struct bpf_map *map, __u32 *key, __u64 *val, void *unused)
>>      56: (bf) r6 = r3
>>    ...
>>      83: (18) r2 = subprog[-46]
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>>   tools/bpf/bpftool/xlated_dumper.c | 3 +++
>>   1 file changed, 3 insertions(+)
>>
>> diff --git a/tools/bpf/bpftool/xlated_dumper.c b/tools/bpf/bpftool/xlated_dumper.c
>> index 8608cd68cdd0..b87caae2e7da 100644
>> --- a/tools/bpf/bpftool/xlated_dumper.c
>> +++ b/tools/bpf/bpftool/xlated_dumper.c
>> @@ -196,6 +196,9 @@ static const char *print_imm(void *private_data,
>>          else if (insn->src_reg == BPF_PSEUDO_MAP_VALUE)
>>                  snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
>>                           "map[id:%u][0]+%u", insn->imm, (insn + 1)->imm);
>> +       else if (insn->src_reg == BPF_PSEUDO_FUNC)
>> +               snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
>> +                        "subprog[%+d]", insn->imm + 1);
> 
> print_call_pcrel() doesn't do +1 adjustment, why is it needed here?

original intention is to have imm + 1, so user will directly get to the 
target insn. But yes, it makes sense to be consistent here. bpf 
programmer may already know to add 1 implicitly to the current insn
index for the target. Will fix in the next version.

> 
>>          else
>>                  snprintf(dd->scratch_buff, sizeof(dd->scratch_buff),
>>                           "0x%llx", (unsigned long long)full_imm);
>> --
>> 2.24.1
>>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-23 18:55     ` Yonghong Song
@ 2021-02-23 19:07       ` Alexei Starovoitov
  2021-02-23 19:21         ` Andrii Nakryiko
  2021-02-23 19:19       ` Andrii Nakryiko
  1 sibling, 1 reply; 29+ messages in thread
From: Alexei Starovoitov @ 2021-02-23 19:07 UTC (permalink / raw)
  To: Yonghong Song, Andrii Nakryiko
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team

On 2/23/21 10:55 AM, Yonghong Song wrote:
>> BTW, doesn't Clang emit instruction with BPF_PSEUDO_FUNC set properly
>> already? If not, why not?
> 
> This is really a contract between libbpf and kernel, similar to
> BPF_PSEUDO_MAP_FD/BPF_PSEUDO_MAP_VALUE/BPF_PSEUDO_BTF_ID.
> Adding encoding in clang is not needed as this is simply a load
> of function address as far as clang concerned.

Andrii, I had the same thought when I first looked at it.
The llvm can be taught to do this, but it would be a change in behavior.
Older llvms will generate relo while new one will not.
To ease adoption libbpf would probably need to support both.
Hence no real need to tweak llvm.
If we go with llvm only approach my ongoing work on naked functions
would require to tweak llvm and libbpf again.
While the llvm does the same relo for naked funcs already.
So I will reuse this libbpf support as-is.
Only for &&label and jmptables the extra llvm work will be needed.

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-23 18:55     ` Yonghong Song
  2021-02-23 19:07       ` Alexei Starovoitov
@ 2021-02-23 19:19       ` Andrii Nakryiko
  2021-02-23 19:47         ` Yonghong Song
  1 sibling, 1 reply; 29+ messages in thread
From: Andrii Nakryiko @ 2021-02-23 19:19 UTC (permalink / raw)
  To: Yonghong Song
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team

On Tue, Feb 23, 2021 at 10:56 AM Yonghong Song <yhs@fb.com> wrote:
>
>
>
> On 2/23/21 12:03 AM, Andrii Nakryiko wrote:
> > On Wed, Feb 17, 2021 at 12:56 PM Yonghong Song <yhs@fb.com> wrote:
> >>
> >> A new relocation RELO_SUBPROG_ADDR is added to capture
> >> local (static) function pointers loaded with ld_imm64
> >> insns. Such ld_imm64 insns are marked with
> >> BPF_PSEUDO_FUNC and will be passed to kernel so
> >> kernel can replace them with proper actual jited
> >> func addresses.
> >>
> >> Signed-off-by: Yonghong Song <yhs@fb.com>
> >> ---
> >>   tools/lib/bpf/libbpf.c | 40 +++++++++++++++++++++++++++++++++++++---
> >>   1 file changed, 37 insertions(+), 3 deletions(-)
> >>
> >> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
> >> index 21a3eedf070d..772c7455f1a2 100644
> >> --- a/tools/lib/bpf/libbpf.c
> >> +++ b/tools/lib/bpf/libbpf.c
> >> @@ -188,6 +188,7 @@ enum reloc_type {
> >>          RELO_CALL,
> >>          RELO_DATA,
> >>          RELO_EXTERN,
> >> +       RELO_SUBPROG_ADDR,
> >>   };
> >>
> >>   struct reloc_desc {
> >> @@ -579,6 +580,11 @@ static bool is_ldimm64(struct bpf_insn *insn)
> >>          return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
> >>   }
> >>
> >> +static bool insn_is_pseudo_func(struct bpf_insn *insn)
> >> +{
> >> +       return is_ldimm64(insn) && insn->src_reg == BPF_PSEUDO_FUNC;
> >> +}
> >> +
> >>   static int
> >>   bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
> >>                        const char *name, size_t sec_idx, const char *sec_name,
> >> @@ -3406,6 +3412,16 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
> >>                  return -LIBBPF_ERRNO__RELOC;
> >>          }
> >>
> >> +       if (GELF_ST_BIND(sym->st_info) == STB_LOCAL &&
> >> +           GELF_ST_TYPE(sym->st_info) == STT_SECTION &&
> >
> > STB_LOCAL + STT_SECTION is a section symbol. But STT_FUNC symbol could
> > be referenced as well, no? So this is too strict.
>
> Yes, STT_FUNC symbol could be referenced but we do not have use
> case yet. If we encode STT_FUNC (global), the kernel will reject
> it. We can extend libbpf to support STT_FUNC once we got a use
> case.

I don't really like tailoring libbpf generic SUBPROG_ADDR relocation
to one current specific use case, though. Taking the address of
SUBPROG_ADDR is not, conceptually, tied with passing it to for_each as
a callback. E.g., what if you just want to compare two registers
pointing to subprogs, without actually passing them to for_each(). I
don't know if it's possible right now, but I don't see why that
shouldn't be supported. In the latter case, adding arbitrary
restrictions about static vs global functions doesn't make much sense.

So let's teach libbpf the right logic without assuming any specific
use case. It pays off in the long run.

>
> >
> >> +           (!shdr_idx || shdr_idx == obj->efile.text_shndx) &&
> >
> > this doesn't look right, shdr_idx == 0 is a bad condition and should
> > be rejected, not accepted.
>
> it is my fault. Will fix in the next revision.
>
> >
> >> +           !(sym->st_value % BPF_INSN_SZ)) {
> >> +               reloc_desc->type = RELO_SUBPROG_ADDR;
> >> +               reloc_desc->insn_idx = insn_idx;
> >> +               reloc_desc->sym_off = sym->st_value;
> >> +               return 0;
> >> +       }
> >> +
> >
> > So see code right after sym_is_extern(sym) check. It checks for valid
> > shrd_idx, which is good and would be good to use that. After that we
> > can assume shdr_idx is valid and we can make a simple
> > obj->efile.text_shndx check then and use that as a signal that this is
> > SUBPROG_ADDR relocation (instead of deducing that from STT_SECTION).
> >
> > And !(sym->st_value % BPF_INSN_SZ) should be reported as an error, not
> > silently skipped. Again, just how BPF_JMP | BPF_CALL does it. That way
> > it's more user-friendly, if something goes wrong. So it will look like
> > this:
> >
> > if (shdr_idx == obj->efile.text_shndx) {
> >      /* check sym->st_value, pr_warn(), return error */
> >
> >      reloc_desc->type = RELO_SUBPROG_ADDR;
> >      ...
> >      return 0;
> > }
>
> Okay. Will do similar checking to insn->code == (BPF_JMP | BPF_CALL)
> in the next revision.
>
> >
> >>          if (sym_is_extern(sym)) {
> >>                  int sym_idx = GELF_R_SYM(rel->r_info);
> >>                  int i, n = obj->nr_extern;
> >> @@ -6172,6 +6188,10 @@ bpf_object__relocate_data(struct bpf_object *obj, struct bpf_program *prog)
> >>                          }
> >>                          relo->processed = true;
> >>                          break;
> >> +               case RELO_SUBPROG_ADDR:
> >> +                       insn[0].src_reg = BPF_PSEUDO_FUNC;
> >
> > BTW, doesn't Clang emit instruction with BPF_PSEUDO_FUNC set properly
> > already? If not, why not?
>
> This is really a contract between libbpf and kernel, similar to
> BPF_PSEUDO_MAP_FD/BPF_PSEUDO_MAP_VALUE/BPF_PSEUDO_BTF_ID.
> Adding encoding in clang is not needed as this is simply a load
> of function address as far as clang concerned.

Yeah, not a big deal, I was under the impression we do that for other
BPF_PSEUDO cases, but checking other parts of libbpf, doesn't seem
like that's the case.

>
> >
> >> +                       /* will be handled as a follow up pass */
> >> +                       break;
> >>                  case RELO_CALL:
> >>                          /* will be handled as a follow up pass */
> >>                          break;
> >> @@ -6358,11 +6378,11 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
> >>
> >>          for (insn_idx = 0; insn_idx < prog->sec_insn_cnt; insn_idx++) {
> >>                  insn = &main_prog->insns[prog->sub_insn_off + insn_idx];
> >> -               if (!insn_is_subprog_call(insn))
> >> +               if (!insn_is_subprog_call(insn) && !insn_is_pseudo_func(insn))
> >>                          continue;
> >>
> >>                  relo = find_prog_insn_relo(prog, insn_idx);
> >> -               if (relo && relo->type != RELO_CALL) {
> >> +               if (relo && relo->type != RELO_CALL && relo->type != RELO_SUBPROG_ADDR) {
> >>                          pr_warn("prog '%s': unexpected relo for insn #%zu, type %d\n",
> >>                                  prog->name, insn_idx, relo->type);
> >>                          return -LIBBPF_ERRNO__RELOC;
> >> @@ -6374,8 +6394,22 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
> >>                           * call always has imm = -1, but for static functions
> >>                           * relocation is against STT_SECTION and insn->imm
> >>                           * points to a start of a static function
> >> +                        *
> >> +                        * for local func relocation, the imm field encodes
> >> +                        * the byte offset in the corresponding section.
> >> +                        */
> >> +                       if (relo->type == RELO_CALL)
> >> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
> >> +                       else
> >> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm / BPF_INSN_SZ + 1;
> >> +               } else if (insn_is_pseudo_func(insn)) {
> >> +                       /*
> >> +                        * RELO_SUBPROG_ADDR relo is always emitted even if both
> >> +                        * functions are in the same section, so it shouldn't reach here.
> >>                           */
> >> -                       sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
> >> +                       pr_warn("prog '%s': missing relo for insn #%zu, type %d\n",
> >
> > nit: "missing subprog addr relo" to make it clearer?
>
> sure. will do.

given the "generic support" comment above, I think we should still
support this case as well. WDYT?

>
> >
> >> +                               prog->name, insn_idx, relo->type);
> >> +                       return -LIBBPF_ERRNO__RELOC;
> >>                  } else {
> >>                          /* if subprogram call is to a static function within
> >>                           * the same ELF section, there won't be any relocation
> >> --
> >> 2.24.1
> >>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-23 19:07       ` Alexei Starovoitov
@ 2021-02-23 19:21         ` Andrii Nakryiko
  0 siblings, 0 replies; 29+ messages in thread
From: Andrii Nakryiko @ 2021-02-23 19:21 UTC (permalink / raw)
  To: Alexei Starovoitov
  Cc: Yonghong Song, bpf, Alexei Starovoitov, Cong Wang,
	Daniel Borkmann, Kernel Team

On Tue, Feb 23, 2021 at 11:08 AM Alexei Starovoitov <ast@fb.com> wrote:
>
> On 2/23/21 10:55 AM, Yonghong Song wrote:
> >> BTW, doesn't Clang emit instruction with BPF_PSEUDO_FUNC set properly
> >> already? If not, why not?
> >
> > This is really a contract between libbpf and kernel, similar to
> > BPF_PSEUDO_MAP_FD/BPF_PSEUDO_MAP_VALUE/BPF_PSEUDO_BTF_ID.
> > Adding encoding in clang is not needed as this is simply a load
> > of function address as far as clang concerned.
>
> Andrii, I had the same thought when I first looked at it.
> The llvm can be taught to do this, but it would be a change in behavior.
> Older llvms will generate relo while new one will not.
> To ease adoption libbpf would probably need to support both.
> Hence no real need to tweak llvm.
> If we go with llvm only approach my ongoing work on naked functions
> would require to tweak llvm and libbpf again.
> While the llvm does the same relo for naked funcs already.
> So I will reuse this libbpf support as-is.
> Only for &&label and jmptables the extra llvm work will be needed.

Yeah, that's fine. I wasn't complaining :) It would be safer if LLVM
emitted the intent, but it's fine, libbpf seems to be doing fine
inferring it. I was also under the impression we do get BPF_PSEUDO_xxx
for other types of relos (for whatever reason), which is not really
the case.

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper
  2021-02-23 18:46       ` Alexei Starovoitov
@ 2021-02-23 19:37         ` Yonghong Song
  0 siblings, 0 replies; 29+ messages in thread
From: Yonghong Song @ 2021-02-23 19:37 UTC (permalink / raw)
  To: Alexei Starovoitov, Alexei Starovoitov
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, kernel-team



On 2/23/21 10:46 AM, Alexei Starovoitov wrote:
> On 2/23/21 10:39 AM, Yonghong Song wrote:
>>
>>
>> On 2/22/21 12:59 PM, Alexei Starovoitov wrote:
>>> On Wed, Feb 17, 2021 at 10:18:07AM -0800, Yonghong Song wrote:
>>>> @@ -5893,6 +6004,14 @@ static int retrieve_ptr_limit(const struct 
>>>> bpf_reg_state *ptr_reg,
>>>>           else
>>>>               *ptr_limit = -off;
>>>>           return 0;
>>>> +    case PTR_TO_MAP_KEY:
>>>> +        if (mask_to_left) {
>>>> +            *ptr_limit = ptr_reg->umax_value + ptr_reg->off;
>>>> +        } else {
>>>> +            off = ptr_reg->smin_value + ptr_reg->off;
>>>> +            *ptr_limit = ptr_reg->map_ptr->key_size - off;
>>>> +        }
>>>> +        return 0;
>>>
>>> This part cannot be exercised because for_each will require cap_bpf.
>>> Eventually we might relax this requirement and above code will be 
>>> necessary.
>>> Could you manually test it that it's working as expected by forcing
>>> sanitize_ptr_alu() to act on it?
>>
>> I did some manual test and hacking the verifier to make this code 
>> executed and it looks fine and verifier succeeded.
>>
>> But since this code won't execute with current implementation
>> with bpf_capable(). It probably makes sense to remove this code
>> for now and will add it back later once bpf_pseudo_func is permitted for
>> unprivileged user.
> 
> I think we might forget it later.
> I would leave the code here and maybe add the comment that it's tested
> for future use, but not needed yet.

okay. will keep it.


^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-23 19:19       ` Andrii Nakryiko
@ 2021-02-23 19:47         ` Yonghong Song
  2021-02-23 21:24           ` Andrii Nakryiko
  0 siblings, 1 reply; 29+ messages in thread
From: Yonghong Song @ 2021-02-23 19:47 UTC (permalink / raw)
  To: Andrii Nakryiko
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team



On 2/23/21 11:19 AM, Andrii Nakryiko wrote:
> On Tue, Feb 23, 2021 at 10:56 AM Yonghong Song <yhs@fb.com> wrote:
>>
>>
>>
>> On 2/23/21 12:03 AM, Andrii Nakryiko wrote:
>>> On Wed, Feb 17, 2021 at 12:56 PM Yonghong Song <yhs@fb.com> wrote:
>>>>
>>>> A new relocation RELO_SUBPROG_ADDR is added to capture
>>>> local (static) function pointers loaded with ld_imm64
>>>> insns. Such ld_imm64 insns are marked with
>>>> BPF_PSEUDO_FUNC and will be passed to kernel so
>>>> kernel can replace them with proper actual jited
>>>> func addresses.
>>>>
>>>> Signed-off-by: Yonghong Song <yhs@fb.com>
>>>> ---
>>>>    tools/lib/bpf/libbpf.c | 40 +++++++++++++++++++++++++++++++++++++---
>>>>    1 file changed, 37 insertions(+), 3 deletions(-)
>>>>
>>>> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
>>>> index 21a3eedf070d..772c7455f1a2 100644
>>>> --- a/tools/lib/bpf/libbpf.c
>>>> +++ b/tools/lib/bpf/libbpf.c
>>>> @@ -188,6 +188,7 @@ enum reloc_type {
>>>>           RELO_CALL,
>>>>           RELO_DATA,
>>>>           RELO_EXTERN,
>>>> +       RELO_SUBPROG_ADDR,
>>>>    };
>>>>
>>>>    struct reloc_desc {
>>>> @@ -579,6 +580,11 @@ static bool is_ldimm64(struct bpf_insn *insn)
>>>>           return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
>>>>    }
>>>>
>>>> +static bool insn_is_pseudo_func(struct bpf_insn *insn)
>>>> +{
>>>> +       return is_ldimm64(insn) && insn->src_reg == BPF_PSEUDO_FUNC;
>>>> +}
>>>> +
>>>>    static int
>>>>    bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
>>>>                         const char *name, size_t sec_idx, const char *sec_name,
>>>> @@ -3406,6 +3412,16 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
>>>>                   return -LIBBPF_ERRNO__RELOC;
>>>>           }
>>>>
>>>> +       if (GELF_ST_BIND(sym->st_info) == STB_LOCAL &&
>>>> +           GELF_ST_TYPE(sym->st_info) == STT_SECTION &&
>>>
>>> STB_LOCAL + STT_SECTION is a section symbol. But STT_FUNC symbol could
>>> be referenced as well, no? So this is too strict.
>>
>> Yes, STT_FUNC symbol could be referenced but we do not have use
>> case yet. If we encode STT_FUNC (global), the kernel will reject
>> it. We can extend libbpf to support STT_FUNC once we got a use
>> case.
> 
> I don't really like tailoring libbpf generic SUBPROG_ADDR relocation
> to one current specific use case, though. Taking the address of
> SUBPROG_ADDR is not, conceptually, tied with passing it to for_each as
> a callback. E.g., what if you just want to compare two registers
> pointing to subprogs, without actually passing them to for_each(). I
> don't know if it's possible right now, but I don't see why that
> shouldn't be supported. In the latter case, adding arbitrary
> restrictions about static vs global functions doesn't make much sense.
> 
> So let's teach libbpf the right logic without assuming any specific
> use case. It pays off in the long run.

Okay, Will support global function as well. It won't hurt.

> 
>>
>>>
>>>> +           (!shdr_idx || shdr_idx == obj->efile.text_shndx) &&
>>>
>>> this doesn't look right, shdr_idx == 0 is a bad condition and should
>>> be rejected, not accepted.
>>
>> it is my fault. Will fix in the next revision.
>>
>>>
>>>> +           !(sym->st_value % BPF_INSN_SZ)) {
>>>> +               reloc_desc->type = RELO_SUBPROG_ADDR;
>>>> +               reloc_desc->insn_idx = insn_idx;
>>>> +               reloc_desc->sym_off = sym->st_value;
>>>> +               return 0;
>>>> +       }
>>>> +
>>>
>>> So see code right after sym_is_extern(sym) check. It checks for valid
>>> shrd_idx, which is good and would be good to use that. After that we
>>> can assume shdr_idx is valid and we can make a simple
>>> obj->efile.text_shndx check then and use that as a signal that this is
>>> SUBPROG_ADDR relocation (instead of deducing that from STT_SECTION).
>>>
>>> And !(sym->st_value % BPF_INSN_SZ) should be reported as an error, not
>>> silently skipped. Again, just how BPF_JMP | BPF_CALL does it. That way
>>> it's more user-friendly, if something goes wrong. So it will look like
>>> this:
>>>
>>> if (shdr_idx == obj->efile.text_shndx) {
>>>       /* check sym->st_value, pr_warn(), return error */
>>>
>>>       reloc_desc->type = RELO_SUBPROG_ADDR;
>>>       ...
>>>       return 0;
>>> }
>>
>> Okay. Will do similar checking to insn->code == (BPF_JMP | BPF_CALL)
>> in the next revision.
>>
>>>
>>>>           if (sym_is_extern(sym)) {
>>>>                   int sym_idx = GELF_R_SYM(rel->r_info);
>>>>                   int i, n = obj->nr_extern;
>>>> @@ -6172,6 +6188,10 @@ bpf_object__relocate_data(struct bpf_object *obj, struct bpf_program *prog)
>>>>                           }
>>>>                           relo->processed = true;
>>>>                           break;
>>>> +               case RELO_SUBPROG_ADDR:
>>>> +                       insn[0].src_reg = BPF_PSEUDO_FUNC;
>>>
>>> BTW, doesn't Clang emit instruction with BPF_PSEUDO_FUNC set properly
>>> already? If not, why not?
>>
>> This is really a contract between libbpf and kernel, similar to
>> BPF_PSEUDO_MAP_FD/BPF_PSEUDO_MAP_VALUE/BPF_PSEUDO_BTF_ID.
>> Adding encoding in clang is not needed as this is simply a load
>> of function address as far as clang concerned.
> 
> Yeah, not a big deal, I was under the impression we do that for other
> BPF_PSEUDO cases, but checking other parts of libbpf, doesn't seem
> like that's the case.
> 
>>
>>>
>>>> +                       /* will be handled as a follow up pass */
>>>> +                       break;
>>>>                   case RELO_CALL:
>>>>                           /* will be handled as a follow up pass */
>>>>                           break;
>>>> @@ -6358,11 +6378,11 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
>>>>
>>>>           for (insn_idx = 0; insn_idx < prog->sec_insn_cnt; insn_idx++) {
>>>>                   insn = &main_prog->insns[prog->sub_insn_off + insn_idx];
>>>> -               if (!insn_is_subprog_call(insn))
>>>> +               if (!insn_is_subprog_call(insn) && !insn_is_pseudo_func(insn))
>>>>                           continue;
>>>>
>>>>                   relo = find_prog_insn_relo(prog, insn_idx);
>>>> -               if (relo && relo->type != RELO_CALL) {
>>>> +               if (relo && relo->type != RELO_CALL && relo->type != RELO_SUBPROG_ADDR) {
>>>>                           pr_warn("prog '%s': unexpected relo for insn #%zu, type %d\n",
>>>>                                   prog->name, insn_idx, relo->type);
>>>>                           return -LIBBPF_ERRNO__RELOC;
>>>> @@ -6374,8 +6394,22 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
>>>>                            * call always has imm = -1, but for static functions
>>>>                            * relocation is against STT_SECTION and insn->imm
>>>>                            * points to a start of a static function
>>>> +                        *
>>>> +                        * for local func relocation, the imm field encodes
>>>> +                        * the byte offset in the corresponding section.
>>>> +                        */
>>>> +                       if (relo->type == RELO_CALL)
>>>> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
>>>> +                       else
>>>> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm / BPF_INSN_SZ + 1;
>>>> +               } else if (insn_is_pseudo_func(insn)) {
>>>> +                       /*
>>>> +                        * RELO_SUBPROG_ADDR relo is always emitted even if both
>>>> +                        * functions are in the same section, so it shouldn't reach here.
>>>>                            */
>>>> -                       sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
>>>> +                       pr_warn("prog '%s': missing relo for insn #%zu, type %d\n",
>>>
>>> nit: "missing subprog addr relo" to make it clearer?
>>
>> sure. will do.
> 
> given the "generic support" comment above, I think we should still
> support this case as well. WDYT?

Even for global function with ldimm64, relocations should have been 
generated previously. I will double verify to ensure this is true
for global function as well for different cases, in the same section or 
different sections, etc.

> 
>>
>>>
>>>> +                               prog->name, insn_idx, relo->type);
>>>> +                       return -LIBBPF_ERRNO__RELOC;
>>>>                   } else {
>>>>                           /* if subprogram call is to a static function within
>>>>                            * the same ELF section, there won't be any relocation
>>>> --
>>>> 2.24.1
>>>>

^ permalink raw reply	[flat|nested] 29+ messages in thread

* Re: [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation
  2021-02-23 19:47         ` Yonghong Song
@ 2021-02-23 21:24           ` Andrii Nakryiko
  0 siblings, 0 replies; 29+ messages in thread
From: Andrii Nakryiko @ 2021-02-23 21:24 UTC (permalink / raw)
  To: Yonghong Song
  Cc: bpf, Alexei Starovoitov, Cong Wang, Daniel Borkmann, Kernel Team

On Tue, Feb 23, 2021 at 11:47 AM Yonghong Song <yhs@fb.com> wrote:
>
>
>
> On 2/23/21 11:19 AM, Andrii Nakryiko wrote:
> > On Tue, Feb 23, 2021 at 10:56 AM Yonghong Song <yhs@fb.com> wrote:
> >>
> >>
> >>
> >> On 2/23/21 12:03 AM, Andrii Nakryiko wrote:
> >>> On Wed, Feb 17, 2021 at 12:56 PM Yonghong Song <yhs@fb.com> wrote:
> >>>>
> >>>> A new relocation RELO_SUBPROG_ADDR is added to capture
> >>>> local (static) function pointers loaded with ld_imm64
> >>>> insns. Such ld_imm64 insns are marked with
> >>>> BPF_PSEUDO_FUNC and will be passed to kernel so
> >>>> kernel can replace them with proper actual jited
> >>>> func addresses.
> >>>>
> >>>> Signed-off-by: Yonghong Song <yhs@fb.com>
> >>>> ---
> >>>>    tools/lib/bpf/libbpf.c | 40 +++++++++++++++++++++++++++++++++++++---
> >>>>    1 file changed, 37 insertions(+), 3 deletions(-)
> >>>>
> >>>> diff --git a/tools/lib/bpf/libbpf.c b/tools/lib/bpf/libbpf.c
> >>>> index 21a3eedf070d..772c7455f1a2 100644
> >>>> --- a/tools/lib/bpf/libbpf.c
> >>>> +++ b/tools/lib/bpf/libbpf.c
> >>>> @@ -188,6 +188,7 @@ enum reloc_type {
> >>>>           RELO_CALL,
> >>>>           RELO_DATA,
> >>>>           RELO_EXTERN,
> >>>> +       RELO_SUBPROG_ADDR,
> >>>>    };
> >>>>
> >>>>    struct reloc_desc {
> >>>> @@ -579,6 +580,11 @@ static bool is_ldimm64(struct bpf_insn *insn)
> >>>>           return insn->code == (BPF_LD | BPF_IMM | BPF_DW);
> >>>>    }
> >>>>
> >>>> +static bool insn_is_pseudo_func(struct bpf_insn *insn)
> >>>> +{
> >>>> +       return is_ldimm64(insn) && insn->src_reg == BPF_PSEUDO_FUNC;
> >>>> +}
> >>>> +
> >>>>    static int
> >>>>    bpf_object__init_prog(struct bpf_object *obj, struct bpf_program *prog,
> >>>>                         const char *name, size_t sec_idx, const char *sec_name,
> >>>> @@ -3406,6 +3412,16 @@ static int bpf_program__record_reloc(struct bpf_program *prog,
> >>>>                   return -LIBBPF_ERRNO__RELOC;
> >>>>           }
> >>>>
> >>>> +       if (GELF_ST_BIND(sym->st_info) == STB_LOCAL &&
> >>>> +           GELF_ST_TYPE(sym->st_info) == STT_SECTION &&
> >>>
> >>> STB_LOCAL + STT_SECTION is a section symbol. But STT_FUNC symbol could
> >>> be referenced as well, no? So this is too strict.
> >>
> >> Yes, STT_FUNC symbol could be referenced but we do not have use
> >> case yet. If we encode STT_FUNC (global), the kernel will reject
> >> it. We can extend libbpf to support STT_FUNC once we got a use
> >> case.
> >
> > I don't really like tailoring libbpf generic SUBPROG_ADDR relocation
> > to one current specific use case, though. Taking the address of
> > SUBPROG_ADDR is not, conceptually, tied with passing it to for_each as
> > a callback. E.g., what if you just want to compare two registers
> > pointing to subprogs, without actually passing them to for_each(). I
> > don't know if it's possible right now, but I don't see why that
> > shouldn't be supported. In the latter case, adding arbitrary
> > restrictions about static vs global functions doesn't make much sense.
> >
> > So let's teach libbpf the right logic without assuming any specific
> > use case. It pays off in the long run.
>
> Okay, Will support global function as well. It won't hurt.
>
> >
> >>
> >>>
> >>>> +           (!shdr_idx || shdr_idx == obj->efile.text_shndx) &&
> >>>
> >>> this doesn't look right, shdr_idx == 0 is a bad condition and should
> >>> be rejected, not accepted.
> >>
> >> it is my fault. Will fix in the next revision.
> >>
> >>>
> >>>> +           !(sym->st_value % BPF_INSN_SZ)) {
> >>>> +               reloc_desc->type = RELO_SUBPROG_ADDR;
> >>>> +               reloc_desc->insn_idx = insn_idx;
> >>>> +               reloc_desc->sym_off = sym->st_value;
> >>>> +               return 0;
> >>>> +       }
> >>>> +
> >>>
> >>> So see code right after sym_is_extern(sym) check. It checks for valid
> >>> shrd_idx, which is good and would be good to use that. After that we
> >>> can assume shdr_idx is valid and we can make a simple
> >>> obj->efile.text_shndx check then and use that as a signal that this is
> >>> SUBPROG_ADDR relocation (instead of deducing that from STT_SECTION).
> >>>
> >>> And !(sym->st_value % BPF_INSN_SZ) should be reported as an error, not
> >>> silently skipped. Again, just how BPF_JMP | BPF_CALL does it. That way
> >>> it's more user-friendly, if something goes wrong. So it will look like
> >>> this:
> >>>
> >>> if (shdr_idx == obj->efile.text_shndx) {
> >>>       /* check sym->st_value, pr_warn(), return error */
> >>>
> >>>       reloc_desc->type = RELO_SUBPROG_ADDR;
> >>>       ...
> >>>       return 0;
> >>> }
> >>
> >> Okay. Will do similar checking to insn->code == (BPF_JMP | BPF_CALL)
> >> in the next revision.
> >>
> >>>
> >>>>           if (sym_is_extern(sym)) {
> >>>>                   int sym_idx = GELF_R_SYM(rel->r_info);
> >>>>                   int i, n = obj->nr_extern;
> >>>> @@ -6172,6 +6188,10 @@ bpf_object__relocate_data(struct bpf_object *obj, struct bpf_program *prog)
> >>>>                           }
> >>>>                           relo->processed = true;
> >>>>                           break;
> >>>> +               case RELO_SUBPROG_ADDR:
> >>>> +                       insn[0].src_reg = BPF_PSEUDO_FUNC;
> >>>
> >>> BTW, doesn't Clang emit instruction with BPF_PSEUDO_FUNC set properly
> >>> already? If not, why not?
> >>
> >> This is really a contract between libbpf and kernel, similar to
> >> BPF_PSEUDO_MAP_FD/BPF_PSEUDO_MAP_VALUE/BPF_PSEUDO_BTF_ID.
> >> Adding encoding in clang is not needed as this is simply a load
> >> of function address as far as clang concerned.
> >
> > Yeah, not a big deal, I was under the impression we do that for other
> > BPF_PSEUDO cases, but checking other parts of libbpf, doesn't seem
> > like that's the case.
> >
> >>
> >>>
> >>>> +                       /* will be handled as a follow up pass */
> >>>> +                       break;
> >>>>                   case RELO_CALL:
> >>>>                           /* will be handled as a follow up pass */
> >>>>                           break;
> >>>> @@ -6358,11 +6378,11 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
> >>>>
> >>>>           for (insn_idx = 0; insn_idx < prog->sec_insn_cnt; insn_idx++) {
> >>>>                   insn = &main_prog->insns[prog->sub_insn_off + insn_idx];
> >>>> -               if (!insn_is_subprog_call(insn))
> >>>> +               if (!insn_is_subprog_call(insn) && !insn_is_pseudo_func(insn))
> >>>>                           continue;
> >>>>
> >>>>                   relo = find_prog_insn_relo(prog, insn_idx);
> >>>> -               if (relo && relo->type != RELO_CALL) {
> >>>> +               if (relo && relo->type != RELO_CALL && relo->type != RELO_SUBPROG_ADDR) {
> >>>>                           pr_warn("prog '%s': unexpected relo for insn #%zu, type %d\n",
> >>>>                                   prog->name, insn_idx, relo->type);
> >>>>                           return -LIBBPF_ERRNO__RELOC;
> >>>> @@ -6374,8 +6394,22 @@ bpf_object__reloc_code(struct bpf_object *obj, struct bpf_program *main_prog,
> >>>>                            * call always has imm = -1, but for static functions
> >>>>                            * relocation is against STT_SECTION and insn->imm
> >>>>                            * points to a start of a static function
> >>>> +                        *
> >>>> +                        * for local func relocation, the imm field encodes
> >>>> +                        * the byte offset in the corresponding section.
> >>>> +                        */
> >>>> +                       if (relo->type == RELO_CALL)
> >>>> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
> >>>> +                       else
> >>>> +                               sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm / BPF_INSN_SZ + 1;
> >>>> +               } else if (insn_is_pseudo_func(insn)) {
> >>>> +                       /*
> >>>> +                        * RELO_SUBPROG_ADDR relo is always emitted even if both
> >>>> +                        * functions are in the same section, so it shouldn't reach here.
> >>>>                            */
> >>>> -                       sub_insn_idx = relo->sym_off / BPF_INSN_SZ + insn->imm + 1;
> >>>> +                       pr_warn("prog '%s': missing relo for insn #%zu, type %d\n",
> >>>
> >>> nit: "missing subprog addr relo" to make it clearer?
> >>
> >> sure. will do.
> >
> > given the "generic support" comment above, I think we should still
> > support this case as well. WDYT?
>
> Even for global function with ldimm64, relocations should have been
> generated previously. I will double verify to ensure this is true
> for global function as well for different cases, in the same section or
> different sections, etc.

Thanks! Subprogram call within another subprogram definitely doesn't
generate relocation, but this might be the only exception. Sorry for
nagging about this :) If relo is always there, then this error is good
as is.

>
> >
> >>
> >>>
> >>>> +                               prog->name, insn_idx, relo->type);
> >>>> +                       return -LIBBPF_ERRNO__RELOC;
> >>>>                   } else {
> >>>>                           /* if subprogram call is to a static function within
> >>>>                            * the same ELF section, there won't be any relocation
> >>>> --
> >>>> 2.24.1
> >>>>

^ permalink raw reply	[flat|nested] 29+ messages in thread

end of thread, back to index

Thread overview: 29+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-02-17 18:18 [PATCH bpf-next v2 00/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 01/11] bpf: factor out visit_func_call_insn() in check_cfg() Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 02/11] bpf: factor out verbose_invalid_scalar() Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 03/11] bpf: refactor check_func_call() to allow callback function Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 04/11] bpf: add bpf_for_each_map_elem() helper Yonghong Song
2021-02-22 20:59   ` Alexei Starovoitov
2021-02-23 18:39     ` Yonghong Song
2021-02-23 18:46       ` Alexei Starovoitov
2021-02-23 19:37         ` Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 05/11] bpf: add hashtab support for " Yonghong Song
2021-02-22 22:56   ` Alexei Starovoitov
2021-02-23 18:41     ` Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 06/11] bpf: add arraymap " Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 07/11] libbpf: move function is_ldimm64() earlier in libbpf.c Yonghong Song
2021-02-23  8:06   ` Andrii Nakryiko
2021-02-17 18:18 ` [PATCH bpf-next v2 08/11] libbpf: support local function pointer relocation Yonghong Song
2021-02-23  8:03   ` Andrii Nakryiko
2021-02-23 18:55     ` Yonghong Song
2021-02-23 19:07       ` Alexei Starovoitov
2021-02-23 19:21         ` Andrii Nakryiko
2021-02-23 19:19       ` Andrii Nakryiko
2021-02-23 19:47         ` Yonghong Song
2021-02-23 21:24           ` Andrii Nakryiko
2021-02-17 18:18 ` [PATCH bpf-next v2 09/11] bpftool: print local function pointer properly Yonghong Song
2021-02-23  8:06   ` Andrii Nakryiko
2021-02-23 19:00     ` Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 10/11] selftests/bpf: add hashmap test for bpf_for_each_map_elem() helper Yonghong Song
2021-02-17 18:18 ` [PATCH bpf-next v2 11/11] selftests/bpf: add arraymap " Yonghong Song
2021-02-17 18:29 ` [PATCH bpf-next v2 00/11] bpf: add " Yonghong Song

BPF Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/bpf/0 bpf/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 bpf bpf/ https://lore.kernel.org/bpf \
		bpf@vger.kernel.org
	public-inbox-index bpf

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.bpf


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git