[PATCH v3 dwarves 0/5] btf_encoder: implement shared elf_functions table

[PATCH v3 dwarves 0/5] btf_encoder: implement shared elf_functions table

[Ihor Solodrai]

v3 of the patchset fixes a couple of bugs and addresses feedback.

Notable changes in comparison to v2:

* use proper interface from stdatomic.h for atomic operations in
  btf_encoder__find_function()
* simplify btf_encoder__add_saved_funcs(), because actually we don't
  need to accumulate gathered elf_function states there, we only need
  to determine if a function should be added to BTF
* fix segfault in a case when the number of btf encoders is less than
  the number of threads
* correctly clean up elf_functions->entries in
  elf_functions__collect() when no functions are present in the Elf
* correctly clean up elf_functions_list at the end of
  btf_encoder__encode()
* remove post_cus__load_module() hook as it was unused
* remove btf_encoders__merge() as it is redundant

v2: https://lore.kernel.org/dwarves/20241009233520.989453-1-ihor.solodrai@pm.me/
v1: https://lore.kernel.org/dwarves/20241004051347.41143-1-ihor.solodrai@pm.me/

Ihor Solodrai (5):
  dwarf_loader: introduce pre_load_module hook to conf_load
  btf_encoder: introduce elf_functions struct type
  btf_encoder: collect elf_functions in btf_encoder__pre_load_module
  btf_encoder: store a list of elf_function per function name
  btf_encoder: switch to shared elf_functions table

 btf_encoder.c  | 387 +++++++++++++++++++++++++++++++++----------------
 btf_encoder.h  |   3 +
 dwarf_loader.c |  14 +-
 dwarves.h      |  11 +-
 pahole.c       |  12 +-
 5 files changed, 292 insertions(+), 135 deletions(-)

-- 
2.43.0

[PATCH v3 dwarves 1/5] dwarf_loader: introduce pre_load_module hook to conf_load

[Ihor Solodrai]

Add a function pointer to conf_load, which is called immediately after
Elf is extracted from Dwfl_Module in cus__proces_dwflmod.

This is a preparation for making elf_functions table shared between
encoders. Shared table can be built as soon as the relevant Elf is
available.

Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
---
 dwarf_loader.c | 14 +++++++-------
 dwarves.h      | 11 +++++++++--
 2 files changed, 16 insertions(+), 9 deletions(-)

diff --git a/dwarf_loader.c b/dwarf_loader.c
index e54a16c..83a7f54 100644
--- a/dwarf_loader.c
+++ b/dwarf_loader.c
@@ -3723,13 +3723,6 @@ static int cus__load_module(struct cus *cus, struct conf_load *conf,
 	return DWARF_CB_OK;
 }
 
-struct process_dwflmod_parms {
-	struct cus	 *cus;
-	struct conf_load *conf;
-	const char	 *filename;
-	uint32_t	 nr_dwarf_sections_found;
-};
-
 static int cus__process_dwflmod(Dwfl_Module *dwflmod,
 				void **userdata __maybe_unused,
 				const char *name __maybe_unused,
@@ -3753,11 +3746,18 @@ static int cus__process_dwflmod(Dwfl_Module *dwflmod,
 	Dwarf *dw = dwfl_module_getdwarf(dwflmod, &dwbias);
 
 	int err = DWARF_CB_OK;
+	if (parms->conf->pre_load_module) {
+		err = parms->conf->pre_load_module(dwflmod, elf);
+		if (err)
+			return DWARF_CB_ABORT;
+	}
+
 	if (dw != NULL) {
 		++parms->nr_dwarf_sections_found;
 		err = cus__load_module(cus, parms->conf, dwflmod, dw, elf,
 				       parms->filename);
 	}
+
 	/*
 	 * XXX We will fall back to try finding other debugging
 	 * formats (CTF), so no point in telling this to the user
diff --git a/dwarves.h b/dwarves.h
index f147b2b..eb3be6e 100644
--- a/dwarves.h
+++ b/dwarves.h
@@ -36,6 +36,7 @@
 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))
 
 struct cu;
+struct cus;
 
 enum load_steal_kind {
 	LSK__KEEPIT,
@@ -58,6 +59,13 @@ typedef uint32_t type_id_t;
 struct btf;
 struct conf_fprintf;
 
+struct process_dwflmod_parms {
+	struct cus	 *cus;
+	struct conf_load *conf;
+	const char	 *filename;
+	uint32_t	 nr_dwarf_sections_found;
+};
+
 /** struct conf_load - load configuration
  * @thread_exit - called at the end of a thread, 1st user: BTF encoder dedup
  * @extra_dbg_info - keep original debugging format extra info
@@ -106,6 +114,7 @@ struct conf_load {
 	struct conf_fprintf	*conf_fprintf;
 	int			(*threads_prepare)(struct conf_load *conf, int nr_threads, void **thr_data);
 	int			(*threads_collect)(struct conf_load *conf, int nr_threads, void **thr_data, int error);
+	int			(*pre_load_module)(Dwfl_Module *mod, Elf *elf);
 };
 
 /** struct conf_fprintf - hints to the __fprintf routines
@@ -167,8 +176,6 @@ struct conf_fprintf {
 	uint8_t    skip_emitting_modifier:1;
 };
 
-struct cus;
-
 struct cus *cus__new(void);
 void cus__delete(struct cus *cus);
 
-- 
2.43.0

Re: [PATCH v3 dwarves 1/5] dwarf_loader: introduce pre_load_module hook to conf_load

[Alan Maguire]

On 16/10/2024 01:10, Ihor Solodrai wrote:
> Add a function pointer to conf_load, which is called immediately after
> Elf is extracted from Dwfl_Module in cus__proces_dwflmod.
> 
> This is a preparation for making elf_functions table shared between
> encoders. Shared table can be built as soon as the relevant Elf is
> available.
> 
> Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>

looks good to me

Reviewed-by: Alan Maguire <alan.maguire@oracle.com>

> ---
>  dwarf_loader.c | 14 +++++++-------
>  dwarves.h      | 11 +++++++++--
>  2 files changed, 16 insertions(+), 9 deletions(-)
> 
> diff --git a/dwarf_loader.c b/dwarf_loader.c
> index e54a16c..83a7f54 100644
> --- a/dwarf_loader.c
> +++ b/dwarf_loader.c
> @@ -3723,13 +3723,6 @@ static int cus__load_module(struct cus *cus, struct conf_load *conf,
>  	return DWARF_CB_OK;
>  }
>  
> -struct process_dwflmod_parms {
> -	struct cus	 *cus;
> -	struct conf_load *conf;
> -	const char	 *filename;
> -	uint32_t	 nr_dwarf_sections_found;
> -};
> -
>  static int cus__process_dwflmod(Dwfl_Module *dwflmod,
>  				void **userdata __maybe_unused,
>  				const char *name __maybe_unused,
> @@ -3753,11 +3746,18 @@ static int cus__process_dwflmod(Dwfl_Module *dwflmod,
>  	Dwarf *dw = dwfl_module_getdwarf(dwflmod, &dwbias);
>  
>  	int err = DWARF_CB_OK;
> +	if (parms->conf->pre_load_module) {
> +		err = parms->conf->pre_load_module(dwflmod, elf);
> +		if (err)
> +			return DWARF_CB_ABORT;
> +	}
> +
>  	if (dw != NULL) {
>  		++parms->nr_dwarf_sections_found;
>  		err = cus__load_module(cus, parms->conf, dwflmod, dw, elf,
>  				       parms->filename);
>  	}
> +
>  	/*
>  	 * XXX We will fall back to try finding other debugging
>  	 * formats (CTF), so no point in telling this to the user
> diff --git a/dwarves.h b/dwarves.h
> index f147b2b..eb3be6e 100644
> --- a/dwarves.h
> +++ b/dwarves.h
> @@ -36,6 +36,7 @@
>  #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]) + __must_be_array(arr))
>  
>  struct cu;
> +struct cus;
>  
>  enum load_steal_kind {
>  	LSK__KEEPIT,
> @@ -58,6 +59,13 @@ typedef uint32_t type_id_t;
>  struct btf;
>  struct conf_fprintf;
>  
> +struct process_dwflmod_parms {
> +	struct cus	 *cus;
> +	struct conf_load *conf;
> +	const char	 *filename;
> +	uint32_t	 nr_dwarf_sections_found;
> +};
> +
>  /** struct conf_load - load configuration
>   * @thread_exit - called at the end of a thread, 1st user: BTF encoder dedup
>   * @extra_dbg_info - keep original debugging format extra info
> @@ -106,6 +114,7 @@ struct conf_load {
>  	struct conf_fprintf	*conf_fprintf;
>  	int			(*threads_prepare)(struct conf_load *conf, int nr_threads, void **thr_data);
>  	int			(*threads_collect)(struct conf_load *conf, int nr_threads, void **thr_data, int error);
> +	int			(*pre_load_module)(Dwfl_Module *mod, Elf *elf);
>  };
>  
>  /** struct conf_fprintf - hints to the __fprintf routines
> @@ -167,8 +176,6 @@ struct conf_fprintf {
>  	uint8_t    skip_emitting_modifier:1;
>  };
>  
> -struct cus;
> -
>  struct cus *cus__new(void);
>  void cus__delete(struct cus *cus);
>  

[PATCH v3 dwarves 2/5] btf_encoder: introduce elf_functions struct type

[Ihor Solodrai]

Extract elf_functions struct type from btf_encoder.

Replace methods operating functions table in btf_encoder by methods
operating on elf_functions:
- btf_encoder__collect_function -> elf_functions__collect_function
- btf_encoder__collect_symbols -> elf_functions__collect

Now these functions do not depend on btf_encoder being passed to them
as a parameter.

Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
---
 btf_encoder.c | 122 +++++++++++++++++++++++++++-----------------------
 1 file changed, 66 insertions(+), 56 deletions(-)

diff --git a/btf_encoder.c b/btf_encoder.c
index 5954238..9c840fa 100644
--- a/btf_encoder.c
+++ b/btf_encoder.c
@@ -102,6 +102,13 @@ struct elf_secinfo {
 	struct gobuffer secinfo;
 };
 
+struct elf_functions {
+	struct elf_symtab *symtab;
+	struct elf_function *entries;
+	int cnt;
+	int suffix_cnt; /* number of .isra, .part etc */
+};
+
 /*
  * cu: cu being processed.
  */
@@ -126,12 +133,7 @@ struct btf_encoder {
 	struct elf_secinfo *secinfo;
 	size_t             seccnt;
 	int                encode_vars;
-	struct {
-		struct elf_function *entries;
-		int		    allocated;
-		int		    cnt;
-		int		    suffix_cnt; /* number of .isra, .part etc */
-	} functions;
+	struct elf_functions functions;
 };
 
 struct btf_func {
@@ -1299,55 +1301,28 @@ static int functions_cmp(const void *_a, const void *_b)
 	return strcmp(a->name, b->name);
 }
 
-#ifndef max
-#define max(x, y) ((x) < (y) ? (y) : (x))
-#endif
-
-static void *reallocarray_grow(void *ptr, int *nmemb, size_t size)
-{
-	int new_nmemb = max(1000, *nmemb * 3 / 2);
-	void *new = realloc(ptr, new_nmemb * size);
-
-	if (new)
-		*nmemb = new_nmemb;
-	return new;
-}
-
-static int btf_encoder__collect_function(struct btf_encoder *encoder, GElf_Sym *sym)
+static int elf_functions__collect_function(struct elf_functions *functions, GElf_Sym *sym)
 {
-	struct elf_function *new;
+	struct elf_function *func;
 	const char *name;
 
 	if (elf_sym__type(sym) != STT_FUNC)
 		return 0;
-	name = elf_sym__name(sym, encoder->symtab);
+
+	name = elf_sym__name(sym, functions->symtab);
 	if (!name)
 		return 0;
 
-	if (encoder->functions.cnt == encoder->functions.allocated) {
-		new = reallocarray_grow(encoder->functions.entries,
-					&encoder->functions.allocated,
-					sizeof(*encoder->functions.entries));
-		if (!new) {
-			/*
-			 * The cleanup - delete_functions is called
-			 * in btf_encoder__encode_cu error path.
-			 */
-			return -1;
-		}
-		encoder->functions.entries = new;
-	}
-
-	memset(&encoder->functions.entries[encoder->functions.cnt], 0,
-	       sizeof(*new));
-	encoder->functions.entries[encoder->functions.cnt].name = name;
+	func = &functions->entries[functions->cnt];
+	func->name = name;
 	if (strchr(name, '.')) {
 		const char *suffix = strchr(name, '.');
-
-		encoder->functions.suffix_cnt++;
-		encoder->functions.entries[encoder->functions.cnt].prefixlen = suffix - name;
+		functions->suffix_cnt++;
+		func->prefixlen = suffix - name;
 	}
-	encoder->functions.cnt++;
+
+	functions->cnt++;
+
 	return 0;
 }
 
@@ -2099,26 +2074,60 @@ int btf_encoder__encode(struct btf_encoder *encoder)
 	return err;
 }
 
