225 lines
7.8 KiB
C++
225 lines
7.8 KiB
C++
// Unit test for caprice32-0002: CWE-407 watchpoint linear scan O(W) per memory access
|
|
//
|
|
// In src/z80.cpp, read_mem() and write_mem() -- called for every Z80 memory
|
|
// access -- scan the watchpoints vector with std::any_of:
|
|
// std::any_of(watchpoints.begin(), watchpoints.end(),
|
|
// [&](const auto& w) { return w.address == addr && (w.type & READ); })
|
|
//
|
|
// This is O(W) per memory access. A typical Z80 instruction performs 1-4 memory
|
|
// accesses, so with W watchpoints we pay O(4W) per instruction. Combined with
|
|
// ~4 MHz Z80 clock, this is ~16 million O(W) probes per second.
|
|
//
|
|
// Fix: maintain two std::unordered_set<dword> -- watchpoint_reads and
|
|
// watchpoint_writes -- kept in sync with the watchpoints vector.
|
|
// Inner loop becomes: watchpoint_reads.count(addr) or watchpoint_writes.count(addr)
|
|
// which is O(1) average.
|
|
//
|
|
// Compile: g++ -std=c++17 -O2 -o test_caprice32_0002 test_caprice32_0002.cpp
|
|
// Run: ./test_caprice32_0002
|
|
|
|
#include <cassert>
|
|
#include <cstdint>
|
|
#include <cstdio>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
typedef uint32_t dword;
|
|
typedef uint16_t word;
|
|
|
|
enum WatchpointType { READ = 1, WRITE = 2, READWRITE = 3 };
|
|
|
|
struct Watchpoint {
|
|
Watchpoint(word val, WatchpointType t) : address(val), type(t) {}
|
|
dword address;
|
|
WatchpointType type;
|
|
};
|
|
|
|
// --- DEFECT: O(W) std::any_of per memory access ---
|
|
struct DefectMemory {
|
|
std::vector<Watchpoint> watchpoints;
|
|
int last_read_scanned = 0;
|
|
int last_write_scanned = 0;
|
|
|
|
void add(Watchpoint wp) { watchpoints.push_back(wp); }
|
|
|
|
bool read_mem(word addr) {
|
|
last_read_scanned = 0;
|
|
if (!watchpoints.empty()) {
|
|
for (const auto& w : watchpoints) {
|
|
++last_read_scanned;
|
|
if (w.address == addr && (w.type & READ)) return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
|
|
bool write_mem(word addr) {
|
|
last_write_scanned = 0;
|
|
if (!watchpoints.empty()) {
|
|
for (const auto& w : watchpoints) {
|
|
++last_write_scanned;
|
|
if (w.address == addr && (w.type & WRITE)) return true;
|
|
}
|
|
}
|
|
return false;
|
|
}
|
|
};
|
|
|
|
// --- FIX: O(1) unordered_set lookup ---
|
|
struct FixedMemory {
|
|
std::vector<Watchpoint> watchpoints;
|
|
std::unordered_set<dword> watchpoint_reads;
|
|
std::unordered_set<dword> watchpoint_writes;
|
|
int last_read_scanned = 0;
|
|
int last_write_scanned = 0;
|
|
|
|
void add(Watchpoint wp) {
|
|
watchpoints.push_back(wp);
|
|
if (wp.type & READ) watchpoint_reads.insert(wp.address);
|
|
if (wp.type & WRITE) watchpoint_writes.insert(wp.address);
|
|
}
|
|
|
|
void remove_at(std::size_t idx) {
|
|
const auto& wp = watchpoints[idx];
|
|
// Only erase from sets if no other watchpoint covers this address+type.
|
|
bool other_read = false, other_write = false;
|
|
for (std::size_t i = 0; i < watchpoints.size(); i++) {
|
|
if (i == idx) continue;
|
|
if (watchpoints[i].address == wp.address) {
|
|
if (watchpoints[i].type & READ) other_read = true;
|
|
if (watchpoints[i].type & WRITE) other_write = true;
|
|
}
|
|
}
|
|
if (!other_read && (wp.type & READ)) watchpoint_reads.erase(wp.address);
|
|
if (!other_write && (wp.type & WRITE)) watchpoint_writes.erase(wp.address);
|
|
watchpoints.erase(watchpoints.begin() + idx);
|
|
}
|
|
|
|
bool read_mem(word addr) {
|
|
if (!watchpoints.empty()) {
|
|
if (watchpoint_reads.count(addr)) { last_read_scanned = 1; return true; }
|
|
}
|
|
last_read_scanned = 0;
|
|
return false;
|
|
}
|
|
|
|
bool write_mem(word addr) {
|
|
if (!watchpoints.empty()) {
|
|
if (watchpoint_writes.count(addr)) { last_write_scanned = 1; return true; }
|
|
}
|
|
last_write_scanned = 0;
|
|
return false;
|
|
}
|
|
};
|
|
|
|
static void test_defect_scans_all_on_miss() {
|
|
const int W = 500;
|
|
DefectMemory d;
|
|
for (int i = 0; i < W; ++i)
|
|
d.add(Watchpoint(word(0x4000 + i), READWRITE));
|
|
|
|
bool hit = d.read_mem(0x0000);
|
|
assert(!hit);
|
|
assert(d.last_read_scanned == W && "defect: all W watchpoints scanned for miss");
|
|
printf("PASS defect: %d watchpoints, read miss -> scanned %d\n", W, d.last_read_scanned);
|
|
|
|
hit = d.write_mem(0x0000);
|
|
assert(!hit);
|
|
assert(d.last_write_scanned == W && "defect: all W watchpoints scanned for write miss");
|
|
printf("PASS defect: %d watchpoints, write miss -> scanned %d\n", W, d.last_write_scanned);
|
|
}
|
|
|
|
static void test_fix_constant_work_on_miss() {
|
|
const int W = 500;
|
|
FixedMemory f;
|
|
for (int i = 0; i < W; ++i)
|
|
f.add(Watchpoint(word(0x4000 + i), READWRITE));
|
|
|
|
bool hit = f.read_mem(0x0000);
|
|
assert(!hit);
|
|
assert(f.last_read_scanned == 0 && "fix: O(1) hash miss costs 0 recorded scans");
|
|
printf("PASS fix: %d watchpoints, read miss -> scanned %d (O(1))\n", W, f.last_read_scanned);
|
|
|
|
hit = f.write_mem(0x0000);
|
|
assert(!hit);
|
|
assert(f.last_write_scanned == 0);
|
|
printf("PASS fix: %d watchpoints, write miss -> scanned %d (O(1))\n", W, f.last_write_scanned);
|
|
}
|
|
|
|
static void test_fix_detects_read_watchpoint() {
|
|
FixedMemory f;
|
|
f.add(Watchpoint(0x2000, READ));
|
|
f.add(Watchpoint(0x3000, WRITE));
|
|
|
|
assert(f.read_mem(0x2000) && "fix: READ watchpoint fires on read");
|
|
assert(!f.read_mem(0x3000) && "fix: WRITE-only watchpoint does not fire on read");
|
|
assert(f.write_mem(0x3000) && "fix: WRITE watchpoint fires on write");
|
|
assert(!f.write_mem(0x2000) && "fix: READ-only watchpoint does not fire on write");
|
|
printf("PASS fix: watchpoint type separation (READ/WRITE) correct\n");
|
|
}
|
|
|
|
static void test_fix_readwrite_watchpoint() {
|
|
FixedMemory f;
|
|
f.add(Watchpoint(0x1000, READWRITE));
|
|
|
|
assert(f.read_mem(0x1000) && "fix: READWRITE watchpoint fires on read");
|
|
assert(f.write_mem(0x1000) && "fix: READWRITE watchpoint fires on write");
|
|
printf("PASS fix: READWRITE watchpoint fires on both read and write\n");
|
|
}
|
|
|
|
static void test_fix_remove_at_cleans_sets() {
|
|
FixedMemory f;
|
|
f.add(Watchpoint(0x5000, READ));
|
|
f.add(Watchpoint(0x6000, WRITE));
|
|
|
|
f.remove_at(0); // remove 0x5000/READ
|
|
|
|
assert(!f.read_mem(0x5000) && "fix: removed watchpoint no longer fires on read");
|
|
assert(f.write_mem(0x6000) && "fix: remaining watchpoint still fires");
|
|
printf("PASS fix: remove_at cleans sets correctly\n");
|
|
}
|
|
|
|
static void test_fix_remove_shared_address_preserved() {
|
|
// Two watchpoints at same address, different types. Remove one, other survives.
|
|
FixedMemory f;
|
|
f.add(Watchpoint(0x7000, READ));
|
|
f.add(Watchpoint(0x7000, WRITE));
|
|
|
|
f.remove_at(0); // remove READ watchpoint; WRITE should remain
|
|
|
|
assert(!f.read_mem(0x7000) && "fix: READ watchpoint removed, no read hit");
|
|
assert(f.write_mem(0x7000) && "fix: WRITE watchpoint survives after sibling removed");
|
|
printf("PASS fix: shared-address partial remove keeps other type intact\n");
|
|
}
|
|
|
|
static void test_speedup_ratio() {
|
|
const int W = 500;
|
|
DefectMemory d;
|
|
FixedMemory f;
|
|
for (int i = 0; i < W; ++i) {
|
|
word addr = word(0xC000 + i);
|
|
d.add(Watchpoint(addr, READWRITE));
|
|
f.add(Watchpoint(addr, READWRITE));
|
|
}
|
|
|
|
d.read_mem(0x0000);
|
|
f.read_mem(0x0000);
|
|
|
|
printf("PASS speedup: defect=%d scans/read, fix=%d scans/read, ratio ~%dx\n",
|
|
d.last_read_scanned, f.last_read_scanned, d.last_read_scanned);
|
|
assert(d.last_read_scanned == W);
|
|
assert(f.last_read_scanned == 0);
|
|
}
|
|
|
|
int main() {
|
|
printf("--- caprice32-0002 CWE-407 watchpoint O(W) scan per memory access ---\n");
|
|
test_defect_scans_all_on_miss();
|
|
test_fix_constant_work_on_miss();
|
|
test_fix_detects_read_watchpoint();
|
|
test_fix_readwrite_watchpoint();
|
|
test_fix_remove_at_cleans_sets();
|
|
test_fix_remove_shared_address_preserved();
|
|
test_speedup_ratio();
|
|
printf("ALL PASS\n");
|
|
return 0;
|
|
}
|