linux-kernel - [PATCH 1/6] kallsyms: Optimize multiple times of realloc() to one time of malloc()

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20240613133711.2867745-2-zhengyejian1@huawei.com>
Date: Thu, 13 Jun 2024 21:37:06 +0800
From: Zheng Yejian <zhengyejian1@...wei.com>
To: <rostedt@...dmis.org>, <mhiramat@...nel.org>, <mark.rutland@....com>,
	<mpe@...erman.id.au>, <npiggin@...il.com>, <christophe.leroy@...roup.eu>,
	<naveen.n.rao@...ux.ibm.com>, <tglx@...utronix.de>, <mingo@...hat.com>,
	<bp@...en8.de>, <dave.hansen@...ux.intel.com>, <x86@...nel.org>,
	<hpa@...or.com>, <mcgrof@...nel.org>, <mathieu.desnoyers@...icios.com>,
	<masahiroy@...nel.org>, <nathan@...nel.org>, <nicolas@...sle.eu>,
	<kees@...nel.org>, <james.clark@....com>, <kent.overstreet@...ux.dev>,
	<yhs@...com>, <jpoimboe@...nel.org>, <peterz@...radead.org>
CC: <zhengyejian1@...wei.com>, <linux-kernel@...r.kernel.org>,
	<linux-trace-kernel@...r.kernel.org>, <linuxppc-dev@...ts.ozlabs.org>,
	<linux-modules@...r.kernel.org>, <linux-kbuild@...r.kernel.org>,
	<bpf@...r.kernel.org>
Subject: [PATCH 1/6] kallsyms: Optimize multiple times of realloc() to one time of malloc()

Array 'table' is used to store pointers of symbols that read from in.map
file, and its size depends on the number of symbols. Currently 'table'
is expanded by calling realloc() every 10000 symbols read.

However, there generally are around 100000+ symbols, which means that
the expansion is generally 10+ times.

As an optimization, introduce linked list 'sym_list' to associate and
count all symbols, then store them into 'table' at one time.

Signed-off-by: Zheng Yejian <zhengyejian1@...wei.com>
---
 scripts/kallsyms.c | 33 ++++++++++++++++++++-------------
 1 file changed, 20 insertions(+), 13 deletions(-)

diff --git a/scripts/kallsyms.c b/scripts/kallsyms.c
index 47978efe4797..6559a9802f6e 100644
--- a/scripts/kallsyms.c
+++ b/scripts/kallsyms.c
@@ -33,6 +33,7 @@
 #define KSYM_NAME_LEN		512
 
 struct sym_entry {
+	struct sym_entry *next;
 	unsigned long long addr;
 	unsigned int len;
 	unsigned int seq;
@@ -60,7 +61,8 @@ static struct addr_range percpu_range = {
 };
 
 static struct sym_entry **table;
-static unsigned int table_size, table_cnt;
+static struct sym_entry *sym_list;
+static unsigned int table_cnt;
 static int all_symbols;
 static int absolute_percpu;
 static int base_relative;
@@ -273,6 +275,7 @@ static void read_map(const char *in)
 	struct sym_entry *sym;
 	char *buf = NULL;
 	size_t buflen = 0;
+	int i;
 
 	fp = fopen(in, "r");
 	if (!fp) {
@@ -286,18 +289,22 @@ static void read_map(const char *in)
 			continue;
 
 		sym->start_pos = table_cnt;
-
-		if (table_cnt >= table_size) {
-			table_size += 10000;
-			table = realloc(table, sizeof(*table) * table_size);
-			if (!table) {
-				fprintf(stderr, "out of memory\n");
-				fclose(fp);
-				exit (1);
-			}
-		}
-
-		table[table_cnt++] = sym;
+		table_cnt++;
+		sym->next = sym_list;
+		sym_list = sym;
+	}
+	table = malloc(sizeof(*table) * table_cnt);
+	if (!table) {
+		fprintf(stderr, "unable to allocate memory for table\n");
+		free(buf);
+		fclose(fp);
+		exit(EXIT_FAILURE);
+	}
+	sym = sym_list;
+	i = table_cnt - 1;
+	while (sym) {
+		table[i--] = sym;
+		sym = sym->next;
 	}
 
 	free(buf);
-- 
2.25.1