[RFC bpf-next 0/5] bpf: making BTF self-describing

[RFC bpf-next 0/5] bpf: making BTF self-describing

[Alan Maguire]

One problem with the BPF Type Format (BTF) is that it is hard
to extend.  BTF consists of a set of kinds, each representing
an aspect of type or variable information such as an integer,
struct, array and so on.  The problem is that at the time BTF
is encoded, we do not provide information about the kinds we
have used, so when the encoded BTF is later parsed, the tools
that parse it must know about all the kinds used at encoding
time in order to parse the BTF.  If an unknown kind is found,
we have no way of knowing what size it is, so have to give
up parsing since we cannot skip past it due to the unknown
size.

So if BTF is created with a newer toolchain which has a new
kind in it, but later parsed with an older toolchain, it
is unparseable.  Ideally we would like such BTF to be
capable of parsing, so we need a mechanism to encode info
about the kinds used at encoding time that is then easily
accessible to parsing operations.  The alternative is
the current situation, where encoding has to be pessimistic
and we have to skip various kind encodings to avoid parsing
failures.

Here we propose a scheme to encode kind information such
that parsing can proceed.  The following steps are
involved:

1. a libbpf function is introduced btf__add_kinds() which
   adds kind information
2. that kind information is encoded in BTF as a set of
   structures representing the kind encodings
3. tools will call btf__add_kinds() at BTF encoding time
   to add this kind encoding information
4. at parsing time, if an unrecognized kind is found, the
   kind encoding is used to determine the size of the
   kind representation and parsing proceeds

Steps 1 and 2 are accomplished in patches 1 and 2.
Patches 3 and 4 tackle step 4 for userspace and kernel.
Finally patch 5 tests BTF kind encoding and decoding.

To support BTF kind encoding for kernel BTF, pahole
would have to be updated to call btf__add_kinds(). 
[1] and [2] can be used to try this out.

More details are provided in the individual patches.

One potential application of this approach would be a
stable backport of patches 1 and 3; this would allow
older kernels to use latest pahole without adding
additional "skip" directives when new kinds are
added.

So assuming something like this landed, how would it
effect adding a new kind?  Once that kind was available
in the libbpf that dwarves uses, it would mean that
BTF would contain instances of that new kind.  However
if an older libbpf (that had support for parsing kind
descriptions) encountered it, parsing would still work;
the new information encoded would not be available
however.

So the result would be that a new kind would be able
to be added without breaking BTF parsing.

[1] https://github.com/alan-maguire/dwarves/tree/btf-kind-encoding
[2] https://github.com/alan-maguire/libbpf/tree/btf-kind-encoding

Alan Maguire (5):
  bpf: add kind/metadata prefixes to uapi/linux/btf.h
  libbpf: provide libbpf API to encode BTF kind information
  libbpf: use BTF-encoded kind information to help parse unrecognized
    kinds
  bpf: parse unrecognized kind info using encoded kind information (if
    present)
  selftests/bpf: test kind encoding/decoding

 include/uapi/linux/btf.h                          |   7 +
 kernel/bpf/btf.c                                  |  87 +++++-
 tools/include/uapi/linux/btf.h                    |   7 +
 tools/lib/bpf/btf.c                               | 357 ++++++++++++++++++++++
 tools/lib/bpf/btf.h                               |  10 +
 tools/lib/bpf/libbpf.map                          |   1 +
 tools/testing/selftests/bpf/prog_tests/btf_kind.c | 234 ++++++++++++++
 7 files changed, 696 insertions(+), 7 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_kind.c

-- 
1.8.3.1

[RFC bpf-next 1/5] bpf: add kind/metadata prefixes to uapi/linux/btf.h

[Alan Maguire]

This allows us to share them with kernel and userspace so that
both libbpf and the kernel can parse BTF kind information.

Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
---
 include/uapi/linux/btf.h       | 7 +++++++
 tools/include/uapi/linux/btf.h | 7 +++++++
 2 files changed, 14 insertions(+)

diff --git a/include/uapi/linux/btf.h b/include/uapi/linux/btf.h
index ec1798b..68628e9 100644
--- a/include/uapi/linux/btf.h
+++ b/include/uapi/linux/btf.h
@@ -197,4 +197,11 @@ struct btf_enum64 {
 	__u32	val_hi32;
 };
 
+/* Prefixes used for names encoding BTF kind information via structs;
+ * a "struct __BTF_KIND_ARRAY" represents how BTF_KIND_ARRAY is encoded,
+ * while a "struct __BTF_KIND_META_ARRAY" represents the metadata encoding.
+ */
+#define BTF_KIND_PFX		"__BTF_KIND_"
+#define BTF_KIND_META_PFX	"__BTF_KIND_META_"
+
 #endif /* _UAPI__LINUX_BTF_H__ */
diff --git a/tools/include/uapi/linux/btf.h b/tools/include/uapi/linux/btf.h
index ec1798b..68628e9 100644
--- a/tools/include/uapi/linux/btf.h
+++ b/tools/include/uapi/linux/btf.h
@@ -197,4 +197,11 @@ struct btf_enum64 {
 	__u32	val_hi32;
 };
 
+/* Prefixes used for names encoding BTF kind information via structs;
+ * a "struct __BTF_KIND_ARRAY" represents how BTF_KIND_ARRAY is encoded,
+ * while a "struct __BTF_KIND_META_ARRAY" represents the metadata encoding.
+ */
+#define BTF_KIND_PFX		"__BTF_KIND_"
+#define BTF_KIND_META_PFX	"__BTF_KIND_META_"
+
 #endif /* _UAPI__LINUX_BTF_H__ */
-- 
1.8.3.1

[RFC bpf-next 2/5] libbpf: provide libbpf API to encode BTF kind information

[Alan Maguire]

This can be used by BTF parsers to handle kinds they do not know about;
this is useful when the encoding libbpf is more recent than the parsing
BTF; the parser can then skip over the encoded types it does not know
about.

We use BTF to encode the BTF kinds that are known at the time of
BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
to describe each kind and any associated metadata allows BTF parsing
to handle new kinds that the parser (in libbpf or the kernel) does
not know about.  These kinds will not be used, but since we know
their format they can be skipped over and the rest of the BTF can
be parsed.  This means we can encode BTF without worrying about the
kinds a BTF parser knows about, and means we can avoid using
--skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
everything it can, something as simple as a libbpf package update
then unlocks that encoded information, whereas if we encode
pessimistically and drop representations of new kinds, this is not
possible.

So, in short, by carrying a representation of all the kinds encoded,
parsers can parse all of the encoded kinds, even if they cannot use
them all.

We use BTF itself to carry this representation because this approach
does not require BTF parsing to understand a new BTF header format;
BTF parsing simply sees some additional types it does not do anything
with.  However, a BTF parser that knows about the encoding of kind
information can use this information to guide parsing.

The process works by explicitly adding btf structs for each kind.
Each struct consists of a "struct __btf_type" followed by an array of
metadata structs representing the following metadata (for those kinds
that have it).  For kinds where a single metadata structure is used,
the metadata array has one element.  For kinds where the number
of metadata elements varies as per the info.vlen field, a zero-element
array is encoded.

For a given kind, we add a struct __BTF_KIND_<kind>.  For example,

struct __BTF_KIND_INT {
	struct __btf_type type;
};

For a type with one metadata element, the representation looks like
this:

struct __BTF_KIND_META_ARRAY {
	__u32 type;
	__u32 index_type;
	__u32 nelems;
};

struct __BTF_KIND_ARRAY {
	struct __btf_type type;
	struct __BTF_KIND_META_ARRAY meta[1];
};

For a type with an info.vlen-determined number of following metadata
objects, a zero-length array is used:

struct __BTF_KIND_STRUCT {
	struct __btf_type type;
	struct __BTF_KIND_META_STRUCT meta[0];
};

In order to link kind numeric kind values to the appropriate struct,
a typedef is added; for example:

typedef struct __BTF_KIND_INT __BTF_KIND_1;

When BTF parsing encounters a kind that is not known, the
typedef __BTF_KIND_<kind number> is looked up, and we find which
struct type id it points to.  So

	1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT

This approach is preferred, since it ensures the structs representing
BTF kinds have names which match their associated kind rather than
an opaque number.

From there, BTF parsing can look up that struct and determine
	- its basic size;
	- if it has metadata; and if so
	- how many array instances are present;
		- if 0, we know it is a vlen-determined number;
		  i.e. vlen * meta_size
		- if > 0, simply use the overall struct size;

Based upon that information, BTF parsing can proceed for such
unknown kinds, since sufficient information was provided
at encoding time to skip over them.

Note that this assumes that the above kind-related data
structures are represented in BTF _prior_ to any kinds that
are new to the parser.  It also assumes the basic kinds
required to represent kinds + metadata; base types, structs,
arrays, etc.

Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
---
 tools/lib/bpf/btf.c      | 281 +++++++++++++++++++++++++++++++++++++++++++++++
 tools/lib/bpf/btf.h      |  10 ++
 tools/lib/bpf/libbpf.map |   1 +
 3 files changed, 292 insertions(+)

diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index 71e165b..e3cea44 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -28,6 +28,16 @@
 
 static struct btf_type btf_void;
 
+/* info used to encode/decode an unrecognized kind */
+struct btf_kind_desc {
+	int kind;
+	const char *struct_name;	/* __BTF_KIND_ARRAY */
+	const char *typedef_name;	/* __BTF_KIND_2 */
+	const char *meta_name;		/* __BTF_KIND_META_ARRAY */
+	int nr_meta;
+	int meta_size;
+};
+
 struct btf {
 	/* raw BTF data in native endianness */
 	void *raw_data;
@@ -5011,3 +5021,274 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void
 
 	return 0;
 }