-
-static int btf_encoder__collect_symbols(struct btf_encoder *encoder)
+static int elf_functions__collect(struct elf_functions *functions)
 {
-	uint32_t sym_sec_idx;
+	uint32_t nr_symbols = elf_symtab__nr_symbols(functions->symtab);
+	struct elf_function *tmp;
+	Elf32_Word sym_sec_idx;
 	uint32_t core_id;
 	GElf_Sym sym;
+	int err;
 
-	elf_symtab__for_each_symbol_index(encoder->symtab, core_id, sym, sym_sec_idx) {
-		if (btf_encoder__collect_function(encoder, &sym))
-			return -1;
+	/* We know that number of functions is less than number of symbols,
+	 * so we can overallocate temporarily.
+	 */
+	functions->entries = calloc(nr_symbols, sizeof(struct elf_function));
+	if (!functions->entries) {
+		fprintf(stderr, "could not allocate memory for elf_functions table\n");
+		err = -ENOMEM;
+		goto out_free;
+	}
+
+	functions->cnt = 0;
+	elf_symtab__for_each_symbol_index(functions->symtab, core_id, sym, sym_sec_idx) {
+		if (elf_functions__collect_function(functions, &sym)) {
+			err = -1;
+			goto out_free;
+		}
 	}
 
-	if (encoder->functions.cnt) {
-		qsort(encoder->functions.entries, encoder->functions.cnt, sizeof(encoder->functions.entries[0]),
+	if (functions->cnt) {
+		qsort(functions->entries,
+		      functions->cnt,
+		      sizeof(functions->entries[0]),
 		      functions_cmp);
-		if (encoder->verbose)
-			printf("Found %d functions!\n", encoder->functions.cnt);
+	} else {
+		err = 0;
+		goto out_free;
+	}
+
+	/* Reallocate to the exact size */
+	tmp = realloc(functions->entries, functions->cnt * sizeof(struct elf_function));
+	if (tmp) {
+		functions->entries = tmp;
+	} else {
+		fprintf(stderr, "could not reallocate memory for elf_functions table\n");
+		err = -ENOMEM;
+		goto out_free;
 	}
 
 	return 0;
+
+out_free:
+	free(functions->entries);
+	functions->entries = NULL;
+	functions->cnt = 0;
+	return err;
 }
 
 static bool ftype__has_arg_names(const struct ftype *ftype)
@@ -2377,6 +2386,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
 				printf("%s: '%s' doesn't have symtab.\n", __func__, cu->filename);
 			goto out;
 		}
+		encoder->functions.symtab = encoder->symtab;
 
 		/* index the ELF sections for later lookup */
 
@@ -2415,7 +2425,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
 		if (!found_percpu && encoder->verbose)
 			printf("%s: '%s' doesn't have '%s' section\n", __func__, cu->filename, PERCPU_SECTION);
 
-		if (btf_encoder__collect_symbols(encoder))
+		if (elf_functions__collect(&encoder->functions))
 			goto out_delete;
 
 		if (encoder->verbose)
@@ -2456,7 +2466,7 @@ void btf_encoder__delete(struct btf_encoder *encoder)
 
 	for (i = 0; i < encoder->functions.cnt; i++)
 		btf_encoder__delete_func(&encoder->functions.entries[i]);
-	encoder->functions.allocated = encoder->functions.cnt = 0;
+	encoder->functions.cnt = 0;
 	free(encoder->functions.entries);
 	encoder->functions.entries = NULL;
 
-- 
2.43.0

Re: [PATCH v3 dwarves 2/5] btf_encoder: introduce elf_functions struct type

[Alan Maguire]

On 16/10/2024 01:10, Ihor Solodrai wrote:
> Extract elf_functions struct type from btf_encoder.
> 
> Replace methods operating functions table in btf_encoder by methods
> operating on elf_functions:
> - btf_encoder__collect_function -> elf_functions__collect_function
> - btf_encoder__collect_symbols -> elf_functions__collect
> 
> Now these functions do not depend on btf_encoder being passed to them
> as a parameter.
> 
> Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>

a few small things, but

Reviewed-by: Alan Maguire <alan.maguire@oracle.com>

> ---
>  btf_encoder.c | 122 +++++++++++++++++++++++++++-----------------------
>  1 file changed, 66 insertions(+), 56 deletions(-)
> 
> diff --git a/btf_encoder.c b/btf_encoder.c
> index 5954238..9c840fa 100644
> --- a/btf_encoder.c
> +++ b/btf_encoder.c
> @@ -102,6 +102,13 @@ struct elf_secinfo {
>  	struct gobuffer secinfo;
>  };
>  
> +struct elf_functions {
> +	struct elf_symtab *symtab;
> +	struct elf_function *entries;
> +	int cnt;
> +	int suffix_cnt; /* number of .isra, .part etc */
> +};
> +
>  /*
>   * cu: cu being processed.
>   */
> @@ -126,12 +133,7 @@ struct btf_encoder {
>  	struct elf_secinfo *secinfo;
>  	size_t             seccnt;
>  	int                encode_vars;
> -	struct {
> -		struct elf_function *entries;
> -		int		    allocated;
> -		int		    cnt;
> -		int		    suffix_cnt; /* number of .isra, .part etc */
> -	} functions;
> +	struct elf_functions functions;
>  };
>  
>  struct btf_func {
> @@ -1299,55 +1301,28 @@ static int functions_cmp(const void *_a, const void *_b)
>  	return strcmp(a->name, b->name);
>  }
>  
> -#ifndef max
> -#define max(x, y) ((x) < (y) ? (y) : (x))
> -#endif
> -
> -static void *reallocarray_grow(void *ptr, int *nmemb, size_t size)
> -{
> -	int new_nmemb = max(1000, *nmemb * 3 / 2);
> -	void *new = realloc(ptr, new_nmemb * size);
> -
> -	if (new)
> -		*nmemb = new_nmemb;
> -	return new;
> -}
> -
> -static int btf_encoder__collect_function(struct btf_encoder *encoder, GElf_Sym *sym)
> +static int elf_functions__collect_function(struct elf_functions *functions, GElf_Sym *sym)
>  {
> -	struct elf_function *new;
> +	struct elf_function *func;
>  	const char *name;
>  
>  	if (elf_sym__type(sym) != STT_FUNC)
>  		return 0;
> -	name = elf_sym__name(sym, encoder->symtab);
> +
> +	name = elf_sym__name(sym, functions->symtab);
>  	if (!name)
>  		return 0;
>  
> -	if (encoder->functions.cnt == encoder->functions.allocated) {
> -		new = reallocarray_grow(encoder->functions.entries,
> -					&encoder->functions.allocated,
> -					sizeof(*encoder->functions.entries));
> -		if (!new) {
> -			/*
> -			 * The cleanup - delete_functions is called
> -			 * in btf_encoder__encode_cu error path.
> -			 */
> -			return -1;
> -		}
> -		encoder->functions.entries = new;
> -	}
> -
> -	memset(&encoder->functions.entries[encoder->functions.cnt], 0,
> -	       sizeof(*new));
> -	encoder->functions.entries[encoder->functions.cnt].name = name;
> +	func = &functions->entries[functions->cnt];
> +	func->name = name;
>  	if (strchr(name, '.')) {
>  		const char *suffix = strchr(name, '.');
> -
> -		encoder->functions.suffix_cnt++;
> -		encoder->functions.entries[encoder->functions.cnt].prefixlen = suffix - name;
> +		functions->suffix_cnt++;
> +		func->prefixlen = suffix - name;
>  	}
> -	encoder->functions.cnt++;
> +
> +	functions->cnt++;
> +
>  	return 0;
>  }
>  
> @@ -2099,26 +2074,60 @@ int btf_encoder__encode(struct btf_encoder *encoder)
>  	return err;
>  }
>  
> -
> -static int btf_encoder__collect_symbols(struct btf_encoder *encoder)
> +static int elf_functions__collect(struct elf_functions *functions)
>  {
> -	uint32_t sym_sec_idx;
> +	uint32_t nr_symbols = elf_symtab__nr_symbols(functions->symtab);
> +	struct elf_function *tmp;
> +	Elf32_Word sym_sec_idx;
>  	uint32_t core_id;
>  	GElf_Sym sym;
> +	int err;
>  
> -	elf_symtab__for_each_symbol_index(encoder->symtab, core_id, sym, sym_sec_idx) {
> -		if (btf_encoder__collect_function(encoder, &sym))
> -			return -1;
> +	/* We know that number of functions is less than number of symbols,
> +	 * so we can overallocate temporarily.
> +	 */
> +	functions->entries = calloc(nr_symbols, sizeof(struct elf_function));

So in testing  we hit a case (a module) with no functions, I presume a
case with zero symbols is extremely unlikely, but maybe just in case,

if (nr_symbols == 0)
	goto out_free;

(we should probably just initialize int err = 0; above)

> +	if (!functions->entries) {
> +		fprintf(stderr, "could not allocate memory for elf_functions table\n");
> +		err = -ENOMEM;
> +		goto out_free;
> +	}
> +
> +	functions->cnt = 0;
> +	elf_symtab__for_each_symbol_index(functions->symtab, core_id, sym, sym_sec_idx) {
> +		if (elf_functions__collect_function(functions, &sym)) {
> +			err = -1;
> +			goto out_free;
> +		}
>  	}
>  
> -	if (encoder->functions.cnt) {
> -		qsort(encoder->functions.entries, encoder->functions.cnt, sizeof(encoder->functions.entries[0]),
> +	if (functions->cnt) {
> +		qsort(functions->entries,
> +		      functions->cnt,
> +		      sizeof(functions->entries[0]),
>  		      functions_cmp);
> -		if (encoder->verbose)
> -			printf("Found %d functions!\n", encoder->functions.cnt);
> +	} else {
> +		err = 0;

nit: as noted above start with err = 0 and we can just goto out_free.

> +		goto out_free;
> +	}
> +
> +	/* Reallocate to the exact size */
> +	tmp = realloc(functions->entries, functions->cnt * sizeof(struct elf_function));
> +	if (tmp) {
> +		functions->entries = tmp;
> +	} else {
> +		fprintf(stderr, "could not reallocate memory for elf_functions table\n");
> +		err = -ENOMEM;
> +		goto out_free;
>  	}
>  
>  	return 0;
> +
> +out_free:
> +	free(functions->entries);
> +	functions->entries = NULL;
> +	functions->cnt = 0;
> +	return err;
>  }
>  
>  static bool ftype__has_arg_names(const struct ftype *ftype)
> @@ -2377,6 +2386,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
>  				printf("%s: '%s' doesn't have symtab.\n", __func__, cu->filename);
>  			goto out;
>  		}
> +		encoder->functions.symtab = encoder->symtab;
>  

nit: unless there's a reason otherwise, this assignment seems to more
naturally belong in elf_functions__collect().

>  		/* index the ELF sections for later lookup */
>  
> @@ -2415,7 +2425,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
>  		if (!found_percpu && encoder->verbose)
>  			printf("%s: '%s' doesn't have '%s' section\n", __func__, cu->filename, PERCPU_SECTION);
>  
> -		if (btf_encoder__collect_symbols(encoder))
> +		if (elf_functions__collect(&encoder->functions))
>  			goto out_delete;
>  
>  		if (encoder->verbose)
> @@ -2456,7 +2466,7 @@ void btf_encoder__delete(struct btf_encoder *encoder)
>  
>  	for (i = 0; i < encoder->functions.cnt; i++)
>  		btf_encoder__delete_func(&encoder->functions.entries[i]);
> -	encoder->functions.allocated = encoder->functions.cnt = 0;
> +	encoder->functions.cnt = 0;
>  	free(encoder->functions.entries);
>  	encoder->functions.entries = NULL;
>  

[PATCH v3 dwarves 3/5] btf_encoder: collect elf_functions in btf_encoder__pre_load_module

[Ihor Solodrai]

Introduce a global elf_functions_list variable in btf_encoder.c that
contains an elf_functions per ELF.

An elf_functions structure is allocated and filled out by
btf_encoder__pre_load_module() hook, and the list is cleared after
btf_encoder__encode() is done.

At this point btf_encoders don't use shared elf_functions yet (each
maintains their own copy as before), but it is built before encoders
are initialized.

Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
---
 btf_encoder.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++
 btf_encoder.h |  2 ++
 pahole.c      |  3 +++
 3 files changed, 71 insertions(+)

diff --git a/btf_encoder.c b/btf_encoder.c
index 9c840fa..8e8fd05 100644
--- a/btf_encoder.c
+++ b/btf_encoder.c
@@ -103,6 +103,8 @@ struct elf_secinfo {
 };
 
 struct elf_functions {
+	struct list_head node; /* for elf_functions_list */
+	Elf *elf; /* source ELF */
 	struct elf_symtab *symtab;
 	struct elf_function *entries;
 	int cnt;
@@ -147,6 +149,67 @@ struct btf_kfunc_set_range {
 	uint64_t end;
 };
 
+
+/* In principle, multiple ELFs can be processed in one pahole run,
+ * so we have to store elf_functions table per ELF.
+ * An element is added to the list on btf_encoder__pre_load_module,
+ * and removed after btf_encoder__encode is done.
+ */
+static LIST_HEAD(elf_functions_list);
+
+static inline void elf_functions__delete(struct elf_functions *funcs)
+{
+	free(funcs->entries);
+	elf_symtab__delete(funcs->symtab);
+	list_del(&funcs->node);
+	free(funcs);
+}
+
+static inline void elf_functions__delete_all(void)
+{
+	struct list_head *pos, *tmp;
+
+	list_for_each_safe(pos, tmp, &elf_functions_list) {
+		struct elf_functions *funcs = list_entry(pos, struct elf_functions, node);
+
+		elf_functions__delete(funcs);
+	}
+}
+
+static int elf_functions__collect(struct elf_functions *functions);
+
+int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf)
+{
+	struct elf_functions *funcs;
+	int err;
+
+	funcs = calloc(1, sizeof(*funcs));
+	if (!funcs) {
+		err = -ENOMEM;
+		goto out_delete;
+	}
+
+	funcs->symtab = elf_symtab__new(NULL, elf);
+	if (!funcs->symtab) {
+		err = -1;
+		goto out_delete;
+	}
+
+	funcs->elf = elf;
+	err = elf_functions__collect(funcs);
+	if (err)
+		goto out_delete;
+
+	list_add_tail(&funcs->node, &elf_functions_list);
+
+	return 0;
+
+out_delete:
+	elf_functions__delete(funcs);
+	return err;
+}
+
+
 static LIST_HEAD(encoders);
 static pthread_mutex_t encoders__lock = PTHREAD_MUTEX_INITIALIZER;
 
@@ -2071,6 +2134,8 @@ int btf_encoder__encode(struct btf_encoder *encoder)
 #endif
 		err = btf_encoder__write_elf(encoder, encoder->btf, BTF_ELF_SEC);
 	}
+
+	elf_functions__delete_all();
 	return err;
 }
 
