package zitcli
import (
"container/list"
"log"
"sync"
"sync/atomic"
"time"
"unsafe"
)
// lru is a byte-bounded, least-recently-used memo over zit reads.
//
// Bounded by BYTES, not entries, because the values are store content:
// an entry-count cap is fine for listings and meaningless for anything
// whose entries vary by orders of magnitude — one Cat can be a 30MB
// blob, and sixty-four of them is two gigabytes of resident memory. A
// diff has the same shape: a one-line fix and a thousand-file merge are
// both one entry and nothing like one cost.
//
// Per repository rather than shared across the fleet. A shared budget
// uses memory better, but it lets one busy store evict another's
// entries, so a reader on a quiet repository pays for traffic they have
// nothing to do with. Predictable beats optimal here.
//
// Per-repository budgets alone do not bound the process, though: they
// add up. The blob budget was sized as "eleven repositories at that
// budget is a ceiling the process can actually afford", and the fleet
// grew to thirty-three, two of them (netbsd-src, pkgsrc) with listings
// of 200,000 and 68,000 files. A crawler walking check-ins across the
// fleet filled every budget at once and the forge was killed for memory
// at 11.6 GB on 2026-10-15. So every cache also charges one forge-wide
// ceiling (SetCacheCeiling), and a put that takes the forge over it
// evicts the PUTTING cache's own least-recently-used entries: the
// repository being crawled pays for its crawl, and a quiet one keeps
// what it holds, which is the trade the per-repository budget exists
// for. What a quiet repository cannot do while the forge is full is add:
// its put evicts its own oldest entries and, if that is not enough,
// drops the new one, so it misses rather than taking from another.
//
// EVERY key must be derived from an immutable version. That is not a
// property this type can check, so it is the caller's obligation and the
// reason ops resolve names to hashes before reading — see
// Deps.resolveVersion. A moving name cached here would serve stale
// content forever.
type lru[V any] struct {
mu sync.Mutex
max int64
used int64
ceil *ceiling
ll *list.List // front = most recently used
items map[string]*list.Element // key -> element holding *entry[V]
sizeOf func(V) int64
// repo and kind name this cache in the log line a refused value
// writes, and dropLogged is when it last wrote one.
repo, kind string
dropLogged time.Time
}
type entry[V any] struct {
key string
val V
size int64
}
func newLRU[V any](max int64, sizeOf func(V) int64) *lru[V] {
return &lru[V]{max: max, ceil: &forgeCeiling, ll: list.New(), items: map[string]*list.Element{}, sizeOf: sizeOf}
}
// ceiling is a byte budget shared by every cache that charges it.
// Zero means none.
type ceiling struct {
max atomic.Int64
used atomic.Int64
}
// forgeCeiling is the one every cache in the process charges.
var forgeCeiling ceiling
// SetCacheCeiling bounds the bytes all repositories' caches hold
// together; 0 removes the bound. A server sets it once at startup.
func SetCacheCeiling(bytes int64) { forgeCeiling.max.Store(bytes) }
func (f *ceiling) limit() int64 { return f.max.Load() }
func (f *ceiling) over() bool {
m := f.max.Load()
return m > 0 && f.used.Load() > m
}
// charge moves n bytes in or out of this cache and its ceiling.
func (c *lru[V]) charge(n int64) {
c.used += n
c.ceil.used.Add(n)
}
// get returns a cached value and marks it recently used. The value is
// the cached one, so callers must not mutate it — every caller hands it
// straight to a reader or a parser.
func (c *lru[V]) get(key string) (V, bool) {
var zero V
if c == nil {
return zero, false
}
c.mu.Lock()
defer c.mu.Unlock()
el, ok := c.items[key]
if !ok {
return zero, false
}
c.ll.MoveToFront(el)
return el.Value.(*entry[V]).val, true
}
// put stores a value, evicting least-recently-used entries until it
// fits. A single value larger than the whole budget is NOT cached and
// not an error: admitting it would evict everything else to hold one
// item, which is worse than missing.
func (c *lru[V]) put(key string, val V) {
if c == nil {
return
}
size := c.sizeOf(val)
if size > c.max || (c.ceil.limit() > 0 && size > c.ceil.limit()) {
c.mu.Lock()
c.dropped(size, "larger than the budget")
c.mu.Unlock()
return
}
c.mu.Lock()
defer c.mu.Unlock()
var e *entry[V]
if el, ok := c.items[key]; ok {
e = el.Value.(*entry[V])
c.charge(size - e.size)
e.val, e.size = val, size
c.ll.MoveToFront(el)
} else {
e = &entry[V]{key: key, val: val, size: size}
c.items[key] = c.ll.PushFront(e)
c.charge(e.size)
}
// Over this cache's budget, or over the forge's: either way it is
// this cache's own entries that go, oldest first. If that reaches
// the new entry itself, this cache has nothing left to give and the
// value is simply not kept.
for c.used > c.max || c.ceil.over() {
back := c.ll.Back()
if back == nil {
return
}
old := c.ll.Remove(back).(*entry[V])
delete(c.items, old.key)
c.charge(-old.size)
if old == e {
c.dropped(size, "no room left")
return
}
}
}
// dropped logs a value this cache could not keep, at most once a minute
// per cache: a miss that repeats is otherwise invisible, and on a large
// store it is the difference between milliseconds and a minute. The
// caller holds mu.
func (c *lru[V]) dropped(size int64, why string) {
if c.repo == "" || time.Since(c.dropLogged) < time.Minute {
return
}
c.dropLogged = time.Now()
log.Printf("zitcli: %s %s cache did not keep %d MB (%s): it holds %d MB of %d, the forge's caches %d MB of %d",
c.repo, c.kind, size>>20, why, c.used>>20, c.max>>20, c.ceil.used.Load()>>20, c.ceil.limit()>>20)
}
// release empties the cache and gives its bytes back to the ceiling.
// Called when the Client that owns it is collected, so a dropped
// repository (unregistered, removed, re-registered) stops counting
// against the forge.
func (c *lru[V]) release() {
if c == nil {
return
}
c.mu.Lock()
defer c.mu.Unlock()
c.charge(-c.used)
c.ll.Init()
clear(c.items)
}
// stats reports entries and bytes held, for tests and diagnostics.
func (c *lru[V]) stats() (entries int, bytes int64) {
if c == nil {
return 0, 0
}
c.mu.Lock()
defer c.mu.Unlock()
return len(c.items), c.used
}
// CacheUse is what one of a repository's caches holds.
type CacheUse struct {
Kind string `json:"kind"`
Entries int `json:"entries"`
Bytes int64 `json:"bytes"`
Budget int64 `json:"budget"`
}
func (c *lru[V]) use() CacheUse {
n, b := c.stats()
return CacheUse{Kind: c.kind, Entries: n, Bytes: b, Budget: c.max}
}
// ForgeCacheUse reports the bytes every repository's caches hold
// together and the ceiling over them (0: none).
func ForgeCacheUse() (used, limit int64) {
return forgeCeiling.used.Load(), forgeCeiling.limit()
}
// blobCache is the LRU over file contents.
type blobCache = lru[[]byte]
func newBlobCache(max int64) *blobCache {
// cap, not len: a blob is the buffer zit's output was read into,
// which grows by doubling, so its length undercounted what it held
// by as much as half.
return newLRU[[]byte](max, func(v []byte) int64 { return int64(cap(v)) })
}
// listingCache is the LRU over file listings. Bounded by bytes like the
// others: it was 64 entries, which is nothing on quarry's own store and
// over two gigabytes on netbsd-src, whose one listing is 200,000 files.
type listingCache = lru[[]LsEntry]
const lsEntryLineBytes = 32
func newListingCache(max int64) *listingCache {
return newLRU[[]LsEntry](max, func(v []LsEntry) int64 {
// lsEntryLineBytes: the strings are substrings of zit's whole
// output, which they keep alive, so the rest of each line (size,
// kind, separators) is held too.
n := int64(cap(v)) * int64(unsafe.Sizeof(LsEntry{}))
for _, e := range v {
n += int64(len(e.Blob)+len(e.Name)+len(e.Perm)) + lsEntryLineBytes
}
return n
})
}
// diffCache is the LRU over check-in diffs.
//
// The pair of hashes is immutable, so a hit is permanently correct and
// this memo never needs invalidating — the reason a diff is worth
// caching at all. What it does need is a bound that reflects what a
// diff can weigh, which is why it is the same byte-budgeted structure
// as the blob cache rather than a count of entries.
type diffCache = lru[diffResult]
func newDiffCache(max int64) *diffCache {
return newLRU[diffResult](max, func(v diffResult) int64 {
// The unified text dominates; the entry list is names and
// statuses. Counted rather than ignored because a merge across
// a thousand files carries a thousand of them.
n := int64(len(v.unified))
for _, e := range v.entries {
n += int64(len(e.Name) + len(e.Status))
}
return n
})
}