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_noprof),
 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 int find_symbol(void *data, const char *name, unsigned long addr)
191{
192	struct test_stat *stat = (struct test_stat *)data;
193
194	if (!strcmp(name, stat->name)) {
195		stat->real_cnt++;
196		stat->addr = addr;
197
198		if (stat->save_cnt < MAX_NUM_OF_RECORDS) {
199			stat->addrs[stat->save_cnt] = addr;
200			stat->save_cnt++;
201		}
202
203		if (stat->real_cnt == stat->max)
204			return 1;
205	}
206
207	return 0;
208}
209
210static void test_perf_kallsyms_on_each_symbol(void)
211{
212	u64 t0, t1;
213	struct test_stat stat;
214
215	memset(&stat, 0, sizeof(stat));
216	stat.max = INT_MAX;
217	stat.name = stub_name;
218	stat.perf = 1;
219	t0 = ktime_get_ns();
220	kallsyms_on_each_symbol(find_symbol, &stat);
221	t1 = ktime_get_ns();
222	pr_info("kallsyms_on_each_symbol() traverse all: %lld ns\n", t1 - t0);
223}
224
225static int match_symbol(void *data, unsigned long addr)
226{
227	struct test_stat *stat = (struct test_stat *)data;
228
229	stat->real_cnt++;
230	stat->addr = addr;
231
232	if (stat->save_cnt < MAX_NUM_OF_RECORDS) {
233		stat->addrs[stat->save_cnt] = addr;
234		stat->save_cnt++;
235	}
236
237	if (stat->real_cnt == stat->max)
238		return 1;
239
240	return 0;
241}
242
243static void test_perf_kallsyms_on_each_match_symbol(void)
244{
245	u64 t0, t1;
246	struct test_stat stat;
247
248	memset(&stat, 0, sizeof(stat));
249	stat.max = INT_MAX;
250	stat.name = stub_name;
251	t0 = ktime_get_ns();
252	kallsyms_on_each_match_symbol(match_symbol, stat.name, &stat);
253	t1 = ktime_get_ns();
254	pr_info("kallsyms_on_each_match_symbol() traverse all: %lld ns\n", t1 - t0);
255}
256
257static int test_kallsyms_basic_function(void)
258{
259	int i, j, ret;
260	int next = 0, nr_failed = 0;
261	char *prefix;
262	unsigned short rand;
263	unsigned long addr, lookup_addr;
264	char namebuf[KSYM_NAME_LEN];
265	struct test_stat *stat, *stat2;
266
267	stat = kmalloc(sizeof(*stat) * 2, GFP_KERNEL);
268	if (!stat)
269		return -ENOMEM;
270	stat2 = stat + 1;
271
272	prefix = "kallsyms_lookup_name() for";
273	for (i = 0; i < ARRAY_SIZE(test_items); i++) {
274		addr = kallsyms_lookup_name(test_items[i].name);
275		if (addr != test_items[i].addr) {
276			nr_failed++;
277			pr_info("%s %s failed: addr=%lx, expect %lx\n",
278				prefix, test_items[i].name, addr, test_items[i].addr);
279		}
280	}
281
282	prefix = "kallsyms_on_each_symbol() for";
283	for (i = 0; i < ARRAY_SIZE(test_items); i++) {
284		memset(stat, 0, sizeof(*stat));
285		stat->max = INT_MAX;
286		stat->name = test_items[i].name;
287		kallsyms_on_each_symbol(find_symbol, stat);
288		if (stat->addr != test_items[i].addr || stat->real_cnt != 1) {
289			nr_failed++;
290			pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
291				prefix, test_items[i].name,
292				stat->real_cnt, stat->addr, test_items[i].addr);
293		}
294	}
295
296	prefix = "kallsyms_on_each_match_symbol() for";
297	for (i = 0; i < ARRAY_SIZE(test_items); i++) {
298		memset(stat, 0, sizeof(*stat));
299		stat->max = INT_MAX;
300		stat->name = test_items[i].name;
301		kallsyms_on_each_match_symbol(match_symbol, test_items[i].name, stat);
302		if (stat->addr != test_items[i].addr || stat->real_cnt != 1) {
303			nr_failed++;
304			pr_info("%s %s failed: count=%d, addr=%lx, expect %lx\n",
305				prefix, test_items[i].name,
306				stat->real_cnt, stat->addr, test_items[i].addr);
307		}
308	}
309
310	if (nr_failed) {
311		kfree(stat);
312		return -ESRCH;
313	}
314
315	for (i = 0; i < kallsyms_num_syms; i++) {
316		addr = kallsyms_sym_address(i);
317		if (!is_ksym_addr(addr))
318			continue;
319
320		ret = lookup_symbol_name(addr, namebuf);
321		if (unlikely(ret)) {
322			namebuf[0] = 0;
323			pr_info("%d: lookup_symbol_name(%lx) failed\n", i, addr);
324			goto failed;
325		}
326
327		lookup_addr = kallsyms_lookup_name(namebuf);
328
329		memset(stat, 0, sizeof(*stat));
330		stat->max = INT_MAX;
331		kallsyms_on_each_match_symbol(match_symbol, namebuf, stat);
332
333		/*
334		 * kallsyms_on_each_symbol() is too slow, randomly select some
335		 * symbols for test.
336		 */
337		if (i >= next) {
338			memset(stat2, 0, sizeof(*stat2));
339			stat2->max = INT_MAX;
340			stat2->name = namebuf;
341			kallsyms_on_each_symbol(find_symbol, stat2);
342
343			/*
344			 * kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol()
345			 * need to get the same traversal result.
346			 */
347			if (stat->addr != stat2->addr ||
348			    stat->real_cnt != stat2->real_cnt ||
349			    memcmp(stat->addrs, stat2->addrs,
350				   stat->save_cnt * sizeof(stat->addrs[0]))) {
351				pr_info("%s: mismatch between kallsyms_on_each_symbol() and kallsyms_on_each_match_symbol()\n",
352					namebuf);
353				goto failed;
354			}
355
356			/*
357			 * The average of random increments is 128, that is, one of
358			 * them is tested every 128 symbols.
359			 */
360			get_random_bytes(&rand, sizeof(rand));
361			next = i + (rand & 0xff) + 1;
362		}
363
364		/* Need to be found at least once */
365		if (!stat->real_cnt) {
366			pr_info("%s: Never found\n", namebuf);
367			goto failed;
368		}
369
370		/*
371		 * kallsyms_lookup_name() returns the address of the first
372		 * symbol found and cannot be NULL.
373		 */
374		if (!lookup_addr) {
375			pr_info("%s: NULL lookup_addr?!\n", namebuf);
376			goto failed;
377		}
378		if (lookup_addr != stat->addrs[0]) {
379			pr_info("%s: lookup_addr != stat->addrs[0]\n", namebuf);
380			goto failed;
381		}
382
383		/*
384		 * If the addresses of all matching symbols are recorded, the
385		 * target address needs to be exist.
386		 */
387		if (stat->real_cnt <= MAX_NUM_OF_RECORDS) {
388			for (j = 0; j < stat->save_cnt; j++) {
389				if (stat->addrs[j] == addr)
390					break;
391			}
392
393			if (j == stat->save_cnt) {
394				pr_info("%s: j == save_cnt?!\n", namebuf);
395				goto failed;
396			}
397		}
398	}
399
400	kfree(stat);
401
402	return 0;
403
404failed:
405	pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr);
406	kfree(stat);
407	return -ESRCH;
408}
409
410static int test_entry(void *p)
411{
412	int ret;
413
414	do {
415		schedule_timeout(5 * HZ);
416	} while (system_state != SYSTEM_RUNNING);
417
418	pr_info("start\n");
419	ret = test_kallsyms_basic_function();
420	if (ret) {
421		pr_info("abort\n");
422		return 0;
423	}
424
425	test_kallsyms_compression_ratio();
426	test_perf_kallsyms_lookup_name();
427	test_perf_kallsyms_on_each_symbol();
428	test_perf_kallsyms_on_each_match_symbol();
429	pr_info("finish\n");
430
431	return 0;
432}
433
434static int __init kallsyms_test_init(void)
435{
436	struct task_struct *t;
437
438	t = kthread_create(test_entry, NULL, "kallsyms_test");
439	if (IS_ERR(t)) {
440		pr_info("Create kallsyms selftest task failed\n");
441		return PTR_ERR(t);
442	}
443	kthread_bind(t, 0);
444	wake_up_process(t);
445
446	return 0;
447}
448late_initcall(kallsyms_test_init);