@@ -2387,6 +2452,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
 			goto out;
 		}
 		encoder->functions.symtab = encoder->symtab;
+		encoder->functions.elf = cu->elf;
 
 		/* index the ELF sections for later lookup */
 
diff --git a/btf_encoder.h b/btf_encoder.h
index 824963b..7debd67 100644
--- a/btf_encoder.h
+++ b/btf_encoder.h
@@ -34,4 +34,6 @@ struct btf *btf_encoder__btf(struct btf_encoder *encoder);
 
 int btf_encoder__add_encoder(struct btf_encoder *encoder, struct btf_encoder *other);
 
+int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf);
+
 #endif /* _BTF_ENCODER_H_ */
diff --git a/pahole.c b/pahole.c
index b9e97ef..891af3a 100644
--- a/pahole.c
+++ b/pahole.c
@@ -3814,6 +3814,9 @@ int main(int argc, char *argv[])
 		conf_load.threads_collect = pahole_threads_collect;
 	}
 
+	if (btf_encode)
+		conf_load.pre_load_module = btf_encoder__pre_load_module;
+
 	// Make 'pahole --header type < file' a shorter form of 'pahole -C type --count 1 < file'
 	if (conf.header_type && !class_name && prettify_input) {
 		conf.count = 1;
-- 
2.43.0

Re: [PATCH v3 dwarves 3/5] btf_encoder: collect elf_functions in btf_encoder__pre_load_module

[Alan Maguire]

On 16/10/2024 01:10, Ihor Solodrai wrote:
> Introduce a global elf_functions_list variable in btf_encoder.c that
> contains an elf_functions per ELF.
>

Arnaldo can help provide context here, but at least notionally I think
the idea of maintaining libdwarves as a library has value. In that
context, avoiding global lists where possible is a good thing I think,
since if it was used as a library, multiple invokations could confuse
the elf_functions list. To that end, can we make the elf_functions_list
a field in the conf_load perhaps? It already contains base_btf so there
is a precedent for storing data relevant to all encoders there, and
btf_encoder__new() has conf_load as a parameter, so the elf functions
list can still always be retrieved on encoder creation. In addition the
parameter to cus__process_dwflmod() has the parms structure which
contains the conf_load; you'd just need to pass that through to your
pre_load_module() callback I think.

It shouldn't be a massive change but I think it would be worthwhile.

Thanks!

> An elf_functions structure is allocated and filled out by
> btf_encoder__pre_load_module() hook, and the list is cleared after
> btf_encoder__encode() is done.
> 
> At this point btf_encoders don't use shared elf_functions yet (each
> maintains their own copy as before), but it is built before encoders
> are initialized.
> 
> Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
> ---
>  btf_encoder.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  btf_encoder.h |  2 ++
>  pahole.c      |  3 +++
>  3 files changed, 71 insertions(+)
> 
> diff --git a/btf_encoder.c b/btf_encoder.c
> index 9c840fa..8e8fd05 100644
> --- a/btf_encoder.c
> +++ b/btf_encoder.c
> @@ -103,6 +103,8 @@ struct elf_secinfo {
>  };
>  
>  struct elf_functions {
> +	struct list_head node; /* for elf_functions_list */
> +	Elf *elf; /* source ELF */
>  	struct elf_symtab *symtab;
>  	struct elf_function *entries;
>  	int cnt;
> @@ -147,6 +149,67 @@ struct btf_kfunc_set_range {
>  	uint64_t end;
>  };
>  
> +
> +/* In principle, multiple ELFs can be processed in one pahole run,
> + * so we have to store elf_functions table per ELF.
> + * An element is added to the list on btf_encoder__pre_load_module,
> + * and removed after btf_encoder__encode is done.
> + */
> +static LIST_HEAD(elf_functions_list);
> +
> +static inline void elf_functions__delete(struct elf_functions *funcs)
> +{
> +	free(funcs->entries);
> +	elf_symtab__delete(funcs->symtab);
> +	list_del(&funcs->node);
> +	free(funcs);
> +}
> +
> +static inline void elf_functions__delete_all(void)
> +{
> +	struct list_head *pos, *tmp;
> +
> +	list_for_each_safe(pos, tmp, &elf_functions_list) {
> +		struct elf_functions *funcs = list_entry(pos, struct elf_functions, node);
> +
> +		elf_functions__delete(funcs);
> +	}
> +}
> +
> +static int elf_functions__collect(struct elf_functions *functions);
> +
> +int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf)
> +{
> +	struct elf_functions *funcs;
> +	int err;
> +
> +	funcs = calloc(1, sizeof(*funcs));
> +	if (!funcs) {
> +		err = -ENOMEM;
> +		goto out_delete;
> +	}
> +
> +	funcs->symtab = elf_symtab__new(NULL, elf);
> +	if (!funcs->symtab) {
> +		err = -1;
> +		goto out_delete;
> +	}
> +
> +	funcs->elf = elf;
> +	err = elf_functions__collect(funcs);
> +	if (err)
> +		goto out_delete;
> +
> +	list_add_tail(&funcs->node, &elf_functions_list);
> +
> +	return 0;
> +
> +out_delete:
> +	elf_functions__delete(funcs);
> +	return err;
> +}
> +
> +
>  static LIST_HEAD(encoders);
>  static pthread_mutex_t encoders__lock = PTHREAD_MUTEX_INITIALIZER;
>  
> @@ -2071,6 +2134,8 @@ int btf_encoder__encode(struct btf_encoder *encoder)
>  #endif
>  		err = btf_encoder__write_elf(encoder, encoder->btf, BTF_ELF_SEC);
>  	}
> +
> +	elf_functions__delete_all();
>  	return err;
>  }
>  
> @@ -2387,6 +2452,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
>  			goto out;
>  		}
>  		encoder->functions.symtab = encoder->symtab;
> +		encoder->functions.elf = cu->elf;
>  
>  		/* index the ELF sections for later lookup */
>  
> diff --git a/btf_encoder.h b/btf_encoder.h
> index 824963b..7debd67 100644
> --- a/btf_encoder.h
> +++ b/btf_encoder.h
> @@ -34,4 +34,6 @@ struct btf *btf_encoder__btf(struct btf_encoder *encoder);
>  
>  int btf_encoder__add_encoder(struct btf_encoder *encoder, struct btf_encoder *other);
>  
> +int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf);
> +
>  #endif /* _BTF_ENCODER_H_ */
> diff --git a/pahole.c b/pahole.c
> index b9e97ef..891af3a 100644
> --- a/pahole.c
> +++ b/pahole.c
> @@ -3814,6 +3814,9 @@ int main(int argc, char *argv[])
>  		conf_load.threads_collect = pahole_threads_collect;
>  	}
>  
> +	if (btf_encode)
> +		conf_load.pre_load_module = btf_encoder__pre_load_module;
> +
>  	// Make 'pahole --header type < file' a shorter form of 'pahole -C type --count 1 < file'
>  	if (conf.header_type && !class_name && prettify_input) {
>  		conf.count = 1;

Re: [PATCH v3 dwarves 3/5] btf_encoder: collect elf_functions in btf_encoder__pre_load_module

[Arnaldo Carvalho de Melo]

On Thu, Oct 17, 2024 at 11:56:04AM +0100, Alan Maguire wrote:
> On 16/10/2024 01:10, Ihor Solodrai wrote:
> > Introduce a global elf_functions_list variable in btf_encoder.c that
> > contains an elf_functions per ELF.
> >
> 
> Arnaldo can help provide context here, but at least notionally I think
> the idea of maintaining libdwarves as a library has value. In that

Yeah, but in all these years I'm not aware of any user, I even need to
do some testing on building pahole statically with libdwarves to see if
we get performance improvements...

> context, avoiding global lists where possible is a good thing I think,

Even without a library :-)

