[PATCH bpf-next v2 0/2] limit bpf_core_types_are_compat recursion

[PATCH bpf-next v2 0/2] limit bpf_core_types_are_compat recursion

[Matteo Croce]

From: Matteo Croce <mcroce@microsoft.com>

As formerly discussed on the BPF mailing list:
https://lore.kernel.org/bpf/CAADnVQJDax2j0-7uyqdqFEnpB57om_z+Cqmi1O2QyLpHqkVKwA@mail.gmail.com/

Matteo Croce (2):
  bpf: limit bpf_core_types_are_compat() recursion
  selftests/bpf: test maximum recursion depth for
    bpf_core_types_are_compat()

 include/linux/btf.h                           |   5 +
 kernel/bpf/btf.c                              | 105 +++++++++++++++++-
 .../selftests/bpf/bpf_testmod/bpf_testmod.c   |   3 +
 tools/testing/selftests/bpf/progs/core_kern.c |  14 +++
 4 files changed, 126 insertions(+), 1 deletion(-)

-- 
2.34.1

[PATCH bpf-next v2 1/2] bpf: limit bpf_core_types_are_compat() recursion

[Matteo Croce]

From: Matteo Croce <mcroce@microsoft.com>

In userspace, bpf_core_types_are_compat() is a recursive function which
can't be put in the kernel as is.
Limit the recursion depth to 2, to avoid potential stack overflows
in kernel.

Signed-off-by: Matteo Croce <mcroce@microsoft.com>
---
 include/linux/btf.h |   5 +++
 kernel/bpf/btf.c    | 105 +++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 109 insertions(+), 1 deletion(-)

diff --git a/include/linux/btf.h b/include/linux/btf.h
index f6c43dd513fa..36bc09b8e890 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -327,6 +327,11 @@ static inline const struct btf_var_secinfo *btf_type_var_secinfo(
 	return (const struct btf_var_secinfo *)(t + 1);
 }
 
+static inline struct btf_param *btf_params(const struct btf_type *t)
+{
+	return (struct btf_param *)(t + 1);
+}
+
 #ifdef CONFIG_BPF_SYSCALL
 struct bpf_prog;
 
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index b983cee8d196..fcc3d9e45320 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -6785,10 +6785,113 @@ int register_btf_kfunc_id_set(enum bpf_prog_type prog_type,
 }
 EXPORT_SYMBOL_GPL(register_btf_kfunc_id_set);
 
