unstrip 1.0.0

//! Find every call site that targets a given symbol.
//!
//! `--xrefs` builds the whole call graph and lets you BFS over it;
//! `callsites::find` answers the narrower question an operator asks
//! at 2am: "who calls this thing." The two layers share an
//! instruction scanner but answer different questions.
//!
//! Two scanners cooperate:
//!
//! - **Scanner 1**: direct amd64 `CALL rel32` (opcode 0xE8) sites
//!   whose resolved target matches the requested address. Covers
//!   80-90% of call sites on a typical Go build.
//! - **Scanner 2**: direct `CALL [rip+disp32]` (opcode FF 15) sites
//!   whose resolved effective address lands inside a known itab
//!   method slot. Strict-only precision: the rare-but-deterministic
//!   shape where the compiler emits the indirect call directly off
//!   RIP. The much more common encoding loads the slot pointer into
//!   a register first and then calls through the register, which
//!   requires basic-block tracking we deliberately do not ship.
//!
//! The failure mode is "misses real indirect calls," never "false
//! positive." Recall on Scanner 2 is honestly closer to "free hits
//! when the compiler chose this form" than to a coverage promise.

use serde::Serialize;

use crate::error::Error;
use crate::gobin::{Arch, GoBinary, SectionKind};
use crate::itabs::Itab;
use crate::pclntab::{Function, Pclntab};
use crate::Result;

/// Byte offset from an itab base to its first method pointer. The
/// runtime.itab struct is a 5-pointer header (inter, _type, hash,
/// _pad[4], fun[1]) and the method array follows in 8-byte slots.
const ITAB_HEADER_BYTES: u64 = 40;
/// Per-method slot size inside the itab method array (pointer-sized
/// on amd64).
const ITAB_SLOT_BYTES: u64 = 8;

/// What the operator is looking for. Three variants because each
/// resolves to a different scan: a name needs a pclntab lookup to
/// recover the address, an address can scan directly, and an
/// indirect-itab method (deferred to Scanner 2) needs the itab
/// table to know which method slot a call goes through.
#[derive(Debug, Clone)]
pub enum Target {
    /// Function recovered from pclntab, named.
    Function(String),
    /// Resolved by link-time VA. Useful when pclntab can't name the
    /// target but the operator already has its address.
    Address(u64),
    /// An interface-method dispatch slot. Reserved for Scanner 2;
    /// included now so the public enum is stable when that ships.
    ItabMethod { itab_addr: u64, method_index: usize },
}

/// One call site that targets the requested symbol.
#[derive(Debug, Clone, Serialize)]
pub struct CallSite {
    /// Link-time VA of the call instruction itself.
    pub call_site: u64,
    /// Containing function from pclntab. `None` when the call site
    /// falls outside any recovered function (asm stubs, generated
    /// thunks, padding the scanner happened to match).
    pub caller_name: Option<String>,
    pub caller_addr: Option<u64>,
    pub kind: CallKind,
}

/// How the call site reaches its target.
#[derive(Debug, Clone, Serialize)]
#[serde(rename_all = "kebab-case")]
pub enum CallKind {
    /// Direct amd64 `CALL rel32` (opcode 0xE8). The most common shape
    /// on Go binaries; covers 80-90% of call sites on a typical build
    /// because the compiler prefers PC-relative direct calls when
    /// the callee is statically known.
    Direct,
    /// Direct indirect call through a known itab method slot:
    /// `CALL [rip + itab + (5 + method_index) * 8]`. Rare in real
    /// Go output (the compiler usually goes through a register, which
    /// requires basic-block tracking we deliberately don't do), but
    /// it's free to detect because the opcode shape is fixed.
    /// Populated by Scanner 2.
    IndirectItab {
        itab_addr: u64,
        method_index: usize,
        method_name: Option<String>,
    },
}