> since if it was used as a library, multiple invokations could confuse
> the elf_functions list. To that end, can we make the elf_functions_list
> a field in the conf_load perhaps? It already contains base_btf so there

conf_load looks with the structs we have now, so I would try to start
there.

- Arnaldo

> is a precedent for storing data relevant to all encoders there, and
> btf_encoder__new() has conf_load as a parameter, so the elf functions
> list can still always be retrieved on encoder creation. In addition the
> parameter to cus__process_dwflmod() has the parms structure which
> contains the conf_load; you'd just need to pass that through to your
> pre_load_module() callback I think.
> 
> It shouldn't be a massive change but I think it would be worthwhile.
> 
> Thanks!
> 
> > An elf_functions structure is allocated and filled out by
> > btf_encoder__pre_load_module() hook, and the list is cleared after
> > btf_encoder__encode() is done.
> > 
> > At this point btf_encoders don't use shared elf_functions yet (each
> > maintains their own copy as before), but it is built before encoders
> > are initialized.
> > 
> > Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
> > ---
> >  btf_encoder.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++
> >  btf_encoder.h |  2 ++
> >  pahole.c      |  3 +++
> >  3 files changed, 71 insertions(+)
> > 
> > diff --git a/btf_encoder.c b/btf_encoder.c
> > index 9c840fa..8e8fd05 100644
> > --- a/btf_encoder.c
> > +++ b/btf_encoder.c
> > @@ -103,6 +103,8 @@ struct elf_secinfo {
> >  };
> >  
> >  struct elf_functions {
> > +	struct list_head node; /* for elf_functions_list */
> > +	Elf *elf; /* source ELF */
> >  	struct elf_symtab *symtab;
> >  	struct elf_function *entries;
> >  	int cnt;
> > @@ -147,6 +149,67 @@ struct btf_kfunc_set_range {
> >  	uint64_t end;
> >  };
> >  
> > +
> > +/* In principle, multiple ELFs can be processed in one pahole run,
> > + * so we have to store elf_functions table per ELF.
> > + * An element is added to the list on btf_encoder__pre_load_module,
> > + * and removed after btf_encoder__encode is done.
> > + */
> > +static LIST_HEAD(elf_functions_list);
> > +
> > +static inline void elf_functions__delete(struct elf_functions *funcs)
> > +{
> > +	free(funcs->entries);
> > +	elf_symtab__delete(funcs->symtab);
> > +	list_del(&funcs->node);
> > +	free(funcs);
> > +}
> > +
> > +static inline void elf_functions__delete_all(void)
> > +{
> > +	struct list_head *pos, *tmp;
> > +
> > +	list_for_each_safe(pos, tmp, &elf_functions_list) {
> > +		struct elf_functions *funcs = list_entry(pos, struct elf_functions, node);
> > +
> > +		elf_functions__delete(funcs);
> > +	}
> > +}
> > +
> > +static int elf_functions__collect(struct elf_functions *functions);
> > +
> > +int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf)
> > +{
> > +	struct elf_functions *funcs;
> > +	int err;
> > +
> > +	funcs = calloc(1, sizeof(*funcs));
> > +	if (!funcs) {
> > +		err = -ENOMEM;
> > +		goto out_delete;
> > +	}
> > +
> > +	funcs->symtab = elf_symtab__new(NULL, elf);
> > +	if (!funcs->symtab) {
> > +		err = -1;
> > +		goto out_delete;
> > +	}
> > +
> > +	funcs->elf = elf;
> > +	err = elf_functions__collect(funcs);
> > +	if (err)
> > +		goto out_delete;
> > +
> > +	list_add_tail(&funcs->node, &elf_functions_list);
> > +
> > +	return 0;
> > +
> > +out_delete:
> > +	elf_functions__delete(funcs);
> > +	return err;
> > +}
> > +
> > +
> >  static LIST_HEAD(encoders);
> >  static pthread_mutex_t encoders__lock = PTHREAD_MUTEX_INITIALIZER;
> >  
> > @@ -2071,6 +2134,8 @@ int btf_encoder__encode(struct btf_encoder *encoder)
> >  #endif
> >  		err = btf_encoder__write_elf(encoder, encoder->btf, BTF_ELF_SEC);
> >  	}
> > +
> > +	elf_functions__delete_all();
> >  	return err;
> >  }
> >  
> > @@ -2387,6 +2452,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
> >  			goto out;
> >  		}
> >  		encoder->functions.symtab = encoder->symtab;
> > +		encoder->functions.elf = cu->elf;
> >  
> >  		/* index the ELF sections for later lookup */
> >  
> > diff --git a/btf_encoder.h b/btf_encoder.h
> > index 824963b..7debd67 100644
> > --- a/btf_encoder.h
> > +++ b/btf_encoder.h
> > @@ -34,4 +34,6 @@ struct btf *btf_encoder__btf(struct btf_encoder *encoder);
> >  
> >  int btf_encoder__add_encoder(struct btf_encoder *encoder, struct btf_encoder *other);
> >  
> > +int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf);
> > +
> >  #endif /* _BTF_ENCODER_H_ */
> > diff --git a/pahole.c b/pahole.c
> > index b9e97ef..891af3a 100644
> > --- a/pahole.c
> > +++ b/pahole.c
> > @@ -3814,6 +3814,9 @@ int main(int argc, char *argv[])
> >  		conf_load.threads_collect = pahole_threads_collect;
> >  	}
> >  
> > +	if (btf_encode)
> > +		conf_load.pre_load_module = btf_encoder__pre_load_module;
> > +
> >  	// Make 'pahole --header type < file' a shorter form of 'pahole -C type --count 1 < file'
> >  	if (conf.header_type && !class_name && prettify_input) {
> >  		conf.count = 1;

Re: [PATCH v3 dwarves 3/5] btf_encoder: collect elf_functions in btf_encoder__pre_load_module

[Ihor Solodrai]

On Thursday, October 17th, 2024 at 1:13 PM, Arnaldo Carvalho de Melo <acme@kernel.org> wrote:

> On Thu, Oct 17, 2024 at 11:56:04AM +0100, Alan Maguire wrote:
> 
> > On 16/10/2024 01:10, Ihor Solodrai wrote:
> > 
> > > Introduce a global elf_functions_list variable in btf_encoder.c that
> > > contains an elf_functions per ELF.
> > 
> > Arnaldo can help provide context here, but at least notionally I think
> > the idea of maintaining libdwarves as a library has value. In that
> 
> 
> Yeah, but in all these years I'm not aware of any user, I even need to
> do some testing on building pahole statically with libdwarves to see if
> we get performance improvements...
> 
> > context, avoiding global lists where possible is a good thing I think,
> 
> 
> Even without a library :-)
> 
> > since if it was used as a library, multiple invokations could confuse
> > the elf_functions list. To that end, can we make the elf_functions_list
> > a field in the conf_load perhaps? It already contains base_btf so there
> 
> 
> conf_load looks with the structs we have now, so I would try to start
> there.
> 
> - Arnaldo
> 
> > is a precedent for storing data relevant to all encoders there, and
> > btf_encoder__new() has conf_load as a parameter, so the elf functions
> > list can still always be retrieved on encoder creation. In addition the
> > parameter to cus__process_dwflmod() has the parms structure which
> > contains the conf_load; you'd just need to pass that through to your
> > pre_load_module() callback I think.
> > 
> > It shouldn't be a massive change but I think it would be worthwhile.
> > 
> > Thanks!

Hi Alan, Arnaldo, thank you for review.

I understand your points, however adding elf_functions to conf_load
feels wrong to me. The global list I added was analogous to `encoders`
list in btf_encoder.c

I poked at the code a bit and came up with a context struct. It's
still a global variable, but with a clear init/exit interface.

Potentially other global BTF encoding-related state, for example
"main" btf_encoder and base_btf, could be stored in this context too.

Please see the diff below and let me know what you think.


---
 btf_encoder.c | 119 ++++++++++++++++++++++++++++----------------------
 btf_encoder.h |   3 ++
 pahole.c      |  16 ++++---
 3 files changed, 80 insertions(+), 58 deletions(-)

diff --git a/btf_encoder.c b/btf_encoder.c
index 1ec39fe..90aaa25 100644
--- a/btf_encoder.c
+++ b/btf_encoder.c
@@ -154,19 +154,76 @@ struct btf_kfunc_set_range {
 	uint64_t end;
 };
 
