Message-ID: <CAK7LNARQncjxxqbjiMHXdAnakpo8QYo-5kYnN=KaD2xDe0uXPA@mail.gmail.com>
Date: Thu, 29 Aug 2024 03:15:02 +0900
From: Masahiro Yamada <masahiroy@...nel.org>
To: Sami Tolvanen <samitolvanen@...gle.com>
Cc: Luis Chamberlain <mcgrof@...nel.org>, Miguel Ojeda <ojeda@...nel.org>, 
	Greg Kroah-Hartman <gregkh@...uxfoundation.org>, Matthew Maurer <mmaurer@...gle.com>, 
	Alex Gaynor <alex.gaynor@...il.com>, Wedson Almeida Filho <wedsonaf@...il.com>, Gary Guo <gary@...yguo.net>, 
	Petr Pavlu <petr.pavlu@...e.com>, Neal Gompa <neal@...pa.dev>, Hector Martin <marcan@...can.st>, 
	Janne Grunau <j@...nau.net>, Asahi Linux <asahi@...ts.linux.dev>, linux-kbuild@...r.kernel.org, 
	linux-kernel@...r.kernel.org, linux-modules@...r.kernel.org, 
	rust-for-linux@...r.kernel.org
Subject: Re: [PATCH v2 06/19] gendwarfksyms: Add a cache for processed DIEs

On Fri, Aug 16, 2024 at 2:39 AM Sami Tolvanen <samitolvanen@...gle.com> 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@...gle.com>
> ---
>  scripts/gendwarfksyms/Makefile        |   1 +
>  scripts/gendwarfksyms/die.c           | 170 +++++++++++++++++++++++
>  scripts/gendwarfksyms/dwarf.c         | 192 ++++++++++++++++++++------
>  scripts/gendwarfksyms/gendwarfksyms.c |   6 +
>  scripts/gendwarfksyms/gendwarfksyms.h |  58 +++++++-
>  5 files changed, 382 insertions(+), 45 deletions(-)
>  create mode 100644 scripts/gendwarfksyms/die.c
>
> diff --git a/scripts/gendwarfksyms/Makefile b/scripts/gendwarfksyms/Makefile
> index 623f8fc975ea..fcbac52ca00a 100644
> --- a/scripts/gendwarfksyms/Makefile
> +++ b/scripts/gendwarfksyms/Makefile
> @@ -1,6 +1,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..ad6ba435d9dd
> --- /dev/null
> +++ b/scripts/gendwarfksyms/die.c
> @@ -0,0 +1,170 @@
> +// SPDX-License-Identifier: GPL-2.0-or-later
> +/*
> + * Copyright (C) 2024 Google LLC
> + */
> +
> +#include <string.h>
> +#include "gendwarfksyms.h"
> +
> +#define DIE_HASH_BITS 20
> +
> +/* uintptr_t die->addr -> struct die * */
> +static DEFINE_HASHTABLE(die_map, DIE_HASH_BITS);
> +
> +static unsigned int map_hits;
> +static unsigned int map_misses;
> +
> +static int create_die(Dwarf_Die *die, struct die **res)
> +{
> +       struct die *cd;
> +
> +       cd = malloc(sizeof(struct die));
> +       if (!cd) {
> +               error("malloc failed");
> +               return -1;
> +       }
> +
> +       cd->state = INCOMPLETE;
> +       cd->mapped = false;
> +       cd->fqn = NULL;
> +       cd->tag = -1;
> +       cd->addr = (uintptr_t)die->addr;
> +       cd->list = NULL;
> +
> +       hash_add(die_map, &cd->hash, addr_hash(cd->addr));
> +       *res = cd;
> +       return 0;
> +}
> +
> +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, addr_hash(addr)) {
> +               if (cd->addr == addr && cd->state == state) {
> +                       *res = cd;
> +                       return 0;
> +               }
> +       }
> +
> +       return -1;
> +}
> +
> +int die_map_get(Dwarf_Die *die, enum die_state state, struct die **res)
> +{
> +       if (__die_map_get((uintptr_t)die->addr, state, res) == 0) {
> +               map_hits++;
> +               return 0;
> +       }
> +
> +       map_misses++;
> +       return check(create_die(die, res));
> +}
> +
> +static void reset_die(struct die *cd)
> +{
> +       struct die_fragment *tmp;
> +       struct die_fragment *df = cd->list;
> +
> +       while (df) {
> +               if (df->type == STRING)
> +                       free(df->data.str);
> +
> +               tmp = df->next;
> +               free(df);
> +               df = tmp;
> +       }
> +
> +       cd->state = INCOMPLETE;
> +       cd->mapped = false;
> +       if (cd->fqn)
> +               free(cd->fqn);
> +       cd->fqn = NULL;
> +       cd->tag = -1;
> +       cd->addr = 0;
> +       cd->list = NULL;
> +}
> +
> +void die_map_free(void)
> +{
> +       struct hlist_node *tmp;
> +       unsigned int stats[LAST + 1];
> +       struct die *cd;
> +       int i;
> +
> +       memset(stats, 0, sizeof(stats));
> +
> +       hash_for_each_safe(die_map, i, tmp, cd, 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 <= LAST; i++)
> +               debug("%s: %u entries", die_state_name(i), stats[i]);
> +}
> +
> +static int append_item(struct die *cd, struct die_fragment **res)
> +{
> +       struct die_fragment *prev;
> +       struct die_fragment *df;
> +
> +       df = malloc(sizeof(struct die_fragment));
> +       if (!df) {
> +               error("malloc failed");
> +               return -1;
> +       }
> +
> +       df->type = EMPTY;
> +       df->next = NULL;
> +
> +       prev = cd->list;
> +       while (prev && prev->next)
> +               prev = prev->next;



So, this entirely traverses the singly-linked list
every time a new item is appended to the tail.


In my analysis, this while loop iterates for thousands
of times in total for emitting each export symbol.


Why isn't this list_add_tail()?








--
Best Regards
Masahiro Yamada

Powered by blists - more mailing lists