diff mbox series

[v3,06/20] gendwarfksyms: Add a cache for processed DIEs

Message ID 20240923181846.549877-28-samitolvanen@google.com (mailing list archive)
State Handled Elsewhere
Headers show
Series Implement DWARF modversions | expand

Commit Message

Sami Tolvanen Sept. 23, 2024, 6:18 p.m. UTC 
Basic types in DWARF repeat frequently and traversing the DIEs using
libdw is relatively slow. Add a simple hashtable based cache for the
processed DIEs.

Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
 scripts/gendwarfksyms/Makefile        |   1 +
 scripts/gendwarfksyms/die.c           | 143 ++++++++++++++++++++++++++
 scripts/gendwarfksyms/dwarf.c         | 136 +++++++++++++++++-------
 scripts/gendwarfksyms/gendwarfksyms.c |   6 ++
 scripts/gendwarfksyms/gendwarfksyms.h |  62 ++++++++++-
 5 files changed, 307 insertions(+), 41 deletions(-)
 create mode 100644 scripts/gendwarfksyms/die.c

Comments

Petr Pavlu Oct. 1, 2024, 2:10 p.m. UTC | #1 
On 9/23/24 20:18, Sami Tolvanen wrote:
> Basic types in DWARF repeat frequently and traversing the DIEs using
> libdw is relatively slow. Add a simple hashtable based cache for the
> processed DIEs.
> 
> Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
> ---
>  scripts/gendwarfksyms/Makefile        |   1 +
>  scripts/gendwarfksyms/die.c           | 143 ++++++++++++++++++++++++++
>  scripts/gendwarfksyms/dwarf.c         | 136 +++++++++++++++++-------
>  scripts/gendwarfksyms/gendwarfksyms.c |   6 ++
>  scripts/gendwarfksyms/gendwarfksyms.h |  62 ++++++++++-
>  5 files changed, 307 insertions(+), 41 deletions(-)
>  create mode 100644 scripts/gendwarfksyms/die.c
> 
> diff --git a/scripts/gendwarfksyms/Makefile b/scripts/gendwarfksyms/Makefile
> index 9f8fec4fd39b..c0d4ce50fc27 100644
> --- a/scripts/gendwarfksyms/Makefile
> +++ b/scripts/gendwarfksyms/Makefile
> @@ -2,6 +2,7 @@
>  hostprogs-always-y += gendwarfksyms
>  
>  gendwarfksyms-objs += gendwarfksyms.o
> +gendwarfksyms-objs += die.o
>  gendwarfksyms-objs += dwarf.o
>  gendwarfksyms-objs += symbols.o
>  
> diff --git a/scripts/gendwarfksyms/die.c b/scripts/gendwarfksyms/die.c
> new file mode 100644
> index 000000000000..28d89fce89fc
> --- /dev/null
> +++ b/scripts/gendwarfksyms/die.c
> @@ -0,0 +1,143 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Copyright (C) 2024 Google LLC
> + */
> +
> +#include <string.h>
> +#include "gendwarfksyms.h"
> +
> +#define DIE_HASH_BITS 20
> +
> +/* {die->addr, state} -> struct die * */
> +static HASHTABLE_DEFINE(die_map, 1 << DIE_HASH_BITS);
> +
> +static unsigned int map_hits;
> +static unsigned int map_misses;
> +
> +static inline unsigned int die_hash(uintptr_t addr, enum die_state state)
> +{
> +	return hash_32(addr_hash(addr) ^ (unsigned int)state);
> +}
> +
> +static void init_die(struct die *cd)
> +{
> +	cd->state = DIE_INCOMPLETE;
> +	cd->fqn = NULL;
> +	cd->tag = -1;
> +	cd->addr = 0;
> +	INIT_LIST_HEAD(&cd->fragments);
> +}
> +
> +static struct die *create_die(Dwarf_Die *die, enum die_state state)
> +{
> +	struct die *cd;
> +
> +	cd = xmalloc(sizeof(struct die));
> +	init_die(cd);
> +	cd->addr = (uintptr_t)die->addr;
> +
> +	hash_add(die_map, &cd->hash, die_hash(cd->addr, state));
> +	return cd;
> +}
> +
> +int __die_map_get(uintptr_t addr, enum die_state state, struct die **res)
> +{
> +	struct die *cd;
> +
> +	hash_for_each_possible(die_map, cd, hash, die_hash(addr, state)) {
> +		if (cd->addr == addr && cd->state == state) {
> +			*res = cd;
> +			return 0;
> +		}
> +	}
> +
> +	return -1;
> +}
> +
> +struct die *die_map_get(Dwarf_Die *die, enum die_state state)
> +{
> +	struct die *cd;
> +
> +	if (__die_map_get((uintptr_t)die->addr, state, &cd) == 0) {
> +		map_hits++;
> +		return cd;
> +	}
> +
> +	map_misses++;
> +	return create_die(die, state);
> +}
> +
> +static void reset_die(struct die *cd)
> +{
> +	struct die_fragment *tmp;
> +	struct die_fragment *df;
> +
> +	list_for_each_entry_safe(df, tmp, &cd->fragments, list) {
> +		if (df->type == FRAGMENT_STRING)
> +			free(df->data.str);
> +		free(df);
> +	}
> +
> +	if (cd->fqn && *cd->fqn)
> +		free(cd->fqn);
> +	init_die(cd);
> +}
> +
> +void die_map_free(void)
> +{
> +	struct hlist_node *tmp;
> +	unsigned int stats[DIE_LAST + 1];
> +	struct die *cd;
> +	int i;
> +
> +	memset(stats, 0, sizeof(stats));
> +
> +	hash_for_each_safe(die_map, cd, tmp, hash) {
> +		stats[cd->state]++;
> +		reset_die(cd);
> +		free(cd);
> +	}
> +	hash_init(die_map);
> +
> +	if (map_hits + map_misses > 0)
> +		debug("hits %u, misses %u (hit rate %.02f%%)", map_hits,
> +		      map_misses,
> +		      (100.0f * map_hits) / (map_hits + map_misses));
> +
> +	for (i = 0; i <= DIE_LAST; i++)
> +		debug("%s: %u entries", die_state_name(i), stats[i]);
> +}
> +
> +static struct die_fragment *append_item(struct die *cd)
> +{
> +	struct die_fragment *df;
> +
> +	df = xmalloc(sizeof(struct die_fragment));
> +	df->type = FRAGMENT_EMPTY;
> +	list_add_tail(&df->list, &cd->fragments);
> +	return df;
> +}
> +
> +void die_map_add_string(struct die *cd, const char *str)
> +{
> +	struct die_fragment *df;
> +
> +	if (!cd)
> +		return;
> +
> +	df = append_item(cd);
> +	df->data.str = xstrdup(str);
> +	df->type = FRAGMENT_STRING;
> +}
> +
> +void die_map_add_die(struct die *cd, struct die *child)
> +{
> +	struct die_fragment *df;
> +
> +	if (!cd)
> +		return;
> +
> +	df = append_item(cd);
> +	df->data.addr = child->addr;
> +	df->type = FRAGMENT_DIE;
> +}
> diff --git a/scripts/gendwarfksyms/dwarf.c b/scripts/gendwarfksyms/dwarf.c
> index 3e9e8500f448..f0c881bef026 100644
> --- a/scripts/gendwarfksyms/dwarf.c
> +++ b/scripts/gendwarfksyms/dwarf.c
> @@ -71,17 +71,19 @@ static bool match_export_symbol(struct state *state, Dwarf_Die *die)
>  /*
>   * Type string processing
>   */
> -static void process(const char *s)
> +static void process(struct die *cache, const char *s)
>  {
>  	s = s ?: "<null>";
>  
>  	if (dump_dies)
>  		fputs(s, stderr);
> +
> +	die_map_add_string(cache, s);
>  }
>  
>  #define MAX_FMT_BUFFER_SIZE 128
>  
> -static void process_fmt(const char *fmt, ...)
> +static void process_fmt(struct die *cache, const char *fmt, ...)
>  {
>  	char buf[MAX_FMT_BUFFER_SIZE];
>  	va_list args;
> @@ -91,7 +93,7 @@ static void process_fmt(const char *fmt, ...)
>  	if (checkp(vsnprintf(buf, sizeof(buf), fmt, args)) >= sizeof(buf))
>  		error("vsnprintf overflow: increase MAX_FMT_BUFFER_SIZE");
>  
> -	process(buf);
> +	process(cache, buf);
>  	va_end(args);
>  }
>  
> @@ -162,18 +164,28 @@ static char *get_fqn(Dwarf_Die *die)
>  	return fqn;
>  }
>  
> -static void process_fqn(Dwarf_Die *die)
> +static void update_fqn(struct die *cache, Dwarf_Die *die)
> +{
> +	if (!cache->fqn)
> +		cache->fqn = get_fqn(die) ?: "";
> +}