+#define MAX_TYPES_ARE_COMPAT_DEPTH 2
+
+static
+int __bpf_core_types_are_compat(const struct btf *local_btf, __u32 local_id,
+				const struct btf *targ_btf, __u32 targ_id,
+				int level)
+{
+	const struct btf_type *local_type, *targ_type;
+	int depth = 32; /* max recursion depth */
+
+	/* caller made sure that names match (ignoring flavor suffix) */
+	local_type = btf_type_by_id(local_btf, local_id);
+	targ_type = btf_type_by_id(targ_btf, targ_id);
+	if (btf_kind(local_type) != btf_kind(targ_type))
+		return 0;
+
+recur:
+	depth--;
+	if (depth < 0)
+		return -EINVAL;
+
+	local_type = btf_type_skip_modifiers(local_btf, local_id, &local_id);
+	targ_type = btf_type_skip_modifiers(targ_btf, targ_id, &targ_id);
+	if (!local_type || !targ_type)
+		return -EINVAL;
+
+	if (btf_kind(local_type) != btf_kind(targ_type))
+		return 0;
+
+	switch (btf_kind(local_type)) {
+	case BTF_KIND_UNKN:
+	case BTF_KIND_STRUCT:
+	case BTF_KIND_UNION:
+	case BTF_KIND_ENUM:
+	case BTF_KIND_FWD:
+		return 1;
+	case BTF_KIND_INT:
+		/* just reject deprecated bitfield-like integers; all other
+		 * integers are by default compatible between each other
+		 */
+		return btf_int_offset(local_type) == 0 && btf_int_offset(targ_type) == 0;
+	case BTF_KIND_PTR:
+		local_id = local_type->type;
+		targ_id = targ_type->type;
+		goto recur;
+	case BTF_KIND_ARRAY:
+		local_id = btf_array(local_type)->type;
+		targ_id = btf_array(targ_type)->type;
+		goto recur;
+	case BTF_KIND_FUNC_PROTO: {
+		struct btf_param *local_p = btf_params(local_type);
+		struct btf_param *targ_p = btf_params(targ_type);
+		__u16 local_vlen = btf_vlen(local_type);
+		__u16 targ_vlen = btf_vlen(targ_type);
+		int i, err;
+
+		if (local_vlen != targ_vlen)
+			return 0;
+
+		for (i = 0; i < local_vlen; i++, local_p++, targ_p++) {
+			if (level <= 1)
+				return -EINVAL;
+
+			btf_type_skip_modifiers(local_btf, local_p->type, &local_id);
+			btf_type_skip_modifiers(targ_btf, targ_p->type, &targ_id);
+			err = __bpf_core_types_are_compat(local_btf, local_id,
+							  targ_btf, targ_id,
+							  level - 1);
+			if (err <= 0)
+				return err;
+		}
+
+		/* tail recurse for return type check */
+		btf_type_skip_modifiers(local_btf, local_type->type, &local_id);
+		btf_type_skip_modifiers(targ_btf, targ_type->type, &targ_id);
+		goto recur;
+	}
+	default:
+		return 0;
+	}
+}
+
+/* Check local and target types for compatibility. This check is used for
+ * type-based CO-RE relocations and follow slightly different rules than
+ * field-based relocations. This function assumes that root types were already
+ * checked for name match. Beyond that initial root-level name check, names
+ * are completely ignored. Compatibility rules are as follows:
+ *   - any two STRUCTs/UNIONs/FWDs/ENUMs/INTs are considered compatible, but
+ *     kind should match for local and target types (i.e., STRUCT is not
+ *     compatible with UNION);
+ *   - for ENUMs, the size is ignored;
+ *   - for INT, size and signedness are ignored;
+ *   - for ARRAY, dimensionality is ignored, element types are checked for
+ *     compatibility recursively;
+ *   - CONST/VOLATILE/RESTRICT modifiers are ignored;
+ *   - TYPEDEFs/PTRs are compatible if types they pointing to are compatible;
+ *   - FUNC_PROTOs are compatible if they have compatible signature: same
+ *     number of input args and compatible return and argument types.
+ * These rules are not set in stone and probably will be adjusted as we get
+ * more experience with using BPF CO-RE relocations.
+ */
 int bpf_core_types_are_compat(const struct btf *local_btf, __u32 local_id,
 			      const struct btf *targ_btf, __u32 targ_id)
 {
-	return -EOPNOTSUPP;
+	return __bpf_core_types_are_compat(local_btf, local_id,
+					   targ_btf, targ_id,
+					   MAX_TYPES_ARE_COMPAT_DEPTH);
 }
 
 static bool bpf_core_is_flavor_sep(const char *s)
-- 
2.34.1

[PATCH bpf-next v2 2/2] selftests/bpf: test maximum recursion depth for bpf_core_types_are_compat()

[Matteo Croce]

From: Matteo Croce <mcroce@microsoft.com>

bpf_core_types_are_compat() was limited to 2 recursion levels, which are
enough to parse a function prototype.
Add a test which checks the existence of a function prototype, so to
test the bpf_core_types_are_compat() code path.

Signed-off-by: Matteo Croce <mcroce@microsoft.com>
---
 .../selftests/bpf/bpf_testmod/bpf_testmod.c        |  3 +++
 tools/testing/selftests/bpf/progs/core_kern.c      | 14 ++++++++++++++
 2 files changed, 17 insertions(+)