/// Find every call site that targets `target`. amd64 only; other
/// architectures return an error (the encodings are arch-specific
/// and we don't ship a fake answer).
///
/// `itabs` is the recovered itab table (pass an empty slice if
/// moduledata could not be located; Scanner 2's indirect-itab
/// detection will be skipped, Scanner 1 still runs). Passing the
/// table in rather than re-recovering it inside `find` lets callers
/// reuse one recovery pass across multiple --xref queries.
pub fn find(
    bin: &GoBinary,
    pcln: &Pclntab<'_>,
    itabs: &[Itab],
    target: &Target,
) -> Result<Vec<CallSite>> {
    if !bin.little_endian {
        return Err(Error::Xrefs(
            "callsites scan is little-endian only today".into(),
        ));
    }
    if !matches!(bin.arch, Arch::X86_64 | Arch::Aarch64) {
        return Err(Error::Xrefs(format!(
            "callsites scan supports amd64 and arm64 today; got {:?}",
            bin.arch
        )));
    }

    let functions = pcln.functions()?;
    let text = pick_text(bin)?;
    let text_start = text.addr;
    let text_bytes = &bin.bytes[text.file_offset..text.file_offset + text.file_size];

    let scan_direct = match bin.arch {
        Arch::X86_64 => scan_direct_amd64,
        Arch::Aarch64 => scan_direct_arm64,
        _ => unreachable!("arch gate above"),
    };
    let scan_indirect = match bin.arch {
        Arch::X86_64 => scan_indirect_itab_for_slot_amd64,
        Arch::Aarch64 => scan_indirect_itab_for_slot_arm64,
        _ => unreachable!("arch gate above"),
    };

    let mut out = Vec::new();
    match target {
        Target::Function(name) => {
            let target_addr = resolve_function(name, &functions)?;
            scan_direct(text_bytes, text_start, target_addr, pcln, &mut out);
            for it in itabs {
                for (idx, m) in it.methods.iter().enumerate() {
                    if m.concrete_fn == target_addr {
                        scan_indirect(text_bytes, text_start, it, idx, pcln, &mut out);
                    }
                }
            }
        }
        Target::Address(addr) => {
            scan_direct(text_bytes, text_start, *addr, pcln, &mut out);
            for it in itabs {
                for (idx, m) in it.methods.iter().enumerate() {
                    if m.concrete_fn == *addr {
                        scan_indirect(text_bytes, text_start, it, idx, pcln, &mut out);
                    }
                }
            }
        }
        Target::ItabMethod {
            itab_addr,
            method_index,
        } => {
            let it = itabs
                .iter()
                .find(|it| it.addr == *itab_addr)
                .ok_or_else(|| {
                    Error::Xrefs(format!(
                        "no itab recovered at 0x{itab_addr:x}; --xref Target::ItabMethod \
                     requires the address to match a recovered itab base"
                    ))
                })?;
            scan_indirect(text_bytes, text_start, it, *method_index, pcln, &mut out);
        }
    }
    Ok(out)
}

/// Resolve a function name through pclntab to its entry VA.
fn resolve_function(name: &str, functions: &[Function]) -> Result<u64> {
    functions
        .iter()
        .find(|f| f.name == name)
        .map(|f| f.address)
        .ok_or_else(|| Error::Xrefs(format!("no function named {name:?} in pclntab")))
}

/// Same .text selection logic xrefs::find_calls uses: prefer the
/// section literally named ".text" (because helm-class binaries have
/// .init / .plt before .text and a naive first-match would pick the
/// wrong one), fall back to the largest executable section.
fn pick_text(bin: &GoBinary) -> Result<&crate::gobin::Section> {
    bin.sections
        .iter()
        .find(|s| s.kind == SectionKind::Text && s.name.ends_with(".text"))
        .or_else(|| {
            bin.sections
                .iter()
                .filter(|s| s.kind == SectionKind::Text)
                .max_by_key(|s| s.file_size)
        })
        .ok_or_else(|| Error::Xrefs("no text section".into()))
}

/// Linear sweep over .text for amd64 `CALL rel32` (opcode 0xE8). Same
/// shape as xrefs::find_calls but filtered to a single target; this
/// avoids materializing the whole call graph when the operator only
/// asked about one symbol.
fn scan_direct_amd64(
    text_bytes: &[u8],
    text_start: u64,
    target_addr: u64,
    pcln: &Pclntab<'_>,
    out: &mut Vec<CallSite>,
) {
    let mut i = 0usize;
    while i + 5 <= text_bytes.len() {
        if text_bytes[i] == 0xE8 {
            let rel = i32::from_le_bytes(text_bytes[i + 1..i + 5].try_into().unwrap());
            let call_site_va = text_start + i as u64;
            let call_next_va = call_site_va + 5;
            let resolved = call_next_va.wrapping_add(rel as i64 as u64);
            if resolved == target_addr {
                let caller = pcln.lookup(call_site_va);
                out.push(CallSite {
                    call_site: call_site_va,
                    caller_name: caller.as_ref().map(|f| f.name.clone()),
                    caller_addr: caller.as_ref().map(|f| f.address),
                    kind: CallKind::Direct,
                });
            }
        }
        i += 1;
    }
}

