[PATCH dwarves v3] btf_encoder: group all function ELF syms by function name

[Ihor Solodrai <ihor.solodrai@linux.dev>]

btf_encoder collects function ELF symbols into a table, which is later
used for processing DWARF data and determining whether a function can
be added to BTF.

So far the ELF symbol name was used as a key for search in this table,
and a search by prefix match was attempted in cases when ELF symbol
name has a compiler-generated suffix.

This implementation has bugs [1][2], causing some functions to be
inappropriately excluded from (or included into) BTF.

Rework the implementation of the ELF functions table. Use a name of a
function without any suffix - a symbol name before the first
occurrence of '.' - as a key. This way btf_encoder__find_function()
always returns a valid elf_function object (or NULL).

Collect an array of symbol name + address pairs from GElf_Sym for each
elf_function when building the elf_functions table.

Take into account that some symbols associated with a function name
are not relevant, and do not collect them into elf_functions table:
  * ".cold" suffix indicates a piece of hot/cold split
  * ".part" suffix indicates a piece of partial inline

When inspecting symbol name we have to search for any occurrence of
the target suffix, as opposed to testing the entire suffix, or the end
of a string. This is because suffixes may be combined by the compiler,
for example producing ".isra0.cold", and the conclusion will be
incorrect.

Introduce ambiguous_addr flag to the elf_function. It is set when the
functions are deduped in elf_functions__collect() examining the array
of ELF symbols in elf_function__has_ambiguous_address(). It tests
whether there is only one unique address for this function name.

In btf_encoder__add_saved_funcs() check ambiguous_addr flag when
deciding whether a function should be included in BTF.

Successful CI run: https://github.com/acmel/dwarves/actions/runs/16683734552

[1] https://lore.kernel.org/bpf/2f8c792e-9675-4385-b1cb-10266c72bd45@linux.dev/
[2] https://lore.kernel.org/dwarves/6b4fda90fbf8f6aeeb2732bbfb6e81ba5669e2f3@linux.dev/

v2->v3:
  * Move ambiguous_addr flag from btf_encoder_func_state to
    elf_function. We don't have to process DWARF to know the value of
    ambiguous_addr, so elf_function is more appropriate.
  * Don't even add symbols with non_fn suffixes into elf_functions
    table. This saves us space and string comparisons. (Alan)
  * Increase elf_function->sym_cnt size from u8 to u16, and other
    nits. (Jiri)

v2: https://github.com/acmel/dwarves/pull/68/commits/f23968d964eb50359715257962a6f9e07c8cf793
v2 (discussion): https://lore.kernel.org/dwarves/aIjG4q6oirhi4pN1@krava/
v1: https://lore.kernel.org/dwarves/98f41eaf6dd364745013650d58c5f254a592221c@linux.dev/

Signed-off-by: Ihor Solodrai <ihor.solodrai@linux.dev>
Acked-by: Jiri Olsa <jolsa@kernel.org>
---
 btf_encoder.c | 247 ++++++++++++++++++++++++++++++++------------------
 1 file changed, 161 insertions(+), 86 deletions(-)

diff --git a/btf_encoder.c b/btf_encoder.c
index 0bc2334..1803e86 100644
--- a/btf_encoder.c
+++ b/btf_encoder.c
@@ -92,11 +92,17 @@ struct btf_encoder_func_state {
 	struct btf_encoder_func_annot *annots;
 };
 
+struct elf_function_sym {
+	const char *name;
+	uint64_t addr;
+};
+
 struct elf_function {
-	const char	*name;
-	char		*alias;
-	size_t		prefixlen;
-	bool		kfunc;
+	char		*name;
+	struct elf_function_sym *syms;
+	uint16_t 	sym_cnt;
+	uint16_t 	ambiguous_addr:1;
+	uint16_t	kfunc:1;
 	uint32_t	kfunc_flags;
 };
 
