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@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);
}
--
2.43.0
