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