xref: /openbmc/linux/scripts/kallsyms.c (revision 1dbb4f0235a450f22e518124cbf9b922802ce38f)
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: kallsyms [--all-symbols] [--absolute-percpu]
9  *                         [--base-relative] in.map > out.S
10  *
11  *      Table compression uses all the unused char codes on the symbols and
12  *  maps these to the most used substrings (tokens). For instance, it might
13  *  map char code 0xF7 to represent "write_" and then in every symbol where
14  *  "write_" appears it can be replaced by 0xF7, saving 5 bytes.
15  *      The used codes themselves are also placed in the table so that the
16  *  decompresion can work without "special cases".
17  *      Applied to kernel symbols, this usually produces a compression ratio
18  *  of about 50%.
19  *
20  */
21 
22 #include <getopt.h>
23 #include <stdbool.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <ctype.h>
28 #include <limits.h>
29 
30 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
31 
32 #define _stringify_1(x)	#x
33 #define _stringify(x)	_stringify_1(x)
34 
35 #define KSYM_NAME_LEN		512
36 
37 /*
38  * A substantially bigger size than the current maximum.
39  *
40  * It cannot be defined as an expression because it gets stringified
41  * for the fscanf() format string. Therefore, a _Static_assert() is
42  * used instead to maintain the relationship with KSYM_NAME_LEN.
43  */
44 #define KSYM_NAME_LEN_BUFFER	2048
45 _Static_assert(
46 	KSYM_NAME_LEN_BUFFER == KSYM_NAME_LEN * 4,
47 	"Please keep KSYM_NAME_LEN_BUFFER in sync with KSYM_NAME_LEN"
48 );
49 
50 struct sym_entry {
51 	unsigned long long addr;
52 	unsigned int len;
53 	unsigned int start_pos;
54 	unsigned int percpu_absolute;
55 	unsigned char sym[];
56 };
57 
58 struct addr_range {
59 	const char *start_sym, *end_sym;
60 	unsigned long long start, end;
61 };
62 
63 static unsigned long long _text;
64 static unsigned long long relative_base;
65 static struct addr_range text_ranges[] = {
66 	{ "_stext",     "_etext"     },
67 	{ "_sinittext", "_einittext" },
68 };
69 #define text_range_text     (&text_ranges[0])
70 #define text_range_inittext (&text_ranges[1])
71 
72 static struct addr_range percpu_range = {
73 	"__per_cpu_start", "__per_cpu_end", -1ULL, 0
74 };
75 
76 static struct sym_entry **table;
77 static unsigned int table_size, table_cnt;
78 static int all_symbols;
79 static int absolute_percpu;
80 static int base_relative;
81 
82 static int token_profit[0x10000];
83 
84 /* the table that holds the result of the compression */
85 static unsigned char best_table[256][2];
86 static unsigned char best_table_len[256];
87 
88 
89 static void usage(void)
90 {
91 	fprintf(stderr, "Usage: kallsyms [--all-symbols] [--absolute-percpu] "
92 			"[--base-relative] in.map > out.S\n");
93 	exit(1);
94 }
95 
96 static char *sym_name(const struct sym_entry *s)
97 {
98 	return (char *)s->sym + 1;
99 }
100 
101 static bool is_ignored_symbol(const char *name, char type)
102 {
103 	/* Symbol names that exactly match to the following are ignored.*/
104 	static const char * const ignored_symbols[] = {
105 		/*
106 		 * Symbols which vary between passes. Passes 1 and 2 must have
107 		 * identical symbol lists. The kallsyms_* symbols below are
108 		 * only added after pass 1, they would be included in pass 2
109 		 * when --all-symbols is specified so exclude them to get a
110 		 * stable symbol list.
111 		 */
112 		"kallsyms_addresses",
113 		"kallsyms_offsets",
114 		"kallsyms_relative_base",
115 		"kallsyms_num_syms",
116 		"kallsyms_names",
117 		"kallsyms_markers",
118 		"kallsyms_token_table",
119 		"kallsyms_token_index",
120 		/* Exclude linker generated symbols which vary between passes */
121 		"_SDA_BASE_",		/* ppc */
122 		"_SDA2_BASE_",		/* ppc */
123 		NULL
124 	};
125 
126 	/* Symbol names that begin with the following are ignored.*/
127 	static const char * const ignored_prefixes[] = {
128 		"__efistub_",		/* arm64 EFI stub namespace */
129 		"__kvm_nvhe_$",		/* arm64 local symbols in non-VHE KVM namespace */
130 		"__kvm_nvhe_.L",	/* arm64 local symbols in non-VHE KVM namespace */
131 		"__AArch64ADRPThunk_",	/* arm64 lld */
132 		"__ARMV5PILongThunk_",	/* arm lld */
133 		"__ARMV7PILongThunk_",
134 		"__ThumbV7PILongThunk_",
135 		"__LA25Thunk_",		/* mips lld */
136 		"__microLA25Thunk_",
137 		"__kcfi_typeid_",	/* CFI type identifiers */
138 		NULL
139 	};
140 
141 	/* Symbol names that end with the following are ignored.*/
142 	static const char * const ignored_suffixes[] = {
143 		"_from_arm",		/* arm */
144 		"_from_thumb",		/* arm */
145 		"_veneer",		/* arm */
146 		NULL
147 	};
148 
149 	/* Symbol names that contain the following are ignored.*/
150 	static const char * const ignored_matches[] = {
151 		".long_branch.",	/* ppc stub */
152 		".plt_branch.",		/* ppc stub */
153 		NULL
154 	};
155 
156 	const char * const *p;
157 
158 	for (p = ignored_symbols; *p; p++)
159 		if (!strcmp(name, *p))
160 			return true;
161 
162 	for (p = ignored_prefixes; *p; p++)
163 		if (!strncmp(name, *p, strlen(*p)))
164 			return true;
165 
166 	for (p = ignored_suffixes; *p; p++) {
167 		int l = strlen(name) - strlen(*p);
168 
169 		if (l >= 0 && !strcmp(name + l, *p))
170 			return true;
171 	}
172 
173 	for (p = ignored_matches; *p; p++) {
174 		if (strstr(name, *p))
175 			return true;
176 	}
177 
178 	if (type == 'U' || type == 'u')
179 		return true;
180 	/* exclude debugging symbols */
181 	if (type == 'N' || type == 'n')
182 		return true;
183 
184 	if (toupper(type) == 'A') {
185 		/* Keep these useful absolute symbols */
186 		if (strcmp(name, "__kernel_syscall_via_break") &&
187 		    strcmp(name, "__kernel_syscall_via_epc") &&
188 		    strcmp(name, "__kernel_sigtramp") &&
189 		    strcmp(name, "__gp"))
190 			return true;
191 	}
192 
193 	return false;
194 }
195 
196 static void check_symbol_range(const char *sym, unsigned long long addr,
197 			       struct addr_range *ranges, int entries)
198 {
199 	size_t i;
200 	struct addr_range *ar;
201 
202 	for (i = 0; i < entries; ++i) {
203 		ar = &ranges[i];
204 
205 		if (strcmp(sym, ar->start_sym) == 0) {
206 			ar->start = addr;
207 			return;
208 		} else if (strcmp(sym, ar->end_sym) == 0) {
209 			ar->end = addr;
210 			return;
211 		}
212 	}
213 }
214 
215 static struct sym_entry *read_symbol(FILE *in)
216 {
217 	char name[KSYM_NAME_LEN_BUFFER+1], type;
218 	unsigned long long addr;
219 	unsigned int len;
220 	struct sym_entry *sym;
221 	int rc;
222 
223 	rc = fscanf(in, "%llx %c %" _stringify(KSYM_NAME_LEN_BUFFER) "s\n", &addr, &type, name);
224 	if (rc != 3) {
225 		if (rc != EOF && fgets(name, ARRAY_SIZE(name), in) == NULL)
226 			fprintf(stderr, "Read error or end of file.\n");
227 		return NULL;
228 	}
229 	if (strlen(name) >= KSYM_NAME_LEN) {
230 		fprintf(stderr, "Symbol %s too long for kallsyms (%zu >= %d).\n"
231 				"Please increase KSYM_NAME_LEN both in kernel and kallsyms.c\n",
232 			name, strlen(name), KSYM_NAME_LEN);
233 		return NULL;
234 	}
235 
236 	if (strcmp(name, "_text") == 0)
237 		_text = addr;
238 
239 	/* Ignore most absolute/undefined (?) symbols. */
240 	if (is_ignored_symbol(name, type))
241 		return NULL;
242 
243 	check_symbol_range(name, addr, text_ranges, ARRAY_SIZE(text_ranges));
244 	check_symbol_range(name, addr, &percpu_range, 1);
245 
246 	/* include the type field in the symbol name, so that it gets
247 	 * compressed together */
248 
249 	len = strlen(name) + 1;
250 
251 	sym = malloc(sizeof(*sym) + len + 1);
252 	if (!sym) {
253 		fprintf(stderr, "kallsyms failure: "
254 			"unable to allocate required amount of memory\n");
255 		exit(EXIT_FAILURE);
256 	}
257 	sym->addr = addr;
258 	sym->len = len;
259 	sym->sym[0] = type;
260 	strcpy(sym_name(sym), name);
261 	sym->percpu_absolute = 0;
262 
263 	return sym;
264 }
265 
266 static int symbol_in_range(const struct sym_entry *s,
267 			   const struct addr_range *ranges, int entries)
268 {
269 	size_t i;
270 	const struct addr_range *ar;
271 
272 	for (i = 0; i < entries; ++i) {
273 		ar = &ranges[i];
274 
275 		if (s->addr >= ar->start && s->addr <= ar->end)
276 			return 1;
277 	}
278 
279 	return 0;
280 }
281 
282 static int symbol_valid(const struct sym_entry *s)
283 {
284 	const char *name = sym_name(s);
285 
286 	/* if --all-symbols is not specified, then symbols outside the text
287 	 * and inittext sections are discarded */
288 	if (!all_symbols) {
289 		if (symbol_in_range(s, text_ranges,
290 				    ARRAY_SIZE(text_ranges)) == 0)
291 			return 0;
292 		/* Corner case.  Discard any symbols with the same value as
293 		 * _etext _einittext; they can move between pass 1 and 2 when
294 		 * the kallsyms data are added.  If these symbols move then
295 		 * they may get dropped in pass 2, which breaks the kallsyms
296 		 * rules.
297 		 */
298 		if ((s->addr == text_range_text->end &&
299 		     strcmp(name, text_range_text->end_sym)) ||
300 		    (s->addr == text_range_inittext->end &&
301 		     strcmp(name, text_range_inittext->end_sym)))
302 			return 0;
303 	}
304 
305 	return 1;
306 }
307 
308 /* remove all the invalid symbols from the table */
309 static void shrink_table(void)
310 {
311 	unsigned int i, pos;
312 
313 	pos = 0;
314 	for (i = 0; i < table_cnt; i++) {
315 		if (symbol_valid(table[i])) {
316 			if (pos != i)
317 				table[pos] = table[i];
318 			pos++;
319 		} else {
320 			free(table[i]);
321 		}
322 	}
323 	table_cnt = pos;
324 
325 	/* When valid symbol is not registered, exit to error */
326 	if (!table_cnt) {
327 		fprintf(stderr, "No valid symbol.\n");
328 		exit(1);
329 	}
330 }
331 
332 static void read_map(const char *in)
333 {
334 	FILE *fp;
335 	struct sym_entry *sym;
336 
337 	fp = fopen(in, "r");
338 	if (!fp) {
339 		perror(in);
340 		exit(1);
341 	}
342 
343 	while (!feof(fp)) {
344 		sym = read_symbol(fp);
345 		if (!sym)
346 			continue;
347 
348 		sym->start_pos = table_cnt;
349 
350 		if (table_cnt >= table_size) {
351 			table_size += 10000;
352 			table = realloc(table, sizeof(*table) * table_size);
353 			if (!table) {
354 				fprintf(stderr, "out of memory\n");
355 				fclose(fp);
356 				exit (1);
357 			}
358 		}
359 
360 		table[table_cnt++] = sym;
361 	}
362 
363 	fclose(fp);
364 }
365 
366 static void output_label(const char *label)
367 {
368 	printf(".globl %s\n", label);
369 	printf("\tALGN\n");
370 	printf("%s:\n", label);
371 }
372 
373 /* Provide proper symbols relocatability by their '_text' relativeness. */
374 static void output_address(unsigned long long addr)
375 {
376 	if (_text <= addr)
377 		printf("\tPTR\t_text + %#llx\n", addr - _text);
378 	else
379 		printf("\tPTR\t_text - %#llx\n", _text - addr);
380 }
381 
382 /* uncompress a compressed symbol. When this function is called, the best table
383  * might still be compressed itself, so the function needs to be recursive */
384 static int expand_symbol(const unsigned char *data, int len, char *result)
385 {
386 	int c, rlen, total=0;
387 
388 	while (len) {
389 		c = *data;
390 		/* if the table holds a single char that is the same as the one
391 		 * we are looking for, then end the search */
392 		if (best_table[c][0]==c && best_table_len[c]==1) {
393 			*result++ = c;
394 			total++;
395 		} else {
396 			/* if not, recurse and expand */
397 			rlen = expand_symbol(best_table[c], best_table_len[c], result);
398 			total += rlen;
399 			result += rlen;
400 		}
401 		data++;
402 		len--;
403 	}
404 	*result=0;
405 
406 	return total;
407 }
408 
409 static int symbol_absolute(const struct sym_entry *s)
410 {
411 	return s->percpu_absolute;
412 }
413 
414 static void write_src(void)
415 {
416 	unsigned int i, k, off;
417 	unsigned int best_idx[256];
418 	unsigned int *markers;
419 	char buf[KSYM_NAME_LEN];
420 
421 	printf("#include <asm/bitsperlong.h>\n");
422 	printf("#if BITS_PER_LONG == 64\n");
423 	printf("#define PTR .quad\n");
424 	printf("#define ALGN .balign 8\n");
425 	printf("#else\n");
426 	printf("#define PTR .long\n");
427 	printf("#define ALGN .balign 4\n");
428 	printf("#endif\n");
429 
430 	printf("\t.section .rodata, \"a\"\n");
431 
432 	if (!base_relative)
433 		output_label("kallsyms_addresses");
434 	else
435 		output_label("kallsyms_offsets");
436 
437 	for (i = 0; i < table_cnt; i++) {
438 		if (base_relative) {
439 			/*
440 			 * Use the offset relative to the lowest value
441 			 * encountered of all relative symbols, and emit
442 			 * non-relocatable fixed offsets that will be fixed
443 			 * up at runtime.
444 			 */
445 
446 			long long offset;
447 			int overflow;
448 
449 			if (!absolute_percpu) {
450 				offset = table[i]->addr - relative_base;
451 				overflow = (offset < 0 || offset > UINT_MAX);
452 			} else if (symbol_absolute(table[i])) {
453 				offset = table[i]->addr;
454 				overflow = (offset < 0 || offset > INT_MAX);
455 			} else {
456 				offset = relative_base - table[i]->addr - 1;
457 				overflow = (offset < INT_MIN || offset >= 0);
458 			}
459 			if (overflow) {
460 				fprintf(stderr, "kallsyms failure: "
461 					"%s symbol value %#llx out of range in relative mode\n",
462 					symbol_absolute(table[i]) ? "absolute" : "relative",
463 					table[i]->addr);
464 				exit(EXIT_FAILURE);
465 			}
466 			printf("\t.long\t%#x\n", (int)offset);
467 		} else if (!symbol_absolute(table[i])) {
468 			output_address(table[i]->addr);
469 		} else {
470 			printf("\tPTR\t%#llx\n", table[i]->addr);
471 		}
472 	}
473 	printf("\n");
474 
475 	if (base_relative) {
476 		output_label("kallsyms_relative_base");
477 		output_address(relative_base);
478 		printf("\n");
479 	}
480 
481 	output_label("kallsyms_num_syms");
482 	printf("\t.long\t%u\n", table_cnt);
483 	printf("\n");
484 
485 	/* table of offset markers, that give the offset in the compressed stream
486 	 * every 256 symbols */
487 	markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
488 	if (!markers) {
489 		fprintf(stderr, "kallsyms failure: "
490 			"unable to allocate required memory\n");
491 		exit(EXIT_FAILURE);
492 	}
493 
494 	output_label("kallsyms_names");
495 	off = 0;
496 	for (i = 0; i < table_cnt; i++) {
497 		if ((i & 0xFF) == 0)
498 			markers[i >> 8] = off;
499 
500 		/* There cannot be any symbol of length zero. */
501 		if (table[i]->len == 0) {
502 			fprintf(stderr, "kallsyms failure: "
503 				"unexpected zero symbol length\n");
504 			exit(EXIT_FAILURE);
505 		}
506 
507 		/* Only lengths that fit in up-to-two-byte ULEB128 are supported. */
508 		if (table[i]->len > 0x3FFF) {
509 			fprintf(stderr, "kallsyms failure: "
510 				"unexpected huge symbol length\n");
511 			exit(EXIT_FAILURE);
512 		}
513 
514 		/* Encode length with ULEB128. */
515 		if (table[i]->len <= 0x7F) {
516 			/* Most symbols use a single byte for the length. */
517 			printf("\t.byte 0x%02x", table[i]->len);
518 			off += table[i]->len + 1;
519 		} else {
520 			/* "Big" symbols use two bytes. */
521 			printf("\t.byte 0x%02x, 0x%02x",
522 				(table[i]->len & 0x7F) | 0x80,
523 				(table[i]->len >> 7) & 0x7F);
524 			off += table[i]->len + 2;
525 		}
526 		for (k = 0; k < table[i]->len; k++)
527 			printf(", 0x%02x", table[i]->sym[k]);
528 		printf("\n");
529 	}
530 	printf("\n");
531 
532 	output_label("kallsyms_markers");
533 	for (i = 0; i < ((table_cnt + 255) >> 8); i++)
534 		printf("\t.long\t%u\n", markers[i]);
535 	printf("\n");
536 
537 	free(markers);
538 
539 	output_label("kallsyms_token_table");
540 	off = 0;
541 	for (i = 0; i < 256; i++) {
542 		best_idx[i] = off;
543 		expand_symbol(best_table[i], best_table_len[i], buf);
544 		printf("\t.asciz\t\"%s\"\n", buf);
545 		off += strlen(buf) + 1;
546 	}
547 	printf("\n");
548 
549 	output_label("kallsyms_token_index");
550 	for (i = 0; i < 256; i++)
551 		printf("\t.short\t%d\n", best_idx[i]);
552 	printf("\n");
553 }
554 
555 
556 /* table lookup compression functions */
557 
558 /* count all the possible tokens in a symbol */
559 static void learn_symbol(const unsigned char *symbol, int len)
560 {
561 	int i;
562 
563 	for (i = 0; i < len - 1; i++)
564 		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
565 }
566 
567 /* decrease the count for all the possible tokens in a symbol */
568 static void forget_symbol(const unsigned char *symbol, int len)
569 {
570 	int i;
571 
572 	for (i = 0; i < len - 1; i++)
573 		token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
574 }
575 
576 /* do the initial token count */
577 static void build_initial_tok_table(void)
578 {
579 	unsigned int i;
580 
581 	for (i = 0; i < table_cnt; i++)
582 		learn_symbol(table[i]->sym, table[i]->len);
583 }
584 
585 static unsigned char *find_token(unsigned char *str, int len,
586 				 const unsigned char *token)
587 {
588 	int i;
589 
590 	for (i = 0; i < len - 1; i++) {
591 		if (str[i] == token[0] && str[i+1] == token[1])
592 			return &str[i];
593 	}
594 	return NULL;
595 }
596 
597 /* replace a given token in all the valid symbols. Use the sampled symbols
598  * to update the counts */
599 static void compress_symbols(const unsigned char *str, int idx)
600 {
601 	unsigned int i, len, size;
602 	unsigned char *p1, *p2;
603 
604 	for (i = 0; i < table_cnt; i++) {
605 
606 		len = table[i]->len;
607 		p1 = table[i]->sym;
608 
609 		/* find the token on the symbol */
610 		p2 = find_token(p1, len, str);
611 		if (!p2) continue;
612 
613 		/* decrease the counts for this symbol's tokens */
614 		forget_symbol(table[i]->sym, len);
615 
616 		size = len;
617 
618 		do {
619 			*p2 = idx;
620 			p2++;
621 			size -= (p2 - p1);
622 			memmove(p2, p2 + 1, size);
623 			p1 = p2;
624 			len--;
625 
626 			if (size < 2) break;
627 
628 			/* find the token on the symbol */
629 			p2 = find_token(p1, size, str);
630 
631 		} while (p2);
632 
633 		table[i]->len = len;
634 
635 		/* increase the counts for this symbol's new tokens */
636 		learn_symbol(table[i]->sym, len);
637 	}
638 }
639 
640 /* search the token with the maximum profit */
641 static int find_best_token(void)
642 {
643 	int i, best, bestprofit;
644 
645 	bestprofit=-10000;
646 	best = 0;
647 
648 	for (i = 0; i < 0x10000; i++) {
649 		if (token_profit[i] > bestprofit) {
650 			best = i;
651 			bestprofit = token_profit[i];
652 		}
653 	}
654 	return best;
655 }
656 
657 /* this is the core of the algorithm: calculate the "best" table */
658 static void optimize_result(void)
659 {
660 	int i, best;
661 
662 	/* using the '\0' symbol last allows compress_symbols to use standard
663 	 * fast string functions */
664 	for (i = 255; i >= 0; i--) {
665 
666 		/* if this table slot is empty (it is not used by an actual
667 		 * original char code */
668 		if (!best_table_len[i]) {
669 
670 			/* find the token with the best profit value */
671 			best = find_best_token();
672 			if (token_profit[best] == 0)
673 				break;
674 
675 			/* place it in the "best" table */
676 			best_table_len[i] = 2;
677 			best_table[i][0] = best & 0xFF;
678 			best_table[i][1] = (best >> 8) & 0xFF;
679 
680 			/* replace this token in all the valid symbols */
681 			compress_symbols(best_table[i], i);
682 		}
683 	}
684 }
685 
686 /* start by placing the symbols that are actually used on the table */
687 static void insert_real_symbols_in_table(void)
688 {
689 	unsigned int i, j, c;
690 
691 	for (i = 0; i < table_cnt; i++) {
692 		for (j = 0; j < table[i]->len; j++) {
693 			c = table[i]->sym[j];
694 			best_table[c][0]=c;
695 			best_table_len[c]=1;
696 		}
697 	}
698 }
699 
700 static void optimize_token_table(void)
701 {
702 	build_initial_tok_table();
703 
704 	insert_real_symbols_in_table();
705 
706 	optimize_result();
707 }
708 
709 /* guess for "linker script provide" symbol */
710 static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
711 {
712 	const char *symbol = sym_name(se);
713 	int len = se->len - 1;
714 
715 	if (len < 8)
716 		return 0;
717 
718 	if (symbol[0] != '_' || symbol[1] != '_')
719 		return 0;
720 
721 	/* __start_XXXXX */
722 	if (!memcmp(symbol + 2, "start_", 6))
723 		return 1;
724 
725 	/* __stop_XXXXX */
726 	if (!memcmp(symbol + 2, "stop_", 5))
727 		return 1;
728 
729 	/* __end_XXXXX */
730 	if (!memcmp(symbol + 2, "end_", 4))
731 		return 1;
732 
733 	/* __XXXXX_start */
734 	if (!memcmp(symbol + len - 6, "_start", 6))
735 		return 1;
736 
737 	/* __XXXXX_end */
738 	if (!memcmp(symbol + len - 4, "_end", 4))
739 		return 1;
740 
741 	return 0;
742 }
743 
744 static int compare_symbols(const void *a, const void *b)
745 {
746 	const struct sym_entry *sa = *(const struct sym_entry **)a;
747 	const struct sym_entry *sb = *(const struct sym_entry **)b;
748 	int wa, wb;
749 
750 	/* sort by address first */
751 	if (sa->addr > sb->addr)
752 		return 1;
753 	if (sa->addr < sb->addr)
754 		return -1;
755 
756 	/* sort by "weakness" type */
757 	wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
758 	wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
759 	if (wa != wb)
760 		return wa - wb;
761 
762 	/* sort by "linker script provide" type */
763 	wa = may_be_linker_script_provide_symbol(sa);
764 	wb = may_be_linker_script_provide_symbol(sb);
765 	if (wa != wb)
766 		return wa - wb;
767 
768 	/* sort by the number of prefix underscores */
769 	wa = strspn(sym_name(sa), "_");
770 	wb = strspn(sym_name(sb), "_");
771 	if (wa != wb)
772 		return wa - wb;
773 
774 	/* sort by initial order, so that other symbols are left undisturbed */
775 	return sa->start_pos - sb->start_pos;
776 }
777 
778 static void sort_symbols(void)
779 {
780 	qsort(table, table_cnt, sizeof(table[0]), compare_symbols);
781 }
782 
783 static void make_percpus_absolute(void)
784 {
785 	unsigned int i;
786 
787 	for (i = 0; i < table_cnt; i++)
788 		if (symbol_in_range(table[i], &percpu_range, 1)) {
789 			/*
790 			 * Keep the 'A' override for percpu symbols to
791 			 * ensure consistent behavior compared to older
792 			 * versions of this tool.
793 			 */
794 			table[i]->sym[0] = 'A';
795 			table[i]->percpu_absolute = 1;
796 		}
797 }
798 
799 /* find the minimum non-absolute symbol address */
800 static void record_relative_base(void)
801 {
802 	unsigned int i;
803 
804 	for (i = 0; i < table_cnt; i++)
805 		if (!symbol_absolute(table[i])) {
806 			/*
807 			 * The table is sorted by address.
808 			 * Take the first non-absolute symbol value.
809 			 */
810 			relative_base = table[i]->addr;
811 			return;
812 		}
813 }
814 
815 int main(int argc, char **argv)
816 {
817 	while (1) {
818 		static struct option long_options[] = {
819 			{"all-symbols",     no_argument, &all_symbols,     1},
820 			{"absolute-percpu", no_argument, &absolute_percpu, 1},
821 			{"base-relative",   no_argument, &base_relative,   1},
822 			{},
823 		};
824 
825 		int c = getopt_long(argc, argv, "", long_options, NULL);
826 
827 		if (c == -1)
828 			break;
829 		if (c != 0)
830 			usage();
831 	}
832 
833 	if (optind >= argc)
834 		usage();
835 
836 	read_map(argv[optind]);
837 	shrink_table();
838 	if (absolute_percpu)
839 		make_percpus_absolute();
840 	sort_symbols();
841 	if (base_relative)
842 		record_relative_base();
843 	optimize_token_table();
844 	write_src();
845 
846 	return 0;
847 }
848