home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2009 February / PCWFEB09.iso / Software / Linux / Kubuntu 8.10 / kubuntu-8.10-desktop-i386.iso / casper / filesystem.squashfs / usr / src / linux-headers-2.6.27-7 / scripts / kallsyms.c < prev    next >
Encoding:
C/C++ Source or Header  |  2008-10-09  |  13.2 KB  |  559 lines

  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. static int compare_symbols(const void *a, const void *b)
  504. {
  505.     const struct sym_entry *sa;
  506.     const struct sym_entry *sb;
  507.     int wa, wb;
  508.  
  509.     sa = a;
  510.     sb = b;
  511.  
  512.     /* sort by address first */
  513.     if (sa->addr > sb->addr)
  514.         return 1;
  515.     if (sa->addr < sb->addr)
  516.         return -1;
  517.  
  518.     /* sort by "weakness" type */
  519.     wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
  520.     wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
  521.     if (wa != wb)
  522.         return wa - wb;
  523.  
  524.     /* sort by initial order, so that other symbols are left undisturbed */
  525.     return sa->start_pos - sb->start_pos;
  526. }
  527.  
  528. static void sort_symbols(void)
  529. {
  530.     qsort(table, table_cnt, sizeof(struct sym_entry), compare_symbols);
  531. }
  532.  
  533. int main(int argc, char **argv)
  534. {
  535.     if (argc >= 2) {
  536.         int i;
  537.         for (i = 1; i < argc; i++) {
  538.             if(strcmp(argv[i], "--all-symbols") == 0)
  539.                 all_symbols = 1;
  540.             else if (strncmp(argv[i], "--symbol-prefix=", 16) == 0) {
  541.                 char *p = &argv[i][16];
  542.                 /* skip quote */
  543.                 if ((*p == '"' && *(p+2) == '"') || (*p == '\'' && *(p+2) == '\''))
  544.                     p++;
  545.                 symbol_prefix_char = *p;
  546.             } else
  547.                 usage();
  548.         }
  549.     } else if (argc != 1)
  550.         usage();
  551.  
  552.     read_map(stdin);
  553.     sort_symbols();
  554.     optimize_token_table();
  555.     write_src();
  556.  
  557.     return 0;
  558. }
  559.