ia64/linux-2.6.18-xen.hg

view scripts/kallsyms.c @ 897:329ea0ccb344

balloon: try harder to balloon up under memory pressure.

Currently if the balloon driver is unable to increase the guest's
reservation it assumes the failure was due to reaching its full
allocation, gives up on the ballooning operation and records the limit
it reached as the "hard limit". The driver will not try again until
the target is set again (even to the same value).

However it is possible that ballooning has in fact failed due to
memory pressure in the host and therefore it is desirable to keep
attempting to reach the target in case memory becomes available. The
most likely scenario is that some guests are ballooning down while
others are ballooning up and therefore there is temporary memory
pressure while things stabilise. You would not expect a well behaved
toolstack to ask a domain to balloon to more than its allocation nor
would you expect it to deliberately over-commit memory by setting
balloon targets which exceed the total host memory.

This patch drops the concept of a hard limit and causes the balloon
driver to retry increasing the reservation on a timer in the same
manner as when decreasing the reservation.

Also if we partially succeed in increasing the reservation
(i.e. receive less pages than we asked for) then we may as well keep
those pages rather than returning them to Xen.

Signed-off-by: Ian Campbell <ian.campbell@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Fri Jun 05 14:01:20 2009 +0100 (2009-06-05)
parents 831230e53067
children
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/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 */
27 #define _GNU_SOURCE
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <ctype.h>
34 #define KSYM_NAME_LEN 127
37 struct sym_entry {
38 unsigned long long addr;
39 unsigned int len;
40 unsigned char *sym;
41 };
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)
58 {
59 fprintf(stderr, "Usage: kallsyms [--all-symbols] [--symbol-prefix=<prefix char>] < in.map > out.S\n");
60 exit(1);
61 }
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 }
73 static int read_symbol(FILE *in, struct sym_entry *s)
74 {
75 char str[500];
76 char *sym, stype;
77 int rc;
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 }
88 sym = str;
89 /* skip prefix char */
90 if (symbol_prefix_char && str[0] == symbol_prefix_char)
91 sym++;
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;
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;
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;
135 return 0;
136 }
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",
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;
160 /* skip prefix char */
161 if (symbol_prefix_char && *(s->sym + 1) == symbol_prefix_char)
162 offset++;
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 }
183 /* Exclude symbols which vary between passes. */
184 if (strstr((char *)s->sym + offset, "_compiled."))
185 return 0;
187 for (i = 0; special_symbols[i]; i++)
188 if( strcmp((char *)s->sym + offset, special_symbols[i]) == 0 )
189 return 0;
191 return 1;
192 }
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 }
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 }
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;
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;
247 return total;
248 }
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];
257 printf("#include <asm/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");
266 printf(".data\n");
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");
274 output_label("kallsyms_num_syms");
275 printf("\tPTR\t%d\n", table_cnt);
276 printf("\n");
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 }
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;
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");
298 off += table[i].len + 1;
299 }
300 printf("\n");
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");
307 free(markers);
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");
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 }
326 /* table lookup compression functions */
328 /* count all the possible tokens in a symbol */
329 static void learn_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 /* 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;
342 for (i = 0; i < len - 1; i++)
343 token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
344 }
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;
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 }
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;
370 for (i = 0; i < table_cnt; i++) {
372 len = table[i].len;
373 p1 = table[i].sym;
375 /* find the token on the symbol */
376 p2 = memmem(p1, len, str, 2);
377 if (!p2) continue;
379 /* decrease the counts for this symbol's tokens */
380 forget_symbol(table[i].sym, len);
382 size = len;
384 do {
385 *p2 = idx;
386 p2++;
387 size -= (p2 - p1);
388 memmove(p2, p2 + 1, size);
389 p1 = p2;
390 len--;
392 if (size < 2) break;
394 /* find the token on the symbol */
395 p2 = memmem(p1, size, str, 2);
397 } while (p2);
399 table[i].len = len;
401 /* increase the counts for this symbol's new tokens */
402 learn_symbol(table[i].sym, len);
403 }
404 }
406 /* search the token with the maximum profit */
407 static int find_best_token(void)
408 {
409 int i, best, bestprofit;
411 bestprofit=-10000;
412 best = 0;
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 }
423 /* this is the core of the algorithm: calculate the "best" table */
424 static void optimize_result(void)
425 {
426 int i, best;
428 /* using the '\0' symbol last allows compress_symbols to use standard
429 * fast string functions */
430 for (i = 255; i >= 0; i--) {
432 /* if this table slot is empty (it is not used by an actual
433 * original char code */
434 if (!best_table_len[i]) {
436 /* find the token with the breates profit value */
437 best = find_best_token();
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;
444 /* replace this token in all the valid symbols */
445 compress_symbols(best_table[i], i);
446 }
447 }
448 }
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;
455 memset(best_table, 0, sizeof(best_table));
456 memset(best_table_len, 0, sizeof(best_table_len));
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 }
467 static void optimize_token_table(void)
468 {
469 build_initial_tok_table();
471 insert_real_symbols_in_table();
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 }
479 optimize_result();
480 }
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();
502 read_map(stdin);
503 optimize_token_table();
504 write_src();
506 return 0;
507 }