From patchwork Thu Jan 9 19:00:54 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ihor Solodrai X-Patchwork-Id: 13933152 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-40134.protonmail.ch (mail-40134.protonmail.ch [185.70.40.134]) (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 9B8E71B4133 for ; Thu, 9 Jan 2025 19:00:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=185.70.40.134 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736449261; cv=none; b=OSMJkd7XlA6fcyMerohfRQ8pmDRzXytxeLHlrpQsDmq7ChHhe+fHjMGsSdGdfOm1KodXoiKuxjkDDEfVEu64P2aRAt8qiTv8leX4bV9j0Vl3HPOLb1KT0RoSYdSYOw0xw5BsPfoP49nNPgY44p7X7ynMuKBkqiPNM2nFQM3KxX0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736449261; c=relaxed/simple; bh=nWRBvXIZLUG/0nIGRYJF9tUFh/pcE2I31qSTDymXz8o=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=Z57+SCEIY5cND40AFNpSjKQU5Jt4QwiCBjo/56dHISEIOB/wuRRmoujwY4N0ACYrtIP0UC2ADpljwzMBDmD0b99CHfbiHgVmUZmGXlrpq2zwFnNqKXLDBM4GRJcX4Yb6SaOKoyzdKJNgpH+p9xynsJKWla3J+OE538M7BwJ7kzw= 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=qAgv0GVW; arc=none smtp.client-ip=185.70.40.134 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="qAgv0GVW" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pm.me; s=protonmail3; t=1736449257; x=1736708457; 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=qAgv0GVW3VUTEQWpt6gCjQJqUq8aL7elAApeyiGPQgTFDY+RXKLULOTFadMJ15m1f mxVyaNRqOwkjdlC7QgJy8ovrdCpMyht2/sf5dXkyRmsBqBpk/nCf4ULIQlpbKhLAor Ux0o0OgVIf9rHPhTBtSFXus6Cnk/f95JOHAT/8QoHu5SAn/Gw4RMaHXnyNIXFHaVf3 BviASX32VLpF3FmoMgtDnoBNMLiTDDI8a/xWrsouKInq5TOb/6ARw1BS7RgHRrmgxQ 5idrMMoLuFMfokM034WDjTxbQ3dyXREHGY0swotMDHuBX97RVJx9lusFEqL7kECcZ4 uvIfC6wlYKCnw== Date: Thu, 09 Jan 2025 19:00:54 +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 RESEND 10/10] btf_encoder: switch func_states from a list to an array Message-ID: <20250109185950.653110-11-ihor.solodrai@pm.me> In-Reply-To: <20250109185950.653110-1-ihor.solodrai@pm.me> References: <20250109185950.653110-1-ihor.solodrai@pm.me> Feedback-ID: 27520582:user:proton X-Pm-Message-ID: 199c3894c60d4be22ce735d63b1bc3eda9dd18c4 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) {