+static struct {
+	bool initialized;
+
+	/* In principle, multiple ELFs can be processed in one pahole run,
+	 * so we have to store elf_functions table per ELF.
+	 * An element is added to the list on btf_encoder__pre_load_module,
+	 * and removed after btf_encoder__encode is done.
+	 */
+	struct list_head elf_functions_list;
+
+	/* mutex only needed for add/delete, as this can happen in multiple encoding
+	 * threads.  Traversal of the list is currently confined to thread collection.
+	 */
+	pthread_mutex_t btf_encoder_list_lock;
+	struct list_head btf_encoder_list;
+
+} btf_encoding_context;
+
+int btf_encoding_context__init() {
+	int err = 0;
+
+	if (btf_encoding_context.initialized) {
+		fprintf(stderr, "btf_encoding_context__init() called while context is already initialized\n");
+		err = -1;
+		goto out;
+	}
+
+	INIT_LIST_HEAD(&btf_encoding_context.elf_functions_list);
+	INIT_LIST_HEAD(&btf_encoding_context.btf_encoder_list);
+	pthread_mutex_init(&btf_encoding_context.btf_encoder_list_lock, NULL);
+	btf_encoding_context.initialized = true;
+
+out:
+	return err;
+}
+
+static inline void elf_functions__delete(struct elf_functions *funcs);
+
+void btf_encoding_context__exit() {
+	struct list_head *pos, *tmp;
+
+	if (!btf_encoding_context.initialized) {
+		fprintf(stderr, "btf_encoding_context__exit() called while context is not initialized\n");
+		return;
+	}
+
+	list_for_each_safe(pos, tmp, &btf_encoding_context.elf_functions_list) {
+		struct elf_functions *funcs = list_entry(pos, struct elf_functions, node);
+		list_del(&funcs->node);
+		elf_functions__delete(funcs);
+	}
+
+	pthread_mutex_lock(&btf_encoding_context.btf_encoder_list_lock);
+	list_for_each_safe(pos, tmp, &btf_encoding_context.btf_encoder_list) {
+		struct btf_encoder *encoder = list_entry(pos, struct btf_encoder, node);
+		list_del(&encoder->node);
+		btf_encoder__delete(encoder);
+	}
+	pthread_mutex_unlock(&btf_encoding_context.btf_encoder_list_lock);
+
+	pthread_mutex_destroy(&btf_encoding_context.btf_encoder_list_lock);
+	btf_encoding_context.initialized = false;
+}
 
-/* In principle, multiple ELFs can be processed in one pahole run,
- * so we have to store elf_functions table per ELF.
- * An element is added to the list on btf_encoder__pre_load_module,
- * and removed after btf_encoder__encode is done.
- */
-static LIST_HEAD(elf_functions_list);
 
 static struct elf_functions *elf_functions__get(Elf *elf)
 {
 	struct list_head *pos;
 
-	list_for_each(pos, &elf_functions_list) {
+	list_for_each(pos, &btf_encoding_context.elf_functions_list) {
 		struct elf_functions *funcs = list_entry(pos, struct elf_functions, node);
 
 		if (funcs->elf == elf)
@@ -198,21 +255,9 @@ static void __elf_functions__delete(struct elf_functions *funcs)
 static inline void elf_functions__delete(struct elf_functions *funcs)
 {
 	__elf_functions__delete(funcs);
-	list_del(&funcs->node);
 	free(funcs);
 }
 
-static inline void elf_functions__delete_all(void)
-{
-	struct list_head *pos, *tmp;
-
-	list_for_each_safe(pos, tmp, &elf_functions_list) {
-		struct elf_functions *funcs = list_entry(pos, struct elf_functions, node);
-
-		elf_functions__delete(funcs);
-	}
-}
-
 static int elf_functions__collect(struct elf_functions *functions);
 
 int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf)
@@ -237,7 +282,7 @@ int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf)
 	if (err)
 		goto out_delete;
 
-	list_add_tail(&funcs->node, &elf_functions_list);
+	list_add_tail(&funcs->node, &btf_encoding_context.elf_functions_list);
 
 	return 0;
 
@@ -246,37 +291,11 @@ out_delete:
 	return err;
 }
 
-
-static LIST_HEAD(encoders);
-static pthread_mutex_t encoders__lock = PTHREAD_MUTEX_INITIALIZER;
-
-/* mutex only needed for add/delete, as this can happen in multiple encoding
- * threads.  Traversal of the list is currently confined to thread collection.
- */
-
-#define btf_encoders__for_each_encoder(encoder)		\
-	list_for_each_entry(encoder, &encoders, node)
-
 static void btf_encoders__add(struct btf_encoder *encoder)
 {
-	pthread_mutex_lock(&encoders__lock);
-	list_add_tail(&encoder->node, &encoders);
-	pthread_mutex_unlock(&encoders__lock);
-}
-
-static void btf_encoders__delete(struct btf_encoder *encoder)
-{
-	struct btf_encoder *existing = NULL;
-
-	pthread_mutex_lock(&encoders__lock);
-	/* encoder may not have been added to list yet; check. */
-	btf_encoders__for_each_encoder(existing) {
-		if (encoder == existing)
-			break;
-	}
-	if (encoder == existing)
-		list_del(&encoder->node);
-	pthread_mutex_unlock(&encoders__lock);
+	pthread_mutex_lock(&btf_encoding_context.btf_encoder_list_lock);
+	list_add_tail(&encoder->node, &btf_encoding_context.btf_encoder_list);
+	pthread_mutex_unlock(&btf_encoding_context.btf_encoder_list_lock);
 }
 
 #define PERCPU_SECTION ".data..percpu"
@@ -2215,7 +2234,6 @@ int btf_encoder__encode(struct btf_encoder *encoder)
 		err = btf_encoder__write_elf(encoder, encoder->btf, BTF_ELF_SEC);
 	}
 
-	elf_functions__delete_all();
 	return err;
 }
 
@@ -2588,7 +2606,6 @@ void btf_encoder__delete(struct btf_encoder *encoder)
 	if (encoder == NULL)
 		return;
 
-	btf_encoders__delete(encoder);
 	for (shndx = 0; shndx < encoder->seccnt; shndx++)
 		__gobuffer__delete(&encoder->secinfo[shndx].secinfo);
 	zfree(&encoder->filename);
diff --git a/btf_encoder.h b/btf_encoder.h
index 29f652a..c3886b8 100644
--- a/btf_encoder.h
+++ b/btf_encoder.h
@@ -23,6 +23,9 @@ enum btf_var_option {
 	BTF_VAR_GLOBAL = 2,
 };
 
+int btf_encoding_context__init();
+void btf_encoding_context__exit();
+
 struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filename, struct btf *base_btf, bool verbose, struct conf_load *conf_load);
 void btf_encoder__delete(struct btf_encoder *encoder);
 
diff --git a/pahole.c b/pahole.c
index 6f83636..2a6e012 100644
--- a/pahole.c
+++ b/pahole.c
@@ -3280,12 +3280,6 @@ static int pahole_threads_collect(struct conf_load *conf, int nr_threads, void *
 	err = 0;
 
 out:
-	for (i = 0; i < nr_threads; i++) {
-		if (threads[i]->encoder && threads[i]->encoder != btf_encoder) {
-			btf_encoder__delete(threads[i]->encoder);
-			threads[i]->encoder = NULL;
-		}
-	}
 	free(threads[0]);
 
 	return err;
@@ -3818,8 +3812,12 @@ int main(int argc, char *argv[])
 		conf_load.threads_collect = pahole_threads_collect;
 	}
 
-	if (btf_encode)
+	if (btf_encode) {
 		conf_load.pre_load_module = btf_encoder__pre_load_module;
+		int err = btf_encoding_context__init();
+		if (err < 0)
+			goto out;
+	}
 
 	// Make 'pahole --header type < file' a shorter form of 'pahole -C type --count 1 < file'
 	if (conf.header_type && !class_name && prettify_input) {
@@ -3928,7 +3926,11 @@ try_sole_arg_as_class_names:
 			goto out_cus_delete;
 		}
 	}
+
 out_ok:
+	if (btf_encode)
+		btf_encoding_context__exit();
+
 	if (stats_formatter != NULL)
 		print_stats();
 
-- 
2.43.0


> > > [...]

[PATCH v3 dwarves 4/5] btf_encoder: store a list of elf_function per function name

[Ihor Solodrai]

btf_encoder__save_func() accumulates observations of DWARF functions,
maintaining an elf_function per function name.

Part of this routine is a funcs_match() call, which requires access to
BTF implicitly referenced by btf_encoder_func_state.  In case when
elf_functions table is maintained by each btf_encoder this is not an
issue, because every btf_encoder_func_state available to this encoder
can only reference its own BTF. However if elf_functions table becomes
shared then existing elf_function/btf_encoder_function_state structs
can be produced by other encoders referring to their own BTFs. In this
case funcs_match() can not be called unless BTFs are available and
writes to them are synchronized in some manner (which is not
desirable).

Accumulated states are later merged between encoders in
btf_encoder__add_saved_funcs(). To enable sharing of the elf_functions
table between encoders, two members are introduced to struct
elf_function:
  - elf_function *next - to enable linked-list
  - btf_encoder *encoder - to find elf_function corresponding to a
    particular encoder in a list

Each element of elf_functions->entries is a head of a list that stores
elf_function structs, one for each encoder that searched for this
function name at least once.

btf_encoder__find_function() is modified to perform the search on
shared elf_functions table, and atomically update a corresponding list
as necessary.

At this point each btf_encoder is still maintaining it's own
elf_functions table, but the updated implementation is used.

Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
---
 btf_encoder.c | 122 +++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 96 insertions(+), 26 deletions(-)

diff --git a/btf_encoder.c b/btf_encoder.c
index 8e8fd05..002358c 100644
--- a/btf_encoder.c
+++ b/btf_encoder.c
@@ -30,6 +30,7 @@
 
 #include <assert.h>
 #include <errno.h>
+#include <stdatomic.h>
 #include <stdint.h>
 #include <search.h> /* for tsearch(), tfind() and tdestroy() */
 #include <pthread.h>
@@ -86,10 +87,15 @@ struct btf_encoder_func_state {
 };
 
 struct elf_function {
+	/* bsearch key */
 	const char	*name;
-	char		*alias;
-	bool		 generated;
-	size_t		prefixlen;
+	size_t		 prefixlen;
+	/* for list search */
+	_Atomic(struct elf_function *) next;
+	_Atomic(struct btf_encoder *) encoder;
+	/* encoder-specific state */
+	char *alias;
+	bool generated;
 	struct btf_encoder_func_state state;
 };
 
@@ -106,7 +112,7 @@ struct elf_functions {
 	struct list_head node; /* for elf_functions_list */
 	Elf *elf; /* source ELF */
 	struct elf_symtab *symtab;
-	struct elf_function *entries;
+	struct elf_function *entries; /* an array, each element is a head of a list */
 	int cnt;
 	int suffix_cnt; /* number of .isra, .part etc */
 };
