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
 10struct 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 */
 25struct symsearch {
 26	unsigned int table_size;
 27	struct syminfo table[];
 28};
 29
 30static 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
 50static 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 */
 68static 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 */
113static 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
124void 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
139void 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 */
153Elf_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}