Palacios Public Git Repository

To checkout Palacios execute

  git clone http://v3vee.org/palacios/palacios.web/palacios.git
This will give you the master branch. You probably want the devel branch or one of the release branches. To switch to the devel branch, simply execute
  cd palacios
  git checkout --track -b devel origin/devel
The other branches are similar.


small fix
[palacios-OLD.git] / scripts / kallsyms.c
1 /* Generate assembler source containing symbol information
2  *
3  * Copyright 2002       by Kai Germaschewski
4  *
5  * This software may be used and distributed according to the terms
6  * of the GNU General Public License, incorporated herein by reference.
7  *
8  * Usage: nm -n vmlinux | scripts/kallsyms [--all-symbols] > symbols.S
9  *
10  * ChangeLog:
11  *
12  * (25/Aug/2004) Paulo Marques <pmarques@grupopie.com>
13  *      Changed the compression method from stem compression to "table lookup"
14  *      compression
15  *
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
23  *  of about 50%.
24  *
25  */
26
27 #define _GNU_SOURCE
28
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <ctype.h>
33
34 #define KSYM_NAME_LEN           127
35
36
37 struct sym_entry {
38         unsigned long long addr;
39         unsigned int len;
40         unsigned char *sym;
41 };
42
43
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';
49
50 int token_profit[0x10000];
51
52 /* the table that holds the result of the compression */
53 unsigned char best_table[256][2];
54 unsigned char best_table_len[256];
55
56
57 static void usage(void)
58 {
59         fprintf(stderr, "Usage: kallsyms [--all-symbols] [--symbol-prefix=<prefix char>] < in.map > out.S\n");
60         exit(1);
61 }
62
63 /*
64  * This ignores the intensely annoying "mapping symbols" found
65  * in ARM ELF files: $a, $t and $d.
66  */
67 static inline int is_arm_mapping_symbol(const char *str)
68 {
69         return str[0] == '$' && strchr("atd", str[1])
70                && (str[2] == '\0' || str[2] == '.');
71 }
72
73 static int read_symbol(FILE *in, struct sym_entry *s)
74 {
75         char str[500];
76         char *sym, stype;
77         int rc;
78
79         rc = fscanf(in, "%llx %c %499s\n", &s->addr, &stype, str);
80         if (rc != 3) {
81                 if (rc != EOF) {
82                         /* skip line */
83                         fgets(str, 500, in);
84                 }
85                 return -1;
86         }
87
88         sym = str;
89         /* skip prefix char */
90         if (symbol_prefix_char && str[0] == symbol_prefix_char)
91                 sym++;
92
93         /* Ignore most absolute/undefined (?) symbols. */
94         if (strcmp(sym, "_stext") == 0)
95                 _stext = s->addr;
96         else if (strcmp(sym, "_etext") == 0)
97                 _etext = s->addr;
98         else if (strcmp(sym, "_sinittext") == 0)
99                 _sinittext = s->addr;
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')
107         {
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") &&
112                     strcmp(sym, "__gp"))
113                         return -1;
114
115         }
116         else if (toupper(stype) == 'U' ||
117                  is_arm_mapping_symbol(sym))
118                 return -1;
119         /* exclude also MIPS ELF local symbols ($L123 instead of .L123) */
120         else if (str[0] == '$')
121                 return -1;
122
123         /* include the type field in the symbol name, so that it gets
124          * compressed together */
125         s->len = strlen(str) + 1;
126         s->sym = malloc(s->len + 1);
127         if (!s->sym) {
128                 fprintf(stderr, "kallsyms failure: "
129                         "unable to allocate required amount of memory\n");
130                 exit(EXIT_FAILURE);
131         }
132         strcpy((char *)s->sym + 1, str);
133         s->sym[0] = stype;
134
135         return 0;
136 }
137
138 static int symbol_valid(struct sym_entry *s)
139 {
140         /* Symbols which vary between passes.  Passes 1 and 2 must have
141          * identical symbol lists.  The kallsyms_* symbols below are only added
142          * after pass 1, they would be included in pass 2 when --all-symbols is
143          * specified so exclude them to get a stable symbol list.
144          */
145         static char *special_symbols[] = {
146                 "kallsyms_addresses",
147                 "kallsyms_num_syms",
148                 "kallsyms_names",
149                 "kallsyms_markers",
150                 "kallsyms_token_table",
151                 "kallsyms_token_index",
152
153         /* Exclude linker generated symbols which vary between passes */
154                 "_SDA_BASE_",           /* ppc */
155                 "_SDA2_BASE_",          /* ppc */
156                 NULL };
157         int i;
158         int offset = 1;
159
160         /* skip prefix char */
161         if (symbol_prefix_char && *(s->sym + 1) == symbol_prefix_char)
162                 offset++;
163
164         /* if --all-symbols is not specified, then symbols outside the text
165          * and inittext sections are discarded */
166         if (!all_symbols) {
167                 if ((s->addr < _stext || s->addr > _etext)
168                     && (s->addr < _sinittext || s->addr > _einittext)
169                     && (s->addr < _sextratext || s->addr > _eextratext))
170                         return 0;
171                 /* Corner case.  Discard any symbols with the same value as
172                  * _etext _einittext or _eextratext; they can move between pass
173                  * 1 and 2 when the kallsyms data are added.  If these symbols
174                  * move then they may get dropped in pass 2, which breaks the
175                  * kallsyms rules.
176                  */
177                 if ((s->addr == _etext && strcmp((char*)s->sym + offset, "_etext")) ||
178                     (s->addr == _einittext && strcmp((char*)s->sym + offset, "_einittext")) ||
179                     (s->addr == _eextratext && strcmp((char*)s->sym + offset, "_eextratext")))
180                         return 0;
181         }
182
183         /* Exclude symbols which vary between passes. */
184         if (strstr((char *)s->sym + offset, "_compiled."))
185                 return 0;
186
187         for (i = 0; special_symbols[i]; i++)
188                 if( strcmp((char *)s->sym + offset, special_symbols[i]) == 0 )
189                         return 0;
190
191         return 1;
192 }
193
194 static void read_map(FILE *in)
195 {
196         while (!feof(in)) {
197                 if (table_cnt >= table_size) {
198                         table_size += 10000;
199                         table = realloc(table, sizeof(*table) * table_size);
200                         if (!table) {
201                                 fprintf(stderr, "out of memory\n");
202                                 exit (1);
203                         }
204                 }
205                 if (read_symbol(in, &table[table_cnt]) == 0)
206                         table_cnt++;
207         }
208 }
209
210 static void output_label(char *label)
211 {
212         if (symbol_prefix_char)
213                 printf(".globl %c%s\n", symbol_prefix_char, label);
214         else
215                 printf(".globl %s\n", label);
216         printf("\tALGN\n");
217         if (symbol_prefix_char)
218                 printf("%c%s:\n", symbol_prefix_char, label);
219         else
220                 printf("%s:\n", label);
221 }
222
223 /* uncompress a compressed symbol. When this function is called, the best table
224  * might still be compressed itself, so the function needs to be recursive */
225 static int expand_symbol(unsigned char *data, int len, char *result)
226 {
227         int c, rlen, total=0;
228
229         while (len) {
230                 c = *data;
231                 /* if the table holds a single char that is the same as the one
232                  * we are looking for, then end the search */
233                 if (best_table[c][0]==c && best_table_len[c]==1) {
234                         *result++ = c;
235                         total++;
236                 } else {
237                         /* if not, recurse and expand */
238                         rlen = expand_symbol(best_table[c], best_table_len[c], result);
239                         total += rlen;
240                         result += rlen;
241                 }
242                 data++;
243                 len--;
244         }
245         *result=0;
246
247         return total;
248 }
249
250 static void write_src(void)
251 {
252         unsigned int i, k, off;
253         unsigned int best_idx[256];
254         unsigned int *markers;
255         char buf[KSYM_NAME_LEN+1];
256
257         printf("#include <arch/types.h>\n");
258         printf("#if BITS_PER_LONG == 64\n");
259         printf("#define PTR .quad\n");
260         printf("#define ALGN .align 8\n");
261         printf("#else\n");
262         printf("#define PTR .long\n");
263         printf("#define ALGN .align 4\n");
264         printf("#endif\n");
265
266         printf(".data\n");
267
268         output_label("kallsyms_addresses");
269         for (i = 0; i < table_cnt; i++) {
270                 printf("\tPTR\t%#llx\n", table[i].addr);
271         }
272         printf("\n");
273
274         output_label("kallsyms_num_syms");
275         printf("\tPTR\t%d\n", table_cnt);
276         printf("\n");
277
278         /* table of offset markers, that give the offset in the compressed stream
279          * every 256 symbols */
280         markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
281         if (!markers) {
282                 fprintf(stderr, "kallsyms failure: "
283                         "unable to allocate required memory\n");
284                 exit(EXIT_FAILURE);
285         }
286
287         output_label("kallsyms_names");
288         off = 0;
289         for (i = 0; i < table_cnt; i++) {
290                 if ((i & 0xFF) == 0)
291                         markers[i >> 8] = off;
292
293                 printf("\t.byte 0x%02x", table[i].len);
294                 for (k = 0; k < table[i].len; k++)
295                         printf(", 0x%02x", table[i].sym[k]);
296                 printf("\n");
297
298                 off += table[i].len + 1;
299         }
300         printf("\n");
301
302         output_label("kallsyms_markers");
303         for (i = 0; i < ((table_cnt + 255) >> 8); i++)
304                 printf("\tPTR\t%d\n", markers[i]);
305         printf("\n");
306
307         free(markers);
308
309         output_label("kallsyms_token_table");
310         off = 0;
311         for (i = 0; i < 256; i++) {
312                 best_idx[i] = off;
313                 expand_symbol(best_table[i], best_table_len[i], buf);
314                 printf("\t.asciz\t\"%s\"\n", buf);
315                 off += strlen(buf) + 1;
316         }
317         printf("\n");
318
319         output_label("kallsyms_token_index");
320         for (i = 0; i < 256; i++)
321                 printf("\t.short\t%d\n", best_idx[i]);
322         printf("\n");
323 }
324
325
326 /* table lookup compression functions */
327
328 /* count all the possible tokens in a symbol */
329 static void learn_symbol(unsigned char *symbol, int len)
330 {
331         int i;
332
333         for (i = 0; i < len - 1; i++)
334                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
335 }
336
337 /* decrease the count for all the possible tokens in a symbol */
338 static void forget_symbol(unsigned char *symbol, int len)
339 {
340         int i;
341
342         for (i = 0; i < len - 1; i++)
343                 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
344 }
345
346 /* remove all the invalid symbols from the table and do the initial token count */
347 static void build_initial_tok_table(void)
348 {
349         unsigned int i, pos;
350
351         pos = 0;
352         for (i = 0; i < table_cnt; i++) {
353                 if ( symbol_valid(&table[i]) ) {
354                         if (pos != i)
355                                 table[pos] = table[i];
356                         learn_symbol(table[pos].sym, table[pos].len);
357                         pos++;
358                 }
359         }
360         table_cnt = pos;
361 }
362
363 /* replace a given token in all the valid symbols. Use the sampled symbols
364  * to update the counts */
365 static void compress_symbols(unsigned char *str, int idx)
366 {
367         unsigned int i, len, size;
368         unsigned char *p1, *p2;
369
370         for (i = 0; i < table_cnt; i++) {
371
372                 len = table[i].len;
373                 p1 = table[i].sym;
374
375                 /* find the token on the symbol */
376                 p2 = memmem(p1, len, str, 2);
377                 if (!p2) continue;
378
379                 /* decrease the counts for this symbol's tokens */
380                 forget_symbol(table[i].sym, len);
381
382                 size = len;
383
384                 do {
385                         *p2 = idx;
386                         p2++;
387                         size -= (p2 - p1);
388                         memmove(p2, p2 + 1, size);
389                         p1 = p2;
390                         len--;
391
392                         if (size < 2) break;
393
394                         /* find the token on the symbol */
395                         p2 = memmem(p1, size, str, 2);
396
397                 } while (p2);
398
399                 table[i].len = len;
400
401                 /* increase the counts for this symbol's new tokens */
402                 learn_symbol(table[i].sym, len);
403         }
404 }
405
406 /* search the token with the maximum profit */
407 static int find_best_token(void)
408 {
409         int i, best, bestprofit;
410
411         bestprofit=-10000;
412         best = 0;
413
414         for (i = 0; i < 0x10000; i++) {
415                 if (token_profit[i] > bestprofit) {
416                         best = i;
417                         bestprofit = token_profit[i];
418                 }
419         }
420         return best;
421 }
422
423 /* this is the core of the algorithm: calculate the "best" table */
424 static void optimize_result(void)
425 {
426         int i, best;
427
428         /* using the '\0' symbol last allows compress_symbols to use standard
429          * fast string functions */
430         for (i = 255; i >= 0; i--) {
431
432                 /* if this table slot is empty (it is not used by an actual
433                  * original char code */
434                 if (!best_table_len[i]) {
435
436                         /* find the token with the breates profit value */
437                         best = find_best_token();
438
439                         /* place it in the "best" table */
440                         best_table_len[i] = 2;
441                         best_table[i][0] = best & 0xFF;
442                         best_table[i][1] = (best >> 8) & 0xFF;
443
444                         /* replace this token in all the valid symbols */
445                         compress_symbols(best_table[i], i);
446                 }
447         }
448 }
449
450 /* start by placing the symbols that are actually used on the table */
451 static void insert_real_symbols_in_table(void)
452 {
453         unsigned int i, j, c;
454
455         memset(best_table, 0, sizeof(best_table));
456         memset(best_table_len, 0, sizeof(best_table_len));
457
458         for (i = 0; i < table_cnt; i++) {
459                 for (j = 0; j < table[i].len; j++) {
460                         c = table[i].sym[j];
461                         best_table[c][0]=c;
462                         best_table_len[c]=1;
463                 }
464         }
465 }
466
467 static void optimize_token_table(void)
468 {
469         build_initial_tok_table();
470
471         insert_real_symbols_in_table();
472
473         /* When valid symbol is not registered, exit to error */
474         if (!table_cnt) {
475                 fprintf(stderr, "No valid symbol.\n");
476                 exit(1);
477         }
478
479         optimize_result();
480 }
481
482
483 int main(int argc, char **argv)
484 {
485         if (argc >= 2) {
486                 int i;
487                 for (i = 1; i < argc; i++) {
488                         if(strcmp(argv[i], "--all-symbols") == 0)
489                                 all_symbols = 1;
490                         else if (strncmp(argv[i], "--symbol-prefix=", 16) == 0) {
491                                 char *p = &argv[i][16];
492                                 /* skip quote */
493                                 if ((*p == '"' && *(p+2) == '"') || (*p == '\'' && *(p+2) == '\''))
494                                         p++;
495                                 symbol_prefix_char = *p;
496                         } else
497                                 usage();
498                 }
499         } else if (argc != 1)
500                 usage();
501
502         read_map(stdin);
503         optimize_token_table();
504         write_src();
505
506         return 0;
507 }