java-topology/tools/tickets/defects/buildkit-0001.md

id	repo	file	line	status	severity	complexity	pattern
buildkit-0001	moby/buildkit	cache/remotecache/v1/cachestorage.go	244	unpatched	MEDIUM	O(K × L) — K cache keys imported, L links per key	slices.Contains on []string links slice in HasLink(); in-memory backend uses map[string]struct{} (O(1)) but v1 disk importer uses []string (O(n))

Description

cacheKeyStorage.HasLink() in the v1 remote cache importer checks link existence with:

if slices.Contains(it.links[l], target) {  // O(|links|)

it.links is map[nlink][]string — links stored as string slices. The in-memory backend (memorycachestorage.go:233) correctly uses map[string]struct{} for O(1) lookup. The two backends are inconsistent.

Call context

HasLink is called from cachemanager.go:397 inside a loop over all cache keys for a result. For each key, it checks each link before adding it. For a remote cache import with K cache entries each having L links, the total cost is O(K × L) comparisons. For a large monorepo build with hundreds of cached layers, this is measurable.

Activation

docker buildx build --cache-from=registry://... — the v1 remote cache import path. Every --cache-from invocation with a registry cache hits this code.

Fix

Change map[nlink][]string to map[nlink]map[string]struct{} in itemWithOutgoingLinks, matching the in-memory backend exactly:

// Before
type itemWithOutgoingLinks struct {
    item  *item
    links map[nlink][]string
}

// After
type itemWithOutgoingLinks struct {
    item  *item
    links map[nlink]map[string]struct{}
}

Update addItemToStorage to use links[cl][id] = struct{}{} instead of append, and HasLink to use _, ok := it.links[l][target] instead of slices.Contains.

Work items

• patch
• unit test (operation count: HasLink calls before/after on cache with L=100 links)
• integration test (docker buildx build --cache-from with large registry cache)