kallsyms.c 18.1 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
/* Generate assembler source containing symbol information
 *
 * Copyright 2002       by Kai Germaschewski
 *
 * This software may be used and distributed according to the terms
 * of the GNU General Public License, incorporated herein by reference.
 *
 * Usage: nm -n vmlinux | scripts/kallsyms [--all-symbols] > symbols.S
 *
 *      Table compression uses all the unused char codes on the symbols and
 *  maps these to the most used substrings (tokens). For instance, it might
 *  map char code 0xF7 to represent "write_" and then in every symbol where
 *  "write_" appears it can be replaced by 0xF7, saving 5 bytes.
 *      The used codes themselves are also placed in the table so that the
 *  decompresion can work without "special cases".
 *      Applied to kernel symbols, this usually produces a compression ratio
 *  of about 50%.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
25
#include <limits.h>
Linus Torvalds's avatar
Linus Torvalds committed
26

27 28 29 30
#ifndef ARRAY_SIZE
#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#endif

31
#define KSYM_NAME_LEN		128
Linus Torvalds's avatar
Linus Torvalds committed
32 33 34

struct sym_entry {
	unsigned long long addr;
35
	unsigned int len;
36
	unsigned int start_pos;
Linus Torvalds's avatar
Linus Torvalds committed
37
	unsigned char *sym;
38
	unsigned int percpu_absolute;
Linus Torvalds's avatar
Linus Torvalds committed
39 40
};

41 42
struct addr_range {
	const char *start_sym, *end_sym;
43 44 45 46
	unsigned long long start, end;
};

static unsigned long long _text;
47
static unsigned long long relative_base;
48
static struct addr_range text_ranges[] = {
49 50 51 52 53 54 55 56
	{ "_stext",     "_etext"     },
	{ "_sinittext", "_einittext" },
	{ "_stext_l1",  "_etext_l1"  },	/* Blackfin on-chip L1 inst SRAM */
	{ "_stext_l2",  "_etext_l2"  },	/* Blackfin on-chip L2 SRAM */
};
#define text_range_text     (&text_ranges[0])
#define text_range_inittext (&text_ranges[1])

57 58 59 60
static struct addr_range percpu_range = {
	"__per_cpu_start", "__per_cpu_end", -1ULL, 0
};

Linus Torvalds's avatar
Linus Torvalds committed
61
static struct sym_entry *table;
62
static unsigned int table_size, table_cnt;
Linus Torvalds's avatar
Linus Torvalds committed
63
static int all_symbols = 0;
64
static int absolute_percpu = 0;
65
static int base_relative = 0;
Linus Torvalds's avatar
Linus Torvalds committed
66

67
int token_profit[0x10000];
Linus Torvalds's avatar
Linus Torvalds committed
68 69

/* the table that holds the result of the compression */
70
unsigned char best_table[256][2];
Linus Torvalds's avatar
Linus Torvalds committed
71 72 73
unsigned char best_table_len[256];


74
static void usage(void)
Linus Torvalds's avatar
Linus Torvalds committed
75
{
76
	fprintf(stderr, "Usage: kallsyms [--all-symbols] "
77
			"[--base-relative] < in.map > out.S\n");
Linus Torvalds's avatar
Linus Torvalds committed
78 79 80 81 82 83 84
	exit(1);
}

/*
 * This ignores the intensely annoying "mapping symbols" found
 * in ARM ELF files: $a, $t and $d.
 */
85
static inline int is_arm_mapping_symbol(const char *str)
Linus Torvalds's avatar
Linus Torvalds committed
86
{
87
	return str[0] == '$' && strchr("axtd", str[1])
Linus Torvalds's avatar
Linus Torvalds committed
88 89 90
	       && (str[2] == '\0' || str[2] == '.');
}

91 92
static int check_symbol_range(const char *sym, unsigned long long addr,
			      struct addr_range *ranges, int entries)
93 94
{
	size_t i;
95
	struct addr_range *ar;
96

97 98
	for (i = 0; i < entries; ++i) {
		ar = &ranges[i];
99

100 101
		if (strcmp(sym, ar->start_sym) == 0) {
			ar->start = addr;
102
			return 0;
103 104
		} else if (strcmp(sym, ar->end_sym) == 0) {
			ar->end = addr;
105 106 107 108 109 110 111
			return 0;
		}
	}

	return 1;
}

