* [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type
@ 2024-05-16 23:04 Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 1/3] libbpf: put forward declarations to btf_dump->emit_queue Eduard Zingerman
` (3 more replies)
0 siblings, 4 replies; 6+ messages in thread
From: Eduard Zingerman @ 2024-05-16 23:04 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
jose.marchesi, alan.maguire, Eduard Zingerman
This is a follow-up to the following discussion:
https://lore.kernel.org/bpf/20240503111836.25275-1-jose.marchesi@oracle.com/
As suggested by Andrii, this series adds several API functions to
allow more flexibility with btf dump:
- a function to add a type and all its dependencies to the emit queue;
- functions to provide access to the emit queue owned by btf_dump object;
- a function to print a given type (skipping any dependencies).
This should allow filtering printed types and also adding
attributes / pre-processor statements to specific types.
There are several ways to add such API:
1. The simplest in terms of code changes is to refactor
btf_dump_emit_type() to push types and forward declarations
to the emit queue, instead of printing those directly;
2. More intrusive: refactor btf_dump_emit_type() and
btf_dump_order_type() to avoid doing topological sorting twice and
put forward declarations to the emit queue at once.
This series opts for (2) as it seems to simplify library code a bit.
For the sake of discussion, source code for option (1) as available at:
https://github.com/eddyz87/bpf/tree/libbpf-sort-for-dump-api-simple
Also, this series opts for the following new API function:
int btf_dump__dump_one_type(struct btf_dump *d, __u32 id, bool fwd);
As adding _opts variant of btf_dump__dump_type seems a bit clumsy:
struct btf_dump_opts {
size_t sz;
bool fwd;
bool skip_dependencies;
bool skip_last_semi;
};
int btf_dump__dump_type_opts(struct btf_dump *d, __u32 id,
struct btf_dump_opts *opts);
but maybe community would prefer the later variant.
Eduard Zingerman (3):
libbpf: put forward declarations to btf_dump->emit_queue
libbpf: API to access btf_dump emit queue and print single type
selftests/bpf: tests for btf_dump emit queue API
tools/lib/bpf/btf.h | 33 ++
tools/lib/bpf/btf_dump.c | 363 ++++++++----------
tools/lib/bpf/libbpf.map | 4 +
.../selftests/bpf/prog_tests/btf_dump.c | 86 +++++
4 files changed, 289 insertions(+), 197 deletions(-)
--
2.34.1
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH bpf-next 1/3] libbpf: put forward declarations to btf_dump->emit_queue
2024-05-16 23:04 [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
@ 2024-05-16 23:04 ` Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 2/3] libbpf: API to access btf_dump emit queue and print single type Eduard Zingerman
` (2 subsequent siblings)
3 siblings, 0 replies; 6+ messages in thread
From: Eduard Zingerman @ 2024-05-16 23:04 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
jose.marchesi, alan.maguire, Eduard Zingerman
As a preparatory step for introducing public API for BTF topological
ordering / single type printing, this commit removes ordering logic
from btf_dump_emit_type() and moves parts necessary to compute forward
declarations to btf_dump_order_type().
Before this commit the topological ordering of types was effectively
done twice:
- first time in btf_dump_order_type(), which ordered types using only
"strong" links (one structure embedded in another);
- second time in btf_dump_emit_type() to emit forward declarations.
After this commit:
- btf_dump_emit_type() is responsible only for printing
declaration / forward declaration of a single type;
- btf_dump->emit_queue now contains pairs of form
{id, forward declaration flag};
- btf_dump->emit_state is no longer necessary,
as EMITTED state is effectively replaced by ORDERED state
in btf_dump->order_state;
Notable changes to btf_dump_order_type() logic:
- no need to return strong / weak result, emit forward declaration to
the queue for weak links instead;
- track containing type id ('cont_id'), as btf_dump_emit_type() did,
to avoid unnecessary forward declarations in recursive structs;
- PTRs can no longer be marked ORDERED (see comment in the code);
- incorporate btf_dump_emit_missing_aliases() and
btf_dump_is_blacklisted() checks from btf_dump_emit_type().
When called for e.g. PTR type pointing to a struct
btf_dump__dump_type() would previously result in an empty emit queue:
btf_dump_order_type() would have reached struct with
'through_ptr' == true, thus not adding it to the queue.
To mimic such behavior this patch adds a type filter to
btf_dump__dump_type(): only STRUCT, UNION, TYPEDEF, ENUM, ENUM64, FWD
types are ordered.
The downside of a single pass algorithm is that for the following
situation old logic would have avoided extra forward declaration:
struct bar {};
struct foo { /* Suppose btf_dump__dump_type(foo) */
struct bar *a; /* is called first. */
struct bar b;
};
The btf_dump_order_type() would have ordered 'bar' before 'foo',
btf_dump_emit_type() would have been first called for 'bar' thus
avoiding forward declaration for 'sturct bar' when processing 'foo'.
In contrast, new logic would act as follows:
- when processing foo->a forward declaration for 'bar' would be enqueued;
- when processing foo->b full declaration for 'bar' would be enqueued;
In practice this does not seem to be a big issue, number of forward
declarations in vmlinux.h (for BPF selftests config) compared:
- before this patch: 1223
- after this patch: 1236
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
tools/lib/bpf/btf_dump.c | 328 +++++++++++++++++----------------------
1 file changed, 145 insertions(+), 183 deletions(-)
diff --git a/tools/lib/bpf/btf_dump.c b/tools/lib/bpf/btf_dump.c
index 5dbca76b953f..1d0ec57d01a9 100644
--- a/tools/lib/bpf/btf_dump.c
+++ b/tools/lib/bpf/btf_dump.c
@@ -36,24 +36,16 @@ enum btf_dump_type_order_state {
ORDERED,
};
-enum btf_dump_type_emit_state {
- NOT_EMITTED,
- EMITTING,
- EMITTED,
-};
-
/* per-type auxiliary state */
struct btf_dump_type_aux_state {
/* topological sorting state */
enum btf_dump_type_order_state order_state: 2;
- /* emitting state used to determine the need for forward declaration */
- enum btf_dump_type_emit_state emit_state: 2;
- /* whether forward declaration was already emitted */
- __u8 fwd_emitted: 1;
/* whether unique non-duplicate name was already assigned */
__u8 name_resolved: 1;
/* whether type is referenced from any other type */
__u8 referenced: 1;
+ /* whether forward declaration was already ordered */
+ __u8 fwd_ordered: 1;
};
/* indent string length; one indent string is added for each indent level */
@@ -93,7 +85,10 @@ struct btf_dump {
size_t cached_names_cap;
/* topo-sorted list of dependent type definitions */
- __u32 *emit_queue;
+ struct {
+ __u32 id:31;
+ __u32 fwd:1;
+ } *emit_queue;
int emit_queue_cap;
int emit_queue_cnt;
@@ -208,7 +203,6 @@ static int btf_dump_resize(struct btf_dump *d)
if (d->last_id == 0) {
/* VOID is special */
d->type_states[0].order_state = ORDERED;
- d->type_states[0].emit_state = EMITTED;
}
/* eagerly determine referenced types for anon enums */
@@ -255,8 +249,8 @@ void btf_dump__free(struct btf_dump *d)
free(d);
}
-static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr);
-static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id);
+static int btf_dump_order_type(struct btf_dump *d, __u32 id, __u32 cont_id, bool through_ptr);
+static void btf_dump_emit_type(struct btf_dump *d, __u32 id, bool fwd);
/*
* Dump BTF type in a compilable C syntax, including all the necessary
@@ -276,6 +270,7 @@ static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id);
*/
int btf_dump__dump_type(struct btf_dump *d, __u32 id)
{
+ const struct btf_type *t;
int err, i;
if (id >= btf__type_cnt(d->btf))
@@ -286,12 +281,23 @@ int btf_dump__dump_type(struct btf_dump *d, __u32 id)
return libbpf_err(err);
d->emit_queue_cnt = 0;
- err = btf_dump_order_type(d, id, false);
- if (err < 0)
- return libbpf_err(err);
+ t = btf_type_by_id(d->btf, id);
+ switch (btf_kind(t)) {
+ case BTF_KIND_STRUCT:
+ case BTF_KIND_UNION:
+ case BTF_KIND_TYPEDEF:
+ case BTF_KIND_ENUM:
+ case BTF_KIND_ENUM64:
+ case BTF_KIND_FWD:
+ err = btf_dump_order_type(d, id, id, false);
+ if (err < 0)
+ return libbpf_err(err);
+ default:
+ break;
+ };
for (i = 0; i < d->emit_queue_cnt; i++)
- btf_dump_emit_type(d, d->emit_queue[i], 0 /*top-level*/);
+ btf_dump_emit_type(d, d->emit_queue[i].id, d->emit_queue[i].fwd);
return 0;
}
@@ -374,9 +380,9 @@ static int btf_dump_mark_referenced(struct btf_dump *d)
return 0;
}
-static int btf_dump_add_emit_queue_id(struct btf_dump *d, __u32 id)
+static int __btf_dump_add_emit_queue_id(struct btf_dump *d, __u32 id, bool fwd)
{
- __u32 *new_queue;
+ typeof(d->emit_queue[0]) *new_queue = NULL;
size_t new_cap;
if (d->emit_queue_cnt >= d->emit_queue_cap) {
@@ -388,10 +394,45 @@ static int btf_dump_add_emit_queue_id(struct btf_dump *d, __u32 id)
d->emit_queue_cap = new_cap;
}
- d->emit_queue[d->emit_queue_cnt++] = id;
+ d->emit_queue[d->emit_queue_cnt].id = id;
+ d->emit_queue[d->emit_queue_cnt].fwd = fwd;
+ d->emit_queue_cnt++;
return 0;
}
+static int btf_dump_add_emit_queue_id(struct btf_dump *d, __u32 id)
+{
+ return __btf_dump_add_emit_queue_id(d, id, false);
+}
+
+static int btf_dump_add_emit_queue_fwd(struct btf_dump *d, __u32 id)
+{
+ struct btf_dump_type_aux_state *tstate = &d->type_states[id];
+
+ if (tstate->fwd_ordered)
+ return 0;
+
+ tstate->fwd_ordered = 1;
+ return __btf_dump_add_emit_queue_id(d, id, true);
+}
+
+static bool btf_dump_emit_missing_aliases(struct btf_dump *d, __u32 id, bool dry_run);
+
+static bool btf_dump_is_blacklisted(struct btf_dump *d, __u32 id)
+{
+ const struct btf_type *t = btf__type_by_id(d->btf, id);
+
+ /* __builtin_va_list is a compiler built-in, which causes compilation
+ * errors, when compiling w/ different compiler, then used to compile
+ * original code (e.g., GCC to compile kernel, Clang to use generated
+ * C header from BTF). As it is built-in, it should be already defined
+ * properly internally in compiler.
+ */
+ if (t->name_off == 0)
+ return false;
+ return strcmp(btf_name_of(d, t->name_off), "__builtin_va_list") == 0;
+}
+
/*
* Determine order of emitting dependent types and specified type to satisfy
* C compilation rules. This is done through topological sorting with an
@@ -441,32 +482,33 @@ static int btf_dump_add_emit_queue_id(struct btf_dump *d, __u32 id)
* The rule is as follows. Given a chain of BTF types from X to Y, if there is
* BTF_KIND_PTR type in the chain and at least one non-anonymous type
* Z (excluding X, including Y), then link is weak. Otherwise, it's strong.
- * Weak/strong relationship is determined recursively during DFS traversal and
- * is returned as a result from btf_dump_order_type().
+ * Weak/strong relationship is determined recursively during DFS traversal.
+ *
+ * When type id is reached via a weak link a forward declaration for
+ * that type is added to the emit queue, otherwise "full" declaration
+ * is added to the emit queue.
+ *
+ * We also keep track of "containing struct/union type ID" to determine when
+ * we reference it from inside and thus can avoid emitting unnecessary forward
+ * declaration.
*
* btf_dump_order_type() is trying to avoid unnecessary forward declarations,
* but it is not guaranteeing that no extraneous forward declarations will be
* emitted.
*
* To avoid extra work, algorithm marks some of BTF types as ORDERED, when
- * it's done with them, but not for all (e.g., VOLATILE, CONST, RESTRICT,
+ * it's done with them, but not for all (e.g., PTR, VOLATILE, CONST, RESTRICT,
* ARRAY, FUNC_PROTO), as weak/strong semantics for those depends on the
* entire graph path, so depending where from one came to that BTF type, it
* might cause weak or strong ordering. For types like STRUCT/UNION/INT/ENUM,
* once they are processed, there is no need to do it again, so they are
- * marked as ORDERED. We can mark PTR as ORDERED as well, as it semi-forces
- * weak link, unless subsequent referenced STRUCT/UNION/ENUM is anonymous. But
- * in any case, once those are processed, no need to do it again, as the
- * result won't change.
+ * marked as ORDERED.
*
* Returns:
- * - 1, if type is part of strong link (so there is strong topological
- * ordering requirements);
- * - 0, if type is part of weak link (so can be satisfied through forward
- * declaration);
+ * - 0, on success;
* - <0, on error (e.g., unsatisfiable type loop detected).
*/
-static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr)
+static int btf_dump_order_type(struct btf_dump *d, __u32 id, __u32 cont_id, bool through_ptr)
{
/*
* Order state is used to detect strong link cycles, but only for BTF
@@ -486,48 +528,78 @@ static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr)
/* return true, letting typedefs know that it's ok to be emitted */
if (tstate->order_state == ORDERED)
- return 1;
+ return 0;
t = btf__type_by_id(d->btf, id);
if (tstate->order_state == ORDERING) {
/* type loop, but resolvable through fwd declaration */
- if (btf_is_composite(t) && through_ptr && t->name_off != 0)
- return 0;
+ if (btf_is_composite(t) && through_ptr && t->name_off != 0) {
+ if (id != cont_id)
+ return btf_dump_add_emit_queue_fwd(d, id);
+ else
+ return 0;
+ }
pr_warn("unsatisfiable type cycle, id:[%u]\n", id);
return -ELOOP;
}
switch (btf_kind(t)) {
case BTF_KIND_INT:
+ tstate->order_state = ORDERED;
+ if (btf_dump_emit_missing_aliases(d, id, true))
+ return btf_dump_add_emit_queue_id(d, id);
+ else
+ return 0;
case BTF_KIND_FLOAT:
tstate->order_state = ORDERED;
return 0;
case BTF_KIND_PTR:
- err = btf_dump_order_type(d, t->type, true);
- tstate->order_state = ORDERED;
+ /* Depending on whether pointer is a part of a recursive struct
+ * declaration, it might not necessitate generation of a forward
+ * declaration for the target type, e.g.:
+ *
+ * struct foo {
+ * struct foo *p; // no need for forward declaration
+ * }
+ *
+ * struct bar {
+ * struct foo *p; // forward declaration is needed
+ * }
+ *
+ * Hence, don't mark pointer as ORDERED, to allow traversal
+ * to the target type and comparison with 'cont_id'.
+ */
+ err = btf_dump_order_type(d, t->type, cont_id, true);
return err;
case BTF_KIND_ARRAY:
- return btf_dump_order_type(d, btf_array(t)->type, false);
+ return btf_dump_order_type(d, btf_array(t)->type, cont_id, false);
case BTF_KIND_STRUCT:
case BTF_KIND_UNION: {
const struct btf_member *m = btf_members(t);
+ __u32 new_cont_id;
+
/*
* struct/union is part of strong link, only if it's embedded
* (so no ptr in a path) or it's anonymous (so has to be
* defined inline, even if declared through ptr)
*/
- if (through_ptr && t->name_off != 0)
- return 0;
+ if (through_ptr && t->name_off != 0) {
+ if (id != cont_id)
+ return btf_dump_add_emit_queue_fwd(d, id);
+ else
+ return 0;
+ }
tstate->order_state = ORDERING;
+ new_cont_id = t->name_off == 0 ? cont_id : id;
vlen = btf_vlen(t);
for (i = 0; i < vlen; i++, m++) {
- err = btf_dump_order_type(d, m->type, false);
+ err = btf_dump_order_type(d, m->type, new_cont_id, false);
if (err < 0)
return err;
}
@@ -539,7 +611,7 @@ static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr)
}
tstate->order_state = ORDERED;
- return 1;
+ return 0;
}
case BTF_KIND_ENUM:
case BTF_KIND_ENUM64:
@@ -555,51 +627,44 @@ static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr)
return err;
}
tstate->order_state = ORDERED;
- return 1;
+ return 0;
case BTF_KIND_TYPEDEF: {
- int is_strong;
-
- is_strong = btf_dump_order_type(d, t->type, through_ptr);
- if (is_strong < 0)
- return is_strong;
-
- /* typedef is similar to struct/union w.r.t. fwd-decls */
- if (through_ptr && !is_strong)
+ if (btf_dump_is_blacklisted(d, id))
return 0;
+ err = btf_dump_order_type(d, t->type, t->type, through_ptr);
+ if (err < 0)
+ return err;
+
/* typedef is always a named definition */
err = btf_dump_add_emit_queue_id(d, id);
if (err)
return err;
d->type_states[id].order_state = ORDERED;
- return 1;
+ return 0;
}
case BTF_KIND_VOLATILE:
case BTF_KIND_CONST:
case BTF_KIND_RESTRICT:
case BTF_KIND_TYPE_TAG:
- return btf_dump_order_type(d, t->type, through_ptr);
+ return btf_dump_order_type(d, t->type, cont_id, through_ptr);
case BTF_KIND_FUNC_PROTO: {
const struct btf_param *p = btf_params(t);
- bool is_strong;
- err = btf_dump_order_type(d, t->type, through_ptr);
+ err = btf_dump_order_type(d, t->type, cont_id, through_ptr);
if (err < 0)
return err;
- is_strong = err > 0;
vlen = btf_vlen(t);
for (i = 0; i < vlen; i++, p++) {
- err = btf_dump_order_type(d, p->type, through_ptr);
+ err = btf_dump_order_type(d, p->type, cont_id, through_ptr);
if (err < 0)
return err;
- if (err > 0)
- is_strong = true;
}
- return is_strong;
+ return err;
}
case BTF_KIND_FUNC:
case BTF_KIND_VAR:
@@ -613,9 +678,6 @@ static int btf_dump_order_type(struct btf_dump *d, __u32 id, bool through_ptr)
}
}
-static void btf_dump_emit_missing_aliases(struct btf_dump *d, __u32 id,
- const struct btf_type *t);
-
static void btf_dump_emit_struct_fwd(struct btf_dump *d, __u32 id,
const struct btf_type *t);
static void btf_dump_emit_struct_def(struct btf_dump *d, __u32 id,
@@ -649,73 +711,33 @@ static const char *btf_dump_ident_name(struct btf_dump *d, __u32 id);
static size_t btf_dump_name_dups(struct btf_dump *d, struct hashmap *name_map,
const char *orig_name);
-static bool btf_dump_is_blacklisted(struct btf_dump *d, __u32 id)
-{
- const struct btf_type *t = btf__type_by_id(d->btf, id);
-
- /* __builtin_va_list is a compiler built-in, which causes compilation
- * errors, when compiling w/ different compiler, then used to compile
- * original code (e.g., GCC to compile kernel, Clang to use generated
- * C header from BTF). As it is built-in, it should be already defined
- * properly internally in compiler.
- */
- if (t->name_off == 0)
- return false;
- return strcmp(btf_name_of(d, t->name_off), "__builtin_va_list") == 0;
-}
-
/*
* Emit C-syntax definitions of types from chains of BTF types.
*
- * High-level handling of determining necessary forward declarations are handled
- * by btf_dump_emit_type() itself, but all nitty-gritty details of emitting type
+ * All nitty-gritty details of emitting type
* declarations/definitions in C syntax are handled by a combo of
* btf_dump_emit_type_decl()/btf_dump_emit_type_chain() w/ delegation to
* corresponding btf_dump_emit_*_{def,fwd}() functions.
*
- * We also keep track of "containing struct/union type ID" to determine when
- * we reference it from inside and thus can avoid emitting unnecessary forward
- * declaration.
- *
* This algorithm is designed in such a way, that even if some error occurs
* (either technical, e.g., out of memory, or logical, i.e., malformed BTF
* that doesn't comply to C rules completely), algorithm will try to proceed
* and produce as much meaningful output as possible.
*/
-static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id)
+static void btf_dump_emit_type(struct btf_dump *d, __u32 id, bool fwd)
{
- struct btf_dump_type_aux_state *tstate = &d->type_states[id];
- bool top_level_def = cont_id == 0;
const struct btf_type *t;
__u16 kind;
- if (tstate->emit_state == EMITTED)
- return;
-
t = btf__type_by_id(d->btf, id);
kind = btf_kind(t);
- if (tstate->emit_state == EMITTING) {
- if (tstate->fwd_emitted)
- return;
-
+ if (fwd) {
switch (kind) {
case BTF_KIND_STRUCT:
case BTF_KIND_UNION:
- /*
- * if we are referencing a struct/union that we are
- * part of - then no need for fwd declaration
- */
- if (id == cont_id)
- return;
- if (t->name_off == 0) {
- pr_warn("anonymous struct/union loop, id:[%u]\n",
- id);
- return;
- }
btf_dump_emit_struct_fwd(d, id, t);
btf_dump_printf(d, ";\n\n");
- tstate->fwd_emitted = 1;
break;
case BTF_KIND_TYPEDEF:
/*
@@ -723,11 +745,8 @@ static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id)
* was emitted, but it can be used only for "weak"
* references through pointer only, not for embedding
*/
- if (!btf_dump_is_blacklisted(d, id)) {
- btf_dump_emit_typedef_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- }
- tstate->fwd_emitted = 1;
+ btf_dump_emit_typedef_def(d, id, t, 0);
+ btf_dump_printf(d, ";\n\n");
break;
default:
break;
@@ -739,36 +758,18 @@ static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id)
switch (kind) {
case BTF_KIND_INT:
/* Emit type alias definitions if necessary */
- btf_dump_emit_missing_aliases(d, id, t);
-
- tstate->emit_state = EMITTED;
+ btf_dump_emit_missing_aliases(d, id, false);
break;
case BTF_KIND_ENUM:
case BTF_KIND_ENUM64:
- if (top_level_def) {
- btf_dump_emit_enum_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- }
- tstate->emit_state = EMITTED;
- break;
- case BTF_KIND_PTR:
- case BTF_KIND_VOLATILE:
- case BTF_KIND_CONST:
- case BTF_KIND_RESTRICT:
- case BTF_KIND_TYPE_TAG:
- btf_dump_emit_type(d, t->type, cont_id);
- break;
- case BTF_KIND_ARRAY:
- btf_dump_emit_type(d, btf_array(t)->type, cont_id);
+ btf_dump_emit_enum_def(d, id, t, 0);
+ btf_dump_printf(d, ";\n\n");
break;
case BTF_KIND_FWD:
btf_dump_emit_fwd_def(d, id, t);
btf_dump_printf(d, ";\n\n");
- tstate->emit_state = EMITTED;
break;
case BTF_KIND_TYPEDEF:
- tstate->emit_state = EMITTING;
- btf_dump_emit_type(d, t->type, id);
/*
* typedef can server as both definition and forward
* declaration; at this stage someone depends on
@@ -776,55 +777,14 @@ static void btf_dump_emit_type(struct btf_dump *d, __u32 id, __u32 cont_id)
* through pointer), so unless we already did it,
* emit typedef as a forward declaration
*/
- if (!tstate->fwd_emitted && !btf_dump_is_blacklisted(d, id)) {
- btf_dump_emit_typedef_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- }
- tstate->emit_state = EMITTED;
+ btf_dump_emit_typedef_def(d, id, t, 0);
+ btf_dump_printf(d, ";\n\n");
break;
case BTF_KIND_STRUCT:
case BTF_KIND_UNION:
- tstate->emit_state = EMITTING;
- /* if it's a top-level struct/union definition or struct/union
- * is anonymous, then in C we'll be emitting all fields and
- * their types (as opposed to just `struct X`), so we need to
- * make sure that all types, referenced from struct/union
- * members have necessary forward-declarations, where
- * applicable
- */
- if (top_level_def || t->name_off == 0) {
- const struct btf_member *m = btf_members(t);
- __u16 vlen = btf_vlen(t);
- int i, new_cont_id;
-
- new_cont_id = t->name_off == 0 ? cont_id : id;
- for (i = 0; i < vlen; i++, m++)
- btf_dump_emit_type(d, m->type, new_cont_id);
- } else if (!tstate->fwd_emitted && id != cont_id) {
- btf_dump_emit_struct_fwd(d, id, t);
- btf_dump_printf(d, ";\n\n");
- tstate->fwd_emitted = 1;
- }
-
- if (top_level_def) {
- btf_dump_emit_struct_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- tstate->emit_state = EMITTED;
- } else {
- tstate->emit_state = NOT_EMITTED;
- }
- break;
- case BTF_KIND_FUNC_PROTO: {
- const struct btf_param *p = btf_params(t);
- __u16 n = btf_vlen(t);
- int i;
-
- btf_dump_emit_type(d, t->type, cont_id);
- for (i = 0; i < n; i++, p++)
- btf_dump_emit_type(d, p->type, cont_id);
-
+ btf_dump_emit_struct_def(d, id, t, 0);
+ btf_dump_printf(d, ";\n\n");
break;
- }
default:
break;
}
@@ -1037,19 +997,21 @@ static const char *missing_base_types[][2] = {
{ "__Poly128_t", "unsigned __int128" },
};
-static void btf_dump_emit_missing_aliases(struct btf_dump *d, __u32 id,
- const struct btf_type *t)
+static bool btf_dump_emit_missing_aliases(struct btf_dump *d, __u32 id, bool dry_run)
{
const char *name = btf_dump_type_name(d, id);
int i;
for (i = 0; i < ARRAY_SIZE(missing_base_types); i++) {
- if (strcmp(name, missing_base_types[i][0]) == 0) {
+ if (strcmp(name, missing_base_types[i][0]) != 0)
+ continue;
+ if (!dry_run)
btf_dump_printf(d, "typedef %s %s;\n\n",
missing_base_types[i][1], name);
- break;
- }
+ return true;
}
+
+ return false;
}
static void btf_dump_emit_enum_fwd(struct btf_dump *d, __u32 id,
--
2.34.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH bpf-next 2/3] libbpf: API to access btf_dump emit queue and print single type
2024-05-16 23:04 [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 1/3] libbpf: put forward declarations to btf_dump->emit_queue Eduard Zingerman
@ 2024-05-16 23:04 ` Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 3/3] selftests/bpf: tests for btf_dump emit queue API Eduard Zingerman
2024-05-17 0:02 ` [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
3 siblings, 0 replies; 6+ messages in thread
From: Eduard Zingerman @ 2024-05-16 23:04 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
jose.marchesi, alan.maguire, Eduard Zingerman, Andrii Nakryiko
Add several API functions to allow more flexibility with btf dump:
- int btf_dump__order_type(struct btf_dump *d, __u32 id);
adds a type and all it's dependencies to the emit queue
in topological order;
- struct btf_dump_emit_queue_item *btf_dump__emit_queue(struct btf_dump *d);
__u32 btf_dump__emit_queue_cnt(struct btf_dump *d);
provide access to the emit queue owned by btf_dump object;
- int btf_dump__dump_one_type(struct btf_dump *d, __u32 id, bool fwd);
prints a given type in C format (skipping any dependencies).
This API should allow to do the following on the libbpf client side:
- filter printed types using arbitrary criteria;
- add arbitrary type attributes or pre-processor statements for
selected types.
This is a follow-up to the following discussion:
https://lore.kernel.org/bpf/20240503111836.25275-1-jose.marchesi@oracle.com/
Suggested-by: Andrii Nakryiko <andrii.nakryiko@gmail.com>
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
tools/lib/bpf/btf.h | 33 ++++++++++++++++++++++
tools/lib/bpf/btf_dump.c | 61 ++++++++++++++++++++++------------------
tools/lib/bpf/libbpf.map | 4 +++
3 files changed, 71 insertions(+), 27 deletions(-)
diff --git a/tools/lib/bpf/btf.h b/tools/lib/bpf/btf.h
index 8e6880d91c84..81d70ac35562 100644
--- a/tools/lib/bpf/btf.h
+++ b/tools/lib/bpf/btf.h
@@ -249,6 +249,39 @@ LIBBPF_API void btf_dump__free(struct btf_dump *d);
LIBBPF_API int btf_dump__dump_type(struct btf_dump *d, __u32 id);
+/* Dumps C language definition or forward declaration for type **id**:
+ * - returns 1 if type is printable;
+ * - returns 0 if type is non-printable.
+ */
+LIBBPF_API int btf_dump__dump_one_type(struct btf_dump *d, __u32 id, bool fwd);
+
+/* **struct btf_dump** tracks a list of types that should be dumped,
+ * these types are sorted in the topological order satisfying C language semantics:
+ * - if type A includes type B (e.g. A is a struct with a field of type B),
+ * then B comes before A;
+ * - if type A references type B via a pointer
+ * (e.g. A is a struct with a field of type pointer to B),
+ * then B's forward declaration comes before A.
+ *
+ * **struct btf_dump_emit_queue_item** represents a single entry of the emit queue.
+ */
+struct btf_dump_emit_queue_item {
+ __u32 id:31;
+ __u32 fwd:1;
+};
+
+/* Adds type **id** and it's dependencies to the emit queue. */
+LIBBPF_API int btf_dump__order_type(struct btf_dump *d, __u32 id);
+
+/* Provides access to currently accumulated emit queue,
+ * returned pointer is owned by **struct btf_dump** and should not be
+ * freed explicitly.
+ */
+LIBBPF_API struct btf_dump_emit_queue_item *btf_dump__emit_queue(struct btf_dump *d);
+
+/* Returns the size of currently accumulated emit queue */
+LIBBPF_API __u32 btf_dump__emit_queue_cnt(struct btf_dump *d);
+
struct btf_dump_emit_type_decl_opts {
/* size of this struct, for forward/backward compatiblity */
size_t sz;
diff --git a/tools/lib/bpf/btf_dump.c b/tools/lib/bpf/btf_dump.c
index 1d0ec57d01a9..cb233f891582 100644
--- a/tools/lib/bpf/btf_dump.c
+++ b/tools/lib/bpf/btf_dump.c
@@ -85,10 +85,7 @@ struct btf_dump {
size_t cached_names_cap;
/* topo-sorted list of dependent type definitions */
- struct {
- __u32 id:31;
- __u32 fwd:1;
- } *emit_queue;
+ struct btf_dump_emit_queue_item *emit_queue;
int emit_queue_cap;
int emit_queue_cnt;
@@ -250,7 +247,6 @@ void btf_dump__free(struct btf_dump *d)
}
static int btf_dump_order_type(struct btf_dump *d, __u32 id, __u32 cont_id, bool through_ptr);
-static void btf_dump_emit_type(struct btf_dump *d, __u32 id, bool fwd);
/*
* Dump BTF type in a compilable C syntax, including all the necessary
@@ -296,12 +292,32 @@ int btf_dump__dump_type(struct btf_dump *d, __u32 id)
break;
};
- for (i = 0; i < d->emit_queue_cnt; i++)
- btf_dump_emit_type(d, d->emit_queue[i].id, d->emit_queue[i].fwd);
+ for (i = 0; i < d->emit_queue_cnt; i++) {
+ err = btf_dump__dump_one_type(d, d->emit_queue[i].id, d->emit_queue[i].fwd);
+ if (err < 0)
+ return libbpf_err(err);
+ if (err > 0)
+ btf_dump_printf(d, ";\n\n");
+ }
return 0;
}
+int btf_dump__order_type(struct btf_dump *d, __u32 id)
+{
+ return btf_dump_order_type(d, id, id, false);
+}
+
+struct btf_dump_emit_queue_item *btf_dump__emit_queue(struct btf_dump *d)
+{
+ return d->emit_queue;
+}
+
+__u32 btf_dump__emit_queue_cnt(struct btf_dump *d)
+{
+ return d->emit_queue_cnt;
+}
+
/*
* Mark all types that are referenced from any other type. This is used to
* determine top-level anonymous enums that need to be emitted as an
@@ -382,7 +398,7 @@ static int btf_dump_mark_referenced(struct btf_dump *d)
static int __btf_dump_add_emit_queue_id(struct btf_dump *d, __u32 id, bool fwd)
{
- typeof(d->emit_queue[0]) *new_queue = NULL;
+ struct btf_dump_emit_queue_item *new_queue = NULL;
size_t new_cap;
if (d->emit_queue_cnt >= d->emit_queue_cap) {
@@ -724,7 +740,7 @@ static size_t btf_dump_name_dups(struct btf_dump *d, struct hashmap *name_map,
* that doesn't comply to C rules completely), algorithm will try to proceed
* and produce as much meaningful output as possible.
*/
-static void btf_dump_emit_type(struct btf_dump *d, __u32 id, bool fwd)
+int btf_dump__dump_one_type(struct btf_dump *d, __u32 id, bool fwd)
{
const struct btf_type *t;
__u16 kind;
@@ -737,8 +753,7 @@ static void btf_dump_emit_type(struct btf_dump *d, __u32 id, bool fwd)
case BTF_KIND_STRUCT:
case BTF_KIND_UNION:
btf_dump_emit_struct_fwd(d, id, t);
- btf_dump_printf(d, ";\n\n");
- break;
+ return 1;
case BTF_KIND_TYPEDEF:
/*
* for typedef fwd_emitted means typedef definition
@@ -746,29 +761,23 @@ static void btf_dump_emit_type(struct btf_dump *d, __u32 id, bool fwd)
* references through pointer only, not for embedding
*/
btf_dump_emit_typedef_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- break;
+ return 1;
default:
- break;
+ return 0;
}
-
- return;
}
switch (kind) {
case BTF_KIND_INT:
/* Emit type alias definitions if necessary */
- btf_dump_emit_missing_aliases(d, id, false);
- break;
+ return btf_dump_emit_missing_aliases(d, id, false);
case BTF_KIND_ENUM:
case BTF_KIND_ENUM64:
btf_dump_emit_enum_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- break;
+ return 1;
case BTF_KIND_FWD:
btf_dump_emit_fwd_def(d, id, t);
- btf_dump_printf(d, ";\n\n");
- break;
+ return 1;
case BTF_KIND_TYPEDEF:
/*
* typedef can server as both definition and forward
@@ -778,15 +787,13 @@ static void btf_dump_emit_type(struct btf_dump *d, __u32 id, bool fwd)
* emit typedef as a forward declaration
*/
btf_dump_emit_typedef_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- break;
+ return 1;
case BTF_KIND_STRUCT:
case BTF_KIND_UNION:
btf_dump_emit_struct_def(d, id, t, 0);
- btf_dump_printf(d, ";\n\n");
- break;
+ return 1;
default:
- break;
+ return 0;
}
}
diff --git a/tools/lib/bpf/libbpf.map b/tools/lib/bpf/libbpf.map
index c1ce8aa3520b..137e4cbaa7a7 100644
--- a/tools/lib/bpf/libbpf.map
+++ b/tools/lib/bpf/libbpf.map
@@ -422,4 +422,8 @@ LIBBPF_1.5.0 {
bpf_program__attach_sockmap;
ring__consume_n;
ring_buffer__consume_n;
+ btf_dump__emit_queue;
+ btf_dump__emit_queue_cnt;
+ btf_dump__order_type;
+ btf_dump__dump_one_type;
} LIBBPF_1.4.0;
--
2.34.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH bpf-next 3/3] selftests/bpf: tests for btf_dump emit queue API
2024-05-16 23:04 [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 1/3] libbpf: put forward declarations to btf_dump->emit_queue Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 2/3] libbpf: API to access btf_dump emit queue and print single type Eduard Zingerman
@ 2024-05-16 23:04 ` Eduard Zingerman
2024-05-17 0:02 ` [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
3 siblings, 0 replies; 6+ messages in thread
From: Eduard Zingerman @ 2024-05-16 23:04 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
jose.marchesi, alan.maguire, Eduard Zingerman
Test cases for btf_dump__dump_one_type() and company:
- peek a type, save it's dependencies to the emit queue,
print the content of the emit queue, expect only relevant
dependencies;
- print a forward declaration for a single type,
expect no dependencies in the output;
- print a full dependencies for a type,
expect no dependencies in the output.
Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
.../selftests/bpf/prog_tests/btf_dump.c | 86 +++++++++++++++++++
1 file changed, 86 insertions(+)
diff --git a/tools/testing/selftests/bpf/prog_tests/btf_dump.c b/tools/testing/selftests/bpf/prog_tests/btf_dump.c
index e9ea38aa8248..04f32472e221 100644
--- a/tools/testing/selftests/bpf/prog_tests/btf_dump.c
+++ b/tools/testing/selftests/bpf/prog_tests/btf_dump.c
@@ -255,6 +255,90 @@ static void test_btf_dump_incremental(void)
btf__free(btf);
}
+static void test_btf_dump_emit_queue(void)
+{
+ struct btf_dump_emit_queue_item *items;
+ struct btf_dump *d = NULL;
+ struct btf *btf = NULL;
+ u32 union_simple;
+ int err, i, cnt;
+
+ btf = btf__parse_elf("btf_dump_test_case_syntax.bpf.o", NULL);
+ if (!ASSERT_OK_PTR(btf, "btf_parse_elf")) {
+ err = -PTR_ERR(btf);
+ btf = NULL;
+ goto err_out;
+ }
+
+ union_simple = btf__find_by_name_kind(btf, "union_simple", BTF_KIND_UNION);
+ ASSERT_GT(union_simple, 0, "'union_simple' id");
+
+ dump_buf_file = open_memstream(&dump_buf, &dump_buf_sz);
+ if (!ASSERT_OK_PTR(dump_buf_file, "dump_memstream"))
+ return;
+ d = btf_dump__new(btf, btf_dump_printf, dump_buf_file, NULL);
+ if (!ASSERT_OK(libbpf_get_error(d), "btf_dump__new"))
+ goto err_out;
+
+ err = btf_dump__order_type(d, union_simple);
+ ASSERT_OK(err, "order type 'union_simple'");
+ cnt = btf_dump__emit_queue_cnt(d);
+ items = btf_dump__emit_queue(d);
+ for (i = 1; i < cnt; i++) {
+ err = btf_dump__dump_one_type(d, items[i].id, items[i].fwd);
+ if (err > 0)
+ fprintf(dump_buf_file, ";\n\n");
+ }
+
+ fflush(dump_buf_file);
+ dump_buf[dump_buf_sz] = 0;
+
+ ASSERT_STREQ(dump_buf,
+"union union_empty {};\n"
+"\n"
+"union union_simple {\n"
+" void *ptr;\n"
+" int num;\n"
+" int_t num2;\n"
+" union union_empty u;\n"
+"};\n\n", "c_dump1");
+
+ btf_dump__free(d);
+ d = btf_dump__new(btf, btf_dump_printf, dump_buf_file, NULL);
+ if (!ASSERT_OK(libbpf_get_error(d), "btf_dump__new")) {
+ d = NULL;
+ goto err_out;
+ }
+ err = btf_dump__order_type(d, union_simple);
+ ASSERT_OK(err, "order type 'union_simple'");
+
+ rewind(dump_buf_file);
+ btf_dump__dump_one_type(d, union_simple, true);
+ fflush(dump_buf_file);
+ dump_buf[dump_buf_sz] = 0;
+
+ ASSERT_STREQ(dump_buf, "union union_simple", "c_dump2");
+
+ rewind(dump_buf_file);
+ btf_dump__dump_one_type(d, union_simple, false);
+ fflush(dump_buf_file);
+ dump_buf[dump_buf_sz] = 0;
+
+ ASSERT_STREQ(dump_buf,
+"union union_simple {\n"
+" void *ptr;\n"
+" int num;\n"
+" int_t num2;\n"
+" union union_empty u;\n"
+"}", "c_dump3");
+
+err_out:
+ fclose(dump_buf_file);
+ free(dump_buf);
+ btf_dump__free(d);
+ btf__free(btf);
+}
+
#define STRSIZE 4096
static void btf_dump_snprintf(void *ctx, const char *fmt, va_list args)
@@ -873,6 +957,8 @@ void test_btf_dump() {
}
if (test__start_subtest("btf_dump: incremental"))
test_btf_dump_incremental();
+ if (test__start_subtest("btf_dump: emit queue"))
+ test_btf_dump_emit_queue();
btf = libbpf_find_kernel_btf();
if (!ASSERT_OK_PTR(btf, "no kernel BTF found"))
--
2.34.1
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type
2024-05-16 23:04 [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
` (2 preceding siblings ...)
2024-05-16 23:04 ` [PATCH bpf-next 3/3] selftests/bpf: tests for btf_dump emit queue API Eduard Zingerman
@ 2024-05-17 0:02 ` Eduard Zingerman
2024-05-17 2:03 ` Eduard Zingerman
3 siblings, 1 reply; 6+ messages in thread
From: Eduard Zingerman @ 2024-05-17 0:02 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
jose.marchesi, alan.maguire
On Thu, 2024-05-16 at 16:04 -0700, Eduard Zingerman wrote:
> This is a follow-up to the following discussion:
> https://lore.kernel.org/bpf/20240503111836.25275-1-jose.marchesi@oracle.com/
>
> As suggested by Andrii, this series adds several API functions to
> allow more flexibility with btf dump:
> - a function to add a type and all its dependencies to the emit queue;
> - functions to provide access to the emit queue owned by btf_dump object;
> - a function to print a given type (skipping any dependencies).
The series fails on the CI despite passing local testing,
I'll submit v2 when ready.
[...]
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type
2024-05-17 0:02 ` [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
@ 2024-05-17 2:03 ` Eduard Zingerman
0 siblings, 0 replies; 6+ messages in thread
From: Eduard Zingerman @ 2024-05-17 2:03 UTC (permalink / raw)
To: bpf, ast
Cc: andrii, daniel, martin.lau, kernel-team, yonghong.song,
jose.marchesi, alan.maguire
On Thu, 2024-05-16 at 17:02 -0700, Eduard Zingerman wrote:
> On Thu, 2024-05-16 at 16:04 -0700, Eduard Zingerman wrote:
> > This is a follow-up to the following discussion:
> > https://lore.kernel.org/bpf/20240503111836.25275-1-jose.marchesi@oracle.com/
> >
> > As suggested by Andrii, this series adds several API functions to
> > allow more flexibility with btf dump:
> > - a function to add a type and all its dependencies to the emit queue;
> > - functions to provide access to the emit queue owned by btf_dump object;
> > - a function to print a given type (skipping any dependencies).
>
> The series fails on the CI despite passing local testing,
> I'll submit v2 when ready.
>
> [...]
The bug was caused by a logical error in typedefs handling.
Do not mark typedef as ORDERED, always emit a forward declaration for
it instead. Otherwise the following situation would be troublesome:
typedef struct foo foo_alias;
struct foo {};
struct root {
foo_alias *a; <-- foo->a leads to forward declaration for 'foo',
foo_alias b; if 'foo_alias' is marked ORDERED
}; foo->b will not traverse to generate
full declaration for 'foo'.
The patch below fixes error.
CI builds seem ok:
https://github.com/kernel-patches/bpf/pull/7052
---
diff --git a/tools/lib/bpf/btf_dump.c b/tools/lib/bpf/btf_dump.c
index cb233f891582..7e845ad9ca9e 100644
--- a/tools/lib/bpf/btf_dump.c
+++ b/tools/lib/bpf/btf_dump.c
@@ -653,12 +653,9 @@ static int btf_dump_order_type(struct btf_dump *d, __u32 id, __u32 cont_id, bool
if (err < 0)
return err;
- /* typedef is always a named definition */
- err = btf_dump_add_emit_queue_id(d, id);
+ err = btf_dump_add_emit_queue_fwd(d, id);
if (err)
return err;
-
- d->type_states[id].order_state = ORDERED;
return 0;
}
case BTF_KIND_VOLATILE:
^ permalink raw reply related [flat|nested] 6+ messages in thread
end of thread, other threads:[~2024-05-17 2:03 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-05-16 23:04 [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 1/3] libbpf: put forward declarations to btf_dump->emit_queue Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 2/3] libbpf: API to access btf_dump emit queue and print single type Eduard Zingerman
2024-05-16 23:04 ` [PATCH bpf-next 3/3] selftests/bpf: tests for btf_dump emit queue API Eduard Zingerman
2024-05-17 0:02 ` [PATCH bpf-next 0/3] API to access btf_dump emit queue and print single type Eduard Zingerman
2024-05-17 2:03 ` Eduard Zingerman
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).