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: kallsyms [--all-symbols] [--absolute-percpu]
   9  *                         [--lto-clang] in.map > out.S
  10  *
  11  *      Table compression uses all the unused char codes on the symbols and
  12  *  maps these to the most used substrings (tokens). For instance, it might
  13  *  map char code 0xF7 to represent "write_" and then in every symbol where
  14  *  "write_" appears it can be replaced by 0xF7, saving 5 bytes.
  15  *      The used codes themselves are also placed in the table so that the
  16  *  decompresion can work without "special cases".
  17  *      Applied to kernel symbols, this usually produces a compression ratio
  18  *  of about 50%.
  19  *
  20  */
  21
  22 #include <errno.h>
  23 #include <getopt.h>
  24 #include <stdbool.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <ctype.h>
  29 #include <limits.h>
  30
  31 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
  32
  33 #define KSYM_NAME_LEN           512
  34
  35 struct sym_entry {
  36         unsigned long long addr;
  37         unsigned int len;
  38         unsigned int seq;
  39         unsigned int start_pos;
  40         unsigned int percpu_absolute;
  41         unsigned char sym[];
  42 };
  43
  44 struct addr_range {
  45         const char *start_sym, *end_sym;
  46         unsigned long long start, end;
  47 };
  48
  49 static unsigned long long _text;
  50 static unsigned long long relative_base;
  51 static struct addr_range text_ranges[] = {
  52         { "_stext",     "_etext"     },
  53         { "_sinittext", "_einittext" },
  54 };
  55 #define text_range_text     (&text_ranges[0])
  56 #define text_range_inittext (&text_ranges[1])
  57
  58 static struct addr_range percpu_range = {
  59         "__per_cpu_start", "__per_cpu_end", -1ULL, 0
  60 };
  61
  62 static struct sym_entry **table;
  63 static unsigned int table_size, table_cnt;
  64 static int all_symbols;
  65 static int absolute_percpu;
  66 static int lto_clang;
  67
  68 static int token_profit[0x10000];
  69
  70 /* the table that holds the result of the compression */
  71 static unsigned char best_table[256][2];
  72 static unsigned char best_table_len[256];
  73
  74
  75 static void usage(void)
  76 {
  77         fprintf(stderr, "Usage: kallsyms [--all-symbols] [--absolute-percpu] "
  78                         "[--lto-clang] in.map > out.S\n");
  79         exit(1);
  80 }
  81
  82 static char *sym_name(const struct sym_entry *s)
  83 {
  84         return (char *)s->sym + 1;
  85 }
  86
  87 static bool is_ignored_symbol(const char *name, char type)
  88 {
  89         if (type == 'u' || type == 'n')
  90                 return true;
  91
  92         if (toupper(type) == 'A') {
  93                 /* Keep these useful absolute symbols */
  94                 if (strcmp(name, "__kernel_syscall_via_break") &&
  95                     strcmp(name, "__kernel_syscall_via_epc") &&
  96                     strcmp(name, "__kernel_sigtramp") &&
  97                     strcmp(name, "__gp"))
  98                         return true;
  99         }
 100
 101         return false;
 102 }
 103
 104 static void check_symbol_range(const char *sym, unsigned long long addr,
 105                                struct addr_range *ranges, int entries)
 106 {
 107         size_t i;
 108         struct addr_range *ar;
 109
 110         for (i = 0; i < entries; ++i) {
 111                 ar = &ranges[i];
 112
 113                 if (strcmp(sym, ar->start_sym) == 0) {
 114                         ar->start = addr;
 115                         return;
 116                 } else if (strcmp(sym, ar->end_sym) == 0) {
 117                         ar->end = addr;
 118                         return;
 119                 }
 120         }
 121 }
 122
 123 static struct sym_entry *read_symbol(FILE *in, char **buf, size_t *buf_len)
 124 {
 125         char *name, type, *p;
 126         unsigned long long addr;
 127         size_t len;
 128         ssize_t readlen;
 129         struct sym_entry *sym;
 130
 131         errno = 0;
 132         readlen = getline(buf, buf_len, in);
 133         if (readlen < 0) {
 134                 if (errno) {
 135                         perror("read_symbol");
 136                         exit(EXIT_FAILURE);
 137                 }
 138                 return NULL;
 139         }
 140
 141         if ((*buf)[readlen - 1] == '\n')
 142                 (*buf)[readlen - 1] = 0;
 143
 144         addr = strtoull(*buf, &p, 16);
 145
 146         if (*buf == p || *p++ != ' ' || !isascii((type = *p++)) || *p++ != ' ') {
 147                 fprintf(stderr, "line format error\n");
 148                 exit(EXIT_FAILURE);
 149         }
 150
 151         name = p;
 152         len = strlen(name);
 153
 154         if (len >= KSYM_NAME_LEN) {
 155                 fprintf(stderr, "Symbol %s too long for kallsyms (%zu >= %d).\n"
 156                                 "Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
 157                         name, len, KSYM_NAME_LEN);
 158                 return NULL;
 159         }
 160
 161         if (strcmp(name, "_text") == 0)
 162                 _text = addr;
 163
 164         /* Ignore most absolute/undefined (?) symbols. */
 165         if (is_ignored_symbol(name, type))
 166                 return NULL;
 167
 168         check_symbol_range(name, addr, text_ranges, ARRAY_SIZE(text_ranges));
 169         check_symbol_range(name, addr, &percpu_range, 1);
 170
 171         /* include the type field in the symbol name, so that it gets
 172          * compressed together */
 173         len++;
 174
 175         sym = malloc(sizeof(*sym) + len + 1);
 176         if (!sym) {
 177                 fprintf(stderr, "kallsyms failure: "
 178                         "unable to allocate required amount of memory\n");
 179                 exit(EXIT_FAILURE);
 180         }
 181         sym->addr = addr;
 182         sym->len = len;
 183         sym->sym[0] = type;
 184         strcpy(sym_name(sym), name);
 185         sym->percpu_absolute = 0;
 186
 187         return sym;
 188 }
 189
 190 static int symbol_in_range(const struct sym_entry *s,
 191                            const struct addr_range *ranges, int entries)
 192 {
 193         size_t i;
 194         const struct addr_range *ar;
 195
 196         for (i = 0; i < entries; ++i) {
 197                 ar = &ranges[i];
 198
 199                 if (s->addr >= ar->start && s->addr <= ar->end)
 200                         return 1;
 201         }
 202
 203         return 0;
 204 }
 205
 206 static bool string_starts_with(const char *s, const char *prefix)
 207 {
 208         return strncmp(s, prefix, strlen(prefix)) == 0;
 209 }
 210
 211 static int symbol_valid(const struct sym_entry *s)
 212 {
 213         const char *name = sym_name(s);
 214
 215         /* if --all-symbols is not specified, then symbols outside the text
 216          * and inittext sections are discarded */
 217         if (!all_symbols) {
 218                 /*
 219                  * Symbols starting with __start and __stop are used to denote
 220                  * section boundaries, and should always be included:
 221                  */
 222                 if (string_starts_with(name, "__start_") ||
 223                     string_starts_with(name, "__stop_"))
 224                         return 1;
 225
 226                 if (symbol_in_range(s, text_ranges,
 227                                     ARRAY_SIZE(text_ranges)) == 0)
 228                         return 0;
 229                 /* Corner case.  Discard any symbols with the same value as
 230                  * _etext _einittext; they can move between pass 1 and 2 when
 231                  * the kallsyms data are added.  If these symbols move then
 232                  * they may get dropped in pass 2, which breaks the kallsyms
 233                  * rules.
 234                  */
 235                 if ((s->addr == text_range_text->end &&
 236                      strcmp(name, text_range_text->end_sym)) ||
 237                     (s->addr == text_range_inittext->end &&
 238                      strcmp(name, text_range_inittext->end_sym)))
 239                         return 0;
 240         }
 241
 242         return 1;
 243 }
 244
 245 /* remove all the invalid symbols from the table */
 246 static void shrink_table(void)
 247 {
 248         unsigned int i, pos;
 249
 250         pos = 0;
 251         for (i = 0; i < table_cnt; i++) {
 252                 if (symbol_valid(table[i])) {
 253                         if (pos != i)
 254                                 table[pos] = table[i];
 255                         pos++;
 256                 } else {
 257                         free(table[i]);
 258                 }
 259         }
 260         table_cnt = pos;
 261 }
 262
 263 static void read_map(const char *in)
 264 {
 265         FILE *fp;
 266         struct sym_entry *sym;
 267         char *buf = NULL;
 268         size_t buflen = 0;
 269
 270         fp = fopen(in, "r");
 271         if (!fp) {
 272                 perror(in);
 273                 exit(1);
 274         }
 275
 276         while (!feof(fp)) {
 277                 sym = read_symbol(fp, &buf, &buflen);
 278                 if (!sym)
 279                         continue;
 280
 281                 sym->start_pos = table_cnt;
 282
 283                 if (table_cnt >= table_size) {
 284                         table_size += 10000;
 285                         table = realloc(table, sizeof(*table) * table_size);
 286                         if (!table) {
 287                                 fprintf(stderr, "out of memory\n");
 288                                 fclose(fp);
 289                                 exit (1);
 290                         }
 291                 }
 292
 293                 table[table_cnt++] = sym;
 294         }
 295
 296         free(buf);
 297         fclose(fp);
 298 }
 299
 300 static void output_label(const char *label)
 301 {
 302         printf(".globl %s\n", label);
 303         printf("\tALGN\n");
 304         printf("%s:\n", label);
 305 }
 306
 307 /* Provide proper symbols relocatability by their '_text' relativeness. */
 308 static void output_address(unsigned long long addr)
 309 {
 310         if (_text <= addr)
 311                 printf("\tPTR\t_text + %#llx\n", addr - _text);
 312         else
 313                 printf("\tPTR\t_text - %#llx\n", _text - addr);
 314 }
 315
 316 /* uncompress a compressed symbol. When this function is called, the best table
 317  * might still be compressed itself, so the function needs to be recursive */
 318 static int expand_symbol(const unsigned char *data, int len, char *result)
 319 {
 320         int c, rlen, total=0;
 321
 322         while (len) {
 323                 c = *data;
 324                 /* if the table holds a single char that is the same as the one
 325                  * we are looking for, then end the search */
 326                 if (best_table[c][0]==c && best_table_len[c]==1) {
 327                         *result++ = c;
 328                         total++;
 329                 } else {
 330                         /* if not, recurse and expand */
 331                         rlen = expand_symbol(best_table[c], best_table_len[c], result);
 332                         total += rlen;
 333                         result += rlen;
 334                 }
 335                 data++;
 336                 len--;
 337         }
 338         *result=0;
 339
 340         return total;
 341 }
 342
 343 static int symbol_absolute(const struct sym_entry *s)
 344 {
 345         return s->percpu_absolute;
 346 }
 347
 348 static void cleanup_symbol_name(char *s)
 349 {
 350         char *p;
 351
 352         /*
 353          * ASCII[.]   = 2e
 354          * ASCII[0-9] = 30,39
 355          * ASCII[A-Z] = 41,5a
 356          * ASCII[_]   = 5f
 357          * ASCII[a-z] = 61,7a
 358          *
 359          * As above, replacing the first '.' in ".llvm." with '\0' does not
 360          * affect the main sorting, but it helps us with subsorting.
 361          */
 362         p = strstr(s, ".llvm.");
 363         if (p)
 364                 *p = '\0';
 365 }
 366
 367 static int compare_names(const void *a, const void *b)
 368 {
 369         int ret;
 370         const struct sym_entry *sa = *(const struct sym_entry **)a;
 371         const struct sym_entry *sb = *(const struct sym_entry **)b;
 372
 373         ret = strcmp(sym_name(sa), sym_name(sb));
 374         if (!ret) {
 375                 if (sa->addr > sb->addr)
 376                         return 1;
 377                 else if (sa->addr < sb->addr)
 378                         return -1;
 379
 380                 /* keep old order */
 381                 return (int)(sa->seq - sb->seq);
 382         }
 383
 384         return ret;
 385 }
 386
 387 static void sort_symbols_by_name(void)
 388 {
 389         qsort(table, table_cnt, sizeof(table[0]), compare_names);
 390 }
 391
 392 static void write_src(void)
 393 {
 394         unsigned int i, k, off;
 395         unsigned int best_idx[256];
 396         unsigned int *markers;
 397         char buf[KSYM_NAME_LEN];
 398
 399         printf("#include <asm/bitsperlong.h>\n");
 400         printf("#if BITS_PER_LONG == 64\n");
 401         printf("#define PTR .quad\n");
 402         printf("#define ALGN .balign 8\n");
 403         printf("#else\n");
 404         printf("#define PTR .long\n");
 405         printf("#define ALGN .balign 4\n");
 406         printf("#endif\n");
 407
 408         printf("\t.section .rodata, \"a\"\n");
 409
 410         output_label("kallsyms_num_syms");
 411         printf("\t.long\t%u\n", table_cnt);
 412         printf("\n");
 413
 414         /* table of offset markers, that give the offset in the compressed stream
 415          * every 256 symbols */
 416         markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
 417         if (!markers) {
 418                 fprintf(stderr, "kallsyms failure: "
 419                         "unable to allocate required memory\n");
 420                 exit(EXIT_FAILURE);
 421         }
 422
 423         output_label("kallsyms_names");
 424         off = 0;
 425         for (i = 0; i < table_cnt; i++) {
 426                 if ((i & 0xFF) == 0)
 427                         markers[i >> 8] = off;
 428                 table[i]->seq = i;
 429
 430                 /* There cannot be any symbol of length zero. */
 431                 if (table[i]->len == 0) {
 432                         fprintf(stderr, "kallsyms failure: "
 433                                 "unexpected zero symbol length\n");
 434                         exit(EXIT_FAILURE);
 435                 }
 436
 437                 /* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
 438                 if (table[i]->len > 0x3FFF) {
 439                         fprintf(stderr, "kallsyms failure: "
 440                                 "unexpected huge symbol length\n");
 441                         exit(EXIT_FAILURE);
 442                 }
 443
 444                 /* Encode length with ULEB128. */
 445                 if (table[i]->len <= 0x7F) {
 446                         /* Most symbols use a single byte for the length. */
 447                         printf("\t.byte 0x%02x", table[i]->len);
 448                         off += table[i]->len + 1;
 449                 } else {
 450                         /* "Big" symbols use two bytes. */
 451                         printf("\t.byte 0x%02x, 0x%02x",
 452                                 (table[i]->len & 0x7F) | 0x80,
 453                                 (table[i]->len >> 7) & 0x7F);
 454                         off += table[i]->len + 2;
 455                 }
 456                 for (k = 0; k < table[i]->len; k++)
 457                         printf(", 0x%02x", table[i]->sym[k]);
 458                 printf("\n");
 459         }
 460         printf("\n");
 461
 462         /*
 463          * Now that we wrote out the compressed symbol names, restore the
 464          * original names, which are needed in some of the later steps.
 465          */
 466         for (i = 0; i < table_cnt; i++) {
 467                 expand_symbol(table[i]->sym, table[i]->len, buf);
 468                 strcpy((char *)table[i]->sym, buf);
 469         }
 470
 471         output_label("kallsyms_markers");
 472         for (i = 0; i < ((table_cnt + 255) >> 8); i++)
 473                 printf("\t.long\t%u\n", markers[i]);
 474         printf("\n");
 475
 476         free(markers);
 477
 478         output_label("kallsyms_token_table");
 479         off = 0;
 480         for (i = 0; i < 256; i++) {
 481                 best_idx[i] = off;
 482                 expand_symbol(best_table[i], best_table_len[i], buf);
 483                 printf("\t.asciz\t\"%s\"\n", buf);
 484                 off += strlen(buf) + 1;
 485         }
 486         printf("\n");
 487
 488         output_label("kallsyms_token_index");
 489         for (i = 0; i < 256; i++)
 490                 printf("\t.short\t%d\n", best_idx[i]);
 491         printf("\n");
 492
 493         output_label("kallsyms_offsets");
 494
 495         for (i = 0; i < table_cnt; i++) {
 496                 /*
 497                  * Use the offset relative to the lowest value
 498                  * encountered of all relative symbols, and emit
 499                  * non-relocatable fixed offsets that will be fixed
 500                  * up at runtime.
 501                  */
 502
 503                 long long offset;
 504                 int overflow;
 505
 506                 if (!absolute_percpu) {
 507                         offset = table[i]->addr - relative_base;
 508                         overflow = (offset < 0 || offset > UINT_MAX);
 509                 } else if (symbol_absolute(table[i])) {
 510                         offset = table[i]->addr;
 511                         overflow = (offset < 0 || offset > INT_MAX);
 512                 } else {
 513                         offset = relative_base - table[i]->addr - 1;
 514                         overflow = (offset < INT_MIN || offset >= 0);
 515                 }
 516                 if (overflow) {
 517                         fprintf(stderr, "kallsyms failure: "
 518                                 "%s symbol value %#llx out of range in relative mode\n",
 519                                 symbol_absolute(table[i]) ? "absolute" : "relative",
 520                                 table[i]->addr);
 521                         exit(EXIT_FAILURE);
 522                 }
 523                 printf("\t.long\t%#x    /* %s */\n", (int)offset, table[i]->sym);
 524         }
 525         printf("\n");
 526
 527         output_label("kallsyms_relative_base");
 528         output_address(relative_base);
 529         printf("\n");
 530
 531         if (lto_clang)
 532                 for (i = 0; i < table_cnt; i++)
 533                         cleanup_symbol_name((char *)table[i]->sym);
 534
 535         sort_symbols_by_name();
 536         output_label("kallsyms_seqs_of_names");
 537         for (i = 0; i < table_cnt; i++)
 538                 printf("\t.byte 0x%02x, 0x%02x, 0x%02x\n",
 539                         (unsigned char)(table[i]->seq >> 16),
 540                         (unsigned char)(table[i]->seq >> 8),
 541                         (unsigned char)(table[i]->seq >> 0));
 542         printf("\n");
 543 }
 544
 545
 546 /* table lookup compression functions */
 547
 548 /* count all the possible tokens in a symbol */
 549 static void learn_symbol(const unsigned char *symbol, int len)
 550 {
 551         int i;
 552
 553         for (i = 0; i < len - 1; i++)
 554                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
 555 }
 556
 557 /* decrease the count for all the possible tokens in a symbol */
 558 static void forget_symbol(const unsigned char *symbol, int len)
 559 {
 560         int i;
 561
 562         for (i = 0; i < len - 1; i++)
 563                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
 564 }
 565
 566 /* do the initial token count */
 567 static void build_initial_token_table(void)
 568 {
 569         unsigned int i;
 570
 571         for (i = 0; i < table_cnt; i++)
 572                 learn_symbol(table[i]->sym, table[i]->len);
 573 }
 574
 575 static unsigned char *find_token(unsigned char *str, int len,
 576                                  const unsigned char *token)
 577 {
 578         int i;
 579
 580         for (i = 0; i < len - 1; i++) {
 581                 if (str[i] == token[0] && str[i+1] == token[1])
 582                         return &str[i];
 583         }
 584         return NULL;
 585 }
 586
 587 /* replace a given token in all the valid symbols. Use the sampled symbols
 588  * to update the counts */
 589 static void compress_symbols(const unsigned char *str, int idx)
 590 {
 591         unsigned int i, len, size;
 592         unsigned char *p1, *p2;
 593
 594         for (i = 0; i < table_cnt; i++) {
 595
 596                 len = table[i]->len;
 597                 p1 = table[i]->sym;
 598
 599                 /* find the token on the symbol */
 600                 p2 = find_token(p1, len, str);
 601                 if (!p2) continue;
 602
 603                 /* decrease the counts for this symbol's tokens */
 604                 forget_symbol(table[i]->sym, len);
 605
 606                 size = len;
 607
 608                 do {
 609                         *p2 = idx;
 610                         p2++;
 611                         size -= (p2 - p1);
 612                         memmove(p2, p2 + 1, size);
 613                         p1 = p2;
 614                         len--;
 615
 616                         if (size < 2) break;
 617
 618                         /* find the token on the symbol */
 619                         p2 = find_token(p1, size, str);
 620
 621                 } while (p2);
 622
 623                 table[i]->len = len;
 624
 625                 /* increase the counts for this symbol's new tokens */
 626                 learn_symbol(table[i]->sym, len);
 627         }
 628 }
 629
 630 /* search the token with the maximum profit */
 631 static int find_best_token(void)
 632 {
 633         int i, best, bestprofit;
 634
 635         bestprofit=-10000;
 636         best = 0;
 637
 638         for (i = 0; i < 0x10000; i++) {
 639                 if (token_profit[i] > bestprofit) {
 640                         best = i;
 641                         bestprofit = token_profit[i];
 642                 }
 643         }
 644         return best;
 645 }
 646
 647 /* this is the core of the algorithm: calculate the "best" table */
 648 static void optimize_result(void)
 649 {
 650         int i, best;
 651
 652         /* using the '\0' symbol last allows compress_symbols to use standard
 653          * fast string functions */
 654         for (i = 255; i >= 0; i--) {
 655
 656                 /* if this table slot is empty (it is not used by an actual
 657                  * original char code */
 658                 if (!best_table_len[i]) {
 659
 660                         /* find the token with the best profit value */
 661                         best = find_best_token();
 662                         if (token_profit[best] == 0)
 663                                 break;
 664
 665                         /* place it in the "best" table */
 666                         best_table_len[i] = 2;
 667                         best_table[i][0] = best & 0xFF;
 668                         best_table[i][1] = (best >> 8) & 0xFF;
 669
 670                         /* replace this token in all the valid symbols */
 671                         compress_symbols(best_table[i], i);
 672                 }
 673         }
 674 }
 675
 676 /* start by placing the symbols that are actually used on the table */
 677 static void insert_real_symbols_in_table(void)
 678 {
 679         unsigned int i, j, c;
 680
 681         for (i = 0; i < table_cnt; i++) {
 682                 for (j = 0; j < table[i]->len; j++) {
 683                         c = table[i]->sym[j];
 684                         best_table[c][0]=c;
 685                         best_table_len[c]=1;
 686                 }
 687         }
 688 }
 689
 690 static void optimize_token_table(void)
 691 {
 692         build_initial_token_table();
 693
 694         insert_real_symbols_in_table();
 695
 696         optimize_result();
 697 }
 698
 699 /* guess for "linker script provide" symbol */
 700 static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
 701 {
 702         const char *symbol = sym_name(se);
 703         int len = se->len - 1;
 704
 705         if (len < 8)
 706                 return 0;
 707
 708         if (symbol[0] != '_' || symbol[1] != '_')
 709                 return 0;
 710
 711         /* __start_XXXXX */
 712         if (!memcmp(symbol + 2, "start_", 6))
 713                 return 1;
 714
 715         /* __stop_XXXXX */
 716         if (!memcmp(symbol + 2, "stop_", 5))
 717                 return 1;
 718
 719         /* __end_XXXXX */
 720         if (!memcmp(symbol + 2, "end_", 4))
 721                 return 1;
 722
 723         /* __XXXXX_start */
 724         if (!memcmp(symbol + len - 6, "_start", 6))
 725                 return 1;
 726
 727         /* __XXXXX_end */
 728         if (!memcmp(symbol + len - 4, "_end", 4))
 729                 return 1;
 730
 731         return 0;
 732 }
 733
 734 static int compare_symbols(const void *a, const void *b)
 735 {
 736         const struct sym_entry *sa = *(const struct sym_entry **)a;
 737         const struct sym_entry *sb = *(const struct sym_entry **)b;
 738         int wa, wb;
 739
 740         /* sort by address first */
 741         if (sa->addr > sb->addr)
 742                 return 1;
 743         if (sa->addr < sb->addr)
 744                 return -1;
 745
 746         /* sort by "weakness" type */
 747         wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
 748         wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
 749         if (wa != wb)
 750                 return wa - wb;
 751
 752         /* sort by "linker script provide" type */
 753         wa = may_be_linker_script_provide_symbol(sa);
 754         wb = may_be_linker_script_provide_symbol(sb);
 755         if (wa != wb)
 756                 return wa - wb;
 757
 758         /* sort by the number of prefix underscores */
 759         wa = strspn(sym_name(sa), "_");
 760         wb = strspn(sym_name(sb), "_");
 761         if (wa != wb)
 762                 return wa - wb;
 763
 764         /* sort by initial order, so that other symbols are left undisturbed */
 765         return sa->start_pos - sb->start_pos;
 766 }
 767
 768 static void sort_symbols(void)
 769 {
 770         qsort(table, table_cnt, sizeof(table[0]), compare_symbols);
 771 }
 772
 773 static void make_percpus_absolute(void)
 774 {
 775         unsigned int i;
 776
 777         for (i = 0; i < table_cnt; i++)
 778                 if (symbol_in_range(table[i], &percpu_range, 1)) {
 779                         /*
 780                          * Keep the 'A' override for percpu symbols to
 781                          * ensure consistent behavior compared to older
 782                          * versions of this tool.
 783                          */
 784                         table[i]->sym[0] = 'A';
 785                         table[i]->percpu_absolute = 1;
 786                 }
 787 }
 788
 789 /* find the minimum non-absolute symbol address */
 790 static void record_relative_base(void)
 791 {
 792         unsigned int i;
 793
 794         for (i = 0; i < table_cnt; i++)
 795                 if (!symbol_absolute(table[i])) {
 796                         /*
 797                          * The table is sorted by address.
 798                          * Take the first non-absolute symbol value.
 799                          */
 800                         relative_base = table[i]->addr;
 801                         return;
 802                 }
 803 }
 804
 805 int main(int argc, char **argv)
 806 {
 807         while (1) {
 808                 static const struct option long_options[] = {
 809                         {"all-symbols",     no_argument, &all_symbols,     1},
 810                         {"absolute-percpu", no_argument, &absolute_percpu, 1},
 811                         {"lto-clang",       no_argument, &lto_clang,       1},
 812                         {},
 813                 };
 814
 815                 int c = getopt_long(argc, argv, "", long_options, NULL);
 816
 817                 if (c == -1)
 818                         break;
 819                 if (c != 0)
 820                         usage();
 821         }
 822
 823         if (optind >= argc)
 824                 usage();
 825
 826         read_map(argv[optind]);
 827         shrink_table();
 828         if (absolute_percpu)
 829                 make_percpus_absolute();
 830         sort_symbols();
 831         record_relative_base();
 832         optimize_token_table();
 833         write_src();
 834
 835         return 0;
 836 }