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 #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 /* 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 = 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; /* 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 } 200