@@ -157,10 +163,29 @@ struct btf_kfunc_set_range {
  */
 static LIST_HEAD(elf_functions_list);
 
-static inline void elf_functions__delete(struct elf_functions *funcs)
+static void __elf_functions__delete(struct elf_functions *funcs)
 {
+	struct elf_function *func, *next;
+
+	for (int i = 0; i < funcs->cnt; i++) {
+		/* free all list elements except the head */
+		func = funcs->entries[i].next;
+		while (func) {
+			next = func->next;
+			free(func->alias);
+			zfree(&func->state.annots);
+			zfree(&func->state.parms);
+			free(func);
+			func = next;
+		}
+	}
 	free(funcs->entries);
 	elf_symtab__delete(funcs->symtab);
+}
+
+static inline void elf_functions__delete(struct elf_functions *funcs)
+{
+	__elf_functions__delete(funcs);
 	list_del(&funcs->node);
 	free(funcs);
 }
@@ -1296,12 +1321,30 @@ static int32_t btf_encoder__add_func(struct btf_encoder *encoder, struct functio
 	return 0;
 }
 
+#define for_each_elf_function(func, head) \
+	for (struct elf_function *func = head; func; func = func->next)
+
+static inline struct elf_function *find_elf_function(struct elf_function *list_head,
+						     const struct btf_encoder *encoder)
+{
+	for_each_elf_function(f, list_head) {
+		if (f->encoder == encoder)
+			return f;
+	}
+
+	return NULL;
+}
+
 static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder)
 {
 	int i;
 
 	for (i = 0; i < encoder->functions.cnt; i++) {
-		struct elf_function *func = &encoder->functions.entries[i];
+		struct elf_function *func = find_elf_function(&encoder->functions.entries[i], encoder);
+
+		if (!func)
+			continue;
+
 		struct btf_encoder_func_state *state = &func->state;
 		struct btf_encoder *other_encoder = NULL;
 
@@ -1315,11 +1358,11 @@ static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder)
 			struct elf_function *other_func;
 			struct btf_encoder_func_state *other_state;
 			uint8_t optimized, unexpected, inconsistent;
+			other_func = find_elf_function(&other_encoder->functions.entries[i], other_encoder);
 
-			if (other_encoder == encoder)
+			if (other_encoder == encoder || !other_func)
 				continue;
 
-			other_func = &other_encoder->functions.entries[i];
 			other_state = &other_func->state;
 			if (!other_state->initialized)
 				continue;
@@ -1389,12 +1432,53 @@ static int elf_functions__collect_function(struct elf_functions *functions, GElf
 	return 0;
 }
 
-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(struct btf_encoder *encoder,
+						       const char *name,
+						       size_t prefixlen)
 {
 	struct elf_function key = { .name = name, .prefixlen = prefixlen };
+	struct elf_function *func, *head, *tmp;
+
+	head = bsearch(&key,
+		       encoder->functions.entries,
+		       encoder->functions.cnt,
+		       sizeof(key),
+		       functions_cmp);
+
+	/* If head is NULL, then there was no such function name in Elf */
+	if (!head)
+		return NULL;
 
-	return bsearch(&key, encoder->functions.entries, encoder->functions.cnt, sizeof(key), functions_cmp);
+	/* If head->encoder is NULL, then calling btf_encoder is the
+	 * first one to encounter this function name.  In this case
+	 * try to claim the head.
+	 */
+	tmp = NULL;
+	if (atomic_compare_exchange_strong(&head->encoder, &tmp, encoder))
+		return head;
+
+	/* If the head is already claimed (or if current claim attempt
+	 * failed), search through the list, and add new elf_function
+	 * for this encoder if not found.
+	 */
+	func = find_elf_function(head, encoder);
+	if (!func) {
+		func = zalloc(sizeof(*func));
+		func->name = head->name;
+		func->prefixlen = head->prefixlen;
+		/* Whenever btf_encoder allocates a new elf_function, it sets
+		 * itself as its encoder. So if the first search through the list
+		 * didn't find an elf_function, we can be sure no other
+		 * encoder would add it.  Therefore we only have to ensure
+		 * that the head->next is updated atomically.
+		 */
+		func->encoder = encoder;
+		do {
+			func->next = head->next;
+		} while (!atomic_compare_exchange_weak(&head->next, &func->next, func));
+	}
+
+	return func;
 }
 
 static bool btf_name_char_ok(char c, bool first)
@@ -2506,18 +2590,9 @@ out_delete:
 	return NULL;
 }
 
-void btf_encoder__delete_func(struct elf_function *func)
-{
-	free(func->alias);
-	zfree(&func->state.annots);
-	zfree(&func->state.parms);
-}
-
 void btf_encoder__delete(struct btf_encoder *encoder)
 {
-	int i;
 	size_t shndx;
-
 	if (encoder == NULL)
 		return;
 
@@ -2528,13 +2603,8 @@ void btf_encoder__delete(struct btf_encoder *encoder)
 	zfree(&encoder->source_filename);
 	btf__free(encoder->btf);
 	encoder->btf = NULL;
-	elf_symtab__delete(encoder->symtab);
 
-	for (i = 0; i < encoder->functions.cnt; i++)
-		btf_encoder__delete_func(&encoder->functions.entries[i]);
-	encoder->functions.cnt = 0;
-	free(encoder->functions.entries);
-	encoder->functions.entries = NULL;
+	__elf_functions__delete(&encoder->functions);
 
 	free(encoder);
 }
-- 
2.43.0

Re: [PATCH v3 dwarves 4/5] btf_encoder: store a list of elf_function per function name

[Alan Maguire]

hi Ihor

On 16/10/2024 01:10, Ihor Solodrai wrote:
> btf_encoder__save_func() accumulates observations of DWARF functions,
> maintaining an elf_function per function name.
> 

I've been struggling with the latter few patches in this series, and I
think that's in part due to the fact that you have to deal with some
(what I _think_ are) unnecessary complications in the existing code.

It should be easier to share ELF representations, but the situation
you've inherited is we mix immutable (ELF representation) and mutable
(function state information saved) representations, leading to
complications that require synchronization across threads.

Stepping back, I think with a few simplifications, we can lay a better
foundation for your work, and BTF encoding in general. Specifically if we

- always save and later add functions; currently we only save if we want
  to avoid inconsistencies, but this means having to maintain two
  codepaths for function addition which is messy. It is simpler to
  always save and later see if we want to add functions.
- fully separate ELF representation (immutable) from saved function
  represention (mutable). this will enable ELF sharing, and saved
  functions state can simply point back at the appropriate ELF function
- For each encoder, we just save all function state representations in a
  simple list; no merging is done at this point
- when adding saved functions, we combine lists from all encoders, merge
  findings on inconsistent representations where required, and add all
  functions without inconsistent representations.

This will mean no concurrency issues, and we end up with a simpler
representation which I think should make ELF sharing much easier. I've
got a rough prototype of 3 prerequisite patches doing the above at
https://github.com/acmel/dwarves/compare/master...alan-maguire:dwarves:elf-prep

The changes are contained in the last 3 patches there if you want to
take a look.

> Part of this routine is a funcs_match() call, which requires access to
> BTF implicitly referenced by btf_encoder_func_state.  In case when
> elf_functions table is maintained by each btf_encoder this is not an
> issue, because every btf_encoder_func_state available to this encoder
> can only reference its own BTF. However if elf_functions table becomes
> shared then existing elf_function/btf_encoder_function_state structs
> can be produced by other encoders referring to their own BTFs. In this
> case funcs_match() can not be called unless BTFs are available and
> writes to them are synchronized in some manner (which is not
> desirable).
> 
> Accumulated states are later merged between encoders in
> btf_encoder__add_saved_funcs(). To enable sharing of the elf_functions
> table between encoders, two members are introduced to struct
> elf_function:
>   - elf_function *next - to enable linked-list
>   - btf_encoder *encoder - to find elf_function corresponding to a
>     particular encoder in a list
> 
> Each element of elf_functions->entries is a head of a list that stores
> elf_function structs, one for each encoder that searched for this
> function name at least once.
> 
> btf_encoder__find_function() is modified to perform the search on
> shared elf_functions table, and atomically update a corresponding list
> as necessary.
> 
> At this point each btf_encoder is still maintaining it's own
> elf_functions table, but the updated implementation is used.
> 
> Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
> Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
> ---
>  btf_encoder.c | 122 +++++++++++++++++++++++++++++++++++++++-----------
>  1 file changed, 96 insertions(+), 26 deletions(-)
> 
> diff --git a/btf_encoder.c b/btf_encoder.c
> index 8e8fd05..002358c 100644
> --- a/btf_encoder.c
> +++ b/btf_encoder.c
> @@ -30,6 +30,7 @@
>  
>  #include <assert.h>
>  #include <errno.h>
> +#include <stdatomic.h>
>  #include <stdint.h>
>  #include <search.h> /* for tsearch(), tfind() and tdestroy() */
>  #include <pthread.h>
> @@ -86,10 +87,15 @@ struct btf_encoder_func_state {
>  };
>  
>  struct elf_function {
> +	/* bsearch key */
>  	const char	*name;
> -	char		*alias;
> -	bool		 generated;
> -	size_t		prefixlen;
> +	size_t		 prefixlen;
> +	/* for list search */
> +	_Atomic(struct elf_function *) next;
> +	_Atomic(struct btf_encoder *) encoder;
> +	/* encoder-specific state */
> +	char *alias;
> +	bool generated;
>  	struct btf_encoder_func_state state;
>  };
>  
> @@ -106,7 +112,7 @@ struct elf_functions {
>  	struct list_head node; /* for elf_functions_list */
>  	Elf *elf; /* source ELF */
>  	struct elf_symtab *symtab;
> -	struct elf_function *entries;
> +	struct elf_function *entries; /* an array, each element is a head of a list */
>  	int cnt;
>  	int suffix_cnt; /* number of .isra, .part etc */
>  };
> @@ -157,10 +163,29 @@ struct btf_kfunc_set_range {
>   */
>  static LIST_HEAD(elf_functions_list);
>  
> -static inline void elf_functions__delete(struct elf_functions *funcs)
> +static void __elf_functions__delete(struct elf_functions *funcs)
>  {
> +	struct elf_function *func, *next;
> +
> +	for (int i = 0; i < funcs->cnt; i++) {
> +		/* free all list elements except the head */
> +		func = funcs->entries[i].next;
> +		while (func) {
> +			next = func->next;
> +			free(func->alias);
> +			zfree(&func->state.annots);
> +			zfree(&func->state.parms);
> +			free(func);
> +			func = next;
> +		}
> +	}
>  	free(funcs->entries);
>  	elf_symtab__delete(funcs->symtab);
> +}
> +
> +static inline void elf_functions__delete(struct elf_functions *funcs)
> +{
> +	__elf_functions__delete(funcs);
>  	list_del(&funcs->node);
>  	free(funcs);
>  }
> @@ -1296,12 +1321,30 @@ static int32_t btf_encoder__add_func(struct btf_encoder *encoder, struct functio
>  	return 0;
>  }
>  
> +#define for_each_elf_function(func, head) \
> +	for (struct elf_function *func = head; func; func = func->next)
> +
> +static inline struct elf_function *find_elf_function(struct elf_function *list_head,
> +						     const struct btf_encoder *encoder)
> +{
> +	for_each_elf_function(f, list_head) {
> +		if (f->encoder == encoder)
> +			return f;
> +	}
> +
> +	return NULL;
> +}
> +
>  static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder)
>  {
>  	int i;
>  
>  	for (i = 0; i < encoder->functions.cnt; i++) {
> -		struct elf_function *func = &encoder->functions.entries[i];
> +		struct elf_function *func = find_elf_function(&encoder->functions.entries[i], encoder);
> +
> +		if (!func)
> +			continue;
> +
>  		struct btf_encoder_func_state *state = &func->state;
>  		struct btf_encoder *other_encoder = NULL;
>  
> @@ -1315,11 +1358,11 @@ static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder)
>  			struct elf_function *other_func;
>  			struct btf_encoder_func_state *other_state;
>  			uint8_t optimized, unexpected, inconsistent;
> +			other_func = find_elf_function(&other_encoder->functions.entries[i], other_encoder);
>  
> -			if (other_encoder == encoder)
> +			if (other_encoder == encoder || !other_func)
>  				continue;
>  
> -			other_func = &other_encoder->functions.entries[i];
>  			other_state = &other_func->state;
>  			if (!other_state->initialized)
>  				continue;
> @@ -1389,12 +1432,53 @@ static int elf_functions__collect_function(struct elf_functions *functions, GElf
>  	return 0;
>  }
>  
> -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(struct btf_encoder *encoder,
> +						       const char *name,
> +						       size_t prefixlen)
>  {
>  	struct elf_function key = { .name = name, .prefixlen = prefixlen };
> +	struct elf_function *func, *head, *tmp;
> +
> +	head = bsearch(&key,
> +		       encoder->functions.entries,
> +		       encoder->functions.cnt,
> +		       sizeof(key),
> +		       functions_cmp);
> +
> +	/* If head is NULL, then there was no such function name in Elf */
> +	if (!head)
> +		return NULL;
>  
> -	return bsearch(&key, encoder->functions.entries, encoder->functions.cnt, sizeof(key), functions_cmp);
> +	/* If head->encoder is NULL, then calling btf_encoder is the
> +	 * first one to encounter this function name.  In this case
> +	 * try to claim the head.
> +	 */
> +	tmp = NULL;
> +	if (atomic_compare_exchange_strong(&head->encoder, &tmp, encoder))
> +		return head;
> +
> +	/* If the head is already claimed (or if current claim attempt
> +	 * failed), search through the list, and add new elf_function
> +	 * for this encoder if not found.
> +	 */
> +	func = find_elf_function(head, encoder);
> +	if (!func) {
> +		func = zalloc(sizeof(*func));
> +		func->name = head->name;
> +		func->prefixlen = head->prefixlen;
> +		/* Whenever btf_encoder allocates a new elf_function, it sets
> +		 * itself as its encoder. So if the first search through the list
> +		 * didn't find an elf_function, we can be sure no other
> +		 * encoder would add it.  Therefore we only have to ensure
> +		 * that the head->next is updated atomically.
> +		 */
> +		func->encoder = encoder;
> +		do {
> +			func->next = head->next;
> +		} while (!atomic_compare_exchange_weak(&head->next, &func->next, func));
> +	}
> +
> +	return func;
>  }
>  
>  static bool btf_name_char_ok(char c, bool first)
> @@ -2506,18 +2590,9 @@ out_delete:
>  	return NULL;
>  }
>  
> -void btf_encoder__delete_func(struct elf_function *func)
> -{
> -	free(func->alias);
> -	zfree(&func->state.annots);
> -	zfree(&func->state.parms);
> -}
> -
>  void btf_encoder__delete(struct btf_encoder *encoder)
>  {
> -	int i;
>  	size_t shndx;
> -
>  	if (encoder == NULL)
>  		return;
>  
> @@ -2528,13 +2603,8 @@ void btf_encoder__delete(struct btf_encoder *encoder)
>  	zfree(&encoder->source_filename);
>  	btf__free(encoder->btf);
>  	encoder->btf = NULL;
> -	elf_symtab__delete(encoder->symtab);
>  
> -	for (i = 0; i < encoder->functions.cnt; i++)
> -		btf_encoder__delete_func(&encoder->functions.entries[i]);
> -	encoder->functions.cnt = 0;
> -	free(encoder->functions.entries);
> -	encoder->functions.entries = NULL;
> +	__elf_functions__delete(&encoder->functions);
>  
>  	free(encoder);
>  }

