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
syminfo_compare(const void * s1,const void * s2)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
symbol_count(struct elf_info * elf)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 */
symsearch_populate(struct elf_info * elf,struct syminfo * table,unsigned int table_size)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 */
symsearch_fixup(struct syminfo * table,unsigned int table_size)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
symsearch_init(struct elf_info * elf)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
symsearch_finish(struct elf_info * elf)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 */
symsearch_find_nearest(struct elf_info * elf,Elf_Addr addr,unsigned int secndx,bool allow_negative,Elf_Addr min_distance)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