diff --git a/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c b/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c
index 595d32ab285a..a457071a7751 100644
--- a/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c
+++ b/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c
@@ -13,6 +13,9 @@
 #define CREATE_TRACE_POINTS
 #include "bpf_testmod-events.h"
 
+typedef int (*func_proto_typedef)(long);
+func_proto_typedef funcp = NULL;
+
 DEFINE_PER_CPU(int, bpf_testmod_ksym_percpu) = 123;
 
 noinline void
diff --git a/tools/testing/selftests/bpf/progs/core_kern.c b/tools/testing/selftests/bpf/progs/core_kern.c
index 13499cc15c7d..bfea86b42563 100644
--- a/tools/testing/selftests/bpf/progs/core_kern.c
+++ b/tools/testing/selftests/bpf/progs/core_kern.c
@@ -101,4 +101,18 @@ int balancer_ingress(struct __sk_buff *ctx)
 	return 0;
 }
 
+typedef int (*func_proto_typedef___match)(long);
+typedef void (*func_proto_typedef___doesnt_match)(char*);
+
+int out[2];
+
+SEC("raw_tracepoint/sys_enter")
+int core_relo_recur_limit(void *ctx)
+{
+	out[0] = bpf_core_type_exists(func_proto_typedef___match);
+	out[1] = bpf_core_type_exists(func_proto_typedef___doesnt_match);
+
+	return 0;
+}
+
 char LICENSE[] SEC("license") = "GPL";
-- 
2.34.1

Re: [PATCH bpf-next v2 2/2] selftests/bpf: test maximum recursion depth for bpf_core_types_are_compat()

[Alexei Starovoitov]

On Wed, Feb 2, 2022 at 1:13 PM Matteo Croce <mcroce@linux.microsoft.com> wrote:
>
> From: Matteo Croce <mcroce@microsoft.com>
>
> bpf_core_types_are_compat() was limited to 2 recursion levels, which are
> enough to parse a function prototype.
> Add a test which checks the existence of a function prototype, so to
> test the bpf_core_types_are_compat() code path.
>
> Signed-off-by: Matteo Croce <mcroce@microsoft.com>
> ---
>  .../selftests/bpf/bpf_testmod/bpf_testmod.c        |  3 +++
>  tools/testing/selftests/bpf/progs/core_kern.c      | 14 ++++++++++++++
>  2 files changed, 17 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c b/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c
> index 595d32ab285a..a457071a7751 100644
> --- a/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c
> +++ b/tools/testing/selftests/bpf/bpf_testmod/bpf_testmod.c
> @@ -13,6 +13,9 @@
>  #define CREATE_TRACE_POINTS
>  #include "bpf_testmod-events.h"
>
> +typedef int (*func_proto_typedef)(long);
> +func_proto_typedef funcp = NULL;
> +
>  DEFINE_PER_CPU(int, bpf_testmod_ksym_percpu) = 123;
>
>  noinline void
> diff --git a/tools/testing/selftests/bpf/progs/core_kern.c b/tools/testing/selftests/bpf/progs/core_kern.c
> index 13499cc15c7d..bfea86b42563 100644
> --- a/tools/testing/selftests/bpf/progs/core_kern.c
> +++ b/tools/testing/selftests/bpf/progs/core_kern.c
> @@ -101,4 +101,18 @@ int balancer_ingress(struct __sk_buff *ctx)
>         return 0;
>  }
>
> +typedef int (*func_proto_typedef___match)(long);
> +typedef void (*func_proto_typedef___doesnt_match)(char*);
> +
> +int out[2];
> +
> +SEC("raw_tracepoint/sys_enter")
> +int core_relo_recur_limit(void *ctx)
> +{
> +       out[0] = bpf_core_type_exists(func_proto_typedef___match);
> +       out[1] = bpf_core_type_exists(func_proto_typedef___doesnt_match);

How does it test it?
The kernel code could be a nop and there will be no failure in this "test".
Please make it real.
Also add tests that exercise the limit of recursion.
One that goes over and fails and another that is right at the limit
and passes.