112
static int read_symbol(FILE *in, struct sym_entry *s)
Linus Torvalds's avatar
Linus Torvalds committed
113
{
114
	char sym[500], stype;
Linus Torvalds's avatar
Linus Torvalds committed
115 116
	int rc;

117
	rc = fscanf(in, "%llx %c %499s\n", &s->addr, &stype, sym);
Linus Torvalds's avatar
Linus Torvalds committed
118
	if (rc != 3) {
119
		if (rc != EOF && fgets(sym, 500, in) == NULL)
120
			fprintf(stderr, "Read error or end of file.\n");
Linus Torvalds's avatar
Linus Torvalds committed
121 122
		return -1;
	}
123
	if (strlen(sym) > KSYM_NAME_LEN) {
124
		fprintf(stderr, "Symbol %s too long for kallsyms (%zu vs %d).\n"
125
				"Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
126
			sym, strlen(sym), KSYM_NAME_LEN);
127 128
		return -1;
	}
Linus Torvalds's avatar
Linus Torvalds committed
129 130

	/* Ignore most absolute/undefined (?) symbols. */
131 132
	if (strcmp(sym, "_text") == 0)
		_text = s->addr;
133 134
	else if (check_symbol_range(sym, s->addr, text_ranges,
				    ARRAY_SIZE(text_ranges)) == 0)
135
		/* nothing to do */;
136
	else if (toupper(stype) == 'A')
Linus Torvalds's avatar
Linus Torvalds committed
137 138
	{
		/* Keep these useful absolute symbols */
139 140 141 142
		if (strcmp(sym, "__kernel_syscall_via_break") &&
		    strcmp(sym, "__kernel_syscall_via_epc") &&
		    strcmp(sym, "__kernel_sigtramp") &&
		    strcmp(sym, "__gp"))
Linus Torvalds's avatar
Linus Torvalds committed
143 144 145
			return -1;

	}
146
	else if (toupper(stype) == 'U' ||
147
		 is_arm_mapping_symbol(sym))
Linus Torvalds's avatar
Linus Torvalds committed
148
		return -1;
149
	/* exclude also MIPS ELF local symbols ($L123 instead of .L123) */
150
	else if (sym[0] == '$')
151
		return -1;
152
	/* exclude debugging symbols */
153
	else if (stype == 'N' || stype == 'n')
154
		return -1;
Linus Torvalds's avatar
Linus Torvalds committed
155 156 157

	/* include the type field in the symbol name, so that it gets
	 * compressed together */
158
	s->len = strlen(sym) + 1;
159
	s->sym = malloc(s->len + 1);
160 161 162 163 164
	if (!s->sym) {
		fprintf(stderr, "kallsyms failure: "
			"unable to allocate required amount of memory\n");
		exit(EXIT_FAILURE);
	}
165
	strcpy((char *)s->sym + 1, sym);
166
	s->sym[0] = stype;
Linus Torvalds's avatar
Linus Torvalds committed
167

168 169
	s->percpu_absolute = 0;

170 171 172
	/* Record if we've found __per_cpu_start/end. */
	check_symbol_range(sym, s->addr, &percpu_range, 1);

Linus Torvalds's avatar
Linus Torvalds committed
173 174 175
	return 0;
}

176 177
static int symbol_in_range(struct sym_entry *s, struct addr_range *ranges,
			   int entries)
178 179
{
	size_t i;
180
	struct addr_range *ar;
181

182 183
	for (i = 0; i < entries; ++i) {
		ar = &ranges[i];
184

185
		if (s->addr >= ar->start && s->addr <= ar->end)
186
			return 1;
187 188
	}

189
	return 0;
190 191
}

