ia64/xen-unstable

view xen/tools/symbols.c @ 17062:0769835cf50f

x86 shadow: Reduce scope of shadow lock.

emulate_map_dest doesn't require holding lock, since
only shadow related operation possibly involved is to
remove shadow which is less frequent and can acquire
lock inside. Rest are either guest table walk or
per-vcpu monitor table manipulation

Signed-off-by Kevin Tian <kevin.tian@intel.com>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Feb 14 10:33:12 2008 +0000 (2008-02-14)
parents 33242afccb32
children 8d5474a5c66b
line source
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/symbols [--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 */
27 #define _GNU_SOURCE
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <stdint.h>
33 #include <ctype.h>
35 #define KSYM_NAME_LEN 127
38 struct sym_entry {
39 unsigned long long addr;
40 unsigned int len;
41 unsigned char *sym;
42 };
45 static struct sym_entry *table;
46 static unsigned int table_size, table_cnt;
47 static unsigned long long _stext, _etext, _sinittext, _einittext, _sextratext, _eextratext;
48 static int all_symbols = 0;
49 static char symbol_prefix_char = '\0';
51 int token_profit[0x10000];
53 /* the table that holds the result of the compression */
54 unsigned char best_table[256][2];
55 unsigned char best_table_len[256];
58 static void usage(void)
59 {
60 fprintf(stderr, "Usage: symbols [--all-symbols] [--symbol-prefix=<prefix char>] < in.map > out.S\n");
61 exit(1);
62 }
64 /*
65 * This ignores the intensely annoying "mapping symbols" found
66 * in ARM ELF files: $a, $t and $d.
67 */
68 static inline int is_arm_mapping_symbol(const char *str)
69 {
70 return str[0] == '$' && strchr("atd", str[1])
71 && (str[2] == '\0' || str[2] == '.');
72 }
74 static int read_symbol(FILE *in, struct sym_entry *s)
75 {
76 char str[500];
77 char *sym, stype;
78 int rc;
80 rc = fscanf(in, "%llx %c %499s\n", &s->addr, &stype, str);
81 if (rc != 3) {
82 if (rc != EOF) {
83 /* skip line */
84 fgets(str, 500, in);
85 }
86 return -1;
87 }
89 sym = str;
90 /* skip prefix char */
91 if (symbol_prefix_char && str[0] == symbol_prefix_char)
92 sym++;
94 /* Ignore most absolute/undefined (?) symbols. */
95 if (strcmp(sym, "_stext") == 0)
96 _stext = s->addr;
97 else if (strcmp(sym, "_etext") == 0)
98 _etext = s->addr;
99 else if (strcmp(sym, "_sinittext") == 0)
100 _sinittext = s->addr;
101 else if (strcmp(sym, "_einittext") == 0)
102 _einittext = s->addr;
103 else if (strcmp(sym, "_sextratext") == 0)
104 _sextratext = s->addr;
105 else if (strcmp(sym, "_eextratext") == 0)
106 _eextratext = s->addr;
107 else if (toupper((uint8_t)stype) == 'A')
108 {
109 /* Keep these useful absolute symbols */
110 if (strcmp(sym, "__kernel_syscall_via_break") &&
111 strcmp(sym, "__kernel_syscall_via_epc") &&
112 strcmp(sym, "__kernel_sigtramp") &&
113 strcmp(sym, "__gp"))
114 return -1;
116 }
117 else if (toupper((uint8_t)stype) == 'U' ||
118 is_arm_mapping_symbol(sym))
119 return -1;
120 /* exclude also MIPS ELF local symbols ($L123 instead of .L123) */
121 else if (str[0] == '$')
122 return -1;
124 /* include the type field in the symbol name, so that it gets
125 * compressed together */
126 s->len = strlen(str) + 1;
127 s->sym = malloc(s->len + 1);
128 strcpy((char *)s->sym + 1, str);
129 s->sym[0] = stype;
131 return 0;
132 }
134 static int symbol_valid(struct sym_entry *s)
135 {
136 /* Symbols which vary between passes. Passes 1 and 2 must have
137 * identical symbol lists. The symbols_* symbols below are only added
138 * after pass 1, they would be included in pass 2 when --all-symbols is
139 * specified so exclude them to get a stable symbol list.
140 */
141 static char *special_symbols[] = {
142 "symbols_addresses",
143 "symbols_num_syms",
144 "symbols_names",
145 "symbols_markers",
146 "symbols_token_table",
147 "symbols_token_index",
149 /* Exclude linker generated symbols which vary between passes */
150 "_SDA_BASE_", /* ppc */
151 "_SDA2_BASE_", /* ppc */
152 NULL };
153 int i;
154 int offset = 1;
156 /* skip prefix char */
157 if (symbol_prefix_char && *(s->sym + 1) == symbol_prefix_char)
158 offset++;
160 /* if --all-symbols is not specified, then symbols outside the text
161 * and inittext sections are discarded */
162 if (!all_symbols) {
163 if ((s->addr < _stext || s->addr > _etext)
164 && (s->addr < _sinittext || s->addr > _einittext)
165 && (s->addr < _sextratext || s->addr > _eextratext))
166 return 0;
167 /* Corner case. Discard any symbols with the same value as
168 * _etext _einittext or _eextratext; they can move between pass
169 * 1 and 2 when the symbols data are added. If these symbols
170 * move then they may get dropped in pass 2, which breaks the
171 * symbols rules.
172 */
173 if ((s->addr == _etext && strcmp((char*)s->sym + offset, "_etext")) ||
174 (s->addr == _einittext && strcmp((char*)s->sym + offset, "_einittext")) ||
175 (s->addr == _eextratext && strcmp((char*)s->sym + offset, "_eextratext")))
176 return 0;
177 }
179 /* Exclude symbols which vary between passes. */
180 if (strstr((char *)s->sym + offset, "_compiled."))
181 return 0;
183 for (i = 0; special_symbols[i]; i++)
184 if( strcmp((char *)s->sym + offset, special_symbols[i]) == 0 )
185 return 0;
187 return 1;
188 }
190 static void read_map(FILE *in)
191 {
192 while (!feof(in)) {
193 if (table_cnt >= table_size) {
194 table_size += 10000;
195 table = realloc(table, sizeof(*table) * table_size);
196 if (!table) {
197 fprintf(stderr, "out of memory\n");
198 exit (1);
199 }
200 }
201 if (read_symbol(in, &table[table_cnt]) == 0)
202 table_cnt++;
203 }
204 }
206 static void output_label(char *label)
207 {
208 if (symbol_prefix_char)
209 printf(".globl %c%s\n", symbol_prefix_char, label);
210 else
211 printf(".globl %s\n", label);
212 printf("\tALGN\n");
213 if (symbol_prefix_char)
214 printf("%c%s:\n", symbol_prefix_char, label);
215 else
216 printf("%s:\n", label);
217 }
219 /* uncompress a compressed symbol. When this function is called, the best table
220 * might still be compressed itself, so the function needs to be recursive */
221 static int expand_symbol(unsigned char *data, int len, char *result)
222 {
223 int c, rlen, total=0;
225 while (len) {
226 c = *data;
227 /* if the table holds a single char that is the same as the one
228 * we are looking for, then end the search */
229 if (best_table[c][0]==c && best_table_len[c]==1) {
230 *result++ = c;
231 total++;
232 } else {
233 /* if not, recurse and expand */
234 rlen = expand_symbol(best_table[c], best_table_len[c], result);
235 total += rlen;
236 result += rlen;
237 }
238 data++;
239 len--;
240 }
241 *result=0;
243 return total;
244 }
246 static void write_src(void)
247 {
248 unsigned int i, k, off;
249 unsigned int best_idx[256];
250 unsigned int *markers;
251 char buf[KSYM_NAME_LEN+1];
253 printf("#include <asm/types.h>\n");
254 printf("#if BITS_PER_LONG == 64\n");
255 printf("#define PTR .quad\n");
256 printf("#define ALGN .align 8\n");
257 printf("#else\n");
258 printf("#define PTR .long\n");
259 printf("#define ALGN .align 4\n");
260 printf("#endif\n");
262 printf(".data\n");
264 output_label("symbols_addresses");
265 for (i = 0; i < table_cnt; i++) {
266 printf("\tPTR\t%#llx\n", table[i].addr);
267 }
268 printf("\n");
270 output_label("symbols_num_syms");
271 printf("\tPTR\t%d\n", table_cnt);
272 printf("\n");
274 /* table of offset markers, that give the offset in the compressed stream
275 * every 256 symbols */
276 markers = (unsigned int *) malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
278 output_label("symbols_names");
279 off = 0;
280 for (i = 0; i < table_cnt; i++) {
281 if ((i & 0xFF) == 0)
282 markers[i >> 8] = off;
284 printf("\t.byte 0x%02x", table[i].len);
285 for (k = 0; k < table[i].len; k++)
286 printf(", 0x%02x", table[i].sym[k]);
287 printf("\n");
289 off += table[i].len + 1;
290 }
291 printf("\n");
293 output_label("symbols_markers");
294 for (i = 0; i < ((table_cnt + 255) >> 8); i++)
295 printf("\tPTR\t%d\n", markers[i]);
296 printf("\n");
298 free(markers);
300 output_label("symbols_token_table");
301 off = 0;
302 for (i = 0; i < 256; i++) {
303 best_idx[i] = off;
304 expand_symbol(best_table[i], best_table_len[i], buf);
305 printf("\t.asciz\t\"%s\"\n", buf);
306 off += strlen(buf) + 1;
307 }
308 printf("\n");
310 output_label("symbols_token_index");
311 for (i = 0; i < 256; i++)
312 printf("\t.short\t%d\n", best_idx[i]);
313 printf("\n");
314 }
317 /* table lookup compression functions */
319 /* count all the possible tokens in a symbol */
320 static void learn_symbol(unsigned char *symbol, int len)
321 {
322 int i;
324 for (i = 0; i < len - 1; i++)
325 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
326 }
328 /* decrease the count for all the possible tokens in a symbol */
329 static void forget_symbol(unsigned char *symbol, int len)
330 {
331 int i;
333 for (i = 0; i < len - 1; i++)
334 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
335 }
337 /* remove all the invalid symbols from the table and do the initial token count */
338 static void build_initial_tok_table(void)
339 {
340 unsigned int i, pos;
342 pos = 0;
343 for (i = 0; i < table_cnt; i++) {
344 if ( symbol_valid(&table[i]) ) {
345 if (pos != i)
346 table[pos] = table[i];
347 learn_symbol(table[pos].sym, table[pos].len);
348 pos++;
349 }
350 }
351 table_cnt = pos;
352 }
354 static void *memmem_pvt(void *h, size_t hlen, void *n, size_t nlen)
355 {
356 char *p;
357 for (p = h; (p - (char *)h) <= (long)(hlen - nlen); p++)
358 if (!memcmp(p, n, nlen)) return p;
359 return NULL;
360 }
362 /* replace a given token in all the valid symbols. Use the sampled symbols
363 * to update the counts */
364 static void compress_symbols(unsigned char *str, int idx)
365 {
366 unsigned int i, len, size;
367 unsigned char *p1, *p2;
369 for (i = 0; i < table_cnt; i++) {
371 len = table[i].len;
372 p1 = table[i].sym;
374 /* find the token on the symbol */
375 p2 = memmem_pvt(p1, len, str, 2);
376 if (!p2) continue;
378 /* decrease the counts for this symbol's tokens */
379 forget_symbol(table[i].sym, len);
381 size = len;
383 do {
384 *p2 = idx;
385 p2++;
386 size -= (p2 - p1);
387 memmove(p2, p2 + 1, size);
388 p1 = p2;
389 len--;
391 if (size < 2) break;
393 /* find the token on the symbol */
394 p2 = memmem_pvt(p1, size, str, 2);
396 } while (p2);
398 table[i].len = len;
400 /* increase the counts for this symbol's new tokens */
401 learn_symbol(table[i].sym, len);
402 }
403 }
405 /* search the token with the maximum profit */
406 static int find_best_token(void)
407 {
408 int i, best, bestprofit;
410 bestprofit=-10000;
411 best = 0;
413 for (i = 0; i < 0x10000; i++) {
414 if (token_profit[i] > bestprofit) {
415 best = i;
416 bestprofit = token_profit[i];
417 }
418 }
419 return best;
420 }
422 /* this is the core of the algorithm: calculate the "best" table */
423 static void optimize_result(void)
424 {
425 int i, best;
427 /* using the '\0' symbol last allows compress_symbols to use standard
428 * fast string functions */
429 for (i = 255; i >= 0; i--) {
431 /* if this table slot is empty (it is not used by an actual
432 * original char code */
433 if (!best_table_len[i]) {
435 /* find the token with the breates profit value */
436 best = find_best_token();
438 /* place it in the "best" table */
439 best_table_len[i] = 2;
440 best_table[i][0] = best & 0xFF;
441 best_table[i][1] = (best >> 8) & 0xFF;
443 /* replace this token in all the valid symbols */
444 compress_symbols(best_table[i], i);
445 }
446 }
447 }
449 /* start by placing the symbols that are actually used on the table */
450 static void insert_real_symbols_in_table(void)
451 {
452 unsigned int i, j, c;
454 memset(best_table, 0, sizeof(best_table));
455 memset(best_table_len, 0, sizeof(best_table_len));
457 for (i = 0; i < table_cnt; i++) {
458 for (j = 0; j < table[i].len; j++) {
459 c = table[i].sym[j];
460 best_table[c][0]=c;
461 best_table_len[c]=1;
462 }
463 }
464 }
466 static void optimize_token_table(void)
467 {
468 build_initial_tok_table();
470 insert_real_symbols_in_table();
472 /* When valid symbol is not registered, exit to error */
473 if (!table_cnt) {
474 fprintf(stderr, "No valid symbol.\n");
475 exit(1);
476 }
478 optimize_result();
479 }
482 int main(int argc, char **argv)
483 {
484 if (argc >= 2) {
485 int i;
486 for (i = 1; i < argc; i++) {
487 if(strcmp(argv[i], "--all-symbols") == 0)
488 all_symbols = 1;
489 else if (strncmp(argv[i], "--symbol-prefix=", 16) == 0) {
490 char *p = &argv[i][16];
491 /* skip quote */
492 if ((*p == '"' && *(p+2) == '"') || (*p == '\'' && *(p+2) == '\''))
493 p++;
494 symbol_prefix_char = *p;
495 } else
496 usage();
497 }
498 } else if (argc != 1)
499 usage();
501 read_map(stdin);
502 optimize_token_table();
503 write_src();
505 return 0;
506 }