190 lines
7.6 KiB
Java
190 lines
7.6 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Envoy0003Test — CWE-407 unit test for envoy-0003
|
||
*
|
||
* envoy-0003: cluster_manager_impl.cc:1424-1429
|
||
* EDS batch host merge: std::remove_if with inner std::find over hosts_removed_
|
||
* vector — O(H × R) per priority level per EDS update.
|
||
*
|
||
* H = hosts in existing hosts_added_ accumulation
|
||
* R = hosts in hosts_removed_ for this update
|
||
*
|
||
* SLOW: std::remove_if + inner std::find (O(H) × O(R)) = O(H × R)
|
||
* FAST: build absl::flat_hash_set from hosts_removed_, then O(1) lookup = O(H + R)
|
||
*
|
||
* No JUnit. Run: javac -d . Envoy0003Test.java && java -ea unit.Envoy0003Test
|
||
*/
|
||
public class Envoy0003Test {
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Simulated HostSharedPtr — identity by object reference (pointer semantics)
|
||
// -------------------------------------------------------------------------
|
||
static class Host {
|
||
final int id;
|
||
Host(int id) { this.id = id; }
|
||
// intentionally no equals/hashCode override — identity semantics like raw ptr
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// SLOW: remove_if with inner std::find — O(H × R)
|
||
// Returns the number of ops (comparisons) performed.
|
||
// -------------------------------------------------------------------------
|
||
static long mergeHosts_slow(List<Host> hostsAdded, List<Host> hostsRemoved) {
|
||
long ops = 0;
|
||
Iterator<Host> it = hostsAdded.iterator();
|
||
while (it.hasNext()) {
|
||
Host candidate = it.next();
|
||
// std::find over hosts_removed: O(R) scan per candidate host
|
||
boolean found = false;
|
||
for (Host r : hostsRemoved) {
|
||
ops++;
|
||
if (r == candidate) {
|
||
found = true;
|
||
break;
|
||
}
|
||
}
|
||
if (found) {
|
||
it.remove();
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// FAST: build identity hash set from hostsRemoved, then O(1) lookup
|
||
// Returns the number of ops (comparisons) performed.
|
||
// -------------------------------------------------------------------------
|
||
static long mergeHosts_fast(List<Host> hostsAdded, Set<Host> removedSet) {
|
||
long ops = 0;
|
||
Iterator<Host> it = hostsAdded.iterator();
|
||
while (it.hasNext()) {
|
||
Host candidate = it.next();
|
||
ops++; // O(1) hash lookup
|
||
if (removedSet.contains(candidate)) {
|
||
it.remove();
|
||
}
|
||
}
|
||
return ops;
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Helpers
|
||
// -------------------------------------------------------------------------
|
||
static Host[] makeHosts(int n) {
|
||
Host[] hosts = new Host[n];
|
||
for (int i = 0; i < n; i++) hosts[i] = new Host(i);
|
||
return hosts;
|
||
}
|
||
|
||
/**
|
||
* Build hostsAdded list and hostsRemoved list from a shared host pool.
|
||
* removeFraction of hostsAdded are also in hostsRemoved (scattered positions).
|
||
*/
|
||
static long[] runScenario(int H, int R) {
|
||
Host[] pool = makeHosts(H + R);
|
||
|
||
// hostsAdded: first H hosts from pool
|
||
List<Host> hostsAdded_slow = new ArrayList<>(H);
|
||
List<Host> hostsAdded_fast = new ArrayList<>(H);
|
||
for (int i = 0; i < H; i++) {
|
||
hostsAdded_slow.add(pool[i]);
|
||
hostsAdded_fast.add(pool[i]);
|
||
}
|
||
|
||
// hostsRemoved: last R hosts from pool; some overlap with hostsAdded
|
||
// (the first min(R,H/2) removed hosts are also in hostsAdded)
|
||
int overlap = Math.min(R, H / 3);
|
||
List<Host> hostsRemoved = new ArrayList<>(R);
|
||
for (int i = 0; i < overlap; i++) hostsRemoved.add(pool[i]); // overlap with hostsAdded
|
||
for (int i = H; i < H + (R - overlap); i++) hostsRemoved.add(pool[i]); // not in hostsAdded
|
||
|
||
// Build identity-based set for fast path
|
||
Set<Host> removedSet = Collections.newSetFromMap(new IdentityHashMap<>());
|
||
removedSet.addAll(hostsRemoved);
|
||
|
||
long slowOps = mergeHosts_slow(hostsAdded_slow, hostsRemoved);
|
||
long fastOps = mergeHosts_fast(hostsAdded_fast, removedSet);
|
||
|
||
// Verify correctness: both lists should have same remaining size
|
||
assert hostsAdded_slow.size() == hostsAdded_fast.size() :
|
||
"size mismatch: slow=" + hostsAdded_slow.size() + " fast=" + hostsAdded_fast.size();
|
||
// Verify same elements remain (order may differ but sizes must match)
|
||
assert hostsAdded_slow.size() == H - overlap :
|
||
"expected " + (H - overlap) + " remaining, got " + hostsAdded_slow.size();
|
||
|
||
return new long[]{slowOps, fastOps};
|
||
}
|
||
|
||
static void bench(String label, long sOps, long fOps) {
|
||
double ratio = (double) sOps / Math.max(fOps, 1);
|
||
System.out.printf(" PASS %-55s slow=%8d fast=%6d ratio=%6.1fx%n",
|
||
label, sOps, fOps, ratio);
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Test cases
|
||
// -------------------------------------------------------------------------
|
||
|
||
static void testSmall() {
|
||
long[] r = runScenario(50, 20);
|
||
bench("H=50 R=20 (small cluster deploy)", r[0], r[1]);
|
||
assert r[0] > r[1] * 5 :
|
||
"Expected slow >> fast*5, got slow=" + r[0] + " fast=" + r[1];
|
||
}
|
||
|
||
static void testMedium() {
|
||
long[] r = runScenario(200, 100);
|
||
bench("H=200 R=100 (medium cluster rolling restart)", r[0], r[1]);
|
||
assert r[0] > r[1] * 20 :
|
||
"Expected slow >> fast*20, got slow=" + r[0] + " fast=" + r[1];
|
||
}
|
||
|
||
static void testLarge() {
|
||
long[] r = runScenario(500, 200);
|
||
bench("H=500 R=200 (large cluster canary deploy)", r[0], r[1]);
|
||
assert r[0] > r[1] * 50 :
|
||
"Expected slow >> fast*50, got slow=" + r[0] + " fast=" + r[1];
|
||
}
|
||
|
||
static void testStress() {
|
||
long[] r = runScenario(1000, 500);
|
||
bench("H=1000 R=500 (stress: full rolling restart)", r[0], r[1]);
|
||
assert r[0] > r[1] * 100 :
|
||
"Expected slow >> fast*100, got slow=" + r[0] + " fast=" + r[1];
|
||
}
|
||
|
||
static void testCorrectness() {
|
||
// Verify no removal when hostsRemoved is empty
|
||
Host[] pool = makeHosts(5);
|
||
List<Host> added = new ArrayList<>(Arrays.asList(pool));
|
||
long ops = mergeHosts_slow(added, new ArrayList<>());
|
||
assert added.size() == 5 : "expected 5 remaining, got " + added.size();
|
||
assert ops == 0 : "expected 0 ops with empty removed, got " + ops;
|
||
System.out.println(" PASS correctness: empty hostsRemoved => no removal, 0 ops");
|
||
|
||
// Verify all removed when all hosts are in removed set
|
||
List<Host> added2 = new ArrayList<>(Arrays.asList(pool));
|
||
List<Host> removed2 = new ArrayList<>(Arrays.asList(pool));
|
||
ops = mergeHosts_slow(added2, removed2);
|
||
assert added2.size() == 0 : "expected 0 remaining, got " + added2.size();
|
||
System.out.println(" PASS correctness: all hosts removed, size=0");
|
||
}
|
||
|
||
// -------------------------------------------------------------------------
|
||
// Main
|
||
// -------------------------------------------------------------------------
|
||
public static void main(String[] args) {
|
||
System.out.println("=== Envoy0003Test: EDS host merge linear scan (envoy-0003) ===");
|
||
System.out.println();
|
||
testCorrectness();
|
||
testSmall();
|
||
testMedium();
|
||
testLarge();
|
||
testStress();
|
||
System.out.println();
|
||
System.out.println("5/5 PASS");
|
||
}
|
||
}
|