192
static int symbol_valid(struct sym_entry *s)
Linus Torvalds's avatar
Linus Torvalds committed
193 194
{
	/* Symbols which vary between passes.  Passes 1 and 2 must have
195 196 197
	 * identical symbol lists.  The kallsyms_* symbols below are only added
	 * after pass 1, they would be included in pass 2 when --all-symbols is
	 * specified so exclude them to get a stable symbol list.
Linus Torvalds's avatar
Linus Torvalds committed
198 199
	 */
	static char *special_symbols[] = {
200
		"kallsyms_addresses",
201 202
		"kallsyms_offsets",
		"kallsyms_relative_base",
203 204 205 206 207 208
		"kallsyms_num_syms",
		"kallsyms_names",
		"kallsyms_markers",
		"kallsyms_token_table",
		"kallsyms_token_index",

Linus Torvalds's avatar
Linus Torvalds committed
209 210 211 212
	/* Exclude linker generated symbols which vary between passes */
		"_SDA_BASE_",		/* ppc */
		"_SDA2_BASE_",		/* ppc */
		NULL };
213

214 215
	static char *special_prefixes[] = {
		"__crc_",		/* modversions */
216
		"__efistub_",		/* arm64 EFI stub namespace */
217 218
		NULL };

219 220
	static char *special_suffixes[] = {
		"_veneer",		/* arm */
221 222
		"_from_arm",		/* arm */
		"_from_thumb",		/* arm */
223 224
		NULL };

Linus Torvalds's avatar
Linus Torvalds committed
225
	int i;
226 227
	char *sym_name = (char *)s->sym + 1;

Linus Torvalds's avatar
Linus Torvalds committed
228 229 230
	/* if --all-symbols is not specified, then symbols outside the text
	 * and inittext sections are discarded */
	if (!all_symbols) {
231 232
		if (symbol_in_range(s, text_ranges,
				    ARRAY_SIZE(text_ranges)) == 0)
Linus Torvalds's avatar
Linus Torvalds committed
233 234
			return 0;
		/* Corner case.  Discard any symbols with the same value as
235 236 237 238
		 * _etext _einittext; they can move between pass 1 and 2 when
		 * the kallsyms data are added.  If these symbols move then
		 * they may get dropped in pass 2, which breaks the kallsyms
		 * rules.
Linus Torvalds's avatar
Linus Torvalds committed
239
		 */
240
		if ((s->addr == text_range_text->end &&
241
				strcmp(sym_name,
242
				       text_range_text->end_sym)) ||
243
		    (s->addr == text_range_inittext->end &&
244
				strcmp(sym_name,
245
				       text_range_inittext->end_sym)))
Linus Torvalds's avatar
Linus Torvalds committed
246 247 248 249 250
			return 0;
	}

	/* Exclude symbols which vary between passes. */
	for (i = 0; special_symbols[i]; i++)
251
		if (strcmp(sym_name, special_symbols[i]) == 0)
Linus Torvalds's avatar
Linus Torvalds committed
252 253
			return 0;

254 255 256 257 258 259 260 261
	for (i = 0; special_prefixes[i]; i++) {
		int l = strlen(special_prefixes[i]);

		if (l <= strlen(sym_name) &&
		    strncmp(sym_name, special_prefixes[i], l) == 0)
			return 0;
	}

262 263 264 265 266 267 268
	for (i = 0; special_suffixes[i]; i++) {
		int l = strlen(sym_name) - strlen(special_suffixes[i]);

		if (l >= 0 && strcmp(sym_name + l, special_suffixes[i]) == 0)
			return 0;
	}

Linus Torvalds's avatar
Linus Torvalds committed
269 270 271
	return 1;
}

272
static void read_map(FILE *in)
Linus Torvalds's avatar
Linus Torvalds committed
273 274
{
	while (!feof(in)) {
275 276 277
		if (table_cnt >= table_size) {
			table_size += 10000;
			table = realloc(table, sizeof(*table) * table_size);
Linus Torvalds's avatar
Linus Torvalds committed
278 279 280 281 282
			if (!table) {
				fprintf(stderr, "out of memory\n");
				exit (1);
			}
		}
283 284
		if (read_symbol(in, &table[table_cnt]) == 0) {
			table[table_cnt].start_pos = table_cnt;
285
			table_cnt++;
286
		}
Linus Torvalds's avatar
Linus Torvalds committed
287 288 289 290 291
	}
}

static void output_label(char *label)
{
292
	printf(".globl %s\n", label);
Linus Torvalds's avatar
Linus Torvalds committed
293
	printf("\tALGN\n");
294
	printf("%s:\n", label);
Linus Torvalds's avatar
Linus Torvalds committed
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323
}

