| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Mon, 17 Jun 2024 17:58:24 +0000
From: Sami Tolvanen <samitolvanen@...gle.com>
To: Masahiro Yamada <masahiroy@...nel.org>, Luis Chamberlain <mcgrof@...nel.org>,
Miguel Ojeda <ojeda@...nel.org>, Greg Kroah-Hartman <gregkh@...uxfoundation.org>
Cc: Matthew Maurer <mmaurer@...gle.com>, Alex Gaynor <alex.gaynor@...il.com>,
Wedson Almeida Filho <wedsonaf@...il.com>, Gary Guo <gary@...yguo.net>, linux-kbuild@...r.kernel.org,
linux-kernel@...r.kernel.org, linux-modules@...r.kernel.org,
rust-for-linux@...r.kernel.org, Sami Tolvanen <samitolvanen@...gle.com>
Subject: [PATCH 05/15] gendwarfksyms: Add a cache
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>
---
tools/gendwarfksyms/Build | 1 +
tools/gendwarfksyms/cache.c | 147 ++++++++++++++++++++++++++++
tools/gendwarfksyms/gendwarfksyms.c | 4 +
tools/gendwarfksyms/gendwarfksyms.h | 37 ++++++-
tools/gendwarfksyms/types.c | 140 ++++++++++++++++++--------
5 files changed, 286 insertions(+), 43 deletions(-)
create mode 100644 tools/gendwarfksyms/cache.c
diff --git a/tools/gendwarfksyms/Build b/tools/gendwarfksyms/Build
index 518642c9b9de..220a4aa9b380 100644
--- a/tools/gendwarfksyms/Build
+++ b/tools/gendwarfksyms/Build
@@ -1,4 +1,5 @@
gendwarfksyms-y += gendwarfksyms.o
+gendwarfksyms-y += cache.o
gendwarfksyms-y += crc32.o
gendwarfksyms-y += symbols.o
gendwarfksyms-y += types.o
diff --git a/tools/gendwarfksyms/cache.c b/tools/gendwarfksyms/cache.c
new file mode 100644
index 000000000000..9adda113e0b6
--- /dev/null
+++ b/tools/gendwarfksyms/cache.c
@@ -0,0 +1,147 @@
+// SPDX-License-Identifier: GPL-2.0-or-later
+/*
+ * Copyright (C) 2024 Google LLC
+ */
+
+#include <string.h>
+#include "gendwarfksyms.h"
+
+#define DIE_HASH_BITS 10
+
+/* die->addr -> struct cached_die */
+DEFINE_HASHTABLE(die_cache, DIE_HASH_BITS);
+
+static unsigned int cache_hits;
+static unsigned int cache_misses;
+
+static int create_die(Dwarf_Die *die, struct cached_die **res)
+{
+ struct cached_die *cd;
+
+ cd = malloc(sizeof(struct cached_die));
+ if (!cd) {
+ error("malloc failed");
+ return -1;
+ }
+
+ cd->state = INCOMPLETE;
+ cd->addr = (uintptr_t)die->addr;
+ cd->list = NULL;
+
+ hash_add(die_cache, &cd->hash, cd->addr);
+ *res = cd;
+ return 0;
+}
+
+int cache_get(Dwarf_Die *die, enum cached_die_state state,
+ struct cached_die **res)
+{
+ struct cached_die *cd;
+ uintptr_t addr = (uintptr_t)die->addr;
+
+ hash_for_each_possible(die_cache, cd, hash, addr) {
+ if (cd->addr == addr && cd->state == state) {
+ *res = cd;
+ cache_hits++;
+ return 0;
+ }
+ }
+
+ cache_misses++;
+ return check(create_die(die, res));
+}
+
+static void reset_die(struct cached_die *cd)
+{
+ struct cached_item *tmp;
+ struct cached_item *ci = cd->list;
+
+ while (ci) {
+ if (ci->type == STRING)
+ free(ci->data.str);
+
+ tmp = ci->next;
+ free(ci);
+ ci = tmp;
+ }
+
+ cd->state = INCOMPLETE;
+ cd->list = NULL;
+}
+
+void cache_free(void)
+{
+ struct cached_die *cd;
+ struct hlist_node *tmp;
+ int i;
+
+ hash_for_each_safe(die_cache, i, tmp, cd, hash) {
+ reset_die(cd);
+ free(cd);
+ }
+ hash_init(die_cache);
+
+ if ((cache_hits + cache_misses > 0))
+ debug("cache: hits %u, misses %u (hit rate %.02f%%)",
+ cache_hits, cache_misses,
+ (100.0f * cache_hits) / (cache_hits + cache_misses));
+}
+
+static int append_item(struct cached_die *cd, struct cached_item **res)
+{
+ struct cached_item *prev;
+ struct cached_item *ci;
+
+ ci = malloc(sizeof(struct cached_item));
+ if (!ci) {
+ error("malloc failed");
+ return -1;
+ }
+
+ ci->type = EMPTY;
+ ci->next = NULL;
+
+ prev = cd->list;
+ while (prev && prev->next)
+ prev = prev->next;
+
+ if (prev)
+ prev->next = ci;
+ else
+ cd->list = ci;
+
+ *res = ci;
+ return 0;
+}
+
+int cache_add_string(struct cached_die *cd, const char *str)
+{
+ struct cached_item *ci;
+
+ if (!cd)
+ return 0;
+
+ check(append_item(cd, &ci));
+
+ ci->data.str = strdup(str);
+ if (!ci->data.str) {
+ error("strdup failed");
+ return -1;
+ }
+
+ ci->type = STRING;
+ return 0;
+}
+
+int cache_add_die(struct cached_die *cd, Dwarf_Die *die)
+{
+ struct cached_item *ci;
+
+ if (!cd)
+ return 0;
+
+ check(append_item(cd, &ci));
+ ci->data.addr = (uintptr_t)die->addr;
+ ci->type = DIE;
+ return 0;
+}
diff --git a/tools/gendwarfksyms/gendwarfksyms.c b/tools/gendwarfksyms/gendwarfksyms.c
index 7938b7440674..38ccaeb72426 100644
--- a/tools/gendwarfksyms/gendwarfksyms.c
+++ b/tools/gendwarfksyms/gendwarfksyms.c
@@ -15,12 +15,15 @@
/* Print type descriptions and debugging output to stderr */
bool debug;
+/* Don't use caching */
+bool no_cache;
static const struct {
const char *arg;
bool *flag;
} options[] = {
{ "--debug", &debug },
+ { "--no-cache", &no_cache },
};
static int usage(void)
@@ -126,6 +129,7 @@ int main(int argc, const char **argv)
dwfl_end(dwfl);
symbol_print_versions();
+ cache_free();
return 0;
}
diff --git a/tools/gendwarfksyms/gendwarfksyms.h b/tools/gendwarfksyms/gendwarfksyms.h
index 7440f1c73500..ea5a9fbda66f 100644
--- a/tools/gendwarfksyms/gendwarfksyms.h
+++ b/tools/gendwarfksyms/gendwarfksyms.h
@@ -18,6 +18,7 @@
* Options -- in gendwarfksyms.c
*/
extern bool debug;
+extern bool no_cache;
/*
* Output helpers
@@ -69,6 +70,35 @@ extern int symbol_read_list(FILE *file);
extern struct symbol *symbol_get(uintptr_t addr, const char *name);
extern void symbol_print_versions(void);
+/*
+ * cache.c
+ */
+enum cached_item_type { EMPTY, STRING, DIE };
+
+struct cached_item {
+ enum cached_item_type type;
+ union {
+ char *str;
+ uintptr_t addr;
+ } data;
+ struct cached_item *next;
+};
+
+enum cached_die_state { INCOMPLETE, COMPLETE };
+
+struct cached_die {
+ enum cached_die_state state;
+ uintptr_t addr;
+ struct cached_item *list;
+ struct hlist_node hash;
+};
+
+extern int cache_get(Dwarf_Die *die, enum cached_die_state state,
+ struct cached_die **res);
+extern int cache_add_string(struct cached_die *pd, const char *str);
+extern int cache_add_die(struct cached_die *pd, Dwarf_Die *die);
+extern void cache_free(void);
+
/*
* types.c
*/
@@ -81,12 +111,13 @@ struct state {
unsigned long crc;
};
-typedef int (*die_callback_t)(struct state *state, Dwarf_Die *die);
+typedef int (*die_callback_t)(struct state *state, struct cached_die *cache,
+ Dwarf_Die *die);
typedef bool (*die_match_callback_t)(Dwarf_Die *die);
extern bool match_all(Dwarf_Die *die);
-extern int process_die_container(struct state *state, Dwarf_Die *die,
- die_callback_t func,
+extern int process_die_container(struct state *state, struct cached_die *cache,
+ Dwarf_Die *die, die_callback_t func,
die_match_callback_t match);
extern int process_module(Dwfl_Module *mod, Dwarf *dbg, Dwarf_Die *cudie);
diff --git a/tools/gendwarfksyms/types.c b/tools/gendwarfksyms/types.c
index 7508d0fb8b80..78046c08be23 100644
--- a/tools/gendwarfksyms/types.c
+++ b/tools/gendwarfksyms/types.c
@@ -72,7 +72,7 @@ static Dwarf_Die *get_exported(struct state *state, Dwarf_Die *die)
/*
* Type string and CRC processing
*/
-static int process(struct state *state, const char *s)
+static int process(struct state *state, struct cached_die *cache, const char *s)
{
s = s ?: "<null>";
@@ -80,12 +80,13 @@ static int process(struct state *state, const char *s)
fputs(s, stderr);
state->crc = partial_crc32(s, state->crc);
- return 0;
+ return cache_add_string(cache, s);
}
#define MAX_FMT_BUFFER_SIZE 128
-static int process_fmt(struct state *state, const char *fmt, ...)
+static int process_fmt(struct state *state, struct cached_die *cache,
+ const char *fmt, ...)
{
char buf[MAX_FMT_BUFFER_SIZE];
va_list args;
@@ -98,7 +99,7 @@ static int process_fmt(struct state *state, const char *fmt, ...)
error("vsnprintf overflow: increase MAX_FMT_BUFFER_SIZE");
res = -1;
} else {
- check(process(state, buf));
+ check(process(state, cache, buf));
}
va_end(args);
@@ -106,7 +107,8 @@ static int process_fmt(struct state *state, const char *fmt, ...)
}
/* Process a fully qualified name from DWARF scopes */
-static int process_fqn(struct state *state, Dwarf_Die *die)
+static int process_fqn(struct state *state, struct cached_die *cache,
+ Dwarf_Die *die)
{
Dwarf_Die *scopes = NULL;
const char *name;
@@ -117,7 +119,7 @@ static int process_fqn(struct state *state, Dwarf_Die *die)
if (!res) {
name = get_name(die);
name = name ?: "<unnamed>";
- return check(process(state, name));
+ return check(process(state, cache, name));
}
for (i = res - 1; i >= 0; i--) {
@@ -126,25 +128,25 @@ static int process_fqn(struct state *state, Dwarf_Die *die)
name = get_name(&scopes[i]);
name = name ?: "<unnamed>";
- check(process(state, name));
+ check(process(state, cache, name));
if (i > 0)
- check(process(state, "::"));
+ check(process(state, cache, "::"));
}
free(scopes);
return 0;
}
-#define DEFINE_PROCESS_UDATA_ATTRIBUTE(attribute) \
- static int process_##attribute##_attr(struct state *state, \
- Dwarf_Die *die) \
- { \
- Dwarf_Word value; \
- if (get_udata_attr(die, DW_AT_##attribute, &value)) \
- check(process_fmt(state, \
- " " #attribute "(%" PRIu64 ")", \
- value)); \
- return 0; \
+#define DEFINE_PROCESS_UDATA_ATTRIBUTE(attribute) \
+ static int process_##attribute##_attr( \
+ struct state *state, struct cached_die *cache, Dwarf_Die *die) \
+ { \
+ Dwarf_Word value; \
+ if (get_udata_attr(die, DW_AT_##attribute, &value)) \
+ check(process_fmt(state, cache, \
+ " " #attribute "(%" PRIu64 ")", \
+ value)); \
+ return 0; \
}
DEFINE_PROCESS_UDATA_ATTRIBUTE(alignment)
@@ -155,8 +157,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 cached_die *cache,
+ Dwarf_Die *die, die_callback_t func,
+ die_match_callback_t match)
{
Dwarf_Die current;
int res;
@@ -164,32 +167,65 @@ int process_die_container(struct state *state, Dwarf_Die *die,
res = check(dwarf_child(die, ¤t));
while (!res) {
if (match(¤t))
- check(func(state, ¤t));
+ check(func(state, cache, ¤t));
res = check(dwarf_siblingof(¤t, ¤t));
}
return 0;
}
-static int process_type(struct state *state, Dwarf_Die *die);
+static int process_type(struct state *state, struct cached_die *parent,
+ Dwarf_Die *die);
-static int process_type_attr(struct state *state, Dwarf_Die *die)
+static int process_type_attr(struct state *state, struct cached_die *cache,
+ Dwarf_Die *die)
{
Dwarf_Die type;
if (get_ref_die_attr(die, DW_AT_type, &type))
- return check(process_type(state, &type));
+ return check(process_type(state, cache, &type));
/* Compilers can omit DW_AT_type -- print out 'void' to clarify */
- return check(process(state, "base_type void"));
+ return check(process(state, cache, "base_type void"));
+}
+
+static int process_base_type(struct state *state, struct cached_die *cache,
+ Dwarf_Die *die)
+{
+ check(process(state, cache, "base_type "));
+ check(process_fqn(state, cache, die));
+ check(process_byte_size_attr(state, cache, die));
+ return check(process_alignment_attr(state, cache, die));
}
-static int process_base_type(struct state *state, Dwarf_Die *die)
+static int process_cached(struct state *state, struct cached_die *cache,
+ Dwarf_Die *die)
{
- check(process(state, "base_type "));
- check(process_fqn(state, die));
- check(process_byte_size_attr(state, die));
- return check(process_alignment_attr(state, die));
+ struct cached_item *ci = cache->list;
+ Dwarf_Die child;
+
+ while (ci) {
+ switch (ci->type) {
+ case STRING:
+ check(process(state, NULL, ci->data.str));
+ break;
+ case DIE:
+ if (!dwarf_die_addr_die(state->dbg,
+ (void *)ci->data.addr,
+ &child)) {
+ error("dwarf_die_addr_die failed");
+ return -1;
+ }
+ check(process_type(state, NULL, &child));
+ break;
+ default:
+ error("empty cached_item");
+ return -1;
+ }
+ ci = ci->next;
+ }
+
+ return 0;
}
static void state_init(struct state *state)
@@ -197,19 +233,41 @@ static void state_init(struct state *state)
state->crc = 0xffffffff;
}
-static int process_type(struct state *state, Dwarf_Die *die)
+static int process_type(struct state *state, struct cached_die *parent,
+ Dwarf_Die *die)
{
+ struct cached_die *cache = NULL;
int tag = dwarf_tag(die);
+ /*
+ * If we have the DIE already cached, use it instead of walking
+ * through DWARF.
+ */
+ if (!no_cache) {
+ check(cache_get(die, COMPLETE, &cache));
+
+ if (cache->state == COMPLETE) {
+ check(process_cached(state, cache, die));
+ check(cache_add_die(parent, die));
+ return 0;
+ }
+ }
+
switch (tag) {
case DW_TAG_base_type:
- check(process_base_type(state, die));
+ check(process_base_type(state, cache, die));
break;
default:
debug("unimplemented type: %x", tag);
break;
}
+ if (!no_cache) {
+ /* Update cache state and append to the parent (if any) */
+ cache->state = COMPLETE;
+ check(cache_add_die(parent, die));
+ }
+
return 0;
}
@@ -218,17 +276,18 @@ static int process_type(struct state *state, Dwarf_Die *die)
*/
static int process_subprogram(struct state *state, Dwarf_Die *die)
{
- return check(process(state, "subprogram;\n"));
+ return check(process(state, NULL, "subprogram;\n"));
}
static int process_variable(struct state *state, Dwarf_Die *die)
{
- check(process(state, "variable "));
- check(process_type_attr(state, die));
- return check(process(state, ";\n"));
+ check(process(state, NULL, "variable "));
+ check(process_type_attr(state, NULL, die));
+ return check(process(state, NULL, ";\n"));
}
-static int process_exported_symbols(struct state *state, Dwarf_Die *die)
+static int process_exported_symbols(struct state *state,
+ struct cached_die *cache, Dwarf_Die *die)
{
int tag = dwarf_tag(die);
@@ -237,8 +296,9 @@ static int process_exported_symbols(struct state *state, Dwarf_Die *die)
case DW_TAG_namespace:
case DW_TAG_class_type:
case DW_TAG_structure_type:
- return check(process_die_container(
- state, die, process_exported_symbols, match_all));
+ return check(process_die_container(state, cache, die,
+ process_exported_symbols,
+ match_all));
/* Possible exported symbols */
case DW_TAG_subprogram:
@@ -271,5 +331,5 @@ int process_module(Dwfl_Module *mod, Dwarf *dbg, Dwarf_Die *cudie)
struct state state = { .mod = mod, .dbg = dbg };
return check(process_die_container(
- &state, cudie, process_exported_symbols, match_all));
+ &state, NULL, cudie, process_exported_symbols, match_all));
}
--
2.45.2.627.g7a2c4fd464-goog
Powered by blists - more mailing lists