Re: [PATCH v3 dwarves 4/5] btf_encoder: store a list of elf_function per function name

[Ihor Solodrai]

On Monday, October 21st, 2024 at 10:51 AM, Alan Maguire <alan.maguire@oracle.com> wrote:

> hi Ihor
> 
> On 16/10/2024 01:10, Ihor Solodrai wrote:
> 
> > btf_encoder__save_func() accumulates observations of DWARF functions,
> > maintaining an elf_function per function name.
> 
> 
> I've been struggling with the latter few patches in this series, and I
> think that's in part due to the fact that you have to deal with some
> (what I think are) unnecessary complications in the existing code.
> 
> It should be easier to share ELF representations, but the situation
> you've inherited is we mix immutable (ELF representation) and mutable
> (function state information saved) representations, leading to
> complications that require synchronization across threads.
> 
> Stepping back, I think with a few simplifications, we can lay a better
> foundation for your work, and BTF encoding in general. Specifically if we
> 
> - always save and later add functions; currently we only save if we want
> to avoid inconsistencies, but this means having to maintain two
> codepaths for function addition which is messy. It is simpler to
> always save and later see if we want to add functions.
> - fully separate ELF representation (immutable) from saved function
> represention (mutable). this will enable ELF sharing, and saved
> functions state can simply point back at the appropriate ELF function
> - For each encoder, we just save all function state representations in a
> simple list; no merging is done at this point
> - when adding saved functions, we combine lists from all encoders, merge
> findings on inconsistent representations where required, and add all
> functions without inconsistent representations.
> 
> This will mean no concurrency issues, and we end up with a simpler
> representation which I think should make ELF sharing much easier. I've
> got a rough prototype of 3 prerequisite patches doing the above at
> https://github.com/acmel/dwarves/compare/master...alan-maguire:dwarves:elf-prep
> 
> The changes are contained in the last 3 patches there if you want to
> take a look.

Hi Alan.

Finally got time to try your changes.  Apologies for delay, was busy
with other things.

TL;DR Here is my patchset rebased on top of your commits:
* https://github.com/theihor/dwarves/pull/7

Please take a look, and let's sync on how do we plan to merge it
in. Your commits seem to have debug code in them, so maybe you'd want
to submit a clean version first.


I must say earlier Eduard pointed out (off-list) the problems that
you've described, but at the time I thought it would be too many
changes if I tried to address them.

It is indeed easier to move to a shared ELF functions table if all
function states are collected before merging them, mostly because the
need for thread synchronization disappears. I was able to effectively
delete patch 4/5 of the series.

One thing that bothered me is that now btf_encoder__add_saved_funcs()
does more work (compared to v3 of the patchset). This is of course due
to the fact that it is required to collect all function states from
all encoders and group them by name, while it was done "automatically"
when states were stored in elf_functions table. It's not good, because
this step is single-threaded.

However, I did some superficial measurements, and it appears
btf_encoder__add_saved_funcs() step takes ~2% of the time when
encoding vmlinux. So it's probably not worth complicating.

Regarding "global variables" fork of our discussion [1], I didn't get
any feedback from you or Arnaldo in response to suggested diff.
I included a more thought out version in the branch [2], please take 
a look.


See below some perf stats: marginal speedup and slower RSS growth
with increasing number of threads.

WIP v4 branch [2]:

     Performance counter stats for '/home/theihor/dev/dwarves/build/pahole -J -j23 --btf_features=encode_force,var,float,enum64,decl_tag,type_tag,optimized_func,consistent_func,decl_tag_kfuncs --btf_encode_detached=/dev/null --lang_exclude=rust /home/theihor/git/kernel.org/bpf-next/kbuild-output/.tmp_vmlinux1' (13 runs):

        83,054,827,477      cycles:u                                                                ( +-  0.29% )

                3.9829 +- 0.0374 seconds time elapsed  ( +-  0.94% )

    -j2: 	Maximum resident set size (kbytes): 783296
    -j4: 	Maximum resident set size (kbytes): 866976
    -j8: 	Maximum resident set size (kbytes): 992740
    -j16: 	Maximum resident set size (kbytes): 1038788
    -j32: 	Maximum resident set size (kbytes): 1169284
    -j64: 	Maximum resident set size (kbytes): 1347232

dwarves/next [3]

     Performance counter stats for '/home/theihor/dev/dwarves/build/pahole -J -j23 --btf_features=encode_force,var,float,enum64,decl_tag,type_tag,optimized_func,consistent_func,decl_tag_kfuncs --btf_encode_detached=/dev/null --lang_exclude=rust /home/theihor/git/kernel.org/bpf-next/kbuild-output/.tmp_vmlinux1' (13 runs):

        87,748,403,977      cycles:u                                                                ( +-  0.23% )

                4.0570 +- 0.0240 seconds time elapsed  ( +-  0.59% )

    checking max rss
    -j2: 	Maximum resident set size (kbytes): 787256
    -j4: 	Maximum resident set size (kbytes): 884360
    -j8: 	Maximum resident set size (kbytes): 1018996
    -j16: 	Maximum resident set size (kbytes): 1083528
    -j32: 	Maximum resident set size (kbytes): 1279880
    -j64: 	Maximum resident set size (kbytes): 1634656


[1]: https://lore.kernel.org/dwarves/4G5AFfVer_N_eJCZYc22pQM9rXbHOV2CZ4uOmqh4gFd1K2mgnbIDIZUpynMNCdJ-CEyvsBr0-cPdUzgNnM05NPkPjRdqdAnCAp8DrvUc-Iw=@pm.me/
[2]: https://github.com/theihor/dwarves/pull/7
[3]: https://github.com/theihor/dwarves/commit/729fd9963df576a04f2ba371b033c5300ebf0a91

> [...]

Re: [PATCH v3 dwarves 4/5] btf_encoder: store a list of elf_function per function name

[Ihor Solodrai]

On Wednesday, October 30th, 2024 at 5:14 PM, Ihor Solodrai <ihor.solodrai@pm.me> wrote:

> 
> Hi Alan.
> 
> Finally got time to try your changes. Apologies for delay, was busy
> with other things.
> 
> TL;DR Here is my patchset rebased on top of your commits:
> * https://github.com/theihor/dwarves/pull/7
> 
> Please take a look, and let's sync on how do we plan to merge it
> in. Your commits seem to have debug code in them, so maybe you'd want
> to submit a clean version first.

Alan, Arnaldo,

Did you get a chance to review the changes rebased on Alan's work?

I think the state of commits in the branch is good enough as is, so
I am inclined to send them as v4 of the patchset, assuming Alan
doesn't mind me including his patches.

Thanks.

> > [...]
> 
>

Re: [PATCH v3 dwarves 4/5] btf_encoder: store a list of elf_function per function name

[Alan Maguire]

On 06/11/2024 23:28, Ihor Solodrai wrote:
> On Wednesday, October 30th, 2024 at 5:14 PM, Ihor Solodrai <ihor.solodrai@pm.me> wrote:
> 
>>
>> Hi Alan.
>>
>> Finally got time to try your changes. Apologies for delay, was busy
>> with other things.
>>
>> TL;DR Here is my patchset rebased on top of your commits:
>> * https://github.com/theihor/dwarves/pull/7
>>
>> Please take a look, and let's sync on how do we plan to merge it
>> in. Your commits seem to have debug code in them, so maybe you'd want
>> to submit a clean version first.
> 
> Alan, Arnaldo,
> 
> Did you get a chance to review the changes rebased on Alan's work?
> 
> I think the state of commits in the branch is good enough as is, so
> I am inclined to send them as v4 of the patchset, assuming Alan
> doesn't mind me including his patches.
>

I need to clean up my patches and verify they generate identical BTF
from the same vmlinux, so there's a bit of work to do there first. I
should have something ready early next week. Hopefully won't look much
different, just with debug stuff removed.

Thanks

Alan

[PATCH v3 dwarves 5/5] btf_encoder: switch to shared elf_functions table

[Ihor Solodrai]

Do not collect functions from ELF for each new btf_encoder, and
instead set a pointer to a shared elf_functions table, built
beforehand by btf_encoder__pre_cus__load_module().

