Re: [PATCH v4 10/19] gendwarfksyms: Limit structure expansion

Petr Pavlu
2024-10-16T14:16:25Z

On 10/8/24 20:38, Sami Tolvanen wrote:
> Expand each structure type only once per exported symbol. This
> is necessary to support self-referential structures, which would
> otherwise result in infinite recursion, but is still sufficient for
> catching ABI changes.
>
> For pointers, limit structure expansion after the first pointer
> in the symbol type. This should be plenty for detecting ABI
> differences, but it stops us from pulling in half the kernel for
> types that contain pointers to large kernel data structures, like
> task_struct, for example.
>
> Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
> Acked-by: Neal Gompa <neal@gompa.dev>
> ---
> scripts/gendwarfksyms/Makefile | 1 +
> scripts/gendwarfksyms/cache.c | 44 +++++++++++
> scripts/gendwarfksyms/dwarf.c | 109 +++++++++++++++++++++++---
> scripts/gendwarfksyms/gendwarfksyms.h | 37 +++++++++
> 4 files changed, 182 insertions(+), 9 deletions(-)
> create mode 100644 scripts/gendwarfksyms/cache.c
>
> diff --git a/scripts/gendwarfksyms/Makefile b/scripts/gendwarfksyms/Makefile
> index c0d4ce50fc27..c06145d84df8 100644
> --- a/scripts/gendwarfksyms/Makefile
> +++ b/scripts/gendwarfksyms/Makefile
> @@ -2,6 +2,7 @@
> hostprogs-always-y += gendwarfksyms
>
> gendwarfksyms-objs += gendwarfksyms.o
> +gendwarfksyms-objs += cache.o
> gendwarfksyms-objs += die.o
> gendwarfksyms-objs += dwarf.o
> gendwarfksyms-objs += symbols.o
> diff --git a/scripts/gendwarfksyms/cache.c b/scripts/gendwarfksyms/cache.c
> new file mode 100644
> index 000000000000..2f1517133a20
> --- /dev/null
> +++ b/scripts/gendwarfksyms/cache.c
> @@ -0,0 +1,44 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Copyright (C) 2024 Google LLC
> + */
> +
> +#include "gendwarfksyms.h"
> +
> +struct expanded {
> + uintptr_t addr;
> + struct hlist_node hash;
> +};
> +
> +void __cache_mark_expanded(struct expansion_cache *ec, uintptr_t addr)
> +{
> + struct expanded *es;
> +
> + es = xmalloc(sizeof(struct expanded));
> + es->addr = addr;
> + hash_add(ec->cache, &es->hash, addr_hash(addr));
> +}
> +
> +bool __cache_was_expanded(struct expansion_cache *ec, uintptr_t addr)
> +{
> + struct expanded *es;
> +
> + hash_for_each_possible(ec->cache, es, hash, addr_hash(addr)) {
> + if (es->addr == addr)
> + return true;
> + }
> +
> + return false;
> +}
> +
> +void cache_clear_expanded(struct expansion_cache *ec)
> +{
> + struct hlist_node *tmp;
> + struct expanded *es;
> +
> + hash_for_each_safe(ec->cache, es, tmp, hash) {
> + free(es);
> + }
> +
> + hash_init(ec->cache);
> +}
> diff --git a/scripts/gendwarfksyms/dwarf.c b/scripts/gendwarfksyms/dwarf.c
> index f5cebbdcc212..51dd8e82f9e7 100644
> --- a/scripts/gendwarfksyms/dwarf.c
> +++ b/scripts/gendwarfksyms/dwarf.c
> @@ -26,6 +26,7 @@ static void process_linebreak(struct die *cache, int n)
> !dwarf_form##attr(&da, value); \
> }
>
> +DEFINE_GET_ATTR(flag, bool)
> DEFINE_GET_ATTR(udata, Dwarf_Word)
>
> static bool get_ref_die_attr(Dwarf_Die *die, unsigned int id, Dwarf_Die *value)
> @@ -79,6 +80,13 @@ static bool match_export_symbol(struct state *state, Dwarf_Die *die)
> return !!state->sym;
> }
>
> +static bool is_declaration(Dwarf_Die *die)
> +{
> + bool value;
> +
> + return get_flag_attr(die, DW_AT_declaration, &value) && value;
> +}
> +
> /*
> * Type string processing
> */
> @@ -455,19 +463,28 @@ static void __process_structure_type(struct state *state, struct die *cache,
> die_callback_t process_func,
> die_match_callback_t match_func)
> {
> + bool is_decl;
> +
> process(cache, type);
> process_fqn(cache, die);
> process(cache, " {");
> process_linebreak(cache, 1);
>
> - check(process_die_container(state, cache, die, process_func,
> - match_func));
> + is_decl = is_declaration(die);
> +
> + if (!is_decl && state->expand.expand) {
> + cache_mark_expanded(&state->expansion_cache, die->addr);
> + check(process_die_container(state, cache, die, process_func,
> + match_func));
> + }
>
> process_linebreak(cache, -1);
> process(cache, "}");
>
> - process_byte_size_attr(cache, die);
> - process_alignment_attr(cache, die);
> + if (!is_decl && state->expand.expand) {
> + process_byte_size_attr(cache, die);
> + process_alignment_attr(cache, die);
> + }
> }
>
> #define DEFINE_PROCESS_STRUCTURE_TYPE(structure) \
> @@ -520,7 +537,7 @@ static void process_unspecified_type(struct state *state, struct die *cache,
> Dwarf_Die *die)
> {
> /*
> - * These can be emitted for stand-elone assembly code, which means we
> + * These can be emitted for stand-alone assembly code, which means we
> * might run into them in vmlinux.o.
> */
> process(cache, "unspecified_type");

Nit: This hunk should be folded into patch #9 ("gendwarfksyms: Expand
structure types").

> @@ -552,6 +569,42 @@ static void process_cached(struct state *state, struct die *cache,
> }
> }
>
> +static void state_init(struct state *state)
> +{
> + state->expand.expand = true;
> + state->expand.ptr_depth = 0;
> + state->expand.ptr_expansion_depth = 0;
> + hash_init(state->expansion_cache.cache);
> +}
> +
> +static void expansion_state_restore(struct expansion_state *state,
> + struct expansion_state *saved)
> +{
> + state->expand = saved->expand;
> + state->ptr_depth = saved->ptr_depth;
> + state->ptr_expansion_depth = saved->ptr_expansion_depth;
> +}
> +
> +static void expansion_state_save(struct expansion_state *state,
> + struct expansion_state *saved)
> +{
> + expansion_state_restore(saved, state);
> +}
> +
> +static bool is_pointer_type(int tag)
> +{
> + return tag == DW_TAG_pointer_type || tag == DW_TAG_reference_type;
> +}
> +
> +static bool is_expanded_type(int tag)
> +{
> + return tag == DW_TAG_class_type || tag == DW_TAG_structure_type ||
> + tag == DW_TAG_union_type || tag == DW_TAG_enumeration_type;
> +}
> +
> +/* The maximum depth for expanding structures in pointers */
> +#define MAX_POINTER_EXPANSION_DEPTH 2
> +
> #define PROCESS_TYPE(type) \
> case DW_TAG_##type##_type: \
> process_##type##_type(state, cache, die); \
> @@ -559,18 +612,52 @@ static void process_cached(struct state *state, struct die *cache,
>
> static int process_type(struct state *state, struct die *parent, Dwarf_Die *die)
> {
> + enum die_state want_state = DIE_COMPLETE;
> struct die *cache;
> + struct expansion_state saved;
> int tag = dwarf_tag(die);
>
> + expansion_state_save(&state->expand, &saved);
> +
> + /*
> + * Structures and enumeration types are expanded only once per
> + * exported symbol. This is sufficient for detecting ABI changes
> + * within the structure.
> + *
> + * We fully expand the first pointer reference in the exported
> + * symbol, but limit the expansion of further pointer references
> + * to at most MAX_POINTER_EXPANSION_DEPTH levels.
> + */
> + if (is_pointer_type(tag))
> + state->expand.ptr_depth++;
> +
> + if (state->expand.ptr_depth > 0 && is_expanded_type(tag)) {
> + if (state->expand.ptr_expansion_depth >=
> + MAX_POINTER_EXPANSION_DEPTH ||
> + cache_was_expanded(&state->expansion_cache, die->addr))
> + state->expand.expand = false;
> +
> + if (state->expand.expand)
> + state->expand.ptr_expansion_depth++;
> + }
> +
> /*
> - * If we have the DIE already cached, use it instead of walking
> + * If we have want_state already cached, use it instead of walking
> * through DWARF.
> */
> - cache = die_map_get(die, DIE_COMPLETE);
> + if (!state->expand.expand && is_expanded_type(tag))
> + want_state = DIE_UNEXPANDED;
> +
> + cache = die_map_get(die, want_state);
> +
> + if (cache->state == want_state) {
> + if (want_state == DIE_COMPLETE && is_expanded_type(tag))
> + cache_mark_expanded(&state->expansion_cache, die->addr);
>
> - if (cache->state == DIE_COMPLETE) {
> process_cached(state, cache, die);
> die_map_add_die(parent, cache);
> +
> + expansion_state_restore(&state->expand, &saved);
> return 0;
> }
>

The commit message and the comment in process_type() describe that each
structure type should be expanded only once per symbol, but that doesn't
seem to be the case?

Consider the following example:

struct A { int m; };
void foo(struct A a1, struct A a2) {}

Running gendwarfksyms on the compiled file shows the following debug
output:

$ echo foo | ./build/scripts/gendwarfksyms/gendwarfksyms --debug --dump-types --dump-versions --dump-dies test.o
[...]
gendwarfksyms: process_symbol: foo
subprogram (
formal_parameter structure_type A {
member base_type int byte_size(4) encoding(5) m data_member_location(0)
} byte_size(4) a1 ,
formal_parameter structure_type A {
member base_type int byte_size(4) encoding(5) m data_member_location(0)
} byte_size(4) a2
)
-> base_type void

I think it indicates that struct A was expanded twice. My expectation
would be to see:

gendwarfksyms: process_symbol: foo
subprogram (
formal_parameter structure_type A {
member base_type int byte_size(4) encoding(5) m data_member_location(0)
} byte_size(4) a1 ,
formal_parameter structure_type A {
} a2
)
-> base_type void

If I follow correctly, the type_expand() logic on the output eventually
performs only the first expansion for the CRC calculation. However, it
looks this process_type() code should do the same, if only to be a bit
faster. Or did I misunderstand anything how this should work?

I played with the following (applies on the top of the series), which
matches my understanding of what should happen:

diff --git a/scripts/gendwarfksyms/dwarf.c b/scripts/gendwarfksyms/dwarf.c
index 0112b5e8fbf5..1cc39be02b80 100644
--- a/scripts/gendwarfksyms/dwarf.c
+++ b/scripts/gendwarfksyms/dwarf.c
@@ -661,7 +661,6 @@ static void __process_structure_type(struct state *state, struct die *cache,
is_decl = is_declaration(cache, die);

if (!is_decl && state->expand.expand) {
- cache_mark_expanded(&state->expansion_cache, die->addr);
state->expand.current_fqn = cache->fqn;
check(process_die_container(state, cache, die, process_func,
match_func));
@@ -850,32 +849,35 @@ static int process_type(struct state *state, struct die *parent, Dwarf_Die *die)
if (is_pointer_type(tag))
state->expand.ptr_depth++;

- if (state->expand.ptr_depth > 0 && is_expanded_type(tag)) {
- if (state->expand.ptr_expansion_depth >=
- MAX_POINTER_EXPANSION_DEPTH ||
- cache_was_expanded(&state->expansion_cache, die->addr))
+ if (is_expanded_type(tag)) {
+ if (cache_was_expanded(&state->expansion_cache, die->addr))
state->expand.expand = false;

+ if (state->expand.ptr_depth > 0) {
+ if (state->expand.ptr_expansion_depth >=
+ MAX_POINTER_EXPANSION_DEPTH)
+ state->expand.expand = false;
+
+ if (state->expand.expand)
+ state->expand.ptr_expansion_depth++;
+ }
+
if (state->expand.expand)
- state->expand.ptr_expansion_depth++;
+ cache_mark_expanded(&state->expansion_cache, die->addr);
+ else
+ want_state = DIE_UNEXPANDED;
}

/*
* If we have want_state already cached, use it instead of walking
* through DWARF.
*/
- if (!state->expand.expand && is_expanded_type(tag))
- want_state = DIE_UNEXPANDED;
-
cache = die_map_get(die, want_state);

if (cache->state == want_state) {
die_debug_g("cached addr %p tag %x -- %s", die->addr, tag,
die_state_name(cache->state));

- if (want_state == DIE_COMPLETE && is_expanded_type(tag))
- cache_mark_expanded(&state->expansion_cache, die->addr);
-
process_cached(state, cache, die);
die_map_add_die(parent, cache);

> @@ -611,9 +698,10 @@ static int process_type(struct state *state, struct die *parent, Dwarf_Die *die)
>
> /* Update cache state and append to the parent (if any) */
> cache->tag = tag;
> - cache->state = DIE_COMPLETE;
> + cache->state = want_state;
> die_map_add_die(parent, cache);
>
> + expansion_state_restore(&state->expand, &saved);
> return 0;
> }
>
> @@ -675,11 +763,14 @@ static int process_exported_symbols(struct state *unused, struct die *cache,
> if (!match_export_symbol(&state, die))
> return 0;
>
> + state_init(&state);
> +
> if (tag == DW_TAG_subprogram)
> process_subprogram(&state, &state.die);
> else
> process_variable(&state, &state.die);
>
> + cache_clear_expanded(&state.expansion_cache);
> return 0;
> }
> default:
> diff --git a/scripts/gendwarfksyms/gendwarfksyms.h b/scripts/gendwarfksyms/gendwarfksyms.h
> index f317de5b0653..6147859ae2af 100644
> --- a/scripts/gendwarfksyms/gendwarfksyms.h
> +++ b/scripts/gendwarfksyms/gendwarfksyms.h
> @@ -104,6 +104,7 @@ struct symbol *symbol_get(const char *name);
>
> enum die_state {
> DIE_INCOMPLETE,
> + DIE_UNEXPANDED,
> DIE_COMPLETE,
> DIE_LAST = DIE_COMPLETE
> };
> @@ -133,6 +134,7 @@ static inline const char *die_state_name(enum die_state state)
> {
> switch (state) {
> CASE_CONST_TO_STR(DIE_INCOMPLETE)
> + CASE_CONST_TO_STR(DIE_UNEXPANDED)
> CASE_CONST_TO_STR(DIE_COMPLETE)
> }
>
> @@ -155,9 +157,40 @@ void die_map_add_linebreak(struct die *pd, int linebreak);
> void die_map_add_die(struct die *pd, struct die *child);
> void die_map_free(void);
>
> +/*
> + * cache.c
> + */
> +
> +#define EXPANSION_CACHE_HASH_BITS 11
> +
> +/* A cache for addresses we've already seen. */
> +struct expansion_cache {
> + HASHTABLE_DECLARE(cache, 1 << EXPANSION_CACHE_HASH_BITS);
> +};
> +
> +void __cache_mark_expanded(struct expansion_cache *ec, uintptr_t addr);
> +bool __cache_was_expanded(struct expansion_cache *ec, uintptr_t addr);
> +
> +static inline void cache_mark_expanded(struct expansion_cache *ec, void *addr)
> +{
> + __cache_mark_expanded(ec, (uintptr_t)addr);
> +}
> +
> +static inline bool cache_was_expanded(struct expansion_cache *ec, void *addr)
> +{
> + return __cache_was_expanded(ec, (uintptr_t)addr);
> +}
> +
> +void cache_clear_expanded(struct expansion_cache *ec);
> +
> /*
> * dwarf.c
> */
> +struct expansion_state {
> + bool expand;
> + unsigned int ptr_depth;
> + unsigned int ptr_expansion_depth;
> +};
>
> struct state {
> struct symbol *sym;
> @@ -165,6 +198,10 @@ struct state {
>
> /* List expansion */
> bool first_list_item;
> +
> + /* Structure expansion */
> + struct expansion_state expand;
> + struct expansion_cache expansion_cache;
> };
>
> typedef int (*die_callback_t)(struct state *state, struct die *cache,

--
Thanks,
Petr