[bpf-next,v4,02/13] bpf: btf: Add BTF_KIND_FUNC

Message ID 20181108203657.3138259-3-yhs@fb.com
State Changes Requested
Delegated to: BPF Maintainers
Headers show
Series
  • bpf: add btf func info support
Related show

Commit Message

Yonghong Song Nov. 8, 2018, 8:36 p.m.
This patch adds BTF_KIND_FUNC support to the type section.
BTF_KIND_FUNC is used to specify the signature of a
defined subprogram or the pointee of a function pointer.

In BTF, the function type related data structures are
  struct bpf_param {
    __u32 name_off; /* parameter name */
    __u32 type; /* parameter type */
  };
  struct bpf_type {
    __u32 name_off; /* function name */
    __u32 info; /* BTF_KIND_FUNC and num of parameters (#vlen) */
    __u32 type; /* return type */
  }
The data layout of the function type:
  struct bpf_type
  #vlen number of bpf_param's

For a defined subprogram with valid function body,
  . function name and all parameter names except the vararg
    must be valid C identifier.
For the pointee of a function pointer,
  . function name and all parameter names will
have name_off = 0 to indicate a non-existing name.

As a concrete example, for the C program below,
  int foo(int (*bar)(int)) { return bar(5); }
two func types will be generated:
  FuncType #1: subprogram "foo" with parameter "bar"
  FuncType #2: pointee of function pointer "int (*)(int)"

Signed-off-by: Martin KaFai Lau <kafai@fb.com>
Signed-off-by: Yonghong Song <yhs@fb.com>
---
 include/uapi/linux/btf.h |  17 ++-
 kernel/bpf/btf.c         | 309 ++++++++++++++++++++++++++++++++++-----
 2 files changed, 290 insertions(+), 36 deletions(-)

Comments

Edward Cree Nov. 8, 2018, 8:52 p.m. | #1
On 08/11/18 20:36, Yonghong Song wrote:
> This patch adds BTF_KIND_FUNC support to the type section.
> BTF_KIND_FUNC is used to specify the signature of a
> defined subprogram or the pointee of a function pointer.
>
> In BTF, the function type related data structures are
>   struct bpf_param {
>     __u32 name_off; /* parameter name */
>     __u32 type; /* parameter type */
>   };
>   struct bpf_type {
>     __u32 name_off; /* function name */
>     __u32 info; /* BTF_KIND_FUNC and num of parameters (#vlen) */
>     __u32 type; /* return type */
>   }
> The data layout of the function type:
>   struct bpf_type
>   #vlen number of bpf_param's
>
> For a defined subprogram with valid function body,
>   . function name and all parameter names except the vararg
>     must be valid C identifier.
Given that there's an intention to support other frontends besides
 C, what's the reason for this restriction?

> For the pointee of a function pointer,
>   . function name and all parameter names will
> have name_off = 0 to indicate a non-existing name.
Why can't function pointer parameters have names?
E.g. imagine something like struct net_device_ops.  All those
 function pointers have named parameters and that's relevant info
 when debugging.

-Ed
Yonghong Song Nov. 9, 2018, 12:40 a.m. | #2
On 11/8/18 12:52 PM, Edward Cree wrote:
> On 08/11/18 20:36, Yonghong Song wrote:
>> This patch adds BTF_KIND_FUNC support to the type section.
>> BTF_KIND_FUNC is used to specify the signature of a
>> defined subprogram or the pointee of a function pointer.
>>
>> In BTF, the function type related data structures are
>>    struct bpf_param {
>>      __u32 name_off; /* parameter name */
>>      __u32 type; /* parameter type */
>>    };
>>    struct bpf_type {
>>      __u32 name_off; /* function name */
>>      __u32 info; /* BTF_KIND_FUNC and num of parameters (#vlen) */
>>      __u32 type; /* return type */
>>    }
>> The data layout of the function type:
>>    struct bpf_type
>>    #vlen number of bpf_param's
>>
>> For a defined subprogram with valid function body,
>>    . function name and all parameter names except the vararg
>>      must be valid C identifier.
> Given that there's an intention to support other frontends besides
>   C, what's the reason for this restriction?

This (C) is the typical usage today. If later on other frontend
generates bpf programs with more relaxed symbol name requirement,
we can certainly relax the rule.

> 
>> For the pointee of a function pointer,
>>    . function name and all parameter names will
>> have name_off = 0 to indicate a non-existing name.
> Why can't function pointer parameters have names?

