223 lines
8 KiB
Java
223 lines
8 KiB
Java
package unit;
|
||
|
||
import java.util.ArrayList;
|
||
import java.util.HashSet;
|
||
import java.util.List;
|
||
import java.util.Set;
|
||
import java.util.Objects;
|
||
|
||
/**
|
||
* CWE-407 unit test: elasticsearch-004
|
||
* IndexGraveyard.containsIndex — List<Tombstone> linear scan called per-index
|
||
* inside DanglingIndicesState loop → O(I × T).
|
||
*
|
||
* Slow path: for (Tombstone t : tombstones) { if t.equals(index) ... } — O(T) per call.
|
||
* Fast path: HashSet<Index>.contains() — O(1) per call.
|
||
*
|
||
* Compile: javac -d . IndexGraveyardDanglingContains.java
|
||
* Run: java -ea unit.IndexGraveyardDanglingContains
|
||
*/
|
||
public class IndexGraveyardDanglingContains {
|
||
|
||
/** Minimal stand-in for an Index (name + uuid). */
|
||
static final class Index {
|
||
final String name;
|
||
final String uuid;
|
||
|
||
Index(String name, String uuid) {
|
||
this.name = name;
|
||
this.uuid = uuid;
|
||
}
|
||
|
||
@Override
|
||
public boolean equals(Object o) {
|
||
if (!(o instanceof Index)) return false;
|
||
Index other = (Index) o;
|
||
return name.equals(other.name) && uuid.equals(other.uuid);
|
||
}
|
||
|
||
@Override
|
||
public int hashCode() {
|
||
return Objects.hash(name, uuid);
|
||
}
|
||
}
|
||
|
||
/** Minimal stand-in for a Tombstone. */
|
||
static final class Tombstone {
|
||
final Index index;
|
||
Tombstone(Index index) { this.index = index; }
|
||
Index getIndex() { return index; }
|
||
}
|
||
|
||
// ---- Slow path: List-based linear scan per call (O(T)) ----
|
||
|
||
static boolean slowContainsIndex(List<Tombstone> tombstones, Index index) {
|
||
for (Tombstone tombstone : tombstones) {
|
||
if (tombstone.getIndex().equals(index)) {
|
||
return true;
|
||
}
|
||
}
|
||
return false;
|
||
}
|
||
|
||
/** Simulates DanglingIndicesState with slow O(I×T) behaviour. */
|
||
static long slowFindDanglingIndices(List<Index> diskIndices, List<Tombstone> tombstones) {
|
||
long ops = 0;
|
||
List<Index> dangling = new ArrayList<>();
|
||
for (Index index : diskIndices) {
|
||
for (Tombstone t : tombstones) { // counts each tombstone comparison
|
||
ops++;
|
||
if (t.getIndex().equals(index)) break;
|
||
}
|
||
if (!slowContainsIndex(tombstones, index)) {
|
||
dangling.add(index);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ---- Fast path: HashSet O(1) membership test ----
|
||
|
||
static long fastFindDanglingIndices(List<Index> diskIndices, List<Tombstone> tombstones) {
|
||
long ops = 0;
|
||
// Build set once: O(T)
|
||
Set<Index> graveyardSet = new HashSet<>(tombstones.size() * 2);
|
||
for (Tombstone t : tombstones) {
|
||
graveyardSet.add(t.getIndex());
|
||
ops++;
|
||
}
|
||
// Check each disk index: O(1) per check
|
||
List<Index> dangling = new ArrayList<>();
|
||
for (Index index : diskIndices) {
|
||
ops++; // O(1) hash lookup
|
||
if (!graveyardSet.contains(index)) {
|
||
dangling.add(index);
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// ---- Correctness check ----
|
||
|
||
static List<Index> slowResult(List<Index> diskIndices, List<Tombstone> tombstones) {
|
||
List<Index> dangling = new ArrayList<>();
|
||
for (Index index : diskIndices) {
|
||
if (!slowContainsIndex(tombstones, index)) {
|
||
dangling.add(index);
|
||
}
|
||
}
|
||
return dangling;
|
||
}
|
||
|
||
static List<Index> fastResult(List<Index> diskIndices, List<Tombstone> tombstones) {
|
||
Set<Index> graveyardSet = new HashSet<>();
|
||
for (Tombstone t : tombstones) graveyardSet.add(t.getIndex());
|
||
List<Index> dangling = new ArrayList<>();
|
||
for (Index index : diskIndices) {
|
||
if (!graveyardSet.contains(index)) dangling.add(index);
|
||
}
|
||
return dangling;
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
int passed = 0;
|
||
|
||
// ---- Test 1: correctness at small scale ----
|
||
{
|
||
List<Tombstone> tombstones = new ArrayList<>();
|
||
List<Index> diskIndices = new ArrayList<>();
|
||
// 10 tombstones, 20 disk indices — 5 overlap
|
||
for (int i = 0; i < 10; i++) {
|
||
tombstones.add(new Tombstone(new Index("idx-" + i, "uuid-" + i)));
|
||
}
|
||
for (int i = 0; i < 20; i++) {
|
||
diskIndices.add(new Index("idx-" + i, "uuid-" + i));
|
||
}
|
||
List<Index> slow = slowResult(diskIndices, tombstones);
|
||
List<Index> fast = fastResult(diskIndices, tombstones);
|
||
assert slow.size() == fast.size()
|
||
: "FAIL: slow=" + slow.size() + " fast=" + fast.size();
|
||
assert slow.containsAll(fast) && fast.containsAll(slow)
|
||
: "FAIL: result mismatch";
|
||
System.out.println("PASS test1: correctness (small scale) — " + fast.size() + " dangling");
|
||
passed++;
|
||
}
|
||
|
||
// ---- Test 2: correctness — all tombstoned ----
|
||
{
|
||
List<Tombstone> tombstones = new ArrayList<>();
|
||
List<Index> diskIndices = new ArrayList<>();
|
||
for (int i = 0; i < 50; i++) {
|
||
tombstones.add(new Tombstone(new Index("idx-" + i, "uuid-" + i)));
|
||
diskIndices.add(new Index("idx-" + i, "uuid-" + i));
|
||
}
|
||
List<Index> slow = slowResult(diskIndices, tombstones);
|
||
List<Index> fast = fastResult(diskIndices, tombstones);
|
||
assert slow.size() == 0 : "FAIL: expected 0 dangling";
|
||
assert fast.size() == 0 : "FAIL: expected 0 dangling (fast)";
|
||
System.out.println("PASS test2: correctness (all tombstoned) — " + fast.size() + " dangling");
|
||
passed++;
|
||
}
|
||
|
||
// ---- Test 3: operation count ratio ----
|
||
{
|
||
int I = 500; // dangling index files on disk
|
||
int T = 500; // tombstones (max default)
|
||
List<Tombstone> tombstones = new ArrayList<>();
|
||
List<Index> diskIndices = new ArrayList<>();
|
||
// None overlap → worst case for slow (full scan every time)
|
||
for (int i = 0; i < T; i++) {
|
||
tombstones.add(new Tombstone(new Index("tomb-" + i, "uuid-t" + i)));
|
||
}
|
||
for (int i = 0; i < I; i++) {
|
||
diskIndices.add(new Index("disk-" + i, "uuid-d" + i));
|
||
}
|
||
|
||
long slowOps = slowFindDanglingIndices(diskIndices, tombstones);
|
||
long fastOps = fastFindDanglingIndices(diskIndices, tombstones);
|
||
double ratio = (double) slowOps / fastOps;
|
||
|
||
System.out.printf("PASS test3: I=%d T=%d slow=%d ops fast=%d ops ratio=%.1fx%n",
|
||
I, T, slowOps, fastOps, ratio);
|
||
assert ratio >= 10.0
|
||
: "FAIL: ratio " + ratio + " < 10x at I=" + I + " T=" + T;
|
||
passed++;
|
||
}
|
||
|
||
// ---- Test 4: timing benchmark ----
|
||
{
|
||
int I = 2000;
|
||
int T = 500;
|
||
List<Tombstone> tombstones = new ArrayList<>();
|
||
List<Index> diskIndices = new ArrayList<>();
|
||
for (int i = 0; i < T; i++) {
|
||
tombstones.add(new Tombstone(new Index("tomb-" + i, "uuid-t" + i)));
|
||
}
|
||
for (int i = 0; i < I; i++) {
|
||
diskIndices.add(new Index("disk-" + i, "uuid-d" + i));
|
||
}
|
||
|
||
int reps = 200;
|
||
|
||
long t0 = System.nanoTime();
|
||
for (int r = 0; r < reps; r++) slowResult(diskIndices, tombstones);
|
||
long slowNs = System.nanoTime() - t0;
|
||
|
||
long t1 = System.nanoTime();
|
||
for (int r = 0; r < reps; r++) fastResult(diskIndices, tombstones);
|
||
long fastNs = System.nanoTime() - t1;
|
||
|
||
double ratio = (double) slowNs / fastNs;
|
||
System.out.printf("PASS test4: timing I=%d T=%d slow=%.1fms fast=%.1fms ratio=%.1fx%n",
|
||
I, T,
|
||
slowNs / 1e6 / reps,
|
||
fastNs / 1e6 / reps,
|
||
ratio);
|
||
assert ratio >= 10.0
|
||
: "FAIL: timing ratio " + ratio + " < 10x";
|
||
passed++;
|
||
}
|
||
|
||
System.out.println(passed + "/" + passed + " PASS");
|
||
}
|
||
}
|