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
  26 #define KSYM_NAME_LEN           128
  27
  28 struct sym_entry {
  29         unsigned long long addr;
  30         unsigned int len;
  31         unsigned int start_pos;
  32         unsigned char *sym;
  33 };
  34
  35 static struct sym_entry *table;
  36 static unsigned int table_size, table_cnt;
  37 static unsigned long long _text, _stext, _etext, _sinittext, _einittext;
  38 static int all_symbols = 0;
  39 static char symbol_prefix_char = '\0';
  40
  41 int token_profit[0x10000];
  42
  43 /* the table that holds the result of the compression */
  44 unsigned char best_table[256][2];
  45 unsigned char best_table_len[256];
  46
  47
  48 static void usage(void)
  49 {
  50         fprintf(stderr, "Usage: kallsyms [--all-symbols] [--symbol-prefix=<prefix char>] < in.map > out.S\n");
  51         exit(1);
  52 }
  53
  54 /*
  55  * This ignores the intensely annoying "mapping symbols" found
  56  * in ARM ELF files: $a, $t and $d.
  57  */
  58 static inline int is_arm_mapping_symbol(const char *str)
  59 {
  60         return str[0] == '$' && strchr("atd", str[1])
  61                && (str[2] == '\0' || str[2] == '.');
  62 }
  63
  64 static int read_symbol(FILE *in, struct sym_entry *s)
  65 {
  66         char str[500];
  67         char *sym, stype;
  68         int rc;
  69
  70         rc = fscanf(in, "%llx %c %499s\n", &s->addr, &stype, str);
  71         if (rc != 3) {
  72                 if (rc != EOF) {
  73                         /* skip line */
  74                         fgets(str, 500, in);
  75                 }
  76                 return -1;
  77         }
  78
  79         sym = str;
  80         /* skip prefix char */
  81         if (symbol_prefix_char && str[0] == symbol_prefix_char)
  82                 sym++;
  83
  84         /* Ignore most absolute/undefined (?) symbols. */
  85         if (strcmp(sym, "_text") == 0)
  86                 _text = s->addr;
  87         else if (strcmp(sym, "_stext") == 0)
  88                 _stext = s->addr;
  89         else if (strcmp(sym, "_etext") == 0)
  90                 _etext = s->addr;
  91         else if (strcmp(sym, "_sinittext") == 0)
  92                 _sinittext = s->addr;
  93         else if (strcmp(sym, "_einittext") == 0)
  94                 _einittext = s->addr;
  95         else if (toupper(stype) == 'A')
  96         {
  97                 /* Keep these useful absolute symbols */
  98                 if (strcmp(sym, "__kernel_syscall_via_break") &&
  99                     strcmp(sym, "__kernel_syscall_via_epc") &&
 100                     strcmp(sym, "__kernel_sigtramp") &&
 101                     strcmp(sym, "__gp"))
 102                         return -1;
 103
 104         }
 105         else if (toupper(stype) == 'U' ||
 106                  is_arm_mapping_symbol(sym))
 107                 return -1;
 108         /* exclude also MIPS ELF local symbols ($L123 instead of .L123) */
 109         else if (str[0] == '$')
 110                 return -1;
 111         /* exclude debugging symbols */
 112         else if (stype == 'N')
 113                 return -1;
 114
 115         /* include the type field in the symbol name, so that it gets
 116          * compressed together */
 117         s->len = strlen(str) + 1;
 118         s->sym = malloc(s->len + 1);
 119         if (!s->sym) {
 120                 fprintf(stderr, "kallsyms failure: "
 121                         "unable to allocate required amount of memory\n");
 122                 exit(EXIT_FAILURE);
 123         }
 124         strcpy((char *)s->sym + 1, str);
 125         s->sym[0] = stype;
 126
 127         return 0;
 128 }
 129
 130 static int symbol_valid(struct sym_entry *s)
 131 {
 132         /* Symbols which vary between passes.  Passes 1 and 2 must have
 133          * identical symbol lists.  The kallsyms_* symbols below are only added
 134          * after pass 1, they would be included in pass 2 when --all-symbols is
 135          * specified so exclude them to get a stable symbol list.
 136          */
 137         static char *special_symbols[] = {
 138                 "kallsyms_addresses",
 139                 "kallsyms_num_syms",
 140                 "kallsyms_names",
 141                 "kallsyms_markers",
 142                 "kallsyms_token_table",
 143                 "kallsyms_token_index",
 144
 145         /* Exclude linker generated symbols which vary between passes */
 146                 "_SDA_BASE_",           /* ppc */
 147                 "_SDA2_BASE_",          /* ppc */
 148                 NULL };
 149         int i;
 150         int offset = 1;
 151
 152         /* skip prefix char */
 153         if (symbol_prefix_char && *(s->sym + 1) == symbol_prefix_char)
 154                 offset++;
 155
 156         /* if --all-symbols is not specified, then symbols outside the text
 157          * and inittext sections are discarded */
 158         if (!all_symbols) {
 159                 if ((s->addr < _stext || s->addr > _etext)
 160                     && (s->addr < _sinittext || s->addr > _einittext))
 161                         return 0;
 162                 /* Corner case.  Discard any symbols with the same value as
 163                  * _etext _einittext; they can move between pass 1 and 2 when
 164                  * the kallsyms data are added.  If these symbols move then
 165                  * they may get dropped in pass 2, which breaks the kallsyms
 166                  * rules.
 167                  */
 168                 if ((s->addr == _etext &&
 169                                 strcmp((char *)s->sym + offset, "_etext")) ||
 170                     (s->addr == _einittext &&
 171                                 strcmp((char *)s->sym + offset, "_einittext")))
 172                         return 0;
 173         }
 174
 175         /* Exclude symbols which vary between passes. */
 176         if (strstr((char *)s->sym + offset, "_compiled."))
 177                 return 0;
 178
 179         for (i = 0; special_symbols[i]; i++)
 180                 if( strcmp((char *)s->sym + offset, special_symbols[i]) == 0 )
 181                         return 0;
 182
 183         return 1;
 184 }
 185
 186 static void read_map(FILE *in)
 187 {
 188         while (!feof(in)) {
 189                 if (table_cnt >= table_size) {
 190                         table_size += 10000;
 191                         table = realloc(table, sizeof(*table) * table_size);
 192                         if (!table) {
 193                                 fprintf(stderr, "out of memory\n");
 194                                 exit (1);
 195                         }
 196                 }
 197                 if (read_symbol(in, &table[table_cnt]) == 0) {
 198                         table[table_cnt].start_pos = table_cnt;
 199                         table_cnt++;
 200                 }
 201         }
 202 }
 203
 204 static void output_label(char *label)
 205 {
 206         if (symbol_prefix_char)
 207                 printf(".globl %c%s\n", symbol_prefix_char, label);
 208         else
 209                 printf(".globl %s\n", label);
 210         printf("\tALGN\n");
 211         if (symbol_prefix_char)
 212                 printf("%c%s:\n", symbol_prefix_char, label);
 213         else
 214                 printf("%s:\n", label);
 215 }
 216
 217 /* uncompress a compressed symbol. When this function is called, the best table
 218  * might still be compressed itself, so the function needs to be recursive */
 219 static int expand_symbol(unsigned char *data, int len, char *result)
 220 {
 221         int c, rlen, total=0;
 222
 223         while (len) {
 224                 c = *data;
 225                 /* if the table holds a single char that is the same as the one
 226                  * we are looking for, then end the search */
 227                 if (best_table[c][0]==c && best_table_len[c]==1) {
 228                         *result++ = c;
 229                         total++;
 230                 } else {
 231                         /* if not, recurse and expand */
 232                         rlen = expand_symbol(best_table[c], best_table_len[c], result);
 233                         total += rlen;
 234                         result += rlen;
 235                 }
 236                 data++;
 237                 len--;
 238         }
 239         *result=0;
 240
 241         return total;
 242 }
 243
 244 static void write_src(void)
 245 {
 246         unsigned int i, k, off;
 247         unsigned int best_idx[256];
 248         unsigned int *markers;
 249         char buf[KSYM_NAME_LEN];
 250
 251         printf("#include <asm/types.h>\n");
 252         printf("#if BITS_PER_LONG == 64\n");
 253         printf("#define PTR .quad\n");
 254         printf("#define ALGN .align 8\n");
 255         printf("#else\n");
 256         printf("#define PTR .long\n");
 257         printf("#define ALGN .align 4\n");
 258         printf("#endif\n");
 259
 260         printf("\t.section .rodata, \"a\"\n");
 261
 262         /* Provide proper symbols relocatability by their '_text'
 263          * relativeness.  The symbol names cannot be used to construct
 264          * normal symbol references as the list of symbols contains
 265          * symbols that are declared static and are private to their
 266          * .o files.  This prevents .tmp_kallsyms.o or any other
 267          * object from referencing them.
 268          */
 269         output_label("kallsyms_addresses");
 270         for (i = 0; i < table_cnt; i++) {
 271                 if (toupper(table[i].sym[0]) != 'A') {
 272                         if (_text <= table[i].addr)
 273                                 printf("\tPTR\t_text + %#llx\n",
 274                                         table[i].addr - _text);
 275                         else
 276                                 printf("\tPTR\t_text - %#llx\n",
 277                                         _text - table[i].addr);
 278                 } else {
 279                         printf("\tPTR\t%#llx\n", table[i].addr);
 280                 }
 281         }
 282         printf("\n");
 283
 284         output_label("kallsyms_num_syms");
 285         printf("\tPTR\t%d\n", table_cnt);
 286         printf("\n");
 287
 288         /* table of offset markers, that give the offset in the compressed stream
 289          * every 256 symbols */
 290         markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
 291         if (!markers) {
 292                 fprintf(stderr, "kallsyms failure: "
 293                         "unable to allocate required memory\n");
 294                 exit(EXIT_FAILURE);
 295         }
 296
 297         output_label("kallsyms_names");
 298         off = 0;
 299         for (i = 0; i < table_cnt; i++) {
 300                 if ((i & 0xFF) == 0)
 301                         markers[i >> 8] = off;
 302
 303                 printf("\t.byte 0x%02x", table[i].len);
 304                 for (k = 0; k < table[i].len; k++)
 305                         printf(", 0x%02x", table[i].sym[k]);
 306                 printf("\n");
 307
 308                 off += table[i].len + 1;
 309         }
 310         printf("\n");
 311
 312         output_label("kallsyms_markers");
 313         for (i = 0; i < ((table_cnt + 255) >> 8); i++)
 314                 printf("\tPTR\t%d\n", markers[i]);
 315         printf("\n");
 316
 317         free(markers);
 318
 319         output_label("kallsyms_token_table");
 320         off = 0;
 321         for (i = 0; i < 256; i++) {
 322                 best_idx[i] = off;
 323                 expand_symbol(best_table[i], best_table_len[i], buf);
 324                 printf("\t.asciz\t\"%s\"\n", buf);
 325                 off += strlen(buf) + 1;
 326         }
 327         printf("\n");
 328
 329         output_label("kallsyms_token_index");
 330         for (i = 0; i < 256; i++)
 331                 printf("\t.short\t%d\n", best_idx[i]);
 332         printf("\n");
 333 }
 334
 335
 336 /* table lookup compression functions */
 337
 338 /* count all the possible tokens in a symbol */
 339 static void learn_symbol(unsigned char *symbol, int len)
 340 {
 341         int i;
 342
 343         for (i = 0; i < len - 1; i++)
 344                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
 345 }
 346
 347 /* decrease the count for all the possible tokens in a symbol */
 348 static void forget_symbol(unsigned char *symbol, int len)
 349 {
 350         int i;
 351
 352         for (i = 0; i < len - 1; i++)
 353                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
 354 }
 355
 356 /* remove all the invalid symbols from the table and do the initial token count */
 357 static void build_initial_tok_table(void)
 358 {
 359         unsigned int i, pos;
 360
 361         pos = 0;
 362         for (i = 0; i < table_cnt; i++) {
 363                 if ( symbol_valid(&table[i]) ) {
 364                         if (pos != i)
 365                                 table[pos] = table[i];
 366                         learn_symbol(table[pos].sym, table[pos].len);
 367                         pos++;
 368                 }
 369         }
 370         table_cnt = pos;
 371 }
 372
 373 static void *find_token(unsigned char *str, int len, unsigned char *token)
 374 {
 375         int i;
 376
 377         for (i = 0; i < len - 1; i++) {
 378                 if (str[i] == token[0] && str[i+1] == token[1])
 379                         return &str[i];
 380         }
 381         return NULL;
 382 }
 383
 384 /* replace a given token in all the valid symbols. Use the sampled symbols
 385  * to update the counts */
 386 static void compress_symbols(unsigned char *str, int idx)
 387 {
 388         unsigned int i, len, size;
 389         unsigned char *p1, *p2;
 390
 391         for (i = 0; i < table_cnt; i++) {
 392
 393                 len = table[i].len;
 394                 p1 = table[i].sym;
 395
 396                 /* find the token on the symbol */
 397                 p2 = find_token(p1, len, str);
 398                 if (!p2) continue;
 399
 400                 /* decrease the counts for this symbol's tokens */
 401                 forget_symbol(table[i].sym, len);
 402
 403                 size = len;
 404
 405                 do {
 406                         *p2 = idx;
 407                         p2++;
 408                         size -= (p2 - p1);
 409                         memmove(p2, p2 + 1, size);
 410                         p1 = p2;
 411                         len--;
 412
 413                         if (size < 2) break;
 414
 415                         /* find the token on the symbol */
 416                         p2 = find_token(p1, size, str);
 417
 418                 } while (p2);
 419
 420                 table[i].len = len;
 421
 422                 /* increase the counts for this symbol's new tokens */
 423                 learn_symbol(table[i].sym, len);
 424         }
 425 }
 426
 427 /* search the token with the maximum profit */
 428 static int find_best_token(void)
 429 {
 430         int i, best, bestprofit;
 431
 432         bestprofit=-10000;
 433         best = 0;
 434
 435         for (i = 0; i < 0x10000; i++) {
 436                 if (token_profit[i] > bestprofit) {
 437                         best = i;
 438                         bestprofit = token_profit[i];
 439                 }
 440         }
 441         return best;
 442 }
 443
 444 /* this is the core of the algorithm: calculate the "best" table */
 445 static void optimize_result(void)
 446 {
 447         int i, best;
 448
 449         /* using the '\0' symbol last allows compress_symbols to use standard
 450          * fast string functions */
 451         for (i = 255; i >= 0; i--) {
 452
 453                 /* if this table slot is empty (it is not used by an actual
 454                  * original char code */
 455                 if (!best_table_len[i]) {
 456
 457                         /* find the token with the breates profit value */
 458                         best = find_best_token();
 459
 460                         /* place it in the "best" table */
 461                         best_table_len[i] = 2;
 462                         best_table[i][0] = best & 0xFF;
 463                         best_table[i][1] = (best >> 8) & 0xFF;
 464
 465                         /* replace this token in all the valid symbols */
 466                         compress_symbols(best_table[i], i);
 467                 }
 468         }
 469 }
 470
 471 /* start by placing the symbols that are actually used on the table */
 472 static void insert_real_symbols_in_table(void)
 473 {
 474         unsigned int i, j, c;
 475
 476         memset(best_table, 0, sizeof(best_table));
 477         memset(best_table_len, 0, sizeof(best_table_len));
 478
 479         for (i = 0; i < table_cnt; i++) {
 480                 for (j = 0; j < table[i].len; j++) {
 481                         c = table[i].sym[j];
 482                         best_table[c][0]=c;
 483                         best_table_len[c]=1;
 484                 }
 485         }
 486 }
 487
 488 static void optimize_token_table(void)
 489 {
 490         build_initial_tok_table();
 491
 492         insert_real_symbols_in_table();
 493
 494         /* When valid symbol is not registered, exit to error */
 495         if (!table_cnt) {
 496                 fprintf(stderr, "No valid symbol.\n");
 497                 exit(1);
 498         }
 499
 500         optimize_result();
 501 }
 502
 503 /* guess for "linker script provide" symbol */
 504 static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
 505 {
 506         const char *symbol = (char *)se->sym + 1;
 507         int len = se->len - 1;
 508
 509         if (len < 8)
 510                 return 0;
 511
 512         if (symbol[0] != '_' || symbol[1] != '_')
 513                 return 0;
 514
 515         /* __start_XXXXX */
 516         if (!memcmp(symbol + 2, "start_", 6))
 517                 return 1;
 518
 519         /* __stop_XXXXX */
 520         if (!memcmp(symbol + 2, "stop_", 5))
 521                 return 1;
 522
 523         /* __end_XXXXX */
 524         if (!memcmp(symbol + 2, "end_", 4))
 525                 return 1;
 526
 527         /* __XXXXX_start */
 528         if (!memcmp(symbol + len - 6, "_start", 6))
 529                 return 1;
 530
 531         /* __XXXXX_end */
 532         if (!memcmp(symbol + len - 4, "_end", 4))
 533                 return 1;
 534
 535         return 0;
 536 }
 537
 538 static int prefix_underscores_count(const char *str)
 539 {
 540         const char *tail = str;
 541
 542         while (*tail != '_')
 543                 tail++;
 544
 545         return tail - str;
 546 }
 547
 548 static int compare_symbols(const void *a, const void *b)
 549 {
 550         const struct sym_entry *sa;
 551         const struct sym_entry *sb;
 552         int wa, wb;
 553
 554         sa = a;
 555         sb = b;
 556
 557         /* sort by address first */
 558         if (sa->addr > sb->addr)
 559                 return 1;
 560         if (sa->addr < sb->addr)
 561                 return -1;
 562
 563         /* sort by "weakness" type */
 564         wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
 565         wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
 566         if (wa != wb)
 567                 return wa - wb;
 568
 569         /* sort by "linker script provide" type */
 570         wa = may_be_linker_script_provide_symbol(sa);
 571         wb = may_be_linker_script_provide_symbol(sb);
 572         if (wa != wb)
 573                 return wa - wb;
 574
 575         /* sort by the number of prefix underscores */
 576         wa = prefix_underscores_count((const char *)sa->sym + 1);
 577         wb = prefix_underscores_count((const char *)sb->sym + 1);
 578         if (wa != wb)
 579                 return wa - wb;
 580
 581         /* sort by initial order, so that other symbols are left undisturbed */
 582         return sa->start_pos - sb->start_pos;
 583 }
 584
 585 static void sort_symbols(void)
 586 {
 587         qsort(table, table_cnt, sizeof(struct sym_entry), compare_symbols);
 588 }
 589
 590 int main(int argc, char **argv)
 591 {
 592         if (argc >= 2) {
 593                 int i;
 594                 for (i = 1; i < argc; i++) {
 595                         if(strcmp(argv[i], "--all-symbols") == 0)
 596                                 all_symbols = 1;
 597                         else if (strncmp(argv[i], "--symbol-prefix=", 16) == 0) {
 598                                 char *p = &argv[i][16];
 599                                 /* skip quote */
 600                                 if ((*p == '"' && *(p+2) == '"') || (*p == '\'' && *(p+2) == '\''))
 601                                         p++;
 602                                 symbol_prefix_char = *p;
 603                         } else
 604                                 usage();
 605                 }
 606         } else if (argc != 1)
 607                 usage();
 608
 609         read_map(stdin);
 610         sort_symbols();
 611         optimize_token_table();
 612         write_src();
 613
 614         return 0;
 615 }