blob: 0d2db41177b2344fbc17f98146de1e15d763d463 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/* Generate assembler source containing symbol information
2 *
3 * Copyright 2002 by Kai Germaschewski
4 *
5 * This software may be used and distributed according to the terms
6 * of the GNU General Public License, incorporated herein by reference.
7 *
Yuma Uedaadc402212022-11-18 22:36:31 +09008 * Usage: kallsyms [--all-symbols] [--absolute-percpu]
Masahiro Yamada79549da2023-03-08 20:52:43 +09009 * [--base-relative] [--lto-clang] in.map > out.S
Linus Torvalds1da177e2005-04-16 15:20:36 -070010 *
Linus Torvalds1da177e2005-04-16 15:20:36 -070011 * Table compression uses all the unused char codes on the symbols and
12 * maps these to the most used substrings (tokens). For instance, it might
13 * map char code 0xF7 to represent "write_" and then in every symbol where
14 * "write_" appears it can be replaced by 0xF7, saving 5 bytes.
15 * The used codes themselves are also placed in the table so that the
16 * decompresion can work without "special cases".
17 * Applied to kernel symbols, this usually produces a compression ratio
18 * of about 50%.
19 *
20 */
21
Masahiro Yamadaaa221f22022-09-26 18:02:28 +090022#include <getopt.h>
Masahiro Yamadaa41333e2019-11-24 01:04:39 +090023#include <stdbool.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070024#include <stdio.h>
25#include <stdlib.h>
26#include <string.h>
27#include <ctype.h>
Ard Biesheuvel2213e9a2016-03-15 14:58:19 -070028#include <limits.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070029
Mike Frysinger17b1f0d2009-06-08 19:12:13 -040030#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
Mike Frysinger17b1f0d2009-06-08 19:12:13 -040031
Boqun Fengb4719272022-07-27 20:54:19 +020032#define _stringify_1(x) #x
33#define _stringify(x) _stringify_1(x)
34
Miguel Ojedab8a94bf2021-04-05 05:03:50 +020035#define KSYM_NAME_LEN 512
Linus Torvalds1da177e2005-04-16 15:20:36 -070036
Miguel Ojeda6e8c5bb2022-07-27 21:41:56 +020037/*
38 * A substantially bigger size than the current maximum.
39 *
40 * It cannot be defined as an expression because it gets stringified
41 * for the fscanf() format string. Therefore, a _Static_assert() is
42 * used instead to maintain the relationship with KSYM_NAME_LEN.
43 */
Miguel Ojedab8a94bf2021-04-05 05:03:50 +020044#define KSYM_NAME_LEN_BUFFER 2048
Miguel Ojeda6e8c5bb2022-07-27 21:41:56 +020045_Static_assert(
46 KSYM_NAME_LEN_BUFFER == KSYM_NAME_LEN * 4,
47 "Please keep KSYM_NAME_LEN_BUFFER in sync with KSYM_NAME_LEN"
48);
Boqun Fengb4719272022-07-27 20:54:19 +020049
Linus Torvalds1da177e2005-04-16 15:20:36 -070050struct sym_entry {
51 unsigned long long addr;
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -070052 unsigned int len;
Zhen Lei60443c82022-11-02 16:49:14 +080053 unsigned int seq;
Paulo Marquesf2df3f62008-02-06 01:37:33 -080054 unsigned int start_pos;
Ard Biesheuvel8c996942016-03-15 14:58:15 -070055 unsigned int percpu_absolute;
Linus Torvalds9d829732020-05-04 09:16:37 -070056 unsigned char sym[];
Linus Torvalds1da177e2005-04-16 15:20:36 -070057};
58
Kees Cook78eb7152014-03-17 13:18:27 +103059struct addr_range {
60 const char *start_sym, *end_sym;
Mike Frysinger17b1f0d2009-06-08 19:12:13 -040061 unsigned long long start, end;
62};
63
64static unsigned long long _text;
Ard Biesheuvel2213e9a2016-03-15 14:58:19 -070065static unsigned long long relative_base;
Kees Cook78eb7152014-03-17 13:18:27 +103066static struct addr_range text_ranges[] = {
Mike Frysinger17b1f0d2009-06-08 19:12:13 -040067 { "_stext", "_etext" },
68 { "_sinittext", "_einittext" },
Mike Frysinger17b1f0d2009-06-08 19:12:13 -040069};
70#define text_range_text (&text_ranges[0])
71#define text_range_inittext (&text_ranges[1])
72
Rusty Russellc6bda7c2014-03-17 14:05:46 +103073static struct addr_range percpu_range = {
74 "__per_cpu_start", "__per_cpu_end", -1ULL, 0
75};
76
Masahiro Yamada8d605262020-02-02 14:09:21 +090077static struct sym_entry **table;
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -070078static unsigned int table_size, table_cnt;
Masahiro Yamada831362f2019-11-24 01:04:44 +090079static int all_symbols;
80static int absolute_percpu;
81static int base_relative;
Zhen Lei010a0aa2022-11-02 16:49:15 +080082static int lto_clang;
Linus Torvalds1da177e2005-04-16 15:20:36 -070083
Masahiro Yamadaf43e9da2019-02-04 10:53:16 +090084static int token_profit[0x10000];
Linus Torvalds1da177e2005-04-16 15:20:36 -070085
86/* the table that holds the result of the compression */
Masahiro Yamadaf43e9da2019-02-04 10:53:16 +090087static unsigned char best_table[256][2];
88static unsigned char best_table_len[256];
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
90
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -070091static void usage(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -070092{
Yuntao Wang8d3a7502022-05-22 22:12:40 +080093 fprintf(stderr, "Usage: kallsyms [--all-symbols] [--absolute-percpu] "
Zhen Lei010a0aa2022-11-02 16:49:15 +080094 "[--base-relative] [--lto-clang] in.map > out.S\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -070095 exit(1);
96}
97
Masahiro Yamada29e55ad2019-11-24 01:04:35 +090098static char *sym_name(const struct sym_entry *s)
99{
100 return (char *)s->sym + 1;
101}
102
Masahiro Yamadaa41333e2019-11-24 01:04:39 +0900103static bool is_ignored_symbol(const char *name, char type)
104{
Masahiro Yamadaa7b00a12023-03-08 20:52:36 +0900105 if (type == 'u' || type == 'n')
Masahiro Yamada887df762019-11-24 01:04:41 +0900106 return true;
107
108 if (toupper(type) == 'A') {
109 /* Keep these useful absolute symbols */
110 if (strcmp(name, "__kernel_syscall_via_break") &&
111 strcmp(name, "__kernel_syscall_via_epc") &&
112 strcmp(name, "__kernel_sigtramp") &&
113 strcmp(name, "__gp"))
114 return true;
115 }
116
Masahiro Yamadaa41333e2019-11-24 01:04:39 +0900117 return false;
118}
119
Masahiro Yamadab6233d02019-11-24 01:04:42 +0900120static void check_symbol_range(const char *sym, unsigned long long addr,
121 struct addr_range *ranges, int entries)
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400122{
123 size_t i;
Kees Cook78eb7152014-03-17 13:18:27 +1030124 struct addr_range *ar;
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400125
Kees Cook78eb7152014-03-17 13:18:27 +1030126 for (i = 0; i < entries; ++i) {
127 ar = &ranges[i];
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400128
Kees Cook78eb7152014-03-17 13:18:27 +1030129 if (strcmp(sym, ar->start_sym) == 0) {
130 ar->start = addr;
Masahiro Yamadab6233d02019-11-24 01:04:42 +0900131 return;
Kees Cook78eb7152014-03-17 13:18:27 +1030132 } else if (strcmp(sym, ar->end_sym) == 0) {
133 ar->end = addr;
Masahiro Yamadab6233d02019-11-24 01:04:42 +0900134 return;
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400135 }
136 }
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400137}
138
Masahiro Yamada8d605262020-02-02 14:09:21 +0900139static struct sym_entry *read_symbol(FILE *in)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140{
Boqun Fengb4719272022-07-27 20:54:19 +0200141 char name[KSYM_NAME_LEN_BUFFER+1], type;
Masahiro Yamada8d605262020-02-02 14:09:21 +0900142 unsigned long long addr;
143 unsigned int len;
144 struct sym_entry *sym;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700145 int rc;
146
Boqun Fengb4719272022-07-27 20:54:19 +0200147 rc = fscanf(in, "%llx %c %" _stringify(KSYM_NAME_LEN_BUFFER) "s\n", &addr, &type, name);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700148 if (rc != 3) {
Boqun Fengb66c8742022-07-27 17:58:20 +0200149 if (rc != EOF && fgets(name, ARRAY_SIZE(name), in) == NULL)
Jean Sacrenef894872010-09-10 23:13:33 -0600150 fprintf(stderr, "Read error or end of file.\n");
Masahiro Yamada8d605262020-02-02 14:09:21 +0900151 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152 }
Masahiro Yamadabe9f6132020-02-02 14:09:20 +0900153 if (strlen(name) >= KSYM_NAME_LEN) {
Eugene Loh6db29832019-01-17 14:46:00 -0800154 fprintf(stderr, "Symbol %s too long for kallsyms (%zu >= %d).\n"
Masahiro Yamadabb66fc62014-06-10 19:08:13 +0900155 "Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
Masahiro Yamadabe9f6132020-02-02 14:09:20 +0900156 name, strlen(name), KSYM_NAME_LEN);
Masahiro Yamada8d605262020-02-02 14:09:21 +0900157 return NULL;
Andi Kleenf3462aa2013-10-23 15:07:53 +0200158 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700159
Masahiro Yamadabe9f6132020-02-02 14:09:20 +0900160 if (strcmp(name, "_text") == 0)
Masahiro Yamada8d605262020-02-02 14:09:21 +0900161 _text = addr;
Masahiro Yamadab6233d02019-11-24 01:04:42 +0900162
Mikhail Petrov7883a142020-03-11 23:37:09 +0300163 /* Ignore most absolute/undefined (?) symbols. */
164 if (is_ignored_symbol(name, type))
165 return NULL;
166
Masahiro Yamada8d605262020-02-02 14:09:21 +0900167 check_symbol_range(name, addr, text_ranges, ARRAY_SIZE(text_ranges));
168 check_symbol_range(name, addr, &percpu_range, 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169
170 /* include the type field in the symbol name, so that it gets
171 * compressed together */
Masahiro Yamada8d605262020-02-02 14:09:21 +0900172
173 len = strlen(name) + 1;
174
Masahiro Yamada9d1b3892020-02-11 01:18:52 +0900175 sym = malloc(sizeof(*sym) + len + 1);
Masahiro Yamada8d605262020-02-02 14:09:21 +0900176 if (!sym) {
Jesper Juhlf1a136e2006-03-25 03:07:46 -0800177 fprintf(stderr, "kallsyms failure: "
178 "unable to allocate required amount of memory\n");
179 exit(EXIT_FAILURE);
180 }
Masahiro Yamada8d605262020-02-02 14:09:21 +0900181 sym->addr = addr;
182 sym->len = len;
183 sym->sym[0] = type;
Masahiro Yamada9d1b3892020-02-11 01:18:52 +0900184 strcpy(sym_name(sym), name);
Masahiro Yamada8d605262020-02-02 14:09:21 +0900185 sym->percpu_absolute = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186
Masahiro Yamada8d605262020-02-02 14:09:21 +0900187 return sym;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700188}
189
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900190static int symbol_in_range(const struct sym_entry *s,
191 const struct addr_range *ranges, int entries)
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400192{
193 size_t i;
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900194 const struct addr_range *ar;
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400195
Kees Cook78eb7152014-03-17 13:18:27 +1030196 for (i = 0; i < entries; ++i) {
197 ar = &ranges[i];
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400198
Kees Cook78eb7152014-03-17 13:18:27 +1030199 if (s->addr >= ar->start && s->addr <= ar->end)
Mike Frysingerac6ca5c2009-06-15 07:52:48 -0400200 return 1;
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400201 }
202
Mike Frysingerac6ca5c2009-06-15 07:52:48 -0400203 return 0;
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400204}
205
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900206static int symbol_valid(const struct sym_entry *s)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700207{
Masahiro Yamada29e55ad2019-11-24 01:04:35 +0900208 const char *name = sym_name(s);
Ard Biesheuvelbd8b22d2015-03-30 15:20:31 +0200209
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210 /* if --all-symbols is not specified, then symbols outside the text
211 * and inittext sections are discarded */
212 if (!all_symbols) {
Kees Cook78eb7152014-03-17 13:18:27 +1030213 if (symbol_in_range(s, text_ranges,
214 ARRAY_SIZE(text_ranges)) == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 return 0;
216 /* Corner case. Discard any symbols with the same value as
Robin Getza3b81112008-02-06 01:36:26 -0800217 * _etext _einittext; they can move between pass 1 and 2 when
218 * the kallsyms data are added. If these symbols move then
219 * they may get dropped in pass 2, which breaks the kallsyms
220 * rules.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700221 */
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400222 if ((s->addr == text_range_text->end &&
Masahiro Yamada29e55ad2019-11-24 01:04:35 +0900223 strcmp(name, text_range_text->end_sym)) ||
Mike Frysinger17b1f0d2009-06-08 19:12:13 -0400224 (s->addr == text_range_inittext->end &&
Masahiro Yamada29e55ad2019-11-24 01:04:35 +0900225 strcmp(name, text_range_inittext->end_sym)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700226 return 0;
227 }
228
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 return 1;
230}
231
Masahiro Yamada5e5c4fa2019-11-24 01:04:31 +0900232/* remove all the invalid symbols from the table */
233static void shrink_table(void)
234{
235 unsigned int i, pos;
236
237 pos = 0;
238 for (i = 0; i < table_cnt; i++) {
Masahiro Yamada8d605262020-02-02 14:09:21 +0900239 if (symbol_valid(table[i])) {
Masahiro Yamada5e5c4fa2019-11-24 01:04:31 +0900240 if (pos != i)
241 table[pos] = table[i];
242 pos++;
243 } else {
Masahiro Yamada8d605262020-02-02 14:09:21 +0900244 free(table[i]);
Masahiro Yamada5e5c4fa2019-11-24 01:04:31 +0900245 }
246 }
247 table_cnt = pos;
248
249 /* When valid symbol is not registered, exit to error */
250 if (!table_cnt) {
251 fprintf(stderr, "No valid symbol.\n");
252 exit(1);
253 }
254}
255
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900256static void read_map(const char *in)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257{
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900258 FILE *fp;
Masahiro Yamada8d605262020-02-02 14:09:21 +0900259 struct sym_entry *sym;
260
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900261 fp = fopen(in, "r");
262 if (!fp) {
263 perror(in);
264 exit(1);
265 }
266
267 while (!feof(fp)) {
268 sym = read_symbol(fp);
Masahiro Yamada8d605262020-02-02 14:09:21 +0900269 if (!sym)
270 continue;
271
272 sym->start_pos = table_cnt;
273
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700274 if (table_cnt >= table_size) {
275 table_size += 10000;
276 table = realloc(table, sizeof(*table) * table_size);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277 if (!table) {
278 fprintf(stderr, "out of memory\n");
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900279 fclose(fp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280 exit (1);
281 }
282 }
Masahiro Yamada8d605262020-02-02 14:09:21 +0900283
284 table[table_cnt++] = sym;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700285 }
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900286
287 fclose(fp);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288}
289
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900290static void output_label(const char *label)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700291{
Masahiro Yamada534c9f22018-05-09 16:23:47 +0900292 printf(".globl %s\n", label);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700293 printf("\tALGN\n");
Masahiro Yamada534c9f22018-05-09 16:23:47 +0900294 printf("%s:\n", label);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295}
296
Masahiro Yamadafd2ab2f2019-12-09 12:51:48 +0900297/* Provide proper symbols relocatability by their '_text' relativeness. */
298static void output_address(unsigned long long addr)
299{
300 if (_text <= addr)
301 printf("\tPTR\t_text + %#llx\n", addr - _text);
302 else
303 printf("\tPTR\t_text - %#llx\n", _text - addr);
304}
305
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306/* uncompress a compressed symbol. When this function is called, the best table
307 * might still be compressed itself, so the function needs to be recursive */
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900308static int expand_symbol(const unsigned char *data, int len, char *result)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700309{
310 int c, rlen, total=0;
311
312 while (len) {
313 c = *data;
314 /* if the table holds a single char that is the same as the one
315 * we are looking for, then end the search */
316 if (best_table[c][0]==c && best_table_len[c]==1) {
317 *result++ = c;
318 total++;
319 } else {
320 /* if not, recurse and expand */
321 rlen = expand_symbol(best_table[c], best_table_len[c], result);
322 total += rlen;
323 result += rlen;
324 }
325 data++;
326 len--;
327 }
328 *result=0;
329
330 return total;
331}
332
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900333static int symbol_absolute(const struct sym_entry *s)
Kees Cook78eb7152014-03-17 13:18:27 +1030334{
Ard Biesheuvel8c996942016-03-15 14:58:15 -0700335 return s->percpu_absolute;
Kees Cook78eb7152014-03-17 13:18:27 +1030336}
337
Zhen Lei010a0aa2022-11-02 16:49:15 +0800338static void cleanup_symbol_name(char *s)
339{
340 char *p;
341
Zhen Lei010a0aa2022-11-02 16:49:15 +0800342 /*
343 * ASCII[.] = 2e
344 * ASCII[0-9] = 30,39
345 * ASCII[A-Z] = 41,5a
346 * ASCII[_] = 5f
347 * ASCII[a-z] = 61,7a
348 *
349 * As above, replacing '.' with '\0' does not affect the main sorting,
350 * but it helps us with subsorting.
351 */
352 p = strchr(s, '.');
353 if (p)
354 *p = '\0';
355}
356
Zhen Lei60443c82022-11-02 16:49:14 +0800357static int compare_names(const void *a, const void *b)
358{
359 int ret;
Zhen Lei60443c82022-11-02 16:49:14 +0800360 const struct sym_entry *sa = *(const struct sym_entry **)a;
361 const struct sym_entry *sb = *(const struct sym_entry **)b;
362
Masahiro Yamadadd1553b2023-03-08 20:52:42 +0900363 ret = strcmp(sym_name(sa), sym_name(sb));
Zhen Lei60443c82022-11-02 16:49:14 +0800364 if (!ret) {
365 if (sa->addr > sb->addr)
366 return 1;
367 else if (sa->addr < sb->addr)
368 return -1;
369
370 /* keep old order */
371 return (int)(sa->seq - sb->seq);
372 }
373
374 return ret;
375}
376
377static void sort_symbols_by_name(void)
378{
379 qsort(table, table_cnt, sizeof(table[0]), compare_names);
380}
381
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700382static void write_src(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700383{
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700384 unsigned int i, k, off;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385 unsigned int best_idx[256];
386 unsigned int *markers;
Tejun Heo9281ace2007-07-17 04:03:51 -0700387 char buf[KSYM_NAME_LEN];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388
Masahiro Yamada500193e2019-02-04 10:53:18 +0900389 printf("#include <asm/bitsperlong.h>\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 printf("#if BITS_PER_LONG == 64\n");
391 printf("#define PTR .quad\n");
Mathias Krause72d3ebb2018-12-30 13:36:00 +0100392 printf("#define ALGN .balign 8\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393 printf("#else\n");
394 printf("#define PTR .long\n");
Mathias Krause72d3ebb2018-12-30 13:36:00 +0100395 printf("#define ALGN .balign 4\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 printf("#endif\n");
397
Jan Beulichaad09472006-12-08 02:35:57 -0800398 printf("\t.section .rodata, \"a\"\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399
Linus Torvalds1da177e2005-04-16 15:20:36 -0700400 output_label("kallsyms_num_syms");
Jan Beulich80ffbaa2018-09-03 06:09:34 -0600401 printf("\t.long\t%u\n", table_cnt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402 printf("\n");
403
404 /* table of offset markers, that give the offset in the compressed stream
405 * every 256 symbols */
Jesper Juhlf1a136e2006-03-25 03:07:46 -0800406 markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
407 if (!markers) {
408 fprintf(stderr, "kallsyms failure: "
409 "unable to allocate required memory\n");
410 exit(EXIT_FAILURE);
411 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700412
413 output_label("kallsyms_names");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414 off = 0;
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700415 for (i = 0; i < table_cnt; i++) {
416 if ((i & 0xFF) == 0)
417 markers[i >> 8] = off;
Zhen Lei60443c82022-11-02 16:49:14 +0800418 table[i]->seq = i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419
Miguel Ojeda73bbb942021-04-05 04:58:39 +0200420 /* There cannot be any symbol of length zero. */
421 if (table[i]->len == 0) {
422 fprintf(stderr, "kallsyms failure: "
423 "unexpected zero symbol length\n");
424 exit(EXIT_FAILURE);
425 }
426
427 /* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
428 if (table[i]->len > 0x3FFF) {
429 fprintf(stderr, "kallsyms failure: "
430 "unexpected huge symbol length\n");
431 exit(EXIT_FAILURE);
432 }
433
434 /* Encode length with ULEB128. */
435 if (table[i]->len <= 0x7F) {
436 /* Most symbols use a single byte for the length. */
437 printf("\t.byte 0x%02x", table[i]->len);
438 off += table[i]->len + 1;
439 } else {
440 /* "Big" symbols use two bytes. */
441 printf("\t.byte 0x%02x, 0x%02x",
442 (table[i]->len & 0x7F) | 0x80,
443 (table[i]->len >> 7) & 0x7F);
444 off += table[i]->len + 2;
445 }
Masahiro Yamada8d605262020-02-02 14:09:21 +0900446 for (k = 0; k < table[i]->len; k++)
447 printf(", 0x%02x", table[i]->sym[k]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700448 printf("\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700449 }
450 printf("\n");
451
Masahiro Yamadadd1553b2023-03-08 20:52:42 +0900452 /*
453 * Now that we wrote out the compressed symbol names, restore the
454 * original names, which are needed in some of the later steps.
455 */
456 for (i = 0; i < table_cnt; i++) {
457 expand_symbol(table[i]->sym, table[i]->len, buf);
458 strcpy((char *)table[i]->sym, buf);
459 }
460
Linus Torvalds1da177e2005-04-16 15:20:36 -0700461 output_label("kallsyms_markers");
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700462 for (i = 0; i < ((table_cnt + 255) >> 8); i++)
Jan Beulich80ffbaa2018-09-03 06:09:34 -0600463 printf("\t.long\t%u\n", markers[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 printf("\n");
465
466 free(markers);
467
468 output_label("kallsyms_token_table");
469 off = 0;
470 for (i = 0; i < 256; i++) {
471 best_idx[i] = off;
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700472 expand_symbol(best_table[i], best_table_len[i], buf);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700473 printf("\t.asciz\t\"%s\"\n", buf);
474 off += strlen(buf) + 1;
475 }
476 printf("\n");
477
478 output_label("kallsyms_token_index");
479 for (i = 0; i < 256; i++)
480 printf("\t.short\t%d\n", best_idx[i]);
481 printf("\n");
Masahiro Yamada404bad72023-03-08 20:52:41 +0900482
483 if (!base_relative)
484 output_label("kallsyms_addresses");
485 else
486 output_label("kallsyms_offsets");
487
488 for (i = 0; i < table_cnt; i++) {
489 if (base_relative) {
490 /*
491 * Use the offset relative to the lowest value
492 * encountered of all relative symbols, and emit
493 * non-relocatable fixed offsets that will be fixed
494 * up at runtime.
495 */
496
497 long long offset;
498 int overflow;
499
500 if (!absolute_percpu) {
501 offset = table[i]->addr - relative_base;
502 overflow = (offset < 0 || offset > UINT_MAX);
503 } else if (symbol_absolute(table[i])) {
504 offset = table[i]->addr;
505 overflow = (offset < 0 || offset > INT_MAX);
506 } else {
507 offset = relative_base - table[i]->addr - 1;
508 overflow = (offset < INT_MIN || offset >= 0);
509 }
510 if (overflow) {
511 fprintf(stderr, "kallsyms failure: "
512 "%s symbol value %#llx out of range in relative mode\n",
513 symbol_absolute(table[i]) ? "absolute" : "relative",
514 table[i]->addr);
515 exit(EXIT_FAILURE);
516 }
Masahiro Yamadadd1553b2023-03-08 20:52:42 +0900517 printf("\t.long\t%#x /* %s */\n", (int)offset, table[i]->sym);
Masahiro Yamada404bad72023-03-08 20:52:41 +0900518 } else if (!symbol_absolute(table[i])) {
519 output_address(table[i]->addr);
520 } else {
521 printf("\tPTR\t%#llx\n", table[i]->addr);
522 }
523 }
524 printf("\n");
525
526 if (base_relative) {
527 output_label("kallsyms_relative_base");
528 output_address(relative_base);
529 printf("\n");
530 }
531
Masahiro Yamadadd1553b2023-03-08 20:52:42 +0900532 if (lto_clang)
533 for (i = 0; i < table_cnt; i++)
534 cleanup_symbol_name((char *)table[i]->sym);
535
Masahiro Yamada404bad72023-03-08 20:52:41 +0900536 sort_symbols_by_name();
537 output_label("kallsyms_seqs_of_names");
538 for (i = 0; i < table_cnt; i++)
539 printf("\t.byte 0x%02x, 0x%02x, 0x%02x\n",
540 (unsigned char)(table[i]->seq >> 16),
541 (unsigned char)(table[i]->seq >> 8),
542 (unsigned char)(table[i]->seq >> 0));
543 printf("\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -0700544}
545
546
547/* table lookup compression functions */
548
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549/* count all the possible tokens in a symbol */
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900550static void learn_symbol(const unsigned char *symbol, int len)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700551{
552 int i;
553
554 for (i = 0; i < len - 1; i++)
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700555 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556}
557
558/* decrease the count for all the possible tokens in a symbol */
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900559static void forget_symbol(const unsigned char *symbol, int len)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700560{
561 int i;
562
563 for (i = 0; i < len - 1; i++)
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700564 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700565}
566
Masahiro Yamada5e5c4fa2019-11-24 01:04:31 +0900567/* do the initial token count */
Zhen Leifcdf7192022-11-02 16:49:13 +0800568static void build_initial_token_table(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700569{
Masahiro Yamada5e5c4fa2019-11-24 01:04:31 +0900570 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571
Masahiro Yamada5e5c4fa2019-11-24 01:04:31 +0900572 for (i = 0; i < table_cnt; i++)
Masahiro Yamada8d605262020-02-02 14:09:21 +0900573 learn_symbol(table[i]->sym, table[i]->len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574}
575
Masahiro Yamada2558c132019-11-24 01:04:37 +0900576static unsigned char *find_token(unsigned char *str, int len,
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900577 const unsigned char *token)
Paulo Marques7c5d2492007-06-20 18:09:00 +0100578{
579 int i;
580
581 for (i = 0; i < len - 1; i++) {
582 if (str[i] == token[0] && str[i+1] == token[1])
583 return &str[i];
584 }
585 return NULL;
586}
587
Linus Torvalds1da177e2005-04-16 15:20:36 -0700588/* replace a given token in all the valid symbols. Use the sampled symbols
589 * to update the counts */
Masahiro Yamada4bfe2b72019-11-24 01:04:38 +0900590static void compress_symbols(const unsigned char *str, int idx)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591{
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700592 unsigned int i, len, size;
593 unsigned char *p1, *p2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700594
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700595 for (i = 0; i < table_cnt; i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700596
Masahiro Yamada8d605262020-02-02 14:09:21 +0900597 len = table[i]->len;
598 p1 = table[i]->sym;
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700599
600 /* find the token on the symbol */
Paulo Marques7c5d2492007-06-20 18:09:00 +0100601 p2 = find_token(p1, len, str);
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700602 if (!p2) continue;
603
604 /* decrease the counts for this symbol's tokens */
Masahiro Yamada8d605262020-02-02 14:09:21 +0900605 forget_symbol(table[i]->sym, len);
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700606
607 size = len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700608
609 do {
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700610 *p2 = idx;
611 p2++;
612 size -= (p2 - p1);
613 memmove(p2, p2 + 1, size);
614 p1 = p2;
615 len--;
616
617 if (size < 2) break;
618
Linus Torvalds1da177e2005-04-16 15:20:36 -0700619 /* find the token on the symbol */
Paulo Marques7c5d2492007-06-20 18:09:00 +0100620 p2 = find_token(p1, size, str);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700622 } while (p2);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623
Masahiro Yamada8d605262020-02-02 14:09:21 +0900624 table[i]->len = len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700626 /* increase the counts for this symbol's new tokens */
Masahiro Yamada8d605262020-02-02 14:09:21 +0900627 learn_symbol(table[i]->sym, len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700628 }
629}
630
631/* search the token with the maximum profit */
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700632static int find_best_token(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700633{
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700634 int i, best, bestprofit;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635
636 bestprofit=-10000;
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700637 best = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700638
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700639 for (i = 0; i < 0x10000; i++) {
640 if (token_profit[i] > bestprofit) {
641 best = i;
642 bestprofit = token_profit[i];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700643 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645 return best;
646}
647
648/* this is the core of the algorithm: calculate the "best" table */
649static void optimize_result(void)
650{
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700651 int i, best;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700652
653 /* using the '\0' symbol last allows compress_symbols to use standard
654 * fast string functions */
655 for (i = 255; i >= 0; i--) {
656
657 /* if this table slot is empty (it is not used by an actual
658 * original char code */
659 if (!best_table_len[i]) {
660
Cao jincbf7a902018-02-27 16:16:19 +0800661 /* find the token with the best profit value */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 best = find_best_token();
Xiaochen Wange0a04b12011-05-01 11:41:41 +0800663 if (token_profit[best] == 0)
664 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665
666 /* place it in the "best" table */
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700667 best_table_len[i] = 2;
668 best_table[i][0] = best & 0xFF;
669 best_table[i][1] = (best >> 8) & 0xFF;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670
671 /* replace this token in all the valid symbols */
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700672 compress_symbols(best_table[i], i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700673 }
674 }
675}
676
677/* start by placing the symbols that are actually used on the table */
678static void insert_real_symbols_in_table(void)
679{
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700680 unsigned int i, j, c;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700682 for (i = 0; i < table_cnt; i++) {
Masahiro Yamada8d605262020-02-02 14:09:21 +0900683 for (j = 0; j < table[i]->len; j++) {
684 c = table[i]->sym[j];
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700685 best_table[c][0]=c;
686 best_table_len[c]=1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700687 }
688 }
689}
690
691static void optimize_token_table(void)
692{
Zhen Leifcdf7192022-11-02 16:49:13 +0800693 build_initial_token_table();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700694
695 insert_real_symbols_in_table();
696
697 optimize_result();
698}
699
Lai Jiangshanb478b782009-03-13 15:10:26 +0800700/* guess for "linker script provide" symbol */
701static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
702{
Masahiro Yamada29e55ad2019-11-24 01:04:35 +0900703 const char *symbol = sym_name(se);
Lai Jiangshanb478b782009-03-13 15:10:26 +0800704 int len = se->len - 1;
705
706 if (len < 8)
707 return 0;
708
709 if (symbol[0] != '_' || symbol[1] != '_')
710 return 0;
711
712 /* __start_XXXXX */
713 if (!memcmp(symbol + 2, "start_", 6))
714 return 1;
715
716 /* __stop_XXXXX */
717 if (!memcmp(symbol + 2, "stop_", 5))
718 return 1;
719
720 /* __end_XXXXX */
721 if (!memcmp(symbol + 2, "end_", 4))
722 return 1;
723
724 /* __XXXXX_start */
725 if (!memcmp(symbol + len - 6, "_start", 6))
726 return 1;
727
728 /* __XXXXX_end */
729 if (!memcmp(symbol + len - 4, "_end", 4))
730 return 1;
731
732 return 0;
733}
734
Paulo Marquesf2df3f62008-02-06 01:37:33 -0800735static int compare_symbols(const void *a, const void *b)
736{
Masahiro Yamada8d605262020-02-02 14:09:21 +0900737 const struct sym_entry *sa = *(const struct sym_entry **)a;
738 const struct sym_entry *sb = *(const struct sym_entry **)b;
Paulo Marquesf2df3f62008-02-06 01:37:33 -0800739 int wa, wb;
740
Paulo Marquesf2df3f62008-02-06 01:37:33 -0800741 /* sort by address first */
742 if (sa->addr > sb->addr)
743 return 1;
744 if (sa->addr < sb->addr)
745 return -1;
746
747 /* sort by "weakness" type */
748 wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
749 wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
750 if (wa != wb)
751 return wa - wb;
752
Lai Jiangshanb478b782009-03-13 15:10:26 +0800753 /* sort by "linker script provide" type */
754 wa = may_be_linker_script_provide_symbol(sa);
755 wb = may_be_linker_script_provide_symbol(sb);
756 if (wa != wb)
757 return wa - wb;
758
759 /* sort by the number of prefix underscores */
Masahiro Yamadaaa915242019-11-24 01:04:36 +0900760 wa = strspn(sym_name(sa), "_");
761 wb = strspn(sym_name(sb), "_");
Lai Jiangshanb478b782009-03-13 15:10:26 +0800762 if (wa != wb)
763 return wa - wb;
764
Paulo Marquesf2df3f62008-02-06 01:37:33 -0800765 /* sort by initial order, so that other symbols are left undisturbed */
766 return sa->start_pos - sb->start_pos;
767}
768
769static void sort_symbols(void)
770{
Masahiro Yamada8d605262020-02-02 14:09:21 +0900771 qsort(table, table_cnt, sizeof(table[0]), compare_symbols);
Paulo Marquesf2df3f62008-02-06 01:37:33 -0800772}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700773
Rusty Russellc6bda7c2014-03-17 14:05:46 +1030774static void make_percpus_absolute(void)
775{
776 unsigned int i;
777
778 for (i = 0; i < table_cnt; i++)
Masahiro Yamada8d605262020-02-02 14:09:21 +0900779 if (symbol_in_range(table[i], &percpu_range, 1)) {
Ard Biesheuvel8c996942016-03-15 14:58:15 -0700780 /*
781 * Keep the 'A' override for percpu symbols to
782 * ensure consistent behavior compared to older
783 * versions of this tool.
784 */
Masahiro Yamada8d605262020-02-02 14:09:21 +0900785 table[i]->sym[0] = 'A';
786 table[i]->percpu_absolute = 1;
Ard Biesheuvel8c996942016-03-15 14:58:15 -0700787 }
Rusty Russellc6bda7c2014-03-17 14:05:46 +1030788}
789
Ard Biesheuvel2213e9a2016-03-15 14:58:19 -0700790/* find the minimum non-absolute symbol address */
791static void record_relative_base(void)
792{
793 unsigned int i;
794
Ard Biesheuvel2213e9a2016-03-15 14:58:19 -0700795 for (i = 0; i < table_cnt; i++)
Masahiro Yamada8d605262020-02-02 14:09:21 +0900796 if (!symbol_absolute(table[i])) {
Masahiro Yamadaf34ea022019-11-24 01:04:32 +0900797 /*
798 * The table is sorted by address.
799 * Take the first non-absolute symbol value.
800 */
Masahiro Yamada8d605262020-02-02 14:09:21 +0900801 relative_base = table[i]->addr;
Masahiro Yamadaf34ea022019-11-24 01:04:32 +0900802 return;
803 }
Ard Biesheuvel2213e9a2016-03-15 14:58:19 -0700804}
805
Paulo Marquesb3dbb4e2005-09-06 15:16:31 -0700806int main(int argc, char **argv)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700807{
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900808 while (1) {
809 static struct option long_options[] = {
810 {"all-symbols", no_argument, &all_symbols, 1},
811 {"absolute-percpu", no_argument, &absolute_percpu, 1},
812 {"base-relative", no_argument, &base_relative, 1},
Zhen Lei010a0aa2022-11-02 16:49:15 +0800813 {"lto-clang", no_argument, &lto_clang, 1},
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900814 {},
815 };
816
817 int c = getopt_long(argc, argv, "", long_options, NULL);
818
819 if (c == -1)
820 break;
821 if (c != 0)
822 usage();
823 }
824
825 if (optind >= argc)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700826 usage();
827
Masahiro Yamadaaa221f22022-09-26 18:02:28 +0900828 read_map(argv[optind]);
Masahiro Yamada5e5c4fa2019-11-24 01:04:31 +0900829 shrink_table();
Rusty Russellc6bda7c2014-03-17 14:05:46 +1030830 if (absolute_percpu)
831 make_percpus_absolute();
Masahiro Yamadaf34ea022019-11-24 01:04:32 +0900832 sort_symbols();
Ard Biesheuvel2213e9a2016-03-15 14:58:19 -0700833 if (base_relative)
834 record_relative_base();
Sam Ravnborg2ea03892009-01-14 21:38:20 +0100835 optimize_token_table();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836 write_src();
837
838 return 0;
839}