the-tree/scripts/sorttable.h

0001 /* SPDX-License-Identifier: GPL-2.0-only */
0002 /*
0003  * sorttable.h
0004  *
0005  * Added ORC unwind tables sort support and other updates:
0006  * Copyright (C) 1999-2019 Alibaba Group Holding Limited. by:
0007  * Shile Zhang <shile.zhang@linux.alibaba.com>
0008  *
0009  * Copyright 2011 - 2012 Cavium, Inc.
0010  *
0011  * Some of code was taken out of arch/x86/kernel/unwind_orc.c, written by:
0012  * Copyright (C) 2017 Josh Poimboeuf <jpoimboe@redhat.com>
0013  *
0014  * Some of this code was taken out of recordmcount.h written by:
0015  *
0016  * Copyright 2009 John F. Reiser <jreiser@BitWagon.com>. All rights reserved.
0017  * Copyright 2010 Steven Rostedt <srostedt@redhat.com>, Red Hat Inc.
0018  */
0019
0020 #undef extable_ent_size
0021 #undef compare_extable
0022 #undef get_mcount_loc
0023 #undef sort_mcount_loc
0024 #undef elf_mcount_loc
0025 #undef do_sort
0026 #undef Elf_Addr
0027 #undef Elf_Ehdr
0028 #undef Elf_Shdr
0029 #undef Elf_Rel
0030 #undef Elf_Rela
0031 #undef Elf_Sym
0032 #undef ELF_R_SYM
0033 #undef Elf_r_sym
0034 #undef ELF_R_INFO
0035 #undef Elf_r_info
0036 #undef ELF_ST_BIND
0037 #undef ELF_ST_TYPE
0038 #undef fn_ELF_R_SYM
0039 #undef fn_ELF_R_INFO
0040 #undef uint_t
0041 #undef _r
0042 #undef _w
0043
0044 #ifdef SORTTABLE_64
0045 # define extable_ent_size   16
0046 # define compare_extable    compare_extable_64
0047 # define get_mcount_loc     get_mcount_loc_64
0048 # define sort_mcount_loc    sort_mcount_loc_64
0049 # define elf_mcount_loc     elf_mcount_loc_64
0050 # define do_sort        do_sort_64
0051 # define Elf_Addr       Elf64_Addr
0052 # define Elf_Ehdr       Elf64_Ehdr
0053 # define Elf_Shdr       Elf64_Shdr
0054 # define Elf_Rel        Elf64_Rel
0055 # define Elf_Rela       Elf64_Rela
0056 # define Elf_Sym        Elf64_Sym
0057 # define ELF_R_SYM      ELF64_R_SYM
0058 # define Elf_r_sym      Elf64_r_sym
0059 # define ELF_R_INFO     ELF64_R_INFO
0060 # define Elf_r_info     Elf64_r_info
0061 # define ELF_ST_BIND        ELF64_ST_BIND
0062 # define ELF_ST_TYPE        ELF64_ST_TYPE
0063 # define fn_ELF_R_SYM       fn_ELF64_R_SYM
0064 # define fn_ELF_R_INFO      fn_ELF64_R_INFO
0065 # define uint_t         uint64_t
0066 # define _r         r8
0067 # define _w         w8
0068 #else
0069 # define extable_ent_size   8
0070 # define compare_extable    compare_extable_32
0071 # define get_mcount_loc     get_mcount_loc_32
0072 # define sort_mcount_loc    sort_mcount_loc_32
0073 # define elf_mcount_loc     elf_mcount_loc_32
0074 # define do_sort        do_sort_32
0075 # define Elf_Addr       Elf32_Addr
0076 # define Elf_Ehdr       Elf32_Ehdr
0077 # define Elf_Shdr       Elf32_Shdr
0078 # define Elf_Rel        Elf32_Rel
0079 # define Elf_Rela       Elf32_Rela
0080 # define Elf_Sym        Elf32_Sym
0081 # define ELF_R_SYM      ELF32_R_SYM
0082 # define Elf_r_sym      Elf32_r_sym
0083 # define ELF_R_INFO     ELF32_R_INFO
0084 # define Elf_r_info     Elf32_r_info
0085 # define ELF_ST_BIND        ELF32_ST_BIND
0086 # define ELF_ST_TYPE        ELF32_ST_TYPE
0087 # define fn_ELF_R_SYM       fn_ELF32_R_SYM
0088 # define fn_ELF_R_INFO      fn_ELF32_R_INFO
0089 # define uint_t         uint32_t
0090 # define _r         r
0091 # define _w         w
0092 #endif
0093
0094 #if defined(SORTTABLE_64) && defined(UNWINDER_ORC_ENABLED)
0095 /* ORC unwinder only support X86_64 */
0096 #include <asm/orc_types.h>
0097
0098 #define ERRSTR_MAXSZ    256
0099
0100 char g_err[ERRSTR_MAXSZ];
0101 int *g_orc_ip_table;
0102 struct orc_entry *g_orc_table;
0103
0104 pthread_t orc_sort_thread;
0105
0106 static inline unsigned long orc_ip(const int *ip)
0107 {
0108     return (unsigned long)ip + *ip;
0109 }
0110
0111 static int orc_sort_cmp(const void *_a, const void *_b)
0112 {
0113     struct orc_entry *orc_a;
0114     const int *a = g_orc_ip_table + *(int *)_a;
0115     const int *b = g_orc_ip_table + *(int *)_b;
0116     unsigned long a_val = orc_ip(a);
0117     unsigned long b_val = orc_ip(b);
0118
0119     if (a_val > b_val)
0120         return 1;
0121     if (a_val < b_val)
0122         return -1;
0123
0124     /*
0125      * The "weak" section terminator entries need to always be on the left
0126      * to ensure the lookup code skips them in favor of real entries.
0127      * These terminator entries exist to handle any gaps created by
0128      * whitelisted .o files which didn't get objtool generation.
0129      */
0130     orc_a = g_orc_table + (a - g_orc_ip_table);
0131     return orc_a->sp_reg == ORC_REG_UNDEFINED && !orc_a->end ? -1 : 1;
0132 }
0133
0134 static void *sort_orctable(void *arg)
0135 {
0136     int i;
0137     int *idxs = NULL;
0138     int *tmp_orc_ip_table = NULL;
0139     struct orc_entry *tmp_orc_table = NULL;
0140     unsigned int *orc_ip_size = (unsigned int *)arg;
0141     unsigned int num_entries = *orc_ip_size / sizeof(int);
0142     unsigned int orc_size = num_entries * sizeof(struct orc_entry);
0143
0144     idxs = (int *)malloc(*orc_ip_size);
0145     if (!idxs) {
0146         snprintf(g_err, ERRSTR_MAXSZ, "malloc idxs: %s",
0147              strerror(errno));
0148         pthread_exit(g_err);
0149     }
0150
0151     tmp_orc_ip_table = (int *)malloc(*orc_ip_size);
0152     if (!tmp_orc_ip_table) {
0153         snprintf(g_err, ERRSTR_MAXSZ, "malloc tmp_orc_ip_table: %s",
0154              strerror(errno));
0155         pthread_exit(g_err);
0156     }
0157
0158     tmp_orc_table = (struct orc_entry *)malloc(orc_size);
0159     if (!tmp_orc_table) {
0160         snprintf(g_err, ERRSTR_MAXSZ, "malloc tmp_orc_table: %s",
0161              strerror(errno));
0162         pthread_exit(g_err);
0163     }
0164
0165     /* initialize indices array, convert ip_table to absolute address */
0166     for (i = 0; i < num_entries; i++) {
0167         idxs[i] = i;
0168         tmp_orc_ip_table[i] = g_orc_ip_table[i] + i * sizeof(int);
0169     }
0170     memcpy(tmp_orc_table, g_orc_table, orc_size);
0171
0172     qsort(idxs, num_entries, sizeof(int), orc_sort_cmp);
0173
0174     for (i = 0; i < num_entries; i++) {
0175         if (idxs[i] == i)
0176             continue;
0177
0178         /* convert back to relative address */
0179         g_orc_ip_table[i] = tmp_orc_ip_table[idxs[i]] - i * sizeof(int);
0180         g_orc_table[i] = tmp_orc_table[idxs[i]];
0181     }
0182
0183     free(idxs);
0184     free(tmp_orc_ip_table);
0185     free(tmp_orc_table);
0186     pthread_exit(NULL);
0187 }
0188 #endif
0189
0190 static int compare_extable(const void *a, const void *b)
0191 {
0192     Elf_Addr av = _r(a);
0193     Elf_Addr bv = _r(b);
0194
0195     if (av < bv)
0196         return -1;
0197     if (av > bv)
0198         return 1;
0199     return 0;
0200 }
0201 #ifdef MCOUNT_SORT_ENABLED
0202 pthread_t mcount_sort_thread;
0203
0204 struct elf_mcount_loc {
0205     Elf_Ehdr *ehdr;
0206     Elf_Shdr *init_data_sec;
0207     uint_t start_mcount_loc;
0208     uint_t stop_mcount_loc;
0209 };
0210
0211 /* Sort the addresses stored between __start_mcount_loc to __stop_mcount_loc in vmlinux */
0212 static void *sort_mcount_loc(void *arg)
0213 {
0214     struct elf_mcount_loc *emloc = (struct elf_mcount_loc *)arg;
0215     uint_t offset = emloc->start_mcount_loc - _r(&(emloc->init_data_sec)->sh_addr)
0216                     + _r(&(emloc->init_data_sec)->sh_offset);
0217     uint_t count = emloc->stop_mcount_loc - emloc->start_mcount_loc;
0218     unsigned char *start_loc = (void *)emloc->ehdr + offset;
0219
0220     qsort(start_loc, count/sizeof(uint_t), sizeof(uint_t), compare_extable);
0221     return NULL;
0222 }
0223
0224 /* Get the address of __start_mcount_loc and __stop_mcount_loc in System.map */
0225 static void get_mcount_loc(uint_t *_start, uint_t *_stop)
0226 {
0227     FILE *file_start, *file_stop;
0228     char start_buff[20];
0229     char stop_buff[20];
0230     int len = 0;
0231
0232     file_start = popen(" grep start_mcount System.map | awk '{print $1}' ", "r");
0233     if (!file_start) {
0234         fprintf(stderr, "get start_mcount_loc error!");
0235         return;
0236     }
0237
0238     file_stop = popen(" grep stop_mcount System.map | awk '{print $1}' ", "r");
0239     if (!file_stop) {
0240         fprintf(stderr, "get stop_mcount_loc error!");
0241         pclose(file_start);
0242         return;
0243     }
0244
0245     while (fgets(start_buff, sizeof(start_buff), file_start) != NULL) {
0246         len = strlen(start_buff);
0247         start_buff[len - 1] = '\0';
0248     }
0249     *_start = strtoul(start_buff, NULL, 16);
0250
0251     while (fgets(stop_buff, sizeof(stop_buff), file_stop) != NULL) {
0252         len = strlen(stop_buff);
0253         stop_buff[len - 1] = '\0';
0254     }
0255     *_stop = strtoul(stop_buff, NULL, 16);
0256
0257     pclose(file_start);
0258     pclose(file_stop);
0259 }
0260 #endif
0261 static int do_sort(Elf_Ehdr *ehdr,
0262            char const *const fname,
0263            table_sort_t custom_sort)
0264 {
0265     int rc = -1;
0266     Elf_Shdr *s, *shdr = (Elf_Shdr *)((char *)ehdr + _r(&ehdr->e_shoff));
0267     Elf_Shdr *strtab_sec = NULL;
0268     Elf_Shdr *symtab_sec = NULL;
0269     Elf_Shdr *extab_sec = NULL;
0270     Elf_Sym *sym;
0271     const Elf_Sym *symtab;
0272     Elf32_Word *symtab_shndx = NULL;
0273     Elf_Sym *sort_needed_sym = NULL;
0274     Elf_Shdr *sort_needed_sec;
0275     Elf_Rel *relocs = NULL;
0276     int relocs_size = 0;
0277     uint32_t *sort_needed_loc;
0278     const char *secstrings;
0279     const char *strtab;
0280     char *extab_image;
0281     int extab_index = 0;
0282     int i;
0283     int idx;
0284     unsigned int shnum;
0285     unsigned int shstrndx;
0286 #ifdef MCOUNT_SORT_ENABLED
0287     struct elf_mcount_loc mstruct = {0};
0288     uint_t _start_mcount_loc = 0;
0289     uint_t _stop_mcount_loc = 0;
0290 #endif
0291 #if defined(SORTTABLE_64) && defined(UNWINDER_ORC_ENABLED)
0292     unsigned int orc_ip_size = 0;
0293     unsigned int orc_size = 0;
0294     unsigned int orc_num_entries = 0;
0295 #endif
0296
0297     shstrndx = r2(&ehdr->e_shstrndx);
0298     if (shstrndx == SHN_XINDEX)
0299         shstrndx = r(&shdr[0].sh_link);
0300     secstrings = (const char *)ehdr + _r(&shdr[shstrndx].sh_offset);
0301
0302     shnum = r2(&ehdr->e_shnum);
0303     if (shnum == SHN_UNDEF)
0304         shnum = _r(&shdr[0].sh_size);
0305
0306     for (i = 0, s = shdr; s < shdr + shnum; i++, s++) {
0307         idx = r(&s->sh_name);
0308         if (!strcmp(secstrings + idx, "__ex_table")) {
0309             extab_sec = s;
0310             extab_index = i;
0311         }
0312         if (!strcmp(secstrings + idx, ".symtab"))
0313             symtab_sec = s;
0314         if (!strcmp(secstrings + idx, ".strtab"))
0315             strtab_sec = s;
0316
0317         if ((r(&s->sh_type) == SHT_REL ||
0318              r(&s->sh_type) == SHT_RELA) &&
0319             r(&s->sh_info) == extab_index) {
0320             relocs = (void *)ehdr + _r(&s->sh_offset);
0321             relocs_size = _r(&s->sh_size);
0322         }
0323         if (r(&s->sh_type) == SHT_SYMTAB_SHNDX)
0324             symtab_shndx = (Elf32_Word *)((const char *)ehdr +
0325                               _r(&s->sh_offset));
0326
0327 #ifdef MCOUNT_SORT_ENABLED
0328         /* locate the .init.data section in vmlinux */
0329         if (!strcmp(secstrings + idx, ".init.data")) {
0330             get_mcount_loc(&_start_mcount_loc, &_stop_mcount_loc);
0331             mstruct.ehdr = ehdr;
0332             mstruct.init_data_sec = s;
0333             mstruct.start_mcount_loc = _start_mcount_loc;
0334             mstruct.stop_mcount_loc = _stop_mcount_loc;
0335         }
0336 #endif
0337
0338 #if defined(SORTTABLE_64) && defined(UNWINDER_ORC_ENABLED)
0339         /* locate the ORC unwind tables */
0340         if (!strcmp(secstrings + idx, ".orc_unwind_ip")) {
0341             orc_ip_size = s->sh_size;
0342             g_orc_ip_table = (int *)((void *)ehdr +
0343                            s->sh_offset);
0344         }
0345         if (!strcmp(secstrings + idx, ".orc_unwind")) {
0346             orc_size = s->sh_size;
0347             g_orc_table = (struct orc_entry *)((void *)ehdr +
0348                                  s->sh_offset);
0349         }
0350 #endif
0351     } /* for loop */
0352
0353 #if defined(SORTTABLE_64) && defined(UNWINDER_ORC_ENABLED)
0354     if (!g_orc_ip_table || !g_orc_table) {
0355         fprintf(stderr,
0356             "incomplete ORC unwind tables in file: %s\n", fname);
0357         goto out;
0358     }
0359
0360     orc_num_entries = orc_ip_size / sizeof(int);
0361     if (orc_ip_size % sizeof(int) != 0 ||
0362         orc_size % sizeof(struct orc_entry) != 0 ||
0363         orc_num_entries != orc_size / sizeof(struct orc_entry)) {
0364         fprintf(stderr,
0365             "inconsistent ORC unwind table entries in file: %s\n",
0366             fname);
0367         goto out;
0368     }
0369
0370     /* create thread to sort ORC unwind tables concurrently */
0371     if (pthread_create(&orc_sort_thread, NULL,
0372                sort_orctable, &orc_ip_size)) {
0373         fprintf(stderr,
0374             "pthread_create orc_sort_thread failed '%s': %s\n",
0375             strerror(errno), fname);
0376         goto out;
0377     }
0378 #endif
0379
0380 #ifdef MCOUNT_SORT_ENABLED
0381     if (!mstruct.init_data_sec || !_start_mcount_loc || !_stop_mcount_loc) {
0382         fprintf(stderr,
0383             "incomplete mcount's sort in file: %s\n",
0384             fname);
0385         goto out;
0386     }
0387
0388     /* create thread to sort mcount_loc concurrently */
0389     if (pthread_create(&mcount_sort_thread, NULL, &sort_mcount_loc, &mstruct)) {
0390         fprintf(stderr,
0391             "pthread_create mcount_sort_thread failed '%s': %s\n",
0392             strerror(errno), fname);
0393         goto out;
0394     }
0395 #endif
0396     if (!extab_sec) {
0397         fprintf(stderr, "no __ex_table in file: %s\n", fname);
0398         goto out;
0399     }
0400
0401     if (!symtab_sec) {
0402         fprintf(stderr, "no .symtab in file: %s\n", fname);
0403         goto out;
0404     }
0405
0406     if (!strtab_sec) {
0407         fprintf(stderr, "no .strtab in file: %s\n", fname);
0408         goto out;
0409     }
0410
0411     extab_image = (void *)ehdr + _r(&extab_sec->sh_offset);
0412     strtab = (const char *)ehdr + _r(&strtab_sec->sh_offset);
0413     symtab = (const Elf_Sym *)((const char *)ehdr +
0414                           _r(&symtab_sec->sh_offset));
0415
0416     if (custom_sort) {
0417         custom_sort(extab_image, _r(&extab_sec->sh_size));
0418     } else {
0419         int num_entries = _r(&extab_sec->sh_size) / extable_ent_size;
0420         qsort(extab_image, num_entries,
0421               extable_ent_size, compare_extable);
0422     }
0423
0424     /* If there were relocations, we no longer need them. */
0425     if (relocs)
0426         memset(relocs, 0, relocs_size);
0427
0428     /* find the flag main_extable_sort_needed */
0429     for (sym = (void *)ehdr + _r(&symtab_sec->sh_offset);
0430          sym < sym + _r(&symtab_sec->sh_size) / sizeof(Elf_Sym);
0431          sym++) {
0432         if (ELF_ST_TYPE(sym->st_info) != STT_OBJECT)
0433             continue;
0434         if (!strcmp(strtab + r(&sym->st_name),
0435                 "main_extable_sort_needed")) {
0436             sort_needed_sym = sym;
0437             break;
0438         }
0439     }
0440
0441     if (!sort_needed_sym) {
0442         fprintf(stderr,
0443             "no main_extable_sort_needed symbol in file: %s\n",
0444             fname);
0445         goto out;
0446     }
0447
0448     sort_needed_sec = &shdr[get_secindex(r2(&sym->st_shndx),
0449                          sort_needed_sym - symtab,
0450                          symtab_shndx)];
0451     sort_needed_loc = (void *)ehdr +
0452         _r(&sort_needed_sec->sh_offset) +
0453         _r(&sort_needed_sym->st_value) -
0454         _r(&sort_needed_sec->sh_addr);
0455
0456     /* extable has been sorted, clear the flag */
0457     w(0, sort_needed_loc);
0458     rc = 0;
0459
0460 out:
0461 #if defined(SORTTABLE_64) && defined(UNWINDER_ORC_ENABLED)
0462     if (orc_sort_thread) {
0463         void *retval = NULL;
0464         /* wait for ORC tables sort done */
0465         rc = pthread_join(orc_sort_thread, &retval);
0466         if (rc) {
0467             fprintf(stderr,
0468                 "pthread_join failed '%s': %s\n",
0469                 strerror(errno), fname);
0470         } else if (retval) {
0471             rc = -1;
0472             fprintf(stderr,
0473                 "failed to sort ORC tables '%s': %s\n",
0474                 (char *)retval, fname);
0475         }
0476     }
0477 #endif
0478
0479 #ifdef MCOUNT_SORT_ENABLED
0480     if (mcount_sort_thread) {
0481         void *retval = NULL;
0482         /* wait for mcount sort done */
0483         rc = pthread_join(mcount_sort_thread, &retval);
0484         if (rc) {
0485             fprintf(stderr,
0486                 "pthread_join failed '%s': %s\n",
0487                 strerror(errno), fname);
0488         } else if (retval) {
0489             rc = -1;
0490             fprintf(stderr,
0491                 "failed to sort mcount '%s': %s\n",
0492                 (char *)retval, fname);
0493         }
0494     }
0495 #endif
0496     return rc;
0497 }