1 /* Generate assembler source containing symbol information
3 * Copyright 2002 by Kai Germaschewski
5 * This software may be used and distributed according to the terms
6 * of the GNU General Public License, incorporated herein by reference.
8 * Usage: nm -n vmlinux | scripts/kallsyms [--all-symbols] > symbols.S
12 * (25/Aug/2004) Paulo Marques <pmarques@grupopie.com>
13 * Changed the compression method from stem compression to "table lookup"
16 * Table compression uses all the unused char codes on the symbols and
17 * maps these to the most used substrings (tokens). For instance, it might
18 * map char code 0xF7 to represent "write_" and then in every symbol where
19 * "write_" appears it can be replaced by 0xF7, saving 5 bytes.
20 * The used codes themselves are also placed in the table so that the
21 * decompresion can work without "special cases".
22 * Applied to kernel symbols, this usually produces a compression ratio
34 #define KSYM_NAME_LEN 127
38 unsigned long long addr
;
44 static struct sym_entry
*table
;
45 static unsigned int table_size
, table_cnt
;
46 static unsigned long long _stext
, _etext
, _sinittext
, _einittext
, _sextratext
, _eextratext
;
47 static int all_symbols
= 0;
48 static char symbol_prefix_char
= '\0';
50 int token_profit
[0x10000];
52 /* the table that holds the result of the compression */
53 unsigned char best_table
[256][2];
54 unsigned char best_table_len
[256];
57 static void usage(void)
59 fprintf(stderr
, "Usage: kallsyms [--all-symbols] [--symbol-prefix=<prefix char>] < in.map > out.S\n");
64 * This ignores the intensely annoying "mapping symbols" found
65 * in ARM ELF files: $a, $t and $d.
67 static inline int is_arm_mapping_symbol(const char *str
)
69 return str
[0] == '$' && strchr("atd", str
[1])
70 && (str
[2] == '\0' || str
[2] == '.');
73 static int read_symbol(FILE *in
, struct sym_entry
*s
)
79 rc
= fscanf(in
, "%llx %c %499s\n", &s
->addr
, &stype
, str
);
89 /* skip prefix char */
90 if (symbol_prefix_char
&& str
[0] == symbol_prefix_char
)
93 /* Ignore most absolute/undefined (?) symbols. */
94 if (strcmp(sym
, "_stext") == 0)
96 else if (strcmp(sym
, "_etext") == 0)
98 else if (strcmp(sym
, "_sinittext") == 0)
100 else if (strcmp(sym
, "_einittext") == 0)
101 _einittext
= s
->addr
;
102 else if (strcmp(sym
, "_sextratext") == 0)
103 _sextratext
= s
->addr
;
104 else if (strcmp(sym
, "_eextratext") == 0)
105 _eextratext
= s
->addr
;
106 else if (toupper(stype
) == 'A')
108 /* Keep these useful absolute symbols */
109 if (strcmp(sym
, "__kernel_syscall_via_break") &&
110 strcmp(sym
, "__kernel_syscall_via_epc") &&
111 strcmp(sym
, "__kernel_sigtramp") &&
116 else if (toupper(stype
) == 'U' ||
117 is_arm_mapping_symbol(sym
))
120 /* include the type field in the symbol name, so that it gets
121 * compressed together */
122 s
->len
= strlen(str
) + 1;
123 s
->sym
= malloc(s
->len
+ 1);
124 strcpy((char *)s
->sym
+ 1, str
);
130 static int symbol_valid(struct sym_entry
*s
)
132 /* Symbols which vary between passes. Passes 1 and 2 must have
133 * identical symbol lists. The kallsyms_* symbols below are only added
134 * after pass 1, they would be included in pass 2 when --all-symbols is
135 * specified so exclude them to get a stable symbol list.
137 static char *special_symbols
[] = {
138 "kallsyms_addresses",
142 "kallsyms_token_table",
143 "kallsyms_token_index",
145 /* Exclude linker generated symbols which vary between passes */
146 "_SDA_BASE_", /* ppc */
147 "_SDA2_BASE_", /* ppc */
152 /* skip prefix char */
153 if (symbol_prefix_char
&& *(s
->sym
+ 1) == symbol_prefix_char
)
156 /* if --all-symbols is not specified, then symbols outside the text
157 * and inittext sections are discarded */
159 if ((s
->addr
< _stext
|| s
->addr
> _etext
)
160 && (s
->addr
< _sinittext
|| s
->addr
> _einittext
)
161 && (s
->addr
< _sextratext
|| s
->addr
> _eextratext
))
163 /* Corner case. Discard any symbols with the same value as
164 * _etext _einittext or _eextratext; they can move between pass
165 * 1 and 2 when the kallsyms data are added. If these symbols
166 * move then they may get dropped in pass 2, which breaks the
169 if ((s
->addr
== _etext
&& strcmp((char*)s
->sym
+ offset
, "_etext")) ||
170 (s
->addr
== _einittext
&& strcmp((char*)s
->sym
+ offset
, "_einittext")) ||
171 (s
->addr
== _eextratext
&& strcmp((char*)s
->sym
+ offset
, "_eextratext")))
175 /* Exclude symbols which vary between passes. */
176 if (strstr((char *)s
->sym
+ offset
, "_compiled."))
179 for (i
= 0; special_symbols
[i
]; i
++)
180 if( strcmp((char *)s
->sym
+ offset
, special_symbols
[i
]) == 0 )
186 static void read_map(FILE *in
)
189 if (table_cnt
>= table_size
) {
191 table
= realloc(table
, sizeof(*table
) * table_size
);
193 fprintf(stderr
, "out of memory\n");
197 if (read_symbol(in
, &table
[table_cnt
]) == 0)
202 static void output_label(char *label
)
204 if (symbol_prefix_char
)
205 printf(".globl %c%s\n", symbol_prefix_char
, label
);
207 printf(".globl %s\n", label
);
209 if (symbol_prefix_char
)
210 printf("%c%s:\n", symbol_prefix_char
, label
);
212 printf("%s:\n", label
);
215 /* uncompress a compressed symbol. When this function is called, the best table
216 * might still be compressed itself, so the function needs to be recursive */
217 static int expand_symbol(unsigned char *data
, int len
, char *result
)
219 int c
, rlen
, total
=0;
223 /* if the table holds a single char that is the same as the one
224 * we are looking for, then end the search */
225 if (best_table
[c
][0]==c
&& best_table_len
[c
]==1) {
229 /* if not, recurse and expand */
230 rlen
= expand_symbol(best_table
[c
], best_table_len
[c
], result
);
242 static void write_src(void)
244 unsigned int i
, k
, off
;
245 unsigned int best_idx
[256];
246 unsigned int *markers
;
247 char buf
[KSYM_NAME_LEN
+1];
249 printf("#include <asm/types.h>\n");
250 printf("#if BITS_PER_LONG == 64\n");
251 printf("#define PTR .quad\n");
252 printf("#define ALGN .align 8\n");
254 printf("#define PTR .long\n");
255 printf("#define ALGN .align 4\n");
260 output_label("kallsyms_addresses");
261 for (i
= 0; i
< table_cnt
; i
++) {
262 printf("\tPTR\t%#llx\n", table
[i
].addr
);
266 output_label("kallsyms_num_syms");
267 printf("\tPTR\t%d\n", table_cnt
);
270 /* table of offset markers, that give the offset in the compressed stream
271 * every 256 symbols */
272 markers
= (unsigned int *) malloc(sizeof(unsigned int) * ((table_cnt
+ 255) / 256));
274 output_label("kallsyms_names");
276 for (i
= 0; i
< table_cnt
; i
++) {
278 markers
[i
>> 8] = off
;
280 printf("\t.byte 0x%02x", table
[i
].len
);
281 for (k
= 0; k
< table
[i
].len
; k
++)
282 printf(", 0x%02x", table
[i
].sym
[k
]);
285 off
+= table
[i
].len
+ 1;
289 output_label("kallsyms_markers");
290 for (i
= 0; i
< ((table_cnt
+ 255) >> 8); i
++)
291 printf("\tPTR\t%d\n", markers
[i
]);
296 output_label("kallsyms_token_table");
298 for (i
= 0; i
< 256; i
++) {
300 expand_symbol(best_table
[i
], best_table_len
[i
], buf
);
301 printf("\t.asciz\t\"%s\"\n", buf
);
302 off
+= strlen(buf
) + 1;
306 output_label("kallsyms_token_index");
307 for (i
= 0; i
< 256; i
++)
308 printf("\t.short\t%d\n", best_idx
[i
]);
313 /* table lookup compression functions */
315 /* count all the possible tokens in a symbol */
316 static void learn_symbol(unsigned char *symbol
, int len
)
320 for (i
= 0; i
< len
- 1; i
++)
321 token_profit
[ symbol
[i
] + (symbol
[i
+ 1] << 8) ]++;
324 /* decrease the count for all the possible tokens in a symbol */
325 static void forget_symbol(unsigned char *symbol
, int len
)
329 for (i
= 0; i
< len
- 1; i
++)
330 token_profit
[ symbol
[i
] + (symbol
[i
+ 1] << 8) ]--;
333 /* remove all the invalid symbols from the table and do the initial token count */
334 static void build_initial_tok_table(void)
339 for (i
= 0; i
< table_cnt
; i
++) {
340 if ( symbol_valid(&table
[i
]) ) {
342 table
[pos
] = table
[i
];
343 learn_symbol(table
[pos
].sym
, table
[pos
].len
);
350 /* replace a given token in all the valid symbols. Use the sampled symbols
351 * to update the counts */
352 static void compress_symbols(unsigned char *str
, int idx
)
354 unsigned int i
, len
, size
;
355 unsigned char *p1
, *p2
;
357 for (i
= 0; i
< table_cnt
; i
++) {
362 /* find the token on the symbol */
363 p2
= memmem(p1
, len
, str
, 2);
366 /* decrease the counts for this symbol's tokens */
367 forget_symbol(table
[i
].sym
, len
);
375 memmove(p2
, p2
+ 1, size
);
381 /* find the token on the symbol */
382 p2
= memmem(p1
, size
, str
, 2);
388 /* increase the counts for this symbol's new tokens */
389 learn_symbol(table
[i
].sym
, len
);
393 /* search the token with the maximum profit */
394 static int find_best_token(void)
396 int i
, best
, bestprofit
;
401 for (i
= 0; i
< 0x10000; i
++) {
402 if (token_profit
[i
] > bestprofit
) {
404 bestprofit
= token_profit
[i
];
410 /* this is the core of the algorithm: calculate the "best" table */
411 static void optimize_result(void)
415 /* using the '\0' symbol last allows compress_symbols to use standard
416 * fast string functions */
417 for (i
= 255; i
>= 0; i
--) {
419 /* if this table slot is empty (it is not used by an actual
420 * original char code */
421 if (!best_table_len
[i
]) {
423 /* find the token with the breates profit value */
424 best
= find_best_token();
426 /* place it in the "best" table */
427 best_table_len
[i
] = 2;
428 best_table
[i
][0] = best
& 0xFF;
429 best_table
[i
][1] = (best
>> 8) & 0xFF;
431 /* replace this token in all the valid symbols */
432 compress_symbols(best_table
[i
], i
);
437 /* start by placing the symbols that are actually used on the table */
438 static void insert_real_symbols_in_table(void)
440 unsigned int i
, j
, c
;
442 memset(best_table
, 0, sizeof(best_table
));
443 memset(best_table_len
, 0, sizeof(best_table_len
));
445 for (i
= 0; i
< table_cnt
; i
++) {
446 for (j
= 0; j
< table
[i
].len
; j
++) {
454 static void optimize_token_table(void)
456 build_initial_tok_table();
458 insert_real_symbols_in_table();
460 /* When valid symbol is not registered, exit to error */
462 fprintf(stderr
, "No valid symbol.\n");
470 int main(int argc
, char **argv
)
474 for (i
= 1; i
< argc
; i
++) {
475 if(strcmp(argv
[i
], "--all-symbols") == 0)
477 else if (strncmp(argv
[i
], "--symbol-prefix=", 16) == 0) {
478 char *p
= &argv
[i
][16];
480 if ((*p
== '"' && *(p
+2) == '"') || (*p
== '\'' && *(p
+2) == '\''))
482 symbol_prefix_char
= *p
;
486 } else if (argc
!= 1)
490 optimize_token_table();
This page took 0.041874 seconds and 6 git commands to generate.