scripts/mod/symsearch.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 /*
   4  * Helper functions for finding the symbol in an ELF which is "nearest"
   5  * to a given address.
   6  */
   7
   8 #include "modpost.h"
   9
  10 struct syminfo {
  11         unsigned int symbol_index;
  12         unsigned int section_index;
  13         Elf_Addr addr;
  14 };
  15
  16 /*
  17  * Container used to hold an entire binary search table.
  18  * Entries in table are ascending, sorted first by section_index,
  19  * then by addr, and last by symbol_index.  The sorting by
  20  * symbol_index is used to ensure predictable behavior when
  21  * multiple symbols are present with the same address; all
  22  * symbols past the first are effectively ignored, by eliding
  23  * them in symsearch_fixup().
  24  */
  25 struct symsearch {
  26         unsigned int table_size;
  27         struct syminfo table[];
  28 };
  29
  30 static int syminfo_compare(const void *s1, const void *s2)
  31 {
  32         const struct syminfo *sym1 = s1;
  33         const struct syminfo *sym2 = s2;
  34
  35         if (sym1->section_index > sym2->section_index)
  36                 return 1;
  37         if (sym1->section_index < sym2->section_index)
  38                 return -1;
  39         if (sym1->addr > sym2->addr)
  40                 return 1;
  41         if (sym1->addr < sym2->addr)
  42                 return -1;
  43         if (sym1->symbol_index > sym2->symbol_index)
  44                 return 1;
  45         if (sym1->symbol_index < sym2->symbol_index)
  46                 return -1;
  47         return 0;
  48 }
  49
  50 static unsigned int symbol_count(struct elf_info *elf)
  51 {
  52         unsigned int result = 0;
  53
  54         for (Elf_Sym *sym = elf->symtab_start; sym < elf->symtab_stop; sym++) {
  55                 if (is_valid_name(elf, sym))
  56                         result++;
  57         }
  58         return result;
  59 }
  60
  61 /*
  62  * Populate the search array that we just allocated.
  63  * Be slightly paranoid here.  The ELF file is mmap'd and could
  64  * conceivably change between symbol_count() and symsearch_populate().
  65  * If we notice any difference, bail out rather than potentially
  66  * propagating errors or crashing.
  67  */
  68 static void symsearch_populate(struct elf_info *elf,
  69                                struct syminfo *table,
  70                                unsigned int table_size)
  71 {
  72         bool is_arm = (elf->hdr->e_machine == EM_ARM);
  73
  74         for (Elf_Sym *sym = elf->symtab_start; sym < elf->symtab_stop; sym++) {
  75                 if (is_valid_name(elf, sym)) {
  76                         if (table_size-- == 0)
  77                                 fatal("%s: size mismatch\n", __func__);
  78                         table->symbol_index = sym - elf->symtab_start;
  79                         table->section_index = get_secindex(elf, sym);
  80                         table->addr = sym->st_value;
  81
  82                         /*
  83                          * For ARM Thumb instruction, the bit 0 of st_value is
  84                          * set if the symbol is STT_FUNC type. Mask it to get
  85                          * the address.
  86                          */
  87                         if (is_arm && ELF_ST_TYPE(sym->st_info) == STT_FUNC)
  88                                 table->addr &= ~1;
  89
  90                         table++;
  91                 }
  92         }
  93
  94         if (table_size != 0)
  95                 fatal("%s: size mismatch\n", __func__);
  96 }
  97
  98 /*
  99  * Do any fixups on the table after sorting.
 100  * For now, this just finds adjacent entries which have
 101  * the same section_index and addr, and it propagates
 102  * the first symbol_index over the subsequent entries,
 103  * so that only one symbol_index is seen for any given
 104  * section_index and addr.  This ensures that whether
 105  * we're looking at an address from "above" or "below"
 106  * that we see the same symbol_index.
 107  * This does leave some duplicate entries in the table;
 108  * in practice, these are a small fraction of the
 109  * total number of entries, and they are harmless to
 110  * the binary search algorithm other than a few occasional
 111  * unnecessary comparisons.
 112  */
 113 static void symsearch_fixup(struct syminfo *table, unsigned int table_size)
 114 {
 115         /* Don't look at index 0, it will never change. */
 116         for (unsigned int i = 1; i < table_size; i++) {
 117                 if (table[i].addr == table[i - 1].addr &&
 118                     table[i].section_index == table[i - 1].section_index) {
 119                         table[i].symbol_index = table[i - 1].symbol_index;
 120                 }
 121         }
 122 }
 123
 124 void symsearch_init(struct elf_info *elf)
 125 {
 126         unsigned int table_size = symbol_count(elf);
 127
 128         elf->symsearch = NOFAIL(malloc(sizeof(struct symsearch) +
 129                                        sizeof(struct syminfo) * table_size));
 130         elf->symsearch->table_size = table_size;
 131
 132         symsearch_populate(elf, elf->symsearch->table, table_size);
 133         qsort(elf->symsearch->table, table_size,
 134               sizeof(struct syminfo), syminfo_compare);
 135
 136         symsearch_fixup(elf->symsearch->table, table_size);
 137 }
 138
 139 void symsearch_finish(struct elf_info *elf)
 140 {
 141         free(elf->symsearch);
 142         elf->symsearch = NULL;
 143 }
 144
 145 /*
 146  * Find the syminfo which is in secndx and "nearest" to addr.
 147  * allow_negative: allow returning a symbol whose address is > addr.
 148  * min_distance: ignore symbols which are further away than this.
 149  *
 150  * Returns a pointer into the symbol table for success.
 151  * Returns NULL if no legal symbol is found within the requested range.
 152  */
 153 Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr,
 154                                 unsigned int secndx, bool allow_negative,
 155                                 Elf_Addr min_distance)
 156 {
 157         unsigned int hi = elf->symsearch->table_size;
 158         unsigned int lo = 0;
 159         struct syminfo *table = elf->symsearch->table;
 160         struct syminfo target;
 161
 162         target.addr = addr;
 163         target.section_index = secndx;
 164         target.symbol_index = ~0;  /* compares greater than any actual index */
 165         while (hi > lo) {
 166                 unsigned int mid = lo + (hi - lo) / 2;  /* Avoids overflow */
 167
 168                 if (syminfo_compare(&table[mid], &target) > 0)
 169                         hi = mid;
 170                 else
 171                         lo = mid + 1;
 172         }
 173
 174         /*
 175          * table[hi], if it exists, is the first entry in the array which
 176          * lies beyond target.  table[hi - 1], if it exists, is the last
 177          * entry in the array which comes before target, including the
 178          * case where it perfectly matches the section and the address.
 179          *
 180          * Note -- if the address we're looking up falls perfectly
 181          * in the middle of two symbols, this is written to always
 182          * prefer the symbol with the lower address.
 183          */
 184         Elf_Sym *result = NULL;
 185
 186         if (allow_negative &&
 187             hi < elf->symsearch->table_size &&
 188             table[hi].section_index == secndx &&
 189             table[hi].addr - addr <= min_distance) {
 190                 min_distance = table[hi].addr - addr;
 191                 result = &elf->symtab_start[table[hi].symbol_index];
 192         }
 193         if (hi > 0 &&
 194             table[hi - 1].section_index == secndx &&
 195             addr - table[hi - 1].addr <= min_distance) {
 196                 result = &elf->symtab_start[table[hi - 1].symbol_index];
 197         }
 198         return result;
 199 }