When is update_fqn() called with cache->fqn being already non-NULL?

In general, I find handling of cache->fqn slightly confusing, mostly
because the member has three states: NULL initially,
a statically-allocated empty string if the DIE doesn't have a name and
a dynamically-allocated non-zero-length string otherwise.

I wonder if it would be possible to reduce it to two states: NULL
initially and when the DIE doesn't have a name, or a regular string.

> +
> +static void process_fqn(struct die *cache, Dwarf_Die *die)
>  {
> -	process(" ");
> -	process(get_fqn(die) ?: "");
> +	update_fqn(cache, die);
> +	if (*cache->fqn)
> +		process(cache, " ");
> +	process(cache, cache->fqn);
>  }
>  
> -#define DEFINE_PROCESS_UDATA_ATTRIBUTE(attribute)                           \
> -	static void process_##attribute##_attr(Dwarf_Die *die)              \
> -	{                                                                   \
> -		Dwarf_Word value;                                           \
> -		if (get_udata_attr(die, DW_AT_##attribute, &value))         \
> -			process_fmt(" " #attribute "(%" PRIu64 ")", value); \
> +#define DEFINE_PROCESS_UDATA_ATTRIBUTE(attribute)                          \
> +	static void process_##attribute##_attr(struct die *cache,          \
> +					       Dwarf_Die *die)             \
> +	{                                                                  \
> +		Dwarf_Word value;                                          \
> +		if (get_udata_attr(die, DW_AT_##attribute, &value))        \
> +			process_fmt(cache, " " #attribute "(%" PRIu64 ")", \
> +				    value);                                \
>  	}
>  
>  DEFINE_PROCESS_UDATA_ATTRIBUTE(alignment)
> @@ -185,8 +197,9 @@ bool match_all(Dwarf_Die *die)
>  	return true;
>  }
>  
> -int process_die_container(struct state *state, Dwarf_Die *die,
> -			  die_callback_t func, die_match_callback_t match)
> +int process_die_container(struct state *state, struct die *cache,
> +			  Dwarf_Die *die, die_callback_t func,
> +			  die_match_callback_t match)
>  {
>  	Dwarf_Die current;
>  	int res;
> @@ -195,7 +208,7 @@ int process_die_container(struct state *state, Dwarf_Die *die,
>  	while (!res) {
>  		if (match(&current)) {
>  			/* <0 = error, 0 = continue, >0 = stop */
> -			res = checkp(func(state, &current));
> +			res = checkp(func(state, cache, &current));
>  			if (res)
>  				return res;
>  		}
> @@ -206,39 +219,78 @@ int process_die_container(struct state *state, Dwarf_Die *die,
>  	return 0;
>  }
>  
> -static int process_type(struct state *state, Dwarf_Die *die);
> +static int process_type(struct state *state, struct die *parent,
> +			Dwarf_Die *die);
>  
> -static void process_type_attr(struct state *state, Dwarf_Die *die)
> +static void process_type_attr(struct state *state, struct die *cache,
> +			      Dwarf_Die *die)
>  {
>  	Dwarf_Die type;
>  
>  	if (get_ref_die_attr(die, DW_AT_type, &type)) {
> -		check(process_type(state, &type));
> +		check(process_type(state, cache, &type));
>  		return;
>  	}
>  
>  	/* Compilers can omit DW_AT_type -- print out 'void' to clarify */
> -	process("base_type void");
> +	process(cache, "base_type void");
> +}
> +
> +static void process_base_type(struct state *state, struct die *cache,
> +			      Dwarf_Die *die)
> +{
> +	process(cache, "base_type");
> +	process_fqn(cache, die);
> +	process_byte_size_attr(cache, die);
> +	process_encoding_attr(cache, die);
> +	process_alignment_attr(cache, die);
>  }
>  
> -static void process_base_type(struct state *state, Dwarf_Die *die)
> +static void process_cached(struct state *state, struct die *cache,
> +			   Dwarf_Die *die)
>  {
> -	process("base_type");
> -	process_fqn(die);
> -	process_byte_size_attr(die);
> -	process_encoding_attr(die);
> -	process_alignment_attr(die);
> +	struct die_fragment *df;
> +	Dwarf_Die child;
> +
> +	list_for_each_entry(df, &cache->fragments, list) {
> +		switch (df->type) {
> +		case FRAGMENT_STRING:
> +			process(NULL, df->data.str);
> +			break;
> +		case FRAGMENT_DIE:
> +			if (!dwarf_die_addr_die(dwarf_cu_getdwarf(die->cu),
> +						(void *)df->data.addr, &child))
> +				error("dwarf_die_addr_die failed");
> +			check(process_type(state, NULL, &child));
> +			break;
> +		default:
> +			error("empty die_fragment");
> +		}
> +	}
>  }
>  
> -#define PROCESS_TYPE(type)                         \
> -	case DW_TAG_##type##_type:                 \
> -		process_##type##_type(state, die); \
> +#define PROCESS_TYPE(type)                                \
> +	case DW_TAG_##type##_type:                        \
> +		process_##type##_type(state, cache, die); \
>  		break;
>  
> -static int process_type(struct state *state, Dwarf_Die *die)
> +static int process_type(struct state *state, struct die *parent, Dwarf_Die *die)
>  {
> +	struct die *cache;
>  	int tag = dwarf_tag(die);
>  
> +	/*
> +	 * If we have the DIE already cached, use it instead of walking
> +	 * through DWARF.
> +	 */
> +	cache = die_map_get(die, DIE_COMPLETE);
> +
> +	if (cache->state == DIE_COMPLETE) {
> +		process_cached(state, cache, die);
> +		die_map_add_die(parent, cache);
> +		return 0;
> +	}
> +
>  	switch (tag) {
>  	PROCESS_TYPE(base)
>  	default:
> @@ -246,6 +298,11 @@ static int process_type(struct state *state, Dwarf_Die *die)
>  		break;
>  	}
>  
> +	/* Update cache state and append to the parent (if any) */
> +	cache->tag = tag;
> +	cache->state = DIE_COMPLETE;
> +	die_map_add_die(parent, cache);
> +
>  	return 0;
>  }
>  
> @@ -256,14 +313,15 @@ static void process_symbol(struct state *state, Dwarf_Die *die,
>  			   die_callback_t process_func)
>  {
>  	debug("%s", state->sym->name);
> -	check(process_func(state, die));
> +	check(process_func(state, NULL, die));
>  	if (dump_dies)
>  		fputs("\n", stderr);
>  }
>  
> -static int __process_subprogram(struct state *state, Dwarf_Die *die)
> +static int __process_subprogram(struct state *state, struct die *cache,
> +				Dwarf_Die *die)
>  {
> -	process("subprogram");
> +	process(cache, "subprogram");
>  	return 0;
>  }
>  
> @@ -272,10 +330,11 @@ static void process_subprogram(struct state *state, Dwarf_Die *die)
>  	process_symbol(state, die, __process_subprogram);
>  }
>  
> -static int __process_variable(struct state *state, Dwarf_Die *die)
> +static int __process_variable(struct state *state, struct die *cache,
> +			      Dwarf_Die *die)
>  {
> -	process("variable ");
> -	process_type_attr(state, die);
> +	process(cache, "variable ");
> +	process_type_attr(state, cache, die);
>  	return 0;
>  }
>  
> @@ -284,7 +343,8 @@ static void process_variable(struct state *state, Dwarf_Die *die)
>  	process_symbol(state, die, __process_variable);
>  }
>  
> -static int process_exported_symbols(struct state *unused, Dwarf_Die *die)
> +static int process_exported_symbols(struct state *unused, struct die *cache,
> +				    Dwarf_Die *die)
>  {
>  	int tag = dwarf_tag(die);
>  
> @@ -294,7 +354,7 @@ static int process_exported_symbols(struct state *unused, Dwarf_Die *die)
>  	case DW_TAG_class_type:
>  	case DW_TAG_structure_type:
>  		return check(process_die_container(
> -			NULL, die, process_exported_symbols, match_all));
> +			NULL, cache, die, process_exported_symbols, match_all));
>  
>  	/* Possible exported symbols */
>  	case DW_TAG_subprogram:
> @@ -318,6 +378,6 @@ static int process_exported_symbols(struct state *unused, Dwarf_Die *die)
>  
>  void process_cu(Dwarf_Die *cudie)
>  {
> -	check(process_die_container(NULL, cudie, process_exported_symbols,
> +	check(process_die_container(NULL, NULL, cudie, process_exported_symbols,
>  				    match_all));
>  }
> diff --git a/scripts/gendwarfksyms/gendwarfksyms.c b/scripts/gendwarfksyms/gendwarfksyms.c
> index 5032ec487626..66806b0936e4 100644
> --- a/scripts/gendwarfksyms/gendwarfksyms.c
> +++ b/scripts/gendwarfksyms/gendwarfksyms.c
> @@ -43,6 +43,10 @@ static int process_module(Dwfl_Module *mod, void **userdata, const char *name,
>  	debug("%s", name);
>  	dbg = dwfl_module_getdwarf(mod, &dwbias);
>  
> +	/*
> +	 * Look for exported symbols in each CU, follow the DIE tree, and add
> +	 * the entries to die_map.
> +	 */
>  	do {
>  		res = dwarf_get_units(dbg, cu, &cu, NULL, NULL, &cudie, NULL);
>  		if (res < 0)
> @@ -53,6 +57,8 @@ static int process_module(Dwfl_Module *mod, void **userdata, const char *name,
>  		process_cu(&cudie);
>  	} while (cu);
>  
> +	die_map_free();
> +
>  	return DWARF_CB_OK;
>  }
>  
> diff --git a/scripts/gendwarfksyms/gendwarfksyms.h b/scripts/gendwarfksyms/gendwarfksyms.h
> index a058647e2361..7df270429c21 100644
> --- a/scripts/gendwarfksyms/gendwarfksyms.h
> +++ b/scripts/gendwarfksyms/gendwarfksyms.h
> @@ -89,6 +89,60 @@ void symbol_read_exports(FILE *file);
>  void symbol_read_symtab(int fd);
>  struct symbol *symbol_get(const char *name);
>  
> +/*
> + * die.c
> + */
> +
> +enum die_state {
> +	DIE_INCOMPLETE,
> +	DIE_COMPLETE,
> +	DIE_LAST = DIE_COMPLETE
> +};
> +
> +enum die_fragment_type {
> +	FRAGMENT_EMPTY,
> +	FRAGMENT_STRING,
> +	FRAGMENT_DIE
> +};
> +
> +struct die_fragment {
> +	enum die_fragment_type type;
> +	union {
> +		char *str;
> +		uintptr_t addr;
> +	} data;
> +	struct list_head list;
> +};
> +
> +#define CASE_CONST_TO_STR(name) \
> +	case name:              \
> +		return #name;
> +
> +static inline const char *die_state_name(enum die_state state)
> +{
> +	switch (state) {
> +	default:
> +	CASE_CONST_TO_STR(DIE_INCOMPLETE)
> +	CASE_CONST_TO_STR(DIE_COMPLETE)
> +	}

Nit: I suggest to move the default case out of the switch statement:

	switch (state) {
	CASE_CONST_TO_STR(DIE_INCOMPLETE)
	CASE_CONST_TO_STR(DIE_COMPLETE)
	}
	error("unexpected die_state: %d", state);

This way, if someone adds a new value in die_state and forgets to handle
it in die_state_name(), they get a compiler warning.. or a runtime error
later.

> +}
> +
> +struct die {
> +	enum die_state state;
> +	char *fqn;
> +	int tag;
> +	uintptr_t addr;
> +	struct list_head fragments;
> +	struct hlist_node hash;
> +};
> +
> +int __die_map_get(uintptr_t addr, enum die_state state, struct die **res);
> +struct die *die_map_get(Dwarf_Die *die, enum die_state state);
> +void die_map_add_string(struct die *pd, const char *str);
> +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);
> +
>  /*
>   * dwarf.c
>   */
> @@ -98,12 +152,14 @@ struct state {
>  	Dwarf_Die die;
>  };
>  
> -typedef int (*die_callback_t)(struct state *state, Dwarf_Die *die);
> +typedef int (*die_callback_t)(struct state *state, struct die *cache,
> +			      Dwarf_Die *die);
>  typedef bool (*die_match_callback_t)(Dwarf_Die *die);
>  bool match_all(Dwarf_Die *die);
>  
> -int process_die_container(struct state *state, Dwarf_Die *die,
> -			  die_callback_t func, die_match_callback_t match);
> +int process_die_container(struct state *state, struct die *cache,
> +			  Dwarf_Die *die, die_callback_t func,
> +			  die_match_callback_t match);
>  
>  void process_cu(Dwarf_Die *cudie);
>
Sami Tolvanen Oct. 1, 2024, 8:18 p.m. UTC | #2 
On Tue, Oct 1, 2024 at 2:10 PM Petr Pavlu <petr.pavlu@suse.com> wrote:
>
> On 9/23/24 20:18, Sami Tolvanen wrote:
> > +static void update_fqn(struct die *cache, Dwarf_Die *die)
> > +{
> > +     if (!cache->fqn)
> > +             cache->fqn = get_fqn(die) ?: "";
> > +}
>
> When is update_fqn() called with cache->fqn being already non-NULL?

In patch 16, because we need the name before process_fqn() is called,
and if we end up outputting the name after that, cache->fqn is already
non-NULL.

> In general, I find handling of cache->fqn slightly confusing, mostly
> because the member has three states: NULL initially,
> a statically-allocated empty string if the DIE doesn't have a name and
> a dynamically-allocated non-zero-length string otherwise.
>
> I wonder if it would be possible to reduce it to two states: NULL
> initially and when the DIE doesn't have a name, or a regular string.

I also thought about it, but using an empty string to represent an
unnamed DIE and NULL to represent an uninitialized value seemed the
most reasonable option.

> > +static inline const char *die_state_name(enum die_state state)
> > +{
> > +     switch (state) {
> > +     default:
> > +     CASE_CONST_TO_STR(DIE_INCOMPLETE)
> > +     CASE_CONST_TO_STR(DIE_COMPLETE)
> > +     }
>
> Nit: I suggest to move the default case out of the switch statement:
>
>         switch (state) {
>         CASE_CONST_TO_STR(DIE_INCOMPLETE)
>         CASE_CONST_TO_STR(DIE_COMPLETE)
>         }
>         error("unexpected die_state: %d", state);
>
> This way, if someone adds a new value in die_state and forgets to handle
> it in die_state_name(), they get a compiler warning.. or a runtime error
> later.

Sure, I'll change this.

Sami
diff mbox series

Patch

diff --git a/scripts/gendwarfksyms/Makefile b/scripts/gendwarfksyms/Makefile
index 9f8fec4fd39b..c0d4ce50fc27 100644
--- a/scripts/gendwarfksyms/Makefile
+++ b/scripts/gendwarfksyms/Makefile
@@ -2,6 +2,7 @@ 
 hostprogs-always-y += gendwarfksyms
 
 gendwarfksyms-objs += gendwarfksyms.o
+gendwarfksyms-objs += die.o
 gendwarfksyms-objs += dwarf.o
 gendwarfksyms-objs += symbols.o
 
diff --git a/scripts/gendwarfksyms/die.c b/scripts/gendwarfksyms/die.c
new file mode 100644
index 000000000000..28d89fce89fc
--- /dev/null
+++ b/scripts/gendwarfksyms/die.c
@@ -0,0 +1,143 @@ 
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Copyright (C) 2024 Google LLC
+ */
+
+#include <string.h>
+#include "gendwarfksyms.h"
+
+#define DIE_HASH_BITS 20
+
+/* {die->addr, state} -> struct die * */
+static HASHTABLE_DEFINE(die_map, 1 << DIE_HASH_BITS);
+
+static unsigned int map_hits;
+static unsigned int map_misses;
+
+static inline unsigned int die_hash(uintptr_t addr, enum die_state state)
+{
+	return hash_32(addr_hash(addr) ^ (unsigned int)state);
+}
+
+static void init_die(struct die *cd)
+{
+	cd->state = DIE_INCOMPLETE;
+	cd->fqn = NULL;
+	cd->tag = -1;
+	cd->addr = 0;
+	INIT_LIST_HEAD(&cd->fragments);
+}
+
+static struct die *create_die(Dwarf_Die *die, enum die_state state)
+{
+	struct die *cd;
+
+	cd = xmalloc(sizeof(struct die));
+	init_die(cd);
+	cd->addr = (uintptr_t)die->addr;
+
+	hash_add(die_map, &cd->hash, die_hash(cd->addr, state));
+	return cd;
+}
+
+int __die_map_get(uintptr_t addr, enum die_state state, struct die **res)
+{
+	struct die *cd;
+
+	hash_for_each_possible(die_map, cd, hash, die_hash(addr, state)) {
+		if (cd->addr == addr && cd->state == state) {
+			*res = cd;
+			return 0;
+		}
+	}
+
+	return -1;
+}
+
+struct die *die_map_get(Dwarf_Die *die, enum die_state state)
+{
+	struct die *cd;
+
+	if (__die_map_get((uintptr_t)die->addr, state, &cd) == 0) {
+		map_hits++;
+		return cd;
+	}
+
+	map_misses++;
+	return create_die(die, state);
+}
+
+static void reset_die(struct die *cd)
+{
+	struct die_fragment *tmp;
+	struct die_fragment *df;
+
+	list_for_each_entry_safe(df, tmp, &cd->fragments, list) {
+		if (df->type == FRAGMENT_STRING)
+			free(df->data.str);
+		free(df);
+	}
+
+	if (cd->fqn && *cd->fqn)
+		free(cd->fqn);
+	init_die(cd);
+}
+
+void die_map_free(void)
+{
+	struct hlist_node *tmp;
+	unsigned int stats[DIE_LAST + 1];
+	struct die *cd;
+	int i;
+
+	memset(stats, 0, sizeof(stats));
+
+	hash_for_each_safe(die_map, cd, tmp, hash) {
+		stats[cd->state]++;
+		reset_die(cd);
+		free(cd);
+	}
+	hash_init(die_map);
+
+	if (map_hits + map_misses > 0)
+		debug("hits %u, misses %u (hit rate %.02f%%)", map_hits,
+		      map_misses,
+		      (100.0f * map_hits) / (map_hits + map_misses));
+
+	for (i = 0; i <= DIE_LAST; i++)
+		debug("%s: %u entries", die_state_name(i), stats[i]);
+}
+
+static struct die_fragment *append_item(struct die *cd)
+{
+	struct die_fragment *df;
+
+	df = xmalloc(sizeof(struct die_fragment));
+	df->type = FRAGMENT_EMPTY;
+	list_add_tail(&df->list, &cd->fragments);
+	return df;
+}
+
+void die_map_add_string(struct die *cd, const char *str)
+{
+	struct die_fragment *df;
+
+	if (!cd)
+		return;
+
+	df = append_item(cd);
+	df->data.str = xstrdup(str);
+	df->type = FRAGMENT_STRING;
+}
+
+void die_map_add_die(struct die *cd, struct die *child)
+{
+	struct die_fragment *df;
+
+	if (!cd)
+		return;
+
+	df = append_item(cd);
+	df->data.addr = child->addr;
+	df->type = FRAGMENT_DIE;
+}
diff --git a/scripts/gendwarfksyms/dwarf.c b/scripts/gendwarfksyms/dwarf.c
index 3e9e8500f448..f0c881bef026 100644
--- a/scripts/gendwarfksyms/dwarf.c
+++ b/scripts/gendwarfksyms/dwarf.c
@@ -71,17 +71,19 @@  static bool match_export_symbol(struct state *state, Dwarf_Die *die)
 /*
  * Type string processing
  */
-static void process(const char *s)
+static void process(struct die *cache, const char *s)
 {
 	s = s ?: "<null>";
 
 	if (dump_dies)
 		fputs(s, stderr);
+
+	die_map_add_string(cache, s);
 }
 
 #define MAX_FMT_BUFFER_SIZE 128
 
-static void process_fmt(const char *fmt, ...)
+static void process_fmt(struct die *cache, const char *fmt, ...)
 {
 	char buf[MAX_FMT_BUFFER_SIZE];
 	va_list args;
@@ -91,7 +93,7 @@  static void process_fmt(const char *fmt, ...)
 	if (checkp(vsnprintf(buf, sizeof(buf), fmt, args)) >= sizeof(buf))
 		error("vsnprintf overflow: increase MAX_FMT_BUFFER_SIZE");
 
-	process(buf);
+	process(cache, buf);
 	va_end(args);
 }
 
@@ -162,18 +164,28 @@  static char *get_fqn(Dwarf_Die *die)
 	return fqn;
 }
 
-static void process_fqn(Dwarf_Die *die)
+static void update_fqn(struct die *cache, Dwarf_Die *die)
+{
+	if (!cache->fqn)
+		cache->fqn = get_fqn(die) ?: "";
+}
+
+static void process_fqn(struct die *cache, Dwarf_Die *die)
 {
-	process(" ");
-	process(get_fqn(die) ?: "");
+	update_fqn(cache, die);
+	if (*cache->fqn)
+		process(cache, " ");
+	process(cache, cache->fqn);
 }
 
-#define DEFINE_PROCESS_UDATA_ATTRIBUTE(attribute)                           \
-	static void process_##attribute##_attr(Dwarf_Die *die)              \
-	{                                                                   \
-		Dwarf_Word value;                                           \
-		if (get_udata_attr(die, DW_AT_##attribute, &value))         \
-			process_fmt(" " #attribute "(%" PRIu64 ")", value); \
+#define DEFINE_PROCESS_UDATA_ATTRIBUTE(attribute)                          \
+	static void process_##attribute##_attr(struct die *cache,          \
+					       Dwarf_Die *die)             \
+	{                                                                  \
+		Dwarf_Word value;                                          \
+		if (get_udata_attr(die, DW_AT_##attribute, &value))        \
+			process_fmt(cache, " " #attribute "(%" PRIu64 ")", \
+				    value);                                \
 	}
 
 DEFINE_PROCESS_UDATA_ATTRIBUTE(alignment)
@@ -185,8 +197,9 @@  bool match_all(Dwarf_Die *die)
 	return true;
 }
 
-int process_die_container(struct state *state, Dwarf_Die *die,
-			  die_callback_t func, die_match_callback_t match)
+int process_die_container(struct state *state, struct die *cache,
+			  Dwarf_Die *die, die_callback_t func,
+			  die_match_callback_t match)
 {
 	Dwarf_Die current;
 	int res;
@@ -195,7 +208,7 @@  int process_die_container(struct state *state, Dwarf_Die *die,
 	while (!res) {
 		if (match(&current)) {
 			/* <0 = error, 0 = continue, >0 = stop */
-			res = checkp(func(state, &current));
+			res = checkp(func(state, cache, &current));
 			if (res)
 				return res;
 		}
@@ -206,39 +219,78 @@  int process_die_container(struct state *state, Dwarf_Die *die,
 	return 0;
 }
 
-static int process_type(struct state *state, Dwarf_Die *die);
+static int process_type(struct state *state, struct die *parent,
+			Dwarf_Die *die);
 
-static void process_type_attr(struct state *state, Dwarf_Die *die)
+static void process_type_attr(struct state *state, struct die *cache,
+			      Dwarf_Die *die)
 {
 	Dwarf_Die type;
 
 	if (get_ref_die_attr(die, DW_AT_type, &type)) {
-		check(process_type(state, &type));
+		check(process_type(state, cache, &type));
 		return;
 	}
 
 	/* Compilers can omit DW_AT_type -- print out 'void' to clarify */
-	process("base_type void");
+	process(cache, "base_type void");
+}
+
+static void process_base_type(struct state *state, struct die *cache,
+			      Dwarf_Die *die)
+{
+	process(cache, "base_type");
+	process_fqn(cache, die);
+	process_byte_size_attr(cache, die);
+	process_encoding_attr(cache, die);
+	process_alignment_attr(cache, die);
 }
 
-static void process_base_type(struct state *state, Dwarf_Die *die)
+static void process_cached(struct state *state, struct die *cache,
+			   Dwarf_Die *die)
 {
-	process("base_type");
-	process_fqn(die);
-	process_byte_size_attr(die);
-	process_encoding_attr(die);
-	process_alignment_attr(die);
+	struct die_fragment *df;
+	Dwarf_Die child;
+
+	list_for_each_entry(df, &cache->fragments, list) {
+		switch (df->type) {
+		case FRAGMENT_STRING:
+			process(NULL, df->data.str);
+			break;
+		case FRAGMENT_DIE:
+			if (!dwarf_die_addr_die(dwarf_cu_getdwarf(die->cu),
+						(void *)df->data.addr, &child))
+				error("dwarf_die_addr_die failed");
+			check(process_type(state, NULL, &child));
+			break;
+		default:
+			error("empty die_fragment");
+		}
+	}
 }
 
-#define PROCESS_TYPE(type)                         \
-	case DW_TAG_##type##_type:                 \
-		process_##type##_type(state, die); \
+#define PROCESS_TYPE(type)                                \
+	case DW_TAG_##type##_type:                        \
+		process_##type##_type(state, cache, die); \
 		break;
 
-static int process_type(struct state *state, Dwarf_Die *die)
+static int process_type(struct state *state, struct die *parent, Dwarf_Die *die)
 {
+	struct die *cache;
 	int tag = dwarf_tag(die);
 
+	/*
+	 * If we have the DIE already cached, use it instead of walking
+	 * through DWARF.
+	 */
+	cache = die_map_get(die, DIE_COMPLETE);
+
+	if (cache->state == DIE_COMPLETE) {
+		process_cached(state, cache, die);
+		die_map_add_die(parent, cache);
+		return 0;
+	}
+
 	switch (tag) {
 	PROCESS_TYPE(base)
 	default:
@@ -246,6 +298,11 @@  static int process_type(struct state *state, Dwarf_Die *die)
 		break;
 	}
 
+	/* Update cache state and append to the parent (if any) */
+	cache->tag = tag;
+	cache->state = DIE_COMPLETE;
+	die_map_add_die(parent, cache);
+
 	return 0;
 }
 
@@ -256,14 +313,15 @@  static void process_symbol(struct state *state, Dwarf_Die *die,
 			   die_callback_t process_func)
 {
 	debug("%s", state->sym->name);
-	check(process_func(state, die));
+	check(process_func(state, NULL, die));
 	if (dump_dies)
 		fputs("\n", stderr);
 }
 
-static int __process_subprogram(struct state *state, Dwarf_Die *die)
+static int __process_subprogram(struct state *state, struct die *cache,
+				Dwarf_Die *die)
 {
-	process("subprogram");
+	process(cache, "subprogram");
 	return 0;
 }
 
@@ -272,10 +330,11 @@  static void process_subprogram(struct state *state, Dwarf_Die *die)
 	process_symbol(state, die, __process_subprogram);
 }
 
-static int __process_variable(struct state *state, Dwarf_Die *die)
+static int __process_variable(struct state *state, struct die *cache,
+			      Dwarf_Die *die)
 {
-	process("variable ");
-	process_type_attr(state, die);
+	process(cache, "variable ");
+	process_type_attr(state, cache, die);
 	return 0;
 }
 
@@ -284,7 +343,8 @@  static void process_variable(struct state *state, Dwarf_Die *die)
 	process_symbol(state, die, __process_variable);
 }
 
-static int process_exported_symbols(struct state *unused, Dwarf_Die *die)
+static int process_exported_symbols(struct state *unused, struct die *cache,
+				    Dwarf_Die *die)
 {
 	int tag = dwarf_tag(die);
 
@@ -294,7 +354,7 @@  static int process_exported_symbols(struct state *unused, Dwarf_Die *die)
 	case DW_TAG_class_type:
 	case DW_TAG_structure_type:
 		return check(process_die_container(
-			NULL, die, process_exported_symbols, match_all));
+			NULL, cache, die, process_exported_symbols, match_all));
 
 	/* Possible exported symbols */
 	case DW_TAG_subprogram:
@@ -318,6 +378,6 @@  static int process_exported_symbols(struct state *unused, Dwarf_Die *die)
 
 void process_cu(Dwarf_Die *cudie)
 {
-	check(process_die_container(NULL, cudie, process_exported_symbols,
+	check(process_die_container(NULL, NULL, cudie, process_exported_symbols,
 				    match_all));
 }
diff --git a/scripts/gendwarfksyms/gendwarfksyms.c b/scripts/gendwarfksyms/gendwarfksyms.c
index 5032ec487626..66806b0936e4 100644
--- a/scripts/gendwarfksyms/gendwarfksyms.c
+++ b/scripts/gendwarfksyms/gendwarfksyms.c
@@ -43,6 +43,10 @@  static int process_module(Dwfl_Module *mod, void **userdata, const char *name,
 	debug("%s", name);
 	dbg = dwfl_module_getdwarf(mod, &dwbias);
 
+	/*
+	 * Look for exported symbols in each CU, follow the DIE tree, and add
+	 * the entries to die_map.
+	 */
 	do {
 		res = dwarf_get_units(dbg, cu, &cu, NULL, NULL, &cudie, NULL);
 		if (res < 0)
@@ -53,6 +57,8 @@  static int process_module(Dwfl_Module *mod, void **userdata, const char *name,
 		process_cu(&cudie);
 	} while (cu);
 
+	die_map_free();
+
 	return DWARF_CB_OK;
 }
 
diff --git a/scripts/gendwarfksyms/gendwarfksyms.h b/scripts/gendwarfksyms/gendwarfksyms.h
index a058647e2361..7df270429c21 100644
--- a/scripts/gendwarfksyms/gendwarfksyms.h
+++ b/scripts/gendwarfksyms/gendwarfksyms.h
@@ -89,6 +89,60 @@  void symbol_read_exports(FILE *file);
 void symbol_read_symtab(int fd);
 struct symbol *symbol_get(const char *name);
 
+/*
+ * die.c
+ */
+
+enum die_state {
+	DIE_INCOMPLETE,
+	DIE_COMPLETE,
+	DIE_LAST = DIE_COMPLETE
+};
+
+enum die_fragment_type {
+	FRAGMENT_EMPTY,
+	FRAGMENT_STRING,
+	FRAGMENT_DIE
+};
+
+struct die_fragment {
+	enum die_fragment_type type;
+	union {
+		char *str;
+		uintptr_t addr;
+	} data;
+	struct list_head list;
+};
+
+#define CASE_CONST_TO_STR(name) \
+	case name:              \
+		return #name;
+
+static inline const char *die_state_name(enum die_state state)
+{
+	switch (state) {
+	default:
+	CASE_CONST_TO_STR(DIE_INCOMPLETE)
+	CASE_CONST_TO_STR(DIE_COMPLETE)
+	}
+}
+
+struct die {
+	enum die_state state;
+	char *fqn;
+	int tag;
+	uintptr_t addr;
+	struct list_head fragments;
+	struct hlist_node hash;
+};
+
+int __die_map_get(uintptr_t addr, enum die_state state, struct die **res);
+struct die *die_map_get(Dwarf_Die *die, enum die_state state);
+void die_map_add_string(struct die *pd, const char *str);
+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);
+
 /*
  * dwarf.c
  */
@@ -98,12 +152,14 @@  struct state {
 	Dwarf_Die die;
 };
 
-typedef int (*die_callback_t)(struct state *state, Dwarf_Die *die);
+typedef int (*die_callback_t)(struct state *state, struct die *cache,
+			      Dwarf_Die *die);
 typedef bool (*die_match_callback_t)(Dwarf_Die *die);
 bool match_all(Dwarf_Die *die);
 
-int process_die_container(struct state *state, Dwarf_Die *die,
-			  die_callback_t func, die_match_callback_t match);
+int process_die_container(struct state *state, struct die *cache,
+			  Dwarf_Die *die, die_callback_t func,
+			  die_match_callback_t match);
 
 void process_cu(Dwarf_Die *cudie);