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