/* uncompress a compressed symbol. When this function is called, the best table
 * might still be compressed itself, so the function needs to be recursive */
static int expand_symbol(unsigned char *data, int len, char *result)
{
	int c, rlen, total=0;

	while (len) {
		c = *data;
		/* if the table holds a single char that is the same as the one
		 * we are looking for, then end the search */
		if (best_table[c][0]==c && best_table_len[c]==1) {
			*result++ = c;
			total++;
		} else {
			/* if not, recurse and expand */
			rlen = expand_symbol(best_table[c], best_table_len[c], result);
			total += rlen;
			result += rlen;
		}
		data++;
		len--;
	}
	*result=0;

	return total;
}

324 325
static int symbol_absolute(struct sym_entry *s)
{
326
	return s->percpu_absolute;
327 328
}

329
static void write_src(void)
Linus Torvalds's avatar
Linus Torvalds committed
330
{
331
	unsigned int i, k, off;
Linus Torvalds's avatar
Linus Torvalds committed
332 333
	unsigned int best_idx[256];
	unsigned int *markers;
334
	char buf[KSYM_NAME_LEN];
Linus Torvalds's avatar
Linus Torvalds committed
335 336 337 338 339 340 341 342 343 344

	printf("#include <asm/types.h>\n");
	printf("#if BITS_PER_LONG == 64\n");
	printf("#define PTR .quad\n");
	printf("#define ALGN .align 8\n");
	printf("#else\n");
	printf("#define PTR .long\n");
	printf("#define ALGN .align 4\n");
	printf("#endif\n");

345
	printf("\t.section .rodata, \"a\"\n");
Linus Torvalds's avatar
Linus Torvalds committed
346

347 348 349 350 351 352 353 354 355 356 357 358
	/* Provide proper symbols relocatability by their relativeness
	 * to a fixed anchor point in the runtime image, either '_text'
	 * for absolute address tables, in which case the linker will
	 * emit the final addresses at build time. Otherwise, use the
	 * offset relative to the lowest value encountered of all relative
	 * symbols, and emit non-relocatable fixed offsets that will be fixed
	 * up at runtime.
	 *
	 * The symbol names cannot be used to construct normal symbol
	 * references as the list of symbols contains symbols that are
	 * declared static and are private to their .o files.  This prevents
	 * .tmp_kallsyms.o or any other object from referencing them.
359
	 */
360 361 362 363 364
	if (!base_relative)
		output_label("kallsyms_addresses");
	else
		output_label("kallsyms_offsets");

365
	for (i = 0; i < table_cnt; i++) {
366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388
		if (base_relative) {
			long long offset;
			int overflow;

			if (!absolute_percpu) {
				offset = table[i].addr - relative_base;
				overflow = (offset < 0 || offset > UINT_MAX);
			} else if (symbol_absolute(&table[i])) {
				offset = table[i].addr;
				overflow = (offset < 0 || offset > INT_MAX);
			} else {
				offset = relative_base - table[i].addr - 1;
				overflow = (offset < INT_MIN || offset >= 0);
			}
			if (overflow) {
				fprintf(stderr, "kallsyms failure: "
					"%s symbol value %#llx out of range in relative mode\n",
					symbol_absolute(&table[i]) ? "absolute" : "relative",
					table[i].addr);
				exit(EXIT_FAILURE);
			}
			printf("\t.long\t%#x\n", (int)offset);
		} else if (!symbol_absolute(&table[i])) {
389 390 391 392
			if (_text <= table[i].addr)
				printf("\tPTR\t_text + %#llx\n",
					table[i].addr - _text);
			else
393 394
				printf("\tPTR\t_text - %#llx\n",
					_text - table[i].addr);
395 396 397
		} else {
			printf("\tPTR\t%#llx\n", table[i].addr);
		}
Linus Torvalds's avatar
Linus Torvalds committed
398 399 400
	}
	printf("\n");

401 402 403 404 405 406
	if (base_relative) {
		output_label("kallsyms_relative_base");
		printf("\tPTR\t_text - %#llx\n", _text - relative_base);
		printf("\n");
	}

Linus Torvalds's avatar
Linus Torvalds committed
407
	output_label("kallsyms_num_syms");
408
	printf("\tPTR\t%u\n", table_cnt);
Linus Torvalds's avatar
Linus Torvalds committed
409 410 411 412
	printf("\n");

	/* table of offset markers, that give the offset in the compressed stream
	 * every 256 symbols */
413 414 415 416 417 418
	markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
	if (!markers) {
		fprintf(stderr, "kallsyms failure: "
			"unable to allocate required memory\n");
		exit(EXIT_FAILURE);
	}
Linus Torvalds's avatar
Linus Torvalds committed
419 420 421

	output_label("kallsyms_names");
	off = 0;
422 423 424
	for (i = 0; i < table_cnt; i++) {
		if ((i & 0xFF) == 0)
			markers[i >> 8] = off;
Linus Torvalds's avatar
Linus Torvalds committed
425 426 427 428 429 430 431 432 433 434 435

		printf("\t.byte 0x%02x", table[i].len);
		for (k = 0; k < table[i].len; k++)
			printf(", 0x%02x", table[i].sym[k]);
		printf("\n");

		off += table[i].len + 1;
	}
	printf("\n");

	output_label("kallsyms_markers");
436
	for (i = 0; i < ((table_cnt + 255) >> 8); i++)
Linus Torvalds's avatar
Linus Torvalds committed
437 438 439 440 441 442 443 444 445
		printf("\tPTR\t%d\n", markers[i]);
	printf("\n");

	free(markers);

	output_label("kallsyms_token_table");
	off = 0;
	for (i = 0; i < 256; i++) {
		best_idx[i] = off;
446
		expand_symbol(best_table[i], best_table_len[i], buf);
Linus Torvalds's avatar
Linus Torvalds committed
447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466
		printf("\t.asciz\t\"%s\"\n", buf);
		off += strlen(buf) + 1;
	}
	printf("\n");

	output_label("kallsyms_token_index");
	for (i = 0; i < 256; i++)
		printf("\t.short\t%d\n", best_idx[i]);
	printf("\n");
}


