java-topology/defects/openmw-0004/test/openmw-0004-test.cpp

// openmw-0004-test.cpp
// CWE-407: objectpaging.cpp mMovedRefs std::find O(R*M) per cell during paging
//
// In ObjectPaging::createChunk, for every reference read from a cell ESM file,
// std::find(cell->mMovedRefs.begin(), cell->mMovedRefs.end(), ref.mRefNum) is
// called. This is the same mMovedRefs linear-scan pattern as openmw-0003, but
// in the object paging codepath which processes many cells during terrain loading.
//
// Fix: build unordered_set of moved ref numbers once per cell, O(1) lookups.

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdio>
#include <list>
#include <unordered_set>
#include <vector>

struct RefNum {
    int mIndex;
    int mContentFile;

    bool operator==(const RefNum& other) const {
        return mIndex == other.mIndex && mContentFile == other.mContentFile;
    }

    struct Hash {
        size_t operator()(const RefNum& r) const {
            return std::hash<long long>()(((long long)r.mContentFile << 32) | (unsigned)r.mIndex);
        }
    };
};

struct MovedCellRef {
    RefNum mRefNum;
    bool operator==(const RefNum& ref) const {
        return mRefNum == ref;
    }
};

using MovedCellRefTracker = std::list<MovedCellRef>;

struct Cell {
    MovedCellRefTracker mMovedRefs;
};

// Simulate processing refs from multiple cells (object paging processes many cells)
// ---------- DEFECTIVE ----------
int processPageDefective(const std::vector<Cell>& cells, const std::vector<std::vector<RefNum>>& cellRefs) {
    int processed = 0;
    for (size_t c = 0; c < cells.size(); c++) {
        for (const auto& ref : cellRefs[c]) {
            // O(M) per ref per cell
            if (std::find(cells[c].mMovedRefs.begin(), cells[c].mMovedRefs.end(), ref)
                != cells[c].mMovedRefs.end())
                continue;
            processed++;
        }
    }
    return processed;
}

// ---------- PATCHED ----------
int processPagePatched(const std::vector<Cell>& cells, const std::vector<std::vector<RefNum>>& cellRefs) {
    int processed = 0;
    for (size_t c = 0; c < cells.size(); c++) {
        // Build set once per cell
        std::unordered_set<RefNum, RefNum::Hash> movedSet;
        movedSet.reserve(cells[c].mMovedRefs.size());
        for (const auto& moved : cells[c].mMovedRefs)
            movedSet.insert(moved.mRefNum);

        for (const auto& ref : cellRefs[c]) {
            if (movedSet.count(ref))
                continue;
            processed++;
        }
    }
    return processed;
}

int main() {
    const int numCells = 25;   // typical paging chunk processes ~25 cells
    const int refsPerCell = 500;
    const int movedPerCell = 100;

    std::vector<Cell> cells(numCells);
    std::vector<std::vector<RefNum>> cellRefs(numCells);

    for (int c = 0; c < numCells; c++) {
        for (int i = 0; i < refsPerCell; i++)
            cellRefs[c].push_back({i, c});
        for (int i = 0; i < movedPerCell; i++)
            cells[c].mMovedRefs.push_back({{i * 4, c}});
    }

    // Correctness
    int r1 = processPageDefective(cells, cellRefs);
    int r2 = processPagePatched(cells, cellRefs);
    assert(r1 == r2);
    printf("PASS correctness: both processed %d refs (%d cells x %d refs)\n",
           r1, numCells, refsPerCell);

    // Performance
    auto bench = [&](auto fn) {
        auto t0 = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < 100; i++)
            fn(cells, cellRefs);
        auto t1 = std::chrono::high_resolution_clock::now();
        return std::chrono::duration<double, std::milli>(t1 - t0).count() / 100.0;
    };

    double defMs = bench(processPageDefective);
    double patMs = bench(processPagePatched);
    double ratio = defMs / patMs;

    printf("Defective: %.2f ms  Patched: %.2f ms  Ratio: %.1fx\n", defMs, patMs, ratio);
    assert(ratio > 2.0 && "Patched should be at least 2x faster");
    printf("PASS performance: %.1fx speedup\n", ratio);

    return 0;
}