From patchwork Thu Nov 28 01:23:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ihor Solodrai X-Patchwork-Id: 13887514 Received: from mail-10631.protonmail.ch (mail-10631.protonmail.ch [79.135.106.31]) (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 8A6B21DFCB for ; Thu, 28 Nov 2024 01:24:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=79.135.106.31 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1732757052; cv=none; b=FJ8ge0A3cocW1dAc3JsDTs3VxS4iBT3UoDX8a/Sf9gkMbh+Xex2WlIlSIcr3aizc02PUi10129gKX53BBYNb1kJchsdZ/S43zq8o7Y6nNadTExy5UY5mcNS+mqW8GECQuyL9ASLBcfXonEfE/jBhxIbu5ojcdi7jTgxfxo+mMFQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1732757052; c=relaxed/simple; bh=VyUoytH5yipFSmUpqy83K06XS9vJ1JN0+I7sEXvVzmQ=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=o74AopmZ0HndXZ/Q+iKR2Agd3Ns0Wsj4YuEmk4NHgxE8u/LvSMSa3Qmkkgr0U/rz4F85/3iGzuNzb8QbAdGWgYadglUNy4QRtXDYAShZwOcosshpa08oJ5OQVqrvP+cocGvYDTiJtw5fBSZBSw/3co3wQH7er+DVFnB3VUuq/5g= 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=jYgpzI4h; arc=none smtp.client-ip=79.135.106.31 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="jYgpzI4h" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pm.me; s=protonmail3; t=1732757042; x=1733016242; bh=7PHLPcTP4m+jx53byFzteomqcYUMdoh6jm3404BupMc=; 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=jYgpzI4hwpP14+hCZ4cYQ+UisQsml89NPx8eCKOFF1dI/aNY9Ledn7v1FdkekzVil OWQ8aUcIYyqiZQM/iWeEnu2vuF9Y/6vrJz+zWMszq86lQksWP80aWi46Ne1AJ3KzMx 7bmIwHp40x1XxzK8B7JbnwdVJ+4hU9l5mbJYuTP0ASsn0VsHgcY1ke7M7jmnyKSydV n+VnYncvPjXevBUw/ySvlvPREoAYez3sfkkNJQtgGekbM99PpuUfksuSQ6imcbePN6 +AAIByjrkSiWQ6VeYLsAkvkdT/erQdWT1GIWARR2JF7hrTX5y5cZyVgPlBkSBQaxQl XkmvDFdnZj+fQ== Date: Thu, 28 Nov 2024 01:23:57 +0000 To: dwarves@vger.kernel.org, acme@kernel.org From: Ihor Solodrai Cc: bpf@vger.kernel.org, alan.maguire@oracle.com, eddyz87@gmail.com, andrii@kernel.org, mykolal@fb.com Subject: [RFC PATCH 3/9] btf_encoder: separate elf function, saved function representations Message-ID: <20241128012341.4081072-4-ihor.solodrai@pm.me> In-Reply-To: <20241128012341.4081072-1-ihor.solodrai@pm.me> References: <20241128012341.4081072-1-ihor.solodrai@pm.me> Feedback-ID: 27520582:user:proton X-Pm-Message-ID: 65edc4c32db36b81e970ffbeba9582009362f06f Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-State: RFC From: Alan Maguire Have saved function representation point back at immutable ELF function table. This will make sharing the ELF function table across encoders easier. Simply accumulate saved functions for each encoder, and on completion combine them into a name-sorted list. Then carry out comparisons to check for inconsistent representations, skipping functions that are inconsistent in their representation. Thre is a small growth in maximum resident set size due to saving more functions; it grows from Maximum resident set size (kbytes): 701888 to: Maximum resident set size (kbytes): 704168 ...with this patch for -j1. Signed-off-by: Alan Maguire Signed-off-by: Ihor Solodrai --- btf_encoder.c | 297 +++++++++++++++++++++++++++----------------------- 1 file changed, 161 insertions(+), 136 deletions(-) diff --git a/btf_encoder.c b/btf_encoder.c index 01d7094..6114cc8 100644 --- a/btf_encoder.c +++ b/btf_encoder.c @@ -72,14 +72,15 @@ 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; uint16_t nr_parms; uint16_t nr_annots; - uint8_t initialized:1; 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; @@ -90,7 +91,6 @@ struct elf_function { char *alias; uint32_t addr; size_t prefixlen; - struct btf_encoder_func_state state; }; struct elf_secinfo { @@ -127,6 +127,7 @@ struct btf_encoder { struct elf_secinfo *secinfo; size_t seccnt; int encode_vars; + struct list_head func_states; struct { struct elf_function *entries; int allocated; @@ -695,25 +696,26 @@ static int32_t btf_encoder__tag_type(struct btf_encoder *encoder, uint32_t tag_t } static int32_t btf_encoder__add_func_proto(struct btf_encoder *encoder, struct ftype *ftype, - struct elf_function *func) + struct btf_encoder_func_state *state) { - struct btf *btf = encoder->btf; const struct btf_type *t; + struct btf *btf; struct parameter *param; uint16_t nr_params, param_idx; int32_t id, type_id; char tmp_name[KSYM_NAME_LEN]; const char *name; - struct btf_encoder_func_state *state; - assert(ftype != NULL || func != NULL); + assert(ftype != NULL || state != NULL); /* add btf_type for func_proto */ if (ftype) { + btf = encoder->btf; nr_params = ftype->nr_parms + (ftype->unspec_parms ? 1 : 0); type_id = btf_encoder__tag_type(encoder, ftype->tag.type); - } else if (func) { - state = &func->state; + } else if (state) { + encoder = state->encoder; + btf = state->encoder->btf; nr_params = state->nr_parms; type_id = state->ret_type_id; } else { @@ -1033,10 +1035,13 @@ static bool types__match(struct btf_encoder *encoder, return false; } -static bool funcs__match(struct btf_encoder *encoder, struct elf_function *func, - struct btf *btf1, struct btf_encoder_func_state *s1, - struct btf *btf2, struct btf_encoder_func_state *s2) +static bool funcs__match(struct btf_encoder_func_state *s1, + struct btf_encoder_func_state *s2) { + struct btf_encoder *encoder = s1->encoder; + struct elf_function *func = s1->elf; + struct btf *btf1 = s1->encoder->btf; + struct btf *btf2 = s2->encoder->btf; uint8_t i; if (s1->nr_parms != s2->nr_parms) { @@ -1074,8 +1079,7 @@ static bool funcs__match(struct btf_encoder *encoder, struct elf_function *func, static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct function *fn, struct elf_function *func) { - struct btf_encoder_func_state *existing = &func->state; - struct btf_encoder_func_state state = { 0 }; + struct btf_encoder_func_state *state = zalloc(sizeof(*state)); struct ftype *ftype = &fn->proto; struct btf *btf = encoder->btf; struct llvm_annotation *annot; @@ -1083,22 +1087,23 @@ static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct functi uint8_t param_idx = 0; int str_off, err = 0; - /* if already skipping this function, no need to proceed. */ - if (existing->unexpected_reg || existing->inconsistent_proto) - return 0; + if (!state) + return -ENOMEM; - state.nr_parms = ftype->nr_parms + (ftype->unspec_parms ? 1 : 0); - state.ret_type_id = ftype->tag.type == 0 ? 0 : encoder->type_id_off + ftype->tag.type; - if (state.nr_parms > 0) { - state.parms = zalloc(state.nr_parms * sizeof(*state.parms)); - if (!state.parms) { + state->encoder = encoder; + state->elf = func; + state->nr_parms = ftype->nr_parms + (ftype->unspec_parms ? 1 : 0); + state->ret_type_id = ftype->tag.type == 0 ? 0 : encoder->type_id_off + ftype->tag.type; + if (state->nr_parms > 0) { + state->parms = zalloc(state->nr_parms * sizeof(*state->parms)); + if (!state->parms) { err = -ENOMEM; goto out; } } - state.inconsistent_proto = ftype->inconsistent_proto; - state.unexpected_reg = ftype->unexpected_reg; - state.optimized_parms = ftype->optimized_parms; + state->inconsistent_proto = ftype->inconsistent_proto; + state->unexpected_reg = ftype->unexpected_reg; + state->optimized_parms = ftype->optimized_parms; ftype__for_each_parameter(ftype, param) { const char *name = parameter__name(param) ?: ""; @@ -1107,21 +1112,21 @@ static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct functi err = str_off; goto out; } - state.parms[param_idx].name_off = str_off; - state.parms[param_idx].type_id = param->tag.type == 0 ? 0 : - encoder->type_id_off + param->tag.type; + state->parms[param_idx].name_off = str_off; + state->parms[param_idx].type_id = param->tag.type == 0 ? 0 : + encoder->type_id_off + param->tag.type; param_idx++; } if (ftype->unspec_parms) - state.parms[param_idx].type_id = 0; + state->parms[param_idx].type_id = 0; list_for_each_entry(annot, &fn->annots, node) - state.nr_annots++; - if (state.nr_annots) { + state->nr_annots++; + if (state->nr_annots) { uint8_t idx = 0; - state.annots = zalloc(state.nr_annots * sizeof(*state.annots)); - if (!state.annots) { + state->annots = zalloc(state->nr_annots * sizeof(*state->annots)); + if (!state->annots) { err = -ENOMEM; goto out; } @@ -1131,46 +1136,24 @@ static int32_t btf_encoder__save_func(struct btf_encoder *encoder, struct functi err = str_off; goto out; } - state.annots[idx].value = str_off; - state.annots[idx].component_idx = annot->component_idx; + state->annots[idx].value = str_off; + state->annots[idx].component_idx = annot->component_idx; idx++; } } - state.initialized = 1; - - if (state.unexpected_reg) - btf_encoder__log_func_skip(encoder, func, - "unexpected register used for parameter\n"); - if (!existing->initialized) { - memcpy(existing, &state, sizeof(*existing)); - return 0; - } - - /* If saving and we find an existing entry, we want to merge - * observations across both functions, checking that the - * "seen optimized parameters", "inconsistent prototype" - * and "unexpected register" status is reflected in the - * func entry. - * If the entry is new, record encoder state required - * to add the local function later (encoder + type_id_off) - * such that we can add the function later. - */ - existing->optimized_parms |= state.optimized_parms; - existing->unexpected_reg |= state.unexpected_reg; - if (!existing->unexpected_reg && - !funcs__match(encoder, func, encoder->btf, &state, - encoder->btf, existing)) - existing->inconsistent_proto = 1; + list_add_tail(&state->node, &encoder->func_states); + return 0; out: - zfree(&state.annots); - zfree(&state.parms); + zfree(&state->annots); + zfree(&state->parms); + free(state); return err; } static int32_t btf_encoder__add_func(struct btf_encoder *encoder, - struct elf_function *func) + struct btf_encoder_func_state *state) { - struct btf_encoder_func_state *state = &func->state; + struct elf_function *func = state->elf; int btf_fnproto_id, btf_fn_id, tag_type_id = 0; int16_t component_idx = -1; const char *name; @@ -1178,7 +1161,7 @@ static int32_t btf_encoder__add_func(struct btf_encoder *encoder, char tmp_value[KSYM_NAME_LEN]; uint16_t idx; - btf_fnproto_id = btf_encoder__add_func_proto(encoder, NULL, func); + btf_fnproto_id = btf_encoder__add_func_proto(encoder, NULL, state); name = func->alias ?: func->name; if (btf_fnproto_id >= 0) btf_fn_id = btf_encoder__add_ref_type(encoder, BTF_KIND_FUNC, btf_fnproto_id, @@ -1216,62 +1199,6 @@ static int32_t btf_encoder__add_func(struct btf_encoder *encoder, return 0; } -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 btf_encoder_func_state *state = &func->state; - struct btf_encoder *other_encoder = NULL; - - 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. - */ - btf_encoders__for_each_encoder(other_encoder) { - struct elf_function *other_func; - struct btf_encoder_func_state *other_state; - uint8_t optimized, unexpected, inconsistent; - - if (other_encoder == encoder) - continue; - - other_func = &other_encoder->functions.entries[i]; - 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; - } - /* 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 (!encoder->skip_encoding_inconsistent_proto || - (!state->unexpected_reg && !state->inconsistent_proto)) { - if (btf_encoder__add_func(encoder, func)) - return -1; - } - state->processed = 1; - } - return 0; -} - static int functions_cmp(const void *_a, const void *_b) { const struct elf_function *a = _a; @@ -1282,16 +1209,16 @@ static int functions_cmp(const void *_a, const void *_b) * prefix len and prefix matches. */ if (a->prefixlen && a->prefixlen == b->prefixlen) - ret = strncmp(a->name, b->name, b->prefixlen); + ret = strncmp(a->name, b->name, a->prefixlen); else ret = strcmp(a->name, b->name); if (ret != 0) return ret; /* avoid address mismatch */ - if (a->addr != 0 && b->addr != 0) { - if (a->addr != b->addr) - return a->addr > b->addr ? 1 : -1; - } + if (a->addr != 0 && b->addr != 0) { + if (a->addr != b->addr) + return a->addr > b->addr ? 1 : -1; + } return 0; } @@ -1309,6 +1236,109 @@ static void *reallocarray_grow(void *ptr, int *nmemb, size_t size) return new; } +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; + + return functions_cmp((*a)->elf, (*b)->elf); +} + +static int saved_functions_combine(void *_a, void *_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, + max(a->elf->prefixlen, b->elf->prefixlen)); + if (ret != 0) + return ret; + optimized = a->optimized_parms | b->optimized_parms; + unexpected = a->unexpected_reg | b->unexpected_reg; + inconsistent = a->inconsistent_proto | b->inconsistent_proto; + if (!unexpected && !inconsistent && !funcs__match(a, b)) + inconsistent = 1; + a->optimized_parms = b->optimized_parms = optimized; + a->unexpected_reg = b->unexpected_reg = unexpected; + a->inconsistent_proto = b->inconsistent_proto = inconsistent; + + return 0; +} + +static void btf_encoder__delete_saved_funcs(struct btf_encoder *encoder) +{ + struct btf_encoder_func_state *pos, *s; + + list_for_each_entry_safe(pos, s, &encoder->func_states, node) { + list_del(&pos->node); + free(pos->parms); + free(pos->annots); + free(pos); + } +} + +static int btf_encoder__add_saved_funcs(struct btf_encoder *encoder) +{ + struct btf_encoder_func_state **saved_fns, *s; + struct btf_encoder *e = NULL; + int i = 0, j, nr_saved_fns = 0; + + /* Retrieve function states from each encoder, combine them + * and sort by name, addr. + */ + btf_encoders__for_each_encoder(e) { + list_for_each_entry(s, &e->func_states, node) + nr_saved_fns++; + } + /* Another thread already did this work */ + if (nr_saved_fns == 0) { + printf("nothing to do for encoder...\n"); + return 0; + } + + printf("got %d saved functions...\n", nr_saved_fns); + saved_fns = calloc(nr_saved_fns, sizeof(*saved_fns)); + btf_encoders__for_each_encoder(e) { + list_for_each_entry(s, &e->func_states, node) + saved_fns[i++] = s; + } + printf("added %d saved fns\n", i); + 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]; + + /* Compare across sorted functions that match by name/prefix; + * share inconsistent/unexpected reg state between them. + */ + j = i + 1; + + 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 + * 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 (!encoder->skip_encoding_inconsistent_proto || + (!state->unexpected_reg && !state->inconsistent_proto)) { + if (btf_encoder__add_func(state->encoder, state)) { + free(saved_fns); + return -1; + } + } + } + /* Now that we are done with function states, free them. */ + free(saved_fns); + btf_encoders__for_each_encoder(e) + btf_encoder__delete_saved_funcs(e); + return 0; +} + static int btf_encoder__collect_function(struct btf_encoder *encoder, GElf_Sym *sym) { struct elf_function *new; @@ -1346,6 +1376,8 @@ static int btf_encoder__collect_function(struct btf_encoder *encoder, GElf_Sym * encoder->functions.suffix_cnt++; encoder->functions.entries[encoder->functions.cnt].prefixlen = suffix - name; + } else { + encoder->functions.entries[encoder->functions.cnt].prefixlen = strlen(name); } encoder->functions.cnt++; return 0; @@ -2353,6 +2385,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) @@ -2437,16 +2470,8 @@ 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) @@ -2461,12 +2486,12 @@ void btf_encoder__delete(struct btf_encoder *encoder) 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.allocated = encoder->functions.cnt = 0; free(encoder->functions.entries); encoder->functions.entries = NULL; + btf_encoder__delete_saved_funcs(encoder); + free(encoder); }