Change the algorithm of btf_encoder__add_saved_funcs().  Traverse
elf_functions table once and for each function do the following:
* check function states of each elf_function in a list to determine if
  it should be added to BTF
* if yes, add the function to the BTF of the owner of the first
  elf_function in the list

Do not call btf_encoder__add_saved_funcs() on every
btf_encoder__add_encoder(). Instead, for non-reproducible
multi-threaded case do that in pahole_threads_collect(), and for
single-threaded or reproducible_build do that right before
btf_encoder__encode().

Signed-off-by: Ihor Solodrai <ihor.solodrai@pm.me>
---
 btf_encoder.c | 113 +++++++++++++++++++++++---------------------------
 btf_encoder.h |   1 +
 pahole.c      |   9 +++-
 3 files changed, 61 insertions(+), 62 deletions(-)

diff --git a/btf_encoder.c b/btf_encoder.c
index 002358c..1ec39fe 100644
--- a/btf_encoder.c
+++ b/btf_encoder.c
@@ -80,7 +80,6 @@ struct btf_encoder_func_state {
 	uint8_t optimized_parms:1;
 	uint8_t unexpected_reg:1;
 	uint8_t inconsistent_proto:1;
-	uint8_t processed:1;
 	int ret_type_id;
 	struct btf_encoder_func_parm *parms;
 	struct btf_encoder_func_annot *annots;
@@ -141,7 +140,7 @@ struct btf_encoder {
 	struct elf_secinfo *secinfo;
 	size_t             seccnt;
 	int                encode_vars;
-	struct elf_functions functions;
+	struct elf_functions *functions;
 };
 
 struct btf_func {
@@ -163,6 +162,19 @@ struct btf_kfunc_set_range {
  */
 static LIST_HEAD(elf_functions_list);
 
+static struct elf_functions *elf_functions__get(Elf *elf)
+{
+	struct list_head *pos;
+
+	list_for_each(pos, &elf_functions_list) {
+		struct elf_functions *funcs = list_entry(pos, struct elf_functions, node);
+
+		if (funcs->elf == elf)
+			return funcs;
+	}
+	return NULL;
+}
+
 static void __elf_functions__delete(struct elf_functions *funcs)
 {
 	struct elf_function *func, *next;
@@ -238,8 +250,6 @@ out_delete:
 static LIST_HEAD(encoders);
 static pthread_mutex_t encoders__lock = PTHREAD_MUTEX_INITIALIZER;
 
-static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder);
-
 /* mutex only needed for add/delete, as this can happen in multiple encoding
  * threads.  Traversal of the list is currently confined to thread collection.
  */
@@ -891,8 +901,6 @@ int32_t btf_encoder__add_encoder(struct btf_encoder *encoder, struct btf_encoder
 	if (encoder == other)
 		return 0;
 
-	btf_encoder__add_saved_funcs(other);
-
 	for (shndx = 1; shndx < other->seccnt; shndx++) {
 		struct gobuffer *var_secinfo_buf = &other->secinfo[shndx].secinfo;
 		size_t sz = gobuffer__size(var_secinfo_buf);
@@ -1335,61 +1343,52 @@ static inline struct elf_function *find_elf_function(struct elf_function *list_h
 	return NULL;
 }
 
-static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder)
-{
-	int i;
 
-	for (i = 0; i < encoder->functions.cnt; i++) {
-		struct elf_function *func = find_elf_function(&encoder->functions.entries[i], encoder);
-
-		if (!func)
-			continue;
+/* Each element of elf_functions->entries is a list of a variable
+ * number of elf_function structs, because not all encoders saved a
+ * particular function.  However each function saved by at least one
+ * encoder needs to be added to BTF _somewhere_. Here we traverse the
+ * entire elf_functions table, and for each list of elf_function
+ * structs a function is added to the BTF of the encoder of the first
+ * elf_function in the list.
+ */
+int btf_encoder__add_saved_funcs(struct btf_encoder *base_encoder)
+{
+	struct elf_functions *functions = base_encoder->functions;
 
-		struct btf_encoder_func_state *state = &func->state;
-		struct btf_encoder *other_encoder = NULL;
+	for (int i = 0; i < functions->cnt; i++) {
+		struct elf_function *list_head = &functions->entries[i];
+		struct btf_encoder_func_state *state, *other_state;
+		struct elf_function *func;
+		bool skip_func = false;
 
-		if (!state->initialized || state->processed)
-			continue;
-		/* merge optimized-out status across encoders; since each
-		 * encoder has the same elf symbol table we can use the
-		 * same index to access the same elf symbol.
+		/* list_head without an encoder means no encoder has
+		 * saved a function with this name
 		 */
-		btf_encoders__for_each_encoder(other_encoder) {
-			struct elf_function *other_func;
-			struct btf_encoder_func_state *other_state;
-			uint8_t optimized, unexpected, inconsistent;
-			other_func = find_elf_function(&other_encoder->functions.entries[i], other_encoder);
-
-			if (other_encoder == encoder || !other_func)
-				continue;
+		if (!list_head->encoder)
+			continue;
 
+		func = list_head;
+		state = &func->state;
+		for_each_elf_function(other_func, list_head) {
 			other_state = &other_func->state;
-			if (!other_state->initialized)
-				continue;
-			optimized = state->optimized_parms | other_state->optimized_parms;
-			unexpected = state->unexpected_reg | other_state->unexpected_reg;
-			inconsistent = state->inconsistent_proto | other_state->inconsistent_proto;
-			if (!unexpected && !inconsistent &&
-			    !funcs__match(encoder, func,
-					  encoder->btf, state,
-					  other_encoder->btf, other_state))
-				inconsistent = 1;
-			state->optimized_parms = other_state->optimized_parms = optimized;
-			state->unexpected_reg = other_state->unexpected_reg = unexpected;
-			state->inconsistent_proto = other_state->inconsistent_proto = inconsistent;
-
-			other_state->processed = 1;
+			skip_func |= other_state->inconsistent_proto;
+			skip_func |= other_state->unexpected_reg;
+			skip_func |= !funcs__match(func->encoder, func,
+						   func->encoder->btf, state,
+						   other_func->encoder->btf, other_state);
+			if (skip_func)
+				break;
 		}
 		/* do not exclude functions with optimized-out parameters; they
 		 * may still be _called_ with the right parameter values, they
 		 * just do not _use_ them.  Only exclude functions with
 		 * unexpected register use or multiple inconsistent prototypes.
 		 */
-		if (!state->unexpected_reg && !state->inconsistent_proto) {
-			if (btf_encoder__add_func(encoder, NULL, func))
+		if (!skip_func) {
+			if (btf_encoder__add_func(func->encoder, NULL, func))
 				return -1;
 		}
-		state->processed = 1;
 	}
 	return 0;
 }
@@ -1440,8 +1439,8 @@ static struct elf_function *btf_encoder__find_function(struct btf_encoder *encod
 	struct elf_function *func, *head, *tmp;
 
 	head = bsearch(&key,
-		       encoder->functions.entries,
-		       encoder->functions.cnt,
+		       encoder->functions->entries,
+		       encoder->functions->cnt,
 		       sizeof(key),
 		       functions_cmp);
 
@@ -2166,9 +2165,6 @@ int btf_encoder__encode(struct btf_encoder *encoder)
 	int err;
 	size_t shndx;
 
-	/* for single-threaded case, saved funcs are added here */
-	btf_encoder__add_saved_funcs(encoder);
-
 	for (shndx = 1; shndx < encoder->seccnt; shndx++)
 		if (gobuffer__size(&encoder->secinfo[shndx].secinfo))
 			btf_encoder__add_datasec(encoder, shndx);
@@ -2535,8 +2531,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
 				printf("%s: '%s' doesn't have symtab.\n", __func__, cu->filename);
 			goto out;
 		}
-		encoder->functions.symtab = encoder->symtab;
-		encoder->functions.elf = cu->elf;
+		encoder->functions = elf_functions__get(cu->elf);
 
 		/* index the ELF sections for later lookup */
 
@@ -2575,9 +2570,6 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam
 		if (!found_percpu && encoder->verbose)
 			printf("%s: '%s' doesn't have '%s' section\n", __func__, cu->filename, PERCPU_SECTION);
 
-		if (elf_functions__collect(&encoder->functions))
-			goto out_delete;
-
 		if (encoder->verbose)
 			printf("File %s:\n", cu->filename);
 		btf_encoders__add(encoder);
@@ -2603,8 +2595,7 @@ void btf_encoder__delete(struct btf_encoder *encoder)
 	zfree(&encoder->source_filename);
 	btf__free(encoder->btf);
 	encoder->btf = NULL;
-
-	__elf_functions__delete(&encoder->functions);
+	elf_symtab__delete(encoder->symtab);
 
 	free(encoder);
 }
@@ -2703,7 +2694,7 @@ int btf_encoder__encode_cu(struct btf_encoder *encoder, struct cu *cu, struct co
 			continue;
 		if (!ftype__has_arg_names(&fn->proto))
 			continue;
-		if (encoder->functions.cnt) {
+		if (encoder->functions->cnt) {
 			const char *name;
 
 			name = function__name(fn);
@@ -2719,7 +2710,7 @@ int btf_encoder__encode_cu(struct btf_encoder *encoder, struct cu *cu, struct co
 					save = true;
 				else
 					func->generated = true;
-			} else if (encoder->functions.suffix_cnt &&
+			} else if (encoder->functions->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
diff --git a/btf_encoder.h b/btf_encoder.h
index 7debd67..29f652a 100644
--- a/btf_encoder.h
+++ b/btf_encoder.h
@@ -33,6 +33,7 @@ int btf_encoder__encode_cu(struct btf_encoder *encoder, struct cu *cu, struct co
 struct btf *btf_encoder__btf(struct btf_encoder *encoder);
 
 int btf_encoder__add_encoder(struct btf_encoder *encoder, struct btf_encoder *other);
+int btf_encoder__add_saved_funcs(struct btf_encoder *base_encoder);
 
 int btf_encoder__pre_load_module(Dwfl_Module *mod, Elf *elf);
 
diff --git a/pahole.c b/pahole.c
index 891af3a..6f83636 100644
--- a/pahole.c
+++ b/pahole.c
@@ -3262,12 +3262,16 @@ static int pahole_threads_collect(struct conf_load *conf, int nr_threads, void *
 	if (error)
 		goto out;
 
+	err = btf_encoder__add_saved_funcs(btf_encoder);
+	if (err < 0)
+		goto out;
+
 	for (i = 0; i < nr_threads; i++) {
 		/*
 		 * Merge content of the btf instances of worker threads to the btf
 		 * instance of the primary btf_encoder.
                 */
-		if (!threads[i]->btf)
+		if (!threads[i]->encoder || !threads[i]->btf)
 			continue;
 		err = btf_encoder__add_encoder(btf_encoder, threads[i]->encoder);
 		if (err < 0)
@@ -3915,6 +3919,9 @@ try_sole_arg_as_class_names:
 			exit(1);
 		}
 
+		if (conf_load.nr_jobs <= 1 || conf_load.reproducible_build)
+			btf_encoder__add_saved_funcs(btf_encoder);
+
 		err = btf_encoder__encode(btf_encoder);
 		if (err) {
 			fputs("Failed to encode BTF\n", stderr);
-- 
2.43.0