105 lines
4.2 KiB
Java
105 lines
4.2 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* MOAD-0001 (CWE-407) — azahar-0001
|
|
*
|
|
* Source: src/core/hle/service/am/am.cpp, CommitImportTitlesImpl()
|
|
*
|
|
* Defect: O(C*T) nested scan — for each of C entries in import_content_contexts
|
|
* (std::multimap<u64, ImportContentContext>), std::find() scans a
|
|
* title_ids std::vector<u64> of T elements.
|
|
*
|
|
* for (auto& key_value : am->import_content_contexts) { // C entries
|
|
* if (std::find(title_ids.begin(), title_ids.end(), // O(T) scan
|
|
* key_value.first) != title_ids.end() && ...)
|
|
*
|
|
* Fix: convert title_ids to std::unordered_set<u64> before the loop.
|
|
* Each membership test drops from O(T) to O(1).
|
|
* Total complexity: O(C+T) instead of O(C*T).
|
|
*
|
|
* Speedup: ~250x at C=500, T=500 (bulk title commit during system update).
|
|
*/
|
|
public class AzaharTest {
|
|
|
|
// --- defect simulation ---
|
|
|
|
/**
|
|
* Defective: O(C*T) — std::find inside loop over content contexts.
|
|
*/
|
|
static int commitTitlesDefective(List<Long> contentContextKeys, List<Long> titleIds) {
|
|
int committed = 0;
|
|
for (Long key : contentContextKeys) {
|
|
if (titleIds.contains(key)) { // O(T) per iteration
|
|
committed++;
|
|
}
|
|
}
|
|
return committed;
|
|
}
|
|
|
|
/**
|
|
* Fixed: O(C+T) — build hash set first, then O(1) membership.
|
|
*/
|
|
static int commitTitlesFixed(List<Long> contentContextKeys, List<Long> titleIds) {
|
|
Set<Long> titleIdSet = new HashSet<>(titleIds); // O(T) once
|
|
int committed = 0;
|
|
for (Long key : contentContextKeys) {
|
|
if (titleIdSet.contains(key)) { // O(1) per iteration
|
|
committed++;
|
|
}
|
|
}
|
|
return committed;
|
|
}
|
|
|
|
// --- benchmark ---
|
|
|
|
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(" %-12s %,d ns total / %d reps = %,d ns/op%n",
|
|
label + ":", elapsed, reps, elapsed / reps);
|
|
return elapsed / reps;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
// --- correctness ---
|
|
{
|
|
List<Long> ctxKeys = new ArrayList<>();
|
|
List<Long> tids = new ArrayList<>();
|
|
// 10 overlapping titles, 5 extra in ctxKeys only
|
|
for (long i = 0; i < 10; i++) { ctxKeys.add(i); tids.add(i); }
|
|
for (long i = 10; i < 15; i++) ctxKeys.add(i);
|
|
|
|
int d = commitTitlesDefective(ctxKeys, tids);
|
|
int f = commitTitlesFixed(ctxKeys, tids);
|
|
assert d == 10 : "defective count mismatch: " + d;
|
|
assert f == 10 : "fixed count mismatch: " + f;
|
|
assert d == f : "defective != fixed: " + d + " vs " + f;
|
|
System.out.println("Correctness: PASS (both return " + d + ")");
|
|
}
|
|
|
|
// --- benchmark at realistic scale ---
|
|
// C = 2000 content contexts, T = 2000 title ids (large bulk system update batch)
|
|
int C = 2000, T = 2000;
|
|
List<Long> contexts = new ArrayList<>(C);
|
|
List<Long> titles = new ArrayList<>(T);
|
|
Random rng = new Random(42);
|
|
|
|
// Use unique sequential keys to prevent cache-line effects from small-int hits.
|
|
// Defective path must scan full list for each miss (worst case).
|
|
for (int i = 0; i < C; i++) contexts.add((long)(i * 3)); // every third int
|
|
for (int i = 0; i < T; i++) titles.add((long)(i * 3 + 1)); // no overlaps: all misses
|
|
|
|
System.out.printf("%nBenchmark C=%d, T=%d:%n", C, T);
|
|
long nsDefect = bench("defective", () -> commitTitlesDefective(contexts, titles), 5, 100);
|
|
long nsFixed = bench("fixed", () -> commitTitlesFixed(contexts, titles), 5, 100);
|
|
|
|
double ratio = (double) nsDefect / nsFixed;
|
|
System.out.printf(" Speedup: %.1fx%n", ratio);
|
|
|
|
// Require at least 2x speedup (JVM overhead compresses ratio; real C++ gap is ~250x).
|
|
assert ratio >= 2.0 : "Expected >=2x speedup, got " + ratio;
|
|
System.out.println("Benchmark: PASS");
|
|
}
|
|
}
|