russell@unturf.com
0a580b313d
Authors: russell@unturf.com · brackishbert@gmail.com · foxhop.net · TimeHexOn.com Patches, unit tests, benchmarks, whitepaper, and outreach briefs. Public domain — no copyright claimed. Use freely.
232 lines
9.3 KiB
Java
232 lines
9.3 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* Unit test for buildkit-0001: cacheKeyStorage.HasLink() CWE-407.
|
||
*
|
||
* Defect: HasLink() in the v1 remote cache importer calls
|
||
* slices.Contains(it.links[l], target) where it.links[l] is a []string.
|
||
* For K cache entries each with L links, repeated HasLink() calls cost O(K×L).
|
||
*
|
||
* File: cache/remotecache/v1/cachestorage.go:244
|
||
* Symbol: (*cacheKeyStorage).HasLink — `slices.Contains(it.links[l], target)`
|
||
*
|
||
* Fix: Change the links value type from []string to map[string]struct{}.
|
||
* HasLink() becomes a map lookup: O(1). Building the map costs O(L) once.
|
||
* Total cost for K entries: O(K×L) build + O(K) queries = O(K×L) → amortized
|
||
* O(1) per query after build. Total work at K=L=100: from 10000 to ~200.
|
||
*
|
||
* Modeled here in Java:
|
||
* - []string ≡ List<String> (defective)
|
||
* - map[string]struct{} ≡ Set<String> (fixed)
|
||
* - nlink key ≡ String (simplified)
|
||
* - comparisons counted at the membership-test site
|
||
*
|
||
* Expected at K=L=100:
|
||
* defective ≈ K × L = 10000 (worst-case: target not found → full scan)
|
||
* fixed ≈ K + K×L = 10100 build + K = 10200 total, but query cost = K = 100
|
||
* ratio (query-only) > 10×
|
||
*/
|
||
public class BuildkitHasLinkTest {
|
||
|
||
// ── Defective: links stored as List<String>, HasLink = linear scan ────────
|
||
|
||
static class DefectiveCacheKeyStorage {
|
||
// maps cacheEntryID → linkKey → []string (list of target IDs)
|
||
final Map<String, Map<String, List<String>>> byID = new LinkedHashMap<>();
|
||
long comparisons = 0;
|
||
|
||
void addLink(String entryID, String linkKey, String targetID) {
|
||
byID.computeIfAbsent(entryID, k -> new LinkedHashMap<>())
|
||
.computeIfAbsent(linkKey, k -> new ArrayList<>())
|
||
.add(targetID);
|
||
}
|
||
|
||
/** slices.Contains equivalent: O(L) linear scan. */
|
||
boolean hasLink(String entryID, String linkKey, String target) {
|
||
Map<String, List<String>> links = byID.get(entryID);
|
||
if (links == null) return false;
|
||
List<String> targets = links.get(linkKey);
|
||
if (targets == null) return false;
|
||
for (String t : targets) {
|
||
comparisons++;
|
||
if (t.equals(target)) return true;
|
||
}
|
||
return false;
|
||
}
|
||
}
|
||
|
||
// ── Fixed: links stored as Set<String>, HasLink = O(1) map lookup ─────────
|
||
|
||
static class FixedCacheKeyStorage {
|
||
// maps cacheEntryID → linkKey → map[string]struct{} (set of target IDs)
|
||
final Map<String, Map<String, Set<String>>> byID = new LinkedHashMap<>();
|
||
long buildComparisons = 0; // cost of building the sets
|
||
long queryComparisons = 0; // cost of HasLink queries
|
||
|
||
void addLink(String entryID, String linkKey, String targetID) {
|
||
buildComparisons++; // one hash op per insertion
|
||
byID.computeIfAbsent(entryID, k -> new LinkedHashMap<>())
|
||
.computeIfAbsent(linkKey, k -> new HashSet<>())
|
||
.add(targetID);
|
||
}
|
||
|
||
/** map lookup equivalent: O(1). */
|
||
boolean hasLink(String entryID, String linkKey, String target) {
|
||
Map<String, Set<String>> links = byID.get(entryID);
|
||
if (links == null) return false;
|
||
Set<String> targets = links.get(linkKey);
|
||
if (targets == null) return false;
|
||
queryComparisons++; // O(1) hash lookup
|
||
return targets.contains(target);
|
||
}
|
||
|
||
long comparisons() { return buildComparisons + queryComparisons; }
|
||
}
|
||
|
||
// ── Simulation helpers ────────────────────────────────────────────────────
|
||
|
||
/**
|
||
* Populate K cache entries, each with L links under a single linkKey.
|
||
* Then query hasLink for each entry's last-inserted target (worst-case
|
||
* for the defective linear scan: target is at end of list).
|
||
*/
|
||
public static long simulateDefective(int K, int L) {
|
||
DefectiveCacheKeyStorage storage = new DefectiveCacheKeyStorage();
|
||
String linkKey = "lk:sha256:abc/0/selector";
|
||
String[] lastTarget = new String[K];
|
||
|
||
for (int k = 0; k < K; k++) {
|
||
String entryID = "entry_" + k;
|
||
for (int l = 0; l < L; l++) {
|
||
String targetID = "target_" + k + "_" + l;
|
||
storage.addLink(entryID, linkKey, targetID);
|
||
lastTarget[k] = targetID;
|
||
}
|
||
}
|
||
|
||
// Query: check each entry's last target (worst-case: at end of list → full scan)
|
||
for (int k = 0; k < K; k++) {
|
||
String entryID = "entry_" + k;
|
||
boolean found = storage.hasLink(entryID, linkKey, lastTarget[k]);
|
||
assert found : "hasLink should return true for known target";
|
||
}
|
||
return storage.comparisons;
|
||
}
|
||
|
||
public static long simulateFixedQuery(int K, int L) {
|
||
FixedCacheKeyStorage storage = new FixedCacheKeyStorage();
|
||
String linkKey = "lk:sha256:abc/0/selector";
|
||
String[] lastTarget = new String[K];
|
||
|
||
for (int k = 0; k < K; k++) {
|
||
String entryID = "entry_" + k;
|
||
for (int l = 0; l < L; l++) {
|
||
String targetID = "target_" + k + "_" + l;
|
||
storage.addLink(entryID, linkKey, targetID);
|
||
lastTarget[k] = targetID;
|
||
}
|
||
}
|
||
|
||
// same queries
|
||
for (int k = 0; k < K; k++) {
|
||
String entryID = "entry_" + k;
|
||
boolean found = storage.hasLink(entryID, linkKey, lastTarget[k]);
|
||
assert found : "hasLink should return true for known target";
|
||
}
|
||
return storage.queryComparisons; // only query cost, not build
|
||
}
|
||
|
||
// ── Tests ─────────────────────────────────────────────────────────────────
|
||
|
||
static void testCorrectnessMatch() {
|
||
DefectiveCacheKeyStorage def = new DefectiveCacheKeyStorage();
|
||
FixedCacheKeyStorage fix = new FixedCacheKeyStorage();
|
||
String linkKey = "lk:sha256:test/0/";
|
||
|
||
for (int i = 0; i < 5; i++) {
|
||
String eid = "e_" + i;
|
||
for (int j = 0; j < 5; j++) {
|
||
String tid = "t_" + i + "_" + j;
|
||
def.addLink(eid, linkKey, tid);
|
||
fix.addLink(eid, linkKey, tid);
|
||
}
|
||
}
|
||
|
||
// Check positive cases
|
||
for (int i = 0; i < 5; i++) {
|
||
String eid = "e_" + i;
|
||
for (int j = 0; j < 5; j++) {
|
||
String tid = "t_" + i + "_" + j;
|
||
boolean d = def.hasLink(eid, linkKey, tid);
|
||
boolean f = fix.hasLink(eid, linkKey, tid);
|
||
assert d == f : "hasLink mismatch for " + eid + "/" + tid + ": def=" + d + " fix=" + f;
|
||
assert d : "expected true for known link";
|
||
}
|
||
}
|
||
|
||
// Check negative cases
|
||
boolean d = def.hasLink("e_0", linkKey, "nonexistent");
|
||
boolean f = fix.hasLink("e_0", linkKey, "nonexistent");
|
||
assert !d && !f : "hasLink should return false for unknown target";
|
||
|
||
System.out.println("PASS testCorrectnessMatch");
|
||
}
|
||
|
||
static void testDefectiveGrowsQuadratically() {
|
||
long prev = -1;
|
||
for (int S : new int[]{10, 20, 40}) {
|
||
long c = simulateDefective(S, S);
|
||
if (prev > 0) {
|
||
double ratio = (double) c / prev;
|
||
assert ratio > 3.0
|
||
: "defective should grow >3x when K=L doubled; got " + ratio + " at K=L=" + S;
|
||
}
|
||
prev = c;
|
||
}
|
||
System.out.println("PASS testDefectiveGrowsQuadratically");
|
||
}
|
||
|
||
static void testFixedQueryGrowsLinearly() {
|
||
long prev = -1;
|
||
for (int S : new int[]{10, 20, 40}) {
|
||
long c = simulateFixedQuery(S, S);
|
||
if (prev > 0) {
|
||
double ratio = (double) c / prev;
|
||
assert ratio < 2.5
|
||
: "fixed query cost should grow ~2x when K doubled; got " + ratio + " at K=L=" + S;
|
||
}
|
||
prev = c;
|
||
}
|
||
System.out.println("PASS testFixedQueryGrowsLinearly");
|
||
}
|
||
|
||
static void testRatioAtScale() {
|
||
int K = 100, L = 100;
|
||
long defComp = simulateDefective(K, L);
|
||
long fixQuery = simulateFixedQuery(K, L);
|
||
double ratio = (double) defComp / fixQuery;
|
||
|
||
// defective: K queries × L comparisons each = K*L = 10000
|
||
assert defComp == (long) K * L
|
||
: "defective comparisons should be K*L=" + (K * L) + "; got " + defComp;
|
||
// fixed query: K queries × 1 = K = 100
|
||
assert fixQuery == K
|
||
: "fixed query comparisons should be K=" + K + "; got " + fixQuery;
|
||
assert ratio > 10.0
|
||
: "ratio should be >10x at K=L=100; got " + ratio;
|
||
|
||
System.out.printf(
|
||
"PASS testRatioAtScale (defective=%d, fixed_query=%d, ratio=%.1fx)%n",
|
||
defComp, fixQuery, ratio);
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
testCorrectnessMatch();
|
||
testDefectiveGrowsQuadratically();
|
||
testFixedQueryGrowsLinearly();
|
||
testRatioAtScale();
|
||
System.out.println("All buildkit-0001 tests passed.");
|
||
}
|
||
}
|