@@ -115,7 +121,6 @@ struct elf_functions {
 	struct elf_symtab *symtab;
 	struct elf_function *entries;
 	int cnt;
-	int suffix_cnt; /* number of .isra, .part etc */
 };
 
 /*
@@ -161,10 +166,18 @@ struct btf_kfunc_set_range {
 	uint64_t end;
 };
 
+static inline void elf_function__clear(struct elf_function *func) {
+	free(func->name);
+	if (func->sym_cnt)
+		free(func->syms);
+	memset(func, 0, sizeof(*func));
+}
+
 static inline void elf_functions__delete(struct elf_functions *funcs)
 {
-	for (int i = 0; i < funcs->cnt; i++)
-		free(funcs->entries[i].alias);
+	for (int i = 0; i < funcs->cnt; i++) {
+		elf_function__clear(&funcs->entries[i]);
+	}
 	free(funcs->entries);
 	elf_symtab__delete(funcs->symtab);
 	list_del(&funcs->node);
@@ -981,8 +994,7 @@ static void btf_encoder__log_func_skip(struct btf_encoder *encoder, struct elf_f
 
 	if (!encoder->verbose)
 		return;
-	printf("%s (%s): skipping BTF encoding of function due to ",
-	       func->alias ?: func->name, func->name);
+	printf("%s : skipping BTF encoding of function due to ", func->name);
 	va_start(ap, fmt);
 	vprintf(fmt, ap);
 	va_end(ap);
@@ -1176,6 +1188,47 @@ static struct btf_encoder_func_state *btf_encoder__alloc_func_state(struct btf_e
 	return state;
 }
 
+/* some "." suffixes do not correspond to real functions;
+ * - .part for partial inline
+ * - .cold for rarely-used codepath extracted for better code locality
+ */
+static inline bool is_non_fn_suffix(const char *suffix) {
+	static const char *skip[] = {
+		".cold",
+		".part"
+	};
+	int i;
+
+	if (!suffix)
+		return false;
+
+	for (i = 0; i < ARRAY_SIZE(skip); i++) {
+		if (strstr(suffix, skip[i]))
+			return true;
+	}
+
+	return false;
+}
+
+static bool elf_function__has_ambiguous_address(struct elf_function *func) {
+	struct elf_function_sym *sym;
+	uint64_t addr;
+
+	if (func->sym_cnt <= 1)
+		return false;
+
+	addr = 0;
+	for (int i = 0; i < func->sym_cnt; i++) {
+		sym = &func->syms[i];
+		if (addr && addr != sym->addr)
+			return true;
+		else
+			addr = sym->addr;
+	}
+
+	return false;
+}
+
 static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct function *fn, struct elf_function *func)
 {
 	struct btf_encoder_func_state *state = btf_encoder__alloc_func_state(encoder);
@@ -1294,7 +1347,7 @@ static int32_t btf_encoder__add_func(struct btf_encoder *encoder,
 	int err;
 
 	btf_fnproto_id = btf_encoder__add_func_proto(encoder, NULL, state);
-	name = func->alias ?: func->name;
+	name = func->name;
 	if (btf_fnproto_id >= 0)
 		btf_fn_id = btf_encoder__add_ref_type(encoder, BTF_KIND_FUNC, btf_fnproto_id,
 						      name, false);
@@ -1338,40 +1391,29 @@ static int32_t btf_encoder__add_func(struct btf_encoder *encoder,
 	return 0;
 }
 
-static int functions_cmp(const void *_a, const void *_b)
+static int elf_function__name_cmp(const void *_a, const void *_b)
 {
 	const struct elf_function *a = _a;
 	const struct elf_function *b = _b;
 
-	/* if search key allows prefix match, verify target has matching
-	 * prefix len and prefix matches.
-	 */
-	if (a->prefixlen && a->prefixlen == b->prefixlen)
-		return strncmp(a->name, b->name, b->prefixlen);
 	return strcmp(a->name, b->name);
 }
 
-#ifndef max
-#define max(x, y) ((x) < (y) ? (y) : (x))
-#endif
-
 static int saved_functions_cmp(const void *_a, const void *_b)
 {
 	const struct btf_encoder_func_state *a = _a;
 	const struct btf_encoder_func_state *b = _b;
 
-	return functions_cmp(a->elf, b->elf);
+	return elf_function__name_cmp(a->elf, b->elf);
 }
 
 static int saved_functions_combine(struct btf_encoder_func_state *a, struct btf_encoder_func_state *b)
 {
 	uint8_t optimized, unexpected, inconsistent;
-	int ret;
 
-	ret = strncmp(a->elf->name, b->elf->name,
-		      max(a->elf->prefixlen, b->elf->prefixlen));
-	if (ret != 0)
-		return ret;
+	if (a->elf != b->elf)
+		return 1;
+
 	optimized = a->optimized_parms | b->optimized_parms;
 	unexpected = a->unexpected_reg | b->unexpected_reg;
 	inconsistent = a->inconsistent_proto | b->inconsistent_proto;
@@ -1432,7 +1474,7 @@ static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder, bool skip_e
 		 * just do not _use_ them.  Only exclude functions with
 		 * unexpected register use or multiple inconsistent prototypes.
 		 */
-		add_to_btf |= !state->unexpected_reg && !state->inconsistent_proto;
+		add_to_btf |= !state->unexpected_reg && !state->inconsistent_proto && !state->elf->ambiguous_addr;
 
 		if (add_to_btf) {
 			err = btf_encoder__add_func(state->encoder, state);
@@ -1447,32 +1489,6 @@ out:
 	return err;
 }
 
-static void elf_functions__collect_function(struct elf_functions *functions, GElf_Sym *sym)
-{
-	struct elf_function *func;
-	const char *name;
-
-	if (elf_sym__type(sym) != STT_FUNC)
-		return;
-
-	name = elf_sym__name(sym, functions->symtab);
-	if (!name)
-		return;
-
-	func = &functions->entries[functions->cnt];
-	func->name = name;
-	if (strchr(name, '.')) {
-		const char *suffix = strchr(name, '.');
-
-		functions->suffix_cnt++;
-		func->prefixlen = suffix - name;
-	} else {
-		func->prefixlen = strlen(name);
-	}
-
-	functions->cnt++;
-}
-
 static struct elf_functions *btf_encoder__elf_functions(struct btf_encoder *encoder)
 {
 	struct elf_functions *funcs = NULL;
@@ -1490,13 +1506,12 @@ static struct elf_functions *btf_encoder__elf_functions(struct btf_encoder *enco
 	return funcs;
 }
 
-static struct elf_function *btf_encoder__find_function(const struct btf_encoder *encoder,
-						       const char *name, size_t prefixlen)
+static struct elf_function *btf_encoder__find_function(const struct btf_encoder *encoder, const char *name)
 {
 	struct elf_functions *funcs = elf_functions__find(encoder->cu->elf, &encoder->elf_functions_list);
-	struct elf_function key = { .name = name, .prefixlen = prefixlen };
+	struct elf_function key = { .name = (char*)name };
 
-	return bsearch(&key, funcs->entries, funcs->cnt, sizeof(key), functions_cmp);
+	return bsearch(&key, funcs->entries, funcs->cnt, sizeof(key), elf_function__name_cmp);
 }
 
 static bool btf_name_char_ok(char c, bool first)
@@ -2060,7 +2075,7 @@ static int btf_encoder__collect_kfuncs(struct btf_encoder *encoder)
 			continue;
 		}
 
-		elf_fn = btf_encoder__find_function(encoder, func, 0);
+		elf_fn = btf_encoder__find_function(encoder, func);
 		if (elf_fn) {
 			elf_fn->kfunc = true;
 			elf_fn->kfunc_flags = pair->flags;
@@ -2135,14 +2150,34 @@ int btf_encoder__encode(struct btf_encoder *encoder, struct conf_load *conf)
 	return err;
 }
 
+static inline int elf_function__push_sym(struct elf_function *func, struct elf_function_sym *sym) {
+	struct elf_function_sym *tmp;
+
+	if (func->sym_cnt)
+		tmp = realloc(func->syms, (func->sym_cnt + 1) * sizeof(func->syms[0]));
+	else
+		tmp = calloc(sizeof(func->syms[0]), 1);
+
+	if (!tmp)
+		return -ENOMEM;
+
+	func->syms = tmp;
+	func->syms[func->sym_cnt] = *sym;
+	func->sym_cnt++;
+
+	return 0;
+}
+
 static int elf_functions__collect(struct elf_functions *functions)
 {
 	uint32_t nr_symbols = elf_symtab__nr_symbols(functions->symtab);
-	struct elf_function *tmp;
+	struct elf_function_sym func_sym;
+	struct elf_function *func, *tmp;
+	const char *sym_name, *suffix;
 	Elf32_Word sym_sec_idx;
+	int err = 0, i, j;
 	uint32_t core_id;
 	GElf_Sym sym;
-	int err = 0;
 
 	/* We know that number of functions is less than number of symbols,
 	 * so we can overallocate temporarily.
@@ -2153,18 +2188,77 @@ static int elf_functions__collect(struct elf_functions *functions)
 		goto out_free;
 	}
 
+	/* First, collect an elf_function for each GElf_Sym
+	 * Where func->name is without a suffix
+	 */
 	functions->cnt = 0;
 	elf_symtab__for_each_symbol_index(functions->symtab, core_id, sym, sym_sec_idx) {
-		elf_functions__collect_function(functions, &sym);
+
+		if (elf_sym__type(&sym) != STT_FUNC)
+			continue;
+
+		sym_name = elf_sym__name(&sym, functions->symtab);
+		if (!sym_name)
+			continue;
+
+		suffix = strchr(sym_name, '.');
+		if (is_non_fn_suffix(sym_name))
+			continue;
+
+		func = &functions->entries[functions->cnt];
+		if (suffix)
+			func->name = strndup(sym_name, suffix - sym_name);
+		else
+			func->name = strdup(sym_name);
+
+		if (!func->name) {
+			err = -ENOMEM;
+			goto out_free;
+		}
+
+		func_sym.name = sym_name;
+		func_sym.addr = sym.st_value;
+
+		err = elf_function__push_sym(func, &func_sym);
+		if (err)
+			goto out_free;
+
+		functions->cnt++;
 	}
 
+	/* At this point functions->entries is an unordered array of elf_function
+	 * each having a name (without a suffix) and a single elf_function_sym (maybe with suffix)
+	 * Now let's sort this table by name.
+	 */
 	if (functions->cnt) {
-		qsort(functions->entries, functions->cnt, sizeof(*functions->entries), functions_cmp);
+		qsort(functions->entries, functions->cnt, sizeof(*functions->entries), elf_function__name_cmp);
 	} else {
 		err = 0;
 		goto out_free;
 	}
 
+	/* Finally dedup by name, transforming { name -> syms[1] } entries into { name -> syms[n] } */
+	i = 0;
+	j = 1;
+	for (j = 1; j < functions->cnt; j++) {
+		struct elf_function *a = &functions->entries[i];
+		struct elf_function *b = &functions->entries[j];
+
+		if (!strcmp(a->name, b->name)) {
+			elf_function__push_sym(a, &b->syms[0]);
+			elf_function__clear(b);
+		} else {
+			// at this point all syms for `a` have been collected
+			// check for ambiguous addresses before moving on
+			a->ambiguous_addr = elf_function__has_ambiguous_address(a);
+			i++;
+			if (i != j)
+				functions->entries[i] = functions->entries[j];
+		}
+	}
+
+	functions->cnt = i + 1;
+
 	/* Reallocate to the exact size */
 	tmp = realloc(functions->entries, functions->cnt * sizeof(struct elf_function));
 	if (tmp) {
@@ -2661,30 +2755,11 @@ int btf_encoder__encode_cu(struct btf_encoder *encoder, struct cu *cu, struct co
 			if (!name)
 				continue;
 
-			/* prefer exact function name match... */
-			func = btf_encoder__find_function(encoder, name, 0);
-			if (!func && funcs->suffix_cnt &&
-			    conf_load->btf_gen_optimized) {
-				/* falling back to name.isra.0 match if no exact
-				 * match is found; only bother if we found any
-				 * .suffix function names.  The function
-				 * will be saved and added once we ensure
-				 * it does not have optimized-out parameters
-				 * in any cu.
-				 */
-				func = btf_encoder__find_function(encoder, name,
-								  strlen(name));
-				if (func) {
-					if (encoder->verbose)
-						printf("matched function '%s' with '%s'%s\n",
-						       name, func->name,
-						       fn->proto.optimized_parms ?
-						       ", has optimized-out parameters" :
-						       fn->proto.unexpected_reg ? ", has unexpected register use by params" :
-						       "");
-					if (!func->alias)
-						func->alias = strdup(name);
-				}
+			func = btf_encoder__find_function(encoder, name);
+			if (!func) {
+				if (encoder->verbose)
+					printf("could not find function '%s' in the ELF functions table\n", name);
+				continue;
 			}
 		} else {
 			if (!fn->external)
-- 
2.49.0