From patchwork Thu Sep 8 13:09:30 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12970054 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5FCFBC38145 for ; Thu, 8 Sep 2022 13:10:48 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232199AbiIHNKr (ORCPT ); Thu, 8 Sep 2022 09:10:47 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35130 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232203AbiIHNKd (ORCPT ); Thu, 8 Sep 2022 09:10:33 -0400 Received: from szxga08-in.huawei.com (szxga08-in.huawei.com [45.249.212.255]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 7BDAFBF61; Thu, 8 Sep 2022 06:10:12 -0700 (PDT) Received: from dggpemm500020.china.huawei.com (unknown [172.30.72.53]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4MNfWw45tNz14QMJ; Thu, 8 Sep 2022 21:06:20 +0800 (CST) Received: from dggpemm500006.china.huawei.com (7.185.36.236) by dggpemm500020.china.huawei.com (7.185.36.49) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:10 +0800 Received: from thunder-town.china.huawei.com (10.174.178.55) by dggpemm500006.china.huawei.com (7.185.36.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:09 +0800 From: Zhen Lei To: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Petr Mladek , Joe Lawrence , , , Masahiro Yamada , Alexei Starovoitov , Jiri Olsa , Kees Cook , Andrew Morton , "Luis Chamberlain" , CC: Zhen Lei Subject: [PATCH 1/7] scripts/kallsyms: don't compress symbol type when CONFIG_KALLSYMS_ALL=y Date: Thu, 8 Sep 2022 21:09:30 +0800 Message-ID: <20220908130936.674-2-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220908130936.674-1-thunder.leizhen@huawei.com> References: <20220908130936.674-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Currently, to search for a symbol, we need to expand the symbols in 'kallsyms_names' one by one, and then use the expanded string for comparison. This is very slow. In fact, we can first compress the name being looked up and then use it for comparison when traversing 'kallsyms_names'. This increases the size of 'kallsyms_names'. About 48KiB, 2.67%, on x86 with defconfig. Before: kallsyms_num_syms=131392, sizeof(kallsyms_names)=1823659 After : kallsyms_num_syms=131392, sizeof(kallsyms_names)=1872418 However, if CONFIG_KALLSYMS_ALL is not set, the size of 'kallsyms_names' does not change. Signed-off-by: Zhen Lei --- scripts/kallsyms.c | 15 ++++++++++++--- 1 file changed, 12 insertions(+), 3 deletions(-) diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index f18e6dfc68c5839..ab6fe7cd014efd1 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -60,6 +60,7 @@ static unsigned int table_size, table_cnt; static int all_symbols; static int absolute_percpu; static int base_relative; +static int sym_start_idx; static int token_profit[0x10000]; @@ -511,7 +512,7 @@ static void learn_symbol(const unsigned char *symbol, int len) { int i; - for (i = 0; i < len - 1; i++) + for (i = sym_start_idx; i < len - 1; i++) token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++; } @@ -520,7 +521,7 @@ static void forget_symbol(const unsigned char *symbol, int len) { int i; - for (i = 0; i < len - 1; i++) + for (i = sym_start_idx; i < len - 1; i++) token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--; } @@ -538,7 +539,7 @@ static unsigned char *find_token(unsigned char *str, int len, { int i; - for (i = 0; i < len - 1; i++) { + for (i = sym_start_idx; i < len - 1; i++) { if (str[i] == token[0] && str[i+1] == token[1]) return &str[i]; } @@ -780,6 +781,14 @@ int main(int argc, char **argv) } else if (argc != 1) usage(); + /* + * Skip the symbol type, do not compress it to optimize the performance + * of finding or traversing symbols in kernel, this is good for modules + * such as livepatch. + */ + if (all_symbols) + sym_start_idx = 1; + read_map(stdin); shrink_table(); if (absolute_percpu) From patchwork Thu Sep 8 13:09:31 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12970055 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 2655FC6FA8A for ; Thu, 8 Sep 2022 13:10:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232237AbiIHNKs (ORCPT ); Thu, 8 Sep 2022 09:10:48 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:36990 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232245AbiIHNKe (ORCPT ); Thu, 8 Sep 2022 09:10:34 -0400 Received: from szxga08-in.huawei.com (szxga08-in.huawei.com [45.249.212.255]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EB32F5FF69; Thu, 8 Sep 2022 06:10:12 -0700 (PDT) Received: from dggpemm500022.china.huawei.com (unknown [172.30.72.53]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4MNfWx1dTnz14QQB; Thu, 8 Sep 2022 21:06:21 +0800 (CST) Received: from dggpemm500006.china.huawei.com (7.185.36.236) by dggpemm500022.china.huawei.com (7.185.36.162) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:11 +0800 Received: from thunder-town.china.huawei.com (10.174.178.55) by dggpemm500006.china.huawei.com (7.185.36.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:10 +0800 From: Zhen Lei To: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Petr Mladek , Joe Lawrence , , , Masahiro Yamada , Alexei Starovoitov , Jiri Olsa , Kees Cook , Andrew Morton , "Luis Chamberlain" , CC: Zhen Lei Subject: [PATCH 2/7] scripts/kallsyms: rename build_initial_tok_table() Date: Thu, 8 Sep 2022 21:09:31 +0800 Message-ID: <20220908130936.674-3-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220908130936.674-1-thunder.leizhen@huawei.com> References: <20220908130936.674-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Except for the function build_initial_tok_table(), no token abbreviation is used elsewhere. $ cat scripts/kallsyms.c | grep tok | wc -l 33 $ cat scripts/kallsyms.c | grep token | wc -l 31 Here, it would be clearer to use the full name. Signed-off-by: Zhen Lei --- scripts/kallsyms.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index ab6fe7cd014efd1..678ebe7d4c1cc38 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -526,7 +526,7 @@ static void forget_symbol(const unsigned char *symbol, int len) } /* do the initial token count */ -static void build_initial_tok_table(void) +static void build_initial_token_table(void) { unsigned int i; @@ -651,7 +651,7 @@ static void insert_real_symbols_in_table(void) static void optimize_token_table(void) { - build_initial_tok_table(); + build_initial_token_table(); insert_real_symbols_in_table(); From patchwork Thu Sep 8 13:09:32 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12970057 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id C40CFC6FA82 for ; Thu, 8 Sep 2022 13:10:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232114AbiIHNKt (ORCPT ); Thu, 8 Sep 2022 09:10:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35530 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232207AbiIHNKf (ORCPT ); Thu, 8 Sep 2022 09:10:35 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1842A65248; Thu, 8 Sep 2022 06:10:13 -0700 (PDT) Received: from dggpemm500023.china.huawei.com (unknown [172.30.72.55]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MNfYN450QznV70; Thu, 8 Sep 2022 21:07:36 +0800 (CST) Received: from dggpemm500006.china.huawei.com (7.185.36.236) by dggpemm500023.china.huawei.com (7.185.36.83) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:11 +0800 Received: from thunder-town.china.huawei.com (10.174.178.55) by dggpemm500006.china.huawei.com (7.185.36.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:10 +0800 From: Zhen Lei To: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Petr Mladek , Joe Lawrence , , , Masahiro Yamada , Alexei Starovoitov , Jiri Olsa , Kees Cook , Andrew Morton , "Luis Chamberlain" , CC: Zhen Lei Subject: [PATCH 3/7] kallsyms: Adjust the types of some local variables Date: Thu, 8 Sep 2022 21:09:32 +0800 Message-ID: <20220908130936.674-4-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220908130936.674-1-thunder.leizhen@huawei.com> References: <20220908130936.674-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: The type of kallsyms_num_syms is 'unsigned int', adjust the type of local variables associated with it for indexing, so that their types are consistent. Signed-off-by: Zhen Lei --- kernel/kallsyms.c | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 3e7e2c2ad2f75ef..9dd4774b6c6edf6 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -190,8 +190,7 @@ static bool cleanup_symbol_name(char *s) unsigned long kallsyms_lookup_name(const char *name) { char namebuf[KSYM_NAME_LEN]; - unsigned long i; - unsigned int off; + unsigned int i, off; /* Skip the search for empty string. */ if (!*name) @@ -218,8 +217,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *, void *data) { char namebuf[KSYM_NAME_LEN]; - unsigned long i; - unsigned int off; + unsigned int i, off; int ret; for (i = 0, off = 0; i < kallsyms_num_syms; i++) { @@ -237,7 +235,7 @@ static unsigned long get_symbol_pos(unsigned long addr, unsigned long *offset) { unsigned long symbol_start = 0, symbol_end = 0; - unsigned long i, low, high, mid; + unsigned int i, low, high, mid; /* This kernel should never had been booted. */ if (!IS_ENABLED(CONFIG_KALLSYMS_BASE_RELATIVE)) From patchwork Thu Sep 8 13:09:33 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12970058 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id E085DC6FA90 for ; Thu, 8 Sep 2022 13:10:51 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232280AbiIHNKu (ORCPT ); Thu, 8 Sep 2022 09:10:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:35532 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232249AbiIHNKf (ORCPT ); Thu, 8 Sep 2022 09:10:35 -0400 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 40A1065838; Thu, 8 Sep 2022 06:10:14 -0700 (PDT) Received: from dggpemm500024.china.huawei.com (unknown [172.30.72.56]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4MNfZ83pz5zHnjP; Thu, 8 Sep 2022 21:08:16 +0800 (CST) Received: from dggpemm500006.china.huawei.com (7.185.36.236) by dggpemm500024.china.huawei.com (7.185.36.203) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:12 +0800 Received: from thunder-town.china.huawei.com (10.174.178.55) by dggpemm500006.china.huawei.com (7.185.36.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:11 +0800 From: Zhen Lei To: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Petr Mladek , Joe Lawrence , , , Masahiro Yamada , Alexei Starovoitov , Jiri Olsa , Kees Cook , Andrew Morton , "Luis Chamberlain" , CC: Zhen Lei Subject: [PATCH 4/7] kallsyms: Improve the performance of kallsyms_lookup_name() Date: Thu, 8 Sep 2022 21:09:33 +0800 Message-ID: <20220908130936.674-5-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220908130936.674-1-thunder.leizhen@huawei.com> References: <20220908130936.674-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Currently, to search for a symbol, we need to expand the symbols in 'kallsyms_names' one by one, and then use the expanded string for comparison. This is very slow. In fact, we can first compress the name being looked up and then use it for comparison when traversing 'kallsyms_names'. This requires CONFIG_KALLSYMS_ALL=y. The pseudo code of the test case is as follows: static int stat_find_name(...) { start = sched_clock(); (void)kallsyms_lookup_name(name); end = sched_clock(); //Update min, max, cnt, sum } /* * Traverse all symbols in sequence and collect statistics on the time * taken by kallsyms_lookup_name() to lookup each symbol. */ kallsyms_on_each_symbol(stat_find_name, NULL); The test results are as follows (twice): After : min=7106, max= 564822, cnt=131392, avg= 247965 After : min=6971, max= 557676, cnt=131393, avg= 248350 Before: min= 682, max=23045734, cnt=131392, avg=6966802 Before: min= 647, max=17676731, cnt=131392, avg=6965314 The average time consumed is only 3.56% and the maximum time consumed is only 2.76% of the time consumed before optimization. Signed-off-by: Zhen Lei --- kernel/kallsyms.c | 86 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 86 insertions(+) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 9dd4774b6c6edf6..e1cd7305aa5f548 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -87,6 +87,72 @@ static unsigned int kallsyms_expand_symbol(unsigned int off, return off; } +static int kallsyms_name_to_tokens(const char *name, char *buf) +{ + int i, j, k, n; + int len, token_len; + const char *token; + unsigned char token_idx[KSYM_NAME_LEN]; + unsigned char token_bak[KSYM_NAME_LEN]; + + if (!IS_ENABLED(CONFIG_KALLSYMS_ALL)) + return 0; + + /* + * n, number of tokens in the string name. + * token_idx[i], the start index of the ith token. + * token_idx[n] is used to calculate the length of the last token. + */ + n = strlen(name); + if (n >= KSYM_NAME_LEN) + return 0; + for (i = 0; i <= n; i++) + token_idx[i] = (unsigned char)i; + + /* + * For tokens whose token_len >= 2, a larger index value indicates + * a higher occurrence frequency. See scripts/kallsyms.c + */ + for (i = 255; i >= 0; i--) { + token = &kallsyms_token_table[kallsyms_token_index[i]]; + token_len = strlen(token); + if (token_len <= 1) + continue; + + /* + * Find and merge two tokens into one. + * + * |<-- new_token -->| + * | token1 | token2 | + * token_idx[]: j j+1 j+2 + * + */ + for (j = 0; j < n - 1; j++) { + len = token_idx[j + 2] - token_idx[j]; + if (len == token_len && + !strncmp(name + token_idx[j], token, len)) { + token_bak[token_idx[j]] = (unsigned char)i; + for (k = j + 1; k < n; k++) + token_idx[k] = token_idx[k + 1]; + n--; + } + } + } + + for (j = 0; j < n; j++) { + len = token_idx[j + 1] - token_idx[j]; + if (len <= 1) { + buf[j] = name[token_idx[j]]; + continue; + } + + buf[j] = token_bak[token_idx[j]]; + } + buf[n] = 0; + + return n; +} + /* * Get symbol type information. This is encoded as a single char at the * beginning of the symbol name. @@ -191,11 +257,29 @@ unsigned long kallsyms_lookup_name(const char *name) { char namebuf[KSYM_NAME_LEN]; unsigned int i, off; + int len; /* Skip the search for empty string. */ if (!*name) return 0; + len = kallsyms_name_to_tokens(name, namebuf); + if (!len) + goto slow_path; + + for (i = 0, off = 0; i < kallsyms_num_syms; i++) { + if (kallsyms_names[off] == len + 1 && + !memcmp(&kallsyms_names[off + 2], namebuf, len)) { + return kallsyms_sym_address(i); + } + + off += kallsyms_names[off] + 1; + } + + if (!IS_ENABLED(CONFIG_LTO_CLANG)) + goto module_lookup; + +slow_path: for (i = 0, off = 0; i < kallsyms_num_syms; i++) { off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); @@ -205,6 +289,8 @@ unsigned long kallsyms_lookup_name(const char *name) if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0) return kallsyms_sym_address(i); } + +module_lookup: return module_kallsyms_lookup_name(name); } From patchwork Thu Sep 8 13:09:34 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12970059 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 275C0C6FA8B for ; Thu, 8 Sep 2022 13:10:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232250AbiIHNKu (ORCPT ); Thu, 8 Sep 2022 09:10:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39034 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232251AbiIHNKf (ORCPT ); Thu, 8 Sep 2022 09:10:35 -0400 Received: from szxga08-in.huawei.com (szxga08-in.huawei.com [45.249.212.255]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BDDB9719A7; Thu, 8 Sep 2022 06:10:15 -0700 (PDT) Received: from dggpemm500020.china.huawei.com (unknown [172.30.72.54]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4MNfX01FB1z14QQD; Thu, 8 Sep 2022 21:06:24 +0800 (CST) Received: from dggpemm500006.china.huawei.com (7.185.36.236) by dggpemm500020.china.huawei.com (7.185.36.49) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:13 +0800 Received: from thunder-town.china.huawei.com (10.174.178.55) by dggpemm500006.china.huawei.com (7.185.36.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:12 +0800 From: Zhen Lei To: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Petr Mladek , Joe Lawrence , , , Masahiro Yamada , Alexei Starovoitov , Jiri Olsa , Kees Cook , Andrew Morton , "Luis Chamberlain" , CC: Zhen Lei Subject: [PATCH 5/7] kallsyms: Add helper kallsyms_on_each_match_symbol() Date: Thu, 8 Sep 2022 21:09:34 +0800 Message-ID: <20220908130936.674-6-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220908130936.674-1-thunder.leizhen@huawei.com> References: <20220908130936.674-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Function kallsyms_on_each_symbol() traverses all symbols and submits each symbol to the hook 'fn' for judgment and processing. For some cases, the hook actually only handles the matched symbol, such as livepatch. So that, we can first compress the name being looked up and then use it for comparison when traversing 'kallsyms_names', this greatly reduces the time consumed by traversing. This requires CONFIG_KALLSYMS_ALL=y, so that scripts/kallsyms does not compress that type character of each symbol. If CONFIG_KALLSYMS_ALL=n, the traversal of symbols is rolled back to the mode before optimization. The pseudo code of the test case is as follows: static int tst_find(void *data, const char *name, struct module *mod, unsigned long addr) { if (strcmp(name, "vmap") == 0) *(unsigned long *)data = addr; return 0; } static int tst_match(void *data, unsigned long addr) { *(unsigned long *)data = addr; return 0; } start = sched_clock(); kallsyms_on_each_match_symbol(tst_match, "vmap", &addr); end = sched_clock(); start = sched_clock(); kallsyms_on_each_symbol(tst_find, &addr); end = sched_clock(); The test results are as follows (twice): kallsyms_on_each_match_symbol: 1058511, 1079288 kallsyms_on_each_symbol : 26097313, 24765180 kallsyms_on_each_match_symbol() consumes only 4.2% of kallsyms_on_each_symbol()'s time. Signed-off-by: Zhen Lei --- include/linux/kallsyms.h | 8 ++++++++ kernel/kallsyms.c | 41 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 49 insertions(+) diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h index ad39636e0c3f122..f9f2cc084cab16b 100644 --- a/include/linux/kallsyms.h +++ b/include/linux/kallsyms.h @@ -69,6 +69,8 @@ static inline void *dereference_symbol_descriptor(void *ptr) int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *, unsigned long), void *data); +extern int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long), + const char *name, void *data); /* Lookup the address for a symbol. Returns 0 if not found. */ unsigned long kallsyms_lookup_name(const char *name); @@ -168,6 +170,12 @@ static inline int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct { return -EOPNOTSUPP; } + +static inline int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long), + const char *name, void *data) +{ + return -EOPNOTSUPP; +} #endif /*CONFIG_KALLSYMS*/ static inline void print_ip_sym(const char *loglvl, unsigned long ip) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index e1cd7305aa5f548..9816a0ac30c8c48 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -316,6 +316,47 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *, return 0; } +int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long), + const char *name, void *data) +{ + unsigned int i, off; + int len, ret; + char namebuf[KSYM_NAME_LEN]; + + len = kallsyms_name_to_tokens(name, namebuf); + if (!len) + goto slow_path; + + for (i = 0, off = 0; i < kallsyms_num_syms; i++) { + if ((i & 0xfff) == 0) + cond_resched(); + + if ((kallsyms_names[off] == len + 1) && + !memcmp(&kallsyms_names[off + 2], namebuf, len)) { + ret = fn(data, kallsyms_sym_address(i)); + if (ret != 0) + return ret; + cond_resched(); + } + off += kallsyms_names[off] + 1; + } + + return 0; + +slow_path: + for (i = 0, off = 0; i < kallsyms_num_syms; i++) { + off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); + if (!strcmp(name, namebuf)) { + ret = fn(data, kallsyms_sym_address(i)); + if (ret != 0) + return ret; + } + cond_resched(); + } + + return 0; +} + static unsigned long get_symbol_pos(unsigned long addr, unsigned long *symbolsize, unsigned long *offset) From patchwork Thu Sep 8 13:09:35 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12970060 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6F80FC6FA94 for ; Thu, 8 Sep 2022 13:10:53 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232257AbiIHNKw (ORCPT ); Thu, 8 Sep 2022 09:10:52 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37018 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232253AbiIHNKf (ORCPT ); Thu, 8 Sep 2022 09:10:35 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id BDFC6719B6; Thu, 8 Sep 2022 06:10:15 -0700 (PDT) Received: from dggpemm500021.china.huawei.com (unknown [172.30.72.53]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MNfYQ4V98znV72; Thu, 8 Sep 2022 21:07:38 +0800 (CST) Received: from dggpemm500006.china.huawei.com (7.185.36.236) by dggpemm500021.china.huawei.com (7.185.36.109) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:13 +0800 Received: from thunder-town.china.huawei.com (10.174.178.55) by dggpemm500006.china.huawei.com (7.185.36.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:13 +0800 From: Zhen Lei To: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Petr Mladek , Joe Lawrence , , , Masahiro Yamada , Alexei Starovoitov , Jiri Olsa , Kees Cook , Andrew Morton , "Luis Chamberlain" , CC: Zhen Lei Subject: [PATCH 6/7] livepatch: Use kallsyms_on_each_match_symbol() to improve performance Date: Thu, 8 Sep 2022 21:09:35 +0800 Message-ID: <20220908130936.674-7-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220908130936.674-1-thunder.leizhen@huawei.com> References: <20220908130936.674-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Based on the test results of kallsyms_on_each_match_symbol() and kallsyms_on_each_symbol(), this can reduce the performance overhead by approximately 95%, if CONFIG_KALLSYMS_ALL=y. Signed-off-by: Zhen Lei --- kernel/livepatch/core.c | 20 +++++++++++++++++++- 1 file changed, 19 insertions(+), 1 deletion(-) diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c index 42f7e716d56bf72..31b57ccf908017e 100644 --- a/kernel/livepatch/core.c +++ b/kernel/livepatch/core.c @@ -153,6 +153,24 @@ static int klp_find_callback(void *data, const char *name, return 0; } +static int klp_match_callback(void *data, unsigned long addr) +{ + struct klp_find_arg *args = data; + + args->addr = addr; + args->count++; + + /* + * Finish the search when the symbol is found for the desired position + * or the position is not defined for a non-unique symbol. + */ + if ((args->pos && (args->count == args->pos)) || + (!args->pos && (args->count > 1))) + return 1; + + return 0; +} + static int klp_find_object_symbol(const char *objname, const char *name, unsigned long sympos, unsigned long *addr) { @@ -167,7 +185,7 @@ static int klp_find_object_symbol(const char *objname, const char *name, if (objname) module_kallsyms_on_each_symbol(klp_find_callback, &args); else - kallsyms_on_each_symbol(klp_find_callback, &args); + kallsyms_on_each_match_symbol(klp_match_callback, name, &args); /* * Ensure an address was found. If sympos is 0, ensure symbol is unique; From patchwork Thu Sep 8 13:09:36 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12970061 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8BDEBC6FA82 for ; Thu, 8 Sep 2022 13:10:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S232286AbiIHNKx (ORCPT ); Thu, 8 Sep 2022 09:10:53 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:39064 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S232200AbiIHNKf (ORCPT ); Thu, 8 Sep 2022 09:10:35 -0400 Received: from szxga02-in.huawei.com (szxga02-in.huawei.com [45.249.212.188]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 630CD76765; Thu, 8 Sep 2022 06:10:16 -0700 (PDT) Received: from dggpemm500022.china.huawei.com (unknown [172.30.72.57]) by szxga02-in.huawei.com (SkyGuard) with ESMTP id 4MNfXF6P81zjX3G; Thu, 8 Sep 2022 21:06:37 +0800 (CST) Received: from dggpemm500006.china.huawei.com (7.185.36.236) by dggpemm500022.china.huawei.com (7.185.36.162) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:14 +0800 Received: from thunder-town.china.huawei.com (10.174.178.55) by dggpemm500006.china.huawei.com (7.185.36.236) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2375.24; Thu, 8 Sep 2022 21:10:13 +0800 From: Zhen Lei To: Josh Poimboeuf , Jiri Kosina , Miroslav Benes , Petr Mladek , Joe Lawrence , , , Masahiro Yamada , Alexei Starovoitov , Jiri Olsa , Kees Cook , Andrew Morton , "Luis Chamberlain" , CC: Zhen Lei Subject: [PATCH 7/7] livepatch: Improve the search performance of module_kallsyms_on_each_symbol() Date: Thu, 8 Sep 2022 21:09:36 +0800 Message-ID: <20220908130936.674-8-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220908130936.674-1-thunder.leizhen@huawei.com> References: <20220908130936.674-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Currently we traverse all symbols of all modules to find the specified function for the specified module. But in reality, we just need to find the given module and then traverse all the symbols in it. In order to achieve this purpose, split the call to hook 'fn' into two phases: 1. Finds the given module. Pass pointer 'mod'. Hook 'fn' directly returns the comparison result of the module name without comparing the function name. 2. Finds the given function in that module. Pass pointer 'mod = NULL'. Hook 'fn' skip the comparison of module name and directly compare function names. Phase1: mod1-->mod2..(subsequent modules do not need to be compared) | Phase2: -->f1-->f2-->f3 Signed-off-by: Zhen Lei --- kernel/livepatch/core.c | 7 ++----- kernel/module/kallsyms.c | 13 ++++++++++++- 2 files changed, 14 insertions(+), 6 deletions(-) diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c index 31b57ccf908017e..98e23137e4133bc 100644 --- a/kernel/livepatch/core.c +++ b/kernel/livepatch/core.c @@ -130,15 +130,12 @@ static int klp_find_callback(void *data, const char *name, { struct klp_find_arg *args = data; - if ((mod && !args->objname) || (!mod && args->objname)) - return 0; + if (mod) + return strcmp(args->objname, mod->name); if (strcmp(args->name, name)) return 0; - if (args->objname && strcmp(args->objname, mod->name)) - return 0; - args->addr = addr; args->count++; diff --git a/kernel/module/kallsyms.c b/kernel/module/kallsyms.c index f5c5c9175333df7..b033613e6c7e3bb 100644 --- a/kernel/module/kallsyms.c +++ b/kernel/module/kallsyms.c @@ -510,6 +510,11 @@ int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *, if (mod->state == MODULE_STATE_UNFORMED) continue; + /* check mod->name first */ + ret = fn(data, NULL, mod, 0); + if (ret) + continue; + /* Use rcu_dereference_sched() to remain compliant with the sparse tool */ preempt_disable(); kallsyms = rcu_dereference_sched(mod->kallsyms); @@ -522,10 +527,16 @@ int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *, continue; ret = fn(data, kallsyms_symbol_name(kallsyms, i), - mod, kallsyms_symbol_value(sym)); + NULL, kallsyms_symbol_value(sym)); if (ret != 0) goto out; } + + /* + * The given module is found, the subsequent modules do not + * need to be compared. + */ + break; } out: mutex_unlock(&module_mutex);