From patchwork Mon Oct 17 06:49:40 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3233 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303565wrs; Sun, 16 Oct 2022 23:52:41 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7wqoPErib+vTwpXdX+KOhztKAatsI4uJ/CUbm5P+gjO+BYEfTtsYNZUrk9XaeOmqJYc0EV X-Received: by 2002:a17:90b:33cd:b0:20d:9da6:56e3 with SMTP id lk13-20020a17090b33cd00b0020d9da656e3mr26451269pjb.143.1665989561544; Sun, 16 Oct 2022 23:52:41 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989561; cv=none; d=google.com; s=arc-20160816; b=d4ZsAAgAgMZaj4NBJAZSTWI+v3rejfKNes00DBGa3NWiZjReEtEwevcsft7QaCMVeK dRGxZ+yTTKGTmCH7othsDmAsgVaDyQFjN8Q5eTiJgWuNfiUZudzx2nJHa7L9A1SZipnu NxKvMZESyPNlilhADCyNrdf+n+oceq8Tht4ipeg1j70aQErXcKjw3GZuqxUYcz9Yux42 5jebtoNH+TIL8M3QkLadD54Hm1dJgMmoYDXXyhVcT2eVX2gqJPRg/eFeiTe+yevZAHvz MfBLYQLc1axXE/ZM3ICSBZ7fk+Xi7D8/6yNJDS3fXdXqw/TwuOXIBps1M2KDkJ8EQ7pd TZ/Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=27ivNInO1WNZHSaFBcLCEgzvlo2LVYUDZnP7WEvjbqs=; b=lg0/CPHgIMhOD7v3QsE3T/JtyHHDjMceQi9pybijJbWnnbH6pti0uyKEfzovBxhQKZ sOo/XAIHIgyHumZezAP6h0IiT7JEU8PVmEwv7iuedQo0EQNkSIxQ8lLp2sB+STHrv+3k lJORlffbFiPvK+HavCboFsUtOV3t8jfD5i+GjZRVRRxPlG6mPSzABly9+/FOaPlwvKBT YoDtxH5BLx35MpX+VPbplAtFNAMGNVKBWLxl27yhsCfre3pUzVi1Vbwlod57b4LRWxb5 +Dd+bc5u2hV5LXirVQbIKUOq/vdPjvaT6SEAVRsYRyxIL/3fkbVyYp7iQWt14YIhM6H3 rpWw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id il8-20020a17090b164800b001fddf1a3380si11062462pjb.109.2022.10.16.23.52.28; Sun, 16 Oct 2022 23:52:41 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230177AbiJQGvg (ORCPT + 99 others); Mon, 17 Oct 2022 02:51:36 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51040 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230017AbiJQGuy (ORCPT ); Mon, 17 Oct 2022 02:50:54 -0400 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 22E4D57893; Sun, 16 Oct 2022 23:50:49 -0700 (PDT) Received: from dggpemm500022.china.huawei.com (unknown [172.30.72.56]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4MrSHY6tbJzJn5j; Mon, 17 Oct 2022 14:48:09 +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; Mon, 17 Oct 2022 14:50:37 +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; Mon, 17 Oct 2022 14:50:36 +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 v7 01/11] scripts/kallsyms: rename build_initial_tok_table() Date: Mon, 17 Oct 2022 14:49:40 +0800 Message-ID: <20221017064950.2038-2-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916670544083059?= X-GMAIL-MSGID: =?utf-8?q?1746916670544083059?= 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 03fa07ad45d95b8..ab105bdde4efe4f 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -573,7 +573,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; @@ -698,7 +698,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 Mon Oct 17 06:49:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3239 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303740wrs; Sun, 16 Oct 2022 23:53:21 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6G1MdOo8xMk9uAbCKojkfdiXu9tXyHXC3Vj+0X2jHvv4CebpVZl6pL9EgrcNBdFb98DhfC X-Received: by 2002:a63:ea4a:0:b0:439:4695:c0f8 with SMTP id l10-20020a63ea4a000000b004394695c0f8mr9257040pgk.440.1665989601459; Sun, 16 Oct 2022 23:53:21 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989601; cv=none; d=google.com; s=arc-20160816; b=ybrPUDWuN3b2zD1UlGDmhUoAfrakOnjK8ftxQLIb+7yZ8p2lnIuM3SY6jKw1LZIQOs LBAyWy813p7lAQ5oiykO/8RwQB1ja1Z9I+W7XXWWFRt9B1nO4vV+Z0MxD2Gp3sdnRiWY HMi9UcVy4cjMkTVSlm3Icz0+5bT26HLIowND8hBGp9wsGlytjQvIg6MV1lw6T4lHk1Wp +iP2NkhS82Kzs5PclL/Vu7urwaF/v8vdtj7iLC4sfUt+vk0EgJSjHiX+9sfz3AqMcCLC XTrmd3BHJfSJpndxljyY+NZsm6v0AOVFF8PMcUtTm07+G3vhEyKQ4dSYnhsRkjbIt+JW lEaQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=Is7+OOl36ade0pAq6Q0IbTXWwu988P2ysLwHnz0sC/g=; b=o1Z6C3f4uiDjZl/ohQSqfneVTywCwykl2z1vaP3q18NRYf0htDlryew1+Srln9VvbM Agz+V2u2I5GfdwEgTzLryW1N4Fsr20rxFWBPBJp/+dgpQYRsQ7TLtgbZoOB5L2VKlGFu C22+hoE9WgOvNz9Za17oqiOmKlRdZ6nl4JABUVN4N9wQOKefMHvHzztymZYx7blAzrk+ jqlCnmGHCZNQrrItebv3MAJ9iAqN5m0iiBC6USO/mTEUEuHGX1qEKLdyRyO3CWZAHRCw Ufxli5GjZ92RpbvxfmamdNlrK+JxVoJkNoI7dX1t0AJss7qblWDrzjzOqIRqG5CHxwWh HOVg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id 72-20020a63014b000000b0041a4f434cecsi11092062pgb.798.2022.10.16.23.53.08; Sun, 16 Oct 2022 23:53:21 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230234AbiJQGw2 (ORCPT + 99 others); Mon, 17 Oct 2022 02:52:28 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53082 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230225AbiJQGwD (ORCPT ); Mon, 17 Oct 2022 02:52:03 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EE0AF5809D; Sun, 16 Oct 2022 23:51:08 -0700 (PDT) Received: from dggpemm500023.china.huawei.com (unknown [172.30.72.53]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MrSFX5QCQzmVdM; Mon, 17 Oct 2022 14:46:24 +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; Mon, 17 Oct 2022 14:50:38 +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; Mon, 17 Oct 2022 14:50:37 +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 v7 02/11] scripts/kallsyms: don't compress symbol types Date: Mon, 17 Oct 2022 14:49:41 +0800 Message-ID: <20221017064950.2038-3-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916712650101927?= X-GMAIL-MSGID: =?utf-8?q?1746916712650101927?= 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 | 38 +++++++++++++++++++++++--------------- 1 file changed, 23 insertions(+), 15 deletions(-) diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index ab105bdde4efe4f..d3aae0491b3e963 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -51,6 +51,7 @@ struct sym_entry { unsigned int len; unsigned int start_pos; unsigned int percpu_absolute; + unsigned char type; unsigned char sym[]; }; @@ -94,7 +95,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) @@ -242,11 +243,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: " @@ -255,7 +252,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; @@ -503,6 +500,12 @@ static void write_src(void) exit(EXIT_FAILURE); } + /* + * Store the symbol type togerher with symbol name. + * It helps to reduce the size. + */ + table[i]->len++; + /* Only lengths that fit in up-to-two-byte ULEB128 are supported. */ if (table[i]->len > 0x3FFF) { fprintf(stderr, "kallsyms failure: " @@ -522,7 +525,8 @@ static void write_src(void) (table[i]->len >> 7) & 0x7F); off += table[i]->len + 2; } - for (k = 0; k < table[i]->len; k++) + printf(", 0x%02x", table[i]->type); + for (k = 0; k < table[i]->len - 1; k++) printf(", 0x%02x", table[i]->sym[k]); printf("\n"); } @@ -685,14 +689,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; } } @@ -709,7 +717,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; @@ -753,8 +761,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; @@ -790,7 +798,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 Mon Oct 17 06:49:42 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3237 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303652wrs; Sun, 16 Oct 2022 23:52:58 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6/CCEHe8JFxTy9Y7Isu8oZzMq44gm8dw+dSaDLA4wiM6hKfeASYChc0BOWX7ckeI7SMwh1 X-Received: by 2002:a63:8a42:0:b0:460:58ec:cc66 with SMTP id y63-20020a638a42000000b0046058eccc66mr9449865pgd.195.1665989577999; Sun, 16 Oct 2022 23:52:57 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989577; cv=none; d=google.com; s=arc-20160816; b=YL/3p+HILa+uDw9s7qbOrE4tl8Ld7yMatZk0V4Rmk9UeBmL+zowzXm4oyIBTGnLukA oOCy3ahoJByHmz9RICd1C8D9kK5T34CCzAQ6Lrnkf4tTb5E1qM2Njy8Guym3mex4HVKQ oyB8wsWD7qzDKlqETq3qoro+hqHLmlBlDCb4H/dqQ+99R7Wzwu1Cmo0jXKcJC58d5Njz 19i0qDUV9/jT7p7wCqdQo85GcWsxlzge9RH098LVcKpXdrMoqJL/cm4MRIFiVXi5EVg0 cMRgEzxmSSupW0Jh9KJNu33tlmUcgmf45vJfDI3gJwu6M391N5fwozKLeo7LR5RX92YD nDrg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=gKNE04sMxvDfRRfyhoocySo4Wvx6KdIvTfkmbHX6nTs=; b=iyNeoRRrnuwOj/kYKLelQennrDkhwGTlLSqAwd1Ys4rluxOxq+Ex2ZzhtIAVYxOvf+ aJjmm3yBQwT3BzqqfnaPQ1qzOQJKf2KXrynskWZv9YhemjyeyT+IRIqivsUD6v0Zxu+W 6kvDb9jTNqF9zuxgBXB5Ov9fGLqzZCQAGjjWkqGjOZhvpDFhEuG/vBfKINGidA8XIk8O Hd6GOMDsSYTq+RwU8/ORbuL9uKDyMFeu8gN6Tz4i0Qr7Mzx+t10g89mbLKECJNAJIFac TNb2r8NgTRgGogwf5TZggb6F78hyBzbKj143vSonDNbjvC7xW9RGZycgwQtdSFs40rrk b5uA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id 37-20020a630d65000000b0046b15902616si12036708pgn.270.2022.10.16.23.52.45; Sun, 16 Oct 2022 23:52:57 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230217AbiJQGvu (ORCPT + 99 others); Mon, 17 Oct 2022 02:51:50 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51038 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230051AbiJQGvU (ORCPT ); Mon, 17 Oct 2022 02:51:20 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id DBD3557BC0; Sun, 16 Oct 2022 23:50:51 -0700 (PDT) Received: from dggpemm500024.china.huawei.com (unknown [172.30.72.55]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MrSGs54JnzpWPs; Mon, 17 Oct 2022 14:47:33 +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; Mon, 17 Oct 2022 14:50:39 +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; Mon, 17 Oct 2022 14:50:38 +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 v7 03/11] scripts/kallsyms: remove helper sym_name() and cleanup Date: Mon, 17 Oct 2022 14:49:42 +0800 Message-ID: <20221017064950.2038-4-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916687689804894?= X-GMAIL-MSGID: =?utf-8?q?1746916687689804894?= 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 d3aae0491b3e963..60686094f665164 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -52,7 +52,7 @@ struct sym_entry { unsigned int start_pos; unsigned int percpu_absolute; unsigned char type; - unsigned char sym[]; + unsigned char name[]; }; struct addr_range { @@ -93,11 +93,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.*/ @@ -253,7 +248,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; @@ -277,7 +272,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 */ @@ -527,7 +522,7 @@ static void write_src(void) } printf(", 0x%02x", table[i]->type); for (k = 0; k < table[i]->len - 1; k++) - printf(", 0x%02x", table[i]->sym[k]); + printf(", 0x%02x", table[i]->name[k]); printf("\n"); } printf("\n"); @@ -582,7 +577,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, @@ -607,14 +602,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; @@ -636,7 +631,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); } } @@ -694,7 +689,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; } @@ -716,7 +711,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) @@ -773,8 +768,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 Mon Oct 17 06:49:43 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3244 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1304630wrs; Sun, 16 Oct 2022 23:57:15 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6FQYmSDHWsytiN8vxjT27GVHmEXoUdU8yWK1HLek72uZovB/zUYpKqrT0wip1MhKeOhXo5 X-Received: by 2002:a17:90b:1b05:b0:20d:3b10:3800 with SMTP id nu5-20020a17090b1b0500b0020d3b103800mr31810146pjb.91.1665989824982; Sun, 16 Oct 2022 23:57:04 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989824; cv=none; d=google.com; s=arc-20160816; b=Fu8aN4967ttukynN1BAXjjtN7slKulQBbJ5RnYQnTSQFD7UEUudKdWjkiJiLQoz8wi LOdVS2r55Evm2OOcYEAbUudlDeMz8b2fhTPBbFeLRaJMZTa+CmSSZndUouqzfUXMXxQ/ nYFRqvo4AcM3szQ5oea3haU2k9o6tpY1S8jO6Ex4NYI3wkXzMPmWgnLFZSNox6QTq1TY 2KsOonvAsUT9PlglRj1tvG8rD+NlHhTFblyM+GRHPyJ3791VcDZ92bOpxt+j6Zb/t7Hk /IGWEzeuRYakO+iARuTJl9Qh4qJijBZyvWDfae9STVP036tDct3vKCMeD6Czbe6k3Yhi 8qVA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=UJ4RaFcNRf3O7KVx1GQhKaki5L1mPXcRCU0jG+T33N4=; b=Cp4T8mFNIWDZaucQbhlTZu2pLXZB2Tv3GthANXzVQ3Oy+sru/iGWqMolqFcJyqnJwE kNl2wQdt/qVpx4MUe3BD1oluXNKLmZ4J99FUZO4RU6yUoSDOd6j6MfV7naBTmC+nyEBg Kcpk6aS/cGrnloA4bdJHVmW9ybWrgLge3cUfJ2ZjUr6AwxPZN96h5QyfPCihA8pzYOVa J2lZjkddLvebcPJxb+yZIGQAR0fUj46eJUleeGg0ccOXxIgv3YBRudH9N5DyCVyX1yC2 VPwdkEYK4PUrVK0EHge9torzhB5GweTo4D1edsHQ60qL7jOhvZLXZ8I/s9IANyV7Bdjv rQmQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id s10-20020a056a00178a00b00565a581ecc0si12391965pfg.11.2022.10.16.23.56.48; Sun, 16 Oct 2022 23:57:04 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230250AbiJQGxl (ORCPT + 99 others); Mon, 17 Oct 2022 02:53:41 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52682 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230187AbiJQGxT (ORCPT ); Mon, 17 Oct 2022 02:53:19 -0400 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5A9F759261; Sun, 16 Oct 2022 23:52:11 -0700 (PDT) Received: from dggpemm500021.china.huawei.com (unknown [172.30.72.53]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4MrSJl5bwDzJn55; Mon, 17 Oct 2022 14:49:11 +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; Mon, 17 Oct 2022 14:50:40 +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; Mon, 17 Oct 2022 14:50:39 +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 v7 04/11] kallsyms: Add helper kallsyms_compress_symbol_name() Date: Mon, 17 Oct 2022 14:49:43 +0800 Message-ID: <20221017064950.2038-5-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916946304874680?= X-GMAIL-MSGID: =?utf-8?q?1746916946304874680?= 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(). The implementation of kallsyms_compress_symbol_name() is almost the same as that of compress_symbols() in scripts/kallsyms.c. 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. The modifier '__maybe_unused' of kallsyms_compress_symbol_name() is temporary and will be removed in the next patch. Signed-off-by: Zhen Lei --- kernel/kallsyms.c | 80 ++++++++++++++++++++++++++++++++++++++ kernel/kallsyms_internal.h | 1 + scripts/kallsyms.c | 18 +++++++++ 3 files changed, 99 insertions(+) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 60c20f301a6ba2c..f1fe404af184047 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -95,6 +95,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 __maybe_unused 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. 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 60686094f665164..9864ce5e6c5bfc1 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -548,6 +548,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 Mon Oct 17 06:49:44 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3241 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303879wrs; Sun, 16 Oct 2022 23:53:50 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5ai7fPe8NIRfijLNTUtCAofDOSjr6qDKMMcb8kltlOBonL9dFrfPg3K896Bvps+kO13K/w X-Received: by 2002:a05:6a00:1312:b0:536:fefd:e64a with SMTP id j18-20020a056a00131200b00536fefde64amr10953166pfu.26.1665989630299; Sun, 16 Oct 2022 23:53:50 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989630; cv=none; d=google.com; s=arc-20160816; b=ATSmsBJSQYt37B/rf95mQWXf0clsM6h3qw+JVhE9FXhxa13gS9s3XKIi5N/LJYwlh5 2uTJ/Mz4KjPP8OzS+UTcx2oPpg1wGhsCGbCjYZRCeocnxACVKBqbx65iAWR+CB1IewZS LKH1FgN9NvU75GXCIRnVy3c68J/juQ1R/HDDYdZq8NcpqDV1Jf9pWGZdmcxY5LUxQiVA dUmpGjH3JqEQGKX9gIIYvHf/Ff6At3r+k5kRF8d4xFlSJm9OEe+TKHBP/jIk9FY80665 nleRUYKP5yQ2pFajbbAzg+N85O7wVwhIRvTQ57rwW5nEfsJ8y+c+wSI/D+lPtLlilR3K 5l6g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=ZeI92u2d8Jac0FCGZfGl7wFgcNhugFOjSps6u7eAOd4=; b=pPPVILW51w9nOX01l3clppEakOA/KIC+ToylSpMbnhfkWeF44p6qXVjgpBxeRkxVzh Xj/cDVw/DvSwDT1JkidmSx7UGillNUEn0OW6ekkFfLBqrnbSd6BYGeyTH8UbnKh0cxsL k8eEiLFprmoJivbUWD0ypqHky9XB9x6uBnOq1kRJ+h8a6CKMM7Gqy718i/+Pq224kLSo JdnmkHt/J0XxFASeMIp6R43InaKCXwUn40ZuMnfEQMAC+t/xffpyox4XsVI+YFOR8oGR 9SiHNDbpwstpBJoMvGAFCI1IcMNB7W561Lv8NWl8H56XUFVHaG9H7T2UsX0of+bm2Ckl CiqA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id m21-20020a637d55000000b0045c39503df3si10447951pgn.451.2022.10.16.23.53.38; Sun, 16 Oct 2022 23:53:50 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230268AbiJQGwh (ORCPT + 99 others); Mon, 17 Oct 2022 02:52:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51076 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230173AbiJQGwE (ORCPT ); Mon, 17 Oct 2022 02:52:04 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AC7E6580A5; Sun, 16 Oct 2022 23:51:09 -0700 (PDT) Received: from dggpemm500020.china.huawei.com (unknown [172.30.72.57]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MrSFY5BTXzmVdG; Mon, 17 Oct 2022 14:46:25 +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; Mon, 17 Oct 2022 14:50:41 +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; Mon, 17 Oct 2022 14:50:40 +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 v7 05/11] kallsyms: Improve the performance of kallsyms_lookup_name() Date: Mon, 17 Oct 2022 14:49:44 +0800 Message-ID: <20221017064950.2038-6-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916742690896998?= X-GMAIL-MSGID: =?utf-8?q?1746916742690896998?= 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 | 50 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 46 insertions(+), 4 deletions(-) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index f1fe404af184047..7f3987cc975be3b 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -107,7 +107,7 @@ static unsigned char *find_token(unsigned char *str, int len, return NULL; } -static int __maybe_unused kallsyms_compress_symbol_name(const char *name, char *buf, size_t size) +static int kallsyms_compress_symbol_name(const char *name, char *buf, size_t size) { int i, j, n, len; unsigned char *p1, *p2; @@ -267,23 +267,65 @@ static bool cleanup_symbol_name(char *s) return false; } +static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, + unsigned long *addr) +{ + unsigned int i, off; + unsigned int len, x; + const unsigned char *name; + + for (i = 0, off = 0; namelen && i < kallsyms_num_syms; i++) { + /* + * For each entry in kallsyms_names[], the storage format is: + * ---------------------------- + * | len(1-2) | type(1) | name(x) | + * ---------------------------- + * + * Number of bytes in parentheses, and: len = 1 + x + */ + len = kallsyms_names[off]; + off++; + if (len & 0x80) { + len = (len & 0x7f) | (kallsyms_names[off] << 7); + off++; + } + name = &kallsyms_names[off + 1]; + off += len; + + x = len - 1; + if (x != namelen) + continue; + + if (!memcmp(name, namebuf, namelen)) { + *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 int off; + unsigned long addr; + 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); } From patchwork Mon Oct 17 06:49:45 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3234 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303585wrs; Sun, 16 Oct 2022 23:52:44 -0700 (PDT) X-Google-Smtp-Source: AMsMyM7+ke0zUkIxlP/eTWmUITt5t2cV3S3RuNB+1SIAwkHd789nouwVV3gXPMTsoFxX9K1CY3gM X-Received: by 2002:a17:90b:3b45:b0:20c:2eae:e70 with SMTP id ot5-20020a17090b3b4500b0020c2eae0e70mr12072652pjb.240.1665989564594; Sun, 16 Oct 2022 23:52:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989564; cv=none; d=google.com; s=arc-20160816; b=J1xujGcd1pomPrhZvV0k9S9mXS19WoDej7BWhPicQl/ylcY2+YvxkuAG3wQrYycvUV ZvYGB//3n+nmgFakmo+9D5zdtYTfhB4FqX2HnDct1WFclS9bF0vW1U/pG1Zvc2D1kyy6 4N0jxQZZKQoFTxm7tXazzX0HqMltbhkeAAocfyGaMWXP8GRvt6dLprGJEvoVQW/sPMks byhXAdGebyrqM96lXn6m5k2Em+SOAXR+imxFHBIZJAnPIcAaOJ3IAY/3xv5eBy4yiNjo TU9Gbu2MKrWEgUP5TbieHV7w9KGvmuejs13vjSNqGUnpCW4r9xcyx6BasNgXLHgFuVCL sRyg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=ibW68/iPNDOflGmVU1S2xaLNG2b8Pnw9zPNq14nsaIg=; b=KtYsAK/4f/tSnq6TIE0GlJycz/ACxOs9EWTEz0Sr94q1d6gVYAqR+EtI/+rtNqjC4a hcr6uX78+hU+6Jx71h75/X8lP04xaZV44M7eQpz+QemG+VjpFQd7iWdUp46ionmavcF6 qbkrtPAYzpnMO2v8j2PZ5dFFanr2aPNHHAdvfJ1xi5+J0W56wh3kkdicyBSDMZD6mRKg YFbFCTM1gyVenmeRh4ofq9jRLCcm2+wBlfVN9jlThPmF4S2X97xGEZzwjKjGmGq7zz0b iMe6+3HiPa5Pw19eQ/GW5euIniKSyhC/n3B+Kw7o9udpgK2EBGbiMj58Z6g2bX/9WX1e tMRA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id k14-20020a633d0e000000b0043a20d557a9si12602969pga.229.2022.10.16.23.52.31; Sun, 16 Oct 2022 23:52:44 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230072AbiJQGvk (ORCPT + 99 others); Mon, 17 Oct 2022 02:51:40 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51064 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229963AbiJQGuy (ORCPT ); Mon, 17 Oct 2022 02:50:54 -0400 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id F421757887; Sun, 16 Oct 2022 23:50:49 -0700 (PDT) Received: from dggpemm500022.china.huawei.com (unknown [172.30.72.56]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4MrSHZ0GCyzJn5l; Mon, 17 Oct 2022 14:48:10 +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; Mon, 17 Oct 2022 14:50:42 +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; Mon, 17 Oct 2022 14:50:41 +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 v7 06/11] kallsyms: Improve the performance of kallsyms_lookup_name() when CONFIG_LTO_CLANG=y Date: Mon, 17 Oct 2022 14:49:45 +0800 Message-ID: <20221017064950.2038-7-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916673500759278?= X-GMAIL-MSGID: =?utf-8?q?1746916673500759278?= LLVM appends various suffixes for local functions and variables, suffixes observed: - foo.llvm.[0-9a-f]+ - foo.[0-9a-f]+ Therefore, when CONFIG_LTO_CLANG=y, kallsyms_lookup_name() needs to truncate the suffix of the symbol name before comparing the local function or variable name. Currently, to improve performance, we compare tokens generated by compressing the function name or variable name without suffix. However, the symbols recorded in kallsyms_names[] are compressed with suffixes. During symbol compression, the suffix header may be combined with a subsequent token to generate a new token, or may be combined with a previous token to generate a new token. This combination process must follow a strict sequence, otherwise we may not get the same result. For example: Assume that the following three combinations occur in descending order: c. > b[c.] > ab The compression result of "abc." is: "a" + "bc." The compression result of "abc" is: "ab" + "c" Therefore, when CONFIG_LTO_CLANG=y, the compression algorithm needs to be adjusted. That is, the token with the suffix header cannot be combined with the token before it. The two substrings before and after the suffix header are compressed separately. sub-string1 (function or variable name, without suffix) sub-string2 (suffix, contains suffix header '.') The implementation of the tool is as follows: 1. A new table polluted_table[] is added, it records all tokens with suffix headers after expansion. These tokens are called polluted tokens, which are polluted by suffix headers. When combined with other tokens, these tokens cannot be placed behind them. This ensures that the suffix header is at the beginning of all tokens after expansion. 2. Because the suffix needs to be processed only when CONFIG_LTO_CLANG=y, option "--lto-clang" is added, to avoid affecting the compression ratio when CONFIG_LTO_CLANG=n. According to the test result, the memory increment is less than 1KB, regardless of whether CONFIG_LTO_CLANG=y or CONFIG_LTO_CLANG=n. The implementation on the kernel side is relatively simple: 1. Compare only when the length is equal or the next token after expansion starts with suffix initial. Although there is no guarantee that this suffix initial is the suffix header, for example, the suffix may contain two '.', such as "show_cpuinfo.llvm.3123972329667954434". Don't worry, one with '.' and one without '.', the comparison is bound to fail. Signed-off-by: Zhen Lei --- kernel/kallsyms.c | 30 ++++++++++++----- scripts/kallsyms.c | 74 +++++++++++++++++++++++++++++++++++++++-- scripts/link-vmlinux.sh | 4 +++ 3 files changed, 97 insertions(+), 11 deletions(-) diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c index 7f3987cc975be3b..bd1f263b1c69b53 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -267,6 +267,25 @@ static bool cleanup_symbol_name(char *s) return false; } +/* + * Please refer to the comments in cleanup_symbol_name() for more details. + * The former is used to handle expanded symbols, while this function is used + * to handle unexpanded symbols. + */ +static bool cleanup_compressed_symbol_name(int token) +{ + char first; + + if (!IS_ENABLED(CONFIG_LTO_CLANG)) + return false; + + first = kallsyms_token_table[kallsyms_token_index[token]]; + if (first == '.') + return true; + + return false; +} + static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, unsigned long *addr) { @@ -293,7 +312,8 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, off += len; x = len - 1; - if (x != namelen) + if ((x < namelen) || + (x > namelen && !cleanup_compressed_symbol_name(name[namelen]))) continue; if (!memcmp(name, namebuf, namelen)) { @@ -309,8 +329,6 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, unsigned long kallsyms_lookup_name(const char *name) { char namebuf[KSYM_NAME_LEN]; - unsigned long i; - unsigned int off; unsigned long addr; int ret, len; @@ -323,12 +341,6 @@ 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); - } return module_kallsyms_lookup_name(name); } diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c index 9864ce5e6c5bfc1..7fbb976f3805b17 100644 --- a/scripts/kallsyms.c +++ b/scripts/kallsyms.c @@ -78,6 +78,10 @@ static unsigned int table_size, table_cnt; static int all_symbols; static int absolute_percpu; static int base_relative; +static int lto_clang; + +static unsigned char polluted_table[256]; +static unsigned char polluted_table_len; static int token_profit[0x10000]; @@ -89,7 +93,7 @@ static unsigned char best_table_len[256]; static void usage(void) { fprintf(stderr, "Usage: kallsyms [--all-symbols] [--absolute-percpu] " - "[--base-relative] in.map > out.S\n"); + "[--base-relative] [--lto-clang] in.map > out.S\n"); exit(1); } @@ -653,6 +657,67 @@ static void compress_symbols(const unsigned char *str, int idx) } } +static void init_polluted_table(void) +{ + int i; + unsigned char c; + unsigned char suffix_head[] = {'.'}; + + if (!lto_clang) + return; + + for (i = 0; i < sizeof(suffix_head); i++) { + c = suffix_head[i]; + if (best_table_len[c]) + polluted_table[polluted_table_len++] = c; + } +} + +static void update_polluted_table(unsigned char new_token) +{ + int i; + unsigned char first_token; + + if (!lto_clang) + return; + + /* + * Polluted tokens are prohibited from being at the end, so they can + * only be at the beginning, only the first sub-token needs to be + * checked. + */ + first_token = best_table[new_token][0]; + for (i = 0; i < polluted_table_len; i++) { + if (first_token == polluted_table[i]) { + polluted_table[polluted_table_len++] = new_token; + return; + } + } +} + +/* + * To ensure that the first character of the suffix(such as '.') is at the + * beginning of the expanded substring. During compression, no token with + * suffix header(all of them are recorded in polluted_table[]) is allowed + * to be at the end. + */ +static bool is_forbidden(int index) +{ + int i; + unsigned char last_token; + + if (!lto_clang) + return false; + + last_token = (index >> 8) & 0xFF; + for (i = 0; i < polluted_table_len; i++) { + if (last_token == polluted_table[i]) + return true; + } + + return false; +} + /* search the token with the maximum profit */ static int find_best_token(void) { @@ -662,7 +727,7 @@ static int find_best_token(void) best = 0; for (i = 0; i < 0x10000; i++) { - if (token_profit[i] > bestprofit) { + if ((token_profit[i] > bestprofit) && !is_forbidden(i)) { best = i; bestprofit = token_profit[i]; } @@ -693,6 +758,8 @@ static void optimize_result(void) best_table[i][0] = best & 0xFF; best_table[i][1] = (best >> 8) & 0xFF; + update_polluted_table((unsigned char)i); + /* replace this token in all the valid symbols */ compress_symbols(best_table[i], i); } @@ -715,6 +782,8 @@ static void insert_real_symbols_in_table(void) best_table[c][0] = c; best_table_len[c] = 1; } + + init_polluted_table(); } static void optimize_token_table(void) @@ -839,6 +908,7 @@ int main(int argc, char **argv) {"all-symbols", no_argument, &all_symbols, 1}, {"absolute-percpu", no_argument, &absolute_percpu, 1}, {"base-relative", no_argument, &base_relative, 1}, + {"lto-clang", no_argument, <o_clang, 1}, {}, }; diff --git a/scripts/link-vmlinux.sh b/scripts/link-vmlinux.sh index 918470d768e9c7d..32e573943cf036b 100755 --- a/scripts/link-vmlinux.sh +++ b/scripts/link-vmlinux.sh @@ -156,6 +156,10 @@ kallsyms() kallsymopt="${kallsymopt} --base-relative" fi + if is_enabled CONFIG_LTO_CLANG; then + kallsymopt="${kallsymopt} --lto-clang" + fi + info KSYMS ${2} scripts/kallsyms ${kallsymopt} ${1} > ${2} } From patchwork Mon Oct 17 06:49:46 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3240 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303874wrs; Sun, 16 Oct 2022 23:53:49 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5YzRNT82FuBIJQUCarZiJYw2qHTUEiHg5YCM9GqO9V5EtQw/3pXo8nu79TaRSgP5JoqHJA X-Received: by 2002:a17:90b:1242:b0:20a:f75c:de7 with SMTP id gx2-20020a17090b124200b0020af75c0de7mr32549242pjb.70.1665989629549; Sun, 16 Oct 2022 23:53:49 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989629; cv=none; d=google.com; s=arc-20160816; b=iQqPnEG0E8xUiwC3b8qB9AIl950IoKBTIkOmAHHhswjorWhpOB/kfdpgXID6fdIC/w VYU96ofCoW2FxaAYsgVSwjhfp73YtTuN+K3AZ25yOSo9+oaYsAkz9XCugndTOwv0LSOv aXMvMmEglsdPFWoIz6efvf64KZNWdJVeCSIEbWO7nKDoP53QzkzmhO3p02JfuhONPX+Z JVzDV0GIH/xnlcklygm4ed1yeqwIybywx3JW+N3PDCvNvdZcDkJskwZ88aIqDpQsm/As fZfWrn52+asgZwpMSRX+dcgR5aPPCNc31fb8Jd4Kw20GAqyRoG3eujDjTqFegEEgIHbx pBVw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=NIUcwOJ2uQnqU8kjaXNKO6houACo5d0WwezPl00KdX4=; b=XERaQroO+pH4FiHpCVTyaJStK8z1It20rX/Jls0HxQgwL1on4Q9ymB7SHekHwpY8g4 ByMsuQ1ICdBsQDZ/NNZWCnMrosAMP1gj1Re4q3lI4xil2xvHl1qhyhyUtxHXsOlAWPdC OqEEVuicrn6cqlamvkKiWxMIU6cZSYKKOl3txfEUcKoD4HSbkPnXvr/l9hAV4uScTxhu fGzgFJjIlDNXJMddNGZbR9vxwBJHXqKdOyYELZ5Tr/nwo+mHD9jDjc9KT9uL27hQguzi iQ8Lc7OqsFQ4b2dj4C3mflSrHCiTx6er08QraTh5KIR86PQ+sV1T0EiakeJSEuMoUHcv QCgA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id n15-20020a170902f60f00b0017f8290fcf0si10992991plg.272.2022.10.16.23.53.37; Sun, 16 Oct 2022 23:53:49 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230237AbiJQGwd (ORCPT + 99 others); Mon, 17 Oct 2022 02:52:33 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:53090 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230227AbiJQGwD (ORCPT ); Mon, 17 Oct 2022 02:52:03 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CDD6A5809C; Sun, 16 Oct 2022 23:51:08 -0700 (PDT) Received: from dggpemm500023.china.huawei.com (unknown [172.30.72.53]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MrSFX63pNzmVSC; Mon, 17 Oct 2022 14:46:24 +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; Mon, 17 Oct 2022 14:50:43 +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; Mon, 17 Oct 2022 14:50:42 +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 v7 07/11] kallsyms: Add helper kallsyms_on_each_match_symbol() Date: Mon, 17 Oct 2022 14:49:46 +0800 Message-ID: <20221017064950.2038-8-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916742103252237?= X-GMAIL-MSGID: =?utf-8?q?1746916742103252237?= 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 649faac31ddb162..0cd33be7142ad0d 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 bd1f263b1c69b53..a1d3aa2c44e8d6f 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -286,14 +286,17 @@ static bool cleanup_compressed_symbol_name(int token) return false; } -static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, - unsigned long *addr) +static int __kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, + unsigned int *index, + unsigned int *offset, + unsigned long *addr) { - unsigned int i, off; + unsigned int i = *index; + unsigned int off = *offset; unsigned int len, x; const unsigned char *name; - for (i = 0, off = 0; namelen && i < kallsyms_num_syms; i++) { + for (; namelen && i < kallsyms_num_syms; i++) { /* * For each entry in kallsyms_names[], the storage format is: * ---------------------------- @@ -317,6 +320,10 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, continue; if (!memcmp(name, namebuf, namelen)) { + /* Prepare for the next iteration */ + *index = i + 1; + *offset = off; + *addr = kallsyms_sym_address(i); return 0; } @@ -325,6 +332,14 @@ static int kallsyms_lookup_compressed_name(unsigned char *namebuf, int namelen, 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) { @@ -367,6 +382,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 Mon Oct 17 06:49:47 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3235 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303610wrs; Sun, 16 Oct 2022 23:52:48 -0700 (PDT) X-Google-Smtp-Source: AMsMyM6uo/mBOuW870m6sn5oi1O1eYe2o8KFskhzpdymyGntataO18jMnUfXQ3UgBxOAgVQSVZ4r X-Received: by 2002:a63:804a:0:b0:461:25fe:e7c5 with SMTP id j71-20020a63804a000000b0046125fee7c5mr899556pgd.395.1665989568276; Sun, 16 Oct 2022 23:52:48 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989568; cv=none; d=google.com; s=arc-20160816; b=aH+tSYRmon8Ssm+E4dqgevbPzCL0ouIpYHO89gCqB+ZFMASGhKOlOjRIWCLgo2dD9D a64DB5CB2Fb8LESlAfOdsfoMSqlP2BF7tEmYdiJtmLNW4hSyPEHWku2dg3elG+XWSiby oIZNC7hYot24lkcZ94wDclCNkptF0LYBsli/SmH6nICHP0OCj61THr9oupjeUqOe7FUH tIGDp7+sRMTwd3lz4w4c86Jm3yiFn43HGLq1iKECS1uL3Lfo5fOkBfFZHtpsXPXLnOx7 f17WKwNBtaMlt2GeVnicIJ/iB242EWuQs/sz29dxpklBctzKcOdMQhcfzrNEYiCY19xh a8Kw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=T450yJZh4GvXL7uMU2jqhwhOgLb71ZEducUmipNOAus=; b=nUNHvJA25xaTQsQJgReGtX8EEtYMNadyvIwSABOW235AWVD6DTJloGgmlU6BK2mTTN pwcP7u1w6MwXnOtzYHlMQfYNv91Z7o45ax/fhVvxxMkLOlsIcPkSaeIzu3rLpVFm5gmW tKwcn/XwxZ42tgxIze1V57KzrXRzYQgM+x1c6flRdmr6xcV7eyHo4HxgYTpvoGN4S49E 0uYEWQ+hT0xzSvaacoXNbT2IjyS9sfbuMPmGAiC83QXO0JszjxRHTCAwbTrax8cyPlUC MTyzO11jugVPfnGx8eod3iNizl4xnFPBnW56VtzWwNFK6pvvtNxQ+06EIWHIoOOiWusM 6JPw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id z11-20020a170903018b00b00183243c7a2dsi10489910plg.406.2022.10.16.23.52.35; Sun, 16 Oct 2022 23:52:48 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230111AbiJQGvn (ORCPT + 99 others); Mon, 17 Oct 2022 02:51:43 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51028 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230026AbiJQGuz (ORCPT ); Mon, 17 Oct 2022 02:50:55 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id A6977578BB; Sun, 16 Oct 2022 23:50:51 -0700 (PDT) Received: from dggpemm500024.china.huawei.com (unknown [172.30.72.55]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MrSGs5ZwszpWQ0; Mon, 17 Oct 2022 14:47:33 +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; Mon, 17 Oct 2022 14:50:44 +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; Mon, 17 Oct 2022 14:50:43 +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 v7 08/11] livepatch: Use kallsyms_on_each_match_symbol() to improve performance Date: Mon, 17 Oct 2022 14:49:47 +0800 Message-ID: <20221017064950.2038-9-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916677529785879?= X-GMAIL-MSGID: =?utf-8?q?1746916677529785879?= 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 9ada0bc5247be5d..50bfc3481a4ee38 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 Mon Oct 17 06:49:48 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3242 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1304046wrs; Sun, 16 Oct 2022 23:54:38 -0700 (PDT) X-Google-Smtp-Source: AMsMyM4Ov6o5XzA0tsVP3haEn3Qcnp5seoWxw+6AqihKYXizts9L6P7VRh/wD7E+Fgs81BRgrgvP X-Received: by 2002:aa7:958f:0:b0:563:6987:8b88 with SMTP id z15-20020aa7958f000000b0056369878b88mr10855781pfj.31.1665989677924; Sun, 16 Oct 2022 23:54:37 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989677; cv=none; d=google.com; s=arc-20160816; b=YUiuO+mZE/kg1ShFNrn/jGEFnx3g3ocpqM+y3E0WH2urEsqL8IlbkMb2Pzp8nvsg+0 VIxnwVgsK8r58Zg0GS8dbauSmzLKOc5v4fcV7sS29ZhPpW6A/NL0+ZBwY0e3AnvILbR4 BfQqfJwpG2ezGqdfwtdNEU4PLByiT+8S2ikvzXSYDosvXJ+EkDoHwtNWEgq/uxXe1fQm Vz7qfvPxgROVM8F7HGptBYJehneua/sHX4iP5Iudcsr4zAE1S5FRAISmEknEGuqGWMja Ai97HYjVaMIIOP/TVyMS2pCA/KUqyGwIVeJqGppL1Do7fq1M4mLI9MvWN6DkXFVKJSW5 0y8Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=x+qI4LJ5JrJ3M7Q1W5gysaPj0SLVspAorDwDzXWWRbQ=; b=U6mMxG7olC0xm+7nIBuGx50gu8OxGQAY2VUCqSMBjCcxa9DyhXZzhr01a4TcgcnXdB 15GhPqnFfX85FX5MC2Lt7H12XVzpNtJp9ghBDURKWse7p+tDvTDKC7QnzvgrB5WF5nup KE0ZOmpwAfqGOPOI3roMaCsvpaxYd21mpcnJFQdPfeVfKQKVADwksPjKLGm+nLtS5otx Dq9aV52aCebpDm1If/wy1uqjippSBY51Nrtsas6rIXUqU8eOpQ/+fLxDCMv+Oq+PQg7w MHlT8f095h/kt8BSm1Vhp99N3DPVtBSCIimiicV2sNUDahjbwMNbllrBJyouyasBILmL 3U0A== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id b9-20020a170902d50900b001783df7f2e9si353614plg.166.2022.10.16.23.54.25; Sun, 16 Oct 2022 23:54:37 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230193AbiJQGxh (ORCPT + 99 others); Mon, 17 Oct 2022 02:53:37 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52026 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230189AbiJQGxS (ORCPT ); Mon, 17 Oct 2022 02:53:18 -0400 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id AC59C580A1; Sun, 16 Oct 2022 23:52:11 -0700 (PDT) Received: from dggpemm500021.china.huawei.com (unknown [172.30.72.53]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4MrSJl6nMmzJn56; Mon, 17 Oct 2022 14:49:11 +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; Mon, 17 Oct 2022 14:50:45 +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; Mon, 17 Oct 2022 14:50:44 +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 v7 09/11] livepatch: Improve the search performance of module_kallsyms_on_each_symbol() Date: Mon, 17 Oct 2022 14:49:48 +0800 Message-ID: <20221017064950.2038-10-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS,T_FILL_THIS_FORM_SHORT autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916792485905115?= X-GMAIL-MSGID: =?utf-8?q?1746916792485905115?= 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 ec61fb53979a92a..0a3b44ff885a48c 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 50bfc3481a4ee38..d4fe2d1b0e562bc 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 Mon Oct 17 06:49:49 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3243 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1304110wrs; Sun, 16 Oct 2022 23:54:54 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5ChK4HQuC44dInqlK0nTtrL5UApVwId3ZZwDLN4Xw0cOsB0Le479xTnRYzwCyybsiZCn0k X-Received: by 2002:a17:903:2585:b0:185:483e:e4ce with SMTP id jb5-20020a170903258500b00185483ee4cemr10376615plb.17.1665989693907; Sun, 16 Oct 2022 23:54:53 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989693; cv=none; d=google.com; s=arc-20160816; b=dlnLNIkFzUiiwtngp7LF2sAA9TXGsR4I/++ErxV1DXNW16I6LfYfkJAXXcpE7P4xWC Ly8XPw1RR5DYBAOSC5s79qFduaMk4sIyP2Mw1P+4AzDaJpfR+yFYdf33BHFjtlVLhROP ZhTUcXqmpiMd6CyggyMj7kVUVw23ICkvwgIbFO9tto/lEsE2kcYLfP9AFthEUa8x6SyD xxrbCb4C3gp5nCl0cwOgngb7VIDykJSjq3SIsmRQ5ENonzs0dxd36yxh/lRzu6Nr45u9 ojpZNQHF4zx8YZKJKYg2JWJvW3A/IQfnPP4h4+mxv4/+bUWqPtwEl/YXehkxgDZnEvYF QUYg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=1lrzctejlCIsKw7PwWgi0IFpQXygAWq1apD+7MY6U1s=; b=IIklw3LxK3FZk/Xr9eqszKavv+dI6ZmVTHpsfer9dIbuRQKLBMmrCrjEaj86q2k9+3 QoN/G5ueSQObKdg3ratslEfXBFz9FsX/GW4Qvp+VCtshFbpdfjTOHLIkJX6X/Foa+uHq e6yQYWqXtknzQQXv9iR6ZTzYlv5fsD1ih2PPbwbLkA2c2JHail3KI+eoV5ktSbsvFjdl gGyYg7NxiItNTjMRtFhrFoR3Ov7wI2WMG/OoeoSOKy6V3HLtkPL3Yj2YSudovLg062jY tRtX9FqqGQ8AQkxKLoUsNbD/uCOZpaR5laqQeSokaQLwschDfEw7GSInuurM09GtDeck hIQA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id m2-20020a656a02000000b00452bad3abcfsi13427492pgu.324.2022.10.16.23.54.38; Sun, 16 Oct 2022 23:54:53 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229989AbiJQGwp (ORCPT + 99 others); Mon, 17 Oct 2022 02:52:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:52412 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230187AbiJQGwI (ORCPT ); Mon, 17 Oct 2022 02:52:08 -0400 Received: from szxga01-in.huawei.com (szxga01-in.huawei.com [45.249.212.187]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E8BBC580A8; Sun, 16 Oct 2022 23:51:09 -0700 (PDT) Received: from dggpemm500020.china.huawei.com (unknown [172.30.72.57]) by szxga01-in.huawei.com (SkyGuard) with ESMTP id 4MrSFY5hd0zmVqY; Mon, 17 Oct 2022 14:46:25 +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; Mon, 17 Oct 2022 14:50:46 +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; Mon, 17 Oct 2022 14:50:45 +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 v7 10/11] kallsyms: Delete an unused parameter related to kallsyms_on_each_symbol() Date: Mon, 17 Oct 2022 14:49:49 +0800 Message-ID: <20221017064950.2038-11-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916809063739772?= X-GMAIL-MSGID: =?utf-8?q?1746916809063739772?= 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 0cd33be7142ad0d..5002ebe9dff5a0e 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 a1d3aa2c44e8d6f..017fe0570d5f348 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -363,8 +363,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]; @@ -374,7 +373,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 fbf2543111c05c2..e3ef4f0defb2e37 100644 --- a/kernel/trace/ftrace.c +++ b/kernel/trace/ftrace.c @@ -8267,8 +8267,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 Mon Oct 17 06:49:50 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhen Lei X-Patchwork-Id: 3236 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a5d:4ac7:0:0:0:0:0 with SMTP id y7csp1303621wrs; Sun, 16 Oct 2022 23:52:52 -0700 (PDT) X-Google-Smtp-Source: AMsMyM5X3K9tknW9q/Uh4j/72XA/4XQhqSzEjZuJs52crceBE1o8fvu11iXonCxisy48tKSIS6OA X-Received: by 2002:a05:6a00:1501:b0:563:9f05:bd6e with SMTP id q1-20020a056a00150100b005639f05bd6emr11189575pfu.48.1665989572583; Sun, 16 Oct 2022 23:52:52 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1665989572; cv=none; d=google.com; s=arc-20160816; b=vWa28ydmffbUQskLbt/hho6EOwjCxwbslIHVMH5C8JCsAdQXzm3uRHb3mApOofdUrP pG+8eYWH0VXQyblTK0bcL2F7D1tHlTj/apsCoNsjn41NkG8j2mub93nYWu8En9swg1sO C0qhmrGCideG4Ns0BirS5cIpkhxEEqaACEAEOW5HwM7WftbAIIChfVQ50gJKvDTqXaNw AUntIvYhWDLDTZnqhukLKjK2ODOc1yKUImG6xwlo/UhOGCEF6+wrFI6LlBPGYGMh/0AQ i9G44NvI6VV80/Cy/2NQV8WD9+kfPzKvXCBSOGcI/j5rMeGnSp6Q0MTq0SwqSG7cW2vG LxvA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=8FFB6eMVaFCHc/f4bYaP0VNUls2SowcsMwQKHAVOxzA=; b=pFtDvjp0BGB1jWn7YKZgawAUrK4w0ngPuuf+glxli0MfVsnJG6nl8IZIZXSg30RBUr eE5A/wY+ZVyql0/df+Fzfcnic72jpy9REtakJo4JUSIsQDWlUOPbVaOdv84tRA7IgNs2 4qRMRKaLuH5CoLatnJIHnPBfJu1iDK+lFpEjekHH9Fg9FuUKI3dCcDzYtd7AwYRPITP7 u2JNNXFI4GqU11JkHlHhHpjiEn2l8EldNiJJe931AfoXvvw+s6UzT3GG9RD495CPKhIk mAKoGcXOEP30svX/E0DH6UIxeBsqiPyTNM3TPqwYyt56Z8Bv+EtN0N/ili7//LB9B/QZ pGmw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id x70-20020a638649000000b004632044db0asi9765992pgd.190.2022.10.16.23.52.39; Sun, 16 Oct 2022 23:52:52 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230126AbiJQGvp (ORCPT + 99 others); Mon, 17 Oct 2022 02:51:45 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:51094 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230039AbiJQGuz (ORCPT ); Mon, 17 Oct 2022 02:50:55 -0400 Received: from szxga03-in.huawei.com (szxga03-in.huawei.com [45.249.212.189]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 5A000578AF; Sun, 16 Oct 2022 23:50:51 -0700 (PDT) Received: from dggpemm500022.china.huawei.com (unknown [172.30.72.56]) by szxga03-in.huawei.com (SkyGuard) with ESMTP id 4MrSHc15ZszJn5Q; Mon, 17 Oct 2022 14:48:12 +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; Mon, 17 Oct 2022 14:50:47 +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; Mon, 17 Oct 2022 14:50:46 +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 v7 11/11] kallsyms: Add self-test facility Date: Mon, 17 Oct 2022 14:49:50 +0800 Message-ID: <20221017064950.2038-12-thunder.leizhen@huawei.com> X-Mailer: git-send-email 2.37.3.windows.1 In-Reply-To: <20221017064950.2038-1-thunder.leizhen@huawei.com> References: <20221017064950.2038-1-thunder.leizhen@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.174.178.55] X-ClientProxiedBy: dggems702-chm.china.huawei.com (10.3.19.179) To dggpemm500006.china.huawei.com (7.185.36.236) X-CFilter-Loop: Reflected X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_MED, SPF_HELO_NONE,SPF_PASS autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1746916681707722501?= X-GMAIL-MSGID: =?utf-8?q?1746916681707722501?= 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 | 464 +++++++++++++++++++++++++++++++++++++ 5 files changed, 480 insertions(+), 1 deletion(-) create mode 100644 kernel/kallsyms_selftest.c diff --git a/include/linux/kallsyms.h b/include/linux/kallsyms.h index 5002ebe9dff5a0e..d4079b3d951d1ef 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 694f7c160c9c107..90c8aa75a6495a6 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -1723,6 +1723,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 d754e0be1176df3..e7fc37a6806979f 100644 --- a/kernel/Makefile +++ b/kernel/Makefile @@ -69,6 +69,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 017fe0570d5f348..f886bc71630d486 100644 --- a/kernel/kallsyms.c +++ b/kernel/kallsyms.c @@ -226,7 +226,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..d6736e7fb2b0bc5 --- /dev/null +++ b/kernel/kallsyms_selftest.c @@ -0,0 +1,464 @@ +// 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; + int perf; + 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 = (u32)div_u64(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 bool match_cleanup_name(const char *s, const char *name) +{ + char *p; + int len; + + if (!IS_ENABLED(CONFIG_LTO_CLANG)) + return false; + + p = strchr(s, '.'); + if (!p) + return false; + + len = strlen(name); + if (p - s != len) + return false; + + return !strncmp(s, name, len); +} + +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->perf && match_cleanup_name(name, stat->name))) { + 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; + stat.perf = 1; + 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, lookup_addr; + char namebuf[KSYM_NAME_LEN]; + struct test_stat stat, 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; + } + + /* + * The first '.' may be the initial letter, in which case the + * entire symbol name will be truncated to an empty string in + * cleanup_symbol_name(). Do not test these symbols. + * + * For example: + * cat /proc/kallsyms | awk '{print $3}' | grep -E "^\." | head + * .E_read_words + * .E_leading_bytes + * .E_trailing_bytes + * .E_write_words + * .E_copy + * .str.292.llvm.12122243386960820698 + * .str.24.llvm.12122243386960820698 + * .str.29.llvm.12122243386960820698 + * .str.75.llvm.12122243386960820698 + * .str.99.llvm.12122243386960820698 + */ + if (IS_ENABLED(CONFIG_LTO_CLANG) && !namebuf[0]) + continue; + + lookup_addr = kallsyms_lookup_name(namebuf); + + memset(&stat, 0, sizeof(stat)); + stat.max = INT_MAX; + kallsyms_on_each_match_symbol(match_symbol, namebuf, &stat); + + /* + * 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 (stat.addr != stat2.addr || + stat.real_cnt != stat2.real_cnt || + memcmp(stat.addrs, stat2.addrs, + stat.save_cnt * sizeof(stat.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 (!stat.real_cnt) + goto failed; + + /* + * kallsyms_lookup_name() returns the address of the first + * symbol found and cannot be NULL. + */ + if (!lookup_addr || lookup_addr != stat.addrs[0]) + goto failed; + + /* + * If the addresses of all matching symbols are recorded, the + * target address needs to be exist. + */ + if (stat.real_cnt <= MAX_NUM_OF_RECORDS) { + for (j = 0; j < stat.save_cnt; j++) { + if (stat.addrs[j] == addr) + break; + } + + if (j == stat.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);