]>
git.ipfire.org Git - thirdparty/linux.git/blob - scripts/kallsyms.c
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: kallsyms [--all-symbols] [--absolute-percpu]
9 * [--base-relative] [--lto-clang] in.map > out.S
11 * 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
31 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
33 #define KSYM_NAME_LEN 512
36 unsigned long long addr
;
39 unsigned int start_pos
;
40 unsigned int percpu_absolute
;
45 const char *start_sym
, *end_sym
;
46 unsigned long long start
, end
;
49 static unsigned long long _text
;
50 static unsigned long long relative_base
;
51 static struct addr_range text_ranges
[] = {
52 { "_stext", "_etext" },
53 { "_sinittext", "_einittext" },
55 #define text_range_text (&text_ranges[0])
56 #define text_range_inittext (&text_ranges[1])
58 static struct addr_range percpu_range
= {
59 "__per_cpu_start", "__per_cpu_end", -1ULL, 0
62 static struct sym_entry
**table
;
63 static unsigned int table_size
, table_cnt
;
64 static int all_symbols
;
65 static int absolute_percpu
;
66 static int base_relative
;
69 static int token_profit
[0x10000];
71 /* the table that holds the result of the compression */
72 static unsigned char best_table
[256][2];
73 static unsigned char best_table_len
[256];
76 static void usage(void)
78 fprintf(stderr
, "Usage: kallsyms [--all-symbols] [--absolute-percpu] "
79 "[--base-relative] [--lto-clang] in.map > out.S\n");
83 static char *sym_name(const struct sym_entry
*s
)
85 return (char *)s
->sym
+ 1;
88 static bool is_ignored_symbol(const char *name
, char type
)
90 if (type
== 'u' || type
== 'n')
93 if (toupper(type
) == 'A') {
94 /* Keep these useful absolute symbols */
95 if (strcmp(name
, "__kernel_syscall_via_break") &&
96 strcmp(name
, "__kernel_syscall_via_epc") &&
97 strcmp(name
, "__kernel_sigtramp") &&
105 static void check_symbol_range(const char *sym
, unsigned long long addr
,
106 struct addr_range
*ranges
, int entries
)
109 struct addr_range
*ar
;
111 for (i
= 0; i
< entries
; ++i
) {
114 if (strcmp(sym
, ar
->start_sym
) == 0) {
117 } else if (strcmp(sym
, ar
->end_sym
) == 0) {
124 static struct sym_entry
*read_symbol(FILE *in
, char **buf
, size_t *buf_len
)
126 char *name
, type
, *p
;
127 unsigned long long addr
;
130 struct sym_entry
*sym
;
133 readlen
= getline(buf
, buf_len
, in
);
136 perror("read_symbol");
142 if ((*buf
)[readlen
- 1] == '\n')
143 (*buf
)[readlen
- 1] = 0;
145 addr
= strtoull(*buf
, &p
, 16);
147 if (*buf
== p
|| *p
++ != ' ' || !isascii((type
= *p
++)) || *p
++ != ' ') {
148 fprintf(stderr
, "line format error\n");
155 if (len
>= KSYM_NAME_LEN
) {
156 fprintf(stderr
, "Symbol %s too long for kallsyms (%zu >= %d).\n"
157 "Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
158 name
, len
, KSYM_NAME_LEN
);
162 if (strcmp(name
, "_text") == 0)
165 /* Ignore most absolute/undefined (?) symbols. */
166 if (is_ignored_symbol(name
, type
))
169 check_symbol_range(name
, addr
, text_ranges
, ARRAY_SIZE(text_ranges
));
170 check_symbol_range(name
, addr
, &percpu_range
, 1);
172 /* include the type field in the symbol name, so that it gets
173 * compressed together */
176 sym
= malloc(sizeof(*sym
) + len
+ 1);
178 fprintf(stderr
, "kallsyms failure: "
179 "unable to allocate required amount of memory\n");
185 strcpy(sym_name(sym
), name
);
186 sym
->percpu_absolute
= 0;
191 static int symbol_in_range(const struct sym_entry
*s
,
192 const struct addr_range
*ranges
, int entries
)
195 const struct addr_range
*ar
;
197 for (i
= 0; i
< entries
; ++i
) {
200 if (s
->addr
>= ar
->start
&& s
->addr
<= ar
->end
)
207 static int symbol_valid(const struct sym_entry
*s
)
209 const char *name
= sym_name(s
);
211 /* if --all-symbols is not specified, then symbols outside the text
212 * and inittext sections are discarded */
214 if (symbol_in_range(s
, text_ranges
,
215 ARRAY_SIZE(text_ranges
)) == 0)
217 /* Corner case. Discard any symbols with the same value as
218 * _etext _einittext; they can move between pass 1 and 2 when
219 * the kallsyms data are added. If these symbols move then
220 * they may get dropped in pass 2, which breaks the kallsyms
223 if ((s
->addr
== text_range_text
->end
&&
224 strcmp(name
, text_range_text
->end_sym
)) ||
225 (s
->addr
== text_range_inittext
->end
&&
226 strcmp(name
, text_range_inittext
->end_sym
)))
233 /* remove all the invalid symbols from the table */
234 static void shrink_table(void)
239 for (i
= 0; i
< table_cnt
; i
++) {
240 if (symbol_valid(table
[i
])) {
242 table
[pos
] = table
[i
];
250 /* When valid symbol is not registered, exit to error */
252 fprintf(stderr
, "No valid symbol.\n");
257 static void read_map(const char *in
)
260 struct sym_entry
*sym
;
271 sym
= read_symbol(fp
, &buf
, &buflen
);
275 sym
->start_pos
= table_cnt
;
277 if (table_cnt
>= table_size
) {
279 table
= realloc(table
, sizeof(*table
) * table_size
);
281 fprintf(stderr
, "out of memory\n");
287 table
[table_cnt
++] = sym
;
294 static void output_label(const char *label
)
296 printf(".globl %s\n", label
);
298 printf("%s:\n", label
);
301 /* Provide proper symbols relocatability by their '_text' relativeness. */
302 static void output_address(unsigned long long addr
)
305 printf("\tPTR\t_text + %#llx\n", addr
- _text
);
307 printf("\tPTR\t_text - %#llx\n", _text
- addr
);
310 /* uncompress a compressed symbol. When this function is called, the best table
311 * might still be compressed itself, so the function needs to be recursive */
312 static int expand_symbol(const unsigned char *data
, int len
, char *result
)
314 int c
, rlen
, total
=0;
318 /* if the table holds a single char that is the same as the one
319 * we are looking for, then end the search */
320 if (best_table
[c
][0]==c
&& best_table_len
[c
]==1) {
324 /* if not, recurse and expand */
325 rlen
= expand_symbol(best_table
[c
], best_table_len
[c
], result
);
337 static int symbol_absolute(const struct sym_entry
*s
)
339 return s
->percpu_absolute
;
342 static void cleanup_symbol_name(char *s
)
353 * As above, replacing the first '.' in ".llvm." with '\0' does not
354 * affect the main sorting, but it helps us with subsorting.
356 p
= strstr(s
, ".llvm.");
361 static int compare_names(const void *a
, const void *b
)
364 const struct sym_entry
*sa
= *(const struct sym_entry
**)a
;
365 const struct sym_entry
*sb
= *(const struct sym_entry
**)b
;
367 ret
= strcmp(sym_name(sa
), sym_name(sb
));
369 if (sa
->addr
> sb
->addr
)
371 else if (sa
->addr
< sb
->addr
)
375 return (int)(sa
->seq
- sb
->seq
);
381 static void sort_symbols_by_name(void)
383 qsort(table
, table_cnt
, sizeof(table
[0]), compare_names
);
386 static void write_src(void)
388 unsigned int i
, k
, off
;
389 unsigned int best_idx
[256];
390 unsigned int *markers
;
391 char buf
[KSYM_NAME_LEN
];
393 printf("#include <asm/bitsperlong.h>\n");
394 printf("#if BITS_PER_LONG == 64\n");
395 printf("#define PTR .quad\n");
396 printf("#define ALGN .balign 8\n");
398 printf("#define PTR .long\n");
399 printf("#define ALGN .balign 4\n");
402 printf("\t.section .rodata, \"a\"\n");
404 output_label("kallsyms_num_syms");
405 printf("\t.long\t%u\n", table_cnt
);
408 /* table of offset markers, that give the offset in the compressed stream
409 * every 256 symbols */
410 markers
= malloc(sizeof(unsigned int) * ((table_cnt
+ 255) / 256));
412 fprintf(stderr
, "kallsyms failure: "
413 "unable to allocate required memory\n");
417 output_label("kallsyms_names");
419 for (i
= 0; i
< table_cnt
; i
++) {
421 markers
[i
>> 8] = off
;
424 /* There cannot be any symbol of length zero. */
425 if (table
[i
]->len
== 0) {
426 fprintf(stderr
, "kallsyms failure: "
427 "unexpected zero symbol length\n");
431 /* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
432 if (table
[i
]->len
> 0x3FFF) {
433 fprintf(stderr
, "kallsyms failure: "
434 "unexpected huge symbol length\n");
438 /* Encode length with ULEB128. */
439 if (table
[i
]->len
<= 0x7F) {
440 /* Most symbols use a single byte for the length. */
441 printf("\t.byte 0x%02x", table
[i
]->len
);
442 off
+= table
[i
]->len
+ 1;
444 /* "Big" symbols use two bytes. */
445 printf("\t.byte 0x%02x, 0x%02x",
446 (table
[i
]->len
& 0x7F) | 0x80,
447 (table
[i
]->len
>> 7) & 0x7F);
448 off
+= table
[i
]->len
+ 2;
450 for (k
= 0; k
< table
[i
]->len
; k
++)
451 printf(", 0x%02x", table
[i
]->sym
[k
]);
457 * Now that we wrote out the compressed symbol names, restore the
458 * original names, which are needed in some of the later steps.
460 for (i
= 0; i
< table_cnt
; i
++) {
461 expand_symbol(table
[i
]->sym
, table
[i
]->len
, buf
);
462 strcpy((char *)table
[i
]->sym
, buf
);
465 output_label("kallsyms_markers");
466 for (i
= 0; i
< ((table_cnt
+ 255) >> 8); i
++)
467 printf("\t.long\t%u\n", markers
[i
]);
472 output_label("kallsyms_token_table");
474 for (i
= 0; i
< 256; i
++) {
476 expand_symbol(best_table
[i
], best_table_len
[i
], buf
);
477 printf("\t.asciz\t\"%s\"\n", buf
);
478 off
+= strlen(buf
) + 1;
482 output_label("kallsyms_token_index");
483 for (i
= 0; i
< 256; i
++)
484 printf("\t.short\t%d\n", best_idx
[i
]);
488 output_label("kallsyms_addresses");
490 output_label("kallsyms_offsets");
492 for (i
= 0; i
< table_cnt
; i
++) {
495 * Use the offset relative to the lowest value
496 * encountered of all relative symbols, and emit
497 * non-relocatable fixed offsets that will be fixed
504 if (!absolute_percpu
) {
505 offset
= table
[i
]->addr
- relative_base
;
506 overflow
= (offset
< 0 || offset
> UINT_MAX
);
507 } else if (symbol_absolute(table
[i
])) {
508 offset
= table
[i
]->addr
;
509 overflow
= (offset
< 0 || offset
> INT_MAX
);
511 offset
= relative_base
- table
[i
]->addr
- 1;
512 overflow
= (offset
< INT_MIN
|| offset
>= 0);
515 fprintf(stderr
, "kallsyms failure: "
516 "%s symbol value %#llx out of range in relative mode\n",
517 symbol_absolute(table
[i
]) ? "absolute" : "relative",
521 printf("\t.long\t%#x /* %s */\n", (int)offset
, table
[i
]->sym
);
522 } else if (!symbol_absolute(table
[i
])) {
523 output_address(table
[i
]->addr
);
525 printf("\tPTR\t%#llx\n", table
[i
]->addr
);
531 output_label("kallsyms_relative_base");
532 output_address(relative_base
);
537 for (i
= 0; i
< table_cnt
; i
++)
538 cleanup_symbol_name((char *)table
[i
]->sym
);
540 sort_symbols_by_name();
541 output_label("kallsyms_seqs_of_names");
542 for (i
= 0; i
< table_cnt
; i
++)
543 printf("\t.byte 0x%02x, 0x%02x, 0x%02x\n",
544 (unsigned char)(table
[i
]->seq
>> 16),
545 (unsigned char)(table
[i
]->seq
>> 8),
546 (unsigned char)(table
[i
]->seq
>> 0));
551 /* table lookup compression functions */
553 /* count all the possible tokens in a symbol */
554 static void learn_symbol(const unsigned char *symbol
, int len
)
558 for (i
= 0; i
< len
- 1; i
++)
559 token_profit
[ symbol
[i
] + (symbol
[i
+ 1] << 8) ]++;
562 /* decrease the count for all the possible tokens in a symbol */
563 static void forget_symbol(const unsigned char *symbol
, int len
)
567 for (i
= 0; i
< len
- 1; i
++)
568 token_profit
[ symbol
[i
] + (symbol
[i
+ 1] << 8) ]--;
571 /* do the initial token count */
572 static void build_initial_token_table(void)
576 for (i
= 0; i
< table_cnt
; i
++)
577 learn_symbol(table
[i
]->sym
, table
[i
]->len
);
580 static unsigned char *find_token(unsigned char *str
, int len
,
581 const unsigned char *token
)
585 for (i
= 0; i
< len
- 1; i
++) {
586 if (str
[i
] == token
[0] && str
[i
+1] == token
[1])
592 /* replace a given token in all the valid symbols. Use the sampled symbols
593 * to update the counts */
594 static void compress_symbols(const unsigned char *str
, int idx
)
596 unsigned int i
, len
, size
;
597 unsigned char *p1
, *p2
;
599 for (i
= 0; i
< table_cnt
; i
++) {
604 /* find the token on the symbol */
605 p2
= find_token(p1
, len
, str
);
608 /* decrease the counts for this symbol's tokens */
609 forget_symbol(table
[i
]->sym
, len
);
617 memmove(p2
, p2
+ 1, size
);
623 /* find the token on the symbol */
624 p2
= find_token(p1
, size
, str
);
630 /* increase the counts for this symbol's new tokens */
631 learn_symbol(table
[i
]->sym
, len
);
635 /* search the token with the maximum profit */
636 static int find_best_token(void)
638 int i
, best
, bestprofit
;
643 for (i
= 0; i
< 0x10000; i
++) {
644 if (token_profit
[i
] > bestprofit
) {
646 bestprofit
= token_profit
[i
];
652 /* this is the core of the algorithm: calculate the "best" table */
653 static void optimize_result(void)
657 /* using the '\0' symbol last allows compress_symbols to use standard
658 * fast string functions */
659 for (i
= 255; i
>= 0; i
--) {
661 /* if this table slot is empty (it is not used by an actual
662 * original char code */
663 if (!best_table_len
[i
]) {
665 /* find the token with the best profit value */
666 best
= find_best_token();
667 if (token_profit
[best
] == 0)
670 /* place it in the "best" table */
671 best_table_len
[i
] = 2;
672 best_table
[i
][0] = best
& 0xFF;
673 best_table
[i
][1] = (best
>> 8) & 0xFF;
675 /* replace this token in all the valid symbols */
676 compress_symbols(best_table
[i
], i
);
681 /* start by placing the symbols that are actually used on the table */
682 static void insert_real_symbols_in_table(void)
684 unsigned int i
, j
, c
;
686 for (i
= 0; i
< table_cnt
; i
++) {
687 for (j
= 0; j
< table
[i
]->len
; j
++) {
688 c
= table
[i
]->sym
[j
];
695 static void optimize_token_table(void)
697 build_initial_token_table();
699 insert_real_symbols_in_table();
704 /* guess for "linker script provide" symbol */
705 static int may_be_linker_script_provide_symbol(const struct sym_entry
*se
)
707 const char *symbol
= sym_name(se
);
708 int len
= se
->len
- 1;
713 if (symbol
[0] != '_' || symbol
[1] != '_')
717 if (!memcmp(symbol
+ 2, "start_", 6))
721 if (!memcmp(symbol
+ 2, "stop_", 5))
725 if (!memcmp(symbol
+ 2, "end_", 4))
729 if (!memcmp(symbol
+ len
- 6, "_start", 6))
733 if (!memcmp(symbol
+ len
- 4, "_end", 4))
739 static int compare_symbols(const void *a
, const void *b
)
741 const struct sym_entry
*sa
= *(const struct sym_entry
**)a
;
742 const struct sym_entry
*sb
= *(const struct sym_entry
**)b
;
745 /* sort by address first */
746 if (sa
->addr
> sb
->addr
)
748 if (sa
->addr
< sb
->addr
)
751 /* sort by "weakness" type */
752 wa
= (sa
->sym
[0] == 'w') || (sa
->sym
[0] == 'W');
753 wb
= (sb
->sym
[0] == 'w') || (sb
->sym
[0] == 'W');
757 /* sort by "linker script provide" type */
758 wa
= may_be_linker_script_provide_symbol(sa
);
759 wb
= may_be_linker_script_provide_symbol(sb
);
763 /* sort by the number of prefix underscores */
764 wa
= strspn(sym_name(sa
), "_");
765 wb
= strspn(sym_name(sb
), "_");
769 /* sort by initial order, so that other symbols are left undisturbed */
770 return sa
->start_pos
- sb
->start_pos
;
773 static void sort_symbols(void)
775 qsort(table
, table_cnt
, sizeof(table
[0]), compare_symbols
);
778 static void make_percpus_absolute(void)
782 for (i
= 0; i
< table_cnt
; i
++)
783 if (symbol_in_range(table
[i
], &percpu_range
, 1)) {
785 * Keep the 'A' override for percpu symbols to
786 * ensure consistent behavior compared to older
787 * versions of this tool.
789 table
[i
]->sym
[0] = 'A';
790 table
[i
]->percpu_absolute
= 1;
794 /* find the minimum non-absolute symbol address */
795 static void record_relative_base(void)
799 for (i
= 0; i
< table_cnt
; i
++)
800 if (!symbol_absolute(table
[i
])) {
802 * The table is sorted by address.
803 * Take the first non-absolute symbol value.
805 relative_base
= table
[i
]->addr
;
810 int main(int argc
, char **argv
)
813 static const struct option long_options
[] = {
814 {"all-symbols", no_argument
, &all_symbols
, 1},
815 {"absolute-percpu", no_argument
, &absolute_percpu
, 1},
816 {"base-relative", no_argument
, &base_relative
, 1},
817 {"lto-clang", no_argument
, <o_clang
, 1},
821 int c
= getopt_long(argc
, argv
, "", long_options
, NULL
);
832 read_map(argv
[optind
]);
835 make_percpus_absolute();
838 record_relative_base();
839 optimize_token_table();