Merge tag 'kbuild-fixes-v5.0-2' of git://git.kernel.org/pub/scm/linux/kernel/git...
[sfrench/cifs-2.6.git] / scripts / kallsyms.c
1 /* 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  *
8  * Usage: nm -n vmlinux | scripts/kallsyms [--all-symbols] > symbols.S
9  *
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
17  *  of about 50%.
18  *
19  */
20
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24 #include <ctype.h>
25 #include <limits.h>
26
27 #ifndef ARRAY_SIZE
28 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
29 #endif
30
31 #define KSYM_NAME_LEN           128
32
33 struct sym_entry {
34         unsigned long long addr;
35         unsigned int len;
36         unsigned int start_pos;
37         unsigned char *sym;
38         unsigned int percpu_absolute;
39 };
40
41 struct addr_range {
42         const char *start_sym, *end_sym;
43         unsigned long long start, end;
44 };
45
46 static unsigned long long _text;
47 static unsigned long long relative_base;
48 static struct addr_range text_ranges[] = {
49         { "_stext",     "_etext"     },
50         { "_sinittext", "_einittext" },
51 };
52 #define text_range_text     (&text_ranges[0])
53 #define text_range_inittext (&text_ranges[1])
54
55 static struct addr_range percpu_range = {
56         "__per_cpu_start", "__per_cpu_end", -1ULL, 0
57 };
58
59 static struct sym_entry *table;
60 static unsigned int table_size, table_cnt;
61 static int all_symbols = 0;
62 static int absolute_percpu = 0;
63 static int base_relative = 0;
64
65 int token_profit[0x10000];
66
67 /* the table that holds the result of the compression */
68 unsigned char best_table[256][2];
69 unsigned char best_table_len[256];
70
71
72 static void usage(void)
73 {
74         fprintf(stderr, "Usage: kallsyms [--all-symbols] "
75                         "[--base-relative] < in.map > out.S\n");
76         exit(1);
77 }
78
79 /*
80  * This ignores the intensely annoying "mapping symbols" found
81  * in ARM ELF files: $a, $t and $d.
82  */
83 static inline int is_arm_mapping_symbol(const char *str)
84 {
85         return str[0] == '$' && strchr("axtd", str[1])
86                && (str[2] == '\0' || str[2] == '.');
87 }
88
89 static int check_symbol_range(const char *sym, unsigned long long addr,
90                               struct addr_range *ranges, int entries)
91 {
92         size_t i;
93         struct addr_range *ar;
94
95         for (i = 0; i < entries; ++i) {
96                 ar = &ranges[i];
97
98                 if (strcmp(sym, ar->start_sym) == 0) {
99                         ar->start = addr;
100                         return 0;
101                 } else if (strcmp(sym, ar->end_sym) == 0) {
102                         ar->end = addr;
103                         return 0;
104                 }
105         }
106
107         return 1;
108 }
109
110 static int read_symbol(FILE *in, struct sym_entry *s)
111 {
112         char sym[500], stype;
113         int rc;
114
115         rc = fscanf(in, "%llx %c %499s\n", &s->addr, &stype, sym);
116         if (rc != 3) {
117                 if (rc != EOF && fgets(sym, 500, in) == NULL)
118                         fprintf(stderr, "Read error or end of file.\n");
119                 return -1;
120         }
121         if (strlen(sym) >= KSYM_NAME_LEN) {
122                 fprintf(stderr, "Symbol %s too long for kallsyms (%zu >= %d).\n"
123                                 "Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
124                         sym, strlen(sym), KSYM_NAME_LEN);
125                 return -1;
126         }
127
128         /* Ignore most absolute/undefined (?) symbols. */
129         if (strcmp(sym, "_text") == 0)
130                 _text = s->addr;
131         else if (check_symbol_range(sym, s->addr, text_ranges,
132                                     ARRAY_SIZE(text_ranges)) == 0)
133                 /* nothing to do */;
134         else if (toupper(stype) == 'A')
135         {
136                 /* Keep these useful absolute symbols */
137                 if (strcmp(sym, "__kernel_syscall_via_break") &&
138                     strcmp(sym, "__kernel_syscall_via_epc") &&
139                     strcmp(sym, "__kernel_sigtramp") &&
140                     strcmp(sym, "__gp"))
141                         return -1;
142
143         }
144         else if (toupper(stype) == 'U' ||
145                  is_arm_mapping_symbol(sym))
146                 return -1;
147         /* exclude also MIPS ELF local symbols ($L123 instead of .L123) */
148         else if (sym[0] == '$')
149                 return -1;
150         /* exclude debugging symbols */
151         else if (stype == 'N' || stype == 'n')
152                 return -1;
153
154         /* include the type field in the symbol name, so that it gets
155          * compressed together */
156         s->len = strlen(sym) + 1;
157         s->sym = malloc(s->len + 1);
158         if (!s->sym) {
159                 fprintf(stderr, "kallsyms failure: "
160                         "unable to allocate required amount of memory\n");
161                 exit(EXIT_FAILURE);
162         }
163         strcpy((char *)s->sym + 1, sym);
164         s->sym[0] = stype;
165
166         s->percpu_absolute = 0;
167
168         /* Record if we've found __per_cpu_start/end. */
169         check_symbol_range(sym, s->addr, &percpu_range, 1);
170
171         return 0;
172 }
173
174 static int symbol_in_range(struct sym_entry *s, struct addr_range *ranges,
175                            int entries)
176 {
177         size_t i;
178         struct addr_range *ar;
179
180         for (i = 0; i < entries; ++i) {
181                 ar = &ranges[i];
182
183                 if (s->addr >= ar->start && s->addr <= ar->end)
184                         return 1;
185         }
186
187         return 0;
188 }
189
190 static int symbol_valid(struct sym_entry *s)
191 {
192         /* Symbols which vary between passes.  Passes 1 and 2 must have
193          * identical symbol lists.  The kallsyms_* symbols below are only added
194          * after pass 1, they would be included in pass 2 when --all-symbols is
195          * specified so exclude them to get a stable symbol list.
196          */
197         static char *special_symbols[] = {
198                 "kallsyms_addresses",
199                 "kallsyms_offsets",
200                 "kallsyms_relative_base",
201                 "kallsyms_num_syms",
202                 "kallsyms_names",
203                 "kallsyms_markers",
204                 "kallsyms_token_table",
205                 "kallsyms_token_index",
206
207         /* Exclude linker generated symbols which vary between passes */
208                 "_SDA_BASE_",           /* ppc */
209                 "_SDA2_BASE_",          /* ppc */
210                 NULL };
211
212         static char *special_prefixes[] = {
213                 "__crc_",               /* modversions */
214                 "__efistub_",           /* arm64 EFI stub namespace */
215                 NULL };
216
217         static char *special_suffixes[] = {
218                 "_veneer",              /* arm */
219                 "_from_arm",            /* arm */
220                 "_from_thumb",          /* arm */
221                 NULL };
222
223         int i;
224         char *sym_name = (char *)s->sym + 1;
225
226         /* if --all-symbols is not specified, then symbols outside the text
227          * and inittext sections are discarded */
228         if (!all_symbols) {
229                 if (symbol_in_range(s, text_ranges,
230                                     ARRAY_SIZE(text_ranges)) == 0)
231                         return 0;
232                 /* Corner case.  Discard any symbols with the same value as
233                  * _etext _einittext; they can move between pass 1 and 2 when
234                  * the kallsyms data are added.  If these symbols move then
235                  * they may get dropped in pass 2, which breaks the kallsyms
236                  * rules.
237                  */
238                 if ((s->addr == text_range_text->end &&
239                                 strcmp(sym_name,
240                                        text_range_text->end_sym)) ||
241                     (s->addr == text_range_inittext->end &&
242                                 strcmp(sym_name,
243                                        text_range_inittext->end_sym)))
244                         return 0;
245         }
246
247         /* Exclude symbols which vary between passes. */
248         for (i = 0; special_symbols[i]; i++)
249                 if (strcmp(sym_name, special_symbols[i]) == 0)
250                         return 0;
251
252         for (i = 0; special_prefixes[i]; i++) {
253                 int l = strlen(special_prefixes[i]);
254
255                 if (l <= strlen(sym_name) &&
256                     strncmp(sym_name, special_prefixes[i], l) == 0)
257                         return 0;
258         }
259
260         for (i = 0; special_suffixes[i]; i++) {
261                 int l = strlen(sym_name) - strlen(special_suffixes[i]);
262
263                 if (l >= 0 && strcmp(sym_name + l, special_suffixes[i]) == 0)
264                         return 0;
265         }
266
267         return 1;
268 }
269
270 static void read_map(FILE *in)
271 {
272         while (!feof(in)) {
273                 if (table_cnt >= table_size) {
274                         table_size += 10000;
275                         table = realloc(table, sizeof(*table) * table_size);
276                         if (!table) {
277                                 fprintf(stderr, "out of memory\n");
278                                 exit (1);
279                         }
280                 }
281                 if (read_symbol(in, &table[table_cnt]) == 0) {
282                         table[table_cnt].start_pos = table_cnt;
283                         table_cnt++;
284                 }
285         }
286 }
287
288 static void output_label(char *label)
289 {
290         printf(".globl %s\n", label);
291         printf("\tALGN\n");
292         printf("%s:\n", label);
293 }
294
295 /* uncompress a compressed symbol. When this function is called, the best table
296  * might still be compressed itself, so the function needs to be recursive */
297 static int expand_symbol(unsigned char *data, int len, char *result)
298 {
299         int c, rlen, total=0;
300
301         while (len) {
302                 c = *data;
303                 /* if the table holds a single char that is the same as the one
304                  * we are looking for, then end the search */
305                 if (best_table[c][0]==c && best_table_len[c]==1) {
306                         *result++ = c;
307                         total++;
308                 } else {
309                         /* if not, recurse and expand */
310                         rlen = expand_symbol(best_table[c], best_table_len[c], result);
311                         total += rlen;
312                         result += rlen;
313                 }
314                 data++;
315                 len--;
316         }
317         *result=0;
318
319         return total;
320 }
321
322 static int symbol_absolute(struct sym_entry *s)
323 {
324         return s->percpu_absolute;
325 }
326
327 static void write_src(void)
328 {
329         unsigned int i, k, off;
330         unsigned int best_idx[256];
331         unsigned int *markers;
332         char buf[KSYM_NAME_LEN];
333
334         printf("#include <asm/types.h>\n");
335         printf("#if BITS_PER_LONG == 64\n");
336         printf("#define PTR .quad\n");
337         printf("#define ALGN .balign 8\n");
338         printf("#else\n");
339         printf("#define PTR .long\n");
340         printf("#define ALGN .balign 4\n");
341         printf("#endif\n");
342
343         printf("\t.section .rodata, \"a\"\n");
344
345         /* Provide proper symbols relocatability by their relativeness
346          * to a fixed anchor point in the runtime image, either '_text'
347          * for absolute address tables, in which case the linker will
348          * emit the final addresses at build time. Otherwise, use the
349          * offset relative to the lowest value encountered of all relative
350          * symbols, and emit non-relocatable fixed offsets that will be fixed
351          * up at runtime.
352          *
353          * The symbol names cannot be used to construct normal symbol
354          * references as the list of symbols contains symbols that are
355          * declared static and are private to their .o files.  This prevents
356          * .tmp_kallsyms.o or any other object from referencing them.
357          */
358         if (!base_relative)
359                 output_label("kallsyms_addresses");
360         else
361                 output_label("kallsyms_offsets");
362
363         for (i = 0; i < table_cnt; i++) {
364                 if (base_relative) {
365                         long long offset;
366                         int overflow;
367
368                         if (!absolute_percpu) {
369                                 offset = table[i].addr - relative_base;
370                                 overflow = (offset < 0 || offset > UINT_MAX);
371                         } else if (symbol_absolute(&table[i])) {
372                                 offset = table[i].addr;
373                                 overflow = (offset < 0 || offset > INT_MAX);
374                         } else {
375                                 offset = relative_base - table[i].addr - 1;
376                                 overflow = (offset < INT_MIN || offset >= 0);
377                         }
378                         if (overflow) {
379                                 fprintf(stderr, "kallsyms failure: "
380                                         "%s symbol value %#llx out of range in relative mode\n",
381                                         symbol_absolute(&table[i]) ? "absolute" : "relative",
382                                         table[i].addr);
383                                 exit(EXIT_FAILURE);
384                         }
385                         printf("\t.long\t%#x\n", (int)offset);
386                 } else if (!symbol_absolute(&table[i])) {
387                         if (_text <= table[i].addr)
388                                 printf("\tPTR\t_text + %#llx\n",
389                                         table[i].addr - _text);
390                         else
391                                 printf("\tPTR\t_text - %#llx\n",
392                                         _text - table[i].addr);
393                 } else {
394                         printf("\tPTR\t%#llx\n", table[i].addr);
395                 }
396         }
397         printf("\n");
398
399         if (base_relative) {
400                 output_label("kallsyms_relative_base");
401                 printf("\tPTR\t_text - %#llx\n", _text - relative_base);
402                 printf("\n");
403         }
404
405         output_label("kallsyms_num_syms");
406         printf("\t.long\t%u\n", table_cnt);
407         printf("\n");
408
409         /* table of offset markers, that give the offset in the compressed stream
410          * every 256 symbols */
411         markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
412         if (!markers) {
413                 fprintf(stderr, "kallsyms failure: "
414                         "unable to allocate required memory\n");
415                 exit(EXIT_FAILURE);
416         }
417
418         output_label("kallsyms_names");
419         off = 0;
420         for (i = 0; i < table_cnt; i++) {
421                 if ((i & 0xFF) == 0)
422                         markers[i >> 8] = off;
423
424                 printf("\t.byte 0x%02x", table[i].len);
425                 for (k = 0; k < table[i].len; k++)
426                         printf(", 0x%02x", table[i].sym[k]);
427                 printf("\n");
428
429                 off += table[i].len + 1;
430         }
431         printf("\n");
432
433         output_label("kallsyms_markers");
434         for (i = 0; i < ((table_cnt + 255) >> 8); i++)
435                 printf("\t.long\t%u\n", markers[i]);
436         printf("\n");
437
438         free(markers);
439
440         output_label("kallsyms_token_table");
441         off = 0;
442         for (i = 0; i < 256; i++) {
443                 best_idx[i] = off;
444                 expand_symbol(best_table[i], best_table_len[i], buf);
445                 printf("\t.asciz\t\"%s\"\n", buf);
446                 off += strlen(buf) + 1;
447         }
448         printf("\n");
449
450         output_label("kallsyms_token_index");
451         for (i = 0; i < 256; i++)
452                 printf("\t.short\t%d\n", best_idx[i]);
453         printf("\n");
454 }
455
456
457 /* table lookup compression functions */
458
459 /* count all the possible tokens in a symbol */
460 static void learn_symbol(unsigned char *symbol, int len)
461 {
462         int i;
463
464         for (i = 0; i < len - 1; i++)
465                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
466 }
467
468 /* decrease the count for all the possible tokens in a symbol */
469 static void forget_symbol(unsigned char *symbol, int len)
470 {
471         int i;
472
473         for (i = 0; i < len - 1; i++)
474                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
475 }
476
477 /* remove all the invalid symbols from the table and do the initial token count */
478 static void build_initial_tok_table(void)
479 {
480         unsigned int i, pos;
481
482         pos = 0;
483         for (i = 0; i < table_cnt; i++) {
484                 if ( symbol_valid(&table[i]) ) {
485                         if (pos != i)
486                                 table[pos] = table[i];
487                         learn_symbol(table[pos].sym, table[pos].len);
488                         pos++;
489                 }
490         }
491         table_cnt = pos;
492 }
493
494 static void *find_token(unsigned char *str, int len, unsigned char *token)
495 {
496         int i;
497
498         for (i = 0; i < len - 1; i++) {
499                 if (str[i] == token[0] && str[i+1] == token[1])
500                         return &str[i];
501         }
502         return NULL;
503 }
504
505 /* replace a given token in all the valid symbols. Use the sampled symbols
506  * to update the counts */
507 static void compress_symbols(unsigned char *str, int idx)
508 {
509         unsigned int i, len, size;
510         unsigned char *p1, *p2;
511
512         for (i = 0; i < table_cnt; i++) {
513
514                 len = table[i].len;
515                 p1 = table[i].sym;
516
517                 /* find the token on the symbol */
518                 p2 = find_token(p1, len, str);
519                 if (!p2) continue;
520
521                 /* decrease the counts for this symbol's tokens */
522                 forget_symbol(table[i].sym, len);
523
524                 size = len;
525
526                 do {
527                         *p2 = idx;
528                         p2++;
529                         size -= (p2 - p1);
530                         memmove(p2, p2 + 1, size);
531                         p1 = p2;
532                         len--;
533
534                         if (size < 2) break;
535
536                         /* find the token on the symbol */
537                         p2 = find_token(p1, size, str);
538
539                 } while (p2);
540
541                 table[i].len = len;
542
543                 /* increase the counts for this symbol's new tokens */
544                 learn_symbol(table[i].sym, len);
545         }
546 }
547
548 /* search the token with the maximum profit */
549 static int find_best_token(void)
550 {
551         int i, best, bestprofit;
552
553         bestprofit=-10000;
554         best = 0;
555
556         for (i = 0; i < 0x10000; i++) {
557                 if (token_profit[i] > bestprofit) {
558                         best = i;
559                         bestprofit = token_profit[i];
560                 }
561         }
562         return best;
563 }
564
565 /* this is the core of the algorithm: calculate the "best" table */
566 static void optimize_result(void)
567 {
568         int i, best;
569
570         /* using the '\0' symbol last allows compress_symbols to use standard
571          * fast string functions */
572         for (i = 255; i >= 0; i--) {
573
574                 /* if this table slot is empty (it is not used by an actual
575                  * original char code */
576                 if (!best_table_len[i]) {
577
578                         /* find the token with the best profit value */
579                         best = find_best_token();
580                         if (token_profit[best] == 0)
581                                 break;
582
583                         /* place it in the "best" table */
584                         best_table_len[i] = 2;
585                         best_table[i][0] = best & 0xFF;
586                         best_table[i][1] = (best >> 8) & 0xFF;
587
588                         /* replace this token in all the valid symbols */
589                         compress_symbols(best_table[i], i);
590                 }
591         }
592 }
593
594 /* start by placing the symbols that are actually used on the table */
595 static void insert_real_symbols_in_table(void)
596 {
597         unsigned int i, j, c;
598
599         memset(best_table, 0, sizeof(best_table));
600         memset(best_table_len, 0, sizeof(best_table_len));
601
602         for (i = 0; i < table_cnt; i++) {
603                 for (j = 0; j < table[i].len; j++) {
604                         c = table[i].sym[j];
605                         best_table[c][0]=c;
606                         best_table_len[c]=1;
607                 }
608         }
609 }
610
611 static void optimize_token_table(void)
612 {
613         build_initial_tok_table();
614
615         insert_real_symbols_in_table();
616
617         /* When valid symbol is not registered, exit to error */
618         if (!table_cnt) {
619                 fprintf(stderr, "No valid symbol.\n");
620                 exit(1);
621         }
622
623         optimize_result();
624 }
625
626 /* guess for "linker script provide" symbol */
627 static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
628 {
629         const char *symbol = (char *)se->sym + 1;
630         int len = se->len - 1;
631
632         if (len < 8)
633                 return 0;
634
635         if (symbol[0] != '_' || symbol[1] != '_')
636                 return 0;
637
638         /* __start_XXXXX */
639         if (!memcmp(symbol + 2, "start_", 6))
640                 return 1;
641
642         /* __stop_XXXXX */
643         if (!memcmp(symbol + 2, "stop_", 5))
644                 return 1;
645
646         /* __end_XXXXX */
647         if (!memcmp(symbol + 2, "end_", 4))
648                 return 1;
649
650         /* __XXXXX_start */
651         if (!memcmp(symbol + len - 6, "_start", 6))
652                 return 1;
653
654         /* __XXXXX_end */
655         if (!memcmp(symbol + len - 4, "_end", 4))
656                 return 1;
657
658         return 0;
659 }
660
661 static int prefix_underscores_count(const char *str)
662 {
663         const char *tail = str;
664
665         while (*tail == '_')
666                 tail++;
667
668         return tail - str;
669 }
670
671 static int compare_symbols(const void *a, const void *b)
672 {
673         const struct sym_entry *sa;
674         const struct sym_entry *sb;
675         int wa, wb;
676
677         sa = a;
678         sb = b;
679
680         /* sort by address first */
681         if (sa->addr > sb->addr)
682                 return 1;
683         if (sa->addr < sb->addr)
684                 return -1;
685
686         /* sort by "weakness" type */
687         wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
688         wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
689         if (wa != wb)
690                 return wa - wb;
691
692         /* sort by "linker script provide" type */
693         wa = may_be_linker_script_provide_symbol(sa);
694         wb = may_be_linker_script_provide_symbol(sb);
695         if (wa != wb)
696                 return wa - wb;
697
698         /* sort by the number of prefix underscores */
699         wa = prefix_underscores_count((const char *)sa->sym + 1);
700         wb = prefix_underscores_count((const char *)sb->sym + 1);
701         if (wa != wb)
702                 return wa - wb;
703
704         /* sort by initial order, so that other symbols are left undisturbed */
705         return sa->start_pos - sb->start_pos;
706 }
707
708 static void sort_symbols(void)
709 {
710         qsort(table, table_cnt, sizeof(struct sym_entry), compare_symbols);
711 }
712
713 static void make_percpus_absolute(void)
714 {
715         unsigned int i;
716
717         for (i = 0; i < table_cnt; i++)
718                 if (symbol_in_range(&table[i], &percpu_range, 1)) {
719                         /*
720                          * Keep the 'A' override for percpu symbols to
721                          * ensure consistent behavior compared to older
722                          * versions of this tool.
723                          */
724                         table[i].sym[0] = 'A';
725                         table[i].percpu_absolute = 1;
726                 }
727 }
728
729 /* find the minimum non-absolute symbol address */
730 static void record_relative_base(void)
731 {
732         unsigned int i;
733
734         relative_base = -1ULL;
735         for (i = 0; i < table_cnt; i++)
736                 if (!symbol_absolute(&table[i]) &&
737                     table[i].addr < relative_base)
738                         relative_base = table[i].addr;
739 }
740
741 int main(int argc, char **argv)
742 {
743         if (argc >= 2) {
744                 int i;
745                 for (i = 1; i < argc; i++) {
746                         if(strcmp(argv[i], "--all-symbols") == 0)
747                                 all_symbols = 1;
748                         else if (strcmp(argv[i], "--absolute-percpu") == 0)
749                                 absolute_percpu = 1;
750                         else if (strcmp(argv[i], "--base-relative") == 0)
751                                 base_relative = 1;
752                         else
753                                 usage();
754                 }
755         } else if (argc != 1)
756                 usage();
757
758         read_map(stdin);
759         if (absolute_percpu)
760                 make_percpus_absolute();
761         if (base_relative)
762                 record_relative_base();
763         sort_symbols();
764         optimize_token_table();
765         write_src();
766
767         return 0;
768 }