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  * ChangeLog:
  11  *
  12  * (25/Aug/2004) Paulo Marques <pmarques@grupopie.com>
  13  *      Changed the compression method from stem compression to "table lookup"
  14  *      compression
  15  *
  16  *      Table compression uses all the unused char codes on the symbols and
  17  *  maps these to the most used substrings (tokens). For instance, it might
  18  *  map char code 0xF7 to represent "write_" and then in every symbol where
  19  *  "write_" appears it can be replaced by 0xF7, saving 5 bytes.
  20  *      The used codes themselves are also placed in the table so that the
  21  *  decompresion can work without "special cases".
  22  *      Applied to kernel symbols, this usually produces a compression ratio
  23  *  of about 50%.
  24  *
  25  */
  26
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <ctype.h>
  31
  32 /* maximum token length used. It doesn't pay to increase it a lot, because
  33  * very long substrings probably don't repeat themselves too often. */
  34 #define MAX_TOK_SIZE            11
  35 #define KSYM_NAME_LEN           127
  36
  37 /* we use only a subset of the complete symbol table to gather the token count,
  38  * to speed up compression, at the expense of a little compression ratio */
  39 #define WORKING_SET             1024
  40
  41 /* first find the best token only on the list of tokens that would profit more
  42  * than GOOD_BAD_THRESHOLD. Only if this list is empty go to the "bad" list.
  43  * Increasing this value will put less tokens on the "good" list, so the search
  44  * is faster. However, if the good list runs out of tokens, we must painfully
  45  * search the bad list. */
  46 #define GOOD_BAD_THRESHOLD      10
  47
  48 /* token hash parameters */
  49 #define HASH_BITS               18
  50 #define HASH_TABLE_SIZE         (1 << HASH_BITS)
  51 #define HASH_MASK               (HASH_TABLE_SIZE - 1)
  52 #define HASH_BASE_OFFSET        2166136261U
  53 #define HASH_FOLD(a)            ((a)&(HASH_MASK))
  54
  55 /* flags to mark symbols */
  56 #define SYM_FLAG_VALID          1
  57 #define SYM_FLAG_SAMPLED        2
  58
  59 struct sym_entry {
  60         unsigned long long addr;
  61         char type;
  62         unsigned char flags;
  63         unsigned char len;
  64         unsigned char *sym;
  65 };
  66
  67
  68 static struct sym_entry *table;
  69 static int size, cnt;
  70 static unsigned long long _stext, _etext, _sinittext, _einittext;
  71 static int all_symbols = 0;
  72
  73 struct token {
  74         unsigned char data[MAX_TOK_SIZE];
  75         unsigned char len;
  76         /* profit: the number of bytes that could be saved by inserting this
  77          * token into the table */
  78         int profit;
  79         struct token *next;     /* next token on the hash list */
  80         struct token *right;    /* next token on the good/bad list */
  81         struct token *left;    /* previous token on the good/bad list */
  82         struct token *smaller; /* token that is less one letter than this one */
  83         };
  84
  85 struct token bad_head, good_head;
  86 struct token *hash_table[HASH_TABLE_SIZE];
  87
  88 /* the table that holds the result of the compression */
  89 unsigned char best_table[256][MAX_TOK_SIZE+1];
  90 unsigned char best_table_len[256];
  91
  92
  93 static void
  94 usage(void)
  95 {
  96         fprintf(stderr, "Usage: kallsyms [--all-symbols] < in.map > out.S\n");
  97         exit(1);
  98 }
  99
 100 /*
 101  * This ignores the intensely annoying "mapping symbols" found
 102  * in ARM ELF files: $a, $t and $d.
 103  */
 104 static inline int
 105 is_arm_mapping_symbol(const char *str)
 106 {
 107         return str[0] == '$' && strchr("atd", str[1])
 108                && (str[2] == '\0' || str[2] == '.');
 109 }
 110
 111 static int
 112 read_symbol(FILE *in, struct sym_entry *s)
 113 {
 114         char str[500];
 115         int rc;
 116
 117         rc = fscanf(in, "%llx %c %499s\n", &s->addr, &s->type, str);
 118         if (rc != 3) {
 119                 if (rc != EOF) {
 120                         /* skip line */
 121                         fgets(str, 500, in);
 122                 }
 123                 return -1;
 124         }
 125
 126         /* Ignore most absolute/undefined (?) symbols. */
 127         if (strcmp(str, "_stext") == 0)
 128                 _stext = s->addr;
 129         else if (strcmp(str, "_etext") == 0)
 130                 _etext = s->addr;
 131         else if (strcmp(str, "_sinittext") == 0)
 132                 _sinittext = s->addr;
 133         else if (strcmp(str, "_einittext") == 0)
 134                 _einittext = s->addr;
 135         else if (toupper(s->type) == 'A')
 136         {
 137                 /* Keep these useful absolute symbols */
 138                 if (strcmp(str, "__kernel_syscall_via_break") &&
 139                     strcmp(str, "__kernel_syscall_via_epc") &&
 140                     strcmp(str, "__kernel_sigtramp") &&
 141                     strcmp(str, "__gp"))
 142                         return -1;
 143
 144         }
 145         else if (toupper(s->type) == 'U' ||
 146                  is_arm_mapping_symbol(str))
 147                 return -1;
 148
 149         /* include the type field in the symbol name, so that it gets
 150          * compressed together */
 151         s->len = strlen(str) + 1;
 152         s->sym = (char *) malloc(s->len + 1);
 153         strcpy(s->sym + 1, str);
 154         s->sym[0] = s->type;
 155
 156         return 0;
 157 }
 158
 159 static int
 160 symbol_valid(struct sym_entry *s)
 161 {
 162         /* Symbols which vary between passes.  Passes 1 and 2 must have
 163          * identical symbol lists.  The kallsyms_* symbols below are only added
 164          * after pass 1, they would be included in pass 2 when --all-symbols is
 165          * specified so exclude them to get a stable symbol list.
 166          */
 167         static char *special_symbols[] = {
 168                 "kallsyms_addresses",
 169                 "kallsyms_num_syms",
 170                 "kallsyms_names",
 171                 "kallsyms_markers",
 172                 "kallsyms_token_table",
 173                 "kallsyms_token_index",
 174
 175         /* Exclude linker generated symbols which vary between passes */
 176                 "_SDA_BASE_",           /* ppc */
 177                 "_SDA2_BASE_",          /* ppc */
 178                 NULL };
 179         int i;
 180
 181         /* if --all-symbols is not specified, then symbols outside the text
 182          * and inittext sections are discarded */
 183         if (!all_symbols) {
 184                 if ((s->addr < _stext || s->addr > _etext)
 185                     && (s->addr < _sinittext || s->addr > _einittext))
 186                         return 0;
 187         }
 188
 189         /* Exclude symbols which vary between passes. */
 190         if (strstr(s->sym + 1, "_compiled."))
 191                 return 0;
 192
 193         for (i = 0; special_symbols[i]; i++)
 194                 if( strcmp(s->sym + 1, special_symbols[i]) == 0 )
 195                         return 0;
 196
 197         return 1;
 198 }
 199
 200 static void
 201 read_map(FILE *in)
 202 {
 203         while (!feof(in)) {
 204                 if (cnt >= size) {
 205                         size += 10000;
 206                         table = realloc(table, sizeof(*table) * size);
 207                         if (!table) {
 208                                 fprintf(stderr, "out of memory\n");
 209                                 exit (1);
 210                         }
 211                 }
 212                 if (read_symbol(in, &table[cnt]) == 0)
 213                         cnt++;
 214         }
 215 }
 216
 217 static void output_label(char *label)
 218 {
 219         printf(".globl %s\n",label);
 220         printf("\tALGN\n");
 221         printf("%s:\n",label);
 222 }
 223
 224 /* uncompress a compressed symbol. When this function is called, the best table
 225  * might still be compressed itself, so the function needs to be recursive */
 226 static int expand_symbol(unsigned char *data, int len, char *result)
 227 {
 228         int c, rlen, total=0;
 229
 230         while (len) {
 231                 c = *data;
 232                 /* if the table holds a single char that is the same as the one
 233                  * we are looking for, then end the search */
 234                 if (best_table[c][0]==c && best_table_len[c]==1) {
 235                         *result++ = c;
 236                         total++;
 237                 } else {
 238                         /* if not, recurse and expand */
 239                         rlen = expand_symbol(best_table[c], best_table_len[c], result);
 240                         total += rlen;
 241                         result += rlen;
 242                 }
 243                 data++;
 244                 len--;
 245         }
 246         *result=0;
 247
 248         return total;
 249 }
 250
 251 static void
 252 write_src(void)
 253 {
 254         int i, k, off, valid;
 255         unsigned int best_idx[256];
 256         unsigned int *markers;
 257         char buf[KSYM_NAME_LEN+1];
 258
 259         printf("#include <asm/types.h>\n");
 260         printf("#if BITS_PER_LONG == 64\n");
 261         printf("#define PTR .quad\n");
 262         printf("#define ALGN .align 8\n");
 263         printf("#else\n");
 264         printf("#define PTR .long\n");
 265         printf("#define ALGN .align 4\n");
 266         printf("#endif\n");
 267
 268         printf(".data\n");
 269
 270         output_label("kallsyms_addresses");
 271         valid = 0;
 272         for (i = 0; i < cnt; i++) {
 273                 if (table[i].flags & SYM_FLAG_VALID) {
 274                         printf("\tPTR\t%#llx\n", table[i].addr);
 275                         valid++;
 276                 }
 277         }
 278         printf("\n");
 279
 280         output_label("kallsyms_num_syms");
 281         printf("\tPTR\t%d\n", valid);
 282         printf("\n");
 283
 284         /* table of offset markers, that give the offset in the compressed stream
 285          * every 256 symbols */
 286         markers = (unsigned int *) malloc(sizeof(unsigned int)*((valid + 255) / 256));
 287
 288         output_label("kallsyms_names");
 289         valid = 0;
 290         off = 0;
 291         for (i = 0; i < cnt; i++) {
 292
 293                 if (!table[i].flags & SYM_FLAG_VALID)
 294                         continue;
 295
 296                 if ((valid & 0xFF) == 0)
 297                         markers[valid >> 8] = off;
 298
 299                 printf("\t.byte 0x%02x", table[i].len);
 300                 for (k = 0; k < table[i].len; k++)
 301                         printf(", 0x%02x", table[i].sym[k]);
 302                 printf("\n");
 303
 304                 off += table[i].len + 1;
 305                 valid++;
 306         }
 307         printf("\n");
 308
 309         output_label("kallsyms_markers");
 310         for (i = 0; i < ((valid + 255) >> 8); i++)
 311                 printf("\tPTR\t%d\n", markers[i]);
 312         printf("\n");
 313
 314         free(markers);
 315
 316         output_label("kallsyms_token_table");
 317         off = 0;
 318         for (i = 0; i < 256; i++) {
 319                 best_idx[i] = off;
 320                 expand_symbol(best_table[i],best_table_len[i],buf);
 321                 printf("\t.asciz\t\"%s\"\n", buf);
 322                 off += strlen(buf) + 1;
 323         }
 324         printf("\n");
 325
 326         output_label("kallsyms_token_index");
 327         for (i = 0; i < 256; i++)
 328                 printf("\t.short\t%d\n", best_idx[i]);
 329         printf("\n");
 330 }
 331
 332
 333 /* table lookup compression functions */
 334
 335 static inline unsigned int rehash_token(unsigned int hash, unsigned char data)
 336 {
 337         return ((hash * 16777619) ^ data);
 338 }
 339
 340 static unsigned int hash_token(unsigned char *data, int len)
 341 {
 342         unsigned int hash=HASH_BASE_OFFSET;
 343         int i;
 344
 345         for (i = 0; i < len; i++)
 346                 hash = rehash_token(hash, data[i]);
 347
 348         return HASH_FOLD(hash);
 349 }
 350
 351 /* find a token given its data and hash value */
 352 static struct token *find_token_hash(unsigned char *data, int len, unsigned int hash)
 353 {
 354         struct token *ptr;
 355
 356         ptr = hash_table[hash];
 357
 358         while (ptr) {
 359                 if ((ptr->len == len) && (memcmp(ptr->data, data, len) == 0))
 360                         return ptr;
 361                 ptr=ptr->next;
 362         }
 363
 364         return NULL;
 365 }
 366
 367 static inline void insert_token_in_group(struct token *head, struct token *ptr)
 368 {
 369         ptr->right = head->right;
 370         ptr->right->left = ptr;
 371         head->right = ptr;
 372         ptr->left = head;
 373 }
 374
 375 static inline void remove_token_from_group(struct token *ptr)
 376 {
 377         ptr->left->right = ptr->right;
 378         ptr->right->left = ptr->left;
 379 }
 380
 381
 382 /* build the counts for all the tokens that start with "data", and have lenghts
 383  * from 2 to "len" */
 384 static void learn_token(unsigned char *data, int len)
 385 {
 386         struct token *ptr,*last_ptr;
 387         int i, newprofit;
 388         unsigned int hash = HASH_BASE_OFFSET;
 389         unsigned int hashes[MAX_TOK_SIZE + 1];
 390
 391         if (len > MAX_TOK_SIZE)
 392                 len = MAX_TOK_SIZE;
 393
 394         /* calculate and store the hash values for all the sub-tokens */
 395         hash = rehash_token(hash, data[0]);
 396         for (i = 2; i <= len; i++) {
 397                 hash = rehash_token(hash, data[i-1]);
 398                 hashes[i] = HASH_FOLD(hash);
 399         }
 400
 401         last_ptr = NULL;
 402         ptr = NULL;
 403
 404         for (i = len; i >= 2; i--) {
 405                 hash = hashes[i];
 406
 407                 if (!ptr) ptr = find_token_hash(data, i, hash);
 408
 409                 if (!ptr) {
 410                         /* create a new token entry */
 411                         ptr = (struct token *) malloc(sizeof(*ptr));
 412
 413                         memcpy(ptr->data, data, i);
 414                         ptr->len = i;
 415
 416                         /* when we create an entry, it's profit is 0 because
 417                          * we also take into account the size of the token on
 418                          * the compressed table. We then subtract GOOD_BAD_THRESHOLD
 419                          * so that the test to see if this token belongs to
 420                          * the good or bad list, is a comparison to zero */
 421                         ptr->profit = -GOOD_BAD_THRESHOLD;
 422
 423                         ptr->next = hash_table[hash];
 424                         hash_table[hash] = ptr;
 425
 426                         insert_token_in_group(&bad_head, ptr);
 427
 428                         ptr->smaller = NULL;
 429                 } else {
 430                         newprofit = ptr->profit + (ptr->len - 1);
 431                         /* check to see if this token needs to be moved to a
 432                          * different list */
 433                         if((ptr->profit < 0) && (newprofit >= 0)) {
 434                                 remove_token_from_group(ptr);
 435                                 insert_token_in_group(&good_head,ptr);
 436                         }
 437                         ptr->profit = newprofit;
 438                 }
 439
 440                 if (last_ptr) last_ptr->smaller = ptr;
 441                 last_ptr = ptr;
 442
 443                 ptr = ptr->smaller;
 444         }
 445 }
 446
 447 /* decrease the counts for all the tokens that start with "data", and have lenghts
 448  * from 2 to "len". This function is much simpler than learn_token because we have
 449  * more guarantees (tho tokens exist, the ->smaller pointer is set, etc.)
 450  * The two separate functions exist only because of compression performance */
 451 static void forget_token(unsigned char *data, int len)
 452 {
 453         struct token *ptr;
 454         int i, newprofit;
 455         unsigned int hash=0;
 456
 457         if (len > MAX_TOK_SIZE) len = MAX_TOK_SIZE;
 458
 459         hash = hash_token(data, len);
 460         ptr = find_token_hash(data, len, hash);
 461
 462         for (i = len; i >= 2; i--) {
 463
 464                 newprofit = ptr->profit - (ptr->len - 1);
 465                 if ((ptr->profit >= 0) && (newprofit < 0)) {
 466                         remove_token_from_group(ptr);
 467                         insert_token_in_group(&bad_head, ptr);
 468                 }
 469                 ptr->profit=newprofit;
 470
 471                 ptr=ptr->smaller;
 472         }
 473 }
 474
 475 /* count all the possible tokens in a symbol */
 476 static void learn_symbol(unsigned char *symbol, int len)
 477 {
 478         int i;
 479
 480         for (i = 0; i < len - 1; i++)
 481                 learn_token(symbol + i, len - i);
 482 }
 483
 484 /* decrease the count for all the possible tokens in a symbol */
 485 static void forget_symbol(unsigned char *symbol, int len)
 486 {
 487         int i;
 488
 489         for (i = 0; i < len - 1; i++)
 490                 forget_token(symbol + i, len - i);
 491 }
 492
 493 /* set all the symbol flags and do the initial token count */
 494 static void build_initial_tok_table(void)
 495 {
 496         int i, use_it, valid;
 497
 498         valid = 0;
 499         for (i = 0; i < cnt; i++) {
 500                 table[i].flags = 0;
 501                 if ( symbol_valid(&table[i]) ) {
 502                         table[i].flags |= SYM_FLAG_VALID;
 503                         valid++;
 504                 }
 505         }
 506
 507         use_it = 0;
 508         for (i = 0; i < cnt; i++) {
 509
 510                 /* subsample the available symbols. This method is almost like
 511                  * a Bresenham's algorithm to get uniformly distributed samples
 512                  * across the symbol table */
 513                 if (table[i].flags & SYM_FLAG_VALID) {
 514
 515                         use_it += WORKING_SET;
 516
 517                         if (use_it >= valid) {
 518                                 table[i].flags |= SYM_FLAG_SAMPLED;
 519                                 use_it -= valid;
 520                         }
 521                 }
 522                 if (table[i].flags & SYM_FLAG_SAMPLED)
 523                         learn_symbol(table[i].sym, table[i].len);
 524         }
 525 }
 526
 527 /* replace a given token in all the valid symbols. Use the sampled symbols
 528  * to update the counts */
 529 static void compress_symbols(unsigned char *str, int tlen, int idx)
 530 {
 531         int i, len, learn, size;
 532         unsigned char *p;
 533
 534         for (i = 0; i < cnt; i++) {
 535
 536                 if (!(table[i].flags & SYM_FLAG_VALID)) continue;
 537
 538                 len = table[i].len;
 539                 learn = 0;
 540                 p = table[i].sym;
 541
 542                 do {
 543                         /* find the token on the symbol */
 544                         p = (unsigned char *) strstr((char *) p, (char *) str);
 545                         if (!p) break;
 546
 547                         if (!learn) {
 548                                 /* if this symbol was used to count, decrease it */
 549                                 if (table[i].flags & SYM_FLAG_SAMPLED)
 550                                         forget_symbol(table[i].sym, len);
 551                                 learn = 1;
 552                         }
 553
 554                         *p = idx;
 555                         size = (len - (p - table[i].sym)) - tlen + 1;
 556                         memmove(p + 1, p + tlen, size);
 557                         p++;
 558                         len -= tlen - 1;
 559
 560                 } while (size >= tlen);
 561
 562                 if(learn) {
 563                         table[i].len = len;
 564                         /* if this symbol was used to count, learn it again */
 565                         if(table[i].flags & SYM_FLAG_SAMPLED)
 566                                 learn_symbol(table[i].sym, len);
 567                 }
 568         }
 569 }
 570
 571 /* search the token with the maximum profit */
 572 static struct token *find_best_token(void)
 573 {
 574         struct token *ptr,*best,*head;
 575         int bestprofit;
 576
 577         bestprofit=-10000;
 578
 579         /* failsafe: if the "good" list is empty search from the "bad" list */
 580         if(good_head.right == &good_head) head = &bad_head;
 581         else head = &good_head;
 582
 583         ptr = head->right;
 584         best = NULL;
 585         while (ptr != head) {
 586                 if (ptr->profit > bestprofit) {
 587                         bestprofit = ptr->profit;
 588                         best = ptr;
 589                 }
 590                 ptr = ptr->right;
 591         }
 592
 593         return best;
 594 }
 595
 596 /* this is the core of the algorithm: calculate the "best" table */
 597 static void optimize_result(void)
 598 {
 599         struct token *best;
 600         int i;
 601
 602         /* using the '\0' symbol last allows compress_symbols to use standard
 603          * fast string functions */
 604         for (i = 255; i >= 0; i--) {
 605
 606                 /* if this table slot is empty (it is not used by an actual
 607                  * original char code */
 608                 if (!best_table_len[i]) {
 609
 610                         /* find the token with the breates profit value */
 611                         best = find_best_token();
 612
 613                         /* place it in the "best" table */
 614                         best_table_len[i] = best->len;
 615                         memcpy(best_table[i], best->data, best_table_len[i]);
 616                         /* zero terminate the token so that we can use strstr
 617                            in compress_symbols */
 618                         best_table[i][best_table_len[i]]='\0';
 619
 620                         /* replace this token in all the valid symbols */
 621                         compress_symbols(best_table[i], best_table_len[i], i);
 622                 }
 623         }
 624 }
 625
 626 /* start by placing the symbols that are actually used on the table */
 627 static void insert_real_symbols_in_table(void)
 628 {
 629         int i, j, c;
 630
 631         memset(best_table, 0, sizeof(best_table));
 632         memset(best_table_len, 0, sizeof(best_table_len));
 633
 634         for (i = 0; i < cnt; i++) {
 635                 if (table[i].flags & SYM_FLAG_VALID) {
 636                         for (j = 0; j < table[i].len; j++) {
 637                                 c = table[i].sym[j];
 638                                 best_table[c][0]=c;
 639                                 best_table_len[c]=1;
 640                         }
 641                 }
 642         }
 643 }
 644
 645 static void optimize_token_table(void)
 646 {
 647         memset(hash_table, 0, sizeof(hash_table));
 648
 649         good_head.left = &good_head;
 650         good_head.right = &good_head;
 651
 652         bad_head.left = &bad_head;
 653         bad_head.right = &bad_head;
 654
 655         build_initial_tok_table();
 656
 657         insert_real_symbols_in_table();
 658
 659         optimize_result();
 660 }
 661
 662
 663 int
 664 main(int argc, char **argv)
 665 {
 666         if (argc == 2 && strcmp(argv[1], "--all-symbols") == 0)
 667                 all_symbols = 1;
 668         else if (argc != 1)
 669                 usage();
 670
 671         read_map(stdin);
 672         optimize_token_table();
 673         write_src();
 674
 675         return 0;
 676 }
 677