projects/linux·blob 4a95bc12 · refs

1414 lines · 31.7 KiB

1// SPDX-License-Identifier: GPL-2.0-only
2/*
3 * sorttable.c: Sort the kernel's table
4 *
5 * Added ORC unwind tables sort support and other updates:
6 * Copyright (C) 1999-2019 Alibaba Group Holding Limited. by:
7 * Shile Zhang <[email protected]>
8 *
9 * Copyright 2011 - 2012 Cavium, Inc.
10 *
11 * Based on code taken from recortmcount.c which is:
12 *
13 * Copyright 2009 John F. Reiser <[email protected]>. All rights reserved.
14 *
15 * Restructured to fit Linux format, as well as other updates:
16 * Copyright 2010 Steven Rostedt <[email protected]>, Red Hat Inc.
17 */
18
19/*
20 * Strategy: alter the vmlinux file in-place.
21 */
22
23#include <sys/types.h>
24#include <sys/mman.h>
25#include <sys/stat.h>
26#include <getopt.h>
27#include <elf.h>
28#include <fcntl.h>
29#include <stdio.h>
30#include <stdlib.h>
31#include <stdbool.h>
32#include <string.h>
33#include <unistd.h>
34#include <errno.h>
35#include <pthread.h>
36
37#include <tools/be_byteshift.h>
38#include <tools/le_byteshift.h>
39
40#ifndef EM_ARCOMPACT
41#define EM_ARCOMPACT 93
42#endif
43
44#ifndef EM_XTENSA
45#define EM_XTENSA 94
46#endif
47
48#ifndef EM_AARCH64
49#define EM_AARCH64 183
50#endif
51
52#ifndef EM_MICROBLAZE
53#define EM_MICROBLAZE 189
54#endif
55
56#ifndef EM_ARCV2
57#define EM_ARCV2 195
58#endif
59
60#ifndef EM_RISCV
61#define EM_RISCV 243
62#endif
63
64#ifndef EM_LOONGARCH
65#define EM_LOONGARCH 258
66#endif
67
68typedef union {
69 Elf32_Ehdr e32;
70 Elf64_Ehdr e64;
71} Elf_Ehdr;
72
73typedef union {
74 Elf32_Shdr e32;
75 Elf64_Shdr e64;
76} Elf_Shdr;
77
78typedef union {
79 Elf32_Sym e32;
80 Elf64_Sym e64;
81} Elf_Sym;
82
83typedef union {
84 Elf32_Rela e32;
85 Elf64_Rela e64;
86} Elf_Rela;
87
88static uint32_t (*r)(const uint32_t *);
89static uint16_t (*r2)(const uint16_t *);
90static uint64_t (*r8)(const uint64_t *);
91static void (*w)(uint32_t, uint32_t *);
92static void (*w8)(uint64_t, uint64_t *);
93typedef void (*table_sort_t)(char *, int);
94
95static struct elf_funcs {
96 int (*compare_extable)(const void *a, const void *b);
97 uint64_t (*ehdr_shoff)(Elf_Ehdr *ehdr);
98 uint16_t (*ehdr_shstrndx)(Elf_Ehdr *ehdr);
99 uint16_t (*ehdr_shentsize)(Elf_Ehdr *ehdr);
100 uint16_t (*ehdr_shnum)(Elf_Ehdr *ehdr);
101 uint64_t (*shdr_addr)(Elf_Shdr *shdr);
102 uint64_t (*shdr_offset)(Elf_Shdr *shdr);
103 uint64_t (*shdr_size)(Elf_Shdr *shdr);
104 uint64_t (*shdr_entsize)(Elf_Shdr *shdr);
105 uint32_t (*shdr_link)(Elf_Shdr *shdr);
106 uint32_t (*shdr_name)(Elf_Shdr *shdr);
107 uint32_t (*shdr_type)(Elf_Shdr *shdr);
108 uint8_t (*sym_type)(Elf_Sym *sym);
109 uint32_t (*sym_name)(Elf_Sym *sym);
110 uint64_t (*sym_value)(Elf_Sym *sym);
111 uint16_t (*sym_shndx)(Elf_Sym *sym);
112 uint64_t (*rela_offset)(Elf_Rela *rela);
113 uint64_t (*rela_info)(Elf_Rela *rela);
114 uint64_t (*rela_addend)(Elf_Rela *rela);
115 void (*rela_write_addend)(Elf_Rela *rela, uint64_t val);
116} e;
117
118static uint64_t ehdr64_shoff(Elf_Ehdr *ehdr)
119{
120 return r8(&ehdr->e64.e_shoff);
121}
122
123static uint64_t ehdr32_shoff(Elf_Ehdr *ehdr)
124{
125 return r(&ehdr->e32.e_shoff);
126}
127
128static uint64_t ehdr_shoff(Elf_Ehdr *ehdr)
129{
130 return e.ehdr_shoff(ehdr);
131}
132
133#define EHDR_HALF(fn_name) \
134static uint16_t ehdr64_##fn_name(Elf_Ehdr *ehdr) \
135{ \
136 return r2(&ehdr->e64.e_##fn_name); \
137} \
138 \
139static uint16_t ehdr32_##fn_name(Elf_Ehdr *ehdr) \
140{ \
141 return r2(&ehdr->e32.e_##fn_name); \
142} \
143 \
144static uint16_t ehdr_##fn_name(Elf_Ehdr *ehdr) \
145{ \
146 return e.ehdr_##fn_name(ehdr); \
147}
148
149EHDR_HALF(shentsize)
150EHDR_HALF(shstrndx)
151EHDR_HALF(shnum)
152
153#define SHDR_WORD(fn_name) \
154static uint32_t shdr64_##fn_name(Elf_Shdr *shdr) \
155{ \
156 return r(&shdr->e64.sh_##fn_name); \
157} \
158 \
159static uint32_t shdr32_##fn_name(Elf_Shdr *shdr) \
160{ \
161 return r(&shdr->e32.sh_##fn_name); \
162} \
163 \
164static uint32_t shdr_##fn_name(Elf_Shdr *shdr) \
165{ \
166 return e.shdr_##fn_name(shdr); \
167}
168
169#define SHDR_ADDR(fn_name) \
170static uint64_t shdr64_##fn_name(Elf_Shdr *shdr) \
171{ \
172 return r8(&shdr->e64.sh_##fn_name); \
173} \
174 \
175static uint64_t shdr32_##fn_name(Elf_Shdr *shdr) \
176{ \
177 return r(&shdr->e32.sh_##fn_name); \
178} \
179 \
180static uint64_t shdr_##fn_name(Elf_Shdr *shdr) \
181{ \
182 return e.shdr_##fn_name(shdr); \
183}
184
185#define SHDR_WORD(fn_name) \
186static uint32_t shdr64_##fn_name(Elf_Shdr *shdr) \
187{ \
188 return r(&shdr->e64.sh_##fn_name); \
189} \
190 \
191static uint32_t shdr32_##fn_name(Elf_Shdr *shdr) \
192{ \
193 return r(&shdr->e32.sh_##fn_name); \
194} \
195static uint32_t shdr_##fn_name(Elf_Shdr *shdr) \
196{ \
197 return e.shdr_##fn_name(shdr); \
198}
199
200SHDR_ADDR(addr)
201SHDR_ADDR(offset)
202SHDR_ADDR(size)
203SHDR_ADDR(entsize)
204
205SHDR_WORD(link)
206SHDR_WORD(name)
207SHDR_WORD(type)
208
209#define SYM_ADDR(fn_name) \
210static uint64_t sym64_##fn_name(Elf_Sym *sym) \
211{ \
212 return r8(&sym->e64.st_##fn_name); \
213} \
214 \
215static uint64_t sym32_##fn_name(Elf_Sym *sym) \
216{ \
217 return r(&sym->e32.st_##fn_name); \
218} \
219 \
220static uint64_t sym_##fn_name(Elf_Sym *sym) \
221{ \
222 return e.sym_##fn_name(sym); \
223}
224
225#define SYM_WORD(fn_name) \
226static uint32_t sym64_##fn_name(Elf_Sym *sym) \
227{ \
228 return r(&sym->e64.st_##fn_name); \
229} \
230 \
231static uint32_t sym32_##fn_name(Elf_Sym *sym) \
232{ \
233 return r(&sym->e32.st_##fn_name); \
234} \
235 \
236static uint32_t sym_##fn_name(Elf_Sym *sym) \
237{ \
238 return e.sym_##fn_name(sym); \
239}
240
241#define SYM_HALF(fn_name) \
242static uint16_t sym64_##fn_name(Elf_Sym *sym) \
243{ \
244 return r2(&sym->e64.st_##fn_name); \
245} \
246 \
247static uint16_t sym32_##fn_name(Elf_Sym *sym) \
248{ \
249 return r2(&sym->e32.st_##fn_name); \
250} \
251 \
252static uint16_t sym_##fn_name(Elf_Sym *sym) \
253{ \
254 return e.sym_##fn_name(sym); \
255}
256
257static uint8_t sym64_type(Elf_Sym *sym)
258{
259 return ELF64_ST_TYPE(sym->e64.st_info);
260}
261
262static uint8_t sym32_type(Elf_Sym *sym)
263{
264 return ELF32_ST_TYPE(sym->e32.st_info);
265}
266
267static uint8_t sym_type(Elf_Sym *sym)
268{
269 return e.sym_type(sym);
270}
271
272SYM_ADDR(value)
273SYM_WORD(name)
274SYM_HALF(shndx)
275
276#define __maybe_unused __attribute__((__unused__))
277
278#define RELA_ADDR(fn_name) \
279static uint64_t rela64_##fn_name(Elf_Rela *rela) \
280{ \
281 return r8((uint64_t *)&rela->e64.r_##fn_name); \
282} \
283 \
284static uint64_t rela32_##fn_name(Elf_Rela *rela) \
285{ \
286 return r((uint32_t *)&rela->e32.r_##fn_name); \
287} \
288 \
289static uint64_t __maybe_unused rela_##fn_name(Elf_Rela *rela) \
290{ \
291 return e.rela_##fn_name(rela); \
292}
293
294RELA_ADDR(offset)
295RELA_ADDR(info)
296RELA_ADDR(addend)
297
298static void rela64_write_addend(Elf_Rela *rela, uint64_t val)
299{
300 w8(val, (uint64_t *)&rela->e64.r_addend);
301}
302
303static void rela32_write_addend(Elf_Rela *rela, uint64_t val)
304{
305 w(val, (uint32_t *)&rela->e32.r_addend);
306}
307
308/*
309 * Get the whole file as a programming convenience in order to avoid
310 * malloc+lseek+read+free of many pieces. If successful, then mmap
311 * avoids copying unused pieces; else just read the whole file.
312 * Open for both read and write.
313 */
314static void *mmap_file(char const *fname, size_t *size)
315{
316 int fd;
317 struct stat sb;
318 void *addr = NULL;
319
320 fd = open(fname, O_RDWR);
321 if (fd < 0) {
322 perror(fname);
323 return NULL;
324 }
325 if (fstat(fd, &sb) < 0) {
326 perror(fname);
327 goto out;
328 }
329 if (!S_ISREG(sb.st_mode)) {
330 fprintf(stderr, "not a regular file: %s\n", fname);
331 goto out;
332 }
333
334 addr = mmap(0, sb.st_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);
335 if (addr == MAP_FAILED) {
336 fprintf(stderr, "Could not mmap file: %s\n", fname);
337 goto out;
338 }
339
340 *size = sb.st_size;
341
342out:
343 close(fd);
344 return addr;
345}
346
347static uint32_t rbe(const uint32_t *x)
348{
349 return get_unaligned_be32(x);
350}
351
352static uint16_t r2be(const uint16_t *x)
353{
354 return get_unaligned_be16(x);
355}
356
357static uint64_t r8be(const uint64_t *x)
358{
359 return get_unaligned_be64(x);
360}
361
362static uint32_t rle(const uint32_t *x)
363{
364 return get_unaligned_le32(x);
365}
366
367static uint16_t r2le(const uint16_t *x)
368{
369 return get_unaligned_le16(x);
370}
371
372static uint64_t r8le(const uint64_t *x)
373{
374 return get_unaligned_le64(x);
375}
376
377static void wbe(uint32_t val, uint32_t *x)
378{
379 put_unaligned_be32(val, x);
380}
381
382static void wle(uint32_t val, uint32_t *x)
383{
384 put_unaligned_le32(val, x);
385}
386
387static void w8be(uint64_t val, uint64_t *x)
388{
389 put_unaligned_be64(val, x);
390}
391
392static void w8le(uint64_t val, uint64_t *x)
393{
394 put_unaligned_le64(val, x);
395}
396
397/*
398 * Move reserved section indices SHN_LORESERVE..SHN_HIRESERVE out of
399 * the way to -256..-1, to avoid conflicting with real section
400 * indices.
401 */
402#define SPECIAL(i) ((i) - (SHN_HIRESERVE + 1))
403
404static inline int is_shndx_special(unsigned int i)
405{
406 return i != SHN_XINDEX && i >= SHN_LORESERVE && i <= SHN_HIRESERVE;
407}
408
409/* Accessor for sym->st_shndx, hides ugliness of "64k sections" */
410static inline unsigned int get_secindex(unsigned int shndx,
411 unsigned int sym_offs,
412 const Elf32_Word *symtab_shndx_start)
413{
414 if (is_shndx_special(shndx))
415 return SPECIAL(shndx);
416 if (shndx != SHN_XINDEX)
417 return shndx;
418 return r(&symtab_shndx_start[sym_offs]);
419}
420
421static int compare_extable_32(const void *a, const void *b)
422{
423 Elf32_Addr av = r(a);
424 Elf32_Addr bv = r(b);
425
426 if (av < bv)
427 return -1;
428 return av > bv;
429}
430
431static int compare_extable_64(const void *a, const void *b)
432{
433 Elf64_Addr av = r8(a);
434 Elf64_Addr bv = r8(b);
435
436 if (av < bv)
437 return -1;
438 return av > bv;
439}
440
441static int compare_extable(const void *a, const void *b)
442{
443 return e.compare_extable(a, b);
444}
445
446static inline void *get_index(void *start, int entsize, int index)
447{
448 return start + (entsize * index);
449}
450
451static int extable_ent_size;
452static int long_size;
453
454#define ERRSTR_MAXSZ 256
455
456#ifdef UNWINDER_ORC_ENABLED
457/* ORC unwinder only support X86_64 */
458#include <asm/orc_types.h>
459
460static char g_err[ERRSTR_MAXSZ];
461static int *g_orc_ip_table;
462static struct orc_entry *g_orc_table;
463
464static pthread_t orc_sort_thread;
465
466static inline unsigned long orc_ip(const int *ip)
467{
468 return (unsigned long)ip + *ip;
469}
470
471static int orc_sort_cmp(const void *_a, const void *_b)
472{
473 struct orc_entry *orc_a, *orc_b;
474 const int *a = g_orc_ip_table + *(int *)_a;
475 const int *b = g_orc_ip_table + *(int *)_b;
476 unsigned long a_val = orc_ip(a);
477 unsigned long b_val = orc_ip(b);
478
479 if (a_val > b_val)
480 return 1;
481 if (a_val < b_val)
482 return -1;
483
484 /*
485 * The "weak" section terminator entries need to always be on the left
486 * to ensure the lookup code skips them in favor of real entries.
487 * These terminator entries exist to handle any gaps created by
488 * whitelisted .o files which didn't get objtool generation.
489 */
490 orc_a = g_orc_table + (a - g_orc_ip_table);
491 orc_b = g_orc_table + (b - g_orc_ip_table);
492 if (orc_a->type == ORC_TYPE_UNDEFINED && orc_b->type == ORC_TYPE_UNDEFINED)
493 return 0;
494 return orc_a->type == ORC_TYPE_UNDEFINED ? -1 : 1;
495}
496
497static void *sort_orctable(void *arg)
498{
499 int i;
500 int *idxs = NULL;
501 int *tmp_orc_ip_table = NULL;
502 struct orc_entry *tmp_orc_table = NULL;
503 unsigned int *orc_ip_size = (unsigned int *)arg;
504 unsigned int num_entries = *orc_ip_size / sizeof(int);
505 unsigned int orc_size = num_entries * sizeof(struct orc_entry);
506
507 idxs = (int *)malloc(*orc_ip_size);
508 if (!idxs) {
509 snprintf(g_err, ERRSTR_MAXSZ, "malloc idxs: %s",
510 strerror(errno));
511 pthread_exit(g_err);
512 }
513
514 tmp_orc_ip_table = (int *)malloc(*orc_ip_size);
515 if (!tmp_orc_ip_table) {
516 snprintf(g_err, ERRSTR_MAXSZ, "malloc tmp_orc_ip_table: %s",
517 strerror(errno));
518 pthread_exit(g_err);
519 }
520
521 tmp_orc_table = (struct orc_entry *)malloc(orc_size);
522 if (!tmp_orc_table) {
523 snprintf(g_err, ERRSTR_MAXSZ, "malloc tmp_orc_table: %s",
524 strerror(errno));
525 pthread_exit(g_err);
526 }
527
528 /* initialize indices array, convert ip_table to absolute address */
529 for (i = 0; i < num_entries; i++) {
530 idxs[i] = i;
531 tmp_orc_ip_table[i] = g_orc_ip_table[i] + i * sizeof(int);
532 }
533 memcpy(tmp_orc_table, g_orc_table, orc_size);
534
535 qsort(idxs, num_entries, sizeof(int), orc_sort_cmp);
536
537 for (i = 0; i < num_entries; i++) {
538 if (idxs[i] == i)
539 continue;
540
541 /* convert back to relative address */
542 g_orc_ip_table[i] = tmp_orc_ip_table[idxs[i]] - i * sizeof(int);
543 g_orc_table[i] = tmp_orc_table[idxs[i]];
544 }
545
546 free(idxs);
547 free(tmp_orc_ip_table);
548 free(tmp_orc_table);
549 pthread_exit(NULL);
550}
551#endif
552
553#ifdef MCOUNT_SORT_ENABLED
554
555static int compare_values_64(const void *a, const void *b)
556{
557 uint64_t av = *(uint64_t *)a;
558 uint64_t bv = *(uint64_t *)b;
559
560 if (av < bv)
561 return -1;
562 return av > bv;
563}
564
565static int compare_values_32(const void *a, const void *b)
566{
567 uint32_t av = *(uint32_t *)a;
568 uint32_t bv = *(uint32_t *)b;
569
570 if (av < bv)
571 return -1;
572 return av > bv;
573}
574
575static int (*compare_values)(const void *a, const void *b);
576
577/* Only used for sorting mcount table */
578static void rela_write_addend(Elf_Rela *rela, uint64_t val)
579{
580 e.rela_write_addend(rela, val);
581}
582
583struct func_info {
584 uint64_t addr;
585 uint64_t size;
586};
587
588/* List of functions created by: nm -S vmlinux */
589static struct func_info *function_list;
590static int function_list_size;
591
592/* Allocate functions in 1k blocks */
593#define FUNC_BLK_SIZE 1024
594#define FUNC_BLK_MASK (FUNC_BLK_SIZE - 1)
595
596static int add_field(uint64_t addr, uint64_t size)
597{
598 struct func_info *fi;
599 int fsize = function_list_size;
600
601 if (!(fsize & FUNC_BLK_MASK)) {
602 fsize += FUNC_BLK_SIZE;
603 fi = realloc(function_list, fsize * sizeof(struct func_info));
604 if (!fi)
605 return -1;
606 function_list = fi;
607 }
608 fi = &function_list[function_list_size++];
609 fi->addr = addr;
610 fi->size = size;
611 return 0;
612}
613
614/* Used for when mcount/fentry is before the function entry */
615static int before_func;
616
617/* Only return match if the address lies inside the function size */
618static int cmp_func_addr(const void *K, const void *A)
619{
620 uint64_t key = *(const uint64_t *)K;
621 const struct func_info *a = A;
622
623 if (key + before_func < a->addr)
624 return -1;
625 return key >= a->addr + a->size;
626}
627
628/* Find the function in function list that is bounded by the function size */
629static int find_func(uint64_t key)
630{
631 return bsearch(&key, function_list, function_list_size,
632 sizeof(struct func_info), cmp_func_addr) != NULL;
633}
634
635static int cmp_funcs(const void *A, const void *B)
636{
637 const struct func_info *a = A;
638 const struct func_info *b = B;
639
640 if (a->addr < b->addr)
641 return -1;
642 return a->addr > b->addr;
643}
644
645static int parse_symbols(const char *fname)
646{
647 FILE *fp;
648 char addr_str[20]; /* Only need 17, but round up to next int size */
649 char size_str[20];
650 char type;
651
652 fp = fopen(fname, "r");
653 if (!fp) {
654 perror(fname);
655 return -1;
656 }
657
658 while (fscanf(fp, "%16s %16s %c %*s\n", addr_str, size_str, &type) == 3) {
659 uint64_t addr;
660 uint64_t size;
661
662 /* Only care about functions */
663 if (type != 't' && type != 'T' && type != 'W')
664 continue;
665
666 addr = strtoull(addr_str, NULL, 16);
667 size = strtoull(size_str, NULL, 16);
668 if (add_field(addr, size) < 0)
669 return -1;
670 }
671 fclose(fp);
672
673 qsort(function_list, function_list_size, sizeof(struct func_info), cmp_funcs);
674
675 return 0;
676}
677
678static pthread_t mcount_sort_thread;
679static bool sort_reloc;
680
681static long rela_type;
682
683static char m_err[ERRSTR_MAXSZ];
684
685struct elf_mcount_loc {
686 Elf_Ehdr *ehdr;
687 Elf_Shdr *init_data_sec;
688 uint64_t start_mcount_loc;
689 uint64_t stop_mcount_loc;
690};
691
692/* Fill the array with the content of the relocs */
693static int fill_relocs(void *ptr, uint64_t size, Elf_Ehdr *ehdr, uint64_t start_loc)
694{
695 Elf_Shdr *shdr_start;
696 Elf_Rela *rel;
697 unsigned int shnum;
698 unsigned int count = 0;
699 int shentsize;
700 void *array_end = ptr + size;
701
702 shdr_start = (Elf_Shdr *)((char *)ehdr + ehdr_shoff(ehdr));
703 shentsize = ehdr_shentsize(ehdr);
704
705 shnum = ehdr_shnum(ehdr);
706 if (shnum == SHN_UNDEF)
707 shnum = shdr_size(shdr_start);
708
709 for (int i = 0; i < shnum; i++) {
710 Elf_Shdr *shdr = get_index(shdr_start, shentsize, i);
711 void *end;
712
713 if (shdr_type(shdr) != SHT_RELA)
714 continue;
715
716 rel = (void *)ehdr + shdr_offset(shdr);
717 end = (void *)rel + shdr_size(shdr);
718
719 for (; (void *)rel < end; rel = (void *)rel + shdr_entsize(shdr)) {
720 uint64_t offset = rela_offset(rel);
721
722 if (offset >= start_loc && offset < start_loc + size) {
723 if (ptr + long_size > array_end) {
724 snprintf(m_err, ERRSTR_MAXSZ,
725 "Too many relocations");
726 return -1;
727 }
728
729 /* Make sure this has the correct type */
730 if (rela_info(rel) != rela_type) {
731 snprintf(m_err, ERRSTR_MAXSZ,
732 "rela has type %lx but expected %lx\n",
733 (long)rela_info(rel), rela_type);
734 return -1;
735 }
736
737 if (long_size == 4)
738 *(uint32_t *)ptr = rela_addend(rel);
739 else
740 *(uint64_t *)ptr = rela_addend(rel);
741 ptr += long_size;
742 count++;
743 }
744 }
745 }
746 return count;
747}
748
749/* Put the sorted vals back into the relocation elements */
750static void replace_relocs(void *ptr, uint64_t size, Elf_Ehdr *ehdr, uint64_t start_loc)
751{
752 Elf_Shdr *shdr_start;
753 Elf_Rela *rel;
754 unsigned int shnum;
755 int shentsize;
756
757 shdr_start = (Elf_Shdr *)((char *)ehdr + ehdr_shoff(ehdr));
758 shentsize = ehdr_shentsize(ehdr);
759
760 shnum = ehdr_shnum(ehdr);
761 if (shnum == SHN_UNDEF)
762 shnum = shdr_size(shdr_start);
763
764 for (int i = 0; i < shnum; i++) {
765 Elf_Shdr *shdr = get_index(shdr_start, shentsize, i);
766 void *end;
767
768 if (shdr_type(shdr) != SHT_RELA)
769 continue;
770
771 rel = (void *)ehdr + shdr_offset(shdr);
772 end = (void *)rel + shdr_size(shdr);
773
774 for (; (void *)rel < end; rel = (void *)rel + shdr_entsize(shdr)) {
775 uint64_t offset = rela_offset(rel);
776
777 if (offset >= start_loc && offset < start_loc + size) {
778 if (long_size == 4)
779 rela_write_addend(rel, *(uint32_t *)ptr);
780 else
781 rela_write_addend(rel, *(uint64_t *)ptr);
782 ptr += long_size;
783 }
784 }
785 }
786}
787
788static int fill_addrs(void *ptr, uint64_t size, void *addrs)
789{
790 void *end = ptr + size;
791 int count = 0;
792
793 for (; ptr < end; ptr += long_size, addrs += long_size, count++) {
794 if (long_size == 4)
795 *(uint32_t *)ptr = r(addrs);
796 else
797 *(uint64_t *)ptr = r8(addrs);
798 }
799 return count;
800}
801
802static void replace_addrs(void *ptr, uint64_t size, void *addrs)
803{
804 void *end = ptr + size;
805
806 for (; ptr < end; ptr += long_size, addrs += long_size) {
807 if (long_size == 4)
808 w(*(uint32_t *)ptr, addrs);
809 else
810 w8(*(uint64_t *)ptr, addrs);
811 }
812}
813
814/* Sort the addresses stored between __start_mcount_loc to __stop_mcount_loc in vmlinux */
815static void *sort_mcount_loc(void *arg)
816{
817 struct elf_mcount_loc *emloc = (struct elf_mcount_loc *)arg;
818 uint64_t offset = emloc->start_mcount_loc - shdr_addr(emloc->init_data_sec)
819 + shdr_offset(emloc->init_data_sec);
820 uint64_t size = emloc->stop_mcount_loc - emloc->start_mcount_loc;
821 unsigned char *start_loc = (void *)emloc->ehdr + offset;
822 Elf_Ehdr *ehdr = emloc->ehdr;
823 void *e_msg = NULL;
824 void *vals;
825 int count;
826
827 vals = malloc(long_size * size);
828 if (!vals) {
829 snprintf(m_err, ERRSTR_MAXSZ, "Failed to allocate sort array");
830 pthread_exit(m_err);
831 }
832
833 if (sort_reloc) {
834 count = fill_relocs(vals, size, ehdr, emloc->start_mcount_loc);
835 /* gcc may use relocs to save the addresses, but clang does not. */
836 if (!count) {
837 count = fill_addrs(vals, size, start_loc);
838 sort_reloc = 0;
839 }
840 } else
841 count = fill_addrs(vals, size, start_loc);
842
843 if (count < 0) {
844 e_msg = m_err;
845 goto out;
846 }
847
848 if (count != size / long_size) {
849 snprintf(m_err, ERRSTR_MAXSZ, "Expected %u mcount elements but found %u\n",
850 (int)(size / long_size), count);
851 e_msg = m_err;
852 goto out;
853 }
854
855 /* zero out any locations not found by function list */
856 if (function_list_size) {
857 for (void *ptr = vals; ptr < vals + size; ptr += long_size) {
858 uint64_t key;
859
860 key = long_size == 4 ? *(uint32_t *)ptr : *(uint64_t *)ptr;
861 if (!find_func(key)) {
862 if (long_size == 4)
863 *(uint32_t *)ptr = 0;
864 else
865 *(uint64_t *)ptr = 0;
866 }
867 }
868 }
869
870 compare_values = long_size == 4 ? compare_values_32 : compare_values_64;
871
872 qsort(vals, count, long_size, compare_values);
873
874 if (sort_reloc)
875 replace_relocs(vals, size, ehdr, emloc->start_mcount_loc);
876 else
877 replace_addrs(vals, size, start_loc);
878
879out:
880 free(vals);
881
882 pthread_exit(e_msg);
883}
884
885/* Get the address of __start_mcount_loc and __stop_mcount_loc in System.map */
886static void get_mcount_loc(struct elf_mcount_loc *emloc, Elf_Shdr *symtab_sec,
887 const char *strtab)
888{
889 Elf_Sym *sym, *end_sym;
890 int symentsize = shdr_entsize(symtab_sec);
891 int found = 0;
892
893 sym = (void *)emloc->ehdr + shdr_offset(symtab_sec);
894 end_sym = (void *)sym + shdr_size(symtab_sec);
895
896 while (sym < end_sym) {
897 if (!strcmp(strtab + sym_name(sym), "__start_mcount_loc")) {
898 emloc->start_mcount_loc = sym_value(sym);
899 if (++found == 2)
900 break;
901 } else if (!strcmp(strtab + sym_name(sym), "__stop_mcount_loc")) {
902 emloc->stop_mcount_loc = sym_value(sym);
903 if (++found == 2)
904 break;
905 }
906 sym = (void *)sym + symentsize;
907 }
908
909 if (!emloc->start_mcount_loc) {
910 fprintf(stderr, "get start_mcount_loc error!");
911 return;
912 }
913
914 if (!emloc->stop_mcount_loc) {
915 fprintf(stderr, "get stop_mcount_loc error!");
916 return;
917 }
918}
919#else /* MCOUNT_SORT_ENABLED */
920static inline int parse_symbols(const char *fname) { return 0; }
921#endif
922
923static int do_sort(Elf_Ehdr *ehdr,
924 char const *const fname,
925 table_sort_t custom_sort)
926{
927 int rc = -1;
928 Elf_Shdr *shdr_start;
929 Elf_Shdr *strtab_sec = NULL;
930 Elf_Shdr *symtab_sec = NULL;
931 Elf_Shdr *extab_sec = NULL;
932 Elf_Shdr *string_sec;
933 Elf_Sym *sym;
934 const Elf_Sym *symtab;
935 Elf32_Word *symtab_shndx = NULL;
936 Elf_Sym *sort_needed_sym = NULL;
937 Elf_Shdr *sort_needed_sec;
938 uint32_t *sort_needed_loc;
939 void *sym_start;
940 void *sym_end;
941 const char *secstrings;
942 const char *strtab;
943 char *extab_image;
944 int sort_need_index;
945 int symentsize;
946 int shentsize;
947 int idx;
948 int i;
949 unsigned int shnum;
950 unsigned int shstrndx;
951#ifdef MCOUNT_SORT_ENABLED
952 struct elf_mcount_loc mstruct = {0};
953#endif
954#ifdef UNWINDER_ORC_ENABLED
955 unsigned int orc_ip_size = 0;
956 unsigned int orc_size = 0;
957 unsigned int orc_num_entries = 0;
958#endif
959
960 shdr_start = (Elf_Shdr *)((char *)ehdr + ehdr_shoff(ehdr));
961 shentsize = ehdr_shentsize(ehdr);
962
963 shstrndx = ehdr_shstrndx(ehdr);
964 if (shstrndx == SHN_XINDEX)
965 shstrndx = shdr_link(shdr_start);
966 string_sec = get_index(shdr_start, shentsize, shstrndx);
967 secstrings = (const char *)ehdr + shdr_offset(string_sec);
968
969 shnum = ehdr_shnum(ehdr);
970 if (shnum == SHN_UNDEF)
971 shnum = shdr_size(shdr_start);
972
973 for (i = 0; i < shnum; i++) {
974 Elf_Shdr *shdr = get_index(shdr_start, shentsize, i);
975
976 idx = shdr_name(shdr);
977 if (!strcmp(secstrings + idx, "__ex_table"))
978 extab_sec = shdr;
979 if (!strcmp(secstrings + idx, ".symtab"))
980 symtab_sec = shdr;
981 if (!strcmp(secstrings + idx, ".strtab"))
982 strtab_sec = shdr;
983
984 if (shdr_type(shdr) == SHT_SYMTAB_SHNDX)
985 symtab_shndx = (Elf32_Word *)((const char *)ehdr +
986 shdr_offset(shdr));
987
988#ifdef MCOUNT_SORT_ENABLED
989 /* locate the .init.data section in vmlinux */
990 if (!strcmp(secstrings + idx, ".init.data"))
991 mstruct.init_data_sec = shdr;
992#endif
993
994#ifdef UNWINDER_ORC_ENABLED
995 /* locate the ORC unwind tables */
996 if (!strcmp(secstrings + idx, ".orc_unwind_ip")) {
997 orc_ip_size = shdr_size(shdr);
998 g_orc_ip_table = (int *)((void *)ehdr +
999 shdr_offset(shdr));
1000 }
1001 if (!strcmp(secstrings + idx, ".orc_unwind")) {
1002 orc_size = shdr_size(shdr);
1003 g_orc_table = (struct orc_entry *)((void *)ehdr +
1004 shdr_offset(shdr));
1005 }
1006#endif
1007 } /* for loop */
1008
1009#ifdef UNWINDER_ORC_ENABLED
1010 if (!g_orc_ip_table || !g_orc_table) {
1011 fprintf(stderr,
1012 "incomplete ORC unwind tables in file: %s\n", fname);
1013 goto out;
1014 }
1015
1016 orc_num_entries = orc_ip_size / sizeof(int);
1017 if (orc_ip_size % sizeof(int) != 0 ||
1018 orc_size % sizeof(struct orc_entry) != 0 ||
1019 orc_num_entries != orc_size / sizeof(struct orc_entry)) {
1020 fprintf(stderr,
1021 "inconsistent ORC unwind table entries in file: %s\n",
1022 fname);
1023 goto out;
1024 }
1025
1026 /* create thread to sort ORC unwind tables concurrently */
1027 if (pthread_create(&orc_sort_thread, NULL,
1028 sort_orctable, &orc_ip_size)) {
1029 fprintf(stderr,
1030 "pthread_create orc_sort_thread failed '%s': %s\n",
1031 strerror(errno), fname);
1032 goto out;
1033 }
1034#endif
1035 if (!extab_sec) {
1036 fprintf(stderr, "no __ex_table in file: %s\n", fname);
1037 goto out;
1038 }
1039
1040 if (!symtab_sec) {
1041 fprintf(stderr, "no .symtab in file: %s\n", fname);
1042 goto out;
1043 }
1044
1045 if (!strtab_sec) {
1046 fprintf(stderr, "no .strtab in file: %s\n", fname);
1047 goto out;
1048 }
1049
1050 extab_image = (void *)ehdr + shdr_offset(extab_sec);
1051 strtab = (const char *)ehdr + shdr_offset(strtab_sec);
1052 symtab = (const Elf_Sym *)((const char *)ehdr + shdr_offset(symtab_sec));
1053
1054#ifdef MCOUNT_SORT_ENABLED
1055 mstruct.ehdr = ehdr;
1056 get_mcount_loc(&mstruct, symtab_sec, strtab);
1057
1058 if (!mstruct.init_data_sec || !mstruct.start_mcount_loc || !mstruct.stop_mcount_loc) {
1059 fprintf(stderr,
1060 "incomplete mcount's sort in file: %s\n",
1061 fname);
1062 goto out;
1063 }
1064
1065 /* create thread to sort mcount_loc concurrently */
1066 if (pthread_create(&mcount_sort_thread, NULL, &sort_mcount_loc, &mstruct)) {
1067 fprintf(stderr,
1068 "pthread_create mcount_sort_thread failed '%s': %s\n",
1069 strerror(errno), fname);
1070 goto out;
1071 }
1072#endif
1073
1074 if (custom_sort) {
1075 custom_sort(extab_image, shdr_size(extab_sec));
1076 } else {
1077 int num_entries = shdr_size(extab_sec) / extable_ent_size;
1078 qsort(extab_image, num_entries,
1079 extable_ent_size, compare_extable);
1080 }
1081
1082 /* find the flag main_extable_sort_needed */
1083 sym_start = (void *)ehdr + shdr_offset(symtab_sec);
1084 sym_end = sym_start + shdr_size(symtab_sec);
1085 symentsize = shdr_entsize(symtab_sec);
1086
1087 for (sym = sym_start; (void *)sym + symentsize < sym_end;
1088 sym = (void *)sym + symentsize) {
1089 if (sym_type(sym) != STT_OBJECT)
1090 continue;
1091 if (!strcmp(strtab + sym_name(sym),
1092 "main_extable_sort_needed")) {
1093 sort_needed_sym = sym;
1094 break;
1095 }
1096 }
1097
1098 if (!sort_needed_sym) {
1099 fprintf(stderr,
1100 "no main_extable_sort_needed symbol in file: %s\n",
1101 fname);
1102 goto out;
1103 }
1104
1105 sort_need_index = get_secindex(sym_shndx(sym),
1106 ((void *)sort_needed_sym - (void *)symtab) / symentsize,
1107 symtab_shndx);
1108 sort_needed_sec = get_index(shdr_start, shentsize, sort_need_index);
1109 sort_needed_loc = (void *)ehdr +
1110 shdr_offset(sort_needed_sec) +
1111 sym_value(sort_needed_sym) - shdr_addr(sort_needed_sec);
1112
1113 /* extable has been sorted, clear the flag */
1114 w(0, sort_needed_loc);
1115 rc = 0;
1116
1117out:
1118#ifdef UNWINDER_ORC_ENABLED
1119 if (orc_sort_thread) {
1120 void *retval = NULL;
1121 /* wait for ORC tables sort done */
1122 rc = pthread_join(orc_sort_thread, &retval);
1123 if (rc) {
1124 fprintf(stderr,
1125 "pthread_join failed '%s': %s\n",
1126 strerror(errno), fname);
1127 } else if (retval) {
1128 rc = -1;
1129 fprintf(stderr,
1130 "failed to sort ORC tables '%s': %s\n",
1131 (char *)retval, fname);
1132 }
1133 }
1134#endif
1135
1136#ifdef MCOUNT_SORT_ENABLED
1137 if (mcount_sort_thread) {
1138 void *retval = NULL;
1139 /* wait for mcount sort done */
1140 rc = pthread_join(mcount_sort_thread, &retval);
1141 if (rc) {
1142 fprintf(stderr,
1143 "pthread_join failed '%s': %s\n",
1144 strerror(errno), fname);
1145 } else if (retval) {
1146 rc = -1;
1147 fprintf(stderr,
1148 "failed to sort mcount '%s': %s\n",
1149 (char *)retval, fname);
1150 }
1151 }
1152#endif
1153 return rc;
1154}
1155
1156static int compare_relative_table(const void *a, const void *b)
1157{
1158 int32_t av = (int32_t)r(a);
1159 int32_t bv = (int32_t)r(b);
1160
1161 if (av < bv)
1162 return -1;
1163 if (av > bv)
1164 return 1;
1165 return 0;
1166}
1167
1168static void sort_relative_table(char *extab_image, int image_size)
1169{
1170 int i = 0;
1171
1172 /*
1173 * Do the same thing the runtime sort does, first normalize to
1174 * being relative to the start of the section.
1175 */
1176 while (i < image_size) {
1177 uint32_t *loc = (uint32_t *)(extab_image + i);
1178 w(r(loc) + i, loc);
1179 i += 4;
1180 }
1181
1182 qsort(extab_image, image_size / 8, 8, compare_relative_table);
1183
1184 /* Now denormalize. */
1185 i = 0;
1186 while (i < image_size) {
1187 uint32_t *loc = (uint32_t *)(extab_image + i);
1188 w(r(loc) - i, loc);
1189 i += 4;
1190 }
1191}
1192
1193static void sort_relative_table_with_data(char *extab_image, int image_size)
1194{
1195 int i = 0;
1196
1197 while (i < image_size) {
1198 uint32_t *loc = (uint32_t *)(extab_image + i);
1199
1200 w(r(loc) + i, loc);
1201 w(r(loc + 1) + i + 4, loc + 1);
1202 /* Don't touch the fixup type or data */
1203
1204 i += sizeof(uint32_t) * 3;
1205 }
1206
1207 qsort(extab_image, image_size / 12, 12, compare_relative_table);
1208
1209 i = 0;
1210 while (i < image_size) {
1211 uint32_t *loc = (uint32_t *)(extab_image + i);
1212
1213 w(r(loc) - i, loc);
1214 w(r(loc + 1) - (i + 4), loc + 1);
1215 /* Don't touch the fixup type or data */
1216
1217 i += sizeof(uint32_t) * 3;
1218 }
1219}
1220
1221static int do_file(char const *const fname, void *addr)
1222{
1223 Elf_Ehdr *ehdr = addr;
1224 table_sort_t custom_sort = NULL;
1225
1226 switch (ehdr->e32.e_ident[EI_DATA]) {
1227 case ELFDATA2LSB:
1228 r = rle;
1229 r2 = r2le;
1230 r8 = r8le;
1231 w = wle;
1232 w8 = w8le;
1233 break;
1234 case ELFDATA2MSB:
1235 r = rbe;
1236 r2 = r2be;
1237 r8 = r8be;
1238 w = wbe;
1239 w8 = w8be;
1240 break;
1241 default:
1242 fprintf(stderr, "unrecognized ELF data encoding %d: %s\n",
1243 ehdr->e32.e_ident[EI_DATA], fname);
1244 return -1;
1245 }
1246
1247 if (memcmp(ELFMAG, ehdr->e32.e_ident, SELFMAG) != 0 ||
1248 (r2(&ehdr->e32.e_type) != ET_EXEC && r2(&ehdr->e32.e_type) != ET_DYN) ||
1249 ehdr->e32.e_ident[EI_VERSION] != EV_CURRENT) {
1250 fprintf(stderr, "unrecognized ET_EXEC/ET_DYN file %s\n", fname);
1251 return -1;
1252 }
1253
1254 switch (r2(&ehdr->e32.e_machine)) {
1255 case EM_AARCH64:
1256#ifdef MCOUNT_SORT_ENABLED
1257 sort_reloc = true;
1258 rela_type = 0x403;
1259 /* arm64 uses patchable function entry placing before function */
1260 before_func = 8;
1261#endif
1262 /* fallthrough */
1263 case EM_386:
1264 case EM_LOONGARCH:
1265 case EM_RISCV:
1266 case EM_S390:
1267 case EM_X86_64:
1268 custom_sort = sort_relative_table_with_data;
1269 break;
1270 case EM_PARISC:
1271 case EM_PPC:
1272 case EM_PPC64:
1273 custom_sort = sort_relative_table;
1274 break;
1275 case EM_ARCOMPACT:
1276 case EM_ARCV2:
1277 case EM_ARM:
1278 case EM_MICROBLAZE:
1279 case EM_MIPS:
1280 case EM_XTENSA:
1281 break;
1282 default:
1283 fprintf(stderr, "unrecognized e_machine %d %s\n",
1284 r2(&ehdr->e32.e_machine), fname);
1285 return -1;
1286 }
1287
1288 switch (ehdr->e32.e_ident[EI_CLASS]) {
1289 case ELFCLASS32: {
1290 struct elf_funcs efuncs = {
1291 .compare_extable = compare_extable_32,
1292 .ehdr_shoff = ehdr32_shoff,
1293 .ehdr_shentsize = ehdr32_shentsize,
1294 .ehdr_shstrndx = ehdr32_shstrndx,
1295 .ehdr_shnum = ehdr32_shnum,
1296 .shdr_addr = shdr32_addr,
1297 .shdr_offset = shdr32_offset,
1298 .shdr_link = shdr32_link,
1299 .shdr_size = shdr32_size,
1300 .shdr_name = shdr32_name,
1301 .shdr_type = shdr32_type,
1302 .shdr_entsize = shdr32_entsize,
1303 .sym_type = sym32_type,
1304 .sym_name = sym32_name,
1305 .sym_value = sym32_value,
1306 .sym_shndx = sym32_shndx,
1307 .rela_offset = rela32_offset,
1308 .rela_info = rela32_info,
1309 .rela_addend = rela32_addend,
1310 .rela_write_addend = rela32_write_addend,
1311 };
1312
1313 e = efuncs;
1314 long_size = 4;
1315 extable_ent_size = 8;
1316
1317 if (r2(&ehdr->e32.e_ehsize) != sizeof(Elf32_Ehdr) ||
1318 r2(&ehdr->e32.e_shentsize) != sizeof(Elf32_Shdr)) {
1319 fprintf(stderr,
1320 "unrecognized ET_EXEC/ET_DYN file: %s\n", fname);
1321 return -1;
1322 }
1323
1324 }
1325 break;
1326 case ELFCLASS64: {
1327 struct elf_funcs efuncs = {
1328 .compare_extable = compare_extable_64,
1329 .ehdr_shoff = ehdr64_shoff,
1330 .ehdr_shentsize = ehdr64_shentsize,
1331 .ehdr_shstrndx = ehdr64_shstrndx,
1332 .ehdr_shnum = ehdr64_shnum,
1333 .shdr_addr = shdr64_addr,
1334 .shdr_offset = shdr64_offset,
1335 .shdr_link = shdr64_link,
1336 .shdr_size = shdr64_size,
1337 .shdr_name = shdr64_name,
1338 .shdr_type = shdr64_type,
1339 .shdr_entsize = shdr64_entsize,
1340 .sym_type = sym64_type,
1341 .sym_name = sym64_name,
1342 .sym_value = sym64_value,
1343 .sym_shndx = sym64_shndx,
1344 .rela_offset = rela64_offset,
1345 .rela_info = rela64_info,
1346 .rela_addend = rela64_addend,
1347 .rela_write_addend = rela64_write_addend,
1348 };
1349
1350 e = efuncs;
1351 long_size = 8;
1352 extable_ent_size = 16;
1353
1354 if (r2(&ehdr->e64.e_ehsize) != sizeof(Elf64_Ehdr) ||
1355 r2(&ehdr->e64.e_shentsize) != sizeof(Elf64_Shdr)) {
1356 fprintf(stderr,
1357 "unrecognized ET_EXEC/ET_DYN file: %s\n",
1358 fname);
1359 return -1;
1360 }
1361
1362 }
1363 break;
1364 default:
1365 fprintf(stderr, "unrecognized ELF class %d %s\n",
1366 ehdr->e32.e_ident[EI_CLASS], fname);
1367 return -1;
1368 }
1369
1370 return do_sort(ehdr, fname, custom_sort);
1371}
1372
1373int main(int argc, char *argv[])
1374{
1375 int i, n_error = 0; /* gcc-4.3.0 false positive complaint */
1376 size_t size = 0;
1377 void *addr = NULL;
1378 int c;
1379
1380 while ((c = getopt(argc, argv, "s:")) >= 0) {
1381 switch (c) {
1382 case 's':
1383 if (parse_symbols(optarg) < 0) {
1384 fprintf(stderr, "Could not parse %s\n", optarg);
1385 return -1;
1386 }
1387 break;
1388 default:
1389 fprintf(stderr, "usage: sorttable [-s nm-file] vmlinux...\n");
1390 return 0;
1391 }
1392 }
1393
1394 if ((argc - optind) < 1) {
1395 fprintf(stderr, "usage: sorttable vmlinux...\n");
1396 return 0;
1397 }
1398
1399 /* Process each file in turn, allowing deep failure. */
1400 for (i = optind; i < argc; i++) {
1401 addr = mmap_file(argv[i], &size);
1402 if (!addr) {
1403 ++n_error;
1404 continue;
1405 }
1406
1407 if (do_file(argv[i], addr))
1408 ++n_error;
1409
1410 munmap(addr, size);
1411 }
1412
1413 return !!n_error;
1414}