Currently, both bcc and llvm does not retain function pointer
arguments in dwarf. For LLVM, the IR generation for function pointer
type discards the argument name. So I did the checking because
llvm does not generate it.

We can relax the restrictions later if the compiler starts
to keep argument names in the IR.

> E.g. imagine something like struct net_device_ops.  All those
>   function pointers have named parameters and that's relevant info
>   when debugging.
> 
> -Ed
>

Patch

diff --git a/include/uapi/linux/btf.h b/include/uapi/linux/btf.h
index 972265f32871..9e7c74a83ee7 100644
--- a/include/uapi/linux/btf.h
+++ b/include/uapi/linux/btf.h
@@ -40,7 +40,8 @@  struct btf_type {
 	/* "size" is used by INT, ENUM, STRUCT and UNION.
 	 * "size" tells the size of the type it is describing.
 	 *
-	 * "type" is used by PTR, TYPEDEF, VOLATILE, CONST and RESTRICT.
+	 * "type" is used by PTR, TYPEDEF, VOLATILE, CONST, RESTRICT
+	 * and FUNC.
 	 * "type" is a type_id referring to another type.
 	 */
 	union {
@@ -64,8 +65,9 @@  struct btf_type {
 #define BTF_KIND_VOLATILE	9	/* Volatile	*/
 #define BTF_KIND_CONST		10	/* Const	*/
 #define BTF_KIND_RESTRICT	11	/* Restrict	*/
-#define BTF_KIND_MAX		11
-#define NR_BTF_KINDS		12
+#define BTF_KIND_FUNC		12	/* Function	*/
+#define BTF_KIND_MAX		12
+#define NR_BTF_KINDS		13
 
 /* For some specific BTF_KIND, "struct btf_type" is immediately
  * followed by extra data.
@@ -110,4 +112,13 @@  struct btf_member {
 	__u32	offset;	/* offset in bits */
 };
 
+/* BTF_KIND_FUNC is followed by multiple "struct btf_param".
+ * The exact number of btf_param is stored in the vlen (of the
+ * info in "struct btf_type").
+ */
+struct btf_param {
+	__u32	name_off;
+	__u32	type;
+};
+
 #endif /* _UAPI__LINUX_BTF_H__ */
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 2a50d87de485..62140da0c10d 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -5,6 +5,7 @@ 
 #include <uapi/linux/types.h>
 #include <linux/seq_file.h>
 #include <linux/compiler.h>
+#include <linux/ctype.h>
 #include <linux/errno.h>
 #include <linux/slab.h>
 #include <linux/anon_inodes.h>
@@ -259,6 +260,7 @@  static const char * const btf_kind_str[NR_BTF_KINDS] = {
 	[BTF_KIND_VOLATILE]	= "VOLATILE",
 	[BTF_KIND_CONST]	= "CONST",
 	[BTF_KIND_RESTRICT]	= "RESTRICT",
+	[BTF_KIND_FUNC]		= "FUNC",
 };
 
 struct btf_kind_operations {
@@ -281,6 +283,9 @@  struct btf_kind_operations {
 static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS];
 static struct btf_type btf_void;
 
+static int btf_resolve(struct btf_verifier_env *env,
+		       const struct btf_type *t, u32 type_id);
+
 static bool btf_type_is_modifier(const struct btf_type *t)
 {
 	/* Some of them is not strictly a C modifier
@@ -314,9 +319,27 @@  static bool btf_type_is_fwd(const struct btf_type *t)
 	return BTF_INFO_KIND(t->info) == BTF_KIND_FWD;
 }
 
+static bool btf_type_is_func(const struct btf_type *t)
+{
+	return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC;
+}
+
+static bool btf_type_is_func_prog(const struct btf_type *t)
+{
+	return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC &&
+	       t->name_off;
+}
+
+static bool btf_type_is_func_proto(const struct btf_type *t)
+{
+	return BTF_INFO_KIND(t->info) == BTF_KIND_FUNC &&
+	       !t->name_off;
+}
+
 static bool btf_type_nosize(const struct btf_type *t)
 {
-	return btf_type_is_void(t) || btf_type_is_fwd(t);
+	return btf_type_is_void(t) || btf_type_is_fwd(t) ||
+	       btf_type_is_func(t);
 }
 
 static bool btf_type_nosize_or_null(const struct btf_type *t)
@@ -433,6 +456,27 @@  static bool btf_name_offset_valid(const struct btf *btf, u32 offset)
 		offset < btf->hdr.str_len;
 }
 
+static bool btf_name_valid_identifier(const struct btf *btf, u32 offset)
+{
+	/* offset must be valid */
+	const char *src = &btf->strings[offset];
+	const char *src_limit;
+
+	if (!isalpha(*src) && *src != '_')
+		return false;
+
+	/* set a limit on identifier length */
+	src_limit = src + KSYM_NAME_LEN;
+	src++;
+	while (*src && src < src_limit) {
+		if (!isalnum(*src) && *src != '_')
+			return false;
+		src++;
+	}
+
+	return !*src;
+}
+
 static const char *btf_name_by_offset(const struct btf *btf, u32 offset)
 {
 	if (!offset)
@@ -747,7 +791,9 @@  static bool env_type_is_resolve_sink(const struct btf_verifier_env *env,
 		/* int, enum or void is a sink */
 		return !btf_type_needs_resolve(next_type);
 	case RESOLVE_PTR:
-		/* int, enum, void, struct or array is a sink for ptr */
+		/* int, enum, void, struct, array or func_proto is a sink
+		 * for ptr
+		 */
 		return !btf_type_is_modifier(next_type) &&
 			!btf_type_is_ptr(next_type);
 	case RESOLVE_STRUCT_OR_ARRAY:
@@ -1170,6 +1216,14 @@  static int btf_modifier_resolve(struct btf_verifier_env *env,
 		return -EINVAL;
 	}
 
+	if (btf_type_is_func_proto(next_type)) {
+		if (env->resolve_mode == RESOLVE_PTR)
+			goto resolved;
+
+		btf_verifier_log_type(env, v->t, "Invalid type_id");
+		return -EINVAL;
+	}
+
 	/* "typedef void new_void", "const void"...etc */
 	if (btf_type_is_void(next_type) || btf_type_is_fwd(next_type))
 		goto resolved;
@@ -1185,7 +1239,8 @@  static int btf_modifier_resolve(struct btf_verifier_env *env,
 	 * pretty print).
 	 */
 	if (!btf_type_id_size(btf, &next_type_id, &next_type_size) &&
-	    !btf_type_nosize(btf_type_id_resolve(btf, &next_type_id))) {
+	    (!btf_type_nosize(btf_type_id_resolve(btf, &next_type_id)) ||
+	     btf_type_is_func_prog(next_type))) {
 		btf_verifier_log_type(env, v->t, "Invalid type_id");
 		return -EINVAL;
 	}
@@ -1212,7 +1267,8 @@  static int btf_ptr_resolve(struct btf_verifier_env *env,
 	}
 
 	/* "void *" */
-	if (btf_type_is_void(next_type) || btf_type_is_fwd(next_type))
+	if (btf_type_is_void(next_type) || btf_type_is_fwd(next_type) ||
+	    btf_type_is_func_proto(next_type))
 		goto resolved;
 
 	if (!env_type_is_resolve_sink(env, next_type) &&
@@ -1242,7 +1298,8 @@  static int btf_ptr_resolve(struct btf_verifier_env *env,
 	}
 
 	if (!btf_type_id_size(btf, &next_type_id, &next_type_size) &&
-	    !btf_type_nosize(btf_type_id_resolve(btf, &next_type_id))) {
+	    (!btf_type_nosize(btf_type_id_resolve(btf, &next_type_id)) ||
+	     btf_type_is_func_prog(next_type))) {
 		btf_verifier_log_type(env, v->t, "Invalid type_id");
 		return -EINVAL;
 	}
@@ -1550,6 +1607,14 @@  static s32 btf_struct_check_meta(struct btf_verifier_env *env,
 			return -EINVAL;
 		}
 
+		if (member->name_off &&
+		    !btf_name_valid_identifier(btf, member->name_off)) {
+			btf_verifier_log_member(env, t, member,
+						"Invalid member name:%s",
+						btf_name_by_offset(btf, member->name_off));
+			return -EINVAL;
+		}
+
 		/* A member cannot be in type void */
 		if (!member->type || !BTF_TYPE_ID_VALID(member->type)) {
 			btf_verifier_log_member(env, t, member,
@@ -1787,6 +1852,174 @@  static struct btf_kind_operations enum_ops = {
 	.seq_show = btf_enum_seq_show,
 };
 
+static s32 btf_func_check_meta(struct btf_verifier_env *env,
+			       const struct btf_type *t,
+			       u32 meta_left)
+{
+	u32 meta_needed = btf_type_vlen(t) * sizeof(struct btf_param);
+
+	if (meta_left < meta_needed) {
+		btf_verifier_log_basic(env, t,
+				       "meta_left:%u meta_needed:%u",
+				       meta_left, meta_needed);
+		return -EINVAL;
+	}
+
+	btf_verifier_log_type(env, t, NULL);
+
+	return meta_needed;
+}
+
+static void btf_func_log(struct btf_verifier_env *env,
+			 const struct btf_type *t)
+{
+	u16 nr_args = btf_type_vlen(t), i;
+	struct btf_param *args = (struct btf_param *)(t + 1);
+
+	btf_verifier_log(env, "return=%u args=(", t->type);
+	if (!nr_args) {
+		btf_verifier_log(env, "void");
+		goto done;
+	}
+
+	if (nr_args == 1 && !args[0].type) {
+		/* Only one vararg */
+		btf_verifier_log(env, "vararg");
+		goto done;
+	}
+
+	btf_verifier_log(env, "%u %s", args[0].type,
+			 btf_name_by_offset(env->btf,
+					    args[0].name_off));
+	for (i = 1; i < nr_args - 1; i++)
+		btf_verifier_log(env, ", %u %s", args[i].type,
+				 btf_name_by_offset(env->btf,
+						    args[i].name_off));
+
+	if (nr_args > 1) {
+		struct btf_param *last_arg = &args[nr_args - 1];
+
+		if (last_arg->type)
+			btf_verifier_log(env, ", %u %s", last_arg->type,
+					 btf_name_by_offset(env->btf,
+							    last_arg->name_off));
+		else
+			btf_verifier_log(env, ", vararg");
+	}
+
+done:
+	btf_verifier_log(env, ")");
+}
+
+static int btf_func_check(struct btf_verifier_env *env,
+			  const struct btf_type *t,
+			  u32 type_id)
+{
+	u16 nr_args = btf_type_vlen(t), i;
+	const struct btf *btf = env->btf;
+	const struct btf_type *ret_type;
+	struct btf_param *args = (struct btf_param *)(t + 1);
+	u32 ret_type_id;
+	int err;
+
+	/* Check non-0 name_off must point to valid identifier */
+	if (t->name_off &&
+	    !btf_name_valid_identifier(btf, t->name_off)) {
+		btf_verifier_log_type(env, t, "Invalid type_id");
+		return -EINVAL;
+	}
+
+	/* Check func return type which could be "void" (t->type == 0) */
+	ret_type_id = t->type;
+	if (ret_type_id) {
+		/* return type is not "void" */
+		ret_type = btf_type_by_id(btf, ret_type_id);
+		if (btf_type_needs_resolve(ret_type) &&
+		    !env_type_is_resolved(env, ret_type_id)) {
+			err = btf_resolve(env, ret_type, ret_type_id);
+			if (err)
+				return err;
+		}
+
+		/* Ensure the return type is a type that has a size */
+		if (!btf_type_id_size(btf, &ret_type_id, NULL)) {
+			btf_verifier_log_type(env, t, "Invalid return type");
+			return -EINVAL;
+		}
+	}
+
+	if (!nr_args)
+		return 0;
+
+	/* Last func arg type_id could be 0 if it is a vararg */
+	if (!args[nr_args - 1].type) {
+		if (args[nr_args - 1].name_off) {
+			btf_verifier_log_type(env, t, "Invalid arg#%u", nr_args);
+			return -EINVAL;
+		}
+		nr_args--;
+	}
+
+	err = 0;
+	for (i = 0; i < nr_args; i++) {
+		const struct btf_type *arg_type;
+		u32 arg_type_id;
+
+		arg_type_id = args[i].type;
+		arg_type = btf_type_by_id(btf, arg_type_id);
+		if (!arg_type ||
+		    /* func has name, all its args must have names.
+		     * func has no name, all its args cannot have names.
+		     */
+		    (!!args[i].name_off != !!t->name_off)) {
+			btf_verifier_log_type(env, t, "Invalid arg#%u", i + 1);
+			err = -EINVAL;
+			break;
+		}
+
+		if (args[i].name_off &&
+		    (!btf_name_offset_valid(btf, args[i].name_off) ||
+		     !btf_name_valid_identifier(btf, args[i].name_off))) {
+			btf_verifier_log_type(env, t,
+					      "Invalid arg#%u", i + 1);
+			err = -EINVAL;
+			break;
+		}
+
+		if (btf_type_needs_resolve(arg_type) &&
+		    !env_type_is_resolved(env, arg_type_id)) {
+			err = btf_resolve(env, arg_type, arg_type_id);
+			if (err)
+				break;
+		}
+
+		if (!btf_type_id_size(btf, &arg_type_id, NULL)) {
+			btf_verifier_log_type(env, t, "Invalid arg#%u", i + 1);
+			err = -EINVAL;
+			break;
+		}
+	}
+
+	return err;
+}
+
+static struct btf_kind_operations func_ops = {
+	.check_meta = btf_func_check_meta,
+	.resolve = btf_df_resolve,
+	/*
+	 * BTF_KIND_FUNC cannot be directly referred by
+	 * a struct's member.
+	 *
+	 * It should be a funciton pointer instead.
+	 * (i.e. struct's member -> BTF_KIND_PTR -> BTF_KIND_FUNC)
+	 *
+	 * Hence, there is no btf_func_check_member().
+	 */
+	.check_member = btf_df_check_member,
+	.log_details = btf_func_log,
+	.seq_show = btf_df_seq_show,
+};
+
 static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS] = {
 	[BTF_KIND_INT] = &int_ops,
 	[BTF_KIND_PTR] = &ptr_ops,
@@ -1799,6 +2032,7 @@  static const struct btf_kind_operations * const kind_ops[NR_BTF_KINDS] = {
 	[BTF_KIND_VOLATILE] = &modifier_ops,
 	[BTF_KIND_CONST] = &modifier_ops,
 	[BTF_KIND_RESTRICT] = &modifier_ops,
+	[BTF_KIND_FUNC] = &func_ops,
 };
 
 static s32 btf_check_meta(struct btf_verifier_env *env,
@@ -1870,30 +2104,6 @@  static int btf_check_all_metas(struct btf_verifier_env *env)
 	return 0;
 }
 
-static int btf_resolve(struct btf_verifier_env *env,
-		       const struct btf_type *t, u32 type_id)
-{
-	const struct resolve_vertex *v;
-	int err = 0;
-
-	env->resolve_mode = RESOLVE_TBD;
-	env_stack_push(env, t, type_id);
-	while (!err && (v = env_stack_peak(env))) {
-		env->log_type_id = v->type_id;
-		err = btf_type_ops(v->t)->resolve(env, v);
-	}
-
-	env->log_type_id = type_id;
-	if (err == -E2BIG)
-		btf_verifier_log_type(env, t,
-				      "Exceeded max resolving depth:%u",
-				      MAX_RESOLVE_DEPTH);
-	else if (err == -EEXIST)
-		btf_verifier_log_type(env, t, "Loop detected");
-
-	return err;
-}
-
 static bool btf_resolve_valid(struct btf_verifier_env *env,
 			      const struct btf_type *t,
 			      u32 type_id)
@@ -1927,6 +2137,39 @@  static bool btf_resolve_valid(struct btf_verifier_env *env,
 	return false;
 }
 
+static int btf_resolve(struct btf_verifier_env *env,
+		       const struct btf_type *t, u32 type_id)
+{
+	u32 save_log_type_id = env->log_type_id;
+	const struct resolve_vertex *v;
+	int err = 0;
+
+	env->resolve_mode = RESOLVE_TBD;
+	env_stack_push(env, t, type_id);
+	while (!err && (v = env_stack_peak(env))) {
+		env->log_type_id = v->type_id;
+		err = btf_type_ops(v->t)->resolve(env, v);
+	}
+
+	env->log_type_id = type_id;
+	if (err == -E2BIG) {
+		btf_verifier_log_type(env, t,
+				      "Exceeded max resolving depth:%u",
+				      MAX_RESOLVE_DEPTH);
+	} else if (err == -EEXIST) {
+		btf_verifier_log_type(env, t, "Loop detected");
+	}
+
+	/* Final sanity check */
+	if (!err && !btf_resolve_valid(env, t, type_id)) {
+		btf_verifier_log_type(env, t, "Invalid resolve state");
+		err = -EINVAL;
+	}
+
+	env->log_type_id = save_log_type_id;
+	return err;
+}
+
 static int btf_check_all_types(struct btf_verifier_env *env)
 {
 	struct btf *btf = env->btf;
@@ -1949,10 +2192,10 @@  static int btf_check_all_types(struct btf_verifier_env *env)
 				return err;
 		}
 
-		if (btf_type_needs_resolve(t) &&
-		    !btf_resolve_valid(env, t, type_id)) {
-			btf_verifier_log_type(env, t, "Invalid resolve state");
-			return -EINVAL;
+		if (btf_type_is_func(t)) {
+			err = btf_func_check(env, t, type_id);
+			if (err)
+				return err;
 		}
 	}