+
+/* Here we use BTF to encode the BTF kinds that are known at the time of
+ * BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
+ * to describe each kind and any associated metadata allows BTF parsing
+ * to handle new kinds that the parser (in libbpf or the kernel) does
+ * not know about.  These kinds will not be used, but since we know
+ * their format they can be skipped over and the rest of the BTF can
+ * be parsed.  This means we can encode BTF without worrying about the
+ * kinds a BTF parser knows about, and means we can avoid using
+ * --skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
+ * everything it can, something as simple as a libbpf package update
+ * then unlocks that encodeded information, whereas if we encode
+ * pessimistically and drop representations of new kinds, this is not
+ * possible.
+ *
+ * So, in short, by carrying a representation of all the kinds encoded,
+ * parsers can parse all of the encoded kinds, even if they cannot use
+ * them all.
+ *
+ * We use BTF itself to carry this representation because this approach
+ * does not require BTF parsing to understand a new BTF header format;
+ * BTF parsing simply sees some additional types it does not do anything
+ * with.  A BTF parser that knows about the encoding of kind information
+ * however can use this information in parsing.
+ *
+ * The process works by explicitly adding btf structs for each kind.
+ * Each struct consists of a struct __btf_type followed by an array of
+ * metadata structs representing the following metadata (for those kinds
+ * that have it).  For kinds where a single metadata structure is used,
+ * the metadata array has one element.  For kinds where the number
+ * of metadata elements varies as per the info.vlen field, a zero-element
+ * array is encoded.
+ *
+ * For a given kind, we add a struct __BTF_KIND_<kind>.  For example,
+ *
+ * struct __BTF_KIND_INT {
+ *	struct __btf_type type;
+ * };
+ *
+ * For a type with one metadata element, the representation looks like
+ * this:
+ *
+ * struct __BTF_KIND_META_ARRAY {
+ *	__u32 type;
+ *	__u32 index_type;
+ *	__u32  nelems;
+ * };
+ *
+ * struct __BTF_KIND_ARRAY {
+ *	struct __btf_type type;
+ *	struct __BTF_KIND_META_ARRAY meta[1];
+ * };
+ *
+ *
+ * For a type with an info.vlen-determined number of following metadata
+ * objects, a zero-length array is used:
+ *
+ * struct __BTF_KIND_STRUCT {
+ *	struct __btf_type type;
+ *	struct __BTF_KIND_META_STRUCT meta[0];
+ * };
+ *
+ * In order to link kind numeric kind values to the appropriate struct,
+ * a typedef is added; for example:
+ *
+ * typedef struct __BTF_KIND_INT __BTF_KIND_1;
+ *
+ * When BTF parsing encounters a kind that is not known, the
+ * typedef __BTF_KIND_<kind number> is looked up, and we find which
+ * struct type id it points to.  So
+ *
+ *	1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT
+ *
+ * This approach is preferred, since it ensures the structs representing
+ * BTF kinds have names which match their associated kind rather than
+ * an opaque number.
+ *
+ * From there, BTF parsing can look up that struct and determine
+ *	- its basic size;
+ *	- if it has metadata; and if so
+ *	- how many array instances are present;
+ *		- if 0, we know it is a vlen-determined number;
+ *		- if > 0, simply use the overall struct size;
+ *
+ * Based upon that information, BTF parsing can proceed for such
+ * unknown kinds, since sufficient information was provided
+ * at encoding time.
+ *
+ * Note that this assumes that the above kind-related data
+ * structures are represented in BTF _prior_ to any kinds that
+ * are new to the parser.  It also assumes the basic kinds
+ * required to represent kinds + metadata; base types, structs,
+ * arrays, etc.
+ */
+
+/* info used to encode a kind metadata field */
+struct btf_meta_field {
+	const char *type;
+	const char *name;
+	int size;
+	int type_id;
+};
+
+#define BTF_MAX_META_FIELDS             10
+
+#define BTF_META_FIELD(__type, __name)					\
+	{ .type = #__type, .name = #__name, .size = sizeof(__type) }
+
+#define BTF_KIND_STR(__kind)	#__kind
+
+struct btf_kind_encoding {
+	struct btf_kind_desc kind;
+	struct btf_meta_field meta[BTF_MAX_META_FIELDS];
+};
+
+#define BTF_KIND(__name, __nr_meta, __meta_size, ...)			\
+	{ .kind = {							\
+	  .kind = BTF_KIND_##__name,					\
+	  .struct_name = BTF_KIND_PFX#__name,				\
+	  .meta_name = BTF_KIND_META_PFX #__name,			\
+	  .nr_meta = __nr_meta,						\
+	  .meta_size = __meta_size,					\
+	}, .meta = { __VA_ARGS__ } }
+
+struct btf_kind_encoding kinds[] = {
+	BTF_KIND(UNKN,		0,	0),
+
+	BTF_KIND(INT,		0,	0),
+
+	BTF_KIND(PTR,		0,	0),
+
+	BTF_KIND(ARRAY,		1,	sizeof(struct btf_array),
+					BTF_META_FIELD(__u32, type),
+					BTF_META_FIELD(__u32, index_type),
+					BTF_META_FIELD(__u32, nelems)),
+
+	BTF_KIND(STRUCT,	0,	sizeof(struct btf_member),
+					BTF_META_FIELD(__u32, name_off),
+					BTF_META_FIELD(__u32, type),
+					BTF_META_FIELD(__u32, offset)),
+
+	BTF_KIND(UNION,		0,	sizeof(struct btf_member),
+					BTF_META_FIELD(__u32, name_off),
+					BTF_META_FIELD(__u32, type),
+					BTF_META_FIELD(__u32, offset)),
+
+	BTF_KIND(ENUM,		0,	sizeof(struct btf_enum),
+					BTF_META_FIELD(__u32, name_off),
+					BTF_META_FIELD(__s32, val)),
+
+	BTF_KIND(FWD,		0,	0),
+
+	BTF_KIND(TYPEDEF,	0,	0),
+
+	BTF_KIND(VOLATILE,	0,	0),
+
+	BTF_KIND(CONST,		0,	0),
+
+	BTF_KIND(RESTRICT,	0,	0),
+
+	BTF_KIND(FUNC,		0,	0),
+
+	BTF_KIND(FUNC_PROTO,	0,	sizeof(struct btf_param),
+					BTF_META_FIELD(__u32, name_off),
+					BTF_META_FIELD(__u32, type)),
+
+	BTF_KIND(VAR,		1,	sizeof(struct btf_var),
+					BTF_META_FIELD(__u32, linkage)),
+
+	BTF_KIND(DATASEC,	0,	sizeof(struct btf_var_secinfo),
+					BTF_META_FIELD(__u32, type),
+					BTF_META_FIELD(__u32, offset),
+					BTF_META_FIELD(__u32, size)),
+
+
+	BTF_KIND(FLOAT,		0,	0),
+
+	BTF_KIND(DECL_TAG,	1,	sizeof(struct btf_decl_tag),
+					BTF_META_FIELD(__s32, component_idx)),
+
+	BTF_KIND(TYPE_TAG,	0,	0),
+
+	BTF_KIND(ENUM64,	0,	sizeof(struct btf_enum64),
+					BTF_META_FIELD(__u32, name_off),
+					BTF_META_FIELD(__u32, val_lo32),
+					BTF_META_FIELD(__u32, val_hi32)),
+};
+
+/* Try to add representations of the kinds supported to BTF provided.  This will allow parsers
+ * to decode kinds they do not support and skip over them.
+ */
+int btf__add_kinds(struct btf *btf)
+{
+	int btf_type_id, __u32_id, __s32_id, struct_type_id;
+	char name[64];
+	int i;
+
+	/* should have base types; if not bootstrap them. */
+	__u32_id = btf__find_by_name(btf, "__u32");
+	if (__u32_id < 0) {
+		__s32 unsigned_int_id = btf__find_by_name(btf, "unsigned int");
+
+		if (unsigned_int_id < 0)
+			unsigned_int_id = btf__add_int(btf, "unsigned int", 4, 0);
+		__u32_id = btf__add_typedef(btf, "__u32", unsigned_int_id);
+	}
+	__s32_id = btf__find_by_name(btf, "__s32");
+	if (__s32_id < 0) {
+		__s32 int_id = btf__find_by_name_kind(btf, "int", BTF_KIND_INT);
+
+		if (int_id < 0)
+			int_id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
+		__s32_id = btf__add_typedef(btf, "__s32", int_id);
+	}
+
+	/* add "struct __btf_type" if not already present. */
+	btf_type_id = btf__find_by_name(btf, "__btf_type");
+	if (btf_type_id < 0) {
+		__s32 union_id = btf__add_union(btf, NULL, sizeof(__u32));
+
+		btf__add_field(btf, "size", __u32_id, 0, 0);
+		btf__add_field(btf, "type", __u32_id, 0, 0);
+
+		btf_type_id = btf__add_struct(btf, "__btf_type", sizeof(struct btf_type));
+		btf__add_field(btf, "name_off", __u32_id, 0, 0);
+		btf__add_field(btf, "info", __u32_id, sizeof(__u32) * 8, 0);
+		btf__add_field(btf, NULL, union_id, sizeof(__u32) * 16, 0);
+	}
+
+	for (i = 0; i < ARRAY_SIZE(kinds); i++) {
+		struct btf_kind_encoding *kind = &kinds[i];
+		int meta_id, array_id = 0;
+
+		if (btf__find_by_name(btf, kind->kind.struct_name) > 0)
+			continue;
+
+		if (kind->kind.meta_size != 0) {
+			struct btf_meta_field *field;
+			__u32 bit_offset = 0;
+			int j;
+
+			meta_id = btf__add_struct(btf, kind->kind.meta_name, kind->kind.meta_size);
+
+			for (j = 0; bit_offset < kind->kind.meta_size * 8; j++) {
+				field = &kind->meta[j];
+
+				field->type_id = btf__find_by_name(btf, field->type);
+				if (field->type_id < 0) {
+					pr_debug("cannot find type '%s' for kind '%s' field '%s'\n",
+						 kind->meta[j].type, kind->kind.struct_name,
+						 kind->meta[j].name);
+				} else {
+					btf__add_field(btf, field->name, field->type_id, bit_offset, 0);
+				}
+				bit_offset += field->size * 8;
+			}
+			array_id = btf__add_array(btf, __u32_id, meta_id,
+						  kind->kind.nr_meta);
+
+		}
+		struct_type_id = btf__add_struct(btf, kind->kind.struct_name,
+						 sizeof(struct btf_type) +
+						 (kind->kind.nr_meta * kind->kind.meta_size));
+		btf__add_field(btf, "type", btf_type_id, 0, 0);
+		if (kind->kind.meta_size != 0)
+			btf__add_field(btf, "meta", array_id, sizeof(struct btf_type) * 8, 0);
+		snprintf(name, sizeof(name), BTF_KIND_PFX "%u", i);
+		btf__add_typedef(btf, name, struct_type_id);
+	}
+	return 0;
+}
diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
index 8e6880d..a054082 100644
--- a/tools/lib/bpf/btf.h
+++ b/tools/lib/bpf/btf.h
@@ -219,6 +219,16 @@ LIBBPF_API int btf__add_datasec_var_info(struct btf *btf, int var_type_id,
 LIBBPF_API int btf__add_decl_tag(struct btf *btf, const char *value, int ref_type_id,
 			    int component_idx);
 
+/**
+ * @brief **btf__add_kinds()** adds BTF representations of the kind encoding for
+ * all of the kinds known to libbpf.  This ensures that when BTF is encoded, it
+ * will include enough information for parsers to decode (and skip over) kinds
+ * that the parser does not know about yet.  This ensures that an older BTF
+ * parser can read newer BTF, and avoids the need for the BTF encoder to limit
+ * which kinds it emits to make decoding easier.
+ */
+LIBBPF_API int btf__add_kinds(struct btf *btf);
+
 struct btf_dedup_opts {
 	size_t sz;
 	/* optional .BTF.ext info to dedup along the main BTF info */
diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
index 71bf569..6121ff1 100644
--- a/tools/lib/bpf/libbpf.map
+++ b/tools/lib/bpf/libbpf.map
@@ -375,6 +375,7 @@ LIBBPF_1.1.0 {
 		bpf_link_get_fd_by_id_opts;
 		bpf_map_get_fd_by_id_opts;
 		bpf_prog_get_fd_by_id_opts;
+		btf__add_kinds;
 		user_ring_buffer__discard;
 		user_ring_buffer__free;
 		user_ring_buffer__new;
-- 
1.8.3.1

[RFC bpf-next 3/5] libbpf: use BTF-encoded kind information to help parse unrecognized kinds

[Alan Maguire]

btf__add_kinds() adds typedef/struct representations of the kinds supported
at BTF encoding time.  When decoding/parsing, we can then use information
about unrecognized kinds to skip over them.  This will be useful if the
BTF encoder encoded info using a new kind, but the parser doesn't support
it yet.

Note that only size determinations of unrecognized kinds are supported;
lookup, dedup and other features are not supported; the aim here is to
not break BTF parsing if newer kinds are encountered.

Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
---
 tools/lib/bpf/btf.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)

diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
index e3cea44..da719de 100644
--- a/tools/lib/bpf/btf.c
+++ b/tools/lib/bpf/btf.c
@@ -28,6 +28,8 @@
 
 static struct btf_type btf_void;
 
+#define NR_BTF_KINDS_POSSIBLE	0x20
+
 /* info used to encode/decode an unrecognized kind */
 struct btf_kind_desc {
 	int kind;
@@ -131,6 +133,9 @@ struct btf {
 
 	/* Pointer size (in bytes) for a target architecture of this BTF */
 	int ptr_sz;
+
+	/* representations of unrecognized kinds are stored here */
+	struct btf_kind_desc unrecognized_kinds[NR_BTF_KINDS_POSSIBLE - NR_BTF_KINDS];
 };
 
 static inline __u64 ptr_to_u64(const void *ptr)
@@ -420,6 +425,75 @@ static int btf_bswap_type_rest(struct btf_type *t)
 	}
 }
 
+static int btf_unrecognized_kind_type_size(struct btf *btf, const struct btf_type *t)
+{
+	struct btf_kind_desc *unrec_kind = NULL;
+	__u16 kind = btf_kind(t);
+	int size = 0;
+
+	if (kind >= NR_BTF_KINDS && kind < NR_BTF_KINDS_POSSIBLE)
+		unrec_kind = &btf->unrecognized_kinds[kind - NR_BTF_KINDS];
+	if (!unrec_kind) {
+		pr_debug("No information about unrecognized kind:%u\n", kind);
+		return -EINVAL;
+	}
+
+	if (unrec_kind->kind != kind) {
+		const char *kind_struct_name;
+		const struct btf_type *kt;
+		const struct btf_member *m;
+		const struct btf_array *a;
+		char typedef_name[64];
+		__s32 id;
+
+		/* we need to fill in information on this kind; it will be cached in struct btf
+		 * for subsequent references.
+		 */
+		snprintf(typedef_name, sizeof(typedef_name), BTF_KIND_PFX "%u", kind);
+		id = btf__find_by_name_kind(btf, typedef_name, BTF_KIND_TYPEDEF);
+		if (id < 0)
+			return id;
+		kt = btf__type_by_id(btf, id);
+		kt = btf__type_by_id(btf, kt->type);
+		kind_struct_name = btf__str_by_offset(btf, kt->name_off);
+		/* struct should contain type + optional meta fields; otherwise unsupported */
+		switch (btf_vlen(kt)) {
+		case 1:
+			unrec_kind->nr_meta = 0;
+			unrec_kind->meta_size = 0;
+			break;
+		case 2:
+			m = btf_members(kt);
+			kt = btf__type_by_id(btf, (++m)->type);
+			if (btf_kind(kt) != BTF_KIND_ARRAY) {
+				pr_debug("Unexpected kind %u for member in '%s'\n",
+					 btf_kind(kt), kind_struct_name);
+				return -EINVAL;
+			}
+			a = btf_array(kt);
+			unrec_kind->nr_meta = a->nelems;
+			kt = btf__type_by_id(btf, a->type);
+			unrec_kind->meta_size = kt->size;
+			unrec_kind->meta_name = btf__str_by_offset(btf, kt->name_off);
+			break;
+		default:
+			pr_debug("unexpected nr of fields for '%s'(%u)\n", kind_struct_name,
+				 kind);
+			return -EINVAL;
+		}
+		unrec_kind->kind = kind;
+		unrec_kind->struct_name = kind_struct_name;
+	}
+	size = sizeof(struct btf_type);
+	if (unrec_kind->meta_size > 0) {
+		if (unrec_kind->nr_meta == 0)
+			size += btf_vlen(t) * unrec_kind->meta_size;
+		else
+			size += unrec_kind->nr_meta * unrec_kind->meta_size;
+	}
+	return size;
+}
+
 static int btf_parse_type_sec(struct btf *btf)
 {
 	struct btf_header *hdr = btf->hdr;
@@ -433,6 +507,8 @@ static int btf_parse_type_sec(struct btf *btf)
 
 		type_size = btf_type_size(next_type);
 		if (type_size < 0)
+			type_size = btf_unrecognized_kind_type_size(btf, next_type);
+		if (type_size < 0)
 			return type_size;
 		if (next_type + type_size > end_type) {
 			pr_warn("BTF type [%d] is malformed\n", btf->start_id + btf->nr_types);
-- 
1.8.3.1

[RFC bpf-next 4/5] bpf: parse unrecognized kind info using encoded kind information (if present)

[Alan Maguire]

When BTF parsing encounters an unrecognized kind (> BTF_KIND_MAX), look
for __BTF_KIND_<num> typedef which points at the associated kind struct;
it tells us if there is metadata and how much.  This all allows us to
proceed with BTF parsing rather than bailing when hitting a kind we
do not support.

Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
---
 kernel/bpf/btf.c | 87 +++++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 80 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 1a59cc7..ce00a4c5 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -222,6 +222,14 @@ struct btf_id_dtor_kfunc_tab {
 	struct btf_id_dtor_kfunc dtors[];
 };
 
+struct btf_kind_desc {
+	u16 kind;
+	u16 nr_meta;
+	u32 meta_size;
+};
+
+#define NR_BTF_KINDS_POSSIBLE	0x20
+
 struct btf {
 	void *data;
 	struct btf_type **types;
@@ -246,6 +254,7 @@ struct btf {
 	u32 start_str_off; /* first string offset (0 for base BTF) */
 	char name[MODULE_NAME_LEN];
 	bool kernel_btf;
+	struct btf_kind_desc unrecognized_kinds[NR_BTF_KINDS_POSSIBLE - NR_BTF_KINDS];
 };
 
 enum verifier_phase {
@@ -4873,7 +4882,7 @@ static s32 btf_check_meta(struct btf_verifier_env *env,
 			  u32 meta_left)
 {
 	u32 saved_meta_left = meta_left;
-	s32 var_meta_size;
+	s32 var_meta_size = 0;
 
 	if (meta_left < sizeof(*t)) {
 		btf_verifier_log(env, "[%u] meta_left:%u meta_needed:%zu",
@@ -4888,12 +4897,80 @@ static s32 btf_check_meta(struct btf_verifier_env *env,
 		return -EINVAL;
 	}
 
-	if (BTF_INFO_KIND(t->info) > BTF_KIND_MAX ||
-	    BTF_INFO_KIND(t->info) == BTF_KIND_UNKN) {
+	if (BTF_INFO_KIND(t->info) == BTF_KIND_UNKN ||
+	    BTF_INFO_KIND(t->info) >= NR_BTF_KINDS_POSSIBLE) {
 		btf_verifier_log(env, "[%u] Invalid kind:%u",
 				 env->log_type_id, BTF_INFO_KIND(t->info));
 		return -EINVAL;
 	}
+	if (BTF_INFO_KIND(t->info) <= BTF_KIND_MAX) {
+		var_meta_size = btf_type_ops(t)->check_meta(env, t, meta_left);
+		if (var_meta_size < 0)
+			return var_meta_size;
+	} else {
+		struct btf_kind_desc *unrec_kind;
+		u8 kind = BTF_INFO_KIND(t->info);
+		struct btf *btf = env->btf;
+
+		unrec_kind = &btf->unrecognized_kinds[kind - NR_BTF_KINDS];
+
+		if (unrec_kind->kind != kind) {
+			const struct btf_member *m;
+			const struct btf_type *kt;
+			const struct btf_array *a;
+			char name[64];
+			s32 id;
+
+			/* BTF may encode info about unrecognized kinds; check for this here. */
+			snprintf(name, sizeof(name), BTF_KIND_PFX "%u", kind);
+			id = btf_find_by_name_kind(btf, name, BTF_KIND_TYPEDEF);
+			if (id > 0) {
+				kt = btf_type_by_id(btf, id);
+				if (kt)
+					kt = btf_type_by_id(btf, kt->type);
+			}
+			if (id < 0 || !kt) {
+				btf_verifier_log_type(env, t, "[%u] invalid kind:%u",
+						      env->log_type_id, kind);
+				return -EINVAL;
+			}
+			switch (btf_type_vlen(kt)) {
+			case 1:
+				/* no metadata */
+				unrec_kind->kind = kind;
+				unrec_kind->nr_meta = 0;
+				unrec_kind->meta_size = 0;
+				break;
+			case 2:
+				m = btf_members(kt);
+				kt = btf_type_by_id(btf, (++m)->type);
+				if (btf_kind(kt) != BTF_KIND_ARRAY) {
+					btf_verifier_log_type(env, t, "[%u] invalid metadata:%u",
+							      env->log_type_id, kind);
+					return -EINVAL;
+				}
+				a = btf_array(kt);
+				kt = btf_type_by_id(btf, a->type);
+				if (!kt) {
+					btf_verifier_log_type(env, t, "[%u] invalid metadata:%u",
+							      env->log_type_id, kind);
+					return -EINVAL;
+				}
+				unrec_kind->kind = kind;
+				unrec_kind->nr_meta = a->nelems;
+				unrec_kind->meta_size = kt->size;
+				break;
+			default:
+				btf_verifier_log_type(env, t, "[%u] invalid metadata:%u",
+						      env->log_type_id, kind);
+				return -EINVAL;
+			}
+		}
+		if (!unrec_kind->nr_meta)
+			var_meta_size = btf_type_vlen(t) * unrec_kind->meta_size;
+		else
+			var_meta_size = unrec_kind->nr_meta * unrec_kind->meta_size;
+	}
 
 	if (!btf_name_offset_valid(env->btf, t->name_off)) {
 		btf_verifier_log(env, "[%u] Invalid name_offset:%u",
@@ -4901,10 +4978,6 @@ static s32 btf_check_meta(struct btf_verifier_env *env,
 		return -EINVAL;
 	}
 
-	var_meta_size = btf_type_ops(t)->check_meta(env, t, meta_left);
-	if (var_meta_size < 0)
-		return var_meta_size;
-
 	meta_left -= var_meta_size;
 
 	return saved_meta_left - meta_left;
-- 
1.8.3.1

[RFC bpf-next 5/5] selftests/bpf: test kind encoding/decoding

[Alan Maguire]

verify btf__add_kinds() adds kind encodings for all kinds supported,
and after adding kind-related types for unknown kinds, ensure that
parsing uses this info when those kinds are encountered rather than
giving up.

Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
---
 tools/testing/selftests/bpf/prog_tests/btf_kind.c | 234 ++++++++++++++++++++++
 1 file changed, 234 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/btf_kind.c

diff --git a/tools/testing/selftests/bpf/prog_tests/btf_kind.c b/tools/testing/selftests/bpf/prog_tests/btf_kind.c
new file mode 100644
index 0000000..e0865ab
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/btf_kind.c
@@ -0,0 +1,234 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2022, Oracle and/or its affiliates. */
+
+#include <test_progs.h>
+#include <bpf/btf.h>
+#include <bpf/libbpf.h>
+
+/* verify kind encoding exists for each kind; ensure it consists of a
+ * typedef __BTF_KIND_<num> pointing at a struct __BTF_KIND_<name>,
+ * and the latter has a struct btf_type field and an optional metadata
+ * field.
+ */
+void test_btf_kind_encoding(struct btf *btf)
+{
+	int type_cnt;
+	__u16 i;
+
+	type_cnt = btf__type_cnt(btf);
+	if (!ASSERT_GT(type_cnt, 0, "check_type_cnt"))
+		return;
+
+	for (i = 0; i <= BTF_KIND_MAX; i++) {
+		const struct btf_type *t, *mt;
+		const struct btf_array *a;
+		struct btf_member *m;
+		char name[64];
+		__s32 tid;
+
+		snprintf(name, sizeof(name), BTF_KIND_PFX"%u", i);
+
+		tid = btf__find_by_name(btf, name);
+
+		if (!ASSERT_GT(tid, 0, "find_typedef"))
+			continue;
+
+		t = btf__type_by_id(btf, tid);
+		if (!ASSERT_OK_PTR(t, "typedef_ptr"))
+			continue;
+		t = btf__type_by_id(btf, t->type);
+		if (!ASSERT_OK_PTR(t, "struct_ptr"))
+			continue;
+		if (!ASSERT_EQ(strncmp(btf__name_by_offset(btf, t->name_off),
+				       BTF_KIND_PFX,
+				       strlen(BTF_KIND_PFX)),
+			      0, "check_struct_name"))
+			continue;
+		if (!ASSERT_GT(btf_vlen(t), 0, "check_struct_vlen"))
+			continue;
+		m = btf_members(t);
+		mt = btf__type_by_id(btf, m->type);
+		if (!ASSERT_EQ(btf_kind(mt), BTF_KIND_STRUCT, "member_kind"))
+			continue;
+		if (!ASSERT_EQ(strcmp(btf__name_by_offset(btf, mt->name_off),
+				      "__btf_type"), 0, "member_type_name"))
+			continue;
+		if (btf_vlen(t) == 1)
+			continue;
+		m++;
+		mt = btf__type_by_id(btf, m->type);
+		if (!ASSERT_EQ(btf_kind(mt), BTF_KIND_ARRAY, "member_kind"))
+			continue;
+		a = btf_array(mt);
+		mt = btf__type_by_id(btf, a->type);
+		if (!ASSERT_EQ(strncmp(btf__name_by_offset(btf, mt->name_off),
+				       BTF_KIND_META_PFX,
+				       strlen(BTF_KIND_META_PFX)), 0,
+			       "check_meta_name"))
+			continue;
+	}
+}
+
+static __s32 add_kind(struct btf *btf, __u16 unrec_kind, int nr_meta, int meta_size)
+{
+	__s32 btf_type_id, id, struct_id, array_id;
+	char name[64];
+	int ret;
+
+	/* fabricate unrecognized kind definitions that will be used
+	 * when we add a type using the unrecognized kind later.
+	 */
+	btf_type_id = btf__find_by_name_kind(btf, "__btf_type", BTF_KIND_STRUCT);
+	if (!ASSERT_GT(btf_type_id, 0, "check_btf_type_id"))
+		return btf_type_id;
+
+	if (meta_size > 0) {
+		__s32 __u32_id;
+
+		__u32_id = btf__find_by_name(btf, "__u32");
+		if (!ASSERT_GT(__u32_id, 0, "find_u32"))
+			return __u32_id;
+
+		array_id = btf__add_array(btf, __u32_id, btf_type_id, nr_meta);
+		if (!ASSERT_GT(array_id, 0, "btf__add_array"))
+			return array_id;
+	}
+
+	snprintf(name, sizeof(name), BTF_KIND_PFX "UNREC%d", unrec_kind);
+	struct_id = btf__add_struct(btf, name, sizeof(struct btf_type) + (nr_meta * meta_size));
+	if (!ASSERT_GT(struct_id, 0, "check_struct_id"))
+		return struct_id;
+
+	ret = btf__add_field(btf, "type", btf_type_id, 0, 0);
+	if (!ASSERT_EQ(ret, 0, "btf__add_field"))
+		return ret;
+	if (meta_size > 0) {
+		ret = btf__add_field(btf, "meta", array_id, 96, 0);
+		if (!ASSERT_EQ(ret, 0, "btf__add_field_meta"))
+			return ret;
+	}
+	snprintf(name, sizeof(name), BTF_KIND_PFX "%u", unrec_kind);
+	id = btf__add_typedef(btf, name, struct_id);
+	if (!ASSERT_GT(id, 0, "btf__add_typedef"))
+		return id;
+
+	return btf_type_id;
+}
+
+/* fabricate unrecognized kinds at BTF_KIND_MAX + 1/2/3, and after adding
+ * the appropriate struct/typedefs to the BTF such that it recognizes
+ * these kinds, ensure that parsing of BTF containing the unrecognized kinds
+ * can succeed.
+ */
+void test_btf_kind_decoding(struct btf *btf)
+{
+	const struct btf_type *old_unrecs[6];
+	__s32 id, btf_type_id, unrec_ids[6];
+	__u16 unrec_kind = BTF_KIND_MAX + 1;
+	struct btf_type *new_unrecs[6];
+	const void *raw_data;
+	struct btf *raw_btf;
+	char btf_path[64];
+	__u32 raw_size;
+	int i, fd;
+
+	/* fabricate unrecognized kind definitions that will be used
+	 * when we add a type using the unrecognized kind later.
+	 *
+	 * Kinds are created with
+	 * - no metadata;
+	 * - a single metadata object
+	 * - a vlen-determined number of metadata objects.
+	 */
+	btf_type_id = add_kind(btf, unrec_kind, 0, 0);
+	if (!ASSERT_GT(btf_type_id, 0, "add_kind1"))
+		return;
+	if (!ASSERT_GT(add_kind(btf, unrec_kind + 1, 1, sizeof(struct btf_type)), 0, "add_kind2"))
+		return;
+	if (!ASSERT_GT(add_kind(btf, unrec_kind + 2, 0, sizeof(struct btf_type)), 0, "add_kind3"))
+		return;
+
+	/* now create our types with unrecognized kinds by adding typedef kinds
+	 * and overwriting them with our unrecognized kind values.
+	 */
+	for (i = 0; i < ARRAY_SIZE(unrec_ids); i++) {
+		char name[64];
+
+		snprintf(name, sizeof(name), "unrec_kind%d", i);
+		unrec_ids[i] = btf__add_typedef(btf, name, btf_type_id);
+		if (!ASSERT_GT(unrec_ids[i], 0, "btf__add_typedef"))
+			return;
+		old_unrecs[i] = btf__type_by_id(btf, unrec_ids[i]);
+		if (!ASSERT_OK_PTR(old_unrecs[i], "check_unrec_ptr"))
+			return;
+		new_unrecs[i] = (struct btf_type *)old_unrecs[i];
+	}
+
+	/* add an id after it that we will look up to verify we can parse
+	 * beyond unrecognized kinds.
+	 */
+	id = btf__add_typedef(btf, "test_lookup", btf_type_id);
+	if (!ASSERT_GT(id, 0, "add_test_lookup_id"))
+		return;
+	/* ...but because we converted two BTF types into metadata, the id
+	 * for lookup after modification will be two less.
+	 */
+	id -= 2;
+
+	/* now modify typedefs added above to become unrecognized kinds */
+	new_unrecs[0]->info = (unrec_kind << 24);
+
+	/* unrecognized kind with 1 metadata object */
+	new_unrecs[1]->info = ((unrec_kind + 1) << 24);
+
+	/* unrecognized kind with vlen-determined number of metadata objects; vlen == 1 here */
+	new_unrecs[3]->info = ((unrec_kind + 2) << 24) | 0x1;
+
+	/* having another instance of the unrecognized kind allows us to test
+	 * the caching codepath; we store unrecognized kind data the
+	 * first time we encounter one to avoid the cost of typedef/struct
+	 * lookups each time an unrecognized kind is seen.
+	 */
+	new_unrecs[5]->info = (unrec_kind << 24);
+	/* now write our BTF to a raw file, ready for parsing. */
+	snprintf(btf_path, sizeof(btf_path), "/tmp/btf_kind.%d", getpid());
+	raw_data = btf__raw_data(btf, &raw_size);
+	if (!ASSERT_OK_PTR(raw_data, "check_raw_data"))
+		return;
+	fd = open(btf_path, O_WRONLY | O_CREAT);
+	write(fd, raw_data, raw_size);
+	close(fd);
+
+	/* verify parsing succeeds, and that we can read type info past
+	 * the unrecognized kind.
+	 */
+	raw_btf = btf__parse_raw(btf_path);
+	if (!ASSERT_OK_PTR(raw_btf, "btf__parse_raw"))
+		goto unlink;
+	ASSERT_EQ(btf__find_by_name_kind(raw_btf, "test_lookup",
+					 BTF_KIND_TYPEDEF), id,
+		  "verify_id_lookup");
+
+	/* finally, verify the kernel can handle unrecognized kinds. */
+	ASSERT_EQ(btf__load_into_kernel(raw_btf), 0, "btf_load_into_kernel");
+unlink:
+	unlink(btf_path);
+}
+
+void test_btf_kind(void)
+{
+	struct btf *btf = btf__new_empty();
+
+	if (!ASSERT_OK_PTR(btf, "btf_new"))
+		return;
+
+	if (!ASSERT_OK(btf__add_kinds(btf), "btf__add_kinds"))
+		goto cleanup;
+
+	if (test__start_subtest("btf_kind_encoding"))
+		test_btf_kind_encoding(btf);
+	if (test__start_subtest("btf_kind_decoding"))
+		test_btf_kind_decoding(btf);
+cleanup:
+	btf__free(btf);
+}
-- 
1.8.3.1

Re: [RFC bpf-next 2/5] libbpf: provide libbpf API to encode BTF kind information

[Andrii Nakryiko]

On Wed, Nov 23, 2022 at 9:42 AM Alan Maguire <alan.maguire@oracle.com> wrote:
>
> This can be used by BTF parsers to handle kinds they do not know about;
> this is useful when the encoding libbpf is more recent than the parsing
> BTF; the parser can then skip over the encoded types it does not know
> about.
>
> We use BTF to encode the BTF kinds that are known at the time of
> BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
> to describe each kind and any associated metadata allows BTF parsing
> to handle new kinds that the parser (in libbpf or the kernel) does
> not know about.  These kinds will not be used, but since we know
> their format they can be skipped over and the rest of the BTF can
> be parsed.  This means we can encode BTF without worrying about the
> kinds a BTF parser knows about, and means we can avoid using
> --skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
> everything it can, something as simple as a libbpf package update
> then unlocks that encoded information, whereas if we encode
> pessimistically and drop representations of new kinds, this is not
> possible.
>
> So, in short, by carrying a representation of all the kinds encoded,
> parsers can parse all of the encoded kinds, even if they cannot use
> them all.
>
> We use BTF itself to carry this representation because this approach
> does not require BTF parsing to understand a new BTF header format;
> BTF parsing simply sees some additional types it does not do anything
> with.  However, a BTF parser that knows about the encoding of kind
> information can use this information to guide parsing.
>
> The process works by explicitly adding btf structs for each kind.
> Each struct consists of a "struct __btf_type" followed by an array of
> metadata structs representing the following metadata (for those kinds
> that have it).  For kinds where a single metadata structure is used,
> the metadata array has one element.  For kinds where the number
> of metadata elements varies as per the info.vlen field, a zero-element
> array is encoded.
>
> For a given kind, we add a struct __BTF_KIND_<kind>.  For example,
>
> struct __BTF_KIND_INT {
>         struct __btf_type type;
> };
>
> For a type with one metadata element, the representation looks like
> this:
>
> struct __BTF_KIND_META_ARRAY {
>         __u32 type;
>         __u32 index_type;
>         __u32 nelems;
> };
>
> struct __BTF_KIND_ARRAY {
>         struct __btf_type type;
>         struct __BTF_KIND_META_ARRAY meta[1];
> };
>
> For a type with an info.vlen-determined number of following metadata
> objects, a zero-length array is used:
>
> struct __BTF_KIND_STRUCT {
>         struct __btf_type type;
>         struct __BTF_KIND_META_STRUCT meta[0];
> };
>
> In order to link kind numeric kind values to the appropriate struct,
> a typedef is added; for example:
>
> typedef struct __BTF_KIND_INT __BTF_KIND_1;
>
> When BTF parsing encounters a kind that is not known, the
> typedef __BTF_KIND_<kind number> is looked up, and we find which
> struct type id it points to.  So
>
>         1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT
>
> This approach is preferred, since it ensures the structs representing
> BTF kinds have names which match their associated kind rather than
> an opaque number.
>
> From there, BTF parsing can look up that struct and determine
>         - its basic size;
>         - if it has metadata; and if so
>         - how many array instances are present;
>                 - if 0, we know it is a vlen-determined number;
>                   i.e. vlen * meta_size
>                 - if > 0, simply use the overall struct size;
>
> Based upon that information, BTF parsing can proceed for such
> unknown kinds, since sufficient information was provided
> at encoding time to skip over them.
>
> Note that this assumes that the above kind-related data
> structures are represented in BTF _prior_ to any kinds that
> are new to the parser.  It also assumes the basic kinds
> required to represent kinds + metadata; base types, structs,
> arrays, etc.
>
> Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
> ---
>  tools/lib/bpf/btf.c      | 281 +++++++++++++++++++++++++++++++++++++++++++++++
>  tools/lib/bpf/btf.h      |  10 ++
>  tools/lib/bpf/libbpf.map |   1 +
>  3 files changed, 292 insertions(+)
>
> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> index 71e165b..e3cea44 100644
> --- a/tools/lib/bpf/btf.c
> +++ b/tools/lib/bpf/btf.c
> @@ -28,6 +28,16 @@
>
>  static struct btf_type btf_void;
>
> +/* info used to encode/decode an unrecognized kind */
> +struct btf_kind_desc {
> +       int kind;
> +       const char *struct_name;        /* __BTF_KIND_ARRAY */
> +       const char *typedef_name;       /* __BTF_KIND_2 */
> +       const char *meta_name;          /* __BTF_KIND_META_ARRAY */
> +       int nr_meta;
> +       int meta_size;
> +};
> +
>  struct btf {
>         /* raw BTF data in native endianness */
>         void *raw_data;
> @@ -5011,3 +5021,274 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void
>
>         return 0;
>  }
> +
> +/* Here we use BTF to encode the BTF kinds that are known at the time of
> + * BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
> + * to describe each kind and any associated metadata allows BTF parsing
> + * to handle new kinds that the parser (in libbpf or the kernel) does
> + * not know about.  These kinds will not be used, but since we know
> + * their format they can be skipped over and the rest of the BTF can
> + * be parsed.  This means we can encode BTF without worrying about the
> + * kinds a BTF parser knows about, and means we can avoid using
> + * --skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
> + * everything it can, something as simple as a libbpf package update
> + * then unlocks that encodeded information, whereas if we encode
> + * pessimistically and drop representations of new kinds, this is not
> + * possible.
> + *
> + * So, in short, by carrying a representation of all the kinds encoded,
> + * parsers can parse all of the encoded kinds, even if they cannot use
> + * them all.
> + *
> + * We use BTF itself to carry this representation because this approach
> + * does not require BTF parsing to understand a new BTF header format;
> + * BTF parsing simply sees some additional types it does not do anything
> + * with.  A BTF parser that knows about the encoding of kind information
> + * however can use this information in parsing.
> + *
> + * The process works by explicitly adding btf structs for each kind.
> + * Each struct consists of a struct __btf_type followed by an array of
> + * metadata structs representing the following metadata (for those kinds
> + * that have it).  For kinds where a single metadata structure is used,
> + * the metadata array has one element.  For kinds where the number
> + * of metadata elements varies as per the info.vlen field, a zero-element
> + * array is encoded.
> + *
> + * For a given kind, we add a struct __BTF_KIND_<kind>.  For example,
> + *
> + * struct __BTF_KIND_INT {
> + *     struct __btf_type type;
> + * };
> + *
> + * For a type with one metadata element, the representation looks like
> + * this:
> + *
> + * struct __BTF_KIND_META_ARRAY {
> + *     __u32 type;
> + *     __u32 index_type;
> + *     __u32  nelems;
> + * };
> + *
> + * struct __BTF_KIND_ARRAY {
> + *     struct __btf_type type;
> + *     struct __BTF_KIND_META_ARRAY meta[1];
> + * };
> + *
> + *
> + * For a type with an info.vlen-determined number of following metadata
> + * objects, a zero-length array is used:
> + *
> + * struct __BTF_KIND_STRUCT {
> + *     struct __btf_type type;
> + *     struct __BTF_KIND_META_STRUCT meta[0];
> + * };
> + *
> + * In order to link kind numeric kind values to the appropriate struct,
> + * a typedef is added; for example:
> + *
> + * typedef struct __BTF_KIND_INT __BTF_KIND_1;
> + *
> + * When BTF parsing encounters a kind that is not known, the
> + * typedef __BTF_KIND_<kind number> is looked up, and we find which
> + * struct type id it points to.  So
> + *
> + *     1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT
> + *
> + * This approach is preferred, since it ensures the structs representing
> + * BTF kinds have names which match their associated kind rather than
> + * an opaque number.
> + *
> + * From there, BTF parsing can look up that struct and determine
> + *     - its basic size;
> + *     - if it has metadata; and if so
> + *     - how many array instances are present;
> + *             - if 0, we know it is a vlen-determined number;
> + *             - if > 0, simply use the overall struct size;
> + *
> + * Based upon that information, BTF parsing can proceed for such
> + * unknown kinds, since sufficient information was provided
> + * at encoding time.
> + *
> + * Note that this assumes that the above kind-related data
> + * structures are represented in BTF _prior_ to any kinds that
> + * are new to the parser.  It also assumes the basic kinds
> + * required to represent kinds + metadata; base types, structs,
> + * arrays, etc.
> + */

Goodness gracious! :)

Aesthetics of all this aside (which hurts me deeply, but let's ignore
that for a moment), this whole requirement that these
self-describing-but-also-convention-driven types which are supposed to
help with parsing types information are themselves in types
information is quite unusual. Yes, by saying "we assume they come
before a first type with unknown kind" we kind of work around this,
but even the fact that you can use btf__type_by_id() and
btf__find_by_name_kind() before BTF is fully parsed is kind of by
accident. All-in-all this screams "a kludge" at me, sorry.

I really don't like this approach, even if *technically* it would
work. But even if so, it would add quite a bunch of size to BTF just
to self-describe it.

Let's go again (and in more detail) over my alternative proposal I
briefly described in another email thread.

So, what I'm proposing is similar in spirit and solves all the same
goals you have (and actually some more, I'll point this out below).
The only downside is that we'll need to, again, teach kernel to
understand this BTF format extension to allow kernel to use it (so we
still will need an opt-in flag for pahole, unfortunately, but
hopefully just this one time). That's pretty much the only downside.
But it's more compact, simpler and more straightforward, more elegant
(IMO), and it is easy for libbpf to sanitize it for old kernels.

Ok, so it's pretty much completely described by these changes:

--- a/include/uapi/linux/btf.h
+++ b/include/uapi/linux/btf.h
@@ -8,6 +8,21 @@
 #define BTF_MAGIC      0xeB9F
 #define BTF_VERSION    1

+struct btf_kind_meta {
+       /* extra flags, initially define just one:
+        * 0x01 - required or optional (is it safe to skip if unknown)
+        */
+       __u16 flags;
+       __u8 info_sz;
+       __u8 elem_sz;
+};
+
+struct btf_metadata {
+       __u8 kind_meta_cnt;
+       __u32 :0;
+       struct btf_kind_meta[];
+};
+
 struct btf_header {
        __u16   magic;
        __u8    version;
@@ -19,6 +34,8 @@ struct btf_header {
        __u32   type_len;       /* length of type section       */
        __u32   str_off;        /* offset of string section     */
        __u32   str_len;        /* length of string section     */
+       __u32   meta_off;
+       __u32   meta_len;
 };


So, we add meta_off/meta_len fields to btf_header, which, if non-zero,
will point to a piece of metadata (4-byte aligned) that's described by
struct btf_metadata.

In btf_metadata, the first byte records the number of known BTF kinds,
we have three more bytes for extra flags or counters for
extensibility, they should be zeroed out right now.

After these 4 bytes we have kind_meta_cnt struct btf_kind_meta
entries, each 4-byte long. It's a 1-indexed array, where each entry
corresponds to sequentially numbered BTF kinds. First two bytes are
reserved for flags and stuff like that. Among those, I think the most
useful right now would be the "optional flag". If set, it would mean
that generally speaking it's safe to skip types of that kind without
losing integrity of the data. So e.g., we could have used that for
DECL_TAGS, or perhaps even for FUNCs, if we had this metadata back
then, as these kinds are, generally speaking, not referenced from
other types (not 100% for FUNCs, as we can have FUNC externs, but
those came later). Anyways, for kernel needs we can say that optional
kinds don't cause failure to validate BTF.

*But for security reasons we should make the kernel zero-out
corresponding parts of type information, just to prevent injection of
well-known data by malicious user*.

Next, to the meat of the proposal. info_sz is size in bytes of an
additional singular information (e.g., btf_array for ARRAY kind,
4-byte info for INT kind, etc) that goes after common 12-byte struct
btf_type. It can be zero, of course. elem_sz is a size in bytes of
each nested element (field info for STRUCT, arg info for FUNC_ARG,
etc). Number of elements is defined by btf_vlen(t), which works for
any kind, regardless if it's known or not. If elem_sz is zero, KIND
can't have nested elements (and thus if vlen is non-zero, that's a
corruption).

That's it. We don't allow mixing differently-sized nested elements
within a single kind, but we don't have that today and we don't have
any meaningful ways to express this. And I don't think we'd want to do
this anyways (there are way to work around that if absolutely
necessary, as well).

From libbpf's point of view, this metadata section is easy to
sanitize, as kernel allows btf_headers of bigger size than is known to
it, provided they are zeroed out. So libbpf will just zero out
meta_off/meta_len fields, and contents of the metadata section.

As for the size, it adds just 8 + 4 + 19 * 4 = 88 bytes to the overall
BTF size. It's nothing. I didn't count the total size for your
approach, but at the very least it would be 19 * 2 * sizeof(struct
btf_type) (=12) = 456, but that's super conservative.

Note also that each btf_type can always have a name (described by
btf_type->name_off), so generic BTF tools can easily output what is
the name of the skipped entity, regardless of its actual kind. Tools
can also point out how many nested elements it is supposed to have.
Both are quite nice features, IMO.

Anyways, that's what I had in mind. I think we should bite a bullet
and do it, so that future extensions can make use of this
self-describing metadata.

Thoughts?


> +
> +/* info used to encode a kind metadata field */
> +struct btf_meta_field {
> +       const char *type;
> +       const char *name;
> +       int size;
> +       int type_id;
> +};
> +
> +#define BTF_MAX_META_FIELDS             10
> +
> +#define BTF_META_FIELD(__type, __name)                                 \
> +       { .type = #__type, .name = #__name, .size = sizeof(__type) }
> +
> +#define BTF_KIND_STR(__kind)   #__kind
> +
> +struct btf_kind_encoding {
> +       struct btf_kind_desc kind;
> +       struct btf_meta_field meta[BTF_MAX_META_FIELDS];
> +};
> +
> +#define BTF_KIND(__name, __nr_meta, __meta_size, ...)                  \
> +       { .kind = {                                                     \
> +         .kind = BTF_KIND_##__name,                                    \
> +         .struct_name = BTF_KIND_PFX#__name,                           \
> +         .meta_name = BTF_KIND_META_PFX #__name,                       \
> +         .nr_meta = __nr_meta,                                         \
> +         .meta_size = __meta_size,                                     \
> +       }, .meta = { __VA_ARGS__ } }
> +
> +struct btf_kind_encoding kinds[] = {
> +       BTF_KIND(UNKN,          0,      0),
> +
> +       BTF_KIND(INT,           0,      0),
> +
> +       BTF_KIND(PTR,           0,      0),
> +
> +       BTF_KIND(ARRAY,         1,      sizeof(struct btf_array),
> +                                       BTF_META_FIELD(__u32, type),
> +                                       BTF_META_FIELD(__u32, index_type),
> +                                       BTF_META_FIELD(__u32, nelems)),
> +
> +       BTF_KIND(STRUCT,        0,      sizeof(struct btf_member),
> +                                       BTF_META_FIELD(__u32, name_off),
> +                                       BTF_META_FIELD(__u32, type),
> +                                       BTF_META_FIELD(__u32, offset)),
> +
> +       BTF_KIND(UNION,         0,      sizeof(struct btf_member),
> +                                       BTF_META_FIELD(__u32, name_off),
> +                                       BTF_META_FIELD(__u32, type),
> +                                       BTF_META_FIELD(__u32, offset)),
> +
> +       BTF_KIND(ENUM,          0,      sizeof(struct btf_enum),
> +                                       BTF_META_FIELD(__u32, name_off),
> +                                       BTF_META_FIELD(__s32, val)),
> +
> +       BTF_KIND(FWD,           0,      0),
> +
> +       BTF_KIND(TYPEDEF,       0,      0),
> +
> +       BTF_KIND(VOLATILE,      0,      0),
> +
> +       BTF_KIND(CONST,         0,      0),
> +
> +       BTF_KIND(RESTRICT,      0,      0),
> +
> +       BTF_KIND(FUNC,          0,      0),
> +
> +       BTF_KIND(FUNC_PROTO,    0,      sizeof(struct btf_param),
> +                                       BTF_META_FIELD(__u32, name_off),
> +                                       BTF_META_FIELD(__u32, type)),
> +
> +       BTF_KIND(VAR,           1,      sizeof(struct btf_var),
> +                                       BTF_META_FIELD(__u32, linkage)),
> +
> +       BTF_KIND(DATASEC,       0,      sizeof(struct btf_var_secinfo),
> +                                       BTF_META_FIELD(__u32, type),
> +                                       BTF_META_FIELD(__u32, offset),
> +                                       BTF_META_FIELD(__u32, size)),
> +
> +
> +       BTF_KIND(FLOAT,         0,      0),
> +
> +       BTF_KIND(DECL_TAG,      1,      sizeof(struct btf_decl_tag),
> +                                       BTF_META_FIELD(__s32, component_idx)),
> +
> +       BTF_KIND(TYPE_TAG,      0,      0),
> +
> +       BTF_KIND(ENUM64,        0,      sizeof(struct btf_enum64),
> +                                       BTF_META_FIELD(__u32, name_off),
> +                                       BTF_META_FIELD(__u32, val_lo32),
> +                                       BTF_META_FIELD(__u32, val_hi32)),
> +};
> +
> +/* Try to add representations of the kinds supported to BTF provided.  This will allow parsers
> + * to decode kinds they do not support and skip over them.
> + */
> +int btf__add_kinds(struct btf *btf)
> +{
> +       int btf_type_id, __u32_id, __s32_id, struct_type_id;
> +       char name[64];
> +       int i;
> +
> +       /* should have base types; if not bootstrap them. */
> +       __u32_id = btf__find_by_name(btf, "__u32");
> +       if (__u32_id < 0) {
> +               __s32 unsigned_int_id = btf__find_by_name(btf, "unsigned int");
> +
> +               if (unsigned_int_id < 0)
> +                       unsigned_int_id = btf__add_int(btf, "unsigned int", 4, 0);
> +               __u32_id = btf__add_typedef(btf, "__u32", unsigned_int_id);
> +       }
> +       __s32_id = btf__find_by_name(btf, "__s32");
> +       if (__s32_id < 0) {
> +               __s32 int_id = btf__find_by_name_kind(btf, "int", BTF_KIND_INT);
> +
> +               if (int_id < 0)
> +                       int_id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
> +               __s32_id = btf__add_typedef(btf, "__s32", int_id);
> +       }
> +
> +       /* add "struct __btf_type" if not already present. */
> +       btf_type_id = btf__find_by_name(btf, "__btf_type");
> +       if (btf_type_id < 0) {
> +               __s32 union_id = btf__add_union(btf, NULL, sizeof(__u32));
> +
> +               btf__add_field(btf, "size", __u32_id, 0, 0);
> +               btf__add_field(btf, "type", __u32_id, 0, 0);
> +
> +               btf_type_id = btf__add_struct(btf, "__btf_type", sizeof(struct btf_type));
> +               btf__add_field(btf, "name_off", __u32_id, 0, 0);
> +               btf__add_field(btf, "info", __u32_id, sizeof(__u32) * 8, 0);
> +               btf__add_field(btf, NULL, union_id, sizeof(__u32) * 16, 0);
> +       }
> +
> +       for (i = 0; i < ARRAY_SIZE(kinds); i++) {
> +               struct btf_kind_encoding *kind = &kinds[i];
> +               int meta_id, array_id = 0;
> +
> +               if (btf__find_by_name(btf, kind->kind.struct_name) > 0)
> +                       continue;
> +
> +               if (kind->kind.meta_size != 0) {
> +                       struct btf_meta_field *field;
> +                       __u32 bit_offset = 0;
> +                       int j;
> +
> +                       meta_id = btf__add_struct(btf, kind->kind.meta_name, kind->kind.meta_size);
> +
> +                       for (j = 0; bit_offset < kind->kind.meta_size * 8; j++) {
> +                               field = &kind->meta[j];
> +
> +                               field->type_id = btf__find_by_name(btf, field->type);
> +                               if (field->type_id < 0) {
> +                                       pr_debug("cannot find type '%s' for kind '%s' field '%s'\n",
> +                                                kind->meta[j].type, kind->kind.struct_name,
> +                                                kind->meta[j].name);
> +                               } else {
> +                                       btf__add_field(btf, field->name, field->type_id, bit_offset, 0);
> +                               }
> +                               bit_offset += field->size * 8;
> +                       }
> +                       array_id = btf__add_array(btf, __u32_id, meta_id,
> +                                                 kind->kind.nr_meta);
> +
> +               }
> +               struct_type_id = btf__add_struct(btf, kind->kind.struct_name,
> +                                                sizeof(struct btf_type) +
> +                                                (kind->kind.nr_meta * kind->kind.meta_size));
> +               btf__add_field(btf, "type", btf_type_id, 0, 0);
> +               if (kind->kind.meta_size != 0)
> +                       btf__add_field(btf, "meta", array_id, sizeof(struct btf_type) * 8, 0);
> +               snprintf(name, sizeof(name), BTF_KIND_PFX "%u", i);
> +               btf__add_typedef(btf, name, struct_type_id);
> +       }
> +       return 0;
> +}
> diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
> index 8e6880d..a054082 100644
> --- a/tools/lib/bpf/btf.h
> +++ b/tools/lib/bpf/btf.h
> @@ -219,6 +219,16 @@ LIBBPF_API int btf__add_datasec_var_info(struct btf *btf, int var_type_id,
>  LIBBPF_API int btf__add_decl_tag(struct btf *btf, const char *value, int ref_type_id,
>                             int component_idx);
>
> +/**
> + * @brief **btf__add_kinds()** adds BTF representations of the kind encoding for
> + * all of the kinds known to libbpf.  This ensures that when BTF is encoded, it
> + * will include enough information for parsers to decode (and skip over) kinds
> + * that the parser does not know about yet.  This ensures that an older BTF
> + * parser can read newer BTF, and avoids the need for the BTF encoder to limit
> + * which kinds it emits to make decoding easier.
> + */
> +LIBBPF_API int btf__add_kinds(struct btf *btf);
> +
>  struct btf_dedup_opts {
>         size_t sz;
>         /* optional .BTF.ext info to dedup along the main BTF info */
> diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
> index 71bf569..6121ff1 100644
> --- a/tools/lib/bpf/libbpf.map
> +++ b/tools/lib/bpf/libbpf.map
> @@ -375,6 +375,7 @@ LIBBPF_1.1.0 {
>                 bpf_link_get_fd_by_id_opts;
>                 bpf_map_get_fd_by_id_opts;
>                 bpf_prog_get_fd_by_id_opts;
> +               btf__add_kinds;
>                 user_ring_buffer__discard;
>                 user_ring_buffer__free;
>                 user_ring_buffer__new;
> --
> 1.8.3.1
>

Re: [RFC bpf-next 2/5] libbpf: provide libbpf API to encode BTF kind information

[Alan Maguire]

On 29/11/2022 05:35, Andrii Nakryiko wrote:
> On Wed, Nov 23, 2022 at 9:42 AM Alan Maguire <alan.maguire@oracle.com> wrote:
>>
>> This can be used by BTF parsers to handle kinds they do not know about;
>> this is useful when the encoding libbpf is more recent than the parsing
>> BTF; the parser can then skip over the encoded types it does not know
>> about.
>>
>> We use BTF to encode the BTF kinds that are known at the time of
>> BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
>> to describe each kind and any associated metadata allows BTF parsing
>> to handle new kinds that the parser (in libbpf or the kernel) does
>> not know about.  These kinds will not be used, but since we know
>> their format they can be skipped over and the rest of the BTF can
>> be parsed.  This means we can encode BTF without worrying about the
>> kinds a BTF parser knows about, and means we can avoid using
>> --skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
>> everything it can, something as simple as a libbpf package update
>> then unlocks that encoded information, whereas if we encode
>> pessimistically and drop representations of new kinds, this is not
>> possible.
>>
>> So, in short, by carrying a representation of all the kinds encoded,
>> parsers can parse all of the encoded kinds, even if they cannot use
>> them all.
>>
>> We use BTF itself to carry this representation because this approach
>> does not require BTF parsing to understand a new BTF header format;
>> BTF parsing simply sees some additional types it does not do anything
>> with.  However, a BTF parser that knows about the encoding of kind
>> information can use this information to guide parsing.
>>
>> The process works by explicitly adding btf structs for each kind.
>> Each struct consists of a "struct __btf_type" followed by an array of
>> metadata structs representing the following metadata (for those kinds
>> that have it).  For kinds where a single metadata structure is used,
>> the metadata array has one element.  For kinds where the number
>> of metadata elements varies as per the info.vlen field, a zero-element
>> array is encoded.
>>
>> For a given kind, we add a struct __BTF_KIND_<kind>.  For example,
>>
>> struct __BTF_KIND_INT {
>>         struct __btf_type type;
>> };
>>
>> For a type with one metadata element, the representation looks like
>> this:
>>
>> struct __BTF_KIND_META_ARRAY {
>>         __u32 type;
>>         __u32 index_type;
>>         __u32 nelems;
>> };
>>
>> struct __BTF_KIND_ARRAY {
>>         struct __btf_type type;
>>         struct __BTF_KIND_META_ARRAY meta[1];
>> };
>>
>> For a type with an info.vlen-determined number of following metadata
>> objects, a zero-length array is used:
>>
>> struct __BTF_KIND_STRUCT {
>>         struct __btf_type type;
>>         struct __BTF_KIND_META_STRUCT meta[0];
>> };
>>
>> In order to link kind numeric kind values to the appropriate struct,
>> a typedef is added; for example:
>>
>> typedef struct __BTF_KIND_INT __BTF_KIND_1;
>>
>> When BTF parsing encounters a kind that is not known, the
>> typedef __BTF_KIND_<kind number> is looked up, and we find which
>> struct type id it points to.  So
>>
>>         1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT
>>
>> This approach is preferred, since it ensures the structs representing
>> BTF kinds have names which match their associated kind rather than
>> an opaque number.
>>
>> From there, BTF parsing can look up that struct and determine
>>         - its basic size;
>>         - if it has metadata; and if so
>>         - how many array instances are present;
>>                 - if 0, we know it is a vlen-determined number;
>>                   i.e. vlen * meta_size
>>                 - if > 0, simply use the overall struct size;
>>
>> Based upon that information, BTF parsing can proceed for such
>> unknown kinds, since sufficient information was provided
>> at encoding time to skip over them.
>>
>> Note that this assumes that the above kind-related data
>> structures are represented in BTF _prior_ to any kinds that
>> are new to the parser.  It also assumes the basic kinds
>> required to represent kinds + metadata; base types, structs,
>> arrays, etc.
>>
>> Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
>> ---
>>  tools/lib/bpf/btf.c      | 281 +++++++++++++++++++++++++++++++++++++++++++++++
>>  tools/lib/bpf/btf.h      |  10 ++
>>  tools/lib/bpf/libbpf.map |   1 +
>>  3 files changed, 292 insertions(+)
>>
>> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
>> index 71e165b..e3cea44 100644
>> --- a/tools/lib/bpf/btf.c
>> +++ b/tools/lib/bpf/btf.c
>> @@ -28,6 +28,16 @@
>>
>>  static struct btf_type btf_void;
>>
>> +/* info used to encode/decode an unrecognized kind */
>> +struct btf_kind_desc {
>> +       int kind;
>> +       const char *struct_name;        /* __BTF_KIND_ARRAY */
>> +       const char *typedef_name;       /* __BTF_KIND_2 */
>> +       const char *meta_name;          /* __BTF_KIND_META_ARRAY */
>> +       int nr_meta;
>> +       int meta_size;
>> +};
>> +
>>  struct btf {
>>         /* raw BTF data in native endianness */
>>         void *raw_data;
>> @@ -5011,3 +5021,274 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void
>>
>>         return 0;
>>  }
>> +
>> +/* Here we use BTF to encode the BTF kinds that are known at the time of
>> + * BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
>> + * to describe each kind and any associated metadata allows BTF parsing
>> + * to handle new kinds that the parser (in libbpf or the kernel) does
>> + * not know about.  These kinds will not be used, but since we know
>> + * their format they can be skipped over and the rest of the BTF can
>> + * be parsed.  This means we can encode BTF without worrying about the
>> + * kinds a BTF parser knows about, and means we can avoid using
>> + * --skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
>> + * everything it can, something as simple as a libbpf package update
>> + * then unlocks that encodeded information, whereas if we encode
>> + * pessimistically and drop representations of new kinds, this is not
>> + * possible.
>> + *
>> + * So, in short, by carrying a representation of all the kinds encoded,
>> + * parsers can parse all of the encoded kinds, even if they cannot use
>> + * them all.
>> + *
>> + * We use BTF itself to carry this representation because this approach
>> + * does not require BTF parsing to understand a new BTF header format;
>> + * BTF parsing simply sees some additional types it does not do anything
>> + * with.  A BTF parser that knows about the encoding of kind information
>> + * however can use this information in parsing.
>> + *
>> + * The process works by explicitly adding btf structs for each kind.
>> + * Each struct consists of a struct __btf_type followed by an array of
>> + * metadata structs representing the following metadata (for those kinds
>> + * that have it).  For kinds where a single metadata structure is used,
>> + * the metadata array has one element.  For kinds where the number
>> + * of metadata elements varies as per the info.vlen field, a zero-element
>> + * array is encoded.
>> + *
>> + * For a given kind, we add a struct __BTF_KIND_<kind>.  For example,
>> + *
>> + * struct __BTF_KIND_INT {
>> + *     struct __btf_type type;
>> + * };
>> + *
>> + * For a type with one metadata element, the representation looks like
>> + * this:
>> + *
>> + * struct __BTF_KIND_META_ARRAY {
>> + *     __u32 type;
>> + *     __u32 index_type;
>> + *     __u32  nelems;
>> + * };
>> + *
>> + * struct __BTF_KIND_ARRAY {
>> + *     struct __btf_type type;
>> + *     struct __BTF_KIND_META_ARRAY meta[1];
>> + * };
>> + *
>> + *
>> + * For a type with an info.vlen-determined number of following metadata
>> + * objects, a zero-length array is used:
>> + *
>> + * struct __BTF_KIND_STRUCT {
>> + *     struct __btf_type type;
>> + *     struct __BTF_KIND_META_STRUCT meta[0];
>> + * };
>> + *
>> + * In order to link kind numeric kind values to the appropriate struct,
>> + * a typedef is added; for example:
>> + *
>> + * typedef struct __BTF_KIND_INT __BTF_KIND_1;
>> + *
>> + * When BTF parsing encounters a kind that is not known, the
>> + * typedef __BTF_KIND_<kind number> is looked up, and we find which
>> + * struct type id it points to.  So
>> + *
>> + *     1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT
>> + *
>> + * This approach is preferred, since it ensures the structs representing
>> + * BTF kinds have names which match their associated kind rather than
>> + * an opaque number.
>> + *
>> + * From there, BTF parsing can look up that struct and determine
>> + *     - its basic size;
>> + *     - if it has metadata; and if so
>> + *     - how many array instances are present;
>> + *             - if 0, we know it is a vlen-determined number;
>> + *             - if > 0, simply use the overall struct size;
>> + *
>> + * Based upon that information, BTF parsing can proceed for such
>> + * unknown kinds, since sufficient information was provided
>> + * at encoding time.
>> + *
>> + * Note that this assumes that the above kind-related data
>> + * structures are represented in BTF _prior_ to any kinds that
>> + * are new to the parser.  It also assumes the basic kinds
>> + * required to represent kinds + metadata; base types, structs,
>> + * arrays, etc.
>> + */
> 
> Goodness gracious! :)
> 
> Aesthetics of all this aside (which hurts me deeply, but let's ignore
> that for a moment), this whole requirement that these
> self-describing-but-also-convention-driven types which are supposed to
> help with parsing types information are themselves in types
> information is quite unusual. Yes, by saying "we assume they come
> before a first type with unknown kind" we kind of work around this,
> but even the fact that you can use btf__type_by_id() and
> btf__find_by_name_kind() before BTF is fully parsed is kind of by
> accident. All-in-all this screams "a kludge" at me, sorry.
> 
> I really don't like this approach, even if *technically* it would
> work. But even if so, it would add quite a bunch of size to BTF just
> to self-describe it.
> 
> Let's go again (and in more detail) over my alternative proposal I
> briefly described in another email thread.
> 
> So, what I'm proposing is similar in spirit and solves all the same
> goals you have (and actually some more, I'll point this out below).
> The only downside is that we'll need to, again, teach kernel to
> understand this BTF format extension to allow kernel to use it (so we
> still will need an opt-in flag for pahole, unfortunately, but
> hopefully just this one time). That's pretty much the only downside.
> But it's more compact, simpler and more straightforward, more elegant
> (IMO), and it is easy for libbpf to sanitize it for old kernels.
> 
> Ok, so it's pretty much completely described by these changes:
> 
> --- a/include/uapi/linux/btf.h
> +++ b/include/uapi/linux/btf.h
> @@ -8,6 +8,21 @@
>  #define BTF_MAGIC      0xeB9F
>  #define BTF_VERSION    1
> 
> +struct btf_kind_meta {
> +       /* extra flags, initially define just one:
> +        * 0x01 - required or optional (is it safe to skip if unknown)
> +        */
> +       __u16 flags;
> +       __u8 info_sz;
> +       __u8 elem_sz;
> +};
> +
> +struct btf_metadata {
> +       __u8 kind_meta_cnt;
> +       __u32 :0;
> +       struct btf_kind_meta[];
> +};
> +
>  struct btf_header {
>         __u16   magic;
>         __u8    version;
> @@ -19,6 +34,8 @@ struct btf_header {
>         __u32   type_len;       /* length of type section       */
>         __u32   str_off;        /* offset of string section     */
>         __u32   str_len;        /* length of string section     */
> +       __u32   meta_off;
> +       __u32   meta_len;
>  };
>

Ok, if we're going this route though, let's try to think through any 
other info we need to add so the format changes are a one-time thing.
We should add flags too. One current use-case would be the 
"is this BTF standalone, or does it require base BTF?" [1]. Either using
an existing value in the header flags field, or using the space for a flags 
field in  struct btf_metadata would probably make sense.

Do we have any other outstanding issues with BTF that would be eased
by some sort of up-front declaration? If we can at least tackle those
things at once, the pain will be somewhat less when updating the toolchain.

> 
> So, we add meta_off/meta_len fields to btf_header, which, if non-zero,
> will point to a piece of metadata (4-byte aligned) that's described by
> struct btf_metadata.
> 
> In btf_metadata, the first byte records the number of known BTF kinds,
> we have three more bytes for extra flags or counters for
> extensibility, they should be zeroed out right now.
> 

Right; see above for one flags use-case.

> After these 4 bytes we have kind_meta_cnt struct btf_kind_meta
> entries, each 4-byte long. It's a 1-indexed array, where each entry
> corresponds to sequentially numbered BTF kinds. First two bytes are
> reserved for flags and stuff like that. Among those, I think the most
> useful right now would be the "optional flag". If set, it would mean
> that generally speaking it's safe to skip types of that kind without
> losing integrity of the data. So e.g., we could have used that for
> DECL_TAGS, or perhaps even for FUNCs, if we had this metadata back
> then, as these kinds are, generally speaking, not referenced from
> other types (not 100% for FUNCs, as we can have FUNC externs, but
> those came later). Anyways, for kernel needs we can say that optional
> kinds don't cause failure to validate BTF.
> 

This would definitely be useful; but are you saying here that
a struct with a reference to an unknown kind should fail BTF
validation (something like a struct with an enum64 member parsed by a
libbpf prior to enum64 support)? Not sure there's any alternative
for a case like that...

> *But for security reasons we should make the kernel zero-out
> corresponding parts of type information, just to prevent injection of
> well-known data by malicious user*.
> 
> Next, to the meat of the proposal. info_sz is size in bytes of an
> additional singular information (e.g., btf_array for ARRAY kind,
> 4-byte info for INT kind, etc) that goes after common 12-byte struct
> btf_type. It can be zero, of course. elem_sz is a size in bytes of
> each nested element (field info for STRUCT, arg info for FUNC_ARG,
> etc). Number of elements is defined by btf_vlen(t), which works for
> any kind, regardless if it's known or not. If elem_sz is zero, KIND
> can't have nested elements (and thus if vlen is non-zero, that's a
> corruption).
> 
> That's it. We don't allow mixing differently-sized nested elements
> within a single kind, but we don't have that today and we don't have
> any meaningful ways to express this. And I don't think we'd want to do
> this anyways (there are way to work around that if absolutely
> necessary, as well).
> 
> From libbpf's point of view, this metadata section is easy to
> sanitize, as kernel allows btf_headers of bigger size than is known to
> it, provided they are zeroed out. So libbpf will just zero out
> meta_off/meta_len fields, and contents of the metadata section.
> 
> As for the size, it adds just 8 + 4 + 19 * 4 = 88 bytes to the overall
> BTF size. It's nothing. I didn't count the total size for your
> approach, but at the very least it would be 19 * 2 * sizeof(struct
> btf_type) (=12) = 456, but that's super conservative.
> 
> Note also that each btf_type can always have a name (described by
> btf_type->name_off), so generic BTF tools can easily output what is
> the name of the skipped entity, regardless of its actual kind. Tools
> can also point out how many nested elements it is supposed to have.
> Both are quite nice features, IMO.
> 
> Anyways, that's what I had in mind. I think we should bite a bullet
> and do it, so that future extensions can make use of this
> self-describing metadata.
> 
> Thoughts?
>

It'll work, a few specific questions we should probably resolve up front:

- We can deduce the presence of the metadata info from the header length, so we
  don't need a BTF version bump, right?

- from the encoding perspective, you mentioned having metadata opt-in;
  so I presume we'd have a btf__add_metadata() API (it is zero by default so
  accepted by the kernel I think) if --encode_metadata is set? Perhaps eventually
  we could move to opt-out.

- there are some cases where what is valid has evolved over time. For example,
  kind flags have appeared for some kinds; should we have a flag for "supports kind
  flag"? (set for struct/union/enum/fwd/eum64)?

I can probably respin what I have, unless you want to take it on?

[1] https://lore.kernel.org/bpf/CAEf4BzYXRT9pFmC1RqnNBmvQWGQkd0zs9rbH9z9Ug8FWOArb_Q@mail.gmail.com/
 
> 
>> +
>> +/* info used to encode a kind metadata field */
>> +struct btf_meta_field {
>> +       const char *type;
>> +       const char *name;
>> +       int size;
>> +       int type_id;
>> +};
>> +
>> +#define BTF_MAX_META_FIELDS             10
>> +
>> +#define BTF_META_FIELD(__type, __name)                                 \
>> +       { .type = #__type, .name = #__name, .size = sizeof(__type) }
>> +
>> +#define BTF_KIND_STR(__kind)   #__kind
>> +
>> +struct btf_kind_encoding {
>> +       struct btf_kind_desc kind;
>> +       struct btf_meta_field meta[BTF_MAX_META_FIELDS];
>> +};
>> +
>> +#define BTF_KIND(__name, __nr_meta, __meta_size, ...)                  \
>> +       { .kind = {                                                     \
>> +         .kind = BTF_KIND_##__name,                                    \
>> +         .struct_name = BTF_KIND_PFX#__name,                           \
>> +         .meta_name = BTF_KIND_META_PFX #__name,                       \
>> +         .nr_meta = __nr_meta,                                         \
>> +         .meta_size = __meta_size,                                     \
>> +       }, .meta = { __VA_ARGS__ } }
>> +
>> +struct btf_kind_encoding kinds[] = {
>> +       BTF_KIND(UNKN,          0,      0),
>> +
>> +       BTF_KIND(INT,           0,      0),
>> +
>> +       BTF_KIND(PTR,           0,      0),
>> +
>> +       BTF_KIND(ARRAY,         1,      sizeof(struct btf_array),
>> +                                       BTF_META_FIELD(__u32, type),
>> +                                       BTF_META_FIELD(__u32, index_type),
>> +                                       BTF_META_FIELD(__u32, nelems)),
>> +
>> +       BTF_KIND(STRUCT,        0,      sizeof(struct btf_member),
>> +                                       BTF_META_FIELD(__u32, name_off),
>> +                                       BTF_META_FIELD(__u32, type),
>> +                                       BTF_META_FIELD(__u32, offset)),
>> +
>> +       BTF_KIND(UNION,         0,      sizeof(struct btf_member),
>> +                                       BTF_META_FIELD(__u32, name_off),
>> +                                       BTF_META_FIELD(__u32, type),
>> +                                       BTF_META_FIELD(__u32, offset)),
>> +
>> +       BTF_KIND(ENUM,          0,      sizeof(struct btf_enum),
>> +                                       BTF_META_FIELD(__u32, name_off),
>> +                                       BTF_META_FIELD(__s32, val)),
>> +
>> +       BTF_KIND(FWD,           0,      0),
>> +
>> +       BTF_KIND(TYPEDEF,       0,      0),
>> +
>> +       BTF_KIND(VOLATILE,      0,      0),
>> +
>> +       BTF_KIND(CONST,         0,      0),
>> +
>> +       BTF_KIND(RESTRICT,      0,      0),
>> +
>> +       BTF_KIND(FUNC,          0,      0),
>> +
>> +       BTF_KIND(FUNC_PROTO,    0,      sizeof(struct btf_param),
>> +                                       BTF_META_FIELD(__u32, name_off),
>> +                                       BTF_META_FIELD(__u32, type)),
>> +
>> +       BTF_KIND(VAR,           1,      sizeof(struct btf_var),
>> +                                       BTF_META_FIELD(__u32, linkage)),
>> +
>> +       BTF_KIND(DATASEC,       0,      sizeof(struct btf_var_secinfo),
>> +                                       BTF_META_FIELD(__u32, type),
>> +                                       BTF_META_FIELD(__u32, offset),
>> +                                       BTF_META_FIELD(__u32, size)),
>> +
>> +
>> +       BTF_KIND(FLOAT,         0,      0),
>> +
>> +       BTF_KIND(DECL_TAG,      1,      sizeof(struct btf_decl_tag),
>> +                                       BTF_META_FIELD(__s32, component_idx)),
>> +
>> +       BTF_KIND(TYPE_TAG,      0,      0),
>> +
>> +       BTF_KIND(ENUM64,        0,      sizeof(struct btf_enum64),
>> +                                       BTF_META_FIELD(__u32, name_off),
>> +                                       BTF_META_FIELD(__u32, val_lo32),
>> +                                       BTF_META_FIELD(__u32, val_hi32)),
>> +};
>> +
>> +/* Try to add representations of the kinds supported to BTF provided.  This will allow parsers
>> + * to decode kinds they do not support and skip over them.
>> + */
>> +int btf__add_kinds(struct btf *btf)
>> +{
>> +       int btf_type_id, __u32_id, __s32_id, struct_type_id;
>> +       char name[64];
>> +       int i;
>> +
>> +       /* should have base types; if not bootstrap them. */
>> +       __u32_id = btf__find_by_name(btf, "__u32");
>> +       if (__u32_id < 0) {
>> +               __s32 unsigned_int_id = btf__find_by_name(btf, "unsigned int");
>> +
>> +               if (unsigned_int_id < 0)
>> +                       unsigned_int_id = btf__add_int(btf, "unsigned int", 4, 0);
>> +               __u32_id = btf__add_typedef(btf, "__u32", unsigned_int_id);
>> +       }
>> +       __s32_id = btf__find_by_name(btf, "__s32");
>> +       if (__s32_id < 0) {
>> +               __s32 int_id = btf__find_by_name_kind(btf, "int", BTF_KIND_INT);
>> +
>> +               if (int_id < 0)
>> +                       int_id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
>> +               __s32_id = btf__add_typedef(btf, "__s32", int_id);
>> +       }
>> +
>> +       /* add "struct __btf_type" if not already present. */
>> +       btf_type_id = btf__find_by_name(btf, "__btf_type");
>> +       if (btf_type_id < 0) {
>> +               __s32 union_id = btf__add_union(btf, NULL, sizeof(__u32));
>> +
>> +               btf__add_field(btf, "size", __u32_id, 0, 0);
>> +               btf__add_field(btf, "type", __u32_id, 0, 0);
>> +
>> +               btf_type_id = btf__add_struct(btf, "__btf_type", sizeof(struct btf_type));
>> +               btf__add_field(btf, "name_off", __u32_id, 0, 0);
>> +               btf__add_field(btf, "info", __u32_id, sizeof(__u32) * 8, 0);
>> +               btf__add_field(btf, NULL, union_id, sizeof(__u32) * 16, 0);
>> +       }
>> +
>> +       for (i = 0; i < ARRAY_SIZE(kinds); i++) {
>> +               struct btf_kind_encoding *kind = &kinds[i];
>> +               int meta_id, array_id = 0;
>> +
>> +               if (btf__find_by_name(btf, kind->kind.struct_name) > 0)
>> +                       continue;
>> +
>> +               if (kind->kind.meta_size != 0) {
>> +                       struct btf_meta_field *field;
>> +                       __u32 bit_offset = 0;
>> +                       int j;
>> +
>> +                       meta_id = btf__add_struct(btf, kind->kind.meta_name, kind->kind.meta_size);
>> +
>> +                       for (j = 0; bit_offset < kind->kind.meta_size * 8; j++) {
>> +                               field = &kind->meta[j];
>> +
>> +                               field->type_id = btf__find_by_name(btf, field->type);
>> +                               if (field->type_id < 0) {
>> +                                       pr_debug("cannot find type '%s' for kind '%s' field '%s'\n",
>> +                                                kind->meta[j].type, kind->kind.struct_name,
>> +                                                kind->meta[j].name);
>> +                               } else {
>> +                                       btf__add_field(btf, field->name, field->type_id, bit_offset, 0);
>> +                               }
>> +                               bit_offset += field->size * 8;
>> +                       }
>> +                       array_id = btf__add_array(btf, __u32_id, meta_id,
>> +                                                 kind->kind.nr_meta);
>> +
>> +               }
>> +               struct_type_id = btf__add_struct(btf, kind->kind.struct_name,
>> +                                                sizeof(struct btf_type) +
>> +                                                (kind->kind.nr_meta * kind->kind.meta_size));
>> +               btf__add_field(btf, "type", btf_type_id, 0, 0);
>> +               if (kind->kind.meta_size != 0)
>> +                       btf__add_field(btf, "meta", array_id, sizeof(struct btf_type) * 8, 0);
>> +               snprintf(name, sizeof(name), BTF_KIND_PFX "%u", i);
>> +               btf__add_typedef(btf, name, struct_type_id);
>> +       }
>> +       return 0;
>> +}
>> diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
>> index 8e6880d..a054082 100644
>> --- a/tools/lib/bpf/btf.h
>> +++ b/tools/lib/bpf/btf.h
>> @@ -219,6 +219,16 @@ LIBBPF_API int btf__add_datasec_var_info(struct btf *btf, int var_type_id,
>>  LIBBPF_API int btf__add_decl_tag(struct btf *btf, const char *value, int ref_type_id,
>>                             int component_idx);
>>
>> +/**
>> + * @brief **btf__add_kinds()** adds BTF representations of the kind encoding for
>> + * all of the kinds known to libbpf.  This ensures that when BTF is encoded, it
>> + * will include enough information for parsers to decode (and skip over) kinds
>> + * that the parser does not know about yet.  This ensures that an older BTF
>> + * parser can read newer BTF, and avoids the need for the BTF encoder to limit
>> + * which kinds it emits to make decoding easier.
>> + */
>> +LIBBPF_API int btf__add_kinds(struct btf *btf);
>> +
>>  struct btf_dedup_opts {
>>         size_t sz;
>>         /* optional .BTF.ext info to dedup along the main BTF info */
>> diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
>> index 71bf569..6121ff1 100644
>> --- a/tools/lib/bpf/libbpf.map
>> +++ b/tools/lib/bpf/libbpf.map
>> @@ -375,6 +375,7 @@ LIBBPF_1.1.0 {
>>                 bpf_link_get_fd_by_id_opts;
>>                 bpf_map_get_fd_by_id_opts;
>>                 bpf_prog_get_fd_by_id_opts;
>> +               btf__add_kinds;
>>                 user_ring_buffer__discard;
>>                 user_ring_buffer__free;
>>                 user_ring_buffer__new;
>> --
>> 1.8.3.1
>>

Re: [RFC bpf-next 2/5] libbpf: provide libbpf API to encode BTF kind information

[Andrii Nakryiko]

On Tue, Nov 29, 2022 at 5:51 AM Alan Maguire <alan.maguire@oracle.com> wrote:
>
> On 29/11/2022 05:35, Andrii Nakryiko wrote:
> > On Wed, Nov 23, 2022 at 9:42 AM Alan Maguire <alan.maguire@oracle.com> wrote:
> >>
> >> This can be used by BTF parsers to handle kinds they do not know about;
> >> this is useful when the encoding libbpf is more recent than the parsing
> >> BTF; the parser can then skip over the encoded types it does not know
> >> about.
> >>
> >> We use BTF to encode the BTF kinds that are known at the time of
> >> BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
> >> to describe each kind and any associated metadata allows BTF parsing
> >> to handle new kinds that the parser (in libbpf or the kernel) does
> >> not know about.  These kinds will not be used, but since we know
> >> their format they can be skipped over and the rest of the BTF can
> >> be parsed.  This means we can encode BTF without worrying about the
> >> kinds a BTF parser knows about, and means we can avoid using
> >> --skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
> >> everything it can, something as simple as a libbpf package update
> >> then unlocks that encoded information, whereas if we encode
> >> pessimistically and drop representations of new kinds, this is not
> >> possible.
> >>
> >> So, in short, by carrying a representation of all the kinds encoded,
> >> parsers can parse all of the encoded kinds, even if they cannot use
> >> them all.
> >>
> >> We use BTF itself to carry this representation because this approach
> >> does not require BTF parsing to understand a new BTF header format;
> >> BTF parsing simply sees some additional types it does not do anything
> >> with.  However, a BTF parser that knows about the encoding of kind
> >> information can use this information to guide parsing.
> >>
> >> The process works by explicitly adding btf structs for each kind.
> >> Each struct consists of a "struct __btf_type" followed by an array of
> >> metadata structs representing the following metadata (for those kinds
> >> that have it).  For kinds where a single metadata structure is used,
> >> the metadata array has one element.  For kinds where the number
> >> of metadata elements varies as per the info.vlen field, a zero-element
> >> array is encoded.
> >>
> >> For a given kind, we add a struct __BTF_KIND_<kind>.  For example,
> >>
> >> struct __BTF_KIND_INT {
> >>         struct __btf_type type;
> >> };
> >>
> >> For a type with one metadata element, the representation looks like
> >> this:
> >>
> >> struct __BTF_KIND_META_ARRAY {
> >>         __u32 type;
> >>         __u32 index_type;
> >>         __u32 nelems;
> >> };
> >>
> >> struct __BTF_KIND_ARRAY {
> >>         struct __btf_type type;
> >>         struct __BTF_KIND_META_ARRAY meta[1];
> >> };
> >>
> >> For a type with an info.vlen-determined number of following metadata
> >> objects, a zero-length array is used:
> >>
> >> struct __BTF_KIND_STRUCT {
> >>         struct __btf_type type;
> >>         struct __BTF_KIND_META_STRUCT meta[0];
> >> };
> >>
> >> In order to link kind numeric kind values to the appropriate struct,
> >> a typedef is added; for example:
> >>
> >> typedef struct __BTF_KIND_INT __BTF_KIND_1;
> >>
> >> When BTF parsing encounters a kind that is not known, the
> >> typedef __BTF_KIND_<kind number> is looked up, and we find which
> >> struct type id it points to.  So
> >>
> >>         1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT
> >>
> >> This approach is preferred, since it ensures the structs representing
> >> BTF kinds have names which match their associated kind rather than
> >> an opaque number.
> >>
> >> From there, BTF parsing can look up that struct and determine
> >>         - its basic size;
> >>         - if it has metadata; and if so
> >>         - how many array instances are present;
> >>                 - if 0, we know it is a vlen-determined number;
> >>                   i.e. vlen * meta_size
> >>                 - if > 0, simply use the overall struct size;
> >>
> >> Based upon that information, BTF parsing can proceed for such
> >> unknown kinds, since sufficient information was provided
> >> at encoding time to skip over them.
> >>
> >> Note that this assumes that the above kind-related data
> >> structures are represented in BTF _prior_ to any kinds that
> >> are new to the parser.  It also assumes the basic kinds
> >> required to represent kinds + metadata; base types, structs,
> >> arrays, etc.
> >>
> >> Signed-off-by: Alan Maguire <alan.maguire@oracle.com>
> >> ---
> >>  tools/lib/bpf/btf.c      | 281 +++++++++++++++++++++++++++++++++++++++++++++++
> >>  tools/lib/bpf/btf.h      |  10 ++
> >>  tools/lib/bpf/libbpf.map |   1 +
> >>  3 files changed, 292 insertions(+)
> >>
> >> diff --git a/tools/lib/bpf/btf.c b/tools/lib/bpf/btf.c
> >> index 71e165b..e3cea44 100644
> >> --- a/tools/lib/bpf/btf.c
> >> +++ b/tools/lib/bpf/btf.c
> >> @@ -28,6 +28,16 @@
> >>
> >>  static struct btf_type btf_void;
> >>
> >> +/* info used to encode/decode an unrecognized kind */
> >> +struct btf_kind_desc {
> >> +       int kind;
> >> +       const char *struct_name;        /* __BTF_KIND_ARRAY */
> >> +       const char *typedef_name;       /* __BTF_KIND_2 */
> >> +       const char *meta_name;          /* __BTF_KIND_META_ARRAY */
> >> +       int nr_meta;
> >> +       int meta_size;
> >> +};
> >> +
> >>  struct btf {
> >>         /* raw BTF data in native endianness */
> >>         void *raw_data;
> >> @@ -5011,3 +5021,274 @@ int btf_ext_visit_str_offs(struct btf_ext *btf_ext, str_off_visit_fn visit, void
> >>
> >>         return 0;
> >>  }
> >> +
> >> +/* Here we use BTF to encode the BTF kinds that are known at the time of
> >> + * BTF encoding; the use of basic BTF kinds (structs, arrays, base types)
> >> + * to describe each kind and any associated metadata allows BTF parsing
> >> + * to handle new kinds that the parser (in libbpf or the kernel) does
> >> + * not know about.  These kinds will not be used, but since we know
> >> + * their format they can be skipped over and the rest of the BTF can
> >> + * be parsed.  This means we can encode BTF without worrying about the
> >> + * kinds a BTF parser knows about, and means we can avoid using
> >> + * --skip_new_kind solutions.  This is valuable, as if kernel BTF encodes
> >> + * everything it can, something as simple as a libbpf package update
> >> + * then unlocks that encodeded information, whereas if we encode
> >> + * pessimistically and drop representations of new kinds, this is not
> >> + * possible.
> >> + *
> >> + * So, in short, by carrying a representation of all the kinds encoded,
> >> + * parsers can parse all of the encoded kinds, even if they cannot use
> >> + * them all.
> >> + *
> >> + * We use BTF itself to carry this representation because this approach
> >> + * does not require BTF parsing to understand a new BTF header format;
> >> + * BTF parsing simply sees some additional types it does not do anything
> >> + * with.  A BTF parser that knows about the encoding of kind information
> >> + * however can use this information in parsing.
> >> + *
> >> + * The process works by explicitly adding btf structs for each kind.
> >> + * Each struct consists of a struct __btf_type followed by an array of
> >> + * metadata structs representing the following metadata (for those kinds
> >> + * that have it).  For kinds where a single metadata structure is used,
> >> + * the metadata array has one element.  For kinds where the number
> >> + * of metadata elements varies as per the info.vlen field, a zero-element
> >> + * array is encoded.
> >> + *
> >> + * For a given kind, we add a struct __BTF_KIND_<kind>.  For example,
> >> + *
> >> + * struct __BTF_KIND_INT {
> >> + *     struct __btf_type type;
> >> + * };
> >> + *
> >> + * For a type with one metadata element, the representation looks like
> >> + * this:
> >> + *
> >> + * struct __BTF_KIND_META_ARRAY {
> >> + *     __u32 type;
> >> + *     __u32 index_type;
> >> + *     __u32  nelems;
> >> + * };
> >> + *
> >> + * struct __BTF_KIND_ARRAY {
> >> + *     struct __btf_type type;
> >> + *     struct __BTF_KIND_META_ARRAY meta[1];
> >> + * };
> >> + *
> >> + *
> >> + * For a type with an info.vlen-determined number of following metadata
> >> + * objects, a zero-length array is used:
> >> + *
> >> + * struct __BTF_KIND_STRUCT {
> >> + *     struct __btf_type type;
> >> + *     struct __BTF_KIND_META_STRUCT meta[0];
> >> + * };
> >> + *
> >> + * In order to link kind numeric kind values to the appropriate struct,
> >> + * a typedef is added; for example:
> >> + *
> >> + * typedef struct __BTF_KIND_INT __BTF_KIND_1;
> >> + *
> >> + * When BTF parsing encounters a kind that is not known, the
> >> + * typedef __BTF_KIND_<kind number> is looked up, and we find which
> >> + * struct type id it points to.  So
> >> + *
> >> + *     1 -> typedef __BTF_KIND_1 -> struct __BTF_KIND_INT
> >> + *
> >> + * This approach is preferred, since it ensures the structs representing
> >> + * BTF kinds have names which match their associated kind rather than
> >> + * an opaque number.
> >> + *
> >> + * From there, BTF parsing can look up that struct and determine
> >> + *     - its basic size;
> >> + *     - if it has metadata; and if so
> >> + *     - how many array instances are present;
> >> + *             - if 0, we know it is a vlen-determined number;
> >> + *             - if > 0, simply use the overall struct size;
> >> + *
> >> + * Based upon that information, BTF parsing can proceed for such
> >> + * unknown kinds, since sufficient information was provided
> >> + * at encoding time.
> >> + *
> >> + * Note that this assumes that the above kind-related data
> >> + * structures are represented in BTF _prior_ to any kinds that
> >> + * are new to the parser.  It also assumes the basic kinds
> >> + * required to represent kinds + metadata; base types, structs,
> >> + * arrays, etc.
> >> + */
> >
> > Goodness gracious! :)
> >
> > Aesthetics of all this aside (which hurts me deeply, but let's ignore
> > that for a moment), this whole requirement that these
> > self-describing-but-also-convention-driven types which are supposed to
> > help with parsing types information are themselves in types
> > information is quite unusual. Yes, by saying "we assume they come
> > before a first type with unknown kind" we kind of work around this,
> > but even the fact that you can use btf__type_by_id() and
> > btf__find_by_name_kind() before BTF is fully parsed is kind of by
> > accident. All-in-all this screams "a kludge" at me, sorry.
> >
> > I really don't like this approach, even if *technically* it would
> > work. But even if so, it would add quite a bunch of size to BTF just
> > to self-describe it.
> >
> > Let's go again (and in more detail) over my alternative proposal I
> > briefly described in another email thread.
> >
> > So, what I'm proposing is similar in spirit and solves all the same
> > goals you have (and actually some more, I'll point this out below).
> > The only downside is that we'll need to, again, teach kernel to
> > understand this BTF format extension to allow kernel to use it (so we
> > still will need an opt-in flag for pahole, unfortunately, but
> > hopefully just this one time). That's pretty much the only downside.
> > But it's more compact, simpler and more straightforward, more elegant
> > (IMO), and it is easy for libbpf to sanitize it for old kernels.
> >
> > Ok, so it's pretty much completely described by these changes:
> >
> > --- a/include/uapi/linux/btf.h
> > +++ b/include/uapi/linux/btf.h
> > @@ -8,6 +8,21 @@
> >  #define BTF_MAGIC      0xeB9F
> >  #define BTF_VERSION    1
> >
> > +struct btf_kind_meta {
> > +       /* extra flags, initially define just one:
> > +        * 0x01 - required or optional (is it safe to skip if unknown)
> > +        */
> > +       __u16 flags;
> > +       __u8 info_sz;
> > +       __u8 elem_sz;
> > +};
> > +
> > +struct btf_metadata {
> > +       __u8 kind_meta_cnt;
> > +       __u32 :0;
> > +       struct btf_kind_meta[];
> > +};
> > +
> >  struct btf_header {
> >         __u16   magic;
> >         __u8    version;
> > @@ -19,6 +34,8 @@ struct btf_header {
> >         __u32   type_len;       /* length of type section       */
> >         __u32   str_off;        /* offset of string section     */
> >         __u32   str_len;        /* length of string section     */
> > +       __u32   meta_off;
> > +       __u32   meta_len;
> >  };
> >
>
> Ok, if we're going this route though, let's try to think through any
> other info we need to add so the format changes are a one-time thing.
> We should add flags too. One current use-case would be the
> "is this BTF standalone, or does it require base BTF?" [1]. Either using
> an existing value in the header flags field, or using the space for a flags
> field in  struct btf_metadata would probably make sense.

Yes, it's a good idea. But instead of a flag, I wonder if we should
add some sort of "build ID" concept here, so that we can check
validity of base BTF as expected by split BTF?

>
> Do we have any other outstanding issues with BTF that would be eased
> by some sort of up-front declaration? If we can at least tackle those
> things at once, the pain will be somewhat less when updating the toolchain.

Base vs split BTF + some check whether base BTF is valid is the only
thing that currently comes to mind.

>
> >
> > So, we add meta_off/meta_len fields to btf_header, which, if non-zero,
> > will point to a piece of metadata (4-byte aligned) that's described by
> > struct btf_metadata.
> >
> > In btf_metadata, the first byte records the number of known BTF kinds,
> > we have three more bytes for extra flags or counters for
> > extensibility, they should be zeroed out right now.
> >
>
> Right; see above for one flags use-case.
>
> > After these 4 bytes we have kind_meta_cnt struct btf_kind_meta
> > entries, each 4-byte long. It's a 1-indexed array, where each entry
> > corresponds to sequentially numbered BTF kinds. First two bytes are
> > reserved for flags and stuff like that. Among those, I think the most
> > useful right now would be the "optional flag". If set, it would mean
> > that generally speaking it's safe to skip types of that kind without
> > losing integrity of the data. So e.g., we could have used that for
> > DECL_TAGS, or perhaps even for FUNCs, if we had this metadata back
> > then, as these kinds are, generally speaking, not referenced from
> > other types (not 100% for FUNCs, as we can have FUNC externs, but
> > those came later). Anyways, for kernel needs we can say that optional
> > kinds don't cause failure to validate BTF.
> >
>
> This would definitely be useful; but are you saying here that
> a struct with a reference to an unknown kind should fail BTF
> validation (something like a struct with an enum64 member parsed by a
> libbpf prior to enum64 support)? Not sure there's any alternative
> for a case like that...

From the kernel validation point -- yes, probably. From generic
tooling and libbpf-side -- perhaps not. I think kernel will always
have to be pretty strict due to security reasons.


>
> > *But for security reasons we should make the kernel zero-out
> > corresponding parts of type information, just to prevent injection of
> > well-known data by malicious user*.
> >
> > Next, to the meat of the proposal. info_sz is size in bytes of an
> > additional singular information (e.g., btf_array for ARRAY kind,
> > 4-byte info for INT kind, etc) that goes after common 12-byte struct
> > btf_type. It can be zero, of course. elem_sz is a size in bytes of
> > each nested element (field info for STRUCT, arg info for FUNC_ARG,
> > etc). Number of elements is defined by btf_vlen(t), which works for
> > any kind, regardless if it's known or not. If elem_sz is zero, KIND
> > can't have nested elements (and thus if vlen is non-zero, that's a
> > corruption).
> >
> > That's it. We don't allow mixing differently-sized nested elements
> > within a single kind, but we don't have that today and we don't have
> > any meaningful ways to express this. And I don't think we'd want to do
> > this anyways (there are way to work around that if absolutely
> > necessary, as well).
> >
> > From libbpf's point of view, this metadata section is easy to
> > sanitize, as kernel allows btf_headers of bigger size than is known to
> > it, provided they are zeroed out. So libbpf will just zero out
> > meta_off/meta_len fields, and contents of the metadata section.
> >
> > As for the size, it adds just 8 + 4 + 19 * 4 = 88 bytes to the overall
> > BTF size. It's nothing. I didn't count the total size for your
> > approach, but at the very least it would be 19 * 2 * sizeof(struct
> > btf_type) (=12) = 456, but that's super conservative.
> >
> > Note also that each btf_type can always have a name (described by
> > btf_type->name_off), so generic BTF tools can easily output what is
> > the name of the skipped entity, regardless of its actual kind. Tools
> > can also point out how many nested elements it is supposed to have.
> > Both are quite nice features, IMO.
> >
> > Anyways, that's what I had in mind. I think we should bite a bullet
> > and do it, so that future extensions can make use of this
> > self-describing metadata.
> >
> > Thoughts?
> >
>
> It'll work, a few specific questions we should probably resolve up front:
>
> - We can deduce the presence of the metadata info from the header length, so we
>   don't need a BTF version bump, right?

yep

>
> - from the encoding perspective, you mentioned having metadata opt-in;
>   so I presume we'd have a btf__add_metadata() API (it is zero by default so
>   accepted by the kernel I think) if --encode_metadata is set? Perhaps eventually
>   we could move to opt-out.

I'd say that btf__new() should by default produce metadata, unless
opted out through opts. But pahole should default for opt-out to not
regress on old kernels built with new pahole.

>
> - there are some cases where what is valid has evolved over time. For example,
>   kind flags have appeared for some kinds; should we have a flag for "supports kind
>   flag"? (set for struct/union/enum/fwd/eum64)?
>

"supports kind flag" seems way too specific, tbh. Seems wrong to have
such a flag.


> I can probably respin what I have, unless you want to take it on?

Let's discuss base vs split BTF identification first.

>
> [1] https://lore.kernel.org/bpf/CAEf4BzYXRT9pFmC1RqnNBmvQWGQkd0zs9rbH9z9Ug8FWOArb_Q@mail.gmail.com/
>
> >
> >> +
> >> +/* info used to encode a kind metadata field */
> >> +struct btf_meta_field {
> >> +       const char *type;
> >> +       const char *name;
> >> +       int size;
> >> +       int type_id;
> >> +};
> >> +
> >> +#define BTF_MAX_META_FIELDS             10
> >> +
> >> +#define BTF_META_FIELD(__type, __name)                                 \
> >> +       { .type = #__type, .name = #__name, .size = sizeof(__type) }
> >> +
> >> +#define BTF_KIND_STR(__kind)   #__kind
> >> +
> >> +struct btf_kind_encoding {
> >> +       struct btf_kind_desc kind;
> >> +       struct btf_meta_field meta[BTF_MAX_META_FIELDS];
> >> +};
> >> +
> >> +#define BTF_KIND(__name, __nr_meta, __meta_size, ...)                  \
> >> +       { .kind = {                                                     \
> >> +         .kind = BTF_KIND_##__name,                                    \
> >> +         .struct_name = BTF_KIND_PFX#__name,                           \
> >> +         .meta_name = BTF_KIND_META_PFX #__name,                       \
> >> +         .nr_meta = __nr_meta,                                         \
> >> +         .meta_size = __meta_size,                                     \
> >> +       }, .meta = { __VA_ARGS__ } }
> >> +
> >> +struct btf_kind_encoding kinds[] = {
> >> +       BTF_KIND(UNKN,          0,      0),
> >> +
> >> +       BTF_KIND(INT,           0,      0),
> >> +
> >> +       BTF_KIND(PTR,           0,      0),
> >> +
> >> +       BTF_KIND(ARRAY,         1,      sizeof(struct btf_array),
> >> +                                       BTF_META_FIELD(__u32, type),
> >> +                                       BTF_META_FIELD(__u32, index_type),
> >> +                                       BTF_META_FIELD(__u32, nelems)),
> >> +
> >> +       BTF_KIND(STRUCT,        0,      sizeof(struct btf_member),
> >> +                                       BTF_META_FIELD(__u32, name_off),
> >> +                                       BTF_META_FIELD(__u32, type),
> >> +                                       BTF_META_FIELD(__u32, offset)),
> >> +
> >> +       BTF_KIND(UNION,         0,      sizeof(struct btf_member),
> >> +                                       BTF_META_FIELD(__u32, name_off),
> >> +                                       BTF_META_FIELD(__u32, type),
> >> +                                       BTF_META_FIELD(__u32, offset)),
> >> +
> >> +       BTF_KIND(ENUM,          0,      sizeof(struct btf_enum),
> >> +                                       BTF_META_FIELD(__u32, name_off),
> >> +                                       BTF_META_FIELD(__s32, val)),
> >> +
> >> +       BTF_KIND(FWD,           0,      0),
> >> +
> >> +       BTF_KIND(TYPEDEF,       0,      0),
> >> +
> >> +       BTF_KIND(VOLATILE,      0,      0),
> >> +
> >> +       BTF_KIND(CONST,         0,      0),
> >> +
> >> +       BTF_KIND(RESTRICT,      0,      0),
> >> +
> >> +       BTF_KIND(FUNC,          0,      0),
> >> +
> >> +       BTF_KIND(FUNC_PROTO,    0,      sizeof(struct btf_param),
> >> +                                       BTF_META_FIELD(__u32, name_off),
> >> +                                       BTF_META_FIELD(__u32, type)),
> >> +
> >> +       BTF_KIND(VAR,           1,      sizeof(struct btf_var),
> >> +                                       BTF_META_FIELD(__u32, linkage)),
> >> +
> >> +       BTF_KIND(DATASEC,       0,      sizeof(struct btf_var_secinfo),
> >> +                                       BTF_META_FIELD(__u32, type),
> >> +                                       BTF_META_FIELD(__u32, offset),
> >> +                                       BTF_META_FIELD(__u32, size)),
> >> +
> >> +
> >> +       BTF_KIND(FLOAT,         0,      0),
> >> +
> >> +       BTF_KIND(DECL_TAG,      1,      sizeof(struct btf_decl_tag),
> >> +                                       BTF_META_FIELD(__s32, component_idx)),
> >> +
> >> +       BTF_KIND(TYPE_TAG,      0,      0),
> >> +
> >> +       BTF_KIND(ENUM64,        0,      sizeof(struct btf_enum64),
> >> +                                       BTF_META_FIELD(__u32, name_off),
> >> +                                       BTF_META_FIELD(__u32, val_lo32),
> >> +                                       BTF_META_FIELD(__u32, val_hi32)),
> >> +};
> >> +
> >> +/* Try to add representations of the kinds supported to BTF provided.  This will allow parsers
> >> + * to decode kinds they do not support and skip over them.
> >> + */
> >> +int btf__add_kinds(struct btf *btf)
> >> +{
> >> +       int btf_type_id, __u32_id, __s32_id, struct_type_id;
> >> +       char name[64];
> >> +       int i;
> >> +
> >> +       /* should have base types; if not bootstrap them. */
> >> +       __u32_id = btf__find_by_name(btf, "__u32");
> >> +       if (__u32_id < 0) {
> >> +               __s32 unsigned_int_id = btf__find_by_name(btf, "unsigned int");
> >> +
> >> +               if (unsigned_int_id < 0)
> >> +                       unsigned_int_id = btf__add_int(btf, "unsigned int", 4, 0);
> >> +               __u32_id = btf__add_typedef(btf, "__u32", unsigned_int_id);
> >> +       }
> >> +       __s32_id = btf__find_by_name(btf, "__s32");
> >> +       if (__s32_id < 0) {
> >> +               __s32 int_id = btf__find_by_name_kind(btf, "int", BTF_KIND_INT);
> >> +
> >> +               if (int_id < 0)
> >> +                       int_id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
> >> +               __s32_id = btf__add_typedef(btf, "__s32", int_id);
> >> +       }
> >> +
> >> +       /* add "struct __btf_type" if not already present. */
> >> +       btf_type_id = btf__find_by_name(btf, "__btf_type");
> >> +       if (btf_type_id < 0) {
> >> +               __s32 union_id = btf__add_union(btf, NULL, sizeof(__u32));
> >> +
> >> +               btf__add_field(btf, "size", __u32_id, 0, 0);
> >> +               btf__add_field(btf, "type", __u32_id, 0, 0);
> >> +
> >> +               btf_type_id = btf__add_struct(btf, "__btf_type", sizeof(struct btf_type));
> >> +               btf__add_field(btf, "name_off", __u32_id, 0, 0);
> >> +               btf__add_field(btf, "info", __u32_id, sizeof(__u32) * 8, 0);
> >> +               btf__add_field(btf, NULL, union_id, sizeof(__u32) * 16, 0);
> >> +       }
> >> +
> >> +       for (i = 0; i < ARRAY_SIZE(kinds); i++) {
> >> +               struct btf_kind_encoding *kind = &kinds[i];
> >> +               int meta_id, array_id = 0;
> >> +
> >> +               if (btf__find_by_name(btf, kind->kind.struct_name) > 0)
> >> +                       continue;
> >> +
> >> +               if (kind->kind.meta_size != 0) {
> >> +                       struct btf_meta_field *field;
> >> +                       __u32 bit_offset = 0;
> >> +                       int j;
> >> +
> >> +                       meta_id = btf__add_struct(btf, kind->kind.meta_name, kind->kind.meta_size);
> >> +
> >> +                       for (j = 0; bit_offset < kind->kind.meta_size * 8; j++) {
> >> +                               field = &kind->meta[j];
> >> +
> >> +                               field->type_id = btf__find_by_name(btf, field->type);
> >> +                               if (field->type_id < 0) {
> >> +                                       pr_debug("cannot find type '%s' for kind '%s' field '%s'\n",
> >> +                                                kind->meta[j].type, kind->kind.struct_name,
> >> +                                                kind->meta[j].name);
> >> +                               } else {
> >> +                                       btf__add_field(btf, field->name, field->type_id, bit_offset, 0);
> >> +                               }
> >> +                               bit_offset += field->size * 8;
> >> +                       }
> >> +                       array_id = btf__add_array(btf, __u32_id, meta_id,
> >> +                                                 kind->kind.nr_meta);
> >> +
> >> +               }
> >> +               struct_type_id = btf__add_struct(btf, kind->kind.struct_name,
> >> +                                                sizeof(struct btf_type) +
> >> +                                                (kind->kind.nr_meta * kind->kind.meta_size));
> >> +               btf__add_field(btf, "type", btf_type_id, 0, 0);
> >> +               if (kind->kind.meta_size != 0)
> >> +                       btf__add_field(btf, "meta", array_id, sizeof(struct btf_type) * 8, 0);
> >> +               snprintf(name, sizeof(name), BTF_KIND_PFX "%u", i);
> >> +               btf__add_typedef(btf, name, struct_type_id);
> >> +       }
> >> +       return 0;
> >> +}
> >> diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
> >> index 8e6880d..a054082 100644
> >> --- a/tools/lib/bpf/btf.h
> >> +++ b/tools/lib/bpf/btf.h
> >> @@ -219,6 +219,16 @@ LIBBPF_API int btf__add_datasec_var_info(struct btf *btf, int var_type_id,
> >>  LIBBPF_API int btf__add_decl_tag(struct btf *btf, const char *value, int ref_type_id,
> >>                             int component_idx);
> >>
> >> +/**
> >> + * @brief **btf__add_kinds()** adds BTF representations of the kind encoding for
> >> + * all of the kinds known to libbpf.  This ensures that when BTF is encoded, it
> >> + * will include enough information for parsers to decode (and skip over) kinds
> >> + * that the parser does not know about yet.  This ensures that an older BTF
> >> + * parser can read newer BTF, and avoids the need for the BTF encoder to limit
> >> + * which kinds it emits to make decoding easier.
> >> + */
> >> +LIBBPF_API int btf__add_kinds(struct btf *btf);
> >> +
> >>  struct btf_dedup_opts {
> >>         size_t sz;
> >>         /* optional .BTF.ext info to dedup along the main BTF info */
> >> diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
> >> index 71bf569..6121ff1 100644
> >> --- a/tools/lib/bpf/libbpf.map
> >> +++ b/tools/lib/bpf/libbpf.map
> >> @@ -375,6 +375,7 @@ LIBBPF_1.1.0 {
> >>                 bpf_link_get_fd_by_id_opts;
> >>                 bpf_map_get_fd_by_id_opts;
> >>                 bpf_prog_get_fd_by_id_opts;
> >> +               btf__add_kinds;
> >>                 user_ring_buffer__discard;
> >>                 user_ring_buffer__free;
> >>                 user_ring_buffer__new;
> >> --
> >> 1.8.3.1
> >>

Re: [RFC bpf-next 2/5] libbpf: provide libbpf API to encode BTF kind information

[Alan Maguire]

On 29/11/2022 17:01, Andrii Nakryiko wrote:
> On Tue, Nov 29, 2022 at 5:51 AM Alan Maguire <alan.maguire@oracle.com> wrote:
>>
<snip>>>> I really don't like this approach, even if *technically* it would
>>> work. But even if so, it would add quite a bunch of size to BTF just
>>> to self-describe it.
>>>
>>> Let's go again (and in more detail) over my alternative proposal I
>>> briefly described in another email thread.
>>>
>>> So, what I'm proposing is similar in spirit and solves all the same
>>> goals you have (and actually some more, I'll point this out below).
>>> The only downside is that we'll need to, again, teach kernel to
>>> understand this BTF format extension to allow kernel to use it (so we
>>> still will need an opt-in flag for pahole, unfortunately, but
>>> hopefully just this one time). That's pretty much the only downside.
>>> But it's more compact, simpler and more straightforward, more elegant
>>> (IMO), and it is easy for libbpf to sanitize it for old kernels.
>>>
>>> Ok, so it's pretty much completely described by these changes:
>>>
>>> --- a/include/uapi/linux/btf.h
>>> +++ b/include/uapi/linux/btf.h
>>> @@ -8,6 +8,21 @@
>>>  #define BTF_MAGIC      0xeB9F
>>>  #define BTF_VERSION    1
>>>
>>> +struct btf_kind_meta {
>>> +       /* extra flags, initially define just one:
>>> +        * 0x01 - required or optional (is it safe to skip if unknown)
>>> +        */
>>> +       __u16 flags;
>>> +       __u8 info_sz;
>>> +       __u8 elem_sz;
>>> +};
>>> +
>>> +struct btf_metadata {
>>> +       __u8 kind_meta_cnt;
>>> +       __u32 :0;
>>> +       struct btf_kind_meta[];
>>> +};
>>> +
>>>  struct btf_header {
>>>         __u16   magic;
>>>         __u8    version;
>>> @@ -19,6 +34,8 @@ struct btf_header {
>>>         __u32   type_len;       /* length of type section       */
>>>         __u32   str_off;        /* offset of string section     */
>>>         __u32   str_len;        /* length of string section     */
>>> +       __u32   meta_off;
>>> +       __u32   meta_len;
>>>  };
>>>
>>
>> Ok, if we're going this route though, let's try to think through any
>> other info we need to add so the format changes are a one-time thing.
>> We should add flags too. One current use-case would be the
>> "is this BTF standalone, or does it require base BTF?" [1]. Either using
>> an existing value in the header flags field, or using the space for a flags
>> field in  struct btf_metadata would probably make sense.
> 
> Yes, it's a good idea. But instead of a flag, I wonder if we should
> add some sort of "build ID" concept here, so that we can check
> validity of base BTF as expected by split BTF?
>

I think that would be valuable; it would be great to be able
to spot up-front an incompatibility between split and base
BTF. Are you thinking a hash over the type and string sections
or similar? Any such id shouldn't require actual BTF parsing
I think, since a simple validation could occur absent actual
parsing of the base BTF object. Would we maintain an id 
for base and split BTF, or just record the base id in split BTF
to validate the base? Not needing to recompute the base id
each time for module BTF generation seems like it would make 
it worthwhile to record the BTF id of the current object as well 
as the id of the base object it is built upon.

So something like

struct btf_metadata {
	__u32 id;
	__u32 base_id;
	__u8 kind_meta_cnt;
	__u32 :0;
	struct btf_kind_meta[];
};

...where a 0 base_id implies the object is a root/standalone BTF object?

 
>>
>> Do we have any other outstanding issues with BTF that would be eased
>> by some sort of up-front declaration? If we can at least tackle those
>> things at once, the pain will be somewhat less when updating the toolchain.
> 
> Base vs split BTF + some check whether base BTF is valid is the only
> thing that currently comes to mind.
>

The topic of multiple levels of split BTF has come up before, but I don't 
think that has any additional implications from a metadata perspective;
each level would specify the base_id of the level below.

>>
>>>
>>> So, we add meta_off/meta_len fields to btf_header, which, if non-zero,
>>> will point to a piece of metadata (4-byte aligned) that's described by
>>> struct btf_metadata.
>>>
>>> In btf_metadata, the first byte records the number of known BTF kinds,
>>> we have three more bytes for extra flags or counters for
>>> extensibility, they should be zeroed out right now.
>>>
>>
>> Right; see above for one flags use-case.
>>
>>> After these 4 bytes we have kind_meta_cnt struct btf_kind_meta
>>> entries, each 4-byte long. It's a 1-indexed array, where each entry
>>> corresponds to sequentially numbered BTF kinds. First two bytes are
>>> reserved for flags and stuff like that. Among those, I think the most
>>> useful right now would be the "optional flag". If set, it would mean
>>> that generally speaking it's safe to skip types of that kind without
>>> losing integrity of the data. So e.g., we could have used that for
>>> DECL_TAGS, or perhaps even for FUNCs, if we had this metadata back
>>> then, as these kinds are, generally speaking, not referenced from
>>> other types (not 100% for FUNCs, as we can have FUNC externs, but
>>> those came later). Anyways, for kernel needs we can say that optional
>>> kinds don't cause failure to validate BTF.
>>>
>>
>> This would definitely be useful; but are you saying here that
>> a struct with a reference to an unknown kind should fail BTF
>> validation (something like a struct with an enum64 member parsed by a
>> libbpf prior to enum64 support)? Not sure there's any alternative
>> for a case like that...
> 
> From the kernel validation point -- yes, probably. From generic
> tooling and libbpf-side -- perhaps not. I think kernel will always
> have to be pretty strict due to security reasons.
> 
> 
>>
>>> *But for security reasons we should make the kernel zero-out
>>> corresponding parts of type information, just to prevent injection of
>>> well-known data by malicious user*.
>>>
>>> Next, to the meat of the proposal. info_sz is size in bytes of an
>>> additional singular information (e.g., btf_array for ARRAY kind,
>>> 4-byte info for INT kind, etc) that goes after common 12-byte struct
>>> btf_type. It can be zero, of course. elem_sz is a size in bytes of
>>> each nested element (field info for STRUCT, arg info for FUNC_ARG,
>>> etc). Number of elements is defined by btf_vlen(t), which works for
>>> any kind, regardless if it's known or not. If elem_sz is zero, KIND
>>> can't have nested elements (and thus if vlen is non-zero, that's a
>>> corruption).
>>>
>>> That's it. We don't allow mixing differently-sized nested elements
>>> within a single kind, but we don't have that today and we don't have
>>> any meaningful ways to express this. And I don't think we'd want to do
>>> this anyways (there are way to work around that if absolutely
>>> necessary, as well).
>>>
>>> From libbpf's point of view, this metadata section is easy to
>>> sanitize, as kernel allows btf_headers of bigger size than is known to
>>> it, provided they are zeroed out. So libbpf will just zero out
>>> meta_off/meta_len fields, and contents of the metadata section.
>>>
>>> As for the size, it adds just 8 + 4 + 19 * 4 = 88 bytes to the overall
>>> BTF size. It's nothing. I didn't count the total size for your
>>> approach, but at the very least it would be 19 * 2 * sizeof(struct
>>> btf_type) (=12) = 456, but that's super conservative.
>>>
>>> Note also that each btf_type can always have a name (described by
>>> btf_type->name_off), so generic BTF tools can easily output what is
>>> the name of the skipped entity, regardless of its actual kind. Tools
>>> can also point out how many nested elements it is supposed to have.
>>> Both are quite nice features, IMO.
>>>
>>> Anyways, that's what I had in mind. I think we should bite a bullet
>>> and do it, so that future extensions can make use of this
>>> self-describing metadata.
>>>
>>> Thoughts?
>>>
>>
>> It'll work, a few specific questions we should probably resolve up front:
>>
>> - We can deduce the presence of the metadata info from the header length, so we
>>   don't need a BTF version bump, right?
> 
> yep
> 
>>
>> - from the encoding perspective, you mentioned having metadata opt-in;
>>   so I presume we'd have a btf__add_metadata() API (it is zero by default so
>>   accepted by the kernel I think) if --encode_metadata is set? Perhaps eventually
>>   we could move to opt-out.
> 
> I'd say that btf__new() should by default produce metadata, unless
> opted out through opts. But pahole should default for opt-out to not
> regress on old kernels built with new pahole.
> 

Ok; we'll need new APIs btf__new_empty[_split]_opts() to handle this I think.

Alan

>>
>> - there are some cases where what is valid has evolved over time. For example,
>>   kind flags have appeared for some kinds; should we have a flag for "supports kind
>>   flag"? (set for struct/union/enum/fwd/eum64)?
>>
> 
> "supports kind flag" seems way too specific, tbh. Seems wrong to have
> such a flag.
> 
> 
>> I can probably respin what I have, unless you want to take it on?
> 
> Let's discuss base vs split BTF identification first.
> 
>>
>> [1] https://lore.kernel.org/bpf/CAEf4BzYXRT9pFmC1RqnNBmvQWGQkd0zs9rbH9z9Ug8FWOArb_Q@mail.gmail.com/
>>
>>>
>>>> +
>>>> +/* info used to encode a kind metadata field */
>>>> +struct btf_meta_field {
>>>> +       const char *type;
>>>> +       const char *name;
>>>> +       int size;
>>>> +       int type_id;
>>>> +};
>>>> +
>>>> +#define BTF_MAX_META_FIELDS             10
>>>> +
>>>> +#define BTF_META_FIELD(__type, __name)                                 \
>>>> +       { .type = #__type, .name = #__name, .size = sizeof(__type) }
>>>> +
>>>> +#define BTF_KIND_STR(__kind)   #__kind
>>>> +
>>>> +struct btf_kind_encoding {
>>>> +       struct btf_kind_desc kind;
>>>> +       struct btf_meta_field meta[BTF_MAX_META_FIELDS];
>>>> +};
>>>> +
>>>> +#define BTF_KIND(__name, __nr_meta, __meta_size, ...)                  \
>>>> +       { .kind = {                                                     \
>>>> +         .kind = BTF_KIND_##__name,                                    \
>>>> +         .struct_name = BTF_KIND_PFX#__name,                           \
>>>> +         .meta_name = BTF_KIND_META_PFX #__name,                       \
>>>> +         .nr_meta = __nr_meta,                                         \
>>>> +         .meta_size = __meta_size,                                     \
>>>> +       }, .meta = { __VA_ARGS__ } }
>>>> +
>>>> +struct btf_kind_encoding kinds[] = {
>>>> +       BTF_KIND(UNKN,          0,      0),
>>>> +
>>>> +       BTF_KIND(INT,           0,      0),
>>>> +
>>>> +       BTF_KIND(PTR,           0,      0),
>>>> +
>>>> +       BTF_KIND(ARRAY,         1,      sizeof(struct btf_array),
>>>> +                                       BTF_META_FIELD(__u32, type),
>>>> +                                       BTF_META_FIELD(__u32, index_type),
>>>> +                                       BTF_META_FIELD(__u32, nelems)),
>>>> +
>>>> +       BTF_KIND(STRUCT,        0,      sizeof(struct btf_member),
>>>> +                                       BTF_META_FIELD(__u32, name_off),
>>>> +                                       BTF_META_FIELD(__u32, type),
>>>> +                                       BTF_META_FIELD(__u32, offset)),
>>>> +
>>>> +       BTF_KIND(UNION,         0,      sizeof(struct btf_member),
>>>> +                                       BTF_META_FIELD(__u32, name_off),
>>>> +                                       BTF_META_FIELD(__u32, type),
>>>> +                                       BTF_META_FIELD(__u32, offset)),
>>>> +
>>>> +       BTF_KIND(ENUM,          0,      sizeof(struct btf_enum),
>>>> +                                       BTF_META_FIELD(__u32, name_off),
>>>> +                                       BTF_META_FIELD(__s32, val)),
>>>> +
>>>> +       BTF_KIND(FWD,           0,      0),
>>>> +
>>>> +       BTF_KIND(TYPEDEF,       0,      0),
>>>> +
>>>> +       BTF_KIND(VOLATILE,      0,      0),
>>>> +
>>>> +       BTF_KIND(CONST,         0,      0),
>>>> +
>>>> +       BTF_KIND(RESTRICT,      0,      0),
>>>> +
>>>> +       BTF_KIND(FUNC,          0,      0),
>>>> +
>>>> +       BTF_KIND(FUNC_PROTO,    0,      sizeof(struct btf_param),
>>>> +                                       BTF_META_FIELD(__u32, name_off),
>>>> +                                       BTF_META_FIELD(__u32, type)),
>>>> +
>>>> +       BTF_KIND(VAR,           1,      sizeof(struct btf_var),
>>>> +                                       BTF_META_FIELD(__u32, linkage)),
>>>> +
>>>> +       BTF_KIND(DATASEC,       0,      sizeof(struct btf_var_secinfo),
>>>> +                                       BTF_META_FIELD(__u32, type),
>>>> +                                       BTF_META_FIELD(__u32, offset),
>>>> +                                       BTF_META_FIELD(__u32, size)),
>>>> +
>>>> +
>>>> +       BTF_KIND(FLOAT,         0,      0),
>>>> +
>>>> +       BTF_KIND(DECL_TAG,      1,      sizeof(struct btf_decl_tag),
>>>> +                                       BTF_META_FIELD(__s32, component_idx)),
>>>> +
>>>> +       BTF_KIND(TYPE_TAG,      0,      0),
>>>> +
>>>> +       BTF_KIND(ENUM64,        0,      sizeof(struct btf_enum64),
>>>> +                                       BTF_META_FIELD(__u32, name_off),
>>>> +                                       BTF_META_FIELD(__u32, val_lo32),
>>>> +                                       BTF_META_FIELD(__u32, val_hi32)),
>>>> +};
>>>> +
>>>> +/* Try to add representations of the kinds supported to BTF provided.  This will allow parsers
>>>> + * to decode kinds they do not support and skip over them.
>>>> + */
>>>> +int btf__add_kinds(struct btf *btf)
>>>> +{
>>>> +       int btf_type_id, __u32_id, __s32_id, struct_type_id;
>>>> +       char name[64];
>>>> +       int i;
>>>> +
>>>> +       /* should have base types; if not bootstrap them. */
>>>> +       __u32_id = btf__find_by_name(btf, "__u32");
>>>> +       if (__u32_id < 0) {
>>>> +               __s32 unsigned_int_id = btf__find_by_name(btf, "unsigned int");
>>>> +
>>>> +               if (unsigned_int_id < 0)
>>>> +                       unsigned_int_id = btf__add_int(btf, "unsigned int", 4, 0);
>>>> +               __u32_id = btf__add_typedef(btf, "__u32", unsigned_int_id);
>>>> +       }
>>>> +       __s32_id = btf__find_by_name(btf, "__s32");
>>>> +       if (__s32_id < 0) {
>>>> +               __s32 int_id = btf__find_by_name_kind(btf, "int", BTF_KIND_INT);
>>>> +
>>>> +               if (int_id < 0)
>>>> +                       int_id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
>>>> +               __s32_id = btf__add_typedef(btf, "__s32", int_id);
>>>> +       }
>>>> +
>>>> +       /* add "struct __btf_type" if not already present. */
>>>> +       btf_type_id = btf__find_by_name(btf, "__btf_type");
>>>> +       if (btf_type_id < 0) {
>>>> +               __s32 union_id = btf__add_union(btf, NULL, sizeof(__u32));
>>>> +
>>>> +               btf__add_field(btf, "size", __u32_id, 0, 0);
>>>> +               btf__add_field(btf, "type", __u32_id, 0, 0);
>>>> +
>>>> +               btf_type_id = btf__add_struct(btf, "__btf_type", sizeof(struct btf_type));
>>>> +               btf__add_field(btf, "name_off", __u32_id, 0, 0);
>>>> +               btf__add_field(btf, "info", __u32_id, sizeof(__u32) * 8, 0);
>>>> +               btf__add_field(btf, NULL, union_id, sizeof(__u32) * 16, 0);
>>>> +       }
>>>> +
>>>> +       for (i = 0; i < ARRAY_SIZE(kinds); i++) {
>>>> +               struct btf_kind_encoding *kind = &kinds[i];
>>>> +               int meta_id, array_id = 0;
>>>> +
>>>> +               if (btf__find_by_name(btf, kind->kind.struct_name) > 0)
>>>> +                       continue;
>>>> +
>>>> +               if (kind->kind.meta_size != 0) {
>>>> +                       struct btf_meta_field *field;
>>>> +                       __u32 bit_offset = 0;
>>>> +                       int j;
>>>> +
>>>> +                       meta_id = btf__add_struct(btf, kind->kind.meta_name, kind->kind.meta_size);
>>>> +
>>>> +                       for (j = 0; bit_offset < kind->kind.meta_size * 8; j++) {
>>>> +                               field = &kind->meta[j];
>>>> +
>>>> +                               field->type_id = btf__find_by_name(btf, field->type);
>>>> +                               if (field->type_id < 0) {
>>>> +                                       pr_debug("cannot find type '%s' for kind '%s' field '%s'\n",
>>>> +                                                kind->meta[j].type, kind->kind.struct_name,
>>>> +                                                kind->meta[j].name);
>>>> +                               } else {
>>>> +                                       btf__add_field(btf, field->name, field->type_id, bit_offset, 0);
>>>> +                               }
>>>> +                               bit_offset += field->size * 8;
>>>> +                       }
>>>> +                       array_id = btf__add_array(btf, __u32_id, meta_id,
>>>> +                                                 kind->kind.nr_meta);
>>>> +
>>>> +               }
>>>> +               struct_type_id = btf__add_struct(btf, kind->kind.struct_name,
>>>> +                                                sizeof(struct btf_type) +
>>>> +                                                (kind->kind.nr_meta * kind->kind.meta_size));
>>>> +               btf__add_field(btf, "type", btf_type_id, 0, 0);
>>>> +               if (kind->kind.meta_size != 0)
>>>> +                       btf__add_field(btf, "meta", array_id, sizeof(struct btf_type) * 8, 0);
>>>> +               snprintf(name, sizeof(name), BTF_KIND_PFX "%u", i);
>>>> +               btf__add_typedef(btf, name, struct_type_id);
>>>> +       }
>>>> +       return 0;
>>>> +}
>>>> diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
>>>> index 8e6880d..a054082 100644
>>>> --- a/tools/lib/bpf/btf.h
>>>> +++ b/tools/lib/bpf/btf.h
>>>> @@ -219,6 +219,16 @@ LIBBPF_API int btf__add_datasec_var_info(struct btf *btf, int var_type_id,
>>>>  LIBBPF_API int btf__add_decl_tag(struct btf *btf, const char *value, int ref_type_id,
>>>>                             int component_idx);
>>>>
>>>> +/**
>>>> + * @brief **btf__add_kinds()** adds BTF representations of the kind encoding for
>>>> + * all of the kinds known to libbpf.  This ensures that when BTF is encoded, it
>>>> + * will include enough information for parsers to decode (and skip over) kinds
>>>> + * that the parser does not know about yet.  This ensures that an older BTF
>>>> + * parser can read newer BTF, and avoids the need for the BTF encoder to limit
>>>> + * which kinds it emits to make decoding easier.
>>>> + */
>>>> +LIBBPF_API int btf__add_kinds(struct btf *btf);
>>>> +
>>>>  struct btf_dedup_opts {
>>>>         size_t sz;
>>>>         /* optional .BTF.ext info to dedup along the main BTF info */
>>>> diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
>>>> index 71bf569..6121ff1 100644
>>>> --- a/tools/lib/bpf/libbpf.map
>>>> +++ b/tools/lib/bpf/libbpf.map
>>>> @@ -375,6 +375,7 @@ LIBBPF_1.1.0 {
>>>>                 bpf_link_get_fd_by_id_opts;
>>>>                 bpf_map_get_fd_by_id_opts;
>>>>                 bpf_prog_get_fd_by_id_opts;
>>>> +               btf__add_kinds;
>>>>                 user_ring_buffer__discard;
>>>>                 user_ring_buffer__free;
>>>>                 user_ring_buffer__new;
>>>> --
>>>> 1.8.3.1
>>>>

Re: [RFC bpf-next 2/5] libbpf: provide libbpf API to encode BTF kind information

[Andrii Nakryiko]

On Wed, Nov 30, 2022 at 2:38 PM Alan Maguire <alan.maguire@oracle.com> wrote:
>
> On 29/11/2022 17:01, Andrii Nakryiko wrote:
> > On Tue, Nov 29, 2022 at 5:51 AM Alan Maguire <alan.maguire@oracle.com> wrote:
> >>
> <snip>>>> I really don't like this approach, even if *technically* it would
> >>> work. But even if so, it would add quite a bunch of size to BTF just
> >>> to self-describe it.
> >>>
> >>> Let's go again (and in more detail) over my alternative proposal I
> >>> briefly described in another email thread.
> >>>
> >>> So, what I'm proposing is similar in spirit and solves all the same
> >>> goals you have (and actually some more, I'll point this out below).
> >>> The only downside is that we'll need to, again, teach kernel to
> >>> understand this BTF format extension to allow kernel to use it (so we
> >>> still will need an opt-in flag for pahole, unfortunately, but
> >>> hopefully just this one time). That's pretty much the only downside.
> >>> But it's more compact, simpler and more straightforward, more elegant
> >>> (IMO), and it is easy for libbpf to sanitize it for old kernels.
> >>>
> >>> Ok, so it's pretty much completely described by these changes:
> >>>
> >>> --- a/include/uapi/linux/btf.h
> >>> +++ b/include/uapi/linux/btf.h
> >>> @@ -8,6 +8,21 @@
> >>>  #define BTF_MAGIC      0xeB9F
> >>>  #define BTF_VERSION    1
> >>>
> >>> +struct btf_kind_meta {
> >>> +       /* extra flags, initially define just one:
> >>> +        * 0x01 - required or optional (is it safe to skip if unknown)
> >>> +        */
> >>> +       __u16 flags;
> >>> +       __u8 info_sz;
> >>> +       __u8 elem_sz;
> >>> +};
> >>> +
> >>> +struct btf_metadata {
> >>> +       __u8 kind_meta_cnt;
> >>> +       __u32 :0;
> >>> +       struct btf_kind_meta[];
> >>> +};
> >>> +
> >>>  struct btf_header {
> >>>         __u16   magic;
> >>>         __u8    version;
> >>> @@ -19,6 +34,8 @@ struct btf_header {
> >>>         __u32   type_len;       /* length of type section       */
> >>>         __u32   str_off;        /* offset of string section     */
> >>>         __u32   str_len;        /* length of string section     */
> >>> +       __u32   meta_off;
> >>> +       __u32   meta_len;
> >>>  };
> >>>
> >>
> >> Ok, if we're going this route though, let's try to think through any
> >> other info we need to add so the format changes are a one-time thing.
> >> We should add flags too. One current use-case would be the
> >> "is this BTF standalone, or does it require base BTF?" [1]. Either using
> >> an existing value in the header flags field, or using the space for a flags
> >> field in  struct btf_metadata would probably make sense.
> >
> > Yes, it's a good idea. But instead of a flag, I wonder if we should
> > add some sort of "build ID" concept here, so that we can check
> > validity of base BTF as expected by split BTF?
> >
>
> I think that would be valuable; it would be great to be able
> to spot up-front an incompatibility between split and base
> BTF. Are you thinking a hash over the type and string sections
> or similar? Any such id shouldn't require actual BTF parsing
> I think, since a simple validation could occur absent actual

yep, I was thinking of just a simple CRC32 as a checksum algorithm?

> parsing of the base BTF object. Would we maintain an id
> for base and split BTF, or just record the base id in split BTF
> to validate the base? Not needing to recompute the base id
> each time for module BTF generation seems like it would make
> it worthwhile to record the BTF id of the current object as well
> as the id of the base object it is built upon.

I'd record "my checksum" and "base checksum, if split"? I presume zero
is a valid value for CRC32, so probably a separate flag for whether
BTF is split or not would be necessary after all.

>
> So something like
>
> struct btf_metadata {
>         __u32 id;
>         __u32 base_id;

so these are not IDs, that shouldn't be confused with kernel's BTF
object ID. It's checksums.

>         __u8 kind_meta_cnt;
>         __u32 :0;
>         struct btf_kind_meta[];
> };
>
> ...where a 0 base_id implies the object is a root/standalone BTF object?

see above, probably need a separate flag, because zero might be a valid checksum

>
>
> >>
> >> Do we have any other outstanding issues with BTF that would be eased
> >> by some sort of up-front declaration? If we can at least tackle those
> >> things at once, the pain will be somewhat less when updating the toolchain.
> >
> > Base vs split BTF + some check whether base BTF is valid is the only
> > thing that currently comes to mind.
> >
>
> The topic of multiple levels of split BTF has come up before, but I don't
> think that has any additional implications from a metadata perspective;
> each level would specify the base_id of the level below.

yep, it's still a split BTF, I don't think any extra stuff is needed.
Technically libbpf already supports multi-level split BTFs.

>
> >>
> >>>
> >>> So, we add meta_off/meta_len fields to btf_header, which, if non-zero,
> >>> will point to a piece of metadata (4-byte aligned) that's described by
> >>> struct btf_metadata.
> >>>
> >>> In btf_metadata, the first byte records the number of known BTF kinds,
> >>> we have three more bytes for extra flags or counters for
> >>> extensibility, they should be zeroed out right now.
> >>>
> >>
> >> Right; see above for one flags use-case.
> >>
> >>> After these 4 bytes we have kind_meta_cnt struct btf_kind_meta
> >>> entries, each 4-byte long. It's a 1-indexed array, where each entry
> >>> corresponds to sequentially numbered BTF kinds. First two bytes are
> >>> reserved for flags and stuff like that. Among those, I think the most
> >>> useful right now would be the "optional flag". If set, it would mean
> >>> that generally speaking it's safe to skip types of that kind without
> >>> losing integrity of the data. So e.g., we could have used that for
> >>> DECL_TAGS, or perhaps even for FUNCs, if we had this metadata back
> >>> then, as these kinds are, generally speaking, not referenced from
> >>> other types (not 100% for FUNCs, as we can have FUNC externs, but
> >>> those came later). Anyways, for kernel needs we can say that optional
> >>> kinds don't cause failure to validate BTF.
> >>>
> >>
> >> This would definitely be useful; but are you saying here that
> >> a struct with a reference to an unknown kind should fail BTF
> >> validation (something like a struct with an enum64 member parsed by a
> >> libbpf prior to enum64 support)? Not sure there's any alternative
> >> for a case like that...
> >
> > From the kernel validation point -- yes, probably. From generic
> > tooling and libbpf-side -- perhaps not. I think kernel will always
> > have to be pretty strict due to security reasons.
> >
> >
> >>
> >>> *But for security reasons we should make the kernel zero-out
> >>> corresponding parts of type information, just to prevent injection of
> >>> well-known data by malicious user*.
> >>>
> >>> Next, to the meat of the proposal. info_sz is size in bytes of an
> >>> additional singular information (e.g., btf_array for ARRAY kind,
> >>> 4-byte info for INT kind, etc) that goes after common 12-byte struct
> >>> btf_type. It can be zero, of course. elem_sz is a size in bytes of
> >>> each nested element (field info for STRUCT, arg info for FUNC_ARG,
> >>> etc). Number of elements is defined by btf_vlen(t), which works for
> >>> any kind, regardless if it's known or not. If elem_sz is zero, KIND
> >>> can't have nested elements (and thus if vlen is non-zero, that's a
> >>> corruption).
> >>>
> >>> That's it. We don't allow mixing differently-sized nested elements
> >>> within a single kind, but we don't have that today and we don't have
> >>> any meaningful ways to express this. And I don't think we'd want to do
> >>> this anyways (there are way to work around that if absolutely
> >>> necessary, as well).
> >>>
> >>> From libbpf's point of view, this metadata section is easy to
> >>> sanitize, as kernel allows btf_headers of bigger size than is known to
> >>> it, provided they are zeroed out. So libbpf will just zero out
> >>> meta_off/meta_len fields, and contents of the metadata section.
> >>>
> >>> As for the size, it adds just 8 + 4 + 19 * 4 = 88 bytes to the overall
> >>> BTF size. It's nothing. I didn't count the total size for your
> >>> approach, but at the very least it would be 19 * 2 * sizeof(struct
> >>> btf_type) (=12) = 456, but that's super conservative.
> >>>
> >>> Note also that each btf_type can always have a name (described by
> >>> btf_type->name_off), so generic BTF tools can easily output what is
> >>> the name of the skipped entity, regardless of its actual kind. Tools
> >>> can also point out how many nested elements it is supposed to have.
> >>> Both are quite nice features, IMO.
> >>>
> >>> Anyways, that's what I had in mind. I think we should bite a bullet
> >>> and do it, so that future extensions can make use of this
> >>> self-describing metadata.
> >>>
> >>> Thoughts?
> >>>
> >>
> >> It'll work, a few specific questions we should probably resolve up front:
> >>
> >> - We can deduce the presence of the metadata info from the header length, so we
> >>   don't need a BTF version bump, right?
> >
> > yep
> >
> >>
> >> - from the encoding perspective, you mentioned having metadata opt-in;
> >>   so I presume we'd have a btf__add_metadata() API (it is zero by default so
> >>   accepted by the kernel I think) if --encode_metadata is set? Perhaps eventually
> >>   we could move to opt-out.
> >
> > I'd say that btf__new() should by default produce metadata, unless
> > opted out through opts. But pahole should default for opt-out to not
> > regress on old kernels built with new pahole.
> >
>
> Ok; we'll need new APIs btf__new_empty[_split]_opts() to handle this I think.
>

Perhaps it's time to generalize to btf__new_opts() and support
split/non-split and data/no-data as options?

> Alan
>
> >>
> >> - there are some cases where what is valid has evolved over time. For example,
> >>   kind flags have appeared for some kinds; should we have a flag for "supports kind
> >>   flag"? (set for struct/union/enum/fwd/eum64)?
> >>
> >
> > "supports kind flag" seems way too specific, tbh. Seems wrong to have
> > such a flag.
> >
> >
> >> I can probably respin what I have, unless you want to take it on?
> >
> > Let's discuss base vs split BTF identification first.
> >
> >>
> >> [1] https://lore.kernel.org/bpf/CAEf4BzYXRT9pFmC1RqnNBmvQWGQkd0zs9rbH9z9Ug8FWOArb_Q@mail.gmail.com/
> >>
> >>>

[...]