Re: [RFC dwarves] btf_encoder: Remove duplicates from functions entries

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

On 7/22/25 3:45 AM, Alan Maguire wrote:
> On 22/07/2025 00:27, Ihor Solodrai wrote:
>> On 7/21/25 7:27 AM, Jiri Olsa wrote:
>>> On Mon, Jul 21, 2025 at 12:41:00PM +0100, Alan Maguire wrote:
>>>> On 17/07/2025 16:25, Jiri Olsa wrote:
>>
>> [...]
>>
>> The current implementation is just buggy in this regard.
>>
> 
> There are a few separable issues here I think.

You're right. I think in my mind all the issues we are discussing here
boil down to a single fundamental problem: one (function) name maps to
many things. But then there are a lot of details about what those
things are, how to find them, represent them etc.

> 
> First as you say, certain suffixes should not be eligible as matches at
> all - .cold is one, and .part is another (partial inlining). As such
> they should be filtered and removed as potential matches.
> 
> Second we need to fix the function sort/search logic.

Ok, here is my stab at it. See a patch draft below.

Using ELF symbol name as the key in elf_functions table is bug-prone,
given that we lookup a name loaded from DWARF (without suffixes).

So instead of having a table of ELF sym names directly and attempting
to search there, I tried a table of unsuffixed names (assuming that
any prefix before first '.' is a proper name, which is an assumption
already present in pahole).

To not lose the information from the ELF symbols, we simply collect it
at the time that table is built, basically constructing a mapping:

    function name -> [array of elf sym info]

Then we can inspect this array when a decision about inclusion into
BTF has to made. In the patch I check for .cold and multiple
addresses.

There is little difference in resulting BTF, but the bug I reported
gets fixed with the change, as well as ambigous address problem.

Please let me know if the approach makes sense.


From 1088367c1facb8b2e6700df17aa5b6e306578334 Mon Sep 17 00:00:00 2001
From: Ihor Solodrai <isolodrai@meta.com>
Date: Tue, 22 Jul 2025 15:16:36 -0700
Subject: [PATCH] btf_encoder: group all function ELF syms by function name

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, causing some functions to be
inappropriately excluded from (or included into) BTF.

Rework the implementation of the ELF functions table: use a proper
name of a function (without any suffix) as a key, and collect each
relevant ELF symbol information for later examination. This way we can
guarantee that btf_encoder__find_function() always returns correct
elf_function object (or NULL).

Collect an array of symbol name + address pairs from GElf_Sym for each
elf_function. Then, in saved_functions_combine() use this information
when deciding whether a function should be included in BTF.

In particular, exclude functions with ambiguous address, taking into
account that .cold symbols can be ignored.

Signed-off-by: Ihor Solodrai <ihor.solodrai@linux.dev>
---
 btf_encoder.c | 248 +++++++++++++++++++++++++++++++++-----------------
 1 file changed, 162 insertions(+), 86 deletions(-)

diff --git a/btf_encoder.c b/btf_encoder.c
index 0bc2334..fcc30aa 100644
--- a/btf_encoder.c
+++ b/btf_encoder.c
@@ -87,16 +87,22 @@ struct btf_encoder_func_state {
 	uint8_t optimized_parms:1;
 	uint8_t unexpected_reg:1;
 	uint8_t inconsistent_proto:1;
+	uint8_t ambiguous_addr:1;
 	int ret_type_id;
 	struct btf_encoder_func_parm *parms;
 	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;
+	uint8_t 	sym_cnt;
+	uint8_t		kfunc:1;
 	uint32_t	kfunc_flags;
 };
 
@@ -161,10 +167,18 @@ struct btf_kfunc_set_range {
 	uint64_t end;
 };
 
+static inline void elf_function__free_content(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__free_content(&funcs->entries[i]);
+	}
 	free(funcs->entries);
 	elf_symtab__delete(funcs->symtab);
 	list_del(&funcs->node);
@@ -981,8 +995,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 +1189,33 @@ static struct btf_encoder_func_state *btf_encoder__alloc_func_state(struct btf_e
 	return state;
 }
 
