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