java-topology/whitepaper/outreach/ppsspp.md

PPSSPP — CWE-407 Disclosure Brief

2026-04-13 · Patches available — awaiting upstream merge

Finding

Four O(n²) defects in PPSSPP across the HLE kernel thread, semaphore, and mutex synchronization primitives, plus the IR JIT block cache. All patched. Patches ready for upstream review. Three defects fire on every lock/wait contention timeout cycle; one fires on JIT block invalidation.

The Defects

ppsspp-0001 (PATCHED — MEDIUM): Core/HLE/sceKernelThread.cpp:2544

// In sceKernelWaitThreadEnd / sceKernelWaitThreadEndCB:
if (std::find(t->waitingThreads.begin(), t->waitingThreads.end(), currentThread) == t->waitingThreads.end())
    t->waitingThreads.push_back(currentThread);

waitingThreads holds thread IDs as a vector. std::find scans the entire vector before each push_back — O(W) per wait where W = waiting threads. In barrier-like patterns where many threads wait on the same target, total cost reaches O(W²).

ppsspp-0002 (PATCHED — MEDIUM): Core/HLE/sceKernelSemaphore.cpp:370

// In sceKernelWaitSema / sceKernelWaitSemaCB:
if (std::find(s->waitingThreads.begin(), s->waitingThreads.end(), threadID) == s->waitingThreads.end())
    s->waitingThreads.push_back(threadID);

Same pattern as ppsspp-0001 in the semaphore wait path. The code comment says "May be in a tight loop timing out (where we don't remove from waitingThreads yet), don't want to add duplicates." — that tight-loop scenario compounds the O(W) dedup cost.

ppsspp-0003 (PATCHED — MEDIUM): Core/MIPS/IR/IRJit.cpp:363

// In IRBlockCache::RemoveBlockFromPageLookup:
auto iter = std::find(byPage_[page].begin(), byPage_[page].end(), blockIndex);
if (iter != byPage_[page].end()) {
    byPage_[page].erase(iter);
}

byPage_[page] maps pages to compiled block indices as a vector. std::find scans the vector for block removal — O(B) per page where B = blocks in that page. Fires on every JIT block invalidation from sceKernelIcacheClearAll and self-modifying code patterns.

ppsspp-0004 (PATCHED — MEDIUM): Core/HLE/sceKernelMutex.cpp:547,569,951,986

// In sceKernelLockMutex / sceKernelLockMutexCB / sceKernelLockLwMutex / sceKernelLockLwMutexCB:
if (std::find(mutex->waitingThreads.begin(), mutex->waitingThreads.end(), threadID) == mutex->waitingThreads.end())
    mutex->waitingThreads.push_back(threadID);

Identical std::find dedup pattern at four call sites across mutex and lightweight mutex lock paths. Same tight-loop timeout scenario documented in code comments. Games with thread pools or producer-consumer patterns trigger this on every lock contention timeout cycle.

Complexity Proof

ppsspp-0001/0002/0004: At W=100 waiting threads, T=200 timeout cycles:

• Defective: 200 × (100² / 2) = ~1,000,000 comparisons per contention burst
• Fixed: 200 × 100 = 20,000 comparisons (unordered_set shadow)
• 50× op reduction.

ppsspp-0003: At B=500 blocks per page, I=100 invalidations:

• Defective: 100 × (500 / 2) = ~25,000 comparisons
• Fixed: 100 × 1 = 100 lookups (unordered_set replacement)
• 250× op reduction.

Impact

PPSSPP emulates PlayStation Portable games on PC, Android, iOS, and other platforms — used by millions of users worldwide. The three synchronization defects (ppsspp-0001/0002/0004) fire in the HLE kernel, the core emulation layer that every PSP game relies on. Games that use producer-consumer threading, barrier synchronization, or tight semaphore loops hit these paths repeatedly. The JIT defect (ppsspp-0003) fires whenever self-modifying code or icache flushes invalidate compiled blocks — common in homebrew and some commercial titles.

The Fix

ppsspp-0001/0002/0004: Maintain a parallel std::unordered_set<SceUID> (waitingThreadSet) alongside each waitingThreads vector for O(1) dedup. Remove from set wherever the vector gets cleared or erased.

ppsspp-0003: Replace the std::vector<int> per page with an std::unordered_set<int> for O(1) membership test and removal.

Patch

Fixes available:

• defects/ppsspp/patch/ppsspp-0001-kernel-thread-waitingThreads-dedup.patch
• defects/ppsspp/patch/ppsspp-0002-kernel-semaphore-waitingThreads-dedup.patch
• defects/ppsspp/patch/ppsspp-0003-irjit-bypage-block-removal.patch
• defects/ppsspp/patch/ppsspp-0004-kernel-mutex-waitingThreads-dedup.patch

Four patches across sceKernelThread.cpp, sceKernelSemaphore.cpp, IRJit.cpp, and sceKernelMutex.cpp.

What We Ask

Patches ready for review.

1. Confirm receipt and assign a GitHub issue reference (hrydgard/ppsspp).
2. Assess severity — ppsspp-0001/0002/0004 fire in HLE kernel synchronization (hot path); ppsspp-0003 fires on JIT block invalidation.
3. Coordinate a disclosure date — we target 90 days from first contact.
4. We will credit the PPSSPP team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.