1// SPDX-License-Identifier: GPL-2.0-or-later
2/*
3 * Test the function and performance of kallsyms
4 *
5 * Copyright (C) Huawei Technologies Co., Ltd., 2022
6 *
7 * Authors: Zhen Lei <thunder.leizhen@huawei.com> Huawei
8 */
9
10#define pr_fmt(fmt) "kallsyms_selftest: " fmt
11
12#include <linux/init.h>
13#include <linux/module.h>
14#include <linux/kallsyms.h>
15#include <linux/random.h>
16#include <linux/sched/clock.h>
17#include <linux/kthread.h>
18#include <linux/vmalloc.h>
19
20#include "kallsyms_internal.h"
21#include "kallsyms_selftest.h"
22
23
24#define MAX_NUM_OF_RECORDS		64
25
26struct test_stat {
27	int min;
28	int max;
29	int save_cnt;
30	int real_cnt;
31	int perf;
32	u64 sum;
33	char *name;
34	unsigned long addr;
35	unsigned long addrs[MAX_NUM_OF_RECORDS];
36};
37
38struct test_item {
39	char *name;
40	unsigned long addr;
41};
42
43#define ITEM_FUNC(s)				\
44	{					\
45		.name = #s,			\
46		.addr = (unsigned long)s,	\
47	}
48
49#define ITEM_DATA(s)				\
50	{					\
51		.name = #s,			\
52		.addr = (unsigned long)&s,	\
53	}
54
55
56static int kallsyms_test_var_bss_static;
57static int kallsyms_test_var_data_static = 1;
58int kallsyms_test_var_bss;
59int kallsyms_test_var_data = 1;
60
61static int kallsyms_test_func_static(void)
62{
63	kallsyms_test_var_bss_static++;
64	kallsyms_test_var_data_static++;
65
66	return 0;
67}
68
69int kallsyms_test_func(void)
70{
71	return kallsyms_test_func_static();
72}
73
74__weak int kallsyms_test_func_weak(void)
75{
76	kallsyms_test_var_bss++;
77	kallsyms_test_var_data++;
78	return 0;
79}
80
81static struct test_item test_items[] = {
82	ITEM_FUNC(kallsyms_test_func_static),
83	ITEM_FUNC(kallsyms_test_func),
84	ITEM_FUNC(kallsyms_test_func_weak),
85	ITEM_FUNC(vmalloc),
86	ITEM_FUNC(vfree),
87#ifdef CONFIG_KALLSYMS_ALL
88	ITEM_DATA(kallsyms_test_var_bss_static),
89	ITEM_DATA(kallsyms_test_var_data_static),
90	ITEM_DATA(kallsyms_test_var_bss),
91	ITEM_DATA(kallsyms_test_var_data),
92#endif
93};
94
95static char stub_name[KSYM_NAME_LEN];
96
97static int stat_symbol_len(void *data, const char *name, unsigned long addr)
98{
99	*(u32 *)data += strlen(name);
100
101	return 0;
102}
103
104static void test_kallsyms_compression_ratio(void)
105{
106	u32 pos, off, len, num;
107	u32 ratio, total_size, total_len = 0;
108
109	kallsyms_on_each_symbol(stat_symbol_len, &total_len);
110
111	/*
112	 * A symbol name cannot start with a number. This stub name helps us
113	 * traverse the entire symbol table without finding a match. It's used
114	 * for subsequent performance tests, and its length is the average
115	 * length of all symbol names.
116	 */
117	memset(stub_name, '4', sizeof(stub_name));
118	pos = total_len / kallsyms_num_syms;
119	stub_name[pos] = 0;
120
121	pos = 0;
122	num = 0;
123	off = 0;
124	while (pos < kallsyms_num_syms) {
125		len = kallsyms_names[off];
126		num++;
127		off++;
128		pos++;
129		if ((len & 0x80) != 0) {
130			len = (len & 0x7f) | (kallsyms_names[off] << 7);
131			num++;
132			off++;
133		}
134		off += len;
135	}
136
137	/*
138	 * 1. The length fields is not counted
139	 * 2. The memory occupied by array kallsyms_token_table[] and
140	 *    kallsyms_token_index[] needs to be counted.
141	 */
142	total_size = off - num;
143	pos = kallsyms_token_index[0xff];
144	total_size += pos + strlen(&kallsyms_token_table[pos]) + 1;
145	total_size += 0x100 * sizeof(u16);
146
147	pr_info(" ---------------------------------------------------------\n");
148	pr_info("| nr_symbols | compressed size | original size | ratio(%%) |\n");
149	pr_info("|---------------------------------------------------------|\n");
150	ratio = (u32)div_u64(10000ULL * total_size, total_len);
151	pr_info("| %10d |    %10d   |   %10d  |  %2d.%-2d   |\n",
152		kallsyms_num_syms, total_size, total_len, ratio / 100, ratio % 100);
153	pr_info(" ---------------------------------------------------------\n");
154}
155
156static int lookup_name(void *data, const char *name, unsigned long addr)
157{
158	u64 t0, t1, t;
159	struct test_stat *stat = (struct test_stat *)data;
160
161	t0 = ktime_get_ns();
162	(void)kallsyms_lookup_name(name);
163	t1 = ktime_get_ns();
164
165	t = t1 - t0;
166	if (t < stat->min)
167		stat->min = t;
168
169	if (t > stat->max)
170		stat->max = t;
171
172	stat->real_cnt++;
173	stat->sum += t;
174
175	return 0;
176}
177
178static void test_perf_kallsyms_lookup_name(void)
179{
180	struct test_stat stat;
181
182	memset(&stat, 0, sizeof(stat));
183	stat.min = INT_MAX;
184	kallsyms_on_each_symbol(lookup_name, &stat);
185	pr_info("kallsyms_lookup_name() looked up %d symbols\n", stat.real_cnt);
186	pr_info("The time spent on each symbol is (ns): min=%d, max=%d, avg=%lld\n",
187		stat.min, stat.max, div_u64(stat.sum, stat.real_cnt));
188}
189
190static bool match_cleanup_name(const char *s, const char *name)
191{
192	char *p;
193	int len;
194
195	if (!IS_ENABLED(CONFIG_LTO_CLANG))
196		return false;
197
198	p = strstr(s, ".llvm.");
199	if (!p)
200		return false;
201
202	len = strlen(name);
203	if (p - s != len)
204		return false;
205
206	return !strncmp(s, name, len);
207}
208
209static int find_symbol(void *data, const char *name, unsigned long addr)
210{
211	struct test_stat *stat = (struct test_stat *)data;
212
213	if (strcmp(name, stat->name) == 0 ||
214	    (!stat->perf && match_cleanup_name(name, stat->name))) {
215		stat->real_cnt++;
216		stat->addr = addr;
217
218		if (stat->save_cnt < MAX_NUM_OF_RECORDS) {
219			stat->addrs[stat->save_cnt] = addr;
220			stat->save_cnt++;
221		}
222
223		if (stat->real_cnt == stat->max)
224			return 1;
225	}
226
227	return 0;
228}
229
230static void test_perf_kallsyms_on_each_symbol(void)
231{
232	u64 t0, t1;
233	struct test_stat stat;
234
235	memset(&stat, 0, sizeof(stat));
236	stat.max = INT_MAX;
237	stat.name = stub_name;
238	stat.perf = 1;
239	t0 = ktime_get_ns();
240	kallsyms_on_each_symbol(find_symbol, &stat);
241	t1 = ktime_get_ns();
242	pr_info("kallsyms_on_each_symbol() traverse all: %lld ns\n", t1 - t0);
243}
244
245static int match_symbol(void *data, unsigned long addr)
246{
247	struct test_stat *stat = (struct test_stat *)data;
248
249	stat->real_cnt++;
250	stat->addr = addr;
251
252	if (stat->save_cnt < MAX_NUM_OF_RECORDS) {
253		stat->addrs[stat->save_cnt] = addr;
254		stat->save_cnt++;
255	}
256
257	if (stat->real_cnt == stat->max)
258		return 1;
259
260	return 0;
261}
262
263static void test_perf_kallsyms_on_each_match_symbol(void)
264{
265	u64 t0, t1;
266	struct test_stat stat;
267
268	memset(&stat, 0, sizeof(stat));
269	stat.max = INT_MAX;
270	stat.name = stub_name;
271	t0 = ktime_get_ns();
272	kallsyms_on_each_match_symbol(match_symbol, stat.name, &stat);
273	t1 = ktime_get_ns();
274	pr_info("kallsyms_on_each_match_symbol() traverse all: %lld ns\n", t1 - t0);
275}
276
277static int test_kallsyms_basic_function(void)
278{
279	int i, j, ret;
280	int next = 0, nr_failed = 0;
281	char *prefix;
282	unsigned short rand;
283	unsigned long addr, lookup_addr;
284	char namebuf[KSYM_NAME_LEN];
285	struct test_stat *stat, *stat2;
286
287	stat = kmalloc(sizeof(*stat) * 2, GFP_KERNEL);
288	if (!stat)
289		return -ENOMEM;
290	stat2 = stat + 1;
291
292	prefix = "kallsyms_lookup_name() for";
293	for (i = 0; i < ARRAY_SIZE(test_items); i++) {
294		addr = kallsyms_lookup_name(test_items[i].name);
295		if (addr != test_items[i].addr) {
296			nr_failed++;
297			pr_info("%s %s failed: addr=%lx, expect %lx\n",
298				prefix, test_items[i].name, addr, test_items[i].addr);
299		}
300	}
301
302	prefix = "kallsyms_on_each_symbol() for";
303	for (i = 0; i < ARRAY_SIZE(test_items); i++) {
304		memset(stat, 0, sizeof(*stat));
305		stat->max = INT_MAX;
306		stat->name = test_items[i].name;
307		kallsyms_on_each_symbol(find_symbol, stat);
308		if (stat->addr != test_items[i].addr || stat->real_cnt != 1) {
309			nr_failed++;
310			pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
311				prefix, test_items[i].name,
312				stat->real_cnt, stat->addr, test_items[i].addr);
313		}
314	}
315
316	prefix = "kallsyms_on_each_match_symbol() for";
317	for (i = 0; i < ARRAY_SIZE(test_items); i++) {
318		memset(stat, 0, sizeof(*stat));
319		stat->max = INT_MAX;
320		stat->name = test_items[i].name;
321		kallsyms_on_each_match_symbol(match_symbol, test_items[i].name, stat);
322		if (stat->addr != test_items[i].addr || stat->real_cnt != 1) {
323			nr_failed++;
324			pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
325				prefix, test_items[i].name,
326				stat->real_cnt, stat->addr, test_items[i].addr);
327		}
328	}
329
330	if (nr_failed) {
331		kfree(stat);
332		return -ESRCH;
333	}
334
335	for (i = 0; i < kallsyms_num_syms; i++) {
336		addr = kallsyms_sym_address(i);
337		if (!is_ksym_addr(addr))
338			continue;
339
340		ret = lookup_symbol_name(addr, namebuf);
341		if (unlikely(ret)) {
342			namebuf[0] = 0;
343			pr_info("%d: lookup_symbol_name(%lx) failed\n", i, addr);
344			goto failed;
345		}
346
347		lookup_addr = kallsyms_lookup_name(namebuf);
348
349		memset(stat, 0, sizeof(*stat));
350		stat->max = INT_MAX;
351		kallsyms_on_each_match_symbol(match_symbol, namebuf, stat);
352
353		/*
354		 * kallsyms_on_each_symbol() is too slow, randomly select some
355		 * symbols for test.
356		 */
357		if (i >= next) {
358			memset(stat2, 0, sizeof(*stat2));
359			stat2->max = INT_MAX;
360			stat2->name = namebuf;
361			kallsyms_on_each_symbol(find_symbol, stat2);
362
363			/*
364			 * kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol()
365			 * need to get the same traversal result.
366			 */
367			if (stat->addr != stat2->addr ||
368			    stat->real_cnt != stat2->real_cnt ||
369			    memcmp(stat->addrs, stat2->addrs,
370				   stat->save_cnt * sizeof(stat->addrs[0]))) {
371				pr_info("%s: mismatch between kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol()\n",
372					namebuf);
373				goto failed;
374			}
375
376			/*
377			 * The average of random increments is 128, that is, one of
378			 * them is tested every 128 symbols.
379			 */
380			get_random_bytes(&rand, sizeof(rand));
381			next = i + (rand & 0xff) + 1;
382		}
383
384		/* Need to be found at least once */
385		if (!stat->real_cnt) {
386			pr_info("%s: Never found\n", namebuf);
387			goto failed;
388		}
389
390		/*
391		 * kallsyms_lookup_name() returns the address of the first
392		 * symbol found and cannot be NULL.
393		 */
394		if (!lookup_addr) {
395			pr_info("%s: NULL lookup_addr?!\n", namebuf);
396			goto failed;
397		}
398		if (lookup_addr != stat->addrs[0]) {
399			pr_info("%s: lookup_addr != stat->addrs[0]\n", namebuf);
400			goto failed;
401		}
402
403		/*
404		 * If the addresses of all matching symbols are recorded, the
405		 * target address needs to be exist.
406		 */
407		if (stat->real_cnt <= MAX_NUM_OF_RECORDS) {
408			for (j = 0; j < stat->save_cnt; j++) {
409				if (stat->addrs[j] == addr)
410					break;
411			}
412
413			if (j == stat->save_cnt) {
414				pr_info("%s: j == save_cnt?!\n", namebuf);
415				goto failed;
416			}
417		}
418	}
419
420	kfree(stat);
421
422	return 0;
423
424failed:
425	pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr);
426	kfree(stat);
427	return -ESRCH;
428}
429
430static int test_entry(void *p)
431{
432	int ret;
433
434	do {
435		schedule_timeout(5 * HZ);
436	} while (system_state != SYSTEM_RUNNING);
437
438	pr_info("start\n");
439	ret = test_kallsyms_basic_function();
440	if (ret) {
441		pr_info("abort\n");
442		return 0;
443	}
444
445	test_kallsyms_compression_ratio();
446	test_perf_kallsyms_lookup_name();
447	test_perf_kallsyms_on_each_symbol();
448	test_perf_kallsyms_on_each_match_symbol();
449	pr_info("finish\n");
450
451	return 0;
452}
453
454static int __init kallsyms_test_init(void)
455{
456	struct task_struct *t;
457
458	t = kthread_create(test_entry, NULL, "kallsyms_test");
459	if (IS_ERR(t)) {
460		pr_info("Create kallsyms selftest task failed\n");
461		return PTR_ERR(t);
462	}
463	kthread_bind(t, 0);
464	wake_up_process(t);
465
466	return 0;
467}
468late_initcall(kallsyms_test_init);
469