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
26 struct 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
38 struct 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
56 static int kallsyms_test_var_bss_static;
57 static int kallsyms_test_var_data_static = 1;
58 int kallsyms_test_var_bss;
59 int kallsyms_test_var_data = 1;
60
61 static 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
69 int 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
81 static 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
95 static char stub_name[KSYM_NAME_LEN];
96
97 static int stat_symbol_len(void *data, const char *name, unsigned long addr)
98 {
99 *(u32 *)data += strlen(name);
100
101 return 0;
102 }
103
104 static 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
156 static 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
178 static 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
190 static 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
209 static 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
230 static 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
245 static 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
263 static 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
277 static 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
424 failed:
425 pr_info("Test for %dth symbol failed: (%s) addr=%lx", i, namebuf, addr);
426 kfree(stat);
427 return -ESRCH;
428 }
429
430 static 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
454 static 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 }
468 late_initcall(kallsyms_test_init);
469
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.