/* table lookup compression functions */

/* count all the possible tokens in a symbol */
static void learn_symbol(unsigned char *symbol, int len)
{
	int i;

	for (i = 0; i < len - 1; i++)
467
		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
Linus Torvalds's avatar
Linus Torvalds committed
468 469 470 471 472 473 474 475
}

/* decrease the count for all the possible tokens in a symbol */
static void forget_symbol(unsigned char *symbol, int len)
{
	int i;

	for (i = 0; i < len - 1; i++)
476
		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
Linus Torvalds's avatar
Linus Torvalds committed
477 478
}

479
/* remove all the invalid symbols from the table and do the initial token count */
Linus Torvalds's avatar
Linus Torvalds committed
480 481
static void build_initial_tok_table(void)
{
482
	unsigned int i, pos;
Linus Torvalds's avatar
Linus Torvalds committed
483

484 485
	pos = 0;
	for (i = 0; i < table_cnt; i++) {
Linus Torvalds's avatar
Linus Torvalds committed
486
		if ( symbol_valid(&table[i]) ) {
487 488 489 490
			if (pos != i)
				table[pos] = table[i];
			learn_symbol(table[pos].sym, table[pos].len);
			pos++;
Linus Torvalds's avatar
Linus Torvalds committed
491 492
		}
	}
493
	table_cnt = pos;
Linus Torvalds's avatar
Linus Torvalds committed
494 495
}

496 497 498 499 500 501 502 503 504 505 506
static void *find_token(unsigned char *str, int len, unsigned char *token)
{
	int i;

	for (i = 0; i < len - 1; i++) {
		if (str[i] == token[0] && str[i+1] == token[1])
			return &str[i];
	}
	return NULL;
}

Linus Torvalds's avatar
Linus Torvalds committed
507 508
/* replace a given token in all the valid symbols. Use the sampled symbols
 * to update the counts */
