| 1 | |
| 2 |
|
| 3 | |
| 4 | * Helper functions for finding the symbol in an ELF which is "nearest"
|
| 5 | * to a given address.
|
| 6 |
|
| 7 | #include <xalloc.h>
|
| 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 |
|
| 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 = xmalloc(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;
|
| 165 | while (hi > lo) {
|
| 166 | unsigned int mid = lo + (hi - lo) / 2;
|
| 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 | }
|