From patchwork Wed Nov 1 15:04:01 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Masahiro Yamada X-Patchwork-Id: 160570 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:abcd:0:b0:403:3b70:6f57 with SMTP id f13csp486115vqx; Wed, 1 Nov 2023 08:05:35 -0700 (PDT) X-Google-Smtp-Source: AGHT+IF5WonUab+idszVhWOBktE+6nbpReha15nX+ZpLe22N5i8snEHAps2bTzLDWQG6/KslX51S X-Received: by 2002:a05:6a21:1509:b0:174:464:9def with SMTP id nq9-20020a056a21150900b0017404649defmr12743320pzb.62.1698851134916; Wed, 01 Nov 2023 08:05:34 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1698851134; cv=none; d=google.com; s=arc-20160816; b=DeUeP3o+HAQVCTOcS/SrkXSClkkFO/Nvna2xWc0yqb7mKIqwNrisJvp3hZQxskwnz6 CHNpKq/flheOhYzS5GCqzgpGYX0fgsfNBo//e24CkmJl5yEEyZAeuqHidFhMfNKq73zc bKwY/J85SktrhdaQ0B66HpXRwE7PbUu7Nnye+78WL0reL8jaAhN+Hy187QIT00RBPFEW w/XI1MwbXOveG7hvXVVsBCNFg2MR/kG2vDsoN9GOmkZ4UTxKQfFGl6hThjTRW4bCehdv YbGP99ELgno7ZYZDk2fvCwVkheAmk10S8l15PffODbsv8vwodVZG4qysW08884jAp4pO oktw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature; bh=cxmlDGFj0N4UHQuYP9fFKwseg0bW2GejAjjsZSpewOc=; fh=dBMhXJFA9J4pDfXGrZbkhy+Gp1pVbk3H3l2Zx64V9wM=; b=H52aDzk+IcoJ2u3xMMqQh43VI2RmEARy0Ta0ytaIfK/KOSRpiDDrd33d5TAv+Q+Vtc ycR9dwkh0Jin4cLT65DG36KxqO78rsMp2YD2svNPx/ND59y7QmhKPSWqj7bHg6CPeYrl 5wLQ68jjKd21O2U9FT5P1lnL6cb0Y7Tx05llQ3PLgtIdPpaZXuk72cKNiP4hwgHPt81e 9jjJpVcnebYtLqNl6d7ZTU4KorApQuIt/JZ1x4S0jRl18y9ZZZeMRxlwhHUpjYQr/t3f hl4Z6g0n5QVmmt+5qZLTbI38d2M6gEMjHX+V9I/Gv/Mqu6OutxvEh1akIpspCHUm7i5u 2nYQ== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=kHNj6pS4; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from lipwig.vger.email (lipwig.vger.email. [23.128.96.33]) by mx.google.com with ESMTPS id n19-20020a638f13000000b005b9083b81f5si44195pgd.487.2023.11.01.08.05.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 01 Nov 2023 08:05:34 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) client-ip=23.128.96.33; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=kHNj6pS4; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.33 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from out1.vger.email (depot.vger.email [IPv6:2620:137:e000::3:0]) by lipwig.vger.email (Postfix) with ESMTP id 26D1680CC21B; Wed, 1 Nov 2023 08:05:26 -0700 (PDT) X-Virus-Status: Clean X-Virus-Scanned: clamav-milter 0.103.10 at lipwig.vger.email Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232910AbjKAPFK (ORCPT + 35 others); Wed, 1 Nov 2023 11:05:10 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39994 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232591AbjKAPFE (ORCPT ); Wed, 1 Nov 2023 11:05:04 -0400 Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7EE3010C; Wed, 1 Nov 2023 08:04:59 -0700 (PDT) Received: by smtp.kernel.org (Postfix) with ESMTPSA id CA0BCC43215; Wed, 1 Nov 2023 15:04:57 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1698851099; bh=JtLodipaGPF999feXSGnDvTxAtoqNAWxEAUjQUNvakM=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=kHNj6pS4OyGwkRF8mHZhF+YVeLtrDGwcNAKX1Zwq7SVqBaUinKfojmeq61mmW93ue aVZXMQkUH5pLMuQ5Kaelo4ooNejJ4jksN2d+Eg+0ZScv15cLJtcyrPWqxeTVetNlMF 8UEea089U8sUyU2HgFFoW0N2fkE8oPSB/2a39oBZB+PAJbkaKQ/zAfsGkMOCWaGnBQ qAtFnwgPLInYKcwp/41z8I3GoQIioOh9eMbz337H/zRIWgMInDlVQ94hyP+irQNR3c L69698PAr+M/CkRp15c3q7x50/j2wAwzNnrWPFXHqiqFu1ZymFoUrrj/IQJwbeBQCn zId1tz02kA3sw== From: Masahiro Yamada To: linux-kbuild@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Greg Ungerer , Jack Brennen , Masahiro Yamada , Nathan Chancellor , Nick Desaulniers , Nicolas Schier Subject: [PATCH 4/7] modpost: introduce a filtering feature to symsearch Date: Thu, 2 Nov 2023 00:04:01 +0900 Message-Id: <20231101150404.754108-5-masahiroy@kernel.org> X-Mailer: git-send-email 2.40.1 In-Reply-To: <20231101150404.754108-1-masahiroy@kernel.org> References: <20231101150404.754108-1-masahiroy@kernel.org> MIME-Version: 1.0 X-Spam-Status: No, score=-1.6 required=5.0 tests=DKIMWL_WL_HIGH,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,MAILING_LIST_MULTI, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lipwig.vger.email Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-Greylist: Sender passed SPF test, not delayed by milter-greylist-4.6.4 (lipwig.vger.email [0.0.0.0]); Wed, 01 Nov 2023 08:05:26 -0700 (PDT) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1781374527444448402 X-GMAIL-MSGID: 1781374527444448402 If adjacent table entries have the same section index and address, symsearch_fixup() modifies the entries so the symbol lookup returns the first symbol entry in the original .symtab section, but it may not be the optimal result. Add the filter() callback for more flexible symbol selection. After the binary search is finished, a linear search begins to determine the best symbol. Typically, the one found in the first iteration is the closest, but the linear search continues as long as it sees another symbol on the same distance. In each iteration, filter() is called to determine if the current symbol should be taken. Here are some useful scenarios: - When multiple entries share the same section index and address, filter() can be used to break a tie. - When there is an unwanted symbol depending on the search context, filter() can return false to skip it. Currently, there is one hard-coded policy: if the target address falls perfectly in the middle of the two neighbors, the lower address is preferred. Let's move this preference to the filter function because it is not directly related to the binary search algorithm. This commit does not introduce any functional change, but more useful filtering policies will be added in subsequent commits. Signed-off-by: Masahiro Yamada --- scripts/mod/symsearch.c | 102 ++++++++++++++++++++++++++++++---------- 1 file changed, 77 insertions(+), 25 deletions(-) diff --git a/scripts/mod/symsearch.c b/scripts/mod/symsearch.c index 97566aee0979..4549c5b0bb81 100644 --- a/scripts/mod/symsearch.c +++ b/scripts/mod/symsearch.c @@ -5,6 +5,8 @@ * to a given address. */ +#include + #include "modpost.h" struct syminfo { @@ -142,17 +144,11 @@ void symsearch_finish(struct elf_info *elf) elf->symsearch = NULL; } -/* - * Find the syminfo which is in secndx and "nearest" to addr. - * allow_negative: allow returning a symbol whose address is > addr. - * min_distance: ignore symbols which are further away than this. - * - * Returns a pointer into the symbol table for success. - * Returns NULL if no legal symbol is found within the requested range. - */ -Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr, - unsigned int secndx, bool allow_negative, - Elf_Addr min_distance) +static Elf_Sym *symsearch_find(struct elf_info *elf, Elf_Addr addr, + unsigned int secndx, bool allow_negative, + Elf_Addr min_distance, + bool (*filter)(const Elf_Sym *, const Elf_Sym *, void *), + void *filter_data) { const struct syminfo *table = elf->symsearch->table; unsigned int table_size = elf->symsearch->table_size; @@ -178,22 +174,78 @@ Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr, * entry in the array which comes before target, including the * case where it perfectly matches the section and the address. * - * Note -- if the address we're looking up falls perfectly - * in the middle of two symbols, this is written to always - * prefer the symbol with the lower address. + * If there are multiple candidates, the filter() callback can be used + * to break a tie. filter() is provided with the current symbol and the + * best one so far. If it returns true, the current one is selected. + * Only a few iterations are expected, hence the linear search is fine. */ - Elf_Sym *result = NULL; + Elf_Addr distance; + Elf_Sym *best = NULL; + Elf_Sym *sym; + int i; - if (allow_negative && hi < table_size && - table[hi].section_index == secndx && - table[hi].addr - addr <= min_distance) { - min_distance = table[hi].addr - addr; - result = &elf->symtab_start[table[hi].symbol_index]; + /* Search to the left. */ + for (i = hi - 1; i >= 0; i--) { + if (table[i].section_index != secndx) + break; + + distance = addr - table[i].addr; + if (distance > min_distance) + break; + + sym = &elf->symtab_start[table[i].symbol_index]; + if (filter(sym, best, filter_data)) { + min_distance = distance; + best = sym; + } } - if (hi > 0 && - table[hi - 1].section_index == secndx && - addr - table[hi - 1].addr <= min_distance) { - result = &elf->symtab_start[table[hi - 1].symbol_index]; + + if (!allow_negative) + return best; + + /* Search to the right if allow_negative is true. */ + for (i = hi; i < table_size; i++) { + if (table[i].section_index != secndx) + break; + + distance = table[i].addr - addr; + if (distance > min_distance) + break; + + sym = &elf->symtab_start[table[i].symbol_index]; + if (filter(sym, best, filter_data)) { + min_distance = distance; + best = sym; + } } - return result; + + return best; +} + +/* Return true if sym1 is preferred over sym2. */ +static bool symsearch_nearest_filter(const Elf_Sym *sym1, const Elf_Sym *sym2, + void *data) +{ + /* If sym2 is NULL, this is the first occurrence, always take it. */ + if (sym2 == NULL) + return true; + + /* Prefer lower address. */ + return sym1->st_value < sym2->st_value; +} + +/* + * Find the syminfo which is in secndx and "nearest" to addr. + * allow_negative: allow returning a symbol whose address is > addr. + * min_distance: ignore symbols which are further away than this. + * + * Returns a pointer into the symbol table for success. + * Returns NULL if no legal symbol is found within the requested range. + */ +Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr, + unsigned int secndx, bool allow_negative, + Elf_Addr min_distance) +{ + return symsearch_find(elf, addr, secndx, allow_negative, min_distance, + symsearch_nearest_filter, NULL); }