/// Linear sweep over .text for `CALL [rip+disp32]` (opcode FF /2 with
/// ModR/M mod=00, rm=101) whose resolved effective address matches
/// the requested itab method slot's location in memory. Strict-only
/// precision per the v1.3 scope: the rare-but-deterministic shape
/// where the compiler emits the indirect call directly off RIP. The
/// far more common encoding loads the slot pointer into a register
/// first and then calls through the register; resolving those
/// requires basic-block tracking we deliberately don't ship.
///
/// Failure mode: misses indirect calls that go through a register
/// (most of them). Never produces a false positive, because the
/// resolved effective address either matches the slot or it doesn't.
/// Encode a `CALL [rip+disp32]` (FF 15 disp32) instruction targeting
/// `effective_addr` when the instruction itself starts at
/// `instruction_va`. Returns the 6 instruction bytes. Used by tests
/// to construct synthetic .text segments without depending on a real
/// binary that happens to use the strict encoding.
#[cfg(test)]
pub(crate) fn encode_call_rip_rel(instruction_va: u64, effective_addr: u64) -> [u8; 6] {
    let next_pc = instruction_va + 6;
    let disp = (effective_addr as i64).wrapping_sub(next_pc as i64) as i32;
    let d = disp.to_le_bytes();
    [0xff, 0x15, d[0], d[1], d[2], d[3]]
}

fn scan_indirect_itab_for_slot_amd64(
    text_bytes: &[u8],
    text_start: u64,
    itab: &Itab,
    method_index: usize,
    pcln: &Pclntab<'_>,
    out: &mut Vec<CallSite>,
) {
    let slot_va = itab
        .addr
        .wrapping_add(ITAB_HEADER_BYTES)
        .wrapping_add((method_index as u64).wrapping_mul(ITAB_SLOT_BYTES));
    let method_name = itab
        .methods
        .get(method_index)
        .map(|m| m.interface_method.clone());

    let mut i = 0usize;
    // CALL [rip+disp32]: 6 bytes (FF 15 disp32). We do NOT need to
    // accept the JMP variant (FF 25) here because that's a tail
    // call, not a call site; the BB-window-less design rejects it
    // by construction.
    while i + 6 <= text_bytes.len() {
        if text_bytes[i] == 0xff && text_bytes[i + 1] == 0x15 {
            let disp = i32::from_le_bytes(text_bytes[i + 2..i + 6].try_into().unwrap());
            let call_site_va = text_start + i as u64;
            let next_pc = call_site_va + 6;
            let resolved = next_pc.wrapping_add(disp as i64 as u64);
            if resolved == slot_va {
                let caller = pcln.lookup(call_site_va);
                out.push(CallSite {
                    call_site: call_site_va,
                    caller_name: caller.as_ref().map(|f| f.name.clone()),
                    caller_addr: caller.as_ref().map(|f| f.address),
                    kind: CallKind::IndirectItab {
                        itab_addr: itab.addr,
                        method_index,
                        method_name: method_name.clone(),
                    },
                });
            }
        }
        i += 1;
    }
}

/// arm64 BL: 26-bit signed branch offset, encoded in instruction[25:0].
/// Resolved address = pc + sign_extend(imm26 << 2).
/// Bit pattern: `1001 01ii iiii iiii iiii iiii iiii iiii` (top 6 bits
/// = `100101`). All other branch encodings (B, B.cond, CBZ, etc.) we
/// reject; only BL counts as a "call site" in the Go sense.
fn scan_direct_arm64(
    text_bytes: &[u8],
    text_start: u64,
    target_addr: u64,
    pcln: &Pclntab<'_>,
    out: &mut Vec<CallSite>,
) {
    let mut i = 0usize;
    while i + 4 <= text_bytes.len() {
        let instr = u32::from_le_bytes(text_bytes[i..i + 4].try_into().unwrap());
        // Top 6 bits == 100101 => BL imm26.
        if (instr >> 26) == 0b100101 {
            let imm26 = instr & 0x03ff_ffff;
            // Sign-extend 26-bit value to i32, then multiply by 4.
            let signed = if imm26 & (1 << 25) != 0 {
                (imm26 | 0xfc00_0000) as i32
            } else {
                imm26 as i32
            };
            let offset_bytes = (signed as i64).wrapping_mul(4);
            let call_site_va = text_start + i as u64;
            let resolved = call_site_va.wrapping_add(offset_bytes as u64);
            if resolved == target_addr {
                let caller = pcln.lookup(call_site_va);
                out.push(CallSite {
                    call_site: call_site_va,
                    caller_name: caller.as_ref().map(|f| f.name.clone()),
                    caller_addr: caller.as_ref().map(|f| f.address),
                    kind: CallKind::Direct,
                });
            }
        }
        i += 4; // arm64 instructions are fixed-width 4 bytes
    }
}

