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