[PATCH 11/15] gendwarfksyms: Limit structure expansion

[Sami Tolvanen <samitolvanen@google.com>]

Expand each structure type only once per exported symbol. This
is necessary to support self-referential structures, which would
otherwise result in infinite recursion. Expanding each structure type
just once is enough to catch ABI changes.

For pointers to structure types, limit expansion to three levels
inside the pointer. This should be plenty for catching ABI differences
and stops us from pulling in half the kernel for structs that contain
pointers to large structs like task_struct.

Signed-off-by: Sami Tolvanen <samitolvanen@google.com>
---
 tools/gendwarfksyms/cache.c         | 49 ++++++++++++++++
 tools/gendwarfksyms/gendwarfksyms.h |  9 ++-
 tools/gendwarfksyms/types.c         | 87 ++++++++++++++++++++++++++---
 3 files changed, 136 insertions(+), 9 deletions(-)

diff --git a/tools/gendwarfksyms/cache.c b/tools/gendwarfksyms/cache.c
index 85a2adeb649d..1d6eb27d799d 100644
--- a/tools/gendwarfksyms/cache.c
+++ b/tools/gendwarfksyms/cache.c
@@ -158,3 +158,52 @@ int cache_add_die(struct cached_die *cd, Dwarf_Die *die)
 	ci->type = DIE;
 	return 0;
 }
+
+/* A list of structure types that were already expanded for the current symbol */
+struct expanded {
+	uintptr_t addr;
+	struct hlist_node hash;
+};
+
+/* die->addr -> struct expanded */
+DEFINE_HASHTABLE(expansion_cache, DIE_HASH_BITS);
+
+int cache_mark_expanded(Dwarf_Die *die)
+{
+	struct expanded *es;
+
+	es = malloc(sizeof(struct expanded));
+	if (!es) {
+		error("malloc failed");
+		return -1;
+	}
+
+	es->addr = (uintptr_t)die->addr;
+	hash_add(expansion_cache, &es->hash, es->addr);
+	return 0;
+}
+
+bool cache_was_expanded(Dwarf_Die *die)
+{
+	struct expanded *es;
+	uintptr_t addr = (uintptr_t)die->addr;
+
+	hash_for_each_possible(expansion_cache, es, hash, addr) {
+		if (es->addr == addr)
+			return true;
+	}
+
+	return false;
+}
+
+void cache_clear_expanded(void)
+{
+	struct hlist_node *tmp;
+	struct expanded *es;
+	int i;
+
+	hash_for_each_safe(expansion_cache, i, tmp, es, hash) {
+		free(es);
+	}
+	hash_init(expansion_cache);
+}
diff --git a/tools/gendwarfksyms/gendwarfksyms.h b/tools/gendwarfksyms/gendwarfksyms.h
index 4646eaf5c85e..568f3727017e 100644
--- a/tools/gendwarfksyms/gendwarfksyms.h
+++ b/tools/gendwarfksyms/gendwarfksyms.h
@@ -95,7 +95,7 @@ struct cached_item {
 	struct cached_item *next;
 };
 
