// SPDX-License-Identifier: GPL-2.0

/*
 * Helper functions for finding the symbol in an ELF which is "nearest"
 * to a given address.
 */
#include <xalloc.h>
#include "modpost.h"

struct syminfo {
        unsigned int symbol_index;
        unsigned int section_index;
        Elf_Addr addr;
};

/*
 * Container used to hold an entire binary search table.
 * Entries in table are ascending, sorted first by section_index,
 * then by addr, and last by symbol_index.  The sorting by
 * symbol_index is used to ensure predictable behavior when
 * multiple symbols are present with the same address; all
 * symbols past the first are effectively ignored, by eliding
 * them in symsearch_fixup().
 */
struct symsearch {
        unsigned int table_size;
        struct syminfo table[];
};

static int syminfo_compare(const void *s1, const void *s2)
{
        const struct syminfo *sym1 = s1;
        const struct syminfo *sym2 = s2;

        if (sym1->section_index > sym2->section_index)
                return 1;
        if (sym1->section_index < sym2->section_index)
                return -1;
        if (sym1->addr > sym2->addr)
                return 1;
        if (sym1->addr < sym2->addr)
                return -1;
        if (sym1->symbol_index > sym2->symbol_index)
                return 1;
        if (sym1->symbol_index < sym2->symbol_index)
                return -1;
        return 0;
}

static unsigned int symbol_count(struct elf_info *elf)
{
        unsigned int result = 0;

        for (Elf_Sym *sym = elf->symtab_start; sym < elf->symtab_stop; sym++) {
                if (is_valid_name(elf, sym))
                        result++;
        }
        return result;
}

/*
 * Populate the search array that we just allocated.
 * Be slightly paranoid here.  The ELF file is mmap'd and could
 * conceivably change between symbol_count() and symsearch_populate().
 * If we notice any difference, bail out rather than potentially
 * propagating errors or crashing.
 */
static void symsearch_populate(struct elf_info *elf,
                               struct syminfo *table,
                               unsigned int table_size)
{
        bool is_arm = (elf->hdr->e_machine == EM_ARM);

        for (Elf_Sym *sym = elf->symtab_start; sym < elf->symtab_stop; sym++) {
                if (is_valid_name(elf, sym)) {
                        if (table_size-- == 0)
                                fatal("%s: size mismatch\n", __func__);
                        table->symbol_index = sym - elf->symtab_start;
                        table->section_index = get_secindex(elf, sym);
                        table->addr = sym->st_value;

                        /*
                         * For ARM Thumb instruction, the bit 0 of st_value is
                         * set if the symbol is STT_FUNC type. Mask it to get
                         * the address.
                         */
                        if (is_arm && ELF_ST_TYPE(sym->st_info) == STT_FUNC)
                                table->addr &= ~1;

                        table++;
                }
        }

        if (table_size != 0)
                fatal("%s: size mismatch\n", __func__);
}

/*
 * Do any fixups on the table after sorting.
 * For now, this just finds adjacent entries which have
 * the same section_index and addr, and it propagates
 * the first symbol_index over the subsequent entries,
 * so that only one symbol_index is seen for any given
 * section_index and addr.  This ensures that whether
 * we're looking at an address from "above" or "below"
 * that we see the same symbol_index.
 * This does leave some duplicate entries in the table;
 * in practice, these are a small fraction of the
 * total number of entries, and they are harmless to
 * the binary search algorithm other than a few occasional
 * unnecessary comparisons.
 */
static void symsearch_fixup(struct syminfo *table, unsigned int table_size)
{
        /* Don't look at index 0, it will never change. */
        for (unsigned int i = 1; i < table_size; i++) {
                if (table[i].addr == table[i - 1].addr &&
                    table[i].section_index == table[i - 1].section_index) {
                        table[i].symbol_index = table[i - 1].symbol_index;
                }
        }
}

void symsearch_init(struct elf_info *elf)
{
        unsigned int table_size = symbol_count(elf);

        elf->symsearch = xmalloc(sizeof(struct symsearch) +
                                       sizeof(struct syminfo) * table_size);
        elf->symsearch->table_size = table_size;

        symsearch_populate(elf, elf->symsearch->table, table_size);
        qsort(elf->symsearch->table, table_size,
              sizeof(struct syminfo), syminfo_compare);

        symsearch_fixup(elf->symsearch->table, table_size);
}

void symsearch_finish(struct elf_info *elf)
{
        free(elf->symsearch);
        elf->symsearch = NULL;
}

/*
 * Find the syminfo which is in secndx and "nearest" to addr.
 * allow_negative: allow returning a symbol whose address is > addr.
 * min_distance: ignore symbols which are further away than this.
 *
 * Returns a pointer into the symbol table for success.
 * Returns NULL if no legal symbol is found within the requested range.
 */
Elf_Sym *symsearch_find_nearest(struct elf_info *elf, Elf_Addr addr,
                                unsigned int secndx, bool allow_negative,
                                Elf_Addr min_distance)
{
        unsigned int hi = elf->symsearch->table_size;
        unsigned int lo = 0;
        struct syminfo *table = elf->symsearch->table;
        struct syminfo target;

        target.addr = addr;
        target.section_index = secndx;
        target.symbol_index = ~0;  /* compares greater than any actual index */
        while (hi > lo) {
                unsigned int mid = lo + (hi - lo) / 2;  /* Avoids overflow */

                if (syminfo_compare(&table[mid], &target) > 0)
                        hi = mid;
                else
                        lo = mid + 1;
        }

        /*
         * table[hi], if it exists, is the first entry in the array which
         * lies beyond target.  table[hi - 1], if it exists, is the last
         * entry in the array which comes before target, including the
         * case where it perfectly matches the section and the address.
         *
         * Note -- if the address we're looking up falls perfectly
         * in the middle of two symbols, this is written to always
         * prefer the symbol with the lower address.
         */
        Elf_Sym *result = NULL;

        if (allow_negative &&
            hi < elf->symsearch->table_size &&
            table[hi].section_index == secndx &&
            table[hi].addr - addr <= min_distance) {
                min_distance = table[hi].addr - addr;
                result = &elf->symtab_start[table[hi].symbol_index];
        }
        if (hi > 0 &&
            table[hi - 1].section_index == secndx &&
            addr - table[hi - 1].addr <= min_distance) {
                result = &elf->symtab_start[table[hi - 1].symbol_index];
        }
        return result;
}