From patchwork Tue Jan 7 19:09:53 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ihor Solodrai X-Patchwork-Id: 13929535 Received: from mail-10629.protonmail.ch (mail-10629.protonmail.ch [79.135.106.29]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id F3B4E1F4E4E for ; Tue, 7 Jan 2025 19:10:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.135.106.29 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736277006; cv=none; b=TBW1OkDoyOr57iS7HDoCgs7bVH4PU2RyH6Q0FkM+SFdSk12QKj6XFEjEbfFigjJkGe+KhB8cccr2hNgcu3TaJcQN8aSg/Rig8K8+Naa9x7T//JbaQBgrURYgOW9nt43Euzc3lYuR2L22/Lw8N0RmU1/A1OncNYJI3cunQ6aVWxI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736277006; c=relaxed/simple; bh=nWRBvXIZLUG/0nIGRYJF9tUFh/pcE2I31qSTDymXz8o=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=HjyfhMUNy28dzR5o36sx60KCQgzJuohhymDdpk8rOh0cyx/iVTTXRUIEcWVloOOsTD0HHiGZKkEEwGYciwQQ1K+ihuEzSZev9fcovg+cxiLOGQF5Hku2C/SRBG082jq521lXvuF4KqDJVSkMkl2t33lcj3b6UvV1yuIcH3Ke8Jk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=pm.me; spf=pass smtp.mailfrom=pm.me; dkim=pass (2048-bit key) header.d=pm.me header.i=@pm.me header.b=h+gkayPy; arc=none smtp.client-ip=79.135.106.29 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=pm.me Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=pm.me Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=pm.me header.i=@pm.me header.b="h+gkayPy" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pm.me; s=protonmail3; t=1736276999; x=1736536199; bh=23TypOfuJ4mIy7H6YtvpcaGiYoIB9NhyhrjCz2YicjA=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector:List-Unsubscribe:List-Unsubscribe-Post; b=h+gkayPyXJZuzU1r341bT6mZy0ILMs3LF0sUx1bz+Bo2n3kP5k1AlzK/u13CDiH41 LvmqLxo/rCglD5puvGriQHGdHXaSrEdnkv4zK7UWz+jBooWiA3BaHgkC++xtD0yDP8 59C+5JgiyDSNJSwcxceG3V0V8oaH8Uqu2kWt4dAk0rJPKfJGUzqt1mt0IysjpWDZ2d 8O6sN57an9Enbr9f/AR3tkObk0Zq5D5u7WeGs0YDZguOcLxm/zgJ1T7TcNLe/1fqCM O2/oW7+qif3Yy9IVkESHWn5MsbxpgbaTC4omAkhArgvF5tqt9s6+dyWdqL5Bqqok32 WvYWBeg6DSnqA== Date: Tue, 07 Jan 2025 19:09:53 +0000 To: dwarves@vger.kernel.org From: Ihor Solodrai Cc: bpf@vger.kernel.org, acme@kernel.org, alan.maguire@oracle.com, eddyz87@gmail.com, andrii@kernel.org, mykolal@fb.com, olsajiri@gmail.com Subject: [PATCH dwarves v4] btf_encoder: switch func_states from a list to an array Message-ID: <20250107190855.2312210-11-ihor.solodrai@pm.me> In-Reply-To: <20250107190855.2312210-1-ihor.solodrai@pm.me> References: <20250107190855.2312210-1-ihor.solodrai@pm.me> Feedback-ID: 27520582:user:proton X-Pm-Message-ID: c252fb91eb6bbb56fab06b9dae7145258bf739b0 Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 With only a single encoder, it's now easier to acummulate function states into an array, and then sort it before merging the states and adding the functions to BTF. Previously a list (per encoder) was collected, and because the sorting is required, the lists had to be converted into a temporary array in a separate step. Signed-off-by: Ihor Solodrai --- btf_encoder.c | 95 ++++++++++++++++++++++++++++++--------------------- 1 file changed, 57 insertions(+), 38 deletions(-) diff --git a/btf_encoder.c b/btf_encoder.c index da99fbb..78efd70 100644 --- a/btf_encoder.c +++ b/btf_encoder.c @@ -72,7 +72,6 @@ struct btf_encoder_func_annot { /* state used to do later encoding of saved functions */ struct btf_encoder_func_state { - struct list_head node; struct btf_encoder *encoder; struct elf_function *elf; uint32_t type_id_off; @@ -134,7 +133,11 @@ struct btf_encoder { struct elf_secinfo *secinfo; size_t seccnt; int encode_vars; - struct list_head func_states; + struct { + struct btf_encoder_func_state *array; + int cnt; + int cap; + } func_states; /* This is a list of elf_functions tables, one per ELF. * Multiple ELF modules can be processed in one pahole run, * so we have to store elf_functions tables per ELF. @@ -1078,9 +1081,31 @@ static bool funcs__match(struct btf_encoder_func_state *s1, return true; } +static struct btf_encoder_func_state *btf_encoder__alloc_func_state(struct btf_encoder *encoder) +{ + struct btf_encoder_func_state *tmp; + + if (encoder->func_states.cnt >= encoder->func_states.cap) { + + /* We only need to grow to accommodate duplicate + * function declarations across different CUs, so the + * rate of the array growth shouldn't be high. + */ + encoder->func_states.cap += 64; + + tmp = realloc(encoder->func_states.array, sizeof(*tmp) * encoder->func_states.cap); + if (!tmp) + return NULL; + + encoder->func_states.array = tmp; + } + + return &encoder->func_states.array[encoder->func_states.cnt++]; +} + static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct function *fn, struct elf_function *func) { - struct btf_encoder_func_state *state = zalloc(sizeof(*state)); + struct btf_encoder_func_state *state = btf_encoder__alloc_func_state(encoder); struct ftype *ftype = &fn->proto; struct btf *btf = encoder->btf; struct llvm_annotation *annot; @@ -1142,7 +1167,6 @@ static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct functi idx++; } } - list_add_tail(&state->node, &encoder->func_states); return 0; out: zfree(&state->annots); @@ -1219,17 +1243,15 @@ static int functions_cmp(const void *_a, const void *_b) static int saved_functions_cmp(const void *_a, const void *_b) { - struct btf_encoder_func_state * const *a = _a; - struct btf_encoder_func_state * const *b = _b; + const struct btf_encoder_func_state *a = _a; + const struct btf_encoder_func_state *b = _b; - return functions_cmp((*a)->elf, (*b)->elf); + return functions_cmp(a->elf, b->elf); } -static int saved_functions_combine(void *_a, void *_b) +static int saved_functions_combine(struct btf_encoder_func_state *a, struct btf_encoder_func_state *b) { uint8_t optimized, unexpected, inconsistent; - struct btf_encoder_func_state *a = _a; - struct btf_encoder_func_state *b = _b; int ret; ret = strncmp(a->elf->name, b->elf->name, @@ -1250,44 +1272,37 @@ static int saved_functions_combine(void *_a, void *_b) static void btf_encoder__delete_saved_funcs(struct btf_encoder *encoder) { - struct btf_encoder_func_state *pos, *s; + struct btf_encoder_func_state *state; - list_for_each_entry_safe(pos, s, &encoder->func_states, node) { - list_del(&pos->node); - free(pos->parms); - free(pos->annots); - free(pos); + for (int i = 0; i < encoder->func_states.cnt; i++) { + state = &encoder->func_states.array[i]; + free(state->parms); + free(state->annots); } + + free(encoder->func_states.array); + + encoder->func_states.array = NULL; + encoder->func_states.cnt = 0; + encoder->func_states.cap = 0; } static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder, bool skip_encoding_inconsistent_proto) { - struct btf_encoder_func_state **saved_fns = NULL, *s; - int err = 0, i = 0, j, nr_saved_fns = 0; - - /* Retrieve function states from the encoder, combine them - * and sort by name, addr. - */ - list_for_each_entry(s, &encoder->func_states, node) { - nr_saved_fns++; - } + struct btf_encoder_func_state *saved_fns = encoder->func_states.array; + int nr_saved_fns = encoder->func_states.cnt; + int err = 0, i = 0, j; if (nr_saved_fns == 0) goto out; - saved_fns = calloc(nr_saved_fns, sizeof(*saved_fns)); - if (!saved_fns) { - err = -ENOMEM; - goto out; - } - - list_for_each_entry(s, &encoder->func_states, node) { - saved_fns[i++] = s; - } + /* Sort the saved_fns so that we can merge multiple states of + * the "same" function into one, before adding it to the BTF. + */ qsort(saved_fns, nr_saved_fns, sizeof(*saved_fns), saved_functions_cmp); for (i = 0; i < nr_saved_fns; i = j) { - struct btf_encoder_func_state *state = saved_fns[i]; + struct btf_encoder_func_state *state = &saved_fns[i]; bool add_to_btf = !skip_encoding_inconsistent_proto; /* Compare across sorted functions that match by name/prefix; @@ -1295,7 +1310,7 @@ static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder, bool skip_e */ j = i + 1; - while (j < nr_saved_fns && saved_functions_combine(saved_fns[i], saved_fns[j]) == 0) + while (j < nr_saved_fns && saved_functions_combine(&saved_fns[i], &saved_fns[j]) == 0) j++; /* do not exclude functions with optimized-out parameters; they @@ -1313,7 +1328,6 @@ static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder, bool skip_e } out: - free(saved_fns); btf_encoder__delete_saved_funcs(encoder); return err; @@ -2404,7 +2418,7 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam encoder->need_index_type = false; encoder->array_index_id = 0; encoder->encode_vars = 0; - INIT_LIST_HEAD(&encoder->func_states); + if (!conf_load->skip_encoding_btf_vars) encoder->encode_vars |= BTF_VAR_PERCPU; if (conf_load->encode_btf_global_vars) @@ -2417,6 +2431,11 @@ struct btf_encoder *btf_encoder__new(struct cu *cu, const char *detached_filenam encoder->symtab = funcs->symtab; + /* Start with funcs->cnt. The array may grow in btf_encoder__alloc_func_state() */ + encoder->func_states.array = zalloc(sizeof(*encoder->func_states.array) * funcs->cnt); + encoder->func_states.cap = funcs->cnt; + encoder->func_states.cnt = 0; + GElf_Ehdr ehdr; if (gelf_getehdr(cu->elf, &ehdr) == NULL) {