509
static void compress_symbols(unsigned char *str, int idx)
Linus Torvalds's avatar
Linus Torvalds committed
510
{
511 512
	unsigned int i, len, size;
	unsigned char *p1, *p2;
Linus Torvalds's avatar
Linus Torvalds committed
513

514
	for (i = 0; i < table_cnt; i++) {
Linus Torvalds's avatar
Linus Torvalds committed
515 516

		len = table[i].len;
517 518 519
		p1 = table[i].sym;

		/* find the token on the symbol */
520
		p2 = find_token(p1, len, str);
521 522 523 524 525 526
		if (!p2) continue;

		/* decrease the counts for this symbol's tokens */
		forget_symbol(table[i].sym, len);

		size = len;
Linus Torvalds's avatar
Linus Torvalds committed
527 528

		do {
529 530 531 532 533 534 535 536 537
			*p2 = idx;
			p2++;
			size -= (p2 - p1);
			memmove(p2, p2 + 1, size);
			p1 = p2;
			len--;

			if (size < 2) break;

Linus Torvalds's avatar
Linus Torvalds committed
538
			/* find the token on the symbol */
539
			p2 = find_token(p1, size, str);
Linus Torvalds's avatar
Linus Torvalds committed
540

541
		} while (p2);
Linus Torvalds's avatar
Linus Torvalds committed
542

543
		table[i].len = len;
Linus Torvalds's avatar
Linus Torvalds committed
544

545 546
		/* increase the counts for this symbol's new tokens */
		learn_symbol(table[i].sym, len);
Linus Torvalds's avatar
Linus Torvalds committed
547 548 549 550
	}
}

/* search the token with the maximum profit */
551
static int find_best_token(void)
Linus Torvalds's avatar
Linus Torvalds committed
552
{
553
	int i, best, bestprofit;
Linus Torvalds's avatar
Linus Torvalds committed
554 555

	bestprofit=-10000;
556
	best = 0;
Linus Torvalds's avatar
Linus Torvalds committed
557

558 559 560 561
	for (i = 0; i < 0x10000; i++) {
		if (token_profit[i] > bestprofit) {
			best = i;
			bestprofit = token_profit[i];
Linus Torvalds's avatar
Linus Torvalds committed
562 563 564 565 566 567 568 569
		}
	}
	return best;
}

/* this is the core of the algorithm: calculate the "best" table */
static void optimize_result(void)
{
570
	int i, best;
Linus Torvalds's avatar
Linus Torvalds committed
571 572 573 574 575 576 577 578 579

	/* using the '\0' symbol last allows compress_symbols to use standard
	 * fast string functions */
	for (i = 255; i >= 0; i--) {

		/* if this table slot is empty (it is not used by an actual
		 * original char code */
		if (!best_table_len[i]) {

580
			/* find the token with the best profit value */
Linus Torvalds's avatar
Linus Torvalds committed
581
			best = find_best_token();
582 583
			if (token_profit[best] == 0)
				break;
Linus Torvalds's avatar
Linus Torvalds committed
584 585

			/* place it in the "best" table */
586 587 588
			best_table_len[i] = 2;
			best_table[i][0] = best & 0xFF;
			best_table[i][1] = (best >> 8) & 0xFF;
Linus Torvalds's avatar
Linus Torvalds committed
589 590

			/* replace this token in all the valid symbols */
591
			compress_symbols(best_table[i], i);
Linus Torvalds's avatar
Linus Torvalds committed
592 593 594 595 596 597 598
		}
	}
}

/* start by placing the symbols that are actually used on the table */
static void insert_real_symbols_in_table(void)
{
599
	unsigned int i, j, c;
Linus Torvalds's avatar
Linus Torvalds committed
600 601 602 603

	memset(best_table, 0, sizeof(best_table));
	memset(best_table_len, 0, sizeof(best_table_len));

604 605 606 607 608
	for (i = 0; i < table_cnt; i++) {
		for (j = 0; j < table[i].len; j++) {
			c = table[i].sym[j];
			best_table[c][0]=c;
			best_table_len[c]=1;
Linus Torvalds's avatar
Linus Torvalds committed
609 610 611 612 613 614 615 616 617 618
		}
	}
}

static void optimize_token_table(void)
{
	build_initial_tok_table();

	insert_real_symbols_in_table();

619
	/* When valid symbol is not registered, exit to error */
620
	if (!table_cnt) {
621 622 623 624
		fprintf(stderr, "No valid symbol.\n");
		exit(1);
	}

Linus Torvalds's avatar
Linus Torvalds committed
625 626 627
	optimize_result();
}

