From patchwork Sat Sep 24 12:20:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987603 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 C6D72C32771 for ; Sat, 24 Sep 2022 12:22:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233410AbiIXMWv (ORCPT ); Sat, 24 Sep 2022 08:22:51 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:54986 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S231389AbiIXMWu (ORCPT ); Sat, 24 Sep 2022 08:22:50 -0400 Received: from szxga02-in.huawei.com (szxga02-in.huawei.com [45.249.212.188]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5390FFDE; Sat, 24 Sep 2022 05:22:50 -0700 (PDT) Received: from dggpemm500023.china.huawei.com (unknown [172.30.72.53]) by szxga02-in.huawei.com (SkyGuard) with ESMTP id 4MZShr2Dq5zHtkL; Sat, 24 Sep 2022 20:18:04 +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.31; Sat, 24 Sep 2022 20:22:48 +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.31; Sat, 24 Sep 2022 20:22:47 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 01/11] scripts/kallsyms: rename build_initial_tok_table() Date: Sat, 24 Sep 2022 20:20:41 +0800 Message-ID: <20220924122051.362-2-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) 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 Reviewed-by: Petr Mladek --- scripts/kallsyms.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index f18e6dfc68c5839..8caccc8f4a23703 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -525,7 +525,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; @@ -650,7 +650,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 Sat Sep 24 12:20:42 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987605 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 5B37AC07E9D for ; Sat, 24 Sep 2022 12:22:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233821AbiIXMWy (ORCPT ); Sat, 24 Sep 2022 08:22:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55008 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233719AbiIXMWx (ORCPT ); Sat, 24 Sep 2022 08:22:53 -0400 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 71725FDE; Sat, 24 Sep 2022 05:22:51 -0700 (PDT) Received: from dggpemm500024.china.huawei.com (unknown [172.30.72.55]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4MZSlm4qgRzHpv3; Sat, 24 Sep 2022 20:20:36 +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.31; Sat, 24 Sep 2022 20:22:49 +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.31; Sat, 24 Sep 2022 20:22:48 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 02/11] scripts/kallsyms: don't compress symbol types Date: Sat, 24 Sep 2022 20:20:42 +0800 Message-ID: <20220924122051.362-3-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) 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. Because we do not know the symbol type, and the symbol type may be combined with the following characters to form a token. So if we don't compress the symbol type, we can first compress the searched symbol and then make a quick comparison based on the compressed length and content. In this way, for entries with mismatched lengths, there is no need to expand and compare strings. And for those matching lengths, there's no need to expand the symbol. This saves a lot of time. According to my test results, the average performance of kallsyms_lookup_name() can be improved by 20 to 30 times. Of course, because the symbol type is forcibly not compressed, the compression rate also decreases. Here are the test results with defconfig: arm64: <<<<<< --------------------------------------------------------------- | ALL | nr_symbols | compressed size | original size | ratio(%) | -----|---------------------------------------------------------| Before | Y | 174094 | 1884938 | 3750653 | 50.25 | After | Y | 174099 | 1960154 | 3750756 | 52.26 | Before | N | 61744 | 725507 | 1222737 | 59.33 | After | N | 61747 | 745733 | 1222801 | 60.98 | --------------------------------------------------------------- The memory overhead is increased by: 73.5KiB and 4.0% if CONFIG_KALLSYMS_ALL=y. 19.8KiB and 2.8% if CONFIG_KALLSYMS_ALL=n. x86: <<<<<<<< --------------------------------------------------------------- | ALL | nr_symbols | compressed size | original size | ratio(%) | -----|---------------------------------------------------------| Before | Y | 131415 | 1697542 | 3161216 | 53.69 | After | Y | 131540 | 1747769 | 3163933 | 55.24 | Before | N | 60695 | 737627 | 1283046 | 57.49 | After | N | 60699 | 754797 | 1283149 | 58.82 | --------------------------------------------------------------- The memory overhead is increased by: 49.0KiB and 3.0% if CONFIG_KALLSYMS_ALL=y. 16.8KiB and 2.3% if CONFIG_KALLSYMS_ALL=n. This additional memory overhead is worth it compared to the performance improvement, I think. Let's use an extra field to hold type and eventually put it together with name in write_src(). Signed-off-by: Zhen Lei --- scripts/kallsyms.c | 39 +++++++++++++++++++++++---------------- 1 file changed, 23 insertions(+), 16 deletions(-) diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index 8caccc8f4a23703..296277128d450ff 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -34,6 +34,7 @@ struct sym_entry { unsigned int len; unsigned int start_pos; unsigned int percpu_absolute; + unsigned char type; unsigned char sym[]; }; @@ -77,7 +78,7 @@ static void usage(void) static char *sym_name(const struct sym_entry *s) { - return (char *)s->sym + 1; + return (char *)s->sym; } static bool is_ignored_symbol(const char *name, char type) @@ -227,11 +228,7 @@ static struct sym_entry *read_symbol(FILE *in) check_symbol_range(name, addr, text_ranges, ARRAY_SIZE(text_ranges)); check_symbol_range(name, addr, &percpu_range, 1); - /* include the type field in the symbol name, so that it gets - * compressed together */ - - len = strlen(name) + 1; - + len = strlen(name); sym = malloc(sizeof(*sym) + len + 1); if (!sym) { fprintf(stderr, "kallsyms failure: " @@ -240,7 +237,7 @@ static struct sym_entry *read_symbol(FILE *in) } sym->addr = addr; sym->len = len; - sym->sym[0] = type; + sym->type = type; strcpy(sym_name(sym), name); sym->percpu_absolute = 0; @@ -471,12 +468,18 @@ static void write_src(void) if ((i & 0xFF) == 0) markers[i >> 8] = off; - printf("\t.byte 0x%02x", table[i]->len); + /* + * Store the symbol type togerher with symbol name. + * It helps to reduce the size. + */ + printf("\t.byte 0x%02x", table[i]->len + 1); + printf(", 0x%02x", table[i]->type); for (k = 0; k < table[i]->len; k++) printf(", 0x%02x", table[i]->sym[k]); printf("\n"); - off += table[i]->len + 1; + /* fields 'len' and 'type' occupy one byte each */ + off += table[i]->len + 1 + 1; } printf("\n"); @@ -637,14 +640,18 @@ static void optimize_result(void) /* start by placing the symbols that are actually used on the table */ static void insert_real_symbols_in_table(void) { - unsigned int i, j, c; + unsigned int i, j; + unsigned char c; for (i = 0; i < table_cnt; i++) { for (j = 0; j < table[i]->len; j++) { c = table[i]->sym[j]; - best_table[c][0]=c; - best_table_len[c]=1; + best_table[c][0] = c; + best_table_len[c] = 1; } + c = table[i]->type; + best_table[c][0] = c; + best_table_len[c] = 1; } } @@ -661,7 +668,7 @@ static void optimize_token_table(void) static int may_be_linker_script_provide_symbol(const struct sym_entry *se) { const char *symbol = sym_name(se); - int len = se->len - 1; + int len = se->len; if (len < 8) return 0; @@ -705,8 +712,8 @@ static int compare_symbols(const void *a, const void *b) return -1; /* sort by "weakness" type */ - wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W'); - wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W'); + wa = (sa->type == 'w') || (sa->type == 'W'); + wb = (sb->type == 'w') || (sb->type == 'W'); if (wa != wb) return wa - wb; @@ -742,7 +749,7 @@ static void make_percpus_absolute(void) * ensure consistent behavior compared to older * versions of this tool. */ - table[i]->sym[0] = 'A'; + table[i]->type = 'A'; table[i]->percpu_absolute = 1; } } From patchwork Sat Sep 24 12:20:43 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987606 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 5BCE3C6FA93 for ; Sat, 24 Sep 2022 12:22:56 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233831AbiIXMWy (ORCPT ); Sat, 24 Sep 2022 08:22:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55022 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233786AbiIXMWx (ORCPT ); Sat, 24 Sep 2022 08:22:53 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 0752EE1090; Sat, 24 Sep 2022 05:22:51 -0700 (PDT) Received: from dggpemm500021.china.huawei.com (unknown [172.30.72.55]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MZSl21YlWzpTpf; Sat, 24 Sep 2022 20:19:58 +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.31; Sat, 24 Sep 2022 20:22:50 +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.31; Sat, 24 Sep 2022 20:22:49 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 03/11] scripts/kallsyms: remove helper sym_name() and cleanup Date: Sat, 24 Sep 2022 20:20:43 +0800 Message-ID: <20220924122051.362-4-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Now, the type and name of a symbol are no longer stored together. So the helper sym_name() is no longer needed. Correspondingly, replacing the field name 'sym[]' with 'name[]' is more accurate. Suggested-by: Petr Mladek Signed-off-by: Zhen Lei --- scripts/kallsyms.c | 29 ++++++++++++----------------- 1 file changed, 12 insertions(+), 17 deletions(-) diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index 296277128d450ff..ca378a7e9425c00 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -35,7 +35,7 @@ struct sym_entry { unsigned int start_pos; unsigned int percpu_absolute; unsigned char type; - unsigned char sym[]; + unsigned char name[]; }; struct addr_range { @@ -76,11 +76,6 @@ static void usage(void) exit(1); } -static char *sym_name(const struct sym_entry *s) -{ - return (char *)s->sym; -} - static bool is_ignored_symbol(const char *name, char type) { /* Symbol names that exactly match to the following are ignored.*/ @@ -238,7 +233,7 @@ static struct sym_entry *read_symbol(FILE *in) sym->addr = addr; sym->len = len; sym->type = type; - strcpy(sym_name(sym), name); + strcpy((char *)sym->name, name); sym->percpu_absolute = 0; return sym; @@ -262,7 +257,7 @@ static int symbol_in_range(const struct sym_entry *s, static int symbol_valid(const struct sym_entry *s) { - const char *name = sym_name(s); + const char *name = (char *)s->name; /* if --all-symbols is not specified, then symbols outside the text * and inittext sections are discarded */ @@ -475,7 +470,7 @@ static void write_src(void) printf("\t.byte 0x%02x", table[i]->len + 1); printf(", 0x%02x", table[i]->type); for (k = 0; k < table[i]->len; k++) - printf(", 0x%02x", table[i]->sym[k]); + printf(", 0x%02x", table[i]->name[k]); printf("\n"); /* fields 'len' and 'type' occupy one byte each */ @@ -533,7 +528,7 @@ static void build_initial_token_table(void) unsigned int i; for (i = 0; i < table_cnt; i++) - learn_symbol(table[i]->sym, table[i]->len); + learn_symbol(table[i]->name, table[i]->len); } static unsigned char *find_token(unsigned char *str, int len, @@ -558,14 +553,14 @@ static void compress_symbols(const unsigned char *str, int idx) for (i = 0; i < table_cnt; i++) { len = table[i]->len; - p1 = table[i]->sym; + p1 = table[i]->name; /* find the token on the symbol */ p2 = find_token(p1, len, str); if (!p2) continue; /* decrease the counts for this symbol's tokens */ - forget_symbol(table[i]->sym, len); + forget_symbol(table[i]->name, len); size = len; @@ -587,7 +582,7 @@ static void compress_symbols(const unsigned char *str, int idx) table[i]->len = len; /* increase the counts for this symbol's new tokens */ - learn_symbol(table[i]->sym, len); + learn_symbol(table[i]->name, len); } } @@ -645,7 +640,7 @@ static void insert_real_symbols_in_table(void) for (i = 0; i < table_cnt; i++) { for (j = 0; j < table[i]->len; j++) { - c = table[i]->sym[j]; + c = table[i]->name[j]; best_table[c][0] = c; best_table_len[c] = 1; } @@ -667,7 +662,7 @@ static void optimize_token_table(void) /* guess for "linker script provide" symbol */ static int may_be_linker_script_provide_symbol(const struct sym_entry *se) { - const char *symbol = sym_name(se); + const char *symbol = (char *)se->name; int len = se->len; if (len < 8) @@ -724,8 +719,8 @@ static int compare_symbols(const void *a, const void *b) return wa - wb; /* sort by the number of prefix underscores */ - wa = strspn(sym_name(sa), "_"); - wb = strspn(sym_name(sb), "_"); + wa = strspn((char *)sa->name, "_"); + wb = strspn((char *)sb->name, "_"); if (wa != wb) return wa - wb; From patchwork Sat Sep 24 12:20:44 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987607 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 1D69BC6FA94 for ; Sat, 24 Sep 2022 12:22:57 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233838AbiIXMWz (ORCPT ); Sat, 24 Sep 2022 08:22:55 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55054 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233822AbiIXMWy (ORCPT ); Sat, 24 Sep 2022 08:22:54 -0400 Received: from szxga08-in.huawei.com (szxga08-in.huawei.com [45.249.212.255]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E293DDF3AC; Sat, 24 Sep 2022 05:22:52 -0700 (PDT) Received: from dggpemm500020.china.huawei.com (unknown [172.30.72.55]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4MZSjX1kD0z1P6np; Sat, 24 Sep 2022 20:18:40 +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.31; Sat, 24 Sep 2022 20:22:51 +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.31; Sat, 24 Sep 2022 20:22:50 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 04/11] scripts/kallsyms: generate kallsyms_best_token_table[] Date: Sat, 24 Sep 2022 20:20:44 +0800 Message-ID: <20220924122051.362-5-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: To speed up the lookup of a symbol in the kernel, we'd better compress the searched symbol first and then make a quick comparison based on the compressed length and content. But the tokens in kallsyms_token_table[] have been expanded, a more complex process is required to complete the compression of a symbol. So generate kallsyms_best_token_table[] helps us to compress a symbol in the kernel using a process similar to compress_symbol(). Some minor changes have been made to reduce memory usage and improve compression performance. 1. Some entries in best_table[] are single characters, and most of them are clustered together. such as a-z, A-Z, 0-9. These individual characters are not used in the process of compressing a symbol. Let kallsyms_best_token_table[i][0] = 0x00, [i][0] = number of consecutive single characters (for exampe, a-z is 26). When [i][0] = 0x00 is encountered, we can skip to the next token with two elements. 2. Now ARRAY_SIZE(kallsyms_best_token_table) is not fixed, we store the content of best_table[] to kallsyms_best_token_table[] in reverse order. That is, the higher the frequency, the lower the index. Signed-off-by: Zhen Lei --- kernel/kallsyms_internal.h | 1 + scripts/kallsyms.c | 18 ++++++++++++++++++ 2 files changed, 19 insertions(+) diff --git a/kernel/kallsyms_internal.h b/kernel/kallsyms_internal.h index 2d0c6f2f0243a28..d9672ede8cfc215 100644 --- a/kernel/kallsyms_internal.h +++ b/kernel/kallsyms_internal.h @@ -26,5 +26,6 @@ extern const char kallsyms_token_table[] __weak; extern const u16 kallsyms_token_index[] __weak; extern const unsigned int kallsyms_markers[] __weak; +extern const unsigned char kallsyms_best_token_table[] __weak; #endif // LINUX_KALLSYMS_INTERNAL_H_ diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index ca378a7e9425c00..40a6fe6d14ef03f 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -499,6 +499,24 @@ static void write_src(void) for (i = 0; i < 256; i++) printf("\t.short\t%d\n", best_idx[i]); printf("\n"); + + output_label("kallsyms_best_token_table"); + for (i = 255, k = 0; (int)i >= 0; i--) { + if (best_table_len[i] <= 1) { + k++; + continue; + } + + if (k) { + printf("\t.byte 0x00, 0x%02x\n", k); + k = 0; + } + + printf("\t.byte 0x%02x, 0x%02x\n", best_table[i][0], best_table[i][1]); + } + if (k) + printf("\t.byte 0x00, 0x%02x\n", k); + printf("\n"); } From patchwork Sat Sep 24 12:20:45 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987608 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 40571C07E9D for ; Sat, 24 Sep 2022 12:22:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233197AbiIXMW5 (ORCPT ); Sat, 24 Sep 2022 08:22:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55074 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233830AbiIXMWz (ORCPT ); Sat, 24 Sep 2022 08:22:55 -0400 Received: from szxga08-in.huawei.com (szxga08-in.huawei.com [45.249.212.255]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AD494FDE; Sat, 24 Sep 2022 05:22:53 -0700 (PDT) Received: from dggpemm500022.china.huawei.com (unknown [172.30.72.53]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4MZSjY0Crqz1P6nC; Sat, 24 Sep 2022 20:18:41 +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.31; Sat, 24 Sep 2022 20:22:51 +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.31; Sat, 24 Sep 2022 20:22:51 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 05/11] kallsyms: Improve the performance of kallsyms_lookup_name() Date: Sat, 24 Sep 2022 20:20:45 +0800 Message-ID: <20220924122051.362-6-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) 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 process can be optimized. And now scripts/kallsyms no longer compresses the symbol types, each symbol type always occupies one byte. So we can first compress the searched symbol and then make a quick comparison based on the compressed length and content. In this way, for entries with mismatched lengths, there is no need to expand and compare strings. And for those matching lengths, there's no need to expand the symbol. This saves a lot of time. According to my test results, the average performance of kallsyms_lookup_name() can be improved by 20 to 30 times. 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=5250, max= 726560, avg= 302132 After : min=5320, max= 726850, avg= 301978 Before: min=170, max=15949190, avg=7553906 Before: min=160, max=15877280, avg=7517784 The average time consumed is only 4.01% and the maximum time consumed is only 4.57% of the time consumed before optimization. Signed-off-by: Zhen Lei --- kernel/kallsyms.c | 124 ++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 120 insertions(+), 4 deletions(-) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 3e7e2c2ad2f75ef..22281dc9a49e35d 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -87,6 +87,86 @@ static unsigned int kallsyms_expand_symbol(unsigned int off, return off; } +static unsigned char *find_token(unsigned char *str, int len, + const unsigned char *token) +{ + int i; + + for (i = 0; i < len - 1; i++) { + if (str[i] == token[0] && str[i+1] == token[1]) + return &str[i]; + } + return NULL; +} + +static int kallsyms_compress_symbol_name(const char *name, char *buf, size_t size) +{ + int i, j, n, len; + unsigned char *p1, *p2; + const unsigned char *token; + + len = strscpy(buf, name, size); + if (WARN_ON_ONCE(len <= 0)) + return 0; + + /* + * For each entry in kallsyms_best_token_table[], the storage + * format is: + * 1. For tokens that cannot be used to compress characters, the value + * at [j] is 0, and the value at [j+1] is the number of consecutive + * tokens with this feature. + * 2. For each token: the larger the token value, the higher the + * frequency, and the lower the index. + * + * ------------------------------- + * | j | [j] [j+1] | token | + * -----|---------------|---------| + * | 0 | ?? ?? | 255 | + * | 2 | ?? ?? | 254 | + * | ... | ?? ?? | ... | + * | n-2 | ?? ?? | x | + * | n | 00 len | x-1 | + * | n+2 | ?? ?? | x-1-len | + * above '??' is non-zero + */ + for (i = 255, j = 0; i >= 0; i--, j += 2) { + if (!kallsyms_best_token_table[j]) { + i -= kallsyms_best_token_table[j + 1]; + if (i < 0) + break; + j += 2; + } + token = &kallsyms_best_token_table[j]; + + p1 = buf; + + /* find the token on the symbol */ + p2 = find_token(p1, len, token); + if (!p2) + continue; + + n = len; + + do { + *p2 = i; + p2++; + n -= (p2 - p1); + memmove(p2, p2 + 1, n); + p1 = p2; + len--; + + if (n < 2) + break; + + /* find the token on the symbol */ + p2 = find_token(p1, n, token); + + } while (p2); + } + + return len; +} + /* * Get symbol type information. This is encoded as a single char at the * beginning of the symbol name. @@ -186,26 +266,62 @@ static bool cleanup_symbol_name(char *s) return false; } +static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, + unsigned long *addr) +{ + unsigned int i, off; + unsigned int name_len; + const unsigned char *name; + + for (i = 0, off = 0; len && i < kallsyms_num_syms; i++) { + /* + * For each entry in kallsyms_names[], the storage format is: + * ---------------------------- + * | len(1) | type(1) | name(x) | + * ---------------------------- + * + * Number of bytes in parentheses, and: len = 1 + x + */ + name_len = kallsyms_names[off] - 1; + name = &kallsyms_names[off + 2]; + off += name_len + 2; + + if (name_len != len) + continue; + + if (!memcmp(name, namebuf, len)) { + *addr = kallsyms_sym_address(i); + return 0; + } + } + + return -ENOENT; +} + /* Lookup the address for this symbol. Returns 0 if not found. */ unsigned long kallsyms_lookup_name(const char *name) { char namebuf[KSYM_NAME_LEN]; - unsigned long i; + unsigned long i, addr; unsigned int off; + int ret, len; /* Skip the search for empty string. */ if (!*name) return 0; + len = kallsyms_compress_symbol_name(name, namebuf, ARRAY_SIZE(namebuf)); + ret = kallsyms_lookup_compressed_name(namebuf, len, &addr); + if (!ret) + return addr; + for (i = 0, off = 0; i < kallsyms_num_syms; i++) { off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - if (strcmp(namebuf, name) == 0) - return kallsyms_sym_address(i); - if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0) return kallsyms_sym_address(i); } + return module_kallsyms_lookup_name(name); } From patchwork Sat Sep 24 12:20:46 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987609 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 B0308C32771 for ; Sat, 24 Sep 2022 12:22:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233843AbiIXMW5 (ORCPT ); Sat, 24 Sep 2022 08:22:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55086 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233744AbiIXMWz (ORCPT ); Sat, 24 Sep 2022 08:22:55 -0400 Received: from szxga08-in.huawei.com (szxga08-in.huawei.com [45.249.212.255]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4737AE1090; Sat, 24 Sep 2022 05:22:54 -0700 (PDT) Received: from dggpemm500023.china.huawei.com (unknown [172.30.72.56]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4MZSjY5Tswz1P6qL; Sat, 24 Sep 2022 20:18:41 +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.31; Sat, 24 Sep 2022 20:22:52 +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.31; Sat, 24 Sep 2022 20:22:51 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 06/11] kallsyms: Add helper kallsyms_lookup_clang_name() Date: Sat, 24 Sep 2022 20:20:46 +0800 Message-ID: <20220924122051.362-7-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Literally, there is no sense that cleanup_symbol_name() is associated with CLANG. So add helper kallsyms_lookup_clang_name() can enhance the readability of the code. More importantly, if CONFIG_LTO_CLANG=n, there is no need to execute that loop at all. Signed-off-by: Zhen Lei --- kernel/kallsyms.c | 34 ++++++++++++++++++++++++++-------- 1 file changed, 26 insertions(+), 8 deletions(-) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 22281dc9a49e35d..7366995f40395ec 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -266,6 +266,28 @@ static bool cleanup_symbol_name(char *s) return false; } +static int kallsyms_lookup_clang_name(unsigned char *namebuf, int len, + const char *name, + unsigned long *addr) +{ + unsigned long i; + unsigned int off; + + if (!IS_ENABLED(CONFIG_LTO_CLANG)) + return -ENOENT; + + for (i = 0, off = 0; i < kallsyms_num_syms; i++) { + off = kallsyms_expand_symbol(off, namebuf, len); + + if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0) { + *addr = kallsyms_sym_address(i); + return 0; + } + } + + return -ENOENT; +} + static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, unsigned long *addr) { @@ -302,8 +324,7 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, unsigned long kallsyms_lookup_name(const char *name) { char namebuf[KSYM_NAME_LEN]; - unsigned long i, addr; - unsigned int off; + unsigned long addr; int ret, len; /* Skip the search for empty string. */ @@ -315,12 +336,9 @@ unsigned long kallsyms_lookup_name(const char *name) if (!ret) return addr; - for (i = 0, off = 0; i < kallsyms_num_syms; i++) { - off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - - if (cleanup_symbol_name(namebuf) && strcmp(namebuf, name) == 0) - return kallsyms_sym_address(i); - } + ret = kallsyms_lookup_clang_name(namebuf, len, name, &addr); + if (!ret) + return addr; return module_kallsyms_lookup_name(name); } From patchwork Sat Sep 24 12:20:47 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987610 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 6841AC07E9D for ; Sat, 24 Sep 2022 12:23:02 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233857AbiIXMXA (ORCPT ); Sat, 24 Sep 2022 08:23:00 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55174 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229794AbiIXMW5 (ORCPT ); Sat, 24 Sep 2022 08:22:57 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 2844BE11C3; Sat, 24 Sep 2022 05:22:55 -0700 (PDT) Received: from dggpemm500024.china.huawei.com (unknown [172.30.72.53]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MZSl52MDpzpVCl; Sat, 24 Sep 2022 20:20:01 +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.31; Sat, 24 Sep 2022 20:22:53 +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.31; Sat, 24 Sep 2022 20:22:52 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 07/11] kallsyms: Add helper kallsyms_on_each_match_symbol() Date: Sat, 24 Sep 2022 20:20:47 +0800 Message-ID: <20220924122051.362-8-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) 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. 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, "stub_name") == 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, "stub_name", &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: 557400, 583900 kallsyms_on_each_symbol : 16659500, 16113950 kallsyms_on_each_match_symbol() consumes only 3.48% of kallsyms_on_each_symbol()'s time. Signed-off-by: Zhen Lei --- include/linux/kallsyms.h | 8 ++++++++ kernel/kallsyms.c | 44 ++++++++++++++++++++++++++++++++++++---- 2 files changed, 48 insertions(+), 4 deletions(-) diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h index ad39636e0c3f122..2138219ae0296e9 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); +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 7366995f40395ec..309bee76d7f5ac0 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -288,14 +288,17 @@ static int kallsyms_lookup_clang_name(unsigned char *namebuf, int len, return -ENOENT; } -static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, - unsigned long *addr) +static int __kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, + unsigned int *index, + unsigned int *offset, + unsigned long *addr) { - unsigned int i, off; + unsigned int i = *index; + unsigned int off = *offset; unsigned int name_len; const unsigned char *name; - for (i = 0, off = 0; len && i < kallsyms_num_syms; i++) { + for (; len && i < kallsyms_num_syms; i++) { /* * For each entry in kallsyms_names[], the storage format is: * ---------------------------- @@ -312,6 +315,10 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, continue; if (!memcmp(name, namebuf, len)) { + /* Prepare for the next iteration */ + *index = i + 1; + *offset = off; + *addr = kallsyms_sym_address(i); return 0; } @@ -320,6 +327,14 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, return -ENOENT; } +static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int len, + unsigned long *addr) +{ + unsigned int i = 0, off = 0; + + return __kallsyms_lookup_compressed_name(namebuf, len, &i, &off, addr); +} + /* Lookup the address for this symbol. Returns 0 if not found. */ unsigned long kallsyms_lookup_name(const char *name) { @@ -366,6 +381,27 @@ 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) +{ + int ret, len; + unsigned long addr; + unsigned int i = 0, off = 0; + char namebuf[KSYM_NAME_LEN]; + + len = kallsyms_compress_symbol_name(name, namebuf, ARRAY_SIZE(namebuf)); + do { + ret = __kallsyms_lookup_compressed_name(namebuf, len, &i, &off, &addr); + if (ret) + return 0; /* end of lookup */ + + ret = fn(data, addr); + cond_resched(); + } while (!ret); + + return ret; +} + static unsigned long get_symbol_pos(unsigned long addr, unsigned long *symbolsize, unsigned long *offset) From patchwork Sat Sep 24 12:20:48 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987611 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 CB4D0C07E9D for ; Sat, 24 Sep 2022 12:23:04 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233863AbiIXMXB (ORCPT ); Sat, 24 Sep 2022 08:23:01 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55200 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233846AbiIXMW5 (ORCPT ); Sat, 24 Sep 2022 08:22:57 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5D1A1E171E; Sat, 24 Sep 2022 05:22:56 -0700 (PDT) Received: from dggpemm500021.china.huawei.com (unknown [172.30.72.54]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MZSjZ6ppxzlWhP; Sat, 24 Sep 2022 20:18:42 +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.31; Sat, 24 Sep 2022 20:22:54 +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.31; Sat, 24 Sep 2022 20:22:53 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 08/11] livepatch: Use kallsyms_on_each_match_symbol() to improve performance Date: Sat, 24 Sep 2022 20:20:48 +0800 Message-ID: <20220924122051.362-9-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) 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(), the average performance can be improved by 20 to 30 times. 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 Sat Sep 24 12:20:49 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987612 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 060D2C07E9D for ; Sat, 24 Sep 2022 12:23:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233886AbiIXMXU (ORCPT ); Sat, 24 Sep 2022 08:23:20 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55294 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233854AbiIXMXA (ORCPT ); Sat, 24 Sep 2022 08:23:00 -0400 Received: from szxga02-in.huawei.com (szxga02-in.huawei.com [45.249.212.188]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5E303E21DF; Sat, 24 Sep 2022 05:22:57 -0700 (PDT) Received: from dggpemm500020.china.huawei.com (unknown [172.30.72.54]) by szxga02-in.huawei.com (SkyGuard) with ESMTP id 4MZSjp5YLSzWgrs; Sat, 24 Sep 2022 20:18:54 +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.31; Sat, 24 Sep 2022 20:22:54 +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.31; Sat, 24 Sep 2022 20:22:54 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 09/11] livepatch: Improve the search performance of module_kallsyms_on_each_symbol() Date: Sat, 24 Sep 2022 20:20:49 +0800 Message-ID: <20220924122051.362-10-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) 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. Let's add a new parameter 'const char *modname' to function module_kallsyms_on_each_symbol(), then we can compare the module names directly in this function and call hook 'fn' after matching. And the parameter 'struct module *' in the hook 'fn' can also be deleted. Phase1: mod1-->mod2..(subsequent modules do not need to be compared) | Phase2: -->f1-->f2-->f3 Signed-off-by: Zhen Lei --- include/linux/module.h | 4 ++-- kernel/livepatch/core.c | 13 ++----------- kernel/module/kallsyms.c | 15 ++++++++++++--- 3 files changed, 16 insertions(+), 16 deletions(-) diff --git a/include/linux/module.h b/include/linux/module.h index 518296ea7f73af6..6e1a531d78e7e8b 100644 --- a/include/linux/module.h +++ b/include/linux/module.h @@ -879,8 +879,8 @@ static inline bool module_sig_ok(struct module *module) } #endif /* CONFIG_MODULE_SIG */ -int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *, - struct module *, unsigned long), +int module_kallsyms_on_each_symbol(const char *modname, + int (*fn)(void *, const char *, unsigned long), void *data); #endif /* _LINUX_MODULE_H */ diff --git a/kernel/livepatch/core.c b/kernel/livepatch/core.c index 31b57ccf908017e..b02de4cb311c703 100644 --- a/kernel/livepatch/core.c +++ b/kernel/livepatch/core.c @@ -118,27 +118,19 @@ static struct klp_object *klp_find_object(struct klp_patch *patch, } struct klp_find_arg { - const char *objname; const char *name; unsigned long addr; unsigned long count; unsigned long pos; }; -static int klp_find_callback(void *data, const char *name, - struct module *mod, unsigned long addr) +static int klp_find_callback(void *data, const char *name, unsigned long addr) { struct klp_find_arg *args = data; - if ((mod && !args->objname) || (!mod && args->objname)) - return 0; - if (strcmp(args->name, name)) return 0; - if (args->objname && strcmp(args->objname, mod->name)) - return 0; - args->addr = addr; args->count++; @@ -175,7 +167,6 @@ static int klp_find_object_symbol(const char *objname, const char *name, unsigned long sympos, unsigned long *addr) { struct klp_find_arg args = { - .objname = objname, .name = name, .addr = 0, .count = 0, @@ -183,7 +174,7 @@ static int klp_find_object_symbol(const char *objname, const char *name, }; if (objname) - module_kallsyms_on_each_symbol(klp_find_callback, &args); + module_kallsyms_on_each_symbol(objname, klp_find_callback, &args); else kallsyms_on_each_match_symbol(klp_match_callback, name, &args); diff --git a/kernel/module/kallsyms.c b/kernel/module/kallsyms.c index f5c5c9175333df7..329cef573675d49 100644 --- a/kernel/module/kallsyms.c +++ b/kernel/module/kallsyms.c @@ -495,8 +495,8 @@ unsigned long module_kallsyms_lookup_name(const char *name) } #ifdef CONFIG_LIVEPATCH -int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *, - struct module *, unsigned long), +int module_kallsyms_on_each_symbol(const char *modname, + int (*fn)(void *, const char *, unsigned long), void *data) { struct module *mod; @@ -510,6 +510,9 @@ int module_kallsyms_on_each_symbol(int (*fn)(void *, const char *, if (mod->state == MODULE_STATE_UNFORMED) continue; + if (strcmp(modname, mod->name)) + continue; + /* Use rcu_dereference_sched() to remain compliant with the sparse tool */ preempt_disable(); kallsyms = rcu_dereference_sched(mod->kallsyms); @@ -522,10 +525,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)); + 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); From patchwork Sat Sep 24 12:20:50 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987613 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 1C781C07E9D for ; Sat, 24 Sep 2022 12:23:31 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233903AbiIXMXa (ORCPT ); Sat, 24 Sep 2022 08:23:30 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55254 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233861AbiIXMXA (ORCPT ); Sat, 24 Sep 2022 08:23:00 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 9C010E2346; Sat, 24 Sep 2022 05:22:57 -0700 (PDT) Received: from dggpemm500022.china.huawei.com (unknown [172.30.72.57]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MZSl74zgFzpVJh; Sat, 24 Sep 2022 20:20:03 +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.31; Sat, 24 Sep 2022 20:22:55 +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.31; Sat, 24 Sep 2022 20:22:54 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 10/11] kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol() Date: Sat, 24 Sep 2022 20:20:50 +0800 Message-ID: <20220924122051.362-11-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: The parameter 'struct module *' in the hook function associated with kallsyms_on_each_symbol() is no longer used. Delete it. Suggested-by: Petr Mladek Signed-off-by: Zhen Lei --- include/linux/kallsyms.h | 3 +-- kernel/kallsyms.c | 5 ++--- kernel/trace/ftrace.c | 3 +-- 3 files changed, 4 insertions(+), 7 deletions(-) diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h index 2138219ae0296e9..015c7685765978e 100644 --- a/include/linux/kallsyms.h +++ b/include/linux/kallsyms.h @@ -66,8 +66,7 @@ static inline void *dereference_symbol_descriptor(void *ptr) } #ifdef CONFIG_KALLSYMS -int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *, - unsigned long), +int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long), void *data); int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long), const char *name, void *data); diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 309bee76d7f5ac0..8e7e83842bcfdd3 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -362,8 +362,7 @@ unsigned long kallsyms_lookup_name(const char *name) * Iterate over all symbols in vmlinux. For symbols from modules use * module_kallsyms_on_each_symbol instead. */ -int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *, - unsigned long), +int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long), void *data) { char namebuf[KSYM_NAME_LEN]; @@ -373,7 +372,7 @@ int kallsyms_on_each_symbol(int (*fn)(void *, const char *, struct module *, for (i = 0, off = 0; i < kallsyms_num_syms; i++) { off = kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf)); - ret = fn(data, namebuf, NULL, kallsyms_sym_address(i)); + ret = fn(data, namebuf, kallsyms_sym_address(i)); if (ret != 0) return ret; cond_resched(); diff --git a/kernel/trace/ftrace.c b/kernel/trace/ftrace.c index 439e2ab6905ee1e..f135a0a334a3fcb 100644 --- a/kernel/trace/ftrace.c +++ b/kernel/trace/ftrace.c @@ -8250,8 +8250,7 @@ struct kallsyms_data { size_t found; }; -static int kallsyms_callback(void *data, const char *name, - struct module *mod, unsigned long addr) +static int kallsyms_callback(void *data, const char *name, unsigned long addr) { struct kallsyms_data *args = data; const char **sym; From patchwork Sat Sep 24 12:20:51 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Leizhen (ThunderTown)" X-Patchwork-Id: 12987614 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 47DDDC6FA86 for ; Sat, 24 Sep 2022 12:23:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233915AbiIXMXb (ORCPT ); Sat, 24 Sep 2022 08:23:31 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:55980 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S233879AbiIXMXU (ORCPT ); Sat, 24 Sep 2022 08:23:20 -0400 Received: from szxga02-in.huawei.com (szxga02-in.huawei.com [45.249.212.188]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 96572E237F; Sat, 24 Sep 2022 05:22:58 -0700 (PDT) Received: from dggpemm500023.china.huawei.com (unknown [172.30.72.56]) by szxga02-in.huawei.com (SkyGuard) with ESMTP id 4MZSj01bwPzHthx; Sat, 24 Sep 2022 20:18:12 +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.31; Sat, 24 Sep 2022 20:22:56 +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.31; Sat, 24 Sep 2022 20:22:55 +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" , , "Steven Rostedt" , Ingo Molnar CC: Zhen Lei Subject: [PATCH v6 11/11] kallsyms: Add self-test facility Date: Sat, 24 Sep 2022 20:20:51 +0800 Message-ID: <20220924122051.362-12-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.26.0.windows.1 In-Reply-To: <20220924122051.362-1-thunder.leizhen@huawei.com> References: <20220924122051.362-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems703-chm.china.huawei.com (10.3.19.180) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected Precedence: bulk List-ID: Added test cases for basic functions and performance of functions kallsyms_lookup_name(), kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol(). It also calculates the compression rate of the kallsyms compression algorithm for the current symbol set. The basic functions test begins by testing a set of symbols whose address values are known. Then, traverse all symbol addresses and find the corresponding symbol name based on the address. It's impossible to determine whether these addresses are correct, but we can use the above three functions along with the addresses to test each other. Due to the traversal operation of kallsyms_on_each_symbol() is too slow, only 60 symbols can be tested in one second, so let it test on average once every 128 symbols. The other two functions validate all symbols. If the basic functions test is passed, print only performance test results. If the test fails, print error information, but do not perform subsequent performance tests. Start self-test automatically after system startup if CONFIG_KALLSYMS_SELFTEST=y. Example of output content: (prefix 'kallsyms_selftest:' is omitted) start --------------------------------------------------------- | nr_symbols | compressed size | original size | ratio(%) | |---------------------------------------------------------| | 174099 | 1960154 | 3750756 | 52.26 | --------------------------------------------------------- kallsyms_lookup_name() looked up 174099 symbols The time spent on each symbol is (ns): min=5250, max=726560, avg=302132 kallsyms_on_each_symbol() traverse all: 16659500 ns kallsyms_on_each_match_symbol() traverse all: 557400 ns finish Signed-off-by: Zhen Lei --- include/linux/kallsyms.h | 1 + init/Kconfig | 13 ++ kernel/Makefile | 1 + kernel/kallsyms.c | 2 +- kernel/kallsyms_selftest.c | 421 +++++++++++++++++++++++++++++++++++++ 5 files changed, 437 insertions(+), 1 deletion(-) create mode 100644 kernel/kallsyms_selftest.c diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h index 015c7685765978e..c7219d74e29000c 100644 --- a/include/linux/kallsyms.h +++ b/include/linux/kallsyms.h @@ -66,6 +66,7 @@ static inline void *dereference_symbol_descriptor(void *ptr) } #ifdef CONFIG_KALLSYMS +unsigned long kallsyms_sym_address(int idx); int kallsyms_on_each_symbol(int (*fn)(void *, const char *, unsigned long), void *data); int kallsyms_on_each_match_symbol(int (*fn)(void *, unsigned long), diff --git a/init/Kconfig b/init/Kconfig index 532362fcfe31fd3..60193fd185fb6e6 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -1716,6 +1716,19 @@ config KALLSYMS symbolic stack backtraces. This increases the size of the kernel somewhat, as all symbols have to be loaded into the kernel image. +config KALLSYMS_SELFTEST + bool "Test the basic functions and performance of kallsyms" + depends on KALLSYMS + default n + help + Test the basic functions and performance of some interfaces, such as + kallsyms_lookup_name. It also calculates the compression rate of the + kallsyms compression algorithm for the current symbol set. + + Start self-test automatically after system startup. Suggest executing + "dmesg | grep kallsyms_selftest" to collect test results. "finish" is + displayed in the last line, indicating that the test is complete. + config KALLSYMS_ALL bool "Include all symbols in kallsyms" depends on DEBUG_KERNEL && KALLSYMS diff --git a/kernel/Makefile b/kernel/Makefile index 318789c728d3290..122a5fed457bd98 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -68,6 +68,7 @@ endif obj-$(CONFIG_UID16) += uid16.o obj-$(CONFIG_MODULE_SIG_FORMAT) += module_signature.o obj-$(CONFIG_KALLSYMS) += kallsyms.o +obj-$(CONFIG_KALLSYMS_SELFTEST) += kallsyms_selftest.o obj-$(CONFIG_BSD_PROCESS_ACCT) += acct.o obj-$(CONFIG_CRASH_CORE) += crash_core.o obj-$(CONFIG_KEXEC_CORE) += kexec_core.o diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 8e7e83842bcfdd3..1512db69aa0a1b2 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -208,7 +208,7 @@ static unsigned int get_symbol_offset(unsigned long pos) return name - kallsyms_names; } -static unsigned long kallsyms_sym_address(int idx) +unsigned long kallsyms_sym_address(int idx) { if (!IS_ENABLED(CONFIG_KALLSYMS_BASE_RELATIVE)) return kallsyms_addresses[idx]; diff --git a/kernel/kallsyms_selftest.c b/kernel/kallsyms_selftest.c new file mode 100644 index 000000000000000..f7538a70d36c531 --- /dev/null +++ b/kernel/kallsyms_selftest.c @@ -0,0 +1,421 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Test the function and performance of kallsyms + * + * Copyright (C) Huawei Technologies Co., Ltd., 2022 + * + * Authors: Zhen Lei Huawei + */ + +#define pr_fmt(fmt) "kallsyms_selftest: " fmt + +#include +#include +#include +#include +#include +#include +#include + +#include "kallsyms_internal.h" + + +#define MAX_NUM_OF_RECORDS 64 + +struct test_stat { + int min; + int max; + int save_cnt; + int real_cnt; + u64 sum; + char *name; + unsigned long addr; + unsigned long addrs[MAX_NUM_OF_RECORDS]; +}; + +struct test_item { + char *name; + unsigned long addr; +}; + +#define ITEM_FUNC(s) \ + { \ + .name = #s, \ + .addr = (unsigned long)s, \ + } + +#define ITEM_DATA(s) \ + { \ + .name = #s, \ + .addr = (unsigned long)&s, \ + } + +static int test_var_bss_static; +static int test_var_data_static = 1; +int test_var_bss; +int test_var_data = 1; + +static int test_func_static(void) +{ + test_var_bss_static++; + test_var_data_static++; + + return 0; +} + +int test_func(void) +{ + return test_func_static(); +} + +__weak int test_func_weak(void) +{ + test_var_bss++; + test_var_data++; + return 0; +} + +static struct test_item test_items[] = { + ITEM_FUNC(test_func_static), + ITEM_FUNC(test_func), + ITEM_FUNC(test_func_weak), + ITEM_FUNC(vmalloc), + ITEM_FUNC(vfree), +#ifdef CONFIG_KALLSYMS_ALL + ITEM_DATA(test_var_bss_static), + ITEM_DATA(test_var_data_static), + ITEM_DATA(test_var_bss), + ITEM_DATA(test_var_data), + ITEM_DATA(vmap_area_list), +#endif +}; + +static char stub_name[KSYM_NAME_LEN]; + +static int stat_symbol_len(void *data, const char *name, unsigned long addr) +{ + *(u32 *)data += strlen(name); + + return 0; +} + +static void test_kallsyms_compression_ratio(void) +{ + int i; + const u8 *name; + u32 pos; + u32 ratio, total_size, total_len = 0; + + kallsyms_on_each_symbol(stat_symbol_len, &total_len); + + /* + * A symbol name cannot start with a number. This stub name helps us + * traverse the entire symbol table without finding a match. It's used + * for subsequent performance tests, and its length is the average + * length of all symbol names. + */ + memset(stub_name, '4', sizeof(stub_name)); + pos = total_len / kallsyms_num_syms; + stub_name[pos] = 0; + + pos = kallsyms_num_syms - 1; + name = &kallsyms_names[kallsyms_markers[pos >> 8]]; + for (i = 0; i <= (pos & 0xff); i++) + name = name + (*name) + 1; + + /* + * 1. The length fields is not counted + * 2. The memory occupied by array kallsyms_token_table[] and + * kallsyms_token_index[] needs to be counted. + */ + total_size = (name - kallsyms_names) - kallsyms_num_syms; + pos = kallsyms_token_index[0xff]; + total_size += pos + strlen(&kallsyms_token_table[pos]) + 1; + total_size += 0x100 * sizeof(u16); + + pr_info(" ---------------------------------------------------------\n"); + pr_info("| nr_symbols | compressed size | original size | ratio(%%) |\n"); + pr_info("|---------------------------------------------------------|\n"); + ratio = 10000ULL * total_size / total_len; + pr_info("| %10d | %10d | %10d | %2d.%-2d |\n", + kallsyms_num_syms, total_size, total_len, ratio / 100, ratio % 100); + pr_info(" ---------------------------------------------------------\n"); +} + +static int lookup_name(void *data, const char *name, unsigned long addr) +{ + u64 t0, t1, t; + unsigned long flags; + struct test_stat *stat = (struct test_stat *)data; + + local_irq_save(flags); + t0 = sched_clock(); + (void)kallsyms_lookup_name(name); + t1 = sched_clock(); + local_irq_restore(flags); + + t = t1 - t0; + if (t < stat->min) + stat->min = t; + + if (t > stat->max) + stat->max = t; + + stat->real_cnt++; + stat->sum += t; + + return 0; +} + +static void test_perf_kallsyms_lookup_name(void) +{ + struct test_stat stat; + + memset(&stat, 0, sizeof(stat)); + stat.min = INT_MAX; + kallsyms_on_each_symbol(lookup_name, &stat); + pr_info("kallsyms_lookup_name() looked up %d symbols\n", stat.real_cnt); + pr_info("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n", + stat.min, stat.max, stat.sum / stat.real_cnt); +} + +static int find_symbol(void *data, const char *name, unsigned long addr) +{ + struct test_stat *stat = (struct test_stat *)data; + + if (strcmp(name, stat->name) == 0) { + stat->real_cnt++; + stat->addr = addr; + + if (stat->save_cnt < MAX_NUM_OF_RECORDS) { + stat->addrs[stat->save_cnt] = addr; + stat->save_cnt++; + } + + if (stat->real_cnt == stat->max) + return 1; + } + + return 0; +} + +static void test_perf_kallsyms_on_each_symbol(void) +{ + u64 t0, t1; + unsigned long flags; + struct test_stat stat; + + memset(&stat, 0, sizeof(stat)); + stat.max = INT_MAX; + stat.name = stub_name; + local_irq_save(flags); + t0 = sched_clock(); + kallsyms_on_each_symbol(find_symbol, &stat); + t1 = sched_clock(); + local_irq_restore(flags); + pr_info("kallsyms_on_each_symbol() traverse all: %lld ns\n", t1 - t0); +} + +static int match_symbol(void *data, unsigned long addr) +{ + struct test_stat *stat = (struct test_stat *)data; + + stat->real_cnt++; + stat->addr = addr; + + if (stat->save_cnt < MAX_NUM_OF_RECORDS) { + stat->addrs[stat->save_cnt] = addr; + stat->save_cnt++; + } + + if (stat->real_cnt == stat->max) + return 1; + + return 0; +} + +static void test_perf_kallsyms_on_each_match_symbol(void) +{ + u64 t0, t1; + unsigned long flags; + struct test_stat stat; + + memset(&stat, 0, sizeof(stat)); + stat.max = INT_MAX; + stat.name = stub_name; + local_irq_save(flags); + t0 = sched_clock(); + kallsyms_on_each_match_symbol(match_symbol, stat.name, &stat); + t1 = sched_clock(); + local_irq_restore(flags); + pr_info("kallsyms_on_each_match_symbol() traverse all: %lld ns\n", t1 - t0); +} + +static int test_kallsyms_basic_function(void) +{ + int i, j, ret; + int next = 0, nr_failed = 0; + char *prefix; + unsigned short rand; + unsigned long addr; + char namebuf[KSYM_NAME_LEN]; + struct test_stat stat, stat1, stat2; + + prefix = "kallsyms_lookup_name() for"; + for (i = 0; i < ARRAY_SIZE(test_items); i++) { + addr = kallsyms_lookup_name(test_items[i].name); + if (addr != test_items[i].addr) { + nr_failed++; + pr_info("%s %s failed: addr=%lx, expect %lx\n", + prefix, test_items[i].name, addr, test_items[i].addr); + } + } + + prefix = "kallsyms_on_each_symbol() for"; + for (i = 0; i < ARRAY_SIZE(test_items); i++) { + memset(&stat, 0, sizeof(stat)); + stat.max = INT_MAX; + stat.name = test_items[i].name; + kallsyms_on_each_symbol(find_symbol, &stat); + if (stat.addr != test_items[i].addr || stat.real_cnt != 1) { + nr_failed++; + pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n", + prefix, test_items[i].name, + stat.real_cnt, stat.addr, test_items[i].addr); + } + } + + prefix = "kallsyms_on_each_match_symbol() for"; + for (i = 0; i < ARRAY_SIZE(test_items); i++) { + memset(&stat, 0, sizeof(stat)); + stat.max = INT_MAX; + stat.name = test_items[i].name; + kallsyms_on_each_match_symbol(match_symbol, test_items[i].name, &stat); + if (stat.addr != test_items[i].addr || stat.real_cnt != 1) { + nr_failed++; + pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n", + prefix, test_items[i].name, + stat.real_cnt, stat.addr, test_items[i].addr); + } + } + + if (nr_failed) + return -ESRCH; + + for (i = 0; i < kallsyms_num_syms; i++) { + addr = kallsyms_sym_address(i); + if (!is_ksym_addr(addr)) + continue; + + ret = lookup_symbol_name(addr, namebuf); + if (unlikely(ret)) { + namebuf[0] = 0; + goto failed; + } + + stat.addr = kallsyms_lookup_name(namebuf); + + memset(&stat1, 0, sizeof(stat1)); + stat1.max = INT_MAX; + kallsyms_on_each_match_symbol(match_symbol, namebuf, &stat1); + + /* + * kallsyms_on_each_symbol() is too slow, randomly select some + * symbols for test. + */ + if (i >= next) { + memset(&stat2, 0, sizeof(stat2)); + stat2.max = INT_MAX; + stat2.name = namebuf; + kallsyms_on_each_symbol(find_symbol, &stat2); + + /* + * kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol() + * need to get the same traversal result. + */ + if (stat1.addr != stat2.addr || + stat1.real_cnt != stat2.real_cnt || + memcmp(stat1.addrs, stat2.addrs, + stat1.save_cnt * sizeof(stat1.addrs[0]))) + goto failed; + + /* + * The average of random increments is 128, that is, one of + * them is tested every 128 symbols. + */ + get_random_bytes(&rand, sizeof(rand)); + next = i + (rand & 0xff) + 1; + } + + /* Need to be found at least once */ + if (!stat1.real_cnt) + goto failed; + + /* + * kallsyms_lookup_name() returns the address of the first + * symbol found and cannot be NULL. + */ + if (!stat.addr || stat.addr != stat1.addrs[0]) + goto failed; + + /* + * If the addresses of all matching symbols are recorded, the + * target address needs to be exist. + */ + if (stat1.real_cnt <= MAX_NUM_OF_RECORDS) { + for (j = 0; j < stat1.save_cnt; j++) { + if (stat1.addrs[j] == addr) + break; + } + + if (j == stat1.save_cnt) + goto failed; + } + } + + return 0; + +failed: + pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr); + return -ESRCH; +} + +static int test_entry(void *p) +{ + int ret; + + do { + schedule_timeout(5 * HZ); + } while (system_state != SYSTEM_RUNNING); + + pr_info("start\n"); + ret = test_kallsyms_basic_function(); + if (ret) { + pr_info("abort\n"); + return 0; + } + + test_kallsyms_compression_ratio(); + test_perf_kallsyms_lookup_name(); + test_perf_kallsyms_on_each_symbol(); + test_perf_kallsyms_on_each_match_symbol(); + pr_info("finish\n"); + + return 0; +} + +static int __init kallsyms_test_init(void) +{ + struct task_struct *t; + + t = kthread_create(test_entry, NULL, "kallsyms_test"); + if (IS_ERR(t)) { + pr_info("Create kallsyms selftest task failed\n"); + return PTR_ERR(t); + } + kthread_bind(t, 0); + wake_up_process(t); + + return 0; +} +late_initcall(kallsyms_test_init);