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(info: 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, table: elf->symsearch->table, table_size); |
133 | qsort(base: elf->symsearch->table, nmemb: table_size, |
134 | size: sizeof(struct syminfo), compar: syminfo_compare); |
135 | |
136 | symsearch_fixup(table: elf->symsearch->table, table_size); |
137 | } |
138 | |
139 | void symsearch_finish(struct elf_info *elf) |
140 | { |
141 | free(ptr: 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(s1: &table[mid], s2: &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 | |