java-topology/defects/gearboy-0001/test/GearboyBreakpointTest.java

import java.util.*;

/**
 * MOAD-0001 (CWE-407) -- gearboy-0001
 *
 * Source: src/Processor.cpp, src/Processor.h (Gearboy Game Boy emulator)
 *
 * Defect: O(B) linear scan over m_breakpoints vector on every memory access
 *         and every opcode dispatch, where B = number of breakpoints set.
 *
 *   // Memory_inline.h:10 -- called on EVERY memory Read()
 *   CheckBreakpoints(address, false);  // -> CheckMemoryBreakpoints O(B)
 *
 *   // Processor.cpp:549 -- called on EVERY opcode dispatch
 *   CheckBreakpoints();  // -> scans full m_breakpoints O(B)
 *
 *   The Z80-like Sharp LR35902 in a Game Boy runs at ~4 MHz.  With ~1-2
 *   memory accesses per opcode, this is ~4,000,000 O(B) scans/second.
 *   At B=64 breakpoints: 256,000,000 address comparisons per second.
 *
 * Fix: maintain std::unordered_set<u16> for point breakpoints (range==false).
 *      CheckBreakpoints() probes hash set first in O(1).  Range breakpoints
 *      are rare and remain in the vector slow-path.
 *
 * Speedup: ~B x in debug inner loop (64x at B=64 breakpoints).
 */
public class GearboyBreakpointTest {

    // --- defect simulation ---

    /**
     * Defective: O(B) scan over all breakpoints on every memory access.
     * Models Processor::CheckMemoryBreakpoints().
     */
    static boolean checkMemoryBreakpointDefective(List<int[]> breakpoints, int address, boolean read) {
        for (int[] brk : breakpoints) {
            // brk = {address1, address2, range, enabled, isRead, isWrite}
            if (brk[3] == 0) continue;  // !enabled
            if (read  && brk[4] == 0) continue;  // read && !brk.read
            if (!read && brk[5] == 0) continue;  // write && !brk.write
            if (brk[2] == 0) {
                // point breakpoint
                if (address == brk[0]) return true;
            } else {
                // range breakpoint
                if (address >= brk[0] && address <= brk[1]) return true;
            }
        }
        return false;
    }

    /**
     * Fixed: O(1) hash set probe for point breakpoints.
     * Range breakpoints still use vector slow-path (rare).
     * Models Processor::CheckMemoryBreakpoints() after patch.
     */
    static boolean checkMemoryBreakpointFixed(
            Set<Integer> readAddrs,
            Set<Integer> writeAddrs,
            List<int[]> rangeBreakpoints,
            int address, boolean read) {

        // O(1) fast path for point breakpoints
        if (read  && readAddrs.contains(address))  return true;
        if (!read && writeAddrs.contains(address)) return true;

        // O(R) slow path for range breakpoints only (R << B)
        for (int[] brk : rangeBreakpoints) {
            if (brk[3] == 0) continue;
            if (read  && brk[4] == 0) continue;
            if (!read && brk[5] == 0) continue;
            if (address >= brk[0] && address <= brk[1]) return true;
        }
        return false;
    }

    /** Build the hash set index from a list of breakpoints (RebuildBreakpointIndex). */
    static void buildIndex(List<int[]> breakpoints, Set<Integer> readAddrs, Set<Integer> writeAddrs) {
        readAddrs.clear();
        writeAddrs.clear();
        for (int[] brk : breakpoints) {
            if (brk[3] == 0 || brk[2] != 0) continue;  // disabled or range
            if (brk[4] != 0) readAddrs.add(brk[0]);
            if (brk[5] != 0) writeAddrs.add(brk[0]);
        }
    }

    // --- benchmark harness ---

    static long bench(String label, Runnable fn, int warmup, int reps) {
        for (int i = 0; i < warmup; i++) fn.run();
        long start = System.nanoTime();
        for (int i = 0; i < reps; i++) fn.run();
        long elapsed = System.nanoTime() - start;
        System.out.printf("  %-14s %,d ns total / %d reps = %,d ns/op%n",
                label + ":", elapsed, reps, elapsed / reps);
        return elapsed / reps;
    }