-enum cached_die_state { INCOMPLETE, COMPLETE };
+enum cached_die_state { INCOMPLETE, UNEXPANDED, COMPLETE };
 
 struct cached_die {
 	enum cached_die_state state;
@@ -111,6 +111,10 @@ extern int cache_add_linebreak(struct cached_die *pd, int linebreak);
 extern int cache_add_die(struct cached_die *pd, Dwarf_Die *die);
 extern void cache_free(void);
 
+extern int cache_mark_expanded(Dwarf_Die *die);
+extern bool cache_was_expanded(Dwarf_Die *die);
+extern void cache_clear_expanded(void);
+
 /*
  * types.c
  */
@@ -120,6 +124,9 @@ struct state {
 	Dwarf *dbg;
 	struct symbol *sym;
 	Dwarf_Die origin;
+	unsigned int ptr_expansion_depth;
+	bool in_pointer_type;
+	bool expand;
 	unsigned long crc;
 };
 
diff --git a/tools/gendwarfksyms/types.c b/tools/gendwarfksyms/types.c
index fa74e6fc26e3..da3aa2ad9f57 100644
--- a/tools/gendwarfksyms/types.c
+++ b/tools/gendwarfksyms/types.c
@@ -381,14 +381,21 @@ static int __process_structure_type(struct state *state,
 	check(process(state, cache, " {"));
 	check(process_linebreak(cache, 1));
 
-	check(process_die_container(state, cache, die, process_func,
-				    match_func));
+	if (state->expand) {
+		check(cache_mark_expanded(die));
+		check(process_die_container(state, cache, die, process_func,
+					    match_func));
+	} else {
+		check(process(state, cache, "<unexpanded>"));
+	}
 
 	check(process_linebreak(cache, -1));
 	check(process(state, cache, "}"));
 
-	check(process_byte_size_attr(state, cache, die));
-	check(process_alignment_attr(state, cache, die));
+	if (state->expand) {
+		check(process_byte_size_attr(state, cache, die));
+		check(process_alignment_attr(state, cache, die));
+	}
 
 	return 0;
 }
@@ -475,9 +482,38 @@ static int process_cached(struct state *state, struct cached_die *cache,
 
 static void state_init(struct state *state)
 {
+	state->ptr_expansion_depth = 0;
+	state->in_pointer_type = false;
+	state->expand = true;
 	state->crc = 0xffffffff;
 }
 
+static void state_restore(struct state *state, struct state *saved)
+{
+	state->ptr_expansion_depth = saved->ptr_expansion_depth;
+	state->in_pointer_type = saved->in_pointer_type;
+	state->expand = saved->expand;
+}
+
+static void state_save(struct state *state, struct state *saved)
+{
+	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 3
+
 #define PROCESS_TYPE(type)                                       \
 	case DW_TAG_##type##_type:                               \
 		check(process_##type##_type(state, cache, die)); \
@@ -486,19 +522,52 @@ static void state_init(struct state *state)
 static int process_type(struct state *state, struct cached_die *parent,
 			Dwarf_Die *die)
 {
+	enum cached_die_state want_state = COMPLETE;
 	struct cached_die *cache = NULL;
+	struct state saved;
 	int tag = dwarf_tag(die);
 
+	state_save(state, &saved);
+
 	/*
-	 * If we have the DIE already cached, use it instead of walking
+	 * Structures and enumeration types are expanded only once per
+	 * exported symbol. This is sufficient for detecting ABI changes
+	 * within the structure.
+	 *
+	 * If the exported symbol contains a pointer to a structure,
+	 * at most MAX_POINTER_EXPANSION_DEPTH levels are expanded into
+	 * the referenced structure.
+	 */
+	state->in_pointer_type = saved.in_pointer_type || is_pointer_type(tag);
+
+	if (state->in_pointer_type &&
+	    state->ptr_expansion_depth >= MAX_POINTER_EXPANSION_DEPTH)
+		state->expand = false;
+	else
+		state->expand = saved.expand && !cache_was_expanded(die);
+
+	/* Keep track of pointer expansion depth */
+	if (state->expand && state->in_pointer_type && is_expanded_type(tag))
+		state->ptr_expansion_depth++;
+
+	/*
+	 * If we have want_state already cached, use it instead of walking
 	 * through DWARF.
 	 */
 	if (!no_cache) {
-		check(cache_get(die, COMPLETE, &cache));
+		if (!state->expand && is_expanded_type(tag))
+			want_state = UNEXPANDED;
+
+		check(cache_get(die, want_state, &cache));
+
+		if (cache->state == want_state) {
+			if (want_state == COMPLETE && is_expanded_type(tag))
+				check(cache_mark_expanded(die));
 
-		if (cache->state == COMPLETE) {
 			check(process_cached(state, cache, die));
 			check(cache_add_die(parent, die));
+
+			state_restore(state, &saved);
 			return 0;
 		}
 	}
@@ -540,10 +609,11 @@ static int process_type(struct state *state, struct cached_die *parent,
 
 	if (!no_cache) {
 		/* Update cache state and append to the parent (if any) */
-		cache->state = COMPLETE;
+		cache->state = want_state;
 		check(cache_add_die(parent, die));
 	}
 
+	state_restore(state, &saved);
 	return 0;
 }
 
@@ -596,6 +666,7 @@ static int process_exported_symbols(struct state *state,
 		else
 			check(process_variable(state, die));
 
+		cache_clear_expanded();
 		return check(
 			symbol_set_crc(state->sym, state->crc ^ 0xffffffff));
 	default:
-- 
2.45.2.627.g7a2c4fd464-goog