628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666
/* guess for "linker script provide" symbol */
static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
{
	const char *symbol = (char *)se->sym + 1;
	int len = se->len - 1;

	if (len < 8)
		return 0;

	if (symbol[0] != '_' || symbol[1] != '_')
		return 0;

	/* __start_XXXXX */
	if (!memcmp(symbol + 2, "start_", 6))
		return 1;

	/* __stop_XXXXX */
	if (!memcmp(symbol + 2, "stop_", 5))
		return 1;

	/* __end_XXXXX */
	if (!memcmp(symbol + 2, "end_", 4))
		return 1;

	/* __XXXXX_start */
	if (!memcmp(symbol + len - 6, "_start", 6))
		return 1;

	/* __XXXXX_end */
	if (!memcmp(symbol + len - 4, "_end", 4))
		return 1;

	return 0;
}

static int prefix_underscores_count(const char *str)
{
	const char *tail = str;

667
	while (*tail == '_')
668 669 670 671 672
		tail++;

	return tail - str;
}

673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693
static int compare_symbols(const void *a, const void *b)
{
	const struct sym_entry *sa;
	const struct sym_entry *sb;
	int wa, wb;

	sa = a;
	sb = b;

	/* sort by address first */
	if (sa->addr > sb->addr)
		return 1;
	if (sa->addr < sb->addr)
		return -1;

	/* sort by "weakness" type */
	wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
	wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
	if (wa != wb)
		return wa - wb;

694 695 696 697 698 699 700 701 702 703 704 705
	/* sort by "linker script provide" type */
	wa = may_be_linker_script_provide_symbol(sa);
	wb = may_be_linker_script_provide_symbol(sb);
	if (wa != wb)
		return wa - wb;

	/* sort by the number of prefix underscores */
	wa = prefix_underscores_count((const char *)sa->sym + 1);
	wb = prefix_underscores_count((const char *)sb->sym + 1);
	if (wa != wb)
		return wa - wb;

706 707 708 709 710 711 712 713
	/* sort by initial order, so that other symbols are left undisturbed */
	return sa->start_pos - sb->start_pos;
}

static void sort_symbols(void)
{
	qsort(table, table_cnt, sizeof(struct sym_entry), compare_symbols);
}
Linus Torvalds's avatar
Linus Torvalds committed
714

715 716 717 718 719
static void make_percpus_absolute(void)
{
	unsigned int i;

	for (i = 0; i < table_cnt; i++)
720 721 722 723 724 725
		if (symbol_in_range(&table[i], &percpu_range, 1)) {
			/*
			 * Keep the 'A' override for percpu symbols to
			 * ensure consistent behavior compared to older
			 * versions of this tool.
			 */
726
			table[i].sym[0] = 'A';
727 728
			table[i].percpu_absolute = 1;
		}
729 730
}

731 732 733 734 735 736 737 738 739 740 741 742
/* find the minimum non-absolute symbol address */
static void record_relative_base(void)
{
	unsigned int i;

	relative_base = -1ULL;
	for (i = 0; i < table_cnt; i++)
		if (!symbol_absolute(&table[i]) &&
		    table[i].addr < relative_base)
			relative_base = table[i].addr;
}

743
int main(int argc, char **argv)
Linus Torvalds's avatar
Linus Torvalds committed
744
{
745 746 747 748 749
	if (argc >= 2) {
		int i;
		for (i = 1; i < argc; i++) {
			if(strcmp(argv[i], "--all-symbols") == 0)
				all_symbols = 1;
750 751
			else if (strcmp(argv[i], "--absolute-percpu") == 0)
				absolute_percpu = 1;
752
			else if (strcmp(argv[i], "--base-relative") == 0)
753 754
				base_relative = 1;
			else
755 756 757
				usage();
		}
	} else if (argc != 1)
Linus Torvalds's avatar
Linus Torvalds committed
758 759 760
		usage();

	read_map(stdin);
761 762
	if (absolute_percpu)
		make_percpus_absolute();
763 764
	if (base_relative)
		record_relative_base();
765 766
	sort_symbols();
	optimize_token_table();
Linus Torvalds's avatar
Linus Torvalds committed
767 768 769 770
	write_src();

	return 0;
}