Re: [PATCH bpf-next v3 02/10] bpf: btf: Validate type reference

[kbuild test robot]

Hi Martin,

Thank you for the patch! Perhaps something to improve:

[auto build test WARNING on bpf-next/master]

url:
https://github.com/0day-ci/linux/commits/Martin-KaFai-Lau/BTF-BPF-Type-Format/20180417-142247
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master


coccinelle warnings: (new ones prefixed by >>)

>> kernel/bpf/btf.c:353:2-3: Unneeded semicolon
   kernel/bpf/btf.c:280:2-3: Unneeded semicolon
   kernel/bpf/btf.c:663:2-3: Unneeded semicolon

Please review and possibly fold the followup patch.

---
0-DAY kernel test infrastructureOpen Source Technology Center
https://lists.01.org/pipermail/kbuild-all   Intel Corporation

[PATCH bpf-next v3 02/10] bpf: btf: Validate type reference

[Martin KaFai Lau]

After collecting all btf_type in the first pass in an earlier patch,
the second pass (in this patch) can validate the reference types
(e.g. the referring type does exist and it does not refer to itself).

While checking the reference type, it also gathers other information (e.g.
the size of an array).  This info will be useful in checking the
struct's members in a later patch.  They will also be useful in doing
pretty print later.

Signed-off-by: Martin KaFai Lau 
Acked-by: Alexei Starovoitov 
---
 include/linux/btf.h |  37 +++
 kernel/bpf/btf.c| 668 +++-
 2 files changed, 704 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/btf.h

diff --git a/include/linux/btf.h b/include/linux/btf.h
new file mode 100644
index ..f14b60368753
--- /dev/null
+++ b/include/linux/btf.h
@@ -0,0 +1,37 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/* Copyright (c) 2018 Facebook */
+
+#ifndef _LINUX_BTF_H
+#define _LINUX_BTF_H 1
+
+#include 
+
+struct btf;
+struct btf_type;
+
+/* Figure out the size of a type_id.  If type_id is a modifier
+ * (e.g. const), it will be resolved to find out the type with size.
+ *
+ * For example:
+ * In describing "const void *",  type_id is "const" and "const"
+ * refers to "void *".  The return type will be "void *".
+ *
+ * If type_id is a simple "int", then return type will be "int".
+ *
+ * @btf: struct btf object
+ * @type_id: Find out the size of type_id. The type_id of the return
+ *   type is set to *type_id.
+ * @ret_size: It can be NULL.  If not NULL, the size of the return
+ *type is set to *ret_size.
+ * Return: The btf_type (resolved to another type with size info if needed).
+ * NULL is returned if type_id itself does not have size info
+ * (e.g. void) or it cannot be resolved to another type that
+ * has size info.
+ * *type_id and *ret_size will not be changed in the
+ * NULL return case.
+ */
+const struct btf_type *btf_type_id_size(const struct btf *btf,
+   u32 *type_id,
+   u32 *ret_size);
+
+#endif
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 905be2f48a35..6ade409da2f9 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -105,6 +105,50 @@
  *
  * In the first pass, it still does some verifications (e.g.
  * checking the name is a valid offset to the string section).
+ *
+ * Pass #2
+ * ~~~
+ * The main focus is to resolve a btf_type that is referring
+ * to another type.
+ *
+ * We have to ensure the referring type:
+ * 1) does exist in the BTF (i.e. in btf->types[])
+ * 2) does not cause a loop:
+ * struct A {
+ * struct B b;
+ * };
+ *
+ * struct B {
+ * struct A a;
+ * };
+ *
+ * btf_type_needs_resolve() decides if a btf_type needs
+ * to be resolved.
+ *
+ * The needs_resolve type implements the "resolve()" ops which
+ * essentially does a DFS and detects backedge.
+ *
+ * During resolve (or DFS), different C types have different
+ * "RESOLVED" conditions.
+ *
+ * When resolving a BTF_KIND_STRUCT, we need to resolve all its
+ * members because a member is always referring to another
+ * type.  A struct's member can be treated as "RESOLVED" if
+ * it is referring to a BTF_KIND_PTR.  Otherwise, the
+ * following valid C struct would be rejected:
+ *
+ * struct A {
+ * int m;
+ * struct A *a;
+ * };
+ *
+ * When resolving a BTF_KIND_PTR, it needs to keep resolving if
+ * it is referring to another BTF_KIND_PTR.  Otherwise, we cannot
+ * detect a pointer loop, e.g.:
+ * BTF_KIND_CONST -> BTF_KIND_PTR -> BTF_KIND_CONST -> BTF_KIND_PTR +
+ *^ |
+ *+-+
+ *
  */
 
 #define BITS_PER_U64 (sizeof(u64) * BITS_PER_BYTE)
@@ -127,12 +171,19 @@
 i < btf_type_vlen(struct_type);\
 i++, member++)
 
+#define for_each_member_from(i, from, struct_type, member) \
+   for (i = from, member = btf_type_member(struct_type) + from;\
+i < btf_type_vlen(struct_type);\
+i++, member++)
+
 struct btf {
union {
struct btf_header *hdr;
void *data;
};
struct btf_type **types;
+   u32 *resolved_ids;
+   u32 *resolved_sizes;
const char *strings;
void *nohdr_data;
u32 nr_types;
@@ -140,10 +191,42 @@ struct btf {
u32 data_size;
 };
 
+enum verifier_phase {
+   CHECK_META,
+   CHECK_TYPE,
+};
+
+struct resolve_vertex {
+   const struct btf_type *t;
+   u32 type_id;
+   u16 next_member;
+};
+
+enum visit_state {
+   NOT_VISITED,
+   VISITED,
+   RESOLVED,
+};
+
+enum resolve_mode {
+   RESOLVE_TBD,/* To Be Determined */
+