1 /* Generate assembler source containing symbol information
3 * Copyright 2002 by Kai Germaschewski
5 * This software may be used and distributed according to the terms
6 * of the GNU General Public License, incorporated herein by reference.
8 * Usage: nm -n vmlinux | scripts/kallsyms [--all-symbols] > symbols.S
10 * Table compression uses all the unused char codes on the symbols and
11 * maps these to the most used substrings (tokens). For instance, it might
12 * map char code 0xF7 to represent "write_" and then in every symbol where
13 * "write_" appears it can be replaced by 0xF7, saving 5 bytes.
14 * The used codes themselves are also placed in the table so that the
15 * decompresion can work without "special cases".
16 * Applied to kernel symbols, this usually produces a compression ratio
29 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
31 #define _stringify_1(x) #x
32 #define _stringify(x) _stringify_1(x)
34 #define KSYM_NAME_LEN 512
37 * A substantially bigger size than the current maximum.
39 * It cannot be defined as an expression because it gets stringified
40 * for the fscanf() format string. Therefore, a _Static_assert() is
41 * used instead to maintain the relationship with KSYM_NAME_LEN.
43 #define KSYM_NAME_LEN_BUFFER 2048
45 KSYM_NAME_LEN_BUFFER == KSYM_NAME_LEN * 4,
46 "Please keep KSYM_NAME_LEN_BUFFER in sync with KSYM_NAME_LEN"
50 unsigned long long addr;
53 unsigned int start_pos;
54 unsigned int percpu_absolute;
59 const char *start_sym, *end_sym;
60 unsigned long long start, end;
63 static unsigned long long _text;
64 static unsigned long long relative_base;
65 static struct addr_range text_ranges[] = {
66 { "_stext", "_etext" },
67 { "_sinittext", "_einittext" },
69 #define text_range_text (&text_ranges[0])
70 #define text_range_inittext (&text_ranges[1])
72 static struct addr_range percpu_range = {
73 "__per_cpu_start", "__per_cpu_end", -1ULL, 0
76 static struct sym_entry **table;
77 static unsigned int table_size, table_cnt;
78 static int all_symbols;
79 static int absolute_percpu;
80 static int base_relative;
83 static int token_profit[0x10000];
85 /* the table that holds the result of the compression */
86 static unsigned char best_table[256][2];
87 static unsigned char best_table_len[256];
90 static void usage(void)
92 fprintf(stderr, "Usage: kallsyms [--all-symbols] [--absolute-percpu] "
93 "[--base-relative] [--lto-clang] in.map > out.S\n");
97 static char *sym_name(const struct sym_entry *s)
99 return (char *)s->sym + 1;
102 static bool is_ignored_symbol(const char *name, char type)
104 /* Symbol names that exactly match to the following are ignored.*/
105 static const char * const ignored_symbols[] = {
107 * Symbols which vary between passes. Passes 1 and 2 must have
108 * identical symbol lists. The kallsyms_* symbols below are
109 * only added after pass 1, they would be included in pass 2
110 * when --all-symbols is specified so exclude them to get a
111 * stable symbol list.
113 "kallsyms_addresses",
115 "kallsyms_relative_base",
119 "kallsyms_token_table",
120 "kallsyms_token_index",
121 /* Exclude linker generated symbols which vary between passes */
122 "_SDA_BASE_", /* ppc */
123 "_SDA2_BASE_", /* ppc */
127 /* Symbol names that begin with the following are ignored.*/
128 static const char * const ignored_prefixes[] = {
129 "__efistub_", /* arm64 EFI stub namespace */
130 "__kvm_nvhe_$", /* arm64 local symbols in non-VHE KVM namespace */
131 "__kvm_nvhe_.L", /* arm64 local symbols in non-VHE KVM namespace */
132 "__AArch64ADRPThunk_", /* arm64 lld */
133 "__ARMV5PILongThunk_", /* arm lld */
134 "__ARMV7PILongThunk_",
135 "__ThumbV7PILongThunk_",
136 "__LA25Thunk_", /* mips lld */
138 "__kcfi_typeid_", /* CFI type identifiers */
142 /* Symbol names that end with the following are ignored.*/
143 static const char * const ignored_suffixes[] = {
144 "_from_arm", /* arm */
145 "_from_thumb", /* arm */
150 /* Symbol names that contain the following are ignored.*/
151 static const char * const ignored_matches[] = {
152 ".long_branch.", /* ppc stub */
153 ".plt_branch.", /* ppc stub */
157 const char * const *p;
159 for (p = ignored_symbols; *p; p++)
160 if (!strcmp(name, *p))
163 for (p = ignored_prefixes; *p; p++)
164 if (!strncmp(name, *p, strlen(*p)))
167 for (p = ignored_suffixes; *p; p++) {
168 int l = strlen(name) - strlen(*p);
170 if (l >= 0 && !strcmp(name + l, *p))
174 for (p = ignored_matches; *p; p++) {
175 if (strstr(name, *p))
179 if (type == 'U' || type == 'u')
181 /* exclude debugging symbols */
182 if (type == 'N' || type == 'n')
185 if (toupper(type) == 'A') {
186 /* Keep these useful absolute symbols */
187 if (strcmp(name, "__kernel_syscall_via_break") &&
188 strcmp(name, "__kernel_syscall_via_epc") &&
189 strcmp(name, "__kernel_sigtramp") &&
190 strcmp(name, "__gp"))
197 static void check_symbol_range(const char *sym, unsigned long long addr,
198 struct addr_range *ranges, int entries)
201 struct addr_range *ar;
203 for (i = 0; i < entries; ++i) {
206 if (strcmp(sym, ar->start_sym) == 0) {
209 } else if (strcmp(sym, ar->end_sym) == 0) {
216 static struct sym_entry *read_symbol(FILE *in)
218 char name[KSYM_NAME_LEN_BUFFER+1], type;
219 unsigned long long addr;
221 struct sym_entry *sym;
224 rc = fscanf(in, "%llx %c %" _stringify(KSYM_NAME_LEN_BUFFER) "s\n", &addr, &type, name);
226 if (rc != EOF && fgets(name, ARRAY_SIZE(name), in) == NULL)
227 fprintf(stderr, "Read error or end of file.\n");
230 if (strlen(name) >= KSYM_NAME_LEN) {
231 fprintf(stderr, "Symbol %s too long for kallsyms (%zu >= %d).\n"
232 "Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
233 name, strlen(name), KSYM_NAME_LEN);
237 if (strcmp(name, "_text") == 0)
240 /* Ignore most absolute/undefined (?) symbols. */
241 if (is_ignored_symbol(name, type))
244 check_symbol_range(name, addr, text_ranges, ARRAY_SIZE(text_ranges));
245 check_symbol_range(name, addr, &percpu_range, 1);
247 /* include the type field in the symbol name, so that it gets
248 * compressed together */
250 len = strlen(name) + 1;
252 sym = malloc(sizeof(*sym) + len + 1);
254 fprintf(stderr, "kallsyms failure: "
255 "unable to allocate required amount of memory\n");
261 strcpy(sym_name(sym), name);
262 sym->percpu_absolute = 0;
267 static int symbol_in_range(const struct sym_entry *s,
268 const struct addr_range *ranges, int entries)
271 const struct addr_range *ar;
273 for (i = 0; i < entries; ++i) {
276 if (s->addr >= ar->start && s->addr <= ar->end)
283 static int symbol_valid(const struct sym_entry *s)
285 const char *name = sym_name(s);
287 /* if --all-symbols is not specified, then symbols outside the text
288 * and inittext sections are discarded */
290 if (symbol_in_range(s, text_ranges,
291 ARRAY_SIZE(text_ranges)) == 0)
293 /* Corner case. Discard any symbols with the same value as
294 * _etext _einittext; they can move between pass 1 and 2 when
295 * the kallsyms data are added. If these symbols move then
296 * they may get dropped in pass 2, which breaks the kallsyms
299 if ((s->addr == text_range_text->end &&
300 strcmp(name, text_range_text->end_sym)) ||
301 (s->addr == text_range_inittext->end &&
302 strcmp(name, text_range_inittext->end_sym)))
309 /* remove all the invalid symbols from the table */
310 static void shrink_table(void)
315 for (i = 0; i < table_cnt; i++) {
316 if (symbol_valid(table[i])) {
318 table[pos] = table[i];
326 /* When valid symbol is not registered, exit to error */
328 fprintf(stderr, "No valid symbol.\n");
333 static void read_map(const char *in)
336 struct sym_entry *sym;
345 sym = read_symbol(fp);
349 sym->start_pos = table_cnt;
351 if (table_cnt >= table_size) {
353 table = realloc(table, sizeof(*table) * table_size);
355 fprintf(stderr, "out of memory\n");
361 table[table_cnt++] = sym;
367 static void output_label(const char *label)
369 printf(".globl %s\n", label);
371 printf("%s:\n", label);
374 /* Provide proper symbols relocatability by their '_text' relativeness. */
375 static void output_address(unsigned long long addr)
378 printf("\tPTR\t_text + %#llx\n", addr - _text);
380 printf("\tPTR\t_text - %#llx\n", _text - addr);
383 /* uncompress a compressed symbol. When this function is called, the best table
384 * might still be compressed itself, so the function needs to be recursive */
385 static int expand_symbol(const unsigned char *data, int len, char *result)
387 int c, rlen, total=0;
391 /* if the table holds a single char that is the same as the one
392 * we are looking for, then end the search */
393 if (best_table[c][0]==c && best_table_len[c]==1) {
397 /* if not, recurse and expand */
398 rlen = expand_symbol(best_table[c], best_table_len[c], result);
410 static int symbol_absolute(const struct sym_entry *s)
412 return s->percpu_absolute;
415 static char * s_name(char *buf)
417 /* Skip the symbol type */
421 static void cleanup_symbol_name(char *s)
435 * As above, replacing '.' with '\0' does not affect the main sorting,
436 * but it helps us with subsorting.
443 static int compare_names(const void *a, const void *b)
446 char sa_namebuf[KSYM_NAME_LEN];
447 char sb_namebuf[KSYM_NAME_LEN];
448 const struct sym_entry *sa = *(const struct sym_entry **)a;
449 const struct sym_entry *sb = *(const struct sym_entry **)b;
451 expand_symbol(sa->sym, sa->len, sa_namebuf);
452 expand_symbol(sb->sym, sb->len, sb_namebuf);
453 cleanup_symbol_name(s_name(sa_namebuf));
454 cleanup_symbol_name(s_name(sb_namebuf));
455 ret = strcmp(s_name(sa_namebuf), s_name(sb_namebuf));
457 if (sa->addr > sb->addr)
459 else if (sa->addr < sb->addr)
463 return (int)(sa->seq - sb->seq);
469 static void sort_symbols_by_name(void)
471 qsort(table, table_cnt, sizeof(table[0]), compare_names);
474 static void write_src(void)
476 unsigned int i, k, off;
477 unsigned int best_idx[256];
478 unsigned int *markers;
479 char buf[KSYM_NAME_LEN];
481 printf("#include <asm/bitsperlong.h>\n");
482 printf("#if BITS_PER_LONG == 64\n");
483 printf("#define PTR .quad\n");
484 printf("#define ALGN .balign 8\n");
486 printf("#define PTR .long\n");
487 printf("#define ALGN .balign 4\n");
490 printf("\t.section .rodata, \"a\"\n");
493 output_label("kallsyms_addresses");
495 output_label("kallsyms_offsets");
497 for (i = 0; i < table_cnt; i++) {
500 * Use the offset relative to the lowest value
501 * encountered of all relative symbols, and emit
502 * non-relocatable fixed offsets that will be fixed
509 if (!absolute_percpu) {
510 offset = table[i]->addr - relative_base;
511 overflow = (offset < 0 || offset > UINT_MAX);
512 } else if (symbol_absolute(table[i])) {
513 offset = table[i]->addr;
514 overflow = (offset < 0 || offset > INT_MAX);
516 offset = relative_base - table[i]->addr - 1;
517 overflow = (offset < INT_MIN || offset >= 0);
520 fprintf(stderr, "kallsyms failure: "
521 "%s symbol value %#llx out of range in relative mode\n",
522 symbol_absolute(table[i]) ? "absolute" : "relative",
526 printf("\t.long\t%#x\n", (int)offset);
527 } else if (!symbol_absolute(table[i])) {
528 output_address(table[i]->addr);
530 printf("\tPTR\t%#llx\n", table[i]->addr);
536 output_label("kallsyms_relative_base");
537 output_address(relative_base);
541 output_label("kallsyms_num_syms");
542 printf("\t.long\t%u\n", table_cnt);
545 /* table of offset markers, that give the offset in the compressed stream
546 * every 256 symbols */
547 markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
549 fprintf(stderr, "kallsyms failure: "
550 "unable to allocate required memory\n");
554 output_label("kallsyms_names");
556 for (i = 0; i < table_cnt; i++) {
558 markers[i >> 8] = off;
561 /* There cannot be any symbol of length zero. */
562 if (table[i]->len == 0) {
563 fprintf(stderr, "kallsyms failure: "
564 "unexpected zero symbol length\n");
568 /* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
569 if (table[i]->len > 0x3FFF) {
570 fprintf(stderr, "kallsyms failure: "
571 "unexpected huge symbol length\n");
575 /* Encode length with ULEB128. */
576 if (table[i]->len <= 0x7F) {
577 /* Most symbols use a single byte for the length. */
578 printf("\t.byte 0x%02x", table[i]->len);
579 off += table[i]->len + 1;
581 /* "Big" symbols use two bytes. */
582 printf("\t.byte 0x%02x, 0x%02x",
583 (table[i]->len & 0x7F) | 0x80,
584 (table[i]->len >> 7) & 0x7F);
585 off += table[i]->len + 2;
587 for (k = 0; k < table[i]->len; k++)
588 printf(", 0x%02x", table[i]->sym[k]);
593 output_label("kallsyms_markers");
594 for (i = 0; i < ((table_cnt + 255) >> 8); i++)
595 printf("\t.long\t%u\n", markers[i]);
600 sort_symbols_by_name();
601 output_label("kallsyms_seqs_of_names");
602 for (i = 0; i < table_cnt; i++)
603 printf("\t.byte 0x%02x, 0x%02x, 0x%02x\n",
604 (unsigned char)(table[i]->seq >> 16),
605 (unsigned char)(table[i]->seq >> 8),
606 (unsigned char)(table[i]->seq >> 0));
609 output_label("kallsyms_token_table");
611 for (i = 0; i < 256; i++) {
613 expand_symbol(best_table[i], best_table_len[i], buf);
614 printf("\t.asciz\t\"%s\"\n", buf);
615 off += strlen(buf) + 1;
619 output_label("kallsyms_token_index");
620 for (i = 0; i < 256; i++)
621 printf("\t.short\t%d\n", best_idx[i]);
626 /* table lookup compression functions */
628 /* count all the possible tokens in a symbol */
629 static void learn_symbol(const unsigned char *symbol, int len)
633 for (i = 0; i < len - 1; i++)
634 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
637 /* decrease the count for all the possible tokens in a symbol */
638 static void forget_symbol(const unsigned char *symbol, int len)
642 for (i = 0; i < len - 1; i++)
643 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
646 /* do the initial token count */
647 static void build_initial_token_table(void)
651 for (i = 0; i < table_cnt; i++)
652 learn_symbol(table[i]->sym, table[i]->len);
655 static unsigned char *find_token(unsigned char *str, int len,
656 const unsigned char *token)
660 for (i = 0; i < len - 1; i++) {
661 if (str[i] == token[0] && str[i+1] == token[1])
667 /* replace a given token in all the valid symbols. Use the sampled symbols
668 * to update the counts */
669 static void compress_symbols(const unsigned char *str, int idx)
671 unsigned int i, len, size;
672 unsigned char *p1, *p2;
674 for (i = 0; i < table_cnt; i++) {
679 /* find the token on the symbol */
680 p2 = find_token(p1, len, str);
683 /* decrease the counts for this symbol's tokens */
684 forget_symbol(table[i]->sym, len);
692 memmove(p2, p2 + 1, size);
698 /* find the token on the symbol */
699 p2 = find_token(p1, size, str);
705 /* increase the counts for this symbol's new tokens */
706 learn_symbol(table[i]->sym, len);
710 /* search the token with the maximum profit */
711 static int find_best_token(void)
713 int i, best, bestprofit;
718 for (i = 0; i < 0x10000; i++) {
719 if (token_profit[i] > bestprofit) {
721 bestprofit = token_profit[i];
727 /* this is the core of the algorithm: calculate the "best" table */
728 static void optimize_result(void)
732 /* using the '\0' symbol last allows compress_symbols to use standard
733 * fast string functions */
734 for (i = 255; i >= 0; i--) {
736 /* if this table slot is empty (it is not used by an actual
737 * original char code */
738 if (!best_table_len[i]) {
740 /* find the token with the best profit value */
741 best = find_best_token();
742 if (token_profit[best] == 0)
745 /* place it in the "best" table */
746 best_table_len[i] = 2;
747 best_table[i][0] = best & 0xFF;
748 best_table[i][1] = (best >> 8) & 0xFF;
750 /* replace this token in all the valid symbols */
751 compress_symbols(best_table[i], i);
756 /* start by placing the symbols that are actually used on the table */
757 static void insert_real_symbols_in_table(void)
759 unsigned int i, j, c;
761 for (i = 0; i < table_cnt; i++) {
762 for (j = 0; j < table[i]->len; j++) {
763 c = table[i]->sym[j];
770 static void optimize_token_table(void)
772 build_initial_token_table();
774 insert_real_symbols_in_table();
779 /* guess for "linker script provide" symbol */
780 static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
782 const char *symbol = sym_name(se);
783 int len = se->len - 1;
788 if (symbol[0] != '_' || symbol[1] != '_')
792 if (!memcmp(symbol + 2, "start_", 6))
796 if (!memcmp(symbol + 2, "stop_", 5))
800 if (!memcmp(symbol + 2, "end_", 4))
804 if (!memcmp(symbol + len - 6, "_start", 6))
808 if (!memcmp(symbol + len - 4, "_end", 4))
814 static int compare_symbols(const void *a, const void *b)
816 const struct sym_entry *sa = *(const struct sym_entry **)a;
817 const struct sym_entry *sb = *(const struct sym_entry **)b;
820 /* sort by address first */
821 if (sa->addr > sb->addr)
823 if (sa->addr < sb->addr)
826 /* sort by "weakness" type */
827 wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
828 wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
832 /* sort by "linker script provide" type */
833 wa = may_be_linker_script_provide_symbol(sa);
834 wb = may_be_linker_script_provide_symbol(sb);
838 /* sort by the number of prefix underscores */
839 wa = strspn(sym_name(sa), "_");
840 wb = strspn(sym_name(sb), "_");
844 /* sort by initial order, so that other symbols are left undisturbed */
845 return sa->start_pos - sb->start_pos;
848 static void sort_symbols(void)
850 qsort(table, table_cnt, sizeof(table[0]), compare_symbols);
853 static void make_percpus_absolute(void)
857 for (i = 0; i < table_cnt; i++)
858 if (symbol_in_range(table[i], &percpu_range, 1)) {
860 * Keep the 'A' override for percpu symbols to
861 * ensure consistent behavior compared to older
862 * versions of this tool.
864 table[i]->sym[0] = 'A';
865 table[i]->percpu_absolute = 1;
869 /* find the minimum non-absolute symbol address */
870 static void record_relative_base(void)
874 for (i = 0; i < table_cnt; i++)
875 if (!symbol_absolute(table[i])) {
877 * The table is sorted by address.
878 * Take the first non-absolute symbol value.
880 relative_base = table[i]->addr;
885 int main(int argc, char **argv)
888 static struct option long_options[] = {
889 {"all-symbols", no_argument, &all_symbols, 1},
890 {"absolute-percpu", no_argument, &absolute_percpu, 1},
891 {"base-relative", no_argument, &base_relative, 1},
892 {"lto-clang", no_argument, <o_clang, 1},
896 int c = getopt_long(argc, argv, "", long_options, NULL);
907 read_map(argv[optind]);
910 make_percpus_absolute();
913 record_relative_base();
914 optimize_token_table();