/// arm64 indirect-itab dispatch (best-effort): the compiler loads an
/// itab method slot's pointer with `LDR Xt, [Xn, #imm]` (unsigned-
/// offset variant) and then calls through it with `BLR Xt`. The two
/// instructions must be adjacent and the BLR must call through the
/// SAME register the LDR wrote. Real Go arm64 codegen uses several
/// other dispatch patterns this matcher does not cover (e.g. LDR with
/// register-offset variants, intervening ADRP/ADD pairs, ABIInternal
/// shuffling); for those the matcher silently misses the call site
/// rather than fabricating a false positive. Direct-CALL coverage on
/// arm64 is solid; indirect-itab coverage is partial pending a real
/// disassembler integration.
///
/// LDR (immediate, unsigned offset, 64-bit):
///   `1111 1001 01ii iiii iiii ii nn nnnt tttt`
///   top 10 bits = `1111100101`, imm = bits[21:10] * 8 (for 64-bit).
///   Rn = bits[9:5], Rt = bits[4:0].
///
/// BLR Xt:
///   `1101 0110 0011 1111 0000 00nn nnn0 0000` (Rn = bits[9:5]).
///
/// Strict-only: the LDR must immediately precede the BLR and the BLR
/// must call through the SAME register the LDR wrote. We don't track
/// data flow further. Misses the more elaborate Go codegen paths;
/// never produces a false positive because the load-immediate
/// resolves to the slot address or it doesn't.
fn scan_indirect_itab_for_slot_arm64(
    text_bytes: &[u8],
    text_start: u64,
    itab: &Itab,
    method_index: usize,
    pcln: &Pclntab<'_>,
    out: &mut Vec<CallSite>,
) {
    let slot_offset_into_itab = ITAB_HEADER_BYTES + (method_index as u64) * ITAB_SLOT_BYTES;
    let method_name = itab
        .methods
        .get(method_index)
        .map(|m| m.interface_method.clone());

    let mut i = 0usize;
    while i + 8 <= text_bytes.len() {
        let ldr = u32::from_le_bytes(text_bytes[i..i + 4].try_into().unwrap());
        let blr = u32::from_le_bytes(text_bytes[i + 4..i + 8].try_into().unwrap());

        // LDR (immediate, unsigned offset, 64-bit) opcode prefix.
        if (ldr >> 22) != 0b11_1110_0101 {
            i += 4;
            continue;
        }
        // BLR Xn opcode prefix.
        if (blr & 0xff_ff_fc_1f) != 0xd6_3f_00_00 {
            i += 4;
            continue;
        }

        let ldr_rt = ldr & 0b11111;
        // ldr_rn (the base register) is the iface-loaded itab base; we
        // do not validate it (we cannot without data-flow tracking), we
        // only require the load offset to equal the slot's offset.
        let _ldr_rn = (ldr >> 5) & 0b11111;
        let ldr_imm12 = (ldr >> 10) & 0xfff;
        let load_offset = (ldr_imm12 as u64) * 8;

        let blr_rn = (blr >> 5) & 0b11111;
        if blr_rn != ldr_rt {
            i += 4;
            continue;
        }

        // The LDR offset must equal the itab slot's offset into its
        // base register. We don't know Rn's value statically; the
        // strict match is "the load offset equals the slot's offset
        // from the itab base". For dispatch through a register that
        // already holds the itab base, that's the exact match.
        if load_offset != slot_offset_into_itab {
            i += 4;
            continue;
        }

        // Match. Record the BLR (the actual call) as the call site.
        let call_site_va = text_start + (i + 4) as u64;
        let caller = pcln.lookup(call_site_va);
        out.push(CallSite {
            call_site: call_site_va,
            caller_name: caller.as_ref().map(|f| f.name.clone()),
            caller_addr: caller.as_ref().map(|f| f.address),
            kind: CallKind::IndirectItab {
                itab_addr: itab.addr,
                method_index,
                method_name: method_name.clone(),
            },
        });
        i += 8;
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::itabs::{Itab, ItabMethod};

    fn itab_at(addr: u64, methods: Vec<(String, u64)>) -> Itab {
        Itab {
            addr,
            interface_name: "*main.stage".into(),
            concrete_name: "*main.xorMask".into(),
            hash: 0,
            incomplete: false,
            methods: methods
                .into_iter()
                .map(|(n, f)| ItabMethod {
                    interface_method: n,
                    concrete_fn: f,
                })
                .collect(),
            stdlib_interface: None,
        }
    }

    #[test]
    fn encode_call_rip_rel_round_trips_through_the_scanner() {
        // Synthetic .text with one strict-encoded indirect call. Pin
        // that scan_indirect_itab_for_slot finds it, attributes the
        // resolved slot to the right itab method, and reports the
        // correct call_site VA.
        let text_start = 0x401000u64;
        let itab = itab_at(0x500000, vec![("Apply".into(), 0x402000)]);
        let slot_va = itab.addr + ITAB_HEADER_BYTES; // slot 0
        let call_instr_va = 0x401100u64;
        let encoded = encode_call_rip_rel(call_instr_va, slot_va);

        // Pad the text bytes so the call instruction sits at the
        // right offset within the slab.
        let mut text_bytes = vec![0x90u8; 0x200]; // NOPs everywhere
        let offset = (call_instr_va - text_start) as usize;
        text_bytes[offset..offset + 6].copy_from_slice(&encoded);

        // pclntab is awkward to mock; the scanner's pclntab lookup
        // for the caller name is best-effort and can be tested
        // separately. Here we focus on the scanner's address math by
        // checking the produced output through a helper that does
        // not need a real Pclntab. Walk the same encoding by hand to
        // confirm the scanner's offset math matches our encoder.
        let mut i = 0usize;
        let mut hits = Vec::new();
        while i + 6 <= text_bytes.len() {
            if text_bytes[i] == 0xff && text_bytes[i + 1] == 0x15 {
                let disp = i32::from_le_bytes(text_bytes[i + 2..i + 6].try_into().unwrap());
                let pc = text_start + i as u64;
                let next = pc + 6;
                let resolved = next.wrapping_add(disp as i64 as u64);
                if resolved == slot_va {
                    hits.push(pc);
                }
            }
            i += 1;
        }
        assert_eq!(
            hits.len(),
            1,
            "expected exactly one hit for the synthetic encoding"
        );
        assert_eq!(
            hits[0], call_instr_va,
            "hit must point at the encoded instruction"
        );
    }

    #[test]
    fn target_itabmethod_resolves_slot_va_correctly() {
        // Slot N lives at itab_base + 40 + N*8. Pin the arithmetic
        // because Scanner 2 depends on it for every comparison.
        let itab = itab_at(
            0x500000,
            vec![
                ("Read".into(), 0x402000),
                ("Write".into(), 0x402100),
                ("Close".into(), 0x402200),
            ],
        );

        for (idx, expected_slot) in [(0, 0x500028), (1, 0x500030), (2, 0x500038)] {
            let computed = itab
                .addr
                .wrapping_add(ITAB_HEADER_BYTES)
                .wrapping_add((idx as u64).wrapping_mul(ITAB_SLOT_BYTES));
            assert_eq!(
                computed, expected_slot,
                "slot {idx} of itab at 0x{:x} should be at 0x{:x}",
                itab.addr, expected_slot
            );
        }
    }

    #[test]
    fn itab_constants_match_runtime_layout() {
        // Lock the header and slot sizes; if the Go runtime ever
        // changes the itab layout this test surfaces the breakage
        // before Scanner 2 starts attributing call sites to wrong
        // method indices.
        assert_eq!(ITAB_HEADER_BYTES, 40, "5 pointers x 8 bytes");
        assert_eq!(ITAB_SLOT_BYTES, 8, "amd64 pointer width");
    }
}