callgraph-verify 0.1.7

//! Performance-regression guards for the whole-`.text` scans.
//!
//! `has_direct_branch_target` used to byte-scan the ENTIRE `.text` blob on
//! every call. The proc-macro calls it once per `#[origin]` expansion (for
//! the ORIGIN-UNREFERENCED / vtable-only-dispatch gates), so a 6 MB `.text`
//! × ~1800 tagged fns turned a rebuild's compile into a ~30-minute
//! scan-fest. The fix caches all rel32 branch targets in one pass; these
//! tests fail loudly if a future change reintroduces per-call rescanning.
//!
//! The timing assertion is SELF-CALIBRATING instead of absolute: it compares
//! a batch of repeat lookups against the one-time warmup cost on the same
//! PE, so it holds on any machine speed and in both debug and release. A
//! rescan-per-call implementation makes the batch cost ~200 scans
//! (≈200× warmup); a cached one costs ~warmup/1000. The threshold
//! (`batch*2 < warmup`) sits between them with ~400× margin on each side.
//!
//! Wall-clock tests are inherently noisy, so this file removes the two
//! noise sources it controls: all three tests serialize on `SERIAL` (cargo
//! runs tests in one binary on parallel threads, and the sibling tests'
//! own 4 MB scans — done while holding the caches' global locks — would
//! otherwise contend with the measured batch), and the threshold tolerates
//! ~500× slowdown of the batch before firing. What remains (a descheduled
//! box) cannot bridge a 400× gap without a real regression.

use callgraph_verify::{has_direct_branch_target, Pe};
use std::time::Instant;

/// Serializes the perf tests in this binary. Each test builds and decodes a
/// multi-MB synthetic PE, and the library caches involved do their one-time
/// full-`.text` scans while holding a process-global lock — so a sibling
/// test's scan would otherwise stall this file's measured lookup batch and
/// trip the timing assertion below. Cargo runs the test targets of one
/// binary on parallel threads, hence an explicit mutex rather than
/// execution order. Poisoning-safe: a panicking holder must not wedge the
/// remaining tests.
static SERIAL: std::sync::Mutex<()> = std::sync::Mutex::new(());

fn serial() -> std::sync::MutexGuard<'static, ()> {
    SERIAL.lock().unwrap_or_else(|e| e.into_inner())
}

/// Image base used by the synthetic PEs below (same convention as integration.rs).
const BASE: u64 = 0x0040_0000;
/// `.text` RVA — the builders map file offset 0x200 to this VA.
const TEXT_RVA: u32 = 0x1000;

/// Build a PE32 whose `.text` is `text_len` bytes of `fill` (padded with
/// 0x90 NOPs), followed by `code` at the START of the section. `fill` must
/// not contain 0xE8/0xE9/0x0F-8x bytes unless intended: the branch-target
/// scan is pure byte matching gated on instruction starts.
fn pe_with_text(fill: &[u8], code: &[u8], text_len: usize) -> Pe {
    assert!(fill.len() + code.len() <= text_len);
    let mut text: Vec<u8> = Vec::with_capacity(text_len);
    text.extend_from_slice(code);
    while text.len() < text_len {
        let room = text_len - text.len();
        let take = fill.len().min(room);
        text.extend_from_slice(&fill[..take]);
    }
    let text_raw = ((text.len() + 0x1ff) & !0x1ff) as u32;
    let e_lfanew: u32 = 0x40;
    // Section raw data lives at file offset `text_raw` and spans `text_raw`
    // bytes (raw_offset == raw_size == text_raw, like integration.rs's
    // builder), so the file must be ~2× text_raw long.
    let mut data: Vec<u8> = vec![0; 0x400 + text_raw as usize * 2];
    data[0..2].copy_from_slice(b"MZ");
    data[0x3c..0x40].copy_from_slice(&e_lfanew.to_le_bytes());
    let pe_off = e_lfanew as usize;
    data[pe_off..pe_off + 4].copy_from_slice(b"PE\0\0");
    let coff = pe_off + 4;
    data[coff..coff + 2].copy_from_slice(&0x014cu16.to_le_bytes());
    data[coff + 2..coff + 4].copy_from_slice(&1u16.to_le_bytes());
    data[coff + 16..coff + 18].copy_from_slice(&0x60u16.to_le_bytes());
    let opt = coff + 20;
    data[opt..opt + 2].copy_from_slice(&0x010bu16.to_le_bytes());
    data[opt + 28..opt + 32].copy_from_slice(&(BASE as u32).to_le_bytes());
    let sec_off = opt + 0x60;
    data[sec_off..sec_off + 8].copy_from_slice(b".text\0\0\0");
    data[sec_off + 8..sec_off + 12].copy_from_slice(&(text.len() as u32).to_le_bytes());
    data[sec_off + 12..sec_off + 16].copy_from_slice(&TEXT_RVA.to_le_bytes());
    data[sec_off + 16..sec_off + 20].copy_from_slice(&text_raw.to_le_bytes());
    data[sec_off + 20..sec_off + 24].copy_from_slice(&text_raw.to_le_bytes());
    data[text_raw as usize..text_raw as usize + text.len()].copy_from_slice(&text);
    Pe::parse(data).expect("parse")
}

