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@xxxxxxxxx> > Signed-off-by: Ihor Solodrai <ihor.solodrai@xxxxx> > --- > 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); > }