+static inline bool str_has_suffix(const char *str, const char *suffix) {
+	int prefixlen = strlen(str) - strlen(suffix);
+
+	if (prefixlen < 0)
+		return false;
+
+	return !strcmp(str + prefixlen, suffix);
+}
+
+static bool elf_function__has_ambiguous_address(struct elf_function *func) {
+	if (func->sym_cnt <= 1)
+		return false;
+
+	uint64_t addr = 0;
+	for (int i = 0; i < func->sym_cnt; i++) {
+		struct elf_function_sym *sym = &func->syms[i];
+		if (!str_has_suffix(sym->name, ".cold")) {
+			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);
@@ -1191,6 +1231,9 @@ static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct functi
 
 	state->encoder = encoder;
 	state->elf = func;
+
+	state->ambiguous_addr = elf_function__has_ambiguous_address(func);
+
 	state->nr_parms = ftype->nr_parms + (ftype->unspec_parms ? 1 : 0);
 	state->ret_type_id = ftype->tag.type == 0 ? 0 : encoder->type_id_off + ftype->tag.type;
 	if (state->nr_parms > 0) {
@@ -1294,7 +1337,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,48 +1381,39 @@ 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;
+	uint8_t optimized, unexpected, inconsistent, ambiguous_addr;
+
+	if (a->elf != b->elf)
+		return 1;
 
-	ret = strncmp(a->elf->name, b->elf->name,
-		      max(a->elf->prefixlen, b->elf->prefixlen));
-	if (ret != 0)
-		return ret;
 	optimized = a->optimized_parms | b->optimized_parms;
 	unexpected = a->unexpected_reg | b->unexpected_reg;
 	inconsistent = a->inconsistent_proto | b->inconsistent_proto;
-	if (!unexpected && !inconsistent && !funcs__match(a, b))
+	ambiguous_addr = a->ambiguous_addr | b->ambiguous_addr;
+	if (!unexpected && !inconsistent && !ambiguous_addr && !funcs__match(a, b))
 		inconsistent = 1;
 	a->optimized_parms = b->optimized_parms = optimized;
 	a->unexpected_reg = b->unexpected_reg = unexpected;
 	a->inconsistent_proto = b->inconsistent_proto = inconsistent;
+	a->ambiguous_addr = b->ambiguous_addr = ambiguous_addr;
 
 	return 0;
 }
@@ -1447,32 +1481,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 +1498,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 +2067,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 +2142,45 @@ 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 void print_func_table(struct elf_functions *functions) {
+	for (int i = 0; i < functions->cnt; i++) {
+		struct elf_function *func = &functions->entries[i];
+		printf("%s -> [", func->name);
+		for (int j = 0; j < func->sym_cnt; j++) {
+			printf("{ %s %lx } ", func->syms[j].name, func->syms[j].addr);
+		}
+		printf("]\n");
+	}
+}
+
 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 *func, *tmp;
 	Elf32_Word sym_sec_idx;
+	const char *sym_name;
 	uint32_t core_id;
+	struct elf_function_sym func_sym;
 	GElf_Sym sym;
-	int err = 0;
+	int err = 0, i, j;
 
 	/* We know that number of functions is less than number of symbols,
 	 * so we can overallocate temporarily.
@@ -2153,18 +2191,75 @@ 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;
+
+		func = &functions->entries[functions->cnt];
+
+		const char *suffix = strchr(sym_name, '.');
+		if (suffix) {
+			functions->suffix_cnt++;
+			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__free_content(b);
+		} else {
+			i++;
+			if (i != j)
+				functions->entries[i] = functions->entries[j];
+		}
+	}
+
+	functions->cnt = i + 1;
+
+	print_func_table(functions);
+
 	/* Reallocate to the exact size */
 	tmp = realloc(functions->entries, functions->cnt * sizeof(struct elf_function));
 	if (tmp) {
@@ -2661,30 +2756,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.50.1


> 
> Third we need to decide how to deal with cases where the function does
> not correspond to an mcount boundary. It'd be interesting to see if the
> filtering helps here, but part of the problem is also that we don't
> currently have a mechanism to help guide the match between function name
> and function site that is done when the fentry attach is carried out.
> Yonghong and I talked about it in [1].
> 
> Addresses seem like the natural means to help guide that, so a
> DATASEC-like set of addresses would help this matching. I had a WIP
> version of this but it wasn't working fully yet. I'll revive it and see
> if I can get it out as an RFC. Needs to take into account the work being
> done on inlines too [1].
> 
> In terms of the tracer's actual intent, multi-site functions are often
> "static inline" functions in a .h file that don't actually get inlined;
> the user intent would be often to trace all instances, but it seems to
> me we need to provide a means to support both this or to trace a
> specific instance. How the latter is best represented from the tracer
> side I'm not sure; raw addresses would be one way I suppose. Absent an
> explicit request from the tracer I'm not sure what heuristics make most
> sense; currently we just pick the first instance I suspect, and might
> need to continue to do so for backwards compatibility.
> 
> 
>> I am not aware of long term plans for addressing this, though it looks
>> like this was discussed before. I'd appreciate if you share any
>> relevant threads.
>>
> 
> Yonghong and I discussed this a bit in [1], and the inline thread in [2]
> has some more details.

Thank you for sharing. I guess I was wrong when I said I'm not aware
of the plans, because I am a little bit familiar with the work on BTF
representation of inlined funcs.

As far as I understand, partly because of the current limitations of
BTF, the best pahole/btf_encoder can do with optimized functions right
now is determine whether a function was not modified too much across
instances (optimized_parms, unexpected_reg etc.), and if yes then
exclude it from BTF.

Anything smarter requires extending BTF.

> 
> [1]
> https://lpc.events/event/18/contributions/1945/attachments/1508/3179/Kernel%20func%20tracing%20in%20the%20face%20of%20compiler%20optimization.pdf
> [2]
> https://lore.kernel.org/bpf/20250416-btf_inline-v1-0-e4bd2f8adae5@meta.com/
> 
>> Thanks.
>>
>> [...]