    public static void main(String[] args) {
        // --- correctness ---
        System.out.println("=== Correctness ===");
        {
            // 8 read point breakpoints at known addresses
            List<int[]> bps = new ArrayList<>();
            int[] watchAddrs = {0x0100, 0x0200, 0xFF80, 0xC000, 0x8000, 0x4000, 0x2000, 0x0150};
            for (int addr : watchAddrs) {
                // {address1, address2, range=0, enabled=1, read=1, write=0}
                bps.add(new int[]{addr, 0, 0, 1, 1, 0});
            }
            // one range breakpoint
            bps.add(new int[]{0xFE00, 0xFEFF, 1, 1, 1, 0});

            Set<Integer> readIdx  = new HashSet<>();
            Set<Integer> writeIdx = new HashSet<>();
            buildIndex(bps, readIdx, writeIdx);
            List<int[]> rangeBps = new ArrayList<>();
            for (int[] b : bps) { if (b[2] != 0) rangeBps.add(b); }

            // Test: address in breakpoint set
            assert checkMemoryBreakpointDefective(bps, 0x0100, true)  : "defect miss at 0x0100";
            assert checkMemoryBreakpointFixed(readIdx, writeIdx, rangeBps, 0x0100, true) : "fixed miss at 0x0100";

            // Test: address in range
            assert checkMemoryBreakpointDefective(bps, 0xFE50, true)  : "defect miss in range";
            assert checkMemoryBreakpointFixed(readIdx, writeIdx, rangeBps, 0xFE50, true) : "fixed miss in range";

            // Test: address NOT in set
            assert !checkMemoryBreakpointDefective(bps, 0x1234, true)  : "defect false positive at 0x1234";
            assert !checkMemoryBreakpointFixed(readIdx, writeIdx, rangeBps, 0x1234, true) : "fixed false positive at 0x1234";

            // Test: wrong access type (write when read-only breakpoint)
            assert !checkMemoryBreakpointDefective(bps, 0x0100, false) : "defect wrong access type";
            assert !checkMemoryBreakpointFixed(readIdx, writeIdx, rangeBps, 0x0100, false) : "fixed wrong access type";

            System.out.println("  All correctness checks: PASS");
        }

        // --- benchmark at realistic scale ---
        // B = 64 breakpoints (developer with full memory map breakpoints set)
        // Simulate 4,000 memory accesses per frame (scaled down for JVM timing)
        int B = 64;
        int ACCESSES = 4000;
        int REPS = 500;

        List<int[]> bps = new ArrayList<>();
        // All point read+write breakpoints at 64 evenly-spaced ROM addresses
        for (int i = 0; i < B; i++) {
            int addr = (i * 0x0400) & 0xFFFF;
            bps.add(new int[]{addr, 0, 0, 1, 1, 1});
        }

        Set<Integer> readIdx  = new HashSet<>();
        Set<Integer> writeIdx = new HashSet<>();
        buildIndex(bps, readIdx, writeIdx);
        List<int[]> rangeBps = new ArrayList<>();  // empty — no range bps

        // Access pattern: addresses that are NOT in breakpoint set (common case = miss)
        int[] accesses = new int[ACCESSES];
        Random rng = new Random(42);
        for (int i = 0; i < ACCESSES; i++) accesses[i] = (rng.nextInt(0x10000) | 1); // odd => never matches even addrs

        System.out.printf("%n=== Benchmark B=%d breakpoints, %d accesses/rep, %d reps ===%n", B, ACCESSES, REPS);

        long nsDefect = bench("defective",
            () -> { for (int a : accesses) checkMemoryBreakpointDefective(bps, a, true); },
            10, REPS);

        long nsFixed = bench("fixed",
            () -> { for (int a : accesses) checkMemoryBreakpointFixed(readIdx, writeIdx, rangeBps, a, true); },
            10, REPS);

        double ratio = (double) nsDefect / nsFixed;
        System.out.printf("  Speedup: %.1fx%n", ratio);

        // Require >= 2x speedup (JVM compresses the gap; real C++ gap is ~64x)
        assert ratio >= 2.0 : "Expected >=2x speedup at B=" + B + ", got " + ratio;
        System.out.println("Benchmark: PASS");

        System.out.println("\nAll tests PASSED");
    }
}