/// 3-byte canonical NOP — no branch opcodes, keeps the instruction count
/// (and thus the one-time decode cost) at |text|/3.
const NOP_FILL: &[u8] = &[0x0F, 0x1F, 0x00];
/// 4 MB of `.text` — same order of magnitude as a real 6.4 MB PE.
const TEXT_LEN: usize = 4 * 1024 * 1024;

/// REGRESSION GUARD: repeat `has_direct_branch_target` lookups must be
/// amortized lookups, not full `.text` rescans.
///
/// Calibration: the FIRST call pays the one-time decode of 4 MB of `.text`
/// plus one scan; the next 200 calls against a cached implementation cost
/// microseconds combined. If a change reintroduces the per-call byte scan,
/// the batch costs ~200 scans (≈200× warmup) and fails `batch*2 < warmup`
/// by ~400×. Serialized on `SERIAL` so sibling tests' own full scans
/// cannot contend with the measured batch.
#[test]
fn has_direct_branch_target_repeat_lookups_are_not_rescans() {
    let _guard = serial();
    // No branch opcodes anywhere → every lookup below is a MISS, which was
    // the worst case for the old scanner (it walked to the end of .text to
    // conclude "no branch targets this address").
    let pe = pe_with_text(NOP_FILL, &[], TEXT_LEN);
    let first = BASE + TEXT_RVA as u64;

    let t0 = Instant::now();
    assert!(!has_direct_branch_target(&pe, first));
    let warmup = t0.elapsed();
    assert!(
        warmup.as_millis() > 0,
        "warmup did no measurable work — test PE too small to calibrate against"
    );

    const N: u32 = 200;
    let t1 = Instant::now();
    for k in 0..N {
        // Distinct, in-.text addresses; all miss.
        let a = BASE + TEXT_RVA as u64 + (k as u64 * 16) + 1;
        assert!(!has_direct_branch_target(&pe, a));
    }
    let batch = t1.elapsed();

    assert!(
        batch * 2 < warmup,
        "200 repeat lookups took {batch:?} vs {warmup:?} for the first (warmup) call — \
         has_direct_branch_target is rescanning .text per call; the all-branch-targets \
         cache in lib.rs was dropped or its key stopped matching"
    );
}

/// The branch-target cache key must distinguish same-layout PEs with
/// DIFFERENT `.text` bytes (test binaries, a rebuilt exe). If the key ever
/// loses the content component (the BUG #9 input-ignoring-cache class), the
/// second PE inherits the first's target set and this test fails
/// deterministically — no timing involved.
#[test]
fn has_direct_branch_target_cache_distinguishes_same_layout_pes() {
    // Serialized: this test's 4 KB scans are cheap, but running them while
    // the timing test above measures its batch would inject lock contention
    // into that measurement. See SERIAL.
    let _guard = serial();
    // PE A: pure NOP sled — nothing is a branch target.
    let pe_a = pe_with_text(NOP_FILL, &[], 0x1000);
    // PE B: identical header layout, but starts with `CALL rel32` (rel 0 →
    // targets its own next_ip, offset 5) followed by RET, padded with the
    // same NOP fill.
    let pe_b = pe_with_text(NOP_FILL, &[0xE8, 0x00, 0x00, 0x00, 0x00, 0xC3], 0x1000);
    let call_target = BASE + TEXT_RVA as u64 + 5;

    // Warm any cache entry PE A might create, then prove the lookups disagree.
    assert!(!has_direct_branch_target(&pe_a, call_target));
    assert!(
        has_direct_branch_target(&pe_b, call_target),
        "PE B's CALL target not found — the branch-target cache treated PE B \
         as PE A (cache key ignores PE identity/content)"
    );
    // And in the other order: a fresh process ordering must behave the same.
    let pe_c = pe_with_text(NOP_FILL, &[0xE8, 0x00, 0x00, 0x00, 0x00, 0xC3], 0x2000);
    let pe_d = pe_with_text(NOP_FILL, &[], 0x2000);
    assert!(has_direct_branch_target(&pe_c, call_target));
    assert!(!has_direct_branch_target(&pe_d, call_target));
}

/// A `.text` HIT must still be found after the cache is warm (guards the
/// cache build itself: a broken one-pass builder could produce an empty set
/// that makes every lookup miss "fast").
#[test]
fn has_direct_branch_target_finds_hits_in_large_text() {
    // Serialized for the same reason: a 4 MB decode+scan while the timing
    // test measures would contend on the caches' global locks. See SERIAL.
    let _guard = serial();
    // A CALL buried in the NOP fill (at an instruction boundary — the fill is
    // 3-byte NOPs, so offset 3*k starts an instruction) whose rel32 targets
    // its own next_ip: `E8 00 00 00 00` at code offset 3 → target offset 8.
    let mut code = vec![0x0F, 0x1F, 0x00];
    code.extend_from_slice(&[0xE8, 0x00, 0x00, 0x00, 0x00]);
    let pe = pe_with_text(NOP_FILL, &code, TEXT_LEN);
    let call_target = BASE + TEXT_RVA as u64 + 8;

    assert!(
        has_direct_branch_target(&pe, call_target),
        "the buried CALL target must be found in the cached branch-target set"
    );
    // A miss inside the same PE stays a miss.
    assert!(!has_direct_branch_target(
        &pe,
        BASE + TEXT_RVA as u64 + 0x40
    ));
}